随笔 - 94  文章 - 0  trackbacks - 0
<2020年2月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
1234567

常用链接

留言簿

随笔分类

随笔档案

收藏夹

调试技巧

搜索

  •  

最新评论

阅读排行榜

评论排行榜

60天内阅读排行

取模
最简单的hash算法

targetServer = serverList[hash(key) % serverList.size]

直接用key的hash值(计算key的hash值的方法可以自由选择,比如算法CRC32、MD5,甚至本地hash系统,如Java的hashcode)模上server总数来定位目标server。这种算法不仅简单,而且具有不错的随机分布特性。

但是问题也很明显,server总数不能轻易变化。因为如果增加/减少memcached server的数量,对原先存储的所有key的后续查询都将定位到别的server上,导致所有的cache都不能被命中而失效。

一致性hash
为了解决这个问题,需要采用一致性hash算法(consistent hash)
相对于取模的算法,一致性hash算法除了计算key的hash值外,还会计算每个server对应的hash值,然后将这些hash值映射到一个有限的值域上(比如0~2^32)。通过寻找hash值大于hash(key)的最小server作为存储该key数据的目标server。如果找不到,则直接把具有最小hash值的server作为目标server。

为了方便理解,可以把这个有限值域理解成一个环,值顺时针递增。
circle space
如上图所示,集群中一共有5个memcached server,已通过server的hash值分布到环中。

如果现在有一个写入cache的请求,首先计算x=hash(key),映射到环中,然后从x顺时针查找,把找到的第一个server作为目标server来存储cache,如果超过了2^32仍然找不到,则命中第一个server。比如x的值介于A~B之间,那么命中的server节点应该是B节点
image
可以看到,通过这种算法,对于同一个key,存储和后续的查询都会定位到同一个memcached server上。

那么它是怎么解决增/删server导致的cache不能命中的问题呢?
假设,现在增加一个server F,如下图


此时,cache不能命中的问题仍然存在,但是只存在于B~F之间的位置(由C变成了F),其他位置(包括F~C)的cache的命中不受影响(删除server的情况类似)。尽管仍然有cache不能命中的存在,但是相对于取模的方式已经大幅减少了不能命中的cache数量。

虚拟节点
但是,这种算法相对于取模方式也有一个缺陷:当server数量很少时,很可能他们在环中的分布不是特别均匀,进而导致cache不能均匀分布到所有的server上。

posted on 2019-12-18 15:42 长戟十三千 阅读(30) 评论(0)  编辑 收藏 引用 所属分类: 编程技巧随笔

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理