第七章数据分片

显然，我们必须打破顺序处理的限制，不能让计算机受到束缚。我们必须明确定义，为数据提供优先级和描述。我们应该陈述关系，而非过程。

——格蕾丝·默里·霍珀，《管理与未来的计算机》（1962）

致早期版本读者

本电子书为早期版本，您看到的是作者写作过程中的原始未编辑内容——这样您就能在这些技术正式发布前抢先掌握。

这将是最终书籍的第七章。本书的 GitHub 仓库地址为：https://github.com/ept/ddia2-feedback

如果您希望积极参与本草案的审阅和评论，请在 GitHub 上联系我们。

7.1 分片的基本概念

分布式数据库通常通过两种方式在多个节点间分布数据：

复制（Replication）：在多个节点上保存相同数据的副本（我们在第六章讨论过）
分片（Sharding）：将大量数据拆分成更小的分片或分区，存储在不同的节点上（本章主题）

通常，分片的定义方式是每条数据（每条记录、每行或每个文档）恰好属于一个分片。实现这一目标有多种方法，我们将在本章深入讨论。实际上，每个分片本身就是一个小型数据库，尽管某些数据库系统支持同时操作多个分片的操作。

分片通常与复制结合使用，这样每个分片的副本可以存储在多个节点上。这意味着，尽管每条记录只属于一个分片，但为了容错，它仍可能存储在多个不同的节点上。

如果使用单主复制模型，分片和复制的组合可能如图 7-1 所示。每个分片的主节点分配给一个节点，其从节点分配给其他节点。每个节点可能是某些分片的主节点，同时是其他分片的从节点，但每个分片仍然只有一个主节点。

图 7-1：结合复制与分片——每个节点作为某些分片的主节点，同时作为其他分片的从节点

我们在第六章讨论的所有关于数据库复制的内容同样适用于分片的复制。由于分片方案的选择与复制方案的选择基本独立，为了简化，本章将忽略复制的内容。

7.1.1 分片与分区

本章所说的”分片”在不同软件中有不同的名称：

Kafka：分区（partition）
CockroachDB：范围（range）
HBase、TiDB：区域（region）
Bigtable、YugabyteDB：表片（tablet）
Cassandra、ScyllaDB、Riak：虚拟节点（vnode）
Couchbase：vBucket

某些数据库将分区和分片视为两个不同的概念。例如，在 PostgreSQL 中，分区是将大表拆分成多个存储在同一台机器上的文件（这有诸多优势，如删除整个分区非常快），而分片则是将数据集分布在多台机器上。但在许多其他系统中，分区只是分片的另一种说法。

虽然”分区”一词相当直观，但”分片”这个词可能令人意外。据一种理论，该术语源自在线角色扮演游戏《网络创世纪》（Ultima Online），其中一块魔法水晶被击碎成多片，每片都折射出一个游戏世界的副本。“分片”因此成为一组并行游戏服务器之一的代名词，后来被引入到数据库领域。另一种理论认为，shard 最初是”System for Highly Available Replicated Data”（高可用复制数据系统）的缩写——据说是 1980 年代的一个数据库，其细节已湮没在历史中。

顺便一提，分区与网络分区（network partitions，即 netsplits）无关，后者是节点间网络故障的一种类型，我们将在第九章讨论。

7.2 分片的优缺点

7.2.1 主要优势：可扩展性

分片数据库的主要原因是可扩展性：当数据量或写入吞吐量过大，单节点无法处理时，分片允许您将数据和写入分散到多个节点。（如果问题是读取吞吐量，您不一定需要分片——可以使用第六章讨论的读扩展。）

事实上，分片是我们实现水平扩展（scale-out 架构）的主要工具之一：即通过添加更多（较小的）机器来扩展系统容量，而不是迁移到更大的机器。如果您能将工作负载划分，使每个分片处理大致相等的份额，就可以将这些分片分配到不同的机器上，并行处理其数据和查询。

虽然复制在小型和大型规模下都有用，因为它实现了容错和离线操作，但分片是一种重量级解决方案，主要适用于大规模场景。如果您的数据量和写入吞吐量可以在单台机器上处理（而现在的单台机器性能已经很强大！），通常最好避免分片，坚持使用单分片数据库。

7.2.2 主要劣势：复杂性

这样建议的原因是分片通常会增加复杂性：您通常必须通过选择分区键来决定哪些记录放入哪个分片；所有具有相同分区键的记录都放置在同一个分片中。这个选择很重要，因为如果您知道记录在哪个分片，访问记录会很快，但如果不知道分片，就必须在所有分片上进行低效的搜索，而且分片方案很难更改。

因此，分片通常适用于键值数据（可以轻松地按键分片），但对于关系数据则较难处理——您可能希望通过二级索引搜索，或连接分布在不同分片上的记录。我们将在”分片与二级索引”一节中进一步讨论。

分片的另一个问题是，一次写入可能需要更新多个不同分片中的相关记录。虽然单节点事务相当常见（见第八章），但确保跨多个分片的一致性需要分布式事务。正如我们将在第八章看到的，某些数据库支持分布式事务，但它们通常比单节点事务慢得多，可能成为整个系统的瓶颈，而且某些系统根本不支持它们。

7.2.3 单机分片

某些系统甚至在单台机器上使用分片，通常每个 CPU 核心运行一个单线程进程，以利用 CPU 的并行性，或利用非统一内存访问（NUMA）架构——在这种架构中，某些内存库比其他的更接近某个 CPU。例如，Redis、VoltDB 和 FoundationDB 每个核心使用一个进程，依靠分片在同一台机器内的 CPU 核心间分散负载。

7.3 多租户场景下的分片

软件即服务（SaaS）产品和云服务通常是多租户的，每个租户是一个客户。多个用户可能在同一租户上拥有登录账号，但每个租户拥有与其他租户隔离的独立数据集。例如，在电子邮件营销服务中，注册的每个企业通常是一个独立的租户，因为一个企业的通讯订阅、投递数据等与其他企业的数据是分开的。

有时分片用于实现多租户系统：要么为每个租户分配一个独立的分片，要么将多个小租户组合成一个更大的分片。这些分片可能是物理上独立的数据库，或者是更大逻辑数据库中可独立管理的部分。

7.3.1 多租户分片的优势

优势	说明
资源隔离	如果一个租户执行计算密集型操作，其他租户的性能不太可能受到影响
权限隔离	如果访问控制逻辑有 bug，租户数据物理分离降低了意外访问其他租户数据的风险
单元化架构	可将特定租户组的服务和存储分组到独立的单元中，提供故障隔离
按租户备份恢复	单独备份每个租户的分片，可在不影响其他租户的情况下恢复租户状态
合规性	如 GDPR 等法规要求，分片存储便于数据导出和删除操作
数据驻留	可将租户分片分配到特定区域，满足数据驻留法律要求
渐进式模式推出	可逐个租户进行模式迁移，降低风险

7.3.2 多租户分片的挑战

假设每个租户足够小，能容纳在单个节点上。如果不满足，需要在单个租户内再进行分片
小租户过多时的开销问题。为每个小租户创建独立分片可能开销过大；组合租户又面临租户增长后的迁移问题
跨租户功能实现困难。需要跨多个分片连接数据时，实现变得复杂

7.4 键值数据的分片

假设您有大量数据想要分片。如何决定哪些记录存储在哪个节点上？

分片的目标是将数据和查询负载均匀分布在节点上。如果每个节点承担公平的份额，理论上 10 个节点应该能够处理单节点 10 倍的数据量和 10 倍的读写吞吐量（忽略复制）。此外，如果添加或移除节点，我们希望重新平衡负载，使其均匀分布在 11 个（添加时）或剩余 9 个（移除时）节点上。

如果分片不公平，某些分片的数据或查询比其他分片多，我们称之为倾斜（skewed）。倾斜的存在大大降低了分片的有效性。在极端情况下，所有负载可能都落在一个分片上，导致 9/10 的节点空闲，瓶颈是单个繁忙节点。负载过高的分片称为热分片（hot shard）或热点（hot spot）。如果某个键的负载特别高（如社交网络中的名人），我们称之为热键（hot key）。

因此，我们需要一个算法，输入记录的分区键，告诉我们该记录在哪个分片中。在键值存储中，分区键通常是键或键的第一部分。在关系模型中，分区键可能是表的某列（不一定是主键）。该算法需要支持重新平衡，以缓解热点。

7.4.1 按键范围分片

一种分片方式是为每个分片分配一个连续的分区键范围（从某个最小值到某个最大值），就像纸质百科全书的卷册一样（见图 7-2）。在这个例子中，条目的分区键是其标题。如果要查找特定标题的条目，您可以轻松确定哪个分片包含该条目——找到其键范围包含您要查找标题的卷册，然后从书架上取出正确的书。

图 7-2：纸质百科全书按键范围分片

键范围不一定均匀分布，因为您的数据可能不均匀分布。例如，在图 7-2 中，第 1 卷包含以 A 和 B 开头的词，而第 12 卷包含以 T、U、V、W、X、Y、Z 开头的词。简单地每两个字母一卷会导致某些卷比其他卷大得多。为了均匀分布数据，分片边界需要适应数据。

分片边界可以由管理员手动选择，也可以由数据库自动选择。手动键范围分片的例子有 Vitess（MySQL 的分片层）；自动变体用于 Bigtable、其开源等价物 HBase、MongoDB 的范围分片选项、CockroachDB、RethinkDB 和 FoundationDB。YugabyteDB 提供手动和自动表片拆分。

在每个分片内，键按排序顺序存储（如 B 树或 SSTable，见第四章）。这有利于范围扫描，您可以将键视为串联索引，在一次查询中获取多条相关记录。例如，考虑一个存储传感器网络数据的应用，键是测量的时间戳。在这种情况下，范围扫描非常有用，因为您可以轻松获取特定月份的所有读数。

键范围分片的缺点是，如果有大量写入邻近的键，容易产生热分片。例如，如果键是时间戳，分片对应时间范围——如每月一个分片。不幸的是，如果传感器测量发生时就将数据写入数据库，所有写入都会进入同一个分片（当前月份的分片），导致该分片写入过载，而其他分片空闲。

为避免传感器数据库中的这个问题，您需要使用时间戳以外的内容作为键的第一元素。例如，可以在每个时间戳前加上传感器 ID，使键排序首先按传感器 ID，然后按时间戳。假设同时有许多传感器处于活动状态，写入负载将更均匀地分布在分片上。缺点是，当您想获取时间范围内多个传感器的值时，现在需要为每个传感器执行单独的范围查询。

键范围分片数据的重新平衡

首次设置数据库时，没有键范围可拆分为分片。某些数据库（如 HBase 和 MongoDB）允许您在空数据库上配置初始分片集，这称为预拆分（pre-splitting）。这需要您已经对键分布有所了解，以便选择适当的键范围边界。

随着数据量和写入吞吐量的增长，键范围分片的系统通过将现有分片拆分为两个或多个较小的分片来扩展，每个分片持有原始分片键范围的连续子范围。生成的较小分片可以分布在多个节点上。如果大量数据被删除，您可能还需要将几个相邻的小分片合并成一个更大的分片。这个过程类似于 B 树顶层发生的情况。

对于自动管理分片边界的数据库，分片拆分通常由以下因素触发：

分片达到配置的大小（例如，HBase 默认为 10 GB）
某些系统中，写入吞吐量持续超过阈值。因此，热分片即使没有存储大量数据也可能被拆分，以便更均匀地分布其写入负载。

键范围分片的一个优势是分片数量适应数据量。如果数据量小，少量分片就足够了，开销小；如果数据量大，每个分片的大小限制在可配置的最大值内。

这种方法的缺点是拆分分片是昂贵的操作，因为它需要将所有数据重写到新文件中，类似于日志结构存储引擎中的压缩。需要拆分的分片通常也是负载高的分片，拆分的成本可能加剧该负载，使其面临过载风险。

7.4.2 按键哈希分片

如果您希望分区键邻近（但不同）的记录分组到同一个分片（如时间戳的情况），键范围分片很有用。如果您不关心分区键是否邻近（如多租户应用中的租户 ID），常见的方法是先对分区键进行哈希，再映射到分片。

良好的哈希函数将倾斜的数据转换为均匀分布。假设您有一个 32 位哈希函数，接受字符串输入。每当给它一个新字符串，它就返回一个 0 到 2³²−1 之间的看似随机的数字。即使输入字符串非常相似，它们的哈希也均匀分布在该数字范围内（但相同输入总是产生相同输出）。

对于分片目的，哈希函数不需要加密强度强：例如，MongoDB 使用 MD5，而 Cassandra 和 ScyllaDB 使用 Murmur3。许多编程语言有内置的简单哈希函数（用于哈希表），但它们可能不适合分片：例如，Java 的 Object.hashCode() 和 Ruby 的 Object#hash，相同键在不同进程中可能有不同的哈希值，使它们不适合分片。

哈希取模节点数

有了哈希值后，如何选择存储它的分片？您的第一个想法可能是对系统中的节点数取模（使用许多编程语言中的 % 运算符）。例如，hash(key) % 10 将返回 0 到 9 之间的数字。如果我们有 10 个编号为 0 到 9 的节点，这似乎是分配每个键到节点的简单方法。

mod N 方法的问题是，如果节点数 N 变化，大多数键必须从一台节点移动到另一台节点。图 7-3 显示了拥有三个节点并添加第四个时发生的情况。重新平衡前，节点 0 存储哈希为 0、3、6、9 等的键。添加第四个节点后，哈希为 3 的键移动到节点 3，哈希为 6 的键移动到节点 2，哈希为 9 的键移动到节点 1，等等。

图 7-3：通过哈希键并对节点数取模将键分配给节点。改变节点数会导致许多键从一台节点移动到另一台节点

mod N 函数计算简单，但导致非常低效的重新平衡，因为记录从一台节点到另一台节点有大量不必要的移动。我们需要一种不会不必要地移动数据的方法。

固定分片数

一个简单但广泛使用的解决方案是创建比节点数多得多的分片，并为每个节点分配多个分片。例如，运行在 10 节点集群上的数据库可能从一开始就分成 1,000 个分片，这样每个节点分配 100 个分片。然后键存储在分片号 hash(key) % 1,000 中，系统单独跟踪每个分片存储在哪个节点上。

现在，如果向集群添加节点，系统可以将现有节点的一些分片重新分配给新节点，直到再次均匀分布。这个过程如图 7-4 所示。如果从集群中移除节点，则反向进行相同操作。

图 7-4：向具有每个节点多个分片的数据库集群添加新节点

在这个模型中，只有整个分片在节点间移动，这比拆分分片便宜。分片数量不变，键到分片的分配也不变。唯一改变的是分片到节点的分配。这种分配更改不是即时的——通过网络传输大量数据需要时间——因此在传输进行期间，任何读写操作仍使用分片的旧分配。

通常选择分片数量为可被许多因子整除的数字，以便数据集可以均匀分布在各种不同数量的节点上——不需要节点数是 2 的幂。您甚至可以考虑集群中不匹配的硬件：通过为更强大的节点分配更多分片，可以使这些节点承担更大的负载份额。

这种分片方法用于 Citus（PostgreSQL 的分片层）、Riak、Elasticsearch 和 Couchbase 等。只要您在首次创建数据库时对需要的分片数有良好的估计，它就工作良好。然后您可以轻松添加或移除节点，限制是您不能拥有比分片数更多的节点。

如果您发现最初配置的分片数错误——例如，如果您已达到需要比分片数更多节点的规模——则需要昂贵的**重新分片（resharding）**操作。它需要拆分每个分片并将其写入新文件，在此过程中使用大量额外的磁盘空间。某些系统不允许在并发写入数据库时重新分片，这使得在不宕机的情况下更改分片数变得困难。

如果数据集的总大小变化很大（例如，开始时小但可能随时间增长很大），选择正确的分片数很困难。由于每个分片包含总数据的固定比例，每个分片的大小与集群中的总数据量成比例增长。如果分片非常大，重新平衡和从节点故障恢复变得昂贵。但如果分片太小，它们会产生太多开销。当分片大小”恰到好处”时，既不太大也不太小，性能最佳，如果分片数固定但数据集大小变化，这可能很难实现。

哈希范围分片

如果无法预先预测需要的分片数，最好使用分片数能轻松适应工作负载的方案。前述键范围分片方案具有此属性，但当有大量写入邻近键时有热点风险。一个解决方案是将键范围分片与哈希函数结合，使每个分片包含哈希值范围而非键范围。

图 7-5 显示了一个使用 16 位哈希函数的例子，返回 0 到 65,535 = 2¹⁶−1 之间的数字（实际上哈希通常是 32 位或更多）。即使输入键非常相似（如连续的时间戳），它们的哈希也均匀分布在该范围内。然后我们可以为每个分片分配一个哈希值范围：例如，0 到 16,383 的值分配给分片 0，16,384 到 32,767 的值分配给分片 1，等等。

图 7-5：为每个分片分配连续的哈希值范围

与键范围分片一样，哈希范围分片中的分片可以在变得太大或负载太重时拆分。这仍然是昂贵的操作，但可以按需进行，因此分片数量适应数据量，而非预先固定。

与键范围分片相比的缺点是，对分区键的范围查询效率不高，因为范围内的键现在分散在所有分片中。但是，如果键由两列或多列组成，且分区键只是这些列中的第一列，您仍然可以对第二列及后续列执行高效的范围查询：只要范围查询中的所有记录具有相同的分区键，它们就在同一个分片中。

数据仓库中的分区与范围查询

BigQuery、Snowflake 和 Delta Lake 等数据仓库支持类似的索引方法，尽管术语不同。在 BigQuery 中，分区键决定记录位于哪个分区，而”聚簇列”决定分区内的记录排序方式。Snowflake 自动将记录分配给”微分区”，但允许用户为表定义聚簇键。Delta Lake 支持手动和自动分区分配，并支持聚簇键。聚簇数据不仅提高范围扫描性能，还可以提高压缩和过滤性能。

哈希范围分片用于 YugabyteDB 和 DynamoDB，也是 MongoDB 的一个选项。Cassandra 和 ScyllaDB 使用这种方法的变体，如图 7-6 所示：哈希值空间被拆分为与节点数成比例的数量（图 7-6 中每个节点 3 个范围，但实际数字 Cassandra 默认为每个节点 8 个，ScyllaDB 为 256 个），这些范围之间有随机边界。这意味着某些范围比其他范围大，但通过每个节点有多个范围，这些不平衡往往会被平均。

图 7-6：Cassandra 和 ScyllaDB 将可能的哈希值范围（此处为 0-1023）拆分为具有随机边界的连续范围，并为每个节点分配多个范围

当添加或移除节点时，添加和移除范围边界，并相应地拆分或合并分片。在图 7-6 的例子中，当添加节点 3 时，节点 1 将其两个范围的部分转移给节点 3，节点 2 将其一个范围的部分转移给节点 3。这具有给新节点大约公平份额的数据集的效果，而不需要比必要更多的数据从一台节点传输到另一台节点。

一致性哈希

一致性哈希算法是一种将键映射到指定数量分片的哈希函数，满足两个属性：

映射到每个分片的键数大致相等
当分片数量变化时，尽可能少的键从一台分片移动到另一台

注意，这里的”一致性”与副本一致性（见第六章）或 ACID 一致性（见第八章）无关，而是描述键尽可能保持在同一分片的趋势。

Cassandra 和 ScyllaDB 使用的分片算法类似于一致性哈希的原始定义，但也提出了其他几种一致性哈希算法，如最高随机权重（又称会合哈希）和跳跃一致性哈希。使用 Cassandra 的算法，如果添加一个节点，少量现有分片被拆分为子范围；另一方面，使用会合和跳跃一致性哈希，新节点被分配之前分散在所有其他节点上的单个键。哪种更可取取决于应用。

7.4.3 倾斜工作负载与热点缓解

一致性哈希确保键均匀分布在节点上，但这并不意味着实际负载均匀分布。如果工作负载高度倾斜——即某些分区键下的数据量远大于其他键，或某些键的请求速率远高于其他键——您仍可能遇到某些服务器过载而其他服务器几乎空闲的情况。

例如，在社交媒体网站上，拥有数百万粉丝的名人用户在做某事时可能引发活动风暴。这一事件可能导致对同一键的大量读写（分区键可能是名人的用户 ID，或人们评论的行为 ID）。

在这种情况下，需要更灵活的分片策略。基于键范围（或哈希范围）定义分片的系统可以将单个热键单独放在一个分片中，甚至可能为其分配专用机器。

也可以在应用层补偿倾斜。例如，如果一个键已知非常热，一个简单的技术是在键的开头或结尾添加随机数。仅一个两位十进制随机数就会将键的写入均匀分布在 100 个不同的键上，允许这些键分布到不同的分片。

然而，将写入分散到不同键后，任何读取现在都需要做额外工作，因为它们必须从所有 100 个键读取数据并合并。热分片的读取量没有减少；只有写入负载被拆分。这种技术还需要额外的簿记：只有对少数热键追加随机数才有意义；对于绝大多数写入吞吐量低的键，这将是不必要的开销。因此，您还需要某种方式来跟踪哪些键被拆分，以及将常规键转换为特殊管理热键的过程。

问题因负载随时间变化而进一步复杂化：例如，某个特定的社交媒体帖子可能几天内经历高负载，但之后很可能平静下来。此外，某些键可能写入热而另一些读取热，需要不同的处理策略。

某些系统（特别是为大规模设计的云服务）有自动处理热分片的方法；例如，Amazon 称之为热量管理或自适应容量。

7.5 操作：自动或手动重新平衡

关于重新平衡有一个重要问题我们略过了：分片的拆分和重新平衡是自动发生还是手动进行？

某些系统自动决定何时拆分分片以及何时将它们从一台节点移动到另一台节点，无需人工交互，而其他系统则让管理员显式配置分片。也有中间地带：例如，Couchbase 和 Riak 自动生成建议的分片分配，但需要管理员提交后才能生效。

完全自动重新平衡可能很方便，因为正常维护的操作工作较少，这样的系统甚至可以自动扩展以适应工作负载变化。云数据库如 DynamoDB 被宣传为能够在几分钟内自动添加和移除分片以适应负载的大幅增减。

然而，自动分片管理也可能不可预测。重新平衡是昂贵的操作，因为它需要重新路由请求并通过网络移动大量数据。如果不仔细进行，这个过程可能使网络或节点过载，可能损害其他请求的性能。系统必须在重新平衡进行期间继续处理写入；如果系统接近其最大写入吞吐量，分片拆分过程甚至可能跟不上传入写入的速率。

这种自动化与自动故障检测结合时可能很危险。例如，假设一个节点过载，暂时对请求响应缓慢。其他节点断定过载节点已死，自动重新平衡集群以将负载移开。这给其他节点和网络增加了额外负载，使情况更糟。存在引发级联故障的风险，其他节点也变得过载并被错误地怀疑宕机。

因此，让人工参与重新平衡可能是件好事。它比全自动过程慢，但可以帮助防止操作意外。

7.6 请求路由

我们已经讨论了如何将数据集分片到多个节点，以及如何在添加或移除节点时重新平衡这些分片。现在转向问题：如果您想读取或写入特定键，如何知道需要连接哪个节点——即哪个 IP 地址和端口号？

我们称这个问题为请求路由，它与我们之前讨论的服务发现非常相似。两者最大的区别是，对于运行应用代码的服务，每个实例通常是无状态的，负载均衡器可以将请求发送到任何实例。对于分片数据库，键的请求只能由包含该键的分片的副本节点处理。

这意味着请求路由必须了解从键到分片、从分片到节点的分配。从高层次看，有几种不同的方法解决这个问题（见图 7-7）：

允许客户端联系任何节点（如通过轮询负载均衡器）。如果该节点恰好拥有请求适用的分片，它可以直接处理请求；否则，它将请求转发到适当节点，接收回复，然后将回复传递给客户端。
将所有客户端请求先发送到路由层，路由层确定应该由哪个节点处理每个请求并相应转发。这个路由层本身不处理任何请求；它只是作为分片感知的负载均衡器。
要求客户端了解分片和分片到节点的分配。在这种情况下，客户端可以直接连接到适当节点，无需任何中介。

图 7-7：将请求路由到正确节点的三种不同方式

在所有情况下，都存在一些关键问题：

谁决定哪个分片应该位于哪个节点上？ 最简单的做法是有一个协调器做出决定，但如果运行协调器的节点宕机，如何使其容错？如果协调器角色可以故障转移到另一个节点，如何防止脑裂情况（见”处理节点故障”），即两个不同的协调器做出矛盾的分片分配？
执行路由的组件（可能是节点之一、路由层或客户端）如何了解分片到节点分配的变化？
当分片从一台节点移动到另一台节点时，存在切换期，新节点已接管，但发往旧节点的请求可能仍在传输中。如何处理这些请求？

许多分布式数据系统依赖单独的协调服务（如 ZooKeeper 或 etcd）来跟踪分片分配，如图 7-8 所示。它们使用共识算法（见第十章）提供容错和防止脑裂保护。每个节点在 ZooKeeper 中注册自己，ZooKeeper 维护分片到节点的权威映射。其他参与者，如路由层或分片感知客户端，可以订阅 ZooKeeper 中的此信息。每当分片更改所有权，或添加或移除节点时，ZooKeeper 通知路由层，使其保持路由信息最新。

图 7-8：使用 ZooKeeper 跟踪分片到节点的分配

例如，HBase 和 SolrCloud 使用 ZooKeeper 管理分片分配，Kubernetes 使用 etcd 跟踪哪个服务实例在哪里运行。MongoDB 有类似的架构，但依赖自己的配置服务器实现和 mongos 守护进程作为路由层。Kafka、YugabyteDB 和 TiDB 使用内置的 Raft 共识协议实现来执行此协调功能。

Cassandra、ScyllaDB 和 Riak 采用不同方法：它们使用节点间的流言协议（gossip protocol） 传播集群状态的任何变化。这提供的一致性比共识协议弱得多；可能出现脑裂，即集群的不同部分对同一分片有不同的节点分配。无领导数据库可以容忍这一点，因为它们通常做出较弱的一致性保证（见”法定一致性的局限性”）。

使用路由层或将请求发送到随机节点时，客户端仍需要找到要连接的 IP 地址。这些不像分片到节点的分配那样变化快，因此通常使用 DNS 就足够了。

本讨论集中在为单个键寻找分片，这与分片 OLTP 数据库最相关。分析数据库通常也使用分片，但它们的查询执行方式非常不同：查询通常需要并行聚合和连接来自许多不同分片的数据。我们将在第十一章讨论这种并行查询执行的技术。

7.7 分片与二级索引

到目前为止我们讨论的分片方案依赖于客户端知道它想要访问的任何记录的分区键。这在键值数据模型中最容易实现，其中分区键是主键的第一部分（或整个主键），因此我们可以使用分区键确定分片，从而将读写路由到负责该键的节点。

如果涉及二级索引，情况变得更加复杂（另见”多列和二级索引”）。二级索引通常不唯一标识记录，而是一种搜索特定值出现的方式：查找用户 123 的所有行为，查找包含单词”hogwash”的所有文章，查找颜色为红色的所有汽车，等等。

键值存储通常没有二级索引，但它们是关系数据库的面包和黄油，在文档数据库中也很常见，是 Solr 和 Elasticsearch 等全文搜索引擎的存在理由。二级索引的问题是它们不能整齐地映射到分片。对具有二级索引的数据库进行分片有两种主要方法：本地索引和全局索引。

7.7.1 本地二级索引

例如，假设您运营一个销售二手车的网站（见图 7-9）。每个列表有唯一 ID，您使用该 ID 作为分片的分区键（例如，ID 0-499 在分片 0，ID 500-999 在分片 1，等等）。

如果您想让用户搜索汽车，允许他们按颜色和制造商过滤，您需要在颜色和制造商上建立二级索引（在文档数据库中这些是字段；在关系数据库中它们是列）。如果您声明了索引，数据库可以自动执行索引。例如，每当向数据库添加一辆红色汽车时，数据库分片自动将其 ID 添加到索引项 color:red 的 ID 列表中。如第四章所述，该 ID 列表也称为倒排列表（postings list）。

图 7-9：本地二级索引——每个分片只索引自己分片内的记录

⚠️ 警告

如果您的数据库只支持键值模型，您可能会想在应用代码中通过创建从值到 ID 的映射来实现二级索引。如果走这条路，您需要非常小心确保索引与底层数据保持一致。竞态条件和间歇性写入失败（某些更改已保存但其他没有）很容易使数据不同步——见”多对象事务的需求”。

在这种索引方法中，每个分片完全独立：每个分片维护自己的二级索引，只覆盖该分片中的记录。它不关心其他分片中存储什么数据。每当您写入数据库——添加、移除或更新记录——您只需要处理包含您要写入记录的分片。因此，这种类型的二级索引称为本地索引。在信息检索上下文中，它也称为文档分区索引（document-partitioned index）。

从本地二级索引读取时，如果您已经知道要查找记录的分区键，可以直接在适当的分片上执行搜索。此外，如果您只需要一些结果而不需要全部，可以将请求发送到任何分片。

但是，如果您想要所有结果且事先不知道它们的分区键，您需要将查询发送到所有分片，并合并返回的结果，因为匹配的记录可能分散在所有分片中。在图 7-9 中，红色汽车出现在分片 0 和分片 1 中。

这种查询分片数据库的方法可能使二级索引的读取查询相当昂贵。即使您并行查询分片，它也容易出现尾延迟放大（见”响应时间指标的使用”）。它还限制了应用的可扩展性：添加更多分片可以让您存储更多数据，但如果每个分片都必须处理每个查询，它不会增加您的查询吞吐量。

尽管如此，本地二级索引被广泛使用：例如，MongoDB、Riak、Cassandra、Elasticsearch、SolrCloud 和 VoltDB 都使用本地二级索引。

7.7.2 全局二级索引

与其让每个分片有自己的本地二级索引，我们可以构建一个覆盖所有分片数据的全局索引。但是，我们不能只将索引存储在一个节点上，因为它可能成为瓶颈，违背分片的目的。全局索引也必须被分片，但它可以与主键索引不同地分片。

图 7-10 显示了这可能的样子：来自所有分片的红色汽车 ID 出现在索引的 color:red 下，但索引被分片，使得以字母 a 到 r 开头的颜色出现在分片 0，以 s 到 z 开头的颜色出现在分片 1。汽车制造商的索引类似地分区（分片边界在 f 和 h 之间）。

图 7-10：全局二级索引反映来自所有分片的数据，本身按索引值分片

这种索引也称为词分区（term-partitioned）：回想”全文搜索”中，在全文搜索中，词是文本中可搜索的关键词。这里我们将其泛化为指可在二级索引中搜索的任何值。

全局索引使用词作为分区键，因此当您查找特定词或值时，可以找出需要查询哪个分片。与之前一样，分片可以包含连续的词范围（如图 7-10），或基于词的哈希将词分配给分片。

全局索引的优势是，具有单一条件的查询（如 color = red）只需要从单个分片读取即可获取倒排列表。但是，如果您想获取记录而不仅仅是 ID，您仍然必须从负责这些 ID 的所有分片读取。

如果您有多个搜索条件或词（例如，搜索特定颜色和特定制造商的汽车，或搜索同一文本中出现的多个词），这些词很可能被分配到不同的分片。要计算两个条件的逻辑与，系统需要找出出现在两个倒排列表中的所有 ID。如果倒排列表短，这不是问题，但如果它们长，通过网络发送它们来计算交集可能很慢。

全局二级索引的另一个挑战是，写入比本地索引更复杂，因为写入单条记录可能影响索引的多个分片（文档中的每个词可能在不同的分片上）。这使得保持二级索引与底层数据同步更加困难。一个选择是使用分布式事务原子更新存储主记录及其二级索引的分片（见第八章）。

全局二级索引用于 CockroachDB、TiDB 和 YugabyteDB；DynamoDB 支持本地和全局二级索引。在 DynamoDB 的情况下，写入异步反映在全局索引中，因此从全局索引读取可能是陈旧的（类似于复制延迟，见”复制延迟的问题”）。尽管如此，如果读取吞吐量高于写入吞吐量，且倒排列表不太长，全局索引很有用。

7.8 本章总结

在本章中，我们探讨了将大数据集分片成较小子集的不同方法。当数据量如此之大，单台机器无法再存储和处理时，分片是必要的。

分片的目标是将数据和查询负载均匀分布在多台机器上，避免热点（负载过高的节点）。这需要选择适合您数据的分片方案，并在节点添加或移除时重新平衡分片。

我们讨论了两种主要的分片方法：

方法	描述	优势	劣势
键范围分片	键排序，分片拥有从某个最小值到某个最大值的所有键	支持高效范围查询	如果应用经常访问排序顺序中邻近的键，有热点风险
哈希分片	对每个键应用哈希函数，分片拥有哈希值范围	负载分布更均匀	破坏键的顺序，使范围查询效率低下

对于哈希分片，通常预先创建固定数量的分片，为每个节点分配多个分片，并在添加或移除节点时在节点间移动整个分片。与键范围一样，拆分分片也是可能的。

通常使用键的第一部分作为分区键（即标识分片），并在该分片内按键的其余部分排序记录。这样您仍然可以在具有相同分区键的记录间进行高效的范围查询。

我们还讨论了分片与二级索引的交互。二级索引也需要分片，有两种方法：

类型	写入	读取	说明
本地二级索引	只需更新单个分片	需要从所有分片读取	二级索引与主键和值存储在同一分片中
全局二级索引	可能需要更新多个二级索引分片	可以从单个分片提供倒排列表（获取实际记录仍需从多个分片读取）	基于索引值单独分片，条目可能引用主键所有分片的记录

最后，我们讨论了将查询路由到适当分片的技术，以及协调服务通常如何用于跟踪分片到节点的分配。

设计上，每个分片大部分独立运行——这正是分片数据库能够扩展到多台机器的原因。然而，需要写入多个分片的操作可能有问题：例如，如果对一个分片的写入成功，但对另一个失败，会发生什么？我们将在后续章节中解决这个问题。

参考文献

[1] Claire Giordano. Understanding partitioning and sharding in Postgres and Citus. citusdata.com, August 2023.

[2] Brandur Leach. Partitioning in Postgres, 2022 edition. brandur.org, October 2022.

[3] Raph Koster. Database “sharding” came from UO? raphkoster.com, January 2009.

[4] Garrett Fidalgo. Herding elephants: Lessons learned from sharding Postgres at Notion. notion.com, October 2021.

[5] Ulrich Drepper. What Every Programmer Should Know About Memory. akkadia.org, November 2007.

[6] Jingyu Zhou 等. FoundationDB: A Distributed Unbundled Transactional Key Value Store. ACM SIGMOD, June 2021.

[7] Marco Slot. Citus 12: Schema-based sharding for PostgreSQL. citusdata.com, July 2023.

[8] Robisson Oliveira. Reducing the Scope of Impact with Cell-Based Architecture. AWS Well-Architected white paper, September 2023.

[9] Gwen Shapira. Things DBs Don’t Do - But Should. thenile.dev, February 2023.

[10] Malte Schwarzkopf 等. Position: GDPR Compliance by Construction. Poly, August 2019.

[11] Gwen Shapira. Introducing pg_karnak: Transactional schema migration across tenant databases. thenile.dev, November 2024.

[12] Arka Ganguli 等. Scaling Datastores at Slack with Vitess. slack.engineering, December 2020.

[13] Ikai Lan. App Engine Datastore Tip: Monotonically Increasing Values Are Bad. ikaisays.com, January 2011.

[14] Enis Soztutar. Apache HBase Region Splitting and Merging. cloudera.com, February 2013.

[15] Eric Evans. Rethinking Topology in Cassandra. Cassandra Summit, June 2013.

[16] Martin Kleppmann. Java’s hashCode Is Not Safe for Distributed Systems. martin.kleppmann.com, June 2012.

[17] Mostafa Elhemali 等. Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service. USENIX ATC, July 2022.

[18] Brandon Williams. Virtual Nodes in Cassandra 1.2. datastax.com, December 2012.

[19] Branimir Lambov. New Token Allocation Algorithm in Cassandra 3.0. datastax.com, January 2016.

[20] David Karger 等. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. ACM STOC, May 1997.

[21] Damian Gryski. Consistent Hashing: Algorithmic Tradeoffs. dgryski.medium.com, April 2018.

[22] David G. Thaler 和 Chinya V. Ravishankar. Using name-based mappings to increase hit rates. IEEE/ACM Transactions on Networking, February 1998.

[23] John Lamping 和 Eric Veach. A Fast, Minimal Memory, Consistent Hash Algorithm. arxiv.org, June 2014.

[24] Samuel Axon. 3% of Twitter’s Servers Dedicated to Justin Bieber. mashable.com, September 2010.

[25] Gerald Guo 和 Thawan Kooburat. Scaling services with Shard Manager. engineering.fb.com, August 2020.

[26] Sangmin Lee 等. Shard Manager: A Generic Shard Management Framework for Geo-distributed Applications. ACM SOSP, October 2021.

[27] Scott Lystig Fritchie. A Critique of Resizable Hash Tables: Riak Core & Random Slicing. infoq.com, August 2018.

[28] Andy Warfield. Building and operating a pretty big storage system called S3. allthingsdistributed.com, July 2023.

[29] Rich Houlihan. DynamoDB adaptive capacity: smooth performance for chaotic workloads. AWS re:Invent, November 2017.

[30] Christopher D. Manning 等. Introduction to Information Retrieval. Cambridge University Press, 2008.

[31] Michael Busch 等. Earlybird: Real-Time Search at Twitter. IEEE ICDE, April 2012.

[32] Nadav Har’El. Indexing in Cassandra 3. github.com, April 2017.

[33] Zachary Tong. Customizing Your Document Routing. elastic.co, June 2013.

[34] Andrew Pavlo. H-Store Frequently Asked Questions. hstore.cs.brown.edu, October 2013.

第七章 数据分片