首页  思维导图  详情

levelDB

2020-09-24 11:05:05   0  举报





AI智能生成

leveldb架构简介

leveldb的查找、存储策略。

作者其他创作

大纲/内容

写入一个KV具体步骤：

1.kv写操作会写入到log文件中，顺序写，做持久化（系统崩溃会从log文件中恢复，log文件也是按照一定格式的二进制数据）

2.写入到log文件后会写入到memtable(一个叫做跳跃表的数据结构)

3.之后write操作就返回成功

4.当memtable数据量达到上限后，那么memtable会变为immutable memtable, 2个表的结构都是一样的，都是跳跃表，不过后者是只读的。

5.此时会新产生一个memtable来支持新的写操作

6.immutable memtable中内容会定期刷新到磁盘，然后清除对应的log文件，生成新的log文件

7.磁盘中数据的存储格式叫sstable

存储架构

1.memtable和immutable memtable 都是跳越表的结构， sstable如上，是google的bigtable中描述的sstable

2.level0是由immutable table直接dump到磁盘中，level1由level0经过compaction获得， level2由level1经过compaction获得，
每个文件后缀为.sst, 每个level中文件数是有限制的，超过限制会被compaction到更高的位置，因此叫leveldb.

3.每个level符合以下规则：
（1）level0中单个文件是有序的，但是文件与文件之间是无序的，并且可能有重复的key.
(2)level1-leveln 每一个level在自己level中都是全局有序的，
（3）manifest文件中包含了每个sst文件中包含的最小的key和最大的key，方便查找。

manifest文件保存了每个sst文件在哪一层，最小的key是啥，最大的key是啥，通过读取manifest文件就可以知道key大概是在哪个level的.sst文件中

读过程

读的顺序是:1.memtable
2.Immutable memtable
3.level0
4.level1

首先会经过memtable进行查找，找不到就依次按顺序往下找，一直找不到就返回empty

从memtable和immutable中查找的过程是：

1.先用迭代器查找，

2.再对找到的内容进行解码，根据找到的标记是value类型还是delete类型来决定返回value还是empty.

sstable查找过程

删除过程

leveldb没有实际的删除操作，就是write一个删除标记和key进去。

我们知道所有key的插入都是有时间顺序的，从memtable到level n一路往后，
如果添加了name1,value1的kv, 现在想要删掉name1的key,只需要插入一条name del标志的记录
这样我们查找的时候就会先遇到name =del的记录，表示key已经被删除，返回empty.