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

前置知識(shí)：數(shù)據(jù)庫(kù)中刪除數(shù)據(jù)的三種方式

以 Mysql 5.7 為例，數(shù)據(jù)庫(kù)刪除數(shù)據(jù)的方式一共有三種：

1. delete

2. truncate

3. drop

以上三種方式都可以刪除數(shù)據(jù)，但是使用場(chǎng)景是不同的。

對(duì)于整個(gè)表進(jìn)行刪除的執(zhí)行速度來(lái)說(shuō)：

drop > truncate >> delete

DELETE

delete 是屬于數(shù)據(jù)庫(kù)的 DML 操作語(yǔ)言，一般是根據(jù)條件逐行進(jìn)行刪除。

使用 delete 刪除數(shù)據(jù)時(shí)，數(shù)據(jù)庫(kù)只能刪除數(shù)據(jù)不能刪除表的結(jié)構(gòu)，并且會(huì)觸發(fā)數(shù)據(jù)庫(kù)的事務(wù)機(jī)制。

delete 執(zhí)行時(shí)，會(huì)先將所刪除數(shù)據(jù)緩存到 rollback segment 中，事務(wù) commit 之后生效。

在 InnoDB 中，使用 delete 其實(shí)并不會(huì)真正的把數(shù)據(jù)刪除，是一種邏輯刪，數(shù)據(jù)庫(kù)底層實(shí)際上只是給刪除的數(shù)據(jù)做了一個(gè)已刪除的標(biāo)記，因此，刪除數(shù)據(jù)后的表占空間大小和刪除前是一樣的。

TRUNCATE

truncate 屬于數(shù)據(jù)庫(kù) DDL 定義語(yǔ)言，不走事務(wù)，原數(shù)據(jù)不放到 rollback segment 中，操作不觸發(fā) trigger。執(zhí)行后立即生效，無(wú)法找回（慎用 刪除執(zhí)行后，數(shù)據(jù)就沒(méi)了，不可恢復(fù)）。

truncate 刪除表會(huì)立刻釋放磁盤(pán)空間。truncate table其實(shí)有點(diǎn)類(lèi)似于drop table 然后 create,只不過(guò)這個(gè) create table 的過(guò)程做了優(yōu)化，比如表結(jié)構(gòu)文件之前已經(jīng)有了等等。所以速度上是接近 drop table 的速度;

DROP

drop 屬于數(shù)據(jù)庫(kù) DDL 定義語(yǔ)言，同 truncate ，執(zhí)行后立即生效，無(wú)法找回。

drop table table_name立刻釋放磁盤(pán)空間 ,drop 語(yǔ)句將刪除表的結(jié)構(gòu)、被依賴(lài)的約束(constraint)、觸發(fā)器(trigger)、索引(index); 依賴(lài)于該表的存儲(chǔ)過(guò)程/函數(shù)將保留,但是變?yōu)?invalid 狀態(tài)。

Tianmu 引擎對(duì) delete 功能的調(diào)研

Tianmu 是一個(gè)列式存儲(chǔ)引擎，列式存儲(chǔ)的出現(xiàn)主要是為了方便快捷查詢(xún)和高效存儲(chǔ)大量同類(lèi)型的數(shù)據(jù)而設(shè)計(jì)的，主要使用場(chǎng)景就是 OLAP。下面是 OLAP場(chǎng)景的部分關(guān)鍵特征：

• 絕大多數(shù)是讀請(qǐng)求

• 數(shù)據(jù)以相當(dāng)大的批次(> 1000行)更新，而不是單行更新;或者根本沒(méi)有更新。

• 已添加到數(shù)據(jù)庫(kù)的數(shù)據(jù)不能修改。

• 對(duì)于讀取，從數(shù)據(jù)庫(kù)中提取相當(dāng)多的行，但只提取列的一小部分。

• 列中的數(shù)據(jù)相對(duì)較?。簲?shù)字和短字符串(例如，每個(gè)URL 60個(gè)字節(jié))

• 處理單個(gè)查詢(xún)時(shí)需要高吞吐量(每臺(tái)服務(wù)器每秒可達(dá)數(shù)十億行)

• 事務(wù)不是必須的

• 對(duì)數(shù)據(jù)一致性要求低

而 OLAP 場(chǎng)景下，對(duì)于數(shù)據(jù)的 delete 的操作可以說(shuō)沒(méi)有或者頻率很小。列式存儲(chǔ)對(duì)比行式存儲(chǔ)來(lái)說(shuō)并不擅長(zhǎng)數(shù)據(jù)的增刪改，如果是為了極致的查詢(xún)性能，完全可以舍棄 DML 操作（比如初期的 ClickHouse 也不支持 delete）。但是為了功能的完整性，我們初期就放開(kāi)了 insert 和 update ?的功能，不過(guò)沒(méi)有對(duì) delete 功能進(jìn)行支持。

隨著用戶(hù)的呼聲越來(lái)越多，我們開(kāi)始對(duì)各個(gè)有列式存儲(chǔ)的數(shù)據(jù)庫(kù)進(jìn)行了一個(gè)調(diào)研，如下表所示：

通過(guò)分析目前行業(yè)內(nèi)支持列式存儲(chǔ)的主流數(shù)據(jù)庫(kù)，大部分都是支持的，就算不支持直接 delete,也是支持 DML 同步的，所以 Tianmu 引擎的 delete 功能確實(shí)有必要進(jìn)行開(kāi)發(fā)支持。

主流列式數(shù)據(jù)庫(kù)的 delete 方案

openGauss

存儲(chǔ)結(jié)構(gòu)

openGauss 列存儲(chǔ)引擎的底層存儲(chǔ)結(jié)構(gòu)與 Tianmu 引擎類(lèi)似 ，存儲(chǔ)基本單位是CU（Compression Unit，壓縮單元），即表中一列的一部分?jǐn)?shù)據(jù)組成的壓縮數(shù)據(jù)塊。行存引擎中是以行作為單位來(lái)管理，而當(dāng)使用列存儲(chǔ)時(shí)，整個(gè)表整體被按照不同列劃分為若干個(gè) CU。

每個(gè) CU 對(duì)應(yīng)一個(gè) CUDesc 的記錄，在 CUDesc 里記錄了整個(gè) CU 的事務(wù)時(shí)間戳信息、CU 的大小、存儲(chǔ)位置、magic 校驗(yàn)碼、min/max 等信息。

每張列存表還配有張 Delta 表，Delta 表自身為行存儲(chǔ)表。當(dāng)有少量的數(shù)據(jù)插入到一張列存表時(shí)，數(shù)據(jù)會(huì)被暫時(shí)放入 Delta 表，等到達(dá)閾值或滿(mǎn)足一定條件或操作時(shí)再行整合為 CU 文件。Delta 表可以避免單點(diǎn)數(shù)據(jù)操作帶來(lái)的很重的 CU 操作與開(kāi)銷(xiāo)。

delete 策略

CU 中數(shù)據(jù)的刪除，實(shí)際上是標(biāo)記刪除。刪除操作，相當(dāng)于是更新了 CUDesc 表中 CU 對(duì)應(yīng) CUDesc 記錄的 delete bitmap（刪除位圖）結(jié)構(gòu)，標(biāo)記列中某行對(duì)應(yīng)數(shù)據(jù)已被刪除，而 CU 文件數(shù)據(jù)不會(huì)被更改。這樣可以避免刪除操作帶來(lái)的 IO 放大以及解壓、壓縮的高額 CPU 開(kāi)銷(xiāo)。這樣的設(shè)計(jì)，也可以使得對(duì)于同一個(gè) CU 的 select（查詢(xún)）和 delete（刪除）互不阻塞，提升并發(fā)能力。列存儲(chǔ) CU 中數(shù)據(jù)更新，則是遵循 append-only（僅允許追加）原則的，即 CU 文件僅會(huì)向后進(jìn)行延展擴(kuò)充，亦或是啟用新的 CU 文件，而不是在對(duì)應(yīng)行在 CU 中的位置就地更新。

ClickHouse

存儲(chǔ)結(jié)構(gòu)

ClickHouse 支持在建表時(shí)，指定將數(shù)據(jù)按照某些列進(jìn)行 sort by。排序后，保證了相同 sort key 的數(shù)據(jù)在磁盤(pán)上連續(xù)存儲(chǔ)，且有序擺放。在進(jìn)行等值、范圍查詢(xún)時(shí)，where 條件命中的數(shù)據(jù)都緊密存儲(chǔ)在一個(gè)或若干個(gè)連續(xù)的 Block 中，而不是分散的存儲(chǔ)在任意多個(gè) Block， 大幅減少需要 IO 的 block 數(shù)量。另外，連續(xù) IO 也能夠充分利用操作系統(tǒng) page cache的預(yù)取能力，減少 page fault。

delete 策略

特點(diǎn)：缺少高頻率，低延遲的修改或刪除已存在數(shù)據(jù)的能力。僅能用于批量刪除或修改數(shù)據(jù)。

ClickHouse是個(gè)分析型數(shù)據(jù)庫(kù)。OLAP場(chǎng)景下，數(shù)據(jù)一般是不變的，因此 ClickHouse 對(duì) update、delete 的支持是比較弱的，實(shí)際上并不支持標(biāo)準(zhǔn)的 update、delete 操作。

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

標(biāo)準(zhǔn)SQL的更新、刪除操作是同步的，即客戶(hù)端要等服務(wù)端返回執(zhí)行結(jié)果（通常是int值），而ClickHouse的update、delete是通過(guò)異步方式實(shí)現(xiàn)的，當(dāng)執(zhí)行update語(yǔ)句時(shí)，服務(wù)端立即返回，但是實(shí)際上此時(shí)數(shù)據(jù)還沒(méi)變，而是排隊(duì)等著。

Mutation具體過(guò)程

首先，使用where條件找到需要修改的分區(qū)；然后，重建每個(gè)分區(qū)，用新的分區(qū)替換舊的，分區(qū)一旦被替換，就不可回退；對(duì)于單獨(dú)一個(gè)分區(qū)，是原子性的；但對(duì)于整個(gè) mutation，如果涉及多個(gè)分區(qū)，則不是原子性的。

PolarDB In-Memory Column Index

存儲(chǔ)結(jié)構(gòu)

特點(diǎn)：PolarDB 將列存實(shí)現(xiàn)為 InnoDB 的二級(jí)索引。

在 PolarDB 中所有 Primary Index 和 Secondary Index 都實(shí)現(xiàn)為一個(gè) B+Tree。列索引在定義上是一個(gè) Index，但其實(shí)是一個(gè)虛擬的索引，用于捕獲對(duì)該索引覆蓋列的增刪改操作。

實(shí)現(xiàn)為 InnoDB 二級(jí)索引方案的優(yōu)點(diǎn)：

• 查詢(xún)執(zhí)行器的工程實(shí)現(xiàn)非常簡(jiǎn)單

• 可以復(fù)用 InnoDB 的事務(wù)處理框架

• 可以復(fù)用 InnoDB 的數(shù)據(jù)編碼格式

• DDL 語(yǔ)句操作非常靈活

• 可以復(fù)用 InnoDB 的 Redo 事務(wù)日志模塊

• 二級(jí)索引與主表有一樣的生命周期，方便管理

PolarDB In-Memory Column Index 的存儲(chǔ)使用了無(wú)序且追加寫(xiě)的格式。

列索引中記錄按 RowGroup 進(jìn)行組織，每個(gè) RowGroup 中不同的列會(huì)各自打包形成 DataPack。

每個(gè) RowGroup 都采用追加寫(xiě)，分屬每個(gè)列的 DataPack 也是采用追加寫(xiě)模式。

對(duì)于一個(gè)列索引，只有個(gè) Active RowGroup 負(fù)責(zé)接受新的寫(xiě)入。

當(dāng)該 RowGroup 寫(xiě)滿(mǎn)之后即凍結(jié)，其包含的所有 DataPack 會(huì)轉(zhuǎn)為壓縮格保存到磁盤(pán)上，同時(shí)記錄每個(gè)數(shù)據(jù)塊的統(tǒng)計(jì)信息便于過(guò)濾。

列存 RowGroup 中每新寫(xiě)入一行都會(huì)分配一個(gè) RowID 用作定位，屬于一行的所有列都可以用該 RowID 計(jì)算定位，同時(shí)系統(tǒng)維護(hù) PK 到 RowID 的映射索引，以支持后續(xù)的刪除和修改操作。

delete 策略

在 PolarDB In-Memory Column Index 中，刪除操作只需要設(shè)置一個(gè)刪除標(biāo)記位。更新操作采用標(biāo)記刪除的方式來(lái)支持，對(duì)于更新操作，首先根據(jù) RowID 計(jì)算出其原始位置并設(shè)置刪除標(biāo)記，然后在 ActiveRowGroup 中寫(xiě)入新的數(shù)據(jù)版本。

當(dāng)一個(gè) RowGroup 中的無(wú)效記錄超過(guò)一定閾值，則會(huì)觸發(fā)后臺(tái)異步 compaction 操作，其作用一方面是回收空間，另一方面可以讓有效數(shù)據(jù)存儲(chǔ)更加緊湊，提升分析型查詢(xún)的效率。

各列式存儲(chǔ)的delete方案匯總

好了，以上就是我對(duì) delete 功能的一個(gè)調(diào)研情況，下一期我將分享一下，Tinamu 引擎實(shí)現(xiàn) delete 的具體思路。

作者：李紅建（空海）

編輯：宇亭