Sorry!Hbase的LSM Tree就是可以为所欲为!

Stella981
• 阅读 540

我们先抛出一个问题:

Sorry!Hbase的LSM Tree就是可以为所欲为!

LSM树是HBase里使用的非常有创意的一种数据结构。在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中,则是使用日志结构合并树(Log-structured Merge Tree,LSM Tree)来组织数据。

首先,我们从B+树讲起

为什么在RDBMS中我们需要B+树(或者广义地说,索引)?一句话:减少寻道时间。在存储系统中广泛使用的HDD是磁性介质+机械旋转的,这就使得其顺序访问较快而随机访问较慢。使用B+树组织数据可以较好地利用HDD的这种特点,其本质是多路平衡查找树。一个典型的B+树如下图所示:

Sorry!Hbase的LSM Tree就是可以为所欲为!

  • B+树的磁盘读写代价更低:B+树的内部节点并没有指向关键字具体信息的指针,因此其内部节点相对B树更小,如果把所有同一内部节点的关键字存放在同一盘块中,那么盘块所能容纳的关键字数量也越多,一次性读入内存的需要查找的关键字也就越多,相对IO读写次数就降低了。

  • B+树的查询效率更加稳定:由于非终结点并不是最终指向文件内容的结点,而只是叶子结点中关键字的索引。所以任何关键字的查找必须走一条从根结点到叶子结点的路。所有关键字查询的路径长度相同,导致每一个数据的查询效率相当。

  • 由于B+树的数据都存储在叶子结点中,分支结点均为索引,方便扫库,只需要扫一遍叶子结点即可,但是B树因为其分支结点同样存储着数据,我们要找到具体的数据,需要进行一次中序遍历按序来扫,所以B+树更加适合在区间查询的情况,所以通常B+树用于数据库索引。

如果你对B+树不够熟悉,可以参考这里:https://blog.csdn.net/b_x_p/article/details/86434387

那么,B+树有什么缺点呢?

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

LSM Tree

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

LSM Tree(Log-structured merge-tree)起源于1996年的一篇论文:The log-structured merge-tree (LSM-tree)。当时的背景是:为一张数据增长很快的历史数据表设计一种存储结构,使得它能够解决:在内存不足,磁盘随机IO太慢下的严重写入性能问题。

LSM Tree(Log-structured merge-tree)广泛应用在HBase,TiDB等诸多数据库和存储引擎上:

Sorry!Hbase的LSM Tree就是可以为所欲为!

我们来看看大佬设计这个数据结构:

Sorry!Hbase的LSM Tree就是可以为所欲为!

Ck tree是一个有序的树状结构,数据的写入流转从C0 tree 内存开始,不断被合并到磁盘上的更大容量的Ck tree上。由于内存的读写速率都比外存要快非常多,因此数据写入的效率很高。并且数据从内存刷入磁盘时是预排序的,也就是说,LSM树将原本的随机写操作转化成了顺序写操作,写性能大幅提升。不过它牺牲了一部分读性能,因为读取时需要将内存中的数据和磁盘中的数据合并。

回到Hbase来,我们在之前的文章中《Hbase性能优化手册》中提到过Hbase的读写流程:

Sorry!Hbase的LSM Tree就是可以为所欲为!

MemStore是HBase中C0的实现,向HBase中写数据的时候,首先会写到内存中的MemStore,当达到一定阀值之后,flush(顺序写)到磁盘,形成新的StoreFile(HFile),最后多个StoreFile(HFile)又会进行Compact。

memstore内部维护了一个数据结构:ConcurrentSkipListMap,数据存储是按照RowKey排好序的跳跃列表。跳跃列表的算法有同平衡树一样的渐进的预期时间边界,并且更简单、更快速和使用更少的空间。

Sorry!Hbase的LSM Tree就是可以为所欲为!

HBase为了提升LSM结构下的随机读性能,还引入了布隆过滤器(建表语句中可以指定),对应HFile中的Bloom index block,其结构图如下所示。

Sorry!Hbase的LSM Tree就是可以为所欲为!

通过布隆过滤器,HBase就能以少量的空间代价,换来在读取数据时非常快速地确定是否存在某条数据,效率进一步提升。

欢迎关注,《大数据成神之路》系列文章 欢迎关注,《大数据成神之路》系列文章 欢迎关注,《大数据成神之路》系列文章

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
Wesley13 Wesley13
2年前
java将前端的json数组字符串转换为列表
记录下在前端通过ajax提交了一个json数组的字符串,在后端如何转换为列表。前端数据转化与请求varcontracts{id:'1',name:'yanggb合同1'},{id:'2',name:'yanggb合同2'},{id:'3',name:'yang
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
皕杰报表之UUID
​在我们用皕杰报表工具设计填报报表时,如何在新增行里自动增加id呢?能新增整数排序id吗?目前可以在新增行里自动增加id,但只能用uuid函数增加UUID编码,不能新增整数排序id。uuid函数说明:获取一个UUID,可以在填报表中用来创建数据ID语法:uuid()或uuid(sep)参数说明:sep布尔值,生成的uuid中是否包含分隔符'',缺省为
Easter79 Easter79
2年前
Twitter的分布式自增ID算法snowflake (Java版)
概述分布式系统中,有一些需要使用全局唯一ID的场景,这种时候为了防止ID冲突可以使用36位的UUID,但是UUID有一些缺点,首先他相对比较长,另外UUID一般是无序的。有些时候我们希望能使用一种简单一些的ID,并且希望ID能够按照时间有序生成。而twitter的snowflake解决了这种需求,最初Twitter把存储系统从MySQL迁移
Wesley13 Wesley13
2年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Wesley13 Wesley13
2年前
MySQL部分从库上面因为大量的临时表tmp_table造成慢查询
背景描述Time:20190124T00:08:14.70572408:00User@Host:@Id:Schema:sentrymetaLast_errno:0Killed:0Query_time:0.315758Lock_
为什么mysql不推荐使用雪花ID作为主键
作者:毛辰飞背景在mysql中设计表的时候,mysql官方推荐不要使用uuid或者不连续不重复的雪花id(long形且唯一),而是推荐连续自增的主键id,官方的推荐是auto_increment,那么为什么不建议采用uuid,使用uuid究
Python进阶者 Python进阶者
5个月前
Excel中这日期老是出来00:00:00,怎么用Pandas把这个去除
大家好,我是皮皮。一、前言前几天在Python白银交流群【上海新年人】问了一个Pandas数据筛选的问题。问题如下:这日期老是出来00:00:00,怎么把这个去除。二、实现过程后来【论草莓如何成为冻干莓】给了一个思路和代码如下:pd.toexcel之前把这