专栏首页码农知识点HBase/TiDB都在用的数据结构:LSM Tree,不得了解一下?

HBase/TiDB都在用的数据结构:LSM Tree,不得了解一下?

LSM Tree(Log-structured merge-tree)广泛应用在HBase,TiDB等诸多数据库和存储引擎上,我们先来看一下它的一些应用:

参考资料【4】

这么牛X的名单,你不想了解下LSM Tree吗?装X之前,我们先来了解一些基本概念。

设计数据存储系统可能需要考虑的一些问题有:ACID,RUM(Read,Write,Memory)。

ACID

ACID 相信小伙伴都被面试官问过,我想简单讨论的一点是:如何 持久化数据 才能保证数据写入的 事务性 和 读写性能?

事务性可简单理解为:1.数据必须持久化。2.一次数据的写入返回给用户 写入成功就一定成功,失败就一定失败。 读写性能可简单理解为:一次读 或 一次写 需要的IO次数,因为访问速率:CPU>>内存>>SSD/磁盘。

对于单机存储,最简单的方式当然是:写一条就持久化一条,读一条就遍历一遍所有数据,然后返回。当然没人这么干,在内存中我们都还知道用个HashMap呢。

拿Mysql InnoDB举例子:读性能体现在数据的索引在磁盘上主要用B+树来保证。写性能体现在运用 WAL机制 来避免每次写都去更新B+树上的全量索引和数据内容,而是通过redo log记录下来每次写的增量内容,顺序将redo log写入磁盘。同时在内存中记录下来本次写入应该在B+树上更新的脏页数据,然后在一定条件下触发脏页的刷盘。

redo log是数据增删改的实时增量数据,顺序写入保证了写性能和事务性。磁盘上的B+树是数据增删改的全量数据,通过定时脏页刷盘保证这份数据的完整性。

这里的问题是:虽然通过WAL机制,提高了写入性能,但是仍然避免不了脏页数据定时刷盘的随机IO写入。因为数据在磁盘上是以block为单位存储的(比如4K,16K),假如你更新了Order表一条数据,又更新了Product表一条数据,脏页刷盘时,这两条数据在磁盘上的block位置可能差了十万八千里,就变成了随机IO的写入。

参考资料【3】

RUM

RUM(Read,Write,Memory)类似分布式领域的CAP定理。如果想得到三者中的两者性能,必须以牺牲第三者的性能为代价。衡量这三者的性能指标有:读放大、写放大、空间放大。

读放大:是指每次查询读取磁盘的次数。如果每次查询需要查询5个page (或block),则读放大是5.

写放大:是指数据写入存储设备的量和数据写入数据库的量之比。如果用户写入数据库的大小是10MB,而实际写入磁盘的大小是30MB,则写放大是3.另外SSD的写入次数是有限的,写放大会减少SSD的寿命。

空间放大:是指数据在存储设备的总量和数据在数据库的总量之比。如果用户往数据库上存10MB,而数据库实际在磁盘上用了100MB去存,则空间放大就是10.

通常,数据结构可以最多优化这其中的两者,如B+树有更少的读放大,LSM Tree有更少的写放大。

下面我们将介绍LSM Tree的结构,它是如何解决 B+树中“全量数据的随机写入” 问题的;在RUM问题上,又该如何优化LSM Tree。

为什么要有LSM Tree

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

如果我们先后修改两条数据,那么在脏数据块落盘时,不是一条条随机写入,而是以一个脏块批量落盘时,就能解决 B+树中“全量数据的随机写入” 问题了。

参考资料【3】

所以大佬设计了这么一种结构:

An LSM-tree of K+1 components

Ck tree是一个有序的树状结构,数据的写入流转从C0 tree 内存开始,不断被合并到磁盘上的更大容量的Ck tree上。这种方式写入是顺序写的,增删改操作都是append。 这样一次I/O可以进行多条数据的写入,从而充分利用每一次写I/O。

merge所做的事情有:当上一棵树容量不足时,1.将上棵树中要删除的数据删除掉,进行GC回收。2.合并数据的最新版本,使得Ck tree不会过度膨胀。

这种初始结构存在的问题有:随着数据量的增大,merge费劲,没有好的索引结构,读放大严重。现代的LSM Tree结构如下:

参考资料【4】

MemTable:是LSM Tree在内存中还未刷盘的写入数据,这里面的数据可以修改。是一个有序的树状结构,如RocksDB中的跳表。

SSTable(Sorted String Table):是一个键是有序的,存储字符串形式键值对的磁盘文件。当SSTable太大时,可以将其划分为多个block;我们需要通过 下图中的Index 记录下来每个block的起始位置,那么就可以构建每个SSTable的稀疏索引。这样在读SSTable前,通过Index结构就知道要读取的数据块磁盘位置了。

LSM Tree读数据

读数据 包括点读和范围读,我们分开讨论。假设LSM Tree中的key为[0-99],

点读:是指准确地取出一条数据,如get(23),则其示意图为:

参考资料【4】

按照图中标示的顺序,会先读取内存,在从Level0依次往高层读取,直到找到key=23的数据。

范围读:是指读取一个范围内的数据,如读取[23-40]内的所有数据( select * from t where key >= 23 && key <=40),

则需要做的是在每一层SSTable找到这个范围内的第一个block,然后遍历block块的数据,直到不符合范围条件。

参考资料【4】

ReadOnly MemTable:如RocksDB,在MemTable 和 Level0数据之间还有一个内存的ReadOnly MemTable结构。它是LSM Tree在内存中还未刷盘的写入数据,这里面的数据不可以修改。是当MemTable到达一定量需要刷到SSTable时,由MemTable完整copy下来的。这样可避免从MemTable直接刷到SSTable时的并发竞争问题。

LSM Tree写数据

在LSM Tree写入数据时,我们把ReadOnly MemTable画上,示意图如下:

当有写请求时,数据会先写入MemTable,同时写入 WAL Log;当MemTable空间不足时,触发ReadOnly MemTable copy,同时写入WAL Log;然后刷新到磁盘Level0的SSTable中。当低层SSTable空间不足时,不断通过Compaction和高层SSTable进行Merge。

LSM Tree合并策略

LSM Tree有两种合并策略,Tiering 和 Leveling。我们看图说话:

Tiering的特点是:每层可能有N个重叠的sorted runs,当上一层的sorted runs 要merge下来时,不会和当前层重叠的sorted runs马上合并,而是等到当前层空间不足时,才会合并,然后再merge到下一层。

Tiering这种策略可以减小写放大,但是以读放大和空间放大为代价。

Leveling的特点是:每层只有一个sorted run,当上一层的sorted run 要merge下来时,会马上和当前层的sorted run合并。

Leveling这种策略可以减小读放大和空间放大,但以写放大为代价。

LSM Tree的优化

参考资料[2-4]中的大佬们提到了不少优化方式,我这里从读,合并方面简要总结下LSM Tree的优化。

点读的优化

尽管我们可以通过SSTable的内存block稀疏索引结构简单判断key是否可能存在于block中,但如上get(23),如果level1读不到,仍需要往下读level2,level3。(因为数据是按照增删改的时间顺序一层层往下落盘的,如果一个key不存在低level中,可能存在于更早的高level中)。这样的点读IO次数较多,读放大严重。

布隆过滤器 对于精确查询,hash的时间复杂度为 O(1),那么可以通过布隆过滤器来优化。我们只需要查询时先过一遍布隆过滤器,就能排除掉一定不存在的key了,避免不必要的IO查询。

布隆过滤器:是通过hash算法来判断一个key是否存在于某个集合中,布隆过滤器通常是一个bit数组,用针对一个key多次hash算法确定的多个bit值来表示key是否存在。多个bit值全为1,则表示key可能存在,否则不存在。好处是多个bit值通常比直接存储一个存在的key占用空间小,省内存。

分层布隆过滤器 上述布隆过滤器是假设每层数据都使用相同的布隆过滤器来进行过滤,而数据随着层数的增加通常是指数级增长的,如果使低层的数据使用更精确的布隆过滤器(所需bit数更多,但是精确度更高),高层的数据使用稍微不那么精确的布隆过滤器,则整体点查的效率将提高。参考资料【3】中Monkey做了上述优化,即使随着数据量和层数的增大,点查仍能保持在一个稳定的时间内。

范围读的优化

Hash的不足就是无法支持范围查询索引,优化方式有: 并行查询 因为读数据不存在竞争问题,可以并行读每层的数据,缩短整体查询时间,但是这种方式实际并没有缩短IO次数。

前缀布隆过滤器 前缀布隆过滤器是以key的前缀来Hash构建布隆过滤器,而不是key本身的值。这样可以起到过滤 like Monica* 这样的查询条件作用。RocksDB有做此优化。

合并的优化

上面提到了两种合并策略Tiering 和 Leveling。Tiering可以减小写放大,Leveling可以减小读放大和空间放大。参考资料【3】中提到了数据库所采用的合并策略走势如下:

随着数据量的增大,整条曲线会上移。优化的重点在于:如何结合两种合并策略,使曲线整体下移。

Lazy Leveling

参考资料【3】中Dostoevsky采用了一种Lazy Leveling的策略:它是对低层数据采用Tiering合并策略,对高层数据采用Leveling合并策略。从而权衡了读写性能。

RUM的取舍

RUM的取舍和权衡类似于分布式领域的CAP,在特定的场景采用适合的优化手段才能使整体性能最优。参考资料【3】中的大佬还提到了Fluid Merge策略。233酱表示虽过了眼瘾,但仍是个CRUD渣渣。

关于RUM的优化,233酱最后放一张图,希望对你我有所启发。


后记

LSM Tree是这两年一直听到的名词,但是一直没有花时间搞懂它。233酱趁这次机会现学现卖,对其有了更深一步的了解。

对本文内容感兴趣的小伙伴可进一步阅读参考资料,如果文中有错误或者不理解的地方也欢迎小伙伴们和我交流指正。

参考资料: [1].https://kernelmaker.github.io/lsm-tree [2].https://www.youtube.com/watch?v=aKAJMd0iKtI [3].https://www.youtube.com/watch?v=b6SI8VbcT4w [4].https://www.bilibili.com/video/BV1fb411x7zz?from=search&seid=8679886514280300283 [5].https://tikv.github.io/deep-dive-tikv/key-value-engine/B-Tree-vs-Log-Structured-Merge-Tree.html

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【大数据哔哔集20210112】Sorry,Hbase的LSM Tree真的可以为所欲为!

    LSM树是HBase里使用的非常有创意的一种数据结构。在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我...

    大数据真好玩
  • TiDB测试小结

    首先对我来说,我觉得能够开发数据库,而且能够有很深的技术情结,真是一件很cool的事情,我比较欣赏极客精神,同时满足了业务,也在技术上的价值得以体现,这种模式值...

    jeanron100
  • 深入理解什么是LSM-Tree

    十多年前,谷歌发布了大名鼎鼎的"三驾马车"的论文,分别是GFS(2003年),MapReduce(2004年),BigTable(2006年),为开源界在大数据...

    我是攻城师
  • 原创分享 TiDB 的列式存储引擎是如何实现的?

    TiDB 是一款分布式 HTAP 数据库,它目前有两种存储节点,分别是 TiKV 和 TiFlash。TiKV 采用了行式存储,更适合 TP 类型的业务;而 T...

    PingCAP
  • 从B+树到LSM树,及LSM树在HBase中的应用

    在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据...

    Spark学习技巧
  • Druid架构设计思想详解

    对于目前大多数Druid 的使用场景来说,Druid 本质上是一个分布式的时序数据库,而对于一个数据库的性能来说,其数据的组织方式至关重要。为了更好地阐述Dru...

    博文视点Broadview
  • 写给社区的回顾和展望:TiDB 2019, Level Up !

    同时在技术上,2018 年我觉得也交出了一份令人满意的答卷,TiDB 的几个主要项目今年一共合并了 4380 个提交,这几天在整理 2018 年的 Change...

    PingCAP
  • 分布式数据库的几个事实

    Oracle 12C正式发布前,我曾经参加过一个中国企业用户与Oracle研发副总裁的圆桌会议,主要是提出国内企业级用户对Oracle数据库的一些需求,供Ora...

    jeanron100
  • Hbase 和 MySQL 的区别是什么?一文深度对比!

    来源:blog.csdn.net/weixin_41605937/ article/details/110933984

    芋道源码
  • Hbase和MySQL的区别是什么?一文深度对比!

    MySQL + HBase是我们日常应用中常用的两个数据库,分别解决应用的在线事务问题和大数据场景的海量存储问题。

    架构师修炼
  • 十问 TiDB :关于架构设计的一些思考

    做 TiDB 的缘起是从思考一个问题开始的:为什么在数据库领域有这么多永远也躲不开的坑?从 2015 年我们写下第一行代码,3 年以来我们迎面遇到无数个问题,一...

    PingCAP
  • 苹果公司开源FoundationDB的简单分析

    美国时间 2018年4月19日,苹果公司宣布开源FoundationDB。FoundationDB 本来是一个开源项目,于2015年被苹果收购以后,其代码从Gi...

    用户1564362
  • 掌握了LSM架构,你就掌握了90%的分布式数据库

    很多的数据库现在都在使用LSM tree作为其核心结构,因为它可以提供非常高的写入吞吐量。一些分布式数据库比如Bigtable、HBase、LevelDB、SQ...

    ImportSource
  • 概要介绍LSM树

    这张经典图片来自 Flink PMC 的 Stefan Richter 在Flink Forward 2018演讲的PPT

    十毛
  • LSM设计一个数据库引擎

    以 Mysql、postgresql 为代表的传统 RDBMS 都是基于 b-tree 的 page-orented 存储引擎。现代计算机的最大处理瓶颈在磁盘的...

    码哥字节
  • LevelDB 完全解析(0):基本原理和整体架构

    之前零零散散写过几篇和 LSM-Tree、LevelDB 有关的文章。之后也看了一些代码和论文,笔记也做了一些,但大都比较零乱、随意,没花功夫整理。

    linjinhe
  • 简讲LSM树(Log-Structured Merge Tree)

    前言:最近在了解大数据实时分析技术druid,究其原理时发现用到了类LSM树思想以实现高效的数据插入,于是展开了对LSM的了解,了解之后感觉这东西虽然也并没有很...

    杨松青
  • 十分钟看懂时序数据库(I)-存储

    2017年时序数据库忽然火了起来。开年2月Facebook开源了beringei时序数据库;到了4月基于PostgreSQL打造的时序数据库TimeScaleD...

    小小科
  • 千亿级服务器监控数据存储实践

    公司目前有几十万台左右服务器,TMP(腾讯监控平台)平均每天采集1200亿+监控数据,本文将从当前存储架构存在的问题出发,介绍使用大数据平台组件 Hbase 存...

    jackiefang

扫码关注云+社区

领取腾讯云代金券