第7章 分片
显然，我们必须摆脱顺序的束缚，不受计算机的限制。我们必须陈述定义，为数据的优先级和描述做好准备。我们必须陈述关系，而非过程。 — Grace Murray Hopper，《管理与未来的计算机》(1962)
分布式数据库通常通过两种方式将数据分布到节点上：
- 它在多个节点上存储同一数据的副本。这是复制，我们在第6章中讨论过。
- 如果数据量或写入吞吐量过大，单个节点无法处理，则会将数据拆分为更小的分片或分区，并将不同的分片存储在不同的节点上。我们将在此章讨论分片。
通常，分片的定义方式是：每条数据（每条记录、行或文档）恰好属于一个分片。实现这一目标有多种方法，我们将在本章深入探讨。实际上，每个分片本身就是一个小的数据库，尽管某些数据库系统支持同时操作多个分片的操作。
分片通常与复制结合使用，因此每个分片的副本存储在多个节点上。这意味着即使每条记录只属于一个分片，为了容错，它仍可能存储在多个不同的节点上。
一个节点可以存储多个分片。如果使用单主复制模型，分片与复制的组合可以如图7-1所示。每个分片的主节点分配到一个节点，其从节点分配到其他节点。每个节点可能是某些分片的主节点，同时是其他分片的从节点，但每个分片仍然只有一个主节点。
图7-1说明
图7-1. 复制与分片的结合：每个节点充当某些分片的主节点和其他分片的从节点。
分片与分区
我们在此章中称为“分片”的概念，在不同软件中有许多名称。例如：在Kafka中称为分区，在CockroachDB中称为范围，在HBase和TiDB中称为区域，在Couchbase中称为vBucket，在Riak中称为vnode，在Cassandra中称为令牌范围，在Bigtable、YugabyteDB和ScyllaDB中称为tablet，仅举几例。
某些数据库将分区和分片视为两个不同的概念。例如，在PostgreSQL中，分区是将一个大表分割成存储在同一机器上的多个文件的一种方式（这有几个优点，例如可以非常快速地删除整个分区），而分片则是在多台机器之间拆分数据集 [1, 2]。在许多其他系统中，“分区”只是“分片”的另一种说法。
虽然“分区”这个词相当形象，但“分片”一词可能令人惊讶。根据一种理论，该术语源于在线角色扮演游戏《网络创世纪》，其中一块魔法水晶被击碎成碎片，每个碎片折射出一个游戏世界的副本 [3]。因此，“分片”一词逐渐意指一组并行游戏服务器中的一个，后来被引入数据库。另一种理论是，它最初是“System for Highly Available Replicated Data”（高度可用复制数据系统）的缩写——据说是20世纪80年代的一个数据库，其细节已消失在历史中。
顺便一提，“分区”与网络分区（网络分裂）无关，网络分区是节点之间网络的一种故障类型。我们将在第9章讨论此类故障。
第6章中关于数据库复制的一切内容同样适用于分片的复制。由于分片方案的选择通常独立于复制方案的选择，为简单起见，本章将忽略复制。
分片的优缺点
分片数据库的主要原因是可扩展性。当数据量或写入吞吐量对于单个节点来说已经过大时，分片是一种解决方案，因为它允许你将数据和写入分散到多个节点。（如果问题是读取吞吐量，你未必需要分片——你可以使用读扩展，如第6章所述。）
事实上，分片是我们实现水平扩展（无共享架构）的主要工具之一，如“共享内存、共享磁盘与无共享架构”（第51页）所讨论的——即系统通过增加更多（更小）的机器来提升容量，而不是升级到更大的机器。如果你能将工作负载划分成每个分片处理大致相等的份额，那么你就可以将这些分片分配给不同的机器，使其并行处理数据和查询。
虽然复制在小型和大型规模下都很有用，因为它提供了容错和离线操作能力，但分片是一种重量级解决方案，主要适用于大规模场景。如果你的数据量和写入吞吐量是单台机器可以处理的（而且现代单台机器能力很强！），通常最好避免分片，坚持使用单分片数据库。
提出此建议的原因是分片增加了复杂性。通常你需要通过选择分区键来决定将哪些记录放入哪个分片；所有具有相同分区键的记录都被放置在同一个分片中 [4]。这一选择很重要，因为如果你知道记录在哪个分片中，访问它会很快；但如果你不知道，则必须在所有分片中进行低效的搜索。分片方案也很难更改。
分片通常适用于键值数据，因为你可以轻松地按键分片，但关系数据则更难处理，因为你可能需要按二级索引搜索或连接分布在不同分片上的记录。我们将在“分片与二级索引”（第268页）进一步讨论。
分片的另一个问题是写入可能需要更新多个分片中的相关记录。虽然单节点上的事务相当常见，但确保跨多个分片的一致性需要分布式事务。正如我们将在第8章中看到的，某些数据库支持分布式事务，但它们通常比单节点事务慢得多，并可能成为整个系统的瓶颈。
单机分片
有些系统甚至在单台机器上使用分片，通常为每个CPU核心运行一个单线程进程，以利用CPU的并行性或利用非均匀内存访问（NUMA）架构，其中某些内存库离一个CPU比离其他CPU更近 [5]。例如，Redis、VoltDB和FoundationDB为每个核心使用一个进程，并依赖分片将负载分散到同一台机器的CPU核心上 [6]。
分片用于多租户
软件即服务（SaaS）产品和云服务通常是多租户的，其中每个租户是一个客户。多个用户可能在同一租户下拥有登录账户，但每个租户有一个独立的数据集，与其他租户的数据集分离。例如，在电子邮件营销服务中，每个注册的企业通常是一个独立的租户，因为一家企业的新闻通讯注册、投递数据等与其他企业的数据是分开的。
有时分片用于实现多租户系统。要么每个租户被分配一个独立的分片，要么多个小租户被组合成一个更大的分片。这些分片可能是物理上独立的数据库（我们在“嵌入式存储引擎”第125页提到过），或者是一个更大逻辑数据库中可单独管理的部分 [7]。使用分片实现多租户有几个优点：
- 资源隔离：如果一个租户执行了计算密集的操作，如果它们运行在不同的分片上，其他租户的性能受到的影响较小。
- 权限隔离：如果访问控制逻辑中存在错误，如果租户的数据集在物理上彼此分离存储，你不大可能意外地将一个租户的访问权限赋予另一个租户的数据。
- 基于单元的架构：你不仅可以在数据存储层面应用分片，还可以应用于运行应用程序代码的服务。在基于单元的架构中，特定租户集合的服务和存储被分组到一个独立的单元中，并且不同单元的设置使得它们可以很大程度上彼此独立运行。这种方法提供了故障隔离：一个单元中的故障仅限于该单元，其他单元中的租户不受影响 [8]。
- 按租户备份和恢复：独立备份每个租户的分片，使得可以从备份恢复一个租户的状态而不影响其他租户，这在租户意外删除或覆盖重要数据时非常有用 [9]。
术语解释
在本章中，“分片”和“分区”在某些上下文中可互换使用，但具体含义取决于数据库系统。在PostgreSQL中，分区是单机概念，而分片是跨机器概念。在其他系统中，两者同义。
第7章：分片
Regulatory compliance (合规性)
诸如GDPR和CCPA等数据隐私法规赋予个人访问和请求删除企业存储的其个人信息的权利。如果每个人的数据存储在单独的分片中，就转化为在其分片上简单执行数据导出和删除操作[10]。
Data residence (数据驻留)
如果某个特定租户的数据需要存储在特定司法管辖区以遵守数据驻留法律，那么支持区域感知的数据库可以允许你将该租户的分片分配给特定区域。
Gradual schema rollout (渐进式模式推出)
模式迁移（之前在文档模型中的模式灵活性第80页讨论过）可以逐步推出，一次一个租户。这降低了风险，因为你可以检测到问题，防止其影响所有租户，但事务性地执行此操作可能很困难[11]。
使用分片实现多租户的主要挑战如下：
- 它假定每个单个租户足够小，可以放在单个节点上。如果不是这样，并且你有一个租户太大而无法容纳在一台机器上，那么你需要在该租户内额外执行分片，这使我们回到为可扩展性进行分片的话题[12]。
- 如果你有许多小租户，为每个租户创建一个单独的分片可能产生过多的开销。你可以将几个小租户组合成一个更大的分片，但这样你就面临如何将租户从一个分片移动到另一个分片（随着它们增长）的问题。
- 如果你需要支持跨多个租户连接数据的特性，那么在需要跨多个分片连接数据时，这些特性实现起来会更困难。
键值数据的分片
假设你有大量数据，并且想要分片它。你如何决定哪些记录存储在哪些节点上？
分片的目标是跨节点均匀分布数据和查询负载。如果每个节点承担公平的份额，那么——理论上——10个节点应该能够处理10倍于单个节点的数据量以及10倍的读写吞吐量（忽略复制）。如果你添加或删除一个节点，你还希望能够重新平衡负载，使其均匀分布在新数量的节点上。
如果分片不公平，以至于某些分片拥有的数据或查询多于其他分片，我们称之为偏斜 (skewed)。偏斜的存在会大大降低分片的效果。在极端情况下，所有负载可能最终集中在一个分片上，导致9个节点闲置，而瓶颈是那个忙碌的节点。负载异常高的分片称为热分片 (hot shard) 或热点 (hot spot)。如果某个键的负载特别高（例如社交网络中的名人），我们称之为热键 (hot key)。
要将数据集拆分为分片，我们需要一种算法，该算法以记录的分区键作为输入，并告诉我们该记录属于哪个分片。在键值存储中，分区键通常是键或键的第一部分。在关系模型中，分区键可能是表的一列（不一定是其主键）。该算法需要便于重新平衡以缓解热点。
按键范围分片
一种分片方式是为每个分片分配一个连续的分区键范围（从最小值到最大值），就像纸质百科全书的卷一样，如图7-2所示。在这个例子中，条目的分区键是其标题。如果你想查找特定标题的条目，通过找到键范围包含你所查找标题的卷，你可以轻松确定哪个分片包含该条目，从而从书架上选出正确的书。
图7-2. 纸质百科全书按键范围分片。
![图7-2描述：一本印刷的百科全书打开显示多个卷，从A-B到T-Z，说明不同卷包含不同字母范围的词汇。]
键的范围不一定均匀分布，因为你的数据可能分布不均匀。例如，在图7-2中，第1卷包含以A和B开头的单词，而第12卷包含以T、U、V、W、X、Y和Z开头的单词。简单地让每个卷对应字母表中的两个字母会导致某些卷比其他卷大得多。为了均匀分布数据，分片边界需要适应数据。
256 | 第7章：分片
分片边界可以由管理员手动选择，或者数据库可以自动选择。例如，Vitess（MySQL的分片层）使用手动键范围分片；Bigtable及其开源等效HBase、MongoDB中基于范围的分片选项，以及CockroachDB、RethinkDB和FoundationDB使用自动变体[6]。YugabyteDB提供手动和自动平板分割选项。
在每个分片内，键按排序顺序存储（例如，在B树或SSTable中，如第4章所述）。这具有范围扫描很容易的优点，你可以将键视为级联索引，以便在一个查询中获取多个相关记录（参见第145页的“多维和全文索引”）。例如，考虑一个存储来自传感器网络数据的应用程序，其中键是测量的时间戳。在这种情况下，范围扫描非常有用，因为它们让你轻松获取，比如，某个特定月份的所有读数。
键范围分片的一个缺点：如果对邻近键有大量写入，很容易出现热分片。例如，如果键是时间戳，那么分片对应时间范围——例如，每个分片负责一个月。如果你在测量发生时将传感器数据写入数据库，所有写入最终都会进入同一个分片（当前月份的分片），因此该分片会被写入过载，而其他分片则处于空闲状态[13]。
为了避免传感器数据库中的这个问题，你需要使用时间戳以外的其他东西作为键的第一个元素。例如，你可以用传感器ID作为每个时间戳的前缀，这样键的顺序首先按传感器ID排序，然后按时间戳排序。假设你在同一时间有许多活跃的传感器，写入负载将更均匀地分布在各个分片上。缺点是当你想要获取时间范围内多个传感器的值时，你现在需要为每个传感器执行单独的范围查询。
重新平衡键范围分片的数据
当你首次设置数据库时，没有键范围可以拆分成多个分片。某些数据库，如HBase和MongoDB，允许你在空数据库上配置一组初始分片，这称为预分割 (pre-splitting)。这要求你已经对键分布的大致情况有所了解，以便选择合适的键范围边界[14]。
随后，随着数据量和写入吞吐量的增加，采用键范围分片的系统通过将现有分片拆分成两个或更多更小的分片来增长，每个更小的分片容纳原始分片键范围内的连续子范围。然后可以将生成的小分片分布到多个节点上。如果大量数据被删除，你可能还需要将几个因变小而相邻的分片合并成一个更大的分片。这个过程类似于B树顶层发生的情况（参见第125页的“B-Trees”）。
对于自动管理分片边界的数据库，分片拆分通常由分片达到配置的大小（例如，在HBase上，默认是10 GB）或在某些系统中写入吞吐量持续高于某个阈值触发。因此，即使热分片没有存储大量数据，也可能被拆分，以便其写入负载更均匀地分布。
NOTE
不幸的是，分片数量会适应数据量。如果只有少量数据，少量分片就足够了，因此开销很小；如果有大量数据，每个单独分片的大小被限制为可配置的最大值[15]。
不幸的是，拆分分片是一项昂贵的操作，因为它需要将所有数据重写到新文件中，类似于日志结构存储引擎中的压缩。需要拆分分片的分片通常也处于高负载下，而拆分的成本可能会加剧该负载，使其面临过载风险。
按键哈希分片
如果你的记录希望将分区键相近（但不同）的记录分组到同一分片中（例如时间戳的情况），键范围分片很有用。如果你不关心分区键是否彼此靠近（例如，在多租户应用程序中它们可能是租户ID），常见的方法是先将分区键哈希，然后再映射到分片。
一个好的哈希函数可以将偏斜的数据变得均匀分布。假设你有一个32位的哈希函数，它接受一个字符串。每当你给它一个新字符串，它会返回一个从0到2^32 − 1之间的看似随机的数字。即使输入字符串非常相似，它们的哈希值也均匀分布在该数字范围内（但同一输入始终产生相同输出）。
用于分片目的时，哈希函数不需要是密码学强度的：例如，MongoDB使用MD5，而Cassandra和ScyllaDB使用Murmur3。许多编程语言都有内置的简单哈希函数（因为它们用于哈希表），但它们可能不适合分片：例如，在Java的Object.hashCode()和Ruby的Object#hash中，同样的键在不同进程中可能具有不同的哈希值，这使得它们不适用于分片[16]。
哈希取模节点数
一旦你哈希了键，如何选择哪个分片来存储它？你首先可能会想到取哈希值与系统中节点数的模（在许多编程语言中使用%运算符）。例如，hash(key) % 10会返回一个从0到9的数字（如果我们将哈希写成十进制数，hash % 10将是最后一位数字）。如果我们有10个节点，编号0到9，这似乎是给每个键分配一个节点的简单方法。
WARNING
然而，这只是基本思想。实际上，简单的取模会导致重新平衡困难：当节点数变化时，大多数键的位置会改变，导致大量数据迁移。因此，许多系统使用更复杂的哈希一致算法，如一致性哈希（consistent hashing）或固定数量的虚拟分片。但本节重点是哈希函数本身的特性，取模只是引出问题。
258 | 第7章：分片
第7章：分片
键值数据的分片
使用模 N（在许多编程语言中通过 % 运算符实现）的方法存在的问题是：当节点数 N 发生变化时，大多数键必须从一个节点移动到另一个节点。图7-3展示了当你有三个节点并增加第四个节点时的情况。在再平衡之前，节点0存储了哈希值为0、3、6、9等的键。添加第四个节点后，哈希值为3的键移到了节点3，哈希值为6的键移到了节点2，哈希值为9的键移到了节点1，依此类推。
图7-3. 通过对键进行哈希并取模节点数来分配键到节点。改变节点数会导致许多键从一个节点移动到另一个节点。
模 N 函数易于计算，但会导致非常低效的再平衡，因为大量记录不必要地在节点之间移动。我们需要一种尽可能少移动数据的方法。
固定数量的分片
一种简单但广泛使用的解决方案是创建比节点数量多得多的分片，并为每个节点分配多个分片。例如，一个运行在10个节点集群上的数据库，起初可能被拆分成1000个分片，每个节点分配100个分片。然后，键被存储在分片编号为 hash(key) % 1000 的分片中，系统单独跟踪哪个分片存储在哪个节点上。
现在，如果向集群添加一个节点，系统可以将一些分片从现有节点重新分配给新节点，直到再次公平分布。这一过程如图7-4所示。如果从集群中移除一个节点，则发生相反的过程。
在这种模型中，只有整个分片在节点之间移动，这比分拆分片更轻量。分片数量不变，键到分片的分配也不变。唯一变化的是分片到节点的分配。这种重新分配不是即时的——通过网络传输大量数据需要一些时间——因此在传输过程中发生的任何读写操作仍使用旧的分片分配。
图7-4. 向具有每个节点多个分片的数据库集群添加新节点
通常选择的分片数量是能被许多因数整除的，这样数据集可以均匀地分布在不同数量的节点上——例如，不要求节点数是2的幂[4]。你甚至可以考虑到集群中硬件不匹配的情况：通过给更强大的节点分配更多分片，可以使这些节点承担更大的负载。
这种分片方法被用于 Citus（PostgreSQL 的分片层）、Riak、Elasticsearch 和 Couchbase 等。只要你在首次创建数据库时对所需分片数量有良好估计，这个方法就能很好地工作。然后你可以轻松添加或删除节点，但受限于节点数不能超过分片数。
如果你发现最初配置的分片数量不合适——例如，当规模达到需要更多节点时，但分片数不够——则需要执行昂贵的重新分片操作。它需要拆分每个分片并将其写入新文件，过程中会消耗大量额外的磁盘空间。某些系统不允许在并发写入数据库时进行重新分片，这使得在不中断服务的情况下更改分片数量变得困难。
如果数据集的总大小高度可变（例如，起初很小但可能随时间大幅增长），则选择合适的分片数量很困难。由于每个分片包含总数据的固定比例，每个分片的大小与集群中的数据总量成比例增长。如果分片非常大，再平衡和从节点故障中恢复的成本就会很高。但如果分片太小，则会导致过多开销。当分片大小“恰到好处”，既不太大也不太小，才能实现最佳性能；如果分片数量固定而数据集大小变化，这很难实现。
哈希范围分片
如果无法预先预测所需分片数量，最好使用一种能够轻松适应工作负载的方案。前面提到的键范围分片方案具有这种特性，但当有大量写入到相邻键时存在热点风险。一种解决方案是将键范围分片与哈希函数结合起来，这样每个分片包含一段哈希值范围而非键范围。
图7-5展示了一个例子，使用一个16位哈希函数，返回0到65,535 = 2^16 − 1之间的数字（实际上，哈希通常是32位或更多）。即使输入键非常相似（例如连续的时间戳），它们的哈希值也均匀分布在该范围内。然后我们可以为每个分片分配一段哈希值范围——例如，值0到16383给分片0，值16384到32767给分片1，依此类推。
图7-5. 为每个分片分配一段连续的哈希值范围
与键范围分片一样，在哈希范围分片中，当分片变得过大或负载过重时，可以将其拆分。这仍然是一个昂贵的操作，但可以根据需要发生，因此分片数量会适应数据量，而不是预先固定。
与键范围分片相比的缺点是：针对分区键的范围查询效率不高，因为该范围内的键现在分散在所有分片中。然而，如果键由两列或更多列组成，且分区键只是这些列中的第一列，你仍然可以对第二列及后续列执行高效的范围查询。只要范围查询中的所有记录具有相同的分区键，它们就会位于同一个分片中。
数据仓库中的分区和范围查询
数据仓库如 BigQuery、Snowflake 和 Delta Lake 支持类似的索引方法，尽管术语有所不同。例如，在 BigQuery 中，分区键决定了记录位于哪个分区，而“聚类列”决定了记录在分区内的排序方式。Snowflake 自动将记录分配到“微分区”，但允许用户为表定义聚类键。Delta Lake 支持手动和自动分区分配，并支持聚类键。聚类数据不仅提高了范围扫描性能，还能改善压缩和过滤性能。
YugabyteDB 和 DynamoDB [17] 使用哈希范围分片，并且是 MongoDB 的一个选项。Cassandra 和 ScyllaDB 使用这种方法的变体，如图7-6所示。
图7-6. Cassandra 和 ScyllaDB 将可能的哈希值范围（这里为0–1024）拆分成具有随机边界的连续范围，并为每个节点分配多个范围。
哈希值的空间被拆分成与节点数成比例的数量（图中显示每个节点3个范围，但实际数量为每个节点16个）。
页码参考：258–262（章节连续）
第7章：分片
在 Cassandra 中默认每个节点有 16 个范围，而在 ScyllaDB 中每个节点有 256 个范围，哈希值空间被划分为与节点数量成比例的多个连续范围，这些范围具有随机边界。每个节点被分配多个范围（图中显示每个节点 3 个范围，但实际数字取决于系统）。这意味着某些范围比其他范围大，但通过每个节点拥有多个范围，这些不平衡往往会趋于平衡[15]。
当节点被添加或移除时，范围边界会被调整，分片也会相应地被拆分或合并。在图 7-6 中，当节点 3 被添加时，节点 1 将其两个范围的一部分转移给节点 3，节点 2 将其一个范围的一部分转移给节点 3。这种效果使新节点获得大致公平的数据集份额，而不会在节点之间传输超过必要的数据量。
一致性哈希
一致性哈希算法是一种哈希函数，它将键映射到指定数量的分片，同时满足两个属性：
- 每个分片映射的键数量大致相等。
- 当分片数量发生变化时，尽可能少的键从一个分片移动到另一个分片。
NOTE
这里的“一致性”与副本一致性（参见第6章）或 ACID 一致性（参见第8章）无关，而是描述键尽可能停留在同一分片的趋势。
Cassandra 和 ScyllaDB 使用的分片算法类似于一致性哈希的原始定义[18]，但也提出了其他几种一致性哈希算法[19]，例如最高随机权重（也称为 rendezvous hashing）[20]和跳跃一致性哈希[21]。使用这些方法，不是将少量现有分片拆分成子范围来为新增节点创建新分片，而是将之前分散在所有其他节点上的单个键分配给新节点。哪种方法更可取取决于应用场景。
偏斜工作负载与缓解热点
一致性哈希确保键均匀分布在各个节点上，但这并不意味着实际负载是均匀分布的。如果工作负载高度偏斜——即某些分区键下的数据比其他键多得多，或者某些键的请求速率远高于其他键——那么仍然可能导致某些服务器过载而其他服务器几乎闲置。
例如，在社交媒体网站上，一个拥有数百万粉丝的 celebrity 用户的帖子可能会引发活动风暴[22]。此事件可能导致大量读取和写入针对同一个键（分区键可能是 celebrity 的用户 ID，或人们正在评论的操作的 ID）。
在这种情况下，需要更灵活的分片策略[23, 24]。一个基于键范围（或哈希范围）定义分片的系统，可以将单个热点键单独放入一个分片，甚至可以为其分配一台专用机器[25]。
还可以在应用层面补偿偏斜。例如，如果一个键已知非常热，一种简单的方法是在键的开头或结尾添加一个随机数。仅添加两位随机数就可以将对该键的写入均匀地分散到 100 个键上，从而允许将这些键分布到不同的分片。
然而，将写入分散到多个键后，任何读取现在都需要做额外的工作，因为它们必须从所有 100 个键读取数据并将其合并。热点键的每个分片的读取量并未减少；只有写入负载被分散了。这种技术还需要额外的簿记：仅为少数热点键追加随机数才有意义；对于绝大多数写入吞吐量低的键，这将是不必要的开销。因此，还需要某种方式来跟踪哪些键被拆分，以及将常规键转换为特殊管理的热点键的过程。
随着负载随时间变化，这个问题变得更加复杂：例如，某个已经病毒式传播的特定社交媒体帖子可能会经历几天的高负载，但之后很可能平静下来。此外，某些键可能是写入热点，而其他键是读取热点，这需要不同的处理策略。
一些系统（尤其是为大规模设计的云服务）具有处理热点分片的自动化方法。例如，亚马逊称之为热管理[26]或自适应容量[17]。这些系统如何工作的细节超出了本书的范围。
操作：自动重平衡与手动重平衡
关于重平衡，我们忽略了一个重要问题：分片的拆分和重平衡是自动发生还是手动发生？
某些系统在无需任何人干预的情况下自动决定何时拆分分片以及何时将它们从一个节点移动到另一个节点，而其他系统则将分片交由管理员显式配置。也存在中间地带——例如，Couchbase 和 Riak 会自动生成建议的分片分配，但需要管理员提交后才生效。
全自动重平衡可能很方便，因为常规维护的操作工作量更少，并且此类系统甚至可以自动扩缩以适应工作负载的变化。诸如 DynamoDB 之类的云数据库被宣传为能够自动添加和移除分片，以适应几分钟内负载的大幅增加或减少[17, 27]。
然而，自动分片管理也可能不可预测。重平衡是一项代价高昂的操作，因为它需要重新路由请求并将大量数据从一个节点移动到另一个节点。如果此过程处理不当，可能会使网络或节点过载，并损害其他请求的性能。系统必须在重平衡进行时继续处理写入；如果系统接近其最大写入吞吐量，分片拆分过程甚至可能无法跟上传入写入的速率[27]。
这种自动化与自动故障检测相结合时可能很危险。例如，假设一个节点过载并暂时响应缓慢。其他节点判断该过载节点已死，并自动重平衡集群以将负载移离它。这给其他节点和网络带来了额外负载，使情况变得更糟。存在引发级联故障的风险，即其他节点变得过载并也被错误地怀疑宕机。
因此，在重平衡中引入人工干预可能是好的。它比完全自动化的过程慢，但有助于防止操作上的意外。如果由于已知事件（如网络星期一假期销售或世界杯等热门体育赛事门票销售）预计流量激增，手动重平衡对于预防性重平衡也很有用。
请求路由
我们已经讨论了如何跨多个节点对数据集进行分片，以及如何在添加或移除节点时重平衡这些分片。现在让我们转向另一个问题：如果要读取或写入特定键，如何知道需要连接到哪个节点——即哪个 IP 地址和端口号？
我们将此问题称为请求路由，它与我们之前在“负载均衡器、服务发现与服务网格”（第184页）中讨论的服务发现非常相似。两者最大的区别在于，运行应用代码的服务通常每个实例都是无状态的，负载均衡器可以将请求发送到任何实例。而对于分片数据库，对某个键的请求只能由包含该键的分片的副本节点处理。
这意味着请求路由必须了解从键到分片以及从分片到节点的映射关系。在高层，有几种方法可以解决此问题（如图7-7所示）：
- 允许客户端联系任何节点（例如通过轮询负载均衡器）。如果该节点恰好拥有该请求所涉及的分片，则可以直接处理该请求；否则，它将请求转发给适当的节点，接收回复，并将回复传递给客户端。
- 首先将所有来自客户端的请求发送到一个路由层，该路由层确定应处理每个请求的节点，并相应转发。该路由层本身不处理任何请求；它仅充当分片感知的负载均衡器。
- 要求客户端了解分片以及分片到节点的分配情况。在这种情况下，客户端可以直接连接到适当的节点，无需任何中介。
graph TD subgraph 方法1 C1[客户端] -->|请求| N1[任意节点] N1 -->|如果拥有分片| Handle1[直接处理] N1 -->|如果未拥有| Forward1[转发到正确节点] Forward1 --> Reply1[回复返回客户端] end subgraph 方法2 C2[客户端] -->|请求| RT[路由层] RT -->|转发| N2[目标节点] N2 -->|回复| RT RT -->|回复| C2 end subgraph 方法3 C3[客户端] -->|直接请求| N3[目标节点] N3 -->|回复| C3 end
图7-7. 将请求路由到正确节点的三种方式
每种情况都有一些关键问题：
- 谁决定哪个分片应该存在于哪个节点上？最简单的办法是让单个协调者做出决定，但如果是这样，如何使它在运行协调者的节点宕机时具备容错能力？以及如果协调者角色可以故障转移到另一个节点，如何防止出现脑裂情况（参见第204页“处理节点宕机”），即两个不同的协调者做出矛盾的分片分配？
- 执行路由的组件（可能是节点之一、路由层或客户端）如何获知分片到节点分配的变化？
第7章：分片
- 当一个分片从一个节点迁移到另一个节点时，存在一个切换期，在此期间新节点已接管，但发往旧节点的请求可能仍在处理中。你如何处理这些请求？
许多分布式数据系统依赖独立的协调服务（如 ZooKeeper 或 etcd）来跟踪分片分配，如图 7-8 所示。它们使用共识算法（参见第10章）来提供容错性和防止脑裂。每个节点在 ZooKeeper 中注册自己，ZooKeeper 维护分片到节点的权威映射。其他参与者（如路由层或感知分片的客户端）可以订阅 ZooKeeper 中的这一信息。每当分片所有权变更或节点添加/移除时，ZooKeeper 通知路由层，使其路由信息保持最新。
graph LR subgraph "协调服务 (如 ZooKeeper)" ZK[ZooKeeper] -- 维护分片分配 --> mapping[分片到节点的映射] end subgraph "节点" N1[节点1] -- 注册 --> ZK N2[节点2] -- 注册 --> ZK N3[节点3] -- 注册 --> ZK end subgraph "路由层/客户端" RT[路由层] -- 订阅通知 --> ZK C[客户端] -- 订阅 --> ZK end RT -- 路由请求 --> N1 RT -- 路由请求 --> N2
图 7-8. 使用 ZooKeeper 跟踪分片到节点的分配
例如，HBase 和 SolrCloud 使用 ZooKeeper 管理分片分配；Kubernetes 使用 etcd 跟踪哪个服务实例运行在何处。MongoDB 具有类似的架构，但它依赖自己的配置服务器实现和 mongos 守护进程作为路由层。Kafka、YugabyteDB、TiDB 和 ScyllaDB [28] 使用内置的 Raft 共识协议实现来执行此协调功能。
Riak 采用不同的方法：它使用节点间的 gossip 协议传播集群状态的任何变化。这提供的比共识协议弱得多的一致性；可能出现脑裂，即集群的不同部分对同一分片有不同的节点分配。无主数据库可以容忍这一点，因为它们通常本来就只做出弱一致性保证（参见“理解仲裁一致性的局限性”第233页）。
NOTE
当使用路由层或将请求发送到随机节点时，客户端仍需要找到要连接的 IP 地址。这些地址不像分片到节点的分配那样变化迅速，因此通常使用 DNS 就足够了。
请求路由 | 267
关于请求路由的讨论主要集中在如何为单个键找到分片，这对于分片型 OLTP 数据库最为相关。分析型数据库也经常使用分片，但它们通常具有非常不同类型的查询执行：而不是在单个分片中执行，查询通常需要并行地聚合和连接来自多个分片的数据。我们将在第11章中讨论这种并行查询执行的技术。
分片与二级索引
到目前为止讨论的分片方案依赖于客户端知道它要访问的任何记录的分区键。这在键值数据模型中最容易实现，其中分区键是主键的第一部分（或整个主键），因此我们可以使用分区键确定分片，从而将读写路由到负责该键的节点。
如果涉及二级索引，情况会变得更加复杂（参见“多列索引与二级索引”第132页）。二级索引通常不唯一标识一条记录，而是搜索特定值出现的方式：查找用户123的所有操作，查找包含单词“hogwash”的所有文章，查找所有颜色为红色的汽车，等等。
键值存储通常没有二级索引，但它们是关系数据库的标准功能，在文档数据库中也很常见。这种索引也是全文搜索引擎（如 Solr 和 Elasticsearch）存在的理由。二级索引的问题在于它们不能整齐地映射到分片。有两种主要方法可以对带有二级索引的数据库进行分片：本地索引和全局索引。
本地二级索引
在第一种索引方法中，每个分片独立维护自己的二级索引，仅覆盖该分片中的记录。它不关心其他分片中存储的数据。每当向数据库写入（添加、删除或更新记录）时，只需要处理包含正在写入记录的分片。因此，这种类型的二级索引被称为本地索引。在信息检索上下文中，它也被称为文档分区索引[29]。
例如，假设你运营一个二手车销售网站。每条列表都有一个唯一 ID，你使用该 ID 作为分片的分区键，如图 7-9 所示（ID 0-499 在分片 0，ID 500-999 在分片 1，等等）。如果你希望允许用户搜索汽车，允许他们按颜色和品牌筛选，则需要在颜色和品牌上建立二级索引（在文档数据库中，这些是字段；在关系数据库中，它们是列）。如果你声明了索引，数据库可以自动执行索引。例如，每当向数据库添加一辆红色汽车时，数据库分片自动将其 ID 添加到索引条目 color:red 的 ID 列表中。如第4章所述，该 ID 列表也称为倒排列表。
图 7-9. 使用本地二级索引，每个分片仅索引其包含的记录。
TIP
如果你的数据库仅支持键值模型，你可能倾向于在应用程序代码中通过创建从值到 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. 全局二级索引反映来自所有分片的数据，并且其本身按索引值分片。
这种索引也称为词项分区[29]。回想一下“全文搜索”第146页，在全文搜索中，词项是文本中可搜索的关键词。这里我们将其泛化为在二级索引中可搜索的任何值。
全局索引使用词项作为分区键，因此当你查找特定词项或值时，可以确定需要查询哪个分片。同样，
第7章：分片
您可以搜索的文本。这里我们将其泛化为任何可以在二级索引中搜索的值。
全局索引使用词条作为分区键，这样当您查找特定词条或值时，就能确定需要查询哪个分片。同样地，一个分片可以包含一个连续的词条范围（如图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, 2023年8月. 存档于 perma.cc/8BTK-8959
[2] Brandur Leach. “Partitioning in Postgres, 2022 Edition.” brandur.org, 2022年10月. 存档于 perma.cc/Z5LE-6AKX
[3] Raph Koster. “Database ‘Sharding’ Came from UO?” raphkoster.com, 2009年1月. 存档于 perma.cc/4N9U-5KYF
[4] Garrett Fidalgo. “Herding Elephants: Lessons Learned from Sharding Postgres at Notion.” notion.com, 2021年10月. 存档于 perma.cc/5J5V-W2VX
[5] Ulrich Drepper. “What Every Programmer Should Know About Memory.” akkadia.org, 2007年11月. 存档于 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, and Vishesh Yadav. “FoundationDB: A Distributed Unbundled Transactional Key Value Store.” 载于 ACM International Conference on Management of Data (SIGMOD), 2021年6月. doi:10.1145/3448016.3457559
[7] Marco Slot. “Citus 12: Schema-Based Sharding for PostgreSQL.” citusdata.com, 2023年7月. 存档于 perma.cc/R874-EC9W
[8] Robisson Oliveira. “Reducing the Scope of Impact with Cell-Based Architecture.” AWS Well-Architected White Paper, Amazon Web Services, 2023年9月. 存档于 perma.cc/4KWW-47NR
[9] Gwen Shapira. “Things DBs Don’t Do—But Should.” thenile.dev, 2023年2月. 存档于 perma.cc/C3J4-JSFW
[10] Malte Schwarzkopf, Eddie Kohler, M. Frans Kaashoek, and Robert Morris. “Position: GDPR Compliance by Construction.” 载于 Towards Polystores That Manage Multiple Databases, Privacy, Security and/or Policy Issues for Heterogenous Data (Poly), 2019年8月. doi:10.1007/978-3-030-33752-0_3
[11] Gwen Shapira. “Introducing pg_karnak: Transactional Schema Migration Across Tenant Databases.” thenile.dev, 2024年11月. 存档于 perma.cc/R5RD-8HR9
[12] Arka Ganguli, Guido Iaquinti, Maggie Zhou, and Rafael Chacón. “Scaling Datastores at Slack with Vitess.” slack.engineering, 2020年12月. 存档于 perma.cc/UW8F-ALJK
[13] Ikai Lan. “App Engine Datastore Tip: Monotonically Increasing Values Are Bad.” ikaisays.com, 2011年1月. 存档于 perma.cc/BPX8-RPJB
[14] Enis Soztutar. “Apache HBase Region Splitting and Merging.” cloudera.com, 2013年2月. 存档于 perma.cc/S9HS-2X2C
[15] Eric Evans. “Rethinking Topology in Cassandra.” 载于 Cassandra Summit, 2013年6月. 存档于 perma.cc/2DKM-F438
[16] Martin Kleppmann. “Java’s hashCode Is Not Safe for Distributed Systems.” martin.kleppmann.com, 2012年6月. 存档于 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, and Akshat Vig. “Amazon DynamoDB: A Scalable, Predictably Performant, and Fully Managed NoSQL Database Service.” 载于 USENIX Annual Technical Conference (ATC), 2022年7月.
[18] David Karger, Eric Lehman, Tom Leighton, Rina Panigrahy, Matthew Levine, and 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), 1997年5月. doi:10.1145/258533.258660
[19] Damian Gryski. “Consistent Hashing: Algorithmic Tradeoffs.” dgryski.medium.com, 2018年4月. 存档于 perma.cc/B2WF-TYQ8
[20] David G. Thaler and Chinya V. Ravishankar. “Using Name-Based Mappings to Increase Hit Rates.” IEEE/ACM Transactions on Networking, 第6卷, 第1期, 第1–14页, 1998年2月. doi:10.1109/90.663936
[21] John Lamping and Eric Veach. “A Fast, Minimal Memory, Consistent Hash Algorithm.” arXiv:1406.2294, 2014年6月.
[22] Samuel Axon. “3% of Twitter’s Servers Dedicated to Justin Bieber.” mashable.com, 2010年9月. 存档于 perma.cc/F35N-CGVX
[23] Gerald Guo and Thawan Kooburat. “Scaling Services with Shard Manager.” engineering.fb.com, 2020年8月. 存档于 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, and Chunqiang Tang. “Shard Manager: A Generic Shard Management Framework for Geo-Distributed Applications.” 载于 28th ACM SIGOPS Symposium on Operating Systems Principles (SOSP), 2021年10月. doi:10.1145/3477132.3483546
[25] Scott Lystig Fritchie. “A Critique of Resizable Hash Tables: Riak Core & Random Slicing.” infoq.com, 2018年8月. 存档于 perma.cc/RPX7-7BLN
[26] Andy Warfield. “Building and Operating a Pretty Big Storage System Called S3.” allthingsdistributed.com, 2023年7月. 存档于 perma.cc/6S7P-GLM4
[27] Rich Houlihan. “DynamoDB Adaptive Capacity: Smooth Performance for Chaotic Workloads (DAT327).” 载于 AWS re:Invent, 2017年11月.
[28] Kostja Osipov. “ScyllaDB’s Safe Topology and Schema Changes on Raft.” scylladb.com, 2024年6月. 存档于 perma.cc/4S82-M277
[29] Christopher D. Manning, Prabhakar Raghavan, and 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, and Jimmy Lin. “Earlybird: Real-Time Search at Twitter.” 载于 28th IEEE International Conference on Data Engineering (ICDE), 2012年4月. doi:10.1109/ICDE.2012.149
[31] Nadav Har’El. “Indexing in Cassandra 3.” github.com, 2017年4月. 存档于 perma.cc/3ENV-8T9P
[32] Zachary Tong. “Customizing Your Document Routing.” elastic.co, 2013年6月. 存档于 perma.cc/97VM-MREN
[33] Andrew Pavlo. “H-Store Documentation: Frequently Asked Questions.” hstore.cs.brown.edu, 2013年10月. 存档于 perma.cc/X3ZA-DW6Z
7.1 分区
图像分析：第283页，图像1
该图片未能加载，无法查看具体内容。根据上下文，图片可能是描述分片（Sharding）的示意图，展示数据如何被拆分并分布到多个节点。
图像分析：第284页，图像1
该图片展示了分布式数据库中的数据分片（Sharding）概念，将数据拆分到多个节点上，每个节点存储一部分数据。
图像分析：第285页，图像1
图片展示了分布式数据库中的分片（Sharding）概念，数据被水平分割并分布到多个节点，每个节点存储一部分数据，以提高可扩展性和写入吞吐量。
图像分析：第286页，图像1
根据上下文，该图片可能展示分片（sharding）和复制（replication）两种分布式数据库数据分布方式的对比示意图。
图像分析：第290页，图像1
图片内容无法获取，根据上下文推测可能展示了分片（Sharding）的架构示意图或数据分布方式。
图像分析：第291页，图像1
图片无法显示，无法分析其具体内容。根据上下文，可能涉及分布式数据库的分片示意图。建议重新提供图片以进行准确分析。
图像分析：第293页，图像1
该图片可能是数据库分片架构图，展示数据被分割到多个节点，每个节点存储一部分数据，以实现水平扩展和提高写入吞吐量。
图像分析：第293页，图像2
图片内容不可见，无法分析图片中的具体信息。
图像分析：第294页，图像1
图片可能展示数据分片（Sharding）的示意图，数据被分割成多个分片并分布在不同节点上，以处理大量数据或高写入吞吐量。