阅读本文之前建议对LSM树有一定的认识。本文将介绍LSM Tree的主流实现，即LevelDB和RocksDB作为KV数据库。

两者对外提供的主要接口基本一致，就是包含以下5个基本操作

  • get(K) 查找key K对应的value
  • put(K,V) 插入键值对（K，V）
  • update(K,V) 查找key K对应的value更新为V
  • delete(K) 删除key K对应的条目
  • scan(K1,K2) 得到从K1到K2的所有key和value

我们将从静态和动态角度去介绍两个数据库
先从LevelDB开始，相对好理解。毕竟RocksDB是在levelDB上做的改进

LeveldDB

接下从静态和动态角度去介绍

静态视角：假想整个系统正在运行过程中（不断插入删除读取数据），此时我们给LevelDb照相，从照片可以看到之前系统的数据在内存和磁盘中是如何分布的，处于什么状态等.
动态视角：了解系统是如何写入一条记录，读出一条记录，删除一条记录的，同时也包括除了这些接口操作外的内部操作比如compaction，系统运行时崩溃后如何恢复系统等等方面。

架构 - 静态视角

内存 （对应LSM的C0）

  • memtable

    • 结构：SKIPLIST ， 和immutable memtable 完全相同。
    • 读写：允许读写
    • 功能：当Memtable写入的数据占用内存到达指定数量，则自动转换为Immutable Memtable，等待Dump到磁盘中，系统会自动生成新的Memtable供写操作写入新数据
    • 删除：并不存在真正的删除操作,删除某个Key的Value在Memtable内是作为插入一条记录实施的，但是会打上一个Key的删除标记，真正的删除操作是Lazy的，会在以后的Compaction过程中去掉这个KV
    • 重启时：会从log中恢复。

  • immutable memtable

    • 正在进行写入磁盘操作的memtable

磁盘中

  • log(WAL)

    • 属于write-ahead-log，每个写入操作，都会往log尾部添加一个完整的kv记录
    • 主作用是故障恢复，可以用于恢复memtable和immutable memtable

  • current
    current指出当前有效的那个manifest是哪个
    随着Compaction进行，sstable变化，manifest会记录这些变化

  • manifest
    记载sst各文件的信息(LEVEL, NAME, MIN_KEY, MAX_KEY)

  • SST文件（Semi-sort table） （对应LSM的C1-N）

    • 文件中key有序存储，存储一个范围(K1,K2)之间的键值对
    • Level 0的 SST之间可能存在key重叠 ， Level 1+ 的SST不会有key重叠
    • 所有文件是一种层级结构，第一层为Level 0，第二层为Level 1，层级逐渐增高，每一层的容量也会增大，这也是称为LevelDB的原因。这level的设计上LevelDB和RocksDB完全一致。其大小关系往往是每个级别差10倍，如下图：

SST文件 (对应LSM的C1-N)

物理布局

逻辑结构

数据存储区

存储实际的key-value，单个block里面内容如下

“重启点”（Restart Point）, 其实是一些指针，为了降低数据冗余 指出Block内容中的一些记录位置。在这条记录开始，不再采取只记载不同的Key部分，而是重新记录所有的Key值。

数据管理区
  • meta block ：记录这个SST文件的一些元信息，比如record个数，数据大小等
  • footer ： 指向（索引）index block的index
  • index block： 指向data block在文件中的地址，用于查找数据在哪个block内

操作 - 动态视角

写 - 插入、 更新、删除数据

  • 插入： 同步操作就是（决定延迟），就是先顺序写入log（内部无序），然后写入memtable。 异步写入后续就是要看compaction。
  • 更新： 当做插入处理。
  • 删除： 不是直接删除，而是加入了一个删除标记

compaction

目的： 完成数据的沉降，同时由于之前的插入、删除操作，数据有很多的冗余。压缩，然后删除掉一些不再有效的KV数据，减小数据规模，减少文件数。

flush (Memtable -> LEVEL0)
  • 触发条件： memtable大小超过阈值
  • 结果： 其过程就是把immutable memtable简单持久化一个新sst
  • 过程：依次写入sst，然后新建索引（所以一个level 0 sst数据大小和immutable memtable是一样的）
  • 注意： 因为不考虑其他sst，所以level0的sst 键会存在会重叠
compaction (Level i -> Level i+1)

就是按文件产生次序轮询，合并之后原文件就失效等待删除，新的文件生效（manifest记录）

  • 触发条件level i 大小或者文件个数超过阈值
  • 过程: 以level i的一个文件为驱动，在 level i 找和level i+1 找存在key重叠的sst，然后滚动合并
    • 当i是0时，因为leveli文件之间存在重叠，所以是leveli和leveli+1的多个文件一起合并。
    • 当i是1时，当因为leveli的sst之间没有重叠，所以就是一个leveli的文件和多个L+1合并
  • 结果图示(i>=1情况)：
  • 合并过程图示（即一个多路归并排序,图中L代表leveli的文件，L+1代表leveli+1的文件）：

读

先内存后磁盘，硬盘从上层至下层。（找到数据就返回，因为level小的里面的记录肯定是最新的）
先在memtable里面找，如果找不到则从磁盘文件中，对于磁盘上的每一个level，查找有三级：

  1. sst定位：优先新鲜(level小的)sst， 唯一特殊的就是level 0不同sst可能会有key重叠，所以要在manifest中找到符合条件的文件，按从新到旧的顺序依次查找。
  2. sst内查找： 先看sst的索引是否已经加载到Cache， 没有就加载，然后定位block
  3. block内查找：先在restart points上找，然后restart points之间顺序查找
缓存 Cache

为了加快查询，数据库都会将数据放入内存，来降低重复访问同一段数据带来的开销。
如：

  1. manifest内容存在缓存中
  2. 打开一个sst时，其索引块也会加载到缓存中
  3. 在一个block内查找时，也会将block加入到缓存

RocksDB

结构和levelDB大同小异，只是多了一些改进

  1. 增加了column family，有了列簇的概念，可把一些相关的key存储在一起
  2. 内存中有多个immute memtalbe，可防止Leveldb中的 write stall
  3. 可支持多线程同时compation，理论上多线程同时comaption会比一个线程compation要快（TODO执行commpactiron的中心在哪）
  4. 支持TTL
  5. flush与compation分开不同的线程池来调度，并具有不同的优先级，flush要优于compation，这样可以加快flush，防止stall
  6. 对SSD存储做了优化，可以以in-memory方式运行
  7. 增加了对 write ahead log（WAL）的管理机制，更方便管理WAL，WAL是binlog文件
  8. 支持多种不同的compaction策略

结构

特性

同LSM Tree，唯一区别在于每一层分成了多个文件。

  • 优点：
    • 写延迟低
    • 访问新数据更快，适合时序、实时存储
    • 空间放大率低
  • 缺点：
    • 写放大、读放大高
    • 读放大
    • 磁盘上修改数据的粒度必须是文件