leveldb代码阅读（一）

2024-04-02 09:46:34

leveldb是一个由谷歌开源的高效的单机key-value存储系统，该系统提供了key到value的有序映射，现有的主流的kv存储系统有很多基于或者借鉴了leveldb的思想。主体代码大约1w行。基于 LSM(LOG Structured Merge Tree) 实现，将所有的 Key/Value 按照 Key 的词法序有序地储存在文件中，具有很高的随机/顺序写性能，非常适用于写多读少的环境。

DBImpl是leveldb数据库的结构体，一个DBImpl就是一个数据库，DBImpl的结构体在db_impl.h中。DBImpl和DB是友元类（friend class），DB可以直接访问DBImpl中的私有成员和保护成员，DB类是leveldb的对外接口。DBImpl中主要的成员主要有：

  port::Mutex mutex_; 
  MemTable* mem_;
  MemTable* imm_ GUARDED_BY(mutex_);  // Memtable being compacted
  WritableFile* logfile_;
  log::Writer* log_;
  // Queue of writers.
  std::deque<Writer*> writers_ GUARDED_BY(mutex_);
  SnapshotList snapshots_ GUARDED_BY(mutex_);

上图简单展示了 LevelDB 的整体架构。

MemTable：内存数据结构，具体实现是 SkipList。接受用户的读写请求，新的数据会先在这里写入。
Immutable MemTable：当 MemTable 的大小达到设定的阈值后，会被转换成 Immutable MemTable，只接受读操作，不再接受写操作，然后由后台线程 flush 到磁盘上 —— 这个过程称为 minor compaction。
Log：数据写入 MemTable 之前会先写日志，用于防止宕机导致 MemTable 的数据丢失。一个日志文件对应到一个 MemTable。
SSTable：Sorted String Table。分为 level-0 到 level-n 多层，每一层包含多个 SSTable，文件内数据有序。除了 level-0 之外，每一层内部的 SSTable 的 key 范围都不相交。
Manifest：Manifest 文件中记录 SSTable 在不同 level 的信息，包括每一层由哪些 SSTable，每个 SSTable 的文件大小、最大 key、最小 key 等信息。
Current：重启时，LevelDB 会重新生成 Manifest，所以 Manifest 文件可能同时存在多个，Current 记录的是当前使用的 Manifest 文件名。
TableCache：TableCache 用于缓存 SSTable 的文件描述符、索引和 filter。
BlockCache：SSTable 的数据是被组织成一个个 block。BlockCache 用于缓存这些 block（解压后）的数据。

首先我们会把数据写入memtable(位于内存中)，当memtable满了之后。就会变成immutable memtable。也就是所谓的冷却状态，这个时候的memtable无法再被写入数据。在immutable memtable中的数据会准备写入SST(磁盘)中。

C++多线程读写问题

如果不使用任何同步机制（例如mutex或atomic），在多线程中读写同一个变量，那么程序的结果是难以预料的。编译器和CPU的行为会影响到程序执行的结果：

C++不保证一条没有任何机制的语句是原子操作，其他线程可能看见指令执行的中间结果
为了优化程序执行性能，CPU可能会调整指令的执行顺序（如果两条指令不互相依赖）

如果CPU没有乱序执行指令，那么Thread-2将输出100，然而，对于Thread-1来说，x=100和y=200两个语句之间没有依赖关系，CPU可能调整两者的执行顺序，Thread-2将输出0或者100。

在CPU cache的影响下，一个CPU执行了某个指令，不会立即被其他CPU看见。

尽管A可能先于B执行，但CPU cache的影响下，Thread-2不能保证立即看到A执行的结果，所以Thread-2可能输出0或者100。

std::atomic

C++中对共享数据的存取在并法条件下可能引发data race的行为，需要限制并发程序以某种特定的顺序执行，有两种方式，使用mutex保护共享数据，或者原子操作，针对原子类型的操作要么一步完成，要么不完成，不会在中途切换cpu，这样可以防止多线程指令交叉执行带来的可能错误。非原子操作下，某个线程可能看见的是其他线程未操作完成的数据。

atomic头文件声明了两个C++类，atomic和atomic_flag。

https://www.jianshu.com/p/8c1bb012d5f8

C++中的memory order

memory order解决的是多线程读写中的问题2，是单个线程中的操作造成多线程出现的问题。为了解决2中重排造成的问题，C++中有6种可以应用于原子变量的内存次序。（思考：memory fence保证的是执行的顺序，但是这并不能解决问题3中cache产生的问题：cache刷新的顺序没有受到约束）

举例如下。这种写法可以让data=42先于flag=true执行，让while循环先于assert执行。

#include <atomic>
 
std::atomic<int> data;
std::atomic<bool> flag;
 
void thread1() {
    data.store(42, std::memory_order_relaxed);
    flag.store(true, std::memory_order_release);
}
 
void thread2() {
    while (!flag.load(std::memory_order_acquire)) {
    }
    assert(data.load(std::memory_order_relaxed) == 42);
}

Slice切片

Slice类中有两个成员，data_和size_，前者是数据，后者是大小。

关于C++11默认的拷贝构造和拷贝赋值#

default拷贝构造函数是浅拷贝

需要注意的是两个slice比较大小的函数。只比较共同长度的那一部分，如果那一部分相同，那么谁长谁大。例如，“123”<"23"

SkipList跳表

SkipList 是平衡树的一种替代数据结构，但是和红黑树不相同的是，SkipList 对于树的平衡的实现是基于一种随机化的算法的，这样也就是说 SkipList 的插入和删除的工作是比较简单的。SkipList 不仅是维护有序数据的一个简单实现，而且相比较平衡树来说，在插入数据的时候可以避免频繁的树节点调整操作，所以写入效率是很高的，LevelDB 整体而言是个高写入系统，SkipList 在其中应该也起到了很重要的作用。Redis 为了加快插入操作，也使用了 SkipList 来作为内部实现数据结构。leveldb中的跳表是线程安全的，写数据要加锁，读数据不需要加锁，只要保证跳表不会在读的过程中被销毁。

声明新的node的时候，是一个node加一个next_数组大小，Node类中成员的排列是连续的。next_数组存储了各层的后继节点，next_数组的长度取决于生成节点时跳表的高度height，node类中有一个私有成员next_[1]，用Node*数组来代替Node**，实际上就是个指针。

Arena内存池

使用了单链表的内存池。用blocks数组管理已经分配出去的内存块。回收内存的时候将其逐一回收。（todo:为什么使用array delete，为什么没有对remaining内存回收？）

需要注意的是采取了内存对齐的措施。

Memtable/Immutable Memtable

memtable的主要功能是将内部编码、内存分配（arena）和SkipList封装在一起，提供了将 KV 数据写入，删除以及读取 KV 记录的操作接口，但是事实上 Memtable 并不存在真正的删除操作，删除某个 key 的 value 在 Memtable 内是作为插入一条记录实施的，但是会打上一个 key 的删除标记（tag的ValueType置为kTypeDeletion），真正的删除操作是 Lazy 的，会在以后的 Compaction 过程中去掉这个 KV。

memtable使用了引用计数，维护了一个refs_变量。每次调用Ref()，引用计数++，调用unref()，引用计数--，若引用计数为0，则delete此对象。

memtable中定义了两个友元类：memtableIterator和memtableBackWardIterator。定义了自己的内存池、比较器和跳表。

memtable中有两个主要的函数：Add和Get。

memtable中的数据用编码之后的格式存储，其中sequence是序列号（快照是根据sequence生成的），type标志着这条entry是否被删除。

Log

//todo：

SSTable

// todo:

VersionSet, Version, VersionEdit

Version保存当前磁盘以及内存中的文件信息，一般只有一个version为”current version”。同时还保存了一系列的历史version，这些version的存在是因为有读操作还在引用（iterator和get，Compaction操作后会产生新的version作为current version
VersionSet就是一系列Version的集合
VersionEdit表示Version之间的变化，表示增加了多少文件，删除了多少文件

Snapshot

快照提供了一个当前KV存储的一个可读视图，使得读取操作不受写操作影响，可以在读操作过程中始终看到一致的数据
一个快照对应当前存储的最新数据版本号

写操作

Put操作会将(key,value)转化成writebatch后，通过write接口来完成
在write之前需要通过MakeRoomForWrite来保证MemTable有空间来接受write请求，这个过程中可能阻塞写请求，以及进行compaction。
BuildBatchGroup就是尽可能的将多个writebatch合并在一起然后写下去，能够提升吞吐量
AddRecord就是在写入MemTable之前,现在操作写入到log文件中
最后WriteBatchInternal::InsertInto会将数据写入到MemTable中

读操作

首先判断options.snapshot是否为空，如果为不为空，快照值就取这个值，否则取最新数据的版本号
然后依次尝试去MemTable, Immutable MemTable, VersionSet中去查找。VersionSet中的查找流程:
1. 逐层查找，确定key可能所在的文件
2. 然后根据文件编号,在TableCache中查找，如果未命中，会将Table信息Load到cache中
3. 根据Table信息，确定key可能所在的Block
4. 在BlockCache中查找Block，如果未命中，会将Block load到Cache中。然后在Block内查找key是否命中
更新读数据的统计信息，作为一根文件是否应该进行Compaction的依据，后面讲述Compaction时会说明
最后释放对Memtable，Immutable MemTable，VersionSet的引用

设计模式

memtabe的写入过程从WriteBatchInternal::InsertInto()函数开始。模式很奇怪，定义了memTableInserter的handler，用iterate的方式处理？

tips：

用统一的status类作为open、write、get等函数的返回值，以此查看执行是否成功。如果是get等需要执行结果数据的函数，用一个地址传参作为承接。

【参考】
https://developer.aliyun.com/article/618109

https://blog.csdn.net/sjc2870/article/details/112342573

码农公寓