本文由小红书基础架构存储组空洞和刘备分享，原题“小红书如何应对万亿级社交网络关系挑战？图存储系统 REDtao 来了！”，本文有修订和改动。
1、引言
小红书是一个社区属性为主的产品，它涵盖了各个领域的生活社区，并存储海量的社交网络关系。
为了解决社交场景下超大规模数据的更新与关联读取问题，并减少数据库压力和成本，我们自研了面向超大规模社交网络的图存储系统 REDtao，大大提高了系统稳定性。该系统借鉴了 Facebook 的图存储系统设计，将缓存和底层数据库封装起来，并对外提供统一的图查询 API，实现了访问收敛，同时在缓存中实现了高效的边聚合。
本文将为你分享小红书面向超大规模社交网络的图存储系统REDtao的架构设计与技术实践过程，希望能带给你启发。
技术交流：
- 移动端IM开发入门文章：《新手入门一篇就够：从零开发移动端IM》
- 开源IM框架源码：https://github.com/JackJiang2011/MobileIMSDK（备用地址点此）
（本文已同步发布于：http://www.52im.net/thread-4495-1-1.html）
2、关于作者
空洞：小红书基础架构存储组，负责图存储系统 REDtao 和分布式缓存的研发。
刘备：小红书基础架构存储组负责人，负责REDkv / REDtao / REDtable / REDgraph 的整体架构和技术演进。
基础架构存储组是给小红书的业务部门提供稳定可靠的存储和数据库服务，满足业务对存储产品的功能、性能、成本和稳定性要求。目前负责自研分布式 KV、分布式缓存、图存储系统、图数据库和表格存储。
已上线的存储产品包括：
- 1）REDkv : 分布式高性能 KV；
- 2）REDtao ：满足一跳查询的高性能图存储数据库；
- 3）REDtable ：提供 Schema 语义和二级索引的表格存储；
- 4）REDgraph ：提供两跳及以上的图语义查询数据库。
3、技术背景
小红书是以年轻人为主的生活记录、分享平台，用户可以通过短视频、图文等形式记录生活点滴，分享生活方式。
在小红书的社交领域里，我们有用户、笔记、商品等实体，这些实体之间有各种各样的关系。
例如：用户与笔记之间可能存在“拥有”（发布）、“点赞”、“收藏”等三种关系，同时还存在对应的反向关系“被点赞”，“被收藏”等。
小红书的社交图谱数据已经达到了万亿条边的规模，且增长速度非常快。当用户登陆小红书时，每个用户都会看到关注的好友、粉丝、点赞、收藏以及其他为其量身定做的内容。
这些信息高度个性化，需要实时从这些海量社交关系数据中读取用户相关信息。这是一个读为主的过程，读取压力非常大。
过去，我们将这些社交图谱数据都存储在运维成熟的 MySQL 数据库中。
然而，即使我们只有百万请求每秒的规模，MySQL 的 CPU 使用率仍然到达了 55% 。随着用户和 DAU 爆发式的增长，需要不断扩容 MySQL 数据库，这带来了巨大的成本和稳定性压力。
为了解决这些问题且考虑到没有合适的开源方案，2021 年初我们开启了从 0 到 1 自研 REDtao 的历程。
4、方案调研和API设计
4.1方案调研
我们充分调研了业内其他厂商的实现，发现有着强社交属性的公司基本上都有一个自研的图存储系统（如下图所示）。
比如：
- 1）Facebook 实现了一个叫做 “TAO” 专门的分布式社交图谱数据库，并将其作为最核心的存储系统；
- 2）Pinterest 和 Facebook 类似，也实现了类似的图存储系统；
- 3）字节跳动自研了 ByteGraph 并将其用于存储核心的社交图谱数据；
- 4）Linkedln 在 KV 之上构建了社交图谱服务。
考虑到当时我们的社交图谱数据已经存放在 MySQL 数据库上且规模巨大，而社交图谱数据服务是非常重要的服务，对稳定性的要求非常高。回溯 Facebook 当年遇到的问题和我们类似，数据存储在 Memcache 和 MySQL 中。因此，参考 Facebook 的 Tao 图存储系统更贴合我们的实际情况和已有的技术架构，风险更小。
4.2API设计
社交图谱的访问主要是边的关系查询。
我们的图模型将关系表示为一个 <key, value> 对，其中 key 是 ( FromId, AssocType, ToId ) 的三元组，value 是属性的 JSON 格式。
比如“用户 A ”关注“用户 B ”，映射到 REDtao 的数据存储结构为：
1<FromId:用户A的ID, AssocType：关注， ToId：用户B的ID> -> Value （属性的json字段）
我们对业务方的需求进行分析，封装了 25 个图语义的 API 给业务方使用，满足了其增删改查的需求，并收敛业务方的使用方式。
相比于 Facebook 的 Tao，我们还补充了社交图谱所需要的图语义，为反作弊场景提供了额外的过滤参数。
同时，在缓存层面，我们支持对不同的字段在缓存中配置局部二级索引。
下面给一些典型的使用场景。
1）场景一：获取关注了 A 的所有正常用户（并且剔除作弊用户）：
1getAssocs(“被关注类型”, 用户A的ID, 分页偏移量, 最大返回值, 只返回正常用户，是否按照时间从新到旧)
2）场景二：获取 A 的粉丝个数（并且剔除作弊用户）：
1getAssocCount(“被关注类型”, 用户A的ID, 只返回正常用户)
5、整体架构设计
REDtao 的架构设计考虑了下面这几个关键的要素：
整体架构分为三层：
- 1）接入层；
- 2）缓存层；
- 3）持久层。
业务方通过 REDtao SDK 接入服务。
如下图：
在这个架构中：和 Facebook Tao 不一样的是，我们的缓存层是一个独立的分布式集群，和下面的持久层是解耦的。缓存层和下面的持久层可以独立的扩容缩容，缓存分片和 MySQL 分片不需要一一对应，这样带来了更好的灵活性，MySQL 集群也变成了一个可以插拔替换的持久存储。
1）读流程：客户端将读请求发送给 router，router 接收到 RPC 请求后，根据边类型选择对应的 REDtao 集群，根据三元组 ( FromId, AssocType, ToId ) 通过一致性 Hash 计算出分片所在的 Follower 节点，将请求转发到该节点上。Follower 节点接收到该请求，首先查询本地的图缓存，如果命中则直接返回结果。如果没有命中，则将请求转发给 Leader 节点。同样的，Leader 节点如果命中则返回，如果不命中则查询底层 MySQL 数据库。
2）写流程：客户端将写请求发送给 router，和读流程一样，会转发到对应的 Follower 节点上。Follower 节点会转发写请求给 Leader 节点，Leader 节点转发给 MySQL，当 MySQL 返回写入成功后，Leader 会清除本地图缓存对应的 Key，并同步给其他所有 Follower 清除掉该 Key，保证数据的最终一致性。
6、高可用设计
REDtao 分为独立的两层：缓存层和持久层。每一层都保证高可用性。
1）自研的分布式缓存：
我们自研了实现图语义的分布式 cache 集群，支持故障自动检测和恢复、水平扩缩容。
它是一个双层 cache，每个分片都有一个 Leader 和若干个 Follower。所有的请求都先发给外层的 Follower，再由 Follower 转发给 Leader。这样的好处是读压力大的时候只需要水平扩展 Follower，单点 Leader 写入的方式也降低了复杂度，更容易实现数据的一致性。
如果一个副本故障，系统会在秒级别内进行切换。当持久层发生故障时，分布式缓存层仍然可以对外提供读取服务。
2）高可用的MySQL集群：
MySQL 集群通过自研的中间件实现了分库分表方案，并支持 MySQL 的水平扩容。每个 MySQL 数据库有若干从库，并且与公司内部其他的 MySQL 运维方案一致，保证高可用性。
3）限流保护功能：
为防止缓存击穿导致 MySQL 突发大量请求，从而导致 MySQL 宕机，我们通过限制每个主节点最大 MySQL 并发请求数来实现限流保护 MySQL。达到最大并发请求限制之后的请求会被挂起等待，直到已有请求被处理返回，或者达到等待超时请求被拒绝不会被继续请求到 MySQL 。限流阈值在线可调，根据 MySQL 集群规模调整对应限制。
为防止爬虫或者作弊用户频繁刷同一条数据，我们利用 REDtaoQueue 顺序执行对写入或者点查同一条边的请求，队列长度会被限制，控制同一时间大量相同的请求执行。相比于单个全局的队列控制所有请求的方式，基于每个请求的队列可以很好地限制单个同一请求，而不影响其他正常请求。
7、高性能设计
数据结构的设计是 REDtao 高性能的重要保证。
我们采用了三层嵌套 HashTable 的设计, 通过根据某个起点 from_id 从第一级 HashTable 中查找到 REDtaoGraph，记录了所有 type 下对应的所有的出边信息。
接着，在第二级 HashTable 中，根据某个 type_id 查找到 AssocType 对应某个 type 下边所有出边的计数、索引以及其他元数据。
最终在最后一级 HashTable ，通过 AssocType 的某个 to_id 查找到最终边信息。
我们记录了创建时间、更新时间、版本、数据以及 REDtaoQueue，time_index 则对应根据创建时间排序列表。
最后一级 HashTable 以及索引限制存储最新的 1000 个边信息，以限制超级点占据过多内存，同时集中提高最新热数据的查询命中率以及效率。REDtaoQueue 用于排队当前某个关系的读写，只记录了当前最后一个请求的元数据。
每次查询或写入时，首先查询 REDtaoAssoc：
- 1）若缓存不存在，则会首先创建只包含 REDtaoQueue 的对象；
- 2）若缓存已存在，则会更新队列元数据，将自己设置为队列的最后一个请求，并挂起等待被执行。
通过这种多层 hash+ 跳表的设计，我们能高效地组织点、边、索引、时间序链表之间的关系。内存的申请、释放在同一个线程上完成。
在线上环境中，我们的系统可以在一台 16 核的云厂商虚拟机上跑到 150w 查询请求/s，同时 CPU 利用率仅有 22.5% 。下方是线上集群的一个监控图，单机的 QPS 到达 3w ，每个 RPC 请求聚合了 50 个查询。
8、易用性设计
1）丰富的图语义 API ：
我们在 REDtao 中封装了 25 个图语义的 API 给业务方使用，满足了业务方的增删改查的需求。业务方无需自行编写 SQL 语句即可实现相应操作，使用方式更加简单和收敛。
2）统一的访问 URL ：
由于社区后端数据太大，我们按照不同的服务和优先级拆分成了几个 REDtao 集群。
为了让业务方不感知后端的集群拆分逻辑，我们实现了统一的接入层。
不同的业务方只需使用同一个服务 URL ，通过 SDK 将请求发送到接入层。接入层会接收到不同业务方的图语义的请求，并根据边的类型路由到不同的 REDtao 集群。它通过订阅配置中心，能够实时感知到边的路由关系，从而实现统一的访问 URL，方便业务方使用。
9、数据一致性设计
作为社交图谱数据，数据的一致性至关重要。我们需要严格保证数据的最终一致性以及一定场景下的强一致性。为此，我们采取了以下措施：
1）缓存更新冲突的解决：
REDtao 为每个写入请求生成一个全局递增的唯一版本号。在使用 MySQL 数据更新本地缓存时，需要比较版本号，如果版本号比缓存的数据版本低，则会拒绝此更新请求，以避免冲突。
2）写后读的一致性：
Proxy 会将同一个 fromId 的点或边请求路由到同一个读 cache 节点上，以保证读取数据一致性。
3）主节点异常场景：
Leader 节点收到更新请求后，会将更新请求变为 invalidate cache 请求异步的发送给其他 follower，以保证 follower 上的数据最终一致。在异常情况下，如果 Leader 发送的队列已满导致 invalidate cache 请求丢失，那么会将其他的 follower cache 全部清除掉。
如果 Leader 故障，新选举的 Leader 也会通知其他 follower 将 cache 清除。
此外，Leader 会对访问 MySQL 的请求进行限流，从而保证即使个别分片的cache被清除掉也不会将 MySQL 打崩。
4）少量强一致的请求：
由于 MySQL 的从库也提供读服务，对于少量要求强一致的读请求，客户端可以将请求染上特殊标志，REDtao 会透传该标志，数据库 Proxy 层会根据该标志将读请求转发到 MySQL 主库上，从而保证数据的强一致。
10、 跨云多活设计
跨云多活是公司的重要战略，也是 REDtao 支持的一个重要特性。
REDtao 的跨云多活架构整体如下：
这里不同于 Facebook Tao 的跨云多活实现，Facebook Tao 的跨云多活实现如下图所示。
Facebook 的方案依赖于底层的 MySQL 的主从复制都通过 DTS Replication 来做。而 MySQL 原生的主从复制是自身功能，DTS 服务并不包含 MySQL 的主从复制。该方案需要对 MySQL 和 DTS 做一定的改造。前面说到，我们的缓存和持久层是解藕的，在架构上不一样。
因此，REDtao 的跨云多活架构是我们结合自身场景下的设计，它在不改动现有 MySQL 功能的前提下实现了跨云多活功能。
1）持久层我们通过 MySQL 原生的主从 binlog 同步将数据复制到其他云的从库上。其他云上的写请求和少量要求强一致读将被转发到主库上。正常的读请求将读取本区的 MySQL 数据库，满足读请求对时延的要求。
2）缓存层的数据一致性是通过 MySQL DTS 订阅服务实现的，将 binlog 转换为 invalidate cache 请求，以清理掉本区 REDtao cache 层的 stale 数据。由于读请求会随机读取本区的任何一个 MySQL 数据库，因此 DTS 订阅使用了一个延迟订阅的功能，保证从 binlog 同步最慢的节点中读取日志，避免 DTS 的 invalidate cache 请求和本区 read cache miss 的请求发生冲突从而导致数据不一致。
11、云原生实现
REDtao 的云原生特性重点体现在弹性伸缩、支持多 AZ 和 Region 数据分布、产品可以实现在不同的云厂商间迁移等几个方面。REDtao 在设计之初就考虑到支持弹性扩缩容、故障自动检测及恢复。
随着 Kubernetes 云原生技术越来越成熟，我们也在思考如何利用 k8s 的能力将部署和虚拟机解绑，进一步云原生化，方便在不同的云厂商之间部署和迁移。
REDtao 实现了一个运行在 Kubernetes 集群上的 Operator，以实现更快的部署、扩容和坏机替换。
为了让 k8s 能感知集群分片的分配并且控制同一分片下的 Pods 调度在不同宿主机上，集群分组分片分配由 k8s Operator 渲染并控制创建 DuplicateSet （小红书自研 k8s 资源对象）。
REDtao 则会创建主从并根据 Operator 渲染出来的分片信息创建集群，单个 Pod 故障重启会重新加入集群，无需重新创建整个集群。集群升级时，Operator 通过感知主从分配控制先从后主的顺序，按照分片分配的顺序滚动升级以减少升级期间线上影响。
12、老服务的平滑升级实践
但凡变革，皆属不易。实现全新的 REDtao 只是完成了相对容易的那部分工作。
小红书的社交图谱数据服务已经在 MySQL 上运行多年，有很多不同的业务跑在上面，任何小的问题都会影响到小红书的在线用户。因此，如何保证不停服的情况下让现有业务无感知地迁移到 REDtao 上成为一个非常大的挑战。
我们的迁移工作关键有两点：
1）将老的大 MySQL 集群按优先级拆分成了四个 REDtao 集群。这样，我们可以先将优先级最低的服务迁移到一个 REDtao 集群，充分灰度后再迁移高优先级的集群；
2）专门开发了一个 Tao Proxy SDK，支持对原来的 MySQL 集群和 REDtao 集群进行双写双读，数据校验比对。
迁移时：我们首先将低优先级的数据从 MySQL 通过 DTS 服务迁移到了一个 REDtao 集群，并升级好业务方的 SDK 。DTS 服务一直对增量数据进行同步。业务方 SDK 会订阅配置中心的配置变更，我们修改配置让 Tao Proxy SDK 同时读写 MySQL 集群和 REDtao 集群，并关闭 DTS 服务。此时会使用 MySQL 集群的结果返回给用户。
在停止 DTS 服务时：有可能会有新的 MySQL 数据通过 DTS 同步过来，造成了 REDtao 集群新写的数据被同步过来的老数据覆盖。因此，在关闭 DTS 服务后，我们会通过工具读取开双写之后到关闭 DTS 服务这个时间段的 binlog 对数据进行校验和修复。
修复完成之后：Tao Proxy SDK 的双读会展示两边不一致的数据量，并过滤掉因为双写时延不一致导致数据不一致的请求。灰度一段时间后观察到 diff 的数目基本为 0，将 Tao Proxy SDK 的配置改为只读写新的 REDtao 集群。
最终：我们在 22 年初完成小红书所有核心社交图谱万亿边级别数据的迁移和正确性校验，并做到了整个迁移服务无感知，迁移过程没有发生一起故障。
13、新图存储系统带来的结果和收益
我们的社交图谱数据访问中，90% 以上的请求都是读请求，并且社交图谱的数据有非常强的时间局部性（即最近更新的数据最容易被访问）。REDtao 上线后，获得 90% 以上的 cache 命中率， 对MySQL 的 QPS 降低了 70%+ ，大大降低了 MySQL 的 CPU 使用率。在缩容 MySQL 的副本数目后，整体成本降低了21.3%。
业务的访问方式都全部收敛到 REDtao 提供的 API 接口上，在迁移过程中，我们还治理了一些老的不合理访问 MySQL 数据库的方式，以及自定义某些字段赋予特殊含义的不合理做法，通过 REDtao 规范了数据访问。
对比 2022 年初和 2023 年初，随着 DAU 的增长，社交图谱的请求增长了 250% 以上，如果是之前 MySQL 的老架构，扩容资源基本上和请求增长速度成正比，至少需要扩容 1 倍的资源成本（数万核）。
而得益于 REDtao 系统的存在，因其 90% 的缓存命中率，实际上整体成本只增加了 14.7%（数千核）就能扛下 2.5 倍的请求增长。在成本和稳定性上有了较大的提升。
14、未来展望
在较短的时间，我们自研了图存储系统 REDtao ，解决了社交图谱关系数据快速增长的问题。
REDtao 借鉴了 FaceBook Tao 的论文，并对整体架构、跨云多活做了较多的改进，全新实现了一个高性能的分布式图缓存，更加贴合我们自身的业务特点和提供了更好的弹性。同时，利用 k8s 能力进一步实现了云原生化。
随着 DAU 的持续增长，万亿的数据规模也在继续增长，我们也面临着更多的技术挑战。
目前公司内部的 OLTP 图场景主要分为三块：
1）社交图谱数据服务：通过自研图存储系统 REDtao 满足了社交场景超大规模数据的更新与关联读取问题。目前已经存储了万亿规模的关系；
2）风控场景：通过自研图数据库 REDgraph，满足多跳的实时在线查询。目前存储了千亿点和边的关系，满足 2 跳以及 2 跳以上的查询；
3）社交推荐：这块主要是两跳的查询。每天通过 Hive 批量地导入全量的数据，通过 DTS 服务近实时的写入更新数据。因为是在线场景，对时延的要求非常高，当前的 REDgraph 还无法满足这么高的要求，因此业务方主要是用 REDkv 来存储。
针对以上场景：为了快速满足业务需求，我们使用了三套不同的自研存储系统：REDtao 、REDgraph 和 REDkv 。
显然相对于 3 套存储系统，用一个统一的架构和系统去解决这几个图相关的场景是更加合适的。
未来：我们会将 REDgraph 和 REDtao 融合成一个统一的数据库产品，打造业内顶尖的图技术，对公司内部更多的场景进行赋能。
15、相关资料
[1] 以微博类应用场景为例，总结海量社交系统的架构设计步骤
[3] 基于社交网络的Yelp是如何实现海量用户图片的无损压缩的？
[4] 社交软件红包技术解密(一)：全面解密QQ红包技术方案——架构、技术实现等
[5] 社交软件红包技术解密(六)：微信红包系统的存储层架构演进实践
[6] 社交软件红包技术解密(九)：谈谈手Q红包的功能逻辑、容灾、运维、架构等
[7] 渐行渐远的人人网：十年亲历者的互联网社交产品复盘和反思
[9] 盘点移动互联网时代的社交产品进化史（上篇）：谁主沉浮
[10] 盘点移动互联网时代的社交产品进化史（下篇）：大浪淘沙
（本文已同步发布于：http://www.52im.net/thread-4495-1-1.html）
