// 对LSM的层的抽象，由SSTable组成
public class Level {
private final List<SSTable> ssts;
public void add(SSTable sst) {
ssts.add(sst);
// 在当前level总查找key对应的value, 从老到新遍历所有SSTable
public String find(String key) {
for (int i = ssts.size() - 1; i >= 0; i--) {
String value = ssts.get(i).get(key);
if (!value.equals("")) {
return value;
return "";
// sst与当前level进行compact操作
public void compactWith(SSTable sst) {...}
// 对给定sst集合与当前level进行compact操作
public void compactWith(List<SSTable> ssts) {...}
LsmKvDb的实现代码如下，写数据时写入MemTable，当达到阈值后转Immutable MemTable。Immutable MemTable与MemTable具有相同的数据结构，唯一不同的是前者只读不写，后者既读也写。
* 基于LSM树的key-value数据库, 采用分层架构
* MemTable -> Immutable MemTable -> Level0 -> Level1 -> Level2
public class LsmKvDb implements KvDb {
// 存储SSTable的目录
private final String sstDir;
// 当前写入的MemTable
private MemTable memTable;
// MemTable到达阈值大小后转储到immutableMts
private final List<MemTable> immutableMts;
// 后台定时将immutableMts中的MemTable刷到Level0，各SSTable之间可能由Key重叠
private final Level level0;
// 后台定时将Level0中的SSTable与Level1中的进行合并
private final Level level1;
// 当Level1中的SSTable的数量到达一定阈值后，选择最老的SSTable与Level2中的进行合并
private final Level level2;
@Override
public String get(String key) {
// step1: 从MemTable中读取
String value = memTable.get(key);
if (!value.equals("")) {
return value;
// step2: 从Immutable MemTable中读取，从新到老
for (int i = immutableMts.size() - 1; i >= 0; i--) {
value = immutableMts.get(i).get(key);
if (!value.equals("")) {
return value;
// step3: 从Level0中读取
value = level0.find(key);
if (!value.equals("")) {
return value;
// step4: 从Level1中读取
// step5: 从Level2中读取
return "";
@Override
public void set(String key, String value) {
memTable.add(key, value);
// 当MemTable大小到达阈值后转成Immutable MemTable
if (memTable.size() > MEMTABLE_MAX_SIZE) {
synchronized (this) {
immutableMts.add(memTable);
memTable = MemTable.create();
Compaction
在文章 《从Hash索引到LSM树（一）》已经对Compaction机制已经有了讲解， 其目的是清除掉已经被覆写或删除了的纪录，避免数据存储文件无休止的增长下去。对于LSM树而言，该机制同样适用，随着数据的不断添加、更新和删除，一些SSTable之间必然存在着重叠的key或被删除的key。通过Compaction，可以将多个SSTable合并成一个，从而节省了磁盘空间。
在上篇文章中，对segment file的compact操作主要依赖于Hash索引。因为是索引覆盖全部的key，所以可以很容易通过新的segment file的Hash索引来判断该key是否已经被处理过。但对于SSTable而言，并没有覆盖全部key的Hash索引，那么如何进行compact才高效呢？
得益于SSTable的有序性，我们可以应用归并排序算法来进行compact操作！
LSM树的Compaction通常有三种类型，分别是minor compact、major compact和full compact。
Minor Compact
minor compact指的是将Immutable MemTable中的数据直接转存到Level0中的SSTable。
minor compact
因为是直接将各个Immutable MemTable的数据转储成SSTable，并没有做合并的操作，因此在Level0中，各个SSTable之间的key可能存在重叠的现象。
Major Compact
major compact指的是将Level n中的SSTable合并到Level n+1中。
Level0 -> Level1的合并步骤如下：
1、选中Level0中的最老的SSTable sst0，然后在Level0中找到与sst0 的key存在重叠的所有SSTable sst0...n。
2、在Level1中，选取所有与 sst0...n存在key重叠的SSTable sst'0...m。
3、对sst0...n和sst'0...m采用多路归并排序算法进行合并，得到新的sst‘’0...k，并存储在Level1中。
4、删除sst0...n和sst'0...m。
major compact Level0 -> Level1
不同于Level0，Level1和Level2中各个SSTable之间并不存在key重叠的现象，因此Level1 -> Level2的合并会稍微简单些。
Level1 -> Level2的合并步骤如下：
1、选中Level1中的最老的SSTable sst0。
2、在Level2中，选取所有与 sst0存在key重叠的SSTable sst'0...m。
3、对sst0和sst'0...m采用多路归并排序算法进行合并，得到新的sst''0...k，并存储在Level2中。
4、删除sst0和sst'0...m。
major compact Level1 -> Level2
Full Compact
full compact指的是对Level0、Level1、Level2中所有的SSTable进行compact操作，同样也是采用多路归并排序算法。
full compact
通常full compact耗时较多，所以一般都会选择在流量较少的时刻进行。
优化LSM树
为SSTable引入block
到目前为止，对于在一个SSTable中查找一个key，我们首先会根据min key和max key判断该key是否属于该SSTable所属的范围，如果属于，则对SSTable采用二分查找法进行搜索。二分查找之所以在LsmKvDb中行得通，是因为这是一个简单的SSTable实现 —— 数据按string存储和\n分隔。在实际的运用中，为了尽可能地利用磁盘空间，SSTable中数据通常都是以字节码的形式存储，也不会以\n分隔每条record，这种情况下采用二分查找的实现就比较复杂了，而且效率也会太高。
一个常见的优化方法是，在SSTable中对record按照一定的size组织成多个block，并以block为单位进行压缩。为了能够快速找到某个key所属的block，需要在内存中维护每个block的起始key对应在SSTable中的offset（一个稀疏的Hash索引）。
按block存储的SSTable
在查找key的步骤如下：
1、根据索引定位到key所属的block。
2、将该block加载到内存中，并解压。
3、对内存中的数据采用二分查找。
在设计block的大小时，应该利用磁盘的空间局部性原理，使得系统能够只花费一次磁盘I/O就能将整个block加载到内存中。
为SSTable引入Bloom Filter
其实当目标key属于某个SSTable的key范围时，该key也不一定会存在于该SSTable中。但是到目前为止，只要目标key在某个SSTable的范围内，LsmKvDb都会进行查找操作。随着系统中的SSTable数目的增多，查询效率必然会随之下降。
一个常见的优化方法时，为SSTable引入布隆过滤器Bloom Filter。
Bloom Filter是保存在内存中的一种数据结构，可以用来告诉你 “某样东西一定不存在或者可能存在”。它由一个超长的二进制位数组和一系列的Hash函数组成。二进制位数组初始全部为0，当有元素加入集合时，这个元素会被一系列Hash函数计算映射出一系列的值，所有的值在位数组的偏移量处置为1。如果需要判断某个元素是否存在于集合当中，只需判断该元素被Hash后的值在数组中的值，如果存在为0的，则该元素一定不存在；如果全为1，则可能存在，这种情况可能有误判。
Bloom Filter
通过Bloom Filter，我们可以很快就能判断目标key是否不存在于SSTable中，从而提升了读性能。
Google的Guava库就提供了一个BloomFilter的实现，并且可以按需来设置误判率。
本文承接上《从Hash索引到LSM树（一）》， 主要介绍了LSM树的基本原理，并且在原来append-only log的基础上实现了一个简单的基于LSM树的key-value数据库LsmKvDb。LSM树主要由MemTable、Immutable MemTable、SSTable组成，其中MemTable和Immutable MemTable在内存中维护，而SSTable则存储在磁盘中。SSTable的有序性使得LSM树在无需Hash索引的情况下具有不错的读取性能，而且支持区间查询；而Memable则使得LSM树具备很高的写入性能。
本系列文章，我们从一个最简单的key-value数据库起步，一步步通过Hash索引、LSM树、布隆过滤器等技术手段对其进行了优化，从中也深入分析了各个技术点的实现原理。但数据库的索引技术远不止这些，比如最常用到的B/B+树，也是非常值得深入学习的，以后有机会再对其进行深入分析～
点击关注，第一时间了解华为云新鲜技术~
展开阅读全文
