LevelDB阅读笔记:DB接口

LevelDB使用接口

class DB

在leveldb中，作者提供了class DB这个抽象基类作为整个levelbd库暴露给外界的接口，这个基类包含了leveldb这个kv系统应该支持的操作接口，例如打开数据库，关闭数据库，读写操作，快照等等。该类放置在文件include/leveldb/db.h中。

除了抽象基类db，其他的一些需要被用户使用到的对象，包括：用于打开DB的Option类，用于进行读写操作的ReadOption, WriteOption等等也在该文件中被声明，其定义可以在include/leveldb/option.h中找到。

总的来说，整个db.h文件的构建如下：

struct Options;
struct ReadOptions;
struct WriteOptions;
class WriteBatch;

class LEVELDB_EXPORT DB {
 public:
  static Status Open(const Options& options, const std::string& name,
                     DB** dbptr);

  DB() = default;

  DB(const DB&) = delete;
  DB& operator=(const DB&) = delete;

  virtual ~DB();
	
  // Read/write operation interface
  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;
  
  // Iterator and Snapshort
  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;
};

LEVELDB_EXPORT Status DestroyDB(const std::string& name,
                                const Options& options);


LEVELDB_EXPORT Status RepairDB(const std::string& dbname,
                               const Options& options);

接口

• DB的创建： static Open(const Options& options, const std::string& name, DB** dbptr)

  Q: 为什么不直接把name放到options里面，还要单独为name占据一个参数的位置呢？

  A: 一个我认为合理的解释是Options有默认构造函数，但std::string的默认构造函数是空字符串，在这个数据库场景下是非法的。

• 读写操作接口：

  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;

其中，每个读写操作：Put, Delete, Write, Get都带有一个对应的Option参数作为本次操作的配置。此外，Put，Delete操作都是单次操作，可以看到：它们的参数都是单个的key和value；但是Write操作是批量更新操作，其参数是一个WriteBatch。

为一个KV数据库同时提供单点的更新：Put与Delete, 以及批量更新的操作Write是一种非常典型的模式。这背后，是有应用需求在支持这种设计。显然单点更新的延迟更低，但批量更新可以获得较高的吞吐，各自有各自的优势。而且很难说LevelDB内部是不是也可能将一个Put和Delete单次更新缓存在一个WriteBatch中。

• 范围操作：

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

  LevelDB并没有提供显式的range操作，通过返回迭代器来由用户进行范围查询。迭代器应该包含哪些数据结构，以及如何维护迭代器与DB本身数据之间的一致性，我认为是设计迭代器这类数据结构的难点。

• 获取数据库本身的信息：

  virtual bool GetProperty(const Slice& property, std::string* value) = 0;
  virtual void GetApproximateSizes(const Range* range, int n, uint64_t* sizes) = 0;

​ 实际上，这部分并不是一个KV设计的重点，但是至少还是应该要有。

---

设计

从上面的代码中，我们可以看出以下几点设计：

• LevelDB使用static函数来进行一个DB对象的创建，这种方式与DBImpl对DB的继承有关，可以屏蔽底层的实现细节：

  // db_impl.cc: 
  Status DB::Open(const Options& options, const std::string& dbname, DB** dbptr);

• 与Open对应的是，DestroyDB, RepairDB均不是作为DB的成员函数，而是独立于class DB实现的函数，并且其参数中也没有明确的DB*指针来指明操作的目标DB, 而是与Open一样，是通过std::string类型的dbname作为参数实现的。

• 其他的接口均作为DB的成员函数来提供服务，但都被设置为纯虚函数，以此来屏蔽实现细节。

除此之外，还有一些值得注意的地方：

• NewIterator和GetSnapshot函数的接口被设计为返回一个对应对象的指针，而且注释中明确说明Iterator对象是在堆上分配的：

  // Return a heap-allocated iterator over the contents of the database.

而Snapshot对象不清楚，但估计也差不多，而且注释中要求一个创建的Snapshot对象需要通过ReleaseSnapshot来进行释放和销毁。这里值得注意的原因是在自己写迭代器时总是会纠结于到底是返回一个指针还是一个Iterator对象。在LevelDB中，该接口返回指针的原因是，Iterator对象本身也是一个抽象基类，所以需要返回指针来代表实际的迭代器对象，但是不可能返回一个指向局部对象的指针，所以只能是使用堆上对象进行返回了。这样的弊端在于需要调用者来显式释放迭代器对象。

此外，这里的Iterator类基本上应该是作为整个DB的迭代器基类，因此其他内部的类，例如索引，或是sstable内部实现的用于局部遍历数据的iterator不应该继承此处的Iterator基类。

• DB基类还提供了CompactRange接口用于对指定范围的key-value数据进行compact操作：按照注释所声明的那样，compact会删除重复的key-value对，并且重新安排数据的存储来减少访问它们的开销。

  我之前也曾经非常疑惑是否需要为一个本身就提供了内部数据compact的KV再显式地提供compact接口，从这里来看应该是需要的，这会使得该数据库的功能更加完善。而Bitcask模型，应该是内部并不维护后台的compaction，而完全由用户显式地调用Compact接口来实现数据compact的功能。

---

其他与DB相关的类包括：

class Range;		// 基本上就是两个Slice组成的pair，用来指定一个range的范围，注意这里的Range是左开右闭的区间
class Snapshot;	// 一个Snapshot的基类，基本没有内容
struct Options;			
struct ReadOptions;
struct WriteOptions; // 3个用于进行configuration的option结构，注意它们并非相互继承的关系
class WriteBatch; // 多个Update操(指Put和Delete)的聚合，用于一次性apply多个更新操作

Options类

Options类内部的参数对整个DB的执行行为进行了控制，并且对一些内部数据结构的参数进行了指定。按照代码中的注释，class Options的配置参数可以分为两类：

• Affect Behaviour

  • bool create_if_missing = false; & bool error_if_exists = false; ： 用于在打开一个DB时控制该DB的行为，前者指定当目标DB不存在时(Open())是否要创建db，后者用于指定当一个db存在时是否要报错。由于DB只提供了Open接口，因此这个借口需要同时实现：Create以及Open existed的功能。
  • Env* env: 说明当前执行的环境，主要是操作系统相关的一些东西。作为一个跨平台执行的数据库，基于系统封装很有必要
  • const Comparator* comparator: 说明该DB所基于的排序。很明显，同一个DB自从创建开始就应该一直使用相同的顺序，代码的注释中特别提到了这一点。
  • Logger* info_log = nullptr: 用于指定日志信息的输出目标，如果此处设置为nullptr，leveldb内部会创建新的文件用于存储日志。值得说明的是，这里的日志和DB内部的写前日志(Write-Ahead Log)不是一个东西, 更像是用于记录运行时状态的日志信息。（这里也可以看出作为一个工业产品与科研玩具的不同。）

• Affect Performance

  ​ 此类参数大多是关于db内部数据结构的配置，例如cache的大小，打开文件的数目，文件的大小等等，这里并不展开描述。

---

ReadOptions类

struct LEVELDB_EXPORT ReadOptions {
  ReadOptions() = default;
  // Default parameters:
  bool verify_checksums = false;
  bool fill_cache = true;
  const Snapshot* snapshot = nullptr;
};

ReadOptions类的配置参数较少，并且从其命名上就能看出该配置代表的性质。值得注意的是fill_cache，该值表明了在读取时是否用读取的数据来填充cache，作者在注释中的建议是在进行scan range时不要将该参数设置为true: 在范围查询会通过NewIterator返回一个迭代器，返回查询是通过不断递增这个迭代器来达到目的的，如果fill_cache设置为true，可能会导致执行scan时数据不断填充cache，从而导致cache被”污染“。

WriteOptions类

WriteOptions仅有一个参数sync,用于控制该次写操作是否从操作系统buffer中被刷新到磁盘上。显然，如果该值被置为true，那么写操作很慢但是会被持久化，反之db将无法保证此次写操作的持久化。

LevelDB的一次写会被先写入到memtable中，然后再一次性将一个memtable刷新到磁盘中。如果在一次Put操作中将该值置为true，那么这次写操作会bypass memtable吗？还是说它会照常写入memtable，但是提前进行memtable的flush。这个问题需要到后面看到memtable的部分才能完全解答。

---

WriteBatch类

WriteBatch类是leveldb提供给用户的头文件内容之一，因为该类被用于DB的Write接口：

virtual Status Write(const WriteOptions& options, WriteBatch* updates) = 0;

从名字可以看出来,WriteBatch缓存了多个Put, Delete请求，然后通过一次Write调用写入到DB内部。通过write_batch.h文件头部的注释可以看出这一点：

// WriteBatch holds a collection of updates to apply atomically to a DB.
//
// The updates are applied in the order in which they are added
// to the WriteBatch.  For example, the value of "key" will be "v3"
// after the following batch is written:
//
//    batch.Put("key", "v1");
//    batch.Delete("key");
//    batch.Put("key", "v2");
//    batch.Put("key", "v3");
//
// Multiple threads can invoke const methods on a WriteBatch without
// external synchronization, but if any of the threads may call a
// non-const method, all threads accessing the same WriteBatch must use
// external synchronization.

不过让我好奇的是这里所谓的：apply atomically to a DB是什么意思，atomically需要从两个方面满足要求：

• 多个线程并发写入或读取时需要保证一个batch内部的数据是原子更新的
• 在WriteBatch写入时，如果发生了掉电或者crash，这个batch内部的所有的数据要么是完全被持久化的，要么完全没有持久化。

在后面的代码部分我们会着重关注这里的原子性实现。

类的构成：

WriteBatch的数据部分只有一个std::string,用于保存这个batch中的所有Put与Delete请求，WriteBatch提供了Put，Delete接口，其含义与DB的对应接口相同，即进行一个Put和Delete操作。当对一个WriteBatch对象调用Put或是Delete时，WriteBatch会在内部生成该操作的一条记录。

class LEVELDB_EXPORT WriteBatch {
 public:
  class LEVELDB_EXPORT Handler {
   public:
    virtual ~Handler();
    virtual void Put(const Slice& key, const Slice& value) = 0;
    virtual void Delete(const Slice& key) = 0;
  };

  WriteBatch();

  // Intentionally copyable.
  WriteBatch(const WriteBatch&) = default;
  WriteBatch& operator=(const WriteBatch&) = default;

  ~WriteBatch();

  // Store the mapping "key->value" in the database.
  void Put(const Slice& key, const Slice& value);

  // If the database contains a mapping for "key", erase it.  Else do nothing.
  void Delete(const Slice& key);

  // Clear all updates buffered in this batch.
  void Clear();

  // The size of the database changes caused by this batch.
  //
  // This number is tied to implementation details, and may change across
  // releases. It is intended for LevelDB usage metrics.
  size_t ApproximateSize() const;

  // Copies the operations in "source" to this batch.
  //
  // This runs in O(source size) time. However, the constant factor is better
  // than calling Iterate() over the source batch with a Handler that replicates
  // the operations into this batch.
  void Append(const WriteBatch& source);

  // Support for iterating over the contents of a batch.
  Status Iterate(Handler* handler) const;

 private:
  friend class WriteBatchInternal;

  std::string rep_;  // See comment in write_batch.cc for the format of rep_
};

此外，WriteBatch还提供了一个Handler类，这个类是一个抽象基类，并且仅提供了Put和Delete接口，其含义是，Handler会将WriteBatch中的记录应用于对应的其他对象上，这里的其他对象取决于Handler内部的实现。

例如，在write_batch.cc中，通过继承WriteBatch::Handler实现了MemTable::Inserter，因此，可以将一个WriteBatch中的所有数据应用于指定的MemTable上。应用的方式是通过调用WriteBatch中的Iterate函数，遍历所有记录，对每个记录调用Handler的对应Put或是Delete操作。

---

类成员函数实现

WriteBatch并没有直接对所有成员函数进行实现，而是通过一个friend class WriteBatchInternal进行内部实现，再由WriteBatch直接调用WriteBatchInternal的对应实现执行函数。而一个WriteBatchInternal以一个WriteBatch作为参数，需要获得其内部的数据信息，因此是一个friend class。

而WriteBatchInternal只需要对一个WriteBatch对象进行数据的处理，本身并不需要维护任何数据信息，因此它并不需要任何成员数据，而且其所有对WriteBatch接口的实现都是static的：

// WriteBatchInternal provides static methods for manipulating a
// WriteBatch that we don't want in the public WriteBatch interface.
class WriteBatchInternal {
 public:
  // Return the number of entries in the batch.
  static int Count(const WriteBatch* batch);

  // Set the count for the number of entries in the batch.
  static void SetCount(WriteBatch* batch, int n);

  // Return the sequence number for the start of this batch.
  static SequenceNumber Sequence(const WriteBatch* batch);

  // Store the specified number as the sequence number for the start of
  // this batch.
  static void SetSequence(WriteBatch* batch, SequenceNumber seq);

  static Slice Contents(const WriteBatch* batch) { return Slice(batch->rep_); }

  static size_t ByteSize(const WriteBatch* batch) { return batch->rep_.size(); }

  static void SetContents(WriteBatch* batch, const Slice& contents);

  static Status InsertInto(const WriteBatch* batch, MemTable* memtable);

  static void Append(WriteBatch* dst, const WriteBatch* src);
};

正是通过这样连接WriteBatch与WriteBatchInternal之间的关系，leveldb屏蔽了WriteBatch的具体实现细节，并且在WriteBatchInternal内部提供了额外的接口使得leveldb内部其他组件也可以使用WriteBatch（例如memtable）。

---

batch内部数据格式

由于WriteBatch是通过一个std::string来存储所有数据，而std::string基本上就只是一个char数组，因此需要有固定的格式才能从这个char数组中解析出每一个Put和Delete请求。

WriteBatch的数据格式较为简单，如下图所示：

// WriteBatch->rep_:
//	|<-SequenceNumber->|<-Count->|<------Records------>|
//	|<-------8B------->|<--4B--->|<------------------->|

// Records:
// 	|<-ValueType->|<-KeySize->|<-KeyContents->|<-ValueSize->|<-ValueContents->|
//  |<----1B----->|<-------------------Unknown------------------------------->|

首先，一个WriteBatch对象包含了一个头部（Header), 用于一个8B的sequence number，以及一个4B的Count，前者说明这一个Batch内的所有记录的Sequence Number，后者说明记录的数目。

紧接着的是多条操作记录，记录是Put还是Get是通过ValueType(kTypeValue, kTypeDeletion)来标识的，然后是经过Encoding的keysize，以及key的contents，以及经过Encoding的value size,以及value的内容。只有当ValueType表示是一次Put操作，即该值为(kTypeValue)时才会有Value域。

---

WriteBatchInternal接口实现

一旦明确了上述WriteBatch组织的数据, 要实现Put, Delete等操作就非常容易了，下面以WriteBatchInternal::Put为例说明实现逻辑：

void WriteBatch::Put(const Slice& key, const Slice& value) {
  WriteBatchInternal::SetCount(this, WriteBatchInternal::Count(this) + 1);// 递增该batch的记录数目
  rep_.push_back(static_cast<char>(kTypeValue));	// 标记该值为value(对应的，Delete就应当是kTypeDelete)
  PutLengthPrefixedSlice(&rep_, key);		// 添加key，该encoding函数会先将encoding之后的key size添加到rep_尾部，然后添加
  																			// 内容
  PutLengthPrefixedSlice(&rep_, value);	// 添加value
}

一个值得特别说明的实现是Iterate函数，该函数调用时传入一个Handler, 由Handler内部实现对每条记录如何应用到其他结构上：如memtable。

Status WriteBatch::Iterate(Handler* handler) const {
  Slice input(rep_);
  if (input.size() < kHeader) {
    return Status::Corruption("malformed WriteBatch (too small)");
  }	// 首先判断该WriteBatch的数据是否已经被污染：通过判断Header是否依旧存在
    while (!input.empty()) {	// 对每个读取到的WriteBatch中的记录执行如下操作
    found++;
    char tag = input[0];	// 1. 读取该记录的ValueType
    input.remove_prefix(1);	// remove_prefix相当于递增读取的pointer
    switch (tag) {
      case kTypeValue:	// 如果该value类型是普通的value
        if (GetLengthPrefixedSlice(&input, &key) &&	
            GetLengthPrefixedSlice(&input, &value)) { // 获得该条记录的key和value，并且在GetLengthPrefixedSlice内部
          																						// 已经对读取指针进行了相应的递增
          handler->Put(key, value);	// 通过Handler执行相应操作
        } else {
          return Status::Corruption("bad WriteBatch Put");
        }
        break;
      case kTypeDeletion:	// 如果该记录是Deletion操作
        if (GetLengthPrefixedSlice(&input, &key)) {	// 获取该记录的Key
          handler->Delete(key);	// 	执行删除操作
        } else {
          return Status::Corruption("bad WriteBatch Delete");
        }
        break;
      default:
        return Status::Corruption("unknown WriteBatch tag");
    }
  }
  if (found != WriteBatchInternal::Count(this)) {	// 比较上述执行的记录数目是否与Batch Header中说明的数目相同
    return Status::Corruption("WriteBatch has wrong count");
  } else {
    return Status::OK();
  }
}

从上述实现中，我们应该明白，对于这类内部具有特定数据格式的字符串，我们在使用时必须完全检查它的每一个域，以确保其内容是绝对合法的。例如，在最后，该函数还检查了在while循环中执行的记录数目是否真正等于batch头部记录的count的数目。

---

总结

到目前为止，我们已经考察了leveldb对外提供的类接口，即class DB这个抽象基类，以及Options这族用于控制数据库行为的参数类，还有就是用于批量更新的WriteBatch类。我们学到了以下内容：

• 使用抽象基类与实现类分离的做法有助于屏蔽内部实现，例如leveldb中的class DB与class DBImpl,但是如何将DB指针赋值为对应的implementation class的指针是一个问题，因为一般情况下用户是不会知道有一个DBImpl类的存在的。在LevelDB中，作者通过统一的Open接口来进行赋值。

• 定义抽象基类往往意味着与该类相关的其他类也会被定义为抽象基类，例如class DB与class Iterator。它们的具体实现都向用户隐藏了。

• 使用Option进行性能和行为调参是一个好办法，这不仅在工业界有用，在进行学术研究时，也可以为我们发现系统瓶颈提供帮助。但必须精细地设计参数，例如WriteOption中的sync参数已经足以考察buffered和unbuffered的性能差异了。

• WriteBatch与WriteBatchInternal的设计也屏蔽了底层的实现细节，而这仅仅只需要将WriteBatchInternal设置为WriteBatch的friend class即可实现。但是WriteBatch更让我受益的一点是定义了Handler基类以及对应的Iterate函数，这使得无需定义额外的迭代器就可以实现对WriteBatch记录的遍历。但这其实是提供遍历功能时的两个不同的做法：

  • 提供迭代器，维护迭代器与实际数据的一致性，并由用户自主决定如何使用迭代器
  • 提供遍历函数，要求用户提供使用每条记录的用途，由WriteBatch使用提供的Handler执行

  提供迭代器是昂贵的（参考DB的Iterator基类，迭代器本身需要实现很多功能），而提供遍历功能是逻辑和实现简单的，在一个小小的WriteBatch上，使用后者比较合适。

  简单来说，如果你只需要遍历所有数据，那么使用后者；如果你需要迭代器来实现更加丰富的功能，比如从指定位置开始，向后遍历，重置迭代器等操作；使用后者。