LevelDB 基本概念

LevelDB 是一个由 Google 公司所研发的 K-V 存储嵌入式数据库管理系统编程库，以开源的 BSD 许可证发布。其作为 LSM Tree 的经典实现，具有很高的随机写，顺序读/写性能，但是随机读的性能很一般，也就是说，LevelDB很适合应用在查询较少，而写很多的场景。

为什么需求K-V数据库？

K-V 数据库主要用于存取、管理关联性的数组。关联性数组又称映射、字典，是一种抽象的数据结构，其数据对象为一个个的 key-value 数据对，且在整个数据库中每个 key 均是唯一的。

随着近年来互联网的兴起，云计算、大数据应用越来越广泛，对于数据库来说也出现了一些需要面对的新情况：

数据量呈指数级增长，存储也开始实现分布式。
查询响应时间要求越来越快，需在1秒内完成查询操作。
应用一般需要 7 × 24 小时连续运行，因此对稳定性要求越来越高，通常要求数据库支持热备份，并实现故障下快速无缝切换。
在某些应用中，写数据比读数据更加频繁，对数据写的速度要求也越来越高。
在实际应用中，并不是所有环境下的数据都是完整的结构化数据，非结构化数据普遍存在，因此如何实现对灵活多变的非结构化数据的支持是需要考虑的一个问题。

正是在上述情况的催生下，2010年开始兴起了一场 NoSQL 运动，而 K-V 数据库作为 NoSQL 中一种重要的数据库也日益繁荣，因此催生出了许多成功的商业化产品，并得到了广泛应用。

BigTable与LevelDB

早在 2004 年，Google 开始研发一种结构化的分布式存储系统，它被设计用来处理海量数据，通常是分布在数千台普通服务器上的 PB 级的数据——这一系统就是风靡全球的 Bigtable。

2006 年，Google 发表了一篇论文——《Bigtable: A Distributed Storage System for StructuredData》。这篇论文公布了 Bigtable 的具体实现方法，揭开了 Bigtable 的技术面纱。Bigtable 虽然也有行、列、表的概念，但不同于传统的关系数据库，从本质上讲，它是一个稀疏的、分布式的、持久化的、多维的排序键-值映射。

虽然 Google 公布了 Bigtable 的实现论文，但 Bigtable 依赖于 Google 其他项目所开发的未开源的库，Google 一直没有将 Bigtable 的代码开源。然而这一切在 2011 年迎来了转机。Sanjay Ghemawat 和 Jeff Dean 这两位来自 Google 的重量级工程师，为了能将 Bigtable 的实现原理与技术细节分享给大众开发者，于2011年基于 Bigtable 的基本原理，采用 C++ 开发了一个高性能的 K-V 数据库——LevelDB。由于没有历史的产品包袱，LevelDB 结构简单，不依赖于任何第三方库，具有很好的独立性，虽然其有针对性地对 Bigtable 进行了一定程度的简化，然而Bigtable的主要技术思想与数据结构均在 LevelDB 予以体现了。因此 LevelDB 可看作 Bigtable 的简化版或单机版。

特点

优点：

key 与 value 采用字符串形式，且长度没有限制。
数据能持久化存储，同时也能将数据缓存到内存，实现快速读取。
基于 key 按序存放数据，并且 key 的排序比较函数可以根据用户需求进行定制。
支持简易的操作接口 API，如 Put、Get、Delete，并支持批量写入。
可以针对数据创建数据内存快照。
支持前向、后向的迭代器。
采用 Google 的 Snappy 压缩算法对数据进行压缩，以减少存储空间。
基本不依赖其他第三方模块，可非常容易地移植到 Windows、Linux、UNIX、Android、iOS。

缺点：

不是传统的关系数据库，不支持SQL查询与索引。
只支持单进程，不支持多进程。
不支持多种数据类型。
不支持 C/S 的访问模式。用户在应用时，需要自己进行网络服务的封装。

应用场景

LevelDB主要应用于查少写多的场景，如：

常见的 Web 场景，可以存储用户的个人信息资料、对文章或博客的评论、邮件等。
具体到电子商务领域，可以存储购物车中的商品、产品类别、产品评论。
存储整个网页，其将网页的 URL 作为 key，网页的内容作为 value。
构建更为复杂的存储系统，如日志系统、缓存、消息队列等。
……

RocksDB

RocksDB 是基于 LevelDB 开发的，并保留、继承了 LevelDB 原有的基本功能，也是一个嵌入式的 K-V 数据存储库。RocksDB 设计之初，正值 SSD 硬盘兴起。然而在当时，无论是传统的关系数据库如 MySQL，还是分布式数据库如 HDFS、HBase，均没有充分发挥 SSD 硬盘的数据读写性能。因而 Facebook 当时的目标就是开发一款针对 SSD 硬盘的数据存储产品，从而有了后面的 RocksDB。RocksDB 采用嵌入式的库模式，充分发挥了 SSD 的性能。

为什么要基于LevelDB实现RocksDB？

一般而言，数据库产品有两种访问模式可供选择。一种是直接访问本地挂载的硬盘，即嵌入式的库模式；另一种是客户端通过网络访问数据服务器，并获取数据。假设 SSD 硬盘的读写约 100 μs，机械硬盘的读写约 10 ms，两台 PC 间的网络传输延迟为 50 μs。可以分析得知，如果在机械硬盘时代，采用 C/S 的数据服务模式，客户端进行一次数据查询约为 10.05 ms，可见网络延迟对于数据查询速度的影响微乎其微；而在 SSD 硬盘时代，客户端进行一次数据查询约为 150 μs，但与直接访问 SSD 硬盘相比，整体速度慢了 50%，因而直接影响了整体性能。正是在这样的背景下，Facebook的工程师们选择了 LevelDB 来实现 RocksDB 的原型。

RocksDB 使用了一个插件式的架构，这使得它能够通过简单的扩展适用于各种不同的场景。插件式架构主要体现在以下几个方面：

不同的压缩模块插件：例如 Snappy、Zlib、BZip 等（LevelDB 只使用 Snappy）。
Compaction 过滤器：一个应用能够定义自己的 Compaction 过滤器，从而可以在 Compaction 操作时处理键。例如，可以定义一个过滤器处理键过期，从而使 RocksDB 有了类似过期时间的概念。
MemTable 插件：LevelDB 中的 MemTable 是一个 SkipList，适用于写入和范围扫描，但并不是所有场景都同时需要良好的写入和范围扫描功能，此时用 SkipList 就有点大材小用了。因此 RocksDB 的 MemTable 定义为一个插件式结构，可以是 SkipList，也可以是一个数组，还可以是一个前缀哈希表（以字符串前缀进行哈希，哈希之后寻找桶，桶内的数据可以是一个 B 树）。因为数组是无序的，所以大批量写入比使用 SkipList 具有更好的性能，但不适用于范围查找，并且当内存中的数组需要生成为 SSTable 时，需要进行再排序后写入Level 0。前缀哈希表适用于读取、写入和在同一前缀下的范围查找。因此可以根据场景使用不同的MemTable。
SSTable 插件：SSTable 也可以自定义格式，使之更适用于 SSD 的读取和写入。除了插件式架构，RocksDB 还进行了一些写入以及 Compaction 操作方面的优化，主要有以下几个方面：
- 线程池：可以定义一个线程池进行 Level 0～Level 5 的 Compaction 操作，另一个线程池进行将MemTable 生成为 SSTable 的操作。如果 Level 0～Level 5 的 Compaction 操作没有重叠的文件，可以并行操作，以加快 Compaction 操作的执行。
- 多个 Immutable MemTable：当 MemTable 写满之后，会将其赋值给一个 ImmutableMemTable，然后由后台线程生成一个 SSTable。但如果此时有大量的写入，MemTable 会迅速再次写满，此时如果Immutable MemTable 还未执行完 Compaction 操作就会阻塞写入。因此 RocksDB 使用一个队列将Immutable MemTable 放入，依次由后台线程处理，实现同时存在多个 ImmutableMemTable。以此优化写入，避免写放大，当使用慢速存储时也能够加大写吞吐量。