leveldb注释1–整体介绍

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

整体架构如下图所示:

leveldb整体结构

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

此条目发表在 leveldb 分类目录,贴了 , , 标签。将固定链接加入收藏夹。

leveldb注释1–整体介绍》有 1 条评论

  1. coos 说:

    请问关于锁定的问题。当我想要多个程序进行读操作的时候(同一个数据库),遇到了只有一个程序能够占用数据库的问题。我想,既然是读操作,没有必要锁定,不知道该如何控制写锁定而读不锁定?

coos 发表评论 取消回复

电子邮件地址不会被公开。 必填项已被标记为 *

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>