专栏首页linjinhe的专栏LevelDB 完全解析(0):基本原理和整体架构

LevelDB 完全解析(0):基本原理和整体架构

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

这次打算将之前的文章和之后的笔记一起整理一下,成为一个系列文章——本文是本系列文章的第一篇。

LSM-Tree

Log Structured Merge Tree,简称 LSM-Tree。2006年,Google 发表了 BigTable 的论文。这篇论文提到 BigTable 单机上所使用的数据结构就是 LSM-Tree。 很多存储产品使用 LSM-Tree 作为数据结构,比如 Apache HBaseApache Cassandra,MongoDB 的 Wired Tiger 存储引擎,LevelDB 存储引擎,RocksDB 存储引擎等。 简单地说,LSM-Tree 的设计目标是提供比传统的 B-Tree/B+Tree 更好的写性能。LSM-Tree 通过将磁盘的随机写转化为顺序写来提高写性能 ,而付出的代价就是牺牲部分读性能、写放大(B-Tree/B+Tree 同样有写放大的问题)。

如何优化写性能

如果我们对写性能特别敏感,我们最好怎么做?—— Append only:所有写操作都是将数据添加到文件末尾。这样顺序写的性能是最好的,大约等于磁盘的理论速度(无论是 SSD 还是 HDD,顺序写性能都要明显由于随机写性能)。但是 append only 的方式会带来一些问题:

  • 不支持有序遍历。
  • 需要垃圾回收(清理过期数据)。

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

  • 存储系统的 WAL
  • 能知道明确的 offset 的查询,比如 Bitcask

如何优化读性能

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

  • 有序存储,比如 B-Tree/B+Tree。但是 B-Tree/B+Tree 会导致随机写。
  • 哈希存储 —— 不支持有序遍历,适用范围有限。

读写性能的权衡

如何获得接近 append only 的写性能,而又能拥有不错的读性能呢?以 LevelDB/RocksDB 为代表的 LSM-Tree 存储引擎给出了一个参考答案。原始的 LSM-Tree 可以参考论文。下面的讨论主要以 LevelDB 为例子。 LevelDB 的写操作(Put/Delete/Write)主要由两步组成:

  1. 写日志(WAL,顺序写)。
  2. 写 MemTable(内存中的 SkipList)。

所以,正常情况下,LevelDB 的写速度非常快。

内存中的 MemTable 写满后,会转换为 Immutable MemTable,然后被后台线程 compact 成按 key 有序存储的 SSTable(顺序写)。 SSTable 按照数据从新到旧被组织成多个层次(上层新下层旧),点查询(Get)的时候从上往下一层层查找,所以 LevelDB 的读操作可能会有多次磁盘 IO(LevelDB 通过 table cache、block cache 和 bloom filter 等优化措施来减少读操作的 I/O 次数)。 后台线程的定期 compaction 负责回收过期数据和维护每一层数据的有序性。在数据局部有序的基础上,LevelDB 实现了数据的(全局)有序遍历。

LevelDB 接口使用

LevelDB 提供的接口很简单,请参考官网文档

LevelDB 整体架构

LevelDB整体架构.png

上图简单展示了 LevelDB 的整体架构。

  1. MemTable:内存数据结构,具体实现是 SkipList。 接受用户的读写请求,新的数据会先在这里写入。
  2. Immutable MemTable:当 MemTable 的大小达到设定的阈值后,会被转换成 Immutable MemTable,只接受读操作,不再接受写操作,然后由后台线程 flush 到磁盘上 —— 这个过程称为 minor compaction。
  3. Log:数据写入 MemTable 之前会先写日志,用于防止宕机导致 MemTable 的数据丢失。一个日志文件对应到一个 MemTable。
  4. SSTable:Sorted String Table。分为 level-0 到 level-n 多层,每一层包含多个 SSTable,文件内数据有序。除了 level-0 之外,每一层内部的 SSTable 的 key 范围都不相交。
  5. Manifest:Manifest 文件中记录 SSTable 在不同 level 的信息,包括每一层由哪些 SSTable,每个 SSTable 的文件大小、最大 key、最小 key 等信息。
  6. Current:重启时,LevelDB 会重新生成 Manifest,所以 Manifest 文件可能同时存在多个,Current 记录的是当前使用的 Manifest 文件名。
  7. TableCache:TableCache 用于缓存 SSTable 的文件描述符、索引和 filter。
  8. BlockCache:SSTable 的数据是被组织成一个个 block。BlockCache 用于缓存这些 block(解压后)的数据。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LevelDB 完全解析(7):初始化

    options - 打开/创建 LevelDB 实例的配置参数。 dbname - 保存数据的目录名。 dbptr - 初始化成功的 LevelDB 实例保...

    linjinhe
  • LevelDB 完全解析(4):Manifest

    内容上,Manifest 文件保存了整个 LevelDB 实例的元数据,比如:每一层有哪些 SSTable。 格式上,Manifest 文件其实就是一个 lo...

    linjinhe
  • LevelDB 完全解析(6):Filter

    LevelDB 可以设置通过 bloom filter 来减少不必要的读 I/O 次数。

    linjinhe
  • LevelDB 完全解析(3):SSTable

    SSTable 全称 Sorted String Table,顾名思义,里面的 key-value 都是有序保存的。除了两个 MemTable,LevelDB ...

    linjinhe
  • LevelDB 完全解析(2):Log

    这里的 log 是指 Write Ahead Log。前面说了,LevelDB 写入的数据会先保存到 MemTable。为了防止宕机导致数据丢失,在将数据写入 ...

    linjinhe
  • LevelDB 完全解析(5):Cache

    在 LevelDB 中,block cache 和 table cache 都是基于 ShardedLRUCache 实现的。

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

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

    jaydenwen123
  • 【深度知识】LevelDB从入门到原理详解

    LevelDB是Google开源的持久化KV单机数据库,具有很高的随机写,顺序读/写性能,但是随机读的性能很一般,也就是说,LevelDB很适合应用在查询较少,...

    辉哥
  • 分布式——详解Google leveldb中的LMST细节

    LSMT是一个在分布式系统当中应用非常广泛,并且原理直观简单的数据结构。在上一篇文章当中我们进行了详细的讨论,有所遗忘或者是新关注的同学可以点击下方的链接回顾一...

    TechFlow-承志
  • 漫谈 LevelDB 数据结构(三):LRU 缓存( LRUCache)

    LRU 是工程中多见的一个数据结构,常用于缓存场景。近年来,LRU 也是面试中一道炙手可热的考题,一来工程用的多,二来代码量较少,三来涉及的数据结构也很典型。L...

    青藤木鸟
  • 谈一谈若干的K-V NoSQL应用:LevelDB、Redis、Tair、RockesDB

    NoSQL、尤其是key-value NoSQL在日常开发中扮演了非常重要的角色,除非对于关系型数据或者事务之类的有着非常强的诉求,不妨就根据业务特点试一下No...

    邹志全
  • LevelDB 完全解析(1):MemTable

    MemTable,顾名思议,就是内存表。每个 LevelDB 实例最多会维护两个 MemTable: mem_ 和 imm_。mem_ 可以读写,imm_ 只读...

    linjinhe
  • 漫谈 LevelDB 数据结构(一):跳表(Skip List)

    早对 LevelDB 有所耳闻,这次心血来潮结合一些资料粗略过了遍代码,果然名不虚传 —— 绝对是不世出的工艺品!如果你对存储感兴趣、如果你想优雅使用 C++、...

    青藤木鸟
  • Clickhouse 系列 - 番外 - LSM 算法

    在本系列的第三章中介绍了 clickhouse 通过 block 和 lsm 来减少磁盘读取的数据量。严谨的逻辑应该时 clickhouse 通过 lsm 算法...

    不会飞的小鸟
  • LevelDB:读操作

    前面写了两篇文章介绍 LevelDB 的整体架构和接口使用。这篇文章,我们从代码的角度看看 LevelDB 的设计与实现,先从读操作开始。

    linjinhe
  • 漫谈 LevelDB 数据结构(二):布隆过滤器(Bloom Filter)

    LevelDB 是一个单机的 KV 存储引擎,但没有使用传统的平衡查找树以平衡读写性能,而是使用了 LSM-tree 结构来组织数据,牺牲部分读性能来换取较高的...

    青藤木鸟
  • 既生 Redis 何生 LevelDB ?

    了解 Redis 的同学都知道它是一个纯内存的数据库,凭借优秀的并发和易用性打下了互联网项的半壁江山。Redis 之所以高性能是因为它的纯内存访问特性,而这也成...

    老钱
  • leveldb实现分析

    | 导语  leveldb是google开源的单机key-value存储引擎。基于Log-Structured-Merge Tree的实现。本文先介绍leve...

    腾讯Bugly
  • 秒级去重:ClickHouse在腾讯海量游戏营销活动分析中的应用

    导语 | 腾讯内部每日都需要对海量的游戏营销活动数据做效果分析,而活动参与人数的去重一直是一项难点。本文将为大家介绍腾讯游戏营销活动分析系统——奕星,在去重服...

    腾讯QQ大数据

扫码关注云+社区

领取腾讯云代金券