Open levy5307 opened 3 years ago
https://levy5307.github.io/blog/SLM-DB/
SLM-DB全名Single-Level Key-Value Store with Persistent Memory。是使用了Persistent memory对LSM-tree based存储引擎进行了一系列优化。
LSM-tree的缺点
读放大。由于读放大存在导致读取操作需要遍历LSM-tree多层，比较耗时 写放大。写放大高达十倍至多，占用磁盘空间。
SLM-DB
上图为SLM-DB的整体架构图。其主要使用了Persistent Memory进行了如下优化。
在SLM-DB中，LSM-tree只有一层。对于LevelDB等传统的LSM-tree based数据库，设计成多层的原因在于减少写放大带来的影响。设想如果LSM-tree只有一层（为了高效索引，level 0一定是有序的），当flush一个immutable memtable时，可能level 0中的所有文件都与该immutable memtable有交集，为了维持有序行，此时的compaction将会导致所有的SST文件都牵涉进来，影响太大了。而设计成多层影响则小了很多。而SLM-DB则没有这个问题，其第一层是虽然是无序的，但是通过B+-tree进行了索引，所以在flush时只需要将其放入level 0就可以了，不必和所有文件进行compaction，只要同步更新B+-tree就可以了。
写优化
MemTable保存在Persistent Memory中，省去了WAL的写入
读优化
实现了一个B+-tree，用以索引key，其每个叶子节点保存key及其对应的location info，该location info格式为[SST file id, data block offset, block size]。该B+-tree同样保存在Persistent Memory中
当将immutable memtable flush时，或者进行compaction时，需要同时对B+-tree进行更新。在SLM-DB中创建了两个线程，一个用于Compaction创建新文件，另外一个用于更新B+-tree。当新创建文件被flush到磁盘时，其内部的key便会发送到一个mq里，而更新B+-tree的线程作为该mq的消费者，获取这些key并对B+-tree进行更新。当更新完B+-tree之后，才会去更新MANIFEST文件，代表compaction完成。
通过B+-tree便可以直接定位到key对应的data block，完全消除了读放大。另外对于范围读，由于B+-tree的特性，只要找到第一个key，随后沿着叶子节点横向指针遍历就可以了。
Selective Compaction
在SLM-DB中也是需要compaction的，compaction的目的主要有两个：
删除过期数据 提升KV键值对的顺序性，使得范围查询的key落在尽量少的SSTable中，提升范围查询性能。
其触发时机有如下几个：
当SSTable文件的组织结构发生变化时（例如flush） 对一个确定的SSTable文件出现了多次seek 维护了一个compaction candidate list，当其中的文件数量超过某个阈值时
在进行compaction时，会在compaction candidate list中选取一定数量的文件进行compaction，选取规则如下：
对每个文件s，计算其与其他文件的重叠率。得出与所有其他compaction candidate list中文件的重叠率之和 选取重叠率最高的一些文件进行compaction
前面已经讲到过，在进行compaction时，需要开启两个线程，一个用于创建新文件，另一个用于更新B+-tree
file creation thread
与flush不同，compaction过程中可能会创新多个新文件（固定大小）。在merge操作过程中，需要通过查询B+-tree来判定该key是否还有效。当其还有效，将其与其他key合并入新文件；当其无效或者有效的key存在其他文件中，则将当前key删除，不合入新文件。
insertion thread
当file creation thread将新文件创建完成，便将这些key发送到一个队列中。insert thread便开始去更新B+-tree，同时file creation thread便去创建其他的新文件。当所有新创建文件的key都更新到了B+-tree之后，再去更新MANIFEST文件，并删除旧文件，此时代表compaction完成。
当前compaction candidate list中的文件选择也需要遵循一些策略，SLM-DB中实现了三种策略：
live-key ratio select
统计每个SST文件中的有效key的比例，当该比例低于某个阈值时，代表该SST文件中的垃圾过多，则将其加入到compaction candidate list中。
该ratio统计方法如下：在一个新文件创建时，记录其总的key数量，并记录当前有效key的数量为总的key数量。当执行某个key的写入操作时，该文件中的key便会无效。在更新B+-tree过程中，可以查找到当前存储该key的SST文件，将其live-key数量减1，随后再更新B+-tree
leaf node scan
该方法主要用于提高数据的顺序性。
在进行compaction时，将会选取一些keys，并会唤起一个leaf node scan。在该scan过程中，记录这些key所命中的文件数量（只要有包含至少一个key就算），如果该数量超过某个阈值，则将对应的这些文件放入compaction candidate list。因为命中文件数量越少，说明这些key的顺序性越好（命中文件数量为1代表所有的key都在同一个文件中）
这些keys的数量基于如下两个条件：
SST文件中的key的平均数量 要scan的SST文件数量
degree of sequentially per range
同leaf node scan，该方法主要也是用于提高数据的顺序性，具体方法如下：
当执行range query时，将该range拆分成多个sub-range query。对每个sub-range query，记录需要查询的文件的数量。当操作完成后，找到访问文件最多的sub-range query，如果其查询的文件数量大于某个阈值，则将这些对应的文件加入到compaction candidate list中。
KV Store Operations
Put
同LevelDB一样，将写入的插入到memtable中。
Get
先从memtable和immutable memtable中查询该key，如果查询不到则去遍历B+-tree，通过B+-tree可以找到该key所在的SST文件的data block
Range query
通过B+-tree可以找到该range中的第一个key，然后沿着叶子节点遍历。并将遍历得到的结果与memtable和immutable memtable中的结果进行合并，便是所有该range结果了。
Reference
https://levy5307.github.io/blog/SLM-DB/
SLM-DB全名Single-Level Key-Value Store with Persistent Memory。是使用了Persistent memory对LSM-tree based存储引擎进行了一系列优化。
LSM-tree的缺点
SLM-DB
上图为SLM-DB的整体架构图。其主要使用了Persistent Memory进行了如下优化。
在SLM-DB中，LSM-tree只有一层。对于LevelDB等传统的LSM-tree based数据库，设计成多层的原因在于减少写放大带来的影响。设想如果LSM-tree只有一层（为了高效索引，level 0一定是有序的），当flush一个immutable memtable时，可能level 0中的所有文件都与该immutable memtable有交集，为了维持有序行，此时的compaction将会导致所有的SST文件都牵涉进来，影响太大了。而设计成多层影响则小了很多。而SLM-DB则没有这个问题，其第一层是虽然是无序的，但是通过B+-tree进行了索引，所以在flush时只需要将其放入level 0就可以了，不必和所有文件进行compaction，只要同步更新B+-tree就可以了。
写优化
MemTable保存在Persistent Memory中，省去了WAL的写入
读优化
实现了一个B+-tree，用以索引key，其每个叶子节点保存key及其对应的location info，该location info格式为[SST file id, data block offset, block size]。该B+-tree同样保存在Persistent Memory中
当将immutable memtable flush时，或者进行compaction时，需要同时对B+-tree进行更新。在SLM-DB中创建了两个线程，一个用于Compaction创建新文件，另外一个用于更新B+-tree。当新创建文件被flush到磁盘时，其内部的key便会发送到一个mq里，而更新B+-tree的线程作为该mq的消费者，获取这些key并对B+-tree进行更新。当更新完B+-tree之后，才会去更新MANIFEST文件，代表compaction完成。
通过B+-tree便可以直接定位到key对应的data block，完全消除了读放大。另外对于范围读，由于B+-tree的特性，只要找到第一个key，随后沿着叶子节点横向指针遍历就可以了。
Selective Compaction
在SLM-DB中也是需要compaction的，compaction的目的主要有两个：
其触发时机有如下几个：
在进行compaction时，会在compaction candidate list中选取一定数量的文件进行compaction，选取规则如下：
前面已经讲到过，在进行compaction时，需要开启两个线程，一个用于创建新文件，另一个用于更新B+-tree
file creation thread
与flush不同，compaction过程中可能会创新多个新文件（固定大小）。在merge操作过程中，需要通过查询B+-tree来判定该key是否还有效。当其还有效，将其与其他key合并入新文件；当其无效或者有效的key存在其他文件中，则将当前key删除，不合入新文件。
insertion thread
当file creation thread将新文件创建完成，便将这些key发送到一个队列中。insert thread便开始去更新B+-tree，同时file creation thread便去创建其他的新文件。当所有新创建文件的key都更新到了B+-tree之后，再去更新MANIFEST文件，并删除旧文件，此时代表compaction完成。
当前compaction candidate list中的文件选择也需要遵循一些策略，SLM-DB中实现了三种策略：
live-key ratio select
统计每个SST文件中的有效key的比例，当该比例低于某个阈值时，代表该SST文件中的垃圾过多，则将其加入到compaction candidate list中。
该ratio统计方法如下：在一个新文件创建时，记录其总的key数量，并记录当前有效key的数量为总的key数量。当执行某个key的写入操作时，该文件中的key便会无效。在更新B+-tree过程中，可以查找到当前存储该key的SST文件，将其live-key数量减1，随后再更新B+-tree
leaf node scan
该方法主要用于提高数据的顺序性。
在进行compaction时，将会选取一些keys，并会唤起一个leaf node scan。在该scan过程中，记录这些key所命中的文件数量（只要有包含至少一个key就算），如果该数量超过某个阈值，则将对应的这些文件放入compaction candidate list。因为命中文件数量越少，说明这些key的顺序性越好（命中文件数量为1代表所有的key都在同一个文件中）
这些keys的数量基于如下两个条件：
degree of sequentially per range
同leaf node scan，该方法主要也是用于提高数据的顺序性，具体方法如下：
当执行range query时，将该range拆分成多个sub-range query。对每个sub-range query，记录需要查询的文件的数量。当操作完成后，找到访问文件最多的sub-range query，如果其查询的文件数量大于某个阈值，则将这些对应的文件加入到compaction candidate list中。
KV Store Operations
Put
同LevelDB一样，将写入的插入到memtable中。
Get
先从memtable和immutable memtable中查询该key，如果查询不到则去遍历B+-tree，通过B+-tree可以找到该key所在的SST文件的data block
Range query
通过B+-tree可以找到该range中的第一个key，然后沿着叶子节点遍历。并将遍历得到的结果与memtable和immutable memtable中的结果进行合并，便是所有该range结果了。
Reference
SLM-DB