数据分区方法总结

数据分区与数据复制

分区通常与复制结合使用，即每个分区在多个节点都存有副本。这意味着某条记录属于特定分区 ，而同样的内容会保存在不同的节点上以提高系统的容错性。

一个节点上可能存储了多个分区。每个分区都有自己的主副本，例如被分配给某节点，而从副分配在其他一些节点。 一个节点可能即是某些分区主副本，同时又是其他分区的从副本。

键－值数据的分区

而如果分区不均匀，则会出现某些分区节点比其他分区承担更多的数据量或查询负载，称之为倾斜。倾斜会导致分区效率严重下降，在极端情况下，所有的负载可能会集中在一个分区节点上，这就意味着10 个节点 个空闲，系统的瓶颈在最繁忙的那个节点上。这种负载严重不成比例的分区即成为系统热点。

避免热点最简单的方怯是将记录随机分配给所有节点上。这种方也可以比较均匀地分布数据，但是有一个很大的缺点：当试图读取特定的数据时，没有办法知道数据保存在哪个节点上，所以不得不井行查询所有节点。

基于关键字区间分区

一种分区方式是为每个分区分配一段连续的关键字或者关键宇区间范围（以最小值和最大值来指示）。如果知道关键字区间的上下限，就可以轻松确定！那个分区包含这些关键字。 如果还知道哪个分区分配在哪个节点，就可以直接向该节点发出请求（对于百科全书的例子，就是从书架上直接取到所要的书籍）。

关键字的区间段不一定非要均匀分布，这主要是因为数据本身可能就不均匀。例如，在上图中卷1只包含以 开头的单词，但是卷12则包含了开始的单词。

然而，基于关键字的区间分区的缺点是某些访问模式会导致热点。如果关键字是时间戳，则分区对应于一个时间范围，例如每天一个分区。然而，当测量数据从传感器写入数据库时，所有的写入操作都集中在同一个分区（即当天的分区），这会导致该分区在写入时负载过高，而其他分区始终处于空闲状态。

为了避免上述问题，需要使用时间戳以外的其他内容作为关键字的第 项。例如，可以在时间戳前面加上传感器名称作为前缀，这样首先由传感器名称，然后按时间进行分区。假设同时有许多传感器处于活动状态，则写入负载最终会比较均匀地分布在多个节点上。接下来，当需要获取 个时间范围内、多个传感器的数据时，可以根据传感器名称，各自执行区间查询。

基于关键字晗希值分区

一个好的哈希函数可以处理数据倾斜并使其均匀分布。例如一个处理字符串的32位哈希函数，当输入某个字符串，它会返回一个0和2^32~1之间近似随机分布的数值。即使输入的字符串非常相似，返回的哈希值也会在上述数字范围内均匀分布。

一且找到合适的关键宇 合希函数，就可以为每个分区分配一个哈希范围（而不是直接作用于关键宇范围），关键宇根据其哈希值的范围划分到不同的分区中。

这种方总可以很好地将关键字均匀地分配到多个分区中。分区边界可以是均匀间隔，也可以是伪随机选择（在这种情况下，该技术有时被称为一致性哈希）。

然而，通过关键宇哈希进行分区，我们丧失了良好的区间查询特性。即使关键字相邻，但经过哈希之后会分散在不同的分区中，区间查询就失去了原有的有序相邻的特性。

Cassandra在两种分区策略之间做了一个折中。 Cassandra 中的表可以声明为由多个列组成的复合主键。复合主键只有第一部分可用于哈希分区，而其他列则用作组合索引来对Cassandra SSTable 中的数据进行排序。因此，它不支持在第一列上进行区间查询，但如果为第一列指定好了固定值，可以对其他列执行高效的区间查询。

组合索引为一对多的关系提供了一个优雅的数据模型。例如，在社交网站上，一个用户可能会发布很多消息更新。 如果更新的关键字设置为（ user_id, update_ timestamp ）的组合，那么可以有效地检索由某用户一段时间内所做的所有更新，且按时间戳排序。不同的用户可以存储在不同的分区上，但是对于某一用户，消息按时间戳顺序存储在一个分区上。

负载倾斜与热点

为什么不用取模？
hash( key) mod 10 会返回 个介于0和9之间的数字，如果有10个节点，则依次对应节点0到9，这似乎是将每个关键宇分配到节点的最简单方法。

对节点数取模方法的问题是 ，如果节点数N发生了变化，会导致很多关键字需要从现节点迁移到另一个节点。 例如 ，假设 hash(key) = 123456 假定最初10个节点，那么这个关键字应该放在节点 6( 123456 mod 10 = 6）；当节点数增加到11时，它需要移动到节点3 ( 123456 mod 11=3) 当继续增长到 12 个节点时，又需要移动到节0( 123456 mod 12 = 0）。这种频繁的迁移操作大大增加了再平衡的成本。

一.固定数量的分区

一个简单的想法是，首先，创建远超实际节点数的分区数，然后
为每个节点分配多个分区。 例如，对于10个节点的集群，数据库可 从一开始就逻辑划分为 1000 个分区，这样大约每个节点承担 100个分区。

接下来，如果集群中添加了一个新节点，该新节点可以从每个现有 节点上匀走几个分区，直到分区再次达到全局平衡。如果从集群中删除节点，则采取相反的均衡措施。

选中的整个分区会在节点之间迁移，但分区的总数量仍维持不变， 不会改变关键字到分区的映射关系。这里唯一要调整的是分区与节点的对应关系。考虑到节点间通过网络传输数据总是需要些时间，这样调整可以逐步完成，在此期间， 旧的分区仍然可以接收读写请求。

固定分区的弊端

使用该策略时，分区的数量往往在数据库创建时就确定好，之后不会改变。因此，如果数据集的总规模高度不确定或可变（例如，开始非常小，但随着时间的推移可能会变得异常庞大）， 此时如何选择合适的分区数就有些困难。

二. 动态分区

对于采用关键宇区间分区的数据库，如果边界设置有问题，最终可能会出现所有数据都挤在一个分区而其他分区基本为空。

因此，一些数据库如HBase和RethinkDB 等采用了动态创建分区。当分区的数据增长超过一个可配的参数阔值（ HBase上默认值是 10GB ），它就拆分为两个分区，每个承担一半的数据。相反，如果大量数据被删除，并且分区缩小到某个阑值以下，则将其与相邻分区进行合井。该过程类似于B树的分裂操作。

动态分区的问题是，对于一个空的数据库，因为没有任何先验知识可以帮助确定分区的边界，所以会从一个分区开始。可能数据集很小，但直到达到第一个分裂点之前，所有的 写入操作都必须由单 节点来处理，而其他节点则处于空闲状态。为了缓解这个问题， HBase和MongoDB允许在一个空的数据库上配置一组初始分区（这被称为预分裂）。

三. 按节点比例分区

Cassandra和Ketama采用了第三种方式，使分区数与集群节点数成正比关系。换句话说，每个节点具有固定数量的分区。此时，当节点数不变时，每个分区的大小与数据集大小保持正比的增长关系；当节点数增大时，分区则会调整变得更小。较大的数据量通常需要大量的节点来存储，因此这种方法也使每个分区大小保持稳定。

当一个新节点加入集群时，它随机选择固定数量的现有分区进行分裂，然后拿走这些分区的一半数据量，将另一半数据留在原节点。随机选择可能会带来不太公平的分区分裂，但是当平均分区数量较大（Cassandra默认情况下，每个节点有256个分区），新节点最终会从现有节点中拿走相当数量的负载。 Cassandra 在3.0 时推出了改进算法，可以避免上述不公平的分裂。

请求路由

当有大量的客户请求访问某些资源时，请求路由策略会采用一些手段做到负载均衡和快速响应。主要有以下三种处理策略：

1. 允许客户端链接任意的节点（例如，采用循环式的负载均衡器）。如果某节点恰好拥有所请求的分区，则直接处理该请求 ：否则，将请求转发到下一个合适的节点，接收答复，并将答复返回给客户端。
2. 将所有客户端的请求都发送到一个路由层，由后者负责将请求转发到对应的分区节点上。路由层本身不处理任何请求，它仅充一个分区感知的负载均衡器。
3. 客户端感知分区和节点分配关系。此时，客户端可以直接连接到目标节点，而不需要任何中介。

许多分布式数据系统依靠独立的协调服务（如ZooKeeper ）跟踪集群范围内的元数据，每个节点都向ZooKeeper 中注册自己， ZooKeeper维护了分区到节点的最终映射关系。其他参与者（如路由层或分区感知的客户端 ）可以向ZooKeeper 订阅此信息。一旦分区发生了改变，或者添加、 删除节点， ZooKeeper就会主动通知路由层，这样使路由信息保持最新状态。

并行查询执行

然而对于大规模并行处理（ MPP ）这一类主要用于数据分析的关系数据库，在查询类型方面要复杂得多。典型的数据仓库查询包含多个联合、过滤、分组和聚合操作。 MPP查询优化器会将复杂的查询分解成许多执行阶段和分区， 以便在集群的不同节点上并行执行。尤其是涉及全表扫描这样的查询操作，可以通过并行执行获益颇多。

两种二级索引对比

• 基于文档来分区二级索引（本地索引）。 二级索引存储在与关键字相同的分区中，这意味着写入时我们只需要更新一个分区，但缺点是读取二级索引时需要在所有分区上执行scatter/gather。
• 基于词条来分区二级索引（全局索引）。它是基于索引的值而进行的独立分区。二级索引中的条目可能包含来自关键字的多个分区里的记录。在写入时，不得不更新二级索引的多个分区；但读取时，则可以从单个分区直接快速提取数据。

简言之，就是基于文档的二级索引，它是个局部索引（本地索引），将字段的某个关键字（例如上图红色）仅仅存到本地节点。这样做方便写入，因为各个分区均可以写入同一个关键字（比如红色）的内容；但是弊端就是一旦涉及到查询，就需要在所有分区进行scatter/gather操作。适用于写居多的情景。

而词条二级索引恰好相反，它构建了一个全局索引，比如红色这个关键字只会映射到一个分区（可以采用hash映射），但凡查询red数据，都可以快速的一次性检索出，非常适合读取的情景。但是写入的时候会很麻烦，因为单个文档的更新时，里面可能设计多个二级索引，这些索引的分区又不完全在一起，所以会引发显著的写放大。比如上面增加191的语句，他需要将各个不同的关键字，分别存到不同分区对应字段。