分布式基础-Paxos、Chubby/Zookeeper

一、Paxos算法

1. 概念
考虑到消息延迟、重发、丢失、网络分化,结点宕机/重启等多类异常,分布式异步环境下要参与各方对某个事物达成一致理解往往比较困难. Paxos是分布式环境下一种共识(Consensus)算法/机制,其问题模型可以描述为:

有多个提议者(Proposer)提出议案(Proposal),有多个决策者(Acceptor),每个决策者可投票决定是否接受(accept)某个议案,当某个议案被大多数(Majority,如半数以上)决策者一致接受后,称该议案被通过,本轮投票结束. Paxos的目的就是保证每轮投票(一次Paxos实例)在大多数决策者存活的前提下,一定能最终产生一致通过的议案。所有关注投票结果的观察者(Learner)能及时获知最终议案.

在分布式系统中,参与者一般是以单机进程为单位,上述“议案”的含义很广泛,如可以是某个值,也可以是某些操作,总之是需要参与各方达成一致的任何内容. 上述3种角色(Proposer/Acceptor/Learner)是为了方便以及通用地描述问题区分的,实践中一般一个进程会同时担任多个角色,例如多个replica servers中选举primary的应用场景,每个server都发起提议自己成为primary(Proposer),处理来自其他peer的提案(Acceptor),以及要获取最终结果(Learner)来初始化自身状态.

由此例也可以看出Paxos不关心具体哪个议案被通过(很可能无关紧要,如谁当primary都一样),只确保最终某个被一致选中(如果出现多个primary,每个primary都去同步数据,则将产生致命错误).

Paxos的优势是完全的一致性(Consistency)和较高的可用性(Availability),即只要半数以上结点能继续工作就一定能产生一致的结果.

2. 算法
Paxos算法是为了解决上述问题严格推导出来的,其过程在Lamport的Paxos Made Simple一文中描述得非常简单明了,推荐参考,这里仅描述最终推导出的核心算法过程.

Paxos依赖两个条件:
(a) 全局唯一自增ID产生器,供每个Proposer给议案编号使用.
(b) 每个Acceptor要有持久化存储和重启后恢复相关状态的能力,以确保算法能在多数结点恢复后能继续.

(单个Paxos实例)算法过程:

阶段一: Prepare
1) Proposer:向所有(或足够多)的Acceptor发起一个Prepare请求,其中包含一个(Proposal)唯一编号N.
2) Acceptor:收到一个Prepare (N) 请求后
(a) 如果该Acceptor没有accept过任何Proposal, 则返回承诺不会再accept比N小的Proposal
(b) 否则返回其accept过的编号最大的Proposal(Number, Value),并且承诺不会再accept比N小的Proposal

阶段二: Accept
1) Proposer:收集到足够多的Acceptor的Prepare回复后
(a) 如果所有Acceptor都没accept过任何Proposal,则Proposer可以任意选取一个AnyValue,向所有(或足够多)的Acceptor发起Accept请求提议Proposal (N, AnyValue).
(b) 否则选择所有Acceptor返回的编号最大的Proposal的Value,向所有(或足够多)的Acceptor发起Accept请求提议Proposal (N, Value).
这里的N与Prepare阶段请求中的编号一致.
2) Acceptor:收到一个Accept请求的Proposal提议(N, V)后,如果没有承诺过不再accept比N小的Proposal,则可以accept该Proposal,并记录/更新相应状态,否则否决.

直观上看,Paxos就是多个Proposer不断尝试争抢占坑的过程,一旦谁先占到了多数坑位,就能将Value(提议内容)传播给后续更大编号(更高优先级)的提议,从而胜出.

Learner:
当Acceptor accept了某个Proposal后,可以及时通知所有Learner,由Learner判断当前是否已经产生了结果. 也可以选取一个或部分Learner做代表(Distinguished Learner),代表Leaner再去同步其他Learner,以减少消息量. 当丢包或其他网络问题时,也可以Learner主动查询Acceptor,但如果部分Acceptor挂掉,则Learner可能无法确定结果,此时Learner可以要求重新发起Paxos过程.

一种无法产生结果的情况:
理论上如果多个Proposer独立提出议案,可能出现通过不断提高Proposal编号相互抢占(否决)从而导致永远不出结果,如Proposer_A完成prepare阶段编号为n1, 此时Proposer_B也发起prepare并将编号提高的n2>n1,导致Proposer_A在Accept阶段被否决,而Proposer_A将编号提高的n3>n2继续尝试,又导致Proposer_B在Accept阶段被否决,接着Proposer_B又提高编号...

一个办法是可以选出一个Proposer代表(Distinguished Proposer),这样一定能产生结果.

实践:
Paxos的工程实现比较灵活,有多种优化方案和较大的权衡空间,具体和相关案例可以参考wiki paxos

二、 Chubby/Zookeeper

Chubby是Google开发的松散分布式环境下的锁服务,旨在提供高可用分布式锁和小文件存储系统,以及其上的事件通知机制。主要由多个lock server和client lib组成:
chubby_arch

以下逐点说下:

1. 全局一致和高可用
chubby/zk的 lock server之间通过paxos协议选举出master,再由master同步其上的更新,以达到每个chubby结点DB状态一致和整体高可用. 由于chubby集群本身的这些特性,依赖chubby/zk服务的客户系统也相当于在某种程度上间接拥有了一致性和高可用,不能完全传递的原因是,chubby/zk与client系统之间的网络分化问题仍然存在,而paxos只解决chubby/zk内部的网络问题. 这种情况下可以使用chubby/zk提供的lease机制来保证一致性,但牺牲了一定的可用性(如chubby需要等分配给client的lease超时才释放Lock).

2. 分布式锁
为什么需要分布式锁呢,考虑单机进程下的普通锁,如果多个进程要更新一共享资源,可以通过其加锁来实现互斥访问,如mutex、文件锁等等. 同样的在分布式环境下,不同物理节点上的进程也可能有类似的需求,而能提供分布式环境下资源锁的服务就叫分布式锁,如最简单的可以利用redis原子setkey操作(setne),只是redis集群的可靠性、一致性以及原始设计不如专业的chubby/zk.

另外单机环境下,加解锁等系统调用一般只有成功/失败两态,进程挂掉操作系统也会帮助接管。但分布式环境下要复杂得多,不能直接照搬单机锁编程的逻辑,举个例子:

结点A从某锁服务获取到写锁后,对某个资源E发起操作R1,正常情况下在R1完成A释放lock之前,其他结点无法操作E. 但假如R1发出去后A挂掉,此时锁服务为了不永久阻塞,会选择在某个时候(如通过会话/lease超时机制)将A锁释放,接着B获取到E的锁并发起操作R2,但假如R1此时正好延迟到达了,那么将和R2发生冲突. 毕竟分布式环境下结点挂掉和延迟丢包等是常态,所以并不是说拿到了锁就可以像单机那样放心操作了.

Chubby的解决办法是,A能获取到当前锁ID,并由R1携带,负责操作E的服务收到R1后再去Chubby验证一遍ID,如果此时锁已经被B拿到则ID会验证失败,因而延迟到达的R1不会被执行. 如果E不具备验证的能力,则另一个折中方案是A的锁异常释放后在一小段时间内禁止其他人如B来加锁,让A的旧包尽可能地在网络中消耗掉. ID可以简单地设计为(资源ID+加锁次数)

Chubby重新选主后会尽量迁移会话等状态到新的master上,也包括保持锁的原来状态,达到failover发生时对外界透明的效果.

2. 小文件存储系统和事件通知
Chubby锁是用类unix的路径标识的,同时每个路径node可以存储少量文件数据和维护相关元数据。同时client可以监听某个node上的事件,如文件内容变更,目录子节点变更等。Chubby主要考虑高可用和一致性问题,其次是性能和存储容量,因而DB容量一般比较小,便于快速同步和备份,所以存储的内容主要是元数据信息如client系统的primary地址、服务参数、各种配置信息等.

3. 带lease的分布式缓存
client提供带lease的分布式cache,以降低对master的读请求压力,client要更新缓存时write through到master,后者再发cache失效命令给各相关client. 由于这个特性chubby在google经常被用于名字服务如DNS等,解决了后者设置cache TTL大小不确定的问题.

4. 应用实例
如GFS从多个replica-servers中选primary即master-server,所有replica-server尝试Lock某个chubby锁文件,其中一个获取成功后成为primary,并将其地址信息写入锁文件中,chubby会将该文件变更事件通知给其他replica和关注该文件的client,各自读取到新primary地址并好后续准备. 此后客户系统的primary一般通过lease机制维持其身份,一旦primary挂掉或其lease不够则所有客户系统server重新通过chubby锁竞争成为新primary.

除了选主外BigTable等系统还利用chubby存储元数据和Root索引等位置信息.

另外Chubby也常用作动态配置库,通过事件机制下发配置更新.

发表评论

电子邮件地址不会被公开。