对于leveldb源码学习一我们主要是去了解了接口有哪些接口的功能是什么也大致明白了他的架构是什么样子这篇主要是去探究那些接口是怎么写的是如何实现的由于每一个接口代码量太多我只会写出比较关键的部分。我们第一个要探究的就是put是怎么实现的1.db_impl.cc一句话db_impl.cc实现了 LevelDB 的真正数据库对象DBImpl负责打开数据库、恢复日志、读写 MemTable、生成 SSTable、调度 Compaction、清理旧文件、管理 Snapshot 和 Iterator。你可以把 LevelDB 分成两层对外接口层 DB、Options、ReadOptions、WriteOptions、WriteBatch 内部实现层 DBImpl、MemTable、Log、VersionSet、TableCache、Compaction其中DBImpl是内部实现层的总控制器。前面db.h里有class DB { public: virtual Status Put(...) 0; virtual Status Get(...) 0; virtual Status Write(...) 0; };而DBImpl就是真正继承DB并实现这些函数的类。所以DB 是接口。 DBImpl 是实现。2.DBImpl::Writer结构体struct DBImpl::Writer {explicit Writer(port::Mutex* mu): batch(nullptr), sync(false), done(false), cv(mu) {}Status status;WriteBatch* batch;bool sync;bool done;port::CondVar cv;};首先是结构体他的目的是表示一个正在等待写入数据库的写请求其中每个参数的意思是status这次写入最后的结果batch这次要写入的一批操作sync这次写入是否要求刷盘done这次写入是否完成cv条件变量用来睡眠和唤醒等待线程这个设计非常重要。LevelDB 不是每个线程来了都自己抢着写 WAL 和 MemTable。它会把写请求排成队列writers_ 队列 Writer1 - Writer2 - Writer3 - ...然后队头线程负责真正写入。这和很多数据库里的“写入串行化”思想类似。3.为什么写入要排队因为 LevelDB 写入时要维护一些全局顺序SequenceNumber WAL log 顺序 MemTable 插入顺序数据库不能让多个线程乱序写。比如两个线程同时写线程 APut key v1 线程 BPut key v2LevelDB 必须给它们一个明确顺序先 A 后 B最终 key v2或者先 B 后 A最终 key v1不能乱。所以Writer队列就是为了保证写入顺序。这和 MySQL 里 redo log、事务提交顺序也有相似思想。4.SanitizeOptions允许用户去修改配置但是修改的配置会按照要求在一定的范围之类5.DBImpl构造函数把数据库内部组件组装起来你看到DBImpl::DBImpl(const Options raw_options, const std::string dbname) : env_(raw_options.env), internal_comparator_(raw_options.comparator), internal_filter_policy_(raw_options.filter_policy), options_(SanitizeOptions(...)), table_cache_(new TableCache(...)), mem_(nullptr), imm_(nullptr), logfile_(nullptr), log_(nullptr), tmp_batch_(new WriteBatch), versions_(new VersionSet(...)) {}这就是在初始化数据库内部组件。几个重点成员env_ 操作系统环境负责文件读写、锁、后台线程等。 internal_comparator_ 内部 key 比较器。 options_ 修正后的配置。 table_cache_ SSTable 文件缓存。 mem_ 当前正在写入的 MemTable。 imm_ 已经写满、等待刷盘的 Immutable MemTable。 logfile_ / log_ 当前 WAL 日志文件。 tmp_batch_ 临时 WriteBatch用于合并多个写请求。 versions_ 管理所有 SSTable 文件版本信息。你可以这样理解DBImpl 构造函数 把 LevelDB 运行需要的核心零件装起来。6. 析构函数关闭数据库前等后台任务结束代码里DBImpl::~DBImpl() { mutex_.Lock(); shutting_down_.store(true, std::memory_order_release); while (background_compaction_scheduled_) { background_work_finished_signal_.Wait(); } mutex_.Unlock(); ... }意思是数据库对象销毁时要先通知后台任务停止并等待正在运行的后台 Compaction 完成。为什么因为如果数据库正在后台压缩文件你直接销毁对象就可能出现后台线程还在用 mem_ 后台线程还在写 SSTable 后台线程还在访问 versions_ 主线程已经 delete 掉了这些对象这就是典型的并发资源悬空问题。所以析构时必须先停止后台任务 再释放资源这和 MySQL/Redis 关闭服务时要先停止后台线程、刷盘、释放文件句柄是同一种思想。7.NewDB()创建一个全新的数据库代码里Status DBImpl::NewDB() { VersionEdit new_db; new_db.SetComparatorName(user_comparator()-Name()); new_db.SetLogNumber(0); new_db.SetNextFile(2); new_db.SetLastSequence(0); const std::string manifest DescriptorFileName(dbname_, 1); ... }这个函数是在数据库不存在时创建新库。它主要做几件事1. 创建 VersionEdit记录新数据库的元信息 2. 创建 MANIFEST 文件 3. 把数据库初始状态写入 MANIFEST 4. 创建 CURRENT 文件让 CURRENT 指向当前 MANIFEST这里的几个概念很重要MANIFEST 记录数据库当前有哪些 SSTable、每个文件在哪一层、key 范围是什么。 CURRENT 一个很小的文件里面写着当前应该使用哪个 MANIFEST。你可以类比 MySQLSSTable 文件 真正的数据文件 MANIFEST 数据文件元信息目录 CURRENT 指向当前元信息文件的指针8.Recover()数据库打开时恢复状态这是非常核心的函数Status DBImpl::Recover(VersionEdit* edit, bool* save_manifest)它在DB::Open里面被调用。作用是打开数据库时根据 CURRENT、MANIFEST、WAL 日志把数据库恢复到正确状态。它大概做这些事1. 创建数据库目录 2. 加数据库锁防止多个进程同时打开 3. 如果数据库不存在根据 create_if_missing 决定是否创建 4. 如果数据库存在根据 error_if_exists 决定是否报错 5. 从 MANIFEST 恢复已有 SSTable 版本信息 6. 找出需要恢复的 log 文件 7. 按日志编号顺序重放 WAL 8. 更新 LastSequence这就是数据库的 crash recovery。和 MySQL 的崩溃恢复非常像LevelDB读取 WAL log恢复 MemTable / SSTable 状态 MySQL读取 redo log恢复 Buffer Pool / 数据页状态 Redis读取 AOF重放命令恢复内存状态共同思想是磁盘上的数据文件可能不是最新状态。 所以打开数据库时要根据日志把最近操作补回来。9.RecoverLogFile()重放 WAL 日志这个函数更具体Status DBImpl::RecoverLogFile(...)它做的事情是打开某个 log 文件 一条一条读取 log record 把 record 解析成 WriteBatch 把 WriteBatch 插入 MemTable 如果 MemTable 太大就写成 Level-0 SSTable代码里有WriteBatchInternal::SetContents(batch, record); status WriteBatchInternal::InsertInto(batch, mem);意思是log record 里面保存的是 WriteBatch 的编码内容。 恢复时把它还原成 batch再插入 MemTable。这也说明了你前面学的WriteBatch为什么重要LevelDB 的 WAL 日志里记录的本质上就是 WriteBatch。写入时WriteBatch - WAL WriteBatch - MemTable恢复时WAL - WriteBatch - MemTable这个设计很统一。10.WriteLevel0Table()把 MemTable 写成 SSTable代码里Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base)这个函数的作用是把一个 MemTable 里的内容写成磁盘上的 SSTable 文件。流程大概是1. 给新 SSTable 分配 file number 2. 从 MemTable 创建 Iterator 3. 调用 BuildTable 生成 SSTable 文件 4. 记录这个文件的 smallest key 和 largest key 5. 把新文件加入 VersionEdit 6. 记录 compaction 统计信息这就是 LevelDB 从内存到磁盘的关键步骤。写入路径可以这样理解Put/Delete | WAL | MemTable | MemTable 满 | Immutable MemTable | WriteLevel0Table | Level-0 SSTable也就是说WriteLevel0Table是内存数据变成磁盘有序文件的地方。11.CompactMemTable()压缩 immutable MemTable代码里void DBImpl::CompactMemTable()作用是把已经写满的 immutable MemTable 刷成 SSTable并更新 MANIFEST。重点流程1. 调用 WriteLevel0Table把 imm_ 写成 Level-0 SSTable 2. 创建 VersionEdit 3. 写入 MANIFEST记录新文件 4. 释放 imm_ 5. 删除过期文件这里要注意写 SSTable 成功还不够。 还必须更新 MANIFEST。否则数据库下次打开时不知道这个新 SSTable 是有效数据文件。所以 LevelDB 里很多操作都不是只写数据文件还要写元数据。这和 MySQL 里数据页、redo、元信息保持一致是一个思想。12、MaybeScheduleCompaction()1. 函数作用MaybeScheduleCompaction()直译或许可以调度一次压缩它不是直接执行合并压缩只做一件事判断现在要不要启动后台压缩任务。它会依次判断一堆条件有任意一条不满足就不触发后台压缩已有后台压缩正在跑不能重复开避免磁盘 IO 打满数据库正在关闭停止一切后台任务之前后台任务出过致命错误不再调度存在 immutable memtable内存表满了必须刷盘合并用户手动触发了压缩当前版本 Version 检测到 SST 文件层数超限、文件过多需要合并。只要满足「需要压缩」且所有前置放行条件就执行cpp运行env_-Schedule(DBImpl::BGWork, this);2.env_-Schedule(任务函数, 对象)是什么Env是 LevelDB 封装的操作系统环境层里面自带线程池 / 后台工作线程Schedule 往后台线程池丢一个异步任务DBImpl::BGWork是后台真正执行 compaction、刷 imm 表的函数this是当前 DB 实例后台函数拿到数据库指针去做合并。关键点前台用户写请求线程不会阻塞在这里做繁重压缩。 Schedule 只是把任务丢进队列立刻返回写操作马上响应客户端。3. 类比 MySQL、Redis 后台机制统一设计思想MySQL 例子前台执行insert/update只是写内存缓冲池buffer pool不会同步刷磁盘脏页 刷脏页、undo/purge 清理、索引合并全部丢后台线程异步做。Redis 例子前台set只写内存 AOF 重写、RDB 持久化、过期 key 淘汰全部后台异步执行。LevelDB 同理前台db-Put()/WriteBatch只写内存 memtable快速返回 重活memtable 落地 L0、SST 分层合并、文件删除、空间回收全部交给后台线程执行。核心设计思想一句话解释前台线程只处理用户即时请求保证低延迟磁盘 IO、文件合并这类耗 CPU、耗磁盘的重量级整理工作全部丢到后台线程异步执行不阻塞用户读写。拆开两层好处提升前台读写速度降低延迟Compaction 需要大量磁盘读写、key 归并排序非常慢。 如果 Put 同步等待压缩完成每一次写入都会卡顿吞吐量暴跌。 丢后台后用户写完立刻返回感知不到耗时。统一管控后台负载避免 IO 风暴MaybeScheduleCompaction会检查是否已有后台任务在跑同一时间最多只有一次 compaction。 防止无限创建压缩线程导致磁盘被占满、业务卡死。故障隔离 后台压缩报错磁盘满、IO 错误不会直接崩溃前台写入只会标记后台错误后续调度时拦截。完整流程串联结合你之前学的 imm 刷 L0前台大量 Putmemtable 写满 → 切换成 imm_不可变内存表用户写完返回前台线程调用MaybeScheduleCompaction()函数判断有 imm_、无后台任务、数据库正常 → 调度 BGWork 后台任务后台线程异步执行WriteLevel0Table 把 imm_生成 L0 SST构建 VersionEdit、写入 MANIFEST 更新版本释放 imm 内存、清理过期 SST 文件前台全程不等待上面磁盘操作继续接收新的写入请求。通俗大白话总结就像餐厅前台服务员用户读写线程只负责接单、记菜单写内存 memtable快速接待客人后厨后台 BGWork 线程慢慢洗菜、做菜、整理库存compaction 文件合并、刷盘MaybeScheduleCompaction相当于领班判断后厨空着就安排备菜后厨忙就先不安排不让客人等。13.BackgroundCompaction()后台真正执行压缩代码里void DBImpl::BackgroundCompaction()这是 Compaction 的调度中心。它大概做这些事1. 如果 imm_ 不为空优先 compact MemTable 2. 如果是手动 compact就按用户指定范围选 compaction 3. 如果是自动 compact就让 versions_-PickCompaction() 4. 如果只是简单移动文件就直接从一层移动到下一层 5. 否则调用 DoCompactionWork 真正合并文件 6. 完成后清理旧文件这里说明 LevelDB 的 Compaction 分两类轻量情况 文件可以直接移动到下一层不需要重写。 重量情况 多个 SSTable 需要合并、过滤旧版本、生成新 SSTable。14.DoCompactionWork()真正合并 SSTable这是整个文件里最复杂、也最核心的函数之一Status DBImpl::DoCompactionWork(CompactionState* compact)它做的是读取参与 compaction 的多个 SSTable把它们合并成新的 SSTable并丢弃过期数据。这里最关键的是它会判断某条记录要不要 drop。代码里有两类丢弃逻辑1. 如果同一个 key 已经有更新版本旧版本可以丢 2. 如果删除标记已经没有必要保留也可以丢比如key - v1, seq10 key - v2, seq20如果没有快照需要看到 seq10那么 seq10 的旧版本就可以丢掉。再比如Delete key, seq30如果更低层已经没有这个 key 的旧数据了那么这个删除标记也可以丢掉。这就是 Compaction 真正的价值清理旧版本 清理删除标记 合并文件 降低读放大 降低空间浪费你之前问的 MySQL/Redis 类比这里也很像LevelDB Compaction 清理旧版本和 tombstone。 MySQL purge 清理 MVCC undo 旧版本。 Redis AOF rewrite 清理历史命令只保留最终状态。15.Get()LevelDB 的读取路径代码里Status DBImpl::Get(const ReadOptions options, const Slice key, std::string* value)这个函数就是用户调用db-Get(read_options, key, value);最终进入的地方。读取顺序非常重要1. 确定 snapshot sequence 2. 先查 mem_ 3. 再查 imm_ 4. 最后查当前 Version 里的 SSTable代码里也体现了if (mem-Get(lkey, value, s)) { // Done } else if (imm ! nullptr imm-Get(lkey, value, s)) { // Done } else { s current-Get(options, lkey, value, stats); }这就是 LevelDB 的读路径读最新内存表 | 读等待刷盘的内存表 | 读磁盘 SSTable这个顺序很好理解最新写入的数据一定先在 MemTable。 如果 MemTable 没有可能在 Immutable MemTable。 再没有才去磁盘文件里找。这和 Redis MySQL 类比也很自然先查快的地方。 找不到再查慢的地方。只不过 LevelDB 这里是在存储引擎内部完成。分步逐条解释1. 确定 snapshot sequence快照序列号LevelDB 每一次写入 (Put/Delete) 都会分配一个全局递增序列号SequenceNumber用来实现快照、隔离、MVCC。如果用户传入了自定义快照ReadOptions.snapshot就用快照对应的序列号没指定快照就用数据库当前最新全局序列号。 作用查询时只读取 ≤ 当前序列号的数据屏蔽这条快照之后新增的数据保证快照一致性。2. 先查 mem_活跃内存表mem_当前正在接收写入的可变 MemTable最新的数据都存在这里。遍历 memtable 跳表查找 key如果找到判断这条记录的序列号 ≤ 快照序列号如果是 Put直接返回 value如果是 Delete墓碑代表 key 已被删除返回 “不存在”找到直接 return不会去查 imm 和 SST减少磁盘 IO。3. 再查 imm_不可变内存表当 mem_ 写满后会切换为imm_新数据写到新 mem_imm_ 等待后台线程刷成 L0 SST。 imm_ 里的数据比 mem_ 旧但比磁盘 SST 新。mem_ 没找到才会去查 imm_同样匹配 key 校验序列号命中直接返回。4. 最后查当前 Version 里的 SSTable磁盘文件内存两张表都没找到才走磁盘也就是Version管理的所有层级 SST 文件优先查 L0L0 文件 key 区间重叠需要逐个遍历匹配L1~Lmax每层有序不重叠通过二分快速定位最多一个 SST逐层从上到下查找上层更新下层更旧一旦在某个 SST 中找到 key校验序列号区分 Put/Delete返回结果全部 SST 遍历完都没有 → key 不存在。16.NewIterator()创建统一视图的迭代器代码里Iterator* DBImpl::NewIterator(const ReadOptions options)它会先调用NewInternalIterator(...)内部会收集多个迭代器mem_ iterator imm_ iterator SSTable iterators然后通过NewMergingIterator(...)把它们合并成一个有序迭代器。这很关键。因为 LevelDB 的数据分散在MemTable Immutable MemTable Level-0 SSTable Level-1 SSTable Level-2 SSTable ...但用户使用 Iterator 时不想关心这些。用户只想it-SeekToFirst(); it-Next();所以 LevelDB 内部要把多个来源合并成一个逻辑有序流。这和 MySQL 执行计划里把多个数据来源组合成一个结果集也有一点设计思想上的相似。17.GetSnapshot()/ReleaseSnapshot()快照管理代码里const Snapshot* DBImpl::GetSnapshot() { MutexLock l(mutex_); return snapshots_.New(versions_-LastSequence()); }意思是创建一个快照记录当前最新 sequence number。释放时void DBImpl::ReleaseSnapshot(const Snapshot* snapshot) { MutexLock l(mutex_); snapshots_.Delete(static_castconst SnapshotImpl*(snapshot)); }Snapshot 的本质不是复制一份完整数据库。它只是记录一个 sequence number。比如当前 LastSequence 100 GetSnapshot() 得到 snapshot(seq100)之后即使数据库继续写到 seq120这个 snapshot 读的时候仍然只看sequence 100 的数据这就是 LevelDB 的 MVCC 味道。和 MySQL 的 ReadView 很像MySQL ReadView 决定当前事务能看到哪些版本。 LevelDB Snapshot 决定当前读取能看到哪些 sequence number。在这个里面有一个思考点就是为什么要上锁而前面的get则不用。首先MutexLock 是什么MutexLock l(mutex_);RAII 自动锁构造函数上锁mutex_.Lock()函数结束、对象销毁时自动解锁不会漏解锁。整个GetSnapshot()函数内所有共享变量访问都被同一把mutex_保护保证原子性读取最新序列号 创建快照并插入链表这两步作为一个不可分割的原子操作。其实答案就是get是只是去读但是GetSnapshot()在读取全局序列号时会对其进行修改共享的快照链表。如果更精确一点的话就是GetSnapshot()不修改全局序列号只是读取正在被并发修改的全局序列号同时修改共享快照链表这两步合起来必须加锁 而普通Get()只做纯查询不碰这两个临界资源所以不用这把锁。普通db-Get()读取路径只是只读遍历 mem/imm/SST不会修改快照链表、不会读写全局序列号 但GetSnapshot()要读取可变全局序列号 修改共享快照链表属于「读 修改临界区」必须加锁。不加锁会出现什么 bug读到损坏的序列号快照查询数据不一致快照链表并发插入导致链表结构损坏程序 crashCompaction 遍历快照链表时访问野指针崩溃重复创建重复序列号快照版本回收逻辑错乱。18.Write()最核心的写入路径这是整个文件最应该认真看的函数Status DBImpl::Write(const WriteOptions options, WriteBatch* updates)它是用户调用db-Put(...) db-Delete(...) db-Write(...)最终都会走到的地方。整体流程是1. 创建 Writer把本次写请求放入 writers_ 队列 2. 等自己成为队头 3. 调用 MakeRoomForWrite确保 MemTable 有空间 4. 调用 BuildBatchGroup把多个写请求合并成一个大 batch 5. 给 batch 设置 sequence number 6. 写入 WAL log 7. 如果 synctrue就 Sync 日志文件 8. 把 batch 插入 MemTable 9. 更新 LastSequence 10. 唤醒队列里已经一起完成的 writer在这个里面为什么需要等到队头才去执行是一个可以去思考的问题。「等自己成为队头」完整含义首先需要直到writers_ 是什么他是 DBImpl 内部一个等待写入的线程队列条件变量 链表。 多个业务线程同时调用db-Put()/db-Write()时每个线程都会封装成一个Writer对象塞进writers_排队。LevelDB 写入采用批量合并写group commit 不让每个写请求单独落盘、单独写 memtable而是队列头部一次性捞一批请求合并执行减少 WAL IO、锁竞争提升吞吐。1. 流程还原线程进来第一步封装自己为 Writerpush 进 writers_ 队列。 然后执行循环等待逻辑while (自己不是队列第一个元素) { 等待条件变量 cond_; }也就是只要当前线程的 Writer 不在队列头部就阻塞休眠不往下执行写逻辑。2. 为什么要等自己变成队头批量合并写的规则只有队头 Writer 才有资格真正执行写入流程。排在后面的所有 Writer 全部阻塞等待队头线程会一次性把自己 后面连续一批等待的 Writer 全部打包合并成一个大 Batch统一写 WAL、统一插入 MemTable、统一分配序列号一次性完成一批请求写完后批量唤醒这批等待的线程全部返回成功。举个场景 线程 1、2、3、4 同时并发写依次进入 writers_队列 队列顺序[W1, W2, W3, W4]W1 是队头不用等继续执行 MakeRoomForWrite、合并 BatchW2、W3、W4 发现自己不是队头全部阻塞休眠 W1 执行 BuildBatchGroup把 W1W2W3W4 全部合并成一个大 batch一次性写入 写完后唤醒 W2/W3/W4四个线程同时返回上层业务。3. 如果不等待、直接执行会怎么样每个线程都尝试去写 WAL、修改 memtable、更新全局序列号必然出现大量锁争抢频繁上下文切换每个请求单独刷 WAL磁盘 IO 爆炸性能暴跌序列号分配并发冲突必须加超大粒度锁并发直接退化串行。其次需要思考的是第六步与第七步有什么区别写入 WAL log只是把日志数据写入操作系统页缓存page cache数据现在在内存缓冲区还没真正落到磁盘硬件上写入速度极快只是内存拷贝此时如果机器突然断电、内核崩溃这份新写的 WAL 数据会直接丢失。synctrue 执行 Syncfsync/fdatasync---------------------------------------------------------------------------------------------------------------------------------强制把内核缓存里的 WAL 数据刷到磁盘持久化存储触发磁盘硬件 IO把缓存数据写入磁盘盘片完成 sync 之后就算断电数据也不会丢sync 很慢涉及磁盘物理写入开销大。这就是 LevelDB 写入的主干。可以画成用户 Put/Delete/Write | v Writer 入队 | v 成为队头 | v MakeRoomForWrite | v BuildBatchGroup 合并多个写 | v 写 WAL | v 写 MemTable | v 返回 Status这段代码非常体现数据库系统设计。19.BuildBatchGroup()合并多个写请求代码里WriteBatch* DBImpl::BuildBatchGroup(Writer** last_writer)这个函数做的是把写队列里连续的多个 Writer 合并成一个更大的 WriteBatch。为什么要合并因为每个写请求单独写 WAL 成本比较高。如果多个写请求排在队列里可以合并Writer1: Put A Writer2: Put B Writer3: Delete C变成一个大 batch: Put A Put B Delete C然后一次写 WAL一次插入 MemTable。这和 Redis pipeline、MySQL group commit 思想非常像多个小请求合并处理提高吞吐。但代码里也有两个限制1. batch 不能无限大 2. sync 写不能被非 sync 写带着一起处理因为如果 batch 太大小请求会被拖慢。所以它用了size_t max_size 1 20; if (size (128 10)) { max_size size (128 10); }意思大概是最多合并到 1MB。 如果第一个请求很小就不要合并太多避免小请求延迟太高。这就是吞吐和延迟之间的权衡。20.MakeRoomForWrite()写入前确保 MemTable 有空间代码里Status DBImpl::MakeRoomForWrite(bool force)这个函数负责写入前检查当前 MemTable 是否还能写如果不能就切换新的 MemTable并安排旧 MemTable 刷盘。它里面几个判断非常重要1. 如果有后台错误停止写入 2. 如果 Level-0 文件太多稍微延迟写入 3. 如果 MemTable 还有空间直接写 4. 如果 imm_ 还没 compact 完就等待 5. 如果 Level-0 文件多到危险程度就等待 6. 否则创建新 log把当前 mem_ 变成 imm_再创建新的 mem_这就是 LevelDB 的写入背压机制。什么叫背压就是当后台整理跟不上前台写入时前台写入不能无限冲。否则会出现Level-0 文件越来越多 读性能越来越差 Compaction 压力越来越大 磁盘越来越乱所以 LevelDB 会让写入慢下来甚至等待 compaction。这和 MySQL、Redis 都类似MySQL 脏页太多时前台写入可能变慢。 Redis AOF rewrite 或内存压力大时也可能影响请求延迟。数据库不是只追求“写得快”还要防止系统被写爆。21.DB::Put和DB::Delete的默认实现代码最后有Status DB::Put(const WriteOptions opt, const Slice key, const Slice value) { WriteBatch batch; batch.Put(key, value); return Write(opt, batch); } Status DB::Delete(const WriteOptions opt, const Slice key) { WriteBatch batch; batch.Delete(key); return Write(opt, batch); }这非常重要。它证明了我们前面说的单条 Put/Delete本质上也是一个只有一条操作的 WriteBatch。也就是说Put(key, value)等价于创建 WriteBatch batch.Put(key, value) db-Write(batch)所以 LevelDB 的写入核心其实只有一个DBImpl::Write(...)Put和Delete都只是便利函数。22.DB::Open()打开数据库入口代码里Status DB::Open(const Options options, const std::string dbname, DB** dbptr)这是用户真正调用的入口leveldb::DB* db; Status s leveldb::DB::Open(options, ./testdb, db);内部做这些事1. 创建 DBImpl 2. 加锁 3. 调用 Recover 恢复数据库 4. 如果恢复后还没有 mem_创建新的 log 和 MemTable 5. 如果需要保存新的 MANIFEST 6. 删除过期文件 7. 安排后台 compaction 8. 成功则把 impl 赋给 *dbptr 9. 失败则 delete impl这里你能看到DB和DBImpl的关系用户拿到的是 DB* 实际对象是 DBImpl*这就是典型的 C 多态DB* db new DBImpl(...);用户只看到接口内部实现隐藏起来。23.DestroyDB()删除整个数据库最后还有Status DestroyDB(const std::string dbname, const Options options)这个函数负责删除数据库目录下的 LevelDB 文件。它会1. 列出数据库目录下文件 2. 加数据库锁 3. 删除除 LOCK 外的数据库文件 4. 解锁 5. 删除 LOCK 文件 6. 尝试删除目录这个函数很危险。它不是删除一个 key而是删除整个数据库。
对于leveldb源码学习一我们主要是去了解了接口有哪些接口的功能是什么也大致明白了他的架构是什么样子这篇主要是去探究那些接口是怎么写的是如何实现的由于每一个接口代码量太多我只会写出比较关键的部分。我们第一个要探究的就是put是怎么实现的1.db_impl.cc一句话db_impl.cc实现了 LevelDB 的真正数据库对象DBImpl负责打开数据库、恢复日志、读写 MemTable、生成 SSTable、调度 Compaction、清理旧文件、管理 Snapshot 和 Iterator。你可以把 LevelDB 分成两层对外接口层 DB、Options、ReadOptions、WriteOptions、WriteBatch 内部实现层 DBImpl、MemTable、Log、VersionSet、TableCache、Compaction其中DBImpl是内部实现层的总控制器。前面db.h里有class DB { public: virtual Status Put(...) 0; virtual Status Get(...) 0; virtual Status Write(...) 0; };而DBImpl就是真正继承DB并实现这些函数的类。所以DB 是接口。 DBImpl 是实现。2.DBImpl::Writer结构体struct DBImpl::Writer {explicit Writer(port::Mutex* mu): batch(nullptr), sync(false), done(false), cv(mu) {}Status status;WriteBatch* batch;bool sync;bool done;port::CondVar cv;};首先是结构体他的目的是表示一个正在等待写入数据库的写请求其中每个参数的意思是status这次写入最后的结果batch这次要写入的一批操作sync这次写入是否要求刷盘done这次写入是否完成cv条件变量用来睡眠和唤醒等待线程这个设计非常重要。LevelDB 不是每个线程来了都自己抢着写 WAL 和 MemTable。它会把写请求排成队列writers_ 队列 Writer1 - Writer2 - Writer3 - ...然后队头线程负责真正写入。这和很多数据库里的“写入串行化”思想类似。3.为什么写入要排队因为 LevelDB 写入时要维护一些全局顺序SequenceNumber WAL log 顺序 MemTable 插入顺序数据库不能让多个线程乱序写。比如两个线程同时写线程 APut key v1 线程 BPut key v2LevelDB 必须给它们一个明确顺序先 A 后 B最终 key v2或者先 B 后 A最终 key v1不能乱。所以Writer队列就是为了保证写入顺序。这和 MySQL 里 redo log、事务提交顺序也有相似思想。4.SanitizeOptions允许用户去修改配置但是修改的配置会按照要求在一定的范围之类5.DBImpl构造函数把数据库内部组件组装起来你看到DBImpl::DBImpl(const Options raw_options, const std::string dbname) : env_(raw_options.env), internal_comparator_(raw_options.comparator), internal_filter_policy_(raw_options.filter_policy), options_(SanitizeOptions(...)), table_cache_(new TableCache(...)), mem_(nullptr), imm_(nullptr), logfile_(nullptr), log_(nullptr), tmp_batch_(new WriteBatch), versions_(new VersionSet(...)) {}这就是在初始化数据库内部组件。几个重点成员env_ 操作系统环境负责文件读写、锁、后台线程等。 internal_comparator_ 内部 key 比较器。 options_ 修正后的配置。 table_cache_ SSTable 文件缓存。 mem_ 当前正在写入的 MemTable。 imm_ 已经写满、等待刷盘的 Immutable MemTable。 logfile_ / log_ 当前 WAL 日志文件。 tmp_batch_ 临时 WriteBatch用于合并多个写请求。 versions_ 管理所有 SSTable 文件版本信息。你可以这样理解DBImpl 构造函数 把 LevelDB 运行需要的核心零件装起来。6. 析构函数关闭数据库前等后台任务结束代码里DBImpl::~DBImpl() { mutex_.Lock(); shutting_down_.store(true, std::memory_order_release); while (background_compaction_scheduled_) { background_work_finished_signal_.Wait(); } mutex_.Unlock(); ... }意思是数据库对象销毁时要先通知后台任务停止并等待正在运行的后台 Compaction 完成。为什么因为如果数据库正在后台压缩文件你直接销毁对象就可能出现后台线程还在用 mem_ 后台线程还在写 SSTable 后台线程还在访问 versions_ 主线程已经 delete 掉了这些对象这就是典型的并发资源悬空问题。所以析构时必须先停止后台任务 再释放资源这和 MySQL/Redis 关闭服务时要先停止后台线程、刷盘、释放文件句柄是同一种思想。7.NewDB()创建一个全新的数据库代码里Status DBImpl::NewDB() { VersionEdit new_db; new_db.SetComparatorName(user_comparator()-Name()); new_db.SetLogNumber(0); new_db.SetNextFile(2); new_db.SetLastSequence(0); const std::string manifest DescriptorFileName(dbname_, 1); ... }这个函数是在数据库不存在时创建新库。它主要做几件事1. 创建 VersionEdit记录新数据库的元信息 2. 创建 MANIFEST 文件 3. 把数据库初始状态写入 MANIFEST 4. 创建 CURRENT 文件让 CURRENT 指向当前 MANIFEST这里的几个概念很重要MANIFEST 记录数据库当前有哪些 SSTable、每个文件在哪一层、key 范围是什么。 CURRENT 一个很小的文件里面写着当前应该使用哪个 MANIFEST。你可以类比 MySQLSSTable 文件 真正的数据文件 MANIFEST 数据文件元信息目录 CURRENT 指向当前元信息文件的指针8.Recover()数据库打开时恢复状态这是非常核心的函数Status DBImpl::Recover(VersionEdit* edit, bool* save_manifest)它在DB::Open里面被调用。作用是打开数据库时根据 CURRENT、MANIFEST、WAL 日志把数据库恢复到正确状态。它大概做这些事1. 创建数据库目录 2. 加数据库锁防止多个进程同时打开 3. 如果数据库不存在根据 create_if_missing 决定是否创建 4. 如果数据库存在根据 error_if_exists 决定是否报错 5. 从 MANIFEST 恢复已有 SSTable 版本信息 6. 找出需要恢复的 log 文件 7. 按日志编号顺序重放 WAL 8. 更新 LastSequence这就是数据库的 crash recovery。和 MySQL 的崩溃恢复非常像LevelDB读取 WAL log恢复 MemTable / SSTable 状态 MySQL读取 redo log恢复 Buffer Pool / 数据页状态 Redis读取 AOF重放命令恢复内存状态共同思想是磁盘上的数据文件可能不是最新状态。 所以打开数据库时要根据日志把最近操作补回来。9.RecoverLogFile()重放 WAL 日志这个函数更具体Status DBImpl::RecoverLogFile(...)它做的事情是打开某个 log 文件 一条一条读取 log record 把 record 解析成 WriteBatch 把 WriteBatch 插入 MemTable 如果 MemTable 太大就写成 Level-0 SSTable代码里有WriteBatchInternal::SetContents(batch, record); status WriteBatchInternal::InsertInto(batch, mem);意思是log record 里面保存的是 WriteBatch 的编码内容。 恢复时把它还原成 batch再插入 MemTable。这也说明了你前面学的WriteBatch为什么重要LevelDB 的 WAL 日志里记录的本质上就是 WriteBatch。写入时WriteBatch - WAL WriteBatch - MemTable恢复时WAL - WriteBatch - MemTable这个设计很统一。10.WriteLevel0Table()把 MemTable 写成 SSTable代码里Status DBImpl::WriteLevel0Table(MemTable* mem, VersionEdit* edit, Version* base)这个函数的作用是把一个 MemTable 里的内容写成磁盘上的 SSTable 文件。流程大概是1. 给新 SSTable 分配 file number 2. 从 MemTable 创建 Iterator 3. 调用 BuildTable 生成 SSTable 文件 4. 记录这个文件的 smallest key 和 largest key 5. 把新文件加入 VersionEdit 6. 记录 compaction 统计信息这就是 LevelDB 从内存到磁盘的关键步骤。写入路径可以这样理解Put/Delete | WAL | MemTable | MemTable 满 | Immutable MemTable | WriteLevel0Table | Level-0 SSTable也就是说WriteLevel0Table是内存数据变成磁盘有序文件的地方。11.CompactMemTable()压缩 immutable MemTable代码里void DBImpl::CompactMemTable()作用是把已经写满的 immutable MemTable 刷成 SSTable并更新 MANIFEST。重点流程1. 调用 WriteLevel0Table把 imm_ 写成 Level-0 SSTable 2. 创建 VersionEdit 3. 写入 MANIFEST记录新文件 4. 释放 imm_ 5. 删除过期文件这里要注意写 SSTable 成功还不够。 还必须更新 MANIFEST。否则数据库下次打开时不知道这个新 SSTable 是有效数据文件。所以 LevelDB 里很多操作都不是只写数据文件还要写元数据。这和 MySQL 里数据页、redo、元信息保持一致是一个思想。12、MaybeScheduleCompaction()1. 函数作用MaybeScheduleCompaction()直译或许可以调度一次压缩它不是直接执行合并压缩只做一件事判断现在要不要启动后台压缩任务。它会依次判断一堆条件有任意一条不满足就不触发后台压缩已有后台压缩正在跑不能重复开避免磁盘 IO 打满数据库正在关闭停止一切后台任务之前后台任务出过致命错误不再调度存在 immutable memtable内存表满了必须刷盘合并用户手动触发了压缩当前版本 Version 检测到 SST 文件层数超限、文件过多需要合并。只要满足「需要压缩」且所有前置放行条件就执行cpp运行env_-Schedule(DBImpl::BGWork, this);2.env_-Schedule(任务函数, 对象)是什么Env是 LevelDB 封装的操作系统环境层里面自带线程池 / 后台工作线程Schedule 往后台线程池丢一个异步任务DBImpl::BGWork是后台真正执行 compaction、刷 imm 表的函数this是当前 DB 实例后台函数拿到数据库指针去做合并。关键点前台用户写请求线程不会阻塞在这里做繁重压缩。 Schedule 只是把任务丢进队列立刻返回写操作马上响应客户端。3. 类比 MySQL、Redis 后台机制统一设计思想MySQL 例子前台执行insert/update只是写内存缓冲池buffer pool不会同步刷磁盘脏页 刷脏页、undo/purge 清理、索引合并全部丢后台线程异步做。Redis 例子前台set只写内存 AOF 重写、RDB 持久化、过期 key 淘汰全部后台异步执行。LevelDB 同理前台db-Put()/WriteBatch只写内存 memtable快速返回 重活memtable 落地 L0、SST 分层合并、文件删除、空间回收全部交给后台线程执行。核心设计思想一句话解释前台线程只处理用户即时请求保证低延迟磁盘 IO、文件合并这类耗 CPU、耗磁盘的重量级整理工作全部丢到后台线程异步执行不阻塞用户读写。拆开两层好处提升前台读写速度降低延迟Compaction 需要大量磁盘读写、key 归并排序非常慢。 如果 Put 同步等待压缩完成每一次写入都会卡顿吞吐量暴跌。 丢后台后用户写完立刻返回感知不到耗时。统一管控后台负载避免 IO 风暴MaybeScheduleCompaction会检查是否已有后台任务在跑同一时间最多只有一次 compaction。 防止无限创建压缩线程导致磁盘被占满、业务卡死。故障隔离 后台压缩报错磁盘满、IO 错误不会直接崩溃前台写入只会标记后台错误后续调度时拦截。完整流程串联结合你之前学的 imm 刷 L0前台大量 Putmemtable 写满 → 切换成 imm_不可变内存表用户写完返回前台线程调用MaybeScheduleCompaction()函数判断有 imm_、无后台任务、数据库正常 → 调度 BGWork 后台任务后台线程异步执行WriteLevel0Table 把 imm_生成 L0 SST构建 VersionEdit、写入 MANIFEST 更新版本释放 imm 内存、清理过期 SST 文件前台全程不等待上面磁盘操作继续接收新的写入请求。通俗大白话总结就像餐厅前台服务员用户读写线程只负责接单、记菜单写内存 memtable快速接待客人后厨后台 BGWork 线程慢慢洗菜、做菜、整理库存compaction 文件合并、刷盘MaybeScheduleCompaction相当于领班判断后厨空着就安排备菜后厨忙就先不安排不让客人等。13.BackgroundCompaction()后台真正执行压缩代码里void DBImpl::BackgroundCompaction()这是 Compaction 的调度中心。它大概做这些事1. 如果 imm_ 不为空优先 compact MemTable 2. 如果是手动 compact就按用户指定范围选 compaction 3. 如果是自动 compact就让 versions_-PickCompaction() 4. 如果只是简单移动文件就直接从一层移动到下一层 5. 否则调用 DoCompactionWork 真正合并文件 6. 完成后清理旧文件这里说明 LevelDB 的 Compaction 分两类轻量情况 文件可以直接移动到下一层不需要重写。 重量情况 多个 SSTable 需要合并、过滤旧版本、生成新 SSTable。14.DoCompactionWork()真正合并 SSTable这是整个文件里最复杂、也最核心的函数之一Status DBImpl::DoCompactionWork(CompactionState* compact)它做的是读取参与 compaction 的多个 SSTable把它们合并成新的 SSTable并丢弃过期数据。这里最关键的是它会判断某条记录要不要 drop。代码里有两类丢弃逻辑1. 如果同一个 key 已经有更新版本旧版本可以丢 2. 如果删除标记已经没有必要保留也可以丢比如key - v1, seq10 key - v2, seq20如果没有快照需要看到 seq10那么 seq10 的旧版本就可以丢掉。再比如Delete key, seq30如果更低层已经没有这个 key 的旧数据了那么这个删除标记也可以丢掉。这就是 Compaction 真正的价值清理旧版本 清理删除标记 合并文件 降低读放大 降低空间浪费你之前问的 MySQL/Redis 类比这里也很像LevelDB Compaction 清理旧版本和 tombstone。 MySQL purge 清理 MVCC undo 旧版本。 Redis AOF rewrite 清理历史命令只保留最终状态。15.Get()LevelDB 的读取路径代码里Status DBImpl::Get(const ReadOptions options, const Slice key, std::string* value)这个函数就是用户调用db-Get(read_options, key, value);最终进入的地方。读取顺序非常重要1. 确定 snapshot sequence 2. 先查 mem_ 3. 再查 imm_ 4. 最后查当前 Version 里的 SSTable代码里也体现了if (mem-Get(lkey, value, s)) { // Done } else if (imm ! nullptr imm-Get(lkey, value, s)) { // Done } else { s current-Get(options, lkey, value, stats); }这就是 LevelDB 的读路径读最新内存表 | 读等待刷盘的内存表 | 读磁盘 SSTable这个顺序很好理解最新写入的数据一定先在 MemTable。 如果 MemTable 没有可能在 Immutable MemTable。 再没有才去磁盘文件里找。这和 Redis MySQL 类比也很自然先查快的地方。 找不到再查慢的地方。只不过 LevelDB 这里是在存储引擎内部完成。分步逐条解释1. 确定 snapshot sequence快照序列号LevelDB 每一次写入 (Put/Delete) 都会分配一个全局递增序列号SequenceNumber用来实现快照、隔离、MVCC。如果用户传入了自定义快照ReadOptions.snapshot就用快照对应的序列号没指定快照就用数据库当前最新全局序列号。 作用查询时只读取 ≤ 当前序列号的数据屏蔽这条快照之后新增的数据保证快照一致性。2. 先查 mem_活跃内存表mem_当前正在接收写入的可变 MemTable最新的数据都存在这里。遍历 memtable 跳表查找 key如果找到判断这条记录的序列号 ≤ 快照序列号如果是 Put直接返回 value如果是 Delete墓碑代表 key 已被删除返回 “不存在”找到直接 return不会去查 imm 和 SST减少磁盘 IO。3. 再查 imm_不可变内存表当 mem_ 写满后会切换为imm_新数据写到新 mem_imm_ 等待后台线程刷成 L0 SST。 imm_ 里的数据比 mem_ 旧但比磁盘 SST 新。mem_ 没找到才会去查 imm_同样匹配 key 校验序列号命中直接返回。4. 最后查当前 Version 里的 SSTable磁盘文件内存两张表都没找到才走磁盘也就是Version管理的所有层级 SST 文件优先查 L0L0 文件 key 区间重叠需要逐个遍历匹配L1~Lmax每层有序不重叠通过二分快速定位最多一个 SST逐层从上到下查找上层更新下层更旧一旦在某个 SST 中找到 key校验序列号区分 Put/Delete返回结果全部 SST 遍历完都没有 → key 不存在。16.NewIterator()创建统一视图的迭代器代码里Iterator* DBImpl::NewIterator(const ReadOptions options)它会先调用NewInternalIterator(...)内部会收集多个迭代器mem_ iterator imm_ iterator SSTable iterators然后通过NewMergingIterator(...)把它们合并成一个有序迭代器。这很关键。因为 LevelDB 的数据分散在MemTable Immutable MemTable Level-0 SSTable Level-1 SSTable Level-2 SSTable ...但用户使用 Iterator 时不想关心这些。用户只想it-SeekToFirst(); it-Next();所以 LevelDB 内部要把多个来源合并成一个逻辑有序流。这和 MySQL 执行计划里把多个数据来源组合成一个结果集也有一点设计思想上的相似。17.GetSnapshot()/ReleaseSnapshot()快照管理代码里const Snapshot* DBImpl::GetSnapshot() { MutexLock l(mutex_); return snapshots_.New(versions_-LastSequence()); }意思是创建一个快照记录当前最新 sequence number。释放时void DBImpl::ReleaseSnapshot(const Snapshot* snapshot) { MutexLock l(mutex_); snapshots_.Delete(static_castconst SnapshotImpl*(snapshot)); }Snapshot 的本质不是复制一份完整数据库。它只是记录一个 sequence number。比如当前 LastSequence 100 GetSnapshot() 得到 snapshot(seq100)之后即使数据库继续写到 seq120这个 snapshot 读的时候仍然只看sequence 100 的数据这就是 LevelDB 的 MVCC 味道。和 MySQL 的 ReadView 很像MySQL ReadView 决定当前事务能看到哪些版本。 LevelDB Snapshot 决定当前读取能看到哪些 sequence number。在这个里面有一个思考点就是为什么要上锁而前面的get则不用。首先MutexLock 是什么MutexLock l(mutex_);RAII 自动锁构造函数上锁mutex_.Lock()函数结束、对象销毁时自动解锁不会漏解锁。整个GetSnapshot()函数内所有共享变量访问都被同一把mutex_保护保证原子性读取最新序列号 创建快照并插入链表这两步作为一个不可分割的原子操作。其实答案就是get是只是去读但是GetSnapshot()在读取全局序列号时会对其进行修改共享的快照链表。如果更精确一点的话就是GetSnapshot()不修改全局序列号只是读取正在被并发修改的全局序列号同时修改共享快照链表这两步合起来必须加锁 而普通Get()只做纯查询不碰这两个临界资源所以不用这把锁。普通db-Get()读取路径只是只读遍历 mem/imm/SST不会修改快照链表、不会读写全局序列号 但GetSnapshot()要读取可变全局序列号 修改共享快照链表属于「读 修改临界区」必须加锁。不加锁会出现什么 bug读到损坏的序列号快照查询数据不一致快照链表并发插入导致链表结构损坏程序 crashCompaction 遍历快照链表时访问野指针崩溃重复创建重复序列号快照版本回收逻辑错乱。18.Write()最核心的写入路径这是整个文件最应该认真看的函数Status DBImpl::Write(const WriteOptions options, WriteBatch* updates)它是用户调用db-Put(...) db-Delete(...) db-Write(...)最终都会走到的地方。整体流程是1. 创建 Writer把本次写请求放入 writers_ 队列 2. 等自己成为队头 3. 调用 MakeRoomForWrite确保 MemTable 有空间 4. 调用 BuildBatchGroup把多个写请求合并成一个大 batch 5. 给 batch 设置 sequence number 6. 写入 WAL log 7. 如果 synctrue就 Sync 日志文件 8. 把 batch 插入 MemTable 9. 更新 LastSequence 10. 唤醒队列里已经一起完成的 writer在这个里面为什么需要等到队头才去执行是一个可以去思考的问题。「等自己成为队头」完整含义首先需要直到writers_ 是什么他是 DBImpl 内部一个等待写入的线程队列条件变量 链表。 多个业务线程同时调用db-Put()/db-Write()时每个线程都会封装成一个Writer对象塞进writers_排队。LevelDB 写入采用批量合并写group commit 不让每个写请求单独落盘、单独写 memtable而是队列头部一次性捞一批请求合并执行减少 WAL IO、锁竞争提升吞吐。1. 流程还原线程进来第一步封装自己为 Writerpush 进 writers_ 队列。 然后执行循环等待逻辑while (自己不是队列第一个元素) { 等待条件变量 cond_; }也就是只要当前线程的 Writer 不在队列头部就阻塞休眠不往下执行写逻辑。2. 为什么要等自己变成队头批量合并写的规则只有队头 Writer 才有资格真正执行写入流程。排在后面的所有 Writer 全部阻塞等待队头线程会一次性把自己 后面连续一批等待的 Writer 全部打包合并成一个大 Batch统一写 WAL、统一插入 MemTable、统一分配序列号一次性完成一批请求写完后批量唤醒这批等待的线程全部返回成功。举个场景 线程 1、2、3、4 同时并发写依次进入 writers_队列 队列顺序[W1, W2, W3, W4]W1 是队头不用等继续执行 MakeRoomForWrite、合并 BatchW2、W3、W4 发现自己不是队头全部阻塞休眠 W1 执行 BuildBatchGroup把 W1W2W3W4 全部合并成一个大 batch一次性写入 写完后唤醒 W2/W3/W4四个线程同时返回上层业务。3. 如果不等待、直接执行会怎么样每个线程都尝试去写 WAL、修改 memtable、更新全局序列号必然出现大量锁争抢频繁上下文切换每个请求单独刷 WAL磁盘 IO 爆炸性能暴跌序列号分配并发冲突必须加超大粒度锁并发直接退化串行。其次需要思考的是第六步与第七步有什么区别写入 WAL log只是把日志数据写入操作系统页缓存page cache数据现在在内存缓冲区还没真正落到磁盘硬件上写入速度极快只是内存拷贝此时如果机器突然断电、内核崩溃这份新写的 WAL 数据会直接丢失。synctrue 执行 Syncfsync/fdatasync---------------------------------------------------------------------------------------------------------------------------------强制把内核缓存里的 WAL 数据刷到磁盘持久化存储触发磁盘硬件 IO把缓存数据写入磁盘盘片完成 sync 之后就算断电数据也不会丢sync 很慢涉及磁盘物理写入开销大。这就是 LevelDB 写入的主干。可以画成用户 Put/Delete/Write | v Writer 入队 | v 成为队头 | v MakeRoomForWrite | v BuildBatchGroup 合并多个写 | v 写 WAL | v 写 MemTable | v 返回 Status这段代码非常体现数据库系统设计。19.BuildBatchGroup()合并多个写请求代码里WriteBatch* DBImpl::BuildBatchGroup(Writer** last_writer)这个函数做的是把写队列里连续的多个 Writer 合并成一个更大的 WriteBatch。为什么要合并因为每个写请求单独写 WAL 成本比较高。如果多个写请求排在队列里可以合并Writer1: Put A Writer2: Put B Writer3: Delete C变成一个大 batch: Put A Put B Delete C然后一次写 WAL一次插入 MemTable。这和 Redis pipeline、MySQL group commit 思想非常像多个小请求合并处理提高吞吐。但代码里也有两个限制1. batch 不能无限大 2. sync 写不能被非 sync 写带着一起处理因为如果 batch 太大小请求会被拖慢。所以它用了size_t max_size 1 20; if (size (128 10)) { max_size size (128 10); }意思大概是最多合并到 1MB。 如果第一个请求很小就不要合并太多避免小请求延迟太高。这就是吞吐和延迟之间的权衡。20.MakeRoomForWrite()写入前确保 MemTable 有空间代码里Status DBImpl::MakeRoomForWrite(bool force)这个函数负责写入前检查当前 MemTable 是否还能写如果不能就切换新的 MemTable并安排旧 MemTable 刷盘。它里面几个判断非常重要1. 如果有后台错误停止写入 2. 如果 Level-0 文件太多稍微延迟写入 3. 如果 MemTable 还有空间直接写 4. 如果 imm_ 还没 compact 完就等待 5. 如果 Level-0 文件多到危险程度就等待 6. 否则创建新 log把当前 mem_ 变成 imm_再创建新的 mem_这就是 LevelDB 的写入背压机制。什么叫背压就是当后台整理跟不上前台写入时前台写入不能无限冲。否则会出现Level-0 文件越来越多 读性能越来越差 Compaction 压力越来越大 磁盘越来越乱所以 LevelDB 会让写入慢下来甚至等待 compaction。这和 MySQL、Redis 都类似MySQL 脏页太多时前台写入可能变慢。 Redis AOF rewrite 或内存压力大时也可能影响请求延迟。数据库不是只追求“写得快”还要防止系统被写爆。21.DB::Put和DB::Delete的默认实现代码最后有Status DB::Put(const WriteOptions opt, const Slice key, const Slice value) { WriteBatch batch; batch.Put(key, value); return Write(opt, batch); } Status DB::Delete(const WriteOptions opt, const Slice key) { WriteBatch batch; batch.Delete(key); return Write(opt, batch); }这非常重要。它证明了我们前面说的单条 Put/Delete本质上也是一个只有一条操作的 WriteBatch。也就是说Put(key, value)等价于创建 WriteBatch batch.Put(key, value) db-Write(batch)所以 LevelDB 的写入核心其实只有一个DBImpl::Write(...)Put和Delete都只是便利函数。22.DB::Open()打开数据库入口代码里Status DB::Open(const Options options, const std::string dbname, DB** dbptr)这是用户真正调用的入口leveldb::DB* db; Status s leveldb::DB::Open(options, ./testdb, db);内部做这些事1. 创建 DBImpl 2. 加锁 3. 调用 Recover 恢复数据库 4. 如果恢复后还没有 mem_创建新的 log 和 MemTable 5. 如果需要保存新的 MANIFEST 6. 删除过期文件 7. 安排后台 compaction 8. 成功则把 impl 赋给 *dbptr 9. 失败则 delete impl这里你能看到DB和DBImpl的关系用户拿到的是 DB* 实际对象是 DBImpl*这就是典型的 C 多态DB* db new DBImpl(...);用户只看到接口内部实现隐藏起来。23.DestroyDB()删除整个数据库最后还有Status DestroyDB(const std::string dbname, const Options options)这个函数负责删除数据库目录下的 LevelDB 文件。它会1. 列出数据库目录下文件 2. 加数据库锁 3. 删除除 LOCK 外的数据库文件 4. 解锁 5. 删除 LOCK 文件 6. 尝试删除目录这个函数很危险。它不是删除一个 key而是删除整个数据库。
![[C++]内存管理：串顺序存储的内存回收](http://pic.xiahunao.cn/yaotu/[C++]内存管理：串顺序存储的内存回收)
