leveldb研究系列八——Ssttable文件的compaction和LRUcache

第二篇的时候我们讲到Ssttbale是通过inmutable memtable不断导出至磁盘一开始是ssttable 0,而后向下归并，一层又一层形成了ssttable，所以形象地称之为leveldb. Ssttable文件里面的数据都是key有序的，Ssttbale 文件相互指间没有区间重叠，但是这里有一个特殊，就是Sstable 0，Ssttable0 的区间可能和其他Ssttable的区间有重叠，如前面所讲的，Ssttbale采用lsm策略，把索引合并和更新延后，批量处理，这就造成了Ssttable 0没有及时被更新合并，而是等到达到一个point的时候，再进行归并合并。这样做的目的在于降低磁盘i/o的访问次数，提高写性能，代价就是在读（查询的时候） 要做多层索引查询（多一次SSttbale0的），降低了读（查询）的性能。

这就是以读换写的trade。

现在我们重点谈谈，SSttable 0和其他Ssttable文件的归并过程，其实最重要的两点：

1.多路归并的过程中,将至少选择和SSttable0 区间有重叠的SSttable文件，并且一般也会多选择区间不重叠的SSttable文件，这样做的目的是在于尽量保持文件长度的均衡

2。归并过程中对于key相同的，根据他们的sequence 序列号，（前面讲到，序列号指出key的先后)  存入最新的<key,value>,如果是删除操作则直接丢弃

这里很想和大家聊聊多路归并排序。

http://blog.chinaunix.net/uid-25324849-id-2182916.html

这个博客讲多路排序讲的不错。

我在这里再想和大家探讨一下leveldb的多路归并的性能，leveldb对于N个SStable文件的归并提供N个Block的物理内存做排序，m路归并,那么在归并过程中读磁盘的次数就是N*logN/logm次.  m越大，磁盘i/o次数越少。

再说一下败者树吧，败者树相对于胜者树的好处在于：在一次构建完成以后，只要和父节点比较并且调整父节点就可以，不必和兄弟比较（节约查找成本）。

对于n个record，N个block缓存，m多路的内存中排序的时间性能（不考虑磁盘i/o) 为 logN*n。

到此为止，我们已经分析好leveldb的compaction操作。

最后我们讲一个LRUcache， leveldb几乎实现了一个标准的lrucache，那么什么是LRUcache呢？

LRUcache是为了减少磁盘i/o 加快读取，把之前的key,value，放入内存缓存中， Lru的策略是将最久没有使用的key,value置换到磁盘中。

leveldb采用双向链表来实现LRUcache,实现一个FIFO，每次被访问的数据会被加入链表插入端，最久未被使用的在另一端被删除。

另外用来快速查找的定位的，leveldb实现了一个hash-handletable类来快速定位key所在链表的位置。

另外，  另外呢 这个hash-handletable类也是分成16组的目的是减少多线程的锁开销加快并发。  其实就相对于再hash，（两次hash) 不过意义更显著。

struct LRUHandle {
  void* value;
  void (*deleter)(const Slice&, void* value);
  LRUHandle* next_hash;    //hash碰撞时候直接下拉
  LRUHandle* next;      //双向链表   next
  LRUHandle* prev;       //双向链表 prev
  size_t charge;      // TODO(opt): Only allow uint32_t?
  size_t key_length;
  uint32_t refs;      
  uint32_t hash;      // Hash of key(); used for fast sharding and comparisons
  char key_data[1];   // Beginning of key

  Slice key() const {
    // For cheaper lookups, we allow a temporary Handle object
    // to store a pointer to a key in "value".
    if (next == this) {
      return *(reinterpret_cast<Slice*>(value));
    } else {
      return Slice(key_data, key_length);
    }
  }
           

双向链表，有碰撞时候就用下拉链表

查找代码如下

Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  LRUHandle* e = table_.Lookup(key, hash);//hash后查找
  if (e != NULL) {
    e->refs++;
    LRU_Remove(e);
    LRU_Append(e);
  }
  return reinterpret_cast<Cache::Handle*>(e);
}
           

那么table_Lookup是怎么实现的呢

LRUHandle* Lookup(const Slice& key, uint32_t hash) {
    return *FindPointer(key, hash);       //此函数实现
  }
           

LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
    LRUHandle** ptr = &list_[hash & (length_ - 1)];
    while (*ptr != NULL &&
           ((*ptr)->hash != hash || key != (*ptr)->key())) {               //在冲突下拉链表中查找
      ptr = &(*ptr)->next_hash;
    }
    return ptr;
  }
           

实际上在这些工作之前，查找的第一步是 在16个独立的hash类中查找，也就是说首先得找到在那个Handletable中查找

代码如下

virtual Handle* Lookup(const Slice& key) {

    const uint32_t hash = HashSlice(key);

    return shard_[Shard(hash)].Lookup(key, hash);   //定位具体的handletable;

  }

到此为止LRUcache已经分析清楚了 其他的insert,delete就不一一去写了

累觉不爱  哈哈 终于写完了 thanks~