Memcache（11）
网上其实有很多文章说明了memcached是如何运作的，特别是底层的内存分配是如何运作的。我参考过很多资料，比较有启发意义的有几个：
1. 几个关键概念
Page为内存分配的单位
Memcached的内存分配以page为单位，默认情况下一个page是1M，可以通过-I参数修改，最小1K，最大128M。如果需要申请内存时，memcached会划分出一个新的page并分配给需要的slab区域。page一旦被分配在memcached重启前不会被回收或者重新分配（page ressign已经从1.2.8版移除了）。
Slabs划分数据空间
Memcached并不是将所有大小的数据都放在一起的，而是预先将数据空间划分为一系列大小的slabs，每个slab只负责一定大小范围内的数据存储。每个slab只存储大于其上一个slab的size并小于或者等于自己最大size的数据。例如：slab 3只存储大小介于137 到 224 bytes的数据。如果一个数据大小为230byte的数据进行存储，它将被分配到slab 4中。每个slab负责的空间其实是不等的，memcached默认情况下下一个slab的最大值为前一个的1.25倍，这个可以通过修改-f参数来修改增长比例。
Chunk才是存放缓存数据的单位
Chunk是一系列固定的内存空间，这个大小就是管理它的slab的最大存放大小。例如：slab 1的所有chunk都是104byte，而slab 4的所有chunk都是280byte。chunk是memcached实际存放缓存数据的地方，因为chunk的大小固定为slab能够存放的最大值，所以所有分配给当前slab的数据都可以被chunk存下。如果实际的数据大小小于chunk的大小，空余的空间将会被闲置，这个是为了防止内存碎片而设计的。举例来说，如果chunk size是224byte，而存储的数据只有200byte，剩下的24byte将被闲置。此外，memcached允许配置的最小的chunk空间为48个字节（key+value+flags），通过-n参数可以调节这个数值。
2. 理解这三者之间的关系
要理解memcached是如何分配内存的就要从理解上述三个东西之间的关系开始。
page是memcached在收到内存不够的请求，并进行内存分配的单位。举例来说，slab2的所有空间都用完了，又有大小适合slab2的数据过来了，那么slab2就会向memcached请求新的内存空间，memcached就会划分一个page大小的内存量到slab2。page的默认大小是1M，这个数值可以通过参数-I来修改。
slab是memcached用来划定存储空间的大小概念，每当memcached启动的时候，它会按照-n参数配置的值（如果有的话，否则为默认值）来决定第一个slab的大小，然后根据-f参数的值来决定后续slab大小的增长速率，一个一个地决定后续的slab的大小，直到slab的大小达到设定的page大小（一般是1M）。
chunk是实际用来存储数据的内存空间，它的大小和包含它的slab的大小是一致的。当page大小的内存分配到slab的时候，slab会根据自身的大小将page大小的内存分割成 page / slabsize 个chunk。
memcached启动时候，slab创建以及chunk分配的细节可以参照下面的数据（使用-vv命令查看的详细内存分配过程）
/usr/bin/memcached -u nobody -m 64 -p 11211 -l 127.0.0.1 -vv
slab class & 1: chunk size & & & &96 perslab & 10922
slab class & 2: chunk size & & & 120 perslab & &8738
slab class & 3: chunk size & & & 152 perslab & &6898
slab class & 4: chunk size & & & 192 perslab & &5461
3. 举个例子来分析
首先，是memcached启动时候的情况：
商人A很有钱，他有100个大小一摸一样的仓库（100M的memcached服务器，每个page大小1M，就是一个仓库）。商人A根据自己的商品尺寸，将自己的仓库分成了42种（42个slab），定义为最小一种的仓库是专门用来存放尺寸为96的货物的（slab1大小为96个字节），然后每种仓库存放的货物大小都是之前一种的1.25倍（增长因子-f为1.25）。商人预先将42个仓库按照预定义的42种货物大小整理、装修了下（memcached启动时候的42个slab预分配、chunk分割）。1号仓库（slab1）中有10922个（1M
* 1024 * 1024 / 96）货物存储空间（chunk），后续的仓库类型的装修、空间分配都以此类推。
其次，来看下slab满了的时候的情况：
商人A进了一批尺寸是150的货物，共6899个。货物按大小分配，进入3号仓库（ slab3）。因为3号仓库是仓库类型3，其大小只有6898个位置（6898个chunk），6898个货物被安置到仓库类型3（slab3）的3号仓库里去。然后还多出来一个货物没地方放，商人就安排了一个新的仓库装修成仓库类型3（1M的空间分配给slab3，大小为152个字节，含6898个chunk），然后将多余的一个货物放入到新的仓库里。
这个例子看过以后，相信大家都已经很明白前述的三个概念之间的关系以及memcached是如何分配内存空间的了。
4. memcached里的内存浪费
读过上文之后大家应该很明白memcached的内存分配方式了。memcached这样分配内存的好处是不会存在内存碎片，但是坏处也很明显，就是内存的浪费。就拿前面的商人例子来说，如果遇到一种极端的情况，所有的货物进来的都是121个字节的大小，那么按逻辑他们都会被分到slab3里面去，也就是分到大小是152的slab里，也就是说每塞进一个对象，就会有31个字节的内存空间被浪费掉了。
5. memcached的数据回收机制
memcached内部不会监视记录是否过期，而是在get时查看记录的时间戳，检查记录是否过期。 这种技术被称为lazy（惰性）expiration。因此，memcached不会在过期监视上耗费CPU时间。如果某一个item在memcached里过期了，这个东西并不会被删除，而是客户端无法再看见该记录（invisible，透明）， 其存储空间即可重复使用。一般情况下memcached会优先使用已超时的记录的空间，但即使如此，也会发生追加新记录时空间不足的情况， 此时就要使用名为 Least Recently Used（LRU）机制来分配空间。
顾名思义，这是删除“最近最少使用”的记录的机制。 因此，当memcached的内存空间不足时（无法从slab class 获取到新的空间时），就从最近未被使用的记录中搜索，并将其空间分配给新的记录。
以上，主要是memcached的内存分配利用的一些经验。当然，memcached的配置、调优、监控在这篇文章里是没有涉及的
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：142762次
积分：2685
积分：2685
排名：第13142名
原创：69篇
转载：389篇
评论：10条
(2)(10)(18)(42)(4)(5)(5)(1)(20)(2)(10)(9)(42)(8)(22)(27)(45)(5)(7)(4)(4)(8)(6)(9)(7)(30)(20)(16)(9)(3)(25)(29)(5)每个slab包含若干大小为1M的内存页，这些内存又被分割成多个chunk，每个chunk存储一个item；
在mc启动初始化时，每个slab都预分配一个1M的内存页，由slabs_preallocate&完成(也可将相应代码注释掉关闭预分配功能)；
chunk的增长因子由-f指定，默认1.25，起始大小为48字节；
为实际存储数据的结构体，由两部分组成，属性信息和数据部分，数据部分包括cas，key和真实的value信息。
typedef&struct&_stritem&{&&
&&&&struct&_stritem&*//item在slab中存储时，是以双链表的形式存储的,next即后向指针&&
&&&&struct&_stritem&*//prev为前向指针&&
&&&&struct&_stritem&*h_//Hash桶中元素的链接指针&&
&&&&rel_time_t&&&&&&&//最近访问时间&&
&&&&rel_time_t&&&&&&//过期时间&&
&&&&int&&&&&&&&&&&&&//数据大小&&
&&&&unsigned&short&&//引用次数&&
&&&&uint8_t&&&&&&&&&&&&&
&&&&uint8_t&&&&&&&&&it_&&&&
&&&&uint8_t&&&&&&&&&slabs_//标记item属于哪个slabclass下&&
&&&&uint8_t&&&&&&&&&&&&&&&&//key的长度&&
&&&&union&{&&
&&&&&&&&uint64_t&&&
&&&&&&&&char&&&
&&&&}&data[];//真实的数据信息&&
何时分配新的slab? 1 bigger item； 2 no free chunk；
If the new item is bigger than the size
of any existing blocks, then a new slab is created, divided up into
blocks of a suitable size. If an existing slab with the right block size
already exists, but there are no free blocks, a new slab is created.&
内存页一旦被分配给slab，在memcache生命周期内不再更改，在内存总量确定的情形下，其它slab可能出现饿死现象；
为此1.4.11引入slab automove
algorithm is slow and conservative. If a slab class is seen as having
the highest eviction count 3 times 10 seconds apart, it will take a page
from a slab class which has had zero evictions in the last 30 seconds
and move the memory.
若某个slab在10秒内出现3次eviction，则从过去30秒内没有出现eviction的slab里挪取一个内存页使用；
分为手工分配和自动分配：
手工： &-o slab_reassign；在mc运行时输入echo "slabs reassign 1 4" | nc localhost 11211
自动： -o slab_reassign, slab_automove；mc每10秒进行一次重分配，手工暂停echo &"slabs automove 0" | nc localhost 11211
typedef&struct&{ &
& & unsigned&int&&&&&&&&&&&/*&每个item大小,&sizes&of&items&*/&&
& & unsigned&int&&&&&&&&/*&每个page中包含多少个item&,&how&many&items&per&slab&*/&&
& &&void&**&&&&&&&&&&&&&&&/*&空闲的item指针,&list&of&item&ptrs&*/&&
& & unsigned&int&sl_&&&&&&/*&以分配空闲的item&个数,&size&of&previous&array&*/&&
& & unsigned&int&sl_&&&&&&&/*&当前空闲的item位置(也就是实际空闲item个数)，从后往前的，&first&free&slot&*/&&
& &&void&*end_page_&&&&&&&&&/*&指向最后一个页面中空闲的item开始位置,&pointer&to&next&free&item&at&end&of&page,&or&0&*/&&
& & unsigned&int&end_page_&/*&最后一个页面，item个数,&number&of&items&remaining&at&end&of&last&alloced&page&*/&&
& & unsigned&int&&&&&&&&&&/*&实际使用slab(page)个数&how&many&slabs&were&allocated&for&this&class&*/&&
& &&void&**slab_&&&&&&&&&&&/*&所有page的指针,&array&of&slab&pointers&*/&&
& & unsigned&int&list_&&&&&/*&已经分配page指针个数，size&of&prev&array&*/&&
& & unsigned&int&&&&&&&&/*&index+1&of&dying&slab,&or&zero&if&none&*/&&
& &&size_t&&&&&&&&&&&&/*&所有被使用了的内存的大小,&The&number&of&requested&bytes&*/&&
}&slabclass_t; &
图片来源&&&
LRU和expired item
memcache并不会监视和清理过期数据，而是在客户端get时检查，称为lazy expiration。
item被检测到超时并不会被删除，而是放入slab-&slots头部；
do_item_get --
& &--判断该item是否过期
& &do_item_unlink(it,&hv);//将item从hashtable和LRU链中移除&&&&&&&&&&&&&
& &do_item_remove(it);//删除item&
do_item_remove
& item_free(it);//释放item&&
& & slabs_free(it,&ntotal,&clsid);//slabclass结构执行释放&
& & & & & &do_slabs_free(ptr,&size,&id);//执行释放&
以下是do_slabs_free的代码，将expired item放入slab-&slots的头部 &&&&&&
& & it&=&(item&*) &
& & it-&it_flags&|=&ITEM_SLABBED;//修改item的状态标识，修改为空闲&&
& & it-&prev&=&0;//断开数据链表&&
& & it-&next&=&p-& &
& &&if&(it-&next)&it-&next-&prev&=& &
& & p-&slots&=&&
问：expired item何时被重用？
1 slab在新加item时会先查看LRU队尾；
2 如果队尾的item恰巧超时则重用，否则执行slabs_alloc；这一过程循环5次，若还没有找到可用item，则再次调用slabs_alloc；
3&slabs_alloc依次尝试 &a slab-&slot即expired item链表； &b slab-&end_page_ptr 最后一个页面的空闲item； c 分配新的内存页
也就是说，只有LRU最后的5个元素状态为expired时，才有机会直接重用LRU，否则会依次尝试expired item list和slab的最后一个内存页的free item；
以下是代码实现
当客户端执行add操作，即往slab添加item时，调用do_item_alloc；
do_item_alloc
& & mutex_lock(&cache_lock);//执行LRU锁&存储时，会尝试从LRU中选择合适的空间的空间&&
& &&int&tries&=&5;//如果LRU中尝试5次还没合适的空间，则执行申请空间的操作&
&&&&search&=&tails[id];//第id个LRU表的尾部&
& & /* We walk up *only* for locked items. Never searching for expired
&&&&for&(;&tries&&&0&&&&search&!=&NULL;&tries--,&search=search-&prev)&{
&&&&&&&&uint32_t&hv&=&hash(ITEM_key(search),&search-&nkey,&0);//获取分段锁&
& & & &&if&((search-&exptime&!=&0&&&&search-&exptime&&&current_time) &||&(search-&time&&=&oldest_live&&&&oldest_live&&=&current_time))&{&//过期时间的判断&&
&&&&&&&&&&&&it&=&&
& & & & }&else&if&((it&=&slabs_alloc(ntotal,&id))&==&NULL)&{//申请合适的slabclass&&
& & & & & ......
& & & & }&
&&&&&&&&break;&&
& &&if&(!tried_alloc&&&&(tries&==&0&||&search&==&NULL))//5次循环查找，未找到合适的空间&&
& & & & it&=&slabs_alloc(ntotal,&id);//则从内存池申请新的空间&
& &&return& &
注：每次新分配item时，先进行5次循环：检查LRU尾部item是否过期，过期则重用，否则尝试slabs_alloc申请新内存； &若5次后仍未获取可用内存，则再次尝试slabs_alloc申请内存；
slabs_alloc
& & & &pthread_mutex_lock(&slabs_lock);
& & ret =&do_slabs_alloc(size, id);
& & pthread_mutex_unlock(&slabs_lock);
do_slabs_alloc(const&size_t&size,&unsigned&int&id)
& & p&=&&slabclass[id]; &
& &&/*&fail&unless&we&have&space&at&the&end&of&a&recently&allocated&page,&we&have&something&on&our&freelist,&or&we&could&allocate&a&new&page&*/&&
& &&//&1&最后面的页面有空间&2&空闲的地方有空间&3&分配一个新的页面&&
& &&if&(!&(p-&end_page_ptr&!=&0&||&p-&sl_curr&!=&0&||&&do_slabs_newslab(id)&!=&0))&{ &
& & & &&/*&We&don't&have&more&memory&available&*/&&
& & & & ret&=&NULL; &
& & }&else&if&(p-&sl_curr&!=&0)&{ &
& & & &&/*&return&off&our&freelist&*/&&
& & & &&//从空闲(回收)地方分配&&
& & & & ret&=&p-&slots[--p-&sl_curr]; &
& & }&else&{ &
& & & &&/*&if&we&recently&allocated&a&whole&page,&return&from&that&*/&&
& & & & assert(p-&end_page_ptr&!=&NULL); &
& & & & ret&=&p-&end_page_ &
& & & &&if&(--p-&end_page_free&!=&0)&{ &
& & & & & & p-&end_page_ptr&=&((caddr_t)p-&end_page_ptr)&+&p-& &
& & & & }&else&{ &
& & & & & & p-&end_page_ptr&=&0; &
& & & & } &
& &&if&(ret)&{ &
& & & & p-&requested&+=& &
& & & & MEMCACHED_SLABS_ALLOCATE(size,&id,&p-&size,&ret); &
& & }&else&{ &
& & & & MEMCACHED_SLABS_ALLOCATE_FAILED(size,&id); &
& &&return& &
do_slabs_newslab--即为该slab新分配一个数据页；
&&&&int&len&=&p-&size&*&p-&&
& & memory_allocate((size_t)len))
Views(...) Comments()}