distributed algorithm

极客时间 分布式算法 整理

Paxos

basic paxos

proposer： 发起请求的人，提议一个值，用于投票表决

acceptor：对每个提议的值进行投票

learner：被告知投票结果，接受达成共识的值。一般来说，学习者是数据备份节点，比如【Master-Slave】模型中的 Slave，被动地接受数据，容灾备份。

stage

prepare

客户端发送准备请求，节点接受提案号，并作出响应【尚无提案】，承诺不接受比当前节点获得提案号小的提案号。如果接收到了小于当前节点提案号的提案，那么节点将不接受并且不做响应。

Accept

客户端收到大多数节点的准备响应后发送接收请求，这时会提交提案号和提案值，如果客户端接收的准备响应为【尚无提案】，那么会将自己的提案值提交给节点。节点接收时，按准备阶段接收的小提案号的提案请求会被拒绝，大于等于的会被接受达成共识。

如果集群中有学习者，当接受者通过提案就会通知所有学习者。学习者发现大多数接收者通过了某个提案就会学习（接受）该提案的值。

Acceptor 保证三个承诺，具体来说：如果准备请求的提案编号，小于等于接受者已经响应的准备请求的提案编号，那么接受者将承诺不响应这个准备请求；
如果接受请求中的提案的提案编号，小于接受者已经响应的准备请求的提案编号，那么接受者将承诺不通过这个提案；
如果接受者之前有通过提案，那么接受者将承诺，会在准备请求的响应中，包含已经通过的最大编号的提案信息。

basic paxos 能容忍一半以内的节点过账

multi-paxos

review

basic paxos 只能就单个值达成共识，一旦遇到为一系列值实现共识时就不管用了。

Multi-Paxos 是一种思想，不是算法。而Multi-Paxos 算法是一个统称，它是指基于 Multi-Paxos 思想，通过多个 Basic Paxos实例实现一系列值的共识的算法（比如 Chubby Multi-Paxos 实现、Raft 算法等）。

problem

如果多个提议者同时提交提案，可能出现因为提案冲突，在准备阶段没有提议者接收到大多数准备响应，协商失败，需要重新协商。你想象一下，一个 5 节点的集群，如果 3个节点作为提议者同时提案，就可能发生因为没有提议者接收大多数响应（比如 1 个提议者接收到 1 个准备响应，另外 2 个提议者分别接收到 2 个准备响应）而准备失败，需要重新协商。

2轮的 rpc 消耗较大，延迟高，不建议

leader

引入领导者，让领导者作为唯一的提议者，这样不存在多个提议者提议自然也就没有冲突了。

客户端【A，B，C】 <-> 【single leader】 <-> 节点【I, II】

optimize

当领导者处于稳定状态时，省掉准备阶段，直接进入接受阶段。

Chubby 的 Multi-Paxos 实现

1. 引入了 leader

2. leader 是通过执行 basic paxos 投票选举产生的，并且运行过程中主节点通过续租来延长 租期(Lease)。实际场景中可能几天内都是同一个节点作为leader，leader故障后其他节点会选举新的leader，即leader一直存在且唯一。

3. 实现了优化：稳定态省掉准备阶段

   1. 稳定态：领导者节点上，序列中的命令是最新的，不再需要通过准备请求来发现之前被大多数节点通过的 提案，领导者可以独立指定提案中的值。
   2. 准备阶段的意义，是发现接受者节点上，已经通过的提案的值。如果在所有接受者节点上，都没有已经通过的提案了，这时，领导者就可以自己指定提案的值了，那么，准备阶 段就没有意义了，也就是可以省掉了。

4. 实现了成员变更，保证节点变更时集群平稳运行。

5. 为了实现强一致性，读操作也只能在主节点上执行。

Raft

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

role which also called server state

• Follower: accept and process message from leader, and election itself as candidate when the heartbeat to leader timeout.
• Candidate: send request vote(rpc message) to other nodes. It will be promoted to leader if only it won majority votes.
• Leader：1. process write request 2. manage log copy 3. restrict them from initiating new elections by sending heartbeats

tips: Raft use strong leader model, only one leader can be existed.

跟随者：就相当于普通群众，默默地接收和处理来自领导者的消息，当等待领导者心跳 信息超时的时候，就主动站出来，推荐自己当候选人
候选人：候选人将向其他节点发送请求投票（RequestVote）RPC 消息，通知其他节点来投票，如果赢得了大多数选票，就晋升当领导者
领导者：蛮不讲理的霸道总裁，一切以我为准，平常的主要工作内容就是 3 部分，处理写请求、管理日志复制和不断地发送心跳信息，通知其他节点“我是领导者，我还活着，你们现在不要发起新的选举，找个新领导者来替代我。”

leader election process

1. all nodes begin as follower state with zero term. 在初始状态下，集群中所有的节点都是跟随者的状态。
2. raft has implemented random timeout feature. Raft 算法实现了随机超时时间的特性。
3. the node A has minimum timout will be the first one does not get the leader’s heart beat. 它会最先因为没有等到领导者的心跳信息，发生超时。
4. At this time, node A will increase its term and elect itself as candidate. It votes itself first and then send voteRequest to other node with asking them elect A as Leader.这个时候，节点 A 就增加自己的任期编号，并推举自己为候选人，先给自己投上一张选票，然后向其他节点发送请求投票 RPC 消息，请它们选举自己为领导者。
5. When other noe accept A request but does not vote at term 1, it will vote A and increase its term.如果其他节点接收到候选人 A 的请求投票 RPC 消息，在编号为 1 的这届任期内，也还没有进行过投票，那么它将把选票投给节点 A，并增加自己的任期编号
6. If candidate win majority votes in the ‘elect timeout’. it will be the leader at that term.如果候选人在选举超时时间内赢得了大多数的选票，那么它就会成为本届任期内新的领导者。
7. When node A as the leader, it will periodically send heart beat to inform other nodes it’s the leader and prevent followers initiating election. 节点 A 当选领导者后，他将周期性地发送心跳消息，通知其他服务器我是领导者，阻止跟随者发起新的选举。

QA

1. Q: How do nodes communicate ?
   1. RequestVote Rpc, send from candidate at election time, to inform other node send vote.
   2. AppendEntries Rpc, send from leader to copy log and provide heart beat message.
2. Q: What is the term ?
   1. Follower will increase its term when elect itself as candidate at waiting leader’s heart beat timeout. 跟随者在等待领导者心跳信息超时后，推举自己为候选人时，会增加自己的任期号.
   2. When node get term field at vote request from other nodes, it will update its term to max(its term, vote's term)
   3. candidate or leader will be follower immediately when it receives greater term from other request.
   4. node will reject the request if its term is smaller than node has.
3. Q: rules in election?
   1. leader send heart beat to all followers.
   2. follower elect itself when leader’s heartbeat timeout.
   3. candidate will be leader if win the majority votes.
   4. leader will be still leader except problem(leader dead or network delay) happened.
   5. At each term every node will send no more than one vote with first come first got rule.
      1. 在一次选举中，每一个服务器节点最多会对一个任期编号投出一张选票，并且按照“先来先服务”的原则进行投票。比如节点 C 的任期编号为 3，先收到了 1 个包含任期编号为 4 的投票请求（来自节点 A），然后又收到了 1 个包含任期编号为 4 的投票请求（来 自节点 B）。那么节点 C 将会把唯一一张选票投给节点 A，当再收到节点 B 的投票请求RPC 消息时，对于编号为 4 的任期，已没有选票可投了。
   6. When got the same term, follower with high log integrity will reject send vote to lower log integrity.
      1. 当任期编号相同时，日志完整性高的跟随者（也就是最后一条日志项对应的任期编号值更大，索引号更大），拒绝投票给日志完整性低的候选人。
      2. 比如节点 B、C 的任期编号都是 3，节点 B 的最后一条日志项对应的任期编号为 3，而节点 C 为 2，那么当节点 C请求节点 B 投票给自己时，节点 B 将拒绝投票。
   7. The election is initiated by followers, who elect themselves as candidates; Majority votes refer to more than half of the votes of cluster members; The goal of the majority voting rule is to ensure that there is at most one leader in a given term of office.
      1. 选举是跟随者发起的，推举自己为候选人；大多数选票是指集群成员半数以上的选票；大多数选票规则的目标，是为了保证在一个给定的任期内最多只有一个领导者。
4. Q: random timeout
   1. follower wait leader’s heartbeat.跟随者等待领导者心跳信息超时的时间间隔，是随机的
   2. Election will be invalid if no candidate win majority vote. 当没有候选人赢得过半票数，选举无效了，这时需要等待一个随机时间间隔，也就是说，等待选举超时的时间间隔，是随机的
5. Important notes:
   1. node with high log integrity can be the leader, log must be successive.
   2. all methods include –term, leader’s heartbeat, random election timeout, first come will be first served vote rule, majority votes rule and so on are trying to promise only one leader at each term and decrease the possibility of failure situation.

how to copy log

log entry

Replica date exists in the form of logs, and log was constructed by log entry.

1. command send from client’s request will be executed by status machine.

2. log index an increase digit number, identifies log entry.

3. the term number of leader who created this log entry.

copy log

1. 接收到客户端请求后，领导者基于客户端请求中的指令，创建一个新日志项，并附加到本地日志中。
2. 领导者通过日志复制 RPC，将新的日志项复制到其他的服务器。
3. 当领导者将日志项，成功复制到大多数的服务器上的时候，领导者会将这条日志项提交到它的状态机中。
4. 领导者将执行的结果返回给客户端。
5. 当跟随者接收到心跳信息，或者新的日志复制 RPC 消息后，如果跟随者发现领导者已经提交了某条日志项，而它还没提交，那么跟随者就将这条日志项提交到本地的状态机中。

keep consistency of log

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，复制并更新覆盖该索引值之后的日志项（也就是不一致的日志项），最终实现了集群各节点日志的一致。
6. 领导者从来不会 覆盖或者删除自己的日志。

Member Changes

配置，建议这么理解：它就是在说集群是哪些节点组成的，是集群各节点地址信息的集合。比如节点 A、B、C 组成的集群，那么集群的配置就是[A, B, C]集合。

单节点变更，就是通过一次变更一个节点实现成员变更。不管旧的集群配置是怎么组成的，旧配置的“大多数”和新配置的“大多数”都会有一个节点是重叠的。

需要你注意的是，在分区错误、节点故障等情况下，如果我们并发执行单节点变更，那么就可能出现一次单节点变更尚未完成，新的单节点变更又在执行，
导致集群出现 2 个领导者的情况。
如果你遇到这种情况，可以在领导者启动时，创建一个 NO_OP 日志项（也就是空日志项），只有当领导者将 NO_OP 日志项提交后，再执行成员变更请求

Gossip protocol

业务在可用性上比较敏感，比如监控主机和业务运行的告警系统。这个时候，相信你希望自己的系统能在极端情况下（比如集群中只有一个节点在运行）也能运行。
回忆了二阶段提交协议和 Raft 算法之后，你发现它们都需要全部节点或者大多数节点正常运行，才能稳定运行。可以通过 Gossip 协议实现这个目标。

直接邮寄（Direct Mail）

直接发送更新数据，当数据发送失败时，将数据缓存下来，然后重传。但注意下缓存队列满了丢数据的问题，只采用直接邮寄是无法实现最终一致性的，想最终一致得依靠反熵

反熵（Anti-entropy）

反熵指的是集群中的节点，每隔段时间就随机选择某个其他节点，然后通过互相交换自己的所有数据来消除两者之间的差异，实现数据的最终一致性

• 推：是将自己的所有副本数据，推给对方，修复对方副本中的熵：
• 拉：是拉取对方的所有副本数据，修复自己副本中的熵
• 推拉：同时修复自己副本和对方副本中的熵

反熵需要节点两两交换和比对自己所有的数据，执行反熵时通讯成本会很高，所以不建议在实际场景中频繁执行反熵， 并且可以通过引入校验和（Checksum）等机制，降低需要对比的数据量和通讯消息等。

虽然反熵很实用，但是执行反熵时，相关的节点都是已知的，而且节点数量不能太多，如果 是一个动态变化或节点数比较多的分布式环境（比如在 DevOps 环境中检测节点故障，并动态维护集群节点状态），这时反熵就不适用了。
那么当你面临这个情况要怎样实现最终一致性呢？答案就是谣言传播。

谣言传播（Rumor mongering）

当一个节点有了新数据后，这个节点变成活跃状态，并周期性地联系其他节点向其发送新数据，直到所有的节点都存储了该新数据（非常具有传染性）

如何使用 Anti-entropy 实现最终一致： InfluxDB 的反熵样例

在自研 InfluxDB 中，一份数据副本是由多个分片组成的，也就是实现了数据分片，三节点三副本的集群，就像下图的样子：

NodeA:Shard]1,S2; NodeB:S1,S2; NodeC:S1,S2

Node ABC 上分片的数据是一致的。

数据丢失的两种功能情况

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

第一种情况修复起来不复杂，我们只需要将分片数据，通过 RPC 通讯，从其他节点上拷贝过来就可以了。

第二种需要设计一个闭环的流程，按照一个顺序修复，执行完流程后，也就是实现了一致性了。
它是按照一定顺序来修复节点的数据差异，先随机选择一个节点，然后循环修复，每个节点生成 自己节点有、下一个节点没有的差异数据，发送给下一个节点，进行修复.
数据修复的起始节点为节点 A，数据修复是按照顺时针顺序，循环修复的。
需要你注意的是，最后节点 A 又对节点 B 的数据执行了一次数据修复操作，因为只有这样，节点 C 有、节点 B 缺失的差异数据，才会同步到节点 B 上.

非随机的原因是希望能在一个确定的时间范围内实现数据副本的最终一致性，而不是基于随机性的概率，在一个不确定的时间范围内实现数据副本的最终一致性

最后需要你注意的是，因为反熵需要做一致性对比，很消耗系统性能，所以建议你将是否启用反熵功能、执行一致性检测的时间间隔等，做成可配置的，能在不同场景中按需使用。

Quorum NWR

适用于已经实现AP了，临时的需求需要C（最终一致性），那么可以采用这个算法，当 W + R > N 时，就可以实现强一致性

N 表示副本数，又叫做复制因子（Replication Factor）。即 N 表示集群中同一份数据有多少个副本。
例如在三节点的集群中，DATA-1 有 2 个副本，DATA-2 有 3 个副本，DATA-3 有 1 个副本。也就是说，副本数可以不等于节点数，不同的数据可以有不同的副本数。

Quorum NWR 需要实现自定义副本的功能。也就是说，用户可以自定义指定数据的副本数。

W，又称写一致性级别（Write Consistency Level），表示成功完成 W 个副本更新，才完成该份数据的写操作

R，又称读一致性级别（Read Consistency Level），表示读取一个数据对象时需要读 R 个副本。

W + R > N 代表 WR必有交集，交集点就是最新的数据

如何实现 Quorum NWR

InfluxDB 中创建保留策略时设置指定DB的副本数可用命令
create retention policy “rp_one_day” on “telegraf” duration 1d replication 3
通过 replication 参数指定了数据库 telegraf 的副本数为3

副本数不能超过节点数据。你可以这么理解，多副本的意义在于冗余备份，如果副本数超过节点数，就意味着在一个节点上会存在多个副本，那么这时冗余备份的意义就不大了。
比如机器故障时，节点上的多个副本是同时被影响的。

InfluxDB 企业版，支持“any、one、quorum、all”4 种写一致性级别：

1. any：任何一个节点写入成功后，或者接收节点已将数据写入 Hinted-handoff 缓存（也就是写其他节点失败后，本地节点上缓存写失败数据的队列）后，就会返回成功给客户端。
2. one：任何一个节点写入成功后，立即返回成功给客户端，不包括成功写入到 Hinted-handoff 缓存。
3. quorum：当大多数节点写入成功后，就会返回成功给客户端。此选项仅在副本数大于 2时才有意义，否则等效于 all。
4. all：仅在所有节点都写入成功后，返回成功。

对时序数据库而言，读操作常会拉取大量数据，查询性能是挑战，是必须要考虑优化的，因此，在 InfluxDB 企业版中，不支持读一致性级别，只支持写一致性级别。
另外，我们可以通过设置写一致性级别为 all，来实现强一致性。

N 决定了副本的冗余备份能力；
如果设置 W = N，读性能比较好；
如果设置 R = N，写性能比较好；
如果设置 W = (N + 1) / 2、R = (N + 1) / 2，容错能力比较好，能容忍少数节点（也就是 (N - 1) / 2）的故障。

PBFT

口信消息法有个非常致命的缺陷（为什么落地困难）。如果将军数为 n、叛将数为 f，那么算法需要递归协商 f+1 轮，消息复杂度为 O(n ^ (f + 1))，消息数量指数级暴增。
你可以想象一下， 如果叛将数为 64，消息数已经远远超过 int64 所能表示的了，这是无法想象的。

PBFT 如何达成共识

在这里我想说的是， PBFT 算法是通过签名（或消息认证码 MAC）约束恶意节点的行为， 也就是说，每个节点都可以通过验证消息签名确认消息的发送来源，一个节点无法伪造另外一个节点的消息。最终，基于大多数原则（2f + 1）实现共识的。

需要你注意的是，最终的共识是否达成，客户端（苏秦）是会做判断的，如果客户端在指定时间内未收到请求对应的 f + 1 相同响应，就认为集群出故障了，共识未达成，客户端会重新发送请求。

另外需要你注意的是，PBFT 算法通过视图变更（View Change）的方式，来处理主节点（赵国将领）作恶，当发现主节点在作恶时，会以“轮流上岗”方式，推举新的主节点。

消息消耗仍然较高

最后我想说的是，尽管 PBFT 算法相比口信消息型拜占庭之解已经有了很大的优化，将消息复杂度从 O(n ^ (f + 1)) 降低为 O(n ^ 2)，能在实际场景中落地，并解决实际的共识问题。
但 PBFT 还是需要比较多的消息。比如在 13 节点集群中（f 为 4）。

• 请求消息：1
• 预准备消息：3f = 12
• 准备消息：3f * (3f - f) = 96
• 提交消息：(3f - f + 1) * (3f + 1)= 117
• 回复消息：3f - 1 = 11
• 也就是说，一次共识协商需要 237 个消息，你看，消息数还是蛮多的，所以我推荐你，在
• 中小型分布式系统中使用 PBFT 算法。

PBFT 算法实现的是一系列值的共识，而不是口信模型的单值的共识

相比 Raft 算法完全不适应有人作恶的场景，PBFT 算法能容忍 (n - 1)/3 个恶意节点 (也可以是故障节点)。
另外，相比 PoW 算法，PBFT 的优点是不消耗算力，所以在日常实践中，PBFT 比较适用于相对“可信”的场景中，比如联盟链。
需要你注意的是，PBFT 算法与 Raft 算法类似，也存在一个“领导者”（就是主节点）， 同样，集群的性能也受限于“领导者”。
另外，O(n ^ 2) 的消息复杂度，以及随着消息数的增加，网络时延对系统运行的影响也会越大，这些都限制了运行 PBFT 算法的分布式系统的规模，也决定了 PBFT 算法适用于中小型分布式系统。

PoW算法

背景： PBFT 算法虽然能防止坏人作恶，但只能防止少数的坏人作恶，也就是 (n - 1) / 3 个坏人 (其中 n 为节点数)。
可如果区块链也只能防止一定比例的坏人作恶，那就麻烦了，因为坏人可以不断增加节点数，轻松突破 (n - 1) / 3 的限制。

区块链通过工作量证明（Proof of Work）增加了坏人作恶的成本。

工作量证明 (Proof Of Work）

我们给出的工作量要求是，基于一个基本的字符串（比如”geektime”），你可以在这个字符串后面添加一个整数值，然后对变更后（添加整数值) 的字符串进行 SHA256 哈希运算，
如果运算后得到的哈希值（16 进制形式）是以”0000”开头的，就验证通过。为了达到这个工作量证明的目标，我们需要不停地递增整数值，一个一个试，对得到的新字符串进行SHA256 哈希运算。
按照这个规则，我们需要经过 35024 次计算，才能找到恰好前 4 位为 0 的哈希值。

区块链如何实现 PoW 算法的

区块的组成

• 区块头（Block Head）：区块头主要由上一个区块的哈希值、区块体的哈希值、4 字节的随机数（nonce）等组成的。
• 区块体（Block Body）：区块包含的交易数据，其中的第一笔交易是 Coinbase 交易，这是一笔激励矿工的特殊交易。

拥有 80 字节固定长度的区块头，就是用于区块链工作量证明的哈希运算中输入字符串，而且通过双重 SHA256 哈希运算
（也就是对 SHA256 哈希运算的结果，再执行一次哈希运算），计算出的哈希值，只有小于目标值（target），才是有效的，否则哈希值是无效的，必须重算。