图数据库存储技术及实践
分享嘉宾：周研博士 创邻科技 CTO
编辑整理：李晓 网易
出品平台：DataFunTalk
导读：本次分享主题为图数据库存储技术及实践，将介绍创邻科技在多年实践和优化中对图数据库存储技术的一些思考。主要包括以下几大部分：
图数据库简介
该章节我们主要介绍为什么需要图数据库？它能够应用在什么场景，主要解决的问题是什么？以及什么是图数据库？
图数据库存储核心目标
该章节主要介绍图数据库较传统关系型数据库的深链查询优势，以及图数据库存储系统设计的核心目标。
图数据库存储技术方案
该章节主要介绍了数组、链表、LSM树三种存储方式的优劣势，在实际实现一个图数据库的过程中，应根据使用场景和设计理念去做取舍。
Galaxybase图数据库应用实践
最后，该章节介绍原生分布式并行图数据库Galaxybase，涉及其优势特点、存储架构、性能优势、生态和客户案例等信息。
01
图数据库简介
1. 关联是不可逆的趋势
世界万物是普遍联系的，Internet带来了信息的联通，IoT带来了设备的联通，微信、微博、抖音、快手等APP将线下的社会关系转移到了线上，形成更加广泛的人际关系的联通。随着社交、零售、金融、电信、物流等行业的快速发展，在人们的生产生活中，每时每刻都产生着大量的数据，促使当今社会支起了一张庞大而复杂的关系网。随着技术的发展，我们对这些数据的分析和使用，不再局限于从统计角度分析相关性，而是希望从关联的角度，揭示数据的因果联系。
2.关联分析的场景
在社交网络场景中，我们可以通过粉丝对KOL的关注、点赞、评论、转发等多种关系，快速确定和品牌调性契合度较高的KOL，从而实现精准营销。在好友推荐、舆情追踪等场景也可以运用关联分析的方法。
在金融场景中，我们可以使用关联分析的方法来判断信用卡欺诈团伙，具体方法是把和申请件相关的申请人、联系人、推荐人，以及他们的手机地址、邮箱，还有申请件提交时使用的设备ip、cookie等信息，放到一张相互关联的网络中，就可以通过关联分析来找到异常的欺诈网络。在金融场景中，还有一种天然的网络，就是账号之间的转账网络。过去如果想隐藏一笔资金的真实流向，最基本的操作就是把这笔资金分散成很多小的资金，然后通过账号之间的多次转手之后再汇总到目标帐户，传统的分析方法很难对这样的转账操作进行高效的追踪分析，而使用关联分析的方法就可以把资金的流向分析得一目了然。
在零售环境中，我们可以通过构建商品知识图谱，并加入用户信息、用户消费信息关联商品知识图谱，从而可以实现360度的用户画像、商品的实时推荐，以及反薅羊毛等业务场景。
在电力系统中，基于发电厂、变电站、线路段开关等电气设备组成的天然的电网拓扑，可以实现电网调度的实施仿真，还有故障分析，降低由于研判时间较长带来的停电时间，并可以计算出每一度使用的电当中，清洁能源和化石能源所占比例，为企业及时调整用电结构助力。
在电信场景中，电话号码之间的主叫和被叫关系也是一张天然的网络。通过分析不同呼叫方式的网络模型，也可以非常容易地判断出某次呼叫是一个正常通话还是一个骚扰电话，甚至是诈骗电话。因为坏人会频繁更换号码，所以通过黑名单的方式来拦截它的滞后性比较高，而通过网络关联分析的方法，可以迅速识别出不正常的呼叫形式。
在政企应用的场景中，可以通过关联分析实现道路规划、智能交通，还通过打通各个来源的数据信息，可以实现疫情的精准防控。
在制造业领域，可以通过建立实时的供应链网络来进行供应链管理、物流优化、产品溯源。
在网络安全领域，可以通过追踪成千上万个IP地址之间的调用关系，来寻找一次网络攻击的真正源头，也可以分析调用链路上的薄弱环节，防患于未然。
世界万物是普遍联系的，如果能够妥善地刻画和分析这些联系，我们就可以发现关联分析几乎能运用到生产生活的方方面面。前面列举的只是关联分析的一些常见场景，其应用远远不止这些，还有很多其他的场景，比如企业的股权穿透，公安的案情分析，生物医药领域的基因分析和新药研发等。
3. 关联分析的难题
前面提到的很多场景背后都涉及到数据量的问题。在以上场景中，我们遇到的数据量都非常巨大。比如一个典型的社交网络中，光是自然人的数量就有十亿数量级，再加发帖、评论、话题这些实体，总的实体数量很容易达到百亿的规模，而这些实体之间关系的数量可以达到千亿甚至万亿的规模。又比如转账网络，账户实体数量可能在几亿至几十亿量级，但是账户间的转账关系可能是账户数量的几百甚至上千倍，也能达到万亿规模。其他像零售场景，反映的是用户每次浏览、咨询、下单这些关联的动作。电信网络中要反映每次电话中的主叫和被叫的关系。不难想像，在这些场景中，我们所面对的数据量都是天文数字。处理这样规模的数据肯定需要依靠专业产品，而不是简单自己写几个程序就能解决的。
在这样的大规模数据中，关联分析通常还要处理较深的关联跳数。在这里，跳数是指在网络中从一个实体出发，要经过多少次找邻居的操作才能到达目标实体。在不同的关联分析场景中，由于数据模型不同，常见的关联跳数也不同，少则5-6跳，多则20-30跳。在关系型数据库，这样的关联操作是用Join操作来完成的。在关系代数中，Join的本质是做笛卡尔积。在这样的大规模数据中进行Join操作，对系统资源的要求高，而查询的响应时间通常会比较久。当然，我们有各种优化校验的方式，比如建索引、排序合并和哈希Join等，然而在很多生产编码规范中，都不允许对3张以上的表进行多表Join，也就无法进行3跳以上的关联分析。
除了数据规模大，关联跳数深以外，关联分析还有一个特性就是实时要求高。比如电信欺诈问题，我们接到一个诈骗电话，最好是在几秒内甚至是还正在响铃还没有接起电话时，就能进行诈骗预警。如果把这些呼叫数据拿出来，放到离线分析系统中跑批计算，得到结果可能已经是一周以后了，这样起不到防范效果。又比如疫情精准防控，也是越快越准地定位密接人群，效果就越好。在这些数据规模大、关联跳数深、实时要求高的场景中，传统的数据存储、查询、分析、计算方式都不能很好地完成任务。
4. 图数据库基本概念
为解决以上问题，我们需要图数据库。按照维基百科的定义，图数据库是一个使用图结构进行语义查询的数据库，它使用点、边和属性来表示和存储数据。
这里的图指的是图论中的graph，由点和边组成，G=（V，E）。在实际使用场景中，点用来表示实体，边用来表示关系，可以是有向的，也可以是无向的。目前主流的图数据库使用的都是属性图模型（Property Graph Model），也就是除了点和边以外，在点和边上还可以附带任意多数量的属性。一个属性可以理解为一个键值对。有了属性之后，图数据库的表达能力大大增强了，几乎可以描述现实场景中任何数据形态。
02
图数据库存储核心目标
接下来探讨一下图数据库存储的核心目标，也就是图数据库存储需要解决的根本问题。
1. 图查询的核心语义
首先来回顾一下，数据规模大、关联跳数深、实时要求高的场景下，完成一个图查询或者图分析，要进行的核心操作是什么。单独的访问点和边，以及上面的属性并不是这里的关键。在关联分析中，最核心的操作是邻居的迭代遍历。这也解释了为什么关系型数据库进行这个操作的时候性能不佳：因为在关系型数据库中，边（也就是实体之间的关系）并不是直接存储的，而是以外键的形式来表示。从实现功能的角度，我们完全可以底层使用关系型数据库，对外暴露一个具备图语义的抽象接口，让用户能够进行点边和属性的查询，但是这样做的性能是无法达到使用要求的，即便在主键和外键上都建立了索引，在面临大规模数据的时候，或者查询跳数比较深的时候，索引对性能的提升也是非常有限的。
2. 深链查询性能对比
上表中用who-trust-whom公开数据集，对比了多关联跳数在关系数据库的查询时间（不加索引、加索引）和图数据库的查询时间。
首先对比加索引和不加索引的情况，可以看出，在2跳的时候，加索引是能够明显提升查询速度的，3跳的时候提升就不多了，到4跳的时候加不加索引都已经变得很慢了。而使用图数据库，查询性能可以一直保持在非常快的水平。
3. 免索引邻接（Index Free Adjacency）
图数据库存储的核心目标是实现免索引邻接。
在写入时，免索引邻接可以保证一个点和与它直接相邻的边总是存储在一起。因此查询时迭代遍历一个点的所有邻居就可以直接进行，而不需要依赖其他索引类的数据结构。和依赖于一个全局索引相比，免索引邻接会让邻居遍历操作每一次迭代的时间复杂度降为O(1)，也就是说不需要任何其他操作就能直接进行迭代。因此迭代一个点的所有邻居的时间，就是这个点的邻居数量乘以O(1)，仅与这个点自己的邻居数量有关，而与整个图中全体的点边数量是无关的。如果使用全局索引，那么每次定位都需要一个O(log(n))的时间复杂度。这里的n是参与全局索引的数据规模，可以理解为整体的边数量。因此迭代一个点的所有邻接的时间，就是这个点的邻居数量乘以O(log(n))。
这样我们从算法的时间度复杂度上看，O(log(n))已经是非常快的，但是当我们处理非常巨大的数据量时，这个值也会非常可观。另外还需要注意的是，log(n)的值会随着n的增大而不断增大。假设图中一个点只有一个邻居，若使用全局索引，它也是会随着图中的总边数增加而越来越慢。所以如果具备了免索引邻接的能力，那么获取这个邻居的时间就是一个恒定值，而与全局的图规模无关。这个特点就会带来巨大的性能提升。所以我们可以明确，图数据库存储的核心目标就是实现免索引邻接。
03
图数据库存储技术方案
1. 使用数组存储
首先最直接的方法就是用一个数组，把每一个点上面的所有边，按照顺序一起存储。点文件就是一系列的点组成，每个点的存储，包括点的ID、META信息，以及这个点的一系列属性。每个边文件中，按照起始点的顺序存储点上对应的边。每条边的存储包括终止点ID、META信息，以及边的属性。META信息包括点边类型、边方向、实现事务的额外字段等。在这个存储里，可以直接从起始点遍历所有的边数据，它的读取性能非常高。
但是这样的存储方式也需要处理一个很棘手的问题，就是变长数组的问题。变长可能由很多因素导致，比如两个点的属性数量可能不一样，属性本身内容有可能不一样，属性值如果是字符串的话，字符串也是变长的，由于属性长度不一样导致每个点的存储空间也是变长的。所以点文件和边文件中都会面临变长数组的问题。
解决思路有两种，一是用额外的offset来记住存储位置，另一个就是预先划分好一些预留空间，用于后续的增长。
2. 使用链表存储
为了彻底解决数组存储的变长问题，可以改用链表方式来存储。在链表的存储方式中，点文件和边文件里面存储的全部都是ID，每个ID都是固定长度的，通过ID可以计算偏移量位置，通过偏移量位置直接读取数据。因为它能够通过位置计算ID，偏移量和ID是一一对应的，所以每个点也不用保存自身的ID。
我们再看一下在链表存储中如何进行边迭代。
首先从点A出发，在点文件中找到首个边ID：α，去边文件中找到α对应的偏移量，就能把整条边数据读出来。边数据里，有起始点和终止点，比如这条边的起始点A、终止点B。下一条边的偏移量是θ，那么就再找到θ的位置。θ边读出来，它是从起始点C到终止点A。这时候点A是处于终止点的位置上，我们找对应终止点的下一条边，是ω。然后再找ω的偏移量，读出来，是一个A到D的边，A在起始点的位置上，下一条边是NULL，迭代遍历结束。我们可以看到，链表存储的方式很好地解决了变长的问题。
这看起来是个完美的解决方案，但其实仍存在问题。
在链表存储下，每次迭代时offset的位置是随机的，不是连续存储的，因此会有大量的随机读操作。而磁盘对随机读操作是很不友好的，也就是说虽然时间复杂度是O(1)，但是这个O(1)的单位是磁盘随机读的时间。而前面数组方案中的O(1)的单位是磁盘顺序读的时间，这两者在性能上差别非常大。所以使用链表的存储方法，非常依赖一个高效实现的缓存机制。如果我们能把这个存储结构在内存中缓存起来，那么在内存中进行随机访问的性能会非常高。
3. 使用LSM树存储
LSM树存储是一种基于顺序写盘、多层结构的KV存储。
上图展示了LSM树读写操作的核心流程。一个写请求进来时，直接写入内存中的MemTable。如果这个MemTable没满，这个写请求就直接返回了，所以写请求性能是很高的。当这个MemTable满了的时候，把它变成Immutable MemTable，同时生成一个新的MemTable供后续的写请求使用。同时，把Immutable MemTable的内容写到磁盘上，形成SSTable文件。内存中的MemTable和Immutable MemTable都是按Key排序的，所以SSTable也是按Key排序的。SSTable文件是分层组织的，直接从内存中写出来的是第0层，当第0层数据达到一定大小之后，就把它跟第1层合并，类似归并排序。合并出来的第1层文件也是顺序写排的，当第1层达到一定大小也会继续和下层合并，以此类推。在合并的时候，会清除重复的数据或者被删除的数据。
在读取请求来的时候，首先去内存中的MemTable查找，查到就直接返回。没查到就去第0层的文件中查找，第0层没有再到第1层，这样逐层查找。
因为在SSTable文件的存储中，key是有序排列的，所以我们只要通过LSM树实现免索引邻接的能力。关键点在于合理地设计边的Key，要让一个点的所有边在排序后是相邻的。
上图中例1，只要把边Key的最高位放起始点ID，那么排序之后，从这个起点出发的边自然就会排在一起。这里还可以有一个编号字段，加入编号字段就可以支持在两点之间的同类型多条边的共存。因为LSM树是KV结构，所以如果只有起始点、终止点和META的话，那么两点之间同类型的边只有一个Key，所以只能存一条。对于像转账交易、访问记录这样具有事件性质的边来说，两点之间肯定会有多条同类型的边，在这样的场景下，这个能力就是非常重要的。
在某些场景下边的Key也可以不以起始点开始，比如例2的场景下。可以先放边的类型，再放起始点ID。这样做的目的是为了能够通过边类型直接做分片。因为在分布式环境下，做这样的分片可能会有更好的性能。这样虽然一个点的所有边是分散存储的，但是一个点某个类型的所有边还是顺序存储在一起的。如果业务场景是边查群总是按照类型分别迭代的，那么它也能提供很好的免索引邻接的能力。
LSM树也存在一些难点需要克服。
首先，SSTable文件是分层的，在查询时的最坏情况下，需要找遍所有层才能知道找得到或者找不到，因此读性能是没有直接使用数组的方式那么高的。另外，Compaction对它的影响是很大的，Compaction是个后台操作，会占用大量的磁盘IO，势必对前台读写性能造成影响。第三是，使用LSM方案通常都要依赖第三方存储，对于一些特定的需求，必须要改动第三方存储项目才能实现。
4. 优化之路
可以看到，几种常见的实现免索引邻接的存储方式，都不是一劳永逸的方案，而是各有各的优势和短板：
通过数组的方式读取速度快，但写入速度慢；通过LSM树的方式写入速度快，但是读取速度慢。
通过链表的方式，读取和写入的速度都不占优，但却是灵活性最高的方式。
在实际实现一个图数据库的过程中，要根据我们的设计理念去做取舍。
实现一个完整的图数据库产品，还有很多功能和性能的问题需要考虑。比如图数据库特有的反向边一致性的问题，还有分布式条件下怎样做分区分片，怎样处理分布式事务，是否支持mvcc快照，实时副本怎么做，WAL怎么做，属性索引怎么做，以及是否支持数据过期等。这些都是一个成熟的图数据库产品需要解决的问题。解决这些问题的同时，也要兼顾底层存储的特性。
04
Galaxybase 图数据库应用实践
1. Galaxybase特点
Galaxybase是一个国产高性能分布式图数据库。它具有如下特点：
速度快：原生分布式并行图存储，毫秒级完成传统方案无法实现的深链分析, 较同类技术百倍提升。
高扩展：完全分布式架构，动态在线扩容，高效支持万亿级超级大图。
实时计算：内置丰富分布式图算法、无ETL实现实时图分析。
高效数据压缩：优化资源利用，节省硬件和维护成本。
全自主可控、兼容国际开源生态与国产底层硬件。
2. 分布式图存储技术方案
Galaxybase数据库使用的是业界领先的数据分片，加动态压缩的分布式存储技术。它支持属性图的存储。在分布式部署环境中不同分区的文件可以根据计算出来的分布函数放在不同的集群机器上。备份数据也是以分区文件的形式，在集群不同机器之间进行同步。分区数据文件内部的点边数据格式采用的是高压缩比的动态压缩技术，可以大幅节省存储空间。Galaxybase原生图存储引擎是100%自研的，不依赖任何第三方存储引擎。因此可以和图查询、图计算功能做充分的整合优化，以实现非常好的产品性能。
3. Galaxybase性能优势：打破图数据处理规模世界纪录
这是我们和中山大学携手共建的一个国家重点研发图计算项目。它依托国家超算广州中心的环境，仅用50台机器的集群就完成了5万亿规模交易数据的智能挖掘系统，实现了当前全球商业图数据支持的最大规模图数据处理。打破了之前用1000台机器集群创造了1.2万亿规模的大图处理的世界记录。我们涵盖的出入度，最大有超过1000万的超级节点。六跳深链查询平均耗时仅6.7秒。
4. 优异的查询性能
LDBC SNB测试
模拟社交网络图，是迄今为止图数据库在模拟业务场景下最完整的基准测试。
测试详情
Galaxybase图数据库具有优异的查询性能。上图是LDBC-SNB官方对Galaxybase进行测试的结果。测试由国外权威机构进行，首先进行了结果正确性验证确保图数据库返回正确结果；随后进行了系统稳定性、可用性、事务支持性和可恢复性验证，均达到官方标准；最后进行了各项性能测试。Galaxybase表现优异，达到国际领先水平。在使用完全相同系统配置前置下，Galaxybase较LDBC之前公布的最高记录吞吐量提升了70%，平均查询性能达6倍以上提升，最高查询性能提升72倍。
5. 丰富的图算法支持
Galaxybase也提供了丰富的算法支持，提供了包括像图遍历、路径发现、中心性分析、社群发现、相似度分析、子图模式匹配等几个大类的上百种图算法。不久前率先通过了信通院图计算平台的一个产品基础能力评测，涉及五个能力域，34个能力项的评测，全方位覆盖了图平台的基本能力、兼容能力、管理能力、高可用和扩展能力。
6. 云启创新生态
同时，我们也加入了腾讯云启创新生态。我们创邻和腾讯合作联合推出了高性能的图数据库产品TGDB，已经在农行、交行、国家电网等超大型客户场景中落地。TGDB当前在墨天轮的图数据库类目中排名第一。
7. 标杆用户与合作伙伴
我们已经服务了金融、能源、教育、互联网、政府多个行业中的头部客户。在农行、交行、民生、上农商、南电、国电、浙大、腾讯、公安都已经有落地进入实际生产的案例。我们的合作伙伴包括腾讯云、百度云、AWS等。欢迎大家来使用Galaxybase图数据库。
今天的分享就到这里，谢谢大家。
在文末分享、点赞、在看，给个3连击呗~
01/分享嘉宾
周研
创邻科技CTO
浙江大学计算机博士，图数据库领域专家，具有多年分布式图数据库设计和应用实践经验。
02/免费下载资料
03/报名看直播 免费领PPT
04/关于我们
DataFun：专注于大数据、人工智能技术应用的分享与交流。发起于2017年，在北京、上海、深圳、杭州等城市举办超过100+线下和100+线上沙龙、论坛及峰会，已邀请超过2000位专家和学者参与分享。其公众号 DataFunTalk 累计生产原创文章700+，百万+阅读，14万+精准粉丝。
🧐 分享、点赞、在看，给个3连击呗！👇