Memcached Consistent Hashing 介绍

小编辑 发布于 2010/02/27 10:48
阅读 1K+
收藏 2

介绍高效率地分散数据的Consistent Hashing算法。

Consistent Hashing 的简单说明,

如下所示:首先求出memcached服务器(节点)的哈希值, 并将其配置到0~232的圆(continuum)上。

然后用同样的方法求出存储数据的键的哈希值,并映射到圆上。

然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器上。

如果超过232仍然找不到服务器,就会保存到第一台memcached服务器上。

Consistent Hashing 基本原理

从上图的状态中添加一台memcached服务器。余数分布式算法由于保存键的服务器会发生巨大变化 而影响缓存的命中率,但Consistent Hashing中,

只有在continuum上增加服务器的地点逆时针方向的 第一台服务器上的键会受到影响。

Consistent Hashing 添加服务器

因此,Consistent Hashing最大限度地抑制了键的重新分布。 而且,有的Consistent Hashing的实现方法还采用了虚拟节点的思想。

使用一般的hash函数的话,服务器的映射地点的分布非常不均匀。 因此,使用虚拟节点的思想,为每个物理节点(服务器) 在continuum上分配100~200个点。这样就能抑制分布不均匀, 最大限度地减小服务器增减时的缓存重新分布。

通过下文中介绍的使用Consistent Hashing算法的memcached客户端函数库进行测试的结果是, 由服务器台数(n)和增加的服务器台数(m)计算增加服务器后的命中率计算公式如下:

(1 - n/(n+m)) * 100

加载中
返回顶部
顶部