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

数据类型

具有完善的类型支持

类型

成员

注释

数字

[u]int8/16/32/64

浮点数

float/double

字符串

String

布尔值

Boolean

时间

Date/DateTime/DateTime64

数字存储

UUID

UUID

NULL

如: Nullable(Uint32)

Nullable(type)

数组

如: Array(Uint32)

Array(type)

结构体

如: Tuple(name String, age Uint32)

Tuple(name type, ...)

我们的未来

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

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

本站文章资源均来源自网络,除非特别声明,否则均不代表站方观点,并仅供查阅,不作为任何参考依据!
如有侵权请及时跟我们联系,本站将及时删除!
如遇版权问题,请查看 本站版权声明
THE END
分享
二维码
海报
WeGraphDB: 微信自研超大规模图数据库
一直以来,图数据库被大家认为是图辅助分析系统,在开源的世界里更是如此,比如安全打击,大家倾向于用(图查询-展示-剪枝-迭代)等方式来分析诈骗团伙。然而,上述的大...
<<上一篇
下一篇>>