LevelDB

LevelDB 学习笔记

---

概述

内存数据结构

LevelDB 的内存中维护了 2 个跳跃列表，一个是只读的 rtable，一个是可修改的 wtable。

写入数据到 wtable ，待 wtable 的大小达到一个阈值，LevelDB 将它凝固成只读的 rtable，同时生成一个新的 wtable 继续接受写操作。
rtable 将会被异步线程刷到磁盘中。
Get 操作会优先查询 wtable，如果找不到就去 rtable 中去找，rtable 如果还找不到，再去磁盘文件里去找。

磁盘数据结构

LevelDB 在磁盘上存储了很多 sst 文件，sst 表示 Sorted String Table，文件里所有的 Key 都会有序的。每个文件都会对应一个层级，每个层级都会有多个文件。底层的文件内容来源于上一层，最终它们都会来源于 0 层文件，而 0 层的文件又来源于内存里的 rtable 序列化。一个 rtable 会被序列化为一个完整的 0 层文件。

从内存的 rtable 序列化成 0 层 sst 文件称之为「Minor Compaction」，从 n 层 sst 文件下沉到 n+1 层 sst 文件称之为「Major Compaction」。之所以这样区分是因为 Minor 速度很快耗费资源少，将 rtable 完整地序列化为一个 sst 文件就完事了。而 Major 会涉及到多个文件之间的合并操作，耗费资源多，速度慢。层级越深的文件总容量越大，在 LevelDB 源码里有一个层级容量公式，容量和层级呈指数级关系。
capacity = level > 0 && 10^(level+1) M

这就是为什么叫 Level DB

鸿篇巨制 —— LevelDB 的整体架构
https://mp.weixin.qq.com/s/rN6HX2VzsRi3_EKXYKuJAA

---