一致性哈希

算法简介

在传统的哈希表算法中,当哈希表槽的数量改变时,需要重新映射所有 key。例如在客户端侧实现的 Redis 数据分片中,如果使用 hash(key)%n 来决定 key 对应的 Redis 实例节点的话,那么当 Redis 实例的数量增加或者减少的时候,所有 key 的映射结果将都会被修改。

在一致性哈希算法中,当哈希表槽的数量改变时,平均只需要重新映射 k/n 个 key,其中 k 是 key 的总数,n 是哈希表槽的总数。一致性哈希算法的主要思想是将每个哈希表槽与一个或多个哈希值的区间关联起来,当一个哈希表槽被删除的时候,则它附近区间的数据会被并入到领近的区间,从而不会影响到其它区间内的数据。

实现思路

优点缺点

参考资料

最后更新于