hash一致性算法

一致性hash算法是,1097麻省理工提出的分布式hashDHT实现算法,极倔internet的热点问题

平衡性 hash结果尽可能的分布到所有的缓存中去,缓冲空间利用率最高

单调性 保持已有的缓存能映射到对应的位置,新加入的缓存能加入新的位置不会映射到旧的位置

分散性 尽量降低分散性的缓存不一致情况发生

负载 负载被粉丝降低负荷

一致性hash实现算法 chord算法 

基本要素:节点ID(NID)  资源ID(KID)  常hash函数(sha-1)  chord环 (2^m的环)

因为对于hash(k)的范围在int范围,所以我们将0~2^32作为一个环。其步骤为:
1,求出每个服务器的hash(服务器ip)值,将其配置到一个 0~2^n 的圆环上(n通常取32)。
2,用同样的方法求出待存储对象的主键 hash值,也将其配置到这个圆环上,然后从数据映射到的位置开始顺时针查找,将数据分布到找到的第一个服务器节点上。

这是一致性hash算法的原理,加入一个redis节点:redis node5,影响的范围只有黄色标出的那部分,不会造成全局的变动。

雪崩效应 

   当有节点宕机时,当B节点宕机后,原本存储在B节点的k1,k2将会迁移到节点C上,这可能会导致很大的问题。如果B上存储的是热点数据,将数据迁移到C节点上,然后C需要承受B+C的数据,也承受不住,也挂了。。。。然后继续CD都挂了。这就造成了雪崩效应。

我们可以针对每个实际的节点,虚拟出多个虚拟节点,用来映射到圈上的位置,进行存储对应的数据。

 A节点对应A1,A2,BCD节点同理。这时候,如果A节点挂了,A节点的数据迁移情况是:A1数据会迁移到C2,A2数据迁移到D1。这就相当于A的数据被C和D分担了,这就避免了雪崩效应的发送,而且虚拟节点我们可以自定义设置,使其适用于我们的应用。

原文地址:https://www.cnblogs.com/hellohell/p/9019530.html