专栏首页linjinhe的专栏LSM-Tree 的写放大写放大、读放大、空间放大RockDB 写放大简单分析参考文档

LSM-Tree 的写放大写放大、读放大、空间放大RockDB 写放大简单分析参考文档

本文缺少实际的实践经验。全部来自在网上的“道听途说”和自己的“胡思乱想”。

写放大、读放大、空间放大

基于 LSM-Tree 的存储系统越来越常见了,如 RocksDB、LevelDB。LSM-Tree 能将离散随机写请求都转换成批量顺序写请求(WAL + Compaction),以此提高写性能。但也带来了一些问题:

  • 读放大(Read Amplification)。LSM-Tree 的读操作需要从新到旧(从上到下)一层一层查找,直到找到想要的数据。这个过程可能需要不止一次 I/O。特别是 range query 的情况,影响很明显。
  • 空间放大(Space Amplification)。因为所有的写入都是顺序写(append-only)的,不是 in-place update ,所以过期数据不会马上被清理掉。

RocksDB 和 LevelDB 通过后台的 compaction 来减少读放大(减少 SST 文件数量)和空间放大(清理过期数据),但也因此带来了写放大(Write Amplification)的问题。

  • 写放大。实际写入 HDD/SSD 的数据大小和程序要求写入数据大小之比。正常情况下,HDD/SSD 观察到的写入数据多于上层程序写入的数据。

在 HDD 作为主流存储的时代,RocksDB 的 compaction 带来的写放大问题并没有非常明显。这是因为:

  1. HDD 顺序读写性能远远优于随机读写性能,足以抵消写放大带来的开销。
  2. HDD 的写入量基本不影响其使用寿命。

现在 SSD 逐渐成为主流存储,compaction 带来的写放大问题显得越来越严重:

  1. SSD 顺序读写性能比随机读写性能好一些,但是差距并没有 HDD 那么大。所以,顺序写相比随机写带来的好处,能不能抵消写放大带来的开销,这是个问题。
  2. SSD 的使用寿命和其写入量有关,写放大太严重会大大缩短 SSD 的使用寿命。因为 SSD 不支持覆盖写,必须先擦除(erase)再写入。而每个 SSD block(block 是 SSD 擦除操作的基本单位) 的平均擦除次数是有限的。

所以,在 SSD 上,LSM-Tree 的写放大是一个非常值得关注的问题。而写放大、读放大、空间放大,三者就像 CAP 定理一样,需要做好权衡和取舍。

RockDB 写放大简单分析

说明:RocksDB 支持多种 Compaction。下面分析的是 Level Style Compaction。

RocksDB 的写放大分析:

  • +1 - redo log 的写入
  • +1 - Immutable Memtable 写入到 L0 文件
  • +2 - L0 和 L1 compaction(L0 SST 文件的 key 范围是重叠的,出于性能考虑,一般尽量保持 L0 和 L1 的数据大小是一样的,每次拿全量 L0 的数据和全量 L1 的数据进行 compaction)
  • +11 - Ln-1 和 Ln 合并的写入(n >= 2,默认情况下,Ln 的数据大小是 Ln-1 的 10 倍,见 max_bytes_for_level_multiplier )。

所以,总的写放大是 4 + 11 * (n-1) = 11 * n - 7 倍。关键是 n 的取值。

假设 max_bytes_for_level_multiplier 取默认值 10,则 n 的取值受 L1 的大小和 LSM-Tree 的大小影响。 L1 的大小由 max_bytes_for_level_base 决定,默认是 256 MB。

默认情况下 L0 的大小和 L1 一样大,也是 256 MB。不过 L0 比较特殊,当 L0 的 SST 文件数量达到 level0_file_num_compaction_trigger 时,触发 L0 -> L1 的 comapction。所以 L0 的最大大小为 write_buffer_size * min_write_buffer_number_to_merge * level0_file_num_compaction_trigger

因此,RocksDB 每一层的默认大小为 : L0 - 256 MB L1 - 256 MB L2 - 2.5 GB L3 - 25 GB L4 - 250 GB L5 - 2500 GB

用户可以根据自己的场景需求调整上面的各个参数。

参考文档

本文参与 腾讯云自媒体分享计划 ,欢迎热爱写作的你一起参与!
本文分享自作者个人站点/博客:https://www.jianshu.com/u/96141c0d5c5c复制
如有侵权,请联系 yunjia_community@tencent.com 删除。
登录 后参与评论
0 条评论

相关文章

  • WiscKey:LSM-Tree 写放大优化WiscKey 简介WiscKey 带来的好处WiscKey 面临的问题和挑战参考文档

    WiscKey 的提出,主要是为了优化 LSM-Tree 的写放大问题。此前已经有不少论文讨论过这个问题,如 LSM-trie 和 PebblesDB,但是大部...

    linjinhe
  • Titan 的设计与实现

    Titan 是由 PingCAP 研发的一个基于 RocksDB 的高性能单机 key-value 存储引擎,其主要设计灵感来源于 USENIX FAST 20...

    PingCAP
  • HBase/TiDB都在用的数据结构:LSM Tree,不得了解一下?

    LSM Tree(Log-structured merge-tree)广泛应用在HBase,TiDB等诸多数据库和存储引擎上,我们先来看一下它的一些应用:

    Monica2333
  • lsm派系(不仅lsm tree)存储模型概述(下篇)

    这部分内容主要回答我们在文章开头提到的第二个问题。第二个问题展开其实是一连串的问题。例如:lsm派系难道只有lsm tree这一类存储模型吗?如果答案是否定的,...

    jaydenwen123
  • 设计数据密集型应用(3):Storage and Retrieval

    Hash Index 是一种相对简单的索引结构。几乎每一种程序设计语言都有提供内存数据结构 hash map/table 的标准库,比如 C++ 中的 std:...

    linjinhe
  • DB·洞见#2回顾 | 基于LSM-Tree存储的数据库性能改进

    LSM-Tree(Log Structured Merge Tree)是数据库领域内较高效的key-value存储结构,被广泛应用于工业界数据库系统,如经典的...

    腾讯云数据库 TencentDB
  • 《数据密集型型系统设计》LSM-Tree VS BTree

    本文为《数据密集型应用系统设计》的读书笔记第一部分第三章的笔记整理,也是个人认为的这本书第一部分最重要的内容。本文将会针对目前数据库系统两个主要阵营进行展开,分...

    阿东
  • 原创分享 TiDB 的列式存储引擎是如何实现的?

    TiDB 是一款分布式 HTAP 数据库,它目前有两种存储节点,分别是 TiKV 和 TiFlash。TiKV 采用了行式存储,更适合 TP 类型的业务;而 T...

    PingCAP
  • 一文了解数据库索引:哈希、B-Tree 与 LSM

    索引(Index)是帮助数据库系统高效获取数据的数据结构,数据库索引本质上是以增加额外的写操作与用于维护索引数据结构的存储空间为代价的用于提升数据库中数据检索效...

    王下邀月熊
  • ClickHouse和他的朋友们(5)存储引擎技术进化与MergeTree

    21 世纪的第二个 10 年,虎哥已经在存储引擎一线奋战近 10 年,由于强大的兴趣驱动,这么多年来几乎不放过 arXiv 上与存储相关的每一篇 paper。尤...

    老叶茶馆
  • DDIA 读书分享 第三章(上):LSM-Tree 和 B-Tree

    第二章讲了上层抽象:数据模型和查询语言。本章下沉一些,聚焦数据库底层如何处理查询和存储。这其中,有个逻辑链条:

    木鸟杂记
  • 联网数据库 IoTDB —— 存储引擎原理篇

    Apache IoTDB(物联网数据库)是一体化收集、存储、管理与分析物联网时序数据的软件系统。Apache IoTDB 采用轻量式架构,具有高性能和丰富的功能...

    麒思妙想
  • LevelDB 完全解析(0):基本原理和整体架构

    之前零零散散写过几篇和 LSM-Tree、LevelDB 有关的文章。之后也看了一些代码和论文,笔记也做了一些,但大都比较零乱、随意,没花功夫整理。

    linjinhe
  • 数据库选型时必知的存储引擎基础

    在评估和选型数据库的时候,人们往往将重点放在数据建模的灵活性,一致性保证,线性可伸缩性,容错性,低延迟,高吞吐量和易于管理等方面。但怎么才能评判出这些指标呢?很...

    ImportSource
  • LSM-tree 基本原理及应用

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

    Apache IoTDB
  • LotusDB 设计与实现—1 基本概念

    LotusDB 是一个基于 LSM Tree 进行设计,并结合 B+ 树优势的单机 KV 存储引擎,读写性能稳定、快速。

    roseduan
  • WiscKey —— SSD 介质下的 LSM-Tree 优化

    LSM-tree 是大数据时代一个经典的存储结构,是 Bigtable,Habse,LevelDB,RocksDB 等大数据存储的构建基础。LSM-tree 高...

    木鸟杂记
  • LSM简介

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

    linjinhe

扫码关注云+社区

领取腾讯云代金券