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/