# Log Structured Merge (LSM) Tree & Usages in KV Stores

## Background

数据库中的各种奇技淫巧，实际上都来自于内存与磁盘的读写模式和性能区别。

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-XvaiOI60h2yO9SqtJ%2F-M-YX9ZgBW_eEulHKiXa%2FScreen%20Shot%202020-02-08%20at%202.41.48%20PM.jpg?alt=media\&token=8af1c24c-b2e9-444f-9530-fab78eba876b)

总结如下表：

|      Memory      |        Disk       |
| :--------------: | :---------------: |
| byte-addressable | block-addressable |
|       fast       |        slow       |
|     expensive    |       cheap       |

当数据库中的数据无法一次性装入内存时，数据的读写就可能需要从内存穿透到磁盘。在 OLTP 场景下，每次事务写入和读取的数据数量都不大。但因为磁盘是块存储设备，无论是否需要，写入和读取都以块 (block) 为单位：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-XvaiOI60h2yO9SqtJ%2F-M-YZlHLWdk7CexN8YwF%2FScreen%20Shot%202020-02-08%20at%202.53.16%20PM.jpg?alt=media\&token=751e18e1-868a-46ed-827c-f994026ebb1a)

这就导致许多不必要的数据传输。除此之外，在磁盘中连续读取或写入相邻的数据块比随机的数据块效率高。因此数据库在组织数据、索引时，为了减少不必要的 I/O，同时提高 I/O 的效率，就需要尽可能做到：

* 让具有局部性的数据、索引在磁盘上相邻存储
* 让具有局部性的数据、索引批量写入到磁盘中

从而达到两个目的：

* 读出的数据都是需要的
* 写入的数据都是有用的

## B+ Tree

B+ tree 作为数据库索引，已经被许多成熟的关系型数据库所验证。如下图所示：

![ref: https://janzhou.org/2015/bf-tree-approximate-tree-indexing.html](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-Yar5_d-lrTCgfIt11%2F-M-Ycfwmw0MX_p19VQSg%2FScreen%20Shot%202020-02-08%20at%203.10.21%20PM.jpg?alt=media\&token=aa6689ba-6d50-4e87-b3a2-215926db2484)

得益于其矮胖的平衡树形结构，且将所有数据置于叶子节点，B+ 树的读取性能好且稳定。但它的劣势在于，更新数据时成本较高，不仅要更新数据，还要更新索引。如果表中有多个索引，则都要更新，更新每个索引时还可能更新多个节点，因此写数据的性能在一些写要求苛刻的场景下并不能满足要求。

详见 [Tree Indexes](https://zhenghe.gitbook.io/open-courses/cmu-15-445-645-database-systems/tree-indexes)

## LSM Tree

在键值数据库场景下，相较于 B+ 树，LSM 树能够提供更高效的写性能。LSM 树的基本思路就是批量写数据，即先将需要写入的数据放在内存中，等到达一定容量时再写入磁盘。其基本结构如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-Yar5_d-lrTCgfIt11%2F-M-Ym_mMM3Fu-tawDx4Y%2FScreen%20Shot%202020-02-08%20at%203.53.38%20PM.jpg?alt=media\&token=b556d0f5-90db-4895-8b39-5d0b8453bb2a)

### Buffer

在 buffer 中存储着最新写入的键值对数据，这些数据通常按照键的顺序存储在相应的有序数据结构中，如跳表。同时 Buffer 也是数据查询的入口，存储着最新鲜的数据，或者数据的最新版本。

### Sorted String Table (SST)

当 Buffer 中的数据容量到达一定阈值时，会被顺序地写入磁盘中。磁盘中的数据分为多个层次，每层的数据容量指数递增。每层数据又可以继续被划分为一个或多个 SST，每个 SST 中的数据按顺序排列。且同一层级中的多个 SST 之间的键数据通常不会有交集。每层数据量大小都有限制，当数据量达到阈值时，该层的某个 SST 需要与下一层的若干个 SST 合并 (merge)，流入下一层中。因此图中越上层的数据越新、越下层的数据量越大。

通常认为 SST 是不可变 (Immutable) 的数据结构，所有数据更新都通过写入新的 SST 实现，而所有合并操作也是通过生成新的 SST 实现。这种方式对实现数据库的多版本并发控制 (MVCC) 比较友好。

### Writes

写入键值数据时，先将数据插入放到内存中的缓存 (buffer) 数据结构中，写入请求就可以返回响应。这个过程完全在内存中，因此效率很高。这里的写入操作包含插入、更新和删除，对于 LSM Tree 来说，更新和删除也是插入新的键值对，只不过删除存放的值是一个删除标记。

需要注意的是，大部分数据库为了保证 durability，都会将操作日志写入 WAL (write-ahead log) 中，因此这里实际上每次写数据，都有日志落盘。但因为日志是 append-only 的结构，因此这种写入的效率通常很高。

### Merge (Compaction)

上文提到，disk 中每层数据都有容量限制，当 L 层数据超过阈值时，需要将 L 层的某个 SST 与 L+1 层中键的范围与该 SST 有重叠的多个 SST 合并，产生新的一组 SST 存放在 L+1 层中。如果此时 L+1 层中的数据容量也达到阈值，则会触发连续的合并。

在合并的过程中，相同键的值会被合并，只留下最新的值或者被删除，因此合并的过程也是压缩 (compaction) 的过程。

### Lookups

由于上层的数据比下层的新，因此单条数据的查询首先从 buffer 开始，然后到 L0，L1，...，Ln，在每层数据查询时可以使用二分查找。范围查询也类似，可能需要查询多层数据。这种结构对于具有时间局部性的数据效率更高。

有许多优化手段可以避免每次查询都在每层的每个 SST 上执行二分查找。最常见的有两种，fence pointers 和 Bloom filters。

#### fence pointers

fence pointers 的思路就是记录每个 SST 中建的最大值和最小值，由于每层中的多个 SST 的键值范围互相不重叠，这样对于单个键的查询，就能将查找范围缩小到某一个 SST 中。

#### Bloom filters

bloom filter 则是在 fence pointers 之前的一层过滤器，通过其较低的 FP(false positive)，将大多数不必要的查询拒之门外。

整个数据查询的架构如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-Yar5_d-lrTCgfIt11%2F-M-Z2mfZW1yUNEnqI3u-%2FScreen%20Shot%202020-02-08%20at%205.08.36%20PM.jpg?alt=media\&token=d89b9257-a789-429e-b176-d0f113ea82dc)

### Tiering & Leveling

在 LSM 树的实现中，合并时间点的选择决定了该实现的读写性能取舍。通常合并地越频繁，读取数据所涉及的 SST 数量越少，读性能越好，与此同时写操作的放大效应越大，单条数据被合并的次数越多，写性能越差。

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-Z2z3al8j6tz-1SD_x%2F-M-Z9hkFWxgu5KSt2hAZ%2FScreen%20Shot%202020-02-08%20at%205.39.02%20PM.jpg?alt=media\&token=6703f6f5-3caf-4807-83ad-e1ade339b2cc)

在 Tiering 中，每一层数据有多个 SST；在 Leveling 中，每一层数据通常只有一个 SST：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-Z2z3al8j6tz-1SD_x%2F-M-ZAezOD81BAMANvsKG%2FScreen%20Shot%202020-02-08%20at%205.43.11%20PM.jpg?alt=media\&token=a8912238-62c4-46e3-94bb-d60c68db916c)

其中两层之间的容量比例是很重要的参数，记为 R。R 越大，则层数越少；R 越小，则层数越多。数据的总层数为 $$\log\_{R}N$$ 。当 R 很小时，Tiering 与 Leveling 的效果趋于一致。通常 Tiering 中的 R 比较大，而 Leveling 的 R 比较小，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-Z2z3al8j6tz-1SD_x%2F-M-ZC1SNfqo6AMJ39QVu%2FScreen%20Shot%202020-02-08%20at%205.49.09%20PM.jpg?alt=media\&token=c793c0df-549a-49c7-8f13-af9774df2aba)

考虑极端情况：当 R 很小时，相邻两层数据容量差别小，每层数据就是一个 sorted array，在每层中查找数据只需一次二分查找，这种情况下读性能好；当 R 很大时，每层数据约等于没有顺序，就像日志一样，这种情况下写性能好。

很自然的，不同业务场景对读写性能有不同的需求，因此在各个 R 上都有相应的键值数据库存在：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-Z2z3al8j6tz-1SD_x%2F-M-ZCwdqw9C_YoiAQ9he%2FScreen%20Shot%202020-02-08%20at%205.53.09%20PM.jpg?alt=media\&token=bd0d4f0b-3da9-4de5-b4ea-cc25df8a8b7b)

## Case Study: couchbase/moss

moss 是由 couchbase 的工程师开发的键值数据库，本节的 case study 来自于 Marty Schoch 在 GopherConn 2017 上的分享：[Building a High-Performance Key/Value Store in Go](https://www.youtube.com/watch?v=ttebJcN5bgQ)。

### General Purpose Key-Value Stores

站在 Go 语言工程师的角度上，通用键值数据库中的 key 和 value 就是 byte slice：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-ZyU66hrCxamFg90JD%2F-M-_-lnU7L4gJwvYjzvA%2FScreen%20Shot%202020-02-08%20at%209.35.08%20PM.jpg?alt=media\&token=c77ef856-c8de-4588-b7d6-3cd606f54f0f)

通用键值数据库通常需要支持：

1. Get/Set/Delete Values by Key
2. Iterate Ranges of Key-Value Pairs
3. Atomic Batch Updates
4. Isolated Read Snapshots
5. Persistence to Disk

1， 2， 3， 5 项都容易理解，Isolated Read Snapshots 其实就是 MVCC，即当用户开始遍历键值数据时，之后的数据更新对当前的遍历不可见。

### Special Purpose Key-Value Store

moss 团队需要的并非一个通用键值数据库，他们有特殊的性能关注点：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-ZyU66hrCxamFg90JD%2F-M-_05cOIkJFi0I1t9DO%2FScreen%20Shot%202020-02-08%20at%209.36.38%20PM.jpg?alt=media\&token=d10140bd-1b94-42e4-ba12-65aa909c20bd)

1. 写吞吐
2. 写入数据后到能查询之间的时延

### Off-The-Shelf Solutions

在决定开发自己的键值数据库之前，moss 工程师也调研了一些市面上开源的数据库，如 BoltDB, RocksDB, GoLevelDB 以及 Badger。

#### BoltDB

BoltDB 是 Go 语言编写的键值数据库。BoltDB 通过单线程解决并发控制解决方案，支持可序列化事务隔离，通过成熟的 B+ 树来解决内存、磁盘读写模式的不匹配问题，BoltDB 已经在许多商业系统中成功运用，其可靠性也得到了验证。它的优势在于极高的读效率，但由于它使用 B+ 树，天然地其写性能要弱于使用 LSM 树的键值数据库解决方案。

有关 BoltDB 的分析可参考本人的项目 [ZhengHe-MD/learn-bolt](https://github.com/ZhengHe-MD/learn-bolt)。

#### RocksDB

RocksDB 是基于 google 的 LevelDB 二次开发的键值数据库，其内部采用了 LSM 树设计，在 Write-Amplification-Factor (WAF)、Read-Amplification-Factor (RAF) 和 Space-Amplification-Factor (SAF) 中取得更灵活的权衡，它支持多线程数据压缩，能够处理 TB 级别数据。相较于 BoltDB，RocksDB 有更好的读写性能平衡，但它使用 C++ 编写，使得 moss 工程师需要利用 cgo 来跨越 Go 和 C++ 的边界，且这一层边界开销也有一定的性能损耗，因此 moss 团队没有采用 RocksDB。

#### GoLevelDB

GoLevelDB 是 LevelDB 的 Go 语言原生实现，其同样采用 LSM 树设计，但经过反复调试，moss 团队发现它无法达到其读写性能的高要求，因此放弃。

#### Badger

在 moss 团队开始寻找键值数据库解决方案时，badger 项目还未开源，因此无法验证其是否满足需求。

### Design Philosophy

Rob Pike 在 Notes on C Programming 说道：

> Rule3: Fancy algorithms are slow when n is small, and n is usually small. Fancy algorithms have big constants. Until you know that n is frequently going to be big, don't get fancy.
>
> Rule4: Fancy algorithms are buggier than simple ones, and they're much harder to implement. Use simple algorithms as well as simple data structures.

Dave Cheney 提到：

> Simplicity cannot be added later

moss 团队的设计理念非常明确：能简则简。

### Interface Design

#### Collection

在 moss 中，每个数据库就是一个 Collection，它只暴露两个接口：

```go
type Collection interface {
    ExecuteBatch(b Batch) error
    Snapshot() (Snapshot, error)
}
```

它的设计十分精简：

* 所有写数据操作都是一个 Batch
* 所有读数据操作都从一个 Snapshot 上发起

#### Batch

```go
type Batch interface {
    Set(key, value []byte) error
    Delete(key []byte) error
}
```

#### Snapshot

```go
type Snapshot interface {
    Get(key []byte) ([]byte, error)
    Iterator(start, end []byte) (Iterator, error)
}
```

### Basic Idea

moss 的解决方案很简单，用户写入一批键值数据 (这里忽略其值)，如下图所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-_1xBgFU6daN-MUOVc%2F-M-_3_CzuEeARfs7x-Nw%2FScreen%20Shot%202020-02-08%20at%209.51.50%20PM.jpg?alt=media\&token=b27877a3-26d9-4086-ad77-a2daa35811b0)

如果可以将这批数据按 key 排序：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-_1xBgFU6daN-MUOVc%2F-M-_43vKkQJNjK0d-1CB%2FScreen%20Shot%202020-02-08%20at%209.53.35%20PM.jpg?alt=media\&token=036b98b0-a0e3-446f-8234-247d09714f31)

就可以很方便地查询数据：

* 查询单个键：二分查找
* 范围查询：二分查找 + 循环遍历

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-_1xBgFU6daN-MUOVc%2F-M-_4ReQaPZkLAo3ggos%2FScreen%20Shot%202020-02-08%20at%209.55.37%20PM.jpg?alt=media\&token=6dbb3a90-fd09-464c-9849-38bb4a3249d4)

### Data Layout

将用户插入的一批数据成为 Batch，在数据库内部排序后称为 Segment：

```go
type segment struct {
    data []byte
    meta []uint64
}
```

假设用户执行：

```go
Set([]byte("name"), []byte("marty"))
```

接收该键值对的 segment 会将 "name" 和 "marty" 依次 append 到 data 之后，并在 meta 中增加 2 个 uint64 的元数据：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-_5msUVRxORheqeRwQ%2F-M-_63mxqeEpnvX0nLZ8%2FScreen%20Shot%202020-02-08%20at%2010.02.33%20PM.jpg?alt=media\&token=8255bd2c-9068-47cd-99f5-cd71a77cfbe6)

* 20 表示键值数据在 data 中的偏移量
* s 表示操作名称 (set)
* 4、5 分别表示键和值的长度

元数据中的两个 uint64 具体结构如下：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-_5msUVRxORheqeRwQ%2F-M-_6fPtxAqy4czLfV3i%2FScreen%20Shot%202020-02-08%20at%2010.05.24%20PM.jpg?alt=media\&token=793cd79e-d825-4e28-a2da-dacccfe55d6e)

这样存储的好处是，排序时只需要调整 meta，而无需修改 data。

显然用户会向数据库中插入许多 batch，每当插入新的 batch 时，moss 数据库就先将 batch 原地排序，然后插入到 segmentStack 中，并用锁来保护 segmentStack 的并发安全：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-_5msUVRxORheqeRwQ%2F-M-_98VpRI9ul1Uj4l_G%2FScreen%20Shot%202020-02-08%20at%2010.16.10%20PM.jpg?alt=media\&token=19af6a03-7058-42df-9e39-01461c4228c9)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-_5msUVRxORheqeRwQ%2F-M-_9Ipyf7FR7CDdip_X%2FScreen%20Shot%202020-02-08%20at%2010.16.46%20PM.jpg?alt=media\&token=332d2fa5-817e-4182-9d4a-e1147f36d207)

在 segmentStack 中，新的 segment 在栈顶，老的 segment 在栈底。这种结构与 LSM 树如出一辙，新的数据在栈顶，老的数据在栈底。

### Operation

#### Get

当用户要查询单个键时，就从栈顶的 segment 开始，依次对每个 segment 执行二分查找，直到找到键值数据或遍历完整个 segmentStack。

#### Iteration

利用小根堆，将每个 segment 中排序最小的元素开始放入小根堆中：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-_5msUVRxORheqeRwQ%2F-M-_AfDbQdU-Y4xQhDUP%2FScreen%20Shot%202020-02-08%20at%2010.22.51%20PM.jpg?alt=media\&token=eabef75b-a145-4d1a-9d95-ce8aa6501391)

读取堆顶元素，然后从相应的 segment 中补进新元素，直到遍历完成所有 segments，也就完成了 iteration 的操作。

#### Atomic Batches

利用锁来保护 segmentStack 的并发安全即可。

#### Isolated Snapshots

在 moss 眼中，所有 segments 都是 immutable 的数据，一旦 batch 变成 segment，该 segment 中的数据就不会再发生变化。这时候支持 Isolated Snapshots/MVCC 就很容易了，因为 segmentStack 保存的是对 segment 的指针，只要复制一份 segmentStack 即可满足要求。新到来的写入操作不会改变已存在的 segment。

#### Background Merger

当然，如果一直往 segmentStack 中压入 segment，前者会变得很长，数据读取的效率会下降，这时候就需要合并：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-_CDmSNB8GPtrY42Y-%2F-M-c1P249FaOfzO36aCu%2FScreen%20Shot%202020-02-09%20at%2011.41.05%20AM.jpg?alt=media\&token=7b4ca7f3-7748-4ac0-9ef5-c12eddf2ade8)

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-_CDmSNB8GPtrY42Y-%2F-M-c1Z6vgfOc0EWAzJQ9%2FScreen%20Shot%202020-02-09%20at%2011.41.53%20AM.jpg?alt=media\&token=a47eebb7-d2a7-43b9-b596-b8d79b3b74b3)

### Database File

moss 的数据库文件形式为 append-only，内部数据存储的内容如下所示：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-c3ib1GjENlamoAoTR%2F-M-c4CQhbAzaKf1a0U1Z%2FScreen%20Shot%202020-02-09%20at%2011.53.27%20AM.jpg?alt=media\&token=9935ffbb-79c2-4c9d-b739-33ea7f8421e6)

其中 footer 中保存着指向 segments 偏移量的指针，且每个 footer 都保存对之前所有 segments 的指针。数据库启动时，会打开该文件，从后往前找到第一个合法的 Footer。如果最后一个 Footer 没有完整写入，数据库会找到更早的 Footer，当然这会丢失一些数据，但不影响数据库的正常运行。另外考虑到 WAL，数据的持久性依然可以得到保障。

从数据库读取文件后，moss 会将相应的 segments mmap 到内存中，让操作系统来处理内存管理逻辑：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-c3ib1GjENlamoAoTR%2F-M-c6KseGG-KjBSq3S8i%2FScreen%20Shot%202020-02-09%20at%2012.02.45%20PM.jpg?alt=media\&token=daa80180-9f0f-4f09-be8b-4954176cf67e)

此外，moss 还会利用 background merger 将文件中的 segments 合并。类似地，所有 segments 都是 immutable 的数据，每次合并都将生成新的数据文件：

![](https://1008303647-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LMjQD5UezC9P8miypMG%2F-M-c3ib1GjENlamoAoTR%2F-M-c7GjFf-8lb8l1M9Ow%2FScreen%20Shot%202020-02-09%20at%2012.06.53%20PM.jpg?alt=media\&token=ff4df9b5-7e1b-4b04-a056-932f5114c656)

从而保障 Isolated Read Snapshots 正常进行。

## References

* Projects
  * [github: couchbase/moss](https://github.com/couchbase/moss)
  * [github: google/leveldb](https://github.com/google/leveldb)
    * [doc/impl.md](https://github.com/google/leveldb/blob/master/doc/impl.md)
  * [github: facebook/rocksdb](https://github.com/facebook/rocksdb)
  * [github: syndtr/goleveldb](https://github.com/syndtr/goleveldb)
* Books
  * [Getting Started with LevelDB](https://www.amazon.com/Getting-Started-LevelDB-Andy-Dent/dp/1783281014)
* Blogs
  * [SSTable and Log Structured Storage: LevelDB](https://www.igvita.com/2012/02/06/sstable-and-log-structured-storage-leveldb/)
* Courses
  * [CS265: Big Data Systems: An LSM-Tree Based Key-Value Store](http://daslab.seas.harvard.edu/classes/cs265/project.html)
* Videos
  * [Youtube: Scaling Write-Intensive Key-Value Store by Microsoft Research](https://www.youtube.com/watch?v=b6SI8VbcT4w)
  * [Youtube: Building a High-Performance Key-Value Store in Go by Marty Schoch](https://www.youtube.com/watch?v=ttebJcN5bgQ) & [slides](https://speakerdeck.com/mschoch/value-store-in-go?slide=3)