哈希算法
在使用哈希算法对数据进行获取到哈希值后,如果直接取模放置到桶内,当需要对桶进行增减时,需要对已有的所有数据进行迁移,在实际应用于缓存时导致缓存雪崩,这个时候就需要一致性哈希算法了.
一致性哈希(翻译)
这儿直接取了核心的技术片段进行翻译,未翻译内容包括:History,Example
基础实现
思考一个负载均衡问题:大量对象(对话,网页,视频等)需要被指定到 n 个服务器中.一种方式是通过计算对象的id = hash(o) 并使用标准的哈希函数 mod(n)将对象平均地放置在这 n 个服务器中.但如果增加或减少服务器(n 改变了),系统中几乎所有的对象指定的服务器都得改变.这就带来服务器增减之类的事件引发几乎所有对象重新计算并移动到新的服务器中.
一致性哈希被设计用来避免此类问题.主要的实现方式是使用hash函数随机地将对象与服务器映射到一个整圆中(eg:在水平坐标轴上的角度hash(o) 对 360 取模)).每个对象被指定到顺时针方向上的下一个服务器上.这不仅让对象平均分布在服务器上,更重要的是,当一个服务器宕机从这个圆中移除时,只需要这个宕机服务器上的对象需要被重新指定到顺时针方向上的下一个服务器上.类似的,当一个新的服务器被添加到这个圆中时,只需要这个新服务器上的对象被重新指定即可.
拓展
按基本算法,当某个server宕机,原在其上的对象会全部安排下顺时针方向的下一个server,这会让这个新的server产生原来的两位负载.解决方案:让每个server分布多个位置,这样可以防止出现以上情况.另外一种情况是,当一个对象访问过热(多次访问)而不得不将其放置在多个server上,这种情况下,对象通过遍历圆被指定到多个连续的server上.
与协定哈希比较
- Rendezvous hashing 是让每个 client 都使用 Highest random weight hashing 算法,对于每个对象 O 都合适此算法而得出 O 在每个 site 上的权重,而只需要取最高权限的 site 放置对象 O 即可.
- 一致性哈希是协定哈希的一种特殊情况,这种情况下Rendezvous hashing 的 k 是 1 .
- k 用来指定对象分布到按权重排序下的第几个 site .
- 当某个 site 容量是其他 site 的 2 倍,在 site 的集合中放置其他site两倍数量即可实现”能者多劳”.但如果容量并不是整数倍这种做法会产生误差.
- 当增减一个site/server ,只需要相应的O 进行重新指定即可,实现一致性哈希.