`

(转)浅谈分布式系统的基本问题:可用性与一致性

阅读更多

该文章来自于阿里巴巴技术协会(ATA)精选文章。

背景

可用性(Availability)和一致性(Consistency)是分布式系统的基本问题,先有著名的CAP理论定义过分布式环境下二者不可兼得的 关系,又有神秘的Paxos协议号称是史上最简单的分布式系统一致性算法并获得图灵奖,再有开源产品ZooKeeper实现的ZAB协议号称超越 Paxos,它们之间究竟有什么联系?在网络上没有文章将其清楚地阐述过,于是想到把自己对CAP理论、Paxos协议以及ZAB协议的理解整理成短文, 但我唯一不保证的是正确性,各位看官看着办。

分布式系统的挑战

一致性可理解为所有节点都能访问到最新版本的数据,这在单机场景下非常容易实现,使用共享内存和锁即可解决,但数据存储在单机会有两个限制:1)单机不可 用系统整体将不可用;2)系统吞吐量受限于单机的计算能力。消除这两个限制的方法是用多机来存储数据的多个副本,负责更新的客户端会同时更新数据的多个副 本,于是问题就来了,多机之间的网络可能无法连接,当负责更新的客户端无法同时到连接多个机器时,如何能保证所有客户端都能读到最新版本的数据?

如下图1中所示,Client A负责更新数据,为了保证Server 1Server 2上的数据是一致的,Client A会将X=1的写操作同时发给Server 1Server 2,但是当Client AServer 2之间发生网络分区(网络无法连接)时,此时如果让write X=1的写操作在Server 1上成功,那Client BClient C将从Server 1Server 2上读取到不一致的X值;此时如果要保持X值的一致性,那么write X=1的写操作在Server 1Server 2上都必须失败,这就是著名的CAP理论:在容忍网络分区的前提下,要么牺牲数据的一致性,要么牺牲写操作的可用性。

1CAP理论示意图

 

解决这个问题你可能会想到让Client C同时读取Server 1Server 2上的X值和版本信息,然后取Server 1Server 2最新版本的X, 如下图2所示。但Client CServer 1之间也可能发生网络分区,这本质上是牺牲读可用性换取写可用性,并没有突破CAP理论。



 
2:对图1中可用性的优化

 

CAP理论

CAP理论由加州大学伯克利分校的计算机教授Eric Brewer2000年提出,其核心思想是任何基于网络的数据共享系统最多只能满足数据一致性(Consistency)、可用性 (Availability)和网络分区容忍(Partition Tolerance)三个特性中的两个,三个特性的定义如下:

   数据一致性:等同于所有节点拥有数据的最新版本

   可用性:数据具备高可用性

   分区容忍:容忍网络出现分区,分区之间网络不可达

在大规模的分布式环境下,网络分区是必须容忍的现实,于是只能在可用性和一致性两者间做出选择,CAP理论似乎给分布式系统定义了一个悲观的结局,一时间 大家都按照CAP理论在对热门的分布式系统进行判定,譬如认为HBase是一个CP系统,CassandraAP系统,我个人认为这是不严谨的,理由是 CAP理论是对分布式系统中一个数据无法同时达到可用性和一致性的断言,而一个系统中往往存在很多类型的数据,部分数据(譬如银行账户中的余额)是需要强 一致性的,而另外一部分数据(譬如银行的总客户数)并不要求强一致性,所以拿CAP理论来划分整个系统是不严谨的, CAP理论带来的价值是指引我们在设计分布式系统时需要区分各种数据的特点,并仔细考虑在小概率的网络分区发生时究竟为该数据选择可用性还是一致性。

CAP理论的另外一种误读是系统设计时选择其一而完全不去优化另外一项,可用性和一致性的取值范围并不是只有01,可用性的值域可以定义成0 100%的连续区间,而一致性也可分为强一致性、弱一致性、读写一致性、最终一致性等多个不同的强弱等级,细想下去CAP理论定义的其实是在容忍网络分区 的条件下,“强一致性”和“极致可用性”无法同时达到。(注:这里用“极致可用性”而不用“100%可用性”是因为即使不考虑一致性,多台server 成的分布式系统也达不到100%的可用性,如果单个server的可用性是P,那nserver的极致可用性是,公式的意思是只要任何一台或多台server可用就认为系统都是可用的)

虽然无法达到同时达到强一致性和极致可用性,但我们可以根据数据类型在二者中选择其一后去优化另外一个,Paxos协议就是一种在保证强一致性前提下把可用性优化到极限的算法。

Paxos协议

Paxos协议由Leslie Lamport最早在1990年提出,由于Paxos在云计算领域的广泛应用Leslie Lamport因此获得了2013年度图灵奖。

Paxos协议提出只要系统中2f+1个节点中的f+1个节点可用,那么系统整体就可用并且能保证数据的强一致性,它对于可用性的提升是极大的,仍然假设单节点的可用性是P,那么2f+1个节点中任意组合的f+1以上个节点正常的可用性P(total)=,又假设P=0.99f=2P(total)=0.9999901494,可用性将从单节点的29提升到了59,这意味着系统每年的宕机时间从87.6小时降到0.086小时,这已经可以满足地球上99.99999999%的应用需求。

Leslie写的两篇论文:《The Part-Time Parliament》和《Paxos Made Simple》比较完整的阐述了Paxos的工作流程和证明过程,Paxos协议把每个数据写请求比喻成一次提案(proposal),每个提案都有一个 独立的编号,提案会转发到提交者(Proposer)来提交,提案必须经过2f+1个节点中的f+1个节点接受才会生效,2f+1个节点叫做这次提案的投 票委员会(Quorum),投票委员会中的节点叫做AcceptorPaxos协议流程还需要满足两个约束条件: aAcceptor必须接受它收到的第一个提案;b)如果一个提案的v值被大多数Acceptor接受过,那后续的所有被接受的提案中也必须包含v v值可以理解为提案的内容,提案由一个或多个v和提案编号组成)。

Paxos协议流程划分为两个阶段,第一阶段是Proposer学习提案最新状态的准备阶段;第二阶段是根据学习到的状态组成正确提案提交的阶段,完整的协议过程如下:

阶段 1.

1) Proposer选择一个提案编号,然后向半数以上的Acceptors发送编号为 n prepare请求。

2) 如果一个Acceptor收到一个编号为prepare请求,且 n 大于它已经响应的所有prepare请求的编号,那么它就会保证不会再通过(accept)任何编号小于 n 的提案,同时将它已经通过的最大编号的提案(如果存在的话)作为响应。

阶段 2.

1) 如果Proposer收到来自半数以上的Acceptor对于它的prepare请求(编号为n )的响应,那么它就会发送一个针对编号为 n value值为 v 的提案的accept请求给Acceptors,在这里 v 是收到的响应中编号最大的提案的值,如果响应中不包含提案,那么它就是任意值。

2) 如果Acceptor收到一个针对编号的提案的accept请求,只要它还未对编号大于 n prepare请求作出响应,它就可以通过这个提案。

 

        用时序图来描述Paxos协议如图3所示:

3Paxos协议流程的时序图

上述Paxos协议流程看起来比较复杂,是因为要保证很多边界条件下的协议完备性,譬如初试值为空、两个Proposer同时提交提案等情况,但 Paxos协议的核心可以简单描述为:Proposer先从大多数Acceptor那里学习提案的最新内容,然后根据学习到的编号最大的提案内容组成新的 提案提交,如果提案获得大多数Acceptor的投票通过就意味着提案被通过。由于学习提案和通过提案的Acceptor集合都超过了半数,所以一定能学 到最新通过的提案值,两次提案通过的Acceptor集合中也一定存在一个公共的Acceptor,在满足约束条件b时这个公共的Acceptor时保证 了数据的一致性,于是Paxos协议又被称为多数派协议。

Paxos协议的真正伟大之处在于它的简洁性,Paxos协议流程中任何消息都是可以丢失的,一致性保证并不依赖某个特殊消息传递的成功,这极大的简化了 分布式系统的设计,极其匹配分布式环境下网络可能分区的特点,相比较在Paxos协议之前的“两阶段提交(2PC)”也能保证数据强一致性,但复杂度相当 高且依赖单个协调者的可用性。

那既然Paxos如此强大,那为什么还会出现ZAB协议?

ZAB协议

<!--[if !supportLists]-->1)       <!--[endif]-->Paxos协议虽然是完备的,但要把它应用到实际的分布式系统中还有些问题要解决:

在多个Proposer的场景下,Paxos不保证先提交的提案先被接受,实际应用中要保证多提案被接受的先后顺序怎么办?

2) Paxos允许多个Proposer提交提案,那有可能出现活锁问题,出现场景是这样的:提案 n在第二阶段还没有完成时,新的提案n+1的第一阶段prepare请求到达Acceptor,按协议规定Acceptor将响应新提案的prepare 请求并保证不会接受小于n+1的任何请求,这可能导致提案n将不会被通过,同样在n+1提案未完成第二阶段时,假如提案n的提交者又提交了n+2提案,这 可能导致n+1提案也无法通过。

3) Paxos协议规定提案的值v只要被大多数Acceptor接受过,后续的所有提案不能修改值v,那现实情况下我还要修改v值怎么办?

 

ZooKeeper的核心算法ZAB通过一个简单的约束解决了前2个问题:所有提案都转发到唯一的Leader(通过Leader选举算法从 Acceptor中选出来的)来提交,由Leader来保证多个提案之间的先后顺序,同时也避免了多Proposer引发的活锁问题。

ZAB协议的过程用时序图描述如图4所示,相比Paxos协议省略了Prepare阶段,因为Leader本身就有提案的最新状态,不需要有提案内容学习的过程,图中的Follower对应Paxos协议中的AcceptorObserver对应Paxos中的Learner
 
 4ZAB协议的工作过程 <!--[endif]-->

ZAB引入Leader后也会带来一个新问题: Leader宕机了怎么办?其解决方案是选举出一个新的Leader,选举Leader的过程也是一个Paxos提案决议过程,这里不展开讨论。

那如何做到提案的值v可以修改呢?这不是ZAB协议的范畴,研究ZooKeeper源码后发现它是这么做的:ZooKeeper提供了一个znode的概 念,znode可以被修改,ZooKeeper对每个znode都记录了一个自增且连续的版本号,对znode的任何修改操作(create/set /setAcl)都会促发一次Paxos多数派投票过程,投票通过后znode版本号加1,这相当于用znode不同版本的多次Paxos协议来破除单次 Paxos协议无法修改提案值的限制。

从保证一致性的算法核心角度看ZAB确实是借鉴了Paxos的多数派思想,但它提供的全局时序保证以及ZooKeeper提供给用户可修改的znode Paxos在开源界大放异彩,所以ZAB的价值不仅仅是提供了Paxos算法的优化实现,也难怪ZAB的作者一直强调ZABPaxos是不一样的算 法。

总结

CAP理论告诉我们在分布式环境下网络分区无法避免,需要去权衡选择数据的一致性和可用性,Paxos协议提出了一种极其简单的算法在保障数据一致性时最 大限度的优化了可用性,ZooKeeperZAB协议把Paxos更加简化,并提供全局时序保证,使得Paxos能够广泛应用到工业场景。

参考资料

CAP 理论》: http://en.wikipedia.org/wiki/CAP_theorem

The Part-Time Parliament》:http://courses.csail.mit.edu/6.897/fall04/papers/Lamport/lamport-paxos.pdf

Paxos Made Simple》:http://dsdoc.net/paxosmadesimple/index.html

ZAB协议》:http://blog.csdn.net/bruceleexiaokan/article/details/7849601

《关于ZAB》:https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab+in+words

ZooKeeper的一致性协议:ZAB》:http://blog.csdn.net/chen77716/article/details/7309915

  • 大小: 16.6 KB
  • 大小: 18.5 KB
  • 大小: 5.2 KB
  • 大小: 209.9 KB
  • 大小: 1.4 KB
  • 大小: 666 Bytes
分享到:
评论

相关推荐

    浅谈分布式事务实现技术及应用场景探讨.pdf

    "浅谈分布式事务实现技术及应用场景探讨" 分布式事务是指在分布式系统中,多个节点之间的数据访问和更新操作集合,需要保证事务的原子性、一致性、隔离性和持久性。随着软件系统支持用户数的不断提高,对其架构的...

    浅谈分布式锁

    随着互联网公司业务的不断扩展和技术的进步,分布式系统的数据量和业务复杂性大幅增加,分布式锁在处理数据一致性问题上显得尤为重要。 CAP理论指出,任何分布式系统无法同时满足一致性(Consistency)、可用性...

    浅谈分布式数据库系统架构.pdf

    系统采用全局事务管理集群来保证分布式事务的一致性,通过集群快照等新技术来解决分布式系统中数据一致性的问题。 分布式数据库系统架构通常包含以下关键组件: - 数据库驱动集群:集成在应用中,与应用部署在一起...

    浅谈分布式存储系统架构设计.pdf

    分布式存储系统则以其高资源利用率、高效存储管理、高性能、高可靠性和可用性以及标准化接口等优势,成为了理想的解决方案。 分布式存储系统的核心在于其架构设计。本文中提到的分布式文件存储系统是一种基于通用...

    浅谈分布式数据库系统的设计与优化.pdf

    分片方法必须确保可以从各个局部数据库片段重建全局数据库,这样即使在分布式系统的一部分出现问题时,整个系统依然可以完整地重建数据。 3. 不相交性准则。对于水平分片,要求数据片段间不相交,确保每个数据项只...

    浅谈分布式内存数据库系统设计.pdf

    分布式内存数据库系统设计与传统数据库系统设计存在较大差异,需要针对分布式特性,考虑数据一致性、备份、容错和负载均衡等问题。设计时不仅需要创新性的算法和技术,还要考虑如何充分利用网络带宽和内存资源,以...

    浅谈分布式数据库架构.pdf

    这种架构可以有效避免集中式架构的性能瓶颈,并提高系统的可用性与扩展性。分布式数据库可以分为全局外层、全局概念层、局部概念层和局部内层四层结构。全局外层负责处理客户端的请求,全局概念层对全局数据库进行...

    浅谈分布式数据库的数据存储.pdf

    为了系统的可靠性,需要有数据的多个副本,但同时也会带来一致性维护和系统总开销增加的问题。因此,进行分布式设计时的一个重要原则是使数据和应用程序的本地性尽可能高,即应用数据尽可能本地化以减少通信成本。...

    浅谈分布式数据库中数据分片与分配关系的比较.pdf

    分布式数据库是计算机数据库技术发展的一种重要分支,其核心在于将数据库的存储和管理分散到多个物理节点上,以实现高性能、高可用性和易于扩展的目的。分布式数据库与集中式数据库相比,在数据分片与分配上具有显著...

    浅谈常用的分布式事务选型

    ### 分布式事务选型详解 #### 一、引言 在分布式系统中,随着业务需求的...而对于对系统可用性要求较高的场景,则可以考虑使用TCC或Saga等技术。在实际应用中,还需要综合考虑系统性能、成本等因素,做出合理的选择。

    浅谈PowerBuilder分布式技术在系统开发中的应用.pdf

    例如,在需要处理大量并发请求的电子商务平台、大型企业应用或者需要高可用性和负载均衡的云计算服务中,分布式系统可以确保服务的高响应速度和稳定性,同时提高数据的安全性。通过将系统部署在多个服务器上,分布式...

    浅谈Redis在分布式系统中的协调性运用

    在分布式系统中,协调性是确保各个节点之间正确协作的关键因素。...然而,值得注意的是,虽然Redis提供了很多便利,但在设计分布式系统时,仍需结合实际场景,权衡性能、可用性和复杂性,选择最适合的协调方案。

    浅谈CAS在分布式ID生成方案上的应用

    在分布式系统中,各个节点之间需要频繁地交换数据和状态,为了确保数据的一致性和完整性,常常需要为每一笔交易或者操作分配一个全局唯一的标识符(ID)。这种ID通常被称为分布式ID,它对于分布式系统的正常运行至关...

    浅谈J2EE框架和分布式网络管理.pdf

    2. 可伸缩性:J2EE通过其容器提供一种机制支持分布式应用系统的可伸缩性。例如,通过提供组件事务支持、数据库连接、生命周期管理等服务,J2EE容器能够让应用系统在没有修改代码的情况下提升性能和可伸缩性。 3. 高...

    postgresql高可用

    通常用“几个9”来表示系统可用性的百分比,例如: - **90% (1个9)**:每年允许停机时间为36.5天。 - **99% (2个9)**:每年允许停机时间为3.65天。 - **99.9% (3个9)**:每年允许停机时间为8.76小时。 - **99.99% ...

    浅谈基于Postgres-XL的分布式地质大数据集群架构.pdf

    分布式系统的难点在于如何保证数据的一致性、系统的可用性和容错性。 在分布式地质大数据集群架构中,Postgres-XL扮演了重要的角色。Postgres-XL由多个PostgreSQL数据库实例组成,通过整合各个实例的资源,提供一个...

    浅谈分布式锁的几种使用方式(redis、zookeeper、数据库)

    分布式锁是一种在分布式系统中确保同一资源在同一时刻只被一个客户端使用的机制,它解决了多节点并发访问共享资源的问题。在微服务和云架构中,分布式锁是不可或缺的组件,能够防止数据不一致性和并发问题。本文将...

    浅谈oracle rac和分布式数据库的区别

    - 分布式数据库:在分布式系统中,由于数据分布在不同节点,事务的ACID(原子性、一致性、隔离性、持久性)属性需要跨节点协调,可能引入两阶段提交等复杂机制,以确保数据一致性,这可能影响性能。 3. 故障恢复和...

    浅谈互联网架构.pdf

    在数据的高可用性方面,CAP原理是核心概念,它指的是在分布式系统中,一致性(Consistency)、可用性(Availibility)、分区容错性(PartitionTolerance)三者不可兼得,设计时需根据实际业务需求进行取舍。...

Global site tag (gtag.js) - Google Analytics