Galaxybase原生分布式并行图数据库介绍

1、技术创新，变革未来Galaxybase原生分布式并行图数据库介绍目录图数据库技术发展趋势图数据库如何选型Galaxybase图数据库系统介绍Galaxybase底层技术设计与实现Galaxybase产品功能及金融应用实践图数据库技术发展趋势图数据库市场规模从现在起到2022年将以每年100的速度增长（Gartner）图数据库是所有数据库中受欢迎程度增量最快的，六年达到1000%（DB Engines）世界100强企业76%使用了图数据库，涵盖金融、软件、物流、零售、航空、电信、医疗等行业 的头部企业和机构。数据库技术发展趋势图数据库选型的核心考虑因素数据库性能：查询及算法系统成熟度算法正确及完

2、备度异常处理跨数据集的性能稳定性数据库的可扩展性数据库对第三方的依赖原生vs非原生国产vs国际数据库厂商对商业的支撑力度1. 图数据库性能的核心测试项基础查询及计算性能K度查询性能图算法性能场景化查询/计算性能1.1图数据库基础查询及计算性能名称点数量边数量点边数量比原始数据大小是否带属性Graph5002,396,01967,108,8641:281008MB否Twitter-201041,652,2301,468,365,1821:3524.6GB否服务器配置（单节点）CPU参数12 Intel(R) Core(TM) i7-7800X CPU 3.50GHz内存128G DDR4网络宽带

3、千兆硬盘5.5T机械硬盘操作系统：Ubuntu 16.04.1 LTS（kernel：4.15.0-72-generic） Java 版 本 ：Java SE 8 Update 201 (build 1.8.0_201-b09) Docker版本：Docker version 17.06.2测试 K步子图的查询响应时间K步邻居查询是判断图遍历性能的一个优秀标准，它询问在起始顶点的 K 步的所有顶点。一个顶点的一步邻居就是其相邻顶点的集合。K-hop neighbor读取300个样本数据，测试时按顺序读取，统计其第1步到第N步扩展的所遍历到邻居点的个数，记录平均时间进行对比。 分别测试N=1、2

4、、3、4、5、6的情况。样本集取自TigerGraph的benchmark项目。对于所有1度查询、2度查询，超时时间界限均设置为3分钟/查询。对于所有3度查询、4度查询、5度查询、6度查询，超时时间界限均设 置为 1 小时/ 查询。为了将测试重心集中在图遍历和最小化网络输出时间上，我们只输出 K 度内邻居数量的大小，而不是完整的邻居列表。为了查询结果的严谨性，我们在参与测试的图数据库中，对所有测试 查询结果进行交叉验证。由于有的图数据库3-6度查询耗时过长，且频频超时，为了避免等待过长时间，我们将测试样本数量减少到10个。Sample：Tiger 300Galaxybase-D v3.0.2T

5、igerGraph-D V2.5.3Neo4j V3.5.19HugeGraph V0.10.4Nebula v1.01平均邻居数Graph500数据集KN1time(ms)1.954.3626.3430.4816.695129% failedKN2time(ms)43.2120.6813144.0712804.776111.52488931% failedKN3time(ms)345.83667.73127358.691643.6850144.11431863% failedKN4time(ms)573.72812.94694885.4156659.46184270.691553062% f

6、ailed70%KN5time(ms)600.31804.147370.58161173.79N/A1572970% failed80%KN6time(ms)609.76802.3139199.67160828.41N/A1576110% failed90%Graph500 数据集的跨产品性能结果Sample：Tiger 300Galaxybase-D v3.0.2TigerGraph-D V2.5.3Neo4j V3.5.19HugeGraph V0.10.4Nebula v1.01平均邻居数Twitter数据集KN1time(ms)14.1422.45144.61188.22315.910

7、6363% failed6%KN2time(ms)428.8927.7216758.8920067.4114222.863265143% failed44%66%KN3time(ms)8020.9414241.62346308.5N/AN/A20690415% failed70%KN4time(ms)24137.4734486.3N/AN/AN/A32533073% failedKN5time(ms)28612.4338934.63N/AN/AN/A34748002% failedKN6time(ms)29341.9539562.22N/AN/AN/A34989566% failedTwitt

8、er 数据集的跨产品性能结果NA：全部样本timeout/failedSample：Tiger 300Galaxybase-D v3.0.2TigerGraph-D V2.5.3Tiger自测数据Neo4jHugeGraphNebula平均邻居数Graph500数据集KN1time(ms)1.954.366.326.3430.4816.695129% failedKN2time(ms)43.2120.687113144.0712804.776111.5248893% failedKN3time(ms)345.83667.73410127358.691643.6850144.11431863%

9、failedKN4time(ms)573.72812.94694885.4156659.46184270.691553062% failed70%KN5time(ms)600.31804.147370.58161173.79N/A1572979% failed80%KN6time(ms)609.76802.31178039199.67160828.41N/A1576110% failed90%测试环境对测试结果的影响我们的benchmark在低配置环境下比 TigerGraph自测的 结果好算法对测试结果的影响TigerGraph benchmark中K度扩展的gsql没有考虑单点会被多次重复

10、查找的问题CREATE OR REPLACE QUERY kNeighbor(VERTEXS, INT depth) for graph socialOrAccumvisited = false; SumAccumloop=O; SumAccum count= O;Start= S;Start = SELECT v FROM Start:vACCUM v.visited = true;WHILE (loop:v WHERE v.visited != truePOST-ACCUM v.visited = true;count+= Start.size(); loop+= 1;END;PRINT

11、count as vertexCount;平均运行时间测试系统Galaxybase v3.02TigerGraph v2.5.3Neo4j v3.5.19HugeGraph v0.10.4Nebula v1.01平均邻居数T数据集测试项结果异常Tiger300RandomTiger300RandomTiger300RandomTiger300RandomTiger300RandomTiger300RandomGraph500KN1time(ms)1.951.24.362.3626.341.3130.483.1716.690.99512920% failedKN2time(ms)43.22.44

12、120.684.4113144.0770.5412804.7769.356111.5236.6348893110628% failedKN3time(ms)345.8395.51667.73206.68127358.627788.0191643.6820430.2850144.111521.691431863711027% failedKN4time(ms)573.72285.98812.94418.41694885.4127694.81156659.4659192.47184270.6973039.8715530621047797% failed70%KN5time(ms)600.31357

13、.32804.1456.747370.58853185.75161173.7978544.24N/AN/A15729791104633% failed80%20%KN6time(ms)609.76368.7802.31461.7239199.67846214.25160828.4180721.51N/AN/A15761101116873% failed90%60%选取方法对测试结果的影响Graph500数据集 Tiger300 vs 随机点平均运行时间测试系统Galaxybase v3.02TigerGraph v2.5.3Neo4j v3.5.19HugeGraph v0.10.4Nebul

14、a v1.01平均邻居数T数据集测试项结果异常Tiger300RandomTiger300RandomTiger300RandomTiger300RandomTiger300RandomTiger300RandomTwitterKN1time(ms)14.141.1422.452.24144.611.49188.223.82315.91.5410636330% failed6%KN2time(ms)428.834.59927.7235.8316758.89325.9120067.41490.8614222.86639.023265143186017% failed44%8.67%66%KN3t

15、ime(ms)8020.941799.5114241.623503.94346308.5N/AN/A2281.36N/AN/A206904156940730% failed70%40%KN4time(ms)24137.4710090.934486.315442.92N/AN/AN/AN/AN/AN/A3253307318783121% failedKN5time(ms)28612.4322849.638934.6333014.37N/AN/AN/AN/AN/AN/A3474800231800494% failedKN6time(ms)29341.9528564.839562.2239179.1

16、2N/AN/AN/AN/AN/AN/A3498956634675974% failedNA：全部样本timeout/failedTwitter数据集 Tiger300 vs 随机点Galaxybase和TigerGraph在边度数高的图中性能优势更大Tiger 300数据/随机取数数据Galaxybase-Dv3.0.2TigerGraph-DV2.5.3Neo4jV3.5.19HugeGraphV0.10.4Nebulav1.01平均邻居数比例Graph500 数据集KN1time(ms)1.631.8520.109.6216.86254.94% failedKN2time(ms)17.70

17、27.37186.33184.64166.8446.01% failedKN3time(ms)3.623.234.584.494.352.01% failedKN4time(ms)2.001.945.442.651.48% failedKN5time(ms)1.681.762.051.42% failedKN6time(ms)1.651.741.991.41% failed表中数值越大代表在边出度/入度越大的场景下，性能越差Tiger 300数据/随机取数数据Galaxybase-Dv3.0.2TigerGraph-DV2.5.3Neo4jV3.5.19HugeGraphV0.10.4Nebu

18、lav1.01平均邻居数比例Twitter 数据集KN1time(ms)12.4010.0297.0549.27205.133497.64% failedKN2time(ms)12.4025.8951.4240.8822.2617.55% failedKN3time(ms)4.464.0642.98% failedKN4time(ms)2.392.231.73% failedKN5time(ms)9% failedKN6time(ms)1.031.011.01% failed表中数值越大代表在边出度/入度越大的场景下，性能越差Sample-Tiger: 300Sample

19、-Random: 300GalaxyTigerNeoHugeNebula平均邻居数GalaxyTigerNeoHugeNebula平均邻居数Graph500KN1time(ms)1.954.3626.3430.4816.69561.313.170.9920.12% failedKN2time(ms)43.2120.6813144.0712804.776111.52488931.32.444.4170.5469.3536.6310627.5% failedKN3time(ms)345.83667.73127358.691643.6850144.11431862.695.51

20、206.6827788.0120430.2811521.69711027.2% failedKN4time(ms)573.72812.94694885.4156659.46184270.6970%1553061.8285.98418.41127694.859192.4773039.871047797% failedKN5time(ms)600.31804.147370.5880%39199.6790%161173.79N/A1572978.5357.32456.7853185.820%846214.360%78544.24N/A1104633% failedKN6time(ms)609.768

21、02.31160828.41N/A1576109.7368.7461.7280721.51N/A1116873% failedGalaxyTigerNeoHugeNebula平均邻居数GalaxyTigerNeoHugeNebula平均邻居数TwitterKN1time(ms)14.1422.45144.61188.226%315.9106341.493.821.5430.41% failedKN2time(ms)428.8927.7216758.8920067.4114222.8644%66%326514334.5935.83325.91490.86639.021860

22、16.5% failed8.67%KN3time(ms)8020.9414241.62346308.570%N/AN/A20690415.31799.513503.94N/A2281.36N/A6940730% failed40%KN4time(ms)24137.4734486.3N/AN/AN/A32533072.810090.915442.92N/AN/AN/A18783121% failedKN5time(ms)28612.4338934.63N/AN/AN/A34748002.322849.633014.37N/AN/AN/A31800494% failedKN6time(ms)293

23、41.9539562.22N/AN/AN/A34989565.928564.839179.12N/AN/AN/A34675974% failedTwitter/Graph500GalaxyTigerNeoHugeNebula平均邻居数GalaxyTigerNeoHugeNebula平均邻居数KN17.251282055.149082575.49012908118.927501520.73641630.950.9491531.1374051.2050471.5555561.511431KN29.925925937.687437851.2750152736.6781222614.176238.12

24、47174.6202157.0780117.4452617.50332KN323.193303121.328411214.450000518.8410616.953459.761554KN442.071864342.421703920.947700135.2853336.9085817.92629KN547.662757648.420134322.090576863.9471672.2889628.78829KN648.1204949.310391222.199955977.4743784.8547231.04737图数据基础查询及计算性能Benchmark小结Galaxybase在各项测试全

25、面占优，Tigergraph跟随其后Galaxybase和Tigergraph处理邻居数较多的“超级节点”能力突出，远超其他产品Galaxybase 3度及3度以上的深链查询性能较大部分对比图数据库具备很大性能优势Neo4j在3度以内的查询在跨数据集、数据规模变化的情况下性能变化小，说明其单机针对index-free adjacency 的优化完备3度查询以内Nebula比Hugegraph有优势，从4度开始Hugegraph超过NebulaHugegraph在平均邻居数不大的情况下，因为总体数据规模变大而产生不稳定，说明其针对index-free adjacency的优化不完备，性能会受到图

26、的规模影响大Nebula性能在跨数据集数据总体规模变化的情况下影响较大，几乎呈线性1.2 图数据库场景化查询及计算性能社交网络场景LDBC简介LDBC SNB模拟了一个社交网络图，在此图上引入两种不同的工作负载交互式工作负载指定了一组只读遍历，它触及图形的一小部分，并进一步划分为交互式简单 查询（IS）和（IC）交互复杂查询商业智能（BI）工作负载触及了很大一部分的图，组合了复杂程度不同各种查询，这些查询通常都会涉及对结果进行分组、聚合和排序等复杂操作LDBC SNB是迄今为止图形数据库在社交网路场景下最完整的基准测试LDBC测试结果对标paper中的测试，在256G内存的 单机环境上和Tig

27、ergraph 进行了对比 测试。使用的是LDBC SF100测试集。18X32XLDBC测试结果42X注：其他图数据库厂商未提供公开的全面LDBC测试报告项目数量Galaxybase 快二者接 近Tiger graph快领先 比例最快 倍数交互式短查询（IS）7700100%18倍交互式复杂查 询（IC）14111278%32倍商业智能查询（BI）25124948%42倍总计463051165%42倍Galaxybase较快 二者接近图数据场景化查询及计算性能Benchmark小结2. 数据库成熟度性能数据所无法体现的系统软实力异常处理及系统边界超级节点处理问题返回节点数上限问题版本升级的稳

28、定性算法库的完备性及正确性问题跨数据集的性能稳定性Hugegraph 未解决异常：一个点具有的边数量超过10000个之后无法删除，删除将抛出异常 Edges size has reached tx capacity 10000异常处理及系统边界异常处理及系统边界Hugegraph 未解决异常：在 Twitter-2010 图上进行 K-hop neighbor 测试时抛出了 Too many records(must = 800000) 问题，从异 常信息中推断，是因为在进行扩展时某个步骤的记录数量超过了 800000 ，在查找HugeGraph 文档后，未找到 相关的配置项，研究代码后发现：

29、com.baidu.hugegraph.traversal.algorithm.HugeTraverser.DEFAULT_LIMIT 在代码中hard code了这个限制public static final long DEFAULT_CAPACITY = 800000L;Nebulagraph 未解决异常：Nebula 在 Twitter-2010 这种数据量较大的数据集下无法稳定运行，出现了各种异常情况，这里对在测试中出现的异常情况进行了记录TProtocolException 异常： 在测试 Twitter-2010 的 K-hop neighbor (2度)时抛出了该异常异常处理及系

30、统边界Nebulagraph抛出 Get neighbors failed 异常在测试 Twitter-2010 的 K-hop neighbor (2度)时，该异常在 TProtocolException 异常之后，测试成功运行了一段时间，后续全部抛出了 Get neighbors failed. 异常从测试情况中可知，该异常已经导致 Nebula 数据库进入了一个异常的状态。我们进行了三轮测试，在第二轮测试时第一轮可以正常进行的测试项也无法获得响应了异常处理及系统边界Nebulagraph抛出TTransportException 异常以上异常是在测试中遇到较为频繁的异常情况，在测试 Gr

31、aph500 数据集 K-hop neighbor (5/6 度)时也遇到了异 常情况在异常中看到了 .SocketException: Connection reset 信息，检查数据库状态后发现 nebula-graphd 服 务已经异常终止运行了异常处理及系统边界最新的 Nebula Importer 导入未成功在遇到异常情况后，我们希望在多台机器上进行复测，观察是否都会出现相同的异常情况，以确定以上异常情况进入 Docker 官网发现 Nebula Importer 最近提交了更新，后续发现是导入工具的问题，测试时间是 2020-12-17异常处理及系统边界最新的Nebulagraph

32、升级到2.0版本后性能大幅下降，Graph500和Twitter2度无法跑完，尝试shortest path，也导 致了服务器down，已反馈论坛： 相同的数据在1.2版上跑几秒,2.0版跑一个小时没跑出来，尚未解决 /t/topic/2124版本升级的稳定性TigerGraph K-hop gsql语句严谨性HugeGraph 官方提供的最短路径算法部分结果不正确，算法来源：https:/hugegraph.github.io/hugegraph- doc/clients/restful-api/traverser.html示例1点 A 1:1751939 到点 B 1:4165129 存在

33、一条OUT方向的最短路径，长度为2。点 B 1:4165129 到点 C 1:507269 存在一条OUT方向的最短路径，长度为1但是结合两个路径，起始点 A 1:1751939 到终止点 C 1:507269 却找不到最短路径，该路径在 Galaxybase 和 Neo4j 上可以正常找出示例2点 A 1:586 到点 B 1:19489341 两点之间存在一条边直接相连，但查询最短路径路径长度并不是 1返回的最短路径还经过了中间节点 1:13 ，最短路径不正确算法库的完备性及正确性问题跨数据集的性能稳定性Hugegraph在平均邻居数不大的情况下，因为总体数据规模变大而产生不稳定，说 明其

34、针对index-free adjacency的优化不完备，性能会受到图的规模影响大Nebula在跨数据集数据总体规模变化的情况下性能影响较大，几乎呈线性下降3. 数据库的可扩展性单机 vs 集群系统的一些常见迷思：单机够用了，我只有90G原始文件，图能变多大？只有Google才有大图的需求！数据量刚好把单机内存吃掉80%，又不是装不下。多机分布式必须比单机快！怎么可能比单机慢，否则我花钱多买机器还越跑越慢？！本来有1台机器，现在2台机器分布式了，查询速度也必须是原先的2倍！不用出单机和分布式benchmark两个版本了，分布式装在单机上跑，反正从数据大小上看单机内存都能 放下，为啥没比放在多台

35、分布式机器上快很多？用单机版加Raft做读写分离搭建分布式图数据库，既能够跑单机benchmark因为其实数据都在本地有， 同时还能分布式serve读，多好，干嘛要切图（graph partitioning，相当于把大图切成小片分布式存 储）？单机的优势小数据全放内存里，直接用指针，通讯成本低充分内存结构优化，使用连续内存空间顺序读取轻松使用本地global变量，一致性协同简单All threads share two global epoch counters, GRE for reads and GWE for writes，initialized to 0 A write transac

36、tion goes through three phases: work, persist, and apply.A transaction has two local variables: a transaction-local read epoch counter TRE, which the worker initializes to GREIn the persist phase, . the transaction manager first advances the GWE counter by 1, then write WAL Next, it notifies the inv

37、olved transactions by assigning them a write timestamp TWE, set as GWE.After all transactions in the commit group make their updates visible, the transaction manager advances the global read timestamp GRE, exposing thenew updates to upcoming transactions. This also guarantees that the read timestamp

38、 of a transaction is always smaller than the write timestamp of any ongoing transaction.所有涉及write的事务都需要读写GRE和GWE注意：这还只是单机多线程事务，如果是多机分布式事务呢？协议会非常复杂，overhead更大！单机 VS 集群分布式多机单 机本地指针？连续内存空间？所有update事务都要 读 写 的global 变量GRE GWE？内存要是都用来存图数据了，还剩下什么内存跑算法？或者支持多用户同时跑查询和算法？指向固定IP？要是那个机器down了怎么办？总体不存在连续内存空间本地顺序读，

39、怎么优化？所有update事务都要 读 写 放在某个IP机器里的global 变量GREGWE？单机和分布式多机很不同数据切片、分布式，可以多个切片并行load线性加速多机处理不一定同时完成，分布式共识算法？多机之间的通讯和数据传输时间不可忽略，远程调用昂贵线性提升支持多用户高并发查询和算法执行单机 VS 集群 一家之言单机够用了，我只有90G原始文件，图能变多大？只有Google才有大图的需求！答：很小的数据确实只需要用单机，但是要充分考虑当前数据膨胀3-5倍，和未来数据增。数据量刚好把单机内存吃掉80%，又不是装不下。答：如果只有少数用户同时跑查询和算法是可以的；但是如果有场景可能多人跑算

40、法会遇到问题，譬如每人跑一个算法需要吃5%内存的算法，这个单机基本上就只能允许4个人用，也会影响系统速度。多机分布式必须比单机快！怎么可能比单机慢，否则我花钱多买机器还越跑越慢？！答：适合单机的小数据量、用户少、算法需求少只是简单查询的场景单机快。分布式涉及复杂的数据分片、协同协议、通讯建 立、数据传输、远程调用等，在适合单机的场景下就是比单机慢，这种情况不应该买多机。本来有1台机器，现在2台机器了，查询速度也必须是原先的2倍！答：1台机器可以用的各种优化多台机器用不了了，譬如连续内存顺序读，分布式反而可能慢！不用出单机和分布式benchmark两个版本了，分布式装在单机上跑，反正从数据大小上看单机内存都能放下，为啥没比放在多 台分布式机