Memcached的分布式
Memcached虽然称为“分布式”缓存服务器，但服务器端并没有“分布式”功能。服务器端仅包括内存存储功能，至于memcached的分布式，则是完全由客户端程序库实现的。这种分布式是memcached的最大特点。
那么memcached的分布式是什么意思呢？
下面假设memcached服务器有node1、node2、node3三台，应用程序要保存键名为“tokyo”、“kanagawa”、“chiba”、“saitama”、“gunma”的数据。
首先向memcached中添加“tokyo”，将“tokyo”传给客户端程序库后，客户端实现的算法就会根据“键”来决定保存数据的memcached服务器。服务器选定后，即命令它保存“tokyo”及其值。如下图：
同样，“kanagawa”、“chiba”、“saitama”、“gunma”都是先选择服务器再保存。接下来获取保存的数据。获取时也要将要获取的键“tokyo”传递给函数库。函数库通过与数据保存时相同的算法，根据“键”选择服务器。使用的算法相同，就能选中与保存时相同的服务器，然后发送get命令。只要数据没有因为某些原因被删除，就能获得保存的值。
这样，将不同的键保存到不同的服务器上，就实现了memcached 的分布式。memcached 服务器增多后，键就会分散，即使一台 memcached 服务器发生故障无法连接，也不会影响其他的缓存，系统依然能继续运行。
分布式算法
1）Memcached分布式部署之普通Hash算法分布
普通Hash算法是根据余数计算分散，根据服务器台数的余数进行分散，求得Key的整数哈希值，再除以服务器台数，根据其余数来选择服务器。下面提供一个图供参考。
比如：对于字符串string（一个Key），先求得string的整数哈希值，这里比如是50。而服务器的数目是3，50对3取余等于2，那么此string对应的节点就是node2。所以路由算法把string路由到node2服务器上存储。由于求哈希值随机性比较强，所以使用余数hash路由算法就可以保证缓存数据在整个Memcache服务器集群中有比较好的均匀性分布。
余数计算的方法简单，数据的分散性也相当优秀，普通Hash分布对于Memcached服务器数量固定的情况推荐使用。但也有其缺点，那就是当添加或移除服务器时，缓存重组的代价相当巨大。添加服务器后，余数就会产生巨变，这样就无法获取与保存时相同的服务器，从而影响缓存的命中率。对于服务器集群伸缩性支持的不太很好。
比如：由于3台memcache集群无法支持现有的业务，需要在添加2台成员，此时服务器集群由3台变成了5台。那么你就需要在客户端添加服务器列表，此时对于key(string)哈希值还是50，路由计算时就是50除以5取余等于0，对应的服务器是node0，这就会导致客户端再次查询string时缓存不会命中，同时对于node2来说也是浪费了内存。
由于hash算法主要依据服务器数来进行分布，所以当服务器数有变化时就会导致整个集群数据访问出现问题。这里只是列举了一个Key，在实际业务中对于增加服务器或减少服务器会导致大量的Key缓存不会命中。这显然也是无法接受的，所有对于此类分布式又出来了另外一种算法，就是一致性Hash算法。
2）Memcached分布式部署之一致性Hash算法分布（Consistent Hashing）
当Memcache服务器数量固定时，普通Hash分布可以很好的运作。但是当服务器数量发生改变时，问题就出来了。因为同一个Key经Hash算法处理后，与服务器数量取模，会导致结果与服务器数量未变化时不同，这就导致之前保存的数据丢失。采取一致性Hash分布可以有效的解决这个问题，把丢失的数据减到最小（注意这里并没有说完全不丢失）。
一致性Hash分布算法分4个步骤：
步骤1：将一个32位整数[0 ~ (2^32-1)]想象成一个环型Hash空间，其中0 作为开头，(2^32-1) 作为结尾。
步骤2：通过Hash函数把Key处理成整数。这样就可以在环上找到一个位置与之对应。
步骤3：把Memcached服务器群映射到环上，使用Hash函数处理服务器对应的IP地址即可。
步骤4：把数据映射到Memcached服务器上。查找一个Key对应的Memcached服务器位置的方法如下：从当前Key的位置，沿着圆环顺时针方向出发，查找位置离得最近的一台Memcached服务器，并将Key对应的数据保存在此服务器上。
大概过程就是如下图：
将string交给hash函数处理，换成整数比如为50，可以在环上找到一个对应的位置。然后处理服务器的IP也换算成整数，这里比如有node0为30、node1为80、node2为120，那么根据数据映射到Memcached服务器上的规则，从当前key的位置，沿着圆环顺时针方出发，查找位置离得最近的一台Memcached服务器进行数据存储，那么离50顺时针方向最近的数为80，所以就存储在node1这台服务器上。也很好理解。
上面对一致性hash算法说完之后，发现跟hash算法做的事情是一样的，并没有什么改变啊？的确没有什么变化，都是存储数据。但是当集群发生增加或较少服务器数量时呢？就能体现出一致性hash算法的有点了。比如对于现有的3台集群在添加1台node3服务器时会跟hash算法发生什么区别呢?
这里比如node3经过hash函数处理之后值为65，那么查找string Key时，由于string的哈希值为50，所以客户端路由会去离50顺时针方向最近的一台主机上获取缓存值，此时由于添加了一台hash值为65的node3服务器。那么客户端就会去node3服务器上查找string，当然也就发生了缓存命中失败，客户端又需要重新去数据库查找数据了。同样是缓存命中失败，但是一致性Hash算法只会影响到新添加服务器顺时针最近的一台主机，那就是hash值为80的服务器，而影响的Key的范围最大也就是从圆环位置为30到80这50个Key（最大哦），并不会像Hash算法那么使整个集群发生动荡。这就是一致性hash算法，也挺简单。
最后说一下，对于在个圆环上一致性Hash算法是怎么去找到顺时针方向离它最近的一个节点呢？这个就是使用了算法中的二叉树算法，二叉树算法很简单博客中搜索二叉树算法有介绍，一看就明白。至于一致性Hash算法想具体了解的，可以好好看看“Memcached分布式一致性hash算法”。
Memcache使用一致性Hash算法实例（在同一台MC服务器上测试）：
先在Memcached服务器上开启三个实例
|
1 2 3 4 5 6 7 8 9 10 11 |
[root@localhost ~]# killall memcached [root@localhost ~]# memcached -u nobody -d -p 11211 [root@localhost ~]# memcached -u nobody -d -p 11212 [root@localhost ~]# memcached -u nobody -d -p 11213 [root@localhost ~]# netstat -anplt | grep memcached tcp 0 0 0.0.0.0:11211 0.0.0.0:* LISTEN 30678/memcached tcp 0 0 0.0.0.0:11212 0.0.0.0:* LISTEN 30685/memcached tcp 0 0 0.0.0.0:11213 0.0.0.0:* LISTEN 30694/memcached tcp 0 0 :::11211 :::* LISTEN 30678/memcached tcp 0 0 :::11212 :::* LISTEN 30685/memcached tcp 0 0 :::11213 :::* LISTEN 30694/memcached |
然后在网站目录下建立一个hash.php的页面，代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
[root@localhost ~]# vi /usr/local/httpd/htdocs/hash.php <?php ini_set("memcache.hash_strategy","consistent"); ini_set("memcache.hash_function","crc32"); ini_set("error_reporting","E_CORE_ERROR"); ini_set("memcache.allow_failover","0"); $memcache = new Memcache; $memcache1 = new Memcache; $memcache2 = new Memcache; $memcache3 = new Memcache; $memcache->addServer('localhost', 11211); $memcache->addServer('localhost', 11212); $memcache->addServer('localhost', 11213); $memcache->flush(); $memcache1->connect('localhost',11211); $memcache2->connect('localhost',11212); $memcache3->connect('localhost',11213); $fp1 = fopen("mem1.txt","w"); $fp2 = fopen("mem2.txt","w"); $fp3 = fopen("mem3.txt","w"); for($i=0;$i<100;$i++){ $memcache->set($i,$i,0,120); fwrite($fp1,$memcache1->get($i)." "); fwrite($fp2,$memcache2->get($i)." "); fwrite($fp3,$memcache3->get($i)." "); } fclose($fp1); fclose($fp2); fclose($fp3); ?> |
然后在浏览器中执行http://192.168.60.10/hash.php，执行完之后会在三台服务器上一共存储100个键值，接下来分别在三台MC服务器上进行查看各自存储的键值。
第一台:11211
|
1 2 3 4 |
[root@localhost ~]# telnet 127.0.0.1 11211 stats STAT curr_items 38 STAT total_items 38 |
第二台:11212
|
1 2 3 4 |
[root@localhost ~]# telnet 127.0.0.1 11212 stats STAT curr_items 25 STAT total_items 25 |
第三台:11213
|
1 2 3 4 |
[root@localhost ~]# telnet 127.0.0.1 11213 stats STAT curr_items 37 STAT total_items 37 |
可以看到三台MC服务器上一共存储刚好100个键值。
