记录于 2023.4.6，源于 hbase 原理的学习。
LSM 的核心思想#
LSM 树有以下三个重要组成部分：
-
MemTable
MemTable 是在内存中的数据结构，用于保存最近更新的数据，会按照 Key 有序地组织这些数据，LSM 树对于具体如何组织有序地组织数据并没有明确的数据结构定义，例如 Hbase 使跳跃表来保证内存中 key 的有序。
因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过 WAL (Write-ahead logging，预写式日志) 的方式来保证数据的可靠性。
-
Immutable MemTable
当 MemTable 达到一定大小后，会转化成 Immutable MemTable。Immutable MemTable 是将转 MemTable 变为 SSTable 的一种中间状态。写操作由新的 MemTable 处理，在转存过程中不阻塞数据更新操作。
-
SSTable(Sorted String Table)
有序键值对集合，是 LSM 树组在磁盘中的数据结构。为了加快 SSTable 的读取，可以通过建立 key 的索引以及布隆过滤器来加快 key 的查找。
LSM 树的 Compact 策略#
主要介绍两种基本策略：size-tiered 和 leveled。
重要的概念
- 读放大：读取数据时实际读取的数据量大于真正的数据量。例如在 LSM 树中需要先在 MemTable 查看当前 key 是否存在，不存在继续从 SSTable 中寻找。
- 写放大：写入数据时实际写入的数据量大于真正的数据量。例如在 LSM 树中写入时可能触发 Compact 操作，导致实际写入的数据量远大于该 key 的数据量。
- 空间放大：数据实际占用的磁盘空间比数据的真正大小更多。上面提到的冗余存储，对于一个 key 来说，只有最新的那条记录是有效的，而之前的记录都是可以被清理回收的。
size-tiered 策略#
size-tiered 策略保证每层 SSTable 的大小相近，同时限制每一层 SSTable 的数量。如上图，每层限制 SSTable 为 N，当每层 SSTable 达到 N 后，则触发 Compact 操作合并这些 SSTable，并将合并后的结果写入到下一层成为一个更大的 sstable。
由此可以看出，当层数达到一定数量时，最底层的单个 SSTable 的大小会变得非常大。并且 size-tiered 策略会导致空间放大比较严重。即使对于同一层的 SSTable，每个 key 的记录是可能存在多份的，只有当该层的 SSTable 执行 compact 操作才会消除这些 key 的冗余记录。
leveled 策略#
leveled 策略也是采用分层的思想，每一层限制总文件的大小。
但是跟 size-tiered 策略不同的是，leveled 会将每一层切分成多个大小相近的 SSTable。这些 SSTable 是这一层是全局有序的，意味着一个 key 在每一层至多只有 1 条记录，不存在冗余记录。
leveled 策略相较于 size-tiered 策略来说，每层内 key 是不会重复的，即使是最坏的情况，除开最底层外，其余层都是重复 key，按照相邻层大小比例为 10 来算，冗余占比也很小。因此空间放大问题得到缓解。但是写放大问题会更加突出