发布者: Xuan Zhou

1.简介

levelDB是Jeff Dean和Sanjay Ghemawat发起的开源key-value DB,支持读、写、删除这些基本功能,也支持快照(通过log file),数据压缩(snappy compress)。目前有一些开源的数据库是基于levelDB实现的,比如,Tair ldb以及SSDB

levelDB的读写性能很好,参考官方benchmark数据(由于使用了cache,顺序读性能优于随机读)。比较适用于随机写操作密集或是顺序读较多的情况

1.1 levelDB用法

源代码: leveldb-1.15.0

levelDB的使用:

tar xvf FileName.tar leveldb-1.15.0
cd leveldb-1.15.0
make

就会在目录中生成libleveldb.a及libleveldb.so, 一个例子:

#include <iostream>
#include "leveldb/db.h"
int main()
{
    leveldb::DB* db;
    leveldb::Options options;
    options.create_if_missing = true;
     
    leveldb::Status status = leveldb::DB::Open(options, "/home/xuzhou/leveldb-1.15.0/test/testdb", &db);
    // put test
    char numStringPut[64];
    for (int i = 0; i < 10000; ++i)
    {
        sprintf(numStringPut, "%d" , i);
        std::string keyPut(numStringPut);
        std::string valuePut = keyPut;
        status = db->Put(leveldb::WriteOptions(), keyPut, valuePut);
        assert(status.ok());   
    }
    // get test
    char numStringGet[64];
    for (int i = 0; i < 10000; ++i)
    {
        sprintf(numStringGet, "%d" , i);
        std::string keyGet(numStringGet);
        std::string valueGet;
        status = db->Get(leveldb::ReadOptions(), keyGet, &valueGet);
        assert(status.ok());       
        std::cout << "keyGet:" << keyGet << " valueGet:" << valueGet << std::endl;       
    }  
    // delete test
    char numStringDelete[64];
    for (int i = 0; i < 10000; ++i)
    {
        sprintf(numStringDelete, "%d" , i);
        std::string keyDelete(numStringDelete);
        status = db->Delete(leveldb::WriteOptions(), keyDelete);
        assert(status.ok());       
    }  
     
    delete db;
    return 0;
}

编译运行:

bash-3.00$ g++ -o test -g main.cpp -lpthread -L./ -lleveldb -I/home/xuzhou/leveldb-1.15.0/include
bash-3.00$ ./test
bash-3.00$ pwd
/home/xuzhou/leveldb-1.15.0/test/testdb
bash-3.00$ ls
000003.log  CURRENT  LOCK  LOG  MANIFEST-000002

1.2 与其它数据库比较

1.2.1 Redis vs levelDB

RedislevelDB
相同点 持久化存储
写速度快
不同点完全内存查找,速度快随机查找性能差,可能产生磁盘IO,速度较慢
value类型不仅限于字符串(字符串列表,无序不重复的字符串集合,有序不重复的字符串集合,key和value都为字符串的hash表 key-value均为字符串,可自定义Comparator
多语言支持一个C++库
存储容量受限于内存,磁盘只作为备份存储容量依赖硬盘,可支持TB级别数据

1.2.2 sqlite vs levelDB

  1. b+ tree vs lsm tree
  2. sql vs nosql
  3. 性能比较: 官方benchmark数据

2.整体结构

2.1 LSM tree

b+ tree是各种传统db及磁盘索引结构,它的缺点在于每次写操作都可能带来多次的磁盘IO(磁头的旋转和寻道都很耗时,所以顺序读写性能都会优于随机读写),写开销很大,怎样避免磁盘IO呢,LSM tree(Log-Structured Merge-Tree)就是为了优化磁盘写的一种存储结构, 是由The Log-Structured Merge-Tree 提出的,主要是通过将随机写操作转换为内存写和log追加,再批量写入磁盘。levelDB就是基于这种存储结构实现的。

2.2 levelDB的整体结构

其中:

内存中的结构:

  1. memtable: 是内存中的一个跳表结构。当用户向levelDB中写入数据时,会先向log file中写入一条log记录,然后将这个key-value插入跳表中(为什么要使用跳表,后面会介绍)
  2. immutable table:正在进行compact的memtable。当memtable的占用的内存到达write_buffer_size,就会将这个memtable变为immutable table,并重新生成新的memtable和log file

磁盘中的结构

  1. level0: 这个level比较特殊,其中的每个文件都是对immutable table进行compaction生成的,每个文件内部都是由一些有序key-value record组成的block的集合,但是文件和文件之间是无序的,可能有重叠(为什么需要这个特殊的的level)
  2. level1~levelN:这些level的结构比较相似,每层level里也是一些key-value有序的sst file,但是同一层的sst file之间也是有序的,所以在同一层的sst files之间不存在重叠的key-value,其中levelK的总容量为10^K,但每个文件大小都是2M
  3. log file: 用于记录DB操作,用于恢复还没有写入磁盘的memTable, immutable table操作,保证数据一致性。文件名中含有log num,必须保证每次新建的log file的log num最大,以此保证log num最大的log file是最新的
  4. manifest file: log文件,由若干条记录组成(快照+若干条version_edit信息),每次进行compaction后,就会进行version更新,manifest就会将记录version中文件的变化等信息作为一条record写入文件。当需要文件恢复时,通过当前manifest文件的所有record就能获得当前所有level的信息,再通过读log文件,就能恢复memTable, immutable table的信息
  5. current file: 指向当前version的manifest file

3.文件结构

3.1 背景知识

  • slice:是levelDB中最基本的结构,和string类似,包括一个指向字符串的指针及其长度,主要包含一些字符串操作的函数:
const char* data_;
size_t size_;
  • status: levelDB中的消息传递类

  • Arena: 一个比较简单的内存池,为memtable分配内存

  • skip list: memtable的主要结构(线程安全),进行逻辑删除,只对删除的key-value做标记,在compaction的时候才进行删除记录。其查找,插入及删除(只进行逻辑删除)的复杂度都为logN,同时实现比平衡二叉树简单很多,而且用概率的方式平衡性更好。具体细节可以参考:Skiplist vs Non-blocking

  • Varint:不定长整数,每个byte中最高用来标记是否结束,其余7位用来表示数字,最高为0,表示该bit为整数的最后一个byte

3.2 memTable结构

在levelDB中,用户输入的key-value中的key会与SequenceNumber及ValueType构成InternalKey, InternalKey是levelDB中用于比较索引的key, 每个InternalKey都是唯一的

其中:

  1. user_key: 用户输入的key字符串
  2. SequenceNumber: 一个64位整数,这个整数根据entry插入的时间顺序递增,可以认为是entry的时间戳,当user_key相同时, InternalKey以SequenceNumber降序递增
  3. ValueType: entry的操作类型,kTypeDeletion(删除), kTypeValue(插入)

而插入skiplist的entry结构为:

3.3 .sst file(data block)

.sst file的整体结构如图所示:

在这个版本里meta_block只用于存放filter的数据,可能在以后的版本中增加更多其它类型的数据

其中,data_block, index_block以及metaindex_block都以key-value组成block的形式存放所有数据。meta_block中存放的是filter

Footer是文件的结尾,其结构为:

handle中存放的是offset及size,那么根据footer就能找到metaindex_block以及index_block的位置

index_block中key为data_block的last_key(查找时就能通过index_block定位key所在的data_block), value为data_block_handle

metainde_block中key为meta_name, value为meta_block_handle

因此,在查找时sst文件的读取顺序为Footer->index_block(二分查找)->meta_block(filter,快速查找)->data_block

为了减小存储容量,TableBuilder会对这些不同类型的block进行压缩(option,压缩和解压缩的过程会降低levelDB的读写速率),并加入校验码(保证数据的正确性),形成的block结构为

其中type表示是否进行压缩

而data_block, index_block以及metaindex_block的具体结构为:

每个block中会有若干个restart_point,restart_offset存放了这些restart point的offset,由于block中存放的entry都是有序的,那么根据restart_offset的到的restart_point也是key有序的,那么就可以通过二分查找定位key是存放在哪两个start_point之间的。但是在两个start_point之间除了start_point之外的entry的key都是依赖于上一条entry的key, 因此两个start_point之间的查找都是顺序查找。

每条entry的结构为:

shared_bytes == 0的位置表示restart_point, entry中的key都只保存和上一个key不同的部分,相同的部份只通过shared_length从上个key中获取(相当于对key进行了压缩,主要也是为了节省存储空间)

3.3.1 file reader

file_reader是将一个.sst file解析成table的过程 其类关系如图:

.sst file通过table::open解析, 并使用table::Rep来记录文件信息(levelDB比较喜欢将所有类成员包成rep struct进行访问)

table::Rep结构

3.3.2 file writer

可以看作file reader的逆过程,将若干有序的entries写入并形成.sst文件的过程, 类关系如图:

tablebuilder::rep的结构为:

3.3.3 meta block(filter data)

前面已经介绍过,meta block目前只用于存放filter block. 其位于data block之后,为每2KB的数据创建一个filter,用于快速过滤key不在data_block中的请求(提高查找速度),其类图结构为:

filter clock的结构为:

其中,K(数目和data_block一致)和N的值可能是不等的(其中有些filter是空的,主要是为了快速定位filter)

这是由kFilterBaseLg决定的,filter_offset的index为data_block的offset » kFilterBaseLg, 例如,

当每个data_block为6KB, kFilterBaseLg = 11时,每个filter长度为64时,filter的base为2^11也就是2KB,

那么(0 ~ 6KB-1)的data_block就会进行两次filter,但只有第一个filter是有效的,后面的filter都是空的,其filter_index的结构为:

levelDB中提供的默认filter为bloom_filter(参考及例子:Bloom Filters by Example),也可以使用自定义的filter

3.4 log file

3.4.1 类图结构

levelDB通过log_file进行版本控制,数据恢复和快照(主要利用SequenceNumber),主要通过log::Reader和log::writer进行读写

log writer的结构如图所示:

log reader的结构如图所示:

3.4.2 文件结构

log file由若干大小为32KB的block组成,每个block由若干record组成,每条record的结构为:

checksum为32位的crc校验码,type可能为FULL, FIRST, MIDDLE, LAST中的一种example)

FULL: 表示record完全在这个block中

FIRST: 表示block剩余的offset放不完一整条record,这是record的第一部分

MIDDLE: 表示这部分在record中间且占满这块block, 前面某一块为FIRST,后面某一块为LAST

LAST: 表示这是record的最后一部分,占block的前面部分或是整个block

一个例子:

3.5 manifest file(log file)

每个manifest file会管理这个version所有的信息,其内容结构为:

current file保存了当前manifest file的名字

4 levelDB的key-value读写流程

4.1 写流程

levelDB的写速度相对于读来说速度很快,也比较简单。首先顺序写log文件然后将key-value插入skiplist。dan其流程为:

在levelDB中,delete也是作为write_record被写进levelDB的

4.2 读流程

相较于写流程,levelDB的读流程比较复杂,所以读速度远小于写速度,尤其是随机读以及很旧的数据读取,速度会大大降低。数据读速度低的原因在于levelDB中某个key可能存有n条记录,需要读取最新的一条record,因此在查找时需要按照memtable,immutable memtable, level0~levelN的顺序一层一层的查找,如果数据存储在levelN,就要将整个levelDB的所有层都进行查找才能读取数据(会多次磁盘读),才能找到数据。levelDB使用了2种途径来加快查找速率:

  1. cache, LRU cache缓存最近读过的文件及block,顺序读的速率会高于随机读。
  2. compaction, 一定条件时触发compaction, 减少冗余数据以及将低层数据向高层移动,后面详细介绍

读流程如图所示:

其中:

  1. 如果在level0~levelN的查找过程中发现需要compaction,就会在查找完成后,通过DBImpl::MaybeScheduleCompaction进行compaction

  2. Version::Get会从当前version的文件中,根据level0~levelN的顺序一层一层进行查找,直到找到key, 其中,level0(文件之间非有序)中的所有文件都会被查找,level(1~N)(文件之间有序)只会查找

5 compaction

levelDB的数据主要都是以.sst文件分为不同level存放在磁盘中的,除了level0, level1~N的文件之间都是key有序存放的。level0的每个文件都是来由一个immutable_table生成的,所以文件之间可能会存在key range的重叠,level0的compaction与其它level有点区别,他要将level0中所有含有compaction range的文件与level 1进行compaction. 那么确定哪个level需要compaction:

  1. 当level0中的文件数目超过一定数目(4个)时,会将level0中所有的data和level1中的data进行merge,生成新的level1文件(每2M data为一个文件)
  2. 当level1~N中的levelK的data size超过(10^K)MB,就会将levelK中的一个文件和level(K+1)中的所有文件merge生成新的level(K+1)
  3. 当level的查询次数到达阀值时,该level就要进行compaction

而compaction range则是由上次该level的compaction range的最后一个key的下一条开始的(compaction比较均匀),通过compaction, data逐渐从低层向高层移动,以减少查找及遍历开销

compaction的总流程图为:

当compaction不仅仅是将levelK的某个文件直接移动到level(K+1)时,DBImpl::DoCompactionWork会将compaction中的input files(包括levelK文件及level(K+1)中与其重复range的文件) merge形成level(K+1)的output files, 其流程图为:

6 Iterator

Iterator是levelDB中所有查找、遍历以及归并的执行者。这些iterator的关系为:

其中:

  1. TwoLevelIterator是用于遍历每个sst文件iter,其中包含一个index_iter_以及data_iter_, data_iter_初始是空的,在seek到index_iter_时,调用InitDataBlock时才会被初始化。
  2. MergingIterator则存放了一个iterator list,混合遍历list中的各种结构, compaction中的主要归并功能由其实现,由于key相同时,sequence number会以降序排列,因此key相同时,旧的数据会被drop
  3. DBIter中含有一个MergingIterator(InternalKey有序),其主要功能也是遍历整个DB data,但是它需要考虑sequence number,进行快照恢复和版本数据管理

例入:MergingIterator的遍历过程

当MergingIterator

example 1:MergingIterator的遍历过程

当MergingIterator管理3个iterator时,每个iterator当前指向绿色箭头所指位置, current在2:8:1(user_key:sequenceNumber:valueType)的位置,方向为forward, 怎么找到prev和next呢:

  1. 找next的过程: 假设当前方向为forward, current位置所在的iter移动到next,然后在3个iter的指向位置(橙色箭头所指位置)找最小值为2:7:1, 方向仍为forward
  2. 找prev的过程: 假设当前方向为forward, 所有的iter都移动到prev,然后在3个iter的指向位置(灰色箭头所指位置)找最大值为1:2:1, 方向改为reverse

example 2: DBIter的遍历过程

DBIter包含了一个MergingIterator,因此可以看成一个已经有序的遍历,DBIter需要做一些版本相关的处理,假设当前处于current(5:5:0)位置,方向为forward,那么怎么找到它的prev及next呢:

  1. next: 方向为forward, 首先next到6:4:0, 由于这个数据的type是delete, 跳过所有user_key为6的节点,到7:12:1,该entry的type不是delete,即为next
  2. prev: 方向为reverse, 首先prev到2:7:1,保存key值2,一直向前找到key值2的开头entry 2:8:0,由于这个数据的type是delete,继续向前, key值为1的最开始节点为delete,也都被跳过,找到0:11:1, 即为prev


-EOF-
睿初科技软件开发技术博客,转载请注明出处

blog comments powered by Disqus