精华内容
下载资源
问答
  • LevelDb

    2019-01-27 19:47:44
    LevelDb
                   

    LevelDb 是 Google 开源的持久化 KV 单机存储引擎。

     

    针对存储面对的普遍随机 IO 问题,leveldb 采用了 merge-dump 的方式,将逻辑场景的写请求转换成顺序写log 和写 memtable 操作,由后台进程将 memtable 持久化成 sstable。

     

    对于读请求,随机 IO 还是无法避免,但它设计了一系列策略来保证读的效率。

     

    1. 特点

     
    1. 键和值都是任意的字节数组
    2.   
    3. 数据根据键排序,排序规则可重载
    4.   
    5. 有三种基本的操作:Put(key,value), Get(key), Delete(key)
    6.   
    7. 支持多个操作组合的原子操作
    8.   
    9. 用户可以创建临时快照,得到一个一致的数据视图
    10.   
    11. 支持向前和向后的数据迭代
    12.   
    13. 数据用Snappy压缩库自动压缩
    14.   
    15. 外部操作(如文件系统操作等)通过一个虚拟接口使用,用户可以对操作系统进行定制相应操作
    16.  

    2. 局限性

     
    1. 这不是一个SQL数据库。它不具有关系数据模型,它不支持SQL查询,也不支持索引
    2.   
    3. 在同一时间只有一个进程(可以是多线程)可以访问一个数据库
    4.   
    5. 有没有客户端-服务器模型的支持
    6.  

    3. 性能

     

    以下是谷歌官方提供的性能测试报告:

     

    3.1 测试环境

     

    LevelDB: version 1.1
    日期: Sun May 1 12:11:26 2011
    CPU: 4 x Intel(R) Core(TM)2 Quad CPU Q6600@2.40GHz
    CPUCache: 4096 KB
    键: 每个16 bytes 
    值: 每个100 bytes(压缩后50 bytes) 元组数目: 1000000
    内存大小: 110.6 MB (估计)
    文件大小: 62.9 MB (估计)

     

    3.2 写的性能

     

    顺序添加 : 1.765 micros/op; 62.7 MB/s 
    同步添加 : 268.409 micros/op; 0.4 MB/s (10000 ops)
    随机添加 : 2.460 micros/op; 45.0 MB/s 
    数据重写 : 2.380 micros/op; 46.5 MB/s 

     

    随机写入的速度可以达到每秒40万条

     

    3.3 读的性能

     

    随机读取 : 16.677 micros/op; (大约每秒6万条)
    顺序读取 : 0.476 micros/op; 232.3 MB/s 
    逆序读取 : 0.724 micros/op; 152.9 MB/s 

     

    如果增加数据压缩后,性能有所提高

     

    随机读取 : 11.602 micros/op; (大约每秒8.5万条)
    顺序读取 : 0.423 micros/op; 232.3 MB/s 
    逆序读取 : 0.663 micros/op; 152.9 MB/s 

     

    如果提供足够的缓存性能还会有所提升

     

    随机读取 : 9.775 micros/op; (不使用压缩大约每秒10万条)
    随机读取 : 5.215 micros/op; (使用压缩大约每秒19万条)

     

    顺序读的性能尤为突出,在每秒230万条以上 

     

    4. 使用方法

     

     

     

    4.1 打开一个数据库

     

    一个leveldb数据库有一个名字对应的文件系统目录,所有数据库的内容存储在此目录中:

     
      
    1 #include <assert>2 #include "leveldb/db.h"3 4 leveldb::DB* db;5 leveldb::Options options;6 options.create_if_missing = true;7 leveldb::Status status = leveldb::DB::Open(options, "/tmp/testdb", &db);8 assert(status.ok());
     
     

    如果你想在数据库已经存在的情况下报错,那需要设置options如下:

     
      
    1 options.error_if_exists = true;
     
     

    4.2 状态

     

    也许您已经到leveldb::Status,这类型可以得到leveldb的大部分功能结果,您可以检查结果是否是ok的,还可以打印相关的错误消息:

     
      
    1 leveldb::Status s = ...;2 if (!s.ok()) cerr << s.ToString() << endl;
     
     

    4.3 关闭数据库

     

    当您对一个数据库的操作完成了,只需删除数据库对象就可以了关闭数据库:

     
      
    1 ... open the db as described above ...2 ... do something with db ...3 delete db;
     
     

    4.4 读和写

     

    leveldb提供了Put,delete,Get方法来修改和查询数据库:

     
      
    1 std::string value;2 leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value);3 if (s.ok()) s = db->Put(leveldb::WriteOptions(), key2, value);4 if (s.ok()) s = db->Delete(leveldb::WriteOptions(), key1);
     
     

    4.5 原子化更新

     

    leveldb提供一个操作序列的原子化:

     
      
     1 #include "leveldb/write_batch.h" 2 ... 3 std::string value; 4 leveldb::Status s = db->Get(leveldb::ReadOptions(), key1, &value); 5 if (s.ok()) { 6     leveldb::WriteBatch batch; 7     batch.Delete(key1); 8     batch.Put(key2, value); 9     s = db->Write(leveldb::WriteOptions(), &batch);10 }
     
     

    除了用于原子化,WriteBatch也可以通过把很多操作放到一起用来加快批更新。

     

    4.6 同步写入

     

    默认情况下,每次写入leveldb是异步的:写入函数只要把写操作交付给操作系统就返回,从操作系统的内存传输到底层的持久性存储是异步的。
    可以打开sync标志来指定某次写操作直到被写入的数据已经被一路推到永久存储时才返回:

     
      
    1 leveldb::WriteOptions write_options;2 write_options.sync = true;3 db->Put(write_options, ...);
     
     

    异步写入的速度往往超过同步写入的一千倍,但异步写的缺点是机器崩溃可能会导致最后的少量更新丢失。同步写可以更新标记,说明崩溃时在何处重新启动。

     

    4.7 并发

     

    一个数据库只能由一个进程打开,而在一个单一的过程中,同一个leveldb:: DB对象可以被多个并发的线程安全地共享。

     

    4.8 迭代

     

    下面的例子展示了如何打印在一个数据库中的所有键值对:

     
      
    1 leveldb::Iterator* it = db->NewIterator(leveldb::ReadOptions());2 for (it->SeekToFirst(); it->Valid(); it->Next()) {3     cout << it->key().ToString() << ": "  << it->value().ToString() << endl;4 }5 assert(it->status().ok());  // Check for any errors found during the scan6 delete it;
     
     

    下面例子显示了如何只处理范围[start,limit)内的键:

     
      
    1 for (it->Seek(start); it->Valid() && it->key().ToString() < limit; it->Next()) {2     ...3 }
     
     

    您也可以以相反的顺序处理条目。 (警告:反向迭代可能会略慢于正向迭代。):

     
      
    1 for (it->SeekToLast(); it->Valid(); it->Prev()) {2     ...3 }
     
     

    4.9 快照

     

    快照提供key-value整个存储状态的只读视图,ReadOptions::snapshot可能非NULL来表明读操作于DB的特定版本状态。
    如果ReadOptions::snapshot是NULL,会对当前状态产生快照。
    快照通过DB::GetSnapshot()方法创建:

     
      
    1 leveldb::ReadOptions options;2 options.snapshot = db->GetSnapshot();3 ... apply some updates to db ...4 leveldb::Iterator* iter = db->NewIterator(options);5 ... read using iter to view the state when the snapshot was created ...6 delete iter;7 db->ReleaseSnapshot(options.snapshot);
     
     

    需要注意的是当一个快照不再需要,要用DB::ReleaseSnapshot方法来释放。 

     

    5. 参数设定

     

    参数可以通过改变include/leveldb/options.h中定义的默认值来设定。
    leveldb 中启动时的一些配置,通过 Option 传入。
    get/put/delete 时,也有相应的ReadOption/WriteOption。

     

    5.1 参数项

     
      
     1 // include/leveldb/option.h 2 Options { 3 // 传入的 comparator 4 const Comparator* comparator; 5 // open 时,如果 db 目录不存在就创建 6 bool create_if_missing; 7 // open 时,如果 db 目录存在就报错 8 bool error_if_exists; 9 // 是否保存中间的错误状态(RecoverLog/compact),compact 时是否读到的 block 做检验。10 bool paranoid_checks;11 // 传入的 Env。12 Env* env;13 // 传入的打印日志的 Logger14 Logger* info_log;15 // memtable 的最大 size16 size_t write_buffer_size;17 // db 中打开的文件最大个数18 // db 中需要打开的文件包括基本的 CURRENT/LOG/MANIFEST/LOCK, 以及打开的 sstable 文件。19 // sstable 一旦打开,就会将 index 信息加入 TableCache,所以把20 // (max_open_files - 10)作为 table cache 的最大数量.21 int max_open_files;22 // 传入的 block 数据的 cache 管理23 Cache* block_cache;24 // sstable 中 block 的 size25 size_t block_size;26 // block 中对 key 做前缀压缩的区间长度27 int block_restart_interval;28 // 压缩数据使用的压缩类型(默认支持 snappy,其他类型需要使用者实现)29 CompressionType compression;30 }31 32 // include/leveldb/option.h33 struct ReadOptions {34 // 是否对读到的 block 做校验35 bool verify_checksums;36 // 读到的 block 是否加入 block cache37 bool fill_cache;38 // 指定读取的 SnapShot39 const Snapshot* snapshot;40 }41 42 // include/leveldb/option.h43 struct WriteOptions {44 // write 时,记 binlog 之后,是否对 binlog 做 sync。45 bool sync;46 // 如果传入不为 NULL,write 完成之后同时做 SnapShot.47 const Snapshot** post_write_snapshot;48 }
     
     

    另外还有一些编译时的常量,与 Option 一起控制:

     
      
     1 // db/dbformat.h 2 namespace config { 3 // level 的最大值 4 static const int kNumLevels = 7; 5 // level-0 中 sstable 的数量超过这个阈值,触发 compact 6 static const int kL0_CompactionTrigger = 4; 7 // level-0 中 sstable 的数量超过这个阈值, 慢处理此次写(sleep1ms) 8 static const int kL0_SlowdownWritesTrigger = 8; 9 // level-0 中 sstable 的数量超过这个阈值, 阻塞至 compact memtable 完成。10 static const int kL0_StopWritesTrigger = 12;11 // memtable dump 成的 sstable,允许推向的最高 level12 // (参见 Compact 流程的 VersionSet::PickLevelForMemTableOutput())13 static const int kMaxMemCompactLevel = 2;14 }15 // db/version_set.cc16 namespace leveldb {17 // compact 过程中,level-0 中的 sstable 由 memtable 直接 dump 生成,不做大小限制18 // 非 level-0 中的 sstable 的大小设定为 kTargetFileSize19 static const int kTargetFileSize = 2 * 1048576;20 // compact level-n 时,与 level-n+2 产生 overlap 的数据 size (参见 Compaction)21 static const int64_t kMaxGrandParentOverlapBytes = 10 * kTargetFileSize;22 }
     
     

    5.2 块大小

     

    leveldb把相邻键码放入相同的块,以这样的块为单元来转移到持久存储中,缺省的块大小约为4096未压缩字节。
    主要是做批量扫描的应用可以通过增加块大小来提高性能。
    使用小于1KB或比高于MB数量级的块大小没有什么好处,而压缩会在块大小较大的条件下更有效。

     

    5.3 压缩

     

    每个块在写入持久存储之前被单独压缩。压缩是缺省的,因为默认的压缩方法是非常快的,不可压缩的数据会自动禁用压缩。
    在少见情况,应用程序可能要完全禁用压缩来改善性能:

     
      
    1 leveldb::Options options;2 options.compression = leveldb::kNoCompression;3 ... leveldb::DB::Open(options, name, ...) ....
     
     

    6. 校验

     

    ReadOptions::verify_checksums可以设置为true来强制读操作对所有数据校验,默认为false
    如果数据库损坏了,leveldb::RepairDB函数可以恢复尽可能多的数据。

     

     

     

     

     

     

     

     

     

     

     

     


    <script type="text/javascript" src="http://pagead2.googlesyndication.com/pagead/show_ads.js"></script>           

    再分享一下我老师大神的人工智能教程吧。零基础!通俗易懂!风趣幽默!还带黄段子!希望你也加入到我们人工智能的队伍中来!https://blog.csdn.net/jiangjunshow

    展开全文
  • Leveldb

    2021-01-06 07:31:03
    <div><p>Leveldb storage engine for Voldemort. Only modifies contrib/leveldb provide jni to leveldb and the storage engine to use it from voldemort Please see the readme for more informations.</p><p>该...
  • LevelDB

    2021-04-09 09:55:02
    目录LevelDB基础读写数据SSTable文件Cache版本控制 LevelDB基础   LevelDB是Google开源的持久化KV单机数据库,具有很高的随机写,顺序读/写性能,但是随机读的性能很一般,即LevelDB很适合应用在查询较少,而写很...

    LevelDB基础

      LevelDB是Google开源的持久化KV单机数据库,具有很高的随机写,顺序读/写性能,但是随机读的性能很一般,即LevelDB很适合应用在查询较少,而写很多的场景。LevelDB应用了LSM (Log Structured Merge) 策略,lsm_tree对索引变更进行延迟及批量处理,并通过一种类似于归并排序的方式高效地将更新迁移到磁盘,降低索引插入开销。LevelDB具有以下特点和限制:

    特点:
    1、key和value都是任意长度的字节数组;
    2、entry(即一条K-V记录)默认是按照key的字典顺序存储的,当然开发者也可以重载这个排序函数;
    3、提供的基本操作接口:Put()、Delete()、Get()、Batch()4、支持批量操作以原子操作进行;
    5、可以创建数据全景的snapshot(快照),并允许在快照中查找数据;
    6、可以通过前向(或后向)迭代器遍历数据(迭代器会隐含的创建一个snapshot);
    7、自动使用Snappy压缩数据;
    8、可移植性;
    
    限制:
    1、非关系型数据模型(NoSQL),不支持sql语句,也不支持索引;
    2、一次只允许一个进程访问一个特定的数据库;
    3、没有内置的C/S架构,但开发者可以使用LevelDB库自己封装一个server;
    

      下图是LevelDB运行一段时间后的存储模型快照:内存中的MemTable和Immutable MemTable以及磁盘上的几种主要文件:Current文件,Manifest文件,log文件以及SSTable文件,以上六个文件和数据结构是LevelDb的主体构成元素。
    在这里插入图片描述
    log文件、MemTable、SSTable文件都是用来存储k-v记录的。针对于manifest和Current文件的作用,SSTable中的某个文件属于特定层级,而且其存储的记录是key有序的,那么必然有文件中的最小key和最大key,这是非常重要的信息,Manifest 就记载了SSTable各个文件的管理信息,比如属于哪个Level,文件名称叫啥,最小key和最大key各自是多少。下图是Manifest所存储内容的示意:
    在这里插入图片描述
      另外,在LevleDb的运行过程中,随着Compaction的进行,SSTable文件会发生变化,会有新的文件产生,老的文件被废弃,Manifest也会跟着反映这种变化,此时往往会新生成Manifest文件来记载这种变化,而Current则用来指出哪个Manifest文件才是我们关心的那个Manifest文件。

    读写数据

    写操作流程:
    1、顺序写入磁盘log文件;
    2、写入内存memtable(采用skiplist结构实现);
    3、写入磁盘SST文件(sorted string table files),这步是数据归档的过程(永久化存储);

    注意:

    • log文件的作用是是用于系统崩溃恢复而不丢失数据,假如没有Log文件,因为写入的记录刚开始是保存在内存中的,此时如果系统崩溃,内存中的数据还没有来得及Dump到磁盘,所以会丢失数据;
    • 在写memtable时,如果其达到check point(满员)的话,会将其改成immutable memtable(只读),然后等待dump到磁盘SST文件中,此时也会生成新的memtable供写入新数据;
    • memtable和sst文件中的key都是有序的,log文件的key是无序的;
    • LevelDB删除操作也是插入,只是标记Key为删除状态,真正的删除要到Compaction的时候才去做真正的操作;
    • LevelDB没有更新接口,如果需要更新某个Key的值,只需要插入一条新纪录即可;或者先删除旧记录,再插入也可;

    读操作流程:
    1、在内存中依次查找memtable、immutable memtable;
    2、如果配置了cache,查找cache;
    3、根据mainfest索引文件,在磁盘中查找SST文件;
    在这里插入图片描述
      举个例子:我们先往levelDb里面插入一条数据 {key=“www.samecity.com” value=“我们”},过了几天,samecity网站改名为:69同城,此时我们插入数据{key=“www.samecity.com” value=“69同城”},同样的key,不同的value;逻辑上理解好像levelDb中只有一个存储记录,即第二个记录,但是在levelDb中很可能存在两条记录,即上面的两个记录都在levelDb中存储了,此时如果用户查询key=“www.samecity.com”,我们当然希望找到最新的更新记录,也就是第二个记录返回,因此,查找的顺序应该依照数据更新的新鲜度来,对于SSTable文件来说,如果同时在level L和Level L+1找到同一个key,level L的信息一定比level L+1的要新。

    log文件

      log文件在LevelDb中的主要作用是系统故障恢复时,能够保证不会丢失数据。因为在将记录写入内存的Memtable之前,会先写入Log文件,这样即使系统发生故障,Memtable中的数据没有来得及Dump到磁盘的SSTable文件,LevelDB也可以根据log文件恢复内存的Memtable数据结构内容,不会造成系统丢失数据,在这点上LevelDb和Bigtable是一致的。
      关于log文件的具体物理和逻辑布局,LevelDb对于一个log文件,会把它切割成以32K为单位的物理Block,每次读取的单位以一个Block作为基本读取单位,下图展示的log文件由3个Block构成,所以从物理布局来讲,一个log文件就是由连续的32K大小Block构成的。
    在这里插入图片描述
    在应用的视野里是看不到这些Block的,应用看到的是一系列的Key:Value对,在LevelDb内部,会将一个Key:Value对看做一条记录的数据,另外在这个数据前增加一个记录头,用来记载一些管理信息,以方便内部处理。
      记录头包含三个字段,CheckSum是对“类型”和“数据”字段的校验码,为了避免处理不完整或者是被破坏的数据,当LevelDb读取记录数据时候会对数据进行校验,如果发现和存储的CheckSum相同,说明数据完整无破坏,可以继续后续流程。“记录长度”记载了数据的大小,“数据”则是上面讲的Key:Value数值对,“类型”字段则指出了每条记录的逻辑结构和log文件物理分块结构之间的关系,主要有以下四种类型:FULL/FIRST/MIDDLE/LAST。如果记录类型是FULL,代表了当前记录内容完整地存储在一个物理Block里,没有被不同的物理Block切割开;如果记录被相邻的物理Block切割开,则类型会是其他三种类型中的一种。

    SSTable文件

      LevelDb不同层级有很多SSTable文件(以后缀.sst为特征),所有.sst文件内部布局都是一样的。Log文件是物理分块的,SSTable也一样会将文件划分为固定大小的物理存储块,但是两者逻辑布局大不相同,根本原因是:Log文件中的记录是Key无序的,即先后记录的key大小没有明确大小关系,而.sst文件内部则是根据记录的Key由小到大排列的。SST文件并不是平坦的结构,而是分层组织的,这也是LevelDB名称的来源。SST文件的一些实现细节:
    1、每个SST文件大小上限为2MB,所以,LevelDB通常存储了大量的SST文件;
    2、SST文件由若干个4K大小的blocks组成,block也是读/写操作的最小单元;
    3、SST文件的最后一个block是一个index,指向每个data block的起始位置,以及每个block第一个entry的key值(block内的key有序存储);
    4、使用Bloom filter加速查找,只要扫描index,就可以快速找出所有可能包含指定entry的block。
    5、同一个block内的key可以共享前缀(只存储一次),这样每个key只要存储自己唯一的后缀就行了。如果block中只有部分key需要共享前缀,在这部分key与其它key之间插入"reset"标识。
    在这里插入图片描述
      上图展示了一个.sst文件的物理划分结构,同Log文件一样,也是划分为固定大小的存储块,每个Block分为三个部分,肉色部分是数据存储区, 蓝色的Type区用于标识数据存储区是否采用了数据压缩算法(Snappy压缩或者无压缩两种),CRC部分则是数据校验码,用于判别数据是否在生成和传输中出错。下图展示了.sst文件的内部逻辑解释。
    在这里插入图片描述
      从大的方面,可以将.sst文件划分为数据存储区和数据管理区,数据存储区存放实际的Key:Value数据,数据管理区则提供一些索引指针等管理数据,目的是更快速便捷的查找相应的记录。两个区域都是在上述的分块基础上的,就是说文件的前面若干块实际存储KV数据,后面数据管理区存储管理数据。管理数据又分为四种不同类型:紫色的Meta Block,红色的MetaBlock 索引和蓝色的数据索引块以及一个文件尾部块。
      由log直接读取的entry会写到Level 0的SST中(最多4个文件);当Level 0的4个文件都存储满了,会选择其中一个文件Compact到Level 1的SST中;注意:Level 0的SSTable文件和其它Level的文件相比有特殊性:这个层级内的.sst文件,两个文件可能存在key重叠,比如有两个level 0的sst文件,文件A和文件B,文件A的key范围是:{bar, car},文件B的Key范围是{blue,samecity},那么很可能两个文件都存在key=”blood”的记录。对于其它Level的SSTable文件来说,则不会出现同一层级内.sst文件的key重叠现象,就是说Level L中任意两个.sst文件,可以保证它们的key值是不会重叠的。

    Log:最大4MB (可配置), 会写入Level 0;
    Level 0:最多4SST文件,;
    Level 1:总大小不超过10MB;
    Level 2:总大小不超过100MB;
    Level 3+:总大小不超过上一个Level ×10的大小。
    

      在读操作中,要查找一条entry,先查找log,如果没有找到,然后在Level 0中查找,如果还是没有找到,再依次往更底层的Level顺序查找;如果查找了一条不存在的entry,则要遍历一遍所有的Level才能返回"Not Found"的结果。在写操作中,新数据总是先插入开头的几个Level中,开头的这几个Level存储量也比较小,因此,对某条entry的修改或删除操作带来的性能影响就比较可控。可见,SST采取分层结构是为了最大限度减小插入新entry时的开销。

    Compaction操作

      对于LevelDb来说,写入记录操作很简单,删除记录仅仅写入一个删除标记就算完事,但是读取记录比较复杂,需要在内存以及各个层级文件中依照新鲜程度依次查找,代价很高。为了加快读取速度,levelDb采取了compaction的方式来对已有的记录进行整理压缩,通过这种方式,来删除掉一些不再有效的KV数据,减小数据规模,减少文件数量等。
      LevelDb的compaction机制和过程与Bigtable所讲述的是基本一致的,Bigtable中讲到三种类型的compaction:minor ,major和full:

    • minor Compaction,就是把memtable中的数据导出到SSTable文件中;
    • major compaction就是合并不同层级的SSTable文件;
    • full compaction就是将所有SSTable进行合并;

    LevelDb包含其中两种,minor和major。Minor compaction 的目的是当内存中的memtable大小到了一定值时,将内容保存到磁盘文件中,如下图:
    在这里插入图片描述
      immutable memtable其实是一个SkipList,其中的记录是根据key有序排列的,遍历key并依次写入一个level 0 的新建SSTable文件中,写完后建立文件的index 数据,这样就完成了一次minor compaction。从图中也可以看出,对于被删除的记录,在minor compaction过程中并不真正删除这个记录,原因也很简单,这里只知道要删掉key记录,但是这个KV数据在哪里?那需要复杂的查找,所以在minor compaction的时候并不做删除,只是将这个key作为一个记录写入文件中,至于真正的删除操作,在以后更高层级的compaction中会去做。
      当某个level下的SSTable文件数目超过一定设置值后,levelDb会从这个level的SSTable中选择一个文件(level>0),将其和高一层级的level+1的SSTable文件合并,这就是major compaction。
      在大于0的层级中,每个SSTable文件内的Key都是由小到大有序存储的,而且不同文件之间的key范围(文件内最小key和最大key之间)不会有任何重叠。Level 0的SSTable文件有些特殊,尽管每个文件也是根据Key由小到大排列,但是因为level 0的文件是通过minor compaction直接生成的,所以任意两个level 0下的两个sstable文件可能再key范围上有重叠。所以在做major compaction的时候,对于大于level 0的层级,选择其中一个文件就行,但是对于level 0来说,指定某个文件后,本level中很可能有其他SSTable文件的key范围和这个文件有重叠,这种情况下,要找出所有有重叠的文件和level 1的文件进行合并,即level 0在进行文件选择的时候,可能会有多个文件参与major compaction。
      LevelDb在选定某个level进行compaction后,还要选择是具体哪个文件要进行compaction,比如这次是文件A进行compaction,那么下次就是在key range上紧挨着文件A的文件B进行compaction,这样每个文件都会有机会轮流和高层的level 文件进行合并。
      如果选好了level L的文件A和level L+1层的文件进行合并,那么问题又来了,应该选择level L+1哪些文件进行合并?levelDb选择L+1层中和文件A在key range上有重叠的所有文件来和文件A进行合并。也就是说,选定了level L的文件A,之后在level L+1中找到了所有需要合并的文件B,C,D……等等。剩下的问题就是具体是如何进行major 合并的?就是说给定了一系列文件,每个文件内部是key有序的,如何对这些文件进行合并,使得新生成的文件仍然Key有序,同时抛掉哪些不再有价值的KV 数据。
    在这里插入图片描述
      Major compaction的过程如下:对多个文件采用多路归并排序的方式,依次找出其中最小的Key记录,也就是对多个文件中的所有记录重新进行排序。之后采取一定的标准判断这个Key是否还需要保存,如果判断没有保存价值,那么直接抛掉,如果觉得还需要继续保存,那么就将其写入level L+1层中新生成的一个SSTable文件中。就这样对KV数据一一处理,形成了一系列新的L+1层数据文件,之前的L层文件和L+1层参与compaction 的文件数据此时已经没有意义了,所以全部删除。这样就完成了L层和L+1层文件记录的合并过程。
      那么在major compaction过程中,判断一个KV记录是否抛弃的标准是什么呢?其中一个标准是:对于某个key来说,如果在小于L层中存在这个Key,那么这个KV在major compaction过程中可以抛掉。因为对于层级低于L的文件中如果存在同一Key的记录,那么说明对于Key来说,有更新鲜的Value存在,那么过去的Value就等于没有意义了,所以可以删除。

    Cache

      对于levelDb来说,读取操作如果没有在内存的memtable中找到记录,要多次进行磁盘访问操作。假设最优情况,即第一次就在level 0中最新的文件中找到了这个key,那么也需要读取2次磁盘,一次是将SSTable的文件中的index部分读入内存,这样根据这个index可以确定key是在哪个block中存储;第二次是读入这个block的内容,然后在内存中查找key对应的value。
      LevelDb中引入了两个不同的Cache:Table Cache和Block Cache。其中Block Cache是配置可选的,即在配置文件中指定是否打开这个功能。
    在这里插入图片描述
      如上图,在Table Cache中,key值是SSTable的文件名称,Value部分包含两部分,一个是指向磁盘打开的SSTable文件的文件指针,这是为了方便读取内容;另外一个是指向内存中这个SSTable文件对应的Table结构指针,table结构在内存中,保存了SSTable的index内容以及用来指示block cache用的cache_id ,当然除此外还有其它一些内容。
      比如在get(key)读取操作中,如果levelDb确定了key在某个level下某个文件A的key range范围内,那么需要判断是不是文件A真的包含这个KV。此时,levelDb会首先查找Table Cache,看这个文件是否在缓存里,如果找到了,那么根据index部分就可以查找是哪个block包含这个key。如果没有在缓存中找到文件,那么打开SSTable文件,将其index部分读入内存,然后插入Cache里面,去index里面定位哪个block包含这个Key 。如果确定了文件哪个block包含这个key,那么需要读入block内容,这是第二次读取。
    在这里插入图片描述
      Block Cache是为了加快这个过程的,其中的key是文件的cache_id加上这个block在文件中的起始位置block_offset。而value则是这个Block的内容。
      如果levelDb发现这个block在block cache中,可以直接在cache里的block内容里面查找key的value就行,如果没找到呢?那么读入block内容并把它插入block cache中。
      levelDb就是这样通过两个cache来加快读取速度的。可以看出,如果读取的数据局部性比较好,即要读的数据大部分在cache里面都能读到,那么读取效率较高,而如果是对key进行顺序读取效率也不错,因为一次读入后可以多次被复用。但是如果是随机读取,其效率会很低下。

    版本控制

      在Leveldb中,Version就代表了一个版本,它包括当前磁盘及内存中的所有文件信息。在所有的version中,只有一个是CURRENT(当前版本),其它都是历史版本。当执行一次compaction 或者 创建一个Iterator后,Leveldb将在当前版本基础上创建一个新版本,当前版本就变成了历史版本。VersionSet 是所有Version的集合,管理着所有存活的Version。VersionEdit 表示Version之间的变化,相当于delta 增量,表示有增加了多少文件,删除了文件:

    Version0 + VersionEdit --> Version1 
    Version0->Version1->Version2->Version3
    

    VersionEdit会保存到MANIFEST文件中,当做数据恢复时就会从MANIFEST文件中读出来重建数据。
      Leveldb的这种版本的控制,类似于双buffer切换。比如我们的服务器上有一个字典库,每天我们需要更新这个字典库,我们可以新开一个buffer,将新的字典库加载到这个新buffer中,等到加载完毕,将字典的指针指向新的字典库。Leveldb的version管理和双buffer切换类似,但是如果原version被某个iterator引用,那么这个version会一直保持,直到没有被任何一个iterator引用,此时就可以删除这个version。

    展开全文
  • leveldb

    2020-05-21 12:24:23
  • levelDB

    2018-03-21 15:54:17
    所有的数据存储在levelDB这个Google开源的KeyValue文件数据库中,整个区块链的所有数据都存储在一个levelDB的数据库中,levelDB支持按照文件大小切分文件的功能,所以我们看到的区块链的数据都是一个一个小文件,...

    所有的数据存储在levelDB这个Google开源的KeyValue文件数据库中,整个区块链的所有数据都存储在一个levelDB的数据库中,levelDB支持按照文件大小切分文件的功能,所以我们看到的区块链的数据都是一个一个小文件,其实这些小文件都是一个同一个levelDB实例。

    levelDB官方网站介绍的特点

    特点

    • key和value都是任意长度的字节数组;
    • entry(即一条K-V记录)默认是按照key的字典顺序存储的,当然开发者也可以重载这个排序函数;
    • 提供的基本操作接口:Put()、Delete()、Get()、Batch();
    • 支持批量操作以原子操作进行;
    • 可以创建数据全景的snapshot(快照),并允许在快照中查找数据;
    • 可以通过前向(或后向)迭代器遍历数据(迭代器会隐含的创建一个snapshot);
    • 自动使用Snappy压缩数据;
    • 可移植性;

    限制

    • 非关系型数据模型(NoSQL),不支持sql语句,也不支持索引;
    • 一次只允许一个进程访问一个特定的数据库;
    • 没有内置的C/S架构,但开发者可以使用LevelDB库自己封装一个server;

    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,937
精华内容 2,774
关键字:

leveldb