Category Archives: Algorithm

一、概述
将区块链的共识算法放到这里，其实只是做个简单的补充。
想了解更多内容，可以参考:
区块链资料汇总
区块链白皮书

二、常见区块链共识机制说明
1、PoW: Proof of Work，工作量证明
工作量证明中，所有参与的节点一起计算区块的Hash值，通过调整区块的一个随机数nonce，得到不同的Hash值。
最终第一个计算出前N位为0的Hash值，获得记账资格，并获取区块的奖励。
其余节点可以快速验证Hash结果，从而快速达成一致（算出这个Hash工作量很大，验证工作量很小）。
此类区块链，采用长链高于短链的原则，也就是如果产生了分区，短链必须遵从于长链的结果，达到最终一致性。

如果要攻破PoW，需要在该网络中，破坏者算力超过全网络算力一半，才有可能破坏最终一致性。

但PoW计算量太大，能耗太高，而且达成一致性的速度太慢，吞吐量就很难提高。

2、PoS: Proof of Stack，权益证明
权益证明网络中，所有参与节点都知道彼此节点的权益（比如，每个Token*该Token持有时间，然后求和）
在达成一致性的时候，权益越大（Token越多，持有时间越久）的节点，越容易被选择为记账节点

如果要攻破PoS，就需要较长时间持有大量的Token，增加了攻击者的攻击成本。

但PoS会导致，强者恒强，造成垄断。与区块链区中心化的目标，背道而驰。

3、DPoS: Delegated Proof of Stake，委托式权益证明
在委托式权益证明网络中，每个节点都知道彼此节点的权益（比如，持有的Token数）
想参与记账的节点，被叫做受托节点，受托节点会进行竞选，要求普通节点投票给他
普通节点不参与记账，而是根据自己的利益，投票给自己选中的受托节点，节点权益越高，投票权重越高
最终，获得最多投票的受托节点进行记账

三、部分区块链项目的共识机制

一、两阶段提交2PC（Two-Phase Commit）
1、概述
顾名思义，两阶段提交，就是分布式数据库系统，把事务的提交过程，分为两个阶段进行操作，从而保持数据的一致性。

2、流程
a、准备阶段（Prepare Phase）
协调者（Coordinator）收到事务请求。
协调者向所有参与者（Participants）发送准备事务提交的请求。
参与者收到准备请求后，会检查本地事务的状态，判断能否完成此事务请求，并将检查结果反馈给协调者。
如果可以完成请求，参与者需要确保所有操作都已完成，事务处于可以提交、可以回滚的状态。

b、提交阶段（Commit Phase）：
协调者根据所有参与者的反馈结果，决定是否提交事务。
如果任何一个参与者不同意提交，则协调者向所有参与者发送回滚请求，全部参与者进行事务回滚，事务失败。
如果所有参与者都同意提交，则协调者向所有参与者发送提交请求，全部参与者进行事务提交，事务成功。

3、示例
假设我们有一个分布式数据库系统，包含两个数据库实例A和B，以及一个协调者C。

a、准备阶段：
客户端向协调者C发送事务请求。
协调者C向数据库A和B发送准备提交的请求。
数据库A和B检查本地事务状态，判断事务可以提交，确认所有操作已完成，并将结果反馈给协调者C。

b、提交阶段：
数据库A和B都反馈可以提交，协调者C向数据库A和B发送提交请求。
数据库A和B执行提交操作，更新数据并持久化。

二、三阶段提交3PC（Three-Phase Commit）
1、概述
顾名思义，三阶段提交就是分布式数据库系统，把事务的提交过程，分为三个阶段进行操作，可以解决两阶段提交协议2PC的阻塞问题。

2、流程
a、CanCommit阶段
协调者（Coordinator）收到事务请求。
协调者向所有参与者发送一个“CanCommit”请求。
参与者收到请求后，会根据本地状态，判断是否可以完成此事务，并将判断结果反馈给协调者。
如果参与者判断可以支持事务，则返回“就绪”（Ready）；否则，则返回“中止”（Abort）。

b、PreCommit阶段
协调者收到所有参与者的确认消息后。
如果所有参与者都返回“就绪”（Ready），则协调者会向所有参与者发送“PreCommit”请求。
参与者收到请求后，会锁定其资源以防止其他事务干扰，需要确保所有操作都已完成，事务处于可以提交、可以回滚的状态，并返回确认消息给协调者。

如果任何一个参与者不同意提交，则协调者向所有参与者发送取消请求，事务失败。

c、DoCommit阶段
协调者收到所有参与者的确认消息后，如果所有参与者都表示准备好提交事务，则协调者会向所有参与者发送“DoCommit”请求。
参与者收到请求后，会真正提交事务，并返回确认消息给协调者。
协调者收到所有参与者的确认消息后，事务成功。

如果任何一个参与者不同意提交，则协调者向所有参与者发送回滚请求，全部参与者进行事务回滚，事务失败。

3、示例
假设我们有一个分布式数据库系统，包含两个数据库实例A和B，以及一个协调者C。

a、CanCommit阶段
协调者C收到事务请求。
协调者C向所有参与者发送一个“CanCommit”请求。
A判断可以支持事务，返回“就绪”（Ready）。
B判断可以支持事务，返回“就绪”（Ready）。

b、PreCommit阶段
参与者A和B都向协调者C反馈“就绪”，协调者C判断可以进行下一阶段。
C向A和B发送“PreCommit”请求。
A和B收到消息后，锁定资源，让事务处于可以提交、可以回滚的状态，并返回确认消息给协调者。

c、DoCommit阶段
协调者C收到所有参与者的确认消息。
C向参与者A和B发送“DoCommit”请求。
参与者A，提交事务，向C返回提交成功。
参与者B，提交事务，向C返回提交成功。
C收到所有参与者的提交成功消息后，事务完成。

三、事务补偿TCC（Try Confirm Cancel）
1、概述
在高并发场景下，2PC和3PC的效率根本无法满足要求，于是大家就考虑如何在应用层进行优化，而不要把压力都给到数据库呢，于是TCC应运而生。
TCC可以跨数据库类型、跨系统类型操作，而且灵活性强，效率高。
但TCC需要大量业务代码的改造，各服务需要实现Try、Confirm和Cancel接口，而且要求接口必须支持幂等操作，是一种入侵性比较强的一致性实现方式。

2、流程
TCC通常会将一个大的事务，拆分为多个子事务，并将事务的提交拆分为三个阶段：Try、Confirm 和 Cancel。
这里要注意，对于非严格一致的场景，可以通过MQ等方法异步解决问题，不要加入TCC。TCC应该只涉及到强一致性的各个服务。

a、Try阶段
在Try阶段，系统会进行业务检查，并预留资源。
比如：检查用户余额、检查库存，并暂时冻结资源。

b、Confirm阶段
确认所有业务服务的操作。
比如：扣余额，扣库存。

c、Cancel阶段
如果在Try或Confirm阶段有任何问题导致事务需要回滚，系统会执行Cancel阶段，释放之前预留的所有资源。
比如：释放余额、释放库存等。

3、示例
有一个电商平台，用户想要购买一个商品，这笔交易涉及到以下几个子业务：
用户账户扣款：需要确保账户余额足够，并能正确扣款。
库存服务扣减库存：确保商品库存足够，并能正确扣库存。
订单服务创建订单：记录交易的详细信息，并能设置为正确的状态。

a、Try阶段
客户下单，事务协调器（Transaction Coordinator）指示每个服务进行Try操作：
账户服务尝试扣款，但只是冻结资金，不会实际扣除。
库存服务标记商品库存为预留状态，不会实际减少库存。
订单服务准备创建订单，但不会实际创建。

b、Confirm阶段
如果事务协调器（Transaction Coordinator）收到所有Try操作都成功的消息，确认它们的操作：
账户服务将冻结的资金实际扣减。
库存服务将预留的库存实际扣减。
订单服务实际创建订单，并标记为已完成支付。
事务协调器（Transaction Coordinator）收到全部操作成功消息，此时可判断事务成功。

c、Cancel阶段
如果Try或Confirm的任意操作失败，事务协调器将指示每个服务撤销它们的操作：
账户服务将冻结的资金解冻。
库存服务将预留的库存重新释放。
订单服务放弃创建订单。
事务协调器（Transaction Coordinator）同时会判断，事务失败，并监督完成全部业务补偿操作。

一、概述
上一节说了OM算法，但OM算法效率太低了，在实际工程上几乎无法使用。
1999年，Miguel Castro和Barbara Liskov提出了PBFT（Practical Byzantine Fault Tolerance）算法，大幅提高拜占庭容错算法的效率和实用性。
PBFT算法更好的平衡了效率和容错能力，在n个节点的网络中，同样可以允许的故障的节点数可以达到f =（n-1）/3个。

二、PBFT算法的工作原理
PBFT算法主要包括三个阶段：预准备（Pre-Prepare）、准备（Prepare）和提交（Commit）。
PBFT算法的复杂度为O(n^2)，虽然消息数量还是很多，所以不适合大规模的网络，但比OM算法已经有大幅提升。

1、发起请求
客户端向主节点发起请求。

2、预准备阶段（Pre-Prepare）
主节点（Primary Node）收到消息后，为其分配一个视图消息编号vid，并广播预准备消息给所有副本节点。
广播消息格式为（Pre-Prepare，视图编号v，视图消息编号vid，请求内容msg，请求内容摘要msg-hash，时间有效区间T，主节点签名sign）

3、准备阶段（Prepare）
副本节点接收到Pre-Prepare预准备消息后，进行验证：
a、消息签名不正确，不通过
b、通过v和vid判断是否有相同编号消息，但不同内容的消息，不通过
c、超出时间有效期间T，不通过
d、msg与msg-hash不一致，不通过
e、通过
消息验证通过后，副本节点进入准备阶段，并进行消息广播
广播消息格式为（Prepare，视图编号v，视图消息编号vid，请求内容msg，请求内容摘要msg-hash，时间有效区间T，副本消息签名sign）

4、提交阶段（Commit）
每个节点在收到Prepare准备消息后，进行验证：
a、消息签名不正确，不通过
b、通过v和vid判断是否有相同编号消息，但不同内容的消息，不通过
c、超出时间有效期间T，不通过
d、msg与msg-hash与之前Pre-Prepare不一致，不通过
e、通过
每个节点在接收到足够数量的提交消息（通常是2f+1个）后，进入Commit阶段，并进行消息广播
广播消息格式为（Commit，视图编号v，视图消息编号vid，请求内容msg，请求内容摘要msg-hash，时间有效区间T，节点消息签名sign）

5、回复阶段
每个节点在收到Commit提交消息后，进行验证：
a、消息签名不正确，不通过
b、通过v和vid判断是否有相同编号消息，但不同内容的消息，不通过
c、超出时间有效期间T，不通过
d、msg与msg-hash与之前Prepare不一致，不通过
e、通过
节点收到（2f+1）条相同结果的Commit消息后，确认请求已成功执行，返回给客户端。

客户端收到（f+1）条相同结果的消息后，得到最终结果。
这里设置为f+1，因为节点最多收到f条一样的错误消息，不可能收到f+1条错误的消息。

三、主节点选举
如果主节点出现了异常，或则主节点故意作恶，PBFT是无法达成一致的。
此时，就要通过视图变更（View Change，类似于主节点任期的概念），选择新的主节点。

1、故障检测
当遇到以下情况时，备份节点会触发视图变更：
主节点，在约定时间内不响应客户端及备份节点请求
备份节点发送了准备消息后，在约定的时间内未接收到来自其他节点的2f个相同的准备消息。
备份节点发送了提交消息后，在约定的时间内未接收到来自其他节点的2f个相同的提交消息。
备份节点接收到异常消息，比如视图值、序号和已接受的消息相同，但内容摘要不同。

2、发起变更消息
触发视图变更的节点会向其他节点广播视图变更消息（View-Change消息）
这个消息包含了当前视图号v+1、序列号n（最后一个稳定的检查点的序列号）、以及已经准备好的消息集合P。

3、收集变更消息
其他节点在收到视图变更消息后，会检查消息的有效性。
如果消息有效，节点会记录该消息到本地日志中，并启动一个定时器，等待接收2f+1个视图变更消息来确认视图变更的成功。

4、选举主节点
当一个节点接收到2f+1个视图变更消息后，它会确认视图变更成功，并通过预定规则开始选举新的主节点：
(v + 1) mod |R|，其中v为当前视图的值，|R|为节点数选出下一个视图的主节点
节点启用新的视图号v+1，并将选举结果，广播通知其他节点。

5、广播NEW-VIEW消息
新的主节点接收到2f个其他节点的视图变更消息后，会广播一个NEW-VIEW消息，这个消息包含了上一个视图中所有未确认的请求信息。

6、处理未确认的请求
在新的视图中，副本节点需要处理在旧视图中未能达成一致的那些请求。
一旦新主节点广播了新视图消息，副本节点将执行这些请求，并进入提交阶段。

7、变更完毕，恢复正常

一、概述
前面讲的几种一致性算法，比较适合封闭式网络，各节点都是可信的，也就是没有节点故意作恶。
但对于开放式网络，可以允许任意节点加入的时候，我们无法判定这些节点是否有恶意，也就是无法判定这些节点是否可信。
此时，我们就需要一种新的思路了：
当存在少数节点作恶（ 消息可能被伪造） 场景下，其余节点如何达成一致性呢？
对于此种场景，最出名的就是拜占庭算法，而为了更快的理解拜占庭算法，我们要先解释一下拜占庭问题。

二、拜占庭将军问题（The Byzantine Generals Problem）
拜占庭问题又叫拜占庭将军问题，是Leslie Lamport在1982年提出用来解释一致性问题的一个虚构模型。
拜占庭是古代东罗马帝国的首都，由于地域宽广，守卫边境的多个将军（系统节点） 需要通过信使来传递消息，达成某些一致的决定。
但由于将军中可能存在叛徒（恶意节点），这些叛徒将努力向不同的将军发送不同的消息，试图会干扰一致性的达成。
拜占庭问题即为在此情况下，如何让忠诚的将军们能达成行动的一致。
（其实，还有一个隐含的限定，就是节点无法伪装为其他节点，实际中可以通过签名算法来达到这个目的）。

这样说可能有些抽象，我们举个例子：
比如一共有3个将军G1~G3，3个将军约定，少数服从多数。
G1、G2为忠诚的将军，G3是个叛徒
此时，G3有多种破坏方案，让G1和G2无法取得共识：

1、破坏方案A、否认提案内容，消息重放
比如：G1发起提案，G1要求明天进攻A城市，要把消息发给G2~G3

但G3先收到了消息，然后通过小道（比如更快的路由）向G2发送了“撤退”的提案
G2先收到了撤退的消息，后收到进攻的消息
G3向G1反馈进攻

结果：（G1被欺骗，G2被劫持）
由于只有G1发起了进攻，兵力不足，吃了败仗。
G3一口咬定，收到了G1要撤退的消息。

2、破坏方案B、故意发起错误提案
比如：G3发起提案，要把消息发给G1~G2。
但G3给G1的提案是进攻，给G2的提案时撤退

结果：（G1和G2不一致，但G1和G2认为彼此一致）
由于只有G1发起了进攻，兵力不足，吃了败仗。
G3一口咬定，发送了撤退的消息。

3、破坏方案C、故意传播相反的消息，操纵投票结果
比如：G1发起提案，G1要求明天进攻A城市，要把消息发给G2~G3。

此时：
G1希望进攻
G2希望撤退（比如节点有问题，无法接收事务提交）
G3是个叛徒，他给G1答复“进攻”，给G2答复“撤退”

结果：（G1和G2不一致，但G1和G2认为彼此一致）
G1收到了2票进攻，1票撤退，于是进攻
G2收到了1票进攻，2票撤退，于是撤退
G3是个叛徒，撤退
由于只有G1发起了进攻，兵力不足，吃了败仗。

三、Byzantine Fault Tolerant (BFT) 算法
对于上述问题，作者提出了一种BFT算法（OM算法），并证明了：
当叛变者为m，将军总人数不小于3m+1时，存在有效的算法，不论叛变者如何折腾，忠诚的将军们总能达成一致的结果。
或者，当将军总人数为n，当叛变者不大于(n-1)/3时（向下取整），存在有效的算法，不论叛变者如何折腾，忠诚的将军们总能达成一致的结果。

当恶意节点为m，节点总数必须不小于3m+1，可以这样证明：
在极端情况下：
a、m个正常节点下线。
b、m个恶意节点给出同一的恶意结论F。
c、此时必须至少有m+1个正常节点，给出正确结论T，才能保证系统得到结论T
因此节点总数，必须不小于3m+1

可见，能确保达成一致的拜占庭系统节点数至少为 4，允许出现1个坏的节点。如果叛变者过多，则无法保证能达到一致性。

四、OM算法过程
OM算法（Oral Message Algorithm）的核心思想是通过递归的方式，将命令从指挥官传递给下属，确保所有忠诚的下属最终都能接收到相同的命令。
OM算法复杂度为O(n^(m+1))，就是当有m个叛变者时，进行m+1轮递归通讯。
算法复杂度太大，在实际工程中无法应用。

1、初始化：
指挥官（通常是忠诚的将军）发送其命令给所有其他将军。
如果某个将军没有收到命令，则默认执行撤退命令。

2、递归传递：
每个将军在接收到命令后，会将该命令传递给其他未收到命令的将军。
如果某个将军接收到多个不同的命令，它会选择一个多数命令作为最终命令。

3、递归终止：
当所有将军都接收到相同的命令时，递归终止。
最终，所有忠诚的将军都会执行相同的命令。

具体步骤如下：
1、OM(0)：（递归终止条件）
指挥官发送其命令给所有其他将军。
每个将军使用接收到的命令来做出决策。如果没有接收到命令，则使用默认命令（撤退）。

2、OM(x)：（递归步骤：x=m、m-1、…、2、1）：
指挥官发送其命令给所有其他n位将军。
对于每个将军i，如果它接收到命令，则将军i作为新的指挥官，执行OM(x-1)，并将其收到的多数命令，传递给其他n-2位将军。

3、重复上述过程，所有忠诚的将军都会执行相同的命令。

Gossip是一个最终一致性协议，适用于大规模的、弱一致性的、去中心化的场景。

为了达到最终一致性，Gossip实际上提供了三种同步方式：Direct Mail（直接邮寄）、Rumor Mongering（谣言传播）及 Anti-Entropy（反熵）。看起来都是新技术名词，但分开来看，却都十分简单。

1、Direct Mail（直接邮寄，增量）
通俗解释就是，当一个节点收到客户端的新信息后，就把这个新信息传递给系统内的每个节点。
Direct Mail功能实现简单、效率也很高。

但在一个开放性的大规模非中心化网络中，经常会出现节点的变化（增加、掉线、宕机），这种场景下，仅靠Direct Mail，是不可能实现最终一致性的。
比如，节点X宕机了1一小时，然后启动。这一小时中的数据就丢失了。虽然在技术上，我们可以将信息做一些缓存，但在一个开放网络里，管理每个节点是否接收并处理好自己发送的全部消息，这本身就是个技术难题，而且效率将会及其低下。

2、Anti-Entropy（反熵，全量）
通俗解释就是，一个节点，定期会选择一些节点，对比数据的差异，并相互修复缺失的数据。
同步方式，可以是推送、拉取、连推带拉。
Anti-Entropy会比较整个数据库的异同，是达成最终一致性的最后手段。

Anti-Entropy消息以固定的概率传播全量的数据。
所有节点只有两种状态：Suspective(病原)、Infective(感染)，也被称作simple epidemics(SI model)。
S节点会把所有的数据都跟I节点共享，以便消除节点之间数据的任何不一致，它可以保证最终、完全的一致。

但是，在一个开放性的大规模非中心化网络中，定期同步全量数据，将会带来巨大的资源消耗。
所以这个操作的频率，必须足够低，否则整个网络就不用做其他事情了。
注：在实际工程落地中，为了加快数据同步效率，并不一定会“随机”选择同步节点，而是会想办法，用一定的顺序，尽快让全部节点完成同步。

聪明的你一定会发现，通过Direct Mail和Anti-Entropy，已经可以实现最终一致性的效果了。
但Direct Mail无法保证成功，Anti-Entropy无法保证频率，我们需要寻找额外的同步方案，在消耗尽量少资源的前提下，让整个网络的的可用性大幅提升。

3、Rumor Mongering（谣言传播，增量）
通俗解释就是，当一个节点收到新消息后，随机挑选N个节点，把新消息推送给这些节点。这N的节点在收到消息后，又会分别随机选择N个节点，推送新消息。
同步方式，同样可以是推送、拉取、连推带拉。

Rumor Mongering消息以固定的概率传播增量数据。
所有节点有三种状态：Suspective(病原)、Infective(感染)、Removed(愈除)。也被称作complex epidemics(SIR model)。
S节点只会把追加消息发送给随机选择的I节点。而这个消息在某个时间点之后会被标记为Removed，并且不再被传播。
根据六度分隔理论，经过几轮随机推送，可以基本确保每个节点都收到了新消息。但部分特殊节点仍有可能并未收到所有的追加消息。
所以，通过Direct Mail和Rumor Mongering并无法保证达到最终一致性。

聪明的你一定会发现，这一个信息，会被多次重复推送，一个节点也会重复接收。这其实是一个实现复杂度和性能之间的一个均衡。
和协议的名字相似，风言风语，口口相传，很快全村就都知道了。

4、新节点加入怎么处理
当一个节点加入网络后，会先使用Anti-Entropy的拉取方式，获取一个相对比较新的数据库。
然后就可以通过Direct Mail、Rumor Mongering获取新数据啦。
最后，还有Anti-Entropy，定期全量对比更新数据，这样新节点加入后，网络很快就能达到一致性了。

可见，Gossip协议，原理很简单，实现也并不复杂。虽然有一定程度的通讯浪费，但对于开放性的大规模非中心化网络中，Gossip协议很好的平衡了可用性、性能、工程复杂度之间的关系，实际中也获得了不少项目的青睐。

分布式一致性算法05 NWR协议

一、基本概念
NWR模型是一种强一致性算法，它巧妙的利用了N（备份数）、W（写入成功数）、R（读取成功数）之间的关系（W+R>N），从而达到一致性的要求。

其中：
N（备份数）：系统中备份的总数。
W（写入成功数）：执行写操作时，需要写入成功的最小备份数量。
R（读取成功数）：执行读操作时，需要查询成功的最小备份数量。

为了保证一致性，必须满足以下条件：
W+R>N
这个不等式确保了在执行读操作时，至少有一个最新的备份被读取到，从而避免了读到过时的数据。

二、相关角色
NWR协议中，所有的节点是一样的。

三、算法流程
1、客户端请求写入
各节点收到消息，写入成功后，返回写入成功
当客户端收到W以上个写入成功后，认为写入成功
2、客户端读取请求
个节点收到读取消息，返回结果
当客户端收到R个以上的结果后，直接使用最新版本的数据即可。

由于W+R>N，所以客户端至少可以读取到一份最新的数据，不会读取到历史版本。

四、举例说明
假设我们有一个分布式系统，其中有5个节点，即N=5。
要求确保写操作在至少3个节点上成功（W=3），并且读操作至少查询3个节点（R=3）。

1、写操作
客户端向系统发送一个写请求，比如更新某个键值对。

2、写操作的传播
写请求被发送到所有5个备份节点，等待至少3个节点确认写操作成功。

3、写操作的确认
假设有3个节点成功更新了数据，满足了W=3的要求，写操作被认为是成功的。

4、读操作
客户端发送一个读请求，希望获取最新的键值对数据。

5、读操作的数据收集
系统从5个备份节点中的任意3个节点获取数据，由于W+R>N（3+3>5），至少有一个节点上的数据是最新的。

6、结果的确认
客户端收到来自3个节点的响应，可能会发现不同节点的数据版本不同。
客户端选择版本号最高的数据使用即可。

五、NWR的优点
1、实现简单
2、在NWR体系下，无需等待所有节点都写入成功，即可判定数据更新成功，而且保证可以读取到最新数据，提升了系统的吞吐量，同时系统的可用性也有较大提升。
3、即使部分节点宕机，只要能保证W+R>N，系统还是处于可运行状态，比如
N=5，W=3，R=3
即使宕掉2个节点，仍然可以保证运行，只不过系统退化为了强C系统。

六、NWR突破了CAP的限制吗？
并没有哦，其实我们挑战一下NWR的设置就可以看懂了（先不考虑P，我们讨论一下CA）
当W=N、R=1的时候，其实就是写入时，牺牲了A，保证了C（节点都一致）
当W=1、R=N，其实就是写入时，保证了A，牺牲了C（节点都不一致）

分布式一致性算法04 ZAB协议

一、基本概念
ZAB（Zookeeper Atomic Broadcast）协议是为Apache Zookeeper框架设计的一致性协议。
与Paxos仅能保证事务的一致性不同，ZAB可以同时保证事务的顺序性和一致性。

二、ZAB算法涉及三种角色和四种状态
三种角色：
1、领导者（Leader）： 在同一时间，集群只会有一个领导者。所有的写请求都必须在领导者节点执行。
2、跟随者（Follower）：集群可以有多个跟随者，它们会响应领导者的心跳，并参与领导者选举和提案提交的投票。跟随者可以直接处理来自客户端的读请求，但会将写请求转发给领导者处理。
3、观察者（Observer）：与跟随者类似，但不参与竞选和投票权。

节点有四种状态：
LOOKING：选举状态，该状态下的节点认为当前集群中没有领导者，会发起领导者选举。
LEADING ：领导者状态，意味着当前节点是领导者。
FOLLOWING ：跟随者状态，意味着当前节点是跟随者。
OBSERVING： 观察者状态，意味着当前节点是观察者。

三、关键概念
1、Epoch（纪元）
定义：Epoch是ZXID的高32位，表示领导者的任期编号。每次新的领导者被选举出来时，Epoch都会增加。
作用：
标识领导者的任期。不同的Epoch代表不同的领导者任期，确保了领导者的唯一性。
当发生分区或领导者故障时，新的领导者会具有更高的Epoch，从而确保了新的领导者具有最新的状态。

2、ZXID（事务ID）
定义：ZXID是一个64位的数字，用于唯一标识Zookeeper中的每个事务。
组成：ZXID的高32位表示Epoch，低32位表示事务计数器（XID）。
作用：
确保事务的全局顺序性。每个事务都有一个唯一的ZXID，保证了事务在所有服务器上的处理顺序一致。
通过比较ZXID，服务器可以确定事务的先后顺序，以及是否已经处理过某个事务。

四、ZAB选举流程
1、初始化：
集群中的每个服务器（Server）启动时，都处于“Looking”状态，即寻找Leader状态。

2、投票：
每个处于“Looking”状态的服务器都会发送投票（Vote）给其他服务器，尝试将自己选举为Leader。
投票格式大概为：
（新Leader节点的ID, 新Epoch编号, 当前最新的ZXID，投票节点的ID）

3、收集选票：
收到各节点的选票后，各节点会根据以下规则，判定如何投票：
优先检查任期编号Epoch，任期编号大的节点作为领导者；
如果任期编号Epoch相同，比较事务标识符ZXID的最大值，值大的节点作为领导者；
如果事务标识符的最大值相同，比较节点ID，节点ID大的节点作为领导者；
通过这样的规则，首先保证了数据最新的节点，获取更高的票数。

4、确定Leader
如果没有任何节点获取了过半选票，则要开始下一轮选举，回到步骤2，但此时不再会投票给自己，而是会投票给上一轮最合适的节点。
如果某个服务器获得了超过半数的投票，它就认为自己被选举为新的Leader。

5、同步：
新Leader会与集群中的Follower进行数据同步，确保所有Follower的数据与Leader一致。
数据同步完成，Leader就可以接收客户端的事务请求了。

五、ZAB选举示例
假设我们有一个Zookeeper集群，包含5个节点（P1~P5），所有节点都处于“Looking”状态。
Epoch=2；XID=5；ZXID=（2，5）
投票信息格式为：
（新Leader的ID, 新Leader的Epoch编号, 新Leader的最新的ZXID，选举轮次，投票节点的ID）

1、初始化
P1~P5开始寻找Leader，并发送投票请求，并投票给自己。

2、投票
P1：（新Leader=P1, 新Leader的Epoch=2, 新Leader的最新的ZXID=（2，5），选举轮次=1，投票节点=P1）
P2：（新Leader=P2, 新Leader的Epoch=2, 新Leader的最新的ZXID=（2，5），选举轮次=1，投票节点=P2）
P3：（新Leader=P3, 新Leader的Epoch=2, 新Leader的最新的ZXID=（2，3），选举轮次=1，投票节点=P3）
P4：（新Leader=P4, 新Leader的Epoch=2, 新Leader的最新的ZXID=（2，2），选举轮次=1，投票节点=P4）
P5：（新Leader=P5, 新Leader的Epoch=1, 新Leader的最新的ZXID=（1，1），选举轮次=1，投票节点=P5）

3、收集选票
对于同一轮的选票，节点自行对比判定选举结果：
P1：新Leader=P2，因为P2节点ID更大
P2：新Leader=P2，不变
P3：新Leader=P2，因为P2 ZXID更大
P4：新Leader=P2，因为P2 ZXID更大
P5：新Leader=P2，因为P2 Epoch更大
但如果一个节点收到了更小选举轮次（logicalclock）的投票，该投票会被忽略。

4、再次投票，这样P2会获得全部5票

5、确定Leader
P2认为被选举为Leader。其余节点，会主动与P2交换最大的ZXID，如果P2的更新则承认P2的领导地位，否则重新发起选举。
当过半节点承认P2的领导地位时，P2正式成为Leader。
同时P2会将Epoch+1，此时：
Epoch=3；ZXID=（3，0）

6、同步
P2根据之前各节点反馈的最大ZXID，开始与其他节点进行数据同步，强制要求所有Follower的数据与自己的数据一致。
数据同步完成后，P2告知全部Follower数据同步完毕，P2开始接收提案，各节点开始同步P2的提案。

六、ZAB同步算法的工作流程
延续上面的例子，Zookeeper集群，包含5个节点（P1~P5），P2是Leader
Epoch=3；XID=0；ZXID=（3，0）

1、客户端请求：
客户端向P3发送写请求，P3会将写请求转交给Leader P2。

2、事务提案：
Leader接收到请求后，会生成一个事务提案Proposal，分配一个全局唯一的ZXID，并进行持久化。

3、广播提案：
Leader将事务提案发送给所有Follower。

4、Follower投票：
Follower接收到提案后，会将Proposal写入本地日志，并根据自身的数据状态进行投票（必须按ZXID顺序提交），并将投票结果发送回Leader。

5、Leader决策
当Leader收到超过半数Follower的同意投票后，提交事务。同时将通知所有Follower更新状态。
如果提案被拒绝，事务将被回滚。

6、客户端响应
P3收到Leader事务提交的消息，P3会向客户端返回操作结果，客户端根据结果进行相应的处理。

七、ZAB协议的关键点：
1、顺序一致性：ZAB协议通过全局唯一的ZXID，保证了客户端请求的顺序性。
2、可靠性：即使在部分节点宕机的情况下（投票数可以过半），ZAB协议也能够保证系统的可靠性和数据的一致性。
3、防止分区：当新Leader选举成功后，如果旧Leader恢复过来，由于新Leader有更高的Epoch，旧Leader的请求不再会被接受；一个节点，如果与Leader失联，则是无法处理读写请求的；

可以看出，ZAB算法与RAFT算法整体的考虑方向是一致的，就是先选择一个Leader，通过Leader控制事务提交的顺序。
但就具体的实现而言，RAFT的实现更简单可以实现强一致性，ZAB的实现更复杂一些可以实现最终一致性。

分布式一致性算法03 RAFT协议

一、基本概念
Raft算法首选会选举一位领导者（Leader），所有的写请求都先提交给Leader，Leader通过日志复制（Log Replication）来保持集群中所有节点的状态一致。

在这个过程中有一些限制：
1、Leader只能有一个，Leader会通过心跳包告知其他节点，“我是Leader，我还活着，你们别想选举”
2、Leader和Follower之间通过日志同步的方式达成一致；在一条日志中，包含了索引编号、指令、Leader任期等信息
3、日志记录了所有的事务操作，必须在所有节点上顺序一致（索引编号是递增的）
4、Raft算法通过任期编号和选举超时机制来避免分裂脑现象，确保在任期内只有一个Leader

二、RAFT算法通常涉及三种角色
领导者（Leader）：负责处理所有客户端请求，将日志条目（Log Entries）复制到其他节点。
跟随者（Follower）：接收领导者的日志条目并保持与领导者的心跳连接。
候选者（Candidate）：当跟随者在一定时间内没有收到领导者的心跳时，它们会变成候选者并尝试成为新的领导者。
在实际情况中，一个节点通常只会承担一个角色，但这个角色通过选举机制是可以相互转换的。

三、RAFT Leader初始过程
1、当系统初始化时，或者Leader状态异常无法正常发送心跳包后，会开启选举过程。
2、此时，每个节点都是Follower，每个Follower都持有一个时间随机的选举计时器。
3、当一个Follower的选举计时器超时后，该Follower会判定Leader不可用，于是它自增任期号，并转换为Candidate。
4、Candidate首选会给自己投票，并向其他节点发送 RequestVote RPCs 请求投票，该请求中包含新任期号以及日志信息。
5、其余节点收到请求后，会检查请求中的任期号和自己的日志信息。如果受到的任期号更大，它们会投票给该Candidate。
6、如果一个Candidate从集群中大多数节点那里收到投票，它就赢得了选举，成为新的Leader。
7、新的Leader会立即向所有节点发送心跳信息，以通知它们自己的存在，并防止它们变成Candidate。

四、选举过程举例
假设一个5节点组成的Raft集群P1~P5，其中P1是Leader，其余为Follower，此时任期为Term1。此时P1故障，无法发送心跳包。

1、P2~P4节点都为Follower状态，每个节点都会初始化一个随机的选举计时器。
计时器分别为：P2 100ms，P3 200ms，P4 300ms，P5 400ms

2、由于一直收不到心跳包，P2的选举计时器会首先超时。
此时P2会在任期号Term1上增加，生成任期号Term2，并转换为 Candidate 状态。

3、P2给自己投票，并向其他全部节点发送 RequestVote RPCs 请求投票，并带上任期号Term2

4、P3~P5收到投票后，对比Term2和自己日志中的任期号
如果日志任期号更达，则拒绝投票
在本例中，Term2任期号更大，P3~P5就都会投票给P2

5、P2收到P3~P5的投票，加上自己的一票，超过半数，选举成功，P2成为新的Leader

6、P2会立即向所有节点发送心跳信息，其他竞选失败的Candidate，退回为Follower状态，开始跟随Leader的日志。
所有Follower会重置选举计时器，等待再次成为Candidate，并发起选举。

7、在日志复制之前，P2需要确定自己的日志与Follower的日志是否一致。它会发送AppendEntries RPC请求给Follower，并在请求中包含自己日志的最后一个日志Entry（索引和命令）和任期（PrevLogEntry和PrevLogTerm）。
如果Follower的日志与Leader匹配，则可以开始日志同步。
如果Follower的日志与Leader不匹配，它会发送一个失败的响应。Leader则会回退一个日志Entry，再次与Follower确认，直至双方一致为止。此时，Leader会将最新日志同步给Follower，从而让双方日志完全一致。

8、P2此时正式成为Leader，开始接收请求，并开始同步日志（AppendEntries RPC）

投票过程有一些限制：
单次投票：当Follower收到不同Candidate的同一Term的 RequestVote RPCs时，只会投票给第一个
仅投票给日志完整性高的Candidate：当Follower收到Candidate的RequestVote RPCs时，如果Candidate的日志完整性不如自己高，则拒绝投票
过半投票：Candidate必须有过半的投票，才能升级为Leader，从而避免脑裂

当然，也会有一些特殊情况：
系统启动：节点启动后默认为Follower，由于没有Leader，各节点很快会进入选举超时，并转换为Candidate，并发起选举。
选举失败：没有任何Candidate获得足够的票数，这样会继续进入下一轮选举，而且这个等待选票的时间，也是随机的

四、Raft算法的工作流程
当完成Leader的选举后，工作流程就比较简单了。

接收请求：
客户端向Leader发送一个写请求，比如设置键值对key1=value1。

日志复制：
Leader创建一个新的日志条目，并将其追加到自己的日志末尾。

日志同步：
Leader将这个日志条目发送给跟所有的Follower，包含了日志条目的信息以及领导者的任期号等。
Follower收到日志后，首先验证任期是否有效，如果任期有效，而且日志条目与本地日志记录兼容，则存储这个日志条目到自己的日志末尾。
跟随者在成功存储日志条目后，会向领导者发送一个确认响应（包含当前的任期号和成功标识）。

日志提交：
Leader等待Follower的确认消息，一旦收到大多数Follower的确认，它就将日志记录为“已提交”状态。
此时，Leader会向客户端返回操作成功。

应用日志：
Leader会在心跳包以及新日志复制的消息中，带上当前最新日志索引编号。
Follower接收到指令后，会将编号小于等于最新日志索引编号的日志条目，应用到自己的状态机中。
由于所有节点都按照相同的日志条目顺序执行操作，因此所有节点的状态机最终将保持一致。

五、效率提升
仅Leader接收请求：
避免集群多次通讯达成一致的过程，Leader接收并处理全部请求，然后同步给Follower。大幅提高吞吐能力。

日志压缩：
为了减少存储空间的使用，会定期进行日志压缩，保留关键的日志信息，而丢弃已经被持久化和应用的日志条目。

随机选举计时器：
通过随机时间，避免了所有节点一起发起投票，只投给自己的情况。用相对较低

单节点变更：
当增减节点的时候，保证一次只增减1个节点，可以有效的避免脑裂的出现

分布式一致性算法02 Multi-Paxos算法

一、基本概念
Multi-Paxos算法，在Paxos的基础上，通过引入领导者（Leader）的概念，大幅提升了效率。

二、Multi-Paxos算法通常涉及三种角色：
Leader（领导者）/Proposer（提议者） ：在Multi-Paxos中，通常会选举出一个Leader作为Proposer，负责提出提议，并尝试让多数接受者接受该提议。
Acceptor（接受者） ：负责接受或拒绝提议者的提议。每个节点都可以是Acceptor，负责记录和确认提议。
Learner（学习者） ：负责学习最终达成一致的提议。

三、Multi-Paxos算法的基本过程
1、初始化阶段
首先，通过Paxos算法，选择一个领导者（Leader），它负责发起全部提议。

2、准备阶段（Prepare Phase）
领导者向集群中的其他节点发送Prepare消息，这些消息包含当前的最大提议编号。
Acceptor（接受者）接收到Prepare消息后，会返回一个响应，表明它们是否已经接收到更高编号的提议。
如果领导者接收到大多数节点的响应，表示它们没有更高的提议，则可以继续下一步。

3、接受阶段（Accept Phase）
领导者根据收到的Prepare响应选择一个提议编号，并向集群中的其他节点发送Accept消息。这些消息包含提议编号和提议值。
节点接收到Accept消息后，如果该提议编号高于它们当前已接受的提议，则会接受该提议并返回确认消息。如果大多数节点确认接受该提议，则该提议被接受。

4、提交阶段（Commit Phase）
一旦提议被大多数节点接受，领导者将该提议标记为已提交，并通知集群中的其他节点。
节点接收到提交通知后，将执行该提议，并更新其状态。

5、应用阶段（Apply Phase）
最后，领导者将已提交的提议应用到状态机中，并通知集群中的其他节点。
节点接收到应用通知后，也会将提议应用到其状态机中，从而确保所有节点的状态一致。

四、举例说明
假设我们有一个分布式系统，由10个节点组成：P1、P2是提议者（Proposer），A1、A2、A3、A4、A5是接受者（Acceptor），L1、L2、L3是学习者（Learner）。

1、初始化阶段
在Multi-Paxos中，任何提议者都可以被选为领导者。
系统启动时，通过某种机制（比如Paxos算法）选举出一个新的领导者，这里假设P1被选为领导者。

2、准备阶段（Prepare Phase）
领导者P1，生成一个提议编号（例如7），向所有接受者询问，是否可以接受编号为7的提议。
接受者A1~A5收到消息后，由于提议编号7大于它们之前见过的任何提议编号，将进入承诺状态，并向P1发送可接受提议编号7的提议，并承诺不会接受任何编号小于7的提议。
【通过算法优化，其实可以节省提议编号这个阶段，直接发起提议】

3、接受阶段（Accept Phase）
当受到大多数接受者同意提议编号的消息后，P1向集群中的所有接受者发送Accept消息，提议编号7的内容为V7。
接收者收提议后，如果该提议编号高于它们当前已接受的提议，则会接受该提议并返回确认消息。

4、提交阶段（Commit Phase）
一旦P1收到来自多数接受者的已接受消息，它将向所有接受者发送提交消息，指示它们可以提交这个提议。

5、应用阶段（Apply Phase）
接受者在收到提交消息后，将提议的键值对应用到状态机中，并将结果通知学习者。

五、与Paxos算法对比
并发性：Paxos算法在每次达成共识时都需要进行两轮消息传递，这限制了它的并发能力。而Multi-Paxos通过引入领导者（Leader）的概念，允许多个提议者并发地提出提议，从而提高了并发性。
消息复杂度：在Paxos算法中，每个提议都需要两轮的通信（Prepare和Accept阶段），这增加了消息的复杂度。Multi-Paxos通过减少通信轮次，允许领导者在一轮中提出多个提议，从而减少了消息的复杂度。
实时性：由于Multi-Paxos允许并发提议，它在实时性方面通常优于Paxos算法。在Paxos算法中，每个提议都需要等待前一个提议完成后才能开始，这可能导致延迟。
容错性：Paxos算法和Multi-Paxos都具有很好的容错性，但Multi-Paxos由于其并发性，在某些容错情况下可能表现更好，例如在领导者失败时可以快速选举新领导者并继续处理提议。
实现复杂度：Paxos算法的实现相对复杂，而Multi-Paxos虽然在理论上提供了并发性的优势，但其实现也引入了额外的复杂性，如领导者选举和故障恢复机制。
优化和变种：Multi-Paxos有许多优化和变种，如Fast Paxos和EPaxos，它们通过进一步减少通信轮次或利用特定的系统特性来提高性能。而在实际应用中，许多系统采用Multi-Paxos或其变种，如Raft算法，以提高性能。

分布式一致性算法01 Paxos算法

一、基本概念
Paxos是分布式一致性的经典算法，由Leslie Lamport在1990年提出。

二、Paxos算法通常涉及三种角色：
Proposer（提议者） ：负责提出提议（Proposal），即向系统中提出一个值。Proposer通常是客户端，负责发起提议并分配一个不重复的自增ID给每个提议。
Acceptor（接受者） ：参与决策过程，负责接收并回应Proposer的提议。每个Acceptor只能接受一个值，并且为了保证最多只有一个值被选定（Chosen），Proposal必须被超过一半的Acceptors所接受。
Learner（学习者） ：负责学习最终被选定的值。Learner不参与协商过程，只是接收并记录最终被选定的值。
在实际过程中，一个节点可以同时承担1~3个角色。

三、Paxos算法的基本过程
1、准备阶段（Prepare Phase）：
提议者（Proposer）选择一个提议编号（ballot number），并将其发送给所有接受者（Acceptor）。
接受者在接收到提议者的准备请求后，如果当前编号大于其已承诺的最高编号，则更新其承诺编号，并返回一个承诺（promise）给提议者，承诺中包含当前已接受的最高编号和值。

2、提议阶段（Proposal Phase）：
提议者收集到多数接受者的承诺后，选择一个值（value），并结合最新的提议编号，生成提议（propose）消息发送给接受者。
接受者在接收到提议消息后，如果提议编号大于其已有的承诺编号，则接受该提议，并返回确认消息给提议者。

3、决定阶段（Decide Phase）：
提议者收集到多数接受者的确认消息后，可以决定该值为最终值，并将其写入日志或状态机中。
学习者（Learner）从提议者处获取并学习最终决定的值，确保所有节点都有一致的状态。

四、举例说明：
假设我们有一个分布式系统，包含10个节点：P1、P2是提议者，A1、A2、A3、A4、A5是接受者，L1、L2、L3是学习者。

1、准备阶段：
P1提出一个提议编号，编号为1。
P1向所有接受者A1~A5发送询问，询问P1将发起编号为1提议是否可以。
A1收到提议时，并没有反馈过任何一次提议，于是反馈可以接受，并承诺，后续不会接受编号比1小的提议。A2~A4类似。

几乎同时，P2提出一个提议，编号为5。
P2向所有接受者A1~A5发送询问，询问P2将发起编号为5提议是否可以。
A1收到提议时，承诺的最小编号为1，于是反馈可以接受，并承诺，后续不会接受编号比5小的提议。A2~A4类似。

到这里，P1和P2的提议，前后都被允许提交了。当然，也有情况可能是，部分节点先收到了P2，这种情况下，P1的提议编号就无效了，需要重新拟定编号，这个编号必须单调增加。

2、提议阶段
P1收到了过半节点的提议编号反馈，向所有接受者A1~A5发送提议，告知提议编号为1的提议值为V1。
接受者收到提交消息时，已经无法接收比5小的提议，于是就拒绝P1，提议不通过。

P2收到了过半节点的提议编号反馈，向所有接受者A1~A5发送提议，告知提议编号为5的提议值为V5。
接受者收到提交消息时，反馈P2同意了5号提议。

3、决定阶段
当提议5收到过半同意反馈时（5个节点中3个以上同意），认为提议通过，各节点并将V5写入日志。
此时，学习者L1、L2、L3也会学习到V5的结果，并写入日志。

五、Paxos算法的特点
多数同意：在Paxos算法中，只有当提议者收到超过半数接受者的同意时，提议才可能被提交。
唯一性：Paxos算法保证了在任何给定的一轮中，只有一个提议可以被接受。
容错性：即使在一些节点失败的情况下，Paxos算法也能够工作。
Paxos算法的实现和理解都相当复杂，但它是许多现代分布式系统一致性协议的基础，如Raft算法等。