超级顶点（稠密点）处理

原理介绍

在图论中，超级顶点（稠密点）是指一个点有着极多的相邻边。相邻边可以是出边（我指向谁）或者是入边（谁指向我）。

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

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

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

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

Note

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

重复属性索引

在属性图中，除了网络拓扑结构中的超级顶点，还有一类情况类似于超级顶点————某属性有极高重复率，也即”相同的点类型 Tag，不同的顶点 VID，同一属性字段，拥有相同属性值”。

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

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

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

建议的办法

数据库端的常见办法

  1. 截断: 只访问一定阈值的边，超过该阈值的其他边则不返回。
  2. Compact：重新组织 RocksDB 中数据的排列方式，减少随机读，增加顺序读。

应用端的常见办法

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

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

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

    按日、周、或者月为粒度，合并陈旧的转账明细。也就是批量删除陈旧的边，改为少量的边“月总额”和“次数。而保留最近月的转账明细。

  • 拆分相同类型的边，变为多种不同类型的边

    例如，(机场)<-[depart]-(航班)场景，每个架次航班的离港，都建模为一条航班和机场之间的边。那么大型机场的离港航班会极多。

    根据不同的航空公司将 depart 这个Edge type拆分更细的Edge type，如 depart_ceair, depart_csair 等。在查询（图遍历）时，指定离港的航空公司。

  • 切分顶点本身

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

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

    1. (人1)-[借款]->(银行A1), (人2)-[借款]->(银行A2), (人2)-[借款]->(银行A3);
    2. (银行A1)-[属于]->(银行A), (银行A2)-[属于]->(银行A), (银行A3)-[属于]->(银行A).

    这里的 A1、A2、A3 既可以是 A 真实的三个分行（例如北京、上海、浙江），也可以是三个按某种规则设立的虚拟分行，例如按借款金额划分 A1: 1-1000, A2: 1001-10000, A3: 10000+。这样，查询时对于 A 的任何操作，都转变为为对于 A1、A2、A3 的三次单独操作。

最后更新: September 17, 2021