kudu之CFile设计原理

不念不忘少年蓝@ 2022-01-23 09:51 290阅读 0赞

本文翻译自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 Index。

# 文件格式 #

CFile的 header, blocks, and footer是连续写入文件不带填充的。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxcXEwMTk5MTgx_size_16_color_FFFFFF_t_70]

## 版本 ##

CFile的header 和 footer 每个都包含一个“magic”，它表示CFile的版本。  
![在这里插入图片描述][20190603150641853.png]

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

## Data Block Layout ##

![在这里插入图片描述][20190603151059103.png]  
如果CFile配置为使用压缩，则在附加checksum之前压缩编码数据。

## Nullable Data Block Layout ##

被标记为可为空的列将存储在Nullable Data Block中，该块包括跟踪哪些行为空和不为空的位图。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxcXEwMTk5MTgx_size_16_color_FFFFFF_t_70 1]  
如果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（可变宽度）列的普通编码布局如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxcXEwMTk5MTgx_size_16_color_FFFFFF_t_70 2]

## 字典编码 ##

字典编码可用于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的头开始：  
![在这里插入图片描述][20190603161041822.png]  
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> <block offset> <block size>
    <key> <block offset> <block size>
    ...
       key: vint64 for positional, otherwise varint-length-prefixed string
       offset: vint64
       block size: vint32
    
    <offset to first key>   (fixed32)
    <offset to second key>  (fixed32)
    ...
       These offsets are relative to the start of the block.
    
    <trailer>
       A IndexBlockTrailerPB protobuf
    <trailer length>

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

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

# DeltaFile #

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

# BloomFile #

BloomFile是CFile的包装器，它存储了bloomfilter数据结构。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxcXEwMTk5MTgx_size_16_color_FFFFFF_t_70]: /images/20220123/908973d796aa419bba5c5fc290c5dbfd.png
[20190603150641853.png]: /images/20220123/4ce41196acc04295acadab6df2206795.png
[20190603151059103.png]: /images/20220123/6c2c3065f50e465893f22547ff0d53ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxcXEwMTk5MTgx_size_16_color_FFFFFF_t_70 1]: /images/20220123/cbd80604c4e74150bd188f62822d23b8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxcXEwMTk5MTgx_size_16_color_FFFFFF_t_70 2]: /images/20220123/e5b84c2f6bdd4329a3f4a2cae0179450.png
[20190603161041822.png]: /images/20220123/5174ed041afe454ba3bac6d6a6569550.png