Kyle's Notebook

《DDIA》阅读笔记(九):一致性与共识(可线性化)

Word count: 3.2kReading time: 10 min
2021/02/13

《DDIA》阅读笔记(九):一致性与共识(可线性化)

本章结构如下:

  • 一致性与共识
    • 可线性化
      • 达成条件
      • 可线性化与可串行化
      • 依赖条件
        • 加锁与主节点选举
        • 约束与唯一性保证
        • 跨通道的时间依赖
      • 实现方式
        • 主从复制(部分支持可线性化)
        • 共识算法(可线性化)
        • 多主复制(不可线性化)
        • 无主复制(可能不可线性化)
      • 线性化代价
        • CAP 理论
        • 非线性系统
        • 网络延迟

为了构建容错系统,最好先建立一套通用的抽象机制和与之对应的技术保证,只需实现一次,其上的各种应用程序都可以安全地信赖底层的保证。

共识:即所有的节点就某一项提议达成一致。通过实现正确得共识算法,可以避免发生脑裂等问题。

一致性保证:

  • 大多数多副本系统都至少提供了最终一致性保证,但无法确定系统何时收敛。即使系统在大多数情况下都运行良好,在系统面临故障或高并发压力时,最终一致性的临界条件或错误才会对外暴露,因此难以测试和发现错误。

  • 分布式系统下也存在更强的一致性模型,可使上层应用逻辑更简单、不容易出错,但也意味着牺牲性能或容错性,需要结合自身需求选择。

  • 分布式一致性模型与事务相似,但事务隔离主要为了处理并发执行事务时的各种临界条件,而分布式一致性主要是针对延迟和故障等问题来协调副本之间的状态。

在最终一致性数据库中,同时查询不同的副本可能会得到不同的答案。

可线性化的思想:数据库对上提供只有单个副本的假象,即每个客户端都拥有相同的数据视图,而不必担心复制滞后。一旦某个客户端成功提交写请求,后续其他所有客户端的读请求一定都能看到刚写入的值。

可线性化的达成条件:如果与写并发的读操作可能返回旧值或新值,不同的读客户端会看到旧值和新值之间来回跳变的情况。为使系统可线性化,需要添加约束:在写操作的开始与结束之间必定存在某个时间点,x 的值发生了从 0 到 1 的跳变。如果某个客户端的读取返回了新值 1,即使写操作尚未提交,所有后续的读取也必须全部返回新值。

可线性化与可串行化

可串行化和可线性化是正交的概念:

  • 可串行化:事务的隔离属性,其中每个事务可以读写多个对象。它用来确保事务执行的结果与串行执行的结果完全相同,即使串行执行的顺序可能与事务实际执行顺序不同。

  • 可线性化:读写寄存器(单个对象)的最新值保证。它并不要求将操作组合到事务中,因此无法避免写倾斜等问题,除非采用其他额外措施(如实体化冲突)。

数据库可以同时支持可串行化与线性化,被称为 严格的可串行化 或者 强的单副本可串行化

  • 基于两阶段加锁或实际以串行执行都是典型的可线性化。

  • 可串行化的快照隔离不是可线性化(不保证读取到最新的数据):它可以从一致性快照中读取,以避免读、写之间的竞争。由于其不包括快照点创建时刻之后的写入数据,从快照读取肯定不满足线性化。

依赖条件

在以下场景需要线性化保证。

加锁与主节点选举

主从复制系统需要确保有且只有一个主节点,否则会产生脑裂:一般是加上满足可线性化的锁:所有节点都必须同意某个节点持有锁。

  • 提供协调者服务的系统:ZooKeeper、Etcd,其中线性化存储服务是所有这些协调服务的基础。

  • Oracle Real Application Clusters (RAC) 的分布式锁有更细粒度的实现:每个磁盘页面均设置一把锁,多个节点可以并发地共享访问存储系统。可线性化的锁处于事务执行的关键路径上。

出于性能考虑,RAC 部署时通常都要求专用的集群互连网络连接数据库节点。

约束与唯一性保证

比如用户名唯一标识一名用户,如果在写入数据时强制执行这些约束,则需要线性化。

  • 由于操作上要求线性化,本质上与加锁类似。在某些实际场合中可以放宽这些限制,比如使用其他措施提供补偿。

  • 硬性的唯一约束需要线性化保证,比如主键,其他属性约束则不一定,比如外键等。

跨通道的时间依赖

线性化违例之所以被注意到,是因为系统中存在其他的通信渠道。比如以下的例子中用户可以上传照片到某网站,有一个后台进
程将照片调整为更低的分辨率以方便更快下载:

图片上传下载架构

  • 采用消息队列将图像调整命令从 Web 服务器发送到调整器,Web 服务器把照片先写入文件存储服务,完成后把调整命令写入队列。

  • 如果文件存储服务不是可线性化的,则可能存在竞争:消息队列比存储服务内部的复制执行更快。当调整模块在读取图像看到图像的某个旧版本或读取不到内容。可能导致文件存储中的全尺寸图片与调整之后图片出现永久不一致。

由于 Web 服务器和调整模块之间存在文件存储服务器和消息队列两个不同的通信通道,如果没有线性化就近性保证,两个通道之间存在竞争条件。

如果可以控制某一个通信通道可以尝试保证“写后读”,但会引入额外的复杂性。

实现方式

在多副本系统中实现线性化,本质上意味着表现为只有一个数据副本,且在其上的所有操作都是原子的。

最简单的实现方法是只用一个副本,但会牺牲容错。因此需要考虑的是各种复制方案是否满足可线性化。

主从复制(部分支持可线性化)

主节点承担数据写入,从节点在各自节点上维护备份副本。

  • 如果在主节点或者同步更新的从节点上读取,则可以满足线性化。

  • 但并非每个数据库实例都是可线性化的,主要是可能采用了快照隔离的设计,或者存在并发方面的 bug。

  • 在主节点上读取的前提是确知主节点,但从节点都可能自认为是主节点,如果“自以为”的主节点对外提供服务就会违反线性化。

  • 对于异步复制,在故障切换过程中甚至可能丢失已提交的写入,导致同时违反持久性和线性化。

共识算法(可线性化)

与主从复制机制相似,但通过内置措施防止脑裂和过期的版本。

通过共识算法可安全实现线性化存储,如 ZooKeeper 和 Etcd。

多主复制(不可线性化)

通常无法线性化,主要由于它们同时在多个节点上执行并发写入,并将数据异步复制到其他节点。

由于存在多副本,它们可能会产生冲突的写入,需要额外的解决方案。

无主复制(可能不可线性化)

配置法定读取和写入满足(w + r > n)可满足一定程度的一致性。但也完全取决于 Quorum 的配置以及强一致性的定义,可能无法保证线性化:比如基于墙钟的 LWW 冲突解决方式就是非线性化(时钟偏移时间戳无法保证与事件顺序一致)。

不规范的 Quorum 会破坏线性化,但遵从严格的 Quorum 也不一定能保证可线性化。比如:

  • x 的初始值为 0,客户端 C 向所有的三个副本发送请求将其更新为 1(n = w = 3)。

  • 客户端 A 从两个节点(r = 2)读取数据,在其中一个节点上看到新值 1。

  • 客户端 B 从两个节点读取,两个节点都返回 0。

  • 即使满足仲裁条件(w + r > n),但 B 的请求在 A 的请求完成后才开始(此时 C 还未完成),A 得到新值,B 得到旧值,显然不是线性化。

满足线性化的方法:读操作在返回结果给应用之前必须同步执行读修复、写操作在发送结果之前必须读取 Quorum 节点以获取最新值。但这样会严重牺牲性能,且只能实现线性化读写,线性化的“比较设置”操作需要共识算法支持。

线性化代价

对于主从复制或多主复制,网络中断必然违背可线性化读写需求。如果客户端可以直接连接到主节点所在的数据中心,则可以避免此问题,否则,只能等到数据中心之间的网络恢复之后才能继续正常工作。

CAP 理论

对于任何可线性化的数据库,只要有不可靠的网络都会发生违背线性化的风险。

  • 如果要求线性化,但由于网络方面的问题、某些副本与其他副本断开连接之后无法继续处理请求,就必须等待网络修复或者直接返回错误,结果都是服务 不可用

  • 如果不要求线性化,断开连接之后每个副本可独立处理请求(例如多主复制模型下的写操作),此时服务可用但结果行为不符合线性化,即 不一致

不要求线性化的应用更能容忍网络故障,这种思路被称为 CAP 理论:

  • 一致性(Consistency)

  • 可用性(Availability)

  • 分区容错性(Partition Tolerance)

其中在分布式系统中分区是必然的,网络故障不论是否可接受都会发生,所以 CAP 定理的含义是:一旦发生网络故障,只能选择线性化(一致性)或可用性。

非线性系统

很少有系统可以真正保证线性化,现代多核 CPU 上的内存就是非线性化:

  • 如果某个 CPU 核上运行的线程修改一个内存,另一个 CPU 核上的线程尝试读取,则系统无法保证可以读到刚写入的值,除非使用内存屏障或 fence 指令。

  • 每个 CPU 核都有自己独立的 cache 和寄存器,内存访问首先进入 cache 系统,所有修改默认会异步地刷新到主存。

  • 访问 cache 比访问主存要快得多,异步刷新的特性对于现代 CPU 的性能至关重要,同时这就导致出现了多个数据副本(一个在主存,另外几个在不同级别的 cache 中),而副本更新是异步的,无法保证线性化。

网络延迟

CAP 理论不适用于当今的“多核-内存”一致性模型,因为在计算机内部通常假设通信是可靠的(不会假定 CPU 核与其他核断开后还能安然工作),不支持线性化是为了提高性能而非容错性。

分布式数据库也是处于性能考虑。由于无论网络故障是否发生,线性化对性能影响都是巨大的。假设要满足线性化,则读写请求响应时间至少要与网路中延迟成正比,由于网络高度不确定的延迟,线性化读写性能必然非常差。

CATALOG
  1. 1. 《DDIA》阅读笔记(九):一致性与共识(可线性化)
    1. 1.1. 可线性化与可串行化
    2. 1.2. 依赖条件
      1. 1.2.1. 加锁与主节点选举
      2. 1.2.2. 约束与唯一性保证
      3. 1.2.3. 跨通道的时间依赖
    3. 1.3. 实现方式
      1. 1.3.1. 主从复制(部分支持可线性化)
      2. 1.3.2. 共识算法(可线性化)
      3. 1.3.3. 多主复制(不可线性化)
      4. 1.3.4. 无主复制(可能不可线性化)
    4. 1.4. 线性化代价
      1. 1.4.1. CAP 理论
      2. 1.4.2. 非线性系统
      3. 1.4.3. 网络延迟