超级顶点（稠密点）处理

    由于幂律分布的特点，超级顶点现象非常普遍。 例如社交网络中的影响力领袖（网红大V）、证券市场中的热门股票、银行系统中的四大行、交通网络中的枢纽站、互联网中的高流量网站等、电商网络中的爆款产品。

    在 Nebula Graph 2.6.1 中，一个 和其属性是一个 Key-Value（以该点的 VID 以及其他元信息作为 Key），其 Out-Edge Key-Value 和 In-Edge Key-Value 都存储在同一个 partition 中(具体原理详见存储架构，并且以 LSM-tree 的形式组织存放在硬盘（和缓存）中。

    因此不论是从该点出发的有向遍历，或者以该点为终点的有向遍历，都会涉及到大量的（最理想情况，当完成操作之后），或者大量的随机 IO（有关于该点和其出入边频繁的写入)。

    经验上说，当一个点的出入度超过 1 万时，就可以视为是稠密点。需要考虑一些特殊的设计和处理。

    Note

    Nebula Graph 中没有专用的字段来记录每个点的出度和入度，因此无法预知哪些点会是超级节点。一个折中办法是使用 Spark 周期性地计算和统计。

    Nebula Graph 2.6.1 属性索引的设计复用了存储模块 RocksDB 的功能，这种情况下的索引会被建模为前缀相同的 Key。对于该属性的查找，（如果未能命中缓存，）会对应为硬盘上的“一次随机查找 + 一次前缀顺序扫描”，以找到对应的点 VID（此后，通常会从该顶点开始图遍历，这样又会发生该点对应 Key-Value 的一次随机读+顺序扫描）。当重复率越高，扫描范围就越大。

    关于属性索引的原理详细介绍在博客《分布式图数据库 Nebula Graph 的 Index 实践》。

    经验上说，当重复属性值超过 1 万时，也需要特殊的设计和处理。

    建议的办法

    数据库端的常见办法

    1. ：重新组织 RocksDB 中数据的排列方式，减少随机读，增加顺序读。

    应用端的常见办法

    根据业务意义，将一些超级顶点拆分：

    • 删除多条边，合并为一条

      例如，一个转账场景： (账户A)-[转账]->(账户B)。每次建模为一条AB之间的边，那么(账户A)和(账户B)之间会有着数万十次转账的场景。

    • 切分顶点本身

      例如，对于的借款网络，某大型银行A的借款次数和借款人会非常的多。

      可以将该大行节点 A 拆分为多个相关联的子节点 A1、A2、A3,

    最后更新: September 17, 2021