翻译部分来自github地址 https://github.com/cloudera/kudu/blob/master/docs/design-docs/cfile.md，加上个人的理解。

介绍

Cfile是磁盘上的列式存储文件格式，包含了数据部分以及对应的b-tree索引。在Kudu的一个DiskRowSet中，每一个列和其对应的多个Deltafile映射成一个单独的cfile。这里理解下，一个tablet有一个memrowset和若干个diskrowset，每个diskrowset中所有列的data数据和若干个deltafile构成一个cfile，逻辑图如下所示。

cfile1.jpg

最终可以理解为一个diskrowset就是一个cfile（一个列的情况，多个列，就是多个cfile），diskrowset是概念上的名词，cfile则是物理上的文件格式。

cfile除了包含数据，deltafile，还有bloomfilter，如果有 compound primary key，则还包含了ad-hoc index。

Cfile的格式

cfile包含了一个header，若干个block，一个footer（上图中的data部分，还可以细分），block包含了多个类型，每个类型的格式也不同， 涉及：data block，nullable data block，index block，dictionary block，在一个cfile中，每个类型的block都有一个或者多个存在。

其中Data部分起始部分是为空值，仅仅针对为null的column，对应主键没有这个的null值的，bitmap就是以那些值为null的RowId建立起来的位图，这样Data就不用存储这些空值，data部分不同的column类型文件会有不同的编码方式

其中，所有data block共享一个连续值的序列，这个序列的每一个值，都是唯一的，代表了数据的ordinal索引（ordinal index)。因此，cfile中的一个block可以通过索引的范围来定位和识别，比如，某个cfile的前三个block对应的索引范围可能是[0,55],[56,132],[133,511]。从这些范围可以看到，每个block的索引范围的跨度可能不同，那是因为每次flush的数据包含了多个列，而每个列flush的时候数据大小是不同的。

为了能够高效的随机查找ordinal index，需要一个a positional index也可能包含在cfile中，这个postitional index包含了每个block的ordinal index范围的起始index。

如果data block中存储的是一个有序的数据，比如，primary column对应的数据，则会在cfile中生成一个value index，能够高效的随机查看这个block中的数据。

Header Layout

field	width (bytes)	notes
magic	8	see below
length	4	32-bit unsigned length of the following Protobuf message
message	variable	encoded CFileHeaderPB Protobuf message
checksum	4	optional CRC-32 checksum of magic, length, and message

Footer Layout

field	width (bytes)	notes
checksum	4	optional CRC-32 checksum of message, magic, and length
magic	8	see below
message	variable	encoded CFileFooterPB Protobuf message
length	4	unsigned 32-bit length of the preceding Protobuf message

header和footer的magic指明了cfile的version。

Data Block Layout

field	width (bytes)	notes
data	variable	encoded data values
checksum	4	optional CRC-32 checksum of the data

如果cfile配置为压缩，那么，data先进行压缩后，再加上压缩后checksum。

Nullable Data Block Layout

field	width (bytes)	notes
value count	variable	LEB128 encoded count of values
bitmap length	variable	LEB128 encoded length of the following null bitmap
null bitmap	variable	RLE encoded bitmap
data	variable	encoded non-null data values
checksum	4	optional CRC-32 checksum of the value count, bitmap length, null bitmap, and data

如果列被配置为可空的，则被存储为nullable block，这个类型的块包含了bitmap来追踪哪些row是空的，哪些row是非空的。如果配置为压缩格式，则value count，bitmap，null bitmap，编码的data压缩之后，再加上压缩后的checksum。

Data Encodings

data block经过编码后再进行存储，如果开启了压缩，则先编码后压缩。因为多个列存在在一个cfile中（大小达到预先设置的阈值后flush到磁盘生成一个cfile），每个列占用的大小不同，即占用不同数量的data block，每个data block都是单独编码，单独压缩，即使他们可能是同一个列，比如，row1占用了5个data block，row2占用了2个datablock，等等，但是无论如何，他们共享一个统计的ordinal index之所以没有一个列占用一个边长的datablock，个人觉得考虑到检索的性能，块的大小以及编码难度等问题，固定长度的datablock反而更容易。

Plain Encoding

最简单的编码方式，Plain encoding for BINARY or STRING (variable-width) columns 适用列 is laid out as follows:

ordinal position	little-endian uint32
num values	little-endian uint32
offsets position	little-endian uint32
values	sequential values with no padding
offsets	group-varint frame-of-reference encoded value offsets

Dictionary Encoding

Prefix Encoding

Run-length Encoding

Bitshuffle Encoding

Group Varint Frame-of-Reference Encoding

汇总，

eee.png

对于ad_hoc文件使用的prefix，delta fle使用的是plain，bloomfile使用的是plain

Cfile Index

cfile包含了positional（ordinal） index和data index。其中，positional index作用在于seek to the data block containing the Nth entry in this CFile，根据rowId找到Data中的偏移；而data index作用在于seek to the data block containing '123' in this CFile，根据key的值找到data中的偏移。value index只能适用于cfile中的数据是有序的，比如primary key column，而且value index针对只有一个column为key的情况下，这个时候DiskRowSet是没有ad_hoc索引的，使用value index来代替。

ordinal和data index都存储为b-tree在cfile的index block中。data block的起始index会被追加到leaf index block作为叶子节点，当一个leaf index block写满之后，这个block他被add到另高层的tree node节点下面 （如下图的int 1 下面，leaf0--leafn沾满了一个index block），并且开辟新的leaf index block等待后续的index数据写入（leaf n+1...)，当写满一个leaf index block时候，就用一个label来标记这个块（int 1 int2...）这些label也构成一个树形，看起来是b+树，怎么说成是b-树？？？。

if the intermediate index block fills, it will start a new intermediate block and spill into an even higher-layer internal block.这里看起来更像是b-树的描述，

index block的索引结构.jpg

In this case, we wrote N leaf blocks, which filled up the internal node labeled Int 1. At this point, the writer would create Int 0 with one entry pointing to Int 1. Further leaf blocks (N+1 and N+2) would be written to a new internal node (Int 2). When the file is completed, Int 2 will spill, adding its entry into Int 0 as well. 当写入了n个leaf 节点数据后，block满了，此时，使用int1来标记他们；后续的数据要写入到新的index block中，并且使用int 2来标记，而int 1和int 2需要用int 0 来标记。这种算法会并非生成平衡的b-tree。

两个索引的index block编码相同，如下，

11.jpg

上述树形结构会通过后序遍历的方式写入到index block中（后序遍历方式写入文件，先根遍历方式读取到内存中生成树），如上图的编码，在文件的最后会通过trailer表明了一个b-tree的leaf node或者inner node是一个index block还是data block。

问题，个人理解

data block是按照多列放在一起，统计使用一个序列的ordinal index指明，那么如何区分不同的列呢？以及一行对应每列的数据如何查找？

1. 如何区分不同的列？
2. 一行数据如何查找？

第一个问题，每列占用不同数量的data block，可以使用下标范围表明，比如row1[0,100]，row2[101,150]，虽然跨了多个data block，但是可以统一到一起表示。这样就可以通过下表范围来表明不同的列。

第二个问题，找到一行数据，需要根据业务的sql语句，分成包含主键和不包含主键的检索，首先讨论

• 不包含主键，可以通过boom过滤器来做，每列有个bloom过滤器，来判断是否包含where的条件，每列值怎么取？通过第一个问题的解决方案定位列数据。
• 包含主键，单一列为主键，和复合主键，无论哪种，要么是value index，要么是ad hoc index，不管怎样，这两个index的作用是什么？如上述描述，'根据key的值找到data中的偏移',也就是根据业务的id来查看对应的数据的rowid也就是ordinal index的位置，业务的id是逻辑上的数据，value index和ad hoc index里面应该包含业务id和全局ordinal index的映射关系！，但是，ordinal index是多个列共享的，明显比逻辑id多，怎么搞？个人感觉可以把主键列（即便是复合主键）当在data blocks的第一个位置，之后的列按照固定属性往后排即可，这样逻辑id和第一位置的主键列的部分ordinal index就能够映射上，即，把全局ordinal index中的主键部分的index部分和对应的业务id，做成value inex或者ad hoc index。组后结合每个列不同的下表范围很容易组合成数据。如下，会举例子

row1 [0,100] key datasize=1
row2 [101,302] datasize=2
row3 [303,605] datasize=3
因为data block都是非空的数据，因此每列都是101行，但是数据大小不同。
通过ad hoc index或者value index，结合用户输入的id，得出row1的49 offset，那么row2是多少呢？101+492=199， row3 303+493=450，那么49,199,405这三个offset对应的到底是什么数据呢？使用positional index即可~（加快检索，不能直接从上三个数直接找，因为不知道在哪个data block中，从positional index可以很快定位到具体哪个data block）过程，如下图所示

search in cfile/cfile data部分细致化.jpg

DeltaFile

每一个deltafile都会被写入cfile中，实际上，cfile仅仅是cfile的简单包装而已，deltafile中包含了若干个redo和undo delta data。这些deltas关联了一个row的更新并且组织成Rowchangelist，写入到cfile中的二进制值，其中，每一个值叫做DeltaKey，包含了ordinal row index和timestamp。cfile通过value index会加速delta的值对应的的具体row数据。

BloomFile

BloomFile is a wrapper around CFile which stores a bloomfilter datastructure.