论文阅读笔记: MemC3: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing

Posted by CodingCat on January 19, 2015

这是一篇发表在NSDI 2013的论文,其基本思想是利用并行的Cuckoo 哈希算法和CLOCK替换算法,来取代Memcached的Cache放置算法,在以读操作为主导的场景下达到更高的系统吞吐量。

Memcached的基本做法以及哈希表的基本概念

Memcache将内存分割为1MB大小的内存页,每一个内存页再被细分为固定大小的chunk. 为了适应不同大小的object, memcached维护不同的slab class, 每一个slab class对应了不同的chunk size。当存储一个新的对象的时候,找到最适合该对象的slab class,然后将其添加到这个slab class的LRU 队列中。

再来看传统的哈希表结构,在传统哈希表中,每一个元素经过一定的哈希函数的计算得到一个键值,这个键值决定了元素在哈希表中的位置。我们称之为,元素所处的哈希桶。当多个元素拥有相同的哈希函数值的时候,系统在每一个哈希桶上构建一个链表,来放置相同哈希值的元素。

这种哈希机制也叫做闭址哈希。闭址哈希的好处是实现简单,但是在读操作为主的场景下,会引入较大的计算复杂度,尤其是存在严重的哈希冲突的时候。因为查询一个元素会需要遍历整个哈希桶上的链表。

Cuckoo Hashing的哈希表结构和闭址哈希其实很类似,也是一个二维结构,其不同之处在于 1) 每一个函数可以在Cuckoo Hashing的表中有两个可能的位置,也就是说,Cuckoo Hashing提供了两个独立的函数来决定元素的可能位置; 2) 处于同一个哈希桶中的元素不再是拥有相同哈希值的元素,而仅仅是被哈希函数哈希到同一个第一维空间上而已。

260B9214-1757-4589-AAD0-27F8406A3A34

上图截取于The Art of Multi-processors Programming 一书,在第一维空间中,空间大小为2,所以有两个哈希桶,而在哈希桶内部还要进行一次计算(mod 8)来决定元素在哈希桶中的位置。

Cuckoo Hashing与闭址哈希最大的不同在于哈希冲突的处理方式。当遇到目标哈希桶内的位置已经被占据的时候,Cuckoo Hashing选择踢掉已经存在的元素,放置新元素,再试图将已经存在的元素放置到他的另一个可能的位置中,这个过程被递归调用,直到找到一个空的位置或者已经尝试的次数大于事先约定的最大尝试数(比如哈希表满的时候我们只能返回插入失败)。

MemC3要解决什么

MemC3第一个要解决的问题是如何有效的减少访存次数。

这个问题为什么会存在呢。首先因为在Cuckoo Hashing的实现中,我们并不要求每一个元素都被映射到一个定长的键值,所以在哈希表中存储的实际上是指向了最终元素及其键值(为什么有键值稍后再讲)的指针,而不是具体的元素。这是为了更好的利用内存空间。因为哈希表某一个特定位置我们通常为了追求实现的方便性,会设置成定长的chunk, 所以我们如果直接把元素和键值存储在哈希表中,哈希表每一个元素的长度就必须以最长的键值长度+最长的元素长度来设置,会造成很大的内存空间浪费。

那么在上述的Cuckoo Hashing算法中,在每一个哈希桶中查找元素时,我们必须多次去内存空间找到元素进行比较,同样的在传统的memcached的实现里, 查找一个链表也需要不断去内存空间里找到元素并比较。为了减少这种不必要的访存开销,MemC3在哈希表中除了存储指针还存储了一个tag, 这个tag可以当成是对元素哈希值的再哈希所得到的值。在查找元素的时候,只有当tag相同我们才会去访问内存找到元素,进行近一步的比较 (为什么?因为不同的KEY值有可能得到相同的tag, 所谓的哈希冲突嘛)

那么在插入时,我们同样需要减少对内存的访问,尤其是在替换元素的时候。所以我们希望能够通过存在哈希表里的信息就计算出元素所属的哈希桶的位置。于是,Mem3C就提出了下面的计算方法:

A04F9C6F-7C30-463C-A28D-378CB908AEB7

MemC3第二个要解决的问题是并发访问的问题。这个并发访问的问题研究中又包含着三个小的问题:

  1. 死锁问题: 在Cuckcoo Hashing中,因为插入一个新的元素会涉及到多个哈希桶中的元素替换,所以在多余一个写操作并发的时候,有可能出现死锁。这就是典型的多writer情况下的死锁。 MemC3显然没太花心思考虑,直接限制了同一时刻,在全局范围内只允许一个写操作。

  2. 并发的写与读造成的元素短暂性失效问题。在如下场景下,假如一个新的元素要加入到哈希表T1当前a的位置,那么必然要踢走a. 假如a的另一个有效位置在T2为空的位置,那么会出现一个短暂性的a在整个哈希表中找不到的现象,那就是a在插入到T2之前的那一时刻。

T1 (a)

T2 ()

要解决这个问题只能把a的整个插入过程做成原子性操作,但是原子性操作又会带来较大的性能开销。所以Mem3C提出,我们先找出插入一个哈希元素要涉及的所有的哈希桶的位置,然后从后往前,反向添加元素。于是在上述过程中,我们先在T2里插入a, 那么这一时刻a一定是存在的,那么再在a的原先位置上加入新的元素。

  1. 第三个并发问题就是读写同步问题。最简单的方法当然是一旦有写操作就锁住整个哈希桶,但是这同样不是一个高效的方法。Mem3C的方法就比较有意思了

Mem3C为每一个key 分配了一个version number, 当进行写操作的时候先将version number 加1, 当完成整个写操作之后,再把这个version number +1。也就是说当一个key已经是稳定状态的时候,version number必然是偶数。于是在读操作的时候我们只要check version number是不是奇数就知道是不是有并发的写操作,并且check 因为并发引起的重试得到的version number值是不是重试之前的值,就能得到是不是已经有写操作更新了key,而使得数据是脏数据。

为了不带来过大的内存开销,Mem3C允许多个key共享一个version number, 从而牺牲了部分并发度,而换取更好的内存效率。

另一个小的优化我觉得很trivial, 就是在决定cuckoo hashing需要设计那几个哈希桶的时候是一个并行过程。

MemC3 要解决的第三个问题就是cache的管理问题

在当前的memcached的实现中,系统采用了LRU算法来剔除元素为新元素争取空间。但是为了维护LRU列表,对每一个元素都要花出18个字节的代价,双向列表,两个指针各8个字节,还有2个字节的访问计数器。当存储对象比较小的时候,这个开销所占的比例就会显得有些大。

MemC3采用了CLOCK算法,对每一个slab class ,MemC3维护一个环形Buffer, buffer中的每一个比特代表了当前元素最近是否被访问到 1 - 访问到了, 0 - 没有。当需要剔除元素的时候,系统检测对应比特位,如果是0则剔除元素,如果是1,则将其置为0并且继续寻找,直到找到一个为0的元素。其实CLOCK就是用一个比特来实现了一个近似的LRU算法以换取更好的内存效率。

这里论文中额外讨论的是当CLOCK算法决定剔除一个元素时,必须更新元素对应的version number,以达到并发控制的目的. (和写操作是一样的)

总结

Mem3C是一个工程味道很浓的文章,也符合 david anderson组一贯的风格。活儿还是比较细的,写的我觉得不是最高水平,但是也很不错了。这个工作发在NSDI证明了系统这个方向,还是应该以问题为导向做些实际的工作的。