分布式与一致性协议相关

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

举个例子。这3位将军各自一脸严肃地决定明天是进攻还是撤退，并让信使传递消息，按照\"少数服从多数\"的原则投票决定，两个人意见一致就可以了:1.齐根据侦察情况决定撤退2.楚和燕根据侦察信息，决定进攻可是，问题来了:一旦有人暗通秦国，就会出现作战计划不一致的情况。比如齐向楚、燕分别发送\"撤退\"的消息，燕向齐和楚发送\"进攻\"的消息。撤退:进攻 = 1：1，无论楚投进攻还是撤退，都会成为2:1，这时候还是会形成一个一致的作战方案。但是，楚这个叛将在暗中配合秦国，让信使向齐发送了\"撤退\

二忠一叛难题。为了便于理解和层层深入，先假设只有3个国家要攻打秦国，这3个国家的三位将军，分别叫齐、楚、燕。同时因为很强大，所以只有3个国家半数以上的将军都参与进攻，才能击败敌人(假设)，且在这个期间，将军们彼此之间需要通过信使传递消息，待协商一致之后，才能在同一是按点发动进攻。

首先是3位忠将先发送作战信息的情况。为了演示方便，假设苏秦先发起作战信息，作战指令是\"进攻\"。那么在第一轮作战信息协商中，苏秦向齐、楚、燕发送作战指令\"进攻\

在第二轮作战信息协商中，齐、楚、燕分别作为指挥官，向另外两位将军发送作战信息\"进攻\

最终，齐和燕收到的作战信息都是\"进攻、进攻、撤退\"，按照烧出服从多数的原则，齐、燕和苏秦一起执行作战指令\"进攻\

然后在第二轮作战信息协商中，苏秦、齐、燕分别作为指挥官，向另外两位将军发送作战信息，如图所示最终，苏秦、齐和燕收到的作战信息都是\"撤退、撤退、进攻\"，按照少数服从多数的原则，苏秦、齐和燕执行作战指令\"撤退\"，实现了作战计划的一致性。也就是说，无论叛将楚如何捣乱，苏秦、齐、和燕都会执行一致的作战计划，从而保证作战的胜利。

这个解决办法其实是在兰伯特在论文\"The Byzantine Generals Problem\

口信消息。该如何处理呢？先来说第一个解决办法。首先，3位将军都分拨一部分军队，由苏秦率领，苏秦参与作战计划讨论并执行作战指令。这样，3位将军的作战讨论就变为了4位将军的作战计划，这能够增加讨论中忠诚将军的数量。然后，4位将军约定了，如果没有受到命令，就执行预设的命令，比如\"撤退\"。除此之外，它们还约定一些流程来发送作战信息、执行作战指令，比如，进行两轮作战信息协商。为什么要进行两轮协商呢?后面再解释。第一轮:1.先发送作战信息的将军作为指挥官，其他将军作为副官2.指挥官将他的作战信息发送给每位副官3.每位副官将从指挥官处收到的作战信息作为他的作战指令;如果没有收到作战信息，则把默认的\"撤退\"作为作战指令第二轮:1.除了第一轮的指挥官外，剩余的3位将军将分别作为指挥官，向另外两位将军发送作战信息。2.然后，这3位将军按照少数服从多数的原则，执行收到的作战指令为了更直观地理解苏秦地整个解决方案，接下来将演示作战信息的协商过程。会分别以忠将和叛将先发送作战信息为例来完整地演示叛将对作战计划干扰破坏的可能性

什么是签名消息？签名消息是指带有数字签名的消息。数字签名与在纸质合同上进行签名来确认合同内容和证明身份类似。它既可以证实内容的完整性，又可以确认内容的来源，实现不可抵赖性(Non-Repudiation)。既然数字签名的优点那么多，那么如何实现签名消息呢?今天Bob要给Alice发送一条消息，告诉她，\"我已经到北京了\

为了更直观地理解如何基于签名消息实现忠将们的作战计划的一致性，下面来演示一下作战信息协商过程，仍会分别以忠将和叛将先发送作战信息为例来完整地演示叛将对作战计划干扰破坏的可能性。忠将先发送作战信息的情况是什么样的呢？为了演示方便，假设苏秦先发起带有签名的作战信息，作战指令是\"进攻\

在第二轮作战信息协商中，齐、楚、燕分别作为指挥官，向另外两位发送作战信息\"进攻\".虽然楚、燕已经叛变了，但是在签名的约束下，它们无法篡改和伪造忠将的消息。为了达到干扰作战计划的目的，它们一个选择发送消息，一个选择默不作声，不配合，如图所示

在第三轮作战信息协商中，齐、楚分别作为指挥官，将接收到的作战信息附加上自己的签名，并转发给另一位，如图所示，(这时的叛将燕还是默不作声，不配合)。最终，齐收到的作战信息都是\"进攻\"(它收到了苏秦和楚地作战信息)，按照\"执行盒子最中间的指令\"的约定，齐会和苏秦一起执行作战指令\"进攻\

忠将先发送消息

如果是叛将楚先发送作战消息，干扰作战计划，结果会有所不同吗？在第一轮作战信息协商中，楚向苏秦发送作战指令\"进攻\

接着，在第三轮作战信息协商中，苏秦、齐、燕分别作为指挥官，将接收到的作战信息附加上自己的签名，并转发给另外以为，如图所示

最终，苏秦和齐接收到的作战信息都是\"撤退、进攻\"，按照\"执行盒子最中间的指令\"的约定，苏秦、齐和燕一起执行作战指令\"撤退\"，实现了作战计划的一致性。也就是说，无论叛将楚和燕如何捣乱，苏秦和齐都能执行一致的作战计划，保证作战的胜利。

叛将先发送消息

签名消息型拜占庭问题之解。根据前面提到的，苏秦通过签名消息的方式，不仅能在不增加将军认数的情况下解决二忠一叛的难题，还能实现无论叛将数多少，都能保证忠诚的将军们始终达成一致的作战计划。为了便于理解，以二忠二叛(更复杂的叛将作恶模型，因为叛将们可以相互勾结、串通)为例来具体演示一下，苏秦是怎样实现作战计划的一致性的。如图所示首先，苏秦要通过印章、虎符等信物，实现这样几个特性1.忠将的签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现2.任何人都能验证将军签名的真伪其次，4位将军约定了一些流程来发送作战信息、执行作战指令第一轮:1.先发送作战指令的将军作为指挥官，其他将军作为副官2.指挥官将他签名的作战指令发送给每位副官3.每位副官将从指挥官处收到的新的作战指令(也就是与之前收到的作战指令不同)，按照顺序(比如按照首字母字典排序)放到一个盒子里面第二轮:1.除了第一轮的指挥官外，剩余的3位将军将分别作为指挥官，在上一轮收到的作战指令加上自己的签名，并转发给其他将军第三轮:1.除了第一、二轮的指挥官外，剩余的两位将军将分别作为指挥官，在上一轮收到的作战指令上，加上自己的签名，并转发给其他将军。最后，各位将军按照约定，比如使用盒子里最中间的那个指令来执行作战指令。假设盒子中的指令为A、B、C，那中间的指令就是第n/2个命令。其中，n为盒子里的指令数，指令从0开始编号，也就是B

如何解决n>(3f+1)的限制。其实，苏秦还可以通过签名的方式在不增加将军人数的情况下解决二忠一叛的难题。这个办法的关键在于通过消息签名约束叛将的作恶行为，也就是说，任何篡改和伪造忠将的行为都会被发现。既然签名消息这么重要，那么，什么是签名消息呢?

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

拜占庭将军问题

概述。前面提到了拜占庭将军问题之后，有人可能会感到困惑:口信消息型拜占庭问题直接在实际项目中是如何落地的呢？事实上，它很难在实际项目中落地，因为口信消息型拜占庭问题之解是一个非常理论化的算法，没有与实际场景结合，也没有考虑如何在实际场景中落地和实现。比如，它实现的是在拜占庭错误场景下，忠将们如何在判断干扰时就一致行动达成共识。但是它并不关心结果是什么，这会出现一种情况:现在适合进攻，但将军们达成的最终共识却是撤退。很显然，这不是我们想要的结果。因为在实际场景中，我们需要就提议的一系列值(而不是单值)，即使在拜占庭错误发生的时候，也能达成共识。那我们应该怎么做呢？答案就是采用PBFT算法。PBFT算法非常实用，它是一种能在实际场景中落地的拜占庭容错算法，在区块链中应用广泛(比如Hyperledger Sawtooth、Zilliqa)。为了更好地理解PBFT算法，下面会先介绍口信消息型拜占庭问题之解的局限，再介绍PBFT算法的原理。老规矩，我们先看一道思考题。假设苏秦再一次带队抗秦，如苏秦和4个国家的4位将军赵、魏、楚、韩商量军机要事，如图所示，结果刚商量完没多久苏秦就接到了情报:联军中可能存在一个叛徒。这时，苏秦要如何下发作战指令来保证忠将们正确、一致地执行下发的作战指令，而不被叛徒干扰呢？

PBFT算法是如何达成共识的。我们先来看看如何通过PBFT算法解决苏秦面临的共识问题。先假设苏秦制定的作战指令是进攻，而楚是叛徒(为了演示方便)，如图所示需要注意的是，所有的消息都是签名消息，也就是说，消息发送者的身份和消息内容都是无法伪造和篡改的(比如，楚无法伪造一个假装来自赵的消息)。首先，苏秦联系找，向赵发送包含作战指令\"进攻\

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

主节点作恶会出现什么问题。在PBFT算法中，主节点作恶有如下几种情况:1.主节点接收到客户端请求后不做任何处理，也就是默不作声2.主节点接收到客户端请求后给不同的预准备请求分配不同的序号3.主节点只给部分系欸但发送预准备消息需要注意的是，不管出现哪种情况，共识都是无法达成的，也就是说，如果恶意节点当选了主节点，此时无论忠诚节点数有多少，忠诚节点们都将无法达成共识。而这种情况肯定是无法接受的，这需要我们设计一个机制，在发现主节点可能作恶时，将作恶的主节点替换掉，并保证最终只有忠诚的节点担任主节点。这样，PBFT算法才能保证当节点数为3f+1(其中f为恶意节点数)时，忠诚的节点们能就客户端提议的指令达成共识，并执行一致的指令。那么，在PBFT算法中，视图变更是如何选举出新的主节点并替换掉作恶的主节点呢？

如何替换作恶的主节点。在我看来，视图变更是保证PBFT算法稳定运行的关键。当系统运行异常时，客户端或备份节点出发系统的视图变更，通过\"轮流上岗\

注意。相比Raft算法完全不适应有人作恶的场景，PBFT算法能容忍(n-1)/3个恶意节点(也可以是故障节点)。另外，相比Pow算法，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 Sawtooth2.与其他拜占庭容错算法结合来落地公有链，比如Zilliqa，将Pow算法和PBFT算法结合起来，实现公有链的共识协商。具体来说，PoW算法用于认证，证明节点不是\"坏人\"，PBFT算法用于实现共识。针对PBFT算法消息数过多、不适应大型分布式系统的痛点，Zilliqa实现了分片(Sharding)技术。另外，也有团队因为PBFT算法消息数过多、不适应大型分布式系统的痛点，放弃使用PBFT算法，而是通过法律来约束\"节点作恶\"的行为，比如IBM的Hyperledger Fabric。技术是发展的，适合的才是最好的。在实际工作中，建议根据场景的可信度来决定是否采用PBFT算法，是否改进和优化PBFT算法。

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

PBFT算法

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

紧接着，客户端向节点1发送写请求\"SET X=2\

如果节点1收到写请求后，只将节点1的X值更新为2，然后返回Success给客户端，如图所示

此时如果客户端访问节点2执行读操作，就无法读到最新写入的X值，这就不满足一致性了，如图所示

如果节点1收到写请求后，通过节点间的通信，同时将节点1和节点2的X值都更新为2，然后返回Success给客户端，如图所示

那么在完成写请求后，不管客户端访问哪个节点，读取到的都是同一份最新写入的数据，如图所示，这就叫一致性。

举个例子。两个节点的KV存储系统，原始的KV记录为\"X=1\"，如图所示:

可用性是指任何来自客户端的请求，不管访问哪个非故障节点，都能得到响应数据，但不保证是同一份最新数据。也可以把可用性看作分布式系统对访问本系统的客户端的另外一种承诺:我尽力给你返回数据，不会不响应你，但是我不保证每个节点给你的数据都是最新的。这个指标抢到的是服务可用，但不保证数据正确。

举个例子。当节点1和节点2的通信出现问题时，如果系统仍能继续工作，那么两个节点是满足分区容错性的

分区容错性是指，当节点间出现任意数量的消息丢失或高延迟的时候，系统仍然可以继续工作，也就是说，分布式系统告诉访问本系统的客户端:不管我的内部出现什么样的数据同步问题，我都会一直运行。这个指标强调的是集群对分区故障的容错能力.因为分布式系统与单机系统不同，它涉及多节点间的通信和交互，节点间的分区故障是必然发生的，所以，在分布式系统中分区容错性是必须要考虑的。现在在了解了一致性、可用性和分区容错性，那么在涉及分布式系统时，是从一致性、可用性、分区容错性中选择其一，还是三者都可以选择呢？这3个指标之间有什么冲突吗?

CAP三指标。CAP理论对分布式系统的特性做了高度抽象，形成了3个指标:1.一致性(Consistency);2.可用性(Availability)3.分区容错性(Parition Tolerance)一致性是指客户端的每次读操作，不管访问哪个节点，要么读到的是同一份最新写入的数据，要么读取失败。大家可以把一致性看作分布式系统对访问自己的客户端的一种承诺:不管你访问哪个节点，要么我给你返回的是绝对一致的最新写入的数据，要么你读取失败。可以看到，一致性强调的是数据正确。

CAP不可能三角。CAP不可能三角是指对于一个分布式系统而言，一致性、可用性、分区容错性指标不可兼得，只能从中选择两个，如图所示。CAP不可能三角最初是埃里克·布鲁尔(Eric Brewer)基于自己的工程实践提出的一个猜想，后被塞斯·吉尔伯特(Seth Gilbert)和南希·林奇(Nancy Lynch)证明，(https://dl.acm.org/citation.cfm?id=564601)基于证明的严谨性的考虑，塞斯吉尔伯特和南希林奇对指标的含义做了预设和限制，比如，将一致性限制为原子一致性。那么如何使用CAP理论来思考和涉及分区容错一致性模型呢？

以开源版的InfluxDB为例，InfluxDB是由节点和META和DATA节点两个逻辑单元组成的(如图所示)，这两个节点的功能和数据特点不同，需要我们分别为它们涉及分区容错一致性模型。具体涉及如下:1.作为分布式系统，分区容错性时必须要实现的，不能因为节点间出现了分区故障，而出现整个系统不工作的情况2.考虑到META节点保存的是系统运行的关键元信息，比如数据库名、表名、保留策略信息等，所以必须实现一致性。也就是说，每次读都要能读到最新数据，这样才能避免因为查询不到指定的元信息，而导致时序数据记录写入失败或者系统没办法正常运行。比如创建数据库telegraf之后，如果系统不能立刻读取到这条新的元信息，那么相关的时序数据记录就会因为找不到指定数据库信息而写入失败，所以，应该选择CAP理论中的C和P，采用CP架构3.DATA节点保存的是具体的时序数据记录，比如一条记录CPU负载的时序数据\

注意。在当前分布式系统开发中，延迟是非常重要的一个指标。比如，在QQ后台的名字路由系统中，通过延迟评估服务可用性进行负载均衡和容灾；再比如再Hashicorp Raft实现中，通过延迟评估领导者节点的服务可用性，以及是否发起领导者选举，所以，希望大家在分布式系统的开发中，也能意识到延迟的重要性，能通过延迟来衡量服务的可用性

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

需要注意的是，在第一个阶段，每个参与者投票表决事务是放其还是提交。一旦参与者投票要求提交事务，那么就不允许放弃事务。也就是说，在一个参与者投票要求提交事务之前，它必须保证能够执行提交协议中它自己的那一部分，即是参与者出现故障或者中途被替换掉。这个特性是我们需要在代码实现时保障的。还需注意的是，在第二个阶段，事务的每个参与者执行最终统一的决定，提交事务或者放弃事务。这个约定是为了实现ACID中的原子性。二阶段提交协议最早是用来实现数据库的分布式事务的，不过现在最常用的是XA协议。XA协议是X/Open国际联盟基于二阶段提交协议提出的，也叫X/Open DTP(Distributed Transaction Processing)模型，比如MySQL就通过MySQL XA实现了分布式事务(MySQL中的XA事务需要将事务隔离级别设置为串行化)。但是不管是原始的二阶段提交协议，还是XA协议都存在一些问题:1.在提交请求阶段，需要预留资源，在资源预留期间，其他人不能操作(比如XA协议在第一阶段会将相关资源锁定，比如间隙锁的使用以及重要数据的更新时)：2.数据库是独立的系统。因为上面这两点，我们无法根据业务特点弹性地调整锁地粒度，而这些都会影响数据库地并发性能。那用什么办法可以解决这些问题呢?答案就是TCC

二阶段提交协议。二阶段提交协议，顾名思义，就是通过二阶段的协商来完成一个提交操作，那么具体是怎么操作的呢？首先，苏秦发消息给赵，赵接收到消息后就扮演协调者(Coordinator)的身份联系魏和韩发起二阶段提交，如图所示。赵发起二阶段提交后，先进入提交请求阶段(又称投票阶段)。为了方便演示，我们先假设赵、魏、韩明天都能去攻打秦国，大致步骤如图所示。也就是说，第一步，赵分别向魏、韩发送消息:\"明天攻打秦国，方便么?\"第二步，赵、魏、韩分别评估明天能否去攻打秦国，如果能，就预留时间并锁定，不再安排其他军事活动第三步，赵得到全部的回复结果(包括他自己的评估结果)，都是YES赵收到所有回复后，进入提交执行阶段(又称完成阶段)，大致步骤如图所示首先，赵按照\"要么全部执行，要么放弃\

TCC。TCC是Try(预留)、Confirm(确认)、Cancel(撤销)3个操作的合称，它包含了预留、确认(或撤销)两个阶段。那么如何使用TCC协议解决苏秦面临的问题呢?首先，我们进入预留阶段，大致步骤如图所示第一步，苏秦分别通知赵、魏、韩预留明天的时间和相关资源。然后诉求你注册确认操作(明天攻打秦国)和撤销操作(取消明天攻打秦国)。第二步，苏秦收到赵、魏、韩的预留答复，都是Success.如果预留节点的执行都没有问题，则进入确认阶段，大致步骤如图所示第一步，苏秦执行确认操作，通知赵、魏、韩攻打秦国第二步，收到确认操作的响应，完成分布式事务。如果预留阶段执行出错，比如赵的一部分军队还在赶来的路上，无法出兵，那么就将进入撤销阶段，大致步骤如图所示第一步，苏秦执行撤销操作，通知赵、魏、韩取消明天攻打秦国的计划第二步，收到撤销操作的响应。在经过了预留和确认(或撤销)阶段的协商，苏秦实现这个分布式事务:赵、魏、韩三国，要么明天一起进攻，要么明天都按兵不动。其实在我看来，TCC本质上是补偿事务，它的核心思想是为每个操作都注册一个与其对应的确认操作和补偿操作(也就是撤销操作)。它是业务层面的协议，你也可以将TCC理解为编程模型。TCC的3个操作是需要在业务代码中编码实现的，为了实现一致性，确认操作和补偿操作必须是幂等的，因为这两个操作可能需要失败重试。另外，TCC不依赖于数据库的事务，而是在业务中实现了分布式事务，这样能减轻数据库的压力，但对业务代码的入侵性更强，实现的复杂度也更高。所以推荐在需要分布式事务能力的时候，优先考虑线程的事务型数据库，比如MySQL XA，在现有的事务型数据库不能满足业务需求的时候，再考虑基于TCC实现分布式事务。

最后补充一下，三阶段提交协议虽然针对二阶段提交协议的\"协调者故障，参与者长期锁定资源\"的痛点引入了询问阶段和超时机制来减少资源被长时间锁定的情况，不过这会导致集群各节点在正常运行的情况下，使用更多的消息进行协商，增加了系统负载和响应延迟。因此，不建议使用三阶段提交协议，

注意。可以将ACID特性理解为CAP中一致性的边界，最强的一致性，也就是CAP的\"酸\"(Acid)。根据CAP理论，如果分布式系统中实现了一致性，那么可用性必然受到影响。比如，如果出现一个节点故障，则整个分布式事务的执行都是失败的。实际上，绝大部分场景对一致性要求没那么高，短暂的不一致时能接受的，另外，基于可用性和并发性能的考虑，建议在开发实现分布式系统时，如果不是必须，尽量不要实现ACID而是考虑实现最终一致性。

ACID理论:CAP的\"酸\

实现基本可用的4板斧。在我看来，基本可用是指分布式系统在出现不可预知的故障时，允许损失部分功能的可用性，以保障核心功能的可用性。就像弹簧一样，遇到外界的压迫，它不是折断，而是变形伸缩，不断适应外力，实现基本的可用。具体来说，你可以把基本可用理解为，当系统节点出现大规模故障的时候，比如专线的光纤被挖断、突发流量导致系统过载(出现了突发事件。服务被大量访问)，可以通过服务降级，牺牲部分功能的可用性，以保障系统的核心功能可用。以12306订票系统基本可用的设计为例，该订票系统在春运期间会因为开始售票后先到先得的缘故出现极其海量的请求峰值，如何解决这个问题呢?我们可以在不同的事件出售不同区域的票，以错开访问请求，削弱请求峰值，比如，在春运期间，深圳出发的火车票在8点开售，北京出发的火车票在9点开售。这就是我们常说的流量削峰。另外，你可能已经发现了，在春运期间，自己提交的购票请求往往会在队列中等待处理，可能在几分钟或十几分钟后，才能被系统处理，然后响应处理结果，这就是我们熟悉的延迟响应。12306订票系统在出现超出系统处理能力的突然流量的情况下，会通过牺牲响应事件的可用性来保障核心功能的运行。通过流量削峰和延迟响应，系统是不是就实现了基本的可用呢？现在它不会再像最初的时候那样常常报404错误了吧？再比如，你负责一个互联网系统，此时突然出现了网络热点事件，涌进来好多用户，产生了海量的突然流量，导致系统过载，大量图片因为网络超时无法显示。那么这个时候你可以通过哪些方法保障系统的基本可用呢？相信你马上就想到体验降级，比如用小图片来替代原始图片，通过降低图片的清晰度和大小，来提升系统的处理能力。然后你还能想到过载保护，比如把接收到的请求放在指定的队列中排队处理，如果请求等待时间超时了(假设是100ms)，则之解拒绝超时请求；如果队列满了，则清除队列中一定数量的排队请求，以保护系统不过载，实现系统的基本可用。你看，与12306的设计类似，只不过你是通过牺牲部分功能的可用性来保障互联网的核心功能运行的。说了这么多，主要是想强调:基本可用在本质上是一种妥协，即在出现节点故障或系统过载的时候，通过牺牲非核心功能的可用性来保障核心功能的稳定运行。希望大家在后续的分布式系统的开发中，不仅能掌握流量削峰、延迟响应、体验降级、过载保护这四板斧，更能理解这4板斧背后的妥协中，从而灵活地处理不可预知的突然问题

最终一致性。在我看来，最终一致性是指系统中所有数据副本在经过一段时间的同步后最终达到一种一致的状态。也就是说，在数据一致性上，系统存在一个短暂的延迟。几乎所有的互联网系统采用的都是最终一致性，只有在确实无法使用最终一致性时，才使用强一致性或事务。比如，对于决定系统运行的敏感元数据，我们需要考虑采用强一致性；对于与钱有关的支付系统或金融系统的数据，我们需要考虑采用事务。你可以将强一致行理解为嘴仗一致性的特例，也就是说，你可以把强一致性看作不存在延迟的一致性。在实践中，你也可以这样思考:如果业务的某功能无法忍受一致性的延迟(比如分布式锁对应的数据)，则可以考虑强一致性；如果业务功能能容忍短暂的一致性的延迟(比如QQ状态数据)，则可以考虑最终一致性。那么如何实现最终一致性呢？你首先要知道它以什么为准，因为这时实现最终一致性的关键。一般来说，在实际工程实践中有这样两个标准:1.以最新写入的数据为准，比如，AP模型的KV存储采用的就是这种方式2.以第一次写入的数据为准，如果你不希望存储的数据被更改，可以以它为准。那实现最终一致性的具体方式是什么呢？下面介绍几种常用的方式.1.读时修复。在读取数据时，检测到数据的不一致并进行修复，比如Cassandra的Read Repair实现，具体来说，在向Cassandra系统查询数据的时候，如果检测到不同节点的数据副本不一致，则系统会自动修复数据2.写时修复:在写入数据时，检测到数据的不一致并进行修复，比如Cassandra的Hinted Handoff实现，具体来说，在向Cassandra集群的节点之间远程写数据的时候，如果写失败就将数据缓存下来，然后定时重传，以修复数据的不一致性3.异步修复，这时最常用的方式，定时对账检测副本数据的一致性，若检测到不一致则进行修复需要注意的是，因为写时修复不需要做数据一致性对比，性能消耗比较低，对系统运行影响也不大，所以推荐在实现最终一致性时优先选择这种方式。而读时修复和异步修复需要做数据一致性对比，性能消耗比较多，所以在开发实际系统时，建议尽量优化一致性对比的算法，以降低性能消耗，避免对系统运行造成影响。另外，再补充一点，在实现最终一致性的时候，推荐同时实现自定义写一致性级别(比如All、Quorum、One、Any)，让用户可以自主选择相应的一致性级别，比如可以通过设置一致性级别为All来实现强一致性。现在，相比你已经了解了BASE理论的核心内容了吧？不过这只是理论层面的，那么在实践中，我们该如何使用BASE理论呢？

注意。BASE理论是对CAP中一致性和可用性权衡的结果，它来源于对大规模互联网分布式系统实践的总结，是基于CAP定理逐步演化而来的。它的核心思想是，如果非必需，不推荐实现事务或强一致性，鼓励优先考虑可用性和性能，根据业务的场景特点来实现非常弹性的基本可用，以及实现数据的最终一致性。

如何使用BASE理论。以InfluxDB系统中DATA节点的集群实现为例。DATA节点的核心功能是读和写，所以基本可用是指读和写的基本可用。我们可以通过分片和多副本实现读和写的基本可用。也就是说，将同一业务的数据先分片，再以多份副本的形式分布在不同的节点上。如图所示。除非这个3节点2副本的DATA集群超过一半的节点都发生故障，否则是能保障所有数据的读写的。那么，如何实现最终一致性呢？就像上文提到的，我们可以通过写时修复和异步修复实现最终一致性。另外可以同时实现自定义写一致性级别，如支持All、Quorum、One、Any4种写一致性级别，用户在写数据的时候，可以根据业务数据特点，设置不同的写一致性级别。

注意。对于任何集群而言，不可预知的故障的最终后果都是系统过载，所以，如何设计过载保护，实现系统在过载时的基本可用，时开发和运营互联网后天的分布式系统的重中之重。建议在开发实现分布式系统前就要充分考虑如何实现基本可用

BASE理论:CAP的\"碱\

CAP理论

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

你需要了解的3种角色。在Basic Paxos中有提议者(Proposer)、接收者(Acceptor)、学习者(Learner)3种角色，它们之间的关系如图所示。提议者: 提议一个值，用于投票表决。为了方便理解，你可以把上图中的客户端1和客户端2看作提议者。但在绝大多数场景中，集群中收到客户端请求的节点菜是提议者，这样做的好处是，对业务代码没有入侵性，也就是说，我们不需要在业务代码中实现算法逻辑，就可以像使用数据库一样访问后端的数据接受者:对每个提议的值进行投票，并存储接受的值，比如A、B、C3个节点，一般来说，集群中的所有节点，都在扮演接受者的角色，参与共识协商，并接受和存储数据学习者:被告知投票的结果，接受达成共识的值并存储该值，不参与投票的过程，一般来说，学习者是数据备份节点，比如Master-Slave模型中的Slave，被动地接受数据，容灾备份。你可能会疑惑:前面不是说接收客户端请求的节点是提议者吗？这里怎么又说该节点是接受者呢？这是因为一个节点(或进程)可以身兼多个角色。想象一下，一个3节点的集群，1个节点收到了请求，那么该节点将作为提议者发起二阶段提交，然后这个节点还会和另外两个节点一起作为接受者进行共识协商，如图所示。其实，这3种角色在本质上代表的是3种功能:1.提议者代表接入和协调功能，收到客户端请求后，发起二阶段提交，进行共识协商；2.接受者代表投票协商和存储数据功能，对提议的值进行投票，接受达成共识的值并存储该值3.学习者代表存储数功能，不参与共识协商，只接受达成共识的值并存储该值因为一个完整的算法过程是由这3种角色对应的功能组成的，所以理解这3种角色是理解Basic Paxos如何就提议的值达成共识的基础

1.准备节点。先来看第一个阶段，首先，客户端1、2作为提议者，分别向所有接受者发送包含提案编号的准备请求，如图所示。需要注意的是，准备请求中不需要指定提案的值，只需要携带提案编号就可以了，这也是很多人容易产生误解的地方。接着，节点A、B收到提案编号为1的准备请求，节点C收到提案编号为5的准备请求后，将进行如图所示的处理。由于之前没有通过任何提案，所以，节点A、B将返回一个\"尚无提案\"的响应，也就是说，节点A和B在告诉提议者，我之前没有通过任何提案，并承诺以后不再响应提案编号小于或等于1的准备请求，也不会通过编号小于1的提案。节点C也是如此，它将返回一个\"尚无提案\"的响应，并承诺以后不再响应提案编号小于等于5的准备请求，也不会通过编号小于5的提案。另外，节点A、B收到提案编号为5的准备请求，节点C收到提案编号为1的准备请求后将进行如图所示的处理过程。当节点A、B收到提案编号为5的准备请求时，因为提案编号5大于它们之前响应的主备请求的提案编号1，而且两个节点都没有通过任何提案，所以，节点A、B.将返回一个\"尚无提案\"的响应，并承诺以后不再响应提案编号小于等于5的准备请求，也不会通过编号小于5的提案。当节点C收到提案编号为1的准备请求时，由于提案编号1小于它之前响应的准备请求的提案编号5，所以节点C将丢弃该准备请求，不做响应

注意。本质上而言，提案编号的大小代表着优先级，你可以这么理解，根据提案编号的大小，接受者保证3个承诺，具体来说:1.如果准备请求的提案编号小于或等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求；2.如果接受请求中的提案编号小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；3.如果接受者之前有通过提案，那么接受者将承诺准备请求的响应中会包含已经通过的最大编号的提案信息

2.接受阶段.第二个阶段也就是接受阶段，首先，客户端1、2在收到大多数节点的准备请求之后，会分别发送接受请求，如图所示.客户端1收到大多数的接受者(节点A、B)的准备响应后，会根据响应中的提案编号最大的提案的值设置接受请求中的值。因为该值在来自节点A和B的准备响应都为空(\"尚无提案\

领导者。我们可以通过引入领导者(Leader)节点来解决第一个问题。也就是说将领导者节点作为唯一提议者，如图所示。这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况了。这里补充一点:在论文中，兰伯特没有说如何选举领导者，需要我们在实现Multi-Paxos算法的时候自己实现。比如Chubby中的主节点(也就是领导者节点)是通过执行Basic Paxos算法进行投票选举产生的，那么如何解决第二个问题，也就是如何优化Basic Paxos执行呢

优化Basic Paxos执行过程。我们可以采用\

Chubby是如何实现Multi-Paxos算法的既然兰伯特只是大概地介绍了Multi-Paxos思想，那么Chubby是如何补充细节，实现Multi-Paxos算法的呢？首先，它通过引入主节点，实现了兰伯特提到地领导者节点地特性。也就是说，主节点作为唯一提议者，这样就不存在多个提议者同时提交提案的情况，也就不存在提案冲突的情况。另外，在Chubby中，主节点是通过执行Basic Paxos算法进行投票选举产生的，并且在运行过程中，主节点会通过不断续租的方式来延长租期(Lease)。比如在实际场景中，某节点在数天内都是同一个节点作为主节点。如果主节点故障了，那么其他节点会投票选出新的主节点，也就是说主节点一直存在，而且是唯一的。其次，Chubby实现了兰伯特提到的，\"当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段\

注意。Basic Paxos是经过证明的，而Multi-Paxos是一种思想，缺失实现算法的必须编程细节，这就导致Multi-Paxos的最终算法实现是建立在一个未经证明的基础之上，其正确性有待验证。换句话说，实现Multi-Paxos算法的最大挑战是如何证明它是正确的。比如Chubby的作者做了大量的测试，运行一致性检测脚本，以验证和观察系统的健壮性。在实际使用时，不推荐设计和实现新的Multi-Paxos算法，而是建议优先考虑Raft算法，因为Raft的正确性是经过证明的。当Raft算法不能满足需求时，再考虑实现和优化Multi-Paxos算法

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

Paxos算法

概述。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算法支持跟随者、候选人和领导者3种状态。为了方便理解，我们使用不同的图形表示不同的状态，如图u宋史，在任何时候，每一个服务器节点都处于这3个状态中的其中1个1.跟随者:相当于普通群众，默默地接收和处理来自领导者的消息，当领导者心跳信息超时的时候，它会主动站出来，推荐自己当候选人2.候选人:候选人将向其他节点发送请求投票(RequestVote) RPC消息，通知其他节点来投票，如果它赢得了大多数选票，那么它将晋升为领导者3.领导者:一切以我为准，平常的主要工作包含三部分，处理写请求、管理日志复制和不断发送心跳信息，通知其他节点\"我是领导者，你们现在不要发起新的选举，找个新领导者来替代我\"需要注意的是，Raft算法是强领导者模型，集群中只能有一个\"霸道总裁\"。

节点间如何通信。在Raft算法中，服务器节点采用地沟通方式是远程过程调用(RPC)，在领导者选举中，我们需要用到这样两类RPC:1.请求投票(RequestVote)RPC时由候选人在选举期间发起，通知各节点进行投票2.日志复制(AppendEntries)RPC是由领导者发起地，用来复制日志和提供心跳消息需要注意的是，日志复制RPC只能由领导者发起，这是实现强领导者模型的关键之一，理解这一点有助于后续更好地理解日志复制，以及如何实现日志的一致

什么是任期。我们知道，议会选举中的领导者是有任期的，当领导者任命到期后，需要重新再次选举。Raft算法中的领导者也是有任期，每个任期由单调递增的数字(任期编号)标识。比如，节点A的任期编号是1。任期编号会随着选举的举行而变化，分析如下。1.跟随者在领导者心跳信息超时并推荐自己为候选人时，会增加自己的任期编号，比如节点A的当前任期编号为0，那么在推荐自己为候选人时，它会将自己的任期编号增加为1。2.如果一个服务器节点发现自己的任期编号比其他节点小，那么它会更新自己的编号到较大的编号值。比如节点B的任期编号是0，当受到来自节点A的请求投票RPC消息时，因为消息中包含了节点A的任期编号，且编号为1，所以节点B将把自己的编号更新为1.与现实议会选举中的领导者的任期不同，Raft算法中的任期不只是指时间段，而且任期编号的大小会影响领导者选举和请求的处理。1.Raft算法中约定，如果一个候选人或者领导者发现自己的任期编号比其他节点小，那么它会立即恢复成跟随者状态。比如分区错误恢复后，任期编号为3的领导者节点B收到来自新领导者的包含任期编号为4的心跳信息，那么节点B将立即恢复成跟随者状态2.Raft算法中还约定，如果一个节点接收到一个包含较小的任期编号值得请求，那么它会直接拒绝这个请求。比如任期编号为4的节点C在收到任期编号为3的请求投票RPC消息时，会拒绝这个消息。可以看到，Raft算法中的任期比议会选举中的任期要复杂一些。同样，Raft算法中的选举规则的内容也会比较多

选举有哪些规则。在议会选举中，比成员身份、领导者的任期还重要的就是选举的规则，比如一人一票、弹劾制度等。\"无规矩不成方圆\"，Raft算法中也约定了选举规则，主要包含以下内容。1.领导者周期性的向所有跟随者发送心跳消息(即不包含日志项的日志复制RPC消息)，通知大家我是领导者，阻止跟随者发起新的选举。2.如果在指定时间内，跟随者没有接收到来自领导者的消息，那么它就认为当前没有领导者，同时推荐自己为候选人，发起领导者选举。3.在一次选举中，赢得大多数选票的候选人将晋升为领导者4.在一个任期内，领导者一直都会是领导者，直到它自身出现问题(比如宕机)或者网络延迟，其他节点才会发起一轮新的选举。5.在一次选举中，每一个服务器节点最多会对一个任期编号透出一张选票，并且按照\"先来先服务\

选举过程四连问。老话说，细节是魔鬼。这些细节也是大家在学习Raft算法时比较难掌握地，所以这里有必要具体分析一下。一步步来

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

如何复制日志。你可以把Raft算法的日志复制理解成一个优化后的二阶段提交(将二阶段优化成了一阶段)。优化后减少了一半的往返消息，也就是降低了一半的消息延迟，那日志复制的具体过程又是什么呢？首先，领导者进入第一阶段，通过日志复制RPC消息将日志项复制到集群中的其他节点上。接着如果领导者接收到大多数的\"复制成功\"响应后，它会将日志项应用到它的状态机，并返回成功给客户端。如果领导者没有接收到大多数的\"复制成功\"响应，那么就返回错误给客户端。有人可能会有这样的疑问，领导者将日志项应用到它的状态机，为什么没有通知跟随者应用日志项呢？这是Raft算法实现的一个优化，即领导者不需要直接发送消息通知其他节点应用指定日志项。因为领导者的日志复制RPC或心跳消息包含了当前最大的、将会被提交(Commit)的日志项索引值，所以通过日志复制RPC消息或心跳消息，跟随者就可以知道领导者的日志提交位置信息。因此，当其他节点接收到领导者的心跳消息或者新的日志复制RPC消息后，它就会把这条日志项应用到它的状态机，从而降低了处理客户端请求一半的消息延迟。如图所示是Raft算法的日志复制的实现过程示意图。1.接收到客户端请求后，领导者基于客户端请求中的指令创建一个新日志项，并附加到本地日志中2.领导者通过日志复制RPC消息将新的日志项复制到其他服务器3.当领导者将日志项成功复制到大多数的服务器上时，领导者会将这条日志项应用到它的状态机中4.领导者将执行的结果返回给客户端5.当跟随者接收到心跳信息或者新的日志复制RPC消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没应用，那么跟随者就会将这条日志项应用到本地的状态机中。不过这是一个理想状态的日志复制。在实际环境中，你可能会遇到进程崩溃、服务器宕机等问题，导致日志不一致。那么在这种情况下，Raft算法是如何处理不一致，实现日志的一致的呢？

如何实现日志的一致性。在Raft算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是说，Raft算法是通过以领导者的日志为准，来强制实现各节点日志的一致的。具体分为以下两个步骤。1.领导者通过日志复制RPC消息的一致性检查，找到跟随者节点上与自己相同的日志项的最大索引值。也就是说，领导者和跟随者的日志在这个索引值之前是一致的，在之后的日志是不一致的。2.领导者强制跟随者更新不一致的日志项，以实现日志的一致性。下面我们来详细走一遍这个过程，如图苏轼，为了方便演示，我们引入两个新变量.1.PrevLogEntry:表示当前要复制的日志项的前面一条日志项的索引值。比如在图中的，如果领导者将索引值为8的日志项发送给跟随者，那么此时PrevLogEntry值为72.PrevLogTerm:表示当前要复制的日志项的前面一条日志项的任期编号，比如图中的，如果领导者将索引值为8的日志项发送给跟随者，那么此时PrevLogTerm值为4领导者处理不一致的具体实现过程分析如下:1.领导者通过日志复制RPC消息，发送当前最新日志项到跟随者(为了演示方便，假设当前需要复制的日志项是最新的)，这个消息的PrevLogEntry值为7，PrevLogTerm值为42.如果跟随者在它的日志中找不到与PrevLogEntry值为7、PrevLogTerm值为4的日志项，也就是说它的日志和领导者的不一致，那么跟随者就拒绝接收新的日志项，并返回失败给领导者3.这时，领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者，新的日志项的PrevLogEntry值为6，PrevLogTerm值为3.4.如果跟随者在它的日志中找到了PrevLogEntry值为6、PrevLogTerm值为3的日志项，那么日志复制RPC消息返回成功，这样一来，领导者就知道在PrevLogEntry值为6、PrevLogTerm值为3的位置，跟随者的日志项与自己的日志项相同。5.领导者通过日志复制RPC消息复制并更新该索引值之后的日志项(也就是不一致的日志项)，最终实现集群个节点日志的一致。从上面步骤可以看到，领导者通过日志复制RPC消息的一致性检查，找到跟随者节点上与自己相同的日志项的最大所引致。然后复制并更新该索引值之后的日志项，实现各节点日志的一致。需要注意的是，跟随者中的不一致的日志项会被领导者的日志覆盖，而且领导者从来不会覆盖或者删除自己的日志。

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

成员变更问题。在我看来，上图所示的集群中进行成员变更的最大风险是，可能会同时出现两个领导者。比如在进行成员变更时，节点A、B、C之间发生了分区错误，节点A、B组成旧配置中的\"大多数\"，也就是变更前的3节点集群中的\"大多数\"，那么这时的领导者(节点A)依旧是领导者。然后，节点C和新节点D、E组成了新配置的\"大多数\"，也就是变更后的5节点集群中的\"大多数\"，它们可能会选举出新的领导者(比如节点C)。那么这时旧出现了同时存在两个领导者的情况，如图所示两个领导者违背了\"领导者的唯一性\"的原则，进而影响到集群的稳定运行。如何解决这个问题呢？也许有人想到下面这种解决办法。集群在启动时的配置是固定的，不存在成员变更，此时，Raft算法的领导者选举能保证只有一个领导者，也就是说，这时不会出现多个领导者的问题，那么我们是否可以先将集群关闭再启动新集群，即先关闭节点A、B、C组成的集群，待成员变更后，再启动由节点A、B、C、D、E组成的新集群?在我看来，这个方法不可行。为什么呢？因为每次变更都要重启集群，意味着在集群变更期间服务不可用，这势必会影响用户体验。想象以下，你正在玩王者荣耀，但时不时会受到系统弹出的对话框，通知你，系统升级，游戏暂停3分钟。这种体验糟糕不糟糕?既然这种办法影响用户体验，根本行不通，那应该怎样解决成员变更的问题呢？最常用的方法就是单节点变更。注意。成员变更的问题主要在于成员变更时，可能存在新旧配置的两个\"大多数\"，导致集群中同时出现两个领导者，破坏了Raft算法的领导者的唯一性原则，影响了集群的稳定运行

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

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算法

```cpackage mainimport (\"flag\"\"fmt\")var keysPtr = flag.Int(\"keys\

```cpackage mainimport (\"flag\"\"fmt\"\"log\"\"stathat.com/c/consistent\"\"strconv\")var keysPtr = flag.Int(\"keys\

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算法又有什么不一样呢？

一致哈希算法

注意。说到ZAB协议，很多人可能有这样的疑问:为什么ZAB协议的作者在\"Zab vs. Paxos\"宣称ZAB协议不是Paxos算法，但又有很多资料提到ZAB协议是Multi-Paxos算法呢？究竟该如何理解呢？我的看法是，你可以把它理解为Multi-Paxos算法。因为技术是发展的，概念的内涵也在变化。ZAB协议与Raft算法(主备、强领导者模型)非常类似，它是作为共识算法和Multi-Paxos算法提出的。当它被广泛接受和认可后，共识算法的内涵也就丰富和发展了，不仅能实现一系列值的共识，还能保证值的顺序性。同样，Multi-Paxos算法不仅指代多次执行Basic Paxos的算法，还能指代主备、强领导者模型的共识算法。当然，在学习技术过程中，我们不可避免地遇到有歧义、有争议地信息，比如，有人提到，\"从网桑搜了搜相关资料，发现大部分资料将谣言传播等同于Gossip协议，也有把反熵等同于Gossip协议地，感到很迷惑\"。这就需要我们不仅要在平时地工作和学习中认真、全面地学习理论，掌握概念地内涵，还要能\"包容\"和\"发展\"着理解技术

注意。ZAB协议的术语众多，而且有些术语表达的是同一个含义，它们有些在文档中出现，有些在代码中出现，你只有准确理解术语，才能更好地理解ZAB协议地原理。这里补充一些内容。1.提案(Proposal):进行共识协商地基本单元，可以理解为操作(Operation)或指令(Command)，常出现在文档中2.事务(Transaction):也是指提案，常出现代码中。比如，pRequest2Txn()将接收到的请求转换为事务；再比如，未提交提案会持久化存储在事务日志中。这里需要注意的是，这个术语很容易引起误解，因为它不是指更广泛被接受的含义，具有ACID特性的操作序列，而是仅仅指提案

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

ZAB协议支持哪些成员身份。ZAB协议支持3种成员身份，即领导者、跟随者、观察者。1.领导者(Leader):作为主(Primary)节点，在同一时间集群只会有一个领导者。需要注意的是，所有的写请求都必须在领导者节点上执行。2.跟随者(Follwer):作为备份(Backup)节点，集群可以有多个跟随者，它们会响应领导者的心跳消息，并参与领导者选举和提案提交的投票。需要注意的是，跟随者可以直接处理并响应来自客户端的读请求，但对于写请求，则需要将它转发给领导者处理3.观察者(Observer):作为备份(Backup)节点，与跟随者类似，但是没有投票权，也就是说，观察者不参与与领导者选举和提案提交的投票。你可以对比着Paxos中的学习者来理解。需要注意的是，虽然ZAB协议支持3种成员身份，但是它定义了4种成员状态。1.LOOKING:选举状态，该状态下的节点认为当前集群中没有领导者，所以会发起领导者选举2.FOLLOWING:跟随者状态，意味着当前节点是跟随者3.LEADING:领导者状态，意味着当前节点是领导者4.OBSERVING:观察者状态，意味着当前节点是观察者。为什么多了一种成员状态呢？这是因为ZAB协议支持领导者选举，而选举过程涉及一个过渡状态(也就是选举状态)

ZAB协议是如何选举领导者的。既然要选举领导者，那就会涉及成员身份变更，那么ZAB协议支持哪些成员身份呢？

核心流程图

注意。这里只是演示了一种选举情况，还有更多情况需要实践，比如接收到来自逻辑时钟的值比当前节点的值小的节点的投票哦信息，再比如接收到来自领导者的投票信息

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

注意。在ZooKeeper的代码实现中，处于提交状态的提案是可能会改变的，为什么呢？在ZooKeeper中，一个提案进入提交状态的方式有两种:被复制到大多数节点上和被领导者提交或接收到来自领导者的提交消息(leader.COMMIT)而被提交。在这种状态下，提交的提案是不会改变的。另外，在ZooKeeper的设计中，节点在退出跟随者状态时(在follower.shutdown()函数中)会将所有本地未提交的提案都提交。需要注意的是，此时提交的提案可能并未被复制到大多数节点上，而且这种设计会导致ZooKeeper中出现处于\"提交\"状态的提案可能会被删除(也就是接收到领导者的TRUNC消息而删除的提案)的情况。更准确地说，在ZooKeeper中，被复制到大多数节点上地提案最终会被提交，并不会再改变，而只在少数节点存在地提案可能会被提交和不再改变，，也可能会被删除。为了更好地理解，举个具体的例子。如果写请求对应的提案\"SET X=1\"已经复制到大多数节点上，那么它最终会被提交，之后也不会再改变。也就是说，再没有新的X赋值操作的前提下，不管节点怎么崩溃、领导者如何变更，你查询到的X的值都为1。如果写请求对应的提案\"SET X=1\"未被复制到大多数节点上，比如在领导者广播消息过程中，领导者崩溃了，那么提案\"SET X=1\"可能会被复制到大多数节点上提交并不再改变，也可能会被删除。这个行为是未确定的，具体取决于新的领导者是否包含该提案。另外，补充下，在ZAB协议选举出了新的领导者后，该领导者不能立即处理写请求，还需要通过成员发现、数据同步两个阶段进行故障恢复。这是由于ZAB协议的设计决定的，不是所有的共识算法都必须这样，比如通过Raft算法选举出新的领导者后，领导者是可以立即处理写请求的。

ZAB集群如何从故障中恢复。如果我们想把ZAB集群恢复到正常状态，那么新领导者就必须确立自己的领导关系，成为唯一有效的领导者，然后作为主节点\"领导\"各备份节点一起处理读写请求

成员发现。成员发现是通过跟随者和领导者交互来完成的，目标是确保大多数节点对领导者的关系没有异议，也就是确立领导者的领导地位。成员发现的实现流程如图所示。

数据同步。数据同步也是通过跟随者和领导者交互来完成的。目标是确保跟随者节点上的数据与领导者节点上的数据一直。数据同步的实现流程如图所示。

ZooKeeper如何从故障中恢复。

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

举个例子。某集群发生分区故障，节点C与节点A(领导者)、节点B断联，那么节点C将设置自己的状态为LOOKING，此时节点C既不能执行读操作，也不能执行写操作。如图所示，其次，当大多数节点进入广播阶段后，领导者才能提交提案，因为提案提交需要来自大多数节点的确认。最后写请求只能在领导者节点上处理，所以ZooKeeper集群写性能约等于单机。而读请求可以在所有的节点上处理，所以，读性能是水平扩展的。也就是说，你可以通过分集群的方式来突破写性能的限制，并通过增加更加节点来扩展集群的读性能。

ZooKeeper处理读写请求的原理。其实前面已经演示\"如何实现操作顺序性\"时旧已经介绍了ZooKeeper处理读写请求的原理。这里不再赘述，只在前面的基础上补充几点。首先，在ZooKeeper中，与领导者\"失联\

如何实现写操作。在ZooKeeper代码中，处理写请求的核心流程如图所示。这里我用跟随者接收到写请求的情况演示一下。

如何实现读操作。相比写操作，读操作的处理要简单很多，因为接收到度请求的节点只需要查询本地数据，然后响应数据给客户端就可以了。读操作的核心流程如图所示。

ZooKeeper处理读写请求的代码实现。ZooKeeper处理读写请求的具体流程分析如下。

ZAB协议:如何处理读写请求。你应该有这样的体会，如果你想了解一个网络服务，执行的第一个功能肯定是写操作，然后才会执行读操作。比如，你要了解ZooKeeper，那么肯定会在zkClient.sh命令行中执行写操作(比如create /geekbang 123)写入数据，然后再执行读操作(比如get /geekbang)查询数据。这样一来，你才会直观地理解ZooKeeper的使用方法。在我看来，任何网络服务最重要的功能就是处理读写请求，因为我们访问网络服务的本质就是执行读写操作，ZooKeeper也不例外，对ZooKeeper而言，这些功能更重要，因为如何处理写请求关乎着操作的顺序性，会影响节点的创建；而如何处理读请求关乎着一致性，也影响着客户端是否会读到旧数据。接下来，会从ZooKeeper系统的角度全面地分析整个读写请求的流程，帮助你更加全面、透彻地理解读写请求背后的原理。我们都知道，在ZooKeeper中，写请求必须在领导者上处理，如果跟随者接收到写请求，则需要将写请求转发给领导者，当写请求对应的提案被复制到大多数节点上时，领导者会提交提案，并通知跟随者提交提案。而读请求可以在任何节点上处理，也就是说，ZooKeeper实现的是最终一致性。所以，理解了如何处理读写请求，不仅能理解读写这个最重要功能的核心原理，还能更好地理解ZooKeeper的性能和一致性。这样在实际场景中安装部署ZooKeeper的时候，就能游刃有余地做资源规划了。比如，如果度请求比较多，可以增加节点，如配置5节点集群，而不是常见的3节点集群。

思维拓展。1.在ZAB协议中，主节点是基于TCP协议来广播消息的，且保证了消息接收的顺序性。那么你不妨想想，如果ZAB采用的是UDP协议，能保证消息接收的顺序性吗？为什么呢？答案:ZAB(ZooKeeper Atomic Broadcast)协议是ZooKeeper分布式协调服务中用于实现分布式系统间一致性的一种协议。在ZAB协议中，主节点(Leader)负责将消息广播给所有从节点(Followers)，确实保证了消息接收的顺序性，这是通过TCP协议的连接性和确认机制来实现的。如果ZAB协议采用UDP协议来广播消息，那么消息接收的顺序性将无法得到保证。这是因为UDP(用户数据报协议)是一种无连接的协议，它不保证数据保的顺序、可靠传输或者数据的完整性。在UDP中，数据包(datagrams)可能会丢失、重复或乱序到达。这些特性使得UDP在高速传输但可以容忍一定数据丢失的应用场景中非常有用，比如视频流或在线游戏。在分布式系统中消息的顺序性是非常重要的，因为它涉及到系统的一致性和状态同步。如果消息顺序无法保证，可能会导致系统状态的不一致，从而影响整个分布式系统的正确性。因此，如果ZAB协议基于UDP来实现，就需要引入额外的机制来确保消息的顺序性，例如:1.1 序列号:为每个消息分配一个序列号，接收方根据序列号重新排序消息1.2 确认和重传:接收方对于收到的消息进行确认，发送方对于未确认的消息进行重传1.3 选择性重传:只重传哪些确认丢失的消息这些机制会增加协议的复杂性，并且可能会降低系统的性能。因此，在设计分布式协议时，通常会根据应用的需求来选择合适的传输协议，对于需要强一致性的系统，如ZooKeeper，使用TCP是更合适的选择2.ZAB协议是通过快速领导者选举来选举出新的领导者的。那么选举中会出现选票被瓜分、选举失败的问题吗？为什么?答案:因为存在任期编号大的优先、zxid较大节点优先、zxid相同，服务器id较大的节点优先3.提案提交的大多数原则和领导者选举的大多数原则，确保了被复制到大多数节点的提案不再改变。那么你不妨思考和推演一下，这是为什么?答案:\"大多数\"原则在提案提交和领导者选举中都起到了确保系统一致性、容错能力和稳定性的关键作用4.ZooKeeper提供的是最终一致性，读操作可以在任何节点上执行。如果读操作访问的是备份节点，为什么无法保证每次都能读到最新的数据呢？答案:有可能备份节点还没有收到领导者的提交响应，所以存在延迟

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算法也都有领导者，难道实现一致性就必须要领导者吗？没有领导者就无法实现一致性吗？其实有些没有领导者的算法也能实现一致性

ZAB协议

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

直接邮寄。是指直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。如图所示，节点A直接将更新数据发送给了节点B、D.在这里补充一点，直接邮寄虽然实现起来比较容易，数据同步也很及时，但可能会因为缓存队列满了而丢失数据。也就是说，只采用直接邮寄是无法实现最终一致性的。

推方式是指将自己的所有副本数据推给对方，以修复对方的数据副本中的熵，如图所示

拉方式是指拉取对方的所有副本数据，以修复自己的数据副本中的熵，如图所示

理解了推方式和拉方式之后，推拉方式就很好理解了，它是指同时修复自己和对方的数据副本中的熵。如图所示

谣言传播，即广泛地散播谣言，是指当一个节点有了新数据后，这个节点就会变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据。如图所示。节点A向节点B、D发送新数据，节点B收到新数据后变成活跃节点，然后节点B向节点C、D发送新数据。其实，谣言传播非常具有传染性，它适合动态变化的分布式系统。

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

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

重点总结。1.Gossip协议作为一种异步修复、实现最终一致性的协议，反熵再存储组件中应用广泛，比如Dynamo、InfluxDB、Cassandra，在需要实现最终一致性的实际工作场景中，优先考虑反熵2.因为谣言传播具有传染性，如一个节点传给了另一个节点，另一个节点又将充当传播者，传给其他节点，所以非常适合动态比那花的分布式系统，比如Cassandra3.一般而言，在实际场景中实现数据副本的最终一致性时，直接邮寄的方式是一定要实现的，因为不需要做一致性对比，只需要通过发送更细年数据或重传缓存来修复数据，新跟那个损耗低。在存储组件中，节点都是已知的，一般采用反熵修复数据副本的一致性。当集群节点是变化的，或者集群节点数比较多时，这时要采用谣言传播的方式更新数据，实现最终一致性。如果我们在实际场景中涉及了一套AP型分布式系统，并通过反熵实现了各数据副本的最终一致性，且系统也在线上稳定地运行着，此时突然有同时提出希望数据写入成功后，能立即读取到新数据需求，也就是要实现强一致性，这时我们该怎么呢？难道我们必须推倒架构，一切从头再来？

Gossip协议

概述。不知道你在工作中有没有遇到过这样的事情:你开发实现了一套AP型分布式系统，实现了最终一致性，且业务接入后运行正常，一切看起来都那么美好。可是突然有同事说，我们要拉这几个业务的数据做实时分析，希望数据写入成功后，就能立即读取到新数据，也就是要实现强一致性(Werner Vogels提出的客户端侧一致性模型，不是指线性一致性)，即数据更改后，要保证用户能立即查询到，这时你该怎么办呢？首先你要明确最终一致性和强一致性有什么区别.1.强一致性能保证写操作完成后，任何后续访问都能读到更新后的值。2.最终一致性只能保证如果对某个对象没有新的写操作了，最终所有后续访问都能读到相同的最近更新的值。也就是说，写操作完成后，后续访问可能会读到旧数据。其实，为了一个临时的需求而重新开发一套系统或者迁移数据到新系统肯定是不合适的。因为工作量比较大，而且耗时也长，所以建议通过Quorum NWR算法解决这个问题。通过Quorum NWR算法，我们可以自定义一致性级别，通过临时调整写入或者查询的方式满足新需求，当W+R>N时，就可以实现强一致性了。也就是说，在原有系统上开发并实现一个新功能，即可满足业务同事的需求。其实，在AP型分布式系统中(如Dynamo、Cassandra、InfluxDB企业版的DATA节点集群)，Quorum NWR算法时通常都会实现的一个功能，很常用。掌握了Quorum NWR算法，不仅可以掌握一种常用的、实现一致性的方法，而且可以在后续的实际场景中根据业务的特点，灵活地指定一致性级别。

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

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

Quorum NWR算法

注意。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 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能解决指令执行的原子性问题呢？

TCC

概述。谈起比特币，你应该并不陌生。比特币是基于区块链实现的，而区块链运行在因特网上，这就存在有人试图作恶的情况。有些读者可能已经发现了，口信消息型拜占庭问题之解、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字节的哈希值，如代码所示```cecho -n \"geektime\" | sha256sumbb2f0f297fe9d3b8669b6b4cec3bff99b9de596c46af2e4c4a504cfe1372dc52```那我们如何通过哈希函数进行哈希运算，从而证明工作量呢？这里举个具体的例子帮助大家理解。我们给出的工作量要求是，给定一个基本的字符串(比如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环境。我们要理解两类算法之间的差异，根据场景特点，选择合适的算法，保障业务高效、稳定的运行

PoW算法

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 这确保了在领导者宕机后，新的领导者也能知道哪些操作是已经被提交的，从而保证操作的顺序性

疑惑的问题

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

coherence。Coherence只出现在Cache Coherence一词中，称为\"缓存一致性\"，研究多核场景，即怎么保证多个核上的CPU缓存数据是一致的。一般是单机维度的，不算分布式领域

Paxos与Raft。Paxos其实是一类协议，Paxos中包含Basic Paxso、Multi-Paxos、Cheap Paxos和其他的变种。Raft就是Multi-Paxos的一个变种，Raft通过简化Multi-Paxos的模型，实现了一种更容易让人理解和工程实现的共识算法，Paxos是第一个被证明完备的共识算法，能够让分布式网络中的节点出现错误时仍然保持一致，当然前提是没有恶意节点，也就是拜占庭将军问题。在传统的分布式系统领域是不需要担心这种问题的。因为不论是分布式数据库、消息队列、分布式存储，你的机器都不会故意发送错误信息，最常见的问题反而是节点失去响应，所以它们在这种前提下，Paxos是足够用的

复制状态机。Consensus共识在实现机制上属于复制状态机(Replicated State Machine)的范畴，复制状态机是一种很有效的容错技术，基于复制日志来实现，每个Server存储着一份包含序列的日志文件，状态机会按顺序执行这些命令。因为日志中的命令和顺序都相同，因此所有节点会得到相同的数据。因此保证系统一致性就简化为保证操作日志的一致，这种复制日志的方式被大量运用，如果GSF、HDFS、ZooKeeper和etcd都是这种机制。

区块链。共识算法还有一个很重要的领域，就是比较火的区块链，比如工作量证明(POW)、权益证明(POS)和委托权益证明(DPOS)、置信度证明(POB)等等，都是共识算法。大家熟知的zk、etcd这种之所以叫\"传统分布式\"，就是相对于区块链这种\"新型分布式系统\"而言的，都是多节点共同工作，只是区块链有几点特殊:1.区块链需要解决的是拜占庭将军问题，Paxos之类的一致性算法无法对抗欺诈节点2.区块链中不存在中央空置房，没有一个节点可以控制或协调账本数据的生成3.区块链中的共识算法如果达不到一致性，则任何人都可以硬分叉，另建一个社区、一条链4.分布式系统的性能理论上可以无限提升，但是区块链是以相对的低效率来换取公正，主流的公有链每秒只能处理几笔到几十笔交易

consensus。consensus准确的翻译是共识，即多个提议者达成共识的过程，例如Paxos，Raft就是共识算法，Paxos是一种共识理论，分布式系统是他的场景，一致性是他的目标。一些常见的误解:使用了Raft或者Paxos的系统都是线性一致的(Linearizability即强一致)，其实不然，共识算法只能提供基础，要实现线性一致还需要在算法之上做出更多的努力。因为分布式系统引入了多个节点，节点规模越大、宕机、网络时延、网络分区就会成为常态，任何一个问题都可能导致节点之间的数据不一致，因此Paxos和Raft准确来讲是用来解决一致性问题的共识算法，用于分布式场景，而非\"缓存一致性\"这种单机场景。所以很多文章也就简称\"Paxos是分布式系统中的一致性算法\"。一致性(Consistency)的含义比共识(Consensus)要宽泛，一致性指的是多个副本对外呈现的状态。包括顺序一致性、线性一致性、最终一致性等。而共识特指达成一致的过程，但注意，共识并不意味着实现了一致性，一些情况它是做不到的

背景。如买最后一张车票，两个售票处分别通过某种方式确认过这张票的存在。这时，两家售票处几乎同时分别来了一个乘客要买这张票，从各自\"观察\"看来，自己一方的乘客都是先到的，这种情况下，怎么能达成对结果的共识呢？看起来很容易，卖给物理时间上率先提交请求的乘客即可。然而，对于两个来自不同位置的请求来说，要判断在时间上的\"先后\"关系并不是那么容易。两个车站的时钟时刻可能是不一致的。时钟计时可能不精确的。根据相对论的观点，不同空间位置的时间是不一致的。因此追求绝对时间戳的方案是不可行的，能做的是要对事件的发生进行排序。这也是解决分布式系统领域很多问题的核心秘诀，把不同时空发生的多个事件进行全局唯一排序，而这个顺序还得是大家都认可的。排了序，一个一个处理就行了，和单机没有任何区别(不考虑突然故障情况，只考虑共识机制)如果存在可靠的物理时钟，实现排序往往更为简单。高精度的石英钟的漂移率为10的-7次方，最准确的原子震荡时钟的漂移率为10的-13次方。Google曾在其分布式数据库Spanner中采用基于原子时钟和GPS的\"TrueTIme\"方案，能够将不同数据中心的事件偏差控制在10ms知心区间。在不考虑成本的前提下，这种方案简单、有效。然而，计算机系统的时钟误差要大得多，这就造成分布式系统达成一致顺序十分具有挑战性，或者说基本不可能。要实现绝对理想的严格一致性(Strict Consistency)代价很大。除非系统不发生任何故障，而且所有节点之间的通信无需任何时间，此时整个系统其实就等价于一台机器了，因此根据实际需求的可用，人们可能选择不同强度的一致性。

举例说明

顺序一致性(Sequential Consistency).虽然强度上 线性一致性 > 顺序一致性，但因为顺序一致性出现的时间比较早(1979年)，线性是在顺序的基础上的加强(1990年)。因此先介绍下 顺序一致性。顺序一致性也算强一致性的一种，它的原理比较晦涩。

线性一致性(Linearizability).线性一致性又被称为强一致性、严格一致性、原子一致性。是程序能实现的最高的一致性模型，也是分布式系统用户最期望的一致性。CAP中的C一般就指它。顺序一致性中进程只关心大家认同的顺序一样就行，不需要与全局时钟一致，线性就更严格，从这种偏序(partial order)要达到全序(total order)要求是:1.任何一次读都能读到某个数据的最近一次写的数据2.系统中的所有进程，看到的操作顺序，都与全局时钟下的顺序一致。以前面讲的例3继续讨论:```cB1看到X的新值，C1反而看到的是旧值，即对用户来说，x的值发生了回跳```在线性一致的系统中，如果B1看到的x值为1，则C1看到的值也一定为1。任何操作在该系统生效的时刻都对应时间轴上的一个点。如果我们把这些时刻连接起来，如图中紫线所示，则这条线会一致沿时间轴向前，不会反向回跳。所以任何操作都需要互相比较决定，谁发生在前，谁发生在后。例如B1发生在A0之前，C1发生在A0之后，而在前面顺序一致性模型中，我们无法比较诸如B1和A0的先后关系。线性一致性的理论在软件上有哪些体现呢？

因果一致性Causal Consistency因果一致性，属于弱一致性，因为在Causal Consistency中，只对有因果关系的事件有顺序要求。没有因果一致性时会发生如下情形:1.夏侯铁柱在朋友圈发表状态:\"我戒指丢了\"2.夏侯铁柱在同一条状态下评论\"我找到了\"3.诸葛建国在同一条状态下评论\"太棒了\"4.远在美国的键盘侠看到\"我戒指丢了\" \"太棒了\"，开始喷诸葛建国5.远在美国的键盘侠看到\"我戒指丢了\" \"我找到啦\" \"太棒了\"，意识到喷错人了。所以很多系统采用因果一致性系统来避免这种问题，例如微信的朋友圈就采用了因果一致性

最终一致性Eventual Consistency.最终一致性这个词大家听到的次数应该是最多的，也是弱一致性，不过因为大多数场景下用户可以接受，应用也就比较广泛。理念:不保证在任意时刻任意节点上的同一份数据都是相同的，但是随者事件的迁移，不同节点上的同一份数据总是在向趋同的方向变化。简单说，就是在一段时间后，节点间的数据会最终达到一致状态。不过最终一致性的要求非常低，除了向Gossip这样明确以最终一致性为卖点的协议外，包括Redis主备、MongoDB、乃至MySQL热备都可以算是最终一致性，甚至如果我记录操作日志，然后在副本故障了100天之后手动在副本上执行日志以达成一致，也算是符合最终一致性的定义。有人说最终一致性就是没有一致性，因为没人可以知道什么时候算是最终。上面提到的因果一致性可以理解为是最终一致性的变种，如果进程A通知进程B它已经更新了一个数据项，那么进程B的后续访问将返回更新后的值，并且写操作将被保证取代前一次写入。和进程A没有因果关系的C的访问将遵循正常的最终一致性规则。最终一致性其实分支很多，以下都是它的变种:1.Causal Consistency(因果一致性)2.Read-your-writes Consistency(读自己所写一致性)3.Session Consistency(会话一致性)4.Monotonic Read Consistency(单调读一致性)5.Monotonic Write Consistency(单调写一致性)后面要提到的BASE理论中的E，就是Eventual Consistency最终一致

CAP理论。CAP理论中的C也就是我们常说的分布式系统中的一致性，更确切地说，指的是分布式一致性中地一种:也就是前面说地线性一致性(Linearizability)也叫做原子一致性(Atomic Consistency).CAP理论也是个被滥用地词汇，很多时候我们会用CAP模型去评估一个分布式系统，但是CAP模型却有一定的局限性。因为按照CAP理论，很多系统MongoDB、ZooKeeper既不满足(线性一致性)，也不满足可用性(任意一个工作中的节点都要可以处理请求)，但这并不意味着它们不是优秀的系统，而是CAP定理本身的局限性(没有考虑处理延迟，容错等)

BASE理论。正因为CAP中的一致性和可用性是强一致行和高可用，后来又有人基于CAP理论提出了BASE理论，即基本可用(Basicly Available)、软状态(Soft State)、最终一致性(Eventual Consistency).BASE的核心思想是即使无法做到强一致性，但每个应用都可以根据自身的业务特点，采用适当的方法来使系统达到最终一致性。显然最终一致性弱于CAP中的线性一致性。很多分布式系统都是基于BASE中的\"基本可用\"和\"最终一致性\"来实现的，比如MySQL/PostgreSQL Replication异步复制

ACID一致性与CAP一致性的区别.ACID一致性使有关数据库规则，如果数据表结构定义一个字段值是唯一的，那么一致性系统将解决所有操作中导致这个字段值非唯一的情况，如果带有一个外键的一行记录被删除，那么其外键相关记录也应该被删除，这就是ACID一致性的意思。CAP理论的一致性是保证同样一个数据在所有不同服务器上的拷贝i都是相同的，这是一种逻辑保证，而不是物理，因为光速限制，在不同服务器上这种复制是需要时间的，集群通过阻止客户端查看不同节点上还未同步的数据维持逻辑视图。当跨分布式系统提供ACID是，这两个概念会混淆在一起，Google's Spanner System能够提供分布式系统的ACID，其包含ACID+CAP涉及，也就是两阶段提交2PC+多副本复制机制

ACID/2PC/3PC/TCC/Paxos关系。ACID是处理事务的原则，限定了原子性、一致性、隔离性、持久性。ACID、CAP、BASE这些都只是理论，只是在实现时的目标或者折中，ACID专注于分布式事务，CAP和BASE是分布式通用理论。解决分布式事务有2PC、3PC、TCC等方式，通过增加协调者来进行协商，里面也有最终一致的思想。而Paxos协议与分布式事务并不是同一层面的东西，Paxos用于解决多个副本之间的一致性问题。比如日志同步，保证各个节点的日志一致性，选主的唯一性。简而言之，2PC用于保证多个数据分片上事务的原子性，Paxos协议用于保证同一个数据分片在多个副本的一致性，所以两者可以是互补的关系，不是替代关系。对于2PC协调者单点问题，可以利用Paxos协议解决，当协调者出现问题时，选一个新的协调者继续提供服务，原理上Paxos和2PC相似，但目的上是不同的，etcd中也有事务的操作，比如迷你事务

分布式系统的一致性与共识算法

分布式与一致性协议