简讲LSM树(Log-Structured Merge Tree)

前言:最近在了解大数据实时分析技术druid,究其原理时发现用到了类LSM树思想以实现高效的数据插入,于是展开了对LSM的了解,了解之后感觉这东西虽然也并没有很特别,但在大数据、分布式架构中的应用还是非常有价值的,下面简单做下分享!

首先需要介绍下三种存储引擎:

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

众所周知,数据库的数据大多存储在磁盘上,而磁盘的访问相对内存的访问来说是一项很耗时的操作,对比如下。因此,提高数据库数据的查找速度的关键点之一便是尽量减少磁盘的访问次数,LSM正是基于这样的思考而设计。

更通俗的讲,LSM树原理就是把一棵大树拆分成N棵小树,它首先写入内存中,随着小树越来越大,内存中的小树会批量flush到磁盘中独立的文件中以提高IO性能,而为了提高读性能磁盘中的树定期可以做merge操作,合并成一棵大树。

前面提到HBase用到了LSM树思想,下面以其为例简单做下图解:

LSM思想中的两个要点:“拆分小树”、“合并大树”,在HBase中如何体现呢:

  • 数据插入不是直接写到磁盘,而是先写入内存MemStore,当达到一定条件后批量将内存flush到HRegion磁盘中(一般是Hadoop DataNode),这样MemStore就变成了DataNode上的磁盘文件StoreFile
  • 为了尽量提供好的读取能力,HRegionServer会定期对DataNode的数据做merge操作,彻底删除无效空间,多棵小树在这个时机合并成大树。
  • 另外,HBase为防止内存中未dump到磁盘的数据出现丢失,写内存的同时会写临时HLog到磁盘,这样一旦出了异常,能够通过HLog恢复内存数据。

通过以上的分析,应该知道LSM树的由来了,LSM树的设计思想非常朴素:将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘,不过读取的时候稍微麻烦,需要合并各个磁盘中历史数据和内存中最近修改操作,可见写快读慢特点很明显,所以LSM-tree显然比较适合那些数据插入操作远多于数据更新删除操作与读操作的场景!

可能有人会觉得,读能力应该是大部分系统最应该保证的特性,所以用读换写似乎不是个好买卖,但别急,这么分析一下:内存的速度远超磁盘,甚至可达1000倍以上,读取的性能提升,主要还是依靠内存命中率而非磁盘读的次数,所以可以从这个角度去思考优化。

最后讲讲LSM Tree主要的读优化方式:

  • Bloom filter: 就是个带随即概率的bitmap,可以快速的告诉你,某一个小树里有没有指定的那个数据的。于是就可以不用二分查找,而只需简单的计算几次就能知道数据是否在某个小树里。效率得到了提升,但付出的是空间代价。
  • compact:即前面已经提到的小树合并为大树,因为等需要的时候去读取多个小树会有性能问题,所以需要有个进程不断地将小树合并到大树上,这样读取的时候就直接读大树就可以了。

 以上内容可能有理解不到位的地方,欢迎指正!

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

一个技术人的金融之路

1 篇文章1 人订阅

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AhDung

【手记】调用Process.EnterDebugMode引发异常:并非所有引用的特权或组都分配给呼叫方

刚上线一个新版本,其中有台电脑打开软件就报【xx的类型初始值设定项引发异常】(还好不是一大波电脑,新东西上线就怕哀鸿遍野),如图:

1632
来自专栏岑玉海

Spark的机器学习算法mlib的例子运行

  Spark自带了机器学习的算法mlib,页面网址 http://spark.incubator.apache.org/docs/latest/mllib-g...

4075
来自专栏大数据智能实战

Spark Hbase读取操作的一些总结与测试

Spark连接HBase实现查询的操作有好多种步骤,其中常用的是直接调用Hbase本身提供的写入和读出的接口。 然而不少人在此基础上进行了各种封装,有的支持sp...

2627
来自专栏喔家ArchiSelf

MCU上的代码执行时间

在许多实时应用程序中,二八原则并不生效,CPU 可以花费95%(或更多)的时间在不到5% 的代码上。电动机控制、引擎控制、无线通信以及其他许多对时间敏感的应用程...

872
来自专栏Spark学习技巧

SparkStreaming源码阅读思路

1372
来自专栏我是攻城师

在scala中使用spark sql解决特定需求

3015
来自专栏Spark学习技巧

从coalesce算子发散开的

1023
来自专栏雪胖纸的玩蛇日常

pyhton 关于 configparser 配置 模块 实践使用中碰到的坑

2147
来自专栏Spark学习技巧

大数据查询——HBase读写设计与实践

作者 | 汪婷编辑 | Vincent导语:本文介绍的项目主要解决 check 和 opinion2 张历史数据表(历史数据是指当业务发生过程中的完整中间流程和...

2889
来自专栏FreeBuf

工业控制系统安全之——Modbus学习笔记

O、术语 1 word =2 byte; 1 byte =8 bit. 校验码:校验码是由前面的数据通过某种算法得出的,用以检验该组数据的正确性。代码作为数据在...

63510

扫码关注云+社区