毕业后荒废了很多时间. 最近收拾心情, 想找几个存储的开源项目学习下. 先看了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上, 可以不发生随机写.

总结

代码虽然很短, 还是能学到一点知识, 尤其是随机写转为顺序写的思路. 最牛逼的是对删除请求, 只删索引不改数据的机制真是简单高效.

update

1. 关于删除操作: 上文没有介绍清楚, 这里详细解释下, 从item结构可以看出它没有next指针, 也就是说, 对某个slab而言, 可以认为它只提供append item操作, 新分配的item都压在slab数据尾部. 当需要删除某个key时, fatcache只在在hash表上删除对应的itemx(前文介绍过, itemx只是item的摘要, md唯一标识key), 也就是说不管item在内存slab还是在磁盘slab, 都不会发生删除item的操作. item的真正删除是以slab为单位, 从内存淘汰到磁盘后才发生的. 作为一个缓存服务, 这没有任何问题.

2. 如何将fatcache改造为永久存储服务: fatcache代码模块化不错, 改造起来应该没什么大问题, 比较不好处理的是第1点提到的未真正删除item而带来的存储空间出现空洞的问题. 这也许可以分两方面解决: 一是对item在内存的情况, 可以用对应slab上的最后一个item覆盖待删除item的空间(对同一slab, item大小是相同的), 这种方式可以保证slab作为数组类的操作, 不会出现空洞, 仍然不需要使用额外的next指针来维护链表; 二是对item在磁盘的情况, 可以通过某种机制在特定时刻触发磁盘slab的回收, 回收时可以针对该磁盘slab上的所有item, 一一查找hash表, 如果找不到itemx或者itemx指向存储空间不同(说明item已被删除, 或者删除后插入了key相同的数据), 跳过该item, 否则, 将item从fatcache中删除后重新插入. 最后将磁盘slab标记为free即可.