Maples' Space

云计算：5. 分布式锁服务Chubby

Posted on In , 4.7k 4 mins.
介绍google的分布式锁服务---Chubby

这里我们讨论强一致性算法

1. Paxos算法

1.0 Glossary

consensus 共识 quorum 法定人数

proposers, acceptors, learners

proposal, accept, majority, chosen, value

image-20210407142542380

1.1 算法的提出与证明

  • 角色
    • proposers: 提出提案，提案信息包括提案编号和提议的value
    • acceptor: 收到提案后可以接受（accept）提案，若提案获得多数派（majority）的acceptors的接受，则称该提案被批准（chosen）
    • learners: 只能学习被批准的提案
  • 条件
    • 决议（value）只有在被proposers提出后才能被批准（未经批准的决议称为提案（proposal））
    • 在一次Paxos算法的执行实例中，只批准（chosen）一个value
    • learners只能获得被批准（chosen）的value

1.2 算法的内容

过程：proposer提出一个提案前，首先要和足以形成多数派的acceptors进行通信，获得他们进行的最近一次接受（accept）的提案（prepare过程），之后根据回收的信息决定这次提案的value，形成提案开始投票。当获得多数acceptors接受（accept）后，提案获得批准（chosen），由acceptor将这个消息告知learner。

1.2.1 决议的提出和批准

两个阶段：

  1. prepare阶段：
    1. proposer选择一个提案编号n并将prepare请求发送给acceptors中的一个多数派
    2. acceptors收到prepare消息后，如果提案的编号大于它已经回复的所有prepare消息(回复消息表示接受accept)，则acceptor将自己上次接受的提案回复给proposer，并承诺不再回复小于n的提案
  2. 批准阶段：
    1. 当一个proposer收到了多数acceptors对prepare的回复后，就进入批准阶段。它要向回复prepare请求的acceptors发送accept请求，包括编号n和根据P2c决定的value（如果根据P2c没有已经接受的value，那么它可以自由决定value）
    2. 在不违背自己向其他proposer的承诺的前提下，acceptor收到accept请求后即批准这个请求

这个过程在任何时候中断都可以保证正确性。例如如果一个proposer发现已经有其他proposers提出了编号更高的提案，则有必要中断这个过程。因此为了优化，在上述prepare过程中，如果一个acceptor发现存在一个更高编号的提案，则需要通知proposer，提醒其中断这次提案。

1.2.2 例子

用实际的例子来更清晰地描述上述过程：

有A1, A2, A3, A4, A5 5位议员，就税率问题进行决议。议员A1决定降税率,因此它向所有人发出一个草案。这个草案的内容是：

1
现有的税率是什么?如果没有决定，我来决定一下. 提出时间：本届议会第3年3月15日;提案者：A1

在最简单的情况下，没有人与其竞争;信息能及时顺利地传达到其它议员处。

于是, A2-A5回应：

1
我已收到你的提案，等待最终批准

而A1在收到2份回复后就发布最终决议：

1
税率已定为10%,新的提案不得再讨论本问题。

这实际上退化为二阶段提交协议。

现在我们假设在A1提出提案的同时, A5决定将税率定为20%:

1
现有的税率是什么?如果没有决定，我来决定一下.时间：本届议会第3年3月16日;提案者：A5

草案要通过侍从送到其它议员的案头. A1的草案将由4位侍从送到A2-A5那里。现在，负责A2和A3的侍从将草案顺利送达，负责A4和A5的侍从则不上班. A5的草案则顺利的送至A4和A3手中。

现在, A1, A2, A3收到了A1的提案; A4, A3, A5收到了A5的提案。按照协议, A1, A2, A4, A5将接受他们收到的提案，侍从将拿着

1
我已收到你的提案，等待最终批准

的回复回到提案者那里。

而A3的行为将决定批准哪一个。

在讨论之前我们要明确一点，提案是全局有序的。在这个示例中，是说每个提案提出的日期都不一样。即第3年3月15日只有A1的提案；第3年3月16日只有A5的提案。不可能在某一天存在两个提案。

情况一

假设A1的提案先送到A3处，而A5的侍从决定放假一段时间。于是A3接受并派出了侍从. A1等到了两位侍从，加上它自己已经构成一个多数派，于是税率10%将成为决议. A1派出侍从将决议送到所有议员处：

1
税率已定为10%,新的提案不得再讨论本问题。

A3在很久以后收到了来自A5的提案。由于税率问题已经讨论完毕，开始讨论某些议员在第3年3月17日提出的议案。因此这个3月16日提出的议案他不去理会。他自言自语地抱怨一句：

1
这都是老问题了，没有必要讨论了。

情况二

依然假设A1的提案先送到A3处，但是这次A5的侍从不是放假了，只是中途耽搁了一会。这次, A3依然会将”接受”回复给A1.但是在决议成型之前它又收到了A5的提案。则：

  1. 如果A5提案的提出时间比A1的提案更晚一些，这里确实满足这种情况，因为3月16日晚于3月15日。则A3回复：
1
我已收到您的提案，等待最终批准，但是您之前有人提出将税率定为10%,请明察。

于是, A1和A5都收到了足够的回复。这时关于税率问题就有两个提案在同时进行。但是A5知道之前有人提出税率为10%.于是A1和A5都会向全体议员广播：

1
税率已定为10%,新的提案不得再讨论本问题。

共识到了保证。

  1. 如果A5提案的提出时间比A1的提案更早一些。假设A5的提案是3月14日提出，则A3直接不理会。
1
A1不久后就会广播税率定为10%.

1.2.3 决议的发布

一个显而易见的方法是当acceptors批准一个value时，将这个消息发送给所有learners。但是这个方法会导致消息量过大。

由于假设没有Byzantine failures，learners可以通过别的learners获取已经通过的决议。因此acceptors只需将批准的消息发送给指定的某一个learner，其他learners向它询问已经通过的决议。这个方法降低了消息量，但是指定learner失效将引起系统失效。

因此acceptors需要将accept消息发送给learners的一个子集，然后由这些learners去通知所有learners。

但是由于消息传递的不确定性，可能会没有任何learner获得了决议批准的消息。当learners需要了解决议通过情况时，可以让一个proposer重新进行一次提案。注意一个learner可能兼任proposer。

1.2.4 Progress的保证

根据上述过程当一个proposer发现存在编号更大的提案时将终止提案。这意味着提出一个编号更大的提案会终止之前的提案过程。如果两个proposer在这种情况下都转而提出一个编号更大的提案，就可能陷入活锁，违背了Progress的要求。一般活锁可以通过 随机睡眠-重试 的方法解决。这种情况下的解决方案是选举出一个leader，仅允许leader提出提案。但是由于消息传递的不确定性，可能有多个proposer自认为自己已经成为leader。Lamport在The Part-Time Parliament一文中描述并解决了这个问题。

1.3 Multi-Paxos

Paxos的典型部署需要一组连续的被接受的值（value），作为应用到一个分布式状态机的一组命令。如果每个命令都通过一个Basic Paxos算法实例来达到一致，会产生大量开销。

如果Leader是相对稳定不变的，第1阶段就变得不必要。 这样，系统可以在接下来的Paxos算法实例中，跳过的第1阶段，直接使用同样的Leader。

为了实现这一目的，在同一个Leader执行每轮Paxos算法时，提案编号 I 每次递增一个值，并与每个值一起发送。Multi-Paxos在没有故障发生时，将消息延迟(从propose阶段到learn阶段)从4次延迟降低为2次延迟。

1.3.1 Multi-Paxos没有失败的情况

在下面的图中，只显示了基本Paxos协议的一个实例(或“执行”)和一个初始Leader(Proposer)。注意，Multi-Paxos使用几个Basic Paxos的实例。

1
2
3
4
5
6
7
8
9
Client   Proposer      Acceptor     Learner
   |         |          |  |  |       |  | --- First Request ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Prepare(N)
   |         |<---------X--X--X       |  |  Promise(N,I,{Va,Vb,Vc})
   |         X--------->|->|->|       |  |  Accept!(N,I,V)
   |         |<---------X--X--X------>|->|  Accepted(N,I,V)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

1.3.2 跳过阶段1的Multi-Paxos

在这种情况下，Basic Paxos的后续实例(由I+1表示)使用相同的Leader，因此，包含在Prepare和Promise的阶段1(Basic Paxos协议的这些后续实例)将被跳过。注意，这里要求Leader应该是稳定的，即它不应该崩溃或改变。

1
2
3
4
5
6
7
Client   Proposer       Acceptor     Learner
   |         |          |  |  |       |  |  --- Following Requests ---
   X-------->|          |  |  |       |  |  Request
   |         X--------->|->|->|       |  |  Accept!(N,I+1,W)
   |         |<---------X--X--X------>|->|  Accepted(N,I+1,W)
   |<---------------------------------X--X  Response
   |         |          |  |  |       |  |

1.4 Fast-Paxos

2. Raft

分布式选举算法

Redis哨兵机制

3. ZAB

原子广播 崩溃恢复

Paxos，Raft，2PC，3PC

弱一致性：Gossip协议

4. Zookeeper

curator

分布式锁：zookeeper redis

Homework: 搭建Zookeeper集群

实现方法

本次使用了三台云服务器，分别为node-0001, node-0002, node-0003

  • 在三台服务器上分别安装zookeeper环境。
  • 在三台服务器的zoo.cfg文件末尾添加配置（由于三台服务器在同一网络下，因此直接使用内网IP）
    1
    2
    3
    server.1=192.168.0.67:2888:3888
    server.2=192.168.0.23:2888:3888
    server.3=192.168.0.42:2888:3888
  • 根据id和对应的IP地址分别配置myid
  • 关闭防火墙
  • 启动zookeeper

结果截图

集群中包含了三台云服务器，node-0001, node-0002, node-0003.

node-0001

image-20210412204429224

node-0002

image-20210412204534447

node-0003

image-20210412204616901

可以发现有一个leader和两个follower。

Reference