LevelDB之LSM数据模型

简介

LevelDB是谷歌开源的单机版持久化kv存储数据库,主要使用LSM(日志结构合并树)的存储模型,LSM主要是通过大量的随机写转化为顺序写,从而极大的提升了数据写入的的性能,虽然于此同时牺牲了部分读的性能。适合写多读少的场景。

LSM数据存储模型

WAL

WAL预写式日志(Write-ahead logging)是数据库设计中常用的设计,当插入一条数据时,数据先写入WAL文件中,之后再插入到内存中的MemTable当程序挂掉之后,就可以从WAL中恢复内存中的MemTable

Memtable

MemTable对应的就是WAL文件,是该文件内容在内存中的存储结构,通常采用SkipList来实现。MemTable提供了K-v数据的写入、删除以及读取的操作接口。其内部将k-v对按照key值有序存储,这样方便在快速序列化到SSTable文件中,仍然保持数据的有效性。

Immutable MemTable

Immutable MemTable是内存中只读的MemTable,由于内存是有限的,通常我们会设置一个阀值,当memTable占用的内存达到阀值后就自动切换为IM,IM和MEmTable就区别就是它是只读的,系统此时会生成新的MemTable供写操作继续写入,这样是为了避免直接将Memtable中的内存序列化到磁盘会阻塞写操作。

SSTable

SSTable就是MemTable中的数据在磁盘上的有序存储,其内部数据是根据key从小到大排序的,通常为了加快查找的速度,需要在SSTable中家属数据索引,可以快速读到指定kv的数据。
SSTable通常采用分级的结构,MemTable中的数据达到阀值后在Level0层创建一个新的SSTable。当某个Level下的文件数超过一定值后,就会将这个Level下的一个SSTable和更高一级的SSTable合并,由于SSTable中的KV都是有序的相当于是一个多路归并排序,所以合并操作相当快速,最终生成一个新的SSTable,将旧的文件删除,这样就完成了一次合并操作。
SSTable的大小控制
0 ↠ 4 SST, 1 ↠ 10M, 2 ↠ 100M, 3 ↠ 1G, 4 ↠ 10G, 5 ↠ 100G, 6 ↠ 1T, 7 ↠ 10T

增删改查KV

写入

lsm-tree-write.png
写入操作只需要顺序写入WAL文件中,成功后将kv数据写入memTable中即可,然后再写入SST文件,

通常采用分级合并的方法  

读取

lsm-read.png
LSM的读取效率不是很高,当需要读取指定key的数据时,先在内存中的MemTable和Immutable MemTable中查找,如果没有找到,则继续从Level0层开始寻找,然后再从更高层的SSTable文件中查找,直接找到目标key,否则返回不存在这个key,并且如果找到这个key 那么这个key的数据一定的最新的。
每一层的SSTable文件的key范围是不重复的,所以只需要查找其中一个SSTable文件即可指定key的数据,这一层中。但是Level0不适合这样做,因为Level0层SSTable文件的key值可能存在重复,需要查找多个文件

读取优化

因为读取的效率比较差,所以在LevelDB中,会存在一些缓存文件,记录着SSTable文件的一些关键信息,可以帮助快速定位到要查询的SSTable文件,避免频繁读取

总结

LSM将随机写转换为顺序写来大幅提高写入操作的性能,但是也牺牲了读性能。

这种算法对于时间列数据库比较适合。持续写入数据量大,数据和事件相关,编码到key值中很容易使key值有序,读取操作相对来说较少,通常会读取一段时间范围内的数据,这样就把LSM读取性能差的劣势缩小了,反而数据在SSTable中是按照key值顺序排列,读取大块链接的数据时效率也很高。

参考