Memcached分布式结构和Consistent Hashing算法【转载】

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

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

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

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

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

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