从零实现LevelDB 1. 日志结构合并树和LevelDB介绍

#C++##golang##项目##基础架构工程师##数据库#

在本节，我们将会了解：

1. LSM-Tree介绍及优缺点
2. 基于LSM-Tree实现的LevelDB介绍及组件

在如今的大数据时代，高效的数据存储与查询技术对于各种应用至关重要。目前主流存储的数据结构包括B树(B Tree)、日志结构合并树（Log-Structured-Merge-Tree, LSM-Tree）等。其中，LSM-Tree凭借着其优越的写性能、高空间利用率、简化的并发控制和奔溃恢复机制而被广泛应用于各种NoSQL系统，包括BigTable、Cassandra、LevelDB、RocksDB等在内。而LevelDB作为LSM-Tree实现的一个经典作品。在本节，我们将会对LSM-Tree和LevelDB进行一个概览。

LSM-Tree介绍

LSM-tree是O'Neil、Cheng等人在1996年提出的一种新型的磁盘数据结构，用以解决写多读少的使用场景。

它利用了磁盘顺序顺序写速度快于随机写的特性，将大量的磁盘随机写操作转换为批量顺序写，从而实现写入性能的提升。

LSM-tree由两个树状组件C0树和C1树组成，C0树是一个完全驻留在内存中的较小组件，C1树则是一个驻留在磁盘上的较大组件。

插入时首先插入到C0树中，当C0树达到阈值大小时，会触发一个合并过程，将C0树的一部分与C1树归并，归并仅有顺序写，归并完成后将结果写回磁盘。

LevelDB介绍

LevelDB是谷歌的传奇工程师Sanjay Ghemawat和Jeff Dean实现的一个LSM-tree开源存储引擎，基于C++实现，凭借着其优秀的设计风格和代码实现，被认为是提高编程能力、入门存储的最好项目之一。

在本节，我们将对LevelDB的整体架构、主要操作流程做一个简单介绍，以便在后文实现时有整体的概念。

架构介绍

LevelDB由多个重要的组件组成，包括驻留内存的Memtable，驻留在磁盘的SStable，用以版本控制的Current、Manifest文件，用以实现原子性的Log模块以及压缩数据的Compaction模块等组件。

MemTable：内存中的数据结构，用于暂存新写入的数据。它通常由一个有序的数据结构实现，如跳表（Skip List）、红黑树或平衡二叉搜索树，在LevelDB中由跳表实现。MemTable又分为Mutable MemTable和Immutable MemTable，Immutable MemTable为不可修改状态。在LevelDB中，Mutable MemTable用以暂存用户写入的数据，当Mutable MemTable容量达到阈值时，会将Mutable MemTable转换为Immutable Memtable并写入SST文件，同时，LevelDB会创建一个新的Mutable MemTable接收用户数据。

SST文件：Sorted String Table(简称SST)是LSM树在磁盘上持久化存储的一种有序数据结构。在LevelDB中，SST文件分布在Level 0到Level N多个层级上，每一层级包含若干个SST文件，层级越高，SST文件也越多。其中，Level0的SST文件由Immutable Memtable直接Flush到磁盘，由于是直接Flush，没有做有序合并操作，因此，Level 0的SST文件虽然内部有序，但文件与文件之间很有可能产生重叠。Level 1到Level N层级的SST文件则是通过合并上一层级和当前层级的SST文件来生成的。合并会确保新生成的SST文件内部数据有序，且同一层级的SST文件之间互不重叠。

Log：在将数据写入Memtable之前，会写入到日志中，以确保数据的可靠性和一致性。日志采用追加的形式，所以具有较高的写入速度。当系统发生宕机时，可以通过WAL来恢复未提交到磁盘的数据。

Manifest文件： 记录了LevelDB中的元信息，包括SST文件在不同层级的分布、最大最小key等。

Current文件: 记录了当前Manifest的文件名，用以在LevelDB启动时找到Manifest文件。

Compaction：合并操作，用于将多个SSTable文件合并成一个新的SSTable文件。合并操作可以删除过期数据或已经被更新的数据，减少存储空间的浪费。同时，合并操作还可以减少SSTable文件的数量，提高读取效率。

写(write)

顺序写 VS 随机写

在介绍写入时，我们需要先了解为什么顺序写比随机写更快。

以传统的机械硬盘(HDD)为例，HDD是一种标准的“唱片机结构”，当用户要写入/读取数据时，HDD要将磁头移动到指定的磁道（寻道时间），并等待磁头到数据的起始位置（旋转等待时间），如果每个数据都在不同位置，那么我们就会看到每读取一个数据磁头疯狂地在不同的磁道上移动，这就是随机IO所带来的问题，如果数据在不同的位置，每次读取数据都要增加寻道时间和旋转等待时间，数据量越大，由于寻道时间和旋转等待时间所累积带来的时间代价也越大。

所以如果能将随机IO转换成顺序IO，那么写入/读取数据时，则只需要一次的寻道时间和旋转等待时间。假设有n条数据，减少的时间为(n-1)*(寻道时间+旋转等待时间)。

除了HDD，磁盘还有一种存储介质——固态硬盘(SDD)。SDD是一块支持随机寻址的存储芯片，理论上随机寻址与顺序寻址的速度是一样是，但由于存储介质的问题，随机IO仍然比顺序IO更慢，如下图。

上图是顺序IO和随机IO在现代SSD设备上的表现对比。可以看到，哪怕是SSD，顺序IO仍然比随机IO更快，即顺序写快于随机写。

因此，不管是HDD还是SDD，顺序IO都比随机IO更快。

写流程

在LevelDB中，写操作，除了我们传统熟知的Put(key,value)，删除(Delete)也是一种特殊的写操作。

在删除时，会将删除对象的标识置为删除(kTypeDeletion)，然后再写入该条目，表示该数据已被删除。后续读到删除标识的数据时，即明白该数据已被删除。

在LevelDB中，有一个全局序号，越大的序号代表数据越新。当用户写入数据时，LevelDB会将用户传入的数据以及LevelDB中的序号组装成内部使用的InternalKey格式再写入。

同时，为了提高批量写入的效率和达到写入的原子性，写入的数据都会封装成WriteBatch对象。我们会在后文对InternalKey和WriteBatch进行了解和实现。

获取(Get)

简单来说，Get(user_key)就是要找到user_key相同，同时是最新(序号最大)的数据。同时，LevelDB支持快照(snapshot)功能，snapshot其实就是一个序号，支持让用户找到序号之后的数据。

因为数据总是先写入MemTable，所以在读取数据时首先要读取MemTable，如果MemTable未找到，再依次从Immutable Memtable、Level 0的SST文件、Level 1的SST文件...依次寻找。

由于Manifest记录了各层的SST文件以及文件的边界（最大最小key），所以可以快速的知道某个key是否处于SST文件的边界内。

压缩(Compaction)

压缩分为MinorCompaction和MajorCompaction。Immutable Memtable写入Level 0的SST文件的过程称为MinorCompaction，而Level 0到Level N之间的压缩则是MajorCompaction。

LSM的优缺点

虽然LSM-Tree能将离散的随机写请求都转换成批量的顺序写请求（WAL + Compaction），提高了写入的性能。但也带来了一些问题：

1. 读放大（Read Amplification）：数据库实际从磁盘读取的数据大小与返回给用户的数据大小之比。

LSM树中，数据可能分布在多个层次的SST文件中。所以当数据不在内存时，查找数据需要从Level 0的SST文件一直往下层寻找，直到找到数据之前，这个多层查找的过程会产生许多次无效的查询，这就是读放大的原因。

1. 写放大（Write Amplification）：数据库实际从磁盘写入的数据大小与用户写入的数据大小之比。

压缩（Compaction）是LSM树中的一个重要环节，用于将多个SSTable文件（或内存中的memtable）合并成一个或多个新的、有序的SSTable文件。在合并过程中，即使某些数据没有发生变化，也可能需要被读取、排序和重新写入磁盘，这会导致一个数据会在磁盘中多次写入，这是写放大的原因。

上图是数据总大小为1GB和10GB，键大小为16B，值大小为1KB时，读放大和写放大的比例。可以看到，随着数据量的增加，写和读的放大问题越来越严重。

总结

总的来说，LSM-Tree通过牺牲了一部分查询性能，换取了较高的写入性能, 但同时也带来了写放大、读放大的挑战。因此，在应用到实际场景之前，要充分权衡它们的利弊问题。

参考文献

[1]. Patrick O’Neil, Edward Cheng, Dieter Gawlick, and Elizabeth O’Neil. 1996. The log-structured merge-tree (LSM-Tree). Acta Inf. 33, 4 (Jun 1996), 351–385. https://doi.org/10.1007/s002360050048

[2]. Chen Luo and Michael J. Carey. 2019. LSM-based storage techniques: a survey. The VLDB Journal 29, 1 (Jan 2020), 393–418. https://doi.org/10.1007/s00778-019-00555-y