当前位置:Gxlcms > 数据库问题 > LevelDB的源码阅读(一)

LevelDB的源码阅读(一)

时间:2021-07-01 10:21:17 帮助过:20人阅读

git clone https://github.com/google/leveldb.git

项目结构

  • db/, 数据库逻辑
  • doc/, MD文档
  • helpers/, LevelDB内存版, 通过namespace覆盖
  • port/, 平台相关代码
  • table/, LSM有关的

主要模块 

Log 文件

客户端的写请求会先 append 到 Log 文件,成功后再写入到 Memtable。如果宕机可以通过 Log 文件来恢复 Memtable。

Memtable 和 Immutable Memtable

内存数据结构,基于跳表。客户端的读写请求都会由 Memtable 处理。 当 Memtable 占用的内存达到一定阈值,重新生成新的 Memtable 处理客户端请求。原来的 Memtable 转成 Immutable Memtable,等待归并到 SST 文件中。

SST 文件

落地到磁盘的存储文件。SST 分为不同的 level,具体参考文档。

Manifest 文件

Manifest 记录不同 level 的 SST 文件,包括每个 SST 文件的 key range、大小等 metadata。

Current 文件

Current 记录了最新的 Manifest 文件。

LSMtree的核心思想以及问题

在LSM Tree中,所有数据直接写入memtable并打log, 当memtable足够大的时候, 变为immemtable, 开始往硬盘挪, 成为SSTable. 你可以用任何有道理的数据结构来表示memtable, immemtable和SSTable. LevelDB选择用跳跃表(skiplist)实现memtable和immemtable, 用有序行组来实现SSTable。

LSM Tree存在如下问题:

1.适用于插入多而查找少的情况。在查找key时,最坏情况要从memtable读到immemtable, 再到所有SSTable.

2.SSTable要怎么有效merge(major compaction)? 如果只有一个SSTable, 我要把新immemtable归并进去, 就要重写这个SSTable. 数据有多大, 这个SSTable也会有多大.那么把SSTable分成若干份, 每份2MB呢?在最坏的情况下,比如,当前这个immemtable恰好永远有一个key与任意SSTable中至少一个key重复,就回到刚刚重写全库的情况了.

 针对以上问题,LevelDB打了两个增强补丁: 

1. 添加BloomFilter, 这样可以提升全库扫描的速度, 直接跳过没有这个key的SSTable. 

2. leveled compaction, 把SSTable分成不同的等级. 除等级0以外, 其余各等级的SSTable不会有重复的key.

LevelDB的做法让每次compaction波及到的范围是可预期的. 官方文档的说法是"The compaction picks a file from level L and all overlapping files from the next level L+1". 只按等级延迟合并,没有任何随机读写操作, 机制上简单, 而且不需要bookkeeping,可以优雅得释放被删除记录的空间。

 需要注意的是:因为下级可能还有相同key的数据,因此,compaction不一定会清空所有deletion maker. 

 

参考文献:

1.https://zhuanlan.zhihu.com/p/27329248

2.http://masutangu.com/2017/06/leveldb_1/

 

LevelDB的源码阅读(一)

标签:宕机   namespace   ast   逻辑   选择   mmu   释放   keep   官方文档   

人气教程排行