CHAPTER 5: DESIGN CONSISTENT HASHING

1. 传统hash存在的问题

传统的直接使用hash(key)/n 这种方式其实有着自己的使用场景，如果你的n是固定的永远不变的，其实是没有问题的，这里的不变的就是n的数量不变，因为只要n不变那么key分布的位置就不会变化的；而一旦n要变化，这传统的方式就会带来一个极大的问题是：几乎所有的key需要重新被调整分布，这样动静太大了；

2. consist hash

Quoted from Wikipedia: "Consistent hashing is a special kind of hashing such that when a hash table is re-sized and consistent hashing is used, only k/n keys need to be remapped on average, where k is the number of keys, and n is the number of slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped [1]

(View Source)

这是wiki对consist hash的定义的，主要是为了解决传统hash中，当集群成员数量变化导致的remapped问题；一致性hash在集群数量产生变更的时候，平均的key的调整数量为k/n , k为key的个数，n为slot的个数，也就是从统计来说，它只需要调整一个节点的key即可，这也符合正常要求：一个节点出现问题，那么就将这个节点的key全部迁移即可， 不要对其他的节点进行影响；(slot正常情况下会在node分布均匀)

1. hash space: 主要是指一个hash算法结果值的范围,比如sha-1的范围是[0,2^160-1]
2. hash ring: 就是这范围的一种比较形象的表示;

2.1 核心的几个步骤

• server按照自己的ip或者其他能代表它身份的信息，经过相同的hash算法找到自己在hash ring上的位置

  

• key在存储的时候，按照hash算法的结果找到对应的位置，然后顺时针找到第一个server来存储它

  

2.2 成员add和remove

• 增加节点

  

  能看到增加了s4之后，remapped的影响面之后在[s3,s4]之间这块范围，之前这块范围是有s0来存储的，所以一致性hash的好处就在于增加/删除节点的时候需要remapped的key的个数非常的少；

• 删除节点

  

  删除节点也一样，s1的删除影响的范围在于[s0,s1]这个keys，因为这块之前有s1来负责，现在开始要有s2来负责，这种算法的好处几乎做到了能将影响面控制在最小范围之内；

2.3 基础一致性hash算法的问题

如何保证每个server能存储差不多的key，也就是负载均衡； 原因在于server本身在环上的位置也是靠计算的，你没办法用相对直观的方式去分配它负责的key的范围; 比如下面这个图，如果s1下限了，那么s2要承担超过几乎50%的key的范围，这个很容易导致s2出现压力过大的问题;

解决方式是: Virtual node 虚拟节点的；通过将真实节点虚拟成100-1000个虚拟节点然后放到ring上，那么整个hash ring就会被分裂成相对比较均匀的区域，而且本身hash算法从算法层面来保证key会比较均匀的落在hash ring上，那么就可以解决所谓的热点问题;

As the number of virtual nodes increases, the distribution of keys becomes more balanced. This is because the standard deviation gets smaller with more virtual nodes, leading to balanced data distribution. Standard deviation measures how data are spread out. The outcome of an experiment carried out by online research [2] shows that with one or two hundred virtual nodes, the standard deviation is between 5% (200 virtual nodes) and 10% (100 virtual nodes) of the mean. The standard deviation will be smaller when we increase the number of virtual nodes. However, more spaces are needed to store data about virtual nodes. This is a tradeoff, and we can tune the number of virtual nodes to fit our system requirements.

(View Source)

通过标准差的方式去衡量整个的负载均衡的情况的，100-200个虚拟节点测试结果大概标准差在10%或者5%h之间 的，其实这样的负载均衡是可以被接受的；增加虚拟节点个数可以减少标准差但是会增加整体find的过程的和存储这些节点的空间

2.3 自己的思考

我们思考一下在分布式环境下要做到数据分片本质上就两种方式，分别为

• range

• hash

其实这两种方式的本质是一致性的，主要是区别在于key最终要落在范围不同；range是结果范围是按照用户的key的取值范围，比如mongo的按照range分片本质上取值范围是所有的字符串的范围；而所谓的hash分片，本质上是hash算法结果的取值范围；

正常情况下分布式管理key存储在哪个位置都会有一个meta表，基本上的结构应该是:

你会发现你需要这么一张表去管理这个映射关系的，但是这种方式带来的问题是什么: 需要不断的去维护这份信息的正确性，删除节点、增加节点，数据迁移等等都需要你去更新这份数据，如果这份数据错了那就表示你的key将找不到的；而一致性hash的方案能解决这个问题，它不需要这份信息的存储，它只需要靠计算+server lookup的方式来获得key的存储节点；

所以想较于一致性hash算法的remapped的好处，其实本质上通过上述的通过一个meta信息管理也可以做到影响面比较小，扩容缩容只不过比一致性hash算法要稍微麻烦一点点，但是影响面也可以控制的比较小；而一致性hash最最重要的是元信息的管理不需要存储只需要计算，这样的好处是：减少瓶颈点，减少复杂度;

目前有哪些比较有名的系统在使用这套算法呢:

1. cassandra

2. dynamo

3. ceph

4. …

关于一致性hash好处讲了很多，那么有哪些缺点呢？

1. 可控性比较差，尤其是运维复杂度比较高；很多操作的预期不明确

   1. 添加节点之后会出现整个集群都开始数据搬迁的，如果这个时候有的节点压力本身比较大的时候，这无疑是容易出现问题，但是如果我用上面那种方式，其实整个过程是相对可控的；

   2. 没办法做定点的操作,需要你预先模拟整个hash ring的状态，复杂度挺高的；

2. 计算资源，其实这到不是很大的问题

3. 虚拟节点的个数的确定，不同机型需要根据硬件能力来决定虚拟节点的个数，无疑增加了复杂度；最好做到标准化

4. 扩容，大概率只能一个节点一个节点进行扩容；还记得上面如何寻找被影响keys，是通过逆时针的方式寻找，如果一下子添加多个服务器，可能找到真正有数据的节点是很复杂的；当然也有解决方法