leveldb 原理解析

发布时间:2021-10-25 02:17:59



目录
概览Features
整体结构MemtableImmutable Memtable
SSTable 文件(SST)SSTable的物理结构Block 物理结构节省 key 空间在 block 内查找一个 key: 迭代器(Block::Iter)读取 Block(Table::BlockReader)
DataBlock为什么 key需要有序
MetaBlockFilterBlock 物理结构
IndexBlockMetaIndexBlockFooter从 table 中读取某个 key读取 TableTable Cache 结构

Manifest 文件Current 文件Log 文件snapshotcompactionminor compactionmajor compaction数据压缩

主要操作写操作读操作



官网
github
自己加了 comment 的github分支


本文是根据https://blog.csdn.net/qq_26499321/article/details/78063856 并加上自己看代码的笔记整理的 。
很多地方有源码信息。可以据此快速定位源码查看。
图尽量符合拿来主义原则
.


概览

LevelDB is a fast key-value storage library written at Google that provides an ordered mapping from string keys to string values.


Features
Keys and values are arbitrary byte arrays.Data is stored sorted by key.Callers can provide a custom comparison function to override the sort order.The basic operations are Put(key,value), Get(key), Delete(key).Multiple changes can be made in one atomic batch.Users can create a transient snapshot to get a consistent view of data.Forward and backward iteration is supported over the data.Data is automatically compressed using the Snappy compression library.External activity (file system operations etc.) is relayed through a virtual interface so users can customize the operating system interactions.

LevelDB 是由 Google 开发的 key-value 非关系型数据库存储系统,是基于 LSM(Log-Structured-Merge Tree) 的典型实现,LSM 的原理是:当写数据库时,首先纪录写操作到 log 文件中,然后再操作内存数据库,当达到 checkpoint 时,则写入磁盘,同时删除相应的 log 文件,后续重新生成新的内存数据库和 log 文件。


详见
SSTable and Log Structured Storage


整体结构


如图所示,整个结构包含内存中的 Memtable 和 Imutable(immutable Memtable)。他们用来缓存用户的写入操作。
其它的结构是都存在于硬盘中。
sstable(SST) 是一个个数据表,储存着用户数据,它是不可修改的。sstable 作为落盘的存储结构,每个 sstable 最大 2MB,从宏观来看,它属于分层的结构,即:


level 0:最多存储 4 个 sstablelevel 1:存储不超过 10MB 大小的 sstablelevel 2:存储不超过 100MB 大小的 sstablelevel 3 及之后:存储大小不超过上一级大小的 10 倍

之所以这样分层,是为了提高查找效率,也是 LevelDB 名称的由来。当每一层超过限制时,会进行 compaction(见compaction章节) 操作,合并到上一层。


Log 文件用来记录db 的更新日志,系统恢复的时候可以使用它恢复未持久化到 SST 中的更新。
Manifest 文件记录了所有 SST 的元信息,包含文件名称、level、最大最小 key等。同时Manifest也记录了未处理的 Log 文件号。 启动启动后,从此获取 log 文件名,实施恢复。
Current 用来记录最新的Manifest文件名称。因为在运行的过程中 SST 信息和 log 文件都在改变。而Manifest文件本身是不可变的,因此会不断生成新的Manifest文件,而Current文件则用来追踪最新的Manifest文件名。


SSTables and Log Structured Merge Trees:


    On-disk SSTable indexes are loaded into memoryAll writes go directly to the MemTable indexReads check the MemTable first and then the SSTable indexesPeriodically, the MemTable is flushed to disk as an SSTablePeriodically, on-disk SSTables are “collapsed together”

Memtable

Memtable是内存中的一个结构(MemTable::Table)。
底层存储结构是 Skiplist。


SkipList Table


Skiplist 的 key(也是 entry) 为


memtable key = {klength}{userkey}{tag}{vlength}{value}
klength = userkey.size()+sizeof(tag)
tag = (SequenceNumber<< 8)|(type)
sizeof(tag) == 8

因此Skiplist的 key 实际*擞τ貌迦氲 k 和 v 信息。
但是KeyComparator只比较前三项: {klength}{userkey}{tag}
也就是按 user_key升序 - SequenceNumber(数据版本号)降序 - type降序 排列, 同一个 user_key 不同 SequenceNumber 的 entries 会在一起。在查找的时候需要指定user_key 和 SequenceNum,找到的 key 会是小于等于指定 SequenceNum 的最大 SequenceNum的key。也就是符合指定版本条件的最新的 key。这是实现 snapshot 的基础,见 snapshot 章节。


Immutable Memtable

当Memtable大小达到配置的限制时,它就会变成 Immutable Memtable。这两个实际上是一样的数据结构。只是使用了两个不同的指针。Memtable接受写入。 Immutable Memtable不接受写入,只接受读取,并会被后台线程 dump 到 level0的 SSTable。


SSTable 文件(SST)

SSTable is a simple abstraction to efficiently store large numbers of key-value pairs while optimizing for high throughput, sequential read/write workloads.


SSTable是 leveldb 数据库的核心数据结构。每个SSTable都是一个完整的数据表。SSTable 内部最核心的则是数据、索引和过滤器


SSTable的物理结构


SSTable 由 DataBlock, MetaBlock,MetaIndexBlock,IndexBlock,Footer 这5部分构成。这5部分在逻辑上存储不同的内容,但是物理上存储方式只有3种。其中


DataBlock/MetaIndexBlock/IndexBlock 拥有相同的物理结构 leveldb::Block,构造方法 leveldb::BlockBuilderMetaBlock 目前只有一种,物理结构是 FilterBlock, 构造方法 leveldb::FilterBlockBuilderFooter 很简单的一个结构。

它们的逻辑内容分别是


DataBlock, 存储用户数据,kv 信息IndexBlock, 存储索引信息MetaBlock/FilterBlock, 存储Filter(布隆过滤器)MetaIndexBlock, 存储MetaBlock的索引(偏移量)Footer, SST的根部,从这里才能找到其它 Block

下面详细介绍各种结构


Block 物理结构

它对应的是leveldb::Block。


分为3个部分。


前面是一个个Entry为KV记录,其顺序是根据Key值由小到大排列的。然后是“*舻恪保≧estart Point)偏移量列表 int32 Restart[N],Restart[i]是第 i 个*舻鉋ntry的offset,该 Entry.key.shared_bytes=0。Restart[]的末尾是*舻闶俊um_restarts=Restart.size()最后是Tailer,包含一个字节的压缩类型,和4个字节的校验和。当前有不压缩和 Snappy 压缩两种 type。
节省 key 空间

Restart[i]记录了第 i 个*舻愕膐ffset。为了节省 key 空间,对于offset 范围属于[Restart[i],Restart[i+1])的一批 Entry[], Entry[i+1]只记录了和Entry[i].key 一样的前缀长度 shared_bytes、独有的后缀长度 unshared_bytes,和独有的后缀 key_delta。据此就能构造一个完整的 Entry[i+1].key。


由于在 SSTable的所有 DataBlock,以及每个 DataBlock中,key 都是有序的。因此连续的 Entry 的 key 是很有可能有重合的前缀的,因此能节省空间。
添加 key:


void BlockBuilder::Add(const Slice& key, const Slice& value)

在 block 内查找一个 key: 迭代器(Block::Iter)

Block::Iter 迭代器提供了Next(),Prev(),Seek(key) 这三个主要方法。因此支持对所有的 Entry 进行遍历。以及跳到指定的 key。


Iter::Next() :迭代的过程中保存当前迭代位置的 key。Next() 就能根据key和key_delta构造新的 key 了。Iter::Prev():对于Prev()则会麻烦点,需要先前面最靠*的一个*舻悖僖桓龈霰槔 key,直到当前 key 的前一个 key。Iter::Seek(key) :二分查找*舻 key, 然后从*舻 Entry 开始遍历寻找目标 key。这是最常用的方法,复杂度为 logN。
读取 Block(Table::BlockReader)

可以配置Block Cache,Cache 的 key是所属文件(SST)的cache_id加上这个block在SST的偏移量block_offset。而value则是这个Block的内容。


block_cache_key={cache_id}{block offset}

如果 cache miss 了,则从文件中读取整个 Block
Block cache 是 leveldb 的最细粒度的缓存了。没有针对一个 kv 的缓存,这也是缓存效率不够高的原因。很多基于 leveldb 的分布式 kv 存储系统会在 leveldb 之上再加一层 kv 缓存。


DataBlock

物理结构是 Block。
DataBlock 是用来存储用户的 (key, value) 数据的。
其中Entry Key定义为


DataBlock Key := UserKey + SequenceNum + Type
//对比Memtable中的Key,可以发现Data Block中的Key并没有拼接UserKey的长度在UserKey前
//这是由于上面讲到的物理结构中已经有了Key的长度信息。
Type := kTypeDeletion or kTypeValue

如果type=kTypeDeletion的话,一般 value 为空。即只标记为删除。
DataBlock 的 Entry Key 依然含有SequenceNum,因此可以跟 Memtable 一样根据SequenceNum来做版本控制。实现 snapshot。


为什么 key需要有序

上面描述过,在一个 block 中,key 有序的话就可以做二分查找。虽然有*舻悖侵*舻阋彩怯行虻模虼艘部梢愿葜*舻愣植檎摇


在一个 SSTable 中,每个 DataBlock 的 key 也是有序的,这样就能根据 indexBlock 来做二分查找DataBlock。


同样,除了 level0 的文件之间可能有 key 重合。其它的 level 都没有重合key,因此也能做 SST 的二分查找。
因此在所有的 SST 中查找一个 key 的时候,先二分查找到一个 SST 文件,再二分查找到一个 DataBlock,再二分查找到 Entry。 整个复杂度是 logN。


还有,compaction(文件压缩合并)的时候,如果 key 是有序的,就可以做归并了。


MetaBlock

物理结构是 FilterBlock。
比较特殊的Block,用来存储元信息,当前MetaBlock只有一个,即 FilterBlock,存储的是整个表的 key 的 BloomFilter。写入Data Block的数据会同时更新对应FilterBlock中的过滤器。读取数据时也会首先经过布隆过滤器过滤。FilterBlock的物理结构也与其他Block有所不同.


FilterBlock 物理结构

[filter 0]
[filter 1]
[filter 2]
...
[filter N-1]
[offset of filter 0] : 4 bytes
[offset of filter 1] : 4 bytes
[offset of filter 2] : 4 bytes
...
[offset of filter N-1] : 4 bytes
[offset of beginning of offset array] : 4 bytes
lg(base) : 1 byte

前面是 filters[],然后是 filterOffsets[], 然后是filterOffsetsOffset
上图所示拥有 filters.size()==N 个 filter。每个filter[i]有自己的filterOffsets[i]指向它。


对于每个 DataBlock,如果它的 offset 是DataBlockOffset,则它所属的 filter 是


filters[DataBlockOffset/2KB]


因此,每个 filter 都是一批连续的 DataBlock 的BloomFilter。该BloomFilter的误判率为1%。也就是说:


如果BloomFilter判定某个 key 存在该 block,则它有1%的可能性实际上不存在。如果BloomFilter判断某个 key 不存在该 block,则它一定不存在。

查看一个 key 是否可能匹配某个 DataBlock 的过程:


    先根据 block_offset 获取 filterIndex=DataBlockOffset/2KB再根据 filterIndex 获取 filterOffset = filterOffsets[filterIndex]再根据 filterOffset 获取 filter = filters[filterOffset]再看 key 是否匹配 filter

构建文件格式


FilterBlockBuilder::FilterBlockBuilder(const FilterPolicy* policy)

从文件读取构造


FilterBlockReader::FilterBlockReader(const FilterPolicy* policy,
const Slice& contents)

过滤器查看指定的 dataBlock 偏移量 的 dataBlock 是否可能匹配key


bool FilterBlockReader::KeyMayMatch(uint64_t block_offset, const Slice& key)

IndexBlock

物理结构是 Block。
记录DataBlock位置信息的Block,其中的每一条Entry指向一个DataBlock,Entry 的(k,v)为:


Key:在[DataBlock的最大Key,下一个 DataBlock 的最小 key) 范围内的最短 key,Value:指向该DataBlock位置的Handle

和 DataBlock的存储格式一样,IndexBlock的 key 也是有序的,因此可以使用二分查找看某个 key 在哪个IndexBlockEntry 里面,然后获取 DataBlock 的 Handle,再获取 DataBlock,再在DataBlock二分查找对应的 key。


一个 SSTable 只有一个 IndexBlock,读取SSTable的时候,IndexBlock是直接加载到内存中的。因此查看某个 key 在哪个 DataBlock 里面很快。至于读取 DataBlock 的速度,则要看是否hit了Block cache 了,



Status TableBuilder::Finish()

MetaIndexBlock

物理结构是 Block。
当前MetaBlock只有一个 FilterBlock。因此MetaIndexBlock也只有一条 Entry,这个 Entry 的(k,v)为:


k:filterNamev:指向 FilterBlock的 BlockHandle

构建过程见


Status TableBuilder::Finish()

Footer

leveldb::Footer
位于Table尾部,记录指向MetaIndexBlock的Handle和指向Index Block的Handle。需要说明的是Table中所有的Handle(leveldb::BlockHandle)是通过偏移量Offset以及Size一同来表示的,用来指明所指向的Block位置。Footer是SST文件解析开始的地方,通过Footer中记录的这两个关键元信息Block的位置,可以方便的开启之后的解析工作。另外Footer中还记录了用于验证文件是否为合法SST文件的常数值Magic num。


构建过程见


Status TableBuilder::Finish()

从 table 中读取某个 key

读取过程


    从 indexBlock二分查找看是在哪个 DataBlock 中,获取 block_offset以(block_offset, key)为参数,调用 filter,看是否存在,不存在则返回读取DataBlock,二分查找获取(k,v)

可见,如果 SSTable 的 IndexBlock 和 FilterBlock 已经读取到内存。则可能需要一次文件 IO 来读取 DataBlock,如果该DataBlock已有缓存,则不需要文件 IO。


Status Table::InternalGet(const ReadOptions& options, const Slice& k,
void* arg,
void (*saver)(void*, const Slice&, const Slice&))

以及 indexBlock - DataBlock 双层迭代器:


void TwoLevelIterator::Seek(const Slice& target)

读取 Table

不像 BlockCache 是可配置的。Table 的 Cache 不是可配置的,是一定存在的,且是 LRU。在Cache中,


Table Cache 结构


key值是SSTable的文件名称(file_number)。
value是个TableAndFile::TableAndFile指针。它包含两部分:


struct TableAndFile {
RandomAccessFile* file;
Table* table;
};

file指向磁盘打开的SSTable文件,这是为了方便读取内容;
table指向内存中这个SSTable文件对应的Table结构(leveldb::Table),table结构在内存中,保存了
SSTable的indexBlock/FilterBlock内容以及用来指示block cache用的cache_id ,当然除此外还有其它一些内容。 使用这些 Table 的元信息能够迅速判断一个 key 是否在本 table 中,而不用轻易去磁盘读取 DataBlock(当然因为 Bloom 过滤器有误判率,有时还是需要读取 DataBlock)。
Table不包含 DataBlock,因此是轻量的,因此使用缓存是没问题的。


Status TableCache::FindTable(uint64_t file_number, uint64_t file_size,
Cache::Handle** handle)

Manifest 文件

Manifest文件中记录该版本下所有Level 中的SST文件的分布,以及所有 SST 文件的元信息(leveldb::FileMetaData),包括文件号、文件大小、最大最小key等。在内存中,它对应一个 Version(leveldb::Version)。因此,当给定 key 的时候,很容易就能查出 key 是否在哪个文件里面。当给定 key range 的时候,很容易就能算出哪些文件和key range有交集,这在压缩(Compaction)的时候很有用。由于 SST 生成以后就是不可变的,可以认为,version 就代表了某个时刻的SST 的 snapshot。


同时,内存中维护一个 VersionSet(leveldb::VersionSet),VersionSet维护一个 Version 的循环链表,以及当前的 Version:current_。当生成新的 Manifest 文件的时候,会根据当前的版本 current_ (当做base_), 以及表示 version 变更情况的 VersionEdit 生成一个新的 Version:newVersion。然后保存到新的 Manifest 文件,将 Current 文件(见 Current 章节)指向这个新的 Manifest 文件。并在内存中更新current_ = newVersion


生成新的 Manifest 的文件和 Version:


VersionSet::LogAndApply(VersionEdit* edit, port::Mutex* mu)

Current 文件

从上面的介绍可以看出,LevelDB启动时的首要任务就是找到当前的Manifest,而Manifest可能有多个。Current文件简单的记录了当前Manifest的文件名,从而让这个过程变得非常简单。
  Current文件的内容只有一个信息,就是记载当前的manifest文件名。因为在LevleDb的运行过程中,随着Compaction的进行,SSTable文件会发生变化,会有新的文件产生,老的文件被废弃,Manifest也会跟着反映这种变化,此时往往会新生成Manifest文件来记载这种变化,而Current则用来指出哪个Manifest文件才是最新的。


leveldb::CurrentFileName(dbname)

当一个 DB 被打开的时候,会读取 current manifest 构造 Version 信息,此时 VersionSet 只包含该恢复出来的 Version。


Log 文件

当应用写入一条KV数据的时候,LevelDb会先往log文件里写入(可配置是否sync),成功后将数据写入Memtable中,这样基本就算完成了写入操作。Log文件在系统中的作用主要是用于系统崩溃恢复而不丢失数据,假如没有Log文件,因为写入的记录刚开始是保存在内存Memtable中的,此时如果系统崩溃,Memtable 还没有来得及Dump到磁盘,所以会丢失数据(Redis就存在这个问题)。 系统启动的时候,会从 manifest 文件读取需要处理的 VersionSet::log_number_ ,大于等于该 log_number_ 的 log 文件都需要被加载并处理。
  因为一次写入操作只涉及一次磁盘顺序写和一次内存写入,所以这是为何说LevelDb写入速度极快的主要原因。


Log文件划分为固定大小的Block(32KB,log::kBlockSize)。每个Block中包含多个Physical Record;Physical Record的前(4 + 2 + 1, log::kHeaderSize)字节为Header,包括4字节checksum用做校验,2字节存储Record实际内容数据的长度,1字节的Type(log::RecordType)可以是Full、First、Middle或Last中的一种,表示该Physical Record是否完整的logical record,如果Type不是Full,则通过Type指明其前后的Block中是否有当前Record的前驱后继。
Log Block 的格式


Block := Record * N
Record := Header + Content
Header := Checksum + Length + Type
Type := kFullType/kFirstType/kMiddleType/kLastType


LevelDB首先将每条写入数据序列化为一个Logical Record。根据当前 block 剩余空间的情况,如果一个 Logical Record 比较小,就会被格式化为一个kFullType类型的 physical record。否则,会被拆分为多个kFirstType/kMiddleType/kLastType类型的 physical record。并保证Block的开始位置一定是一个新的Physical record。这种安排使得发生数据错误时,最多只需丢弃一个Block大小的内容。显而易见地,不同的Logical record可能共存于一个Block,同时,一个Logical record也可能横跨几个Block。


一个Logical Record拆分为多个physical record后,这些physical record顺序写入当前 block或者开辟新的 block。如果在一个 block 的最后,剩余空间很小,连 record header 都放不下,则剩余空间填充空数据,跳到下一个 block (32KB 对齐)起始位置,开启一个新的 physical record。


所以,再读/写一个logical record 的时候,会连续读/写多个连续的 block,都是顺序读写。效率很高。


写一个 logical record


Writer::AddRecord(const Slice& slice)

读取一个 logical record


Reader::ReadRecord(Slice* record, std::string* scratch)

snapshot

我们把应用插入的 原始 key 叫 user_key。不管是 MemTable 还是 SSTable,都是将 user_key 和 sequence一起当做新 key 保存的( 还有 type,可忽略,因为同一个 user_key的不同版本用sequence区分就够了。对于 Memtable,还有个 klength,对于版本没啥作用)。sequence 是在数据插入MemTable的时候生成的,是递增的。sequence 是 SequenceNum 的简称。


InternalKey = UserKey + tag
tag = SequenceNum + Type

插入数据的时候SequenceNumber 会 递增,例如插入key1, key2, key3, key4等数据时,依次对应的SequenceNumber为1, 2, 3, 4。当然,并不是每次都会如此简单,当存在合并写(DBImpl::Write)时,例如key1, key2,/key3/key4,key5。key1对应的SequenceNumber为1, key2, key3, key4对应的SequenceNumber为2, key5对应的SequenceNumber为5。


leveldb 定义了个SnapshotImpl类


class SnapshotImpl : public Snapshot {
const SequenceNumber sequence_number_;
}

它的核心是一个 SequenceNumber。它只是一个 uint64_t 的数字。
内存中会维护一个snapshots_,它是snapshot的双向链表。每次 Get 的时候会先获取一个SequenceNumber构造snapshot,并插入到双向链表中。当一个snapshot用完后,从双向链表中删除就行了。
在Get操作时,可以通过option传入snapshot参数,否则默认取最新(大)的 snapshot。
去 Memtable 和 SST 查找 user_key 的时候,将 {user_key}{snapshot.SequenceNumber}组合起来查找。根据比较器 leveldb::InternalKeyComparator 就会找到SequenceNumber小于等于snapshot.SequenceNumber的 key。相当于是版本更高的 update 都被过滤掉了。从而实现了版本控制。
  那么如何保持快照的数据不会被删除了?在leveldb中,唯一会删除数据的地方就是compaction。从compaction那一节中,我们可以知道,只有快照链表不关心的数据才会被删除。因此,持有快照的线程不用担心在操作过程中需要的数据被删除了。


compaction

为了加快读取速度,levelDb采取了compaction的方式来对已有的数据进行整理压缩,通过这种方式,来删除掉一些不再有效的KV数据,减小数据规模,减少文件数量等。
  数据压缩是LevelDB中重要的部分。也即多个文件进行合并生成新的文件,冷数据会随着Compaction不断的下移,同时过期的数据也会在合并过程中被删除。
  LevelDB的压缩操作由单独的后台线程负责。这里的Compaction包括两个部分,Memtable 向Level 0 SST文件的minor Compaction,以及SST文件向下层的major Compaction。


在计算哪个 level最需要压缩的时候,会对每个 level 计算一个 score。


level=0, score = file_num/4level>0, score = level_bytes/ MaxBytesForLevel(level)

其中MaxBytesForLevel(i+1)=10MaxBytesForLevel(i) , 见 VersionSet::Finalize(Version v)


只有 score >1 的情况下才会触发 compaction, 且一次 compaction 只取 score 最高的进行。因此,level=0合并的触发条件是 SST 个数大于4个。level>0的合并条件是整个 level 的文件总大小超过了一定大小,且 level 越高文件总大小限制越大,越难以发生合并。


VersionSet::NeedsCompaction()

当然,还可以手动触发一次compaction。


同一时刻只有一个compaction在后台运行。


DBImpl::MaybeScheduleCompaction()

合并生成的文件大小同样受限制。如果超过了,则会生成多个文件。


minor compaction


Memtable 不会直接 dump 成 SST,如果一个Memtable触发了大小限制,会先尝试把它变成 Immutable Memtable, 并生成新的空的Memtable。如果此时已经有 Immutable Memtable,则会等待。


后台线程会择机将Immutable Memtable Dump 到 level0~level2(依据一定的策略) 。这是个dump 的时候会获得一个Immutable的Iterator用来遍历其中的所有内容来 build 新的SST 。然后生成新的 manifest 文件和 Version,并将内存中的Immutable Memtable丢弃。然后执行一些废弃文件删除操作。包含:


    非最新的 manifest 文件文件号小于最新manifest 文件记录的 log_number_ 的log 文件。(文件号比较大的用于系统崩溃后恢复,因为这些 Log 文件记录的操作还只存在与 Memtable 中,未持久化到 SSTable。)在内存 versionSet 里面没有记录的 SSTable 文件临时文件

DBImpl::CompactMemTable()


major compaction


当某个level下的SSTable文件总个数(对于 level=0)或者总大小(对于 level>0)超过一定设置值后,levelDb会从这个level的SSTable中选择一个文件,将其和高一层级的level+1的SSTable文件合并,这就是major compaction。 也有特殊情况,低 level 的文件直接*移到高 level,虽然没有发生合并,但也属于compaction。
  我们知道在大于0的层级中,每个SSTable文件内的Key都是由小到大有序存储的,而且不同文件之间的key范围(文件内最小key和最大key之间)不会有任何重叠。Level 0的SSTable文件有些特殊,尽管每个文件也是根据Key由小到大排列,但是因为level 0的文件是通过minor compaction直接生成的,所以任意两个level 0下的两个sstable文件可能再key范围上有重叠。所以在做major compaction的时候,对于大于level 0的层级,选择其中一个文件就行,但是对于level 0来说,指定某个文件后,本level中很可能有其他SSTable文件的key范围和这个文件有重叠,这种情况下,要找出所有有重叠的文件和level 1的文件进行合并,即level 0在进行文件选择的时候,可能会有多个文件参与major compaction。
  同层的文件轮流来compaction,比如这次是文件A进行compaction,那么下次就是在key range上紧挨着文件A的文件B进行compaction,这样每个文件都会有机会轮流和高层的level 文件进行合并。如果选好了level L的文件A和level L+1层的文件进行合并,那么问题又来了,应该选择level L+1哪些文件进行合并?levelDb选择L+1层中和文件A在key range上有重叠的所有文件来和文件A进行合并。
  有人可能会觉得那岂不是生成的高 level 文件的 key range 越来越大了?其实不会的,因为生成的文件也是有大小限制的,如果超过了指定大小,则会生成多个文件。但是生成的文件之间依然不会有 key 重叠。而且因为在归并的过程中,很多冗余的 key 已经被丢弃了,因此生成的文件总大小将会小很多。因此这就是一种数据压缩


数据压缩

上面说过了,在归并的过程中,冗余的 key 会被丢弃,那如何判断要不要丢弃呢?
多路归并的过程中,是按 key 的升序归并的,对于同一个 user_key, sequence 更大的先归并。归并时会从 SnapshotList 中获取最小的版本号smallest_snapshot,它的存在说明有线程持有该版本号,该版本号要求对于同一个 user_key, 有一个sequence<=smallest_snapshot 的最大的sequence存在就行了,更小的sequence的 entry 都可以丢弃。因此当归并到某个 user_key的时候,如果满足以下两种情况,则该 key 可以被丢弃。
情况1:
相同 user_key 已被归并且它的 sequence<=smallest_snapshot


其次,对于一个kTypeDeletion的 key,如果它满足以下两个条件,则它也可以被丢弃:
情况2:


    没有比 level+1 更高的该 user_key 存在。(因此它不会去覆盖更高level的 key,这个删除标记就没意义)sequence<=smallest_snapshot 。(如果正在压缩的 文件中还有该 user_key,则它们的 sequence 更小,按照情况1也会被丢弃,因此该 key 不会去覆盖它们)

如果低 level 的有 key,就会覆盖该 key。那该 key 更没有存在的必要了。
压缩操作见:


DBImpl::DoCompactionWork(CompactionState* compact)

主要操作
写操作

LevelDB的写操作包括设置Put(key,value) 和删除Delete(key) 两种。需要指出的是这两种情况在LevelDB的处理上是一致的,删除操作其实是向LevelDB插入一条标识为删除的key,而 value 则为空。 真正的删除操作是Lazy的,会在以后的Compaction过程中去掉这个KV。

  从图中可以看出,对于一个插入操作Put(Key,Value)来说,完成插入操作包含两个具体步骤:
  首先是将这条KV记录以顺序写的方式追加到之前介绍过的log文件末尾,因为尽管这是一个磁盘读写操作,但是文件的顺序追加写入效率是很高的,所以并不会导致写入速度的降低;
  第二个步骤是:如果写入log文件成功,那么将这条KV记录插入内存中的Memtable中,前面介绍过,Memtable只是一层封装,其内部其实是一个Key有序的SkipList列表,插入一条新记录的过程也很简单,即先查找合适的插入位置,然后修改相应的链接指针将新记录插入即可。完成这一步,写入记录就算完成了。
  所以一个插入记录操作涉及一次磁盘文件追加写和内存SkipList插入操作,这是为何levelDb写入速度如此高效的根本原因。


DBImpl::Write(const WriteOptions& options, WriteBatch* my_batch)

函数说明
不管是 delete 操作还是 put 操作,都先转换为一个WriteBatch,然后以该WriteBatch为任务放入一个任务队列,然后等待直到轮到自己执行。由于可能有多个线程在执行写操作,轮到某个线程的时候,它会从队列头部取出一部分WriteBatch,合并成一个WriteBatch(里面的 kv 共用同一个 SequenceNumber)一起执行。因此,轮到某个线程执行的时候他的任务可能已经被别的线程顺带执行了,此时直接返回即可。


执行一次WriteBatch的时候,先写 Logfile (如果是同步模式,则执行 sync 操作),然后再更新 Memtable。最后更新最新的SequenceNumber供下次写入使用。


读操作


首先,生成内部查询所用的Key,用生成的Key,依次尝试从 Memtable,Immtable以及SST文件中读取,直到找到(或者查到最高level,查找失败,说明整个系统中不存在这个Key)。
  从信息的更新时间来说,很明显Memtable存储的是最新鲜的KV对;Immutable Memtable中存储的KV数据对的新鲜程度次之;而所有SSTable文件中的KV数据新鲜程度一定不如内存中的Memtable和Immutable Memtable的。对于SSTable文件来说,如果同时在level L和Level L+1找到同一个key,level L的信息一定比level L+1的要新。也就是说,上面列出的查找路径就是按照数据新鲜程度排列出来的,越新鲜的越先查找。找到了就返回。


从SST文件中查找需要依次尝试在每一层中读取,得益于Manifest中记录的每个文件的key区间,我们可以很方便的知道某个key是否在文件中。Level 0的文件由于直接由Immutable Dump 产生,不同的文件可能有 key 重叠,所以需要对每个文件依次查找。对于其他Level,由于归并过程保证了其互相不重叠且有序,二分查找的方式提供了更好的查询效率。
  可以看出同一个Key出现在上层的操作会屏蔽下层的。也因此删除Key时只需要在Memtable压入一条标记为删除的条目即可。被其屏蔽的所有条目会在之后的归并过程中清除。
  相对写操作,读操作处理起来要复杂很多,所以写的速度必然要远远高于读数据的速度,也就是说,LevelDb比较适合写操作多于读操作的应用场合。而如果应用是很多读操作类型的,那么顺序读取效率会比较高,因为这样大部分内容都会在缓存中找到, 因为 levelDb 缓存的最细粒度是 DataBlock,而不是某个 kv。应该尽可能避免大量的随机读取操作。

相关文档

  • 初中思想品德教师述职报告
  • php图片缩放比例缩放,PHP自定义图片缩放函数实现等比例不失真缩放的方法
  • hdu 1584 蜘蛛牌 (区间dp)
  • 练习乒乓球拉球的技巧有哪些
  • 优秀的医大学生自我鉴定范文
  • 牛奶和豆浆哪个比较好孩子早上喝牛奶好还是喝豆浆好
  • 孔雀的童话小故事文字版
  • 语重心长的近义词
  • 入党积极分子培养考察登记表填写范本
  • 心情日记模板汇总8篇
  • 槟榔和烟哪个危害大看完你还敢吃槟榔和抽烟吗
  • 触动人心的句子76句
  • 单位职工读书心得体会干货6篇
  • 爱情文字唯美语录大全
  • 局部农业改革可再养活30亿人
  • 忆苏轼作文800字
  • 法律咨询服务协议
  • 基于proteus的51单片机仿真实例七十九、8位数码管驱动芯片max7221应用实例
  • 欣赏日式装修中的飘窗装修效果图
  • 乔迁的祝福语大全
  • 简单个人租房合同标准范本
  • 中国留学生在俄生活怎样
  • 2016年12月CET6阅读理解精练
  • 电脑怎么上不了网页走丢了怎么办
  • b365酵素可以长期喝吗b365酵素有副作用吗
  • emule不能连接服务器解决办法
  • QT 中ui界面显示 圆形按钮
  • 手机能连上wifi但上不了网
  • 为什么炒豆角不容易熟该怎么炒
  • Dota中卡尔技能总数的组合数量
  • 猜你喜欢

  • 化学官能团相互转换大全(part3)
  • 【最新】高中物理第1章电磁感应与现代生活章末综合测评沪科版选修3 2
  • 交通事故责任认定的依据和划分标准是怎样的-
  • 江西省崇仁县第一中学2017届九年级语文上学期第一次月
  • 2000定额问题解答汇总
  • 迟子建散文赏析
  • 渐开线少齿差和零齿差内啮合齿轮副的变位切削
  • 我国城市居民国内旅游需求影响因素分析
  • 制造技术 金属切削的基础知识
  • 高中物理人教版选修3-4课件:13.5 光的衍射
  • 初二英语下学期期中考试试卷.doc
  • 新编文档-第2章 2.2.1 第1课时-精品文档
  • 【范例推荐】工程公司内部审计管理办法(WORD12页)
  • 七年级上册文学常识复*资料
  • 2019-2020学年度最新(部编版)人教版一年级上册语文园地四 (2)精品教学课件
  • 人音版音乐九下第4单元《鼓乐》ppt精品优秀课件
  • 煤层厚度变化的影响因素
  • (目录)2018-2023年中国料理机行业发展趋势预测与投资战略规划研究报告(目录)
  • 【学习方法】FPGA开发
  • 【2019年整理】中2班期末语文试题
  • 大学新生军训心得体会学*600字
  • 郑州发展跨境电子商务模式分析
  • 教师政治学习心得体会详细7篇
  • 兴义市恒昌贸易有限公司企业信用报告-天眼查
  • 家庭环境影响着孩子性格的形成
  • 带耳机引起耳鸣怎么办
  • 快手如何录制长视频
  • 公司员工薪酬管理制度怎么写
  • 宝马轿车:液晶显示屏德文与中英文对照表
  • 二本学渣考研失败,音视频时代你还不会NDK开发?含小米、腾讯、阿里
  • 流苏绕琴弦诗词
  • 最新-市人大机关扶贫工作计划 精品
  • 2020年中学考试数学复*等比、合比性质综合应用
  • 生态哲学 地球母亲,我想对你说
  • 2015年度湖州金泰科技股份有限公司销售收入与资产数据报告
  • 江苏省2016年监理工程师执业资格:工程师的口头指示考试试题
  • 集团新员工培训手册PPT课件
  • 学校落实从严治党主体责任 酮??;?愕辰üぷ骰惚
  • 小程序 祝福小工具源码分享
  • 菠萝的吃法及食用宜忌
  • 上海华油商务有限公司企业信用报告-天眼查
  • QORVO免费工具让RF设计更容易
  • 电脑版