键值数据的分区

基于关键字区间的分区

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

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

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

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

基于关键字Hash值分区

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

负载倾斜和热点

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

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

分区与二级索引

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

基于文档分区的二级索引

figure 6-4

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

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

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

基于词条的二级索引

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

figure 6-5

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

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

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

分区再平衡(Rebalancing Partitions)

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

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

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

下面谈各种再平衡策略。

为什么不能用取模?

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

固定数量的分区

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

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

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

figure 6-6

动态分区

按节点比例分区

自动与手动再平衡操作

请求路由

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

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

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

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

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

figure 6-7

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

figure 6-8

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