第一章可靠、可扩展与可维护的应用系统

对于一个应用系统，如果“数据”是其成败决定性因素，包括数据的规模、数据的复杂度或者数据产生与变化的速率等，那么可以称之为“数据密集型应用系统”。与之对应的计算密集型，CPU 主频往往是后者最大的制约瓶颈。

认识数据系统

• 常见应用系统构成模块
  • 数据库：存储数据，之后再次访问。
  • 高速缓存：缓存复杂或操作代价高昂的结果，加快下一次访问。
  • 索引：用户可以按关键字搜索数据并支持各种过滤。
  • 流式处理：持续发送消息至另一个进程，采取异步方式处理。
  • 批处理：定期处理大量的累计数据。
• 大多数数据密集型系统需要注意到三个问题
  • 可靠性（Reliability）：当出现意外情况如硬件、软件故障、人为失误等，系统应可以继续正常运转，虽然性能可能降低，但确保功能准确。
  • 可扩展性（Scalability）：随着规模的增大，例如数据量、流量或复杂性，系统应以合理的方式来匹配这种增长。
  • 可维护性（Maintainability）：随之时间的推移，许多新的人员参与到系统开发和运维，以维护现有功能或适配新场景，系统都应高效运转。

可靠性

• 系统即使发生了某些错误，系统仍可以继续正常工作。
• 故障通常被定义为组件偏离其正常规格，而失效意味系统作为一个整体停止，无法向用户提供所需的服务。
• 我们不太可能将故障概率降低到零，因此通常涉及容错机制来避免从故障引发系统失败。因此需要我们在不可靠组件基础上构建可靠性系统的相关技术。
• 一般包括如下故障
  • 硬件故障
    • 一般容易想到有：硬盘崩溃，内存故障，电力停电，有人误拔掉网线。
    • 我们第一反应是为硬件添加冗余来减少系统故障率，当一个组件发生故障，冗余组件可以快速接管，之后再更换失效的组件，虽然不能完全放置硬件故障所引发的失效，但是被普遍采用。
  • 软件错误
    • 由于软件错误，导致输入特定值时应用服务器总是崩溃。
    • 一个应用程序使用了某些共享资源如 CPU，没有释放回来。
    • 系统依赖某些服务，但该服务突然变慢，甚至无响应。
    • 级联故障，某个组件的小故障，引发另一个组件的故障。
    • 需要注意
      • 假设条件与系统之间交互，全面测试。
      • 进程隔离，允许进程崩溃，并自动重启。
      • 对于消息队列，消息的幂等性等。
  • 人为错误
    • 如何防止人为错误
      • 以最小出错的方式设计系统，精心设计抽象层、API 以及管理界面。
      • 想办法分离最容易出错的地方、容易引发故障的接口。
      • 充分的测试。
      • 当出现人为失误，提供快速的恢复机制以尽量减少故障影响。
      • 设置详细而清晰的监控子系统，包括性能指标和错误率。
      • 推行管理流程并加以培训。

可扩展性

• 可靠性通常包含如下指标
  • 评测负载
    • 对于 Twitter 的主键，以及用户的缓存。
  • 性能
    • 如果负载增加，将会发生什么
      • 负载增加，但系统资源保持不变，系统性能会发生什么变化？
      • 负载增加，如果要保持性能不变，需要增加多少资源？
    • 注意延迟和响应时间的区别？
    • 一个服务涉及多个不同的后端调用，则最慢的调用会拖累整个服务响应时间。
    • 针对特定级别负载而设计的架构不太可能应付超出预设目标10 倍的实际负载，如果目标服务处理快速增长阶段，那么需要认真考虑每增加一个数据量大负载，架构应如何设计。
    • 现在谈论更多的是如何在垂直扩展和水平扩展之间做取舍。
    • 把无状态服务分布然后扩展至多台机器相对比较容易，而有状态服务则从单个节点扩展到分布式多机环境的复杂性会大大增加。
  • 延迟百分位数
  • 吞吐量

可维护性

• 众所周知，软件的大部分成本并不在最初的开发阶段，而是在于整个生命周期内持续的投入，这包括维护与缺陷修复，监控系统来保持正常运行、故障排查、适配新平台、搭配新场景、技术缺陷的完美以及增加新功能等。
• 坦白说，每一个遗留系统总有其过期的理由，我们很难给出一个通用的建议该如何处理他们。
• 软件系统的三个设计原则
  • 可运维性：运维更轻松
    • 一个优秀的运行团队至少需要负责
      • 监控系统的健康状况，出现异常及时恢复。
      • 系统故障或性能下降，追踪问题。
      • 保持软件和平台的更新。
      • 了解不同系统之间如何交互影响，避免执行带有破坏性的操作。
      • 预测未来可能的问题，并在问题发生之前既解决。
      • 建立用于部署、配置管理等良好的实践规范和工具包。
      • 执行复杂度维护任务。
      • 当配置更改时，维护系统的安全稳健。
      • 制定流程来规范操作行为，来保持生产环境的稳定。
      • 保持相关的知识传承。
  • 简单性
    • 复杂性的表现方式
      • 状态空间的膨胀
      • 模块之间紧耦合，相互依赖
      • 不一致的命名和术语
      • 为了性能而采取的特殊处理
      • 未解决特定问题而引入的特殊框架
    • 消除意外复杂性最好手段之一是抽象。一个好的设计抽象可以隐藏大量的实现细节，并对外提供干净、易懂的接口。
    • 使用高级的开发语言。
  • 可演化性
    • 最终可以轻松地修改数据系统，使其适应不断变化的需求，这和简单性欲抽象性密切相关。
    • 简单易懂的系统往往比复杂的系统更容易修改。

小结

• 一个应用必须完成预期的多种需求，主要包括功能性需求和非功能性需求。
• 功能性需求
  • 应该做什么
  • 存储
  • 索引
  • 检索
  • 处理数据
• 非功能需求
  • 常规特性
  • 安全性
  • 可靠性
  • 合规性
  • 可伸缩性
  • 兼容性
  • 可维护性

第二章数据模型与查询语言

语言的边界就是思想的边界。

• 一个复杂的应用程序可能会有更多的中间层，比如基于 API 的 API，每个层都通过提供一个明确的数据模型来隐藏更低层次中的复杂性。

• 掌握一个数据模型需要花费很多精力（想想关系数据建模有多少本书）。即便只使用一个数据模型，不用操心其内部工作机制，构建软件也是非常困难的。然而，因为数据模型对上层软件的功能（能做什么，不能做什么）有着至深的影响，所以选择一个适合的数据模型是非常重要的。

关系模型与文档模型

• 最著名的数据模型就是 SQL ，于1970 被 Edgar Codd 提出
  • 数据被组织成关系，其中每个关系是元组的无序集合。
• 当时的其他数据库迫使应用程序开发人员必须考虑数据库内部的数据表示形式。关系模型致力于将上述实现细节隐藏在更简洁的接口之后。

NoSQL

• 采用 NoSQL 的几个因素
  • 需要比关系数据库更好的可伸缩性，包括非常大的数据集或非常高的的写入吞吐量
  • 相比商业数据库，免费和开源更受偏爱
  • 关系数据库不能很好的支持一些特殊的查询操作
  • 受挫与关系模型的局限，渴望一种更具多态性和表现力的数据模型

关系和文档数据库的整合

• 随着时间的推移，关系数据库和文档数据库似乎变得越来越相似。
• 数据模型相互补充，如果一个数据库能够处理类似文档的数据，并能够对其执行关系查询，那么应用程序就可以使用最符合其需求的功能组合。

图数据模型

• 一个图由两种对象组成：顶点（vertices）（也称为节点（node）或实体（entities））和边（edges）（也称为关系（relationships）或弧（arcs））。
• 社交图谱、网络图谱、公路或铁路网络
• 属性图
  • 每个顶点
    • 唯一的标识符
    • 一组出边
    • 一组入边
    • 一组属性（键值对）
  • 每条边包括
    • 唯一标识符
    • 边的起点、尾部顶点
    • 边的终点、头部顶点
    • 描述两个顶点之间关系类型的标签
    • 一组属性（键值对）

小结

• 文档数据库的应用场景：数据通常是自我包含的，而且文档之间的关系非常稀少。
• 图形数据库之间用户相反的场景：任意事物都可能与任何事物相关联。
• 文档数据库和图数据库有一个共同点，就是他们通常不会为存储的数据强制一个模式，可以使应用程序更容易适应不断变化的需求。

第三章、存储于检索

一个数据库在基础的层次上需要完成两件事情：当你把数据交给数据库时，它应当把数据存储起来，而后当你向数据库要数据时，它应当把数据返回给你。

• 两大类存储引擎
  • 日志结构（log-structured）
  • 面向页面（page-oriented）

驱动数据库的数据结构

一个最简单的数据库

#!/bin/bash

db_set (){
	echo "$1,$2">> database
}

db_get (){
	grep "^$1," database | sed -e "s/^$1,//"| tail -n 1
}

• 数据库使用日志记录的一个弊端在于，如果数据量特别大，我们在查找的时候，需要从头到尾扫描，算法开销属于线性增长。
• 为了提高数据库的查询效率，人们使用索引，索引是从主数据衍生的附加的结构，许多数据结构允许添加与删除索引，不会影响数据的内容，只影响数据查询的性能。
• 维护额外的索引会产生开销，任何类型的索引通常都会减慢写入速度，因为每次写入数据时都需要更新索引。
• 哈希索引，键值存储与字典类型非常相似，通常字典都是用散列映射实现的。
• 哈希映射：保留一个内存中的哈希映射，其中每个键映射到一个数据文件中的字节偏移量，指明了可以找到对应值的位置。当你将新的键值对追加写入文件中时，还要更新散列映射，以反映刚刚写入的数据的偏移量。当你想查找一个值时，使用哈希映射来查找文件中的偏移量，寻找（seek）该位置并读取改值。
• 数据库日志存储考虑因素
  • 文件格式
  • 删除记录
  • 崩溃恢复
  • 部分写入记录
  • 并发控制
• 一个页面会被指定为B树的根；在索引中查找一个键时，就从这里开始。该页面包含几个键和对子页面的引用。每个子页面负责一段连续范围的键，引用之间的键，指明了引用子页面的键范围。
• 如果要更新B树中现有键的值，则搜索包含该键的叶页，更改该页中的值，并将该页写回到磁盘（对该页的任何引用保持有效）。如果你想添加一个新的键，你需要找到其范围包含新键的页面，并将其添加到该页面。如果页面中没有足够的可用空间容纳新键，则将其分成两个半满页面，并更新父页面以解释键范围的新分区。
• B树的基本底层写操作是用新数据覆盖磁盘上的页面。假定覆盖不改变页面的位置：即，当页面被覆盖时，对该页面的所有引用保持完整。这与日志结构索引（如LSM树）形成鲜明对比，后者只附加到文件（并最终删除过时的文件），但从不修改文件。
• 为了使数据库对崩溃具有韧性，B树实现通常会带有一个额外的磁盘数据结构：预写式日志（WAL, write-ahead-log）（也称为重做日志（redo log））。这是一个仅追加的文件，每个B树修改都可以应用到树本身的页面上。当数据库在崩溃后恢复时，这个日志被用来使B树恢复到一致的状态。
• 更新页面的一个额外的复杂情况是，如果多个线程要同时访问B树，则需要仔细的并发控制——否则线程可能会看到树处于不一致的状态。这通常通过使用锁存器（latches）（轻量级锁）保护树的数据结构来完成。日志结构化的方法在这方面更简单，因为它们在后台进行所有的合并，而不会干扰传入的查询，并且不时地将旧的分段原子交换为新的分段。
• B 树和 LSM 树区别
  • 通常LSM树的写入速度更快，而B树的读取速度更快。 LSM树上的读取通常比较慢，因为它们必须在压缩的不同阶段检查几个不同的数据结构和SSTables。
  • LSM 优点
    • B树索引必须至少两次写入每一段数据：一次写入预先写入日志，一次写入树页面本身（也许再次分页）。即使在该页面中只有几个字节发生了变化，也需要一次编写整个页面的开销。有些存储引擎甚至会覆盖同一个页面两次，以免在电源故障的情况下导致页面部分更新。
    • 由于反复压缩和合并SSTables，日志结构索引也会重写数据。这种影响——在数据库的生命周期中写入数据库导致对磁盘的多次写入——被称为写放大（write amplification）。需要特别注意的是固态硬盘，固态硬盘的闪存寿命在覆写有限次数后就会耗尽。
    • 在写入繁重的应用程序中，性能瓶颈可能是数据库可以写入磁盘的速度。在这种情况下，写放大会导致直接的性能代价：存储引擎写入磁盘的次数越多，可用磁盘带宽内的每秒写入次数越少。
    • LSM树通常能够比B树支持更高的写入吞吐量，部分原因是它们有时具有较低的写放大（尽管这取决于存储引擎配置和工作负载），部分是因为它们顺序地写入紧凑的SSTable文件而不是必须覆盖树中的几个页面。这种差异在磁性硬盘驱动器上尤其重要，顺序写入比随机写入快得多。
    • LSM树可以被压缩得更好，因此经常比B树在磁盘上产生更小的文件。 B树存储引擎会由于分割而留下一些未使用的磁盘空间：当页面被拆分或某行不能放入现有页面时，页面中的某些空间仍未被使用。由于LSM树不是面向页面的，并且定期重写SSTables以去除碎片，所以它们具有较低的存储开销，特别是当使用平坦压缩时。
  • LSM树的缺点
    • 日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。
    • 压缩的另一个问题出现在高写入吞吐量：磁盘的有限写入带宽需要在初始写入（记录和刷新内存表到磁盘）和在后台运行的压缩线程之间共享。写入空数据库时，可以使用全磁盘带宽进行初始写入，但数据库越大，压缩所需的磁盘带宽就越多。
    • 如果写入吞吐量很高，并且压缩没有仔细配置，压缩跟不上写入速率。在这种情况下，磁盘上未合并段的数量不断增加，直到磁盘空间用完，读取速度也会减慢，因为它们需要检查更多段文件。
    • B树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。
• 一个二级索引可以很容易地从一个键值索引构建。主要的不同是键不是唯一的。即可能有许多行（文档，顶点）具有相同的键。这可以通过两种方式来解决：或者通过使索引中的每个值，成为匹配行标识符的列表（如全文索引中的发布列表），或者通过向每个索引添加行标识符来使每个关键字唯一。无论哪种方式，B树和日志结构索引都可以用作辅助索引。

事务处理还是分析？

• 事务不一定具有ACID（原子性，一致性，隔离性和持久性）属性。事务处理只是意味着允许客户端进行低延迟读取和写入——而不是批量处理作业，而这些作业只能定期运行（例如每天一次）。

• 属性	事务处理 OLTP	分析系统 OLAP
  主要读取模式	查询少量记录，按键读取	在大批量记录上聚合
  主要写入模式	随机访问，写入要求低延时	批量导入（ETL），事件流
  主要用户	终端用户，通过Web应用	内部数据分析师，决策支持
  处理的数据	数据的最新状态（当前时间点）	随时间推移的历史事件
  数据集尺寸	GB ~ TB	TB ~ PB

  使用单独的数据仓库，而不是直接查询OLTP系统进行分析的一大优势是数据仓库可针对分析访问模式进行优化。

• 数据仓库包含公司各种OLTP系统中所有的只读数据副本。从OLTP数据库中提取数据（使用定期的数据转储或连续的更新流），转换成适合分析的模式，清理并加载到数据仓库中。将数据存入仓库的过程称为“抽取-转换-加载（ETL）。

• 存储引擎分为两大类：优化事务处理（OLTP）或在线分析（OLAP）

  • OLTP系统通常面向用户，这意味着系统可能会收到大量的请求。为了处理负载，应用程序通常只访问每个查询中的少部分记录。应用程序使用某种键来请求记录，存储引擎使用索引来查找所请求的键的数据。磁盘寻道时间往往是这里的瓶颈。
  • 数据仓库和类似的分析系统会低调一些，因为它们主要由业务分析人员使用，而不是由最终用户使用。它们的查询量要比OLTP系统少得多，但通常每个查询开销高昂，需要在短时间内扫描数百万条记录。磁盘带宽（而不是查找时间）往往是瓶颈，列式存储是这种工作负载越来越流行的解决方案。

• 在OLTP方面，我们能看到两派主流的存储引擎：

  • 日志结构学派
    • 只允许附加到文件和删除过时的文件，但不会更新已经写入的文件。 Bitcask，SSTables，LSM树，LevelDB，Cassandra，HBase，Lucene等都属于这个类别。
  • 就地更新学派
    • 将磁盘视为一组可以覆写的固定大小的页面。 B树是这种哲学的典范，用在所有主要的关系数据库中和许多非关系型数据库。

• 日志结构的存储引擎是相对较新的发展。他们的主要想法是，他们系统地将随机访问写入顺序写入磁盘，由于硬盘驱动器和固态硬盘的性能特点，可以实现更高的写入吞吐量。

第四章、编码与演化

• 新旧版本的代码，以及新旧数据格式可能会在系统中同时共处。系统想要继续顺利运行，就需要保持双向兼容性：
  • ***向后兼容(backward compatibility)***新代码可以读旧数据。
  • ***向前兼容(forward compatibility)***旧代码可以读新数据。
• 向后兼容性通常并不难实现：新代码的作者当然知道由旧代码使用的数据格式，因此可以显示地处理它（最简单的办法是，保留旧代码即可读取旧数据）。
• 向前兼容性可能会更棘手，因为旧版的程序需要忽略新版数据格式中新增的部分。

编码数据的格式

• 程序通常（至少）使用两种形式的数据：
  • 在内存中，数据保存在对象，结构体，列表，数组，哈希表，树等中。这些数据结构针对CPU的高效访问和操作进行了优化（通常使用指针）。
  • 如果要将数据写入文件，或通过网络发送，则必须将其**编码（encode）**为某种自包含的字节序列（例如，JSON文档）。由于每个进程都有自己独立的地址空间，一个进程中的指针对任何其他进程都没有意义，所以这个字节序列表示会与通常在内存中使用的数据结构完全不同^i。
• 需要在两种表示之间进行某种类型的翻译。从内存中表示到字节序列的转换称为编码（Encoding）（也称为序列化（serialization）或编组（marshalling）），反过来称为解码（Decoding）（解析（Parsing），反序列化（deserialization），反编组( unmarshalling）。
• 除非临时使用，采用语言内置编码通常是一个坏主意。
• JSON，XML和CSV属于文本格式，之前存在一些微妙的问题
  • **数值（numbers）**的编码多有歧义之处。XML和CSV不能区分数字和字符串（除非引用一个外部模式）。 JSON虽然区分字符串与数值，但不区分整数和浮点数，而且不能指定精度。
  • 当处理更大的数值时，这个问题显得尤为严重。例如大于$2^{53}$的整数无法使用IEEE 754双精度浮点数精确表示，因此在使用浮点数（例如JavaScript）的语言进行分析时，这些数字会变得不准确。 Twitter有一个关于大于$2^{53}$的数字的例子，它使用64位整数来标识每条推文。 Twitter API返回的JSON包含了两种推特ID，一种是JSON数值，另一种是十进制字符串，以避免JavaScript程序无法正确解析数字的问题
  • JSON和XML对Unicode字符串（即人类可读的文本）有很好的支持，但是它们不支持二进制数据（即不带**字符编码(character encoding)**的字节序列）。
  • XML 和 JSON 都有可选的模式支持。这些模式语言相当强大，所以学习和实现起来都相当复杂。 XML模式的使用相当普遍，但许多基于JSON的工具才不会去折腾模式。
  • CSV没有任何模式，因此每行和每列的含义完全由应用程序自行定义。如果应用程序变更添加了新的行或列，那么这种变更必须通过手工处理。
• 二进制编码：对于仅在组织内部使用的数据，使用最小公约数式的编码格式压力较小。
• Thrift和Protocol Buffers每一个都带有一个代码生成工具，它采用了类似于这里所示的模式定义，并且生成了以各种编程语言实现模式的类。
• Thrift有两种不同的二进制编码格式，分别称为BinaryProtocol和CompactProtocol。
• 在前面所示的模式中，每个字段被标记为必需或可选，但是这对字段如何编码没有任何影响（二进制数据中没有任何字段指示是否需要字段）。所不同的是，如果未设置该字段，则所需的运行时检查将失败，这对于捕获错误非常有用。
• Thrift和Protobuf依赖于代码生成：在定义了模式之后，可以使用您选择的编程语言生成实现此模式的代码。这在Java，C ++或C＃等静态类型语言中很有用，因为它允许将高效的内存中结构用于解码的数据，并且在编写访问数据结构的程序时允许在IDE中进行类型检查和自动完成。
• 在动态类型编程语言（如JavaScript，Ruby或Python）中，生成代码没有太多意义，因为没有编译时类型检查器来满足。代码生成在这些语言中经常被忽视，因为它们避免了明确的编译步骤。而且，对于动态生成的模式（例如从数据库表生成的Avro模式），代码生成对获取数据是一个不必要的障碍。
• 许多数据系统也为其数据实现某种专有的二进制编码。例如，大多数关系数据库都有一个网络协议，您可以通过该协议向数据库发送查询并获取响应。这些协议通常特定于特定的数据库，并且数据库供应商提供将来自数据库的网络协议的响应解码为内存数据结构的驱动程序（例如使用ODBC或JDBC API）。

数据流的类型

• 如何在流程之间流动的一些最常见的方式
  • 通过数据库
  • 通过服务调用
  • 通过异步消息传递
• 在数据库中，写入数据库的过程对数据进行编码，从数据库读取的过程对数据进行解码。可能只有一个进程访问数据库，在这种情况下，读者只是相同进程的后续版本-在这种情况下，您可以考虑将数据库中的内容存储为向未来的自我发送消息。
• 数据库通常允许任何时候更新任何值。这意味着在一个单一的数据库中，可能有一些值是五毫秒前写的，而一些值是五年前写的。
• 面向服务/微服务架构的一个关键设计目标是通过使服务独立部署和演化来使应用程序更易于更改和维护。
• RPC方案的前后向兼容性属性从它使用的编码方式中继承
  • Thrift，gRPC（Protobuf）和Avro RPC可以根据相应编码格式的兼容性规则进行演变。
  • 在SOAP中，请求和响应是使用XML模式指定的。这些可以演变，但有一些微妙的陷阱。
  • RESTful API通常使用JSON（没有正式指定的模式）用于响应，以及用于请求的JSON或URI编码/表单编码的请求参数。添加可选的请求参数并向响应对象添加新的字段通常被认为是保持兼容性的改变。
• 与直接RPC相比，使用消息代理有几个优点：
  • 如果收件人不可用或过载，可以充当缓冲区，从而提高系统的可靠性。
  • 它可以自动将消息重新发送到已经崩溃的进程，从而防止消息丢失。
  • 避免发件人需要知道收件人的IP地址和端口号（这在虚拟机经常出入的云部署中特别有用）。
  • 它允许将一条消息发送给多个收件人。
  • 将发件人与收件人逻辑分离（发件人只是发布邮件，不关心使用者）。
• 与RPC相比，差异在于消息传递通信通常是单向的：发送者通常不期望收到其消息的回复。一个进程可能发送一个响应，但这通常是在一个单独的通道上完成的。这种通信模式是异步的：发送者不会等待消息被传递，而只是发送它，然后忘记它。
• 通常情况下，消息代理的使用方式如下：一个进程将消息发送到指定的队列或主题，代理确保将消息传递给一个或多个消费者或订阅者到那个队列或主题。在同一主题上可以有许多生产者和许多消费者。
• 消息代理通常不会执行任何特定的数据模型-消息只是包含一些元数据的字节序列，因此您可以使用任何编码格式。如果编码是向后兼容的，则您可以灵活地更改发行商和消费者的独立编码，并以任意顺序进行部署。

第五章、复制

• 希望复制原因
  • 使得数据与用户在地理上接近（从而减少延迟）
  • 即使系统的一部分出现故障，系统也能继续工作（从而提高可用性）
  • 伸缩可以接受读请求的机器数量（从而提高读取吞吐量）
• 三种流行的变更复制算法：单领导者（single leader），多领导者（multi leader）**和**无领导者（leaderless）。几乎所有分布式数据库都使用这三种方法之一。

领导者与追随者

• 存储数据库副本的每个节点称为副本（replica）。当存在多个副本时，会不可避免的出现一个问题：如何确保所有数据都落在了所有的副本上？
• 每一次向数据库的写入操作都需要传播到所有副本上，否则副本就会包含不一样的数据。最常见的解决方案被称为基于领导者的复制（leader-based replication）（也称**主动/被动（active/passive）或主/从（master/slave）**复制）
  • 副本之一被指定为领导者（leader），也称为主库（master|primary）。当客户端要向数据库写入时，它必须将请求发送给领导者，领导者会将新数据写入其本地存储。
  • 其他副本被称为追随者（followers），亦称为只读副本（read replicas），从库（slaves），备库（ sencondaries），热备（hot-standby）[^i]。每当领导者将新数据写入本地存储时，它也会将数据变更发送给所有的追随者，称之为复制日志（replication log）**记录或**变更流（change stream）。每个跟随者从领导者拉取日志，并相应更新其本地数据库副本，方法是按照领导者处理的相同顺序应用所有写入。
  • 当客户想要从数据库中读取数据时，它可以向领导者或追随者查询。但只有领导者才能接受写操作（从客户端的角度来看从库都是只读的）。

同步复制与异步复制

• 通常情况下，复制的速度相当快：大多数数据库系统能在一秒向从库应用变更，但它们不能提供复制用时的保证。有些情况下，从库可能落后主库几分钟或更久；例如：从库正在从故障中恢复，系统在最大容量附近运行，或者如果节点间存在网络问题。
• 同步复制的优点是，从库保证有与主库一致的最新数据副本。如果主库突然失效，我们可以确信这些数据仍然能在从库上上找到。缺点是，如果同步从库没有响应（比如它已经崩溃，或者出现网络故障，或其它任何原因），主库就无法处理写入操作。主库必须阻止所有写入，并等待同步副本再次可用。
• 将所有从库都设置为同步的是不切实际的：任何一个节点的中断都会导致整个系统停滞不前。实际上，如果在数据库上启用同步复制，通常意味着其中一个跟随者是同步的，而其他的则是异步的。
• 如果同步从库变得不可用或缓慢，则使一个异步从库同步。这保证你至少在两个节点上拥有最新的数据副本：主库和同步从库。这种配置有时也被称为半同步（semi-synchronous）。
• 通常情况下，基于领导者的复制都配置为完全异步。在这种情况下，如果主库失效且不可恢复，则任何尚未复制给从库的写入都会丢失。这意味着即使已经向客户端确认成功，写入也不能保证持久（Durable）。然而，一个完全异步的配置也有优点：即使所有的从库都落后了，主库也可以继续处理写入。

设置新从库

• 有时候需要设置一个新的从库：也许是为了增加副本的数量，或替换失败的节点。如何确保新的从库拥有主库数据的精确副本？
• 简单地将数据文件从一个节点复制到另一个节点通常是不够的：客户端不断向数据库写入数据，数据总是在不断变化，标准的数据副本会在不同的时间点总是不一样。复制的结果可能没有任何意义。
• 可以通过锁定数据库（使其不可用于写入）来使磁盘上的文件保持一致，但是这会违背高可用的目标。幸运的是，拉起新的从库通常并不需要停机。从概念上讲，过程如下所示：
• 在某个时刻获取主库的一致性快照（如果可能），而不必锁定整个数据库。大多数数据库都具有这个功能，因为它是备份必需的。对于某些场景，可能需要第三方工具，例如MySQL的innobackupex。
• 将快照复制到新的从库节点。
• 从库连接到主库，并拉取快照之后发生的所有数据变更。这要求快照与主库复制日志中的位置精确关联。该位置有不同的名称：例如，PostgreSQL将其称为日志序列号（log sequence number, LSN），MySQL将其称为二进制日志坐标（binlog coordinates）。
• 当从库处理完快照之后积压的数据变更，我们说它**赶上（caught up）**了主库。现在它可以继续处理主库产生的数据变化了。

处理节点宕机

系统中的任何节点都可能宕机，可能因为意外的故障，也可能由于计划内的维护（例如，重启机器以安装内核安全补丁）。对运维而言，能在系统不中断服务的情况下重启单个节点好处多多。我们的目标是，即使个别节点失效，也能保持整个系统运行，并尽可能控制节点停机带来的影响。

如何通过基于主库的复制实现高可用？

从库失效：追赶恢复

在其本地磁盘上，每个从库记录从主库收到的数据变更。如果从库崩溃并重新启动，或者，如果主库和从库之间的网络暂时中断，则比较容易恢复：从库可以从日志中知道，在发生故障之前处理的最后一个事务。因此，从库可以连接到主库，并请求在从库断开连接时发生的所有数据变更。当应用完所有这些变化后，它就赶上了主库，并可以像以前一样继续接收数据变更流。

主库失效：故障切换

主库失效处理起来相当棘手：其中一个从库需要被提升为新的主库，需要重新配置客户端，以将它们的写操作发送给新的主库，其他从库需要开始拉取来自新主库的数据变更。这个过程被称为故障切换（failover）。

故障切换可以手动进行（通知管理员主库挂了，并采取必要的步骤来创建新的主库）或自动进行。自动故障切换过程通常由以下步骤组成：

1. 确认主库失效。有很多事情可能会出错：崩溃，停电，网络问题等等。没有万无一失的方法来检测出现了什么问题，所以大多数系统只是简单使用超时（Timeout）：节点频繁地相互来回传递消息，并且如果一个节点在一段时间内（例如30秒）没有响应，就认为它挂了（因为计划内维护而故意关闭主库不算）。
2. 选择一个新的主库。这可以通过选举过程（主库由剩余副本以多数选举产生）来完成，或者可以由之前选定的控制器节点（controller node）**来指定新的主库。主库的最佳人选通常是拥有旧主库最新数据副本的从库（最小化数据损失）。让所有的节点同意一个新的领导者，是一个**共识问题。
3. 重新配置系统以启用新的主库。客户端现在需要将它们的写请求发送给新主库（将在“请求路由”中讨论这个问题）。如果老领导回来，可能仍然认为自己是主库，没有意识到其他副本已经让它下台了。系统需要确保老领导认可新领导，成为一个从库。

故障切换会出现很多大麻烦：

• 如果使用异步复制，则新主库可能没有收到老主库宕机前最后的写入操作。在选出新主库后，如果老主库重新加入集群，新主库在此期间可能会收到冲突的写入，那这些写入该如何处理？最常见的解决方案是简单丢弃老主库未复制的写入，这很可能打破客户对于数据持久性的期望。

• 如果数据库需要和其他外部存储相协调，那么丢弃写入内容是极其危险的操作。例如在GitHub 【13】的一场事故中，一个过时的MySQL从库被提升为主库。数据库使用自增ID作为主键，因为新主库的计数器落后于老主库的计数器，所以新主库重新分配了一些已经被老主库分配掉的ID作为主键。这些主键也在Redis中使用，主键重用使得MySQL和Redis中数据产生不一致，最后导致一些私有数据泄漏到错误的用户手中。

• 发生某些故障时可能会出现两个节点都以为自己是主库的情况。这种情况称为脑裂(split brain)，非常危险：如果两个主库都可以接受写操作，却没有冲突解决机制（参见“多领导者复制”），那么数据就可能丢失或损坏。一些系统采取了安全防范措施：当检测到两个主库节点同时存在时会关闭其中一个节点[^ii]，但设计粗糙的机制可能最后会导致两个节点都被关闭【14】。

  [^ii]: 这种机制称为屏蔽（fencing），充满感情的术语是：爆彼之头（Shoot The Other Node In The Head, STONITH）。

• 主库被宣告死亡之前的正确超时应该怎么配置？在主库失效的情况下，超时时间越长，意味着恢复时间也越长。但是如果超时设置太短，又可能会出现不必要的故障切换。例如，临时负载峰值可能导致节点的响应时间超时，或网络故障可能导致数据包延迟。如果系统已经处于高负载或网络问题的困扰之中，那么不必要的故障切换可能会让情况变得更糟糕。

这些问题没有简单的解决方案。因此，即使软件支持自动故障切换，不少运维团队还是更愿意手动执行故障切换。

节点故障、不可靠的网络、对副本一致性，持久性，可用性和延迟的权衡，这些问题实际上是分布式系统中的基本问题。第8章和第9章将更深入地讨论它们。

复制日志的实现

基于主库的复制底层是如何工作的？实践中有好几种不同的复制方式，所以先简要地看一下。

基于语句的复制

在最简单的情况下，主库记录下它执行的每个写入请求（语句（statement））并将该语句日志发送给其从库。对于关系数据库来说，这意味着每个INSERT，UPDATE或DELETE语句都被转发给每个从库，每个从库解析并执行该SQL语句，就像从客户端收到一样。

虽然听上去很合理，但有很多问题会搞砸这种复制方式：

• 任何调用**非确定性函数（nondeterministic）**的语句，可能会在每个副本上生成不同的值。例如，使用NOW()获取当前日期时间，或使用RAND()获取一个随机数。
• 如果语句使用了自增列（auto increment），或者依赖于数据库中的现有数据（例如，UPDATE ... WHERE <某些条件>），则必须在每个副本上按照完全相同的顺序执行它们，否则可能会产生不同的效果。当有多个并发执行的事务时，这可能成为一个限制。
• 有副作用的语句（例如，触发器，存储过程，用户定义的函数）可能会在每个副本上产生不同的副作用，除非副作用是绝对确定的。

的确有办法绕开这些问题——例如，当语句被记录时，主库可以用固定的返回值替换任何不确定的函数调用，以便从库获得相同的值。但是由于边缘情况实在太多了，现在通常会选择其他的复制方法。

基于语句的复制在5.1版本前的MySQL中使用。因为它相当紧凑，现在有时候也还在用。但现在在默认情况下，如果语句中存在任何不确定性，MySQL会切换到基于行的复制（稍后讨论）。 VoltDB使用了基于语句的复制，但要求事务必须是确定性的，以此来保证安全【15】。

传输预写式日志（WAL）

在第3章中，我们讨论了存储引擎如何在磁盘上表示数据，并且我们发现，通常写操作都是追加到日志中：

• 对于日志结构存储引擎（请参阅“SSTables和LSM树”），日志是主要的存储位置。日志段在后台压缩，并进行垃圾回收。
• 对于覆写单个磁盘块的B树，每次修改都会先写入预写式日志（Write Ahead Log, WAL），以便崩溃后索引可以恢复到一个一致的状态。

在任何一种情况下，日志都是包含所有数据库写入的仅追加字节序列。可以使用完全相同的日志在另一个节点上构建副本：除了将日志写入磁盘之外，主库还可以通过网络将其发送给其从库。

当从库应用这个日志时，它会建立和主库一模一样数据结构的副本。

PostgreSQL和Oracle等使用这种复制方法【16】。主要缺点是日志记录的数据非常底层：WAL包含哪些磁盘块中的哪些字节发生了更改。这使复制与存储引擎紧密耦合。如果数据库将其存储格式从一个版本更改为另一个版本，通常不可能在主库和从库上运行不同版本的数据库软件。

看上去这可能只是一个微小的实现细节，但却可能对运维产生巨大的影响。如果复制协议允许从库使用比主库更新的软件版本，则可以先升级从库，然后执行故障切换，使升级后的节点之一成为新的主库，从而执行数据库软件的零停机升级。如果复制协议不允许版本不匹配（传输WAL经常出现这种情况），则此类升级需要停机。

逻辑日志复制（基于行）

另一种方法是，复制和存储引擎使用不同的日志格式，这样可以使复制日志从存储引擎内部分离出来。这种复制日志被称为逻辑日志，以将其与存储引擎的（物理）数据表示区分开来。

关系数据库的逻辑日志通常是以行的粒度描述对数据库表的写入的记录序列：

• 对于插入的行，日志包含所有列的新值。
• 对于删除的行，日志包含足够的信息来唯一标识已删除的行。通常是主键，但是如果表上没有主键，则需要记录所有列的旧值。
• 对于更新的行，日志包含足够的信息来唯一标识更新的行，以及所有列的新值（或至少所有已更改的列的新值）。

修改多行的事务会生成多个这样的日志记录，后面跟着一条记录，指出事务已经提交。 MySQL的二进制日志（当配置为使用基于行的复制时）使用这种方法【17】。

由于逻辑日志与存储引擎内部分离，因此可以更容易地保持向后兼容，从而使领导者和跟随者能够运行不同版本的数据库软件甚至不同的存储引擎。

对于外部应用程序来说，逻辑日志格式也更容易解析。如果要将数据库的内容发送到外部系统（如数据），这一点很有用，例如复制到数据仓库进行离线分析，或建立自定义索引和缓存【18】。这种技术被称为数据变更捕获（change data capture），第11章将重新讲到它。

基于触发器的复制

到目前为止描述的复制方法是由数据库系统实现的，不涉及任何应用程序代码。在很多情况下，这就是你想要的。但在某些情况下需要更多的灵活性。例如，如果您只想复制数据的一个子集，或者想从一种数据库复制到另一种数据库，或者如果您需要冲突解决逻辑（参阅“处理写入冲突”），则可能需要将复制移动到应用程序层。

一些工具，如Oracle Golden Gate 【19】，可以通过读取数据库日志，使得其他应用程序可以使用数据。另一种方法是使用许多关系数据库自带的功能：触发器和存储过程。

触发器允许您注册在数据库系统中发生数据更改（写入事务）时自动执行的自定义应用程序代码。触发器有机会将更改记录到一个单独的表中，使用外部程序读取这个表，再加上任何业务逻辑处理，会后将数据变更复制到另一个系统去。例如，Databus for Oracle 【20】和Bucardo for Postgres 【21】就是这样工作的。

基于触发器的复制通常比其他复制方法具有更高的开销，并且比数据库的内置复制更容易出错，也有很多限制。然而由于其灵活性，仍然是很有用的。

复制延迟问题

容忍节点故障只是需要复制的一个原因。正如在第二部分的介绍中提到的，另一个原因是可伸缩性（处理比单个机器更多的请求）和延迟（让副本在地理位置上更接近用户）。

基于主库的复制要求所有写入都由单个节点处理，但只读查询可以由任何副本处理。所以对于读多写少的场景（Web上的常见模式），一个有吸引力的选择是创建很多从库，并将读请求分散到所有的从库上去。这样能减小主库的负载，并允许向最近的副本发送读请求。

在这种伸缩体系结构中，只需添加更多的追随者，就可以提高只读请求的服务容量。但是，这种方法实际上只适用于异步复制——如果尝试同步复制到所有追随者，则单个节点故障或网络中断将使整个系统无法写入。而且越多的节点越有可能会被关闭，所以完全同步的配置是非常不可靠的。

不幸的是，当应用程序从异步从库读取时，如果从库落后，它可能会看到过时的信息。这会导致数据库中出现明显的不一致：同时对主库和从库执行相同的查询，可能得到不同的结果，因为并非所有的写入都反映在从库中。这种不一致只是一个暂时的状态——如果停止写入数据库并等待一段时间，从库最终会赶上并与主库保持一致。出于这个原因，这种效应被称为最终一致性（eventually consistency）[^iii]【22,23】

[^iii]: 道格拉斯·特里（Douglas Terry）等人创造了术语最终一致性。【24】并经由Werner Vogels 【22】推广，成为许多NoSQL项目的战吼。然而，不只有NoSQL数据库是最终一致的：关系型数据库中的异步复制追随者也有相同的特性。

“最终”一词故意含糊不清：总的来说，副本落后的程度是没有限制的。在正常的操作中，复制延迟（replication lag），即写入主库到反映至从库之间的延迟，可能仅仅是几分之一秒，在实践中并不显眼。但如果系统在接近极限的情况下运行，或网络中存在问题，延迟可以轻而易举地超过几秒，甚至几分钟。

因为滞后时间太长引入的不一致性，可不仅是一个理论问题，更是应用设计中会遇到的真实问题。本节将重点介绍三个由复制延迟问题的例子，并简述解决这些问题的一些方法。

读己之写

许多应用让用户提交一些数据，然后查看他们提交的内容。可能是用户数据库中的记录，也可能是对讨论主题的评论，或其他类似的内容。提交新数据时，必须将其发送给领导者，但是当用户查看数据时，可以从追随者读取。如果数据经常被查看，但只是偶尔写入，这是非常合适的。

但对于异步复制，问题就来了。如图5-3所示：如果用户在写入后马上就查看数据，则新数据可能尚未到达副本。对用户而言，看起来好像是刚提交的数据丢失了，用户会不高兴，可以理解。

图5-3 用户写入后从旧副本中读取数据。需要写后读(read-after-write)的一致性来防止这种异常

在这种情况下，我们需要读写一致性（read-after-write consistency），也称为读己之写一致性（read-your-writes consistency）【24】。这是一个保证，如果用户重新加载页面，他们总会看到他们自己提交的任何更新。它不会对其他用户的写入做出承诺：其他用户的更新可能稍等才会看到。它保证用户自己的输入已被正确保存。

如何在基于领导者的复制系统中实现读后一致性？有各种可能的技术，这里说一些：

• 读用户可能已经修改过的内容时，都从主库读；这就要求有一些方法，不用实际查询就可以知道用户是否修改了某些东西。举个例子，社交网络上的用户个人资料信息通常只能由用户本人编辑，而不能由其他人编辑。因此一个简单的规则是：从主库读取用户自己的档案，在从库读取其他用户的档案。

• 如果应用中的大部分内容都可能被用户编辑，那这种方法就没用了，因为大部分内容都必须从主库读取（扩容读就没效果了）。在这种情况下可以使用其他标准来决定是否从主库读取。例如可以跟踪上次更新的时间，在上次更新后的一分钟内，从主库读。还可以监控从库的复制延迟，防止对任意比主库滞后超过一分钟的从库发出查询。

• 客户端可以记住最近一次写入的时间戳，系统需要确保从库为该用户提供任何查询时，该时间戳前的变更都已经传播到了本从库中。如果当前从库不够新，则可以从另一个从库读，或者等待从库追赶上来。

  时间戳可以是逻辑时间戳（指示写入顺序的东西，例如日志序列号）或实际系统时钟（在这种情况下，时钟同步变得至关重要；参阅“不可靠的时钟”）。

• 如果您的副本分布在多个数据中心（出于可用性目的与用户尽量在地理上接近），则会增加复杂性。任何需要由领导者提供服务的请求都必须路由到包含主库的数据中心。

另一种复杂的情况是：如果同一个用户从多个设备请求服务，例如桌面浏览器和移动APP。这种情况下可能就需要提供跨设备的写后读一致性：如果用户在某个设备上输入了一些信息，然后在另一个设备上查看，则应该看到他们刚输入的信息。

在这种情况下，还有一些需要考虑的问题：

• 记住用户上次更新时间戳的方法变得更加困难，因为一台设备上运行的程序不知道另一台设备上发生了什么。元数据需要一个中心存储。
• 如果副本分布在不同的数据中心，很难保证来自不同设备的连接会路由到同一数据中心。（例如，用户的台式计算机使用家庭宽带连接，而移动设备使用蜂窝数据网络，则设备的网络路线可能完全不同）。如果你的方法需要读主库，可能首先需要把来自同一用户的请求路由到同一个数据中心。

单调读

从异步从库读取第二个异常例子是，用户可能会遇到时光倒流（moving backward in time）。

如果用户从不同从库进行多次读取，就可能发生这种情况。例如，图5-4显示了用户2345两次进行相同的查询，首先查询了一个延迟很小的从库，然后是一个延迟较大的从库。（如果用户刷新网页，而每个请求被路由到一个随机的服务器，这种情况是很有可能的。）第一个查询返回最近由用户1234添加的评论，但是第二个查询不返回任何东西，因为滞后的从库还没有拉取写入内容。在效果上相比第一个查询，第二个查询是在更早的时间点来观察系统。如果第一个查询没有返回任何内容，那问题并不大，因为用户2345可能不知道用户1234最近添加了评论。但如果用户2345先看见用户1234的评论，然后又看到它消失，那么对于用户2345，就很让人头大了。

图5-4 用户首先从新副本读取，然后从旧副本读取。时光倒流。为了防止这种异常，我们需要单调的读取。

单调读（Monotonic reads）【23】是这种异常不会发生的保证。这是一个比**强一致性（strong consistency）更弱，但比最终一致性（eventually consistency）**更强的保证。当读取数据时，您可能会看到一个旧值；单调读取仅意味着如果一个用户顺序地进行多次读取，则他们不会看到时间后退，即，如果先前读取到较新的数据，后续读取不会得到更旧的数据。

实现单调读取的一种方式是确保每个用户总是从同一个副本进行读取（不同的用户可以从不同的副本读取）。例如，可以基于用户ID的散列来选择副本，而不是随机选择副本。但是，如果该副本失败，用户的查询将需要重新路由到另一个副本。

一致前缀读

第三个复制延迟例子违反了因果律。想象一下Poons先生和Cake夫人之间的以下简短对话：

Mr. Poons Mrs. Cake，你能看到多远的未来？

Mrs. Cake通常约十秒钟，Mr. Poons.

这两句话之间有因果关系：Cake夫人听到了Poons先生的问题并回答了这个问题。

现在，想象第三个人正在通过从库来听这个对话。 Cake夫人说的内容是从一个延迟很低的从库读取的，但Poons先生所说的内容，从库的延迟要大的多（见图5-5）。于是，这个观察者会听到以下内容：

Mrs. Cake通常约十秒钟，Mr. Poons.

Mr. Poons Mrs. Cake，你能看到多远的未来？

对于观察者来说，看起来好像Cake夫人在Poons先生发问前就回答了这个问题。这种超能力让人印象深刻，但也会把人搞糊涂。【25】。

图5-5 如果某些分区的复制速度慢于其他分区，那么观察者在看到问题之前可能会看到答案。

防止这种异常，需要另一种类型的保证：一致前缀读（consistent prefix reads）【23】。这个保证说：如果一系列写入按某个顺序发生，那么任何人读取这些写入时，也会看见它们以同样的顺序出现。

这是分区（partitioned）（分片（sharded））数据库中的一个特殊问题，将在第6章中讨论。如果数据库总是以相同的顺序应用写入，则读取总是会看到一致的前缀，所以这种异常不会发生。但是在许多分布式数据库中，不同的分区独立运行，因此不存在全局写入顺序：当用户从数据库中读取数据时，可能会看到数据库的某些部分处于较旧的状态，而某些处于较新的状态。

一种解决方案是，确保任何因果相关的写入都写入相同的分区。对于某些无法高效完成这种操作的应用，还有一些显式跟踪因果依赖关系的算法，本书将在“关系与并发”一节中返回这个主题。

复制延迟的解决方案

在使用最终一致的系统时，如果复制延迟增加到几分钟甚至几小时，则应该考虑应用程序的行为。如果答案是“没问题”，那很好。但如果结果对于用户来说是不好体验，那么设计系统来提供更强的保证是很重要的，例如写后读。明明是异步复制却假设复制是同步的，这是很多麻烦的根源。

如前所述，应用程序可以提供比底层数据库更强有力的保证，例如通过主库进行某种读取。但在应用程序代码中处理这些问题是复杂的，容易出错。

如果应用程序开发人员不必担心微妙的复制问题，并可以信赖他们的数据库“做了正确的事情”，那该多好呀。这就是**事务（transaction）**存在的原因：数据库通过事务提供强大的保证，所以应用程序可以更加简单。

单节点事务已经存在了很长时间。然而在走向分布式（复制和分区）数据库时，许多系统放弃了事务。声称事务在性能和可用性上的代价太高，并断言在可伸缩系统中最终一致性是不可避免的。这个叙述有一些道理，但过于简单了，本书其余部分将提出更为细致的观点。第七章和第九章将回到事务的话题，并讨论一些替代机制。

多主复制

本章到目前为止，我们只考虑使用单个领导者的复制架构。虽然这是一种常见的方法，但也有一些有趣的选择。

基于领导者的复制有一个主要的缺点：只有一个主库，而所有的写入都必须通过它。如果出于任何原因（例如和主库之间的网络连接中断）无法连接到主库，就无法向数据库写入。

基于领导者的复制模型的自然延伸是允许多个节点接受写入。复制仍然以同样的方式发生：处理写入的每个节点都必须将该数据更改转发给所有其他节点。称之为多领导者配置（也称多主、多活复制）。在这种情况下，每个领导者同时扮演其他领导者的追随者。

多主复制的应用场景

在单个数据中心内部使用多个主库很少是有意义的，因为好处很少超过复杂性的代价。但在一些情况下，多活配置是也合理的。

运维多个数据中心

假如你有一个数据库，副本分散在好几个不同的数据中心（也许这样可以容忍单个数据中心的故障，或地理上更接近用户）。使用常规的基于领导者的复制设置，主库必须位于其中一个数据中心，且所有写入都必须经过该数据中心。

多领导者配置中可以在每个数据中心都有主库。图5-6展示了这个架构的样子。在每个数据中心内使用常规的主从复制；在数据中心之间，每个数据中心的主库都会将其更改复制到其他数据中心的主库中。

图5-6 跨多个数据中心的多主复制

我们来比较一下在运维多个数据中心时，单主和多主的适应情况。

性能

在单活配置中，每个写入都必须穿过互联网，进入主库所在的数据中心。这可能会增加写入时间，并可能违背了设置多个数据中心的初心。在多活配置中，每个写操作都可以在本地数据中心进行处理，并与其他数据中心异步复制。因此，数据中心之间的网络延迟对用户来说是透明的，这意味着感觉到的性能可能会更好。

容忍数据中心停机

在单主配置中，如果主库所在的数据中心发生故障，故障切换可以使另一个数据中心里的追随者成为领导者。在多活配置中，每个数据中心可以独立于其他数据中心继续运行，并且当发生故障的数据中心归队时，复制会自动赶上。

容忍网络问题

数据中心之间的通信通常穿过公共互联网，这可能不如数据中心内的本地网络可靠。单主配置对这数据中心间的连接问题非常敏感，因为通过这个连接进行的写操作是同步的。采用异步复制功能的多活配置通常能更好地承受网络问题：临时的网络中断并不会妨碍正在处理的写入。

有些数据库默认情况下支持多主配置，但使用外部工具实现也很常见，例如用于MySQL的Tungsten Replicator 【26】，用于PostgreSQL的BDR【27】以及用于Oracle的GoldenGate 【19】。

尽管多主复制有这些优势，但也有一个很大的缺点：两个不同的数据中心可能会同时修改相同的数据，写冲突是必须解决的（如图5-6中“冲突解决”）。本书将在“处理写入冲突”中详细讨论这个问题。

由于多主复制在许多数据库中都属于改装的功能，所以常常存在微妙的配置缺陷，且经常与其他数据库功能之间出现意外的反应。例如自增主键、触发器、完整性约束等，都可能会有麻烦。因此，多主复制往往被认为是危险的领域，应尽可能避免【28】。

需要离线操作的客户端

多主复制的另一种适用场景是：应用程序在断网之后仍然需要继续工作。

例如，考虑手机，笔记本电脑和其他设备上的日历应用。无论设备目前是否有互联网连接，你需要能随时查看你的会议（发出读取请求），输入新的会议（发出写入请求）。如果在离线状态下进行任何更改，则设备下次上线时，需要与服务器和其他设备同步。

在这种情况下，每个设备都有一个充当领导者的本地数据库（它接受写请求），并且在所有设备上的日历副本之间同步时，存在异步的多主复制过程。复制延迟可能是几小时甚至几天，具体取决于何时可以访问互联网。

从架构的角度来看，这种设置实际上与数据中心之间的多领导者复制类似，每个设备都是一个“数据中心”，而它们之间的网络连接是极度不可靠的。从历史上各类日历同步功能的破烂实现可以看出，想把多活配好是多么困难的一件事。

有一些工具旨在使这种多领导者配置更容易。例如，CouchDB就是为这种操作模式而设计的【29】。

协同编辑

实时协作编辑应用程序允许多个人同时编辑文档。例如，Etherpad 【30】和Google Docs 【31】允许多人同时编辑文本文档或电子表格（该算法在“自动冲突解决”中简要讨论）。我们通常不会将协作式编辑视为数据库复制问题，但与前面提到的离线编辑用例有许多相似之处。当一个用户编辑文档时，所做的更改将立即应用到其本地副本（Web浏览器或客户端应用程序中的文档状态），并异步复制到服务器和编辑同一文档的任何其他用户。

如果要保证不会发生编辑冲突，则应用程序必须先取得文档的锁定，然后用户才能对其进行编辑。如果另一个用户想要编辑同一个文档，他们首先必须等到第一个用户提交修改并释放锁定。这种协作模式相当于在领导者上进行交易的单领导者复制。

但是，为了加速协作，您可能希望将更改的单位设置得非常小（例如，一个按键），并避免锁定。这种方法允许多个用户同时进行编辑，但同时也带来了多领导者复制的所有挑战，包括需要解决冲突【32】。

处理写入冲突

多领导者复制的最大问题是可能发生写冲突，这意味着需要解决冲突。

例如，考虑一个由两个用户同时编辑的维基页面，如图5-7所示。用户1将页面的标题从A更改为B，并且用户2同时将标题从A更改为C。每个用户的更改已成功应用到其本地主库。但当异步复制时，会发现冲突【33】。单主数据库中不会出现此问题。

图5-7 两个主库同时更新同一记录引起的写入冲突

同步与异步冲突检测

在单主数据库中，第二个写入将被阻塞，并等待第一个写入完成，或中止第二个写入事务，强制用户重试。另一方面，在多活配置中，两个写入都是成功的，并且在稍后的时间点仅仅异步地检测到冲突。那时要求用户解决冲突可能为时已晚。

原则上，可以使冲突检测同步-即等待写入被复制到所有副本，然后再告诉用户写入成功。但是，通过这样做，您将失去多主复制的主要优点：允许每个副本独立接受写入。如果您想要同步冲突检测，那么您可以使用单主程序复制。

避免冲突

处理冲突的最简单的策略就是避免它们：如果应用程序可以确保特定记录的所有写入都通过同一个领导者，那么冲突就不会发生。由于多领导者复制处理的许多实现冲突相当不好，避免冲突是一个经常推荐的方法【34】。

例如，在用户可以编辑自己的数据的应用程序中，可以确保来自特定用户的请求始终路由到同一数据中心，并使用该数据中心的领导者进行读写。不同的用户可能有不同的“家庭”数据中心（可能根据用户的地理位置选择），但从任何用户的角度来看，配置基本上都是单一的领导者。

但是，有时您可能需要更改指定的记录的主库——可能是因为一个数据中心出现故障，您需要将流量重新路由到另一个数据中心，或者可能是因为用户已经迁移到另一个位置，现在更接近不同的数据中心。在这种情况下，冲突避免会中断，你必须处理不同主库同时写入的可能性。

收敛至一致的状态

单主数据库按顺序进行写操作：如果同一个字段有多个更新，则最后一个写操作将决定该字段的最终值。

在多主配置中，没有明确的写入顺序，所以最终值应该是什么并不清楚。在图5-7中，在主库1中标题首先更新为B而后更新为C；在主库2中，首先更新为C，然后更新为B。两个顺序都不是“更正确”的。

如果每个副本只是按照它看到写入的顺序写入，那么数据库最终将处于不一致的状态：最终值将是在主库1的C和主库2的B。这是不可接受的，每个复制方案都必须确保数据在所有副本中最终都是相同的。因此，数据库必须以一种**收敛（convergent）**的方式解决冲突，这意味着所有副本必须在所有变更复制完成时收敛至一个相同的最终值。

实现冲突合并解决有多种途径：

• 给每个写入一个唯一的ID（例如，一个时间戳，一个长的随机数，一个UUID或者一个键和值的哈希），挑选最高ID的写入作为胜利者，并丢弃其他写入。如果使用时间戳，这种技术被称为最后写入胜利（LWW, last write wins）。虽然这种方法很流行，但是很容易造成数据丢失【35】。我们将在本章末尾更详细地讨论LWW。
• 为每个副本分配一个唯一的ID，ID编号更高的写入具有更高的优先级。这种方法也意味着数据丢失。
• 以某种方式将这些值合并在一起-例如，按字母顺序排序，然后连接它们（在图5-7中，合并的标题可能类似于“B/C”）。
• 用一种可保留所有信息的显式数据结构来记录冲突，并编写解决冲突的应用程序代码（也许通过提示用户的方式）。

自定义冲突解决逻辑

作为解决冲突最合适的方法可能取决于应用程序，大多数多主复制工具允许使用应用程序代码编写冲突解决逻辑。该代码可以在写入或读取时执行：

写时执行

只要数据库系统检测到复制更改日志中存在冲突，就会调用冲突处理程序。例如，Bucardo允许您为此编写一段Perl代码。这个处理程序通常不能提示用户——它在后台进程中运行，并且必须快速执行。

读时执行

当检测到冲突时，所有冲突写入被存储。下一次读取数据时，会将这些多个版本的数据返回给应用程序。应用程序可能会提示用户或自动解决冲突，并将结果写回数据库。例如，CouchDB以这种方式工作。

请注意，冲突解决通常适用于单个行或文档层面，而不是整个事务【36】。因此，如果您有一个事务会原子性地进行几次不同的写入（请参阅第7章），则对于冲突解决而言，每个写入仍需分开单独考虑。

题外话：自动冲突解决

冲突解决规则可能很快变得复杂，并且自定义代码可能容易出错。亚马逊是一个经常被引用的例子，由于冲突解决处理程序令人意外的效果：一段时间以来，购物车上的冲突解决逻辑将保留添加到购物车的物品，但不包括从购物车中移除的物品。因此，顾客有时会看到物品重新出现在他们的购物车中，即使他们之前已经被移走【37】。

已经有一些有趣的研究来自动解决由于数据修改引起的冲突。有几行研究值得一提：

• 无冲突复制数据类型（Conflict-free replicated datatypes）（CRDT）【32,38】是可以由多个用户同时编辑的集合，映射，有序列表，计数器等的一系列数据结构，它们以合理的方式自动解决冲突。一些CRDT已经在Riak 2.0中实现【39,40】。
• 可合并的持久数据结构（Mergeable persistent data structures）【41】显式跟踪历史记录，类似于Git版本控制系统，并使用三向合并功能（而CRDT使用双向合并）。
• 可执行的转换（operational transformation）[42]是Etherpad 【30】和Google Docs 【31】等合作编辑应用背后的冲突解决算法。它是专为同时编辑项目的有序列表而设计的，例如构成文本文档的字符列表。

这些算法在数据库中的实现还很年轻，但很可能将来它们将被集成到更多的复制数据系统中。自动冲突解决方案可以使应用程序处理多领导者数据同步更为简单。

什么是冲突？

有些冲突是显而易见的。在图5-7的例子中，两个写操作并发地修改了同一条记录中的同一个字段，并将其设置为两个不同的值。毫无疑问这是一个冲突。

其他类型的冲突可能更为微妙，难以发现。例如，考虑一个会议室预订系统：它记录谁订了哪个时间段的哪个房间。应用需要确保每个房间只有一组人同时预定（即不得有相同房间的重叠预订）。在这种情况下，如果同时为同一个房间创建两个不同的预订，则可能会发生冲突。即使应用程序在允许用户进行预订之前检查可用性，如果两次预订是由两个不同的领导者进行的，则可能会有冲突。

现在还没有一个现成的答案，但在接下来的章节中，我们将更好地了解这个问题。我们将在第7章中看到更多的冲突示例，在第12章中我们将讨论用于检测和解决复制系统中冲突的可伸缩方法。

多主复制拓扑

复制拓扑（replication topology）描述写入从一个节点传播到另一个节点的通信路径。如果你有两个领导者，如图5-7所示，只有一个合理的拓扑结构：领导者1必须把他所有的写到领导者2，反之亦然。当有两个以上的领导，各种不同的拓扑是可能的。图5-8举例说明了一些例子。

图5-8 三个可以设置多领导者复制的示例拓扑。

最普遍的拓扑是全部到全部（[图5-8 c]），其中每个领导者将其写入每个其他领导。但是，也会使用更多受限制的拓扑：例如，默认情况下，MySQL仅支持环形拓扑（circular topology）【34】，其中每个节点接收来自一个节点的写入，并将这些写入（加上自己的任何写入）转发给另一个节点。另一种流行的拓扑结构具有星形的形状^v。个指定的根节点将写入转发给所有其他节点。星型拓扑可以推广到树。

在圆形和星形拓扑中，写入可能需要在到达所有副本之前通过多个节点。因此，节点需要转发从其他节点收到的数据更改。为了防止无限复制循环，每个节点被赋予一个唯一的标识符，并且在复制日志中，每个写入都被标记了所有已经过的节点的标识符【43】。当一个节点收到用自己的标识符标记的数据更改时，该数据更改将被忽略，因为节点知道它已经被处理过。

循环和星型拓扑的问题是，如果只有一个节点发生故障，则可能会中断其他节点之间的复制消息流，导致它们无法通信，直到节点修复。拓扑结构可以重新配置为在发生故障的节点上工作，但在大多数部署中，这种重新配置必须手动完成。更密集连接的拓扑结构（例如全部到全部）的容错性更好，因为它允许消息沿着不同的路径传播，避免单点故障。

另一方面，全部到全部的拓扑也可能有问题。特别是，一些网络链接可能比其他网络链接更快（例如，由于网络拥塞），结果是一些复制消息可能“超过”其他复制消息，如图5-9所示。

图5-9 使用多主程序复制时，可能会在某些副本中写入错误的顺序。

在图5-9中，客户端A向主库1的表中插入一行，客户端B在主库3上更新该行。然而，主库2可以以不同的顺序接收写入：它可以首先接收更新（其中，从它的角度来看，是对数据库中不存在的行的更新），并且仅在稍后接收到相应的插入（其应该在更新之前）。

这是一个因果关系的问题，类似于我们在“一致前缀读”中看到的：更新取决于先前的插入，所以我们需要确保所有节点先处理插入，然后再处理更新。仅仅在每一次写入时添加一个时间戳是不够的，因为时钟不可能被充分地同步，以便在主库2处正确地排序这些事件（见第8章）。

要正确排序这些事件，可以使用一种称为**版本向量（version vectors）**的技术，本章稍后将讨论这种技术（参阅“检测并发写入”）。然而，冲突检测技术在许多多领导者复制系统中执行得不好。例如，在撰写本文时，PostgreSQL BDR不提供写入的因果排序【27】，而Tungsten Replicator for MySQL甚至不尝试检测冲突【34】。

如果您正在使用具有多领导者复制功能的系统，那么应该了解这些问题，仔细阅读文档，并彻底测试您的数据库，以确保它确实提供了您认为具有的保证。

无主复制

我们在本章到目前为止所讨论的复制方法——单主复制、多主复制——都是这样的想法：客户端向一个主库发送写请求，而数据库系统负责将写入复制到其他副本。主库决定写入的顺序，而从库按相同顺序应用主库的写入。

一些数据存储系统采用不同的方法，放弃主库的概念，并允许任何副本直接接受来自客户端的写入。最早的一些的复制数据系统是无领导的（leaderless）【1,44】，但是在关系数据库主导的时代，这个想法几乎已被忘却。在亚马逊将其用于其内部的Dynamo系统^vi之后，它再一次成为数据库的一种时尚架构【37】。 Riak，Cassandra和Voldemort是由Dynamo启发的无领导复制模型的开源数据存储，所以这类数据库也被称为Dynamo风格。

在一些无领导者的实现中，客户端直接将写入发送到到几个副本中，而另一些情况下，一个**协调者（coordinator）**节点代表客户端进行写入。但与主库数据库不同，协调者不执行特定的写入顺序。我们将会看到，这种设计上的差异对数据库的使用方式有着深远的影响。

当节点故障时写入数据库

假设你有一个带有三个副本的数据库，而其中一个副本目前不可用，或许正在重新启动以安装系统更新。在基于主机的配置中，如果要继续处理写入，则可能需要执行故障切换（参阅「处理节点宕机」）。

另一方面，在无领导配置中，故障切换不存在。图5-10显示了发生了什么事情：客户端（用户1234）并行发送写入到所有三个副本，并且两个可用副本接受写入，但是不可用副本错过了它。假设三个副本中的两个承认写入是足够的：在用户1234已经收到两个确定的响应之后，我们认为写入成功。客户简单地忽略了其中一个副本错过了写入的事实。

图5-10 法定写入，法定读取，并在节点中断后读修复。

现在想象一下，不可用的节点重新联机，客户端开始读取它。节点关闭时发生的任何写入都从该节点丢失。因此，如果您从该节点读取数据，则可能会将陈旧（过时）值视为响应。

为了解决这个问题，当一个客户端从数据库中读取数据时，它不仅仅发送它的请求到一个副本：读请求也被并行地发送到多个节点。客户可能会从不同的节点获得不同的响应。即来自一个节点的最新值和来自另一个节点的陈旧值。版本号用于确定哪个值更新（参阅“检测并发写入”）。

读修复和反熵

复制方案应确保最终将所有数据复制到每个副本。在一个不可用的节点重新联机之后，它如何赶上它错过的写入？

在Dynamo风格的数据存储中经常使用两种机制：

读修复（Read repair）

当客户端并行读取多个节点时，它可以检测到任何陈旧的响应。例如，在图5-10中，用户2345获得了来自副本3的版本6值和来自副本1和2的版本7值。客户端发现副本3具有陈旧值，并将新值写回到该副本。这种方法适用于读频繁的值。

反熵过程（Anti-entropy process）

此外，一些数据存储具有后台进程，该进程不断查找副本之间的数据差异，并将任何缺少的数据从一个副本复制到另一个副本。与基于领导者的复制中的复制日志不同，此反熵过程不会以任何特定的顺序复制写入，并且在复制数据之前可能会有显著的延迟。

并不是所有的系统都实现了这两个，例如，Voldemort目前没有反熵过程。请注意，如果没有反熵过程，某些副本中很少读取的值可能会丢失，从而降低了持久性，因为只有在应用程序读取值时才执行读修复。

读写的法定人数

在图5-10的示例中，我们认为即使仅在三个副本中的两个上进行处理，写入仍然是成功的。如果三个副本中只有一个接受了写入，会怎样？我们能推多远呢？

如果我们知道，每个成功的写操作意味着在三个副本中至少有两个出现，这意味着至多有一个副本可能是陈旧的。因此，如果我们从至少两个副本读取，我们可以确定至少有一个是最新的。如果第三个副本停机或响应速度缓慢，则读取仍可以继续返回最新值。

更一般地说，如果有n个副本，每个写入必须由w节点确认才能被认为是成功的，并且我们必须至少为每个读取查询r个节点。（在我们的例子中，$n = 3，w = 2，r = 2$）。只要$w + r> n$，我们期望在读取时获得最新的值，因为r个读取中至少有一个节点是最新的。遵循这些r值，w值的读写称为法定人数（quorum）^vii的读和写【44】。你可以认为，r和w是有效读写所需的最低票数。

在Dynamo风格的数据库中，参数n，w和r通常是可配置的。一个常见的选择是使n为奇数（通常为3或5）并设置$w = r =（n +1）/2$（向上取整）。但是可以根据需要更改数字。例如，设置$w = n$和$r = 1$的写入很少且读取次数较多的工作负载可能会受益。这使得读取速度更快，但具有只有一个失败节点导致所有数据库写入失败的缺点。

集群中可能有多于n的节点。（集群的机器数可能多于副本数目），但是任何给定的值只能存储在n个节点上。这允许对数据集进行分区，从而支持可以放在一个节点上的数据集更大的数据集。将在第6章回到分区。

法定人数条件$w + r> n$允许系统容忍不可用的节点，如下所示：

• 如果$w <n$，如果节点不可用，我们仍然可以处理写入。
• 如果$r <n$，如果节点不可用，我们仍然可以处理读取。
• 对于$n = 3，w = 2，r = 2$，我们可以容忍一个不可用的节点。
• 对于$n = 5，w = 3，r = 3$，我们可以容忍两个不可用的节点。这个案例如图5-11所示。
• 通常，读取和写入操作始终并行发送到所有n个副本。参数w和r决定我们等待多少个节点，即在我们认为读或写成功之前，有多少个节点需要报告成功。

图5-11 如果$w + r > n$，读取r个副本，至少有一个r副本必然包含了最近的成功写入

如果少于所需的w或r节点可用，则写入或读取将返回错误。由于许多原因，节点可能不可用：因为由于执行操作的错误（由于磁盘已满而无法写入）导致节点关闭（崩溃，关闭电源），由于客户端和服务器之间的网络中断节点，或任何其他原因。我们只关心节点是否返回了成功的响应，而不需要区分不同类型的错误。

法定人数一致性的局限性

如果你有n个副本，并且你选择w和r，使得$w + r> n$，你通常可以期望每个读取返回为一个键写的最近的值。情况就是这样，因为你写的节点集合和你读过的节点集合必须重叠。也就是说，您读取的节点中必须至少有一个具有最新值的节点（如图5-11所示）。

通常，r和w被选为多数（超过$n/2$）节点，因为这确保了$w + r> n$，同时仍然容忍多达$n/2$个节点故障。但是，法定人数不一定必须是大多数，只是读写使用的节点交集至少需要包括一个节点。其他法定人数的配置是可能的，这使得分布式算法的设计有一定的灵活性【45】。

您也可以将w和r设置为较小的数字，以使$w + r≤n$（即法定条件不满足）。在这种情况下，读取和写入操作仍将被发送到n个节点，但操作成功只需要少量的成功响应。

较小的w和r更有可能会读取过时的数据，因为您的读取更有可能不包含具有最新值的节点。另一方面，这种配置允许更低的延迟和更高的可用性：如果存在网络中断，并且许多副本变得无法访问，则可以继续处理读取和写入的机会更大。只有当可达副本的数量低于w或r时，数据库才分别变得不可用于写入或读取。

但是，即使在$w + r> n$的情况下，也可能存在返回陈旧值的边缘情况。这取决于实现，但可能的情况包括：

• 如果使用宽松的法定人数（见“宽松的法定人数与提示移交”），w个写入和r个读取落在完全不同的节点上，因此r节点和w之间不再保证有重叠节点【46】。
• 如果两个写入同时发生，不清楚哪一个先发生。在这种情况下，唯一安全的解决方案是合并并发写入（请参阅第171页的“处理写入冲突”）。如果根据时间戳（最后写入胜利）挑选出一个胜者，则由于时钟偏差[35]，写入可能会丢失。我们将返回“检测并发写入”中的此主题。
• 如果写操作与读操作同时发生，写操作可能仅反映在某些副本上。在这种情况下，不确定读取是返回旧值还是新值。
• 如果写操作在某些副本上成功，而在其他节点上失败（例如，因为某些节点上的磁盘已满），在小于w个副本上写入成功。所以整体判定写入失败，但整体写入失败并没有在写入成功的副本上回滚。这意味着如果一个写入虽然报告失败，后续的读取仍然可能会读取这次失败写入的值【47】。
• 如果携带新值的节点失败，需要读取其他带有旧值的副本。并且其数据从带有旧值的副本中恢复，则存储新值的副本数可能会低于w，从而打破法定人数条件。
• 即使一切工作正常，有时也会不幸地出现关于**时序（timing）**的边缘情况，我们将在第334页上的“线性化和法定人数”中看到这点。

因此，尽管法定人数似乎保证读取返回最新的写入值，但在实践中并不那么简单。 Dynamo风格的数据库通常针对可以忍受最终一致性的用例进行优化。允许通过参数w和r来调整读取陈旧值的概率，但把它们当成绝对的保证是不明智的。

尤其是，通常没有得到“与延迟有关的问题”（读取您的写入，单调读取或一致的前缀读取）中讨论的保证，因此前面提到的异常可能会发生在应用程序中。更强有力的保证通常需要事务或共识。我们将在第七章和第九章回到这些话题。

监控陈旧度

从运维的角度来看，监视你的数据库是否返回最新的结果是很重要的。即使应用可以容忍陈旧的读取，您也需要了解复制的健康状况。如果显著落后，应该提醒您，以便您可以调查原因（例如，网络中的问题或超载节点）。

对于基于领导者的复制，数据库通常会公开复制滞后的度量标准，您可以将其提供给监视系统。这是可能的，因为写入按照相同的顺序应用于领导者和追随者，并且每个节点在复制日志中具有一个位置（在本地应用的写入次数）。通过从领导者的当前位置中减去随从者的当前位置，您可以测量复制滞后量。

然而，在无领导者复制的系统中，没有固定的写入顺序，这使得监控变得更加困难。而且，如果数据库只使用读修复（没有反熵过程），那么对于一个值可能会有多大的限制是没有限制的-如果一个值很少被读取，那么由一个陈旧副本返回的值可能是古老的。

已经有一些关于衡量无主复制数据库中的复制陈旧度的研究，并根据参数n，w和r来预测陈旧读取的预期百分比【48】。不幸的是，这还不是很常见的做法，但是将过时测量值包含在数据库的标准度量标准中是一件好事。最终的一致性是故意模糊的保证，但是对于可操作性来说，能够量化“最终”是很重要的。

宽松的法定人数与提示移交

合理配置的法定人数可以使数据库无需故障切换即可容忍个别节点的故障。也可以容忍个别节点变慢，因为请求不必等待所有n个节点响应——当w或r节点响应时它们可以返回。对于需要高可用、低延时、且能够容忍偶尔读到陈旧值的应用场景来说，这些特性使无主复制的数据库很有吸引力。

然而，法定人数（如迄今为止所描述的）并不像它们可能的那样具有容错性。网络中断可以很容易地将客户端从大量的数据库节点上切断。虽然这些节点是活着的，而其他客户端可能能够连接到它们，但是从数据库节点切断的客户端，它们也可能已经死亡。在这种情况下，剩余的可用节点可能会少于可用节点，因此客户端可能无法达到法定人数。

在一个大型的群集中（节点数量明显多于n个），网络中断期间客户端可能连接到某些数据库节点，而不是为了为特定值组成法定人数的节点们。在这种情况下，数据库设计人员需要权衡一下：

• 将错误返回给我们无法达到w或r节点的法定数量的所有请求是否更好？
• 或者我们是否应该接受写入，然后将它们写入一些可达的节点，但不在n值通常存在的n个节点之间？

后者被认为是一个宽松的法定人数（sloppy quorum）【37】：写和读仍然需要w和r成功的响应，但是那些可能包括不在指定的n个“主”节点中的值。比方说，如果你把自己锁在房子外面，你可能会敲开邻居的门，问你是否可以暂时停留在沙发上。

一旦网络中断得到解决，代表另一个节点临时接受的一个节点的任何写入都被发送到适当的“本地”节点。这就是所谓的提示移交（hinted handoff）。（一旦你再次找到你的房子的钥匙，你的邻居礼貌地要求你离开沙发回家。）

宽松的法定人数对写入可用性的提高特别有用：只要有任何w节点可用，数据库就可以接受写入。然而，这意味着即使当$w + r> n$时，也不能确定读取某个键的最新值，因为最新的值可能已经临时写入了n之外的某些节点【47】。

因此，在传统意义上，一个宽松的法定人数实际上不是一个法定人数。这只是一个保证，即数据存储在w节点的地方。不能保证r节点的读取直到提示已经完成。

在所有常见的Dynamo实现中，宽松的法定人数是可选的。在Riak中，它们默认是启用的，而在Cassandra和Voldemort中它们默认是禁用的【46,49,50】。

运维多个数据中心

我们先前讨论了跨数据中心复制作为多主复制的用例（参阅“多主复制”）。无主复制还适用于多数据中心操作，因为它旨在容忍冲突的并发写入，网络中断和延迟尖峰。

Cassandra和Voldemort在正常的无主模型中实现了他们的多数据中心支持：副本的数量n包括所有数据中心的节点，在配置中，您可以指定每个数据中心中您想拥有的副本的数量。无论数据中心如何，每个来自客户端的写入都会发送到所有副本，但客户端通常只等待来自其本地数据中心内的法定节点的确认，从而不会受到跨数据中心链路延迟和中断的影响。对其他数据中心的高延迟写入通常被配置为异步发生，尽管配置有一定的灵活性【50,51】。

Riak将客户端和数据库节点之间的所有通信保持在一个数据中心本地，因此n描述了一个数据中心内的副本数量。数据库集群之间的跨数据中心复制在后台异步发生，其风格类似于多领导者复制【52】。

检测并发写入

Dynamo风格的数据库允许多个客户端同时写入相同的Key，这意味着即使使用严格的法定人数也会发生冲突。这种情况与多领导者复制相似（参阅“处理写入冲突”），但在Dynamo样式的数据库中，在读修复或提示移交期间也可能会产生冲突。

问题在于，由于可变的网络延迟和部分故障，事件可能在不同的节点以不同的顺序到达。例如，图5-12显示了两个客户机A和B同时写入三节点数据存储区中的键X：

• 节点1 接收来自 A 的写入，但由于暂时中断，从不接收来自 B 的写入。
• 节点2 首先接收来自 A 的写入，然后接收来自 B 的写入。
• 节点3 首先接收来自 B 的写入，然后从 A 写入。

图5-12 并发写入Dynamo风格的数据存储：没有明确定义的顺序。

如果每个节点只要接收到来自客户端的写入请求就简单地覆盖了某个键的值，那么节点就会永久地不一致，如图5-12中的最终获取请求所示：节点2认为 X 的最终值是 B，而其他节点认为值是 A 。

为了最终达成一致，副本应该趋于相同的值。如何做到这一点？有人可能希望复制的数据库能够自动处理，但不幸的是，大多数的实现都很糟糕：如果你想避免丢失数据，你（应用程序开发人员）需要知道很多有关数据库冲突处理的内部信息。

在“处理写冲突”一节中已经简要介绍了一些解决冲突的技术。在总结本章之前，让我们来更详细地探讨这个问题。

最后写入胜利（丢弃并发写入）

实现最终融合的一种方法是声明每个副本只需要存储最**“最近”的值，并允许“更旧”**的值被覆盖和抛弃。然后，只要我们有一种明确的方式来确定哪个写是“最近的”，并且每个写入最终都被复制到每个副本，那么复制最终会收敛到相同的值。

正如**“最近”的引号所表明的，这个想法其实颇具误导性。在图5-12的例子中，当客户端向数据库节点发送写入请求时，客户端都不知道另一个客户端，因此不清楚哪一个先发生了。事实上，说“发生”是没有意义的：我们说写入是并发（concurrent）**的，所以它们的顺序是不确定的。

即使写入没有自然的排序，我们也可以强制任意排序。例如，可以为每个写入附加一个时间戳，挑选最**“最近”的最大时间戳，并丢弃具有较早时间戳的任何写入。这种冲突解决算法被称为最后写入胜利（LWW, last write wins）**，是Cassandra 【53】唯一支持的冲突解决方法，也是Riak 【35】中的一个可选特征。

LWW实现了最终收敛的目标，但以持久性为代价：如果同一个Key有多个并发写入，即使它们都被报告为客户端成功（因为它们被写入 w 个副本），但只有一个写入将存活，而其他写入将被静默丢弃。此外，LWW甚至可能会删除不是并发的写入，我们将在的“有序事件的时间戳”中讨论。

有一些情况，如缓存，其中丢失的写入可能是可以接受的。如果丢失数据不可接受，LWW是解决冲突的一个很烂的选择。

与LWW一起使用数据库的唯一安全方法是确保一个键只写入一次，然后视为不可变，从而避免对同一个密钥进行并发更新。例如，Cassandra推荐使用的方法是使用UUID作为键，从而为每个写操作提供一个唯一的键【53】。

“此前发生”的关系和并发

我们如何判断两个操作是否是并发的？为了建立一个直觉，让我们看看一些例子：

• 在图5-9中，两个写入不是并发的：A的插入发生在B的增量之前，因为B递增的值是A插入的值。换句话说，B的操作建立在A的操作上，所以B的操作必须有后来发生。我们也可以说B是**因果依赖（causally dependent）**于A
• 另一方面，图5-12中的两个写入是并发的：当每个客户端启动操作时，它不知道另一个客户端也正在执行操作同样的Key。因此，操作之间不存在因果关系。

如果操作B了解操作A，或者依赖于A，或者以某种方式构建于操作A之上，则操作A在另一个操作B之前发生。在另一个操作之前是否发生一个操作是定义什么并发的关键。事实上，我们可以简单地说，如果两个操作都不在另一个之前发生，那么两个操作是并发的（即，两个操作都不知道另一个）【54】。

因此，只要有两个操作A和B，就有三种可能性：A在B之前发生，或者B在A之前发生，或者A和B并发。我们需要的是一个算法来告诉我们两个操作是否是并发的。如果一个操作发生在另一个操作之前，则后面的操作应该覆盖较早的操作，但是如果这些操作是并发的，则存在需要解决的冲突。

并发性，时间和相对性

如果两个操作**“同时”发生，似乎应该称为并发——但事实上，它们在字面时间上重叠与否并不重要。由于分布式系统中的时钟问题，现实中是很难判断两个事件是否同时**发生的，这个问题我们将在第8章中详细讨论。

为了定义并发性，确切的时间并不重要：如果两个操作都意识不到对方的存在，就称这两个操作并发，而不管它们发生的物理时间。人们有时把这个原理和狭义相对论的物理学联系起来【54】，它引入了信息不能比光速更快的思想。因此，如果事件之间的时间短于光通过它们之间的距离，那么发生一定距离的两个事件不可能相互影响。

在计算机系统中，即使光速原则上允许一个操作影响另一个操作，但两个操作也可能是并行的。例如，如果网络缓慢或中断，两个操作间可能会出现一段时间间隔，且仍然是并发的，因为网络问题阻止一个操作意识到另一个操作的存在。

捕获"此前发生"关系

来看一个算法，它确定两个操作是否为并发的，还是一个在另一个之前。为了简单起见，我们从一个只有一个副本的数据库开始。一旦我们已经制定了如何在单个副本上完成这项工作，我们可以将该方法概括为具有多个副本的无领导者数据库。

图5-13显示了两个客户端同时向同一购物车添加项目。（如果这样的例子让你觉得太麻烦了，那么可以想象，两个空中交通管制员同时把飞机添加到他们正在跟踪的区域）最初，购物车是空的。在它们之间，客户端向数据库发出五次写入：

1. 客户端1 将牛奶加入购物车。这是该键的第一次写入，服务器成功存储了它并为其分配版本号1，最后将值与版本号一起回送给客户端。
2. 客户端2 将鸡蛋加入购物车，不知道客户端1 同时添加了牛奶（客户端2 认为它的鸡蛋是购物车中的唯一物品）。服务器为此写入分配版本号2，并将鸡蛋和牛奶存储为两个单独的值。然后它将这两个值都反回给客户端2 ，并附上版本号2 。
3. 客户端1 不知道客户端2 的写入，想要将面粉加入购物车，因此认为当前的购物车内容应该是[牛奶，面粉]。它将此值与服务器先前向客户端1 提供的版本号1 一起发送到服务器。服务器可以从版本号中知道[牛奶，面粉]的写入取代了[牛奶]的先前值，但与[鸡蛋]的值是并发的。因此，服务器将版本3 分配给[牛奶，面粉]，覆盖版本1值[牛奶]，但保留版本2 的值[蛋]，并将所有的值返回给客户端1 。
4. 同时，客户端2 想要加入火腿，不知道客端户1 刚刚加了面粉。客户端2 在最后一个响应中从服务器收到了两个值[牛奶]和[蛋]，所以客户端2 现在合并这些值，并添加火腿形成一个新的值，[鸡蛋，牛奶，火腿]。它将这个值发送到服务器，带着之前的版本号2 。服务器检测到新值会覆盖版本2 [鸡蛋]，但新值也会与版本3 [牛奶，面粉]并发，所以剩下的两个是v3 [牛奶，面粉]，和v4：[鸡蛋，牛奶，火腿]
5. 最后，客户端1 想要加培根。它以前在v3中从服务器接收[牛奶，面粉]和[鸡蛋]，所以它合并这些，添加培根，并将最终值[牛奶，面粉，鸡蛋，培根]连同版本号v3发往服务器。这会覆盖v3[牛奶，面粉]（请注意[鸡蛋]已经在最后一步被覆盖），但与v4[鸡蛋，牛奶，火腿]并发，所以服务器保留这两个并发值。

图5-13 捕获两个客户端之间的因果关系，同时编辑购物车。

图5-13中的操作之间的数据流如图5-14所示。箭头表示哪个操作发生在其他操作之前，意味着后面的操作知道或依赖于较早的操作。在这个例子中，客户端永远不会完全掌握服务器上的数据，因为总是有另一个操作同时进行。但是，旧版本的值最终会被覆盖，并且不会丢失任何写入。

图5-14 图5-13中的因果依赖关系图。

请注意，服务器可以通过查看版本号来确定两个操作是否是并发的——它不需要解释该值本身（因此该值可以是任何数据结构）。该算法的工作原理如下：

• 服务器为每个键保留一个版本号，每次写入键时都增加版本号，并将新版本号与写入的值一起存储。
• 当客户端读取键时，服务器将返回所有未覆盖的值以及最新的版本号。客户端在写入前必须读取。
• 客户端写入键时，必须包含之前读取的版本号，并且必须将之前读取的所有值合并在一起。（来自写入请求的响应可以像读取一样，返回所有当前值，这使得我们可以像购物车示例那样连接多个写入。）
• 当服务器接收到具有特定版本号的写入时，它可以覆盖该版本号或更低版本的所有值（因为它知道它们已经被合并到新的值中），但是它必须保持所有值更高版本号（因为这些值与传入的写入同时发生）。

当一个写入包含前一次读取的版本号时，它会告诉我们写入的是哪一种状态。如果在不包含版本号的情况下进行写操作，则与所有其他写操作并发，因此它不会覆盖任何内容——只会在随后的读取中作为其中一个值返回。

合并同时写入的值

这种算法可以确保没有数据被无声地丢弃，但不幸的是，客户端需要做一些额外的工作：如果多个操作并发发生，则客户端必须通过合并并发写入的值来擦屁股。 Riak称这些并发值兄弟（siblings）。

合并兄弟值，本质上是与多领导者复制中的冲突解决相同的问题，我们先前讨论过（参阅“处理写入冲突”）。一个简单的方法是根据版本号或时间戳（最后写入胜利）选择一个值，但这意味着丢失数据。所以，你可能需要在应用程序代码中做更聪明的事情。

以购物车为例，一种合理的合并兄弟方法就是集合求并。在图5-14中，最后的两个兄弟是[牛奶，面粉，鸡蛋，熏肉]和[鸡蛋，牛奶，火腿]。注意牛奶和鸡蛋出现在两个，即使他们每个只写一次。合并的价值可能是像[牛奶，面粉，鸡蛋，培根，火腿]，没有重复。

然而，如果你想让人们也可以从他们的手推车中删除东西，而不是仅仅添加东西，那么把兄弟求并可能不会产生正确的结果：如果你合并了两个兄弟手推车，并且只在其中一个兄弟值里删掉了它，那么被删除的项目会重新出现在兄弟的并集中【37】。为了防止这个问题，一个项目在删除时不能简单地从数据库中删除;相反，系统必须留下一个具有合适版本号的标记，以指示合并兄弟时该项目已被删除。这种删除标记被称为墓碑（tombstone）。（我们之前在“哈希索引”中的日志压缩的上下文中看到了墓碑。）

因为在应用程序代码中合并兄弟是复杂且容易出错的，所以有一些数据结构被设计出来用于自动执行这种合并，如“自动冲突解决”中讨论的。例如，Riak的数据类型支持使用称为CRDT的数据结构家族【38,39,55】可以以合理的方式自动合并兄弟，包括保留删除。

版本向量

图5-13中的示例只使用一个副本。当有多个副本但没有领导者时，算法如何修改？

图5-13使用单个版本号来捕获操作之间的依赖关系，但是当多个副本并发接受写入时，这是不够的。相反，除了对每个键使用版本号之外，还需要在每个副本中使用版本号。每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本中看到的版本号。这个信息指出了要覆盖哪些值，以及保留哪些值作为兄弟。

所有副本的版本号集合称为版本向量（version vector）【56】。这个想法的一些变体正在使用，但最有趣的可能是在Riak 2.0 【58,59】中使用的分散版本矢量（dotted version vector）【57】。我们不会深入细节，但是它的工作方式与我们在购物车示例中看到的非常相似。

与图5-13中的版本号一样，当读取值时，版本向量会从数据库副本发送到客户端，并且随后写入值时需要将其发送回数据库。（Riak将版本向量编码为一个字符串，它称为因果上下文（causal context））。版本向量允许数据库区分覆盖写入和并发写入。

另外，就像在单个副本的例子中，应用程序可能需要合并兄弟。版本向量结构确保从一个副本读取并随后写回到另一个副本是安全的。这样做可能会创建兄弟，但只要兄弟姐妹合并正确，就不会丢失数据。

版本向量和向量时钟

版本向量有时也被称为矢量时钟，即使它们不完全相同。差别很微妙——请参阅参考资料的细节【57,60,61】。简而言之，在比较副本的状态时，版本向量是正确的数据结构。

本章小结

在本章中，我们考察了复制的问题。复制可以用于几个目的：

高可用性

即使在一台机器（或多台机器，或整个数据中心）停机的情况下也能保持系统正常运行

断开连接的操作

允许应用程序在网络中断时继续工作

延迟

将数据放置在距离用户较近的地方，以便用户能够更快地与其交互

可伸缩性

能够处理比单个机器更高的读取量可以通过对副本进行读取来处理

尽管是一个简单的目标-在几台机器上保留相同数据的副本，但复制却是一个非常棘手的问题。它需要仔细考虑并发和所有可能出错的事情，并处理这些故障的后果。至少，我们需要处理不可用的节点和网络中断（甚至不考虑更隐蔽的故障，例如由于软件错误导致的无提示数据损坏）。

我们讨论了复制的三种主要方法：

单主复制

客户端将所有写入操作发送到单个节点（领导者），该节点将数据更改事件流发送到其他副本（追随者）。读取可以在任何副本上执行，但从追随者读取可能是陈旧的。

多主复制

客户端发送每个写入到几个领导节点之一，其中任何一个都可以接受写入。领导者将数据更改事件流发送给彼此以及任何跟随者节点。

无主复制

客户端发送每个写入到几个节点，并从多个节点并行读取，以检测和纠正具有陈旧数据的节点。每种方法都有优点和缺点。单主复制是非常流行的，因为它很容易理解，不需要担心冲突解决。在出现故障节点，网络中断和延迟峰值的情况下，多领导者和无领导者复制可以更加稳健，但以更难以推理并仅提供非常弱的一致性保证为代价。

复制可以是同步的，也可以是异步的，在发生故障时对系统行为有深远的影响。尽管在系统运行平稳时异步复制速度很快，但是在复制滞后增加和服务器故障时要弄清楚会发生什么，这一点很重要。如果一个领导者失败了，并且你推动一个异步更新的追随者成为新的领导者，那么最近承诺的数据可能会丢失。

我们研究了一些可能由复制滞后引起的奇怪效应，我们讨论了一些有助于决定应用程序在复制滞后时的行为的一致性模型：

写后读

用户应该总是看到自己提交的数据。

单调读

用户在一个时间点看到数据后，他们不应该在某个早期时间点看到数据。

一致前缀读

用户应该将数据视为具有因果意义的状态：例如，按照正确的顺序查看问题及其答复。

最后，我们讨论了多领导者和无领导者复制方法所固有的并发问题：因为他们允许多个写入并发发生冲突。我们研究了一个数据库可能使用的算法来确定一个操作是否发生在另一个操作之前，或者它们是否同时发生。我们还谈到了通过合并并发更新来解决冲突的方法。

第六章、数据分区

• 分区概念
  • 分区：每一条数据只属于某个特定分区。
  • 采用数据分区的主要目的是提高可扩展性。不同的分区可以放在一个无共享集群的不同节点上。
  • 分区通常与复制结合使用，即每个分区在多个节点都存在有副本。某条记录属于特定的分区，而同样的内容会保存在不同的节点上以提高系统的容错性。
  • 一个节点可能存储多个分区，每个分区都有自己的主副本，一个节点可能即是某些分区的主副本，同时又是其他分区的从副本。
  • 分区的主要目的是将数据和查询负载均匀分布在所有节点上。
• 分区方案
  • 键值数据的分区
    • 如果节点平均分担负载，那么理论上10 个节点应该能够处理10 倍的数据量和10 倍与单节点的读写吞吐量。
    • 避免热点最简单的方法是将记录随机分配给所有节点，但与此同时查询节点内容时，比较复杂。
  • 基于关键字区间的分区
    • 为每个分区分配一段连续的关键字或者关键字区间范围。
    • 关键字区间不一定要均匀，因为数据本身可能就不均匀。
    • 基于关键字的区间分区的缺点是某些访问模式会导致热点。如果关键字是时间戳，某一时间段内可能都会集中在同一个分区，导致负载过高，其他分区始终处于空闲状态。
  • 基于关键字哈希值分区
    • 一个好的哈希函数可以处理数据倾斜并使其均匀分布。
    • 通过哈希函数，理论上可以将 Key均匀的分配到每个分区上，但是丧失了良好的区间查找特性。
    • 采用哈希分区时，通常事先创建好足够多的分区，让每个节点承担多个分区，当添加或删除节点时将某些分区从一个节点迁移到另一个节点，也可以支持动态分区。
• 二级索引分区
  • 基于文档来分区的二级索引
    • 二级索引存储在与关键字相同的分区中，这意味着写入时我们只需要更新一个分区。
    • 缺点是读取二级索引时需要在所有分区执行 scatter/gather。
  • 基于词条来分区二级索引
    • 它是基于索引的值而进行的独立分区
    • 二级索引中的条目可能包含来自关键字的多个分区里的记录。
    • 在写入时，不得不更新二级索引的多个分区，但读取时，则可以从单个分区直接快速提取数据。
• 请求路由
  • 三种不同的策略
    • 允许客户端连接任意节点，如果某个节点恰好拥有所请求的分区，则直接处理该请求；否则将请求转发到下一个合适的节点，接收答复，并将答复返回给客户端。
      • Cassandra、Riak
    • 将所有客户端的请求都发送到一个路由层，由后者负责将请求转发到对应的分区节点上，路由层本身不处理任何请求，它仅充当一个分区感知的负载均衡器。
      • 常见的 DNS，针对分区和节点变化往往没有那么频繁
    • 客户端感知分区和节点分配关系。客户端可以直接连接到目标节点，而不需要任何中介。
      • Zookeeper、HBase、SolrCloud、Kafka

第七章、事务

ACID 概念

• 事务不是一个天然存在的东西，它是被人为创造出来e，目的是简化应用层的编程模型。
• 如何判断是否需要事务？
• 现行的大多数数据库都是基于 IBM 1975 年推出的第一个 SystemR 相似的总体设计。
• ACID 的含义，最早在1983 年被提出。
  • 原子性（Atomicity）
  • 一致性（Consistency）
  • 隔离性（Isolation）
  • 持久性（durability）
• 原子性
  • 描述了客户端发起一个包含多个写操作的请求时可能发生的情况，把多个写操作纳入到一个原子事务，万一出现上述故障而导致没法完成最终提交时，则事务会中止，并且数据库须丢弃或撤离那些局部完成的更改。
  • 在出错时中止事务，并将部分完成的写入全部丢弃。
• 一致性
  • 一致性哈希则是某些应用用于动态分区再平衡的方法。
  • 一致性本质上要求应用层来维护状态一致，应用程序有责任正确地定义事务来保持一致性，这不是数据库可以保证的事情。
  • 原子性，隔离性和持久性是数据库自身的属性，而一致性更多是应用层的属性。
  • 应用程序可能借助数据库提供的原子性和隔离性，以达到一致性，但一致性本身并不源于数据库。
• 隔离性
  • 隔离性意味着并发执行的多个事情相互隔离，他们不能相互交叉。
  • 经典的数据库教材吧隔离定义为可串行化，这意味着可以假装它是数据库上运行的唯一事务。
  • 在实践中，很少有数据库使用串行隔离，Oracle 本质上使用的是快照隔离。
• 持久性
  • 持久性保证一旦事务提交成功，即使存在硬件故障或数据库崩溃，事务所写入的任何数据也不会消失。
  • 为了实现持久性的保证，数据库必须等到这些写入或复制完成之后才能报告事务成功提交。
• 弱隔离级别
  • 只有出现某个事务修改数据而另一个事务同时要读取该数据，或者两个事务同时修改相同的数据时，才会引发并发问题。

读提交

• 读-提交是最基本的事务隔离级别
  • 读数据库时，只能看到已成功提交的数据（防止“脏读”）。
  • 写数据库时，只会覆盖已成功提交的数据（防止“脏写”）。
• 防止脏读
  • 如果一个事务已经完成部分数据写入，但事务尚未提交，此时如果另一个事务可以看到尚未提交的数据，那就是脏读。
  • 脏读场景
    • 如果事务更新的多个对象，脏读意味着另一个事务可能会看到部分更新，而非全部。
    • 如果事务发生中止，则所有写入操作都需要回滚，如果发生了脏读，这意味着他看的到一些数据稍后被回滚，实际并未提交到数据库中。
• 防止脏写
  • 如果两个事务同时尝试更新相同的对象，则后写入的操作会覆盖较早的写入，如果先写入的是尚未提交事务的一部分，如果此时后写入的继续覆盖，那么就会发生脏写。
  • 通常防止脏写的方式是推迟第二个写请求，知道前面的事务完成提交（或者中止）。
  • 防止脏写可以防止一下情况
    • 如果事务需要更新多个对象，脏写会带来非预期的错误结果。
    • 读写隔离不能解决计数器增量的竞争情况。
• 实现读提交
  • 数据库通常采用行级锁来防止脏写：当事务想修改某个对象时，他必须首先获得该对象的锁，然后一直持有锁直到事务提交（或中止）。
  • 如何防止脏读？使用锁的方式效率太低，实际采用的是：对于每个待更新的对象，数据库都会维护其旧值和当前持锁事务将要设置的新值两个版本。
  • 在事务提交前，所有其他读操作都读取旧值，仅当写事务提交之后，才会切换到读取新值。

快照级别隔离和可重复读

• 有 A、B 两个500 美元的账号，假设 A 账户给 B 账户转100 美元，经历中间过程，最终 A 账号400 美元，B 账户600 美元，但是如果在中间运算的过程中，你可能会看到 A账户400 美元，B账户500 美元的情况，这种异常现象称为不可重复读（nonrepeatable read）或读倾斜（read skew）。
• 虽然中间经历的过程并非永久性，但是在有些场景就不能容忍：
  • 备份场景：备份数据库的过程，在整体备份过程中可能发生上午转账的场景，如果使用上述的方式的数据库进行备份恢复，则会导致永久性的不一致。
  • 分析查询与完整性检查场景：有时查询可能会扫描大半个数据库，如果查询在不同时间点观察数据库，可能返回无意义的结果。
• 快照级别隔离对于长时间运行的只读查询非常有用。
• 实现快照级别隔离
  • 快照级别隔离的实现通常采用写锁来防止脏写，这意味着增在进行写操作的事务会阻止同一对象上的其他事物。但是读取则不需要加锁。
  • 快照级别隔离的一个关键点是读操作不会阻止写操作，使得在处理正常写入的同时，在一致性快照上执行长时间的只读查询，且两者之间没有任何锁的竞争。
  • 考虑到多个正在进行的事务可能会在不同的时间点查看数据库状态，所以数据库保留了对象多个不同的提交版本，这种技术被称为多版本并发控制（Multi-Version Concurrency Control，MVCC）。
  • 如果只是为了提供读-提交级别隔离，而不是完整的快照级别隔离，则只保留对象的两个版本就足够了：一个已提交的旧版本和尚未提交的新版本。
  • 支持快照级别隔离的存储引擎往往直接采用 MVCC 来实现读-提交隔离，典型就是在读-提交级别下，对每一个不同的查询单独创建一个快照；而快照级别隔离则是使用一个快照来运行整个事务。
• 一致性快照的可见性规则
  • 每笔事务开始时，数据库列出所有当时尚在进行中的其他事务，然后忽略这些事务完成的部分写入，即不可见。
  • 所有中止事务所做的修改全部不可见。
  • 较晚事务 ID 所作的任何修改不可见，不管这些事务是否完成了提交。
• 索引与快照级别隔离
  • 一种方案是索引直接指向对象的所有版本，然后想办法过滤当前事务不可见的那些版本。当后台的垃圾回收进程决定删除某个就对象版本时，对应的索引条目也需要随之删除。
  • 另一种采用追加、写时复制的技术，当需要更新时，不会修改现有的页面，而总是创建一个新的修改副本，拷贝必要的内容，然后让父节点，或者递归向上直到树的 root 节点都指向新创建的节点。

防止更新丢失

• 读-提交和快照级别隔离主要都是为了解决只读事务遇到并发写时可以看到什么。
• 另一种情况是两个写事务并发，而脏写知识写并发的一个特例，其中主要涉及到了更新丢失的问题。
• 应用程序从数据库读取某些值，根据应用逻辑做出修改，然后写回新值(read-modify-write过程)。当有两个事务在同样的数据对象上执行类似操作时，由于隔离性，第二个写操作并不包括第一个事务修改后的值，最终会导致第一个事务的修改值可能会丢失。

并发写事务的解决方案

原子写操作

• update xx set value = value+1 where id = 1;
• 原子操作通常采用对读取对象加独占锁的方式来实现，这样在更新被提交之前不会其他事务可以读它。
• 另一种方式是强制所有的原子操作都在单线程上执行。

显式加锁

• 由应用程序显式锁定待更新的对象。然后，应用程序可以执行“读-修改-写回”这样的操作序列; 此时如果有其他事务尝试同时读取对象，则必须等待当前正在执行的序列全部完成。
• FOR UPDATE指令指示数据库对返回的所有结果行要加锁。

自动检测更新丢失

• 先让他们并发执行，但如果事务管理器检测到了更新丢失风险，则会中止当前事务，并强制回退到安全的“读-修改-写回”方式。
• 该方法的一个优点是数据库完全可以借助快照级别隔离来高效地执行检查。

原子比较和设置

• 使用该操作可以避免更新丢失，即只有在上次读取的数据没有发生变化时才允许更新; 如果已经发生了变化，则回退到“读-修改-写回”方式。

冲突解决与复制

• 多副本数据库通常支持多个并发写，然后保留多个冲突版本(互称为兄弟)，之后由应用层逻辑或依靠特定的数据结构来解决、合并多版本。

写倾斜与幻读

• 在一个事务中的写入改变了另一个事务查询结果的现象，称为幻读。
• 快照级别隔离可以避免只读查询时的幻读，但是对于我们上面所讨论那些读-写事务，它却无法解决棘手的写倾斜问题。

串行化

• 可串行化隔离通常被认为是最强的隔离级别。它保证即使事务可能会井行执行，但最终的结果与每次一个即串行执行结果相同。
• 串行化的三种实现方法
  • 严格按照串行顺序执行。
  • 两阶段锁定。
  • 乐观井发控制技术，例如可串行化的快照隔离。

实际串行执行

• 转向单线程的思考
  • 内存越来越便直，现在讲多应用可以将整个活动数据集都加载到内存中。
  • 数据库设计人员意识到 OLTP事务通常执行很快，只产生少量的读写操作
• 采用存储过程封装事务
  • 事务总体沿用的依然是交互式客户端/服务器风格，一次一个请求语句。应用程序来提交查询，读取结果，可能会根据前一个查询的结果来进行其他查询，依此类推。
  • 如果不允许事务并发，而是一次仅处理一个，那么吞吐量非常低，数据库总是在等待应用提交下一个请求。在这种类型的数据库中，为了获得足够的吞吐性能，需要能够同时处理多个事务。
  • 存储过程与内存式数据存储使得单线程上执行所有事务变得可行。它们不需要等待 I/O，避免加锁开销等复杂的井发控制机制，可以得到相当不错的吞吐量。
• 分区
  • 串行执行所有事务使得井发控制更加简单，但是数据库的吞吐量被限制在单机单个CPU核。虽然只读事务可以在单独的快照上执行，但是对于那些高写入需求的应用程序，单线程事务处理很容易成为严重的瓶颈。
• 串行执行小结
  • 事务必须简短而高效，否则一个缓慢的事务会影响到所有其他事务的执行性能。
  • 仅限于活动数据集完全可以加载到内存的场景。有些很少访问的数据可能会被移到磁盘，但万一单线程事务需要访问它，就会严重拖累性能。
  • 写入吞吐量必须足够低，才能在单个CPU核上处理;否则就需要采用分区，最好没有跨分区事务。
  • 跨分区事务虽然也可以支持，但是占比必须很小。

两阶段加锁

• 可以使用加锁的方法来防止脏写，如果两个事务同时尝试写入同一个对象时，以加锁的方式来确保第二个写入等待前面事务完成(包括中止或提交)。

• 多个事务可以同时读取同一对象，但只要出现任何写操作(包括修改或删除)，则必须加锁以独占访问。

• 2PL不仅在井发写操作之间互斥，读取也会和修改产生互斥。 快照级别隔离的口 号 “读写互不干扰” 非常准确地点明了它 和两阶段加锁的关键区别。

• 2PL 基本用法如下:

  • 如果事务要读取对象 ，必须先以共享模式获得锁。可以有多个事务同时获得一个 对象的共享锁，但是如果某个事务已经获得了对象的独占锁，则所有其他事务必 须等待。
  • 如果事务要修改对象，必须以独占模式获取锁。不允许多个事务同时持有该锁 (包括共享或独占模式)，换言之，如果对象上已被加锁， 则修改事务必须等待。
  • 如果事务首先读取对象，然后尝试写入对象，则需要将共享锁升级为独占锁。升级锁的流程等价于直接获得独占锁。
  • 事务 获得锁之后， 一直 持有锁直到事务结束(包括提交或中止)。这也是名字 “两阶段”的来由，在第一阶段即事务执行之前要获取锁，第二阶段(即事务结束时)则释放锁。

• 在2PL模式下数据库的访问延迟具有非常大的不确定性，如果工作负载存在严 重竞争 ，以百分比方式观察延迟指标会发现非常缓慢。

• 同样是基于加锁方式的读-提交隔离也可能发生死锁，然而在2PL下，取决于事务的访 问模式，死锁可能变得更为频繁。

• 谓词锁

  • 它的作用类似于之前描述的共享/独占锁， 而区别在于，它并不属于某个特定的对象，而是作用于满足某些搜索条件的所有查询对象。
  • 谓词锁锁会限制如下访问
    • 如果事务 A 想要读取某些搞足匹配条件的对象，例如采用 SELECT查询，它必须以共享模式获得查询条件的谓词锁。如果另一个事务B正持有任何一个匹配对象的 互斥锁，那么A必须等到B释放锁之后才能继续执行查询。
    • 如果事务A想要插入、更新或删除任何对象，则必须首先检查所有旧值和新值是 否与现有的任何谓词锁匹配(即冲突)。如果事务B持有这样的谓词锁，那么A 必须等到B完成提交(或中止)后才能继续。

可串行化的快照隔离

• 事务首先查询某些数据， 根据查询的结果来决定采取后续操作， 例如修改数据。 而在快照隔离情况下， 数据可能在查询期间就已经被其他事务修改， 导致原事务在提 交时决策的依据信息已出现变化。
• 数据库如何知道查询结果是否发生了改变呢
  • 读取是否作用于一 个(即将)过期的MVCC对象(读取之前已经有未提交的写 入)。
  • 检查写入是否影响即将完成的读取(读取之后， 又有新的写入)。
• 当另一个事务尝试修改时， 它首先检查索引， 从而确定是否最近存在一 些读目标数据 的其他事务。 这个过程类似于在受影响的字段范围上获取写锁， 但它并不会阻塞读 取， 而是直到读事务提交时才进一步通知他们:所读到的数据现在已经发生了变化。

第八章、分布式系统的挑战

对于复杂系统我们做一个悲观假定：所有可能出错的事情一定是会出错。

故障与部分失效

• 在分布式系统中，可能会出现系统的一部分工作正常，但其他部分出现难以预测的故障，我们称之为“部分失效”。问题的难点在于这种部分失效是不确定的。
• 要使分布式系统可靠工作，就必然面临部分失效，这就需要依靠软件系统来提供容错机制。换句话来说我们需要再不可靠的组件之上构建可靠的系统。
• 最好仔细考虑各种可能的出错情况，包括哪些小概率故障，然后尝试人为构造这种测试场景来充分检测系统行为。
• 可以说，在分布式系统中，怀疑、悲观和偏执狂才能生存。

不可靠的网络

• 在分布式无共享系统中，网络是跨节点同心度 e 唯一路径，我们还假定每台机器都有自己的内存和磁盘，一台机器不能直接访问另一台机器的内存和磁盘除非通过网络想对方发出请求。
• 无共享并不是构建集群系统的唯一方式，但它却是构建互联网服务的主流方式，主要原因是：可以采用相对低廉的硬件机器，采用块区域的多数据中心来实现高可靠性。
• 一个节点可以发送信息到另一个节点，但是网络并不保证它什么时候到达，甚至他是否一定到达。
• 发送之后等待响应过程中，很多事情可能会出错
  • 请求可能已经丢失（有人拔掉网线）
  • 请求可能正在某个队列中等待，无法马上发送（也许网络或接收方已经超负荷）
  • 远程接受节点可能已经失效（例如崩溃或关机）
  • 远程接受节点可能暂时无法响应（运行长时间的垃圾回收）
  • 远程接受节点已经完成了请求处理，但回复且在网络中丢失（网络交换机配置错误）
  • 远程接受节点已经完成了请求处理，但回复却被延迟处理（网络或者发送者的机器超负荷）
• 发送者在不清楚数据包是否完成了发送，只能在等待一段时间之后，如果仍然没有收到回复则选择放弃，并且认为响应不会到达，但是即使判定超时，仍然并不清楚远程节点是否收到了请求。
• 假定你的网络通畅非常可靠，而万一出现问题，一种简单的方法是对用户提示错误，但前提是必须非常清楚接下来软件会如何应对，以确保系统最终可以恢复。
• 检测故障
  • 均衡负载器需要避免像失效的节点继续分发请求。
  • 主节点失败，需要将某个从节点提成为主节点，不过，由于网络的不确定性很难准确判断节点是否确实失效。
  • 网络的不确定性是的判断节点是否失效非常困难。
  • 如果系统服务进程崩溃，但操作系统仍正常运行，可以通过脚本通知其他节点。
• 超市与无期限的延迟
  • 如果超时是故障检测唯一可行的方法，那么超时应该设多长呢？不幸的是没有标准答案。
  • 设想一个虚拟的系统，其网络可以保证数据包的最大延迟在一定范围内：要么在实践 d 内完成交付，要么丢失。此外，假定一个非故障节点总能在一段时间 r 内完成请求处理。此时，可以确定成功的请求总能在 2d+r 时间内收到响应，如果再次时间内没有收到响应，则可以推断网络或者远程节点发生了失效，那么 2d+r 是一个理想的超时设置。
• 网络拥塞与排队
  • 不同节点同时发送数据包到相同的目标节点时，网络交换机出现排队可能出现网络阻塞。
  • 当数据包到达目标机器后，如果所有 CPU 核都处于繁忙状态，则网络数据包请求会被操作系统排队，知道应用程序能够处理。
  • 在虚拟化环境下，CPU 核会切换虚拟机，从而导致增在进行的操作系统会突然暂停几十毫秒。
  • TCP 执行流量控制时，节点会主动限制自己的发送速率以避免加重网络链路或接受节点负载。

不可靠的时钟

• 时钟常用场景
  • 请求是否超时
  • 某项服务的 99% 响应时间是多少
  • 过去五分钟，服务平均每秒处理多少个查询
  • 用户在我们站点停留多长时间
  • 什么时间发送提醒邮件
  • 缓存条目何时过期
  • 日志文件中错误消息的时间戳是多少
• 在一定程度上同步机器之间的时钟，最常用的方式是网络时间协议，它可以根据一组专门的时间服务器来调整本地时间，时间服务器则从更精确更高的时间源获取高精度时间。
• 在分布式系统中，可以采用单调时钟测量一段任务的持续时间(例如超时 )，它不 假 定节点间有任何的时钟同步，且可以容忍轻微测量误差。
• 一天可 能不总是 86 400秒，时钟会向后回拨，一个节点上的时间可能与另 一个节点上的时间 完全不同。
• 常见的快照隅离实现中需要单调递增事务ID。 如果写入发生在快照之后(即写入具有 比快照更大的事务ID) , 那么该写入对于快照不可见。 在单节点数据库上， 一个简单 的计数器足以生成事务ID。
• 能否使用同步后的墙上时钟作为事务ID呢?如果我们能够获得足够可靠的同步时钟， 自然它可以符合事务ID属性要求:后发生的事务具有更大的时间戳。 然而问题还是时钟精度的不确定性。
• 在单台机器上编写多线程代码时，有不少工具可以帮助实现线程安全，互斥量、信号量、原子计数器、无锁计数器、无所数据结构、阻塞队列。
• 分布式系统中的一个节点必须假定，执行过程中的任何时刻都可能被暂停相当长一段时间，包括运行在某个函数中间。暂停期间，整个集群的其他部分都在照常运行，甚至会一直将暂停的节点宣告为故障节点。最终暂停的节点可能会回来继续运行，除非再次检查时钟，否则他对刚刚过去的暂停毫无意识。
• 提供实时保证需要来自软件栈的多个层面的支持，首先是一个实时操作系统，保证进程在给定的间隔内完成 CPU 时间片的调度分配，其次，库函数也必须考虑最坏的执行时间；然后动态内存分配很可能要受限或完全被禁止，最终还是需要大量、充分的测试和验证，以确保满足要求。

知识，真相与谎言

• 真相由多数决定
  • 节点不能根据自己的信息来判断自身的状态，由于节点随时会失效，可能会暂停-假死，甚至最终无法恢复，因此分布式系统不能完全依赖于单个节点。
  • 任何决策都需要来自多个节点的最小投票数，从而减少对特定节点的依赖。
  • 如果有法定数量的节点声明另一个节点失效，即使该节点仍然觉得很自在，那它也必须接受失效的裁定，所有个体节点必须遵循法定投票的决议然后离线。
• 主节点与锁
  • 很多情况下我们需要再系统范围内只能有一个实例
    • 只允许一个节点作为数据库分区的主节点，防止出现脑裂。
    • 只允许一个事务或客户端持有特定资源的锁，以防止同时写入而导致的数据破坏。
    • 只允许一个用户来使用特定的用户名，从而确保用户名可以唯一标识用户。
• Fencing 令牌
  • 当使用锁和租约机制来保护资源的并发访问时，必须确保过期的唯一的那个节点不能影响其他正常部分，要实现这个目标，可以采用一种相当简单的技术 fencing（栅栏）。
  • 当使用 ZooKeeper 作为锁服务时，可以用事务标识 zxid 或节点版本 cversion 来充当 fending 令牌，这两个都可以满足单调递增的要求。
  • 在服务端检查令牌可能看起来有些复杂，但其实是推荐的正确做法，系统服务不能假定所有的客户端都表现符合预期，事实上客户端通常由权限级别相对较低的人来操作运行，因此存在一定的误用、滥用风险从安全角度讲，服务端必须防范这种来自客户端的滥用。
• 拜占庭故障
  • fencing 令牌可以检测并阻止那些无意的无操作，但是，如果节点故意试图破坏系统，在发送消息时可以简单地伪造令牌即可。
  • 如果节点明明没有收到某条消息，但却对外声称收到了，这种行为称为拜占庭故障，在这样不信任的环境中需要达成共识的问题也被称为拜占庭将军问题。
  • 如果某个系统即使发生部分节点故障，甚至不遵从协议或者恶意攻击、干扰网络，但仍可继续正常运行，我们称之为拜占庭式容错系统。
• 理论系统模型与现实
  • 常见三种系统模型
    • 同步模型
      • 同步模型假定有上届的网络延迟，由上届的进程暂停和由上届的时钟误差。
      • 大多数系统的实际模型并非同步模型，因为无线延迟和暂停确实可能发生。
    • 部分同步模型
      • 部分同步意味着系统在大多数情况下像一个同步系统一样运行，但有时候会超出网络延迟，进程暂停和时钟漂移的预期上届。
      • 大多数情况下，网络和进程比较稳定，但是我们必须考虑到任何关于时机的假设都有偶尔违背的情况，一旦发生，网络延迟，暂停和始终偏差可能会变得非常大。
    • 异步模型
      • 一个算法不会对时机做任何的假设，甚至里面根本没有时钟，某些算法可以支持纯异步模型，但并不常见。
  • 三种节点失效系统模型
    • 崩溃中止模型
      • 节点可能在任何时候突然停止响应，且节点以后永远消失，无法恢复。
    • 崩溃恢复模型
      • 节点可能在任何时间发生崩溃，且可能会在一段时间之后得到恢复并在此响应。
    • 拜占庭失效模型
      • 节点可能发生任何事情，包括试图作弊和欺骗其他节点。

第九章、一致性与共识

一致性保证

• 大多数多副本的数据库都至少提供了最终的一致性，这意味着如果停止更新数据库，并等待一段时间之后，最终所有读请求会返回相同的内容。
• 当面对只提 供了弱保证的数据库时，需要清醒 地认清系统的局 限性，切不可过于乐观。
• 应用可能在大多数情况下都运行良好，但数据库内部可能已经发生了非常微妙的错误，只有当系统出现故障(例如网络中断)或高井发压力时，最终 一 致性的临界条 件或者错误才会对外暴露出来，因而测试与发现错误变得非常困难。

可线性化

• 可线性化基本的想法是让一个系统看起来好像只有一个数据副本，且所有的操作都是原子的。
• 一旦某个读操作返回了新值，之后所有的读都必须返回新值，直到被再次覆盖。
• 可串行化是事务的格力属性，其中每个事物可以读写多个对象，它用来确保事务执行的结果与串行执行的结果完全相同，即使串行执行的顺序可能与事务实际执行顺序不同。
• 可线性化是读写寄存器的最新只保证。它并要求将操作整合到事务中，因此无法避免写倾斜等问题，除非采取其他额外措施。

线性化的依赖条件

加锁与主节点选举

• 主从复制的系统需要确保有且仅有一个主节点，否则会产生脑裂。选举新的主节点常见的方法是使用锁：即每个启动的节点都是无获得锁，其中只有一个可以成功即成为主节点。
• 不管锁具体如何实现，它必须满足可线性化：所有节点都必须同意那个节点持有锁，否则就会出现问题。
• 提供协调者服务的系统 Zookeeper 和 etecd 等通常用来实现分布式锁和主节点选举，他们都是用了支持容错的共识算法确保可线性化。归根结底，线性化存储服务是所有这些协调服务的基础。

约束与唯一性保证

• 唯一性约束在数据库中很常见，例如用户名或电子邮件地址必须唯一标识一个用户。
• 硬性的唯一性约束，常见如关系型数据库中主键的约束，则需要线性化保证，其他如外键型约束，则并不要求一定线性化。

跨通道的时间依赖

• 如果系统内部有多条不同的通信通道，如果没有线性化的就近性保证，则这个两个通道之间存在竞争条件。

实现线性化系统

• 系统容错最常见的方法就是采用复制机制。
• 主从复制（部分支撑可线性化）
  • 在主从复制的系统中，只有主节点承担数据写入，从节点则在各自节点上维护数据的备份副本。
  • 如果从主节点或者同步更新的从节点上读取，则可以满足线性化，但并非每个主从复制的具体数据库实例都是可线性化的。
• 共识算法（可线性化）
  • 共识算法通过内置一些措施来防止脑裂和过期的副本。
  • 共识算法可能安全地实现线性化存储，这些系统包括 Zookeeper 和 etcd 等。
• 多主复制（不可线性化）
  • 具有多主节点复制的系统通常无法线性化的，主要由于它们同时在多个节点上执行并发写入，并将数据一步复制到其他节点，在此期间可能产生冲突的写入。
• 无主复制（可能不可线性化）
  • 主要取决于具体的 quorum 的配置，以及如何定义强一致性，它可能并不保证线性化。

线性化的代价

• 多主复制特别适合于多个数据中心的场景，由于从一个数据中心到另一个数据中心的复制是异步，其间发生的写操作都暂存到本地队列，等网络恢复之后再继续同步。
• 主从复制，则主节点位于其中的某一个数据中心，所有写请求和线性化读取都必须发送给主节点。

CAP 理论

• CAP 有时也代表一致性，可用性，分区容错性，系统只能支持其中两个特性。其中网络分区是一种故障，不管喜欢还是不喜欢，它都可能发生，所以无法选择或逃避分区的问题。

顺序与因果关系

• 英国关系对所发生的施加了某种排序：发送消息先于收到消息；问题出现在答案之前。
• 快照隔离提供了因果一致性，当从数据库中读数据时，如果查询到了某些数据，也一定能看到触发该数据的前序事件。
• 显示追踪所有已读数据意味着巨大的运行开销，我们可以使用序列号或时间戳来排序事件。

全序关系广播

• 全序关系广播通常直接点之间交换消息的某种协议。
• 满足两个基本安全属性
  • 可靠发送：没有消息丢失，如果消息发送到某一个节点，则它一定要发到所有节点。
  • 严格有序：消息总是以相同的顺序发送给每个节点。
• 即使节点或网络出现了故障，全序关系广播算法的正确性也必须被保证上述两条。
• 全序关系广播正式数据库复制所需要的：如果每条消息代表数据库写请求，并且每个副本都按照相同的顺序处理这些写请求，那么所有副本可以保持一致，这个原则被称为状态肌复制。
• 全序关系广播另一个要点是顺序在发送消息时已经确定，如果消息发送成功，节点不允许追溯地将某个消息插入到先前的某个位置上，这一点使得全序关系广播比基于时间戳要求更强。
• 理解全序关系广播的另一种方式是将其视为日志，传递消息就像追加方式更新日志。由于所有节点必须以相同的顺序发送消息，因此所有节点都可以读取日志并看到相同的消息序列。
• 全序关系广播对于提供 fencing 令牌的锁服务也很有用，每个获取锁的请求都作为小媳妇嫁到日志中，所有消息按照日志中的顺序依次编号。序号还可以作为令牌，它符合单调底层要求，在 Zookeeper 中该序列号称为 zxid。

采用全序关系广播实现线性化存储

• 屈戌关系广播是基于异步模型：保证消息以固定的顺序可靠地发送，但是不保证消息合适发送成功（因此某个接受者可能明显落后于其他接受者）。而可线性化则强调就近性，读取时保证能够看到最新的写入值。
• 为了满足线性化读取
  • 可以采用追加的方式把读请求排序、广播，然后各个节点获取该日志，当本节点收到消息时才执行真正的读操作。消息在日志中的位置已经决定了读取发生的时间点，与 etcd 的 quorum 读取思路相同。
  • 可以以线性化的方式获取当前最新日志中消息的位置，则查询位置，等待知道该位置之前的所有条目都已经发送给你，接下来在执行读取。Zookeeper 的 sync()操作思路相同。
  • 可以从同步更新的副本上进行读取，这样确保总是读取最新值，这种技术可以用于链式复制。

采用线性化存储实现全序关系广播

• 最简单的方式是假设有一个线性化的寄存器来存储一个计数，然后使其支持原子自增读取操作或者院子比较-设置操作。
• 算法思路很简单：对于每个要通过全序关系广播的消息，源自递增并读取该线性化的计数，然后将其作为序列号附加到消息中。接下来，将消息广播到所有节点，而接受者也严格按照序列化来发送回复消息。

分布式事务与共识

• 集群节点达成某种一致
  • 主节点选举
    • 对于主从复制的数据库，所有节点需要就谁来充当主节点达成一致。
    • 防止出现脑裂，出现两个主节点，导致数据不一致，甚至数据丢失。
  • 原子事务提交
    • 对于支持跨节点或跨分区事务的数据库，某个事务可能在一些节点上执行成功，但在其他节点上却不行发生了失败。
    • 如果能够在所有节点上，要么都成功要么都失败。

原子提交与两阶段提交

• 原子性可以防止失败的事务破坏系统，避免形成部分成功夹杂着部分失败。而且对于多对象事务和维护二级索引格外重要。
• 单节点
  • 在单节点上，事务提交非常依赖于数据持久写入磁盘的顺序关系：先写入数据，然后再提交。
  • 事务提交的关键点在于磁盘完成日志记录的时刻，在完成日志记录之前如果发生崩溃，则是无需要中止，如果在日志写入完成之后，即使发生崩溃，事务也被安全提交。
• 多节点
  • bug 一部分节点提交了事务，而其他节点却放弃了事务，节点之间就会变得不一直。
  • 事务提交不可撤销，不能事后再改变主意。这背后深层原因是：一旦数据提交，就被其他事务可见，继而其他客户端就会基于此做出相应的决策。
  • 当然已提交事务的效果可以被之后一笔新的食物来抵消掉，即补偿性事务。

两阶段提交

• 两阶段提交是一种再多节点之间实现事务原子提交的算法，用来确保所有节点要么全部提交，要么全部中止。
• 2PC 事务组成结构
  • 协调者：通常事先为共享库，运行在请求事务相同进程中，也可以是单独的进程或服务。
  • 参与者：多个数据库节点上执行数据读写操作。
• 2PC 请求过程
  • 当应用程序启动 一 个分布式 事务 时 ，它首先向协调者请求事务 ID。该 ID全局唯一。
  • 应用程序在每 个参与节点上执行单节点 事务，并将全局唯 一 事务 ID附加到 事务 上。此时，读写都是在单节点内完成。如果在这个阶段出现问题(例如节点崩愤 或请求超时’)，贝 lj协调者和其他参与者都可以安全中止。
  • 当应用程序准备提交时 ，协调者向所有 参与者发送准备请求 ，并附带全局事务 ID。如果准备请求有任何一个发生失败或者超时，则协调者会通知所有参与者 放弃事务。
  • 参与者在 收到准备 请求之后 ，确保在任何情况下都可以提交 事务 ，包括安全地 将事务数据写入磁盘(不能以任何借口稍后拒绝提交，包括系统崩愤，电源故 障或磁盘空间不足等)，并检查是否存在冲突或约束违规。 一 且向协调者回答 “是”，节点就承诺会提交事务。换句话说，尽管还没有真正提交，但参与者已 表态此后不会行使放弃事务的权利。
  • 当协调者收到所有准备请求的答复肘，就是否提交(或放弃) 事务要做出明确的 决定(即只有所有参与者都投赞成票时才会提交)。协调者把最后的决定写入到 磁盘的事务日志中，防止稍后系统崩愤，并可以恢复之前的决定。这个 时刻 称为 提交点。
  • 协调者的决定 写入磁盘之后 ，接下来向所有 参与者发送提交(或放弃)请求。 如 果此请求出现失败或超时，则协调者必须一直重试 ， 直到成功为止。此时，所有 节点不允肝有任何反悔:开弓没有回头箭， 一 旦做了决定，就必须贯彻执行，即 使需要很多次重试。而如果有参与者在此期间出现故障，在其恢复之后，也必须继续执行。这是因为之前参与者都投票选择了“是” ， 对于做出的承诺同样没有 反悔的余地。
• 协调者发生故障
  • 如果协调者在发送准备请求之前就已失败，则参与者可以安全地终止交易。
  • 一旦参与者收到了准备请求并作了投票“是”，则参与者不能单方面放弃，他必须等待协调者的决定，此时无果协调者发生故障，参与者只能无奈等待，导致最终的结果处于一种不确定的状态。
  • 如果数据库与协调者之间超时，也会单方面终止事务。

三阶段提交

• 两阶提交也称为阻塞式原子提交协议，因为 2PC 可能在等待协调者恢复时卡住。
• 3PC 假定一个有界的网络延迟和节点在规定时间内响应。

分布式事务

• 数据库内部的分布式事务
  • 某些分布式数据库支持跨数据库节点的内部事务。
• 异构分布式事务
  • 在异构分布式事务中，存在两种或两种以上不同的参与者实现技术。
  • 即使是完全不同的系统，跨系统的分布式事务也必须确保原子提交。

Exactly-one 消息处理

• 异构的分布式事务旨在无缝集成多种不同的系统。

• 当且仅当数据库中处理消息

  的事务成功提交，消息队列才会标记该消息已处理完毕 。这个过程是通过自动提交悄 息确认和数据库写入来实现的。即使消息系统和数据库两种不同的技术运行在不同的 节点上，采用分布式事务也能达到上述目标。

支持容错的共识

• 一个或多个节点可以提议某些值，由共识算法来决定最终值。
• 共识算法
  • 协商一致性(Uniform agre巳ment)：所有的节点都接受相同的决议。
  • 诚实性 (Integrity)：所有节点不能反悔， 即对一项提议不能有两次决定。
  • 合法性 (Validity)：如果决定了值 v， 贝Uv一定是由某 个节点所提议的。
  • 可终止性 (Termination)：节点如果不崩愤则最终一定可以达成决议。
• 协商一致性和诚实性属性定义了共识的核心思想:决定一致的结果，能改变。

共识算法与全序广播

• 全序关系广播的要点是，消息按照相同的顺序发送到所有节点，有且只有一次。
• 全序关系广播相当于持续的多轮共识
  • 由于协商一致性，所有节点决定以相同的顺序发送相同的消息。
  • 由于诚实性，消息不能重复。
  • 由于合法性，消息不会被破坏，也不是凭空捏造的。
  • 由于可终止性，消息不会丢失。
• VSR、Raft 和 Zab 都直接采取了全序关系广播，这比重复性的一轮共识只解决一个提议更加高效，而 Paxos 则有对应的优化版本称之为 Multi-Paxos。

主从复制与共识

• 所有的写入都是由主节点负责，如果该节点发生故障，系统将无法写入，知道操作人员再手动配置新的节点称为主节点，需要人为干预，不满足共识的可终止性。
• 所有的节点都需要同意主节点，否则两个主节点会导致数据库出现不一致。

Epoch 和 Quorum

• 如果发现当前的主节点失效，节点就开始一轮投票选举新的主节点，选举会富裕一个单调递增的 epoch 号。如果有两个 epoch 号，则具有更高 epoch 号码的主节点将获胜。
• 相反，它必须从 quorum节点中收集投票。主节点如果想要做出某个决定，须将提议发送给其他所有节点，等待 qu or u m节点的响应。 quorum通常(但不总是)由多数节点组成。井且，只有当没有发现更高epoch主节 点存在时，节点才会对当前的提议(带有 epoch号码)进行投票。
• 多数共识算在是假定一组固定参与投票的 节点集，这意味 着 不能动态、添加或删除节点 。 动态成员资格的扩展特性可以在集群中的按需调整节点数，但相 比于静态的成员组成，其理解程度和接受程度要低很多。

成员与协调服务

• ZooKeeper或etcd这样的项目通常称为“分布式键值存储”或“协调与配置服务” 。 从它们对外提供服务的API来看则与数据库非常相像: 读取、写入对应主键的值，或者遍历主键。
• ZooKeeper和etcd主要针对保存少量、可完全载入内存的数据(虽然它们最终仍要写入磁盘以支持持久性)而设计，所以不要用它们保存大量的数据。它们通常采用容错 的全序广播算住在所有节点上复制这些数据从而实现高可靠。
• 全序广播主要用来实现数据库复制 :每条消息代表的是数据库写请求，然后按照相同的 顺序在多个节点上应用写操作，从而达到多副本之间的一致性。
• Zookeeper 几个操作
  • 线性化的原子操作
    • 使用原子比较-设置操作，可以实现加锁服务。例如如果多个节点同时尝试执行 相同的操作，则确保其中只有一个会成功。
    • 共识协议保证了操作满足原子性和线 性化，即使某些节点发生放障或网络随时被中断。
    • 分布式锁通常实现为 一个带有 到期时间的租约，这样万 一 某些客户端发生故障，可以最终释放锁。
  • 操作全序
    • 当资源被锁或者租约保护肘，需要 fencing令牌 来防止某些客户端由于发生进程暂停而引起锁冲突。 fencing令牌确保每次加 锁时数字总是单调增加。
    • ZooKeeper在实现该功能时，采用了对所有操作执行 全局排序，然后为每个操作都赋予一个单调递增的事务 ID (zxid )和版本号（cversion）。
  • 故障检测
    • 客户端与 ZooKeeper节点维护一个长期会话，客户端会周期性 地 与 ZooKeeper服 务节点互相交换心跳信息，以检查对方是否存活。
    • 即使连接出现闪断，或者某 个ZooKeeper节点发生失效，会话仍处于活动状态。但是，如果长时间心跳停止 且超过了会话超时设置， ZooKeeper会声明会话失败。
    • 此时，所有该会话持有的锁资源可以配置为自动全部释放(ZooKeeper称之为ephemeral nodes即临时节点)。
  • 更改通知
    • 客户端不仅可以读取其他客户端所创建的锁和键值，还可以监视它们的变化 。因 此，客户端可以知道其他客户端何时加入了集群(基于它写入 ZooKeeper的值) 以及客户端是否发生了故障(会 i舌超时导致节点消失)。
    • 通过订阅通知机制，客 户端不需要频繁地轮询服务即可知道感兴趣对象的变化情况。

服务发现

• ZooKeeper、 etcd和Consul还经常用于服务发现。 例如需要某项服务肘， 应该连接 到哪个IP地址等。
• 即使服务发现不需要共识，但主节点选举则肯定需要。因此，如果共识系统已经明确 知道哪一个是主节点，那它可以利用这些信息来帮助次级服务来发现各自的主节点。
• 成员服务用来确定当前|哪些节点处于活动状态井属于集群的有效成员。由于无限的网络延迟，无陆可靠地检测一个节点究竟是否发生了故障。 但是，可以将故障检测与共识绑定在一起，让所有节点就节点的存活达成一致意见。