leveldb注释1–整体介绍

概括的说，leveldb是一个kv型的存储库。主要特点如下：
> 单机嵌入式接口
> 持久化存储
> KV系统，提供读写删除操作(kv都是字节序列)
> 支持快照功能，使得读操作不受写操作影响
> 磁盘上的数据是有序的，且分级存储，同时在文件保存相应的索引以加速读操作
> 删除是一种特殊类型的写操作
> 提供压缩操作以减少存储空间
> 写入，延迟写入，通过log保证数据不丢失

整体架构如下图所示：

leveldb整体结构

为了支持kv型的读写删除操作，leveldb在内存与磁盘中分别用了一些数据结构/数据文件。从上图可以看出，内存中主要有memtable与immutable memtable，而磁盘上主要有CURRENT、MANIFEST、.log、LOCK、LOG以及分级的.sst等文件。

内存中的memtable与immutable table本质上都是一个skip list，保存当前写入内存而未持久化至磁盘的数据。对于特定的db来讲，一开始只有一个memtable，当memtable写入操作超过阈值(或者对应的.log文件超过阈值时)后，会转化为immutable memtable。同时会产生新的memtable以供后续数据插入。而immutable memtable是只能读不能写的。

磁盘上的LOCK文件锁住当前db。LOG文件是leveldb运行过程中产生的一些日志(注意跟.log文件区分)。.log文件则跟memtable配合，保存未持久化的写操作，以防运行过程中程序异常导致数据丢失。sst文件保存了最终的数据。随着压缩的进行，会产生不同level的sst文件。为了描述这些sst文件，比如level0有哪些文件，对应的key-range范围，则有相应的MANIFEST文件。而CURRENT文件则指向描述db最新状态信息的MANIFEST。因为leveldb支持version与snapshot机制，随着leveldb的运行，会不断的增删sst数据文件，原有的描述文件可能仍在使用，而CURRENT指向的MANIFEST则始终表示最新的描述文件。

再来看看leveldb运行过程中的主要操作。
先来看写入操作(put)。从架构图可以看出，leveldb会先将写入操作写至.log文件，写入成功后再写入memtable。由于写log是追加写，而写memtable是skip list的内存操作，因此leveldb的写是相当快的。

对于读操作(get)来讲，主要分为3步。先查memtable，没有找到则在immutable memtable中继续查找；若还没有找到，则表示对应的key-value数据可能已持久化至磁盘中，因此需要借助MANIFEST文件来找到对应的sst文件，然后再在对应的sst文件中查找。由于MANIFEST文件常驻内存，而MANIFEST保存了不同sst文件的key-range，因此查找对应的文件是很快的。找到对应的文件后，由于sst文件内部是有序的，并且有相应的索引索引不同key-range的value，因此需要先读入这些索引，再在索引中二分查找，再根据索引找到对应的块，然后遍历相应的块查找。这个过程可能需要两次大范围的读文件操作。一次是读索引，一次是读对应的block。为了加快这个操作，leveldb有相应的table cache与block cache，以分别加速sst文件与block的读操作。另外有些数据可能在db中就不存在，为了加速这些数据的查找，每个sst文件都可以添加合适的bloom filter。bloom filter是在载入相应的sst文件后对数据进行过滤的。

最后来看看压缩(compact)操作。leveldb的压缩操作分为minor compact与major compact。所有的压缩操作都是启动一个新线程来完成的。从架构图可以看出，minor compact就是遍历immutable memtable(本质上是一个skip list)，dump至一个新的level0 sst文件。从这里可以看出，新dump出来的sst文件可能会跟已有的level0级别的sst文件存在key-range上的重叠。而level[1-6]上的sst文件则不会存在这个这个问题，level[1-6]上的文件是由上一级文件进行major compact得到的。当level 0层文件数超过阈值(>=4)，会触发level0与level1层文件合并。而对于大于等于level1以上的level，总文件字节数超过阈值(10M 100M 1G 10G 100G 1T(level=6))则会触发该操作。至于选择哪个文件与下一级别的文件进行compact，则是轮流进行的。另外如果特定level文件的seek次数(也就是访问次数)超过阈值，也会触发对应的major compact操作，此时则会直接选择该文件与下一level进行major compact操作。

后续我们将先分析内存与磁盘上的数据结构/文件格式代码，再分析GET/PUT等操作对应代码。在此之前，我们看看leveldb源代码的目录结构。
doc/: 包括了一些文档，
> benchmark.html       性能测试文档
> impl.html                   内部实现文档
> index.html                 使用文档
> log_format.html       .log文件格式
> table_format.html   .sst文件格式

helpers/:提供了一个简单的内存文件操作接口，相当于实现了一个Env接口。Env接口对应了leveldb运行的底层平台。
include/leveldb/:对外接口，使用时include该目录下的头文件即可。
> cache.h cache接口，用户可实现合适的cache接口，以加速读操作
> c.h leveldb是用c++编写的，这里提供了c的对外封装
> comparator.h
db.h
env.h
filter_policy.h
iterator.h
options.h
slice.h
status.h
table_builder.h
table.h
write_batch.h

util/:
> arena
> bloom
> cache
> coding
> comparator
> crc32c
> env
> env_posix
> filter_policy
> hash
> histogram
> logging
> mutexlock
> options
> posix_logger
> random
> status
> testharness
> testutil

port/:
> atomic_pointer
> port_example
> port
> port_posix
> README
> thread_annotations

table/: sst table相关操作的封装
> block_builder
> block
> filter_block
> format
> iterator
> iterator_wrapper
> merger
> table_builder
> table
> two_level_iterator

db/:leveldb主要操作的实现部分
> builder
> c
> db_bench
> dbformat
> db_impl
> db_iter
> filename
> log_format
> log_reader
> log_writer
> memtable
> repair
> skiplist
> snapshot
> table_cache
> version_edit
> version_set
> write_batch
> write_batch_internal