列存具有「讀友好，寫不友好」的特點。這個特點使列存和 AP 數據庫彷彿王八看綠豆一樣——對上眼了。因爲 AP 數據庫正好重視讀性能（大查詢吞吐量），不重視寫性能（能容忍 T+1h/1d 更新）。於是，列存順理成章地霸佔了 AP 數據庫的存儲底座。

近年來，隨着業務的發展，越來越多的業務場景霸道地要求 AP 數據庫必須具備實時分析能力。爲此，AP 數據庫必須把上游 TP 數據庫產生的寫入和更新實時地導入進來。這對 AP 數據庫的列存更新效率製造了新的挑戰。

本文將介紹迎接這個挑戰誕生的列存高效更新技術。探討內容包括：

1. 列存更新的難點。

2. 一種低效更新方案。

3. 四類高效更新方案，並介紹這些方案在業界數據庫中的實現。涉及數據庫包括 Iceberg，Hudi，Kudu，Doris，ADB，Hologres 等。

4. 比較總結所有方案。

希望本文能對讀者瞭解列存更新技術有所幫助。

列存更新的難點

我認爲主要面臨兩個難點：一個是寫放大，另一個是無法簡單地做 in-place update。首先這裏的寫放大特指 IO 次數的放大，具體來說：

• 傳統列存（每列一個文件）：寫入需要每列一次磁盤 IO。儘管可以通過攢批來均攤開銷，但大寬表（成百上千列）場景仍然力不從心。

• 行列混存（PAX 格式）：文件被切分成很多 block，一行的所有列數據按列存格式塞到同一個 block 裏面。寫入需要在內存中攢滿一個列存 block，然後以 block 爲單位壓縮並刷盤。所有列一次 IO 搞定。儘管這種做法優化了磁盤 IO 次數，但在內存 IO 次數方面還是有放大，因爲內存 block 不是行存。

下文所有數據庫的列存格式均屬於行列混存。

其次是無法簡單地做 in-place update。原因有二：

1. 容易造成比較大的寫放大。列存的 block 非常大，因爲面向讀場景優化，追求高壓縮率。哪怕是 in-place update 一個 field，也有可能導致大 block 內數據的 reorganize。重寫大 block 會帶來比較大的寫放大。

2. 最致命的，AP 數據庫的趨勢都是 share-storage 架構，基於 HDFS/S3。這類分佈式存儲本身就不支持 in-place update。所以沒得選了，只能做 out-of-place update。

下文所有列存更新技術均屬於 out-of-place update。

低效更新技術

想了解什麼是高效更新技術，必須先了解什麼是低效更新技術。—— 黃金架構師（知乎和公衆號同名）

最簡單的 out-of-place update 方案是 file-level COW(copy-on-write) 。這種方案簡單來說就是更新時無論更新一行還是一批，都直接把原文件拷貝出來更新，然後生成一個新文件。

File-level COW 方案在業界的典型代表是 Hudi COW 表。Hudi COW 表的實現概述如下：

1. 宏觀上看，一張表的數據存儲在 HDFS/S3 上的很多列存文件中。

2. 更新時重寫整個列存文件。因爲要做寫寫衝突檢測（ww-conflict check；爲實現 snapshot isolation），更新需要保證可串行化。Hudi COW 通過 file-level 樂觀鎖來保證這一點。更新文件期間不加鎖，commit 時檢查有沒有併發寫事務搶先更新了相同的文件，如果有，那麼自己就 abort。換句話說，不支持對同一文件的併發更新。

3. 讀取時，按快照選取適當版本的文件。

這個方案的優點是讀性能非常棒，文件級別多版本使得讀完全不受寫的影響。缺點是寫性能很差，因爲寫放大很大，並且寫併發度低。

顯然，file-level COW 是一種低效更新方案。如果用這個方案來應對實時場景，那無異於以卵擊石。

到現在爲止，我們已經具備了低效更新技術的認知。那麼，接下來我們就可以往高效更新技術的殿堂進發了。

高效更新技術

我們可以思考一下，要想高效，應該做好哪些事情？我認爲，主要是兩件事情：

1. 降低寫放大，提升寫併發。單線程性能靠降低寫放大來優化，多線程性能靠提升寫併發來優化。單線程和多線程都在手，性能我有。

2. 儘量少損害讀性能。畢竟咱是 AP 數據庫，讀性能至關重要，還要靠它來喫飯。

爲了做好這兩件事情，我們應該追求：

1. 更細粒度的更新。Hudi COW 拷貝更新整個文件算是 file-level update。如果我們能做到 block-level，tuple-level，甚至是 field-level，寫放大會顯著優化。

2. 更細粒度的併發。Hudi COW 加 file-level 的鎖，算是 file-level concurrency。如果我們能做到 block-level，tuple-level，寫併發會顯著提升。（沒有 filed-level，複雜且開銷不一定小）。當然我們也要清醒地認識到，細粒度的併發需要細粒度的鎖，細粒度的鎖對於批量更新沒有那麼友好（想象一下更新整張表的數據，爲每一行加一個行鎖）。因此這裏存在一些取捨的空間。

上述思考很有意思。我運用這個思考框架，再結合業界數據庫的實際情況，把業界數據庫的高效更新方案按照寫併發和更新粒度分成了四類，分別是：

1. Table-level concurrency + tuple-level update.

2. File-level concurrency + tuple-level update.

3. Tuple-level concurrency + field-level update.

4. Unlimited concurrency + tuple-level update.  (Unlimited concurrency 看起來非常唬人，其含義我們下文再細說。)

這四類方案在各家數據庫中都是怎麼實現的呢？接下來我們挨個分析一下具體的案例。

Table-level concurrency + tuple-level update

這類方案的典型代表是 Iceberg MOR 表。

使用這類方案的數據庫絕對地重視批量更新，輕視併發更新和單行更新，因此更新通過表鎖來實現，僅支持 table-level concurrency。Iceberg MOR 表的實現概述如下：

1. 宏觀看是兩個存儲結構：存儲主要數據的列存文件（data file）和存儲標記刪除的文件（delete file）。data file 和它對應的 delete file 會定期合併成新的 data file。

2. 更新流程：update 看做 delete + insert。先向 delete file 追加一條 delete mark 刪除老版本，然後把新版本寫入 data file。

• Iceberg 的 delete mark 有兩種：1. position delete：記錄刪除行在 data file 中的行號，行號需要在更新的時候從 data file 中查到。2. equation delete：記錄刪除的等值條件。equation delete 的寫入更高效，尤其是在根據非主鍵（唯一鍵）的等值刪除場景。這個場景下一個等值條件會匹配很多行。equation delete 只記錄一個等值條件，而 position delete 需要爲每行查行號併爲每行記錄 delete mark。

• Iceberg 採用 table-level 樂觀鎖。更新操作完成後，需要把新增的 delete file 文件登記到表的元數據裏面去。如果此時發現別的併發事務往這張表已經登記過元數據，那麼自己就 abort（某些情況下會掙扎重試一下）。

• delete mark  和新版本 tuple 加起來的數據量級約等於一個 tuple，所以是 tuple-level update，寫放大很小。

4. 讀取流程：需要 merge 一下 data file 和 delete file（這也是 MOR(merge on read) 名稱的由來）。

• 如果是 position delete，只需要按行號順序地歸併 一下（因爲行號天然有序）。

• 如果是 equation delete，需要爲每一行計算可能很多（每刪除一次就多一個）的等值條件是否匹配。

• 二者對比，顯然 position delete 的讀取更高效。

相比 Hudi COW，Iceberg 的併發能力差了些。拋開併發不談，Iceberg 算是犧牲了一些讀取的性能（需要 merge on read），換取更新的性能。在這個基礎上，Iceberg 還提供了 position delete 和 equation delete 兩種方式，給用戶提供了 MOR 模式下進一步在讀友好和寫友好之間權衡的空間，這個做法很「用戶友好」。

File-level concurrency + tuple-level update

這類方案的典型代表是 Hudi MOR 表。

這類數據庫的特點是重視批量更新，但沒有 Iceberg 那麼極端，所以併發度稍高一點，做到了 file-level。Hudi MOR 表的實現概述如下：

1. 宏觀看是兩個存儲結構：存儲主要數據的列存文件（base file）和存儲增量更新的行存文件（log file）。log file 採用行存對寫比較友好。base file 和它對應的 log file 會定期合併成新的 base file。

2. 更新流程：update 看做 delete + insert。先向 log file 插入一條 delete mark 來標記刪除老版本，然後再向 log file 寫入新版本。

• delete mark 記的是主鍵。但 log file 中的數據是 append 的，並不按照主鍵排序。

• 更新和 Hudi COW 一樣，是 file-level OCC，因此是 file-level concurrency。

• 寫入數據量是 delete mark 加新版本的 tuple，因此是 tuple-level update。

4. 讀取流程：需要 merge 一下 base file 和 log file，實現上是 base file 和 log file 按主鍵做 hash join。由於 log file 中的數據是無序的，即便通過 zone-map 過濾後只需要讀一個 base file 的 block，也要 join 整個 log file。

除了併發度比 Iceberg 高以外，Hudi MOR 和 Iceberg 主要有兩個區別。

第一個區別是 delete mark 的實現不同。

寫性能方面，Iceberg position delete < Hudi 主鍵 delete < Iceberg equation delete。

position delete < 主鍵 delete，是因爲 AP 數據庫的更新大多數情況下是提供了整行數據的 upsert，這種情況下，主鍵 delete 可以做到不需要去 base file 中讀數據，直接寫 log file 就搞定，而 position delete 還得去讀行號。

主鍵 delete < equation delete，這個顯而易見，equation delete 在根據非主鍵（唯一鍵）的等值刪除場景具有絕對的優勢。

讀性能方面，Iceberg position delete > Hudi 主鍵 delete > Iceberg equation delete。

因爲主鍵 delete 需要 base file 和 log file 做 hash join，得構建 hash table 和按行 probe。而 position delete 只需要按天然有序的行號歸併，因此更快。equation delete 需要每一行計算很多的等值條件，因此更慢。

第二個區別是同一主鍵的新老版本存儲位置不同。Hudi 能保證新老版本邏輯上在同一個 base file 中（在 base file 或者它對應的 log file 中），而 Iceberg 新版本可能出現在不同的 data file 中。相比之下，Iceberg 在實現主鍵行級別的索引，主鍵 zone-map 過濾方面出於劣勢。

綜合來看，沒有明顯的勝者，二者互有勝負。

Tuple-level concurrency + Field-level update

這類方案的唯一代表是 Kudu。一個數據庫自成一類。

這類數據庫非常重視單行更新，因此通過行鎖來實現併發，實現了 tuple-level concurrency。（注意：我不確定 Kudu 是否還支持表鎖，通過 cost 判斷該加表鎖還是行鎖。感興趣的讀者可以自行研究一下。）

這類數據庫非常「吝惜」存儲空間，因此更新時只記錄被更新的 field。

Kudu 的實現概述如下

1. 宏觀看有點像一個只有 L0 層的 LSM-tree，但 Kudu 對於寫入和更新分類處理。寫入和更新分別使用自己的 memtable 和文件。寫入寫到行存 MemRowSet（Masstree 實現），定期刷盤成爲 DiskRowSet 列存文件。更新寫到行存 DeltaMemStore，定期刷盤成爲 DiskRowSet 對應的 REDO records 文件。DiskRowSet 文件內嵌一個主鍵 B-tree 索引，用來加速主鍵點查。DiskRowSet 和 REDO records 文件會被週期性地合併。

2. 更新流程：先根據主鍵查詢在 DiskRowSet 中的行號，然後在 DeltaMemStore 中記錄行號以及更新後的 field。因爲只記了更新後的 field，有點像 redo log，所以文件名叫 REDO records。

• 通過行鎖來保證併發更新的事務性，所以是 tuple-level concurrency。

• 寫入的數據量只是更新後的 filed，所以是 field-level update。

4. 讀取流程：需要按行號順序地歸併 DiskRowSet 和 REDO records。

Kudu 的方案是我最喜歡的方案。這個方案寫併發高，寫放大最小。此外，field-level update 非常有利於大寬表的部分列更新場景，因爲不需要花費大量的 IO（每列一次 IO）去補全其他列數據。如果非要找出一個缺點，那就是行鎖對批量更新沒那麼友好。不過這也可以通過動態地選擇表鎖或者行鎖來優化。

Unlimited concurrency + tuple-level update

這類方案的典型代表是 Doris 和阿里雲 ADB。

我創造的 unlimited concurrency 這個術語有點唬人。其實這個術語翻譯成人話就是不支持併發更新的事務性——不加任何鎖，不檢測寫寫衝突，允許丟失更新（lost-update）。

比如 Doris，併發更新採用 last writer wins 策略，同一行的併發更新，後來的更新會覆蓋前面的更新，造成前面的更新丟失。

至於 ADB，我沒有看到 ADB 論文中提到併發更新，找官方文檔也沒找到（也有點迷路了，ADB 有很多版本，MySQL，Postgres 等等，弄暈我了），所以我猜測它也不支持併發更新的事務性，不然沒理由不高調宣傳。因此，我將 ADB 也歸類到了這裏。儘管我不能 100% 確定它屬於這個分類，但我認爲分類錯了也問題不大，它不影響本文的核心思想。

由於不支持更新的事務性，這類數據庫的單行更新和批量更新都比較快。

提問：犧牲事務性，換取更新的性能，你認爲值得嗎？歡迎留言討論。

Doris MOR(unique-key 表) 的實現方式概述如下：

1. 宏觀上看是一個 LSM-tree，只有 memtable 和 L0 層列存文件。

2. 更新流程：採用 LSM-tree 的做法，直接寫入新版本，覆蓋舊版本。

• 每個版本上帶着一個 sequence number，作爲版本排序的依據。

• Doris 默認不支持併發更新（官方文檔）。如有需求，可以通過開關打開，但會有丟失更新的異象。因爲不支持併發更新的事務性，所以我把 Doris 劃分爲 unlimited concurrency。

• 寫入數據量只是一個 tuple，所以是 tuple-level update。

4. 讀取流程：需要 merge 多個文件以及 memtable 來找到同一主鍵的最新版本。

拋開對併發更新事務性的支持不談，Doris MOR 方案的優點是更新非常快。甚至寫入不需要關心是否違反主鍵唯一約束，因爲同一主鍵的新版本總會覆蓋舊版本，保證了絕對的唯一。此外，在提供整行數據的 upsert 場景，Doris 也不需要讀老版本數據，直接寫新版本就可以搞定。Doris MOR 的缺點是讀取的並行度不高，無法做到 file-level 獨立並行讀。因爲文件之間存在依賴，需要多個文件合併到一起，才能找到最新版本的數據。在這個限制下，聚合函數無法下推到文件層並行計算，讀性能比較差。

ADB 的實現概述如下：

1. 宏觀看存儲是兩個結構：磁盤上的列存文件（detail file）和內存中的 delete bitmap。delete bitmap 被切分成很多 compressed segment。

2. 更新流程：update 看做 delete + insert。先在 delete bitmap 標記刪除老版本（把刪除行的對應 bit 置 1 表示刪除），然後寫入新版本。

• delete bitmap 自身的更新通過 segment-level COW 實現，有一定的內存空間開銷。

• 疑似不支持併發更新的事務性，所以我把它劃分到 unlimited concurrency。

• 寫入的數據量是內存 bitmap 的一個 compressed segment，以及磁盤上的一個 tuple。因爲我重點關注磁盤的寫入量，所以這個方案被分類爲 tuple-level update。

4. 讀取需要 merge 列存文件和對應的 delete bitmap segments。

ADB 方案最特別之處在於 in-memory delete bitmap，優點是標記刪除的讀寫性能都很棒，畢竟內存數據結構的威力不可小覷。缺點是內存開銷比較大。

相比與 Doris，ADB 可以實現文件級別甚至更細粒度的並行讀。雖然同一主鍵的新老版本也可能會出現在不同的文件中，但每個文件有自己的 delete bitmap，可用來過濾被刪除的數據。每個文件都知道自己的數據要麼是新版本的，要麼是被刪除的，不依賴別的文件來確定，所以可直接並行讀。

In-memory delete bitmap + segment-level COW 的內存開銷很大。一種優化的思路是將其轉化爲 on-disk bitmap。Hologres 就採用了 on-disk bitmap 的方案，每個文件一個 delete bitmap（roaring bitmap 實現），存儲在整張表一個的 LSM-tree 中。爲了省空間，delete bitmap 的更新不是通過 COW 來實現，而是通過 MOR 來實現，即每個增量更新都會生成一個新版本的 bitmap，讀的時候合併所有版本。感興趣的可以閱讀下 Hologres 的論文。更進一步地，Doris MOW(merge on write) 表在 Hologres 方案的基礎上，爲了減小合併多個 bitmap 的開銷，還會把合併後的結果緩存起來，詳情可以參考 Doris MOW 的設計文檔。

總結

s1aWo4

碼字不易。如果您覺得我的文章對您有幫助，辛苦點贊收藏轉發下，這是對我莫大的鼓勵，非常感謝！

參考

1. https://www.dremio.com/blog/

2. https://hudi.apache.org/docs/concepts/

3. https://kudu.apache.org/kudu.pdf

4. https://cwiki.apache.org/confluence/display/DORIS

5. https://www.vldb.org/pvldb/vol12/p2059-zhan.pdf

6. https://kai-zeng.github.io/papers/hologres.pdf

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/Uq2Y0GVTIXG4tkzyk8km2g