「《DDIA》读书笔记」分布式数据系统(下)

4. 分布式系统的挑战

尽管网络在大多数情况下表现良好,但软件的设计必须假定网络偶尔会出现故障,而软件必须正常处理这些故障。时钟也是如此:尽管大多数时间都工作得很好,但需要准备健壮的软件来处理不正确的时钟。

4.1. 故障和部分失效

单个计算机上的软件没有根本性的不可靠原因:当硬件正常工作时,相同的操作总是产生相同的结果(这是确定性的)。如果存在硬件问题(例如,内存损坏或连接器松动),其后果通常是整个系统故障(例如,内核恐慌,“蓝屏死机”,启动失败)。装有良好软件的个人计算机通常要么功能完好,要么完全失效,而不是介于两者之间。

“这是计算机设计中的一个有意的选择:如果发生内部错误,我们宁愿电脑完全崩溃,而不是返回错误的结果,因为错误的结果很难处理。因为计算机隐藏了模糊不清的物理实现,并呈现出一个理想化的系统模型,并以数学一样的完美的方式运作。 CPU指令总是做同样的事情;如果您将一些数据写入内存或磁盘,那么这些数据将保持不变,并且不会被随机破坏。从第一台数字计算机开始,始终正确地计算这个设计目标贯穿始终。

当你编写运行在多台计算机上的软件时,情况有本质上的区别。在分布式系统中,我们不再处于理想化的系统模型中,我们别无选择,只能面对现实世界的混乱现实。而在现实世界中,各种各样的事情都可能会出现问题

总的来说,单机要么处于功能完好,那么处于完全失效的状态,但分布式系统中可能会有部分失效的状态。

超级计算机对于部分失效的解决方案是:通过让部分失败升级为全局失败来处理部分失败。

如果要使分布式系统工作,就必须接受部分故障的可能性,并在软件中建立容错机制。换句话说,我们需要从不可靠的组件构建一个可靠的系统。

4.2. 不可靠的网络

互联网和数据中心(通常是以太网)中的大多数内部网络都是异步分组网络(asynchronous packet networks)。在这种网络中,一个节点可以向另一个节点发送一个消息(一个数据包),但是网络不能保证它什么时候到达,或者是否到达。如果您发送请求并期待响应,则很多事情可能会出错(其中一些如图8-1所示):

  1. 请求可能已经丢失(可能有人拔掉了网线)。
  2. ==请求可能正在排队,稍后将交付(也许网络或接收方过载)。==(网络请求会排队,并在高峰期拥塞在一起)
  3. 远程节点可能已经失效(可能是崩溃或关机)。
  4. 远程节点可能暂时停止了响应(可能会遇到长时间的垃圾回收暂停;请参阅“进程暂停”),但稍后会再次响应。
  5. 远程节点可能已经处理了请求,但是网络上的响应已经丢失(可能是网络交换机配置错误)。
  6. 远程节点可能已经处理了请求,但是响应已经被延迟,并且稍后将被传递(可能是网络或者你自己的机器过载)。

image-20220120132307735

真实世界中存在网络故障,因此许多系统需要自动检测故障节点,例如:

  1. 负载均衡器需要停止向已死亡的节点转发请求(即移除轮询列表)
  2. 在单主复制的分布式数据库中,如果主库失效,则需要将从库之一升级为新主库

可用的自动检测故障节点方案是==超时==,但如何设置超时时间是一个问题,而且非常不幸的是:异步网络具有无限的延迟(即尽可能快地传送数据包,但数据包到达可能需要的时间没有上限),并且大多数服务器实现并不能保证它们可以在一定的最大时间内处理请求。对于故障检测,即使系统大部分时间快速运行也是不够的:如果你的超时时间很短,往返时间只需要一个瞬时尖峰就可以使系统失衡。

所以设置超时时间比较好的方案是通过实验的方式:在一段较长的时期内、在多台机器上测量网络往返时间的分布,以确定延迟的预期变化。然后,考虑到应用程序的特性,可以确定故障检测延迟与过早超时风险之间的适当折衷。当然了,这也是常量超时时间,更好的做法是:系统不是使用配置的常量超时时间,而是连续测量响应时间及其变化(抖动),并根据观察到的响应时间分布自动调整超时时间,类似于TCP的超时重传机制。

是否可以采用同步网络改善不靠谱的网络,比如使用传统的固定电话(电路交换网络),预先分配好固定的,有保证的带宽量,可以使用,但不能简单实用,下面解释一下为什么不能:

  1. 电话网络中的电路与TCP连接有很大不同:电路是固定数量的预留带宽,在电路建立时没有其他人可以使用,而TCP连接的数据包机会性地使用任何可用的网络带宽。您可以给TCP一个可变大小的数据块(例如,一个电子邮件或一个网页),它会尽可能在最短的时间内传输它。 TCP连接空闲时,不使用任何带宽。
  2. 为什么数据中心网络和互联网使用分组交换?答案是,它们针对突发流量(bursty traffic) 进行了优化。一个电路适用于音频或视频通话,在通话期间需要每秒传送相当数量的比特。另一方面,请求网页,发送电子邮件或传输文件没有任何特定的带宽要求,TCP可以动态调整数据传输速率以适应可用的网络容量。——我们只是希望它尽快完成。

4.3. 不可靠的时钟

网络上的每台机器都有自己的时钟,这是一个实际的硬件设备:通常是石英晶体振荡器。这些设备不是完全准确的,所以每台机器都有自己的时间概念。可以在一定程度上同步时钟:最常用的机制是网络时间协议(NTP),它允许一组服务器报告的时间来调整计算机时钟。服务器则从更精确的时间源(GPS接收机)获取时间。

4.3.1. 时间的类型

  1. 日历时钟:System.currentTimeMillis(),日历时钟可能会被强制重置,出现被NTP服务器回拨的情况,具有相当粗略的分辨率。
  2. 单调钟:System.nanoTime(),保持递增,通过用来测量经过时间。

4.3.2. 时钟不靠谱的原因

  1. NTP守护进程配置错误
  2. 防火墙阻止了NTP的通信
  3. 对设备没有完整的控制权
  4. ......

4.3.3. 依赖时钟出现的问题

问题一:有序事件的时间戳

image-20220120171340052

假设ClientA是“精准时间”,就会出现B被丢弃的情况。

因此,尽管通过保留最“最近”的值并放弃其他值来解决冲突是很诱惑人的,但是要注意,“最近”的定义取决于本地的日历时钟,这很可能是不正确的。

问题二:进程暂停(感觉和时间依赖的关系不大,但又有那么一点关系,主要问题还是在多线程的并发上)

while (true) {
    request = getIncomingRequest();
    // 确保租约还剩下至少10秒
    if (lease.expiryTimeMillis - System.currentTimeMillis() < 10000){
        lease = lease.renew();
    }

    if (lease.isValid()) {
        process(request);
    }
}

这个代码有什么问题?首先,它依赖于同步时钟:租约到期时间由另一台机器设置(例如,当前时间加上30秒,计算到期时间),并将其与本地系统时钟进行比较。如果时钟不同步超过几秒,这段代码将开始做奇怪的事情。

那如果换成本地单调时钟呢?

那会有出现另一个问题:如果程序执行中出现了意外的停顿呢?例如,想象一下,线程在lease.isValid()行周围停止15秒,然后才继续。在这种情况下,在请求被处理的时候,租约可能已经过期,而另一个节点已经接管了领导。然而,没有什么可以告诉这个线程已经暂停了这么长时间了,所以这段代码不会注意到租约已经到期了,直到循环的下一个迭代 ——到那个时候它可能已经做了一些不安全的处理请求。

线程暂停的原因:

  1. GC
  2. 虚拟环境中的挂起
  3. OS线程上下文切换
  4. 同步磁盘访问,线程暂停
  5. 内存访问导致页面错误
  6. ctrl+Z
  7. ......

所有这些事件都可以随时抢占(preempt) 正在运行的线程,并在稍后的时间恢复运行,而线程甚至不会注意到这一点。这个问题类似于在单个机器上使多线程代码线程安全:你不能对时序做任何假设,因为随时可能发生上下文切换,或者出现并行运行。

==当在一台机器上编写多线程代码时,我们有相当好的工具来实现线程安全:互斥量,信号量,原子计数器,无锁数据结构,阻塞队列等等。不幸的是,这些工具并不能直接转化为分布式系统操作,因为分布式系统没有共享内存,只有通过不可靠网络发送的消息。==

4.3.4. Google对于时钟的尝试

==Spanner中的Google TrueTime API会提供一个置信区间,得到一个区间[最早,最晚]==

我们之前讨论过的全局快照,我们都知道快照隔离在数据库中非常有用,快照隔离的实现最常见的方式就是单调递增的事务ID,但在分布式环境中,需要协调,全局单调递增的事务ID很难生成,那我们是否可以使用时间戳作为事务ID呢?Spanner以这种方式实现跨数据中心的快照隔离。

它使用TrueTime API报告的时钟置信区间,并基于以下观察结果:如果您有两个置信区间,每个置信区间包含最早和最晚可能的时间戳( $A = [A, A]$, $B=[B, B]$),这两个区间不重叠(即:$A < A < B < B$)的话,那么B肯定发生在A之后——这是毫无疑问的。只有当区间重叠时,我们才不确定A和B发生的顺序。

为了确保事务时间戳反映因果关系,在提交读写事务之前,Spanner在提交读写事务时,会故意等待置信区间长度的时间。通过这样,它可以确保任何可能读取数据的事务处于足够晚的时间,因此它们的置信区间不会重叠。为了保持尽可能短的等待时间,Spanner需要保持尽可能小的时钟不确定性,为此,Google在每个数据中心都部署了一个GPS接收器或原子钟,这允许时钟同步到大约7毫秒以内。

对分布式事务语义使用时钟同步是一个活跃的研究领域。这些想法很有趣,但是它们还没有在谷歌之外的主流数据库中实现。

4.3.5. 如何保证硬实时

某些软件的运行环境要求很高,不能在特定时间内响应可能会导致严重的损失:控制飞机、火箭、机器人、汽车和其他物体的计算机必须对其传感器输入做出快速而可预测的响应。在这些系统中,软件必须有一个特定的截止时间(deadline),如果截止时间不满足,可能会导致整个系统的故障。这就是所谓的硬实时(hard real-time) 系统。

在系统中提供实时保证需要各级软件栈的支持:一个实时操作系统(RTOS),允许在指定的时间间隔内保证CPU时间的分配。库函数必须申明最坏情况下的执行时间;动态内存分配可能受到限制或完全不允许(实时垃圾收集器存在,但是应用程序仍然必须确保它不会给GC太多的负担);必须进行大量的测试和测量,以确保达到保证。

所有这些都需要大量额外的工作,严重限制了可以使用的编程语言、库和工具的范围(因为大多数语言和工具不提供实时保证)。由于这些原因,开发实时系统非常昂贵,并且它们通常用于安全关键的嵌入式设备。而且,“实时”与“高性能”不一样——事实上,实时系统可能具有较低的吞吐量,因为他们必须让及时响应的优先级高于一切。

4.4. 知识,真想与谎言

最常见的法定人数是超过一半的绝对多数(尽管其他类型的法定人数也是可能的)。多数法定人数允许系统继续工作,如果单个节点发生故障(三个节点可以容忍单节点故障;五个节点可以容忍双节点故障)。系统仍然是安全的,因为在这个制度中只能有一个多数——不能同时存在两个相互冲突的多数决定。

4.4.1. 领导者和锁

image-20220120185403252

当使用锁或租约来保护对某些资源(如图8-4中的文件存储)的访问时,需要确保一个被误认为自己是“天选者”的节点不能扰乱系统的其它部分。实现这一目标的一个相当简单的技术就是防护(fencing),如图8-5所示:

image-20220120185451711

如果将ZooKeeper用作锁定服务,则可将事务标识zxid或节点版本cversion用作防护令牌。由于它们保证单调递增,因此它们具有所需的属性。

4.4.2. 系统模型和现实

时序假设的模型:

  1. 同步模型:意味着你知道网络延迟、暂停和时钟漂移将永远不会超过某个固定的上限
  2. 部分同步:意味着一个系统在大多数情况下像一个同步系统一样运行,但有时候会超出网络延迟,进程暂停和时钟漂移的界限
  3. 异步模型:一个算法不允许对时序做任何假设

节点失效的模型:

  1. 崩溃-停止模型:可能会假设一个节点只能以一种方式失效,即通过崩溃。这意味着节点可能在任意时刻突然停止响应,此后该节点永远消失——它永远不会回来。
  2. 崩溃-恢复模型:我们假设节点可能会在任何时候崩溃,但也许会在未知的时间之后再次开始响应。
  3. 拜占庭故障:节点可以做(绝对意义上的)任何事情,包括试图戏弄和欺骗其他节点

==我们通常会选用崩溃-恢复故障的部分同步模型。==

4.4.3. 算法的正确性

为了定义算法是正确的,我们可以描述它的属性。例如,排序算法的输出具有如下特性:对于输出列表中的任何两个不同的元素,左边的元素比右边的元素小。这只是定义对列表进行排序含义的一种形式方式。

如果一个系统模型中的算法总是满足它在所有我们假设可能发生的情况下的性质,那么这个算法是正确的。

4.4.4. 将系统模型映射到现实世界

算法的理论描述可以简单宣称一些事是不会发生的——在非拜占庭式系统中,我们确实需要对可能发生和不可能发生的故障做出假设。然而,真实世界的实现,仍然会包括处理“假设上不可能”情况的代码,即使代码可能就是printf("Sucks to be you")和exit(666),实际上也就是留给运维来擦屁股。(这可以说是计算机科学和软件工程间的一个差异)。

理论分析与经验测试同样重要。

5. 一致性与共识

5.1. 可线性化

线性一致性(也称原子一致性、强一致性、立即一致性、外部一致性)的基本想法是:让一个系统看起来好像只有一个数据副本,而且所有的操作都是原子性的。

首先看一下非线性一致性的系统:

image-20220121135254760

5.1.1. 如何保证线性一致性

线性一致性的要求是,操作标记的连线总是按时间(从左到右)向前移动,而不是向后移动。这个要求确保了我们之前讨论的新鲜度保证:一旦新的值被写入或读取,所有后续的读都会看到写入的值,直到它被再次覆盖。

image-20220121135723027

5.1.2. 依赖线性一致性

  1. 锁定和领导选举,诸如ZooKeeper、etcd。线性一致性存储服务是这些协调任务的基础;
  2. 硬性的唯一性约束。

5.1.3. 跨信道的时序依赖

图像缩放器需要明确的指令来执行尺寸缩放作业,指令是Web服务器通过消息队列发送的。 Web服务器不会将整个照片放在队列中,因为大多数消息代理都是针对较短的消息而设计的,而一张照片的空间占用可能达到几兆字节。取而代之的是,首先将照片写入文件存储服务,写入完成后再将给缩放器的指令放入消息队列。

image-20220121143323159

如果文件存储服务是线性一致的,那么这个系统应该可以正常工作。如果它不是线性一致的,则存在竞争条件的风险:消息队列(图9-5中的步骤3和4)可能比存储服务内部的复制(replication)更快。在这种情况下,当缩放器读取图像(步骤5)时,可能会看到图像的旧版本,或者什么都没有。如果它处理的是旧版本的图像,则文件存储中的全尺寸图和略缩图就产生了永久性的不一致。

出现这个问题是因为Web服务器和缩放器之间存在两个不同的信道:文件存储与消息队列。没有线性一致性的新鲜性保证,这两个信道之间的竞争条件是可能的。这种情况类似于图9-1,数据库复制与Alice的嘴到Bob耳朵之间的真人音频信道之间也存在竞争条件。

线性一致性并不是避免这种竞争条件的唯一方法,但它是最容易理解的。如果你可以控制额外信道(例如消息队列的例子,而不是在Alice和Bob的例子),则可以使用在“读己之写”讨论过的类似方法,不过会有额外的复杂度代价。

总的来说,就是文件存储服务和MQ有竞争,但可以采用「读自己写」的方法解决。,比如MQ读文件存储服务的主库,避免复制滞后的问题;也可以在记录下存储文件时的时间戳,发送消息时携带上,图像压缩器只会获取存储时间大于携带时间戳的文件,如果获取不到就去另一台机器上获取,以此类推。

5.1.4. 实现线性一致的系统

  1. 单主复制(可能线性一致,因为可能会先脑裂情况)
  2. 共识算法(线性一致)
  3. 多主复制(非线性一致)
  4. 无主复制(可能不是线性一致,见下图)

image-20220121200941613

n=3,w=3,r=2,法定人数满足了w+r>n,但A返回了新值,B还是返回了旧值。

总而言之,最安全的做法是:假设采用Dynamo风格无主复制的系统不能提供线性一致性。

5.1.5. CAP定理

不需要线性一致性的应用对网络问题有更强的容错能力。这种见解通常被称为CAP定理,由Eric Brewer于2000年命名,尽管70年代的分布式数据库设计者早就知道了这种权衡。

在网络正常工作的时候,系统可以提供一致性(线性一致性)和整体可用性。发生网络故障时,你必须在线性一致性和整体可用性之间做出选择。总而言之,围绕着CAP有很多误解和困惑,并不能帮助我们更好地理解系统,所以最好避免使用CAP。

CAP定理的正式定义仅限于很狭隘的范围,它只考虑了一个一致性模型(即线性一致性)和一种故障(网络分区,或活跃但彼此断开的节点)。它没有讨论任何关于网络延迟,死亡节点或其他权衡的事。 因此,尽管CAP在历史上有一些影响力,但对于设计系统而言并没有实际价值。

==在分布式系统中有更多有趣的“不可能”的结果,且CAP定理现在已经被更精确的结果取代,所以它现在基本上成了历史古迹了。==

5.1.6. 线性一致性和网络延迟

Attiya和Welch证明,如果你想要线性一致性,读写请求的响应时间至少与网络延迟的不确定性成正比。

所以很多分布式数据库为了提高性能而选择牺牲了线性一致性。

5.2. 顺序保证

5.2.1. Lamport时间戳

Lamport时间戳,莱斯利·兰伯特(Leslie Lamport)于1978年提出,现在是分布式系统领域中被引用最多的论文之一。

每个节点都有一个唯一标识符,和一个保存自己执行操作数量的计数器。 兰伯特时间戳就是两者的简单组合:(计数器,节点ID)$(counter, node ID)$。两个节点有时可能具有相同的计数器值,但通过在时间戳中包含节点ID,每个时间戳都是唯一的。

image-20220121211504166Lamport时间戳与物理的日历时钟没有任何关系,但是它提供了一个全序:如果你有两个时间戳,则计数器值大者是更大的时间戳。如果计数器值相同,则节点ID越大的,时间戳越大。

虽然Lamport时间戳能够确认操作的因果关系,但是在分布式系统之中仍然存在一些问题:

请考虑一个系统,该系统需要确保用户名唯一标识用户帐户。如果两个用户同时尝试创建具有相同用户名的帐户,则其中一个应该成功,另一个应该失败。显然,如果两个相同的用户名的账户创建,选择具有较低的时间戳的操作成功,因为Lamport时间戳是完全有序的,这种比较是有效的。但是为了确保没有其他节点在同时在较早的时间创建帐户,所以节点不得不与其他每个节点通信进行确认。如果出现网络问题,其他节点中的一个已经失效或无法到达,则系统也将失效。

Lamport时间戳的问题在于:需要收集所有操作之后,操作的总顺序才会出现。如果另一个节点有其他操作,在不知道的情况下,无法构造操作的最终顺序。

5.2.2. 全序广播

线性一致性与全序广播------《Designing Data-Intensive Applications》读书笔记12

全序广播的机制是使用:**通过单Leader多Follower机制,在Leader节点上对所有操作进行排序,从而决定了整个操作顺序,并将操作顺序进行广播。**全序广播可以保证全局知晓信息,而解决Lamport时间戳面临的问题。但是全序广播同样要解决这样几个问题:如果吞吐量大于单Leader的处理量,那么如何扩展系统,以及出现Leader失效的情况,如何进行故障转移。

全序广播要求满足如下两个属性总是被满足:

  • 可靠的交付,没有消息丢失:如果消息被传递到一个节点,它将被传递给所有节点。
  • 完全有序传递,消息以相同的顺序传递给每个节点。

5.2.3. 全序广播实现线性一致的存储

全序广播是异步的:消息被保证以固定的顺序可靠地传送,但是不能保证消息何时被送达。相比之下,线性一致性是新鲜性的保证:读取一定能看见最新的写入值。

拿用户名的那个例子来说,全序广播通过追加日志的方式实现线性一致的CAS:

  1. 在日志中追加一条消息,试探性地指明你要声明的用户名。
  2. 读日志,并等待你刚才追加的消息被读回。
  3. 检查是否有任何消息声称目标用户名的所有权。如果这些消息中的第一条就是你自己的消息,那么你就成功了:你可以提交声称的用户名(也许是通过向日志追加另一条消息)并向客户端确认。如果所需用户名的第一条消息来自其他用户,则中止操作。

这也只保证了写入是线性一致的,不保证读取也是线性一致的,这里有3个方案保证读取也是线性一致的,基本思路都是把异步变同步:

  1. 你可以通过在日志中追加一条消息,然后读取日志,直到该消息被读回才执行实际的读取操作。消息在日志中的位置因此定义了读取发生的时间点。 (etcd的法定人数读取有些类似这种情况。)
  2. 如果日志允许以线性一致的方式获取最新日志消息的位置,则可以查询该位置,等待该位置前的所有消息都传达到你,然后执行读取。 (这是Zookeeper sync() 操作背后的思想)。
  3. 你可以从同步更新的副本中进行读取,因此可以确保结果是最新的。

5.2.4. 线性一致性存储实现全序广播

全序广播需要发送的消息通过线性一致寄存器CAS递增并附加到消息中,然后把消息发送给所有节点,收件人按序列号接收。

请注意,与Lamport时间戳不同,通过自增线性一致性寄存器获得的数字形式上是一个没有间隙的序列。因此,如果一个节点已经发送了消息 4 并且接收到序列号为 6 的传入消息,则它知道它在传递消息 6 之前必须等待消息 5 。Lamport时间戳则与之不同 —— 事实上,这是全序广播和时间戳排序间的关键区别。

讲人话就是:全序广播将Lamport时间戳的操作顺序聚合在一起,离散化了一下,变成了一段连续的序列。

可以证明,线性一致的CAS(或自增并返回)寄存器与全序广播都都等价于共识问题。也就是说,如果你能解决其中的一个问题,你可以把它转化成为其他问题的解决方案。这是相当深刻和令人惊讶的洞察!

5.3. 分布式事务与共识

5.3.1. 二阶段提交

2PC是一种用于实现跨多节点的原子事务提交算法,即确保所有节点提交或所有节点中止。

正常情况下,2PC事务以应用在多个数据库节点上读写数据开始。我们称这些数据库节点为参与者(participants)。当应用准备提交时,协调者开始阶段 1 :它发送一个准备(prepare) 请求到每个节点,询问它们是否能够提交。然后协调者会跟踪参与者的响应:

  1. 如果所有参与者都回答“是”,表示它们已经准备好提交,那么协调者在阶段 2 发出提交(commit) 请求,然后提交真正发生。、
  2. 如果任意一个参与者回复了“否”,则协调者在阶段2 中向所有节点发送中止(abort) 请求。

2PC的阻塞点就是协调者的失效会带来的后果无法预知。

5.3.2. 实践中的分布式事务

分布式事务有常见的两种类型:

  1. 数据库内部的分布式事务
  2. 异构分布式事务(例如来自不同厂商的两个数据库)

ps:XA事务不是一个网络协议,它只是一个用来与事务协调者连接的C API

分布式事务的限制有下面几个:

  1. 协调者的单机问题
  2. 服务器应用通常是无状态的,但是当协调者成为应用服务器的一部分,他会改变部署的性质,使得应用服务器不再是无状态的。
  3. XA需要兼容各种系统,所以功能只能取各个系统的最小公约数

5.3.3. 容错共识

共识算法满足如下几点:

  1. 协商一致性:所有的节点都接受相同的决议
  2. 诚实性:所有节点不能反悔,即对一项提议不能有两次决定
  3. 有效性:如果决定了值v,则v一定是由某个节点所提议的
  4. 可终止性:节点如果不崩溃则最终一定可以达成决议

有许多著名的共识算法:VSR,Paxos,Raft以及Zab

这些算法决定了值的顺序,使它们成为全序广播算法

全序广播要求将消息按照相同的顺序,恰好传递一次,准确传送到所有节点。如果仔细思考,这相当于进行了几轮共识:在每一轮中,节点提议下一条要发送的消息,然后决定在全序中下一条要发送的消息。

所以,全序广播相当于重复进行多轮共识(每次共识决定与一次消息传递相对应)

  1. 由于协商一致性,所有节点决定以相同的顺序传递相同的消息。
  2. 由于诚实性,消息不会重复。
  3. 由于有效性性,消息不会被损坏,也不能凭空编造。
  4. 由于可终止性,消息不会丢失,所以一定能达成决议。

迄今为止所讨论的所有共识协议,在内部都以某种形式使用一个领导者,所以怎么动态的选举出一个领导者呢?

因此,我们有两轮投票:第一次是为了选出一位领导者,第二次是对领导者的提议进行表决。关键的洞察在于,这两次投票的法定人群必须相互重叠(overlap):如果一个提案的表决通过,则至少得有一个参与投票的节点也必须参加过最近的领导者选举。因此,如果在一个提案的表决过程中没有出现更高的纪元编号。那么现任领导者就可以得出这样的结论:没有发生过更高时代的领导选举,因此可以确定自己仍然在领导。然后它就可以安全地对提议值做出决定。

5.3.4. 共识算法的代价

共识算法对于分布式系统来说是一个巨大的突破:它为其他充满不确定性的系统带来了基础的安全属性(协商一致性,诚实性和有效性),然而它们还能保持容错(只要多数节点正常工作且可达,就能取得进展)。它们提供了全序广播,因此它们也可以以一种容错的方式实现线性一致的原子操作。

但它也有它的局限性:

  1. 协商过程之中需要对提案进行表决,而这个表决的过程本质上是一种同步复制。前文我们已经探讨过同步复制与异步复制的优缺点。而在实践之中,我们通常配置使用异步复制。某些提交的数据可能在故障转移时丢失,但为了更好的性能,许多人选择接受这种风险。
  2. 协商一致性严格要求需要多数决。这意味着你需要至少三个节点来容忍一个故障(剩下的两个组成多数),或者至少五个节点来容忍两个故障(剩下的三个组成多数)。
  3. 大多数协商一致算法假设一组固定的节点参与投票,这意味着不能轻易的动态添加或删除集群中的节点。
  4. 如何检测失效的节点也是一个问题。在具有高度可变网络延迟的环境中,经常发生一个节点错误地认为Leader的失效。虽然这个错误不会损害系统的安全性,但是频繁的Leader选举会导致系统糟糕的表现,因为系统最终会花费更多的时间去选择一个领导者而不是做任何有用的工作。

5.4. 总结

线性一致性:其目标是使多副本数据看起来好像只有一个副本一样,并使其上所有操作都原子性地生效。

共识问题等价于「线性一致性的CAS寄存器」,「原子事务提交」,「全序广播」,「锁和租约」,「成员/协调服务」,「唯一性约束」。

并不是所有系统都需要共识:例如,无领导者复制和多领导者复制系统通常并不支持全局共识。正因如此,这些系统可能会发生冲突,但或许也可以接受或寻找其他方案,例如没有线性化保证时,就需要努力处理好数据多个冲突分支以及版本合并等。

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×