NoSQL分片的数据划分方法

jieforest

轮流放置系统迁移量比较大


数据迁移量大的问题可以通过改进轮流放置算法来达到，比较常见的两个改进算法是一致性哈希和范围分区划分算法。

jieforest

一致性 hash 算法（Consistent Hashing）

Consistent Hashing 算法早在 1997 年就在论文 Consistent Hashing and Random Trees 中被提出，目前在 cache 系统中应用越来越广泛。

基本场景

比如你有 N 个 cache 服务器（后面简称 cache），那么如何将一个对象 object 映射到 N 个 cache 上呢？你很可能会采用类似下面的通用方法计算 object 的 hash 值，然后均匀的映射到 N 个 cache：

1. hash(object)%N

复制代码

jieforest

一切都运行正常，再考虑如下的两种情况；

1）一个 cache 服务器 m down  掉了（在实际应用中必须要考虑这种情况），这样所有映射到 cache m 的对象都会失效，怎么办，需要把 cache m 从 cache 中移除，这时候 cache 是 N1 台，映射公式变成了 hash(object)%(N-1)  ；

2）由于访问加重，需要添加  cache  ，这时候  cache  是  N+1  台，映射公式变成了 hash(object)%(N+1)。

这两种情况意味着什么？这意味着突然之间几乎所有的 cache 都失效了。对于服务器而言，这是一场灾难，洪水般的访问都会直接冲向后台服务器。

再来考虑第三个问题，由于硬件能力越来越强，你可能想让后面添加的节点多做点活，显然上面的  hash 算法也做不到。

有什么方法可以改变这个状况呢，这就是一致性哈希（Consistent Hashing）。

jieforest

hash 算法和单调性

hash 算法的一个衡量指标是单调性（  Monotonicity  ），定义如下：

单调性是指如果已经有一些内容通过哈希分派到了相应的缓冲中，又有新的缓冲加入到系统中。哈希的结果应能够保证原有已分配的内容可以被映射到旧的缓冲中去，而不会被映射到新的缓冲集合中。

容易看到，上面的简单 hash  算法  hash(object)%N  难以满足单调性要求。

jieforest

Consistent Hashing 算法的原理

Consistent Hashing 是一种 hash 算法，简单的说，在移除/添加一个  cache  时，它能够尽可能小的改变已存在  key  映射关系，尽可能的满足单调性的要求。

下面就来按照  5  个步骤简单讲讲 Consistent  Hashing  算法的基本原理。

jieforest

1．环形 hash 空间

考虑通常的 hash 算法都是将 value 映射到一个 32 维的 key 值，也即是 0～2^32-1 次方的数值空间；我们可以将这个空间想象成一个首（0）尾（2^32-1）相接的圆环，如图所示的那样。


环形 hash 空间

jieforest

2．把对象映射到 hash  空间

接下来考虑 4 个对象 object1～object4  ，通过 hash 函数计算出的 hash 值 key 在环上的分布如图所示。

1. hash(object1) = key1;
   
2. … …
   
3. hash(object4) = key4;

复制代码

4  个对象的  key  值分布

jieforest

3．把 cache  映射到 hash  空间

Consistent  Hashing  的基本思想就是将对象和  cache  都映射到同一个 hash 数值空间中，并且使用相同的 hash  算法。

假设当前有 A、B 和 C 共 3 台 cache，那么其映射结果如图 3.16 所示，它们在 hash 空间中，以对应的  hash 值排列。

jieforest

1. hash(cache A) = key A;
   
2. … …
   
3. hash(cache C) = key C;

复制代码

cache  和对象的  key  值分布