LevelDB技术分享_weixin_34200628的博客-CSDN博客
LevelDB技术分享
weixin_34200628
于 2015-09-06 17:23:00 发布
66
收藏
文章标签：
运维
数据库
数据结构与算法
原文链接：https://my.oschina.net/jet1987/blog/501829
版权
2019独角兽企业重金招聘Python工程师标准>>>
<apa/>
*一.作者和基本情况。
#Google的两位重量级工程师Jeff和Sanjay开发的，是Google大规模分布式平台Bigtable和MapReduce主要设计和实现者。Bigtable是影响深远的分布式存储系统，里面的两个核心的部分：Master Server和Tablet Server。其中Master Server做一些管理数据的存储以及分布式调度工作，实际的分布式数据存储以及读写操作是由Tablet Server完成的，而LevelDB则可以理解为一个简化版的Tablet Server。
*二.特性和应用场景。
#针对大规模Key/Value数据的单机存储库，能够处理十亿级别规模的数据持久性存储的C++程序库，用了Google自身的tcmalloc内存模块和Snappy快速压缩。
#接口简单，包括读，写，删（后面会降到，其实它的删是一种写操作），支持原子批量操作，支持数据快照功能，支持数据压缩。它和Redis这种内存型的KV系统不同，LevelDB不会像Redis一样狂吃内存，而是将大部分数据存储到磁盘上。
#随机写性能达到40万条记录每秒，而随机读性能达到6万条记录每秒。在小文件存储方面比SQLite3等都块。总体来说，LevelDB的写操作要大大快于读操作，而顺序读写操作则大大快于随机读写操作。
#应用场景：小数据，快速压缩存储，批处理写，写操作多于读操作，重复读取局部性数据。
*三.整体架构
**画下图
#写入数据的过程：Log：一次顺序的磁盘写。成功后，Memtable：一次内存写入。这样基本就算完成了写入操作，所以这是为何说LevelDB写入速度极快的主要原因。
##Log文件在系统中的作用主要是用于系统崩溃恢复而不丢失数据，假如没有Log文件，因为写入的记录刚开始是保存在内存中的，此时如果系统崩溃，内存中的数据还没有来得及Dump到磁盘，所以会丢失数据（Redis就存在这个问题）。为了避免这种情况，LevelDB在写入内存前先将操作记录到Log文件中，然后再记入内存中，这样即使系统崩溃，也可以从Log文件中恢复内存中的Memtable，不会造成数据的丢失。
##那么怎么保证写log时的系统崩溃，而丢失数据呢？
#Memtable:当Memtable插入的数据占用内存到了一个界限后，需要将内存的记录导出到外存文件中，LevelDB会生成新的Log文件和Memtable，原先的Memtable就成为Immutable Memtable，顾名思义，就是说这个Memtable的内容是不可更改的，只能读不能写入或者删除。新到来的数据被记入新的Log文件和Memtable，LevelDB后台调度会将Immutable Memtable的数据导出到磁盘，形成一个新的SSTable文件。
##SSTable:SSTable就是由内存中的数据不断导出并进行Compaction操作后形成的，而且SSTable的所有文件是一种层级结构，第一层为Level 0，第二层为Level 1，依次类推，层级逐渐增高，这也是为何称之为LevelDB的原因。
##SSTable中的文件是Key有序的，就是说在文件中小key记录排在大Key记录之前，各个Level的SSTable都是如此，但是这里需要注意的一点是：Level 0可能存在key重叠，而其他Level不会。后面很多操作的差异都是由于这个原因造成的。
##造成Level0中Key重叠的原因是：从Log到Memtable都是单纯的写，没有去查找，去比较是否有已经存在的Key，那么生成的Level0必定会有重叠的Key。而其他Level不重叠的原因是，从Level0开始，每级递增的Level都是通过合并同级的文件来生成的。
#Manifest：它记载了所有SSTable各个文件的管理信息，比如属于哪个Level，文件名称叫啥，最小key和最大key各自是多少。当你读取数据没能从MemTable和CacheTable中获取到时，那就只能通过Manifest来找Level文件了。
#Current：因为在LevleDb的运行过程中，随着Compaction的进行，SSTable文件会发生变化，会有新的文件产生，老的文件被废弃，Manifest也会跟着反映这种变化，此时往往会新生成Manifest文件来记载这种变化，那么Current就用来记载当前我们关心的manifest文件名。
*那么现在开始来详细讲解具体的模块：
*四.Log文件
#是由连续的32K为单位的物理Block构成的一个文件。那么数据怎么存储在Log中呢？
#*画图
##比如我们有2个KV数据对象。以Record的信息存入。包括：头（CheckSum + 记录长度 + 类型） 和 数据
##第一个KV对象，比较小，加入一个头，头中的类型标记为FULL，New第一个Log，把数据放入。
##第二个KV对象，比较大，那么把KV数据的前一部分加上头，类型标记为FIRST，放入第一个Log中。但是剩下的数据还是大于一个Log，那么截图一部分KV数据+头，类型为MIDDLE，New一个Log，然后把刚才的数据放入，最后，再New一个Log，将最后的KV数据 + 头，类型为LAST，放入。
##当第二个KV对象，够放入第二个Log时，直接使用LAST类型。
*五.MemTable
#当写入Log成功后，会将KV对象写入MemTable，前面讲过这两个过程是基本的写入数据过程，而Log的功能是防止系统崩溃时，内存MemTable中的数据丢失。
#当MemTable数据占用内存到达指定数量，则自动转换为不可写Immutable Memtable，等待Dump到磁盘中生产Level文件。
#MemTable提供了将KV数据写入，删除以及读取KV记录的操作接口，但是事实上Memtable并不存在真正的删除操作,删除某个Key的Value在Memtable内是作为插入一条记录实施的，但是会打上一个Key的删除标记，真正的删除操作是Lazy的，会在以后的Level文件的Compaction过程中去掉这个KV。
#Memtable中KV对是根据Key大小有序存储的，核心数据结构是一个SkipList。SkipList是平衡树的一种替代数据结构，但是和红黑树不相同的是，SkipList对于树的平衡的实现是基于一种随机化的算法的，这样也就是说SkipList的插入和删除的工作是比较简单的。
#SkipList不仅是维护有序数据的一个简单实现，整体而言是个高写入系统，SkipList在其中应该也起到了很重要的作用。Redis为了加快插入操作，也使用了SkipList来作为内部实现数据结构。
#跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了Next的指针，从而提升查找的效率。
*而且相比较平衡树来说，在插入数据的时候可以避免频繁的树节点调整操作，所以写入效率是很高的。（这样说，不是表面了比树快么？没有充分的证据来说服我，因为Linux内核依然在使用红黑树，SkipList在1990年就发表了，如果比树优秀，Linux却不选择SkipList，原因只有一个，SkipList是牺牲空间来换取速度的，不适合Linux）
SkipList，可参考http://www.cnblogs.com/xuqiang/archive/2011/05/22/2053516.html
*六.SSTable
#所有Level文件内部布局是一样的，和Log文件一样是物理分块的，这个大小是可以配置的，不同的是Log中的KV对象是顺序放入，而Level文件是Key由小到大排列的。
##画下Level文件的结构 数据存储区 + 数据管理区 + Type + CRC
##Type表示是否使用Snappy压缩，CRC部分则是数据校验码，用于判别数据是否在生成和传输中出错。
##数据存储区存放实际的Key:Value数据，数据管理区则提供一些索引指针等管理数据，目的是更快速便捷的查找相应的记录。
#数据存储区：按照Key由小到大排列的KV对。Data Block = Block 内容（Record） + Block 尾部（Restart + Num）
##Block 内容：KV记录，其顺序是根据Key值由小到大排列的
##Block 尾部：指向KV记录的指针，重启点。
##因为有序，Key部分有重叠，为了节省存储Key的空间，所以用了重启点。
##画图讲下重启点，以及如果去重叠的。
##Record = Key共享长度 + key非共享长度 + Value长度 + Key非共享内容 + Value内容
#数据管理区：Meta Block + Meta Block Index + Index Block + Footer
##Meta Block未使用，Footer是索引的索引，是为了正确读出索引值而设立的，还有一些预留项。
##画图讲下数据索引。
##<nowiki>Data block i<wiki>
##<nowiki>Data block i+1<wiki>
##<nowiki>Key i:"word"  Offset i Size i <wiki>
##<nowiki>Key i+1:"zipf"  Offset i + 1 Size i + 1 <wiki>
##<nowiki>>= i中最大的Key，且要<i+1的最小Key i的起始位子 i的大小<wiki>
*七.Compaction
#前面说过，生成的Level0有重叠的Key。而其他Level不重叠就是采取了compaction的方式来对已有的记录进行整理压缩，通过这种方式，来删除掉一些不再有效的KV数据，减小数据规模，减少文件数量等。
#levelDb的compaction机制和过程与Bigtable所讲述的是基本一致的，Bigtable中讲到三种类型的compaction: minor ，major和full。所谓minor Compaction，就是把memtable中的数据导出到SSTable文件中；major compaction就是合并不同层级的SSTable文件，而full compaction就是将所有SSTable进行合并。LevelDb包含其中两种，minor和major。
##minor：immutable memtable的SkipList到Level0，很简单的把原来排序的KV对写入Level0，建立数据管理区的Index。
##major：一个Level的文件数据达到预设值时，与Level+1的文件合并。为了保证何必后的Level都有序，合并时需要将Level中的key range找到Level+1在这个范围内的文件。注意：Level0合并到Level1时，因为Level0本身有重叠，而Level1以后都不重叠，所以，合并Level0时，要将所有重叠的Level0都一起合并。
#levelDb在选定某个level进行compaction后，还要选择是具体哪个文件要进行compaction，levelDb在这里有个小技巧， 就是说轮流来，比如这次是文件A进行compaction，那么下次就是在key range上紧挨着文件A的文件B进行compaction，这样每个文件都会有机会轮流和高层的level 文件进行合并。
##如果选好了level L的文件A和level L+1层的文件进行合并，那么问题又来了，应该选择level L+1哪些文件进行合并？levelDb选择L+1层中和文件A在key range上有重叠的所有文件来和文件A进行合并。
##L ，L+1， L+1, L+1  -〉多路归并排序，多个文件重新排序，一定的标准判断是否保存-〉一系列新的L+1层数据文件
#*其中一个标准是:对于某个key来说，如果在小于L层中存在这个Key，那么这个KV在major compaction过程中可以抛掉。（不是很明白怎么做到的）
*八.写入与删除记录
#对于一个插入操作来说，完成插入操作包含两个具体步骤：首先是将这条KV记录以顺序写的方式追加到之前介绍过的log文件末尾，因为尽管这是一个磁盘读写操作，但是文件的顺序追加写入效率是很高的，所以并不会导致写入速度的降低；第二个步骤是:如果写入log文件成功，那么将这条KV记录插入内存中的Memtable中，前面介绍过，Memtable只是一层封装，其内部其实是一个Key有序的SkipList列表，插入一条新记录的过程也很简单，即先查找合适的插入位置，然后修改相应的链接指针将新记录插入即可。完成这一步，写入记录就算完成了，所以一个插入记录操作涉及一次磁盘文件追加写和内存SkipList插入操作，这是为何levelDb写入速度如此高效的根本原因。
#对于一个删除操作，对于levelDb来说，并不存在立即删除的操作，而是与插入操作相同的，区别是，插入操作插入的是Key:Value 值，而删除操作插入的是“Key:删除标记”，并不真正去删除记录，而是后台Compaction的时候才去做真正的删除操作。所以LevelDB没有“更新”操作，你可以直接使用插入操作。
*九.读取记录
#画图，讲解读取顺序，新鲜度。
#Memtable（1）->Immutable Memtable（1）->Level 0（N）->Level 1（N）->...->Level N（N）
##前3个地方，各级内部是会出现重复Key的，前两个中，有序排列的，又只有一个SkipList的，那么获取到最新的数据很方便。
##Level 0则是根据映射表排序的文件新鲜程序来依次查找。
##当打开Level文件查找数据之前，有一个Cache的机制，来缓存打开过的文件，后面一节会讲到。
#写入的方式，导致最新的数据在越前面。所以这个数据的冗余是很大的，但是这整个读写结构，大大加快了读取与写入时间。
#思考点：如果数据刚放入Log，而没有在Memtable中呢？是否有同步控制？
*十.Cache
#Table Cache和Block Cache（配置可选的）
##Table Cache = Key(SSTable文件名) + Value（SSTable文件指针 + （SSTable文件结构体中的Index内容 + Block Cache ID + 其他））
#通过Index找到Key对应的Block后，还要再次从文件中读取Block内容。为了加快这个过程，诞生了Block Cache。
##Block Cache = ID + Offset + Block 内容
#从Cache的机制可以看出，LevelDB侧重于重复读取局部性数据。
*十一.Version、VersionEdit、VersionSet
#Version 保存了当前磁盘以及内存中所有的文件信息，一般只有一个Version叫做"current" version（当前版本）。Leveldb还保存了一系列的历史版本，这些历史版本有什么作用呢？
#当一个Iterator创建后，Iterator就引用到了current version(当前版本)，只要这个Iterator不被delete那么被Iterator引用的版本就会一直存活。这就意味着当你用完一个Iterator后，需要及时删除它。
#当一次Compaction结束后（会生成新的文件，合并前的文件需要删除），Leveldb会创建一个新的版本作为当前版本，原先的当前版本就会变为历史版本。
#VersionSet 是所有Version的集合，管理着所有存活的Version。
#VersionEdit 表示Version之间的变化，相当于delta 增量，表示有增加了多少文件，删除了文件。
##Version0 + VersionEdit -> Version1
#VersionEdit会保存到MANIFEST文件中，当做数据恢复时就会从MANIFEST文件中读出来重建数据。
#leveldb的version管理和双buffer切换类似，双buffer切换来自于图形学中，用于解决屏幕绘制时的闪屏问题，在服务器编程中也有用处。但是如果原version被某个iterator引用，那么这个version会一直保持，直到没有被任何一个iterator引用，此时就可以删除这个version。
转载于:https://my.oschina.net/jet1987/blog/501829
weixin_34200628
关注
关注
点赞
收藏
评论
LevelDB技术分享
2019独角兽企业重金招聘Python工程师标准>>> ...
复制链接
扫一扫
lev, 用于管理LevelDB实例的完整 REPL & CLI.zip
10-10
lev, 用于管理LevelDB实例的完整 REPL & CLI 状态 概要一个简单而方便的命令行工具和 REPL leveldb 。特性带彩色标签补全和 zsh/fish风格关键建议REPL自动保存和重新加载替换历史记录屏幕截图 安装$ npm install -g l
（封装）已知的一个类Student
最新发布
heliuerya的博客
11-17
237
（封装）已知的一个类Student 封装练习 get和set方法的提供
参与评论
您还未登录，请先
登录
后发表或查看评论
LevelDB源码分析之二：comparator
草上爬的博客
12-18
2220
这里的comparator包括抽象类Comparator及其两个实现类：一个是内置的BytewiseComparatorImpl，另一个是InternalKeyComparator。
一.Comparator
Comparator只是导出了几个接口。
class Comparator {
public:
virtual ~Comparator();
// Three-way c
LevelDB库简介
weixin_34183910的博客
10-15
1539
LevelDB库简介
一、LevelDB入门
LevelDB是Google开源的持久化KV单机数据库，具有很高的随机写，顺序读/写性能，但是随机读的性能很一般，也就是说，LevelDB很适合应用在查询较少，而写很多的场景。LevelDB应用了LSM (Log Structured Merge) 策略，lsm_tree对索引变更进行延迟及批量处理，并通过一种类似于归并排序的方式高...
LevelDB使用指南
热门推荐
ZkvIA的博客
10-15
1万+
这篇文章是levelDB官方文档的译文，原文地址:LevelDB library documentation这篇文章主要讲leveldb接口使用和注意事项。
leveldb是一个持久型的key-value数据库。key,value可以是任意的字节数组，key之间是有序的。key的比较函数可以由用户指定。1. 打开数据库leveldb使用文件系统目录名作为name,并把数据库所有内容都存储在这个目录
leveldb源码学习之 DBImpl 类（数据写入）
guangyacyb的博客
04-02
245
推荐结合leveldb-handbook 阅读源码
leveldb以其优秀的写性能著名
整体流程
leveldb的一次写入分为两部分：
将写操作写入日志；
将写操作应用到内存数据库中；
写类型
leveldb对外提供的写入接口有：（1）Put（2）Delete两种。这两种本质对应同一种操作，Delete操作同样会被转换成一个value为空的Put操作。
除此以外，leveldb还...
levelDB 的总结
对酒当歌
08-19
858
1.内存管理类Arena 的实现:
Arena每次按kBlockSize(static const int kBlockSize = 4096;)单位向系统申请内存，提供地址对齐的内存，记录内存使用。当memtable 申请内存时，如果size小于预留内存，直接使用预留的;如果大于预留，需要重新分配内存块，若需求内存大小小于kBlockSize的四分之一，则分配kBlockSize大小，将剩余的记
leveldb.net对象读写封装
weixin_33872566的博客
08-22
83
为什么80%的码农都做不了架构师？>>>
...
技术分享（五）- leveldb源码阅读之概述与LSM-Tree
qq_19257541的博客
04-26
209
文章目录前言概述使用场景谈谈LSM-Tree一些问题点细节关于WAL Log的故障恢复问题细节为什么memtable选用跳表而不是平衡树（如红黑树）？为什么LSM不直接顺序写入磁盘，而是需要在内存中缓冲一下？SSTable分层越多，最坏的情况是将所有分层都扫描一次，leveldb如何去优化这种情况？B+树 VS LSM-树从对事务支持的角度来看B+树的特点LSM-树的特点一个简单使用例子
前言
本文为之前阅读leveldb源码时，结合网上一些博客见解以及自己的理解组合成的一篇文章，本文会从总体以及主要的数据
技术分享（六）- leveldb源码阅读之设计模式
qq_19257541的博客
04-26
110
文章目录前言综述迭代器模式简述leveldb的应用建造者模式简述leveldb的应用
前言
本文为针对leveldb使用的一些设计模式去谈谈自己的理解，里面挑选了迭代器模式与建造者模式，这两个较为常见的设计模式，进行简单谈谈。本文可能会有引用到一些文章的内容，如果有发现，请联系我这边在文末补全。
综述
谈到软件工程，总是绕不开设计模式的。当编写的工程量大的时候，总会在不经意间使用到了一些设计模式。
个人认为，设计模式是为旧代码重构、新代码编写提供一系列拥有较高可拓展性、可维护性、可复用的解决方案。尤其是在旧
linux leveldb centos,CentOS下安装leveldb
weixin_39712969的博客
05-16
120
一、leveldb是什么Leveldb是一个google实现的非常高效的kv数据库，目前的版本1.2能够支持billion级别的数据量了。 在这个数量级别下还有着非常高的性能，主要归功于它的良好的设计。特别是LSM算法。二、leveldb安装(2)解压安装包到指定目录、重命名：tar -zxvf leveldb-1.20.tar.gz -C /usr/local/cd /usr/localmv l...
初识：LevelDB
yizhiweiyan的博客
07-14
164
本文让你搞懂LevelDB是啥，有啥特性，源码如何编译，源码如何调试等等~
LevelDB中用到的技术
csds319的博客
05-16
352
先总结一下leveldb中用到技术，然后再一个个研究一下SkipList：memtable中使用了skiplist技术BigTable：compaction用到了bigtable中的minor和major compactionSnappy：leveldb中存储用到了snappy压缩技术Bloom Filter：查找key的时候使用了该技术加速查找...
【存储引擎】LevelDB 概述
_山月
11-03
559
从系统结构、读写流程、合并流程、适用场景对 LevelDB 作一个概述，作为后续文章的基础
leveldb原理和使用
sizhi_xht的博客
08-31
1125
LevelDB是一个基于本地文件的存储引擎，非分布式存储引擎，原理基于BigTable（LSM文件树），无索引机制，存储条目为Key-value。适用于保存数据缓存、日志存储、高速缓存等应用，主要是避免RPC请求带来的延迟问题。在存取模型上，顺序读取性能极高，但是对于随机读取的情况延迟较大（但性能也不是特别低），比较适合顺序写入（key），随机的key写入也不会带来问题。数据存量通常为物理内存的3~5倍，不建议存储过大的数据，在这个数据量级上，leveldb的性能比那些“分布式存储”要高（即本地磁盘存取延迟
leveldb源码学习——系统函数封装Env
longzuo
10-03
531
Env是一个接口类，提供了基本的系统访问接口，如操作文件，线程等。
leveldb在util中实现了PosixEnv，实现上述接口首先定义了几个基本类型SequentialFile，提供顺序读方法的接口类
RandomAccessFile，提供随机读方法的接口类
WritableFile， 提供顺序写方法的接口类Env接口类定义了以下接口
创建文件句柄读文件
顺序读句柄
随机读句柄
创建
Leveldb学习笔记：leveldb的使用与原理探究
追梦
11-14
314
Leveldb是一个持久化存储的KV系统。
实际上，它就是我们平时说的底层存储引擎，或者说是一个数据库，我们平时所熟知的redis底层用到存储引擎rocketdb就是从leveldb上演化过来的。
LevelDB是什么？为什么我们需要K-V存储？
凌桓丶的博客
03-28
1860
LevelDB 是一个由 Google 公司所研发的 K-V 存储嵌入式数据库管理系统编程库，以开源的 BSD 许可证发布。其作为 LSM Tree 的经典实现，具有很高的随机写，顺序读/写性能，但是随机读的性能很一般，也就是说，LevelDB很适合应用在查询较少，而写很多的场景。
“相关推荐”对你有帮助么？
非常没帮助
没帮助
一般
有帮助
非常有帮助
提交
©️2022 CSDN
皮肤主题：大白
设计师：CSDN官方博客
返回首页
weixin_34200628
CSDN认证博客专家
CSDN认证企业博客
码龄7年
暂无认证
143
原创
周排名
82万+
总排名
106万+
访问
等级
6755
积分
5361
粉丝
207
获赞
18
评论
1228
收藏
私信
关注
热门文章
Cannot read property 'map' of undefined
17495
权力的游戏第一季/全集Game of Thrones迅雷下载
15705
Google的一个代理网站： 仅限技术搜索
11257
C++ Sleep() sleep()
8989
Python发送邮件(最全)
7594
最新评论
听说尤雨溪在开发vue4.0？是谁煽动了前端圈的焦虑情绪
寻求前端工作的小师弟:
编程也就图一乐 收收准备去电子厂打螺丝了
python反编译chm文件并生成pdf文件
Suozhanghjl:
注意作者这里没有为pdfkit配置wkhtmltopdf，具体配置可以查看https://zhuanlan.zhihu.com/p/94608155
二叉树的操作之统计二叉树中节点的个数
weixin_45765737:
int g_nMax = 0;
voild RootFirst(TreeNode *p,int nLevel)
if (null == p->left && null == p->right) //当前为叶子节点
if (g_nMax < nLevel)
g_nMax = nLevel;
return;
if(null != p->left )
RootFirst(p->left,nLevel+1);//遍历左子树
if(null != p->right)
RootFirst(p->right,nLevel+1);//遍历右子树
苏宁 11.11：仓库内多 AGV 协作的全局路径规划算法研究
识堂干饭BOSS高:
董工，这是哪篇论文的内容哈？
从八道面试题看JavaScript DOM事件机制
wangmeng_7:
第七题 我打出来的结果是2，1呀
您愿意向朋友推荐“博客详情页”吗？
强烈不推荐
不推荐
一般般
推荐
强烈推荐
提交
最新文章
Limit point, Accumulation point, and Condensation point of a set
微软最新社会招聘职位列表
XMLHTTP的常用方法和属性
2019年388篇
2018年693篇
2017年927篇
2016年511篇
2015年401篇
2014年364篇
2013年309篇
2012年277篇
2011年191篇
2010年120篇
2009年130篇
2008年92篇
2007年68篇
2006年42篇
2005年20篇
2004年11篇
2003年1篇
目录
目录
最新文章
Limit point, Accumulation point, and Condensation point of a set
微软最新社会招聘职位列表
XMLHTTP的常用方法和属性
2019年388篇
2018年693篇
2017年927篇
2016年511篇
2015年401篇
2014年364篇
2013年309篇
2012年277篇
2011年191篇
2010年120篇
2009年130篇
2008年92篇
2007年68篇
2006年42篇
2005年20篇
2004年11篇
2003年1篇
目录
评论
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
查看更多评论
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额
抵扣说明：
1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。 2.余额无法直接购买下载，可以购买VIP、C币套餐、付费专栏及课程。
余额充值