关于分布式:数据系统分布式系统一致性与共识

为了构建容错零碎，最好先建设一套通用的形象机制和与之对应的技术保障，这样只需实现一次，其上的各种应用程序都能够平安地信赖底层的保障。这与事务的情理雷同：通过事务，应用程序能够伪装没有解体（原子性），没有与其他人并发拜访数据库（隔离性），且存储设备是齐全牢靠的（持久性）。总之，形象的事务机制能够屏蔽零碎外部很多简单的问题，使得应用层轻松无忧。

当初持续沿着这个思路，尝试建设能够让分布式应用疏忽外部各种问题的形象机制。例如，分布式系统最重要的形象之一就是共识：所有的节点就某一项提议达成统一。

一旦解决了共识问题，就能够服务于应用层很多的指标需要。例如，对于一个主从复制的数据库，如果主节点产生生效，就须要切换到另一个节点，此时数据库节点能够采纳共识算法来选举新的主节点。某一时刻必须只有一个主节点，所有的节点必须就此达成统一。如果有两个节点都自认为是主节点，就会产生脑裂，导致数据失落。正确实现共识算法则能够防止此类问题。

咱们须要理解零碎能力的边界，即哪些可行，哪些不可行。在什么状况下，零碎能够容忍故障并持续工作；而其余状况，却无奈保障。

在复制环境下，如果在同一时刻查询数据库的两个节点，则可能会看到不同的数据，这次要是因为写申请会在不同的工夫点达到不同的节点。无论数据库采纳何种复制办法，都无奈完全避免这种不统一状况。

大多数多正本的数据库都至多提供了最终的一致性，这意味着如果进行更新数据库，并期待一段时间之后，最终所有读申请会返回雷同的内容。换句话说，不统一景象是临时的，最终会达到统一。换言之，最终一致性意味着“收敛”，即预期所有的正本最终会收敛到雷同的值。

然而，这是一个十分弱的保障，它无奈通知咱们零碎何时会收敛。而在收敛之前，读申请可能会返回任何值甚至读失败。

当面对只提供了弱保障的数据库时，须要苏醒地认清零碎的局限性，切不可过于乐观。利用可能在大多数状况下都运行良好，但数据库外部可能曾经产生了十分奥妙的谬误，只有当零碎呈现故障或高并发压力时，最终一致性的临界条件或者谬误才会对外裸露进去，因此测试与发现错误变得十分艰难。

咱们将摸索更强的一致性模型。不过，这也意味着更多的代价，例如性能升高或容错性差。尽管如此，更强的保障的益处是使下层应用逻辑更简略，更不容易出错。当理解、比照了多种不同的一致性模型之后，能够联合本身需要，从中抉择最合适的。

在最终一致性数据库中，同时查问两个不同的正本可能会失去两个不同的答案。这会使应用层感到困惑。如果数据库可能对上提供只有单个正本的假象，状况会不会大为简化呢？这样让每个客户端都领有雷同的数据视图，而不用放心复制滞后。

这就是可线性化（也称为原子一致性，强一致性等）的思维。其根本的想法是让一个零碎看起来如同只有一个数据正本，且所有的操作都是原子的。

在一个可线性化的零碎中，一旦某个客户端胜利提交写申请，所有客户端的读申请肯定都能看到刚刚写入的值。这种看似繁多正本的假象意味着它能够保障读取最近最新值，而不是过期的缓存。换句话说，可线性化是一种就近的保障。

可线性化背地的根本思维很简略：使零碎看起来如同只有一个数据正本。

如图展现了三个客户端在线性化数据库中同时读写雷同的主键 x。在分布式语义下，x 被称为寄存器，例如，它能够是键 - 值存储中的一个键，关系数据库中的一行或文档数据库中的一个文档。

每条线代表一个客户端申请，虚线的开始示意发送申请的工夫，结尾则是收到响应的工夫。因为网络提早不确定，客户端并不分明数据库具体何时解决申请，而只晓得它是在发送之后、响应之前的某个两头工夫点。

在这个例子中，寄存器有两类操作：读和写（写可能会产生失败）。x 的初始值为 0，客户端 C 提交写申请将其设置为 1。同时，客户端 A 和 B 在重复轮询数据库以读取最新值。A 和 B 可能会别离读到什么样的返回值呢？

客户端 A 的第一个读取操作在写入开始之前已实现，因而返回的是旧值 0。
客户端 A 的最初一次读操作是在写操作实现之后才开始的，如果数据库是可线性化的，它必定会返回新值 1。
与写操作有时间重叠的任何读取操作则可能返回 0 或者 1，这是因为读写之间存在并发，无奈确切晓得在执行读取时，写入是否曾经失效。

然而，这还没有准确形容线性化：如果与写并发的读操作可能返回旧值或新值，那么在这个过程中，不同的读客户端会看到旧值和新值之间来回跳变的状况。

为使零碎可线性化，咱们须要增加一个重要的束缚：一旦某个读操作返回了新值，之后所有的读（包含雷同或不同的客户端）都必须返回新值。

能够进一步细化时序图来可视化每步操作具体在哪个工夫点失效，如图所示。除了读写之外，咱们引入了第三种类型的操作 cas：示意一个原子比拟 - 设置操作。

图中的每个操作都有一条竖线，示意可能的执行工夫点。这些标记以前后关系顺次连接起来，最终的后果必须是一个无效的寄存器读写程序，即每个读操作须返回最近写操作所设置的值。

可线性化要求，如果连贯这些标记的竖线，它们必须总是按工夫箭头（从左到右）向前挪动，而不能向后挪动。这个要求确保了之前所探讨的就近性保障：一旦新值被写入或读取，所有后续的读都看到的是最新的值，直到被再次笼罩。

图中有一些乏味的细节值得仔细分析：

客户端 B 首先发送读 x 的申请，接下来客户端 D 发送申请将 x 置为 0，紧接着客户端 A 又发送申请将 x 置为 1，而最终返回给 B 的值为 1。这是可能的，它意味着数据库执行的程序是：首先解决 D 的写入 0，而后是 A 的写入 1，最初是 B 的读取。尽管这并不是申请发送的程序，但思考到申请并发以及网络提早等状况，这是一个非法的可承受的解决程序。
客户端 A 在收到数据库写响应之前，客户端 B 即读到了值 1，这表明写入已胜利。这是可能的，但它并不代表执行读产生在执行写之前，只是意味着很可能因为网络提早而耽误了客户端 A 承受响应。
模型没有假设事务间的隔离，即另一个并发客户端可能随时会批改值。例如，C 首先读取到 1，而后读到 2，起因是两次读取之间值被客户端 B 批改了。咱们能够应用 cas 操作来查看值是否被其余并发客户端批改，例如客户端 B 和 C 的 cas 申请胜利，然而 D 的 cas 操作失败。
客户 B 的最初一次读取不满足线性化。该操作与 C 的 cas 写操作同时产生，后者将 x 从 2 更新为 4。在没有其余申请时，B 读取能够返回 2。然而在 B 读取开始之前，客户端 A 曾经读取了新值 4，所以不容许 B 读到比 A 更老的值。

加锁与主节点选举

主从复制的零碎须要确保有且只有一个主节点，否则会产生脑裂。选举新的主节点常见的办法是应用锁：即每个启动的节点都试图取得锁，其中只有一个能够胜利即成为主节点。不论锁具体如何实现，它必须满足可线性化：所有节点都必须批准哪个节点持有锁，否则就会呈现问题。

提供协调者服务的零碎如 ZooKeeper 和 etcd 等通常用来实现分布式锁和主节点选举。它们都应用了反对容错的共识算法确保可线性化。

束缚与唯一性保障

唯一性束缚在数据库中很常见。例如，用户名或电子邮件地址必须惟一标识一个用户，文件存储服务中两个文件不能具备雷同的门路和文件名。如果要在写入数据时强制执行这些束缚，则也须要线性化。

这种状况实质上与加锁十分相似：用户注册等同于试图对用户名进行加锁操作。该操作也相似于原子比拟和设置：如果以后用户名尚未被应用，就设置用户名与客户 ID 进行关联。

其余相似束缚包含银行账户余额不应呈现负值，或者防止发售库存里曾经没有的商品，或者不能同时预约航班或者剧院的雷同的座位。这样的约束条件都要求所有节点就某个最新值达成统一（例如账户余额，库存程度，座位占用率）。

硬性的唯一性束缚，常见如关系型数据库中主键的束缚，则须要线性化保障。其余如外键或属性束缚，则并不要求肯定线性化。

跨通道的工夫依赖

有些时候，线性化违例之所以被留神到，是因为零碎中存在其余的通信渠道。例如，用户能够上传照片到某网站，有一个后盾过程将照片调整为更低的分辨率（即缩略图）以不便更快下载。该网站架构和数据流如图所示。

这里须要明确告诉图像调整模块来调整哪些图片，零碎采纳了音讯队列将此命令从 Web 服务器发送到调整器。因为大多数音讯队列零碎并不适宜大数据流，而思考到照片的大小可能到数兆字节，因而 Web 服务器并不会把照片间接放在队列中。相同，照片会先写入文件存储服务，当写入实现后，把调整的命令放入队列。

如果文件存储服务是可线性化的，那么零碎应该能够失常工作。否则，这里就会引入竞争条件：音讯队列可能比存储服务外部的复制执行更快。在这种状况下，当调整模块在读取图像时，可能会看到图像的某个
旧版本，或者基本读不到任何内容。如果它碰巧读到了旧版本的图像并进行解决，会导致文件存储中的全尺寸图片与调整之后图片呈现永恒的不统一。

因为线性化实质上意味着“体现得如同只有一个数据正本，且其上的所有操作都是原子的”，所以最简略的计划天然是只用一个数据正本。但显然，该办法无奈容错：如果仅有的正本所在的节点产生故障，就会导致数据失落，或者至多在重启之前都无法访问服务。

零碎容错最常见的办法就是采纳复制机制。咱们回顾一下各种复制计划，看看哪些满足可线性化：

主从复制（局部反对可线性化）

在主从复制的零碎中，只有主节点承当数据写入，从节点则在各自节点上保护数据的备份正本。如果从主节点或者同步更新的从节点上读取，则能够满足线性化。但并非每个主从复制的具体数据库实例都是可线性化的，次要是因为它们可能采纳了快照隔离的设计，或者实现时存在并发方面的 bug。

而从主节点上读取的前提是你确定晓得哪个节点是主节点。某节点可能自认为是主节点，但事实并非如此，这个“自以为是”的主节点如果对外提供服务，就会违反线性化。如果应用了异步复制，故障切换过程中甚至可能会失落一些已提交的写入，后果是同时违反持久性和线性化。

共识算法（可线性化）

共识算法与主从复制机制类似，不过共识协定通常内置一些措施来避免脑裂和过期的正本。正是因为这些专门的设计，共识算法能够平安地实现线性化存储。

多主复制（不可线性化）

具备多主节点复制的零碎通常无奈线性化，次要因为它们同时在多个节点上执行并发写入，并将数据异步复制到其余节点。因而它们可能会产生抵触的写入，须要额定的解决方案。

无主复制（可能不可线性化）

对于无主节点复制的零碎，有些人认为只有配置法定读取和写入满足（w + r > n）就能够取得“强一致性”。但这齐全取决于具体的 quorum 的配置，以及如何定义强一致性，它可能并不保障线性化。

例如基于墙上时钟的“最初写入获胜”抵触解决办法简直必定是非线性化，因为这种工夫戳无奈保障与理论事件程序统一（例如因为时钟偏移）。不标准的 quorum 也会毁坏线性化。甚至即便是严格的 quorum，也会产生违反线性化的状况。

线性化与 quorum

直觉上，对于无主复制模型，如果读写听从了严格 quorum，应该是可线性化的。然而如果遭逢不确定的网络提早，就会呈现竞争条件，如图所示。

x 的初始值为 0，写客户端向所有三个正本（n = 3，w = 3）发送写申请将 x 更新为 1。与此同时，客户端 A 从两个节点（r = 2）读取数据，而后在其中一个节点上看到新值 1。与此同时，客户端 B 从两个节点的读取，两者都返回了旧值 0。

咱们发现它尽管满足了仲裁条件（w + r > n），但很显著这不是线性化的：B 的申请在 A 的申请实现之后才开始，A 返回了新值，但 B 却失去了旧值。

不过，能够以就义性能为代价来满足线性化：读操作在返回后果给利用之前，必须同步执行读修复；而写操作在发送后果之前，必须读取 quorum 节点以获取最新值。而且，如果应用了“最初写入获胜”抵触解决方案，当呈现同一个主键的并发写入时，就会丢失线性化。

此外，这种形式只能实现线性化读、写操作，但无奈反对线性化的“比拟和设置”操作，后者须要共识算法的反对。

总而言之，最平安的假设是无主复制零碎无奈保障线性化。

咱们曾经探讨了不同复制计划各自适宜的场景。例如，多主复制非常适合多数据中心。如果两个数据中心之间产生网络中断，会产生什么状况？基于多主复制的数据库，每个数据中心内都能够持续失常运行：因为从一个数据中心到另一个数据中心的复制是异步，期间产生的写操作都暂存在本地队列，等网络复原之后再持续同步。

与之比照，如果是主从复制，则主节点必定位于其中的某一个数据中心。所有写申请和线性化读取都必须发送给主节点，因而，对于那些连贯到非主节点所在数据中心的客户端，读写申请都必须通过数据中心之间的网络，同步发送到主节点所在的数据中心。

因而，对于这样的主从复制零碎，数据中心之间的网络一旦中断，连贯到从数据中心的客户端无奈再分割上主节点，也就无奈实现任何数据库写入和线性化读取。从节点能够提供读服务，但内容可能是过期的（非线性化保障）。所以，如果应用程序要求线性化读写，则网络中断肯定会违反这样的要求。

另一种状况，如果客户端能够间接连贯到主节点所在的数据中心，则能够防止此问题。否则，只能等到数据中心之间的网络复原之后能力持续失常工作。

CAP 实践

不仅仅是主从复制和多主复制才有下面的问题，无论如何实现，任何可线性化的数据库都有这样问题。事实上，这个问题也不局限于多数据中心部署的状况，即便在一个数据中心外部，只有有不牢靠的网络，都会产生违反线性化的危险。咱们能够做以下的衡量思考：

如果利用要求线性化，但因为网络方面的问题，某些正本与其余正本断开连接之后无奈持续解决申请，就必须期待网络修复，或者间接返回谬误。无论哪种形式，后果是服务不可用。
如果利用不要求线性化，那么断开连接之后，每个正本可独立解决申请例如写操作。此时，服务可用, 但后果行为不合乎线性化。

因而，不要求线性化的利用更能容忍网络故障，这种思路通常被称为 CAP 定理。

CAP 有时也代表一致性，可用性和分区容错性，零碎只能反对其中两个个性。不过，这种了解存在误导性，网络分区是一种故障，不论喜爱还是不喜爱，它都可能产生，所以无奈抉择或回避分区的问题。

在网络失常的时候，零碎能够同时保障一致性和可用性。而一旦产生了网络故障，必须要么抉择线性，要么可用性。因而，更精确的称说应该是“网络分区状况下，抉择统一还是可用”。高牢靠的网络会帮忙缩小产生的概率，但无奈做到彻底防止。

只管 CAP 在历史上具备重大的影响力，但对于一个具体的零碎设计来说，它可能没有太大的理论价值。

可线性化与网络提早

尽管线性化是个很有用的保障，但实际上很少有零碎真正满足线性化。例如，古代多核 CPU 上的内存甚至就是非线性化：如果某个 CPU 核上运行的线程批改一个内存地址，紧接着另一个 CPU 核上的线程尝试读取，则零碎无奈保障能够读到刚刚写入的值，除非应用了内存屏障或 fence 指令。

呈现这种景象的起因是每个 CPU 核都有本人独立的 cache 和寄存器。内存拜访首先进入 cache 零碎，所有批改默认会异步地刷新到主存。因为拜访 cache 比拜访主存要快得多，所以这样的异步刷新个性对于古代 CPU 的性能至关重要。然而，这就导致呈现了多个数据正本（一个在主存，另外几个在不同级别的 cache 中），而正本更新是异步形式，无奈保障线性化。

在计算机外部，咱们通常假如通信是牢靠的，例如咱们不会假设一个 CPU 核在与其余核断开之后还能坦然工作。所以，放弃线性化的起因就是性能，而不是为了容错。

许多分布式数据库也是相似，它们抉择不反对线性化是为了进步性能，而不是为了保住容错个性。无论是否产生了网络故障，线性化对性能的影响都是微小的。

线性化寄存器对外出现的如同只有一份数据拷贝，而且每一个操作仿佛都是原子性失效。这意味着操作是依照某种程序执行。

让咱们简要回顾一下探讨程序时波及的前后上下文：

主从复制零碎中主节点的次要作用是确定复制日志中的写入程序，这样使从节点听从雷同的程序执行写入。如果没有这样的惟一主节点，则可能因为并发操作而引发抵触。
可串行化隔离则是确保事务的执行后果与依照某种程序形式执行一样。实现形式能够是严格程序执行，或者容许并发但须要相应的抵触解决方案。
分布式系统的工夫戳与时钟，试图将程序引入到无序的操作世界，例如确定两个写操作哪一个先产生。

排序、可线性化与共识之间存在着某种粗浅的分割。

之所以重复呈现“程序”问题，其中的一个起因是它有助于放弃因果关系。曾经呈现了好几个例子：

在“统一前缀读”中，一个对话的观察者首先看到了问题的答案接着才是问题自身，这违反了咱们对因果的直觉意识。此时，问题与答复之间存在因果关系。
三个主节点之间进行数据复制，因为网络提早，一些写操作会笼罩其余的写入。从某个正本的角度来看，如同是产生了一个对不存在数据行的更新。这里的因果意味着首先必须先创立数据行，而后能力去更新。
在“检测并发写”中，如果有两个操作 A 和 B 是并发关系，则它们之间不存在因果关系。
在事务的快照隔离上下文中，事务是从一致性快照读取。这意味着与因果关系统一：如果快照中蕴含了答案，则它也必须蕴含所提的问题。这样能力确保在某个工夫点察看数据库时合乎因果关系：快照创立时刻点之前的所有数据都要可见，但尔后产生的事件则不可见。

因果关系对所产生的事件施加了某种排序：发送音讯先于收到音讯；问题呈现在答案之前等。这些因果关系的依赖链条定义了零碎中的因果程序，即某件事应该产生另一件事件之前。

如果零碎遵从因果关系所规定的程序，咱们称之为因果一致性。例如，快照隔离提供了因果一致性：当从数据库中读数据时，如果查问到了某些数据，也肯定能看到触发该数据的前序事件。

因果程序并非全序

全序关系反对任何两个元素之间进行比拟，即对于任意两个元素，总是能够指出哪个更大，哪个更小。例如，自然数合乎全序关系，轻易给出两个数字比方 5 和 13，都能够进行比拟。

然而，有些汇合并不合乎全序，例如汇合 {a，b} 大于汇合 {b，c} 么？因为它们都不是对方的子集，所以无奈间接比拟它们。咱们称之为不可比拟，数学汇合只能是偏序。

全序和偏序的差别也会体现在不同的数据库一致性模型中：

可线性化

在一个可线性化的零碎中，存在全序操作关系。零碎的行为就如同只有一个数据正本，且每个操作都是原子的，这意味着对于任何两个操作，咱们总是能够指出哪个操作在先。

因果关系

如果两个操作都没有产生在对方之前，那么这两个操作是并发关系。换言之，如果两个事件是因果关系，那么这两个事件能够被排序；而并发的事件则无奈排序比拟。这表明因果关系至多能够定义为偏序，而非全序。

因而，在可线性化数据存储中不存在并发操作，肯定有一个工夫线将所有操作都全序执行。并发意味着工夫线会呈现分支和合并，而不同分支上的操作无奈间接比拟。

可线性化强于因果一致性

那么因果序和可线性化之间是什么关系呢？答案是可线性化肯定意味着因果关系：任何可线性化的零碎都将正确地保障因果关系。特地是，如果零碎存在多个通信通道，可线性化确保了因果关系会主动全副保留，而不须要额定的工作（比方在不同组件之间的传递工夫戳）。

可线性化能够确保因果性这一论断，使线性化零碎更加简略易懂而富裕吸引力。然而，线性化会显著升高性能和可用性，尤其是在重大网络提早的状况下。正因如此，一些分布式数据系统曾经放弃了线性化，以换来更好的性能，但也存在可能无奈正确工作的危险。

线性化并非是保障因果关系的惟一路径，还有其余办法使得零碎能够满足因果一致性而免于线性化所带来的性能问题。事实上，因果一致性能够认为是，不会因为网络提早而显著影响性能，又能对网络故障提供容错的最强的一致性模型。在许多状况下，许多看似须要线性化的零碎实际上真正须要的是因果一致性，后者的实现能够高效很多。

尽管因果关系很重要，但实际上跟踪所有的因果关系不切实际。这里还有一个更好的办法：咱们能够应用序列号或工夫戳来排序事件。它能够只是一个逻辑时钟，通常是递增的计数器。

这样的序列号或工夫戳十分紧凑，但它们保障了全序关系。也就是说，每一个操作都有惟一的顺序号，并且总是能够通过比拟来确定哪个更大（即操作产生在后）。

咱们能够依照与因果关系统一的程序来创立序列号：保障如果操作 A 产生在 B 之前，那么 A 肯定在全序中呈现在 B 之前。并行操作的序列可能是任意的。这样的全局排序能够捕捉所有的因果信息，但也强加了比因果关系更为严格的程序性。

在主从复制数据库中，复制日志定义了与因果关系统一的写操作全序关系。主节点能够简略地为每个操作递增某个计数器，从而为复制日志中的每个操作赋值一个枯燥递增的序列号。从节点依照复制日志呈现的程序来利用写操作，那后果肯定满足因果一致性。

非因果序列发生器

如果零碎不存在这样惟一的主节点，如何产生序列号就不是那么简略了。实际中能够采纳以下办法：

每个节点都独立产生本人的一组序列号。例如，如果有两个节点，则一个节点只生成奇数，而另一个节点只生成偶数。还能够在序列号中保留一些位用于嵌入所属节点的惟一标识符，确保不同的节点永远不会生成雷同的序列号。
能够把墙上工夫戳信息（物理时钟）附加到每个操作上。工夫戳可能是不间断的，然而只有它们有足够高的分辨率，就能够用来辨别操作。
能够事后调配序列号的区间范畴。例如，节点 A 负责区间 1~1000 的序列号，节点 B 负责 1001~2000。而后每个节点独立地从区间中调配序列号，当序列号呈现缓和时就调配更多的区间。

上述三种思路都可行，相比于把所有申请全副压给惟一的主节点具备更好的扩展性。它们为每个操作生成一个惟一的、近似减少的序列号。不过，它们也都存在一个问题：所产生的序列号与因果关系并不严格统一。

所有这些序列号发生器都无奈保障正确捕捉跨节点操作的程序，因此存在因果关系方面的问题：

每个节点可能有不同的处理速度，如每秒申请数。因而，某个节点产生偶数而另一个产生奇数，偶数的计数器产生速度可能落后于奇数的计数器，反之亦然。这样就无奈精确地晓得哪个操作在先。
物理时钟的工夫戳会受到时钟偏移的影响，也可能导致与理论因果关系不统一。
对于区间分配器，一个操作可能被赋予从 1001~2000 之间的某个序列号，而后产生的操作则路由到另一个节点，拿到了某个 1~1000 之间的序列号，导致与因果序不统一。

Lamport 工夫戳

方才所形容的三个序列号发生器可能与因果关系存在不统一，但还有一个简略的办法能够产生与因果关系统一的序列号。它被称为兰伯特工夫戳（Lamport timestamp）。

下图给出了 Lamport 工夫戳的示例。首先每个节点都有一个惟一的标识符，且每个节点都有一个计数器来记录各自曾经解决的申请总数。Lamport 工夫戳是一个值对（计数器，节点 ID）。两个节点可能会有雷同的计数器值，但工夫戳中还蕴含节点 ID 信息，因而能够确保每个工夫戳都是惟一的。

Lamport 工夫戳与物理墙上时钟并不存在间接对应关系，但它能够保障全序：给定两个 Lamport 工夫戳，计数器较大那个工夫戳大；如计数器值正好雷同，则节点 ID 越大，工夫戳越大。

每个节点以及每个客户端都跟踪迄今为止所见到的最大计数器值，并在每个申请中附带该最大计数器值。当节点收到某个申请（或者回复）时，如果发现申请内嵌的最大计数器值大于节点本身的计数器值，则它立刻把本人的计数器批改为该最大值。

如图所示，客户端 A 从节点 2 收到计数器值 5，而后将最大值 5 发送到节点 1。此时，节点 1 的计数器仅为 1，然而它立刻向前跳到 5，所以下一个操作将取得计数器值 6。只有把最大计数器值嵌入到每一个申请中，该计划能够确保 Lamport 工夫戳与因果关系统一，而申请的因果依赖性肯定会保障后产生的申请失去更大的工夫戳。

工夫戳排序仍然不够

尽管 Lamport 工夫戳定义了与因果序统一的全序关系，但还不足以解决理论分布式系统中许多常见的问题。

例如，一个账户零碎须要确保用户名惟一标识用户。即两个用户如果同时尝试应用雷同的用户名创立账户时，确保其中一个胜利，另一个必须失败。

乍看之下，仿佛全序关系（例如应用 Lamport 工夫戳）应该能够解决问题：如果有这样并发的操作，则抉择工夫戳较低的那个作为获胜者，而让工夫戳大的申请失败。因为工夫戳有序，所以这样的比拟办法也应该是可行的。然而，这种办法确定胜利者有这样一个前提条件：须要收集零碎中所有的用户创立申请，而后才能够比拟它们的工夫戳。然而，当节点刚刚收到用户的创立申请时，它无奈过后就做出决定该申请应该胜利还是失败。此时，节点基本不晓得是否有另一个节点在同时创立雷同用户名。

而为了取得上述两点信息，零碎就必须查看每个节点，询问它们在做什么。如果万一某个节点呈现故障或者因为网络问题而无奈连贯，那么办法就无奈失常运行。显然这不是咱们所冀望的容错零碎。

总而言之，为了实现像用户名唯一性束缚这样的指标，仅仅对操作进行全序排列还是不够的，还须要晓得这些操作是否产生、何时确定等。如果可能在创立用户名时，曾经确定晓得了没有其余节点正在执行雷同用户名的创立，你大能够间接平安返回创立胜利。

全序关系播送通常指节点之间替换音讯的某种协定。它要求满足两个根本平安属性：

牢靠发送：没有音讯失落，如果音讯发送到了某一个节点，则它肯定要发送到所有节点。
严格有序：音讯总是以雷同的程序发送给每个节点。

即便节点或网络呈现了故障，全序关系播送算法的正确实现也必须保障上述两条。当然，网络中断时是不可能发送胜利的，但算法要持续重试，直到最终网络修复，音讯发送胜利（且必须以正确的程序发送）。

应用全序关系播送

像 ZooKeeper 和 etcd 这样的共识服务实际上就实现了全序关系播送。全序关系播送是数据库复制所须要的：如果每条音讯代表数据库写申请，并且每个正本都按雷同的程序解决这些写申请，那么所有正本能够保持一致（或者有些滞后）。该准则也被称为状态机复制。

能够应用全序关系播送来实现可串行化事务。如果每条音讯示意一个确定性事务并且作为存储过程来执行，且每个节点都听从雷同的执行程序，那么能够保障数据库各分区以及各正本之间的一致性。

全序关系播送另一个要点是程序在发送音讯时曾经确定，如果音讯发送胜利，节点不容许将某条音讯插入到先前的某个地位上。这一点使得全序关系播送比基于工夫戳排序要求更强。

了解全序关系播送的另一种形式是将其视为日志（如复制日志，事务日志或预写日志）。传递音讯就像追加形式更新日志。因为所有节点必须以雷同的程序发送音讯，因而所有节点都能够读取日志并看到雷同的音讯序列。

全序关系播送对于提供 fencing 令牌的锁服务也很有用。每个获取锁的申请都作为音讯附加到日志中，所有音讯依照日志中的程序顺次编号。序列号还能够作为令牌，它合乎枯燥递增要求。

采纳全序关系播送实现线性化存储

可线性化与全序关系播送之间有着亲密的分割，也有不同之处。全序关系播送是基于异步模型：保障音讯以固定的程序牢靠地发送，然而不保障音讯何时发送胜利（因而某个接收者可能显著落后于其余接收者）。而可线性化则强调就近性：读取时保障可能看到最新的写入值。

如果有了全序关系播送，就能够在其上构建线性化的存储系统。例如，确保用户名惟一标识一个用户。

对于每一个可能的用户名，都能够有一个带有原子比拟 - 设置操作的线性化寄存器。每个寄存器初始值为空。当用户创立一个用户名时，对该用户名的寄存器执行比拟设置操作。如果多个用户试图同时获取雷同的用户名，则只有一个原子比拟 - 设置操作胜利。

能够通过应用全序关系播送以追加日志的形式来实现线性化的原子比拟 - 设置操作，步骤如下所示：

在日志中追加一条音讯，并指明想要的用户名。
读取日志，将其播送给所有节点，并期待回复。
查看是否有任何音讯宣称该用户名已被占用。如果第一条这样的回复来自于以后节点，那么就胜利取得该用户名，能够提交该获取申明并返回给客户端。反之，如果宣称占用的第一条回复音讯来自其余节点，则停止操作。

因为日志条目以雷同的程序发送到所有节点，而如果存在多个并发写入，则所有节点将首先决定哪个申请在先。抉择第一个写申请作为获胜者，并停止其余申请，以确保所有节点批准一个写申请最终要么提交胜利要么停止。相似的办法还能够用来在日志之上实现可串行化的多对象事务。

尽管此过程可确保线性化写入，但它却无奈保障线性化读取，即从异步日志更新的存储中读取数据时，可能是旧值。具体来说，这里只提供了程序一致性，有时也称为工夫线一致性，它弱于线性化保障。为了同时满足线性化读取，有以下几个计划：

能够采纳追加的形式把读申请排序、播送，而后各个节点获取该日志，当本节点收到音讯时才执行真正的读操作。音讯在日志中的地位曾经决定了读取产生的工夫点。etcd 的 quorum 读取和这个思路有相似之处。
如果能够以线性化的形式获取以后最新日志中音讯的地位，则查问地位，期待直到该地位之前的所有条目都曾经发送给你，接下来再执行读取。这与 ZooKeeper 的 sync()操作思路雷同。
能够从同步更新的正本上进行读取，这样确保总是读取最新值。这种技术能够用于链式复制。

采纳线性化存储实现全序关系播送

最简略的办法是假如有一个线性化的寄存器来存储一个计数，而后使其反对原子自增 - 读取操作或者原子比拟 - 设置操作。

算法思路很简略：对于每个要通过全序关系播送的音讯，原子递增并读取该线性化的计数，而后将其作为序列号附加到音讯中。接下来，将音讯播送到所有节点，而接受者也严格依照序列化来发送回复音讯。

与 Lamport 工夫戳不同，通过递增线性化寄存器取得的数字不会存在任何间隙。因而，如果节点实现了音讯 4 的发送，且接管到了序列化 6 的音讯，那么在它对音讯 6 回复之前必须期待音讯 5。Lamport 工夫戳则不是这样，而这也是区别全序关系播送与基于工夫戳排序的要害。

难点在于解决节点的网络中断，以及节点生效时如何复原该值。线性化的原子比拟 - 设置（或自增）寄存器与全序关系播送二者都等价于共识问题。

共识问题是分布式计算中最重要也是最根本的问题之一，指标是让几个节点就某件事情达成统一。有很多重要的场景都须要集群节点达成某种统一，例如：

主节点选举

对于主从复制的数据库，所有节点须要就谁来充当主节点达成统一。如果因为网络故障起因呈现节点之间无奈通信，就很容易呈现争议。此时，共识对于防止谬误的故障切换十分重要，后者会导致两个节点都自认为是主节点即脑裂。

原子事务提交

对于反对跨节点或跨分区事务的数据库，会面临这样的问题：某个事务可能在一些节点上执行胜利，但在其余节点却可怜产生了失败。为了保护事务的原子性，所有节点必须对事务的后果达成统一：要么全副胜利提交，要么停止 / 回滚。

从单节点到分布式的原子提交

对于在单个数据库节点上执行的事务，原子性通常由存储引擎来负责。当客户端申请数据库节点提交事务时，数据库首先使事务的写入长久化（通常保留在预写日志中），而后把提交记录追加写入到磁盘的日志文件中。如果数据库在该过程两头产生了解体，那么当节点重启后，事务能够从日志中复原：如果在解体之前提交记录已胜利写入磁盘，则认为事务已平安提交；否则，回滚该事务的所有写入。

然而，如果一个事务波及多个节点呢？例如，一个分区数据库中多对象事务，或者是基于词条分区的二级索引。向所有节点简略地发送一个提交申请，而后各个节点独立执行事务提交是相对不够的。这样做很容易产生局部节点提交胜利，而其余一些节点产生失败，从而违反了原子性保障：

某些节点可能会检测到违反束缚或有抵触，因此决定停止，而其余节点则可能胜利提交。
某些提交申请可能在网络中失落，最终因为超时而停止，而其余提交申请则顺利通过。
某些节点可能在日志记录写入之前产生解体，而后在复原时回滚，而其余节点则胜利提交。

如果一部分节点提交了事务，而其余节点却放弃了事务，节点之间就会变得不统一。而且某个节点一旦提交了事务，即便预先发现其余节点产生停止，它也无奈再撤销已提交的事务。正因如此，如果有局部节点提交了事务，则所有节点也必须跟着提交事务。

两阶段提交

两阶段提交（two-phase commit，2PC）是一种在多节点之间实现事务原子提交的算法，用来确保所有节点要么全副提交，要么全副停止。2PC 在某些数据库外部应用，或者以 XA 事务或 SOAP Web 服务 WS-AtomicTransaction 的模式提供给应用程序。

2PC 的根本流程如图所示。不同于单节点上的申请提交，2PC 中的提交 / 停止过程分为两个阶段。

2PC 引入了单节点事务所没有的一个新组件：协调者（也称为事务管理器）。协调者通常实现为共享库，运行在申请事务雷同过程中，但也能够是独自的过程或服务。常见协调者的例子包含 Narayana，JOTM，BTM 或 MSDTC。

通常，2PC 事务从应用程序在多个数据库节点上执行数据读 / 写开始。咱们将这些数据库节点称为事务中的参与者。当应用程序筹备提交事务时，协调者开始阶段 1：发送一个筹备申请到所有节点，询问他们是否能够提交。协调者而后跟踪参与者的回应：

如果所有参与者答复“是”，示意他们已筹备好提交，那么协调者接下来在阶段 2 会收回提交申请，提交开始理论执行。
如果有任何参与者回复“否”，则协调者在阶段 2 中向所有节点发送放弃申请。

具体流程

咱们来更具体地合成这个过程：

当应用程序启动一个分布式事务时，它首先向协调者申请事务 ID。该 ID 全局惟一。
应用程序在每个参加节点上执行单节点事务，并将全局惟一事务 ID 附加到事务上。此时，读写都是在单节点内实现。如果在这个阶段呈现问题，则协调者和其余参与者都能够平安停止。
当应用程序筹备提交时，协调者向所有参与者发送筹备申请，并附带全局事务 ID。如果筹备申请有任何一个产生失败或者超时，则协调者会告诉所有参与者放弃事务。
参与者在收到筹备申请之后，确保在任何状况下都能够提交事务，包含平安地将事务数据写入磁盘，并查看是否存在抵触或束缚违规。一旦向协调者答复“是”，节点就承诺会提交事务。
当协调者收到所有筹备申请的回答时，就是否提交事务要做出明确的决定（即只有所有参与者都投赞成票时才会提交）。协调者把最初的决定写入到磁盘的事务日志中，避免稍后零碎解体，并能够复原之前的决定。这个时刻称为提交点。
协调者的决定写入磁盘之后，接下来向所有参与者发送提交（或放弃）申请。如果此申请呈现失败或超时，则协调者必须始终重试，直到胜利为止。此时，所有节点不容许有任何反悔：一旦做了决定，就必须贯彻执行，即便须要很多次重试。而如果有参与者在此期间呈现故障，在其复原之后，也必须继续执行。

由此可见，该协定有两个关键点：首先，当参与者投票“是”时，它做出了必定提交的承诺。其次，协调者做出了提交（或者放弃）的决定，这个决定也是不可撤销。正是这两个承诺确保了 2PC 的原子性。

协调者产生故障

如果协调者在发送筹备申请之前就已失败，则参与者能够平安地停止交易。然而，一旦参与者收到了筹备申请并做了投票“是”，则参与者不能单方面放弃，它必须期待协调者的决定。如果在决定达到之前，呈现协调者解体或网络故障，则参与者只能无奈期待。此时参与者处在一种不确定的状态。

状况如图所示。在该例子中，协调者实际上做出了提交决定，数据库 2 曾经收到了提交申请。然而，协调者在将提交申请发送到数据库 1 之前产生了解体，因而数据库 1 不晓得该提交还是停止。超时机制也无奈解决问题：如果超时之后数据库 1 决定单方面停止，最终将与实现提交的数据库 2 产生不统一。同理，参与者也不能单方面决定提交，因为可能有些参与者投了否决票导致协调者最终的决定是放弃。

没有协调者的音讯，参与者无奈晓得下一步的口头。2PC 可能顺利完成的惟一办法是期待协调者复原。这就是为什么协调者必须在向参与者发送提交（或停止）申请之前要将决定写入磁盘的事务日志：等协调者复原之后，通过读取事务日志来确定所有未决的事务状态。如果在协调者日志中没有实现提交记录就会停止。此时，2PC 的提交点当初归结为协调者在惯例单节点上的原子提交。

三阶段提交

两阶段提交也被称为阻塞式原子提交协定，因为 2PC 可能在期待协调者复原时卡住。实践上，能够使其改良为非阻塞式从而防止这种状况。然而，实际中要想做到这一点并不容易。

作为 2PC 的代替计划，目前也有三阶段提交算法。然而，3PC 假设一个有界的网络提早和节点在规定工夫内响应。思考到目前大多数具备有限网络提早和过程暂停的理论状况，它无奈保障原子性。

通常，非阻塞原子提交依赖于一个完满的故障检测器，即有一个十分牢靠的机制能够判断出节点是否曾经解体。在有限提早的网络环境中，超时机制并不是牢靠的故障检测器，因为即便节点失常，申请也可能因为网络问题而最终超时。正是因为这样的起因，只管大家曾经意识到上述协调者潜在的问题，但还在广泛应用 2PC。

分布式事务的某些实现存在重大的性能问题。例如，有报告显示 MySQL 的分布式事务比单节点事务慢 10 倍以上。两阶段提交性能降落的次要起因是为了防解体复原而做的磁盘 I / O 以及额定的网络往返开销。

然而，咱们不应该就这么间接地摈弃分布式事务，而应该更加审慎的看待。首先，咱们还是要明确“分布式事务”的确切含意。目前有两种截然不同的分布式事务概念：

数据库外部的分布式事务：某些分布式数据库（例如那些标配反对复制和分区的数据库）反对跨数据库节点的内部事务。例如，VoltDB 和 MySQL Cluster 的 NDB 存储引擎就反对这样的外部分布式事务。此时所有参加节点都运行着雷同的数据库软件。
异构分布式事务：在异构分布式事务中，存在两种或两种以上不同的参与者实现技术。例如来自不同供应商的数据库，甚至是非数据库系统（如消息中间件）。即便是齐全不同的零碎，跨零碎的分布式事务也必须确保原子提交。

数据库内部事务因为不用思考与其余零碎的兼容，因而能够应用任何模式的外部协定并采取有针对性的优化。因而，数据库外部的分布式事务往往可行且工作不错，但异构环境的事务则充斥了挑战。

Exactly-once 音讯解决

异构的分布式事务旨在无缝集成多种不同的零碎。例如，当且仅当数据库中解决音讯的事务胜利提交，音讯队列才会标记该音讯已处理完毕。如果音讯发送或数据库事务任何一个产生失败，则两者都须停止，音讯队列能够在稍后再次重传音讯。因而，通过主动提交音讯和音讯解决的后果，能够确保音讯能够无效解决有且仅有一次（胜利之前有可能须要重试）。而如果事务最初产生停止，则会放弃所有局部实现的后果。

须要指出，只有在所有受影响的零碎都应用雷同的原子提交协定的前提下，这种分布式事务才是可行。例如，如果处理结果之一是发送一封邮件，而邮件服务器却不反对两阶段提交，此时如果某个环节出错须要重试，就会导致邮件系统反复发送两次或更多。但如果假设所有后果或者副作用都能够在事务停止时回滚，就能够平安地重新处理音讯。

XA 交易

X/Open XA（eXtended Architecture，XA）是异构环境下施行两阶段提交的一个工业规范，目前，许多传统关系数据库和音讯队列都反对 XA。

XA 并不是一个网络协议，而是一个与事务协调者进行通信的 C API。当然，它也反对其余语言的 API 绑定，XA 假设应用程序通过网络或客户端的库函数与参与者（包含数据库、音讯服务）节点进行通信。如果驱动程序反对 XA，意味着利用能够调用 XA API 来确定操作是否是异构分布式事务的一部分。如果是，则发送必要的信息给数据库服务器。它还反对回调，这样协调者能够通过回调函数来告诉所有参与者执行筹备或者提交（或者停止）。

事务协调者须要实现 XA API。尽管规范并没有具体要求该如何实现，但实际上，协调者通常也是一个 API 库，它与产生事务的利用程序运行在雷同的过程中。这些 API 会跟踪事务中所有的参与者，协调节点进行筹备（通过回调）工作，而后负责收集参与者的投票，并在本地磁盘的日志文件里记录事务最终的决定。

如果应用程序过程产生解体，或者所在的节点呈现故障，协调者就须要做相应的解决。此时，所有实现了筹备阶段但尚未提交的参与者就会陷入进展。因为事务日志保留在应用服务器的本地磁盘上，该节点必须先重启，而后协调者通过 XA API 读取日志、进而复原事务的决定。实现这些之后，协调者能力持续应用数据库驱动 XA 回调来要求所有参与者执行提交（或停止）。数据库服务器无奈间接与协调者进行通信，而须通过相应的 API 接口。

问题：进展时仍持有锁

数据库事务通常持有待批改行的行级独占锁，用以避免脏写。此外，如果要应用可串行化的隔离，则两阶段锁的数据库还会对事务已经读取的行持有读 - 共享锁。

在事务提交（或停止）之前，数据库都不会开释这些锁。因而，在两阶段提交时，事务在整个进展期间始终持有锁。如果协调者的日志因为某种原因而彻底失落，这些数据对象在管理员手动解决之前，将永恒处于加锁状态。

数据处于加锁时，其余事务就无奈执行批改。取决于数据库的具体实现，其余事务甚至无奈读取这些行。因而，其余的事务事实上无奈无效执行。这可能会导致很多下层利用根本处于不可用状态，所以必须解决处于进展状态的那些事务。

从协调者故障中复原

实践上，如果协调者解体之后重新启动，它应该能够从日志中复原那些进展的事务。然而，在实践中，孤立的不确定事务的确会产生。例如因为软件 bug 导致交易日志失落或者损坏，最终协调者还是呈现了复原失败。

即便重启那些处于进展状态的数据库节点也无奈解决这个问题，这是因为 2PC 的正确实现要求即便产生了重启，也要持续放弃重启之前事务的加锁（否则就会违反原子性保障）。惟一的前途只能是让管理员手动决定到底是执行提交还是回滚。

许多 XA 的实现都反对某种紧急避险措施称之为启发式决策（会毁坏原子性）：参与者节点能够在紧急情况下单方面做出决定，放弃或者持续那些进展的事务，而不须要等到协调者收回指令。这种启发式决策只是为了应急，不能作为惯例伎俩来应用。

分布式事务的限度

XA 事务解决了多个参与者之间如何达成统一这样一个十分事实而重要的问题，但正如下面所看到的，它也引入了不少操作方面的限度。特地是，外围的事务协调者自身就是一种数据库（存储事务的投票后果），因而须要和其余重要的数据库一样分外小心：

如果协调者不反对数据复制，而是在单节点上运行，那么它就是整个零碎的单点故障（因为它的故障导致了很多利用阻塞在进展事务所持有的锁上）。
许多服务器端应用程序都偏向于无状态模式，而所有的长久状态都保留在数据库中，这样应用服务器能够轻松地增加或删除实例。然而，当协调者就是应用服务器的一部分时，部署形式就产生了基本的变动。协调者的日志成为牢靠零碎的重要组成部分，它要求与数据库自身一样重要。这样的应用服务器曾经不再是无状态。
因为 XA 须要与各种数据系统放弃兼容，它最终其实是多零碎可兼容的最低标准，也即无奈提供更多高级性能。

共识是让几个节点就某项提议达成统一。共识问题通常形式化形容如下：一个或多个节点能够提议某些值，由共识算法来决定最终值。

共识算法必须满足以下性质：

协商一致性（Uniform agreement）：所有的节点都承受雷同的决定。
诚恳性（Integrity）：所有节点不能反悔，即对一项提议不能有两次决定。
合法性（Validity）：如果决定了值 v，则 v 肯定是由某个节点所提议的。
可终止性（Termination）：非极其状况下最终肯定能够达成决定。

协商一致性和诚恳性属性定义了共识的核心思想：决定统一的后果，一旦决定，就不能扭转。合法性次要是为了排除一些无意义的计划。

如果不关怀容错，那么满足前三个属性很容易：能够强行指定某个节点为“独裁者”，由它做出所有的决定。然而，如果该节点失败，零碎就无奈持续做出任何决定。其实这就是在两阶段提交时所看到的：如果协调者失败了，那些处于不确定状态的参与者就无从晓得下一步该做什么。

可终止性则引入了容错的思维。它重点强调一个共识算法不能原地空转，必须获得实质性停顿。即便某些节点呈现了故障，其余节点也必须最终做出决定。

上述共识的零碎模型假设当某个节点产生解体后，节点就彻底隐没。在这样的零碎模型下，所有采取期待节点复原的算法都无奈满足可终止性，特地是 2PC 不合乎可终止性要求。

当然，如果所有的节点都解体了，那么无论何种算法都不可能持续做出决定。算法所可能容忍的失败次数和规模都有肯定的限度。事实上，能够证实任何共识算法都须要至多大部分节点正确运行能力确保终止性。而这个少数就能够平安地形成 quorum。因而，可终止性的前提是，产生解体或者不可用的节点数必须小于半数节点。

共识算法与全序播送

最驰名的容错式共识算法包含 VSR，PaxoS，Raft 和 Zab。这些算法存在诸多相似之处，但又不完全相同。

这些算法大部分其实并不是间接应用上述的形式化模型（提议并决定某个值，同时满足下面 4 个属性）。相同，他们是 决定了一系列值，而后采纳全序关系播送算法。

全序关系播送的要点是，音讯依照雷同的程序发送到所有节点，有且只有一次。如果认真想想，这其实相当于进行了多轮的共识过程：在每一轮，节点提出他们接下来想要发送的音讯，而后决定下一个音讯的全局程序。

主从复制与共识

主从复制中，所有的写入操作都由主节点负责，并以雷同的程序发送到从节点来放弃正本更新。这不就是根本的全序关系播送么？那在主从复制时咱们怎么没有思考共识问题呢？

答案取决于如何抉择主节点。如果主节点是由经营人员手动抉择和配置的，那基本上就是一个独裁性质的“一致性算法”：只容许一个节点承受写入，如果该节点产生故障，零碎将无奈写入，直到操作人员再手动配置新的节点成为主节点。这样的计划也能在实践中很好地发挥作用，但它须要人为干涉能力获得停顿，不满足共识的可终止性。

一些数据库反对主动选举主节点和故障切换，通过选举把某个从节点者晋升为新的主节点。这样更靠近容错式全序关系播送，从而达成共识。

然而，还有一个问题，咱们之前曾探讨过脑裂：所有的节点都须要批准主节点，否则两个主节点会导致数据库呈现不统一。因而，咱们须要共识算法选出一位主节点。然而，如果这里形容的共识算法实际上是全序关系播送，且全序关系播送很像主从复制，但主从复制当初又须要选举主节点等。

看起来要选举一个新的主节点，咱们首先须要有一个主节点。怎么解脱这样一个奇怪的循环？

Epoch 和 Quorum

目前所探讨的所有共识协定在其外部都应用了某种模式的主节点，尽管主节点并不是固定的。相同，他们都采纳了一种弱化的保障：协定定义了一个世代编号（epoch number，对应于 Paxos 中的 ballot number，Raft 中的 termnumber），并保障在每个世代里，主节点是惟一确定的。

如果发现以后的主节点生效，节点就开始一轮投票选举新的主节点。选举会赋予一个枯燥递增的 epoch 号。如果呈现了两个不同的主节点对应于不同 epoch 号码，则具备更高 epoch 号码的主节点将获胜。

在主节点做出任何决定之前，它必须首先查看是否存在比它更高的 epoch 号码，否则就会产生抵触的决定。主节点如何晓得它是否已被其余节点所取代了呢？它必须从 quorum 节点中收集投票。主节点如果想要做出某个决定，须将提议发送给其余所有节点，期待 quorum 节点的响应。quorum 通常（但不总是）由少数节点组成。并且，只有当没有发现更高 epoch 主节点存在时，节点才会对以后的提议（带有 epoch 号码）进行投票。

因而，这外面理论存在两轮不同的投票：首先是投票决定谁是主节点，而后是对主节点的提议进行投票。其中的要害一点是，参加两轮的 quorum 必须有重叠：如果某个提议取得通过，那么其中参加投票的节点中必须至多有一个也加入了最近一次的主节点选举。换言之，如果在针对提议的投票中没有呈现更高 epoch 号码，那么能够得出这样的论断：因为没有产生更高 epoch 的主节点选举，以后的主节点位置没有扭转，所以能够平安地就提议进行投票。

投票过程看起来很像两阶段提交。最大的区别是，2PC 的协调者并不是依附选举产生；另外容错共识算法只须要收到少数节点的投票后果即可通过决定，而 2PC 则要求每个参与者都必须做出“是”能力最终通过。此外，共识算法还定义了复原过程，呈现故障之后，通过该过程节点能够选举出新的主节点而后进入统一的状态，确保总是可能满足平安属性。所有这些差别之处都是确保共识算法正确性和容错性的要害。

共识的局限性

不过，也不是所有零碎都采纳了共识，因为益处的背地都是有代价的。这包含：

在达成一致性决定之前，节点投票的过程是一个同步复制过程。数据库通常配置为异步复制，而非同步复制，起因正是为了更好的性能。

共识体系须要严格的少数节点能力运行。如果因为网络故障切断了节点之间的连贯，则只有少数节点所在的分区能够持续工作，剩下的多数节点分区则处于事实上的进展状态。

少数共识算法假设一组固定参加投票的节点集，这意味着不能动静增加或删除节点。动静成员资格的扩大个性能够在集群中的按需调整节点数，但相比于动态的成员组成，其了解水平和接受程度要低很多。

共识零碎通常依附超时机制来检测节点生效。在网络提早高度不确定的环境中，特地是那些跨区域散布的零碎，常常因为网络提早的起因，导致节点谬误地认为主节点产生了故障。

此外，共识算法往往对网络问题特地敏感。

ZooKeeper 或 etcd 这样的我的项目通常称为“协调与配置服务”。应用程序开发者其实很少间接应用 ZooKeeper，次要因为它并非通用的数据库。绝大多数状况是通过其余很多我的项目来间接地依赖于 Zookeeper，例如 HBase，Hadoop YARN，OpenStack Nova 和 Kafka 等。

ZooKeeper 和 etcd 次要针对保留大量、可齐全载入内存的数据（尽管它们最终仍要写人磁盘以反对持久性）而设计，所以不要用它们保留大量的数据。它们通常采纳容错的全序播送算法在所有节点上复制这些数据从而实现高牢靠。

ZooKeeper 不仅实现了全序播送（因而实现了共识），还提供了其余很多乏味的个性：

线性化的原子操作

应用原子比拟 - 设置操作，能够实现加锁服务。例如如果多个节点同时尝试执行雷同的操作，则确保其中只有一个会胜利。共识协定保障了操作满足原子性和线性化，即便某些节点产生故障或网络随时被中断。分布式锁通常实现为一个带有到期工夫的租约，这样万一某些客户端产生故障，能够最终开释锁。

操作全序

当资源被锁或者租约爱护时，须要 fencing 令牌来避免某些客户端因为产生过程暂停而引起锁抵触。fencing 令牌确保每次加锁时数字总是枯燥减少。ZooKeeper 在实现该性能时, 采纳了对所有操作执行全局排序，而后为每个操作都赋予一个枯燥递增的事务 ID 和版本号。

故障检测

客户端与 ZooKeeper 节点保护一个长期会话，客户端会周期性地与 ZooKeeper 服务节点互相交换心跳信息，以查看对方是否存活。即便连贯呈现闪断，或者某个 ZooKeeper 节点产生生效，会话仍处于活动状态。然而，如果长时间心跳进行且超过了会话超时设置，ZooKeeper 会申明会话失败。此时，所有该会话持有的锁资源能够配置为主动全副开释。

更改告诉

客户端不仅能够读取其余客户端所创立的锁和键值，还能够监督它们的变动。因而，客户端能够晓得其余客户端何时退出了集群（基于它写入 ZooKeeper 的值）以及客户端是否产生了故障（会话超时导致节点隐没）。通过订阅告诉机制，客户端不须要频繁地轮询服务即可晓得感兴趣对象的变动状况。

节点任务分配

ZooKeeper 非常适合的一个场景是，如果零碎有多个流程或服务的实例，并且需要其中的一个实例充当主节点；而如果主节点生效，由其余某个节点来接管。显然，这十分吻合主从复制数据库，此外，它对于作业调度零碎（或相似的有状态服务）也十分有用。

还有另一个场景，对于一些分区资源（能够是数据库，音讯流，文件存储，分布式 actor system 等），须要决定将哪个分区调配给哪个节点。当有新节点退出集群时，须要将某些现有分区从以后节点迁徙到新节点，从而实现负载动态平衡。而当节点移除或失败时，其余节点还须要接管失败节点。

上述场景中的工作，能够借助 ZooKeeper 中的原子操作，ephemeral nodes 和告诉机制来实现。如果实现无误，它能够十分不便地使应用程序达到主动故障中复原，缩小人工干预。

应用程序最后可能只运行在单节点，之后可能最终扩大到数千节点。试图在如此宏大的集群上进行少数者投票会十分低效。ZooKeeper 通常是在固定数量的节点（通常三到五个）上运行投票，能够十分高效地反对大量的客户端。因而，ZooKeeper 其实提供了一种将跨节点协调服务（包含共识，操作排序和故障检测）业余外包的形式。通常状况下，ZooKeeper 所治理的数据变动十分迟缓，相似“分区 7 的主节点在 10.1.1.23”这样的信息，其变动频率往往在分钟甚至是小时级别。它不适宜保留那些利用实时运行的状态数据，后者可能每秒产生数千甚至百万次更改。

服务发现

此外，ZooKeeper、etcd 和 Consul 还常常用于服务发现。例如须要某项服务时，应该连贯到哪个 IP 地址等。在典型的云环境中，虚拟机可能会起起停停，这种动态变化的节点无奈提前晓得服务节点的 IP 地址，因而，能够这样配置服务，每当节点启动时将其网络端口信息向 ZooKeeper 等服务注册，而后其他人只需向 ZooKeeper 的注册表中询问即可。

成员服务

成员服务用来确定以后哪些节点处于活动状态并属于集群的无效成员。因为有限的网络提早，无奈牢靠地检测一个节点到底是否产生了故障。然而，能够将故障检测与共识绑定在一起，让所有节点就节点的存活达成一致意见。

这里仍然存在产生误判的可能性，即节点其实处于活动状态却被谬误地宣判为故障。即使这样，零碎就成员资格问题的决定是全体一致的，这是最重要的。

关于分布式:数据系统分布式系统一致性与共识

一致性保障

可线性化

如何达到线性化？

依赖线性化的场景