综述

本章主要介绍了切分大型数据集的若干方法，即如何分区；再讨论数据索引如何影响分区；接下来讨论了分区的再平衡，这对动态添加和删除节点非常重要；最后介绍了如果将请求路由到正确的分区并执行查询。

什么是分区

上一篇讨论了数据复制技术，即在不同的节点保存相同数据的多个副本，提升系统吞吐量。然而，面对一些海量数据集或者非常高的查询压力，复制技术还不够，我们还需要将数据拆分成为分区，也成为分片。
分区定义：每一条数据只属于某一个特定分区。

数据分区的主要目的是提高可扩展性。分区的主要目的是将数据和查询负载均匀分布在所有节点上，而如果分区不均匀，则会出现某些分区节点比其他分区节点承担更多的数据量或者查询负载，称之为倾斜。

如何分区

键-值数据的分区

假设数据是简单的键-值数据模型，这意味着总是可以通过关键字来访问记录。

基于关键字区间分区

为每个分区分配一段连续的关键字或者关键字区间范围（以最小值和最大值来指示），参考理解字典的目录。关键字的区间不一定非要均匀分布，这主要是因为数据本身可能就不均匀。为了更均为的分布数据，分区边界理应适配数据本身的分布特性。
分区边界可以有管理员手动确定，或者有数据库自动选择。
每个分区内可以按照关键字排序保存，方便支持区间查询。
然而，基于关键字的区间分区的特点就是某些访问模式会导致热点，如果关键字是时间戳，分区对应于一个时间范围。这会导致所有当天写入集中到了一个分区，造成热点。为避免这个问题，使用时间戳以外的其他内容作为关键字的第一项。

基于关键字哈希值分区

好的哈希函数可以处理数据倾斜并使其均匀分布，哈希函数：MongoDB使用MD5、Voldmort使用Fowler-Noll-Vo.
关键字哈希分区，会丧失良好的区间查询特性。

分区与二级索引

键-值模型相对简单，即都是通过关键字访问记录，自然可以根据关键字来确定分区，并将读写请求路由到负责该关键字的分区上。但是如果涉及二级索引，情况会变得复杂，二级索引通常不能唯一标识一条记录，而是用来加速特定值的查询，比如：查找用户123的所有操作，查找颜色为红色的汽车等等...
二级索引是关系数据库的必备特性，在文档数据库中应用也非常普遍。二级索引也是Solr和Elasticsearch等全文索引服务器的存在根本。二级索引带来的主要挑战是他们不能规整的映射到分区中，有两种主要的方法来支持对二级索引进行分区：基于文档的分区和基于词条的分区。

分区再平衡

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

• 查询压力增加，因此需要更多的CPU处理负载。
• 数据规模增加，因此需要更多的磁盘和内存来存储数据。
• 节点可能故障，因此需要其他机器来接管失效的节点。
  所有这些变化都要求数据和请求可以从一个节点转移到另一个节点，这个迁移的过程就是再平衡。
  分区再平衡至少要满足的条件：
• 平衡之后，负载、数据存储、读写请求等应该在集群范围内更均匀的分布。
• 再平衡执行过程中，数据库应该可以继续正常提供读写服务。
• 避免不必要的负载迁移，以加快动态平衡，并尽量减少网络和磁盘I/O的影响。

动态平衡策略

1.取模策略。当增加节点时，数据会频繁的迁移。
2.固定数量的分区。指首先，创建远超过实际节点数的分区数，然后为每个节点分配多个分区。当集群增加新节点时，该节点可以从每个现有的节点允走几个分区，知道分区再次达到全局平衡。
3.动态分区（如Hbase）。当分区的数据增加超过一个可配置的参数阈值时，它就会拆分，相反也有进行合并的操作。动态分区的一个优点是分区数量自动适配数据的总量。

4.按节点比例分区。分区数与集群节点数成正比关系，换句话说，每个节点具有固定数量的分区。
动态平衡可以自动执行或者手动执行，而管理员介入是更加安全和推荐的。

请求路由

当客户端需要发送请求时，如何知道应该连接哪个节点？如果发生了分区再平衡，分区和节点的对应关系也会随之发生改变。这里是一个典型的服务发现问题。
处理策略：
1.允许客户端链接任意的节点。如果被请求节点恰好拥有所请求的分区，则直接处理请求；否则，将请求转发到下一个合适的节点。
2.将所有客户端请求发送到一个路由层（个人理解类似于网关），由路由层将请求转发到对应的分区。路由层本身不处理任何请求，仅仅当做分区感知的负载均衡器。
3.客户端感知分区和节点分配关系。此时，客户端可以直接连接到目标节点，而不需要中介。

核心问题是：做出路由决策的组件如何知道分区与节点的对应关系以及其变化情况。
/这里引入了共识协议算法；ZooKeeper提供协调服务。/