本节我们讨论一下数据分区中的两个概念：再平衡（Rebalance）和请求路由。
分区的Rebalance
在数据库的使用中，可能会遇到以下场景：
- 查询量增加，需要增加更多的CPU处理负载；
- 数据量增加，需要增加更多的磁盘的RAM来存储；
- 一台机器崩溃，其他机器需要共同接管失败机器的请求。
所有这些变化都涉及到数据和请求从一个节点移动到另一个节点，这个过程称为Rebalance。
无论使用什么样的分区方式，rebalance至少需要满足以下的要求：
- 在rebalance之后，数据存储和读写请求的负载，在集群中节点应该是相同的；
- 在rebalance的过程，数据库可以持续处理读和写；
- 节点间只移动必要的数据，以尽可能提高rebalance的速度，减少网络和磁盘I/O的负载。
Rebalance的策略
不要使用hash模N的方式
hash模N的方式为，假如有10个节点，计算key的Hash值，模10之后的结果在0到9之间，将请求分配到该数字对应的节点上。
这种方式的问题是，N数量的变化，会导致大多数的key对应的节点发生移动，可以参考这篇文章。因此我们需要寻找一种尽可能少移动数据的方式。
固定数量的分区
一种简单的解决方式是，创建多于节点数量的分区，每个节点存在多个分区。比如，数据库运行在10个节点的集群上，数据分为1000个分区，每个节点处理大约100个分区的数据。
如果添加一个节点，该节点从其他节点中获取一部分分区，直到分区在节点间重新平均分配，该过程如下图所示。
节点间移动的是整个分区，分区的数量并没有变化，每个key对应的分区也没有变化，变化的是分区和节点之间的关系。这个过程需要一些时间，因此在移动的过程中，仍由分区原来的节点处理该分区的读和写。
这种分配方式，使得可以在集群中使用不同性能的硬件，只需要为性能好的节点分配更多的分区数即可。
这里分区的数量是在数据库初始化时设置好的，不能更改的。理论上可以进行分区的分割和合并，但为了保证操作简单，许多固定分区数的数据库会选择不实现分区的分割。因此需要在选择分区数的时候，考虑未来可能的数据增长。如果数据量变化很大时，选择合适的分区数并不容易，太大的话会使rebalance和恢复的成本更高，太小的话会可能出现节点过载。
动态分区
对于使用key范围分区的数据库，比如HBase和RethinkDB，可以使用动态分区的方式。当分区增长到设置好的大小（比如10G）时，分区会分割为两个差不多大小相等的分区，一个分区可以移动到其他节点上；如果分区数据减少到某个阈值，会和相邻的分区合并为一个分区。这个过程很像之前讨论过的B树。
动态分区的好处就是可以根据数据量，动态的调整分区的数量。一般在数据库初始化时，预先设置好几个分区，称为预分割，然后再此基础上进行分区的动态调整。
动态分区不仅适用于按Key范围分区的数据，也可以用在Hash分区的数据上。
按节点分区
动态分区的方式，使得每个分区的大小保持在一个固定的最大值和最小值之间。固定数量的分区，分区的大小和数据集大小有关。这两种方式的分区数都和节点数是无关的。
Cassandra和Ketama使用的方式，是每个节点有固定数量的分区，当总数据量增加时，每个分区的数据增加，但节点的分区数是不变的。当增加了节点的数量，分区会重新变小。因此数据量越多，需要的节点数越多，每个分区的数据量是均等的。
当增加新节点时，随机选择一些分区进行分裂，并将其中一半存储在新节点上。当每个节点的分区数足够多时，分裂的结果是相对比较平等的。分区的边界的选择通常需要基于Hash的分区策略，也就是分区边界是通过Hash函数计算得出的。
运维：自动和手动Rebalance
Rebalance的过程应该是自动还是手动的呢？采用全自动的方式会降低运维的复杂度，但可能会导致不可预期的行为。比如当一个节点因为过载而无法响应请求时，集群的Rebalance会加剧过载的情况。因此最好在Rebalance的过程中增加人工干预的环节，虽然会比全自动Rebalance慢，但可以减少运维的意外情况。
请求路由
数据分区后存储在不同的节点上，那么客户端在请求数据时，需要连接哪个节点呢？这个问题可以推广到一个更普遍的问题：服务发现，不仅在数据库，在其他目标是高可用的软件中都会用到，也有很多公司的开源实现。
从更高的抽象层面，请求路由有以下几种实现方式：
- 允许客户端以轮询的方式访问所有节点，如果访问的节点包括想要的数据，可以直接处理该请求；否则将请求转发到正确的节点上，接收返回信息并传送到客户端上。
- 客户端的请求发送到路由节点上，路由节点决定由哪个节点处理该请求并转发。路由节点并不处理请求，而是作为类似分区级别的负载均衡器。
- 将分区到节点的分配信息通知到客户端，客户端直接访问正确的节点，没有中间途径。
无论哪种方式，难点在于负责路由的组件如何得知节点上分区分配的变化。否则请求可能会发送到错误的节点上，使得请求无法处理。
需要分布式数据系统会使用ZooKeeper管理集群的元数据。每个节点都注册在ZooKeeper上，并在ZooKeeper保存分区和节点的映射关系。其他路由节点或者客户端订阅ZooKeeper的信息，ZooKeeper将映射关系的变化通知给路由节点或客户端。
比如LinkedIn的Espresso，使用Helix进行分区管理；HBase、SolrCloud和Kafka使用ZooKeeper记录分区的分配；MongoDB依赖自己的配置服务器。
Cassandra和Riak使用Gossip协议，将集群状态传播到每个节点上，这样请求可以发到任意一个节点上，并转发到正确的节点上。这种模型引入了更多的复杂性，但可以减少对外部组件，比如ZooKeeper的依赖。
Couchbase不能自动进行rebalance，它会配置一个路由节点moxi，获取到集群节点路由信息的变化。
当路由节点发送请求到随机一个节点时，客户端仍然需要知道路由节点的IP地址，但由于该地址的变化不太频繁，一般使用DNS就足够了。
并行查询的执行
之前讨论的都是针对一个key的简单的读写请求，用于分析的数据库会支持更加复杂的MPP（大量并行查询）的场景，一个典型的数据仓库的查询包括关联、过滤、分组和聚合等操作。MPP的查询优化器将复杂的查询转换为一系列的执行阶段和分区，许多是可以在不同节点上并行执行的。特别是查询需要扫描大量的数据，会从并行执行中手艺。
这部分的内容会在后面的章节进一步介绍。
小结
本节介绍了数据分区中的Rebalance和请求路由的相关概念和实现方式，Rebalance有三种方式：固定数量的分区、动态分区和按节点分区。路由通常是通过使用外部一致性中间件ZooKeeper辅助完成。
