ITPub博客

首页 > 数据库 > NoSQL > leveldb初识

leveldb初识

原创 NoSQL 作者:hotdog04 时间:2015-07-10 09:24:20 0 删除 编辑

 

【1】leveldb的特点:
1、持久化存储的KV系统,不会狂吃内存,大部分数据落盘
2、所有的key有序存储
3、结构简单,写,读,删除,多条操作的原子批量操作
4、支持数据库快照,读操作不受写操作影响,且读操作过程始终数据一致
5、支持数据压缩
6、数据写操作使用跳表数据结构(skiplist),这使得写操作远大于读操作
 官方测试: 随机写:40w/s; 随机读:6w/s。顺序读写大大快于随机读写

【2】levledb的整体架构:
主要6部分组成:
1、MemTable(内存结构)
2、Immutable MemTable(内存结构)
3、Current文件(磁盘)
4、Manifest文件(磁盘)
5、log文件(磁盘)
6、SSTable文件(磁盘)
写入原理:
1、leveldb先写入log文件(顺序写)
2、log文件写入成功后再插入MemTable(skiplist结构)
3、当MemTable数据插入到一个限界后,leveldb生成新
   的log文件和Memtable,用于记录新的写入
4、原来的Memtable成为了Immutable MemTable(只读不可写删)
5、leveldb后台调度将Immutable MemTable导入到磁盘生成SStable
   文件
6、SSTable文件是分层的(这就是leveldb名字的来源),存储的
   key是有序的
7、Manifest文件的作用就是记录SSTable相关信息(文件名,key范围等)
8、leveldb进行compaction时,SSTable会发生变化,生成新的,废弃老的,
   在这个过程中,会生成新的Manifest文件来记录SSTable的变化
9、Current文件的作用是记录当前使用的Manifest文件名
以上过程基本上展示运行过程中各个主要组件的职能,以及leveldb的一些特性:
数据安全(先log后memtable保证数据不丢失)
很好的写入性能(log顺序+内存跳表)
数据压缩和数据持久化实现(SSTable和SSTable的逐层合并)

【3】leveldb的日志文件管理:
它的主要作用是系统故障恢复是,保证数据不会丢失。
leveldb对日志文件的基本读取单位是一个物理block,
每一个block大小32K,从物理布局来讲,一个log文件就是
有连续的32K大小的Block组成
每一条保存到日志的操作记录包括以下内容:
checksum值(类型和数据)+记录长度(数据大小)+类型+数据(kv)
类型包括FULL,FIRST,MIDDLE,LAST;它标记了每个记录的逻辑结构
跟log文件物理分块结构的关系,例如:
block A:
checkum 10 fisrt a:100
checkum 10 MIDDLE b:100
checkum 10 FULL c:100
checkum 10 LAST d:100
--end
解释说明: block A中包括了 记录a的前面部分,b的中间部分,c的全部数据,d的结尾部分
然后根据具体情况根据类型来拼接处来逻辑记录,供使用

【4】leveldb的SSTable文件
SSTable是具体的kv磁盘存储文件,内部的key是顺序的,每个文件
分成成固定大小的物理block,每个block的结构如下:
数据存储区(kv和管理数据等)+type(是否压缩)+CRC(数据校验)
文件格式:
block 1 type crc
block 2 type crc
block 3 type crc
... ...

逻辑结构:
数据存储区(kv)+数据管理区(Meta(of))
文件格式:
------------数据存储区
data block1
data block2
data block3
------------数据管理区
Meta block1
Meta block2
Meta block3
Metablock index
index block
footer
----end

【5】leveldb的MemTable
   MemTable是leveldb的写入,删除和读取记录的接口,leveldb
的删除是lazy的,只是对要删除的key做标记(插入操作),后面的
合并压缩的时候会删除这个kv
   MemTable内部的KV是有序的,它的核心数据结构是skiplist,skiplist
的插入和删除都非常简单,这也是leveldb写入性能很好的原因
(redis为了加快插入操作也用了skiplist)

【6】leveldb的写入,删除和读取
写入:首先把记录追加到log文件末尾,然后插入到memtable中即完成了写入
删除:操作跟插入相同,差异就是它插入的不是kv而是key+删除标记,等
      后台做合并压缩的时候才真正的删除
读操作:metable->immutable memtable->level0 SSTable->level1 SSTable->levelN SSTable
    根据查找路径可以得知leveldb查找优先级是越新鲜的优先级越高(最新的版本最优先)
在SSTable中查找的时候,leveldb会优先在内存的cache中找是否有一个文件的缓存记录,有则
从缓存读取,没有则打开SSTable文件,将这个文件的索引部分加载到cache中,然后根据索引
定位到具体的block(可能包含该key),从文件中得到这个block,如果这个block中不存在,就
往下一级的SSTable查找。
   总上,leveldb的写操作非常简单快速,而读操作处理起来要复杂很多,所以leveldb适合写
多读少的场景,如果是读操作类型的,顺序读的效率会比较好,因为大部分内容会在缓存找到,
避免了大量随机读磁盘

【7】leveldb的合并压缩
leveldb的读取记录比较复杂,需要在内存和各层级文件查找,代价高, leveldb的合并压缩
是对已有的记录进行整理压缩,通过这个方式来完成kv的真正删除,和合并,减小数据规模,
减少文件数量等
LevelDb的Compaction包含其中两种,minor和major

minor:从memtable到level 0
       memtable是一个key顺序的skiplist,写入过程就是
       从小到大遍历memtable,写入到level0的SSTable中,然后
      建立文件的index数据,minor合并压缩不会做key删除
major:从低level到高level
合并文件选择:
level0到level1的合并:
  level0是直接memtable的dump,所有可能会出现key重复,所以合并的时候可能会出现多个level0的文件(有重叠)
跟level1进行合并

levelN到levelN+1的合并(N>0):
  因为每个SSTable文件的key范围不会有重叠,只要逐个选levelN的文件跟levelN+1合并即可

合并方式:
  对多个文件采用多路归并排序的方式,对文件的所有记录从新排序,生成新的数据文件,之前的文件清理掉


【8】leveldb的cache
    如果读操作没有在memtable中找到,就可能需要多次的磁盘访问,最好的情况下第一次level0中的文件找到了这个key,
也需要2次磁盘io,第一次是SSTable文件的index部分读入内存,确定到block;第二次是把block读入到内存,定位
到key
    leveldb运入两个cache来降低IO: table cache 和block cache。 block cache配置可选

table cache:它是一个kv结构,key保存的是SSTable文件名,value保存两个信息:SSTable的文件指针,SSTable对应的Table结构指针
            table结构内存中保存了SSTable的index内容以及用来指示block cache用的cache_id

    当一个get操作的时候,leveldb确定到key在某个level下的文件A, leveldb会先查找table cache,如果找到了,根据index部分找到
    block。

block cache是为了加快这个过程的,它也是一个kv结构,key是文件的cache_id+block_offset(在文件总的其实位置), value是这个block的内容
如果leveldb发现这个block在block cache中,就可以避免读取数据,直接在cache的block内容肇东value返回即可,如果没有就会把block内容
插入到block cache中

 通过上面两个cache加快读操作,如果读取的数据局部性好,大部分数据都在cache里面能够找到,读效率还是很高的


参考:
leveldb:http://www.cnblogs.com/haippy/archive/2011/12/04/2276064.html
leveldb:http://www.samecity.com/blog/Index.asp?SortID=12
skiplist:http://blog.sina.com.cn/s/blog_72995dcc01017w1t.html

 


 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/20625855/viewspace-1728427/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2013-03-11

  • 博文量
    59
  • 访问量
    404559