DDIA

发表于 | 分类于

第一部分：数据系统的基石

第一章： 可靠性，可伸缩性，可维护性

数据密集型应用：

  1. 关键在于数据量，数据复杂度，及数据的快速多变性
  2. 基于标准模块构成，包含：数据库，高速缓存，索引，流式处理，批处理
  3. 三个问题：
    1. 可靠性：系统在 困境（比如硬件故障、软件故障、人为错误）中仍可正常工作（正确完成功能，并能达到期望的性能水准）
    2. 可扩展性：有合理的办法应对系统的增长（数据量、流量、复杂性）
    3. 可维护性：许多不同的人（工程师、运维）在不同的生命周期，都能高效地在系统上工作（使系统保持现有行为，并适应新的应用场景）

可靠性

造成错误的原因叫做 故障（fault），能预料并应对故障的系统特性可称为 容错（fault-tolerant） 或 韧性（resilient）

注意 故障（fault） 不同于 失效（failure）。故障 通常定义为系统的一部分状态偏离其标准，而 失效 则是系统作为一个整体停止向用户提供服务

硬件故障

增加单个硬件的冗余度

如果在硬件冗余的基础上进一步引入软件容错机制，那么系统在容忍整个（单台）机器故障的道路上就更进一步了

软件错误

我们通常认为硬件故障是随机的、相互独立的：一台机器的磁盘失效并不意味着另一台机器的磁盘也会失效

另一类错误是内部的 系统性错误（systematic error）【8】。这类错误难以预料，而且因为是跨节点相关的，所以比起不相关的硬件故障往往可能造成更多的 系统失效

仔细考虑系统中的假设和交互；彻底的测试；进程隔离；允许进程崩溃并重启；测量、监控并分析生产环境中的系统行为

人为错误

人类也是不可靠的，运维配置错误是导致服务中断的首要原因，而硬件故障（服务器或网络）仅导致了 10-25% 的服务中断

最好的系统会组合使用以下几种办法：

以最小化犯错机会的方式设计系统

将人们最容易犯错的地方与可能导致失效的地方 解耦（decouple）

在各个层次进行彻底的测试【3】，从单元测试、全系统集成测试到手动测试。

允许从人为错误中简单快速地恢复，以最大限度地减少失效情况带来的影响

配置详细和明确的监控，比如性能指标和错误率

良好的管理实践与充分的培训

可伸缩性

描述负载

负载参数的最佳选择取决于系统架构，它可能是每秒向 Web 服务器发出的请求、数据库中的读写比率、聊天室中同时活跃的用户数量、缓存命中率或其他东西。除此之外，也许平均情况对你很重要，也许你的瓶颈是少数极端场景。

twitter发布推文和主页时间线的例子中，每个用户粉丝数的分布（可能按这些用户的发推频率来加权）是探讨可伸缩性的一个关键负载参数，因为它决定了扇出负载。

扇出：在事务处理系统中，我们使用它来描述为了服务一个传入请求而需要执行其他服务的请求数量。

描述性能

从两种角度看负载参数增加时会发生什么：

  1. 增加负载参数并保持系统资源（CPU、内存、网络带宽等）不变时，系统性能将受到什么影响？

  2. 增加负载参数并希望保持性能不变时，需要增加多少系统资源？

吞吐量、 响应时间

延迟（latency） 和 响应时间（response time） 经常用作同义词，但实际上它们并不一样。响应时间是客户所看到的，除了实际处理请求的时间（ 服务时间（service time） ）之外，还包括网络延迟和排队延迟。延迟是某个请求等待处理的 持续时长，在此期间它处于 休眠（latent） 状态，并等待服务

通常使用 百分位点（percentiles） 描述响应时间，如p50， p99

响应时间的高百分位点（也称为 尾部延迟，即 tail latencies）非常重要，因为它们直接影响用户的服务体验

百分位点通常用于 服务级别目标（SLO, service level objectives） 和 服务级别协议（SLA, service level agreements），即定义服务预期性能和可用性的合同。 SLA 可能会声明，如果服务响应时间的中位数小于 200 毫秒，且 99.9 百分位点低于 1 秒，则认为服务工作正常

排队延迟（queueing delay） 通常占了高百分位点处响应时间的很大一部分。由于服务器只能并行处理少量的事务（如受其 CPU 核数的限制），所以只要有少量缓慢的请求就能阻碍后续请求的处理，这种效应有时被称为 头部阻塞（head-of-line blocking）

应对负载的方法

纵向和横向伸缩结合

跨多台机器部署 无状态服务（stateless services） 非常简单，但将带状态的数据系统从单节点变为分布式配置则可能引入许多额外复杂度。出于这个原因，常识告诉我们应该将数据库放在单个节点上（纵向伸缩），直到伸缩成本或可用性需求迫使其改为分布式。随着分布式系统的工具和抽象越来越好，至少对于某些类型的应用而言，这种常识可能会改变

一个良好适配应用的可伸缩架构，是围绕着 假设（assumption） 建立的：哪些操作是常见的？哪些操作是罕见的？这就是所谓负载参数。如果假设最终是错误的，那么为伸缩所做的工程投入就白费了，最糟糕的是适得其反

可维护性

软件的大部分开销并不在最初的开发阶段，而是在持续的维护阶段，包括修复漏洞、保持系统正常运行、调查失效、适配新的平台、为新的场景进行修改、偿还技术债、添加新的功能等等。

在设计之初就尽量考虑尽可能减少维护期间的痛苦，从而避免自己的软件系统变成遗留系统。为此，我们将特别关注软件系统的三个设计原则：

  • 可操作性（Operability）便于运维团队保持系统平稳运行。
  • 简单性（Simplicity）从系统中消除尽可能多的 复杂度（complexity），使新工程师也能轻松理解系统（注意这和用户接口的简单性不一样）。
  • 可演化性（evolvability）使工程师在未来能轻松地对系统进行更改，当需求变化时为新应用场景做适配。也称为 可伸缩性（extensibility）、可修改性（modifiability） 或 可塑性（plasticity）。

可操作性：人生苦短，关爱运维

简单性：管理复杂度

复杂度（complexity） 有各种可能的症状，例如：状态空间激增、模块间紧密耦合、纠结的依赖关系、不一致的命名和术语、解决性能问题的 Hack、需要绕开的特例等等

因为复杂度导致维护困难时，预算和时间安排通常会超支。在复杂的软件中进行变更，引入错误的风险也更大：当开发人员难以理解系统时，隐藏的假设、无意的后果和意外的交互就更容易被忽略。相反，降低复杂度能极大地提高软件的可维护性，因此简单性应该是构建系统的一个关键目标。

简化系统并不一定意味着减少功能；它也可以意味着消除 额外的（accidental） 的复杂度。 Moseley 和 Marks【32】把 额外复杂度 定义为：由具体实现中涌现，而非（从用户视角看，系统所解决的）问题本身固有的复杂度。

用于消除 额外复杂度 的最好工具之一是 抽象（abstraction）。

可演化性：拥抱变化

修改数据系统并使其适应不断变化需求的容易程度，是与 简单性 和 抽象性 密切相关的：简单易懂的系统通常比复杂系统更容易修改。

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

关系模型与文档模型

数据被组织成 关系（SQL 中称作 表），其中每个关系是 元组（SQL 中称作 行) 的无序集合。

NoSQL 的诞生

采用 NoSQL 数据库的背后有几个驱动因素，其中包括：

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

在可预见的未来，关系数据库似乎可能会继续与各种非关系数据库一起使用 - 这种想法有时也被称为 混合持久化（polyglot persistence）。

对象关系不匹配

目前大多数应用程序开发都使用面向对象的编程语言来开发，这导致了对 SQL 数据模型的普遍批评：如果数据存储在关系表中，那么需要一个笨拙的转换层，处于应用程序代码中的对象和表，行，列的数据库模型之间。模型之间的不连贯有时被称为 阻抗不匹配（impedance mismatch）

对象关系映射（ORM object-relational mapping） 框架可以减少这个转换层所需的样板代码的数量，但是它们不能完全隐藏这两个模型之间的差异

简历的例子说明了从用户到职位、教育、和联系这些信息之间存在一对多的关系，可以用多种方式来表示：

  1. 传统 SQL 模型（SQL：1999 之前）中，最常见的规范化表示形式是将职位，教育和联系信息放在单独的表中，对 User 表提供外键引用

  2. 后续的 SQL 标准增加了对结构化数据类型和 XML 数据的支持；这允许将多值数据存储在单行内，并支持在这些文档内查询和索引

  3. 第三种选择是将职业，教育和联系信息编码为 JSON 或 XML 文档，将其存储在数据库的文本列中，并让应用程序解析其结构和内容。这种配置下，通常不能使用数据库来查询该编码列中的值

多对一和多对多的关系

存储 ID 还是文本字符串，这是个 副本（duplication） 问题。

去除此类重复是数据库 规范化（normalization） 的关键思想

一个经验法则是，如果重复存储了可以存储在一个地方的值，则模式就不是 规范化（normalized） 的。

不幸的是，对这些数据进行规范化需要多对一的关系（许多人生活在一个特定的地区，许多人在一个特定的行业工作），这与文档模型不太吻合。在关系数据库中，通过 ID 来引用其他表中的行是正常的，因为连接很容易。在文档数据库中，一对多树结构没有必要用连接，对连接的支持通常很弱

此外，即便应用程序的最初版本适合无连接的文档模型，随着功能添加到应用程序中，数据会变得更加互联（多对多）

文档数据库是否在重蹈覆辙

在多对多的关系和连接已常规用在关系数据库时，文档数据库和 NoSQL 重启了辩论：如何以最佳方式在数据库中表示多对多关系

解决IMS层次模型限制的两种模型：关系模型和网状模型

与文档数据库的对比：外键与文档引用

关系型数据库与文档数据库在今日的对比

支持文档数据模型的主要论据是架构灵活性，因局部性而拥有更好的性能，以及对于某些应用程序而言更接近于应用程序使用的数据结构。关系模型通过为连接提供更好的支持以及支持多对一和多对多的关系来反击。

哪种数据模型更有助于简化应用代码

如果应用程序中的数据具有类似文档的结构（即，一对多关系树，通常一次性加载整个树），那么使用文档模型可能是一个好主意

文档模型有一定的局限性：例如，不能直接引用文档中的嵌套的项目，而是需要说 “用户 251 的位置列表中的第二项”（很像层次模型中的访问路径）。但是，只要文件嵌套不太深，这通常不是问题

文档数据库对连接的糟糕支持可能是个问题，也可能不是问题，这取决于应用程序

但如果你的应用程序确实会用到多对多关系，那么文档模型就没有那么诱人了。尽管可以通过反规范化来消除对连接的需求，但这需要应用程序代码来做额外的工作以确保数据一致性。尽管应用程序代码可以通过向数据库发出多个请求的方式来模拟连接，但这也将复杂性转移到应用程序中，而且通常也会比由数据库内的专用代码更慢。在这种情况下，使用文档模型可能会导致更复杂的应用代码与更差的性能

我们没有办法说哪种数据模型更有助于简化应用代码，因为它取决于数据项之间的关系种类。对高度关联的数据而言，文档模型是极其糟糕的，关系模型是可以接受的，而选用图形模型

文档模型中的模式灵活性

读时模式：数据的结构是隐含的，只有在数据被读取时才被解释

写时模式：传统的关系数据库方法中，模式明确，且数据库确保所有的数据都符合其模式

当由于某种原因（例如，数据是异构的）集合中的项目并不都具有相同的结构时，读时模式更具优势。例如，如果：

  • 存在许多不同类型的对象，将每种类型的对象放在自己的表中是不现实的。
  • 数据的结构由外部系统决定。你无法控制外部系统且它随时可能变化。
查询的数据局部性

如果应用程序经常需要访问整个文档（例如，将其渲染至网页），那么存储局部性会带来性能优势

局部性仅仅适用于同时需要文档绝大部分内容的情况。数据库通常需要加载整个文档，即使只访问其中的一小部分，这对于大型文档来说是很浪费的。更新文档时，通常需要整个重写。只有不改变文档大小的修改才可以容易地原地执行。因此，通常建议保持相对小的文档，并避免增加文档大小的写入。这些性能限制大大减少了文档数据库的实用场景。

值得指出的是，为了局部性而分组集合相关数据的想法并不局限于文档模型

文档和关系数据库的融合

自 2000 年代中期以来，大多数关系数据库系统（MySQL 除外）都已支持 XML。这包括对 XML 文档进行本地修改的功能，以及在 XML 文档中进行索引和查询的功能。这允许应用程序使用那种与文档数据库应当使用的非常类似的数据模型。

从 9.3 版本开始的 PostgreSQL 【8】，从 5.7 版本开始的 MySQL 以及从版本 10.5 开始的 IBM DB2【30】也对 JSON 文档提供了类似的支持级别。

随着时间的推移，关系数据库和文档数据库似乎变得越来越相似

关系模型和文档模型的混合是未来数据库一条很好的路线。

数据查询语言

SQL 命令式查询语言（好）

IMS和CODASYL 使用命令式查询语言（不好）

web上的声明式查询，举例说明声明式查询的优势

MapReduce 查询

mongoDB

图数据模型

多对多关系是不同数据模型之间具有区别性的重要特征

如果你的应用程序大多数的关系是一对多关系（树状结构化数据），或者大多数记录之间不存在关系，那么使用文档模型是合适的

关系模型可以处理多对多关系的简单情况，但是随着数据之间的连接变得更加复杂，将数据建模为图形显得更加自然

一个图由两种对象组成：顶点（vertices，也称为 节点，即 nodes，或 实体，即 entities），和 边（edges，也称为 关系，即 relationships，或 弧，即 arcs）。多种数据可以被建模为一个图形。如社交图谱、网络图谱、公路或铁路网络。

图提供了一种一致的方式，用来在单个数据存储中存储完全不同类型的对象

来自爱达荷州的 Lucy 和来自法国 Beaune 的 Alain。他们已婚，住在伦敦。（例子）

有几种不同但相关的方法用来构建和查询图表中的数据。在本节中，我们将讨论属性图模型（由 Neo4j，Titan 和 InfiniteGraph 实现）和三元组存储（triple-store）模型（由 Datomic，AllegroGraph 等实现）。我们将查看图的三种声明式查询语言：Cypher，SPARQL 和 Datalog。除此之外，还有像 Gremlin 这样的图形查询语言和像 Pregel 这样的图形处理框架

属性图

在属性图模型中，每个顶点（vertex）包括：

  • 唯一的标识符
  • 一组出边（outgoing edges）
  • 一组入边（ingoing edges）
  • 一组属性（键值对）

每条边（edge）包括：

  • 唯一标识符
  • 边的起点（尾部顶点，即 tail vertex）
  • 边的终点（头部顶点，即 head vertex）
  • 描述两个顶点之间关系类型的标签
  • 一组属性（键值对）

关于这个模型的一些重要方面是：

1.任何顶点都可以有一条边连接到任何其他顶点。没有模式限制哪种事物可不可以关联。

2.给定任何顶点，可以高效地找到它的入边和出边，从而遍历图，即沿着一系列顶点的路径前后移动

3.通过对不同类型的关系使用不同的标签，可以在一个图中存储几种不同的信息，同时仍然保持一个清晰的数据模型。

这些特性为数据建模提供了很大的灵活性

Cypher 查询语言

Cypher 是属性图的声明式查询语言，为 Neo4j 图形数据库而发明

SQL 中的图查询

三元组存储和 SPARQL

在三元组存储中，所有信息都以非常简单的三部分表示形式存储（主语，谓语，宾语）

三元组的主语相当于图中的一个顶点。而宾语是下面两者之一：

  1. 原始数据类型中的值，例如字符串或数字。在这种情况下，三元组的谓语和宾语相当于主语顶点上的属性的键和值

  2. 图中的另一个顶点。在这种情况下，谓语是图中的一条边，主语是其尾部顶点，而宾语是其头部顶点

SPARQL 查询语言

SPARQL 是一种用于三元组存储的面向 RDF 数据模型的查询语言

基础：Datalog

第三章：存储与检索

驱动数据库的数据结构

两大类存储引擎：日志结构（log-structured） 的存储引擎，以及 面向页面（page-oriented） 的存储引擎（例如 B 树）。

这是存储系统中一个重要的权衡：精心选择的索引加快了读查询的速度，但是每个索引都会拖慢写入速度

散列索引

内存和磁盘中的散列索引：要求所有的键必须能放入可用内存中

日志段和压缩：段被写入后永远不会被修改，所以合并的段被写入一个新的文件

需要考虑的问题：文件格式、删除记录、崩溃恢复、部分写入记录、并发控制

仅追加的日志设计好处：

  1. 追加和分段合并都是顺序写入操作，通常比随机写入快得多，尤其是在磁性机械硬盘上

  2. 如果段文件是仅追加的或不可变的，并发和崩溃恢复就简单多了

  3. 合并旧段的处理也可以避免数据文件随着时间的推移而碎片化的问题

散列表索引也有其局限性：

  1. 散列表必须能放进内存：原则上可以在硬盘上维护一个散列映射，不幸的是硬盘散列映射很难表现优秀
  2. 范围查询效率不高

SSTables和LSM树

要求键值对的序列按键排序，这个格式称为 排序字符串表（Sorted String Table），简称 SSTable

每个键只在每个合并的段文件中出现一次（压缩过程已经保证）

与使用散列索引的日志段相比，SSTable 有几个大的优势：

  1. 即使文件大于可用内存，合并段的操作仍然是简单而高效的（归并排序）
  2. 为了在文件中找到一个特定的键，你不再需要在内存中保存所有键的索引（稀疏内存索引）
  3. 由于读取请求无论如何都需要扫描所请求范围内的多个键值对，因此可以将这些记录分组为块（block），并在将其写入硬盘之前对其进行压缩 。稀疏内存索引中的每个条目都指向压缩块的开始处。除了节省硬盘空间之外，压缩还可以减少对 I/O 带宽的使用。
构建和维护sstables
  1. 有新写入时，将其添加到内存中的平衡树数据结构（例如红黑树）。这个内存树有时被称为 内存表（memtable）。
  2. 当 内存表 大于某个阈值（通常为几兆字节）时，将其作为 SSTable 文件写入硬盘
  3. 收到读取请求时，首先尝试在内存表中找到对应的键，如果没有就在最近的硬盘段中寻找，如果还没有就在下一个较旧的段中继续寻找，以此类推。
  4. 时不时地，在后台运行一个合并和压缩过程，以合并段文件并将已覆盖或已删除的值丢弃掉。

这个方案效果很好。它只会遇到一个问题：如果数据库崩溃，则最近的写入（在内存表中，但尚未写入硬盘）将丢失。为了避免这个问题，我们可以在硬盘上保存一个单独的日志，每个写入都会立即被追加到这个日志上，就像在前面的章节中所描述的那样。这个日志没有按排序顺序，但这并不重要，因为它的唯一目的是在崩溃后恢复内存表。每当内存表写出到 SSTable 时，相应的日志都可以被丢弃。

基于这种合并和压缩排序文件原理的存储引擎通常被称为 LSM 存储引擎。

全文索引比键值索引复杂得多，但是基于类似的想法：在搜索查询中给出一个单词，找到提及单词的所有文档（网页，产品描述等）。这是通过键值结构实现的，其中键是单词（或 词语，即 term），值是所有包含该单词的文档的 ID 列表（记录列表）。在 Lucene 中，从词语到记录列表的这种映射保存在类似于 SSTable 的有序文件中，并根据需要在后台合并【14】。

性能优化

布隆过滤器，优化不存在的键的查找

size-tiered 和 leveled compaction：确定 SSTables 被压缩和合并的顺序和时间的策略

LevelDB 和 RocksDB 使用 leveled compaction（LevelDB 因此得名），HBase 使用 size-tiered，Cassandra 同时支持这两种。对于 sized-tiered，较新和较小的 SSTables 相继被合并到较旧的和较大的 SSTable 中。对于 leveled compaction，key 范围被拆分到较小的 SSTables，而较旧的数据被移动到单独的层级（level），这使得压缩（compaction）能够更加增量地进行，并且使用较少的硬盘空间。

即使有许多微妙的东西，LSM 树的基本思想 —— 保存一系列在后台合并的 SSTables —— 简单而有效。即使数据集比可用内存大得多，它仍能继续正常工作。由于数据按排序顺序存储，你可以高效地执行范围查询（扫描所有从某个最小值到某个最大值之间的所有键），并且因为硬盘写入是连续的，所以 LSM 树可以支持非常高的写入吞吐量。

B树

B 树保持按键排序的键值对，这允许高效的键值查找和范围查询，但与LSM有非常不同的设计理念

B 树将数据库分解成固定大小的块（block）或页面（page），传统上大小为 4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为硬盘空间也是按固定大小的块来组织的。

每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面 —— 类似于指针，但在硬盘而不是在内存中。

B树是使用这些页面引用构建的一个页面树，其中一个页面会被指定为 B 树的根；该页面包含几个键和对子页面的引用。每个子页面负责一段连续范围的键，引用之间的键，指明了引用子页面的键范围。

img

最终，我们将到达某个包含单个键的页面（叶子页面，leaf page），该页面或者直接包含每个键的值，或者包含了对可以找到值的页面的引用。

在 B 树的一个页面中对子页面的引用的数量称为分支因子。分支因子取决于存储页面引用和范围边界所需的空间量，但通常是几百个

如果要更新 B 树中现有键的值，需要搜索包含该键的叶子页面，更改该页面中的值，并将该页面写回到硬盘（对该页面的任何引用都将保持有效）。如果你想添加一个新的键，你需要找到其范围能包含新键的页面，并将其添加到该页面。如果页面中没有足够的可用空间容纳新键，则将其分成两个半满页面，并更新父页面以反映新的键范围分区

大多数数据库可以放入一个三到四层的 B 树，所以你不需要追踪多个页面引用来找到你正在查找的页面

（分支因子为 500 的 4KB 页面的四层树可以存储多达 256TB 的数据）

让B树更可靠

B 树的基本底层写操作是用新数据覆写硬盘上的页面，并假定覆写不改变页面的位置：即，当页面被覆写时，对该页面的所有引用保持完整。这与日志结构索引（如 LSM 树）形成鲜明对比，后者只追加到文件（并最终删除过时的文件），但从不修改文件中已有的内容。

你可以把覆写硬盘上的页面对应为实际的硬件操作。在磁性硬盘驱动器上，这意味着将磁头移动到正确的位置，等待旋转盘上的正确位置出现，然后用新的数据覆写适当的扇区。在固态硬盘上，由于 SSD 必须一次擦除和重写相当大的存储芯片块，所以会发生更复杂的事情。

而且，一些操作需要覆写几个不同的页面。例如，如果因为插入导致页面过满而拆分页面，则需要写入新拆分的两个页面，并覆写其父页面以更新对两个子页面的引用。这是一个危险的操作，因为如果数据库在仅有部分页面被写入时崩溃，那么最终将导致一个损坏的索引（例如，可能有一个孤儿页面不是任何父项的子项） 。

为了使数据库能处理异常崩溃的场景，B 树实现通常会带有一个额外的硬盘数据结构：预写式日志（WAL，即 write-ahead log，也称为 重做日志，即 redo log）。这是一个仅追加的文件，每个 B 树的修改在其能被应用到树本身的页面之前都必须先写入到该文件。当数据库在崩溃后恢复时，这个日志将被用来使 B 树恢复到一致的状态【5,20】。

另外还有一个更新页面的复杂情况是，如果多个线程要同时访问 B 树，则需要仔细的并发控制 —— 否则线程可能会看到树处于不一致的状态。这通常是通过使用 锁存器（latches，轻量级锁）保护树的数据结构来完成。日志结构化的方法在这方面更简单，因为它们在后台进行所有的合并，而不会干扰新接收到的查询，并且能够时不时地将旧的段原子交换为新的段。

B树的优化

  1. 一些数据库（如 LMDB）使用写时复制方案，而不是覆盖页面并维护 WAL 以支持崩溃恢复。

  2. 通过不存储整个键，而是缩短其大小，来节省页面空间。

  3. 通常，页面可以放置在硬盘上的任何位置；没有什么要求相邻键范围的页面也放在硬盘上相邻的区域。如果某个查询需要按照排序顺序扫描大部分的键范围，那么这种按页面存储的布局可能会效率低下，因为每次页面读取可能都需要进行硬盘查找。因此，许多 B 树的实现在布局树时会尽量使叶子页面按顺序出现在硬盘上。但是，随着树的增长，要维持这个顺序是很困难的。相比之下，由于 LSM 树在合并过程中一次又一次地重写存储的大部分，所以它们更容易使顺序键在硬盘上彼此靠近。

  4. 额外的指针已被添加到树中。例如，每个叶子页面可以引用其左边和右边的兄弟页面，使得不用跳回父页面就能按顺序对键进行扫描。

  5. B 树的变体如分形树（fractal tree）借用一些日志结构的思想来减少硬盘查找（而且它们与分形无关）。

比较B树和LSM树

根据经验，通常 LSM 树的写入速度更快，而 B 树的读取速度更快。 LSM 树上的读取通常比较慢，因为它们必须检查几种不同的数据结构和不同压缩（Compaction）层级的 SSTables。然而，基准测试的结果通常和工作负载的细节相关。你需要用你特有的工作负载来测试系统，以便进行有效的比较。

LSM 优点

B 树索引中的每块数据都必须至少写入两次：一次写入预先写入日志（WAL），一次写入树页面本身（如果有分页还需要再写入一次）。即使在该页面中只有几个字节发生了变化，也需要接受写入整个页面的开销。有些存储引擎甚至会覆写同一个页面两次，以免在电源故障的情况下导致页面部分更新【24,25】。

由于反复压缩和合并 SSTables，日志结构索引也会多次重写数据。这种影响 —— 在数据库的生命周期中每次写入数据库导致对硬盘的多次写入 —— 被称为 写放大（write amplification）。需要特别注意的是固态硬盘，固态硬盘的闪存寿命在覆写有限次数后就会耗尽。

在写入繁重的应用程序中，性能瓶颈可能是数据库可以写入硬盘的速度。在这种情况下，写放大会导致直接的性能代价：存储引擎写入硬盘的次数越多，可用硬盘带宽内它能处理的每秒写入次数就越少。

而且，LSM 树通常能够比 B 树支持更高的写入吞吐量，部分原因是它们有时具有较低的写放大（尽管这取决于存储引擎的配置和工作负载），部分是因为它们顺序地写入紧凑的 SSTable 文件而不是必须覆写树中的几个页面【26】。这种差异在磁性硬盘驱动器上尤其重要，其顺序写入比随机写入要快得多。

LSM 树可以被压缩得更好，因此通常能比 B 树在硬盘上产生更小的文件。B 树存储引擎会由于碎片化（fragmentation）而留下一些未使用的硬盘空间：当页面被拆分或某行不能放入现有页面时，页面中的某些空间仍未被使用。由于 LSM 树不是面向页面的，并且会通过定期重写 SSTables 以去除碎片，所以它们具有较低的存储开销，特别是当使用分层压缩（leveled compaction）时【27】。

在许多固态硬盘上，固件内部使用了日志结构化算法，以将随机写入转变为顺序写入底层存储芯片，因此存储引擎写入模式的影响不太明显【19】。但是，较低的写入放大率和减少的碎片仍然对固态硬盘更有利：更紧凑地表示数据允许在可用的 I/O 带宽内处理更多的读取和写入请求

LSM 缺点

日志结构存储的缺点是压缩过程有时会干扰正在进行的读写操作。尽管存储引擎尝试增量地执行压缩以尽量不影响并发访问，但是硬盘资源有限，所以很容易发生某个请求需要等待硬盘先完成昂贵的压缩操作。对吞吐量和平均响应时间的影响通常很小，但是日志结构化存储引擎在更高百分位的响应时间有时会相当长，而 B 树的行为则相对更具可预测性。

压缩的另一个问题出现在高写入吞吐量时：硬盘的有限写入带宽需要在初始写入（记录日志和刷新内存表到硬盘）和在后台运行的压缩线程之间共享。写入空数据库时，可以使用全硬盘带宽进行初始写入，但数据库越大，压缩所需的硬盘带宽就越多。

如果写入吞吐量很高，并且压缩没有仔细配置好，有可能导致压缩跟不上写入速率。在这种情况下，硬盘上未合并段的数量不断增加，直到硬盘空间用完，读取速度也会减慢，因为它们需要检查更多的段文件。通常情况下，即使压缩无法跟上，基于 SSTable 的存储引擎也不会限制传入写入的速率，所以你需要进行明确的监控来检测这种情况【29,30】。

B 树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。这个方面使得 B 树在想要提供强大的事务语义的数据库中很有吸引力：在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在 B 树索引中，这些锁可以直接附加到树上【5】。在 第七章 中，我们将更详细地讨论这一点。

B 树在数据库架构中是非常根深蒂固的，为许多工作负载都提供了始终如一的良好性能，所以它们不可能很快就会消失。在新的数据存储中，日志结构化索引变得越来越流行。没有快速和容易的规则来确定哪种类型的存储引擎对你的场景更好，所以值得去通过一些测试来得到相关的经验。

其他索引结构

次级索引主要的不同是键不是唯一的，即可能有许多行（文档，顶点）具有相同的键。这可以通过两种方式来解决：或者将匹配行标识符的列表作为索引里的值（就像全文索引中的记录列表），或者通过向每个键添加行标识符来使键唯一。无论哪种方式，B 树和日志结构索引都可以用作次级索引。

将值存储在索引中

索引中的键是查询要搜索的内容，而其值可以是以下两种情况之一：它可以是实际的行（文档，顶点），也可以是对存储在别处的行的引用。在后一种情况下，行被存储的地方被称为 堆文件（heap file），并且存储的数据没有特定的顺序。堆文件方法很常见，因为它避免了在存在多个次级索引时对数据的复制：每个索引只引用堆文件中的一个位置，实际的数据都保存在一个地方。

在不更改键的情况下更新值时，堆文件方法可以非常高效：只要新值的字节数不大于旧值，就可以覆盖该记录。如果新值更大，情况会更复杂，因为它可能需要移到堆中有足够空间的新位置。在这种情况下，要么所有的索引都需要更新，以指向记录的新堆位置，或者在旧堆位置留下一个转发指针

在某些情况下，从索引到堆文件的额外跳跃对读取来说性能损失太大，因此可能希望将被索引的行直接存储在索引中。这被称为聚集索引（clustered index）

在 聚集索引（在索引中存储所有的行数据）和 非聚集索引（仅在索引中存储对数据的引用）之间的折衷被称为 覆盖索引（covering index） 或 包含列的索引（index with included columns），其在索引内存储表的一部分列，这允许通过单独使用索引来处理一些查询

与任何类型的数据重复一样，聚集索引和覆盖索引可以加快读取速度，但是它们需要额外的存储空间，并且会增加写入开销。数据库还需要额外的努力来执行事务保证，因为应用程序不应看到任何因为重复而导致的不一致。

多列索引

最常见的多列索引被称为 连接索引（concatenated index） ，它通过将一列的值追加到另一列后面，简单地将多个字段组合成一个键（索引定义中指定了字段的连接顺序）

多维索引（multi-dimensional index） 是一种查询多个列的更一般的方法，这对于地理空间数据尤为重要（经度、纬度）。一个标准的 B 树或者 LSM 树索引不能够高效地处理这种查询，一种选择是使用空间填充曲线将二维位置转换为单个数字，然后使用常规 B 树索引【34】。更普遍的是，使用特殊化的空间索引，例如 R 树。

全文搜索和模糊索引

lucense

在内存中存储一切

内存数据库 + 持久化

反直觉的是，内存数据库的性能优势并不是因为它们不需要从硬盘读取的事实。只要有足够的内存即使是基于硬盘的存储引擎也可能永远不需要从硬盘读取，因为操作系统在内存中缓存了最近使用的硬盘块。相反，它们更快的原因在于省去了将内存数据结构编码为硬盘数据结构的开销

内存数据库的另一个有趣的地方是提供了难以用基于硬盘的索引实现的数据模型。例如，Redis 为各种数据结构（如优先级队列和集合）提供了类似数据库的接口

所谓的 反缓存（anti-caching） 方法通过在内存不足的情况下将最近最少使用的数据从内存转移到硬盘，并在将来再次访问时将其重新加载到内存中。这与操作系统对虚拟内存和交换文件的操作类似，但数据库可以比操作系统更有效地管理内存，因为它可以按单个记录的粒度工作，而不是整个内存页面。尽管如此，这种方法仍然需要索引能完全放入内存中

如果 非易失性存储器（non-volatile memory, NVM） 技术得到更广泛的应用，可能还需要进一步改变存储引擎设计

事务处理还是分析

应用程序通常使用索引通过某个键查找少量记录。根据用户的输入插入或更新记录。由于这些应用程序是交互式的，这种访问模式被称为 在线事务处理（OLTP, OnLine Transaction Processing）。

通常，分析查询需要扫描大量记录，每个记录只读取几列，并计算汇总统计信息（如计数、总和或平均值），而不是将原始数据返回给用户，称为 在线分析处理（OLAP, OnLine Analytice Processing）

数据仓库

数据仓库的数据模型通常是关系型的，因为 SQL 通常很适合分析查询

星型和雪花型：分析的模式

许多数据仓库都以相当公式化的方式使用，被称为星型模式（也称为维度建模）。在模式的中心是一个所谓的事实表，事实表的每一行代表在特定时间发生的事件。事实表中的一些列是属性，事实表中的其他列是对其他表（称为维度表）的外键引用。

“星型模式” 这个名字来源于这样一个事实，即当我们对表之间的关系进行可视化时，事实表在中间，被维度表包围；与这些表的连接就像星星的光芒。

这个模板的变体被称为雪花模式，其中维度被进一步分解为子维度

列式存储

列式存储背后的想法很简单：不要将所有来自一行的值存储在一起，而是将来自每一列的所有值存储在一起。如果每个列式存储在一个单独的文件中，查询只需要读取和解析查询中使用的那些列，这可以节省大量的工作。

列式存储布局依赖于每个列文件包含相同顺序的行

列压缩

列式存储通常很适合压缩，如位图编码

列式存储和列族

Cassandra 和 HBase 有一个列族（column families）的概念，他们从 Bigtable 继承【9】。然而，把它们称为列式（column-oriented）是非常具有误导性的：在每个列族中，它们将一行中的所有列与行键一起存储，并且不使用列压缩。因此，Bigtable 模型仍然主要是面向行的。

内存带宽和矢量化处理

对于需要扫描数百万行的数据仓库查询来说，一个巨大的瓶颈是从硬盘获取数据到内存的带宽

分析型数据库的开发人员还需要有效地利用主存储器到 CPU 缓存的带宽，避免 CPU 指令处理流水线中的分支预测错误和气泡，以及在现代 CPU 上使用单指令多数据（SIMD）指令

除了减少需要从硬盘加载的数据量以外，列式存储布局也可以有效利用 CPU 周期

列式存储中的排序顺序

注：考虑每个列文件中包含相同顺序的行

排序顺序的另一个好处是它可以帮助压缩列。如果主要排序列没有太多个不同的值，那么在排序之后，它将具有很长的序列，其中相同的值连续重复多次。一个简单的游程编码可以将该列压缩到几千字节 —— 即使表中有数十亿行。

第一个排序键的压缩效果最强。第二和第三个排序键会更混乱，因此不会有这么长的连续的重复值

几个不同的排序顺序

在副本上使用不同的排序顺序，在查询时可以选择最合适的副本。

在一个列式存储中有多个排序顺序有点类似于在一个面向行的存储中有多个次级索引。但最大的区别在于面向行的存储将每一行保存在一个地方（在堆文件或聚集索引中），次级索引只包含指向匹配行的指针。在列式存储中，通常在其他地方没有任何指向数据的指针，只有包含值的列。

写入列式存储

使用 B 树的就地更新方法对于压缩的列是不可能的。如果你想在排序表的中间插入一行，你很可能不得不重写所有的列文件。由于行由列中的位置标识，因此插入必须对所有列进行一致地更新。

前面已经看到了一个很好的解决方案：LSM 树。所有的写操作首先进入一个内存中的存储，在这里它们被添加到一个已排序的结构中，并准备写入硬盘。内存中的存储是面向行还是列的并不重要。当已经积累了足够的写入数据时，它们将与硬盘上的列文件合并，并批量写入新文件。这基本上是 Vertica 所做的

聚合：数据立方体和物化视图

数据仓库的另一个值得一提的方面是物化汇总（materialized aggregates）。如前所述，数据仓库查询通常涉及一个聚合函数，如 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX。如果相同的聚合被许多不同的查询使用，那么每次都通过原始数据来处理可能太浪费了。为什么不将一些查询使用最频繁的计数或总和缓存起来？创建这种缓存的一种方式是物化视图（Materialized View）

物化视图是查询结果的实际副本，会被写入硬盘。当底层数据发生变化时，物化视图需要更新，因为它是数据的非规范化副本。数据库可以自动完成该操作，但是这样的更新使得写入成本更高，这就是在 OLTP 数据库中不经常使用物化视图的原因。在读取繁重的数据仓库中，它们可能更有意义。

物化视图的常见特例称为数据立方体或 OLAP 立方【64】。它是按不同维度分组的聚合网格

物化数据立方体的优点是可以让某些查询变得非常快，因为它们已经被有效地预先计算了

数据立方体的缺点是不具有查询原始数据的灵活性

第四章 编码与演化

双向兼容性：

  • 向后兼容 (backward compatibility)

    新代码可以读旧数据。

  • 向前兼容 (forward compatibility)

    旧代码可以读新数据

滚动升级部署

本章中将介绍几种编码数据的格式，包括 JSON、XML、Protocol Buffers、Thrift 和 Avro。尤其将关注这些格式如何应对模式变化，以及它们如何对新旧代码数据需要共存的系统提供支持。

然后将讨论如何使用这些格式进行数据存储和通信：在 Web 服务中，表述性状态传递（REST） 和 远程过程调用（RPC），以及 消息传递系统（如 Actor 和消息队列）。

编码数据的格式

两种格式：内存和网络，序列化与反序列化

语言特定的格式

例如，Java 有 java.io.Serializable 【1】，Ruby 有 Marshal【2】，Python 有 pickle【3】

这类编码通常与特定的编程语言深度绑定，其他语言很难读取这种数据（不好集成）

为了恢复相同对象类型的数据，解码过程需要 实例化任意类 的能力，这通常是安全问题的一个来源（不安全）

双向兼容性差

效率低

JSON、XML和二进制变体

数值（numbers） 的编码多有歧义之处；当处理更大的数值时，这个问题显得尤为严重

JSON 和 XML 对 Unicode 字符串（即人类可读的文本）有很好的支持，但是它们不支持二进制数

XML 【11】和 JSON 【12】都有可选的模式支持

CSV 没有任何模式，因此每行和每列的含义完全由应用程序自行定义

尽管存在这些缺陷，但 JSON、XML 和 CSV 对很多需求来说已经足够好了。它们很可能会继续流行下去，特别是作为数据交换格式来说（即将数据从一个组织发送到另一个组织）。在这种情况下，只要人们对格式是什么意见一致，格式有多美观或者效率有多高效就无所谓了。让不同的组织就这些东西达成一致的难度超过了绝大多数问题。

二进制编码

JSON 比 XML 简洁，但与二进制格式相比还是太占空间。这一事实导致大量二进制编码版本 JSON（MessagePack、BSON、BJSON、UBJSON、BISON 和 Smile 等） 和 XML（例如 WBXML 和 Fast Infoset）的出现

这些格式中的一些扩展了一组数据类型（例如，区分整数和浮点数，或者增加对二进制字符串的支持），另一方面，它们没有改变 JSON / XML 的数据模型。特别是由于它们没有规定模式，所以它们需要在编码数据中包含所有的对象字段名称。

Thrift与Protocol Buffers

Avro

数据流的类型

数据库中的数据流

如果将数据库值解码为应用程序中的模型对象，稍后重新编码这些模型对象，那么未知字段可能会在该翻译过程中丢失

服务中的数据流

面向服务的体系结构（service-oriented architecture，SOA），最近被改进和更名为 微服务架构

REST 不是一个协议，而是一个基于 HTTP 原则的设计哲学【34,35】。它强调简单的数据格式，使用 URL 来标识资源，并使用 HTTP 功能进行缓存控制，身份验证和内容类型协商。与 SOAP 相比，REST 已经越来越受欢迎，至少在跨组织服务集成的背景下【36】，并经常与微服务相关【31】。根据 REST 原则设计的 API 称为 RESTful。

EST 风格的 API 倾向于更简单的方法，通常涉及较少的代码生成和自动化工具。定义格式（如 OpenAPI，也称为 Swagger 【40】）可用于描述 RESTful API 并生成文档。

远程过程调用（RPC）的问题

Web 服务仅仅是通过网络进行 API 请求的一系列技术的最新版本，其中许多技术受到了大量的炒作，但是存在严重的问题。 Enterprise JavaBeans（EJB）和 Java 的 远程方法调用（RMI） 仅限于 Java。分布式组件对象模型（DCOM） 仅限于 Microsoft 平台。公共对象请求代理体系结构（CORBA） 过于复杂，不提供前向或后向兼容性【41】。

网络请求与本地函数调用非常不同：

  1. 本地函数调用是可预测的，并且成功或失败仅取决于受你控制的参数。网络请求是不可预知的：由于网络问题，请求或响应可能会丢失，或者远程计算机可能很慢或不可用，这些问题完全不在你的控制范围之内。网络问题是常见的，所以你必须预测他们，例如通过重试失败的请求。

  2. 本地函数调用要么返回结果，要么抛出异常，或者永远不返回（因为进入无限循环或进程崩溃）。网络请求有另一个可能的结果：由于超时，它可能会返回没有结果。在这种情况下，你根本不知道发生了什么：如果你没有得到来自远程服务的响应，你无法知道请求是否通过。

  3. 如果你重试失败的网络请求，可能会发生请求实际上正在通过，只有响应丢失。在这种情况下，重试将导致该操作被执行多次，除非你在协议中引入去重机制（幂等，即 idempotence）。本地函数调用没有这个问题。

  4. 每次调用本地功能时，通常需要大致相同的时间来执行。网络请求比函数调用要慢得多，而且其延迟也是非常可变的：好的时候它可能会在不到一毫秒的时间内完成，但是当网络拥塞或者远程服务超载时，可能需要几秒钟的时间完成一样的东西。

  5. 调用本地函数时，可以高效地将引用（指针）传递给本地内存中的对象。当你发出一个网络请求时，所有这些参数都需要被编码成可以通过网络发送的一系列字节。如果参数是像数字或字符串这样的基本类型倒是没关系，但是对于较大的对象很快就会变成问题

  6. 客户端和服务可以用不同的编程语言实现，所以 RPC 框架必须将数据类型从一种语言翻译成另一种语言。这可能会捅出大篓子，因为不是所有的语言都具有相同的类型 —— 例如回想一下 JavaScript 的数字大于 $2^{53}$ 的问题（请参阅 “JSON、XML 和二进制变体”）。用单一语言编写的单个进程中不存在此问题。

消息传递中的数据流

与直接 RPC 相比，使用消息代理有几个优点：

  • 如果收件人不可用或过载，可以充当缓冲区，从而提高系统的可靠性。
  • 它可以自动将消息重新发送到已经崩溃的进程，从而防止消息丢失。
  • 避免发件人需要知道收件人的 IP 地址和端口号（这在虚拟机经常出入的云部署中特别有用）。
  • 它允许将一条消息发送给多个收件人。
  • 将发件人与收件人逻辑分离（发件人只是发布邮件，不关心使用者）。
分布式actor 框架

第二部分 分布式数据系统

为什么要分布式？

  1. 扩展性
  2. 容错与高可用性
  3. 延迟考虑

数据系统的扩展方式？

共享内存架构（垂直扩展）的问题：成本增长过快，无异地容错能力

共享磁盘架构：资源竞争以及锁的开销等限制了其进一步的扩展能力

无共享架构（水平扩展）：每个节点独立使用本地的cpu，内存和磁盘，这种方式性价比高、减少访问延迟、有异地容错能力，缺点是复杂度高

将数据分布在多节点的两种方式：复制和分区

复制：在多个节点上保存相同数据的副本，复制可以提供冗余（容错和高可用）和提高系统性能

分区：将一个大块头的数据库拆分成多个较小的子集即分区，不同的分区分配给不同的节点（也称为分片）

第五章 数据复制

为什么？

  1. 使数据在地理上更接近用户，降低延迟
  2. 提供冗余以提升容错性和高可用性
  3. 多副本同时提供数据访问服务，从而提高读吞吐量

复制引入了多副本，需要解决多副本之间的一致性问题。复制的困难之处在于处理复制数据的 变更

三种流行的变更复制算法：单领导者（single leader），多领导者（multi leader） 和 无领导者（leaderless）

领导者与追随者

基于领导者的复制（主从复制）原理：

  1. 副本之一被指定为 领导者（leader），也称为 **主库（master primary）** 。当客户端要向数据库写入时，它必须将请求发送给 领导者，领导者会将新数据写入其本地存储。
  2. 其他副本被称为 追随者（followers），亦称为 只读副本（read replicas），从库（slaves），备库（ secondaries），热备（hot-standby）。每当领导者将新数据写入本地存储时，它也会将数据变更发送给所有的追随者，称之为 复制日志（replication log） 记录或 变更流（change stream）。每个跟随者从领导者拉取日志，并相应更新其本地数据库副本，方法是按照领导者处理的相同顺序应用所有写入。
  3. 当客户想要从数据库中读取数据时，它可以向领导者或追随者查询。 但只有领导者才能接受写操作（从客户端的角度来看从库都是只读的）。

同步复制与异步复制

同步复制的优点是，从库保证有与主库一致的最新数据副本。如果主库突然失效，我们可以确信这些数据仍然能在从库上上找到。

缺点是，如果同步从库没有响应（比如它已经崩溃，或者出现网络故障，或其它任何原因），主库就无法处理写入操作。主库必须阻止所有写入，并等待同步副本再次可用。

因此，将所有从库都设置为同步是不切实际的：任何一个节点的中断都会导致整个系统停滞不前。实际上，如果在数据库上启用同步复制，通常意味着其中 一个 跟随者是同步的，而其他的则是异步的。如果同步从库变得不可用或缓慢，则使一个异步从库同步。这保证你至少在两个节点上拥有最新的数据副本：主库和同步从库。 这种配置有时也被称为 半同步（semi-synchronous）

通常情况下，基于领导者的复制都配置为完全异步。 在这种情况下，如果主库失效且不可恢复，则任何尚未复制给从库的写入都会丢失。 这意味着即使已经向客户端确认成功，写入也不能保证 持久（Durable） 。 然而，一个完全异步的配置也有优点：即使所有的从库都落后了，主库也可以继续处理写入。

弱化的持久性可能听起来像是一个坏的折衷，然而异步复制已经被广泛使用了，特别当有很多追随者，或追随者异地分布时。

设置新从库

也许是为了增加副本的数量，或替换失败的节点，步骤:

  1. 在某个时刻获取主库的一致性快照（如果可能），而不必锁定整个数据库。

  2. 将快照复制到新的从库节点。

  3. 从库连接到主库，并拉取快照之后发生的所有数据变更。这要求快照与主库复制日志中的位置精确关联。该位置有不同的名称：例如，PostgreSQL 将其称为 日志序列号（log sequence number, LSN），MySQL 将其称为 二进制日志坐标（binlog coordinates）。

  4. 当从库处理完快照之后积压的数据变更，我们说它 赶上（caught up） 了主库。现在它可以继续处理主库产生的数据变化了。

处理节点宕机

目标是，即使个别节点失效，也能保持整个系统运行，并尽可能控制节点停机带来的影响

从库失效：追赶恢复

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

主库失效：故障切换

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

自动故障切换过程通常由以下步骤组成：

  1. 确认主库失效。大多数系统只是简单使用 超时（Timeout） ：节点频繁地相互来回传递消息，并且如果一个节点在一段时间内（例如 30 秒）没有响应，就认为它挂了（因为计划内维护而故意关闭主库不算）。

  2. 选择一个新的主库。这可以通过选举过程（主库由剩余副本以多数选举产生）来完成，或者可以由之前选定的 控制器节点（controller node） 来指定新的主库。主库的最佳人选通常是拥有旧主库最新数据副本的从库（最小化数据损失）。让所有的节点同意一个新的领导者，是一个 共识 问题，将在 第九章 详细讨论。

  3. 重新配置系统以启用新的主库。客户端现在需要将它们的写请求发送给新主库。如果旧主库恢复，可能仍然认为自己是主库，而没有意识到其他副本已经让它失去领导权了。系统需要确保旧主库意识到新主库的存在，并成为一个从库。

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

  • 如果使用异步复制，则新主库可能没有收到老主库宕机前最后的写入操作。在选出新主库后，如果老主库重新加入集群，新主库在此期间可能会收到冲突的写入，那这些写入该如何处理？最常见的解决方案是简单丢弃老主库未复制的写入，这很可能打破客户对于数据持久性的期望。
  • 如果数据库需要和其他外部存储相协调，那么丢弃写入内容是极其危险的操作。例如在 GitHub 【13】的一场事故中，一个过时的 MySQL 从库被提升为主库。数据库使用自增 ID 作为主键，因为新主库的计数器落后于老主库的计数器，所以新主库重新分配了一些已经被老主库分配掉的 ID 作为主键。这些主键也在 Redis 中使用，主键重用使得 MySQL 和 Redis 中数据产生不一致，最后导致一些私有数据泄漏到错误的用户手中。
  • 发生某些故障时可能会出现两个节点都以为自己是主库的情况。这种情况称为 脑裂 (split brain)，非常危险：如果两个主库都可以接受写操作，却没有冲突解决机制，那么数据就可能丢失或损坏。一些系统采取了安全防范措施：当检测到两个主库节点同时存在时会关闭其中一个节点 ，但设计粗糙的机制可能最后会导致两个节点都被关闭。
  • 主库被宣告死亡之前的正确超时应该怎么配置？在主库失效的情况下，超时时间越长，意味着恢复时间也越长。但是如果超时设置太短，又可能会出现不必要的故障切换。例如，临时负载峰值可能导致节点的响应时间超时，或网络故障可能导致数据包延迟。如果系统已经处于高负载或网络问题的困扰之中，那么不必要的故障切换可能会让情况变得更糟糕

节点故障、不可靠的网络、对副本一致性，持久性，可用性和延迟的权衡 ，这些问题实际上是分布式系统中的基本问题

复制日志的实现

基于语句的复制

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

存在的问题：

  1. 任何调用 非确定性函数（nondeterministic） 的语句，可能会在每个副本上生成不同的值。例如 NOW() RAND()

  2. 如果语句使用了 自增列（auto increment），或者依赖于数据库中的现有数据（例如，UPDATE ... WHERE <某些条件>），则必须在每个副本上按照完全相同的顺序执行它们，否则可能会产生不同的效果。当有多个并发执行的事务时，这可能成为一个限制。

  3. 有副作用的语句（例如：触发器、存储过程、用户定义的函数）可能会在每个副本上产生不同的副作用，除非副作用是绝对确定的。

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

传输预写式日志（WAL）

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

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

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

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

逻辑日志复制（基于行）

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

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

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

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

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

对于外部应用程序来说，逻辑日志格式也更容易解析。如果要将数据库的内容发送到外部系统，这一点很有用，例如复制到数据仓库进行离线分析，或建立自定义索引和缓存。

基于触发器的复制

触发器允许你注册在数据库系统中发生数据更改（写入事务）时自动执行的自定义应用程序代码。触发器有机会将更改记录到一个单独的表中，使用外部程序读取这个表，再加上任何业务逻辑处理，然后将数据变更复制到另一个系统去

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

复制延迟问题

主从复制+异步：最终一致性，即会有一段时间处于不一致

本节讲复制延迟导致暂时不一致引发的三个问题和解决办法

读己之写

异步引发的读写不一致（写主库，读从库）

基于领导者的复制系统中实现读写一致性的一些方法：

  1. 读用户 可能已经修改过 的内容时，都从主库读；这就要求有一些方法，不用实际查询就可以知道用户是否修改了某些东西。

    举个例子，社交网络上的用户个人资料信息通常只能由用户本人编辑，而不能由其他人编辑。因此一个简单的规则是：从主库读取用户自己的档案，在从库读取其他用户的档案

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

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

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

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

跨设备的写后读一致性:如果用户在某个设备上输入了一些信息，然后在另一个设备上查看，则应该看到他们刚输入的信息。

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

  • 记住用户上次更新时间戳的方法变得更加困难，因为一台设备上运行的程序不知道另一台设备上发生了什么。元数据需要一个中心存储。
  • 如果副本分布在不同的数据中心，很难保证来自不同设备的连接会路由到同一数据中心

单调读

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

如果用户从不同从库进行多次读取，就可能发生这种情况

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

实现单调读取的一种方式是确保每个用户总是从同一个副本进行读取

一致前缀读

第三个异常例子是违反因果律

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

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

一种解决方案是，确保任何因果相关的写入都写入相同的分区。

对于某些无法高效完成这种操作的应用，还有一些显式跟踪因果依赖关系的算法

多主复制

在单个数据中心内部使用多个主库没有太大意义，因为复杂性已经超过了能带来的好处。 但在一些情况下，多主配置是也合理的。

运维多个数据中心

在每个数据中心内使用常规的主从复制；在数据中心之间，每个数据中心的主库都会将其更改复制到其他数据中心的主库中。

优势：性能，容忍数据中心停机，容忍网络问题

缺点：两个不同的数据中心可能会同时修改相同的数据，写冲突是必须解决的

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

需要离线操作的客户端

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

协同编辑

当一个用户编辑文档时，所做的更改将立即应用到其本地副本（Web 浏览器或客户端应用程序中的文档状态），并异步复制到服务器和编辑同一文档的任何其他用户。

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

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

处理写入冲突

img

同步与异步冲突检测

在单主数据库中，第二个写入将被阻塞，并等待第一个写入完成，或中止第二个写入事务，强制用户重试（同步检测）。

在多主配置中，两个写入都是成功的，并且在稍后的时间点仅仅异步地检测到冲突。那时要求用户解决冲突可能为时已晚。

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

避免冲突

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

收敛至一致的状态

冲突合并

自定义冲突解决逻辑

写时执行

读时执行

自动冲突解决

一些有趣的研究来自动解决由于数据修改引起的冲突：

无冲突复制数据类型CRDT：是可以由多个用户同时编辑的集合，映射，有序列表，计数器等的一系列数据结构，它们以合理的方式自动解决冲突。

可合并的持久数据结构：显式跟踪历史记录，类似于 Git 版本控制系统，并使用三向合并功能（而 CRDT 使用双向合并）

可执行的转换：是 Etherpad 【30】和 Google Docs 【31】等合作编辑应用背后的冲突解决算法。它是专为同时编辑项目的有序列表而设计的

什么是冲突

有些冲突是显而易见的：两个写操作并发地修改了同一条记录中的同一个字段，并将其设置为两个不同的值

其他类型的冲突可能更为微妙，难以发现：同时为同一个房间创建两个不同的预订，则可能会发生冲突

多主复制拓扑

复制拓扑（replication topology）描述写入从一个节点传播到另一个节点的通信路径

all-to-all topology：事件因果排序 —-> 版本向量

star topology： 防止无限循环和单点故障

Circular topology： 防止无限循环和单点故障

无主复制

Riak，Cassandra 和 Voldemort 是由 Dynamo 启发的无领导复制模型的开源数据存储，所以这类数据库也被称为 Dynamo 风格

在一些无领导者的实现中，客户端直接将写入发送到几个副本中，而另一些情况下，一个 协调者（coordinator） 节点代表客户端进行写入。但与主库数据库不同，协调者不执行特定的写入顺序

当节点故障时写入数据库

在无主配置中，不存在故障切换。读写都会发送到多个副本

读修复和反熵

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

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

  • 读修复（Read repair）

    当客户端并行读取多个节点时，它可以检测到任何陈旧的响应，并用新值替换旧值。这种方法适用于读频繁的值。

  • 反熵过程（Anti-entropy process）

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

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

读写的法定人数

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

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

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

  1. 如果 $w <n$，如果节点不可用，我们仍然可以处理写入。

  2. 如果 $r <n$，如果节点不可用，我们仍然可以处理读取。
  3. 通常，读取和写入操作始终并行发送到所有 n 个副本。 参数 w 和 r 决定我们等待多少个节点，即在我们认为读或写成功之前，有多少个节点需要报告成功

法定人数一致性的局限性

可以将 w 和 r 设置为较小的数字，以使 $w + r≤n$（即法定条件不满足）。在这种情况下，读取和写入操作仍将被发送到 n 个节点，但操作成功只需要少量的成功响应。这可能会读取过时的数据，因为更有可能不包含具有最新值的节点。另一方面，这种配置允许更低的延迟和更高的可用性：如果存在网络中断，并且许多副本变得无法访问，则可以继续处理读取和写入的机会更大。只有当可达副本的数量低于 w 或 r 时，数据库才分别变得不可用于写入或读取。

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

  1. 如果使用宽松的法定人数，w 个写入和 r 个读取落在完全不同的节点上，因此 r 节点和 w 之间不再保证有重叠节点。

  2. 如果两个写入同时发生，不清楚哪一个先发生。在这种情况下，唯一安全的解决方案是合并并发写入。如果根据时间戳（最后写入胜利）挑选出一个胜者，则由于时钟偏，写入可能会丢失。

  3. 如果写操作与读操作同时发生，写操作可能仅反映在某些副本上。在这种情况下，不确定读取是返回旧值还是新值。

  4. 如果写操作在某些副本上成功，而在其他节点上失败（例如，因为某些节点上的磁盘已满），在小于 w 个副本上写入成功。所以整体判定写入失败，但整体写入失败并没有在写入成功的副本上回滚。这意味着如果一个写入虽然报告失败，后续的读取仍然可能会读取这次失败写入的值。

  5. 如果携带新值的节点失败，需要读取其他带有旧值的副本。并且其数据从带有旧值的副本中恢复，则存储新值的副本数可能会低于 w，从而打破法定人数条件。

  6. 即使一切工作正常，有时也会不幸地出现关于 时序（timing） 的边缘情况

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

尤其是，因为通常没有得到 “复制延迟问题” 中讨论的保证（读己之写，单调读，一致前缀读），前面提到的异常可能会发生在应用程序中。更强有力的保证通常需要 事务 或 共识

监控陈旧度

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

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

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

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

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

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

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

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

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

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

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

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

运维多个数据中心

无主复制也适用于多数据中心操作，因为它旨在容忍冲突的并发写入，网络中断和延迟尖峰。

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

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

检测并发写入

Dynamo 风格的数据库允许多个客户端同时写入相同的 Key，这意味着即使使用严格的法定人数也会发生冲突。这种情况与多领导者复制相似，但在 Dynamo 样式的数据库中，在 读修复 或 提示移交 期间也可能会产生冲突。问题在于，由于可变的网络延迟和部分故障，事件可能在不同的节点以不同的顺序到达

如果你想避免丢失数据，你（应用程序开发人员）需要知道很多有关数据库冲突处理的内部信息。

解决冲突的技术：

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

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

但是写入是 并发（concurrent） 的，所以它们的顺序是不确定的。

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

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

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

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

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

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

如果一个操作发生在另一个操作之前，则后面的操作应该覆盖较早的操作，但是如果这些操作是并发的，则存在需要解决的冲突

捕获”此前发生”关系

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

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

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

合并同时写入的值

然而，如果你想让人们也可以从他们的购物车中 删除 东西，而不是仅仅添加东西，那么把并发值做并集可能不会产生正确的结果：如果你合并了两个客户端的购物车，并且只在其中一个客户端里面删掉了它，那么被删除的项目会重新出现在这两个客户端的交集结果中。为了防止这个问题，一个项目在删除时不能简单地从数据库中删除；相反，系统必须留下一个具有适当版本号的标记，在合并兄弟时表明该项目已被删除。这种删除标记被称为 墓碑（tombstone）

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

版本向量

当有多个副本但没有领导者时,还需要在 每个副本 以及 每个键 使用版本号。每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本中看到的版本号。这个信息指出了要覆盖哪些并发值，以及保留哪些并发值。

所有副本的版本号集合称为 版本向量（version vector）【56】。这个想法的一些变体正在被使用，但最有趣的可能是在 Riak 2.0 【58,59】中使用的 虚线版本向量（dotted version vector）【57】

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

版本向量结构能够确保从一个副本读取并随后写回到另一个副本是安全的。这样做虽然可能会在其他副本上面创建数据，但只要能正确合并就不会丢失数据。

第六章 分区

分区主要是为了可伸缩性

首先介绍分割大型数据集的不同方法，并观察索引如何与分区配合。然后我们将讨论 分区再平衡（rebalancing），如果想要添加或删除集群中的节点，则必须进行再平衡。最后，我们将概述数据库如何将请求路由到正确的分区并执行查询。

分区与复制

分区通常与复制结合使用，使得每个分区的副本存储在多个节点上。这意味着，即使每条记录属于一个分区，它仍然可以存储在多个不同的节点上以获得容错能力。

一个节点可能存储多个分区。如果使用主从复制模型，每个分区领导者（主）被分配给一个节点，追随者（从）被分配给其他节点。 每个节点可能是某些分区的领导者，同时是其他分区的追随者。

第五章 讨论的关于数据库复制的所有内容同样适用于分区的复制。大多数情况下，分区方案的选择与复制方案的选择是独立的

键值数据的分区

分区目标是将数据和查询负载均匀分布在各个节点上

如果分区是不公平的，一些分区比其他分区有更多的数据或查询，我们称之为 偏斜（skew）

不均衡导致的高负载的分区被称为 热点（hot spot）

避免热点最简单的方法是将记录随机分配给节点。这将在所有节点上平均分配数据，但是它有一个很大的缺点：当你试图读取一个特定的值时，你无法知道它在哪个节点上，所以你必须并行地查询所有的节点。

根据键的范围分区

一种分区的方法是为每个分区指定一块连续的键范围，键的范围不一定均匀分布，因为数据也很可能不均匀分布；为了均匀分配数据，分区边界需要依据数据调整。在每个分区中，我们可以按照一定的顺序保存键，好处是进行范围扫描非常简单，你可以将键作为联合索引来处理，以便在一次查询中获取多个相关记录。然而，Key Range 分区的缺点是某些特定的访问模式会导致热点。

根据键的散列分区

一个好的散列函数可以将偏斜的数据均匀分布

使用键散列进行分区，我们失去了键范围分区的一个很好的属性：高效执行范围查询的能力。

Cassandra 采取了折衷的策略。 Cassandra 中的表可以使用由多个列组成的复合主键来声明。键中只有第一列会作为散列的依据，而其他列则被用作 Casssandra 的 SSTables 中排序数据的连接索引。尽管查询无法在复合主键的第一列中按范围扫表，但如果第一列已经指定了固定值，则可以对该键的其他列执行有效的范围扫描。

组合索引方法为一对多关系提供了一个优雅的数据模型。例如，在社交媒体网站上，一个用户可能会发布很多更新。如果更新的主键被选择为 (user_id, update_timestamp)，那么你可以有效地检索特定用户在某个时间间隔内按时间戳排序的所有更新。不同的用户可以存储在不同的分区上，对于每个用户，更新按时间戳顺序存储在单个分区上

负载偏斜与热点消除

在极端情况下，所有的读写操作都是针对同一个键的，所有的请求都会被路由到同一个分区。

例如，在社交媒体网站上，一个拥有数百万追随者的名人用户在做某事时可能会引发一场风暴

如今，大多数数据系统无法自动补偿这种高度偏斜的负载，因此应用程序有责任减少偏斜

例如，如果一个主键被认为是非常火爆的，一个简单的方法是在主键的开始或结尾添加一个随机数。只要一个两位数的十进制随机数就可以将主键分散为 100 种不同的主键，从而存储在不同的分区中。

然而，将主键进行分割之后，任何读取都必须要做额外的工作，因为他们必须从所有 100 个主键分布中读取数据并将其合并。此技术还需要额外的记录：只需要对少量热点附加随机数；对于写入吞吐量低的绝大多数主键来说是不必要的开销。因此，你还需要一些方法来跟踪哪些键需要被分割

分区与次级索引

次级索引通常并不能唯一地标识记录，而是一种搜索记录中出现特定值的方式

次级索引的问题是它们不能整齐地映射到分区。有两种用次级索引对数据库进行分区的方法：

基于文档的分区（document-based） 和 基于关键词（term-based）的分区。

基于文档的次级索引进行分区

在这种索引方法中，每个分区是完全独立的：每个分区维护自己的次级索引，仅覆盖该分区中的文档。它不关心存储在其他分区的数据。无论何时你需要写入数据库（添加，删除或更新文档），只需处理包含你正在编写的文档 ID 的分区即可。出于这个原因，文档分区索引 也被称为 本地索引（而不是将在下一节中描述的 全局索引）。

按次级索引查询则需要将查询发送到所有分区，并合并所有返回的结果。

这种查询分区数据库的方法有时被称为 分散 / 聚集（scatter/gather），并且可能会使次级索引上的读取查询相当昂贵。即使并行查询分区，分散 / 聚集也容易导致尾部延迟放大。然而，它被广泛使用：MongoDB，Riak 【15】，Cassandra 【16】，Elasticsearch 【17】，SolrCloud 【18】和 VoltDB 【19】都使用文档分区次级索引。大多数数据库供应商建议你构建一个能从单个分区提供次级索引查询的分区方案，但这并不总是可行，尤其是当在单个查询中使用多个次级索引时

基于关键词(Term)的次级索引进行分区

我们可以构建一个覆盖所有分区数据的 全局索引，而不是给每个分区创建自己的次级索引（本地索引）。但是，我们不能只把这个索引存储在一个节点上，因为它可能会成为瓶颈，违背了分区的目的。全局索引也必须进行分区，但可以采用与主键不同的分区方式。

我们将这种索引称为 关键词分区（term-partitioned），因为我们寻找的关键词决定了索引的分区方式。

和之前一样，我们可以通过 关键词 本身或者它的散列进行索引分区。根据关键词本身来分区对于范围扫描非常有用（例如对于数值类的属性，像汽车的报价），而对关键词的哈希分区提供了负载均衡的能力。

关键词分区的全局索引读取更有效率：不需要 分散 / 收集 所有分区，客户端只需要向包含关键词的分区发出请求。全局索引的缺点在于写入速度较慢且较为复杂，因为写入单个文档现在可能会影响索引的多个分区（文档中的每个关键词可能位于不同的分区或者不同的节点上） 。在关键词分区索引中，需要跨分区的分布式事务，并不是所有数据库都支持。

在实践中，对全局次级索引的更新通常是 异步 的

分区再平衡

随着时间的推移，数据库会有各种变化：

  • 查询吞吐量增加，所以你想要添加更多的 CPU 来处理负载。
  • 数据集大小增加，所以你想添加更多的磁盘和 RAM 来存储它。
  • 机器出现故障，其他机器需要接管故障机器的责任。

所有这些更改都需要数据和请求从一个节点移动到另一个节点。 将负载从集群中的一个节点向另一个节点移动的过程称为 再平衡。

无论使用哪种分区方案，再平衡通常都要满足一些最低要求：

  • 再平衡之后，负载（数据存储，读取和写入请求）应该在集群中的节点之间公平地共享。
  • 再平衡发生时，数据库应该继续接受读取和写入。
  • 节点之间只移动必须的数据，以便快速再平衡，并减少网络和磁盘 I/O 负载。

再平衡策略

反面教材：hash mod N

模 N（$mod N$）方法的问题是，如果节点数量 N 发生变化，大多数键将需要从一个节点移动到另一个节点.这种频繁的举动使得重新平衡过于昂贵。

固定数量的分区

有一个相当简单的解决方案：创建比节点更多的分区，并为每个节点分配多个分区

只有分区在节点之间的移动。分区的数量不会改变，键所指定的分区也不会改变。唯一改变的是分区所在的节点

可以解决集群中的硬件不匹配问题：通过为更强大的节点分配更多的分区，可以强制这些节点承载更多的负载。

因此，一开始配置的分区数就是你可以拥有的最大节点数量，所以你需要选择足够多的分区以适应未来的增长。但是，每个分区也有管理开销，所以选择太大的数字会适得其反。

由于每个分区包含了总数据量固定比率的数据，因此每个分区的大小与集群中的数据总量成比例增长。如果分区非常大，再平衡和从节点故障恢复变得昂贵。但是，如果分区太小，则会产生太多的开销。当分区大小 “恰到好处” 的时候才能获得很好的性能，如果分区数量固定，但数据量变动很大，则难以达到最佳性能。

动态分区

对于使用键范围分区的数据库，具有固定边界的固定数量的分区将非常不便：如果出现边界错误，则可能会导致一个分区中的所有数据或者其他分区中的所有数据为空。手动重新配置分区边界将非常繁琐。

出于这个原因，按键的范围进行分区的数据库（如 HBase 和 RethinkDB）会动态创建分区。当分区增长到超过配置的大小时（在 HBase 上，默认值是 10GB），会被分成两个分区，每个分区约占一半的数据【26】。与之相反，如果大量数据被删除并且分区缩小到某个阈值以下，则可以将其与相邻分区合并。此过程与 B 树顶层发生的过程类似（请参阅 “B 树”）。

每个分区分配给一个节点，每个节点可以处理多个分区，就像固定数量的分区一样。大型分区拆分后，可以将其中的一半转移到另一个节点，以平衡负载。在 HBase 中，分区文件的传输通过 HDFS（底层使用的分布式文件系统）来实现【3】。

动态分区的一个优点是分区数量适应总数据量。如果只有少量的数据，少量的分区就足够了，所以开销很小；如果有大量的数据，每个分区的大小被限制在一个可配置的最大值【23】。

需要注意的是，一个空的数据库从一个分区开始，因为没有关于在哪里绘制分区边界的先验信息。数据集开始时很小，直到达到第一个分区的分割点，所有写入操作都必须由单个节点处理，而其他节点则处于空闲状态。为了解决这个问题，HBase 和 MongoDB 允许在一个空的数据库上配置一组初始分区（这被称为 预分割，即 pre-splitting）。在键范围分区的情况中，预分割需要提前知道键是如何进行分配的【4,26】。

动态分区不仅适用于数据的范围分区，而且也适用于散列分区。从版本 2.4 开始，MongoDB 同时支持范围和散列分区，并且都支持动态分割分区。

按节点比例分区

动态分局和固定数量分区的分区数都与节点数没有关系

Cassandra 和 Ketama 使用的第三种方法是使分区数与节点数成正比 —— 换句话说，每个节点具有固定数量的分区。在这种情况下，每个分区的大小与数据集大小成比例地增长，而节点数量保持不变，但是当增加节点数时，分区将再次变小。由于较大的数据量通常需要较大数量的节点进行存储，因此这种方法也使每个分区的大小较为稳定。

当一个新节点加入集群时，它随机选择固定数量的现有分区进行拆分，然后占有这些拆分分区中每个分区的一半，同时将每个分区的另一半留在原地。随机化可能会产生不公平的分割，但是平均在更大数量的分区上时（在 Cassandra 中，默认情况下，每个节点有 256 个分区），新节点最终从现有节点获得公平的负载份额。 Cassandra 3.0 引入了另一种再平衡的算法来避免不公平的分割

运维：手动还是自动再平衡

全自动重新平衡可以很方便，因为正常维护的操作工作较少。但是，这可能是不可预测的。再平衡是一个昂贵的操作，因为它需要重新路由请求并将大量数据从一个节点移动到另一个节点。如果没有做好，这个过程可能会使网络或节点负载过重，降低其他请求的性能。

这种自动化与自动故障检测相结合可能十分危险。例如，假设一个节点过载，并且对请求的响应暂时很慢。其他节点得出结论：过载的节点已经死亡，并自动重新平衡集群，使负载离开它。这会对已经超负荷的节点，其他节点和网络造成额外的负载，从而使情况变得更糟，并可能导致级联失败。

出于这个原因，再平衡的过程中有人参与是一件好事。这比完全自动的过程慢，但可以帮助防止运维意外。

请求路由

随着分区重新平衡，分区对节点的分配也发生变化。

这个问题可以概括为 服务发现（service discovery） ，它不仅限于数据库。任何可通过网络访问的软件都有这个问题，特别是如果它的目标是高可用性

概括来说，这个问题有几种不同的方案：

  1. 允许客户联系任何节点（例如，通过 循环策略的负载均衡，即 Round-Robin Load Balancer）。如果该节点恰巧拥有请求的分区，则它可以直接处理该请求；否则，它将请求转发到适当的节点，接收回复并传递给客户端。

  2. 首先将所有来自客户端的请求发送到路由层，它决定了应该处理请求的节点，并相应地转发。此路由层本身不处理任何请求；它仅负责分区的负载均衡。

  3. 要求客户端知道分区和节点的分配。在这种情况下，客户端可以直接连接到适当的节点，而不需要任何中介

以上所有情况中的关键问题是：作出路由决策的组件（可能是节点之一，还是路由层或客户端）如何了解分区 - 节点之间的分配关系变化

这是一个具有挑战性的问题，因为重要的是所有参与者都达成共识 - 否则请求将被发送到错误的节点，得不到正确的处理。 在分布式系统中有达成共识的协议，但很难正确地实现

许多分布式数据系统都依赖于一个独立的协调服务，比如 ZooKeeper 来跟踪集群元数据，每个节点在 ZooKeeper 中注册自己，ZooKeeper 维护分区到节点的可靠映射。 其他参与者（如路由层或分区感知客户端）可以在 ZooKeeper 中订阅此信息。 只要分区分配发生了改变，或者集群中添加或删除了一个节点，ZooKeeper 就会通知路由层使路由信息保持最新状态

Cassandra 和 Riak 采取不同的方法：他们在节点之间使用 流言协议（gossip protocol） 来传播集群状态的变化。请求可以发送到任意节点，该节点会转发到包含所请求的分区的适当节点。这个模型在数据库节点中增加了更多的复杂性，但是避免了对像 ZooKeeper 这样的外部协调服务的依赖。

当使用路由层或向随机节点发送请求时，客户端仍然需要找到要连接的 IP 地址。这些地址并不像分区的节点分布变化的那么快，所以使用 DNS 通常就足够了。

执行并行查询

然而，通常用于分析的 大规模并行处理（MPP, Massively parallel processing） 关系型数据库产品在其支持的查询类型方面要复杂得多。一个典型的数据仓库查询包含多个连接，过滤，分组和聚合操作。 MPP 查询优化器将这个复杂的查询分解成许多执行阶段和分区，其中许多可以在数据库集群的不同节点上并行执行。涉及扫描大规模数据集的查询特别受益于这种并行执行。

第七章 事务

事务（transaction） 一直是简化数据系统各种故障处理的首选机制，是为了简化应用编程模型 而创建的

事务是应用程序将多个读写操作组合成一个逻辑单元的一种方式。从概念上讲，事务中的所有读写操作被视作单个操作来执行：整个事务要么成功 提交（commit），要么失败 中止（abort）或 回滚（rollback）。如果失败，应用程序可以安全地重试。

确切理解事务可以提供的安全保障，以及它们的代价

本章将研究许多出错案例，并探索数据库用于防范这些问题的算法。尤其会深入 并发控制 的领域，讨论各种可能发生的竞争条件，以及数据库如何实现 读已提交（read committed），快照隔离（snapshot isolation） 和 可串行化（serializability） 等隔离级别。

事务的棘手概念

ACID的含义

ACID 代表 原子性（Atomicity），一致性（Consistency），隔离性（Isolation） 和 持久性（Durability）

不同数据库的 ACID 实现并不相同，能提供的保证也比较模糊

原子性

能够在错误时中止事务，丢弃该事务进行的所有写入变更的能力

一致性

对数据的一组特定约束必须始终成立。即 不变式（invariants）

一致性的这种概念取决于应用程序对不变式的理解，应用程序负责正确定义它的事务，并保持一致性

原子性，隔离性和持久性是数据库的属性，而一致性（在 ACID 意义上）是应用程序的属性

隔离性

同时执行的事务是相互隔离的：它们不能相互冒犯。例如，如果一个事务进行多次写入，则另一个事务要么看到全部写入结果，要么什么都看不到，但不应该是一些子集。

持久性

持久性 是一个承诺，即一旦事务成功完成，即使发生硬件故障或数据库崩溃，写入的任何数据也不会丢失。

单对象和多对象操作

原子性和隔离性是多对象事务的前提

单对象写入

当单个对象发生改变时，原子性和隔离性也是适用的。

存储引擎一个普遍的目标是：对单节点上的单个对象（例如键值对）上提供原子性和隔离性。原子性可以通过使用日志来实现崩溃恢复，并且可以使用每个对象上的锁来实现隔离

单对象上的原子操作：原子自增、CAS

单对象原子操作并不是通常意义上的事务，事务通常被理解为，将多个对象上的多个操作合并为一个执行单元的机制。

多对象事务的需求

许多场景需要协调写入几个不同的对象：

  1. 在关系数据模型中，一个表中的行通常具有对另一个表中的行的外键引用
  2. 但是，缺乏连接功能的文档数据库会鼓励非规范化（存储多副本）。当需要更新非规范化的信息时，需要一次更新多个文档。事务在这种情况下非常有用，可以防止非规范化的数据不同步。
  3. 在具有次级索引的数据库中，每次更改值时都需要更新索引（多个）。

这些应用场景仍然可以在没有事务的情况下实现。然而，没有原子性，错误处理就要复杂得多，缺乏隔离性，就会导致并发问题

处理错误和中止

尽管重试一个中止的事务是一个简单而有效的错误处理机制，但它并不完美：

  • 如果事务实际上成功了，但是在服务器试图向客户端确认提交成功时网络发生故障（所以客户端认为提交失败了），那么重试事务会导致事务被执行两次 —— 除非你有一个额外的应用级去重机制。
  • 如果错误是由于负载过大造成的，则重试事务将使问题变得更糟，而不是更好。为了避免这种正反馈循环，可以限制重试次数，使用指数退避算法，并单独处理与过载相关的错误（如果允许）。
  • 仅在临时性错误（例如，由于死锁，异常情况，临时性网络中断和故障切换）后才值得重试。在发生永久性错误（例如，违反约束）之后重试是毫无意义的。
  • 如果事务在数据库之外也有副作用，即使事务被中止，也可能发生这些副作用。如果你想确保几个不同的系统一起提交或放弃，两阶段提交（2PC, two-phase commit） 可以提供帮助。
  • 如果客户端进程在重试中失效，任何试图写入数据库的数据都将丢失。

弱隔离级别

读已提交

最基本的事务隔离级别是 读已提交（Read Committed），它提供了两个保证：

  1. 从数据库读时，只能看到已提交的数据（没有 脏读，即 dirty reads）。

  2. 写入数据库时，只会覆盖已经写入的数据（没有 脏写，即 dirty writes）。

没有脏读

为什么要防止脏读，有几个原因：

  • 如果事务需要更新多个对象，脏读取意味着另一个事务可能会只看到一部分更新。
  • 如果事务中止，则所有写入操作都需要回滚。如果数据库允许脏读，那就意味着一个事务可能会看到稍后需要回滚的数据，即从未实际提交给数据库的数据.
没有脏写

  1. 如果事务更新多个对象，脏写会导致不好的结果。

  2. 读已提交并不能防止两个“计数器增量”之间的竞争状态

实现读已提交

使用 行锁（row-level lock） 来防止脏写：当事务想要修改特定对象（行或文档）时，它必须首先获得该对象的锁。然后必须持有该锁直到事务被提交或中止

防止脏读：对于写入的每个对象，数据库都会记住旧的已提交值，和由当前持有写入锁的事务设置的新值。当事务正在进行时，任何其他读取对象的事务都会拿到旧值。 只有当新值提交后，事务才会切换到读取新值。

快照隔离和可重复读

读已提交不能保证一个事务处理过程中读到的值都是一致的，即不可重复读。这在以下场景会有问题：

  1. 备份
  2. 分析查询和完整性检查

快照隔离（snapshot isolation）是这个问题最常见的解决方案。想法是，每个事务都从数据库的 一致快照（consistent snapshot） 中读取 —— 也就是说，事务可以看到事务开始时在数据库中提交的所有数据。即使这些数据随后被另一个事务更改，每个事务也只能看到该特定时间点的旧数据。

实现快照隔离

从性能的角度来看，快照隔离的一个关键原则是：读不阻塞写，写不阻塞读。

与读取提交的隔离类似，快照隔离的实现通常使用写锁来防止脏写。

为了实现快照隔离，数据库使用了我们看到的 读已提交 用于防止脏读的机制的一般化。数据库必须可能保留一个对象的几个不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它同时维护着单个对象的多个版本，所以这种技术被称为 多版本并发控制（MVCC, multi-version concurrency control）。

如果一个数据库只需要提供 读已提交 的隔离级别，而不提供 快照隔离，那么保留一个对象的两个版本就足够了：提交的版本和被覆盖但尚未提交的版本。支持快照隔离的存储引擎通常也使用 MVCC 来实现 读已提交 隔离级别。一种典型的方法是 读已提交 为每个查询使用单独的快照，而 快照隔离 对整个事务使用相同的快照。

当一个事务开始时，它被赋予一个唯一的永远增长的事务 ID（txid）。每当事务向数据库写入任何内容时，它所写入的数据都会被标记上写入者的事务 ID。

表中的每一行都有一个 created_by 字段，其中包含将该行插入到表中的的事务 ID。此外，每行都有一个 deleted_by 字段，最初是空的。如果某个事务删除了一行，那么该行实际上并未从数据库中删除，而是通过将 deleted_by 字段设置为请求删除的事务的 ID 来标记为删除。在稍后的时间，当确定没有事务可以再访问已删除的数据时，数据库中的垃圾收集过程会将所有带有删除标记的行移除，并释放其空间。（UPDATE 操作在内部翻译为 DELETE 和 INSERT）

观察一致性快照的可见性规则

当一个事务从数据库中读取时，事务 ID 用于决定它可以看见哪些对象，看不见哪些对象。

  1. 在每次事务开始时，数据库列出当时所有其他（尚未提交或尚未中止）的事务清单，即使之后提交了，这些事务已执行的任何写入也都会被忽略。
  2. 被中止事务所执行的任何写入都将被忽略。
  3. 由具有较晚事务 ID（即，在当前事务开始之后开始的）的事务所做的任何写入都被忽略，而不管这些事务是否已经提交。
  4. 所有其他写入，对应用都是可见的。

由于从来不原地更新值，而是每次值改变时创建一个新的版本，数据库可以在提供一致快照的同时只产生很小的额外开销

索引和快照隔离

索引如何在多版本数据库中工作？一种选择是使索引简单地指向对象的所有版本，并且需要索引查询来过滤掉当前事务不可见的任何对象版本。当垃圾收集删除任何事务不再可见的旧对象版本时，相应的索引条目也可以被删除。

在实践中，许多实现细节决定了多版本并发控制的性能。例如，如果同一对象的不同版本可以放入同一个页面中，PostgreSQL 的优化可以避免更新索引。

在 CouchDB、Datomic 和 LMDB 中使用另一种方法。虽然它们也使用 B 树，但它们使用的是一种 仅追加 / 写时拷贝（append-only/copy-on-write） 的变体，它们在更新时不覆盖树的页面，而为每个修改页面创建一份副本。从父页面直到树根都会级联更新，以指向它们子页面的新版本。任何不受写入影响的页面都不需要被复制，并且保持不变【33,34,35】。

使用仅追加的 B 树，每个写入事务（或一批事务）都会创建一颗新的 B 树，当创建时，从该特定树根生长的树就是数据库的一个一致性快照。没必要根据事务 ID 过滤掉对象，因为后续写入不能修改现有的 B 树；它们只能创建新的树根。但这种方法也需要一个负责压缩和垃圾收集的后台进程

防止丢失更新

读已提交和快照隔离主要保证了 只读事务在并发写入时 可以看到什么，却忽略了两个事务并发写入的问题。之前讨论了脏写，另一种特定类型的写-写冲突也是可能出现的。并发的写入事务之间还有其他几种有趣的冲突。其中最着名的是 丢失更新（lost update） 问题。

主要解决方案有：

  1. 原子写：如果可以用原子操作来表达，那这通常是最好的解决方案。
  2. 显示锁定：如果数据库的内置原子操作没有提供必要的功能，防止丢失更新的另一个选择是让应用程序显式地锁定将要更新的对象
  3. 自动检测丢失的更新
  4. 比较并设置（CAS）：只有当前值从上次读取时一直未改变，才允许更新发生
冲突解决和复制

由于在多个节点上存在数据副本，并且在不同节点上的数据可能被并发地修改，因此需要采取一些额外的步骤来防止丢失更新。

一种常见方法是允许并发写入创建多个冲突版本的值（也称为兄弟），并使用应用代码或特殊数据结构在事实发生之后解决和合并这些版本。

原子操作可以在复制的上下文中很好地工作，尤其当它们具有可交换性时（即，可以在不同的副本上以不同的顺序应用它们，且仍然可以得到相同的结果

写入偏斜与幻读

写偏差的特征：两个事务正在更新两个不同的对象。

可以将写入偏差视为丢失更新问题的一般化。如果两个事务读取相同的对象，然后更新其中一些对象（不同的事务可能更新不同的对象），则可能发生写入偏差。在多个事务更新同一个对象的特殊情况下，就会发生脏写或丢失更新（取决于时序）。

写入偏差的模式：

  1. 一个 SELECT 查询找出符合条件的行，并检查是否符合一些要求。

  2. 按照第一个查询的结果，应用代码决定是否继续。

  3. 如果应用决定继续操作，就执行写入（插入、更新或删除），并提交事务。这个写入的效果改变了步骤 2 中的先决条件。换句话说，如果在提交写入后，重复执行一次步骤 1 的 SELECT 查询，将会得到不同的结果。因为写入改变了符合搜索条件的行集。

一个事务中的写入改变另一个事务的搜索查询的结果，被称为 幻读

物化冲突：如果幻读的问题是没有对象可以加锁，也许可以人为地在数据库中引入一个锁对象。它将幻读变为数据库中一组具体行上的锁冲突

可串行化

可串行化（Serializability） 隔离通常被认为是最强的隔离级别。它保证即使事务可以并行执行，最终的结果也是一样的，就好像它们没有任何并发性，连续挨个执行一样

三种方案：

  1. 串行顺序执行事务（真的串行执行）
  2. 两阶段锁定（2PL, two-phase locking），几十年来唯一可行的选择
  3. 乐观并发控制技术，例如 可串行化快照隔离

真的串行（单线程）

存储过程与内存存储，使得在单个线程上执行所有事务变得可行。由于不需要等待 I/O，且避免了并发控制机制的开销，它们可以在单个线程上实现相当好的吞吐量。

分区

顺序执行所有事务使并发控制简单多了，但数据库的事务吞吐量被限制为单机单核的速度。只读事务可以使用快照隔离在其它地方执行，但对于写入吞吐量较高的应用，单线程事务处理器可能成为一个严重的瓶颈。

为了伸缩至多个 CPU 核心和多个节点，可以对数据进行分区。如果你可以找到一种对数据集进行分区的方法，以便每个事务只需要在单个分区中读写数据，那么每个分区就可以拥有自己独立运行的事务处理线程。在这种情况下可以为每个分区指派一个独立的 CPU 核，事务吞吐量就可以与 CPU 核数保持线性伸缩。

但是，对于需要访问多个分区的任何事务，数据库必须在触及的所有分区之间协调事务。存储过程需要跨越所有分区锁定执行，以确保整个系统的可串行性。

由于跨分区事务具有额外的协调开销，所以它们比单分区事务慢得多。 VoltDB 报告的吞吐量大约是每秒 1000 个跨分区写入，比单分区吞吐量低几个数量级，并且不能通过增加更多的机器来增加。

事务是否可以是划分至单个分区很大程度上取决于应用数据的结构。简单的键值数据通常可以非常容易地进行分区，但是具有多个次级索引的数据可能需要大量的跨分区协调。

串行执行小结

在特定约束条件下，真的串行执行事务，已经成为一种实现可串行化隔离等级的可行办法。

  • 每个事务都必须小而快，只要有一个缓慢的事务，就会拖慢所有事务处理。
  • 仅限于活跃数据集可以放入内存的情况。很少访问的数据可能会被移动到磁盘，但如果需要在单线程执行的事务中访问，系统就会变得非常慢 。
  • 写入吞吐量必须低到能在单个 CPU 核上处理，如若不然，事务需要能划分至单个分区，且不需要跨分区协调。
  • 跨分区事务是可能的，但是它们能被使用的程度有很大的限制。

两阶段锁定（2PL）

只要没有写入，就允许多个事务同时读取同一个对象。但对象只要有写入（修改或删除），就需要 独占访问（exclusive access） 权限。在 2PL 中，写入不仅会阻塞其他写入，也会阻塞读，反之亦然。快照隔离使得 读不阻塞写，写也不阻塞读，这是 2PL 和快照隔离之间的关键区别。

实现两阶段锁

读与写的阻塞是通过为数据库中每个对象添加锁来实现的。锁可以处于 共享模式（shared mode） 或 独占模式（exclusive mode）。锁使用如下：

  1. 若事务要读取对象，则须先以共享模式获取锁。允许多个事务同时持有共享锁。但如果另一个事务已经在对象上持有排它锁，则这些事务必须等待。

  2. 若事务要写入一个对象，它必须首先以独占模式获取该锁。没有其他事务可以同时持有锁（无论是共享模式还是独占模式），所以如果对象上存在任何锁，该事务必须等待。

  3. 如果事务先读取再写入对象，则它可能会将其共享锁升级为独占锁。升级锁的工作与直接获得排他锁相同。

  4. 事务获得锁之后，必须继续持有锁直到事务结束（提交或中止）。这就是 “两阶段” 这个名字的来源：第一阶段（当事务正在执行时）获取锁，第二阶段（在事务结束时）释放所有的锁。

由于使用了这么多的锁，因此很可能会发生：事务 A 等待事务 B 释放它的锁，反之亦然。这种情况叫做 死锁（Deadlock）。数据库会自动检测事务之间的死锁，并中止其中一个，以便另一个继续执行。被中止的事务需要由应用程序重试

两阶段锁定的性能

这一部分是由于获取和释放所有这些锁的开销，但更重要的是由于并发性的降低

2PL容易出现死锁，当事务由于死锁而被中止并被重试时，它需要从头重做它的工作。如果死锁很频繁，这可能意味着巨大的浪费。

谓词锁

它类似于前面描述的共享 / 排它锁，但不属于特定的对象（例如，表中的一行），它属于所有符合某些搜索条件的对象。

这里的关键思想是，谓词锁甚至适用于数据库中尚不存在，但将来可能会添加的对象（幻象）。如果两阶段锁定包含谓词锁，则数据库将阻止所有形式的写入偏差和其他竞争条件，因此其隔离实现了可串行化。

索引范围锁

不幸的是谓词锁性能不佳：如果活跃事务持有很多锁，检查匹配的锁会非常耗时。 因此，大多数使用 2PL 的数据库实际上实现了索引范围锁（index-range locking，也称为 next-key locking），这是一个简化的近似版谓词锁

通过使谓词匹配到一个更大的集合来简化谓词锁是安全的。

索引范围锁并不像谓词锁那样精确（它们可能会锁定更大范围的对象，而不是维持可串行化所必需的范围），但是由于它们的开销较低，所以是一个很好的折衷。

如果没有可以挂载范围锁的索引，数据库可以退化到使用整个表上的共享锁。

可串行化快照隔离

一方面，我们实现了性能不好（2PL）或者伸缩性不好（串行执行）的可串行化隔离级别。另一方面，我们有性能良好的弱隔离级别，但容易出现各种竞争条件（丢失更新，写入偏差，幻读等）

可串行化快照隔离提供了完整的可串行化隔离级别，但与快照隔离相比只有很小的性能损失。

悲观与乐观的并发控制

两阶段锁是一种所谓的 悲观并发控制机制（pessimistic） ：它是基于这样的原则：如果有事情可能出错（如另一个事务所持有的锁所表示的），最好等到情况安全后再做任何事情。这就像互斥，用于保护多线程编程中的数据结构。

相比之下，串行化快照隔离 是一种 乐观（optimistic） 的并发控制技术。在这种情况下，乐观意味着，如果存在潜在的危险也不阻止事务，而是继续执行事务，希望一切都会好起来。当一个事务想要提交时，数据库检查是否有什么不好的事情发生（即隔离是否被违反）；如果是的话，事务将被中止，并且必须重试。只有可串行化的事务才被允许提交。

基于过时前提的决策

  1. 检测对旧 MVCC 对象版本的读取（读之前存在未提交的写入）

  2. 检测影响先前读取的写入（读之后发生写入）

可串行化快照隔离的性能

与两阶段锁定相比，可串行化快照隔离的最大优点是一个事务不需要阻塞等待另一个事务所持有的锁。就像在快照隔离下一样，写不会阻塞读，反之亦然。这种设计原则使得查询延迟更可预测，变量更少。特别是，只读查询可以运行在一致快照上，而不需要任何锁定，这对于读取繁重的工作负载非常有吸引力。

与串行执行相比，可串行化快照隔离并不局限于单个 CPU 核的吞吐量：FoundationDB 将检测到的串行化冲突分布在多台机器上，允许扩展到很高的吞吐量。即使数据可能跨多台机器进行分区，事务也可以在保证可串行化隔离等级的同时读写多个分区中的数据。

中止率显著影响 SSI 的整体表现。

第八章 分布式系统的麻烦

故障与部分失效

在分布式系统中，尽管系统的其他部分工作正常，但系统的某些部分可能会以某种不可预知的方式被破坏。这被称为 部分失效（partial failure）。难点在于部分失效是 不确定性的（nonderterministic）：如果你试图做任何涉及多个节点和网络的事情，它有时可能会工作，有时会出现不可预知的失败。

云计算与超级计算机

关于如何构建大型计算系统有一系列的哲学：

  1. 一个极端是高性能计算（HPC）领域。
  2. 另一个极端是 云计算（cloud computing）
  3. 传统企业数据中心位于这两个极端之间。

从不可靠的组件构建可靠的系统

不可靠的网络

超时策略

真实世界的网络故障

检测故障

超时与无穷的延迟

同步网络与异步网络

不可靠的时钟

知识、真相与谎言

第九章 一致性与共识

构建容错系统的最好方法，是找到一些带有实用保证的通用抽象，实现一次，然后让应用依赖这些保证。如事务。

找到可以让应用忽略分布式系统部分问题的抽象概念。例如，分布式系统最重要的抽象之一就是 共识（consensus）：就是让所有的节点对某件事达成一致

了解可以做什么和不可以做什么的范围：在某些情况下，系统可以容忍故障并继续工作；在其他情况下，这是不可能的。我们将深入研究什么可能而什么不可能的限制，既通过理论证明，也通过实际实现。“分布式事务与共识 中，我们将研究解决共识和相关问题的算法

一致性保证

最终一致性：弱一致性模型

分布式一致性主要关于 在面对延迟和故障时如何协调副本间的状态。

线性一致性：最强一致性模型

基本的想法是让一个系统看起来好像只有一个数据副本，而且所有的操作都是原子性的。

要维护数据的单个副本的假象，系统应保障读到的值是最近的、最新的，而不是来自陈旧的缓存或副本。换句话说，线性一致性是一个 新鲜度保证（recency guarantee）

任何一个读取返回新值后，所有后续读取（在相同或其他客户端上）也必须返回新值。

依赖线性一致性的场景

分布式锁和领导选举

#####约束和唯一性保证

跨信道的时序依赖

实现线性一致的系统

单主复制（可能线性一致）

共识算法（线性一致）

多主复制（非线性一致）

无主复制（也许不是线性一致的）

线性一致性和法定人数

直觉上在 Dynamo 风格的模型中，严格的法定人数读写应该是线性一致性的。但是当我们有可变的网络延迟时，就可能存在竞争条件。

通过牺牲性能，可以使 Dynamo 风格的法定人数线性化：读取者必须在将结果返回给应用之前，同步执行读修复，并且写入者必须在发送写入之前，读取法定数量节点的最新状态。

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

线性一致性的代价

CAP（一致性，可用性和分区容错性） 更好的表述成：在分区时要么选择一致，要么选择可用。（分区是指网络分区（network partition）故障，而不是将大数据集细分为小数据集的操作（分片））

CAP 定理的正式定义仅限于很狭隘的范围，它只考虑了一个一致性模型（即线性一致性）和一种故障（网络分区 ，或活跃但彼此断开的节点）。它没有讨论任何关于网络延迟，死亡节点或其他权衡的事。避免使用CAP

线性一致性和网络延迟

虽然线性一致是一个很有用的保证，但实际上，线性一致的系统惊人的少。例如，现代多核 CPU 上的内存甚至都不是线性一致的【43】：如果一个 CPU 核上运行的线程写入某个内存地址，而另一个 CPU 核上运行的线程不久之后读取相同的地址，并没有保证一定能一定读到第一个线程写入的值（除非使用了 内存屏障（memory barrier） 或 围栏（fence）【44】）。

这种行为的原因是每个 CPU 核都有自己的内存缓存和存储缓冲区。默认情况下，内存访问首先走缓存，任何变更会异步写入主存。因为缓存访问比主存要快得多【45】，所以这个特性对于现代 CPU 的良好性能表现至关重要。但是现在就有几个数据副本（一个在主存中，也许还有几个在不同缓存中的其他副本），而且这些副本是异步更新的，所以就失去了线性一致性。

牺牲线性一致性的原因是 性能（performance），而不是容错。

许多分布式数据库也是如此：它们是 为了提高性能 而选择了牺牲线性一致性，而不是为了容错

能找到一个更高效的线性一致存储实现吗？看起来答案是否定的：Attiya 和 Welch 证明，如果你想要线性一致性，读写请求的响应时间至少与网络延迟的不确定性成正比。在像大多数计算机网络一样具有高度可变延迟的网络中，线性读写的响应时间不可避免地会很高。更快地线性一致算法不存在，但更弱的一致性模型可以快得多，所以对延迟敏感的系统而言，这类权衡非常重要。

顺序保证

顺序与因果关系

顺序 反复出现有几个原因，其中一个原因是，它有助于保持 因果关系（causality）。因果关系对事件施加了一种 顺序：因在果之前。

如果一个系统服从因果关系所规定的顺序，我们说它是 因果一致（causally consistent） 的

例如，快照隔离提供了因果一致性：当你从数据库中读取到一些数据时，你一定还能够看到其因果前驱

因果顺序不是全序的，全序（total order） 允许任意两个元素进行比较。

在线性一致的系统中，操作是全序的：如果系统表现的就好像只有一个数据副本，并且所有操作都是原子性的，这意味着对任何两个操作，我们总是能判定哪个操作先发生

因果关系定义了一个偏序，而不是一个全序：一些操作相互之间是有顺序的，但有些则是无法比较的。

在线性一致的数据存储中是不存在并发操作的：必须有且仅有一条时间线，所有的操作都在这条时间线上，构成一个全序关系。

并发意味着时间线会分岔然后合并 —— 在这种情况下，不同分支上的操作是无法比较的（即并发操作）。

线性一致性强于因果一致性

线性一致性 隐含着（implies） 因果关系，但线性一致性可能会损害性能和可用性，尤其是在系统具有严重的网络延迟的情况下

线性一致性并不是保持因果性的唯一途径 —— 还有其他方法。一个系统可以是因果一致的，而无需承担线性一致带来的性能折损（尤其对于 CAP 定理不适用的情况）。实际上在所有的不会被网络延迟拖慢的一致性模型中，因果一致性是可行的最强的一致性模型。而且在网络故障时仍能保持可用

捕获因果关系

序列号顺序

跟踪所有的因果关系是不切实际的

序列号提供了一个全序关系：也就是说每个操作都有一个唯一的序列号，而且总是可以比较两个序列号，确定哪一个更大。

特别是，我们可以使用 与因果一致（consistent with causality） 的全序来生成序列号 ：我们保证，如果操作 A 因果地发生在操作 B 前，那么在这个全序中 A 在 B 前（ A 具有比 B 更小的序列号）。并行操作之间可以任意排序。这样一个全序关系捕获了所有关于因果的信息，但也施加了一个比因果性要求更为严格的顺序。

非因果序列号生成器

主库不存在，生成序列号的方法：

  1. 每个节点都可以生成自己独立的一组序列号（奇数、偶数序列；二进制表示中预留一些位，用于唯一的节点标识符）
  2. 可以预先分配序列号区块

这些方法不能正确地捕获跨节点的操作顺序，生成的序列号与因果不一致：

  1. 每个节点每秒可以处理不同数量的操作。因此，如果一个节点产生偶数序列号而另一个产生奇数序列号，则偶数计数器可能落后于奇数计数器，反之亦然
  2. 来自物理时钟的时间戳会受到时钟偏移的影响，这可能会使其与因果不一致
  3. 在分配区块的情况下，某个操作可能会被赋予一个范围在 1,001 到 2,000 内的序列号，然而一个因果上更晚的操作可能被赋予一个范围在 1 到 1,000 之间的数字

每个节点都有一个唯一标识符，和一个保存自己执行操作数量的计数器。 兰伯特时间戳就是两者的简单组合：（计数器，节点 ID）$(counter, node ID)$

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

使兰伯特时间戳因果一致的关键思想如下所示：每个节点和每个客户端跟踪迄今为止所见到的最大 计数器 值，并在每个请求中包含这个最大计数器值。当一个节点收到最大计数器值大于自身计数器值的请求或响应时，它立即将自己的计数器设置为这个最大值。

版本向量可以区分两个操作是并发的，还是一个因果依赖另一个；而兰伯特时间戳总是施行一个全序。从兰伯特时间戳的全序中，你无法分辨两个操作是并发的还是因果依赖的。 兰伯特时间戳优于版本向量的地方是，它更加紧凑。

兰伯特时间戳的问题是，只有在所有的操作都被收集之后，操作的全序才会出现。如果另一个节点已经产生了一些操作，但你还不知道那些操作是什么，那就无法构造所有操作最终的全序关系：来自另一个节点的未知操作可能需要被插入到全序中的不同位置。

总之：为了实现诸如用户名上的唯一约束这种东西，仅有操作的全序是不够的，你还需要知道这个全序何时会尘埃落定

全序广播

单主复制通过选择一个节点作为主库来确定操作的全序，并在主库的单个 CPU 核上对所有操作进行排序。接下来的挑战是，如果吞吐量超出单个主库的处理能力，这种情况下如何扩展系统；以及，如果主库失效（“处理节点宕机”），如何处理故障切换。在分布式系统文献中，这个问题被称为 全序广播（total order broadcast）。

全序广播通常被描述为在节点间交换消息的协议。 非正式地讲，它要满足两个安全属性：

  • 可靠交付（reliable delivery）：没有消息丢失：如果消息被传递到一个节点，它将被传递到所有节点。
  • 全序交付（totally ordered delivery）消息以相同的顺序传递给每个节点。

像 ZooKeeper 和 etcd 这样的共识服务实际上实现了全序广播

全序广播正是数据库复制所需的：如果每个消息都代表一次数据库的写入，且每个副本都按相同的顺序处理相同的写入，那么副本间将相互保持一致（除了临时的复制延迟）。这个原理被称为 状态机复制

与之类似，可以使用全序广播来实现可串行化的事务：如果每个消息都表示一个确定性事务，以存储过程的形式来执行，且每个节点都以相同的顺序处理这些消息，那么数据库的分区和副本就可以相互保持一致

全序广播的一个重要表现是，顺序在消息送达时被固化：如果后续的消息已经送达，节点就不允许追溯地将（先前）消息插入顺序中的较早位置。这个事实使得全序广播比时间戳排序更强

全序广播对于实现提供防护令牌的锁服务也很有用（请参阅 “防护令牌”）。每个获取锁的请求都作为一条消息追加到日志末尾，并且所有的消息都按它们在日志中出现的顺序依次编号。序列号可以当成防护令牌用，因为它是单调递增的。在 ZooKeeper 中，这个序列号被称为 zxid

使用全序广播实现线性一致的存储

全序广播是异步的：消息被保证以固定的顺序可靠地传送，但是不能保证消息 何时 被送达（所以一个接收者可能落后于其他接收者）。相比之下，线性一致性是新鲜性的保证：读取一定能看见最新的写入值。

通过将全序广播当成仅追加日志的方式来实现这种线性一致的 CAS 操作：

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

由于日志项是以相同顺序送达至所有节点，因此如果有多个并发写入，则所有节点会对最先到达者达成一致。选择冲突写入中的第一个作为胜利者，并中止后来者，以此确定所有节点对某个写入是提交还是中止达成一致。类似的方法可以在一个日志的基础上实现可串行化的多对象事务

尽管这一过程保证写入是线性一致的，但它并不保证读取也是线性一致的 —— 如果你从与日志异步更新的存储中读取数据，结果可能是陈旧的。 （精确地说，这里描述的过程提供了 顺序一致性（sequential consistency）

为了使读取也线性一致，有几个选项：

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

该算法很简单：每个要通过全序广播发送的消息首先对线性一致寄存器执行 自增并返回 操作。然后将从寄存器获得的值作为序列号附加到消息中。然后你可以将消息发送到所有节点（重新发送任何丢失的消息），而收件人将按序列号依序传递（deliver）消息。

一般来说，如果你对线性一致性的序列号生成器进行过足够深入的思考，你不可避免地会得出一个共识算法。

这并非巧合：可以证明，线性一致的 CAS（或自增并返回）寄存器与全序广播都都等价于 共识 问题

分布式事务与共识

共识 是分布式计算中最重要也是最基本的问题之一，目标只是 让几个节点达成一致

共识在很多场景都非常重要：

  1. 领导选举
  2. 原子提交：在支持跨多节点或跨多分区事务的数据库中，一个事务可能在某些节点上失败，但在其他节点上成功。如果我们想要维护事务的原子性，我们必须让所有节点对事务的结果达成一致：要么全部中止 / 回滚（如果出现任何错误），要么它们全部提交（如果没有出错）。这个共识的例子被称为 原子提交（atomic commit） 问题 。原子提交的形式化与共识稍有不同：原子事务只有在 所有 参与者投票提交的情况下才能提交，如果有任何参与者需要中止，则必须中止。 共识则允许就 任意一个 被参与者提出的候选值达成一致。 然而，原子提交和共识可以相互简化为对方

原子提交与两阶段提交

事实证明 2PC 是一种共识算法，但不是一个非常好的共识算法

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

对于在单个数据库节点执行的事务，原子性通常由存储引擎实现。当客户端请求数据库节点提交事务时，数据库将使事务的写入（数据）持久化（通常在预写式日志中），然后将提交记录追加到磁盘中的日志里。如果数据库在这个过程中间崩溃，当节点重启时，事务会从日志中恢复：如果提交记录在崩溃之前成功地写入磁盘，则认为事务被提交；否则来自该事务的任何写入（数据）都被回滚

对于一个事务涉及多个节点的情况，仅向所有节点发送提交请求并独立提交每个节点的事务是不够的。这样很容易发生违反原子性的情况：提交在某些节点上成功，而在其他节点上失败，导致不一致。

事务提交必须是不可撤销的 —— 事务提交之后，你不能改变主意，并追溯性地中止事务。

两阶段提交简介

两阶段提交（two-phase commit） 是一种用于实现跨多个节点的原子事务提交的算法，即确保所有节点提交或所有节点中止。

2PC 中的提交 / 中止过程分为两个阶段（因此而得名），而不是单节点事务中的单个提交请求。

img

2PC 使用一个通常不会出现在单节点事务中的新组件：协调者（以库或单独服务的形式出现）

正常情况下，2PC 事务以应用在多个数据库节点上读写数据开始。我们称这些数据库节点为 参与者（participants）

当应用准备提交时，协调者开始阶段 1 ：它发送一个 准备（prepare） 请求到每个节点，询问它们是否能够提交。然后协调者会跟踪参与者的响应：

  1. 如果所有参与者都回答 “是”，表示它们已经准备好提交，那么协调者在阶段 2 发出 提交（commit） 请求，然后提交真正发生。

  2. 如果任意一个参与者回复了 “否”，则协调者在阶段 2 中向所有节点发送 中止（abort） 请求。

为什么两阶段提交保证了原子性，工作原理：

  1. 当应用想要启动一个分布式事务时，它向协调者请求一个事务 ID。此事务 ID 是全局唯一的。

  2. 应用在每个参与者上启动单节点事务，并在单节点事务上捎带上这个全局事务 ID。所有的读写都是在这些单节点事务中各自完成的。如果在这个阶段出现任何问题（例如，节点崩溃或请求超时），则协调者或任何参与者都可以中止。

  3. 当应用准备提交时，协调者向所有参与者发送一个 准备 请求，并打上全局事务 ID 的标记。如果任意一个请求失败或超时，则协调者向所有参与者发送针对该事务 ID 的中止请求。

  4. 参与者收到准备请求时，需要确保在任意情况下都的确可以提交事务。这包括将所有事务数据写入磁盘（出现故障，电源故障，或硬盘空间不足都不能是稍后拒绝提交的理由）以及检查是否存在任何冲突或违反约束。通过向协调者回答 “是”，节点承诺，只要请求，这个事务一定可以不出差错地提交。换句话说，参与者放弃了中止事务的权利，但没有实际提交。

  5. 当协调者收到所有准备请求的答复时，会就提交或中止事务作出明确的决定（只有在所有参与者投赞成票的情况下才会提交）。协调者必须把这个决定写到磁盘上的事务日志中，如果它随后就崩溃，恢复后也能知道自己所做的决定。这被称为 提交点（commit point）。

  6. 一旦协调者的决定落盘，提交或放弃请求会发送给所有参与者。如果这个请求失败或超时，协调者必须永远保持重试，直到成功为止。没有回头路：如果已经做出决定，不管需要多少次重试它都必须被执行。如果参与者在此期间崩溃，事务将在其恢复后提交 —— 由于参与者投了赞成，因此恢复后它不能拒绝提交。

因此，该协议包含两个关键的 “不归路” 点：当参与者投票 “是” 时，它承诺它稍后肯定能够提交（尽管协调者可能仍然选择放弃）；

以及一旦协调者做出决定，这一决定是不可撤销的。这些承诺保证了 2PC 的原子性

协调者失效

在 2PC 期间，如果参与者之一或网络发生故障时会发生什么情况：如果任何一个 准备 请求失败或者超时，协调者就会中止事务。如果任何提交或中止请求失败，协调者将无条件重试。

如果协调者在发送 准备 请求之前失败，参与者可以安全地中止事务。但是，一旦参与者收到了准备请求并投了 “是”，就不能再单方面放弃 —— 必须等待协调者回答事务是否已经提交或中止。如果此时协调者崩溃或网络出现故障，参与者什么也做不了只能等待。参与者的这种事务状态称为 存疑（in doubt） 的或 不确定（uncertain） 的。

可以完成 2PC 的唯一方法是等待协调者恢复。这就是为什么协调者必须在向参与者发送提交或中止请求之前，将其提交或中止决定写入磁盘上的事务日志：协调者恢复后，通过读取其事务日志来确定所有存疑事务的状态。任何在协调者日志中没有提交记录的事务都会中止。因此，2PC 的 提交点 归结为协调者上的常规单节点原子提交。

两阶段提交被称为 阻塞（blocking）- 原子提交协议，因为存在 2PC 可能卡住并等待协调者恢复的情况。

三阶段提交

3PC 假定网络延迟有界，节点响应时间有限；在大多数具有无限网络延迟和进程暂停的实际系统中，它并不能保证原子性。

实践中的分布式事务

通过两阶段提交实现的分布式事务，一方面，它被视作提供了一个难以实现的重要的安全性保证；另一方面，它们因为导致运维问题，造成性能下降，做出超过能力范围的承诺而饱受批评。两阶段提交所固有的性能成本，大部分是由于崩溃恢复所需的额外强制刷盘（fsync）以及额外的网络往返。

两种截然不同的分布式事务类型经常被混淆：

  • 数据库内部的分布式事务

    一些分布式数据库（即在其标准配置中使用复制和分区的数据库）支持数据库节点之间的内部事务。在这种情况下，所有参与事务的节点都运行相同的数据库软件。

  • 异构分布式事务

    在 异构（heterogeneous） 事务中，参与者是由两种或两种以上的不同技术组成的：例如来自不同供应商的两个数据库，甚至是非数据库系统（如消息代理）。跨系统的分布式事务必须确保原子提交，尽管系统可能完全不同。

恰好一次的消息处理

异构的分布式事务处理能够以强大的方式集成不同的系统。消息队列中的一条消息可以被确认为已处理，当且仅当用于处理消息的数据库事务成功提交，这是通过在同一个事务中原子提交 消息确认 和 数据库写入 两个操作来实现的。

只有当所有受事务影响的系统都使用同样的 原子提交协议（atomic commit protocol） 时，这样的分布式事务才是可能的

XA事务

X/Open XA（扩展架构（eXtended Architecture） 的缩写）是跨异构技术实现两阶段提交的标准

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

XA 假定你的应用使用网络驱动或客户端库来与 参与者（数据库或消息服务）进行通信。如果驱动支持 XA，则意味着它会调用 XA API 以查明操作是否为分布式事务的一部分 —— 如果是，则将必要的信息发往数据库服务器。驱动还会向协调者暴露回调接口，协调者可以通过回调来要求参与者准备、提交或中止。

事务协调者需要实现 XA API。标准没有指明应该如何实现，但实际上协调者通常只是一个库，被加载到发起事务的应用的同一个进程中（而不是单独的服务）。它在事务中跟踪所有的参与者，并在要求它们 准备 之后收集参与者的响应（通过驱动回调），并使用本地磁盘上的日志记录每次事务的决定（提交 / 中止）。

如果应用进程崩溃，或者运行应用的机器报销了，协调者也随之往生极乐。然后任何带有 准备了 但未提交事务的参与者都会在疑虑中卡死。由于协调程序的日志位于应用服务器的本地磁盘上，因此必须重启该服务器，且协调程序库必须读取日志以恢复每个事务的提交 / 中止结果。只有这样，协调者才能使用数据库驱动的 XA 回调来要求参与者提交或中止。数据库服务器不能直接联系协调者，因为所有通信都必须通过客户端库。

怀疑时持有锁

为什么我们这么关心存疑事务？问题在于 锁（locking），在事务提交或中止之前，数据库不能释放这些锁。

因此，在使用两阶段提交时，事务必须在整个存疑期间持有这些锁。如果协调者已经崩溃，需要 20 分钟才能重启，那么这些锁将会被持有 20 分钟。如果协调者的日志由于某种原因彻底丢失，这些锁将被永久持有 —— 或至少在管理员手动解决该情况之前。

从协调者故障中恢复

理论上，如果协调者崩溃并重新启动，它应该干净地从日志中恢复其状态，并解决任何存疑事务。然而在实践中，孤立（orphaned） 的存疑事务确实会出现，即无论出于何种理由，协调者无法确定事务的结果（例如事务日志已经由于软件错误丢失或损坏）。这些事务无法自动解决，所以它们永远待在数据库中，持有锁并阻塞其他事务。

即使重启数据库服务器也无法解决这个问题，因为在 2PC 的正确实现中，即使重启也必须保留存疑事务的锁（否则就会冒违反原子性保证的风险）。这是一种棘手的情况。

唯一的出路是让管理员手动决定提交还是回滚事务。管理员必须检查每个存疑事务的参与者，确定是否有任何参与者已经提交或中止，然后将相同的结果应用于其他参与者。解决这个问题潜在地需要大量的人力，并且可能发生在严重的生产中断期间（不然为什么协调者处于这种糟糕的状态），并很可能要在巨大精神压力和时间压力下完成。

许多 XA 的实现都有一个叫做 启发式决策（heuristic decisions） 的紧急逃生舱口：允许参与者单方面决定放弃或提交一个存疑事务，而无需协调者做出最终决定。要清楚的是，这里 启发式 是 可能破坏原子性（probably breaking atomicity） 的委婉说法，因为它违背了两阶段提交的系统承诺。因此，启发式决策只是为了逃出灾难性的情况而准备的，而不是为了日常使用的。

分布式事务的限制

XA 事务解决了保持多个参与者（数据系统）相互一致的现实的和重要的问题，但正如我们所看到的那样，它也引入了严重的运维问题。特别来讲，这里的核心认识是：事务协调者本身就是一种数据库（存储了事务的结果），因此需要像其他重要数据库一样小心地打交道：

  • 如果协调者没有复制，而是只在单台机器上运行，那么它是整个系统的失效单点
  • 许多服务器端应用都是使用无状态模式开发的（受 HTTP 的青睐），所有持久状态都存储在数据库中，因此具有应用服务器可随意按需添加删除的优点。但是，当协调者成为应用服务器的一部分时，它会改变部署的性质。突然间，协调者的日志成为持久系统状态的关键部分 —— 与数据库本身一样重要，因为协调者日志是为了在崩溃后恢复存疑事务所必需的。这样的应用服务器不再是无状态的了。
  • 由于 XA 需要兼容各种数据系统，因此它必须是所有系统的最小公分母。例如，它不能检测不同系统间的死锁（因为这将需要一个标准协议来让系统交换每个事务正在等待的锁的信息），而且它无法与 SSI（请参阅 可串行化快照隔离）协同工作，因为这需要一个跨系统定位冲突的协议。
  • 对于数据库内部的分布式事务（不是 XA），限制没有这么大 —— 例如，分布式版本的 SSI 是可能的。然而仍然存在问题：2PC 成功提交一个事务需要所有参与者的响应。因此，如果系统的 任何 部分损坏，事务也会失败。因此，分布式事务又有 扩大失效（amplifying failures） 的趋势，这又与我们构建容错系统的目标背道而驰。

这些事实是否意味着我们应该放弃保持几个系统相互一致的所有希望？不完全是 —— 还有其他的办法，可以让我们在没有异构分布式事务的痛苦的情况下实现同样的事情。我们将在 第十一章 和 第十二章 回到这些话题。但首先，我们应该概括一下关于 共识 的话题。

容错共识

共识问题通常形式化如下：一个或多个节点可以 提议（propose） 某些值，而共识算法 决定（decides） 采用其中的某个值。

在这种形式下，共识算法必须满足以下性质:

  1. 一致同意（Uniform agreement）

    没有两个节点的决定不同。

  2. 完整性（Integrity）

    没有节点决定两次。

  3. 有效性（Validity）

    如果一个节点决定了值 v ，则 v 由某个节点所提议。

  4. 终止（Termination）

    由所有未崩溃的节点来最终决定值。

一致同意 和 完整性 属性定义了共识的核心思想：所有人都决定了相同的结果，一旦决定了，你就不能改变主意。有效性 属性主要是为了排除平凡的解决方案：例如，无论提议了什么值，你都可以有一个始终决定值为 null 的算法,该算法满足 一致同意 和 完整性 属性，但不满足 有效性 属性

如果不关心容错，那么满足前三个属性很容易：你可以将一个节点硬编码为 “独裁者”，并让该节点做出所有的决定。但如果该节点失效，那么系统就无法再做出任何决定。事实上，这就是我们在两阶段提交的情况中所看到的：如果协调者失效，那么存疑的参与者就无法决定提交还是中止。

终止 属性形式化了容错的思想。它实质上说的是，一个共识算法不能简单地永远闲坐着等死 —— 换句话说，它必须取得进展。即使部分节点出现故障，其他节点也必须达成一项决定（终止 是一种 活性属性，而另外三种是 安全属性 —— 请参阅 “安全性和活性”）

共识的系统模型假设，当一个节点 “崩溃” 时，它会突然消失而且永远不会回来。在这个系统模型中，任何需要等待节点恢复的算法都不能满足 终止 属性。特别是，2PC 不符合终止属性的要求。

当然如果 所有 的节点都崩溃了，没有一个在运行，那么所有算法都不可能决定任何事情。算法可以容忍的失效数量是有限的：事实上可以证明，任何共识算法都需要至少占总体 多数（majority） 的节点正确工作，以确保终止属性。多数可以安全地组成法定人数

因此 终止 属性取决于一个假设，不超过一半的节点崩溃或不可达。然而即使多数节点出现故障或存在严重的网络问题，绝大多数共识的实现都能始终确保安全属性得到满足 —— 一致同意，完整性和有效性。因此，大规模的中断可能会阻止系统处理请求，但是它不能通过使系统做出无效的决定来破坏共识系统。

大多数共识算法假设不存在 拜占庭式错误，正如在 “拜占庭故障” 一节中所讨论的那样。也就是说，如果一个节点没有正确地遵循协议（例如，如果它向不同节点发送矛盾的消息），它就可能会破坏协议的安全属性。克服拜占庭故障，稳健地达成共识是可能的，只要少于三分之一的节点存在拜占庭故障

共识算法和全序广播

最著名的容错共识算法是 视图戳复制（VSR, Viewstamped Replication），Paxos ，Raft 以及 Zab

大多数这些算法实际上并不直接使用这里描述的形式化模型（提议与决定单个值，并满足一致同意、完整性、有效性和终止属性）。取而代之的是，它们决定了值的 顺序（sequence），这使它们成为全序广播算法。

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

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

  • 由于 一致同意 属性，所有节点决定以相同的顺序传递相同的消息。
  • 由于 完整性 属性，消息不会重复。
  • 由于 有效性 属性，消息不会被损坏，也不能凭空编造。
  • 由于 终止 属性，消息不会丢失。

视图戳复制，Raft 和 Zab 直接实现了全序广播，因为这样做比重复 一次一值（one value a time） 的共识更高效。在 Paxos 的情况下，这种优化被称为 Multi-Paxos。

单领导者复制与共识

如果主库是由运维人员手动选择和配置的，那么你实际上拥有一种 独裁类型 的 “共识算法”：只有一个节点被允许接受写入（即决定写入复制日志的顺序），如果该节点发生故障，则系统将无法写入，直到运维手动配置其他节点作为主库。这样的系统在实践中可以表现良好，但它无法满足共识的 终止 属性，因为它需要人为干预才能取得 进展。一些数据库会自动执行领导者选举和故障切换，如果旧主库失效，会提拔一个从库为新主库。这使我们向容错的全序广播更进一步，从而达成共识。

选出一位领导者需要共识。但如果这里描述的共识算法实际上是全序广播算法，并且全序广播就像单主复制，而单主复制需要一个领导，从而导致先有鸡还是先有蛋的问题

纪元编号和法定人数

迄今为止所讨论的所有共识协议，在内部都以某种形式使用一个领导者，但它们并不能保证领导者是独一无二的。相反，它们可以做出更弱的保证：协议定义了一个 纪元编号并确保在每个时代中，领导者都是唯一的

每次当现任领导被认为挂掉的时候，节点间就会开始一场投票，以选出一个新领导。这次选举被赋予一个递增的纪元编号，因此纪元编号是全序且单调递增的。如果两个不同的时代的领导者之间出现冲突（也许是因为前任领导者实际上并未死亡），那么带有更高纪元编号的领导说了算

在任何领导者被允许决定任何事情之前，必须先检查是否存在其他带有更高纪元编号的领导者，它们可能会做出相互冲突的决定。

它必须从 法定人数（quorum） 的节点中获取选票。对领导者想要做出的每一个决定，都必须将提议值发送给其他节点，并等待法定人数的节点响应并赞成提案。法定人数通常（但不总是）由多数节点组成。只有在没有意识到任何带有更高纪元编号的领导者的情况下，一个节点才会投票赞成提议。

因此，我们有两轮投票：第一次是为了选出一位领导者，第二次是对领导者的提议进行表决。关键的洞察在于，这两次投票的 法定人群 必须相互 重叠（overlap）：如果一个提案的表决通过，则至少得有一个参与投票的节点也必须参加过最近的领导者选举

因此，如果在一个提案的表决过程中没有出现更高的纪元编号。那么现任领导者就可以得出这样的结论：没有发生过更高时代的领导选举，因此可以确定自己仍然在领导。然后它就可以安全地对提议值做出决定。

这一投票过程表面上看起来很像两阶段提交。最大的区别在于，2PC 中协调者不是由选举产生的，而且 2PC 则要求 所有 参与者都投赞成票，而容错共识算法只需要多数节点的投票。而且，共识算法还定义了一个恢复过程，节点可以在选举出新的领导者之后进入一个一致的状态，确保始终能满足安全属性。这些区别正是共识算法正确性和容错性的关键。

共识的局限性

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

节点在做出决定之前对提议进行投票的过程是一种同步复制。

共识系统总是需要严格多数来运转。如果网络故障切断了某些节点同其他节点的连接，则只有多数节点所在的网络可以继续工作，其余部分将被阻塞

大多数共识算法假定参与投票的节点是固定的集合，这意味着你不能简单的在集群中添加或删除节点。共识算法的 动态成员扩展（dynamic membership extension） 允许集群中的节点集随时间推移而变化，但是它们比静态成员算法要难理解得多。

共识系统通常依靠超时来检测失效的节点。在网络延迟高度变化的环境中，特别是在地理上散布的系统中，经常发生一个节点由于暂时的网络问题，错误地认为领导者已经失效。虽然这种错误不会损害安全属性，但频繁的领导者选举会导致糟糕的性能表现，因系统最后可能花在权力倾扎上的时间要比花在建设性工作的多得多。

有时共识算法对网络问题特别敏感。

成员与协调服务

像 ZooKeeper 或 etcd 这样的项目通常被描述为 “分布式键值存储” 或 “协调与配置服务”。这种服务的 API 看起来非常像数据库：你可以读写给定键的值，并遍历键。所以如果它们基本上算是数据库的话，为什么它们要把工夫全花在实现一个共识算法上呢？

ZooKeeper 和 etcd 被设计为容纳少量完全可以放在内存中的数据（虽然它们仍然会写入磁盘以保证持久性），所以你不会想着把所有应用数据放到这里。这些少量数据会通过容错的全序广播算法复制到所有节点上。

ZooKeeper 模仿了 Google 的 Chubby 锁服务，不仅实现了全序广播（因此也实现了共识），而且还构建了一组有趣的其他特性，这些特性在构建分布式系统时变得特别有用：

  1. 线性一致性的原子操作

    使用原子 CAS 操作可以实现锁：如果多个节点同时尝试执行相同的操作，只有一个节点会成功

  2. 操作的全序排序

    当某个资源受到锁或租约的保护时，你需要一个防护令牌来防止客户端在进程暂停的情况下彼此冲突。防护令牌是每次锁被获取时单调增加的数字。ZooKeeper 通过全序化所有操作来提供这个功能，它为每个操作提供一个单调递增的事务 ID（zxid）和版本号（cversion）

  3. 失效检测

    客户端在 ZooKeeper 服务器上维护一个长期会话，客户端和服务器周期性地交换心跳包来检查节点是否还活着

  4. 变更通知

    客户端不仅可以读取其他客户端创建的锁和值，还可以监听它们的变更。通过订阅通知，客户端不用再通过频繁轮询的方式来找出变更。

在这些功能中，只有线性一致的原子操作才真的需要共识。但正是这些功能的组合，使得像 ZooKeeper 这样的系统在分布式协调中非常有用。

将工作分配给节点

ZooKeeper/Chubby 模型运行良好的一个例子是，如果你有几个进程实例或服务，需要选择其中一个实例作为主库或首选服务。如果领导者失败，其他节点之一应该接管。这对单主数据库当然非常实用，但对作业调度程序和类似的有状态系统也很好用。

另一个例子是，当你有一些分区资源（数据库，消息流，文件存储，分布式 Actor 系统等），并需要决定将哪个分区分配给哪个节点时。当新节点加入集群时，需要将某些分区从现有节点移动到新节点，以便重新平衡负载（请参阅 “分区再平衡”）。当节点被移除或失效时，其他节点需要接管失效节点的工作。

这类任务可以通过在 ZooKeeper 中明智地使用原子操作，临时节点与通知来实现。如果设计得当，这种方法允许应用自动从故障中恢复而无需人工干预。

应用最初只能在单个节点上运行，但最终可能会增长到数千个节点。试图在如此之多的节点上进行多数投票将是非常低效的。相反，ZooKeeper 在固定数量的节点（通常是三到五个）上运行，并在这些节点之间执行其多数票，同时支持潜在的大量客户端。因此，ZooKeeper 提供了一种将协调节点（共识，操作排序和故障检测）的一些工作 “外包” 到外部服务的方式。

通常，由 ZooKeeper 管理的数据类型的变化十分缓慢：代表 “分区 7 中的节点运行在 10.1.1.23 上” 的信息可能会在几分钟或几小时的时间内发生变化。它不是用来存储应用的运行时状态的，后者每秒可能会改变数千甚至数百万次。如果应用状态需要从一个节点复制到另一个节点，则可以使用其他工具（如 Apache BookKeeper 【108】）

服务发现

ZooKeeper、etcd 和 Consul 也经常用于服务发现 —— 也就是找出你需要连接到哪个 IP 地址才能到达特定的服务。

但是，服务发现是否需要达成共识还不太清楚。 DNS 是查找服务名称的 IP 地址的传统方式，它使用多层缓存来实现良好的性能和可用性。从 DNS 读取是绝对不线性一致性的，如果 DNS 查询的结果有点陈旧，通常不会有问题【109】。 DNS 的可用性和对网络中断的鲁棒性更重要。

尽管服务发现并不需要共识，但领导者选举却是如此。因此，如果你的共识系统已经知道领导是谁，那么也可以使用这些信息来帮助其他服务发现领导是谁。为此，一些共识系统支持只读缓存副本。这些副本异步接收共识算法所有决策的日志，但不主动参与投票。因此，它们能够提供不需要线性一致性的读取请求。

成员资格服务

成员资格服务确定哪些节点当前处于活动状态并且是集群的活动成员。正如我们在 第八章 中看到的那样，由于无限的网络延迟，无法可靠地检测到另一个节点是否发生故障。但是，如果你通过共识来进行故障检测，那么节点可以就哪些节点应该被认为是存在或不存在达成一致。

即使它确实存在，仍然可能发生一个节点被共识错误地宣告死亡。但是对于一个系统来说，知道哪些节点构成了当前的成员关系是非常有用的。例如，选择领导者可能意味着简单地选择当前成员中编号最小的成员，但如果不同的节点对现有的成员都有谁有不同意见，则这种方法将不起作用。

第三部分 衍生数据

应用程序通常组合使用多种组件：数据存储，索引，缓存，分析系统，等等，并实现在这些组件中移动数据的机制。

研究将多个不同数据系统集成为一个协调一致的应用架构时，会遇到的问题

从高层次上看，存储和处理数据的系统可以分为两大类：

  1. 记录系统（System of record）

    记录系统，也被称为 真相源（source of truth），持有数据的权威版本。当新的数据进入时（例如，用户输入）首先会记录在这里。每个事实正正好好表示一次（表示通常是 正规化的，即 normalized）。

  2. 衍生数据系统（Derived data systems）

    衍生系统 中的数据，通常是另一个系统中的现有数据以某种方式进行转换或处理的结果。如果丢失衍生数据，可以从原始来源重新创建。典型的例子是 缓存（cache）

大多数数据库，存储引擎和查询语言，本质上既不是记录系统也不是衍生系统。数据库只是一个工具：如何使用它取决于你自己。记录系统和衍生数据系统之间的区别不在于工具，而在于应用程序中的使用方式。

第十章 批处理

使用unix工具的批处理

Unix 哲学：

  1. 让每个程序都做好一件事。要做一件新的工作，写一个新程序，而不是通过添加 “功能” 让老程序复杂化。
  2. 期待每个程序的输出成为另一个程序的输入。不要将无关信息混入输出。避免使用严格的列数据或二进制输入格式。不要坚持交互式输入。
  3. 设计和构建软件时，即使是操作系统，也让它们能够尽早地被试用，最好在几周内完成。不要犹豫，扔掉笨拙的部分，重建它们。
  4. 优先使用工具来减轻编程任务，即使必须曲线救国编写工具，且在用完后很可能要扔掉大部分。

这种方法 —— 自动化，快速原型设计，增量式迭代，对实验友好，将大型项目分解成可管理的块 —— 听起来非常像今天的敏捷开发和 DevOps 运动。奇怪的是，四十年来变化不大。

统一的接口:在 Unix 中，这种接口是一个 文件（file，更准确地说，是一个文件描述符) 。一个文件只是一串有序的字节序列

Unix 工具的另一个特点是使用标准输入（stdin）和标准输出（stdout）

MapReduce 和分布式文件系统

第十一章 流处理