前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >学大数据必懂系列之LSM-Tree

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

作者头像
用户5252199
发布2022-11-22 10:16:58
2.5K0
发布2022-11-22 10:16:58
举报
文章被收录于专栏:大数据技术博文

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 删除

本文分享自 大数据技术博文 微信公众号,前往查看

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

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

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • LSM-Tree 介绍
  • LSM-Tree 设计思想
  • LSM-Tree 合并操作
  • LSM-Tree性能的衡量因素
  • LSM-Tree在HBase中的应用
  • 参考资料
相关产品与服务
TDSQL MySQL 版
TDSQL MySQL 版(TDSQL for MySQL)是腾讯打造的一款分布式数据库产品,具备强一致高可用、全球部署架构、分布式水平扩展、高性能、企业级安全等特性,同时提供智能 DBA、自动化运营、监控告警等配套设施,为客户提供完整的分布式数据库解决方案。
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档