redis一致性hash算法理解

一般算法:

  对对象先hash然后对redis数量取模,如果结果是0就存在0的节点上。

  1、2同上,假设有0-3四个redis节点、20个数据:

  redis一致性hash算法理解

进行取模后分布如下:

redis一致性hash算法理解

现在因为压力过大需要扩容,增加一台redis4、第五个节点:

redis一致性hash算法理解

现在只有4个节点还能够命中。命中率是:4/20 = 20%,命中率极其低下。(redis肯定是不会这样用的)

二、redis使用的consistent hashing(一致性hash算法)

  1、环形hash空间:

redis一致性hash算法理解

把对象映射到0-2的32次幂减1的空间里。

现在假设有4个对象:object1-object4,将四个对象hash后映射到环形空间中:

redis一致性hash算法理解

接下来把chche映射到hash空间(基本思想就是讲对象和cache都映射到同一hash数值空间中,并且使用相同的hash算法,可以使用cache的ip地址或者其他因子),假设现在有三个cache:

redis一致性hash算法理解

每个key顺时针往下走,找到的第一个cache节点就是存储位置:

redis一致性hash算法理解

现在移除一个cacheB节点、这时候key4将找不到cache,key4继续使用一致性hash算法运算后算出最新的cacheC,以后存储与读取都将在cacheC上:

redis一致性hash算法理解

移除节点后的影响范围在该节点逆时针计算到遇到的第一个cache节点之间的数据节点。

现在看一下增加一个节点:

redis一致性hash算法理解

影响范围为:添加节点逆时针遇到的第一个cache节点之间的数据节点。(未完待续)

文中图为慕课网geely老师的电商平台课程视频中的图,知识点很多,讲的非常好,课程链接

上一篇:关于一致性Hash算法


下一篇:11.redis cluster的hash slot算法和一致性 hash 算法、普通hash算法的介绍