在数据库操作层面，我们多使用二阶段提交协议（2PC）保证强一致性。在分布式系统中，多使用 Raft 算法来保证强一致性。如果考虑可用性，则使用 Gossip 协议实现最终一致性，配合 Quorum NWR 算法的三个参数来调节容错能力。而 zookeeper 基于读性能的考虑，通过 ZAB 协议提供最终一致性。

可用性

可用性表示能得到响应数据，但不保证数据最新，强调服务可用。前提条件：访问的是非故障节点。

可用性最强的就是 Gossip 协议了，即时只有一个节点，集群可以提供服务。然后是 Paxos/Raft/ZAB/Quorum NWR/FBFT/POW 算法，能够容忍部分节点故障。

而 2PC、TCC 要求所有节点都正常运行，系统才能正常工作，可用性最低。

性能

性能和可用性联系非常紧密，可用性越高，性能越强。

上面可用性的排序同样适用于性能维度。Gossip 协议可用于 AP 型分布式系统，水平扩展能力强，读写性能最强。

Paxos/Raft/ZAB/Quorum NWR/FBFT/POW 算法都是领导者模型，写性能依赖领导者，读性能依赖一致性的实现。性能处于中等位置。

而 2PC、TCC 实现事务时，需要预留和锁定资源，性能较差。

学习路线

第一讲：拜占庭将军问题

必须先把拜占庭将军问题弄懂，这篇我用三国杀卡牌游戏中的四种身份牌来讲解了拜占庭将军问题。

第二讲：CAP、BASE、ACID 理论

是针对 CAP、BASE、ACID 三大理论的讲解，文中我用太极拳中的刚和柔来比喻 ACID 和 BASE，而如何平衡刚和柔就需要 CAP 理论了。

第三讲：Paxos 算法

为了更好地理解 Paxos 算法，我用三国演义中的诸葛亮和庞统两种角色充当提议者对 Paxos 算法的细节进行了分析。

第四讲：Raft 算法

Raft 算法其实比较好理解，但是直接描述出来会让人云里雾里，所以我借助了动图，用动图模拟 Raft 算法的选举过程，轻松易懂。

第五讲：一致性哈希

这个也算作分布式算法中的一种，常用在负载均衡、路由寻址中。该算法理解起来不难，但比较枯燥，所以我用韩信点兵的故事来进行讲解，诙谐有趣。

第六讲：Gossip 协议

Gossip 的英文单词就是流言蜚语，具有传染性，所以我用一个传染性病毒的故事进行讲解，既可以学习分布式算法又可以了解病毒知识，一举两得。

第七讲：Quorum NWR

N、W、R 这三个参数，比较晦涩，为了让大家更容易理解，我用太上老君的炼丹炉比作节点，丹炉里面的药比作数据，用炼造过程来体现 NWR 这三个参数，更加形象化。

第八讲：POW 算法

在学习 POW 算法时，牵扯到区块链的知识，于是我就去看了一本区块链的书《区块链：从数字货币到信用社会》，一本科普书，对我了解区块链、比特币帮助很大。而区块链中用到的核心知识之一就是 POW 算法，也叫做工作量证明。我用紫霞仙子和至尊宝的故事对区块链、比特币、工作量证明进行了讲解，诙谐有趣。

对了，FBFT 和 ZAB 协议还没有给大家讲解，后续可能得过一段时间才能补上，因为有很多读者朋友在催更我的开源项目 PassJava，所以得去倒腾开源项目了。

一、用三国杀讲分布式算法，舒适了吧？

前言

《三国杀》是一款热门的卡牌游戏，结合中国三国时期背景，以身份为线索，以卡牌为形式，益智休闲，老少皆宜。

东汉末年，袁绍作为盟主，汇合了十八路诸侯一起攻打董卓。

在讲解之前，我们先聊下分布式协议和算法整体脉络。

现在很多开发同学对分布式的组件怎么使用都有一定经验，也知道 CAP 理论和 BASE 理论的大致含义。但认真去看分布式算法的真的很少，原因有三：

担心算法过于复杂，所以花的时间很少。
网上的资料能用大白话将分布式算法讲清楚的比较少。
学习分布式算法没有一条清晰的路线。

我会在后续的文章中用故事、大白话的方式来讲解分布式算法的原理，以及学习路线到底是怎么样的？

学习路线

学习分布式协议和算法的路线可以是先学习四大基础理论，作为地基，再学习分布式协议和算法，就像是在地基上建房子。地基打好了，才能建更稳固的高楼大厦。

八大分布式协议和算法

Paxos 算法
Raft 算法
一致性 Hash 算法
Gossip 协议算法
Quorum NWR 算法
FBFT 算法
POW 算法
ZAB 协议

因篇幅原因，本篇只涉及拜占庭将军问题。

拜占庭将军问题

大家可能听过拜占庭将军问题。它是由莱斯利·兰伯特提出的点对点通信中的基本问题，

拜占庭位于如今的土耳其的伊斯坦布尔，是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔，为了达到防御目的，每个军队都分隔很远，将军与将军之间只能靠信差传消息。在战争的时候，拜占庭军队内所有将军和副官必须达成一致的共识，决定是否有赢的机会才去攻打敌人的阵营。但是，在军队内有可能存有叛徒和敌军的间谍，这个就是拜占庭容错问题。

实际上拜占庭问题是分布式领域最复杂的一个容错模型，一旦理解它，就能掌握分布式共识问题的解决思路，还能帮助大家理解常用的共识算法，也可以帮助我们在工作中选择合适的算法，或者设计合适的算法。

为什么第一个基础理论是拜占庭将军问题？

因为它很好地抽象出了分布式系统面临的共识问题。 上面提到的 8 种分布式算法中有 5 种跟拜占庭问题相关，可以说弄懂拜占庭问题对后面学习其他算法就会容易很多。

下面我用三国杀游戏中的身份牌来讲解拜占庭将军问题。

三国杀身份牌

三国杀中主要有四种身份：主公、忠臣、反贼、内奸。每个游戏玩家都会获得一个身份牌。主公只有 1 个。忠臣最多 2 个，反贼最多 4个，内奸最多一个。

主公

获胜条件： 消灭所有反贼和内奸

技巧： 以自己生存为首要目标，分散反贼注意力。配合忠内剿灭反贼并判断谁是忠谁是内。

忠臣

获胜条件： 保护主公存活的前提下消灭所有反贼和内奸。

技巧： 忠臣是主公的屏障，威慑反贼和内奸的天平。

反贼

获胜条件： 消灭主公即可获胜。

技巧： 反贼作为数量最多的身份，需要集中火力猛攻敌人弱点。正确的思路是获胜的关键。

内奸

获胜条件： 先消灭反贼和忠臣，最后与主公单挑成为最后唯一生还者。

技巧： 正确的战术+ 冷静的头脑+ 运气。

还原拜占庭问题

东汉末年，袁绍作为盟主，汇合了十八路诸侯一起攻打董卓。把董卓定为反贼，袁绍定为主公，另外有两个忠诚和一个内奸，就选这三个风云人物：曹操，刘备，孙坚（孙权的爸比），内奸扮演的角色是忠臣，主公和两个忠臣不知道内奸的身份，都当作忠臣对待了。

![战局 3 vs 2] mark

董卓是非常强大的，拥有精良的西凉兵，麾下还有战神吕布。大家都知道三英站吕布的故事，吕布以一已之力对阵刘备、张飞、关羽三人。

要想干掉董卓，袁绍必须统一忠臣的作战计划，三位忠臣还不知道有什么其他花花肠子，有一个还是内奸。如果内奸暗通反贼董卓，给忠臣发送误导性的作战信息，该怎么办？另外假定这几个忠臣都是通过书信交流作战信息，如果书信被拦截了或书信里面的信息被替换了咋办？这些场景都可能扰乱作战计划，最后出现有的忠臣在进攻，有的忠臣撤退了。那么反贼就可以乘此机会发起进攻，逐一攻破。

袁绍本来就没有曹操的机智，那他如何让忠臣们达成共识，制定统一的作战计划呢？

上面的映射关系就是一个拜占庭将军问题的一个简化表述，袁绍现在面临的就是典型的共识问题。也就是在可能有误导信息的情况下，采用合适的通讯机制，让多个将军达成共识，制定一致性的作战计划。

一方选择撤退

刘备、曹操、孙坚通过信使传递进攻或撤退的信息，然后进行协商，到底是进攻还是撤退。遵循少数服从多数，不允许弃权。

曹操疑心比较重，侦查了反贼的地形后，决定撤退。而刘备和孙坚决定进攻。

刘备决定进攻，通过信使告诉曹操和孙坚进攻。
曹操决定撤退，通过信使告诉刘备和孙坚撤退。
孙坚决定进攻，通过信使告诉曹操和刘备进攻。

曹操收到的信息：进攻 2 票，自己的一张撤退票，票数一比，进攻票：撤退票 = 2 : 1，按照上面的少数服从多数原则进行投票表决，曹操还是会进攻。那么三方的作战方案都是进攻，所以是一个一致性的作战方案。最后战胜了董卓。

内奸登场-撤退

因为我们前期的设定，孙坚作为内奸，早已与反贼董卓私下沟通好了，不攻打董卓。

刘备决定进攻，通过信使告诉曹操和孙坚进攻。
曹操决定撤退，通过信使告诉曹操和孙坚撤退。
孙坚决定撤退，通过信使告诉曹操和刘备撤退。

刘备收到进攻和撤退各一票，而自己又选择撤退，所以刘备得到的票数是：进攻 : 撤退 = 1 : 2，遵从少数服从多数的原则，刘备选择最后选择撤退，那么三方的作战方案都是撤退，所以也是一个一致性的作战方案。

内奸使诈-一进一退

内奸看了上述计划，发现忠臣都撤退了，并没有被消灭，就想通过使诈的方式来消灭其中一个忠臣。

刘备决定进攻，通过信使告诉曹操和孙坚进攻。
曹操决定撤退，通过信使告诉曹操和孙坚撤退。
孙坚作为内奸使诈，通过信使告诉刘备进攻，告诉曹操撤退。

那么结果是什么呢？

刘备的票数为进攻 2 票，撤退 1 票，曹操的票数为进攻 1 票，撤退 2 票。按照少数服从多数的原则，刘备最后会选择进攻，而曹操会选择撤退，孙坚作为内奸肯定不会进攻，刘备单独进攻反贼董卓，势单力薄，被董卓干掉了。

从这个场景中，我们看到内奸孙坚通过发送误导信息，非常容易地就干扰了刘备和曹操的作战计划，导致两位忠臣被逐一击破。这个现象就是二忠一判难题。那么主公袁绍该怎么解决这个问题？

拜占庭问题解法

解法原理

就是讲袁绍也参与进来进行投票，这样就增加了一位忠臣的数量。三个忠臣一个叛贼。然后 4 位将军做了一个约定，如果没有收到命令，则执行默认命令，比如撤退。另外约定流程来发送作战信息和如何执行作战指令。这个解法的关键点就是执行两轮作战信息协商。

我们来看下第一轮是怎么做的。

第一步：先发送作战信息的将军我们把他称为指挥官（袁绍），另外的将军我们称作副官（刘备，曹操，孙坚）。
第二步：指挥官将他的作战信息发送给所有的副官。
第三步：每一位副官将从指挥官处收到的作战信息，作为自己的作战指令；假如没有收到指挥官的作战信息，将把默认的撤退作为作战指令。

我们用图来演示：袁绍作为主公先发送作战信息，作战指令为进攻。然后曹操、刘备、孙坚收到进攻的作战指令。

再来看下第二轮是怎么做的。

第一轮指挥官（袁绍）已经发送指令了，现在就需要刘备、曹操、孙坚依次作为指挥官给其他两位副将发送作战信息。
然后这三位副将按照少数服从多数的原则，执行收到的作战指令。

孙坚使诈 - 两撤退

如果孙坚使诈，比如给曹操和刘备都发送撤退信息，如下图所示。那么刘备和曹操收到的作战信息为进攻 2票，撤退 1 票，按照少数服从多数的原则，最后刘备和曹操执行进攻，实现了作战计划的一致性，曹操和刘备联合作战击败了反贼董卓（即使孙坚没有参加作战。）

孙坚使诈 - 一进一退

假如孙坚使诈，给曹操发送撤退指令，给刘备发送进攻指令，那么刘备收到的作战信息是进攻 3票，肯定会发起进攻了，而曹操收到的作战信息是进攻 2 票，撤退 1 票，最后曹操还是会进攻，所以刘备和曹操还是联合作战击败了反贼董卓。

如此看来，引入了一位指挥官后，确实可以避免孙坚使诈，但如果是孙坚在第一轮作为指挥官，其他人作为副官呢？

孙坚作为指挥官

第一轮孙坚向其中一个副官袁绍发送撤退指令，向另外两个副官曹操、刘备发送进攻指令。那么第一轮的结果如下图：

第二轮孙坚休息，其他副官按照孙坚发送的指令开始向另外的副官发送指令。

曹操向刘备和袁绍发送进攻指令。
刘备向曹操和袁绍发送进攻指令。
袁绍向曹操和刘备发送撤退指令。

如下图所示，最后曹操、刘备、袁绍收到的指令为进攻 2 票，撤退 1 票，按照少数服从多数原则，三个人都是发起进攻。执行了一致的作战计划，保证作战的胜利。

小结

通过上面的演示，我们知道了如何解决拜占庭将军问题。其实兰伯特在他的论文中也提到过如何解决。

如果叛将人数为 m，将军数 n >= 3m + 1，那么就可以解决拜占庭将军问题。
前提条件：叛将数 m 一致，需要进行 m + 1 轮的作战协商。

这个公式，大家只需要记住就可以了，推到过程可以参考论文。

比如上述的攻打董卓问题，曹操、刘备、孙坚三个人当中，孙坚是叛将，它可以使诈，使作战计划不统一。必须增加一位忠臣袁绍来协商共识，才能达成一致性作战计划。

拜占庭解法二-签名

那可以在不增加忠臣的情况下，解决拜占庭的二忠一判问题呢？

解法二就是通过签名消息。比如将军之间通过印章、虎符等信物进行通信。来保证这几个特征：

签名无法伪造，对签名消息的内容进行任何更改都会被发现。
任何人都能验证将军签名的真伪。

限于篇幅原因，签名的演示这里就不做展开了，感兴趣的@我，后续会加上。

总结

通过三国杀角色来讲解分布式中共识场景。那他们和分布式系统的映射关系是怎么样的呢？

将军对应计算机节点。
忠臣的将军对应正常运行的计算机节点。
叛变的将军对应出现故障并会发送误导信息的计算机节点。
信使被杀对应通讯故障、信息丢失。
信使被间谍替换对应为通讯被恶意攻击、伪造信息或劫持通讯。

可不要小瞧拜占庭问题，它可是分布式场景最复杂的的故障场景。比如在数字货币的区块链技术中就有用到这些知识点。而且必须使用拜占庭容错算法（也就是 Byzantine Fault Tolerance，BFT）。

拜占庭容错算法还有 FBFT 算法，PoW 算法，当然不会在这篇中去讲这些算法，后续再讲解。一口吃不了大胖子~

有了拜占庭容错算法，肯定有非拜占庭容错算法，顾名思义，就是没有发送误导信息的节点。CFT 算法就是解决分布式系统中存在故障，但不存在恶意节点的场景下的共识问题。简单来说就是可能因系统故障造成丢失消息或消息重复，但不存在错误消息、伪造消息。对应的算法有 Paxos 算法、Raft 算法、ZAB 协议。后续讲解~

上面提到了 5 种算法，居然都是跟拜占庭问题有关，你说今天讲的拜占庭问题重要不重要？

这么多算法该如何选择？

节点可信，选非拜占庭容错算法。否则就用拜占庭容错算法，如区块链中用到的 PoW 算法。

二、用太极拳讲分布式理论，真舒服！

背景：倚天屠龙记中赵敏郡主携带一帮高手围攻武当，武当派掌门张三丰被暗算，传了一套武功给张无忌用来对付赵敏的手下。这套武功就是太极拳。

张三丰：无忌，你可记得多少招式？
张无忌：我全忘了！
张三丰：很好，你只要记住把玄冥二老打趴下就可以了。

上篇用三国杀讲分布式中的拜占庭将军问题，还挺有意思的，这次我们用倚天屠龙记中的太极拳来聊下剩下的三大理论：

CAP 理论
ACID 理论
BASE 理论

太极拳的精髓：以柔克刚，刚柔并进，四两拨千斤，无招胜有招。

我把 CAP 理论称作太极，ACID 理论称为阳或刚，BASE 理论称为阴或柔。ACID 理论追求一致性，BASE 理论本来就叫做柔性事务，追求的是可用性。那张无忌为什么会全忘了还打败了玄冥二老呢？因为太极拳的精髓是拳意，无招胜有招。

一、太极的两面

CAP 理论是对分布式系统的特性做了一个高度的抽象，变成了三大指标：

一致性（Consistency）
可用性（Availability）
分区容错性（Partition Tolerance）

分布式中的一致性，我们可以理解为客户端的每次读操作，不管访问的是哪个几点，要么督导的都是同一份最新写入的数据，要么读取失败。这就很刚了，不能说这种刚不好，在很多场景中，也确实需要保证高度的一致性。

为了帮助大家理解一致性，我举个倚天屠龙记的故事：六大派围攻光明顶。
在这里插入图片描述
峨眉派灭绝师太作为统领，带领江湖六大派围攻光明顶，最开始的进攻策略是从北边进攻。灭绝师太发现从北边进攻不妙，于是飞鸽传书给武当派和少林派从南边进攻的命令，但是少林派的飞鸽被明教轻功绝顶的青翼蝠王韦一笑截获了，最后的结果是少林派从北边进攻，武当派从南边进攻，这不就乱套了吗？如下图所示：

1.1 理解分布式中的 CAP

CAP 放到分布式系统中该如何理解呢？下面举个例子帮助大家理解。

初始环境：客户端查询或更新节点 1 和节点 2，两个节点存的值 A = 1。

客户端更新节点 1 中 A 的值，设置 A = 5。

节点 1 将 A 的值更新为 5 后，返回更新成功给客户端。
节点 1 返回更新成功
客户端访问到了节点 2 ，请求获取 A 的值，结果返回 A = 1。这和节点 1 中存储的 A 的值就不一致了。

那么怎么保证两个节点中的值都是 A = 5 呢？客户端将节点 1 更新后，节点 2 也需要更新，才能告诉客户端更新成功了。

两个节点都更新成功后，客户端访问其中任意一个节点获取到的都是 A = 5。这个就叫做一致性。

一致性强调的是数据正确，每次读取节点中的数据都是最新写入的数据。这个我称作刚。

但是我们生产的集群环境下如果发生分区故障时（节点失联，节点无法响应，节点无法写入数据），客户端查询节点时，我们不能返回错误信息给客户端。比如说业务集群中的一些关键系统，如注册中心，不能因为某个节点失联了，就不响应最新的数据。那么相关的业务也获取不到正确的注册信息而导致系统瘫痪。

可用性就派上用场了，牺牲数据准确性，每个节点使用本地数据来响应客户端的请求。另外当节点不可用时，可以使用快速失败策略，至少不能让服务长时间不能响应可用性强调的是服务可用，不保证数据正确。这个我称作柔。

如下图所示：节点 1 和节点 2 返回给客户端的值分别是 A = 5 和 A = 1，也就是节点 1 和节点 2 并没有保证数据一致性，而是考虑了节点的可用性。
mark

分区容错性的含义就是节点间出现任意数量的消息丢失或高延迟的时候，系统仍然在继续工作。分布式系统告诉客户端，我的内部不论出现什么样的数据同步问题，我会一直运行。强调的是集群堆分区故障的容错能力。

1.2 CAP 三角

那么这三个指标又有什么关系呢？这个就是我们经常听到的 CAP 理论。C 代表一致性（Consistency），A 代表可用性（Availability）、P 代表分区容错性（Partition Tolerance）。

对于分布式系统，CAP 三个指标只能选择其中两个。

CA：保证一致性和可用性。当分布式系统正常运行时（大部分时候所处的状态），这个时候不需要 P，那么 C 和 A 能够同时保证。只有在发生分区故障时，才需要 P，这个时候就只能在 C 和 A 之间做出选择。典型应用：单机版部署的 MySQL。
CP：保证数据的一致性和分区容错性，比如配置信息，必须保证每个节点存的都是最新的，正确的数据。比如 Raft 的强一致性系统，会导致无法执行读操作和写操作。典型应用：Etcd、Consul、Hbase。
AP：保证分布式系统的可用性和分区容错性。用户访问系统，都能得到相应数据，不会出现响应错误，但是可能会读到旧的数据。典型应用：Cassandra 和 DynamoDB。

二、太极的刚

2.1 ACID 的刚

最开始知道 ACID 是研究 SQL 数据库的时候，原子性（Atomicity）、一致性（Consistency）、隔离性（Isolation）、持久性（Durability）。

这四个属性是针对事务而言的，而事务就是为单个工作单元而执行的一系列操作。如查询、修改数据、修改数据定义。

事务不仅仅只用在数据库上，还可以用在业务系统中，比如发券后扣减库存，这种业务场景可以定义为一个事务。单机场景我们可以通过加锁、时间序列等机制来保证单个节点上的 ACID 特性，但无法保证节点间操作的 ACID 特性。

那么分布式系统下该如何解决事务问题呢？这也是面试中经常遇到的题。分布式事务协议大家一定听过，比如二阶段提交协议和 TCC 协议，下面我还是用六大派围攻光明顶故事来讲解二阶段协议。

2.2 围攻光明顶

峨眉派想汇集少林派、武当派、昆仑派明天一起进攻光明顶。如果有一方不同意进攻，或者进攻时机不一致，则需要取消整个行动计划。少林派、武当派、昆仑派进攻光明顶这一组行动可以看成是一个分布式事务，要么全部执行、要么全部不执行。如下图所示：

那如何帮助灭绝师太解决这个协同问题？我们可以用二阶段提交协议来说明。

2.3 二阶段提交协议

在二阶段提交协议中，灭绝师太先给少林派发送进攻的消息，少林派作为协调者的身份，由少林派联系武当派和昆仑派是进攻还是撤退。

二阶段就是说有两个阶段，1.提交请求阶段（投票阶段），2.提交执行阶段（完成阶段）。

阶段一：提交请求阶段：

第一步：少林派作为协调者分别给武当派和昆仑派发送消息：“明天进攻光明顶，可行？”
第二步：少林派、武当派、昆仑派分别评估明天是否能进攻光明顶，如果能，就预留时间并锁定，不再安排其他的进攻事项。
第三步：少林派得到全部的回复结果，包括少林派自己的评估结果。最后三方的结果都是可行。

如下图所示：

阶段二：提交执行阶段：

第一步：少林派统计自己、昆仑派和武当派的消息，都是可以进攻，所以可以执行分布式事务，进攻光明顶。
第二步：少林派通知昆仑派和武当派进攻光明顶。
第三步：少林派、昆仑派、武当派召集手下弟子，进攻光明顶（执行事务）。
第四步：昆仑派、武当派将是否已发起进攻告诉少林派。
第五步：少林派汇总自己、昆仑派、武当派的进攻结果给灭绝师太。这样灭绝师太看到的就是统一的作战计划。

注意：

可以将灭绝师太当做客户端。少林派、武当派、昆仑派当做分布式系统的三个节点。少林派作为协调者。
将评估是否能进攻光明顶以及预留时间可以理解为需要操作的对象和对象状态，是否已经准备好了，能否提交新的操作。
发送消息、飞鸽传书可以理解为网络消息。
第一个阶段中，每个参与者投票表决事务是放弃还是提交，一旦投票要求提交事务，那么就不允许放弃事务。
第二个阶段中，每个参与者执行最终统一的决定，提交事务或者放弃事务。这个就是 ACID 的原子性。
第一个阶段中，需要预留资源，预留期间，其他人不能操作这个资源。

2.4 二阶段协议带来的问题

ACID 特性是 CAP 中一致性的边界，可以称作最强的一致性，如果分布式系统中实现了一致性，必然会影响到可用性。如果一个节点失败，这个分布式事务的执行都是失败的。

绝大数场景中，对一致性要求没那么高，并不需要保证强一致性，短暂的不一致也能接收，最后能保证数据是正确的就OK。也就是说我们可以用最终一致性方案来保证数据的一致性。

另外要提到的就是 TCC 协议（三阶段提交协议），他是针对二阶段提交中的：协调者故障，参与者长期锁定资源的痛点而出的协议。引入了询问阶段和超时机制，减少资源被长时间锁定。但是需要更多的消息进行协商，增加了系统负载和响应延迟，所以三阶段提交协议很少被使用。

三、太极的柔

3.1 BASE 的柔

讲了太极的刚，下面来讲太极的柔。谈到分布式事务的柔，一定会提到 BASE 理论，俗称柔性事务。BASE 理论是 CAP 理论中 AP 的扩展。大部分互联网分布式系统都强调可用性，都会考虑引入 BASE 支持。这个理论非常非常重要，我要告诉你的是，掌握了这个理论，设计出符合自己业务的分布式架构也会变得容易很多，而不是摸不着头脑。

BASE 的核心：基本可用 BA（Basically Available）、软状态 S（Soft state）、最终一致性 E（Eventually consistent）。

那为什么叫它柔性事务？其实它和 ACID 是相对的，不需要保证强一致性，比如一根橡皮筋被拉弯了，你放开橡皮筋后，它就会自行恢复，这个就是橡皮筋柔性的一面。

3.2 BASE 和太极拳有什么关系

太极拳每一招都不是直直的打出去的，每一招都讲求圆滑、画弧线，看起来软绵绵的，其实是柔中带刚。每一招的最后一下都是非常刚硬的抖动一下（这效果我用文字实在描述不出来，大家去看电视吧）。这最后一下就可以看成是刚的一面，也就是最终一致性。
太极拳

3.3 基本可用

怎么理解基本可用？重点是在这个基本，这个理论并没有告诉我们怎么定义基本，这是一个模糊的概念。其实就是要柔到什么程度。

在分布式系统中，我们可以把基本可用理解为保证核心功能可用，允许损失部分功能的可用性。基本可用可以用四种方案来实现。

流量削峰：比如多个秒杀场次，某东的 8 点秒杀场，12 点的秒杀场。
延迟响应：比如双 11 期间某商城创建的订单，会提示客户订单正在创建中，可能需要等个十几秒。
体验降级：比如某次比赛活动，有大量用户进活动页查看图片，这个时候，大量图片因为网络超时而无法显示，这个时候就可以考虑替换原有图片，返回清晰度没有那么高或图片比较小的图片。
过载保护：比如我们常用的消息队列占满了，可以考虑丢弃后来的请求，或清除队列中的一些请求，保护系统不过载，但这都需要结合自身的业务场景来设计。

3.4 最终一致性

最终一致性：系统中的所有的数据副本在经过一段时间的同步后，最终能够达到一个一致的状态。最终可以理解为一个短暂的延迟。

最终一致性在非常多的互联网业务中采用。但是跟钱打交道或金融系统会采用强一致性或事务。

前面提到了 ACID 的强一致性，而最终一致性和它是什么关系？

强一致性其实也是最终一致性的一种。那最终一致性怎么理解？强一致性可以看作不存在延迟的一致性。如果无法容忍延迟就用强一致性，否则就用最终一致性。

3.5 最终一致性和太极拳有什么关系

太极拳最神奇的一个地方就是卸力，当对方使出全力攻击你的时候，用太极的招式将对方使出的力量卸下来，使对方的攻击无效。卸力可以和我们之前讲到的流量削峰对应。另外卸完力之后，就是我们发动攻击的时候。

四、无招胜有招

回到文章的开头，张三丰教给张无忌的太极拳，张无忌全忘了，还怎么能打败玄冥二老的呢？

因为太极拳重视的是拳意，而不是招式。所以张无忌领会了拳意，无招胜有招。

我们设计分布式系统的时候，也不要死记硬背三大理论，要真正懂得原理，然后才能一点一点迭代出最适合当前业务系统的分布式架构。

五、总结

太极拳分为阴和阳两方面，就如 CAP 中的 C 和 A。
CAP 理论是分布式中基础理论，有三个重要指标：一致性、可用性、分区容错性。
ACID 是传统数据库的设计理念，追求强一致性。四个指标：原子性、一致性、隔离性、持久性。是 CAP 中 CP 的延伸。
BASE 理论是 CAP 中一致性和可用性权衡的结果。是 CAP 中的 AP 的延伸。注重可用性和性能优先，根据业务的场景特点，实现弹性的基本可用，然后实现数据的最终一致性。
BASE 理论在很大程度上，解决了事务性系统在性能、容错、可用性等方面的通电。
BASE 理论在 NoSQL 中应用广泛，是 NoSQL 系统设计的事实上的理论支撑。

文中也通过六大派围攻光明顶的案例给大家讲解了二阶段提交的核心原理，相信大家一定能看懂。本篇文章构思 2 周，终于出炉了，不要脸地求个再看和转发~

三、诸葛亮 VS 庞统，拿下 Paxos 共识算法

前言

分布式确实是一个有趣的话题，只要你留心观察，分布式在生活中无处不在。

悟空哥最开始学习分布式是从一篇非常用心写的技术征文开始的，而且这篇文章获得了征文第一名，在此感谢掘金社区提供的平台。想学习的同学可以点这个文章链接：《这三年被分布式坑惨了，曝光十大坑》

前两讲主要是讲解分布式理论，涉及到了分布式的四大理论。

拜占庭将军问题：《用三国杀讲分布式算法，舒适了吧？》

BASE、CAP、ACID：《用太极拳讲分布式理论，舒服！》

从这篇开始，将会讲解分布式的八大协议/算法。本篇主要讲解 Paxos 共识算法。

本文主要内容如下：

Paxos 算法

Paxos 是分布式算法中的老大哥，可以说 Paxos 是分布式共识的代名词。最常用的分布式共识算法都是基于它改进。比如 Raft 算法（后面也会介绍）。所以学习分布式算法必须先学习 Paxos 算法。

Paxos 算法主要包含两个部分：

Basic Paxos 算法：多个节点之间如何就某个值达成共识。（这个值我们称作提案 Value）
Multi-Paxos 算法：执行多个 Basic Paxos 实例，就一系列值达成共识。

Basic Paxos 算法是 Multi-Paxos 思想的核心，Multi 的意思就是多次，也就是说多执行几次 Basic Paxos 算法。所以 Basic Paxos 算法是重中之重。

三国中的 Paxos

三国中刘备集团，有两大军师：诸葛亮和庞统，都是非常厉害的人物，当他们有不同作战计划给多名武将时，如何达成一致？

角色

Paxos 中有三种角色：提议者、接受者、学习者。

让我们用更通俗的方式来讲解 Paxos 算法。让我们穿越回东汉末年，刘备集团的帐营中一同学习 Paxos 算法是怎么攻打曹操的。

刘备的帐营中人物介绍：

主公一名：刘备，作为请求方或客户端。
军师两名：诸葛亮、庞统，作为提议者。
武将三名：关羽、张飞、赵云，作为接受者。
文臣两名：法正、马良，作为学习者。

提议者（Proposer）

提议一个值，用于投票表决。
接入和协调，收到客户端的请求后，可以发起二阶段提交，进行共识协商。
映射到上面的故事中，军师就是用来部署作战计划的。

接受者（Acceptor）

对每个提议的值进行投票，并存储接受的值。
投票协商和存储数据，对提议的值进行投票，并接受达成共识的值，存储保存。
映射到上面的故事中，武将就是用来接受军师的作战计划。
其实，集群中所有的节点都在扮演接受者的角色，参与共识协商，并接受和存储数据。

学习者（Learner）

被告知投票的结果，接受达成共识的值，存储数据，
不参与投票的过程，即不参与共识协商。
映射到上面的故事中，就是两名文臣作为记录作战方案的备胎。

接受者 or 提议者

为什么说节点可以扮演接受者，也可以扮演提议者呢？

上篇我在讲解 BASE 协议的时候，讲到二阶段提交协议。其中有一个协调者的身份，协调者既可以是接受者，也可以是提议者。

作为接受者，接收客户端的消息。比如诸葛亮需要接收刘备的作战要求。
作为提议者，发起二阶段提交。然后这个节点和另外其他节点作为接受者进行共识协商。比如诸葛亮要汇总最终的作战计划给刘备。

如下图所示，节点 1 作为提议者和接受者，节点 2 和节点 3 作为接受者。

诸葛亮 VS 庞统

三国中有刘备集团（占据西蜀）、曹操集团（占据北边）、孙权集团（占据江南）。

诸葛亮和庞统作为提议者，向三个接受者进作战计划的提案。提案中有两个属性：

提案编号，每次军师进行提案，都会有个编号，这里用 n 表示。
提议值，也就是作战计划，这里用 v 表示。所以提案就是 [n, v]。

诸葛亮的作战计划是从北边进攻曹操，庞统的作战计划是从南边进攻曹操，而关羽、张飞、赵云先后收到了他们的作战计划，该听谁的呢？这里就是一个共识的问题。而 Paxos 算法达成共识分两个阶段。准备（Prepare）阶段和接受（Accept）阶段。

准备阶段

诸葛亮和庞统作为提议者，分别向所有的接受者（关羽、张飞、赵云）发送包含作战计划编号（提案编号）的准备请求，但不包含作战计划（提案值）。

发送准备请求

提议者诸葛亮先发送编号为 1 的作战计划的准备请求，庞统发送编号为 2 的作战计划的准备请求。
接受者关羽（节点 X）在8 点收到来自诸葛亮发送的作战计划准备请求，在10 点 收到来自庞统发送的作战计划准备请求。
接受者张飞（节点 Y）在9 点收到来自诸葛亮发送的作战计划准备请求，在 11 点 收到来自庞统发送的作战计划准备请求。
接受者赵云（节点 Z）在 12 点 收到来自庞统发送的作战计划准备请求，在13 点收到来自诸葛亮发送的作战计划准备请求。

注意：准备阶段不需要携带具体的作战计划，所以作战计划可以为空，但是提议编号必须有。

收到准备请求（第一次）

按照接受请求的时间顺序，关羽和张飞收到诸葛亮的请求 [1，空]，赵云收到庞统的请求 [2，空]。

因为关羽、张飞之前没有收到提案，所以返回一个尚无提案的响应。也就是告诉诸葛亮，不会再响应编号小于等于 1 的准备请求了，也不会通过编号小于 1 的提案。响应的时间点是 14 点和 15 点。

而赵云之前也没有收到提案，所以返回一个尚无提案的响应。也就是告诉庞统，不会再响应编号小于等于 2 的准备请求了，也不会通过编号小于 2 的提案。响应的时间点是 16 点。

收到准备请求（第二次）

而对于庞统的准备请求，关羽、张飞收到编号为 2 的准备请求，而编号 2 大于之前接受到的编号 1 ，而且关羽和张飞没有通过任何提案，所以还是会返回给庞统一个尚无提案 的响应。也就是告诉庞统不会再响应编号小于等于 2 的准备请求了，也不会通过编号小于 2 的提案。响应的时间点是 14 点和 15 点。

而赵云最后收到诸葛亮编号为 1 的准备请求后，因编号 1小于之前响应的准备请求的提案编号 2，所以直接丢弃该准备请求，不做响应，如上图的 ❌ 图示。

接受阶段

发送接受请求

诸葛亮和庞统收到准备响应后，会分别发送接受请求，如下图所示：

诸葛亮收到大多数接受者（关羽和张飞）的准备响应后，根据响应中提案编号最大的提案的值，设置接受请求中的值。因为关羽和张飞返回的准备响应都是尚无提案，所以还是发送提案编号为 1，提案值为北的接受请求，北代表从北边进攻曹操。发送的时间点是 15 点过 1 分、16 点。

为什么是 15 点过 1 分？ 因为只要满足大多数接受者的准备请求后，就可以发送接受请求了。关羽和张飞响应的时间点是 14 点和 15 点，所以 15 点以后就可以发送了。

而庞统收到大多数接受者（关羽、张飞和赵云）的准备响应后，根据响应中提案编号最大的提案的值，，设置接受请求中的值。因为关羽、张飞和赵云返回的准备响应都是尚无提案，所以还是发送提案编号为 2，提案值为南的接受请求，南代表从南边进攻曹操。发送的时间点是 18 点、19 点、20 点。

收到接受请求

当关羽、张飞、赵云收到诸葛亮和庞统的接受请求后，会进行如下处理，如下图所示：

关羽、张飞、赵云收到诸葛亮发送的提案 [1，北]时候，因为提案编号 1小于他们承诺的能通过的提案的最小提案编号 2，所以诸葛亮的提案被拒绝了。

而当他们收到庞统的发送的提案 [2，南] 的时候，因为编号 2 不小于之前承诺的编号 2，所以通过庞统的提案 [2，南] ，所以关羽、张飞、赵云他们的作战计划是从南边进攻曹操。达成了共识。

学习者登场

当接受者通过了一个提案时，就通知所有的学习者。当学习者发现大多数的接受者都通过了某个提案，那么学习者也会通过该提案，接受该提案的值。

也就是说关羽、张飞、赵云达成了共识后，学习者法正和马良也同样通过从南边进攻的作战计划。

总结

Basic Paxos 也是通过二阶段提交协议达成共识。准备阶段、接受阶段。不知道二阶段提交协议的，可以看我前面的文章。《用太极拳讲分布式理论，舒服！》
Basic Paxos 不仅仅实现了共识，还实现了容错。有少于一半的节点出现故障时，集群也能正常工作。文中也多次强调了大多数节点都同意的原则，而这个原则赋予了 Basic Paxos 容错的能力。
提案编号代表优先级，保证了三个承诺：
- 如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求。
- 如果接受请求中的提案的提案编号，小于接受者已经响应的准备请求的提案，那么接受者将承诺不通过这个提案。
- 如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息。

加分题

如果关羽和张飞已经通过了提案 [2，南]，而赵云还未通过任何提案，当第三名军师简雍提出一个提案，编号为 8，作战计划为从东边进攻曹操，也就是 [8, 东]的作战计划，那么最终关羽、张飞、赵云的作战计划是怎么样的？欢迎评论区留言。

四、动图讲解分布式 Raft

一、Raft 概述

Raft 算法是分布式系统开发首选的共识算法。比如现在流行 Etcd、Consul。

如果掌握了这个算法，就可以较容易地处理绝大部分场景的容错和一致性需求。比如分布式配置系统、分布式 NoSQL 存储等等，轻松突破系统的单机限制。

Raft 算法是通过一切以领导者为准的方式，实现一系列值的共识和各节点日志的一致。

二、Raft 角色

2.1 角色

跟随者（Follower）：普通群众，默默接收和来自领导者的消息，当领导者心跳信息超时的时候，就主动站出来，推荐自己当候选人。

候选人（Candidate）：候选人将向其他节点请求投票 RPC 消息，通知其他节点来投票，如果赢得了大多数投票选票，就晋升当领导者。

领导者（Leader）：霸道总裁，一切以我为准。处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们不要”发起新的选举，不用找新领导来替代我。

如下图所示，分别用三种图代表跟随者、候选人和领导者。

三、单节点系统

3.1 数据库服务器

现在我们想象一下，有一个单节点系统，这个节点作为数据库服务器，且存储了一个值为 X。

3.2 客户端

左边绿色的实心圈就是客户端，右边的蓝色实心圈就是节点 a（Node a）。Term 代表任期，后面会讲到。

3.3 客户端向服务器发送数据

客户端向单节点服务器发送了一条更新操作，设置数据库中存的值为 8。单机环境下（单个服务器节点），客户端从服务器拿到的值也是 8。一致性非常容易保证。

3.4 多节点如何保证一致性？

但如果有多个服务器节点，怎么保证一致性呢？比如有三个节点：a，b，c。如下图所示。这三个节点组成一个数据库集群。客户端对这三个节点进行更新操作，如何保证三个节点中存的值一致？这个就是分布式一致性问题。Raft 算法就是来解决这个问题的。当然还有其他协议也可以保证，本篇只针对 Raft 算法。

在多节点集群中，在节点故障、分区错误等异常情况下，Raft 算法如何保证在同一个时间，集群中只有一个领导者呢？下面就开始讲解 Raft 算法选举领导者的过程。

四、选举领导过程

4.1 初始状态

初始状态下，集群中所有节点都是跟随者的状态。

如下图所示，有三个节点(Node) a、b、c，任期（Term）都为 0。

4.2 成为候选者

Raft 算法实现了随机超时时间的特性，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。比如 A 节点等待超时的时间间隔 150 ms，B 节点 200 ms，C 节点 300 ms。那么 a 先超时，最先因为没有等到领导者的心跳信息，发生超时。如下图所示，三个节点的超时计时器开始运行。

当 A 节点的超时时间到了后，A 节点成为候选者，并增加自己的任期编号，Term 值从 0 更新为 1，并给自己投了一票。

Node A：Term = 1, Vote Count = 1。
Node B：Term = 0。
Node C：Term = 0。

4.3 投票

我们来看下候选者如何成为领导者的。

第一步：节点 A 成为候选者后，向其他节点发送请求投票 RPC 信息，请它们选举自己为领导者。
第二步：节点 B 和节点 C 接收到节点 A 发送的请求投票信息后，在编号为 1 的这届任期内，还没有进行过投票，就把选票投给节点 A，并增加自己的任期编号。
第三步：节点 A 收到 3 次投票，得到了大多数节点的投票，从候选者成为本届任期内的新的领导者。
第四步：节点 A 作为领导者，固定的时间间隔给节点 B 和节点 C 发送心跳信息，告诉节点 B 和 C，我是领导者，组织其他跟随者发起新的选举。
第五步：节点 B 和节点 C 发送响应信息给节点 A，告诉节点 A 我是正常的。

4.4 任期

英文单词是 term，领导者是有任期的。

自动增加：跟随者在等待领导者心跳信息超时后，推荐自己为候选人，会增加自己的任期号，如上图所示，节点 A 任期为 0，推举自己为候选人时，任期编号增加为 1。
更新为较大值：当节点发现自己的任期编号比其他节点小时，会更新到较大的编号值。比如节点 A 的任期为 1，请求投票，投票消息中包含了节点 A 的任期编号，且编号为 1，节点 B 收到消息后，会将自己的任期编号更新为 1。
恢复为跟随者：如果一个候选人或者领导者，发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。这种场景出现在分区错误恢复后，任期为 3 的领导者受到任期编号为 4 的心跳消息，那么前者将立即恢复成跟随者状态。
拒绝消息：如果一个节点接收到较小的任期编号值的请求，那么它会直接拒绝这个请求，比如任期编号为 6 的节点 A，收到任期编号为 5 的节点 B 的请求投票 RPC 消息，那么节点 A 会拒绝这个消息。

4.5 选举规则

一个任期内，领导者一直都会领导者，直到自身出现问题（如宕机），或者网络问题（延迟），其他节点发起一轮新的选举。
在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，投完了就没了。

4.6 大多数

假设一个集群由 N 个节点组成，那么大多数就是至少 N/2+1。例如： 3 个节点的集群，大多数就是 2。

4.7 心跳超时

为了防止多个节点同时发起投票，会给每个节点分配一个随机的选举超时时间。这个时间内，节点不能成为候选者，只能等到超时。比如上述例子，节点 A 先超时，先成为了候选者。这种巧妙的设计，在大多数情况下只有一个服务器节点先发起选举，而不是同时发起选举，减少了因选票瓜分导致选举失败的情况。

五、领导者故障

如果领导者节点出现故障，则会触发新的一轮选举。如下图所示，领导者节点 B 发生故障，节点 A 和节点 B 就会重新选举 Leader。

第一步：节点 A 发生故障，节点 B 和节点 C 没有收到领导者节点 A 的心跳信息，等待超时。
第二步：节点 C 先发生超时，节点 C 成为候选人。
第三步：节点 C 向节点 A 和节点 B 发起请求投票信息。
第四步：节点 C 响应投票，将票投给了 C，而节点 A 因为发生故障了，无法响应 C 的投票请求。
第五步：节点 C 收到两票（大多数票数），成为领导者。
第六步：节点 C 向节点 A 和 B 发送心跳信息，节点 A 响应心跳信息，节点 A 不响应心跳信息。

总结

Raft 算法通过以下几种方式来进行领导选举，保证了一个任期只有一位领导，极大减少了选举失败的情况。

任期
领导者心跳信息
随机选举超时时间
先来先服务的投票原则
大多数选票原则

本篇通过动图的方式来讲解 Raft 算法如何选举领导者，更容易理解和消化。

五、韩信大招，一致性哈希

这是悟空的第 78 篇原创文章。

本文已收录Github：https://github.com/Jackson0714/PassJava-Learningopen in new window

韩信点兵的成语来源淮安民间传说。常与多多益善搭配。寓意越多越好。我们来看下主公刘邦和韩信大将军的对话。

刘邦：“你觉得我可以带兵多少？”
韩信：“最多十万。”
刘邦不解的问：“那你呢？”
韩信自豪地说：“越多越好，多多益善嘛！

假如刘邦现在给了韩信 1000 个士兵，需要大致均匀分成三组。士兵的编号是 6 位数，从 1-100000 随机分配。比如第一个士兵的值是 245，第二个士兵的编号是82593，其他士兵类似。那么如何对士兵进行分配呢？

刘邦：韩将军，你看这些士兵怎么分配好呢？
韩信：这还不简单，我的一技能就能搞定。

一技能：哈希算法

分组

韩信的一技能哈希算法：将士兵的编号 num 值当做一个 hash 值，再和总做组数 N 做取余操作，得出的结果在 0 到 N - 1 之间，这个士兵就属于那个组。

如下图所示，每来一个士兵都有一个六位的 hash 值（也可以称作编号），然后被韩信用除以 3 取余数的方式分配到三个组。比如第一组中的编号为 123456 的士兵，除以 3 之后，整除，余数为 0，所以分配到第一组。

查找士兵

现在已经分好组了，假如想找到编号为 666666 的士兵该怎么找？首先将 666666 除以 3，得到余数 0，说明在第一个组，然后去第一个组里面找就可以了。

这里有小伙伴可能会问，为什么不是把所有士兵放到一个组？

因为一个组太大了，影响行军速度。映射到互联网架构中，就是通过增加节点从而减小单节点的负载压力。

哈希分组弊端

刘邦看了这个一技能后，大呼：

韩将军真是厉害。
哈希算法看起来很完美，那我再给你五百士兵，需要分成四个组怎么办？

这时，韩信的副将说话了：

这还不简单，再用 4 取余不就好了吗？

刘邦摸着下巴思索片刻后，对副将说：

这个方案可行，但很多士兵都被重新分组了，刚刚建立的团队友情就被分解了。

我们来看下刘邦为什么觉得方案不可行。

比如原来分配到一组的编号为 3 的士兵，当分成四组的时候，通过公式计算：3%4=3，所以会分配到到第四组。

依次类推，会发现很多士兵进行了重新分配，只有小部分不会变换分组，比如 1，2，12 等等。

韩信对着刘邦点点头，对着主公说道：

主公，您说得没错，这就是我的一技能的弱点所在。
不过我还有一个技能：一致性哈希。

二技能：一致性哈希

哈希环

一致性哈希算法也用了取模运算，但是它与哈希算法不同的地方：

哈希算法：对节点的数量进行取模运算。
一致性哈希算法：对 2^32 进行取模运算。

可以想象一下，一致性哈希算法，是将整个哈希值空间组成了一个虚拟的圆环，也就是哈希环。

如下图，把 3 个组映射到固定大小为 2^32 的哈希环中。三个组一共将整个环分成了三个区域，C-A（第一组）、A-B（第二组）、B-C（第三组）。如下图所示：

第一组负责存储落在 C-A 区间内的数据。
第二组负责存储落在 A-B 区间内的数据。
第三组负责存储落在 B-C 区间内的数据。

士兵分配

假定编号为 9527 的士兵，进行哈希运算后，落到 C-A 区域。如下图所示：

第二步，让这个士兵顺时针往前走，遇到的第一个节点 A 就是他所在的组了。如下图所示:

增加分组

目前三个节点的时候，假定编号为 89757 的士兵经过哈希运算后，分配到了 B-C 区域（第三组），也就是属于 C 节点管控。如下图所示：

回到刘邦刚问的问题，如果分组变成四组，该怎么进行士兵分配。

如下图所示，增加一个节点 D，原来的区域 B-C 变成了区域 B-D（第三组）和 D-C（第四组）。

那么这名士兵属于哪个节点管控呢？如下图所示，士兵顺时针往前走，先走到了 D 节点，所以属于 D 节点管控。虽然还是属于第三组，但是这名士兵的领导者已经变了：由 C 变成了 D。

从上面的变化来看，只有 B-C 区域中的部分数据会进行迁移：B-D 之间的数据会由 C 节点迁移到 D 节点。

而其他数据不受影响，也不用进行迁移。而且节点越多，需要迁移的数据就越少。这就是多多益善了~

刘邦看了后，大赞韩信：

不亏是大将军，萧何当时月下追你，值了！

哈希环缺陷

萧何看了韩信画的哈希环后，觉得有些不对劲，思索片刻后，对韩信说：

将军，你这个哈希环上的节点分布不太均匀啊，你看第三组和第四组的的区域好小啊。

萧何说得没错，确实存在这个问题，放到互联网架构中，就存在如下问题：

节点分布不均匀，导致业务对节点的访问冷热不均。

韩信眼中充满着赞赏，知我者莫若萧何。然后胸有成竹地说道：

你说得没错，不过我还有一个技能，虚拟节点映射。

三技能：虚拟节点

一般虚拟节点比物理节点要多，并相对均匀地分布在哈希环上。如下图所示，12 个虚拟节点 N1~N12，相对均匀地分布在虚拟节点上。如果有士兵属于 N2/N3/N4 中的某一个，都会重新映射到 A 节点，依次类推，N5/N6/N7 属于 B 节点的虚拟节点映射。

我们来看下萧何的提出的问题，真实的 B-D 区域比较小，用虚拟节点后，N5/N6/N7 属于 B 节点，N8/N9/N10 属于 D 节点，他们分到的虚拟节点一样多，而且区域大致相等。所以士兵的分配也比较均匀。

萧何看了韩信的三技能后，直呼：妙哉妙哉！

总结

本篇通过韩信点兵的故事，然后从故事中衍生出刘邦、韩信、萧何的对话，来讲解士兵的分组的问题。现在对故事中的知识点做一个总结：

哈希算法会带来增加或删除节点时，数据迁移量太大的问题。
一致性哈希算法降低了数据迁移量。
节点较少，哈希环上每个节点实际占据的区间大小不一，最终导致业务对节点的访问冷热不均。
引入虚拟节点映射解决了分布不均问题。
节点越多时，使用哈希算法时，需要迁移的数据就越多，而使用一致性哈希算法，迁移的数据就越少。
一致性哈希算法本质上是一种路由寻址算法，适合简单的路由寻址场景。
一致性哈希算法常用在负载均衡的架构设计中。

封面图片来源王者荣耀。

- END -

往期推荐：

四：用动图讲解分布式 Raftopen in new window

三：诸葛亮 VS 庞统，拿下分布式 Paxosopen in new window

二：用太极拳讲分布式理论，真舒服！open in new window

一：用三国杀讲分布式算法，舒适了吧？open in new window

作者简介：8 年互联网经验，擅长架构设计、分布式、微服务。手写了一套 SpringCloud 实战教程，自主开发了 PMP 刷题小程序和 Java 刷题小程序。回复 pdf 领取。

六、病毒传播：全靠 Gossip 协议

一、背景

我是一个小病毒，其他病毒都叫我小 B，我长得就是下图这个样子了。

我现在已经有 100 nm 大小了，我还有很多触角，人类把我的触角称为冠，所以给我起了个学术名：冠状病毒。对于这个学术名，我一直不满意，怎么能用外貌来取名呢，这是以貌取毒。

我出生在一个蝙蝠身上，每到晚上，这只动物就到处觅食，它最喜欢的就是在森林中觅食，但最近森林的范围急剧减少，它不得不到人类居住的城市来觅食，看着五颜六色的灯光，我如痴如醉。

这只蝙蝠携带了 100 多种病毒，比如埃博拉病毒、MERS 病毒，我每天和这些病毒一起嬉戏游玩。SARS 病毒是我的近亲，2002 年的时候，它还造成了一次不小的传染病疫情，轰动了整个病毒界，人类称它为非典。

二、意外

这天晚上，乌云密布，空气混浊，蝙蝠飞到了密林深处，突然浑身被一股电流击中，猝然倒地，一只大网将其捕获，随之而来的是穿着一袭黑色大衣的人类把蝙蝠关进了笼子里面。

随后的几天，蝙蝠一直被关在笼子里面，直到有一天，蝙蝠被带到了一个随处可见野生动物的地方，但这些动物要么是被粗绳绑起来了，要么是被关在铁笼里。一个肥头大耳的人类走进了蝙蝠，他将手里攒着的一大叠钞票给了黑衣人后，带走了蝙蝠。

蝙蝠可能与肥头大耳的人类走得太近，我被传到了人类的的手上，随后又通过他接触的食物进入到了他的口中，进而进入到了他的体内。

三、种子节点

进入到人体中后，我欺骗了人类的免疫系统，顺利进入到人体细胞中，释放自己的 RNA，通过正常细胞的 RNA 聚合酶来复制自己的 RNA，从而复制出更多的病毒，进而攻击人体肺部器官。

过了几天后，这名人类出现了发烧现象，同时伴有咳嗽症状，而我的同伴也通过喷嚏传到了其他人体中，同样开始大量复制自己。

一传十，十传百，这个地级市已有数千名人类被病毒感染。而我就被称作种子节点，而那名人类被称作零号病人。

四、Gossip 协议

人体内的正常细胞对我的传染性非常感兴趣。

正常细胞：“冠状大哥，你是怎么这么快进行传播的啊？”
我：“其实我是利用了 Gossip 协议。”
我：Gossip 主要有三大功能，直接邮寄、反熵、谣言传播。

Gossip 的中文意思就是流言蜚语，该协议就像流言蜚语一样，利用一种随机、带有传染性的方式，将信息传播到整个网络中，并在一定时间内，使得系统内的所有节点数据一致。这个就是实现了最终一致性的协议。

4.1 直接邮寄

直接发送需要更新的数据到其他节点，当数据发送失败时，将数据缓存下来，然后重传。如下图所示，人类 A 直接将病毒传染给了 C 和 E，而 B 和 D 没有被感染到，需要重新传染。

优点：实现容易，数据同步及时。

缺点：可能会因为重试的缓存队列满了而丢数据。无法实现最终一致性。

那如何实现最终一致性呢？那就要用到第二种功能了：反熵。

4.2 反熵

反熵这个名词怎么理解呢？

熵指混乱程度，反熵就是消除不同节点间数据的差异，提升节点间数据的相似度。

反熵的过程：

（1）集群中的节点，每隔段时间就随机选择某个其他节点。
（2）互相交换自己的所有数据来消除两者之间的差异。
（3）实现数据的最终一致性。

下面举个病毒传染的例子来说明反熵。

首先人类 A 被感染了两种病毒，分别是病毒 T 和病毒 R，如下图所示：

人类 E 被感染了三种病毒，分别是病毒 T、病毒 S、病毒 Y，如下图所示：

人类 A 将携带的病毒 T 和 R 传染给了人类 E，而 E 本来就携带了病毒 T，所以最后会被传染四种病毒：T、S、Y、R。也就是说通过反熵的方式，修复了人类 E 中缺失的病毒 R。如下图所示：

其实，反熵主要有三种方式：推、拉、推和拉。

4.2.1 推

推：将自己的副本数据推给对象，修复对方副本中的熵。

如下图所示，人类 A 将病毒 R 传染（推）给了人类 E，E 中就包含所有 A 的病毒了。

4.2.2 拉

拉：拉取对方中的所有副本数据，修复自己副本中的熵。

如下图所示：人类 A 只有病毒 T 和 R，经过主动拉方式后，将人类 E 的病毒 S 和病毒 Y 同步到人类 A 身上了，最后，人类 A 携带四种病毒：T、R、S、Y。

4.2.3 推拉

推拉：同时修复自己副本和对象副本中的熵。

如下图所示：人类 A 和人类 E 通过推拉的方式最后都被感染了相同的四种病毒：T、R、S、Y。

4.2.4 反熵的缺点

（1）通过上面推、拉、推拉的方式，我们可以主要到，反熵是需要节点两两交换和比对自己所有的数据，这样来看的话，通讯成本是很高的，所以不建议实际场景中频繁地执行反熵。

那有没有办法来减少反熵的次数呢？

答案是有的，我们可以通过引入校验和等机制来降低需要对比的数据量和通讯信息。

（2）执行反熵时，相关节点都是已知的，且节点数量不能太多。如果节点动态变化或节点数过多，反熵就不合适。

那有没有办法来解决动态、多节点的最终一致性呢？

答案是有的，那就要用到 Gossip 协议的第三种传播功能了，谣言传播或者叫流行病传播。

4.3 流行病传播

4.3.1 过程

Gossip 协议的第三种传播功能，流行病传播，也就是广泛地散播病毒。

如下图所示：A 传染给了 B 和 E，B 传染给了 C 和 D，D 传染给了 F 和 G。最后 ABCDEFG 都被感染了。

在分布式系统中，当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有节点都存储了该数据，可以理解为之前讲的反熵中的推的方式。如下图所示：

4.3.2 缺点

流行病传播的方式有如下缺点：

时间随机：所有节点达到一致性是一个随机性的概率。可以改进反熵的流程：使用闭环修复。
消息冗余：同一节点会多次接收同一消息，增加消息处理的压力，每一次通信都会对网络带宽、CPU 资源造成负载，进而影响达到最终一致性的时间。
拜占庭问题：如果有恶意节点出现，那么其他节点也会出问题。所以需要先修复故障节点。

4.3.3 优点

支持动态、多节点：允许动态增加或减少节点，支持非常多的节点。
大多数节点：不需要大多数节点正常运行也能达到最终一致性
容错：任何节点重启或宕机都不会影响 Gossip 协议的运行，天然的分布式系统容错特性。
去中心化：节点都是对等的，没有特殊节点。任何节点出现问题都不会阻止其他节点继续执行反熵。
速度快：因为每个节点都可以进行传播，所以速度是指数级的，就像现在的新冠病毒一样。

因为 Gossip 协议是一个带冗余的容错算法，为了保证最终一致性的算法。虽然所有节点达到一致的时间点不明确，但也可以通过改进反熵的执行过程来达到可预测，比如闭环反熵（不在本文展开论述）。

五、总结

本文通过一个携带冠状病毒的蝙蝠传染人类的故事来讲解了 Gossip 协议。

Gossip 协议是一种异步修复、实现最终一致性的协议。优先考虑反熵。
反熵在存储组件中用得比较多。比如 Cassandra、InfluxDB。
谣言传播（流行病传播）具有传染性，节点之间相互传染。适合动态变化的分布式系统。比如 Cassandra 动态管理集群的节点状态。
实际场景，直接邮寄一定要实现，性能损耗最低。通过发送更新数据或缓存重传就能修复数据的不一致。
在存储组件中，节点已知，采用反熵修复数据副本的不一致。
集群节点变化时，或节点较多时，采用谣言传播方式，来同步更新多节点的数据，来实现最终一致性。
Gossip 的三种功能其实都是为了实现反熵，第一种用消息队列，第二种用推拉消息，第三种用散播谣言。
如果节点出现故障，需要先修复故障节点。

七、太上老君的炼丹炉之分布式 Quorum NWR 算法

太白金星：听闻老君最近在练神丹妙药，可否与我一讲？
太上老君：老白啊，我最近在练六颗丹药：两颗延年丹、两颗健步丹、两颗恢复丹。
太白金星：那这三个八卦炉定是练这三件法宝的了？
太上老君：正是正是。而且对于相同的丹药，功效和大小还得完全一样。

一、三个炼丹炉怎么分配的

太白金星：老君，你的八卦炉怎么分配的啊？

让我们揭开老君的炼丹炉，看看六颗丹药是怎么分配的。

首先我们是很容易猜到丹炉是怎么分配炼丹的：

一号丹炉炼两颗延年丹。
二号丹炉炼两颗健步丹。
三号丹炉炼两颗恢复丹。

那如此分配会有什么问题呢？

我们试想一下，如果一号丹炉因为炉火太高炸裂了，那么两颗延年丹定会失败。这和把鸡蛋放到一个篮子里面是一个道理。假如篮子不慎被打翻，里面的鸡蛋都掉出来，就都碎了。

太上老君：老白，我把锅炉的盖子揭开给你看看你就知道了。

一号丹炉炼一颗延年丹和一颗健步丹。
二号丹炉炼一颗延年丹和一颗恢复丹。
三号丹炉炼一颗健步丹和一颗恢复丹。

太白金星：老君，为何要如此分配，每个丹药的火候可不那么好把控啊？
太上老君：老白，我可是炼丹大师，火候难不倒我。
太白金星：不愧是老君啊，这样即使有一个丹炉有问题，至少能保证一颗能炼成，而不是两颗都毁了。

映射到我们互联网系统中：丹炉类似于服务器节点或数据库节点，通过多个节点来相互备份数据来保证系统的高可用性（High Availability）。

二、如何保证丹药品质一样

2.1 一致性

太白金星：老君，你刚提到，两颗延年丹需要保证功效一样，大小一样？
太上老君：确实如此，丹药品质必须保持一致，我炼的都是九品丹药，药效差一点则是千差万别。

太上老君说的品质保持一致到底怎么回事？

一号丹炉里面的延年丹和二号丹炉的延年丹如何保证品质一致呢？

这不就是我们常常说的分布式一致性吗？两颗丹药分布在不同的丹炉中，需要保证品质一致。

如下图所示，这两颗延年丹的一大一小，颜色也有不同，这就是品质不一样。

而在架构设计中，比如请求访问到不同的数据库，查到的数据都是一样的，这就是一致性。

如下图所示：浏览器访问数据库 1 和数据库 2 中的数据 A，结果返回的都是 A = 1。

2.2 最终一致性和强一致性

分布式中的一致性又分为最终一致性和强一致性。

所谓强一致性就是写操作完成后，任何后续访问都能读到更新后的值。这就是CP系统所要求的一致性和分区容错性。。

那放到炼丹中怎么理解？

比如老君给一号丹炉的延年丹加入了莲花这种药材，给二号丹炉的延年丹也这么操作，那么老白揭开炉盖看到的两颗延年丹的成分是一样的。

而最终一致性就是不保证后续访问都能读到更新后的值，但是经过一段时间后，再去读，就能得到相同的值。也就是说，在这段时间内，可能读到旧的数据。这就是 AP系统所要求的可用性和分区容错性。

放到炼丹中怎么理解？

比如老君给一号丹炉的延年丹加入了莲花，而经过了一个时辰后，才给二号丹炉加雪莲，那么在这个时辰内，看到的两颗延年丹的成分就不一样了。但经过一个时辰后，最终成分一样。

三、可控的品质：Quorum NWR 协议

Quorum NWR

假如延年丹必须保证品质的强一致性，而健步丹只需要保证品质的最终一致性，这个该怎么控制呢？

这个可没有难倒老君，因为老君懂得分布式协议：Quorum NWR。

Quorum 这个单词的意思：(会议的)法定人数。主要是看后面三个大写字母：N、W、R。由 NWR 来控制一致性。

3.1 参数 N

我们还是来看下丹炉中的情况，两颗延年丹是互为备份的，相当于有两个副本。

N 称作副本数，又叫做复制因子（Replication Factor）。表示同一份数据有多少个副本，所以：延年丹的 N = 2。依次类推：健步丹的 N = 2，恢复丹的 N = 2。如下图所示：

那 N 可以变吗？

如下图所示：比如我想炼 3 颗延年丹，也就是每个丹炉都有延年丹，那就把 N 改成 3 就可以了。而健步丹只需要炼一颗足以，那一号丹炉炼就可以了，所以N = 1。

3.2 参数 W

指定了副本数 N 之后，就可以对副本数据进行读写操作。

读操作：查看所在丹炉内丹药的情况。
写操作：给丹药添加药材、提高温度。

那多个丹药该如何执行读写操作呢？对于写操作，我们有 W 参数，对于读操作，我们有 R 参数。

W 称为写一致性级别（Write Consistency Level），表示成功完成 W 个副本更新，才完成写操作。

比如设置延年丹的 W = 2，表示对延年丹执行写操作时，完成了 2 个副本的更新时，才完成写操作。

如下图所示：一号丹炉和二号丹炉中的延年丹都加入了莲花，而三号丹炉中的延年丹未加入莲花。也就是只完成了两个副本的更新，符合 W = 2 这个条件，即写操作完成。

但是大家发现问题没，三号丹炉的延年丹未加入莲花，那怎么保证太上老君查看丹药情况时，得知是已加入莲花呢？也就是如何保证读写的强一致性，这就要用到第三个参数了：R。

3.3 参数 R

R 称为读一致性级别（Read Consistency Level），表示读取一个数据对象时，需要读 R 个副本，然后返回 R 个副本中最新的那份数据。

回到炼丹的问题中，设置延年丹的 R = 2，也就是查看延年丹的情况时，只需要查看两个丹炉内的延年丹的情况，然后返回最新的延年丹的情况就可以了。

假设查看的是一号和二号丹炉内的延年丹，返回的情况都是：已加入莲花。这种场景是一致性的。
假设查看的是一号和三号丹炉内的延年丹，一号丹炉的延年丹是已加入莲花，三号丹炉是未加入莲花，但是三号丹炉内的延年丹最后一次操作时间是早于一号丹炉的，所以返回一号丹炉内延年丹的情况：已加入莲花。这种场景也是一致性的。

通过上面的两种场景，我们知道，通过设置 R = 2，即使读到第三份未更新的数据，也能返回更新后的数据，实现强一致性。

3.4 参数组合

参数 N、W、R 的不同组合将会带来不同的一致性效果。

比如上面的例子，N = 3，W = 2，R = 2，W + R > N，对于客户端来讲，整个系统能保证强一致性，一定能返回更新后的那份数据。
当 W + R <= N 时，对于客户端来讲，整个系统只能保证最终一致性，访问数据期间可能会返回旧数据。

参数不同，效果不同，分布式系统需要场景来配置。

四、应用

InfluxDB 企业版是时序数据库，它有四种写一致性级别：

any：W + R < N，W = 1，任何一个节点写入成功后，或者写入 Hinted-handoff 缓存（等下次重传），返回成功给客户端。
one：W + R < N，W = 1，任何一个节点写入成功后，立即返回成功给客户端，不包括写入 Hinted-handoff 缓存
quorum：W + R > N，大多数节点写入成功后，就返回成功给客户端。（要求 N 大于2）
all：W = N，所有节点都写入成功后，返回成功。

另外对于时序数据库 InfluxDB 来说，读操作需要读取大量数据，为了保证读取的高效，它不支持读一致性级别（R = N），但是可以通过设置写一致性级别为 all，来实现强一致性。

InfluxDb 实现了 Quorum NWR，当线上业务需要临时做些一致性调整时，设置不同的写一致性级别即可完成快速切换。

五、总结

本文通过太上老君和太白金星关于炼丹的对话，引申出自定义一致性的分布式协议：Quorum NWR 协议。

N 代表副本数，W 代表写多少个副本数，R 代表读多少个副本数。
当 N 大于节点数时，就会出现一个节点存在多个副本的情况，这个节点故障时，多个副本会受到影响。
W + R > N 时，代表强一致性。
W = N 时，读性能好。R = N，写性能好。
W = R = (N+1)/2，容错能力好，能容忍少数节点（也就是(N-1)/2）个节点故障。
如何设置 N、W、R 值，取决于我们的系统该往哪方面优化。
Quorum NWR 分布式算法给业务提供了按需选择一致性级别的灵活度，弥补了 AP 型系统缺乏强一致性的缺点。

太白金星：预祝你炼丹成功！

八、紫霞仙子：顶得住区块链的十二连问吗？

最近更新了八篇分布式的文章，准备写第九篇的时候，发现跟区块链关系非常紧密，于是就先写一篇区块链的科普文章吧。

紫霞仙子：听说你最近在学区块链，给我讲讲呗~

一、用大白话说下什么是区块链？

1.我是至尊宝，我爱紫霞仙子你，在这个时间，这个地点，我对紫霞你说：至尊宝爱紫霞一万年。

2.现在我把这句话写在了纸上：
爱情真言
3.但是如果我把这张纸交给紫霞你，你又怕我反悔。而如果我把这张纸交给月老，我又怕月老可能会修改内容，而改成只爱你一年。

4.我为了防止类似事情发生，就把这些这爱情真言，告诉了师父、二师弟悟能、三师弟悟净、白龙马、牛魔王等认识的人，他们都帮我们记录了这些信息。

5.目前这份信息现在是安全的，我无法抵赖，我会爱你一万年。

6.为了表达对他们帮忙记录信息的感谢，我给他们每个人发了一个红包。

7.而那些帮我们记录的人就称作节点。

8.而至尊宝爱紫霞一万年这句话+时间+地点这些信息，打包起来就形成了一个信息包，也就是区块链中的区块。而多个区块连在一起就是区块链。

9.去中心化就是不需要月老来统一记录这些信息。

10.娶亲当天，我答应了紫霞三个条件，又需要去记录了，而师父和师弟他们很忙，不想浪费时间在记录上面，所以决定选一个人来帮助大家记录这些信息。

12.选谁来记录呢？会不会不安全呢？那就来个很难的算数题吧，谁能算出来，就给谁来记录，我还会给记录的人一个大红包，也就是比特币。而做出算数题就称作工作量证明。

13.而这个记录的人就被称作矿工。矿工们不断算题，争夺信息记录的权利。从而获得信息记录的奖励。

二、什么是区块链？

区块链的英文是 Block Chain，它的技术的产生和发展跟比特币有着千丝万缕的联系。

因比特币的火热，区块链技术被世人所知。比特币是区块链技术最成功最成熟的应用案例。
区块链技术作为构建比特币数据结构及交易体系的基础技术。
区块链是一个去中心化的分布式数据库，该数据由一串使用密码学方法产生的数据区块有序链接而成，而区块中包含有一定时间内产生的无法被篡改的数据记录信息。
区块链由多种技术整合：密码学、数学、经济学、网络科学等。这些技术以特定方式组合在一起，形成了一种新的去中心化数据记录与存储体系。而每个区块上又打上了时间戳，形成了前后关联且连续的诚实数据记录存储结构。

三、为什么要有区块链？

区块链解决了以下两个问题：

交易确认和资金清算问题

现实社会中各种经济活动涉及资金清算的，除了直接的现金交易外，都需要当事人执行以下步骤：

在银行等机构开立账户。
通过开户机构进行资金清算。

但由于公民有多个开户机构的账户，甚至还有跨国账户，而当事人的交易必须通过开户机构之间的清算才能完成。严重影响了交易确认和资金清算的效率和成本。

中心化问题

传统的信用建立是靠很多的中心，譬如央行、商业银行，还有法院、经济警察等。但带来的问题就是成本过高。

而且我们存的钱都是银行管控的，如果银行倒闭了，那存的钱可能就没有意义了。

四、什么是比特币？

比特币由中本聪在 2008 年发表的论文《比特币：一种点对点的电子现金系统中》首次提出。
比特币是一种虚拟的加密数字货币，去中心化的支付系统。不依赖特定的货币机构发行，不受央行和任何金融机构控制。
根据特定算法，通过大量的计算产生。
通过计算得到的区块奖励最开始是 50 个比特币，每隔大约 10 分钟，下一批 50 个比特币产生。总量达到 1050 万（2100 万的 50%）时，奖励减半为 25 个。每隔 4 年，奖励减半，总量最多为 2100万。
比特币可以通过挖矿获得，也可以通过交易购买获得。

下图总结了普通货币和比特币的区别：

五、区块内包含什么？

区块链的区块由区块头和区块体两部分组成。

区块头：由上一个区块的哈希值、区块体的哈希值、4 字节的随机数、时间戳等组成。固定 80个字节。

区块体：区块包含的交易数据，其中第一笔交易是 CoinBase 交易，这个是一比激励矿工的特殊交易。

六、区块链的特性有哪些？

去中心化

区块链不依赖中央处理节点，实现了数据的分布式记录、存储和更新。

每个区块链节点都必须遵循同一个规则，而该规则基于密码算法而非信用，每次数据更新都需要网络内其他用户的批准，所以不需要一套第三方中介机构或信任机构背书。

传统中心化网络中，如果中心被攻击了，则会破坏整个系统。

透明性

读和写数据记录对全网节点是透明的。区块链使用开源的程序、开放的规则和高参与度，可被全网审查、追溯。

开放性

除了被加密的私有信息外，区块链的数据对所有人公开（特殊区块链系统除外）。

任何人都可以通过公开的接口查询记录。

自治性

整个系统可自由安全地交换数据、记录数据、更新数据。

信息不可篡改

信息一旦经过验证并添加至区块链后，就会得到永久存储，无法更改。

除非能够同时控制系统中超过 51%的节点，否则单个节点上对数据库的修改是无效的。

匿名性

交易的双方都是匿名的情况下进行，无须通过公开身份来让对方产生信任。

七、什么是挖矿？

矿指比特币。
挖矿指挖比特币。挖矿的过程其实就是解决复杂的密码学问题。
矿工指运用挖矿设备（比如CPU、GPU 等有计算能力的设备）来进行挖矿的人。而作为对他们服务的奖励，矿工可以得到他们所确认的交易中包含的手续费，以及新产生的比特币。
矿池指大家联合挖矿设备一起来挖矿，算力集中的地方。

而怎么才算挖到比特币呢？这个就牵扯到工作量证明了。

八、什么是工作量证明？

工作量证明的英文是 Proof of Work，简称 PoW。

在现实生活中，也有工作量证明这一说法：比如大学的学位证、毕业证，就是证明大学期间通过 4 年的努力完成了相关课程的学习，别说你没努力就拿到了证书，汗。

也就是说工作量证明就是通过指定的结果，来证明自己做过了一定量的工作。而在区块链中，这个工作就是哈希运算。

区块链中节点通过哈希运算得到符合条件的哈希值，来证明工作量。而这个过程一个随机数的查找过程，俗称挖矿。

找到符合条件的随机数的方法是不停地随机试探，直到搜索到一个有效的数。而这个随机数是由 N 个前导零构成，零的个数取决于网络的难度值。比如以下的随机数由四个前导零构成。

0000ec5927ba10ea45a6822dcc205050ae74ae1ad2d9d41e978e1ec9762dc404

工作量证明的三要素如图所示：

输入：拥有 80 字节固定长度的区块头。

算法：双重 SHA 256 哈希运算。也就是对 SHA256 哈希运算的结果，再执行一次哈希运算。

条件：计算出的哈希值，只有小于目标值，才是有效的，否则无效，必须重算。

九、区块链的工作原理？

计算出符合条件的哈希值后，然后怎么处理呢？

矿工就把这个哈希值的信息广播给集群中的所有其他节点，其他节点就进行验证，验证通过后，就会把之前那个矿工的区块加入到自己的区块链中，最终形成一串区块链。详细步骤如下：

1.节点将新的数据记录向全网进行广播。

2.接收节点对收到的数据记录信息进行合法性校验，如果有效，则将数据记录纳入一个区块中。

3.接收节点对区块执行共识算法。

4.共识达成后，区块被纳入节点的区块中进行延长。

最后形成的区块链就是如下图所示：

十、怎么攻击区块链？

计算哈希值完全依赖硬件的算力，算力越强，算出哈希值的概率越高，时间越短。

也就是说如果有坏人掌握了 51 % 的算力，就可以发起 51 % 的攻击，比如双花攻击（Double Spending）。也就是同一份钱花了 2 次。

如果攻击者掌握了较多的算力，就能挖掘出一条原链更长的攻击链。然后又将攻击链向全网广播。而节点按照约定会接受更长的链，也就是会接受攻击链，丢弃原链。如下图所示：

攻击链是红色那一条，比原链分支多一个区块，被系统接受，称为有效的链，而原链就被废弃了。

十一、区块链的缺点

区块链体积过大

区块链不断地发展，节点存储的区块链数据体积会越来越大，存储和计算负担将会越来越重。比如现在的比特币区块链，完整数据已经超过 60 GB，如果用比特币客户端进行数据同步的话，至少三天三夜。

数据确认时间过长

比特币交易的一次确认时间大约是 10 分钟，而完成 6 次确认的时间是 1 小时。需要等待 1 个小时才能完成确认。

交易频率过低

比特币每秒最高处理 6.67 笔交易。怎么算的呢？

每条交易大约 250 个字节，区块大小假定限制在 1 MB，可以容纳的交易数据量为 4000 条。每 10 分钟产生一个区块，每天可以产生 144 个区块，可以交易 144 * 4000 = 576000 条交易，然后除以每天的总秒数 86400，也就是 576000 / 864400 ≈ 6.67。

目前需要解决扩容问题才能突破这个瓶颈。

受到现行制度的制约

目前监管部门对这项新技术缺乏充分的认识和预期，法律和制度建立可能会滞后，也缺乏必要的制度规范和法律保护，加大了市场主体的风险。

十二、区块链的应用

物联网。传统的物联模式是由一个数据中心负责收集各连接的设备信息，成本很高。而利用区块链使这些设备连在一起形成一个可持续运行的分布式网络。各设备可自行发送更换零配件的订单，甚至还能和其他设备进行电源竞价，使用户家庭能源消耗地最小化。
保险。传统的保险模式是通过投保人申请理赔的方式。而如果用区块链的职能合约技术，保险公司无需等待投保人申请理赔，就能主动进行赔付。
医疗。现在医院都改用电子病历了，但是存储信息是在医院处，这就是一个中心化的问题，而带来了医患纠纷问题和安全性问题。如果用区块链技术，则病历信息不可篡改和高强度保密。

总结

本文用一个故事开头，大白话讲解了区块链的概念，然后用 11 个核心问题来理清区块链中大家常关心的问题。
本文既是一篇科普文章，也是一篇原理性文章，对于原理性的问题，我都用图解的方式来讲解，相信会较容易理解一点。
区块链跟分布式联系紧密，比如区块链中用到 PoW 算法，拜占庭容错，都是充分利用分布式特性。学习区块链的过程也是学习分布式的过程。

巨人的肩膀：

《分布式协议与算法实战》

《区块链：从数字货币到信用社会》
https://zhuanlan.zhihu.com/p/267270739open in new window

https://www.zhihu.com/question/268487023open in new window

昵称

邮箱

网址

按正序
按倒序
按热度