Google云计算原理和应用之分布式锁服务Chubby

Chubby是Google设计的提供粗粒度锁服务的一个文件系统，它基于松耦合分布式系统，解决了分布的一致性问题。通过使用Chubby的锁服务，用户可以确保数据操作过程中的一致性。不过值得注意的是，这种锁只是一种建议性的锁（Advisory Lock）而不是强制性的锁，这种选择系统具有更大的灵活性。
GFS使用Chubby选取一个GFS主服务器，Bigtable使用Chubby指定锁一个主器并发现，控制与其相关的子表服务器。除了最常用的锁服务之外，Chubby还可以作为一个稳定的存储系统存储系统存储包括元数据在内的小数据。同时Google内部还使用Chubby进行名字服务（Name Server)。本节首先要介绍Paxos算法，因此Chubby内部一致性问题的实现用到了Paxos算法;然后围绕Chubby系统的设计和实现展开讲解。

1.Paxos算法
Paxos算法是Leslie Lamport最先提出的一种基于消息传递（Messages Passing）的一致性算法，用于解决分布式系统中的一致性问题。在目前所有的一致性算法中，该算法最常用且被认为是最有效的。
简单地说，分布式系统的一致性问题，就是如何保证系统中初始状态相同的各个节点在执行相同的操作序列时，看到的指令序列是完成一致的，并且最终得到完全一致的结果。怎么才能保证在一个操作序列中每个步骤仅用一个值呢？一个最简单的方案在分布式系统中设置一个专门节点，在每次需要进行操作之前，系统的各个部分向它发出请求，告诉该节点接下来系统要做什么。该节点接受第一个到达的请求内容作为接下来的操作，这样就能够保证系统只有一个唯一的操作序列。但是这样做也有一个很明显的缺陷，那就是一旦这个专门节点失效，整个系统就很可能出现不一致。为了避免这种情况，在系统中必然要设置多个专门节点，由这些节点来共同决定操作序列。针对这种多节点决定操作系列的情况，Lamport提出了Paxos算法。在他的算法中节点被分成了三种类型：proposers,acceptors和learners。其中proposers提出决议（value,实际上就是告诉系统接下来该执行哪个指令），acceptors批准决议，leaners获取并使用已经通过的决议。一个节点可以兼有多重类型。在这种情况下，满足以下三个条件就可以保证数据的一致性。
（1）决议只有在被proposers提出后才能批准。
（2）每次只批准一个决议。
（3）只有决议确定被批准后learners才能获取这个协议。
为了满足上述三个条件（主要是第二个条件）,必须对系统有一些约束条件。Lamport通过约束条件的不断加强，最后得到了一个可以实际运用到算法中的完整约束条件。那么，如何得到这个完整的约束条件。那么，如何得到这个完整的约束条件呢？在决议的过程中，proposers将决议发送给accpetors,acceptors对决议进行批准，批准后的决议才能成为正式的决议。从集合论的观点来看，两组“多数派”（Majority）至少有一