WeGraphDB: 微信自研超大规模图数据库

WeGraph是首款高性能列式计算的HTAP图数据库，提供Cypher语法方言，有着实时KV的低延时和类似于ClickHouse的并行列式计算能力。

大规模图数据库未解难题: 8-2原则的n次方

一直以来，图数据库被大家认为是图辅助分析系统，在开源的世界里更是如此，比如安全打击，大家倾向于用(图查询-展示-剪枝-迭代)等方式来分析诈骗团伙。然而，上述的大厂们更倾向于把图数据库作为在线系统，提供实时低延时图查询服务，微信也亟待解决这样的问题。这两者场景具有一定的差异，普遍认为，后者可以涵盖前者的部分需求，但往往会牺牲易用性。WeGraphDB属于后者，致力于提供高可靠低延时在线服务，同时尽力提供图分析能力。

为什么大多数图数据库无法像MySQL一样，作为主力存储和查询引擎呢?

1.图普遍具有power-law分布特性，少数点连接了多数的边。

2.n跳查询会n次方恶化8-2原则，让系统变得极不稳定。

3.依据我经验: 在查询边数达到1w以上时，访问数据和计算的延时都会呈现指数形式上升，系统突发崩溃概率激增。

存储侧:

已知开源图数据库多以图分析能力为核心卖点，其需求是秒级返回，所谓的毫秒级返回往往是单点/单跳查询，并没有在在线应用的场景上做出太多努力。大厂们自研的图DB则与之想法相悖。Facebook TAO是大家解决这个问题的经典模板: 在cache层实现图单跳查询，避免热点落入后端存储。

计算侧:

在数据量达到1w以上是，经典的行式计算耗时明显增加，逐渐超越数据访问耗时。访问数据有TAO这个经典方案有迹可循，计算上面大家就可显神通了。如何各显神通?定制化开发，经典方案如下:

1.定制化多线程执行: (Query很多场景，如果没有充分优化，会有多线程的barrier，使得只有一个线程在真正执行任务)。

2.定制化执行过程: 业务直接调用给你们的专有函数。

发现问题了么?a)业务方都想优化，b)历史账单越滚越多，c)这不是图数据库，而是图业务中台。

经典查询语法下的行式计算劣势已经被clickhouse/doris等列式计算关系型数据库充分证明，这里只说结论，不再累述。大数据量情况下，列式计算会比行式计算，性能提升2个数量级。GitHub的issue也显示: 列式的模板特化的编程方法，性能甚至超越了JIT实时编译，成为了最主流列式计算引擎function实现方式。

Clickhouse的成功带来了一个重要提示: 通过精细化的列式计算代码，可以让通用查询语法的执行性能超越大部分程序员的手写代码。那么再次回到这个问题本身，在追求计算性能的道路上，我们要走定制化图中台的路线，还是走通用图数据库路线?我选择了后者。

相关论文:

无独有偶，2021年8月份的VLDB，发表了一篇图列式存储&&计算的论文，论证了列式会比行式图数据库带来十几倍到上百倍的性能提升。也为我们的这个自研图数据库项目添加了几分自信VLDB 2021: Columnar Storage and List-based Processing for Graph Database Management Systems

PS: wegraph当前版本只有列式计算，将会在下一版本做列式存储。目前在真实业务场景下和行式相比，约有5 倍的性能提升，和上述论文的测试数据相比还有很大的提升空间。欢迎大家加入我们(Email: trippli@tencent.com)，做更好的图数据库。

WeGraphDB系统架构

存算分离架构

• 计算层提供cypher语法服务，借鉴自clickhouse的精细化计算能力，模板特化的编程方式，多线程并行计算，列式表示和计算。在复杂计算中表现更优秀。
• 存储层包含内存存储(MKV)，SSD存储(FKV)和compaction服务(Data svr)，可以近似类比rocksdb的mem table, SST table和 compaction 后台线程。服务的分离，让每个模块的性能得到充分发挥，提供更稳定的服务。

向量引擎: 列式计算

行算难解之痛:

• 获取数值开销大: 每获取一个数字，都需要调用函数，甚至反序列化定位行内数据。函数调用和数据查找，开销占比高。
• 无法利用SIMD
• cache miss高: 行算多为pull火山模型，一行数据从source尽力处理到output。数据访问和执行代码本身的cache miss很难降低。

处理数据量大(个人经验1w以上)，向量引擎性能甚至可以超越大部分开发者的未经优化代码。

流式计算引擎: Push Pipeline

• block为最小计算单元。多个块按顺序组成一个流，多个流同时进入一个执行单元多线程并发执行。
• DAG计算图: 定义了数据在执行单元中的流向。
• Push/Full机制: 建立了生产者和消费者的平衡机制，让整个执行图均衡运作，降低延时。

语法

强schema类型

追求性能的数据库多使用强schema表结构，neo4j采用schema less无需提前定义label和relation类型，属于为了易用性牺牲性能的做法。

建表区分点和边表

-- 建立点表
CREATE VERTEX person (name string, age Nullable(Unt32));
-- 建立边表
CREATE UNDIRECTED EDGE TABLE friend(time DateTime);

类SQL写入语法

-- 写入点
INSERT VERTEX person (name, age) VALUES hash_i64("trippli") : ("trippli", NULL), hash_i64("ponyma") : ("ponyma", NULL);
-- 写入边
INSERT EDGE friend () VALUES hash_i64("trippli")->hash_i64("ponyma"): (toDateTime('2016-06-15 23:00:00'));

Cypher 查询语法

-- 找到共同好友数>3的好友的好友，最多返回10个
MATCH (self)-[e1:friend]-()-[e2:friend]-(ff)
WHERE id(self) = hash_i64('trippli')

RETURN ff.person.name as friend_of_friend, count() as cnt
WHERE cnt > 3
LIMIT 10

数据类型

具有完善的类型支持

我们的未来

• 列存
• 实时图计算查询更新
• 图可视化
• Query管控
• ...

欢迎加入我们，做更好的图数据库. Email: trippli@tencent.com