memcached

memcached缓存特点

1. 协议简单
2. 基于libevent的事件处理
3. 内置内存存储方式
4. memcached不相互通信的分布式

memcached分布式原理

今天的内容主要涉及memcached特点的第四条，memcached不相互通信，那么memcached是如何实现分布式的呢？memcached的分布式实现主要依赖客户端的实现：

memcached分布式

如上图所示，我们看下缓存的存储的一般流程：

当数据到达客户端，客户端实现的算法就会根据“键”来决定保存的memcached服务器，服务器选定后，命令他保存数据。取的时候也一样，客户端根据“键”选择服务器，使用保存时候的相同算法就能保证选中和存的时候相同的服务器。

余数计算分散法

余数计算分散法是memcached标准的memcached分布式方法，算法如下：

CRC($key)%N

该算法下，客户端首先根据key来计算CRC，然后结果对服务器数进行取模得到memcached服务器节点，对于这种方式有两个问题值得说明一下：

1. 当选择到的服务器无法连接的时候，一种解决办法是将尝试的连接次数加到key后面，然后重新进行hash，这种做法也叫rehash。
2. 第二个问题也是这种方法的致命的缺点，尽管余数计算分散发相当简单，数据分散也很优秀，当添加或者移除服务器的时候，缓存重组的代价相当大。

Consistent Hashing算法

Consistent Hashing算法描述如下：首先求出memcached服务器节点的哈希值，并将其分配到0~2^32的圆上，这个圆我们可以把它叫做值域，然后用同样的方法求出存储数据键的哈希值，并映射到圆上。然后从数据映射到的位置开始顺时针查找，将数据保存到找到的第一个服务器上，如果超过0~2^32仍找不到，就会保存在第一台memcached服务器上：

memcachd基本原理

再抛出上面的问题，如果新添加或移除一台机器，在consistent Hashing算法下会有什么影响。上图中假设有四个节点，我们再添加一个节点叫node5:

添加了node节点之后

node5被放在了node4与node2之间，本来映射到node2和node4之间的区域都会找到node4，当有node5的时候，node5和node4之间的还是找到node4，而node5和node2之间的此时会找到node5，因此当添加一台服务器的时候受影响的仅仅是node5和node2区间。

优化的Consistent Hashing算法

上面可以看出使用consistent Hashing最大限度的抑制了键的重新分配，且有的consistent Hashing的实现方式还采用了虚拟节点的思想。问题起源于使用一般hash函数的话，服务器的映射地点的分布非常不均匀，从而导致数据库访问倾斜，大量的key被映射到同一台服务器上。为了避免这个问题，引入了虚拟节点的机制，为每台服务器计算出多个hash值，每个值对应环上的一个节点位置，这种节点叫虚拟节点。而key的映射方式不变，就是多了层从虚拟节点再映射到物理机的过程。这种优化下尽管物理机很少的情况下，只要虚拟节点足够多，也能够使用得key分布的相对均匀。