数据密集型应用系统设计

前言

DDIA 在大一的时候就有前辈推荐，碍于时间一直没空阅读，恰逢最近考试复习太枯燥且不想内耗于活水的焦虑感中，正好把这本书好好读一下，也做一个阅读笔记方便未来重新思考。

2023.1.13

第一章：可靠性、可伸缩性和可维护性

关于数据系统的思考

数据库、消息队列、缓存等工具分属于几个差异显著的类别。虽然数据库和消息队列表面上有一些相似性但它们有迥然不同的访问模式，这意味着迥异的性能特征和实现手段。

近些年来，出现了许多新的工具。它们针对不同应用场景进行优化，因此不再适合生硬地归入传统类别。类别之间的界限变得越来越模糊，例如：数据存储可以被当成消息队列用（Redis），消息队列则带有类似数据库的持久保证（Apache Kafka）。

越来越多的应用程序有着各种严格而广泛的要求，单个工具不足以满足所有需求。取而代之的是，总体工作被拆分成一系列能被单个工具高效完成的任务，并通过应用代码将它们缝合起来。

可靠性

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

注意 故障（fault） 不同于 失效（failure）。故障 通常定义为系统的一部分状态偏离其标准，而 失效 则是系统作为一个整体停止向用户提供服务。故障的概率不可能降到零，因此最好设计容错机制以防因 故障 而导致 失效。

反直觉的是，在这类容错系统中，通过故意触发来 提高 故障率是有意义的，例如：在没有警告的情况下随机地杀死单个进程。许多高危漏洞实际上是由糟糕的错误处理导致的，因此我们可以通过故意引发故障来确保容错机制不断运行并接受考验，从而提高故障自然发生时系统能正确处理的信心。

硬件故障

硬盘的 平均无故障时间（MTTF, mean time to failure） 约为 10 到 50 年。因此从数学期望上讲，在拥有 10000 个磁盘的存储集群上，平均每天会有 1 个磁盘出故障。

为了减少系统的故障率，第一反应通常都是增加单个硬件的冗余度，例如：磁盘可以组建 RAID，服务器可能有双路电源和热插拔 CPU，数据中心可能有电池和柴油发电机作为后备电源，某个组件挂掉时冗余组件可以立刻接管。

如果在硬件冗余的基础上进一步引入软件容错机制，那么系统在容忍整个（单台）机器故障的道路上就更进一步了。这样的系统也有运维上的便利，例如：如果需要重启机器，单服务器系统就需要计划停机。而允许机器失效的系统则可以一次修复一个节点，无需整个系统停机。

软件错误

这类错误难以预料，而且因为是跨节点相关的，所以比起不相关的硬件故障往往可能造成更多的 系统失效。比如失控进程会用尽一些共享资源，包括 CPU 时间、内存、磁盘空间或网络带宽。

导致这类软件故障的 BUG 通常会潜伏很长时间，直到被异常情况触发为止。虽然软件中的系统性故障没有速效药，但我们还是有很多小办法，例如：仔细考虑系统中的假设和交互；彻底的测试；进程隔离；允许进程崩溃并重启；监控并分析生产环境中的系统行为。如果系统能够提供一些保证（例如在一个消息队列中，进入与发出的消息数量相等），那么系统就可以在运行时不断自检，并在出现 差异（discrepancy） 时报警。

人为错误

一项关于大型互联网服务的研究发现，运维配置错误是导致服务中断的首要原因，而硬件故障（服务器或网络）仅导致了 10-25% 的服务中断。

尽管人类不可靠，但怎么做才能让系统变得可靠？最好的系统会组合使用以下几种办法：

  • 以最小化犯错机会的方式设计系统。例如，精心设计的抽象、API 和管理后台使做对事情更容易，搞砸事情更困难。但如果接口限制太多，人们就会忽略它们的好处而想办法绕开。很难正确把握这种微妙的平衡。

  • 将人们最容易犯错的地方与可能导致失效的地方 解耦（decouple）。特别是提供一个功能齐全的非生产环境 沙箱（sandbox），使人们可以在不影响真实用户的情况下，使用真实数据安全地探索和实验。

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

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

  • 配置详细和明确的监控，比如性能指标和错误率。 在其他工程学科中这指的是 遥测（telemetry）。监控可以向我们发出预警信号，并允许我们检查是否有任何地方违反了假设和约束。

  • 良好的管理实践与充分的培训 —— 一个复杂而重要的方面，但超出了本书的范围。

可靠性的重要性

可靠性不仅仅是针对核电站和空中交通管制软件而言，我们也期望更多平凡的应用能可靠地运行。商务应用中的错误会导致生产力损失，而电商网站的中断则可能会导致收入和声誉的巨大损失。

在某些情况下，我们可能会选择牺牲可靠性来降低开发成本或运营成本，但我们偷工减料时，应该清楚意识到自己在做什么。

DDIA 预言了一切

可伸缩性

可伸缩性（Scalability） 是用来描述系统应对负载增长能力的术语。但是请注意，这不是贴在系统上的一维标签：说 “X 可伸缩” 或 “Y 不可伸缩” 是没有任何意义的。相反，讨论可伸缩性意味着考虑诸如 “如果系统以特定方式增长，有什么选项可以应对增长？” 和 “如何增加计算资源来处理额外的负载？” 等问题。

描述负载

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

Eg. 推特发布贴文 & 主页时间线

大体上讲，这一对操作有两种实现方式。

  1. 发布推文时，只需将新推文插入全局推文集合即可。当一个用户请求自己的主页时间线时，首先查找他关注的所有人，查询这些被关注用户发布的推文并按时间顺序合并。

    SELECT tweets.*, users.*
  FROM tweets
  JOIN users   ON tweets.sender_id = users.id
  JOIN follows ON follows.followee_id = users.id
  WHERE follows.follower_id = current_user

  2. 为每个用户的主页时间线维护一个缓存。 当一个用户发布推文时，查找所有关注该用户的人，并将新的推文插入到每个主页时间线缓存中。

方法 1 系统很难跟上主页时间线查询的负载。方法 2 的效果更好，因为发推频率比查询主页时间线的频率几乎低了两个数量级，所以在这种情况下，最好在写入时做更多的工作，而在读取时做更少的工作。

然而方法 2 的缺点是，发推现在需要大量的额外工作。平均来说，一条推文会发往约 75 个关注者，所以每秒 4.6k 的发推写入，变成了对主页时间线缓存每秒 345k 的写入。但这个平均值隐藏了用户粉丝数差异巨大这一现实，一些用户有超过 3000 万的粉丝，这意味着一条推文就可能会导致主页时间线缓存的 3000 万次写入！

推特轶事的最终转折：推特逐步转向了两种方法的混合。大多数用户发的推文会被扇出写入其粉丝主页时间线缓存中。但是少数拥有海量粉丝的用户（即名流）会被排除在外。当用户读取主页时间线时，分别地获取出该用户所关注的每位名流的推文，再与用户的主页时间线缓存合并。

描述性能

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

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

对于 Hadoop 这样的批处理系统，通常关心的是 吞吐量（throughput），即每秒可以处理的记录数量，或者在特定规模数据集上运行作业的总时间。对于在线系统，通常更重要的是服务的 响应时间（response time），即客户端发送请求到接收响应之间的时间。

即使不断重复发送同样的请求，每次得到的响应时间也都会略有不同。现实世界的系统会处理各式各样的请求，响应时间可能会有很大差异。因此我们需要将响应时间视为一个可以测量的数值 分布（distribution），而不是单个数值。

如果想知道典型场景下用户需要等待多长时间，那么中位数是一个好的度量标准：一半用户请求的响应时间少于响应时间的中位数，另一半服务时间比中位数长。中位数也被称为第 50 百分位点，有时缩写为 p50。

响应时间的高百分位点（也称为 尾部延迟，即 tail latencies）非常重要，因为它们直接影响用户的服务体验。例如亚马逊在描述内部服务的响应时间要求时是以 99.9 百分位点为准，即使它只影响一千个请求中的一个。这是因为请求响应最慢的客户往往也是数据最多的客户，也可以说是最有价值的客户 —— 因为他们掏钱了。

百分位点通常用于 服务级别目标（SLO, service level objectives） 和 服务级别协议（SLA, service level agreements）。 SLA 可能会声明，如果服务响应时间的中位数小于 200 毫秒，且 99.9 百分位点低于 1 秒，则认为服务工作正常。这些指标为客户设定了期望值，并允许客户在 SLA 未达标的情况下要求退款。

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

在多重调用的后端服务里，高百分位数变得特别重要。即使并行调用，最终用户请求仍然需要等待最慢的并行调用完成。只需要一个缓慢的调用就可以使整个最终用户请求变慢。即使只有一小部分后端调用速度较慢，如果最终用户请求需要多个后端调用，则获得较慢调用的机会也会增加，因此较高比例的最终用户请求速度会变慢（效果称为尾部延迟放大）。

应对负载的方法

人们经常讨论 纵向伸缩（scaling up，转向更强大的机器）和 横向伸缩（scaling out，将负载分布到多台小机器上）之间的对立。跨多台机器分配负载也称为 “无共享（shared-nothing）” 架构。可以在单台机器上运行的系统通常更简单，但高端机器可能非常贵，所以非常密集的负载通常无法避免地需要横向伸缩。现实世界中的优秀架构需要将这两种方法务实地结合，因为使用几台足够强大的机器可能比使用大量的小型虚拟机更简单也更便宜。

有些系统是 弹性（elastic） 的，而其他系统则是手动伸缩。如果负载 极难预测（highly unpredictable），则弹性系统可能很有用，但手动伸缩系统更简单，并且意外操作可能会更少。

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

大规模的系统架构通常是应用特定的 —— 没有一招鲜吃遍天的通用可伸缩架构。应用的问题可能是读取量、写入量、要存储的数据量、数据的复杂度、响应时间要求、访问模式或者所有问题的大杂烩。举个例子，用于处理每秒十万个请求（每个大小为 1 kB）的系统与用于处理每分钟 3 个请求（每个大小为 2GB）的系统看上去会非常不一样，尽管两个系统有同样的数据吞吐量。

可维护性

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

  • 可操作性（Operability）

    便于运维团队保持系统平稳运行。

  • 简单性（Simplicity）

    从系统中消除尽可能多的 复杂度（complexity），使新工程师也能轻松理解系统。

  • 可演化性（evolvability）

    使工程师在未来能轻松地对系统进行更改，当需求变化时为新应用场景做适配。也称为 可扩展性（extensibility）、可修改性（modifiability） 或 可塑性（plasticity）。

可操作性

良好的可操作性意味着更轻松的日常工作，进而运维团队能专注于高价值的事情。数据系统可以通过各种方式使日常任务更轻松：

  • 通过良好的监控，提供对系统内部状态和运行时行为的 可见性（visibility）。

  • 为自动化提供良好支持，将系统与标准化工具相集成。

  • 避免依赖单台机器（在整个系统继续不间断运行的情况下允许机器停机维护）。

  • 提供良好的文档和易于理解的操作模型（“如果做 X，会发生 Y”）。

  • 提供良好的默认行为，但需要时也允许管理员自由覆盖默认值。

  • 有条件时进行自我修复，但需要时也允许管理员手动控制系统状态。

  • 行为可预测，最大限度减少意外。

简单性

小型软件项目可以使用简单讨喜的、富表现力的代码，但随着项目越来越大，代码往往变得非常复杂，难以理解。这种复杂度拖慢了所有系统相关人员，进一步增加了维护成本。

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

用于消除 额外复杂度 的最好工具之一是 抽象（abstraction）。一个好的抽象可以将大量实现细节隐藏在一个干净，简单易懂的外观下面。一个好的抽象也可以广泛用于各类不同应用。比起重复造很多轮子，重用抽象不仅更有效率，而且有助于开发高质量的软件。抽象组件的质量改进将使所有使用它的应用受益。

可演化性

系统的需求永远不变，基本是不可能的。更可能的情况是，它们处于常态的变化中，例如：你了解了新的事实、出现意想不到的应用场景、业务优先级发生变化、用户要求新功能等。

修改数据系统并使其适应不断变化需求的容易程度，是与 简单性 和 抽象性 密切相关的：简单易懂的系统通常比复杂系统更容易修改。但由于这是一个非常重要的概念，我们将用一个不同的词来指代数据系统层面的敏捷性： 可演化性（evolvability）。

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

一个复杂的应用程序可能会有更多的中间层次，比如基于 API 的 API，不过基本思想仍然是一样的：每个层都通过提供一个明确的数据模型来隐藏更低层次中的复杂性。这些抽象允许不同的人群有效地协作（例如数据库厂商的工程师和使用数据库的应用程序开发人员）。

关系模型与文档模型

现在最著名的数据模型可能是 SQL。它基于 Edgar Codd 在 1970 年提出的关系模型：数据被组织成 关系（SQL 中称作 表），其中每个关系是 元组（SQL 中称作 行) 的无序集合。

NoSQL 的诞生

“NoSQL” 这个名字让人遗憾，因为实际上它并没有涉及到任何特定的技术。最初它只是作为一个醒目的 Twitter 标签，用在 2009 年一个关于分布式，非关系数据库上的开源聚会上。好在 NoSQL 被追溯性地重新解释为 不仅是 SQL（Not Only SQL）。

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

  • 需要比关系数据库更好的可伸缩性，包括非常大的数据集或非常高的写入吞吐量

  • 相比商业数据库产品，免费和开源软件更受偏爱

  • 关系模型不能很好地支持一些特殊的查询操作

  • 受挫于关系模型的限制性，渴望一种更具多动态性与表现力的数据模型

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

对象关系不匹配

如果数据存储在关系表中，那么需要一个笨拙的转换层，处于应用程序代码中的对象和表，行，列的数据库模型之间。模型之间的不连贯有时被称为 **阻抗不匹配（impedance mismatch）。

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

Eg. Linkedln 简历

整个简介可以通过一个唯一的标识符 user_id 来标识。像 first_name 和 last_name 这样的字段每个用户只出现一次，所以可以在 User 表上将其建模为列。但是，大多数人在职业生涯中拥有多于一份的工作，人们可能有不同样的教育阶段和任意数量的联系信息。从用户到这些项目之间存在一对多的关系，最常见的规范化表示形式是将职位，教育和联系信息放在单独的表中，对 User 表提供外键引用。

对于一个像简历这样自包含文档的数据结构而言，JSON 表示是非常合适的，可以使用面向文档的数据库（如 MongoDB）

{
  "user_id": 251,
  "first_name": "Bill",
  "last_name": "Gates",
  "summary": "Co-chair of the Bill & Melinda Gates... Active blogger.",
  "region_id": "us:91",
  "industry_id": 131,
  "photo_url": "/p/7/000/253/05b/308dd6e.jpg",
  "positions": [
    {
      "job_title": "Co-chair",
      "organization": "Bill & Melinda Gates Foundation"
    },
    {
      "job_title": "Co-founder, Chairman",
      "organization": "Microsoft"
    }
  ],
  "education": [
    {
      "school_name": "Harvard University",
      "start": 1973,
      "end": 1975
    },
    {
      "school_name": "Lakeside School, Seattle",
      "start": null,
      "end": null
    }
  ],
  "contact_info": {
    "blog": "http://thegatesnotes.com",
    "twitter": "http://twitter.com/BillGates"
  }
}

有一些开发人员认为 JSON 模型减少了应用程序代码和存储层之间的阻抗不匹配。JSON 表示比多表模式具有更好的 局部性（locality）。如果在关系型示例中获取简介，那需要执行多个查询（通过 user_id 查询每个表），或者在 User 表与其下属表之间混乱地执行多路连接。而在 JSON 表示中，所有相关信息都在同一个地方，一个查询就足够了。

这里看起来好像会引起一些新的话题，例如 MongoDB 的使用场景，文档数据库在这种时候确实是比关系型数据库更加适合，但是如何把握住这个点是一个值得思考的问题。

多对一和多对多的关系

简历中的会存 region_id ，它是以 ID，而不是纯字符串形式给出的。为什么？

如果用户界面用一个自由文本字段来输入区域和行业，那么将他们存储为纯文本字符串是合理的。另一方式是给出地理区域和行业的标准化的列表，并让用户从下拉列表或自动填充器中进行选择，其优势如下：

  • 各个简介之间样式和拼写统一

  • 避免歧义（例如，如果有几个同名的城市）

  • 易于更新 —— 名称只存储在一个地方，如果需要更改（例如，由于政治事件而改变城市名称），很容易进行全面更新。

  • 本地化支持 —— 当网站翻译成其他语言时，标准化的列表可以被本地化，使得地区和行业可以使用用户的语言来显示

  • 更好的搜索 —— 例如，搜索华盛顿州的慈善家就会匹配这份简介，因为地区列表可以编码记录西雅图在华盛顿这一事实（从 “Greater Seattle Area” 这个字符串中看不出来）

使用 ID 的好处是，ID 对人类没有任何意义，因而永远不需要改变。任何对人类有意义的东西都可能需要在将来某个时候改变 —— 如果这些信息被复制，所有的冗余副本都需要更新。这会导致写入开销，也存在不一致的风险（一些副本被更新了，还有些副本没有被更新）。去除此类重复是数据库 规范化（normalization） 的关键思想。

在关系数据库中，通过 ID 来引用其他表中的行是正常的，因为连接很容易。在文档数据库中，一对多树结构没有必要用连接，对连接的支持通常很弱。

如果数据库本身不支持连接，则必须在应用程序代码中通过对数据库进行多个查询来模拟连接。

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

IBM 的信息管理系统（IMS） 的设计中使用了一个相当简单的数据模型，称为 层次模型（hierarchical model），它与文档数据库使用的 JSON 模型有一些惊人的相似之处。

同文档数据库一样，IMS 能良好处理一对多的关系，但是很难应对多对多的关系，并且不支持连接。开发人员必须决定是否复制（非规范化）数据或手动解决从一个记录到另一个记录的引用。这些二十世纪六七十年代的问题与现在开发人员遇到的文档数据库问题非常相似。

那时人们提出了各种不同的解决方案来解决层次模型的局限性。其中最突出的两个是 关系模型（relational model，它变成了 SQL，并统治了世界）和 网状模型（network model，最初很受关注，但最终变得冷门）。

网状模型

网状模型中记录之间的链接不是外键，而更像编程语言中的指针（同时仍然存储在磁盘上）。访问记录的唯一方法是跟随从根记录起沿这些链路所形成的路径。这被称为 访问路径（access path）。

最简单的情况下，访问路径类似遍历链表：从列表头开始，每次查看一条记录，直到找到所需的记录。但在多对多关系的情况中，数条不同的路径可以到达相同的记录，网状模型的程序员必须跟踪这些不同的访问路径。

查询和更新数据库的代码变得复杂不灵活。无论是分层还是网状模型，如果你没有所需数据的路径，就会陷入困境。你可以改变访问路径，但是必须浏览大量手写数据库查询代码，并重写来处理新的访问路径。更改应用程序的数据模型是很难的。

关系模型

相比之下，关系模型做的就是将所有的数据放在光天化日之下：一个 关系（表） 只是一个 元组（行） 的集合，仅此而已。

外键约束允许对修改进行限制，但对于关系模型这并不是必选项。即使有约束，外键连接在查询时执行，而在 CODASYL 中，连接在插入时高效完成。

在关系数据库中，查询优化器自动决定查询的哪些部分以哪个顺序执行，以及使用哪些索引。如果想按新的方式查询数据，你可以声明一个新的索引，查询会自动使用最合适的那些索引。

与文档数据库相比

在一个方面，文档数据库还原为层次模型：在其父记录中存储嵌套记录（一对多关系，如 positions，education 和 contact_info），而不是在单独的表中。

但是，在表示多对一和多对多的关系时，关系数据库和文档数据库并没有根本的不同：在这两种情况下，相关项目都被一个唯一的标识符引用，这个标识符在关系模型中被称为 外键，在文档模型中称为 文档引用。该标识符在读取时通过连接或后续查询来解析。

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

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

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

如果应用程序中的数据具有类似文档的结构（即，一对多关系树，通常一次性加载整个树），那么使用文档模型可能是一个好主意。将类似文档的结构分解成多个表的关系技术可能导致繁琐的模式和不必要的复杂的应用程序代码。

但如果你的应用程序确实会用到多对多关系，那么文档模型就没有那么诱人了。尽管应用程序代码可以通过向数据库发出多个请求的方式来模拟连接，但这也将复杂性转移到应用程序中，而且通常也会比由数据库内的专用代码更慢。

文档模型中的模式灵活性

文档数据库有时称为 无模式（schemaless），但这具有误导性，因为读取数据的代码通常假定某种结构 —— 即存在隐式模式，但不由数据库强制执行。一个更精确的术语是 读时模式（即 schema-on-read，数据的结构是隐含的，只有在数据被读取时才被解释）。

在应用程序想要改变其数据格式的情况下，这些方法之间的区别尤其明显。例如，假设你把每个用户的全名存储在一个字段中，而现在想分别存储名字和姓氏。在文档数据库中，只需开始写入具有新字段的新文档，并在应用程序中使用代码来处理读取旧文档的情况。例如：

if (user && user.name && !user.first_name) {
  // Documents written before Dec 8, 2013 don't have first_name
  user.first_name = user.name.split(" ")[0];
}

另一方面，在 “静态类型” 数据库模式中，通常会执行以下 迁移（migration） 操作：

ALTER TABLE users ADD COLUMN first_name text;
UPDATE users SET first_name = split_part(name, ' ', 1);      -- PostgreSQL
UPDATE users SET first_name = substring_index(name, ' ', 1);      -- MySQL

模式变更的速度很慢，而且要求停运。大型表上运行 UPDATE 语句在任何数据库上都可能会很慢，因为每一行都需要重写。要是不可接受的话，应用程序可以将 first_name 设置为默认值 NULL，并在读取时再填充，就像使用文档数据库一样。

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

  • 存在许多不同类型的对象，将每种类型的对象放在自己的表中是不现实的。

  • 数据的结构由外部系统决定。你无法控制外部系统且它随时可能变化。

查询的数据局部性

如果应用程序经常需要访问整个文档（例如，将其渲染至网页），那么存储局部性会带来性能优势。如果将数据分割到多个表中），则需要进行多次索引查找才能将其全部检索出来，这可能需要更多的磁盘查找并花费更多的时间。

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

文档与关系数据库的融合

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

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

数据查询语言

SQL 是一种 声明式 查询语言，而 IMS 和 CODASYL 使用 命令式 代码来查询数据库。

命令式语言告诉计算机以特定顺序执行某些操作。可以想象一下，逐行地遍历代码，评估条件，更新变量，并决定是否再循环一遍。

声明式查询语言是迷人的，因为它通常比命令式 API 更加简洁和容易。但更重要的是，它还隐藏了数据库引擎的实现细节，这使得数据库系统可以在无需对查询做任何更改的情况下进行性能提升。

声明式语言往往适合并行执行。现在，CPU 的速度通过核心的增加变得更快，而不是以比以前更高的时钟速度运行。命令代码很难在多个核心和多个机器之间并行化，因为它指定了指令必须以特定顺序执行。声明式语言更具有并行执行的潜力，因为它们仅指定结果的模式，而不指定用于确定结果的算法。在适当情况下，数据库可以自由使用查询语言的并行实现。

Web 上的声明式查询

假设你有一个关于海洋动物的网站。用户当前正在查看鲨鱼页面，因此你将当前所选的导航项目 “鲨鱼” 标记为当前选中项目。

<ul>
    <li class="selected">
        <p>Sharks</p>
        <ul>
            <li>Great White Shark</li>
            <li>Tiger Shark</li>
            <li>Hammerhead Shark</li>
        </ul>
    </li>
    <li><p>Whales</p>
        <ul>
            <li>Blue Whale</li>
            <li>Humpback Whale</li>
            <li>Fin Whale</li>
        </ul>
    </li>
</ul>

现在想让当前所选页面的标题具有一个蓝色的背景，以便在视觉上突出显示。使用 CSS 实现起来非常简单：

li.selected > p {
  background-color: blue;
}

想象一下，必须使用命令式方法的情况会是如何。在 Javascript 中，使用 文档对象模型（DOM） API，其结果可能如下所示：

var liElements = document.getElementsByTagName("li");
for (var i = 0; i < liElements.length; i++) {
    if (liElements[i].className === "selected") {
        var children = liElements[i].childNodes;
        for (var j = 0; j < children.length; j++) {
            var child = children[j];
            if (child.nodeType === Node.ELEMENT_NODE && child.tagName === "P") {
                child.setAttribute("style", "background-color: blue");
            }
        }
    }
}

这段 JavaScript 代码命令式地将元素设置为蓝色背景，但是代码看起来很糟糕。不仅比 CSS 更长，更难理解，而且还有一些严重的问题：如果选定的类被移除（例如，因为用户点击了不同的页面），即使代码重新运行，蓝色背景也不会被移除 - 因此该项目将保持突出显示，直到整个页面被重新加载。使用 CSS，浏览器会自动检测 li.selected > p 规则何时不再适用，并在选定的类被移除后立即移除蓝色背景。

在 Web 浏览器中，使用声明式 CSS 样式比使用 JavaScript 命令式地操作样式要好得多。类似地，在数据库中，使用像 SQL 这样的声明式查询语言比使用命令式查询 API 要好得多。

MapReduce 查询

MapReduce 既不是一个声明式的查询语言，也不是一个完全命令式的查询 API，而是处于两者之间：查询的逻辑用代码片段来表示，这些代码片段会被处理框架重复性调用。

map 和 reduce 函数在功能上有所限制：它们必须是 纯 函数，这意味着它们只使用传递给它们的数据作为输入，它们不能执行额外的数据库查询，也不能有任何副作用。这些限制允许数据库以任何顺序运行任何功能，并在失败时重新运行它们。

db.observations.mapReduce(function map() {
        var year = this.observationTimestamp.getFullYear();
        var month = this.observationTimestamp.getMonth() + 1;
        emit(year + "-" + month, this.numAnimals);
    },
    function reduce(key, values) {
        return Array.sum(values);
    },
    {
        query: {
          family: "Sharks"
        },
        out: "monthlySharkReport"
    });

MongoDB 2.2 添加了一种叫做 聚合管道 的声明式查询语言的支持。用这种语言表述鲨鱼计数查询如下所示：

db.observations.aggregate([
  { $match: { family: "Sharks" } },
  { $group: {
    _id: {
      year:  { $year:  "$observationTimestamp" },
      month: { $month: "$observationTimestamp" }
    },
    totalAnimals: { $sum: "$numAnimals" } }}
]);

聚合管道语言的表现力与 SQL 相当，但是它使用基于 JSON 的语法而不是 SQL。这个故事的寓意是：NoSQL 系统可能会意外发现自己只是重新发明了一套经过乔装改扮的 SQL。

图数据模型

一个图由两种对象组成：顶点（vertices，也称为 节点，即 nodes，或 实体，即 entities），和 边（edges，也称为 关系，即 relationships，或 弧，即 arcs）。多种数据可以被建模为一个图形。典型的例子包括：

  • 社交图谱

    顶点是人，边指示哪些人彼此认识。

  • 公路或铁路网络

    顶点是交叉路口，边线代表它们之间的道路或铁路线。

可以将那些众所周知的算法运用到这些图上：例如，汽车导航系统搜索道路网络中两点之间的最短路径。

图并不局限于同类数据：同样强大地是，图提供了一种一致的方式，用来在单个数据存储中存储完全不同类型的对象。例如，Facebook 维护一个包含许多不同类型的顶点和边的单个图：顶点表示人，地点，事件，签到；边缘表示哪些人是彼此的朋友，哪个签到发生在何处等等。

属性图

可以将图存储看作由两个关系表组成：一个存储顶点，另一个存储边，头部和尾部顶点用来存储每条边；如果你想要一组顶点的输入或输出边，你可以分别通过 head_vertex 或 tail_vertex 来查询 edges 表。

CREATE TABLE vertices (
  vertex_id  INTEGER PRIMARY KEY,
  properties JSON
);

CREATE TABLE edges (
  edge_id     INTEGER PRIMARY KEY,
  tail_vertex INTEGER REFERENCES vertices (vertex_id),
  head_vertex INTEGER REFERENCES vertices (vertex_id),
  label       TEXT,
  properties  JSON
);

CREATE INDEX edges_tails ON edges (tail_vertex);
CREATE INDEX edges_heads ON edges (head_vertex);

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

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

  3. 通过对不同类型的关系使用不同的标签，可以在一个图中存储几种不同的信息。

Cypher 查询语言

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

每个顶点都有一个像 USA 或 Idaho 这样的符号名称，查询的其他部分可以使用这些名称在顶点之间创建边，使用箭头符号：（Idaho） - [：WITHIN] ->（USA） 创建一条标记为 WITHIN 的边，Idaho 为尾节点，USA 为头节点。

CREATE
  (NAmerica:Location {name:'North America', type:'continent'}),
  (USA:Location      {name:'United States', type:'country'  }),
  (Idaho:Location    {name:'Idaho',         type:'state'    }),
  (Lucy:Person       {name:'Lucy' }),
  (Idaho) -[:WITHIN]->  (USA)  -[:WITHIN]-> (NAmerica),
  (Lucy)  -[:BORN_IN]-> (Idaho)

Eg. 找到所有从美国移民到欧洲的人的名字

MATCH
  (person) -[:BORN_IN]->  () -[:WITHIN*0..]-> (us:Location {name:'United States'}),
  (person) -[:LIVES_IN]-> () -[:WITHIN*0..]-> (eu:Location {name:'Europe'})
RETURN person.name

  1. person 顶点拥有一条到某个顶点的 BORN_IN 出边。从那个顶点开始，沿着一系列 WITHIN 出边最终到达一个类型为 Location，name 属性为 United States 的顶点。

  2. person 顶点还拥有一条 LIVES_IN 出边。沿着这条边，可以通过一系列 WITHIN 出边最终到达一个类型为 Location，name 属性为 Europe 的顶点。

对于这样的 Person 顶点，返回其 name 属性。

SQL 中的图查询

一个人的 LIVES_IN 边可以指向任何类型的位置：街道、城市、地区、国家等。一个城市可以在（WITHIN）一个地区内，一个地区可以在（WITHIN）在一个州内，一个州可以在（WITHIN）一个国家内，等等。LIVES_IN 边可以直接指向正在查找的位置，或者一个在位置层次结构中隔了数层的位置。

在 Cypher 中，用 WITHIN*0.. 非常简洁地表述了上述事实：“沿着 WITHIN 边，零次或多次”。它很像正则表达式中的 * 运算符。

自 SQL:1999，查询可变长度遍历路径的思想可以使用称为 递归公用表表达式（WITH RECURSIVE 语法）的东西来表示。但是，与 Cypher 相比，其语法非常笨拙。

同一个查询，用某一个查询语言可以写成 4 行，而用另一个查询语言需要 29 行，这恰恰说明了不同的数据模型是为不同的应用场景而设计的。选择适合应用程序的数据模型非常重要。

第三章：存储与检索

数据库如何存储我们提供的数据，以及如何在我们需要时重新找到数据。

驱动数据库的数据结构

日志（log） 这个词通常指应用日志：即应用程序输出的描述正在发生的事情的文本。本书在更普遍的意义下使用 日志 这一词：一个仅追加的记录序列。它可能压根就不是给人类看的，它可以使用二进制格式，并仅能由其他程序读取。

为了高效查找数据库中特定键的值，我们需要一个数据结构：索引（index）。索引背后的大致思想是通过保存一些额外的元数据作为路标来帮助你找到想要的数据。如果你想以几种不同的方式搜索同一份数据，那么你也许需要在数据的不同部分上建立多个索引。

这是存储系统中一个重要的权衡：精心选择的索引加快了读查询的速度，但是每个索引都会拖慢写入速度。因为这个原因，数据库默认并不会索引所有的内容。你可以选择那些能为应用带来最大收益而且又不会引入超出必要开销的索引。

散列索引

假设我们的数据存储只是一个追加写入的文件，就像前面的例子一样，那么最简单的索引策略就是：保留一个内存中的散列映射，其中每个键都映射到数据文件中的一个字节偏移量，指明了可以找到对应值的位置。当你将新的键值对追加写入文件中时，还要更新散列映射，以反映刚刚写入的数据的偏移量（这同时适用于插入新键与更新现有键）。当你想查找一个值时，使用散列映射来查找数据文件中的偏移量，寻找（seek） 该位置并读取该值即可。

这种简单的方法非常适合每个键的值经常更新的情况。例如，键可能是某个猫咪视频的网址（URL），而值可能是该视频被播放的次数（每次有人点击播放按钮时递增）。在这种类型的工作负载中，有很多写操作，但是没有太多不同的键 —— 每个键有很多的写操作，但是将所有键保存在内存中是可行的。

如何避免最终用完硬盘空间？一种好的解决方案是，将日志分为特定大小的 段（segment），当日志增长到特定尺寸时关闭当前段文件，并开始写入一个新的段文件。然后，我们就可以对这些段进行 压缩（compaction）。这里的压缩意味着在日志中丢弃重复的键，只保留每个键的最近更新。

仅追加日志似乎很浪费：为什么不直接在文件里更新，用新值覆盖旧值？仅追加的设计之所以是个好的设计，有如下几个原因：

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

  • 如果段文件是仅追加的或不可变的，并发和崩溃恢复就简单多了。例如，当一个数据值被更新的时候发生崩溃，你不用担心文件里将会同时包含旧值和新值各自的一部分。

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

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

  • 散列表必须能放进内存。如果你有非常多的键，那就难以处理。原则上可以在硬盘上维护一个散列映射，不幸的是硬盘散列映射很难表现优秀。它需要大量的随机访问 I/O，而后者耗尽时想要再扩充是很昂贵的，并且需要很烦琐的逻辑去解决散列冲突。

  • 范围查询效率不高。例如，你无法轻松扫描 kitty00000 和 kitty99999 之间的所有键 —— 你必须在散列映射中单独查找每个键。

SSTables 和 LSM 树

我们可以对段文件的格式做一个简单的改变：要求键值对的序列按键排序。

我们把这个格式称为 排序字符串表（Sorted String Table），简称 SSTable。我们还要求每个键只在每个合并的段文件中出现一次（压缩过程已经保证）。与使用散列索引的日志段相比，SSTable 有几个大的优势：

  1. 即使文件大于可用内存，合并段的操作仍然是简单而高效的。你并排读取多个输入文件，查看每个文件中的第一个键，复制最低的键（根据排序顺序）到输出文件，不断重复此步骤，将产生一个新的合并段文件，而且它也是也按键排序的。当多个段包含相同的键时，我们可以保留最近段的值，并丢弃旧段中的值。

  2. 为了在文件中找到一个特定的键，你不再需要在内存中保存所有键的索引。你仍然需要一个内存中的索引来告诉你一些键的偏移量，但它可以是稀疏的：每几千字节的段文件有一个键就足够了，因为几千字节可以很快地被扫描完。

  3. 可以将这些记录分组为块（block），并在将其写入硬盘之前对其进行压缩。稀疏内存索引中的每个条目都指向压缩块的开始处。除了节省硬盘空间之外，压缩还可以减少对 I/O 带宽的使用。

构建和维护 SSTables

  • 有新写入时，将其添加到内存中的平衡树数据结构（例如红黑树）。这个内存树有时被称为 内存表（memtable）。

  • 当 内存表 大于某个阈值（通常为几兆字节）时，将其作为 SSTable 文件写入硬盘。这可以高效地完成，因为树已经维护了按键排序的键值对。新的 SSTable 文件将成为数据库中最新的段。当该 SSTable 被写入硬盘时，新的写入可以在一个新的内存表实例上继续进行。

  • 收到读取请求时，首先尝试在内存表中找到对应的键，如果没有就在最近的硬盘段中寻找，如果还没有就在下一个较旧的段中继续寻找，以此类推。

  • 时不时地，在后台运行一个合并和压缩过程，以合并段文件并将已覆盖或已删除的值丢弃掉。

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

用 SSTables 制作 LSM 树

这种索引结构最早由 Patrick O'Neil 等人发明，且被命名为日志结构合并树（或 LSM 树），它是基于更早之前的日志结构文件系统来构建的。基于这种合并和压缩排序文件原理的存储引擎通常被称为 LSM 存储引擎。

性能优化

要让存储引擎在实践中表现良好涉及到大量设计细节。例如，当查找数据库中不存在的键时，LSM 树算法可能会很慢：你必须先检查内存表，然后查看从最近的到最旧的所有的段（可能还必须从硬盘读取每一个段文件），然后才能确定这个键不存在。为了优化这种访问，存储引擎通常使用额外的布隆过滤器。

还有一些不同的策略来确定 SSTables 被压缩和合并的顺序和时间。最常见的选择是 size-tiered 和 leveled compaction。对于 sized-tiered，较新和较小的 SSTables 相继被合并到较旧的和较大的 SSTable 中。对于 leveled compaction，key （按照分布范围）被拆分到较小的 SSTables，而较旧的数据被移动到单独的层级（level），这使得压缩（compaction）能够更加增量地进行，并且使用较少的硬盘空间。

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

B 树

在几乎所有的关系数据库中，B 树仍然是标准的索引实现，许多非关系数据库也会使用到 B 树。

像 SSTables 一样，B 树保持按键排序的键值对，这允许高效的键值查找和范围查询。但这也就是仅有的相似之处了。B 树将数据库分解成固定大小的 块（block） 或 分页（page），传统上大小为 4KB（有时会更大），并且一次只能读取或写入一个页面。这种设计更接近于底层硬件，因为硬盘空间也是按固定大小的块来组织的。每个页面都可以使用地址或位置来标识，这允许一个页面引用另一个页面 —— 类似于指针，但在硬盘而不是在内存中。我们可以使用这些页面引用来构建一个页面树。

一个页面会被指定为 B 树的根；在索引中查找一个键时，就从这里开始。该页面包含几个键和对子页面的引用。每个子页面负责一段连续范围的键，根页面上每两个引用之间的键，表示相邻子页面管理的键的范围（边界）。

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

大多数数据库可以放入一个三到四层的 B 树，所以你不需要追踪多个页面引用来找到你正在查找的页面（分支因子为 500 的 4KB 页面的四层树可以存储多达 256TB 的数据）。

让 B 树更可靠

B 树的基本底层写操作是用新数据覆写硬盘上的页面，并假定覆写不改变页面的位置。这与日志结构索引（如 LSM 树）形成鲜明对比，后者只追加到文件（并最终删除过时的文件）。

在固态硬盘上，由于 SSD 必须一次擦除和重写相当大的存储芯片块，所以会发生更复杂的事情，例如，如果因为插入导致页面过满而拆分页面，则需要写入新拆分的两个页面，并覆写其父页面以更新对两个子页面的引用。如果数据库在系列操作进行到一半时崩溃，那么最终将导致一个损坏的索引（例如，可能有一个孤儿页面没有被任何页面引用） 。

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

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

B 树的优化

  • 不同于覆写页面并维护 WAL 以支持崩溃恢复，一些数据库（如 LMDB）使用写时复制方案。经过修改的页面被写入到不同的位置，并且还在树中创建了父页面的新版本，以指向新的位置。这种方法对于并发控制也很有用（MVCC）。

  • 我们可以通过不存储整个键，而是缩短其大小，来节省页面空间。特别是在树内部的页面上，键只需要提供足够的信息来充当键范围之间的边界。在页面中包含更多的键允许树具有更高的分支因子，因此也就允许更少的层级（B+ 树）。

  • 通常，页面可以放置在硬盘上的任何位置，如果某个查询需要按照排序顺序扫描大部分的键范围，那么这种按页面存储的布局可能会效率低下，因此，许多 B 树的实现在布局树时会尽量使叶子页面按顺序出现在硬盘上。但是，随着树的增长，要维持这个顺序是很困难的。相比之下，由于 LSM 树在合并过程中一次性重写一大段存储，所以它们更容易使顺序键在硬盘上连续存储。

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

比较 B 树和 LSM 树

尽管 B 树实现通常比 LSM 树实现更成熟，但 LSM 树由于性能特征也非常有趣。根据经验，通常 LSM 树的写入速度更快，而 B 树的读取速度更快。 LSM 树上的读取通常比较慢，因为它们必须检查几种不同的数据结构和不同压缩（Compaction）层级的 SSTables。

LSM 树的优点

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

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

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

LSM 树的缺点

压缩过程有时会干扰正在进行的读写操作。尽管存储引擎尝试增量地执行压缩以尽量不影响并发访问，但是硬盘资源有限，所以很容易发生某个请求需要等待硬盘先完成昂贵的压缩操作。

硬盘的有限写入带宽需要在初始写入（记录日志和刷新内存表到硬盘）和在后台运行的压缩线程之间共享。如果写入吞吐量很高，并且压缩没有仔细配置好，有可能导致压缩跟不上写入速率。在这种情况下，硬盘上未合并段的数量不断增加，直到硬盘空间用完，读取速度也会减慢，因为它们需要检查更多的段文件。

B 树的一个优点是每个键只存在于索引中的一个位置，而日志结构化的存储引擎可能在不同的段中有相同键的多个副本。在许多关系数据库中，事务隔离是通过在键范围上使用锁来实现的，在 B 树索引中，这些锁可以直接附加到树上。

其他索引结构

次级索引（secondary indexes）也很常见。在关系数据库中，你可以使用 CREATE INDEX 命令在同一个表上创建多个次级索引，而且这些索引通常对于有效地执行联接（join）而言至关重要。

将值存储在索引中

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

在某些情况下，从索引到堆文件的额外跳跃对读取来说性能损失太大，因此可能希望将被索引的行直接存储在索引中。这被称为聚集索引（clustered index）。在 聚集索引（在索引中存储所有的行数据）和 非聚集索引（仅在索引中存储对数据的引用）之间的折衷被称为 覆盖索引（covering index） 或 包含列的索引（index with included columns），其在索引内存储表的一部分列。这允许通过单独使用索引来处理一些查询（这种情况下，可以说索引 覆盖（cover） 了查询）。

多列索引

最常见的多列索引被称为 联合索引（concatenated index） ，它通过将一列的值追加到另一列后面，简单地将多个字段组合成一个键（索引定义中指定了字段的连接顺序）。由于排序顺序，索引可以用来查找所有具有特定姓氏的人，或所有具有特定姓氏 - 名字组合的人。但如果你想找到所有具有特定名字的人，这个索引是没有用的。

全文搜索和模糊索引

到目前为止所讨论的所有索引都假定你有确切的数据，并允许你查询键的确切值或具有排序顺序的键的值范围。他们不允许你做的是搜索类似的键，如拼写错误的单词。这种模糊的查询需要不同的技术。

例如，全文搜索引擎通常允许搜索目标从一个单词扩展为包括该单词的同义词，忽略单词的语法变体，搜索在相同文档中的近义词，并且支持各种其他取决于文本的语言分析功能。为了处理文档或查询中的拼写错误，Lucene 能够在一定的编辑距离内搜索文本（编辑距离 1 意味着单词内发生了 1 个字母的添加、删除或替换）。

Lucene 为其词典使用了一个类似于 SSTable 的结构。这个结构需要一个小的内存索引，告诉查询需要在排序文件中哪个偏移量查找键。在 LevelDB 中，这个内存中的索引是一些键的稀疏集合，但在 Lucene 中，内存中的索引是键中字符的有限状态自动机，类似于 trie 。这个自动机可以转换成 Levenshtein 自动机，它支持在给定的编辑距离内有效地搜索单词。

其他的模糊搜索技术正朝着文档分类和机器学习的方向发展。

在内存中存储一切

随着 RAM 变得更便宜，每 GB 成本的论据被侵蚀了。许多数据集不是那么大，所以将它们全部保存在内存中是非常可行的，包括可能分布在多个机器上。这导致了内存数据库的发展。

某些内存中的键值存储（如 Memcached）仅用于缓存，在重新启动计算机时丢失的数据是可以接受的。但其他内存数据库的目标是持久性，可以通过特殊的硬件（例如电池供电的 RAM）来实现，也可以将更改日志写入硬盘，还可以将定时快照写入硬盘或者将内存中的状态复制到其他机器上。

除了性能，内存数据库的另一个有趣的地方是提供了难以用基于硬盘的索引实现的数据模型。例如，Redis 为各种数据结构（如优先级队列和集合）提供了类似数据库的接口。因为它将所有数据保存在内存中，所以它的实现相对简单。

事务处理还是分析

属性事务处理系统 OLTP分析系统 OLAP

主要读取模式

查询少量记录，按键读取

在大批量记录上聚合

主要写入模式

随机访问，写入要求低延时

批量导入（ETL）或者事件流

主要用户

终端用户，通过 Web 应用

内部数据分析师，用于决策支持

处理的数据

数据的最新状态（当前时间点）

随时间推移的历史事件

数据集尺寸

GB ~ TB

TB ~ PB

事务处理和分析查询使用了相同的数据库。 SQL 在这方面已证明是非常灵活的：对于 OLTP 类型的查询以及 OLAP 类型的查询来说效果都很好。尽管如此，在二十世纪八十年代末和九十年代初期，企业有停止使用 OLTP 系统进行分析的趋势，转而在单独的数据库上运行分析。这个单独的数据库被称为 数据仓库（data warehouse）。

数据仓库

数据仓库是一个独立的数据库，分析人员可以查询他们想要的内容而不影响 OLTP 操作。数据仓库包含公司各种 OLTP 系统中所有的只读数据副本。从 OLTP 数据库中提取数据（使用定期的数据转储或连续的更新流），转换成适合分析的模式，清理并加载到数据仓库中。将数据存入仓库的过程称为 抽取 - 转换 - 加载（ETL）。

OLTP 数据库和数据仓库之间的分歧

一个数据仓库和一个关系型 OLTP 数据库看起来很相似，因为它们都有一个 SQL 查询接口。然而，系统的内部看起来可能完全不同，因为它们针对非常不同的查询模式进行了优化。现在许多数据库供应商都只是重点支持事务处理负载和分析工作负载这两者中的一个，而不是都支持。

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

在分析型业务中，数据模型的多样性则少得多。许多数据仓库都以相当公式化的方式使用，被称为星型模式。

事实表的每一行代表在特定时间发生的事件。如果我们分析的是网站流量，则每行可能代表一个用户的页面浏览或点击。通常情况下，事实被视为单独的事件，因为这样可以在以后分析中获得最大的灵活性。但是，这意味着事实表可以变得非常大。

事实表中的一些列是属性，事实表中的其他列是对其他表（称为维度表）的外键引用。由于事实表中的每一行都表示一个事件，因此这些维度代表事件发生的对象、内容、地点、时间、方式和原因。

这个模板的变体被称为雪花模式，其中维度被进一步分解为子维度。例如，品牌和产品类别可能有单独的表格，并且表格中的每一行都可以将品牌和类别作为外键引用，而不是将它们作为字符串存储在 表格中。雪花模式比星形模式更规范化，但是星形模式通常是首选，因为分析师使用它更简单。

列式存储

尽管事实表通常超过 100 列，但典型的数据仓库查询一次只会访问其中 4 个或 5 个列（ “SELECT *” 查询很少用于分析）。

在大多数 OLTP 数据库中，存储都是以面向行的方式进行布局的：表格的一行中的所有值都相邻存储。文档数据库也是相似的：整个文档通常存储为一个连续的字节序列。在查询时虽然有索引，但是也需要把所有的行加载到内存，这需要很长的时间。

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

列式存储布局依赖于每个列文件包含相同顺序的行。 因此，如果你需要重新组装完整的行，你可以从每个单独的列文件中获取第 23 项，并将它们放在一起形成表的第 23 行。

列压缩

通常情况下，一列中不同值的数量与行数相比要小得多（例如，零售商可能有数十亿的销售交易，但只有 100,000 个不同的产品）。现在我们可以拿一个有 n 个不同值的列，并把它转换成 n 个独立的位图：每个不同值对应一个位图，每行对应一个比特位。如果该行具有该值，则该位为 1，否则为 0。

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

内存带宽和矢量化处理

对于数据仓库查询来说，一个巨大的瓶颈是从硬盘获取数据到内存的带宽。但是，这不是唯一的瓶颈。分析型数据库的开发人员还需要有效地利用内存到 CPU 缓存的带宽，避免 CPU 指令处理流水线中的分支预测错误和闲置等待，以及在现代 CPU 上使用单指令多数据（SIMD）指令来加速运算。

除了减少需要从硬盘加载的数据量以外，列式存储布局也可以有效利用 CPU 周期。例如，查询引擎可以将一整块压缩好的列数据放进 CPU 的 L1 缓存中，然后在紧密的循环（即没有函数调用）中遍历。相比于每条记录的处理都需要大量函数调用和条件判断的代码，CPU 执行这样一个循环要快得多。列压缩允许列中的更多行被同时放进容量有限的 L1 缓存。前面描述的按位 “与” 和 “或” 运算符可以被设计为直接在这样的压缩列数据块上操作。这种技术被称为矢量化处理（vectorized processing）。

列式存储中的排序顺序

对每列分别执行排序是没有意义的，因为那样就没法知道不同列中的哪些项属于同一行。我们只能在明确一列中的第 k 项与另一列中的第 k 项属于同一行的情况下，才能重建出完整的行。

相反，数据的排序需要对一整行统一操作，即使它们的存储方式是按列的。数据库管理员可以根据他们对常用查询的了解，来选择表格中用来排序的列。例如，如果查询通常以日期范围为目标，例如“上个月”，则可以将 date_key 作为第一个排序键。这样查询优化器就可以只扫描近 1 个月范围的行了，这比扫描所有行要快得多。

按顺序排序的另一个好处是它可以帮助压缩列。如果主要排序列没有太多个不同的值，那么在排序之后，将会得到一个相同的值连续重复多次的序列。

几个不同的排序顺序

既然不同的查询受益于不同的排序顺序，为什么不以几种不同的方式来存储相同的数据呢？反正数据都需要做备份，以防单点故障时丢失数据。因此你可以用不同排序方式来存储冗余数据，以便在处理查询时，调用最适合查询模式的版本。

写入列式存储

列式存储、压缩和排序都有助于更快地读取这些查询。然而，他们的缺点是写入更加困难。使用 B 树的就地更新方法对于压缩的列是不可能的。如果你想在排序表的中间插入一行，你很可能不得不重写所有的列文件。

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

查询操作需要检查硬盘上的列数据和内存中的最近写入，并将两者的结果合并起来。但是，查询优化器对用户隐藏了这个细节。

物化视图

数据仓库的另一个值得一提的方面是物化聚合（materialized aggregates）。如前所述，数据仓库查询通常涉及一个聚合函数，如 SQL 中的 COUNT、SUM、AVG、MIN 或 MAX。如果相同的聚合被许多不同的查询使用，可以提前缓存起来。

创建这种缓存的一种方式是物化视图（Materialized View）。在关系数据模型中，它通常被定义为一个标准（虚拟）视图：一个类似于表的对象，其内容是一些查询的结果。不同的是，物化视图是查询结果的实际副本，会被写入硬盘，而虚拟视图只是编写查询的一个捷径。当底层数据发生变化时，物化视图需要更新，因为它是数据的非规范化副本。

第四章：编码与演化

新旧版本的代码，以及新旧数据格式可能会在系统中同时共处。系统想要继续顺利运行，就需要保持 双向兼容性：

  • 向后兼容 (backward compatibility)

    新的代码可以读取由旧的代码写入的数据。

  • 向前兼容 (forward compatibility)

    旧的代码可以读取由新的代码写入的数据。

编码数据的格式

如果要将数据写入文件，或通过网络发送，则必须将其 编码（encode） 为某种自包含的字节序列（例如，JSON 文档）。 由于每个进程都有自己独立的地址空间，一个进程中的指针对任何其他进程都没有意义，所以这个字节序列表示会与通常在内存中使用的数据结构完全不同。

所以，需要在两种表示之间进行某种类型的翻译。 从内存中表示到字节序列的转换称为 编码（Encoding） （也称为 序列化（serialization） 或 编组（marshalling）），反过来称为 解码（Decoding）。

语言特定的格式

  • 这类编码通常与特定的编程语言深度绑定，其他语言很难读取这种数据。如果以这类编码存储或传输数据，那你就和这门语言绑死在一起了。

  • 在这些库中，数据版本控制通常是事后才考虑的。因为它们旨在快速简便地对数据进行编码，所以往往忽略了前向后向兼容性带来的麻烦问题。

  • Java 的内置序列化由于其糟糕的性能和臃肿的编码而臭名昭著。

因此，除非临时使用，采用语言内置编码通常是一个坏主意。

JSON、XML 和二进制变体

JSON，XML 和 CSV 属于文本格式，因此具有人类可读性，但存在一些微妙的问题：

  • 数字（numbers） 编码有很多模糊之处。在 XML 和 CSV 中，无法区分数字和碰巧由数字组成的字符串（除了引用外部模式）。 JSON 虽然区分字符串与数字，但并不区分整数和浮点数，并且不能指定精度。

  • 无法处理大数字。例如大于 253253 的整数无法使用 IEEE 754 双精度浮点数精确表示，因此在使用浮点数（例如 JavaScript）的语言进行分析时，这些数字会变得不准确。 Twitter 有一个关于大于 253253 的数字的例子，它使用 64 位整数来标识每条推文。 Twitter API 返回的 JSON 包含了两个推特 ID，一个是 JSON 数字，另一个是十进制字符串，以解决 JavaScript 程序中无法正确解析数字的问题。

  • JSON 和 XML 对 Unicode 字符串（即人类可读的文本）有很好的支持，但是它们不支持二进制数据（即不带 字符编码 (character encoding) 的字节序列）。二进制串是很有用的功能，人们通过使用 Base64 将二进制数据编码为文本来绕过此限制。其特有的模式标识着这个值应当被解释为 Base64 编码的二进制数据。这种方案虽然管用，但比较 Hacky，并且会增加三分之一的数据大小。

二进制编码

JSON 比 XML 简洁，但与二进制格式相比还是太占空间。这一事实导致大量二进制编码版本 JSON（MessagePack、BSON、BJSON、UBJSON、BISON 和 Smile 等） 和 XML（例如 WBXML 和 Fast Infoset）的出现。这些格式已经在各种各样的领域中采用，但是没有一个能像文本版 JSON 和 XML 那样被广泛采用。

所有的 JSON 的二进制编码在这方面是相似的。空间节省了一丁点（以及解析加速）是否能弥补可读性的损失，谁也说不准。

Thrift 与 Protocol Buffers

可以使用 Thrift 接口定义语言（IDL） 来描述模式，如下所示：

struct Person {
    1: required string       userName,
    2: optional i64          favoriteNumber,
    3: optional list<string> interests
}

Protocol Buffers 的等效模式定义看起来非常相似：

message Person {
    required string user_name       = 1;
    optional int64  favorite_number = 2;
    repeated string interests       = 3;
}

Thrift 和 Protocol Buffers 每一个都带有一个代码生成工具，它采用了类似于这里所示的模式定义，并且生成了以各种编程语言实现模式的类。

需要注意的一个细节：在前面所示的模式中，每个字段被标记为必需或可选，但是这对字段如何编码没有任何影响（二进制数据中没有任何字段指示某字段是否必须）。区别在于，如果字段设置为 required，但未设置该字段，则所需的运行时检查将失败，这对于捕获错误非常有用。

字段标签和模式演变

字段标记对编码数据的含义至关重要。你可以更改架构中字段的名称，因为编码的数据永远不会引用字段名称，但不能更改字段的标记，因为这会使所有现有的编码数据无效。

你可以添加新的字段到架构，只要你给每个字段一个新的标签号码。如果旧的代码试图读取新代码写入的数据，包括一个新的字段，其标签号码不能识别，它可以简单地忽略该字段。数据类型注释允许解析器确定需要跳过的字节数。这保持了向前兼容性：旧代码可以读取由新代码编写的记录。

只要每个字段都有一个唯一的标签号码，新的代码总是可以读取旧的数据，因为标签号码仍然具有相同的含义。唯一的细节是，如果你添加一个新的字段，你不能设置为必需。如果你要添加一个字段并将其设置为必需，那么如果新代码读取旧代码写入的数据，则该检查将失败，因为旧代码不会写入你添加的新字段。因此，为了保持向后兼容性，在模式的初始部署之后 添加的每个字段必须是可选的或具有默认值。

删除一个字段就像添加一个字段，只是这回要考虑的是向前兼容性。这意味着你只能删除一个可选的字段（必需字段永远不能删除），而且你不能再次使用相同的标签号码（因为你可能仍然有数据写在包含旧标签号码的地方，而该字段必须被新代码忽略）。

数据类型和模式演变

假设你将一个 32 位的整数变成一个 64 位的整数。新代码可以轻松读取旧代码写入的数据，因为解析器可以用零填充任何缺失的位。但是，如果旧代码读取由新代码写入的数据，则旧代码仍使用 32 位变量来保存该值。如果解码的 64 位值不适合 32 位，则它将被截断。

Avro

Avro 也使用模式来指定正在编码的数据的结构。 它有两种模式语言：一种（Avro IDL）用于人工编辑，一种（基于 JSON）更易于机器读取。

动态生成的模式

与 Protocol Buffers 和 Thrift 相比，Avro 方法的一个优点是架构不包含任何标签号码。Avro 对动态生成的模式更友善。例如，假如你有一个关系数据库，你想要把它的内容转储到一个文件中，并且你想使用二进制格式来避免前面提到的文本格式（JSON，CSV，SQL）的问题。如果你使用 Avro，你可以很容易地从关系模式生成一个 Avro 模式，并使用该模式对数据库内容进行编码，并将其全部转储到 Avro 对象容器文件中。

相比之下，如果你为此使用 Thrift 或 Protocol Buffers，则字段标签可能必须手动分配：每次数据库模式更改时，管理员都必须手动更新从数据库列名到字段标签的映射。这种动态生成的模式根本不是 Thrift 或 Protocol Buffers 的设计目标，而是 Avro 的。

代码生成和动态类型的语言

Thrift 和 Protobuf 依赖于代码生成：在定义了模式之后，可以使用你选择的编程语言生成实现此模式的代码。

在动态类型编程语言（如 JavaScript、Ruby 或 Python）中，生成代码没有太多意义，因为没有编译时类型检查器来满足。

Avro 为静态类型编程语言提供了可选的代码生成功能，但是它也可以在不生成任何代码的情况下使用。如果你有一个对象容器文件，你可以简单地使用 Avro 库打开它，并以与查看 JSON 文件相同的方式查看数据。该文件是自描述的，因为它包含所有必要的元数据。

模式的优点

  • 它们可以比各种 “二进制 JSON” 变体更紧凑，因为它们可以省略编码数据中的字段名称。

  • 模式是一种有价值的文档形式，因为模式是解码所必需的，所以可以确定它是最新的。

  • 维护一个模式的数据库允许你在部署任何内容之前检查模式更改的向前和向后兼容性。

  • 对于静态类型编程语言的用户来说，从模式生成代码的能力是有用的，因为它可以在编译时进行类型检查。

数据流的类型

  • 通过数据库

  • 通过服务调用

  • 通过异步消息传递

数据库中的数据流

数据库中的一个值可能会被更新版本的代码写入，然后被仍旧运行的旧版本的代码读取。因此，数据库也经常需要向前兼容。

假设你将一个字段添加到记录模式，并且较新的代码将该新字段的值写入数据库。随后，旧版本的代码（尚不知道新字段）将读取记录，更新记录并将其写回。在这种情况下，理想的行为通常是旧代码保持新的字段不变，即使它不能被解释。

在不同的时间写入不同的值

对于五年前的数据来说，除非对其进行显式重写，否则它仍然会以原始编码形式存在。这种现象有时被概括为：数据的生命周期超出代码的生命周期。

将数据重写（迁移）到一个新的模式当然是可能的，但是在一个大数据集上执行是一个昂贵的事情。大多数关系数据库都允许简单的模式更改，例如添加一个默认值为空的新列，而不重写现有数据。读取旧行时，对于磁盘上的编码数据缺少的任何列，数据库将填充空值。

因此，模式演变允许整个数据库看起来好像是用单个模式编码的，即使底层存储可能包含用各种历史版本的模式编码的记录。

归档存储

也许你不时为数据库创建一个快照，例如备份或加载到数据仓库。在这种情况下，即使源数据库中的原始编码包含来自不同时代的模式版本的混合，数据转储通常也将使用最新模式进行编码。

由于数据转储是一次写入的，而且以后是不可变的，所以 Avro 对象容器文件等格式非常适合。这也是一个很好的机会，可以将数据编码为面向分析的列式格式，例如 Parquet。

服务中的数据流：REST 与 RPC

在网络通信中，最常见的角色分为客户端和服务器。服务器通过公开 API，客户端则通过向 API 发出请求以实现连接，Web 就是利用这种方式运作的。

Web 浏览器并不是唯一的客户端类型，移动设备或桌面计算机上的应用程序也可以发出网络请求，客户端 JavaScript 程序也可以成为 HTTP 客户端。服务器返回的通常不仅仅是用于展示的 HTML，还可能包括客户端程序需要处理的编码数据，如 JSON 等。

服务器也可能是另一服务器的客户端，这种方式常用于分解大型应用程序，形成所谓的服务化架构（SOA）或微服务架构，这使得应用程序更易于更改和维护，也增强了系统的拓展性。

服务对客户端的处理也有一定的限制，这提供了一定的封装性和隔离性。我们需要考虑到服务器和客户端的旧版本和新版本需要兼容，在不同版本的服务 API 之间要保持数据编码的兼容性。

Web 服务

当服务使用 HTTP 作为底层通信协议时，可称之为 Web 服务。

有两种流行的 Web 服务方法：REST 和 SOAP。他们在哲学方面几乎是截然相反的，往往也是各自支持者之间的激烈辩论的主题。

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

SOAP Web 服务的 API 使用称为 Web 服务描述语言（WSDL）的基于 XML 的语言来描述。 WSDL 支持代码生成，客户端可以使用本地类和方法调用（编码为 XML 消息并由框架再次解码）访问远程服务。

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

  • 网络请求是不可预测的：请求或响应可能由于网络问题会丢失，或者远程计算机可能很慢或不可用，这些问题完全不在你的控制范围之内。

  • 由于超时，返回时可能没有结果。在这种情况下，你根本不知道发生了什么。

  • 如果你重试失败的网络请求，可能会发生请求实际上已经完成，只是响应丢失的情况。在这种情况下，重试将导致该操作被执行多次，除非你在协议中建立数据去重机制（幂等性，即 idempotence）。

  • 每次调用本地函数时，通常需要大致相同的时间来执行。网络请求比函数调用要慢得多，而且其延迟也是非常可变的。

  • 调用本地函数时，可以高效地将引用（指针）传递给本地内存中的对象。当你发出一个网络请求时，所有这些参数都需要被编码成可以通过网络发送的一系列字节。

  • 客户端和服务可以用不同的编程语言实现，所以 RPC 框架必须将数据类型从一种语言翻译成另一种语言。这可能会变得很丑陋，因为不是所有的语言都具有相同的类型。

RPC 的当前方向

尽管有这样那样的问题，RPC 不会消失。使用二进制编码格式的自定义 RPC 协议可以实现比通用的 JSON over REST 更好的性能。但是，RESTful API 还有其他一些显著的优点：方便实验和调试，能被所有主流的编程语言和平台所支持，还有大量可用的工具（服务器，缓存，负载平衡器，代理，防火墙，监控，调试工具，测试工具等）的生态系统。

由于这些原因，REST 似乎是公共 API 的主要风格。 RPC 框架的主要重点在于同一组织拥有的服务之间的请求，通常在同一数据中心内。

数据编码和 RPC 的演化

对于可演化性，重要的是可以独立更改和部署 RPC 客户端和服务器。我们可以在通过服务进行数据流的情况下做一个简化的假设：假定所有的服务器都会先更新，其次是所有的客户端。因此，你只需要在请求上具有向后兼容性，并且对响应具有前向兼容性。

RPC 方案的前后向兼容性属性从它使用的编码方式中继承：

  • Thrift、gRPC（Protobuf）等可以根据相应编码格式的兼容性规则进行演变。

  • 在 SOAP 中，请求和响应是使用 XML 模式指定的。这些可以演变，但有一些微妙的陷阱。

  • RESTful API 通常使用 JSON 用于响应，以及用于请求的 JSON 或 URI 编码 / 表单编码的请求参数。添加可选的请求参数并向响应对象添加新的字段通常被认为是保持兼容性的改变。

由于 RPC 经常被用于跨越组织边界的通信，所以服务的兼容性变得更加困难，因此服务的提供者经常无法控制其客户，也不能强迫他们升级。因此，需要长期保持兼容性，也许是无限期的。如果需要进行兼容性更改，则服务提供商通常会并排维护多个版本的服务 API。

关于 API 版本化应该如何工作没有一致意见。对于 RESTful API，常用的方法是在 URL 或 HTTP Accept 头中使用版本号。对于使用 API 密钥来标识特定客户端的服务，另一种选择是将客户端请求的 API 版本存储在服务器上，并允许通过单独的管理界面更新该版本选项。

消息传递中的数据流

  • 如果收件人不可用或过载，可以充当缓冲区，从而提高系统的可靠性。

  • 它可以自动将消息重新发送到已经崩溃的进程，从而防止消息丢失。

  • 避免发件人需要知道收件人的 IP 地址和端口号（这在虚拟机经常出入的云部署中特别有用）。

  • 它允许将一条消息发送给多个收件人。

  • 将发件人与收件人逻辑分离（发件人只是发布邮件，不关心使用者）。

然而，与 RPC 相比，差异在于消息传递通信通常是单向的：发送者通常不期望收到其消息的回复。一个进程可能发送一个响应，但这通常是在一个单独的通道上完成的。这种通信模式是异步的：发送者不会等待消息被传递，而只是发送它，然后忘记它。

消息代理

通常情况下，消息代理的使用方式如下：一个进程将消息发送到指定的队列或主题，代理确保将消息传递给那个队列或主题的一个或多个消费者或订阅者。在同一主题上可以有许多生产者和许多消费者。

一个主题只提供单向数据流。但是，消费者本身可能会将消息发布到另一个主题上，或者发送给原始消息的发送者使用的回复队列（允许请求 / 响应数据流，类似于 RPC）。

消息代理通常不会执行任何特定的数据模型 —— 消息只是包含一些元数据的字节序列，因此你可以使用任何编码格式。如果编码是向后和向前兼容的，你可以灵活地对发布者和消费者的编码进行独立的修改，并以任意顺序进行部署。

如果消费者重新发布消息到另一个主题，则可能需要小心保留未知字段。

第五章：复制

我们希望能复制数据，可能出于各种各样的原因：

  • 使得数据与用户在地理上接近（从而减少延迟）

  • 即使系统的一部分出现故障，系统也能继续工作（从而提高可用性）

  • 伸缩可以接受读请求的机器数量（从而提高读取吞吐量）

复制的困难之处在于处理复制数据的 变更（change），有三种流行的变更复制算法：单领导者（single leader，单主），多领导者（multi leader，多主） 和 无领导者（leaderless，无主）。

领导者和追随者

每一次向数据库的写入操作都需要传播到所有副本上，否则副本就会包含不一样的数据。最常见的解决方案被称为 基于领导者的复制（leader-based replication） （也称 主/从（master/slave） 复制）

  1. 其中一个副本被指定为 领导者（leader），也称为 主库（master|primary） 。当客户端要向数据库写入时，它必须将请求发送给该 领导者，其会将新数据写入其本地存储。

  2. 其他副本被称为 追随者（followers），亦称为 只读副本（read replicas）、从库（slaves）、备库（ secondaries）。每当领导者将新数据写入本地存储时，它也会将数据变更发送给所有的追随者，称之为 复制日志（replication log）。每个跟随者从领导者拉取日志，并相应更新其本地数据库副本。

  3. 当客户想要从数据库中读取数据时，它可以向领导者或任一追随者进行查询。但只有领导者才能接受写入操作（从客户端的角度来看从库都是只读的）。

这种复制模式是许多关系数据库的内置功能，基于领导者的复制并不仅限于数据库，像 Kafka 和 RabbitMQ 高可用队列这样的分布式消息代理也使用它。

同步复制与异步复制

同步复制的优点是，从库能保证有与主库一致的最新数据副本。如果主库突然失效，我们可以确信这些数据仍然能在从库上找到。缺点是，如果同步从库没有响应（比如它已经崩溃，或者出现网络故障，或其它任何原因），主库就无法处理写入操作。

因此，将所有从库都设置为同步的是不切实际的：实际上，如果在数据库上启用同步复制，通常意味着其中 一个 从库是同步的，而其他的从库则是异步的。如果该同步从库变得不可用或缓慢，则将一个异步从库改为同步运行。这保证你至少在两个节点上拥有最新的数据副本：主库和同步从库。 这种配置有时也被称为 半同步（semi-synchronous）。

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

设置新从库

简单地将数据文件从一个节点复制到另一个节点通常是不够的：客户端不断向数据库写入数据，数据总是在不断地变化。

可以通过锁定数据库（使其不可用于写入）来使磁盘上的文件保持一致，但是这会违背高可用的目标。我们可以使用如下过程：

  1. 在某个时刻获取主库的一致性快照。大多数数据库都具有这个功能，因为它是备份必需的。

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

  3. 从库连接到主库，并拉取快照之后发生的所有数据变更。这要求快照与主库复制日志中的位置精确关联。MySQL 将其称为 二进制日志坐标（binlog coordinates）。

  4. 当从库处理完快照之后积累的数据变更，我们就说它 赶上（caught up） 了主库。

处理节点宕机

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

从库失效：追赶恢复

从库可以从日志中知道，在发生故障之前处理的最后一个事务。因此，从库可以连接到主库，并请求在从库断开期间发生的所有数据变更。当应用完所有这些变更后，它就赶上了主库，并可以像以前一样继续接收数据变更流。

主库失效：故障切换

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

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

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

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

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

故障切换的过程中有很多地方可能出错：

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

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

  • 发生某些故障时可能会出现两个节点都以为自己是主库的情况。这种情况称为 脑裂 (split brain)，非常危险：如果两个主库都可以接受写操作，却没有冲突解决机制，那么数据就可能丢失或损坏。

  • 超时配置问题，在主库失效的情况下，超时时间越长意味着恢复时间也越长。但是如果超时设置太短，又可能会出现不必要的故障切换。

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

复制日志的实现

实践中有好几种不同的复制方式。

基于语句的复制

主库记录下它执行的每个写入请求（语句，即 statement）并将该语句日志发送给从库，每个从库解析并执行该 SQL 语句，就像直接从客户端收到一样。

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

  • 任何调用 非确定性函数（nondeterministic） 的语句，可能会在每个副本上生成不同的值。例如，使用 NOW() 获取当前日期时间，或使用 RAND() 获取一个随机数。

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

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

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

基于语句的复制在 5.1 版本前的 MySQL 中被使用到。因为它相当紧凑，现在有时候也还在用。但现在在默认情况下，如果语句中存在任何不确定性，MySQL 会切换到基于行的复制。

传输预写式日志（WAL）

对于覆写单个磁盘块的 B 树，每次修改都会先写入 预写式日志（Write Ahead Log, WAL），以便崩溃后索引可以恢复到一个一致的状态。

该日志是包含了所有数据库写入的仅追加字节序列。可以使用完全相同的日志在另一个节点上构建副本：除了将日志写入磁盘之外，主库还可以通过网络将其发送给从库。通过使用这个日志，从库可以构建一个与主库一模一样的数据结构拷贝。

看上去这可能只是一个小的实现细节，但却可能对运维产生巨大的影响。如果复制协议允许从库使用比主库更新的软件版本，则可以先升级从库，然后执行故障切换，使升级后的节点之一成为新的主库，从而允许数据库软件的零停机升级。

逻辑日志复制（基于行）

复制和存储引擎使用不同的日志格式，这样可以将复制日志从存储引擎的内部实现中解耦出来。这种复制日志被称为逻辑日志（logical log），以将其与存储引擎的（物理）数据表示区分开来。

  • 对于插入的行，日志包含所有列的新值。

  • 对于删除的行，日志包含足够的信息来唯一标识被删除的行，这通常是主键，但如果表上没有主键，则需要记录所有列的旧值。

  • 对于更新的行，日志包含足够的信息来唯一标识被更新的行，以及所有列的新值（或至少所有已更改的列的新值）。

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

由于逻辑日志与存储引擎的内部实现是解耦的，系统可以更容易地做到向后兼容，从而使主库和从库能够运行不同版本的数据库软件，或者甚至不同的存储引擎。

基于触发器的复制

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

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

复制延迟问题

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

在正常的操作中，复制延迟（replication lag），即写入主库到反映至从库之间的延迟，可能仅仅是几分之一秒，在实践中并不显眼。但如果系统在接近极限的情况下运行，或网络中存在问题时，延迟可以轻而易举地超过几秒，甚至达到几分钟。

读你所写

如果用户在写入后马上就查看数据，则新数据可能尚未到达副本。对用户而言，看起来好像是刚提交的数据丢失了。

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

  • 对于用户 可能修改过 的内容，总是从主库读取；这就要求得有办法不通过实际的查询就可以知道用户是否修改了某些东西。例如总是从主库读取用户自己的档案，如果要读取其他用户的档案就去从库。

  • 如果应用中的大部分内容都可能被用户编辑，可以使用其他标准来决定是否从主库读取。例如可以跟踪上次更新的时间，在上次更新后的一分钟内，从主库读。还可以监控从库的复制延迟，防止向任何滞后主库超过一分钟的从库发出查询。

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

  • 如果你的副本分布在多个数据中心（为了在地理上接近用户或者出于可用性目的），还会有额外的复杂性。任何需要由主库提供服务的请求都必须路由到包含该主库的数据中心。

另一种复杂的情况发生在同一位用户从多个设备请求服务的时候，这种情况下可能就需要提供跨设备的写后读一致性。

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

  • 记住用户上次更新时间戳的方法变得更加困难，因为一个设备上运行的程序不知道另一个设备上发生了什么。需要对这些元数据进行中心化的存储。

  • 如果副本分布在不同的数据中心，很难保证来自不同设备的连接会路由到同一数据中心。如果你的方法需要读主库，可能首先需要把来自该用户所有设备的请求都路由到同一个数据中心。

单调读

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

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

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

一致前缀读

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

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

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

一种解决方案是，确保任何因果相关的写入都写入相同的分区，但在一些应用中可能无法高效地完成这种操作。

复制延迟的解决方案

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

数据库通过事务提供强大的保证，所以应用程序可以更加简单。单节点事务已经存在了很长时间。然而在走向分布式（复制和分区）数据库时，许多系统放弃了事务，声称事务在性能和可用性上的代价太高，并断言在可伸缩系统中最终一致性是不可避免的。

多主复制

基于领导者的复制模型的自然延伸是允许多个节点接受写入。复制仍然以同样的方式发生：处理写入的每个节点都必须将该数据变更转发给所有其他节点。我们将其称之为 多领导者配置（multi-leader configuration，也称多主、多活复制，即 master-master replication 或 active/active replication）。在这种情况下，每个主库同时是其他主库的从库。

多主复制的应用场景

在单个数据中心内部使用多个主库的配置没有太大意义，因为其导致的复杂性已经超过了能带来的好处。

运维多个数据中心

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

  • 性能

在多主配置中，每个写操作都可以在本地数据中心进行处理，并与其他数据中心异步复制。因此，数据中心之间的网络延迟对用户来说是透明的，这意味着感觉到的性能可能会更好。

  • 容忍数据中心停机

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

  • 容忍网络问题

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

尽管多主复制有这些优势，但也有一个很大的缺点：两个不同的数据中心可能会同时修改相同的数据，写冲突是必须解决的。

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

需要离线操作的客户端

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

从架构的角度来看，这种设置实际上与数据中心之间的多主复制类似，每个设备都是一个 “数据中心”，而它们之间的网络连接是极度不可靠的。

协同编辑

我们通常不会将协作式编辑视为数据库复制问题，但它与前面提到的离线编辑用例有许多相似之处。当一个用户编辑文档时，所做的更改将立即应用到其本地副本，并异步复制到服务器和编辑同一文档的任何其他用户。

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

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

处理写入冲突

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

同步与异步冲突检测

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

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

避免冲突

由于许多的多主复制实现在处理冲突时处理得相当不好，避免冲突是一个经常被推荐的方法。

在一个用户可以编辑自己数据的应用程序中，可以确保来自特定用户的请求始终路由到同一数据中心，并使用该数据中心的主库进行读写。不同的用户可能有不同的 “主” 数据中心，但从任何一位用户的角度来看，本质上就是单主配置了。

但是，有时你可能需要更改被指定的主库，在这种情况下，冲突避免将失效，你必须处理不同主库同时写入的可能性。

收敛至一致的状态

  • 给每个写入一个唯一的 ID（例如时间戳、长随机数、UUID 或者键和值的哈希），挑选最高 ID 的写入作为胜利者，并丢弃其他写入。如果使用时间戳，这种技术被称为 最后写入胜利（LWW, last write wins）。虽然这种方法很流行，但是很容易造成数据丢失。

  • 为每个副本分配一个唯一的 ID，ID 编号更高的写入具有更高的优先级。这种方法也意味着数据丢失。

  • 以某种方式将这些值合并在一起。

  • 用一种可保留所有信息的显式数据结构来记录冲突，并编写解决冲突的应用程序代码（也许通过提示用户的方式）。

自定义冲突解决逻辑

  • 写时执行

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

  • 读时执行

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

请注意，冲突解决通常适用于单行记录或单个文档的层面，而不是整个事务。

什么是冲突

两个写操作并发地修改了同一条记录中的同一个字段，并将其设置为两个不同的值。毫无疑问这是一个冲突。

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

多主复制拓扑

最常见的拓扑是全部到全部，其中每个主库都将其写入发送给其他所有的主库。默认情况下 MySQL 仅支持 环形拓扑（circular topology），其中每个节点都从一个节点接收写入，并将这些写入（加上自己的写入）转发给另一个节点。另一种流行的拓扑结构具有星形的形状：一个指定的根节点将写入转发给所有其他节点。星形拓扑可以推广到树。

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

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

无主复制

一些数据存储系统采用不同的方法，放弃主库的概念，并允许任何副本直接接受来自客户端的写入。

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

当节点故障时写入数据库

假设三个副本中的两个承认写入是足够的：在用户 1234 已经收到两个确定的响应之后，我们认为写入成功。客户简单地忽略了其中一个副本错过了写入的事实。

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

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

读修复和反熵

  • 读修复（Read repair）

    当客户端并行读取多个节点时，它可以检测到任何陈旧的响应。客户端发现副本具有陈旧值，并将新值写回到该副本。这种方法适用于读频繁的值。

  • 反熵过程（Anti-entropy process）

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

如果没有反熵过程，很少被读取的值可能会从某些副本中丢失，从而降低了持久性，因为只有在应用程序读取值时才执行读修复。

读写的法定人数

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

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

法定人数一致性的局限性

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

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

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

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

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

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

  • 如果写操作在某些副本上成功，而在其他节点上失败，在小于 w 个副本上写入成功。所以整体判定写入失败，但整体写入失败并没有在写入成功的副本上回滚。后续的读取仍然可能会读取这次失败写入的值。

  • 如果携带新值的节点发生故障，需要从其他带有旧值的副本进行恢复，则存储新值的副本数可能会低于 w，从而打破法定人数条件。

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

Dynamo 风格的数据库通常针对可以忍受最终一致性的用例进行优化。你可以通过参数 w 和 r 来调整读取到陈旧值的概率，但把它们当成绝对的保证是不明智的。

监控陈旧度

从运维的角度来看，监视你的数据库是否返回最新的结果是很重要的。即使应用可以容忍陈旧的读取，你也需要了解复制的健康状况。

对于基于领导者的复制，你可以将其提供给监视系统。写入是按照相同的顺序应用于主库和从库，并且每个节点对应了复制日志中的一个位置（已经在本地应用的写入数量）。通过从主库的当前位置中减去从库的当前位置，你可以测量复制延迟的程度。

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

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

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

  • 对于所有无法达到 w 或 r 个节点法定人数的请求，是否返回错误是更好的？

  • 或者我们是否应该接受写入，然后将它们写入一些可达的节点，但不在这些值通常所存在的 n 个节点上？

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

一旦网络中断得到解决，一个节点代表另一个节点临时接受的任何写入都将被发送到适当的 “主” 节点。这就是所谓的 提示移交（hinted handoff）。

宽松的法定人数对写入可用性的提高特别有用：只要有任何 w 个节点可用，数据库就可以接受写入。

在传统意义上，宽松的法定人数实际上并不是法定人数。它只是一个持久性的保证，即数据已存储在某处的 w 个节点。但不能保证 r 个节点的读取能看到它，除非提示移交已经完成。

运维多个数据中心

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

副本的数量 n 包括所有数据中心的节点，你可以在配置中指定每个数据中心所拥有的副本的数量。客户端的写入都会发送到所有副本，但客户端通常只等待来自其本地数据中心内的法定节点的确认，从而不会受到跨数据中心链路延迟和中断的影响。对其他数据中心的高延迟写入通常被配置为异步执行，尽管该配置仍有一定的灵活性。

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

检测并发写入

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

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

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

当客户端向数据库节点发送写入请求时，两个客户端都不知道另一个客户端，因此不清楚哪一个先发送请求。事实上，说这两种情况谁先发送请求是没有意义的：既然我们说写入是 并发（concurrent） 的，那么它们的顺序就是不确定的。

我们可以强制进行排序。例如，可以为每个写入附加一个时间戳，然后挑选最大的时间戳作为 “最近的”，并丢弃具有较早时间戳的任何写入。这种冲突解决算法被称为 最后写入胜利（LWW, last write wins），是 Cassandra 唯一支持的冲突解决方法。

LWW 实现了最终收敛的目标，但以 持久性 为代价：如果同一个键有多个并发写入，即使它们反馈给客户端的结果都是成功的（因为它们被写入 w 个副本），也只有一个写入将被保留，而其他写入将被默默地丢弃。

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

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

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

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

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

捕获“此前发生”关系

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

服务器可以只通过查看版本号来确定两个操作是否是并发的 —— 它不需要对值本身进行解释（因此该值可以是任何数据结构）。

  • 服务器为每个键维护一个版本号，每次写入该键时都递增版本号，并将新版本号与写入的值一起存储。

  • 当客户端读取键时，服务器将返回所有未覆盖的值以及最新的版本号。客户端在写入前必须先读取。

  • 当客户端写入键时，必须包含之前读取的版本号，并且必须将之前读取的所有值合并在一起。

  • 当服务器接收到具有特定版本号的写入时，它可以覆盖该版本号或更低版本的所有值（因为它知道它们已经被合并到新的值中），但是它必须用更高的版本号来保存所有值（因为这些值与正在进行的其它写入是并发的）。

合并并发写入的值

合并并发值，本质上是与多主复制中的冲突解决问题相同。一个简单的方法是根据版本号或时间戳（最后写入胜利）来选择一个值，但这意味着丢失数据。

以购物车为例，一种合理的合并值的方法就是做并集。在上图中，最后的两个兄弟是 [牛奶，面粉，鸡蛋，熏肉] 和 [鸡蛋，牛奶，火腿]。注意牛奶和鸡蛋虽然同时出现在两个并发值里，但他们每个只被写过一次。合并的值可以是 [牛奶，面粉，鸡蛋，培根，火腿]，不再有重复了。

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

版本向量

当多个副本并发接受写入时，只使用单个版本号是不够的。我们还需要对 每个副本 使用版本号。每个副本在处理写入时增加自己的版本号，并且跟踪从其他副本中看到的版本号。这个信息指出了要覆盖哪些并发值，以及要保留哪些并发值或兄弟值。

所有副本的版本号集合称为 版本向量（version vector）。当读取值时，版本向量会从数据库副本发送到客户端，并且随后写入值时需要将其发送回数据库。

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

第六章：分区

对于非常大的数据集，或非常高的吞吐量，仅仅进行复制是不够的：我们需要将数据进行 分区（partitions），也称为 分片（sharding）。

分区与复制

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

键值数据的分区

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

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

现在假设你有一个简单的键值数据模型，其中你总是通过其主键访问记录。例如，在一本老式的纸质百科全书中，你可以通过标题来查找一个条目；由于所有条目按字母顺序排序，因此你可以快速找到你要查找的条目。

根据键的范围分区

一种分区的方法是为每个分区指定一块连续的键范围（从最小值到最大值），如纸质百科全书的卷。如果知道范围之间的边界，则可以轻松确定哪个分区包含某个值。

键的范围不一定均匀分布，因为数据也很可能不均匀分布。只是简单的规定每个卷包含两个字母会导致一些卷比其他卷大。

Key Range 分区的缺点是某些特定的访问模式会导致热点。 如果主键是时间戳，则分区对应于时间范围，例如，给每天分配一个分区，那么所有写入操作都会转到同一个分区（即今天的分区），这样分区可能会因写入而过载，而其他分区则处于空闲状态。

为了避免这个问题，需要使用除了时间戳以外的其他东西作为主键的第一个部分。 例如，可以在每个时间戳前添加测量名称，这样会首先按名称，然后按时间进行分区。 假设有多个测量同时运行，写入负载将最终均匀分布在不同分区上。 现在，当想要在一个时间范围内获取多个测量的值时，你需要为每个测量名称执行一个单独的范围查询。

根据键的散列分区

出于分区的目的，散列函数不需要多么强壮的加密算法：例如，Cassandra 和 MongoDB 使用 MD5。一旦你有一个合适的键散列函数，你可以为每个分区分配一个散列范围（而不是键的范围），每个通过哈希散列落在分区范围内的键将被存储在该分区中。

通过使用键散列进行分区，我们失去了高效执行范围查询的能力。曾经相邻的键现在分散在所有分区中，所以它们之间的顺序就丢失了。在 MongoDB 中，如果你使用了基于散列的分区模式，则任何范围查询都必须发送到所有分区。

Cassandra 采取了折衷的策略。 Cassandra 中的表可以使用由多个列组成的复合主键来声明。键中只有第一列会作为散列的依据，而其他列则被用作 Casssandra 的 SSTables 中排序数据的连接索引。

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

负载偏斜与热点消除

哈希分区可以帮助减少热点。但是，它不能完全避免它们：在极端情况下，所有的读写操作都是针对同一个键的，所有的请求都会被路由到同一个分区。

在社交媒体网站上，一个拥有数百万粉丝的用户在做某事时可能会引发一场风暴。这个事件可能导致同一个键的大量写入（键可能是名人的用户 ID，或者人们正在评论的动作的 ID）。哈希策略不起作用，因为两个相同 ID 的哈希值仍然是相同的。

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

然而，将主键进行分割之后，任何读取都必须要做额外的工作，因为他们必须从所有 100 个主键分布中读取数据并将其合并。

分区与次级索引

如果只通过主键访问记录，我们可以从该键确定分区，并使用它来将读写请求路由到负责该键的分区。如果涉及次级索引，情况会变得更加复杂。次级索引通常并不能唯一地标识记录，而是一种搜索记录中出现特定值的方式，例如查找所有颜色为红色的车辆。

次级索引的问题是它们不能整齐地映射到分区。有两种用次级索引对数据库进行分区的方法：基于文档的分区（document-based） 和 基于关键词（term-based）的分区。

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

每个列表都有一个唯一的 ID，称之为文档 ID，并且用文档 ID 对数据库进行分区（例如，分区 0 中的 ID 0 到 499，分区 1 中的 ID 500 到 999 等）。

你想让用户搜索汽车，允许他们通过颜色和厂商过滤，所以需要一个在颜色和厂商上的次级索引。

在这种索引方法中，每个分区是完全独立的：每个分区维护自己的次级索引，只需处理包含你正在编写的文档 ID 的分区即可。出于这个原因，文档分区索引 也被称为 本地索引。

但是，从文档分区索引中读取需要注意：除非你对文档 ID 做了特别的处理，否则没有理由将所有具有特定颜色或特定品牌的汽车放在同一个分区中。如果要搜索红色汽车，则需要将查询发送到所有分区，并合并所有返回的结果。

基于关键词（Term）的次级索引进行分区

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

来自所有分区的红色汽车在红色索引中，并且索引是分区的，首字母从 a 到 r 的颜色在分区 0 中，s 到 z 的在分区 1。

我们将这种索引称为 关键词分区（term-partitioned），因为我们寻找的关键词决定了索引的分区方式。例如，一个关键词可能是：color:red。

关键词分区的全局索引优于文档分区索引的地方点是不需要 分散 / 收集 所有分区，客户端只需要向包含关键词的分区发出请求。全局索引的缺点在于写入速度较慢且较为复杂，因为写入单个文档现在可能会影响索引的多个分区。

理想情况下，索引总是最新的，写入数据库的每个文档都会立即反映在索引中。但是，在关键词分区索引中，这需要跨分区的分布式事务。

在实践中，对全局次级索引的更新通常是 异步 的（也就是说，如果在写入之后不久读取索引，刚才所做的更改可能尚未反映在索引中）。

分区再平衡

  • 查询吞吐量增加，所以你想要添加更多的 CPU 来处理负载。

  • 数据集大小增加，所以你想添加更多的磁盘和 RAM 来存储它。

  • 机器出现故障，其他机器需要接管故障机器的责任。

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

再平衡策略

有几种不同的分区分配方法。

反面教材：hash mod N

如果节点数量 N 发生变化，大多数键将需要从一个节点移动到另一个节点。例如，假设 hash(key) = 123456。如果最初有 10 个节点，那么这个键一开始放在节点 6 上（因为 123456 mod 10 = 6）。当你增长到 11 个节点时，键需要移动到节点 3（123456 mod 11 = 3），当你增长到 12 个节点时，需要移动到节点 0（123456 mod 12 = 0）。这种频繁的举动使得再平衡的成本过高。

固定数量的分区

有一个相当简单的解决方案：创建比节点更多的分区，并为每个节点分配多个分区。例如，运行在 10 个节点的集群上的数据库可能会从一开始就被拆分为 1,000 个分区，因此大约有 100 个分区被分配给每个节点。

现在，如果一个节点被添加到集群中，新节点可以从当前每个节点中 窃取 一些分区，直到分区再次公平分配。如果从集群中删除一个节点，则会发生相反的情况。

这种变更并不是即时的 — 在网络上传输大量的数据需要一些时间 — 所以在传输过程中，原有分区仍然会接受读写操作。

动态分区

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

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

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

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

按节点比例分区

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

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

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

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

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

请求路由

如果我想读或写键 “foo”，需要连接哪个 IP 地址和端口号？

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

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

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

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

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

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

执行并行查询

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

第七章：事务

事务（transaction） 一直是简化可靠性问题的首选机制。事务是应用程序将多个读写操作组合成一个逻辑单元的一种方式。从概念上讲，事务中的所有读写操作被视作单个操作来执行：整个事务要么成功 提交（commit），要么失败 中止（abort）或 回滚（rollback）。

事务的棘手概念

2000 年以后，非关系（NoSQL）数据库开始普及。它们的目标是在关系数据库的现状基础上，通过提供新的数据模型选择并默认包含复制和分区来进一步提升。事务是这次运动的主要牺牲品：这些新一代数据库中的许多数据库完全放弃了事务，或者重新定义了这个词，描述比以前所理解的更弱得多的一套保证。

随着这种新型分布式数据库的炒作，人们普遍认为事务是可伸缩性的对立面，任何大型系统都必须放弃事务以保持良好的性能和高可用性。另一方面，数据库厂商有时将事务保证作为 “重要应用” 和 “有价值数据” 的基本要求。这两种观点都是 纯粹的夸张。

事实并非如此简单：与其他技术设计选择一样，事务有其优势和局限性。

ACID 的含义

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

今天，当一个系统声称自己 “符合 ACID” 时，实际上能期待的是什么保证并不清楚。不幸的是，ACID 现在几乎已经变成了一个营销术语。

原子性

在多线程编程中，如果一个线程执行一个原子操作，这意味着另一个线程无法看到该操作的中间结果。系统只能处于操作之前或操作之后的状态，而不是介于两者之间的状态。

相比之下，ACID 的原子性并 不 是关于 并发（concurrent） 的。它并不是在描述如果几个进程试图同时访问相同的数据会发生什么情况，这种情况包含在缩写 I 中，即隔离性。

ACID 原子性的定义特征是：能够在错误时中止事务，丢弃该事务进行的所有写入变更的能力。 或许 可中止性（abortability） 是更好的术语，但本书将继续使用原子性，因为这是惯用词。

一致性

ACID 一致性的概念是，对数据的一组特定约束必须始终成立。即 不变式（invariants）。例如，在会计系统中，所有账户整体上必须借贷相抵。

但是，一致性的这种概念取决于应用程序对不变式的理解，应用程序负责正确定义它的事务，并保持一致性。这并不是数据库可以保证的事情：如果你写入违反不变式的脏数据，数据库也无法阻止你（一些特定类型的不变式可以由数据库检查，例如外键约束或唯一约束）。

原子性，隔离性和持久性是数据库的属性，而一致性（在 ACID 意义上）是应用程序的属性。应用可能依赖数据库的原子性和隔离属性来实现一致性，但这并不仅取决于数据库。

隔离性

大多数数据库都会同时被多个客户端访问。如果它们各自读写数据库的不同部分，这是没有问题的，但是如果它们访问相同的数据库记录，则可能会遇到 并发 问题（竞争条件，即 race conditions）。

ACID 意义上的隔离性意味着，同时执行的事务是相互隔离的：它们不能相互冒犯。传统的数据库教科书将隔离性形式化为 可串行化（Serializability）。

在 Oracle 中有一个名为 “可串行的” 隔离级别，但实际上它实现了一种叫做 快照隔离（snapshot isolation） 的功能，这是一种比可串行化更弱的保证。

持久性

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

它通常包括预写日志或类似的文件，以便在磁盘上的数据结构损坏时进行恢复。在带复制的数据库中，持久性可能意味着数据已成功复制到一些节点。为了提供持久性保证，数据库必须等到这些写入或复制完成后，才能报告事务成功提交。

完美的持久性是不存在的 ：如果所有硬盘和所有备份同时被销毁，那显然没有任何数据库能救得了你。

单对象和多对象操作

许多非关系数据库并没有将这些操作组合在一起的方法。即使存在多对象 API（例如，某键值存储可能具有在一个操作中更新几个键的 multi-put 操作），但这并不一定意味着它具有事务语义：该命令可能在一些键上成功，在其他的键上失败，使数据库处于部分更新的状态。

单对象写入

假设你正在向数据库写入一个 20 KB 的 JSON 文档：

  • 如果在发送第一个 10 KB 之后网络连接中断，数据库是否存储了不可解析的 10KB JSON 片段？

  • 如果在数据库正在覆盖磁盘上的前一个值的过程中电源发生故障，是否最终将新旧值拼接在一起？

  • 如果另一个客户端在写入过程中读取该文档，是否会看到部分更新的值？

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

一些数据库也提供更复杂的原子操作，例如自增操作，这样就不再需要读取 - 修改 - 写入序列了。同样流行的是 CAS 操作，仅当值没有被其他并发修改过时，才允许执行写操作。

多对象事务的需求

许多分布式数据存储已经放弃了多对象事务，因为多对象事务很难跨分区实现，而且在需要高可用性或高性能的情况下，它们可能会碍事。

有一些场景中，单对象插入，更新和删除是足够的。但是许多其他场景需要协调写入几个不同的对象：

  • 在关系数据模型中，一个表中的行通常具有对另一个表中的行的外键引用。多对象事务使你确保这些引用始终有效：当插入几个相互引用的记录时，外键必须是正确的和最新的，不然数据就没有意义。

  • 在具有次级索引的数据库中，每次更改值时都需要更新索引。从事务角度来看，这些索引是不同的数据库对象：例如，如果没有事务隔离性，记录可能出现在一个索引中，但没有出现在另一个索引中，因为第二个索引的更新还没有发生。

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

处理错误和中止

事务的一个关键特性是，如果发生错误，它可以中止并安全地重试。 ACID 数据库基于这样的哲学：如果数据库有违反其原子性，隔离性或持久性的危险，则宁愿完全放弃事务，而不是留下半成品。

错误发生不可避免，但许多软件开发人员倾向于只考虑乐观情况，而不是错误处理的复杂性。例如，像一些对象关系映射（ORM, object-relation Mapping）框架不会重试中断的事务 —— 这个错误通常会导致一个从堆栈向上传播的异常。

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

  • 如果事务实际上成功了，但是在服务器试图向客户端确认提交成功时网络发生故障（所以客户端认为提交失败了），那么重试事务会导致事务被执行两次 —— 除非你有一个额外的去重机制。

  • 如果错误是由于负载过大造成的，则重试事务将使问题变得更糟，而不是更好。为了避免这种正反馈循环，可以限制重试次数，使用指数退避算法，并单独处理与过载相关的错误。

  • 仅在临时性错误（例如，由于死锁，异常情况，临时性网络中断和故障切换）后才值得重试。在发生永久性错误（例如，违反约束）之后重试是毫无意义的。

  • 如果事务在数据库之外也有副作用，即使事务被中止，也可能发生这些副作用。例如，如果你正在发送电子邮件，那你肯定不希望每次重试事务时都重新发送电子邮件。如果你想确保几个不同的系统一起提交或放弃，两阶段提交（2PC, two-phase commit） 可以提供帮助。

  • 如果客户端进程在重试中失效，任何试图写入数据库的数据都将丢失。

弱隔离级别

如果两个事务不触及相同的数据，它们可以安全地 并行（parallel） 运行，因为两者都不依赖于另一个。

隔离并没有那么简单。可串行的隔离 会有性能损失，许多数据库不愿意支付这个代价。因此，系统通常使用较弱的隔离级别来防止一部分，而不是全部的并发问题。

读已提交

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

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

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

没有脏读

设想一个事务已经将一些数据写入数据库，但事务还没有提交或中止。另一个事务可以看到未提交的数据吗？如果是的话，那就叫做 脏读（dirty reads）。

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

  • 如果事务需要更新多个对象，脏读取意味着另一个事务可能会只看到一部分更新。例如，用户看到新的未读电子邮件，但看不到更新的数量。这就是电子邮件的脏读。看到处于部分更新状态的数据库会让用户感到困惑，并可能导致其他事务做出错误的决定。

  • 如果事务中止，则所有写入操作都需要回滚。如果数据库允许脏读，那就意味着一个事务可能会看到稍后需要回滚的数据，即从未实际提交给数据库的数据。想想后果就让人头大。

没有脏写

如果先前的写入是尚未提交事务的一部分，又会发生什么情况，后面的写入会覆盖一个尚未提交的值？这被称作 脏写（dirty write）。在 读已提交 的隔离级别上运行的事务必须防止脏写，通常是延迟第二次写入，直到第一次写入事务提交或中止为止。

以一个二手车销售网站为例，Alice 和 Bob 两个人同时试图购买同一辆车。购买汽车需要两次数据库写入：网站上的商品列表需要更新，以反映买家的购买，销售发票需要发送给买家。本来销售是属于 Bob 的（因为他成功更新了商品列表），但发票却寄送给了 Alice（因为她成功更新了发票表）。读已提交会防止这样的事故。

实现读已提交

最常见的情况是，数据库通过使用 行锁（row-level lock） 来防止脏写：当事务想要修改特定对象（行或文档）时，它必须首先获得该对象的锁。然后必须持有该锁直到事务被提交或中止。一次只有一个事务可持有任何给定对象的锁；如果另一个事务要写入同一个对象，则必须等到第一个事务提交或中止后，才能获取该锁并继续。这种锁定是读已提交模式（或更强的隔离级别）的数据库自动完成的。

防止脏读的一种选择是使用相同的锁，并要求任何想要读取对象的事务获取该锁，然后在读取之后立即释放该锁。这将确保在对象具有脏的、未提交的值时不会发生读取（因为在此期间，锁将由进行写入的事务持有）。

但是要求读锁的办法在实践中效果并不好。因为一个长时间运行的写入事务会迫使许多只读事务等到这个慢写入事务完成。

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

快照隔离和可重复读

Alice 在银行有 1000 美元的储蓄，分为两个账户，每个 500 美元。现在有一笔事务从她的一个账户转移了 100 美元到另一个账户。如果她在事务处理的过程中查看其账户余额，她可能会在收到付款之前先看到一个账户的余额（收款账户，余额仍为 500 美元），在发出转账之后再看到另一个账户的余额（付款账户，新余额为 400 美元）。对 Alice 来说，现在她的账户似乎总共只有 900 美元 —— 看起来有 100 美元已经凭空消失了。

这种异常被称为 不可重复读（nonrepeatable read） 或 读取偏差（read skew）：如果 Alice 在事务结束时再次读取账户 1 的余额，她将看到与她之前的查询中看到的不同的值（600 美元）。在读已提交的隔离条件下，不可重复读 被认为是可接受的：Alice 看到的帐户余额确实在阅读时已经提交了。

有些情况下，不能容忍这种暂时的不一致：

  • 备份

    进行备份需要复制整个数据库，对大型数据库而言可能需要花费数小时才能完成。备份进程运行时，数据库仍然会接受写入操作。因此备份可能会包含一些旧的部分和一些新的部分。如果从这样的备份中恢复，那么不一致（如消失的钱）就会变成永久的。

  • 分析查询和完整性检查

    有时，你可能需要运行一个查询，扫描大部分的数据库。这样的查询在分析中很常见，也可能是定期完整性检查。如果这些查询在不同时间点观察数据库的不同部分，则可能会返回毫无意义的结果。

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

快照隔离对长时间运行的只读查询（如备份和分析）非常有用。如果查询的数据在查询执行的同时发生变化，则很难理解查询的含义。

实现快照隔离

从性能的角度来看，快照隔离的一个关键原则是：读不阻塞写，写不阻塞读。这允许数据库在处理一致性快照上的长时间查询时，可以正常地同时处理写入操作，且两者间没有任何锁争用。

数据库必须可能保留一个对象的几个不同的提交版本，因为各种正在进行的事务可能需要看到数据库在不同的时间点的状态。因为它同时维护着单个对象的多个版本，所以这种技术被称为 多版本并发控制（MVCC, multi-version concurrency control）。

支持快照隔离的存储引擎通常也使用 MVCC 来实现 读已提交 隔离级别。一种典型的方法是 读已提交 为每个查询使用单独的快照，而 快照隔离 对整个事务使用相同的快照。

表中的每一行都有一个 created_by 字段，其中包含将该行插入到表中的的事务 ID。此外，每行都有一个 deleted_by 字段，最初是空的。如果某个事务删除了一行，那么该行实际上并未从数据库中删除，而是进行标记删除。在稍后的时间，当确定没有事务可以再访问已删除的数据时，数据库中的垃圾收集过程会将所有带有删除标记的行移除，并释放其空间。

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

  1. 在每次事务开始时，数据库列出当时所有其他（尚未提交或尚未中止）的事务清单，即使之后提交了，这些事务已执行的任何写入也都会被忽略。

  2. 被中止事务所执行的任何写入都将被忽略。

  3. 由具有较晚事务 ID（即，在当前事务开始之后开始的）的事务所做的任何写入都被忽略，而不管这些事务是否已经提交。

  4. 所有其他写入，对应用都是可见的。

换句话说，如果以下两个条件都成立，则可见一个对象：

  • 读事务开始时，创建该对象的事务已经提交。

  • 对象未被标记为删除，或如果被标记为删除，请求删除的事务在读事务开始时尚未提交。

索引和快照隔离

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

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

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

防止丢失更新

如果应用从数据库中读取一些值，修改它并写回修改的值（读取 - 修改 - 写入序列），则可能会发生丢失更新的问题。如果两个事务同时执行，则其中一个的修改可能会丢失，因为第二个写入的内容并没有包括第一个事务的修改

  • 增加计数器或更新账户余额（需要读取当前值，计算新值并写回更新后的值）

  • 将本地修改写入一个复杂值中：例如，将元素添加到 JSON 文档中的一个列表（需要解析文档，进行更改并写回修改的文档）

  • 两个用户同时编辑 wiki 页面，每个用户通过将整个页面内容发送到服务器来保存其更改，覆写数据库中当前的任何内容。

原子写

许多数据库提供了原子更新操作，从而消除了在应用程序代码中执行读取 - 修改 - 写入序列的需要。如果你的代码可以用这些操作来表达，那这通常是最好的解决方案。例如，下面的指令在大多数关系数据库中是并发安全的：

UPDATE counters SET value = value + 1 WHERE key = 'foo';

类似地，像 MongoDB 这样的文档数据库提供了对 JSON 文档的一部分进行本地修改的原子操作，Redis 提供了修改数据结构（如优先级队列）的原子操作。

原子操作通常通过在读取对象时，获取其上的排它锁来实现。以便更新完成之前没有其他事务可以读取它。这种技术有时被称为 游标稳定性（cursor stability）。另一个选择是简单地强制所有的原子操作在单一线程上执行。

显式锁定

让应用程序显式地锁定将要更新的对象。然后应用程序可以执行读取 - 修改 - 写入序列，如果任何其他事务尝试同时读取同一个对象，则强制等待，直到第一个 读取 - 修改 - 写入序列 完成。

例如，考虑一个多人游戏，其中几个玩家可以同时移动相同的棋子。在这种情况下，一个原子操作可能是不够的，因为应用程序还需要确保玩家的移动符合游戏规则，这可能涉及到一些不能合理地用数据库查询实现的逻辑。但你可以使用锁来防止两名玩家同时移动相同的棋子。

BEGIN TRANSACTION;
SELECT * FROM figures
  WHERE name = 'robot' AND game_id = 222
FOR UPDATE;

-- 检查玩家的操作是否有效，然后更新先前 SELECT 返回棋子的位置。
UPDATE figures SET position = 'c4' WHERE id = 1234;
COMMIT;

  • FOR UPDATE 子句告诉数据库应该对该查询返回的所有行加锁。

自动检测丢失的更新

原子操作和锁是通过强制 读取 - 修改 - 写入序列 按顺序发生，来防止丢失更新的方法。另一种方法是允许它们并行执行，如果事务管理器检测到丢失更新，则中止事务并强制它们重试其 读取 - 修改 - 写入序列。

PostgreSQL 的可重复读，Oracle 的可串行化和 SQL Server 的快照隔离级别，都会自动检测到丢失更新，并中止惹麻烦的事务。但是，MySQL/InnoDB 的可重复读并不会检测 丢失更新。一些作者认为，数据库必须能防止丢失更新才称得上是提供了 快照隔离，所以在这个定义下，MySQL 下不提供快照隔离。

比较并设置（CAS）

只有当前值从上次读取时一直未改变，才允许更新发生。如果当前值与先前读取的值不匹配，则更新不起作用，且必须重试读取 - 修改 - 写入序列。

例如，为了防止两个用户同时更新同一个 wiki 页面，可以尝试类似这样的方式，只有当用户开始编辑后页面内容未发生改变时，才会更新成功：

-- 根据数据库的实现情况，这可能安全也可能不安全
UPDATE wiki_pages SET content = '新内容'
  WHERE id = 1234 AND content = '旧内容';

如果内容已经更改并且不再与 “旧内容” 相匹配，则此更新将不起作用，因此你需要检查更新是否生效，必要时重试。但是，如果数据库允许 WHERE 子句从旧快照中读取，则此语句可能无法防止丢失更新，因为即使发生了另一个并发写入，WHERE 条件也可能为真。在依赖数据库的 CAS 操作前要检查其是否安全。

冲突解决和复制

锁和 CAS 操作假定只有一个最新的数据副本。但是多主或无主复制的数据库通常允许多个写入并发执行，并异步复制到副本上，因此无法保证只有一个最新数据的副本。所以基于锁或 CAS 操作的技术不适用于这种情况。

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

原子操作可以在复制的上下文中很好地工作，尤其当它们具有可交换性时（即，可以在不同的副本上以不同的顺序应用它们，且仍然可以得到相同的结果）。例如，递增计数器或向集合添加元素是可交换的操作。

写入偏差与幻读

医院通常会同时要求几位医生待命，但底线是至少有一位医生在待命。在两个事务中，应用首先检查是否有两个或以上的医生正在值班；如果是的话，它就假定一名医生可以安全地休班。由于数据库使用快照隔离，两次检查都返回 2 ，所以两个事务都进入下一个阶段。Alice 更新自己的记录休班了，而 Bob 也做了一样的事情。两个事务都成功提交了，现在没有医生值班了。违反了至少有一名医生在值班的要求。

写入偏差的特征

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

对于写入偏差，我们的选择更受限制：

  • 由于涉及多个对象，单对象的原子操作不起作用。

  • 在一些快照隔离的实现中，自动检测丢失更新对此并没有帮助。

  • 某些数据库允许配置约束，然后由数据库强制执行（例如，唯一性，外键约束或特定值限制）。但是为了指定至少有一名医生必须在线，需要一个涉及多个对象的约束。大多数数据库没有内置对这种约束的支持，但是你可以使用触发器，或者物化视图来实现它们，这取决于不同的数据库。

  • 如果无法使用可串行化的隔离级别，则此情况下的次优选项可能是显式锁定事务所依赖的行。在例子中，你可以写下如下的代码：

BEGIN TRANSACTION;
SELECT * FROM doctors
  WHERE on_call = TRUE
  AND shift_id = 1234 FOR UPDATE;

UPDATE doctors
  SET on_call = FALSE
  WHERE name = 'Alice'
  AND shift_id = 1234;
  
COMMIT;

  • 和以前一样，FOR UPDATE 告诉数据库锁定返回的所有行以用于更新。

写入偏差的更多例子

  • 会议室预订系统

    比如你想要规定不能在同一时间对同一个会议室进行多次的预订。当有人想要预订时，首先检查是否存在相互冲突的预订（即预订时间范围重叠的同一房间），如果没有找到，则创建会议。

    BEGIN TRANSACTION;

-- 检查所有现存的与 12:00~13:00 重叠的预定
SELECT COUNT(*) FROM bookings
WHERE room_id = 123 AND
  end_time > '2015-01-01 12:00' AND start_time < '2015-01-01 13:00';

-- 如果之前的查询返回 0
INSERT INTO bookings(room_id, start_time, end_time, user_id)
  VALUES (123, '2015-01-01 12:00', '2015-01-01 13:00', 666);

COMMIT;

    不幸的是，快照隔离并不能防止另一个用户同时插入冲突的会议。为了确保不会遇到调度冲突，你又需要可串行化的隔离级别了。

  • 多人游戏

    我们使用一个锁来防止丢失更新（也就是确保两个玩家不能同时移动同一个棋子）。但是锁定并不妨碍玩家将两个不同的棋子移动到棋盘上的相同位置，或者采取其他违反游戏规则的行为。取决于你正在执行的规则类型，也许可以使用唯一约束（unique constraint），否则你很容易发生写入偏差。

  • 抢注用户名

    在每个用户拥有唯一用户名的网站上，两个用户可能会尝试同时创建具有相同用户名的帐户。可以在事务检查名称是否被抢占，如果没有则使用该名称创建账户。但是像在前面的例子中那样，在快照隔离下这是不安全的。幸运的是，唯一约束是一个简单的解决办法（第二个事务在提交时会因为违反用户名唯一约束而被中止）。

  • 防止双重开支

    允许用户花钱或使用积分的服务，需要检查用户的支付数额不超过其余额。可以通过在用户的帐户中插入一个试探性的消费项目来实现这一点，列出帐户中的所有项目，并检查总和是否为正值。在写入偏差场景下，可能会发生两个支出项目同时插入，一起导致余额变为负值，但这两个事务都不会注意到另一个。

导致写入偏差的幻读

所有这些例子都遵循类似的模式：

  1. 一个 SELECT 查询找出符合条件的行，并检查是否符合一些要求。（例如：至少有两名医生在值班；不存在对该会议室同一时段的预定；棋盘上的位置没有被其他棋子占据；用户名还没有被抢注；账户里还有足够余额）

  2. 按照第一个查询的结果，应用代码决定是否继续。（可能会继续操作，也可能中止并报错）

  3. 如果应用决定继续操作，就执行写入（插入、更新或删除），并提交事务。

    这个写入的效果改变了步骤 2 中的先决条件。换句话说，如果在提交写入后，重复执行一次步骤 1 的 SELECT 查询，将会得到不同的结果。因为写入改变了符合搜索条件的行集（现在少了一个医生值班，那时候的会议室现在已经被预订了，棋盘上的这个位置已经被占据了，用户名已经被抢注，账户余额不够了）。

这些步骤可能以不同的顺序发生。例如可以首先进行写入，然后进行 SELECT 查询，最后根据查询结果决定是放弃还是提交。

在医生值班的例子中，在步骤 3 中修改的行，是步骤 1 中返回的行之一，所以我们可以通过锁定步骤 1 中的行（SELECT FOR UPDATE）来使事务安全并避免写入偏差。但是其他四个例子是不同的：它们检查是否 不存在 某些满足条件的行，写入会 添加 一个匹配相同条件的行。如果步骤 1 中的查询没有返回任何行，则 SELECT FOR UPDATE 锁不了任何东西。

这种效应：一个事务中的写入改变另一个事务的搜索查询的结果，被称为 幻读。快照隔离避免了只读查询中幻读，但是在像我们讨论的例子那样的读写事务中，幻读会导致特别棘手的写入偏差情况。

物化冲突

如果幻读的问题是没有对象可以加锁，也许可以人为地在数据库中引入一个锁对象

例如，在会议室预订的场景中，可以想象创建一个关于时间槽和房间的表。此表中的每一行对应于特定时间段（例如 15 分钟）的特定房间。可以提前插入房间和时间的所有可能组合行（例如接下来的六个月）。

现在，要创建预订的事务可以锁定（SELECT FOR UPDATE）表中与所需房间和时间段对应的行。在获得锁定之后，它可以检查重叠的预订并像以前一样插入新的预订。请注意，这个表并不是用来存储预订相关的信息 —— 它完全就是一组锁，用于防止同时修改同一房间和时间范围内的预订。

这种方法被称为 物化冲突（materializing conflicts），因为它将幻读变为数据库中一组具体行上的锁冲突。不幸的是，弄清楚如何物化冲突可能很难，也很容易出错，并且让并发控制机制泄漏到应用数据模型是很丑陋的做法。出于这些原因，如果没有其他办法可以实现，物化冲突应被视为最后的手段。在大多数情况下。可串行化（Serializable） 的隔离级别是更可取的。

可串行化

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

真的串行执行

数据库设计人员只是在 2007 年左右才决定，单线程循环执行事务是可行的。

两个进展引发了这个反思：

  • RAM 足够便宜了，许多场景现在都可以将完整的活跃数据集保存在内存中。当事务需要访问的所有数据都在内存中时，事务处理的执行速度要比等待数据从磁盘加载时快得多。

  • 数据库设计人员意识到 OLTP 事务通常很短，而且只进行少量的读写操作。相比之下，长时间运行的分析查询通常是只读的，因此它们可以在串行执行循环之外的一致快照（使用快照隔离）上运行。

串行执行事务的方法在 VoltDB/H-Store，Redis 和 Datomic 中实现。设计用于单线程执行的系统有时可以比支持并发的系统性能更好，因为它可以避免锁的协调开销。但是其吞吐量仅限于单个 CPU 核的吞吐量。为了充分利用单一线程，需要与传统形式的事务不同的结构。

在存储过程恭封装事务

交互式的事务方式中，应用程序和数据库之间的网络通信耗费了大量的时间。如果不允许在数据库中进行并发处理，且一次只处理一个事务，则吞吐量将会非常糟糕，因为数据库大部分的时间都花费在等待应用程序发出当前事务的下一个查询。在这种数据库中，为了获得合理的性能，需要同时处理多个事务。

出于这个原因，具有单线程串行事务处理的系统不允许交互式的多语句事务。取而代之，应用程序必须提前将整个事务代码作为存储过程提交给数据库。如果事务所需的所有数据都在内存中，则存储过程可以非常快地执行，而不用等待任何网络或磁盘 I/O。

存储过程的优点和缺点

存储过程在关系型数据库中已经存在了一段时间了，自 1999 年以来它们一直是 SQL 标准（SQL/PSM）的一部分。出于各种原因，它们的名声有点不太好。

  • 在数据库中运行的代码难以管理：与应用服务器相比，它更难调试，更难以保持版本控制和部署，更难测试，并且难以集成到指标收集系统来进行监控。

  • 数据库通常比应用服务器对性能敏感的多，因为单个数据库实例通常由许多应用服务器共享。数据库中一个写得不好的存储过程（例如，占用大量内存或 CPU 时间）会比在应用服务器中相同的代码造成更多的麻烦。

现代的存储过程实现放弃了 PL/SQL，而是使用现有的通用编程语言：VoltDB 使用 Java 或 Groovy，Datomic 使用 Java 或 Clojure，而 Redis 使用 Lua。

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

分区

对于写入吞吐量较高的应用，单线程事务处理器可能成为一个严重的瓶颈。

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

但是，对于需要访问多个分区的任何事务，数据库必须在触及的所有分区之间协调事务。存储过程需要跨越所有分区锁定执行，以确保整个系统的可串行性。由于跨分区事务具有额外的协调开销，所以它们比单分区事务慢得多，并且不能通过增加更多的机器来增加吞吐量。

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

串行执行小结

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

  • 每个事务都必须小而快，只要有一个缓慢的事务，就会拖慢所有事务处理。

  • 仅限于活跃数据集可以放入内存的情况。很少访问的数据可能会被移动到磁盘，但如果需要在单线程执行的事务中访问，系统就会变得非常慢。

  • 写入吞吐量必须低到能在单个 CPU 核上处理，如若不然，事务需要能划分至单个分区，且不需要跨分区协调。

  • 跨分区事务是可能的，但是它们能被使用的程度有很大的限制。

两阶段锁定

请注意，虽然两阶段锁定（2PL）听起来非常类似于两阶段提交（2PC），但它们是完全不同的东西。

如果两个事务同时尝试写入同一个对象，则锁可确保第二个写入必须等到第一个写入完成事务（中止或提交），然后才能继续。两阶段锁定类似，但是锁的要求更强得多。只要没有写入，就允许多个事务同时读取同一个对象。但对象只要有写入（修改或删除），就需要 独占访问（exclusive access） 权限：

  • 如果事务 A 读取了一个对象，并且事务 B 想要写入该对象，那么 B 必须等到 A 提交或中止才能继续。

  • 如果事务 A 写入了一个对象，并且事务 B 想要读取该对象，则 B 必须等到 A 提交或中止才能继续。

在 2PL 中，写入不仅会阻塞其他写入，也会阻塞读，反之亦然。快照隔离使得 读不阻塞写，写也不阻塞读。

实现两阶段锁

2PL 用于 MySQL（InnoDB）和 SQL Server 中的可串行化隔离级别，以及 DB2 中的可重复读隔离级别。

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

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

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

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

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

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

两阶段锁定的性能

当一个事务需要等待另一个事务时，等待的时长并没有限制。即使你保证所有的事务都很短，如果有多个事务想要访问同一个对象，那么可能会形成一个队列，所以事务可能需要等待几个其他事务才能完成。

因此，运行 2PL 的数据库可能具有相当不稳定的延迟，可能只需要一个缓慢的事务，或者一个访问大量数据并获取许多锁的事务，就能把系统的其他部分拖慢，甚至迫使系统停机。

谓词锁

在会议室预订的例子中，这意味着如果一个事务在某个时间窗口内搜索了一个房间的现有预订，则另一个事务不能同时插入或更新同一时间窗口与同一房间的另一个预订 （可以同时插入其他房间的预订，或在不影响另一个预定的条件下预定同一房间的其他时间段）。

从概念上讲，我们需要一个 谓词锁（predicate lock）。它类似于前面描述的共享 / 排它锁，但不属于特定的对象（例如，表中的一行），它属于所有符合某些搜索条件的对象，如：

SELECT * FROM bookings
WHERE room_id = 123 AND
      end_time > '2018-01-01 12:00' AND
      start_time < '2018-01-01 13:00';

谓词锁限制访问，如下所示：

  • 如果事务 A 想要读取匹配某些条件的对象，它必须获取查询条件上的 共享谓词锁（shared-mode predicate lock）。如果另一个事务 B 持有任何满足这一查询条件对象的排它锁，那么 A 必须等到 B 释放它的锁之后才允许进行查询。

  • 如果事务 A 想要插入，更新或删除任何对象，则必须首先检查旧值或新值是否与任何现有的谓词锁匹配。如果事务 B 持有匹配的谓词锁，那么 A 必须等到 B 已经提交或中止后才能继续。

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

索引范围锁

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

通过使谓词匹配到一个更大的集合来简化谓词锁是安全的。例如，如果你有在中午和下午 1 点之间预订 123 号房间的谓词锁，则锁定 123 号房间的所有时间段是安全的近似，因为任何满足原始谓词的写入也一定会满足这种更松散的近似。

在房间预订数据库中，你可能会在 room_id 列上有一个索引，并且 / 或者在 start_time 和 end_time 上有索引（否则前面的查询在大型数据库上的速度会非常慢）：

  • 假设你的索引位于 room_id 上，并且数据库使用此索引查找 123 号房间的现有预订。现在数据库可以简单地将共享锁附加到这个索引项上，指示事务已搜索 123 号房间用于预订。

  • 或者，如果数据库使用基于时间的索引来查找现有预订，那么它可以将共享锁附加到该索引中的一系列值，指示事务已经将 12:00~13:00 时间段标记为用于预定。

无论哪种方式，搜索条件的近似值都附加到其中一个索引上。现在，如果另一个事务想要插入、更新或删除同一个房间和 / 或重叠时间段的预订，则它将不得不更新索引的相同部分。在这样做的过程中，它会遇到共享锁，它将被迫等到锁被释放。

这种方法能够有效防止幻读和写入偏差。索引范围锁并不像谓词锁那样精确，但是由于它们的开销较低，所以是一个很好的折衷。

如果没有可以挂载范围锁的索引，数据库可以退化到使用整个表上的共享锁。这对性能不利，因为它会阻止所有其他事务写入表格。

可串行化快照隔离

串行化的隔离级别和高性能是从根本上相互矛盾的吗？

也许不是：一个称为 可串行化快照隔离（SSI, serializable snapshot isolation） 的算法是非常有前途的。它提供了完整的可串行化隔离级别，但与快照隔离相比只有很小的性能损失。

悲观与乐观的并发控制

两阶段锁是一种所谓的 悲观并发控制机制（pessimistic） ：它是基于这样的原则：如果有事情可能出错（如另一个事务所持有的锁所表示的），最好等到情况安全后再做任何事情。

相比之下，串行化快照隔离 是一种 乐观（optimistic） 的并发控制技术。当一个事务想要提交时，数据库检查是否有什么不好的事情发生（即隔离是否被违反）；如果是的话，事务将被中止，并且必须重试。只有可串行化的事务才被允许提交。

乐观并发控制是一个古老的想法，其优点和缺点已经争论了很长时间。如果存在很多 争用（contention，即很多事务试图访问相同的对象），则表现不佳，因为这会导致很大一部分事务需要中止。如果系统已经接近最大吞吐量，来自重试事务的额外负载可能会使性能变差。

但是，如果有足够的空闲容量，并且事务之间的争用不是太高，乐观的并发控制技术往往比悲观的性能要好。

顾名思义，SSI 基于快照隔离 —— 也就是说，事务中的所有读取都是来自数据库的一致性快照。与早期的乐观并发控制技术相比这是主要的区别。在快照隔离的基础上，SSI 添加了一种算法来检测写入之间的串行化冲突，并确定要中止哪些事务。

基于过时前提的决策

在快照隔离的情况下，原始查询的结果在事务提交时可能不再是最新的，因为数据可能在同一时间被修改。

换句话说，事务基于一个 前提（premise） 采取行动。之后当事务要提交时，原始数据可能已经改变 —— 前提可能不再成立。

当应用程序进行查询时，数据库不知道应用逻辑如何使用该查询结果。在这种情况下为了安全，数据库需要假设任何对该结果集的变更都可能会使该事务中的写入变得无效。 换而言之，事务中的查询与写入可能存在因果依赖。为了提供可串行化的隔离级别，如果事务在过时的前提下执行操作，数据库必须能检测到这种情况，并中止事务。

数据库如何知道查询结果是否可能已经改变？有两种情况需要考虑：

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

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

检测旧 MVCC 读取

数据库需要跟踪一个事务由于 MVCC 可见性规则而忽略另一个事务的写入。当事务想要提交时，数据库检查是否有任何被忽略的写入现在已经被提交。如果是这样，事务必须中止。

为什么要等到提交？当检测到陈旧的读取时，为什么不立即中止事务？因为如果是只读事务，则不需要中止，因为没有写入偏差的风险。当事务进行读取时，数据库还不知道事务是否要稍后执行写操作。此外，事务可能在其他事务被提交的时候中止或者可能仍然未被提交，因此读取可能终究不是陈旧的。通过避免不必要的中止，SSI 保留了快照隔离从一致快照中长时间读取的能力。

检测影响之前读取的写入

第二种情况要考虑的是另一个事务在读取数据之后修改数据。

![[Pasted image 20240314203809.png]]

事务 42 和 43 都在班次 1234 查找值班医生。如果在 shift_id 上有索引，则数据库可以使用索引项 1234 来记录事务 42 和 43 读取这个数据的事实。（如果没有索引，这个信息可以在表级别进行跟踪）。这个信息只需要保留一段时间：在一个事务完成（提交或中止），并且所有的并发事务完成之后，数据库就可以忘记它读取的数据了。

当事务写入数据库时，它必须在索引中查找最近曾读取受影响数据的其他事务。这个过程类似于在受影响的键范围上获取写锁，但锁并不会阻塞事务直到其他读事务完成，而是像警戒线一样只是简单通知其他事务：你们读过的数据可能不是最新的啦。

事务 43 通知事务 42 其先前读已过时，反之亦然。事务 42 首先提交并成功，尽管事务 43 的写影响了 42 ，但因为事务 43 尚未提交，所以写入尚未生效。然而当事务 43 想要提交时，来自事务 42 的冲突写入已经被提交，所以事务 43 必须中止。

可串行化快照隔离的性能

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

中止率显著影响 SSI 的整体表现。例如，长时间读取和写入数据的事务很可能会发生冲突并中止，因此 SSI 要求同时读写的事务尽量短（只读的长事务可能没问题）。对于慢事务，SSI 可能比两阶段锁定或串行执行更不敏感。

Previous分布式系统典型实例Next二分查找

Last updated