第 7 章 分片

显然，我们必须打破顺序的束缚，不让计算机受其限制。我们必须给出定义、给出优先级和数据描述，必须陈述关系，而不仅仅是过程。

—— Grace Murray Hopper，《管理与未来计算机》（1962）

分布式数据库通常以两种方式把数据分散到节点上：

• 把同一份数据的副本存到多个节点上。这就是复制（replication），见第 6 章。
• 当数据量或写入吞吐量大到单节点装不下时，把数据切成更小的分片（shard，又叫 partition），分别存到不同节点上。本章讨论的就是分片。

通常分片的定义是：每条数据（每条记录、每行或每份文档）都恰好属于某一个分片。具体的实现方式有很多，本章会一一讨论。实际上每个分片就相当于一个小型数据库，尽管某些数据库系统也支持跨多个分片的操作。

分片常常与复制搭配使用：每个分片的副本会保存在多个节点上。也就是说，虽然每条记录只属于一个分片，但出于容错考虑，它仍可能存放在好几台不同的机器上。

一个节点可以存放多个分片。在采用单主复制模型时，分片与复制的组合可能长得像图 7-1：每个分片的主节点在某个节点上，从节点在其他节点上。每个节点对一部分分片来说是主节点，对另一部分则是从节点，但每个分片始终只有一个主节点。

图 7-1. 把复制和分片结合：每个节点都是某些分片的主节点、其他分片的从节点。

图示文字描述： Sharding 与 Partitioning 本章里我们称为分片（shard）的东西，在不同软件里叫法五花八门：Kafka 里叫 partition；CockroachDB 里叫 range；HBase 与 TiDB 里叫 region；Couchbase 里叫 vBucket；Riak 里叫 vnode；Cassandra 里叫 token-range；Bigtable、YugabyteDB 与 ScyllaDB 里叫 tablet——不一而足。 有些数据库把 partition 与 shard 当作两个不同概念。例如 PostgreSQL 中的 partitioning 是把一张大表拆成多个文件、但仍存放在同一台机器上（这能带来不少好处，例如让"整段删除"非常快），而 sharding 则是把数据集拆分到多台机器上 [1, 2]。在许多其他系统里，partitioning 不过是 sharding 的另一种说法而已。 Partitioning 一词相当形象，sharding 这个词的来历则有点出乎意料。一种说法是它源自在线角色扮演游戏《Ultima Online》：游戏中一颗魔法水晶被击碎，每一块碎片（shard）都折射出整个游戏世界的一个副本 [3]。于是 shard 就成了一组并行游戏服务器中的一员，后来这个词被沿用到数据库领域。另一种说法是它最初是 System for Highly Available Replicated Data 的首字母缩写——据说是 1980 年代的某种数据库，细节已不可考。 顺带一提，partitioning 与网络分区（network partition，netsplit）毫无关系，后者是节点间网络的一种故障形态，第 9 章会讨论。 第 6 章讲到的复制内容同样适用于分片的复制。由于分片方案的选择与复制方案的选择基本相互独立，本章为简洁起见就不再涉及复制。

分片的优劣

数据库分片的首要理由是可扩展性。当数据量或写入吞吐量大到单节点扛不住时，分片就是一种可行方案——把数据与写入分散到多个节点上。（如果瓶颈只是读吞吐量，未必需要分片——可以采用第 6 章讨论过的读扩展。）

实际上，正如第 51 页"共享内存、共享磁盘与无共享架构"所述，分片是实现水平扩展（横向扩展架构）的主要工具之一——也就是不靠换上更大的机器，而是靠多加几台（更小的）机器来扩容。只要能把工作切分开来、让每个分片承担大致相当的份额，就可以把这些分片分到不同机器上，让它们并行处理各自的数据和查询。

复制无论规模大小都有用，因为它能实现容错与离线运行。而分片是一种相对"重"的方案，通常只有在大规模时才必要。如果数据量与写入吞吐量单台机器就能扛得住（如今单机的能力不容小觑），通常就应该避免分片，坚持用单分片数据库。

之所以这么建议，是因为分片会带来复杂度。通常你要为每条记录决定它落到哪个分片——这是通过选择分片键（partition key）来完成的；具有相同分片键的所有记录都放在同一个分片中 [4]。这个选择很关键：知道某条记录在哪个分片，访问就很快；否则就只能在所有分片上做一次低效搜索。分片方案本身也很难改动。

对键值数据来说分片通常效果很好——按键分片再自然不过；但对关系型数据就棘手得多：你可能要按二级索引搜索，或者去连接（join）那些散落在不同分片上的记录。第 268 页"分片与二级索引"会详细讨论。

分片的另一个问题是：一次写入可能要同时更新多个分片里的相关记录。单节点上的事务相当常见，但要在多个分片之间保证一致性就需要分布式事务。正如第 8 章会看到的，部分数据库提供分布式事务，但通常比单节点事务慢得多，可能成为整个系统的瓶颈。

也有一些系统即便在单机上也使用分片，通常是每个 CPU 核跑一个单线程进程，以此利用 CPU 的并行能力，或者利用非一致性内存访问（NUMA）架构——某些内存"段"离某个 CPU 更近 [5]。例如 Redis、VoltDB 和 FoundationDB 都给每个核分配一个进程，靠分片把负载分散到同机器的多个 CPU 核上 [6]。

多租户的分片

软件即服务（SaaS）产品和云服务通常是多租户的——每个租户对应一个客户。多名用户可能登录同一租户的账号，但每个租户都有自己独立、与其他租户隔离的数据集。例如在一家邮件营销服务里，每家注册企业通常就是一个独立租户：每家企业的订阅者、投递数据等都与其他企业相互分离。

有时人们会用分片来实现多租户系统：要么给每个租户一个独立分片，要么把多个小租户合到一个更大的分片里。这些分片可能是物理上独立的数据库（前面第 125 页"嵌入式存储引擎"提到过），也可能是同一个逻辑数据库内可分别管理的若干部分 [7]。用分片做多租户有以下几方面好处：

资源隔离

如果某租户跑了一项计算量很大的操作，只要它和其他租户跑在不同分片上，就不太会影响其他租户的性能。

权限隔离

万一访问控制逻辑里有 bug，把不同租户的数据放在物理上隔离的分片中，能降低把某租户的数据误暴露给另一租户的可能性。

单元化架构

不仅数据存储层可以分片，跑应用代码的服务也可以分片。在单元化架构（cell-based architecture）里，特定一组租户的服务与存储会被组合成一个自包含的单元（cell），不同单元之间设置为基本独立运行。这种架构提供了故障隔离：单元内的故障被限制在该单元里，其他单元里的租户不会受影响 [8]。

按租户备份与恢复

为每个租户分别备份分片，就能在不影响其他租户的情况下从备份恢复某租户的状态——租户误删或误覆盖重要数据时，这一点尤其有用 [9]。

合规

GDPR 与 CCPA 等数据隐私法规赋予个人访问企业为其存储的个人信息、要求删除等权利。如果每个人的数据都存在独立分片中，导出和删除操作就只针对该分片，相对简单 [10]。

数据驻留

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

渐进式模式发布

模式迁移（第 80 页"文档模型中的模式灵活性"讨论过）可以一次只在一个租户上滚动发布，从而降低风险——问题在波及所有租户之前就能发现，只是这种方式难以以事务方式完成 [11]。

把分片用于多租户的主要挑战如下：

• 它假定每个租户都小到能塞进单节点。如果某个租户大到单机装不下，就还得在该租户内部做分片，于是又回到为可扩展性而分片这个话题 [12]。
• 如果小租户很多，给每个租户都建一个独立分片可能开销过大。可以把多个小租户合并到一个大分片里，但那样又要面对一个新问题：租户增长起来后该如何在分片之间迁移它们。
• 如果将来要支持跨多个租户连接数据的功能，跨分片 join 会让实现变得更难。

键值数据的分片

假设你有一大堆数据要分片：怎么决定哪些记录放到哪些节点上？

分片的目标是把数据与查询负载均匀地分散到节点上。如果每个节点都承担均等份额，10 个节点在理论上就能处理 10 倍于单节点的数据和读写吞吐量（暂不考虑复制）。增减节点时，你也希望能重新均衡（rebalance）负载，让它在新数量的节点上重新均匀分布。

如果分片不公平、有些分片比别的承载更多数据或查询，就称之为倾斜（skew）。倾斜会让分片的效果大打折扣。极端情况下，所有负载都落在一个分片上，10 个节点里 9 个空闲，瓶颈就是那个忙碌节点。承担过高负载的分片叫做热分片（hot shard）或热点（hot spot）。某个键负载特别高时（例如社交网络上的某位名人），就称为热键。

要把数据集切成分片，我们需要一个算法：以一条记录的分片键为输入，告诉我们它属于哪个分片。键值存储里的分片键通常就是键本身或键的开头部分。在关系模型里，分片键可以是表的某一列（不必是主键）。该算法还要支持再均衡，以便能够缓解热点。

按键范围分片

一种分片方法是：给每个分片分配一段连续的分片键范围（从最小到最大），就像纸质百科全书的卷次那样，见图 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 中 [6]。YugabyteDB 同时提供手动与自动两种 tablet 切分。

每个分片内部，键都按排序顺序存储（例如以 B 树或 SSTable，详见第 4 章）。这样的好处是范围扫描很简单，还可以把键当成联合索引，一次查询就拉出多条相关记录（见第 145 页"多维与全文索引"）。例如某个存储传感器网络数据的应用，键就是测量的时间戳——这种场景下范围扫描非常方便，能一次取出某个月的全部读数。

按键范围分片的一个缺点是：如果对相邻键有大量写入，很容易出现热分片。比如键是时间戳，分片就对应一段段时间范围（例如每月一片）；当数据按发生顺序写入时，所有写入都会涌向同一个分片（当月那一片）——它被写得满满当当，其他分片却闲着 [13]。

要在传感器数据库里避免这种情况，可以让键不以时间戳打头。例如在每个时间戳前加上传感器 ID，让键先按传感器 ID 排序、再按时间戳排序。假设同时活跃的传感器很多，写入负载就会被均匀分散到多个分片。代价是：要取某段时间内多个传感器的值时，得为每个传感器分别做一次范围查询。

按键范围分片数据的再均衡

数据库刚搭起来时，并没有现成的键范围可切。某些数据库（如 HBase 与 MongoDB）允许在空数据库上配置一组初始分片，这就叫预分片（pre-splitting）。这要求你对未来的数据分布已有大致估计，才能选出合适的键范围边界 [14]。

之后随着数据量和写入吞吐量增长，按键范围分片的系统会把已有分片切成两个或更多更小的子分片来扩张，每个子分片持有原分片键范围中的一段连续子范围。新生的小分片随后可分布到多个节点上。如果删除了大量数据，可能还需要把若干变小的相邻分片合并成更大的分片。这一过程与 B 树顶层发生的事情类似（见第 125 页"B 树"）。

自动管理分片边界的数据库通常会在分片达到预设大小时触发切分（例如 HBase 默认 10 GB）；某些系统则是在写入吞吐量持续高于某阈值时触发。这样即便热分片本身数据量不大，也可能被切开，让其写入负载更均匀地分散开。

如此一来，分片数量就能随数据量自适应：数据量小时少量分片就够，开销也低；数据量大时每个分片的大小都被限制在一个可配置的上限 [15]。

只可惜，切分一个分片代价不小：要把所有数据重写到新文件里，类似日志结构存储引擎中的 compaction。需要切分的分片往往本身就处于高负载之下，切分的额外开销会让它的负载雪上加霜，甚至把它推到过载边缘。

按键的哈希分片

如果你希望分片键相邻（但不同）的记录落到同一个分片——例如时间戳——按键范围分片就很有用。但如果你并不在乎分片键之间的邻近性（比如多租户应用里的租户 ID），常见做法是先把分片键哈希一下，再把哈希值映射到分片。

好的哈希函数能把倾斜的数据"均匀化"：例如一个 32 位哈希函数以字符串为输入，每给它一个新字符串都会返回一个看似随机、范围在 0 到 2³² − 1 之间的数字。即便输入字符串非常相近，它们的哈希值也会均匀分布在该数字范围内（同一输入则永远得到同一输出）。

用于分片的哈希函数不需要达到密码学强度：例如 MongoDB 用 MD5，Cassandra 与 ScyllaDB 用 Murmur3。许多编程语言都自带简单的哈希函数（用于哈希表），但它们未必适合做分片：例如 Java 的 Object.hashCode() 与 Ruby 的 Object#hash，同一个键在不同进程里可能给出不同的哈希值，因此不适合用于分片 [16]。

哈希值对节点数取模

把键哈希之后，怎么决定该存到哪个分片？最直觉的反应是：把哈希值对系统中的节点数取模（很多语言里就是 % 运算符）。例如 hash(key) % 10 会返回 0 到 9 之间的数字（哈希若写成十进制，hash % 10 就是末位数字）。如果有 10 个节点（编号 0 到 9），这看起来是种简便的分配方式。

mod N 方法的问题在于：节点数 N 一变，大多数键都得从一个节点搬到另一个节点。图 7-3 展示了从 3 个节点变成 4 个节点时的情形：原本节点 0 存放哈希为 0、3、6、9 的键，加入第四个节点后，哈希为 3 的键搬到节点 3，哈希为 6 的键搬到节点 2，哈希为 9 的键搬到节点 1，依此类推。

图 7-3. 通过对哈希取模分配键到节点。改变节点数会导致大量键迁移。 mod N 函数算起来简单，但它带来的再均衡极其低效——大量记录被毫无必要地在节点之间搬来搬去。我们需要一种尽量少搬数据的办法。

固定数量的分片

一个简单但被广泛采用的方案是：创建远多于节点数的分片，再给每个节点分配若干分片。例如在 10 节点的集群上运行的数据库，一开始就可以分成 1000 个分片，每个节点分到 100 个。键存到分片号 hash(key) % 1000 上，再由系统单独记录哪个分片在哪个节点上。

向集群中加入新节点时，系统可以从现有节点上拿出若干分片转给新节点，直到分布再次较为均衡为止。图 7-4 演示了这一过程。从集群中移除节点时则反过来做。

在这种模型里，节点之间只搬整片，比"切分分片"便宜。分片的数量不变，键到分片的分配也不变；变的只是分片到节点的映射。这种重新分配并非瞬时——通过网络搬大量数据要花时间——因此搬运过程中，分片到节点的旧分配仍用于读写。

图 7-4. 向带多分片的数据库集群中加入新节点。 通常会挑一个能被许多因数整除的分片数，好让数据集能均匀切到不同的节点数上——节点数并不要求是 2 的幂 [4]。你甚至可以照顾集群里的硬件不均：把更多分片分给更强的节点，让它们承担更大份额的负载。

Citus（PostgreSQL 的分片层）、Riak、Elasticsearch、Couchbase 等都采用了这种分片方法。只要你一开始就能较好地估计出需要多少分片，它就工作得很好。添加或删除节点也很方便，只要节点数不超过分片数。

要是发现最初配的分片数选错了——例如规模已经增长到节点数都比分片数多——就得做一次代价昂贵的重新分片（resharding）：把每个分片再切开、重写到新文件里，过程中要消耗大量额外磁盘空间。某些系统不允许在写入数据库的同时做重新分片，这让无停机改分片数变得困难。

如果数据集总规模变化很大（例如一开始很小、却可能涨得很大），选合适的分片数就更难。每个分片占数据总量的固定比例，因此分片大小会随着集群里数据总量按比例增长。分片很大时，再均衡和从节点故障中恢复都会变得很昂贵；分片太小，开销又会过高。性能最好的时候是分片大小"刚刚好"——不大不小——但在分片数固定、数据集大小却在变化时，这一点很难做到。

按哈希范围分片

如果所需的分片数没法事先预测，最好用一种能随工作负载自适应调整分片数的方案。前面讲过的按键范围分片就具备这一特点，但相邻键密集写入时容易产生热点。一种解法是把按键范围分片与哈希函数结合：让每个分片持有的是一段哈希值范围，而非键范围。

图 7-5 用一个 16 位哈希函数（实际中通常是 32 位甚至更大）演示了这一思路：返回值在 0 到 65535 之间。即便输入键非常相近（例如连续的时间戳），哈希值也会均匀分布在该范围内。然后给每个分片分配一段哈希值范围——例如把 0 到 16383 分给分片 0、16384 到 32767 分给分片 1，依此类推。

图 7-5. 把连续的哈希值范围分给每个分片。 与按键范围分片一样，按哈希范围分片时，分片变得过大或负载过高时也可以切分。这依旧是一项昂贵操作，但可按需进行，因此分片数量会随数据量自适应，而不必事先固定。

相较按键范围分片，这种方法的劣势在于分片键上的范围查询效率不高，因为该范围内的键已经散落到所有分片里。但如果键由两列或多列构成、分片键只是第一列，那么在第二及之后的列上仍可以做高效的范围查询。只要范围查询中的所有记录共享同一个分片键，它们就会落在同一个分片里。

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

BigQuery、Snowflake、Delta Lake 等数据仓库支持类似的索引方法，但术语不同。例如在 BigQuery 中，分区键决定记录落在哪个分区，"cluster columns" 决定记录在分区内如何排序；Snowflake 会自动把记录分配到"微分区"中，同时允许用户为表定义聚类键；Delta Lake 则同时支持手动和自动的分区分配，也支持聚类键。聚类不仅能改善范围扫描性能，还能改善压缩与过滤性能。

YugabyteDB 与 DynamoDB [17] 使用按哈希范围分片，MongoDB 也提供该选项。Cassandra 与 ScyllaDB 使用这种方法的一种变体，见图 7-6。

图 7-6. Cassandra 与 ScyllaDB 把可能的哈希值范围（这里 0–1024）切成若干带随机边界的连续段，并把若干段分配给每个节点。 哈希值空间被切成与节点数成比例的若干段（图中每节点 3 段；实际上 Cassandra 默认每节点 16 段，ScyllaDB 默认 256 段），段的边界是随机的。这意味着段与段之间大小不一，但因为每个节点拥有多段，不均衡会被拉平 [15]。

加入或移除节点时，范围边界会相应调整，分片随之切分或合并。例如图 7-6 中加入节点 3 时，节点 1 把自己两段中的一部分让给节点 3，节点 2 也把自己一段中的一部分让给节点 3。这样新节点能拿到大致公平的份额，又不必在节点之间多搬数据。

一致性哈希

一致性哈希算法是一类把键映射到指定数量分片的哈希函数，它满足两点性质：

• 映射到每个分片的键数大致相等。
• 分片数变化时，从一个分片迁移到另一个分片的键尽可能少。

注意这里的"一致"与副本一致性（见第 6 章）或 ACID 一致性（见第 8 章）无关，只是说"分片数变化时键尽量留在原处"这个性质。

Cassandra 与 ScyllaDB 用的分片算法接近一致性哈希的原始定义 [18]，但还有几种其他的一致性哈希算法，例如最高随机权重（又叫 rendezvous hashing）[19, 20] 和跳跃一致性哈希（jump consistent hashing）[21]。这些方法不再切分少量已有分片以腾出空位，而是把零散的键直接分配给新节点，而这些键原本散落在其他所有节点上。具体哪种更合适，得看应用而定。

倾斜负载与缓解热点

一致性哈希能让键均匀分布到节点上，但这并不意味着实际负载也均匀。一旦工作负载高度倾斜——某些分片键下的数据多得多，或某些键的请求率远高于其他键——某些服务器仍可能过载，而其他服务器几乎闲着。

例如，社交媒体上一位拥有数百万粉丝的名人发了一条动态，就可能引发流量风暴 [22]。这种情况会导致同一个键（分片键也许是名人的用户 ID，或被评论的动态 ID）上出现大量读写。

这种情形需要更灵活的分片策略 [23, 24]。按键范围（或哈希范围）来定义分片的系统让"把单个热键单独放在一个分片里、甚至给它分配一台专机"成为可能 [25]。

也可以在应用层补偿倾斜。例如已知某个键特别热时，一个简单技巧是给它加上随机前缀或后缀。仅加两位随机数，就能把对该键的写入分散到 100 个键上，进而分布到不同分片。

不过，把写入拆到多个键之后，读取就要多做事——要从全部 100 个键里读出来再合并。所读的数据量并没有减少，只是把写负载分摊开了。这种技巧还需要额外的簿记：只对少数热键加随机数才划算，对绝大多数写入很少的键而言只会带来不必要的开销。因此你还得记录哪些键被打散过，并能把"普通键"切换成"特别管理的热键"。

负载随时间变化让问题更复杂：一篇病毒式传播的帖子也许只在几天内承受异常高的负载，之后便归于平静。此外，有的键写很热、有的键读很热，要采用不同处理策略。

某些系统（尤其是为大规模而设计的云服务）已有自动化的办法处理热分片。例如亚马逊把它叫 heat management [26] 或 adaptive capacity [17]，具体怎么工作就超出本书范围了。

运维：自动 vs 手动再均衡

关于再均衡，我们一直回避了一个重要问题：分片的切分与移动是自动进行，还是手动进行？

某些系统会自动决定何时切分分片、何时把分片从一个节点搬到另一个节点，无需任何人为干预；另一些系统则要求管理员显式配置分片。中间地带也存在——例如 Couchbase 与 Riak 会自动生成建议的分片分配方案，但要管理员确认后才会生效。

全自动再均衡很方便：日常维护要做的运维事更少，这类系统甚至能根据负载自动伸缩。例如 DynamoDB 等云数据库宣传它们能在几分钟内自动加减分片，以应对负载的剧烈变化 [17, 27]。

但自动分片管理也可能难以预测。再均衡是一项昂贵操作，要重新路由请求，还要把大量数据从一个节点搬到另一个。一不小心就会让网络或节点过载，殃及其他请求。再均衡进行时系统必须继续接受写入；如果系统已经接近最大写入吞吐量，分片切分的速度甚至可能赶不上写入到来的速度 [27]。

这种自动化若再叠加自动故障检测就更危险了。设想某节点过载、一时响应变慢；其他节点判定它"已死"，自动再均衡把负载从它身上挪走。这给其他节点和网络带来更多压力，让情况更糟，可能引发级联失效——其他节点也变得过载、又被错误地判为下线。

因此，让人工参与再均衡反倒是好事：虽然比全自动慢，但能避免运维上的意外。预知流量会激增时（如黑五大促，或世界杯这类大型体育赛事的购票），也可以靠手动再均衡提前做预防性调整。

请求路由

前面已经讨论了如何把数据集分片到多个节点、节点加入或移出时如何再均衡分片。接下来的问题是：要读写某个键时，你怎么知道该连到哪个节点（即哪个 IP 和端口）？

我们把这个问题叫做请求路由（request routing），它与前面第 184 页"负载均衡器、服务发现与服务网格"中讨论的服务发现很相似。最大的区别在于：运行应用代码的服务每个实例通常都是无状态的，负载均衡器可以把请求发给任意实例；但对分片数据库而言，某个键的请求只能由持有该键所在分片副本的节点来处理。

这意味着请求路由必须知道键到分片、分片到节点的分配关系。整体上看，有三种做法（图 7-7）：

1. 让客户端连任意节点（例如经过轮询负载均衡器）。该节点若恰好持有目标分片就直接处理；否则把请求转发给合适的节点，等收到回复后再转回客户端。
2. 把所有请求先发到一个路由层，由它判定应由哪个节点处理并相应转发。这个路由层并不亲自处理请求，它就是一个分片感知的负载均衡器。
3. 要求客户端自己知道分片以及分片到节点的分配。这样客户端可以直接连到合适的节点，无需中间环节。

图 7-7. 把请求路由到正确节点的三种方式。 每种做法都有几个关键问题要解决：

• 由谁来决定哪个分片在哪个节点上？最简单的办法是设一个协调者，但运行协调者的机器一旦宕掉，怎么让它容错？协调者角色若能故障转移到其他节点，又怎么防止脑裂（见第 204 页"处理节点宕机"）让两个协调者做出互相矛盾的分配？
• 执行路由的组件（节点、路由层或客户端）如何得知分片到节点分配的变化？
• 分片从一个节点搬到另一个节点期间，会有一段切换期：新节点已经接管，但老节点上仍有没处理完的请求。这些怎么办？

许多分布式数据系统依赖独立的协调服务（如 ZooKeeper 或 etcd）来跟踪分片分配，如图 7-8。它们靠共识算法（见第 10 章）提供容错并抵御脑裂。每个节点把自己注册到 ZooKeeper，由 ZooKeeper 维护分片到节点的权威映射。其他角色——路由层或分片感知的客户端——可以订阅这些信息。一旦分片归属变化或有节点加入、移出，ZooKeeper 就通知路由层更新路由信息。

图 7-8. 用 ZooKeeper 跟踪分片到节点的分配。 例如，HBase 和 SolrCloud 用 ZooKeeper 管理分片分配，Kubernetes 用 etcd 跟踪服务实例的位置。MongoDB 架构类似，但用自家的 config server 实现，并把 mongos 守护进程当作路由层。Kafka、YugabyteDB、TiDB、ScyllaDB [28] 则用内置的 Raft 共识协议来做这件事。

Riak 走的是另一条路：节点之间用流言协议（gossip protocol）来传播集群状态的变化。这种一致性远弱于共识协议；可能出现脑裂——集群不同部分对同一分片的节点分配看法不一。无主数据库可以容忍这种情况，因为它们本就提供较弱的一致性保证（见第 233 页"理解 quorum 一致性的局限"）。

用路由层或把请求发给随机节点时，客户端仍需找到要连接的 IP 地址。这些地址不像分片到节点的分配那样多变，所以用 DNS 通常就够了。

到目前为止讨论的请求路由聚焦于为单个键找到对应分片，这与分片型 OLTP 数据库最为相关。分析型数据库也常常用分片，但查询执行模式通常截然不同：它一般不在单个分片内执行，而是要从许多分片并行地聚合并 join 数据。这类并行查询执行技术会在第 11 章讨论。

分片与二级索引

前面讨论的分片方案都假设客户端访问任何一条记录时都知道它的分片键。在键值数据模型里这最容易做到——分片键就是主键的第一部分（或者干脆就是主键本身），可以拿它确定分片，把读写路由到负责该键的节点。

一旦涉及二级索引（见第 132 页"多列索引与二级索引"），情况就复杂得多。二级索引通常并不唯一标识一条记录，而是用来查找某个特定值的所有出现：找用户 123 的所有动作，找包含单词 hogwash 的所有文章，找所有红色的车，等等。

键值存储常常没有二级索引，但二级索引在关系型数据库中是标配，在文档数据库里也很常见。这类索引正是 Solr、Elasticsearch 等全文搜索引擎存在的理由（raison d'être）。二级索引带来的麻烦是：它们和分片对应得不那么整齐。给带二级索引的数据库分片，主要有两种做法：本地与全局。

本地二级索引

第一种做法是：每个分片各自维护自己的二级索引，只覆盖该分片中的记录，不管其他分片中的数据。每当你写入数据库——添加、删除或更新记录——都只需操作当前正写入的那个分片。因此这种二级索引叫做本地索引（local index），在信息检索的语境里也叫按文档分片的索引（document-partitioned index）[29]。

例如，设想你运营一个二手车交易网站。每条挂牌信息都有唯一 ID，把这个 ID 作为分片键，如图 7-9（ID 0–499 在分片 0，ID 500–999 在分片 1，依此类推）。你想让用户按颜色和品牌筛选，就要为 color 和 make 建二级索引（在文档数据库里是字段，在关系库里是列）。一旦声明了索引，数据库就能自动维护：每当一辆红色车加入数据库，所在分片就会自动把它的 ID 加到 color:red 这一索引项的 ID 列表中。第 4 章讲过，这种 ID 列表也叫倒排表（postings list）。

图 7-9. 本地二级索引中，每个分片只索引它自己包含的记录。

图示文字描述： 如果你的数据库只支持键值模型，可能会想在应用代码里手工实现二级索引——把值映射到 ID。这条路上要格外小心，必须保证索引与底层数据始终一致。竞态条件以及写入中断（部分更改保存了、另一部分没保存）很容易让数据出现不一致——见第 287 页"对多对象事务的需要"。 从本地二级索引读取时，如果你已经知道要找记录的分片键，就只需在对应分片上做搜索即可。如果你只要部分结果、不在乎齐不齐，可以把请求发给任意一个分片。但要拿到全部结果、又不知道它们的分片键，就得把查询发到所有分片再合并结果——因为匹配的记录可能散落在所有分片中。如图 7-9，红色车在分片 0 和分片 1 都有。

这种查询方式会让带二级索引的读取相当昂贵。即便并行查询所有分片，也容易出现尾延迟放大（见第 41 页"响应时间指标的使用"）。它也限制了应用的可扩展性：分片再多虽能存更多数据，但只要每条查询都要每个分片处理，查询吞吐量也不会跟着涨。

即便如此，本地二级索引仍被广泛采用 [30]——例如 MongoDB、Riak、Cassandra [31]、Elasticsearch [32]、SolrCloud、VoltDB [33] 都用本地二级索引。

全局二级索引

我们也可以构建一个覆盖所有分片数据的全局索引，而不是让每个分片各管各的本地索引。但不能把全局索引整个塞进一个节点——那它就会成为瓶颈，分片本身的意义也就荡然无存。全局索引必须自己也分片，但分片方式可以与主键索引不同。

图 7-10 演示了这种做法。所有分片中红色车的 ID 都出现在 color:red 索引项下，但该索引本身也做了分片：以 a 到 r 开头的颜色出现在分片 0，以 s 到 z 开头的颜色出现在分片 1。车品牌索引也类似（边界在 f 与 h 之间）。

图 7-10. 全局二级索引反映所有分片中的数据，且按被索引的值再分片。 这种索引也叫按词分片（term-partitioned）[29]。回忆一下第 146 页"全文搜索"中"词"（term）指文本里可被搜索的关键词；这里我们把它泛化为二级索引中可被搜索的任意值。

全局索引以词作为分片键，所以查找特定词或值时，可以确定该到哪个分片去查。每个分片可以包含一段连续的词范围（如图 7-10），也可以基于词的哈希值分片。

全局索引的好处是：单条件查询（例如 color = red）只需读一个分片就能拿到倒排表。但要拿到记录本身、而不仅是 ID，仍得从持有这些 ID 的所有分片中读出。

如果有多个搜索条件或词（例如同时按颜色和品牌找车，或要求文本里同时出现多个单词），这些词很可能落在不同分片上。要计算两个条件的逻辑 AND，系统必须找出两个倒排表中都出现的所有 ID。倒排表短时这没问题，但若很长，把它们通过网络传输再求交集就会很慢 [29]。

全局二级索引的另一个挑战是：写入比本地索引更复杂——一次写入可能影响索引的多个分片（文档中各个词可能落在不同分片上）。这让保持二级索引与底层数据同步变得更难。一种办法是用分布式事务，原子地更新存放主记录及其二级索引的分片（见第 8 章）。

CockroachDB、TiDB、YugabyteDB 都使用全局二级索引；DynamoDB 则同时支持本地和全局二级索引。在 DynamoDB 中，写入会异步反映到全局索引，因此从全局索引读取可能拿到陈旧数据（与第 209 页"复制延迟带来的问题"类似）。尽管如此，当读吞吐量高于写吞吐量、且倒排表不太长时，全局索引仍非常有用。

小结

本章探讨了把大数据集切成更小子集的多种方法。当数据多到一台机器存不下、也处理不了时，就需要分片。

分片的目标是把数据和查询负载均匀地分散到多台机器上，避免出现热点（即负载过高的节点）。要做到这一点，需要选择适合数据的分片方案，并在节点加入或移出集群时进行再均衡。

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

按键范围分片

把键排序，每个分片拥有从最小到最大的一段键。排序的好处是支持高效的范围查询，但如果应用频繁访问排序中相邻的键，就存在热点风险。

这种方式下，再均衡通常是在分片变得太大时，把它的键范围切成两段子范围来完成。

按哈希分片

对每个键应用哈希函数，每个分片拥有一段哈希值范围（也可以用一致性哈希算法把哈希值映射到分片）。这种方式破坏了键的顺序，使范围查询低效，但负载分布可能更均匀。

按哈希分片时，常见做法是预先建好固定数量的分片，给每个节点分配若干分片；节点加入或移出时整片地搬移。也可以像按键范围那样切分分片。

常见做法是用键的第一部分作为分片键（用于确定分片），按键的其余部分对分片内的记录排序。这样分片键相同的记录之间仍能高效做范围查询。

我们还讨论了把查询路由到合适分片的技术，并看到了协调服务如何帮助跟踪分片到节点的分配。

最后考察了分片与二级索引的相互作用。二级索引也要分片，方式有两种：

本地二级索引

二级索引与主键、主值放在同一分片中。写入时只需更新一个分片，但二级索引查询要从所有分片读取。

全局二级索引

二级索引按被索引的值另外分片。一条二级索引条目可能引用主键所属分片之外的记录。一次写入可能要更新多个二级索引分片；但一次倒排表查询只需在一个分片上完成（取实际记录仍要从多个分片读取）。

按设计，每个分片基本独立运转——这也正是分片型数据库能扩展到多台机器的原因。但需要写入多个分片的操作就棘手了——比如对一个分片的写入成功、对另一个分片的写入失败时该怎么办？这个问题留给接下来的章节回答。

参考文献

[1] Claire Giordano. "Understanding Partitioning and Sharding in Postgres and Citus." citusdata.com, August 2023. 归档于 perma.cc/8BTK-8959

[2] Brandur Leach. "Partitioning in Postgres, 2022 Edition." brandur.org, October 2022. 归档于 perma.cc/Z5LE-6AKX

[3] Raph Koster. "Database 'Sharding' Came from UO?" raphkoster.com, January 2009. 归档于 perma.cc/4N9U-5KYF

[4] Garrett Fidalgo. "Herding Elephants: Lessons Learned from Sharding Postgres at Notion." notion.com, October 2021. 归档于 perma.cc/5J5V-W2VX

[5] Ulrich Drepper. "What Every Programmer Should Know About Memory." akkadia.org, November 2007. 归档于 perma.cc/NU6Q-DRXZ

[6] Jingyu Zhou, Meng Xu, Alexander Shraer, Bala Namasivayam, Alex Miller, Evan Tschannen, Steve Atherton, Andrew J. Beamon, Rusty Sears, John Leach, Dave Rosenthal, Xin Dong, Will Wilson, Ben Collins, David Scherer, Alec Grieser, Young Liu, Alvin Moore, Bhaskar Muppana, Xiaoge Su, Vishesh Yadav. "FoundationDB: A Distributed Unbundled Transactional Key Value Store." 见 ACM SIGMOD International Conference on Management of Data (SIGMOD), June 2021. doi:10.1145/3448016.3457559

[7] Marco Slot. "Citus 12: Schema-Based Sharding for PostgreSQL." citusdata.com, July 2023. 归档于 perma.cc/R874-EC9W

[8] Robisson Oliveira. "Reducing the Scope of Impact with Cell-Based Architecture." AWS Well-Architected White Paper, Amazon Web Services, September 2023. 归档于 perma.cc/4KWW-47NR

[9] Gwen Shapira. "Things DBs Don't Do—But Should." thenile.dev, February 2023. 归档于 perma.cc/C3J4-JSFW

[10] Malte Schwarzkopf, Eddie Kohler, M. Frans Kaashoek, Robert Morris. "Position: GDPR Compliance by Construction." 见 Towards Polystores That Manage Multiple Databases, Privacy, Security and/or Policy Issues for Heterogenous Data (Poly), August 2019. doi:10.1007/978-3-030-33752-0_3

[11] Gwen Shapira. "Introducing pg_karnak: Transactional Schema Migration Across Tenant Databases." thenile.dev, November 2024. 归档于 perma.cc/R5RD-8HR9

[12] Arka Ganguli, Guido Iaquinti, Maggie Zhou, Rafael Chacón. "Scaling Datastores at Slack with Vitess." slack.engineering, December 2020. 归档于 perma.cc/UW8F-ALJK

[13] Ikai Lan. "App Engine Datastore Tip: Monotonically Increasing Values Are Bad." ikaisays.com, January 2011. 归档于 perma.cc/BPX8-RPJB

[14] Enis Soztutar. "Apache HBase Region Splitting and Merging." cloudera.com, February 2013. 归档于 perma.cc/S9HS-2X2C

[15] Eric Evans. "Rethinking Topology in Cassandra." 见 Cassandra Summit, June 2013. 归档于 perma.cc/2DKM-F438

[16] Martin Kleppmann. "Java's hashCode Is Not Safe for Distributed Systems." martin.kleppmann.com, June 2012. 归档于 perma.cc/LK5U-VZSN

[17] Mostafa Elhemali, Niall Gallagher, Nicholas Gordon, Joseph Idziorek, Richard Krog, Colin Lazier, Erben Mo, Akhilesh Mritunjai, Somu Perianayagam, Tim Rath, Swami Sivasubramanian, James Christopher Sorenson III, Sroaj Sosothikul, Doug Terry, Akshat Vig. "Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service." 见 USENIX Annual Technical Conference (ATC), July 2022.

[18] David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, Daniel Lewin. "Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web." 见 29th Annual ACM Symposium on Theory of Computing (STOC), May 1997. doi:10.1145/258533.258660

[19] Damian Gryski. "Consistent Hashing: Algorithmic Tradeoffs." dgryski.medium.com, April 2018. 归档于 perma.cc/B2WF-TYQ8

[20] David G. Thaler, Chinya V. Ravishankar. "Using Name-Based Mappings to Increase Hit Rates." IEEE/ACM Transactions on Networking, volume 6, issue 1, pages 1–14, February 1998. doi:10.1109/90.663936

[21] John Lamping, Eric Veach. "A Fast, Minimal Memory, Consistent Hash Algorithm." arXiv:1406.2294, June 2014.

[22] Samuel Axon. "3% of Twitter's Servers Dedicated to Justin Bieber." mashable.com, September 2010. 归档于 perma.cc/F35N-CGVX

[23] Gerald Guo, Thawan Kooburat. "Scaling Services with Shard Manager." engineering.fb.com, August 2020. 归档于 perma.cc/EFS3-XQYT

[24] Sangmin Lee, Zhenhua Guo, Omer Sunercan, Jun Ying, Thawan Kooburat, Suryadeep Biswal, Jun Chen, Kun Huang, Yatpang Cheung, Yiding Zhou, Kaushik Veeraraghavan, Biren Damani, Pol Mauri Ruiz, Vikas Mehta, Chunqiang Tang. "Shard Manager: A Generic Shard Management Framework for Geo-Distributed Applications." 见 28th ACM SIGOPS Symposium on Operating Systems Principles (SOSP), October 2021. doi:10.1145/3477132.3483546

[25] Scott Lystig Fritchie. "A Critique of Resizable Hash Tables: Riak Core & Random Slicing." infoq.com, August 2018. 归档于 perma.cc/RPX7-7BLN

[26] Andy Warfield. "Building and Operating a Pretty Big Storage System Called S3." allthingsdistributed.com, July 2023. 归档于 perma.cc/6S7P-GLM4

[27] Rich Houlihan. "DynamoDB Adaptive Capacity: Smooth Performance for Chaotic Workloads (DAT327)." 见 AWS re:Invent, November 2017.

[28] Kostja Osipov. "ScyllaDB's Safe Topology and Schema Changes on Raft." scylladb.com, June 2024. 归档于 perma.cc/4S82-M277

[29] Christopher D. Manning, Prabhakar Raghavan, Hinrich Schütze. Introduction to Information Retrieval. Cambridge University Press, 2008. ISBN: 9780521865715. 在线提供：nlp.stanford.edu/IR-book。

[30] Michael Busch, Krishna Gade, Brian Larson, Patrick Lok, Samuel Luckenbill, Jimmy Lin. "Earlybird: Real-Time Search at Twitter." 见 28th IEEE International Conference on Data Engineering (ICDE), April 2012. doi:10.1109/ICDE.2012.149

[31] Nadav Har'El. "Indexing in Cassandra 3." github.com, April 2017. 归档于 perma.cc/3ENV-8T9P

[32] Zachary Tong. "Customizing Your Document Routing." elastic.co, June 2013. 归档于 perma.cc/97VM-MREN

[33] Andrew Pavlo. "H-Store Documentation: Frequently Asked Questions." hstore.cs.brown.edu, October 2013. 归档于 perma.cc/X3ZA-DW6Z