LevelDB知识整理与总结

发表于 分类于 ， 阅读次数： 本文字数： 7.5k

前言

此前区块链实习时，接触的数据库，碍于2023年事情较多，一直未总结。

本文将整理LevelDB相关知识，并进行总结。

概述

在区块链中，谈到数据库就不得不提LevelDB，比特币、以太坊等都使用LevelDB作为底层数据库。

LevelDB的前身是Google的Bigtable——大数据三驾马车之一。Bigtable由Google在2006发表的Bigtable: A Distributed Storage System for Structured Data论文中提出，是一个分布式的高性能KV数据库，但Bigtable的具体实现并未开源。LevelDB可以看作单机版的Bigtable，它由Bigtable的作者共同完成，并被Google开源。

LevelDB是一个单机KV数据库，采用LSM(Log Structured Merge)结构，具有很高的写性能和较高的读性能，适用于写多读少的情况。LSM的基本思想是：顺序写代替随机写、延时进行归并处理。

参考：https://leveldb-handbook.readthedocs.io/zh/latest/basic.html

架构

1

包含以下几个重要组件：

  • MemTable：内存中的有序的存储区，底层使用 跳表 数据结构。写操作先写入MemTable，达到阈值后，转换为Immutable MemTable。
  • Immutable MemTable：内存中的只读的存储区，会被后台线程异步地持久化到磁盘中，形成一个sstable。
  • log：预写式日志**WAL(Write-Ahead Logging)**，类似于MySQL的undolog+redolog，用于防止写入内存的数据因进程异常、系统掉电等情况而丢失。LevelDB在写MemTable之前，会将所有的写操作写到log文件中。LevelDB在重启后，会从log文件中恢复MemTable数据。
  • sstable(Sorted String Table)：磁盘数据存储文件。SST文件内数据有序，且不可修改。LevelDB磁盘数据分为 Level0 到 LevelN 多层，每一层包含多个 SST 文件。Level0 中的SST文件直接由 Immutable Memtable转换而来，Level0中的不同SST文件之间可能存在交集，非严格有序。剩余每一层都是有序的，数据由上一层进行 Compaction 得到。
  • manifest：用于版本控制。
    • LevelDB中的 版本（version） 记录着每一层中所有文件的元数据，包括文件大小、最小key值和最大key值。
    • 每次Compaction完成，LevelDB都会创建一个新版本，并记录变化的内容（增量），比如：新增哪些sst文件、删除哪些sst文件等等，manifest文件就是用来记录这些变化信息的。
  • current：记录当前manifest的文件名。

写

1

流程：

  1. 先写log。
  2. 再写入MemTable。

关键点：

  • 支持的写操作：Put、Delete，同时支持批量写。
  • 快照：将键值写入MemTable时，LevelDB会对key进行特殊编码，格式如下。其中，序列号（sequence number） 是累加的，最大的表示最新。
    1
  • 并发问题（写-写冲突）：LevelDB同一时间只允许一个写入操作（锁）。当发生并发写入时，为了提高性能，LevelDB会将多个写入合并成一个批量写入。
  • 原子性：先写日志，写入成功，就代表操作完成。若写日志到一半，进程退出，重启后会删除异常日志。
  • 持久性：只要写日志成功，就算持久化。数据库重启后，会根据日志恢复MemTable。

读

1

流程：

  1. 读MemTable；

  2. 读Immutable MemTable；

  3. 按Level0~LevelN的顺序，在每一层的sstable文件中查找指定的key，若搜索到符合条件的数据项，结束查找，否则返回Not Found错误，表示数据库中不存在指定的数据。

    • LevelDB在每一层sstable中查找数据时，都是按序依次查找sstable的。

    • 0层的文件比较特殊。由于0层的文件中可能存在key重合的情况，因此在0层中，文件编号大的sstable优先查找。理由是文件编号较大的sstable中存储的总是最新的数据。

    • 非0层文件，一层中所有文件之间的key不重合，因此LevelDB可以借助sstable元数据（一个文件中最小与最大的key值）进行快速定位（二分），每一层只需要查找一个sstable文件的具体内容。

关键点：

  • 支持的读操作：Get和快照Get，两者的本质都是读快照。
  • 快照：在LevelDB中，用户对同一个key的若干次修改（包括删除）是以维护多条数据项的方式进行存储的（直至Compaction时才会合并成同一条记录），每条数据项都会被赋予一个序列号，代表这条数据项的新旧状态。序列号就相当于快照，读数据时可指定序列号，即指定快照。
  • 隔离性（并发读写）：通过快照读保证。

MemTable

内存中的数据结构，由跳表（详情可参考本人数据结构笔记）实现。写入操作时，写入的是MemTable。MemTable达到阈值后，转换为Immutable MemTable，同时生成一个新的MemTable。

Immutable MemTable是只读的，它一旦生成，很快就会被异步线程持久化到磁盘上（minor compaction），转换成Level0中的一个SST文件。这个过程需要耗费一定的时间，而如果MemTable数据量增长过快，马上又满了，写线程就会阻塞，并等待异步线程持久化Immutable MemTable完成。这是 LevelDB 的卡顿点之一，也是未来 RocksDB 的优化点。

SST

物理结构：为了提高整体的读写效率，一个sstable文件按照固定大小进行块划分，默认每个块(block)的大小为4KB。

1

逻辑结构（如上图）：

  • data block：存储键值对数据。由于sstable中所有的键值对都是严格按序存储的，为了节省存储空间，LevelDB并不会为每一对键值对都存储完整的key值，而是仅存储与上一个key非共享的部分。
  • filter block：存储布隆过滤器。在查询data block中的内容之前，LevelDB首先根据filter block判断指定的data block中是否有需要查询的数据。
  • meta index block：用来存储filter block在整个sstable中的索引信息。
  • index block：存储所有data block的索引信息。index block包含若干条记录，每一条记录对应一个data block的索引信息。记录中包含：该data block中的最大key值、该data block在sstable中的偏移量、该data block的大小。如此设计是为了，可以快速定位目标数据在哪个data block中。
  • footer：存储meta index block与index block在sstable中的索引信息。

写：只有在Compaction时，才会创建SST文件，创建后不可修改。

读：

  1. 读取元数据，包括footer、meta index block、index block、filter block等。
  2. 根据index block找到对应的data block。
  3. 根据filter block判断数据是否存在于data block中。

特性：

  • 只读。
  • 并发访问友好，因为只读。
  • 快速查找。

Compaction

minor compaction

1

将内存中imutable memtable持久化为磁盘Level0中的一个sstable文件。

每次minor compaction结束后，都会生成一个新的sstable文件，也意味着Leveldb的版本状态发生了变化，会进行一个版本的更替。

值得注意的是，minor compaction是一个时效性要求非常高的过程，要求其在尽可能短的时间内完成，否则就会堵塞正常的写入操作，因此minor compaction的优先级高于major compaction。当进行minor compaction的时候有major compaction正在进行，则会首先暂停major compaction。

major compaction

示例（如下图）：Level0层中浅蓝色的三个sstable文件，加上Level1层中的绿色的sstable文件，四个文件进行了合并，输出成两个按序组织的新sstable文件。

1

major compaction触发条件：

  1. 第0层文件数超过上限。
    • 限制0层大小或文件数量，是因为0层文件并非严格排序，进行读操作时，需遍历0层所有文件。对0层大小进行限制，是为了提高读取效率。
  2. 第i(i≥i) 层大小超过10^i MB。
    • 为什么要限制≥1层的大小？假设LevelDB只有0层和1层，那1层文件的个数会越来越多或者总数据量越来越大。而由于0层文件乱序，且0层文件key的取值范围较大，导致每一次0层文件与1层文件进行compaction时，所输入的1层文件数量将非常庞大。所以不仅要限制0层大小，每一层大小同样需要进行控制，使得每次进行major compaction时，IO开销尽量保持常量。
  3. 当某个文件无效读取的次数过多（错峰合并）。
    • 存在的问题：假设0层文件完成合并之后，1层文件同时达到了数据上限，则立马需要进行合并。更加糟糕的是，0-n层的文件同时达到了合并的条件，每一层都需要进行合并。
    • 解决方法：若某个文件的查询次数过多，且查询在该文件中不命中, 那么这种行为就可以视为无效的查询开销，这种文件就可以进行错峰合并。

major compaction过程：

  1. 寻找合适的输入文件。
    • 对于第1、2种触发条件，采用轮转方法选择i层输入文件，记录了上一次该层合并的文件的最大key，下一次则选择在此key之后的首个文件。
  2. 根据key重叠情况扩大输入文件集合。
    • 根据第i层待合并的sstable文件，找第i+1层中key范围重叠的sstable文件，再根据两层的输入文件，找第i层中key范围重叠的sstable文件。
  3. 多路归并。
    • 将所有输入文件中的数据按序整理，而后输出若干个第i+1层的sstable文件。
    • 在整理的过程中，需要将冗余的数据进行清理，即同一条数据的多个版本，只保留最新的那一份。

一次major compaction的过程其本质是一个多路归并的过程，存在大量的磁盘读写开销，显然这是一个严重的性能瓶颈。

同时，当用户写入的速度始终大于major compaction的速度时，就会导致0层的文件数量还是不断上升，用户的读取效率持续下降。所以LevelDB 中规定：

  • 当0层文件数量超过SlowdownTrigger时，写入的速度主要减慢；
  • 当0层文件数量超过PauseTrigger时，写入暂停，直至major compaction完成；

由于LevelDB 内部进行Compaction时有trivial move优化，且根据内部的文件格式组织，用户在使用LevelDB 时，可以尽量将大批量需要写入的数据进行预排序，利用空间局部性，尽量减少多路合并的IO开销。

缓存

LevelDB中使用了一种基于LRUCache的缓存机制，用于缓存：

  • 已打开的sstable文件对象和相关元数据。
  • sstable中的data block的内容。

结构：

1

其中Hash Table是基于论文《Dynamic-Sized Nonblocking Hash Table》实现的，它可以实现resize的过程中不阻塞其他并发的读写请求。

哈希表扩张过程中，最小的封锁粒度为哈希桶级别。当有新的读写请求发生时，若被散列之后得到的哈希桶仍然未构建完成，则“主动”进行构建，并将构建后的哈希桶填入新的哈希表中。后台进程构建到该桶时，发现已经被构建了，则无需重复构建。

版本控制

LevelDB每次Compaction，都会从一个版本升级成另外一个版本。

版本（version） 指整个LevelDB数据库的版本，而非具体数据的版本，相当于整个LevelDB的快照。本质是一个文件，记录着每一层中所有文件的元数据，包括有哪些文件、文件大小、最小key值和最大key值等。LevelDB采用了增量式的记录方式，通过Manifest文件记录版本变化信息。

1

一个Manifest文件中，包含了多条Session Record。

  • 第一条Session Record记载了当时LevelDB的全量版本信息。
  • 后续每条Session Record则记录了从上一个版本到该版本的变化信息，包括：新增的sstable文件、删除的sstable文件、已持久化数据项中最大的序列号等等。

1

当LevelDB进行Compaction时，会创建一条Session Record添加到Manifest文件末尾。

  • 原子性体现：Compaction完成标志为Manifest文件中写入了一条session record。在此之前，即便某些文件写入失败导致进程退出，数据库重启启动时，仍然能够恢复到崩溃之前正确的状态，并将这些无用的sstable文件删除，重新进行compaction动作。
  • 一致性体现：LevelDB状态变更的操作都是以version更新为标记，而version更新是整个流程的最后一步，因此数据库必然都是从一个一致性的状态变更到另外一个一致性的状态。

当LevelDB重启时：

  1. 读取Current指向的Manifest文件，并依次执行Manifest中的Session Record，生成一个新的版本。
  2. 创建新Manifest，第一个Session Record为新版本的快照。
  3. 删除过期的Manifest。
  4. 将新版本设置为数据库的当前版本。

总结

从读写性能的角度进行分析总结

问题1：在常见的数据库中，写数据到磁盘时，都是采用随机写而非顺序写。以在纸上写文章为例，顺序写就是接着文章末尾的空白继续写，随机写则是对文章已写内容进行修改，不管是插入、删除还是修改，肯定更加麻烦。向硬盘中写数据也是同理，随机写会导致更多的碎片化、更多的垃圾回收和数据迁移开销。因此，不管是机械硬盘或固态硬盘，随机写性能低于顺序写。

为了提高写性能，LevelDB用顺序写代替随机写。具体的写数据流程：先写入内存，而后异步地被顺序写入磁盘。

问题2：采用顺序写，磁盘中数据往往是无序的，对读非常不友好。

为了保障读性能，LevelDB做了以下工作：

  1. 通过Compaction将无序数据变为有序。

    • minor compaction将MemTable转换为level0层中的sstable文件，文件内部数据有序。但由于level0层sstable文件序列非严格排序，读数据的时候需遍历，性能并不高。因此，level0层不能太大，且还需要转换为有序的层。

    • major compaction则负责将i层合并为i+1层中有序的sstable文件序列的一部分。由此，保证≥1层都是有序的，而有序数据可采用二分等方式查找，读性能显著提升。

    • 基于Compaction操作，基本决定了LevelDB的读流程：先读内存，而后依次读磁盘各层。

  2. 提高并发读写性能。

    • 采用快照读，避免读写冲突，通过数据项的序列号实现。在写入磁盘后，数据项会有一个序列号，序列号越大表示数据越新。读数据都采用快照读方式，默认读最大的序列号，也可以自己指定序列号。

问题3：由于Compaction过程会引起大量磁盘IO，可能会影响正常的写操作。

为了提高Compaction性能，LevelDB做了以下工作：

  1. 提高minor compaction性能（minor compaction会直接影响数据写入内存的速度）。将内存数据直接转换为level0层中的一个sstable文件，而不与level0层文件进行合并、排序。因此，level0层的sstable序列是非严格排序的。
  2. 提高major compaction性能。由于major compaction需要将i层sstable与i+1层的部分sstable一起归并排序，且i层的key范围可能较大。为了防止输入的i+1层sstable过多、数据量过大，i+1层的大小和sstable数量要尽可能合理。因此，LevelDB各层大小逐步递增。

从ACID等特性角度进行分析总结

对于写操作：

  • 原子性：先写WAL日志，再写内存。只要写入日志完成，就表示写入操作成功。
    • 若写日志完成，写内存未完成时，进程退出，重启后会重新执行日志记录，写入操作终会成功。
    • 若写日志未完成时，进程退出，重启后会删除异常日志，相当于回滚。
  • 持久性：只要写WAL日志完成，就算持久化成功。数据库重启后，会根据日志恢复MemTable。
  • 隔离性（写-写冲突）：写入内存时，会加锁，同一时间只允许一个写操作。同一时间段的多个写操作会合并成一个批量写操作，以此提高并发写的性能。

对于读操作：

  • 隔离性：
    • 读-写冲突（读内存数据时）：MemTable自带读写锁机制（阅读goleveldb源码时发现），不会与写内存操作冲突。
    • 读-Compaction冲突（读磁盘数据时）：
      1. sstable文件是只读的。每次Compaction都只是对若干个sstable文件进行多路合并，然后创建新的sstable文件，不会影响对某个sstable文件的读操作。
      2. 快照读。读都是基于当前最新序列号或指定序列号，而Compaction只会生成新序列号，不会修改旧序列号的数据，即不会与读操作冲突。
      3. 采用引用计数来控制删除行为。当Compaction完成后试图去删除某个sstable文件，会根据该文件的引用计数（是否存在对应的读操作）作适当的删除延迟，即需要等待至该文件的计数为0才真正进行删除。
      4. 版本控制。Compaction完成后，才会更新LevelDB版本，比如写入数据库元数据。在此期间，读操作都基于旧版本文件进行，不受Compaction操作影响。

对于Compaction操作：

  • 原子性：Compaction完成后，会向Manifest文件写入一条session record。
    • 若写入完成，则代表Compaction操作成功。
    • 若写入完成之前，进程退出，重启后会基于Manifest文件回滚到Compaction之前的正确状态，无效的sstable文件将被删除。
  • 一致性：LevelDB状态变更以version更新为标记，而version更新是Compaction操作的最后一步。因此，数据库必然都是从一个一致性的状态变更到另外一个一致性的状态。
    • 如果在写入Manifest之后、更新version之前，进程结束，重启后会基于Manifest文件得到一个新的、正确的版本，状态依旧一致。