LSM树介绍

LSM树介绍

LSM树**(Log-Structured-Merge-Tree)**的核心是利用顺序写来提高写性能，但是分层结构设计会稍微降低读性能。

LSM树会将所有的数据插入、修改、删除等 *** 作记录(注意是 *** 作记录)保存在内存之中，当此类 *** 作达到一定的数据量后，再批量地顺序写入到磁盘当中。

存储结构

1. Active MemTable

MemTable是在内存中的数据结构，用于保存最近更新的数据，会按照Key有序地组织这些数据，LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义，例如Hbase使跳跃表来保证内存中key的有序。

因为数据暂时保存在内存中，内存并不是可靠存储，如果断电会丢失数据，因此通常会通过WAL(Write-ahead logging，预写式日志)的方式来保证数据的可靠性。

2. Immutable MemTable

当MemTable达到一定大小后，会转化成Immutable MemTable。Immutable MemTable是将转MemTable变为SSTable的一种中间状态。写 *** 作由新的MemTable处理，在转存过程中不阻塞数据更新 *** 作。

3. SSTable(Sorted String Table)

有序键值对集合，是LSM树组在磁盘中的数据结构。为了加快SSTable的读取，可以通过建立key的索引以及布隆过滤器来加快key的查找。

1. 冗余存储：对于某个key，实际上最新的那条记录以外，其它的记录都是冗余无用的，但是依旧占用了存储空间，因此需要进行Compact *** 作清楚冗余记录；
2. 读效率低下：需要从最新的数据向前倒序查询，直到找到某个key的记录，最坏情况下需要查询完所有的SSTable。

寧Compact策略

1. size-tiered策略

保证每层SSTable的大小相近，同时限制每一层SSTable的数量。如上图，每层限制SSTable为N，当每层SSTable达到N后，则触发Compact *** 作合并这些SSTable，并将合并后的结果写入到下一层成为一个更大的sstable。

当层数达到一定数量时，最底层的单个SSTable的大小会变得非常大。并且size-tiered策略会导致空间放大比较严重。即使对于同一层的SSTable，每个key的记录是可能存在多份的，只有当该层的SSTable执行compact *** 作才会消除这些key的冗余记录。

2. leveled策略

采用分层思想，每一层限制总文件的大小。

leveled每一层切分为多个大小相近的SSTable，在同一层的SSTable是有全局有序的，一个key在每一层最多只有一个记录，不存在冗余记录。

Compact流程

1. L1的总大小超过了L1本身大小限制；
2. 此时就会从L1选择一个文件，然后将其与L2中有交集部分进行合并，生成的文件会放到L2；

L1第二SSTable的key的范围覆盖了L2中前三个SSTable，那么就需要将L1中第二个SSTable与L2中前三个SSTable执行Compact *** 作。

3. 依次向下进行Compact。

多个不相干的合并是可以并发进行的：

leveled策略相较于size-tiered策略来说，每层内key是不会重复的，即使是最坏的情况，除开最底层外，其余层都是重复key，按照相邻层大小比例为10来算，冗余占比也很小。因此空间放大问题得到缓解。但是写放大问题会更加突出。举一个最坏场景，如果LevelN层某个SSTable的key的范围跨度非常大，覆盖了LevelN+1层所有key的范围，那么进行Compact时将涉及LevelN+1层的全部数据。