大话数据分区

所谓数据分区，在不同的系统中有不同的称呼：例如ES中的shard，Hbase的region，Bigtable的tablet等等。

定义

分区：每一条数据（或者每条记录，每行，每个文档）只属于某个特定分区。而每个分区又可以看成一个完整的小数据库。

目的

采用数据分区的主要目的是：提高可扩展性。不同分区放在一个无共享集群的不同节点上（简单说就是不放在同一个机架中）。因此，数据将分散在更多的磁盘上，查询负载便可以得到均衡，另外也可以提高查询吞吐量。在面对超大且复杂的查询时，便可以在不同分区进行并行处理。

分布式架构

[image:9E6B926D-05D5-482E-99A1-8C838D12FCF6-11683-000010F7F9FBE345/bear_sketch@2x.png]
上图是一个主从复制模型于分区组合使用时数据的分布情况：每个分区都有自己的主副本，也有一些在其他节点的从副本。

分区方案

键——值的数据分区

回到刚才我们所说的目标：提高可扩展性，那我们就可以设想一种情况：10个节点因该能处理10倍的数据量和10倍于单个节点的读写吞吐量（这里忽略了复制所带来的性能消耗）。

这里引入一个概念“倾斜”，所谓倾斜就是指如果分区不均匀，会出现某些分区节点比其他分区承受更多的数据量/查询负载。这就会导致小查询效率严重下降，在极端情况下，甚至倾斜到一个分区节点上，而这个最繁忙的节点就被称为“系统热点”。为了避免这种情况，我们可以将记录随机分配给所有节点，而不考虑其他应用层的要求。但是当读取特定的数据的时候，没有办法知道数据保存在哪个节点上（这里没有考虑副本间的复制），所以又不得不并行查询所有节点。

因此可以通过基于键值的数据模型来设计分区：即通过关键字来访问记录。另外可以再优化一下查询速度，对其进行排序等操作，使用类似于LSM-Tree/BTree的数据结构来进行设计。

基于关键字区间的数据分区

通过对关键字的排序，就可以得到关键字区间，将每个分区分配一段连续的关键字区间范围，在查询时就可以轻松定位到具体的分区位置，甚至可以直接定位到这个分区的节点。

对于这个区间段并不一定要均匀分布，因为数据本身可能就不均匀，这就要具体情况具体看了：哪个区间的数据比较热点，就给哪个区间的分区分的密度小一点，比如根据姓氏分区，姓“A，B，C”的多，姓“D，E”的少，就可以给“A”，“B”，“C”各自独占一个区间，而“C”和“D”就可以分到同一个区间内。这也是Bigtable的开源版本Hbase和MongoDB（2.4版本之前）所采用的分区策略。

缺点：某些访问模式会导致热点问题。尽量避免在同一段时间内向同一个分区/节点写入大量数据，类似于以“时间戳”为键的分区设计就很容易出现这种问题。

基于关键字哈希值的数据分区

一个好的哈希函数可以很好的缓解
（但不能完全避免）数据倾斜与热点问题：例如MongoDB使用MD5，Voldemort使用Fowler-Noll-Vo函数。但是注意⚠️：Java自带的hashCode并不适用，因为同一个键在不同的进程中可能返回不同的哈希值（java是通过内存地址进行hash映射的）

缺点：失去了良好的区间查询特性，因为即使很相似的字符串（例如仅差1ms的时间戳），也有极大可能被分到不同的分区中，所以并不能在同一分区查找有序相邻的数据。所以在MongoDB中，如果要在分区模式下进行区间查询，就需要发送到所有分区上进行查询。

目前为止，没有很好的自动检测并处理负载倾斜的方法，这里给出一个我自己的设想：首先对不同分区进行流量监控，基于其QPS的长时间观察，如果有异常峰值，就开启”临时节点“进行负载均衡，当热点的QPS降下去后，再将临时节点写入的数据迁移至原指定分区。

二级索引

通常二级索引不同唯一标识一条记录，而是用来加速特定值的查询（Solr和Elasticsearch等全文索引服务器的精髓）

二级索引的主要挑战是不能规整的映射到分区中。

基于文档分区的二级索引

二级索引：对于每一条记录（doc）都有唯一的文档ID，其包含了各种属性字段，数据库在加入这些记录的时候，就会对每个字段产生一个二级索引，当查询记录时，就使用二级索引来定位文档ID进而查询相关内容。

分区方法：根据文档ID的值进行分区，例如：[0,199]在分区一，[200,399]在分区二。

在这种索引方法中，每个分区完全独立，各自维护自己的二级索引而不关心其他分区中的数据，所以可以称为“本地索引”，而不是“全局索引”。

缺点：当查询某一个条件时，就需要对所有分区进行查询，比如：查询颜色为“蓝色”的杯子的所有信息，因为这样的杯子可能有很多，而其文档ID不同，分布的分区也不同，所以就需要“分散/聚集”查询。这就很容易导致很大的读延迟，但还是被大多数数据库使用。

基于词条的二级索引分区

对所有的数据构建全局索引，而不是每个分区维护自己的本地索引。另外，不能将全局索引存储在一个节点上，否则就破坏了我们的目标——提高可扩展性。

通俗来说，就是根据词条的term集合所产生的二级索引进行分区，而不是根据文档ID进行分区。例如：年龄为1-10的在一个分区，10-11的在另一个分区，而每个区间都包含了全部的文档ID（也就是所谓的全局索引）

优点：可以支持高效的区间查询，采用hash的方式可以更均匀的划分分区，读取更为高效，因为不用对所有的分区都执行一般查询。

缺点：写入速度慢且非常复杂，想想当有个doc更新时，索引需要怎么处理？必然会引入显著的写放大（也就是用户的一次写入，造成磁盘由于压缩/追加等操作的多次写入）。另外对于词条分区，需要一个跨多个相关分区的分布式事务支持，所以现有数据库都不支持同步更新二级索引。

实际上，对全局二级索引的更新一般是异步的，这就不能保证”写后读“的情况了。

分区再平衡

分区随着时间的推移可能会出现一些变化：
- 查询压力增加——需要更多CPU处理负载
- 数据规模增加——需要更多的磁盘和内存
- 节点出现故障——需要更多的备用机

所谓分区再平衡是指：由以上问题产生的，对数据和请求。从一个节点转移到另一个节点的操作。

分区再平衡通常需要满足：
- 再平衡后，各种分配情况应该在集群范围更均匀分布
- 执行过程中，可以提供正常的读写服务
- 避免不必要的负载迁移，减少网络和磁盘I/O影响

分区再平衡的策略

固定数量的分区

对于之前的hash算法中，并没有提到使用模运算进行分区，这是因为当节点增加时，除数也要随之改变，所以分区的分配策略也会改变，这就需要进行分区间旧数据的迁移，产生了不必要的成本。

使用固定数量的分区就可以解决这个问题：首先创建远大于节点数的分区数，比如在10个节点上创建1000个分区，那么每个节点就需要负责100个分区。当有新节点加入时，就从这10个节点上各拿出10个节点放到新节点中，这样就形成了”11个节点，100个分区“的结果，这样就只需要迁移选中的这100个分区的数据，而与关键字的对应关系仍然保持不变，旧的分区在这个期间仍然可以接收读请求。

但是注意⚠️：过高的分区数量可能会有额外的管理开销，产生副作用。如果分区里的数据量特别大，那么每次再平衡和节点故障恢复的代价就很大；但是一个分区太小，又会产生太多开销。所以就需要选取一个最佳取舍点。

动态分区

HBase支持动态创建分区：当分区的数据增长超过一个参数阈值（HBase默认为10GB）时，就拆分为两个分区。如果数据被大量删除到某个阈值一下，则将其与相邻分区进行合并。类似于B树的分裂操作。另外对于HBase，分区文件的传输需要借助HDFS，实际上Hadoop支持Hbase的数据迁移，只是一个命令的输入而已。

优点：可以自动适配数据总量。

按节点比例分区

Cassandra和Ketama采用分区数与集群节点数成正比关系的分区方式：每个节点具有固定数量的分区。

当一个新节点加入集群时，随机选择固定数量的现有分区进行分裂，并迁移一半的数据量。

随机选择分区边界的前提要求是：基于哈希分区。必须保证分区数据负载时均匀的。

自动与手动再平衡

上述动态平衡需要考虑一个问题：手动执行还是自动执行？

再平衡总体是个比较昂贵的操作，需要重新路由请求并迁移大量数据的操作，如果执行期间出现异常，也会导致各种问题。而全自动的平衡与故障检测会存在很多风险，这里就不一一列举，所以最好是手动确认+自动再平衡。

请求路由

说了这么多，客户端怎么知道我发送的请求应该连接哪个节点？这就是一类典型的服务发现问题（例如Nacos/Zookeeper等）

处理策略：

1. 允许客户端链接任意节点（例如Roubin），让节点选择是否接受此次请求，如果拒绝，那么客户端就需要访问下一个节点。
2. 将所有客户端请求发送到一个路由层（充当负载均衡器的身份）进行请求转发到对应的分区节点。
3. 客户端感知分区和节点分配关系，直接联系目标节点。

那么“负载均衡器”又怎么知道分区与节点的对应关系及其变化情况呢？
这就涉及到了一致性/共识算法的问题。在Zookeeper中，所有节点都需要向ZooKeeper注册自己，其维护了分区到节点的最终映射关系。而对于“负载均衡器”则可以订阅这个信息，一旦分区发生了改变，ZooKeeper就会主动通知他们，使路由信息保持最新状态。而对于目标节点的IP地址，只需要采用DNS解析就可以。

思考一个问题：如果写入需要跨越多分区，其中一个分区写入成功，另一个分区写入失败，该如何解决？