分类目录:LevelDB

LevelDB详解: Compaction

说明 LevelDB是日志型KV存储系统,所有的更新操作(包括插入、更新、删除)都以(key, value)的形式追加至log文件的尾部,这样,系统中更新的访问模式就变成了顺序写,很适合更新频繁的应用场景。

LevelDB详解: 如何从Block中读出key

LevelDB磁盘上的<key, value>数据被存储在sstable中,而数据在sstable内又是按照block为单位索引的,且LevelDB内又以block为单位做了缓存。因此,读取<key, value>的第一步是确定其所在block,这通过查找sstable的index block完成。当读出<key, value>所在data block后,同样需要在该data block内顺序查找。本文的主要目的是搞清楚如何查找index block获得<key, value>所属data block以及查找data block最终获得key对应的value值。

LevelDB详解: 读过程一

LevelDB基本读流程按照如下顺序: 从内存memtable读; 从内存Immutable memtable读; 从level0的sstable读; 从level1的sstable读; …… 上面的读流程中,如果在上一级命中,就不再进入下一层级去读取,因为上一层级的数据总是比下一层级的数据更新,这也是取名levelDB的原因所在。

LevelDB专题七: 记录读取

LevelDB是针对大规模Key/Value数据的单机存储库,从应用的角度来看,LevelDB就是一个存储工具。而作为称职的存储工具,常见的调用接口无非是新增KV,删除KV,读取KV,更新Key对应的Value值这么几种操作。LevelDB没有直接支持更新操作的接口,如果需要更新某个Key的Value,你可以选择直接生猛地插入新的KV,保持Key相同,这样系统内的key对应的value就会被更新;或者你可以先删除旧的KV, 之后再插入新的KV,这样比较委婉地完成KV的更新操作。

LevelDB专题六: 数据写入

在之前的系列文章中,我们介绍了LevelDB的一些静态文件及其详细布局,从本节开始,我们看看LevelDB的一些动态操作,比如读写记录,Compaction,错误恢复等操作。本节介绍LevelDB的记录更新操作,即插入/删除一条KV记录。LevelDB的更新操作速度是非常快的,源于其内部机制决定了这种更新操作的简单性。 图1 levelDB写入记录  图1是LevelDb如何更新KV数据的示意图,完成插入操作包含两个具体步骤: KV记录以顺序的方式追加到log文件末尾,并调用Sync将数据真正写入磁盘。尽管这涉及到一次磁盘IO,但是文件的顺序追加写入效率是很高的,所以并不会导致写入速度的降低; 如果写入log文件成功,那么将这条KV记录插入内存中的Memtable中。前面介绍过,Memtable只是一层封装,其内部其实是一个Key有序的SkipList列表,插入一条新记录的过程也很简单,即先查找合适的插入位置,然后修改相应的链接指针将新记录插入即可。 log文件内是key无序的,而Memtable中是key有序的。对于删除操作,基本方式与插入操作相同的,区别是,插入操作插入的是Key:Value 值,而删除操作插入的是“Key:删除标记”,由后台Compaction程序执行真正的垃圾回收操作。 LevelDB的写入操作就是如此简单,真正的麻烦在后面接下来介绍的读取操作中。

LevelDB专题五: MemTable结构

     Memtable在整个LevelDB体系中的重要地位不言而喻。所有KV数据都是存储在Memtable,Immutable Memtable和SSTable中的。Immutable Memtable从结构上讲和Memtable是完全一样的,区别仅仅在于其是只读的,不允许写入操作。当Memtable写入的数据占用内存到达指定数量,则自动转换为ImmutableMemtable,等待Dump到磁盘中,系统会自动生成新的Memtable供写操作写入新数据,理解了Memtable,那么Immutable Memtable自然不在话下。       LevelDB的MemTable提供了数据写入、删除以及读取记录的操作接口,但是事实上Memtable并不存在真正的删除操作,删除某个Key的Value在Memtable内是作为插入一条记录实施的,但是会打上一个Key的删除标记,真正的删除操作是Lazy的,会在以后的Compaction过程中去掉这个KV。      需要注意的是,LevelDB的Memtable中KV对是根据Key大小有序存储的,在系统插入新的KV时,LevelDb要把这个KV插到合适的位置上以保持这种Key有序性。其实,LevelDb的Memtable类只是一个接口类,真正的操作是通过背后的SkipList来做的,包括插入操作和读取操作等,所以Memtable的核心数据结构是一个SkipList。      SkipList是由WilliamPugh发明。他在Communicationsof the ACM June 1990, 33(6) 668-676 发表了Skiplists: a probabilistic alternative to balanced trees,在该论文中详细解释了SkipList的数据结构和插入删除操作。SkipList是平衡树的一种替代数据结构,但是和红黑树不相同的是,SkipList对于树的平衡的实现是基于一种随机化的算法的,这样也就是说SkipList的插入和删除的工作是比较简单的。      LevelDB的SkipList基本上是一个具体实现,并无特殊之处。SkipList不仅是维护有序数据的一个简单实现,而且相比较平衡树来说,在插入数据的时候可以避免频繁的树节点调整操作,所以写入效率是很高的,LevelDB整体而言是个高写入性能系统,SkipList在其中应该也起到了很重要的作用。Redis为了加快插入操作,也使用了SkipList来作为内部实现数据结构。关于跳表的原理可参考“www.d-kai.me/skip-list”。       LevelDB中对memtable结构的定义如下: class MemTable { public: ...... private: ~MemTable(); struct KeyComparator { const InternalKeyComparator comparator; explicit KeyComparator(const InternalKeyComparator& c) : comparator(c) { } int operator()(const char* a, const char* b) const; }; friend class MemTableIterator; friend class MemTableBackwardIterator; // 使用SkipList作为核心存储结构 typedef SkipList<const char*, KeyComparator> Table; KeyComparator comparator_; int refs_; Arena arena_; Table table_; ...... }

LevelDB专题四: SSTable结构

        SSTable是Bigtable中至关重要的一块,对于LevelDB来说也是如此,对LevelDB的SSTable实现细节的了解也有助于了解Bigtable中一些实现细节。本节内容主要讲述SSTable的静态布局。         前面的“LevelDB整体架构”中说过,SSTable文件形成了不同Level的层级结构,至于这个层级结构是如何形成的我们放在后面Compaction一节细说。这里主要介绍SSTable某个文件的物理布局和逻辑布局,这对了解LevelDB的运行过程很有帮助。         LevelDB不同层级有很多SSTable文件(以后缀.sst为特征),所有.sst文件内部布局都是一样的。上节介绍Log文件是物理分块的,SSTable也一样会将文件划分为固定大小的物理存储块,但是两者逻辑布局大不相同,根本原因是:Log文件中的记录是Key无序的,即先后记录的key大小没有明确大小关系,而.sst文件内部则是根据记录的Key由小到大排列的,从下面介绍的SSTable布局可以体会到Key有序是为何如此设计.sst文件结构的关键。 图1 SSTable文件结构         图1展示了一个.sst文件的物理划分结构,同Log文件一样,也是划分为固定大小的存储块,每个Block分为三个部分,黄色部分是数据区,蓝色是Type区,用于标识数据存储区是否采用了数据压缩算法(Snappy压缩或者无压缩两种),CRC部分则是数据校验码,用于判别数据是否在生成和传输中出错。         以上是.sst的物理布局,下面介绍.sst文件的逻辑布局,所谓逻辑布局,就是说尽管大家都是物理块,但是每一块存储什么内容,内部又有什么结构等。图2展示了.sst文件的内部逻辑解释。 图2 逻辑布局   从图2可以看出,从大的方面,可以将.sst文件划分为数据区和元数据区。数据区存放实际{Key:Value}数据,元数据区则提供一些索引指针等管理数据,目的是更快速便捷的查找相应的记录。每个区域都是分块存储。元数据又分为四种不同类型:紫色的Meta Block,红色的MetaBlock索引和蓝色的数据索引块以及一个文件尾部块。LevelDB 1.2版对于Meta Block尚无实际使用,只是保留了一个接口,估计会在后续版本中加入内容,下面我们看看数据索引区Index block和文件尾部Footer的内部结构。 图3 数据索引   图3是数据索引的内部结构示意图。数据索引区的每条记录是对某个Data Block建立的索引信息,每条索引信息包含三个内容。以图3所示的数据块i的索引Index i来说:红色部分的第一个字段记载大于等于数据块i中最大的Key值的那个Key,第二个字段指出数据块i在.sst文件中的起始位置,第三个字段指出Data Block i的大小(有时候是有数据压缩的)。后面两个字段好理解,是用于定位数据块在文件中的位置的,第一个字段需要详细解释一下,在索引里保存的这个Key值未必一定是某条记录的Key。以图3的例子来说,假设数据块i 的最小Key=“samecity”,最大Key=“the best”;数据块i+1的最小Key=“the fox”,最大Key=“zoo”,那么对于数据块i的索引Index i来说,其第一个字段记载大于等于数据块i的最大Key(“the best”)同时要小于数据块i+1的最小Key(“the fox”),所以例子中Index i的第一个字段是:“the c”,这个是满足要求的;而Index i+1的第一个字段则是“zoo”,即数据块i+1的最大Key。         文件末尾Footer块的内部结构见图4,metaindex_handle指出了metaindex block的起始位置和大小;inex_handle指出了index Block的起始地址和大小;这两个字段可以理解为索引的索引,是为了正确读出索引值而设立的,后面跟着一个填充区和魔数。 图4 Footer         上面主要介绍的是元数据区的内部结构,下面我们看看数据区的一个Block的数据部分内部是如何布局的(图1中的红色部分),图5是其内部布局示意图。 图5 数据Block内部结构   从图中可以看出,其内部也分为两个部分,前面是一个个KV记录,其顺序是根据Key值由小到大排列的,在Block尾部则是一些“重启点”(Restart Point),其实是一些指针,指出Block内容中的一些记录位置。         “重启点”是干什么的呢?我们一再强调,Block内容里的KV记录是按照Key大小有序的,这样的话,相邻的两条记录很可能Key部分存在重叠,比如key i=“the Car”,Key i+1=“the color”,那么两者存在重叠部分“the c”,为了减少Key的存储量,Key i+1可以只存储和上一条Key不同的部分“olor”,两者的共同部分从Key i中可以获得。记录的Key在Block内容部分就是这么存储的,主要目的是减少存储开销。“重启点”的意思是:在这条记录开始,不再采取只记载不同的Key部分,而是重新记录所有的Key值,假设Key i+1是一个重启点,那么Key里面会完整存储“the color”,而不是采用简略的“olor”方式。Block尾部就是指出哪些记录是这些重启点的。 图6 记录格式   在Block内容区,每个KV记录的内部结构是怎样的?图6给出了其详细结构,每个记录包含5个字段:key共享长度,比如上面的“olor”记录, 其key和上一条记录共享的Key部分长度是“the c”的长度,即5;key非共享长度,对于“olor”来说,是4;value长度指出Key:Value中Value的长度,在后面的Value内容字段中存储实际的Value值;而key非共享内容则实际存储“olor”这个Key字符串。   以上这些就是.sst文件的全部奥秘。

LevelDB专题三: Log文件格式

上节内容讲到Log文件在LevelDB中的主要作用是系统故障恢复时,能够保证不会丢失数据。因为在将记录写入内存的Memtable之前,会先写入log文件,这样即使系统发生故障,Memtable中的数据没有来得及Dump到磁盘的SSTable文件,LevelDB也可以根据log文件恢复内存的Memtable数据结构内容,不会造成系统丢失数据,在这点上LevelDb和Bigtable是一致的。 对于一个log文件,LevelDB会把它切割成以32K为单位的物理Block(可以做Block Cache),Block作为基本读取单位。下图展示的log文件由3个Block构成,所以从物理布局来讲,一个log文件就是由连续的32K大小Block构成的。 在应用的视野里是看不到这些Block的,应用看到的是一系列的Key:Value对,在LevelDB内部,会将一个Key:Value对看做一条记录的数据,另外在这个数据前增加一个记录头,用来记载一些管理信息,以方便内部处理,下图显示了一个记录在LevelDB内部是如何表示的。 记录头包含三个字段,CheckSum是对“类型”和“数据”字段的校验码,为了避免处理不完整或者是被破坏的数据,当LevelDB读取记录数据时候会对数据进行校验,如果发现和存储的CheckSum相同,说明数据完整无破坏,可以继续后续流程。“记录长度”记载了数据的大小,“数据”则是上面讲的Key:Value数值对,“类型”字段则指出了每条记录的逻辑结构和log文件物理分块结构之间的关系,具体而言,主要有以下四种类型:FULL/FIRST/MIDDLE/LAST。 如果记录类型是FULL,代表了当前记录内容完整地存储在一个物理Block里,没有被不同的物理Block分割;如果记录被相邻的物理Block切割开,则类型会是其他三种类型中的一种。我们以图1所示的例子来具体说明。 假设目前存在三条记录,Record A,Record B和RecordC。其中Record A大小为10K,RecordB 大小为80K,Record C大小为12K,那么其在log文件中的逻辑布局会如图1所示。 Record A是图中蓝色区域所示,因为大小为10K<32K,能够放在一个物理Block中,所以其类型为FULL;Record B 大小为80K,而Block1因为放入了Record A,所以还剩下22K,不足以放下Record B,所以在Block1的剩余部分放入Record B的开头一部分,类型标识为FIRST,代表了是一个记录的起始部分;RecordB还有58K没有存储,这些只能依次放在后续的物理Block里面,因为Block 2大小只有32K,仍然放不下Record B的剩余部分,所以Block 2全部用来放RecordB,且标识类型为MIDDLE,意思是这是Record B中间一段数据;Record B剩下的部分可以完全放在Block3中,类型标识为LAST,代表了这是Record B的末尾数据;图中黄色的Record C因为大小为12K,Block 3剩下的空间足以全部放下它,所以其类型标识为FULL。 从这个例子可以看出逻辑记录和物理Block之间的关系,LevelDB一次物理读取为一个Block,然后根据类型情况拼接出逻辑记录,供后续流程处理。 Log文件在每次写入后都必须调用Flush()将数据写入磁盘,否则可能造成数据丢失;另外LevelDB只会在启动时才可能去读取Log文件,在内存中重放日志。

LevelDB专题二: 整体架构

LevelDB本质上是一套存储系统以及在这套存储系统上提供的一些操作接口。为了便于理解整个系统及其处理流程,我们可以从两个不同的角度来看待LevleDB:静态角度和动态角度。 从静态角度,可以假想整个系统正在运行过程中(不断插入删除读取数据),此时我们给LevelDB照相,从照片可以看到之前系统的数据在内存和磁盘中是如何分布的,处于什么状态等。从动态的角度,主要是了解系统是如何写入一条记录,读出一条记录,删除一条记录的,同时也包括除了这些接口操作外的内部操作比如compaction,系统运行时崩溃后如何恢复系统等等方面。