【云计算 复习】第2节 分布式锁服务Chubby和Paxos算法（含大题）

一、Chubby

1、概述

（1）Chubby ：Google设计的提供粗粒度锁服务的一个文件系统,所有操作都是在文件的基础上完成的。

（粗粒度就是不精细的意思）

（2）它基于松耦合分布式系统，解决了分布的一致性问题,是一种建议性的锁。

a.松耦合分布式系统： 各个组件之间耦合性很小，联系不紧密

b.建议性锁：每个使用上锁文件的进程都要检查是否有锁存在，如果有，则尊重现 有的锁。

（3）Chubby存储大量小文件，每个文件就代表一个锁。

（4）在GFS中，创建文件就是进行“加锁”操作，创建  文件成功的那个server其实就是抢占到了“锁”。

（5）Google没有直接实现一个包含Paxos算法的函数库，而是在Paxos算法的基础上设计了一个全新的锁服务Chubby。

2.选取Master服务器：

（1）一群机器需要选举Master时，这些机器同时申请某个锁文件。

（2）成功获取锁的服务器当选主服务器，并在文件中写入自己的地址。

（3）之后，其他服务器通过读取文件中的数据获取Master的地址。

3.Chubby的基本架构

（1）客户端：在客户这一端每个客户应用程序都有一个Chubby程序库（ChubbyLibrary），客户端的所有应用都是通过调用这个库中的相关函数来完成的。

（2）服务器端：服务器一端称为Chubby单元，一般是由五个称为副本（Replica）的服务器组成的，这五个副本在配置上完全一致，并且在系统刚开始时处于对等地位。

4.主服务器和租约器

（1）为了提高系统的效率，Chubby做了一个重要的优化，那就是在选择某一个副本作为协调者之后就长期不变。

（2）租约期内所有的客户请求都由主服务器处理。

（3）一定时间内有且仅有一个主服务器。

（4）如果某个服务器被连续推举为主服务器的话，这个租约期就会不断地被更新。

5.可能出现的两种故障（了解）

（1）客户端租约过期

（2）主服务器出错

二、Paxos算法（用于Chubby）

1.概述

（1）基于消息传递的一致性算法，用于解决分布式系统中的一致性问题。

（2）一致性算法中，该算法最常用、公认最有效。

（3）分布式系统的一致性问题， 就是如何保证系统中初始状态相同的各个节点在执行相同的操作序列时，看到的指令序列是完全一致的，并且最终得到完全一致的结果。

2.算法（重点，熟记三个节点，三个条件）

3.系统的约束条件

（1）约束1：每个acceptor只接受它得到的第一个决议。（不完备）

（2）约束2：一旦某个决议得到通过，之后通过的决议必须和该决议保持一致。

a：一旦某个决议x得到通过，之后任何acceptor再批准的决议必须是x。

b：一旦某个决议x得到通过，之后任何proposer再提出的决议必须是x。

c：如果一个编号为n的提案具有值v，那么存在一个“多数派”，要么它们中没有谁批 准过编号小于n的任何提案，要么它们进行的最近一次批准具有值v。

这个编号好像提案的顺序，顺序靠后的2提案批准了，但是原来1提案已经批准过了，这个2就不做数，先到先得原则。

（3）为了保证决议的唯一性，acceptors也要满足一个约束条件：当且仅当 acceptors没有收到编号大于n的请求时，acceptors 才批准编号为n的提案。

批准2提案之前，一定不能收到3提案，不然无效，喜新厌旧原则。

4.一个决议分为两个阶段（考大题，熟记图中的判断公式）

1.准备阶段

2.批准阶段

（1）先确定你能不能发送，准备好参加议会了吗。

（2）然后确定可以开始选举之后，开始收集并统计票数。

（3）为了确保编号唯一，规定编号计算规则 ：

n个proposer，每个编号为ir (0