二手交易网站建设方案,自己怎么做装修网站,wordpress 京东,全国企业信用信息平台LevelDB
基本介绍
是一个key/value存储#xff0c;key值根据用户指定的comparator排序。
特性
keys 和 values 是任意的字节数组。数据按 key 值排序存储。调用者可以提供一个自定义的比较函数来重写排序顺序。提供基本的 Put(key,value)#xff0c;Get(key)#xff0c;…LevelDB
基本介绍
是一个key/value存储key值根据用户指定的comparator排序。
特性
keys 和 values 是任意的字节数组。数据按 key 值排序存储。调用者可以提供一个自定义的比较函数来重写排序顺序。提供基本的 Put(key,value)Get(key)Delete(key) 操作。多个更改可以在一个原子批处理中生效。用户可以创建一个瞬时快照(snapshot)以获得数据的一致性视图。在数据上支持向前和向后迭代。使用 Snappy 压缩库对数据进行自动压缩与外部交互的操作都被抽象成了接口(如文件系统操作等)因此用户可以根据接口自定义的操作系统交互。
LevelDb是一个持久化存储的KV系统和Redis这种内存型的KV系统不同LevelDb不会像Redis一样狂吃内存而是将大部分数据存储到磁盘上。 LevelDb性能非常突出官方网站报道其随机写性能达到40万条记录每秒而随机读性能达到6万条记录每秒。总体来说LevelDb的写操作要大大快于读操作而顺序读写操作则大大快于随机读写操作。
局限性
这不是一个 SQL 数据库它没有关系数据模型不支持 SQL 查询也不支持索引。同时只能有一个进程(可能是具有多线程的进程)访问一个特定的数据库。该程序库没有内置的 client-server 支持有需要的用户必须自己封装。
结构概要 内存中的MemTable和Immutable MemTable以及磁盘上的几种主要文件Current文件Manifest文件log文件以及SSTable文件。当然LevelDb除了这六个主要部分还有一些辅助的文件但是以上六个文件和数据结构是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文件。
简单来说SSTable存真正的k-v记录manifest存SSTable的最小key和最大keycurrent存最新的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的值只需要插入一条新纪录即可或者先删除旧记录再插入也可
这就是为什么大量删除的时候会产生延迟问题。它本身并不删除数据而是标记为删除状态导致拉取数据的时候发现一千个里九百个是删除状态这就会导致不符合客户端调用的拉取1000个的指令。所谓的压缩才是真正的删除数据这就是lavaDB这段时间对上海园区做的事情
读操作流程
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 L1找到同一个keylevel L的信息一定比level L1的要新。
SSTable文件 从大的方面可以将.sst文件划分为数据存储区和数据管理区数据存储区存放实际的Key:Value数据数据管理区则提供一些索引指针等管理数据目的是更快速便捷的查找相应的记录。两个区域都是在上述的分块基础上的就是说文件的前面若干块实际存储KV数据后面数据管理区存储管理数据。管理数据又分为四种不同类型紫色的Meta Block红色的MetaBlock 索引和蓝色的数据索引块以及一个文件尾部块。
Data Block内的KV记录是按照Key由小到大排列的数据索引区的每条记录是对某个Data Block建立的索引信息每条索引信息包含三个内容,数据块i的索引Index i来说红色部分的第一个字段记载大于等于数据块i中最大的Key值的那个Key第二个字段指出数据块i在.sst文件中的起始位置第三个字段指出Data Block i的大小有时候是有数据压缩的。后面两个字段好理解是用于定位数据块在文件中的位置的第一个字段需要详细解释一下在索引里保存的这个Key值未必一定是某条记录的Key。 假设数据块i 的最小Key“samecity”最大Key“the best”;数据块i1的最小Key“the fox”,最大Key“zoo”,那么对于数据块i的索引Index i来说其第一个字段记载大于等于数据块i的最大Key(“the best”)同时要小于数据块i1的最小Key(“the fox”)所以例子中Index i的第一个字段是“the c”这个是满足要求的而Index i1的第一个字段则是“zoo”即数据块i1的最大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是一个大表大表又分为很多个小表每个小表的key有序。最后一个小表记录着之前所有小表的起始位置以及每个小表第一个实体的key值。这样就能知道一个小表的范围。通过布隆过滤器筛出不存在的值然后扫描最后一个小表的index。由于key是有序的这样一来就能知道要查的key在哪个小表里。同一个小表里的key贡献前缀后缀唯一。
由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最多4个SST文件, Level 1总大小不超过10MB Level 2总大小不超过100MB Level 3总大小不超过上一个Level ×10的大小。 比如0 ↠ 4 SST, 1 ↠ 10M, 2 ↠ 100M, 3 ↠ 1G, 4 ↠ 10G, 5 ↠ 100G, 6 ↠ 1T, 7 ↠ 10T 在读操作中要查找一条entry先查找log如果没有找到然后在Level 0中查找如果还是没有找到再依次往更底层的Level顺序查找如果查找了一条不存在的entry则要遍历一遍所有的Level才能返回Not Found的结果。 在写操作中新数据总是先插入开头的几个Level中开头的这几个Level存储量也比较小因此对某条entry的修改或删除操作带来的性能影响就比较可控。 可见SST采取分层结构是为了最大限度减小插入新entry时的开销
这里似乎就是上海LavaDB延迟大的原因删除量大的时候就会发现从上到下找遍了都没能找到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中会去做。
假如大量删除操作进来那岂不是memtable和SST里全是删除标记。然后又要从memtable和SST里去遍历存在的entry这肯定会找很久然后找不到啊。
当某个level下的SSTable文件数目超过一定设置值后levelDb会从这个level的SSTable中选择一个文件level0将其和高一层级的level1的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 L1层的文件进行合并那么问题又来了应该选择level L1哪些文件进行合并levelDb选择L1层中和文件A在key range上有重叠的所有文件来和文件A进行合并。也就是说选定了level L的文件A之后在level L1中找到了所有需要合并的文件B,C,D……等等。剩下的问题就是具体是如何进行major 合并的就是说给定了一系列文件每个文件内部是key有序的如何对这些文件进行合并使得新生成的文件仍然Key有序同时抛掉哪些不再有价值的KV 数据。
Major compaction的过程如下对多个文件采用多路归并排序的方式依次找出其中最小的Key记录也就是对多个文件中的所有记录重新进行排序。之后采取一定的标准判断这个Key是否还需要保存如果判断没有保存价值那么直接抛掉如果觉得还需要继续保存那么就将其写入level L1层中新生成的一个SSTable文件中。就这样对KV数据一一处理形成了一系列新的L1层数据文件之前的L层文件和L1层参与compaction 的文件数据此时已经没有意义了所以全部删除。这样就完成了L层和L1层文件记录的合并过程。
那么在major compaction过程中判断一个KV记录是否抛弃的标准是什么呢其中一个标准是对于某个key来说如果在小于L层中存在这个Key那么这个KV在major compaction过程中可以抛掉。因为我们前面分析过对于层级低于L的文件中如果存在同一Key的记录那么说明对于Key来说有更新鲜的Value存在那么过去的Value就等于没有意义了所以可以删除。 假如我在memtable里有删除标记那么在major压缩的时候就会抛弃这个entry实现删除效果。
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内容这是第二次读取。 也就是说首先确定是在哪个keyrange范围内然后去TableCache找能找到就根据Table pointer-Table index找到对应的block没找到就通过File handle找SStable将把index读入内存插入Cache然后去index里定位要去哪个block里找。确定了block后再读取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-Version3VersionEdit会保存到MANIFEST文件中当做数据恢复时就会从MANIFEST文件中读出来重建数据。
