浅谈skiplist在LevelDB的应用

什么是跳表

具体参考 http://zhangtielei.com/posts/blog-redis-skiplist.html

Leveldb 为什么用跳表

首先 skiplist作为memtable的数据结构，如果光为了存储kv，那么任何数据结构都能被使用，像Redis的dict。但是 LevelDB 有个特性，就是put 2个相同的key，那么2份相同的key会同时存在于 memtable 中，而不是通常人们理解的使用新的value把老的value替换掉。这就意味着，get时需要保证取到的是新的value而不是旧的。 此时，简单tree是无法保证有序的。

• 注意： LevelDB 的delete 也不会删除memtable中kv的，而是和put一样，插入个节点，标记为是"delete"。

跳表如何保证有序

首先，简单跳表当然只能处理key为数字的情况，但是用户put的key，必然是随机二进制，例如 “mykey”。"mykey"就不能作为跳表的key了吗，并不然。因为你可以设置跳表的“比较函数”用来代替数字的比较。
例如，Level中规定:

mykey > mykeyb
mykey < myke
mykey == mykey

其次考虑如何保证有序。LevelDB中，为每个用户操作的key都赋予了一个seq，是全局递增的。 简单来描述，存入 跳表中的 key，是 “key+seq”，有了seq，那么“比较函数”除了比较上述用户的key以外，还需要比较seq，用户不同时刻输入的key虽然一样，但是seq不一样，自然有了大小之分。

mykey$2 > mykey$1

int InternalKeyComparator::Compare(const Slice& akey, const Slice& bkey) const {
    
  // Order by:
  // increasing user key (according to user-supplied comparator)
  // decreasing sequence number
  // decreasing type (though sequence# should be enough to disambiguate)
  int r = user_comparator_->Compare(ExtractUserKey(akey), ExtractUserKey(bkey));
  if (r == 0) {
    
    const uint64_t anum = DecodeFixed64(akey.data() + akey.size() - 8);
    const uint64_t bnum = DecodeFixed64(bkey.data() + bkey.size() - 8);
    if (anum > bnum) {
    
      r = -1;
    } else if (anum < bnum) {
    
      r = +1;
    }
  }
  return r;
}

查找如何保证查到最新的value

假设用户put了2次"key"，但是value不同，那么第二次put的"key"，因为他的seq比第一次put的"key"的seq大，自然，在跳表中位置在第一次的"key"之后。假设seq 分别是1 和 2，那么跳表中存的key为 “key$1” “key$2”。

此时，用户get了这个key，这个操作的key的seq必然大于等于2，假设是100（例如中间put了其他的key，倒是seq增加了）。
LevelDB，此时在跳表中会查询"key$100"。由于 查询的key是 “key$100”，正常的跳表必然是找不到的结果的，因为只有跳表中只有"key$1" 和 “key$2”。

我们看下面查询函数如何处理的。
iter.Seek(memkey.data()) 执行查找，只有当 跳表中一个kv都不存在时，iter.Valid() 才是NULL，其他情况，iter.Valid()都成立。 iter.key()保存了前一个比待搜索的"key$100"小的跳表节点。这就出现了comparator_.comparator.user_comparator()->Compare这一幕。

bool MemTable::Get(const LookupKey& key, std::string* value, Status* s) {
    
  Slice memkey = key.memtable_key();
  Table::Iterator iter(&table_);
  iter.Seek(memkey.data());
  if (iter.Valid()) {
    
    // entry format is:
    // klength varint32
    // userkey char[klength]
    // tag uint64
    // vlength varint32
    // value char[vlength]
    // Check that it belongs to same user key. We do not check the
    // sequence number since the Seek() call above should have skipped
    // all entries with overly large sequence numbers.
    const char* entry = iter.key();
    uint32_t key_length;
    const char* key_ptr = GetVarint32Ptr(entry, entry+5, &key_length);

    if (comparator_.comparator.user_comparator()->Compare(
            Slice(key_ptr, key_length - 8),
            key.user_key()) == 0) {
    
      // Correct user key
      const uint64_t tag = DecodeFixed64(key_ptr + key_length - 8);
      switch (static_cast<ValueType>(tag & 0xff)) {
    
        case kTypeValue: {
    
          Slice v = GetLengthPrefixedSlice(key_ptr + key_length);
          value->assign(v.data(), v.size());
          return true;
        }
        case kTypeDeletion:
          *s = Status::NotFound(Slice());
          return true;
      }
    }
  }
  return false;
}

其实整体逻辑很简单，就是找一个大于大于当前seq的相同的"key"。搜索出来的"iter.key()"，要么是xx$zz就是要么就是key$yy，前者，说明我们搜索的key压根不存在，因为比我们key距离最近的居然是其他的key；若是后者，说明key$yy这个seq为yy的是最近插入/删除的key。

有没有可能 出现跳表的顺序是这样的
“key$1” > “ke$1” > “key$2” > “ke$2”，如果是这样，我们搜索"key$100"时，前一个值有可能是"ke$2"，从而导致查找失败。实际当然是不可能的，"比较函数"保证了这一点。相同的"key"必然是按照seq排序的。

总结

这就是为什么我们常说LevelDB的数据是有序的。试想，如果像Redis一样，把kv存储在字典里面，那么自然没有顺序一说。这也是为什么LevelDB把删除也作为一个跳表的Node，一切操作皆顺序。