《DDIA》阅读笔记（六）：数据分区
本章结构如下：
- 数据分区
- 键值数据分区
- 基于关键字区间
- 基于关键字哈希值
- 一致性哈希
- 组合索引
- 数据倾斜与热点
- 分区与二级索引
- 基于文档（本地）
- 基于词条（全局）
- 分区再平衡
- 动态再平衡策略
- 避免取模
- 固定数量
- 动态平衡
- 按节点比例
- 自动与手动再平衡
- 请求路由
- 分布式协调
- 并行查询执行
- 分区架构
- PGXC
- Hash 分片
- 普通哈希
- 一致性哈希
- Range 静态分片
- Set
- NewSQL
- Range 动态分片
- Group
数据分区也称为数据分片，主要目的是提高可扩展性。
不同的分区可以放在无共享集群的不同节点上，因此把大数据集分配到更多的磁盘（数据量）、查询负载（吞吐量）分布到更多的处理器上。
通常与复制结合使用，每个分区在多个节点都存有副本，某条记录属于特定的分区，相同内容会保存在不同的节点上以提高系统的容错性：每个分区都有自己的主副本，被分配给某节点，而从副本则分配在其他一些节点。
理论上每个分区基本保持独立运行，因此可以将数据库分布扩展到多台机器，但如果写入需要跨多个分区，就涉及分布式事务，情况会变得更复杂。
键值数据的分区
对于键值数据，分区的主要目标是将数据和查询负载均匀分布在所有节点上。
如果分区不均匀，某些分区节点比其他分区承担更多的数据量或查询负载，称之为 倾斜，负载严重不成比例的分区即成为系统热点，会导致分区效率严重下降。
将记录随机均匀分配给所有节点上以避免热点，但当试图读取特定的数据时，无法知道数据保存位置，需要 并行查询所有节点。解决方法是使用键值数据模型，利用关键字访问。
基于关键字区间
先对关键字进行排序，为每个分区分配一段连续的关键字或者关键字区间范围（不一定要均匀分布，因为数据本身可能就不均匀）。
优点是 支持高效的区间查询，将关键字作为一个拼接起来的索引项从而一次查询得到多个相关记录（参考“多列索引”），缺点是 某些访问模式会导致热点：如按日期分区，所有写操作都集中在当天的分区。
要解决范围分区的访问热点，可引入 多关键字拼接 作为分区的键：比如要是同一天写入的数据分配到不同的节点，可以把节点编号与日期拼接作为分区的键。
采用这种分区策略的系统有 Bigtable，其开源版本 HBase、RethinkDB 和 MongoDB 2.4-。
基于关键字哈希值
使用好的哈希函数可以处理数据倾斜、使其均匀分布。
Cassandra 和 MongoDB 使用 MD5、Voldemore 使用 Fowler-Noll-Vo 函数作为哈希函数。
可为每个分区分配一个哈希范围，关键字根据其哈希值的范围划分到不同的分区中。分区边界可以是均匀间隔或伪随机选择（一致性哈希）。
通过关键字哈希进行分区打破了关键字原有的顺序关系，会丧失了良好的区间查询特性。
可在区间分区和哈希分区之间折中（如 Cassandra）：表可以声明为由多个列组成的复合主键，只有第一部分可用于哈希分区，而其他列则用作组合索引来对 SSTable 中的数据进行排序。如果为第一列指定固定值，可对其他列执行高效的区间查询。
哈希策略：
一致性哈希：采用随机选择的分区边界来规避中央控制或分布式共识，主要用于 CDN 等网络缓存系统。
组合索引：为一对多的关系提供了一个优雅的数据模型。比如在社交网站上用户可能会发布多条消息更新，如更新的关键字设置为用户 id 和时间戳的组合，可有效检索由某用户在一段时间内所做的所有更新且按时间戳排序。不同的用户可存储在不同的分区上，但是对于某一用户，消息按时间戳顺序存储在一个分区上。
数据倾斜与热点
即大量读/写操作针对同一个关键字、请求都将被路由到同一个分区的极端情况。
多数系统无法自动消除高度倾斜的负载，只能在应用层减轻：比如在关键字的开头或结尾处添加一个随机数、使数据分配到不同分区。
读取时需从所有关键字中读取数据然后再合并，因此通常只对少量的热点关键字附加随机数才有意义。对于写入吞吐量低的绝大多数关键字引入了不必要的开销，还需要额外的元数据来标记进行特殊处理的关键字。
分区与二级索引
涉及二级索引时分区会变得复杂：二级索引通常不能唯一标识一条记录，而是用来加速特定值的查询（红色的汽车），它们不能规整地映射到分区中。解决方法是使用基于文档的分区和基于词条的分区。
基于文档（本地）
分区之间独立，各自维护二级索引，只负责自己分区内的文档，不关心其他分区中数据。
写入数据时，只需要处理包含目标文档 ID 所在分区。
读取数据时，除非对文档 id 做了特别处理，否则不太可能把关键字为某值的数据放在一个分区（红色的汽车），因此需要将查询发送到所有的分区、再合并所有返回的结果。
这种查询方法也称为分散/聚集，二级索引的查询代价高昂，即使采用了并行查询也容易导致读延迟显著放大。
使用基于文档分区的二级索引有 MongoDB、Riak、Cassandra、Elasticsearch、SolrCloud、VoltDB。
基于词条（全局）
可对所有的数据构建全局索引，而不是每个分区维护自己的本地索引。全局索引也必须进行分区，可以与数据关键字采用不同的分区策略（红色的汽车分收录到索引 red 中，而索引从 a 到 g 开始的颜色分在分区 0 中）。
读取效率比基于文档的分区高效，不需要采用 scatter/gather 对所有的分区都执行一遍查询，客户端只需要向包含词条的分区发出读请求。
缺点在于写入速度较慢且非常复杂，某个文档更新时可能涉及多个分布在不同分区、不同节点上的二级索引。
如果索引时刻保持最新，写入的数据立即反映在最新的索引上，对于词条分区来讲需要跨多个相关分区的分布式事务支持，写入速度会受极大影响。因此在事件中对全局二级索引的更新一般是异步的。
使用全局索引的系统有 Riak 的搜索功能和 Oracle 数据仓库（可选择）。
分区再平衡
随着时间推移，数据库可能出现：
查询压力增加，需要更多的 CPU 来处理负载。
数据规模增加，需要更多的磁盘和内存存储数据。
节点出现故障，需要其他机器来接管失效节点。
这些情况需要把数据和请求从一个节点转移到另一个节点，这个过程称为 再平衡，其至少要满足：
再平衡完成后，负载、数据存储、读写请求等在集群更均匀地分布。
再平衡过程中，数据库应该可以继续正常提供读写服务。
避免不必要的负载迁移，以加快动态再平衡，并尽显减少网络和磁盘 I/0 影响。
再平衡的实现基于以下策略：
避免取模
即将哈希值划分为不同的区间范围，然后将每个区间分配给分区的做法。
如果对节点数取模划定分区，当节点数 N 发生了变化，会导致很多关键字需要从现有的节点迁移到另一个节点，因此再平衡成本很高。
固定数量
在数据库创建时先创建远超实际节点数的固定分区数，然后为每个节点分配多个分区。
为集群添加节点时新节点从现有的节点上匀走几个分区，直到再次达到全局平衡（不必停机）。
选中的分区会在节点之间迁移，分区总数量维持不变，不改变关键字到分区的映射关系，只需调整分区与节点的对应关系。
分区包含固定上限的数据量，实际大小与集群中的数据总量成正比：如果分区里的数据量非常大，每次再平衡和节点故障恢复的代价就很大；但是如果一个分区太小，就会产生太多的开销。
如果分区数量固定了但总数据量却高度不确定，就难以达到一个最佳取舍点。
动态分区
对于采用关键字区间分区的数据库，如果边界设置有问题，最终可能会出现所有数据都在一个分区而其他分区基本为空（倾斜），设定固定边界、固定数量的分区将非常不便，而手动去重新配置分区边界又非常繁琐。
采用动态分区：
HBase（借助 HDFS）、RethinkDB 等，当分区的数据增长超过一个可配置的参数阈值就会拆成两个分区、各自承担一半数据量；如果大量数据被删除，分区缩小到阈值，则将相邻分区合并（类似 B 树的分裂合并）。
分区与节点多对一，当大分区分裂后，可以将其中的一半转移到其他节点以平衡负载。
优点在于分区数量可以自动适配数据总量，数据量小时系统开销很小，在数据量大时每个分区的大小则被限制在一个可分配的最大值。
预分裂：空数据库没有先验知识可帮助确定分区边界，会从一个分区开始分配。直到达到第一个分裂点之前，所有的写入操作都必须由单个节点来处理，而其他节点则处于空闲状态。为了缓解这个问题，HBase、MongoDB 允许在一个空数据库上配置一组初始分区。
按节点比例
以上分区方式中，分区的数量都与节点数量无关。另外也可以使分区数与集群节点数成正比关系（Cassandra 和 Ketama），每个节点具有固定数量的分区：
当节点数不变时，每个分区的大小与数据集大小保持正比的增长关系；当节点数增加时，分区则会调整变得更小。较大的数据量通常需要大量的节点来存储，这种方法使每个分区大小保持稳定。
当一个新节点加入集群时，随机选择固定数量的分区进行分裂，取走原分区一半数据量。当平均分区数量较大时，新节点最终从现有节点中拿走相当数量的负载。
随机选择分区边界的前提要求采用基于哈希分区（也符合一致性哈希），一些新设计的哈希函数也可以以较低的元数据开销达到类似的效果。
自动或手动
全自动式再平衡会更加方便，但也有可能出现结果难以预测的情况导致异常，造成网络或节点负载过重，影响其他请求的性能。而纯手动方式又相对繁琐。Couchbase、Riak、Voldemort 会自动生成一个分区分配建议方案，由故哪里有确认生效。
将自动平衡与自动故障检测相结合可能存在一些风险：例如假设某个节点负载过重，对请求的响应暂时受到影响；其他节点认为该节点失效、激活自动平衡转移其负载。这反而加重该节点、其他节点以及网络的负荷，使总体情况变得更糟，甚至导致级联式的失效扩散。
请求路由
将数据分布在多个节点、分区上，客户端在发送请求时还需要知悉应该连接到哪个节点，还可能随再平衡的发生而变化。
这就需要服务发现能力，有以下几种策略：
节点：允许客户端连接任意的节点，比如循环式的负载均衡器。如果某节点拥有所请求的分区则直接处理求，否则将请求转发到下一个合适的节点接收答复，并将答复返回给客户端。
路由层：将所有客户端的请求都发送到一个路由层，即充当分区感知的负载均衡器。将请求转发到对应的分区节点上。
客户端：客户端感知分区和节点分配关系，直接连接到目标节点。
当使用路由层或随机选择节点发送请求时，客户端需要知道目标节点的 IP 地址。IP 地址的变化往往没有“分区－节点”变化般频繁，采用 DNS 即可。
分布式协调
请求路由需要所有参与者都要达成共识，否则请求可能被发送到错误的节点。
许多分布式数据系统会依靠独立的协调服务跟踪集群元数据，如 ZooKeeper：
每个节点都向 ZK 中注册自己，ZK 维护了分区到节点的最终映射关系。
其他参与者，即路由层或分区感知的客户端可以向 ZK 订阅此信息。
分区发生改变或者添加、删除节点时，ZK 主动通知路由层，使路由信息保持最新状态。
应用实例：
Espresso 使用 Helix（ZooKeeper 底层）实现请求路由层，HBase、SolrCloud、Kafka 都使用 Kafka 跟踪分区分配情况。MongoDB 则是依赖于自身的配置服务器和 Mongos 守护进程充当路由层。
Cassandra 和 Riak 节点之间使用 gossip 协议同步集群状态变化。请求可以发送到任何节点，该节点负责将其转发到目标分区节点，虽然增加了数据库节点的复杂性，但是避免了对外部协调服务的依赖。
Couchbase 不支持自动再平衡功能，通过配置 moxi 路由选择层向集群节点学习最新的路由变化。
并行查询执行
对于大规模并行处理（MPP）一类用于数据分析的关系数据库（比如 Greenplum、GaussDB），查询类型方面要比读取或写入单个关键字查询复杂（对于基于文档分区的二级索引，要求分散/聚集查询）。
对于数据仓库，MPP 查询优化器将复杂的查询（多个联合、过滤、分组和聚合）操作分解成许多执行阶段和分区，以便在集群的不同节点上并行执行。尤其当涉及全表扫描等查询操作，可以通过并行执行获益。