>

字数 727 阅读 12 评论 6

背景知识

随着

LevelDB 使用 LSM-Tree 来作为存储数据结构，极大得提升了写性能。我们知道，MySQL 这种数据库的存储引擎使用了 B+ 树来持久化数据, B+ 树是一个索引树, 可以说是同时考虑了读写均衡, 其结构上对树高进行了优化, 搜索耗时相比 AVL 树降下来. 然而问题是 “对一个随机读优化的排序结构执行随机写是有很大开销的”, 所以对那些需要高频写操作的系统来讲, B+ 树作为存储结构可能并不合适.

LSM-Tree 则更适合需要高频写的场景。它是一种类似日志的数据结构, 它将随机写变为顺序写, 核心思想是:

  • 对变更进行批量 & 延时处理
  • 通过归并排序将更新迁移到硬盘上

LSM-Tree 全称是 “Log Structured-Merge Tree”，最早在 1996 年由 麻省波斯顿大学的 Patrick O’Neil 及其他 3 个研究者发表的论文 The Log-Structured Merge-Tree (LSM-Tree) 中被设计出来。

Log-Structured File System

要理解 Log Structured-Merge Tree 是什么原理，我们需要先回到 Log Structured 到底是什么数据结构，实际上，它最早是由 Berkeley 研究人员（Mendel Rosenblum & John Ousterhout）在 1991 年发表的论文 [1992SOSP-The Design and Implementation of a Log-Structured File System][] 中提出并实现，这篇论文是日志结构文件系统的鼻祖，其目的就是系统的写瓶颈:

The fundamental idea of a log-structured file system is to improve write performance by buffering a sequence of file system changes in the file cache and then writing all the changes to disk sequentially in a single disk write operation.

核心思想就是使用顺序写(追加)替代随机写，因为顺序写不需要多次寻址, 速度能达到硬盘理论传输速度, 而随机写则受限于硬盘寻址速度.

威斯康辛大学的重量级教授 Remzi Arpaci-Dusseau 出版了一本操作系统的书，叫做 “Operating Systems: Three Easy Pieces”，其在 [“Log-structured File Systems”][] 一章中详细介绍了 LFS 的原理，有兴趣的可以详细查看，我在另一篇介绍 LFS 的文章中根据其内容进行简要的介绍和总结。

LSM-Tree

LSM 被设计来提供比传统的 B+ 树或者 ISAM 更好的写操作吞吐量，通过消去随机的本地更新操作来达到这个目标。

LSM 是当前被用在许多产品的文件结构策略：BigTable, Dynamo, HBase, Cassandra, LevelDB/RocksDB, SQLite,甚至在 MongoDB 3.0 中也带了一个可选的 LSM 引擎（Wired Tiger 实现的）

SkipList

源码分析

1) Put/Get

2) Log format

3) Insert & Read a record

4) Multi-Level SSTable

5) SSTable Merge - Minor/Major Compaction

6) VersionSet, VersionEdit

7) Format of SSTable

1、版本控制 VersionEdit

参考：
https://draveness.me/bigtable-leveldb

1992SOSP-The Design and Implementation of a Log-Structured File System
Log-structured File Systems
LSM-based Storage Techniques: A Survey
Stupid File Systems Are Better