开源应用架构（第一卷）
NoSQL 生态系统

13.1.1. SQL 和关系模型

SQL 是一种用于查询数据的声明性语言。声明性语言是指程序员指定他们希望系统做什么，而不是以过程方式定义系统如何执行的语言。一些示例包括：查找员工 39 的记录，仅从其完整记录中输出员工姓名和电话号码，将员工记录过滤为在会计部门工作的员工，计算每个部门的员工人数，或将员工表中的数据与经理表中的数据联接起来。

大体上说，SQL 允许您提出这些问题，而无需考虑数据在磁盘上的布局方式、使用哪些索引来访问数据，或使用哪些算法来处理数据。大多数关系数据库的一个重要架构组件是查询优化器，它决定执行众多逻辑等效查询计划中的哪个计划，以便最快速地回答查询。这些优化器通常比普通数据库用户更好，但有时它们没有足够的知识或对系统的模型过于简单，无法生成最有效的执行。

关系数据库是实践中最常见的数据库，它们遵循关系数据模型。在这个模型中，不同的现实世界实体存储在不同的表中。例如，所有员工都可能存储在员工表中，而所有部门都可能存储在部门表中。表的每一行都有存储在列中的各种属性。例如，员工可能具有员工 ID、薪资、出生日期以及姓名。这些属性中的每一个都将存储在员工表的列中。

关系模型与 SQL 紧密相连。简单的 SQL 查询，如过滤器，检索所有其字段与某个测试匹配的记录（例如，employeeid = 3 或 salary > $20000）。更复杂的构造会导致数据库做一些额外的工作，例如联接来自多个表的数据（例如，员工 3 所在部门的名称是什么？）。其他复杂构造，如聚合（例如，我所有员工的平均薪资是多少？），可能导致全表扫描。

关系数据模型定义了高度结构化的实体，它们之间存在严格的关系。用 SQL 查询这个模型允许复杂的跨数据遍历，而无需太多自定义开发。然而，这种建模和查询的复杂性也有其局限性。

• 复杂性导致不可预测性。SQL 的表达能力使得难以推断每个查询的成本，从而推断工作负载的成本。虽然更简单的查询语言可能会使应用程序逻辑变得复杂，但它们使提供数据存储系统变得更容易，这些系统只响应简单的请求。
• 有许多方法可以对问题进行建模。关系数据模型很严格：分配给每个表的模式指定每行中的数据。如果我们存储的是结构较少的数据，或者行中存储的列存在更多差异，那么关系模型可能会过分限制。同样，应用程序开发人员可能不会发现关系模型适合对每种类型的数据进行建模。例如，很多应用程序逻辑是用面向对象的语言编写的，并且包含高级概念，如列表、队列和集合，一些程序员希望他们的持久层对这些进行建模。
• 如果数据超出单个服务器的容量，那么数据库中的表将不得不被划分为多个计算机。为了避免 JOIN 需要跨网络获取不同表中的数据，我们将不得不对其进行反规范化。反规范化将来自不同表的所有数据存储在同一个地方，这样人们就可以一次性查看这些数据。这使得我们的数据库看起来像一个键查找存储系统，让我们不禁想知道还有哪些其他数据模型可能更适合这些数据。

随意丢弃多年的设计考虑通常是不明智的。当您考虑将数据存储在数据库中时，请考虑 SQL 和关系模型，它们经过数十年的研究和开发，提供了丰富的建模功能，并提供对复杂操作易于理解的保证。当您遇到特定的问题时，例如大量数据、庞大的工作负载或 SQL 和关系数据库可能没有针对其进行优化的困难数据建模决策，NoSQL 是一个不错的选择。

13.1.2. NoSQL 灵感

NoSQL 运动从研究界的大量论文中汲取了灵感。虽然许多论文是 NoSQL 系统设计决策的核心，但有两篇论文特别突出。

Google 的 BigTable [CDG+06] 展示了一个有趣的数据模型，它可以方便地对多列历史数据进行排序存储。数据使用基于范围的分层分区方案分布到多个服务器，并且数据更新使用严格一致性（我们将在13.5 节中定义的概念）。

亚马逊的 Dynamo [DHJ+07] 使用了不同的键导向分布式数据存储。Dynamo 的数据模型更简单，将键映射到应用程序特定的数据块。分区模型更能抵抗故障，但通过一种称为最终一致性的较松散的数据一致性方法来实现这一目标。

我们将更详细地探讨这些概念中的每一个，但重要的是要理解，它们中的许多可以混合搭配。一些 NoSQL 系统，如 HBase¹，严格遵循 BigTable 的设计。另一个名为 Voldemort² 的 NoSQL 系统复制了 Dynamo 的许多功能。其他 NoSQL 项目，如 Cassandra³，从 BigTable（其数据模型）和 Dynamo（其分区和一致性方案）中借鉴了一些功能。

13.1.3. 特征和考虑因素

NoSQL 系统与庞大的 SQL 标准背道而驰，并为构建存储解决方案提供更简单但零散的解决方案。这些系统是在这样的信念下构建的：通过简化数据库在数据上的操作方式，架构师可以更好地预测查询的性能。在许多 NoSQL 系统中，复杂的查询逻辑留给应用程序处理，从而导致数据存储具有更可预测的查询性能，因为查询的缺乏变化性。

NoSQL 系统不仅与关系数据上的声明性查询背道而驰。事务语义、一致性和持久性是银行等组织对数据库的要求。事务在将多个可能复杂的运算组合成一个运算时，提供了一种全有或全无的保证，例如，从一个账户中扣款并将钱存入另一个账户。一致性确保当值更新时，后续查询将看到更新后的值。持久性保证一旦值更新，它将被写入稳定存储（如硬盘驱动器）中，并在数据库崩溃时可恢复。

NoSQL 系统放宽了其中一些保证，对于许多非银行应用程序来说，这是一个可以接受的决策，它可以换取更高的性能，并提供可预测的行为。这些放宽以及数据模型和查询语言的更改，通常使得在数据超出单个机器的能力时，更容易地将数据库安全地划分为多个机器。

NoSQL 系统仍然处于起步阶段。本章描述的系统中的架构决策证明了各种用户的需求。总结多个开源项目的架构特征的最大挑战在于，每个项目都是一个不断变化的目标。请记住，单个系统的细节将发生变化。当您在 NoSQL 系统之间选择时，您可以使用本章来指导您的思考过程，而不是指导您进行功能对功能的产品选择。

当您考虑 NoSQL 系统时，这里提供了一个考虑因素路线图。

• 数据和查询模型：您的数据是以行、对象、数据结构还是文档的形式表示的？您可以要求数据库计算跨多个记录的聚合吗？
• 持久性：当您更改值时，它是否立即写入稳定存储？它是否存储在多台机器上，以防一台机器发生故障？
• 可扩展性：您的数据是否适合存储在单个服务器上？读写量是否需要多个磁盘来处理工作负载？
• 分区：出于可扩展性、可用性或持久性方面的考虑，数据是否需要存储在多台服务器上？您如何知道哪条记录位于哪台服务器上？
• 一致性：如果您已将记录划分为多台服务器并进行复制，那么当记录更改时，这些服务器如何协调？
• 事务语义：当您运行一系列操作时，一些数据库允许您将它们包装在一个事务中，该事务对事务和当前运行的所有其他事务提供 ACID（原子性、一致性、隔离性和持久性）保证的某个子集。您的业务逻辑是否需要这些保证，这些保证通常会带来性能权衡？
• 单服务器性能：如果您想将数据安全地存储在磁盘上，那么哪些磁盘上数据结构最适合读密集型或写密集型工作负载？写磁盘是您的瓶颈吗？
• 分析工作负载：我们将重点关注查找密集型工作负载，这类工作负载是运行响应式用户关注的 Web 应用程序所需的。在许多情况下，您可能希望构建数据集大小的报告，例如，汇总多个用户的统计信息。您的用例和工具链是否需要此类功能？

虽然我们将涉及所有这些考虑因素，但本章对最后三个考虑因素的关注度最低，尽管它们同样重要。

13.2.1. 基于键的 NoSQL 数据模型

NoSQL 系统通常会放弃关系模型和 SQL 的全部表达能力，而是将数据集上的查找限制在单个字段上。例如，即使员工有许多属性，您也可能只能通过她的 ID 来检索员工。因此，NoSQL 系统中的大多数查询都是基于键值查找的。程序员选择一个键来标识每个数据项，并且在大多数情况下，只能通过在数据库中执行其键的查找来检索项。

在基于键值查找的系统中，复杂的联接操作或同一数据的多个键检索可能需要对键名称进行创造性的使用。一个希望通过员工 ID 查找员工并查找部门中所有员工的程序员可能会创建两种键类型。例如，键employee:30将指向员工 ID 为 30 的员工记录，employee_departments:20可能包含部门 20 中所有员工的列表。联接操作被推送到应用程序逻辑中：要检索部门 20 中的员工，应用程序首先从键employee_departments:20中检索一个员工 ID 列表，然后循环遍历每个employee:ID的键值查找在员工列表中。

键值查找模型是有益的，因为它意味着数据库具有一致的查询模式——整个工作负载由键值查找组成，这些键值查找的性能相对一致且可预测。分析以找到应用程序的慢速部分变得更加简单，因为所有复杂的操作都驻留在应用程序代码中。另一方面，数据模型逻辑和业务逻辑现在更加紧密地交织在一起，这会使抽象变得模糊。

让我们快速了解与每个键关联的数据。各种 NoSQL 系统为此提供了不同的解决方案。

13.2.2. 图存储

一类 NoSQL 存储是图存储。并非所有数据都是天生平等的，关系和键值数据模型存储和查询数据的模型并非适合所有数据。图是计算机科学中一种基本的数据结构，诸如 HyperGraphDB¹² 和 Neo4J¹³ 等系统是两个流行的 NoSQL 存储系统，用于存储图结构化数据。图存储在几乎所有方面都不同于我们迄今为止讨论过的其他存储：数据模型、数据遍历和查询模式、数据在磁盘上的物理布局、跨多个机器的分布以及查询的事务语义。由于空间限制，我们无法对这些明显的差异做出公平的阐述，但您应该意识到某些类别的数据可能更适合作为图进行存储和查询。

13.2.3. 复杂查询

在 NoSQL 系统中，仅基于键的查找有明显的例外。MongoDB 允许您根据任意数量的属性索引您的数据，并具有相对高级的语言来指定要检索的数据。基于 BigTable 的系统支持扫描程序来遍历列族并通过对列的过滤器选择特定项。CouchDB 允许您创建数据的不同视图，并运行跨表的 MapReduce 任务，以促进更复杂的查找和更新。大多数系统都绑定到 Hadoop 或其他 MapReduce 框架，以执行数据集规模的分析查询。

13.2.4. 事务

NoSQL 系统通常将性能置于事务语义之上。其他基于 SQL 的系统允许任何语句集——从简单的主键行检索到多个表的复杂联接，然后随后在多个字段上进行平均——放入事务中。

这些 SQL 数据库将为事务提供 ACID 保证。在事务中运行多个操作是原子性的 (ACID 中的 A)，这意味着所有操作都会发生或都不发生。一致性 (C) 确保事务将数据库置于一致的、未损坏的状态。隔离 (I) 确保如果两个事务触及同一记录，它们将不会相互影响。持久性 (D，将在下一节中广泛介绍) 确保一旦事务提交，它就会存储在安全的地方。

符合 ACID 的事务通过使开发人员能够轻松地推断其数据的状态，从而保持开发人员的理智。想象多个事务，每个事务都有多个步骤（例如，首先检查银行账户的值，然后减去 60 美元，然后更新该值）。符合 ACID 的数据库在如何交织这些步骤方面往往受到限制，同时仍然为所有事务提供正确的结果。这种对正确性的推动会导致通常意想不到的性能特征，其中缓慢的事务可能会导致其他快速的事务排队等待。

大多数 NoSQL 系统将性能置于完整的 ACID 保证之上，但确实在键级别提供了保证：对同一键的两个操作将被序列化，避免对键值对造成严重损坏。对于许多应用程序来说，此决定不会造成明显的正确性问题，并且将允许快速操作更规律地执行。但是，它确实将更多关于应用程序设计和正确性的考虑因素留给了开发人员。

Redis 是无事务趋势中值得注意的例外。在一个服务器上，它提供了一个MULTI命令以原子地且一致地组合多个操作，以及一个WATCH命令以允许隔离。其他系统提供更低级的测试和设置功能，该功能提供了一些隔离保证。

13.2.5. 无模式存储

许多 NoSQL 系统的交叉属性是数据库中缺乏模式强制。即使在文档存储和面向列族的存储中，也不需要类似实体的属性相同。这具有支持结构较少的数据需求以及在动态修改模式时需要更少性能开销的优势。此决定将更多责任留给了应用程序开发人员，他们现在必须更加防御性地进行编程。例如，员工记录上缺少lastname属性是需要纠正的错误，还是目前正在通过系统传播的模式更新？在依赖松散模式 NoSQL 系统的项目经过几次迭代之后，数据和模式版本控制在应用程序级代码中很常见。

13.3.1. 单服务器持久性

最简单的持久性形式是单服务器持久性，它确保任何数据修改都能在服务器重启或断电后存活。这通常意味着将更改后的数据写入磁盘，这通常会成为工作负载的瓶颈。即使您指示操作系统将数据写入磁盘文件，操作系统也可能会缓冲写入，避免立即修改磁盘，以便可以将多个写入组合到单个操作中。只有在发出fsync系统调用时，操作系统才会尽力确保将缓冲的更新持久保存到磁盘。

典型的硬盘驱动器每秒可以执行 100-200 次随机访问（查找），并且每次顺序写入的限制为 30-100 MB/秒。在两种情况下，内存的速度都可以快几个数量级。确保高效的单服务器持久性意味着限制系统产生的随机写入次数，并增加每个硬盘驱动器的顺序写入次数。理想情况下，您希望系统最大程度地减少fsync调用之间的写入次数，最大限度地增加这些写入中的顺序写入次数，同时在写入被fsync之前永远不要告诉用户他们的数据已成功写入磁盘。让我们来了解一些提高单服务器持久性保证性能的技术。

13.3.2. 多服务器持久性

由于硬盘驱动器和机器经常会发生不可修复的故障，因此跨机器复制重要数据是必要的。许多 NoSQL 系统为数据提供多服务器持久性。

Redis 采用传统的“主从”方法来复制数据。对主服务器执行的所有操作都以类似日志的方式传达给从服务器，这些服务器在自己的硬件上复制操作。如果主服务器出现故障，从服务器可以接管并从从主服务器接收的操作日志状态提供数据。这种配置可能会导致一些数据丢失，因为主服务器不会确认从服务器在其日志中持久保存操作，然后再向用户确认操作。CouchDB 促进了类似的定向复制形式，其中可以配置服务器来将对其他存储上的文档的更改进行复制。

MongoDB 提供了副本集的概念，其中一定数量的服务器负责存储每个文档。MongoDB 为开发人员提供了确保所有副本都已收到更新，或者在不确保副本拥有最新数据的情况下继续操作的选择。许多其他分布式 NoSQL 存储系统支持数据的多服务器复制。HBase 构建在 HDFS 之上，通过 HDFS 接收多服务器持久性。所有写入都会在返回控制权给用户之前复制到两个或多个 HDFS 节点，从而确保多服务器持久性。

Riak、Cassandra 和 Voldemort 支持更可配置的复制形式。这三个系统都以微妙的不同方式允许用户指定N（最终应该拥有数据副本的机器数量）和W<N（在返回控制权给用户之前应该确认数据已写入的机器数量）。

为了处理整个数据中心无法访问的情况，需要跨数据中心进行多服务器复制。Cassandra、HBase 和 Voldemort 具有机架感知配置，这些配置指定了各种机器所在的机架或数据中心。通常，在远程服务器确认更新之前阻止用户的请求会造成过多的延迟。当跨广域网执行更新以备份数据中心时，更新会以流式传输方式进行，而无需确认。

13.4.1. 在必须之前不要分片

分片会增加系统复杂性，在可能的情况下，应避免分片。让我们了解两种无需分片即可进行扩展的方法：只读副本和缓存。

只读副本和缓存允许您扩展读密集型工作负载。但是，当您开始增加写入和更新数据的频率时，您也会增加包含所有最新数据的主服务器的负载。在本节的剩余部分，我们将介绍将写工作负载分散到多台服务器上的分片技术。

13.4.2. 通过协调器进行分片

CouchDB 项目专注于单服务器体验。Lounge 和 BigCouch 两个项目通过外部代理（充当独立 CouchDB 实例的前端）来促进 CouchDB 工作负载的分片。在此设计中，独立安装彼此之间并不了解。协调器根据请求的文档的键将请求分发到各个 CouchDB 实例。

Twitter 已将分片和复制的概念构建到一个名为 Gizzard¹⁶的协调框架中。Gizzard 采用任何类型的独立数据存储（您可以为 SQL 或 NoSQL 存储系统构建包装器），并将它们排列成任何深度的树，以根据键范围对键进行分区。为了实现容错性，可以配置 Gizzard 将数据复制到同一键范围内的多台物理机器上。

13.4.3. 一致哈希环

好的哈希函数以均匀的方式分布一组键。这使得它们成为在多个服务器之间分配键值对的有力工具。关于一种称为一致性哈希的技术的学术文献非常丰富，并且该技术在数据存储中的第一个应用是在称为分布式哈希表（DHT）的系统中。围绕亚马逊 Dynamo 原则构建的 NoSQL 系统采用了这种分布技术，并且它出现在 Cassandra、Voldemort 和 Riak 中。

哈希环示例

图 13.1：分布式哈希表环

一致性哈希环的工作原理如下。假设我们有一个哈希函数 H，它将键映射到均匀分布的大整数值。我们可以通过对某个相对较大的整数 L 取 H(key) mod L，形成一个在 [1, L] 范围内并围绕自身循环的数字环。这将把每个键映射到 [1,L] 范围内。一致性哈希服务器环是通过获取每个服务器的唯一标识符（例如其 IP 地址）并对其应用 H 来形成的。您可以通过查看由五个服务器 (A-E) 在 图 13.1 中形成的哈希环来直观地了解其工作原理。

在那里，我们选择了 L = 1000。假设 H(A) mod L = 7、H(B) mod L = 234、H(C) mod L = 447、H(D) mod L = 660 和 H(E) mod L = 875。我们现在可以判断哪个服务器应该存储一个键。为此，我们通过查看一个键的哈希值是否落在该服务器与环中的下一个服务器之间的范围内，将所有键映射到一个服务器。例如，A 负责哈希值落在 [7,233] 范围内的键，E 负责哈希值落在 [875, 6] 范围内的键（此范围在 1000 处围绕自身循环）。因此，如果 H('employee30') mod L = 899，它将存储在服务器 E 上，如果 H('employee31') mod L = 234，它将存储在服务器 B 上。

13.4.4. 范围分区

在范围分区方法中，系统中的某些机器会保存有关哪些服务器包含哪些键范围的元数据。查询此元数据以将键和范围查找路由到适当的服务器。与一致性哈希环方法一样，这种范围分区将键空间划分为范围，每个键范围由一台机器管理，并可能复制到其他机器。与一致性哈希方法不同的是，键排序中彼此相邻的两个键很可能出现在同一个分区中。这减少了路由元数据的规模，因为大的范围被压缩为 [开始，结束] 标记。

通过添加对范围到服务器映射的主动记录保存，范围分区方法允许更细粒度地控制负载从负载过重的服务器中分离。如果特定键范围的流量高于其他范围，负载管理器可以缩减该服务器上范围的大小，或者减少该服务器服务的碎片数量。主动管理负载的额外自由是以需要额外的体系结构组件为代价的，这些组件会监控和路由碎片。

BigTable 的方法

Google 的 BigTable 论文描述了一种将数据分片成数据块的范围分区分层技术。数据块存储一个列族内的一系列行键和值。它维护所有必要的日志和数据结构以回答有关其分配范围内键的查询。数据块服务器根据每个数据块所经历的负载来服务多个数据块。

每个数据块的大小保持在 100-200 MB。随着数据块大小的变化，两个具有相邻键范围的小数据块可能会合并，或者一个大数据块可能会拆分成两个。主服务器分析数据块大小、负载和数据块服务器可用性。主服务器随时调整哪个数据块服务器服务哪些数据块。

图 13.2：基于 BigTable 的范围分区

主服务器在元数据表中维护数据块分配。由于此元数据可能变得很大，因此元数据表也被分片成数据块，这些数据块将键范围映射到数据块和负责这些范围的数据块服务器。这导致客户端为找到其托管数据块服务器上的键而执行三层层次结构遍历，如 图 13.2 所示。

让我们来看一个例子。搜索键 900 的客户端将查询服务器 A，该服务器存储元数据级别 0 的数据块。此数据块识别服务器 6 上包含键范围 500-1500 的元数据级别 1 数据块。客户端使用此键向服务器 B 发送请求，该服务器响应包含键 850-950 的数据块在服务器 C 上的一个数据块上找到。最后，客户端将键请求发送到服务器 C，并获得其查询的行数据。客户端可能会缓存级别 0 和 1 的元数据数据块，从而避免由于重复查询而对它们的数据块服务器施加不必要的负载。BigTable 论文解释说，这种 3 层层次结构可以使用 128 MB 数据块容纳 2⁶¹ 字节的存储空间。

13.4.5. 使用哪种分区方案

考虑到基于哈希和范围的分片方法，哪种方法更可取？这取决于。当你经常对数据的键进行范围扫描时，范围分区是明显的选择。当按键顺序读取值时，你不会跳转到网络中的随机节点，这会导致严重的网络开销。但是，如果你不需要范围扫描，应该使用哪种分片方案？

哈希分区可以合理地将数据分布到各个节点，并且可以使用虚拟节点减少随机偏差。哈希分区方案中的路由很简单：在大多数情况下，客户端可以执行哈希函数以找到合适的服务器。使用更复杂重新平衡方案，找到键的正确节点变得更加困难。

范围分区需要维护路由和配置节点的预先成本，这些节点可能会看到繁重的负载，并且在没有相对复杂的容错方案的情况下成为中心故障点。但是，如果做得好的话，范围分区数据可以在小块中进行负载均衡，这些小块可以在高负载情况下重新分配。如果一台服务器宕机，其分配的范围可以分布到许多服务器，而不是在停机期间将服务器的直接邻居加载到服务器上。

13.5.1. 关于 CAP 的一些内容

为什么我们不考虑对数据进行强一致性保证？这归结于现代网络设备架构的分布式系统的属性。这个想法最初是由埃里克·布鲁尔提出的，称为 *CAP 定理*，后来由吉尔伯特和林奇证明 [GL02]。该定理首先介绍了分布式系统的三个属性，它们构成了 CAP 的首字母缩写

• 一致性：在您读取数据时，所有数据的副本是否始终在逻辑上就数据的同一版本达成一致？ (这个一致性的概念与 ACID 中的 C 不同。)
• 可用性：无论有多少副本不可用，副本是否都能响应读写请求？
• 分区容忍性：即使某些副本暂时失去通过网络彼此通信的能力，系统是否还能继续运行？

该定理接着说，在一个运行在多台计算机上的存储系统中，只能实现其中两个属性，而必须牺牲第三个属性。此外，我们被迫实现分区容忍系统。在使用当前消息协议的当前网络硬件上，数据包可能会丢失，交换机可能会发生故障，并且无法确定网络是否已关闭或您尝试向其发送消息的服务器是否不可用。所有 NoSQL 系统都应该是分区容忍的。剩下的选择是在一致性和可用性之间做出选择。没有 NoSQL 系统可以同时提供两者。

选择一致性意味着您的复制数据在所有副本之间不会出现不一致。实现一致性的一个简单方法是要求所有副本确认更新。如果一个副本出现故障，并且您无法确认该副本上的数据更新，那么您将降低其键的可用性。这意味着，在所有副本恢复并响应之前，用户无法收到其更新操作的成功确认。因此，选择一致性意味着选择缺乏对每个数据项的昼夜不间断的可用性。

选择可用性意味着，当用户发出操作时，副本应根据其拥有的数据采取行动，无论其他副本的状态如何。这可能会导致副本之间数据一致性的差异，因为它们不需要确认所有更新，并且某些副本可能没有记录所有更新。

CAP 定理的含义导致了构建 NoSQL 数据存储的强一致性和最终一致性方法。还存在其他方法，例如雅虎的 PNUTS [CRS+08] 系统中提出的松散一致性和松散可用性方法。我们讨论的开源 NoSQL 系统中还没有一个采用这种技术，因此我们将不再赘述。

13.5.2. 强一致性

促进强一致性的系统确保数据项的副本始终能够就键的值达成共识。一些副本可能彼此不同步，但当用户请求 `employee30:salary` 的值时，机器有一种方法可以一致地就用户看到的价值达成一致。如何实现这一点最好用数字来解释。

假设我们在 N 台机器上复制一个键。其中一台机器，可能是 N 台机器中的一台，充当每个用户请求的协调器。协调器确保 N 台机器中的特定数量的机器已接收并确认每个请求。当对某个键进行写入或更新操作时，协调器只有在 W 台副本确认已收到更新后，才向用户确认写入操作已完成。当用户想要读取某个键的值时，协调器只有在至少有 R 台副本响应了相同的值时，才会进行响应。如果 R+W>N，我们说该系统体现了强一致性。

让我们用一些数字来解释这个概念，假设我们在 N=3 台机器上复制每个键（分别称为 A、B 和 C）。假设键 `employee30:salary` 最初设置为 $20,000，但我们想给 `employee30` 加薪到 $30,000。假设对于某个键，我们要求至少 W=2 台 A、B 或 C 机器确认每个写入请求。当 A 和 B 确认对 `(employee30:salary, $30,000)` 的写入请求时，协调器会让用户知道 `employee30:salary` 已成功更新。假设机器 C 从未收到对 `employee30:salary` 的写入请求，因此它仍然保留着 $20,000 的值。当协调器收到对键 `employee30:salary` 的读取请求时，它会将该请求发送到所有 3 台机器

• 如果我们设置 R=1，并且机器 C 首先响应 $20,000，那么我们的员工就不会高兴。
• 但是，如果我们设置 R=2，协调器会看到 C 的值，等待 A 或 B 的第二次响应，该响应将与 C 过时的值发生冲突，最后收到第三台机器的响应，该响应会确认 $30,000 是多数意见。

因此，为了在这个情况下实现强一致性，我们需要设置 R=2}，以便 R+W3}。

当 W 台副本未响应写入请求，或者 R 台副本未以一致的响应响应读取请求时会发生什么？协调器最终可能会超时并向用户发送错误，或者等待情况自行解决。无论哪种方式，系统在至少一段时间内都被认为对该请求不可用。

您选择的 R 和 W 会影响在您的系统对某个键的不同操作变得不可用之前，有多少台机器可以表现异常。例如，如果您强制所有副本确认写入操作，那么 W=N，任何副本故障都会导致写入操作挂起或失败。常见的选择是 R + W = N + 1，这是强一致性所需的最小值，同时仍然允许副本之间存在暂时性差异。许多强一致性系统选择 W=N 和 R=1，因为这样它们就不必为节点不同步而进行设计。

HBase 将其复制存储基于 HDFS，这是一个分布式存储层。HDFS 提供强一致性保证。在 HDFS 中，写入操作只有在复制到所有 N 台（通常为 2 或 3 台）副本后才能成功，因此 W = N。读取操作将由单个副本满足，因此 R = 1。为了避免拖慢写入密集型工作负载，数据会从用户异步并行传输到副本。一旦所有副本确认已收到数据副本，则在所有副本上原子且一致地执行将新数据交换到系统中的最后一步。

13.5.3. 最终一致性

基于 Dynamo 的系统，包括 Voldemort、Cassandra 和 Riak，允许用户根据需要指定 N、R 和 W，即使 R + W <= N 也是如此。这意味着用户可以实现强一致性或最终一致性。当用户选择最终一致性时，即使程序员选择强一致性但 W 小于 N 时，也会出现副本可能不一致的时期。为了在副本之间提供最终一致性，这些系统采用各种工具将过时的副本更新到最新状态。让我们首先了解各种系统如何确定数据已不同步，然后讨论它们如何同步副本，最后介绍一些受 Dynamo 启发的加速同步过程的方法。