Chubby是一个面向松耦合分布式系统的锁服务，GFS（Google File System）和Big Table等大型系统都是用它来解决分布式协作、元数据存储和Master选举等一些列与分布式锁服务相关的问题。Chubby的底层一致性实现就是以Paxos算法为基础，Chubby提供了粗粒度的分布式锁服务，开发人员直接调用Chubby的锁服务接口即可实现分布式系统中多个进程之间粗粒度的同控制，从而保证分布式数据的一致性。

　　2.1 设计目标

　　Chubby被设计成为一个需要访问中心化的分布式锁服务。

　　① 对上层应用程序的侵入性更小，使用一个分布式锁服务的接口方式对上层应用程序的侵入性更小，应用程序只需调用相应的接口即可使用分布式一致性特性，并且更易于保持系统已有的程序结构和网络通信模式。

　　② 便于提供数据的发布与订阅，在Chubby进行Master选举时，需要使用一种广播结果的机制来向所有客户端公布当前Master服务器，这意味着Chubby应该允许其客户端在服务器上进行少量数据的存储和读取（存储主Master地址等信息），也就是对小文件的读写操作。数据的发布与订阅功能和锁服务在分布式一致性特性上是相通的。

　　③ 开发人员对基于锁的接口更为熟悉，Chubby提供了一套近乎和单机锁机制一直的分布式锁服务接口。

　　④ 更便捷地构建更可靠的服务，Chubby中通常使用5台服务器来组成一个集群单元（Cell），根据Quorum机制（在一个由若干个机器组成的集群中，在一个数据项值的选定过程中，要求集群中过半的机器达成一致），只要整个集群中有3台服务器是正常运行的，那么整个集群就可以对外提供正常的服务。

　　⑤ 提供一个完整的、独立的分布式锁服务，Chubby对于上层应用程序的侵入性特别低，对于Master选举同时将Master信息等级并广播的场景，应用程序只需要向Chubby请求一个锁，并且在获得锁之后向相应的锁文件写入Master信息即可，其余的客户端就可以通过读取这个锁文件来获取Master信息。

　　⑥ 提供粗粒度的锁服务，Chubby针对的应用场景是客户端获得锁之后会进行长时间持有（数小时或数天），而非用于短暂获取锁的场景。当锁服务短暂失效时（服务器宕机），Chubby需要保持所有锁的持有状态，以避免持有锁的客户端出现问题。而细粒度锁通常设计为为锁服务一旦失效就释放所有锁，因为其持有时间很短，所以其放弃锁带来的代价较小。

　　⑦ 高可用、高可靠，对于一个由5太机器组成的集群而言，只要保证3台正常运行的机器，整个集群对外服务就能保持可用，另外，由于Chubby支持通过小文件读写服务的方式来进行Master选举结果的发布与订阅，因此在Chubby的实际应用中，必须能够支撑成百上千个Chubby客户端对同一个文件进行监控和读取。

　　⑧ 提供时间通知机制，Chubby客户端需要实时地感知到Master的变化情况，这可以通过让你客户端反复轮询来实现，但是在客户端规模不断增大的情况下，客户端主动轮询的实时性效果并不理想，且对服务器性能和网络带宽压力都非常大，因此，Chubby需要有能力将服务端的数据变化情况以时间的形式通知到所有订阅的客户端。

　　2.2 技术架构

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

　　一个典型的Chubby集群（Chubby Cell），通常由5台服务器组成，这些副本服务器采用Paxos协议，通过投票的方式来选举产生一个获得过半投票的服务器作为Master，一旦成为Master，Chubby就会保证在一段时间内不会再有其他服务器成为Master，这段时期称为Master租期（Master Lease），在运行过程中，Master服务器会通过不断续租的方式来延长Master租期，而如果Master服务器出现故障，那么余下的服务器会进行新一轮的Master选举，最终产生新的Master服务器，开始新的Master租期。

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

　　Chubby客户端通过向记录有Chubby服务端机器列表的DNS来请求获取所有的Chubby服务器列表，然后逐一发起请求询问该服务器是否是Master，在这个询问过程中，那些非Master的服务器，则会将当前Master所在的服务器标志反馈给客户端，这样客户端就能很快速的定位到Master服务器了。

　　只要该Master服务器正常运行，那么客户端就会将所有的请求都发送到该Master服务器上，针对写请求，Master会采用一致性协议将其广播给集群中所有的副本服务器，并且在过半的服务器接受了该写请求后，再响应给客户端正确的应答，而对于读请求，则不需要在集群内部进行广播处理，直接由Master服务器单独处理即可。

　　若该Master服务器发生故障，那么集群中的其他服务器会在Master租期到期后，重新开启新的一轮Master选举，通常一次Master选举大概花费几秒钟的时间，而如果其他副本服务器崩溃，那么整个集群继续工作，该崩溃的服务器会在恢复之后自动加入到Chubby集群中去，新加入的服务器首先需要同步Chubby最新的数据库数据，完成数据库同步之后，新的服务器就可以加入到正常的Paxos运作流程中与其他服务器副本一起协同工作。若崩溃后几小时后仍无法恢复工作，那么需要加入新的机器，同时更新DNS列表（新IP代替旧IP），Master服务器会周期性地轮询DNS列表，因此会很快感知服务器地址的变更，然后Master就会将集群数据库中的地址列表做相应的变更，集群内部的其他副本服务器通过复制方式就可以获取到最新的服务器地址列表了。

　　2.3 目录与文件

　　Chubby对外提供了一套与Unix文件系统非常相近但是更简单的访问接口。Chubby的数据结构可以看作是一个由文件和目录组成的树，其中每一个节点都可以表示为一个使用斜杠分割的字符串，典型的节点路径表示如下：

　　/ls/foo/wombat/pouch

　　其中，ls是所有Chubby节点所共有的前缀，代表着锁服务，是Lock Service的缩写；foo则指定了Chubby集群的名字，从DNS可以查询到由一个或多个服务器组成该Chubby集群；剩余部分的路径/wombat/pouch则是一个真正包含业务含义的节点名字，由Chubby服务器内部解析并定位到数据节点。

　　Chubby的命名空间，包括文件和目录，我们称之为节点（Nodes，我们以数据节点来泛指Chubby的文件或目录）。在同一个Chubby集群数据库中，每一个节点都是全局唯一的。和Unix系统一样，每个目录都可以包含一系列的子文件和子目录列表，而每个文件中则会包含文件内容。Chubby没有符号链接和硬连接的概念。

　　Chubby上的每个数据节点都分为持久节点和临时节点两大类，其中持久节点需要显式地调用接口API来进行删除，而临时节点则会在其对应的客户端会话失效后被自动删除。也就是说，临时节点的生命周期和客户端会话绑定，如果该临时节点对应的文件没有被任何客户端打开的话，那么它就会被删除掉。因此，临时节点通常可以用来进行客户端会话有效性的判断依据。

　　Chubby的每个数据节点都包含了少量的元数据信息，其中包括用于权限控制的访问控制列表（ACL）信息，同时每个节点的元数据还包括4个单调递增的64位标号：

　　① 实例标号，用于标识创建该数据节点的顺序，节点的创建顺序不同，其实例编号也不相同，可以通过实例编号来识别两个名字相同的数据节点是否是同一个数据节点，因为创建时间晚的数据节点，其实例编号必定大于任意先前创建的同名节点。

　　② 文件内容编号（针对文件），用于标识文件内容的变化情况，该编号会在文件内容被写入时增加。

　　③ 锁编号，用于标识节点锁状态的变更情况，该编号会在节点锁从自由状态转化到被持有状态时增加。

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

　　2.4 锁和锁序列器

　　分布式环境中锁机制十分复杂，消息的延迟或是乱序都有可能引起锁的失效，如客户端C1获得互斥锁L后发出请求R，但请求R迟迟没有到达服务端（网络延迟或消息重发等），这时应用程序会认为该客户端进程已经失败，于是为另一个客户端C2分配锁L，然后在发送请求R，并成功应用到了服务器上。然而，之前的请求R经过一波三折后也到达了服务器端，此时，它可能不瘦任何锁控制的情况下被服务端处理，而覆盖了客户端C2的操作，也是导致了数据不一致问题。

　　在Chubby中，任意一个数据节点均可被当做一个读写锁来使用：一种是单个客户端排他（写）模式持有这个锁，另一种则是任意数目的客户端以共享（读）模式持有这个锁，Chubby放弃了严格的强制锁，客户端可以在没有获取任何锁的情况下访问Chubby的文件。

　　Chubby采用了锁延迟和锁序列器两种策略来解决上述由于消息延迟和重排序引起的分布式锁问题，对于锁延迟而言，如果一个客户端以正常的方式主动释放了一个锁，那么Chubby服务端将会允许其他客户端能够立即获取到该锁；如果锁是以异常情况被释放的话，那么Chubby服务器会为该锁保留一定的时间，这称之为锁延迟，这段时间内，其他客户端无法获取该锁，其可以很好的防止一些客户端由于网络闪断的原因而与服务器暂时断开的场景。对于锁序列器而言，其需要Chubby的上层应用配合在代码中加入相应的修改逻辑，任何时候，锁的持有者都可以向Chubby请求一个锁序列器，其包括锁的名字、锁模式（排他或共享）、锁序号，当客户端应用程序在进行一些需要锁机制保护的操作时，可以将该锁序列器一并发送给服务端，服务端收到该请求后，会首先检测该序列器是否有效，以及检查客户端是否处于恰当的锁模式，如果没有通过检查，那么服务端就会拒绝该客户端的请求。

　　2.5 事件通知机制

　　为了避免大量客户端轮询Chubby服务端状态所带来的压力，Chubby提供了事件通知机制，客户端可以向服务端注册事件通知，当触发这些事件时，服务端就会向客户端发送对应的时间通知，消息通知都是通过异步的方式发送给客户端的。常见的事件如下

　　① 文件内容变更 ② 节点删除 ③ 子节点新增、删除 ④ Master服务器转移

　　2.6 缓存

　　其是为了减少客户端与服务端之间的频繁的读请求对服务端的压力设计的，会在客户端对文件内容和元数据信息进行缓存，虽然缓存提高了系统的整体性能，但是其也带来了一定复杂性，如如何保证缓存的一致性。其通过租期机制来保证缓存的一致性。

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

　　2.7 会话

　　Chubby客户端和服务端之间通过创建一个TCP连接来进行所有的网络通信操作，这称之为会话，会话存在生命周期，存在超时时间，在超时时间内，客户端和服务端之间可以通过心跳检测来保持会话的活性，以使会话周期得到延续，这个过程称为KeepAlive（会话激活），如果能够成功地通过KeepAlive过程将Chubby会话一直延续下去，那么客户端创建的句柄、锁、缓存数据等将仍然有效。

　　2.8 KeepAlive请求

　　Master服务端在收到客户端的KeepAlive请求时，首先会将该请求阻塞住，并等到该客户端的当前会话租期即将过期时，才为其续租该客户端的会话租期，之后再向客户端响应这个KeepAlive请求，并同时将最新的会话租期超时时间反馈给客户端，在正常情况下，每个客户端总是会有一个KeepAlive请求阻塞在Master服务器上。

　　2.9 会话超时

　　客户端也会维持一个和Master端近似相同（由于KeepAlive响应在网络传输过程中会花费一定的时间、Master服务端和客户端存在时钟不一致的现象）的会话租期。客户端在运行过程中，按照本地的会话租期超时时间，检测到其会话租期已经过期却尚未收到Master的KeepAlive响应，此时，它将无法确定Master服务端是否已经中止了当前会话，这个时候客户端处于危险状态，此时，客户端会清空其本地缓存并将其标记为不可用，同时客户端还会等待一个被称作宽限期的时间周期，默认为45秒，若在宽限期到期前，客户端与服务端之间成功地进行了KeepAlive，那么客户端就会再次开启本地缓存，否则，客户端就会认为当前会话已经过期了，从而终止本次会话。

　　在客户端进入危险状态时，客户端会通过一个“jeopardy”事件来通知上层应用程序，如果恢复正常，客户端同样会以一个“safe”事件来通知应用程序可以继续正常运行，但如果客户端最终没能从危险状态中恢复过来，那么客户端会以一个“expired”事件来通知应用程序当前Chubby会话已经超时。

　　2.10 Master故障恢复

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

　　如上图所示，一开始在旧的Master服务器上维持了一个会话租期lease M1，在客户端上维持对应的lease C1，同时客户端的KeepAlive请求1一直被Master服务器阻塞着。一段时间后，Master向客户端反馈了KeepAlive响应2，同时开始了新的会话租期lease M2，而客户端在接收到该KeepAlive响应后，立即发送了新的KeepAlive请求3，并同时也开始了新的会话租期lease C2。至此，客户端和服务端的交互都是正常的，随后，Master发生了故障，从而无法反馈客户端的KeepAlive请求3，在此过程中，客户端检测到会话租期lease C2已经过期，它会清空本地缓存并进入宽限期，这段时间内，客户端无法确定Master上的会话周期是否也已经过期，因此它不会销毁它的本地会话，而是将所有应用程序对它的API调用都阻塞住，以避免出现数据不一致的现象。同时，在客户端宽限期开始时，客户端会向上层应用程序发送一个“jeopardy”事件，一段时间后，服务器开始选举产生新的Master，并为该客户端初始化了新的会话租期lease M3，当客户端向新的Master发送KeepAlive请求4时，Master检测到该客户端的Master周期号已经过期，因此会在KeepAlive响应5中拒绝这个客户端请求，并将最新的Master周期号发送给客户端，之后，客户端会携带上最新的Master周期号，再次发送KeepAlive请求6给Master，最终，整个客户端和服务端之间的会话就会再次回复正常。

　　在Master转化的这段时间内，只要客户端的宽限足够长，那么客户端应用程序就可以在没有任何察觉的情况下，实现Chubby的故障恢复，但如果客户端的宽限期设置得比较短，那么Chubby客户端就会丢弃当前会话，并将这个异常情况通知给上层应用程序。

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

　　① 确定Master周期。Master周期用来唯一标识一个Chubby集群的Master统治轮次，以便区分不同的Master，只要发生Master重新选举，就一定会产生新的Master周期，即使选举前后Master是同一台机器。

　　② 新的Master能够对客户端的Master寻址请求进行响应，但是不会立即开始处理客户端会话相关的请求操作。

　　③ Master根据本地数据库中存储的会话和锁信息来构建服务器的内存状态。

　　④ 至此，Master已经能够处理客户端的KeepAlive请求，但仍然无法处理其他会话相关的操作。

　　⑤ Master会发送一个Master故障切换事件给每一个会话，客户端接收到这个事件后，会清空它的本地缓存，并警告上层应用程序可能已经丢失了别的事件，之后再向Master反馈应答。

　　⑥ 此时，Master会一直等待客户端的应答，直到每一个会话都应答了这个切换事件。

　　⑦ Master接收了所有客户端的应答之后，就能够开始处理所有的请求操作。

　　⑧若客户端使用了一个故障切换之间创建的句柄，Master会重新为其创建这个句柄的内存对象，并执行调用，如果该句柄在之前的Master周期中就已经被关闭了，那么它就不能在这个Master周期内再次被重建了，这一机制就确保了由于网络原因使得Master接收到那些延迟或重发的网络数据包也不会错误的重建一个已经关闭的句柄。

三、Paxos协议实现

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

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

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

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

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

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

　　在Paxos中，每一个Paxos Instance都需要进行一轮或多轮的Prepare->Promise->Propose->Accept这样完整的二阶段请求过程来完成对一个提议值的选定，为了保证正确性的前提下尽可能地提高算法运行性能，可以让多个Instance共用一套序号分配机制，并将Prepare->Promise合并为一个阶段。具体做法如下：

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

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

　　-当前之多存在K个未达成一致的Instance，将这些未决的Instance各自最后接受的提议值封装进一个数据包，并作为Promise消息返回。

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

　　③ Master对所有未决Instance和所有未来Instance分别执行Propose->Accept阶段的处理，如果Master能够一直稳定运行的话，那么在接下来的算法运行过程中，就不再需要进行Prepare->Promise处理了。但是，一旦Master发现Acceptor返回了一个Reject消息，说明集群中存在另一个Master并且试图使用更大的提议编号发送了Prepare消息，此时，当前Master就需要重新分配新的提议编号并再次进行Prepare->Promise阶段的处理。

　　利用上述改进的Paxos算法，在Master稳定运行的情况下，只需要使用同一个编号来依次执行每一个Instance的Promise->Accept阶段处理。

　　在集群的某台机器在宕机重启后，为了恢复机器的状态，最简单的办法就是将已记录的所有日志重新执行一遍，但是如果机器上的日志已经很多，则耗时长，因此需要定期对状态机数据做一个数据快照并将其存入磁盘，然后就可以将数据快照点之前的事务日志清除。

　　在恢复过程中，会出现磁盘未损坏和损坏两种情况，若未损坏，则通过磁盘上保存的数据库快照和事务日志就可以恢复到之前的某个时间点的状态，之后再向集群中其他正常运行的副本节点索取宕机后缺失的部分数据变更记录即可；若磁盘损坏，就笑从其他副本节点索取全部的状态数据。
　　chubby使用paxos作为日志错误容错的复制算法，在协议栈的最底层，paxos算法确保了每个replica的本地日志都有相同的entries，replicas的通信则是通过paxos-specific protocal，一旦某个值进入容错日志，每个replica会调用发送一个callback给客户端应用程序，告诉这个已提交的值

chubby的paxos描述【隐藏了propose和promise的消息发送】

1. 选出一个coordinator.


2. 选择一个value，并广播给所有的replicas，该消息称为accept message，其他replicas不是acknowledge message就是reject it


3. 一旦收到大多数的acknowledge， coordinator就广播commit 消息 to notify replicas

选择coordinator？

在chubby中选择coordinator上，paxos确保在某一个值上【选出一个coordinator】达成一致通过引入两种机制：

1）分配一个有序编号给后续的coordinators【通过产生一个最新的编号来成为coordinator， 如Replica r 的编号为s mod n = Ir ， 然后broadcasts all replicas in a propose message 等待replicas 回复 promise】

2）严格限制每个coordinator的选值【什么意思呢？在选择coordinator的时候，使用的是fully paxos，即二阶段paxos，如果在第一阶段后收到一个已确定的值，则使用该值(使用该coordinator)】

与ZK的一点区别？
chubby可以不断轮换coordinator。原文描述为if consensus was achieved by a previous coordinator, the new coordinator is guaranteed to hear about the value decided upon from at least one replica. By induction, that value will have the highest sequence number of all responses received, and so will be selected by the new coordinator. 这样可以轮流换coordinator，这点和ZK还是有区别，ZK一旦leader确定下载，如果不失败的话是不会改变的，但chubby可以不断轮换coordinator

轮换coordinator 怎么解决活锁的问题呢？如果某段时间内有两个replicas一直争抢着要成为coordinator，这个怎么解决？

chubby 解决活锁的办法：In our implementation the master periodically boosts its sequence number by running a full round of the Paxos algorithm, including sending propose messages. Boosting with the right frequency avoids this type of master churn in most cases. 即在希望成为master的时候，是间断性的 right frequency 来避免这一活锁问题

对paxos还有点小不明白的就是并发的情况是怎么样的？有案例吗？

我在看chubby的论文的时候，一直看到那个sequencer的东西，但这个sequencer似乎并不是看得很懂，paxos都是异步的，只要满足序号，并发处理是没有啥问题的

处理拖后腿的replica？

对于拖后腿的replica则让其catch up 那些leading replicas

chubby如何处理优化的？
In a system where replicas are in close network proximity, disk flush time can dominate the overall latency of the implementation.
在replicas都很近的情况下，刷磁盘会很耗代价
使用了lambort的优化made simple的优化：
Propose messages may be omitted if the coordinator identity does not change between instances. This does not interfere with the properties of Paxos because any replica at any time can still try to become coordinator by broadcasting a propose message with a higher sequence number.
为了利用这一优化，所以尽可能的少轮换coordinatorpick a coordinator for long periods of time, trying not to let the coordinator change，但它又说利用了这点每个replica只要写一次磁盘就行了，master在发送accept的消息前写磁盘，其他的replicas在发送acknowledge消息前，写一次磁盘就行了
另一种为增加吞吐量，In order to get additional throughput in a concurrent system, it is possible to batch a collection of values submitted by di?erent application threads into a single Paxos instance

如何处理disk corruption
原因是A disk may be corrupted due to a media failure or due to an operator error (an operator may accidentally erase critical data). When a replica’s disk is corrupted and it loses its persistent state, it may renege on promises it has made to other replicas in the past.
由于不保证它的promise，因此，这违背了paxos的算法的一个关键假设：P2B If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v. 即如果一个议案被选择了，那么此后，任何proposer提出的议案(编号更高)包含的决议都是v
解决disk corruptions的情况：
Either filele(s) contents may change or file(s) may become inaccessible，解决第一种是将文件checksum存储在文件中 后边的问题检测是replica在第一次启动后存放一个marker在GFS中，如果再次启动发现一个empty disk 并且在GFS中有这个标示，则说明是corrupted disk
重建replica的状态 It participates in Paxos as a non-voting member; meaning that it uses the catch-up mechanism to catch up but does not respond with promise or acknowledgment messages. It remains in this state until it observes one complete instance of Paxos that was started after the replica started rebuilding its state. By waiting for the extra instance of Paxos, we ensure that this replica could not have reneged on an earlier promise
另外，论文还说到，利用这一机制还能降低系统的延迟，即可以接受不需要立即刷磁盘。但他们也说还没有实现，不知道现在有没有实现好

master lease的问题
as long as the master has the lease, it is guaranteed that other replicas cannot successfully submit values to Paxos. Thus a master with the lease has up-to-date information in its local data structure which can be used to serve a read operation purely locally. By making the master attempt to renew its lease before it expires we can ensure that a master has a lease most of the time. With our system, masters successfully maintain leases for several days at a time.
意思是如果master有lease的话，则其他的replicas不能重新选coordinator，这里的coordinator和master其实是同一个概念，即每一次只有一个master，然后他们的系统中说master一次成功维持了几天。通过master lease 这样 read 操作总是能读到本地最新的数据，但，是不是也可能读到stale的值呢？我想应该也是有可能的，比如我刚提交的一个值，我马上读，这有可能就读不到，这点其实和ZK应该是一样的，区别应该还是在于chubby可以要求成为master，当然，chubby后面也说了，基于这个的lease机制，如果replicas使用的话，也可以让clients直接从本地replicas上读，说还没有实现。

master turnover以及abort会有什么影响？那如何检测master turnover和abort operations？
似乎对客户端也没有什么影响，只是需要告诉客户端master改变了，你应该发送请求到另外的一个master去，如果返回epoch number相同表明没有变换过

chubby 如何通知客户端master是哪个？
每个replica都知道的

关于group membership
对于group membership似乎还不是很清楚，chubby中也只是说文献没有指出 paxos也没有证明使用该算法来实现group membership的正确性，基本上在该文献中是一笔带过，回头看看其他文献有没有说明这个东西

snapshots的问题
两个问题： it requires unbounded amounts of disk space; and perhaps worse, it may result in unbounded recovery time since a recovering replica has to replay a potentially long log before it has fully caught up with other replicas
所以有必要在某一点上的操作日志对应的内存的数据结构序列化到磁盘，truncate掉之前的日志记录
另外，snapshots的问题并不是由paxos framework来做的，因为its only concern is the consistency of the replicated log.

the lagging replica asks for and receives the remaining log records from the leading replica to bring it fully up-to-date

关于snapshot的时候必须对应日志号，那么在线的时候应该怎么处理？以下是论文中的说法

Our first implementation of the fault-tolerant database blocked the system very briefly while making an in-memory copy of the (small) database. It then stored the copied data on disk via a separate thread. Subsequently we implemented virtually pause-less snapshots. We now use a “shadow” data structure to track updates while the underlying database is serialized to disk.

如果直接accept消息而不是完全paxos的算法会有什么问题吗？
这回到了为什么要使用两阶段的问题，按lambort的说话，paxos made simple 中说第一阶段保证了某一proposal被选择了，第二阶段保证最高的proposal对应的值都是value

chubby使用的是TCP还是UDP？

原文这样描述：This would seem ideal, except that it introduced a tension in our choice of protocol. TCP’s back off policies pay no attention to higher-level timeouts such as Chubby leases, so TCP-based KeepAlives led to many lost sessions at times of high network congestion. We were forced to send KeepAlive RPCs via UDP rather than TCP; UDP has no congestion avoidance mechanisms, so we would prefer to use UDP only when high-level timebounds must be met.

引用

chubby的介绍论文 http://static.googleusercontent.com/external_content/untrusted_dlcp/research.google.com/en//archive/chubby-osdi06.pdf

chubby的实现论文，Paxos Made Live - An Engineering Perspective http://www.cs.ucla.edu/~kohler/class/08w-dsi/chandra07paxos.pdf

在分布式系统设计领域，Paxos可谓是最重要一致性的算法。Google的大牛们称

All working protocols for asynchronous consensus we have so far encountered have Paxos at their core.

可见此算法的地位。网络上讨论此算法的文章多如牛毛，但大多数让人看了之后仍然是一头雾水，就连维基百科中，对此算法的描述亦有含糊和错误之处。但实际上，此算法的核心思想还是比较简单的，只是大多数文章的分析脱离了实际应用，或是陷入大量实现细节以致掩盖了算法的核心。本文将先给出Paxos算法的设计目的，和算法流程，再反过来分析算法的原理。

Paxos算法实现的是分布式系统多个结点之上数据的一致性，这个算法有如下特性

1.基于消息传递，允许消息传输的丢失，重复，乱序，但是不允许消息被攥改

2.在结点数少于半数失效的情况下仍然能正常的工作，结点失效可以在任何时候发生而不影响算法正常执行。

下面是Basic Paxos算法，注意，这个算法只具有在多个冲突请求中选出一个的功能，并不具备序列化多个请求依次执行的功能。

Paxos算法包含三个角色Proposor，Acceptor，Learner。

实现的时候采用一组固定数目Server，每个Server同时担任上述三个角色，多个Client将自己的请求值Value_i随机发给一个Server处理，然后这一组Server经过协商后得出统一的一个值Chosen_Value，这个值必须被每个Server学习到，同时回复给所有发起请求的Client。

具体算法流程如下，为避免歧义，关键字眼Propose,Proposal,Accept,Value,Choose等保留英文原文。

阶段1a—Prepare（预定Proposal序号）

每个Proposor 拿到某个Client的请求Value_i后，在此阶段还不能发起Proposal，只能发送一个Proposal序号N，将序号发送给所有Acceptor（即所有Server包括自己），整个系统中所有Proposal的序号不能重复而且每个Proposor自己用到的序号必须是递增的，通常的做法是，假设K台Server协同运行Paxos算法，那么Server_i（i=0…K-1)用的Proposal序号初始值为i，以后每次要产生新序号时递增K，这样保证了所有Server的Proposal序号不重复。

阶段1b—Respond with Promise

每个Acceptor收到Proposal序号后，先检查之前是否Repond序号更高的Proposal，若没有，那么就给出Response，这个Response带有自己已经Accept的序号最高的Proposal（若还没Accept任何Proposal，回复null），同时，Promise自己不再Accept低于接收序号的Proposal。否则，拒绝Respond。

阶段2a—发起Proposal，请求Accept

Proposal如果得到了来自超过半数的Acceptor的Response，那么就有资格向Acceptor发起Proposal<N,value>。其中，N是阶段1a中发送的序号，value是收到的Response中序号最大的Proposal的Value，若收到的Response全部是null，那么Value自定义，可直接选一个Client请求的Value_i

阶段2b–Accept Proposal

检查收到的Proposal的序号是否违反阶段1b的Promise，若不违反，则Accept收到的Proposal。

所有Acceptor Accept的Proposal要不断通知所有Learner，或者Learner主动去查询，一旦Learner确认Proposal已经被超过半数的Acceptor Accept，那么表示这个Proposal 的Value 被 Chosen，Learner就可以学习这个Proposal的Value，同时在自己Server上就可以不再受理Proposor的请求。

这个算法能达到什么效果呢，只要保证超过半数的Server维持正常工作，同时连接工作Server的网络正常（网络允许消息丢失，重复，乱序），就一定能保证，

P2a: 在将来某一时刻，自从某个Proposal被多数派Acceptor Accept后，之后Accept的Proposal Value一定和这个Proposal Value相同。

这就是整个算法的关键，保证了这一点，剩下的Learn Value过程就简单了，无需再为消息丢失，Server宕机而担心，例如，假设5台Server编号0~4，Server0，Server1，Server2已经Accept Proposal 100，然后Server0,Server1学习到Proposal 100，刚学习完成Server0,Server1就都宕机了，但这时候，Server2 Server3和Server4由于没有学习到Chosen value，因此还要继续提出Proposal，然后呢，根据这个神奇的算法，最后能使得Server3 Server4将来Accept的值一定是之前选出来过的Proposal 100的Value。

看到这里，大家应该能够隐隐猜到，在这个过程中，Server2之前Accept Proposal 100的Value起了关键作用，下面，我们就来严格证明上述红色字体表示的算法关键点：

首先回顾前边两阶段协议的几个关键点：

1.发起Proposal前要先获得多数派Acceptor中Accept过的序号最大的Proposal Value。若Value为null才能采用自己的Value。

2.阶段1b Promise自己不再Accept低于接收序号的Proposal。

3.Propsal被超半数的Acceptor Accept才能被认定为Chosen Value从而被Learner学习。

这几个约束条件共同作用，达到了上述P2a要求的效果，Paxos算法提出者Leslie Lamport是怎么构造出来的呢，事实上很简单：

首先，把P2a加强为如下条件：

P2b:自从某个Proposal被多数派Acceptor Accept后，之后Proposor提出的Proposal Value一定和这个Proposal Value相同。

显而易见，由P2b可以推出P2a，那么怎么满足P2b呢，实际上，只要满足如下条件：

P2c:发起的Proposal的Value为任意一个多数派Acceptor集合中Accept过的序号最大的Proposal Value。若这个Acceptor集合中没有Accept过Proposal才能采用自己的Value。

如何从P2c推出P2b呢，利用数学归纳法可以轻易做出证明：假设在某一时刻一个超半数Acceptor集合C共同Accept了某个Proposal K，由于集合C和任意一个多数派Acceptor集合S必有一个共同成员，那么，在这个时刻之后，任意一个多数派Acceptor集合S 中Accept过的最大序号的Proposal只可能是Proposal K或序号比Proposal K更大的Proposal，假设为Proposal K2。同理，Proposal K2的Value等于Proposal K或Proposal K3的Value，而K<K3<K2，递推下去，最终推出根据P2c定出的Value必然是Proposal K的Value。

我们可以看到，P2c条件基本就是上述两阶段协议的关键点1，但是还有一个问题，这个P2c条件要求找出这个“最大序号Value”和提出Proposal必须是一个原子操作，这实际上是难以实现的，所以，上述两阶段协议用了一个巧妙的方法避开了这个问题，这就是上述关键点2 Promise所起的作用了。在Acceptor respond“最大序号Value”的时候，Promise不再Accept低于收到序号的Proposal，这样“找出这个‘最大序号Value’”和“提出Proposal”之间就不可能插入新的被Accept的序号，从而避免P2c条件被破坏。

到这里为止，基本的Paxos算法就已经透彻分析完了，但是，现在这个算法是使用多个Proposal，会造成活锁问题，需要引入leader来优化，而且，这个算法还只能实现在多个冲突Value中选举一个Value的功能，至于序列化多个Value实现状态机，就需要multi-paxos算法。
Google Chubby是一个分布式锁服务，能存储小文件。GFS和big table用它来进行分布式协作、储存元数据。Chubby是一致性算法Paxos很好的一个实例。相对于Leslie Lamport老先生等大牛学术上的描述，Chubby给出了一个更贴近实战的描述。我这里将最要注意力集中在paxos上。这里的讨论不考虑拜占庭失效问题。

Chubby

集群由若干独立的replica构成，replica在结构和能力上相互对等
replica用paxos来保持log的一致性
replica都有可能离线，然后重新上线。重新上线后，需要保持与其它节点数据的一致
replica的结构

replica有个2个大件：容错的数据库 和 容错的日志。日志部分，每个replica都存有一份本地数据。

replica提交一次value的过程

chubby中的paxos

大体步骤是这样的：

选举一个replica成为coordinator
coordinator选择一个value，广播给所有的replica，这个消息称为accept。replica收到消息后，可以选择同意或者拒绝，并将决定告诉coordinator
当coordinator收到多数replica的同意确认后，就认为一致性达到了，并向相关replica发送commit消息
coordinator失效

因为coordinator可能失效，所以paxos允许同时有多个coordinator。多个replica可以在同时决定称为coordinator并在任意时间执行算法。但是在系统，我们还是要尽量避免coordinator的轮转，因为这样会延缓达到一致。这种灵活的选举制度意味着同时会有不同的replica决定成为coodinator并提交不同的value。cubby就用了paxos中的2种机制来解决：1)给coodinator分配序号 2)限定coodinator能选择的value。

具体这样来实现：

每个replica都记录了它知道的coodinator中最大的编号。这样，它就通过发送过来的accept请求带的编号，拒绝旧coodinator的请求。

当一个replica想成为coordinator的时候，它给自己分配一个唯一的序号。chubby的作者举例了一个序号生成的方法：

有n个replica，每个有一个id，0 <= id <= n - 1。每个replica的序号是 N * n + id，N的初始值是0。
然后将序号广播给其它replica，这称之为propose消息。
其它replica收到propose消息，并将自己之前知道的最大序号返回，这称之为promise消息。如果propose消息中的序号是最大的，replica会承诺不再同意旧coodinator发送的accept消息
如果多数的replica回复的最大的序号小于生成的序号，replica就成为一个coodinator。
paxos算法强迫新的coodinator必须选择和前任相同的value。在2中的promise消息中，包含了每个节点上一次接收到的消息。如果没有收到任何promise消息中包含的value，coordinator可以自行选择value。

有一个常见的优化，选择一个replica作为coordinator之后，就长期不变了，暂称之为master。

对集群不断执行paxos算法，就能达到一致性。在Chubby中，提交一次value到log就触发一次paxos执行。

磁盘失效

chubby在文件中加入校检合，来探测文件损坏。
新replica节点在启动的时候，会在GFS存一个标记，表示自己的是新的。当replica启动时，发现自己磁盘是空的，它就去检测GFS中的marker。这样来区分新replica和磁盘不可访问的情况
Master租约

当有多Master同时存在的时候，会出现master间数据不一致的情况。这样在master上的读，就可能读到脏数据。chubby的解决方法是只要有一个master拥有租约，其它的replica就不能成功地提交value。chubby的replica在租约的有效期内，默认拒绝其它replica的请求。master间断性地提交空的”心跳“value到Paxos集群来刷新租约。

Paxos算法在工程实现时，会遇到非常多的问题，工程实现中很多细节算法并不涉及，同时如何达到较好的性能和稳定性也是一个挑战。Google的分布式锁服务chubby底层就是以Paxos算法作为基础的，这给我们提供了一个很好的范例，展示了如何填补Paxos基本算法在工程实现中的空白之处。

Chubby是以5台独立的机器组成一个cell来提供一个可靠的锁服务，5台机中只要不超过两台出错都不影响服务运行。Chubby的基本架构大致分为三层：

最底层是 log replication，通过Paxos算法保证5台机的log完全一致，同时具备容错性
log层之上就是Key-Value类型的数据存储层，通过下层的log来保证一致性和容错性
存储层之上再实现Chubby提供的锁服务和小文件存储服务
示意图如下

先从Log层说起。

每台机器的数据存储状态可看做一个状态机，只要给定相同的输入序列，状态机就能保证一致的变化，这就是 state machine replication。所以呢，这里的Log层目的就是实现一致的log replication。

但是Paxos算法只能从多个不同proposal value中确定一个一致的value，而这里log需要确定的是无限多个value（提供不间断服务，log无限增长），因此，每个value的确定需要一个Paxos instance。多个instance之间不相干，可以并行进行。当然每个instance也需要一个唯一的instance编号，instance编号按序分配并顺序写入log。把Paxos每个两阶段提交过程Prepare->Promise->Propose->Accept称作一个round，每个Paxos instance内又可能经过多个round才达成一致。这就是Multi-Paxos算法。

上述算法存在大量的优化空间：

多个Proposor的活锁问题会严重影响效率，导致每个instance可能要多个round才能达成一致。
在每个replica上，多个instance的Prepare->Promise阶段可以合并成一个。
因此必须选举一个master作为唯一的proposor。master宕机后其它机器自动再次选举。Paxos算法能够容忍master的“不安全状态”。也就是说，在master切换之时，允许出现短暂的多个master共存，Paxos算法可以保证replica log一致性。
先考虑第二点，如何合并多个instance的Prepare->Promise阶段。原本，多个instance之间是完全独立的，每个instance自己决定每一个round序号，保证在instance内部不重复即可，但现在为了合并Prepare->Promise阶段，多个instance公用一套序号分配，具体做法如下：

当某个replica通过选举获得master资格后，用新分配的编号N广播一个Prepare消息，这个Prepare消息被所有未达成一致的instance和将来还未开始的instance共用。
当Acceptor接收到Prepare后，现在必须对多个instance同时做出回应，这可以封装在一个数据包中，假设最多允许K个instance同时选举，那么：
当前至多有K个未达成一致的instance，将这些未决的instance各自最新accept的value（若没有用null代替）封装进一个数据包，作为Promise消息返回
同时，标记这些未决instance和所有未来instance的highestPromisedNum为N，如果N比它们原先的值大的话。这样，这些未决instance和所有未来instance都不能再accept编号小于N的Proposal。
然后master就可以对所有未决instance和所有未来instance分别执行Propose->Accept阶段，始终使用编号N，如果这个master保持稳定的话，就再也不需要Prepare->Promise了。但是，一旦发现acceptor返回了一个reject消息，说明另一个master启动，用更大的编号M>N发送了Prepare消息，这时自己就要分配新的编号(必须比M更大)再次进行Prepare->Promise阶段。
上述改进的算法，在master稳定的时候，只需要用同一个编号依次执行每个instance的Promise->Accept阶段，每个instance在收到多数派的Accept后，就可以将value写入本地log并广播commit消息，其它replica收到commit消息就可将value写入log。若因为宕机或者网络原因错过了commit消息，可以主动向其它replica查询。在多个master共存的时候，也能保证多个replica的一致性。同时，只要维持多数派机器正常运行，其它机器在任意时刻宕机，都能保证已经commit的value的安全性。

这里面还有一个小的可以改进的地方。如果允许并行执行多个instance，master切换之时，新的master收到的Promise消息可能包含不连续的未决instance，即出现“gap”，state machine replication执行的时候必须按顺序执行log，遇到gap就必须等待gap处的instance达成一致value才能继续执行。为了缩短卡在gap处的时间尽快执行后续log指令，在Promise阶段对gap处提交no-operation指令，最后执行log指令时碰到no-op直接跳过。

对state machine replication的读操作，如果要保证读到最新的数据，必须也为读操作建立一个Paxos instance，序列化写入log，这样对大量的读操作性能就不高。因此，我们需要一个“安全”的选举算法，保证任意时候不出现多个master，这样，就可以对非master机器禁止commit操作，然后将读操作全部集中到master上，这样就能保证读操作始终读到最新的数据。如何实现这个“安全”的选举算法，请点击这里。

实现了一致的log replication，就可以在上层实现一个一致的state machine replication，这就是前边图中的fault-tolerant DB层。DB层在内存中的数据结构这里不做讨论，这里就大致说下snapshot+replay log的实现，这是比较简单的一个问题。

在宕机重启以后，为了恢复state machine 状态，需要将已有的log重新执行一遍，但是如果log积累了很多，那么恢复的时间就非常长，因此需要定期对state machine做一个snapshot存入磁盘，然后就可以将snapshot点之前的log删去。为了避免snapshot阻塞state machine的更新操作，可以建立一个shadow state machine，平常执行log时分别在state machine和shadow上执行，在开始snapshot后，冻结shadow，但不影响原state machine执行，snapshot完成后，再让shadow追赶上最新的log。在新的snapshot完成后才能删除旧的snapshot，这样snapshot执行一半时宕机也不影响恢复。如果state machine占用空间非常大，那么这种简单的整体snapshot方式可能开销就比较大，可以使用更好的办法，这个问题放到别的文章里讨论。

replica宕机后的恢复，分为两种情况，一种是磁盘未损坏，盘上snapshot+log可以恢复到之前某个时间的状态，然后向别的replica索取宕机后缺失的部分，一种磁盘损坏用空盘代替，这时就需要从别的replica索取整个状态，但处理方法是类似的，如果缺的比较少，可能只需要传输近期的log就够了，如果宕机太久或者需要整个重建，那就要传输最近的snapshot+log。

replica宕机重启之后，为了安全起见，暂时不能立即开始参与Paxos instance，需要等待观测到K个Paxos instance成功完成之后，K是允许并发的instance数目。这样就能保证新分配的编号（比观测到的都大）不和自己以前发过的重复。前边提到的一致读操作，也要等到这个时刻到来以后才允许开始。

log是否需要实时commit进磁盘？只要任意时刻保证多数派的机器正常运行，那么宕机后未flush到磁盘的一小部分log也可以从正常的replica中获取，因此不需要实时flush log。这可以极大的提高写盘效率。

在Fault-tolerant DB层之上，就可以比较容易的构建一个分布式锁服务–Chubby，当然需要讨论的问题还有很多，如Chubby中client cache一致性，session状态恢复，keep-Alive机制等等，且听下回分解。