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

标签: 理解 lsm 数据库 | 发表时间:2020-07-14 03:45 | 作者:咔叽咔叽
出处:https://juejin.im/welcome/backend

原文: yetanotherdevblog.com/lsm/

日志结构的合并树( log-structured merge-tree LSM 树)通常是在处理大量写任务时使用的数据结构。通过顺序写来优化写入路径。 LSM 树是许多数据库(包括 BigTable, Cassandra, Scylla,和 RocksDB)背后的核心数据结构。

排序字符串表

LSM 树使用 排序字符串表(Sorted Strings Table 简称 SSTable)的格式保存到磁盘。如名称所示,SSTables 是一种用于存储键-值对的格式,其中键按有序排列。SSTable 将由多个名为段( Segments)的有序文件组成。一旦将这些数据段写入磁盘后,就是不可变的。简化示例如下:

我们可以看到,每个段中的键-值对都是按键排序的。接下来看看什么是片段以及它是如何生成的。

写数据

回想一下,LSM 树只执行顺序写入。我们可能想知道,当值以任意顺序写入时,如何以有序格式的顺序写入数据?这可以通过使用内存中的树结构来解决。通常被称为内存表( memtable),但底层数据结构通常是某种形式的排序树,如 红黑树。当写入数据时,将添加到此红黑树中。

我们的写入将存储在这个红黑树中,直到树达到预定义的大小。一旦红黑树有足够的条目,它就会按有序的顺序作为磁盘上的一个段刷新到磁盘。这就允许我们将段文件顺序写入,即使插入时的顺序是不固定的。

读数据

那么,如何在 SSTable 中找到对应的值呢?一种简单的方法是扫描数据段来查找所需的键。从最新的段开始,扫到最旧的段,直到找到我们想要的键。这意味着我们会优先检索最近写入的键。一个简单的优化是在内存中保存 sparse index 稀疏索引

我们可以使用这个索引来快速找到目标键之前和之后的值的偏移量。现在,只需根据这些界限扫描每个段文件的一小部分。我们考虑一个场景,假如我们想要在上面的段中查找键 dollar。我们可以对稀疏索引执行二分搜索,发现 dollar 介于 dogdowngrade 之间。现在,只需从偏移量 17208 到 19504 进行扫描,即可找到该值(或确定该值是否丢失)。

这是一个很好的改进,但是如果查找不存在的记录呢?仍然需要循环遍历所有段文件,并且找不到目标键。 布隆过滤器可以帮助我们解决这个问题。布隆过滤器是一种节省空间的数据结构,它可以告诉我们数据中某个键是否存在。我们可以在写入数据时将数据添加到过滤器中,并在读取开始时对其进行检查,以便有效地响应不存在的数据的请求。

压缩

随着时间的推移,系统在运行时会积累越来越多的段文件。这些段文件需要清理和维护,以防止段文件的数量失控。这个过程称为压缩。压缩是一个将连续旧段合并到新段的后台进程。

在上面的示例中可以看到,segment 1 和 segment 2 都存有 dog 键的值。较新的段包含了最新的写入值,因此 segment 2 中的值将结转到 segment 4 中。一旦压缩进程为输入段写入了新段,旧段文件将被删除。

删除数据

我们已经讨论了读数据和写数据,但是如何删除数据呢?当段文件被认为是不可变的时,如何从 SSTable 中删除数据呢?删除实际上遵循与写入数据完全相同的路径。每当收到删除请求时,都会为该键写入一个名为 tombstone(也就是标记为删除的 key)的唯一标记。

上面的示例显示,键 dog 在过去的某个时候的值是 52,但现在它有了一个删除标记。这表示如果我们收到键为 dog 的请求,那么会返回一个响应,表明该键不存在。这意味着删除后实际上还会占用磁盘空间,这可能会让许多开发人员感到惊讶。最终,该删除标记将被压缩,这样该值就不再存在于磁盘上。

结论

我们现在了解了 LSM 树存储引擎的工作原理:

  1. 写入数据存储在内存树(也称为内存表)中。任何支持的数据结构(布隆过滤器和稀疏索引)也会在必要时更新。
  2. 当此树变得足够大时,它会被刷新到磁盘,键按有序排列。
  3. 当读取数据时,先检查布隆过滤器。如果过滤器表示该值不存在,则返回客户端没有此键。如果过滤器表示该值存在,则我们以新到旧的顺序迭代段文件。
  4. 对于每个段文件,我们检查稀疏索引,并扫描目标关键字的偏移量,直到找到关键字。一旦在段文件中找到该值,将立即返回。

相关 [理解 lsm 数据库] 推荐:

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

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

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数据的读写问题.

LSM存储组织结构介绍 - bangerlee

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

理解MySQL数据库覆盖索引

- - haohtml's blog
看AUTO_INCREMENT就知道数据并不多,75万条. 很简单对不对?怪异的地方在于:. 如果换成MyISAM做存储引擎的时候,查询耗时只需要0.01s,用InnoDB却会是0.15s左右. 如果只是就这么点差距其实不是什么大不了的事,但是真实的业务需求比这个复杂,造成的差距也很大:MyISAM只需要0.12s,InnoDB则需要2.2s.,最终定位到问题症结是在这条SQL.

从数据库层面理解:随机 I/O & 顺序 I/O

- - CSDN博客数据库推荐文章
      在谈这俩概念前、先来说说 大I/O vs.      通常、我们把 <=16KB 的I/O认为是小I/O、而 >=32KB 的I/O认为是大I/O.      了解I/O的大小、影响到后期对缓存、RAID类型、LUN的一些属性的调优 .      当前大多数数据库使用的都是传统的机械磁盘.

数据库水平切分的实现原理解析

- - 数据库 - ITeye博客
本文系转载,原文地址: http://lishuaibt.iteye.com/blog/409294. 随着互联网应用的广泛普及,海量数据的存储和访问成为了系统设计的瓶颈问题. 对于一个大型的 互联网应用,每天几十亿的PV无疑对数据库造成了相当高的负载. 对于系统的稳定性和扩展性造成了极大的问题.

Android SQLite数据库版本升级原理解析

- - CSDN博客推荐文章
Android使用SQLite数据库保存数据,那数据库版本升级是怎么回事呢,这里说一下. 安装v1.0,假设v1.0版本只有一个account表,这时走继承SQLiteOpenHelper的onCreate,不走onUpgrade. 1、v1.0(直接安装v1.0). 1、v1.0   -->  v2.0              不走onCreate,走onUpgrade.

理解数据库中的undo日志、redo日志、检查点 | 乐天的个人网站

- -
数据库存放数据的文件,本文称其为data file. 数据库的内容在内存里是有缓存的,这里命名为db buffer. 某次操作,我们取了数据库某表格中的数据,这个数据会在内存中缓存一些时间. 对这个数据的修改在开始时候也只是修改在内存中的内容. 当db buffer已满或者遇到其他的情况,这些数据会写入data file.

数据库sharding

- - 数据库 - ITeye博客
当团队决定自行实现sharding的时候,DAO层可能是嵌入sharding逻辑的首选位置,因为在这个层面上,每一个DAO的方法都明确地知道需要访问的数据表以及查询参数,借助这些信息可以直接定位到目标shard上,而不必像框架那样需要对SQL进行解析然后再依据配置的规则进行路由. 另一个优势是不会受ORM框架的制约.