学习
实践
活动
专区
工具
TVP
写文章
专栏首页大数据技术博文学大数据必懂系列之LSM-Tree

学大数据必懂系列之LSM-Tree

LSM-Tree 介绍

LSM树(Log-Structured-Merge-Tree)(日志结构合并树)是一种能够提升磁盘写入速度的数据结构,它通过将大量的磁盘随机写操作,转换为批量顺序写的方式来得到写入性能的提升。但是同时也牺牲了一部分的读性能

LSM-Tree 设计思想

LSM-Tree的设计为一种多层结构、有序数据、针对磁盘存储的一种数据结构,一般在各种Key/Value的数据库中很常用。核心思想就是充分利用磁盘批量顺序写远比随机写高效的特性,同时舍弃部分读效率来换取写效率的大幅提升

一个LSM-Tree是由两个或两个以上的树状组件数据结构组成的,其中一个是驻留在内存中的树,称之为C0树,一个是驻留在磁盘中的树,称之为C1树,除了C0是驻留在内存之外,C1-Ck的树都是驻留在磁盘中的。

在LSM树中,最开始的数据是写入到内存中,也就是C0层的树结构中,当C0树的大小阈值达到了一定大小之后,C0树中的全部或部分数据就会刷入磁盘中的C1树。当然其中还会涉及到容错恢复、合并检查点、旧的C0树子页的清理等等内容,如果感兴趣可以参阅论文:https://www.cs.umb.edu/~poneil/lsmtree.pdf。

数据首先会插入到内存中的树,为了防止数据丢失,写内存的同时需要暂时持久化到磁盘,即输入数据时数据会以完全有序的形式先存储在日志文件(write ahead log (WAL)预写日志)中(对应HBase的MemStore和HLog)。当发生故障时,比如机器关机、进程挂掉、断电等未知风险的时候,会导致内存中数据丢失,通过WAL的机制就可以将数据从日志文件中进行恢复。

LSM-Tree 合并操作

每次持久化到硬盘中是一条独立的线程做的,并且生成单独的文件,因此C1树也不止一个文件,当文件数变多的时候,势必导致每一次查询都会涉及到大量文件的打开,每一次文件的打开都是对 I/O 的消耗。为了控制这种 读放大 的情况出现,LSM Tree 就需要考虑小文件合并的问题。

合并操作会从左至右遍历内存中的叶子节点与磁盘中树的叶子节点进行合并,当合并的数据量达到磁盘的存储页的大小时,会将合并的数据持久化到磁盘。同时更新父亲节点对叶子节点的指针

LSM-Tree性能的衡量因素

几个名词的解释

读放大

过多读取请求。RA 由每个查询的磁盘读取次数计算得出。当数据读取的频率远远超过了数据大小时,从而影响到了读性能,我们称之为读放大,为了减轻读放大,LSM-Tree采用布隆过滤器来避免读取不包括查询键值的SSTable文件

空间放大

磁盘空间使用过多,磁盘使用大于数据实际大小时称之为空间放大。因为空间有限,SA 计算为磁盘上数据库文件的大小与实际数据大小的比率。当使用的磁盘空间大于数据大小时,就会出现高 SA

写放大

过度压缩相同的数据。WA 是通过写入存储的字节数与写入数据库的字节数的比率来计算的。当写入存储的字节数/秒多于实际写入数据库的字节数时,就会出现高 WA

LSM-Tree在HBase中的应用

首先我们来看一下HBase的写入的流程设计:

角色说明 :

RegionServer——HBase工作节点,它在LSM-Tree形式的HDFS中执行信息块的管理和存储,由RegionServer在幕后用于实际存储数据

从底层来看,HBase的大部分功能都位于对表执行读写操作的区域性服务器中。从技术上讲,每个表都可以作为称为HRegions的独立部分的集合分布在不同的region服务器上。单个region服务器节点可以容纳一个表的多个HRegions。每个HRegion保存一定范围内内存和磁盘空间共享的行,并按键属性排序。这些范围在不同区域之间不相交,因此我们可以依赖它们在整个集群中的顺序行为。单个RegionServer的HRegion包括以下部分:

预写日志(WAL)文件——在进入内存之前,每次写操作都持久化数据的第一个位置。正如我前面提到的,lsm树的第一部分保存在内存中,这意味着它可能会受到一些外部因素的影响,比如示例中的功率损失。将此类操作的日志文件保存在单独的位置将允许轻松地恢复此部分,而不会有任何松动。

Memstore——在内存中保存最新信息的排序集合。它是前面描述的lms树结构第一部分的实际实现。定期执行滚动合并到本地硬盘驱动器上称为HFiles的存储文件

HFile -表示从Memstore接收到的一小段数据,并保存在HDFS中。每个HFile包含经过排序的KeyValues集合和B-Tree+索引,该索引允许在不读取整个文件的情况下查找数据。HBase会定期对这些文件进行合并排序操作,使其符合标准HDFS块的配置大小,避免小文件问题

上图的流程说明:

  1. HBase客户端在数据写入时,首先会写入到WAL(write ahead log)中,将数据以追加的方式写入到WAL文件的尾部。WAL保存在每个RegionServer中,RegionServer使用它来恢复未提交到磁盘的数据
  2. 数据一旦写入到WAL之后,然后会将数据复制到MemStore,MemStore其实就是LSM-Tree中的C0树
  3. 数据被放置到MemStore中之后,客户端接收到确认信息
  4. 当MemStore达到阈值时,它将被转存或提交数据到HFile中

参考资料

【LSM-Tree论文】https://www.cs.umb.edu/~poneil/lsmtree.pdf

https://www.jianshu.com/p/06f9f7f41fdb

文章分享自微信公众号:
大数据技术博文

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!

作者:大数据技术博文
原始发表时间:2022-08-23
如有侵权,请联系 cloudcommunity@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • 学大数据必懂系列之SSTable

    Sorted Strings Table(SSTable)是HBase、 Cassandra等一些NoSQL数据库使用的一种持久文件格式,用于获取存储在memt...

    用户5252199
  • 学大数据必懂系列之SkipList

    通俗解释:SKipList 翻译为中文就是 跳跃表,SkipList是一种数据结构,用于快速的查找数据的位置,本质上了来讲是一个List链表。

    用户5252199
  • 学大数据必懂系列之Page Cache

    通俗解释:在应用程序读取磁盘文件时,操作系统内核在读取磁盘时会经过一层Cache,利用这个Cache可以更快速读取数据(毕竟磁盘速度和内存速度还是差了很多)。那...

    用户5252199
  • 学Java分布式和高架构,必懂的两大知识点!

    美的让人心动
  • MarsTalk | 给老婆讲懂数据库系列之原子性

    刚才是串行执行的场景,没有任何问题,转账B成功,转账A失败,总金额不变(都是900元)。

    HelloMin
  • JavaScript系列之JS数据类型,6大基本数据类型

    点击上方蓝字“ITester软件测试小栈“关注我,每周一、三、五早上 09:00准时推送,每月不定期赠送技术书籍。

    ITester软件测试小栈
  • 3分钟搞定 C++ if else 语句 05

    简介:CSDN博客专家,2020年博客之星TOP5,蓝桥签约作者。15-16年曾在网上直播,带领一批程序小白走上程序员之路。

    1_bit
  • 《看聊天记录都学不会C语言?太菜了吧》(18)2分钟搞结构体

    本系列文章将会以通俗易懂的对话方式进行教学,对话中将涵盖了新手在学习中的一般问题。此系列将会持续更新,包括别的语言以及实战都将使用对话的方式进行教学,基础编程语...

    1_bit
  • @@知乎提问数据分析推荐书籍的统计分析2022.11.21

    用户7138673
  • 《看聊天记录都学不会C语言?太菜了吧》(21)(必懂!题解)在现实生活中,打擂台比赛争名次竟用的是冒泡排序?

    本系列文章将会以通俗易懂的对话方式进行教学,对话中将涵盖了新手在学习中的一般问题。此系列将会持续更新,包括别的语言以及实战都将使用对话的方式进行教学,基础编程语...

    1_bit
  • 《看聊天记录都学不会C语言?太菜了吧》(1)我在大佬群里问基础问题没人理?

    本系列文章将会以通俗易懂的对话方式进行教学,对话中将涵盖了新手在学习中的一般问题。此系列将会持续更新,包括别的语言以及实战都将使用对话的方式进行教学,基础编程语...

    1_bit
  • DB · 洞见#2|基于LSM-Tree存储的数据库性能改进

    为让更多数据库从业者了解数据库领域的最新研究成果,熟悉更多行业前沿发展趋势,腾讯云数据库将举办系列“DB · 洞见”直播活动,打造数据库技术交流平台,邀请学界...

    腾讯云数据库 TencentDB
  • 【数据挖掘】系统地学习数据挖掘

    问题:如何系统地学习数据挖掘? 虽然是本科毕业,但是在看数据挖掘方面的算法理论时经常感觉一些公式的推导过程如天书一般,例如看svm的数学证明,EM算法..,感觉...

    陆勤_数据人网
  • 《看聊天记录都学不会C语言?太菜了吧》(7)下一篇文章告诉你牛郎是谁

    本系列文章将会以通俗易懂的对话方式进行教学,对话中将涵盖了新手在学习中的一般问题。此系列将会持续更新,包括别的语言以及实战都将使用对话的方式进行教学,基础编程语...

    1_bit
  • 《看聊天记录都学不会C语言?太菜了吧》(2)我说编程很容易你们不服?

    本系列文章将会以通俗易懂的对话方式进行教学,对话中将涵盖了新手在学习中的一般问题。此系列将会持续更新,包括别的语言以及实战都将使用对话的方式进行教学,基础编程语...

    1_bit
  • 【必懂C++】第一个程序当然是HelloWorld呀 01

    简介:CSDN博客专家,2020年博客之星TOP5,蓝桥签约作者。15-16年曾在网上直播,带领一批程序小白走上程序员之路。

    1_bit
  • 《看聊天记录都学不会C语言?太菜了吧》(4)零基础的我原来早就学会编程了?

    本系列文章将会以通俗易懂的对话方式进行教学,对话中将涵盖了新手在学习中的一般问题。此系列将会持续更新,包括别的语言以及实战都将使用对话的方式进行教学,基础编程语...

    1_bit
  • 『跟着雨哥学AI』系列之八:趣味案例——有关NLP任务数据预处理的那些事儿

    “跟着雨哥学AI”是百度飞桨开源框架近期针对高层API推出的系列课。本课程由多位资深飞桨工程师精心打造,不仅提供了从数据处理、到模型组网、模型训练、模型评估和推...

    用户1386409
  • 数据存储结构 LSM Tree PK B TREE (从底层了解数据库设计)

    随着使用数据库的深度和理解能力的提升,有一个问题硬件的提升,与数据量的变化是否对数据库底层的架构有冲击。 我们公认的BTREE B+TREE 是否还能面对现在...

    AustinDatabases

扫码关注腾讯云开发者

领取腾讯云代金券