作者：李紅建

責編：宇亭

在第一期研發(fā)分享中，我們解釋了，為什么Tinamu作為一款列式存儲引擎在初期不支持 Delete 功能的原因，然后對一些友商列式存儲引擎的 Delete 方案進行了一些調(diào)研和總結(jié)，感興趣的同學可以查看我們上一期的分享：關(guān)于列式數(shù)據(jù)庫實現(xiàn)?Delete 功能的調(diào)研之旅。
本期文章，我將向社區(qū)小伙伴們詳細地介紹一下給 StoneDB 的 Tianmu 存儲引擎添加 Delete 功能的開發(fā)思路，希望對感興趣的同學提供幫助。

Tianmu 引擎的存儲結(jié)構(gòu)

首先我們需要知道 Tianmu 引擎的數(shù)據(jù)是怎么樣存儲的，這樣才知道應該怎么刪除數(shù)據(jù)，所以我們先研究下 Tianmu 引擎的存儲結(jié)構(gòu)。Tianmu 為每個表單獨建立了一個文件夾，以表名+tianmu 命名，每個表的文件夾下面又為各個列分別建立了對應列的文件夾，以列編號為名從 0 開始依次遞增，列文件夾下面存儲元數(shù)據(jù) DN 文件和實際列數(shù)據(jù)的 DATA 文件。

如上圖所示，可以看到每個列文件夾下面有這么幾個文件夾，其中：DATA?文件夾存儲對應列 pack 的文件；DN?文件夾存儲元數(shù)據(jù) DPN 的文件；filters?文件夾下存放著直方圖、映射表、布隆過濾器（Bloom Filter）等中間數(shù)據(jù)的文件；META?文件夾存儲了列的一些固有屬性，如數(shù)據(jù)類型、版本、壓縮類型等；v文件下存儲了列數(shù)據(jù)的版本。

當然，可能一些同學乍一看上面的什么 DN、DPN 都不知道什么意思，其實是因為我們的 Tianmu 引擎使用了非常重要的知識網(wǎng)格（Knowledge Grid）技術(shù)，后面我們有時間會單獨出更詳細的文章來分享知識網(wǎng)格相關(guān)的最新研究。

如上圖所示，DPN（Data Pack Node）?是知識網(wǎng)格的數(shù)據(jù)元信息節(jié)點在代碼中的數(shù)據(jù)結(jié)構(gòu)，數(shù)據(jù)持久化在各個列文件夾下面的 DN 文件中，初始化數(shù)據(jù)元信息節(jié)點時從利用 mmap機制把DN文件映射到內(nèi)存中。pack?是物理的數(shù)據(jù)塊，每個pack存儲著對應列中多個列數(shù)據(jù)，pack 對象跟 DPN 對象?1:1?對應，負責從 各個列文件夾下面的 DATA 文件寫入數(shù)據(jù) 和讀取數(shù)據(jù)。pack 中的數(shù)據(jù)經(jīng)過高度壓縮后存儲到 DATA 文件中。

Tianmu 的數(shù)據(jù)都是根據(jù)列按照行數(shù)據(jù)緊密排序進行存儲的，從文件中讀取和寫入的單位是 pack，其中：

行號與 DPN & pack 的關(guān)系：

DPN id 由 row_id 進行位移右移運行得出， pss 的值一般為 16 ，也就是說每 65536 行的數(shù)據(jù)組成一個 pack，數(shù)據(jù)包結(jié)構(gòu)的信息比如行與數(shù)據(jù)包的偏移量 pss, 數(shù)據(jù)化結(jié)構(gòu)體為 COL_META 持久化在 META 文件中。

行號與 pack 中數(shù)據(jù) id 的關(guān)系：

數(shù)據(jù) ID 由 row_id 對 1 左移 pss 為后的值 取余后得出，基本上數(shù)據(jù)ID也都是在 0~65536 之間。

可以看以下這幅圖：

好了，以上就是我們對 Tianmu 引擎存儲結(jié)構(gòu)的一個簡單介紹。

MySQL 的多引擎架構(gòu)和執(zhí)行接口

了解完 Tianmu 的存儲結(jié)構(gòu)后，我們就要去想如何進行刪除的操作了，這個時候就需要用到 MySQL 的多引擎架構(gòu)和執(zhí)行接口了，因為我們要讓用戶使用 MySQL 客戶端來進行 Tianmu 引擎里的刪除操作。下圖是 MySQL 的多引擎架構(gòu)圖：

可以看到，MySQL 架構(gòu)的最大特點之一，就是支持可插拔存儲引擎。再來看一下MySQL 的執(zhí)行接口邏輯圖：

這個部分，網(wǎng)絡上的一些基礎(chǔ)知識分享很多了，大家可以學習了解一下，我們這邊特別要去講解的是代碼部分的邏輯，下面是我在 GDB 中調(diào)試的幾個重要代碼邏輯：

insert 調(diào)用堆棧：

update 調(diào)用堆棧：

delete調(diào)用堆棧：

由調(diào)用堆?？芍?，insert、update和delete的相關(guān)代碼指令都會調(diào)用到Tianmu::dbhandler::TianmuHandler 類中各自功能的函數(shù)，而 TianmuHandler 繼承自 handler，MySQL 以 handler 為基類，各個引擎的 handler 類為子類，利用多態(tài)的原理實現(xiàn)對不同引擎的調(diào)用。

如果要實現(xiàn)Tianmu的單表 delete 功能，就需要在 TianmuHandler :: delete_row() 中進行實現(xiàn)。同時 handler 類還提供了刪除所有行的虛函數(shù) delete_all_rows() 如需支持刪除所有行的數(shù)據(jù)，可在TianmuHandler :: delete_all_rows() 中進行實現(xiàn)。??

Tianmu?引擎刪除數(shù)據(jù)的過程

由此，我們便可以對 Tianmu 的delete功能進行設(shè)計和研發(fā)了。下面是我調(diào)研實現(xiàn) delete 功能的流程圖：

單表 delete all 功能：

目前我們是支持 truncate 功能的，單表 delete all 的功能就直接復用 truncate 的邏輯。

條件 delete 功能：

條件 delete 這里我們采用標記刪除的策略。列式數(shù)據(jù)庫的存儲結(jié)構(gòu)決定了對真實的數(shù)據(jù)進行刪除時必須要對整個表的數(shù)據(jù)進行重新移動整理，因為除了刪除無用的行，還需要合并數(shù)據(jù)塊。這樣的話，在數(shù)據(jù)量非常多的情況下，對真實的數(shù)據(jù)進行刪除將會是非常大的動作，不僅會消耗機器大量的IO資源和CPU資源，同時刪除的速度也會比較慢。這也是目前主流支持列式數(shù)據(jù)庫的廠商都使用標記刪除的原因。

注意看上面的執(zhí)行流程圖，我們會發(fā)現(xiàn)一個很重要的節(jié)點——Deletebitmap（Delete位圖），這個 Delete 位圖是什么呢？這里要重點講解一下。

位圖（bitmap）的實際存儲形式是個 int32 類型的數(shù)組，原理是使用 int32 類型的值占用的 32 位空間使用 0 或 1 存儲并記錄這 32 個值的狀態(tài)。位圖中的比特總數(shù)等于包中的行的總數(shù)。數(shù)據(jù)在 pack 中的位置和位圖中的位置是一一對應的，這樣可以有效地節(jié)省空間。

那么 Delete 位圖應該存放在哪個位置呢？一般有這么四種方案：

方案1.存放在pack里：

優(yōu)點：進行標記刪除的時候同時可對數(shù)據(jù)置空，可有效的釋放字符串類型的空間，同時可優(yōu)化 select ,insert ,update 帶where子句的數(shù)據(jù)過濾場景。不需要修改上層邏輯。整體邏輯簡單。修改面主要集中在pack層。

缺點：每次刪除都需要對 涉及的pack進行讀取 解壓縮/壓縮。（其他方案在修改元數(shù)據(jù)時也需要對pack進行讀取解壓縮）

方案2.存放DPN里：

優(yōu)點：刪除不需要對 pack 進行讀取保存，只需要修改元數(shù)據(jù)即可，且 delete 位圖大小是固定的。

缺點：delete 位圖過大，一般是 8192 個字節(jié)，遠遠超過原本元數(shù)據(jù)的大小，會極大的影響原 DPN 的讀寫效率。

方案3. RCAttr::hdr 中：優(yōu)點：一個列中只需要維護一個delete位圖即可，節(jié)省存儲空間。缺點：因為列的數(shù)據(jù)數(shù)量是會隨時變化的，不像 pack 和DPN 維護的單獨一個包數(shù)據(jù)的數(shù)量是固定的，這就造成了 ，delete位圖的大小也需要隨時變化。方案4. 為每列新增 deleteBitMap 文件：

在 DPN中增加 deletBitMap 索引，與 deleteBitMap 文件中的 deleteBitMap 對應，如下圖：

優(yōu)點：可以與 DPN 一 一對應，且 delete 位圖大小固定。缺點：需要新增一個文件專門維護 delete bitmap ,讀取 DPN 文件的同時也需要讀取 delelte bitmap 文件，會增加一次 IO。

我們最后的選擇

最后，經(jīng)過綜合考量，我們這里使用了方案 1 進行了把 delete 位圖放到 pack 里進行標記 delete 功能的開發(fā)。

數(shù)據(jù)過濾的流程和涉及邏輯的改造

經(jīng)過上述的思路梳理，我們應該大致能清晰地了解到增加 Delete 功能的流程，因為涉及的東西比較多，我這里做了一個腦圖，具體的代碼，大家可以訪問我們的Github 代碼倉庫進行了解：https://github.com/stoneatom/stonedb

其中Tianmu引擎存儲的元數(shù)據(jù)和pack數(shù)據(jù)是支持多版本的，這樣可以保障數(shù)據(jù)的原子性，而且可以支持并發(fā)的讀取數(shù)據(jù)，也就是說，在執(zhí)行delete時并不會堵塞select，用戶訪問的數(shù)據(jù)是最終確定的版本。關(guān)于多版本和并發(fā)訪問控制會在以后單獨出文章進行詳細的講解。

好了，以上就是目前 StoneDB 自研列式引擎 Tianmu 對 Delete的實現(xiàn)思路，希望這兩期分享能給大家?guī)韼椭?/p>