精华内容
下载资源
问答
  • levelDB的LSM文件树

    2018-12-15 19:15:38
    前言 下面是一篇转自简书的文章,介绍...LSM文件树是基于Bigtable思想用于levelDB数据库(google两位重量级架构,Jeff Dean和Sanjay Ghemawat所发起的开源数据库)的一个存储结构,在这里做一个简单的理解。 LSM文件...

    前言

    下面是一篇转自简书的文章,介绍了leveldb所使用的LSM算法。

    作者:散入风中
    链接:https://www.jianshu.com/p/d578495f8557
    來源:简书

    LSM文件树是基于Bigtable思想用于levelDB数据库(google两位重量级架构,Jeff Dean和Sanjay Ghemawat所发起的开源数据库)的一个存储结构,在这里做一个简单的理解。

    LSM文件树结构与各文件作用解析

    LSM文件树在内存中有两种不同的表现形式,分别为MemTable(可读写的内存表空间),ImmutableMemTable(可读不可写的内存表空间),而levelDB表现出来的是以文件存储为优先的存储形式,区别于Redis这样的内存型nosql,所以在磁盘中,LSM文件树表现出几种主要文件,分别为Current文件,Manifest文件,log文件,以及SSTable文件,以上六种元素构成了levelDB的主体。

    在LSM文件树中,log文件和MemTable是绑定在一起的,并且log文件的优先级大于MemTable,在插入一条数据时,先向log文件中写入插入的数据,成功之后才将这条数据写入MemTable中,如果出现内存断电这种情况,因为写入log执行级别大于写入内存,不需要担心丢失内存数据,我们可以再次根据log中的内容写入MemTable中,这样就避免了Redis的问题,而且,因为只需执行一次磁盘顺序写和一次内存随机写,大大提高了写的效率。

    当MemTable达到一个界限时,会自动转变为ImmutableMemTable,此时该内存可读不可写,会另外开辟一块空间生成新的MemTable和新的log,新到来的数据会被写入到新的log和MemTable中,levelDB后台调度会将ImmutableMemTable导出,生成一个SSTable文件,SSTable就是由这样的不断推演不断产生,并且这些SSTable有一种层级结构,第一层为level0,第二层为level1,这也是levelDB名字的由来。

    而SSTable的某个文件属于特定层级,且key有序,那必然存在最大key和最小key,这是树的特征,也是非常重要的信息,Manifest文件就是用来存储这些信息的,它记载了SSTable各个文件的管理信息,比如属于哪一个Level,文件的名称,min key 和max key 各是什么等。

    Current文件是用来记录当前Manifest名字的一个文件,随着SSTable文件的变化,会有新的SSTable产生,也会有废弃的SSTable被删除,Manifest文件也在随之变化,也会生成新的Manifest文件来记录这种变化,Current就是记录当前的Manifest的文件名,方便我们能够轻易查看到当前数据变化的Manifest的一个文件。

    展开全文
  • 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树,即日志结构合并(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%满的,节点的大小为磁盘块大小。

     

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

    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

    展开全文
  • LSM树存储引擎

    千次阅读 2016-03-27 14:33:40
    2.2.3 LSM树存储引擎 LSM树(Log Structured Merge Tree)的思想非常...LSM树的优势在于有效地规避了磁盘随机写入问题,但读取时可能需要访问较多的磁盘文件。本节介绍LevelDB中的LSM树存储引擎。 1.存储结构
  • 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-03-19 11:06:36
    而前不久我在研究Raft算法时,偶然发现了一种和B+类似的数据结构——LSM树(Log-Structured-Merge-Tree 日志结构合并),它是Google发表的论文Big Table中提到的一种很有趣的文件组织数据结构, 现如今已经被...
  • HBase LSM树

    千次阅读 2016-06-01 18:02:02
    HBase文件系统LSM数据结构的主题思想与特点
  • HBase的LSM树

    千次阅读 2015-07-05 22:57:31
    HBase的LSM树LSM树之前,需要提下三种基本的存储引擎,这样才能清楚LSM树的由来: 哈希存储引擎 是哈希表的持久化实现,支持增、删、改以及随机读取操作,但不支持顺序扫描,对应的存储系统为key-value...
  • LSM树理解

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

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

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

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

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

    千次阅读 2018-08-07 00:35:26
    @Author : Spinach | GHB ... 概念 B+ LSM树 ...LSM树的读写 LSM树的读写 LSM树的优化方式 关于LSM最本质原理的3个问题 ...BLSM树的适应场景 ... LSM树全称是基于日志结构的合并(Log-Structured M...
  • 因此对于关系型数据库来说随机读写比顺序读写慢很多,为了提升IO性能,我们需要一种能将随机操作变为顺序操作的机制,于是便有了本篇要讲的LSM树LSM树能让我们进行顺序写磁盘,从而大幅提升写操作,作为代价的是...
  • LSM 的结构

    2021-08-05 18:00:27
    LSM 存储引擎的结构暗含在它的名字内。LS 代表日志结构,说明它是以日志形式来存储数据的,那么日志有什么特点呢?如果你对财务记账有些了解的话,会知道会计在删除一笔记录时,是不会直接拿着橡皮擦去擦掉这个...
  • B+LSM树对比

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

    2021-04-12 19:45:12
    B、B+LSM树 区别 LSM-Tree(Log Structured Merge Tree) LSM树的索引结构本质是将写入操作全部转化成磁盘的顺序写入,极大地提高了写入操作的性能。但是,这种设计对读取操作是非常不利的,因为需要在读取的...

空空如也

空空如也

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

lsm文件树