分布式的一致性问题的算法
在分布式系统中,一致性(consensus)问题,是指对于系统中的多个服务节点,给定一系列操作,在一致性协议保障下,试图使得它们对处理结果达成一致。
在实际的计算机系统中,存在如下问题:
- 节点间的网络通讯是不可靠的,包括任意延迟和内容故障;
- 节点的处理可能是错误的,甚至节点自身随时可能宕机;
- 同步调用会绕过系统变得不具备可扩展性;
一个分布式的一致性算法应该满足:
可终止性(Termination):一致性的结果在有限的时间内能完成;
一致性(Consensus):不同节点最终完成决策的结果应该相同;
合法性(Validity):决策的结果必须是其他进程提出的提案;
绝对理想的一致性在分布式系统中很难达成,但可以使用带约束的一致性放宽要求:顺序一致性(Sequential Consistency)、线性一致性(Linearizability Consistency,依赖于全局时钟或锁)。
一致性的最坏界限在哪里呢?一般情况下,分布式系统的一致性问题无解。
FLP 不可能原理:在网络可靠,存在节点失效的最小化异步模型系统中,不存在一个可以解决的一致性问题的确定性算法。
但在付出一些代价的情况下,我们能做到多少?
CAP原理:分布式系统不可能同时确保一致性(Consistency)、可用性(Availablity)和分区容忍性(Partition)。
一致性(Consistency):任何操作都应该是原子的,发生在后面的事件能看到前面事件发生导致的结果;
可用性(Availablity):在有限时间内,任何失败节点都能应答请求;
分区容忍性(Partition):网络可能发生分区,即节点之间的通讯不可保障。
当网络不可靠时,系统要么牺牲掉一致性(过一段时间后更新结果,期间不保证一致性),要么牺牲掉可用性(系统故障时拒绝服务,如Paxos、Raft等算法),要么不保证分区容忍性(通过双通道等机制增强可靠性,达到高稳定网络)。既然CAP 不可同时满足,则在设计系统时必然要弱化对某个特性的支持。
ACID 原则描述了对分布式数据库的一致性需求,同时付出了可用性的代价。
Atomicity(原子性):每次操作都是原子的,要么成功,要么不执行;
Consistency(一致性):数据库的状态是一致的,无中间状态;
Isolation(隔离性):各种操作彼此互相不影响;
Durability(持久性):状态的改变是持久的,不会失效;
一个与之相对的原则是 BASE(Basic Availiability,Soft state,Eventually Consistency),牺牲掉对一致性的约束,来换取一定的可用性。
Paxos 问题
Paxos 问题是指分布式的系统中存在故障,但不存在恶意节点(无伪造消息,但可能丢失或重复)场景下的一致性问题。
Paxos 一致性算法,基于两阶段提交并进行扩展,在工程角度实现了一种最大化保障一致性(存在极小概率无法实现一致性)的机制,广泛应用在 Chubby、Zookeeper系统中。
算法中将节点分为三种类型,并满足三点约束要求:proposer(提出一个提案,等待大家批准为结案)、acceptor(负责对提案进行投票)、learner(被告知结案结果,并与之统一,不参与投票过程)。决议(value)只有在被 proposers 提出的 proposal 才能被最终批准;再一次执行实例中,只批准(chosen)一个最终决议;learners 智能获得被批准的决议。
基本过程包括 proposer 提出提案,先争取大多数 acceptor 的支持,超过一半支持时,则发送结案结果给所有人进行确认。proposer 在此过程中出现故障,可以通过超时机制来解决。若每一轮新的提案 proposer 都恰好故障,系统则永远无法达成一致(概率很小)。
Poxos 能保证在超过一半的正常节点存在时,系统能达成一致。
若系统中限定只有某个特定节点是提案者,则一致性肯定能达成,要么达成,要么失败(提案者故障,系统无法工作)。
若存在多个提案者,问题就变得复杂了。
一种情况是同一时间片段(一个提案周期)内只有一个提案者。需要设计一种机制来保障提案者的正确产生,如按照时间、序列、或者比较之类。实际是非常难的。
另一种情况是允许同一时间片段可以出现两个提案者。那同一个节点可能收到两份提案,节点根据提案序号来判断接受哪个。如何为提案分配序号呢?一种可能的方案是每个节点的提案数字区间彼此隔离开,互不冲突。为了满足递增的需求可以配合用时间戳作为高位字段。
两阶段的提交:
提案者发出提案后,收到一些反馈,此时得知的结果是自己的提案被大多数接受了,或者没被接受。即便受到来自大多数的接受反馈,也不能认为最终确认了。
因此引入一个新的阶段(commit 阶段),提案者在前一阶段(prepare阶段)拿到所有反馈后,需要判断和确认该提案是否为可能被大多数接受的提案。
准备阶段,多个提案者可以发送提案:<id, value>, 接收者收到提案就返回收到消息,并只保留最新提案,若收到一个请求的提案号比目前保留的小,则返回保留的提案给提案者,告诉他已经有人发出更新的提案了。
提交阶段,若一个提案者在准备阶段收到大多数的回复(表示大部分人听到它的请求,可能做好了最终确认的准备啦),则再次发出确认消息。若再次收到大多数的回复,并且大家都返回空,则带上原来的提案号和内容;若返回中有更新的提案,则替换提案值为更新提案的值。若没有收到足够多的回复,则需要再次发出请求。接受者若发现该提案号跟自己目前保留的一致,则确认该提案。
Raft 问题
Raft 是对 Paxos 的重新设计和实现,是Paxos 算法的一种简化实现。包括三种角色:leader、candiate 和 follower。
Leader 选举:每个 candidate 随机经过一定时间都会提出选举方案,最近阶段中得票最多者被选举为 leader;
同步 Log:leader 会找到系统中各种事件发生记录的 log 最新记录,并强制所有 follower 来刷新到这个记录;
拜占庭问题与算法
拜占庭问题讨论的是允许少数点作恶(消息可能被伪造)场景下的一致性达成问题(最坏情况下的保障)。
假设只有3个人,A、B、C,三人中如果其中一个是叛徒。当A发出进攻命令时,B如果是叛徒,他可能告诉C,他收到的是“撤退”的命令。这时C收到一个“进攻”,一个“撤退“,于是C被信息迷惑,而无所适从。
如果A是叛徒。他告诉B“进攻”,告诉C“撤退”。当C告诉B,他收到“撤退”命令时,B由于收到了司令“进攻”的命令,而无法与C保持一致。
正由于上述原因,在只有三个角色的系统中,只要有一个是叛徒,即叛徒数等于1/3,拜占庭问题便不可解。
面向拜占庭问题的容错算法 (Byzantine Fault Tolerant,BFT 算法),解决的是网络通讯的可靠,但节点可能故障情况下的一致性达成。
PBFT 算法是第一个得到广泛应用的 BFT 算法,包括三个阶段来达成共识:Pre-Prepare、Prepare 和 commit。
解决思路:
比特币的区块链网络在设计时提出了 PoW(Proof of work)算法思路。一个是限制一段时间内整个网络中出现提案的个数,另一个是放宽对最终一致性确认的需求,约定好大家都确认并沿着已知最长的链进行拓宽。系统的最终确认是概率上存在的,即时有人试图破坏,需要付出超过系统一半算力的代价。各个系列的 PoX 算法都是采用经济上的惩罚来制约破坏者。
可靠性指标
一般来说,单点服务器系统至少能满足两个九(99%)概率可靠性,企业信息系统三个九(99.9%),互联网系统能达到四个九(99.99%)已经是业内领先水平,电信级应用一般能达到五个九(99.999%)。该如何提高可靠性呢?
一是让单点系统变得更可靠,通过替换单点的软硬件来改善可靠性。
二是消灭单点,通过主从、多活等模式让多个节点集体完成原先单点的工作。
已有 0 人发表留言,猛击->> 这里<<-参与讨论
ITeye推荐