【LSM tree 】Log-structured merge-tree 一种分层、有序、面向磁盘的数据结构

文章目录

  • 前言
  • 基本原理
  • 读写流程
    • 写流程
    • 读流程
  • 写放大、读放大和空间放大
  • 优化


前言

LSM Tree 全称是Log-structured merge-tree, 是一种分层,有序,面向磁盘的数据结构。其核心原理是磁盘批量顺序写比随机写性能高很多,可以通过围绕这一原理进行设计和优化,让写性能达到最优。相较于传统的B+树,它减少了磁盘随机读取的需求,从而在一定程度上改善了数据库的写能力,当然在一定程度上牺牲了数据库的读能力。LSM tree也是当今流行的各种NoSQL或NewSQL数据库最基础的底层数据结构,广泛使用在包括Hbase,Cassandra,Leveldb, RocksDB, TiDB等项目中。

基本原理

传统的B+树的缺陷就是在访问节点时涉及到了大量的磁盘随机读写,因为你无法保证节点常驻内存,尤其是当B+树管理的索引量很大的时候,这导致数据库读写性能急剧下降。
LSM tree 采取的做法就是通过引入多部件索引来减少磁盘随机读写的需求。在大量插入情况下我们周期性地选取两部分索引进行合并,并且把合并后的有序文件(或内存块)添加到磁盘尾部(或成为新文件),修改节点信息以保证索引树的正确和完善,并且周期性地回收失效索引。因此与其说LSM tree是一种树,不如说它是通过传统索引组织有序文件或内存块的一种方式。
在这里插入图片描述
LSM tree的节点可以分为两种:

  • MemTable: 保存在内存中的部分,一般可以是红黑树、跳跃表,甚至可以是B树。在HBase中使用的是跳表,在SQLite4中使用的是只能追加写入的红黑树。
  • SSTable: 保存在磁盘上的部分,一般由多个内部KeyValue有序的文件组成,它的key和value都是任意的字节数组,并且了提供了按指定key查找和指定范围dekey区间迭代遍历的功能。SSTable内部包含了系列可匹配大小的Block块。关于这些Block块的index存储在SSTable的尾部,用于帮助快速查找。

写操作直接作用于MemTable,因此写入性能接近写内存。每层SSTable文件到达一定条件后,进行合并操作,然后放置到更高层。合并操作在实现上一般的策略驱动、可插件化的。

读写流程

在这里插入图片描述

写流程

  1. 当收到一个写请求时,会先把该条数据记录在 WAL(Write-ahead logging)里面,用作故障恢复。
  2. 当写完 WAL 后,会把该条数据写入内存的 MemTable 里面(删除操作也通过写入实现,会写入一个删除标记;更新则是写入一条新记录)。
  3. 当 Memtable 超过一定的大小后,会在内存里面冻结,变成不可变的 Memtable,同时为了不阻塞写操作需要新生成一个 Memtable 继续提供服务。
  4. 把内存里面不可变的 Memtable 给 flush 到到硬盘上的 SSTable 层中,此步骤也称为 Minor Compaction,这里需要注意在 L0 层的 SSTable 是没有进行合并的,所以这里的 key range 在多个 SSTable 中可能会出现重叠,在层数大于 0 层之后的 SSTable,不存在重叠 key。
  5. 当每层的磁盘上的 SSTable 的体积超过一定的大小或者个数,也会周期的进行合并。此步骤也称为 Major Compaction。这个阶段会真正的清除掉被标记删除掉的数据以及多版本数据的合并,避免浪费空间,注意由于 SSTable 都是有序的,我们可以直接采用 merge sort 进行高效合并。

读流程

  1. 当收到一个读请求的时候,会直接先在内存里面查询,如果查询到就返回。
  2. 内存查询包括服务中的 Memtable 和不可变的 Memtable,也包括对于 SSTable 的缓存 block cache。
  3. 如果内存中没有查询到就会依次下沉查询 SSTable,直到把所有的层次的 SSTable 查询一遍得到最终结果。

写放大、读放大和空间放大

LSM Tree 将随机写转化为顺序写,而作为代价带来了大量的重复写入。由此会引起写放大、读放大和空间放大。

  • 写放大(Write Amplification):
    平均写入 1 个字节,引擎中在数据的声明周期内实际会写入 n 个字节,其写放大率是 n。如果业务方写入速度是 10MB/s,在引擎端或者操作系统层面能观察到的数据写入速度是 30MB/s,系统的写放大率就是 3。写放大过大会制约系统的实际吞吐。对于 SSD 来说,也会导致 SSD 寿命缩短。

以下是 HBase 中的写放大示意图
在这里插入图片描述

  • 读放大(Read Amplification):

一个读请求,系统所需要读 n 个页面来完成查询,其读放大率是 n。逻辑上的读操作可能会命中引擎内部的 cache 或者文件系统 cache,命中不了 cache 就会进行实际的磁盘 IO,命中 cache 的读取操作的代价虽然很低,但是也会消耗 CPU。
以下是 HBase 中的读放大示意图
在这里插入图片描述

  • 空间放大(Space Amplification):
    平均存储 1 个字节的数据,在存储引擎内部所占用的磁盘空间 n 个字节,其空间放大是 n。比如写入 10MB 的数据,磁盘上实际占用了 100MB,这是空间放大率就是 10。空间放大和写放大在调优的时候往往是排斥的,空间放大越大,那么数据可能不需要频繁的 compaction,其写放大就会降低;如果空间放大率设置的小,那么数据就需要频繁的 compaction 来释放存储空间,导致写放大增大

优化

LSM tree 一般从以下几个方面进行优化:

  1. 压缩

SSTable 是可以启用压缩功能的,并且这种压缩不是将整个 SSTable 一起压缩,而是根据 locality 将数据分组,每个组分别压缩,这样的好处当读取数据的时候,我们不需要解压缩整个文件而是解压缩部分 Group 就可以读取。

  1. 缓存

因为 SSTable 在写入磁盘后,除了 Compaction 之外,是不会变化的,所以我可以将 Scan 的 Block 进行缓存,从而提高检索的效率。

  1. Bloom filter

正常情况下,一个读操作是需要读取所有的 SSTable 将结果合并后返回的,但是对于某些 key 而言,有些 SSTable 是根本不包含对应数据的,因此,我们可以对每一个 SSTable 添加 Bloom Filter,因为 Bloom Filter 在判断一个 SSTable 不存在某个 key 的时候,那么就一定不会存在,利用这个特性可以减少不必要的磁盘扫描。

  1. 合并

通过定期合并瘦身, 可以有效的清除无效数据,缩短读取路径,提高磁盘利用空间。但 Compaction 操作是非常消耗 CPU 和磁盘 IO 的,尤其是在业务高峰期,如果发生了 Major Compaction,则会降低整个系统的吞吐量,这也是在使用一些 NoSQL 数据库时,比如 Hbase,常常会禁用 Major Compaction,并在凌晨业务低峰期进行合并的原因。

ref:https://popesaga.github.io/2020/09/25/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E5%92%8C%E7%AE%97%E6%B3%95%EF%BC%9ALSM%20tree/#%E5%86%99%E6%94%BE%E5%A4%A7%E3%80%81%E8%AF%BB%E6%94%BE%E5%A4%A7%E5%92%8C%E7%A9%BA%E9%97%B4%E6%94%BE%E5%A4%A7

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

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

相关文章

【Vue】日常错误总结(持续更新)

日常遇到的小问题汇总, 内容小篇幅少的就全放这里了, 内容多的会在Vue专栏单独分享~ 目录 【Q】 el-form-item值为 null 或 undefined显示““ 【Q】dialog内组件数据刷新总是延迟慢一拍 问题背景描述 解决方案 代码简单模拟 JS 【Q】el-input 不能输入的解决办法 方法…

IDEA 2023.3 start failed 启动失败修复

发现是 RestfulToolkit 插件有冲突导致的,删除插件后成功启动 open ~/Library/Application\ Support/JetBrains/IntelliJIdea2023.3/plugins参考:https://youtrack.jetbrains.com/issue/IDEA-340080/Critical-startup-error-after-upgrading-to-Intelli…

系统的安全性设计

要设计一个安全的系统,除了要了解一些前面讲到的常用的保护手段和技术措施外,还要对系统中可能出现的安全问题或存在的安全隐患有充分的认识,这样才能对系统的安全作有针对性的设计和强化,即“知己知彼,百战百胜”。 下…

12月11日作业

完善对话框,点击登录对话框,如果账号和密码匹配,则弹出信息对话框,给出提示”登录成功“,提供一个Ok按钮,用户点击Ok后,关闭登录界面,跳转到其他界面 如果账号和密码不匹配&#xf…

基于ssm服装定制系统源码和论文

idea 数据库mysql5.7 数据库链接工具:navcat,小海豚等 环境: jdk8 tomcat8.5 开发技术 ssm 基于ssm服装定制系统源码和论文751 1.1项目研究的背景 困扰管理层的许多问题当中,服装定制将是广大用户们不可忽视的一块。但是管理好服装定制又面临很多麻…

【SpringBoot】从入门到精通的快速开发指南

🎉🎉欢迎来到我的CSDN主页!🎉🎉 🏅我是Java方文山,一个在CSDN分享笔记的博主。📚📚 🌟推荐给大家我的专栏《SpringBoot》。🎯🎯 &…

PDI/Kettle-9.2.0.0-R(对应jdk1.8)源码编译问题记录及源码结构简介

目录 📚第一章 前言📗背景📗目的📗总体方向 📚第二章 代码结构初识基本结构📗代码模块详情 ⁉️问题记录❓问题一:代码分支哪些是发布版本❗答:后缀-R的版本 ❓问题二:50…

怎么选择合适的3ds Max云渲染农场?

3ds Max 用户日常面临的一个共同挑战便是漫长的渲染周期。作为一个强大的三维建模和渲染软件,3ds Max 势必需处理大量的光照、材质和阴影计算任务,因此,良好的渲染方案对从业者而言尤为重口。 一、为何考虑3ds Max云渲染? 云渲染成为了解决…

自动机器学习是什么?概念及应用

自动机器学习 (Auto Machine Learning) 的应用和方法 随着众多企业在大量场景中开始采用机器学习,前后期处理和优化的数据量及规模指数级增长。企业很难雇用充足的人手来完成与高级机器学习模型相关的所有工作,因此机器学习自动化工具是未来人工智能 (A…

【状态机FSM 序列检测 饮料机_2023.12.1】

同步状态机 概念 同步状态机(同一脉冲边沿触发):有限个离散状态及某状之间的转移 异步状态机无法综合 分类 Moore状态机 只和状态有关,与输入无关 Mealy状态机 和状态和输入都有关 Mealy型比Moore型少一个状态 结构 由状态寄…

中文字符串逆序输出

今天碰到这个题,让我逆序输出中文字符串,可给我烦死了,之前没有遇到过,也是查了资料才知道,让我太汗颜了。 英文字符串逆序输出很容易,开辟一块空间用来存放逆序后的字符串,从后往前遍历原字符串…

十四 动手学深度学习v2计算机视觉 ——转置矩阵

文章目录 基本操作填充、步幅和多通道再谈转置卷积不填充,步幅为1填充为p,步幅为1填充为p,步幅为s 基本操作 填充、步幅和多通道 填充: 与常规卷积不同,在转置卷积中,填充被应用于的输出(常规卷…

小小手表探索更多 好玩伴也是好帮手

华为儿童手表 5X 不仅是孩子的好玩伴,也是家长的好帮手。全能形态让小小手表探索更多,高清双摄记录美好,离线定位随时掌握,绿色纯净守护成长,让孩子享受科技带来的安全与乐趣。

为什么随着网络的增加,传统的多层网络结构的非线性表达很难去表示恒等映射,模型会出现网络退化问题,什么是恒等映射!!

文章目录 一、什么是恒等映射二、对于深度神经网络,保持恒等映射并不是必需的,三、恒等映射可以作为一个简单的基准任务来评估和分析网络的一些重要性质 一、什么是恒等映射 恒等映射指的是输入和输出完全相同的映射关系,也就是yx。它是一个线性函数,没…

cordic 算法学习记录

参考:b站教学视频FPGA:Cordic算法介绍与实现_哔哩哔哩_bilibili FPGA硬件实现加减法、移位等操作比较简单,但是实现乘除以及函数计算复杂度高且占用资源多,常见的计算三角函数/平方根的求解方式有①查找表:先把函数对应…

车载导航系统UI界面,可视化大屏设计(PS源文件)

大屏组件可以让UI设计师的工作更加便捷,使其更高效快速的完成设计任务。现分享车载导航系统科技风蓝黑简约UI界面、车载系统UI主界面、车载系统科技风UI界面、首页车载系统科技感界面界面的大屏Photoshop源文件,开箱即用! 若需 更多行业 相关…

攻防世界——BABYRE

下载好文件,IDA64打开 无脑F12 锁定到right 跟进到了这个函数 很明显关键点就是 我们跟进judge 182个字符 懵逼了,说实话 下面是问了人后 —————————— 其实这是一个函数,一个操作指令 但是我们可以发现 在这里,ju…

EasyExcel处理表头的缓存设置

在学习EasyExcel 时会发现针对使用类模型配置表头相关属性时,EasyExcel 会使用到缓存技术以提升表头的解析速度如下代码: 这些参数再何时设置的哪? 在easyExcel 基础参数设置中会有这个参数filedCacheLocation 。默认采用的使用线程级别的…

《opencv实用探索·十九》光流法检测运动目标

前言 光流法(Optical Flow)是计算机视觉中的一种技术,用于估计图像中相邻帧之间的像素位移或运动。它是一种用于追踪图像中物体运动的技术,可以在视频中检测并测量物体的运动轨迹。 光流的直观理解: 光流是一个视频中两…

web微服务规划

一、背景 通过微服务来搭建web系统,就要对微服务进行规划,包括服务的划分,每个服务和数据库的命名规则,服务用到的端口等。 二、微服务划分 1、根据业务进行拆分 如: 一个购物系统可以将微服务拆分为基础中心、会员…