LSMT简介

数据库的核心无外乎两个方面：存储和检索；高效存储，快速检索是每个数据库的愿景，但二者往往不可兼得，此时需要一些取舍...既然已经有关系型数据库，key-value数据库为何存在，如何实现一个key-value数据库；LSMT又是什么？

如何实现key-value数据库？

Log Segment是什么？

SSTable是什么？

LSMT又是什么？

一、自己写一个数据库

#!/bin/bash

#写入并存储数据

db_set () {

echo "$1,$2" >> database

}

#检索并读取数据

db_get () {

grep "^$1," database | sed -e "s/^$1,//" | tail -n 1

}

优点：

简单，且直接在文件后添加内容非常高效；使用key-value格式，key和value(几乎)可以是任何你喜欢的类型（eg:Json文件）

缺点：

数据不能覆盖更新，查询数据需要扫描全表；文件一直在增加，迟早会把磁盘撑爆。

二、优化

1、优化查询——Hash Index

针对上面自己实现的数据库查询效率不高的问题，首先想到的优化方案就是添加索引，避免全表扫描。最简单的索引策略是HashIndex:保存一个内存哈希映射，其中每个键都映射到数据文件中的一个字节偏移位置，通过该偏移位置定位值（Bitcask 中的默认存储引擎）

特点：

1、适合于key值较少且这些key有大量更新的情景，因为内存有限

2、插入或者更新数据时需要更新索引，所以写操作效率不高。即牺牲写性能来提升读的性能。

2、优化存储——Segment Merge

针对上面数据库中数据无限增加的问题，优化的方案是划分小文件（也叫Segment），避免一直写同一个文件，同时对小文件中key相同的数据进行合并且只保留最新值；具体操作如下：

1、划分segment:当数据文件增加到一定大小(例如10M)，将数据文件分割，划分出新的segment，写入新数据。

2、对旧的segment中的key进行合并只保留最新值；有两种合并方式：（1）每个segment中相同key合并；（2）segment间相同key合并。

3、每个segment维护自己的hash index索引。

实际使用时注意项：

File format：使用二进制格式存储数据使得数据库更快且数据存储更简单，尤其是当每条记录的长度一致时，速度非常快。

Deleting records：添加标志（tombstone），读数据时会忽略带该标记的数据。同时segment合并时会丢弃带有该标记的key的所有值。从而实现删除记录的效果。

Crash recovery：重启数据库时内存索引会丢失，故需要定期将内存中数据索引写到磁盘，以加快索引恢复速度。

Concurrency control：写入是严格按顺序的，所以只有一个写线程，数据不变所以可以并发读。

优点：

append-only和分段合并是顺序写操作，而在磁盘上（或SSD上）顺序写比随机写要快得多；如果段文件只是附加的且不可变的，那么系统的并发控制和崩溃恢复要简单得多。

缺点：

哈希表必须存入内存，所以如果你有非常多的键，你就GG;范围查询无效，只能更具key查询数据，无法范围查询。

经过以上两步优化之后的结构我们称之为log Segment

三、SSTable

01

SStable（Sorted String Table）

总的来说，所谓的SSTable就是在上面Log Segment基础上添加以下条件：

1、在log segment基础上对key排序（即数据在存储时是按key排序的）。

2、要求segment中一个key值只出现一次（上面基于存储的优化中对segment的合并操作已经可以保证该条件）

02

SSTables VS log segment

SSTables比使用hashtable的log segment有几个大的优点：

1、因为数据是按照key排序存储的，所以段（segment）合并操作变得简单且高效，即使文件比可用内存大，可以使用类似归并排序（Merge Sort）的方式。

2、不再需要在内存中保存所有键的索引。因为key是有序的，所以索引可以是稀疏的，索引可以分段存储，只存储开始和结束位置的key的索引即可。

3、key段中的数据是可以压缩之后再存磁盘。同时使稀疏内存索引都指向一个压缩块的开始。节省磁盘空间以及IO

03

SSTables构建和维护：

上面提到在Log Segment结构的基础上进一步优化，理论上可以得到SSTable，但是实际操作中如何基于LogSegment构建和维护SSTable呢？

首先有个问题需要解决：数据写入数据库的顺序是随机的，如何使得数据按key排序存入磁盘。虽然在磁盘上维护排序结构是可行的（参考b-tree）,但是在内存汇总维护它相对来说要容易的多。

操作如下：

1、需要写数据时，数据会先插入内存中保存着自平衡的树形结构(AVL/红黑树)，我们称其为memtable，这样就可以以任何顺序中插入key，并按照排序顺序读取它们

2、当memtable比某些阈值(通常是几兆)更大时，将其写入磁盘作为一个SSTable文件（此时SSTable就是已经是按key值排好序的数据文件）在将SSTable写入磁盘时，可以继续写入新的memtable实例。

3、查询key时，首先在memtable中查找，然后是最近的数据块（即磁盘上的SSTable文件中），之后老数据块中查找，依次类推直到查询完所有的数据文件。

4、隔一段时间，数据库会重新压缩并合并数据块（segment），同时删除被打上tombstone标记和过时的数据

04

这个SSTable方案很有效，唯一会遇到的问题就是：数据库崩溃（database crashes）:在memtable中还没有写到磁盘的数据会丢失。

工程中的解决方法（WAL日志）：

可以设置一个单独的日志，每个写都可以立即被追加到该日志中，它的唯一目的是在崩溃后恢复memtable，即数据先写入log，再进入memtable；因为增加了额外的写日志的操作，会影响效率，但是可以保证数据的安全。当然这是可以关闭的。

四、LSMT

01

上面SSTable的思想就是来源于就是LSMT(Log-Structured Merge-Tree）

02

LSM简介：

1、LSM的概念出自1996年的一篇论文，它提出了针对排序文件的合并和压缩的思想。之后基于该原则的存储引擎通常被称为LSM存储引擎

2、SSTable和Memtable的概念出自Google的Bigtable。

3、目前基于LSM实现的数据库有：LevelDB,RocksDB,LuceneHbase,Cassandra

03

工程上实现时仍需要在以上基础上进一步优化：

1、当查找数据库中不存在的键时，LSM-tree算法可能会很慢，因为你必须检查memtable，之后查找磁盘中的数据文件（SSTable）直至找到最老的部分(可能需要从磁盘中读取所有的数据文件)，然后才能确定该key不存在。所以工程中一般采用Bloom filter进行优化。

2、SSTables压缩以及合并的顺序和时间：

size-tiered：较新的和较小的SSTables依次被合并到更老的和更大的SSTables中。

leveled：关键的数据块会被拆分成更小的数据块，旧数据会被移动到一个单独的空间。这个操作是在后台处理的。（类似分布式存储中按数据范围分布方式）

04

优缺点：

尽管这个设计有许多微妙之处，但lsm-tree的基本思想（保持在后台中融合的SSTables）是简单而有效的：

1、当数据集比可用内存大得多的时候，它会继续运行良好。

2、由于数据是以排序的顺序存储的，所以可以高效地执行范围查询

并且由于disk write是顺序的，所以LSM-tree可以支持非常高的写吞吐量。

缺点：

1、压缩过程有时会影响正在进行的读和写的性能，即使压缩和合并操作是后台执行的，因为磁盘资源有限，当磁盘在进行一个昂贵的压缩操作时，正常的数据请求有可能需要等待；

2、compaction的另一个问题是高写吞吐量:磁盘的有限写入带宽需要在初始写入和在后台运行的压缩线程之间共享：当写入一个空数据库时，可以使用整个磁盘带宽来进行初始写入，但是数据库越大，压缩所需的磁盘带宽就越多。

3、基于sstable的存储引擎不会限制输入的速度，这就可能会导致压缩合并的速度跟不上segment生成的速度，而大大降低查询效率甚至耗尽磁盘空间，需要配置相关的监控。

一

只

程序猿

我是雨钓

一只被硅基虫子调戏的

碳基猿

文章来源《Designing Data-Intensive Applications》翻译