[转载]memcache源码分析之items – 先贝夜话 – 博客园.
items是memcache用来管理item的封装,采用的hash表和LRU链的形式,关于hash表的操作见我前几天的文章 memcache源码分析之assoc
关于item内容的存储机制简介
item的内容存储是在slab中管理的,为了对内存进行有效的管理,slab采用的是分桶的大小来存储item的内容的,简单举例解释一下,初始化时会有不同块大小的桶,比如桶1里面的
内存块都是80b的,专门用来存储item内容大小接近80b的。桶2的内存块是100b的,专门用来存储内容大小接近100b的item,桶3是 120b的,用来存储大小接近120b的item,等等。所以,如果有一个item的内容大小是90b,那它只能存储在100b的桶内,不能存储在其他里 面的,120b的也不可以。具体详细介绍请见我后续关于slab的文章。
问题:当100b的桶存储满的时候,memcache怎么办呢?
这个问题的答案就在本文介绍的内容里面。
为一个item分配存储空间的时候,具体的操作是这样的:
1、首先,计算该item占用的空间大小,只有知道了它的大小,才能知道它需要存储在哪个桶中。一个item的大小包括它的item结构体大小 部分、名字长度部分、状态标识部分、内容大小部分等的总和。具体计算方法请看下面的代码分析中 item_make_header 函数。
2、然后寻找合适的slab用于存储,这一部分主要是比较item 和各slab桶的大小,寻找最合适的slab,此部分代码是文件 slabs.c 中的 slabs_clsid 函数,具体内容我后续关于slab的文章会详细分析。
3、从对应slab的tail队列中寻找是否存在过期的item,如果有,清除掉,此处操作最多尝试50次。
4、如果第3步操作失败,并且在对应slab中分配空间失败,那么从slab对应的tail队列中删除没有被引用的item,且最多也是尝试50次。
5、尝试从slab中分配空间。
6、如果第5步失败,会从slab对应的tail队列中删除3个小时(默认)之前的正在引用的item。
7、然后尝试从slab中分配空间。如果失败,返回NULL,成功则会设置item对应的一些信息,返回成功标识。
item的删除过程:
1、设置已被删除状态。并从hash表中删除,次部分代码调用的是 memcache源码分析之assoc 中介绍到的函数assoc_delete
2、从LRU链中删除。函数item_unlink_q。
3、如果要清除item占用的资源,则调用函数do_item_remove和item_free,释放占用内存空间。
另外还提供了一些其他操作,分别包括,获取某个item(会判断是否过期),获取某个item(不判断是否过期),客户端通过flush_all操作清空所有过期item,item的新值替换,访问时间更新等。
当然,有item的删除操作,就要有相应的加入hash表和LRU链的操作。
另外,还提供了一些item和slab状态函数。
想了解详细代码的同学可以看一下下面的简要分析。有错误之处请指正。
items.h
02 |
uint64_t get_cas_id( void ); |
05 |
item *do_item_alloc( char *key, const size_t nkey, const int flags, const rel_time_t exptime, const int nbytes); |
06 |
void item_free(item *it); |
07 |
bool item_size_ok( const size_t nkey, const int flags, const int nbytes); |
09 |
int do_item_link(item *it); |
10 |
void do_item_unlink(item *it); |
11 |
void do_item_remove(item *it); |
12 |
void do_item_update(item *it); |
13 |
int do_item_replace(item *it, item *new_it); |
16 |
char *do_item_cachedump( const unsigned int slabs_clsid, const unsigned int limit, unsigned int *bytes); |
17 |
void do_item_stats(ADD_STAT add_stats, void *c); |
19 |
void do_item_stats_sizes(ADD_STAT add_stats, void *c); |
20 |
void do_item_flush_expired( void ); |
22 |
item *do_item_get( const char *key, const size_t nkey); |
23 |
item *do_item_get_nocheck( const char *key, const size_t nkey); |
24 |
void item_stats_reset( void ); |
25 |
extern pthread_mutex_t cache_lock; |
items.c
002 |
#include "memcached.h" |
003 |
#include <sys/stat.h> |
004 |
#include <sys/socket.h> |
005 |
#include <sys/signal.h> |
006 |
#include <sys/resource.h> |
008 |
#include <netinet/in.h> |
017 |
static void item_link_q(item *it); |
018 |
static void item_unlink_q(item *it); |
025 |
#define ITEM_UPDATE_INTERVAL 60 |
027 |
#define LARGEST_ID POWER_LARGEST |
031 |
unsigned int evicted; |
032 |
unsigned int evicted_nonzero; |
033 |
rel_time_t evicted_time; |
034 |
unsigned int reclaimed; |
035 |
unsigned int outofmemory; |
036 |
unsigned int tailrepairs; |
039 |
static item *heads[LARGEST_ID]; |
040 |
static item *tails[LARGEST_ID]; |
041 |
static itemstats_t itemstats[LARGEST_ID]; |
042 |
static unsigned int sizes[LARGEST_ID]; |
044 |
void item_stats_reset( void ) { |
045 |
pthread_mutex_lock(&cache_lock); |
046 |
memset (itemstats, 0, sizeof (itemstats)); |
047 |
pthread_mutex_unlock(&cache_lock); |
052 |
uint64_t get_cas_id( void ) { |
053 |
static uint64_t cas_id = 0; |
059 |
# define Debug_REFCNT(it,op) \ |
060 |
fprintf (stderr, "item %x refcnt(%c) %d %c%c%c\n" , \ |
061 |
it, op, it->refcount, \ |
062 |
(it->it_flags & ITEM_LINKED) ? 'L' : ' ' , \ |
063 |
(it->it_flags & ITEM_SLABBED) ? 'S' : ' ' ) |
065 |
# define Debug_REFCNT(it,op) while(0) |
081 |
static size_t item_make_header( const uint8_t nkey, const int flags, const int nbytes, char *suffix, uint8_t *nsuffix) { |
083 |
*nsuffix = (uint8_t) snprintf(suffix, 40, " %d %d\r\n" , flags, nbytes - 2); |
084 |
return sizeof (item) + nkey + *nsuffix + nbytes; |
089 |
item *do_item_alloc( char *key, const size_t nkey, const int flags, const rel_time_t exptime, const int nbytes) { |
093 |
size_t ntotal = item_make_header(nkey + 1, flags, nbytes, suffix, &nsuffix); |
094 |
if (settings.use_cas) { |
095 |
ntotal += sizeof (uint64_t); |
098 |
unsigned int id = slabs_clsid(ntotal); |
106 |
for (search = tails[id];tries > 0 && search != NULL;tries--, search=search->prev) { |
107 |
if (search->refcount == 0 && (search->exptime != 0 && search->exptime < current_time)) { |
115 |
itemstats[id].reclaimed++; |
125 |
if (it == NULL && (it = slabs_alloc(ntotal, id)) == NULL) { |
133 |
if (settings.evict_to_free == 0) { |
134 |
itemstats[id].outofmemory++; |
145 |
if (tails[id] == 0) { |
146 |
itemstats[id].outofmemory++; |
150 |
for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) { |
151 |
if (search->refcount == 0) { |
152 |
if (search->exptime == 0 || search->exptime > current_time) { |
153 |
itemstats[id].evicted++; |
154 |
itemstats[id].evicted_time = current_time - search-> time ; |
155 |
if (search->exptime != 0) |
156 |
itemstats[id].evicted_nonzero++; |
161 |
itemstats[id].reclaimed++; |
166 |
do_item_unlink(search); |
170 |
it = slabs_alloc(ntotal, id); |
172 |
itemstats[id].outofmemory++; |
181 |
for (search = tails[id]; tries > 0 && search != NULL; tries--, search=search->prev) { |
182 |
if (search->refcount != 0 && search-> time + TAIL_REPAIR_TIME < current_time) { |
183 |
itemstats[id].tailrepairs++; |
184 |
search->refcount = 0; |
185 |
do_item_unlink(search); |
189 |
it = slabs_alloc(ntotal, id); |
196 |
assert (it->slabs_clsid == 0); |
198 |
it->slabs_clsid = id; |
200 |
assert (it != heads[it->slabs_clsid]); |
202 |
it->next = it->prev = it->h_next = 0; |
204 |
DEBUG_REFCNT(it, '*' ); |
205 |
it->it_flags = settings.use_cas ? ITEM_CAS : 0; |
208 |
memcpy (ITEM_key(it), key, nkey); |
209 |
it->exptime = exptime; |
210 |
memcpy (ITEM_suffix(it), suffix, ( size_t )nsuffix); |
211 |
it->nsuffix = nsuffix; |
217 |
void item_free(item *it) { |
218 |
size_t ntotal = ITEM_ntotal(it); |
220 |
assert ((it->it_flags & ITEM_LINKED) == 0); |
221 |
assert (it != heads[it->slabs_clsid]); |
222 |
assert (it != tails[it->slabs_clsid]); |
223 |
assert (it->refcount == 0); |
226 |
clsid = it->slabs_clsid; |
228 |
it->it_flags |= ITEM_SLABBED; |
229 |
DEBUG_REFCNT(it, 'F' ); |
230 |
slabs_free(it, ntotal, clsid); |
235 |
bool item_size_ok( const size_t nkey, const int flags, const int nbytes) { |
239 |
return slabs_clsid(item_make_header(nkey + 1, flags, nbytes,prefix, &nsuffix)) != 0; |
244 |
static void item_link_q(item *it) { |
246 |
assert (it->slabs_clsid < LARGEST_ID); |
247 |
assert ((it->it_flags & ITEM_SLABBED) == 0); |
249 |
head = &heads[it->slabs_clsid]; |
250 |
tail = &tails[it->slabs_clsid]; |
252 |
assert ((*head && *tail) || (*head == 0 && *tail == 0)); |
255 |
if (it->next) it->next->prev = it; |
257 |
if (*tail == 0) *tail = it; |
258 |
sizes[it->slabs_clsid]++; |
264 |
static void item_unlink_q(item *it) { |
266 |
assert (it->slabs_clsid < LARGEST_ID); |
267 |
head = &heads[it->slabs_clsid]; |
268 |
tail = &tails[it->slabs_clsid]; |
271 |
assert (it->prev == 0); |
275 |
assert (it->next == 0); |
278 |
assert (it->next != it); |
279 |
assert (it->prev != it); |
281 |
if (it->next) it->next->prev = it->prev; |
282 |
if (it->prev) it->prev->next = it->next; |
283 |
sizes[it->slabs_clsid]--; |
289 |
int do_item_link(item *it) { |
290 |
MEMCACHED_ITEM_LINK(ITEM_key(it), it->nkey, it->nbytes); |
291 |
assert ((it->it_flags & (ITEM_LINKED|ITEM_SLABBED)) == 0); |
292 |
it->it_flags |= ITEM_LINKED; |
293 |
it-> time = current_time; |
297 |
stats.curr_bytes += ITEM_ntotal(it); |
298 |
stats.curr_items += 1; |
299 |
stats.total_items += 1; |
303 |
ITEM_set_cas(it, (settings.use_cas) ? get_cas_id() : 0); |
312 |
void do_item_unlink(item *it) { |
313 |
MEMCACHED_ITEM_UNLINK(ITEM_key(it), it->nkey, it->nbytes); |
314 |
if ((it->it_flags & ITEM_LINKED) != 0) { |
315 |
it->it_flags &= ~ITEM_LINKED; |
317 |
stats.curr_bytes -= ITEM_ntotal(it); |
318 |
stats.curr_items -= 1; |
320 |
assoc_delete(ITEM_key(it), it->nkey); |
322 |
if (it->refcount == 0) item_free(it); |
328 |
void do_item_remove(item *it) { |
329 |
MEMCACHED_ITEM_REMOVE(ITEM_key(it), it->nkey, it->nbytes); |
330 |
assert ((it->it_flags & ITEM_SLABBED) == 0); |
331 |
if (it->refcount != 0) { |
333 |
DEBUG_REFCNT(it, '-' ); |
335 |
if (it->refcount == 0 && (it->it_flags & ITEM_LINKED) == 0) { |
342 |
void do_item_update(item *it) { |
343 |
MEMCACHED_ITEM_UPDATE(ITEM_key(it), it->nkey, it->nbytes); |
344 |
if (it-> time < current_time - ITEM_UPDATE_INTERVAL) { |
345 |
assert ((it->it_flags & ITEM_SLABBED) == 0); |
347 |
if ((it->it_flags & ITEM_LINKED) != 0) { |
349 |
it-> time = current_time; |
357 |
int do_item_replace(item *it, item *new_it) { |
358 |
MEMCACHED_ITEM_REPLACE(ITEM_key(it), it->nkey, it->nbytes,ITEM_key(new_it), new_it->nkey, new_it->nbytes); |
359 |
assert ((it->it_flags & ITEM_SLABBED) == 0); |
362 |
return do_item_link(new_it); |
367 |
char *do_item_cachedump( const unsigned int slabs_clsid, const unsigned int limit, unsigned int *bytes) { |
368 |
unsigned int memlimit = 2 * 1024 * 1024; |
370 |
unsigned int bufcurr; |
373 |
unsigned int shown = 0; |
374 |
char key_temp[KEY_MAX_LENGTH + 1]; |
377 |
it = heads[slabs_clsid]; |
379 |
buffer = malloc (( size_t )memlimit); |
380 |
if (buffer == 0) return NULL; |
383 |
while (it != NULL && (limit == 0 || shown < limit)) { |
384 |
assert (it->nkey <= KEY_MAX_LENGTH); |
386 |
strncpy (key_temp, ITEM_key(it), it->nkey); |
387 |
key_temp[it->nkey] = 0x00; |
388 |
len = snprintf(temp, sizeof (temp), "ITEM %s [%d b; %lu s]\r\n" ,key_temp, it->nbytes - 2,(unsigned long )it->exptime + process_started); |
389 |
if (bufcurr + len + 6 > memlimit) |
391 |
memcpy (buffer + bufcurr, temp, len); |
397 |
memcpy (buffer + bufcurr, "END\r\n" , 6); |
406 |
void do_item_stats(ADD_STAT add_stats, void *c) { |
408 |
for (i = 0; i < LARGEST_ID; i++) { |
409 |
if (tails[i] != NULL) { |
410 |
const char *fmt = "items:%d:%s" ; |
411 |
char key_str[STAT_KEY_LEN]; |
412 |
char val_str[STAT_VAL_LEN]; |
413 |
int klen = 0, vlen = 0; |
415 |
APPEND_NUM_FMT_STAT(fmt, i, "number" , "%u" , sizes[i]); |
417 |
APPEND_NUM_FMT_STAT(fmt, i, "age" , "%u" , tails[i]-> time ); |
419 |
APPEND_NUM_FMT_STAT(fmt, i, "evicted" , "%u" , itemstats[i].evicted); |
421 |
APPEND_NUM_FMT_STAT(fmt, i, "evicted_nonzero" , "%u" , itemstats[i].evicted_nonzero); |
423 |
APPEND_NUM_FMT_STAT(fmt, i, "evicted_time" , "%u" , itemstats[i].evicted_time); |
425 |
APPEND_NUM_FMT_STAT(fmt, i, "outofmemory" , "%u" , itemstats[i].outofmemory); |
427 |
APPEND_NUM_FMT_STAT(fmt, i, "tailrepairs" , "%u" , itemstats[i].tailrepairs);; |
429 |
APPEND_NUM_FMT_STAT(fmt, i, "reclaimed" , "%u" , itemstats[i].reclaimed);; |
434 |
add_stats(NULL, 0, NULL, 0, c); |
440 |
void do_item_stats_sizes(ADD_STAT add_stats, void *c) { |
443 |
const int num_buckets = 32768; |
444 |
unsigned int *histogram = calloc (num_buckets, sizeof ( int )); |
446 |
if (histogram != NULL) { |
450 |
for (i = 0; i < LARGEST_ID; i++) { |
451 |
item *iter = heads[i]; |
453 |
int ntotal = ITEM_ntotal(iter); |
454 |
int bucket = ntotal / 32; |
455 |
if ((ntotal % 32) != 0) bucket++; |
456 |
if (bucket < num_buckets) histogram[bucket]++; |
462 |
for (i = 0; i < num_buckets; i++) { |
463 |
if (histogram[i] != 0) { |
466 |
klen = snprintf(key, sizeof (key), "%d" , i * 32); |
467 |
assert (klen < sizeof (key)); |
468 |
APPEND_STAT(key, "%u" , histogram[i]); |
473 |
add_stats(NULL, 0, NULL, 0, c); |
478 |
item *do_item_get( const char *key, const size_t nkey) { |
479 |
item *it = assoc_find(key, nkey); |
482 |
if (settings.verbose > 2) { |
484 |
fprintf (stderr, "> NOT FOUND %s" , key); |
486 |
fprintf (stderr, "> FOUND KEY %s" , ITEM_key(it)); |
492 |
if (it != NULL && settings.oldest_live != 0 && settings.oldest_live <= current_time && it-> time <= settings.oldest_live) { |
497 |
if (it == NULL && was_found) { |
498 |
fprintf (stderr, " -nuked by flush" ); |
502 |
if (it != NULL && it->exptime != 0 && it->exptime <= current_time) { |
507 |
if (it == NULL && was_found) { |
508 |
fprintf (stderr, " -nuked by expire" ); |
514 |
DEBUG_REFCNT(it, '+' ); |
517 |
if (settings.verbose > 2) |
518 |
fprintf (stderr, "\n" ); |
525 |
item *do_item_get_nocheck( const char *key, const size_t nkey) { |
526 |
item *it = assoc_find(key, nkey); |
529 |
DEBUG_REFCNT(it, '+' ); |
536 |
void do_item_flush_expired( void ) { |
539 |
if (settings.oldest_live == 0) |
541 |
for (i = 0; i < LARGEST_ID; i++) { |
547 |
for (iter = heads[i]; iter != NULL; iter = next) { |
548 |
if (iter-> time >= settings.oldest_live) { |
550 |
if ((iter->it_flags & ITEM_SLABBED) == 0) { |
551 |
do_item_unlink(iter); |