详解MemCached原理

memcached是一个高性能的分布式内存缓存服务器，memcached在Linux上可以通过yum命令安装，这样方便很多，在生产环境下建议用Linux系统，memcached使用libevent这个库在Linux系统上才能发挥它的高性能。它的分布式其实在服务端是不具有分布式的特征的，是依靠客户端的分布式算法进行了分布式，memcached是一个纯内存型的数据库，这样在读写速度上相对来说比较快。

memcached的内存分配是预先分配内存，常规的程序使用内存无非是两种，一种是预先分配，一种是动态分配。动态分配从效率的角度来讲相对来说要慢点，因为它需要实时的去分配内存使用，但是这种方式的好处就是可以节约内存使用空间；memcached采用的是预先分配的原则，这种方式是拿空间换时间的方式来提高它的速度，这种方式会造成不能很高效的利用内存空间，但是memcached采用了Slab Allocation机制来解决内存碎片的问题，Slab Allocation的基本原理就是按照预先规定的大小，将分配的内存分割成特定长度的块，并把尺寸相同的块分成组（chunk的集合），借用一下网上的图：

memcached会针对客户端发送的数据选择slab并缓存到chunk中，这样就有一个弊端那就是比如要缓存的数据大小是50个字节，如果被分配到如上图88字节的chunk中的时候就造成了33个字节的浪费，虽然在内存中不会存在碎片，但是也造成了内存的浪费，这也是我上面说的拿空间换时间的原因，不过memcached对于分配到的内存不会释放，而是重复利用。默认情况下如下图chunk是1.25倍的增加的，当然也可以自己通过-f设置，这种内部的分割算法可以参看源码下的slabs.c文件。

memcached本身内部不会监视记录是否过期，而是当get时依靠记录的过期时间检查是否过期，这也是memcached的一种惰性过期机制。默认情况下memcached内部也维护着一套LRU置换算法，当设定的内存满的时候，会进行最近很少使用的数据置换出去从而分配空间，所以对于提升memcached命中率的问题主要还是一是根据业务存放的value值来调整好chunk的大小以达到最大效率的利用内存；二是扩大内存保证所有缓存的数据不被置换出去。

对于memcached的分布式完全就是依靠客户端的一致哈希算法来达到分布式的存储，因为本身各个memcached的服务器之间没办法通信，并不存在副本集或者主从的概念，它的分布式算法主要是先求出每一个memcached的服务器节点的哈希值，并将它们分配到2的32次方的圆上，然后根据存储的key的哈希值来映射到这个圆上，属于哪个区间顺时针找到的节点就存到这个服务器节点上，大致借用图表示如下图：

然而当添加新的memcached节点的时候必然会打乱现有这个圆的结构，这时候是没办法完全保证你以前的key依然会存在之前的节点上，但是这种结构却是能保证在添加缓存服务器的时候把损失降到最小，受结构调整后key不能命中的只有在这个圆上新增的服务器节点逆时针的第一台服务器上，其他的是不受影响的，借用图如下：

memcached和redis一样内部的存储都是key/Value的形式，正是这种哈希表数据结构保证了在内存中查找的时间的复杂度为O(1)，整体上memcached的高性能这两个哈希结构起了很大的最用，当然还有memcached的多路复用I/O模型也在高并发下起到了很大的作用。另外memcached的内部操作还具有CAS原子操作，这种利用CPU指令集的操作来保证在单个节点下数据的一致性效率相对来说比加锁要高很多。