美文网首页
LSM Tree 模型

LSM Tree 模型

作者: wayyyy | 来源:发表于2022-09-01 02:41 被阅读0次

论文原文:The Log-Structured Merge-Tree (LSM-Tree)

以下全文转自:

LSM Tree 模型

LSM Tree 它并不类似于B+ Tree 是一种数据结构,本质上它是一种模型。

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

lsm-tree.png
  • MemTable
    MemTable是在内存中的数据结构,用于保存最近更新的数据,会按照Key有序地组织这些数据,LSM树对于具体如何组织有序地组织数据并没有明确的数据结构定义,例如Hbase使跳跃表来保证内存中key的有序。因为数据暂时保存在内存中,内存并不是可靠存储,如果断电会丢失数据,因此通常会通过WAL(Write-ahead logging,预写式日志)的方式来保证数据的可靠性。

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

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

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

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

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

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

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

  • 读放大
    读取数据时实际读取的数据量大于真正的数据量。例如在LSM树中需要先在MemTable查看当前key是否存在,不存在继续从SSTable中寻找。

  • 写放大
    写入数据时实际写入的数据量大于真正的数据量。例如在LSM树中写入时可能触发Compact操作,导致实际写入的数据量远大于该key的数据量。

  • 空间放大
    数据实际占用的磁盘空间比数据的真正大小更多。上面提到的冗余存储,对于一个key来说,只有最新的那条记录是有效的,而之前的记录都是可以被清理回收的。

相关文章

  • LSM Tree 模型

    论文原文:The Log-Structured Merge-Tree (LSM-Tree)[https://www...

  • HBase的存储结构——LSM-Tree

    LSM-Tree是什么 LSM-Tree(Log Structured Merge Tree),一种分层、有序、面...

  • LSM-tree vs B-tree

    lsm-tree vs B-tree 直觉来看,LSM-tree的优势在于写性能, B-tree的优势在于读性能,...

  • Paper Reading:【FAST 2016】Wisckey

    Wisckey 是针对 LSM-Tree 在 SSD 存储下的优化。LSM-Tree 目前应用已经很广了,主要应用...

  • LSM

    简介 Log Structured Merge Tree,下面简称 LSM。 特点 LSM树(Log-Struct...

  • 深度 | X-Engine的In-Memory读性能优化

    背景 虽然同为LSM-tree架构,X-Engine的设计哲学与传统基于LSM-tree架构的Rocksdb等引擎...

  • LSM Tree

    2019-10-18 LSM 核心思想的核心就是放弃部分读能力,换取写入的最大化能力。LSM Tree ,这个概念...

  • LSM-tree 基本原理及应用

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

  • LSM-tree 基本原理及应用

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

  • LSM Tree 日志结构合并树

    LSM Tree 全称是Log Struct Merge Tree 日志结构合并树。虽然叫tree,但是其实他并不...

网友评论

      本文标题:LSM Tree 模型

      本文链接:https://www.haomeiwen.com/subject/angrnrtx.html