概述

介绍如下内容:

  • 分布式锁服务 Chubby
  • Paxos 算法

分布式锁服务 Chubby

Chubby 是 Google 设计的提供粗粒度锁服务的一个文件系统,它基于松耦合分布式系统,解决了分布的一致性问题。通过使用Chubby的锁服务,用户可以确保数据操作过程中的一致性。不过值得注意的是,这种锁只是一种建议性的锁(Advisory Lock)而不是强制性的锁(Mandatory Lock),这种选择使系统具有更大的灵活性。

GFS 使用 Chubby 选取一个 GFS 主服务器,Bigtable 使用 Chubby 指定一个主服务器并发现、控制与其相关的子表服务器。除了最常用的锁服务之外,Chubby 还可以作为一个稳定的存储系统存储包括元数据在内的小数据。同时 Google 内部还使用 Chubby 进行名字服务(Name Server)。

图片加载失败

基本架构

图片加载失败基本架构

图片加载失败系统设计

图片加载失败

文件系统

图片加载失败

图片加载失败

通信协议

图片加载失败

ACL 机制

图片加载失败

Paxos 算法

Paxos 算法是 Leslie Lamport 最先提出的一种基于消息传递(Messages Passing)的一致性算法,用于解决分布式系统中的一致性问题。在目前所有的一致性算法中,该算法最常用且被认为是最有效的。

一致性问题

为了实现集群的高可用性,用户的数据往往要多重备份,多个副本虽然避免了单点故障,但同时也引入了新的挑战。
假设有一组服务器保存了用户的余额,初始是 100 块,现在用户提交了两个订单,一个订单是消费 10 元,一个订单是充值 50 元。由于网络错误和延迟等原因,导致一部分服务器只收到了第一个订单(余额更新为90元),一部分服务器只收到了第二个订单(余额更新为 150 元),还有一部分服务器两个订单都接收到了(余额更新为 140 元),这三者无法就最终余额达成一致。这就是一致性问题。
一致性算法并不保证所有提出的值都是正确的(这可能是安全管理员的职责)。我们假设所有提交的值都是正确的,算法需要对到底该选哪个做出决策,并使决策的结果被所有参与者获悉。
一致性算法并不保证所有节点中的数据是完全一致的,但它能保证即使一小部分节点出现故障,仍然能对外提供一致的服务(客户端无感知)

  1. 保证分布式系统的一致性。
  2. 在分布式系统中设置一个专门节点,接受其他节点的请求并告诉它们下一步要做什么。
  3. 如果只接受第一个到达的请求显然可以保证系统的一致性。
  4. 但是如果这个节点失效则无法保证系统的一致性。
  5. 所以需要多个专门节点。
  6. Paxos 算法。在他的算法中节点被分成了三种类型:Proposers、Acceptors 和 Learners。
    • Proposers:负责提出决议。
    • Acceptors:负责批准决议。
    • Learners:负责获取并使用已经通过的决议。
  7. 一个节点也可以兼有多重类型。

系统约束条件

  1. 决议只有在被 proposers 提出后才能批准。

  2. 每次只批准一个决议。

  3. 只有决议确定被批准后 learners 才能获取这个决议。

图片加载失败


我们虚拟一个一致性问题的场景:有一个用户小绿,现在要对他的姓氏信息进行修改,此时有多个不同的议案被提出,如何就最终的结果达成一致。

首先看一下下面这种最简单的情况:A1 接受了 Pa 的议案“赵”,A2 和 A3 接受了 Pb 的议案“钱”,那么最终小绿应该姓什么?

图片加载失败

答案很简单:超过半数的的议案就是最终的选定值。小绿应该姓“钱”!在议案提交后,Pa 和 Pb 只要查询一下小绿姓氏,很容易就能查到 “钱”的数量超过半数,因此Pb的议案将会返回“成功”,Pa的议案将会返回“失败”。

P0:当集群中,超过半数的Acceptor接受了一个议案,那我们就可以说这个议案被选定了(Chosen)。

P0 已经是一个完备的一致性算法,保证了P0也就解决了一致性问题。但是 P0 的实用性不佳,一个议案想被半数以上的 Acceptor 接受是一件极其困难的事情!
看下面这种情况:A1,A2,A3 分别接受了“赵”,“钱”,“孙”,结果没有任何一个议案形成多数派,所有的议案都将返回“失败”。议案的数量越多,那议案被选定的概率就越低,这显然是没法容忍的。

图片加载失败


要解决这个问题,必须允许一个 Acceptor 接受多个议案,后接受的议案可以覆盖掉之前接受的议案。

如下图所示, A1 已经接受了“赵”,A2 已经接受了“钱”,此时 Pc 提出了“孙”,并被A1,A2,A3接受,这样就解决了无法形成多数派的问题。

图片加载失败

但现在又会面临下图中的新问题:A1,A2,A3 已经接受了“赵”,此时我们认为“赵”是被选定的,但此时偏偏Pb和Pc不识时务,Pb 向 A2 提出了“钱”,Pc 向 A3 提出了“孙”。这样就从一致性状态,又回到了不一致的状态…这显然破坏了一致性。

图片加载失败


Paxos 就是在上述背景下产生的,Paxos 要实现的目标的是:

T1.一次选举必须要选定一个议案(不能出现所有议案都被拒绝的情况)
T2.一次选举必须只选定一个议案(不能出现两个议案有不同的值,却都被选定的情况)

Paxos 算法的推导

首先,Paxos 算法的必须要能满足第一个条件:

P1:一个Acceptor必须接受它收到的第一个议案。

假设只有一个 Acceptor,只有一个 Proposer。如果 Acceptor 出于某些原因拒绝了 Proposer 的议案,那必然导致 Paxos 的目标 T1 无法达成。因此可以认为目标 T1 隐含了 P1。


在开始 P2 的推导的前,为了区分不同议案,需要先对每个 Proposer 的议案进行编号,编号时必须保证每个议案的编号具有唯一性(不讨论实现方法),而且编号是不断增大的。
Paxos 的目标 T2 隐含了 P2:

P2:如果一个值为v的议案被选定了,那么被选定的更大编号的议案,它的值必须也是v。

P2 很容易理解,除了其中的一个形容词更大编号的,这个形容词很扎眼,为什么只对更大编号的议案进行限制,更小的编号怎么办?
首先把“更大编号的”几个字换成“其他的”,我们称它为 P2S。那么 P2S 能否满足 Paxos 的目标?答案是肯定的。然后比较 P2 和 P2S,谁的约束更强?这得看“更小的编号”是怎么处理的,从论文后面的推演来看更小编号的议案绝对不允许被选定!!!因此满足P2的议案是P2S的一个子集。
显而易见,P2S 和 P2 都能满足 Paxos 目标。换句话说,能满足 Paxos 目标的办法很多,但我们只选其中一个办法就 OK 了。不过,要选最简单的办法(看完后面就知道了)。
总之,现在我们可以得出一个结论:
如果 P1 和 P2 都能够被满足,那么 Paxos 的两个目标就能够达成。如果你对上面这个结论没有异议,那么就说明你已经充分理解了 P1 和 P2。


接下来就需要想办法,如何才能满足 P2:议案在选定前,都要先被 Acceptor 接受,因此要满足 P2,我们只要满足下面的条件:

P2a:如果一个值为 v 的议案被选定了,那么 Acceptor 接受的更大编号的议案,它的值必须也是 v。

P2a 是 P2 的充分条件,但是 P2a 存在一个大麻烦:当一个议案被选定后,一部分 Acceptor 无法立刻获得通知。例如下图中 A1 和 A2 已经接受了“赵”,这时“赵”就被选定了,此时 Pb 向 A3 提出了一个议案“钱”,这是 A3 接受的第一个议案,为了满足 P1,A3 必须接受这个议案,此时就会导致 P2a 无法被满足了。

图片加载失败


为了解决上述的问题,我们想一下:要是此时不让 Pb 提出“钱”这个议案,而是提出“赵”这议案就万事大吉了。顺着这个思路,我们得到了 P2b:

P2b:如果一个值为 v 的议案被选定了,那么 Proposer 提出的更大编号的议案,它的值必须也是 v。

P2b 是一个比 P2a 更强的约束,也就是说 P2b 是 P2a 的充分条件,只要能满足 P2b,那 P2a 就自动满足。但 P2b 很难被满足,考虑下图这种情况,A1 接受了议案“赵”,A2 即将接受议案“赵”,此时 Pb 提出了一个议案“钱”,这种情况下我们又会遇到跟 P2a 完全相同的麻烦。

图片加载失败


很明显,要想满足 P2b,我们必需让 Proposer 拥有“预测未来”的能力,这听起来像在讲鬼故事,后面会想办法解决这一点。 在介绍如何“预测未来”之前,我们必须先确定 Proposer 在提出一个议案时,它的值该如何选取,因为取值的方法决定了“预测”的方法。
一个理所当然的取值方法:找到一个 Acceptor 的多数派的集合,集合内被接受的议案的值都是v,此时 Proposer 提出一个新的议案,议案的值必须也是v;如果没有这样的多数派集合,那 Proposer 就任意提。
这个取值方法,完全能符合 P2b,这是一目了然的,但问题出在 “预测”上,我们必须能预测到即将形成多数派的那个议案,如果有谁能做到那就真的是在讲鬼故事了。
Proposal 提出议案的正确姿势:

P2c:在所有 Acceptor 中,任意选取半数以上的 Acceptor 集合,我们称这个集合为S。Proposal 新提出的议案(简称 Pnew)必须符合下面两个条件之一:

  1. 如果 S 中所有 Acceptor 都没有接受过议案的话,那么Pnew的编号保证唯一性和递增即可,Pnew的值可以是任意值。
  2. 如果 S 中有一个或多个 Acceptor 曾经接受过议案的话,要先找出其中编号最大的那个议案,假设它的编号为 N,值为 V。那么 Pnew 的编号必须大于 N,Pnew 的值必须等于 V。

P2c 提出议案的规则有点复杂,它真的能满足 P2b 吗?至少看上去不是那么一目了然,接下来,上图,举例说明。

假设有一个议案(3,Va)提交后,这个议案成为了被 Acceptor 集群选定的第一个议案 ,那此时集群的状态可能会如下图所示:

图片加载失败

一共 5 个 Acceptor,有 3 个 Acceptor 接受了议案(3,Va),刚刚过半。此时有一个编号为 4 的议案要提出,根据 P2c 的规则 2,首先选一个过半的集合,就选上图中蓝色线圈出来的 A3,A4,A5 好了(任意选),这个集合中编号最大的议案是(3,Va),因此新提出的议案必定为(4,Va)。符合 P2b。
议案(4,Va)提出后,集群的状态可能是下面这样:

图片加载失败

此时再提出编号为 5或 6,7,8,9,10 的议案,这个议案的值必定也是 Va(不信的话请举出反例),符合 P2b。依此类推······

由此可证,P2c 是能够满足 P2b 的!!!

想想看 P2,P2a,P2b 中为什么一定要有“更大编号的”这几个扎眼的字眼,此时你应该能有一点感觉了,可能你会把它理解成“后提出的”,如果你是这样理解的话,请往下看。

有些童鞋肯定早就已经想到了:当议案(3,Va)提交后,这个议案成为了被 Acceptor 集群选定的第一个议案,此时集群的状态有没有可能是下面这样?

图片加载失败

注意,这时议案(4,Vb)才是集群当中的编号最大的议案,要是这样就糟糕了!当我们提出编号为 5 的议案时,它的取值就有可能是 Vb,导致无法满足 P2b。

为了保证不出现这种情况,就要用到前面提到的“预测未来”的能力。跟P2c的议案规则相配套的,需要预测的未来是:

当一个议案在提出时(即使已经在发送的半路上了),它必须能够知道当前已经提出的议案的最大编号。

这样的话,议案(3,Va)提交时,就会知道有一个(4,Vb)的议案已经提交了,然后将自己的编号改成5或更大编号提交,一切就完美了。

但是你知道的,我们并不可能真的预测未来,换个思路,议案肯定是要提交给 Acceptor 的,只要由 Acceptor来保证议案编号的顺序就 OK 了。于是有:

议案(n,v)在提出前,必须将自己的编号通知给半数以上的 Acceptor。收到通知的 Acceptor 将 n 跟自己之前收到的通知进行比较,如果 n 更大,就将n确认为最大编号。当半数以上 Acceptor 确认 n 是最大编号时,议案(n,v)才能正式提交。

两个编号不同的议案,不可能同时被确认为最大编号,证明略。

但是实际环境上,上面的条件还不足以保证议案被接受的顺序,比如议案(n,Va)被确认为最大编号后,开始向 Acceptor 发送,此时(n+1,Vb)提出,由于网络速度的原因,(n+1,Vb)可能比(n,Va)更早被 Acceptor 接收到。

因此 Acceptor 收到一个新的编号 n,在确认 n 比自己之前收到的编号大时,必须做出承诺(Promise):不再接受比 n 小的议案。

这个承诺会导致部分漏网之鱼(在发送途中被抢走最大编号的议案),无法形成多数派。

例如下图所示:有一个在途的议案(1,Va),当A2和A3对议案(2,Vb)做出承诺的同时,(1,Va)就失去了形成多数派的权利。

图片加载失败

至此,我们就形成了一个完整的算法(具体实现请自行搜索 PhxPaxos)。

总结

在这些约束条件的基础上,可以将一个决议的通过分成以下两个阶段。

  1. 准备阶段:Proposers 选择一个提案并将它的编号设为 n,然后将它发送给 acceptors 中的一个“多数派”。Acceptors 收到后,如果提案的编号大于它已经回复的所有消息,则 Acceptors 将自己上次的批准回复给 Proposers,并不再批准小于 n 的提案。

  2. 批准阶段:当 Proposers 接收到 Acceptors 中的这个“多数派”的回复后,就向回复请求的 Acceptors 发送 Accept 请求,在符合 Acceptors 一方的约束条件下,Acceptors 收到 Accept 请求后即批准这个请求。

图片加载失败

参考文章