开发者社区> 桃子红了呐> 正文

LSM树——放弃读能力换取写能力,将多次修改放在内存中形成有序树再统一写入磁盘

简介:
+关注继续查看

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通过滚动合并和多页块的方法推迟和批量进行索引更新,充分利用内存来存储近期或常用数据以降低查找代价,利用硬盘来存储不常用数据以减少存储代价。

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

 

转自:http://blog.csdn.net/dbanote/article/details/8897599

LSM树是Hbase里非常有创意的一种数据结构,它和传统的B+树不太一样,下面先说说B+树。

1 B+树

相信大家对B+树已经非常的熟悉,比如Oracle的普通索引就是采用B+树的方式,下面是一个B+树的例子:

 

根节点和枝节点很简单,分别记录每个叶子节点的最小值,并用一个指针指向叶子节点。

叶子节点里每个键值都指向真正的数据块(如Oracle里的RowID),每个叶子节点都有前指针和后指针,这是为了做范围查询时,叶子节点间可以直接跳转,从而避免再去回溯至枝和跟节点。

B+树最大的性能问题是会产生大量的随机IO,随着新数据的插入,叶子节点会慢慢分裂,逻辑上连续的叶子节点在物理上往往不连续,甚至分离的很远,但做范围查询时,会产生大量读随机IO

对于大量的随机写也一样,举一个插入key跨度很大的例子,如7->1000->3->2000 ... 新插入的数据存储在磁盘上相隔很远,会产生大量的随机写IO.

从上面可以看出,低下的磁盘寻道速度严重影响性能(近些年来,磁盘寻道速度的发展几乎处于停滞的状态)。

2 LSM树

为了克服B+树的弱点,HBase引入了LSM树的概念,即Log-Structured Merge-Trees。

为了更好的说明LSM树的原理,下面举个比较极端的例子:

现在假设有1000个节点的随机key,对于磁盘来说,肯定是把这1000个节点顺序写入磁盘最快,但是这样一来,读就悲剧了,因为key在磁盘中完全无序,每次读取都要全扫描;

那么,为了让读性能尽量高,数据在磁盘中必须得有序,这就是B+树的原理,但是写就悲剧了,因为会产生大量的随机IO,磁盘寻道速度跟不上。

LSM树本质上就是在读写之间取得平衡,和B+树相比,它牺牲了部分读性能,用来大幅提高写性能

它的原理是把一颗大树拆分成N棵小树, 它首先写入到内存中(内存没有寻道速度的问题,随机写的性能得到大幅提升),在内存中构建一颗有序小树,随着小树越来越大,内存的小树会flush到磁盘上。当读时,由于不知道数据在哪棵小树上,因此必须遍历所有的小树,但在每颗小树内部数据是有序的。

 

以上就是LSM树最本质的原理,有了原理,再看具体的技术就很简单了。

1)首先说说为什么要有WAL(Write Ahead Log),很简单,因为数据是先写到内存中,如果断电,内存中的数据会丢失,因此为了保护内存中的数据,需要在磁盘上先记录logfile,当内存中的数据flush到磁盘上时,就可以抛弃相应的Logfile。

2)什么是memstore, storefile?很简单,上面说过,LSM树就是一堆小树,在内存中的小树即memstore,每次flush,内存中的memstore变成磁盘上一个新的storefile。

3)为什么会有compact?很简单,随着小树越来越多,读的性能会越来越差,因此需要在适当的时候,对磁盘中的小树进行merge,多棵小树变成一颗大树。

 

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

下面说说详细例子:

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

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

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

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

LSM Tree优化方式:

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

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

 

更详细的可以参考:http://weakyon.com/2015/04/08/Log-Structured-Merge-Trees.html













本文转自张昺华-sky博客园博客,原文链接:http://www.cnblogs.com/bonelee/p/6244810.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
操作系统入门到成神系列 二】磁盘比内存慢几万倍?
操作系统入门到成神系列 二】磁盘比内存慢几万倍?
30 0
2023阿里云服务器租用费用清单表(CPU内存带宽磁盘)
阿里云服务器1核1G配置19.17元3个月、306.72元一年,1核2G优惠价26.46元3个月、423.36元一年,2核4G配置42.66元3个月,2核8G配置58.86元3个月,4核8G 75.06元3个月,8核16G 139.86元3个月,还有4核16G、8核32G多配置可选
70 0
查看 cpu、内存、磁盘相关指标
查看 cpu、内存、磁盘相关指标
46 0
让你的对象跑出内存,写入到磁盘或者进行网络传输,一文掌握Java对象序列化
让你的对象跑出内存,写入到磁盘或者进行网络传输,一文掌握Java对象序列化
44 0
CleanMyMac X稳定版苹果电脑磁盘内存清理软件
Mac电脑用的时间久了,Mac用户尤其是MacBook用户会经常收到“磁盘几乎已满”的提示,如何解决这个问题,当我们使用苹果MAC一段时间后,就会有大量的垃圾文件占用磁盘空间,例如系统缓存文件、应用程序缓存文件、备份和重复文件、旧版的应用程序及其部件等,为了不影响电脑的后续使用,我们需要经常清理磁盘空间,这里分享一个处理磁盘空间不足提示的小方法。CleanMyMac X下载:http://t.csdn.cn/ye9sT
35 0
ELK搭建(三):监控服务器CPU、网络、磁盘、内存指标
本期我们来讲解如何通过ELK+metricbeat来监控服务器/主机中的CPU、网络、磁盘、内存等指标变化。并绘制会数据看板来方便我们实时监控
160 0
Docker资源(CPU/内存/磁盘IO/GPU)限制与分配指南
什么是cgroup? cgroups其名称源自控制组群(control groups)的简写,是Linux内核的一个功能,用来限制、控制与分离一个进程组(如CPU、内存、磁盘输入输出等)。 什么是Docker资源限制?
938 0
阿里云服务器租用费用(CPU内存带宽磁盘)费用详单
阿里云服务器租用费用,包括优惠活动报价、云服务器CPU内存、公网带宽和系统盘收费明细
132 0
阿里云服务器配置不够可以升级CPU内存带宽磁盘均可升级配置
阿里云服务器支持按需升降配,购买阿里云ECS云服务器不用担心服务器配置高低的问题,如果后续使用过程中云服务器配置不够或者过高,可以使用控制台升降配功能来调整云服务器配置:
280 0
+关注
桃子红了呐
文章
问答
视频
文章排行榜
最热
最新
相关电子书
更多
云服务器ECS内存增强型实例re6全新发布
立即下载
探究高性能的海量节点树
立即下载
用户态高速块缓存方案
立即下载