数据结构 | Log-Structured Merge Tree (LSM Tree)
今天介绍LSM Tree这个数据结构,严格意义上来说,他并不像他的名字一样是一棵树型的数据结构,而更多是一种设计思想。
LSM Tree最先在1996年被提出,后来被广泛运用于现代NoSQL(非关系型数据库)系统中,包括BigTable, Dynamo, HBase, Cassandra, LevelDB, RocksDB, and AsterixDB.
LSM Tree主要是瞄准了IO操作中,顺序写的速度比随机写快几个数量级的特点,采用out-of-place 更新的特性,将随机写入累积到顺序写入,以利用存储设备的高顺序写入带宽。
那他是怎么做到的呢?实际上设计上其实也相当的简单粗暴。
LSM Tree通过将写入操作集中在内存中,并定期将数据合并到持久性存储介质(如磁盘)上,实现了高吞吐量的写入和高效的查询性能。LSM Tree引入了“组件”的概念,组件是指存储数据的单元或数据结构,它们按照特定规则组织和管理数据。
组件根据其存在于内存中或是磁盘中,被划分为:
1. 内存组件(Memory Component):LSM树通过内存组件(也称为memtable)存储最近写入的数据。内存组件通常是一个有序的数据结构(如平衡树或跳表),它提供快速的写入和查询操作。写入操作首先在内存组件中进行,以实现低延迟的写入性能。
2. 磁盘组件(Disk Component):当内存组件达到容量限制或触发某些条件时,LSM树将内存组件中的数据刷新到磁盘组件中。磁盘组件通常是一系列按键有序存储的文件(SSTable),其中每个文件称为一个层级(level)。较新的数据存储在较高的层级,而较旧的数据存储在较低的层级。每个层级的文件都是顺序写入的。磁盘组件之间的数据合并操作以保持数据的有序性和紧凑性。
因此,不难看出,无论是在内存组件还是磁盘组件,LSM Tree都是使用有序的数据结构实现的,这也是为什么说LSM Tree是一种设计思想,而不是一个具体的数据结构的原因,在内存组件中,C0 tree可以采用B+树、红黑树等数据结构实现,他们可以被随机访问,直接修改,内存组件由于存在于内存中,访问快但容量小。在内存组件满或某些条件触发时,从内存组件中刷到磁盘组件中,因此,就起到了将随机写整合为顺序写的效果。
LSM Tree的查询过程
1. 首先进行内存查询:首先,查询操作会在内存组件(如memtable)中进行。由于内存组件是一个有序的数据结构,可以使用二分查找或其他高效的查找算法来定位所需的键。如果找到了匹配的键,则返回对应的值。如果在内存组件中未找到匹配的键,查询将继续进入下一个阶段。
2. 内存缺失时磁盘查询:如果在内存组件中未找到匹配的键,查询将继续在磁盘组件中进行查找。LSM树的磁盘组件通常由多个层级的文件组成,其中较新的数据存储在较高的层级,较旧的数据存储在较低的层级。
LSM Tree的增删改过程
LSM Tree的增删改过程都在内存中进行,按照内存中的有序结构的方式进行增加操作,删除过程同样都可以视作“增”,对于删除操作,在内存中将关键字打上标记,这样,在合并过程中,该key就会被忽略,从而实现删除的效果。
LSM Tree的合并过程
将高一层级的LSM Tree合并到第一层级会触发合并(也可以叫压缩),LSM树会从每个层级中选择一组候选文件进行合并。通常,合并操作从较高层级开始,逐渐向下进行。选择候选文件的策略可以根据不同的实现和需求而有所不同,常见的策略包括选择最旧的文件、选择文件大小最接近某个阈值的文件等。选定的候选文件会按照键的顺序进行排序。这可以通过一次性读取文件中的数据,并使用外部排序算法(如归并排序)来实现。排序后的数据将成为合并操作的输入。合并操作会将排序后的数据合并到一个新的文件中。新文件通常位于较低层级。合并操作的目标是保持数据的有序性和紧凑性。它会逐个比较排序后的键值对,并根据键的顺序将它们写入新文件。如果有重复的键,则通常选择最新的键值对作为合并结果。合并后的新文件可能会包含一些重复的键值对或已标记为删除的数据。为了优化存储空间,可以进行压缩操作。压缩操作会移除重复的键值对、删除标记和其他冗余数据,以减少文件的大小。压缩操作通常在合并操作之后进行,以避免对正在合并的数据产生冗余的压缩开销。
多Level LSM Tree
LSM Tree可以具有多个磁盘组件(似乎在后面的实现中往往只有一种),称为多组分LSM树(Multi-component LSM-trees)是LSM树的一种变体,它引入了多个组件类型以优化存储和查询性能。
在传统的LSM树中,通常只有两种组件类型:内存组件和磁盘组件。然而,多组分LSM树引入了额外的组件类型,以更好地适应不同的工作负载和性能需求。
多组分LSM树的主要组件类型包括:
内存组件(memtable):内存组件是多组分LSM树中的一个重要组成部分,它与传统LSM树中的内存组件相同。它存储最近的写入操作,并提供快速的插入和查询性能。与传统LSM树不同的是,多组分LSM树中的内存组件可以具有不同的配置和特性,以适应不同类型的数据和查询负载。
热存储组件(hot storage component):热存储组件是多组分LSM树中的一种组件类型,用于存储频繁访问的热数据。热存储组件可以位于内存或者高性能的存储介质上,以提供更快的查询响应时间。它通常用于存储最常访问的数据,以减少查询延迟。
冷存储组件(cold storage component):冷存储组件用于存储不经常访问的冷数据。这些组件通常位于较低性能的存储介质上,如磁盘或者低成本的云存储。冷存储组件可以容纳大量的数据,并提供较低的存储成本,但查询性能可能相对较低。
归档存储组件(archive storage component):归档存储组件用于长期存储和归档数据,这些数据很少被访问。归档存储组件通常采用高度压缩的格式,以减小存储空间的占用。这些组件通常位于持久性存储介质上,如冷存储或者备份存储。
多组分LSM树通过引入不同类型的组件,根据数据的访问模式和性能需求,将热数据存储在高性能组件中,而将冷数据存储在较低性能组件中。这样可以提高查询性能和存储效率,同时满足不同类型的数据访问需求。
LSM Tree的异地更新特性
传统的索引结构通常采用in-place更新策略,即直接覆盖旧记录来存储新的更新。而LSM树采用了out-of-place更新策略,即始终将更新存储在新的位置,而不是直接覆盖旧条目。
LSM树的out-of-place特性带来了一些优势。首先,它提高了写入性能,因为可以利用顺序I/O来处理写入操作。相比之下,传统的in-place更新结构需要进行随机的I/O操作,影响写入性能。其次,out-of-place特性简化了恢复过程,因为它不会覆盖旧数据,可以更容易地进行数据恢复。此外,LSM树的out-of-place特性还允许对数据进行可调整的并发控制和高空间利用率的管理。
然而,out-of-place特性也带来了一些挑战。由于记录可能存储在多个位置,读取性能可能会受到影响。此外,LSM树通常需要进行单独的数据重新组织过程,以持续改善存储和查询的效率。
LSM树的out-of-place特性是其设计的关键部分,它使LSM树成为现代NoSQL系统中存储层的重要组成部分,并为各种工作负载提供了高性能和高效的存储管理。
如何继续优化LSM Tree
LSM Tree具有良好的写性能,但是无疑也降低了读性能,如何提升LSM Tree的读性能?
可以考虑采用布隆过滤器,提前过滤一些明确不存在的key,来加快读性能;
可以考虑采用在有序结构上使用的更加高效的查找算法,比如二分查找来提高查找速度;
可以考虑使用hash,将数据分割映射等。
在以下链接中,有之前的创作者设计的LSM Tree的增删查改样例,有兴趣的读者可以了解。
https://blog.csdn.net/jinking01/article/details/105377370
如果想要更多了解LSM Tree的学术上的进展,推荐一篇文献调研:
https://doi.org/10.1007/s00778-019-00555-y
相关文章:

数据结构 | Log-Structured Merge Tree (LSM Tree)
今天介绍LSM Tree这个数据结构,严格意义上来说,他并不像他的名字一样是一棵树型的数据结构,而更多是一种设计思想。 LSM Tree最先在1996年被提出,后来被广泛运用于现代NoSQL(非关系型数据库)系统中…...
QEMU源码全解析 —— virtio(9)
接前一篇文章: 上两回讲解了virtio balloon相关类所涉及的realize函数以及大致流程,如下表所示: realize函数parent_dc_realize函数DeviceClassvirtio_pci_dc_realizePCIDeviceClassvirtio_pci_realizeVirtioPCIClassvirtio_balloon_pci_rea…...

金蝶云星空协同开发环境应用内执行单据类型脚本
文章目录 金蝶云星空协同开发环境应用内执行单据类型脚本业务界面查询单据类型表数据导出数据执行数据库脚本单据类型xml检验是否执行成功检查数据库检查业务数据 金蝶云星空协同开发环境应用内执行单据类型脚本 业务界面 查询单据类型表数据 先使用类型中文在单据类型多语言…...
矩阵理论及其应用邱启荣习题3.5题解
(1) P ( − 1 0 1 − 1 − 1 2 1 1 − 1 ) \begin{pmatrix} -1 & 0&1 \\ -1 & -1&2\\1&1&-1 \end{pmatrix} −1−110−1112−1 A ( 1 0 1 1 1 0 − 1 2 1 ) \begin{pmatrix} 1 & 0&1 \\ 1 & 1&0\\-1&2&1 \end{pmat…...
Java面试题(每天10题)-------连载(49)
目录 Tomcat篇 1、Tomcat的缺省端口是多少?怎么修改? 2、Tomcat有哪几种Connector运行模式(优化)? 3、Tomcat有几种部署方式? 4、Tomcat容器时如何创建servlet类实例?用到了什么原理&…...
python——数据类型
数据类型目录 前言一、Number(数字)数字类型转换:二、String(字符串)常用字符串运算符:字符串格式化:三、Tuple(元组)常用运算符四、List(列表)嵌套列表:常用列表操作:五、Dictionary(字典)六、Set(集合)...
hive中如何求取中位数?
目录 中位数的概念代码实现准备数据实现 中位数的概念 中位数(Median)又称中值,统计学中的专有名词,是按顺序排列的一组数据中居于中间位置的数,代表一个样本、种群或概率分布中的一个数值,其可将数值集合…...
在C#中异步编程
在C#中,异步编程是一种编写并发和响应式代码的技术,通过将耗时的操作放在后台线程中执行,以避免阻塞主线程,提高程序的性能和响应性。异步编程使用async和await关键字,结合任务(Task)和异步操作…...

微服务保护--Feign整合Sentinel
限流是一种预防措施,虽然限流可以尽量避免因高并发而引起的服务故障,但服务还会因为其它原因而故障。而要将这些故障控制在一定范围,避免雪崩,就要靠线程隔离(舱壁模式)和熔断降级手段了。 线程隔离之前讲到…...
二进制to十六进制
输入小于等于十六位的二进制数据,输出十六进制数据; #include <stdio.h> #include <stdlib.h> #include <math.h>int main(void) {char arr[16] { 0 }; int array[16] { 0 }; int hex[4] { 0 };int i 0; int num 0;scanf("…...

Logistic 回归算法
Logistic 回归 Logistic 回归算法Logistic 回归简述Sigmoid 函数Logistic 回归模型表达式求解参数 $\theta $梯度上升优化算法 Logistic 回归简单实现使用 sklearn 构建 Logistic 回归分类器Logistic 回归算法的优缺点 Logistic 回归算法 Logistic 回归简述 Logistic 回归是一…...

ubuntu安装详细步骤
一,先下载vmware 1,第一步打开上面链接 下载网址 : https://www.vmware.com/products/workstation-pro/wo rkstation-pro-evaluation.html 许可证 JU090-6039P-08409-8J0QH-2YR7F ZF3R0-FHED2-M80TY-8QYGC-NPKYF FC7D0-D1YDL-M8DXZ-CYPZE-P2AY6 ZC3T…...
力扣5. 最长回文子串
动态规划 思路: 假设 dp[i][j] 为字符串 (i, j) 子串是否为回文的结果;那么 dp[i][j] dp[i 1][j - 1] 且 (s[i] s[j]);长度为1的字符串都是回文; 原字符串长度为1,是回文;原字符串子串长度为1ÿ…...
肆[4],函数VectorToHomMat2d/AffineTransPoint2d
函数VectorToHomMat2d C形式 LIntExport void VectorToHomMat2d( const HTuple& Px, const HTuple& Py, const HTuple& Qx, const HTuple& Qy, HTuple* HomMat2D);//参数1:图像坐标X数组 //参数2:图像坐标Y数组 //参数3:世界坐标X数组 //参数4:世界坐标Y…...
下载文件 后端返回给前端 response header 响应头
当浏览器在请求资源时,会通过http返回头中的content-type决定如何显示/处理将要加载的数据,如果这个类型浏览器能够支持阅览,浏览器就会直接展示该资源,比如png、jpeg、video等格式。在某些下载文件的场景中,服务端可能…...

lvs负载均集群
目录 NAT模式 LVS负载均衡群集部署 1.部署共享存储 2.配置节点服务器 192.168.17.130 编辑 192.168.17.133 3.配置负载调度器 4.测试效果 NAT模式 LVS负载均衡群集部署 负载调度器:内网关 ens33:192.168.17.70,外网关 ens36&#x…...

luttuce(RedisTempate)实现hash expire lua脚本
话不多说先放脚本: local argv ARGV local length #argv if length > 0 then local unpackArgs {} for i 1, length - 1 dotable.insert(unpackArgs, argv[i]) end if redis.call(exists, KEYS[1]) 1 thenredis.call(del, KEYS[1])redis.call(hset, KEYS[…...
【Xamarin】WebView连接局域网自动跳转外部浏览器问题的解决
xamarin在中国用的很少,但也有一些独到之处。例如用惯了Visual Studio的就很合适。而且类Java开发,几乎没什么障碍。 protected override void OnCreate(Bundle savedInstanceState) {base.OnCreate(savedInstanceState);Xamarin.Essentials.Platform.I…...

【Unity动画】实现不同的肢体动作自由搭配播放Layer+Avatar Mask
这个教程教你学会使用Unity 动画层配合布偶遮罩(AvaterMask) 实现从2个动画身上只保留部分肢体动作,然后搭配播放 例如:一个正常跑的动画片段,我只保留腿部动作,形成一个层叫Run_leg 然后在从一个攻击动作…...
将0x06(16进制)转换为二进制
将0x06(16进制)转换为二进制,可以按照如下步骤进行: 1. 将0x06中的字母"0x"去除。 2. 将数字"06"中的数字"0"去除。 3. 将数字"06"转换为二进制。 根据步骤1和步骤2,去除&q…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...
【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表
1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
linux 下常用变更-8
1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行,YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID: YW3…...
AI编程--插件对比分析:CodeRider、GitHub Copilot及其他
AI编程插件对比分析:CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展,AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者,分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...
实现弹窗随键盘上移居中
实现弹窗随键盘上移的核心思路 在Android中,可以通过监听键盘的显示和隐藏事件,动态调整弹窗的位置。关键点在于获取键盘高度,并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...
.Net Framework 4/C# 关键字(非常用,持续更新...)
一、is 关键字 is 关键字用于检查对象是否于给定类型兼容,如果兼容将返回 true,如果不兼容则返回 false,在进行类型转换前,可以先使用 is 关键字判断对象是否与指定类型兼容,如果兼容才进行转换,这样的转换是安全的。 例如有:首先创建一个字符串对象,然后将字符串对象隐…...
Mobile ALOHA全身模仿学习
一、题目 Mobile ALOHA:通过低成本全身远程操作学习双手移动操作 传统模仿学习(Imitation Learning)缺点:聚焦与桌面操作,缺乏通用任务所需的移动性和灵活性 本论文优点:(1)在ALOHA…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比
在机器学习的回归分析中,损失函数的选择对模型性能具有决定性影响。均方误差(MSE)作为经典的损失函数,在处理干净数据时表现优异,但在面对包含异常值的噪声数据时,其对大误差的二次惩罚机制往往导致模型参数…...