磁盘上的数据结构

发表于 |

本文主要介绍在设计需要序列化到磁盘上的数据结构时，需要考虑的点。

设计要点

序列化和反序列化(serde)

这里的要点，并不只局限在类似于 protobuf 的库上，而是在设计存储格式的时候，都会考虑的问题。

需要关注的 feature：

  • 对于 blob 的支持
    解析是否需要占用大量内存？
  • 读取部分数据
    是否需要解压/解码全部结构，才能读取到该数据呢？
  • 兼容性
    新旧版本应该能够处理彼此的数据。例如：
    • 旧版本能够忽略新增的字段，对于后续被删除的字段，也会保留其编号。
    • 新版本对于旧消息中缺失的字段能补上默认值，或者填入 null。
  • 类型的 cast
    例如支持从 bool 升级为 enum 或者 int。
  • 磁盘 IO 的单位
  • 压缩和解压缩的速度，以及 CPU 开销、内存开销
    需要注意，磁盘 IO 的单位并不一定要和解压缩的单位对应。完全可以从磁盘取一批数据到内存，以最大化利用磁盘带宽。但内存中的数据如何解压缩则纯粹是 CPU bound 的问题了。
    如果预期只需要读一两条的数据，那么就希望有更多的索引能够帮助我们快速 seek 到指定的位置，并解压足够小的 block。但如果预期需要读取所有数据，那么每次解压的单位就可以大很多，从而索引的大小就能做到更小。
  • 编码和解码的速度，以及 CPU 开销、内存开销
    这一点很重要，例如 json 的编解码性能就比较差。
  • 是否可以自描述？
    出于空间考虑，就不会包含，但这就会导致像 Parquet 一样的问题。因为解析库是由不同的语言和库来实现的，因此编码库会担心自己的编码用了新特性，从而导致别人解析不了。
  • 是否有足够的容错

磁盘上的数据结构

  • 完整性校验
  • 尽可能减少 IO 次数
  • 是否多个文件或者多级文件？
  • 是否分开存储 meta 和 data？先写 meta 还是先写 data？

常见格式

Parquet

假设一个表中有 N 列，它们被分入了 M 个 row groups 中。那么每个 row groups 中的一个 Column 称为一个 Column Chunk。

文件的 metadata 包含了每个 Column Chunk 的开始位置。为了能够一趟写完文件，所以最后才会写入 metadata。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
4-byte magic number "PAR1"
<Column 1 Chunk 1>
<Column 2 Chunk 1>
...
<Column N Chunk 1>
<Column 1 Chunk 2>
<Column 2 Chunk 2>
...
<Column N Chunk 2>
...
<Column 1 Chunk M>
<Column 2 Chunk M>
...
<Column N Chunk M>
File Metadata
4-byte length in bytes of file metadata (little endian)
4-byte magic number "PAR1"

在读取时，首先需要读取 metadata，从而定位到所有要读取的 Column Chunks。这些 Column Chunk 稍后可以被顺序读取出来。

Parquet 的格式的设计思想是将 metadata 和 data 分开，这使得可以将 Column 们分入到不同的文件中。于此同时，有一个单独的 metadata 文件去索引多个 parquet 文件。

从下面的图片中可以看到，Parquet 文件实际上是自包含的，也就是说单个 Parquet 文件已经包含完整的数据和元数据，无需依赖外部元数据文件。像 Spark 之类的系统确实会创建一个全局的 metadata 文件，但它的作用就是方便快速的索引。

因为 metadata 在 parquet 文件的 Footer 处，所以需要先读取文件的倒数第 5 到 8 字节，得到它的大小，然后再往前 seek 这个大小解析出 metadata 部分。

Parquet 是使用 Thrift 协议解析序列化的。它和 protobuf 其实差不多，不过 Thrift 自带了 RPC。

Types

Parquet 会在 Column Chunk 层面保存 min max 值。

Nested Encoding

关于 Dremel 格式，可以看 https://paper-notes.zhjwpku.com/datalayout/dremel.html。

To encode nested columns, Parquet uses the Dremel encoding with definition and repetition levels. Definition levels specify how many optional fields in the path for the column are defined. Repetition levels specify at what repeated field in the path has the value repeated. The max definition and repetition levels can be computed from the schema (i.e. how much nesting there is). This defines the maximum number of bits required to store the levels (levels are defined for all values in the column).

Two encodings for the levels are supported BIT_PACKED and RLE. Only RLE is now used as it supersedes BIT_PACKED.

Column chunks

错误恢复

如果文件的 metadata 丢失了，那么文件损坏。如果 Column 的 metadata 丢失了，那么这个 Column Chunk 就损坏了。但是这个 Column 在其他 row group 中的部分是 OK 的。如果 page header 丢失了，那 chunk 中剩余的 page 就丢失了。如果 page 中的 data 损坏了，那么这个 page 就丢失了。

因此，如果 row group 设置的比较小，那么文件可能在 resilient 上更好。但是，这会 file metadata 更大。如果在写入 metadata 的时候出现问题，那么所有写入的数据都丢失了。一个做法是每写 N 个 row group，就写一次 metadata。每个 metadata 都是 cumulative 的，并且包含了写到现在所有的 row group。

Combining this with the strategy used for rc or avro files using sync markers, a reader could recover partially written files.

Avro

LevelDB/RocksDB 的 WAL

见 LevelDB 之 WAL

Dremel

如下图所示，dremel 可以将 nesting 的格式，例如 protobuf 或者 json 拍平成适合列式存储的格式。那么多个 doc 就会被转换成一定数量的列。如下图所示，2 个 doc 被用 6 个列存储。我们不需要记录“内部节点”，只需要记录“叶子节点”就行。

容易看到，每个列的长度是不一样的。这是因为 nesting 格式主要的复杂点是存在 option 和 repeated 的情况。

如果没有上述的情况，就可以理解为一个只包含基础类型的 struct。那么：

  • 如上图所示，每个 fullpath 作为一列。对于每个 doc，按照 fullpath 拍平，将值对应存储到各列就行。这个过程称为 strip。
  • 读取的时候，可以直接按照顺序从各个列中还原成原来的文档，不同列相同的 offset 肯定属于同一个文档。
  • 所有列的长度是一样的。

但是如果有了 option 和 repeated，就不是这样了。

解决方案是引入两个计数：

  • Repetiton Level
    表示这个值在 full path 的哪一级进行重复。如果为 0，说明这是一个新的 doc。
    在下面的例子中，考虑 Name.Language 这个列的 Repetiton Level 值：

    • 如果为 R = 1，就表示在当前这个 doc 中，还有一个 Name 字段。对应如下的情况：

      1
      2
      3
      4
      5
      Doc 1
          Name 1
              Language 1
          Name 2
              Language 2  <====== 属于 Name 2

    • 如果为 R = 2，就表示在当前这个 doc 中，当前这个 Name 字段中，还有一个 Language 字段。对应如下的情况：

      1
      2
      3
      4
      Doc 1
          Name 1
              Language 1
              Language 2  <====== 属于 Name 1

    容易看出，如果没有 Repetition Level，我们无法分清上面两种情况。

  • Definition Level
    用来解决 option 字段的问题。只有 option 和 repeated 字段才需要 definition level，required 的字段不需要。
    如果没有 Definition Level 会怎么样呢？考虑下面的 Schema

    1
    2
    3
    4
    5
    message M {
      repeated group A {
        optional int32 B;
      }
    }

    然后在列存中是

    1
    2
    3
    4
    B = 1
    B = NULL
    B = NULL
    B = 2

    那么它对应的真实数据可能是

    1
    2
    3
    4
    5
    6
    7
    8
    9
    Doc 1
        A
            B   1
            B   NULL
    Doc 2
        A   NULL
    Doc 3
        A
            B   2

    这种情况对应的 Repetiton Level 是 [0, 1, 0, 0]。但是，它有可能是

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    Doc 1
        A
            B   1
            B   NULL
    Doc 2
        A
            B   NULL
    Doc 3
        A
            B   2

    也就是我们无法分辨 Doc 2 中究竟是：

    • A 是空列表
    • A 不是空列表，但是它的唯一元素中的 B 为 NULL

下图中是一个概括性的示例：

  • required 字段的 R level 和 D level 和父亲一样
  • option 字段的 R level 不变，D level 递增
  • repeated 字段的 R level 和 D level 都递增

下面是个 demo，几个关键点：

  • Links.Backward: NULL, R:0, D:1
    如果一个 repeated 或者 optional 字段为空，需要写一个 NULL。
    这里 D 为 1 是因为 Links 是有值的，它的 level 是 1。
  • Name.Language.Code: en-us, R:0, D:2
    尽管在同一个 doc 里面，但这里 R 是 0 而不是 1，因为这里的 Name 没有重复。
    其实这也很好理解，因为 Links.* 和 Name.* 是两个列了，所以不能因为觉得这里的 Name 和上面的 Links 同属一个文档，这个文档就是重复的。
    这里 D 为 2 是因为 Name 和 Language 都是 repeated 字段，所以都自增 1，但是 Code 是 required 的字段，就不需要自增，结果为 2。
  • Name.Language.Country: us, R:0, D:3
    和上面唯一的区别就是 Country 为 optional，所以 D 还要自增 1，所以为 3。
Schema Document Dremel format 
    message Document {
        required int64 DocId;
        optional group Links {
            repeated int64 Backward;
            repeated int64 Forward;
        }
        repeated group Name {
            repeated group Language {
                required string Code;
                optional string Country;
            }
            optional string Url;
        }
    }
    
    DocId: 10
    Links
      Forward: 20
      Forward: 40
      Forward: 60
    Name
      Language
        Code: 'en-us'
        Country: 'us'
      Language
        Code: 'en'
      Url: 'http://A'
    Name
      Url: 'http://B'
    Name
      Language
        Code: 'en-gb'
        Country: 'gb'
    
    R = 0 (current repetition level)
    DocId: 10, R:0, D:0
    Links.Backward: NULL, R:0, D:1 (no value defined so D < 2)
    Links.Forward: 20, R:0, D:2
    R = 1 (we are repeating 'Links.Forward' of level 1)
    Links.Forward: 40, R:1, D:2
    R = 1 (we are repeating 'Links.Forward' again of level 1)
    Links.Forward: 60, R:1, D:2
    Back to the root level: R=0
    Name.Language.Code: en-us, R:0, D:2
    Name.Language.Country: us, R:0, D:3
    R = 2 (we are repeating 'Name.Language' of level 2)
    Name.Language.Code: en, R:2, D:2
    Name.Language.Country: NULL, R:2, D:2 (no value defined so D < 3)
    Name.Url: http://A, R:0, D:2
    R = 1 (we are repeating 'Name' of level 1)
    Name.Language.Code: NULL, R:1, D:1 (Only Name is defined so D = 1)
    Name.Language.Country: NULL, R:1, D:1
    Name.Url: http://B, R:1, D:2
    R = 1 (we are repeating 'Name' again of level 1)
    Name.Language.Code: en-gb, R:1, D:2
    Name.Language.Country: gb, R:1, D:3
    Name.Url: NULL, R:1, D:1

Reference

  1. https://parquet.apache.org/docs/file-format/
  2. https://paper-notes.zhjwpku.com/datalayout/dremel.html
  3. https://github.com/julienledem/redelm/wiki/The-striping-and-assembly-algorithms-from-the-Dremel-paper