一致性哈希算法 / Consistent Hashing

在理解一致性 hash 之前,先来看看这个问题是怎么产生的。

例如我们有一个数据库,里面存了成千上万张图片(你懂的),用户访问图片会呈现一定的规律性,比如某段时间内一张照片火了,那么短时间内会有大量的请求访问这张图片,会对数据库造成压力,这时候我们就想到要加一层缓存,这也是系统架构的终极法宝。

所以,这种场景下典型的系统架构如下图所示:

arch

客户端要访问文件名为 A 的图片,代理服务器根据文件名去缓存服务器中查询,如果cache中没有,那么最终去数据库取,同时也把取到的图片文件缓存在某个缓存服务器中。 这里有个题外话,通常我们会把文件名 A 通过 hash 函数转换成一段数字,便于操作,这里的 hash 函数与本文的一致性 hash 是不一样的。

那么问题来了:如何将图片均匀的缓存在缓存服务器上呢?

最简单的方式,以文件名为 key,缓存服务器个数为 N,取模得到余数,即 key % N = i,i 是几,就把图片缓存到对应编号的服务器上。

这种方式确实能够将数据 均匀的 分布在缓存上,但是最大的缺点是一旦 N 的数量发生变化,那么几乎所有的 i 都会改变,导致缓存失效

例如,

  • key = 5 的文件,在 N = 3 时,缓存在编号为 2 的缓存服务器上。
  • 增加一台服务器,N = 4,那么 key = 5 的文件应该在 1 号服务器上,但事实上它在 2 号。

导致这种情况的根本原因是什么呢? 我们想让数据**均匀**分布,但是均匀的算法却依赖于 N ,而 N 直接依赖于服务器的数量!

所以解决的办法就是,让均匀分布的计算方法不依赖于 N。

去网上搜一搜资料,绝大多数资料都会提到用服务器的 IP 地址,得到一个数字串(比如 MD5 值),然后再对 2^32 取模,这样看起来缓存服务器就不太均匀的均匀分布在了 2^32 的环上,然后再对图片文件名做相同的计算,也让它们分布在 2^32 的环上,最后让图片存在距离最近的缓存上,这就是一致性哈希 的核心思想。

当然,理想很丰满现实很骨感,前面提到不太均匀的均匀分布,为了解决这个问题,又提出了虚拟节点的概念,努力的让缓存均匀分布。

参考资料

  • http://www.zsythink.net/archives/1182
-----------------------
返回首页

| Copyright 2009 - 2018 by Runz |