LSM
1.MySQL存储引擎:
B+树
https://blog.csdn.net/qq_26222859/article/details/80631121
2.HBase
LSM树
核心:将对数据的修改增量保持在内存中,达到指定的大小限制后将这些修改操作批量写入磁盘
https://www.cnblogs.com/yanghuahui/p/3483754.html
关于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树的由来:
- 哈希存储引擎 是哈希表的持久化实现,支持增、删、改以及随机读取操作,但不支持顺序扫描,对应的存储系统为key-value存储系统。对于key-value的插入以及查询,哈希表的复杂度都是O(1),明显比树的操作O(n)快,如果不需要有序的遍历数据,哈希表就是your Mr.Right
- B树存储引擎是B树(关于B树的由来,数据结构以及应用场景可以看之前一篇博文)的持久化实现,不仅支持单条记录的增、删、读、改操作,还支持顺序扫描(B+树的叶子节点之间的指针),对应的存储系统就是关系数据库(Mysql等)。
- 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树 插入数据可以看作是一个N阶合并树。数据写操作(包括插入、修改、删除也是写)都在内存中进行,
数据首先会插入内存中的树。当内存树的数据量超过设定阈值后,会进行合并操作。合并操作会从左至右便利内存中树的子节点 与 磁盘中树的子节点并进行合并,会用最新更新的数据覆盖旧的数据(或者记录为不同版本)。当被合并合并数据量达到磁盘的存储页大小时。会将合并后的数据持久化到磁盘,同时更新父节点对子节点的指针。
LSM树 读数据 磁盘中书的非子节点数据也被缓存到内存中。在需要进行读操作时,总是从内存中的排序树开始搜索,如果没有找到,就从磁盘上的排序树顺序查找。
在LSM树上进行一次数据更新不需要磁盘访问,在内存即可完成,速度远快于B+树。当数据访问以写操作为主,而读操作则集中在最近写入的数据上时,使用LSM树可以极大程度地减少磁盘的访问次数,加快访问速度。
LSM树 删除数据 前面讲了。LSM树所有操作都是在内存中进行的,那么删除并不是物理删除。而是一个逻辑删除,会在被删除的数据上打上一个标签,当内存中的数据达到阈值的时候,会与内存中的其他数据一起顺序写入磁盘。 这种操作会占用一定空间,但是LSM-Tree 提供了一些机制回收这些空间。
转载参考:https://baijiahao.baidu.com/s?id=1613810327967900833&wfr=spider&for=pc
关于LSM结构的相关介绍,这篇文章比较好,特此纪录一下https://yq.aliyun.com/articles/767772
今天给大家分享的内容是LSM树,它的英文是Log-structed Merge-tree。看着有些发怵,但其实它的原理不难,和B树相比简直算是小儿科了。
并且这也是一个非常经典的数据结构,并且在大数据系统当中有非常广泛的应用。有许多耳熟能详的经典系统,底层就是基于LSM树实现的。因此,今天就和大家一起来深入学习一下它的原理。
背景知识
首先,我们先从背景知识开始。我们之前介绍B+树的时候说过,B+树和B树最大的不同就是将所有的数据都放在了叶子节点。从而优化了我们批量插入以及批量查询的效率,而优化的核心逻辑就是因为无论是什么存储介质,顺序存储的效率一定要比随机存储更高,并且高的还不是一点半点。这个已经算是老生常谈了,如果我没记错的话,这已经是我第三次在文章当中提到这一点了。
我最近看到了一张图,很好地阐述了随机读取和顺序读取两者的效率差,我们来看下面这张图。其中绿色的部分表示硬盘顺序读取的最大速度,而红色表示随机读取时的速度。
我们看下纵坐标就知道,这两者差的不是一点半点,已经有数量级的差距了。而且还不止是一个数量级,至少相差了三个数量级,显然这是非常恐怖的。另外,这个差距并不只是在传统的机械硬盘上存在,即使是现在比较先进的SSD固态硬盘上,也一样存在。也就是说这个差距是介质无关的。
直观优化
既然随机读取和顺序读取的效率差了这么多,不由得不让人心动。如果能够发明一个数据结构可以充分地利用上这一点,那么我们的系统对数据的吞吐能力一定可以再上一个台阶。对于许多科技公司而言,尤其是大数据公司,因为数据量带来的机器开销的费用占据了日常支出的大头。如果能够很好地解决这个问题,显然可以节约大量的资源。
一个朴素的想法就是将所有的读写都设计成顺序读写,比如日志系统就是一个典型的例子。在我们记录日志的时候,总是添加在文件的末尾,而不会插入在文件的中间。由于我们总是添加在文件末尾,在磁盘上这是一个顺序的读写。但我们把读写都设计成顺序的,也就意味着我们当我们要查找的内容在文件中间的时候,我们必须要读入文件中的所有内容。
这个思路应用最广泛的地方有两个,一个是数据库的日志当中。在我们用数据库执行写入或者修改操作的时候,数据库会将所有的变更写成log记录下来。还有一处是消息系统的中间件,比如kafka。
但是在复杂的增删查改的场景当中,尤其是涉及到批量读写的场景,简单的文件顺序读写就不能满足需求了。当然我们可以引入哈希表或者是B+树这些数据结构实现功能,但这些复杂的数据结构都避免不了比较慢的随机读写操作,而我们希望随机读写能尽量减少,正是基于这个原理,LSMT被发明了出来。LSMT使用了一种独特的机制牺牲了一些读操作的性能,保证了写操作的能力,它能够让所有的操作顺序化,几乎完全避免了随机读写。
在我们介绍LSMT的原理之前,我们先来介绍一下它的子结构SSTable。
SSTable
第一次看到这个单词的时候觉得一头雾水是正常的,SSTable的全称是Sorted String Table,本质就是一个KV结构顺序排列的文件。我们来看下下图:
最基础的SSTable就是上图当中右侧的部分,即key和value的键值对按照key值的大小排序,并存储在文件当中。当我们需要查找某个key值对应的数据的时候,我们会将整个文件读入进内存,进行查找。同样,写入也是如此,我们会将插入的操作在内存中进行,得到结果之后,直接覆盖原本的文件,而不会在文件当中修改,因为这会牵扯到移动大量的数据。
如果文件中的数据量过大,我们需要另外建立一个索引文件,存储不同的key值对应的offset,方便我们在读取文件的时候快速查找到我们想要查找的文件。索引文件即上图当中左边部分。
需要注意,SSTable是不可修改的,我们只会用新的SSTable去覆盖旧的,而不会再原本的基础上修改。因为修改会涉及随机读写,这是我们不希望的。
LSM的增删改查
理解了SSTable之后,我们来看下基本的LSM实现原理。
其实最基本的LSM原理非常简单,本质上就是在SSTable的基础上增加了一个Memtable,Memtable顾名思义就是存放在内存当中的表结构。当然也不一定是表结构,也可以是树结构,这并不影响,总之是一个可以快速增删改查的数据结构,比如红黑树、SkipList都行。其次我们还需要一个log文件,和数据库当中的log一样,记录数据发生的变化。方便系统故障或者是数据丢失的时候进行找回,所以整体的架构如下:
查找
我们先来看查找的情况,当我们需要查找一个元素的时候,我们会先查找Memtable。原因也很好理解,它就在内存当中,不需要额外读取文件,如果Memtable当中没有找到,我们再一个一个查找SSTable,由于SSTable当中的数据也是顺序存储的,所以我们可以使用二分查找,整个查找的速度也会非常快。但是有一点,由于SSTable的数量可能会很多,而且我们必须要顺序查找,所以当SSTable数量很大的时候,也会影响查找的速度。为了解决这个问题,我们可以引入布隆过滤器进行优化。我们对每一个SSTable建立一个布隆过滤器,可以快速地判断元素是否在某一个SSTable当中。布隆过滤器判断元素不存在是一定准确的,而判断存在可能会有一个很小的几率失误,但这个失误率是可以控制的,我们可以设置合理的参数,使得失误率足够低。
加上了布隆过滤器之后的查找操作是这样的:
上图的星星表示布隆过滤器,也就是说我们先通过布隆过滤器判断元素是否存在之后,再进行查找。
布隆过滤器在之前的文章当中曾经和大家介绍过,有遗忘或者是新关注的同学可以点击下方链接回顾一下。
增删改
除了查找之外的其他操作都发生在Memtable当中,比如当我们要增加一个元素的时候,我们直接增加在Memtable,而不是写入文件。这也保证了增加的速度可以做到非常快。
除此之外,修改和删除也一样,如果需要修改的元素刚好在Memtable当中,没什么好说的我们直接进行修改。那如果不在Memtable当中,如果我们要先查找到再去修改免不了需要进行磁盘读写,这会消耗大量资源。所以我们还是在Memtable当中进行操作,我们会插入这个元素,标记成修改或者是删除。
所以我们可以把增删改这三个操作都看成是添加,但是这就带来了一个问题,这么操作会导致很快Memtable当中就积累了大量数据,而我们的内存资源也是有限的,显然不能无限拓张。为了解决这个问题,我们需要定期将Memtable当中的内容存储到磁盘,存储成一个SSTable。这也是SSTable的来源,SSTable当中的数据不是凭空出现的,而是LSM落盘产生的。
同样,由于我们不断地落盘同样也会导致SSTable的数量增加,前面我们也已经分析过了,SSTable的数量增加会影响我们查找的效率,所以我们不能放任它无限增加。再加上我们还存储了许多修改和删除的信息,我们需要把这些信息落实。为了达成这点,我们需要定期将所有的SSTable合并,在合并的过程当中我们完成数据的删除以及修改工作。换句话说,之前的删除、修改操作只是被记录了下来,直到合并的时候才真正执行。
整个归并的过程并不难,类似于归并排序当中的归并操作,只是我们需要加上状态的判断。
总结
我们回顾一下LSMT的整个过程,虽然说是树,但其实树形结构并不明显。但如果我们观察一下查找元素时候的查询顺序,其实是从Memtable,然后沿着SSTable顺序往下的,这点和树形结构是一致的,可以看成一个比较”窄“的树。如果还是觉得这个数据结构长得不那么像一棵树是正常的,我们不用纠结。另外,从原理上来看,简直有些简单粗暴地过头,但是从实际结果来看,它的效果却非常好,在Hbase、kudu当中有着广泛应用。
我们对比一下它和B+树,在B+树当中,我们为了能够快速读取而使用了多路平衡树,这样可以迅速找到对应key的节点。我们只需要读入节点当中的内容即可,但也正因为平衡树的结构,导致了我们在写入数据的时候会引起树结构的变动,也就涉及到多次文件的随机读写。当我们数据的吞吐量很大的时候,会带来巨大的开销。而LSMT则不然,我们读取的时候效率比B+树要低,但是对于大数据的写入支持得更好。在大数据场景当中,许多对于数据的吞吐量有着很高的要求,比如消息系统、分布式存储等。这个时候B+树就有些无能为力了,但是同样,如果我们需要保证查找的效率,那LSMT也不太合适,因此两者其实并没有谁比谁更优,而是针对的场景不同。
最后,关于LSMT,其实也有很多个变种,其中比较有名的是Jeff Dean写的Leveldb,它在LSMT的基础上做了一些改动,进一步提升了性能