菜鸟笔记
提升您的技术认知

对一致性hash原理的理解-ag真人游戏

一致性hash算法解决的核心问题是,当solt数发生变化的时候能够尽量少的移动数据。该算法最早在《consistent hashing and random trees:distributed caching protocols for relieving hot spots on the world wide web》一文中被提出。它能够在添加/移除一台缓存服务器的时候,尽可能小的改变已存在key的映射关系,避免大量key的重新映射。

原理

一致性hash算法将hash函数的值域空间组织成一个大的圆环,假设hash函数的值域空间为0~ 2^32-1(即hash值是一个32位的无符号整数),整个值域空间按照顺时针方向进行组织,然后对相应的服务器节点进行hash,将它们映射到hash环上,假设有四台服务器,分别是node1,node2,node3,node4,它们在环上的位置如下图所示:

接下来使用相同的hash函数,计算出对应key的hash值在环上的对应位置,根据一致性hash算法,按照顺时针方向,分布在node1和node2之间的key,它们的请求会被定位到node2上,node2和node4之间的key,会被定位到node4上,以此类推。

假设有新节点node5进来,它被hash到node2和node4之间,如下图,受影响的只是node2和node5之间的节点,它们被映射到node5上,其他key的映射不会改变

当然上面只是一种理想的情况,各个节点的分布十分的均匀,正常情况下,当节点数量较少的时候,节点的分布可能十分的不均匀,从而导致数据访问的倾斜,大量的key被映射到同一台服务器上。为了避免这种情况发生,可以引入虚拟节点机制,对每个服务器节点都计算出多个hash值,每个hash值对应环上一个位置,该节点称为虚拟节点,而key的映射方式不变,只是多个一步从虚拟几点映射到实际节点的操作,这样如果虚拟节点数量足够多,即使实际节点很少,也能使得key的分布足够均衡

网站地图