LevelDB剖析(3):memtable和cache

LevelDB内存中除了元数据以外,主要就是memtable和文件cache了. 其中文件cache在功能完整性上是可有可无的,而memtable是完整数据映像的一部分,即用户最新提交的那部分,因此在其落地为table文件之前需要保持稳定高效的读写性服务. 在概念上memtable也可以看做带writeback策略的新数据cache,而log的存在解决了延迟writeback的数据丢失问题;为了避免混淆,本文指的cache都是用于加速查询table文件的cache.

一、memtable
支持高效读写的内存数据结构很多如hash,但memtable不适合用hash实现,因为最终要落地为sstable,但hash本身没有直接维护数据顺序. 各类平衡树结构是保序的,并且高效,但LevelDB选择了SkipList做为memtable的数据结构. SkipList在平均复杂度意义下和平衡树是等价的(最坏复杂度要差些),其优势是整体实现和遍历操作很简单,由于其底层本质上就是一个排序的链接,直接遍历该链表即可完成对memtable的遍历,更适合快速dump的场景.

SkipList逻辑视图:
skiplist_lookup

如图所示,该SkipList的底层就是一个各节点按key(图中为int)排序的链表,只不过每个节点可以有多级next指针域,如key=50的这个节点有3级;不同层级的next指针组成了不同层级上的链表,越往上层链表结点越稀疏(指数递减),跳跃(Skip)区间越大. 在SkipList上的查找和插入操作也很直接,比如上图蓝色路径代表对key=80的查找/插入路径,插入时先插到最底层链表,再根据指数概率递减的原则决定是否依次插入到上层链表中去,因此一次插入可能需要修改多个指针,并发环境下应视为原子事务.

上述逻辑视图中复制了key,实际上节点数据是共享的,实际实现中和普通单链表的区别仅仅是next从单个指针变成了指针数组:

//示意结构,非实际代码
struct SkipListNode {
   Type data;
   SkipListNode *next[1];  //动态分配,至少有最底层
}

memtable场景只存在插入操作,并且一旦插入后便不再改变,直到dump. 因为删除是作为deletion marker记录插入的, 对现有key的更新操作也是类似:对某个UserKey,LevelDB内部会添加一个自增的唯一序号作为InternalKey存储(memtable和sstable存的都是InternalKey),因而统统转化为了插入操作,并且插入后是immutable的. 这样做(多版本)虽然暂时产生了冗余,但简化了很多处理,并且有助于Snapshot功能的实现(参考这里).

InternalKey格式:[UserKey+SeqNum+Tag]. SeqNum全局自增可以看做DB版本号,Tag表示本UserKey是插入还是删除操作。外部以UserKey查询时,可能匹配出多个InternalKey,默认取SeqNum最大的为最新数据返回. 冗余/无效的数据在后续Compact过程中最终会被处理掉.

简单看下memtable的并发读写问题,由于单次插入可能需要修改多个指针,因此当有并发写时必须做事务串行化. 而LevelDB通过使用原子指针和RleaseStore/AcquireLoad语义,允许读写同时进行,即任意时刻最多可以有1个写线程,任意多个读线程在并发访问memtable.

内存中可能同时存在两个memtable:当memtable达到一定大小如4M时,就开始dump到持久层. 此时为了不阻塞服务,需要新建一个memtable(以及对应的log文件)进行切换并继续提供服务,而原memtable被冻结并在Compaction线程中被dump为level_0下的新table,dump完成后原memtable和log即可删除. 如果在旧memtable dump完成前新memtable也被写满了,则说明写入太快,写流程会被阻塞,直到旧memtable完成dump. 一个办法是增加memtable的大小以应对突然的大量写,但会占用更多的资源以及更长的从log中recover的时间.

二、Cache
LevelDB内部主要使用了2个全局cache,一个用于缓存打开的sstable文件对象和相关元数据(FileID->MetaData),叫做table_cache,另一个缓存sstable中的block数据(FileID+Offset->BlockData),叫做block_cache. 分别对应查询流程中涉及到的文件元数据和block内容两个阶段上的缓存需求. cache采用基于hash的通用kv entry结构,并提供了默认的LRU策略实现:

lru_hash

如图,hash表采用常见的bucket + confict_list的方式,hash中的每个entry要么在一个lru_list双链表(红色)中,要么属于in_use_list(蓝色). lru_list中的entry都是用户没有在使用的,因此可用于LRU淘汰(ref_cnt=1),lru_list头指针指向最新插入的刚被使用完的节点(查询命中了cache),尾指针指向最久未被使用的节点,即最佳候选淘汰节点. 在用户从cache获取并使用entry的期间,entry处于in_use_list中(ref_cnt>1),当用户用完时需要显示地调用Cache的Release接口,此时entry被移至lru_list的表头. 淘汰或删除时,先将目标entry从hash中的链表删除,再从lru或in_use链表中删除,最后根据引用计数决定是否调用用户清理函数以及释放entry内存。Entry的内容如下:

/ An entry is a variable length heap-allocated structure.  Entries
// are kept in a circular doubly linked list ordered by access time.
struct LRUHandle {
  void* value;           // value of cache key
  void (*deleter)(const Slice&, void* value);
  LRUHandle* next_hash;  //for hash confict linked list
  LRUHandle* next;       //for 'lru' or 'in_use' doubly linked list
  LRUHandle* prev;       //same 
  size_t charge;         // capacity occupied
  size_t key_length;
  bool in_cache;         // Whether entry is in the cache.
  uint32_t refs;         // References, including cache reference, if present.
  uint32_t hash;         // Hash of key(); used for fast sharding and comparisons
  char key_data[1];      // Beginning of key
}

三个链表指针域分别用于图中的2种链表. 当一个Entry被淘汰时,会调用deleter,例如对于block_cache来说就是释放相应的block所占的内存. capacity表示占用cache空间的大小,比如对block_cache来说就是block的大小,block_cache的总容量就允许被缓存的Block的总大小如8M;而对table_cache来说,每个entry代表一个打开的table文件,其总容量是允许同时打开的table文件数量如1000. hash字段用于快速扩容,动态re-bucket;buckets的大小始终保持大于等于entry数目,因而hash链表平均长度为1.

由于sstable是immutable的,因此cache不存在更新和一致性问题,entry仅在被淘汰或程序结束时整体删除,并发控制相对简单.

发表评论

电子邮件地址不会被公开。