Paxos

Background200 行代码实现 paxos-kv 中介绍了一款十分简洁的分布式 kv 存储实现，它是基于 classic-paxos 实现分布式一致性。在 paxos 的直观解释 中咱们提到，每次写入，也就是每个 paxos 实例须要 2 轮 RPC 实现，效率低。 一个常见的优化就是 mutli-paxos（或 raft），用一次 RPC 对多个实例运行 phase-1；再对每个实例别离运行 phase-2，这样均摊开销是一次 RPC 实现一次写入。 它通过 phase-1 在集群中确定了一个惟一可写的 leader。这种设计在跨机房（或跨云）部署的环境中的缺点是：异地机房的写入就须要 2 个 RTT 能力实现： client → leader → followers → leader → client 也就是说它无奈做到异地多活，在 3 节点的场景里，有 2/3 的写入效率升高到 2 个 RTT。 本文从另一角度登程来解决异地多活的问题，3 机房部署的 3 正本集群中： 任一节点都可写，任一笔写入都能够严格在 1 个 RTT 内实现。这就是明天要介绍的 200 行代码实现 paxos-kv 的改进版: mmp-3: multi-master-paxos 3 正本实现。 同样 show me the code 的准则不能变：本文实现的 3 节点多活代码在: mmp3 异地多活是目前分布式畛域越来越被器重的一个问题，机房正在变成单机，单机房多机分布式在当初大规模部署的业务中曾经满足不了业务的可用性需要了。 简直所有线上环境部署的分布式存储, 都须要跨机房（或者跨云）的部署。而大家也踊跃在解决这些问题： ...

前言paxos 是什么？ 在分布式系统中保障多正本数据强统一的算法。paxos 有啥用？ 没有 paxos 的一堆机器, 叫做分布式；有 paxos 协同的一堆机器, 叫分布式系统。Google Chubby 的作者 Mike Burrows 说过： 这个世界上只有一种一致性算法，那就是Paxos …其余一致性算法, 都能够看做 paxos 在实现中的变体和扩大。另外一个常常被提及的分布式算法是【raft】，raft 的奉献在于把一致性算法落地。因为【Leslie Lamport】的实践很形象，要想把他的实践利用到事实中，还须要工程师齐全把握他的实践再增加工程必要的环节能力跑起来。常常有人问起 raft 和 paxos 的区别，或在实现中应该抉择哪个，在不理解 paxos 之前可能会有这种疑难。对于这个问题, 就像是被问及四则运算和算盘有什么区别，小店老板应该应用四则运算还是用算盘结账一样。记得 Leslie Lamport 2015 年时来了一次北京，那时会场上有人也问了老爷子 paxos 和 raft 有啥区别。老爷子过后给出的答复是：没听过 raft… raft 的外围能够认为是 multi paxos 的一个利用，对于要把握一致性算法的核心内容，从 paxos 动手，更容易去掉无关烦扰，中转问题实质。所以咱们抉择 paxos 作为理解一致性算法的入口，聊开了聊透了。网络上 raft 比 paxos 风行，因为 raft 的形容更直白一些，实际上 raft比 paxos 更简单。raft 具体的解释了“HOW”，短少“WHY”的解释。paxos 从根本上解释分明了“WHY”，但始终短少一份通俗易懂的教程，以至于没有被更宽泛的承受。所以就有了本文，一篇 paxos 入门教程，从根本的分布式中的复制的问题登程，通过逐渐解决和欠缺这几个问题，最初推导出 paxos 的算法。本文分为 2 个局部: 前 1 局部是分布式一致性问题的探讨和解决方案的逐步完善，用人话得出 paxos 算法的过程。如果只心愿了解 paxos 而不打算花太多工夫深刻细节， 只浏览这 1 局部就能够啦。第 2 局部是 paxos 算法和协定的严格形容。这部分能够作为 paxos 原 paper 的实现局部的概括。如果你打算实现本人的 paxos 或相似协定。须要认真理解协定细节，心愿这部分内容能够帮你节俭浏览原 paper 的工夫。图片是 xp 之前做过的 paxos 分享应用的 slides，在此基础上退出了更多口头解释的内容。分布式系统要解决的问题分布式系统要解决的问题 ...

ZooKeeper 介绍ZooKeeper（wiki，home，github） 是用于分布式应用的开源的分布式协调服务。通过暴露简单的原语，分布式应用能在之上构建更高层的服务，如同步、配置管理和组成员管理等。在设计上易于编程开发，并且数据模型使用了熟知的文件系统目录树结构 [doc ]。 共识与 Paxos在介绍 ZooKeeper 之前，有必要了解下 Paxos 和 Chubby。2006 年 Google 在 OSDI 发表关于 Bigtable 和 Chubby 的两篇会议论文，之后再在 2007 年 PODC 会议上发表了论文“Paxos Made Live”，介绍 Chubby 底层实现的共识（consensus）协议 Multi-Paxos，该协议对 Lamport 的原始 Paxos 算法做了改进，提高了运行效率 [ref ]。Chubby 作为锁服务被 Google 应用在 GFS 和 Bigtable 中。受 Chubby 的影响，来自 Yahoo 研究院的 Benjamin Reed 和 Flavio Junqueira 等人开发了被业界称为开源版的 Chubby 的 ZooKeeper（内部实现事实上稍有不同 [ref ]），底层的共识协议为 ZAB。Lamport 的 Paxos 算法出了名的难懂，如何让算法更加可理解（understandable），便成了 Stanford 博士生 Diego Ongaro 的研究课题。Diego Ongaro 在 2014 年发表了介绍 Raft 算法的论文，“In search of an understandable consensus algorithm”。Raft 是可理解版的 Paxos，很快就成为解决共识问题的流行协议之一。这些类 Paxos 协议和 Paxos 系统之间的关系，如下 [Ailijiang2016 ]： ...

CAP 理论是分布式系统设计中的一个重要理论，虽然它为系统设计提供了非常有用的依据，但是也带来了很多误解。本文将从 CAP 诞生的背景说起，然后对理论进行解释，最后对 CAP 在当前背景下的一些新理解进行分析，澄清一些对 CAP 的误解。 CAP 理论诞生的背景CAP 理论的是在“数据一致性 VS 可用性”的争论中产生。CAP 的作者 Brewer 在 90 年代的时候就开始研究基于集群的跨区域系统（实质上是早期的云计算），对于这类系统而言，系统可用性是首要目标，因此他们采用了缓存或者事后更新的方式来优化系统的可用性。尽管这些方法提升了系统的可用性，但是牺牲了系统数据一致性。 Brewer 在 90 年代提出了 BASE 理论（基本可用、软状态、最终一致性），这在当时还不怎么被接受。因为大家还是比较看重 ACID 的优点，不愿意放弃强一致性。因此，Brewer 提出了 CAP 理论，目的就是为了开阔分布式系统的设计空间，通过“三选二”的公式，解放思想，不要只抓着一致性不放。 理解了 CAP 诞生的背景，我们才能更加深入的理解 CAP 理论，以及它带来的启示。“三选二”的观点虽然帮助大家开拓了设计思路，但是也带来了很多误解。下面我们会逐一分析，首先来看一下 CAP 理论的解释。 CAP 理论的经典解释CAP 定理是分布式系统设计中最基础，也是最为关键的理论。它指出，分布式数据存储不可能同时满足以下三个条件。 一致性（Consistency）：每次读取要么获得最近写入的数据，要么获得一个错误。可用性（Availability）：每次请求都能获得一个（非错误）响应，但不保证返回的是最新写入的数据。分区容忍（Partition tolerance）：尽管任意数量的消息被节点间的网络丢失（或延迟），系统仍继续运行。CAP 定理表明，在存在网络分区的情况下，一致性和可用性必须二选一。当网络发生分区（不同节点之间的网络发生故障或者延迟较大）时，要么失去一致性（允许不同分区的数据写入），要么失去可用性（识别到网络分区时停止服务）。而在没有发生网络故障时，即分布式系统正常运行时，一致性和可用性是可以同时被满足的。这里需要注意的是，CAP 定理中的一致性与 ACID 数据库事务中的一致性截然不同。ACID 的 C 指的是事务不能破坏任何数据库规则，如键的唯一性。与之相比，CAP 的 C 仅指单一副本这个意义上的一致性，因此只是 ACID 一致性约束的一个严格的子集。 CAP 理论看起来难理解，其实只要抓住一个核心点就能推导出来，不用死记硬背。在出现网络分区的时候， 如果系统不允许写入，那么意味着降低了系统的可用性，但不同分区的数据能够保持一致，即选择了一致性。如果系统允许写入，那么意味着不同分区之间的数据产生不一致，系统可用性得到保障，即选择可用性。CAP 的新理解CAP 经常被误解，很大程度上是因为在讨论 CAP 的时候可用性和一致性的作用范围往往都是含糊不清的。如果不先定义好可用性、一致性、分区容忍在具体场景下的概念，CAP 实际上反而会束缚系统设计的思路。首先，由于分区很少发生，那么在系统不存在分区的情况下没什么理由牺牲 C 或 A。其次，C 与 A 之间的取舍可以在同一系统内以非常细小的粒度反复发生，而每一次的决策可能因为具体的操作，乃至因为牵涉到特定的数据或用户而有所不同。最后，这三种性质都可以在程度上都可以进行度量，并不是非黑即白的有或无。可用性显然是在 0% 到 100% 之间连续变化的，一致性分很多级别，连分区也可以细分为不同含义，如系统内的不同部分对于是否存在分区可以有不一样的认知。 ...

由于郁白之前写的关于Multi-Paxos 的文章流传非常广, 具体地址: http://oceanbase.org.cn/?p=111 原文提出了一个叫"幽灵复现" 的问题, 认为这个是一个很诡异的问题, 后续和很多人交流关于一致性协议的时候, 也经常会提起这个问题, 但是其实这个问题我认为就是常见的"第三态"问题加了一层包装而已.幽灵复现问题来自郁白的博客:使用Paxos协议处理日志的备份与恢复，可以保证确认形成多数派的日志不丢失，但是无法避免一种被称为“幽灵复现”的现象，如下图所示： LeaderABC第一轮A1-101-51-5第二轮B宕机1-6,201-6,20第三轮A1-201-201-20第一轮中A被选为Leader，写下了1-10号日志，其中1-5号日志形成了多数派，并且已给客户端应答，而对于6-10号日志，客户端超时未能得到应答。第二轮，A宕机，B被选为Leader，由于B和C的最大的logID都是5，因此B不会去重确认6-10号日志，而是从6开始写新的日志，此时如果客户端来查询的话，是查询不到6-10号日志内容的，此后第二轮又写入了6-20号日志，但是只有6号和20号日志在多数派上持久化成功。第三轮，A又被选为Leader，从多数派中可以得到最大logID为20，因此要将7-20号日志执行重确认，其中就包括了A上的7-10号日志，之后客户端再来查询的话，会发现上次查询不到的7-10号日志又像幽灵一样重新出现了。对于将Paxos协议应用在数据库日志同步场景的情况，幽灵复现问题是不可接受，一个简单的例子就是转账场景，用户转账时如果返回结果超时，那么往往会查询一下转账是否成功，来决定是否重试一下。如果第一次查询转账结果时，发现未生效而重试，而转账事务日志作为幽灵复现日志重新出现的话，就造成了用户重复转账。为了处理“幽灵复现”问题，我们在每条日志的内容中保存一个generateID，leader在生成这条日志时以当前的leader ProposalID作为generateID。按logID顺序回放日志时，因为leader在开始服务之前一定会写一条StartWorking日志，所以如果出现generateID相对前一条日志变小的情况，说明这是一条“幽灵复现”日志（它的generateID会小于StartWorking日志），要忽略掉这条日志。第三态问题第三态问题也是我们之前经常讲的问题, 其实在网络系统里面, 对于一个请求都有三种返回结果成功失败超时未知前面两种状态由于服务端都有明确的返回结果, 所以非常好处理, 但是如果是第三种状态的返回, 由于是超时状态, 所以服务端可能对于这个命令是请求是执行成功, 也有可能是执行失败的, 所以如果这个请求是一个写入操作, 那么下一次的读取请求可能读到这个结果, 也可能读到的结果是空的就像在 raft phd 那个论文里面说的, 这个问题其实是和 raft/multi-paxos 协议无关的内容, 只要在分布式系统里面都会存在这个问题, 所以大部分的解决方法是两个对于每一个请求都加上一个唯一的序列号的标识, 然后server的状态机会记录之前已经执行过序列号. 当一个请求超时的时候, 默认的client 的逻辑会重试这个逻辑, 在收到重试的逻辑以后, 由于server 的状态机记录了之前已经执行过的序列号信息, 因此不会再次执行这条指令, 而是直接返回给客户端由于上述方法需要在server 端维护序列号的信息, 这个序列号是随着请求的多少递增的, 大小可想而知(当然也可以做一些只维护最近的多少条序列号个数的优化). 常见的工程实现是让client 的操作是幂等的, 直接重试即可, 比如floyd 里面的具体实现那么对应于raft 中的第三态问题是, 当最后log Index 为4 的请求超时的时候, 状态机中出现的两种场景都是可能的所以下一次读取的时候有可能读到log Index 4 的内容, 也有可能读不到, 所以如果在发生了超时请求以后, 默认client 需要进行重试直到这个操作成功以后, 接下来才可以保证读到的写入结果. 这也是工程实现里面常见的做法对应于幽灵问题, 其实是由于6-10 的操作产生了超时操作, 由于产生了超时操作以后, client 并没有对这些操作进行确认, 而是接下来去读取这个结果, 那么读取不到这个里面的内容, 由于后续的写入和切主操作有重新能够读取到这个6-10 的内容了, 造成了幽灵复现, 导致这个问题的原因还是因为没有进行对超时操作的重确认.回到幽灵复现问题那么Raft 有没有可能出现这个幽灵复现问题呢?其实在早期Raft 没有引入新的Leader 需要写入一个包含自己的空的Entry 的时候也一样会出现这个问题Log Index 4,5 客户端超时未给用户返回, 存在以下日志场景然后 (a) 节点宕机, 这个时候client 是查询不到 Log entry 4, 5 里面的内容在(b)或(c) 成为Leader 期间, 没有写入任何内容, 然后(a) 又恢复, 并且又重新选主, 那么就存在一下日志, 这个时候client 再查询就查询到Log entry 4,5 里面的内容了那么Raft 里面加入了新Leader 必须写入一条当前Term 的Log Entry 就可以解决这个问题, 其实和之前郁白提到的写入一个StartWorking 日志是一样的做法, 由于(b), (c) 有一个Term 3的日志, 就算(a) 节点恢复过来, 也无法成了Leader, 那么后续的读也就不会读到Log Entry 4, 5 里面的内容那么这个问题的本质是什么呢?其实这个问题的本质是对于一致性协议在recovery 的不同做法产生的. 关于一致性协议在不同阶段的做法可以看这个文章 http://baotiao.github.io/2018/01/02/consensus-recovery/也就是说对于一个在多副本里面未达成一致的Log entry, 在Recovery 需要如何处理这一部分未达成一致的log entry.对于这一部分log entry 其实可以是提交, 也可以是不提交, 因为会产生这样的log entry, 一定是之前对于这个client 的请求超时返回了.常见的Multi-Paxos 在对这一部分日志进行重确认的时候, 默认是将这部分的内容提交的, 也就是通过重确认的过程默认去提交这些内容而Raft 的实现是默认对这部分的内容是不提交的, 也就是增加了一个当前Term 的空的Entry, 来把之前leader 多余的log 默认不提交了, 幽灵复现里面其实也是通过增加一个空的当前Leader 的Proposal ID 来把之前的Log Entry 默认不提交所以这个问题只是对于返回超时, 未达成一致的Log entry 的不同的处理方法造成的.在默认去提交这些日志的场景, 在写入超时以后读取不到内容, 但是通过recovery 以后又能够读取到这个内容, 就产生了幽灵复现的问题但是其实之所以会出现幽灵复现的问题是因为在有了一个超时的第三态的请求以后, 在没有处理好这个第三态请求之前, 出现成功和失败都是有可能的.所以本质是在Multi-Paxos 实现中, 在recovery 阶段, 将未达成一致的Log entry 提交造成的幽灵复现的问题, 本质是没有处理好这个第三态的请求。一站式开发者服务，海量学习资源0元起！阿里热门开源项目、机器学习干货、开发者课程/工具、小微项目、移动研发等海量资源；更有开发者福利Kindle、技术图书幸运抽奖，100%中–》https://www.aliyun.com/acts/product-section-2019/developer?utm_content=g_1000047140本文作者：陈宗志阅读原文本文为云栖社区原创内容，未经允许不得转载。 ...