专栏首页linjinhe的专栏LevelDB 完全解析(2):Log

LevelDB 完全解析(2):Log

前文回顾

这里的 log 是指 Write Ahead Log。前面说了,LevelDB 写入的数据会先保存到 MemTable。为了防止宕机导致数据丢失,在将数据写入 MemTable 之前,会先将数据持久化到 log 文件中。

本文主要参考 LevelDB 的文档 log_format.md

Log 的格式

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,读取的时候会被忽略。<br />如果 block 的末尾刚好 7 字节,则填充一个 length 为 0 的 record。

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

enum RecordType {
  // Zero is reserved for preallocated files
  kZeroType = 0,

  kFullType = 1,

  // For fragments
  kFirstType = 2,
  kMiddleType = 3,
  kLastType = 4
};
  1. kFullType - 这是一个完整的 user record。
  2. kFirstType - 这是 user record 的第一个 record。
  3. kMiddleType - 这是 user record 中间的 record。如果写入的数据比较大,kMiddleType 的 record 可能有多个。
  4. kLastType - 这是 user record 的最后一个 record。

Log 的例子

上面这样描述可能比较抽象,这里举个例子来说明一下。

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

  1. A 大小为 1000 字节
  2. B 大小为 97270 字节
  3. C 大小为 8000 字节

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

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

  1. 第一个分片保存到第一个 block,长度为 31754 字节,类型为 kFirstType。因为保存 A 之后,这个 block 剩余的空间为 32768 - 7 - 1000 = 31761 字节。除去 header,可以保存 B 的前 31761 - 7 = 31754 字节。此时 B 还有 97270 - 31754 = 65516 字节需要保存。
  2. 65516 字节超过了一个 block 的大小,所以第二个分片需要完整占用第二个 block,长度为 32768 - 7 = 32761 字节,类型为 kMiddleType。此时 B 还有 65516 - 32761 = 32755 字节需要保存。
  3. 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 文件中的结构如下。

log_example

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

目前 LevelDB 没有对日志进行压缩。

Log 的实现

LevelDB 读写日志的实现逻辑比较清晰,建议根据上面介绍的日志格式仔细看下 log_reader 和 log_write 的实现。

  1. log_format.h - 定义 RecordType、kBlockSize、kHeaderSize。
  2. log_reader.hlog_reader.cc - 日志读取的实现。
  3. log_writer.hlog_writer.cc - 日志写入的实现。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LevelDB 完全解析(1):MemTable

    MemTable,顾名思议,就是内存表。每个 LevelDB 实例最多会维护两个 MemTable: mem_ 和 imm_。mem_ 可以读写,imm_ 只读...

    linjinhe
  • LevelDB 完全解析(3):SSTable

    SSTable 全称 Sorted String Table,顾名思义,里面的 key-value 都是有序保存的。除了两个 MemTable,LevelDB ...

    linjinhe
  • LevelDB 完全解析(4):Manifest

    内容上,Manifest 文件保存了整个 LevelDB 实例的元数据,比如:每一层有哪些 SSTable。 格式上,Manifest 文件其实就是一个 lo...

    linjinhe
  • LevelDB 完全解析(5):Cache

    在 LevelDB 中,block cache 和 table cache 都是基于 ShardedLRUCache 实现的。

    linjinhe
  • LevelDB 完全解析(6):Filter

    LevelDB 可以设置通过 bloom filter 来减少不必要的读 I/O 次数。

    linjinhe
  • LevelDB 完全解析(11):Compaction

    因为 LevelDB 的增删改都是通过追加写来实现的,所以需要通过后台线程的 compaction 来:

    linjinhe
  • LevelDB 完全解析(7):初始化

    options - 打开/创建 LevelDB 实例的配置参数。 dbname - 保存数据的目录名。 dbptr - 初始化成功的 LevelDB 实例保...

    linjinhe
  • LevelDB 完全解析(9):写操作

    以上,便是 LevelDB 的写入流程。写入队列 + 合并写操作,逻辑和代码都十分简洁。比较不足的是,整个写入过程都是单线程的。

    linjinhe
  • LevelDB 完全解析(8):读操作之 Get

    LevelDB 通过 leveldb::DB::Get 接口对外提供点查询的能力,具体的实现是 leveldb::DBImpl::Get。接口声明如下:

    linjinhe
  • LevelDB 完全解析(10):读操作之 Iterator

    通过前面的文章,我们了解到 LevelDB 的数据是保存在内部多个不同组件的,并且每个组件的数据格式都不一样。

    linjinhe
  • lsm派系(不仅lsm tree)存储模型概述(下篇)

    这部分内容主要回答我们在文章开头提到的第二个问题。第二个问题展开其实是一连串的问题。例如:lsm派系难道只有lsm tree这一类存储模型吗?如果答案是否定的,...

    jaydenwen123
  • 【深度知识】LevelDB从入门到原理详解

    LevelDB是Google开源的持久化KV单机数据库,具有很高的随机写,顺序读/写性能,但是随机读的性能很一般,也就是说,LevelDB很适合应用在查询较少,...

    辉哥
  • 【深入浅出leveldb】文件类型与文件名

    leveldb运行一段时间后,系统中会产生一些文件,这些文件有哪些,各个文件又有什么作用,文件名怎么命名的呢?

    公众号guangcity
  • ZBS:SmartX 分布式块存储 -- 元数据篇

    以下文章转载于SmartX知乎博客,不同与国内的很多公司,SmartX完全自主开发了分布式块存储-ZBS,整个系统从架构到实现充分考虑了超融合系统的特点,以下内...

    大数据和云计算技术
  • LevelDB 完全解析(0):基本原理和整体架构

    之前零零散散写过几篇和 LSM-Tree、LevelDB 有关的文章。之后也看了一些代码和论文,笔记也做了一些,但大都比较零乱、随意,没花功夫整理。

    linjinhe
  • leveldb实现分析

    | 导语  leveldb是google开源的单机key-value存储引擎。基于Log-Structured-Merge Tree的实现。本文先介绍leve...

    腾讯Bugly
  • cmake:vs2015/MinGW静态编译leveldb

    leveldb是google的开源项目(https://github.com/google/leveldb), 在linux下编译很方便,然而官方版本却没有提供...

    用户1148648
  • LevelDB

    无论是 put 、 delete 还是batch操作,leveldb 底层都是以 batch 作为执行实例。

    itliusir
  • LevelDB原理解析:数据的读写与合并是怎样发生的?

    导语 | LevelDB是一款十分优秀的存储引擎,具有极高的数据读写性能,尤其是写入性能,在笔者经历的多个项目中都有用到,因此本文打算结合LevelDB的部分源...

    腾小云

扫码关注云+社区

领取腾讯云代金券