阅读笔记（二十三）谷歌paxos算法实践经验《Paxos Made Live - An Engineering Perspective》

以你之姓@ 2023-07-07 08:15 61阅读 0赞

### 一. 前言 ###

《Paxos Made Live - An Engineering Perspective》一文为谷歌公司所写，主要内容为paxos算法工程领域实践遇到的问题和经验教训。关于Paxos共识算法的介绍可以参看[前文][Link 1]，算法本身简洁而优雅，提供了很高的灵活性。但是就是因为很高的灵活性，导致了实现起来会异常复杂。于此相反的是raft做了很多严格的规定，因此实现起来会容易很多，也更易于理解。谷歌在实现Paxos并不顺利，论文中称之为“Non-trivial task”，主要问题有

*  Paxos算法伪代码可以简单地描述，但是实际却需要编写几千行C++代码，因为将算法变为实际的工程，需要加入很多的特性和优化。
 *  算法提供了容错性数学上的证明，但是在实际中验证需要做很多工作
 *  算法在容错方面仅做了简单地考虑，在实际中会遇到“成吨的”其他问题，如算法的错误，编程的BUG，操作问题，硬件故障等等。这些都是算法假设去掉了的，为了保证真实系统的可靠性，这里必须采用很多不同的方式解决。
 *  真实系统不像算法一样精确，而是一直在变化之中，因此需要再算法每个阶段都能容忍网络的变化。

本文就谷歌提出的以上问题来分析论文中谷歌是如何解决这些问题的。

### 二. 应用背景 ###

工程实践一种算法当然是为了应用，因此应用背景是前提条件，抛开特定场景就无法理解很多工程上的做法。在谷歌的大数据生态圈中，GFS用于存储大量的网页文件，MapReduce用于对数据进行处理，BigTable数据库用于存储网页文件索引、信息。GFS和BigTable有着共同的使用场景：大量廉价低性能计算机组成的分布式系统，因此如何保持Log以及各种信息的一致性至关重要。Chubby就是起到该作用，而Chubby的核心就是Paxos算法。

如下图所示是Chubby的系统框架，Chubby Library是对Paxos的实现，上层封装了Chubby Client和服务器进行通信。图中间是Chubby的核心所在，主要由容错日志和容错数据库组成。其中容错日志基于Paxos实现，保证每个机器上运行的Chubby中日志内容相同。容错数据库包括了本地快照和数据库操作的replay-log，原理类似于MySQL的redo-log，可以在共识算法发现异常时对数据操作进行方便的回退或增加。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70]

### 三. 实现细节 ###

##### 1. 处理磁盘故障 #####

磁盘的意外故障会造成文件内容的改变或者文件不可读。为此我们需要磁盘故障检测以及修复的功能。磁盘故障检测主要包括：  
（1）在文件中存储文件目录的校验和，如果校验和变化则表示磁盘出现故障  
（2）在文件复制时，如果出现后面的问题，复制的结果是一个空磁盘，我们对此做GFS的标记，检测到该标记则表明出现了无法访问的文件，即磁盘出现故障  
  磁盘修复主要方法是参与Paxos但是不投票，利用catch-up机制复制文件到本机，不给与promis或者ack回复，直到完成了所有文件的修复为止。

##### 2. master租赁机制（Master Leases） #####

在Paxos运行过程中，master一旦选举成功就具有了发起更新的权力。但是由于Paxos的灵活性或者由于分区等原因，可能会产生多个master，从而造成数据的不一致性。因此我们需要保证任意时刻只有一个master的存在。

为了实现master的唯一性，我们需要做以下限制：  
（1）在master租赁期内，其他的成员不允许提交值  
（2）当master断开连接的时候，选举新的master的序列大于旧的序列。旧序列即使连上了，master也会自我解除权限。**注意这里和paxos算法原文中的优化措施相反，原文中采取的是旧master连上了之后自增重新成为master。这种做法对于网络情况差、经常断线的网络会导致master不停地更换，使得网络效率极低**。

##### 3. 全局逻辑时钟机制（Epoch Numbers） #####

这里采取了类似于[Lamport时钟][Lamport]的逻辑时钟来实现分布式消息的同步问题。

##### 4. 会员组机制（Group Membership） #####

考虑到复杂多变的网络情况、易出现故障的磁盘，我们需要时刻记录当前的Paxos的参与者。对于单个Paxos，自身其实就具有记录功能，但是对于多Paxos的情况，最佳选择是额外实现一个会员组模块存储当前的参与者。

##### 5. 快照功能 #####

仅记录日志的话会存在两个问题：

*  如果出现错误需要回复会需要不停地查找，工作量极大
 *  日志没有上限，会磁盘会造成巨大的负担甚至崩溃

因此，在这里我们也采用了快照技术。

（1） 快照和日志需要保持一致性，每一个快照需要拥有和其内容相关的容错日志的信息，为此我们设计了快照句柄，快照句柄包括了Paxos相关的所有信息。当创建快照时，我们同时创建快照句柄。当需要使用快照恢复文件的时候，根据句柄获取信息，结合快照和日志进行恢复

（2）快照的创建需要消耗一定的时间，冻结日志创建快照会带来一定的延迟。因此我们分三个步骤完成快照：首先客户端决定创建快照，请求快照句柄。接着客户端创建一个线程来创建自己的快照，最终快照创建完后，客户端通知框架，并传输快照句柄。

（3）创建快照可能会失败：客户端未通知框架的时候，从框架的角度是不知道已经产生了新的客户端快照的，因此客户端可以检验其完整性并丢弃。仅仅当框架收到句柄时，该快照才算生效

### 四. 总结 ###

论文中还有提到一些如遇到的意外问题以及对算法性能效果的测试，在此不做展开记录了，推荐查看原文深入学习。

[Link 1]: https://blog.csdn.net/u013354486/article/details/104081997
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200308171612354.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMzNTQ0ODY=,size_16,color_FFFFFF,t_70
[Lamport]: https://blog.csdn.net/u013354486/article/details/104088271