leveldb之DBImpl

1、leveldb::DB的成员函数

基类leveldb::DB，提供面向用户的接口，用户主要使用其提供的接口来操作数据库，最重要的操作为增、删、查找。

class DB {
 public:
  static Status Open(const Options& options,const std::string& name,DB** dbptr);//打开一个名为name的数据库，并存放在dbptr中，会调用Recover()
  DB() { }//构造数据库
  virtual ~DB();

  virtual Status Put(const WriteOptions& options,const Slice& key,const Slice& value) = 0;//向数据库中写一条KV数据
  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;//在数据库中查找key对应的value

  virtual Iterator* NewIterator(const ReadOptions& options) = 0;

  virtual const Snapshot* GetSnapshot() = 0;
  virtual void ReleaseSnapshot(const Snapshot* snapshot) = 0;

  virtual bool GetProperty(const Slice& property, std::string* value) = 0;
  virtual void GetApproximateSizes(const Range* range, int n,uint64_t* sizes) = 0;
  virtual void CompactRange(const Slice* begin, const Slice* end) = 0;
 private:
  // No copying allowed
  DB(const DB&);
  void operator=(const DB&);
};

2、leveldb::DBImpl

类leveldb::DBImpl派生自leveldb::DB，是leveldb最核心的部分。

leveldb::DBImpl中包含了大量的函数，包括派生自leveldb::DB的接口，一些用于测试的函数，还有一些用于后台处理的内部函数，用于完成后台合并等操作。下面是它的成员函数，暂时忽略测试函数和用于数据库恢复的函数以及错误处理的函数。

class DBImpl : public DB {
 public:
  DBImpl(const Options& options, const std::string& dbname);
  virtual ~DBImpl();

  // 派生自leveldb::DB的接口
  virtual Status Put(const WriteOptions&, const Slice& key, const Slice& value);
  virtual Status Delete(const WriteOptions&, const Slice& key);
  virtual Status Write(const WriteOptions& options, WriteBatch* updates);
  virtual Status Get(const ReadOptions& options,const Slice& key,std::string* value);
  virtual Iterator* NewIterator(const ReadOptions&);
  virtual const Snapshot* GetSnapshot();
  virtual void ReleaseSnapshot(const Snapshot* snapshot);
  virtual bool GetProperty(const Slice& property, std::string* value);
  virtual void GetApproximateSizes(const Range* range, int n, uint64_t* sizes);
  virtual void CompactRange(const Slice* begin, const Slice* end);
 private:
  Status NewDB();

  void DeleteObsoleteFiles();
  void CompactMemTable() EXCLUSIVE_LOCKS_REQUIRED(mutex_);
  Status WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base)
      EXCLUSIVE_LOCKS_REQUIRED(mutex_);
  Status MakeRoomForWrite(bool force /* compact even if there is room? */)
      EXCLUSIVE_LOCKS_REQUIRED(mutex_);
  WriteBatch* BuildBatchGroup(Writer** last_writer);
  void MaybeScheduleCompaction() EXCLUSIVE_LOCKS_REQUIRED(mutex_);
  static void BGWork(void* db);
  void BackgroundCall();
  void  BackgroundCompaction() EXCLUSIVE_LOCKS_REQUIRED(mutex_);
  void CleanupCompaction(CompactionState* compact)
      EXCLUSIVE_LOCKS_REQUIRED(mutex_);
  Status DoCompactionWork(CompactionState* compact)
      EXCLUSIVE_LOCKS_REQUIRED(mutex_);

  Status OpenCompactionOutputFile(CompactionState* compact);
  Status FinishCompactionOutputFile(CompactionState* compact, Iterator* input);
  Status InstallCompactionResults(CompactionState* compact)
      EXCLUSIVE_LOCKS_REQUIRED(mutex_);

};

由上可知，leveldb::DBImpl的成员函数主要是

1）实现派生自leveldb::DB的接口（对数据的增、删、查找）

2）后台合并相关的函数 （这一部分在leveldb之Compaction上、下中都见到过，就不再分析）

2.1、增加记录

通过Put()写入一条记录，通过Write()批量写入

为了读取更加方便，leveldb每次写入记录时都会创建一个WriteBatch变量，然后再将WriteBatch变量写入到log文件中，并将WriteBatch中的每一条记录插入到Memtable中。即调用Put()时，首先也会将这一条记录转化为一个WriteBatch的形式，然后再调用Write()操作批量写入。

WriteBatch的格式是固定的（seq  count  type key.size()  key  value.size()  value），按照这种方式将数据写入到log中后，读取时顺序的读取每一个WriteBatch即可获得每一条记录。

Put()的实现如下：

Status DB::Put(const WriteOptions& opt, const Slice& key, const Slice& value) {
  WriteBatch batch;
  batch.Put(key, value);
  return Write(opt, &batch);
}

2.2、删除记录

由对LevelDb之Compaction 的分析可知，leveldb在删除一条记录时并不会直接删除，而是写入一条标记为删除的记录，等待后面的合并操作再真正删除该记录。其实现如下

Status DB::Delete(const WriteOptions& opt, const Slice& key) {
  WriteBatch batch;
  batch.Delete(key);
  return Write(opt, &batch);
}

由上可知，删除记录时也是将记录转化成WriteBatch的形式，然后再将其写入到数据库中。

具体的删除操作在高level的合并时完成（见leveldb之Compaction操作下之具体实现 中一般的合并部分）

因此增加记录和删除记录最终调用的都是Write()函数，具体的实现见leveldb之Put、Get操作

2.3、查找记录

Status DBImpl::Get(const ReadOptions& options,const Slice& key,
                   std::string* value) {
  {
    mutex_.Unlock();
    // First look in the memtable, then in the immutable memtable (if any).
    LookupKey lkey(key, snapshot);
    if (mem->Get(lkey, value, &s)) {  //首先在Memtable中查找
      // Done
    } else if (imm != NULL && imm->Get(lkey, value, &s)) {//若没找到且存在imm，则继续在imm中查找
      // Done
    } else { //如果还没有找到，则继续在SSTable中查找
      s = current->Get(options, lkey, value, &stats);
      have_stat_update = true;
    }
    mutex_.Lock();
  }

}

在当前Version中查找时，首先遍历所有level的所有.sst文件，逐个找出Key值范围覆盖target的文件，然后在缓存table_cache_中查找这些文件，若文件不在缓存中，则为其创建一个描述符并加入到缓存中，保证最近使用的文件在缓存中，以提高查找速度。然后在这些文件中逐个查找目标Key对应的记录。

查找的具体实现见 leveldb之SSTable的创建与访问 中的第三部分

3、leveldb::DBImpl的成员变量

leveldb::DBImpl中有许多成员变量，其中最重要的是：

class DBImpl : public DB {
 private:
  TableCache* table_cache_;//SSTable文件缓存，保存了最近使用的.sst文件信息，以提高查找速度

  MemTable* mem_;
  MemTable* imm_;                // 等待合并的mem_，不能再向其中写入数据
  port::AtomicPointer has_imm_;  //判断是否有imm_
  WritableFile* logfile_;   //log文件，数据在插入mem_之前会写入到log文件中，以便于数据恢复
  uint64_t logfile_number_;
  log::Writer* log_;  //用于向log文件中写数据

  std::deque<Writer*> writers_; //任务队列，等待向mem_中写入数据
  std::set<uint64_t> pending_outputs_;//标记一个文件是否正在进行处理，以防止错误的删除正在执行Compaction的文件
  bool bg_compaction_scheduled_;//标记是否已经完成或正在执行Compaction操作
  VersionSet* versions_;//管理数据库运行过程中生成的所有版本
};

写数据时，首先写入log文件，再插入到mem_中，log文件可用于数据恢复，保证数据不丢失。

查找时，按照mem_，imm_，.sst文件的优先级进行查找，table_cache_缓存最近使用的.sst文件

versions_用于管理这个数据库的所有版本。

4、总结

leveldb::DB类为用户提供了操作数据库的接口，主要包括对记录的增、删、查找。

leveldb::DBImpl类派生自leveldb::DB，实现了leveldb::DB中的接口，并且还增加了许多用于后台合并处理的内部函数。

增、删最终都是向数据库中写入一条记录，可能会导致Memtable写满，从而触发合并操作。查找记录时，按照mem_，imm_，.sst文件的优先级来进行查找。

在.sst文件中查找时是先找到覆盖目标Key值的所有文件，然后在缓存table_cache_中进行查找，并将最近使用的文件加入到缓存中。查找可能导致一些.sst文件的查找次数超过上限，此时也会触发合并操作。

读、写都可能触发leveldb的合并操作，合并操作的具体分析见LevelDb之Compaction