

首页  思维导图  详情



分布式与一致性协议相关

2024-08-01 18:36:54   1  举报





AI智能生成

"分布式与一致性协议是一组用于确保分布式系统中数据一致性的机制。这些协议在处理分布式系统中的并发操作和网络延迟等方面发挥关键作用。核心内容包括一致性算法如Paxos、Raft、两阶段提交协议等。这些算法通过在多个节点之间达成共识，确保数据在多个副本中的一致性。此外，分布式系统还需要处理网络分区、节点故障等异常情况，以确保系统的高可用性。常见的修饰语包括：强一致性、弱一致性、最终一致性等。"

Java

分布式一致性

模版推荐

作者其他创作

大纲/内容

拜占庭将军问题

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

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

苏秦的困境。 战国时期，齐、楚、燕、赵、魏、秦七雄并立，后来秦国的势力不断强大， 成为东方六国的共同威胁。于是这六个国家决定联合起来，全力抗秦，以免被 秦国各个击破。一天，苏秦作为合纵长，挂六国相应，带着六国的军队叩关函谷， 驻军在秦国边境，为围攻秦国做准备。但是，因为各国军队分别驻扎在秦国边境 的不同地方，所以军队之间只能通过信使互相联系，这时，苏秦面临一个很严峻的 问题:如何同意作战计划? 万一一些诸侯国暗通秦国，发送误导性的作战信息，怎么办?如果心事被敌人截杀, 甚至被间谍替换了，又该怎么办?这些都会导致自己的作战计划被扰乱，出现有的 诸侯国在进攻，有的诸侯国在撤退的情况，这时，秦国一定会趁机出兵，把它们 逐一击破。 所以，如果达成公式，指定统一的作战计划呢? 这个问题其实是拜占庭将军问题的一个简化表述，也即一个典型的公式难题:如果在 可能有误导信息的情况下，采用合适的通信机制，让多个将军达成公式，制订一致 的作战计划呢?

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

举个例子。这3位将军各自一脸严肃地决定明天是进攻还是撤退，并让信使传递消息， 按照"少数服从多数"的原则投票决定，两个人意见一致就可以了: 1.齐根据侦察情况决定撤退 2.楚和燕根据侦察信息，决定进攻 可是，问题来了:一旦有人暗通秦国，就会出现作战计划不一致的情况。比如齐向楚、燕 分别发送"撤退"的消息，燕向齐和楚发送"进攻"的消息。撤退:进攻 = 1：1，无论楚投 进攻还是撤退，都会成为2:1，这时候还是会形成一个一致的作战方案。 但是，楚这个叛将在暗中配合秦国，让信使向齐发送了"撤退",向燕发送了"进攻",那么: 1.燕看到的是,撤退:进攻=1:2 2.齐看到的是，撤退:进攻=2:1 如图所示，按照少数服从多数的原则，燕单独进攻秦军，最后的结果当然是燕寡不敌众, 被秦军打败了。在这里可以看到，叛将通过发送误导信息，非常轻松地干扰了齐和燕 的作战计划，导致两位终程将军被秦军逐一击破。这也是常说的二忠一叛难题

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

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

在第二轮作战信息协商中，齐、楚、燕分别作为指挥官，向另外两位将军发送作战信息"进攻", 因为楚已经叛变了，所以，为了干扰作战计划，它会发送"撤退"作战指令，如图所示

最终，齐和燕收到的作战信息都是"进攻、进攻、撤退"，按照烧出服从多数的原则，齐、燕和苏秦一起 执行作战指令"进攻",实现了作战计划的一致性，保证了作战的胜利。那么如果是叛将楚先发送作战信息， 干扰作战计划，结果是否会有所不同?在第一轮作战信息协商中，楚向苏秦发送指令"进攻",向齐、燕发送 作战指令"撤退",如图所示

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

这个解决办法其实是在兰伯特在论文"The Byzantine Generals Problem"中提到的口信问题型拜占庭问题之解 (A Solution with Oral Message):如果叛将认数位m,将军任务不能少于3m+1,那么拜占庭将军问题就能解决了， 不过，作者在论文中没有讲清除一些细节: 这个算法有个前提，也就是叛将认数m,或者说能容忍的叛将数m是已知晓的。在这个算法中，叛将数m决定了递归 循环的次数(也就是说，叛将数m决定了将军们要在多少轮作战信息协商)，既m+1轮(例如这里只有楚是叛将，所以 进行了两轮),从另一个角度理解:n位将军，最多能容忍(n-1)/3位叛将 该算法虽然能解决拜占庭将军问题，但它有一个限制，如果叛将认数为m，那么将军总人数必须不小于3m+1. 在二忠一叛欸度问题中，在存在1位叛将的情况下，必须增加1位将军，将3位将军的协商共识转换位4位将军的协商 共识，这样才能实现忠诚将军的一致性作战计划，那么，有没有什么办法可以在不增加将军认数的情况下之解解决 二忠一叛的难题呢?

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

什么是签名消息？ 签名消息是指带有数字签名的消息。数字签名与在纸质合同上进行签名来确认合同内容和证明身份类似。 它既可以证实内容的完整性，又可以确认内容的来源，实现不可抵赖性(Non-Repudiation)。既然数字 签名的优点那么多，那么如何实现签名消息呢? 今天Bob要给Alice发送一条消息，告诉她，"我已经到北京了"。但是Bob希望这个消息能被Alice完整地 接收到，即内容不能被篡改或者伪造。下面我们一起来看看如何帮Bob和Alice想想办法，看看如何发送 这条消息。 首先，为了避免密钥泄漏，我们推荐Bob和Alice使用非对称加密算法(比如RSA),也就是说，加密和解密 使用不同的密钥，在这里，Bob持有需要安全报关的私钥，Alice持有功开的公钥。然后,Bob用哈希算法 (比如MD5)对消息对消息进行摘要(Digest),然后用私钥对摘要进行加密，生成数字签名(Signature),如图所示

接着，Bob将加密摘要和消息一起发送给Alice，如图所示。 接下来，当Alice接收到消息和加密摘要后，它会用自己的公钥对加密摘要进行解密，并对消息内容进行摘要(Digest-2), 然后将新获取的摘要(Digest-2)和解密后的摘要(Digest-1)进行比对，如果两个摘要(Digest-1和Digest-2)一致，就说明 消息是来自Bob，并且是完整的，如图所示。 可以看到，通过这种方法，Bob的消息就能被Alice完整接收到了，任何篡改和伪造Bob消息的行为都会因为摘要不一致 而被发现。而这条消息就是签名消息。 通过上面的Bob和Alice的故事，可以看到，在数字签名的约束下，叛将是无法篡改和伪造忠将的消息的，因为任何篡改 和伪造消息的行为都会被发现，即作恶的行为被约束了。也就是说，叛将虽然能做"小"恶(比如，不想赢消息或者叛将们 相互串通发送指定的消息)，但它们无法篡改或伪造忠将的消息。 既然数字签名约束了叛将们的作恶行为，那么苏秦怎样才能实现作战的一致性呢？

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

忠将先发送消息

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

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

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

叛将先发送消息

如果是叛将楚先发送作战消息，干扰作战计划，结果会有所不同吗？ 在第一轮作战信息协商中，楚向苏秦发送作战指令"进攻",向齐、燕发送作战指令"撤退"，如图所示(当然还有其他情况， 这里指示选择了其中一种，大家也可以尝试推导其他的情况，看看结果是不是一样).

然后在第二轮作战信息协商中,苏秦、齐、燕分别作为指挥官，将接收到的作战信息附加上自己的签名，并转发给另外两位， 如图所示。为了达到干扰作战计划的目的，叛将楚和燕相互勾结了。比如，燕拿到了楚的私钥，也就是燕可以伪造楚的签名， 此时，燕为了干扰作战计划，给苏秦发送作战指令"进攻"，给齐发送作战指令"撤退"

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

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

需要注意的是，签名消息的拜占庭问题之解，也是需要进行m+1轮(其中m为叛将数，即如果只有楚、燕是叛变的,那么 就进行3轮)协商。我们也可以从另外一个角度理解:n位将军，能容忍(n-2)位叛将(只有一位忠将没有意义，因为此时不需要 达成共识)。另外，签名消息型拜占庭问题之解，解决的是忠将们如何就作战计划达成共识的问题，也即只要忠将们执行了 一致的作战计划就可以了，它不关心这个共识是什么，比如在适合进攻的时候，忠将们可能执行的作战计划是撤退，也就是 说这个算法比较理论化。关于这一点，这个算法解决的是共识问题，没有与实际场景结合，是很难在实际场景中落地的。 在实际场景中，可以考虑改进后的拜占庭容错算法，比如PBFT算法

拜占庭容错算法和非拜占庭容错算法,应该如何选择呢？ 为了帮助大家理解拜占庭将军问题，前面讲了苏秦协商作战的故事，现在让我们跳回到 现实世界，回到计算机世界的分布式场景中: 1.故事里的各位将军可以理解为计算机节点 2.忠诚的将军可以理解为正常运行的计算机节点 3.叛变的将军可以理解为出现故障并会发送误导信息的计算机节点 4.信使被杀可以理解为通信故障、信息丢失 5.信使被间谍替换可以理解为通信被中间人攻击，攻击者在恶意伪造信息和劫持通信 需要注意的是，拜占庭将军问题描述的是最困难，也是最复杂的一种分布式故障场景，该场景 除了存在故障行为，还存在恶意行为。在存在恶意行为的场景中(比如在数字货币的区块链技术中)， 我们必须使用拜占庭容错算法还有PBFT算法、POW算法。 在计算机分布式系统中，最常用的是非拜占庭容错算法，即故障容错(Crash Fault Tolerance, CFT)算法。 CFT算法解决的是分布式系统中存在故障，但不存在恶意节点的场景下的共识问题。也就是说，这个 场景可能会丢失消息或者有消息重复，但不存在错误消息或者伪造消息的情况，常见的CFT算法有 Paxos算法、Raft算法、ZAB协议。 那么，如何在实际场景中选择合适的算法类型呢？如果能确定该环境中各节点是可信赖的，不存在篡改 消息或者伪造消息等恶意行为(例如DevOps环境中的分布式寻址系统)，推荐使用非拜占庭容错算法; 反之则推荐使用拜占庭容错算法，例如区块链中使用Pow算法

PBFT算法

概述。 前面提到了拜占庭将军问题之后，有人可能会感到困惑:口信消息型拜占庭问题直接在实际项目中是如何落地的呢？事实上，它很难在实际项目中落地，因为口信消息型拜占庭问题之解是一个非常理论化的算法，没有与实际场景结合，也没有考虑如何在实际场景中落地和实现。 比如，它实现的是在拜占庭错误场景下，忠将们如何在判断干扰时就一致行动达成共识。但是它并不关心结果是什么，这会出现一种情况:现在适合进攻，但将军们达成的最终共识却是撤退。 很显然，这不是我们想要的结果。因为在实际场景中，我们需要就提议的一系列值(而不是单值)，即使在拜占庭错误发生的时候，也能达成共识。那我们应该怎么做呢？答案就是采用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算法中，主节点作恶有如下几种情况: 1.主节点接收到客户端请求后不做任何处理，也就是默不作声 2.主节点接收到客户端请求后给不同的预准备请求分配不同的序号 3.主节点只给部分系欸但发送预准备消息 需要注意的是，不管出现哪种情况，共识都是无法达成的，也就是说，如果恶意节点当选了主节点，此时无论忠诚节点数有多少，忠诚节点们都将无法达成共识。而这种情况肯定是无法接受的，这需要我们设计一个机制，在发现主节点可能作恶时，将作恶的主节点替换掉，并保证最终只有忠诚的节点担任主节点。这样，PBFT算法才能保证当节点数为3f+1(其中f为恶意节点数)时，忠诚的节点们能就客户端提议的指令达成共识，并执行一致的指令。 那么，在PBFT算法中，视图变更是如何选举出新的主节点并替换掉作恶的主节点呢？

如何替换作恶的主节点。 在我看来，视图变更是保证PBFT算法稳定运行的关键。当系统运行异常时，客户端或备份节点出发系统的视图变更，通过"轮流上岗"的方式(公式是 (V+1) mod |R|, 其中v为当前视图的值，|R|为节点数)选出下一个视图的主节点，最终选出一个忠诚、稳定运行的新主节点，并保证了共识的达成。为了更好地理解视图变更的原理，继续以苏秦为例展开分析，这次，咱们把叛徒楚当作"大元帅",让它扮演主节点的角色，如图所示。 首先，苏秦联系楚，向楚发送包含作战指令"进攻"的请求，如图所示。 当楚接收到苏秦的请求之后，为了达到破坏作战计划的目的，它选择默不作声，心想:我就是不执行三阶段协议，不执行你的指令，也不通知其他将军执行你的指令，你能把我怎么办？ 结果，苏秦始终没有接收到两个相同的响应消息。待过了约定的事件后，苏秦会认为也许各位将军们出了什么问题。这时苏秦会直接给各位将军发送作战指令，如图所示。 当赵、魏、韩接收到来自苏秦的作战指令时，它们会将作战指令分别发送给楚，并等待一段时间，如果在这段事件内它们仍未接收到来自楚地预准备消息，那么它们就认为楚可能已经叛变了，并发起视图变更(采用"轮流上岗"的方式选出新的大元帅，比如赵)，向集群所有节点发送视图变更消息，如图所示。 当赵接收到两个视图变更消息后，它就会发送新视图消息给其他将军，告诉大家，我是大元帅了，如图所示。 其他将军在接收到新视图消息后，就认为选出了新的大元帅。然后，忠诚的将军们就可以一致地执行来自苏秦的作战指令了。 你看，叛变的大元帅就这样被发现和替换掉了，而最终大元帅一定是忠诚的。 回到计算机的世界中，我们应该如何理解呢？其实现原理与签名一样，这里不再赘述。不过为了更全面地理解视图变更，补充几点。 首先，当一个备份节点在定时器超时出发了视图变更后，它将暂时停止接收和处理除了检查点(CHECKPOINT)、视图变更、新视图之外的消息。你可以这样理解，这个节点认为现在集群处于异常状态，所以不能再处理客户端请求相关的消息。 其次，除了演示中触发备份节点进行视图变更的情况，下面几种情况也会触发视图变更，列举如下: 1.备份节点发送了准备消息后，在约定的时间内未接收到来自其他节点的2f个相同的准备消息 2.备份节点发送了提交消息后，在约定的时间内危机收到来自其他节点的2f个相同的提交消息 3.备份节点接收到异常消息，比如视图值、序号和已接收的消息相同，但内容摘要不同。 也就是说，视图变更除了能解决主节点故障和作恶的问题，还能避免备份节点长时间阻塞等待客户端请求被执行的情况。 最后需要大家注意的是，Raft算法的而领导者选举和日志提交都是由集群的节点来完成的。但在PBFT算法中，客户端参与了拜占庭容错的实现，比如，客户端实现定时器，等待接收来自备份节点的响应，如果等待超时，则发送请求给所有节点

注意。 相比Raft算法完全不适应有人作恶的场景，PBFT算法能容忍(n-1)/3个恶意节点(也可以是故障节点)。另外，相比Pow算法，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理论 来思考和设计分区容错一致性模型呢？

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

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

一致性指标描述的是分布式系统的一个非常重要的特性，强调的是数据正确。也就是说，对客户端而言，它每次 都能读取到最新写入的数据。 不过集群毕竟不是单机，当发生分区故障时，不能仅仅因为节点间出现了通信问题，无法响应最新写入的数据， 就在客户端查询数据时一直想客户端返回出错信息，举个例子说明. 业务集群中的一些关键系统，比如名字路由系统(基于Raft算法的强一致性系统),如果仅仅因为发生了分区故障， 无法响应最新数据(比如因通信异常，候选人都无法赢得大多数选票，使得集群没有了领导者)，为了不破坏一致性， 在客户端查询相关路由信息时，系统就一直向客户端返回出错信息，此时相关的业务都将因为获取不倒指定路由 信息而不可用、瘫痪，出现灾难性的故障。 此时，我们就需要牺牲数据正确的要求，在每个节点使用本地数据来响应客户端请求，以保证服务可用，这也是另外 一个指标，可用性。

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

紧接着，客户端向节点1发送写请求"SET X=2",如图所示

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

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

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

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

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

举个例子。比如，用户可以选择向节点1或者节点2发起读操作，如果 不考虑节点间的数据是否一致，只要节点服务器收到请求就立即响应X的值, 如图所示，那么两个节点的服务是满足可用性的

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

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

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

如何使用CAP理论? 我们都直到，只要有网络交互就一定会有延迟和数据丢失，这种状况我们必须接受，还必须保证系统不能挂掉。就像 上面提到的，节点间的分区故障时必然发生的。也就是说，分区容错性(P)是前提，是必须要保证的。 现在就只剩下一致性(C)和可用性(A)可以选择了:要么选择一致性，保证数据正确，要么选择可用性，保证服务可用。 那么CP和AP的含义是什么呢? 1.当选择了一致性(C)的时候，系统一定会读到最新的数据，不会读到旧数据，但如果因为消息丢失、延迟过高发生了 网络分区，那么当集群节点接收到来自客户端的读请求时，为了不破坏一致性，可能会因为无法响应最新数据，而返回 出错信息。 2.当选择了可用性(A)的时候，系统将始终处理客户端的查询，返回特定信息，如果发生了网络分区，一些节点将无法返回 最新的特点信息，而是返回自己当前的相对新的信息。 这里需要强调一点，大部分人对CAP理论有一个误解，认为无论在什么情况下，分布式系统都只能在C和A中选择1个。 其实，在不存在网络分区的情况下，也就是在分布式系统正常运行时(这也是系统在绝大部分时候所处的状态),即在不需要 P时，C和A能够同时保证。只有当发生分区故障的时候，即需要P时，系统才会在C和A之间做出选择。而且如果读操作 会读到旧数据，影响到了系统运行或业务运行(也就是说会有负面的影响)，则推荐选择C，否则推荐选择A.

注意。 CA模型，在分布式系统中不存在。因为舍弃P,意味着舍弃分布式系统，就比如单机版关系型数据库MySQL，如果MySQL 要考虑主备或集群部署，它就必须考虑P. CP模型，采用CP模型的分布式系统，舍弃了可用性，一定会读到最新数据，不会读到旧数据。一旦消息丢失、延迟过高 发生了网络分区，就会影响用户的体验和业务的可用性(比如基于Raft的强一致系统，此时可能无法执行读操作和写操作) 典型的应用有ETCD、Consul和HBase AP模型，采用AP模型的分布式系统，舍弃了一致性，实现了服务器的高可用。用户访问系统时能得到响应数据，不会出现 响应错误，但会读取到旧数据。典型应用有Cassandra和DynamoDB

以开源版的InfluxDB为例，InfluxDB是由节点和META和DATA节点两个逻辑单元组成的(如图所示)，这两个节点的功能和数据特点 不同，需要我们分别为它们涉及分区容错一致性模型。 具体涉及如下: 1.作为分布式系统，分区容错性时必须要实现的，不能因为节点间出现了分区故障，而出现整个系统不工作的情况 2.考虑到META节点保存的是系统运行的关键元信息，比如数据库名、表名、保留策略信息等，所以必须实现一致性。也就是说， 每次读都要能读到最新数据，这样才能避免因为查询不到指定的元信息，而导致时序数据记录写入失败或者系统没办法正常运行。 比如创建数据库telegraf之后，如果系统不能立刻读取到这条新的元信息，那么相关的时序数据记录就会因为找不到指定数据库 信息而写入失败，所以，应该选择CAP理论中的C和P，采用CP架构 3.DATA节点保存的是具体的时序数据记录，比如一条记录CPU负载的时序数据"cpu_usage,host=server0,localtion=cn-sz,user=23,system=57.0". 虽然这些数据不是系统运行相关的元信息，但服务器会被频繁访问，水平扩展、性能、可用性等是关键，所以，应该选择CAP理论中的A和P，采用AP 架构。 综上，基于CAP理论分别设计了InfluxDB的META节点和DATA节点的分区容错一致性模型，我们也可以采用类似的思考方法，设计出符合自己业务 场景的分区容错一致性模型。 如果在上述例子中没有应用CAP理论，或者对CAP理论理解不深入，在设计DATA节点的分区容错一致性模型是不采用AP架构，而是之解使用现在 比较流行的共识算法，比如Raft算法，会有什么问题呢? 1.受限于Raft的强领导者模型。所有写请求都在领导者节点上处理，整个集群的写性能等于单机性能。这样会造成集群接入性能低下，无法支撑海量 或大数据量的时序数据 2.受限于强领导者模型，以及Raft的节点和副本一一对应的限制，无法实现水平扩展。分布式集群扩展了读性能，但并没有提升写性能 在多年的开发实践中，埃里克布鲁尔的猜想将会起到一个关键的作用，不是因为它是CAP理论的本源，意义重大，而是因为它源自高可用、高扩展 的大型互联网系统的实践，强调在数据一致性(ACID)和服务可用性(BASE)之间权衡取舍。

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

ACID理论:CAP的"酸"，追求一致性。 提到ACID,它很容易理解，在单机上实现也不难，比如可以通过锁、时间序列等机制保障操作的顺序执行， 让系统实现ACID特性。但是一说要实现分布式系统的ACID特性比较难实现呢？ ACID理论是对事务特性的抽象和总结，方便我们实现事务。可以这样理解：如果实现了操作的ACID特性， 那么旧实现了事务。二大多数人觉得比较难，是因为分布式系统涉及多个节点间的操作。加锁、时间序列 等机制只能保证单个节点上操作的ACID特性，无法保证节点间操作的ACID特性。那么怎么做才会让实现 不那么难呢？答案是通过分布式事务协议实现，比如二阶段提交协议和TCC(Try-Confirm-Cancel),不过 在介绍二阶段提交协议和TCC之前，咱们先继续看看苏秦的故事，看这回苏秦又遇到了什么事。 最近呢，秦国按耐不住自己躁动的心，开始骚扰魏国边境，魏王头疼，向苏秦求助，苏秦认为"三晋一家亲"， 建议魏王联合赵、韩一起对抗秦国。但是这三个国家实力都很弱，需要大家都同一联合，一致行动，如果有 任何一方不方便行动，就取消整个计划。根据侦察情况，明天发动反攻的胜算比较大。所以苏秦想协调赵、 魏、韩明天一起行动，如图所示，那么对于苏秦来说，他面临的问题是，如何高效协同赵、魏、韩一起行动， 并且保证当有一方不方便行动时，取消整个计划。苏秦面临的这个新问题，就是典型的如何实现分布式事务 的问题。赵、魏、韩明天攻打秦国，这三个操作组成一个分布式事务，要么全部执行，要么全部不执行。 了解了这个问题之后，我们来看看如何通过二阶段提交协议和TCC帮助苏秦解决这个难题

二阶段提交协议。 二阶段提交协议，顾名思义，就是通过二阶段的协商来完成一个提交操作，那么具体是怎么操作的呢？ 首先，苏秦发消息给赵，赵接收到消息后就扮演协调者(Coordinator)的身份联系魏和韩发起二阶段提交， 如图所示。 赵发起二阶段提交后，先进入提交请求阶段(又称投票阶段)。为了方便演示，我们先假设赵、魏、 韩明天都能去攻打秦国，大致步骤如图所示。 也就是说，第一步，赵分别向魏、韩发送消息:"明天攻打秦国，方便么?" 第二步，赵、魏、韩分别评估明天能否去攻打秦国，如果能，就预留时间并锁定，不再安排其他军事活动 第三步，赵得到全部的回复结果(包括他自己的评估结果)，都是YES 赵收到所有回复后，进入提交执行阶段(又称完成阶段)，大致步骤如图所示 首先，赵按照"要么全部执行，要么放弃"的原则，统计投票结果，因为所有的回复结果都是YES,所以赵决定 执行分布式事务:明天攻打秦国。 然后，赵通知魏、韩:"明天攻打秦国"。 接到通知之后，魏、韩执行事务，明天攻打秦国。最后，魏、韩执将执行事务的结果返回给赵。 这样依赖，赵就将事务执行的结果(也就是赵、魏、韩明天一起攻打秦国)返回给苏秦，那么，这时苏秦就 解决了问题，协调好了明天的作战计划。 在这里，赵采用的方法就是二阶段提交协议，在这个协议中: 1.可以将"赵明天带兵攻打秦国、魏明天攻打秦国、韩明天带兵攻打秦国"理解成一个分布式事务操作 2.可以将赵、魏、韩理解为分布式系统的3个节点，其中，赵是协调者。将苏秦理解为业务，也就是客户端 3.可以将消息理解为网络消息 4.可以将"评估明天是否方便，预留时间"理解为评估事务中选哟操作的对象和对象状态，是否准备号，能否 提交新操作。

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

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

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

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

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理论提升系统的可用性呢?

实现基本可用的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种写一致性级别，用户在写数据的时候，可以根据业务数据特点，设置不同 的写一致性级别。

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

Paxos算法

概述。 提到分布式算法，就不得不提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)对提议的值进行投票， 并存储接受的值

你需要了解的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如何就提议的值达成共识 的基础

如何达成共识。 想象这样一个场景，某地出现突发事件，当地村委会、负责人等在积极研究和搜集解决该事件的解决方案，你也决定参与其中， 提交提案，建议一些解决方法。为了和其他村民的提案做区分，你的提案还得包含一个提案编号，以起到唯一标识的作用。 与你的做法类似，在Basic Paxos中，兰伯特也使用提案代表一个提议。不过提案中除了包含提案编号，还包含提议值。为了 方便表示，使用[n,v]表示一个提案，其中n为提案编号，v为提议值。 强调一下，整个共识协商是分为两个阶段进行的(也就是前面提到的二阶段提交:准备阶段、接受阶段)，那么具体要如何协商呢? 我们假设客户端1的提案编号为1，客户端2的提案编号为5，并假设节点A、B先收到来自客户端1的准备请求，节点C先收到客户端2 的准备请求

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的准备响应都为空("尚无提案")，所以就把自己的提议值3作为提案的值，发送接受请求[1,3]. 客户端2收到大多数的接受者(节点A和节点B)的准备响应后，会根据响应中提案编号最大的提案的值设置接受请求中的值， 因为该值在来自节点A、B的准备响应中都为空，所以就把自己的提议值7作为提案的值，发送接受请求[5,7]. 当3个节点收到两个客户端的接受请求时，会进行如图所示的处理. 当节点A、B、C收到接受请求[1,3]的时候，由于提案的提案编号1小于3个节点承诺能通过的最小提案编号5，所以提案[1,3] 将被拒绝。当节点A、B、C收到的接受请求[5,7]的时候，由于提案的提案编号5不小于3个节点承诺能通过的提案的最小编号5， 所以提案[5,7]通过，也就是接受了提议值7,3个节点就X值达成共识。 如果集群中有学习者，接受者通过了一个提案后就会通知所有的学习者，当学习者发现大多数的接受者都通过了某个提案，那么 它也会通过该提案，并接受该提案的值。 通过上面的示例过程可以看到，最终就X的值达成了共识。Basic Paxos的容错能力源自"大多数"的约定，可以这么理解，当少于 一半的节点出现故障时，共识协商仍然可以正常工作

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实例实现一系列值的共识算法。这一点由器需要注意

兰伯特关于Multi-Paxos的思考。 熟悉Basic Paxos的读者可能还记得，Basic Paxos是通过二阶段提交来达成共识的。在第一阶段，也就是准备阶段， 只有接收到大多数准备响应的提议者才能发起接受请求进入第二阶段(也就是接受阶段),如图所示。 但是，如果我们之解通过多次执行Basic Paxos实例来实现一系列值得共识，就会存在这样几个问题: 1.如果多个提议者同时提交提案，可能出现因为提案编号冲突，在准备阶段没有提议者接收到大多数准备响应，导致 协商失败，需要重新协商。你想象一下，一个5节点的集群，如果其中3个节点作为提议者同时提案，就可能发生 因为没有提议者接收大多数响应(比如1个提议者接收到1个准备响应，另外两个提议者分别接收到两个2准备响应) 而准备失败，需要重新协商。还有可能只有提案编号最大的那个提议者的值能获得大多数的响应，前面的值则无响应， 这显然也不符合Multi-Paxos的思想。 2.两轮RPC通信(准备阶段和接受阶段)往返消息多、耗性能、延迟大。你要知道，分布式系统的运行是建立在RPC通信 的基础之上的。因此，延迟一直是分布式系统的通电，是需要我们在开发分布式系统时认真考虑和优化的 那么如何解决上面的两个问题呢？可以通过引入领导者和优化Basic Paxos执行过程来解决

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

优化Basic Paxos执行过程。 我们可以采用"当领导者处于稳定状态时,省掉准备阶段，直接进入接受阶段"这个优化机制，优化Basic Paxos执行过程。 也就是说，领导者节点上的序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的提案，即领导者 可以独立指定提案中的值。这时，领导者在提交命令时，可以省掉准备阶段，直接进入接受阶段，如图所示。 可以看到，与重复执行Basic Paxos相比，当Multi-Paxos引入领导者节点之后，因为只有领导者节点一个提议者，所以不存在 提案冲突。另外，当主节点处于稳定状态时，省掉准备阶段，直接进入接受阶段，会在很大程度上减少了往返的消息数，提升 了性能，降低了延迟。看到这里你可能会问:在实际系统中，该如何实现Multi-Paxos呢?接下来，接下来以Chubby的Multi-Paxos 算法的。

Chubby是如何实现Multi-Paxos算法的 既然兰伯特只是大概地介绍了Multi-Paxos思想，那么Chubby是如何补充细节，实现Multi-Paxos算法的呢？ 首先，它通过引入主节点，实现了兰伯特提到地领导者节点地特性。也就是说，主节点作为唯一提议者，这样就不存在多个 提议者同时提交提案的情况，也就不存在提案冲突的情况。 另外，在Chubby中，主节点是通过执行Basic Paxos算法进行投票选举产生的，并且在运行过程中，主节点会通过不断续租 的方式来延长租期(Lease)。比如在实际场景中，某节点在数天内都是同一个节点作为主节点。如果主节点故障了，那么其他 节点会投票选出新的主节点，也就是说主节点一直存在，而且是唯一的。 其次，Chubby实现了兰伯特提到的，"当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段"这个优化机制。最后, Chubby实现了成员变更(Group Membership)，以此来保证在节点变更时集群的平稳运行。 最后，补充一点:在Chubby中，为了实现强一致性，读操作也只能在主节点上执行。也就是说，只要数据写入成功，之后 所有的客户端读到的数据将都是一致的。具体过程分析如下。 所有的度请求和写请求都由主节点来处理。当主节点从客户端接收到写请求后，作为提议者，它将执行Basic Paxos实例， 将数据发送给所有节点，并在大多数的服务器接收到这个写请求之后，再将响应成功返回给客户端，如图所示。 当主节点接收到读请求后，处理就比较简单了。此时，主节点只需要查询本地数据，然后将数据返回给客户端就可以了， 如图所示。 尽管Chubby的Multi-Paxos实现是一个闭源的实现，但这是Multi-Paxos思想在实际场景中的真正落地，Chubby团队不仅 通过编程实现了算法，还探索了如何补充算法论文缺失的必要实现细节。其中的思考和设计非常具有参考价值，不仅能帮助 我们理解Multi-Paxos思想，还能帮助我们理解其他的Multi-Paxos算法(比如Raft算法)

注意。 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 个节点的故障

Raft算法

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

选举领导者的过程。 那么如何从3个成员中选出领导者呢? 首先，在初始状态下，集群中所有的节点都处于跟随者的状态，如图所示。 Raft算法实现了随机超时时间的特性。也就是说，每个节点等待领导者节点心跳信息的超时时间间隔是随机的。 通过上图可以看到，集群中没有领导者，而节点A的等待超时时间最小(150ms)，所以它会最先因为没有等到 领导者的心跳信息而超时。 这个时候，节点A会增加自己的任期编号，并推荐自己为候选人，先给自己投一张选票，然后先其他阶段发送请求 投票RPC消息，请他们选举自己为领导者，如图所示，如果其他节点接收到候选人A的请求投票RPC消息，且在 编号为1的这届任期内，它也还没有投过票，那么它将把选票投给节点A,并增加自己的任期编号，如图所示。 如果候选人在选举超时时间内赢得了大多数选票，那么它就会成为本届任期内新的领导者，如图所示。 节点A当选领导者后，将周期性的发送心跳消息，通知其他服务器"我是领导者",阻止跟随者发起新的选举、篡权。 如图所示，看到这里，你是不是发现领导者选举很容易理解?它与现实中地议会选举也很类似？当然，你可能还是 会对一些细节产生疑问，比如: 1.节点间是如何通信地? 2.什么是任期? 3.选举有哪些规则 4.随机超时时间又是什么

选举过程四连问。 老话说，细节是魔鬼。这些细节也是大家在学习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.在一次选举中，每一个服务器节点最多会对一个任期编号透出一张选票，并且按照"先来先服务"的原则进行投票。比如任期编号为3的节点C 先收到了一个包含任期编号为4的投票请求(来自节点A),又收到了1个包含任期编号为4的投票请求(来自节点B),那么节点C将会把唯一一张选票 投给节点A，在收到节点B的投票请求RPC消息时，它已没有选票可投了，如图所示 6.日志完整性高的跟随者(也就是最后一条日志对应的任期编号值更大，索引号更大)拒绝投票给日志完整性低的候选人。比如节点B的任期编号为3， 节点C的任期编号是4，节点B的最后一条日志项对应的任期编号为3，而节点C的最后一条日志项对应的任期编号为2，那么当节点C请求节点B投票 给自己时，节点B将拒绝投票，如图所示。 注意。 选举时跟随者发起的，推荐自己为候选人；大多数选票是指集群成员半数以上的选票；大多数选票规则的目标是保证在一个给定的任期内 有且只有一个领导者。 其实在选举中，除了选举规则外，我们还需要避免一些导致选举失败的情况，比如同一任期内，多个候选人同时发起选举，导致选票被瓜分， 选举失败。那么Raft算法是如何避免这个问题的呢?答案就是采用随机超时时间。

如何理解随机超时时间。 议会选举中常出现未达到指定票数，选举无效，需要重新选举的情况。Raft算法的选举中也u才能在类似的问题，那它是如何处理选举无效的问题呢？ 其实,Raft算法巧妙地使用了随机选举超时时间的方法，即把超时时间都分散开来，在大多数情况下只有一个服务器节点发起选举，而不是同时发起选举， 从而减少因选票瓜分导致选举失败的情况。在Raft算法中，随机超时时间有两种含义，这也是很多人容易理解错误的地方,需要注意一下: 1.跟随者等待领导者心跳信息超时的时间间隔是随机的。 2.如果候选人在一个随机时间间隔内没有赢得过半票数，那么选举无效，然后候选人会发起新一轮的选举，也就是说，等待选举超时的时间间隔是随机的。 注意。 Raft算法通过任期、领导者心跳消息、随机选举超时时间、先来先服务的投票原则、大多数选票原则等，保证了一个任期只有一位领导者，也极大地减少了 选举失败的情况

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

如何理解日志。 副本数据是以日志的形式存在的，而日志由日志项组成，那么日志项究竟是什么呢？ 其实，日志项是一种数据格式，它主要包含用户指定的数据，也就是指令(Command)，以及一些附加信息， 比如索引值(Log Index)、任期编号(Term),如图所示。 1.指令:一条由客户端请求指定的、状态机需要执行的命令。你可以将指令理解成客户端指定的数据 2.索引值:日志项对应的整数索引值，用于标识日志项，是一个连续的、单调递增的整数号码 3.任期编号:创建这条日志项的领导者的任期编号。 从图中可以看到，一届领导者任期往往有多条日志项，而且日志项的索引值是连续的，这一点需要特别注意。 现在你可能会问:不是说Raft算法实现了个节点间日志的一致吗？为什么上图中的4个跟随者的日志都不一样呢? 日志是如何复制的呢？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值为7 2.PrevLogTerm:表示当前要复制的日志项的前面一条日志项的任期编号，比如图中的，如果领导者将索引值为8的日志项发送给跟随者， 那么此时PrevLogTerm值为4 领导者处理不一致的具体实现过程分析如下: 1.领导者通过日志复制RPC消息，发送当前最新日志项到跟随者(为了演示方便，假设当前需要复制的日志项是最新的)，这个消息的PrevLogEntry 值为7，PrevLogTerm值为4 2.如果跟随者在它的日志中找不到与PrevLogEntry值为7、PrevLogTerm值为4的日志项，也就是说它的日志和领导者的不一致，那么跟随者 就拒绝接收新的日志项，并返回失败给领导者 3.这时，领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者，新的日志项的PrevLogEntry值为6，PrevLogTerm值为3. 4.如果跟随者在它的日志中找到了PrevLogEntry值为6、PrevLogTerm值为3的日志项，那么日志复制RPC消息返回成功，这样一来，领导者 就知道在PrevLogEntry值为6、PrevLogTerm值为3的位置，跟随者的日志项与自己的日志项相同。 5.领导者通过日志复制RPC消息复制并更新该索引值之后的日志项(也就是不一致的日志项)，最终实现集群个节点日志的一致。 从上面步骤可以看到，领导者通过日志复制RPC消息的一致性检查，找到跟随者节点上与自己相同的日志项的最大所引致。然后复制并更新该 索引值之后的日志项，实现各节点日志的一致。需要注意的是，跟随者中的不一致的日志项会被领导者的日志覆盖，而且领导者从来不会覆盖 或者删除自己的日志。

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算法是如何保障集群稳定运行，而不出现两个领导者呢？老话说的好，认识问题，才能解决问题。为了更好地理解单节点变更地方法，我们先来看一看成员变更时到底会出现什么样的问题

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

如何通过单节点变更解决成员变更问题。 单节点变更就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，则需要执行多次单节点变更。比如在将3节点集群扩容为5节点集群时，你需要执行两次单节点变更，先将3节点集群变更为4节点集群，再将4节点集群变更为5节点集群，如图所示。 让我们回到前面的思考题，看看如何通过单节点变更的方法解决成员变更的问题。为了演示方便，我们假设节点A是领导者，如图所示。 目前的集群配置为【A,B,C】，我们先向集群中加入节点D,这意味着新配置为【A,B,C,D】。具体实现步骤如下: 1.第一步，领导者(节点A)向新节点(节点D)同步数据 2.第二步，领导者(节点A)将新配置【A,B,C,D】作为一个日志项复制到新配置中的所有节点(节点A、B、C、D)上，然后将新配置的日志项应用到本地状态机，完成单节点变更，如图所示。 变更完成后，集群配置变为【A,B,C,D】,我们再向集群中加入节点E，也就是说，新配置为【A,B,C,D,E】。具体实现步骤与上面类似。 1.第一步，领导者(节点A)向新节点(节点E)同步数据 2.第二步，领导者(节点A)将新配置【A,B,C,D,E】作为一个日志项复制到新配置中的所有节点(A、B、C、D、E)上，然后将新配置的日志项应用到本地状态机，完成单节点变更，如图所示。 这样一来，我们就通过一次变更一个节点的方式完成了成员变更，保证了集群中始终只有一个领导者，也保证了集群稳定运行，持续提供服务。 在正常情况下，不管旧的集群配置是怎么组成的，旧配置的"大多数"和新配置的"大多数"都会有一个节点是重叠的。也就是说，不会同时存在旧配置和新配置两个"大多数"。 如果你遇到这种情况，可以在领导者启动时创建一个NO_OP日志项(也就是空的日志项)，当领导者应用该NO_OP日志项后，再执行成员变更请求。具体实现可参考Hashicorp Raft的源码,也就是runLeader()函数，代码如下: ```c noop :=&logFuture{ log: Log{ Type:LogNoop, }, } r.dispatchLogs([*logFuture{noop}]) ``` 当然，有的人会好奇"联合共识"，在我看来，联合共识难以实现，很少被Raft算法采用。比如，除了Logcabin外，目前还没有其他常用Raft算法采用这种方式。 注意。 因为联合共识实现起来复杂，所以绝大多数Raft算法采用的都是单节点变更的方法(比如Etcd、Hashicorp Raft)，其中，Hashicorp Raft单节点变更的实现是由Raft算法的作者迭戈安加罗(Diego Ongaro)设计的，很有参考价值

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% ``` 从示例代码的输出可以看到，迁移成本非常高昂，这在实际生产环境中也是无法想象的

```c package main import ( "flag" "fmt" ) var keysPtr = flag.Int("keys", 10000000, "key number") var nodesPtr = flag.Int("nodes", 3, "node number of old cluster") var newNodesPtr = flag.Int("new-nodes", 4, "node number of new cluster") func hash(key int, nodes int) int { return key % nodes } func main() { flag.Parse() var keys = *keysPtr var nodes = *nodesPtr var newNodes = *newNodesPtr migrate := 0 for i := 0; i < keys; i++ { if hash(i, nodes) != hash(i, newNodes) { migrate++ } } migrateRatio := float64(migrate) / float64(keys) fmt.Printf("%f%%\n", migrateRatio*100) } ```

如何使用一致哈希算法实现哈希寻址。 一致哈希算法也采用取模运算，但与哈希算法是对节点的数量进行取模不同，一致哈希算法是对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%的数据。 需要注意的是，使用一致哈希算法实现哈希寻址时，可以通过增加节点数来降低节点宕机对整个集群的影响，以及故障恢复时需要迁移的数据量。后续在需要时，你也可以通过增加节点数来提升系统的容灾能力和故障恢复效率。

```c package main import ( "flag" "fmt" "log" "stathat.com/c/consistent" "strconv" ) var keysPtr = flag.Int("keys", 10000, "key number") var nodesPtr = flag.Int("nodes", 3, "node number of old cluster") var newNodesPtr = flag.Int("new-nodes", 4, "node number of new cluster") func hash(key int, nodes int) int { return key % nodes } func main() { flag.Parse() var keys = *keysPtr var nodes = *nodesPtr var newNodes = *newNodesPtr c := consistent.New() for i := 0; i < nodes; i++ { c.Add(strconv.Itoa(i)) } newC := consistent.New() for i := 0; i < newNodes; i++ { newC.Add(strconv.Itoa(i)) } migrate := 0 for i := 0; i < keys; i++ { server, err := c.Get(strconv.Itoa(i)) if err != nil { log.Fatal(err) } newServer, err := newC.Get(strconv.Itoa(i)) if err != nil { log.Fatal(err) } if server != newServer { migrate++ } } migrateRatio := float64(migrate) / float64(keys) fmt.Printf("%f%%\n", migrateRatio*100) } ```

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协议

概述。 很多人应该都使用过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无法保证操作的顺序性。

为什么Multi-Paxos无法保证操作的顺序性 为了让你真正理解这个问题，举个具体的例子演示以下(为了演示方便，我们假设当前所有节点上被选定指令的最大序号都为100，那么新提议的指令对应的序号就会是101),假设这时节点A故障了，新当选的领导者为节点B.节点B当选领导者后，需要先作为学习者了解目前已被选定的指令。节点B学习之后，发现当前被选定指令的最大序号为100(因为节点A故障了，它的被选定指令的最大序号102无法被节点B发现)，那么它可以从序号101开始提议新的指令。这时节点B接收到客户端请求，并提议指令Z,指令Z被成功复制到节点B、C，如图所示。假设这时节点B故障了，节点A故障恢复了，选举出领导者C后，节点B故障也恢复了。节点C当选领导者后，需要先作为学习者了解目前已被选定的指令，这时它执行Basic Paxos的准备阶段就会发现之前选定的值(比如Z、Y),然后发送接受请求，最终在序号101、102达成共识的指令是Z、Y，如图所示。 可以看到，原本预期的指令是X、Y，最后变成了Z、Y。现在，你应该可以知道为社么Multi-Paxos不能达到我们想要的结果了吧？ 这个过程其实很明显地验证了"Multi-Paxos虽然能保证达成共识后的值不再改变，但它不关心达成共识的值是什么"。 我们接着回到前面的问题，假设我们在ZooKeeper中直接使用了兰伯特的Multi-Paxos，那么系统在创建节点/geekbang和/geekbang/time时就可能会出现先创建节点/geekbang/time的情况，这样肯定就出错了，如代码所示 ```c [zk: localhost:2181(CONNECTED) 9] create /geekbang/time 456 Node does not exist: /geekbang/time ``` 因为创建节点/geekbang/time时找不到节点/geekbang，所以创建失败。 在这里多说几句，除了Multi-Paxos，兰伯特还有很多关于分布式的理论，这些理论都很经典(比如拜占庭将军问题)，但也因为提出的时间太早了，与实际场景结合的不多，所以后续的众多算法都在这些理论的基础上做了大量的改进(比如，PBFT、Raft等算法)。 另外再延申一下，其实ZAB论文"Zab:High-Performance Broadcast for Primary-Backup System"中关于Paxos问题的分析是有争议的。ZooKeeper当时应该考虑的是Multi-Paxos，而不是有多个提议者的Basic Paxos.因为在Multi-Paxos中，领导者作为唯一提议者，是不存在同时有多个提议者的情况。也就是说，Paxos(更确切地说是Multi-Paxos)无法保证操作的顺序性，但问题的原因不是ZAB论文中演示的原因，本质上是因为Multi-Paxos实现的是一系列值的共识，而不关心最终达成共识的值是什么,也不关心各值得顺序，就像上面演示的过程那样。 既然Multi-Paxos不合适，ZooKeeper是如何实现操作的顺序性的呢？答案是它采用了ZAB协议。 你可能会说:Raft算法可以实现操作的顺序性，为什么ZooKeeper不采用Raft算法呢？这个问题的答案其实比较简单，因为Raft算法是在2013年才正式提出，而ZooKeeper是在2007年开发出来的。

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

ZAB协议是如何实现操作地顺序性的？ 如果用一句话解释ZAB协议到底是什么，我觉得它是能保证操作顺序性的、基于主备模式的原子广播协议。 接下来，还是以指令X、Y为例具体演示一下，帮助你更好地理解为什么ZAB协议能实现操作的顺序性(为了演示，我们假设节点A为主节点，节点B、C为备份节点)。 首先，在ZAB协议中，写操作必须在主节点(比如节点A)上执行。如果客户端访问的节点是备份节点(比如节点B),则备份节点会将写请求转发给主节点，如图所示。 接着，当主节点接收到写请求后，它会基于写请求中的指令(也就是X、Y)来创建一个提案(Proposal)，并使用一个唯一的ID来标识这个提案。这里我说的唯一ID就是事务标识符(TransactionID,也就是zxid),如图所示 从图中可以看到，指令X、Y对应的事务标识符分别为<1,1>和<1,2>。这两个标识符是什么含义呢？ 你可以这么理解，事务标识符是64位的long型变量，由任期编号epoch和计数器counter两部分组成(为了形象和方便理解，我把epoch翻译城任期编号)，格式为<epoch,counter>，其中，高32位位任期编号，低32位为计数器。 1.任期编号就是创建提案时领导者的任期编号，当新领导者当选时，任期编号递增，计数器被设置为零。比如，前领导者的任期编号为1，那么新领导者对应的任期编号将为2 2.计数器就是具体标识提案的整数，每次领导者创建新的提案时，计数器将递增。比如，前一个提案对应的计数器值为1，那么新的提案对应的计数器值将为2 为什么要设计这么复杂呢？因为事务标识符必须按照顺序、唯一标识一个提案，也就是说，事务标识符必须是唯一的、递增的。 在创建完提案之后，主节点会基于TCP协议并按照顺序将提案广播到其他节点，如图所示，这样就能保证先发送的消息先被收到，进而保证消息接收的顺序性。如图所示，指令X一定在指令Y之前到达节点B、C. 然后，当主节点接收到指定提案的大多数确认响应后，该提案将处于提交状态(Commited)，此时主节点会通知备份节点提交该提案，如图所示。 主节点提交提案是有顺序性的。它会根据事务标识大小顺序提交提案，如果前一个提案未提交，此时主节点是不会提交后一个提案的。也就是说，指令X一定会在指令Y之前提交。 最后，主节点返回执行成功的响应给节点B，由节点B再转发给客户端，这样我们就实现了操作的顺序性，保证了指令X一定在指令Y之前执行。 最后想补充的是，当执行完写操作后，接下来你可能需要执行读操作。为了提升读并发能力，ZooKeeper提供的是最终一致性，也就是说，读操作可以在任何节点上执行,如图所示，客户端会读到旧数据。如果客户端必须要读到最新数据，怎么办呢？ZooKeeper提供了一个解决办法，那就是sync命令。我们可以在执行读操作前执行sync命令，从而使客户端可以读到最新数据，如代码所示 ```c [zk: localhost:2181(CONNECTED) 17] create /geekbang 123 Created /geekbang [zk: localhost:2181(CONNECTED) 18] create /geekbang/time 456 Created /geekbang/time [zk: localhost:2181(CONNECTED) 19] sync /geekbang/time Sync is OK [zk: localhost:2181(CONNECTED) 20] get /geekbang/time 456 [zk: localhost:2181(CONNECTED) 22] stat /geekbang/time cZxid = 0x51104 ctime = Sun May 05 15:46:28 CST 2024 mZxid = 0x51104 mtime = Sun May 05 15:46:28 CST 2024 pZxid = 0x51104 cversion = 0 dataVersion = 0 aclVersion = 0 ephemeralOwner = 0x0 dataLength = 3 numChildren = 0 ```

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

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

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

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的领导者选举，仍然用一个例子演示一下。为了方便演示和理解(我们聚焦最核心的领导者PK)，假设投票信息的格式是<proposedLeader,proposedEpoch,proposedLastZxid,node>,具体如下: 1.proposedLeader:节点提议的领导者的集群ID,也就是在集群配置(比如myid配置文件)时指定的ID 2.proposedEpoch:节点提议的领导者的任期编号 3.proposedLastZxid:节点提议的领导者的事务标识符的最大值(也就是最新提案的事务标识符) 4.node:投票的节点，比如节点B. 假设一个ZooKeeper集群由节点A、B、C组成，其中节点A是领导者，节点B、C是跟随者(为了方便演示，假设节点B、C的epoch分别就是1和1，lastZxid分别是101和102，集群ID分别为2和3)，如图所示。如果节点A宕机了，如何选举领导者呢? 首先，当跟随者检测到连接领导者节点的读操作等待超时时，跟随者会将自己的节点状态变更成LOOKING，然后发起领导者选举(为了演示方便，我们假设这时节点B、C都已经检测到了读操作超时)，如图所示。 接着，每个节点会创建一张选票，这张选票是投给自己的，也就是说，节点B、C都"自告奋勇"地推荐自己为领导者并创建选票<2,1,101,B>和<3,1,102,C>，然后各自将选票发送给集群中的所有节点，也就是说，节点B发送给节点B、C,节点C也发送给节点B、C. 一般而言，节点会先接收自己发送给自己的选票(因为不需要跨节点通信，传输速度更快)，也就是说，节点B会先收到来自节点B的选票，节点C会先收到来自节点C的选票，如图所示。 需要注意的是，集群的个节点收到选票后，为了选举出数据最完整的节点，对于每一张接收到的选票，节点都需要进行领导者PK,也就是将选票提议的领导者和自己提议的领导者进行比较，找出更适合作为领导者的节点。约定的规则如下: 1.优先检查任期编号，任期编号大的节点作为领导者 2.如果任期编号相同，则比较事务标识符的最大值，值大的节点作为领导者 3.如果事务标识符的最大值也相同，再比较集群ID，集群ID大的节点作为领导者。 如果选票提议的领导者比自己提议的领导者更适合作为领导者，那么节点将调整选票内容，推荐选票提议的领导者作为领导者。 当节点B、C接收到选票后，因为选票提议的领导者与自己提议的领导者相同，所以，领导者PK的结果是节点B、C不需要调整选票信息，只需要正常接收和保存选票就可以了，如图所示。 接着节点B、C分别接收到来自对方的选票，比如节点B接收到来自节点C的选票，节点C接收到来自节点B的选票，如图所示。 对于节点C而言，它提议的领导者是节点C，而选票(<2,1,101,B>)提议的领导者是节点B,因为节点C的任期编号与节点B相同，但节点C的事务标识符的最大值比节点B的大，所以，按照约定的规则，相比节点B，节点C更适合作为领导者，也就是说，节点C不需要调整选票信息，正常接收和保存选票就可以了。但对于节点B而言，它提议的领导者是节点B,选票(<3,1,102,C>)提议的领导者节点是C,因为C的任期编号与节点B相同，但节点C的事务标识符的最大值比节点B的大，所以，按照约定的规则，相比节点B，节点C应该作为领导者，也就是说，节点B除了接收和保存选票信息，还会更新自己的选票为<3,1,102,B>,即推荐节点C作为领导者，并将选票重新发送给节点B、C，如图所示。 接着，当节点B、C接收到来自节点B的新的选票时，因为这张选票(<3,1,102,B>)提议的领导者，与它们提议的领导者是一样的，都是节点C,所以，它们正常接收和保存这张选票就可以了，如图所示。 最后，因为此时节点B、C提议的领导者(节点C)赢得了大多数选票(两张选票)，所以，节点B、C将根据投票结果变更节点状态，并退出选举。比如因为当选的领导者是节点C，那么节点B将变更为FOLLOWING并退出选举，而节点C将变更状态为LEADING并退出选举，如图所示。 至此，我们就选举了新的领导者(节点C).这个选举的过程很容易理解，这里只是假设了一种选举的情况，实际上还会存在节点间事务标识符相同、节点在广播投票信息前接收到其他节点的投票等情况。

注意。 逻辑时钟(logicclock,也就是选举的轮次)会影响选票的有效性。具体来说，逻辑时钟值大的节点不会接收来自逻辑时钟值小的节点的投票信息。比如， 节点A、B的逻辑时钟分别为1和2，那么节点B将拒绝接收来自节点A的投票信息。 领导者选举的目标是从大多数节点中选举出数据最完整的节点，也就是从大多数节点中选出事务标识符值最大的节点。另外，ZAB协议的本质上是通过 "见贤思齐，相互推荐"的方式来选举领导者的。也就说，根据领导者PK,节点会重新推荐更合适的领导者，最终选举出大多数节点中数据最完整的节点

ZooKeeper是如何选举领导者的。 首先我们来看看ZooKeeper是如何实现成员身份的？ 在ZooKeeper中，成员状态是在QuorumPeer.java中实现的，为枚举型变量 ```java public enum ServerState { LOOKING, FOLLOWING, LEADING, OBSERVING } ``` 其实，ZooKeeper没有直接定义成员身份，而是用了对应的成员状态来表示，比如，处于FOLLOWING状态的节点为跟随者。如果你想研究相关成员的功能和实现，那么可以把对应的成员状态作为切入点来研究。比如，你想研究领导者的功能实现，可以在代码中搜索LEADING关键字，然后研究相应的上下文逻辑，进而得到自己想要的答案。 如果跟随者将自己的状态从跟随者状态变更为选举状态，就表示跟随者在发起领导者选举，那么在ZooKeeper中，领导者选举是如何实现的呢？ 领导者选举是在FastLeaderElection.lookForLeader()中实现的。其核心实现流程如图所示。 为了更好地理解这个流程，我们来一起走读下核心代码: 1.在集群稳定运行时，处于跟随者状态的节点会调用Follower.followLeader()函数周期性地读数据包和处理数据包，如代码所示 ```java QuorumPacket qp = new QuorumPacket(); while (this.isRunning()) { //读取数据包 readPacket(qp); // 处理数据包 processPacket(qp); } ``` 2.当跟随者检测到连接到领导者的读操作超时时(比如领导者节点故障了)，它会抛出异常(Exception)，跳出上面的读取数据保和处理数据保的循环，并将节点状态变更为选举状态。如代码所示 ```java public void run() { case FOLLOWING: ...... finally { // 关闭跟随者节点 follower.shutdown(); setFollower(null); // 设置状态为选举状态 updateServerState(); } break; ...... } ```

核心流程图

3.当节点处于选举状态时，它将调用makeLEStrategy().lookForLeader()函数(实际对应的函数为FastLeaderElection.lookForLeader())发起领导者选举，如代码所示 ```java setCurrentVote(makeLEStrategy().lookForLeader()); ``` 4.在FastLeaderElection.lookForLeader()函数中，节点需要对逻辑时钟(也就是选举的轮次)的值执行加1操作，表示开启一轮新的领导者选举，然后创建投票提案(默认推荐自己为领导者)并通知所有节点，如代码所示 ```java synchronized(this) { // 对逻辑时钟的值执行加一操作 logicalclock.incrementAndGet(); // 创建投票提案，并默认推荐自己为领导者 updateProposal(getInitId(), getInitLastLoggedZxid(), getPeerEpoch()); } // 广播投票信息给所有节点 sendNotifications(); ```

5.当节点处于选举状态时，它会周期性地从队列中读取接收到地投票信息，直到选举成功，如代码所示 ```java while((self.getPeerState() == ServerState.LOOKING) && (!stop)) { // 从队列中读取接收到地投票信息 Notification n = recvqueue.poll(notTimeout, TimeUnit.MILLISECONDS); ...... } ``` 6.当接收到新的投票信息时，节点会进行领导者PK，来判断谁更适合当领导者。如果投票信息中提议的节点比自己提议的节点更适合作为领导者， 则该节点会更新投票信息，推荐投票信息中提议的节点作为领导者，并广播给所有节点，如代码所示 ```java else if (totalOrderPredicate(n.leader, n.zxid,n.peerEpoch,proposedLeader, proposedZxid, proposedEpoch)) { // 如果投票信息中提议的节点比自己提议的节点更适合作为领导者，则更新投票信息 // 并推荐投票信息中提议的节点 updateProposal(n.leader,n.zxid,n.peerEpoch); // 将新的投票信息广播给所有节点 sendNotifications(); } ``` 7.如果自己提议的领导者赢得大多数选票，则执行步骤8，变更节点状态，退出选举，如果自己提议的领导者仍未赢得大多数选票，则执行步骤5， 继续从接收队列中读取新的投票信息。 8.最后，当节点提议的领导者赢得大多数选票时，则节点会根据投票结果，判断并变更节点状态(如变更为领导者或跟随者)，然后退出选举,如代码所示 ```java if (voteSet.hasAllQuorums()) { ...... // 根据投票结果，判断并设置节点状态 setPeerState(propsedLeader, voteSet); // 退出领导者选举 Vote endVote = new Vote(proposedLeader, proposedZxid, logicalclock.get(), proposedEpoch); leaveInstance(endVote); return endVote; ...... } ```

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

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

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

如何确立领导关系。 前面提到，选举出的领导者是在成员发现阶段确立领导关系的。领导者在当选后会递增自己的任期编号，并基于任期编号值的大小来与跟随者协商，最终建立领导关系。具体来说，跟随者会选择任期编号值最大的节点来作为自己的领导者，而被大多数节点认同的领导者将成为真正的领导者。 下面用一个例子来帮助更好地理解。 假设一个ZooKeeper集群由节点A、B、C组成。其中，领导者A已经宕机，节点C是新选出来的领导者，节点B是新的跟随者(为了方便演示，假设节点B、C已提交提案的事务标识符的最大值分别是<1,10>和<1,11>，其中1是任期编号，10、11是事务标识符中的计数器值，节点A宕机前的任期编号也是1)，如图所示。那么节点B、C如何协商建立领导关系呢？ 首先，节点B、C会把自己的ZAB状态设置为成员发现(DISCOVERY)，这就表明，选举(ELECTION)阶段结束了，进入了下一个阶段，如图所示。 这里补充一下，ZAB协议定义了4种状态来标识节点的运行状态。 1.ELECTION(选举)状态:表明节点在进行领导者选举 2.DISCOVERY(成员发现)状态:表明节点在协商沟通领导者的合法性 3.SYNCHRONIZATION(数据同步)状态:表明集群的各节点以领导者的数据为准，修复数据副本的一致性 4.BROADCAST(广播)状态:表明集群各节点在正常处理写请求。 关于这4种状态，简单了解即可。强调一点，只有当集群大多数节点处于广播状态的时候，集群才能提交提案。 接下来，节点B会主动向节点C发送包含自己接收到的领导者任期编号的最大值(也就是前领导者A的任期编号，1)的FOLLOWINFO消息，如图所示。 节点C在接收到来自节点B的信息后，会将包含自己的事务标识符的最大值的LEADINFO消息发送给跟随者。需要注意的是，领导者进入成员发现阶段后会对任期编号加1，即创建新的任期编号，然后基于新任期编号创建新的事务标识符(也就是<2,0>)，如图所示。 当接收到领导者的响应后，跟随者会判断领导者的任期编号是否最新，如果不是，就发起新的选举；如果是，则返回ACKEPOCH消息给领导者。在这里， 节点C的任期编号(也就是2)大于节点B接收到的其他领导任期编号(也就是旧领导者A的任期编号，1)，所以节点B返回确认响应给节点C,并设置ZAB状态为数据同步状态，如图所示 最后，领导者在接收到来自大多数节点的ACKEPOCH消息时，会设置ZAB状态为数据同步。在这里，节点C接收到了节点B和节点C自己发送的消息，满足大多数节点的要求，所以，在接收到来自B的消息后，C设置ZAB状态为数据同步状态。如图所示 现在，ZAB协议在成员发现阶段确立了领导者的领导关系，这样领导者就可以行使领导职能了。下一步，ZAB协议要解决的就是数据冲突问题，以实现各节点数据的一致性，那么它是怎么做的呢？

如何处理冲突数据。 当进入数据同步状态后，领导者会根据跟随者的事务标识符的最大值，判断以哪种方式处理不一致数据(有DIFF、TRUNC、SNAP3种方式)。 因为节点C已提交提案的事务标识符的最大值(也就是<1,11>)大于节点B已提交提案的事务标识符的最大值(也就是<1,10>),所以节点C会用DIFF的方式修复数据副本的不一致。并返回差异数据(也就是事务标识符为<1,11>的提案)和NEWLEADER消息给节点B,如图所示.这里强调一点:节点B已提交提案的最大值，也是节点B最新提案的最大值。因为在ZooKeeper实现种，节点退出跟随者状态时(也就是在进入选举前)，所有未提交的提案都会被提交。这是ZooKeeper的设计。 然后，节点B修复不一致数据，返回NEWLEADER消息的确认响应给领导者(即节点C),如图所示. 接着，节点C在接收到来自大多数节点的NEWLEADER消息的确认响应后会将ZAB状态设置为广播状态。在这里，节点C接收到节点B和节点C自己的确认响应，满足大多数确认的要求。所以，在接收到来自节点B的确认响应后，节点C会将自己的ZAB状态设置为广播状态，并发送UPTODATE消息给所有跟随者，通知它们数据同步已经完成了，如图所示。 最后当节点B接收到UPTODATE消息时，它就直到数据同步已经完成，并设置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算法选举出新的领导者后，领导者是可以立即处理写请求的。

ZooKeeper如何从故障中恢复。

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

1.领导者选举结束，节点进入跟随者状态或者领导者状态后，会分别设置ZAB状态为成员发现状态，具体如下: 1.1 跟随者会调用Follower.followLeader()函数，设置ZAB状态为成员发现状态，如代码所示 ```java self.setZabState(QuorumPeer.ZabState.DISCOVERY); ``` 1.2 领导者会调用Leader.lead()函数，并设置ZAB状态为成员发现状态，如代码所示 ```java self.setZabState(QuorumPeer.ZabState.DISCOVERY); ``` 2.跟随者会主动联系领导者，发送自己已接收的领导者任期编号的最大值(也就是acceptedEpoch)的FOLLOWINFO消息给领导者，如代码所示 ```java // 跟领导者建立网络连接 connectToLeader(leaderServer.addr, leaderServer.hostname); connectionTime = System.currentTimeMills(); // 向领导者报道，并获取领导者的事务标识符最大值 long newEpochZxid = registerWithLeader(Leader.FOLLOWERINFO); ``` 3.在接收到来自跟随者的FOLLOWINFO消息后，在LearnerHandler.run()函数中，领导者将创建包含自己的事务标识符最大值的LEADINFO消息，并响应给跟随者，如代码所示 ```java // 创建LEADINFO消息 QuorumPacket newEpochPacket = new QuorumPacket(Leader.LEADERINFO, newLeaderZxid, ver, null); // 发送LEADINFO消息给跟随者 oa.writeRecord(newEpochPacket, "packet"); ``` 4.在接收到来自领导者的LEADINFO消息后，跟随者会基于领导者的任期编号判断领导者是否合法，如果领导者不合法，则发起新的选举，如果领导者合法，则响应ACKEPOCH消息给领导者，如代码所示 ```java // 创建ACKEPOCH消息，包含已提交提案的事务标识符最大值 QuorumPakcet ackNewEpoch = new QuorumPacket(Leader.ACKEPOCH, lastLoggedZxid, epochBytes, null); // 响应ACKEPOCH消息给领导者 writePacket(ackNewEpoch, true); ```

5.跟随者设置ZAB状态为数据同步状态，如代码所示 ```java self.setZabState(QuorumPeer.ZabState.SYNCHRONIZATION); ``` 6.在LearnerHandler.run()函数中(以及Leader.lead()函数)，领导者会调用waitForEpochAck()函数来阻塞和等待来自大多数节点的ACKEPOCH消息，如代码所示 ```java ss = new StateSummary(bbepoch.getInt(), ackEpochPacket.getZxid()); learnerMaster.waritForEpochAck(this.getSid(), ss) ``` 7.在接收到来自大多数节点的ACKEPOCH消息后，在Leader.lead()函数中，领导者设置ZAB状态为数据同步状态。 ```java self.setZabState(QuorumPeer.ZabState.SYNCHRONIZATION); ``` 这样，ZooKeeper就实现了成员发现，且各节点就领导者的领导关系达成了共识。当跟随者和领导者设置ZAB状态为数据同步状态后，它们就进入了数据同步阶段。那么ZooKeeper中的数据同步是如何实现的呢？

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

1.在LearnerHandler.run()函数中，领导者调用syncFollower()函数，根据跟随者的事务标识符的最大值判断用哪种方式处理不一致数据，并把已提交提案和未提交提案都同步给跟随者，如代码所示 ```java peerLastZxid = ss.getLastZxid(); boolean needSnap = syncFollower(peerLastZxid, learnerMaster); ``` 在这里，你需要了解领导者向跟随者同步数据的3种方式(TRUNC、DIFF、SNAP)，它们分别代表什么含义呢？要想了解这部分内容，首先要了解一下syncFollower()中3个关键变量的含义。 1.peerLastZxid:跟随者节点上提案的事务标识符欸度最大值 2.maxCommittedLog、minCommittedLog:领导者节点内存队列中已提交提案的事务标识符的最大值和最小值。需要注意的是，maxCommittedLog、 minCommittedLog与ZooKeeper的设计有关。在ZooKeeper中，为了更高效地将提案复制到跟随者，领导者会将一定数量(默认值为500)的已提交提案放在内存队列里，而maxCommittedLog、minCommittedLog分别标识的是内存队列中已提交提案的事务标识符最大值和最小值。 说完3个关键变量，再来说说3种同步方式。 1.TRUNC:当peerLastZxid大于maxCommittedLog时，领导者会通知跟随者丢弃超出的那部分提案。比如，如果跟随者的peerLastZxid为11，领导者的maxCommittedLog为10，那么领导者将通知跟随者丢弃事务标识符值为11的提案 2.DIFF:当peerLastZxid小于maxCommittedLog但大于minCommittedLog时，领导者会向跟随者同步缺失的已提交的提案，比如，如果跟随者的peerLastZxid为9，领导者的maxCommittedLog为10，minCommittedLog为9，那么领导者将同步事务标识符值为10的提案给跟随者 3.SNAP:当peerLastZxid小于minCommittedLog时，也就是说，跟随者缺失的提案比较多，那么领导者会同步快照数据给跟随者，并直接覆盖跟随者本地的数据。 在这里，补充一下，领导者先就已提交提案和跟随者达成一致，然后调用learnerMaster.startForwarding()将未提交提案(如果有的话)也缓存发送队列(queuedPackets)，并最终复制给跟随者。也就是说，领导者是以自己的数据为准，实现各节点数据副本的一致的。 需要注意的是，在syncFollower()种，领导者只是将需要发送的差异数据缓存在发送队列，还没有实际发送。

2.在LearnerHandler.run()函数种，领导者创建NEWLEADER消息并缓存在发送队列种，如代码所示: ```java // 创建NEWLEADER消息 QuorumPacket newLeaderQP = new QuorumPacket(Leader.NEWLEADER, newLeaderZxid,learnerMaster.getQuorumVerifierBytes(), null); // 缓存NEWLEADER消息到发送队列中 queuedPackets.add(newLeaderQP); ``` 3.在LearnerHandler.run()函数中，领导者调用startSendingPackets()函数启动一个新线程，并将缓存的数据发送给跟随者，如代码所示 ```java // 发送缓存队列中的数据 startSendingPackets(); ``` 4.跟随者调用syncWithLeader()函数，处理来自领导者的数据同步，如代码所示 ```java // 处理数据同步 syncWithLEader(newEpochZxid); ``` 5.在syncWithLeader()函数中，跟随者在接收到来自领导者的NEWLEADER消息后，返回确认响应给领导者，如代码所示 ```java writePacket(new QuorumPacket(Leader.ACK, newLeaderZxid, null, null), true); ``` 6.在LearnerHandler.run()函数(以及Leader.lead()函数)中，领导者等待来自大多数节点的NEWLEADER消息的响应，如代码所示 ```java learnerMaster.waitForNewLeaderAck(getSid(), qp.getZxid()); ``` 7.当接收到来自大多数节点的NEWLEADER消息的响应时，在Leader.lead()函数中，领导者设置ZAB状态为广播状态，如代码所示 ```java self.setZabState(QuorumPeer.ZabState.BROADCAST); ``` 同时，在LearnerHandler.run()中发送UPTODATE消息给所有跟随者，通知它们数据同步已经完成了，如代码所示 ```java queuedPackets.add(new QuorumPacket(Leader.UPTODATE, -1, null, null)); ``` 8.跟随者在接收到UPTODATE消息后会直到数据不一致已修复，可以处理写请求了，同时设置ZAB状态为广播状态 ```java // 数据同步完成后，跟随者就可以正常处理来自领导者的广播消息了，同时设置ZAB状态为广播状态 self.setZabState(QuorumPeer.ZabState.BROADCAST); ```

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

ZooKeeper处理读写请求的原理。 其实前面已经演示"如何实现操作顺序性"时旧已经介绍了ZooKeeper处理读写请求的原理。这里不再赘述，只在前面的基础上补充几点。 首先，在ZooKeeper中，与领导者"失联"的节点是不能处理读写请求的。比如，如果一个跟随者与领导者的连接发生了读超时，那么它会将自己的状态设置为LOOKING,那么此时它既不能转发写请求给领导者处理，也不能处理读请求，只有当它"找到"领导者后，才能处理读写请求.

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

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

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

1.跟随者在FollowerRequestProcessor.processRequest()中接收到写请求。具体来说，写请求是系统在ZooKeeperServer.submitRequestNow()中发给跟随者的，如代码所示 ```java firstProcessor.processRequest(si) ``` 而firstProcessor是在FollowerZooKeeperServer.setupRequestProcessors()中创建的，如代码所示 ```java protected void setupRequestProcessors() { // 创建finalProcessor,提交提案或响应查询 RequestProcessor finalProcessor = new FinalRequestProcessor(this); // 创建commitProcessor,处理提案提交或读请求 comitProcessor = new CommitProcessor(finalProcessor, Long.toString(getServerId()), true, getZooKeeperServerListener()); commitProcessor.start(); // 创建firstProcessor，接收发给跟随者的请求 firstProcessor = new FollowerRequestProcessor(this,commitProcessor); ((FollowerRequest)firstProcessor).start(); // 创建syncProcessor,将提案持久化存储，并返回确认响应给领导者 syncProcessor = new SyncRequestProcessor(this, new SendAckRequestProcessor(getFollower())); syncProcessor.start(); } ``` 需要注意的是，跟随者节点和领导者节点的firstProcessor是不同的，这样firstProcessor在ZooKeeperServer.submitRequestNow()中被调用时，就分别进入了跟随者和领导者的代码流程。另外，setupRequestProcessors()创建了两条处理链，如图所示。

2.跟随者在FollowerRequestProcessor.run()中将写请求转发给领导者，如代码所示 ```java // 调用learner.request() 将请求发送给领导者 zks.getFollower().request(request); ``` 3.领导者在LeaderRequestProcessor.processRequest()中接收写请求，并最终调用pRequest()创建事务(也就是提案)并持久化存储，如代码所示 ```java // 创建事务 pRequest2Txn(request.type, zks.getNextZxid(), request, create2Request, true); ...... // 分配事务标识符 request.zxid = zks.getZxid(); // 调用ProposalRequestProcessor.processRequest()处理写请求，并将事务持久化存储 nextProcessor.processRequest(request); ``` 需要注意的是，写请求也是在ZooKeeperServer.submitRequestNow()中发给领导者的，如代码所示 ```java firstProcessor.processRequest(si) ``` 而firstProcessor是在LeaderZooKeeperServer.setupRequestProcessors()中创建的，如代码所所示: ```java protected void setupRequestProcessors() { // 创建finalProcessor,最终提交提案和响应查询 RequestProcessor finalProcessor = new FinalRequestProcessor(this); // 创建toBeAppliedProcessor,存储可提交的提案，并在提交提案后从toBeApplied队列移除已提交的提案 RequestProcessor toBeAppliedProcessor = new Leader.ToBeAppliedRequestProcessor(finalProcessor, getLeader()); // 创建commitProcessor,处理提案提交或读请求 commitProcessor = new COmmitProcessor(toBeAppliedProcessor, Long.toString(getServerId()),false, getZooKeeperServerListener()); commitProcessor.start(); // 创建proposalProcessor，按照顺序广播提案给跟随者 ProposalRequestProcessor proposalProcessor = new ProposalRequestProcessor(this, commitProcessor); proposalProcessor.initialize(); // 创建preRequestProcessor,根据请求创建提案 preRequestProcessor = new PreRequestProcessor(this, proposalProcessor); preRequestProcessor.start(); // 创建firstProcessor,接收发给领导者的请求 firstProcessor = new LeaderRequestProcess(this, preRequestProcessor); ... } ``` 需要注意的是，与跟随者类似，setupRequestProcessor()也为领导者创建了两条处理链(其中处理链2是在创建proposalRequestProcessor时创建的)，如图所示.其中，处理链1是核心处理链，最终实现写请求处理(创建提案、广播提案、提交提案)和读请求对应的数据响应。处理链2实现提案持久化存储，并返回确认响应给领导者自己

4.领导者在ProposalRequestProcessor.processRequest()中调用propose()将提案广播给集群所有节点，如代码所示: ```java zks.getLeader().propose(request); ``` 5.跟随者在Follower.processPacket()中接收到提案，持久化存储，并返回确认响应给领导者，如代码所示 ```java fzk.logRequest(hdr, txn, digest); ``` 6.领导者在接收到大多数节点的确认响应(Leader.processAck())后，最终在CommitProcessor.tryToCommit()提交提案，并广播COMMIT消息给跟随者，如代码所示 ```java // 通知跟随者提交 commit(zxid); // 自己提交 zk.commitProcessor.commit(p.request); ``` 7.跟随者接收到COMMIT消息后，在FollowerZooKeeperServer.commit()中提交提案，如果最初的写请求是自己接收到的，则返回成功响应给客户端，如代码所示 ```java // 必须顺序提交 long firstElementZxid = pendingTxns.element().zxid; if (firstElementZxid != zxid) { LOG.error("Commiting zxid 0x" + Long.toHexString(zxid) + "but next pending txn 0x" + Long.toHexString(firstElementZxid)); ServiceUtils.requestSystemExit(ExitCode.UNMATCHED_TXN_COMMIT.getValue()); } // 将准备提交的提案从pendingTxns队列移除 Request request = pendingTxns.remove(); request.logLatency(ServiceMetrics.getMetrics().COMMIT_PROPAGRATION_LATENCY); // 最终调用FinalRequestProcessor.processRequest() 提交提案，如果最初的写请求是自己接收到的，则返回成功响应给客户端 commitProcessor.commit(request); ``` 这样，ZooKeeper就完成了写请求的处理。需要特别注意的是，在分布式系统中，消息或者核心消息的持久化存储很关键，也很重要，因为这是保证集群稳定运行的关键。当然数据写入最终还是为了后续的数据读取，那么ZooKeeper是如何实现读操作的呢？

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

1.跟随者在FollowerRequestProcessor.processRequest()中接收到度请求。 2.跟随者在FinalRequestProcessor.processRequest()中查询本地数据，也就是dataTree中的数据，如代码所示 ```java // 处理读请求 case OpCode.getData: { ...... // 查询本地dataTree中的数据 rsp = handleGetDataRequest(getDataRequest, cnxn, request.authInfo); ...... break; } ``` 3.然后跟随者响应查询到的数据给客户端，如代码所示 ```java case OpCode.getdata: { ...... // 响应查询到的数据给客户端 cnxn.sendResponse(hdr, rsp, "response", path, stat, opCode); break; } ``` 至此，ZooKeeper就完成了读操作的处理。这里补充一点，可以将dataTree理解成Raft的状态机，提交的数据最终都存放在dataTree中

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协议中，主节点是基于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提供的是最终一致性，读操作可以在任何节点上执行。如果读操作访问的是备份节点，为什么无法保证每次都能读到最新的数据呢？ 答案:有可能备份节点还没有收到领导者的提交响应，所以存在延迟

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

Gossip协议

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

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

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

反熵。 那如何实现最终一致性呢？答案就是反熵。本质上,反熵是一种通过异步修复实现最终一致性的方法。常见的最终一致性系统(比如Cassandra)都实现了反熵功能.反熵是指集群中的节点每隔一段时间就随机选择一个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性。如图所示，从图中可以看到，节点A通过反熵的方式修复了节点D中缺失的数据。那具体如何实现呢？ 反熵的实现方式主要有推、拉和推拉3种，将以上面图中两个数据副本的不一致问题为例来详细分析。 也许有人会觉得反熵是一个很奇怪的明此。其实，你可以这么来理解，反熵中的熵是指混乱程度，而反熵是指消除不同节点中数据的差异，以提升节点间数据的相似度，降低熵值。 另外需要注意的是，因为反熵需要节点两两交换和比对自己所有的数据，通信成本会很高，所以不建议在实际场景中频繁执行反熵操作，可以通过引入校验和(Checksum)等机制降低需要比对的数据量和通信消息等。 虽然反熵很实用，但是执行反熵操作时，相关的节点都是已知的，而且节点数不能太多。如果是一个动态变化或节点数比较多的分布式环境(比如在DevOps环境中检测节点故障并动态维护集群节点状态)，这时反熵就不适用了。此时，我们应该怎样实现最终一致性呢？答案就是谣言传播。

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

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

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

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

如何使用反熵实现最终一致性。 在分布式存储系统中，实现数据副本最终一致性的最常用的方法是反熵。为了帮助我们沉底理解和掌握在实际环境中实现反熵的方法，以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型分布式系统，并通过反熵实现了各数据副本的最终一致性，且系统也在线上稳定地运行着，此时突然有同时提出希望数据写入成功后，能立即读取到新数据需求，也就是要实现强一致性，这时我们该怎么呢？难道我们必须推倒架构，一切从头再来？

Quorum NWR算法

概述。 不知道你在工作中有没有遇到过这样的事情:你开发实现了一套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 XA协议

概述。 相信很多人都知道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

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

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三个单词统一翻译为"一致性"。因此在谈一致性之前，有必要对这几个概念做一个区分，否则很容易让人迷惑。

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

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

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.分布式系统的性能理论上可以无限提升，但是区块链是以相对的低效率来换取公正，主流的公有链每秒只能处理几笔到几十笔交易

consistency。 介绍完了Coherence和Consensus共识，我们来看consistency一致性，也就是我们平时说的最多的CAP、BASE、ACID之类。 最简单的，客户端C1将系统中的一个值K由V1更新为V2,客户端C2/C3/C4需要立即读取到K的最新值。 ``` 一致性要求的是一致，并不是正确，如果所有节点给出一个"错误"的答案，那也叫一致性 ``` 对于不同的场景，用户角度对于一致性的要求是不一样的，例如: 1.银行系统:你在柜台存了一笔钱，同时你的朋友转账给你一笔钱，你的女朋友同时又在淘宝消费了一笔钱，你可能会感觉很乱，但你相信，最后你的余额一定是对的，银行可以慢一点，但不会把钱搞错。 2.电商系统:你在淘宝看到一个库存为5的衣服，然后你快速下单，但是被提示"库存不足，无法购买"，你会觉得自己动作太慢，被人抢走了，不太关心库存为啥显示5 3.论坛小站:你注册一个论坛，需要手机验证码，点完发送之后，一直没有响应，过了一天你才收到了这条短信，不过小站而已，不注册也就罢了。 上面是夸张了的的用户情况，在实际业务中，一致性也是分等级的，如强一致行和弱一致性，怎么使用要看具体和系统的容忍度。 强一致性和弱一致性只是一种统称，按照从强到弱，可以划分为: 1.线性一致性Linearizability consitency,也叫原子性 2.顺序一致性Sequential  consistency 3.因果一致性Causal consistency 4.最终一致性Eventual consistency 强一致性包括线性一致性和顺序一致性，其他的如最终一致性都是弱一致性。 关于强和弱的定义，可以参考剑桥大学的slide ```c Strong consistency - ensures that only consistent state can be seen. * All replicas return the same value when queried for the attribute of an object. This may be achieved at a cost - high latency. Weak consistency - for when "fast access" requriement domainates * update some replica, e.g. the closest or some designated replica * the update replica sends up date messages to all other replicas. * different replicas can return different values for the queried attribute of the value should be returned ,or "not known", with a timestamp * in the long term all updates must propagte to all replicas .... ``` 强一致性集群中，对任何一个节点发起请求都会得到相同的回复，但将产生相对高的延迟。而弱一致性具有更低的响应延迟，但可能会回复过期的数据，最终一致性即是经过一段时间后会达到一致的弱一致性

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

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

举例说明

举例说明1:下面的图满足了顺序一致，但不满足线性一致 1.x和y的初始值为0 2.Write(x,4)代表写入x=4，Read(y,2)为读取y=2 从图上看，进程P1，P2的一致性并没有冲突。因为从这两个进程的角度来看，顺序应该是这样的。 ```c Write(y,2), Read(x,0), Write(x,4), Read(y,2) ``` 这个顺序对于两个进程内部的读写顺序都是合理的，只是这个顺序与全局时钟下看到的顺序并不一样。在全局时钟的观点来看，P2进程对变量X的读操作在P1进程对变量X的写操作之后，然而P2读出来的却是就数据0

举例说明2: 假设我们有个分布式KV系统，以下是四个进程对其的操作顺序和结果: -表示持续的时间，因为一次写入或者读取，客户端从发起到响应是由时间的，发起早的客户端，不一定拿到数据就早，有可能因为网络延迟反而更晚。 情况1: ```c A:--W(x,1)------------------------ B:  --W(x,2)------------------------ C:                                   -R(x,1)-         --R(x,2)- D:                     -R(x,1)-              --R(x,2)-- ``` 情况2 ```c A:--W(x,1)------------------------ B:  --W(x,2)------------------------ C:                                 -R(x,2)-        --R(x,1)-- D:                          -R(x,2)-          --R(x,1)-- ``` 上面情况1和2都是满足顺序一致性的，C和D拿到的顺序都是1-2或2-1，只要CD的顺序一致，就是满足顺序一致性。只是从全局看来，情况1更真实，情况2就显得"错误"了，因为情况2是这样的顺序 ```c B W(x,2) -> A W(x,1) -> C R(x,2) -> D R(x,2) -> C R(x,1) -> D R(x,1) ``` 不过一致性不保证正确性，所以这仍然是一个顺序一致，再加一种情况3 ```c A:--W(x,1)------------------------ B:  --W(x,2)------------------------ C:                            -R(x,2)             --R(x,1)- D:                      -R(x,1)-            --R(x,2)--  ``` 情况3就不属于顺序一致了，因为C和D两个进程的读取顺序不同了，回到情况2，C和D拿数据发起的时间是不同的，且有重叠，有可能C拿到1的时候，D已经拿到了2，这就导致了不同的客户端在相同的时间获取了不一样的数据，但其实这种模式在现实中的用的听广泛的: 如，你在Twitter上写了两条推文，你的操作会耗费一定的时间渗透进一层层的缓存系统，不同的朋友将在不同的时间看到你的信息，但每个朋友都会以相同顺序看到了你的两条推文，不会是乱序。只是一个朋友已经看到了第二条，一个朋友才刚看到第一条，不过没关系，它总会看到两条，顺序没错就行，无伤大雅。但有些时候，顺序一致性是不满足要求的

举例说明3： 从时间轴上可以看到，B0发生在A0之前，读取到的x值为0.B2发生A0之后，读取到的x值为1.而读操作B1,C0,C1与写操作A0在时间轴上有重叠，因此它们可能读取到旧的值0，也可能读取到新的值1，注意，C1发生在B1之后(二者在时间轴上没有重叠)，但是B1看到x的新值，C1反而看到的是旧值。对于用户来说，x的值发生了回调。即要求任何一次读都能读取到最新数据，和全局时钟一致，对比例1，既满足顺序一致又满足线性一致应该是这样的。如图所示。 每个读操作都读到了该变量的最新写的结果，同时两个进程看到的操作顺序与全局时钟的顺序一样，都是Write(y,2),Read(x,4),Write(x,4)，Read(y,2)

ZooKeeper. 一种说法是ZooKeeper是最终一致性，因为由于多副本、以及保证大多数成功的ZAB协议，当一个客户端进程写入一个新值，另外一个客户端进程不能保证马上就能读到这个值，但是能保证最终能读取到这个值。另外一种说法是ZooKeeper的ZAB协议类似于Paxos，提供了强一致性。但这两种说法都不准确，ZooKeeper文档中明确写明它的一致性是Sequential Consitency即顺序一致。ZooKeeper中针对同一个FollowerA提交的写请求request1、request2，某些Follower虽然可能不能在提交成功后立即看到(也就是强一致性)，但经过自身与Leader之间的同步后，这些Follower在看到这连个请求时，一定是先看到request1，request2,两个请求之间不会乱序，即顺序一致性。 其实，实现ZooKeeper的一致性更复杂一些，ZooKeeper的读操作是sequential consistency的，ZooKeeper的写操作是linearizability的，关于这个说法，ZooKeeper的官方文档中没有写出来，但是在社区的邮件组有详细的讨论。ZooKeeper的论文《Modular Composition of Coordination Services》中也有提到这个观点。 总结一下，可以这么理解ZooKeeper：从整体(read操作 + write操作)上来说是sequential consistency，写操作实现了Linearizability

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

etcd与raft。 上面提到ZooKeeper的写是线性一致性，读是顺序一致性。而etecd读写都做了线性一致，即etcd是标准的强一致性保证。 etcd是基于raft来实现的，raft是共识算法，虽然共识和一致性的关系很微妙，经常一起讨论，但共识算法只是提供基础，要实现线性一致还需要在算法之上做出更多的努力如库封装，代码实现等。如Raft中对于一致性读给出了两种方案，来保证处理这次读请求的一定是Leader: 1.ReadIndex 2.LeaseRead 基于Raft的软件有很多，如etcd、tidb、SOFAJRaft等，这些软件在实现一致读时都是基于这两种方式。这里对ReadIndex和Lease Read做下解释，即etcd中线性一致性读的具体实现。由于在Raft算法中，写操作成功仅仅意味着日志达成了一致(已经落盘)，而并不能确保当前状态机也已经apply了日志。状态机apply日志的行为在大多数Raft算法的实现中都是异步的，所以此时读取状态机并不能准确反映数据的状态，很可能会读到过期数据。 基于以上这个原因，要想实现线性一致性读，一个交为简单通用的策略就是:每次读操作的时候记录此时集群的committed index,当状态机的apply index大于或等于committed index时才读取数据并返回。由于此时状态机已经把度请求发起时的已提交日志进行了apply动作，所以此时状态机的状态就可以响应度请求发起时的状态，符合线性一致性读的要求。这便是ReadIndex算法。 那如何准确获取集群的committed index？如果获取到的committed index不准确，那么以不准确的committed index为基准的ReadIndex算法讲可能拿到过期数据。为了确保committed index的准确，我们需要: 1.让leader来处理读请求 2.如果follower收到读请求，将请求forward给leader 3.确保当前leader仍然是leader leader会发起一次广播请求，如果还能收到大多数节点的应答，则说明此时leader还是leader.这点非常关键，如果没有这个环节，leader有可能因网络分区等原因已不再是leader,度请求依然由过期的leader处理，那么久将有可能读到过去的数。这样，我们从leader获取的committed index久作为此次读请求的ReadIndex.

以网络分区为例: 1.初始状态时集群有5个节点:A、B、C、D和E,其中A是leader； 2.发生网络隔离，集群被分割成两部分，一个A和B，另外一个是C、D、E。虽然A会持续向其他介个节点发送headerbeat,但由于网络隔离，C、D、E将无法接收到A的heartbeat。默认地，A不处理向follower节点发送heartbeat失败(此处为网络超时)的情况(协议没有明确说明heartbeat是一个必须收到follower ack的双向过程); 3.C、D、E组成的分区在经过一定时间没有收到leader的heartbeat后，触发election timeout，此时C成为leader.此时，原来5节点集群因网络分区分割成两个集群:小集群A和B;大集群C、D、E,C为leader 4.此时客户端进行读写操作。在Raft算法中，客户端无法感知集群的leader变化(更无法感知服务端有网络隔离的事件发生)。客户端在向集群发起读写请求时。如果客户端一开始选择C节点，并成功写入数据(C节点集群已经commit操作日志)，然后因客户端某些原因(比如断线重连)，选择节点A进行读操作。由于A并不知道另外3个节点已经组成当前集群的大多数并写入了新的数据，所以节点A无法返回准确的数据。此时客户端将读到过期数据。不过相应地，如果此时客户端向节点A发起写操作，那么写操作将失败，因为A因网络隔离无法收到大多数节点的写入响应 5.针对上述情况，其实节点C、D、E组成的新集群才是当前5节点集群中大多数，读写操作应该发生在这个集群中而不是原来的小集群(节点A和B).如果此时节点A能感知它已经不再是集群的leader,那么节点A将不再处理读写请求。于是，我们可以在leader处理读写请求时，发起一次check quorum环节: leader向集群的所有节点发起广播。当leader还能收到集群大多数节点的响应，说明leader还是当前集群的有效leader,拥有当前集群完整的数据，否则，读请求失败，将迫使客户端崇训选择新节点进行读写 这样一来，Raft算法久可以保障CAP中的C和P,但无法保障A:网络分区时并不是所有节点都可以响应请求，少数节点的分区将无法进行服务，从而不符合Availablility。因此，Raft算法是CP类型的一致性算法

Raft保证读请求Linearizability的方法: 1.Leader把每次读请求作为一条日志记录，以日志复制的形式提交，并应用到状态机后，读取状态机中的数据返回(一次RTT、一次磁盘写) 2.使用Leader Lease，保证整个集群只有一个Leader，Leader接收到请求后，记录下当前的commit index为read index,当apply index大于等于read index后，则可以读取状态机中的数据返回(0次RTT、0次磁盘写) 3.不适用Leader Lease，而是当Leader通过以下两点保证整个集群中只有其一个正常工作的Leader: 3.1 在每个Term开始时，由于新选出的leader可能不知道上一个Term的commit index，所以需要先在当前新的Term提交一条空操作的日志； 3.2 Leader每次接到读请求后，向多数节点发送心跳确认自己的Leader身份。之后的读流程与Leader Lease的做法相同。(一次RTT、0次磁盘写) 4.从Follower节点读:Follower先向Leader询问read index，Leader收到Follower的请求后依然要通过2或3中的方法确认自己Leader的身份，然后返回当前的commit index作为read index，Follower拿到read index后，等待本地的apply index大于等于read index后，即可读取状态机中的数据返回(2次或1次RTT、0次磁盘写)

Linearizability和Serializability。 Serializability是数据库领域的概念，而Lineaizability是分布式系统、并发编程领域的东西，在这个分布式SQL时代，自然Linearizability和Serializability会经常一起出现。 1.Serializability:数据库领域的ACID中的I.数据库的四种隔离级别，由弱到强分别是Read Uncommited, Read Committed(RC)，Repeatable Read(RR)和Serializability Serializability的含义是:对并发事务包含的操作进行调度后的结果和某种把这些事务一个接一个的执行之后的结果一样。最简单的一种调度实现就是真的把所有的事务进行排队，一个个的执行，显然这满足Serializability，问题就是性能。可以看出Serializability是与数据库事务相关的一个概念，一个事务包含多个读、写操作，这些操作又涉及到多个数据对象。 1.Linearizability:针对单个操作，单个数据对象而说的，属于CAP中C这个范畴。一个数据被更新后，能够立马被后续的读操作读到 2.Strict Serializability:同时满足Serializability和Linearizability 举个最简单的例子:两个事务T1,T2，T1先开始，更新数据对象o,T1提交。接着T2开始，读数据对象o,提交。以下两种调度: 1.T1,T2,满足Serializability，也满足Linearizability 2.T2,T1,满足Serializability，不满足Linearizability,因为T1之前更新的数据T2读不到

因果一致性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最终一致

ACID理论。 ACID是处理事务的原则，一般特指数据库的一致性约束，ACID一致性完全与数据库规则相关，包括约束，级联，触发器等。在事务开始之前和事务结束以后，都必须遵守这些不变量，保证数据库的完整性不被破坏，因此ACID中的C表示数据库执行事务前后状态的一致性，防止非法事务导致数据库被破坏。比如银行系统A和B两个账户的余额总和为100，那么无论A,B之间怎么转换，这个余额和是不变的，前后一致的. 这里的C代表的一致性：事务必须遵循数据库的已定义规则和约束，例如约束、级联和触发器。因此，任何写入数据的数据都必须有效，并且完成的任何事务都会该笔那数据库的状态。没有事务可以创建无效的数据状态。注意，这与CAP定理中定义的一致性是不同的。 ACID可以翻译为酸，相对应得是碱，也就是BASE.不过提BASE之前要先说下CAP，毕竟，BASE是基于CAP理论提出的折中理论

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中也有事务的操作，比如迷你事务