RocksDB原理与实现：基于LSM-Tree的高性能数据库系统

RocksDB原理与实现：基于LSM-Tree的高性能数据库系统

RocksDB是什么？

RocksDB是Facebook开源的一个高性能嵌入式数据库系统，采用C++编写。它专注于在服务器压力下充分发挥高速存储硬件的性能，主要作为数据持久化方案，不提供网络服务。RocksDB基于LevelDB开发，从LevelDB 1.5版本fork出来。

RocksDB解决了什么问题？

RocksDB主要解决了写多读少的场景下的性能问题，通过牺牲一定的读性能来大幅提升写性能。这种设计与MySQL InnoDB的B+树结构形成对比，后者更适合读多写少的场景。

如何实现的？

RocksDB的核心是LSM-Tree（Log-Structured Merge-Tree）数据结构，通过利用磁盘顺序IO来提升写性能。以下是RocksDB的关键组件和实现细节：

LSM-Tree

LSM-Tree的核心思想是通过磁盘顺序写入来优化写性能，适用于写多读少的场景，如日志系统、海量数据存储等。在实现过程中需要解决以下问题：

• 数据冗余问题
• 读性能优化
• 缓存数据结构选择
• 缓存刷盘策略
• 数据一致性保证

Memtable

Memtable是一个内存数据结构，用于存储尚未落盘的数据。写入数据时首先写入Memtable，读取时也先查询Memtable。当Memtable写满后会变为Immutable Memtable，即只读状态，然后创建新的Memtable继续接收写入。Immutable Memtable会异步落盘为SST文件，之后被删除。

Memtable默认使用SkipList数据结构，原因如下：

• SkipList查找下一个节点的时间复杂度为O(1)，适合实现Iterator功能
• 并发读写时，SkipList的锁粒度比红黑树小

落盘策略

RocksDB采用两种落盘策略：

• 定时刷新
• 阈值刷新

WAL（Write-Ahead Log）

WAL用于数据恢复，在出现宕机时可以恢复Memtable的数据。只有当Memtable中的数据落盘到SST文件后，才会删除对应的WAL日志。

SSTable（Sorted String Table）

每个Immutable Memtable都会落盘为一个SSTable文件。L0层可能有重复数据，不利于快速查找；L1~LN层会对重复数据进行合并，类似于时间轮算法，根据数据的冷热程度进行分层。

磁盘数据读性能的提升

• BlockCache：RocksDB在内存中缓存数据以提高读性能，支持LRUCache和ClockCache两种实现方式。
• 布隆过滤器：在SST每一层增加布隆过滤器，提高查找效率。布隆过滤器能确定一定不存在，但有误判率，可通过预期存储元素个数和误判率来控制。

LSM-Tree的三大问题

• 读放大：LSM-Tree最多可达7层，读性能相比B+树要差。
• 空间放大：所有写操作都是顺序写，无效数据不会被马上清理掉。
• 写放大：同一条数据可能多次写入磁盘，不同层级之间可能存在重复数据。

压缩策略

为了平衡读放大、空间放大和写放大，RocksDB提供了不同的合并算法策略，默认使用Leveled Compaction和Tiered Compaction。这些策略在内存和磁盘合并过程中都支持多线程处理。