分布式共识算法

算法拜占庭容错一致性性能可用性
2PC强一致性
TCC最终一致性
Paxos强一致性
ZAB最终一致性
Raft强一致性
Gossip最终一致性
Quorum NWR强一致性
PBFTN/A
POWN/A

一份随时可能发生变化的数据如何在不同集群节点之间同步:

一旦系统中过半数的节点中完成了状态的转换,就认为数据的变化已经被正确地存储在系统当中,这样就可以容忍少数(通常是不超过半数)的节点失联,使得增加机器数量对系统整体的可用性变成是有益的,这种思想在分布式中被称为“Quorum机制“

半数机制,如果遇到网络分区,网络分区少数的那一方就肯定不会产生 Leader,也是为了避免脑裂的产生

在分布式系统中,解决共识的复杂度在于:

  1. 网络各个节点通讯不可靠 消息可能会延迟或者丢失
  2. 系统对外提供的访问是可以并发的

当以下3个问题被同时解决,即达成共识:

共识算法必须满足的性质:

分布式互斥算法

分布式系统中,排他性的资源访问方式,叫作分布式互斥(Distributed Mutual Exclusion),而被互斥访问的共享资源就叫作临界资源(Critical Resource)

分布式选举算法

Bully 算法

它的假设集群中每个节点均知道其他节点的 ID,选举过程:

  1. 集群中每个节点判断自己的 ID 是否为当前活着的节点中 ID 最大的,如果是,则直接向其他节点发送 Victory 消息,宣誓自己的主权
  2. 如果自己不是当前活着的节点中 ID 最大的,则向比自己 ID 大的所有节点发送 Election 消息,并等待其他节点的回复
  3. 若在给定的时间范围内,本节点没有收到其他节点回复的 Alive 消息,则认为自己成为主节点,并向其他节点发送 Victory 消息,宣誓自己成为主节点;若接收到来自比自己 ID 大的节点的 Alive 消息,则等待其他节点发送 Victory 消息
  4. 若本节点收到比自己 ID 小的节点发送的 Election 消息,则回复一个 Alive 消息,告知其他节点,我比你大,重新选举

拜占庭将军问题

口信模型

如果叛将人数为 m,将军人数不能少于 3m + 1,n 位将军,最多能容忍 (n - 1) / 3 位叛将

通过少数服从多数,并使用兜底预案来达成共识

签名机制

每个节点收到一条消息后,都在后面追加自己的签名,并把消息转发给所有其他不在还没签名的节点。最终,每一条消息,都会经过所有节点的签名,按约定的排序和选取算法,可靠节点会做出相同的选择

Paxos

节点类型

基本 Paxos 架构。许多提议者向接受者提出提议。当接受者接受一个值时,它会将结果发送给学习者节点

stateDiagram-v2  direction LR  Proposer1 --> Acceptors1  Proposer1 --> Acceptors2  Proposer1 --> Acceptors3  Proposer2 --> Acceptors1  Proposer2 --> Acceptors2  Proposer2 --> Acceptors3  Acceptors1 --> Learner  Acceptors2 --> Learner  Acceptors3 --> Learner
sequenceDiagram    participant 用户    participant 提案节点    participant 决策节点    participant 记录节点    用户->>提案节点: 操作请求    提案节点->>提案节点: 构造新的提案ID(n),广播Prepare(n)请求    提案节点->>提案节点: 首次设值,返回Promise(n, null)应答    alt 非首次设值        提案节点->>提案节点: 返回Promise(acceptedProposalID, acceptedValue)应答        提案节点->>提案节点: 将acceptedValue作为提案的value    end    提案节点->>决策节点: 广播Accept(id, value)请求    决策节点->>提案节点: 返回Accepted(id, value)应答    决策节点->>记录节点: 形成决议,供记录节点学习

Paxos描述了这样一个场景,有一个叫做Paxos的小岛(Island)上面住了一批居民,岛上面所有的事情由一些特殊的人决定,他们叫做议员(Senator)。议员的总数(Senator Count)是确定的,不能更改。岛上每次环境事务的变更都需要通过一个提议(Proposal),每个提议都有一个编号(PID),这个编号是一直增长的,不能倒退。每个提议都需要超过半数((Senator Count)/2 +1)的议员同意才能生效。每个议员只会同意大于当前编号的提议,包括已生效的和未生效的。如果议员收到小于等于当前编号的提议,他会拒绝,并告知对方:你的提议已经有人提过了。这里的当前编号是每个议员在自己记事本上面记录的编号,他不断更新这个编号。整个议会不能保证所有议员记事本上的编号总是相同的。现在议会有一个目标:保证所有的议员对于提议都能达成一致的看法

一些paxos原型描述:https://www.douban.com/note/208430424/

最原先的Paxos被称为 Basic Paxos,但这个算法如果两个提案节点互不相让地争相提出自己的提案,抢占同一个值的修改权限,就会产生活锁问题

准备阶段

提议者分别向所有接受者发送包含提案编号的准备请求

接受者接受到这准备请求后,如果该编号大于当前接收者已经响应过的准备请求的编号,那么其就会将接受过的编号最大的提案(如果有的话)作为响应返回给提议者,同时该接受者承诺不再接受任何编号小于该编号的提案

接受阶段

如果提议者收到半数以上接受者对其发出的准备请求的响应,那么提议者就会发送一个针对[编号,V]提案的Accept请求给半数以上的接收者,V就是收到的响应中编号最大的提案的value,如果响应中不包含任何提案,那么V就由提议者自己决定

当接受者通过了一个提案时,就通知给所有的学习者。当学习者发现大多数的接受者都通过了某个提案,那么它也通过该提案

Multi Paxos

Multi Paxos对Basic Paxos的核心改进是增加了“选主”的过程

一旦系统有了主节点,用户的操作请求都将直接在主提案节点上操作,通过减少非必须的协商步骤来提升性能:

sequenceDiagram  用户 ->> 主提案节点: 操作请求  主提案节点 ->> 决策节点: 广播Accept(id,i,value)请求  决策节点 -->> 主提案节点: 返回Accepted(id,i,value)应答  主提案节点 ->> 记录节点: 形成决议,供记录节点学习

这就跟zk的算法很像了

实现数据的复制同步只需达到节点总数的一半就可以提交 数据将会生效

许多说法都会提出为了防止产生网络分区,也就说节点之间网络不通,但是还能够向外提供服务,产生脑裂问题,所以通过设置节点数不能小于总数的一半,但实际上这种情况十分少见。 本质上,容忍一半以下节点更多地是为了允许一定量的节点下线,是为了可用性

Raft

分布式一致性协议,主要解决三个问题

让系统里始终有一个 Leader,所有的数据写入,都是发送到 Leader,Leader 需要把对应的数据写入复制到其他的服务器上,这就决定了 Raft 需要解决以下几个问题:

主节点竞选

有三种节点:Follower、Candidate 和 Leader。

stateDiagram-v2  direction LR  [*] --> Follower: 初始化  Follower --> Candidate: 一段时间没有Leader的消息  Candidate --> Candidate: 发起选举  Candidate --> Follower: 发现新的任期号、新的Leader  Candidate --> Leader: 收到半数以上票数  Leader --> Follower: 发现新的任期号

多个候选人同时发起选举,导致选票被瓜分,没有候选人获得半数选票,选举失败,所以每个节点设置的随机竞选超时时间不同,因此下一次再次出现多个 Candidate 瓜分选票的概率很低

每一任新的领导人出现,都会带有一个任期(term),任期是连续的整数,充当逻辑时钟。任期时长不确定,只要网络不发生大面积分区,而且超过半数的节点和 Leader 一直可以正常工作,这届任期可能就会非常长,通过任期可以比较各个节点的数据新旧、识别过期的 Leader 等。

如果一个候选人或者领导者,发现自己的任期编号比其他节点小,那么它会立即恢复成跟随者状态,如果一个节点接收到一个包含较小的任期编号值的请求,那么它会直接拒绝这个请求

日志复制

Raft 对“已提交”的条件定义也很简单有效,如果一个日志被 Leader 复制到大多数节点,日志就算被提交了,这点跟Kafka的生产者提交一样

2022711113515

成员变更

当集群里的机器发生变更时,Raft 引入了一个过渡共识的状态,处于这个状态的算法:

类似于数据迁移的双写策略

数据同步

安全性问题

通过给选举和日志复制增加一系列规则,来实现 Raft 算法的安全性

切换新 Leader 之后,新的 Leader 可能没有同步到最新的日志写入。而这可能会导致,新的 Leader 会尝试覆盖之前 Leader 已经写入的数据

想要确保 Leader 的日志是最新的,只需要在 Leader 选举的时候,让只有最新日志的 Leader 才能被选上就好,即当节点收到选举投票的时候,需检查候选者的最后一条日志中的任期号,若小于自己则拒绝投票。如果任期号相同,日志却比自己短,也拒绝为其投票

日志匹配:

如果某个日志条目在某个任期号中已经被提交,该记录必定出现在更大任期号的所有领导人中,限制 Candidate 提交选举请求的时候,必须至少和 Follower 的日志一样新,才可以获得选票

Goossip协议

最终一致性的分布式共识协议

2020111815129

直接邮寄

直接发送更新数据,当数据发送失败时,将数据缓存下来,然后重传,可能会因为缓存队列满了而丢数据

反熵

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

传谣

Quorum NWR

PBFT

前提:

  1. 消息来源无法伪造
  2. 基于大多数原则(2f + 1)实现共识 f为叛徒数

2022722161932

主节点叛变了怎么办?

如果恶意节点当选了主节点,此时无论忠诚节点数多少,忠诚节点们将都无法达成共识

当客户端发现主节点是叛徒时,就可以向其他可信节点发送指令,这些节点就可以在自己选举出新的可信主节点

PoW

请求方做了一些运算,解决了某个问题,然后把运算结果发送给验证方,进行核验,验证方根据运算结果,这个过程是不对称的,运算要耗费较多的资源,但易于验证

给定一个随机值,如果其哈希值满足特定形式,工作就完成,验证方验证变更的字符串是不是真的满足这个形式来验证通过

区块链的工作证明是通过对区块头执行 SHA256 哈希运算,得到小于目标值(动态调整的公共值,像比特币这个值现在正在越调越小)的哈希值,来证明自己的工作量,只有验证通过后,当前区块才会被加入链中

区块头及区块体

共识的局限性