当前位置: 首页 > news >正文

数据结构 | Log-Structured Merge Tree (LSM Tree)

今天介绍LSM Tree这个数据结构,严格意义上来说,他并不像他的名字一样是一棵树型的数据结构,而更多是一种设计思想。

LSM Tree最先在1996年被提出,后来被广泛运用于现代NoSQL(非关系型数据库)系统中,包括BigTable, Dynamo, HBase, Cassandra, LevelDB, RocksDB, and AsterixDB.

241157b8646cffd77dc4486fa024f7c0.png

LSM Tree主要是瞄准了IO操作中,顺序写的速度比随机写快几个数量级的特点,采用out-of-place 更新的特性,将随机写入累积到顺序写入,以利用存储设备的高顺序写入带宽。

那他是怎么做到的呢?实际上设计上其实也相当的简单粗暴。

LSM Tree通过将写入操作集中在内存中,并定期将数据合并到持久性存储介质(如磁盘)上,实现了高吞吐量的写入和高效的查询性能。LSM Tree引入了“组件”的概念,组件是指存储数据的单元或数据结构,它们按照特定规则组织和管理数据。

组件根据其存在于内存中或是磁盘中,被划分为:

1. 内存组件(Memory Component):LSM树通过内存组件(也称为memtable)存储最近写入的数据。内存组件通常是一个有序的数据结构(如平衡树或跳表),它提供快速的写入和查询操作。写入操作首先在内存组件中进行,以实现低延迟的写入性能。

2. 磁盘组件(Disk Component):当内存组件达到容量限制或触发某些条件时,LSM树将内存组件中的数据刷新到磁盘组件中。磁盘组件通常是一系列按键有序存储的文件(SSTable),其中每个文件称为一个层级(level)。较新的数据存储在较高的层级,而较旧的数据存储在较低的层级。每个层级的文件都是顺序写入的。磁盘组件之间的数据合并操作以保持数据的有序性和紧凑性。

ac5f8a40b9d7bd3bc24a88903aff495a.png

因此,不难看出,无论是在内存组件还是磁盘组件,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的读性能?

  1. 可以考虑采用布隆过滤器,提前过滤一些明确不存在的key,来加快读性能;

  2. 可以考虑采用在有序结构上使用的更加高效的查找算法,比如二分查找来提高查找速度;

  3. 可以考虑使用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(非关系型数据库)系统中&#xf…...

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−11​0−11​12−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十六进制

输入小于等于十六位的二进制数据&#xff0c;输出十六进制数据&#xff1b; #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安装详细步骤

一&#xff0c;先下载vmware 1&#xff0c;第一步打开上面链接 下载网址 : 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. 最长回文子串

动态规划 思路&#xff1a; 假设 dp[i][j] 为字符串 (i, j) 子串是否为回文的结果&#xff1b;那么 dp[i][j] dp[i 1][j - 1] 且 (s[i] s[j])&#xff1b;长度为1的字符串都是回文&#xff1b; 原字符串长度为1&#xff0c;是回文&#xff1b;原字符串子串长度为1&#xff…...

肆[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 响应头

当浏览器在请求资源时&#xff0c;会通过http返回头中的content-type决定如何显示/处理将要加载的数据&#xff0c;如果这个类型浏览器能够支持阅览&#xff0c;浏览器就会直接展示该资源&#xff0c;比如png、jpeg、video等格式。在某些下载文件的场景中&#xff0c;服务端可能…...

lvs负载均集群

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

luttuce(RedisTempate)实现hash expire lua脚本

话不多说先放脚本&#xff1a; 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在中国用的很少&#xff0c;但也有一些独到之处。例如用惯了Visual Studio的就很合适。而且类Java开发&#xff0c;几乎没什么障碍。 protected override void OnCreate(Bundle savedInstanceState) {base.OnCreate(savedInstanceState);Xamarin.Essentials.Platform.I…...

【Unity动画】实现不同的肢体动作自由搭配播放Layer+Avatar Mask

这个教程教你学会使用Unity 动画层配合布偶遮罩&#xff08;AvaterMask&#xff09; 实现从2个动画身上只保留部分肢体动作&#xff0c;然后搭配播放 例如&#xff1a;一个正常跑的动画片段&#xff0c;我只保留腿部动作&#xff0c;形成一个层叫Run_leg 然后在从一个攻击动作…...

将0x06(16进制)转换为二进制

将0x06&#xff08;16进制&#xff09;转换为二进制&#xff0c;可以按照如下步骤进行&#xff1a; 1. 将0x06中的字母"0x"去除。 2. 将数字"06"中的数字"0"去除。 3. 将数字"06"转换为二进制。 根据步骤1和步骤2&#xff0c;去除&q…...

Objective-C常用命名规范总结

【OC】常用命名规范总结 文章目录 【OC】常用命名规范总结1.类名&#xff08;Class Name)2.协议名&#xff08;Protocol Name)3.方法名&#xff08;Method Name)4.属性名&#xff08;Property Name&#xff09;5.局部变量/实例变量&#xff08;Local / Instance Variables&…...

React Native在HarmonyOS 5.0阅读类应用开发中的实践

一、技术选型背景 随着HarmonyOS 5.0对Web兼容层的增强&#xff0c;React Native作为跨平台框架可通过重新编译ArkTS组件实现85%以上的代码复用率。阅读类应用具有UI复杂度低、数据流清晰的特点。 二、核心实现方案 1. 环境配置 &#xff08;1&#xff09;使用React Native…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

项目部署到Linux上时遇到的错误(Redis,MySQL,无法正确连接,地址占用问题)

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理)

上一章用到了V2 的概念&#xff0c;其实 Fiori当中还有 V4&#xff0c;咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)&#xff0c;代理中间件&#xff08;ui5-middleware-simpleproxy&#xff09;-CSDN博客…...

宇树科技,改名了!

提到国内具身智能和机器人领域的代表企业&#xff0c;那宇树科技&#xff08;Unitree&#xff09;必须名列其榜。 最近&#xff0c;宇树科技的一项新变动消息在业界引发了不少关注和讨论&#xff0c;即&#xff1a; 宇树向其合作伙伴发布了一封公司名称变更函称&#xff0c;因…...