【工作】深度理解LSM树

背景

LSM树应用场景太多了,个人接触过的就有这些。。戳个FLAG,一定要弄明白。

  • HBASE
  • LevelDB/RocksDB
  • Ceph底层osd的对象存储
  • 图数据库Dgraph底层存储badger (+bloomfilter)
  • Hadoop的对象存储OZone的container底层存储
  • ClickHouse最主要的MergeTree引擎
  • &

LSM是什么

首先,LSM是一种支持快速查找的存储结构。

各种查找算法,要么依赖哈希如HashMap,要么依赖排序如TreeMap/SkipList,而排序更泛用一些,比如空间更紧凑,支持区间获取等,所以应用更广泛。主流的数据库索引B+树就是优化后的排序好的树状结构,但是B+树的问题在于其插入和删除时需要动态调整树的结构以保持平衡,而这需要较多的随机磁盘读写,这也导致了B+树的写入性能不高。

LSM也是一种基于排序的树,在存储和检索上做了一些策略和优化。

存储的本质是IO性能的最大化利用,当然还得考虑到功能的支持。要知道所有的决策前提是:

  • 内存读写速度比磁盘快几个数量级,但是内存有限
  • 磁盘顺序读写速度又比随机读写快几个数量级(磁盘寻道的物理特性决定)

这样一来,尽可能的使用内存,尽可能的使用顺序读写是设计的关键。如Redis,全内存K-V系统,OPS能到每秒10万级别(配合管道更高),而消息队列kafka结合顺序读写和offset机制,吞吐能达到GB/s单节点(当然是多磁盘)。但是不同设计都是一些取舍的结合,Redis只支持KV操作,不支持区间查找,kafka本质是顺序写入和消费,甚至不支持随机读写,也不支持更新。

而LSM是各种折中的结果,即热点数据读写在内存,并且写入是顺序写,覆盖式更新,弱锁依赖,有很高的写入性能。并且结合数据局部性,排序,bloomfilter等特性,使读取也有很好的效果,是一个既支持k-v操作,也支持区间操作的综合效果较好的存储设计。

LSM起源于 1996 年的一篇论文《The Log-Structured Merge-Tree (LSM-Tree)》,日志合并树。

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

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

image.png

写入流程:一个 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 层,如果没有要查的 key,再查 C1,逐层查。

以上是LSM树的基本思想,实际工程实现上有很多考虑,但是核心不变。

为什么LSM结构是存储系统重要选型

主流的关系型数据库均以 B/B+ tree 作为其构建索引的数据结构,这是因为 B tree 提供了理论上最高的查询效率O(log n)。但对查询性能的追求也造成了 B tree 的相应缺点,即每次插入或删除一条数据时,均需要更新索引,从而造成一次磁盘 IO。这种特性决定了 B tree 只适用于频繁读、较少写的场景。如果在频繁写的场景下,将造成大量的磁盘 IO,从而导致性能骤降。这种应用场景在传统的关系型数据库中比较常见。

而 LSM tree 则避免了频繁写场景下的磁盘 IO 开销,尽管其查询效率无法达到理想的O(log n),但依然非常快,可以接受。所以从本质上来说,LSM tree 相当于牺牲了一部分查询性能,换取了可观的写入性能。这对于 key-value 型或日志型数据库是非常重要的。

技术细节和关键性取舍

LSM本质不是一个算法,当成一个方法更合适。是一个存储结构,然后可以有很多变体。这一点其实B树体系也像。

LSM和Btree差异就要在读性能和写性能进行舍和求。在牺牲的同时,寻找其他方案来弥补。

主要的影响因素:

  • 内存数据多大(hot memory table)?
  • 什么时候合并,选取哪些数据合并 ?(保持层内有序)
  • 数据分为几层 ?(阈值,策略)
  • 重复key怎么处理 ?(异步删)
  • 怎么尽可能减少查询时的搜索次数 ?(过滤器,层内稀疏索引,跳跃表等)

LevelDB

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

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

image.png

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

每一层的所有文件总大小是有限制的,每下一层大十倍。一旦某一层的总大小超过阈值了,就选择一个文件和下一层的文件合并。

并且,合并后保持每层都是总体有序。

每一层可以维护指定的文件个数,同时保证不让key重叠。也就是说把key分区到不同的文件。因此在一层查找一个key,只用查找一个文件。

RocksDB在LevelDB上的改进

  • 多核优化、锁优化、缓存控制优化
  • 支持一次获取多个K-V,还支持Key范围查找。LevelDB只能获取单个Key
  • 支持多线程合并,而LevelDB是单线程合并
  • 增加了合并时过滤器,对一些不再符合条件的K-V进行丢弃,如根据K-V的有效期进行过滤
  • 更多的压缩方式
  • 可以允许根据需要开辟多个Memtable,以解决Put与Compact速度差异的性能瓶颈问题。在LevelDB里面因为只有一个Memtable,如果Memtable满了却还来不及持久化,这个时候LevelDB将会减缓Put操作,导致整体性能下降
  • 前缀bloom过滤器
  • 备份、统计、动态参数修改、命令工具等等

总体来说,RocksDB在很多方面对LevelDB做了优化和增强,更像是一个完整的产品。

小结

LSM树原理是把一棵大树拆分成N棵小树,它首先有序地写入内存中,(比如基于红黑树,或者跳跃表),随着小树越来越大,内存中的小树会flush到磁盘中,磁盘中的树定期可以做merge操作,合并成一棵大树,以优化读性能。

LSM逻辑和物理都是分层的,最上层是内存,层越下容量越大,通常是越老的数据。读取时类似自顶向下查找,先查最顶层,如果没有则查下一层,直到找到。同时每层辅助以布隆过滤器,稀疏索引等手段快速定位目标。

image.png

PS 202110. Hbase的写入和合并

  • 写入的时候最底层封装是一个跳跃表(与红黑树类似 都是map结构 且排序,实现更简单,索引更紧凑,性能查了一下应该是差不多 )
MemStore-> Segment -> CellCet -> this.delegatee = new ConcurrentSkipListMap<>(c);
  • 有多个层次 内存满了写入Hstore
  • 后台有Compaction的检查线程 触发合并时,传入一个List StoreFile ,合并后写入到一个新的StoreFile
  • 合并的过程:各个StoreFile创建Scanner,封装在一个优先队列里。然后就是迭代,比较,写入,持续循环 ... (这里和CarbonData的合并差不多好像)
KeyValueHeap
    protected PriorityQueue<KeyValueScanner> heap = null;

image.png
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,922评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,591评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,546评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,467评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,553评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,580评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,588评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,334评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,780评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,092评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,270评论 1 344
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,925评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,573评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,194评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,437评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,154评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,127评论 2 352