关于协议:DatenLord|Curp-共识协议的重新思考

39次阅读

共计 2751 个字符,预计需要花费 7 分钟才能阅读完成。

共识简介

共识协定是一种让分布式系统中多个节点放弃信息统一的通信协议,即便多数节点产生故障也仍然可能保障信息的精确和统一。而每当咱们在探讨共识协定的时候往往会想到 classic paxos 或者 raft 协定,这两个协定是很多其余协定的根底,后续的很多协定都能够看成是它们的变种,例如 Multi-Paxos 和 Fast-Paxos 等等。咱们明天先从这两个协定动手,先来回顾一下这两个协定是如何工作的。

首先来看 classic paxos 协定,如下图所示。Paxos 分为两个阶段(Phase),第一个阶段是 Prepare,次要工作是在 Log 上占一个 Slot,第二个阶段为 Accept,次要是确定这个 Slot 曾经明确被占用了,且在两个阶段间没有被其他人抢占。当 Client 收到绝大多数人的 Accept Ok 回复之后,阐明该条记录曾经被提交,在整个零碎达成了共识。这里 Client 和 Proposer 能够视为一个整体,整个过程在两个阶段别离有一次消息传递,总共产生两次消息传递。

而后咱们再看 raft 协定,如下图所示。Raft 也是通过 Client 来发动,Client 向 Leader 发送申请,Leader 将申请播送给所有 Follower,当超过半数 Follower 回复音讯,Leader 确定该申请被提交,而后将音讯回复给 Client。这里 Client 和 Leader 之间进行了一消息传递,Leader 和 Follower 之间进行了一次消息传递,总共产生了两次消息传递。

咱们发现在上述的两个协定中,想要达成共识就必须要通过两次消息传递。两次消息传递在数据中心外部还不会造成太大的影响,增大的申请提早往往还能够承受,然而在跨数据中心的场景下,每多一次消息传递就减少几十甚至上百毫秒的提早,所以减小消息传递的数目在跨数据中心的场景下就十分必要。
接下去大家肯定会问“两次音讯是必要的的吗”?答复是在 Raft 和 Classic Paxos 的条件下,两次消息传递是必须的,因为他们同时保障了两个个性:

  • 申请一旦被 commit,则不会被批改或者失落。
  • 申请执行程序一旦被确定,程序也不会被批改或失落。

想要同时保障这两个个性,一次消息传递肯定不够。在 paxos 这种无 Leader 的协定中,一次消息传递只能保障绝大多数节点收到的了申请,那么第 1 个个性可能放弃,然而多个申请间的程序没有方法在多节点间保持一致,毁坏了第 2 个个性。在 Raft 这种有 Leader 的协定中,一次消息传递只能让 Leader 确定执行程序,也就是第 2 个个性,但无奈保障该申请不会失落,因为此时只有 Leader 节点获悉这个申请。

那么咱们有什么方法来缩小一次消息传递呢?答案是放松个性,将个性 2 中的“全局惟一执行程序”给舍弃,扭转成“相冲突的申请保障全局惟一执行程序,无关的申请可乱序执行”。Curp 协定就是引入了这个思维,仅通过 1 个消息传递实现共识协定。上面这个章节咱们来介绍 Curp 协定。

Curp 共识协定

本章咱们来聊一聊 Curp 如何通过 1 个消息传递达成共识。因为细节繁琐和篇幅限度,本文不会残缺探讨 Curp 共识协定的所有方面,而是摘取其中的关键点来论述。下图为 Curp 协定的示意图:

次要流程形容如下:

1、Client 向包含 Master(Leader) 的所有节点发送申请。
2、所有服务节点都保护一个申请“期待池子”,图中的蓝色申请都在“期待池子”中,这些申请都还没有实现同步。
3、所有服务节点收到 Client 发送来的申请后会查看以后申请和“期待池子”中的所有申请是否抵触,如果抵触,则给 Client 回复申请抵触,如果不抵触,则给 Client 回复申请不抵触。
4、Client 在收集到不少于 (f + (f + 1)/ 2 + 1) 个“申请不抵触”回复且其中蕴含 Master 的回复后,认为该申请曾经被 committed。否则 Client 期待 Master 将申请同步到绝大多数节点,而 Master 在同步实现后会将申请移出期待池子,并且告诉 Client 申请达成共识。

这里咱们以 问答 的形式来解释 Curp 协定,不便大家了解。

Q1. Client 在收到不少于 (f + (f + 1)/ 2 + 1) 个“申请不抵触”回复且其中蕴含 Master 的回复后,为什么可能确认申请被 committed?
A1:因为期待队池子是具备排他性质的,被绝大多数节点认可阐明该申请在绝大多数的节点上不存在抵触,也阻止了后续可能抵触的申请被提交。此时即便有 f 个节点产生故障,咱们依然可能在 (f + 1) / 2 + 1 个节点上找到这个申请,申请不会失落。这样不仅保障了这个申请肯定不会失落,还因为有之前的抵触查看,也保障了抵触申请间的执行程序。

Q2. 上一个问题中数字 (f + (f + 1)/ 2 + 1) 很奇怪,为什么不是 f + 1?
A2:共识协定最多容许 f 个节点产生故障,那么剩下的节点为 f + 1 个,最蹩脚的状况中,那 f 个产生故障的节点全副蕴含了该申请,那么剩下的 f + 1 中还至多存在 (f + 1) / 2 + 1 个节点蕴含该申请,占有绝大多数,不便复原流程将该申请复原,避免失落。

Q3. 是否所有的状况下 Curp 都可能在 1 个消息传递后达到共识?
A3:不能保障。最好的状况是所有的申请都不互相冲突,那么所有申请都可能在一个消息传递后达到共识;最坏状况是所有的申请都相冲突,那么简直所有申请都须要等 Master(Leader)节点实现同步后,Client 能力确认申请被 commit,这种状况就是 2 个消息传递,和 Raft 相似。

Q4. Master 同步申请的协定细节是什么?
A4:Master 同步申请的形式 Raft Leader 节点一样,齐全没有区别。

Q5. Curp 协定的复原流程是如何的?
A5:首先复原流程须要选举一个新的 Master(Leader),该流程和 Raft 一样。接下来的复原流程能够大体分成两个模块:曾经同步的申请局部,复原流程和 Raft 协定保持一致;那些还没有被同步的申请须要从所有节点收集,当收集到 f + 1 个节点(包含新 Leader 本人)信息后,保留其中呈现至多 (f + 1) / 2 + 1 次的申请,因为这些申请有可能曾经被 commit 了,因而不能失落。

Curp 协定总结和探讨

通过上一个章节的阐述,咱们不难发现 Curp 协定和 Raft 协定十分像,其中的不同点就在于“期待池子”,这个池子的目标在于给抵触的申请排序,多个抵触申请肯定不能被所有节点的“池子”同时承受,此时最多只有一个申请被 commit,也有可能所有申请都须要期待 master 的同步。也就是这个改变,让协定在某些状况下有更优良的性能体现。

所以总结一下,Curp 协定在乐观状况下一个消息传递就能达到共识,乐观状况下会进化成 Raft 协定,须要两个消息传递能力达成共识。

对于 Curp 协定的更多细节请参考原始论文。

作者 | 施继成,达坦科技(DatenLord)

正文完
 0