庖丁解LevelDB之整体感知

【限时免费】岁尾最强一次云计算大年夜会，看传统、社区、互联网企业若何碰撞？

【编辑推荐】

EMC中国区市场总监讲述信息安然的新思路
备份带库基本概览
七牛助力“互联网＋教导” 除了在线课程还有更多新思路
同有全闪存阵列设计新思路：一硬到底！
分布式架构体系生成全局独一序列号的一个思路

【义务编辑：武晓燕 TEL：（010）68476606】

LevelDB是Google传奇工程师Jeff Dean和Sanjay Ghemawat开源的KV存储引擎，无论大年夜设计照样代码上都可以用精细优雅来形容，异常值得细细咀嚼。本文将大年夜设计思路、整体构造、读写流程、紧缩流程几个方面来进话旧绍，大年夜而可以或许对LevelDB有一个整体的感知。

设计思路

LevelDB的数据是存储在磁盘上的，采取LSM-Tree的构造实现。LSM-Tree将磁盘的随机写转化为次序写，大年夜而大年夜大年夜进步了写速度。为了做到这一点LSM-Tree的思路是将索引树构造拆成一大年夜一小两颗树，较小的一个常驻内存，较大年夜的一个持久化稻磁逄，他们合营保护一个有序的key空间。写入操作会起首操作内存中的树，跟着内存中树的赓续变大年夜，会触发与磁盘中树的归并操作，而归并操作本身仅有次序写。如下图所示：

LSM示意

跟着数据的赓续写入，磁盘中的树会赓续膨胀，为了避免每次介入归并操作的数据量过大年夜，以及优化读操作的┞峰酌，LevelDB将磁盘中的数据又拆分成独裁，每一层的数据达到必定容量后会触发向下一层的归并操作，每一层的数据量比其上一层成倍增长。这也就是LevelDB的名称来源。

整体构造

具体到代码实现上，LevelDB有几个重要的角色，包含对应于上文提到的内存数据的Memtable，分层数据存储的SST文件，版本控制的Manifest、Current文件，以及写Memtable前的WAL。这里简单介绍各个组件的感化和在全部构造中的地位。

Memtable：内存数据构造，跳表实现，新的数据会起首写入这里；
Log文件：写Memtable前会先写Log文件，Log经由过程append的方法次序写入。Log的存在使得机械宕机导致的内存数据损掉得以恢复；
Immutable Memtable：达到Memtable设置的容量上限后，Memtable会变为Immutable为之后向SST文件的归并做预备，顾名思义，Immutable Mumtable不再接收用户写入，同时话苄新的Memtable生成；
SST文件：磁盘数据存储文件。分为Level 0到Level N独裁，每一层包含多个SST文件；单个SST文件容量随层次增长成倍增长；文件内数据有序；个中Level0的SST文件由Immutable直接Dump产生，其他Level的SST文件由其上一层的文件和本层文件归并产生；SST文件在归并过程中次序写生成，生成后仅可能在之后的归并中被删除，而不会有任何的修改操作。
Manifest文件： Manifest文件中记录SST文件在不合Level的分布，单个SST文件的最大年夜最小key，以及其他一些LevelDB须要的元信息。
Current文件: 大年夜膳绫擎的介绍可以看出，LevelDB启动时的重要义务就是找到当前的Manifest，而Manifest可能有多个。Current文件简单的记录了当前Manifest的文件名，大年夜而让这个过程变得异常简单。

LevelDB 构造

读写操作

1，写流程

LevelDB的写操作包含设置key-value和删除key两种。须要指出的是这两种情况在LevelDB的处理上是一致的，删除操作其实是向LevelDB插入一条标识为删除的数据。下面就一路看看LevelDB插入值的过程。

数据紧缩是LevelDB中重要的部分，即上文提到的归并。冷数据会跟着Compaction赓续的下移，同时过时的数据也会在归并过程中被删除。LevelDB的紧缩操作由零丁的后台线程负责。这里的Compaction包含两个部分，Memtable向Level0 SST文件的Compaction，以及SST文件向基层的Compaction，对应于两个比较重要的函数：

LevelDB对外裸露的写接口包含Put，Delete和Write，个中Write须要WriteBatch作为参数，而Put和Delete起首就是将当前的操作封装到一个WriteBatch对象，并调用Write接口。这里的WriteBatch是一批写操作的集合，其存在的意义在于进步写入效力，并供给Batch内所有写入的原子性。

在Write函数中会起首用当前的WriteBatch封装一个Writer，代表一个完全的写入请求。LevelDB加锁包管同一时刻只能有一个Writer工作。其他Writer挂起等待，直到前一个Writer履行完毕后唤醒。单个Writer履行过程如下：

Status status = MakeRoomForWrite(my_batch == NULL); 
uint64_t last_sequence = versions_->LastSequence(); 
Writer* last_writer = &w; 
if (status.ok() && my_batch != NULL) { 
  WriteBatch* updates = BuildBatchGroup(&last_writer); 	
			 1/2    1 2 下一页 尾页	
			

　　推荐阅读
　　Firefox 将跟进把 HTTP 传输的网站全部列为不安全
相干链接
            【限时免费】岁尾最强一次云计算大年夜会，看传统、社区、互联网企业若何碰撞？
            Google 在 HTTPS 的推动上可谓下足了工夫，客岁9月就曾宣布将慢慢下调 Chrome 浏览器对 HTTP 网站的>>>详细阅读


本文标题：庖丁解LevelDB之整体感知
地址：http://www.17bianji.com/lsqh/39969.html
 1/2    1