翻譯部分來(lái)自github地址 https://github.com/cloudera/kudu/blob/master/docs/design-docs/cfile.md，加上個(gè)人的理解。

介紹

Cfile是磁盤上的列式存儲(chǔ)文件格式，包含了數(shù)據(jù)部分以及對(duì)應(yīng)的b-tree索引。在Kudu的一個(gè)DiskRowSet中，每一個(gè)列和其對(duì)應(yīng)的多個(gè)Deltafile映射成一個(gè)單獨(dú)的cfile。這里理解下，一個(gè)tablet有一個(gè)memrowset和若干個(gè)diskrowset，每個(gè)diskrowset中所有列的data數(shù)據(jù)和若干個(gè)deltafile構(gòu)成一個(gè)cfile，邏輯圖如下所示。

cfile1.jpg

最終可以理解為一個(gè)diskrowset就是一個(gè)cfile（一個(gè)列的情況，多個(gè)列，就是多個(gè)cfile），diskrowset是概念上的名詞，cfile則是物理上的文件格式。

cfile除了包含數(shù)據(jù)，deltafile，還有bloomfilter，如果有 compound primary key，則還包含了ad-hoc index。

Cfile的格式

cfile包含了一個(gè)header，若干個(gè)block，一個(gè)footer（上圖中的data部分，還可以細(xì)分），block包含了多個(gè)類型，每個(gè)類型的格式也不同， 涉及：data block，nullable data block，index block，dictionary block，在一個(gè)cfile中，每個(gè)類型的block都有一個(gè)或者多個(gè)存在。

其中Data部分起始部分是為空值，僅僅針對(duì)為null的column，對(duì)應(yīng)主鍵沒(méi)有這個(gè)的null值的，bitmap就是以那些值為null的RowId建立起來(lái)的位圖，這樣Data就不用存儲(chǔ)這些空值，data部分不同的column類型文件會(huì)有不同的編碼方式

其中，所有data block共享一個(gè)連續(xù)值的序列，這個(gè)序列的每一個(gè)值，都是唯一的，代表了數(shù)據(jù)的ordinal索引（ordinal index)。因此，cfile中的一個(gè)block可以通過(guò)索引的范圍來(lái)定位和識(shí)別，比如，某個(gè)cfile的前三個(gè)block對(duì)應(yīng)的索引范圍可能是[0,55],[56,132],[133,511]。從這些范圍可以看到，每個(gè)block的索引范圍的跨度可能不同，那是因?yàn)槊看蝔lush的數(shù)據(jù)包含了多個(gè)列，而每個(gè)列flush的時(shí)候數(shù)據(jù)大小是不同的。

為了能夠高效的隨機(jī)查找ordinal index，需要一個(gè)a positional index也可能包含在cfile中，這個(gè)postitional index包含了每個(gè)block的ordinal index范圍的起始index。

如果data block中存儲(chǔ)的是一個(gè)有序的數(shù)據(jù)，比如，primary column對(duì)應(yīng)的數(shù)據(jù)，則會(huì)在cfile中生成一個(gè)value index，能夠高效的隨機(jī)查看這個(gè)block中的數(shù)據(jù)。

Header Layout

Footer Layout

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

Data Block Layout

如果cfile配置為壓縮，那么，data先進(jìn)行壓縮后，再加上壓縮后checksum。

Nullable Data Block Layout

如果列被配置為可空的，則被存儲(chǔ)為nullable block，這個(gè)類型的塊包含了bitmap來(lái)追蹤哪些row是空的，哪些row是非空的。如果配置為壓縮格式，則value count，bitmap，null bitmap，編碼的data壓縮之后，再加上壓縮后的checksum。

Data Encodings

data block經(jīng)過(guò)編碼后再進(jìn)行存儲(chǔ)，如果開(kāi)啟了壓縮，則先編碼后壓縮。因?yàn)槎鄠€(gè)列存在在一個(gè)cfile中（大小達(dá)到預(yù)先設(shè)置的閾值后flush到磁盤生成一個(gè)cfile），每個(gè)列占用的大小不同，即占用不同數(shù)量的data block，每個(gè)data block都是單獨(dú)編碼，單獨(dú)壓縮，即使他們可能是同一個(gè)列，比如，row1占用了5個(gè)data block，row2占用了2個(gè)datablock，等等，但是無(wú)論如何，他們共享一個(gè)統(tǒng)計(jì)的ordinal index之所以沒(méi)有一個(gè)列占用一個(gè)邊長(zhǎng)的datablock，個(gè)人覺(jué)得考慮到檢索的性能，塊的大小以及編碼難度等問(wèn)題，固定長(zhǎng)度的datablock反而更容易。

Plain Encoding

最簡(jiǎn)單的編碼方式，Plain encoding for BINARY or STRING (variable-width) columns 適用列 is laid out as follows:

Dictionary Encoding

Prefix Encoding

Run-length Encoding

Bitshuffle Encoding

Group Varint Frame-of-Reference Encoding

匯總，

eee.png

對(duì)于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，根據(jù)rowId找到Data中的偏移；而data index作用在于seek to the data block containing '123' in this CFile，根據(jù)key的值找到data中的偏移。value index只能適用于cfile中的數(shù)據(jù)是有序的，比如primary key column，而且value index針對(duì)只有一個(gè)column為key的情況下，這個(gè)時(shí)候DiskRowSet是沒(méi)有ad_hoc索引的，使用value index來(lái)代替。

ordinal和data index都存儲(chǔ)為b-tree在cfile的index block中。data block的起始index會(huì)被追加到leaf index block作為葉子節(jié)點(diǎn)，當(dāng)一個(gè)leaf index block寫滿之后，這個(gè)block他被add到另高層的tree node節(jié)點(diǎn)下面 （如下圖的int 1 下面，leaf0--leafn沾滿了一個(gè)index block），并且開(kāi)辟新的leaf index block等待后續(xù)的index數(shù)據(jù)寫入（leaf n+1...)，當(dāng)寫滿一個(gè)leaf index block時(shí)候，就用一個(gè)label來(lái)標(biāo)記這個(gè)塊（int 1 int2...）這些label也構(gòu)成一個(gè)樹(shù)形，看起來(lái)是b+樹(shù)，怎么說(shuō)成是b-樹(shù)？？？。

if the intermediate index block fills, it will start a new intermediate block and spill into an even higher-layer internal block.這里看起來(lái)更像是b-樹(shù)的描述，

index block的索引結(jié)構(gòu).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. 當(dāng)寫入了n個(gè)leaf 節(jié)點(diǎn)數(shù)據(jù)后，block滿了，此時(shí)，使用int1來(lái)標(biāo)記他們；后續(xù)的數(shù)據(jù)要寫入到新的index block中，并且使用int 2來(lái)標(biāo)記，而int 1和int 2需要用int 0 來(lái)標(biāo)記。這種算法會(huì)并非生成平衡的b-tree。

兩個(gè)索引的index block編碼相同，如下，

11.jpg

上述樹(shù)形結(jié)構(gòu)會(huì)通過(guò)后序遍歷的方式寫入到index block中（后序遍歷方式寫入文件，先根遍歷方式讀取到內(nèi)存中生成樹(shù)），如上圖的編碼，在文件的最后會(huì)通過(guò)trailer表明了一個(gè)b-tree的leaf node或者inner node是一個(gè)index block還是data block。

問(wèn)題，個(gè)人理解

data block是按照多列放在一起，統(tǒng)計(jì)使用一個(gè)序列的ordinal index指明，那么如何區(qū)分不同的列呢？以及一行對(duì)應(yīng)每列的數(shù)據(jù)如何查找？

1. 如何區(qū)分不同的列？
2. 一行數(shù)據(jù)如何查找？

第一個(gè)問(wèn)題，每列占用不同數(shù)量的data block，可以使用下標(biāo)范圍表明，比如row1[0,100]，row2[101,150]，雖然跨了多個(gè)data block，但是可以統(tǒng)一到一起表示。這樣就可以通過(guò)下表范圍來(lái)表明不同的列。

第二個(gè)問(wèn)題，找到一行數(shù)據(jù)，需要根據(jù)業(yè)務(wù)的sql語(yǔ)句，分成包含主鍵和不包含主鍵的檢索，首先討論

• 不包含主鍵，可以通過(guò)boom過(guò)濾器來(lái)做，每列有個(gè)bloom過(guò)濾器，來(lái)判斷是否包含where的條件，每列值怎么??？通過(guò)第一個(gè)問(wèn)題的解決方案定位列數(shù)據(jù)。
• 包含主鍵，單一列為主鍵，和復(fù)合主鍵，無(wú)論哪種，要么是value index，要么是ad hoc index，不管怎樣，這兩個(gè)index的作用是什么？如上述描述，'根據(jù)key的值找到data中的偏移',也就是根據(jù)業(yè)務(wù)的id來(lái)查看對(duì)應(yīng)的數(shù)據(jù)的rowid也就是ordinal index的位置，業(yè)務(wù)的id是邏輯上的數(shù)據(jù)，value index和ad hoc index里面應(yīng)該包含業(yè)務(wù)id和全局ordinal index的映射關(guān)系！，但是，ordinal index是多個(gè)列共享的，明顯比邏輯id多，怎么搞？個(gè)人感覺(jué)可以把主鍵列（即便是復(fù)合主鍵）當(dāng)在data blocks的第一個(gè)位置，之后的列按照固定屬性往后排即可，這樣邏輯id和第一位置的主鍵列的部分ordinal index就能夠映射上，即，把全局ordinal index中的主鍵部分的index部分和對(duì)應(yīng)的業(yè)務(wù)id，做成value inex或者ad hoc index。組后結(jié)合每個(gè)列不同的下表范圍很容易組合成數(shù)據(jù)。如下，會(huì)舉例子

row1 [0,100] key datasize=1
row2 [101,302] datasize=2
row3 [303,605] datasize=3
因?yàn)閐ata block都是非空的數(shù)據(jù)，因此每列都是101行，但是數(shù)據(jù)大小不同。
通過(guò)ad hoc index或者value index，結(jié)合用戶輸入的id，得出row1的49 offset，那么row2是多少呢？101+492=199， row3 303+493=450，那么49,199,405這三個(gè)offset對(duì)應(yīng)的到底是什么數(shù)據(jù)呢？使用positional index即可~（加快檢索，不能直接從上三個(gè)數(shù)直接找，因?yàn)椴恢涝谀膫€(gè)data block中，從positional index可以很快定位到具體哪個(gè)data block）過(guò)程，如下圖所示

search in cfile/cfile data部分細(xì)致化.jpg

DeltaFile

每一個(gè)deltafile都會(huì)被寫入cfile中，實(shí)際上，cfile僅僅是cfile的簡(jiǎn)單包裝而已，deltafile中包含了若干個(gè)redo和undo delta data。這些deltas關(guān)聯(lián)了一個(gè)row的更新并且組織成Rowchangelist，寫入到cfile中的二進(jìn)制值，其中，每一個(gè)值叫做DeltaKey，包含了ordinal row index和timestamp。cfile通過(guò)value index會(huì)加速delta的值對(duì)應(yīng)的的具體row數(shù)據(jù)。

BloomFile

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