《数据密集型应用系统设计》第六章数据分区笔记

键值数据的分区

基于关键字区间的分区

给每个分区分配一段连续的关键字或者关键字区间（以最小值和最大值来指示），从关键字区间的上下限可以确定哪个分区包含这些关键字。

关键字的区间段不一定要均匀分布，这是因为数据本身可能就不是均匀的。比如，某些分区包含以A和B开头字母的键，而某些分区包含了T、U、V、X、Y和Z开始的单词。

基于关键字的区间分区的缺点是某些访问模式会导致热点（hot spot）。比如关键字是时间戳，分区对应一个时间范围，那么可能会出现所有的写入操作都集中在同一个分区（比如当天的分区），而其他分区始终处于空闲状态。

为了避免类似的问题，需要使用时间戳以外的其他内容作为关键字的第一项。

基于关键字Hash值分区

基于关键字Hash值分区，可以解决上面提到的数据倾斜和热点问题，但是丧失了良好的区间查询特性。

负载倾斜和热点

基于关键字Hash值分区的办法，可以减轻数据热点问题，但是不能完全避免这类问题。一种常见的极端场景是，社交网络上某个名人有几百万的粉丝，当其发布一些热点事件时可能会引起访问风暴。此时，Hash起不到任何分流的作用。

大部分系统解决不了这个问题，只能通过应用层来解决这类问题。比如某个关键字被确认是热点，一个简单的技术就是在关键字的开头或结尾处添加随机数，这样将访问分配到不同的分区上。但是随之而来的问题就是，之后的任何读取都需要额外的工作，必须将这些分区上的读取数据进行合并。

分区与二级索引

键值类数据库的分区相对还简单一些，但是如果涉及到二级索引就变得复杂了。二级索引主要的挑战在于：它们不能规整的映射到分区中。

基于文档分区的二级索引

上图中，数据根据ID 进行分区，但是实际查询的时候，还可以按照颜色和厂商进行过滤，所以每个分区上面还创建了颜色和厂商的索引。每次往分区中写入新数据时，自动创建这些二级索引。

在这种索引方式中，每个分区完全独立。各自维护自己的二级索引。因此文档索引也成为本地索引，而不是全局索引。

但是读取的时候，需要查询所有的分区数据然后进行合并才返回给客户端，这种叫分散/聚集（scatter/gather）。

基于词条的二级索引

可以对所有的数据构建全局索引，而不是每个分区维护自己的本地索引。而且吧，为了避免成为瓶颈，不能将全局索引放在一个节点上，否则又破坏了分区均衡的目标，因此全局索引数据也需要进行分区。

上图中，所有数据分区中的颜色进行了分区，比如从a到r开始的颜色放在了分区0中，从s到z的颜色放在了分区1中，类似的，厂商索引也被分区。这种索引方式成为词条分区（term-partitioned）。

• 优点：读取高效，不需要采用scatter/gather方式对所有分区都进行查询；
• 缺点：写入速度慢并且非常复杂，主要是因为单个文档需要更新的时候，里面可能涉及多个二级索引，而二级索引又放在不同的节点上。

在实践中，对全局二级索引数据的更新一般都是异步进行的。

分区再平衡（Rebalancing Partitions）

实际中，数据会发生某些变化，这时候需要将数据和请求从一个节点转移到另一个节点。这样的一个迁移负载的过程称为再平衡（rebalance）。

分区再平衡至少需要满足：

• 平衡之后，负载、数据存储、读写请求能够在集群范围内更均匀分布。
• 再平衡过程中，数据库可以继续处理客户端的读写请求。
• 避免不必要的负载迁移。

下面谈各种再平衡策略。

为什么不能用取模？

对节点数进行取模的方式，最大的问题在于如果节点的数据发生了变化，会导致很多关键字从现有的节点迁移到另一个节点。

固定数量的分区

创建远超实际节点数的分区数，然后给每个节点分配多个分区。比如只有10个节点的集群，划分了1000个逻辑分区。

如果集群中添加了一个新节点，该新节点就可以从每个现有节点上匀走几个分区，直到分区再次达到全局平衡。

这个方式的优点在于，关键字与逻辑分区的映射关系一开始就固定下来了，节点数量的变更只是改变了逻辑分区分布在哪些节点上。节点间迁移分区数据需要时间，这个过程中，就分区依然可以处理客户端的读写请求。

动态分区

按节点比例分区

自动与手动再平衡操作

请求路由

当客户端需要发起请求时，如果知道应该连接哪个节点？如果发生了分区再平衡，分区与节点的对应关系发生了变化。

这类问题属于典型的服务发现（service discover）问题。服务发现问题不限于数据库中，任何需要通过网络访问的系统都有这样的需求，尤其是服务目标需要支持高可用时。

一般有以下三种处理策略。

• 客户端可以发送请求给任意节点，如果节点不能处理请求则路由到可以处理该请求的分区，应答之后再回复客户端。
• 所有客户端的请求发送到一个路由层，由该路由层决定请求应该转发到哪个分区。
• 客户端需要感知分区与节点之间的映射关系。

但是不管是上面的哪种方案，核心问题都是：做为路由决策的组件，如何知道分区与节点的对应关系以及其变化情况？

很多分布式系统依赖于独立的协调服务（比如zookeeper、etcd等）跟踪集群范围内的元数据（metadata）。如下图所示，每个节点都像zookeeper注册自己，zookeeper维护了分区到节点的最终映射关系。而其他参与者（比如路由层或者分区感知的客户端）向zookeeper订阅此信息。当分区信息发生了增删时，zookeeper会主动通知，这样就能够保持最新的状态。

还有另一种策略，在节点之间使用gossip协议来同步集群状态的变化，请求可以发送到任何节点，由该节点负责将其转发到正确的节点上。