天天看点

leveldb源码分析之log文件结构理论基础

log文件在LevelDb中的主要作用是系统故障恢复时,能够保证不会丢失数据。因为在将记录写入内存的Memtable之前,会先写入Log文件,这样即使系统发生故障,Memtable中的数据没有来得及Dump到磁盘的SSTable文件,LevelDB也可以根据log文件恢复内存的Memtable数据结构内容,不会造成系统丢失数据.

leveldb源码分析之log文件结构理论基础

LevelDb对于一个log文件,会把它切割成以32K为单位的物理Block,每次读取的单位以一个Block作为基本读取单位,下图展示的log文件由3个Block构成,所以从物理布局来讲,一个log文件就是由连续的32K大小Block构成的

leveldb源码分析之log文件结构理论基础

在应用的视野里是看不到这些Block的,应用看到的是一系列的Key:Value对,在LevelDb内部,会将一个Key:Value对看做一条记录的数据,另外在这个数据前增加一个记录头,用来记载一些管理信息,以方便内部处理,图3.2显示了一个记录在LevelDb内部是如何表示的。 记录头包含三个字段,ChechSum是对“类型”和“数据”字段的校验码,为了避免处理不完整或者是被破坏的数据,当LevelDb读取记录数据时候会对数据进行校验,如果发现和存储的CheckSum相同,说明数据完整无破坏,可以继续后续流程。“记录长度”记载了数据的大小,“数据”则是上面讲的Key:Value数值对,“类型”字段则指出了每条记录的逻辑结构和log文件物理分块结构之间的关系,具体而言,主要有以下四种类型:FULL/FIRST/MIDDLE/LAST

CheckSum,即CRC验证码,占4个字节
记录长度,即数据部分的长度,2个字节
类型,这条记录的类型,后续讲解,1个字节
数据,就是这条记录的数据。
           

如果记录类型是FULL,代表了当前记录内容完整地存储在一个物理Block里,没有被不同的物理Block切割开;如果记录被相邻的物理Block切割开,则类型会是其他三种类型中的一种。

结合上面的分析,整个log结构如下:

leveldb源码分析之log文件结构理论基础

LevelDB 的 log 文件内容被组织成多个 32 KB 的定长块(block)。每个 block 由 1~多个 record 组成(末尾可能会 padding)。一个 record 由一个固定 7 字节的 header(checksum: uint32 + length: uint16 + type: uint8) 和实际数据(data: uint8[length])组成。

如果 block 的末尾不足 7 字节(小于 header 的大小),则全部填 0x00,读取的时候会被忽略。

如果 block 的末尾刚好 7 字节,则填充一个 length 为 0 的 record。

下面,我们将上层写入的数据称之为 user record,以区分 block 中的 record。由于 block 是定长的,而 user record 是变长的,一个 user record 有可能被截断成多个 record,保存到一段连续的 block 中。因此,在 header 中有一个 type 字段用来表示 record 的类型:

下面以一个例子来解释上面的过程。

初始化整个 log 为空,假设我们有 3 个 user records:

  • A 大小为 1000 字节
  • B 大小为 97270 字节
  • C 大小为 8000 字节

    A 小于 32KB,会被保存到第一个 block,长度为 1000,类型为 kFullType,占用空间为 7 + 1000 = 1007。

B 比较大,会被切分成 3 个分片,保存到不同的 block:

第一个分片保存到第一个 block,长度为 31754 字节,类型为 kFirstType。因为保存 A 之后,这个 block 剩余的空间为 32768 - 7 - 1000 = 31761 字节。除去 header,可以保存 B 的前 31761 - 7 = 31754 字节。此时 B 还有 97270 - 31754 = 65516 字节需要保存。

65516 字节超过了一个 block 的大小,所以第二个分片需要完整占用第二个 block,长度为 32768 - 7 = 32761 字节,类型为 kMiddleType。此时 B 还有 65516 - 32761 = 32755 字节需要保存。

B 的第三个分片保存到第三个 block ,长度为 32755,类型为 kLastType。第三个 block 剩余的空间为 32768 - 7 - 32755 = 6 字节。由于 6 字节小于一个 header 的大小(7 字节),会被进行 padding(填 0)。

C 会被保存到第四个 block,长度为 8000 字节,类型为 kFullType,占用空间 7 + 8000 = 8007。

综上,A、B、C 在 log 文件中的结构如下。

leveldb源码分析之log文件结构理论基础

LevelDB 为什么采用这种定长块的方式保存日志呢?一个明显的好处就是,当日志文件发生数据损坏的时候,这种定长块的模式可以很简单地跳过有问题的块,而不会导致局部的错误影响到整个文件。