1. Chubby

Google Chubby 是一个大名鼎鼎的分布式锁服务，GFS和Big Table等大型系统都用他来解决分布式协作、元数据存储和Master选择等一系列与分布式锁服务相关的问题。Chubby的底层一致性实现就是以Paxos算法为基础的。

1.1 概述

Chubby是一个面向松耦合分布式系统的锁服务，通常用于为一个由大量小型计算机构成的松耦合分布式系统提供高可用的分布式锁服务。一个分布式锁服务的目的是允许他的客户端进程同步彼此的操作，并对当前所处环境的基本状态信息达成一致。

1.2 应用场景

在Chubby的众多应用场景中，最为典型的就是集群中服务器的Master选举。例如在Google文件系统（Google File System，GFS）中使用Chubby锁服务来实现对GFS Master服务器的选举。

1.3 设计目标

Chubby的设计目标：

对上层应用程序的侵入性更小

便于提供数据的发布与订阅

开发人员对基于锁的接口更为熟悉

更便捷的构建更可靠的服务

因此，Chubby被设计成一个需要访问中心化节点的分布式锁服务。同时，在Chubby的设计过程中，提出了以下几个设计目标。

提供一个完整的、独立的分布式锁服务，而非仅仅是一个一致性协议的客户端库

提供粗粒度的锁服务

在提供锁服务的同时提供对小文件的读写功能

高可用、高可靠

提供事件通知机制

1.4 Chubby技术架构

系统结构

Chubby的整个系统结构主要由服务端和客户端两部分组成，客户端通过RPC调用与服务端进行通信，如下图所示。

一个典型的Chubby集群，或称为Chubby cell，通常由5台服务器组成。这些副本服务器采用Paxos协议，通过投票的方式来选举产生一个获得过半投票的服务器作为Master。。一旦某台服务器成为了Master，Chubby就会保证在一段时间内不会再有其他服务器称为Master——这段时间被称为Master租期（Master Lease）.

集群中的每个服务器都维护着一份服务端数据库的副本，但在实际运行过程中，只有Master服务器才能对数据库进行写操作，而其他服务器都是使用Paxos协议从Master服务器上同步数据库数据的更新。

现在我们来看一下Chubby如何来处理客户端的请求：

Chubby客户端定位到Master服务器：Chubby客户端通过向记录有Chubby服务器列表的DNS来请求获取Chubby服务器列表。然后逐个发起请求询问该服务器是否是Master节点，在这个询问过程中，那些非Master服务器，则会将当前Master所在服务器标识反馈给客户端节点。
Client执行客户端请求：客户端定位到Master 服务器之后，只要该Master正常运行，那么客户端就会将所有的请求都发送到该Master服务器上。针对写请求，Chubby Master会采用一致性协议将其广播给集群中所有的副本服务器，并且在过半的服务器接受了该写请求之后，再响应给客户端正确的应答。而对于读请求，则不需要在集群内部进行广播处理，直接由Master服务器单独处理即可。
Chubby Master 选举：在Chubby运行过程中，服务器难免会发生故障。如果当前的Master服务器崩溃了，那么集群中的其他服务器会在Master租期到期后，重新开启新一轮的Master选举。通常，进行一次Master选举大概需要花费几秒钟的时间。而如果是集群中任意一台非Master服务器崩溃，那么整个集群是不会停止工作的，这个崩溃的服务器会在恢复之后自动加入到Chubby集群中去。新加入的服务器首先需要同步Chubby最新的数据库数据，完成数据同步之后，新的服务器就可以加入到正常的Paxos运行流程中与其他服务器副本一起协同工作。

目录和文件

Chubby对外提供了一套与Unix文件系统非常相近但是更简单的访问接口。

Chubby的命名空间，包括文件和目录，我们称之为节点。和Unix系统一样，每个目录都可以包含一系列的子文件和子目录列表，而每个文件中则会包含文件内容。

Chubby上的每个数据节点都分为持久节点和临时节点两大类，其中持久节点需要显示的调用接口API来进行删除，而临时节点则会在其对应的客户端会话失效后被自动删除。

Chubby上的每个数据节点都包含了少量的元数据信息，其中包括用于权限控制的访问控制列表（ACL）信息，分别如下：

实例编号: 唯一标识一个数据节点。

文件内容编号：文件内容编号用于标识文件内容的变化情况。

锁编号：锁编号用于标识节点的锁状态变更情况。该编号会在节点锁从自由（free）状态转换为被持有（head）状态增加。

ACL编号：ACL编号用于标识节点的ACL信息变更情况，该编号会在系欸但的ACL配置信息被写入时增加。

锁与锁序列器

个客户端C1获取到了互斥锁L，并且在锁L的保护下发出请求R，但请求R迟迟没有到达服务端（可能出现网络延时或反复重发等），这时应用程序会认为该客户端进程已经失败，于是便会为另一个客户端C2分配锁L，然后再重新发起之前的请求R，并成功的应用到了服务器上。此时，不幸的事情发生了，客户端C1发起的请求R在经过一波三折之后也到达了服务端，此时，他有可能会在不受任何锁控制的情况下被服务端处理，从而覆盖了客户端C2的操作，于是导致系统数据出现不一致。

Chubby中，任意一个数据节点都可以充当一个读写锁来使用：一种是单个客户端以排他（写）模式持有这个锁，另一种则是任意数目的客户端以共享（读）模式持有这个锁。

对于上面出现的消息延迟和重排序引起的分布式锁问题，我们主要采用锁延迟和锁序列其两种策略来解决上面出现的问题。

锁延迟策略：如果一个客户端以正常的方式主动释放了一个锁，那么Chubby服务端将会允许其他客户端能够立即获取到该锁。而如果一个锁是因为客户端的异常情况（如客户端无响应）而被释放的话，那么Chubby服务器会为该锁保留一定的时间，我们称之为“锁延迟”（lock-delay）

锁序列器策略：任何时候，锁的持有者都可以向Chubby请求一个锁序列器，其包括锁的名字、锁模式（排他或共享模式），以及锁序号。当客户端应用程序在进行一些需要锁机制保护的操作时，可以将该锁序列器一并发送给服务端。Chubby服务端接收到这样的请求后，会首先检测该序列器是否有效，以及检查客户端是否处于恰当的锁模式；如果没有通过检查，那么服务端就会拒绝该客户端请求。

Chubby中的事件通知

Chubby的客户端可以向服务端注册时间通知，当触发这些事件的时候，服务端就会向客户端发送对应的事件通知。Chubby常见的事件通知如下：

文件内容变更

节点删除

子节点新增、删除

Master服务器转移

Chubby中的缓存

为了提高Chubby的性能，同时也是为了减少客户端和服务端之间频繁的读请求对服务端的压力，Chubby除了提供事件通知机制之外，还在客户端中实现了缓存，会在客户端对文件内容和元数据信息进行缓存。使用缓存机制在提高系统整体性能的同时，也为系统带来了一定的复杂性，其中最主要的问题就是应该如何保证缓存的一致性。在Chubby中，通过租期机制来保证缓存的一致性。

Chubby缓存的生命周期和Master租期机制紧密关联，Master会维护每个客户端的数据缓存情况，并通过向客户端发送过期信息的方式来保证客户端数据的一致性。在这种机制下，Chubby就能够保证客户端要么能够从缓存中访问到一致的数据，要么访问出错，而一定不会访问到不一致的数据。具体的，每个客户端的缓存都有一个租期，一旦该租期到期，客户端就需要向服务端续订租期以继续维持缓存的有效性。当文件数据或元数据系你先被修改时，Chubby服务端首先会阻塞该修改操作，然后由Master向所有可能缓存了该数据的客户端发送缓存过期信号，以使其缓存失效，等到Master在接收到所有相关客户端针对该过期信号的应答（应答包括两类，一类是客户端明确要求更新缓存，另一类则是客户端允许缓存租期过期）后，再继续进行之前的修改操作。

会话和会话激活（KeepAlive）

Chubby客户端和服务端之间通过创建一个TCP连接来进行所有的网络通信操作，我们将这一连接称为会话（Session）。会话是有生命周期的，存在一个超时时间，在超时时间内，Chubby客户端和服务端之间可以通过心跳检测来保持会话的活性，以使会话周期得到延续，我们将这个过程称为KeepAlive（会话激活）。

KeepAlive请求

Master在接收到客户端的KeepAlive请求时，首先会将该请求阻塞住，并等到该客户端的当前会话租期即将过期时，才为其续租该客户端的会话租期，之后再向客户端响应这个KeepAlive请求，并同时将最新的会话租期超时时间反馈给客户端。Master对于会话续租时间的设置，默认是12秒，但这不是一个固定的值，Chubby会根据实际的运行情况，自行调节该周期的长短。

客户但在接收到来自Master的续租响应后，会立即发起一个新的KeepAlive请求，再由Master进行阻塞。因此我们可以看出，在正常运行过程中，每一个Chubby客户端总是会有一个KeepAlive请求阻塞在Master服务器上。

会话超时

Chubby的客户端也会维持一个和Master端近似相同的会话租期。一方面，KeepAlive响应在网络传输过程中会花费一定的时间；另一方面，Master服务端和Chubby客户端存在时钟不一致性现象。因此在Chubby会话中，存在Master端会话租期和客户端本地会话租期。

如果Chubby客户端在运行过程中，按照本地的会话租期超时时间，检测到其会话租期已经过期却尚未接收到Master的KeepAlive响应，那么这个时候，他将无法确定Master服务端是否已经终止了当前会话，我们称这个时候客户端处于“危险状态”。此时，Chubby客户端会清空其本地缓存，并将其标记为不可用。同时，客户端还会等待一个被称作“宽限期”的时间周期，这个宽限期默认是45秒。如果在宽限期到期前，客户端和服务端之间成功的进行了KeepAlive，那么客户端就会再次开启本地缓存，否则，客户端就会认为当前会话已经过期了，从而中止本次会话。

Chubby Master故障恢复

Chubby的Master服务器上会于运行着会话租期计时器，用来管理所有会话的生命周期。
如果在运行过程中Master出现了故障，那么该计时器会停止，直到新的Master选举产生后，计时器才会继续计时，也就是说，从旧的Master崩溃到新的Master选举产生所花费的时间将不计入会话超时的计算中，这等价于延长了客户端的会话租期。如果新的Master在短时间内就选举产生了，那么客户端就可以在本地会话租期过期前与其创建连接。而如果Master的选举花费了较长的时间，就会导致客户端只能清空本地的缓存，并进入宽限期进行等待。从这里我们可以看出，由于宽限期的存在，使得会话能够很好地在服务端Master转换的过程中得到维持。整个Chubby Master故障恢复过程中服务端和客户端的交互情况如下图所示。

一旦客户端与新的Master建立上连接之后，客户端和Master之间会通过互相配合来实现对故障的平滑恢复。新的Master会设法将上一个Master服务器的内存状态构造出来。具体的，由于本地数据库记录了每个客户端的会话信息，以及其持有的锁和临时文件等信息，因此Chubby会通过读取本地磁盘的数据来恢复一部分状态。总的来讲，一个新的Chubby Master 服务器选举产生之后，会进行如下几个主要处理。

新的Master选举产生后，首先需要确定Master周期。Master周期用来唯一标识一个Chubby集群的Master统治轮次，以便区分不同的Master。一旦新的Master走起确定下来之后，Master就会拒绝所有携带其他Master周期编号的客户端请求，同时告知其最新的Master周期编号，例如上述提到的 KeepAlive 请求 4.需要注意的一点是，只要发生Master重新选举，就一定会产生新的Master周期，即使是在选举前后Master都是同一台机器的情况下也是如此。
选举产生的新Master能够立即对客户端的Master寻址请求进行响应，但是不会立即开始处理客户端会话相关的请求操作。
Master 根据本地数据库中存储的会话和锁信息，来构建服务器的内存状态。
到现在为止，Master已经能够处理客户端的KeepAlive请求了，但依然无法处理其他会话相关的操作。
Master会发送一个“Master 故障切换”事件给每一个会话，客户端接收到这个事件后，会清空他的本地缓存，并警告上层应用程序可能已经丢失了别的事件，之后再向Master反馈应答。
此时，Master会一直等待客户端的应答，直到每一个会话都应答了这个切换事件。
在Master接收到了所有客户端的应答之后，就能够开始处理所有的请求操作了。
如果客户端使用了一个在故障切换之前创建的句柄，Master会重新为其创建这个句柄的内存对象，并执行调用。而如果该句柄在之前的Master周期中已经被关闭了，那么他就不能在这个Master周期再次被重建了——这一机制就确保了即使由于网络原因使得Master接收到那些延迟或重发的网络数据包，也不会错误的重建一个已经关闭的句柄。

1.5 Paxos协议实现

Chubby服务端的基本架构大致分为三层：

最底层是容错日志系统（Fault-Tolerant Log），通过Paxos算法能够保证集群中所有机器上的日志完全一致，同时具备较好的容错性。

日志层之上是Key-Value类型的容错数据库（Fault-Tolerant DB），其通过下层的日志来保证一致性和容错性。

存储层之上就是Chubby对外提供的分布式锁服务和小文件存储服务。

Paxos算法的作用就在于保证集群内各个副本节点的日志能够保持一致。Chubby事务日志中的每一个Value对应Paxos算法中的一个Instance，由于Chubby需要对外提供不间断的服务，因此事务日志会无限增长，于是在整个Chubby运行过程中，会存在多个Paxos Instance。同时，Chubby会为每一个Paxos Instance都按序分配一个全局唯一的Instance 编号，并将其顺序写入到事务日志中去。

在多Paxos Instance的模式下，为了提升算法执行的性能，就必须选举出一个副本节点作为Paxos算法的主节点（以下简称Master或Coordinator），以避免因为每一个Paxos INstance 都提出提案而陷入多个Paxos Round并存的情况。同时，Paxos会保证在Master重启或出现故障而进行切换的时候，允许出现短暂的多个Master共存却不影响副本之间的一致性。

在Paxos中，每一个PaxosInstance都需要进行一轮或多轮“Prepare→Promise→Propose→Accept”这样完整的二阶段请求过程来完成对一个提案值的选定，而多个Instance之间是完全独立的，每个Instance可以自己决定每一个Round的序号，尽尽只需要保证在Instance 内部不会出现序号重复即可。为了在保证正确性的前提下尽可能的提高算法运行性能，可以让多个Instance共用一套序号分配机制，并将“Prepare→Promise”合并为一个阶段，具体做法如下。

当某个副本节点通过选举成为Master后，就会使用新分配的编号N来广播一个Prepare消息，该Prepare消息会被所有未达成一致的Instance和目前还未开始的Instance共用。

当Acceptor接收到Prepare消息后，必须对多个Instance同时做出回应，这通常可以通过将反馈信息封装在一个数据包中来实现。假设最多允许K个Instance同时进行提案值的选定，那么：

当前至多存在K个未达成一致的Instance，将这些未决的Instance各自最后接受的提案值（若该提案尚未接受任何值，则使用null来代替）封装进一个数据包，并作为Promise消息返回。

同时，判断N是否大于当前Acceptor的highestPromisedNum值（当前已经接受的最大提案编号值），如果大于该值的话，那么就标记这些未决Instance和所有未来的Instance的highestPromisedNum值为N——这样，这些未决Instance和所有未来Instance都不能再接受任何编号小于N的提案。

然后Master就可以对所有未决Instance和所有未来Instance分别执行“Propose→Accept”阶段的处理。值得注意的是，如果当前Master能够一致稳定运行的话，那么在接下来的算法运行过程中，就不再需要进行“Prepare→Promise”的处理了。但是一旦Master发现Acceptor返回了一个Reject消息，说明集群汇总存在另一个Master，并且试图使用更大的提案编号（比如M，其M>N）发送了Prepare消息。碰到这种情况，当前Master就需要重新分配新的提案编号（必须比M更大）并再次进行“Prepare→Promise”阶段的逻辑处理。

在每个Instance的运行过程中，一旦接收到多数派的Accept反馈后，就可以将对应的提案值写入本地事务日志并广播Commit消息给集群中的其他副本节点，其他副本节点在接收到这个COMMIT消息之后也会将提案值写入到事务日志中去。

最后，为了提高整个集群的性能，还有一个改进之处在于：得益于Paxos算法的容错机制，只要任意时刻保证多数派的机器能够正常运行，那么在宕机瞬间未能真正写入到磁盘上（只有当真正调用操作系统Flush接口后，数据才能被真正写入物理磁盘中）的那一小部分事务日志也可以其他正常运行的副本上复制来进行获取，因此不需要实时地进行事务日志的Flush操作，这可以极大地提高事务写入的效率。

Zookeeper分布式一致性原理（三）：Chubby分布式锁服务