即 Atomicity(原子性)、Consistency(一致性)、Isolation(隔离性)、Durability(持久性)。

ACID 原则描述了对分布式数据库的一致性需求,同时付出了可用性的代价。


  • Atomicity:每次操作是原子的,要么成功,要么不执行;

  • Consistency:数据库的状态是一致的,无中间状态;

  • Isolation:各种操作彼此互相不影响;

  • Durability:状态的改变是持久的,不会失效。


一个与之相对的原则是 BASE(Basic Availiability,Soft state,Eventually Consistency), 牺牲掉对一致性的约束(最终一致性),来换取一定的可用性。

ACID 原则

Paxos 与 Raft

Paxos 问题是指分布式的系统中存在故障,但不存在恶意节点(无伪造消息,但可能丢失或重复)场景下的一致性问题。因为最早是 Leslie Lamport 用 Paxon 岛的故事模型来进行描述而命名。

Paxos

1990 年由 Leslie Lamport 提出的 Paxos 一致性算法,在工程角度实现了一种最大化保障一致性(存在极小的概率无法实现一致性)的机制。Paxos 被广泛应用在 Chubby、ZooKeeper 这样的系统中,Leslie Lamport 因此获得了 2013 年度图灵奖。

故事背景是古希腊 Paxon 岛上的多个法官在一个大厅内对一个议案进行表决,如何达成统一的结果。他们之间通过服务人员来传递纸条,但法官可能离开或进入大厅,服务人员可能偷懒去睡觉。

Paxos 是第一个被证明的一致性算法,其原理基于两阶段提交并进行扩展。

作为现在一致性算法设计的鼻祖,以最初论文的难懂(算法本身并不复杂)出名。算法中将节点分为三种类型:

  • proposer:提出一个提案,等待大家批准为结案;

  • acceptor:负责对提案进行投票;

  • learner:被告知结案结果,并与之统一,不参与投票过程。

并满足三点约束要求:

  • 决议(value)只有在被 proposers 提出的 proposal 才能被最终批准;

  • 在一次执行实例中,只批准(chosen)一个最终决议,意味着多数接受(accept)的结果能成为决议;

  • learners 只能获得被批准(chosen)的决议。

Paxos 与 Raft

基本过程包括 proposer 提出提案,先争取大多数 acceptor 的支持,超过一半支持时,则发送结案结果给所有人进行确认。一个潜在的问题是 proposer 在此过程中出现故障,可以通过超时机制来解决。极为凑巧的情况下,每次新的一轮提案的 proposer 都恰好故障,系统则永远无法达成一致(概率很小)。

Paxos 能保证在超过一半的正常节点存在时,系统能达成一致。

读者可以试着自己设计一套能达成一致性的方案,会发现在满足各种约束情况下,算法自然就会那样设计。

单个提案者

如果系统中限定只有某个特定节点是提案者,那么一致性肯定能达成(只有一个方案,要么达成,要么失败)。

但一旦提案者故障,则系统无法工作。

多个提案者

问题一下子变得复杂了。

一种情况是同一时间片段(如一个提案周期)内只有一个提案者。这需要设计一种机制来保障提案者的正确产生,例如按照时间、序列、或者大家猜拳(出一个数字来比较)之类。考虑到分布式系统要处理的工作量很大,这个过程要尽量高效,满足这一条件的机制非常难设计。

另一种情况是允许同一时间片段内可以出现两个提案者。那同一个节点可能收到两份提案, 怎么对他们进行区分呢?很自然的,提案需要带上不同的序号。节点需要根据提案序号来判断接受哪个。比如接受其中序号较大(往往意味着是接受新提出的,因为旧提案者故障概率更大)的提案。

如何为提案分配序号呢?一种可能方案是每个节点的提案数字区间彼此隔离开,互相不冲突。为了满足递增的需求可以配合用时间戳作为高位字段。

两阶段的提交

提案者发出提案之后,收到一些反馈。这个时候得知的一种结果是自己的提案被大多数接受了,一种结果是没被接受。没被接受的话好说,过会再试试。

即便受到来自大多数的接受反馈,也不能认为就最终确认了。因为这些接收者自己并不知道自己刚反馈的提案就恰好是全局的绝大多数。

很自然的,引入了新的一个阶段,即提案者在前一阶段拿到所有的反馈后,判断这个提案是可能被大多数接受的提案,需要对其进行最终确认。

Paxos 里面对这两个阶段分别命名为准备(prepare)和提交(commit)。准备阶段解决大家对哪个提案进行投票的问题,提交阶段解决确认最终值的问题。

下面,我们简化认为更大的提案号意味着更新的提案。

准备阶段,比较简单,多个提案者可以发送提案: <id, value> ,接收者收到提案就返回收到消息,并且只保留最新的提案。如果收到一个请求的提案号比目前保留的小,则返回保留的提案给提案者,告诉它已经有其它人发出更新的提案了。

提交阶段,如果一个提案者在准备阶段收到大多数的回复(表示大部分人听到它的请求,可能做好了最终确认的准备了),则再次发出确认消息。如果再次收到大多数的回复,并且大家都返回空,则带上原来的提案号和内容;如果返回中有更新的提案,则替换提案值为更新

提案的值。如果没收到足够多的回复,则需要再次发出请求。

收者如果发现这个提案号跟自己目前保留的一致,则确认该提案。

Raft

Raft 是对 Paxos 的重新设计和实现。

Raft 算法是Paxos 算法的一种简化实现。

包括三种角色:leader、candiate 和 follower,其基本过程为:

  • Leader 选举:每个 candidate 随机经过一定时间都会提出选举方案,最近阶段中得票最多者被选为 leader;

  • 同步 log:leader 会找到系统中 log 最新的记录,并强制所有的 follower 来刷新到这个记录;

注:此处 log 并非是指日志消息,而是各种事件的发生记录。


玖壹区块链声明

加微信:469649885区块链培训教程
还可免费获取区块链培训班试学名额

分享:

扫一扫在手机阅读、分享本文

区块链评论

玖壹区块链培训

玖壹区块链培训学院简称(玖壹学院http://www.91xiubbs.com/)提供区块链技术培训资料、区块链开发培训视频教程等下载,不过网上自学区块链技术课程必然存在一些缺陷:遇到问题易卡壳、学习周期漫长、无针对性等。区块链培训机构现场面对面的讲授区块链培训课程可以让您和团队在最短时间内掌握正确、系统、高效的区块链实战技术。