关于分布式:一文总结分布式一致性技术是如何演进的

简介: 分布式一致性(Consensus)作为分布式系统的基石,始终都是计算机系统畛域的热点。近年来随着分布式系统的规模越来越大,对可用性和一致性的要求越来越高,分布式一致性的利用也越来越宽泛。纵观分布式一致性在工业界的利用,从最开始的鼻祖Paxos的一统天下,到横空出世的Raft的风行,再到现在Leaderless的EPaxos开始备受关注,背地的技术是如何演进的?本文将从技术角度探讨分布式一致性在工业界的利用,并从可了解性、可用性、效率和实用场景等几个角度进行比照剖析。

分布式一致性

分布式一致性,简略的说就是在一个或多个过程提议了一个值后,使零碎中所有过程对这个值达成统一。

为了就某个值达成统一,每个过程都能够提出本人的提议,最终通过分布式一致性算法,所有正确运行的过程学习到雷同的值。

工业界对分布式一致性的利用,都是为了构建多正本状态机模型(Replicated State Machine),实现高可用和强统一。

分布式一致性使多台机器具备雷同的状态,运行雷同的确定性状态机,在多数机器故障时整体仍能失常工作。

Paxos

Paxos达成一个决定至多须要两个阶段(Prepare阶段和Accept阶段)。

Prepare阶段的作用:

  • 争取提议权,争取到了提议权能力在Accept阶段发动提议,否则须要从新争取。
  • 学习之前曾经提议的值。

Accept阶段使提议造成多数派,提议一旦造成多数派则决定达成,能够开始学习达成的决定。Accept阶段若被回绝须要从新走Prepare阶段。

Multi-Paxos

Basic Paxos达成一次决定至多须要两次网络来回,并发状况下可能须要更多,极其状况下甚至可能造成活锁,效率低下,Multi-Paxos正是为解决此问题而提出。

Multi-Paxos选举一个Leader,提议由Leader发动,没有竞争,解决了活锁问题。提议都由Leader发动的状况下,Prepare阶段能够跳过,将两阶段变为一阶段,提高效率。Multi-Paxos并不假如惟一Leader,它容许多Leader并发提议,不影响安全性,极其状况下进化为Basic Paxos。

Multi-Paxos与Basic Paxos的区别并不在于Multi(Basic Paxos也能够Multi),只是在同一Proposer间断提议时能够优化跳过Prepare间接进入Accept阶段,仅此而已。

Raft

不同于Paxos间接从分布式一致性问题登程推导进去,Raft则是从多正本状态机的角度提出,应用更强的假如来缩小须要思考的状态,使之变的易于了解和实现。

Raft与Multi-Paxos有着千头万绪的关系,上面总结了Raft与Multi-Paxos的异同。

Raft与Multi-Paxos中类似的概念:

  • Raft的Leader即Multi-Paxos的Proposer。
  • Raft的Term与Multi-Paxos的Proposal ID实质上是同一个货色。
  • Raft的Log Entry即Multi-Paxos的Proposal。
  • Raft的Log Index即Multi-Paxos的Instance ID。
  • Raft的Leader选举跟Multi-Paxos的Prepare阶段实质上是雷同的。
  • Raft的日志复制即Multi-Paxos的Accept阶段。

Raft与Multi-Paxos的不同:

Raft假如零碎在任意时刻最多只有一个Leader,提议只能由Leader收回(强Leader),否则会影响正确性;而Multi-Paxos尽管也选举Leader,但只是为了提高效率,并不限度提议只能由Leader收回(弱Leader)。

强Leader在工程中个别应用Leader Lease和Leader Stickiness来保障:

  • Leader Lease:上一任Leader的Lease过期后,随机期待一段时间再发动Leader选举,保障新旧Leader的Lease不重叠。
  • Leader Stickiness:Leader Lease未过期的Follower回绝新的Leader选举申请。

Raft限度具备最新已提交的日志的节点才有资格成为Leader,Multi-Paxos无此限度。

Raft在确认一条日志之前会查看日志连续性,若查看到日志不间断会回绝此日志,保障日志连续性,Multi-Paxos不做此查看,容许日志中有空洞。

Raft在AppendEntries中携带Leader的commit index,一旦日志造成多数派,Leader更新本地的commit index即实现提交,下一条AppendEntries会携带新的commit index告诉其它节点;Multi-Paxos没有日志连接性假如,须要额定的commit音讯告诉其它节点。

EPaxos

EPaxos(Egalitarian Paxos)于SOSP’13提出,比Raft还稍早一些,但Raft在工业界大行其道的工夫里,EPaxos却长期无人问津,直到最近,EPaxos开始被工业界所关注。

EPaxos是一个Leaderless的一致性算法,任意正本均可提交日志,通常状况下,一次日志提交须要一次或两次网络来回。

EPaxos无Leader选举开销,一个正本不可用可立刻拜访其余正本,具备更高的可用性。各正本负载平衡,无Leader瓶颈,具备更高的吞吐量。客户端可抉择最近的正本提供服务,在跨AZ跨地区场景下具备更小的提早。

不同于Paxos和Raft,当时对所有Instance编号排序,而后再对每个Instance的值达成统一。EPaxos不当时规定Instance的程序,而是在运行时动静决定各Instance之间的程序。EPaxos不仅对每个Instance的值达成统一,还对Instance之间的绝对程序达成统一。EPaxos将不同Instance之间的绝对程序也做为一致性问题,在各个正本之间达成统一,因而各个正本可并发地在各自的Instance中发动提议,在这些Instance的值和绝对程序达成统一后,再对它们依照绝对程序从新排序,最初按程序利用到状态机。

从图论的角度看,日志是图的结点,日志之间的程序是图的边,EPaxos对结点和边别离达成统一,而后应用拓扑排序,决定日志的程序。图中也可能造成环路,EPaxos须要解决循环依赖的问题。

EPaxos引入日志抵触的概念(与Parallel Raft相似,与并发抵触不是一个概念),若两条日志之间没有抵触(例如拜访不同的key),则它们的绝对程序无关紧要,因而EPaxos只解决有抵触的日志之间的绝对程序。

若并发提议的日志之间没有抵触,EPaxos只须要运行PreAccept阶段即可提交(Fast Path),否则须要运行Accept阶段能力提交(Slow Path)。

PreAccept阶段尝试将日志以及与其它日志之间的绝对程序达成统一,同时保护该日志与其它日志之间的抵触关系,如果运行完PreAccept阶段,没有发现该日志与其它并发提议的日志之间有抵触,则该日志以及与其它日志之间的绝对程序曾经达成统一,间接发送异步的Commit音讯提交;否则如果发现该日志与其它并发提议的日志之间有抵触,则日志之间的绝对程序还未达成统一,须要运行Accept阶段将抵触依赖关系达成多数派,再发送Commit音讯提交。

EPaxos的Fast Path Quorum为2F,可优化至F + [ (F + 1) / 2 ],在3正本和5正本时,与Paxos、Raft统一。Slow Path 为Paxos Accept阶段,Quorum固定为F + 1。

EPaxos还有一个被动Learn的算法,在复原的时候可用来追赶日志,这里就不做具体的介绍了,感兴趣的能够看论文。

比照剖析

从Paxos到Raft再到EPaxos,背地的技术是怎么样演进的,咱们能够从算法自身来做个比照,上面次要从可了解性、效率、可用性和实用场景等几个角度进行比照剖析。

1 可了解性

家喻户晓,Paxos是出了名的艰涩难懂,不仅难以了解,更难以实现。而Raft则以可了解性和易于实现为指标,Raft的提出大大降低了应用分布式一致性的门槛,将分布式一致性变的大众化、平民化,因而当Raft提出之后,迅速失去青眼,极大地推动了分布式一致性的工程利用。

EPaxos的提出比Raft还早,但却长期无人问津,很大一个起因就是EPaxos切实是难以了解。EPaxos基于Paxos,但却比Paxos更难以了解,大大地妨碍了EPaxos的工程利用。不过,是金子总会发光的,EPaxos因着它独特的劣势,终于被人们发现,具备广大的前景。

2 效率

从Paxos到Raft再到EPaxos,效率有没有晋升呢?咱们次要从负载平衡、音讯复杂度、Pipeline以及并发解决几个方面来比照Multi-Paxos、Raft和EPaxos。

负载平衡

Multi-Paxos和Raft的Leader负载更高,各正本之间负载不平衡,Leader容易成为瓶颈,而EPaxos无需Leader,各正本之间负载齐全平衡。

音讯复杂度

Multi-Paxos和Raft选举出Leader之后,失常只须要一次网络来回就能够提交一条日志,但Multi-Paxos须要额定的异步Commit音讯提交,Raft只须要推动本地的commit index,不应用额定的音讯,EPaxos依据日志抵触状况须要一次或两次网络来回。因而音讯复杂度,Raft最低,Paxos其次,EPaxos最高。

Pipeline

咱们将Pipeline分为程序Pipeline和乱序Pipeline。Multi-Paxos和EPaxos反对乱序Pipeline,Raft因为日志连续性假如,只反对程序Pipeline。但Raft也能够实现乱序Pipeline,只须要在Leader上给每个Follower保护一个相似于TCP的滑动窗口,对应每个Follower上保护一个接管窗口,容许窗口外面的日志不间断,窗口里面是曾经间断的日志,日志一旦间断则向前滑动窗口,窗口外面可乱序Pipeline。

并发解决

Multi-Paxos沿用Paxos的策略,一旦发现并发抵触则回退重试,直到胜利;Raft则应用强Leader来防止并发抵触,Follwer不与Leader竞争,防止了并发抵触;EPaxos则直面并发抵触问题,将抵触依赖也做为一致性问题看待,解决并发抵触。Paxos是抵触回退,Raft是抵触防止,EPaxos是抵触解决。Paxos和Raft的日志都是线性的,而EPaxos的日志是图状的,因而EPaxos的并行性更好,吞吐量也更高。

3 可用性

EPaxos任意正本均可提供服务,某个正本不可用了可立刻切换到其它正本,正本生效对可用性的影响微不足道;而Multi-Paxos和Raft均依赖Leader,Leader不可用了须要从新选举Leader,在新Leader未选举进去之前服务不可用。显然EPaxos的可用性比Multi-Paxos和Raft更好,但Multi-Paxos和Raft比谁的可用性更好呢。

Raft是强Leader,Follower必须等旧Leader的Lease到期后能力发动选举,Multi-Paxos是弱Leader,Follwer能够随时竞选Leader,尽管会对效率造成肯定影响,但在Leader生效的时候能更快的复原服务,因而Multi-Paxos比Raft可用性更好。

4 实用场景

EPaxos更实用于跨AZ跨地区场景,对可用性要求极高的场景,Leader容易造成瓶颈的场景。Multi-Paxos和Raft自身十分类似,实用场景也相似,实用于内网场景,个别的高可用场景,Leader不容易造成瓶颈的场景。

思考

最初留下几个思考题,感兴趣的同学能够思考思考:

1)Paxos的Proposal ID须要惟一吗,不惟一会影响正确性吗?

2)Paxos如果不辨别Max Proposal ID和Accepted Proposal ID,合并成一个Max Proposal ID,过滤Proposal ID小于等于Max Proposal ID的Prepare申请和Accept申请,会影响正确性吗?

3)Raft的PreVote有什么作用,是否肯定须要PreVote?

【腾讯云】轻量 2核2G4M,首年65元

阿里云限时活动-云数据库 RDS MySQL  1核2G配置 1.88/月 速抢

本文由乐趣区整理发布,转载请注明出处,谢谢。

您可能还喜欢...

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据