Memcached源码分析之内存管理篇
使用命令 set(key, value) 向 memcached 插入一条数据, memcached 内部是如何组织数据呢一 把数据组装成 item
memcached 接受到客户端的数据后, 把数据组装成 item, item 的格式如下:
图1 struct item 的结构
源码中这样定义 struct item:
C代码收藏代码
/**
* Structure for storing items within memcached.
*/
typedef struct _stritem {
struct _stritem *next;
struct _stritem *prev;
struct _stritem *h_next; /* hash chain next */
>
>
int nbytes; /*> unsigned shortrefcount;
uint8_t nsuffix; /* length of flags-and-length string */
uint8_t it_flags; /* ITEM_* above */
uint8_t slabs_clsid;/* which slab> uint8_t nkey; /* key length, w/terminating null and padding */
/* this odd type prevents type-punning issues when we do
* the little shuffle to save space when not using CAS. */
union {
uint64_t cas;
char end;
} data[];
/* if it_flags & ITEM_CAS we have 8 bytes CAS */
/* then null-terminated key */
/* then " flags length\r\n" (no terminating null) */
/* then data with terminating \r\n (no terminating null; it's binary!) */
} item;
从源码可以得出 item 的结构分两部分, 第一部分定义 item 结构的属性, 包括连接其它 item 的指针 (next, prev),
还有最近访问时间(time), 过期的时间(exptime), 以及数据部分的大小, 标志位, key的长度, 引用次数, 以及 item 是
从哪个 slabclass 分配而来.
item 结构体的定义使用了一个常用的技巧: 定义空数组 data, 用来指向 item 数据部分的首地址, 使用空数组的
好处是 data 指针本身不占用任何存储空间, 为 item 分配存储空间后, data 自然而然就指向数据部分的首地址.
第二部分是 item 的数据, 由 CAS, key, suffix, value 组成.
二 为 item 分配存储空间
把数据组装成 item 之前, 必须为 item 分配存储空间, memcached 不是直接从操作系统分配内存的, memcached
内部使用了类似内存池的东西, 即slab机制, 来管理内存. 内存的分配和回收都交给 slab 子系统实现. 所以我们先理解
slab, 再回过头来看如何为 item 分配存储空间.
三 使用 slab 管理内存
memcached 中, 内存的分配和回收, 都是通过 slab 实现的, slab机制相当于内存池机制, 实现从操作系统分配一大块
内存, 然后 memcached 自己管理这块内存, 负责分配与回收. 接下来我们详细剖析 slab 机制.
3.1 关于 slabclass
像一般的内存池一样,从操作系统分配到一大块内存后, 为了方便管理, 把这大块内存划分为各种大小的 chunk,
chunk的大小按照一定比例逐渐递增, 如下图所示:
图2: 各个 slabclass 的 chunk> 从 slab 分配内存的时候, 根据请求内存块的大小, 找到大小最合适的 chunk 所在的 slabclass, 然后从这个
slabclass 找空闲的 chunk 分配出去. 所谓最合适就是指 chunk 的大小能够满足要求, 而且碎片最小.
如下图所示:
图3 寻找最合适的 slabclass
这种分配方式的缺点是存在内存碎片, 例如, 将 100字节的 item 存储到一个 128 字节的 chunk, 就有 28 字节
的内存浪费, 如下图所示:
图5 内存碎片
3.2 slabclass 的内部实现
slabclass 是由 chunk> 一些内存, 初始时, 系统为每个 slabclass 分配一个 slab, 一个 slab 就是一个内存块,其大小等于 1M.然后每个
slabclass 再把 slab 切分成一个个 chunk, 算一下, 一个 slab 可以切分得到 1M/chunk_size 个chunk.
先来看一下源码中 slabclass 的定义:
C代码收藏代码
typedef struct {
unsigned int> unsigned int perslab; /* how many items per slab */
void *slots; /* list of item ptrs */
unsigned int sl_curr; /* total free items in list */
void *end_page_ptr; /* pointer to next free item at end of page, or 0 */
unsigned int end_page_free; /* number of items remaining at end of last alloced page */
unsigned int slabs; /* how many slabs were allocated for this> void **slab_list; /* array of slab pointers */
unsigned int list_size; /*> unsigned int killing;/* index+1 of dying slab, or zero if none */
> } slabclass_t;
slabclass 的结构图如下所示:
图6 slabclass 结构图
结合 slabclass 的结构图, 我们说明一下 slabclass 结构体的各个属性:
(1)> size 定义该 slabclass 的 chunk 大小, perslab 表示每个 slab 可以切分成多少个 chunk, 如果一个 slab 等于
1M, 那么就有 perslab = 1M /> (2) slots 和 sl_curr
slots 是回收的 item 链表, 从某个 slabclass 分配出去一个 item, 当 item 回收的时候,
不是把这 item 使用的内存交还给 slab, 而是让这个 item 挂在 slots 链表的尾部. sl_curr 表示当前链表中
有多少个回收而来的空闲 item.
(3) slab_list 和 list_size
前面说过, 初始时, memcached 为每个 slabclass 分配一个 slab, 当这个 slab 内存块使用完后, memcached
就分配一个新的 slab, 所以 slabclass 可以拥有多个 slab, 这些 slab 就是通过 slab_list 数组来管理的, list_size
表示当前 slabclass 有多少个 slab.
(4) end_page_ptr 和 end_page_free
在 subclass 内, 只有最后一个 slab 存在空闲的内存, 其它 slab 的 chunk 都分配出去了, end_page_ptr
指向最后一个 slab 中的空闲内存块, end_page_free 表示最后一个 slab 中还剩下多少个空闲 chunk.图6
中绿色部分的 chunk 表示空闲 chunk
(5) static item *heads;
static item *tails;
当 memcached 没有足够的内存使用时, 必须选择性地回收一些 item, 回收采用 LRU 算法, 这就需要维护
一个按照最近访问时间排序的 LRU 队列. 在 memcached 中,
每个 slabclass 维护一个链表, 比如 slabclass 的链表头指针为 heads, 尾指针为 tails,
已分配出去的 item 都存储在链表中. 而且链表中 item 按照最近访问时间排序, 这样一些链表相当于
LRU 队列.
四 源码分析
4.1 do_slabs_newslab
前面说过每个 slabclass 都拥有一些 slab, 当所有 slab 都用完时, memcached 会给它分配一个新的 slab,
do_slabs_newslab 就是做这个工作的.
C代码收藏代码
static int do_slabs_newslab(const unsigned int> slabclass_t *p = &slabclass;
int len = settings.slab_reassign ? settings.item_size_max
: p->size * p->perslab;
char *ptr;
if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0) ||
(grow_slab_list(id) == 0) ||
((ptr = memory_allocate((size_t)len)) == 0)) {
MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
return 0;
}
memset(ptr, 0, (size_t)len);
p->end_page_ptr = ptr;
p->end_page_free = p->perslab;
p->slab_list = ptr;
mem_malloced += len;
MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);
return 1;
}
分配一个新的 slab, 必须把该 slab 的首地址安插在 slab_list 数组中, 所以先调用 grow_slab_list 来确保 slab_list
数组有足够的容量, 如果容量不足, grow_slab_list 会对 slab_list 扩容.
然后调用 memory_allocate 分配 1M 的内存空间, memory_allocate 从预先分配的内存取下 1M 大小的
空闲内存块,作为新的 slab.
最后调整 end_page_ptr, 新分配的 slab 全部都是空闲内存块, 所以 end_page_ptr 指向新 slab 的首地址.
这个新 slab 的首地址也被安插在 slab_list 数组中.
4.2 do_slabs_alloc
这个函数从指定的 slabclass, 即 slabclass, 分配大小为> 分配的原则是, 优先从 slots 指向的空闲链表中分配, 空闲链表没有, 才从 slab 中分配一个空闲的 chunk.
C代码收藏代码
static void *do_slabs_alloc(const> slabclass_t *p;
void *ret = NULL;
item *it = NULL;
if (id < POWER_SMALLEST ||> MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);
return NULL;
}
p = &slabclass;
assert(p->sl_curr == 0 || ((item *)p->slots)->slabs_clsid == 0);
/* 如果不使用 slab 机制, 则直接从操作系统分配 */
#ifdef USE_SYSTEM_MALLOC
if (mem_limit && mem_malloced +>
MEMCACHED_SLABS_ALLOCATE_FAILED(size,> return 0;
}
mem_malloced +=> ret = malloc(size);
MEMCACHED_SLABS_ALLOCATE(size,> return ret;
#endif
/* 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 */
/* 确保最后一个slab 有空闲的chunk */
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) {
/* 从空闲list分配一个item */
/* return off our freelist */
it = (item *)p->slots;
p->slots = it->next;
if (it->next) it->next->prev = 0;
p->sl_curr--;
ret = (void *)it;
} else {
/* 从最后一个slab中分配一个空闲chunk */
/* if we recently allocated a whole page, return from that */
assert(p->end_page_ptr != NULL);
ret = p->end_page_ptr;
if (--p->end_page_free != 0) {
p->end_page_ptr = ((caddr_t)p->end_page_ptr) + p->size;
} else {
p->end_page_ptr = 0;
}
}
if (ret) {
p->requested +=>
MEMCACHED_SLABS_ALLOCATE(size,> } else {
MEMCACHED_SLABS_ALLOCATE_FAILED(size,> }
return ret;
}
4.3 do_slabs_free
把 ptr 指向的 item 归还给 slabclass
操作很简单, 把 ptr 指向的 item 挂在 slots 空闲链表的最前面
C代码收藏代码
static void do_slabs_free(void *ptr, const> slabclass_t *p;
item *it;
assert(((item *)ptr)->slabs_clsid == 0);
assert(id >= POWER_SMALLEST &&>
if (id < POWER_SMALLEST ||> return;
MEMCACHED_SLABS_FREE(size,> p = &slabclass;
#ifdef USE_SYSTEM_MALLOC
mem_malloced -=> free(ptr);
return;
#endif
/* 把 item 归还给slots指向的空闲链表, 插在链表的最前面 */
it = (item *)ptr;
it->it_flags |= ITEM_SLABBED;
it->prev = 0;
it->next = p->slots;
if (it->next) it->next->prev = it;
p->slots = it;
p->sl_curr++;
p->requested -=> return;
}
4.4 do_item_alloc
从 slab 系统分配一个空闲 item
C代码收藏代码
item *do_item_alloc(char *key, const> uint8_t nsuffix;
item *it = NULL;
char suffix;
> if (settings.use_cas) {
ntotal +=> }
unsigned int> if (id == 0)
return 0;
mutex_lock(&cache_lock);
/* do a quick check if we have any expired items in the tail.. */
item *search;
> search = tails;
if (search != NULL && (refcount_incr(&search->refcount) == 2)) {
/* 先检查 LRU 队列最后一个 item 是否超时, 超时的话就把这个 item 分配给用户 */
if ((search->exptime != 0 && search->exptime < current_time)
|| (search->time slabs_clsid, ITEM_ntotal(it), ntotal);
/* 把这个 item 从 LRU 队列和哈希表中移除 */
do_item_unlink_nolock(it, hash(ITEM_key(it), it->nkey, 0));
/* Initialize the item block: */
it->slabs_clsid = 0;
/* 没有超时的 item, 那就尝试从 slabclass 分配, 运气不好的话, 分配失败,
那就把 LRU 队列最后一个 item 剔除, 然后分配给用户 */
} else if ((it = slabs_alloc(ntotal,> if (settings.evict_to_free == 0) {
itemstats.outofmemory++;
pthread_mutex_unlock(&cache_lock);
return NULL;
}
itemstats.evicted++;
itemstats.evicted_time = current_time - search->time;
if (search->exptime != 0)
itemstats.evicted_nonzero++;
if ((search->it_flags & ITEM_FETCHED) == 0) {
STATS_LOCK();
stats.evicted_unfetched++;
STATS_UNLOCK();
itemstats.evicted_unfetched++;
}
STATS_LOCK();
stats.evictions++;
STATS_UNLOCK();
it = search;
slabs_adjust_mem_requested(it->slabs_clsid, ITEM_ntotal(it), ntotal);
/* 把这个 item 从 LRU 队列和哈希表中移除 */
do_item_unlink_nolock(it, hash(ITEM_key(it), it->nkey, 0));
/* Initialize the item block: */
it->slabs_clsid = 0;
} else {
refcount_decr(&search->refcount);
}
/* LRU 队列是空的, 或者锁住了, 那就只能从 slabclass 分配内存 */
} else {
/* If the LRU is empty or locked, attempt to allocate memory */
it = slabs_alloc(ntotal,> if (search != NULL)
refcount_decr(&search->refcount);
}
if (it == NULL) {
itemstats.outofmemory++;
/* Last ditch effort. There was a very rare bug which caused
* refcount leaks. We leave this just in case they ever happen again.
* We can reasonably assume no item can stay locked for more than
* three hours, so if we find one in the tail which is that old,
* free it anyway.
*/
if (search != NULL &&
search->refcount != 2 &&
search->time + TAIL_REPAIR_TIME < current_time) {
itemstats.tailrepairs++;
search->refcount = 1;
do_item_unlink_nolock(search, hash(ITEM_key(search), search->nkey, 0));
}
pthread_mutex_unlock(&cache_lock);
return NULL;
}
assert(it->slabs_clsid == 0);
assert(it != heads);
/* 顺便对 item 做一些初始化 */
/* Item initialization can happen outside of the lock; the item's already
* been removed from the slab LRU.
*/
it->refcount = 1; /* the caller will have a reference */
pthread_mutex_unlock(&cache_lock);
it->next = it->prev = it->h_next = 0;
it->slabs_clsid => DEBUG_REFCNT(it, '*');
it->it_flags = settings.use_cas ? ITEM_CAS : 0;
it->nkey = nkey;
it->nbytes = nbytes;
memcpy(ITEM_key(it), key, nkey);
it->exptime = exptime;
memcpy(ITEM_suffix(it), suffix, (size_t)nsuffix);
it->nsuffix = nsuffix;
return it;
}
4.5 do_item_link
形成了一个完成的 item 后, 就要把它放入两个数据结构中, 一是 memcached 的哈希表,
memcached 运行过程中只有一个哈希表, 二是 item 所在的 slabclass 的 LRU 队列.
如 图6 所示, 每个 slabclass 都有一个 LRU 队列
C代码收藏代码
int do_item_link(item *it, const uint32_t hv) {
MEMCACHED_ITEM_LINK(ITEM_key(it), it->nkey, it->nbytes);
assert((it->it_flags & (ITEM_LINKED|ITEM_SLABBED)) == 0);
mutex_lock(&cache_lock);
it->it_flags |= ITEM_LINKED;
it->time = current_time;
STATS_LOCK();
stats.curr_bytes += ITEM_ntotal(it);
stats.curr_items += 1;
stats.total_items += 1;
STATS_UNLOCK();
/* Allocate a new CAS> ITEM_set_cas(it, (settings.use_cas) ? get_cas_id() : 0);
/* 把 item 放入哈希表 */
assoc_insert(it, hv);
/* 把 item 放入 LRU 队列*/
item_link_q(it);
refcount_incr(&it->refcount);
pthread_mutex_unlock(&cache_lock);
return 1;
}
4.6 do_item_unlink
do_item_unlink 与 do_item_unlink 做的工作相反, 把 item 从哈希表和 LRU 队列中删除,
而且还释放掉 item 所占的内存 (其实只是把 item 放到空闲链表中).
C代码收藏代码
void do_item_unlink(item *it, const uint32_t hv) {
MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, it->nbytes);
mutex_lock(&cache_lock);
if ((it->it_flags & ITEM_LINKED) != 0) {
it->it_flags &= ~ITEM_LINKED;
STATS_LOCK();
stats.curr_bytes -= ITEM_ntotal(it);
stats.curr_items -= 1;
STATS_UNLOCK();
/* 从哈希表中删除 item */
assoc_delete(ITEM_key(it), it->nkey, hv);
/* 从 LRU 队列中删除 item */
item_unlink_q(it);
/* 释放 item 所占的内存 */
do_item_remove(it);
}
pthread_mutex_unlock(&cache_lock);
}
4.7 item_get
根据 key 找对应的 item, 为了加快查找速度, memcached 使用一个哈希表对 key 和 item 所在的内存
地址做映射. item_get 直接从哈希表中查找就可以了, 当然找到了还要检查 item 是否超时. 超时了的 item
将从哈希表和 LRU 队列中删除掉
C代码收藏代码
/** wrapper around assoc_find which does the lazy expiration logic */
item *do_item_get(const char *key, const> mutex_lock(&cache_lock);
/* 从哈希表中找 item */
item *it = assoc_find(key, nkey, hv);
if (it != NULL) {
refcount_incr(&it->refcount);
/* Optimization for slab reassignment. prevents popular items from
* jamming in busy wait. Can only do this here to satisfy lock order
* of item_lock, cache_lock, slabs_lock. */
if (slab_rebalance_signal &&
((void *)it >= slab_rebal.slab_start && (void *)it < slab_rebal.slab_end)) {
do_item_unlink_nolock(it, hv);
do_item_remove(it);
it = NULL;
}
}
pthread_mutex_unlock(&cache_lock);
int was_found = 0;
if (settings.verbose > 2) {
if (it == NULL) {
fprintf(stderr, "> NOT FOUND %s", key);
} else {
fprintf(stderr, "> FOUND KEY %s", ITEM_key(it));
was_found++;
}
}
/* 找到了, 然后检查是否超时 */
if (it != NULL) {
if (settings.oldest_live != 0 && settings.oldest_live time exptime != 0 && it->exptime it_flags |= ITEM_FETCHED;
DEBUG_REFCNT(it, '+');
}
}
if (settings.verbose > 2)
fprintf(stderr, "\n");
return it;
}
转自http://kenby.iteye.com/blog/1423989
页:
[1]