kudu 存储引擎简析
本文由??網(wǎng)易云?發(fā)布。
?
1?概述
本文主要介紹kudu底層存儲(chǔ)引擎的數(shù)據(jù)組織方式，先看整體結(jié)構(gòu)如下：
一張表會(huì)分成若干個(gè)tablet ， 每個(gè)tablet 包括MetaData 元信息及若干個(gè)RowSet ， RowSet 包含一個(gè)MemRowSet 及若干個(gè)DiskRowSet ， DiskRowSet 中 包 含 一 個(gè) BloomFile 、 Ad_hoc Index 、 BaseData 、 DeltaMem 及 若 干 個(gè) RedoFile 和UndoFile（UndoFile一般情況下只有一個(gè)）。
?
MemRowSet用于新數(shù)據(jù)insert及已在MemRowSet中的數(shù)據(jù)的更新，一個(gè)MemRowSet寫滿后會(huì)將數(shù)據(jù)刷到磁盤形成若干個(gè)DiskRowSet。
DiskRowSet用于老數(shù)據(jù)的mutation，后臺(tái)定期對(duì)DiskRowSet做compaction，以刪除沒用的數(shù)據(jù)及合并歷史數(shù)據(jù)，減少查詢過(guò)程中的IO開銷。
BloomFile根據(jù)一個(gè)DiskRowSet中的key生成一個(gè)bloom filter，用于快速模糊定位某個(gè)key是否在DiskRowSet中存在。Ad_hoc Index是主鍵的索引，用于定位key在DiskRowSet中的具體哪個(gè)偏移位置。
BaseData 是 MemRowSet flush 下 來(lái) 的 數(shù) 據(jù) ， 按 列 存 儲(chǔ) ， 按 主 鍵 有 序 。UndoFile是基于BaseData之前時(shí)間的歷史數(shù)據(jù)，通過(guò)在BaseData上apply UndoFile中的記錄，可以獲得歷史數(shù)據(jù)。RedoFile是基于BaseData之后時(shí)間的mutation記錄，通過(guò)在BaseData上apply RedoFile中的記錄，可獲得較新的數(shù)據(jù)。DeltaMem用于DiskRowSet中數(shù)據(jù)的mutation，先寫到內(nèi)存中，寫滿后flush到磁盤形成RedoFile。
?
2?MemRowSet
MemRowSet的數(shù)據(jù)組織形式是一顆B+Tree，結(jié)構(gòu)如下：
這顆B+樹實(shí)現(xiàn)的比較簡(jiǎn)單，因?yàn)樗鼪]有update跟delete操作，kudu在MemRowSet中中數(shù)據(jù)的mutation采用類似append log 方式，在base數(shù)據(jù)上有個(gè)mutation指針，所有的后續(xù)mutation操作都掛在這個(gè)指針上了。
雖然只有插入，但是也會(huì)出現(xiàn)節(jié)點(diǎn)滿時(shí)需要做split，同時(shí)可能有讀操作也在同步進(jìn)行，kudu使用AtomicVersion（原子變量+位移）實(shí)現(xiàn)了一個(gè)鎖。樹的度跟cpu的CACHELINE_SIZE有關(guān)，是為了讓一個(gè)節(jié)點(diǎn)僅讀取一次cpu cache。
樹的檢索是先找到key所在的LeafNode，然后在LeafNode內(nèi)部進(jìn)行二分查找，LeafNode間有指針進(jìn)行串聯(lián)，為了方便scan，掃整個(gè)MemRowSet一般通過(guò)一個(gè)空串的key找到第一個(gè)LeafNode，然后依次讀數(shù)據(jù)。
?
3?DiskRowSet
這部分是kudu存儲(chǔ)部分最復(fù)雜的東西，分為兩個(gè)部分來(lái)講，DiskRowSet間的組織，DiskRowSet內(nèi)數(shù)據(jù)組織，先看DiskRowSet 間怎么組織的。
?
3.1?DiskRowSet間組織
一個(gè)tablet隨這數(shù)據(jù)的不斷寫入會(huì)包含很多個(gè)DiskRowSet，每個(gè)DiskRowSet上有min_key、max_key標(biāo)明key的范圍，如果要查找一個(gè)key在哪個(gè)DiskRowSet上依次遍歷每個(gè)DiskRowSet效率是很低的，這種情況線段樹這種數(shù)據(jù)結(jié)構(gòu)是很適合做range索引的，將所有的DiskRowSet形成一顆線段樹，結(jié)構(gòu)如下：
?
其實(shí)就是一個(gè)二叉平衡樹，每次從所有range（最小的min_key跟最大的max_key）的中間key做split，將range跨域左右子樹的
DiskRowSet（即split point落在DiskRowSet的min_key與max_key之間）放到overlap rowsets中去。這顆樹實(shí)現(xiàn)的也很簡(jiǎn)單， 因?yàn)樗蛔霾樵冇?#xff0c;生成后就不會(huì)變動(dòng)，若遇到MemRowSet flush或DiskRowSet Merge Compaction就直接重新生成一顆新樹。
這個(gè)樹主要用于在讀或?qū)懙臅r(shí)候定位某個(gè)或若干個(gè)key 在哪些DiskRowSet 的range 范圍內(nèi)， 只能通過(guò)DiskRowSet 的min_key/max_key做一層模糊過(guò)濾，是否正在存在需要做進(jìn)一步檢查。
?
3.2?DiskRowSet內(nèi)數(shù)據(jù)組織
一個(gè)DiskRowSet大體數(shù)據(jù)組織上面概述中已介紹過(guò)，其中DeltaMem跟MemRowSet在內(nèi)存中的組織方式是一樣的，都是B+Tree，而在磁盤上的存儲(chǔ)都是放在CFile中的，下面我們看看CFile的文件格式：
?
?
CFile包含Header、Data、Index、Footer幾塊，其中Data部分起始部分是為空值的條目建立的bitmap，僅針對(duì)可為null的
column，對(duì)于主鍵是沒有這個(gè)的，bitmap就是以那些值為null的RowId建立起來(lái)的位圖，這樣Data中就不用存這些空值。data部分不同的column類型文件會(huì)有不同的編碼方式：
?
對(duì)于ad_hoc文件使用的是prefix，delta file使用的是plain，bloomfile使用的是plain。每種BlockBuilder在處理一定量數(shù)據(jù)后就會(huì)append到Data中。
Index有兩種，posidx_index是根據(jù)RowId找到在Data中的偏移，validx index是根據(jù)key的值找到在Data中的偏移，validx只針對(duì)只有一個(gè)column為key的情況，這個(gè)時(shí)候DiskRowSet沒有Ad_hoc索引，使用validex來(lái)代替。這兩個(gè)index內(nèi)部實(shí)現(xiàn)是一個(gè)B- Tree，index不一定是連續(xù)的，在達(dá)到一定長(zhǎng)度后就會(huì)刷盤，而內(nèi)部可以區(qū)分是中間節(jié)點(diǎn)還是葉子節(jié)點(diǎn)及其孩子節(jié)點(diǎn)的位置。
Footer是記錄了CFile的元信息，包括posidx_index、validx_index兩棵樹根節(jié)點(diǎn)所在位置，數(shù)據(jù)條目、編碼、壓縮方式等。下面看看DiskRowSet數(shù)據(jù)在磁盤上的分布：
?
在磁盤上每個(gè)DiskRowSet有若干個(gè)***.metadata及***.data文件，metadata文件記錄的是DiskRowSet的元信息，主要包括哪些block及block在data中的位置，上圖為block與DiskRowSet中各部分的映射關(guān)系，在寫磁盤是通過(guò)container來(lái)寫，每個(gè)container 可以寫很大一塊連續(xù)的磁盤空間， 用于給某個(gè)CFile寫數(shù)據(jù)， 當(dāng)一個(gè)CFile寫完后會(huì)將container歸還給BlockManager， 這時(shí)container就可以用于下個(gè)CFile寫數(shù)據(jù)了，當(dāng)BlockManager中沒有container可用時(shí)會(huì)新建一個(gè)container給新來(lái)的CFile使用。
?
對(duì)于新建block先看看有無(wú)container可用，若沒有目前默認(rèn)是在所有配置中的data_dir中隨機(jī)選取一個(gè)dir中建一個(gè)新的metadata 及data文件。先寫data，block落盤后再寫metadata。
?
對(duì)于kudu底層數(shù)據(jù)存儲(chǔ)就介紹到這里，希望對(duì)大家有所幫助。
?
?
想要了解網(wǎng)易大數(shù)據(jù)，請(qǐng)戳這里網(wǎng)易大數(shù)據(jù)|專業(yè)的私有化大數(shù)據(jù)平臺(tái)
?
了解 網(wǎng)易云 ：
網(wǎng)易云官網(wǎng)：https://www.163yun.com/
新用戶大禮包：https://www.163yun.com/gift
網(wǎng)易云社區(qū)：https://sq.163yun.com/
?
總結(jié)
以上是生活随笔為你收集整理的kudu 存储引擎简析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： tornado框架的get方法传递参数
- 下一篇： Spring MVC 中的 contro