分布式协议与算法实战

按照少数服从多数原则，齐也会进攻

比如齐向楚、燕分别发送了“撤退”的消息，燕向齐和楚发送了“进攻”的消息。
撤退：进攻 =1:1，无论楚投进攻还是撤退，都会成为 2:1，这个时候还是会形成一个一致性的作战方案。

但是，如果楚是叛徒在暗中配合秦国，让信使向齐发送了“撤退”，向燕发送了“进攻”，那么：
燕看到的是，撤退：进攻 =1:2
齐看到的是，撤退：进攻 =2:1
按照少数服从多数的原则，就会出现燕就会单独进攻的场景

三位将军分别拨出一部分军队由苏秦率领，苏秦参与作战计划讨论及执行，这样就增加了忠诚将军的数量

设定默认策略，如果没有收到命令，就执行约定的默认命令，撤退或者进攻，同事约定好流程，比如需要进行两次作战信息协商

第一轮协商：

第二轮协商：

案例推演一：忠诚将军先发起作战指令

案例推演二：叛将先发起作战指令

总结：如果叛将人数为m，将军人数不能少于3m+1，那么拜占庭将军问题就能解决了。
也就是说，如果有n位将军，最多能容忍 (n-1)/3 位叛将

苏秦还可以通过签名的方式，在不增加将军人数的情况下，解决二忠一叛的难题

通过印章、虎符等信物实现特性：忠诚将军的签名无法伪造，而且对他签名消息的内容进行任何更改都会被发现；任何人都能验证将军签名的真伪。

如果忠诚的将军，比如齐先发起作战信息协商，一旦叛将楚修改或伪造收到的作战信息，那么燕在接收到楚的作战信息的时候，会发现齐的作战信息被修改，楚已叛变

如果叛变将军楚先发送误导的作战信息，那么齐和燕将发现楚发送的作战信息是不一致的，知道楚已经叛变。这个时候，他们可以先处理叛将，然后再重新协商作战计划。

总结：通过签名机制约束叛将的叛变行为，任何叛变行为都会被发现，也就会实现无论有多少忠诚的将军和多少叛将，忠诚的将军们总能达成一致的作战计划。

一致性是指，客户端的每次读操作，不管访问哪个节点，要么读取到的都是同一份最新数据，要么读取失败

一致性可以看做是分布式系统对访问本系统的客户端的一种承诺：不管你访问哪个节点，要么都读取失败，要么给你返回的都是绝对一致的问题

可以看出，一致性强调的是数据正确性，各个节点之间的数据一致性，而不是完整性。（完整性强调的是所有数据的状态都是正确的）

可用性是指，不管客户端访问哪个节点，都能得到响应数据，但不保证是同一份最新数据

可用性可以看做是分布式系统对访问本系统客户端的另一种承诺：我一定会给你返回数据，不会不相应你的请求，但是不保证每个节点的数据都是最新的

可以看出，可用性强调的是服务可用，但不保证数据一致性

分区容错性是指，当任意数量的消息丢失或延迟到达时，系统仍会继续提供服务，不会挂掉。

分区容错性可以看做分布式系统对访问本系统客户端的一种承诺：不管我内部出现什么问题，我会一直运行，提供服务

可以看出，分区容错性强调的是对分区故障的容错能力，系统不挂掉

CAP不可能三角说的是对于一个分布式系统而言，一致性（Consistency）、可用性（Availability）、分区容错性（PartitionTolerance）3个指标不可兼得，只能在3个指标中选择2个。

Raft算法是一个强领导者模型，所有请求都是在领导者节点上处理，整个集群的性能等于领导者的单节点性能，这样就会造成集群性能低下，无法支撑海量的时序数据

Raft算法受限于强领导者模型，只能拓展读性能，写性能无法提升

Raft算法一切以领导者为准的日志负责特性，可能会导致DATA节点丢失数据

第一步，赵分别向魏、韩发送消息：“明天攻打秦国，方便吗？”

第二步，赵、魏、韩，分别评估明天能否去攻打秦国，如果能，就预留时间并锁定，不再安排其他军事活动。

第三步，赵得到全部的回复结果（包括他自己的评估结果），都是 YES。

二阶段是反可伸缩性的，因为在第一阶段，需要预留资源，也就是会锁定资源，其他人不能操作，因此在大规模场景下，并不是最优解。

由于协调者的重要性，一旦协调者发生故障。参与者会一直阻塞下去。尤其在第二阶段，协调者发生故障，那么所有的参与者还都处于锁定事务资源的状态中，而无法继续完成事务操作。

因此2PC算法可以概括为：参与者将操作成败通知协调者，再由协调者根据所有参与者反馈的情况决定各参与者是否要提交操作还是中止操作。

两个阶段是指：第一阶段：准备阶段（投票阶段）和第二阶段：提交阶段（执行阶段）

准备阶段

事务协调者（事务管理器）给每个参与者（资源管理器）发送Prepare消息，每个参与者要么直接返回失败（如权限验证失败），要么在本地执行事务，写本地redo和undo日志，但是不提交事务，达到一种“万事俱备，只欠东风”的状态。

可以将准备阶段进一步分为以下三个步骤：

- 协调者节点向所有参与者节点询问是否可以执行提交操作，并开始等待各参与者的响应
- 参与者节点执行询问发起为止的所有事务操作，并将Undo信息和Redo信息写入日志。（注意：若成功这里其实每个参与者已经执行了事务操作）
- 各参与者节点响应协调者节点发起的询问。如果参与者节点的事务操作实际执行成功，则它返回一个”同意”消息；如果参与者节点的事务操作实际执行失败，则它返回一个”中止”消息。

提交阶段

如果协调者收到了参与者的失败消息或者超时，直接给每个参与者发送回滚（Rollback）消息，否则发送提交（Commit）消息；参与者根据协调者的指令执行提交或者回滚操作，释放事物处理过程中的锁资源。

分两种情况来讨论提交阶段：

- 所有参与节点都返回成功
  1. 协调者向所有参与者节点发出“正式提交”请求
  2. 参与者节点正式完成提交操作，并释放整个事物操作期间的锁资源
  3. 参与者节点向协调者节点发送“完成”消息
  4. 协调者节点收到所有参与者节点反馈的“完成”消息后，事物完成
- 存在参与节点返回中止超时
  1. 协调者节点向所有参与者节点发出”回滚操作(rollback)”的请求
  2. 参与者节点利用之前写入的Undo信息执行回滚，并释放在整个事务期间内占用的资源
  3. 参与者节点向协调者节点发送”回滚完成”消息
  4. 协调者节点受到所有参与者节点反馈的”回滚完成”消息后，取消事务

第一步，苏秦分别发送消息通知赵、魏、韩，让他们预留明天的时间和相关资源。然后苏秦实现确认操作（明天攻打秦国），和撤销操作（取消明天攻打秦国）。

第二步，苏秦收到赵、魏、韩的预留答复，都是OK。

第一步，苏秦执行确认操作，通知赵、魏、韩明天攻打秦国。

第二步，收到确认操作的响应，完成分布式事务。

如果预留阶段执行出错，那么就进入撤销阶段

第一步，苏秦执行撤销操作，通知赵、魏、韩取消明天攻打秦国的计划。

第二步，收到撤销操作的响应。

TCC本质上是补偿事务，它的核心思想是针对每个操作都要注册一个与其对应的确认操作和补偿操作（也就是撤销操作）

TCC是一个业务层面的协议，会和业务代码耦合在一起，需要在业务代码中编码实现，为了实现一致性，确认操作和撤销操作必须是幂等的（这两个操作可能会失败重试）

TCC不依赖数据库的事务能力，在业务中实现分布式事务能力，减轻了DB压力，但是对代码侵入性更强，实现复杂度也更高

比如12306在不同的时间出售不同地区的票，将访问请求错开

如果可能预估流量，可以将多余的流量存储与队列中，让系统根据实际消费能力从队列中消费数据

对用户的请求不是不处理，而是先缓存起来，慢慢处理，异步的给到用户处理结果，对用户来说，相应延迟了，对系统来说，能处理的请求更多了

在超出系统负载的大流量过来后，我们可以牺牲系统非核心能力，保障核心能力可用。比如使用小图片替代原始图片，降低日志级别，非核心接口功能降级

如果使用了以上一些手段还是无法应对大流量，那么可以采用过载保护，根据一定的规则或者随机丢弃一些请求，直接返回上游错误。或者是将多余的请求存储与队列中，队列满了就清空。

以最新写入的数据为准，比如AP模型的KV存储就采用这种方式

以第一次写入数据为准，就是说如果不希望存储的数据被更改，就以第一次为准

写时修复

读时修复

异步修复

实践总结：推荐写时修复+异步修复，确保实现最终一致性。读时修复，需要读取多个节点值并进行比较，性能较差，不推荐

提议者（Proposer）、接受者（Acceptor）、学习者（Learner）

提议者（Proposer）

接受者（Acceptor）

学习者（Learner）

在Base Paxos 中，用提案表示一个提议，每个提案包含提案编号和值，比如用 [n,v] 表示一个提案，n为编号，v为值

整个共识协商分成两个阶段，假设，客户端1提案编号为1，客户端2提案编号为5，节点 A、B先收到客户端1的准备请求，节点C先收到客户端2的准备请求

首先客户端 1、2 作为提议者，分别向所有接受者发送包含提案编号的准备请求
注意：在准备请求中是不需要指定提议的值的，只需要携带提案编号就可以了

由于之前没有通过任何提案，所以节点A、B将返回一个“尚无提案”的响应。
也就是说节点A和B在告诉提议者，我之前没有通过任何提案，并承诺以后不再响应提案编号小于等于1的准备请求，不会通过编号小于1的提案。

节点C也是如此，它将返回一个“尚无提案”的响应，并承诺以后不再响应提案编号小于等于5的准备请求，不会通过编号小于5的提案。

当节点A、B收到提案编号为5的准备请求，和节点C收到提案编号为1的准备请求的时候

当节点A、B收到提案编号为5的准备请求的时候，因为提案编号5大于它们之前响应的准备请求的提案编号1，而且两个节点都没有通过任何提案，所以它将返回一个“尚无提案”的响应，并承诺以后不再响应提案编号小于等于5的准备请求，不会通过编号小于5的提案。

当节点C收到提案编号为1的准备请求的时候，由于提案编号1小于它之前响应的准备请求的提案编号5，所以丢弃该准备请求，不做响应。

首先客户端1、2在收到大多数节点的准备响应之后，会分别发送接受请求

当客户端1收到大多数的接受者（节点A、B）的准备响应后，根据响应中提案编号最大的提案的值，设置接受请求中的值。因为该值在来自节点A、B的准备响应中都为空（也就是图5中的“尚无提案”），所以就把自己的提议值3作为提案的值，发送接受请求[1,3]。

当客户端2收到大多数的接受者的准备响应后（节点A、B和节点C），根据响应中提案编号最大的提案的值，来设置接受请求中的值。因为该值在来自节点A、B、C的准备响应中都为空（也就是图5和图6中的“尚无提案”），所以就把自己的提议值7作为提案的值，发送接受请求[5,7]。

三个节点收到 2 个客户端的接受请求时

当节点A、B、C收到接受请求[1,3]的时候，由于提案的提案编号1小于三个节点承诺能通过的提案的最小提案编号5，所以提案[1,3]将被拒绝。

当节点A、B、C收到接受请求[5,7]的时候，由于提案的提案编号5不小于三个节点承诺能通过的提案的最小提案编号5，所以就通过提案[5,7]，也就是接受了值7，三个节点就X值为7达成了共识。

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

如果多个提议者同时提交提案，可能会出现提案冲突，导致需要多次协商

两轮RPC通信（准备阶段和提交阶段）往返消息内容多、性能较差、耗时高

原始Paxos算法中并没有说明如何选举领导者，这需要实现Paxos算法的自行实现领导者选举

优化Base-Paxos算法执行：如果领导者是稳定的，那么说明领导中的指令序列是完整且最新的，那么可以省略准备阶段，直接进入提交阶段

首先通过主节点，实现了领导者（Leader）节点的特性，主节点作为唯一的提议者，这样就不会存在多个提议者，解决了提议冲突的问题

然后，主节点通过执行Base-Paxos算法来进行投票选举产生，并且只运行过程中，主节点会通过不断续租的方式来延长租期

其次，Chubby实现了 当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段

最后，Chubby实现了成员变更，保证节点变更时，集群的平稳运行

补充：Chubby为了实现强一致性，度操作也在主节点进行

Raft算法数据Multi-Paxos算法，在Multi-Paxos算法的思想基础上，做了一些简化和限制

Raft算法现在是分布式系统开发首选的共识算法

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

领导者（Leader）

跟随者（Follower）

候选人（Candidate）

在初始状态下，集群中所有的节点都是跟随者的状态，Raft算法实现了随机超时的时间特性，也就是说，每个节点等待领导者心跳信息的超时时间间隔具有随机性。

当某个超时时间最短的节点（节点A）到达超时时间后，A节点会增加自己的任期编号，推举自己为候选人，自己先给自己投一票，然后向其他节点发送请求投票的RPC请求，要求其他节点发起投票推举自己喂领导者

其他节点收到候选人A节点的请求投票RPC消息，在编号为1的任期内，还没有进行过投票，那么他就会把选票投给A节点，并增加自己的任期编号
注意：每个节点在每个任期呢，只会投一票

如果候选人A节点在选举超时时间内赢得了大多数选票，那么就会成为本届任期内的领导者

当节点A成为领导者后，A将会周期性的发送心跳消息，通知其他服务器领导者存在，防止其他很随着发起新的选举

节点间如何通信

什么是任期

领导者选举有哪些规则

如何理解随机超时时间

Raft中日志是由多条日志项（Log entry）组成的

Raft 算法的数据副本是以日志的形式存在的，领导者接收到来自客户端的写请求后，处理写请求的过程就是一个复制和提交日志项的过程

日志项是一种数据格式，主要包含用户指定的数据（也就是指令Command），以及一些附加信息，比如索引值（Log index）、任期编号（Term）

指令：一条由客户端请求指定的、状态机需要执行的指令。也就是客户端指定的数据。

索引值：日志项对应的整数索引值，用来标识日志项的，是一个连续的、单调递增的整数序列

任期编号：创建这条日志项的领导者的任期编号

可以把日志复制理解成一个优化后的二阶段提交，减少一半的往返消息，也就是降低了一半的消息延迟

首先，领导者进入第一阶段，通过日志复制（AppendEntries）RPC消息，将日志项复制到集群其他节点上

紧接着，如果领导者收到大多数的“复制成功”响应后，领导者将日志项提交到自己的状态机，并返回成功给客户端。如果领导者没有收到大多数的复制成功响应，那么将返回错误给客户端

注意：第2步骤中，领导者将日志提交到自己的状态机后，并没有通知跟随者提交日志。这是Raft算法的一个优化，领导者不直接发送消息通知其他节点提交日志项。因为领导者的日志复制RPC消息或者心跳消息中，包含了当前最大的，将会被提交的日志项索引值。所以通过消息复制RPC消息或者心跳消息，跟随者就能知道领导者日志提交的位置信息

因此，当其他节点接受领导者心跳消息或者新的日志复制RPC消息后，会将这条日志项提交到他的状态机。这个优化，减少了一次RPC请求，降低了客户端处理的时延，将二阶段优化为一阶段提交，降低一半的消息延迟。

接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。

领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。

当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项提交到它的状态机中。

领导者将执行的结果返回给客户端。

当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没提交，那么跟随者就将这条日志项提交到本地的状态机中。

在Raft算法中，领导者通过强制跟随者直接复制自己的日志项，处理不一致日志。也就是说，Raft是通过以领导者的日志为准，来实现各节点日志的一致的。具体有2个步骤：

首先，领导者通过日志复制RPC的一致性检查，找到跟随者节点上，与自己相同日志项的最大索引值。也就是说，这个索引值之前的日志，领导者和跟随者是一致的，之后的日志是不一致的了。

然后，领导者强制跟随者更新覆盖的不一致日志项，实现日志的一致。

过程演示：

领导者通过日志复制RPC消息，发送当前最新日志项到跟随者（为了演示方便，假设当前需要复制的日志项是最新的），这个消息的PrevLogEntry值为7，PrevLogTerm值为4。

如果跟随者在它的日志中，找不到与PrevLogEntry值为7、PrevLogTerm值为4的日志项，也就是说它的日志和领导者的不一致了，那么跟随者就会拒绝接收新的日志项，并返回失败信息给领导者。

这时，领导者会递减要复制的日志项的索引值，并发送新的日志项到跟随者，这个消息的PrevLogEntry值为6，PrevLogTerm值为3。

如果跟随者在它的日志中，找到了PrevLogEntry值为6、PrevLogTerm值为3的日志项，那么日志复制RPC返回成功，这样一来，领导者就知道在PrevLogEntry值为6、PrevLogTerm值为3的位置，跟随者的日志项与自己相同。

领导者通过日志复制RPC，复制并更新覆盖该索引值之后的日志项（也就是不一致的日志项），最终实现了集群各节点日志的一致。

在集群中进行成员变更的最大风险是，可能会同时出现 2 个领导者。

在启动集群时，配置是固定的，不存在成员变更，在这种情况下，Raft 的领导者选举能保证只有一个领导者。

单节点变更，就是通过一次变更一个节点实现成员变更。如果需要变更多个节点，那你需要执行多次单节点变更。比如将 3 节点集群扩容为 5 节点集群，这时你需要执行 2 次单节点变更，先将 3 节点集群变更为 4 节点集群，然后再将 4 节点集群变更为 5 节点集群

过程推演

假设，现在有一个节点故障了（比如节点 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 个节点，变为 4 节点集群，只需要迁移 24.3% 的数据

也就是说，一致哈希算法具有较好的容错性和可扩展性

在哈希寻址中常出现这样的问题：客户端访问请求集中在少数的节点上，出现了有些机器高负载，有些机器低负载的情况，那么在一致哈希中，可以通过虚拟节点解决该问题

在一致哈希中，如果节点太少，容易因为节点分布不均匀造成数据访问的冷热不均，也就是说大多数访问请求都会集中少量几个节点上

解决方案：
就是对每一个服务器节点计算多个哈希值，在每个计算结果位置上，都放置一个虚拟节点，并将虚拟节点映射到实际节点。比如，可以在主机名的后面增加编号，分别计算“Node-A-01”“Node-A-02”“Node-B-01”“Node-B-02”“Node-C-01”“Node-C-02”的哈希值，于是形成 6 个虚拟节点

从图中看到，增加了节点后，节点在哈希环上的分布就相对均匀了。这时，如果有访问请求寻址到“Node-A-01”这个虚拟节点，将被重定位到节点 A。

总结：
当节点数越多的时候，使用哈希算法时，需要迁移的数据就越多，使用一致哈希时，需要迁移的数据就越少

当我们向 10 个节点集群中增加节点时，如果使用了哈希算法，需要迁移高达 90.91% 的数据，使用一致哈希的话，只需要迁移 6.48% 的数据。

当 W + R > N 的时候，对于客户端来讲，整个系统能保证强一致性，一定能返回更新后的那份数据

当 W + R < N 的时候，对于客户端来讲，整个系统只能保证最终一致性，可能会返回旧数据。

any：任何一个节点写入成功后，或者接收节点已将数据写入 Hinted-handoff 缓存（也就是写其他节点失败后，本地节点上缓存写失败数据的队列）后，就会返回成功给客户端。

one：任何一个节点写入成功后，立即返回成功给客户端，不包括成功写入到 Hinted-handoff 缓存。

quorum：当大多数节点写入成功后，就会返回成功给客户端。此选项仅在副本数大于 2时才有意义，否则等效于 all。

all：仅在所有节点都写入成功后，返回成功。

在 ZooKeeper 中，数据是以节点的形式存储的

Multi Paxos不能保证操作的顺序性，顺序性也是ZAB协议的关键

本质上 Multi-Paxos 实现的是一系列值的共识，不关心最终达成共识的值是什么，不关心各值的顺序

推方式，就是将自己的所有副本数据，推给对方，修复对方副本中的熵

拉方式，就是拉取对方的所有副本数据，修复自己副本中的熵

推拉方式就是同时修复自己副本和对方副本中的熵

缺失分片：也就是说，在某个节点上整个分片都丢失了。

节点之间的分片不一致：也就是说，节点上分片都存在，但里面的数据不一样，有数据丢失的情况发生。

当赵接收到苏秦的请求之后，会执行三阶段协议（Three-phase protocol）

进入提交阶段后，各将军分别广播提交消息给其他将军，也就是告诉其他将军，我已经准备好了，可以执行指令了

最后，当某个将军收到 2f + 1 个验证通过的提交消息后（包括自己，其中 f 为叛徒数，演示中为 1），也就是说，大部分的将军们已经达成共识，这时可以执行作战指令了，那么该将军将执行苏秦的作战指令，执行完毕后发送执行成功的消息给苏秦。

请求方做了一些运算，解决了某个问题，然后把运算结果发送给验证方，进行核验，验证方根据运算结果，就能判断请求方是否做了相关的工作。

这个算法具有不对称性，也就是说，工作对于请求方是有难度的，对于验证方则是比较简单的，易于验证的

区块头（Block Head）：区块头主要由上一个区块的哈希值、区块体的哈希值、4 字节的随机数（nonce）等组成的

区块体（Block Body）：区块包含的交易数据，其中的第一笔交易是 Coinbase 交易，这是一笔激励矿工的特殊交易