毕业后荒废了很多时间. 最近收拾心情, 想找几个存储的开源项目学习下. 先看了fatcache的代码, 它是twitter开源的缓存服务, 可以认为是SSD版的memcache(索引还是在内存). 本文简单分析下, 做个备忘.
generic queue
fatcache使用generic queue维护资源使用情况, generic queue的实现在fc_queue.c. 和常见思路一致：fatcache在启动时, 预先分配一大块内存, 划分为多个元素, 并将多个元素组织成一个队列, 作为空闲队列. 需分配元素时, 将元素从空闲队列中弹出压入已使用队列. 当归还元素时, 将元素从已使用队列弹出压入到空闲队列.
slab allocator
fatcache底层采用slab allocator内存模型, 并且使用hash表快速索引key所在的item.
结构定义
如上所述, fatcache采用slab allocator内存管理模型. slab所占内存大小相同,但slab上item的大小可以不同, fatcache按照item大小将slab分级, 称为slabclass, 每种class有不同的id, 记做cid. slabclass的结构为:
47 struct slabclass {
48 uint32_t nitem; /* # item per slab (const) */
49 size_t size; /* item size (const) */
50 size_t slack; /* unusable slack space (const) */
51 struct slabhinfo partial_msinfoq; /* partial slabinfo q */
52 };
其中,nitem表示该class下每个slab有多少item, size表示每个item的大小, partial_msinfoq作为队列头指针, 指向已使用但未满的slabs所组成的队列.
slab的结构为:
21 struct slab {
22 uint32_t magic; /* slab magic (const) */
23 uint32_t sid; /* slab id */
24 uint8_t cid; /* slab class id */
25 uint8_t unused[3]; /* unused */
26 uint8_t data[1]; /* opaque data */
27 };
magic是魔数, 做校验用. sid表示该slab的id, cid表示该slab的级别. unused作为padding未使用. data便是item数组. 同一个slab在不同的周期可以属于不同slabclass(由cid确定).
slab可以在内存中, 也可以在磁盘上. 每个slab一一对应一个摘要结构体, 称为slabinfo. slabinfo是永在内存中的. 其结构为:
35 struct slabinfo {
36 uint32_t sid; /* slab id (const) */
37 uint32_t addr; /* address as slab_size offset from memory / disk base */
38 TAILQ_ENTRY(slabinfo) tqe; /* link in free q / partial q / full q */
39 uint32_t nalloc; /* # item alloced (monotonic) */
40 uint32_t nfree; /* # item freed (monotonic) */
41 uint8_t cid; /* class id */
42 unsigned mem:1; /* memory? */
43 };
其中,sid为slab的id, cid表示slab属于哪个级别. nalloc表示该slab当前已使用的item数, nfree表示该slab当前仍剩余的空闲item数. mem表示slab在内存中还是在磁盘上.
fatcache作为类memcache, 原理是在内存中维护hash表, 表元素记做itemx:
23 struct itemx {
24 STAILQ_ENTRY(itemx) tqe; /* link in index / free q */
25 uint8_t md[20]; /* sha1 message digest */ //作为key.
26 uint32_t sid; /* owner slab id */
27 uint32_t offset; /* item offset from owner slab base */
28 uint64_t cas; /* cas */
29 } __attribute__ ((__packed__));
sid表示该item所在slab, offset表示item在slab的偏移. cas是memcache协议定义的业务相关字段, 无须理解.
需要说明的是uint8_t md[20]字段, 它表示key的摘要. 因为在fatchache中, key最长可以为256, 明显太大了, 所以fatcache认定md标志一个key, 多个不同的key如果md相同, fatcache将认为这些key相同.
itemx只是item在内存中的摘要信息. 真正的item既可以保存在内存slab中, 也可以在磁盘slab中. item结构为:
23 struct item {
24 uint32_t magic; /* item magic (const) */
25 uint32_t offset; /* raw offset from owner slab base (const) */
26 uint32_t sid; /* slab id (const) */
27 uint8_t cid; /* slab class id (const) */
28 uint8_t unused[2]; /* unused */
29 uint8_t nkey; /* key length */
30 uint32_t ndata; /* date length */
31 rel_time_t expiry; /* expiry in secs */
32 uint32_t flags; /* flags opaque to the server */
33 uint8_t md[20]; /* key message digest */
34 uint32_t hash; /* key hash */
35 uint8_t end[1]; /* item data */
36 };
fatcache将key和value按tl格式保存在end尾端.
处理流程
启动阶段:
fatcache根据参数选项得知总共有多少slab级别(uint8_t nctable), 在内存中创建slabclass数组(struct slabclass *ctable), 依次初始化. 然后在内存中创建slabinfo数组(struct slabinfo *stable), 个数(uint32_t nstable)为配置的内存slab数(uint32_t nmslab)和磁盘slab数(uint32_t ndslab)之和. 然后将slabinfo数组逐一初始化, 前nmslab个元素slabinfo.mem为1, 表示slab在内存. 后ndslab个元素slabinfo.mem为0, 表示slab在磁盘.
然后fatcache创建一大块内存, 大小为nmslab * settings.slab_size (记住每个slab大小相同), 再将内存分割为多个slab并逐一入内存slab空闲队列(struct slabhinfo free_msinfoq). 同理, fatcache将磁盘分割为多个slab并逐一入磁盘slab空闲队列(struct slabhinfo free_dsinfoq).
工作阶段:
fatcache定义了几个辅助函数, 其中 uint8_t slab_cid(size_t size) 表示size大小的item属于哪个slabclass. 当需要分配一块大小为size的item时, 首先用过slab_cid()函数获得对应的cid, 然后通过struct item *slab_get_item(uint8_t cid)函数分配item. 其处理流程为:
1. 如果内存中无空闲的itemx, 则调用slab_evict()函数，它找到最老的磁盘slab, 逐一将该slab上的所有item对应的itemx从hash表中删除.
2.1 如果slabclass.partial_msinfoq不为空, 则对头部的slabinfo, 从其对应的slab上分配一个item. 如果slab此时没有空闲item, 则将slabinfo从partial_msinfoq中移除, 插入到full_msinfoq中
2.2 如果slabclass.partial_msinfo为空, 则从free_msinfoq中弹出一个slabinfo, 从对应的slab上分配item, 并将该slab从free_msinfoq移除后插入partial_msinfoq或full_msinfoq
3. 如果2.1或2.2都未成功分配, 则调用slab_drain()函数, 它将删除磁盘上最老的slab(通过slab_evict()), 然后调用_slab_drain()函数, 找到full_msinfoq中最老的一个slabinfo对应的内存mslab, 然后从free_dsinfoq中找到一个的磁盘dslab, 将mslab数据写入dslab, 交换两个slab对应的slabinfo的标志和所管理的数据的起始地址(即slabinfo.addr和slabinfo.mem). 然后尾递归调用slab_get_item()跳回1重新干活.
淘汰策略
既然使用了generic queue, 淘汰策略必须是FIFO, 这是很容易实现的: slab如果有更新, 插入到queue尾部. 如果需淘汰, 从queue头部开始.
高效的读写
对于写操作：上面的流程保证了slab_get_item()返回的item必定在内存中, 所以上层可以直接将数据写入item尾部(item.end). 如果某个slab已写满, 且没有其他的空闲slab, 则上面的操作3所调用的_slab_drain()函数, 将内存slab和磁盘slab做数据交换时, 可以成片将数据写入磁盘. 可以理解为将随机写缓存在slab中转为顺序写.
对于读操作：SSD对随机读本来就有很高的IOPS.考虑到SSD读写块大小为512字节, fatcache通过下面几行代码在应用层做了对齐:
492 off = slab_to_daddr(sinfo) + addr;
493 aligned_off = ROUND_DOWN(off, 512);
494 aligned_size = ROUND_UP((c->size + (off - aligned_off)), 512);
495
496 n = pread(fd, readbuf, aligned_size, aligned_off);
497 if (n < aligned_size) {
498 log_error("pread fd %d %zu bytes at offset %"PRIu64" failed: %s", fd,
499 aligned_size, (uint64_t)aligned_off, strerror(errno));
500 return NULL;
501 }
502 it = (struct item *)(readbuf + (off - aligned_off));
对于删除操作：SSD在hash表的层面删掉索引. 数据不做修改, 等待自然淘汰. 这种机制保证了如果数据在SSD上, 可以不发生随机写.
总结
代码虽然很短, 还是能学到一点知识, 尤其是随机写转为顺序写的思路. 最牛逼的是对删除请求, 只删索引不改数据的机制真是简单高效.