DDIA-6-数据分区

发表于

数据分区的主要目的—提高可扩展性。也就是应对增长的负载，把负载均匀的分布到各个机器/节点上。

数据分区与数据复制

通常结合使用，也就是每个分区在多个节点都存有副本。

一个节点可能有一个或多个分区。每个分区都有自己的主副本。

Key-Value 数据分区

如何决定哪些记录放在哪个节点上？

如果分区不均匀，那么会导致某些分区节点比其他分区承担更多的数据量的查询负载，成为倾斜。会导致分区效率下降。

避免热点的最简单的方法是将记录随机分配给各个节点。可以比较均匀的分布数据。但是有一个缺点，当读区特定数据时，无法知道保存在哪个节点，所以必须并发读所有节点。这可以改进。

基于Key的区间分区

为每个分区指定一块连续的key范围，就像百科全书一样。

Bigtable使用了这种分区策略，以及其开源等价物HBase。

  • 优点，每个分区可以按照key排序（类似SSTables和LSM-Trees），可以轻松支持区间查询。
  • 缺点，某些访问模式会导致热点。

基于关键字哈希值分区

用来解决数据倾斜和热点问题。

哈希函数的选择，不能使用内置的哈希函数，例如Java的Object.hashCode,同一个Key的返回值可能在不同的进程中不一样。

每一个分区是一个哈希范围。

分区的边界可以是均匀的，也可也是伪随机选择（一致性哈希）。

缺点，丧失了良好的分区查询特性。在MongoDB中，如果使用了哈希分片模式，则区间查询会发送到所有的分区上。

Cassandra在两种分区策略中做了折中。使用了主key哈希，其他列区间的方式。可以支持在其他列上的高效区间查询。

一致性哈希
是一种平均分配负载的方法，最初用于CDN，描述了重新平衡的特定方法。正如我们将在“重新平衡分区”中所看到的，这种特殊的方法对于数据库实际上并不是很好，所以在实际中很少使用。

组合索引 例如社交网络的（user_id, update_timestamp）。可以高效的检索一个用户在一段时间的所有更新，按照时间戳排序。

负载倾斜与消除热点

基于哈希的分区方法可以减轻热点，但是无法完全避免。极端情况就是所有的读写操作都是针对同一个key。社交网络上的名人有几千万粉丝的例子。

解决方法：应用层来减轻倾斜程度。

  • 写入 例如如果某个关键字被确定为热点，就在关键字开头或者结尾加一个随机数。这样只需要一个两位数的十进制数就可以把关键字分不到100个不同的关键字上。
  • 读取 需要从所有100个关键字中读取数据然后进行合并。

因此只有对少量关键字附加随机数才有意义。需要额外的元数据来标记哪些关键字进行了特殊处理。

分区与二级索引

二级索引，情况变得复杂。不能唯一表识一个记录，而是用来做特定值的查询。例如红色的车，包含hogwash的文章。

基于文档分区的二级索引

也称为本地索引。每个分区有自己的索引。

搜索时候，需要将查询发送到所有的问去，然后合并所有的返回结果。这种方法也叫做分散/聚集。查询代价高昂。

尽管如此，它还是广泛用于实践：MongoDB，Riak，Cassandra，ElasticSearch，SolrCloud，VoltDB。。。

基于词条的二级索引分区

构建全局索引。全局索引也必须进行分区。可以与数据关键字采用不同的分区策略。

读取更为高效。不需要分散/聚集。

写入较慢且非常复杂。更新单个文档时，需要涉及到多个二级索引，写放大。所以，现有数据库都不支持同步更新二级索引。

实践中，二级索引的更新都是异步的。

分区再平衡

应对数据库的变化，例如：

  1. 查询压力增加，需要更多的CPU处理负载。
  2. 数据规模增加，需要更多的磁盘和内存。
  3. 节点故障，需要其他机器接管失效节点。

以上这些变化都要求数据和请求从一个节点转移到另一个节点。这样一个迁移负载的过程成为再平衡。

再平衡的目标：

  1. 平衡后，负载，存储，读写请求等应该更均匀。
  2. 再平衡过程中，可以正常的读写。
  3. 避免不必要的负载迁移，尽量减少网络和磁盘IO影响。

再平衡策略

坏方法：取模 mod N

如果N变化，就会产生迁移。频繁的迁移增加了再平衡的成本。

简单的解决方法：固定数量分区

  1. 首先，创建远超过实际节点数的分区。然后为每个节点分配多个分区。
  2. 接下来，如果集群中添加了新节点，就从现有节点中匀走几个给新节点，直到分区再次达到全局平衡。
  3. 如果删除节点，则执行相反的措施。

迁移过程中，总分区数不变。也不会改变关键字到分区的映射关系。

需要调整的是，分区与节点的对应关系。

分区大小应该恰到好处。

动态分区

HBase和RethinkDB等采用了动态创建分区的策略。当分区数据增长超过一个可配置的阀值，就将它拆分为两个分区，每个承担一半的数据量。反过来也是。

动态分区不仅适用于关键字区间分区，也适用于基于哈希的分区策略。

按节点比例分区

每个节点具有固定数量的分区。Cassandra和Ketama采用了这种方式。

当节点数不变时，每个分区的大小与数据集大小保持正比的增长关系。当节点数增加时，分区则会调整的更小。

新节点加入集群时，会随机选择固定数量的现有分区进行分裂，然后拿走这额分区一半的数据量。

随机选择分区边界，前提是要求采用基于哈希的分区。这也符合一致性哈希。

自动与手动再平衡

推荐手动，避免意外发生。

请求路由

客户端请求时，如何直到应该链接哪个节点？

属于服务发现的问题。任何通过网络访问的系统都有这样的要求，尤其是当服务目标支持高可用时。

处理策略：

  1. 允许客户端链接任意的节点。如果请求的节点能满足客户端查询，则返回，否则转发到下一个合适的节点。
  2. 客户端的请求都发送到一个路由层，路由层来转发请求到可以处理的节点。
  3. 客户端感知分区和节点的关系，直接连接到目标节点。

如何应对变化？很多分布式系统依赖一个独立的协调服务（如ZooKeeper），跟踪集群范围内的元数据。每个节点都向Zookeeper中注册自己，ZooKeeper维护了分区到节点的映射。客户端或者路由层订阅这个映射，当有改变时，会通知订阅者更改。

​
Cassandra和Riak采取不同的方法：他们在节点之间使用流言协议（gossip protocol） 来传播群集状态的变化。请求可以发送到任意节点，该节点会转发到包含所请求的分区的适当节点（处理策略的方法1）。这个模型在数据库节点中增加了更多的复杂性，但是避免了对像ZooKeeper这样的外部协调服务的依赖。

执行并行查询

目前只关注了读写单个关键字的建大查询，大多数是NoSQL分布式数据存储所支持的访问类型。

然而，通常用于分析的大规模并行处理（MPP, Massively parallel processing） 关系型数据库产品在其支持的查询类型方面要复杂得多。一个典型的数据仓库查询包含多个连接，过滤，分组和聚合操作。 MPP查询优化器将这个复杂的查询分解成许多执行阶段和分区，其中许多可以在数据库集群的不同节点上并行执行。涉及扫描大规模数据集的查询特别受益于这种并行执行。