分区再平衡

随着时间的推移，数据库会有各种变化。

• 查询吞吐量增加，所以您想要添加更多的CPU来处理负载。
• 数据集大小增加，所以您想添加更多的磁盘和RAM来存储它。
• 机器出现故障，其他机器需要接管故障机器的责任。

所有这些更改都需要数据和请求从一个节点移动到另一个节点将负载从集群中的一个节点向另一个节点移动的过程称为再平衡（reblancing）。无论使用哪种分区方案，再平衡通常都要满足一些最低要求：

• 再平衡之后，负载（数据存储，读取和写入请求）应该在集群中的节点之间公平地共享。
• 再平衡发生时，数据库应该继续接受读取和写入。
• 节点之间只移动必须的数据，以便快速再平衡，并减少网络和磁盘I/O负载。

hash mod N

在分片策略中我们讨论过最好将可能的哈希分成不同的范围，并将每个范围分配给一个分区（例如，如果$0≤hash(key)<b_0$，则将键分配给分区0，如果$b_0 ≤ hash(key) <b_1$，则分配给分区1）。

也许你想知道为什么我们不使用mod（许多编程语言中的％运算符）。例如，hash(key) mod 10会返回一个介于0和9之间的数字（如果我们将哈希写为十进制数，哈希模10将是最后一个数字）。如果我们有10个节点，编号为0到9，这似乎是将每个键分配给一个节点的简单方法。

模$N$方法的问题是，如果节点数量N发生变化，大多数密钥将需要从一个节点移动到另一个节点。例如，假设$hash(key)=123456$。如果最初有10个节点，那么这个键一开始放在节点6上（因为$123456\ mod\ 10 = 6$）。当您增长到11个节点时，密钥需要移动到节点3（$123456\ mod\ 11 = 3$），当您增长到12个节点时，需要移动到节点0（$123456\ mod\ 12 = 0$）。这种频繁的举动使得重新平衡过于昂贵。

固定数量的分区

针对上面的问题，我们可以创建比节点更多的分区，并为每个节点分配多个分区。例如，运行在10个节点的集群上的数据库可能会从一开始就被拆分为1,000个分区，因此大约有100个分区被分配给每个节点。

现在，如果一个节点被添加到集群中，新节点可以从当前每个节点中窃取一些分区，直到分区再次公平分配。如果从集群中删除一个节点，则会发生相反的情况。只有分区在节点之间的移动。分区的数量不会改变，键所指定的分区也不会改变。唯一改变的是分区所在的节点。这种变更并不是即时的，在网络上传输大量的数据需要一些时间，所以在传输过程中，原有分区仍然会接受读写操作。

原则上，您甚至可以解决集群中的硬件不匹配问题：通过为更强大的节点分配更多的分区，可以强制这些节点承载更多的负载。在Riak，Elasticsearch，Couchbase和Voldemort中使用了这种再平衡的方法。在这种配置中，分区的数量通常在数据库第一次建立时确定，之后不会改变。虽然原则上可以分割和合并分区，但固定数量的分区在操作上更简单，因此许多固定分区数据库选择不实施分区分割。因此，一开始配置的分区数就是您可以拥有的最大节点数量，所以您需要选择足够多的分区以适应未来的增长。但是，每个分区也有管理开销，所以选择太大的数字会适得其反。

如果数据集的总大小难以预估（例如，如果它开始很小，但随着时间的推移可能会变得更大），选择正确的分区数是困难的。由于每个分区包含了总数据量固定比率的数据，因此每个分区的大小与集群中的数据总量成比例增长。如果分区非常大，再平衡和从节点故障恢复变得昂贵。但是，如果分区太小，则会产生太多的开销。当分区大小“恰到好处”的时候才能获得很好的性能，如果分区数量固定，但数据量变动很大，则难以达到最佳性能。

动态分区

对于使用键范围分区的数据库，具有固定边界的固定数量的分区将非常不便：如果出现边界错误，则可能会导致一个分区中的所有数据或者其他分区中的所有数据为空。手动重新配置分区边界将非常繁琐。出于这个原因，按键的范围进行分区的数据库（如HBase和RethinkDB）会动态创建分区。当分区增长到超过配置的大小时（在HBase上，默认值是10GB），会被分成两个分区，每个分区约占一半的数据。与之相反，如果大量数据被删除并且分区缩小到某个阈值以下，则可以将其与相邻分区合并。此过程与B树顶层发生的过程类似。

每个分区分配给一个节点，每个节点可以处理多个分区，就像固定数量的分区一样。大型分区拆分后，可以将其中的一半转移到另一个节点，以平衡负载。在HBase中，分区文件的传输通过HDFS（底层分布式文件系统）来实现。动态分区的一个优点是分区数量适应总数据量。如果只有少量的数据，少量的分区就足够了，所以开销很小;如果有大量的数据，每个分区的大小被限制在一个可配置的最大值。

需要注意的是，一个空的数据库从一个分区开始，因为没有关于在哪里绘制分区边界的先验信息。数据集开始时很小，直到达到第一个分区的分割点，所有写入操作都必须由单个节点处理，而其他节点则处于空闲状态。为了解决这个问题，HBase和MongoDB允许在一个空的数据库上配置一组初始分区（这被称为预分割（pre-splitting））。在键范围分区的情况中，预分割需要提前知道键是如何进行分配的。

动态分区不仅适用于数据的范围分区，而且也适用于哈希分区。从版本2.4开始，MongoDB同时支持范围和哈希分区，并且都是进行动态分割分区。

按节点比例分区

通过动态分区，分区的数量与数据集的大小成正比，因为拆分和合并过程将每个分区的大小保持在固定的最小值和最大值之间。另一方面，对于固定数量的分区，每个分区的大小与数据集的大小成正比。在这两种情况下，分区的数量都与节点的数量无关。Cassandra和Ketama使用的第三种方法是使分区数与节点数成正比，即每个节点具有固定数量的分区。

在这种情况下，每个分区的大小与数据集大小成比例地增长，而节点数量保持不变，但是当增加节点数时，分区将再次变小。由于较大的数据量通常需要较大数量的节点进行存储，因此这种方法也使每个分区的大小较为稳定。当一个新节点加入集群时，它随机选择固定数量的现有分区进行拆分，然后占有这些拆分分区中每个分区的一半，同时将每个分区的另一半留在原地。随机化可能会产生不公平的分割，但是平均在更大数量的分区上时（在Cassandra中，默认情况下，每个节点有256个分区），新节点最终从现有节点获得公平的负载份额Cassandra 3.0引入了另一种再分配的算法来避免不公平的分割。

随机选择分区边界要求使用基于哈希的分区（可以从哈希函数产生的数字范围中挑选边界）。实际上，这种方法最符合一致性哈希的原始定义。最新的哈希函数可以在较低元数据开销的情况下达到类似的效果。

运维策略

在全自动重新平衡（系统自动决定何时将分区从一个节点移动到另一个节点，无须人工干预）和完全手动（分区指派给节点由管理员明确配置，仅在管理员明确重新配置时才会更改）之间有一个权衡。例如，Couchbase，Riak和Voldemort会自动生成建议的分区分配，但需要管理员提交才能生效。

全自动重新平衡可以很方便，因为正常维护的操作工作较少。但是，这可能是不可预测的。再平衡是一个昂贵的操作，因为它需要重新路由请求并将大量数据从一个节点移动到另一个节点。如果没有做好，这个过程可能会使网络或节点负载过重，降低其他请求的性能。

这种自动化与自动故障检测相结合可能十分危险。例如，假设一个节点过载，并且对请求的响应暂时很慢。其他节点得出结论：过载的节点已经死亡，并自动重新平衡集群，使负载离开它。这会对已经超负荷的节点，其他节点和网络造成额外的负载，从而使情况变得更糟，并可能导致级联失败。

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