Bigtable与LevelDB关系与解释

文章链接

文章首先做了Bigtable的基本介绍，可参见阅读笔记，随后讨论了LevelDB与其关系及实现细节。

LevelDB简介

Bigtable只是一篇介绍性论文，并且使用了大量Google内部的组件如GFS\Chubby等，使我们难以理解其全貌。LevelDB是一个由Bigtable作者参与开发的，开源、单机版的Bigtable功能的一个实现。
其接口非常简单易懂：

class DB {
 public:
  virtual Status Put(const WriteOptions& options, const Slice& key, const Slice& value) = 0;
  virtual Status Delete(const WriteOptions& options, const Slice& key) = 0;
  virtual Status Write(const WriteOptions& options, WriteBatch* updates) = 0;
  virtual Status Get(const ReadOptions& options, const Slice& key, std::string* value) = 0;
}

写操作

1. 调用MakeRoomForWrite，为内存预留足够空间。空间不足会发生一次minor compaction创建新memtabel（新memtable开始处理线上请求，老memtable开启minor compaction），并有可能因为新增的SSTable再触发一次merge compaction。
2. 调用AddRecord新增一条日志
3. 调用InsertInto往memtable中插入一条数据

日志存储格式

略过不提

记录的插入

Put\Delete方法内部都是往memtable里插入一条数据，传入不同的数据类型。数据包含键值、序列号与类型，拼接后存入内部的一个skiplist。每次读某键的最新数据，就可确认其是删除还是正常状态。

数据的读取

LevelDB 总会将新的键值对写在最前面，并在数据压缩时删除历史数据。前面的MemTable与IMM像是二级缓存，后面则有不同层级的SSTable文件，因为这种层级所以称为LevelDB。
除了Level0需要全部遍历，后面可通过SSTable的smallest/largest信息找到对应的SSTable与对应的值，直到遍历到最后一个Level kNumLevels。

后续很简略的说明了compaction的大体流程，和SSTable的存储方案，可以见原文：https://draveness.me/bigtable-leveldb