烦人的数据不一致问题到底怎么解决？

一、“共识”是什么？为什么会产生？

分布式系统中的一致性问题其实是一个「结果」，本质是由于数据冗余导致的，如果没有冗余，也就不会有一致性问题了。

分布式系统里的各个子系统之间之所以能够相互协作，就是因为其之间冗余了相同的数据作为“信物”，要不然我都不认识你的话，为什么要配合你干活呢。所以这个“信物”变了，你得通知我，要不然我又不认识你了。这个“信物”变更达成一致性的过程称作达成「共识」。所以：

一致性问题是结果，共识是为达到这个结果所要经过的过程，或者说一种手段。

在分布式系统中，冗余数据的场景不限于此，因为规模越大的系统，越不能容忍某一个子系统出问题后产生蝴蝶效应，所以往往会做高可用。小明 1 号倒下了还有千千万万个小明 X 号在坚守岗位，理想中的全天候 24 小时提供服务~。高可用的本质是通过相同数据存储多个副本，并都可对外提供服务。比如每个小明 X 号都有一本《按摩指法白皮书》，谁请假了都可以由其它小明 X 号提供相同的按摩服务。但是这个本《按摩指法白皮书》改了，就得通知到每个人，因为这是服务的全部和来源，所以在做了高可用的集群中数据冗余的问题更为突出。

实际上，如果分布式系统中各个节点都能保证瞬时响应、无故障运行，则达成共识很容易。就好像我们人一样，在一定范围内只要吼一嗓子，通过稳定的空气传播，相关人是否接收到这个消息，并且给出响应几乎可以是“瞬时”的。但是正如〖上篇，?点我〗文中提到，这样的系统只停留在想象中，响应请求往往存在延时，网络会发生中断，节点发生故障，甚至存在恶意节点故意要破坏系统。这就衍生出了经典的「拜占庭将军问题」 ^[1]。

二、拜占庭将军问题

我们一般把「拜占庭将军问题」分为 2 种情况来看待。

1. 拜占庭错误。表示通过伪造信息进行恶意响应产生的错误。

2. 非拜占庭错误。没有进行响应产生的错误。

这个问题的核心在于：

如何解决某个变更在分布式网络中得到一致的执行结果，是被参与多方都承认的，同时这个信息是被确定的，不可推翻的。

好比如何让所有的小明 X 号收到的都是《按摩指法白皮书Ⅱ》，而不是其它的，并且把原来的那本销毁掉。这个问题衍生出了很多“共识”算法，解决「拜占庭错误」的称作 Byzantine Fault Tolerance（BFT）类算法，解决「非拜占庭错误」的称作 Crash Fault Tolerance（CFT）类算法。从这个 2 个名字中也可以看出，本质的工作就是「容错」。有的小伙伴在平时的工作中可能对「容错」的重要性感知没那么强烈，不就产生一个 BUG 或者异常数据么，但是在航天领域，一个小错误可能导致整个发射的失败，代价非常巨大。

对「拜占庭将军问题」想深入的了解的，可以自行查阅相关资料，这里就不展开了，文末附上提出时的论文。

我们常见的软件开发中一般不会考虑「拜占庭错误」，但它是区块链项目的必需品。不过在主流的分布式数据库中，皆能看到「非拜占庭错误」的身影，诸如 Tidb 的 Paxos 算法，CockroachDB 的 Raft 算法。虽然我们大家在日常的 coding 中，对数据库底层原理的了解并不是必须项。但是只要当我们涉及到应用程序级别的高可用时，那么至少「非拜占庭错误」是必须要面临的一道坎。

三、BFT 类算法

BFT 类型算法又有 2 个分支。「基于确定性的」和「基于概率的」。

先聊聊「基于确定性的」，此类算法表示一旦对某个结果达成共识就不可逆转，即共识是最终结果。它的代表作是 PBFT（Practical Byzantine Fault Tolerance）算法 ^[2]，自从有了央行背书（区块链数字票据交易平台），名声更大了。算法的原理，如下图。

▲图片来源于网络，版权归原作者所有

拿军队来比喻，这里的直线 C 可以认为是“总司令”，直线 0 是“军长”，直线 1、直线 2、直线 3 都是“师长”，值得注意的是 3 号师长叛变了。整个过程这样解释。

1. 「request」：总司令给军长下了一个命令，“干！”。

2. 「pre-prepare」：军长把命令又广播给 3 个师长。

3. 「prepare」：每个师长收到并同意之后将发送“收到”给军长和其他两个师长。

4. 「commit」：每个师长收到 2f 个师长（军长不做 prepare）的“收到”请求后发送“随时开干”给军长和其他两个师长。（f 为可容忍的拜占庭节点数）

5. 「reply」：每个师长收到 2f+1 条“随时开干”消息之后，就能认为总司令的命令在相关的师长中都到达了“随时开干”的状态，那么他就直接开炮了！

真正深入了解 PBFT 的话还有很多内容，这里就不继续展开了，有兴趣的小伙伴自行查阅文末论文地址或者直接 通过文末的百度云链接打包下载。

再聊聊「基于概率的」，此类算法的共识结果则是临时的，随着时间推移或某种强化，共识结果被推翻的概率越来越小，成为事实上的最终结果。它的代表作是 PoW（Proof of Work）算法，曾经高达 2W 美元 / 个的比特币就是基于这个算法来实现的。算法的原理拿“修仙”来做个简单的比喻（实际比特中的算法比这更复杂）。

• 自己努力修炼，并让神仙中大于一半的人认可你的修为，同意你成仙。

• 随之你就成为了神仙。并且参与到评判后续其他人是否可以成为“神仙”的事情中去。

• 这个事情如果想通过贿赂来达到的话，随着这个团队的人数越多，贿赂的成本越大，就可以认为去做贿赂的人越少，那么导致被误判的概率就越低，最终就越可信。

被误判的概率公式是： 0.5 ^ 个数，如果个数 =6 的话，误判的概率是 1.5625%。如果个数 =10 的话，就已经是 0.09765625% 了，指数级下降。

值得注意的是，「基于确定性的」和「基于概率的」对于不合作节点的标准是不同的，前者至多能容忍 1/3，后者是小于 1/2。

四、CFT 类算法

正如上面所说 CFT 类算法解决的是分布式系统中存在故障，但不存在恶意节点的场景（即可能消息丢失或重复，但无错误消息）下的共识达成问题。「拜占庭将军问题」的提出者 Leslie Lamport 也在他另外的论文 ^[3]中提出过「Paxos 问题」，与这相似。在论文中通过一个故事类比了这个问题，如下：

希腊岛屿 Paxon 上的「执法者」在「议会大厅」中表决通过『法律』，并通过「服务员」传递纸条的方式交流信息，每个「执法者」会将通过的『法律』记录在自己的「账目」上。问题在于「执法者」和「服务员」都不可靠，他们随时会因为各种事情离开「议会大厅」，并随时可能有新的「执法者」进入「议会大厅」进行法律表决。使用何种方式能够使得这个表决过程正常进行，且通过的『法律』不发生矛盾。

—— 百度百科

这里的关键对象在我们的系统中，可以类比为：

• 议会大厅 = 分布式系统

• 执法者 = 某个程序

• 服务员 = RPC 通道

• 账目 = 数据库

• 法律 = 一次变更操作

Leslie Lamport 自己也提出了解决这个问题的算法，「Paxos」算法 ^[4]。这个算法的关键由以下 3 个定义来体现。

• 每次“变更”都有个唯一的序号，并且能够通过它识别新旧。

• 「执法者」只能接受比已知的“变更”更新的变更。

• 任意两次“变更”必须有相同的「执法者」参与。

这 3 点仅仅是保证一致性的最关键部分，全部内容还有很多。有兴趣的小伙伴自行查阅文末论文地址或者直接 通过文末的百度云链接打包下载。

「Paxos」算法是一种无领导人（Leaderless）算法，实现比较复杂，所以产生了很多变种来简化它，其中名气最大的应该是「Raft」，2013 年才问世。「Raft」算法是一种领导人（Leadership）的算法。由以下 2 个过程保证达成共识。

• 只会存在一个活着的领导人，领导人负责跟随者的数据同步。

• 如果领导人“失联”了，那么每个跟随者都可成为候选人，最终比较谁的 term 最新，谁就是新的领导人。这个 term 是每个节点内部维护的一个自增数。

虽然跟随者的投票秉承先到先得，但是还是会遇到多个 term 相同的候选人获得了相同票数（简称「分割投票问题」），那么进行新一轮投票，直到决出胜负为止。由于 Raft 用随机定时器来自增 term，加上网络是不稳定的，所以再次遇到相同票数的概率就大大降低了。        完整的过程更复杂一些，有一个 Raft 算法的动画推荐给大家，有兴趣的可以了解一下：http://thesecretlivesofdata.com/raft/。

题外话，大家经常用的 Zookeeper 里的「ZAB」（ZooKeeper Atomic Broadcast）算法也是 CFT 类算法，是以 Fast Paxos 算法为基础实现的。

五、结语

回过头来看，我们发现，想要更严谨的一致性，那么就需要增加相互通讯确认的次数，但是这会导致性能低下，正如 PBFT 和 Paxos 一样。但是分布式系统就是这样，到处都需要 Balance，找到最适合的才是最重要的。

聊完了数据层面的「共识」问题，我们下回再聊聊「分布式事务」的问题，围绕着常见的 CAP、BASE 理论展开。

最后如果说想成为数据一致性专家，问有没有捷径的话。去阅读老爷子 Leslie Lamport 的论文就是捷径，他的个人主页：http://www.lamport.org/ 。

文中相关链接如下。

[1]《The Byzantine Generals Problem, ACM Transactions on Programming Languages and Systems》, Leslie Lamport, 1982.

[2]《Practical Byzantine Fault Tolerance》, Miguel Castro&Barbara Liskov, 1999.

[3]《The Part-Time Parliament》, Leslie Lamport, 1998.

[4]《In Search of an Understandable Consensus Algorithm》, Diego Ongaro&John Ousterhout, 2013

百度云链接打包下载
链接：https://pan.baidu.com/s/1fsk63fW4ngZVus07nNEOBA
密码: fcvs

作者介绍

张帆（Zachary），7 年电商行业经验，5 年开发团队管理经验，4 年互联网架构经验，目前任职于上海可得网络科技 (集团) 首席架构师。专注大型系统架构、分布式系统。坚持用心打磨每一篇原创。本文首发于公众号：跨界架构师（ID：Zachary_ZF）。

---

ArchSummit 全球架构师峰会将于 12 月 7-8 日在北京国际会议中心举办，会议专题聚集了微服务金融架构、微服务架构、数据基础平台建设、短视频架构、区块链、信息隐私安全等话题。邀请了阿里巴巴、Netflix、百度、LinkedIn 等公司的技术专家来分享。

大会 7 折报名中，立减 2040 元，有任何问题欢迎咨询票务经理 Lachel- 灰灰，电话 / 微信：17326843116

关注公众号：拾黑（shiheibook）了解更多

[广告]赞助链接：

四季很好，只要有你，文娱排行榜：https://www.yaopaiming.com/
让资讯触达的更精准有趣：https://www.0xu.cn/