【博客718】时序数据库基石:LSM Tree(log-structured merge-tree)

2024-06-15 14:36

本文主要是介绍【博客718】时序数据库基石:LSM Tree(log-structured merge-tree),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

时序数据库基石:LSM Tree(log-structured merge-tree)

1、为什么需要LSM Tree

LSM被设计来提供比传统的B+树更好的写操作吞吐量,通过消去随机的本地更新操作来达到这个目标,使得写入都是顺序写,而不是随机写。
那么为什么这是一个好的方法呢?这个问题的本质还是磁盘随机操作慢,顺序读写快的老问题。这二种操作存在巨大的差距,无论是磁盘还是SSD。

2、LSM Tree是一种思想,非固定实现方式

LSM树是一种将:

  • 磁盘顺序写
  • 多个树状数据结构集合
  • 冷热(新老)数据分级
  • 定期归并
  • 非原地更新

这几种特性统一在一起的思想。

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

3、LSM Tree的定义:

  • LSM树是一个横跨内存和磁盘的,包含多颗"子树"的一个森林。
  • LSM树分为Level 0,Level 1,Level 2 … Level n 多颗子树,其中只有Level 0在内存中,其余Level 1-n在磁盘中。
  • 内存中的Level 0子树一般采用排序树(红黑树/AVL树)、跳表或者TreeMap等这类有序的数据结构,方便后续顺序写磁盘。
  • 磁盘中的Level 1-n子树,本质是数据排好序后顺序写到磁盘上的文件,只是叫做树而已。
  • 每一层的子树都有一个阈值大小,达到阈值后会进行合并,合并结果写入下一层。
  • 只有内存中数据允许原地更新,磁盘上数据的变更只允许追加写,不做原地更新。

在这里插入图片描述

4、LSM Tree中的各级结构

在这里插入图片描述

4-1、MemTable

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

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

4-2、Immutable MemTable

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

4-3、SSTable

LSM Tree采取读写分离的策略,会优先保证写操作的性能;其数据首先存储内存中,而后需要定期 Flush 到硬盘上。LSM-Tree 通过内存插入与磁盘的顺序写,来达到最优的写性能,因为这会大大降低磁盘的寻道次数,一次磁盘 IO 可以写入多个索引块。HBase, Cassandra, RockDB, LevelDB, SQLite 等都是基于 LSM Tree 来构建索引的数据库;LSM Tree 的树节点可以分为两种,保存在内存中的称之为 MemTable, 保存在磁盘上的称之为 SSTable。

LSM tree 通过一种叫做 SSTable (Sorted Strings Table) 的格式,持久化到硬盘上。正如其名,SSTable 是一种用来存储有序的键值对的格式,其中键的组织是有序存储的。一个SSTable 会包括多个有序的子文件,被称为 segment 。 这些 segments 一旦被写入硬盘,就不可以再修改了。一个简单的SSTable 例子如下图所示:

在这里插入图片描述

SSTable的查找优化:
在这里插入图片描述

在这里插入图片描述

这篇关于【博客718】时序数据库基石:LSM Tree(log-structured merge-tree)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1063727

相关文章

Spring Security基于数据库验证流程详解

Spring Security 校验流程图 相关解释说明(认真看哦) AbstractAuthenticationProcessingFilter 抽象类 /*** 调用 #requiresAuthentication(HttpServletRequest, HttpServletResponse) 决定是否需要进行验证操作。* 如果需要验证,则会调用 #attemptAuthentica

MySQL数据库宕机,启动不起来,教你一招搞定!

作者介绍:老苏,10余年DBA工作运维经验,擅长Oracle、MySQL、PG、Mongodb数据库运维(如安装迁移,性能优化、故障应急处理等)公众号:老苏畅谈运维欢迎关注本人公众号,更多精彩与您分享。 MySQL数据库宕机,数据页损坏问题,启动不起来,该如何排查和解决,本文将为你说明具体的排查过程。 查看MySQL error日志 查看 MySQL error日志,排查哪个表(表空间

内核启动时减少log的方式

内核引导选项 内核引导选项大体上可以分为两类:一类与设备无关、另一类与设备有关。与设备有关的引导选项多如牛毛,需要你自己阅读内核中的相应驱动程序源码以获取其能够接受的引导选项。比如,如果你想知道可以向 AHA1542 SCSI 驱动程序传递哪些引导选项,那么就查看 drivers/scsi/aha1542.c 文件,一般在前面 100 行注释里就可以找到所接受的引导选项说明。大多数选项是通过"_

深入理解数据库的 4NF:多值依赖与消除数据异常

在数据库设计中, "范式" 是一个常常被提到的重要概念。许多初学者在学习数据库设计时,经常听到第一范式(1NF)、第二范式(2NF)、第三范式(3NF)以及 BCNF(Boyce-Codd范式)。这些范式都旨在通过消除数据冗余和异常来优化数据库结构。然而,当我们谈到 4NF(第四范式)时,事情变得更加复杂。本文将带你深入了解 多值依赖 和 4NF,帮助你在数据库设计中消除更高级别的异常。 什么是

DM8数据库安装后配置

1 前言 在上篇文章中,我们已经成功将库装好。在安装完成后,为了能够更好地满足应用需求和保障系统的安全稳定运行,通常需要进行一些基本的配置。下面是一些常见的配置项: 数据库服务注册:默认包含14个功能模块,将这些模块注册成服务后,可以更好的启动和管理这些功能;基本的实例参数配置:契合应用场景和发挥系统的最大性能;备份:有备无患;… 2 注册实例服务 注册了实例服务后,可以使用系统服务管理,

速了解MySQL 数据库不同存储引擎

快速了解MySQL 数据库不同存储引擎 MySQL 提供了多种存储引擎,每种存储引擎都有其特定的特性和适用场景。了解这些存储引擎的特性,有助于在设计数据库时做出合理的选择。以下是 MySQL 中几种常用存储引擎的详细介绍。 1. InnoDB 特点: 事务支持:InnoDB 是一个支持 ACID(原子性、一致性、隔离性、持久性)事务的存储引擎。行级锁:使用行级锁来提高并发性,减少锁竞争

开源分布式数据库中间件

转自:https://www.csdn.net/article/2015-07-16/2825228 MyCat:开源分布式数据库中间件 为什么需要MyCat? 虽然云计算时代,传统数据库存在着先天性的弊端,但是NoSQL数据库又无法将其替代。如果传统数据易于扩展,可切分,就可以避免单机(单库)的性能缺陷。 MyCat的目标就是:低成本地将现有的单机数据库和应用平滑迁移到“云”端

ORACLE 11g 创建数据库时 Enterprise Manager配置失败的解决办法 无法打开OEM的解决办法

在win7 64位系统下安装oracle11g,在使用Database configuration Assistant创建数据库时,在创建到85%的时候报错,错误如下: 解决办法: 在listener.ora中增加对BlueAeri-PC或ip地址的侦听,具体步骤如下: 1.启动Net Manager,在“监听程序”--Listener下添加一个地址,主机名写计

MyBatis 切换不同的类型数据库方案

下属案例例当前结合SpringBoot 配置进行讲解。 背景: 实现一个工程里面在部署阶段支持切换不同类型数据库支持。 方案一 数据源配置 关键代码(是什么数据库,该怎么配就怎么配) spring:datasource:name: test# 使用druid数据源type: com.alibaba.druid.pool.DruidDataSource# @需要修改 数据库连接及驱动u

树(Tree)——《啊哈!算法》

树 什么是树?树是一种特殊的图,不包含回路的连通无向树。 正因为树有着“不包含回路”这个特点,所以树就被赋予了很多特性。 一棵树中的任意两个结点有且仅有唯一的一条路径连通。一棵树如果有n个结点,那么它一定恰好有n-1条边。在一棵树中加一条边将会构成一个回路。 一棵树有且只有一个根结点。 没有父结点的结点称为根结点(祖先)。没有子结点的结点称为叶结点。如果一个结点既不是根结点也不是叶