《数据密集型应用系统设计》第6章-数据分区
分区的定义
每一条记录只属于某一个特定分区，查询可能会跨分区。
复制(Replication)和分区(Partitioning)的组合使用
每个节点同时充当某些分区的leader和其他分区的follower：
分区的倾斜问题
分区不均匀，会导致某些分区节点承担更多的负载。
使用区间缓解倾斜问题
比如如下的书架，共有12卷，分区1存放A和B开头的key，分区12包含T、U、V、X、Y、Z开头的key。分区内再按照key排序，这样一来便能支持区间查询。
但是这个方法容易产生热点问题，如果key是时间戳，则分区存储的是某一个时间范围内的数据，比如每一天对应一个分区。这样导致当天的分区总是成为写操作的热点。可以通过细化分区的维度来解决，比如分区的key改为传感器名称+时间，这样当多个传感器处于活动状态时，则负载能较好地均匀分布。
基于hash分区
优秀的hash函数能很好地处理倾斜问题：
hash分区的缺点在于丧失了区间查询的特性，因为相邻的key，hash后会分散在不同的分区。一些数据库的处理方法如下：
- MongoDB的哈希分区模式，区间查询会发送到所有分区上。
- Riak、Couchbase、Voldemort直接就不支持区间查询。
- Cassandra做了折中，可以声明一个表的复合主键key1+key2+…+keyN，只有key1可用来hash分区，而其他key用作组合索引来在SSTable中对数据排序。因此，Cassandra不支持在第一列上区间查询。当确定第一列的值后，就可以对其他列进行区间查询。
极端情况下的倾斜问题
哈希分区可以减轻热点，但无法完全避免。当所有的读写操作都是针对同一个key，则所有请求都会被路由到同一个分区。比如鹿晗公布恋情导致微博瘫痪。这种问题无法在数据层面解决，只能在应用层自行处理。比如当识别出热点key后，就在key的开头或者结尾增加一个随机数，再进行hash，从而分配到不同的分区上。
二级索引的分区问题
上面讨论的都是key-value的分区，一个key可以唯一标识一条记录，自然可以用key来分区，但是二级索引不具有唯一性。比如一张Car表：(id,name,color)，查询所有红颜色的汽车，color就是二级索引。针对二级索引的分区，主要有以下两种方案。
基于文档(Document)分区
比如一个汽车数据库，根据id分区：0-499为分区0，500-999为分区1。每当一辆红色汽车添加到数据库中，相应的二级索引条目"color:red"也会更新：把汽车的id添加到文档中。
这样一来，每个分区各自独立负责自己的二级索引，而不关心其他分区中的数据。增删改时，只需要处理目标id所在的那个分区即可。因此文档分区索引也被称为本地索引。而查询就不一样了，需要查询所有的分区，然后合并结果。这种查询模式被称为scatter/gather。它的缺点显而易见，查询延迟大。
基于词条(Term)分区
与基于文档(Document)分区构建的本地索引不同，基于词条(Term)分区构建的是全局索引。同时，为了避免单点故障，全局索引本身也需要进行分区：
上面的示例中，有两个二级索引：color、make(制造商)。a-r开头的color索引在分区0，s-z开头的color索引则在分区1，make索引也被分区。这种方案的优点在于读取很快(图中的实线)，只需要查询二级索引的分区就能得到所有的主键id。然而缺点就是写入速度慢(图中的虚线)，因为单条记录的更新可能会涉及到多个二级索引，而二级索引分区又有可能位于不同的节点上，从而导致写放大，同时也需要分布式事务的支持。
分区再平衡
节点宕机、增加节点等情况都需要将数据转移到另一个节点。
为什么不用mod
mod会带来频繁的迁移操作，比如hash(key)=12345，节点10个，12345 mod 10 = 6，则key应该放到节点6，现在节点11个，则12345应该放到节点3。
固定数量的分区
10节点的集群，可以从逻辑上先划分一个远超过节点数的分区数，比如1000，这样每个节点承担100个分区。
动态分区
分区过大，就拆分并分给其他节点。分区过小，就合并。
按照节点比例分区
每个节点只承担固定数量的分区，这样一来，分区数和集群节点数成正比。
请求路由问题
客户端怎么知道连接到哪个节点？如果集群正在分区再平衡，则节点和分区的关系还会变化，这是经典的服务发现问题。有以下方法：
- client通过round robin负载均衡连接到任意一个节点，如果存在对应的分区，则直接处理，否则将请求转发到相应的节点上。
- 引入一个路由层，由路由层感知分区与节点的对应关系变化。
- 客户端感知分区与节点的对应关系变化，自行处理。
这其实就是一个分布式共识问题，一些典型的数据库是这样处理的：
- HBase、Kafka使用zk来维护分区情况
- 去中心化的处理，比如Riak和Cassandra，使用gossip协议交换集群状态信息，然后使用上面的方案1。
