0%

LevelDB源码解析(四)- SSTable解析

前言

SSTable就是把一个跳表放入一个文件,但是我们不仅仅是把KeyValue写入文件就结束了,还需要做一些其他的事:

  1. 写入KV
  2. SSTable的一些元信息,如最大Key,最小Key,KV的个数等。
  3. 为KV维护一定的索引,加速查找
  4. 进行一定比例的数据压缩
  5. 数据完整性校验

文件的大体格式如下:

文件的格式大致分为一个一个的Block

  1. Data Block存储的是数据,就是KV。
  2. MetaIndex Block
  3. Index Block
  4. Footer

其中在源码中,DataBlock是大头,2和3叫Footer。

MetaIndex在Java版本的实现中是个空Block。

这三个Block的底层实现都是BlockBuilder,BlockBuilder是个存储KV的格式。

个人感觉上其实BlockBuilder是为了DataBlock打造的,而IndexBlock只是恰好复用了一下。

所以下文将的DataBlock其实就是DataBlock的机制。

DataBlock

BlockBuilder的切分是根据每个Block的大小定的。

当一个Block的大小超过4 * 1024,也就是4M的时候,就会阶段,重启一个Block。

在Block内部的数据,也不是全部堆在一起,而是分为一组一组的,叫做DataGroup(非官方定义,我定的名字)。

分组个数是固定的,根据配置的blockRestartInterval来,默认是16个KV一组。

为什么要进行分组呢,其实这里要提一下写入数据时的压缩。

比如连续的两个Key,”the car”和”the car window”,他们有共同的前缀”the car”,对于这个前缀,我们可以只写入一份来起到数据压缩的效果。

如果我们不分组,那么我们找到一个Key,想知道他原来的Key是啥,得遍历前面所有的Key,这是不现实的。

所以每隔16个KV,我们就从头开始存储,不计算与之前的Key的共同前缀了。

假设我们put三个Entry,三个InternalKey如下:

1
2
3
1. userKey=foo123, seq = 3, type=VALUE, value = "fvdnvfdn"
2. userKey=foo456, seq = 4, type=VALUE, value = "nvjkdfniq"
3. userKey=foo444, seq = 1, type=VALUE, value = "vfnvfdn233"

写SSTable了,真正写入的Bytes,会对InternalKey调用encode方法

1
2
3
4
5
6
7
public Slice encode() {
Slice slice = Slices.allocate(userKey.length() + SIZE_OF_LONG);
SliceOutput sliceOutput = slice.output();
sliceOutput.writeBytes(userKey);
sliceOutput.writeLong(SequenceNumber.packSequenceAndValueType(sequenceNumber, valueType));
return slice;
}

大致就是把seq + valueType拼成一个Long类型,和userKey合在了一起。

写入一个KV的操作基本流程如下:

1
2
3
4
5
6
7
int sharedKeyBytes = calculateSharedBytes(key, lastKey);  // 1
int nonSharedKeyBytes = key.length() - sharedKeyBytes; // 2
VariableLengthQuantity.writeVariableLengthInt(sharedKeyBytes, block); // 3
VariableLengthQuantity.writeVariableLengthInt(nonSharedKeyBytes, block); // 4
VariableLengthQuantity.writeVariableLengthInt(value.length(), block); // 5
block.writeBytes(key, sharedKeyBytes, nonSharedKeyBytes); // 6
block.writeBytes(value, 0, value.length()); // 7

这里我们以

1
2
1. userKey=foo123, seq = 3, type=VALUE, value = "fvdnvfdn"
2. userKey=foo456, seq = 4, type=VALUE, value = "nvjkdfniq"

这两个KeyValue为例,假设foo123已经被写入了,就是lastKey,当前的Key=foo456,其实实际上不是这样的,这里实际拿到的值已经被拼了末尾的Long类型进去,这里为了好解释。同时写入数值也会做相应的转换,这里先忽略。

  1. foo123foo456sharedKeyBytes,也就是开始的foo,数值为3
  2. nonSharedKeyBytes也即是456,数值也是3
  3. 这一步写入sharedKeyBytes值到文件中,文件内容变成 3
  4. 写入nonSharedKeyBytes,文件内容为3 | 3
  5. 写入Value的长度,文件内容变成3 | 3 | 8 |
  6. 写入非共同前缀的字符也就是456,文件内容为 3 | 3 | 8 | 456 |
  7. 写入Value的值,文件内容为 3 | 3 | 8 | 456 | fvdnvfdn

所以整体来看,一个DataGroup中每行Record的数据如下:

前面提到,每个DataGroup有16行,超过16行之后,就会置LastKey为空,然后下一行开始的sharedKeyBytes就是0,nonSharedKeyBytes就是当前Key的完整长度。

下面就要为每个DataGroup建立索引,记录每个DataGroup的开始位置。

变量restartPositions就是为这个索引准备的。

第一个DataGroup的位置就是0。

数据写完之后,把每个DataGroup的开始Offset写入到这个Block中。

看源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public Slice finish()
{
if (!finished) {
finished = true;
if (entryCount > 0) {
restartPositions.write(block); //1
block.writeInt(restartPositions.size());
}
else {
block.writeInt(0);
}
}
return block.slice();
}

//1的源码
public void write(SliceOutput sliceOutput)
{
for (int index = 0; index < size; index++) {
sliceOutput.writeInt(values[index]);
}
}

数据写完后,如果符合压缩条件,还要进行数据压缩。

最后补上Trailer,Trailer就一个Byte和一个Int,Byte表示压缩方式,Int表示对数据的CRC32,用来验证数据完整性。

最后整个DataBlock的数据如下:

Index Block

Index Block的内容每次写入一个DataBlock都会新增。

这里的代码其实还比较绕人,主要是findShortestSeparator这个方法。

让我们先抛开源代码,想一想对DataBlock建立索引需要记录哪些信息。

  1. 最大Key,最小Key
  2. KV的个数
  3. StartOffset,EndOffset

先来看看最大Key和最小Key的问题。

建立这个索引,主要是为了搜索Key,和最大的比较和最小的比较一下,就能知道是否在这个DataBlock中。

那么

问题1:是否需要最小Key?看源码,是Index Block中并没有存。

问题2:是否需要最大Key?是需要的,不过这里并没有存最大Key是什么。为什么?

或者我们再反问一句,存最大Key的意义是为了记录这个DataBlock里面的数据的边界,如果我们存储比MaxKey稍大一点的Key是不是也是同样的效果呢?

举个例子:MaxKey = helloworld,下一个Block的最小Key是hellozoomer,那么我们存储hellox,是不是可以起到同样的效果呢?

这就是方法findShortestSeparator的功能。

算出来一个Key,这个Key > MaxKey && Key < nextBlockFirstKey。能够起到和MaxKey一样的作用,同时存储时能够压缩空间。

解决了问题2,我们再来看看问题1,为啥IndexBlock中没有存MinIndex,我感觉是这样

又不是不能用。

shortestSeparator既可以表示前一个Block的MaxKey,又可以表示后一个Block的MinKey

IndexBlock复用的DataBlock的格式,存储MinKey不太方便

按照上面一个观点,其实一个DataBlock中的KV的个数,在IndexBlock中也没有存储。

其实如果我们看到后面那个,BlockIterator::seak方法,进行二分查找的时候,是直接seek到那个位置,然后读取出第一个Key的。

下面看看IndexBlock的存储。

每写完一个DataBlock,会返回这个DataBlock的两个数值

  1. offset:在文件中的offset
  2. dataSize:block的存储长度

在IndexBlock中,将shorttestSeparator作为key,(offset + dataSize)统一作为Value,构造出一个KV的结构放进去。

其实IndexBlock和DataBlock底层都是BlockBuilder的实现。

所以IndexBlock的格式和DataBlock是一样的。

MetaIndex Block

我看Java版本的实现中是个空Block。

Footer主要是为了记录MetaIndexBlock和IndexBlock的位置信息和一些填充字段和MagicWord。

直接上源码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static void writeFooter(Footer footer, SliceOutput sliceOutput)
{
// remember the starting write index so we can calculate the padding
int startingWriteIndex = sliceOutput.size();

// write metaindex and index handles
writeBlockHandleTo(footer.getMetaindexBlockHandle(), sliceOutput); //1
writeBlockHandleTo(footer.getIndexBlockHandle(), sliceOutput); //2

// write padding
sliceOutput.writeZero(ENCODED_LENGTH - SIZE_OF_LONG - (sliceOutput.size() - startingWriteIndex));//3

// write magic number as two (little endian) integers
sliceOutput.writeInt((int) TableBuilder.TABLE_MAGIC_NUMBER); //4
sliceOutput.writeInt((int) (TableBuilder.TABLE_MAGIC_NUMBER >>> 32));
}
  1. 写入MetaIndexBlock的位置信息(offset + size)
  2. 写入IndexBlock的位置信息(offset + size)
  3. padding
  4. MagicNumber

Table的读取和iterator

对SSTable的读取,需要传入的是SSTable的fileChannel,然后进行初始化:

1
2
3
4
5
6
7
8
9
public Table(String name, FileChannel fileChannel, Comparator<Slice> comparator) {
//...
this.name = name;
this.fileChannel = fileChannel;

Footer footer = init(); // 1
indexBlock = readBlock(footer.getIndexBlockHandle()); //2
metaindexBlockHandle = footer.getMetaindexBlockHandle();
}
  1. seek到文件的尾部,把MetaIndexBlock的位置信息 + IndexBlock的位置信息读取出来
  2. 把IndexBlock的信息全部读取到内存中来

因为DataBlock和IndexBlock的底层都是Block,所以这里先提一下对Block的迭代方法:

实现类是BlockIterator

再回顾下之前的Block的格式

数据每16个KV一组分为DataGroup,在Block的尾部记录每个DataGroup的位置信息,也就是重启点位置。

这里的迭代分几个重要的点:

  1. 重启点的信息可以全部在初始化的时候就反序列化成数组
  2. 遍历DataGroup的KV时,需要记录上一个Key的原始值,不然不好恢复出当前Key的值
  3. 二分搜索时,转化成对RestartPositions数组的二分搜索

讲完了对Block的迭代,下面讲讲对SSTable的迭代

对SSTable的迭代在方法Table::iterator

方法的实现如下:

1
2
3
4
public TableIterator iterator()
{
return new TableIterator(this, indexBlock.iterator());
}

这里的TableIterator的实现思想和Block的迭代的实现思想差不多。

IndexBlock的KV,是对前面DataBlock的【分割Key】+ 位置信息的保存。

所以这里的TableIterator的实现思想是:

  1. 遍历时,转化成对IndexBlock和DataBlock的双层遍历。
  2. 每次读取一个DataBlock在内存中。如果当前DataBlock遍历结束,就从IndexBlock读取下一个DataBlock的位置,seek到那个位置,把下一个DataBlock全部读取到内存中,再对这个DataBlock进行遍历。
  3. 二分查找,先对IndexBlock进行二分查找,找到【分割Key】的所在的DataBlock的位置信息,然后再读取改DataBlock,在这个DataBlock中进行二分搜索。

Welcome to my other publishing channels