本文针对RocksDB的基本概念进行总结

1. 主要概念

1.1. LSM Tree介绍

       B+树读效率高而写效率差；log型文件操作写效率高而读效率差；因此要在排序和log型文件操作之间做个折中，于是就引入了log-structed merge tree模型，通过名称可以看出LSM既有日志型的文件操作，提升写效率，又在每个sstable中排序，保证了查询效率

LSM-tree起源于 1996 年的一篇论文《The Log-Structured Merge-Tree (LSM-Tree)》，后续发展如下：

FAST'16 的《WiscKey: Separating Keys from Values in SSD-conscious Storage》

PebblesDB: Building Key-Value Stores using Fragmented Log-Structured Merge Trees（SOSP 2017）

LSM-tree 是专门为 key-value 存储系统设计的，key-value 类型的存储系统最主要的就两个核心功能，put（k，v）：写入一个（k，v），get（k）：给定一个 k 查找 v。

LSM-tree 最大的特点就是写入速度快，主要利用了磁盘的顺序写，pk掉了需要随机写入的 B-tree

LSM-tree 被用在各种键值数据库中，如 LevelDB，RocksDB，还有分布式行式存储数据库 HBase、Cassandra 也用了 LSM-tree 的存储架构。

下图是 LSM-tree 的组成部分，是一个多层结构，就更一个树一样，上小下大。

首先是内存的 C0 层，保存了所有最近写入的 （k，v），这个内存结构是有序的，并且可以随时原地更新，同时支持随时查询。剩下的 C1 到 Ck 层都在磁盘上，每一层都是一个在 key 上有序的结构。

写入流程：追加到写前日志（Write Ahead Log，也就是真正写入之前记录的日志）中，接下来加到 C0 层，然后逐层向下合并即compact

查询流程：在写入流程中可以看到，最新的数据在 C0 层，最老的数据在 Ck 层，所以查询也是先查 C0 层，如果没有要查的 k，再查 C1，逐层查

1.2. LSM Tree读写放大

读写放大（read and write amplification）是 LSM-tree 的主要问题，这么定义的：读写放大 = 磁盘上实际读写的数据量 / 用户需要的数据量。注意是和磁盘交互的数据量才算，这份数据在内存里计算了多少次是不关心的

写放大：实际写入 HDD/SSD 的数据大小和程序要求写入数据大小之比。

             以 RocksDB 的 Level Style Compaction 机制为例，这种合并机制每次拿上一层的所有文件和下一层合并，下一层大小是上一层的 r 倍。这样单次合并的写放大就是 r 倍.  

             WA = data writeen to disc / data written to database

读放大：为了查询一个 1KB 的数据。最坏需要读 L0 层的 8 个文件，再读 L1 到 L6 的每一个文件，一共 14 个文件。而每一个文件内部需要读 16KB 的索引，4KB的布隆过滤器，4KB的数据块（看不懂不重要，只要知道从一个SSTable里查一个key，需要读这么多东西就可以了）。一共 24*14/1=336倍。key-value 越小读放大越大。 RA = number of queries * disc reads

      空间放大（Space Amplification）。因为所有的写入都是顺序写（append-only）的，不是 in-place update ，所以过期数据不会马上被清理掉。

1.3  Column Family

在RocksDB 3.0中加入了Column Family特性，加入这个特性之后，每一个KV对都会关联一个Column Family,其中默认的Column Family是 “default”. Column Family主要是提供给RocksDB一个逻辑的分区.

从实现上来看不同的Column Family共享WAL，而都有自己的Memtable和SST.这就意味着可以很 快速方便的设置不同的属性给不同的Column Family以及快速删除对应的Column Family. 有如下特点：

• 用于在同一个数据库中存储业务中不同的数据

• 起一定的隔离作用

• 不同的Column Family使用不同的SST文件、MemTable存储数据

• 同一个数据库中不同的Column Family使用相同的日志记录写入日志

• 在存在多个Column Family时，单个日志文件的删除条件为此日志文件中的所有写入的Column Family对应的MemTable已被持久化

2. RocksDB的LSM Tree

LSM Tree 被分成三种文件，第一种是内存中的两个 memtable，一个是正常的接收写入请求的 memtable，一个是不可修改的immutable memtable，另外一部分是磁盘上的 SStable （Sorted String Table），有序字符串表，这个有序的字符串就是数据的 key。

SStable 一共有七层（L0 到 L6）。下一层的总大小限制是上一层的 10 倍

2.1. 写流程

1. 将写入操作顺序写入WAL日志中，接下来把数据写到 memtable中（采用SkipList结构实现）

2. MemTable达到一定大小后，将这个 memtable 切换为不可更改的 immutable memtable，并新开一个 memtable 接收新的写入请求

3. 这个 immutable memtable进行持久化到磁盘，成为L0 层的 SSTable 文件

4. 每一层的所有文件总大小是有限制的，每下一层大十倍。一旦某一层的总大小超过阈值了，就选择一个文件和下一层的文件合并。

注意： 所有下一层被影响到的文件都会参与 Compaction。合并之后，保证 L1 到 L6 层的每一层的数据都是在 key 上全局有序的。而 L0 层是可以有重叠的

    写流程的约束：

• 日志文件用于崩溃恢复

• 每个MemTable及SST文件中的Key都是有序的（字符顺序的升序）

• 日志文件中的Key是无序的

• 删除操作是标记删除，是插入操作的一种，真正的删除要在Compaction的时候实现

• 无更新实现，记录更新通过插入一条新记录实现

2.2. 读流程

先查memtable，再查 immutable memtable，然后查 L0 层的所有文件，最后一层一层往下查。