Leveldb 源码分析 01: 基本元素

Table of Contents

开始前的准备
#

阅读 leveldb 源码的动机
#

每个人阅读 leveldb 的目标都不相同，我阅读 leveldb 的目标主要是

学习和感悟工业级的 C++ 代码如何编写的，学习神牛的编码习惯
学习和理解工业级 LSMT 存储引擎的设计、实现、取舍 ps. Rocksdb 虽好，但代码比较庞大且不易读（例如很多方法几十个参数）
后续对 leveldb 进行二次开发
portable to rust，并且增加一些改进

ps. 这是我 2022 年开始的目标, 目前还在进行中，后续会更新到 blog 中

需要哪些基础和前提
#

良好的数据结构和算法基础
良好的操作系统基础
3年左右编程经验，对 C++ 熟悉最好 1 年左右

环境配置
#

clone leveldb 源码

git clone https://github.com/google/leveldb.git && cd leveldb
git submodule update --init

编译

mkdir build && cd build

cmake -DCMAKE_BUILD_TYPE=Debug -DCMAKE_EXPORT_COMPILE_COMMANDS=1 -DLEVELDB_BUILD_BENCHMARKS=ON -DLEVELDB_BUILD_TESTS=ON -DLEVELDB_EXAMPLE=ON ..

make

提示缺少依赖搜索安装

配置 debug
#

在 examples/exam_01 是一个可以运行的测试程序，我们可以基于此进行 debug 并分析源码.

![[Pasted image 20230625235401.png]]

vscode debug 配置为

// .vscode/launch.json
{
    // Use IntelliSense to learn about possible attributes.
    // Hover to view descriptions of existing attributes.
    // For more information, visit: https://go.microsoft.com/fwlink/?linkid=830387
    "version": "0.2.0",
    "configurations": [
        {
            "name": "Launch example-01",
            "type": "cppdbg",
            "request": "launch",
            "program": "${workspaceFolder}/build/examples/exam_01",
            "args": [
                "/tmp/exam_01", // 配置db路径
            ],
            "cwd": "${workspaceFolder}",
            "environment": [],
            "externalConsole": false,
            "MIMode": "gdb", // 如果是 macos, 请替换为 lldb
            "stopAtEntry": false,
            "setupCommands": [
                {
                    "description": "为 gdb 启用整齐打印",
                    "text": "-enable-pretty-printing",
                    "ignoreFailures": true
                },
                {
                    "description": "将反汇编风格设置为 Intel",
                    "text": "-gdb-set disassembly-flavor intel",
                    "ignoreFailures": true
                }
            ]
        }
    ]
}

leveldbutil 工具介绍和使用
#

leveldbutil 提供了一个 dump 命令用来解码 leveldb 生成的数据库文件。例如下面是 /tmp/exam_01 测试代码生成的数据的目录结构

# tree /tmp/exam_01/
/tmp/exam_01/
├── 000003.log # 可以 dump
├── CURRENT
├── LOCK
├── LOG
└── MANIFEST-000002 # 可以 dump

dump manifest 版本控制文件

# ./build/leveldbutil dump /tmp/exam_01/MANIFEST-000002
--- offset 0; VersionEdit {
  Comparator: leveldb.BytewiseComparator
}
--- offset 35; VersionEdit {
  LogNumber: 3
  PrevLogNumber: 0
  NextFile: 4
  LastSeq: 0
}

dump log 数据文件

# ./build/leveldbutil dump /tmp/exam_01/000003.log 
--- offset 0; sequence 1
  put 'key1' 'value1'
--- offset 32; sequence 2
  put 'key2' 'value2'
--- offset 64; sequence 3
  put 'key3' 'value3'
--- offset 96; sequence 4
  put 'key4' 'value4'
--- offset 128; sequence 5
  put 'key5' 'value5'
--- offset 160; sequence 6
  put 'key6' 'value6'
--- offset 192; sequence 7
  put 'key7' 'value7'
--- offset 224; sequence 8
  put 'key8' 'value8'
--- offset 256; sequence 9
  put 'key9' 'value9'
--- offset 288; sequence 10
  put 'key10' 'value10

基本构建块
#

leveldb 自己实现了一些工具类和数据结构等代码。这些代码广泛在 leveldb 各处使用，因此提前了解，在主干代码中不再深入这部分的细节。

Slice 数据结构
#

Slice 包装了字符串指针 char * , 并提供了一些常用的功能函数和操作符重载. 定义在命名空间 leveldb 内.

Slice 数据布局

namespace leveldb {

class LEVELDB_EXPORT Slice {
 private:
  const char* data_;
  size_t size_;
}

Slice 提供了以下操作

构造函数：
- Slice()：创建一个空的 Slice 对象，将数据指针 data_ 设置为空字符串，大小 size_ 设置为0。
- Slice(const char* d, size_t n)：创建一个 Slice 对象，引用以字符指针 d 开始的 n 个字符的数据。
- Slice(const std::string& s)：创建一个 Slice 对象，引用 std::string 对象 s 的数据。
- Slice(const char* s)：创建一个 Slice 对象，引用以字符指针 s 开始的以 null 结尾的字符串的数据。
数据访问函数：
- data()：返回对数据的指针。
- size()：返回数据的大小（以字节为单位）。
- empty()：检查数据的大小是否为零。
- operator[]()：返回数据中第 n 个字节的值。
修改函数：
- clear()：将 Slice 对象重置为空，将数据指针 data_ 设置为空字符串，大小 size_ 设置为0。
- remove_prefix(size_t n)：从 Slice 对象中删除前面的 n 个字节。
辅助函数：
- ToString()：返回一个包含 Slice 对象引用的数据副本的 std::string 对象。
- compare()：进行三向比较，返回比较结果。
操作符重载：
- operator==()：比较两个 Slice 对象是否相等。
- operator!=()：比较两个 Slice 对象是否不相等。

Status 数据结构
#

锁抽象
#

leveldb 是一个并发系统，因此对底层的锁进行了封装和抽象，提供了

Mutex 和 MutexLock
CondVar

由于 leveldb 使用 C++11 标准库的底层类，因此锁是跨平台的。

leveldb 的锁抽象是一个很典雅的编码方式，实际上我们应该学习 leveldb 这种方式，不应该直接使用操作系统提供的锁系统调用。

Mutex 和 MutexLock
#

Mutex 包装了 std::mutex. Mutex 数据布局

class LOCKABLE Mutex {
 private:
  friend class CondVar;
  std::mutex mu_;
};

Mutex 类定义了

默认构造函数 Mutex()
默认析构函数 ~Mutex()
复制构造函数和赋值运算符：将复制构造函数和赋值运算符声明为 delete，禁止复制和赋值操作，确保 Mutex 对象不被复制。
Lock() 函数：获取互斥锁的所有权，阻塞其他线程对互斥锁的访问。通过调用 mu_.lock() 实现。
Unlock() 函数：释放互斥锁的所有权，允许其他线程对互斥锁进行访问。通过调用 mu_.unlock() 实现。
AssertHeld() 函数：断言当前线程持有互斥锁。这是一个空函数，用于在调试期间验证互斥锁的持有状态。

Mutex 作为底层的锁，被上层的更高层次抽象的锁和条件变量持有。

MutexLock 是一个采用 RAII 手法封装 Mutex 的更高层的抽象, 数据布局为

class SCOPED_LOCKABLE MutexLock {
 private:
  port::Mutex* const mu_;
};

MutexLock 类定义了

构造函数 MutexLock(port::Mutex* mu) 接收一个 Mutex 对象, 并调用 Mutex.Lock 加锁
析构函数调用 Mutex.Unlock 解锁
复制构造函数和赋值运算符：将复制构造函数和赋值运算符声明为 delete，禁止复制和赋值操作。

CondVar
#

CondVar 类是对标准库中的 std::condition_variable 进行了简单的封装. 数据布局为

class CondVar {
 private:
  std::condition_variable cv_;
  Mutex* const mu_;
};

CondVar 类定义了

构造函数 CondVar(Mutex* mu)：接受一个指向 Mutex 对象的指针作为参数，用于初始化条件变量对象。构造函数使用 assert 断言确保传入的 Mutex 指针不为空。
析构函数 ~CondVar()：使用默认的析构函数。
复制构造函数和赋值运算符：将复制构造函数和赋值运算符声明为 delete，禁止复制和赋值操作，确保条件变量对象不被复制。
Wait() 函数：等待条件变量满足某个条件。首先对互斥锁进行上锁，并将锁的所有权转移给 std::unique_lock 对象，确保互斥锁在等待期间不会被其他线程访问。然后调用 cv_.wait(lock)，该语句会释放互斥锁并使当前线程等待，直到接收到通知并重新获得互斥锁。最后通过调用 lock.release() 释放互斥锁的所有权，从而使互斥锁回到原来的所有者。
Signal() 函数：向一个等待中的线程发送信号，唤醒其中的一个线程。通过调用 cv_.notify_one() 实现。
SignalAll() 函数：向所有等待中的线程发送信号，唤醒它们。通过调用 cv_.notify_all() 实现。