kudu之CFile设计原理

阅读量：3685 次

发布时间：2019-05-21

本文共 3599 字，大约阅读时间需要 11 分钟。

本文翻译自https://github.com/apache/kudu/blob/master/docs/design-docs/cfile.md

CFile

CFile是一种磁盘上的列式存储格式，用于保存数据和相关的B-Tree索引。在DiskRowSet中，每个列和DeltaFile将映射到单个CFile上。此外，DiskRowSet的bloomfilter将存储在一个CFile中，如果表具有复合主键，则关联的ad-hoc索引将存储在单独的CFile中。

尽管名称如此，但CFile并不一定与文件系统中的文件一一对应。CFiles到文件系统的映射由BlockManager决定。一个CFile会被写入单个BlockManager块中（不要与CFile内部的CFile blocks混淆，在本文档的其余部分会进行讨论）。

CFile由header，可变数量的block和footer组成。这里有几种不同类型的块，每种块具有不同的格式：数据块，可空数据块，索引块和字典块。

数据块由一系列连续值组成。为每个值分配一个序数索引或偏移量，它在CFile中是唯一的。因此，可以通过块所包含的序数索引的范围在CFile内识别块; 例如，CFile的前三个块可能具有序号索引范围 [0, 55]，[56, 132]和[133, 511]。

为了支持对CFile内的任意有序索引的高效搜索，CFile中包含一个positional index，它维护了起始有序索引到数据块的映射。有关详细信息，请参阅CFile索引。

对于哪些存储排序数据的CFile（例如，存储主键列的CFile），可以创建值索引。值索引支持有效地在CFile中寻找任意值。有关详细信息，请参阅。

文件格式

CFile的 header, blocks, and footer是连续写入文件不带填充的。

版本

CFile的header 和 footer 每个都包含一个“magic”，它表示CFile的版本。

为了对CFile格式进行重大改变，在Kudu 1.3中引入了CFile v2。

Data Block Layout

在这里插入图片描述

如果CFile配置为使用压缩，则在附加checksum之前压缩编码数据。

Nullable Data Block Layout

被标记为可为空的列将存储在Nullable Data Block中，该块包括跟踪哪些行为空和不为空的位图。

如果CFile配置为使用压缩，则在附加checksum之前压缩value count, bitmap length, null bitmap, and encoded data等数据。

Checksums

Checksums的写和校验是可选的。

当在CFile中写入header，data和footer的Checksums时，CFileFooterPB消息中的incompatible_features将被利用起来。用来让reader知道是否存在校验和。

在读取CFile时，应首先读取footer以查找文件是否包含校验和。如果incompatible_featuresbitset表示存在校验和，则reader可以进行校验。

数据编码

块数据在存储之前被编码。如果启用了压缩，则首先对块进行编码，然后进行压缩。

数据块的大小由–cfile-default-block-size指定，当数据量到达这个大小时，会向CFile添加新块。

普通编码

最简单的编码类型是普通编码，它以自然表示形式存储值。

固定宽度（整数）类型的普通编码由little-endian值组成，后跟包含两个little-endian uint32s：值的个数和块的位置。

BINARY或STRING（可变宽度）列的普通编码布局如下：

字典编码

字典编码可用于BINARY或STRING列。CFile中的所有字典编码块共享相同的字典。如果字典变满，CFile中的后续块将切换为普通编码。字典被存储为普通编码的二进制块，并且数据码字被存储为比特编码的 uint32 s。

前缀编码

目前用于BINARY和STRING数据块。它是基于LevelDB对其数据块使用的编码。

Run-length Encoding

整数和布尔类型可以是run-length encoded的，其具有简单的布局：数值个数，块的位置，run-length encoded数据。如果数据不能够做Run-length编码，编码器将自动回退到bit-packed (literal)编码。

Bitshuffle Encoding

整数类型可以是Bitshuffle 编码的。Bitshuffle编码的块自动进行LZ4压缩，因此不建议进行额外的压缩。

Group Varint Frame-of-Reference Encoding

用于内部的UINT32块。Kudu不支持无符号整数列，因此此编码不用于列数据。

从四个group-varint编码uint32的头开始：

The ordinal position是文件中第一个项目的有序位置。例如，文件中的第一个数据块具有有序位置0.如果该块具有400个值，则第二个数据块将具有有序位置400。

其次是实际数据，每组4个整数使用group-varint。最后一组用0填充。每个整数都相对于标头中的min元素。

CFile Index

CFile可以选择包括位置索引和值索引。位置索引用于满足如下查询，例如：“寻找包含此CFile中第N个数据的数据块”。值索引用于满足如下查询，例如：“寻找CFile中包含123的数据块”。值索引仅存在于包含排序存储列数据的CFile中（例如主键列）。

位置索引和值索引以索引块的B-tree形式存在。数据块写入的时候，实体内容会追加到B tree叶子节点的索引块中。当索引块被写满时，他会被添加到上一层的索引块中，然后开始写入新的叶子节点索引块。如果中间索引块填充，它将启动一个新的中间块并溢出到更高层的内部块。

举例如下：

[Int 0]           -----------------------------           |                           |        [Int 1]                     [Int 2]   -----------------             --------------   |       |       |             |            |[Leaf 0]  ...   [Leaf N]     [Leaf N+1]   [Leaf N+2]

在这个例子中，数据写入了N个叶子索引块，写满了标记为Int 1的内部节点。此时，编写器将创建Int 0内部节点，它的一个指针指向Int 1.其余的叶子索引块（N + 1和N + 2）将被写入新的内部节点（Int 2）。写完后int2节点也会添加到int0中。

请注意，此策略不会产生完全平衡的B树，而是在每个级别的所有节点上产生100％的“填充因子”，除了写入的最后一个节点。

对于两种类型的索引，索引块的编码类似：


    
     
     
       
        
        
         ... key: vint64 for positional, otherwise varint-length-prefixed string offset: vint64 block size: vint32
         
           (fixed32)
          
            (fixed32)... These offsets are relative to the start of the block.
           
             A IndexBlockTrailerPB protobuf

使用后序遍历来写入索引块，并且索引块可以与数据块交叉。

trailer 中的内容指定该块是叶子节点还是内部节点，从而得知该节点的指针是指向另一个索引块还是指向数据块。

DeltaFile

DiskRowSet中的每个DeltaFile都写入CFile; 实际上，DeltaFile只是CFile的一个包装器，专门用于REDO和UNDO delta数据。与行更新相关联的增量被分组到RowChangeList中，并作为二进制值写入底层CFile。每个值都以DeltaKey为前缀，DeltaKey由行索引（在DiskRowSet中）和时间戳组成。CFile包括值索引，以便可以有效地定位属于特定行的增量。