Google Chubby中的Paxos

本人是一篇转载文章,并没有对Paxos做出详细的讲解,但通过其对Google Chubby的具体实现流程的解读,应该能让觉得Paxos算法晦涩难懂同学有所领悟。

PS:我个人觉得理解Paxos算法的关键不在于其协调机制的模拟,而在于理解每个节点都可以同时是多个角色。

原文链接:http://crackcell.javaeye.com/blog/609635

另附上Paxos中文wiki:http://zh.wikipedia.org/zh-cn/Paxos%E7%AE%97%E6%B3%95

Google Chubby是一个分布式锁服务,能存储小文件。GFS和big table用它来进行分布式协作、储存元数据。Chubby是一致性算法Paxos很好的一个实例。相对于Leslie Lamport老先生等大牛学术上的描述,Chubby给出了一个更贴近实战的描述。我这里将最要注意力集中在paxos上。这里的讨论不考虑拜占庭失效问题。

Chubby

  • 集群由若干独立的replica构成,replica在结构和能力上相互对等
  • replica用paxos来保持log的一致性
  • replica都有可能离线,然后重新上线。重新上线后,需要保持与其它节点数据的一致

replica的结构

replica有个2个大件:容错的数据库 和 容错的日志。日志部分,每个replica都存有一份本地数据。

replica提交一次value的过程

chubby中的paxos

大体步骤是这样的:

  1. 选举一个replica成为coordinator
  2. coordinator选择一个value,广播给所有的replica,这个消息称为accept。replica收到消息后,可以选择同意或者拒绝,并将决定告诉coordinator
  3. 当coordinator收到多数replica的同意确认后,就认为一致性达到了,并向相关replica发送commit消息

coordinator失效

因为coordinator可能失效,所以paxos允许同时有多个coordinator。多个replica可以在同时决定称为coordinator并在任意时间执行算法。但是在系统,我们还是要尽量避免coordinator的轮转,因为这样会延缓达到一致。这种灵活的选举制度意味着同时会有不同的replica决定成为coodinator并提交不同的value。cubby就用了paxos中的2种机制来解决:1)给coodinator分配序号 2)限定coodinator能选择的value。

具体这样来实现:

每个replica都记录了它知道的coodinator中最大的编号。这样,它就通过发送过来的accept请求带的编号,拒绝旧coodinator的请求。

当一个replica想成为coordinator的时候,它给自己分配一个唯一的序号。chubby的作者举例了一个序号生成的方法:

有n个replica,每个有一个id,0 <= id <= n - 1。每个replica的序号是 N * n + id,N的初始值是0。
  1. 然后将序号广播给其它replica,这称之为propose消息。
  2. 其它replica收到propose消息,并将自己之前知道的最大序号返回,这称之为promise消息。如果propose消息中的序号是最大的,replica会承诺不再同意旧coodinator发送的accept消息
  3. 如果多数的replica回复的最大的序号小于生成的序号,replica就成为一个coodinator。

paxos算法强迫新的coodinator必须选择和前任相同的value。在2中的promise消息中,包含了每个节点上一次接收到的消息。如果没有收到任何promise消息中包含的value,coordinator可以自行选择value。

有一个常见的优化,选择一个replica作为coordinator之后,就长期不变了,暂称之为master。

对集群不断执行paxos算法,就能达到一致性。在Chubby中,提交一次value到log就触发一次paxos执行。

磁盘失效

  • chubby在文件中加入校检合,来探测文件损坏。
  • 新replica节点在启动的时候,会在GFS存一个标记,表示自己的是新的。当replica启动时,发现自己磁盘是空的,它就去检测GFS中的marker。这样来区分新replica和磁盘不可访问的情况

Master租约

当有多Master同时存在的时候,会出现master间数据不一致的情况。这样在master上的读,就可能读到脏数据。chubby的解决方法是只要有一个master拥有租约,其它的replica就不能成功地提交value。chubby的replica在租约的有效期内,默认拒绝其它replica的请求。master间断性地提交空的”心跳“value到Paxos集群来刷新租约。

anyShare分享此文章的同学,将有机会送我iphone5!
          

无觅相关文章插件,快速提升流量

  1. Pingback: Chubby related