Memcached剖析
1. Memcached 简介
Memcached是以LiveJournal旗下Danga Interactive公司的Brad Fitzpatric为首开发的一款软件。现在已成为mixi、hatena、Facebook、Vox、LiveJournal等众多服务中提高Web应用扩展性的重要因素。
许多Web应用都将数据保存到RDBMS中，应用服务器从中读取数据并在浏览器中显示。但随着数据流的增大、访问的集中，就会出现RDBMS的负担加重、数据库响应恶化、网站显示延迟等重大影响。
这时就该Memcached大显身手了。Memcached是高性能的分布式内存缓存服务器。一般的使用目的是，通过缓存数据库查询结果，减少数据库访问次数，以提高动态Web应用的速度、提高可扩展性，如图1所示。
图1 一般情况下Memcached的用途
2. Memcached 的特征
Memcached作为高速运行的分布式缓存服务器，具有以下特征：
（1）协议简单：Memcached的服务器客户端通信并不使用复杂的XML等格式，而使用简单的基于文本行的协议。因此，通过telnet也能在Memcached上保存数据、取得数据。
（2）基libevent的事件处理：libevent是个程序库，它将Linux的epoll、BSD类操作系统的kqueue等事件处理功能封装成统一的接口。即使对服务器的连接数增加，也能发挥O(1)的性能。由于Memcached使用libevent库，因此能在Linux、BSD等操作系统上发挥其高性能。
（3）内置内存存储方式：为了提高性能，Memcached中保存的数据都存储在Memcached内置的内存存储空间中。另外，内容容量达到指定值之后，就基于LRU或3QLRU算法自动删除不使用的数据对象。Memcached本身是为缓存而设计的服务器，因此并没有过多考虑数据的永久性问题。
（4）Memcached不互相通信的分布式：Memcached尽管是分布式缓存服务器，但服务器端并没有提供分布式功能，各个Memcached服务器不会互相通信以共享信息，其分布式功能完全取决于客户端的实现。
3. Memcached 的内存存储
Memcached采用了名为Slab Allocator的机制分配、管理内存。在该机制出现以前，内存的分配是通过对所有记录简单地进行malloc和free来进行的。但是，这种方式会导致内存碎片，加重操作系统内存管理器的负担，最坏的情况下，会导致操作系统比Memcached进程本身还慢，Slab Allocator就是为解决该问题而诞生的。
图2 Slab Alloator结构图
Slab Allocator提前将大块内存划分为1MB大小的若干个slab，然后针对每个slab再进行小对象填充，这个小对象称为chunk，从而避免大量重复的初始化和清理，减轻了内存管理器的负担。Slab Allocator内存分配的原理是按照预先规定的大小，将分配给Memcached服务器的内存吸纳分割成特定长度的内存块（chunk），再把尺寸相同的内存块（chunk）分成组，这些内存块不会释放，可以重复利用。
图3 选择存储记录的组的方法
新增数据对象存储时，因Memcached服务器中保存着slab内空闲chunk的列表，它会根据该列表选择chunk，然后将数据缓存与其中。当有数据存入时Memcached时，根据接收到的数据大小，选择最适合数据大小的slab分配一个能存下这个数据的最小内存块（chunk）。例如：在图3的分配中，100字节的一个数据就会被分配存入112字节的一个内存块中，这样会有12字节被浪费，这部分空间就不能被使用了，这也是Slab Allocator机制的一个缺点。
4. Memcached 的数据驱逐机制
当新增数据对象存储时，若当前已无可用内存，Memcached需要一定机制驱逐旧数据以腾出内存空间容纳新对象，目前Memcached提供了两种数据对象驱逐策略：
（1）LRU
该策略为每个数据对象维护两个指针构建双向链表，当数据对象被访问后置于链表的MRU位置，内存不足时则从链表的LRU位置执行数据驱逐。
（2）3QLRU
该策略在（1）的基础上维护了三个LRU队列，即HOT_LRU、WARM_LRU、COLD_LRU。新分配的数据对象首先放置到HOT_LRU的MRU位置；当HOT_LRU或WARM_LRU队列中的数据对象超过预设的阈值后，将多余的数据对象转移到COLD_LRU中；如果某个位于COLD_LRU队列中的数据对象被访问，将其移动到WARM_LRU队列的MRU位置。
5. Memcached 的分布式实现
Memcached虽然称为分布式缓存服务器，但服务器端并没有分布式功能，Memcached的分布式功能是完全有客户端程序库实现的，如图4所示。这种分布式是Memcached的一大特点。
图4 Memcached的分布式
现在假设有4台Memcached服务器：node1 ~ node4，要保存键为key1 ~ key10的数据。首先往Memcached中添加key1，将key1传给客户端程序之后，客户端实现的分布式算法会根据这个键key1来决定保存数据的Memcached服务器。 服务器选定之后，将会用选定的服务器来保存key1和对应的值。在获取数据的时候，先通过要获取的数据的key来根据客户端实现的相同的算法选择对应的数据保存的服务器，然后取出数据。这样就实现了Memcached的分布式功能。部署的Memcached服务器越多，键就会越分散。即使一台服务器挂掉，也不会影响其他服务器的运行。
目前常用的分布式算法主要有两种：余数计算分散法、一致性哈希算法。
（1）余数计算分散法
这种方法简单的说就是根据服务器的台数的余数来进行分散。首先求取键所对应的整数哈希值，然后根据哈希值与服务器台数取模后的余数来选择服务器。这种方法简单高效，而且数据的分散性也非常的好。但问题是当增加或者删除一台Memcached服务器的时候，余数就会发生巨大的变化。这样就没有办法获取和保存时相对应的服务器，从而极大地降低缓存的命中率。
（2）一致性哈希算法
这种方法首先求出Memcached服务器的哈希值，然后将它分配到0~2^32的圆上，然后使用同样的办法求出数据对象的键的哈希值，将其映射到圆上。然后从数据对象映射的点开始顺时针的查找，将数据对象保存到查找到的第一台服务器上面。如果超出了2^32仍然没有找到服务器，那么就将数据对象保存到第一台Memcached服务器上面。
图5 一致性哈希原理图
这种方法在一定程度上在减少了修改Memcached服务器数量的时候对缓存命中率的影响。在一致性哈希算法中，只有在这个圆上，从增加服务器的那个点逆时针遇到的第一台服务器之间的键会受到影响。因此一致性哈希最大限度的抑制了键的重新分布。
另外一些一致性哈希算法也采用了虚拟节点的办法。因为使用一般的哈希函数的话，服务器的映射地点会分布的可能不太均匀，因此使用虚拟节点的思想，为每一台服务器在圆上分配100~300个点，这样就能够抑制分布不均匀，最大限度的减少服务器增加或减少的时候数据对象的重新分布。