LSM树的基本原理－学习笔记

缺乏、安全感 2023-07-09 04:23 10阅读 0赞

一.什么是LSM树?

LSM全称为"Log-Structured Merged-Tree"．后来被Google发表的`BigTable`论文发扬广大．LSM相对于B+树而言，LSM树在损失部分读性能的前提下尽可能的提高写性能，将`随机写`转换为`顺序写`.

LSM树主要应用于`写多读少`的情况．

二.LSM树的基本思想

LSM树将所有的数据的插入，删除，修改等操作保存在内存之中，当操作达到一定的阀值，批量的写入磁盘之中．而在写入磁盘的时候，达到一定的阀值会进行合并，对于磁盘文件不进行修改.

三.LSM树如何组织起来?

LSM树的结构是横跨内存和磁盘的，其中包含了`memtable`,`sstable`,`log`,`bloom_fifter`组件，下述将会讨论这些组件应该如何实现?

#### 在内存中如何存储? ####

*  首先介绍一下`memtable`这一组件，它是在内存中的数据结构，用来保存最近的一些更新操作．当写数据到`memtable`中，必须先写入`磁盘中的Log`(这里我们可以采用写穿的方式,例如`O_SYNC`或者`fsync`直接去磁盘进行交互),防止数据因为掉电而丢失.
 *  `memtable`一般是需要有序的，这样在落入磁盘的时候是可以加快读取速率的，我们可以通过`跳表`或者`搜索树`等数据结构来组织数据保持有序性，当`memtable`达到一定量的时候，转化为`unmemtable`，同时我们创建新的`memtable`来处理内存的写入.
 *  `unmemtable`在内存中是不可修改的数据结构,它将memtable转换为sstable 的一种中间状态.为了在转存过程中不阻塞写操作，写操作可以由新的`memtable`进行处理,而转换过的`unmemtable`逐步的写入

#### 索引如何建立? ####

*  首先我们开始想到的是在内存中建立索引，但是很明显这种办法是行不通的．想要内存中建立索引，就必须保证索引可以在内存中存入，并且在更新的时候，需要大量的`随机访问磁盘I/O`
 *  我们可以采用磁盘索引的方式，如果数据文件本身就是有序存放的，我们可以不用给每一个key 建立索引．我们可以将key 划分若干个block,只需要建立`block`的索引和block中的部分key的`索引`.
 *  我们可以通过`布隆过滤器`加快查找键在块的位置，之后在`block`中进行搜索即可.

在LSM树，我们可以把按序组织的数据文件称为`sstable`,只保存`block`中的部分键的索引.

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70]  
假设你正在内存中寻找键 `handiwork` ， 但是你不知道段文件中该关键字的确切偏移量。然而， 你知道 `handbag 和 handsome 的偏移`， 而且由于排序特性， 你知道 `handiwork必须出现在这两者之间`。 这意味着您可以跳到 handbag 的偏移位置并从那里扫描， 直到您找到 handiwork （ 或没找到， 如果该文件中没有该键） 。  
我们可以针对整个文件或者块进行相应的压缩，减少磁盘的利用率．

#### 日志应该如何组织? ####

*  LSM树中的`log`的中的数据一般为乱序，它是为了`保证断电的时候的数据恢复`
 *  将对于键的操作写入log之中，若部分键落在磁盘之后，可以在`日志`中清除相应的数据，`防止日志过度膨胀,`

#### 布隆过滤器的作用? ####

*  首先我们可以思考一个问题，如何快速的判断一个key是不是存在某个集合?可能大部分同学都会回答`HashMap`吧，的确,HashMap是一个好的方案，它可以通过O(1)的时间复杂度返回结果，效率相当不错．但是如果`数据量相当庞大`的情况下?
 *  因为负载因子的存在，这时候的HashMap的空间是不能被用满的，也就是说内存的占用是十分庞大的．
 *  我们可以利用布隆过滤器来达到这一需求，布隆过滤器实际上是一个位数组或者可以称之为位变量，布隆过滤器通过对键的hash得到相应的值，将那个值所对应的位置置为１．
 *  我们通过判断位置是不是为１，来确定这个key是不是在这个集合之中.

四.LSM树的增删改查

写入操作

*  写操作首先需要将数据写入Log 中，防止数据丢失，然后数据被写入到内存的memtable 中的，这样一次写操作已经完成了，只需要１次磁盘IO,再加上１次内存操作. 相比较B+树的多次磁盘随机IO,大大提高了效率.

删除操作

*  当有删除操作的时候，并不需要B+树一样，在磁盘中找到相应的数据后再删除，只需要在memtable中插入一条数据当作标志．当读操作读取之后，会知道这个key已经被删除了．在日志合并的过程中，内存中被删除的数据会在磁盘中删除.

更新操作

*  操作memtable,写入一个标志，随后真正的更新操作会被延迟在合并一并完成．

查询操作

*  查询操作就比较慢了，LSM树主要是通过牺牲读性能而提高写性能，需要从内存表，磁盘中读取．
 *  我们可以通过二分法+布隆过滤器提高速率．

合并操作

*  合并内存中的数据到磁盘中
 *  将内存数据合并到磁盘中会产生大量小的集合，并且更新和删除操作会产生大量的冗余数据，通过合并可以介绍之前的冗余数据．

目前比较广泛的两种策略, size\_tiered策略和leveled策略

size\_tiered策略  
当某个规模的集合达到一定的数量，合并为一个大的集合，缺点会变得很耗时.

leveled策略  
分层进行合并，在本层选出一个文件和下一层合并或者直接提升，不会重复，更新的时候发现数据冲突，直接丢弃掉．

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200227210514448.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RyZWFtMDEzMF9f,size_16,color_FFFFFF,t_70