Memcached之你真正理解LRU吗(4)

众所周知，Memcached使用的是LRU（Least Recently Used最近最少使用）算法来回收缓存，将那些属于LRU的数据移出内存，从而腾出空间来加载另外的数据。那么Memcached的最近最少使用算法是怎么实现的呢？也许很多人都会回答：不就是在内存满了的情况下，把最近最少使用的Key替换掉，然后插入新的Key-Value键值对吗？其实不然，下面我们来深入的分析Memcached的LRU的内部实现，在分析LRU之前，让我们先了解一下Memcached的内部原理。

Memcached的内存分配

Memcached是采用Slab Allocator机制分配、管理内存，首先，我们必须理解三个概念：

Slab	相同Chunk大小的集合，一个Slab包含多个Page，一个Page（默认是1M）包含多个Chunk，Chunk就是最终存放数据的地方。
Page	Page默认是1M，一个Page包含多个Chunk。
Chunk	默认情况下Chunk的大小是：96，随着指定的增长因子变化（参数-f <factor>）

Slab Allocator机制是将分配给Memcached的内存，切分成若干个Slab，每个Slab下的Page的大小默认是1M，也就是说，如果一个Slab占用了50M的内存的话，在默认的情况下就有50个Page。在Memcached启动的时候是没有活动的Slab的，在插入数据的时候，如果Chunk不够用才会申请Slab，一旦分配了内存就不会释放，重复利用。

具体如图所示：

Memcached缓存原理

Memcached根据收到的数据的大小，选择最适合数据大小的Slab（如下图）。 Memcached中保存着slab内空闲chunk的列表，根据该列表选择chunk，然后将数据缓存于其中。

Memcached的内存浪费：

将100字节的数据缓存到128字节的chunk中，剩余的28字节就浪费了（如下图）：

了解了上面的一些Memcached基础概念之后，我们接下来说一下Memcached LRU的原理。

Memcache LRU：

首先我们要知道：

1，Memcached的LRU算法针对每个Slab执行，而不是针对整体。

2，数据只会存在指定的Slab中，即使该Slab已经满了，而且更大的Slab有空间，这种情况会在指定的Slab执行LRU算法，因为数据不会被存放到更大的Slab中。

一个Slab会有多个Page，一个page默认是1M，启动Memcached会预分配1M，当1M的数据满之后，如果有新数据进来，那么会重新分配一个Page给这个slab，但是Memcached是有内存上限的，如果不能申请Page的话，这时候就要针对这个Slab再利用LRU算法剔除掉最近最少使用的数据了。

注：

所有的Slab都会分配一个Page，就算超出了-m参数指定的内存大小。

过期的数据如果没被显式调用get，也要占用空间。因为LRU是针对双向链表前面的数据，每个Slab由两个指针来维护该双向链表，即heads和tails指针，分别指向最老的数据和最新的数据。这就可能导致没有过期的数据被踢。

一种有效缓解使用LRU的方法是：

1，避免大对象

如果系统上只有及个别几个大对象的话，会浪费内存空间，因为Slab申请了Page是不能释放内存的，及个别大对象会导致Slab申请了内存资源而得不到充分的利用。

2，调整增长因子

根据项目的需求调整增长因子，使内存充分利用。

总而言之，言而总之，就是让内存充分利用。避免Slab中的Chunk虚位以待。

参考文档：（以下的资料可以认真看一下，虽然有点老，对了解Memcached还是很有帮助的）

http://blog.charlee.li/memcached-001/

http://blog.charlee.li/memcached-002/

http://blog.charlee.li/memcached-003/

http://blog.charlee.li/memcached-004/

http://blog.charlee.li/memcached-005/