导读小红书作为社区属性为主的产品，用户主要通过图文笔记等形式进行互动，而各种对象之间的交互即为关系类型。不同的关系类型业务分属不同业务部门，存在大量的重复开发，导致不仅开发成本高，且难以整体维护。本文将分享小红书应对万亿社交网络关系的图存储技术实践，展示如何深入解决业务痛点。
主要内容包括以下几大部分：1. 自研背景
2. REDTao 设计与实现
3. 业务平滑迁移
4. 成果收益
5. 展望
分享嘉宾｜卢亚德 小红书 存储工程师、图数据库负责人
编辑整理｜康思迪
内容校对｜李瑶
出品社区｜DataFun
自研背景
小红书是一个社区属性为主的产品，涵盖了各个领域的生活社区。用户可以通过短视频、图文等形式记录生活点滴，分享生活方式。我们在梳理小红书的所有社交图谱业务之后，总结了如下一些挑战以及风险点：- 小红书的社交图谱关系数据已经达到了万亿级的规模，且增长速度非常快。
- 社交场景下超大规模数据的更新、读取时效性受到考验。
- 底层数据库集群的 CPU 负载高、扩容频繁、成本和稳定性压力大。
为确保对业务的支撑，技术团队在图存储方面的目标主要包括以下几方面：- 提供统一的图查询 API，实现公司内部社交图谱业务的访问收敛。
- 封装缓存和数据库，减少业务重复开发以及业务维护复杂度。
在开始自研产品的开发之前，我们对业界方案进行了调研。调研结果发现，Facebook 的 Tao 图存储系统更贴合小红书的实际情况和已有的技术架构，风险也更小。因此决定基于 Tao Paper 来研发我们自己的图存储产品。REDTao 设计与实现
上面介绍了 REDTao 自研的背景，接下来将详细介绍其设计与实现。1. 整体架构
REDTao 的整体架构如下图所示，分为三层：接入层、缓存层和持久层。
业务方通过 REDTaoClient 接入，请求先发送至 REDTao router，REDTao router 采用 K8s 部署，可以按需动态扩缩容。在 router 中为业务方透明化了请求逻辑，在业务请求多种关系类型的数据时为其提供了一个统一的服务名，以便业务方可以更加简单、高效地完成多种所需关系类型的请求逻辑。进入缓存层之后，请求先被发送至到 Follower，需要的话再请求到 leader，如果 cache miss 的话，最后还会请求到 MySQL。这个接下来会再细讲。如刚才所说，cache miss 的话最终请求持久层 MySQL 集群，至于 MySQL 如何路由，下面会进行说明。
- 首先来介绍一下读的流程，客户端将读请求发送给 router，router 接收到 RPC 请求后，根据边类型选择对应的 REDTao 集群，根据三元组(FromId,AssocType,ToId)中的 FromID 和 AssocType 通过 Hash 计算出分片所在的 Follower 节点，将请求转发到该 Follower 节点上。Follower 节点接收到请求之后，首先查询本地的图缓存。例如，查询一条关系即三元组(FromId,AssocType,ToId)是否存在，这是一种典型的关系点查，类似于我是否点赞过某条笔记。首先 Follower 在 cache 中查找是否存在这条关系，如果缓存命中，那么直接返回结果；如果没有命中，Follower 则将请求继续转发给 Leader 节点，同样的，Leader 节点也会先在本地缓存进行查找，如果命中则返回给 Follower，Follower 收到响应之后会将数据 commit 到本地缓存中，这样下次再请求到这条关系数据时就可以直接命中，最后 Follower 把数据返回 router；如果 Leader cache 也不命中，Leader 会将请求发送到底层的 MySQL 数据库，查到结果后再 commit 到 Leader 缓存、Follower 缓存，最后再返回给 router。如果在 MySQL 也查询不到这条关系，我们也会把查询结果 commit 到 cache，在 Leader 和 Follower 的 cache 中标记此条关系不存在。这样就可以避免对某条不存在的数据的读请求每次都需要穿透至 MySQL。
- 再来介绍一下写的流程。整体上也是同样的逻辑会走这么一遍流程。比如要添加一条关系，请求先发送到 Router，再发送到对应的 Follower，Follower 会在 cache 当中去检查，如果 cache 中显示这条数据已经标记为 exist，那再去添加就会是 conflict，因此会直接返回给业务层告知这个关系已经存在；而如果在 Follower cache 中没有发现这样一条关系的存在，那么 Follower 就会再把请求发送到其 Leader，同样的，Leader 这边也会检查该条关系是否存在，不存在的话最终 Leader 就会把这个请求发送到 MySQL。对于 update 操作，也是同样的流程。每一次更新完，我们会把结果 commit 到 Leader 的 cache 当中，然后 commit 到 Follower 的 cache 当中，这样下一次再请求时就会命中，跟读流程类似。
3. REDTao 图模型和 API
图模型采用的是典型的图关系定义，模型构建的key就是（FromId，AssocType，ToId）三元组，它唯一定义一条关系。比如，FromId 就是一个用户A，ToId 就是一个用户B或者一条笔记、一个评论，AssocType 就是关注某个用户，或者点赞一条笔记、评论一条笔记，或者点赞一个 comment 等关系。图 API 也很简单，AddAssoc 是增加一条关系；DeleteAssoc 是删除一条关系；ExistAssoc 是判断某条关系是否存在；GetAssoc 是获取一条边的属性数据；UpdateAssocData 是更新关系属性字段。除此之外，还会有其它一些 API，比如供风控使用的，加入发现作弊用户在不停地刷粉丝，如果我们判定其为异常的作弊逻辑，就会在图中标记该关系为作弊，这样在查询时前端就不会显示这些作弊产生的粉丝，粉丝数也会回到正常。还有一类接口是为 DTS 平台提供的，跨云场景下，有些关系数据可能是由其他跨云集群更新的，但本地集群 cache 层还没有意识到这一更新，缓存中保留的可能还是旧数据，不清除的话就会导致数据的不一致性。这种情况下，我们利用自研的 DTS 能力进行 cache 数据清理，这个后面会再讲。4. 易用性
REDTao 中封装了简洁而丰富的图语义 API 给业务方使用，满足了业务方增删改查的需求，业务不再需要关心如何操作 cache 和 MySQL 的具体实现逻辑，使用方式更加简单，实现了查询收敛。由于社区后端数据太大，我们按照不同的服务、优先级拆分成了几个 REDTao 集群。为了对业务方透明化后面的拆分逻辑，我们实现了统一的接入层。不同的业务可以使用同一个服务 URL，在请求发送到接入层之后，接入层通过订阅配置中心获取边类型到集群的路由，会自动分发业务的图请求到对应的 REDTao 集群。5. 高可用
实现了图语义的分布式 cache 集群，故障自动检测和恢复、水平扩缩容。双层 cache，每个分片都有一个 Leader 和若干个 Follower，所有的请求都先发给外层的 Follower，在 cache miss 时再转发给 Leader。这样的好处是读压力大的时候只需要水平扩展 Follower，单点 Leader 写入的方式也降低了复杂度，更容易实现数据的一致性。如果一个副本故障，系统会在秒级别内进行切换。当持久层发生故障时，分布式缓存层仍然可以对外提供读取服务。为防止缓存穿透，REDTao 会缓存不存在的关系对象，并设置 TTL。为防止缓存雪崩，导致限制 MySQL 同时收到大量请求，我们通过限制 Leader 的最大 MySQL 并发请求数来实现限流保护 MySQL。在爬虫或者作弊用户频繁刷同一条数据的场景下，为避免缓存击穿，我们利用等待队列来串行执行对写入或者查询同一条边的请求来控制同一时间的并发请求。MySQL 集群通过自研的中间件实现分库分表，支持 MySQL 的水平扩容。6. 高效的数据结构设计
REDTao 的 cache 数据结构设计，我们采用了三级嵌套 HashTable 的设计。最上面一层，根据某个起点 from_id 从第一级 HashTable 中查找到 REDTaoGraph，该结构记录了所有 type 下对应的所有出边信息。接着，在第二级 HashTable 中，根据某个 type_id 查找到 AssocType，该结构记录了某个 type 下所有出边的计数、出边哈希表、<时间索引,to_id>跳表以及其他元数据。最终，在最后一级 HashTable，通过 AssocType 的某个 to_id 查找到最终边信息 REDTaoAssoc。该级 HashTable 限制存储最新的 1000 个边信息，以限制超级点占据过多内存，同时集中提高最新热数据的查询命中率以及效率。7. 高性能
通过集群监测数据可以看到，我们的缓存命中率是比较高的，请求时延是比较低的。在生产环境中，我们的系统可以在一台 16 核的云厂商虚拟机上跑到 150w 查询请求/s，同时 CPU 利用率仅有 22.5%。单机 QPS 可以到达 3w，其中每个 RPC 请求聚合了 50 个查询。8. 数据一致性
REDTao 为每个请求生成一个全局递增的唯一版本号。在使用 MySQL 数据更新本地缓存时，需要比较版本号，如果版本号比缓存的数据版本低，则会拒绝此更新请求，以避免冲突。Router 会通过对 FromId+AssocType 进行两组 hash 计算分别得到对应的分片组 group id 和 shard id，先通过 group id 找到目标分片组，然后在分片组存在多个 Follower 节点的情况下，通过对 shard id 取模找到目标 Follower，保证相同 FromId+AssocType 的读写请求总是被发送到同一个 Follower 节点，以保证数据的写后读一致性。在存在多 Follower 的情况下，每次 Leader 节点收到更新请求后，会进行 MySQL 的更新，并随后异步发送 invalidate 请求给其他 Follower，以清除其他 Follower 上的 stale 数据；如若失败，会将需要清除的数据保存在相应 Follower 的 invalidation 队列。Follower 定期同 Leader 发送 Sync 请求，Leader 会回复其对应的 Invalidation 队列，收到回复之后 Follower 会清除其 cache 中的 stale 数据。一般情况下，MySQL 读请求随机读取主从库，对于少量要求强一致的读请求，业务可以在请求时设置强制读主标志，REDTao 会透传该标志，MySQL 中间件会根据该标志将读请求路由到主库。9. 跨云多活
单写：所有跨云集群的写入请求都由 MySQL 处理，通过 MySQL 原生主从复制功能将数据变更同步到从库。就近读：除少量要求强一致的读请求将被转发到主库上，正常的读请求将就近读取本区的 MySQL 数据库，满足读请求对时延的要求。- 缓存层，通过自研 DTS 服务订阅 MySQL binlog，将 binlog 转换为 invalidate cache 请求，来清除 REDTao cache 层的 stale 数据，保证数据的最终一致性。
10. 云原生
支持弹性伸缩、快速扩缩容；可以实现更快地部署，并支持多 AZ 部署；故障自动检测，故障节点进行自动迁移恢复；支持平滑升级，每一组 Follower 和 Leader 是一个单独的 group，在部署时进行资源隔离。业务平滑迁移
1. 社交图谱业务时效性、稳定性要求高，需要保证在线业务的平滑迁移
- 开发了专门的 Tao Proxy SDK，支持对旧 MySQL 集群和 REDTao 集群进行双写双读。
- 对双读结果进行数据比对、校验、修复，等到新旧集群数据基本一致并观察一段时间之后，完全切流 REDTao 集群。
2. 数据规模大、业务类型量多,分级分时迁移
- 将旧的超大 MySQL 集群按优先级做拆分，先将优先级最低的服务迁移到一个 REDTao 集群。
成果收益
1. 有效降低了数据访问成本
社交图谱类型的数据访问，具有典型的读多写少特点，而且访问的数据有非常强的时间局部性（即最近更新的数据最容易被访问）。REDTao 上线后，cache 命中率 90%+，请求 MySQL 的 QPS 降低了 70%+，大大降低了 MySQL 的 CPU 使用率。在缩容 MySQL 的副本数目后，整体成本降低了 21.3%。2. 提升成本控制，减少扩容需求
随着 DAU 的增长，在社交图谱请求增长 250%+ 的背景下，相比之前旧架构，如果承载同样量级的请求，至少需要扩容 1 倍以上的资源成本（数万核）。受益于 REDTao 系统超高的缓存命中率，实际上整体成本只增加了 14.7%（数千核），成本可控性和稳定性上都得到了极大的提升。展望
由于资源有限，在 REDTao 初步实现的过程中有一些取舍，完整性尚有欠缺，例如依赖 DTS 来保证多集群之间的 cache 一致性、Leader 与 Follower 在断连一段时间之后的 invalidation 队列同步、cache 失效问题。后续将持续优化 REDTao 存在的一些问题，降低在部分故障场景下对业务的影响。随着 DAU 的持续增长，小红书的数据规模也在持续增长，我们也面临着更多的技术挑战。目前公司内部的 OLTP 图场景主要分为三块：- 社交图谱：通过自研图存储系统 REDTao 满足了社交场景超大规模数据的更新与关联读取问题。目前已经存储了万亿以上规模的关系数据。
- 风控场景：自研图数据库 REDGraph，满足多跳的实时在线查询。目前存储了千亿以上点和边的关系，满足 2 跳以及 2 跳以上的查询。
- 社交推荐：主要是两跳的查询。每天通过 Hive 批量地导入全量的数据，同时通过 DTS 服务近实时的写入更新数据。因为是在线场景，对时延及稳定性的要求非常高，当前的 REDGraph 还无法满足这么高的要求，因此业务方主要是用 RedKV 来存储。
针对以上场景，为了快速满足业务需求，不同业务使用了不同的存储系统：REDTao、REDGraph 和 REDKV。未来，我们希望将 REDGraph 和 REDTao 融合成统一的数据库产品，为公司内部的更多场景赋能。
分享嘉宾
INTRODUCTION
卢亚德
小红书
存储工程师、图数据库负责人
本人毕业于华东师范大学计算机系，先后就职于惠普、EMC、微软、小红书，具有多年分布式存储工作经验，包括对象存储、KV 存储、表格存储以及图数据库等，目前在小红书主要负责图数据库等。