新增小助手，加入社群交流群
與數百位資深資料庫從業人員深度交流
列存引擎 Tianmu 如何實現 Delete？| StoneDB 研發分享 #3
責編：宇亭
Tianmu 引擎的儲存結構
當然，可能一些同學乍一看上面的什麼 DN、DPN 都不知道什麼意思，其實是因為我們的 Tianmu 引擎使用了非常重要的知識網格（Knowledge Grid）技術，後面我們有時間會單獨出更詳細的文章來分享知識網格相關的最新研究。
如上圖所示，DPN（Data Pack Node） 是知識網格的資料元資訊節點在程式碼中的資料結構，資料持久化在各個列資料夾下面的 DN 檔案中，初始化資料元資訊節點時從利用 mmap機制把DN檔案對映到記憶體中。pack 是物理的資料塊，每個pack儲存著對應列中多個列資料，pack 物件跟 DPN 物件 1:1 對應，負責從 各個列資料夾下面的 DATA 檔案寫入資料 和讀取資料。pack 中的資料經過高度壓縮後儲存到 DATA 檔案中。
Tianmu 的資料都是根據列按照行資料緊密排序進行儲存的，從檔案中讀取和寫入的單位是 pack，其中：
行號與 DPN & pack 的關係：
DPN id 由 row_id 進行位移右移執行得出， pss 的值一般為 16 ，也就是說每 65536 行的資料組成一個 pack，資料包結構的資訊比如行與資料包的偏移量 pss, 資料化結構體為 COL_META 持久化在 META 檔案中。
行號與 pack 中資料 id 的關係：
資料 ID 由 row_id 對 1 左移 pss 為後的值 取餘後得出，基本上資料ID也都是在 0~65536 之間。
MySQL 的多引擎架構和執行介面
可以看到，MySQL 架構的最大特點之一，就是支援可插拔儲存引擎。再來看一下MySQL 的執行介面邏輯圖：
#0 Tianmu::handler::ha_tianmu::write_row (this=0x7fdcec0107b0, buf=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/storage/tianmu/handler/ha_tianmu.cpp:455
#1 0x0000000001d6e5a1 in handler::ha_write_row (this=0x7fdcec0107b0, buf=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/sql/handler.cc:8189
#2 0x00000000025ebf12 in write_record (thd=0x7fdcec000bc0,table=0x7fdcec00fdf0,info=0x7fe0c81c9b00, update=0x7fe0c81c9a80)
at /home/Code/GitHub/stonedb/sql/sql_insert.cc:1904
#3 0x00000000025e8fdd in Sql_cmd_insert::mysql_insert (this=0x7fdcec006ab0,thd=0x7fdcec000bc0, table_list=0x7fdcec006518)
at /home/Code/GitHub/stonedb/sql/sql_insert.cc:778
#4 0x00000000025ef9b3 in Sql_cmd_insert::execute (this=0x7fdcec006ab0, thd=0x7fdcec000bc0)
at /home/Code/GitHub/stonedb/sql/sql_insert.cc:3151
#5 0x00000000023cb967 in mysql_execute_command (thd=0x7fdcec000bc0,first_level=true)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:3645
#6 0x00000000023d175d in mysql_parse (thd=0x7fdcec000bc0,parser_state=0x7fe0c81cae70)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:5655
#7 0x00000000023c68b8 in dispatch_command (thd=0x7fdcec000bc0,com_data=0x7fe0c81cb610, command=COM_QUERY)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1495
#8 0x00000000023c57e5 in do_command (thd=0x7fdcec000bc0)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1034
#9 0x00000000024f6beb in handle_connection (arg=0x91fc3a0)
at /home/Code/GitHub/stonedb/sql/conn_handler/connection_handler_per_thread.cc:313
#10 0x0000000002bc3d2a in pfs_spawn_thread (arg=0x91ce010)
at /home/Code/GitHub/stonedb/storage/perfschema/pfs.cc:2197
#11 0x00007fe141fa9ea5 in start_thread () from /lib64/libpthread.so.0
#12 0x00007fe13f246b0d in clone () from /lib64/libc.so.6
#0 Tianmu::handler::ha_tianmu::update_row (this=0x7fdcec0107b0,
old_data=0x7fdcec09eb18 "\374\002", new_data=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/storage/tianmu/handler/ha_tianmu.cpp:508
#1 0x0000000001d6ea41 in handler::ha_update_row (this=0x7fdcec0107b0,
old_data=0x7fdcec09eb18 "\374\002", new_data=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/sql/handler.cc:8230
#2 0x000000000247ed8c in mysql_update (thd=0x7fdcec000bc0, fields=...,
values=..., limit=18446744073709551615, handle_duplicates=DUP_ERROR,
found_return=0x7fe0c81c9c58, updated_return=0x7fe0c81c9c50)
at /home/Code/GitHub/stonedb/sql/sql_update.cc:894
#3 0x0000000002484ead in Sql_cmd_update::try_single_table_update (
this=0x7fdcec006808, thd=0x7fdcec000bc0,
switch_to_multitable=0x7fe0c81c9cff)
at /home/Code/GitHub/stonedb/sql/sql_update.cc:2927
#4 0x00000000024853d7 in Sql_cmd_update::execute (this=0x7fdcec006808,
thd=0x7fdcec000bc0) at /home/Code/GitHub/stonedb/sql/sql_update.cc:3058
#5 0x00000000023cba0c in mysql_execute_command (thd=0x7fdcec000bc0,
first_level=true) at /home/Code/GitHub/stonedb/sql/sql_parse.cc:3655
#6 0x00000000023d175d in mysql_parse (thd=0x7fdcec000bc0,
parser_state=0x7fe0c81cae70)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:5655
#7 0x00000000023c68b8 in dispatch_command (thd=0x7fdcec000bc0,
com_data=0x7fe0c81cb610, command=COM_QUERY)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1495
#8 0x00000000023c57e5 in do_command (thd=0x7fdcec000bc0)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1034
#9 0x00000000024f6beb in handle_connection (arg=0x91fc3a0)
at /home/Code/GitHub/stonedb/sql/conn_handler/connection_handler_per_thread.cc:313
#10 0x0000000002bc3d2a in pfs_spawn_thread (arg=0x91ce010)
at /home/Code/GitHub/stonedb/storage/perfschema/pfs.cc:2197
#11 0x00007fe141fa9ea5 in start_thread () from /lib64/libpthread.so.0
#12 0x00007fe13f246b0d in clone () from /lib64/libc.so.6
delete呼叫堆疊：
#0 Tianmu::handler::ha_tianmu::delete_row (this=0x7fdcec0107b0,
buf=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/storage/tianmu/handler/ha_tianmu.cpp:581
#1 0x0000000001d6ee3f in handler::ha_delete_row (this=0x7fdcec0107b0,
buf=0x7fdcec09e710 "\374\002")
at /home/Code/GitHub/stonedb/sql/handler.cc:8263
#2 0x00000000025e053f in Sql_cmd_delete::mysql_delete (this=0x7fdcec006e28,
thd=0x7fdcec000bc0, limit=18446744073709551615)
at /home/Code/GitHub/stonedb/sql/sql_delete.cc:497
#3 0x00000000025e3268 in Sql_cmd_delete::execute (this=0x7fdcec006e28,
thd=0x7fdcec000bc0) at /home/Code/GitHub/stonedb/sql/sql_delete.cc:1411
#4 0x00000000023cba0c in mysql_execute_command (thd=0x7fdcec000bc0,
first_level=true) at /home/Code/GitHub/stonedb/sql/sql_parse.cc:3655
#5 0x00000000023d175d in mysql_parse (thd=0x7fdcec000bc0,
parser_state=0x7fe0c81cae70)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:5655
#6 0x00000000023c68b8 in dispatch_command (thd=0x7fdcec000bc0,
com_data=0x7fe0c81cb610, command=COM_QUERY)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1495
#7 0x00000000023c57e5 in do_command (thd=0x7fdcec000bc0)
at /home/Code/GitHub/stonedb/sql/sql_parse.cc:1034
#8 0x00000000024f6beb in handle_connection (arg=0x91fc3a0)
at /home/Code/GitHub/stonedb/sql/conn_handler/connection_handler_per_thread.cc:313
#9 0x0000000002bc3d2a in pfs_spawn_thread (arg=0x91ce010)
at /home/Code/GitHub/stonedb/storage/perfschema/pfs.cc:2197
#10 0x00007fe141fa9ea5 in start_thread () from /lib64/libpthread.so.0
#11 0x00007fe13f246b0d in clone () from /lib64/libc.so.6
由呼叫堆疊可知，insert、update和delete的相關程式碼指令都會呼叫到Tianmu::dbhandler::TianmuHandler 類中各自功能的函式，而 TianmuHandler 繼承自 handler，MySQL 以 handler 為基類，各個引擎的 handler 類為子類，利用多型的原理實現對不同引擎的呼叫。
如果要實現Tianmu的單表 delete 功能，就需要在 TianmuHandler :: delete_row() 中進行實現。同時 handler 類還提供了刪除所有行的虛擬函式 delete_all_rows() 如需支援刪除所有行的資料，可在TianmuHandler :: delete_all_rows() 中進行實現。
Tianmu 引擎刪除資料的過程
單表 delete all 功能：
目前我們是支援 truncate 功能的，單表 delete all 的功能就直接複用 truncate 的邏輯。
條件 delete 功能：
條件 delete 這裡我們採用標記刪除的策略。列式資料庫的儲存結構決定了對真實的資料進行刪除時必須要對整個表的資料進行重新移動整理，因為除了刪除無用的行，還需要合併資料塊。這樣的話，在資料量非常多的情況下，對真實的資料進行刪除將會是非常大的動作，不僅會消耗機器大量的IO資源和CPU資源，同時刪除的速度也會比較慢。這也是目前主流支援列式資料庫的廠商都使用標記刪除的原因。
注意看上面的執行流程圖，我們會發現一個很重要的節點——Deletebitmap（Delete點陣圖），這個 Delete 點陣圖是什麼呢？這裡要重點講解一下。
點陣圖（bitmap）的實際儲存形式是個 int32 型別的陣列，原理是使用 int32 型別的值佔用的 32 位空間使用 0 或 1 儲存並記錄這 32 個值的狀態。點陣圖中的位元總數等於包中的行的總數。資料在 pack 中的位置和點陣圖中的位置是一一對應的，這樣可以有效地節省空間。
那麼 Delete 點陣圖應該存放在哪個位置呢？一般有這麼四種方案：
方案1.存放在pack裡：
優點：進行標記刪除的時候同時可對資料置空，可有效的釋放字串型別的空間，同時可優化 select ,insert ,update 帶where子句的資料過濾場景。不需要修改上層邏輯。整體邏輯簡單。修改面主要集中在pack層。
缺點：每次刪除都需要對 涉及的pack進行讀取 解壓縮/壓縮。（其他方案在修改元資料時也需要對pack進行讀取解壓縮）
優點：刪除不需要對 pack 進行讀取儲存，只需要修改元資料即可，且 delete 點陣圖大小是固定的。
缺點：delete 點陣圖過大，一般是 8192 個位元組，遠遠超過原本元資料的大小，會極大的影響原 DPN 的讀寫效率。
在 DPN中增加 deletBitMap 索引，與 deleteBitMap 檔案中的 deleteBitMap 對應，如下圖：
我們最後的選擇
最後，經過綜合考量，我們這裡使用了方案 1 進行了把 delete 點陣圖放到 pack 裡進行標記 delete 功能的開發。
資料過濾的流程和涉及邏輯的改造
經過上述的思路梳理，我們應該大致能清晰地瞭解到增加 Delete 功能的流程，因為涉及的東西比較多，我這裡做了一個腦圖，具體的程式碼，大家可以訪問我們的Github 程式碼倉庫進行了解：http://github.com/stoneatom/stonedb
其中Tianmu引擎儲存的元資料和pack資料是支援多版本的，這樣可以保障資料的原子性，而且可以支援併發的讀取資料，也就是說，在執行delete時並不會堵塞select，使用者訪問的資料是最終確定的版本。關於多版本和併發訪問控制會在以後單獨出文章進行詳細的講解。
好了，以上就是目前 StoneDB 自研列式引擎 Tianmu 對 Delete的實現思路，希望這兩期分享能給大家帶來幫助。當然，由於是文章，裡面很多圖片的細節，我們沒有展開描述，之前我們有開展過技術分享公開課，大家也可以前往B站觀看這兩期視訊：
【StoneDB每日講】Tianmu 引擎 Delete 方案的調研-第一講
http://www.bilibili.com/video/BV1Q14y1t7ZC
【StoneDB每日講】Tianmu 引擎 Delete 功能的誕生-第二講
http://www.bilibili.com/video/BV1Cg411S7tt
本週四，StoneDB啟航計劃的原始碼解讀活動，李紅建老師也會帶大家深入理解一下Tinamu 引擎工具類模組的原始碼，歡迎大家關注收看：
StoneDB 開源地址：http://github.com/stoneatom/stonedb
StoneDB 社群官網：http://stonedb.io
子查詢優化之 Semi-join 優化 | StoneDB 研發分享 #2
HTAP 的下一步？SoTP 初探（下）：解讀 Serving over TP 和其典型案例場景
HTAP 的下一步？SoTP初探(上)：資料分析從“大”資料轉向“小”而“寬”資料
StoneDB 團隊成員與 MySQL 之父 Monty 會面，共話未來資料庫形態
本文分享自微信公眾號 - StoneDB（StoneDB2021）。
如有侵權，請聯絡 [email protected] 刪除。
本文參與“OSC源創計劃”，歡迎正在閱讀的你也加入，一起分享。
「其他文章」
- 為什麼 MySQL 使用 B 樹？| StoneDB資料庫觀察
- 帶你來吃瓜！Andy Pavlo教授帶您一文回顧資料庫的2022年
- 哪篇論文宣佈了 HTAP 資料庫的誕生？ | StoneDB學術分享會#5
- 列存引擎 Tianmu 如何實現 Delete？| StoneDB 研發分享 #3
- StoneDB 首席架構師李浩：如何選擇一款 HTAP 產品？
- 如何給一個 HTAP 資料庫做基準測試？| StoneDB學術分享會 #4
- StoneDB讀寫分離實踐方案
- StoneDB 團隊成員與 MySQL 之父 Monty 會面，共話未來資料庫形態
- 爆肝整理5000字！HTAP的關鍵技術有哪些？| StoneDB學術分享會#3
- 爆肝整理5000字！HTAP的關鍵技術有哪些？| StoneDB學術分享會#3
- 解讀《Benchmarking Hybrid OLTP&OLAP Database Systems》| StoneDB學術分享會
- 深度乾貨！一篇 Paper 帶您讀懂 HTAP | StoneDB 學術分享會第①期
- StoneDB 讀、寫操作的執行過程
- StoneDB 宣佈開源，一體化實時 HTAP 架構為何是當前最優解
- 什麼是真正的HTAP？（一）背景篇
- 什麼是真正的HTAP？（一）背景篇
- 一體化實時HTAP資料庫StoneDB，如何替換MySQL並實現近百倍分析效能的提升
- StoneDB 為國產資料庫添磚加瓦，基於 MySQL 的一體化實時 HTAP 資料庫正式開源！