Chubby: 一个面向松耦合分布式系统的锁服务
- Chubby: Google 内部的分布式锁服务, 底层用 Paxos 做共识, 对外暴露"类文件系统的锁 + 小文件 + 事件"接口, 是 etcd / ZooKeeper 这一类协调服务的思想祖宗;
- cell: 一个故障隔离单元, 通常 1 master + 5 replica;
- coarse-grained lock: 粗粒度锁, 持有时间小时/天级 (典型如"我是这个集群的 master"), 跟毫秒级临界区互斥的 fine-grained lock 相对;
- advisory lock: 建议锁, 系统不强制, 靠"守规矩的应用"自觉遵守;
- safety / liveness: 安全性(“坏事永不发生”, 比如绝不脑裂) / 活性(“好事最终发生”, 比如最终能达成决定);
- FLP: Fischer-Lynch-Paterson 1985, 纯异步 + 可能崩溃下, 不存在同时保证 safety 和 liveness 的确定性共识算法;
- failure detector: 失效检测器, 拿"超时 ⟹ 当它死了"把"它死没死"(判不了) 换成"它超时没"(一看就知道);
论文定位
Mike Burrows, “The Chubby lock service for loosely-coupled distributed systems”, OSDI 2006, Google;
署名就 Burrows 一个人, 这不是一篇推公式的理论论文, 而是一篇工程经验总结: Chubby 在 Google 内部已经给 GFS、Bigtable 这些大家伙撑了好几年选主了, 所以全文都是踩坑之后的反思, 读它的正确姿势是"看一个老练的系统工程师, 怎么在一堆现实约束里做取舍"; 时间线上它比 Raft (2014) 还早了整整 8 年, 那会儿 Paxos 基本是异步共识的唯一选项;
Chubby 的核心主张乍一听有点反直觉; 当年要解决分布式选主/协调, "理论正确答案"是给每个应用塞一个 Paxos 库, 让它们自己投票去; 但 Chubby 偏不, 它把共识藏进一个中心化的服务里, 对外只露出一个长得像文件系统的锁接口;
"a lock service is more useful than a Paxos library": 对干活的团队来说, 锁服务比共识库更有用;
得留意这句话批的不是 Paxos 算法本身 (Chubby 底下用的正是 Paxos), 而是"把 Paxos 打包成库直接甩给开发者"这种交付方式; Chubby 对 Paxos 是真爱, 第二年还专门写了篇《Paxos Made Live》讲他们落地踩了多少坑;
§2.1 Rationale: 为什么是锁服务而不是 Paxos 库
先看传统 Paxos library 是怎么活的: 共识逻辑被塞进每个应用/存储节点, 于是这个服务自己的每个 replica 都得:
- 维护 Paxos 状态;
- 参与提案和多数派投票;
- 复制一致性日志;
- 处理 leader 选举、故障恢复、成员变化;
- 把达成共识的日志 apply 到自己的状态机;
说白了就是共识逻辑跟应用的数据存储、业务逻辑死死绑在一起, 每个想搞高可用的服务都得把这套从头扛一遍; Chubby 想破的就是这个局; 这一节给了四条理由, 是全篇的灵魂, 其实就是同一个立场的四个侧面:
| # | 核心论点 | 一句话 |
|---|---|---|
| 1 | 保留既有程序结构, 高可用可以事后补 | 改动小, 不用重写 |
| 2 | 选完主还得昭告天下, 所以得能存点小数据 | 光有锁不够, 还要能存小文件 |
| 3 | 锁/文件接口程序员熟 | 心智成本低 |
| 4 | 客户端不用自己凑多数派就能往前走 | 把 quorum 需求挪进服务内部 |
理由 1: 保留既有结构, 高可用可以事后补
开发者一开始基本不会为高可用做设计, 系统往往就是个原型, 负载又低, 代码压根没按共识协议那套来组织; 等它做大了、用户多了, 才回头想加副本、加选主;
这时候锁服务的好处就出来了: 你几乎不用动原来的结构就能把高可用挂上去; Burrows 举的例子很实在, 让一组进程选出 master、再由它去写一个已有的文件服务器, 用锁服务只要加两条语句和一个 RPC 参数 (“启动时抢个锁, 写的时候带上 lock 信息”) 就完事; 换共识库你就得把整个程序围着状态机重写一遍; 一个是增量改造, 一个是推倒重来;
理由 2: 选完主还得昭告天下, 所以得能存点小数据
很多服务选出 primary、或者把数据分了区之后, 还得有个办法把结果告诉所有人 (“现在谁是 master”、“分区表长啥样”); 光有加锁解锁干不了这事, 你还得能读写一点点数据; 所以 Chubby 顺手让每个 node 能存个小文件; 这活儿本来可以另起一个 name service 来干, 但既然一个强一致的锁服务已经在那杵着了, 把"存结果 + 广播结果"一并接过来最省事;
这也正是 etcd 为啥既是协调原语、又是个 KV 存储: 选主和"把选主结果发出去"本来就是一个需求的两半; 见 etcd;
理由 3: 锁和文件, 程序员熟
程序员都懂锁、都懂文件; 真没几个懂怎么把 Paxos 用对; 拿大家本来就有的心智模型 (acquire/release、open/read/write) 把共识包起来, 上手快, 还不容易用错; 哪怕分布式锁的语义跟单机锁有些微妙的不一样 (这正是后面 sequencer、lock-delay 要补的坑), 这层熟悉的壳还是把采用门槛压得很低;
理由 4: 客户端不用自己凑多数派就能往前走
这条最绕, 也最值得嚼; 最容易卡住的地方是: “Chubby 自己不也得 3/5 多数派吗, 怎么会只要 1 台在线?” 钥匙在于, 这个"1 台在线"说的根本不是 Chubby 的服务器, 而是你自己应用的副本;
先看世界 A (用共识库): 你的应用想高可用就得自己复制自己, 比如跑 3 个副本内嵌 Paxos, 那"做个决定"就得你这 3 个副本里的多数派 (2 台) 同时在线还能互通; 挂到只剩 1 台, 你自己就凑不出多数派, 选不出主, 直接卡死; quorum 的担子全压在你自己的副本集上;
再看世界 B (用锁服务): "谁是主"这个决定外包给 Chubby 了, 谁抢到锁谁是主; 这时候哪怕你的应用只剩 1 个实例活着, 它照样能跑去 Chubby 把锁抢到、当上 primary、接着干活;
1 | 世界A: App副本1 ┐ |
quorum 并没有凭空消失, 只是被搬了个地方、还顺带摊薄了: 从"每个应用各养一套 5 副本 Paxos", 挪进了大家共享的 Chubby 那一套 (3/5):
| 谁背 quorum | 代价 | |
|---|---|---|
| 共识库 | 每个应用各背一套, N 个应用 = N 套 5 副本 | 重复、贵、每个团队都得懂 Paxos |
| 锁服务 | 大家共享 Chubby 这一套 | 一套 5 副本被全公司成百上千应用复用 |
所以理由 4 真正的杠杆是: 多数派这个要求省不掉, 但犯不着让每个客户端都自己扛一份; 集中到一个共享的协调服务之后, 每个客户端就退化成"只要还有 1 个实例 + 能连上 Chubby"就能安全往前走;
两个"1"别搞混: 应用自己的副本只要 1 个实例就能安全当主 (这是重点); 网络上要连的 Chubby 也只有 1 个 master (master 替你在背后扛内部 quorum, 这是接口上的次要简化);
这跟 etcd 在 k8s 里的角色一模一样: 整个集群就一套 etcd 扛共识, 上面成百的控制器、kubelet 各自单实例就行, 没人需要自建一套 Paxos;
退一步看: 这其实是 control plane / data plane 解耦
四条理由合起来, 干的事就是把一个系统切成两个平面:
| control plane (Chubby) | data plane (应用/数据库) | |
|---|---|---|
| 干什么 | 选主、分配资源所有权、维护锁、存少量元数据、给出一致的协调结果 | 真正的数据读写、高吞吐业务、海量存储与计算 |
| 频率 | 低频但要命 | 高频又重 |
| 一致性 | 强一致 (绝不能两个主) | 看业务取舍 |
Chubby 只管"低频但要命"的协调操作, 应用那一大坨数据它根本不碰; 这也解释了它为啥敢做得又小又慢, 但一致性上一步都不让;
一条容易踩的边界: 协调共识 ≠ 数据复制共识
有个地方特别容易想当然: Chubby 都替我做共识了, 那数据库是不是就不用自己搞 Paxos 了? 不是的;
Chubby 替你做的是应用的"协调共识" (谁是主、哪个 shard 归谁), 它不替你做数据库内部的"数据复制共识"; 一个数据库靠 Chubby 选出了 primary 之后, 它自己那几个副本之间怎么复制数据、怎么保证不丢, 该用自己的 Paxos/Raft 还得用;
也正因为这条边界, 一个 Chubby cluster 能同时伺候一大堆数据库, 各用各的锁互不打架:
1 | DB1 → /locks/db1/master |
每个 DB 都不用自己再起一套 Paxos cluster 来选主, 全共享这一个 Chubby, 这就是理由 4 那个"quorum 摊薄"落到地上的样子;
顺带说说为啥 Chubby 这种小集群特别好养
- 节点数量固定还少 (一个 cell 就 5 个), 不像应用节点动不动成千上万;
- 功能单一, 就管协调加一点点元数据, 出错的面小;
- 部署环境和网络都可控, 升级也不勤;
- 可以专门给它上监控、复制、容灾;
- 只要多数 Chubby replica 在线就行, 不要求所有应用节点都在线;
应用节点天天扩容、重启、升级、挂掉, 把高可用这副重担从"每个应用"收拢到"一小撮精心伺候的 Chubby 节点"身上, 整体反而更稳;
系统骨架 (§2 速写)
1 | 一个 cell (故障隔离单元) |
- 一个 cell = 1 master + 通常 5 个副本, 3/5 在线就能干活;
- 只有 master 对客户端服务 (副本只管参与 Paxos 投票, 随时准备顶上来); 这种主从不对称是为了让一致性和顺序好保证, 跟 etcd 里"只有 apiserver 直连 etcd"是一个套路: 把入口收窄换简单;
- 接口是个阉割版文件系统: 每个文件/目录是一个 node, 能加锁、能存小文件、能订阅事件; 但它故意砍掉了部分读写、seek、rename、move、符号链接这些, 它本来就不是真文件系统, 是"披了层文件皮的协调原语";
粗粒度锁 coarse-grained
这是理解 Chubby 最该抓住的词, 但它特别容易被望文生义, 我一开始也想歪了; 先说它不是什么: 不是说降低了一致性, 也不是说把好几个 Paxos log entry 合并成一个;
它真正的意思很朴素: 一次把锁拿到手, 应用就能攥着它干很久很久的活; 比如节点 A 抢到 /db1/master 这把锁, 就成了 DB1 的 primary, 接下来连续处理几百万次读写, 很久之后才把锁还回去; 所以这把锁是给 leader election、primary ownership、shard 分配、配置管理、服务发现这种"抢一次管很久"的活准备的; 你要是想给每条记录加锁、每个事务都来抢一遍, 那就是拿着钉锤拧螺丝了, Chubby 自己也明说这种细粒度的别找它, 自己在应用里做去;
锁攥得久、抢得不勤, 服务端压力就小, 一个 5 副本的 cell 就能扛上万客户端; 它干脆不去卷吞吐, 力气全使在可用性和一致性上; etcd 后来"做得小、强一致、不追吞吐"也是随了这个命, 它接的是 Chubby 协调服务这一脉, 不是通用数据库那一脉;
这里有个巨容易混的点得单拎出来: "粗粒度锁"的长期, 跟 Multi-Paxos/Raft "稳定 leader"的长期, 压根不是一回事, 它俩是上下两层楼:
| 谁 | 干啥 | |
|---|---|---|
| 楼上 (第一层) | Chubby 内部自己选的 master | 处理 Chubby 请求、用 Paxos 复制锁状态; Multi-Paxos 稳定 leader 是它自己内部的实现 |
| 楼下 (第二层) | 应用抢一把 Chubby 锁选出来的 primary | 处理应用自己的数据和业务 |
“粗粒度"说的是楼下, 是应用怎么用这把锁 (一把锁换一个长期 primary); Multi-Paxos 那个稳定 leader 在楼上, 是 Chubby 自己内部怎么省掉"每条 log entry 都重选一次主”; 都叫"长期", 一个楼上一个楼下, 别串;
Paxos 的 safety / liveness 和 FLP
论文里有一句信息量爆炸的理论陈述:
"Paxos maintains safety without timing assumptions, but clocks must be introduced to ensure liveness; this overcomes the impossibility result of Fischer et al."
要拆它, 先把两种"正确"分清楚:
| Safety 安全性 | Liveness 活性 | |
|---|---|---|
| 口号 | 坏事永远不发生 | 好事最终会发生 |
| 共识里 | 绝不会有两个节点对同一位置达成矛盾决定 (不脑裂) | 系统最终一定能达成某个决定, 不会永远卡住 |
| 坏了咋样 | 数据不一致, 灾难, 不可恢复 | 系统挂起不进展, 但数据还是对的 |
记住这个不对称: safety 坏了是灾难, liveness 坏了只是卡一下; 这一整句话的精髓全在这个不对称上;
FLP (1985) 说的是: 在纯异步系统里 (消息延迟没有上界), 只要有一个节点可能崩, 就不存在任何确定性算法能同时保住 safety 和 liveness; 病根还是那句老话, "它到底死没死"在异步里根本判不了 (你分不清它是真死了还是只是慢); 于是算法陷入两难: 死等吧, 万一它真死了你就永远等下去 (liveness 没了); 超时就往前走吧, 万一它没死、过会儿带着旧决定回来了, 就可能撞出两个冲突的决定 (safety 没了);
Paxos 的破法是把这两半拆开, 各用各的招:
- safety 这边无条件成立: 靠的是 ballot number + quorum 交集这套纯逻辑, 不管消息怎么延迟乱序、时钟怎么乱跑, 它就是不会产生冲突决定; 它从来不赌时间, 所以时间怎么坏都坑不到它的 safety, 这对应高亮句的前半句;
- liveness 这边就没法无条件了, 必须请时钟出场: 纯异步下 Paxos 真有可能永远不进展, 经典的就是 dueling proposers, 俩提案者拿越来越大的编号互相抢占, 谁也提交不了; 破法是选一个唯一的 leader 只让它发提案, 而判断"老 leader 死没死"靠的就是超时, 也就是时钟, 这对应后半句;
那它凭啥就 overcome 了 FLP? 注意 Burrows 用的是 overcome (绕过) 不是 disprove (推翻); FLP 的前提是"纯异步", 现实做法就是把这个前提松一松, 加一个很弱的时间假设 (理论上叫 partial synchrony: 延迟和时钟漂移绝大多数时候是有界的), 这在真实机房里几乎永远成立; 有了它, 就能靠超时比较靠谱地判 leader 死活, liveness 也就回来了;
最妙的地方在这: timeout ⟹ 当它死了 这一招, 不是在"定义 liveness", 而是一个允许出错的失效检测器 (failure detector); 它把"死没死"(判不了) 换成"超时没"(本地一看就知道), 然后耍个无赖, 超时了我就当你死; 关键就在于它允许误判: 一个只是 GC 卡了一下的活节点可能被错判成死, 但这个误判只伤 liveness (多选一轮、临时冒出俩 leader), 永远伤不到 safety (safety 是 ballot + quorum 独立死保的); 正因为"判错了也死不了人", 这个粗暴的检测器才敢这么用;
理论上的一对: FLP (1985) 划下界, 说"一点时间假设都不给 → 共识不可解"; Chandra-Toueg (JACM 1996) 补上另一半, 说给共识配一个"最终弱"的失效检测器 ◇W (允许长期犯错但最终大致准), 共识就又可解了;
timeout=死就是 ◇W 最朴素的工程实现;
绕回 lease: 这跟 lease 根本是同一个思想换了个地方又出现了一遍, 都是拿"时间"这个本地说了算的东西, 去替"对方死没死"这个判不了的问题; Chubby 把这套用了两层: 底下 Paxos 用时钟保进展, 上面 session 用 lease 管客户端的死活 (lease 这思想出自 Gray-Cheriton SOSP 1989, Chubby 把它搬到协调服务上, 就是 etcd Lease 的直系祖宗);
待续 / 下一步
- [ ] §2.x session + KeepAlive + lease: jeopardy / grace period, 看它怎么拿时间替故障检测落地;
- [ ] 锁语义 + 防 stale master: advisory lock / sequencer / lock-delay; 以及 Chubby 怎么保证"同一把锁同一时刻只属于一个有效 session": Paxos 对锁状态达成一致 + lease/session 过期 + lock generation number / fencing token 拦住过期 master 写下游;
- [ ] 缓存 + 失效协议 + events: 跟 etcd 的 Watch 摆一起对照;
- [ ] §3 用 Paxos 做的持久化 DB (已懂 Raft, 对照扫一眼即可);
- [ ] §4 scaling: proxy / partition / lease 减负;
- [ ] §7 Lessons Learned (全篇精华, 值得读两遍);