自己写一个简单 key Value store 之 memcached 研究
自己写一个简单 Key-Value Store 之 Memcached 研究
这个小项目的目标是仿照 Memcached,用 c++ 重写一个类似的简单内存 Key-Value Store。
Memcached
首先,我们来研究下 Memcached 的结构,Memcached 是使用 C 写的:
-
网络模型:
Memcached 使用 libevent 网络库,采用同步 I/O,事件驱动的形式。
虽然采用的 libevent,但却并未使用异步 I/O,而是注册事件,可读或可写事件触发后,lidbevent 调用预先注册的回调函数,在自行进行 I/O 读写。
-
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
-
-
内存管理:
这里的内存管理指的是,上述的 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 中。