LSM-tree 基本原理及应用_LSM数,lsm,lsm-tire_永生只是一场幻梦-CSDN博客

标签: | 发表时间:2020-01-11 09:45 | 作者:
出处:https://blog.csdn.net

LSM-tree 在 NoSQL 系统里非常常见,基本已经成为必选方案了。今天介绍一下 LSM-tree 的主要思想,再举一个 LevelDB 的例子。

正文 3056 字,预计阅读时间 8 分钟。

 

LSM-tree

起源于 1996 年的一篇论文《The Log-Structured Merge-Tree (LSM-Tree)》,这篇论文 32 页,我一直没读,对 LSM 的学习基本都来自顶会论文的背景知识以及开源系统文档。今天的内容和图片主要来源于 FAST'16 的《WiscKey: Separating Keys from Values in SSD-conscious Storage》。

先看名字,log-structured,日志结构的,日志是软件系统打出来的,就跟人写日记一样,一页一页往下写,而且系统写日志不会写错,所以不需要更改,只需要在后边追加就好了。各种数据库的写前日志也是追加型的,因此日志结构的基本就指代追加。注意他还是个 “Merge-tree”,也就是“合并-树”,合并就是把多个合成一个。

 

LSM-tree 是专门为 key-value 存储系统设计的,key-value 类型的存储系统最主要的就两个个功能,put(k,v):写入一个(k,v),get(k):给定一个 k 查找 v。

LSM-tree 最大的特点就是写入速度快,主要利用了磁盘的顺序写,pk掉了需要随机写入的 B-tree。关于磁盘的顺序和随机写可以参考:《硬盘的各种概念》

下图是 LSM-tree 的组成部分,是一个多层结构,就更一个树一样,上小下大。首先是内存的 C0 层,保存了所有最近写入的 (k,v),这个内存结构是有序的,并且可以随时原地更新,同时支持随时查询。剩下的 C1 到 Ck 层都在磁盘上,每一层都是一个在 key 上有序的结构。

写入流程:一个 put(k,v) 操作来了,首先追加到写前日志(Write Ahead Log,也就是真正写入之前记录的日志)中,接下来加到 C0 层。当 C0 层的数据达到一定大小,就把 C0 层 和 C1 层合并,类似归并排序,这个过程就是Compaction(合并)。合并出来的新的 new-C1 会顺序写磁盘,替换掉原来的 old-C1。当 C1 层达到一定大小,会继续和下层合并。合并之后所有旧文件都可以删掉,留下新的。

注意数据的写入可能重复,新版本需要覆盖老版本。什么叫新版本,我先写(a=1),再写(a=233),233 就是新版本了。假如 a 老版本已经到 Ck 层了,这时候 C0 层来了个新版本,这个时候不会去管底下的文件有没有老版本,老版本的清理是在合并的时候做的。

写入过程基本只用到了内存结构,Compaction 可以后台异步完成,不阻塞写入。

查询流程:在写入流程中可以看到,最新的数据在 C0 层,最老的数据在 Ck 层,所以查询也是先查 C0 层,如果没有要查的 k,再查 C1,逐层查。

一次查询可能需要多次单点查询,稍微慢一些。所以 LSM-tree 主要针对的场景是写密集、少量查询的场景。

LSM-tree 被用在各种键值数据库中,如 LevelDB,RocksDB,还有分布式行式存储数据库 Cassandra 也用了 LSM-tree 的存储架构。

 

LevelDB

其实光看上边这个模型还有点问题,比如将 C0 跟 C1 合并之后,新的写入怎么办?另外,每次都要将 C0 跟 C1 合并,这个后台整理也很麻烦啊。这里以 LevelDB 为例,看一下实际系统是怎么利用 LSM-tree 的思想的。

下边这个图是 LevelDB 的架构,首先,LSM-tree 被分成三种文件,第一种是内存中的两个 memtable,一个是正常的接收写入请求的 memtable,一个是不可修改的immutable memtable。

另外一部分是磁盘上的 SStable (Sorted String Table),有序字符串表,这个有序的字符串就是数据的 key。SStable 一共有七层(L0 到 L6)。下一层的总大小限制是上一层的 10 倍。

写入流程:首先将写入操作加到写前日志中,接下来把数据写到 memtable中,当 memtable 满了,就将这个 memtable 切换为不可更改的 immutable memtable,并新开一个 memtable 接收新的写入请求。而这个 immutable memtable 就可以刷磁盘了。这里刷磁盘是直接刷成 L0 层的 SSTable 文件,并不直接跟 L0 层的文件合并。

每一层的所有文件总大小是有限制的,每下一层大十倍。一旦某一层的总大小超过阈值了,就选择一个文件和下一层的文件合并。就像玩 2048 一样,每次能触发合并都会触发,这在 2048 里是最爽的,但是在系统里是挺麻烦的事,因为需要倒腾的数据多,但是也不是坏事,因为这样可以加速查询。

这里注意,所有下一层被影响到的文件都会参与 Compaction。合并之后,保证 L1 到 L6 层的每一层的数据都是在 key 上全局有序的。而 L0 层是可以有重叠的。

上图是个例子,一个 immutable memtable 刷到 L0 层后,触发 L0 和 L1 的合并,假如黄色的文件是涉及本次合并的,合并后,L0 层的就被删掉了,L1 层的就更新了,L1 层还是全局有序的,三个文件的数据顺序是 abcdef。

虽然 L0 层的多个文件在同一层,但也是有先后关系的,后面的同个 key 的数据也会覆盖前面的。这里怎么区分呢?为每个key-value加个版本号。所以在 Compaction 时候应该只会留下最新的版本。

查询流程:先查memtable,再查 immutable memtable,然后查 L0 层的所有文件,最后一层一层往下查。

 

LSM-tree读写放大

读写放大(read and write amplification)是 LSM-tree 的主要问题,这么定义的:读写放大 = 磁盘上实际读写的数据量 / 用户需要的数据量。注意是和磁盘交互的数据量才算,这份数据在内存里计算了多少次是不关心的。比如用户本来要写 1KB 数据,结果你在内存里计算了1个小时,最后往磁盘写了 10KB 的数据,写放大就是 10,读也类似。

写放大:我们以 RocksDB 的 Level Style Compaction 机制为例,这种合并机制每次拿上一层的所有文件和下一层合并,下一层大小是上一层的 r 倍。这样单次合并的写放大就是 r 倍,这里是 r 倍还是 r+1 倍跟具体实现有关,我们举个例子。

假如现在有三层,文件大小分别是:9,90,900,r=10。又写了个 1,这时候就会不断合并,1+9=10,10+90=100,100+900=1000。总共写了 10+100+1000。按理来说写放大应该为 1110/1,但是各种论文里不是这么说的,论文里说的是等号右边的比上加号左边的和,也就是10/1 + 100/10 + 1000/100 = 30 = r * level。个人感觉写放大是一个过程,用一个数字衡量不太准确,而且这也只是最坏情况。

读放大:为了查询一个 1KB 的数据。最坏需要读 L0 层的 8 个文件,再读 L1 到 L6 的每一个文件,一共 14 个文件。而每一个文件内部需要读 16KB 的索引,4KB的布隆过滤器,4KB的数据块(看不懂不重要,只要知道从一个SSTable里查一个key,需要读这么多东西就可以了)。一共 24*14/1=336倍。key-value 越小读放大越大。

 

总结

关于 LSM-tree 的内容和 LevelDB 的设计思想就介绍完了,主要包括写前日志 WAL,memtable,SStable 三个部分。逐层合并,逐层查找。LSM-tree 的主要劣势是读写放大,关于读写放大可以通过一些其他策略去降低。

 

 

 

 

相关 [lsm tree 原理] 推荐:

LSM-tree 基本原理及应用_LSM数,lsm,lsm-tire_永生只是一场幻梦-CSDN博客

- -
LSM-tree 在 NoSQL 系统里非常常见,基本已经成为必选方案了. 今天介绍一下 LSM-tree 的主要思想,再举一个 LevelDB 的例子. 正文 3056 字,预计阅读时间 8 分钟. 起源于 1996 年的一篇论文《The Log-Structured Merge-Tree (LSM-Tree)》,这篇论文 32 页,我一直没读,对 LSM 的学习基本都来自顶会论文的背景知识以及开源系统文档.

[转][转]LSM-Tree (BigTable 的理论模型)

- - heiyeluren的Blog
LSM-Tree理论模型:. 来源:http://www.cnblogs.com/raymondshiquan/archive/2011/06/04/2072630.html . Google的BigTable架构在分布式结构化存储方面大名鼎鼎,其中的MergeDump模型在读写之间找到了一个较好的平衡点,很好的解决了web scale数据的读写问题.

mysql索引原理之B+/-Tree

- - CSDN博客架构设计推荐文章
索引,是为了更快的查询数据,查询算法有很多,对应的数据结构也不少,数据库常用的索引数据结构一般为B+Tree. 关于B-Tree的官方定义个人觉得比较难懂,通俗一点就是举个例子. 假如:一本英文字典,单词+详细解释组成了一条记录,现在需要索引单词,那么以单词为key,单词+详细解释为data,B-Tree就是以一个二元组{key,data}来定义一条记录.

btree/b+tree结构原理和应用

- - BlogJava-首页技术区
最近在公司有点时间所以深入研究了下数据库索引btree/b+tree数据结构和原理,由此牵引出了好多问题,请看如下带着问题研究. 1:为什么 btree/b+tree 数据结构适合数据库索引,它到底是怎么样一个原理和结构. btree/b+tree 数据结构:. 在之前的文章中我们介绍过AVL树,红黑树,它们都属于二叉树,即每个节点最多只能拥有2个子节点,而B-tree(B树)的每个节点可以拥有2个以上的子节点,所以我们简单概括一下:B-tree就是一颗多路平衡查找树,它广泛应用于数据库索引和文件系统中.

XML to tree XML 树

- Bloger - 博客园-首页原创精华区
前面发了一个 html to tree 再发一个 xml to tree. 版权所有:版权所有(C) 2009. 文件名称:xml2tree.js. 完成日期:2009-12-22. 页:http://www.chaige.net */ var XML2Tree = function (ini) {.

LSM存储组织结构介绍 - bangerlee

- - 博客园_首页
LSM(Log Structured Merge Trees)数据组织方式被应用于多种数据库,如LevelDB、HBase、Cassandra等,下面我们从为什么使用LSM、LSM的实现思路两方面介绍这种存储组织结构,完成对LSM的初步了解. LSM相较B+树或其他索引存储实现方式,提供了更好的写性能.

露天小便器P-tree

- Haitao - 设计|生活|发现新鲜
2011年丹麦洛斯基尔德音乐节吸引超过10万的游客,强大的人流量对城市的公共厕所的需求也提出了考验. 但丹麦的AANDEBOOM公司却巧妙的解决了这一问题. 他们设计了50个露天小便器,分别放在主会场附近的2个不同街道. 事实证明,它确实是成功的,有大量游客乐意使用它. 这小便器还有个可爱的名字,P-Tree,向大树尿尿,顿时想到小公狗,翘起腿朝树上尿尿哦.

emacs 新手必看: undo-tree

- leafduo - LinuxTOY
火星人都知道,emacs 只有 undo ,没有 redo ……或者说它有 redo,但是相当的诡异,套用一句经典台词就是: 猥琐,非常的猥琐. 简单的说,emacs 的 redo 就是 undo undo ,也就是传说中的负负得正. 可能有些 emacs 新手,还不知道怎么去操作,因为一般情况下,无论你 undo 多少次,都不会发生 redo 的现象.

[转][转]TokuDB中的COLA-Tree和TokuMax中的Fractal tree(分形树)

- - heiyeluren的blog(黑夜路人的开源世界)
TokuDB中的COLA-Tree.       目前无论是商业的SQL Server,还是开源的MySQL,都基本上还在用比较老的 B+Tree(SQL Server用的是标准的B-Tree)的索引结构. 从原理来说,B系列树在查询过程中应该是不会慢的,而主要问题就是出现在插入. B-Tree在插入的时候,如果是最后一个node,那么速度非常快,因为是顺序写.

理解 LSM 树:写入密集型数据库的秘诀

- - 掘金后端
原文: yetanotherdevblog.com/lsm/. 日志结构的合并树( log-structured merge-tree LSM 树)通常是在处理大量写任务时使用的数据结构. LSM 树是许多数据库(包括 BigTable, Cassandra, Scylla,和 RocksDB)背后的核心数据结构.