在上一节的复制算法中，有个前提是单个节点可以存储全量的数据。对于数据量特别大，单个节点无法存储全量数据需要怎么处理呢？

本章将介绍数据分布在多个节点中的另一种方式：分区。分区是将全量数据进行切分，将拆分的数据存储到不同节点上。由于分区是存储部分数据，可以将数据写入和读取的负载降低，存储数据总量也可以超出单点的瓶颈。然而，分区也带了一些问题需要解决：如何对数据进行拆分，如何建立次级索引，如何保证数据查询，如何确保写入和查询负载是均衡的，如何确保请求到对应的分区？本章将讨论这些问题。

分区方式

分区的目标是将数据存储到不同的节点上。将数据和查询负载均匀的分配到各个节点上。如何分区是不公平的，一些分区比其他分区有更多的数据或查询，我们称之为偏斜（skew）。数据偏斜会导致分区的效率下降。在极端的情况下，所有的负载会压在一个分区上，不均衡导致的高负载分区被称之为热点（hot spot）。

下面将介绍两种常见的分区方式：按照键值分区和按照键的范围分区。

键散列分区

最简单的分区方式就是使用散列函数确定分区。一个好的散列函数可以保证数据均匀的分布在每个分区上。如下图所示，总共划分了 8 个分区，每个区负责制定的散列范围。对给定的键值进行 md5 运算，通过前两个字节确定存储的分区。

按照键的值进行散列，可以直接快速定位到每个值的具体分区。缺点就是无法高效的进行范围查询。任何范围查询都将要发送到全部的分区，然后进行聚合。

有些数据库会使用组合索引。例如：在一个社交媒体网站上，一个用户会发布许多更新。如果更新的主键为（user_id， update_timestamp），那么可以有效的检索特定用户在某个时间段内按照时间戳排序的所有更新。在具体存储的时候，利用 user_id 计算存储的分区，在分区内部使用 LSM 树对 update_timestamp 进行排序存储。

键范围分区

为了解决范围查询的问题，可以将键的值进行排序，按照键范围进行分区。如下图所示，按照书名的字母序进行分区。

在每个分区中，按照一定的顺序保存键。这样可以高效的进行范围查询。使用键范围查询容易造成数据分布不均匀或者导致热点。例如：以时间戳存储传感器的数据，可以每天选择一个分区，可以快速每天的数据。然后，业务上往往查询最近几天的数据，从而造成查询热点。常见的解决方案是先按照传感器的编号进行分区，分区内部使用时间戳排序。

负载偏斜和热点消除

使用散列分区可以很好的解决数据倾斜和热点问题。但是，极端情况下仍然会导致热点问题的产生。例如：一个微博热点，会导致同一个键对应的值对被大量的读。最常见的方案就是应用层进行处理，在 key 的后面加两个随机数，从而让 key 路由到不同的分片。当然，这就需要应用程序记录那些键是需要随机处理，以及写入的时候将这些键的值存储到不同的分区。

也许在未来，数据系统能自动进行检测和补偿倾斜的负载。目前，仍需要应用程序进行相应的处理。

分区与次级索引

目前只介绍了基于主键的存储与查询。在之前的文章里，介绍了次级索引，用于满足业务上复杂的业务场景。在分区场景下，次级索引处理起来相对比较麻烦。核心问题在于如何通过次级索引映射到具体的分区。目前有两种方法使用次级索引对数据进行分区：基于文档的分区和基于关键词的分区。

基于文档的次级索引

基于文档的次级索引：在这种索引方法中，每个分区是独立的，分区内维护自己的次级索引。它不关心存储到其他分区的数据。因此，文档分区索引也叫本地索引。

如下图所示，是一个使用文档分区索引的例子。共有两个分区，P0「0-499」，p1「500-999」。为了支持通过颜色进行查询，创建了 color 次级索引。数据写入时，先确定数据需要存储的分区，然后更新分区内部的二级索引。数据查询时，需要将请求发送到所有的分区，然后将各个分区的结果进行聚合返回。

使用本地索引的优点在于数据写入性能高，缺点就是需要并行查询所有节点，会导致尾部延迟放大。

基于关键词的次级索引

与文档索引对应的就是全局索引。但是，我们不能把这个索引放到一个节点上，避免单点依赖。和主键一样，可以对次级索引进行分区，每个分区维护不同的索引值。

如下图所示，对于次级索引 color，首字母从 a-r 的颜色放到 P0 中，s-z 存储到 P1 中。当数据写入时，根据主键计算分区，将数据存储到分区中；然后计算次级索引的分区，更新次级索引。通过次级索引查询数据时，直接计算对应的分区，查询所有数据。

将这种索引称为关键词分区，其本质是按照关键词进行分区。基于关键词分区的优势在于查询性能高，不用并行的区多个分区查询数据；缺点就是写入复杂，需要同步更新次级索引。

在具体实践中，次级索引的更新往往是异步的，即不一定能保证数据写入成功后，能及时通过次级索引查到写入的数据。

分区再平衡

随着时间推移，当数据集增加、查询吞吐量增加，机器故障时，需要增加节点解决问题。这就涉及到将数据从一个节点迁移到另一个节点，我们称之为再平衡。

再平衡策略

下面将介绍再平衡的一些方法。

哈希取模

哈希取模：对主键进行哈希运算，然后取余得到对应的分区。例如：节点数据为 N，hash(key)%N 得到对应的分区。

哈希取模的问题在于，如果节点数量发生变化，则需要大量的数据从一个节点迁移到另一个节点，造成不必要的开销。例如：hash(key) = 123456。节点数量从 10 增长到 11 然后增长到 12，每次节点增加均需要进行数据变更「节点从 6 到 3 再到 0」。因此，这也是最不推荐的分区方式。

固定数据分区

再平衡最需要解决的问题就是尽可能避免非必要的数据移动，同时又要保证负载均衡。另一种解决方案就是创建比节点数量更多的分区，每个节点分配多个分区。

如下图所示：系统中共有 4 个节点，一共创建 20 个分区，每个节点分配五个分区。当需要新增节点 4 时，从每个节点窃取一个分区。删除节点则执行相反的操作。

使用固定数据数量分区的形式，可以根据节点的性能分配不同数量的分区。使用这种方式可以保证同条记录的分区是固定的，不会发生变动。变动的只是分区所在的节点。因此，需要有一个元数据维护分区与节点的关系。

在固定分区算法中，分区的数量是不能动态更改的。分区的数量选择往往比较重要。分区数量越多，则需要负责的分区计算。如果分区数量较小，分区发生迁移时需要移动的数据就越多。

动态分区

在键范围分区中，为每个节点分配了固定的范围。如果新增节点，则需要手动配置每个节点对应边界。

现在可以使用一种动态分区的方式来避免手动配置。当分区的数据增长到配置的大小时，将会对分区进行分割，每个分区占用节点的一般数据。与之相反，当大量的数据删除时，则会合并分区。

动态分区的优点在于分区的数量会随着数量的增大而增大，随着数据量的减少而减少。

运维：手动 or 自动

再平衡是一个复杂的操作，涉及到数据从一个节点迁移到另一个节点。这中间涉及到种种细节，节点什么时候提供服务、如何确保数据迁移完成等。

全自动的模式的优点在于响应及时，无需人工介入。但缺点就是如何保证算法没有误判。例如，一个节点查询负载升高，如果此时新增节点，会导致数据迁移造成更大的负载，导致级联失败。

使用手动模式最大的缺点就是人工响应。优点在于可以依据真实的情况作出响应。

请求路由

现在我们已经可以将数据分割到多个节点上进行存储。然后，有一个问题还没有讨论。即客户端发送请求时，如何知道要连接那个节点，具体的 ip 和端口号。

针对这个问题，常见的解决方案有下面三种方案：

• 允许客户端连接任意节点，如果节点能处理此请求则直接处理，如果不能处理则转发到对应节点。
• 客户端统一连接到一个路由层，路由层决定请求到那个节点。路由层本身不处理任何请求，它是对消息进行转发。
• 客户端直接知道分区的分配，以及对应的节点。

在上面的三种方案中，均需要解决一个问题，如何知道分区的策略，以及感知节点和分区的变化关系？

在需要分布式系统中，均会引入一个独立的协调服务，比如 ZooKeeper 来跟踪集群原数据。如图所示，每个节点会向 ZK 中注册自己，ZK 维护了节点的映射。路由层订阅 ZK 的信息，从而路由到对应的节点。如果分区配置发生变化，ZK 会通知路由层变更映射信息。

当然，有些数据库系统为了减少服务依赖，会放弃 ZK，使用相关协议在不同节点之间来传播映射关系。

总结

相比于复制，分区是将全部数据划分到一个个区块中，然后在节点上存储不同分区的数据。从而避免了全部数据存储到一个节点上。分区需要解决的首个问题就是将数据拆分到不同分区的方式：

• 按键散列分区：对键进行哈希运算，根据哈希值决定存储的分区。数据相对分散，无法范围查询。
• 按键范围分区：为每个分区划定绝体的键范围。方便范围查询，容易造成数据不均衡。

其次，在分区场景下，还需要考虑二级索引的存储方式。目前有一下两种方式：

• 本地索引。每个分区维护自己的索引，不会考虑其他分区的数据。查询时，需要并行查询所有分区。
• 全局索引。根据次级索引进行分区，每个分区存储这个索引值下的所有数据。避免了并发查询，写入可能依赖事务。

随着系统的不断运行，数据量会不断增长，则需要涉及节点的增加或迁移。这一过程叫做再平衡。常见的方式有：

• 哈希取模。取模确定分区。节点增加会导致大量数据迁移。
• 固定分区数量。将分区和节点解藕。为每个节点分配一定数据量的分区。
• 动态分区。基于键范围的分区下，当分区容量大于配置值，则将分区拆分为两个分区。

无论是使用哪种分区方式，客户端请求时均需要路由到对应的节点。通常引入 ZK 来维护分区的映射关系。然后，将客户端请求路由到最终节点的方式又分多种：

• 请求到任意节点。节点内部维护分区映射关系。需要节点额外维护数据。
• 统一请求到路由层。统一由路由层确保请求需要到那一个节点。对路由层依赖较高。
• 客户端直接请求到对应的节点。客户端需要订阅分区配置信息。