【研發分享】StoneDB如何給Tianmu引擎增加delete功能（調研之旅）

StoneDB 作為開源項目，一直秉持開源開放的基本原則，我們的社區版代碼現在已經完全在 Github 上開源，並不斷提高代碼的可讀友好性，同時，為了讓大家更好地理解我們是如何打造一款一體化 HTAP 開源資料庫的，我們會定期把一些核心技術的研發實現思路分享給大家，也算是拋磚引玉，如果讀者有更好的實 ...

StoneDB 作為開源項目，一直秉持開源開放的基本原則，我們的社區版代碼現在已經完全在 Github 上開源，並不斷提高代碼的可讀友好性，同時，為了讓大家更好地理解我們是如何打造一款一體化 HTAP 開源資料庫的，我們會定期把一些核心技術的研發實現思路分享給大家，也算是拋磚引玉，如果讀者有更好的實現思路，也歡迎與我們溝通，甚至可以參與到我們社區版的開發中~

Tianmu 引擎是 StoneDB 團隊自研的一款列式存儲引擎，在6月初剛開源時，並不支持 delete 功能，對此很多用戶都提出了需求的意見，所以我們當時也把 delete 功能列入到我們的年度 Roadmap里了，預計在10月20號的 StoneDB_5.7_v1.0.1 正式版本中，上線此功能。第一期，我將分享一下對 delete 功能的調研情況。
file
前置知識：資料庫中刪除數據的三種方式
以 Mysql 5.7 為例，資料庫刪除數據的方式一共有三種：

delete
truncate
drop

以上三種方式都可以刪除數據，但是使用場景是不同的。

對於整個表進行刪除的執行速度來說：

drop > truncate >> delete

DELETE

delete 是屬於資料庫的 DML 操作語言，一般是根據條件逐行進行刪除。

使用 delete 刪除數據時，資料庫只能刪除數據不能刪除表的結構，並且會觸發資料庫的事務機制。

delete 執行時，會先將所刪除數據緩存到 rollback segment 中，事務 commit 之後生效。

在 InnoDB 中，使用 delete 其實並不會真正的把數據刪除，是一種邏輯刪，資料庫底層實際上只是給刪除的數據做了一個已刪除的標記，因此，刪除數據後的表占空間大小和刪除前是一樣的。

TRUNCATE

truncate 屬於資料庫 DDL 定義語言，不走事務，原數據不放到 rollback segment 中，操作不觸發 trigger。執行後立即生效，無法找回（慎用刪除執行後，數據就沒了，不可恢復）。

truncate 刪除表會立刻釋放磁碟空間。truncate table其實有點類似於drop table 然後 create,只不過這個 create table 的過程做了優化，比如表結構文件之前已經有了等等。所以速度上是接近 drop table 的速度；

DROP

drop 屬於資料庫 DDL 定義語言，同 truncate ，執行後立即生效，無法找回。

drop table table_name立刻釋放磁碟空間，drop 語句將刪除表的結構、被依賴的約束(constraint)、觸發器(trigger)、索引(index)；依賴於該表的存儲過程/函數將保留,但是變為 invalid 狀態。

file
Tianmu 引擎對 delete 功能的調研
Tianmu 是一個列式存儲引擎，列式存儲的出現主要是為了方便快捷查詢和高效存儲大量同類型的數據而設計的，主要使用場景就是 OLAP。下麵是 OLAP場景的部分關鍵特征：

絕大多數是讀請求。
數據以相當大的批次(> 1000行)更新，而不是單行更新;或者根本沒有更新。
已添加到資料庫的數據不能修改。
對於讀取，從資料庫中提取相當多的行，但只提取列的一小部分。
列中的數據相對較小：數字和短字元串(例如，每個URL 60個位元組)。
處理單個查詢時需要高吞吐量(每台伺服器每秒可達數十億行)。
事務不是必須的。
對數據一致性要求低。

而 OLAP 場景下，對於數據的 delete 的操作可以說沒有或者頻率很小。列式存儲對比行式存儲來說並不擅長數據的增刪改，如果是為了極致的查詢性能，完全可以捨棄 DML 操作（比如初期的 ClickHouse 也不支持 delete）。但是為了功能的完整性，我們初期就放開了 insert 和 update 的功能，不過沒有對 delete 功能進行支持。

隨著用戶的呼聲越來越多，我們開始對各個有列式存儲的資料庫進行了一個調研，如下表所示：
file
目前行業現狀

通過分析目前行業內支持列式存儲的主流資料庫，大部分都是支持的，就算不支持直接 delete,也是支持 DML 同步的，所以 Tianmu 引擎的 delete 功能確實有必要進行開發支持。
file

主流列式資料庫的 delete 方案

openGauss

存儲結構

openGauss 列存儲引擎的底層存儲結構與 Tianmu 引擎類似，存儲基本單位是CU（Compression Unit，壓縮單元），即表中一列的一部分數據組成的壓縮數據塊。行存引擎中是以行作為單位來管理，而當使用列存儲時，整個表整體被按照不同列劃分為若幹個 CU。
file
file
每個 CU 對應一個 CUDesc 的記錄，在 CUDesc 里記錄了整個 CU 的事務時間戳信息、CU 的大小、存儲位置、magic 校驗碼、min/max 等信息。
file
每張列存表還配有張 Delta 表，Delta 表自身為行存儲表。當有少量的數據插入到一張列存表時，數據會被暫時放入 Delta 表，等到達閾值或滿足一定條件或操作時再行整合為 CU 文件。Delta 表可以避免單點數據操作帶來的很重的 CU 操作與開銷。

delete 策略

CU 中數據的刪除，實際上是標記刪除。刪除操作，相當於是更新了 CUDesc 表中 CU 對應 CUDesc 記錄的 delete bitmap（刪除點陣圖）結構，標記列中某行對應數據已被刪除，而 CU 文件數據不會被更改。這樣可以避免刪除操作帶來的 IO 放大以及解壓、壓縮的高額 CPU 開銷。這樣的設計，也可以使得對於同一個 CU 的 select（查詢）和 delete（刪除）互不阻塞，提升併發能力。列存儲 CU 中數據更新，則是遵循 append-only（僅允許追加）原則的，即 CU 文件僅會向後進行延展擴充，亦或是啟用新的 CU 文件，而不是在對應行在 CU 中的位置就地更新。
file

ClickHouse

存儲結構

file
ClickHouse 支持在建表時，指定將數據按照某些列進行 sort by。排序後，保證了相同 sort key 的數據在磁碟上連續存儲，且有序擺放。在進行等值、範圍查詢時，where 條件命中的數據都緊密存儲在一個或若幹個連續的 Block 中，而不是分散的存儲在任意多個 Block，大幅減少需要 IO 的 block 數量。另外，連續 IO 也能夠充分利用操作系統 page cache的預取能力，減少 page fault。

delete 策略

特點：缺少高頻率，低延遲的修改或刪除已存在數據的能力。僅能用於批量刪除或修改數據。

ClickHouse是個分析型資料庫。OLAP場景下，數據一般是不變的，因此 ClickHouse 對 update、delete 的支持是比較弱的，實際上並不支持標準的 update、delete 操作。

ClickHouse 通過 alter 方式實現更新、刪除，它把 update、delete 操作叫做 mutation(突變)。

標準SQL的更新、刪除操作是同步的，即客戶端要等服務端返回執行結果（通常是int值），而ClickHouse的update、delete是通過非同步方式實現的，當執行update語句時，服務端立即返回，但是實際上此時數據還沒變，而是排隊等著。

Mutation具體過程

首先，使用where條件找到需要修改的分區；然後，重建每個分區，用新的分區替換舊的，分區一旦被替換，就不可回退；對於單獨一個分區，是原子性的；但對於整個 mutation，如果涉及多個分區，則不是原子性的。

PolarDB In-Memory Column Index

存儲結構

特點：PolarDB 將列存實現為 InnoDB 的二級索引。
在 PolarDB 中所有 Primary Index 和 Secondary Index 都實現為一個 B+Tree。列索引在定義上是一個 Index，但其實是一個虛擬的索引，用於捕獲對該索引覆蓋列的增刪改操作。
file
實現為 InnoDB 二級索引方案的優點：

查詢執行器的工程實現非常簡單
可以復用 InnoDB 的事務處理框架
可以復用 InnoDB 的數據編碼格式
DDL 語句操作非常靈活
可以復用 InnoDB 的 Redo 事務日誌模塊
二級索引與主表有一樣的生命周期，方便管理

PolarDB In-Memory Column Index 的存儲使用了無序且追加寫的格式。

列索引中記錄按 RowGroup 進行組織，每個 RowGroup 中不同的列會各自打包形成 DataPack。

每個 RowGroup 都採用追加寫，分屬每個列的 DataPack 也是採用追加寫模式。

對於一個列索引，只有個 Active RowGroup 負責接受新的寫入。

當該 RowGroup 寫滿之後即凍結，其包含的所有 DataPack 會轉為壓縮格保存到磁碟上，同時記錄每個數據塊的統計信息便於過濾。

列存 RowGroup 中每新寫入一行都會分配一個 RowID 用作定位，屬於一行的所有列都可以用該 RowID 計算定位，同時系統維護 PK 到 RowID 的映射索引，以支持後續的刪除和修改操作。
file

delete 策略

在 PolarDB In-Memory Column Index 中，刪除操作只需要設置一個刪除標記位。更新操作採用標記刪除的方式來支持，對於更新操作，首先根據 RowID 計算出其原始位置並設置刪除標記，然後在 ActiveRowGroup 中寫入新的數據版本。

當一個 RowGroup 中的無效記錄超過一定閾值，則會觸發後臺非同步 compaction 操作，其作用一方面是回收空間，另一方面可以讓有效數據存儲更加緊湊，提升分析型查詢的效率。
file
各列式存儲的delete方案彙總
file
好了，以上就是我對 delete 功能的一個調研情況，下一期我將分享一下，Tinamu 引擎實現 delete 的具體思路。

作者：李紅建（空海）

編輯：宇亭