分区

分区通常是这样定义的，即每一条数据（或者每条记录，每行或每个文档）只属于某个特定分区。

采用数据分区的主要目的是提高可扩展性。不同的分区可以放在一个无共享集群的不同节点上。这样一个大数据集可以分散在更多的磁盘上，查询负载也随之分布到更多的处理器上

对单个分区进行查询时，每个节点对自己所在分区可以独立执行查询操作，因此添加更多的节点可以提高查询吞吐量。超大而复杂的查询尽管比较困难，但也可能做到跨节点的并行处理。

分区与复制

分区通常与复制结合使用，即每个分区在多个节点都存有副本。这意味着某条记录属于特定的分区，而同样的内容会保存在不同的节点上以提高系统的容错性。

一个节点上可能存储了多个分区。 如下图，每个分区都有自己的主副本，例如被分配给某节点，而从副本则分配在其他一些节点。一个节点可能即是某些分区的主副本，同时又是其他分区的从副本。

K-V 数据的分区

分区的主要目标是将数据和查询负载均匀分布在所有节点上，如果节点平均分担负载，那么理论上 10 个节点应该能够处理 10 倍的数据量和 10 倍于单个节点的读写吞吐量。

而如果分区不均匀，则会出现某些分区节点比其他分区承担更多的数据量或查询负载，称之为倾斜。倾斜会导致分区效率严重下降，在极端情况下，所有的负载可能会集中在一个分区节点上，这就意味着 10 个节点中 9 个空闲，系统的瓶颈在最繁忙的那个节点上。这种负载严重不成比例的分区即成为系统热点。

避免热点最简单的方法是将记录随机分配到所有节点上。这种方法虽然可以比较均匀地分布数据，但是有个很大的缺点，即当我们试图读取特定的数据时，没有办法知道数据保存在哪个节点上，所以不得不井行查询所有节点。

基于Key的区间分区

一种分区方式是为每个分区分配一段连续的 Key 或者 Key 区间范围（以最小值和最大值来标识）。如果知道 Key 区间的上下限，就可以轻松确定哪个分区包含这些 Key。如果还知道哪个分区分配在哪个节点，就可以直接向该节点发出请求。

每个分区内可以按照 Key 排序保存，这样可以轻松支持区间查询，即将关键字作为一个拼接起来的索引项从而一次查询得到多个相关记录。

然而，基于 Key 的区间分区的缺点是某些访问模式会导致热点。如果 Key 是时间戳，则分区对应于一个时间范围，例如每天一个分区。这会导致该分区在写入时负载过高，而其他分区始终处于空闲状态。因此当 Key 为时间戳或者其他类似的属性时，我们需要对这些 Key 进行修改已保证不会产生大量倾斜。

基于Key的哈希值分区

对于上述数据倾斜与热点问题，许多分布式系统采用了基于 Key 的哈希值来分区。一个好的哈希函数可以处理数据倾斜并使其均匀分布。

一旦找到合适的哈希函数，就可以为每个分区分配一个哈希范围（而不是直接作用于 Key 范围），Key 根据其哈希值的范围划分到不同的分区中。如下图所示：

这种方法可以很好地将 Key 均匀分配到多个分区中。分区边界可以是均匀间隔，也可以是伪随机选择（如一致性哈希）。

然而，通过 Key 的哈希值进行分区，就丧失了良好的区间查询特性。即使 Key 原本相邻，但经过哈希之后会分散在不同的分区中，区间查询就失去了原有的有序相邻的特性。

基于哈希的分区方法可以减轻热点，但无法做到完全避免。如在极端情况下，所有的读/写操作都是针对同一个Key，则最终所有请求都将被路由到同一个分区。如今大多数的系统仍然无法自动消除这种高度倾斜的负载，只能通过应用层来减轻倾斜程度。

分区与二级索引

如果涉及到二级索引，分区的逻辑又会变得更加复杂，因为二级索引通常不能唯一标识一条记录，而是用来加速特定值的查询。

二级索引面临的主要挑战是它们不能规整的映射到分区中。目前有两种主要的方法来支持对二级索引进行分区：基于文档的分区和基于词条的分区。

基于文档来分区二级索引（本地索引）：二级索引存储在与关键字相同的分区，这意味着写入时我们只需要更新一个分区，但缺点是读取二级索引时需要在所有分区上执行分散/聚集。
基于词条来分区二级索引（全局索引）：它是基于索引的值而进行的独立分区。二级索引中的条目可能包含来自关键字的多个分区里的记录。在写入时，不得不更新二级索引的多个分区。但读取时，则可以从单个分区直接快速提取数据。

基于文档分区的二级索引

在这种索引方法中，每个分区完全独立，各自维护自己的二级索引，且只负责自己分区内的文档而不关心其他分区中的数据。每当需要写数据库时，包括添加，删除或更新文档等，只需要处理包含目标文档 ID 的那一个分区。因此文档分区索引被称为本地索引，而不是全局索引。

如上图，由于数据可能分布在不同分区中，在读取时我们就需要将查询发送到所有的分区，然后合并所有返回的结果。这种查询分区数据库的方法被称为分散/聚集，其二级索引的查询代价高昂。即使采用了并行查询，也容易导致读延迟显著放大。

基于词条分区的二级索引

我们对所有的数据构建全局索引，而不是每个分区维护自己的本地索引。而且，为避免成为瓶颈，不能将全局索引存储在一个节点上，否则就破坏了设计分区均衡的目标。所以，全局索引也必须进行分区，且可以与数据关键字采用不的分区策略。我们将这种索引方案称为词条分区，它以待查找的关键字本身作为索引。

这种全局的词条分区相比于文档分区索引的主要优点是，它的读取更为高效，即它不需要采用分散/聚集对所有的分区都执行一遍查询，相反，客户端只需要向包含词条的那个分区发出读请求。

然而全局索引的不利之处在于其写入速度较慢且非常复杂，主要因为单个文档更新时，里面可能会涉及多个二级索引，而二级索引的分区又可能完全不同甚至在不同的节点上，由此势必引人显著的写放大。

分区再平衡

随着时间的推移，数据库可能总会出现某些变化：

查询压力增加，因此需要更多的 CPU来处理负载。
数据规模增加，因此需要更多的磁盘和内存来存储数据。
节点可能出现故障，因此需要其他机器来接管失效的节点。

所有这些变化都要求数据和请求可以从一个节点转移到另一个节点。这样一个迁移负载的过程称为再平衡（或动态平衡）。无论对于哪种分区方案，分区再平衡通常至少要满足：

平衡之后，负载、数据存储、读写请求等应该在集群范围更均匀地分布。
再平衡执行过程中，数据库应该可以继续正常提供读写服务。
避免不必要的负载迁移，以加快动态再平衡，井尽量减少网络和磁盘 I/O 影响。

动态再平衡

固定数量的分区

创建远超实际节点数的分区数，然后为每个节点分配多个分区。 例如一个 10 节点的集群，数据库可以从一开始就逻辑划分为 1000 个分区，这样大约每个节点承担 100 个分区。如果集群中添加了新节点，该新节点可以从每个现有的节点上匀走几个分区，直到分区再次达到全局平衡。如果从集群中删除节点，则采取相反的均衡措施。具体逻辑如下图所示：

原则上，也可以将集群中的不同的硬件配置因素考虑进来，即性能更强大的节点将分配更多的分区，从而分担更多的负载。目前 Riak、Elasticsearch、Couchbase、Voldemort 都支持这种动态平衡方法。

动态创建分区

因此，一些数据库如 HBase 和 RethinkDB 等采用了动态创建分区。当分区的数据增长超过一个可配的参数阔值时，它就拆分为两个分区，每个分区承担一半的数据。相反，如果大量数据被删除，并且分区缩小到某个阈值以下，则将其与相邻分区进行合井。该过程类似于 B 树的分裂操作。

动态分区的一个优点是分区数量可以自动适配数据总量。如果只有少量的数据，少量的分区就足够了，这样就减轻了系统的开销；如果有大量数据，每个分区的大小则被限制一个可配置的最大值。 因此分区的数量与数据集的大小成正比关系。

按节点比例分区

在前面两种方法中，分区的数量都与数据集大小有关，而与节点数无关。而 Cassandra 和 Ketama 采用了第三种方式，使分区数与集群节点数成正比关系。换句话说，每个节点具有固定数量的分区。

此外，当节点数不变时，每个分区的大小与数据集大小保持正比的增长关系。当节点数增加时，分区则会调整变得更小。较大的数据量通常需要大量的节点来存储，因此这种方法使每个分区大小保持稳定。

当一个新节点加入集群时，它随机选择固定数量的现有分区进行分裂，然后拿走这些分区的一半数据量，将另一半数据留在原节点。

手动与自动再平衡

动态平衡的执行方式有以下几种：

手动再平衡：分区到节点的映射由管理员来显式配置。
全自动再平衡：由系统自动决定何时将分区从一个节点迁移到另一个节点，不需要任何管理员的介入。
半自动再平衡：自动生成分区分配的建议方案，但需要管理员的确认才能生效。如 Couchbase，Riak 和 Vodemort。

全自动式再平衡会更加方便，它在正常维护之外所增加的操作很少。但是，也有可能出现结果难以预测的情况。再平衡总体讲是个比较昂贵的操作，它需要重新路由请求并将大量数据从一个节点迁移到另一个节点。万一执行过程中间出现异常，会使网络或节点的负载过重，并影响其他请求的性能。

基于以上描述综合考虑，半自动再平衡可能是个更好的选择。虽然它比全自动再平衡响应慢，但它可以有效防止意外发生。

请求路由

当客户端需要发送请求时，如何知道应该连接哪个节点呢？这其实属于一类典型的服务发现问题，这个问题有以下几种不同的处理策略：

允许客户端连接任何一个的节点，如果某节点恰好拥有所请求的分区，则直接处理该请求；否则，将请求转发到下一个合适的节点，接收答复，并将答复返回给客户端。
将所有客户端的请求都发送到路由层，由后者负责将请求转发到对应的分区节点上。路由层本身不处理任何请求，它仅充当一个分区感知的负载均衡器。
客户端感知分区和节点的分配关系。此时，客户端可以直接连接到目标节点，而不需要任何中介。

许多分布式数据系统依靠独立的协调服务（如 ZooKeeper ）跟踪集群范围内的元数据，如下图所示：

每个节点都向 ZooKeeper 注册自己， ZooKeeper 维护了分区到节点的最终映射关系。其他参与者（路由层或分区感知的客户端）可以向 ZooKeeper 订阅此信息。一旦分区发生了改变，或者添加、删除节点， ZooKeeper 就会主动通知路由层，这样使路由信息保持最新状态。