自己写一个简单 Key-Value Store 之 Memcached 研究

这个小项目的目标是仿照 Memcached，用 c++ 重写一个类似的简单内存 Key-Value Store。

Memcached

首先，我们来研究下 Memcached 的结构，Memcached 是使用 C 写的：

  1. 网络模型：

    Memcached 使用 libevent 网络库，采用同步 I/O，事件驱动的形式。

    虽然采用的 libevent，但却并未使用异步 I/O，而是注册事件，可读或可写事件触发后，lidbevent 调用预先注册的回调函数，在自行进行 I/O 读写。

  2. Hash Table：

    /* how many powers of 2's worth of buckets we use */
static unsigned int hashpower = 16;

typedef struct _stritem {
    struct _stritem *next;
    struct _stritem *prev;
    struct _stritem *h_next;    /* hash chain next */
    rel_time_t      time;       /* least recent access */
    rel_time_t      exptime;    /* expire time */
    int             nbytes;     /* size of data */
    unsigned short  refcount;
    uint8_t         nsuffix;    /* length of flags-and-length string */
    uint8_t         it_flags;   /* ITEM_* above */
    uint8_t         slabs_clsid;/* which slab class we're in */
    uint8_t         nkey;       /* key length, w/terminating null and padding */
    uint64_t        cas_id;     /* the CAS identifier */
    void * end[];
    /* 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;

static item** primary_hashtable = calloc(hashsize(hashpower), sizeof(void *));

    • Hash Table 默认的 bucket 大小为 2^16 个。

    • 每个 bucket 存储一个 struct item 的指针。

    • 采用 separate chaining(分离链接) 的方式来解决冲突，并且每个链表的节点和 Key-Value 的值存储在一起，这样存储在一起应该是为了提高 CPU 缓存的命中率，提高访问速度。

    • 每个 item 内有 prev 和 next 指针形成双向链表。

      * item * item * item….

    ​ |

    ​ v

    ​ item

    ​ |

    ​ v

    ​ item

  3. 内存管理：

    这里的内存管理指的是，上述的 item 结构在内存中怎么存放。

    memcached 通过三个结构来存放 item：

    page: 内存申请与分配的基本单位

    slab: item 存放的实际结构，每个 slab 都为 一个 page 的大小，每个 slab 又分为一个或多个 chunk

    slab class: 决定这个类型的 slab 内部会分为多少个 chunk

    chunk: chunk 的大小由 slab class 决定

    $ ./memcached -vv
slab class   1: chunk size        80 perslab   13107
slab class   2: chunk size       104 perslab   10082
slab class   3: chunk size       136 perslab    7710
slab class   4: chunk size       176 perslab    5957
slab class   5: chunk size       224 perslab    4681
slab class   6: chunk size       280 perslab    3744
slab class   7: chunk size       352 perslab    2978
slab class   8: chunk size       440 perslab    2383
slab class   9: chunk size       552 perslab    1899
slab class  10: chunk size       696 perslab    1506
[...etc...]

    可以看到，通过这样的设计，既可以到达预分配内存，去除运行时分配内存的开销，同时又不浪费太多的空间，每个 item 都放到适合其大小的 slab class 中。