7 分片

显然，我们必须跳出电脑指令序列的窠臼，不能让计算机受制于此。我们必须陈述定义、指明优先级、描述数据；我们必须阐明关系，而不是编写过程。

Grace Murray Hopper，未来的计算机及其管理（1962）

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

1. 在多个节点上保存相同数据的副本：这就是 复制（replication），我们已在 第 6 章 中讨论过。
2. 如果不想让每个节点都存储全部数据，可以将大规模数据集拆成更小的 分片（shard） 或 分区（partition），再把不同分片存放到不同节点上。本章讨论的就是分片。

通常情况下，每条数据（每条记录、每行或每个文档）属于且仅属于一个分片。实现这一点有多种方法，本章将深入讨论其中几种。实际上，每个分片都是自己的小型数据库，尽管有些数据库支持同时涉及多个分片的操作。

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

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

我们在 第 6 章 中讨论的关于数据库复制的所有内容，同样适用于分片的复制。大多数情况下，分片方案与复制方案可以独立选择；为简单起见，本章将忽略复制。

分片的利与弊

对数据库进行分片，主要是为了获得 可伸缩性（scalability）：当数据量或写入吞吐量大到单个节点无法承受时，分片可以把数据和写入分散到多个节点上。（如果瓶颈是读取吞吐量，则未必需要分片，可以采用 第 6 章 介绍的 读扩展，read scaling。）

事实上，分片是实现 水平扩展（horizontal scaling，也称 横向扩展，scale-out 架构）的主要手段之一，正如 “共享内存、共享磁盘与无共享架构” 所述：系统不必换用更大的机器，而是通过增加更多（较小的）机器来扩充容量。如果能合理划分工作负载，让每个分片承担大致相等的份额，就可以把这些分片分配给不同机器，并行处理其中的数据和查询。

复制可以提供容错和离线运行能力，因而无论规模大小都有用；分片却是一种重量级方案，主要适用于大规模场景。如果数据量和写入吞吐量仍可由单台机器处理（如今单机的能力可不容小觑！），通常最好避免分片，坚持使用单分片数据库。

之所以这样建议，是因为分片往往会增加复杂性。通常需要选择一个 分区键（partition key），据此决定每条记录应放入哪个分片；分区键相同的记录都会进入同一分片 ⁴。这个选择十分重要：如果知道记录在哪个分片，访问就很快；如果不知道，就只能低效地搜索所有分片，而且日后很难更改分片方案。

因此，分片通常很适合键值数据，因为可以直接按键分片；关系数据则比较棘手，因为你可能需要通过二级索引搜索，或连接散落在不同分片中的记录。我们将在 “分片与二级索引” 中进一步讨论这个问题。

分片还有一个问题：一次写入可能需要更新多个不同分片中的相关记录。单节点事务相当普遍（参见 第 8 章），但要保证多个分片之间的一致性，就需要 分布式事务（distributed transaction）。正如 第 8 章 将要说明的，有些数据库支持分布式事务，但这类事务通常比单节点事务慢得多，可能成为整个系统的瓶颈；还有些系统根本不支持分布式事务。

有些系统甚至会在单台机器上使用分片，通常是在每个 CPU 核心上运行一个单线程进程，以利用 CPU 的并行能力；或者利用 非一致性内存访问（NUMA）架构，因为其中某些内存区域离特定 CPU 比其他 CPU 更近 ⁵。例如，Redis、VoltDB 和 FoundationDB 都采用每个核心一个进程的方式，并依靠分片把负载分摊到同一台机器的各个 CPU 核心上 ⁶。

面向多租户的分片

软件即服务（SaaS）产品和云服务通常采用 多租户（multitenant）模式，每个租户对应一个客户。同一租户可以有多个用户账号，但每个租户拥有一份自成一体、与其他租户隔离的数据集。例如在电子邮件营销服务中，每家注册企业通常都是一个独立租户，因为各家企业的简报订阅信息、投递数据等彼此无关。

多租户系统有时通过分片来实现：可以为每个租户分配一个独立分片，也可以把多个小租户归入一个较大的分片。这些分片可以是物理上相互独立的数据库（我们曾在 “嵌入式存储引擎” 中提到），也可以是一个更大逻辑数据库中能够单独管理的组成部分 ⁷。用分片实现多租户有以下优点：

资源隔离

如果某个租户执行计算开销很大的操作，只要它与其他租户位于不同分片，其他租户的性能就不太容易受到影响。

权限隔离

如果访问控制逻辑存在漏洞，只要各租户的数据集在物理上彼此隔离，意外让一个租户访问另一租户数据的可能性就会降低。

单元化架构

分片不仅可以用在数据存储层，也可以用来划分运行应用代码的服务。在 单元化架构（cell-based architecture）中，为一组特定租户服务的应用与存储会组成一个自包含的 单元（cell），不同单元大体可以彼此独立地运行。这种方法能够实现 故障隔离（fault isolation）：一个单元里的故障只影响该单元，不会殃及其他单元中的租户 ⁸。

按租户备份和恢复

分别备份每个租户的分片，就能从备份中恢复某个租户的状态，而不影响其他租户。租户意外删除或覆盖重要数据时，这一能力很有用 ⁹。

法规合规性

GDPR 等数据隐私法规赋予个人访问并删除关于自己的全部存储数据的权利。如果每个人的数据都存放在独立分片中，实现这一权利就只需对相应分片执行简单的数据导出和删除操作 ¹⁰。

数据驻留

如果数据驻留法规要求某个租户的数据必须存放在特定司法管辖区，那么区域感知数据库可以把该租户的分片分配到指定区域。

逐步推出模式变更

模式迁移（前文已在 “文档模型中的模式灵活性” 中讨论）可以逐步推出，每次只迁移一个租户。这样能在问题波及所有租户之前将其发现，从而降低风险，不过很难以事务方式完成 ¹¹。

使用分片实现多租户的主要挑战是：

• 这种做法假定每个租户的数据量都足够小，能装进单个节点。如果某个租户大到一台机器容纳不下，就还得在租户内部继续分片，于是问题又回到了为了可伸缩性而分片 ¹²。
• 如果小租户很多，为每个租户单独建立分片的开销可能过大。可以把多个小租户合并到一个较大的分片里，但随着租户成长，又会遇到如何把它从一个分片迁移到另一个分片的问题。
• 如果日后需要支持跨租户关联数据的功能，那么跨多个分片连接数据会使这些功能更难实现。

键值数据的分片

假设你有大量数据并且想要分片，如何决定在哪些节点上存储哪些记录呢？

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

如果分片不公平，某些分片承载的数据或查询比其他分片更多，我们就称其为 倾斜（skew）。倾斜会大幅降低分片的效果。在极端情况下，全部负载都可能集中到一个分片上，10 个节点中有 9 个闲置，瓶颈却卡在唯一繁忙的节点上。负载高得不成比例的分片称为 热分片（hot shard）或 热点（hot spot）；如果某个键的负载特别高（例如社交网络中的名人账号），则称为 热键（hot key）。

因此，我们需要一种算法，以记录的分区键为输入，指出这条记录属于哪个分片。在键值存储中，分区键通常就是键或键的第一部分；在关系模型中，它可以是表中的某一列，不一定非得是主键。为了缓解热点，这种算法还必须便于再平衡。

按键的范围分片

一种分片方法，是为每个分片指定一段连续的分区键范围（从某个最小值到某个最大值），就像纸质百科全书的各卷，如 图 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（参见 第 4 章）。这样很容易执行范围扫描，也可以把键当作联合索引，在一次查询中获取多条相关记录（参见 “多维索引与全文索引”）。例如，某个应用程序存储传感器网络的数据，并以测量时间戳作为键；范围扫描在这里就非常有用，可以轻松取出某个月份的全部读数。

键范围分片的缺点是，如果大量写入集中在相邻的键上，很容易形成热分片。例如，键若是时间戳，分片就对应不同时间范围，比如每个月一个分片。遗憾的是，如果传感器在产生测量值时就立即写入数据库，所有写入都会落到同一个分片（本月的分片）中。结果该分片可能被写入压垮，其他分片却无所事事 ¹³。

为了避免传感器数据库出现这个问题，键的第一部分就不能只用时间戳。例如，可以在每个时间戳前加上传感器 ID，使键先按传感器 ID、再按时间戳排序。只要有许多传感器同时工作，写入负载就会更均匀地分布到各个分片。代价是，要获取多个传感器在某段时间内的测量值，现在必须为每个传感器分别执行一次范围查询。

再平衡键范围分片数据

首次建立数据库时，还没有数据可供划定键范围。一些数据库（如 HBase 和 MongoDB）允许在空数据库上配置一组初始分片，这称为 预拆分（pre-splitting）。采用这种办法，必须事先大致了解键将如何分布，才能选出合适的键范围边界 ¹⁴。

此后，随着数据量和写入吞吐量增长，采用键范围分片的系统会把现有分片拆成两个或更多较小分片，每个新分片都保存原键范围中的一段连续子范围；这些较小的分片随后可以分散到多个节点上。如果大量数据被删除，几个相邻且已经变小的分片也可能需要合并成一个较大的分片。这个过程类似于 B 树顶层发生的变化（参见 “B 树”）。

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

• 分片达到配置的大小（例如 HBase 默认为 10 GB）；或者
• 在某些系统中，写入吞吐量持续高于某个阈值。因此，即使一个热分片存储的数据不多，也可能被拆分，以便将其写入负载分布得更加均匀。

键范围分片的优点是，分片数量能够随数据量调整。数据很少时，只需少量分片，开销也很小；数据量巨大时，每个分片的大小仍会被限制在可配置的上限之内 ¹⁵。

这种方法的缺点是，拆分分片代价很高：必须把其中的全部数据重写到新文件里，类似于日志结构存储引擎的压实操作。需要拆分的分片往往本就处于高负载，拆分开销还会雪上加霜，甚至使它彻底过载。

按键的哈希分片

如果希望相邻（但不同）的分区键进入同一个分片，键范围分片就很有用，时间戳便是一个例子。如果不关心分区键是否相邻（例如多租户应用中的租户 ID），常见做法是先计算分区键的哈希值，再将它映射到分片。

好的哈希函数可以把倾斜的数据均匀打散。假设有一个接受字符串输入的 32 位哈希函数，每输入一个新字符串，它都会返回一个看似随机、介于 0 和 2³² − 1 之间的数。即使输入字符串非常相似，所得哈希值也会均匀分布在这个范围内（不过相同输入总会产生相同输出）。

用于分片的哈希函数不必具备密码学强度：例如 MongoDB 使用 MD5，Cassandra 和 ScyllaDB 则使用 Murmur3。许多编程语言都内置了用于哈希表的简单哈希函数，但它们未必适合分片。例如，Java 的 Object.hashCode() 和 Ruby 的 Object#hash 可能会让同一个键在不同进程中得到不同哈希值，因此不能用于分片 ¹⁶。

哈希取模节点数

算出键的哈希值之后，该如何选择存储它的分片？你首先想到的也许是让哈希值对系统中的节点数 取模（许多编程语言使用 % 运算符）。例如，hash(key) % 10 会返回 0 到 9 之间的数；如果把哈希值写成十进制，hash % 10 就是它的末位数字。假设有 10 个节点，编号为 0 到 9，这似乎是把键分配到节点的简单办法。

模 N 方法的问题在于，只要节点数 N 发生变化，大多数键就必须从一个节点移到另一个节点。图 7-3 展示了三个节点增加到四个时的情况。再平衡之前，节点 0 存储哈希值为 0、3、6、9 等的键；加入第四个节点之后，哈希值为 3 的键移到节点 3，哈希值为 6 的键移到节点 2，哈希值为 9 的键移到节点 1，依此类推。

模 N 很容易计算，却会导致极其低效的再平衡，因为大量记录在节点之间进行了不必要的迁移。我们需要一种只移动必要数据的办法。

固定数量的分片

一种简单而常用的解决方案，是创建远多于节点数的分片，再给每个节点分配多个分片。例如，一个运行在 10 节点集群上的数据库可以从一开始就划分成 1,000 个分片，每个节点分得 100 个。键会存入编号为 hash(key) % 1,000 的分片，而系统另行记录每个分片存放在哪个节点上。

如果向集群加入一个节点，系统可以把现有节点上的一部分分片重新分配给新节点，直到分片再次均匀分布。图 7-4 展示了这一过程。移除节点时，则反向执行同样的操作。

在这种模型中，只有完整的分片在节点之间移动，成本低于拆分分片。分片的数量不会改变，键所指定的分片也不会改变；唯一改变的是分片所在的节点。这种变更并非即时——在网络上传输大量数据需要时间——所以传输期间发生的读写，仍按原有的分片到节点映射处理。

分片数量通常会选成一个因数很多的数字，使数据集能够均匀分配到多种不同规模的节点集群中，例如不必要求节点数是 2 的幂 ⁴。甚至还可以照顾集群中的硬件差异：给性能更强的节点分配更多分片，让它们承担更大比例的负载。

Citus（PostgreSQL 的分片层）、Riak、Elasticsearch 和 Couchbase 等系统都采用这种分片方法。只要首次创建数据库时能较准确地估计所需分片数，它就很好用：此后可以轻松增删节点，不过节点数不能超过分片数。

如果发现最初配置的分片数不合适——例如系统规模已经大到所需节点数超过分片数——就必须执行代价高昂的重新分片。这个过程要拆开每个分片、写出新文件，并占用大量额外磁盘空间。有些系统不允许在数据库继续接受写入时重新分片，因此很难在不停机的情况下改变分片数量。

如果数据集总量变化很大（例如开始时很小，随后可能增长许多倍），选择合适的分片数就很困难。由于每个分片包含总数据量的固定比例，其大小会随集群中的数据总量同比增长。分片太大，再平衡和从节点失效中恢复都会十分昂贵；分片太小，又会带来过多管理开销。分片大小不大不小、“恰到好处”时性能最佳，但在分片数固定而数据集大小不断变化时，这一状态很难维持。

按哈希范围分片

如果无法事先预测需要多少分片，最好采用一种能让分片数量轻松适应工作负载的方案。前述键范围分片具备这一性质，但大量写入集中到相邻键时容易形成热点。一种解决办法是将键范围分片与哈希函数结合，使每个分片包含一段 哈希值 范围，而不是一段 键 范围。

图 7-5 展示了一个 16 位哈希函数，它会返回 0 到 65,535 = 2¹⁶ − 1 之间的数（实际使用的哈希通常至少有 32 位）。即使输入键十分相似（例如连续的时间戳），它们的哈希值也会均匀分布在这个范围内。于是，可以为每个分片分配一段哈希值范围：例如 0 到 16,383 归分片 0，16,384 到 32,767 归分片 1，依此类推。

与键范围分片一样，哈希范围分片也可以在分片过大或负载过重时将其拆分。这个操作依然昂贵，但可以按需执行，因此分片数量会随数据量调整，而不是预先固定不变。

它相对于键范围分片的缺点，是无法高效地对分区键执行范围查询，因为范围内的键如今散布在所有分片中。不过，如果键由两列或更多列组成，而分区键只是其中第一列，仍然可以对第二列及之后的列高效执行范围查询：只要范围查询中的所有记录拥有相同分区键，它们就会落在同一个分片中。

YugabyteDB 和 DynamoDB 采用哈希范围分片 ¹⁷，MongoDB 也把它作为一种可选方案。Cassandra 和 ScyllaDB 则采用这种方法的一个变体，如 图 7-6 所示：它们把哈希值空间划分成若干范围，范围数与节点数成正比（图 7-6 中每个节点有 3 个范围；实际默认值是 Cassandra 每个节点 8 个、ScyllaDB 每个节点 256 个），各范围之间的边界随机选定。这样有些范围会比其他范围大，但每个节点拥有多个范围之后，这些不均衡往往能相互抵消 ^{15 18}。

添加或移除节点时，系统会相应增删范围边界，并拆分或合并分片 ¹⁹。在 图 7-6 的例子中，加入节点 3 之后，节点 1 把自己两个范围中的一部分交给节点 3，节点 2 也把一个范围中的一部分交给节点 3。这样，新节点便能分得大致公平的一份数据，同时避免在节点间传输不必要的数据。

一致性哈希

一致性哈希（consistent hashing）算法是一种哈希函数，它把键映射到指定数量的分片，并满足两个性质：

1. 映射到各个分片的键数大致相等；
2. 分片数量改变时，尽可能少地在分片之间迁移键。

注意，这里的 一致性 与副本一致性（参见 第 6 章）或 ACID 一致性（参见 第 8 章）毫无关系；它描述的是让一个键尽量留在原分片中的倾向。

Cassandra 和 ScyllaDB 的分片算法与一致性哈希的原始定义相似 ²⁰，此外还有人提出了多种其他一致性哈希算法 ²¹，例如 最高随机权重（highest random weight，也称 约会哈希，rendezvous hashing）²² 和 跳跃一致性哈希（jump consistent hash）²³。采用 Cassandra 的算法时，加入一个节点会把少量现有分片拆成若干子范围；采用约会哈希或跳跃一致性哈希时，新节点得到的则是此前散布在所有其他节点上的一个个键。哪种方式更合适，取决于具体应用。

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

一致性哈希可以保证键大致均匀地分布到各节点，却不能保证实际负载也同样均匀。如果工作负载高度倾斜——也就是某些分区键下的数据量远大于其他键，或者某些键的请求速率远高于其他键——仍然可能有些服务器不堪重负，另一些服务器却几乎闲置。

例如在社交媒体网站上，一个拥有数百万粉丝的名人做出某个举动，可能引发一场活动风暴 ²⁴，进而产生针对同一个键的大量读写（分区键也许是该名人的用户 ID，也许是众人正在评论的事件 ID）。

这种情况需要更加灵活的分片策略 ^{25 26}。如果系统按键范围（或哈希范围）定义分片，就可以把一个热键单独放进一个分片，甚至给它分配一台专用机器 ²⁷。

也可以在应用层补偿倾斜。例如，如果已知某个键非常热，一种简单办法是在键的开头或末尾添加随机数。只需两位十进制随机数，就能把针对该键的写入均匀拆成 100 个不同的键，让它们分布到不同分片。

不过，写入分散到不同键之后，读取就得付出额外代价：必须从全部 100 个键读取数据，再把结果合并起来。热键分散后，每个分片承受的读取量并没有减少，降低的只有写入负载。这种技术还需要额外的记录工作：只有少数热键值得添加随机数；对于写入吞吐量很低的绝大多数键，这样做只会徒增开销。因此，还需要记录哪些键已被拆分，并设计一个流程，把普通键转换成需要特殊管理的热键。

负载还会随时间变化，使问题更加复杂。例如，某条突然爆火的社交媒体帖子可能连续几天承受很高负载，之后又很快归于平静。此外，有些键是写入热点，有些则是读取热点，二者需要采用不同的处理策略。

一些系统（尤其是面向大规模场景设计的云服务）能够自动处理热分片；例如，Amazon 把相关机制称为 热度管理（heat management）²⁸ 或 自适应容量（adaptive capacity）¹⁷。这些系统的具体工作方式超出了本书的讨论范围。

运维：自动/手动再平衡

关于再平衡有一个此前略过的重要问题：自动还是手动进行？

有些系统无需人工介入，会自动决定何时拆分分片、何时把分片从一个节点迁移到另一个节点；另一些系统则要求管理员显式配置分片。两者之间也有折中方案：例如，Couchbase 和 Riak 会自动生成建议的分片分配，但必须由管理员确认提交后才会生效。

全自动再平衡很方便，因为日常维护所需的运维工作更少；这样的系统甚至可以自动伸缩，以适应工作负载的变化。DynamoDB 等云数据库宣称，能够在几分钟内自动增删分片，应对负载的大幅升降 ^{17 29}。

然而，自动分片管理也可能难以预测。再平衡代价很高，因为它要重新路由请求，并在节点间迁移大量数据。如果处理不够谨慎，这一过程可能使网络或节点过载，拖累其他请求的性能。系统在再平衡期间还必须继续处理写入；如果已经接近最大写入吞吐量，分片拆分的速度甚至可能赶不上新写入到达的速度 ²⁹。

这种自动化机制如果再与自动失效检测结合，可能十分危险。假设某个节点过载，暂时无法及时响应请求；其他节点据此断定它已经失效，于是自动对集群进行再平衡，把负载从该节点移走。这会给其他节点和网络施加额外负载，让局面进一步恶化，甚至引发级联失效：其他节点也相继过载，并被错误地判定为已经宕机。

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

请求路由

我们已经讨论了如何把数据集分片到多个节点，以及如何在增删节点时再平衡这些分片。现在来看下一个问题：如果想读写某个特定的键，怎样知道应该连接哪个节点——也就是哪个 IP 地址和端口？

这个问题称为 请求路由（request routing），与前文 “负载均衡器、服务发现和服务网格” 讨论的 服务发现（service discovery）十分相似。二者最大的区别在于：运行应用代码的服务实例通常是无状态的，负载均衡器可以把请求发给任意实例；而在分片数据库中，某个键的请求只能交给持有该键所在分片副本的节点处理。

因此，请求路由必须了解键到分片、以及分片到节点的映射。概括来说，有以下几种办法（如 图 7-7 所示）：

1. 允许客户端连接任意节点（例如通过轮询负载均衡器）。如果该节点恰好持有请求涉及的分片，就直接处理请求；否则，它把请求转发给正确的节点，收到响应后再转交给客户端。
2. 客户端的所有请求都先发送到一个路由层，由路由层判断哪个节点应当处理每个请求，再相应地转发。路由层本身并不处理请求，只充当一个能够感知分片的负载均衡器。
3. 让客户端了解分片方式以及分片到节点的分配关系。这样，客户端无须经过任何中间层，就能直接连接到正确的节点。

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

• 由谁决定每个分片应当放在哪个节点？最简单的办法是由单一协调者来决定，但如果运行协调者的节点宕机，怎样让协调者具备容错能力？如果协调者能够故障切换到另一个节点，又该如何防止发生脑裂（参见 “处理节点故障”），让两个协调者作出相互矛盾的分片分配？
• 负责路由的组件（可以是某个数据库节点、路由层或客户端）怎样得知分片到节点的分配发生了变化？
• 分片从一个节点迁移到另一个节点时，会有一段切换期：新节点已经接管，但发往旧节点的请求可能仍在途中。应当如何处理这些请求？

许多分布式数据系统依靠 ZooKeeper、etcd 等独立协调服务来记录分片分配，如 图 7-8 所示。这些服务使用共识算法（参见 第 10 章）实现容错并防止脑裂。每个节点都在 ZooKeeper 中注册，ZooKeeper 维护分片到节点的权威映射；路由层或能够感知分片的客户端等其他参与者，可以订阅 ZooKeeper 中的信息。只要分片易主，或有节点加入、退出，ZooKeeper 就会通知路由层，使其路由信息保持最新。

例如，HBase 和 SolrCloud 使用 ZooKeeper 管理分片分配，Kubernetes 使用 etcd 记录每个服务实例的运行位置。MongoDB 的架构与之相似，不过它依靠自有的 配置服务器（config server）实现，并以 mongos 守护进程作为路由层。Kafka、YugabyteDB 和 TiDB 则使用内置的 Raft 共识协议实现这项协调功能。

Cassandra、ScyllaDB 和 Riak 采用另一种办法：节点之间通过 流言协议（gossip protocol）传播集群状态的变化。它提供的一致性比共识协议弱得多，因而可能出现脑裂，使集群的不同部分对同一个分片持有不同的节点分配。无主数据库可以容忍这种情况，因为它们本就只提供较弱的一致性保证（参见 “仲裁一致性的局限”）。

无论使用路由层还是把请求发送给随机节点，客户端仍然要先找到可供连接的 IP 地址。IP 地址的变化没有分片到节点的分配那么频繁，因此通常用 DNS 就足够了。

以上请求路由主要关注如何为单个键找到对应分片，这最适用于分片的 OLTP 数据库。分析型数据库通常也会分片，但其查询执行方式截然不同：查询一般不是在单个分片中执行，而是要并行聚合并连接来自许多分片的数据。我们将在 “JOIN 与 GROUP BY” 中讨论这类并行查询执行技术。

分片与二级索引

到目前为止讨论的分片方案，都要求客户端知道待访问记录的分区键。这在键值数据模型中最容易做到：分区键是主键的第一部分（或整个主键），因此可以据此确定分片，并把读写请求路由到负责该键的节点。

涉及二级索引时，情况会复杂得多（另见 “多列索引与二级索引”）。二级索引通常不能唯一标识一条记录，而是用来搜索某个特定值出现在哪里：例如，查找用户 123 的所有操作、所有包含单词 hogwash 的文章，或所有颜色为 red 的汽车。

键值存储通常没有二级索引，但它是关系数据库的基础能力，在文档数据库中也十分常见，更是 Solr、Elasticsearch 等全文检索引擎的 立身之本。二级索引的问题在于，它无法干净利落地映射到分片。对带有二级索引的数据库进行分片，主要有两种办法：本地索引和全局索引。

本地二级索引

假设你正在运营一个二手车交易网站（如 图 7-9 所示）。每条车辆信息都有唯一 ID，并以该 ID 作为分区键进行分片（例如，ID 0 到 499 归分片 0，ID 500 到 999 归分片 1，依此类推）。

如果要让用户搜索车辆，并按颜色与品牌筛选，就需要在 color 和 make 上建立二级索引（在文档数据库中它们是字段，在关系数据库中则是列）。声明索引后，数据库会自动维护它。例如，每增加一辆红色汽车，所在分片就会自动把它的 ID 加入索引条目 color:red 对应的 ID 列表。正如 第 4 章 所述，这种 ID 列表也称为 倒排列表（postings list）。

在这种索引方式中，每个分片都完全独立：各自维护自己的二级索引，只覆盖本分片中的记录，而不关心其他分片保存了什么数据。每次写入数据库——添加、删除或更新记录——只需处理包含该记录的分片。因此，这种二级索引称为 本地索引（local index）；在信息检索领域，它也称为 按文档分区的索引（document-partitioned index）³⁰。

读取本地二级索引时，如果已经知道目标记录的分区键，就只需在对应分片上搜索。如果只想获得 部分 结果而不要求全部，也可以把请求发给任意分片。

但是，如果需要全部结果，又事先不知道这些记录的分区键，就必须把查询发送到所有分片，再合并返回结果，因为匹配的记录可能散布在每个分片中。在 图 7-9 中，分片 0 和分片 1 都有红色汽车。

这种查询分片数据库的方式，会让二级索引上的读取查询变得相当昂贵。即使并行查询所有分片，也很容易出现尾部延迟放大（参见 “响应时间指标的应用”）。它还会限制应用的可伸缩性：增加分片能容纳更多数据，但如果每次查询仍要由所有分片处理，查询吞吐量并不会随之提高。

尽管如此，本地二级索引依然应用广泛 ³¹：MongoDB、Riak、Cassandra ³²、Elasticsearch ³³、SolrCloud 和 VoltDB ³⁴ 都采用这种索引。

全局二级索引

除了让每个分片各自维护本地二级索引，也可以构建一个覆盖所有分片数据的 全局索引（global index）。不过，不能只把这个索引存放在单个节点上，否则它很可能成为瓶颈，使分片失去意义。因此全局索引本身也必须分片，但可以采用与主键索引不同的分片方式。

图 7-10 展示了它可能采用的形式：来自所有分片的红色汽车 ID 都列在索引的 color:red 条目下；索引本身则经过分片，以字母 a 到 r 开头的颜色归分片 0，以 s 到 z 开头的颜色归分片 1。汽车品牌索引也以类似方式分片，边界位于 f 与 h 之间。

这种索引也称为 按词项分区（term-partitioned）³⁰。回顾 “全文检索”：在全文检索中，词项（term）是文本中可供搜索的关键字；这里我们把它推广为二级索引中任何可供搜索的值。

全局索引以词项作为分区键，因此查找某个词项或值时，可以直接确定需要查询哪个分片。和前面一样，每个分片可以包含一段连续的词项范围（如 图 7-10 所示），也可以根据词项的哈希值把词项分配到各个分片。

全局索引的优点是，如果查询只有一个条件（如 color = red），只需读取一个分片就能取得倒排列表。不过，如果想要的不只是 ID，而是完整记录，仍需读取负责存储这些 ID 的所有分片。

如果查询包含多个条件或词项（例如搜索某种颜色且属于某个品牌的汽车，或搜索同一段文本中同时出现的多个单词），这些词项很可能分属不同分片。为了计算两个条件的逻辑 AND，系统必须找出同时出现在两个倒排列表中的 ID。倒排列表较短时并不难；但如果列表很长，通过网络传输它们再计算交集，速度就可能很慢 ³⁰。

全局二级索引的另一个难题，是写入比本地索引复杂：写入一条记录可能影响索引的多个分片（文档中的每个词项都可能位于不同分片）。因此，二级索引很难与底层数据保持同步。一种办法是使用分布式事务，以原子方式更新保存主记录的分片及其二级索引分片（参见 第 8 章）。

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

总结

在本章中，我们探讨了将大数据集划分成更小子集的不同方法。数据量非常大的时候，在单台机器上存储和处理不再可行，而分片则十分必要。

分片的目标是在多台机器上均匀分布数据和查询负载，避免出现热点（负载不成比例的节点）。这需要选择适合数据的分片方案，并在将节点添加到集群或从集群删除时重新平衡分片。

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

• 键范围分片：键按顺序排列，每个分片拥有从某个最小值到某个最大值之间的所有键。有序存储的优点是能够高效执行范围查询，但如果应用经常访问排序位置彼此接近的键，就可能形成热点。

  采用这种方法时，分片过大之后通常会把键范围拆成两个子范围，从而动态地再平衡分片。

• 哈希分片：先对每个键应用哈希函数，每个分片拥有一段哈希值范围（也可以采用其他一致性哈希算法，把哈希映射到分片）。这种方法破坏了键的顺序，使范围查询效率降低，却可能让负载分布得更加均匀。

  按哈希分片时，通常会预先创建固定数量的分片，给每个节点分配多个分片；增删节点时，再把整个分片从一个节点迁移到另一个节点。也可以像键范围分片那样拆分分片。

常见做法是以键的第一部分作为分区键（即用来确定分片），再按键的其余部分对分片内的记录排序。这样，对于分区键相同的记录，仍然可以高效执行范围查询。

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

• 本地二级索引：二级索引与主键及其值存储在同一个分片。因此写入时只需更新一个分片，但查找二级索引时必须读取所有分片。
• 全局二级索引：根据索引值采用另一套分片方式。二级索引条目可以引用来自主键任意分片的记录。写入记录时，可能需要更新多个二级索引分片；但读取倒排列表时，只需访问一个分片（获取实际记录仍然要读取多个分片）。

最后，我们讨论了如何把查询路由到正确的分片，以及如何通过协调服务记录分片到节点的分配关系。

从设计上说，每个分片大体独立运行——正因如此，分片数据库才能伸缩到多台机器。然而，需要写入多个分片的操作会变得很棘手：例如，一个分片写入成功，另一个分片却失败时会怎样？我们将在接下来的章节中回答这个问题。

参考文献