《现代 Key-Value 数据库原理：从 B+Tree 到 LSM Tree》-第四篇：LevelDB 深度解析

文章目录

• 《现代 Key-Value 数据库原理：从 B+Tree 到 LSM Tree》
• 第四篇：LevelDB 深度解析
• 第一章 为什么 Google 设计 LevelDB
• • 1.1 从 B+Tree 的问题开始
• 1.2 为什么随机写是问题
• 1.3 SSD改变了什么？
• 1.4 LSM Tree的核心思想
• 1.5 B+Tree和LSM的核心区别
• • • B+Tree
    • LSM
• 第二章 LevelDB整体架构
• 第三章 MemTable
• • 3.1 什么是MemTable
• 3.2 为什么MemTable需要有序？
• 3.3 LevelDB为什么使用SkipList？
• 3.4 SkipList是什么？
• 3.5 SkipList结构
• 3.6 SkipList为什么适合MemTable？
• • • 第一：查询快
    • 第二：插入快
    • 第三：天然有序
    • 第四：实现相对简单
• 第四章 Write Path：一次Put到底发生什么
• 4.1 第一步：写WAL
• 4.2 为什么需要WAL？
• 第五章 WAL文件结构
• 5.1 CRC是什么？
• 5.2 WAL与数据库恢复
• 第六章 Immutable MemTable
• 6.1 为什么要有Immutable？
• 6.2 完整流程
• 第七章 SSTable
• 7.1 SSTable为什么重要？
• 7.2 SSTable整体结构
• 第八章 Data Block
• 8.1 为什么分Block？
• 第九章 Index Block
• 9.1 Data Block + Index Block
• 第十章 Meta Block
• 第十一章 Footer
• 11.1 为什么Footer放在最后？
• 第十二章 SSTable完整结构图
• 第十三章 Bloom Filter
• 13.1 为什么需要Bloom Filter？
• 第十四章 Bitmap
• 14.1 查询
• 14.2 查询不存在的数据
• 14.3 Bloom Filter为什么会误判？
• 14.4 Bloom Filter的意义
• 第十五章 Compaction
• 15.1 Compaction是什么？
• 第十六章 Level 0
• 16.1 为什么L0特殊？
• 第十七章 L1、L2
• 17.1 LSM Tree整体
• 第十八章 为什么后台一直Compaction？
• 18.1 Delete为什么也需要Compaction？
• 第十九章 Compaction过程
• 第二十章 Compaction的代价
• 第二十一章 Manifest
• 21.1 CURRENT
• 21.2 MANIFEST
• 21.3 为什么需要MANIFEST？
• 21.4 LOCK
• 21.5 LOG
• 第二十二章 LevelDB目录结构
• 第二十三章 Snapshot
• 23.1 Snapshot有什么用？
• 23.2 Snapshot与MVCC
• 第二十四章 Sequence Number
• 第二十五章 Iterator
• 第二十六章 LevelDB读取流程
• 第二十七章 LevelDB源码结构
• • 27.1 DBImpl
• 27.2 MemTable
• 27.3 VersionSet
• 27.4 Table
• 第二十八章 C++使用LevelDB
• • 28.1 创建数据库
• 28.2 Put
• 28.3 Get
• 28.4 Delete
• 28.5 WriteBatch
• 第二十九章 LevelDB为什么适合AI/视觉数据
• • LMDB
  • LevelDB
• 第三十章 LMDB vs LevelDB
• 第三十一章 Facebook为什么发展RocksDB
• 31.1 为什么需要RocksDB？
• 31.2 RocksDB重点改进
• 31.3 Column Family
• 31.4 RocksDB与LevelDB关系
• 第三十二章 LevelDB完整数据流
• • 写入
• 32.1 读取
• 32.2 崩溃恢复
• 第三十三章 LevelDB真正解决的问题
• 第三十四章 LSM Tree的本质
• 第三十五章 LMDB与LevelDB的设计哲学
• • LMDB
  • LevelDB
• 第三十六章 一张图理解LMDB和LevelDB
• 第三十七章 本篇总结

《现代 Key-Value 数据库原理：从 B+Tree 到 LSM Tree》

第四篇：LevelDB 深度解析

LevelDB 是 Google 开源的嵌入式 Key-Value 存储引擎，由 Jeffrey Dean 和 Sanjay Ghemawat 等人设计。它最核心的思想是：把随机写转换成顺序写，把大量修改先积累在内存中，再通过 SSTable 和 Compaction 组织成适合持久化和查询的数据结构。

如果上一篇 LMDB 可以概括为：

LMDB

B+Tree
+
mmap
+
Copy-On-Write
+
MVCC

那么 LevelDB 可以概括为：

LevelDB

LSM Tree
+
MemTable
+
WAL
+
SSTable
+
Compaction
+
Bloom Filter

这两种数据库代表了两种非常重要的数据库设计路线。

第一章 为什么 Google 设计 LevelDB

1.1 从 B+Tree 的问题开始

上一篇我们已经介绍过 B+Tree。

典型结构：

Root
|
+——+——+
| |
Branch Branch
| |
+—+—+ +—+—+
| | | |
Leaf Leaf Leaf Leaf

假设现在需要插入：

key = 10086
value = xxx

数据库需要：

Root
↓
Branch
↓
Leaf
↓
修改Page

如果Page不在内存：

CPU
↓
Memory Miss
↓
SSD

这就是一个随机IO。

1.2 为什么随机写是问题

假设：

100万次随机写

传统B+Tree可能产生：

Write

↓

随机修改Page

↓

随机IO

如果数据越来越大：

B+Tree

Root
|
|
Branch
/ \\
Leaf Leaf
| |
Disk Disk

不同Key可能对应完全不同的磁盘Page。

于是：

Write A → Page 100
Write B → Page 5000
Write C → Page 200
Write D → Page 8000

形成大量随机写。

1.3 SSD改变了什么？

SSD相比机械硬盘：

随机IO已经快很多。

但是：

SSD并没有让随机写和顺序写完全没有区别。

尤其数据库写入还涉及：

• Page 更新
• 元数据更新
• 日志
• FTL
• Garbage Collection
• Write Amplification

所以：

随机写

依然比：

顺序写

更难优化。

1.4 LSM Tree的核心思想

LSM：

Log-Structured Merge Tree

核心思想：

不要每次修改磁盘上的B+Tree，而是先把修改放到内存中，然后批量顺序写入磁盘。

传统B+Tree：

Write

↓

随机修改B+Tree

↓

Random IO

LSM：

Write

↓

MemTable

↓

WAL

↓

顺序写SSTable

↓

后台Compaction

于是：

大量随机写

↓

内存排序

↓

批量顺序写

1.5 B+Tree和LSM的核心区别

可以把两者理解成：

B+Tree：

边写边维护最终索引结构

LSM：

先写

后整理

例如：

B+Tree

Insert A
↓
修改Tree

Insert B
↓
修改Tree

Insert C
↓
修改Tree

LSM

Insert A
↓
MemTable

Insert B
↓
MemTable

Insert C
↓
MemTable

统一Flush

↓

SSTable

这就是LevelDB最重要的设计思想。

第二章 LevelDB整体架构

LevelDB整体可以画成：

Application
|
|
DB::Put()
|
+———-+———-+
| |
WAL MemTable
| |
| SkipList
| |
| |
+———-+———-+
|
Immutable MemTable
|
Flush
|
v
SSTable
|
+———–+———–+
| |
v v
L0 L1
|
L2
|
L3

读取路径：

Application
|
v
MemTable
|
v
Immutable MemTable
|
v
L0
|
v
L1
|
v
L2
|
v
…

写入路径：

Put
|
+—-> WAL
|
+—-> MemTable
|
| Full
v
Immutable MemTable
|
| Flush
v
SSTable

第三章 MemTable

3.1 什么是MemTable

MemTable：

Memory Table

是LevelDB首先写入的内存数据结构。

例如：

Put("apple", 100)
Put("banana", 200)
Put("cat", 300)

不会马上修改SSTable。

而是：

MemTable

apple → 100
banana → 200
cat → 300

3.2 为什么MemTable需要有序？

因为最终需要生成：

SSTable

而SSTable内部：

Key

按顺序排列

例如：

apple
banana
cat
dog
fish

如果MemTable本身已经有序：

MemTable

↓

顺序Flush

↓

SSTable

就非常方便。

3.3 LevelDB为什么使用SkipList？

LevelDB的MemTable底层使用：

SkipList

而不是普通：

std::map

3.4 SkipList是什么？

SkipList：

一种利用多层链表实现快速查找的数据结构。

普通链表：

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8

查找：

7

需要：

1
↓
2
↓
3
↓
4
↓
5
↓
6
↓
7

复杂度：

O(N)

SkipList增加多层索引：

Level 3:

1 ———————-> 7

Level 2:

1 ——–> 4 ———-> 7

Level 1:

1 –> 2 –> 3 –> 4 –> 5 –> 6 –> 7

查找：

1
↓
Level3
↓
7

平均复杂度：

O(logN)

3.5 SkipList结构

可以理解为：

+———————-+
| |
v |
HEAD ——-> 10 ——————> 50
| | |
| v v
+———> 20 —–> 30 ——-> 50
| | | |
+———> 15 –> 20 –> 30 –> 40 –> 50

底层：

完整数据

上层：

快速索引

3.6 SkipList为什么适合MemTable？

主要有几个原因。

第一：查询快

平均：

O(logN)

第二：插入快

平均：

O(logN)

第三：天然有序

非常适合：

Iterator

以及：

Flush

第四：实现相对简单

相比复杂的平衡树：

SkipList

结构简单

LevelDB因此采用了这种结构。

第四章 Write Path：一次Put到底发生什么

假设：

db->Put(
WriteOptions(),
"name",
"qtree"
);

LevelDB内部大致经过：

Put
|
v
WriteBatch
|
+——-+——-+
| |
v v
WAL MemTable
| |
| |
+——-+——-+
|
Write Complete

4.1 第一步：写WAL

LevelDB首先需要保证：

即使程序突然崩溃，刚刚写入的数据也不能丢。

因此：

Put

↓

WAL

WAL：

Write Ahead Log

即：

预写日志。

4.2 为什么需要WAL？

假设：

Put("A",100)

已经：

MemTable

A → 100

但是：

还没有Flush到SSTable。

突然：

程序崩溃

内存：

MemTable

全部丢失。

如果没有WAL：

A → 100

就消失了。

有WAL：

WAL

Put A=100

崩溃以后：

重新启动

↓

读取WAL

↓

重新构建MemTable

数据恢复。

第五章 WAL文件结构

LevelDB的日志文件通常：

000123.log

结构：

+——————-+
| Header |
+——————-+
| Record |
+——————-+
| Record |
+——————-+
| Record |
+——————-+

每条Record包含：

CRC

Length

Type

Payload

可以理解为：

+——–+——–+——–+————-+
| CRC | Length | Type | Data |
+——–+——–+——–+————-+

5.1 CRC是什么？

CRC：

Cyclic Redundancy Check

循环冗余校验。

用途：

判断日志数据有没有损坏。

例如：

Write:

A=100

生成：

CRC = X

读取：

重新计算：

CRC'

如果：

CRC == CRC'

说明数据大概率完整。

5.2 WAL与数据库恢复

假设程序：

Put A
Put B
Put C

此时：

WAL:

A
B
C

但是：

MemTable

还没有Flush。

突然：

Crash

重启：

读取WAL

↓

Replay A

↓

Replay B

↓

Replay C

↓

重建MemTable

恢复完成。

第六章 Immutable MemTable

MemTable不能无限增长。

假设：

MemTable

100MB

达到限制以后：

不能继续无限写。

LevelDB会：

MemTable

↓

Immutable MemTable

↓

新的MemTable

6.1 为什么要有Immutable？

如果Flush期间：

直接操作MemTable：

Writer
|
v
MemTable
|
v
Disk

写线程就会被Flush阻塞。

LevelDB的解决方法：

Old MemTable

↓

Immutable

新建

New MemTable

于是：

Writer
|
v
New MemTable

同时：

Background Thread

Immutable MemTable

↓

SSTable

6.2 完整流程

Writer
|
v
Current MemTable
|
MemTable Full
|
v
Immutable MemTable
|
|
v
Flush
|
v
L0 SST

与此同时：

Writer

↓

New MemTable

所以写入和Flush可以部分并行。

第七章 SSTable

SSTable：

Sorted String Table

可以理解为：

一个按照Key排序保存的不可变磁盘文件。

例如：

000001.sst

里面：

apple
banana
cat
dog
fish

按Key有序。

7.1 SSTable为什么重要？

MemTable：

内存

可修改

SSTable：

磁盘

不可修改

这两个结构形成：

MemTable

↓

SSTable

7.2 SSTable整体结构

LevelDB的SSTable可以抽象成：

+————————-+
| Data Block |
+————————-+
| Data Block |
+————————-+
| Data Block |
+————————-+
| … |
+————————-+
| Meta Block |
+————————-+
| Meta Index Block |
+————————-+
| Index Block |
+————————-+
| Footer |
+————————-+

这里要特别注意：

用户经常会画成：

Data
Index
Meta
Footer

但真实实现中：

Data Blocks
Meta Blocks
Metaindex Block
Index Block
Footer

之间还有更具体的组织关系。

第八章 Data Block

Data Block是真正存放：

Key-Value

的地方。

例如：

Data Block 1

apple → 100
banana → 200
cat → 300

另一个：

Data Block 2

dog → 400
fish → 500
horse → 600

整体：

SSTable

+—————-+
| Data Block 1 |
+—————-+
| Data Block 2 |
+—————-+
| Data Block 3 |
+—————-+

8.1 为什么分Block？

如果整个SSTable：

1GB

查询一个Key：

cat

不可能把1GB全部加载。

所以：

SSTable

↓

Block

↓

Block Index

↓

定位Block

第九章 Index Block

Index Block：

用来快速定位Data Block。

例如：

Index Block

apple → Block1

dog → Block2

horse → Block3

查询：

fish

Index：

dog < fish < horse

所以：

fish

↓

Block2

结构：

SSTable

|

Index Block

+——-+——-+
| |
apple dog
| |
Block1 Block2

9.1 Data Block + Index Block

完整：

SSTable

|
+——-+——-+
| |
Index Block Data Blocks
|
+——+——+
| |
apple dog
| |
Block1 Block2

查询：

Key
↓
Index Block
↓
Data Block
↓
Value

第十章 Meta Block

Meta Block用于：

保存SSTable的额外元数据。

其中最重要的就是：

Bloom Filter

例如：

Meta Block

Filter Policy

结构：

SSTable

+——————+
| Data Blocks |
+——————+
| Meta Blocks |
| |
| Bloom Filter |
+——————+
| MetaIndex |
+——————+
| Index Block |
+——————+
| Footer |
+——————+

第十一章 Footer

Footer位于SSTable末尾。

它非常重要。

因为：

程序打开SSTable以后：

首先读取Footer。

Footer里面记录：

MetaIndex Block位置

Index Block位置

于是：

打开SSTable

↓

读取Footer

↓

找到Index Block

↓

找到MetaIndex

↓

查询

11.1 为什么Footer放在最后？

因为：

SSTable写入过程：

Data Blocks

↓

Meta Blocks

↓

Index

↓

Footer

最终才能知道：

Index在哪里

Meta在哪里

所以：

最后写Footer。

第十二章 SSTable完整结构图

可以把LevelDB SSTable理解成：

+———————————-+
| |
| Data Block 1 |
| |
+———————————-+
| |
| Data Block 2 |
| |
+———————————-+
| |
| Data Block 3 |
| |
+———————————-+
| |
| Meta Block |
| |
| Bloom Filter |
| |
+———————————-+
| |
| MetaIndex Block |
| |
+———————————-+
| |
| Index Block |
| |
+———————————-+
| |
| Footer |
| |
| MetaIndex Handle |
| Index Handle |
| |
+———————————-+

查询过程：

Key
|
v
Footer
|
+——-+——-+
| |
v v
Index Block MetaIndex
|
v
Data Block
|
v
Value

第十三章 Bloom Filter

Bloom Filter是LevelDB非常重要的优化。

它解决一个非常现实的问题：

一个Key不存在时，能不能不要去磁盘读取SSTable？

答案：

Bloom Filter

13.1 为什么需要Bloom Filter？

假设：

L0

10个SSTable

L1

100个SSTable

L2

1000个SSTable

查询：

key = abc123

如果这个Key根本不存在。

没有Bloom Filter：

查SST1
↓
没有

查SST2
↓
没有

查SST3
↓
没有

…

可能需要检查大量SSTable。

Bloom Filter：

abc123

↓

Bloom Filter

↓

Definitely Not Present

于是：

不用读取SSTable

第十四章 Bitmap

Bloom Filter最基础的数据结构：

Bitmap

例如：

0 0 0 0 0 0 0 0 0 0

假设有一个Key：

apple

经过Hash：

hash1(apple) = 2

hash2(apple) = 7

hash3(apple) = 9

设置：

0 0 1 0 0 0 0 1 0 1

14.1 查询

现在查询：

apple

重新计算：

hash1 → 2

hash2 → 7

hash3 → 9

发现：

2 = 1

7 = 1

9 = 1

所以：

可能存在

14.2 查询不存在的数据

查询：

orange

Hash：

hash1 → 2

hash2 → 5

hash3 → 8

如果：

bitmap[5] = 0

直接判断：

Definitely Not Exist

不需要访问磁盘。

14.3 Bloom Filter为什么会误判？

Bloom Filter：

可以：

False Positive

但是不能：

False Negative

也就是：

可能说：

存在

但实际上不存在。

但是不会说：

不存在

实际上存在。

例如：

apple

hash：

2
7
9

之后：

orange

hash：

2
7
9

恰好全部撞上。

Bloom Filter认为：

orange

可能存在

但实际上：

orange不存在

这就是：

False Positive

14.4 Bloom Filter的意义

它的核心目标不是：

100%准确判断

而是：

快速过滤掉绝大多数不存在的数据。

流程：

Query

↓

Bloom Filter

+—————-+
| |
| Not Exist | → 直接结束
| |
+—————-+

|

| Maybe Exist

v

SSTable

第十五章 Compaction

这是LSM Tree最核心的后台机制。

因为：

SSTable是不可修改的。

不断写入：

Put A
Put B
Put C
…

最终：

SST1
SST2
SST3
SST4
…

越来越多。

查询就会越来越慢。

所以必须：

Merge

15.1 Compaction是什么？

Compaction：

将多个SSTable读取、合并、排序，再生成新的SSTable。

例如：

SST1

A
C
E

SST2

B
D
F

Compaction：

Merge

↓

A
B
C
D
E
F

生成：

New SST

第十六章 Level 0

MemTable Flush之后：

SSTable通常首先进入：

L0

例如：

L0

SST1
SST2
SST3
SST4

这些文件可能：

Key Range

互相重叠。

例如：

SST1:

A ~ F

SST2:

C ~ H

SST3:

E ~ K

16.1 为什么L0特殊？

因为：

多个SSTable：

Key Range可能重叠

例如：

SST1:

A B C

SST2:

B C D

查询：

C

可能两个文件都有。

因此：

查询需要：

SST1
SST2

第十七章 L1、L2

Compaction以后：

L0

↓

L1

L1通常会形成：

Key Range不重叠

例如：

L1

SST1:

A-D

SST2:

E-H

SST3:

I-M

所以查询：

F

只需要：

SST2

17.1 LSM Tree整体

可以画成：

MemTable
|
Flush
|
v
L0
+—–+—–+
| | |
SST SST SST
|
Compaction
|
v
L1
+——+——+
| |
SST SST
|
Compaction
|
v
L2
+——+——+
| | |
SST SST SST
|
v
L3

第十八章 为什么后台一直Compaction？

因为：

如果不Compaction：

SSTable

1
2
3
4
5
6
…
10000

最终：

Read

↓

扫描大量SST

查询性能下降。

Compaction的目的：

大量小SST

↓

少量大SST

同时：

删除旧版本
删除墓碑
整理Key

18.1 Delete为什么也需要Compaction？

假设：

Put:

A = 100

后来：

Delete A

不能直接从旧SSTable删除。

因为：

SSTable不可修改。

所以写入：

Tombstone

可以理解成：

A = DELETE

查询：

看到Tombstone

知道：

A已经被删除

Compaction时：

Old:

A=100

New:

A=DELETE

如果确认旧版本已经不需要：

最终：

A

可以被彻底清理。

第十九章 Compaction过程

假设：

L0

SST1:

A C E

SST2:

B D F

触发Compaction。

第一步：

读取SST1
读取SST2

第二步：

Merge

A
B
C
D
E
F

第三步：

写入：

New SST

第四步：

删除：

SST1
SST2

完整：

SST1 —-\\
\\
→ Merge → New SST
/
SST2 —-/

第二十章 Compaction的代价

Compaction不是免费的。

它会产生：

Read Amplification
Write Amplification
CPU开销
IO开销

例如：

1GB数据

不断Compaction：

可能：

写10GB

这就是：

Write Amplification

因此：

LSM Tree的核心问题其实是：

用后台Compaction换取前台写入性能。

这也是后面RocksDB大量优化的重点。

第二十一章 Manifest

LevelDB目录里：

除了：

000001.sst
000002.sst

还存在：

MANIFEST-000001
CURRENT
LOCK
LOG

这些文件非常重要。

21.1 CURRENT

CURRENT是一个很小的文件。

它记录：

当前正在使用哪个MANIFEST。

例如：

CURRENT

MANIFEST-000007

启动：

读取CURRENT

↓

找到MANIFEST-000007

21.2 MANIFEST

MANIFEST保存：

数据库版本和SSTable元数据变化。

例如：

VersionEdit

AddFile:

L1
000123.sst

DeleteFile:

L0
000100.sst

数据库状态变化：

Version 1

SST1
SST2

↓

Compaction

Version 2

SST3
SST4

MANIFEST记录：

SST1删除
SST2删除

SST3增加
SST4增加

21.3 为什么需要MANIFEST？

因为：

数据库启动时必须知道：

哪些SST属于L0？

哪些属于L1？

哪些属于L2？

哪些已经删除？

不能：

扫描所有SST文件

然后猜测数据库状态。

所以：

CURRENT

↓

MANIFEST

↓

Version

↓

File Metadata

21.4 LOCK

LOCK

用于：

防止多个进程同时打开同一个LevelDB数据库进行不安全操作。

通常：

Process A

↓

LOCK

Process B

↓

无法同时正常打开

21.5 LOG

这里需要特别注意：

LevelDB中的：

LOG

与：

MANIFEST

以及：

WAL

概念不同。

LevelDB的数据写入日志通常就是：

*.log

例如：

000123.log

它负责：

Write Ahead Log

而：

MANIFEST

负责：

数据库Version变化
SSTable布局

所以可以简单理解：

000123.log

↓

用户数据恢复

MANIFEST

↓

数据库结构恢复

第二十二章 LevelDB目录结构

典型：

database/

├── CURRENT
├── LOCK
├── LOG
├── MANIFEST-000001
├── 000003.log
├── 000005.ldb
├── 000006.ldb
└── …

注意：

LevelDB不同版本/实现中，SSTable文件可能使用：

.ldb

或者相关实现中的：

.sst

不要把文件扩展名本身当作LSM设计的一部分。

真正重要的是：

SSTable

这一数据结构。

第二十三章 Snapshot

LevelDB支持：

const Snapshot* snapshot =
db->GetSnapshot();

Snapshot可以理解成：

某一时刻数据库状态的快照。

假设：

T1:

A = 100

创建Snapshot：

Snapshot
↓
T1

随后：

Put A=200

普通读取：

A = 200

Snapshot读取：

A = 100

23.1 Snapshot有什么用？

典型场景：

数据库：

正在持续写入

同时：

需要：

一致性读取

例如：

统计任务

↓

Snapshot

↓

读取整个数据库

即使后台继续：

Put

Delete

统计看到的仍然是：

Snapshot时刻

23.2 Snapshot与MVCC

它与LMDB的MVCC有相似思想：

LMDB

Reader Snapshot

LevelDB

Snapshot Sequence Number

但具体实现机制不同。

LevelDB通过：

Sequence Number

区分不同版本的记录。

第二十四章 Sequence Number

LevelDB内部的Key并不只是：

user_key

而是类似：

internal_key

=

user_key

+

sequence_number

+

value_type

例如：

user key:

A

内部可能：

A + 100 + PUT

下一次修改：

A + 120 + PUT

删除：

A + 150 + DELETE

于是：

A + 150 + DELETE
A + 120 + PUT
A + 100 + PUT

通过Sequence Number：

就可以知道：

哪个版本更新

第二十五章 Iterator

LevelDB提供：

Iterator

例如：

std::unique_ptr<leveldb::Iterator> it(
db->NewIterator(
leveldb::ReadOptions()
)
);

for(it->SeekToFirst();
it->Valid();
it->Next())
{
std::cout
<< it->key().ToString()
<< " = "
<< it->value().ToString()
<< std::endl;
}

Iterator实际上要面对多个数据源：

MemTable
|
Immutable MemTable
|
L0 SSTables
|
L1 SSTables
|
L2 SSTables

因此：

Iterator不是简单的：

std::vector iterator

而是：

Multiple Iterator

↓

Merge Iterator

↓

Sorted Result

第二十六章 LevelDB读取流程

查询：

db->Get(
ReadOptions(),
"camera001",
&value
);

大致：

Get
|
v
MemTable
|
Not Found
|
v
Immutable MemTable
|
Not Found
|
v
L0
|
v
L1
|
v
L2

每个SSTable查询：

Bloom Filter
|
| Not Exist
|————> 下一文件
|
Maybe
|
v
Index Block
|
v
Data Block
|
v
Key
|
v
Value

第二十七章 LevelDB源码结构

LevelDB虽然是一个相对小型的数据库，但源码结构非常值得学习。

典型核心模块：

db/

├── db_impl.cc
├── db_impl.h
├── dbformat.cc
├── dbformat.h
├── memtable.cc
├── memtable.h
├── version_set.cc
├── version_set.h
├── version_edit.cc
├── version_edit.h
├── write_batch.cc
└── write_batch_internal.cc

27.1 DBImpl

DBImpl

可以理解为：

LevelDB数据库核心实现。

负责：

• Put
• Get
• Delete
• Write
• Background Compaction
• Snapshot
• Iterator

27.2 MemTable

核心：

MemTable

↓

SkipList

源码逻辑：

MemTable

↓

InternalKey

↓

SkipList

27.3 VersionSet

负责：

Version
VersionEdit
MANIFEST
Compaction

可以理解为：

管理当前数据库由哪些SSTable组成。

27.4 Table

负责：

SSTable

包括：

Block

BlockBuilder

BlockIterator

Table

TableBuilder

第二十八章 C++使用LevelDB

下面给出一个最基本的使用示例。

28.1 创建数据库

#include <leveldb/db.h>
#include <iostream>

int main()
{
leveldb::DB* db = nullptr;

leveldb::Options options;

options.create_if_missing = true;

leveldb::Status status =
leveldb::DB::Open(
options,
"./testdb",
&db
);

if(!status.ok())
{
std::cerr
<< status.ToString()
<< std::endl;

return –1;
}

std::cout
<< "Database opened"
<< std::endl;

delete db;

return 0;
}

28.2 Put

leveldb::Status status =
db->Put(
leveldb::WriteOptions(),
"name",
"qtree"
);

内部：

Put

↓

WAL

↓

MemTable

28.3 Get

std::string value;

leveldb::Status status =
db->Get(
leveldb::ReadOptions(),
"name",
&value
);

if(status.ok())
{
std::cout
<< value
<< std::endl;
}

28.4 Delete

db->Delete(
leveldb::WriteOptions(),
"name"
);

内部并不是：

直接删除SSTable

而是：

写入Deletion Marker

即：

Tombstone

之后由Compaction处理。

28.5 WriteBatch

多个操作可以：

leveldb::WriteBatch batch;

batch.Put(
"name",
"qtree"
);

batch.Put(
"language",
"C++"
);

batch.Delete(
"old_key"
);

db->Write(
leveldb::WriteOptions(),
&batch
);

逻辑：

WriteBatch

+———-+
| Put A |
| Put B |
| Delete C |
+———-+

↓

WAL

↓

MemTable

相比逐个写入：

db->Put(...);
db->Put(...);
db->Put(...);

批量操作可以减少：

Lock

WAL

同步

次数。

第二十九章 LevelDB为什么适合AI/视觉数据

LevelDB与LMDB都可以用于：

图片

点云

Tensor

训练样本

但是侧重点不同。

LMDB

更加适合：

数据准备完成

↓

大量读取

例如：

训练集

500GB

写一次

读取数百万次

LevelDB

更适合：

数据不断产生

不断更新

不断写入

例如：

工业设备

↓

传感器

↓

实时数据

↓

持续写入

第三十章 LMDB vs LevelDB

这是整个系列非常重要的对比。

第三十一章 Facebook为什么发展RocksDB

LevelDB出现以后，很多公司开始使用。

其中非常重要的一个项目：

Meta Platforms（Facebook）。

Facebook基于LevelDB的思想开发了：

RocksDB。

RocksDB并不是简单：

LevelDB改名

而是：

在LSM思想基础上进行了大量工程化和性能扩展。

31.1 为什么需要RocksDB？

Facebook面对的是：

巨大数据量

高并发

高写入吞吐

SSD

多核CPU

LevelDB原始设计：

简单

轻量

易维护

但是对于Facebook的大规模场景：

需要进一步优化。

31.2 RocksDB重点改进

RocksDB增加和强化了很多能力，例如：

多种Compaction策略

更好的并发

Column Families

Block Cache

Bloom Filter优化

Prefix Bloom Filter

压缩算法

SSD优化

Rate Limiter

后台Flush

后台Compaction

31.3 Column Family

LevelDB：

一个数据库

RocksDB：

可以：

Database

├── Column Family A
├── Column Family B
└── Column Family C

例如：

metadata

images

features

results

分别管理。

31.4 RocksDB与LevelDB关系

可以理解为：

LSM Tree
|
|
LevelDB
|
|
RocksDB
|
+———+———+
| | |
SSD优化 并发优化 Compaction优化

LevelDB：

更像是LSM Tree的经典教学实现和轻量工程实现。

RocksDB：

更像是面向高性能生产环境的大规模LSM存储引擎。

第三十二章 LevelDB完整数据流

现在把LevelDB整个流程串起来。

写入

Put
|
+——-+——-+
| |
v v
WAL MemTable
|
|
Full?
|
Yes
|
v
Immutable MemTable
|
v
Flush
|
v
L0
|
v
Compaction
|
v
L1
|
v
L2
|
v
L3

32.1 读取

Get
|
v
MemTable
|
Not Found
|
v
Immutable MemTable
|
Not Found
|
v
L0
|
Bloom Filter
|
Maybe Exist
|
v
Index Block
|
v
Data Block
|
v
Value

32.2 崩溃恢复

Crash
|
v
Restart
|
v
Read CURRENT
|
v
Read MANIFEST
|
v
Recover Version
|
v
Read WAL
|
v
Replay Records
|
v
Rebuild MemTable
|
v
Database Ready

第三十三章 LevelDB真正解决的问题

LevelDB的核心并不是：

简单地把数据存到磁盘

而是解决：

如何把大量随机写转换成高效的顺序写，同时保持可接受的读取性能。

它的答案是：

Random Write

↓

MemTable

↓

WAL

↓

Sequential Flush

↓

SSTable

↓

Compaction

↓

Sorted Levels

第三十四章 LSM Tree的本质

如果只记住LevelDB一个概念：

记住：

LSM Tree不是一棵传统意义上始终保持完整结构的树，而是一组不同层次、不同生命周期的有序数据文件，通过Compaction逐渐合并成更稳定的结构。

它更像：

Memory

MemTable
|
v
L0
|
v
L1
|
v
L2
|
v
L3

数据：

不断向下沉淀

第三十五章 LMDB与LevelDB的设计哲学

最后把前两篇联系起来。

LMDB

B+Tree

|
Copy-On-Write
|
mmap
|
MVCC

思路：

尽可能让读取直接访问已经组织好的数据。

LevelDB

MemTable

|

WAL

|

SSTable

|

Compaction

|

多层Lsm

思路：

先让写入尽可能快，再通过后台Compaction整理数据。

第三十六章 一张图理解LMDB和LevelDB

Key-Value Database
|
+————+————+
| |
v v
LMDB LevelDB
| |
B+Tree LSM Tree
| |
Copy-On-Write MemTable
| |
mmap WAL
| |
MVCC SSTable
| |
多Reader Bloom Filter
| |
单Writer Compaction
| |
快读取 高写吞吐

可以把它们概括成：

LMDB：

写的时候维护树
→ 读取非常直接

LevelDB：

写的时候先积累
→ 后台慢慢整理

这也是：

B+Tree

与：

LSM Tree

最核心的设计差异。

第三十七章 本篇总结

LevelDB涉及的核心技术可以串成一条完整链路：

Write
|
v
WAL
|
v
MemTable
|
v
SkipList
|
| Full
v
Immutable MemTable
|
| Flush
v
SSTable
|
+—- Data Block
|
+—- Index Block
|
+—- Meta Block
|
+—- Footer
|
v
L0
|
| Compaction
v
L1
|
| Compaction
v
L2
|
v
L3

读取：

Get
|
v
MemTable
|
v
Immutable
|
v
Bloom Filter
|
v
Index Block
|
v
Data Block
|
v
Value

恢复：

CURRENT
|
v
MANIFEST
|
v
Version
|
v
WAL
|
v
MemTable

因此，LevelDB实际上把几个非常重要的数据库技术组合到了一起：

SkipList
WAL
LSM Tree
SSTable
Bloom Filter
Compaction
Snapshot
Iterator

这些技术后来成为现代高性能KV数据库的基础。

而 RocksDB、Pebble、TiKV 等后续系统，本质上都在不同程度上沿用了这套思想，并针对并发、SSD、Compaction、缓存、分布式场景继续优化。