分布式的一致性问题的算法

标签: 分布 一致性 问题 | 发表时间:2018-07-31 23:40 | 作者:AVI
出处:http://www.iteye.com

 

在分布式系统中,一致性(consensus)问题,是指对于系统中的多个服务节点,给定一系列操作,在一致性协议保障下,试图使得它们对处理结果达成一致。

 

在实际的计算机系统中,存在如下问题:

  • 节点间的网络通讯是不可靠的,包括任意延迟和内容故障;
  • 节点的处理可能是错误的,甚至节点自身随时可能宕机;
  • 同步调用会绕过系统变得不具备可扩展性;

一个分布式的一致性算法应该满足:

可终止性(Termination):一致性的结果在有限的时间内能完成;

一致性(Consensus):不同节点最终完成决策的结果应该相同;

合法性(Validity):决策的结果必须是其他进程提出的提案;

 

绝对理想的一致性在分布式系统中很难达成,但可以使用带约束的一致性放宽要求:顺序一致性(Sequential Consistency)、线性一致性(Linearizability Consistency,依赖于全局时钟或锁)。

 

一致性的最坏界限在哪里呢?一般情况下,分布式系统的一致性问题无解。

FLP 不可能原理:在网络可靠,存在节点失效的最小化异步模型系统中,不存在一个可以解决的一致性问题的确定性算法。

三个人在不同房间进行电话沟通投票(投票结果是0或1),但经常会有人睡着。某刻A投票0,B投票1,C收到两人的投票时刚好睡着了,A和B则永远无法在有限时间内获知最终结果。若重新投票,类似情景都可能在取得结果前发生。

 

但在付出一些代价的情况下,我们能做到多少?

 

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 岛上的多个法官在一个大厅内对一个议案进行表决,如何达成统一的结果。它们通过服务人员来传递纸条,但法官可能离开或进入大厅,服务人员可能偷懒去睡觉。

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推荐



相关 [分布 一致性 问题] 推荐:

分布式系统中的事务一致性问题

- - CSDN博客架构设计推荐文章
在分布式系统中,我们经常遇到多数据副本保持一致的问题,在我们所能找到的资料中该问题讲的很笼统,模模糊糊的,把多个问题或分类糅合在一起,难以理解. 在思考和翻阅资料后,通俗地把一致性的问题可分解为2个问题:. 1、任何一次修改保证数据一致性. 在弱一致性的算法,不要求每次修改的内容在修改后多副本的内容是一致的,对问题1的解决比较宽松,更多解决问题2,该类算法追求每次修改的高度并发性,减少多副本之间修改的关联性,以获得更好的并发性能.

关于分布式系统的数据一致性问题

- - 互联网 - ITeye博客
现在先抛出问题,假设有一个主数据中心在北京M,然后有成都A,上海B两个地方数据中心,现在的问题是,假设成都上海各自的数据中心有记录变更,需要先同步到主数据中心,主数据中心更新完成之后,在把最新的数据分发到上海,成都的地方数据中心A,地方数据中心更新数据,保持和主数据中心一致性(数据库结构完全一致).

分布式的一致性问题的算法

- - 行业应用 - ITeye博客
在分布式系统中,一致性(consensus)问题,是指对于系统中的多个服务节点,给定一系列操作,在一致性协议保障下,试图使得它们对处理结果达成一致. 在实际的计算机系统中,存在如下问题:. 节点间的网络通讯是不可靠的,包括任意延迟和内容故障;. 节点的处理可能是错误的,甚至节点自身随时可能宕机;. 同步调用会绕过系统变得不具备可扩展性;.

分布式系统的事务及一致性模型

- Roger - NoSQLFan
下面PPT出自10gen的产品和工程高级副总裁 Roger Bodamer ,参加过Mongo Beijing的人应该记得会上的大个子. 下面PPT 主要就分布式系统的事务及一致性模型进行了分析和讨论. 对分布式存储在CAP原理下的选择和实现进行了描述. Google Megastore系统事务机制.

memcached的总结和分布式一致性hash

- - 开源软件 - ITeye博客
当前很多大型的web系统为了减轻数据库服务器负载,会采用memchached作为缓存系统以提高响应速度. memcached是一个开源的高性能分布式内存对象缓存系统. 其实思想还是比较简单的,实现包括server端(memcached开源项目一般只单指server端)和client端两部分:. server端本质是一个in-memory key-value store,通过在内存中维护一个大的hashmap用来存储小块的任意数据,对外通过统一的简单接口(memcached protocol)来提供操作.

分布式系统数据一致性的6种方案(转)

- - 企业架构 - ITeye博客
编者按:本文由「高可用架构后花园」群讨论整理而成,后花园是一个面向架构师的增值服务,如需了解,请关注「高可用架构」后回复 VIP.                                                                                 问题的起源.

分布式系统的一致性算法简介

- - 互联网 - ITeye博客
在分布式系统中,我们经常遇到多数据副本保持一致的问题,在我们所能找到的资料中该问题讲的很笼统,模模糊糊的,把多个问题或分类糅合在一起,难以理解. 在思考和翻阅资料后,通俗地把一致性的问题可分解为2个问题:. 1、任何一次修改保证数据一致性. 2、多次数据修改的一致性. 在弱一致性的算法,不要求每次修改的内容在修改后多副本的内容是一致的,对问题1的解决比较宽松,更多解决问题2,该类算法追求每次修改的高度并发性,减少多副本之间修改的关联性,以获得更好的并发性能.

分布式一致性协议Raft原理与实例

- - zzm
分布式一致性协议Raft原理与实例. Raft是由Stanford提出的一种更易理解的一致性算法,意在取代目前广为使用的Paxos算法. 目前,在各种主流语言中都有了一些开源实现,比如本文中将使用的基于JGroups的Raft协议实现. 关于Raft的原理,强烈推荐 动画版Raft讲解. 在Raft中,每个结点会处于下面三种状态中的一种:.

分布式系统一致性保障方案总结

- -
猫友会群里经常卧虎藏龙,转载一篇百度大牛,投稿原创文章,大家交流学习 ,文末有作者个人公众号. 欢迎更多猫友投稿,发布原创文章和干货和大家分享交流.        在互联网系统中,理想的情况下,肯定是希望系统能够同时满足“一致性”、“可用性”和“分区容忍性”. 但是基于熟悉的CAP定律也好,还是BASE理论, 我们知道,在实际情况中是不可能实现的.

微服务分布式一致性模式 – ThoughtWorks洞见

- -
微服务拆分后遇到的一个麻烦是分布后的一致性问题. 单体架构的业务处理和数据都在一个进程里面,一致性保障很成熟,开发人员基本上不用关心. 当把业务系统拆分到不同进程时,就遇到了技术性一致性问题. 这带来了纠结,我们希望有一颗银弹,一把解决问题. 但由于分布式一致性在(CAP)理论上没有完美的解决方案,我们所能选择的方案是在特定业务场景下的选择.