半步多 玄玉V笔记

分布式一致性01之算法理论

2020-08-22
玄玉

分布式一致性算法

Paxos算法

Google Chubby 的作者 Mike Burrows 说过:这个世界上只有一种一致性算法,那就是 Paxos,其它算法都是残次品

分布式系统中的节点通信存在两种模型:共享内存和消息传递

基于消息传递通信模型的分布式系统,不可避免会发生进程变慢被杀死、消息延迟、丢失、重复等问题

Paxos 是一种基于消息传递且具有高度容错性的一致性算法(即在以上异常的情况下,仍能保持一致性的协议)

在 Paxos 中,分以下三种角色:

  • Proposer:提议者,用来发出提案 proposal(提案信息包括提案编号 proposal id 和提议的值 value)
  • Acceptor:接受者,参与决策,可以接受或拒绝提案(当提案被超过半数的 Acceptor 接受后,即为被批准)
  • Learner:学习者,不参与决策,只学习被选定的提案

换句话说,Paxos 算法就跟议会制一样,少数服从多数(即超过半数)

一个分布式算法有两个最重要的属性:活性(liveness)和安全性(Safely)

简单来说,liveness 是指那些最终一定会发生的事情,Safely 是指那些需要保证永远都不会发生的事情

而 Paxos 算法的 liveness 就体现在:保证最终有一个提案会被选定

Safety 则是这么约束的:

  1. 决议(value)只有在被 proposer 提出后才能被批准
  2. 在一次 Paxos 算法的执行实例中(即一次投票过程中),只批准(chose)一个 value
  3. learner 只能获得被批准(chosen)的 value

liveness和 Safety 组合的结果就是:最终有且只有一个被提出的提案被选定

上面说的是原始的 Paxos 算法(Basic-Paxos),它只能对一个 value 形成决议

实际应用中几乎都需要连续确定多个值,而且希望效率更高,于是有了 Multi-Paxos

其实 Basic-Paxos 也只是一个逻辑概念,落地还是挺困难的

实际中,所有的 Acceptor 都可以成为 Proposer(即都可以发起投票),甚至会出现两个 Proposer 同时发起一个相同的提案

这时怎么确保提案的发起和执行是有顺序的呢?(这是分布式场景中的一个尖锐问题:缺乏全局时钟,也就是无法保证全局顺序)

下文提到的 ZooKeeper 就解决了这个问题

zk 虽然也用了类似概念,不过它对 Paxos 做了一个工业实践:基于 multi-paxos 算法做了改进

zk 构造了 leader-follower 模式,即映射到 zk 集群时,proposer 对应的就是 leader,acceptor 对应 follower,learner 对应 observer

即只有 leader 才能发起提案,follower 参与投票,observer 则被动接受(这里 leader 存在单点故障,所以又提供了 leader 选举机制)

Raft算法

它跟 ZAB 协议基本很相似,这是一个便于理解该算法的在线动画:http://thesecretlivesofdata.com/raft/

ZAB协议

zk 基于 multi-paxos 提供了 ZAB(Zookeeper Atomic Broadcast)协议

ZAB 协议需要确保那些已经在 leader 服务器上提交的事务最终被所有服务器都提交

ZAB 协议需要确保丢弃那些只在 leader 服务器上被提出的事务

如果让 leader 选举算法能够保证新选举出来的 leader 服务器拥有集群中所有机器最高事务编号(ZXID)的事务 proposal

那么就可以保证这个新选举出来的 leader 一定具有所有已经提交的提案

ZAB 两种基本的模式:崩溃恢复和消息广播

zk 的底层工作机制,就是依靠 ZAB 实现的(实现崩溃恢复和消息广播两个主要功能)

补充:关于拜占庭将军问题,严格来说,Paxos 没有解决,但是 ZAB 解决了(区块链也解决了)

抽屉原理

也叫狄利克雷抽屉原理(又名鸽巢原理、鸽笼原理)

它有两种简单的表述法:

  1. 若有 n 个笼子和 n+1 只鸽子,所有的鸽子都被关在鸽笼里,那么至少有 1 个笼子有至少 2 只鸽子
  2. 若有 n 个笼子和 kn+1 只鸽子,所有的鸽子都被关在鸽笼里,那么至少有 1 个笼子有至少 k+1 只鸽子

我们对它变种一下

2 个抽屉,一个放了 2 个红苹果,一个放了 2 个青苹果。我们取出 3 个苹果,无论怎么取都至少有 1 个是红苹果

再引申一步,我们把红苹果看成更新了的有效数据,青苹果看成未更新的数据

也就是说不需要更新全部数据(并非全部是红苹果)就可以得到有效数据,当然我们需要读取多个副本完成(取出多个苹果)

换句话说,比如有一条数据,往 5 个节点里写入,只要有至少 3 个节点写入成功,我们就认为是写入成功了

读取时至少读取 3 个节点的数据,就一定能获取到刚才写入的最新的数据

这就很像 Quorum 机制了

Quorum机制

Quorum 机制是分布式场景中常用的,用来保证数据安全,并且在分布式环境中实现最终一致性的投票算法

这种算法的主要原理来源于抽屉原理,它最大的优势是既能实现强一致性,而且还能自定义一致性级别

它有 N、W、R 的三个概念:

  • N:复制的节点数,即一份数据被保存的副本数
  • W:写操作成功的节点数,即每次数据写入写成功的副本数(W 小于等于 N)
  • R:读操作获取最新版本数据所需的最小节点数,即每次读取成功至少需要读取的副本数

如图所示:客户端写入 data01、data02、data03、data04 四条数据

分别写入成功副本数为 2、3、4、5(有颜色代表写入成功,灰色代表仍为旧版本数据)

此时如果想要读取到这四条数据,则分别需要读取的副本数至少为 4、3、2、1

总结:只要保证 W + R > N 就一定能读取到最新数据(数据一致性级别完全可以根据读写副本数的约束来达到强一致性)

当 N 已经固定的前提下,我们来看以下三种情况:

  1. W=1,R=N(Write Once Read All)
    分布式环境中,只写一份数据,那么读时,就必须读取所有节点才能得到最新数据(写高效,但读效率低)
  2. R=1,W=N(Read Only Write All)
    分布式环境中,所有节点都同步完毕才能读,故读任意一个节点就能得到最新数据(读高效,但写效率低)
  3. W=Q,R=Q(Q=N/2+1)
    分布式环境中,写超过半数节点,那么读也超过半数节点,使得读写性能平衡(ZooKeeper就是这么干的)

CAP和BASE理论

CAP理论:一个分布式系统不可能同时满足 C、A、P 三个需求

  • C:Consistency,强一致性(分布式环境中多个数据副本保持一致)
  • A:Availability,高可用性(服务一直可用,用户的每个请求都能在有限时间内返回成功或失败)
  • P:PartitionTolerance,分区容错性(网络分区或故障时,依然能够读取到最新数据,并保证服务可用)

网络分区:由于网络失败或延迟导致一部分节点与大部队失去联系,这一部分节点组成了一个小集群
     这个小集群也会进行选举,最终就会出现一个带 leader 的小集群,这样一个集群就变成了两个集群
     也就形成了网络分区(俗称脑裂),这种局部小集群就会引发各种数据一致性、数据超时等问题

既然三个不能同时满足,那就三选二

  1. 放弃 P:这就等于放弃了分布式,变成了单机环境(MySQL 就是放弃了 P),所以分布式系统都会保证 P
  2. 放弃 A:网络分区或其他故障时,服务需要等待一段时间,等待时间内无法对外提供服务,即服务不可用
  3. 放弃 C:实际是指放弃数据的强一致性,而保留最终一致性,具体多久达到数据同步取决于存储系统的设计

  • 对于单机软件,因为不用考虑 P,所以肯定是 CA 型,比如 MySQL
  • 对于分布式软件,因为一定会考虑 P,所以只能在 A 和 C 之间权衡,做到服务基本可用,并且数据最终一致性即可

所以产生了 BASE 理论:即使无法做到强一致性,但每个应用可以根据自身业务特点,采用适当的方式来使系统达到最终一致性

  • Basically Availiable(基本可用):分布式系统出现故障时,允许损失部分可用性,即保证核心可用
  • Soft State(软状态):允许系统存在中间状态,而该中间状态不会影响系统整体可用性
               分布式存储中一般一份数据至少会有三个副本,允许副本同步的延迟就是软状态的体现
  • Eventually Consistent(最终一致):系统中的所有数据副本经过一定时间后,最终能够达到一致的状态

注意:ACID 和 BASE 代表两种截然相反的设计理念,ACID 注重一致性,是传统关系型数据库的设计思路,BASE 关注高可用性


相关文章

Content