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,多棵小树变成一颗大树。
分享到:
相关推荐
1、内容概要:Hadoop+Spark+Hive+HBase+Oozie+Kafka+Flume+Flink+Elasticsearch+Redash等大数据集群及组件搭建指南(详细搭建步骤+实践过程问题总结)。 2、适合人群:大数据运维、大数据相关技术及组件初学者。 3、...
徐老师大数据培训Hadoop+HBase+ZooKeeper+Spark+Kafka+Scala+Ambari
Hadoop集群搭建必备安装包,包括zookeeper3.4.12+hbase1.4.4+sqoop1.4.7bin_hadoop-2.6.0+kafka2.10亲测可用。
基于Python+SpringBoot+Vue+HDFS+MapReduce+HBase+Hive+Kafka+Sp
1-7+HBase+for+Solr+介绍
redhat 6.4 hadoop2.7+hbase1.0+hive1.2+zookeeper3.4.6安装配置, ntp配置
搭建hadoop单机版+hbase单机版+pinpoint整合springboot
HBASE-1.2.6.bin+src.tar.gz ,如果有需要的可以下载。
HBase 实践 如何破解 HBase+ElasticSearch 组合使用遇到的难题.docx
hbase-1.2.6-bin+src.tar.rar 配合教程详见博客https://blog.csdn.net/haobindayi/article/details/82948123
大数据 hadoop spark hbase ambari全套视频教程(购买的付费视频)
springboot集成phoenix+hbase 完整demo!!!!!!!
基于ssh+hadoop+hbase的简单云盘系统+源代码+文档说明 -------- 不懂运行,下载完可以私聊问,可远程教学 该资源内项目源码是个人的毕设,代码都测试ok,都是运行成功后才上传资源,答辩评审平均分达到96分,放心...
apache-phoenix-4.13.0-HBase-1.3-bin.tar.gz hadoop-2.7.4.tar.gz hbase-1.3.1-bin.tar.gz jdk-8u144-linux-x64.tar.gz kafka_2.12-1.0.0.tgz scala-2.12.4.tar.gz scala-2.12.4.tgz spark-2.2.0-bin-hadoop2.7.tgz...
使用github中最新的nutch-2.x源码,奋战10天拿下的Hadoop-2.4.0+Hbase-0.94.18+Nutch-2.3配置攻略,在ubuntu14.04上成功运行本地和分布式爬虫。文档详细描述了三者版本不兼容问题的解决方案以及各个配置文件的详细...
基于Flume+Kafka+Hbase+Flink+FineBI的实时综合案例.txt基于Flume+Kafka+Hbase+Flink+FineBI的实时综合案例.txt基于Flume+Kafka+Hbase+Flink+FineBI的实时综合案例.txt基于Flume+Kafka+Hbase+Flink+FineBI的实时综合...
利用两台云主机(真实环境至少三台)安装hadoop+hbase+sqoop2+phoenix+kerberos的过程笔记,从伪分布式到kerberos认证。
HBase权威指南 中文版的 加 官方文档
- 从 hbase 表 `userProduct` 中查询用户历史评分商品列表。 - 根据用户刚评分的 `productId` 从 hbase 表 `itemCFRecommend` 表中查询相关的商品列表 - 对相关商品列表根据之前查出的最近评分商品列表和历史评分...
hadoop集群配置流程以及用到的配置文件,hadoop2.8.4、hbase2.1.0、zookeeper3.4.12