转载自：http://www.cnblogs.com/xrq730/p/4948707.html
概念
MemCache是一个自由的、开源的、高性能、分布式的”分布式内存对象缓存系统“，用于动态web应用以减轻数据库的负载。
基本原理
MemCache的数据结构是一个存储键值对的HashMap，访问模型原理图如下：
从这个图可以看到，在应用程序服务器上，应用程序如果想访问memcache里的数据，需要有memcache客户端程序，通过memcache API，首先利用路由算法从memcache服务器列表中找到对应服务器，之后再通过通信模块从memcache服务器集群中找到memcache服务器
整理一下读写过程，写缓存的流程如下：
- 应用程序输入需要写缓存的数据到Memcache客户端程序
- MemCache API将key输入路由算法模块，路由算法根据key和Memcache集群服务器列表得到一台服务器编号
- 由服务器编号得到Memcache机器的ip地址和端口号
- API调用通信模块和指定编号的MemCache服务器进行通信，将数据写入该服务器，完成一次分布式缓存的写操作
读过程和写过程相似，使用相同的路由算法和服务器列表，如果在不命中的情况下，会访问数据库，然后执行写缓存操作
需要澄清的是，尽管Memcache被称为“分布式缓存”，但是Memcache本身完全不具备分布式的特点，Memcache服务器集群中的各服务器之间并不互相通信，也就是说，没有同步机制，一台服务器的缓存数据更新时，不会通知其他服务器更新缓存数据，两台服务器中的缓存内容并不相同。这种分布式完全依赖于应用程序服务器的路由算法实现的。
宕机的情况MemCache如何应对：
假如有Node2宕机，那么Node2上存储的数据都不可用了，此时由于集群中的Node0和Node1还存在，下一次请求Node2中存储的数据Key值的时候，肯定没有命中，这时先从数据库中拿到要缓存的数据，然后路由算法模块根据key值在Node0和Node1中选取一个服务器，把对应的数据存放进去，这样下次就又可以走缓存了。
路由算法
从上面的图中，可以看出一个很重要的问题，就是对服务器集群的管理，路由算法至关重要，就和负载均衡算法一样，路由算法决定着究竟该访问集群中的哪台服务器，先看一个简单的路由算法。
-
余数Hash简单的取余数思想，由于HashCode随机性比较强，所以使用余数Hash路由算法就可以保证缓存数据在整个MemCache服务器集群中有比较均衡的分布。问题：如果不考虑服务器集群的伸缩性，那么余数Hash算法几乎可以满足绝大多数的缓存路由需求，但是当分布式缓存集群需要扩容的时候，就难办了。比方说，字符串str对应的HashCode是50、服务器的数目是3，取余数得到1，str对应节点Node1，所以路由算法把str路由到Node1服务器上。假设MemCache服务器集群由3台变为4台吧，更改服务器列表，仍然使用余数Hash，50对4的余数是2，对应Node2，但是str原来是存在Node1上的，这就导致了缓存没有命中。如果扩容到20+的台数，只有前三个HashCode对应的Key是命中的，也就是15%。扩容后会造成大量数据无法正确命中，尽管后续阶段会通过访问数据库的方式将新缓存数据存放到对应的新服务器上，但是原有的缓存并没有被释放（过期将被释放）。在网站业务中，大部分的业务数据度操作请求上事实上是通过缓存获取的，只有少量读操作会访问数据库，因此数据库的负载能力是以有缓存为前提而设计的。当大部分被缓存了的数据因为服务器扩容而不能正确读取时，这些数据访问的压力就落在了数据库的身上，这将大大超过数据库的负载能力，严重的可能会导致数据库宕机。解决办法：分2步：第一步，在网站访问量低谷，通常是深夜，技术团队加班，扩容、重启服务器；第二步，通过模拟请求的方式逐渐预热缓存，使缓存服务器中的数据重新分布
- 一致性Hash
一致性哈希算法通过一个叫做一致性Hash环的数据结构实现Key到缓存服务器的Hash映射。
具体算法过程为：先构造一个长度为2^32的整数环（这个环被称为一致性哈希环），根据节点的Hash值（其分布为[0,2^32-1]）将缓存服务器节点放置在这个Hash环上，然后根据需要缓存的数据的Key值计算得到其Hash值（其分布也为[0, 232-1]），然后在Hash环上顺时针查找距离这个Key值的Hash值最近的服务器节点，完成Key到服务器的映射查找。
原理图如下：
看到加了一个Node4节点，只影响到了一个Key值的数据，本来这个Key值应该是在Node1服务器上的，现在要去Node4了。采用一致性Hash算法，的确会影响到整个集群，但是影响的只是加粗的那一段而已，相比余数Hash算法影响了远超一半的影响率，这种影响要小得多。更重要的是，集群中缓存服务器节点越多，增加节点带来的影响越小，很好理解。换句话说，随着集群规模的增大，继续命中原有缓存数据的概率会越来越大，虽然仍然有小部分数据缓存在服务器中不能被读到，但是这个比例足够小，即使访问数据库，也不会对数据库造成致命的负载压力。
MemCache实现原理
首先要说明一点，MemCache的数据存放在内存中，存放在内存中意味着几点：
1、访问数据的速度比传统的关系型数据库要快，因为Oracle、MySQL这些传统的关系型数据库为了保持数据的持久性，数据存放在硬盘中，IO操作速度慢
2、MemCache的数据存放在内存中同时意味着只要MemCache重启了，数据就会消失
3、既然MemCache的数据存放在内存中，那么势必受到机器位数的限制32位机器最多只能使用2GB的内存空间，64位机器可以认为没有上限
然后看一下MemCache的原理，MemCache最重要的莫过于内存分配的知识点，MemCache采用的内存分配方式是固定空间分配，一张图说明：
这张图片里面涉及了slab_class、slab、page、chunk四个概念，它们之间的关系是：
1、MemCache将内存空间分为一组slab
2、每个slab下又有若干个page，每个page默认是1M，如果一个slab占用100M内存的话，那么这个slab下应该有100个page
3、每个page里面包含一组chunk，chunk是真正存放数据的地方，同一个slab里面的chunk的大小是固定的
4、有相同大小chunk的slab被组织在一起，称为slab_class
MemCache内存分配的方式称为allocator，slab的数量是有限的，几个、十几个或者几十个，这个和启动参数的配置相关。
MemCache中的value过来存放的地方是由value的大小决定的，value总是会被存放到与chunk大小最接近的一个slab中，比如slab[1]的chunk大小为80字节、slab[2]的chunk大小为100字节、slab[3]的chunk大小为128字节（相邻slab内的chunk基本以1.25为比例进行增长，MemCache启动时可以用-f指定这个比例），那么过来一个88字节的value，这个value将被放到2号slab中。放slab的时候，首先slab要申请内存，申请内存是以page为单位的，所以在放入第一个数据的时候，无论大小为多少，都会有1M大小的page被分配给该slab。申请到page后，slab会将这个page的内存按chunk的大小进行切分，这样就变成了一个chunk数组，最后从这个chunk数组中选择一个用于存储数据。
如果这个slab中没有chunk可以分配了怎么办，如果MemCache启动没有追加-M（禁止LRU，这种情况下内存不够会报Out Of Memory错误），那么MemCache会把这个slab中最近最少使用的chunk中的数据清理掉，然后放上最新的数据。针对MemCache的内存分配及回收算法，总结三点：
1、MemCache的内存分配chunk里面会有内存浪费，88字节的value分配在128字节（紧接着大的用）的chunk中，就损失了40字节，但是这也避免了管理内存碎片的问题
2、MemCache的LRU算法不是针对全局的，是针对slab的
3、应该可以理解为什么MemCache存放的value大小是限制的，因为一个新数据过来，slab会先以page为单位申请一块内存，申请的内存最多就只有1M，所以value大小自然不能大于1M了
MemCache的特性和限制
上面已经对于MemCache做了一个比较详细的解读，这里再次总结MemCache的限制和特性：
1、MemCache中可以保存的item数据量是没有限制的，只要内存足够
2、MemCache单进程在32位机中最大使用内存为2G，这个之前的文章提了多次了，64位机则没有限制
3、Key最大为250个字节，超过该长度无法存储
4、单个item最大数据是1MB，超过1MB的数据不予存储
5、MemCache服务端是不安全的，比如已知某个MemCache节点，可以直接telnet过去，并通过flush_all让已经存在的键值对立即失效
6、不能够遍历MemCache中所有的item，因为这个操作的速度相对缓慢且会阻塞其他的操作
7、MemCache的高性能源自于两阶段哈希结构：第一阶段在客户端，通过Hash算法根据Key值算出一个节点；第二阶段在服务端，通过一个内部的Hash算法，查找真正的item并返回给客户端。从实现的角度看，MemCache是一个非阻塞的、基于事件的服务器程序
8、MemCache设置添加某一个Key值的时候，传入expiry为0表示这个Key值永久有效，这个Key值也会在30天之后失效，见memcache.c的源代码