跳转至

超级顶点(稠密点)处理

原理介绍

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

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

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

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

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

Note

NebulaGraph 中没有专用的字段来记录每个点的出度和入度,也没有内置任务来进行统计,因此无法预知哪些点会是超级节点。一个折中的办法是使用 Spark 周期性地计算和统计。

重复属性索引

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

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

关于属性索引的原理详细介绍在博客《分布式图数据库 NebulaGraph 的 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)-[借款]->(银行 A1), (人 2)-[借款]->(银行 A2), (人 2)-[借款]->(银行 A3);
    (银行 A1)-[属于]->(银行 A), (银行 A2)-[属于]->(银行 A), (银行 A3)-[属于]->(银行 A).
    
    这里的 A1、A2、A3 既可以是 A 真实的三个分行(例如北京、上海、浙江),也可以是三个按某种规则设立的虚拟分行,例如按借款金额划分 A1: 1-1000, A2: 1001-10000, A3: 10000+。这样,查询时对于 A 的任何操作,都转变为为对于 A1、A2、A3 的三次单独操作。


最后更新: February 23, 2023