分布式与一致性协议相关

概述。
拜占庭将军问题其实是借拜占庭将军故事展现了分布式共识问题，探讨和论证了解决的办法。
实际上，拜占庭将军问题是分布式领域最复杂的一个容错模型，一旦搞懂了它，久能掌握分布式
共识问题的解决思路，还能更深刻地理解常用的共识算法，这样在设计分布式系统的时候，就能
根据场景特点，更好地选择或者设计合适的算法

什么是拜占庭将军问题?
以战国时期六国抗秦的故事为主线串联

概述。
前面提到了拜占庭将军问题之后，有人可能会感到困惑:口信消息型拜占庭问题直接在实际项目中是如何落地的呢？事实上，它很难在实际项目中落地，因为口信消息型拜占庭问题之解是一个非常理论化的算法，没有与实际场景结合，也没有考虑如何在实际场景中落地和实现。

比如，它实现的是在拜占庭错误场景下，忠将们如何在判断干扰时就一致行动达成共识。但是它并不关心结果是什么，这会出现一种情况:现在适合进攻，但将军们达成的最终共识却是撤退。

很显然，这不是我们想要的结果。因为在实际场景中，我们需要就提议的一系列值(而不是单值)，即使在拜占庭错误发生的时候，也能达成共识。那我们应该怎么做呢？答案就是采用PBFT算法。

PBFT算法非常实用，它是一种能在实际场景中落地的拜占庭容错算法，在区块链中应用广泛(比如Hyperledger Sawtooth、Zilliqa)。为了更好地理解PBFT算法，下面会先介绍口信消息型拜占庭问题之解的局限，再介绍PBFT算法的原理。

老规矩，我们先看一道思考题。
假设苏秦再一次带队抗秦，如苏秦和4个国家的4位将军赵、魏、楚、韩商量军机要事，如图所示，结果刚商量完没多久苏秦就接到了情报:联军中可能存在一个叛徒。这时，苏秦要如何下发作战指令来保证忠将们正确、一致地执行下发的作战指令，而不被叛徒干扰呢？

口信消息型拜占庭问题之解的局限。
口信消息型拜占庭问题之解有个非常致命的缺陷。如果将军数为n、叛将数为f,那么算法需要递归协商f+1轮，消息复杂度为O(n^(f+1))，消息数量指数级暴增。你可以想象以下，如果叛将数为64，那么消息数会远远超过int64所能表示的数量，这是无法想象的，不可行的。

另外，尽管对于签名消息，不管叛将数(比如f)是多少，经过f+1轮的协商，忠将们都能达成一致的作战指令，但是这个算法同样存在"理论化"和"消息数指数级暴增"的痛点，说到这儿，你肯定明白为什么这个算法很难再实际场景中落地了。不过技术是不断发展的，算法也是在解决实际场景问题中不断改进的。那么PBFT算法的原理是什么呢？为什么它能在实际场景中落地呢？

PBFT算法是如何达成共识的。
我们先来看看如何通过PBFT算法解决苏秦面临的共识问题。先假设苏秦制定的作战指令是进攻，而楚是叛徒(为了演示方便)，如图所示
需要注意的是，所有的消息都是签名消息，也就是说，消息发送者的身份和消息内容都是无法伪造和篡改的(比如，楚无法伪造一个假装来自赵的消息)。
首先，苏秦联系找，向赵发送包含作战指令"进攻"的请求，如图所示.
当赵接收到苏秦的请求之后，会执行三阶段协议(Three-phase protocol)。
赵将进入预准备(Pre-prepare)阶段，构造包含作战指令的预准备消息，并广播给其他将军(魏、韩、楚)，如图所示。

在这里想问一个问题:魏、韩、楚收到消息后能之解执行指令吗？
答案是不能，因为他们不能确认自己接收到的指令与其他人接收到的指令是相同的。比如,赵可能是叛徒，赵收到了两个指令，分别是"进攻"和"准备30提案的粮草"，然后他给魏发送的是"进攻"，给韩、楚发送的是"准备30天粮草"，这样就会出现无法一致行动的情况。那么具体怎么办呢？
接收到预准备消息之后，魏、韩、楚将进入准备(Prepare)阶段，并分别广播包含作战指令的准备消息给其他将军。比如，魏广播准备消息给赵、韩、楚，如图所示。为了方便演示，我们假设叛徒楚想通过不发送消息来干扰共识协商(如图所示，楚没有发送消息)。

然后，某个将军在收到2f个(包括自己，其中f为叛徒数,在该演示中是1)一致的包含作战指令的准备消息后，会进入提交阶段(Commit)阶段。在这里，提一个问题:此时该将军(比如魏)可以之解执行指令吗?
答案是不能，因为魏不能确认赵、韩、楚是否收到了2f个一致的包含作战指令的准备消息。也就是说，魏这时无法确认赵、韩、楚是否已经准备好执行作战指令，那么怎么办呢？

进入提交阶段后，阁将军(不包括叛徒楚)分别广播提交信息给其他将军，也就是告诉其他将军，我已经准备好执行指令了，如图所示
最后，当某个将军收到2f+1(包括自己，其中f为叛徒数，在该演示中为1)个验证通过的提交消息后，也就是大部分的将军已经达成共识，可以执行作战指令了，那么该将军将执行苏秦的作战指令，并在执行完毕后发送执行成功的消息给苏秦，如图所示。

最后，当苏秦收到了f+1个(其中f为叛徒数，在该演示中为1)相同的响应(Reply)消息时，说明各位将军们已经就作战指令达成了共识，并执行了作战指令。
你看，将军们经过3轮协商，是不是就指定的作战指令达成了共识并执行了作战指令呢？
在这里，苏秦采用的就是简化版的PBFT算法，在这个算法中:
1.可以将赵、魏、韩、楚理解为分布式系统的四个节点，其中赵是主节点(Primary),魏、韩、楚是备份节点(Backup);
2.可以将苏秦理解魏业务，也就是客户端
3.可以将消息理解为网络消息
4.可以将作战指令"进攻"理解为客户端提议的值，也就是希望被个节点达成共识并提交给状态的值。
PBFT算法通过签名(或消息认证码MAC)来约束恶意节点的行为的，也就是说，每个节点都可以通过验证消息签名来确认消息的发送来源，一个节点无法伪造另外一个节点的消息。同时，该算法是基于大多数原则(2f+1)实现共识的。而最终的共识是否达成，是由客户端进行判断的，如果客户端在指定事件内未收到请求对应f+1个相同响应，则认为集群故障，未达成共识，且客户端会重新发送请求。

需要注意的是，PBFT算法通过视图变更(View Change)的方式来处理主节点作恶行为，当发现主节点在作恶时，该算法会以"轮流上岗"的方式推荐新的主节点。另外，尽管PBFT算法相比口信消息型拜占庭之解已经有了很大的优化，如将消息复杂度从O(n^(f+1))降低为O(n^2)，能在实际场景中落地，以及能解决实际的共识问题等，但PBFT还是有一定的局限，如需要发送比较多的消息，以13节点的集群(f为4)为例，PBFT算法需要涉及如下消息.
1.请求消息:1
2.预准备消息:3f=12
3.准备消息:3f*(3f-f)=96
4.提交消息:(3f-f+1)*(3f+1)=117
5.恢复消息:3f-1=11
也就是说，一次共识协商需要237个消息，消息数还是蛮多的，所以推荐在中小型分布式系统中使用PBFT算法。

注意。
PBFT算法与Raft算法类似，也存在一个"领导者(就是主节点)"，同样，集群的性能也受限于"领导者"。另外，O(n^2)的消息复杂度，以及随者消息数的增加，网络时延对系统运行的影响也会越大，这些都限制了运行PBFT算法的分布式系统的规模，也决定了PBFT算法只适用于中小型分布式系统。

如何替换作恶的主节点。
虽然PBFT算法可以防止备份节点作恶，因为这个算法是由主节点和备份节点组成的，但是，如果主节点作恶(比如主机点接收到了客户端的请求，但就是默不作声，不执行三阶段协议)，那么无论正常节点数有多少，备份节点肯定无法达成共识，整个集群也将无法正常运行。针对这个问题，我们该如何解决呢？
答案是视图变更，也就是通过领导者选举楚新的主节点，并替换掉作恶的主节点。(其中的"视图"可以理解为领导者任期内不同的视图值对应不同的主节点，比如，视图值为1时，主节点为A;视图值为2时，主节点为B)
需要注意的是，对于领导者模型算法而言，不管是非拜占庭容错算法(比如Raft算法)还是拜占庭容错算法(比如PBFT算法)，领导者选举都是它们实现容错能力非常重要的一环。比如，对Raft算法而言，领导者选举实现了领导者节点的容错能力，避免了因领导者节点故障而导致的整个集群不可用的问题。而对PBFT算法而言，视图变更，除了能解决主节点故障导致的集群不可用的问题之外，还能解决主节点是恶意节点的问题。
既然领导者选举这么重要，那么PBFT算法到底是如何实现视图变更的呢？

PBFT算法的局限、解决办法和应用。
如同一枚硬币具有正反两面，任何一个算法也会有优缺点，PBFT算法也不例外。接下来，将介绍PBFT算法的局限、解决办法，以及实际应用情况。
首先，在一般情况下，每个节点都需要持久化保存状态数据(比如准备消息)，以便后续使用，但随着系统运行，数据会越来越多，最终肯定会出现存储空间不足的情况，那么，怎么解决这个问题？
答案是检查点机制，PBFT算法实现了检查点机制，来定时清理节点缓存在本地但已经不再需要的历史数据(比如预准备消息、准备消息和提交消息)，节省了本地的存储空间，且不会影响系统的运行。
其次，我们都知道基于数字签名的加解密非常消耗性能，这也是为什么在一些对加解密要求高的场景中，大家常直接在硬件中实现加解密，比如IPSEC VPN。如果在PBFT算法中，所有消息都是签名消息，那么肯定非常消耗性能，且会极大地制约PBFT算法的落地场景，那么有什么办法优化这个问题吗？
答案是将数字签名和消息验证码(MAC)混合使用。具体来说，在PBFT算法中，只有视图变更消息和新视图消息采用签名消息，其他消息则采用消息验证码，这样一来，就可以节省大量加解密的性能开销。
最后，PBFT算法是一个能在实际场景中落地的拜占庭容错算法，它和区块链也结合紧密，具体有以下几个应用:
1.相对可信、有许可限制的联盟链，比如Hyperledger Sawtooth
2.与其他拜占庭容错算法结合来落地公有链，比如Zilliqa，将Pow算法和PBFT算法结合起来，实现公有链的共识协商。具体来说，PoW算法用于认证，证明节点不是"坏人"，PBFT算法用于实现共识。针对PBFT算法消息数过多、不适应大型分布式系统的痛点，Zilliqa实现了分片(Sharding)技术。
另外，也有团队因为PBFT算法消息数过多、不适应大型分布式系统的痛点，放弃使用PBFT算法，而是通过法律来约束"节点作恶"的行为，比如IBM的Hyperledger Fabric。技术是发展的，适合的才是最好的。在实际工作中，建议根据场景的可信度来决定是否采用PBFT算法，是否改进和优化PBFT算法。

重点总结。
1.PBFT算法是通过签名(或消息认证码MAC)来约束恶意节点的行为，同时采用三阶段协议，基于大多数原则达成共识的。另外，与口信消息型拜占庭问题之解(以及签名消息型拜占庭问题之解)不同的是，PBFT算法实现的是一系列值得共识，而不是单值的共识。
2.客户端通过等待f+1个相同响应消息超时来发现主节点可能在作恶，此时客户端会发送客户端请求给所有集群节点，从而触发可能的视图变更。与Raft算法在领导者期间服务不可用类似，在视图变更时，PBFT集群也是无法提供服务的。

概述。
在开发分布式系统的时候，会遇到一个非常棘手的问题，那就是如何根据业务特点，为系统设计
合适的分区容错一致性模型，以实现集群能力。这个问题棘手在当发生分区错误时，应该如何
保障系统稳定运行而不影响业务。
CAP理论对分布式系统的特性做了高度抽象，比如抽象成一致性、可用性、分区容错性，并对
特性间的冲突(也就是CAP不可能三角)做了总结。
问题来了:什么是一致性、可用性和分区容错性？它们之间有什么关系？我们又该如何使用CAP理论
来思考和设计分区容错一致性模型呢？

CAP理论:分布式系统的PH试纸，用它来测酸碱度。
CAP理论就像PH试纸一样，可以用来度量分布式系统的酸碱度，帮助我们思考如何设计合适的酸碱度，
在一致性和可用性之间进行妥协、这种，进而设计出满足场景特点的分布式系统。那么如何理解CAP理论呢？

ACID理论:CAP的"酸"，追求一致性。
提到ACID,它很容易理解，在单机上实现也不难，比如可以通过锁、时间序列等机制保障操作的顺序执行，
让系统实现ACID特性。但是一说要实现分布式系统的ACID特性比较难实现呢？
ACID理论是对事务特性的抽象和总结，方便我们实现事务。可以这样理解：如果实现了操作的ACID特性，
那么旧实现了事务。二大多数人觉得比较难，是因为分布式系统涉及多个节点间的操作。加锁、时间序列
等机制只能保证单个节点上操作的ACID特性，无法保证节点间操作的ACID特性。那么怎么做才会让实现
不那么难呢？答案是通过分布式事务协议实现，比如二阶段提交协议和TCC(Try-Confirm-Cancel),不过
在介绍二阶段提交协议和TCC之前，咱们先继续看看苏秦的故事，看这回苏秦又遇到了什么事。

最近呢，秦国按耐不住自己躁动的心，开始骚扰魏国边境，魏王头疼，向苏秦求助，苏秦认为"三晋一家亲"，
建议魏王联合赵、韩一起对抗秦国。但是这三个国家实力都很弱，需要大家都同一联合，一致行动，如果有
任何一方不方便行动，就取消整个计划。根据侦察情况，明天发动反攻的胜算比较大。所以苏秦想协调赵、
魏、韩明天一起行动，如图所示，那么对于苏秦来说，他面临的问题是，如何高效协同赵、魏、韩一起行动，
并且保证当有一方不方便行动时，取消整个计划。苏秦面临的这个新问题，就是典型的如何实现分布式事务
的问题。赵、魏、韩明天攻打秦国，这三个操作组成一个分布式事务，要么全部执行，要么全部不执行。
了解了这个问题之后，我们来看看如何通过二阶段提交协议和TCC帮助苏秦解决这个难题

BASE理论:CAP的"碱"，追求可用性。
很多人可能喜欢使用事务型的分布式系统或者强一致性的分布式系统，因为方便，不需要考虑太多，就像
单机系统一样。但是学了CAP理论后，你肯定知道在分布式系统中，要实现强一致性，必然会影响可用性。
比如，在采用两阶段提交协议的集群系统中，要执行提交操作，需要所有节点确认和投票。
所以，集群的可用性时每个节点可用性的乘积，比如，假设有一个拥有3个节点的集群，每个节点的可用性为99.9%，
那么整个集群的可用性为99.7%，也就是说，每个月约宕机129.6分钟(按30天/月算)，这是非常严重的问题。而解决
可用性低的关键在于，根据实际场景，尽量采用可用性优先的AP模型。
有人可能会觉得，这也太难了，难道没有线程的库或者方案来实现合适的AP模型?是的，的确没有。因为AP是一个
动态模型，是基于业务场景特点妥协折中后设计实现的。不过我们可以借助BASE理论达成目的。
在我看来，BASE理论是CAP理论中的AP的延申是对互联网大规模分布式系统的实践总结，强调可用性。
几乎所有的互联网后台分布式系统都得到了BASE的支持，这个理论很重要，地位也很高。一旦掌握它，就能掌握
绝大部分场景的分布式系统的架构技巧，设计出适合业务场景特点的、高可用性的分布式系统。
BASE理论的核心就是基本可用(Basically Available)和最终一致性(Eventually Consistent)。也有人会提到软状态(Soft State).
在我看来，软状态描述的是在实现服务可用时，系统数据的一种过度状态,也就是说不同节点间的数据副本存在
短暂的不一致。那么基本可用以及最终一致性到底是什么呢?我们应该如何在实践中使用BASE理论提升系统的可用性呢?

概述。
提到分布式算法，就不得不提Paxos算法，在过去几十年里，它基本上时分布式共识的代名词，当前最常用的一批共识算法
都是基于它改进的。比如， Fast Paxos算法、Cheap Paxos算法、Raft算法等。但是，很多人都会在准确和系统理解Paxos算法
上踩坑，比如，只知道它可以用来达成共识，却不知道它是如何达成共识的。
这其实从侧面说明了Paxos算法有一定的难度，可分布式算法本身就很复杂，Paxos算法自然也不会例外。当然，除了这一点，
还与Paxos算法的提出者莱斯利兰伯特有关。
兰伯特提出的Paxos算法包含两个部分:
1.一个是Basic Paxos算法，描述的是多节点之间如何就某个值(提案Value)达成共识
2.另一个是Multi_Paxos思想，描述的是执行多个Basic Paxos示例，就一系列值达成共识。
但是，因为兰伯特提到的Multi-Paxos思想缺少代码实现的必要细节(比如怎么选举领导者)，所以我们理解起来比较困难

Basic Paxos:如何在多个节点间确定某变量的值。
在我看来，Basic Paxos是Multi-Paxos思想的核心，说白了，Multi-Paxos就是多执行几次Basic Paxos。所以掌握了Basic Paxos，
我们便能更好地理解后面基于Multi-Paxos思想的共识算法(比如Raft算法)，还能掌握分布式共识算法的最核心内容，当现有算法
不能满足业务需求时，可以权衡折中，设计自己的算法。

假设我们要实现一个分布式集群，这个集群由节点A、B、C组成，提供只读KV存储服务。你应该知道，创建只读变量的时候必须要
对它进行赋值，而且后续不能对该值进行修改。也就是说，一个节点创建只读变量后，就不能再修改它了，所以，所有节点必须要
先对只读变量的值达成共识，然后再由所有节点一起创建这个只读变量。
那么，当有多个客户端(比如客户端1、2)访问这个系统，试图创建同一个只读变量(比如X)时，例如客户端1试图创建值为3的X,客户端
2试图创建值为7的X，该如何达成共识，实现各节点上X值的一致呢？如图所示

在一些经典的算法种，你会看到一些既形象又独有的概念(比如二阶段提交协议种的协调者)，Basic Paxos算法也不例外。为了帮助人们
更好地理解Basic Paxos算法，兰伯特在讲解时也使用了一些独有而且比较重要的概念，如提案(Propose)、准备(Prepare)请求、接受(Accept)请求
、角色等，其中最重要的就是"角色"。因为角色时对Basic Paxos中最核心的3个功能的抽象，比如，由接受者(Acceptor)对提议的值进行投票，
并存储接受的值

Multi-Paxos:Multi-Paxos不是一个算法，而是一个统称。
通过前面的了解，你应该知道，Basic Paxos只能就单个值达成共识，一旦遇到要实现一系列值得共识的情况时，它就不管用了。虽然兰伯特
提到可以通过多次执行Basic Paxos示例(比如每接到一个值，就执行以此Basic Paxos算法)实现一系列值得共识。但是，很多人读完论文后，
还是两眼抹黑，虽然能读懂每个英文单词，但是不理解兰伯特提到得Multi-Paxos到底时什么意思。为什么Multi-Paxos这么难理解呢？
在我看来，兰伯特并没有把Multi-Paxos讲清除，只是介绍了大概的思想，缺少算法过程的细节和编程所必需的细节(比如缺少选举领导者的细节)，
导致每个人实现的Multi-Paxos都不一样。不过从本质上看，大家都是在兰伯特特岛的Mutli-Paxos思想上补充细节，设计自己的Multi-Paxos算法,
然后实现它(比如Chubby的MultiPaxos实现、Raft算法等)。
所以在这里，补充一下:兰伯特提到的Multi-Paxos是一种思想，不是算法。而Multi-Paxos算法是一个统称，它是指基于Multi-Paxos思想，通过
多个Basic Paxos实例实现一系列值的共识算法。这一点由器需要注意

重点总结。
1.除了共识，Basic Paxos还实现了容错，即在少于一半的节点出现故障时，集群也能工作。它不像分布式事务算法那样，必须要所有节点都同意
后才能提交操作。因为"所有节点都同意"这个原则在出现节点故障的时候会导致整个集群不可用。也就是说，"大多数节点都同意"的原则赋予了
Basic Paxos容错的能力，让它能够容忍少于一半的节点的故障
2.Chubby实现了主节点(也就是兰伯特提到的领导者)，也实现了兰伯特提到的"当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段"
这个优化机制省掉Basic Paxos的准备阶段，提升了数据的提交效率，但是所有写请求都在主节点处理，限制了集群处理写请求的并发能力，此时
其并发能力约等于单机的并发能力
3.因为Chubby的Multi-Paxos实现中也约定了"大多数原则"，也就是说，只要大多数节点正常运行，集群就能正常工作，所以Chubby能容错(n-1)/2
个节点的故障

概述。
Raft算法属于Multi-Paxos算法，它在兰伯特Multi-Paxos思想的基础上做了一些简化和限制，比如日志必须是连续的，
只支持领导者(Leader)、跟随者(Follwer)和候选人(Candidate)3种状态。在理解和算法实现上，Raft算法相对容易许多。
除此之外，Raft算法是现在分布式系统首选的共识算法。绝大多数选用Paxos算法的系统(比如Chubby、Spanner)都是在
Raft算法发布前开发的，当时没有其他选择;而全新的系统大多选择了Raft算法(比如Etcd、Consul、CockroachDB)。
掌握了Raft算法，我们就可以得心应手地满足绝大部分场景的容错和一致性需求，比如分布式配置系统、分布式NoSQL存储等，
轻松突破系统的单机限制。
如果要用一句话概括Raft算法，我觉得是这样的:从本质上说，Raft算法是通过一切以领导者为准的方式实现一系列值得共识和
个节点日志的一致。这句话比较抽象，做个比喻:领导者就是Raft算法中的"霸道总裁",通过霸道的"一切以我为准"的方式。决定了
日志中命令的值，也实现了个节点日志的一致。后面会以领导者选举、日志赋值、成员变更为核心，讲解Raft算法的原理。

在正式介绍之前，我们先来看一道思考题。
假设我们有一个由节点A、B、C组成的Raft集群(如图所示)，因为Raft算法是一切以领导者为准，所以如果集群中出现了多个领导者，
就会出现不知道谁来做主的问题。在这样一个有多个节点的集群中，在节点故障、分区容错等异常情况下，Raft算法应该如何
保证在同一个时间内集群中只有一个领导者呢?

Raft是如何选举领导者的。
既然要选举领导者，要从哪些成员中选举呢？除了领导者，Raft算法还支持哪些成员身份呢？这是需要掌握的最基础的背景知识。

Raft是如何复制日志的。
我们知道Raft除了能实现一系列值得共识之外，还能实现各节点日志的一致。但是，你也许会有这样的疑惑:"什么是日志?它和我的业务数据有什么关系呢?"
想象一下，一个木筏(Raft)是由多根整齐一致的原木(Log)组成的，原木又是由木质材料组成的，已知日志是由多条日志项(Log Entry)组成的，如果把日志比喻成原木，那么日志项就是木质材料。在Raft算法中，副本数据是以日志的形式存在的，领导者接收到来自客户端的写请求后，处理写请求的过程就是一个复制和应用(Apply)日志项到状态机的过程。那么Raft算法是如何复制日志，又是如何实现日志的一致的呢？这些内容是Raft算法中非常核心的内容

Raft是如何解决成员变更问题的。
在日常工作中，你可能会遇到服务器故障的情况，这时你需要替换集群中的服务器。如果遇到需要改变数据副本数的情况，则需要增加或移除集群中的服务器。总的来说，在日常工作中，集群中的服务器数量是会发生变化的。也许你会问，Raft算法是共识算法，它对集群成员进行变更时(比如增加2台服务器)，
会不会因为集群分裂出现两个领导者呢？在我看来，的确会出现这个问题，因为Raft算法的领导者选举是建立在"大多数"的基础之上，那么当成员变更，集群
成员发生变化时，就可能同时存在新旧配置的两个"大多数"，出现两个领导者，从而破坏了Raft集群的领导者唯一性，影响了集群的运行。
成员变更不仅是Raft算法中比较难理解也非常重要的一部分，而且是Raft算法中唯一被优化和改进的部分。比如，最初成员变更的是联合共识
(Joint Consensus)，但这个方法实现起来很难，后来Raft算法的作者就提出了一种改进后的方法，单节点变更(single-server change).

在分析之前，我们先介绍以下"配置"这个词。配置是成员变更中一个非常重要的概念，可以这样理解:配置用于说明集群由哪些节点组成，是集群各节点地址信息的集合。比如节点A、B、C组成的集群配置就是【A,B,C】集合。
假设有一个由节点A、B、C组成的Raft集群，现在我们需要增加数据副本数。即增加两个副本(也就是增加两台服务器)，扩展为由节点A、B、C、D、E这5个
节点组成的新集群，如图所示。那么在集群配置变更时，Raft算法是如何保障集群稳定运行，而不出现两个领导者呢？老话说的好，认识问题，才能解决问题。为了更好地理解单节点变更地方法，我们先来看一看成员变更时到底会出现什么样的问题

Raft与一致性。
有很多人把Raft算法当成一致性算法，其实它不是一致性算法而是共识算法，是一个Multi-Paxos算法，实现的是如何就一系列值达成共识。并且，Raft算法
能容忍少数节点的故障。虽然Raft算法能实现强一致性，也就是线性一致性(Linearizability)，但需要客户端协议的配合。在实际场景中，我们一般需要根据
场景特点，在一致性强度和实现复杂度之间进行权衡。比如Consul实现了3种一致性模型。
1.default:客户端访问领导者节点执行读操作，领导者确认自己处于稳定状态时(在leader leasing时间内)，返回本地数据给客户端，否则返回错误给客户端。
在这种情况下，客户端是可能读到旧数据的，比如此时发生了网络分区，新领导者已经更新过数据，但因为网络故障，旧领导者未更新数据也未退位，仍处于
稳定状态。
2.consistent:客户端访问领导者节点执行读操作，领导者在大多数节点确认自己仍是领导者之后返回本地数据给客户端，否则返回错误给客户端。在这种情况
下，客户端读到的都是最新数据。
3.stale:从任意节点读数据，不局限于领导者节点，客户端可能会读到旧数据。
一般而言，在实际工程种，使用Consul的consistent旧可以了，不用线性一致性，只要能保证写操作完成后，每次读都能读到最新值即可。比如为了实现幂等
操作，我们使用一个编号(ID)来唯一标记一个操作，并使用一个状态字段(nil/done)来标记操作是否已经执行，那么只要我们能保证设置了ID对应状态值为done后，能立即和一直读到最新状态值，旧可以防止操作的重复执行，实现幂等性。
总的来说，Raft算法能很好地处理绝大部分场景地一致性问题，推荐在设计分布式系统时，优先考虑Raft算法，当Raft算法不能满足现有场景需求时，再去调研其他共识算法。比如QQ后台地海量分布式系统，其中配置中心、名字服务以及时序数据库地META节点，采用Raft算法。在设计时序数据库的DATA节点一致性时，基于水平扩展、性能和数据完整性等考虑，就没采用Raft算法，而是采用了Quorum NWR、失败重传、反熵等机制。这样安排的好处是，不仅满足了业务的需求，还通过尽可能采用最终一致性方案的方式，实现系统的高性能，降低了成本。

注意。
Raft算法和兰伯特的Mutli-Paxos的不同之处有两点:
1.首先，在Raft算法中，不是所有节点都能当领导者，只有日志较完整地节点(也就是日志完整度不比半数节点低的节点)才能当选领导者
2.其次，在Raft算法中，日志必须是连续的

思维拓展。
Raft算法实现了"一切以我为准"的强领导者模型，那么这个设计有什么限制和局限呢？
领导者接收到大多数的"复制成功"响应后，就会将日志应用到自己的状态机，然后返回"成功"给客户端。如果此时有一个节点不在"大多数"中，也就是说它
接收日志项失败，那么Raft算法会如何实现日志的一致呢？

对于接收日志项失败的节点，Raft算法采用了以下机制来确保日志的一致性：

1.日志追赶（Log Compaction）：如果某个节点因为某些原因（如网络分区、节点故障等）没有接收到最新的日志项，当该节点重新加入集群并成为跟随者后，它会向领导者请求复制缺失的日志项。领导者会将缺失的日志项发送给该节点，使其能够追赶上最新的日志状态。
2.安全性检查：在复制缺失的日志项之前，领导者会首先检查该节点的日志是否与自己保持一致。如果发现不一致（例如该节点包含了一些领导者没有的日志项），领导者会拒绝复制请求，并告知该节点回滚到某个一致的日志位置后再重新请求复制。这样可以确保在复制过程中不会出现日志不一致的情况。
3.安全性保证：Raft算法通过保证“已提交的日志项不会被覆盖或删除”来确保日志的一致性。具体来说，如果一条日志项已经被标记为已提交，那么领导者在后续的日志复制过程中，就不会再覆盖或删除这条已提交的日志项。即使领导者节点出现故障并被新的领导者替换，新的领导者也会继续复制和提交之前的已提交日志项，以确保所有节点的日志保持一致

重点总结。
在了解了Raft算法的特点、领导者选举、什么是日志、如何复制日志以及如何处理不一致日志，还有成员变更的问题和单节点变更的方法等。希望大家能明确以下几个重点:
1.本质上，Raft算法以领导者为中心，选举出的领导者以"一切以我为准"的方式，达成值的共识和实现各节点日志的一直。
2.在Raft算法中，副本数据是以日志的形式存在的，其中日志项中的指令表示用户指定的数据。在Raft算法中日志必须是连续的，而兰伯特的Multi-Paxos不要求日志是连续的，而且在Raft算法中，日志不仅是数据的载体，日志的完整性还影响着领导者选举的结果。也就是说，日志完整性最高的节点才能当选领导者
3.单节点变更是利用"一次变更一个节点，不会同时存在旧配置和新配置两个'大多数'"的特性，实现成员变更。
在了解完Raft算法后，有人可能会有这样的疑问:强领导者模型会限制集群的写性能，有什么办法能突破Raft集群的写性能瓶颈呢？可以通过一致哈希算法来实现分集群。

概述。
有些人可能有这样的疑问:如果我们通过Raft算法实现了KV存储，虽然领导者模型简化了算法实现和共识协商，但写请求只能限制在领导者节点上处理，导致集群的接入性能约等于单机，随着业务发展，集群的性能可能就扛不住了，造成系统过载和服务不可用，这时该怎么办呢？
其实这是一个非常常见的问题。在我看来，这时我们就要通过分集群突破单集群的性能限制了。有人可能会说，分集群还不简单吗? 在模型中加入一个Proxyc层，由Proxy层处理来自客户端的读写请求，在接收到读写请求后，通过对Key做哈希找到对应的集群就可以了.
哈希算法的确是个办法，但它有个明显的缺点:当需要变更集群数时(比如从两个集群扩展为三个集群),大部分的数据都需要迁移，重新映射，而数据的迁移成本是非常高的，那么如何解决哈希算法数据迁移成本高的通电呢？答案就是使用一致哈希(Consistent Hashing)算法。
为了更好地理解如何通过哈希寻址实现KV存储地分集群，除了分析哈希算法寻址问题的本质之外，还会分析一致哈希是如何解决哈希算法数据迁移成本高这个痛点，以及如何实现数据访问的冷热相对均匀。你不仅能理解一致性哈希算法的原理，还能掌握通过一致哈希算法实现数访问冷热均匀的实战能力。

我们先来看一个思考题。
假设我们有一个由A、B、C3个节点组成(为了方便演示，使用节点来替代集群)的KV服务，每个节点存放不同的KV数据，如图所示.
使用哈希算法实现哈希寻址时到底有哪些问题呢？

使用哈希算法有什么问题。
通过哈希算法，每个key都可以寻址到对应的服务器，比如，查询key是key-01,计算公式为hash(key-01)%3,警告过计算寻址到了编号为1的服务器节点A，如图所示。但如果服务器数量发生变化，我们基于新的服务器数量来执行哈希算法时，就会出现路由寻址失败的秦广，导致Proxy无法找到之前寻址到的那个服务器节点，这是为什么呢？
想象以下，加入3个节点不能满足当前的业务虚要，这时我们增加了一个节点，节点数量从3变为4，那么之前的hash(key-01)%3=1就变成了
hash(key-01)%4=X,因为取模运算发生了变化，所以这个X大概率不是1(可能是2)，这时你再查询，就会找不到数据，因为key-01对应的数据存储再节点A上，而不是节点B上，如图所示。同样的道理，如果我们需要下线1个服务器节点(也就是缩容)，也会存在类似的问题。而解决这个问题的办法在于我们要迁移数据，基于新的计算公式hash(key-01)%4来重新对数据和节点做映射。需要注意的是，数据的迁移成本是非常高的。
为了便于理解，我们用一个示例来说明。对于1000万个key 的3节点KV存储，如果我们增加1个节点，即3节点集群变为4节点集群，则需要迁移75%的数据，如代码所示
```c
go run ./hash.go -keys 10000000 -nodes 3 -new-nodes 4
74.999980%
```
从示例代码的输出可以看到，迁移成本非常高昂，这在实际生产环境中也是无法想象的

如何使用一致哈希算法实现哈希寻址。
一致哈希算法也采用取模运算，但与哈希算法是对节点的数量进行取模不同，一致哈希算法是对2^32进行取模。你可以想象以下，一致哈希算法是将整个哈希空间组织成一个虚拟的圆环，也就是哈希换，如图所示，从图中可以看到，哈希环的空间是按顺时针方向组织的，圆环的正上方点的点代表0，0点右侧的第一个点代表1，以此类推，2、3、4、5、6.......知道2^32-1,也就是说0点左侧的第一个点代表2^32-1.在一致哈希算法中，你可以通过执行哈希算法(为了演示方便，假设哈希算法函数为c-hash())将节点映射到哈希环上，比如选择节点的主机名作为参数进行c-hash()函数运算，确定每个节点在哈希环上的位置，如图所示。当需要对指定的key的值进行读写的时候，你可以通过下面两步进行寻址:
1.首先，将key作为参数进行c-hash()函数运算，计算哈希值，并确定此key在环上的位置
2.然后，从这个位置沿着哈希环顺时针"行走"，遇到的第一节点就是key对应的节点
为了更好地理解如何通过一致哈希寻址，用一个示例来说明。假设key-01、key-02、key-03 3个key经过哈希算法c-hash()函数计算后，在哈希环上的位置如图所示。
那么根据一致哈希算法，key-01将寻址到节点A,key-02将寻址到节点B,key-03将寻址到节点C.你可能会问，那一致哈希是如何避免哈希算法的问题的呢？
假设现在有一个节点故障了(比如节点C),如图所示。
可以看到，key-01和key-02不会受到影响，而key-03得寻址将被重定位到A.一般来说，在一致哈希算法中，如果某个节点宕机不可用了，那么受影响的数据仅仅是会寻址到此节点和前一节点之间的数据。比如当节点C宕机时，受影响的数据是会寻址到节点B和节点C之间的数据(例如key-03)，而寻址到其他哈希环空间的数据(例如key-01)不会受到影响。如果此时集群不能满足业务的需求，则需要扩容一个节点(也就是增加一个节点，比如D),如图所示.
可以看到，key-01、key-02不会受到影响，而key-03的寻址被重定位到新节点D.一般而言，在一致哈希算法中，如果增加一个节点，受影响的数据仅仅是会寻址到新节点和前一节点之间的数据，其他数据则不会受到影响。
我们一起来看一个例子，对于1000万个key的3节点KV存储，如果我们使用一致哈希算法增加1个节点，即3节点集群变为4节点集群，则只需要迁移24.3%的数据,如代码所示

```c
go run ./consistent-hash.go -keys 10000000 -nodes 3 -new-nodes 4
24.301550%
```
你看，使用了一致哈希算法后，我们需要迁移的数据量仅为使用哈希算法时的三分之一，是不是大大提升了效率呢？
总的来说，使用一致哈希算法在扩容或缩容时，都只需要重定位环空间中的一小部分数据。也就是说，一致哈希算法具有较好的容错性和可扩展性。需要注意的是，在哈希寻址中常出现这样的问题:客户端访问请求集群在少数的节点上，导致有些机器高负载，有些机器低负载的情况。那么有什么办法能让数据访问分布得比较均匀呢？答案就是虚拟节点。
在一致哈希算法中，如果节点太少，则很容易因为节点分布不均匀造成数据访问的冷热不均，也就是说，大多数访问请求都会集中少量几个节点上，如图所示。从图中可以看到，虽然集群有3个节点，但访问请求主要集中在节点A上。那么如何通过虚拟节点解决冷热不均的问题呢？
其实，可以对每一个服务器节点计算多个哈希值，在每个计算结果位置上都放置一个虚拟节点，并将虚拟节点映射到实际节点。比如，在主机名的后面增加比那好，分别计算Node-A-01、Node-A-02、Node-B-01、Node-B-02、Node-C-01、Node-C-02的哈希值，形成6个虚拟节点，如图所示，可以从图中看到，增加了节点后，节点在哈希环上的分布就相对均匀了，这时，如果有访问请求寻址到Node-A-01这个虚拟节点，将被重定位到节点A。你看这样我们就解决了冷热不均匀的问题。可能有人已经发现了，节点数越多，使用哈希算法时需要迁移的数据就越多，而使用一致哈希算法时需要迁移的数据就越少，如代码清单所示
```c
go run ./hash.go -keys 10000000 -nodes 3 -new-nodes 4
74.999980%
go run ./hash.go -keys 10000000 -nodes 10 -new-nodes 11
90.909000%

go run ./consistent-hashgo.go -keys 10000000 -nodes 3 -new-nodes 4
24.301550%
go run ./consistent-hashgo.go -keys 10000000 -nodes 10 -new-nodes 11
6.479330%
```
从示例代码的输出中可以看到，当我们向10节点集群中增加节点时，如果使用哈希算法，则需要迁移高达90.91%的数据，如果使用一致哈希算法，则需要迁移6.48%的数据。
需要注意的是，使用一致哈希算法实现哈希寻址时，可以通过增加节点数来降低节点宕机对整个集群的影响，以及故障恢复时需要迁移的数据量。后续在需要时，你也可以通过增加节点数来提升系统的容灾能力和故障恢复效率。

Raft集群具有容错能力，能容忍少数的节点故障，那么在多个Raft集群组成的KV系统中，如何设计一致哈希算法，以实现当某个集群的领导者节点出现故障并选举出新的领导者后，整个系统还能稳定运行呢？
在多个Raft集群组成的KV系统中，设计一致哈希算法以实现领导者节点故障后系统的稳定运行，需要确保在领导者节点变更时，数据的一致性和服务的连续性。以下是一些建议的步骤和考虑因素：

1.虚拟节点和环形哈希空间：
一致哈希算法通过引入虚拟节点和环形哈希空间，实现了节点动态扩缩容时数据迁移的最小化。在Raft集群组成的KV系统中，每个Raft集群可以视为一个物理节点，并在其上创建多个虚拟节点。
虚拟节点能够平滑地将数据分布到多个物理节点上，减少单个物理节点故障对系统的影响。
2.领导者故障检测与恢复：
当某个Raft集群的领导者节点出现故障时，该集群内部会通过Raft的领导者选举机制选举出新的领导者。
KV系统需要监控Raft集群的状态，并在检测到领导者节点故障时，更新其内部的一致哈希映射，确保新的领导者节点能够接管服务。
3.数据同步与一致性：
在领导者节点故障期间，可能会有一些数据尚未同步到新的领导者节点。因此，在选举出新的领导者后，需要确保数据的同步和一致性。
这可以通过Raft的日志复制机制来实现。新的领导者节点可以从其他跟随者节点那里拉取缺失的日志条目，并应用到状态机中以更新系统状态。
4.路由与负载均衡：
一致哈希算法通过计算键的哈希值，并将其映射到环形哈希空间上的某个虚拟节点，从而确定数据的存储位置。
在多个Raft集群组成的KV系统中，需要设计一种路由机制，使得客户端能够根据键的哈希值将数据路由到正确的Raft集群和虚拟节点上。
同时，还需要考虑负载均衡的问题，确保各个Raft集群之间的负载相对均衡。
5.故障恢复与容错性：
在设计系统时，需要考虑各种可能的故障场景，并制定相应的故障恢复策略。
例如，当某个Raft集群完全故障时，系统需要能够自动将其从一致哈希映射中移除，并将该集群上的数据迁移到其他健康的集群上。
此外，还需要考虑如何在不影响系统稳定性的前提下，对系统进行扩容和缩容。
6.测试与验证：
在实际部署之前，需要对系统进行充分的测试和验证，以确保其能够在各种故障场景下稳定运行。
这包括单元测试、集成测试、压力测试等不同类型的测试。
综上所述，设计一致哈希算法以实现多个Raft集群组成的KV系统的稳定运行，需要综合考虑虚拟节点、领导者故障检测与恢复、数据同步与一致性、路由与负载均衡、故障恢复与容错性以及测试与验证等多个方面。

重点总结。
1.一致哈希算法是一种特殊的哈希算法，该算法可以使节点增减变化时只影响到部分数据的路由寻址，也就是说我们只要迁移部分数据，就能实现集群的稳定了。
2.当节点数较少时，可能会出现节点在哈希环上分布不均匀的情况，即每个节点实际在环上占据的区间大小不一，最终导致业务对节点的访问冷热不均，而这个问题可以通过引入更多的虚拟节点来解决。
3.一致哈希算法本质上是一种路由寻址算法，适合简单的路由寻址场景，比如，在KV存储系统内部，它的特点是简单，不需要维护路由信息

有人可能会有这样的疑问:关于Raft算法的原理以及一致哈希算法如何突破集群"领导者"的限制，但是有的公司的配置中心、名字路由等使用的是ZooKeeper，那么ZAB协议是如何实现一致性的呢？ZAB协议和Raft算法又有什么不一样呢？

概述。
很多人应该都使用过ZooKeeper， 它是一个开源的分布式协调服务，比如你可以用它进行配置管理、名字服务等。在ZooKeeper中，数据是以节点的形式存储的。如果你要用ZooKeeper做配置管理，那么就需要在里面创建指定配置，假设创建节点/geekbang和/geekbang/time,步骤如代码所示:
```c
[zk: localhost:2181(CONNECTED) 0] create /geekbang 123
Created /geekbang
[zk: localhost:2181(CONNECTED) 1] create /geekbang/time 456
Created /geekbang/time
```
我们分别创建了配置节点/geekbang和/geekbang/time,对应的值分别为123和456.那么在这里提个问题:你觉得在ZooKeeper中能用兰伯特的Multi-Paxos实现各节点数据的公式一致吗？
当然不行。因为兰伯特的Multi-Paxos虽然能保证达成共识后的值不再改变，但它并不关心达成共识的值是什么，也无法保证各值(也就是操作)的顺序性。而这时ZAB协议着力解决的，也是你理解ZAB协议的关键。
为了更好地理解这个协议，接下来将分别以如何实现操作的顺序性、领导者选举、故障恢复、处理读写请求为例展开具体讲解。希望能在全面理解ZAB协议的同时，加深对Paxos算法的理解，接下来，我们从ZAB协议的最核心设计目标(如何实现操作的顺序型)出发，了解它的基础原理。
老规矩，我们先来看一道思考题。
假如有一个由节点A、B、C组成的分布式集群(如图所示)，我们要设计一个算法来保证指令(比如X、Y)执行的顺序型，比如指令X在指令Y之前执行，那么我们该如何设计这个算法呢？

如何实现操作的顺序性？
在了解如何实现操作的顺序性之前，我们先来了解下为什么Multi-Paxos无法保证操作的顺序性。

主节点崩溃了，怎么办？
众所周知，系统在运行中不可避免会出现各种各样的问题，比如进程崩溃了、服务器死机了，这些问题会导致很严重的后果，让系统没办法继续运行。在ZAB协议中，写请求是必须在主节点上处理的，而且提案的广播和提交也是由主节点来完成的。既然主节点那么重要，如果它突然崩溃(宕机)了，该怎么办呢？
答案是选举出新的领导者(也就是新的主节点)。
在我看来，领导者选举关乎节点故障容错能力和集群可用性，是ZAB协议非常核心的设计之一。想象一下，如果没有领导者选举，主节点故障了，那么整个集群将无法写入，这将是极其严重的灾难性故障。理解领导者选举(也就是快速领导者选举，Fast Leader Election)，能帮助我们更深刻地理解ZAB协议，也能在日常工作中更游刃有余地处理集群的可用性问题。比如写请求持续失败时，可以先排查下集群的节点状态。
既然领导者选举这么重要，那么ZAB协议是如何选举领导者的呢？

如何从故障中恢复。
在前面我们提到了ZAB协议的领导者选举，在我看来，它只是选举了一个适合当领导者的节点，然后把这个节点的状态设置成LEAEDING状态。此时，这个节点还不能作为主节点处理写请求，也不能使用领导职能(比如，它没办法阻止其他"领导者"广播提案)。也就是说，集群还没有从故障中恢复过来，而成员发现和数据同步会解决这个问题。
总的来说，成员发现和数据不同不仅让新领导者正式成为领导者，确立了它的领导关系，还解决了个副本数据冲突的问题，实现了数据副本的一致性，使集群能够正常处理写请求，这里需要注意的是：
1.确立领导关系是指在成员发现(DISCOVERY)阶段，领导者和大多数跟随者建立连接，并再次确认各节点对自己当选领导者没有异议，从而确立自己的领导关系
2.处理冲突数据是指在数据同步(SYNCHRONIZATION)阶段，领导者以自己的数据为准，解决各节点数据副本不一致的问题。
理解这两点，有助于更好地理解ZooKeeper如何恢复故障，以及当主节点崩溃时，哪些数据会丢失、哪些数据不会丢失的原因等。换句话说，通过上述内容，我们能更好地理解ZooKeeper的节点故障容错能力

ZAB协议:如何处理读写请求。
你应该有这样的体会，如果你想了解一个网络服务，执行的第一个功能肯定是写操作，然后才会执行读操作。比如，你要了解ZooKeeper，那么肯定会在zkClient.sh命令行中执行写操作(比如create /geekbang 123)写入数据，然后再执行读操作(比如get /geekbang)查询数据。这样一来，你才会直观地理解ZooKeeper的使用方法。

在我看来，任何网络服务最重要的功能就是处理读写请求，因为我们访问网络服务的本质就是执行读写操作，ZooKeeper也不例外，对ZooKeeper而言，这些功能更重要，因为如何处理写请求关乎着操作的顺序性，会影响节点的创建；而如何处理读请求关乎着一致性，也影响着客户端是否会读到旧数据。

接下来，会从ZooKeeper系统的角度全面地分析整个读写请求的流程，帮助你更加全面、透彻地理解读写请求背后的原理。
我们都知道，在ZooKeeper中，写请求必须在领导者上处理，如果跟随者接收到写请求，则需要将写请求转发给领导者，当写请求对应的提案被复制到大多数节点上时，领导者会提交提案，并通知跟随者提交提案。而读请求可以在任何节点上处理，也就是说，ZooKeeper实现的是最终一致性。

所以，理解了如何处理读写请求，不仅能理解读写这个最重要功能的核心原理，还能更好地理解ZooKeeper的性能和一致性。这样在实际场景中安装部署ZooKeeper的时候，就能游刃有余地做资源规划了。比如，如果度请求比较多，可以增加节点，如配置5节点集群，而不是常见的3节点集群。

ZAB协议与Raft算法。
在我看来，ZAB协议和Raft算法很类似，比如主备模式(也即领导者、跟随者模型)、日志必须是连续的、以领导者的日志为准来实现日志一致等。为什么它们比较类似呢？
我的看法是，"英雄所见略同"。比如ZAB协议要实现操作的顺序性，而Raft算法不仅要实现操作的顺序性，还要实现线性一致性，这两个目标决定了它们不能允许日志不连续，且必须按照顺序提交日志，素以，它们要通过上面的方法实现日志的顺序性，并保证达成共识(即提交后的日志不会再改变)。

最后，就ZAB协议和Raft算法做个对比，来具体说说二者的异同。既然要做对比，那么首先要定义对比标准，我们可以这么考虑:你应该有这样的体会，同一个功能，不同的人实现的代码会不一样(比如数据结构、代码逻辑)，所以过于细节的比较，尤其是偏系统实现方面的比较，意义不大(比如比较跟随者是否转发写请求到领导者，不仅意义不大，而且这是ZAB协议和Raft算法都没有约定的，是集群系统需要考虑的)。我们可以从核心原理上做对比。
1.领导者选举:ZAB协议采用的是"见贤思齐、相互推荐"的快速领导者选举(Fast Leader Election)算法，Raft算法采用的是"一张选票、先到先得"的自定义算法。在我看来，Raft算法的领导者选举需要通信的消息数更少、选举也更快
2.日志复制:Raft算法和ZAB协议都是以领导者的日志为准来实现日志一致，而且日志必须是连续的，也必须按照顺序提交
3.读操作和一致性:ZAB协议的设计目标是操作的顺序性，在ZooKeeper中默认实现的是最终一致性，读操作可以在任何节点上执行，而Raft算法的设计目标是强一致性(也就是线性一致性)，所以Raft算法更灵活，它既可以提供强一致性，也可以提供最终一致性
4.写操作:Raft算法和ZAB协议的写操作都必须在领导者节点上处理
5.成员变更:Raft算法和ZAB协议都支持成员变更(其中ZAB协议是以动态配置的方式实现的)，所以在节点变更时，你不需要重启及其，因为集群是一直运行的，服务也不会中断。
6.其他:相比ZAB协议，Raft算法的设计更为简洁，比如Raft算法没有引入类似ZAB协议的成员发现和数据同步阶段，而是当节点发起选举时递增任期编号，在选举结束后广播心跳，直接建立领导关系，然后向各节点同步日志，来实现数据副本的一致性。在我看来，ZAB协议的成员发现可以和领导者选举合到一起，类似Raft算法，在领导者选举结束后直接建立领导者关系，而不是再引入一个新的阶段；数据同步阶段是一个冗余的设计，可以去除。因为ZAB协议无须先实现数据副本的一致性，才可以处理写请求，而且这个设计是没有额外的意义和价值的。
7.另外，ZAB协议与ZooKeeper强耦合，无法在实际系统中独立使用；而Raft算法的实现(比如Hashicorp Raft算法)是可以独立使用的，编程友好

重点总结:
1.ZAB协议是通过"一切以领导者为准"的强领导者模型和严格按照顺序处理、提交提案来实现操作的顺序性的
2.领导者选举的目标是选举出大多数节点中数据最完整的节点，也就是大多数节点中事务标识符值最大的节点。任期编号、事务标识符、集群ID的值的大小决定了哪个节点更适合作为领导者，按照顺序，值最大的节点更适合作为领导者
3.数据同步是通过以领导者的数据为准的方式来实现各节点数据副本的一致性的。需要注意的是，基于"大多数"的提交原则和选举原则能确保被复制到大多数节点并提交的提案不再改变
4.在ZooKeeper中，写请求只能在领导者节点上处理，读请求可以在所有节点上处理，即ZooKeeper实现的是最终一致性。而与领导者"失联"的跟随者(比如发生分区故障时)既不能处理写请求、也不能处理读请求。

你可能会问Paxos算法、Raft算法也都有领导者，难道实现一致性就必须要领导者吗？没有领导者就无法实现一致性吗？其实有些没有领导者的算法也能实现一致性

概述。
有些人的业务需求具有一定的敏感性，比如监控主机和业务运行的告警系统，大家都希望自己的系统在极端情况下(比如集群中只有一个节点在运行)也能运行。在会以了二阶段提交协议和Raft算法之后，你会发现它们都需要全部节点或者大多数节点正常运行才能稳定运行，并不适合此类场景。而如果采用Base理论，则需要实现最终一致性，那么，怎样才能实现最终一致性呢？
在我看来，可以通过Gossip协议来实现这个目标。
Gossip协议，顾名思义，就像流言蜚语一样，是指利用一种随机、带有传染性的方式将信息传播到整个网络中，并在一定时间内使得系统内的所有节点数据一致。掌握这个协议不仅能帮助我们很好地理解这种最常用的、实现最终一致性的算法，也能让我们在后续工作中得心应手地实现数据的最终一致性。

Gossip的三板斧。
Gossip的三板斧分别是直接邮寄(Direct Mail)、反熵(Anti-entropy)和谣言传播(Rumor Mongering)。

如何使用反熵实现最终一致性。
在分布式存储系统中，实现数据副本最终一致性的最常用的方法是反熵。为了帮助我们沉底理解和掌握在实际环境中实现反熵的方法，以InfluxDB的反熵实现为例具体分析一下。
在InfluxDB中，一份数据副本是由多个分片组成的，也就是实现了数据分片。3节点3副本的InfluxDB集群如图所示。
反熵的目标是确保每个DATA节点拥有元信息指定的分片，而且在不同节点上，同一分片组中的分片都没有差异。比如，节点A要拥有分片Shard1和Shard2，而且节点A的Shard1和Shard2与节点B、C中的Shard1和Shard2是一样的。那么，DATA节点熵存在哪些数据缺失的情况呢？换句话说，我们需要解决哪些问题呢？

我们将数据缺失分为这样两种情况。
1.缺失分片:某个节点上的整个分片都丢失了
2.节点之间的分片不一致:节点上的分片都存在，但里面的数据不一样，有数据丢失的情况发生。
第一种情况修复起来很简单，我们只需要通过RPC通信将分片数据从其他节点上复制过来就可以了，如图所示
第二种情况修复起来要复杂一些，我们需要设计一个闭环流程，按照一定的顺序来修复，这样执行完整个流程后也就实现了一致性。具体要怎样设计呢？
它是按照一定顺序来修复节点的数据差异，先随机选择一个节点，该节点生成自己节点有而下一个节点没有的差异数据，并发送给下一个节点，修复下一个节点的数据缺失，然后按照顺序，各节点循环修复，如图所示，从图中可以看到，数据修复的起始节点为节点A,数据修复是按照顺时针顺序循环进行。需要注意的是，最后节点A又对节点B的数据执行了一次数据修复，因为只有这样，节点C、节点B缺失的差异数据才会同步到节点B上。

看到这里，在实现反熵时，实现细节和最初算法的约定有些不同。比如，不是一个节点不断随机选择另一个节点来修复副本上的熵，而是设计了一个闭环的流程，一次修复所有的副本数据不一致问题。
为什么这样设计呢？因为我们希望能在一个确定的时间范围内实现数据副本的最终一致性，而不是基于随机性的概率，在一个不确定的时间范围内实现数据副本的最终一致性。这样做能减少数据不一致对监控试图影响的时长。但是，需要注意的是，技术是要活学活用的，我们要能根据场景特点权衡妥协，设计出最适合这个场景的系统功能。最后需要注意的是，因为反熵需要做一致性对比，很消耗系统资源，所以建议将是否启用反熵功能、执行一致性检测的时间间隔等做成可配置的，以方便在不同场景中按需使用

思维拓展。
既然使用反熵实现最终一致性时需要通过一致性检测发现数据副本的差异，如果每次做一致性检测时都要做数据对比，必然会消耗一部分资源，那么，有什么办法可以降低一致性检测时的性能损失呢？
答案是:我们期望最好的做法是花费更少的时间、花费更少的通信资源，如果我们将每个节点上的数据都进行传输，必然会消耗很多网络资源，反过来，如果我们将每条数据都进行传输，也会很消耗时间，所以使用对数据进行Hash计算，将得到的hash值进行比对，这样就无须再逐个进行比对，我们只要保证，同一数据源可以得到同一个Hash值，而且一个hash值所占用的网络资源也是相当少的

重点总结。
1.Gossip协议作为一种异步修复、实现最终一致性的协议，反熵再存储组件中应用广泛，比如Dynamo、InfluxDB、Cassandra，在需要实现最终一致性的实际工作场景中，优先考虑反熵
2.因为谣言传播具有传染性，如一个节点传给了另一个节点，另一个节点又将充当传播者，传给其他节点，所以非常适合动态比那花的分布式系统，比如Cassandra
3.一般而言，在实际场景中实现数据副本的最终一致性时，直接邮寄的方式是一定要实现的，因为不需要做一致性对比，只需要通过发送更细年数据或重传缓存来修复数据，新跟那个损耗低。在存储组件中，节点都是已知的，一般采用反熵修复数据副本的一致性。当集群节点是变化的，或者集群节点数比较多时，这时要采用谣言传播的方式更新数据，实现最终一致性。

如果我们在实际场景中涉及了一套AP型分布式系统，并通过反熵实现了各数据副本的最终一致性，且系统也在线上稳定地运行着，此时突然有同时提出希望数据写入成功后，能立即读取到新数据需求，也就是要实现强一致性，这时我们该怎么呢？难道我们必须推倒架构，一切从头再来？

概述。
不知道你在工作中有没有遇到过这样的事情:你开发实现了一套AP型分布式系统，实现了最终一致性，且业务接入后运行正常，一切看起来都那么美好。
可是突然有同事说，我们要拉这几个业务的数据做实时分析，希望数据写入成功后，就能立即读取到新数据，也就是要实现强一致性(Werner Vogels提出的客户端侧一致性模型，不是指线性一致性)，即数据更改后，要保证用户能立即查询到，这时你该怎么办呢？首先你要明确最终一致性和强一致性有什么区别.
1.强一致性能保证写操作完成后，任何后续访问都能读到更新后的值。
2.最终一致性只能保证如果对某个对象没有新的写操作了，最终所有后续访问都能读到相同的最近更新的值。也就是说，写操作完成后，后续访问可能会读到旧数据。

其实，为了一个临时的需求而重新开发一套系统或者迁移数据到新系统肯定是不合适的。因为工作量比较大，而且耗时也长，所以建议通过Quorum NWR算法解决这个问题。
通过Quorum NWR算法，我们可以自定义一致性级别，通过临时调整写入或者查询的方式满足新需求，当W+R>N时，就可以实现强一致性了。也就是说，在原有系统上开发并实现一个新功能，即可满足业务同事的需求。
其实，在AP型分布式系统中(如Dynamo、Cassandra、InfluxDB企业版的DATA节点集群)，Quorum NWR算法时通常都会实现的一个功能，很常用。掌握了Quorum NWR算法，不仅可以掌握一种常用的、实现一致性的方法，而且可以在后续的实际场景中根据业务的特点，灵活地指定一致性级别。

Quorum NWR的三要素。
N表示副本数，又叫作复制因子(Replication Factor)。也就是说，N表示集群中同一份数据有多少个副本，如图所示，从图中可以看到，在这个3节点集群中，DATA-1有2个副本，DATA-2有3个副本，DATA-3有1个副本。也就是说，副本数可以不等于节点数，不同的数据可以有不同的副本数。
需要注意的是，在实现Quorum NWR算法的时候，你需要实现自定义副本的功能。也就是说，用户可以自定义指定数据的副本数，比如，用户可以指定DATA-1具有2个副本，DATA-2具有3个副本。
当指定了副本后，我们就可以对副本数据进行读写操作了。但是，这么多副本，你要如何执行读写操作呢？先来看一看写操作，也就是W.

W，又称写一致性级别(Write Consistency Level)，表示成功完成W个副本更新才能完成写操作，如图所示。
从图中可以看到，DATA-2的写副本数为2，也就是说，对DATA-2执行写操作是，只有完成了2个副本的更新(比如节点A、C)才完成写操作。
有的人可能会问，DATA-2有3个数据副本，如果完成了2个副本的更新就表示完成了写操作，那么如何实现强一致性呢？如果客户端读到第3个数据副本(比如节点B)，不就可能无法读到更新后的值了吗？

R,又称读一致性级别(Read Consistency Level)，表示读取一个数据对象时需要读取R个副本。也可以这么理解，读取指定数据时要读取R个副本，然后返回R个副本中最新的那份数据，如图所示。从图中可以看到，DATA-2的读副本数为2，也就是说，客户端读取DATA-2的数据时，需要读取2个副本中的数据，然后返回最新的那份数据。

这里需要注意的是，无论客户端如何执行读操作，哪怕它访问的是写操作未强制更新副本数据的节点(比如节点B)，但因为W(2) + R(2) > N(3),也就是说，访问节点B执行读操作时，因为要读2份数据副本，所以除了节点B上的DATA-2,还会读取节点A或节点C上的DATA-2，如上图所示(比如节点C上的DATA-2),而节点A和节点C的DATA-2数据副本是强制更新成功的，所以返回给客户端的数据肯定是最新的那份数据。
你看，通过设置R为2，即是读到前面问题中的第3份副本数据(比如节点B)，也能返回更新后的那份数据，实现强一致性。

除此之外，关于Quorum NWR算法，我们还需要注意的是，N、W、R的值的不同组合会产生不同的一致性效果，具体来说，不同组合会产生如下两种效果。
1.当W+R>N的时候，对于客户端来说，整个系统能保证强一致性，即一定能返回更新后的那份数据
2.当W+R ≤ N的时候，对于客户端来说，整个系统只能保证最终一致性，即可能会返回旧数据。

如何实现Quorum NWR.
在InfluxDB企业版中，我们可以在创建保留策略时设置指定数据库对应的副本数，如代码所示
```c
create retention policy "rp_one_day" on "telegraf" duration 1d replication 3
```
在上述代码中，我们通过replication参数指定了数据库telegraf对应的副本数为3。需要注意的时，在InfluxDB企业版中，副本数不能超过节点数据。你可以这样理解，多副本的意义在于冗余备份，如果副本数超过节点数，就意味着一个节点上会存在多个副本，那么这时冗余备份的意义就不大了。比如机器故障时，节点上的多个副本是同时被影响的。

InfluxDB企业版支持"Any、One、Quorum、All"4种写一致性级别，具体含义分析如下:
1.Any:任何一个节点写入成功后，或者接收节点已将数据写入Hinted-handoff缓存(也就是写其他节点失败后，本地节点上缓存写失败数据的队列)后，就会返回成功给客户端
2.One:任何一个节点写入成功后，就会立即返回成功给客户端，不包括成功写入Hinted-handoff缓存
3.Quorum:当大多数节点写入成功后，就会返回给客户端。此选项仅在副本数大于2时才有意义，否则等效于All
4.All:仅在所有节点都写入成功后，返回成功
强调一下,对时序数据库而言，读操作会拉取大量数据，其查询性能是挑战，是必须要考虑优化的。因此，InfluxDB企业版不支持读一致性级别，只支持写一致性级别。另外，我们还可以设置写一致性级别为All，来实现强一致性。
如果我们像InfluxDB企业版这样实现了Quorum NWR算法，那么在业务临时需要实现强一致性时，就可以通过设置写一致性级别为All来实现了

思维拓展。
在实现Quorum NWR算法时，需要实现自定义副本的能力，那么一般需要设置几个副本呢？为什么呢？

重点总结。
1.一般而言，不推荐副本数超过当前的节点数，因为当副本数超过节点数时，就会出现同一个节点存在多个副本的情况。当这个节点有故障时，上面的多个副本就都会收到影响
2.当W+R>N时，可以实现强一致性。另外，如何设置N、W、R值，取决于我们想优化哪方面的性能。比如,N决定了副本的冗余备份能力；如果设置W=N,则读性能较好;如果设置R=N，则写性能比较好；如果设置W=(N+1)/2、 R=(N+1)/2，则容错能力比较好，能容忍少数节点[也就是(N-1)/2]的故障。

最后，Quorum NWR算法是一种非常使用的算法，能有效地弥补AP型系统缺乏强一致性的通电，给业务提供了按需选择一致性级别的灵活度。建议子啊开发实现AP型系统时也采用Quorum NWR算法。另外，我们在实际开发种，除了需要考虑数据访问的一致性，还需要考虑系统状态的一致性，也即实现事务，那么如何在分布式系统中实现事务呢？

概述。
相信很多人都知道MySQL支持单机事务，那么在分布式系统中，涉及多个节点，MySQL又是怎样实现分布式事务的呢？
举个例子，一个业务系统需要接收来自外部的指令，然后访问多个内部其他系统来执行指令，但执行完指令后，需要同时更新多个内部MySQL数据库中的值(比如MySQL数据库A、B、C).由于业务敏感，所以系统必须处于一个一致性状态(也就是说，MySQL数据库A、B、C中的值要么同时更新成功，要么全部不更新)，否则会出现有的系统显示指令执行成功，而有的系统显示指令尚未被执行的情况，导致多部门对指令执行结果理解混乱。
那么如何实现多个MySQL数据库更新的一致性呢？答案就是采用MySQL XA.

在我看来，MySQL通过支持XA规范的二阶段提交协议，不仅实现了多个MySQL数据库操作的事务，还能实现MySQL、Oracle、SQL Server等支持XA规范的数据库操作的事务。
通常，理解MySQL XA,不仅要能理解数据层分布式事务的原理，还要能在实际系统中更加深刻地理解二阶段提交协议，这样当你在实际工作中遇到多个MySQL数据库的事务需求时，你就知道如何通过MySQL XA来处理了。

老规矩，咱们先来看一道思考题。
假设有两个MySQL数据A、B(位于不同的服务器节点上),我们需要实现多个数据库更新(比如，UPDATE executed_table SET status=true WHERE id = 100)和插入操作(比如，INSERT INTO operation_table SET id = 100,op='get-cdn-log')的事务，如图所示，那么在MySQL中如何实现呢？
MySQL是通过XA规范实现分布式事务的，所以我们有必要先来了解一下XA规范

什么是XA规范。
提到XA规范，就不得不说DTP(Distributed Transaction Processing, 分布式事务处理)模型，因为XA规范约定的是DTP模型中的两个模块(事务管理其和资源管理器)的通信方式，如图所示。

为了更好地理解DTP模型,我来解释下DTP各模块的作用。
1.AP:应用程序(Application Program)，一般是指事务的发起者(比如数据库客户端或者访问数据库的程序)，定义事务对应的操作(比如更新操作
UPDATE executed_table SET status = true WHERE id = 100)
2.RM:资源管理器(Resource Manager),管理共享资源，并提供访问接口外部程序来访问共享资源,比如数据库。RM还应该具有事务提交或回滚的能力
3.TM:事务管理器(Transaction Manager),一般指分布式事务的协调者。TM与每个RM进行通信，协调并完成事务的处理。

你是不是觉得这个模型看起来很复杂?其实在我看来，你可以这样理解DTP模型:应用程序访问、使用资源管器的资源，并通过事务管理器的事务接口(TX interface)定义需要执行的事务操作，然后事务管理器和资源管理器会基于XA规范执行二阶段提交协议。

那么XA规范是什么呢？它约定了事务管理器和资源管理器之间双向通信的接口规范，并实现了二阶段提交协议，如图所示。
为了更好地理解这个过程，我们一起走一遍实现流程，以加深印象:
1.AP(应用程序)联系TM(事务管理器)发起全局事务
2.TM调用xa_open()建立与资源管理器的会话
3.TM调用xa_start()标记事务分支(Transaction Branch)的开头
4.AP访问RM(资源管理器)并定义具体事务分值的操作，比如更新一条数据记录(UPDATE executed_table SET status=true WHERE id = 100)和插入一条数据记录(INSERT INTO operation_table SET id =100, op='get-cdb-log');
5.TM调用xa_end()标记事务分支的结尾
6.TM调用xa_prepare()通知RM做好事务分支提交的准备工作，比如锁定相关资源，也就是执行二阶段提交协议的提交执行阶段
7.TM调用xa_commit()通知RM提交事务分支(xa_rollback()通知RM回滚事务)，也就是执行二阶段提交协议的提交执行阶段
8.TM调用xa_close()关闭与RM的会话。
整个过程也许有些复杂，不过你可以这样理解xa_start()和xa_end()在准备和标记事务分支的内容,然后调用xa_prepare()和xa_commit()(或者xa_rollback())执行二阶段提交协议，实现操作的原子性。注意，这些接口需要按照一定顺序执行，比如xa_start()必须在xa_end()之前执行。
另外，事务管理器对资源管理器调用的xa_start()和xa_end()这对组合，一般用于标记事务分支(就像上面的更新一条数据记录和插入一条数据记录)的开头和结尾。需要注意的是:
1.对于同一个资源管理器，根据全局事务的要求，可以前后执行多个操作组合，比如，先标记一个插入操作，再标记一个更新操作；
2.事务管理器只是标记事务，并不执行事务，最终是由应用程序通知资源管理器来执行事务操作的。

另外，XA规范还约定了如何向事务管理器注册和取消资源管理器的API接口(也就是ax_reg()和ax_unreg()接口)。这里需要注意的是，这两个接口是以ax_开头的，而不是像xa_start()那样以xa_开头,我们该如何通过MySQL XA实现分布式事务呢？

如何通过MySQL XA实现分布式事务。
首先，你需要创建一个唯一的事务id(比如xid)来唯一标识事务，并调用XA START和XA END来定义事务分支对应的操作(比如
INSERT INTO operation_table SET id = 100, op = 'get-cdn-log')，如图所示。
接着，你需要调用XA PREPARE来执行二阶段提交协议的提交请求阶段，如图所示
最后，你需要调用XA COMMIT 来提交事务(或者第哦啊用XA ROLLBACK来回滚事务)，如图所示，至此，你就实现了全局事务的一致性
从上图所示的流程中可以看到，客户端在扮演事务管理器的角色，而MySQL数据库在扮演资源管理器的角色。但是这压力需要注意，上面流程中的xid必须是唯一值。
另外补充的是，如果你要开启MySQL的XA功能，则必须设置存储引擎为InnoDB，也就是说，在MySQL中，只有InnoDB引擎支持XA规范。d当然，可能有些人对MySQL XA有这样的疑问，能否将XA END和XA PREPARE合并到一起呢？答案是不能，因为在XA END之后，我们是可以直接执行XA COMMIT命令的，也就是一阶段提交(比如当共享资源变更只涉及一个RM时)。最后，我强调一下，MySQL XA性能不高，适合在并发性能要求不高的场景中使用，而我之所以需要采用MySQL XA实现分布式事务，是因为整个系统对并发性能要求不高，而且底层架构是多个第三方的，没办法改造。

注意。
XA规范保证了全局事务的一致性，实现成本较低，而且得到了包括MySQL在内的主流数据库的支持。但是因为XA规范是基于二阶段提交协议实现的，所以它也存在二阶段提交协议的局限，列举如下:
1.首先，XA规范存在单点问题，也就是说，因为事务管理器在整个流程中扮演的角色很关键，如果其宕机，比如第一阶段已经完成了，在第二阶段正准备提交的时候，事务管理器宕机了，那么相关的资源会被锁定，无法访问。
2.其次，XA规范存在资源锁定的问题，也就是说，在进入准备阶段后，资源管理器中的资源将处于锁定状态，知道提交完成或者回滚完成才能解锁

思维拓展。
虽然MySQL XA能解决数据库操作的一致性问题，但它的性能不高，适用于对并发性能要求不高的场景。那么，在MySQL XA不能满足并发需求是，我们应该如何重新涉及底层数据系统，来避免采用分布式事务呢？为什么呢？
当MySQL XA(即MySQL的分布式事务支持)无法满足并发性能需求时，可以考虑一下集中方法来重新设计底层数据系统，
以避免使用分布式事务并提高性能：
1.业务逻辑分解
1.1.将复杂的分布式事务分解为多个小的事务，每个事务在单个数据库上执行。通常在业务逻辑层面保证一致性，
可以避免使用分布式事务
1.2 使用最终一致性模型，如通过事件队列、发布/订阅机制等异步处理数据一致性问题
2.数据分区。
2.1.将数据水平分区到不同的数据库实例中，减少每个数据库实例上的并发访问压力
2.2.通过分库分表来提高单个数据库实例的性能
3.服务拆分
3.1 采用微服务架构，将系统拆分为多个小的、松耦合的服务，每个服务对应一个数据库实例，从而减少分布式事务的使用
3.2 各服务之间通过异步消息或者补偿事务来维持数据的一致性
4.缓存机制
4.1 使用缓存(如Redis)来减少对数据库的读写压力，提高并发性能
4.2 通过缓存来处理读多写少的场景，减少对数据库的访问
5.读写分离
5.1 实施读写分离，将数据库的读操作和写操作分离到不同的数据库实例，以提高并发读取性能
5.2 写操作仍然保证事务性，而读操作可以不参与事务，从而提高整体性能
6.使用NoSQL数据库
6.1 对于不需要强一致性的部分，可以考虑使用NoSQL数据库，如MongoDB、Cassandra等，它们通常提供更高的并发性能
7.业务流程优化
7.1 优化业务流程，减少事务性操作的一来。例如，通过业务上的妥协，允许一定程度的最终一致性
8.性能优化
8.1 对现有数据库进行性能优化，包括但不限于索引优化、查询优化、硬件升级等
9.避免长事务
9.1 长事务会占用大量资源并可能导致锁定问题，通过涉及更短的事务来减少对系统资源的占用
10. 分布式数据库
10.1 考虑使用分布式数据库系统，如Google Spanner 、CockroachDB等，它们在涉及时就考虑了分布式事务的性能

避免使用分布式事务的原因主要包括:
1.性能开销:分布式事务通常涉及多个节点，需要额外的通信和协调，这回增加延迟并降低性能
2.复杂性:分布式事务的管理和调试更加复杂，可能导致难以追踪的问题
3.可用性问题:在分布式系统中，任何节点的故障都可能影响到整个事务，降低了系统的可用性。
因此，在涉及底层数据系统时，应根据业务需求和系统特点，选择合适的策略来避免分布式事务，同时确保系统的高性能和高可用性

重点总结。
1.XA规范是个标准的规范，也就是说，无论是否相同的数据库，只要这些数据库(比如MySQL、Oracle、SQL Server)支持XA规范，那么它们就能实现分布式事务，也就是能保证全局事务的一致性
2.相比商业数据库对XA规范的支持，MySQL XA性能不高，所以，我不推荐在高并发的性能至上的场景中使用MySQL XA.
3.在实际开发中，为了降低单点压力，我们通常会根据业务情况进行分库分表，即将表分布在不同的库中，那么在这种情况下，如果后续需要保证全局事务的一致性，则也需要实现分布式事务。

虽然MySQL XA能实现数据层的分布式事务，但会面临这样一个问题：在接收到外部的指令后，需要访问多个内部系统，执行指令约定的操作，而且，必须保证指令执行的原子性，也就是说，要么全部成功，要么全部失败，此时应该怎么做呢？答案是TCC

概述。
虽然MySQL XA能实现数据层的分布式事务，解决多个MySQL操作的事务问题，但还面临别的问题:在接收到外部的指令后，需要访问多个内部系统，执行指令约定的操作，还必须保证指令执行的原子性(也就是事务要么全部成功，要么全部失败)。那么如何实现指令执行的原子性呢？答案是TCC.
在我看来，基于二阶段提交的XA规范实现的是数据层面操作的事务，而TCC能实现业务层面操作的事务。理解了二阶段提交协议和TCC后，我们就可以从数据层面到业务层面更加全面地理解如何实现分布式事务了，从而在日常工作中更清楚地知道如何处理操作地原子性或者系统状态的一致性等问题。

我们还是先来看一道思考题。
以如何实现订票系统为例，假设现在要实现一个给内部员工提供机票订购服务的企鹅订票系统，但在实现订票系统时，我们需要考虑这样的情况:我想从深圳飞北京，但没有直达的机票，要先顶深圳航空的航班从深圳去上海，再定上海航空的航班从上海去北京，如图所示。
因为我的目的地时北京，所以如果只有一张机票订购成功肯定是不行的。这个系统必须保障两个订票操作的事务要么全部成功，要么全部不成功，那么该如何实现两个订票操作的事务呢？带着这个问题，我们先来了解下什么是TCC

什么是TCC。
前面已经在CAP理论介绍了TCC，这里只想补充一点:可以对比二阶段提交协议来理解TCC包含的预留(Try)、确认(Confirm0或撤销(Cancel)这两个阶段，分析如下。
1.预留和二阶段提交协议中的提交请求阶段的操作类似，具体是指系统会将需要确认的资源预留、锁定，确保确认操作一定能执行成功。
2.确认和二阶段提交协议中的提交执行阶段的操作类似，具体是指系统将最终执行的操作
3.撤销比较像二阶段提交协议中的回滚操作，具体是指系统将撤销之前预留的资源，也就是撤销已执行的预留操作对系统产生的影响。

在我看来，二阶段提交协议和TCC的目标都是实现分布式事务，这也就决定了它们在思想上是类似的。但是这两种算法解决的问题场景是不同的，一个是数据层面，一个是业务层面，这就决定了它们在细节实现是不同的。所以接下来，我们就一起看看TCC的细节。
为了更好地演示TCC的原理，我们假设深圳航空、上海航空分别为订票系统提供了以下3个接口:机票预留接口、确认接口和撤销接口。那么这时，订票系统可以这样来实现操作的事务。
首先，订票系统调用两个航空公司的机票预留接口，向两个航空公司申请机票预留。如图所示。
如果两个机票都预留成功，那么订票系统将执行确认操作，也就是订购机票，如图所示。

但如果此时有机票没有预留成功(比如深圳航空从深圳到上海的机票)，那么该怎么办呢？这时订票系统就需要通过撤销解耦来撤销订票请求，如图所示。
至此，我们就实现了订票操作的事务。在我看来，TCC的难点不在于理解TCC的原理，而在于如何根据实际场景特点来实现预留、确认、撤销3个操作。所以，为了更深刻地理解TCC的3个操作的实现要点，将以一个实际项目为例展开详细说明。

如何通过TCC实现指令执行的原子性。
前文提到，当接收到外部指令时，需要实现操作1、2、3，如果其中任何一个操作失败，那么我都需要暂停指令执行，将系统恢复到操作未执行状态，然后重试，如图所示.其中，操作1、2、3的含义具体如下.
1.操作1：生成指定URL页面对应的图片并持久化存储
2.操作2：调用内部系统1的接口，禁用指定域名的访问权限
3.操作3:通过MySQL XA更新多个数据库的数据记录。
那么我是如何通过TCC来解决这个问题的呢？答案是我在实现每个操作时都会分别实现响应的预留、确认、撤销操作.

首先，操作1是生成指定URL页面对应的图片，具体操作如下:
1.预留操作:生成指定页面的图片并存储到本地
2.确认操作:更新操作1状态为完成
3.撤销操作:删除本地存储的图片
其次，因为操作2是调用内部系统1的解耦，禁用该域名的访问权限，具体操作如下.
1.预留操作:调用内部系统1的禁用指定域名的预留接口，通知内部系统1预留相关的资源
2.确认操作:调用内部系统1的禁用指定域名的确认接口，执行禁用域名的操作
3.撤销操作:调用内部系统1的禁用指定域名的撤销接口，撤销对该域名的禁用，并通知内部系统1释放相关的预留资源
最后，操作3是通过MySQL XA更改多个MySQL数据库中的数据记录，并实现数据更新的事务，具体操作如下.
1.预留操作:执行XA START和XA END命令准备好事务分支操作，并调用XA PREPARE执行二阶段提交协议的提交请求，预留相关资源
2.确认操作:调用XA COMMIT执行确认操作
3.撤销操作:调用XA ROLLBACK执行回滚操作，释放在预留阶段预留的资源.

可以看到，确认操作时预留操作的下一个操作，而撤销操作则是用来撤销一致性的预留操作对系统产生的影响，类似在复制粘贴时，我们通过"Ctrl Z"撤销"Ctrl V"操作的执行，如图所示，这是理解TCC的关键

综上所述，我们首先执行操作1、2、3的预留曹祖，如果预留操作都执行成功了，那么我们将执行确认操作，继续向下执行。但如果预留操作只是部分执行成功，那么我们将执行撤销操作，取消预留操作对系统产生的影响。通过这种方式(指令对应的操作要么全部执行，要么全部不执行)，我们就能实现指令的原子性了。
另外，在执行确认、撤销操作时，有一点需要我们尤为注意，即这两个操作在执行时可能会重试，所以它们需要支持幂等性

思维拓展。
既然可以通过TCC解决了指令执行的原子性问题。那么你不妨想象，为什么TCC能解决指令执行的原子性问题呢？

重点总结。
1.TCC是个业务层面的分布式事务协议，而XA规范是数据层面的分布式事务协议，这也是TCC和XA规范的最大区别。TCC与业务紧密耦合，在实际场景中，需要我们根据场景特点和业务逻辑设计响应的预留、确认、撤销操作。相比MySQL XA,TCC有一定的编程开发工作量。
2.因为TCC是在业务代码中编码实现的，所以，TCC可以跨数据库、跨业务系统实现资源管理，满足复杂业务场景下的事务需求。比如,TCC可以将对不同的数据库、不同的业务系统的多个操作通过编码方式转换为一个原子操作，实现事务
3.因为TCC的每一个操作对于数据库来讲，都是一个本地数据库事务，所以当操作结束时，本地数据库事务的执行就完成了，相关的数据库资源也就被释放了，这就避免了数据库层面的二阶段提交协议长时间锁定资源，导致系统性能低下的问题。

想必你会有这样的疑问:如果有人作恶，Raft、TCC这些算法还使用吗？答案时不适用，因为Raft、TCC算法时非拜占庭容错算法，不适用于拜占庭容错的场景，而常用的拜占庭容错算法有PBFT、PoW算法

概述。
谈起比特币，你应该并不陌生。比特币是基于区块链实现的，而区块链运行在因特网上，这就存在有人试图作恶的情况。有些读者可能已经发现了，口信消息型拜占庭问题之解、PBFT算法虽然能防止坏人作恶，但只能防止少数人的坏人作恶，也就是(n-1)/3个坏人(其中n为节点数)。如果区块链也只能防止一定比例的坏人作恶，那就麻烦了，因为坏人可以不断增加节点数，轻松突破(n-1)/3的限制。那区块链是如何改进这个问题的呢？答案就是PoW(Proff of Work，工作量证明)算法。
在我看来，区块链是通过工作量证明增加坏人作恶的成本，以此来防止坏人作恶的。比如，如果坏人要发起51%攻击，需要控制全网51%的算例，成本是非常高昂。为什么呢？因为根据CryptoSlate估算，对比特币进行51%算力攻击需要上百亿人民币。
为了更好地理解和掌握PoWs算法，接下来会详细讲解它地原理和51%攻击地本质，希望在理解PoW算法的同时，也能了解PoW算法的局限。
首先说说工作量证明的原理，工作量是如何被证明的。

如何理解工作量证明。
什么是工作量证明呢？你可以这么理解:工作量证明就是一份证明，用来确认你做过一定量的工作。比如，你的大学毕业整数就是一份工作量证明，证明你通过4年的努力完成了相关课程的学习。回到计算机世界就是，客户端需要做一定难度的工作才能得出一个结果，验证方却很容易通过结果来检查客户端是不是做了相应的工作。比如小李来BAT面试，说自己的编程能力很强，那么他需要做一定难度的工作来验证自己的能力(比如做一道编程题)。根据做题结果，面试官可以判断他是否适合这个岗位。你看，小李做一道编程题，面试官核验做题结果，这就是一个现实版的工作量证明。
具体的工作量证明如图所示。
请求方做了一些运算，解决了某个问题，然后把运算结果发送给验证方进行核验;验证方根据运算结果，即可判断请求方是否做了相关的工作。
需要注意的是，这个算法具有不对称性，也就是说，工作对于请求方是有难度的，对于验证方则比较简单，是易于验证的。既然工作量证明是通过指定的结果来证明自己做过一定量的工作，那么在区块链的PoW算法中需要做哪些工作呢？答案是哈希运算。区块链是通过哈希运算后的结果值证明自己做过了相关工作。为了更好地理解哈希运算，在介绍哈希运算之前，先来聊一聊哈希函数。哈希函数(Hash Function)也叫散列函数。假设你输入一个任意长度的字符串，哈希函数会计算出一个长度相同的哈希值。假设我们对任意长度字符串(比如geektime)执行SHA256哈希运算，就会得到一个32字节的哈希值，如代码所示
```c
echo -n "geektime" | sha256sum
bb2f0f297fe9d3b8669b6b4cec3bff99b9de596c46af2e4c4a504cfe1372dc52
```
那我们如何通过哈希函数进行哈希运算，从而证明工作量呢？这里举个具体的例子帮助大家理解。
我们给出的工作量要求是，给定一个基本的字符串(比如geektime)，你可以在这个字符串后面添加一个整数值，然后对变更后(添加整数值后)的字符串进行SHA256哈希运算，如果运算后得到的哈希值(十六进制)是以0000开头，就表示验证通过。为了达到这个工作量证明的目标，我们需要不断地递增整数值，一个一个地试，并对得到的新字符串进行SHA256哈希运算。按照这个规则，我们需要经过35204次计算才能找到恰好前4位为0的哈希值。如代码所示
```c
"geektime0" =>
01f28c5df06ef0a575fd0e529be9a6f73b1290794762de014ec84182081e118e
"geektime1" =>
a2567c06fdb5775cb1e3ce17b72754cf146fcc6da75c8f1d87d7ab6a1b8c4523
...
"geektime35022" =>
8afc85049a9e92fe0b6c98b02b27c09fb869fbfe273d0ab84ad8c5ac17b8627e
"geektime35023" =>
0000ec5927ba10ea45a6822dcc205050ae74ae1ad2d9d41e978e1ec9762dc404
```
通过这个示例可以看到，经过一段时间的哈希运算后，我们会得到一个符合条件的哈希值。这个哈希值可以用来证明我们的工作量。这个规则不是固定的，在实际场景中，你可以根据场景特点制定不同的规则，比如，你可以试试分别运行多少次才能找到恰好前3位和前5位为0的哈希值。
现在，你对工作量证明的原理应该有一定的了解了，那么区块链是如何实现工作量证明的呢？

区块链是如何实现PoW算法的。
区块链也是通过SHA256来执行哈希运算计算出符合指定条件的哈希值来证明工作量的。因为在区块链中，PoW算法是基于区块链中的区块信息进行哈希运算的，所以下面我们先来回顾一下区块链的相关知识。
区块链的区块是由区块头、区块体两部分组成的，如图所示。
1.区块头(Block Head):主要由上一个区块的哈希值、区块体的哈希值、4字节的随机数(nonce)等组成
2.区块体(Block Body):区块包含的交易数，其中第一笔交易是Coinbase交易，这是一笔激励矿工的特殊交易。
拥有80字节固定长度的区块头就是用于区块链工作量证明的哈希运算中的输入字符串，而且通过双重SHA256哈希运算(也就是对SHA256哈希运算的结果再执行一次哈希运算)计算出地哈希值只有小于目标值(target)才是有效地，否则哈希值无效，必须重算。可以看到。区块链是通过对区块头执行SHA256哈希运算得到小于目标值的哈希值来证明自己的工作量的。

计算出符合条件的哈希值后，矿工就会把这个信息广播给集群中所有其他节点，待其他节点验证通过后，它们会将这个区块假如自己的区块链中，最终形成一条区块链，如图所示。算例越强，系统大概率会越先计算出这个哈希值。这也就意味着，如果坏人们掌握了51%的算力，就可以发起51%攻击，比如，实现双花(Double Spending)，即同一份钱花两次。
具体来说，如果攻击者掌握了较多的算例，那么他就能挖掘一条比原链更长的攻击链并将攻击链向全网广播，这时，按照约定，节点将接收更长的链，也就是攻击链，丢弃原链，如图所示。

需要注意的是，即使攻击者只有30%的算力，他也有可能连续计算出多个区块的哈希值，挖掘出更长的攻击链，发动攻击。另外，即使攻击者拥有51%的算力，他也有可能半天无法计算出一个区块的哈希值，即攻击失败，也就是说，能否计算出符合条件的哈希值有一定的概率性，但长久来看，攻击者攻击成功的概率等同于攻击者算力的权重

重点总结。
1.在比特币的区块链中，PoW算法是通过SHA256哈希运算计算出符合指定条件的哈希值来证明工作量的。
2.51%攻击的本质是因为比特币的区块链约定了"最长链胜出，其他节点在这条链上扩展"，所以攻击者可以通过优势算力实现对最长链的争夺。
3.除了通过PoW算法增加坏人作恶的成本，比特币还通过"挖矿得币"奖励好人，最终保持了整个系统的稳定运行。
另外，因为拜占庭容错算法(比如PoW算法、PBFT算法)能容忍一定比例的作恶行为，所以它在相对开放的场景中应用广泛，比如公链、联盟链。非拜占庭容错算法(比如Raft算法)无法对作恶行为进行容错，主要用于封闭、绝对可信的场景中，比如私链、公司内网的DevOps环境。我们要理解两类算法之间的差异，根据场景特点，选择合适的算法，保障业务高效、稳定的运行

什么是线性一致性。
线性一致性(Linearizability),也称为原子性或强一致性，是分布式系统中的一个一致性模型，它定义了系统对读写操作的行为，以确保系统表现得好像只有一个数据副本，并且所有操作都是原子的。
在线性一致性模型中，系统的行为应该满足以下条件:
1.单副本视角(Single Copy View):系统对外表现为只有一个数据副本，即所有客户端看到的数据状态是一致的，不管它们连接到哪个服务器副本
2.原子性(Atomicity):每个操作好像都是瞬间完成的，即一旦操作返回给客户端，所有客户端就能立即看到这个操作的结果
3.实时性(Real-time):操作的顺序应该与实际发生的时间顺序一致，即如果操作A在操作B之前完成，那么所有客户端都应该先看到操作A的结果，然后才能看到操作B的结果。

线性一致性模型是分布式系统中一致性最强的一个模型，它为客户端提供了最直观和最易于理解的行为保证。然而，实现线性一致性通常需要牺牲性能和可用性，因为在保持强一致行的同时，系统需要在多个副本之间进行更多的协调和通信。

分布式系统中，线性一致性通常通过以下机制来实现:
1.一致性:如Paxos、Raft、ZAB等，用于在多个副本之间达成共识，并确保操作的顺序和结果的一致性
2.锁机制:用于协调对共享资源的访问，确保同一时间只有一个操作可以修改数据。
3.时间同步:确保不同服务器之间的时钟偏差足够小，以便可以准确判断操作的顺序。

线性一致性模型在需要严格数据一致性的场景张非常重要，例如金融系统、实时控制系统等。然而，对于许多其他类型的分布式系统，尤其是那些对性能和可用性有更高要求的系统，可能会选择较弱的一致性模型，如最终一致性(Eventual Consistency)或其他妥协方案

假如，客户端C1要实现X=1,客户端C2要实现X=2,当Raft中的领导者收到C1的写请求，此时，领导者还没有收到大多数节点的确认，领导者又收到了C2的写请求，此时，C2会不会比C1先一步收到大多数节点的确认？
答案: 在Raft算法中领导者负责将客户端的请求(命令)作为日志条目顺序地追加到自己的日志中,并尝试将这些日志条目复制到集群中的其他服务器，日志条目的顺序是由领导者决定的，并且这个顺序会严格按照领导者接收请求的顺序来复制和提交。
对于上面描述的场景:Raft会这样处理
1.领导者接收请求:领导者首先收到了客户端C1的写请求X=1,并将其作为日志条目添加到自己的日志中。然后，领导者开始尝试将这个日志条目复制到集群中的其他服务器。
2.日志条目复制:在领导者还没收到大多数服务器对这个日志条目X=1的确认之前，领导者又收到了客户端C2的写请求X=2.领导者会将这个请求也作为日志条目添加都自己的日志中，紧随X=1的条目之后。
3.顺序复制:领导者会尝试按照日志条目的顺序将它们复制到其他服务器。这意味着X=2的日志条目被复制到大多数服务器之前，领导者会先尝试完成X=1的日志条目的复制
4.提交日志条目:只有当X=1的日志条目被大多数服务器确认之后，它才会被认为是"已提交"的，此时领导者才会将X=1应用到状态机，并通知客户端C1请求已成功执行。之后，领导者才会开始尝试复制X=2的日志条目，并重复这个过程

因此，即使在领导者还没有收到大多数节点对X=1的确认之前就收到了X=2的请求，X=2也不会比X=1先一步被提交。Raft算法通过这种顺序性的保证来确保操作的线性一致性，即所有客户端的状态变化顺序是一致的。

Raft是如何保证线性一致性的？
Raft算法通过一系列机制来保证线性一致性的，即使得系统表现得好像只有一个数据副本，且所有的操作都是原子的,
以下是Raft算法如何实现线性一致性的关键点:
1.领导者的单一性: 在任意给定时间，系统中只有一个领导者。所有客户端请求都必须通过领导者来处理，
领导者负责将请求作为日志条目复制到其他服务器。这确保了所有操作都可以通过一个中心点来顺序化
2.日志条目的连续性和顺序性:领导者将客户端请求作为日志条目按顺序追加到自己的日志中，并为每个日志条目
分配一个连续的索引号。日志条目在领导者上的顺序决定了它们将被应用到状态机的顺序
3.日志条目的提交:当一个日志条目被复制到大多数服务器上后，它被认为是"已提交的"。一旦日志条目被提交，
它就被应用到状态机上，并且其结果对客户端可见。在Raft中，领导者确保在将结果返回给客户端之前，相应的
日志条目已经被提交
4.领导者的租约:Raft算法中，领导者有一个租约(lease)，它是一个时间间隔，在这个时间内，领导者假定自己
是唯一的活跃领导者。在租约期间，领导者可以不需要与其他服务器通信就能处理客户端请求，这减少了延迟，
并提高了系统的响应速度。
5.领导者变更时的线性一致性:当领导者宕机或失去与大多数服务器的通信时，新的领导者会被选举出来。在领导者
变更期间，系统不处理新的客户端请求，这保证了在领导者变更过程中不会违反线性一致性。新的领导者确保
前任领导者留下的未提交日志条目被正确处理

通过上述机制，Raft算法能够在一个分布式系统中提供线性一致性，即使在面对网络延迟、分区、服务器故障等挑战
时也能保持系统的一致性和稳定性

Raft算法如何保证操作的顺序性。
Raft算法是一种分布式系统中用于管理复制日志的一致性算法，它通过一系列机制来保证操作的顺序性。在分布式系统中，多个服务器需要协同工作，保持数据的一致性，而操作顺序性的保证是至关重要的。Raft算法通过以下几个关键机制来确保操作的顺序性:
1.领导者选举(Leader Election):
1.1 Raft算法中，系统通过领导选举机制选出一个领导者(Leader)，所有日志条目的复制都由领导者负责。
1.2 当现任领导者宕机或失去与大多数服务器的通信时，会触发新的领导者选举
1.3 在选举过程中，节点之间通过投票来决定哪个节点成为新的领导者
1.4 一旦选举出新的领导者，所有的后续操作都会通过领导者来保证顺序性
2.日志复制(Log Replication):
2.1 客户端的请求首先发送给领导者
2.2 领导者将请求作为日志条目(Log Entry)追加到自己的日志中
2.3 随后，领导者并行地将这些日志条目复制到其他服务器
2.4 只有当大多数服务器已经存储了该日志条目时，领导者才会将日志条目应用到状态机，此时操作才被认为是"已提交"
2.5 日志条目在各个服务器上的顺序是由领导者分配的索引号来保证的，因此所有服务器上的日志条目顺序是一致的
3.领导者的单调性(Leader Monotonicty):
3.1 Raft算法中，领导者保证日志条目的顺序单调递增，即在任意任期中，一个日志条目的索引号不会重复
3.2 这保证了即使在网络分区或领导者变更的情况下，日志条目的顺序性也不会被打乱
4.日志匹配属性(Log Matching Property):
4.1 如果在两个不同的日志中，两个条目有着相同的索引号和任期号，那么这两个条目之前的所有日志条目也必然相同。
4.2 这个属性保证了即使在发生网络分区或者服务器故障的情况下，各服务器上的日志在大多数情况下是一致的。
5.提交之前的状态(State Before Commit):
5.1 Raft算法中，领导者会跟踪哪些日志条目已经被提交，并确保在将日志条目应用到状态机之前，这些条目已经被复制到了大多数服务器上
5.2 这确保了在领导者宕机后，新的领导者也能知道哪些操作是已经被提交的，从而保证操作的顺序性

执行多次Basic Paxos为什么如果多个提议者同时提交提案，可能出现因为提案编号冲突，在准备阶段没有提议者收到大多数准备响应，导致协商失败，需要重新协商？
Basic Paxos是一种解决分布式系统中一致性问题的算法。它允许一组进程就某个值达成一致，即使在发生网络分区、进程故障等不确定性的情况下也能保证最终一致性。
在Basic Paxos中，为了达成一致性，提案者(proposer)需要与接收者(acceptor)进行两阶段提交过程:
1.准备阶段(Prepare Phase):
1.1 提案者选择一个提案编号N,并向接受者的多数派发送准备请求(prepare request)
1.2 当接受者收到准备请求后，如果提案编号N大于它已经响应过的任何准备请求的编号，它就会承诺不再接受编号小于N的任何提案，并将其之前接受的最高编号的提案(如果有)作为响应发送回提案。
2.接受阶段(Acceptor Phase):
2.1 当提案者从多数派的接受者那里得到响应后，它会发出一个带有提案编号N和提案值V的接受请求(accept request).
2.2 接受者收到接受请求后，如果它没有违背之前发出的任何承诺，就会接受这个提案

但是，如果有多个提案者同时尝试提交提案，可能会出现以下问题:
1.提案编号冲突:每个提案者选择的提案编号可能相同或小于已经承诺不再接受的其他提案者发送的提案编号
2.准备阶段响应不足:由于网络延迟、分区或进程故障，提案者可能无法从多数派的接受者哪里获得响应。

当发生上述情况时，提案者在准备阶段可能无法接收到大多数接受者的准备响应，导致协商失败。协商失败后，提案者需要重新开始两阶段提交过程，选择一个新的、更大的提案编号，并再次尝试

为了避免提案编号冲突，提案者通常会采用一些策略。例如使用唯一标识符(如进程ID)和时间戳来生成提案编号。此外，还可以通过选举一个领导者(leader)来减少多个提案者同时提交提案的情况，由领导者作为唯一的提案者来提交提案，从而减少冲突和协商失败的可能性

前言。
etcd是线性一致性读，而zk却是顺序一致性读，再加上各种共识、强弱一致的名词，看到欸度时候总会混淆，这里会给出一些例子来帮助理解。

什么是一致性？
在谈到一致性这个词时，你会想到CAP理论的consistency,或者ACID钟的consistency,或者cache一致性协议的coherence，还是Raft/Paxos钟的consensus?
一致性这个词在不同的领域具有不同的含义，毕竟这个中文词在英文词对应了不同的术语，consistency，coherence，consensus三个单词统一翻译为"一致性"。因此在谈一致性之前，有必要对这几个概念做一个区分，否则很容易让人迷惑。