LevelDB剖析(7):并发模型 和 MVCC

LevelDB是线程安全的,即在同一进程内允许用户起多个线程并发调用同一DB实例上的任何接口,但这并不意味着相应吞吐和性能的提升. 我们最后来看下LevelDB支持的并发模型以及其性能瓶颈所在.

下图再次展示了LevelDB上的几个主要操作以及涉及到的结构:
leveldb_concurrecy

1) Compaction是内部线程,恒为1个;Read/Write以及Compaction自身触发产生的Compaction请求在线程内排队处理.
2) Compaction与Read/Write等操作不存在互斥问题,因此其主要瓶颈在于文件系统IO
3) Write操作既要写log......

继续阅读

LevelDB剖析(6):Iterator 和 Snapshot

一、Iterators Done Right
LevelDB中不少场景都存在遍历记录的需求,如:
1) Get:在Block内“遍历”查找某个key
2) Compaction:遍历所有输入table文件,并合并输出
3) DB提供的遍历所有数据的外部接口

某些流程可能比较复杂,比如考虑如何实现3),整体上要对内存、磁盘上的所有数据做遍历+归并去重,memtable和table的遍历机制显然不同,并且level0与其他level又不相同:level0内文件有交集,需要同时参与归并,而level_1及以上则按照key的顺序一个个文件遍历即可;每个文件......

继续阅读

LevelDB剖析(5): Compaction

Compaction是LevelDB的特色所在,其本质是一种内部数据重整机制,而非外部功能接口(用户也可以主动要求发起). 在本系列开篇文章中已经介绍过了Compation操作的背景和分level组织数据的原因,本文就LevelDB中考虑的其他细节问题再来集中整理下.

一、Compaction的目的
1) memtable dump,是table文件的最初来源,并且也相对独立,因此也归到Compaction线程的工作里.
2) 顾名思义,进行冗余数据的合并,控制数据量. 例如某个key更新了10次后最后delete,那么最终这11条记录都可清理掉.
3) 除......

继续阅读

LevelDB剖析(4):Get, Write 和 Recover

前文分别介绍了LevelDB在持久层和内存中的数据组织,现在可以来看看LevelDB中的几个主要接口的流程实现.

一、Get
先简单了解下DB元数据在内存中的内容,主要就是从level到其table文件信息列表的一个映射,文件信息具体包括文件ID(数字标识)、该文件内的最大Key和最小Key、文件大小等. Get流程比较直接,我们按照数据从新到旧的顺序依次从对应位置查找即可:Memtable -> Immutable Memtable(正在Dump的memtable,如果存在) -> Level_0 tables -> Level_1 table -> Level_2 table......

继续阅读

LevelDB剖析(3):memtable和cache

LevelDB内存中除了元数据以外,主要就是memtable和文件cache了. 其中文件cache在功能完整性上是可有可无的,而memtable是完整数据映像的一部分,即用户最新提交的那部分,因此在其落地为table文件之前需要保持稳定高效的读写性服务. 在概念上memtable也可以看做带writeback策略的新数据cache,而log的存在解决了延迟writeback的数据丢失问题;为了避免混淆,本文指的cache都是用于加速查询table文件的cache.

一、memtable
支持高效读写的内存数据结构很多如hash,但memtable不适合用hash实现,因为最终要......

继续阅读