LSM树详解

LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象,事实上,LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构,它其实是一种存储结构,目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。

LSM树的核心特点是利用顺序写来提高写性能,但因为分层(此处分层是指的分为内存和文件两部分)的设计会稍微降低读性能,但是通过牺牲小部分读性能换来高性能写,使得LSM树成为非常流行的存储结构。

1、LSM树的核心思想

如上图所示,LSM树有以下三个重要组成部分:

1) MemTable

MemTable是在内存中的数据结构,用于保存最近更新的数据,会按照Key有序地组织这些数据,LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义,例如Hbase使跳跃表来保证内存中key的有序。

因为数据暂时保存在内存中,内存并不是可靠存储,如果断电会丢失数据,因此通常会通过WAL(Write-ahead logging,预写式日志)的方式来保证数据的可靠性。

2) Immutable MemTable

当 MemTable达到一定大小后,会转化成Immutable MemTable。Immutable MemTable是将转MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理,在转存过程中不阻塞数据更新操作。

3) SSTable(Sorted String Table)

有序键值对集合,是LSM树组在磁盘中的数据结构。为了加快SSTable的读取,可以通过建立key的索引以及布隆过滤器来加快key的查找。

这里需要关注一个重点,LSM树(Log-Structured-Merge-Tree)正如它的名字一样,LSM树会将所有的数据插入、修改、删除等操作记录(注意是操作记录)保存在内存之中,当此类操作达到一定的数据量后,再批量地顺序写入到磁盘当中。这与B+树不同,B+树数据的更新会直接在原数据所在处修改对应的值,但是LSM数的数据更新是日志式的,当一条数据更新是直接append一条更新记录完成的。这样设计的目的就是为了顺序写,不断地将Immutable MemTable flush到持久化存储即可,而不用去修改之前的SSTable中的key,保证了顺序写。

因此当MemTable达到一定大小flush到持久化存储变成SSTable后,在不同的SSTable中,可能存在相同Key的记录,当然最新的那条记录才是准确的。这样设计的虽然大大提高了写性能,但同时也会带来一些问题:

1)冗余存储,对于某个key,实际上除了最新的那条记录外,其他的记录都是冗余无用的,但是仍然占用了存储空间。因此需要进行Compact操作(合并多个SSTable)来清除冗余的记录。
2)读取时需要从最新的倒着查询,直到找到某个key的记录。最坏情况需要查询完所有的SSTable,这里可以通过前面提到的索引/布隆过滤器来优化查找速度。

2、LSM树的Compact策略

从上面可以看出,Compact操作是十分关键的操作,否则SSTable数量会不断膨胀。在Compact策略上,主要介绍两种基本策略:size-tiered和leveled。

不过在介绍这两种策略之前,先介绍三个比较重要的概念,事实上不同的策略就是围绕这三个概念之间做出权衡和取舍。

1)读放大:读取数据时实际读取的数据量大于真正的数据量。例如在LSM树中需要先在MemTable查看当前key是否存在,不存在继续从SSTable中寻找。
2)写放大:写入数据时实际写入的数据量大于真正的数据量。例如在LSM树中写入时可能触发Compact操作,导致实际写入的数据量远大于该key的数据量。
3)空间放大:数据实际占用的磁盘空间比数据的真正大小更多。上面提到的冗余存储,对于一个key来说,只有最新的那条记录是有效的,而之前的记录都是可以被清理回收的。

1) size-tiered 策略

size-tiered策略保证每层SSTable的大小相近,同时限制每一层SSTable的数量。如上图,每层限制SSTable为N,当每层SSTable达到N后,则触发Compact操作合并这些SSTable,并将合并后的结果写入到下一层成为一个更大的sstable。

由此可以看出,当层数达到一定数量时,最底层的单个SSTable的大小会变得非常大。并且size-tiered策略会导致空间放大比较严重。即使对于同一层的SSTable,每个key的记录是可能存在多份的,只有当该层的SSTable执行compact操作才会消除这些key的冗余记录。

2) leveled策略

每一层的总大小固定,从上到下逐渐变大

leveled策略也是采用分层的思想,每一层限制总文件的大小。

但是跟size-tiered策略不同的是,leveled会将每一层切分成多个大小相近的SSTable。这些SSTable是这一层是全局有序的,意味着一个key在每一层至多只有1条记录,不存在冗余记录。之所以可以保证全局有序,是因为合并策略和size-tiered不同,接下来会详细提到。

每一层的SSTable是全局有序的

假设存在以下这样的场景:

1) L1的总大小超过L1本身大小限制:

此时L1超过了最大阈值限制

2) 此时会从L1中选择至少一个文件,然后把它跟L2有交集的部分(非常关键)进行合并。生成的文件会放在L2:

如上图所示,此时L1第二SSTable的key的范围覆盖了L2中前三个SSTable,那么就需要将L1中第二个SSTable与L2中前三个SSTable执行Compact操作。

3) 如果L2合并后的结果仍旧超出L5的阈值大小,需要重复之前的操作 —— 选至少一个文件然后把它合并到下一层:

需要注意的是,多个不相干的合并是可以并发进行的

leveled策略相较于size-tiered策略来说,每层内key是不会重复的,即使是最坏的情况,除开最底层外,其余层都是重复key,按照相邻层大小比例为10来算,冗余占比也很小。因此空间放大问题得到缓解。但是写放大问题会更加突出。举一个最坏场景,如果LevelN层某个SSTable的key的范围跨度非常大,覆盖了LevelN+1层所有key的范围,那么进行Compact时将涉及LevelN+1层的全部数据。

3、总结

LSM树是非常值得了解的知识,理解了LSM树可以很自然地理解Hbase,LevelDb等存储组件的架构设计。ClickHouse中的MergeTree也是LSM树的思想,Log-Structured还可以联想到Kafka的存储方式。

虽然介绍了上面两种策略,但是各个存储都在自己的Compact策略上面做了很多特定的优化,例如Hbase分为Major和Minor两种Compact,这里不再做过多介绍,推荐阅读文末的RocksDb合并策略介绍。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/121568.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Redis-Cluster集群操作--添加节点、删除节点

一、环境部署 部署好Redis-Cluster集群,参考上个本人的博客:Redis-Cluster集群的部署(详细步骤)_是胡也是福的博客-CSDN博客 新准备一台机器,修改主机名,关闭防火墙和selinux,参考&#xff1a…

Jupyter Notebook 好用在哪?

Jupyter Notebook 是一个 Web 应用程序,便于创建和共享文学化程序文档,支持实时代码、数学方程、可视化和 Markdown,其用途包括数据清理和转换、数值模拟、统计建模、机器学习等等。目前,数据挖掘领域中最热门的比赛 Kaggle 里的资…

EI、Scopus双检索| 2023年第四届自动化、机械与设计工程国际会议

会议简介 Brief Introduction 2023年第四届自动化、机械与设计工程国际会议(SAMDE 2023) 会议时间:2023年12月8 -10日 召开地点:中国南京 大会官网:www.samde.org 机械设计制造及其自动化学科在国民经济中处于极其重要…

数学建模--最短路径算法的Python实现

目录 1.算法流程简介 2.算法核心代码 3.算法效果展示 1.算法流程简介 #最短路径算法 #针对有向图的最短路径问题,我们有很多的算法能解决. """ 目前主流算法如下所示: Dijkstra算法:Dijkstra算法是一种单源最短路径算法,用于计算从起点到其它所有节点的最短…

java八股文面试[多线程]——线程间通信方式

多个线程在并发执行的时候,他们在CPU中是随机切换执行的,这个时候我们想多个线程一起来完成一件任务,这个时候我们就需要线程之间的通信了,多个线程一起来完成一个任务,线程通信一般有4种方式: 通过 volat…

TypeScript_树结构-BST树

树结构 树的特点 树通常有一个根。连接着根的是树干树干到上面之后会进行分叉成树枝,树枝还会分又成更小的树枝在树枝的最后是叶子 树的抽象 树可以模拟生活中的很多场景,比如:公司组织架构、家谱、DOM Tree、电脑文件夹架构 优秀的哈希函…

STM32 SPI对存储芯片发送写是能命令后一直忙等待

我采用CUBE配置的SPI外设,对NSS引脚选择了硬件输出,这种方式对读取命令没有影响,但是对写命令有,当我发送写是能命令后,读取状态寄存器的值一直都是忙,我猜测这可能是硬件控制NSS引脚后,对于HAL…

如何用Jmeter编写脚本压测?

随着商业业务不断扩张,调用adsearch服务频率越来越高,所以这次想做个压测,了解目前多少并发量可以到达adsearch服务的界值。 这次选用的jmeter压测工具,压测思路如图: 一、日志入参 日志选取的adsearch 的 getads部分…

WEB APIs day6

一、正则表达式 RegExp是正则表达式的意思 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta http-equiv"X-UA-Compatible" content"IEedge"><meta name"viewport" co…

二叉树的介绍及二叉树的链式结构的实现(C语言版)

前言 二叉树是一种特殊的树&#xff0c;它最大的度为2&#xff0c;每个节点至多只有两个子树。它是一种基础的数据结构&#xff0c;后面很多重要的数据结构都是依靠它来进行实现的。了解并且掌握它是很重要的。 目录 1.二叉树的介绍 1.1概念 1.2现实中的二叉树 1.3特殊的二叉…

QCAD for Mac免费下载:卓越的2D辅助设计工具

QCAD是一款功能强大的2D辅助设计画图软件&#xff0c;现已适配Mac系统&#xff0c;为Mac用户提供了便捷高效的设计工具。 QCAD提供了丰富的绘图功能&#xff0c;可以轻松绘制各种平面图形&#xff0c;包括直线、圆、椭圆、弧线等。 同时&#xff0c;QCAD还支持多种绘图工具&am…

树莓 LUMA-OLED.EXAMPLE使用

详细介绍在文件目录下的README.rst中 第一步 $ sudo usermod -a -G i2c,spi,gpio pi //好像没什么用 $ sudo apt install python3-dev python3-pip python3-numpy libfreetype6-dev libjpeg-dev build-essential //安装依赖包&#xff0c;树莓派中好像已经有了 $ sudo a…

linux信号量

通过学习linux的信号量&#xff0c;对linux的信号量进行了编程。

iPhone 15 Pro展示设计:7项全新变化呈现

我们不应该再等iPhone 15 Pro在苹果9月12日的“Wonderlust”活动上发布了&#xff0c;而且可能会有很多升级。有传言称&#xff0c;iPhone 15 Pro将是自iPhone X以来最大的飞跃&#xff0c;这要归功于大量的新变化&#xff0c;从带有更薄边框的新钛框架到顶级A17仿生芯片和动作…

Burp插件HaE与Authz用法

HaE与Authz均为BurpSuite插件生态的一员&#xff0c;两者搭配可以避免“越权”、“未授权”两类漏洞的重复测试行为。&#xff08;适用于业务繁杂&#xff0c;系统模块功能多的场景&#xff09; 两个插件都可以在store里安装 安装完后&#xff0c;点击Filter Settings勾选Sho…

构建稳定的爬虫系统:如何选择合适的HTTP代理服务商

在构建一个稳定、高效的爬虫系统中&#xff0c;选择合适的HTTP代理服务商是至关重要的一步。本文将介绍如何选取可靠且性能优秀的HTTP代理服务供应商&#xff0c;来完成搭建一个强大而稳定的爬虫系统。 1.了解不同类型和特点 -免费公开代理服务器:提供免费但可能存在限制或不…

整数拆分【动态规划】

整数拆分 给定一个正整数 n &#xff0c;将其拆分为 k 个 正整数 的和&#xff08; k > 2 &#xff09;&#xff0c;并使这些整数的乘积最大化。 返回 你可以获得的最大乘积 。 class Solution {public int integerBreak(int n) {int[] dp new int[n 1];//正整数&#x…

mysql数据库使用技巧整理

查看当前数据库已建立的client连接 > SHOW VARIABLES LIKE max_connections; -- 查看数据库允许的最大连接数&#xff0c;不是实时正在使用的连接数 > SHOW STATUS LIKE Threads_connected; -- 查看当前数据库client的连接数 > SHOW PROCESSLIST; -- 查看具体的连接

【jsvue】联合gtp仿写一个简单的vue框架,以此深度学习JavaScript

用 gtp 学习 Vue 生命周期的原理 lifecycle.js function Vue(options) {// 将选项保存到实例的 $options 属性中this.$options options;// 若存在 beforeCreate 钩子函数&#xff0c;则调用之if (typeof options.beforeCreate function) {options.beforeCreate.call(this);…

类和对象(中)

&#x1f493;博主个人主页:不是笨小孩&#x1f440; ⏩专栏分类:数据结构与算法&#x1f440; C&#x1f440; 刷题专栏&#x1f440; C语言&#x1f440; &#x1f69a;代码仓库:笨小孩的代码库&#x1f440; ⏩社区&#xff1a;不是笨小孩&#x1f440; &#x1f339;欢迎大…