LSM简介

简介

Log Structured Merge Tree,下面简称 LSM。

2006年,Google 发表了 BigTable 的论文。这篇论文提到 BigTable 单机上所使用的数据结构就是 LSM。

目前,LSM 被很多存储产品作为存储结构,比如 Apache HBase, Apache Cassandra, MongoDB 的 Wired Tiger 存储引擎, LevelDB 存储引擎, RocksDB 存储引擎等。

简单地说,LSM 的设计目标是提供比传统的 B+ 树更好的写性能。LSM 通过将磁盘的随机写转化为顺序写来提高写性能 ,而付出的代价就是牺牲部分读性能写放大(B+树同样有写放大的问题)

LSM 相比 B+ 树能提高写性能的本质原因是:外存——无论磁盘还是 SSD,其随机读写都要慢于顺序读写。

优化写性能

如果我们对写性能特别敏感,我们最好怎么做?—— Append Only:所有写操作都是将数据添加到文件末尾。这样做的写性能是最好的,大约等于磁盘的理论速度(200 ~ 300 MB/s)。但是 Append Only 的方式带来的问题是:

  • 读操作不方便。
  • 很难支持范围操作。
  • 需要垃圾回收(合并过期数据)。

所以,纯粹的 Append Only 方式只能适用于一些简单的场景:

  • 数据库的 WAL
  • 能知道明确的 offset,比如 Bitcask

优化读性能

如果我们对读性能特别敏感,一般我们有两种方式:

  • 有序存储,比如 B+ 树,SkipList 等。
  • Hash 存储 —— 不支持范围操作,适用范围有限。

读写性能的权衡

如何获得(接近) Append Only 的写性能,而又能拥有不错的读性能呢?

以 LevelDB 为代表的 LSM 存储引擎给出了一个参考答案。注意,LevelDB 实现的是优化后的 LSM,原始的 LSM 可以参考论文。下面的讨论主要以 LevelDB 为例子。

LevelDB 的写操作主要由两步组成:

  1. 写日志并持久化(Append Only)。
  2. Apply 到内存中的 memtable(SkipList)。

所以,LevelDB 的写速度非常快。

memtable 写“满”后,会转换为 immutable memtable,然后被后台线程 compaction 成按 Key 有序存储的 sst 文件(顺序写)。由于 sst 文件会有多个,所以 LevelDB 的读操作可能会有多次磁盘 IO(LevelDB 通过 table cache、block cache 和 bloom filter 等优化措施来减少读操作的磁盘 IO 次数)。

总结

基于 LSM 数据结构的 LevelDB 的适用场景:

  • 写请求多。
  • 写性能(吞吐+延迟)要求高。

参考文档

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏漏斗社区

黑客游戏| Owasp juice shop (一)

0x01 前言 最近看到一篇关于owasp juice shop的文章,觉的很有意思,斗哥就自己撸了个环境,上手后深深觉的这是一个很棒的漏洞靶场,所以就把该...

5058
来自专栏技术点滴

Flink架构、原理与部署测试一、架构二、原理三、库四、部署参考资料

Apache Flink是一个面向分布式数据流处理和批量数据处理的开源计算平台,它能够基于同一个Flink运行时,提供支持流处理和批处理两种类型应用的功能。

3761
来自专栏小巫技术博客

应用被强杀了怎么办

972
来自专栏进击的程序猿

MapReduce浅读MapReduce概要

几个小时要处理完TB的数据,但是这些程序一般都不是分布式系统人员开发的,使用起来因为一些分布式的系统问题,会非常的痛苦

993
来自专栏安富莱嵌入式技术分享

【RL-TCPnet网络教程】第21章 RL-TCPnet之高效的事件触发框架

本章节为大家讲解高效的事件触发框架实现方法,BSD Socket编程和后面章节要讲解到的FTP、TFTP和HTTP等都非常适合使用这种方式。实际项目中也推荐大家...

1134
来自专栏华章科技

成为大数据顶尖程序员,先过了这些Hadoop面试题!(附答案解析)

导读:在大数据开发岗位的需求下,工资待遇水涨船高,不少编程人员在面对职业瓶颈期的时候,会选择转编程方向发展。

792
来自专栏CSDN技术头条

变不可能为可能,Tachyon帮助Spark变小时级任务到秒

本文作者是Gianmario Spacagna和Harry Powell,Barclays的数据科学家。 集群计算和大数据技术已经取得了很多进展,不过现在很多大...

2028
来自专栏Golang语言社区

机器人 Go 语言库:Gobot

Gobot 是为机器人和物理计算所设计的一组 Go 语言库,提供在同一时间合并多个不同设备的简单且强大的解决方案。 package main import (...

9885
来自专栏安富莱嵌入式技术分享

【RL-TCPnet网络教程】第6章 RL-TCPnet底层驱动说明

本章节为大家讲解RL-TCPnet的底层驱动,主要是STM32自带MAC的驱动实现和PHY的驱动实现。

1832
来自专栏大数据学习笔记

Flink学习笔记:2、Flink介绍

2、Flink介绍 Some of you might have been already using Apache Spark in your day-to-...

4405

扫码关注云+社区

领取腾讯云代金券