Raft 协议:选举、日志复制与强一致
Raft 协议 本文是分布式算法科普系列第二篇。上一篇讲了 Distro 协议如何用"去中心化 + 异步同步"实现 AP 模型——写完立刻返回、事后慢慢对齐。这一篇讲它的反面:Raft 如何用"选出一个老板 + 事事多数同意"实现 CP 模型——宁可暂时不可用、绝不返回错误数据。 一、故事:Paxos 太难了,于是有了 Raft 在 Raft 出现之前,分布式共识领域有一个"上古神器"——Paxos。Paxos 由 Leslie Lamport(就是写 LaTeX 的那位)在 1989 年提出,理论正确性无可挑剔,但有一个致命的工程问题:几乎没有人能真正看懂它。 Lamport 在 1998 年发表了一篇补充论文《Paxos Made Simple》,摘要第一句话就是——“The Paxos algorithm, when presented in plain English, is very simple."(用大白话讲,Paxos 其实很简单。)但工程界的反馈很统一:不,它一点也不 simple。 这不是段子,是真实历史。Google 的 Chubby 分布式锁系统在实现 Paxos 的过程中遇到了大量问题,Chubby 的作者 Mike Burrows 有一句著名的吐槽:“世界上只有两种共识算法——Paxos 和那些没人能证明正确的算法。” 2013 年,斯坦福大学的博士生 Diego Ongaro 和导师 John Ousterhout 决定正面解决这个问题。他们的出发点和前面所有人都不一样——把"可理解性"作为算法的首要设计目标,而不是附带的副产品。 Ongaro 从头设计了一个全新的共识算法,刻意把整个协议拆成三个相对独立的模块——领导者选举、日志复制、安全保证——每个模块都可以单独理解。2014 年,他们发表了论文《In Search of an Understandable Consensus Algorithm》(寻找一个可理解的共识算法),Raft 正式诞生。 ...