超级顶点(稠密点)处理

原理介绍

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

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

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

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

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

重复属性索引

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

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

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

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

建议的办法

数据库端的常见办法

  1. 截断: 只访问一定阈值的边,超过该阈值的其他边则不返回。
  2. 采样:对于每条边有一定概率的返回。
  3. Compact:重新组织 RocksDB 中数据的排列方式,减少随机读,增加顺序读。

应用端的常见办法

根据业务意义,将一些超级顶点拆分:

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

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

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

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

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

根据不同的"航空公司"将 "depart" 这个边类型拆分更细的边类型,如 "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 的三次单独操作。