之前学习的 GFS、MapReduce、Bigtable 都有一个共同点：“都是单 master 系统”，这就带来了单点故障的问题。

MapReduce 的单 master 还好，即使 master 出问题了，简单地重跑一下任务就好了，但 GFS 和 Bigtable 都是要长时间提供在线服务的，这样 master 出了问题都很麻烦。所以 GFS 和 Bigtable 的论文都说有一个对应的 Backup Master 机制，通过一个监控机制，当发现 Master 出现问题的时候，就自动切换到数据和 Master 完全同步的Backup Master，作为系统的“灾难恢复”机制。

乍一听，这个做法简单直接。不过如果仔细想一想，这个操作可没有那么容易实现。我们至少会遇到两个问题：

1. 如何做到 Backup Master 与 Master 的完全同步呢？由于网络的不可靠，当两边数据不完全同步时，主从切换会遇到数据丢失的问题。
2. monitor 本身也是一个单点，当 monitor 说 master 挂掉的时候，master 是真挂掉还是只是 monitor 到 master 的网络中断了呢？进而这可能导致脑裂问题。

而这些问题的本质，就是我们接下来要讲解的分布式共识问题。并且这个分布式共识问题的解决，最终会落地成为 Chubby 这个粗粒度的分布式锁方案。我会分三个部分来讲解这个问题：

• 第一部分，是对于分布式共识问题的探讨，我会讲解二阶段提交和三阶段提交。通过这个过程，带你理解分布式一致性，以及CAP三者共存的挑战。这部分是一个基础知识，你会开始对分布式一致性和分布式事务有一个入门性质的认识。
• 第二部分，我们会仔细来聊一下事务里的ACID到底是指什么，并且专门讲解一下Paxos算法，最后我们会一起来看看“可线性化”这个概念。理解了这些问题，你对分布式一致性和分布式事务就能有一个深入的理解了。
• 第三部分，则是对于《The Chubby lock service for loosely-coupled distributed system》的深入讲解，看看Chubby这个系统为什么这么设计，以及在大数据系统下的应用场景。

1. 2PC 与 3PC

这一讲对分布式共识问题进行探讨，讲解二阶段提交和三阶段提交，通过这一讲的学习，你会理解到分布式系统难在哪里，以及对于CAP这三者无法同时满足这一点，有一个切身的体会。

1.1 从两阶段提交到 CAP 问题

GFS 的 master 存在一个同步复制的 backup master，所有在 master 上的操作必须也在 backup 上操作成功才算完成，这其实就相当于每次的成功都是一个分布式事务，要么同时在 master 和 backup 上成功，要么同时失败。

为了解决分布式事务的问题，我们需要一个机制，来使 master 和 backup 的数据写入可以互相协同，这个解决办法就是两阶段提交（2PC，Two Phases Commit）。

两阶段提交的过程其实非常直观，就是把数据的写入，拆分成了提交请求和提交执行这两个不同的阶段，然后通过一个 coordinator 来协调我们的 Master 和 Backup Master。这个过程是这样的：

第一个阶段是提交请求：

协调者会把要提交的事务请求发给所有参与者，所有的参与者要判断自己是否可以执行这个请求，如果不行的话，它会直接返回给协调者，说自己不能执行这个事务。而如果它确定自己可以执行事务，那么，它会先把要进行的事务以预写日志的方式写入下来。

需要注意，这个写入和我们在Bigtable中所说的，写入日志就意味着数据写入成功有所不同。在提交请求阶段写入的WAL日志，还没有真正在参与者这里生效。并且，在写入的日志里，不仅有如何执行事务的日志（redo logs），也有如何放弃事务，进行回滚的日志（undo logs）。当参与者确定自己会执行事务，并且对应的WAL写入完成之后，它会返回响应给协调者说，“我答应你我会执行事务的”。

第二个阶段是提交执行。

当协调者收到各个参与者的返回结果之后，如果所有人都说它们答应执行这个事务。那么，协调者就可以再次发起请求，告诉大家，可以正式执行刚才的那个事务了。等实际的事务执行完成之后，参与者就会反馈给协调者，而协调者收到所有参与者成功完成的消息之后，整个事务就成功结束。

这里需要注意的是，所有的参与者，一旦在提交请求阶段答应自己会执行事务，就不能再反悔了。如果参与者觉得自己不能执行对应的事务，就需要在提交请求阶段就拒绝掉。

比如，如果参与者是一个MySQL数据库，那么如果协调者发起的数据写入请求，可能会违背MySQL里某个表的字段的唯一性约束。这样MySQL数据库就应该在提交请求阶段告诉协调者，而不是等到要实际执行的时候才说。

而协调者这个时候，就会在提交执行阶段，直接发送事务回滚的请求。这个时候，各个参与者写下的undo logs就会派上用场了，各个节点可以回滚刚才写入的数据，整个事务也就没有发生。

如果打一个生活中的比方，这个两阶段提交，就好像我们买卖房子一样，会分成签订合同和实际交房两个阶段。协调者是房屋中介，当他和买卖双方协调完毕，两边都签字确认之后，就不可更改，之后再进行实际交房。

此时此刻，相信聪明的你一定想起了我们之前一直反复会问的一个问题。那就是，在这个两阶段提交的过程中，如果出现了硬件和网络故障，会发生什么事情呢？

• 如果是参与者发生了硬件故障，或者参与者和协调者之间的网络出现了故障。这个时候的硬件或者网络故障，就意味着参与者没有办法知道协调者到底想要继续推进事务，还是想要回滚。在这种情况下，参与者在硬件故障解决之后，会一直等待协调者给出下一步指令。
• 如果协调者之前已经收到了参与者的答应执行事务的响应，那么协调者会一直尝试重新联系参与者。就好像买房合同你已经签了，但是交房时手机没电了，那么房产中介会不断联系你，直到你接起来电话为止。而如果参与者答应执行事务的响应还没有来得及给协调者，那么协调者在等待一段时间没有得到响应之后，会最终决定放弃整个事务，整个事务会回滚。这就好像当房屋交易合同到了你的手里，但是过了一段时间你没有反应。那么房屋中介就自动认为你已经放弃了这笔交易。

那么，这样也就意味着，当硬件出现故障的时候，可能有一个参与者，已经在自己的节点上完成了事务的执行。但是另外一个参与者，可能要过很长一段时间，在硬件和网络恢复之后，才会完成事务。如果这两个参与者是Master和Backup Master，那么在这段时间里，Master和Backup Master之间的数据就是不一致的。

不过，如果外部所有和参与者的沟通，都需要通过协调者的话，协调者完全可以在Backup Master还没有恢复的时候，都告知外部的客户端等一等，之前的数据操作还没有完成。

看完前面这个描述，相信你也明白了。在两阶段提交的逻辑里，是通过一个位居中间的协调者来对外暴露接口，并对内确认所有的参与者之间的消息是同步的。不过，两阶段提交的问题也很明显，那就是两阶段提交虽然保障了一致性，但是牺牲了可用性。无论是协调者，还是任何一个参与者出现硬件故障，整个服务器其实就阻塞住了，需要等待对应的节点恢复过来。

你会发现，两阶段提交里，任何一个服务器节点出问题，都会导致一次“单点故障”。

而且，两阶段提交的事务里，选择回滚的事务其实非常浪费。每个节点都要在不知道其他节点究竟是否可以执行事务的情况下，先把完成事务和回滚事务的所有动作都准备好。这个开销可并不小，而且在这个过程中，协调者其实是一直在等待所有参与者给出反馈的。

所以，两阶段提交的分布式事务的性能往往好不到哪里去，这个在我们的“大数据”的语境下可不是什么好消息。

1.2 三阶段提交和脑裂问题

第一步，我们不用让各个参与者把执行的动作都准备好，也就是不用去写什么undo logs或者redo logs，而是先判断一下这个事务是不是可以执行，然后再告诉协调者。这一步的请求叫做 CanCommit 请求。

第二步，当协调者发现大家都说可以执行的时候，再发送一个预提交请求，在这个请求的过程里，就和两阶段提交的过程中一样。所有的参与者，都会在这个时候去写redo logs和undo logs。这一步的请求呢，叫做 PreCommit 请求。

在CanCommit请求和PreCommit请求阶段，所有参与者都可以告诉协调者放弃事务，整个事务就会回滚。如果出现网络超时之类的问题，整个事务也会回滚。不过，把整个提交请求的阶段拆分成 CanCommit 和 PreCommit 两个动作，缩短了各个参与者发生同步阻塞的时间。

原先无论任何一个参与者决定不能执行事务，所有的参与者都会白白先把整个事务的redo logs和undo logs等操作做完，并且在请求执行阶段还要再做一次回滚。而在新的三阶段提交场景下，大部分不能执行的事务，都可以在CanCommit阶段就放弃掉。这意味着所有的参与者都不需要白白做无用功了，也不需要浪费很多开销去写redo logs和undo logs等等。

另外，在最后的提交执行阶段，三阶段提交为了提升系统的可用性也做了一点小小的改造。在进入最后的提交执行阶段的时候，如果参与者等待协调者超时了，那么参与者不会一直在那里死等，而是会把已经答应的事务执行完成。这个方式，可以提升整个系统的可用性，在出现一些网络延时、阻塞的情况下，整个事务仍然会推进执行，并最终完成。这个是因为，进入到提交执行阶段的时候，至少所有的参与者已经都在PreCommit阶段答应执行事务了。

但是，在一种特殊的情况下，三阶段提交带来的问题会比二阶段更糟糕。这种情况是这样的：

• 所有参与者在CanCommit阶段都答应了执行事务。
• 在PreCommit阶段，协调者发送PreCommit信息给所有的参与者之后，参与者A挂掉了，所以它没有实际执行事务。协调者收到了这个消息，想要告诉参与者B。而这个时候，参与者B和协调者之间的网络中断了。在等待了一段时间之后，参与者B决定继续执行事务。
• 而在这个时候，就会发生一个很糟糕的状况，那就是参与者B的状态和其他的参与者都不一致了。也就是出现了所谓的“脑裂”，即系统里不同节点出现了两种不同的状态。

可以看到，三阶段提交，其实就是在出现网络分区的情况下，仍然尝试执行事务。同时，又为了减少网络分区下，出现数据不一致的情况，选择拆分了提交请求。把提交请求变成了一个小开销的CanCommit，和一个大开销的PreCommit。

这个方法不能不说不好，我们前面指出的那种特殊情况，在传统的数据库事务领域，发生的概率并不高。我们可能只有2~3台服务器，每秒发生的事务也并不多。但是，一旦涉及到“大数据”这三个字，问题又变得不同了。在Bigtable的论文讲解里，我们看到的是一个上千台服务器的集群，每秒的数据库读写次数可以上升到百万次。在这个数据量下，所谓的“很少会发生”，就变成了“必然会发生”。

实际上，三阶段提交，就是为了可用性，牺牲了一致性。相信你看到这里，对 CAP 理论应该就找到一些感觉了。

那么，是不是我们就没有更好的办法了呢？

答案当然不是这样的。其实两阶段提交也好，三阶段提交也好，最大的问题并不是在可用性和一致性之间的取舍。而是这两种解决方案，都充满了“单点故障”，特别是协调者。因为系统中有一个中心化的协调者，所以其实整个系统很容易出现“单点故障”。换句话说，就是整个系统的“容错”能力很差。所以，我们需要一个对单个节点没有依赖的策略，即使任何一个单个节点的故障，或者网络中断，都不会使得整个事务无法推进下去。这也是我们下一讲要深入讲解的 Paxos 算法。

2. 事务与 Paxos

2PC 与 3PC 存在的单点故障与同步阻塞问题使得分布式系统的优势没有发挥出来，所以，我们需要一个不依赖于单点且不同步阻塞的解决方案，这个方案就是 Paxos 算法。同时，这一节还会介绍数据库领域所说的“事务”到底是什么，以及当我们处于一个分布式环境下，又会面临什么样的挑战。

在学完这一讲后，你会搞清楚三件事：

1. 数据库领域的ACID具体是指什么，里面的隔离性具体分成哪几种隔离等级？
2. 分布式系统场景下，事务怎么来保障系统的“隔离性”？
3. Paxos算法，究竟是怎么一回事儿？

2.1 理解 ACID

前面讲 2PC 是用于解决 master 与 backup 同步的问题，但其实 2PC 也可以用在分布式事务中，比如跨数据库的银行转账业务。

事务性无论是在单机的环境下，还是分布式的环境下，都是非常重要、不可或缺的一个性质。那么，我们通常是使用ACID这四个字母，来描述事务性需要满足的4个属性。下面我们来看看它们各自的含义。

• 原子性（Atomicity），也就是一个事务不能分成更小的粒度。在事务里，也就是几个操作要么同时发生，如果任何一个失败，整个就应该回滚。前面的两阶段提交，其实就是为了保障事务的原子性。但是在三阶段提交中，我们可能就会失去事务的原子性。
• 一致性（Consistency），这个更多是一个应用层面的属性。我们需要确保应用里面的数据是一致的。典型的例子就是银行转账，两个人买卖房屋的银行账户变动，在应用层面，一个人减少的金额和另一个人增加的金额应该同时发生。这样数据才具有一致性，不然的话，就会凭空多出钱来或者少钱。本质上，这个例子就是利用了数据库的事务性，实现了应用层面的数据一致性。而数据库里的唯一约束、外键约束，都属于数据的一致性要求。
• 隔离性（Isolation），它需要解决的问题是，当有多个事务并发执行的时候，相互之间应该隔离，不能看到事务执行的中间状态。这个是我们今天要重点深入剖析的一个问题，也是 Paxos 算法的一个起点。
• 持久性（Durability），就是一旦事务成功提交，对应的数据应该保存在硬盘中，并且在硬件故障或者系统崩溃的情况下也不会丢失。持久性看起来简单，好像把数据往硬盘里一写就完事儿了，但是要真正做到并不容易。比如，如果我们的硬盘坏了，该怎么办呢？GFS里面的Master、Backup Master以及数据的三份副本，都是为了保障数据的持久性。

在数据库的ACID属性里面，A、C和D看起来是显而易见的。但是这个隔离性I，就值得说道说道了。我们之前看到的事务的案例，是一个单独的事务。那么， 如果有两个事务想要同时发生，并且它们想要读写的数据记录之间有重合，该怎么办？对于房屋交易的例子来说，如果不实施隔离性，则可能会出现房屋超卖的现象。

一般数据库的隔离级别，会分成四种：

未提交读（Read Uncommitted）

也就是事务之间完全不隔离。它的问题在于，在一个事务执行的过程中，读取的数据，可能会来自一个会回滚的事务。

未提交读不太会在真实的系统中使用，因为本质上，它会在事务中读到脏数据。

提交读（Read Committed）

这个隔离级别比未提交读强一些，是事务只去读取已经提交了的事务。不过在事务里，当其他事务更新了数据，事务里的多次读取可能会读到不同的结果。

这个隔离级别一般也不太会使用，因为这样一个事务中两个完全相同的读操作，会读到完全不同的数据，也就是会出现“幻读”。

可重复读（Repeatable Read）

这个隔离级别是为了解决刚才的幻读问题。在可重复读的环境下，一个事务A一旦开始，该事务里读到的数据，都是事务开始之前已经提交的数据。如果在事务A的执行过程中，数据库里有新的事务B提交了，那么虽然数据库里的数据已经改变了，但是在事务A的执行过程中，还是只会当成这个事情没有发生。这个隔离方式，就会带来我们刚才所说的一房两卖的问题。

可串行化（Serializable）

这个是最严格的隔离方式。所有的事务，虽然提交的时候可以是并行的，但是在实际执行的过程中，在外部看来是按照一个确定的顺序一个一个执行的。

可以看到，很自然地，我们希望数据库的隔离级别最好都是“可串行化”的。这样，应用开发程序就会很容易写，不需要自己去考虑对特定资源加锁，只要采用事务和逻辑正确的代码，就能完成想要解决的问题。

2.2 摆脱单点故障的 Paxos

了解完了数据库的事务性，特别是里面的“隔离性”，我们发现啊，使用两阶段提交来实现GFS的Master和Backup Master的同步写入，好像有点杀鸡用牛刀的感觉。

为什么这么说呢？那是因为，对于GFS的Master的操作，其实并没有有关隔离性的需求。在这个同步复制的过程中，我们需要的并不是让GFS的文件系统的操作支持事务，比如“检查目录A是否存在，存在的话，在里面新增文件B”。文件系统通常并不需要这三个动作保持事务性，即使需要，也是通过一个外部锁来实现。我们对GFS的Master操作，最抽象来看，就是写日志。而Backup Master起到的作用，就是同步复制日志，每一条日志，都是对文件系统的一次操作。我们可以把这样的一条条操作看成是一个个事件，每一次事件，都让整个文件系统的状态进行了一次改变。所以本质上，这就是一个状态机（State Machine）。

而让Backup Master和Master保持同步来保持高可用性，其实就是要在两个状态机之间做同步复制。所以这个问题，也就变成了一个状态机复制问题（replicated state machine） (opens new window)。

在这个问题里，解决的并不是隔离性里的“可串行化”问题，而是分布式共识里的“可线性化”（Linearizability）问题。所谓的可线性化，就是任何一个客户端写入数据成功之后，再去读取数据，一定能读取到刚才写入的数据。

事实上，所有异步复制的主从系统，如果我们去读从库，都会遇到这样线性不一致的情况。而为了保障线性一致性，或者说系统的可线性化，我们必须让主从节点之间是同步复制的。而要做到高可用的同步复制，我们就需要 Paxos 这样的共识算法。

2.3 并不可行的多协调者

回想一下之前说的两阶段提交，我们可不可以，通过提供多个协调者来避免单点故障呢？不太行，因为这容易发生操作顺序的错乱。我们以两个协调者A和B，以及两个参与者C和D为例，如果A要在C和D上，删除目录/data/bigdata，而B则是要在C和D上，把目录/data/bigdata改名成/data/bigdatapaper。因为是分布式的网络环境，那么可能会出现在C这里，A的请求先到，B的请求后到，/data/bigdata的目录已经被删除了，所以改名也失败了；而在D这里，两个顺序是反过来的，那么D这里的/data/bigdata目录已经改名成功，而删除则失败了。C和D之间的数据也就不一致了。

简单采用两个协调者的办法是行不通的。核心挑战在于，多个协调者之间没有办法相互协调，达成一个两个操作在顺序上的共识。而 Paxos，想要解决的就是这样的问题。

2.4 Paxos 算法中的协调过程

我们希望啊，我们在写入数据的时候，能够向一组服务器发起请求，而不是一个服务器。这组服务器里面的任何一个挂掉了，我们都能向里面的另外一台服务器发送请求，并且这组服务器里面的每一台，最终写入并执行日志的顺序是一样的。

在Paxos算法里，我们把每一个要写入的操作，称之为提案（Proposal）。接受外部请求，要尝试写入数据的服务器节点，称之为提案者（Proposer），比如说，我们可以让一组服务器里面有5个提案者，可以接受外部的客户端请求。

在Paxos算法里，并不是提案者一旦接受到客户端的请求，就决定了接下来的操作和结果的，而是有一个异步协调的过程，在这个协调过程中，只有获得多数通过（accept）的请求才会被选择（chosen）。这也是为什么，我们通常会选择3个或者5个节点这样的奇数数字，因为如果是偶数的话，遇到2:2打平这样的事情，我们就没法做出判断了。

这个投票机制也是Quorum这个名字的由来，因为Quorum在英文里的意思就是法定人数。一旦达到了过半数，那么对应的请求就被通过了。

既然我们的提案者已经准备好5个节点了，我们不妨就复用这5个节点，让这5个节点也作为Quorum，来承担一个叫做接受者（Acceptor）的角色。

2.4.1 给提案编号

首先是每一个请求，我们都称之为一个“提案”。然后每个提案都有一个编号，这个编号由两部分组成。高位是整个提案过程中的轮数（Round），低位是我们刚才的服务器编号。每个服务器呢，都会记录到自己至今为止看到过，或者用到过的最大的轮数。

那么，当某一台服务器，想要发起一个新提案的时候，就要用它拿到的最大轮数加上1，作为新提案的轮数，并且把自己的服务器编号拼接上去，作为提案号发放出去。并且这个提案号必须要存储在磁盘上，避免节点在挂掉之后，不知道最新的提案号是多少。

通过这个方式，我们就让这个提案号做到了两点：

• 首先是不会有重复的提案号，不会存在两个服务器发出相同提案号的情况；
• 其次是提案号能够按照数值大小，区分出先后和大小。即使是同一状态下不同服务器发出的提案，也能比较大小。

2.4.2 Prepare 阶段

那么，当提案者收到一条来自客户端的请求之后，它就会以提案者的身份发起提案。提案包括了前面的提案号，我们把这个提案号就叫做 M。这个提案会广播给所有的接受者，这个广播请求被称为 Prepare 请求。

而所有的 Acceptor 在收到提案的时候，会返回一个响应给提案者。这个响应包含的信息是这样的：

• 首先，所有的接受者一旦收到前面的 Prepare 请求之后，都会承诺它接下来，永远不会接受提案号比当前提案号 M 小的请求；
• 其次，如果接受者之前已经接受过其他提案的内容（假设是 X）了，那么它要存储下已经接受过的内容和对应的提案号。并且在此之后，把这个提案号和已经接受过的内容 X，一起返回给提案者。而如果没有接受过，就把内容填为 NULL。

这样一个来回，就称之为 Paxos 算法里的 Prepare 阶段。要注意，这里的接受者只是返回告知提案者信息，它还没有真正接受请求。这个过程，本质上是提案者去查询所有的接受者，是否已经接受了别的提案。

2.4.3 Accept 阶段

当提案者收到超过半数的响应之后呢，整个提案就进入第二个阶段，也称之为 Accept 阶段。提案者会再次发起一个广播请求，里面包含这样的信息：

• 首先仍然是一个提案号，这个提案号就是刚才的 Prepare 请求里的提案号 M；
• 其次，是提案号里面的内容，一般我们也称之为提案的值。不过这个值，就有两种情况了。

第一种情况，是之前接受者已经接受过值了。那么这里的值，是所有接受者返回过来，接受的值当中，提案号最大的那个提案的值。也就是说，提案者说，既然之前已经做出决策了，那么我们就遵循刚才的决策就好了。

而第二种情况，如果所有的提案者返回的都是NULL，那么这个请求里，提案者就放上自己的值，然后告诉大家，请大家接受我这个值。

那么接受到这个Accept请求的接受者，在此时就可以选择接受还是拒绝这个提案的值。通常来说：

• 如果接受者没有遇到其他并发的提案，自然会接受这个值。一旦提案者收到超过半数的接受者“接受”的请求。那么它就会确定，自己提交的值被选定了。
• 但也有可能，接受者刚才已经答应了某个新的提案者说，不能接受一个比提案号N早的请求。而N>M，所以这个时候接受者会拒绝M。

• 不管是接受还是拒绝，这个时候接受者都会把最新的提案编号N，返回给提案者。
• 还是要注意，这个时候接受者接受了请求，并不代表这个请求在整个系统中被“选择”了。

提案者还是会等待至少一半的接受者返回的响应。如果其中有人拒绝，那么提案者就需要放弃这一轮的提案，重新再来：生成新的提案号、发起Prepare请求、发起Accept请求。而当超过一半人表示接受请求的时候，提案者就认为提案通过了。当然，这个时候我们的提案虽然没有变，但是提案号已经变了。而当没有人拒绝，并且超过一半人表示接受请求的时候，提案者就认为提案通过了。

2.5 可线性化和共识算法

可以看到，在Paxos算法这个过程中，其实一直在确保一件事情，就是所有节点，需要对当前接受了哪一个提案达成多数共识。

如果有多个Proposer同时想要向这个一致性模块写入一条日志，那么最终只会有一条会被成功写入，其余的提案都会被放弃。多个并发在多个Proposer上发生的写入请求，互相之间需要去竞争一次成功提案的机会。

通过Paxos算法，我们能够确保所有服务器上写入日志的顺序是一样的，但是我们并不关心是不是某个提案者会比另一个提案者先写入。毕竟这些请求都是在网络上并发进行的，我们也无法规定谁先谁后。

而在一次Paxos算法完成之后，被放弃的提案可以重新再来。这个节点如果还想要继续写入日志，可以在下一次Paxos算法的过程中，重新开始整个Paxos算法的过程。这样，在多个节点同时接受外部请求的环境下，我们不会出现多个节点之间，执行的日志顺序不一样的情况。

不过，相信你也发现了Paxos算法的一个问题，那就是开销太大了。无论是否系统里面出现并发的情况，任何一个共识的达成，都需要两轮RPC调用。而且，所有的数据写入，都需要在所有的接受者节点上都写入一遍。

所以，虽然Paxos算法帮助我们解决了单点故障，并且在没有单点的情况下，实现了共识算法，确保所有节点的日志顺序是相同的。但是，原始的Paxos算法的性能并不好。只是简单地写入一条日志，我们就可能要解决多个Proposer之间的竞争问题，有可能需要有好几轮的网络上的RPC调用。

当然，我们可以用各种手段在共识算法层面进行优化，比如一次性提交一组日志，而不是一条日志。这也是后续Multi-Paxos这些算法想到的解决方案。

但是，如果我们往一个数据库同步写入日志都要通过Paxos算法，那么无论我们怎么优化，性能都是跟不上的。 根本原因在于，在Paxos算法里，一个节点就需要承接所有的数据请求。虽然在可用性上，我们没有单点的瓶颈了，但是在性能上，我们的瓶颈仍然是单个节点。

事实上，我们接下来要讲解的Chubby，正是看到了Paxos算法的性能制约而搭建起来的。想要知道Chubby究竟是如何规避Paxos算法目前的性能瓶颈的，那就请你接着和我一起来学习下节课的内容吧。

3. 分布式锁 Chubby

前面两节我们都在尝试做一件事情：在 master 与 backup 之间保持数据的同步复制。两阶段提交和 Paxos 算法都是为了做到这一点。而我们要去保障 master 与 backup 之间的同步复制也是为了实现一个目标：提高整个系统的高可用性。因为系统中只有一个Master节点，我们希望能够在Master节点挂掉的时候，快速切换到另外一个节点，所以我们需要这两个节点的数据是完全同步的。不然的话，我们就可能会丢失一部分数据。

这一节来看一下 Chubby 这个系统是怎么一回事，通过这一讲，可以学习到：

• Chubby这个分布式锁系统是怎么一回事儿，它和Paxos算法的关系是什么；
• GFS和Bigtable这样的系统，是如何通过Chubby来保障可用性和一致性的；
• 在系统设计层面，如何尽可能在设计上降低长期协同开发的成本。

3.1 通过 Chubby 转移可用性和“共识”问题

无论是GFS还是Bigtable，其实都是一个单Master的系统。而为了让这样的系统保障高可用性，我们通常会采用两个策略：

1. 第一个，是对它进行同步复制，数据会同步写入另外一个Backup Master，这个方法最简单，我们可以用两阶段提交来解决。
2. 第二个，是对 Master 进行监控，一旦Master出现故障，我们就把它切换到Backup Master就好了。

其实，解决这两个问题的答案，就是 Chubby，也就 Paxos 算法。Chubby 具体的技术实现并不简单，但是思路却非常简单。那就是，我们的“共识”并不需要在每一个操作、每一条日志写入的时候发生，我们只需要有一个共识，确认哪一个是 Master 就好了。

这样，系统的可用性以及容错机制，就从原先的系统里被剥离出来了。我们原先的系统只需要 master，即使是做同步数据复制，也只需要通过两阶段提交这样的策略就可以了。而一旦出现单点故障，我们只需要做一件事情，就是把故障的节点切换到它同步备份的节点就行。

而我们担心的脑裂问题，通过 Paxos 算法来解决就好了。只要通过Paxos算法，让一个一致性模块达成共识，当前哪一个是Master就好，其他的节点都通过这个一致性模块，获取到谁是最新的Master即可。而且，这个一致性模块本身会有多个节点，比如5个节点，另外我们在部署的时候，还会把它们放到不同的机架上，也就是不同的交换机下。这样一来，一致性模块里单个节点出现故障，也并不会影响这个一致性模块对外提供服务。

那么，在 Chubby 这个系统里，它其实针对 Paxos 做了封装，把对外提供的接口变成一个锁。这样，Chubby 就变成了一个通用的分布式锁服务，而不是一个 Paxos 的一致性模块。在锁服务下达成的共识，就不是谁是 Master 了，而是哪一台服务器持有了 Master 的锁。对于应用系统来说，谁持有 Master 的锁，我们就认为这台服务器就是 Master。

事实上，把Chubby对外暴露的接口，变成一个分布式锁服务，Google是经过深思熟虑的。对于锁服务来说，大部分工程师都是非常熟悉的，无论是MySQL这样的关系数据库，还是Redis这样的KV数据库，或者是Java标准库里的Lock类，都是我们经常使用的开发工具。

但大部分工程师并没有听说过 Paxos 算法，之前 MapReduce 论文就说过：“一个好的分布式系统的设计，就是要让使用系统的开发人员意识不到分布式的存在。”那么，通过把Paxos协议封装成一个分布式锁，就可以让所有开发人员立刻上手使用，而不需要让每个人都学习Paxos和共识问题，从而能够更容易地在整个组织的层面快速开发出好用的系统。

而且，Chubby这个锁服务，是一个粗粒度的锁服务。所谓粗粒度，指的是外部客户端占用锁的时间是比较长的。比如说，我们的 master 只要不出现故障，就可以一直占用这把锁。但是，我们并不会用这个锁做很多细粒度的动作，不会通过这个分布式的锁，在 Bigtable 上去实现一个多行数据写入的数据库事务。

这是因为，像Master的切换这样的操作，发生的频率其实很低。这就意味着，Chubby负载也很低。而像Bigtable里面的数据库事务操作，每秒可以有百万次，如果通过Chubby来实现，那Chubby的负载肯定是承受不了的。要知道，Chubby的底层算法，也是Paxos。我们上一讲刚刚一起来了解过这个算法，它的每一个共识的达成，都是需要通过至少两轮的RPC协商来完成的，性能肯定跟不上。

事实上，在Bigtable里，Chubby也主要是被用来做四件事情，第一个是Master的高可用性切换；第二个是存储引导位置（Bootstrap Location），让客户端能够找到METADATA数据的存储位置；第三个是Tablet和Tablet Server之间的分配关系；最后一个是Bigtable里表的Schema。可以看到，Chubby存储的这些数据都是很少变化，但是一旦丢失就会导致数据不一致的元数据。

那么相信到这里，你对Chubby在整个分布式系统中的作用应该就弄明白了。Chubby并不是提供一个底层的Paxos算法库，然后让所有的GFS、Bigtable等等，基于Paxos协议来实现数据库事务。而是把自己变成了一个分布式锁服务，主要解决GFS、Bigtable这些系统的元数据的一致性问题，以及容错场景下的灾难恢复问题。

GFS和Bigtable这些系统，仍然会采用单个Master，然后对数据进行分区的方式，来提升整个系统的性能容量。但是在关键的元数据管理，以及Master节点挂掉切换的时候，会利用Chubby这个分布式锁服务，来确保整个分布式系统是有“共识”的，避免出现脑裂问题。

3.2 Chubby 的系统架构

理解完了Chubby在整个分布式系统中的作用，我们下面就来深入看一下，整个Chubby的系统是怎么样的。

3.2.1 Chubby 的系统架构

首先，Chubby 这个系统也是有 Master 的。

在Chubby里，它自己的多个节点，会先通过“共识”算法，确认一个Master节点。这个Master节点，会作为系统中唯一的一个提案者（Proposer），所有对于Chubby的写入数据的请求，比如获取某个锁，都会发送到这个Master节点，由它作为提案者发起提案，然后所有节点都会作为接受者来接受提案达成共识。

只有一个提案者带来的好处就是，大部分时间，我们不太会因为两个Proposer之间竞争提案，而导致需要很多轮协商才能达成一致的情况。

那看到这里你可能会问了，如果Chubby的Master挂掉了怎么办呢？

不要紧，我们可以通过剩下的节点，通过共识算法再找一个Master出来。而且如果是因为网络故障，导致有两个Master的话，也会很快通过共识算法确定一个Master出来。另外，两个Master其实只是一致性模块里的两个提案者，即使两边都接受外部请求，也都会通过共识算法，只选择一个值出来。

在论文里面，Master的生命周期被称之为租期（lease）。也就是说，Master发起的共识算法达成的共识，是在一段时间T之内，它是Master。而只要Master不崩溃，一般它都会在这个T的时间到期之前，进行续租。而如果Master崩溃了，当T的时间到了，那么所有节点都可以发起自己是Master的一次提案，最终确认一个新的Master。

可以看到，虽然Paxos这样的共识算法其实是不需要单一的Master节点的。但是为了实际应用中的效率问题，我们会采用选举出一个Master的办法，来让整个系统更加简化。

对于Chubby的整个服务器端来说，我们可以把它看成一个三层的系统。最底层，是一个Paxos协议实现的同步日志复制的系统，也就是我们上一讲所说的状态机复制的系统。上面一层，就是通过这个状态机实现的数据库 了，Google是直接采用了BerkeleyDB作为这个数据库。换句话说，Chubby是通过Paxos在多个BerkeleyDB里，实现数据库的同步复制。在BerkeleyDB之上，才是由Chubby自己实现的锁服务。

除了服务器端，Chubby还给所有想要使用Chubby的应用提供了一个客户端。客户端会通过DNS拿到所有的Chubby的服务端的节点，然后可以去里面任何一个节点询问，哪一个是Master。无论是读还是写的请求，客户端都是通过访问Master来获取的。

对于数据写入的请求，Master会作为刚才我们说过的提案者，在所有的Chubby服务器节点上通过Paxos算法进行同步复制。而对于读请求，Master直接返回本地数据就好，因为所有服务器节点上的数据是有共识的。

3.2.2 Chubby 对外提供的接口

既然Chubby的底层存储系统，是BerkeleyDB这样一个KV数据库，那么我们就可以通过它做很多事情了。Chubby对外封装的访问接口，是一个类似于Unix文件系统的接口。使用这个形式，同样也降低了使用Chubby的用户的门槛。毕竟每个工程师都熟悉用ls命令，去查询目录下的子目录和文件列表。

Chubby里的每一个目录或者文件，都被称之为一个节点（node）。外部应用所使用的分布式“锁”，其实就是锁在这个节点上。哪个客户端获得了锁，就可以向对应的目录或者文件里面写入数据。比如谁是真正的Master，就是看谁获得了某个特定的文件锁。

所有的这些其实是目录和文件的“节点”，在Chubby中会分成永久（permanent）节点和临时（ephemeral）节点两种：

• 对于永久节点来说，客户端需要显式地调用 API，才能够删除掉。比如Bigtable里面，Chubby存放的引导位置的信息，就肯定应该使用永久节点。
• 对于临时节点来说，则是一旦客户端和服务器的Session断开，就会自动消失掉。一个比较典型的使用方式，就是我们在 Bigtable 中所说的 Tablet Server 的注册。

比如说，我们可以用一个Chubby里面的目录 /bigtable/tablet_servers，来存放所有上线的 Tablet Server，每个Tablet Server都可以在里面创建一个文件，比如 /bigtable/tablet_servers/ts1、/bigtable/tablet_servers/ts2 … /bigtable/tablet_servers/ts100 这样排列下去。

Tablet Server会一直和Chubby之间维护着一个会话，一旦这个会话结束了，那么对应的节点会被自动删除掉，也就意味着这个节点下线无法使用了。这样，由于网络故障导致的Tablet Server下线，也会表现为会话超时，由此一来，它就很容易在Chubby这样的服务里面实现了。

回顾一下我们之前讲过的Bigtable的论文，Bigtable的Master一旦发现这种情况，就会尝试去Chubby里面获取这个节点对应的锁，如果能够获取到，那么说明Master到Chubby的网络没有问题，Master就会认为是Tablet Server节点下线了，它就要去调度其他的Tablet Server，去承接这个下线了的服务器之前服务的那些tablet。Master只需要监控/bigtable/tablet_servers这个目录，就能够知道线上有哪些Tablet Server可供使用了。

而为了减少Chubby的负载，我们不希望所有想要知道Chubby里面节点变更的客户端，都来不断地轮询查询各个目录和文件的最新变更。因为Chubby管理的通常是各种元数据，这些数据的变更并不频繁。所以，Chubby实现了一个事件通知的机制。

这是一个典型的设计模式中的观察者模型（observer pattern）。客户端可以注册它自己对哪些事件感兴趣，比如特定目录或者文件的内容变更，或者是或者是某个文件或者目录被删除了，一旦这些事件发生了，Chubby就会推送对应的事件信息给这些应用客户端，应用客户端就可以去做类似于调度Tablet Server这样的操作了。

3.2.3 Chubby 作为分布式锁的挑战

现在我们知道，每一个Chubby的目录或者文件，就是一把锁。那么是不是我们有了锁之后，分布式共识的问题就被解决了呢？如果你是这么想的，那么你肯定还没有在网络延时上吃到足够的亏。

首先，作为分布式锁，客户端去获取的锁都是有时效的，也就是它只能占用这个锁一段时间。这个和我们前面提到的Chubby的Master的“租约”原理类似，主要是为了避免某个客户端获取了锁之后，它因为网络或者硬件原因下线了。

这样乍一听起来，我们只要给锁的时间设置一个时效就好了。不过，一旦涉及到不可靠的网络，事情就没有那么简单了。

Chubby的论文里给出了这样一种情况，我们可以一起来看一下：

• 我们有一个应用的客户端A，获取了某个Chubby里面的锁，比方说/chubby/geektime这个文件。A对这个节点的租期呢，是一段时间T。而这个锁，是告诉我们这个客户端可以往外部的Bigtable数据库的一个geektime的行，写入数据。
• 在获取到了锁之后，过了一小段时间，A仍然还持有这个锁，于是A就向Bigtable发起一个请求X，想要往geektime这个行里面去写入数据。
• 但是这个时候，可能A和Bigtable之间的网络非常拥堵，这个请求花了比较长的时间才到达Bigtable。
• 而当这个写入请求X还在路上的时候，客户端A的“租约”到期了。这个时候，另外一个客户端B获取到了对应的锁，然后它往这个Bigtable的geektime的行里，写入了数据Y。
• 当Y被写入之后，请求X才到了Bigtable。但是Bigtable并不知道谁拥有锁，它只会认为应用层面已经通过锁，实现了对于资源的保护。那么，之前客户端A的数据会覆盖掉客户端B写入的数据。但是这个情况肯定是我们不愿意接受的，因为对于客户端B来说，我明明已经持有了锁，为什么我写入的数据会被此时此刻没有锁的人覆盖掉呢？而且，客户端A的数据也是更早版本的数据。

这个就好像你租了一个仓库，租期是一年。你呢，在租期快要到期的时候，向仓库里发了一批货。但是因为物流延误，货在路上耽搁了。当你的仓库租期到期的时候，房东把仓库租给了别人，别人也已经往仓库里面放了他自己的货物。而这个时候，你的货到了，但是因为仓库的门卫并不知道房东把仓库租给了谁，它不会检查你是不是还租着仓库，就直接把你的货物也入库了，而把新的租客的货物给“覆盖”掉了。

当然，Chubby也解决了这个问题，它主要是通过两种方式来解决的。

首先是锁延迟（lock-delay）

也就是当客户端A的“租约”不是正常到期由客户端主动释放的话，它会让客户端继续持有这个锁一段时间。这很好理解，如果是客户端主动释放的话，意味着它已经明确告诉Chubby，我不会再往里面写入数据。而没有主动释放，很有可能是还有请求在网络上传输，我们就再稍微等一会儿。

而如果等一会儿还是没有过来，那么Chubby就会再把锁释放掉。这个就好像你在现实生活中租房子，租约要到期了，如果你是主动和房东说你不再续租了，房东自然可以立刻租给别人。但是可能你因为出差或者疫情隔离，没有来得及和房东沟通，房东也会善意地多等你几天，直到一段时间之后你还是失去联系了，才再会去租给别人。

其次是锁序列器（lock-sequencer）

它本质上是一个乐观锁 (opens new window)，或者在很多地方也叫做 Fencing 令牌。这种方式是这样的：客户端在获取 Chubby 的锁的时候，就要拿到对应的锁的序号，比方说 23。在发送请求的时候，客户端会带上这个序号。而当 Chubby 把锁给了别的客户端之后，对应的锁的序号会变大，变成了 24。而我们对应的业务服务，比如 Bigtable 呢，也要记录每次请求的锁序列号，通过对比锁序列号来确定是否会有之前的锁，尝试去覆盖最新的数据。当遇到这种情况的时候，我们姗姗来迟的来自上一个锁的客户端请求，就会被业务服务拒绝掉。

所以你会看到，Chubby的每个锁，除了文件、目录本身，以及ACL权限这样的元数据之外，还有这样四个编号：

• 实例编号（instance number）：当这个“节点”每次被创建的时候自增。
• 文件内容编号（content generation number）：当文件内容被写入的时候会自增。
• 锁编号（lock generation number）：当锁从“释放”（Free）的状态转变为“持有”（Held）的状态的时候自增。
• ACL 编号（ACL generation number）：当这个“节点”的权限ACL信息更新的时候会自增。

这样，通过锁编号，我们就很容易实现前面所说的锁序列器的功能。其他的编号，也都是实现了数据的“版本”功能。这个也使得我们在不确定的网络情况下，能确保写入的数据是按照我们期望的顺序。如果我们尝试拿过时“版本”的锁来更新最新的数据，那么更新就不会成功。

3.2.4 留给你自己读的 Caching 部分

最后，和其他的分布式系统一样，为了提升性能，Chubby也会在客户端里维护它拿到的数据缓存。Chubby也有像代理、分区等等其他一系列的机制，来让整个系统更容易扩展，不过这些，就不是Chubby在整个大数据领域的核心和重点功能了，我把这部分内容留给你自己去好好研读啦。

小结

我们漫长的旅程终于告一段落了。在过去三讲里，我们从GFS的Master的“同步复制”这个需求出发，逐步了解了两阶段提交、三阶段提交，以及Paxos算法，并且最终在今天一起学习完了Chubby的论文。

我们能看到，Google并没有非常僵化地在所有的分布式系统里面，都简单通过实现一遍Paxos算法，来解决单点故障问题，而是选择通过Chubby实现了一个粗粒度的锁。这个锁，只是帮助我们解决大型分布式系统的元数据管理的一致性，以及Master节点出现故障后的容错恢复问题。

因为大型分布式系统，并不是时时刻刻都会出现数据不一致的风险的。把“哪一个是Master”这个问题通过共识算法来解决，我们在系统的容错恢复上，就避免了出现两个Master的情况。而Chubby也是一个非常适合拿来管理非常重要的元数据的地方，这一点我们在Bigtable的论文里，其实已经看到了。

Chubby的系统本身，其实是通过Paxos实现了多个BerkeleyDB之间日志的同步复制。Chubby相当于是在BerkeleyDB之上，封装好了一个Unix文件系统形式的对外访问接口。并且，为了减轻自己的负载，Chubby还实现了一个观察者模式，外部的客户端可以监听Chubby里的某一个“目录”或者“文件”，一旦内容变更，Chubby会通知这些客户端，而不需要客户端反复过来轮询。这个也是为了提升系统的整体性能。

另外，由于网络延时的存在，即使我们的客户端获取到了锁，当写入请求到达锁对应的业务系统的时候，可能这个锁已经过期了。这个会导致我们错误地用旧数据去覆盖新数据，或者说，在没有获取对应资源的锁的情况下，写入了数据。不过，Chubby通过锁延迟和锁序列器 这两种方式解决了这个问题。

可以看到，和所有之前Google发布的系统一样，Chubby并没有发明什么新的理论，而是巧妙地通过系统工程，来保障系统的可用性。并且在这个过程中，Google选择了尽可能使用各种一般工程师都熟悉的编程模型。Google没有开发一个Paxos库，让所有工程师去学习分布式共识算法，而是提供了一个分布式锁服务Chubby。而在Chubby里，提供的也是我们熟悉的类似Unix的文件系统、观察者模式这样，普通工程师耳熟能详的编程模型。

这一点，在大型组织中设计基础设施的时候非常关键。 我们设计系统的时候，不能光考虑对应系统的功能，如何让整个系统对于其他团队的开发者和使用者易用，也非常关键。我们不仅在Chubby这个系统里看到了这一点，从GFS、MapReduce、Bigtable这些系统里面也能看到这个设计思路，其实这是一个一以贯之的设计思想。

到这里，我们对于大数据论文的基础知识部分就已经学习完了。接下来，我们就要迈入对于大数据论文里面关于数据库部分的学习啦。