LevelDB 源码阅读一：基础数据结构

继上文搭建完 LevelDB 调试环境后，我们开始阅读源码。本文介绍 LevelDB 中最基础的一些数据结构，按照源文件组织的层次结构，自底向上阅读源码。本文涉及的主要源代码包括以下文件：

• include/leveldb/export.h
• include/leveldb/slice.h
• port/thread_annotations.h
• port/port_stdcxx.h
• port/port.h
• include/leveldb/status.h 和 util/status.cc

1. export.h

include/leveldb/export.h 头文件用于 LevelDB 中控制编译导出符号。在 include/leveldb 文件夹下的头文件中，许多函数/类的声明中都添加了 LEVELDB_EXPORT 宏，这个宏在 CMakeLists.txt 文件中有相关的定义与使用。通过编译时的宏定义，LEVELDB_EXPORT 宏在不同的编译器下有不同的定义，如：Linux 下的 __attribute__((visibility("default"))) 和 Windows MSVC 下的 __declspec(dllexport)。

搞明白这一点后，后续阅读代码遇到类似下面的代码：

class LEVELDB_EXPORT Slice;

就可以简单的忽略其中的宏 LEVELDB_EXPORT，它不影响代码的逻辑。

2. slice.h

Slice 类（include/leveldb/slice.h）是 LevelDB 中重要的基础数据结构，很多数据库的操作，如插入、删除等接口，都以 Slice 类型作为参数。

Slice 类含义如其命名一样：切片，它是对底层字符串的索引，仅存储字符串的起点指针和长度，而不控制字符串的生命期。因此，使用者必须保证 Slice 引用的字符串的生命期长于 Slice 对象的生命期，否则可能引发难以排查的 bug。

Slice 提供了以下接口：

class LEVELDB_EXPORT Slice {
 public:
  Slice() : data_(""), size_(0) {}

  Slice(const char* d, size_t n) : data_(d), size_(n) {}

  Slice(const std::string& s) : data_(s.data()), size_(s.size()) {}

  Slice(const char* s) : data_(s), size_(strlen(s)) {}

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

  const char* data() const { return data_; }

  size_t size() const { return size_; }

  bool empty() const { return size_ == 0; }

  char operator[](size_t n) const {
    assert(n < size());
    return data_[n];
  }

  void clear() {
    data_ = "";
    size_ = 0;
  }

  // Drop the first "n" bytes from this slice.
  void remove_prefix(size_t n) {
    assert(n <= size());
    data_ += n;
    size_ -= n;
  }

  // Return a string that contains the copy of the referenced data.
  std::string ToString() const { return std::string(data_, size_); }

  int compare(const Slice& b) const;

  // Return true iff "x" is a prefix of "*this"
  bool starts_with(const Slice& x) const {
    return ((size_ >= x.size_) && (memcmp(data_, x.data_, x.size_) == 0));
  }

 private:
  const char* data_;
  size_t size_;
};

可以看出，Slice 提供了多种构造函数，可以从标准 C 字符串和 C++ string 构造 Slice 对象，并且显式地允许了拷贝构造和拷贝赋值操作。除了构造函数，Slice 提供的接口绝大多数是只读的，即带了 const 声明。

3. thread_annotations.h

该头文件所在路径为 port/thread_annotations.h 。这一头文件的用途在注释中已经说明：

// Use Clang's thread safety analysis annotations when available. In other
// environments, the macros receive empty definitions.
// Usage documentation: https://clang.llvm.org/docs/ThreadSafetyAnalysis.html

注释中的链接放在这里：https://clang.llvm.org/docs/ThreadSafetyAnalysis.html 。简而言之，这个头文件的作用就是在 clang 编译环境下，启用 clang 提供的线程安全静态分析功能；而在其他编译环境下，宏定义为空，无任何操作。关于 Thread Safety Analysis 的使用方法，可参考上面链接，这里不详细介绍。

4. port_stdcxx.h

本头文件路径为 port/port_stdcxx.h。实际上，port 目录下所有源代码的目的已经在 README.md 文件中说明：

This directory contains interfaces and implementations that isolate the
rest of the package from platform details.

Code in the rest of the package includes "port.h" from this directory.
"port.h" in turn includes a platform specific "port_<platform>.h" file
that provides the platform specific implementation.

See port_stdcxx.h for an example of what must be provided in a platform
specific header file.

这个目录中定义的接口是为了隔离 LevelDB 中其余代码与具体平台。port_stdcxx.h 头文件就是一个示例代码，说明了 LevelDB 剩余部分需要依赖哪些与平台相关的接口。

在 port_stdcxx.h 源代码中，首先根据编译环境是否包含某些包，决定是否包含相应的头文件，如下面的 zstd 压缩相关的包：

#define ZSTD_STATIC_LINKING_ONLY  // For ZSTD_compressionParameters.
#include <zstd.h>
#endif  // HAVE_ZSTD

然后，对 C++ 标准库提供的一些组件进行封装，如对 mutex 封装：

// Thinly wraps std::mutex.
class LOCKABLE Mutex {
 public:
  Mutex() = default;
  ~Mutex() = default;

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

  void Lock() EXCLUSIVE_LOCK_FUNCTION() { mu_.lock(); }
  void Unlock() UNLOCK_FUNCTION() { mu_.unlock(); }
  void AssertHeld() ASSERT_EXCLUSIVE_LOCK() {}

 private:
  friend class CondVar;
  std::mutex mu_;
};

类似地，CondVar 对条件变量进行封装。

下面，则是对一些依赖包的接口进行封装，如压缩相关的：

inline bool Snappy_Compress(const char* input, size_t length,
                            std::string* output) {
#if HAVE_SNAPPY
  output->resize(snappy::MaxCompressedLength(length));
  size_t outlen;
  snappy::RawCompress(input, length, &(*output)[0], &outlen);
  output->resize(outlen);
  return true;
#else
  // Silence compiler warnings about unused arguments.
  (void)input;
  (void)length;
  (void)output;
#endif  // HAVE_SNAPPY

  return false;
}

根据编译环境是否有对应的包，条件编译生成不同的代码。

5. port.h

port.h 头文件是 LevelDB 其余部分真正进行包含的头文件，其源码非常简单：

#ifndef STORAGE_LEVELDB_PORT_PORT_H_
#define STORAGE_LEVELDB_PORT_PORT_H_

#include <string.h>

// Include the appropriate platform specific file below.  If you are
// porting to a new platform, see "port_example.h" for documentation
// of what the new port_<platform>.h file must provide.
#if defined(LEVELDB_PLATFORM_POSIX) || defined(LEVELDB_PLATFORM_WINDOWS)
#include "port/port_stdcxx.h"
#elif defined(LEVELDB_PLATFORM_CHROMIUM)
#include "port/port_chromium.h"
#endif

#endif  // STORAGE_LEVELDB_PORT_PORT_H_

可见，这个头文件就是为了封装可能变化的具体平台，提供统一的接口供 LevelDB 剩余部分使用。在 Linux 和 Windows 中，LevelDB 都默认使用上面介绍的 port_stdcxx.h 头文件中的具体实现。

6. status.h 和 status.cc

LevelDB 中的很多接口都以 Status 类型作为返回值类型。其相关源码位于 include/leveldb/status.h 和 util/status.cc 。下面我们来看 Status 类的具体实现。

Status 类的数据成员只有一个，即 const char *state_ ，精简后的 Status 类代码如下：

class LEVELDB_EXPORT Status {
 public:
  // Create a success status.
  Status() noexcept : state_(nullptr) {}
  ~Status() { delete[] state_; }

  // 省略部分构造函数

  // 类静态方法，创建对应类型的 Status 对象
  // Return a success status.
  static Status OK() { return Status(); }

  // Return error status of an appropriate type.
  static Status NotFound(const Slice& msg, const Slice& msg2 = Slice()) {
    return Status(kNotFound, msg, msg2);
  }
  // 省略其他创建错误状态的函数

  // Returns true iff the status indicates success.
  bool ok() const { return (state_ == nullptr); }

  // 省略其他判断错误类型的函数

  // Return a string representation of this status suitable for printing.
  // Returns the string "OK" for success.
  std::string ToString() const;

 private:
  enum Code {
    kOk = 0,
    kNotFound = 1,
    kCorruption = 2,
    kNotSupported = 3,
    kInvalidArgument = 4,
    kIOError = 5
  };

  Code code() const {
    return (state_ == nullptr) ? kOk : static_cast<Code>(state_[4]);
  }

  Status(Code code, const Slice& msg, const Slice& msg2);
  static const char* CopyState(const char* s);

  // OK status has a null state_.  Otherwise, state_ is a new[] array
  // of the following form:
  //    state_[0..3] == length of message
  //    state_[4]    == code
  //    state_[5..]  == message
  const char* state_;
};

根据注释和源码可以看出，Status 的具体状态由枚举类型 Status::Code 定义，包括 1 种正确状态和 5 种错误状态。state_ 成员格式在注释中已经指明：前 4 个字节表示 message 字符串长度；第 5 个字节表示 Code ；后续字节表示 message 字符串。

由于 Status 类需要管理 state_ 成员进行内存的分配和回收，代码中也显式重写了拷贝构造、拷贝赋值、移动构造等拷贝控制相关函数。

另外，Status 类提供了静态方法，用于创建不同类型的错误状态；以及 ToString 方法，用于将 Status 对象转换为可读的字符串。

7. 总结

以上就是 LevelDB 源码阅读系列的第一篇，介绍了最基础的一些头文件和数据结构。从上面的相关代码中，个人体会比较深刻的有两点：

• 良好的设计一定要封装隔离变化

  这一点可以从上文的很多地方看出，比如：

  • export.h 头文件通过宏应对编译环境（GNU or MSVC）的变化；
  • thread_annotations.h 头文件通过自定义宏，将 clang 的特性封装在一个源文件中，而不是扩散到整个项目的代码中；
  • port.h 头文件通过宏进行条件编译，隔离 LevelDB 其余部分代码依赖的平台相关接口，同时允许不同平台的不同实现，如利用 C++ 标准库的 port_stdcxx.h 头文件。

  实际上，LevelDB 中利用这一思想进行设计与实现的例子还有很多，后面遇到时也会再进行介绍。

  上面的相关代码似乎只是对部分接口进行了简单的封装，但是却蕴含了很深刻的软件设计、设计模型相关的思想。这里，本人作为设计模式学习新手，也只能稍微体会到这么一丢丢。于是，我问了 ChatGPT 一个问题：

  良好的设计一定要封装隔离变化 这一点可以从上文的很多地方看出，比如：

  • export.h 头文件通过宏应对编译环境（GNU or MSVC）的变化

  • thread_annotations.h 头文件通过自定义宏，将 clang 的特性封装在一个源文件中，而不是扩散到整个项目的代码中；

  • port.h 头文件通过宏进行条件编译，隔离 LevelDB 其余部分代码依赖的平台相关接口，同时允许不同平台的不同实现，如利用 C++ 标准库的 port_stdcxx.h 头文件。

    上面内容符合设计模式中哪些原则和具体的设计模式？

  下面是 ChatGPT 的回答，个人认为没有大问题，供读者参考：

  上面的内容符合多个设计原则和具体的设计模式，主要包括单一职责原则（SRP）、开闭原则（OCP）、依赖倒置原则（DIP） 以及适配器模式（Adapter Pattern）和策略模式（Strategy Pattern）。

  设计原则

  1. 单一职责原则（SRP）
     • 每个模块或类应该只有一个改变的原因，即它们应该只有一个职责。通过使用不同的头文件来处理不同的功能，代码更加模块化和可维护。
     • 例如，thread_annotations.h 只负责封装线程安全注释的逻辑，export.h 只负责处理编译环境的差异，port.h 负责隔离平台相关的接口。
  2. 开闭原则（OCP）
     • 软件实体（类、模块、函数等）应该可以扩展，但是不应该修改。通过使用宏和条件编译来处理不同的平台和编译器特性，可以扩展支持新的平台或编译器，而无需修改现有代码。
     • 例如，export.h 和 port.h 通过宏来应对不同编译器和平台的变化，使得代码可以在新增平台和编译器时通过增加新的宏定义来适应，而不是修改已有代码。
  3. 依赖倒置原则（DIP）
     • 高层模块不应该依赖低层模块，两者都应该依赖于抽象；抽象不应该依赖细节，细节应该依赖抽象。通过头文件和宏进行封装，实现了不同平台和编译器的隔离，使得高层代码无需直接依赖底层实现细节。
     • 例如，port.h 通过条件编译隔离了平台相关的实现，使得高层的 LevelDB 代码不直接依赖于特定平台的实现细节。

  设计模式

  1. 适配器模式（Adapter Pattern）
     • 适配器模式使得原本由于接口不兼容而不能一起工作的类可以一起工作。通过使用宏和条件编译，将不同平台和编译器特性适配为统一的接口。
     • 例如，export.h 通过宏适配不同编译器的导出符号语法，thread_annotations.h 将 Clang 特定的线程安全注释适配为统一的宏接口。
  2. 策略模式（Strategy Pattern）
     • 策略模式定义了一系列算法，并将每一个算法封装起来，使它们可以互换。本质上是将行为抽象出来，使得可以动态地选择不同的行为实现。
     • 例如，port.h 通过条件编译选择不同的平台实现（如使用 port_stdcxx.h），这种方式允许在不同平台上动态选择不同的实现策略，而不改变客户端代码。

  具体示例解释

  • export.h 头文件通过宏应对编译环境（GNU or MSVC）的变化：
    • 设计模式：适配器模式
    • 设计原则：开闭原则、单一职责原则
    • 通过定义宏来适配不同的编译器，实现了对不同编译环境的封装和隔离。
  • thread_annotations.h 头文件通过自定义宏，将 clang 的特性封装在一个源文件中：
    • 设计模式：适配器模式
    • 设计原则：单一职责原则、开闭原则
    • 将 Clang 的线程安全注释功能封装成统一的宏接口，使得整个项目可以方便地使用这些特性而无需关注编译器的具体实现。
  • port.h 头文件通过宏进行条件编译，隔离 LevelDB 其余部分代码依赖的平台相关接口：
    • 设计模式：策略模式
    • 设计原则：依赖倒置原则、开闭原则、单一职责原则
    • 通过条件编译选择不同的平台实现，使得代码可以在不同平台上运行而无需修改高层代码，实现了对平台差异的封装和隔离。

  总结

  上述设计符合良好的设计原则和模式，通过封装和隔离变化，增强了代码的可维护性、可扩展性和可移植性。这种设计不仅使得代码更易于理解和修改，还能够更好地应对未来的变化。

• 知名的项目也并非完美无缺

  LevelDB 使用的 C++ 标准是 C++ 11。在 C++ 11 中，enum class 语法已经得到了支持，它解决了原有的 enum 作用域泄漏的问题。在 status.h 源文件中，Code 相关代码如下：

  enum Code {
      kOk = 0,
      kNotFound = 1,
      kCorruption = 2,
      kNotSupported = 3,
      kInvalidArgument = 4,
      kIOError = 5
  };

  显然，这里使用 enum class Code{...}; 更合适，因为它能避免作用域泄漏、隐式类型转换等问题。而 LevelDB 却并没有使用新的 C++ 11 标准。或许当时的编译器还不支持；或许 LevelDB 的作者认为没有必要。其中原因，作为普通使用者很难揣测。不过，这一点已经足够证明：知名的项目也并非完美无缺。阅读开源项目源码是学习进步的必不可少的途径，但是完全信奉知名项目的代码，而没有自己的思考和判断，则显然是本末倒置了。这也和：尽信书，不如无书 是一个道理。

  愿我们带着自己的思考和判断，阅读源码，即使是知名项目的源码。以此共勉。