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

总结

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