Memcached分布式结构和Consistent Hashing算法

本文转自：http://www.xiaoyaochong.net/wordpress/?p=210

Memcached尽管是“分布式”缓存服务器，但服务器端并没有分布式功能。各个Memchached不会互相通信以共享信息。那么，怎么样进行分布式呢？完全取决于客户端的实现。

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

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

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

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

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

 

前面将到Memcached服务端是不会互相通信共享信息的，分布式的实现核心是客户端的算法，这个算法叫做Consistent Hashing，关于Consistent Hashing的思想，读者可以在网上搜索详细的分析，这里只简单说明一下。

 

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

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

 因此，Consistent Hashing最大限度地抑制了键的重新分布。而且，有的Consistent Hashing的实现方法还采用了虚拟节点的思想。使用一般的hash函数的话，服务器的映射地点分布非常不均匀。

 

引系使用虚拟节点的思想，为每个物理节点服务器的continuum上分配100～200个点。这样就能抑制分布不均匀，最大限度地减少服务器增减时的缓存重新分布。

 

通过上文介绍的算法，Memcached客户端函数库进行测试的结果是，由服务器台数（n）和增加的服务器台数（m）计算增加服务器后的命中率计算公式如下：

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