LSM树(Log-Structured Merge Tree)存储引擎

2024-06-16 13:48

本文主要是介绍LSM树(Log-Structured Merge Tree)存储引擎,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

LSM树(Log-Structured Merge Tree)存储引擎

代表数据库:nessDB、leveldb、hbase等

核心思想的核心就是放弃部分读能力,换取写入的最大化能力。LSM Tree ,这个概念就是结构化合并树的意思,它的核心思路其实非常简单,就是假定内存足够大,因此不需要每次有数据更新就必须将数据写入到磁盘中,而可以先将最新的数据驻留在磁盘中,等到积累到最后多之后,再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的,可以通过合并排序的方式快速合并到一起)。

日志结构的合并树(LSM-tree)是一种基于硬盘的数据结构,与B-tree相比,能显著地减少硬盘磁盘臂的开销,并能在较长的时间提供对文件的高速插入(删除)。然而LSM-tree在某些情况下,特别是在查询需要快速响应时性能不佳。通常LSM-tree适用于索引插入比检索更频繁的应用系统。Bigtable在提供Tablet服务时,使用GFS来存储日志和SSTable,而GFS的设计初衷就是希望通过添加新数据的方式而不是通过重写旧数据的方式来修改文件。而LSM-tree通过滚动合并和多页块的方法推迟和批量进行索引更新,充分利用内存来存储近期或常用数据以降低查找代价,利用硬盘来存储不常用数据以减少存储代价。

磁盘的技术特性:对磁盘来说,能够最大化的发挥磁盘技术特性的使用方式是:一次性的读取或写入固定大小的一块数据,并尽可能的减少随机寻道这个操作的次数。

\

 

LSM和Btree差异就要在读性能和写性能进行舍和求。在牺牲的同事,寻找其他方案来弥补。

1、LSM具有批量特性,存储延迟。当写读比例很大的时候(写比读多),LSM树相比于B树有更好的性能。因为随着insert操作,为了维护B树结构,节点分裂。读磁盘的随机读写概率会变大,性能会逐渐减弱。 多次单页随机写,变成一次多页随机写,复用了磁盘寻道时间,极大提升效率。

2、B树的写入过程:对B树的写入过程是一次原位写入的过程,主要分为两个部分,首先是查找到对应的块的位置,然后将新数据写入到刚才查找到的数据块中,然后再查找到块所对应的磁盘物理位置,将数据写入去。当然,在内存比较充足的时候,因为B树的一部分可以被缓存在内存中,所以查找块的过程有一定概率可以在内存内完成,不过为了表述清晰,我们就假定内存很小,只够存一个B树块大小的数据吧。可以看到,在上面的模式中,需要两次随机寻道(一次查找,一次原位写),才能够完成一次数据的写入,代价还是很高的。

3、LSM Tree放弃磁盘读性能来换取写的顺序性,似乎会认为读应该是大部分系统最应该保证的特性,所以用读换写似乎不是个好买卖。但别急,听我分析一下。

a、内存的速度远超磁盘,1000倍以上。而读取的性能提升,主要还是依靠内存命中率而非磁盘读的次数  

b、写入不占用磁盘的io,读取就能获取更长时间的磁盘io使用权,从而也可以提升读取效率。例如LevelDb的SSTable虽然降低了了读的性能,但如果数据的读取命中率有保障的前提下,因为读取能够获得更多的磁盘io机会,因此读取性能基本没有降低,甚至还会有提升。而写入的性能则会获得较大幅度的提升,基本上是5~10倍左右。

下面说说详细例子:

LSM Tree弄了很多个小的有序结构,比如每m个数据,在内存里排序一次,下面100个数据,再排序一次……这样依次做下去,我就可以获得N/m个有序的小的有序结构。

在查询的时候,因为不知道这个数据到底是在哪里,所以就从最新的一个小的有序结构里做二分查找,找得到就返回,找不到就继续找下一个小有序结构,一直到找到为止。

 

很容易可以看出,这样的模式,读取的时间复杂度是(N/m)*log2N 。读取效率是会下降的。

这就是最本来意义上的LSM tree的思路。那么这样做,性能还是比较慢的,于是需要再做些事情来提升,怎么做才好呢?

LSM Tree优化方式:

a、Bloom filter: 就是个带随即概率的bitmap,可以快速的告诉你,某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找,而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升,但付出的是空间代价。

b、compact:小树合并为大树:因为小树他性能有问题,所以要有个进程不断地将小树合并到大树上,这样大部分的老数据查询也可以直接使用log2N的方式找到,不需要再进行(N/m)*log2n的查询了




  • 哈希存储引擎  是哈希表的持久化实现,支持增、删、改以及随机读取操作,但不支持顺序扫描,对应的存储系统为key-value存储系统。对于key-value的插入以及查询,哈希表的复杂度都是O(1),明显比树的操作O(n)快,如果不需要有序的遍历数据,哈希表就是your Mr.Right
  • B树存储引擎是B树(关于B树的由来,数据结构以及应用场景可以看之前一篇博文)的持久化实现,不仅支持单条记录的增、删、读、改操作,还支持顺序扫描(B+树的叶子节点之间的指针),对应的存储系统就是关系数据库(Mysql等)。
  • LSM树(Log-Structured Merge Tree)存储引擎和B树存储引擎一样,同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊,LSM树和B+树相比,LSM树牺牲了部分读性能,用来大幅提高写性能。

通过以上的分析,应该知道LSM树的由来了,LSM树的设计思想非常朴素:将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘,不过读取的时候稍微麻烦,需要合并磁盘中历史数据和内存中最近修改操作,所以写入性能大大提升,读取时可能需要先看是否命中内存,否则需要访问较多的磁盘文件。极端的说,基于LSM树实现的HBase的写性能比MySQL高了一个数量级,读性能低了一个数量级。

LSM树原理把一棵大树拆分成N棵小树,它首先写入内存中,随着小树越来越大,内存中的小树会flush到磁盘中,磁盘中的树定期可以做merge操作,合并成一棵大树,以优化读性能。

 

以上这些大概就是HBase存储的设计主要思想,这里分别对应说明下:

  • 因为小树先写到内存中,为了防止内存数据丢失,写内存的同时需要暂时持久化到磁盘,对应了HBase的MemStore和HLog
  • MemStore上的树达到一定大小之后,需要flush到HRegion磁盘中(一般是Hadoop DataNode),这样MemStore就变成了DataNode上的磁盘文件StoreFile,定期HRegionServer对DataNode的数据做merge操作,彻底删除无效空间,多棵小树在这个时机合并成大树,来增强读性能。

 

关于LSM Tree,对于最简单的二层LSM Tree而言,内存中的数据和磁盘你中的数据merge操作,如下图

图来自lsm论文

lsm tree,理论上,可以是内存中树的一部分和磁盘中第一层树做merge,对于磁盘中的树直接做update操作有可能会破坏物理block的连续性,但是实际应用中,一般lsm有多层,当磁盘中的小树合并成一个大树的时候,可以重新排好顺序,使得block连续,优化读性能。

hbase在实现中,是把整个内存在一定阈值后,flush到disk中,形成一个file,这个file的存储也就是一个小的B+树,因为hbase一般是部署在hdfs上,hdfs不支持对文件的update操作,所以hbase这么整体内存flush,而不是和磁盘中的小树merge update,这个设计也就能讲通了。内存flush到磁盘上的小树,定期也会合并成一个大树。整体上hbase就是用了lsm tree的思路。

这篇关于LSM树(Log-Structured Merge Tree)存储引擎的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

异构存储(冷热数据分离)

异构存储主要解决不同的数据,存储在不同类型的硬盘中,达到最佳性能的问题。 异构存储Shell操作 (1)查看当前有哪些存储策略可以用 [lytfly@hadoop102 hadoop-3.1.4]$ hdfs storagepolicies -listPolicies (2)为指定路径(数据存储目录)设置指定的存储策略 hdfs storagepolicies -setStoragePo

HDFS—存储优化(纠删码)

纠删码原理 HDFS 默认情况下,一个文件有3个副本,这样提高了数据的可靠性,但也带来了2倍的冗余开销。 Hadoop3.x 引入了纠删码,采用计算的方式,可以节省约50%左右的存储空间。 此种方式节约了空间,但是会增加 cpu 的计算。 纠删码策略是给具体一个路径设置。所有往此路径下存储的文件,都会执行此策略。 默认只开启对 RS-6-3-1024k

内核启动时减少log的方式

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

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

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

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

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

Smarty模板引擎工作机制(一)

深入浅出Smarty模板引擎工作机制,我们将对比使用smarty模板引擎和没使用smarty模板引擎的两种开发方式的区别,并动手开发一个自己的模板引擎,以便加深对smarty模板引擎工作机制的理解。 在没有使用Smarty模板引擎的情况下,我们都是将PHP程序和网页模板合在一起编辑的,好比下面的源代码: <?php$title="深处浅出之Smarty模板引擎工作机制";$content=

ImportError: cannot import name ‘print_log‘ from ‘logging‘

mmcv升级到2.+后删除了很多 解决 查FAQ文档,找到 添加到mmcv.utils下即可

DAY16:什么是慢查询,导致的原因,优化方法 | undo log、redo log、binlog的用处 | MySQL有哪些锁

目录 什么是慢查询,导致的原因,优化方法 undo log、redo log、binlog的用处  MySQL有哪些锁   什么是慢查询,导致的原因,优化方法 数据库查询的执行时间超过指定的超时时间时,就被称为慢查询。 导致的原因: 查询语句比较复杂:查询涉及多个表,包含复杂的连接和子查询,可能导致执行时间较长。查询数据量大:当查询的数据量庞大时,即使查询本身并不复杂,也可能导致

ORACLE语法-包(package)、存储过程(procedure)、游标(cursor)以及java对Result结果集的处理

陈科肇 示例: 包规范 CREATE OR REPLACE PACKAGE PACK_WMS_YX IS-- Author : CKZ-- Created : 2015/8/28 9:52:29-- Purpose : 同步数据-- Public type declarations,游标 退休订单TYPE retCursor IS REF CURSOR;-- RETURN vi_co_co

多数据源的事务处理总是打印很多无用的log日志

之前做了一个项目,需要用到多数据源以及事务处理,在使用事务处理,服务器总是打印很多关于事务处理的log日志(com.atomikos.logging.Slf4jLogger),但是我们根本不会用到这些log日志,反而使得查询一些有用的log日志变得困难。那要如何屏蔽这些log日志呢? 之前的项目是提高项目打印log日志的级别,后来觉得这样治标不治本。 现在有一个更好的方法: 我使用的是log