精华内容
下载资源
问答
  • LSM树

    万次阅读 多人点赞 2019-06-26 19:14:08
    关于LSM树 LSM树,即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构,它更多是一种数据结构的设计思想。大多NoSQL数据库核心思想都是基于LSM来做的,只是具体的实现不同。所以本来...

    关于LSM树

    LSM树,即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构,它更多是一种数据结构的设计思想。大多NoSQL数据库核心思想都是基于LSM来做的,只是具体的实现不同。所以本来不打算列入该系列,但是有朋友留言了好几次让我讲LSM树,那么就说一下LSM树。

    LSM树诞生背景

    传统关系型数据库使用btree或一些变体作为存储结构,能高效进行查找。但保存在磁盘中时它也有一个明显的缺陷,那就是逻辑上相离很近但物理却可能相隔很远,这就可能造成大量的磁盘随机读写。随机读写比顺序读写慢很多,为了提升IO性能,我们需要一种能将随机操作变为顺序操作的机制,于是便有了LSM树。LSM树能让我们进行顺序写磁盘,从而大幅提升写操作,作为代价的是牺牲了一些读性能。

    关于磁盘IO

    磁盘读写时涉及到磁盘上数据查找,地址一般由柱面号、盘面号和块号三者构成。也就是说移动臂先根据柱面号移动到指定柱面,然后根据盘面号确定盘面的磁道,最后根据块号将指定的磁道段移动到磁头下,便可开始读写。

    整个过程主要有三部分时间消耗,查找时间(seek time) +等待时间(latency time)+传输时间(transmission time) 。分别表示定位柱面的耗时、将块号指定磁道段移到磁头的耗时、将数据传到内存的耗时。整个磁盘IO最耗时的地方在查找时间,所以减少查找时间能大幅提升性能。

    LSM树原理

    LSM树由两个或以上的存储结构组成,比如在论文中为了方便说明使用了最简单的两个存储结构。一个存储结构常驻内存中,称为C0 tree,具体可以是任何方便健值查找的数据结构,比如红黑树、map之类,甚至可以是跳表。另外一个存储结构常驻在硬盘中,称为C1 tree,具体结构类似B树。C1所有节点都是100%满的,节点的大小为磁盘块大小。

    插入步骤

    大体思路是:插入一条新纪录时,首先在日志文件中插入操作日志,以便后面恢复使用,日志是以append形式插入,所以速度非常快;将新纪录的索引插入到C0中,这里在内存中完成,不涉及磁盘IO操作;当C0大小达到某一阈值时或者每隔一段时间,将C0中记录滚动合并到磁盘C1中;对于多个存储结构的情况,当C1体量越来越大就向C2合并,以此类推,一直往上合并Ck。

    合并步骤

    合并过程中会使用两个块:emptying block和filling block。

     

    从C1中读取未合并叶子节点,放置内存中的emptying block中。从小到大找C0中的节点,与emptying block进行合并排序,合并结果保存到filling block中,并将C0对应的节点删除。不断执行第2步操作,合并排序结果不断填入filling block中,当其满了则将其追加到磁盘的新位置上,注意是追加而不是改变原来的节点。合并期间如故宫emptying block使用完了则再从C1中读取未合并的叶子节点。C0和C1所有叶子节点都按以上合并完成后即完成一次合并。

    关于优化措施

    本文用图阐述LSM的基本原理,但实际项目中其实有很多优化策略,而且有很多针对LSM树优化的paper。比如使用布隆过滤器快速判断key是否存在,还有做一些额外的索引以帮助更快找到记录等等。

    插入操作

    向LSM树中插入

    A E L R U

    ,首先会插入到内存中的C0树上,这里使用AVL树,插入“A”,先向磁盘日志文件追加记录,然后再插入C0,

    插入“E”,同样先追加日志再写内存,

    继续插入“L”,旋转后如下,

    插入“R”“U”,旋转后最终如下。

    假设此时触发合并,则因为C1还没有树,所以emptying block为空,直接从C0树中依次找最小的节点。filling block长度为4,这里假设磁盘块大小为4。

    开始找最小的节点,并放到filling block中,

    继续找第二个节点,

    以此类推,填满filling block,

    开始写入磁盘,C1树,

    继续插入

    B F N T

    ,先分别写日志,然后插入到内存的C0树中,

    假如此时进行合并,先加载C1的最左边叶子节点到emptying block,

    接着对C0树的节点和emptying block进行合并排序,首先是“A”进入filling block,

    然后是“B”,

    合并排序最终结果为,

    将filling block追加到磁盘的新位置,将原来的节点删除掉,

    继续合并排序,再次填满filling block,

    将filling block追加到磁盘的新位置,上一层的节点也要以磁盘块(或多个磁盘块)大小写入,尽量避开随机写。另外由于合并过程可能会导致上层节点的更新,可以暂时保存在内存,后面在适当时机写入。

    查找操作

    查找总体思想是先找内存的C0树,找不到则找磁盘的C1树,然后是C2树,以此类推。

    假如要找“B”,先找C0树,没找到。

    接着找C1树,从根节点开始,

    找到“B”。

    删除操作

    删除操作为了能快速执行,主要是通过标记来实现,在内存中将要删除的记录标记一下,后面异步执行合并时将相应记录删除。

    比如要删除“U”,假设标为#的表示删除,则C0树的“U”节点变为,

    而如果C0树不存在的记录,则在C0树中生成一个节点,并标为#,查找时就能在内存中得知该记录已被删除,无需去磁盘找了。比如要删除“B”,那么没有必要去磁盘执行删除操作,直接在C0树中插入一个“B”节点,并标为#。

     

    假如对写操作的吞吐量比较敏感,可采用日志策略(顺序读写,只追加不修改)来提升写性能。存在问题:数据查找需要倒序扫描,花费很多时间。比如,预写日志WAL,WAL的中心概念是数据文件(存储着表和索引)的修改必须在这些动作被日志记录之后才被写入,即在描述这些改变的日志记录被刷到持久存储以后。如果我们遵循这种过程,我们不需要在每个事务提交时刷写数据页面到磁盘,因为我们知道在发生崩溃时可以使用日志来恢复数据库:任何还没有被应用到数据页面的改变可以根据其日志记录重做(这是前滚恢复,也被称为REDO)。使用WAL可以显著降低磁盘的写次数,因为只有日志文件需要被刷出到磁盘以保证事务被提交,而被事务改变的每一个数据文件则不必被刷出。

    其只是提高了写的性能,对于更为复杂的读性能,需要寻找其他的方法,其中有四种方法来提升读性能

    • 二分查找: 将文件数据有序保存,使用二分查找来完成特定key的查找。

    • 哈希:用哈希将数据分割为不同的bucket

    • B+树:使用B+树 或者 ISAM 等方法,可以减少外部文件的读取

    • 外部文件: 将数据保存为日志,并创建一个hash或者查找树映射相应的文件。

    所有的四种方法都可以有效的提高了读操作的性能(最少提供了O(log(n)) ),但是,却丢失了日志文件超好的写性能,上面这些方法,都强加了总体的结构信息在数据上,数据被按照特定的方式放置,所以可以很快的找到特定的数据,但是却对写操作不友善,让写操作性能下降。更糟糕的是,当需要更新hash或者B+树的结构时,需要同时更新文件系统中特定的部分,这就是造成了比较慢的随机读写操作,这种随机的操作要尽量减少。

    既要保证日志文件好的写性能,又要在一定程度上保证读性能,所以LSM-Tree应运而生。

    下面块为引用https://www.cnblogs.com/yanghuahui/p/3483754.html,进行对比

    讲LSM树之前,需要提下三种基本的存储引擎,这样才能清楚LSM树的由来:

    1. 哈希存储引擎  是哈希表的持久化实现,支持增、删、改以及随机读取操作,但不支持顺序扫描,对应的存储系统为key-value存储系统。对于key-value的插入以及查询,哈希表的复杂度都是O(1),明显比树的操作O(n)快,如果不需要有序的遍历数据,哈希表就是your Mr.Right
    2. B树存储引擎是B树(关于B树的由来,数据结构以及应用场景可以看之前一篇博文)的持久化实现,不仅支持单条记录的增、删、读、改操作,还支持顺序扫描(B+树的叶子节点之间的指针),对应的存储系统就是关系数据库(Mysql等)。
    3. LSM树(Log-Structured Merge Tree)存储引擎和B树存储引擎一样,同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。当然凡事有利有弊,LSM树和B+树相比,LSM树牺牲了部分读性能,用来大幅提高写性能。

    LSM树(Log Structured Merge Tree,结构化合并树)的思想非常朴素,就是将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘(由此提升了写性能),是一种基于硬盘的数据结构,与B-tree相比,能显著地减少硬盘磁盘臂的开销。当然凡事有利有弊,LSM树和B+树相比,LSM树牺牲了部分读性能,用来大幅提高写性能。

    读取时需要合并磁盘中的历史数据和内存中最近的修改操作,读取时可能需要先看是否命中内存,否则需要访问较多的磁盘文件(存储在磁盘中的是许多小批量数据,由此降低了部分读性能。但是磁盘中会定期做merge操作,合并成一棵大树,以优化读性能)。LSM树的优势在于有效地规避了磁盘随机写入问题,但读取时可能需要访问较多的磁盘文件。

    代表数据库:nessDB、leveldb、hbase等

    核心思想的核心就是放弃部分读能力,换取写入的最大化能力,放弃磁盘读性能来换取写的顺序性。极端的说,基于LSM树实现的HBase的写性能比Mysql高了一个数量级,读性能低了一个数量级。

    LSM操作

    LSM树 插入数据可以看作是一个N阶合并树。数据写操作(包括插入、修改、删除也是写)都在内存中进行,

    数据首先会插入内存中的树。当内存树的数据量超过设定阈值后,会进行合并操作。合并操作会从左至右便利内存中树的子节点 与 磁盘中树的子节点并进行合并,会用最新更新的数据覆盖旧的数据(或者记录为不同版本)。当被合并合并数据量达到磁盘的存储页大小时。会将合并后的数据持久化到磁盘,同时更新父节点对子节点的指针。

    LSM树 读数据 磁盘中书的非子节点数据也被缓存到内存中。在需要进行读操作时,总是从内存中的排序树开始搜索,如果没有找到,就从磁盘上的排序树顺序查找。

    在LSM树上进行一次数据更新不需要磁盘访问,在内存即可完成,速度远快于B+树。当数据访问以写操作为主,而读操作则集中在最近写入的数据上时,使用LSM树可以极大程度地减少磁盘的访问次数,加快访问速度。

    LSM树 删除数据 前面讲了。LSM树所有操作都是在内存中进行的,那么删除并不是物理删除。而是一个逻辑删除,会在被删除的数据上打上一个标签,当内存中的数据达到阈值的时候,会与内存中的其他数据一起顺序写入磁盘。 这种操作会占用一定空间,但是LSM-Tree 提供了一些机制回收这些空间。


    转载参考:https://baijiahao.baidu.com/s?id=1613810327967900833&wfr=spider&for=pc

                      https://blog.csdn.net/qq_28328381/article/details/81280197

    展开全文
  • 关于LSM树

    2020-07-09 09:37:30
    前言 推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。...所以本来不打算列入该系列,但是有朋友留言了好几次让我讲LSM树,那么就说一下L

    前言

    推出一个新系列,《看图轻松理解数据结构和算法》,主要使用图片来描述常见的数据结构和算法,轻松阅读并理解掌握。本系列包括各种堆、各种队列、各种列表、各种树、各种图、各种排序等等几十篇的样子。

    关于LSM树

    LSM树,即日志结构合并树(Log-Structured Merge-Tree)。其实它并不属于一个具体的数据结构,它更多是一种数据结构的设计思想。大多NoSQL数据库核心思想都是基于LSM来做的,只是具体的实现不同。所以本来不打算列入该系列,但是有朋友留言了好几次让我讲LSM树,那么就说一下LSM树。

    LSM树诞生背景

    传统关系型数据库使用btree或一些变体作为存储结构,能高效进行查找。但保存在磁盘中时它也有一个明显的缺陷,那就是逻辑上相离很近但物理却可能相隔很远,这就可能造成大量的磁盘随机读写。随机读写比顺序读写慢很多,为了提升IO性能,我们需要一种能将随机操作变为顺序操作的机制,于是便有了LSM树。LSM树能让我们进行顺序写磁盘,从而大幅提升写操作,作为代价的是牺牲了一些读性能。

    关于磁盘IO

    磁盘读写时涉及到磁盘上数据查找,地址一般由柱面号、盘面号和块号三者构成。也就是说移动臂先根据柱面号移动到指定柱面,然后根据盘面号确定盘面的磁道,最后根据块号将指定的磁道段移动到磁头下,便可开始读写。

    整个过程主要有三部分时间消耗,查找时间(seek time) +等待时间(latency time)+传输时间(transmission time) 。分别表示定位柱面的耗时、将块号指定磁道段移到磁头的耗时、将数据传到内存的耗时。整个磁盘IO最耗时的地方在查找时间,所以减少查找时间能大幅提升性能。

    LSM树原理

    LSM树由两个或以上的存储结构组成,比如在论文中为了方便说明使用了最简单的两个存储结构。一个存储结构常驻内存中,称为C0 tree,具体可以是任何方便健值查找的数据结构,比如红黑树、map之类,甚至可以是跳表。另外一个存储结构常驻在硬盘中,称为C1 tree,具体结构类似B树。C1所有节点都是100%满的,节点的大小为磁盘块大小。

     

    image

     

     

    插入步骤

    大体思路是:插入一条新纪录时,首先在日志文件中插入操作日志,以便后面恢复使用,日志是以append形式插入,所以速度非常快;将新纪录的索引插入到C0中,这里在内存中完成,不涉及磁盘IO操作;当C0大小达到某一阈值时或者每隔一段时间,将C0中记录滚动合并到磁盘C1中;对于多个存储结构的情况,当C1体量越来越大就向C2合并,以此类推,一直往上合并Ck。

     

    image

     

     

    合并步骤

    合并过程中会使用两个块:emptying block和filling block。

    1. 从C1中读取未合并叶子节点,放置内存中的emptying block中。
    2. 从小到大找C0中的节点,与emptying block进行合并排序,合并结果保存到filling block中,并将C0对应的节点删除。
    3. 不断执行第2步操作,合并排序结果不断填入filling block中,当其满了则将其追加到磁盘的新位置上,注意是追加而不是改变原来的节点。合并期间如故宫emptying block使用完了则再从C1中读取未合并的叶子节点。
    4. C0和C1所有叶子节点都按以上合并完成后即完成一次合并。

    关于优化措施

    本文用图阐述LSM的基本原理,但实际项目中其实有很多优化策略,而且有很多针对LSM树优化的paper。比如使用布隆过滤器快速判断key是否存在,还有做一些额外的索引以帮助更快找到记录等等。

    插入操作

    向LSM树中插入A E L R U,首先会插入到内存中的C0树上,这里使用AVL树,插入“A”,先项磁盘日志文件追加记录,然后再插入C0,

     

    image

     

     

    插入“E”,同样先追加日志再写内存,

     

    image

     

     

    继续插入“L”,旋转后如下,

     

    image

     

     

    插入“R”“U”,旋转后最终如下。

     

    image

     

     

    假设此时触发合并,则因为C1还没有树,所以emptying block为空,直接从C0树中依次找最小的节点。filling block长度为4,这里假设磁盘块大小为4。

    开始找最小的节点,并放到filling block中,

     

    image

     

     

    继续找第二个节点,

     

    image

     

     

    以此类推,填满filling block,

     

    image

     

     

    开始写入磁盘,C1树,

     

    image

     

     

    继续插入B F N T,先分别写日志,然后插入到内存的C0树中,

     

    image

     

     

    假如此时进行合并,先加载C1的最左边叶子节点到emptying block,

     

    image

     

     

    接着对C0树的节点和emptying block进行合并排序,首先是“A”进入filling block,

     

    image

     

     

    然后是“B”,

     

    image

     

     

    合并排序最终结果为,

     

    image

     

     

    将filling block追加到磁盘的新位置,将原来的节点删除掉,

     

    image

     

     

    继续合并排序,再次填满filling block,

     

    image

     

     

    将filling block追加到磁盘的新位置,上一层的节点也要以磁盘块(或多个磁盘块)大小写入,尽量避开随机写。另外由于合并过程可能会导致上层节点的更新,可以暂时保存在内存,后面在适当时机写入。

     

    image

     

     

    查找操作

    查找总体思想是先找内存的C0树,找不到则找磁盘的C1树,然后是C2树,以此类推。

    假如要找“B”,先找C0树,没找到。

     

    image

     

     

    接着找C1树,从根节点开始,

     

    image

     

     

    找到“B”。

     

    image

     

     

    删除操作

    删除操作为了能快速执行,主要是通过标记来实现,在内存中将要删除的记录标记一下,后面异步执行合并时将相应记录删除。

    比如要删除“U”,假设标为#的表示删除,则C0树的“U”节点变为,

     

    image

     

     

    而如果C0树不存在的记录,则在C0树中生成一个节点,并标为#,查找时就能再内存中得知该记录已被删除,无需去磁盘找了。比如要删除“B”,那么没有必要去磁盘执行删除操作,直接在C0树中插入一个“B”节点,并标为#。

     

    image

     

     

    -------------推荐阅读------------

    我的开源项目汇总(机器&深度学习、NLP、网络IO、AIML、mysql协议、chatbot)

    为什么写《Tomcat内核设计剖析》

    我的2017文章汇总——机器学习篇

    我的2017文章汇总——Java及中间件

    我的2017文章汇总——深度学习篇

    我的2017文章汇总——JDK源码篇

    我的2017文章汇总——自然语言处理篇

    我的2017文章汇总——Java并发篇


    跟我交流,向我提问:

     

     

     

    欢迎关注:

     


    作者:超人汪小建
    链接:https://juejin.im/post/5bbbf7615188255c59672125
    来源:掘金
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

    展开全文
  • LSM树详解

    2021-01-07 21:23:24
    LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象,事实上,LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构,它其实是一种存储结构,目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的...

    LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象,事实上,LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构,它其实是一种存储结构,目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的LSM树。

    LSM树的核心特点是利用顺序写来提高写性能,但因为分层(此处分层是指的分为内存和文件两部分)的设计会稍微降低读性能,但是通过牺牲小部分读性能换来高性能写,使得LSM树成为非常流行的存储结构。

    1、LSM树的核心思想

    如上图所示,LSM树有以下三个重要组成部分:

    1) MemTable

    MemTable是在内存中的数据结构,用于保存最近更新的数据,会按照Key有序地组织这些数据,LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义,例如Hbase使跳跃表来保证内存中key的有序。

    因为数据暂时保存在内存中,内存并不是可靠存储,如果断电会丢失数据,因此通常会通过WAL(Write-ahead logging,预写式日志)的方式来保证数据的可靠性。

    2) Immutable MemTable

    当 MemTable达到一定大小后,会转化成Immutable MemTable。Immutable MemTable是将转MemTable变为SSTable的一种中间状态。写操作由新的MemTable处理,在转存过程中不阻塞数据更新操作。

    3) SSTable(Sorted String Table)

    有序键值对集合,是LSM树组在磁盘中的数据结构。为了加快SSTable的读取,可以通过建立key的索引以及布隆过滤器来加快key的查找。

    这里需要关注一个重点,LSM树(Log-Structured-Merge-Tree)正如它的名字一样,LSM树会将所有的数据插入、修改、删除等操作记录(注意是操作记录)保存在内存之中,当此类操作达到一定的数据量后,再批量地顺序写入到磁盘当中。这与B+树不同,B+树数据的更新会直接在原数据所在处修改对应的值,但是LSM数的数据更新是日志式的,当一条数据更新是直接append一条更新记录完成的。这样设计的目的就是为了顺序写,不断地将Immutable MemTable flush到持久化存储即可,而不用去修改之前的SSTable中的key,保证了顺序写。

    因此当MemTable达到一定大小flush到持久化存储变成SSTable后,在不同的SSTable中,可能存在相同Key的记录,当然最新的那条记录才是准确的。这样设计的虽然大大提高了写性能,但同时也会带来一些问题:

    1)冗余存储,对于某个key,实际上除了最新的那条记录外,其他的记录都是冗余无用的,但是仍然占用了存储空间。因此需要进行Compact操作(合并多个SSTable)来清除冗余的记录。
    2)读取时需要从最新的倒着查询,直到找到某个key的记录。最坏情况需要查询完所有的SSTable,这里可以通过前面提到的索引/布隆过滤器来优化查找速度。

    2、LSM树的Compact策略

    从上面可以看出,Compact操作是十分关键的操作,否则SSTable数量会不断膨胀。在Compact策略上,主要介绍两种基本策略:size-tiered和leveled。

    不过在介绍这两种策略之前,先介绍三个比较重要的概念,事实上不同的策略就是围绕这三个概念之间做出权衡和取舍。

    1)读放大:读取数据时实际读取的数据量大于真正的数据量。例如在LSM树中需要先在MemTable查看当前key是否存在,不存在继续从SSTable中寻找。
    2)写放大:写入数据时实际写入的数据量大于真正的数据量。例如在LSM树中写入时可能触发Compact操作,导致实际写入的数据量远大于该key的数据量。
    3)空间放大:数据实际占用的磁盘空间比数据的真正大小更多。上面提到的冗余存储,对于一个key来说,只有最新的那条记录是有效的,而之前的记录都是可以被清理回收的。

    1) size-tiered 策略

    size-tiered策略保证每层SSTable的大小相近,同时限制每一层SSTable的数量。如上图,每层限制SSTable为N,当每层SSTable达到N后,则触发Compact操作合并这些SSTable,并将合并后的结果写入到下一层成为一个更大的sstable。

    由此可以看出,当层数达到一定数量时,最底层的单个SSTable的大小会变得非常大。并且size-tiered策略会导致空间放大比较严重。即使对于同一层的SSTable,每个key的记录是可能存在多份的,只有当该层的SSTable执行compact操作才会消除这些key的冗余记录。

    2) leveled策略

    每一层的总大小固定,从上到下逐渐变大

    leveled策略也是采用分层的思想,每一层限制总文件的大小。

    但是跟size-tiered策略不同的是,leveled会将每一层切分成多个大小相近的SSTable。这些SSTable是这一层是全局有序的,意味着一个key在每一层至多只有1条记录,不存在冗余记录。之所以可以保证全局有序,是因为合并策略和size-tiered不同,接下来会详细提到。

    每一层的SSTable是全局有序的

    假设存在以下这样的场景:

    1) L1的总大小超过L1本身大小限制:

    此时L1超过了最大阈值限制

    2) 此时会从L1中选择至少一个文件,然后把它跟L2有交集的部分(非常关键)进行合并。生成的文件会放在L2:

    如上图所示,此时L1第二SSTable的key的范围覆盖了L2中前三个SSTable,那么就需要将L1中第二个SSTable与L2中前三个SSTable执行Compact操作。

    3) 如果L2合并后的结果仍旧超出L5的阈值大小,需要重复之前的操作 —— 选至少一个文件然后把它合并到下一层:

    需要注意的是,多个不相干的合并是可以并发进行的

    leveled策略相较于size-tiered策略来说,每层内key是不会重复的,即使是最坏的情况,除开最底层外,其余层都是重复key,按照相邻层大小比例为10来算,冗余占比也很小。因此空间放大问题得到缓解。但是写放大问题会更加突出。举一个最坏场景,如果LevelN层某个SSTable的key的范围跨度非常大,覆盖了LevelN+1层所有key的范围,那么进行Compact时将涉及LevelN+1层的全部数据。

    3、总结

    LSM树是非常值得了解的知识,理解了LSM树可以很自然地理解Hbase,LevelDb等存储组件的架构设计。ClickHouse中的MergeTree也是LSM树的思想,Log-Structured还可以联想到Kafka的存储方式。

    虽然介绍了上面两种策略,但是各个存储都在自己的Compact策略上面做了很多特定的优化,例如Hbase分为Major和Minor两种Compact,这里不再做过多介绍,推荐阅读文末的RocksDb合并策略介绍。

    参考来源:

    https://rocksdb.org.cn/doc/Leveled-Compaction.html

    https://www.jianshu.com/p/e89cd503c9ae?utm_campaign=hugo

    展开全文
  • lsmt:LSM树-源码

    2021-02-21 04:20:34
    LSM树 KV商店
  • 前言 在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、...本文先由B+树来引出对LSM树的介绍,然后...
        

    前言

    在有代表性的关系型数据库如MySQL、SQL Server、Oracle中,数据存储与索引的基本结构就是我们耳熟能详的B树和B+树。而在一些主流的NoSQL数据库如HBase、Cassandra、LevelDB、RocksDB中,则是使用日志结构合并树(Log-structured Merge Tree,LSM Tree)来组织数据。本文先由B+树来引出对LSM树的介绍,然后说明HBase中是如何运用LSM树的。

    回顾B+树

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

    195230-ed55a712b3183c67.png

    与普通B树相比,B+树的非叶子节点只有索引,所有数据都位于叶子节点,并且叶子节点上的数据会形成有序链表。B+树的主要优点如下:

    • 结构比较扁平,高度低(一般不超过4层),随机寻道次数少;
    • 数据存储密度大,且都位于叶子节点,查询稳定,遍历方便;
    • 叶子节点形成有序链表,范围查询转化为顺序读,效率高。相对而言B树必须通过中序遍历才能支持范围查询。

    当然,B+树也不是十全十美的,它的主要缺点有两个:

    • 如果写入的数据比较离散,那么寻找写入位置时,子节点有很大可能性不会在内存中,最终会产生大量的随机写,性能下降。下图来自TokuDB的PPT,说明了这一点。
    195230-1e6b4d3738538331.png
    • 如果B+树已经运行了很长时间,写入了很多数据,随着叶子节点分裂,其对应的块会不再顺序存储,而变得分散。这时执行范围查询也会变成随机读,效率降低了。
    195230-9d7e6f7e6d78297a.png

    可见,B+树在多读少写(相对而言)的情境下比较有优势,在多写少读的情境下就不是很有威力了。当然,我们可以用SSD来获得成倍提升的读写速率,但成本同样高昂,对海量存储集群而言不太可行。日志结构合并树(LSM Tree)就是作为B+树的替代方案产生的。

    认识LSM树

    LSM树由Patrick O'Neil等人在论文《The Log-Structured Merge Tree》中提出,它实际上不是一棵树,而是2个或者多个树或类似树的结构(注意这点)的集合。下图示出最简单的有2个结构的LSM树。

    195230-f58bf94c28336ce4.png
    论文中的图,不知为何少了一个字母D

    在LSM树中,最低一级也是最小的C0树位于内存里,而更高级的C1、C2...树都位于磁盘里。数据会先写入内存中的C0树,当它的大小达到一定阈值之后,C0树中的全部或部分数据就会刷入磁盘中的C1树,如下图所示。

    195230-c833dee328972ea4.png

    由于内存的读写速率都比外存要快非常多,因此数据写入C0树的效率很高。并且数据从内存刷入磁盘时是预排序的,也就是说,LSM树将原本的随机写操作转化成了顺序写操作,写性能大幅提升。不过,它的tradeoff就是牺牲了一部分读性能,因为读取时需要将内存中的数据和磁盘中的数据合并。总体上来讲这种tradeoff还是值得的,因为:

    • 可以先读取内存中C0树的缓存数据。内存的效率很高,并且根据局部性原理,最近写入的数据命中率也高。
    • 写入数据未刷到磁盘时不会占用磁盘的I/O,不会与读取竞争。读取操作就能取得更长的磁盘时间,变相地弥补了读性能差距。

    在实际应用中,为了防止内存因断电等原因丢失数据,写入内存的数据同时会顺序在磁盘上写日志,类似于我们常见的预写日志(WAL),这就是LSM这个词中Log一词的来历。另外,如果有多级树的话,低级的树在达到大小阈值后也会在磁盘中进行合并,如下图所示。

    195230-c887520262baf90a.png
    195230-0ee37f170c29523a.png

    下面以HBase为例来简要讲解LSM树是如何发挥其作用的。

    HBase中的LSM树

    在之前的《HBase MemStore 101》这篇文章中,我们已经了解了HBase的读写流程与MemStore的作用。MemStore作为列族级别的写入和读取缓存,它就是HBase中LSM树的C0层。并且它确实也没有采用树形结构来存储,而是采用了跳表——一种替代自平衡BST的结构,详情参见我之前写的《跳跃列表与其在Redis中的实现详解》。MemStore Flush的过程,也就是LSM树中C0层刷写到C1层的过程,而LSM中的日志对应到HBase自然就是HLog了。

    为了方便理解,再次祭出之前用过的HBase读写流程简图。

    195230-708e1899d7e003e3.png

    HFile就是LSM树中的高层实现。从逻辑上来讲,它是一棵满的3层B+树,从上到下的3层索引分别是Root index block、Intermediate index block和Leaf index block,对应到下面的Data block就是HFile的KeyValue结构了。HFile V2索引结构的图示如下,来自hbasefly的文章

    195230-60b488e7cddda9ac.png

    我们已经知道,HFile过多会影响读写性能,因此高层LSM树的合并即对应HFile的合并(Compaction)操作。合并操作又分别Minor和Major Compaction,由于Major Compaction涉及整个Region,对磁盘压力很大,因此要尽量避免。

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

    195230-9a64cd3804c289ad.png

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

    The End

    明天又要开始搬砖,晚安吧各位~

    展开全文
  • LSM树数据结构介绍

    2021-07-17 12:46:14
    LSM树(Log-Structured-Merge-Tree)的名字往往会给初识者一个错误的印象,事实上,LSM树并不像B+树、红黑树一样是一颗严格的树状数据结构,它其实是一种存储结构,目前HBase,LevelDB,RocksDB这些NoSQL存储都是采用的...
  • LSM树学习

    千次阅读 2018-11-02 21:28:52
    LSM树存储模型 关于Mem Table、Immutable Mem Table和SSTable等概念见博客: https://blog.csdn.net/qq910894904/article/details/38014127 LSM的基本思想是将修改的数据保存在内存,达到一定数量后在将修改的...
  • B+树 VS LSM树

    2021-06-09 09:11:30
    目录B+树LSM树比较总结 B+树 简介:为了改善数据访问特性,文件系统或数据库系统通常会对数据排序后存储,加快数据检索速度。传统关系数据库的做法是使用B+树,保证数据在不断更新、插入、删除后依然有序。B+树结构...
  • LSM树的学习总结

    2020-07-28 10:06:44
    LSM树的学习总结-简明-更新中...LSM树的概念LSM树的原理LSM的写入流程如下LSM树的使用LSM树和B树、B+树的区别B树的写入过程 LSM树的概念 英文全名 The Log structured Merage - Tree LSM树的原理 基础原理1:内存...
  • LSM树原理探究

    2020-03-19 11:06:36
    B+树随着mysql Innodb引擎的广泛推广越来越被大家所熟知,而前不久我在研究Raft算法时,偶然发现了一种和B+树类似的数据结构——LSM树(Log-Structured-Merge-Tree 日志结构合并树),它是Google发表的论文Big Table...
  • LSM树存储引擎

    千次阅读 2016-03-27 14:33:40
    2.2.3 LSM树存储引擎 LSM树(Log Structured Merge Tree)的思想非常朴素,就是将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘,读取时需要合并磁盘中的历史数据和内存中最近...
  • LSM树(日志结构合并树)总结-java版

    千次阅读 2019-05-16 11:45:01
    为什么要有LSM树 数据库存储引擎索引的底层结构 BTree的随机写特点 LSM树的诞生背景 简介 LSM树与B树的差异 LSM树优化 LSM树基本原理 LevelDB中的LSM HBase中的LSM树 图解 插入 查找 删除 为什么要有...
  • LSM树理解

    2019-06-17 19:45:00
    对比三种引擎的实现:  hash存储引擎:哈希表持久化的实现,可以快速支持增删改查等随机操作,且时间复杂度为o(1)...lsm树存储引擎和b树存储引擎,一样支持,增删改查,也支持顺序扫描操作。LSM牺牲了读性能,提...
  • HBase中LSM树的介绍

    2019-04-08 00:09:51
    LSM树(Log-Structured Merge Tree)存储引擎和B树存储引擎一样,同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写入问题。 LSM树和B+树相比,LSM树牺牲了部分读性能,用来大幅提高写性能...
  • HBase LSM树存储结构

    多人点赞 2020-07-05 17:47:17
    HBase LSM树存储结构 1、LSM树的由来 ​ 在了解LSM树之前,大家需要对hash表和B+树有所了解。 ​ hash存储方式支持增、删、改以及随机读取操作,但不支持顺序扫描,对应的存储系统为key-value存储系统。对于key-...
  • LSM树原理及应用到HBase的索引

    千次阅读 2018-08-07 00:35:26
    @Author : Spinach | GHB @Link : http://blog.csdn.net/bocai8058 概念 ...LSM树 ...LSM树的读写 LSM树的读写 LSM树的优化方式 ...B树与LSM树的适应场景 ... LSM树全称是基于日志结构的合并树(Log-Structured M...
  • B+树和LSM树对比

    2020-06-23 09:31:25
    B+树 B树存储引擎是B树的持久化实现,不仅支持单条记录的增、删、读、...LSM树(Log-Structured Merge Tree)存储引擎和B树存储引擎一样,同样支持增、删、读、改、顺序扫描操作。而且通过批量存储技术规避磁盘随机写
  • HBase的LSM树

    千次阅读 2015-07-05 22:57:31
    HBase的LSM树LSM树之前,需要提下三种基本的存储引擎,这样才能清楚LSM树的由来: 哈希存储引擎 是哈希表的持久化实现,支持增、删、改以及随机读取操作,但不支持顺序扫描,对应的存储系统为key-value...
  • 因此对于关系型数据库来说随机读写比顺序读写慢很多,为了提升IO性能,我们需要一种能将随机操作变为顺序操作的机制,于是便有了本篇要讲的LSM树LSM树能让我们进行顺序写磁盘,从而大幅提升写操作,作为代价的是...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,194
精华内容 2,077
关键字:

lsm树