当一个缓存服务由多个服务器共同提供时,存在一个key应该路由到哪一个服务器的问题。假如采用最通用的方式 key % N
(N
为服务器的数目),
当服务器数量发生增加或者减少时,分配方式则变成 key % (N+1)
或者 key%(N-1)
,这时候会有大量的key失效迁移,如果后端的key对应的是有状态的存储数据,
那么这种做法就会导致服务器间大量的数据迁移,从而造成服务器的不稳定,而使用槽映射的方式有一个缺点就是所有节点都需要知道槽与节点对应关系,如果client端不保存槽与节点对应的关系,client就需要实现重定向的逻辑。这时候使用一致性hash算法就很适合。
一致性hash算法在1997年由麻省理工学院 karger
等人在解决分布式Cache中提出。一个好的hash算法应该满足四个条件:均衡性(Balance)、单调性(Monotonicity)、分散性(Spread)和负载(Load)。
一致性hash的核心思想是将key做hash运算,然后通常的做法是按照一定的算法得出一个 0 ~ 2^32-1
之间的值,环的大小为 2^23
,key计算出的整数为key在hash环上的位置。
所以就是两步:
如图所示,key做hash之后得到一个整数然后顺时针在环上找第一个遇到的服务器:
如果只使用实际节点,一般都会出现hash出来的范围分配不均的情况,这时候就需要加上虚拟节点,如图: