文档章节

memcached全面剖析–4. memcached的分布式算法

蜀山下的鱼
 蜀山下的鱼
发布于 2015/04/29 00:44
字数 1046
阅读 2
收藏 0
至于memcached的分布式,则是完全由客户端程序库实现的。这种分布式是memcached的最大特点。

memcached的分布式是什么意思?

这里多次使用了“分布式”这个词,但并未做详细解释。现在开始简单地介绍一下其原理,各个客户端的实现基本相同。

下面假设memcached服务器有node1~node3三台,应用程序要保存键名为“tokyo”“kanagawa”“chiba”“saitama”“gunma” 的数据。


图1 分布式简介:准备

首先向memcached中添加“tokyo”。将“tokyo”传给客户端程序库后,客户端实现的算法就会根据“键”来决定保存数据的memcached服务器。服务器选定后,即命令它保存“tokyo”及其值。


图2 分布式简介:添加时

同样,“kanagawa”“chiba”“saitama”“gunma”都是先选择服务器再保存。

接下来获取保存的数据。获取时也要将要获取的键“tokyo”传递给函数库。函数库通过与数据保存时相同的算法,根据“键”选择服务器。使用的算法相同,就能选中与保存时相同的服务器,然后发送get命令。只要数据没有因为某些原因被删除,就能获得保存的值。


图3 分布式简介:获取时

这样,将不同的键保存到不同的服务器上,就实现了memcached的分布式。 memcached服务器增多后,键就会分散,即使一台memcached服务器发生故障无法连接,也不会影响其他的缓存,系统依然能继续运行。

 

根据余数计算分散

求得键的整数哈希值,再除以服务器台数,根据其余数来选择服务器。

根据余数计算分散的缺点

余数计算的方法简单,数据的分散性也相当优秀,但也有其缺点。那就是当添加或移除服务器时,缓存重组的代价相当巨大。添加服务器后,余数就会产生巨变,这样就无法获取与保存时相同的服务器,从而影响缓存的命中率。

Consistent Hashing

Consistent Hashing如下所示:首先求出memcached服务器(节点)的哈希值,并将其配置到0~232的圆(continuum)上。然后用同样的方法求出存储数据的键的哈希值,并映射到圆上。然后从数据映射到的位置开始顺时针查找,将数据保存到找到的第一个服务器上。如果超过232仍然找不到服务器,就会保存到第一台memcached服务器上。


图4 Consistent Hashing:基本原理

从上图的状态中添加一台memcached服务器。余数分布式算法由于保存键的服务器会发生巨大变化而影响缓存的命中率,但Consistent Hashing中,只有在continuum上增加服务器的地点逆时针方向的第一台服务器上的键会受到影响。


图5 Consistent Hashing:添加服务器

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

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

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

总结

本次介绍了memcached的分布式算法,主要有memcached的分布式是由客户端函数库实现,以及高效率地分散数据的Consistent Hashing算法。下次将介绍mixi在memcached应用方面的一些经验,和相关的兼容应用程序。

 

 

本文转载自:http://blog.csdn.net/caiwenfeng_for_23/article/details/8569992

蜀山下的鱼
粉丝 9
博文 405
码字总数 0
作品 0
广州
高级程序员
私信 提问
memcached完全剖析–1. memcached的基础

memcached完全剖析–1. memcached的基础 memcached全面剖析–2.理解memcached的内存存储 memcached全面剖析–3.memcached的删除机制和发展方向 memcached全面剖析–4. memcached的分布式算法...

云栖希望。
2017/12/04
0
0
Memcache基础及工作原理

Memcache工作原理总结http://itindex.net/detail/48448-memcache-%E5%B7%A5%E4%BD%9C-%E5%8E%9F%E7%90%86 深入理解Memcache原理 Memcache内存分配策略http://itindex.net/detail/51456-memca......

醉公子
2016/06/09
52
0
memcached全面剖析–4. memcached的分布式算法

版权声明:可以任意转载,但转载时必须标明原作者charlee、原始链接http://tech.idv2.com/2008/07/24/memcached-004/以及本声明. 之前介绍了memcached的内部情况。本次不再介绍memcached的内...

flynewton
2010/10/15
1K
0
Memcached全面剖析

整个网站应用中,缓存几乎无处不在,既存在于浏览器、也存在于应用服务器和数据库服务器;既可以对数据缓存(分布式缓存),也可以对文件缓存(分布式存储系统),还可以对页面片段缓存(ESI...

亚特兰缇斯
2016/04/03
59
0
【PDF分享】memcached全面剖析.pdf

文档目录: 第1 章 memcached的基础.............................5 1.1 memcached是什么?..............................5 1.2 memcached的特征...............................6 协议简单......

鉴客
2010/09/12
6.8K
43

没有更多内容

加载失败,请刷新页面

加载更多

Handler消息传递机制分析

Handler的用途和用法 写过Android程序的人大概都会遇到ANR(Application Not Responding)。如果程序在一段时间内没有响应,系统就会弹出一个对话框,让用户选择继续等待还是强制关闭应用。为...

tommwq
今天
5
0
JS前端MD5加密

Bootstrap官网获得md5 js地址:https://www.bootcdn.cn/blueimp-md5/ <!--MD5加密--><script src="https://cdn.bootcss.com/blueimp-md5/2.10.0/js/md5.js"></script> 使用方法: md5(pwd)......

被毒打的程序猿_先瑞
今天
6
0
BigDecimal 去后面无用的0的方法

BigDecimal a=new BigDecimal("0.1000"); System.out.println(a.stripTrailingZeros().toPlainString());...

xiaodong16
今天
7
0
JAVA--高级基础开发

[集合版双色球] 十二、双色球规则:双色球每注投注号码由6个红色球号码和1个蓝色球号码组成。红色球号码从1—33中选择;蓝色球号码从1—16中选择;请随机生成一注双色球号码。(要求同色号码...

李文杰-yaya
昨天
25
0
聊聊rocketmq broker的CONSUMER_SEND_MSG_BACK

序 本文主要研究一下rocketmq broker的CONSUMER_SEND_MSG_BACK CONSUMER_SEND_MSG_BACK rocketmq/common/src/main/java/org/apache/rocketmq/common/protocol/RequestCode.java public class......

go4it
昨天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部