XiaoLong's Blog

leveldb1.2源码剖析--Compation

Compaction操作是LSM的核心，所谓Compaction就是将现有的SST文件进行压缩合并，生成新SST文件过程。 Compaction操作的主要目的有两个: 通过减少文件的增长量来保证读操作的性能通过合并文件来删除相同Key的重复更新的或者删除的Key。由于与Compaction相关的逻辑贯穿在整个LevelDB代码库，扣起细节来会太过繁琐，所以本文力求在整体上对...

Posted by gao-xiao-long on March 5, 2017

leveldb1.2源码剖析--版本管理(Version)

在LevelDB中，LSM树由一系列的SST文件组成。每一次Compaction操作后，都会生成新的SST文件，合并完成之后，合并输入文件(input files)则可以丢弃。但是有可能get或者迭代器操作还需要这些input files。所以，这些文件不能立刻删除。需要等get操作执行完成或者迭代器释放之后才可以删除。为了管理这一系列的SST文件，LevelDB引入了版本(Version)...

Posted by gao-xiao-long on February 26, 2017

leveldb1.2源码剖析--查找记录(Get)

相对于Put操作，LevelDB在查找Key时比较复杂，会先在Memtable中查找，如果Memtable中包含要查找的Key，直接返回，否则到Immutable Memtable中读取。如果还是没有找到的话则会在一系列SSTable文件中查找，在SSTable文件中查找的原则是先从Level0文件查找，没有的话再从Level1文件，直到最高的Level中查找。为什么会选择以上的查找路径...

Posted by gao-xiao-long on October 30, 2016

leveldb1.2源码剖析--插入记录(Put)

LevelDB插入一条记录时，采用WAL(write ahead logging)方式，先顺序写到磁盘日志中，然后写入Memtable。这种方式可以保证程序异常结束后数据不丢失，并且由于采用了顺序写+内存写的方式，写性能很高。 LevelDB支持单条写以及批量写的操作,用法分别如下: 一次插入单条记录 db->Put(leveldb::WriteOptions(), key2, ...

Posted by gao-xiao-long on October 4, 2016

leveldb1.2源码剖析--Memtable

Memtable是LevelDB中基于内存的数据结构。当应用写入(Put)一条记录的时候，应用会先将此记录追加到Log文件中，之后再插入Memtable。得益于每次写入操作只会顺序写一次磁盘及写一次内存，LevelDB的写性能很高。当Memtable占用的内存达到指定阈值后，LevelDB会生成新的Log文件及Memtable文件，并将原来的 Memtable转化为Immutable Me...

Posted by gao-xiao-long on September 24, 2016

leveldb1.2源码剖析--SSTable

SSTable为Sorted String Table的简称，用来存储一系列有序Kev-Value对。LevelDb中不同层级下有多个SSTable文件(.sst)，下面介绍单个SSTable文件的静态结构。单个SSTable文件的格式如上图所示，文件由五大部分组成：Data Blocks, Meta Block, Meta Index Block, Data Index Block...

Posted by gao-xiao-long on August 7, 2016

leveldb1.2源码剖析--Log Format

LevelDB中日志文件(*.log)存储了对DB的更新操作，log文件的主要作用是防止系统崩溃后数据的丢失。每次write操作，都会先写log文件，再记入内存中，这样即使系统崩溃，也可以从log文件中恢复数据。 log文件格式 log文件由一系列的block组成，每个block大小为32KB。每个block包含一个或者多个记录(record)。记录的格式为: checksu...

Posted by gao-xiao-long on June 20, 2016

leveldb1.2源码剖析--通用模块(Cache)

leveldb默认使用LRU(least recently used)缓存策略。构造LRU cache的基本数据结构主要有 LRUHandle // 底层数据结构，被索引的实体信息，包含key、value、引用次数等 HandleTable // 底层数据结构，索引LRUHandle的哈希表 LRUCache // 以LRUHandle及HandleTable为基础的LRU...

Posted by gao-xiao-long on May 13, 2016

leveldb1.2源码剖析--通用模块(Arena)

leveldb util目录中提供了通用功能的实现，比如内存管理(arena), 布隆过滤器(bloom), cache等，下面对这内存管理器Arena进行分析 Arena arena是leveldb中实现的一个简单的内存管理器, 对外部暴露如下三个接口: char* Allocate(size_t bytes); // 分配指定大小内存 char* AllocateAligned(s...

Posted by gao-xiao-long on May 5, 2016

leveldb前奏--理解文件I/O

本文分topic讲解Linux环境下文件I/O中涉及到的知识点，温故知新，更深刻的了解文件I/O topic1: 硬盘构造(为什么磁盘顺序读写比随机读写更快) 传统磁盘是由盘片构成，每个盘片表面都覆盖着磁性记录材料。盘片中央有一个可以旋转的主轴，它使得盘片以固定的旋转速率(rotational rate)旋转，通常是5400 ~ 15000转每分钟(Revolution Per Minu...

Posted by gao-xiao-long on April 13, 2016

Custom Theme JavaScript