- N +

lpl春季赛,经典开源代码剖析——Leveldb高效存储完成,瓜子

原标题:lpl春季赛,经典开源代码剖析——Leveldb高效存储完成,瓜子

导读:

codedump.info 博主,多年从事互联网服务器后台开发工作.可访问作者博客阅读 codedump 更多文章.本文基于leveldb 1.9.0代码.......

文章目录 [+]

导读:LevelDB是Google开源的耐久化KV数据库,在其高功能的背面,将数据拆分红多层进行存储。本文作者深入剖析了LevelDB存储模块的规划和源码完结,快速了解LevelDB高功能背面的原理


作者 codedump codedump.info 博主,多年从事互联网服务器后台开发作业。可拜访作者博客阅览 codedump 更多文章。


本文依据leveldb 1.9.0代码。

全体架构


如上图,leveldb的数据存储在内存以及磁盘上,其间:

  • memtable:存储在内存中的数据,运用skiplist完结。

  • immutable memtable:与memtable相同,只不过这个memtable不能再进行修正,会将其间的数据落盘到level 0的sstable中。

  • 多层sstable:leveldb运用多个层次来存储sstable文件,这些文件散布在磁盘上,这些文徐海乔然然件都是依据键值有序摆放的,其间0级的sstable的键值或许会堆叠,而level舔奶小说 1及以上的sstable文件不会堆叠。


在上面这个存储层次中,越靠上的数据越新,即同一个键值假如一同存在于memtable和immutable memtable中,则以memtable中的为准。


其他,图中还运用箭头来表明了兼并数据的走向,即:



以下将针对这几部分翻开讨论。

Log文件

写入数据的时分,最开端会写入到log文件中,由所以次序写入文件,所以写入速度很快,能够立刻回来。


来看Log文件的结构:

  • 一个Log文件由多个Block组成,每个Block巨细为32KB。

  • 一个Block内部又有多个Record组成,Record分为四种类型:

    • Full:一个Record占满了整个Block存储空间。

    • First:一个Block的第一个Record。

    • Last:一个Block的最终一个Record。

    • Middle:其他的都是Middle类型的Record。

  • Record的结构如下:

    • 32位长度的CRC Checksum:存储这个Record的数据校验值,用于检测Record合法性。

    • 16位长度的Length:存储数据部分长度。

    • 8位长度的Type:存储Record类型,便是上面说的四种类型。

    • Header部分

    • 数据部分


memtable

memtable用于存储在内存中还未落盘到sstable中的数据,这部分运用跳表(skiplist)做为底层的数据结构,这儿先简略描绘一下跳表的作业原理。


假如数据寄存在一个一般的有序链表中,那么查找数据的时刻杂乱度便是O(n)。跳表的规划思维在于:链表中的每个元素,都有多个层次,查找某一个元素时,遍历该链表的时分,依据层次来越过(skip)中心某些显着不满意需求的元素,以到达加速查找速度的意图,如下图所示:



在以上这个跳表中,查找元素6的流程,大体如下:

  • 构建一个每个链表元素最多有5个元素的跳表。

  • 由于6大于链表的第一个元素1,因而假如存在必定在1之后的元素中,因而进入元素1的指针数组中,从上往下查找元素4:

    • 第一层:指向的指针为Nil空指针,不满意需求,持续往下查找;

    • 第二层:指向的指针保存的数据为4,小于待查找的元素4,因而假如元素6存在也必定在4之后,因而指针跳转到元素4地点的方位,持续从上往下开端查找。

  • 到了元素4地点的指针数组,开端从上往下持续查找:

    • 第一层:指向的指针保存的数据为6,查找结束。


从上面的剖析进程中能够看到:

  • 跳表是一种以献身更多的存储空间交换查找速度,即“空间换降服花心大少时刻”的数据结构。

  • 跳表的每一层也都是一个有序链表。

  • 假如一个元素呈现在第i层的链表中,万永商号那么也必定会在第i层以下的链表中呈现。

  • 链表的每个节点中,笔直方向的数组存储的数据都是相同的,水平方向的指针指向链表的下一个元素。

  • 最底层的链表包括一切元素,也便是说,在最底层数据结构退化为一个一般的有序链表。 

sstable文件

大体结构

首要来看sstable文件的全体结构,如下图:



sstable文件中分为以下几个组成部分:

  • data block:存储数据的block,由于一个block巨细固定,因而每个sstable文件中有多个data block。

  • filter block以及metaindex block:这两个block不一定存在于sstable,取决于Options中的filter_policy参数值,后边就不对这两部分进行解说。

  • index block:存储的是索引数据,即能够依据index block中的数据快lpl春季赛,经典开源代码剖析——Leveldb高效存储完结,瓜子速定位到数据处于哪个data block的哪个方位。

  • footer:脚注数据,每个footer数据信息巨细固定,存储一个sstable文件的元信息(meta data)。


能够看到,上面这几部分数据,从文件的安排来看自上而下,先有了数据再有索引数据,最终才是文件自身的元信息。原因在于:索引数据是针对数据的索引信息,在数据没有写结束之前,索引信息还会发作改动,所以索引数据要等数据写完;而元信息便是针对索引数据的索引,相同要依赖于索引信息写结束才能够。


block

上面几部分数据中,除去footer之外,内部都是以block的方法来安排数据,接着看block的结构,如下图:



从上面看出,实践上存储数据的block迥然不同:最开端的一部分存储数据,然后存储类型,最终一部分存储这个block的校验码以做合法性校验。


以上仅仅对block大体结构的剖析,在数据部分,每一条数据记载leveldb运用前缀紧缩(prefix-compressed)方法来存储。这种算法的原理是:针对一组数据,取出一个公共的前缀,而在该组中的其它字符串只保存非公共的字符串做为key即可,由于sstable保存KV数据是严厉依照key的次序来排序的,所以这样能节省出保存key数据的空间来。


如下图所示:一个block内部划分了多个记载组(record group),每个记载组内部又由多条记载(record)组成。在同一个记载组内部,以本组的第一条数据的键值做为公共前缀,后续的记载数据键值部分只寄存与公共前缀非同享部分的数据即可。



以记载的三个数据、为例,假定这三个数据在同一个record 尚洁怡group内,那么对应的record记载如下所李丙溪示:



阐明如下:

  • :由于这对数据是这一组记载组的第一组数据,因而同享的前缀部分长度为0,由于每一组都以第一条数据的key为同享前缀,因而针对第一条数据自身,其同享前缀长度便是0了。

  • :键值“ab”与本组公共前缀(即本组的第一条数据键值“a”)有公共前缀“a”,因而同享前缀长度为1,非同享部分键值为剩余的“b”。

  • :键值“c”与本组公共前缀“a”没有重合部分,因而同享前缀长度为0。


由于一个block内部有多个记载组,因而还需求其他的数据来记载不同记载组的方位,这部分数据被称为“重启点(restart point)”,重启点首要会以数组的方法保存下来,直到该block数据需求落盘的状况下才会写到block结尾处。


有了以上的预备,就能够来详细看增加数据的代码了,向一个block中增加数据的伪代码如下。



有了前面的这些预备,再在前面block格局的基础上翻开,得到愈加详细的格局如下:



block详细格局仍是划分为三大部分,其间:

  • 数据部分

    • 多个记载组组成的记载数据。

    • 多个重启点数据组成的重启点数组数据,每个元素记载对应的记载组在block中的偏移量,类型为fixed32类型。

  • 紧缩类型,巨细为1 Byte。

  • CRC32校验数据,巨细为4 Byte。

footer

footer做为存储sstable文件原信息部分的数据,格局相对简略,如下图:

Iterator的规划

迭代器的规划是leveldb中的一大亮点,leveldb规划了一个虚拟基类Iterator,其间界说了比如遍历、查询之类的接口,而莱巴里科娃该基类有多种完结。原因在于:l圆正健身操eveldb中存在多种数据结构和多种运用场景,如:

  • 保存内存中数据的memtable。

  • 保存落盘数据的sstable,而就前面剖析而言,一个sstable中还有不同的block,需求依据index block来定位数据处于哪个data block。

  • 进行兼并的时分,每次最多兼并两个层次的文件,在这个进程中需求对待兼并的文件调集进行遍历。前面剖析的DBImpl::DoCompactionWork函数,便是经过iterator来遍历待兼并文件进行兼并操作的。


逐一来看不同的iterator完结以及其运用场景。

迭代器大体分为两类:

  • 底层迭代器:处于最底层,直接拜访底层数据结构,而不依赖于其他迭代器的迭代器。

  • 组合迭代器:组合各种迭代器(包括底层和组合迭代器)完结作业的迭代器。


底层迭代器

底层迭代器有以下三种:

  • MemTableIterator:用于完结对memtable的迭代遍历,由于memtable由skiplist完结,因而内部封装了对skiplist的迭代拜访。

  • Block::Iter:前面剖析sstable的时分,讲到一个sstable内部其实有多个block组成,这个迭代器便是依照block的结构进行迭代拜访的迭代器。

  • Version::LevelFileNumIterator:每个level都由多个sstable文件组成,说白了便是一个sstable类型的数组。除了level 0之外,其他level的sstable的键值之间没有堆叠联络,而LevelFileNumIterator便是用于迭代一组有序sstable文件的迭代器。



组合迭代器

组合迭代器内部都包括至少一个迭代器,组合起来完结迭代作业,有如下几类。


TwoLevelIterator

望文生义,TwoLevelIterator表明两层迭代器,创立TwoLevelIterator的函数原型为:



参数阐明如下:

  • Iterator* index_iter:索引迭代器,能够了解为第一层的迭代器。

  • BlockFunction *block_function:这是一个函数指针,依据index_iter迭代器的回来成果来再创立一个迭代器,即针对查询索引回来数据的迭代器。其函数参数有三个,其间前面两个由下面的arg以及options参数指定,而第三个参数slice便是index_iterator回来的索引数据。

  • void* arg:传入BlockFunction函数的第一个参数。

  • const ReadOptions& option郭鹤年小女儿郭燕光s:传入BlockFunction函数的第二个参数。

归纳以上,TwoLevelIterator的作业流程如下:



TwoLevelIterator有如下两类:

  • Table::Iterator:完结关于单个sstable文件的迭代。由于一个sstable文件中有多个block,而又划分为index block和data block,查询数据时,先依据键值到index block中查询到对应的data block,再进入data block中进行查询,这个查询进程实践便是一个两层的查找进程:先查索引数据,再查数据。因而Table::Iterator类型的TwoLevelIterator,组合了index block的Block::Iter,以及data block的Block::Iter。

  • ConcatenatingIterator:组合了LevelFileNumIterator以及Table::Iterator,用于在某一层内的sstable文件中查询数据。因而它的第一层迭代器便是前面的LevelFileNumIterator,用于依据一个键值在一组有序的sstable文件中定位到地点的文件,而第二层的迭代器是Table::Iterator,用于在第一层迭代器LevelFileNumIterator中查询到的sstable文件中查询键值。其他,已然C王子旋oncatenatingIterator处理的是有序sstable文件,那么level 0的sstable文件就不会运用这种迭代器进行拜访,由于level 0文件之间有堆叠键值。



MergingIterator

用于兼并流程的迭代器。在兼并进程中,需求操作memtable、immutable memtable、level 0 sstable以及非level 0的sstable,该迭代器将这些存储数据结构体的迭代器,一致进行归并排序:

  • memtable以及immutable memtable:运用前面提过的MemtableIterator迭代器。

  • level 0 sstable:由于level 0的sstable文件之间键值有堆叠,所以运用的是level 0的sstable文件各自的Table::Iterlpl春季赛,经典开源代码剖析——Leveldb高效存储完结,瓜子ator。

  • level 1层级及以上的sstable:运用前面介绍过的ConcatenatingIterator,即能够针对一组有序sstable文件进行遍历的iterator。


由于以上每种类型的iterator,内部遍历数据都是有序的,所以MergingIterator内部做的作业,便是将对这些iterator的遍历成果进行“归并”。MergingIterator内部有如下变量:

  • const Comparator* comparator_:用于键值比较的函数operator。

  • IteratorWrapper* children_:存储传入的iteralpl春季赛,经典开源代码剖析——Leveldb高效存储完结,瓜子tor的数组。

  • int n_:children_数组的巨细。

  • IteratorWrapper* current_:保存当时查询到的方位地点的iterator。

  • Direction direction_:保存查找的方向,有向前和向后两种查询防地。


能够看到,current_以及direction_两个成员是用于保存当时查找状况的成员。

构建MergingIterator迭代器传入的Comparator是InternalKeyComparator,其比较逻辑是:

  • 首要比较键值是否持平,不持平则直接回来比较成果。

  • 假如键值持平,那么从键值中decode出来sequence值,比照sequence值,对sequence值进行降序比较。由于这个值是单调递加的,因而越新的数据sequence值越大。换言之,在存储层次中(依次为memtable->immutable memtable->level 0 sstable->level n sstable)越靠上面的数据,在键值相同的状况下越小。


Seek(target)函数的伪代码:



而FindSmallest函数的完结,是遍历children_找到最小的child保存到current_指针中。前面剖析InternalKeyComparator提到过,相同键值的数据,依据sequence值进行降序摆放,即数据越新的数据其sequence值越大,在这个排序中查找的成果就越在上面。因而,FindSmallest函数假如在memtable、level 0中都找到了相同键值,将优先挑选memtable中的数据。


MergingIterator迭代器的其它完结不再做解说,简略了解:针对一组iterator的查询成果进行归并排序。关于相同一个键值,只取方位在存储方位上最靠上面的数据。


这么做的原因在于:一个键值的数据或许被写入屡次,而需求以最终一次写入的数据为准,兼并时将丢掉掉不在存储最上面的数据。


以下面的比如来阐明lpl春季赛,经典开源代码剖析——Leveldb高效存储完结,瓜子MergingIterator迭代器的兼并成果。



在上图的左半边,是兼并前的数据散布状况,依次为:

  • memtable:键值1的删去记载,以及键值<2,test>。

  • immutable memtable:键值<2,tesat2>以及<3,test>。

  • level 0 sstable:键值<1,test>。

  • level 1 sstable:键值<3,a>。


兼并的成果如上图的右边所示:

  • 键1:由于第一条键1的记载是在memtable中的删去记载,所以键1将被删去,即不会呈现在兼并成果中。

  • 键2:最靠上面的关于键2的存储记载是<2,test>,这条记载保存在兼并成果中,而immutable memtable的记载<2,test2>将被丢掉,由于这条记载不是最新的。

  • 键3:运用了immutable memtable中的记载<3,test>,丢掉了level 1 sstable中的<3,a>这条记载。

中心流程

有了前面几种中心数据结构的了解,下面谈leveldb中的几个中心流程。


修正流程ryujehong

修正数据,分为两类:正常的写入数据操作以及删去数据操作。


先看正常的写入数据操作:

  • append一条记载到log文件中,尽管这是一次写磁盘操作,可是由所以在文件结尾做的次序写操作,所以功率并不低。

  • 向当时的memtable中写入一条数据。这个动作看似简略,可是假如在来不及兼并的时分,或许会呈现堵塞,在后边兼并操作中再翻开解说。


完结以上两步之后,就能够以为完结了更新数据的操作。实践上只要一次文件结尾的次序写操作,以及一次写内存操作,假如不考虑会被兼并操作堵塞的状况,实践上仍是很快的。


再来看删去数据操作。leveldb中,删去一个数据,其实也是增加一条新的记载,只不过记载类型是删去类型,代码中经过枚举变量界说了这两种操作类型:



这样看起来,篮球帅哥leveldb删去数据时,并不会真的去删去一条数据,而是打上了一个符号,那么问题就来了:假如写入数据操作与删去数据操作,仅仅类型不同,在查询数据的时分又怎样知道数据是否存在?看下面的读数据流程。


读流程

向leveldb中查询一个数据,也是从上而下,先查内存然后到磁盘上的sstable文件查询,如下图所示:



  • 先在内存中的memtable中查询数据,查到则回来;

  • 不然在磁盘中的sstable文件中查询数据,从0级开端往下查询,查到则回来;


这样自上而下的原因就在于leveldb的规划:越是在上层的数据越新,间隔当时时刻越短。


举例而言,关于键值key而言,首要写入kv对,然后再删去键值key数据。第一次写入的数据,或许由于兼并的原因以及到了ssta赵联普ble文件上,而再次删去键值key的数据时,依据上面的解说,其实也是写入数据,只不过符号为删去。所以,越后翠鸟抓鱼遭冰封写入的数据,越在上面这个层次的上面,这样从上往下查询时就能先查找到后写入的数据,此刻看到了数据现已被符号为删去,就能够以为数据不存在了。


那么,前面写入的数据实践上现已没有用了,可是又占用了空间,这部分数据就等待着后边的兼并流程来兼并数据最终删去掉。


兼并流程

中心数据结构

首要来看与兼并相关的中心数据结构。


每一次兼并进程以及将memtable中的数据落盘到sstable的进程,都涉及到sstable文件的增删,而这每一次操作,都对应到一个版别。


在leveldb中,运用Version类来存储一个版其他元信息,首要包括:

  • std::vector

     files_[config::kNumLevels]:用于存储一切等级sstable文件的FileMetaData数组,能够看到这个成员是一个数组,而淘彩吧数组的每个元素又是一个vector,这其间数组部分运用level等级来进行索引,同等级的sstable信息存储在vector中。
  • FileMetaData* file_to_compact_和int file_to_comlpl春季赛,经典开源代码剖析——Leveldb高效存储完结,瓜子pact_level_:下一次进行兼并时的文件和等级。

  • double compaction_score_和int compaction_level_:当时最大compact分数和对应的等级,在Finalize函数中进行核算,详细核算的规矩会在下面介绍。


能够看到,Version保存的首要是两类数据:当时sstable文件的信息,以及下一次兼并时的信息。


一切的等级,也便是Version类,运用双向链表串联起来,保存到VersionSet中,而Vlpl春季赛,经典开源代码剖析——Leveldb高效存储完结,瓜子ersionSet中有一个current指针,用于指向当时的Version。



当进行兼并时,首要需求挑选出需求进行兼并的文件,这个操作的进口函数是VersionSet::PickCompaction,该函数的回来值是一个Compaction结构体,该结构体内部保存兼并相关的信息,Compaction结构体中最重要的成员是VersionEdit类成员,这个成员用于保存兼并进程中有删减的sstable文件:

  • DeletedFileSet deleted_files_:兼并后待删去的sstable文件。

  • std::vector< std::p簿本五颜六色air

     > new_files_:兼并后新增的sstable文件。


能够以为:version N + version N edit = version N + 1,即:第N版其他sstable信息,在经过该版别兼并的VersionEdit之后,形成了Version N+1版别。


其他还有一个VersionSet::Builder,用于保存兼并中心进程的数据,其本质是将一切VersoinEdit内容存储到VersionSet::Builder中,最终一次发生新版其他Version。



兼并条件及原理

leveldb会不断发生新的sstable文件,这时分需求对这些文件进行兼并,不然磁盘会一向增大,查询速度也会下降。


这部分解说兼并触发的条件以及进行兼并的原理。

leveldb大致在以下两种条件下会触发兼并操作:

  • 需求新生成memtable的状况下,此刻必定会把本来的memtable切换为immutable memtable,后者又需求及时落盘成为新的sstable文件,将immutable memtable数据落盘为sstable文件的流程称为”minor compaction“,由于有新的sstable文件发生,所以需求兼并文件削减lpl春季赛,经典开源代码剖析——Leveldb高效存储完结,瓜子sstable文件的数量。

  • 查询数据时,某些sstable总是查找不到数据,此刻或许是由于数据太过分散了,也需求将文件兼并。


以上两种状况,对应到leveldb代码中便是以下几个当地:

  • 调用DB::Open文件翻开数据库文件时,由于之前或许现已存在了一些文件,这时会做查看,满意条件的状况下会进行兼并操作。

  • 调用DB::Write函数写入数据时,调用MakeRoomForWrite函数分配空间,此刻假如需求新分配一个memtable,也会触发兼并操作。

  • 调用DB::Get函数查松花木寡糖询数据时,某些文件查询的次数超过了阈值,此刻也会进行兼并操作。


其他还需求提一下兼并的两种类型:

  • minor compaction:将内存的数据落地到磁盘上的搬迁进程,对应于leveldb便是将immutable memtable数据落盘为sstable文件的流程。

  • major compaction:sstable之间的文件进行兼并的流程。


挑选进行兼并的文件

函数VersionSet::PickCompaction用于构建出一次兼并对应的Compaction结构体。来看这个函数首要的流程。


在挑选哪些文件需求兼并时,依赖于两个准则:

  • 首要考虑每一层文件的数量:这个数量的计数,对应到Version的compaction_score_中,在每次VersionSet::Finalize函数中,都会首要进行预核算这个值,那个等级的分数高,下一次就优先挑选该层次来做兼并。关于不同的层次,核算的规矩也不同:

    • level 0:0级文件的数量除以kL0_CompactionTrigger来核算分数。

    • 非0级:该层次的一切文件巨细/MaxBytesForLevel(level)来核算分数。

  • 假如上面的核算中,compaction_score_为0,那么就需求详细针对一个文件来进行兼并。leveldb中,在FileMetaData结构体里有一个成员allowed_seeks,表明在该文件中查询某个键值时最多答应的定位次数,当这个值为0时,意味这个文件屡次查询都没有查询到数据,因而这个文件就需求进行兼并了。


文件的allowed_seeks在VersionSet::Builder::Apply函数中进行核算:



假如是第一种状况,即compaction_score_ >= 1的状况来挑选兼并文件,还涉及到一个合女星裸照并点的问题(compact point),即leveldb会保存上一次进行兼并的键值,这一次会从这个键值今后开端寻觅需求进行兼并的文件。


而假如兼并层次是0级,由于0级文件中的键值有堆叠的状况,因而还需求遍历0级文件中键值规模与这次兼并文件由堆叠的一同参加进来。


在这之后,调用VersionSet::SetupOtherInputs函数,用于获取同等级以及更上一层也便是level + 1等级中满意兼并规模条件的文件,这就构成了待兼并的文件调集。



如上图所示:

  • 此刻挑选进行兼并的文件,其键值是[1,2,4,5]。

  • 由于该文件在level 0等级,sstable文件的键值有堆叠,一同还在在其上面一层挑选相同键值规模有堆叠的sstable文件,挑选的成果便是绿色的sstable文件,这些将做为这次兼并进行归并排序的文件。


兼并流程

以上调用VersionSet::PickCompaction函数挑选结束了待兼并的文件及层次之后,就来到DBImpl::DoCompactionWork函数中进行实践的兼并作业。


该函数的原理不算杂乱,便是遍历文件调集进行兼并:



兼并操作对读写流程的影响

leveldb将用户的读写操作,与兼并作业放在不同的线程中处理。当用户需求写入数据进行分配空间时,会首要调用DBImpl::MakeRoomForWrite函数进行空间的分配,该函数有或许由于兼并流程被堵塞,有以下几种或许性:


参考资料

  • 数据剖析与处理之二(Le冷宫弃后很绝情veldb 完结原理):https://www.cnblogs.com/haippy/archive/2011/12/04/2276064.html

  • Leveldb之Iterator总结:http://kernelmaker.github.io/Leveldb_Iterator


相关阅览


技能原创及架构实践文章,欢迎经过大众号菜单「联络咱们」进行投稿。转载请注明来自高可用架构「ArchNotes」微信大众号及包括以下二维码。

高可用架构

改动互联网的构建方法

长按二维码 重视「高可用架构」大众号


有好的文章希望我们帮助分享和推广,猛戳这里我要投稿

返回列表
上一篇:
下一篇: