memcache 分布式，算法实现

qq70191

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 服务器发生故障 无法连接，也不会影响其他的缓存，系统依然能继续运行。
 
分布式算法  
缓存系统中应用比较多的是余数计算分散和一致性 HASH 计算分散。
余数计算分散  
原理
余数计算分散法简单来说，就是 “ 根据服务器台数的余数进行分散 ” 。
1.          求得传入键的整数哈希值（ int hashCode ）。
2.          使用计算出的 hashCode 除以服务器台数 (N) 取余数（ C=hashCode % N ）
3.          在 N 台服务器中选择序号为 C 的服务器。
特点
余数计算的方法简单，数据的分散性也相当优秀，但也有其缺点。 那就是当添加或移除服务器时，缓存重组的代价相当巨大。 添加服务器后，余数就会产生巨变，这样就无法获取与保存时相同的服务器， 从而影响缓存的命中率。
Consistent Hashing
算法
一致性 HASH 算法我的理解，简单来说就是 , 在一个大的数据范围内的构建一个虚拟的环，首（ 0 ）尾（ Integer.MAXVALUE ）相接的圆环，然后通过 某种    HASH    算法    增加虚拟节点的方式（ 1 个实体节点可以虚拟 N 个虚拟阶段，如 160 ， 200 ， 1000 等）让节点更为均匀的分别在环上。 KEY 请求的时候，也通过相同的某种  HASH 算法 计算出 HASH 值，然后在在到环上定位同向最接近的虚拟节点，最后通过虚拟节点与实体节点的对应关系找到服务的实体节点。

 

网上介绍很多，图也多，不想在截取了。那就给个连接：
http://blog.csdn.net/sparkliang/article/details/5279393
另外公司现有的项目中也使用 Consistent Hashing 用于分表定位，缓存定位等。工程项目中也有先关算法的实现。
 
特点
1.   算法实现比较麻烦，需要构建虚拟环。
2.   解决了余数算法增加节点命中大幅额度降低的问题，理论上，插入一个实体节点，平均会影响到：虚拟节点数 /2 的节点数据的命中
 
参考：http://acooly.iteye.com/blog/1120819