传统hash缺陷
分布式应用的缓存放在N台机器中,通过hash(key)%N找到机器请求缓存服务。但是某一个机器宕机,N的大小发生改变,下一次的请求机器为hash(key)%(N-1),请求机器改变,缓存失效。所以我们希望在删除某台机器节点的时候,其他机器节点缓存仍然有效。
一致性hash基础
一致性hash不在采用取模的方式,而是把整个 [0, 2^32-1] 按照服务的hash值分块,每个服务器负责一块区域,某个落在该区域,则去访问该服务器。
机器映射
将机器节点按照IP或其他ID信息通过hash映射到环上。
key映射
因为key值和服务器hash值都在一个环上,我们定义请求key属于它顺时针方向的第一个Server.
机器删除
对于请求hash(key)在(Server2, Server3)都将访问Server4,该部分缓存失效,其他区间则不受影响。机器添加同理。
虚拟节点
上面解决了机器节点的添加删除问题,但是存在服务器请求平衡性问题。如果在某个区间存在热点值,则该服务器压力会较大。
通过增加虚拟节点使得整个hash环节点的分布能更加紧密,请求能相对更好分散到多个机器,但是均衡程度取决于虚拟节点的添加算法。
如:通过在Server1的IP后面添加”##”,增加Server1.1的虚机节点
hash(server1"192.168.10.123") =》 Server1.1
hash(Server1“192.168.10.123 ##”) =》 Server1.2。
扩展
通过多加虚拟节点使节点分布能更加均与,但是节点分布情况还是取决于虚拟节点添加算法,分布情况还是存在不确定。另一种思路就是:在hash环上固定均与划分vnode, 而维护机器到vnode的映射关系。