一致哈希

一致哈希 是一种特殊的哈希算法。在使用一致哈希算法后，哈希表槽位数（大小）的改变平均只需要对 $K/n$ 个关键字重新映射，其中 $K$ 是关键字的数量， $n$ 是槽位数量。然而在传统的哈希表中，添加或删除一个槽位的几乎需要对所有关键字进行重新映射。

历史

一致哈希由MIT的Karger及其合作者提出，现在这一思想已经扩展到其它领域。在这篇1997年发表的学术论文中介绍了“一致哈希”如何应用于用户易变的分布式Web服务中。哈希表中的每一个代表分布式系统中一个节点，在系统添加或删除节点只需要移动 $K/n$ 项。^[1]

一致哈希也可用于实现健壮缓存来减少大型Web应用中系统部分失效带来的负面影响。^[2]

一致哈希的概念还被应用于分布式散列表（DHT）的设计。DHT使用一致哈希来划分分布式系统的节点。所有关键字都可以通过一个连接所有节点的覆盖网络高效地定位到某个节点。

需求

在使用n台缓存服务器时，一种常用的负载均衡方式是，对资源o的请求使用 ${\mbox{hash}}(o)=o\mod n$ 来映射到某一台缓存服务器。当增加或减少一台缓存服务器时这种方式可能会改变所有资源对应的hash值，也就是所有的缓存都失效了，这会使得缓存服务器大量集中地向原始内容服务器更新缓存。因此需要一致哈希算法来避免这样的问题。一致哈希尽可能使同一个资源映射到同一台缓存服务器。这种方式要求增加一台缓存服务器时，新的服务器尽量分担存储其他所有服务器的缓存资源。减少一台缓存服务器时，其他所有服务器也可以尽量分担存储它的缓存资源。一致哈希算法的主要思想是将每个缓存服务器与一个或多个哈希值域区间关联起来，其中区间边界通过计算缓存服务器对应的哈希值来决定。（定义区间的哈希函数不一定和计算缓存服务器哈希值的函数相同，但是两个函数的返回值的范围需要匹配。）如果一个缓存服务器被移除，则它所对应的区间会被并入到邻近的区间，其他的缓存服务器不需要任何改变。

实现

最简单的一种实现是哈希环法：将每个对象映射到圆环边上的一个点，系统再将可用的节点机器映射到圆环的不同位置。查找某个对象对应的机器时，需要用一致哈希算法计算得到对象对应圆环边上位置，沿着圆环边上查找直到遇到某个节点机器，这台机器即为对象应该保存的位置。当删除一台节点机器时，这台机器上保存的所有对象都要移动到下一台机器。添加一台机器到圆环边上某个点时，这个点的下一台机器需要将这个节点前对应的对象移动到新机器上。更改对象在节点机器上的分布可以通过调整节点机器的位置来实现。

这里是哈希环法的可视化演示，可以观察整个操作的过程。

一致性hash，哈希环法可视化演示

特性

David Karger及其合作者列出了使得一致哈希在互联网分布式缓存中非常有用的几个特性： ^[1]

冗余少
负载均衡
过渡平滑
存储均衡
关键词单调

应用实例

在亚马逊的云存储系统Dynamo的数据划分功能模块中使用一致哈希。^[3]

参考资料

^ ^1.0 ^1.1 Karger, D.; Lehman, E.; Leighton, T.; Panigrahy, R.; Levine, M.; Lewin, D. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. ACM Press New York, NY, USA: 654–663. 1997. doi:10.1145/258533.258660.
^ Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. Web Caching with Consistent Hashing. Computer Networks. 1999, 31 (11): 1203–1213 [2012年3月19日]. doi:10.1016/S1389-1286(99)00055-9. （原始内容存档于2008年7月21日）.
^ DeCandia, G.; Hastorun, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchin, A,; Sivasubramanian, S.; Vosshall, P. ;Vogels, W. Dynamo: Amazon's Highly Available Key-Value Store. Proceedings of the 21st ACM Symposium on Operating Systems Principles. 2007.

外部链接

[KargerEtAl1997-1] 1.0 ^1.1 Karger, D.; Lehman, E.; Leighton, T.; Panigrahy, R.; Levine, M.; Lewin, D. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing. ACM Press New York, NY, USA: 654–663. 1997. doi:10.1145/258533.258660.

[KargerEtAl1999-2] Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. Web Caching with Consistent Hashing. Computer Networks. 1999, 31 (11): 1203–1213 [2012年3月19日]. doi:10.1016/S1389-1286(99)00055-9. （原始内容存档于2008年7月21日）.

[Amazon2007-3] DeCandia, G.; Hastorun, D.; Jampani, M.; Kakulapati, G.; Lakshman, A.; Pilchin, A,; Sivasubramanian, S.; Vosshall, P. ;Vogels, W. Dynamo: Amazon's Highly Available Key-Value Store. Proceedings of the 21st ACM Symposium on Operating Systems Principles. 2007.

[1]

[2]

[3]