本文整理自DTCC2022大会上字节跳动研发工程师陈超的演讲“字节跳动图数据库架构演进——索引与执行优化”。陈超老师深度参与了 ByteGraph 开发到上线以及后续的迭代演进。目前主要负责 ByteGraph 存储层的开发工作。
总体来看本次分享分为三个部分：一是ByteGraph的介绍，包括ByteGraph可以做什么，Gremlin查询接口和举例以及ByteGraph业务介绍;二是ByteGraph架构，分为查询引擎和存储引擎;最后介绍ByteGraph过去面临的关键问题，包括图局部索引、全局索引、分布式事务、重查询优F88体育化、写放大优化和在离线 ByteGraph介绍
如图，字节跳动共有三类数据，分别是用户类、内容类(视频、文章、广告等)、用户和内容之间的联系(点赞、评论、转发、点击)。
使用图表达F88体育业务场景有不少优势，建模直观简洁，能更好地挖掘数据关联。ByteGraph是字节跳动自研的分布式图数据库存储系统，支持有效图模型，支持Gremlin查询语言。具有高吞吐、低延迟、最终一致等特性，读写吞吐可以扩展到千万QPS，ByteGraph一些学术论文已经被数据库VLDB-2022收录。目前ByteGraph已经部署了1000多个集群，遍布全球多个机房，支持头条、抖音、西瓜、知识图谱等。
Gremlin是一种图灵完备的图遍历语言，是Apache子项目之一，规定了Gremlin一些不同算子所涉及到的查询语义，但是具体实现不会有硬性限制，所以在不同的厂商对于Gremlin的标准会有自己的实现。
目前ByteGraph支持了超过1000多个业务集群，服务器规模已经达到上万台。最开始时，ByteGraph用来存储抖音用户关系在线存储，比如好友关系，以及粉丝列表等。有了这些用户互动基础数据之后，也会基于这些基础数据去做推荐，比如抖音推荐、推人、推视频等，基于好友的好友这类多跳查询做关系的挖掘以及关联关系的分析等算法上的内容。
实际案例，如电商业务构图，基于店铺所拥有的品类以及商品所属的品类进行构图，在图上可以做各种各样的查询。例如查询店铺会有哪些品类，还可以用来筛选某个品种类价格处于某一个范围的某种商品。关于第二种查询有一个小技巧，价格本来应该是点上的属性，但是为了加快查询，在商品到品类之间的边上冗余商品点价格的属性，就不用再多次查询每个点属性，从而提升了性能。
ByteGraph整个系统架构分三层：分别是查询引擎层、存储引擎层、磁盘存储层。三层之间相互独立，每一层都可以进行水平扩容。查询语义非常复杂，可能涉及到步骤数量比较多，所以是计算量比较重的查询，但是内存存储开销比较少一些，所以可以开启更多查询引擎层，开更少存储引擎层。
存储引擎层涉及到存储，模块中涉及到如何把全图数据进行切片，称每个切片为一个partition，每一个partition代表一个子图数据，要有相对而言比较良好、比较低的读写放大能力，以及需要考虑到能够在磁盘上组织形式对磁盘比较友好，如何实现这一数据结构也是ByteGraph比较核心的设计。为了保证数据不能丢失，在存储引擎层支持WAL，通过两阶段提交的方式支持事务，存储引擎层用C++编写。
在查询引擎查询层(GQ)和MySQL的SQL层一样，主要工作是做查询的解析和处理，查询引擎首先要做Parser，将查询语言解析成查询语法树，然后生成查询计划。例如一个带索引的查询进来之后，在存储层已经建立了索引之后，这个查询就不应该放到查询层去做，而应该放到存储F88体育层去做，这里也会涉及算子下推的优化。
基于代价的优化中，统计点的出度，以网络通信成本、计算成本和磁盘读取成本计算查询代价。比如要查我关注的人里哪些人也关注了他，这里有两个执行计划，执行计划A做两跳的扩展，先找到A的一度邻居，让一度邻居再去找A的二度邻居，看多少人当中会是需要筛选的B。另外一种方式是找到A的一度邻居之后，再找B的一度邻居，依赖这样的次序去做大小表的join。在不同情况下，A和B有不同的查询代价，大多数查询B会是更优的执行方式。但是也有例外，如A的出度比较小，B的出度比较大，A会是更优的执行方式。
在社交场景中，因为字节跳动是一个比较重社交的公司，参考Facebook在2016年的一篇论文中social hash算法，用来保证我们多跳邻居查询的延迟、网络开销比较低，这种情况ByteGraph第一步基于图导出之后做离线图分区算法，之后会把对应的路由表存到中性化节点里，后续通过路由表提供线上读写访问请求。
接下来讲一下ByteGraph存储引擎细节，整体上存储引擎会把系统的组件划分为几层：
如何基于KV构建一个图的结构?最直观的一种方式是一个KV对一条边，实现简单，同时写放大非常小，适合写入场景，当前的建模写放大非常小，因为粒度很细。但做一跳邻居查询时，读性能退化非常大。另外一种方法是一个KV保存一个起点所有边，这种写放大会变得很大，比如改了一个对应点上某一条边，其实整个边的历史被更改，无法处理字节内部一些超级顶点写入问题，因此在设计上需要做折中。
ByteGraph多属性结构是为了支持点边多属性访问，针对图的结构去定制一些多属性数据结构，有几个特点：会连续紧凑、访问速度快;Header中保存schema版本，快速增加属性;快速访问终点ID/Type、权重，以及时间这种边上固有属性;支持Int/string两种类型的ID/Type。
一是维护B树完整性，由于B树的分裂和合并操作会涉及多个KV，我们并不假设底层KV系统会支持分布式事务，所以需要有日志维护B树内部数据的完整性以及做分列合并的原子性。另一个是缓解写放大问题，每棵B树有自己的WAL日志流，写入请求处理流程中只写入WAL，并修改内存中数据、compaction时再将数据落盘。
关于缓存，ByteGraph目前自己实现了高性能LRU Cache，作为数据库而言，需要将缓存层组织成一个图相关的结构，用于提供最适合图的读写模式缓存性能。同时在缓存层也支持条件过滤等部分算子下推功能。LRU支持不同的策略，基于不同频率的读出以及触发阈值也不一样，比如物理机内存用到60%再往上走可能就比较危险，开始触发LRU Cache，把不经常用到的page下刷写到磁盘里。
ByteGraph存储引擎层的整理结构是把整个图数据模型计入一个特定的点，以及对应的边，抽象成一个B+树的数据结构，随着读写流进来，写入流会更新page上的数据，写入一个WAL，page会变脏，所以会用delta page上link list去记录脏数据，脏数据积累到一定程度之后，把脏数据下刷到子盘里面。同时会有WAL这样的log流。也会有一个LRU Cache来保证物理机内存维持到某一阈值之下，整体内存使用会有上界以及下界。最下面是分布式KV层，里面会混合page以及log两种类型的数据。
局部索引是指对于给定点的起点和边类型，在边的属性上去构建的索引。主要应用场景是用来加速边的过滤以及边属性排序。
索引构建目前支持两种方式：一是同步构建，在主索引去增删查改时，立刻修改元数据以及对应的索引。二是惰性构建，根据查询代价构建，使用惰性构建可以显著节约消耗资源量。比如某一种边类型上有时间索引以及年龄索引，就某一个点出度比较小，这时候可能没有必要构建年龄索引，如果某些点出度比较大，年龄索引构建优势比较大。
全局索引是指基于某一个属性值能够查到在当前Graph里具有特定锁定值所有点的ID，这是全局索引的概念。
比如基于年龄构建全局索引。年龄为18和19岁分别为两棵B树。全局索引更新涉及数据一致性问题，所以会通过分布式事务能力维护数据和索引之间的一致性。同时全局索引也是通过B+树来维护，所以如果索引的排序键区分度不太好的话，比较极端的例子就是男、女两种，全局索引上面的数据量太大，会导致比较严重的性能问题。
ByteGraph采用两阶段提交的协议实现分布式事务，查询层会作为一个协调者，存储层会作为参与者，查询层都是无状态的，所以存储层会保存协调者的状态。
ByteGraph会基于图的负载进行针对性的优化，比如针对重查询的自适应限流。在社交网络中，会存在一些超级节点，例如抖音中网红大V会有千万或者上亿粉丝，如果图查询起到相关大V点，极低QPS也会容易使得单机CPU打满，从而影响单机可用性。
前面介绍了通过WAL缓解部分写入放大，接下来会介绍如何进一步缓解B树的写入放大。
在离线生态方面，ByteGraph非常注重在离线数据融合，在我们内部产品线，除了有ByteGraph这种图数据库，也会有一些图计算产品。
ByteGraph支持存量数据导入，之前存在不同的数据源里，如MySQL、Hive、Redis、HBase等其他外部数据源，可以通过公司内部平台导入到ByteGraph里。数据量小时，调用ByteGraph的写入rpc api，速度达每秒百万QPS。数据量大时，使用MapReduce计算存储格式，直接导入KV存储，速度达到每小时500亿条边。
