渐进式解析 memcached 源码 - 存储机制

阅读量

从某个意义上讲，资源总是有限的，衡量一个计算机处理能力的指标有很多， 根据不同的应用需要也会有不同的指标，比如3D游戏对显卡的性能有要求，Web服务器对吞吐量及响应时间有要求，而缓存服务器对存取效率着重要求， 通常CPU、内存及硬盘的读取和计算速度具有决定性的作用，在同一时刻这些资源是有限的， 正是因为有限我们才需要合理的利用他们。

我们此次就 memcached的 存储模型、hashtable、slabs 三个方面进行解析，分析其存储机制的精妙设计

首先我们引入几个概念，item、chunk、slabclass，记得很久之前看了一段很形象的描述（@特别鸣谢）：

整个 memcached存储就像 我们常用的 田字格写字本

  • 写字本有很多页，每页纸张大小一致，相当于 slabclass
  • 每页有很多个大小一致的格子，相当于 chunk
  • 每个格子都是用来写字的，写一个字或者多个字，字 就相当于 item
  • slabclass memcached 的内存管理单位，无论 扩容还是回收 都是以 slabclass 为单位的，slab机制 实际就相当于 内存池机制。memcached 启动的时候会初始化一个 slabclass数组，每个 slabclass 默认大小 1M。

  • chunk chunk内存块（也称为 slab） 跟 slabclass 一样都是实实在在的内存空间。chunk 存在的意义在于划分不同规格的内存块，以存储不同大小的数据，以免存储资源的浪费。每个 slabclass 都会进行 chunk 划分，不过不同的 slabclass 划分的 chunk 个数不同；slabclass memory(1MB) = chunk nums * perchunk memory ，比如有的 slabclass 有 chunk 2个，每个 chunk 占 0.5MB；而有的 slabclass 有 4个 chunk，那么对应每个 chunk 占 0.25MB。每个 slabclass 划分的 单位chunk大小 是线性递增的，也可以理解为 每个 slabclass 划分的 chunk 个数是线性递减的，取决于 -f 控制的 settings.factor，默认 1.25

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    [wettper@web-lovers memcached-src]$ ./memcached -u wettper -m 512 127.0.0.1 -p 11211 -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
    slab class   5: chunk size       240 perslab    4369
    slab class   6: chunk size       304 perslab    3449
    slab class   7: chunk size       384 perslab    2730
    slab class   8: chunk size       480 perslab    2184
    slab class   9: chunk size       600 perslab    1747
    slab class  10: chunk size       752 perslab    1394
    slab class  11: chunk size       944 perslab    1110
    slab class  12: chunk size      1184 perslab     885
    slab class  13: chunk size      1480 perslab     708
    slab class  14: chunk size      1856 perslab     564
    slab class  15: chunk size      2320 perslab     451
    slab class  16: chunk size      2904 perslab     361
    slab class  17: chunk size      3632 perslab     288
    slab class  18: chunk size      4544 perslab     230
    slab class  19: chunk size      5680 perslab     184
    slab class  20: chunk size      7104 perslab     147
    slab class  21: chunk size      8880 perslab     118
    slab class  22: chunk size     11104 perslab      94
    slab class  23: chunk size     13880 perslab      75
    slab class  24: chunk size     17352 perslab      60
    slab class  25: chunk size     21696 perslab      48
    slab class  26: chunk size     27120 perslab      38
    slab class  27: chunk size     33904 perslab      30
    slab class  28: chunk size     42384 perslab      24
    slab class  29: chunk size     52984 perslab      19
    slab class  30: chunk size     66232 perslab      15
    slab class  31: chunk size     82792 perslab      12
    slab class  32: chunk size    103496 perslab      10
    slab class  33: chunk size    129376 perslab       8
    slab class  34: chunk size    161720 perslab       6
    slab class  35: chunk size    202152 perslab       5
    slab class  36: chunk size    252696 perslab       4
    slab class  37: chunk size    315872 perslab       3
    slab class  38: chunk size    394840 perslab       2
    slab class  39: chunk size    524288 perslab       2
    ......

  • item memcached 的最小存储单元，主要存储 数据、key值 等等其他关系信息（后续会详细介绍）。每个 item 结构体被封装以后根据其 大小放入 对应的 chunk 中，选择规格比 item 大但是最接近的 chunk 中，虽然会 产生部分内存碎片，不过经过 chunk 机制的控制基本将 碎片控制在了可 接受范围内；而 item 存储在 同样规格的哪个 chunk 里面 则是通过 hashtable 去控制，每个 chunk 里面会存储一个 item 单向链表，至于为什么使用 hashtable，后续会详细介绍

存储模型

slabs 模型

memcached-storage1

  • 每个 slabclass 除了分割成若干个 chunk 内存块之外，还会对应一个 free list 的双向链表，slabclass 结构体的 **slot 对应这个空闲列表的头部指针；
  • 内存分配的时候如果空闲列表中有 item，则从空闲列表中取，否则会分配一个 chunk，然后切割成 N个 item 放进 free list 中；
  • item 封装完毕以后，根据大小选择 slabclass，随后检测 slabclass 中是否有 free list，如果有则从 free list 分出来一个 item 进行占位
hashtable 模型
什么是hashtable

Hash，一般翻译为 “散列”，也可以称为 “哈希”，就是把任意长度的 input 通过散列算法，变换成固定长度的 output，该输出就是散列值。这种转换是一种压缩映射，简单的说，就是 一种将任意长度的消息压缩为某一固定长度的消息摘要函数。

那么 hashtable 呢？ 众所周知，数组的特点是 寻址容易，但是插入删除都比较困难；而 链表是 插入删除十分简单，但是寻址困难。为了综合两方的优势，做出 寻址容易 而 插入删除也比较遍历的 数据结构呢，so，就有了 hashtable 哈希表，其实就是一种 “链表的数组”，具体逻辑如下：

  • 把 key 通过一个固定的 hash 算法函数（例如 hashtable(key, value)）转化成一个 固定的整型数值，然后就该 数值对 链表数组长度 求余，求余结果作为 这个key 所在数组的下标；（元素特征转换成数组下标的方法 即是 散列法，但是散列法肯定不止上述一种，常用的还有 平均散列法、斐波那契（Fibonacci）散列法 等）
  • 将 value push 至这个数组下标内存空间里的链表尾部
  • 当对 hashtable 进行查询的时候，再次对 key 进行哈希操作，求出数组下标，然后对数组下标对应的链表进行查询

memcached-storage2

关于 memcached item 的 hashtable

  • hashtable 的 table 长度是 hashsize(n) 计算出来的，n值可以自己设置（12 < n < 64），长度默认为 65536，通常够用了
  • input 的 key 值会被 hash(key, nkey) 为一个 uint32_t 的值 hv
  • 通过 hv 与 table长度进行 按位与计算 hv & hashmask(hashpower) ，计算出数组下标
  • 然后将 item 挂到这个数组下标下，对应 item->h_next

源码解析

由于有些方法里的代码量比较大，我们这里按照 典型的代码片段进行解析，同志们可以根据文章提示的代码位置 和 代码里面的关键词 在源码中搜素，可能数据结构一些元素 看不太懂什么意思，没关系，先混个脸熟，后面看完回头再看过来就明白了

常用数据结构

item 为 memcached 中最小的数据存储单位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/* memcached.h: line 450 */
typedef struct _stritem {
    /* Protected by LRU locks */
    // 指向链表下一个 item 的指针，一般用于 LRU 和 freelist
    struct _stritem *next;
    // 指向链表上一个 item 的指针，一般用于 LRU 和 freelist
    struct _stritem *prev;
    /* Rest are protected by an item lock */
    // h_next 指针，用于 hashtable 寻址，也用于哈希表的冲突链
    struct _stritem *h_next;    /* hash chain next */
    // 最后一次访问时间，绝对时间，LRU 队列里面的 item 是根据 time 降序的，而且当执行 flush 的时候，需要用这个时间跟 执行flush命令时候的时间进行对比，判断是否失效
    rel_time_t      time;       /* least recent access */
    // 过期失效时间，绝对时间，设置为 0 为永不失效，但是在 item 不够的时候 LRU机制可能把一些 永不失效的也 free掉
    rel_time_t      exptime;    /* expire time */
    // item存放的数据长度，这个长度是算上 \r\n 的
    int             nbytes;     /* size of data */
    // 应用次数，用于判断该 item 是否正被其他线程或者其他逻辑使用
    unsigned short  refcount;
    // 后缀长度
    uint8_t         nsuffix;    /* length of flags-and-length string */
    // item 属性，是否使用 cas，受控于 settings.use_cas
    uint8_t         it_flags;   /* ITEM_* above */
    // item 处于哪个 slabs 上面
    uint8_t         slabs_clsid;/* which slab class we're in */
    // 键值长度，实际中为 nkey + 1
    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. */
    // 只有启用 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;

slabclass_t slabclass 数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* slabs.c: line 27 */
typedef struct {
    // 当前 slabclass 可存储最大的item大小
    unsigned int size;      /* sizes of items */
    // 每个 slabclass 可以存储的 item 个数，每个 slab 固定大小为 1MB，存储多少个 item 可以根据 size 进行计算
    unsigned int perslab;   /* how many items per slab */
    // 空闲列表 freelist 的链表头地址，freelist 是根据 item 里面的 item->next / item->prev 建立的双向链表结构 
    void *slots;           /* list of item ptrs */
    // 总共有多少个空闲item，如果 sl_curr 为0，就需要分配空间了，分配是以 1个slab为单位，随后对新 slab 进行切分，归入 freelist
    unsigned int sl_curr;   /* total free items in list */
    // 总共分配了多少个 slab
    unsigned int slabs;     /* how many slabs were allocated for this class */
    //分配的slab链表
    void **slab_list;       /* array of slab pointers */
    unsigned int list_size; /* size of prev array */
    //总共请求的的总大小bytes
    size_t requested; /* The number of requested bytes */
} slabclass_t;
// 定义一个最大长度为 200的 slabclass_t 数组
static slabclass_t slabclass[MAX_NUMBER_OF_SLAB_CLASSES];

slabs 源码

slabs_init slabclass 初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/* slabs.c: line 105 */
void slabs_init(const size_t limit, const double factor, const bool prealloc, const uint32_t *slab_sizes) {
    int i = POWER_SMALLEST - 1;
    // slab(chunk) 内存块最小值；settings.chunk_size 默认是48，意思为 最小的一个item能存储多少数据，可以在启动的时候使用 -n 进行设置，item 的大小是 item结构体本身和item数据组成
    unsigned int size = sizeof(item) + settings.chunk_size;
    
    // 用户设置或者默认的内存限制大小
    mem_limit = limit;
    // 是否预分配内存，通过 -L 控制，如果 OS 允许的话可以进行 预先分配内存，然后后续需要的内存，都从这里的内存申请，具体解释请见 http://www.web-lovers.com/memcached-source-params-init.html#%E8%AF%A6%E7%BB%86%E5%8F%82%E6%95%B0%E6%8E%A2%E7%A9%B6 的 "传入参数含义" 部分
    if (prealloc) {
        /* Allocate everything in a big chunk with malloc */
        mem_base = malloc(mem_limit);
        if (mem_base != NULL) {
            mem_current = mem_base;
            mem_avail = mem_limit;
        } else {
            fprintf(stderr, "Warning: Failed to allocate requested memory in"
                    " one large chunk.\nWill allocate in smaller chunks\n");
        }
    }
    // 初始化 slabclass 数组
    memset(slabclass, 0, sizeof(slabclass));
    // 循环初始化 slabclass，这里需要注意 slabclass数组的第一个元素并不使用，是从 1 开始
    while (++i < MAX_NUMBER_OF_SLAB_CLASSES-1) {
        // ...这点儿不太明白，主要是 内存优化方面的，预先设置 slab 的大小
        if (slab_sizes != NULL) {
            if (slab_sizes[i-1] == 0)
                break;
            size = slab_sizes[i-1];
        } else if (size >= settings.slab_chunk_size_max / factor) {
            break;
        }
        // 8字节对齐，内存对齐原则
        /* Make sure items are always n-byte aligned */
        if (size % CHUNK_ALIGN_BYTES)
            size += CHUNK_ALIGN_BYTES - (size % CHUNK_ALIGN_BYTES);
        // slab(chunk内存块) 规格，也可以理解为可以存储的最大item大小
        slabclass[i].size = size;
        // 最多可以分配多少个 item
        slabclass[i].perslab = settings.slab_page_size / slabclass[i].size;
        // slab(chunk内存块)规格按 factor因子 递增
        if (slab_sizes == NULL)
            size *= factor;
        if (settings.verbose > 1) {
            fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                    i, slabclass[i].size, slabclass[i].perslab);
        }
    }
    
    power_largest = i;
    // 最大的那个 slab 设置
    slabclass[power_largest].size = settings.slab_chunk_size_max;
    slabclass[power_largest].perslab = settings.slab_page_size / settings.slab_chunk_size_max;
    if (settings.verbose > 1) {
        fprintf(stderr, "slab class %3d: chunk size %9u perslab %7u\n",
                i, slabclass[i].size, slabclass[i].perslab);
    }
    /* for the test suite:  faking of how much we've already malloc'd */
    {
        char *t_initial_malloc = getenv("T_MEMD_INITIAL_MALLOC");
        if (t_initial_malloc) {
            mem_malloced = (size_t)atol(t_initial_malloc);
        }
    }
    if (prealloc) {
        slabs_preallocate(power_largest);
    }
}

slabs_clsid slabs检索，查询 item 应该存入哪个slabsclass

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/* slabs.c: line 90 */
unsigned int slabs_clsid(const size_t size) {
    // 从1开始
    int res = POWER_SMALLEST;
    // slabsclass 的第一个元素0 是没有的，所以等于0 或者 大于最大为失败
    if (size == 0 || size > settings.item_size_max)
        return 0;
    // 取大于size但是大小最接近的
    while (size > slabclass[res].size)
        if (res++ == power_largest)     /* won't fit in the biggest slab */
            return power_largest;
    return res;
}

do_slabs_alloc 向 slabclass 申请一个item，在调用函数之前，已经调用 slabs_clsid 函数确定本次申请是向哪个 slabclass_t 申请 item 了，参数 id 就是指明是向哪个 slabclass_t 申请item。如果该 slabclass_t 是有空闲 item，那么就从 freelist 队列分配一个，如果没有空闲item，那么就申请一个内存页并拆分至 freelist，再从新申请的页中分配一个 item 返回值为得到的item，如果没有内存了，返回NULL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
/* slabs.c: line 269 */
static void *do_slabs_alloc(const size_t size, unsigned int id, uint64_t *total_bytes,
        unsigned int flags) {
    slabclass_t *p;
    void *ret = NULL;
    item *it = NULL;
    if (id < POWER_SMALLEST || id > power_largest) {
        MEMCACHED_SLABS_ALLOCATE_FAILED(size, 0);
        return NULL;
    }
    // 获取对应slabclass
    p = &slabclass[id];
    assert(p->sl_curr == 0 || ((item *)p->slots)->slabs_clsid == 0);
    if (total_bytes != NULL) {
        *total_bytes = p->requested;
    }
    assert(size <= p->size);
    /* 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 */
    // sl_curr 为0 说明 freelist 没有空闲，则调用 do_slabs_newslab 申请一个新的内存页
    if (p->sl_curr == 0 && flags != SLABS_ALLOC_NO_NEWPAGE) {
        do_slabs_newslab(id);
    }
    // 如果申请过新的 slab，这里的 freelist 还是为空，则证明没有内存了
    if (p->sl_curr != 0) {
        /* return off our freelist */
        // **slots 指向的就是空闲列表的头指针，这里是 拿到第一个空闲的 item
        it = (item *)p->slots;
        // 剔除 freelist 里面的第一个item
        p->slots = it->next;
        if (it->next) it->next->prev = 0;
        /* Kill flag and initialize refcount here for lock safety in slab
         * mover's freeness detection. */
        it->it_flags &= ~ITEM_SLABBED;
        // 初始化引用
        it->refcount = 1;
        // 空闲列表数目 -1
        p->sl_curr--;
        ret = (void *)it;
    } else {
        ret = NULL;
    }
    if (ret) {
        // 请求量总数增加
        p->requested += size;
        MEMCACHED_SLABS_ALLOCATE(size, id, p->size, ret);
    } else {
        MEMCACHED_SLABS_ALLOCATE_FAILED(size, id);
    }
    return ret;
}

do_slabs_newslab 分配新的 slab

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/* slabs.c: line 236 */
static int do_slabs_newslab(const unsigned int id) {
    // 所属 slabclass
    slabclass_t *p = &slabclass[id];
    slabclass_t *g = &slabclass[SLAB_GLOBAL_PAGE_POOL];
    // settings.slab_reassign是否开启调节不同类型item所占的内存数。可以通过 -o slab_reassign选项禁用
    // 分配一个 slab 的长度，默认 1M，也可以通过 承载最大item * 承载个数进行计算
    int len = (settings.slab_reassign || settings.slab_chunk_size_max != settings.slab_page_size)
        ? settings.slab_page_size
        : p->size * p->perslab;
    char *ptr;
    // mem_malloced 通过环境变量进行设置，默认是0
    if ((mem_limit && mem_malloced + len > mem_limit && p->slabs > 0
         && g->slabs == 0)) {
        mem_limit_reached = true;
        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
        return 0;
    }
    // 这里是进行新的一块内存分配
    if ((grow_slab_list(id) == 0) ||
        (((ptr = get_page_from_global_pool()) == NULL) &&
        ((ptr = memory_allocate((size_t)len)) == 0))) {
        MEMCACHED_SLABS_SLABCLASS_ALLOCATE_FAILED(id);
        return 0;
    }
    memset(ptr, 0, (size_t)len);
    // 分割新的 slab，补充至 freelist空闲列表
    split_slab_page_into_freelist(ptr, id);
    // 将分配的新的内存页交给 slab_list 控制
    p->slab_list[p->slabs++] = ptr;
    MEMCACHED_SLABS_SLABCLASS_ALLOCATE(id);
    return 1;
}

split_slab_page_into_freelist 切分slab至 freelist

1
2
3
4
5
6
7
8
9
10
11
12
/* slabs.c: line 216 */
static void split_slab_page_into_freelist(char *ptr, const unsigned int id) {
    // 获取指定slab
    slabclass_t *p = &slabclass[id];
    int x;
    // 循环拆分
    for (x = 0; x < p->perslab; x++) {
        do_slabs_free(ptr, 0, id);
        ptr += p->size;
    }
}

do_slabs_free slabs_free 释放 item，这里的释放是将 item 回收至 freelist 空闲列表

1
2
3
4
5
6
7
8
/* slabs.c: line 591 */
void slabs_free(void *ptr, size_t size, unsigned int id) {
    pthread_mutex_lock(&slabs_lock);
    // ptr: item指针, size: item大小，id: slabclass位置
    do_slabs_free(ptr, size, id);
    pthread_mutex_unlock(&slabs_lock);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/* slabs.c: line 369 */
static void do_slabs_free(void *ptr, const size_t size, unsigned int id) {
    slabclass_t *p;
    item *it;
    assert(id >= POWER_SMALLEST && id <= power_largest);
    if (id < POWER_SMALLEST || id > power_largest)
        return;
    MEMCACHED_SLABS_FREE(size, id, ptr);
    p = &slabclass[id];
    it = (item *)ptr;
    if ((it->it_flags & ITEM_CHUNKED) == 0) {
#ifdef EXTSTORE
        bool is_hdr = it->it_flags & ITEM_HDR;
#endif
        // 为item的it_flags添加ITEM_SLABBED属性，标明这个item是在slab中没有被分配出去
        it->it_flags = ITEM_SLABBED;
        it->slabs_clsid = 0;
        it->prev = 0;
        // 将item 与 freelist 相互关联起来
        it->next = p->slots;
        if (it->next) it->next->prev = it;
        p->slots = it;
        //空闲列表数目+1
        p->sl_curr++;
#ifdef EXTSTORE
        if (!is_hdr) {
            p->requested -= size;
        } else {
            p->requested -= (size - it->nbytes) + sizeof(item_hdr);
        }
#else
        p->requested -= size;
#endif
    } else {
        do_slabs_free_chunked(it, size);
    }
    return;
}
hashtable 源码

assoc_init hashtable 初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* assoc.c: line 59 */
void assoc_init(const int hashtable_init) {
    // 如果没有设置 hashtable_init 值，则取默认 16
    if (hashtable_init) {
        hashpower = hashtable_init;
    }
    // 因为hash表会动态增大，所以使用动态内存分配，hashsize(hashpower) 获取的就是hashtable长度了，默认 65536
    primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));
    if (! primary_hashtable) {
        fprintf(stderr, "Failed to init hashtable.\n");
        exit(EXIT_FAILURE);
    }
    STATS_LOCK();
    stats_state.hash_power_level = hashpower;
    stats_state.hash_bytes = hashsize(hashpower) * sizeof(void *);
    STATS_UNLOCK();
}

item_get 我们从 item_* 方法中选取 item_get 进行解析 hashtable 的数组定位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/* thread.c: line 557 */
item *item_get(const char *key, const size_t nkey, conn *c, const bool do_update) {
    item *it;
    uint32_t hv;
    // 对 key 进行 hash值计算 
    hv = hash(key, nkey);
    // 为了保证原子性，对item进行加锁操作
    item_lock(hv);
    it = do_item_get(key, nkey, hv, c, do_update);
    // 解锁
    item_unlock(hv);
    return it;
}

do_item_get 方法里有个 assoc_find 操作，用来查找 hashtable 数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* assoc.c: line 74 */
item *assoc_find(const char *key, const size_t nkey, const uint32_t hv) {
    item *it;
    unsigned int oldbucket;
    // 是否正在扩容，memcached 的扩容是另外一个线程进行的，所以这里需要进行判断
    if (expanding &&
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
        it = old_hashtable[oldbucket];
    } else {
        // hv是key的hash值，对hash值和hashtable的数量进行 按位与运算，定位具体 table的下标
        it = primary_hashtable[hv & hashmask(hashpower)];
    }
    item *ret = NULL;
    int depth = 0;
    while (it) {
        // 遍历具体某个hashtable下的单链表，直接比对查找影响效率，这里添加了一个 nkey 长度辅助查找 
        if ((nkey == it->nkey) && (memcmp(key, ITEM_key(it), nkey) == 0)) {
            ret = it;
            break;
        }
        it = it->h_next;
        ++depth;
    }
    MEMCACHED_ASSOC_FIND(key, nkey, depth);
    return ret;
}

assoc_insert 新增一个 item，一般会先找到 key 对应的 hashtable，然后 头插法 放入 hashtable 的头部

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/* assoc.c: line 155 */
int assoc_insert(item *it, const uint32_t hv) {
    unsigned int oldbucket;
//    assert(assoc_find(ITEM_key(it), it->nkey) == 0);  /* shouldn't have duplicately named things defined */
    // 判断是否在扩容中
    if (expanding &&
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
        it->h_next = old_hashtable[oldbucket];
        old_hashtable[oldbucket] = it;
    } else {
        // 头插法 放入hashtable 头部
        it->h_next = primary_hashtable[hv & hashmask(hashpower)];
        primary_hashtable[hv & hashmask(hashpower)] = it;
    }
    MEMCACHED_ASSOC_INSERT(ITEM_key(it), it->nkey);
    return 1;
}

assoc_delete 删除一个 item则不一样，一般会先找到 key 对应的 hashtable，然后遍历 链表 找到对应的 item 并删除，这个查找 item 则使用的是 _hashitem_before 方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* assoc.c: line 174 */
void assoc_delete(const char *key, const size_t nkey, const uint32_t hv) {
    // 找到前一个 item
    item **before = _hashitem_before(key, nkey, hv);
    if (*before) {
        item *nxt;
        /* The DTrace probe cannot be triggered as the last instruction
         * due to possible tail-optimization by the compiler
         */
        MEMCACHED_ASSOC_DELETE(key, nkey);
        nxt = (*before)->h_next;
        // 单链的删除元素比较简单，移除前一个item的 h_next 即可
        (*before)->h_next = 0;   /* probably pointless, but whatever. */
        *before = nxt;
        return;
    }
    /* Note:  we never actually get here.  the callers don't delete things
       they can't find. */
    assert(*before != 0);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/* assoc.c: line 103 */
static item** _hashitem_before (const char *key, const size_t nkey, const uint32_t hv) {
    item **pos;
    unsigned int oldbucket;
    if (expanding &&
        (oldbucket = (hv & hashmask(hashpower - 1))) >= expand_bucket)
    {
        pos = &old_hashtable[oldbucket];
    } else {
        pos = &primary_hashtable[hv & hashmask(hashpower)];
    }
    // 遍历单链表查询，同样这里为了提高效率先进行 长度判断，再使用 memcmp
    while (*pos && ((nkey != (*pos)->nkey) || memcmp(key, ITEM_key(*pos), nkey))) {
        pos = &(*pos)->h_next;
    }
    return pos;
}

本文作者： wettper
本文链接： http://www.web-lovers.com/memcached-source-storage.html
版权声明： 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！

赏

谢谢你请我吃糖果

支付宝
微信

扫一扫，分享到微信

微信分享二维码

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

wettper <br /><br /> 现 离职状态 程序猿 <br /><br /> 叫醒我的不止阳光，还有梦想！<br /><br /> 喵喵、念念、健身、吉他！