每秒十亿次读、96.4% 由缓存命中：Meta 的 TAO 如何存储社交图谱

English version

这是 🚀 Extreme Scale 系列的第三篇。

先看一个本不该成立的数字。在 2013 年 USENIX ATC 的论文里，TAO 的作者报告：Facebook 全站只有一个 TAO 生产部署、一个逻辑实例，却”持续处理每秒十亿次读和数百万次写“，数据量达数 PB，跑在数千台机器上。而它底下的持久存储不是什么新式数据库——是分片后的 MySQL。

直觉的读法是：Facebook 一定把 MySQL 做快了很多倍。并没有。它从 2009 年初开始做的，是建一层让 MySQL 几乎永远不被问到的东西——其缓存层在生产环境测得整体读命中率 96.4%；而真正落到 MySQL 的问题，都是它擅长的小而规整的子集。TAO（”The Associations and Objects”）最好理解为一组机制：把一台很普通的数据库，挡在一个很不普通的负载前面。每个机制的存在，都对应它所取代的那套系统——memcache 加 MySQL、控制逻辑写在应用代码里——的一个具体失效模式。

背景：一个在浏览时才解析图谱的负载

Facebook 的核心抉择，论文里说得很直白：社交图谱要拉，不要推。一个页面要聚合、过滤数百个条目——信息流、评论、点赞、签到——而每个条目都要按当前浏览者做隐私检查，同一次签到，两个人看到的渲染结果可以不同。这让”写的时候预计算视图”不可行：聚合结果取决于谁在看。于是图谱只能在浏览时逐条解析，预算是几百毫秒。就是这一个产品决策，制造了每秒十亿次读。

这个读负载的三个性质，进而决定了整个设计：

创建时间局部性（creation-time locality）。 图谱里大多数数据是老的，但大多数查询只要最新的那一截：最近 50 条评论、最新的点赞。数据库缓冲池的块缓存利用的是空间局部性——磁盘页上相邻的字节——而这个负载基本没有这种局部性。更糟的是，大量查询是否定的（”这个用户赞过那条动态吗”对信息流里大多数动态都是假），为回答一个这种问题把几 KB 磁盘块拖进缓冲池，只会污染缓存、毫无收益。论文直接点名：正是这种错配，让 InnoDB 缓冲池当不了主缓存。

读流量以边为主，不是以节点为主。 论文抽样的生产读请求里，关联（association）操作约占 71%：assoc range 40.9%、assoc get 15.7%、assoc count 11.7%、assoc time range 2.8%，对象 get 只占 28.9%。一个按 key 取整条记录优化的存储，优化的是少数派流量。热路径是：”把这个节点出发的、这种类型的最新边给我，再告诉我一共有多少条。”

读比写高出几个数量级。 每秒十亿次读对数百万次写，比值在一百到一千比一之间。任何”在读上付协调成本、换写更干净”的设计，都是把钱花错了边。TAO 始终反着来，并明说：它”明确地以效率和可用性优先于一致性”。

数据模型：两种东西，一条分片规则

TAO 的整个数据模型只有两样东西。对象（objects）是有类型的节点——用户、帖子、照片、签到——用全局唯一的 64 位 id 标识，按每类型 schema 存键值字段。关联（associations）是有类型的有向边，用三元组 (id1, atype, id2) 标识，任意两个对象之间同一类型最多一条关联，每条带一个 time 字段。关联列表——某个对象出发的、某一类型的全部边，按 time 降序排列——是 API 围绕的单位：点查询测一条边，范围查询翻最新的边，计数查询从维护好的计数器以常数时间返回列表长度。

让这个模型便宜的机制，是一条放置规则，必须说精确：对象的 id 内嵌其 shard id；关联存放在其 id1 所在的 shard 上。每个关联查询都锚在 id1 上——”这个节点出发的边”——把边和源头放在一起，意味着每个这样的查询恰好由一个 shard、一台服务器服务，没有扇出、没有 scatter-gather。两个对象只有被创建时刻意共置时才会落在同一个 shard。数据集被切成的逻辑 shard 数远超服务器数（工程博客称达数十万个），负载均衡靠重映射 shard 到服务器，热点 shard 可以迁移或克隆，而不用动整个数据集。

这条规则的代价在反方向支付，TAO 付得很坦白。反着走一条边——”谁赞了这条帖子”而非”这个用户赞了什么”——是另一个 shard 上的另一个列表；所以需要双向遍历的类型可以声明逆类型（inverse type），TAO 在每次写时同时维护正反两条边。代价是存储翻倍加两 shard 写，换来两个方向的遍历都是单 shard 读。按上面的读写比，这笔交易是对的——而它的失效模式下面会单独讲，因为这两笔写不是原子的。

同样刻意的是 API 拒绝做的事。没有 join，没有跨 shard 事务，没有服务端图遍历或集合求交：论文的论证是，在用户请求里跑复杂遍历几乎总是设计错误；而在无聚类图谱上，客户端用一串简单的点查询和范围查询编排求交，用的带宽和服务端求交差不多。这个拒绝不是缺功能，而是承重约束。API 足够窄，下面的缓存才能理解自己缓存的是什么——列表、前缀、计数——而不是缓存任何写都可能作废的不透明查询结果。这正是 TAO 与它取代的 memcache 层的根本区别。

memcache 加 MySQL 到底坏在哪

TAO 脱胎于旁路缓存（lookaside cache）：应用代码先查 memcache，未命中回源 MySQL，写后作废缓存条目。论文列出了为什么坏的是这个结构、而不是组件本身。每个失效都是一个机制，TAO 的设计就是逐条回应。

整表作废。 边被存成一个缓存列表条目。一条新评论就要作废整个列表，于是最活跃——因而最有价值——的缓存条目，恰好是最常被销毁的那些。流量越集中的地方，命中率掉得越厉害。

整表传输。 一个只需要三条边的查询，也得把整个列表从 memcache 拉到 web 服务器再在本地过滤，为最终要丢掉的数据付网络和 CPU。

没有控制点。 控制逻辑——谁可以查数据库、同时发生的重复未命中如何合并、失控的客户端如何限流——在每个应用进程里各跑一份、互不协调。某个热点条目过期时，没有任何东西能阻止成千上万台 web 服务器同时未命中、同时锤同一个 shard：惊群（thundering herd）没有守门人。

读后写一致性昂贵。 MySQL 副本异步接收写。在读副本的区域里，用户自己刚写的东西，下一次页面加载可能看不见，除非系统逐 key 跟踪哪些是脏的、绕开复制延迟——即更早的 memcache 工作里的 remote markers 机制——复杂且逐 key 付成本。

TAO 对这四条的回答是同一个结构动作：把控制逻辑从客户端拿走，放进一个自己会说图 API 的缓存服务里。下面逐机制拆。

机制一：双层缓存——leader 是守门人，不是更大的缓存

每个区域跑两层缓存。Follower 面向客户端：服务读、水平扩展，读吞吐随 follower 服务器数量增长。Leader 位于 follower 与 MySQL 之间：每个 shard 恰好由一个 leader 托管，该 shard 的所有写都经过它，它也是该 shard 唯一与数据库对话的一层。

按角色拆层、而不是堆两层相同的缓存，才让下面每个机制成为可能：

抑制惊群。 某个 shard 的每次未命中和写都汇到它唯一的 leader，leader 因此能看到这个 shard 的完整请求流。论文把两个控制写得很直接：leader”不向数据库发出并发的重叠查询”——十个 follower 同一瞬间在同一个列表上未命中，变成一次数据库查询、结果填满所有 follower——”并对发往某个 shard 的待处理查询数设上限”。于是无论前端多突发，数据库看到的每个 shard 的查询率都是有界的。这在旁路设计里原则上不可能：协调点不存在。而在这里它存在，因为架构为每个 shard 造了恰好一个咽喉，并把控制逻辑放了进去。

每 shard 写串行化。 某 shard 的所有写都经过它的 leader，leader 因此对该 shard 天然一致，并发写在这里排队定序、而不是竞速。这是比数据库便宜得多的串行化位置：leader 在内存里、在本区域内，且只串行化写（每秒数百万次），读（每秒十亿次）则在所有 follower 上保持并行。

懂图的缓存，而不是结果缓存。 两层都实现 API，所以它们缓存的是对象、关联列表和计数这些数据结构，而不是查询字符串。缓存里计数为零，就能直接回答一个空结果的范围查询。关联列表只缓存连续前缀——最新的 N 条边——这恰是创建时间局部性说会被问到的那一截。问最近 50 条评论的 assoc range，只要前缀覆盖就永远不碰数据库；老边的长尾根本不在内存里，这是设计，不是淘汰运气。

机制二：write-through，两种不同的维护消息

写后如何更新缓存，同时决定新鲜度和命中率。TAO 用两种不同的消息，因为对象和关联列表在作废之下的死法不同。

对对象，leader 在更新后向每个 follower 发作废（invalidation）。删掉一个缓存对象是安全的：下一次读用一次查询就能回填，别的什么都不丢。

对关联，作废是破坏性的。Follower 只缓存列表的连续前缀；一条边写就作废，可能截断这个前缀、丢掉许多仍然有效的缓存边——等于把 memcache 时代的整表作废病再得一遍。所以 leader 改发回填（refill）消息：如果 follower 缓存了那个关联列表，refill 触发它向 leader 重新查询、就地刷新列表，前缀保持完整且最新。同一个触发，两个动词——因为”删掉它”的成本对单个对象微不足道，对前缀则很贵。

两个细节让这套异步机制站得住。第一，版本号：每条缓存维护消息都带版本号，follower 能识别并忽略已被更新状态越过的维护消息——论文指出，发起写的那个 follower 会在 leader 回复时同步更新，而版本号让它在异步的重复消息随后到达时能将其丢弃。第二，changeset 回复：写成功时 leader 返回实际的变更集，沿链路同步传播到发起写的 follower。这正是 TAO 核心一致性保证——同一层内的读后写一致（read-after-write）——背后的机制：刚点完赞的用户刷新就能看到，不是因为系统强一致，而是因为他自己的写在请求返回之前，就沿回复路径被推进了他所连的 follower 的缓存。其他所有人则异步收敛。

机制三：地理——整图复制、写转发、搭复制流的顺风车

社交图谱高度互联；不存在一种用户划分能让跨区域请求变稀有。TAO 的回应是干脆不在地理上切分：每个区域持有整张数 PB 图谱的完整副本，区域定义为彼此靠近的数据中心集群，区域内延迟通常小于 1 毫秒。于是任何读都能在用户所在区域内、以区域内延迟被完整满足，无论它问什么。

代价落在写上，这是故意的。每个 shard 有唯一的主区域（primary region）；到达次区域的写，由本地 leader 转发到主区域的 leader 执行，再靠普通的 MySQL 异步复制传回来。论文的数字把这种不对称写得很具体：主区域内的平均写延迟是 12.1 ms；从往返延迟 58.1 ms 的区域写，则是 74.4 ms——写付跨区域往返，读永远不付。按十亿比数百万的读写比，用远程写买本地读，算术上毫无悬念。

微妙的机制在于：次区域的缓存何时才该听说一次写。如果次区域 leader 在写一被转发时就作废本地缓存，随后的本地读会从本地 MySQL 副本回填——而副本还没收到这次写——把旧值当成新鲜值缓存起来。TAO 用一个办法避开这个竞态：把作废和回填消息直接嵌进 MySQL 复制流，它们只在引发它们的事务已经应用到本区域副本之后才在该区域投递。于是缓存永远不会在本区域的真相源真正含有该变更之前，先被告知”这个变了”。生产环境测得的复制延迟：副本落后主库的时间，85% 的时间小于 1 秒、99% 小于 3 秒、99.8% 小于 10 秒——这就是次区域客户端对别人的写所实际承受的陈旧度预算。

实测结果

论文的生产数字（2013 年硬件、全区域采样）描绘的是一个几乎全靠缓存干活的系统：

• 整体读命中率 96.4%。 大约每 28 次读才有 1 次落到 MySQL。
• 命中与未命中的延迟。 缓存命中的中位延迟在各类操作上约 1.0–1.3 ms，99 分位约 25–33 ms。未命中的中位延迟 5.0–8.2 ms，而对象 get 未命中的平均延迟达 75.3 ms、99 分位 186.4 ms——长尾几乎全住在未命中路径上，这正是命中率、而不是数据库速度，才是关键指标的原因。
• 可用性。 90 天内，从 web 服务器测得的 TAO 查询失败比例为 4.9 × 10⁻⁶——作者自己加了保留：一次失败的查询会抑制依赖它的后续查询，所以这个数字略有美化。
• 故障转移是日常，不是例外。 采样期内，0.15% 的 follower 未命中绕过故障 leader 直连数据库；0.045% 的写被委派给随机存活的 leader；副本数据库因维护或宕机被提升为主库占 0.25% 的时间。这些路径被设计成正常流量，而不是事故。

TAO 做不到什么——边界即设计

跨 shard 无原子性，包括逆边。 带逆类型的写要动两个 shard，TAO 明确不让这两笔写原子化。故障若落在两者之间，正边存在而逆边缺失——一条”悬空”关联，由异步修复任务事后清理。在这个窗口内读两个方向的任何功能，看到的图会短暂自相矛盾。引用整洁性和这里的一切一样，都是最终的。

高度数对象击穿前缀缓存。 许多对象有超过 6,000 条同类型关联；TAO 不缓存这些完整列表，只缓存前缀。问某个具体边是否存在于这种列表的未缓存尾部的点查询，无法从缓存回答——那条边可能在那儿——所以永远落数据库。论文的缓解办法毫不光鲜：改客户端去查逆方向（等价性让便宜的那边可答），或用计数挑方向。让普通列表快的机制，在结构上看不见大列表的尾巴。

最终一致偶尔会”倒退”。 若某条目在转发写已更新缓存、但复制还没更新本地数据库之前被次区域缓存淘汰，回填可能拉回旧值，客户端会看到数据在同一 follower 层内”回到过去”。论文说这在实践中罕见；但它是”缓存跑在副本前面”的真实后果，不是打个补丁就能去掉的 bug。

强一致只作为可选逃生口存在。 读可以被标记为 critical，此时它会被代理到主区域、读同步的 MySQL 真相源——论文的例子是认证：复制延迟不能让旧凭据还能用。你只为需要它的读付跨区域延迟、放弃可用性故事，不多付一分。这个逃生口的存在本身就是承认：最终一致是按数据类型做的决定，不是一种信仰。

热点对象仍需特殊处理。 一个名人对象可以招来比任何单个 follower 应服务的高几个数量级的读。TAO 的回应是 shard 克隆（多个 follower 服务同一 shard，维护消息扇出到全部克隆）和——在 follower 报告的访问率越过阈值之后——按版本号校验的小型客户端缓存，外加对极热对象限流客户端的选项。分片摊平的是平均负载；名人负载是另一个问题、另一套机器，TAO 如此，处处如此。

可迁移的教训

1. 把 API 收窄到缓存能理解为止。 TAO 的决定性动作是拒绝 join、遍历和跨 shard 事务，于是缓存能把列表、前缀和计数存成一等数据结构，而不是不透明的结果。API 上让出的表达力，换来了它下面 96.4% 的命中率。
2. 为每个 shard 造恰好一个守门人。 控制逻辑住在成千上万个互不协调的客户端里时，惊群和无界的数据库负载无解。每 shard 一个 leader 去重重叠的未命中、给待处理查询封顶、串行化写——而且便宜，因为它只需要在写与未命中的速率上做这件事，不需要在读的速率上做。
3. 对象用 invalidation，列表用 refill。 缓存维护不是一种操作。丢一个单值只值一次回填；丢一个缓存前缀毁掉的是整个工作集。让维护动词匹配丢失该缓存结构的成本。
4. 让一致性消息搭复制流，别在旁边另开一条。 缓存绝不能比本地副本更早知道一次变更，否则回填会把旧数据当新鲜数据缓存。让作废消息搭载运数据的那条流，顺序正确性由构造保证。
5. 有意识地花读写比。 处处本地读、远程写、逆边双份存储、只给写者本人的读后写：TAO 的每个取舍都在花写侧成本与存储，买读侧延迟，因为它的负载是每写对应数百次读。抄任何一条之前先量你自己的比值——写重的负载会让这些选择逐条反转。

十三年过去，TAO 仍是这堂课最清晰的实证：到了极端规模，你很少靠造一个更快的数据库取胜。你靠的是精确决定数据库永远不会被问到哪些问题——再建一层来强制执行这个决定。

Sources

• Bronson, Amsden, Cabrera, Chakka, Dimov, Ding, Ferris, Giardullo, Kulkarni, Lawrence, Marchukov, Petrov, Puzar, Venkataramani, “TAO: Facebook’s Distributed Data Store for the Social Graph,” USENIX Annual Technical Conference (ATC ‘13), 2013. https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf ——数据模型、shard 放置规则、leader/follower 设计、refill 与 invalidation 之分、复制流嵌入，以及全部生产数字（每秒十亿读、数百万写、96.4% 命中率、延迟表、复制延迟、4.9 × 10⁻⁶ 失败率、读流量构成）均出自该论文。
• Mark Marchukov, “TAO: The power of the graph,” Engineering at Meta, June 25, 2013. https://engineering.fb.com/2013/06/25/core-infra/tao-the-power-of-the-graph/ ——memcache/MySQL 背景、创建时间局部性、API 概览、数十万 shard、主/次区域设计均出自该文。