导读：KGraph 是快手自 2019 年底自研的一款图平台，目前已经稳定应用在了社交推荐、电商推荐、安全等多个业务场景。
本文将介绍 KGraph 的系统架构，性能表现以及实际应用。主要包括以下几大部分：
背景介绍
KGraph 架构
关键问题分析
应用场景介绍
小结与展望
分享嘉宾｜张世航 快手 高级工程师
编辑整理｜周思源 西安交通大学
出品社区｜DataFun
01
背景介绍
快手是一款国民级别的短视频 APP，同时也是领先的内容社区和社交平台。根据快手发布的 2022 年第一季度财报，快手社区内互相关注的用户对数已达到了 188 亿，同比涨幅接近 70%。在如此规模的用户量级下，仅双关的关系已达到百亿级别，若再考虑快手的其他场景下的关系如用户与视频的关系、直播电商中的点击购买关系，数据规模将非常巨大。如何存储和利用这些关系数据是迫切要解决的重要问题。
2. 推荐
作为一个短视频 APP，让视频的观看者刷到满意的视频以及让发布者的视频脱颖而出是非常重要的任务。实现该目标的方法主要是通过推荐系统。推荐系统主要包括召回和排序两个部分，排序还可以细分为粗排、精排、重排。通过层层筛选找到用户感兴趣的视频。KGraph 主要解决召回部分所遇到的问题。
3. 社交推荐系统的痛点
KGraph 最早是为了解决推荐团队的问题而诞生的。在算法之下若能高效存取核心的基础数据，应该能为上层优化留出更大的空间。在 KGraph 诞生之前，为了能高效存取数据，业务方的解决方案是存储在内存图数据结构当中。其中，内存图数据结构是业务方自定义的，按照图模型的方式加载和使用的数据。
这种方式虽然高效但依然存在几个问题。首先是单机的内存限制导致图规模的限制；其次是非持久化，每次启动都会加载很长时间。关系型数据库可以解决上面提到的问题但是会面临新的问题即性能下降。推荐中依赖的多度关系的计算需要频繁的表连接操作，导致性能低下。
因此，我们研发 KGraph，通过图模型的多跳能力来解决性能问题。
KGraph 架构
1. 迅速发展的图数据库
图数据库指的是存储图数据的数据库，其中图数据是由节点和边（关系）表示的数据结构。图模型可以天然的应用在许多场景中，比如社交网络、风控领域、知识图谱等。根据 DB-engine 的流行趋势排名，自 2013 年 1 月到 2020 年 6 月，图数据库在各个类型的数据库中涨幅最高，但是图数据库目前并没有统一的查询语言标准，比较流行的查询语言包括 Gremlin，Cypher 和 nGQL 等。
2. 有向异构属性图建模
为了满足不同场景的使用，KGraph 采用了有向异构属性图建模。其中边是有向的，每条边 KGraph 存了两次，在起点处存了指向终点的出边，在终点处存了指向起点的入边。异构指的是点和边包含不同的类型，比如点包含用户类型和视频类型，每个点有对应的类型和唯一的 ID，可以通过（类型+ID）的方式查询点。边的类型如观看类型，边需要明确起点和终点，通过起点+终点+类型唯一确定一条边。KGraph 目前只能通过查询点的出边或者点的入边来找到对应的边。属性图指的是点和边上都可以附带属性，比如用户点上有年龄、性别，边上有观看时间等信息。相较于关系型数据库，KGraph 中的图对应于关系数据库中的数据库，类型对应于表，节点和边是图中的实体，相当于表中的一行，属性则对应于表中的一列。
3. 整体框架
目前图数据库依赖的底层存储主要分为两种，一种是原生的图存储，另外一种是依赖于已有的 K-V 存储或者关系型存储。二者各有优缺，原生的存储可以对图模型进行专门的优化可以更好的提升读写性能；依赖已有模型的优势是已有的存储模型较为成熟，KGraph 则在底层存储上选择了后者。KGraph 的存储层是一个自研的分布式 K-V 存储，主要包含三个角色。首先是 DBServer，采用单进程多 Shard 的设计来提供读写服务并支持多 Region，多 AZ 的部署；其次是 Master，主要负责进程的管理和 Shard 的调度，Master 可以处理新进程的加入和故障进程的处理，通过调度 Shard 实现线性的扩容缩容；第三个是 KNS，是路由管理模块。
在存储之上的是 SDK，SDK 定义了图的模型，实现图的基本读写接口；在 SDK 之上的是 GraphServer。KGraphServer 是 KGraph 系统中自研的 Proxy，对于其他语言的支持是通过 KGraphServer 来实现的。KGraphServer 还可以执行简单的多跳过滤等计算操作。Gremlin 的底层存储依赖 KGraph，Nebula 的底层存储可以选择其自带的存储或者是 KGraph 的 K-V 系统。在 GraphServer 之上可以搭建一些大数据平台支持离线数据导入或者离线的图计算等任务。
03
关键问题分析
1. 社交推荐的痛点如何解决
KGraph 的设计主要是为了解决前面提到了两个已有的问题即单机内存限制和关系型数据库性能低下的问题。KGraph 的分布式 K-V 系统的架构设计突破了单机数据量的限制。在 KGraph 的设计中，性能被作为重点考虑，期望单台服务器可以达到千万级的吞吐。搭建一个存储服务可以简单分为两个部分即网络服务和持久化引擎，客户端通过网络访问持久化引擎，通过持久化引擎来读写数据并返回给客户端。因此，高性能的网络框架和高性能的持久化引擎是迫切需要的。
2. DBServer 架构
首先是持久化引擎，目前应用比较广泛的存储硬件是 NVME SSD，可以达到百万 IOPS（Input/Output Operations Per Second），但与期望的千万级别还存在一定差距。因此 KGraph 在绝大多数场景采用 PMem（Persistent Memory），不仅拥有接近 DRAM 的读写能力还拥有持久化的能力。PMem 支持两种使用方式，第一种是内存模式，直接将 PMem 当作大容量的内存来使用，DRAM 当作 PMem 的高速缓存。但是该方式无法解决内存持久化的问题。KGraph 目前采用的是第二种使用方式即 App Direct 模式，在这种方式下将 PMem 当作磁盘来使用，通过在 PMem 上挂载 xfs 文件系统来读写数据。对于线上业务，大容量低 QPS（Queries-per-second）的业务一般采用 SSD 的方案，对于高 QPS 的业务一般采用 PMem 的方案。
从实际业务来看，主要是 xfs 限制了 PMem 的吞吐。在挂载 xfs 时一般开启 dax 选项，导致对文件的读写需要直接落盘，这样对于文件的修改需要加锁修改文件的 meta 信息。加锁会造成瓶颈，目前仍在探索 PMem 新的使用方式。目前正在研发的是基于 PMem 的 Hash 引擎，主要的设计方案是绕过 xfs 系统，通过 PMDK 来读写 PMem。为了高效地寻址数据，把 PMem Block 的索引结构和管理 PMem 空闲空间的 free list 保存在 DRAM 当中，在引擎重启时，通过扫描 PMem 重建索引，这样 DRAM 可以快速索引数据，同时 PMem 可以高效持久化并读写数据。在引擎的上层引入 LRU Cache 来加速读。针对热点问题一般会另外架设两级 cache 架构，采用自研的 logdb记录 binlog，向外提供图接口或者 K-V 接口，由 SDK 直接访问。
从测试结果来看，基于 PMem 的 DBServer 单机读的 QPS 能达到千万级别。
3. 高性能 RPC 框架——KRPC
为了能在分布式场景下使用还需要解决网络框架问题。以单机 40 核为例，要想达到单机千万的服务，可将问题拆解成单核 100W，如果单核 100W 要线性拓展，在设计上还需要注意线程冲突。单线程 100W，意味着留给每次 RPC 的处理时长大约为 1us，也就是 1000ns。以常见数据访问为例，CPU 访问 L1 Cache 的延迟是1纳秒，在含有两个节点的情况下访问本地内存约80纳秒，远程内存访问 140 纳秒，这样，对内存的解引用平均是 100 纳秒。若每次RPC的处理有超过 10 次的内存紧引用，则单线程访问小于 100 万 QPS。为了保证单线程的吞吐，做了代码上的优化。从测试结果来看，每次RPC的处理时间不到 1000 纳秒的延迟。
为了减少线程间冲突，KRPC线程在 RPC 处理的主流程上无锁。在内存的申请和释放方面，KRPC 使用了 tcmalloc，同一块内存的申请和释放都是由同一进程来负责的。KRPC 的架构比较简单，主要有四层架构。最底层是网络层，主要负责管理网络连接和收发网络包。为提升性能，每次读写都会尽可能多的读写数据以减少系统调用的次数。消息层主要负责接收网络层的数据并切割为上层需要的消息，包括 RPC 消息，Redis 消息等。逻辑层是 RPC 框架的核心驱动层，负责处理客户端和服务端的普通逻辑，决定消息的处理流程。最上层为协议层，可以做多协议的拓展。目前兼容的协议有 KRPC，Redis 协议，gRPC 等。KRPC 是为提高存储系统的吞吐而研发的，具有高性能、高吞吐、低延迟、协议可扩展、稳定等特点。
4. 超级节点问题
超级节点是图中出度非常大的一类节点，比如快手的官方账号有十几亿的粉丝。KGraph对外提供的是图模型但是底层依赖的是 K-V 存储，所以需要从图到 K-V 进行编解码。由于点是由（Type+ID）唯一确定的，因此对点的编码可以通过将（Type+Id）当作 Key，属性当作 Value 来存储。
对于边的编解码，需要考虑到一种情况，在实际的业务应用当中，获取一个点的所有出边是一个高频操作，查询某一条特定的边是一种低频的操作，所以一般有三种编解码方案。第一种，因为起点 + 终点 + type唯一确定一条边，所以我们可以把每条边编码成一个KV，这样做的优势是天然支持超级节点，并且读写一条边，都只需要一次 IO，没有写放大，劣势就是获取出边列表需要获取一系列 KV，这里可能用到 Scan，性能较差，这样不能满足业务高效读出边列表的要求，所以 KGraph，在一开始采取了第二个方案；也就是把全部出边编码在一个 KV 的方案，这样做的好处就是读出边列表只需要一次 IO 操作，性能较好，但劣势也很明显，第一是写放大比较大，写一条边，需要修改整个出边列表，第二是无法解决超级节点问题，如果出边较多，整个出边列表编码的 value 大小将非常大。所以，随着这个痛点逐渐明显，KGraph 目前也支持了第三种编码方案，也就是把出边列表编码成多个 KV，并通过一定的方式管理这些 KV 的方案，KGraph 采用的是采用 BTree 的方式管理这些 KV，这种编码可以看做上面两种方案的折中，读出边列表不需要 Scan，但是需要多次 IO，支持超级节点，因为每个 Value 的边数到达上界就会分裂，所以读写放大不在是第二种方案的边的出度，变成了每个 Value 最大的阈值，这样写放大就变得可控。
经过测试，BTree 方案的读出边性能和原有方案接近，写边性能得到较大改善。以 20W出度的点为例，在每个 value 最多存 2000 条边的情况下，BTree 方案的写吞吐比原方案高出 2 个数量级，并且每个value的分裂阈值越小，写放大越小，写边的吞吐越大。如果每个 value 能存 2000 条边，2 层 BTree 就可以存储 400W 条出边，3 层 BTree 就能存 80 亿条边，绝大部分节点，2 层 BTree 即可解决，这样写一般都只需要两次 IO。首先找到 root 节点，然后二分找到叶子节点，读写对应的叶子节点即可
在实际应用中，原方案和 BTree 方案可以动态转化，在边数小于阈值时，采取原方案，这样保留了原方案只需要 1 次 IO 的优点，在边数超过阈值时转化为 BTree 方案，可以支持超级节点，调整写放大。
5. KGraph 性能指标
在高性能的网络框架和存储引擎基础上，KGraph 的极限测试单机吞吐极限达到两千万QPS，并且时延较低，同机房 RPC 延迟在毫秒量级。在实际应用的过程中，单机 QPS 最高达到过 1000WQPS 以上，并且平均延迟为 600us 左右。在分布式场景下，单机的性能可以线性扩展并支持多 AZ 多 region 的部署。上线两年多以来一直保持较高可用性且应用在社交推荐，电商推荐等多业务场景。
同时 KGraph 作为图平台，可以用多跳计算替代关系型数据库的 join，这里以一个简单的测试为例。在一个 100 万个点、每个点平均 50 出度的网络里，找多度关系，这样图的规模大概是 5 千万条边。执行 2 跳的查询大概需要 1.5ms，3 跳需要 40ms，4跳需要 960ms，5 跳需要 8s，4 跳的结果就几乎访问了全图的点，5 条的解决结果访问了全图的边，查询时间还能控制在较低的水平。如果是关系型数据库，在做 4 跳或者 5 跳时，可能就已经不可用。这里还对多跳的 QPS 进行了测试，在同样使用单台机器的的情况下，KGraph 单机的极限吞吐表现更好，有着数量级的差距。
04
应用场景介绍
1. 基于 KGraph 实时查询的社交推荐
第一个应用场景是社交推荐。作为一个社交平台，若能在不同场景下向好友发出推荐请求，促使好友实现关注和回关可以增强好友的社交属性，提升用户粘性。为了计算可能认识/可能感兴趣的其他用户，这里需要解决三个问题。第一个是庞大的数据量，在目前的用户量级来看，按照不同的模型构图，可能包含千亿条边或者万亿条边，这个数据量是非常大的。第二个是吞吐较大，DAU3 亿的情况下，查询的 QPS 将会很高，要做到实时查询也是一个挑战。第三个是为了挖掘更多的关系，比如多度好友等等，需要对用户之间的关系进行多度计算，需要支持这种计算能力。
如果要选择 MySQL，大数据量可能采用分库分表等方案，多度计算需要 join，性能会是问题。所以这里选择了 KGraph，KGraph 能够支持 PB 级别数据的存储，提供千万 QPS 吞吐的能力，同时能够高效的进行多度计算。
在集群的使用方式上，存储层保存了多种在线数据和离线数据，比如可能有用户快手站内关注，互关关系，用户对视频的点赞，评论关系，或者是离线计算的结果比如社群计算结果。基于这些数据可以进行实时的查询并由上层应用进行算法计算。当前 KGraph 也正在跟业务方探索新的合作方式，将业务多跳 + 计算的逻辑下沉到图平台的 GraphServer，GraphServer 可以通过就近机房访问，添加 Cache 等优化措施，对整体的吞吐和延迟进一步优化。
经过测试，不加 Cache 的情况下，单台 GraphServer 每秒可以进行 400W 次点向量的查询和点积计算，以 2 跳计算为例，KGraphServer的单机吞吐是 Nebula 的 2 倍多，且延迟是 nebula 的 2/3。此外，这些存储层保存的数据还可能作为用户推荐的精排环节的特征抽取，互动文案的存取等等。
2. 基于电商图谱的推荐召回
其次就是电商推荐场景。
一方面，客户投放电商广告的目的是引导用户对电商直播的订阅和下单成交进而寻求 GMV 的转化。若能精确找到有潜在购买意图的顾客将可有效提升 GMV（Gross Merchandise Volume）。
另一方面，若用户能快速找到想要的商品也会提升用户的购买体验。电商的场景，也十分适合 KGraph 的图模型。在 KGraph 存储层，保存了电商图谱的各种对象，可能包括用户、店铺、商品、直播、视频等，也构建了对象之间的各种复杂关系，比如可能有用户之间网红家族关系，视频对直播的预热关系，店铺和商品之间的关系等等。基于这些数据，可以进行实时的推荐召回，比如可能有标签召回，根据 KGraph 的电商图谱的数据，通过模型计算，筛选出优质广告，作为召回结果；再比如可能有上架商品实时召回，可能根据用户最近浏览过商品的类目等信息，拉取正在上架同样类目的直播广告进行精准匹配，最终返回直播广告队列，还可能有品牌召回等多种召回策略。除此之外，还可以在这些数据上进行离线的特征计算和存储，有了电商图谱，未来还可以进行更多策略的挖掘。
3. 利用 Spark 的离线图计算
KGraph也支持离线的图计算任务，在 KGraph 的存储之上也支持 Nebula 的查询引擎。在上层还可以使用 Spark，利用 SDK 或者 Nebula 读写 KGraph 的数据执行一些复杂的图算法，比如 k 跳子图或者最短路径，并把结果写回 KGrpah 或者写到 Hive 中。
05
小结与展望
KGraph 最突出的优势是性能优势。凭借 PMem 和高性能网络框架 KRPC，能达到单机千万的极限吞吐和低延迟，为上层优化留出更多空间。KGraph 目前支持 OLTP 的实时查询和 OLAP 计算，已经稳定应用在快手社交推荐和电商推荐等场景。KGraph 目前处在快速发展的阶段，用户规模和集群规模都在不断扩大。展望一下 KGraph 后续的发展，一方面需要系统更加完善，虽然已经对接了 Nebula 查询引擎，但他的查询性能目前还无法满足很多在线查询的要求，我们期望自研图查询引擎，解决 SDK 语义简单的问题。同时还要支持多种图存储底座，比如团队内部自研的存储底座。另外 KGraph 目前还偏向图存储，将来也会更多的做图计算图学习的探索。
随着集群规模的增大，集群的维护已经成为一项很重要的工作。所以，集群的高可用，易维护也是我们关注的重点。另外，除了目前的应用场景以外，也在积极的探索更多的应用场景，比如知识图谱，安全风控等场景。