快手单机千万 QPS 的分布式图数据库 KGraph 的实践
张世航 快手技术团队 2021-11-15 稿
导语
本文基于快手分布式图数据库KGraph作者张世航，在QCon全球软件开发大会（上海站）2021的演讲《快手分布式图数据库 KGraph》整理。
随着数据规模的膨胀与推荐算法复杂度的提升，传统数据库处理多度查询能力不足的问题越来越明显，图数据库的优势得到显现。在平均出度 300 的社交图谱上，一次三度查询会访问近 3000 万条边，即使聚合优化后，也需要发起近 10 万次基础查询。
为应对海量的数据和查询，快手基于 PMem 构建了高性能的单机存储引擎，并基于自研网络框架 KRPC 构建了分布式网络服务，实现了单机 2000 万 QPS，单集群十亿次每秒查询处理能力的分布式图服务。
10月23日，快手分布式图数据库KGraph作者张世航受邀参与QCon全球软件开发大会（上海站）2021，在“系统设计之成本优化”分论坛分享了题为《快手分布式图数据库 KGraph》的演讲，介绍了快手在构建高性能分布式图存储服务过程中，怎样通过极致的单机性能来降低成本支出的。
本次探讨交流主要分为5块内容，分别是图数据库简介、KGraph架构介绍、高性能需求下的问题解决、关键问题分析以及小结和展望。
走进图数据库——图数据库简介
首先对图数据库做一个简单的介绍，什么是图数据库呢？图数据库，他不是存储图片的数据库，是以图论为基础，存储对象是点，边，包括点和边附带的属性，将关系抽象成点和点之间的边，在处理关系上有先天的优势。
图数据库的应用场景非常广泛，典型的比如：
- 社交网络，用户作为点，用户之间的关系作为边，可以进行用户之间的关系运算；
- 推荐系统，用户和视频作为点，用户之间的关注等关系，用户对视频的点赞评论等关系作为边，可以进行多种策略的视频推荐；
- 知识图谱，场景下的各种实体作为点，实体之间的关系作为边等等。
上图右侧即是DB-Engines上2013年来的各种类型数据库的流行度趋势图，可以明显的看出图数据库在近两年来越来越流行，越来越被大众所关注。
根据存储的数据格式，可以分为：
- 原生图存储数据库，比如Nebula，neo4j、tigergraph等；
- 基于已有的KV或者Table存储，比如JanusGraph，KGraph等；
它的优势是原有的存储系统相对成熟。
图数据库还没有像SQL一样，统一的查询语言，目前它的查询语言比较丰富，比如：
- gremlin，是 Apache ThinkerPop 框架下的图遍历语言，支持的图数据库主要有JanusGraph、hugeGraph等；
- Cypher，是Neo4j的查询语言等等。
刚才我们提到，图数据模型，可以很好的运用在社交关系等场景，快手内用户间正好存在着多种关系。
快手在过去几年快速发展，已经成为一款国民级别的短视频APP，其中推荐的算法的质量，很大程度上决定了对用户粘性的大小，影响了核心指标的提升；这其中的社交推荐，需要基于用户之间的多种关系去做推荐，比如用户之间的关注关系，双关关系，或者通讯录好友关系等多种关系，基于这些关系数据，可以去做各种策略的推荐算法。
在2年前KGraph诞生之前，这些关系是存储在内存图结构中，在每个Server端都在内存中，加载了一个关系图数据，这样就会带来两个问题：
- 因为内存容量限制带来的数据容量有限，并且内存的成本较高；
- 服务器的启动需要加载图数据，启动时间长。
对于别的解决方案，我们可以考虑存在关系型数据库当中，这样用户之间多度关系的计算，会转化成频繁的join操作。数据量的膨胀，频繁的join操作，带来的时间和算力成本也非常巨大。
所以我们急需一种新的解决方案，来更加实时的进行推荐，同时也能方便业务快速迭代推荐算法。
在这样一个背景下，针对业务痛点和图模型的优势，在2019年底，开始调研开发了KGraph。
KGraph架构介绍
数据模型
KGraph基于有向异构属性图建模，如上图右侧，一个代表人的节点指向了代表视频的节点，边类型是点赞。
有向图，指的是边是有方向的，一个点的边可以分为出边和入边，出边入边分别存储；异构图，指的是允许存在多种类型的点和边，比如用户和视频分属两种不同的类型；属性图，可以理解为点和边上的键值对，比如用户具有年龄，性别等属性。
对于点的建模如下，有以下几个字段：uint64_t的id或者string类型的用户自定义id；string类型的代表类型的type，由id或者自定义id + type唯一代表一个点；属性，也就是键值对。
对于边：有确定的起点和终点；string类型的代表类型的type，由起点 + 终点 + type唯一代表一条边；属性。
KGraph和Table上的数据对比如图，DataBase和Graph对应，一个Type对应一个Table，一个点或者边对应一个Row，属性指的是Column。
使用方式
对于KGraph的使用方式：
- 可以通过C++ / Java SDK访问，他的形态类似上图右侧；
- 可以通过grpc访问；
- 可以访问Gremlin Server。
KGraph支持Gremlin查询语言，其一是Gremlin的生态比较完备，Gremlin生态的工具，都可以进行迁移使用；其二他是一种函数调用式的查询语言，学习成本比较低，能够很好表达复杂的查询，表达力比SDK 或者 grpc更好。
我们可以简单看两个Gremlin的例子，如右下图：第一个查询语句是对于666节点出边指向的点，其中类型是people的所有点；第二个查询语句是666号关注的所有视频主的粉丝群体，这些粉丝群体关注的女视频主按照重合度排序取前10个。
整体架构
整个系统可以分为三层，KV存储层，图逻辑层，以及计算层。
三层是相互独立的，可以分别实现水平拓展，如果存储的数据比较多，可以线性拓展KV存储层；如果计算任务较重，可以线性拓展计算层。
- 对于KV存储层，KGraph使用了高性能rpc框架KRPC和intel的新硬件PMem，实现了极致的单机性能；
- 对于图逻辑层，主要是对点和边的定义，也就是如何将点和边转化成KV；包括实现了点和边的增删查改等基本接口；
- 对于图计算层，主要设计到两个模块：
- 第一个GraphServer，它的定位第一个是proxy，用户可以通过GRPC或者KRPC访问，第二个定位是一些图算法的实现，比如topN算法；
- 第二个是GremlinServer，它的定位是Gremlin语言的计算层，他的存储后端依赖KGraph存储集群，多个GremlinServer组成了Gremlin分布式集群。
KV存储层
对于KV存储层，集群包含三种角色：client，Master和DataNode。
数据根据client定义的分shard算法，存储在DataNode的各个shard当中，由DataNode服务读写。
Master主要有以下几个作用：
- 维护机器的状态；
- shard调度：包括机器宕机时的failover，添加机器时shard迁移；
- 维护shard的路由信息。
对于一般的的读写流程，client向Master请求路由并缓存在本地，根据client端定义的分区算法，把图相关的数据转化成KV对，通过KRPC协议写对应的DataNode。
高性能需求下的问题解决
针对社交推荐业务痛点，随着数据规模的膨胀，单机内存图数据结构的解决方案已经行不通，我们需要在资源有限的前提下，替换掉原有单机内存图数据结构的解决方案，为此有以下几个设计目标：
- 高性能，目标是单机千万QPS；
- 为了解决内存加载数据耗时长的问题，我们需要一个持久化存储引擎；
- 为了解决本地内存数据容量不足的问题，性能和数据量支持线性扩容。
如何实现一个高性能的单机存储服务，一个存储服务，核心包含两部分：网络服务和存储引擎。所以我们需要解决高性能的网络服务和持久化存储引擎。
PMem简介
在存储介质层面，目前NVME SSD已经大规模商用，但是我们知道，普通NVME SSD硬盘的吞吐一般在百万IOPS，远小于我们期待的千万IOPS，为了让存储介质层面不成为我们的瓶颈，加上我司已经采购了Intel的PMem，所以我们享受了新硬件的红利。
PMem是一种新的存储介质，在存储分层次结构中，利用局部性原理，将经常访问的数据保持在最靠近 CPU 的位置，易失性DRAM速度快，但容量有限，价格昂贵；非易失性存储（如NAND SSD）容量更大，价格较便宜，但是数据读取速度较慢。存储介质很容易成为应用程序性能的瓶颈，在这种背景下，PMem作为一种新的存储介质，给了我们一个新的选择，他在存储的分层结构中占据DRAM之下SSD之上，它具有如下的特点：
- 比DRAM大，比SSD快：能够提供单条512G的容量，访问延迟在几百ns，比SSD快2个数量级；
- 非易失；
- 支持两种模式：
- 在内存模式下，提供大内存容量，性能接近DRAM，CPU 内存控制器将PMem视为易失性系统内存，把DRAM作为PMem的快速缓存；
- 在App Direct模式下，将PMem当成一个持久化设备来使用，可以使用文件系统比如XFS，或者使用PMDK来管理PMem。
为什么PMem既能持久化存储，又比SSD快呢？其一是PMem直接插在内存插槽上，通过DDR-T协议，与CPU进行数据交互；其二是底层的01存储单元不同。根据官网给出的性能指标，以单条128GB为例，写入单元为256B时，能够达到6.8GB/s的读带宽，1.85GB/s的写带宽。
构建高性能存储引擎
在PMem两种模式的选择上，我们需要把PMem当做持久化存储介质使用，在PMem之上挂载了XFS文件系统，配置DAX选项；
底层的数据存储引擎我们支持LSM-Tree的存储引擎以及hash引擎；由于PMem具有优异的随机读性能，在使用哈希引擎时，通过减少读时内存寻址次数和aep寻址次数，可以将读QPS提高到千万QPS；
关于缓存，我们在存储引擎之上实现了一个自研的LRU cache，对于具有热点读问题的业务，在全局cache之上多加一层thread local cache解决热点问题；
为了减少的并发冲突，我们尽量避免多线程写同一数据存储引擎实例，同时读写线程分离，使两者不相互影响。
由此，我们的DataNode对外可以提供千万QPS的极限性能。
PMem架构探索
在目前这种使用方式下，存储引擎的读性能已经完全满足我们的需求，但是在写能力上无法发挥新型存储介质吞吐性能，导致上层的读写性能无法进一步提升，因此我们还正在探索新的存储引擎，主要的架构图如图；
设计思路是在DRAM中存储文件的元信息，索引等，一是这部分数据一般比较小，二是需要频繁的同步持久化；文件的内容存储在PMem中，可以发挥PMem大容量的优势，同时它也具有不错的读写吞吐，使用方式是使用PMDK，通过mmap文件到用户空间，然后按照内存接口操作。
PMem遇到的问题
在使用PMem的过程当中，我们也遇到过一些问题，比如在我们进行引擎测试的过程中，有如下一个场景：
PMem挂载XFS文件系统，配置dax选项，数据存储引擎我们选择LSM-Tree存储引擎，压测随机写；在数据写入一段时间之后，写延迟会突然减半，这是一个非常奇怪的现象，但是可以稳定复现。
因为能稳定复现，所以我们对比了两段时间的火焰图，定位到一个函数；在写入一段时间后，LSM-Tree写WAL时调用的dax_do_io变快了，在dax_do_io上，发现他直接缺少了一个函数调用，就是xfs_end_io_direct_write。
之后我们通过阅读XFS的对应源码，并和内核组同学沟通，发现了问题的原因：
对于前期写延迟较大的原因是，dax_do_io主要是消耗在了xfs_end_io_direct_write的调用栈之中，这里面的主要消耗是xfs_log_commit_cil的一把spin_lock，因为在dax 模式下，针对同一个文件的append-write的， 会更新文件inode相关的元数据(主要是inode-size)，由于没有page-cache就需要落盘，会通过xfs_log进行原子提交。
对于后期性能变好的原因是，我们设置了recycle_log_file_num=n，也就是一个wal文件写完之后会尝试复用之前的wal文件。这个时候，相关的文件inode元数据就会避免更新，也就是不会出现前期 xfs_end_io_direct_write 中log-commit的spinlock竞争问题。
我们通过将recycle_log_file_num设置为0，发现整体的性能和前期性能接近，不会出现后期的性能突然增加的情况，验证了这个问题。
为了解决这个问题，我们做了优化，也就是预先分配WAL文件的空间，来保持一直高速的写入。
高性能RPC框架
解决了引擎层面的读写吞吐问题，下一步，我们需要解决网络框架的问题，设计目标，就定为40核机器能达到4000W QPS的设计目标，针对这个很艰巨的目标，我们可以做一个拆解，为了能实现40核4000W的性能，我们可以着眼于两点：首先我们避免线程间相互冲突，然后我们致力于实现单核100W的QPS，这样我们大体就可以达到单机4000W的QPS。
KRPC设计思路
对于实现单核100W的性能，我们可以先来了解一下数据访问延迟：在某个机型下，CPU访问L1Cache的访问延迟是1ns，L2Cache是3ns，L3Cache是12ns；含有2个node的情况下，本地内存访问大概是80ns，远程内存访问大概是140ns；对于锁的使用，有线程间竞争的情况下，大概是百ns，测试大概是30核1000W的；对于CAS操作的使用，有线程间竞争的情况下，大概是几十ns，测试大概是30核5000W的；对于内存的解引用，平均大概是100ns，其中内存解引用是我们经常面对的一个问题，线程内超过10次的内存解引用，单线程就会小于100WQPS。
由此，在实现上，我们做到了无锁，无shared_ptr，尽可能的减少字符串拷贝，在线程内实现了平摊个位数的内存解引用；对于一些全局的变量，我们尽可能都做了thread local cache，比如对于Server端的find service和method都做了cache。在结果上，我们达到了百万级别的单线程性能。
对于避免线程间的冲突，KRPC在主流程上无锁；另外一个可以提到的点是，关于内存的申请释放方面，对于一块内存的申请和释放都是由同一个线程处理的。
假设A线程频繁的申请内存，B线程频繁的释放内存，A线程的ThreadCache迅速减少，B线程的ThreadCache迅速增多，由此可能会导致A线程调用的ThreadCache::FetchFromCentralCache() 和 B线程调用的ThreadCache:: ReleaseToCentralCache 的竞争，这也是我们考虑到的一个点。
KRPC架构
在架构设计上，KRPC主要分为4层结构：
网络层使用asio管理连接和收发网络包，这一层会一次接受发送尽量多的数据，减少系统调用次数，提升性能；消息层主要负责将网络层的数据切成一个个消息(包括RPC消息、redis消息或者http消息等)；逻辑层是rpc框架的核心驱动层；协议层可以做多协议的扩展。
KRPC的性能指标
结合上面介绍的设计，KRPC达到了以下几个指标：
- 高性能，单机5000W QPS；
- 低延迟，响应延时低于100us；
- 协议可拓展，已经兼容gRPC，redis，http等协议；
- 稳定，简单易用。
KRPC还是一个比较年轻的系统，从2019年底设计开发，到目前KRPC的日均调用量超过十万亿，当前KRPC处于一个快速迭代，功能完善的阶段；其和主流RPC的一个性能对比如图，可以看到KRPC单机5000W的性能有数量级的优势；他的最佳实践就是KGraph。
KGraph性能指标
在有限的资源下，结合高性能存储引擎端以及高性能的rpc框架，KGraph满足了一开始提到的社交推荐的业务目标，他有以下几个特点：
- 高吞吐，对外提供单机2000W QPS的极限吞吐；
- 低延时；
- 可以线性拓展；
- 支持超级节点。
可以看到线上的某个集群数据，12台机器组成的集群， 在1.3亿QPS吞吐下，平均延迟600us，p999延迟小于1ms；在快手某些官方账号上，拥有几个亿的出边，KGraph也支持维护。
集群规模
在集群规模方面，KGraph已经稳定应用在社交推荐，快手电商，社交挖掘等业务上；KGraph已经正式接入了几十个集群，维护几百台服务器；访问量方面，集群QPS容量几十亿；数据量方面，按照单副本计算，存储边数超过10万亿条。
对于业务实践，可以举一个例子，在快手电商的实践过程中，业务方保存用户社交关系，网红关系，用户和短视频的行为，用户和直播的行为，用户对商品的浏览和点击等等，构成了一个庞大的关系网；基于图关系数据，可以用于商品推荐、主播召回等多种场景。
关键问题分析
超级节点问题，所涉及的是如何利用KV对构建图存储系统。
对于点的编码非常直观，id + type唯一确定一个点，所以key由id + type构成，value就是点的属性。
对于边的编码，有多种解决方案：
- 因为起点 + 终点 + type确定一条边，所以key由src + dst + type构成，value就是边的属性，这样的实现，对于更新一条边写放大较小，但对于读写出边列表，需要转化成Scan操作，这个性能是不能满足我们的需要的；
- 保存出边列表，把 src + type 作为key，所有出边的属性序列化成value，这样的实现，对于更新一条边有一定的写放大，并且出边越多，写放大越严重，对于读取出边列表，不需要再转化成Scan操作；随着边数的增多，value的大小会越来越大，这种情况下，该方案就不可行；
- 对于超级节点，我们的解决方案是把一个KV切割成多个KV，把多个KV组织成类似Btree的结构；通过调节value的分裂合并阈值，可以一定程度的平衡读写放大问题。
在实现上，KGraph对于三种方案都有实现，可以通过配置灵活的适应各种场景：
- 对于写多读少的场景，我们可以考虑采用每条边单独编码的方案，他的优点是写放大较小；
- 对于大部分的场景，我们把出边列表打包成一个KV；就是当边数小于阈值时，放在一个KV；边数大于阈值时，组织成BTree结构；阈值支持用户自定义，并且一个KV和BTree结构可以动态转化。
小结与展望
针对各种应用场景，我们进行了有向异构属性图建模，支持Gremlin语言，并且支持超级节点；
在成本优化方面，我们通过极致的单机性能减少成本支出，PMem单机引擎和KRPC组合在一起，实现了KGraph的极限吞吐。
目前KGraph仍然处于快速发展阶段，为了充分发挥PMem的优势，我们还在对自研PMem存储引擎进行探索，对图原生存储以及索引的支持，目前也在探索当中。
作者简介
张世航，2021QCon上海讲师，快手平台研发部分布式存储研发，加入快手后一直从事分布式图数据库的工作，目前主要负责分布式图数据库kgraph的重构工作。
