欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

如何理解“一致性hash”?

程序员文章站 2024-03-19 21:40:10
...

一句话解释什么是“一致性hash”

   字面解释:外界条件发生了改变,而hash后的结果仍然保持较高程度的一致性。

问题背景

   问题背景:假如有4个缓存节点,按照取膜的方式进行分配数据(对4取膜,0/1/2/3 分别对应a/b/c/d节点),假若d节点挂了,那四个节点的数据都不能使用了,因为之前是对4取膜的,现在拿数据就得是对3取膜了,膜4的结果肯定是不使用膜3的,那么就会去后端,会去查库,造成“缓存雪崩”。

   一致性hash的诞生,就是为了解决这个问题的。

一致性hash的策略

   一致性hash的策略:还是传统的取膜操作,不过,不是对机器节点数来取膜,而是对2^32进行取膜。可以想象成,一个巨大的钟表,上面有2^32个刻度,若干机器节点,映射到hash环上。假若有一张图片,这个图片对应的hash环上的地址是:hash(图片名字) % 2^32的值,比如叫x,顺时针方向,x的下一个环上的机器节点,那就是真实存储图片的节点。

   一致性hash的优势:

   假若不使用一致性hash,增加节点/减少节点,所有的缓存都会失效,会造成缓存雪崩(参考问题背景);

   假若使用了一致性hash,增加/减少节点了,只会对某一范围内的缓存数据有影响,大大减少了影响面。

hash环的偏移

   任何方案都不可能是十全十美的,一致性hash也不例外。会有一种情况,数据集中归属于某一个环,又正好是这个环挂了,那一致性hash的意义就不大了。所以,应对这种情况,有了一个新的机制“虚拟节点”

虚拟节点

   假设是4个节点,可以在从4个节点,虚拟出虚拟节点,这样一个实际节点会对应多个虚拟节点,节点的数据一多,数据自然就分布的越均匀。

相关问题

为什么取膜是对2^32?

   因为IPV4最大是 2的32次方,这样就能保证对所有IP取膜不重复。

一致性hash算法?

   借助MD5算法

如何添加虚节点?

   添加虚节点,最重要的是计算虚节点的下标。计算虚节点的下标,可以参考下面的代码,h即为虚节点下标

for n in nodes:
    for v in vNodes:
        h = _hash(str(n) + str(v))

虚拟节点的替代方案

   在github上,看到一篇文章,提到一种方案“再次映射线性空间”,下面是原文摘要

虚节点这种靠数量取胜的策略增加了存储这些虚节点信息所需要的空间。在OpenStack的Swift组件中,使用了一种比较特殊的方法来解决分布不均的问题,改进了这些数据分布的算法,将环上的空间均匀的映射到一个线性空间,这样,就保证分布的均匀性。

   不过,我并不是非常理解:为什么再映射一次到线性空间,就保证了均匀性?如果再次映射到线性空间,增加/减少节点的时候,又是如何处理呢?会不会又绕回最初的原点?

   参考文章链接:

一致性哈希算法的理解与实践

深入云存储系统Swift核心组件:Ring实现原理剖析