in LevelDB 分布式数据库 ~ read.

LevelDB组件-SST

LevelDB组件-SST

SST ( Sort String Table)

LevelDB 里的数据在磁盘上就是以 SST 文件的格式存储的。最新版本的 SSTable 文件名后缀为 ldb, 同时保留了 sst 后缀的兼容。

SST 整体结构

![SST_arch](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-sst.md/105792711238554.png =843x)

Record

用户存入的键值对

![record](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-sst.md/451914211234913.png =719x)

前文提到,skiplist 里面保存的每一个节点的格式是 memtable_key+memtable_value, 所以每个节点里都保存有 user key 的全部信息。但是实际上,对于相邻的节点,user key 有较大几率是有一定重合的。所以在把数据保存到磁盘上的 sst 文件的时候,为了节省空间,LevelDB 对 user key 利用相同的前缀做了一定的压缩.

每一条记录有 key共享长度key非共享长度value长度key非共享内容 + value内容组成. 两条记录如果 user key 有相同的部分,那么第二条记录可以和第一条共享相同的前缀.

比如我们有两条记录需要保存。第一条记录为 hello_world:9,第二条记录为 hello_you:18.

那么第一条记录存储格式为:

0 + 11 + 1 + hello_world + 9

0 是因为默认第一条记录的共享长度为 0. 11 是 "hello_world" 的长度,因为第一条记录没有共享前缀,所以非共享的长度就是 key 的整个长度. 1 是第一条记录的 value 在 varint 编码下占用的字节长度。因为没有共享,所以最后两个部分就是完整的 user key: hello_world 和 user value: 9.

第二条记录存储格式为:

6 + 3 + 1 + you + 18

6 是因为第二条记录和第一条有共享的 hello_前缀,长度为 6. 3 是因为非共享的部分 you 的长度为 3. 1 是第二条记录的 value 在 varint 编码下占用的字节长度。然后最后两个部分是 key 的非共享内容: you 和 user value: 18.

虽然共享前缀能够减少存储空间,但是假如我们有 1000 条记录,我们不可能全部和第一条记录的前缀去计算共享的部分,因为随着 key 的距离间隔变大,key 也会变的越来越不一样,相同的部分会减少。所以我们需要隔一段距离设置一个 restart point, 把当前的 key 设置为比较的基准点,之后的 key 会和新的基准点进行前缀的比较. LevelDB 里默认是每隔 16 条记录就会设置一个 restart point.

Block

LevelDB 把 sst 文件划分为一个一个 block, 根据不同的类型又分为 data block, data block index, meta block, meta block index. 其中 meta block 和 meta block index 只有在打开数据库时传入 filter policy 参数才会有,这里我们只关注 data block 和 data block index.

data block部分, 保存的是用户的键值对信息,也就是上面的一条条的record

每个 block 的大小默认为 4096KB。

data block index 部分,保存的其实就是每个 data block 的起始地址和那个 block 相应的 key 值信息。所以在查询的时候,我们能够迅速定位到自己想要查询的 user key 值在哪个 block 中。

data block

![](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-sst.md/38265714217837.png =729x)

每个 block 包含三个部分:

  • block content: 具体的数据
  • compression type: block content 里面的数据可能是被压缩过了,比如 LevelDB 支持用 snappy 进行压缩,所以这里需要指明 block content 里的数据是如何压缩的。长度为 1 字节.
  • CRC number: 这里存放 block content 加上 compression type 的 CRC32 校验码,用来确保 block 数据的完整性和正确性,长度为 4 字节.

Block Content 中,存放的是一条一条的记录,还有我们之前提到的 restart point 信息,因为一个 block 中会有多个重启点 (每隔 16 条记录就会有一个,16条记录计算前缀压缩), 所以 restart point 的信息保存在 array 里,我们需要记录每个重启点在文件里的偏移量(int)还有这个 array 的长度(int)。其中,每个重启点的偏移量所占用的文件大小为 4 字节,假设一共有 100 个重启点,则这部分的信息一共会占用 100*4 + 4 (array长度) = 404 字节.

![restartpoint](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-sst.md/36700816226114.png =558x)

data index block

SST 文件的索引块里,保存的就是当前文件中每个 block 在文件中的起始偏移量和每个 block 对应的 key 的信息,可以方便 LevelDB 在查找一个 user key 的时候快速的定位到 user key 在哪一个 block 中。索引块里保存的也是一条一条的记录,每一条记录对应着一个 block. 因为 data block 里的数据是根据 key 有序的,意味着对于相邻的两个 block, 前一个 block 里最大的 key, 一定小于后一个 block 中最小的 key.

index block,在实际运行时,尽可能cache在内存中。

索引块里每一条数据分为两个部分:

  • key

    key 值,这个值一定大于等于他所指向的 block 里最大的 key 值,也必须小于它所指向的 block 后面一个 block 中最小的 key 值.

  • BlockHandel

    BlockHandle 对象, BlockHandle 的作用就是方便我们快速的在文件中定位某一个位置.

    BlockHandle 对象里有两个字段:

     - offset: block 的起始位置在当前文件中的偏移量.
     - size: block 的长度.
    

索引块的结构和数据块基本一样,只是在数据块里,存储的是一个个 user key 和 user value. 而在索引块里,存储的是一个个 key 和偏移量.

Meta block

Meta index block 中的每条 key-value 指向一个 meta block。

LevelDB 中只有一个 meta block,保存的是这个 SSTable 中的 key 组成的 bloom filter

![footer](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-sst.md/412334715235478.png =603x)

存储了 data block index 和 meta block index 的 block handle, 方便我们在打开文件的时候能快速定位索引

Footer 长度为固定 2 个 BlockHandle 的最大长度 (20) 和 1 个 64bit 魔数长度,共 48 byte。

BlockHandle 实际长度(编码结果是变长)和最大长度之间的空隙填充为 0(padding).

metaindex_handle 指出了 meta index block 的起始位置和大小.

data index_handle 指出了 index block 的起始地址和大小。

这两个字段都是 BlockHandle 对象,可以理解为索引的索引,通过 Footer 可以直接定位 到 metaindex 和 index block. 最后一个部分是一个固定的常量,被称为魔数 (0xdb4775248b80fb57)。

SST

![sst](https://raw.githubusercontent.com/ccyuki/vnote_img/main/personal/written/leveldb组件-sst.md/295735415226458.png =583x)

  • 通过 Footer 定位到 index block
  • 通过 index block 的 key,定位到具体的 data block
  • 通过 data block 找到 restart point
  • 通过 restart point 进行二分查找,定位到具体的key前缀
  • 通过 key 前缀,遍历16条记录,找到目标 user key

Ref

http://atwoodwang.com/2020/leveldb_sst/