作者：張晨 SelectDB 資深研發工程師

在實時資料倉庫的業務場景中，能夠友好支援資料的實時更新是一個非常重要的能力。例如在資料庫同步（CDC）、電商交易訂單、廣告效果投放、營銷業務報表等業務場景中，面對上游資料的變化，通常需要快速獲取到變更記錄並針對單行或多行資料進行及時變更，保證業務分析師及相關分析平臺能快速捕捉到最新進展，提升業務決策的及時性。

而對於一貫不擅長資料更新的 OLAP 資料庫而言，如何更好實現實時更新的能力，在資料時效性要求愈發強烈以及實時數倉業務應用範圍愈加廣闊的今天，成為了贏得激烈競爭的關鍵。

在過去 Apache Doris 主要通過 Unique Key 資料模型來實現資料實時 Upsert，因底層採取了類似 LSM Tree 結構，對於大資料量的高頻寫入具有足夠強勁的支撐，但由於採取了 Merge on Read 的更新模式，因此讀取效率成了制約 Apache Doris 發揮實時更新能力的瓶頸，在應對實時資料的並行讀寫時可能引發查詢抖動問題。

基於此，在 Apache Doris 1.2.0 版本中，我們在 Unique Key 模型上引入了全新的資料更新方式 Merge-On-Write，力求在實時更新和高效查詢間得到統一。本文將詳細介紹全新主鍵模型的設計實現以及效果。

原 Unique Key 模型的實現

瞭解 Apache Doris 歷史的使用者可能知道，Doris 最初的設計是受 Google Mesa 啟發，最初只有 Duplicate Key 模型和 Aggregate Key 模型，而 Unique Key 模型是在 Doris 發展過程中根據使用者的需求而增加的。但那時實時更新的需求並沒有這麼強，Unique Key ****的實現也相對比較簡單——只是將 Aggregate Key 模型做了一層包裝，並沒有針對實時更新的需求進行深度優化。

具體而言，Unique Key 模型的實現僅是 Aggregate Key 模型的一個特例，如果使用 Aggregate Key 模型，並將所有非 Key 列的聚合型別都設定為 REPLACE，則可以實現完全相同的效果。如下圖所示，對一個 Unique Key 模型的表example_tbl進行 desc，最後一列的聚合型別顯示它等價於所有列都是 REPLACE 聚合型別的 Aggregate Key 表。

Unique Key 資料模型和 Aggregate Key 資料模型都是 Merge- O n-Read 的實現方式，也就是說資料在匯入時先寫入一個新的 Rowset，寫入後並不會執行去重，只有在發起查詢時才會做多路併發排序，在進行多路歸併排序時，會將重複的 Key 排在一起，並進行聚合操作，其中高版本 Key 的會覆蓋低版本的 Key，最終只返回給使用者版本最高的那一條記錄。

下圖是一個簡化後的 Unque Key 模型執行過程表示：

雖然其實現方式較為一致，但是 Unique Key 和 Aggregate Key 資料模型的使用場景有明顯的差異：

• 使用者在建立 Aggregate Key 模型的表時，對於聚合查詢的條件是非常明確的——按照 Aggregate Key 指定的列進行聚合，Value 列上的聚合函式就是使用者主要使用的聚合方法（COUNT/SUM/MAX/MIN 等），例如將 user_id 作為 Aggregate Key，將訪問次數和時長進行 SUM 聚合來計算 uv 和使用者使用時長。

• 但 Unique Key 資料模型的 Key 的主要作用其實是保證唯一性，而不是作為聚合的 Key。例如在訂單場景中，通過 Flink CDC 從 TP 資料庫同步過來的資料，是以訂單 ID 作為 Unique Key 來進行去重的，但查詢的時候通常是對某些 Value 列（例如訂單狀態，訂單金額，訂單耗時，下單時間等）進行過濾、聚合和分析。

不足之處

以上可知，使用者使用 Unique Key 模型進行查詢的時候，實際上是進行了兩次聚合操作，第一次是按照 Unique Key 進行全部資料的逐 Key 聚合，去除掉重複的 Key；第二次是按照查詢真正需要的聚合條件進行聚合。而這兩次聚合的操作就帶來了比較嚴重的效率問題，導致查詢效能低下：

1. 資料去重需要執行代價很高的多路歸併排序，全量 Key 的比較非常消耗 CPU 的計算資源。

2. 無法進行有效的資料裁剪，引入大量額外的資料 IO。例如某個資料分割槽有 1 千萬條資料，但是符合篩選條件的資料只有 1000 條， OLAP 系統豐富的索引就是用來高效地篩選出這 1000 條資料的。但由於無法確定具體檔案裡某條資料的值是否有效，使得這些索引派不上用場，必須先全部進行一次歸併排序並對資料進行去重之後，才能對這些最終確認有效的資料進行過濾。這就帶來了約 1 萬倍的 IO 放大（這一數字僅為粗略的估計，實際的放大效應計算起來更為複雜）。

方案調研與選型

為了解決原 Unique Key 模型存在的問題，以更好的滿足業務場景的需求，我們決定對 Unique Key 模型進行優化，針對讀寫效率問題的優化方案展開了詳細的調研。

關於以上問題的解決方案，業內已經有了較多的探索。代表性的有三類：

1. Delete + Insert。即在資料寫入時通過一個主鍵索引查詢到被覆蓋的 key，將其標記為刪除。比較有代表性的系統是微軟的 SQL Server。

2. Delta Store。將資料分為base data和 delta data，base data中的每一個主鍵都保證唯一，所有更新都記錄在 Delta Store中，查詢時將 base data 和 delta data 進行merge同，時有後臺的 merge 執行緒定期將 delta data和 base data進行合併。比較有代表性的系統是 Apache Kudu。

3. Copy-on-Write。在更新資料時直接將原來的資料整行拷貝、更新後寫入新檔案。資料湖採用這類方式的比較多，比較有代表性的系統是 Apache Hudi 與 Delta Lake。

具體三類方案的實現機制及對比如下：

Delete + Insert ( 即 Merge-on-Write)

比較有代表性的是 SQL Server 在 2015 年 VLDB 上發表的論文《Real-Time Analytical Processing with SQL Server》中提出的方案。簡單來說，這篇論文提出了資料寫入時將舊的資料標記刪除（使用一個 Delete Bitmap 的資料結構），並將新資料記錄在 Delta Store 中，查詢時將 Base 資料、Delete Bitmap、Delta Store 中的資料 Merge 起來以得到最新的資料。整體方案如下圖所示，由於篇幅限制就不展開進行介紹了。

這個方案的優勢在於，任何一個有效的主鍵只存在於一個地方（要麼在 Base Data 中，要麼在 Delta Store 中），這樣就避免了查詢過程中的大量歸併排序的消耗，同時 Base 資料中的各種豐富的列存索引也仍然有效。

Delta Store

Delta Store 的方式比較有代表性的系統就是 Apache Kudu。在 Kudu 中，資料分為 Base Data 和 Delta Data，Base Data 中的主鍵都是唯一的，任何對於 Base 資料的修改會先寫入 Delta Store 中（通過行號標記與 Base Data 中的對應關係，這樣可以避免 Merge 時的排序）。與前面 SQL Server 的 Base + Delta 不同的是，Kudu 沒有標記刪除，所以同一個主鍵的資料會存在於兩個地方，所以查詢時必須將 Base 和 Delta 的資料合併才能得到最新的結果。Kudu 的方案如下圖所示：

https://www.slideshare.net/cloudera/apache-kudu-technical-deep-dive

Kudu 這套方案也能避免讀取資料時的歸併排序所帶來的高昂代價，但是由於一個主鍵的資料會存在於多個地方，它就難以保證索引的準確性，也無法做一些高效的謂詞下推。而索引和謂詞下推都是分析型資料庫進行效能優化的一個重要手段，這個缺點對於效能影響還是挺大的。

Copy-On-Write

由於 Apace Doris 定位是一個實時分析型資料庫，Copy On Write 方案對於實時更新來說成本太高，並不適合 Doris。

方案比較

下面的表格對比了各個方案，其中 Merge-On-Read 是 Unique Key 模型的預設實現，即1.2版本之前的實現方式，Merge-On-Write（寫時合併）即前面提到的 Delete + Insert 方案。

如上可知，Merge-On-Write 付出中等的寫入代價，換取了較低的讀取成本，對謂詞下推、非 key 列索引過濾均能友好支援，並對查詢效能優化有較好的效果。綜合對比後，我們選擇了 Merge-On-Write 作為最終的優化方案。

新版方案的設計與實現

簡單來講，Merge-On-Write 的處理流程是：

1. 對於每一條 Key，查詢它在 Base 資料中的位置（rowsetid + segmentid + 行號）

2. 如果 Key 存在，則將該行資料標記刪除。標記刪除的資訊記錄在 Delete Bitmap中，其中每個 Segment 都有一個對應的 Delete Bitmap

3. 將更新的資料寫入新的 Rowset 中，完成事務，讓新資料可見（能夠被查詢到）

4. 查詢時，讀取 Delete Bitmap，將被標記刪除的行過濾掉，只返回有效的資料

關鍵問題

設計適合 Doris 的 Merge-On-Write方案，需要重點解決以下幾個問題：

1. 匯入時如何高效定位到是否存在需要被標記刪除的舊資料？

2. 標記刪除的資訊如何進行高效的儲存？

3. 查詢階段如何高效的使用標記刪除的資訊來過濾資料？

4. 能否實現多版本支援？

5. 如何避免併發匯入的事務衝突，匯入與 Compaction 的寫衝突？

6. 方案引入的額外記憶體消耗是否合理？

7. 寫入代價導致的寫入效能下降是否在可接受範圍內？

根據以上關鍵問題，我們進行了一系列優化措施，使得以上問題得到較好的解決。 下 文中我們將進行詳細介紹：

主鍵索引

由於 Doris 是面向大規模分析設計的列存系統，並沒有主鍵索引的能力，因此為了能夠快速定位到有沒有要覆蓋的主鍵，以及要覆蓋的主鍵的行號，就需要給 Doris 增加一個主鍵索引。

我們採取瞭如下的優化措施：

1. 為每個 Segment 維護一個主鍵索引。主鍵索引的實現採用了似於 RocksDB Partitioned Index 的方案。該方案能夠實現非常高的查詢 QPS，同時基於檔案的索引方案也能夠節省記憶體佔用。

2. 為每個 Segment 維護一個主鍵索引對應的 Bloom Filter。當 Bloom Filter 命中時才會查詢主鍵索引。

3. 為每個 Segment 記錄一個主鍵的區間範圍 [min-key, max-key]

4. 維護一個純記憶體的區間樹，使用所有 Segment 的主鍵區間構造。在查詢一個主鍵時，無需遍歷所有的 Segment，可以通過區間樹定位到可能包含該主鍵的 Segment，大幅減少需要查詢的索引量 。

5. 對於命中的所有 Segment，按照版本從高到低進行查詢。在 Doris 中高版本意味著更新的資料，因此如果一個主鍵在高版本的 Segment 索引中命中，就無需繼續查詢更低版本的 Segment 。

查詢單個主鍵的流程如下圖所示：

Delete Bitmap

Delete Bitmap 採取多版本的方式進行記錄，具體如下圖所示：

• 圖中的 Segment 檔案是由版本 5 的匯入產生的，包含了該 Tablet 中版本 5 的匯入資料

• 版本 6 的匯入中包含了對主鍵 B 的更新，因此會在 Bitmap 中將第二行標記刪除，並在 DeleteBitmap 中記錄版本 6 的匯入對該 Segment 的修改

• 版本 7 的匯入包含了對主鍵 A 的更新，也會產生一個對應版本的 Bitmap；同理版本 8 的匯入也會產生一個對應的 Bitmap

所有的 Delete Bitmap 儲存在一個大的 Map 中，每次匯入都會將最新的 Delete Bitmap 序列化到RocksDB 中。其中關鍵定義如下：

using SegmentId = uint32_t;
using Version = uint64_t;
using BitmapKey = std::tuple<RowsetId, SegmentId, Version>;
std::map<BitmapKey, roaring::Roaring> delete_bitmap;

每個 Rowset 中的每個 Segment，都會記錄多個版本的 Bitmap。Version 為 x 的 Bitmap 意味著版本為 x 的匯入對當前 Segment 的修改。

多版本 Delete Bitmap 的優點：

1. 能很好的支援多版本的查詢，例如版本 7 的匯入完成後，一個該表的查詢開始執行，會使用 Version 7 來執行，即使這個查詢執行時間較長，在查詢執行期間版本 8 的匯入已經完成，也無需擔心讀到版本 8 的資料（或者漏掉被版本 8 刪除的資料）

2. 能夠很好的支援複雜的 Schema Change。在 Doris 中，複雜的 Schema Change（例如型別轉換）需要先進行雙寫，同時將某個版本之前的歷史資料進行轉換後再刪除掉舊版的資料。多版本的 Delete Bitmap 可以很好的支援當前的 Schema Change 實現

3. 可以支援資料拷貝和副本修復時的多版本需求

不過多版本 Delete Bitmap也有對應的代價，在剛才的例子中，訪問版本 8 的資料，需要將 v6、v7、v8 的三個 Bitmap Merge 在一起才能得出完整的 Bitmap，再用該 Bitmap 對 Segment 資料進行過濾。在實時高頻匯入場景中，很容易產生大量的 Bitmap，而 Roaringbitmap 的並集操作的 CPU Cost 很高，為了儘可能減少大量並集操作的影響，我們為 DeleteBitmap 增加了 LRUCache 來記錄最新合併過的 Bitmap。

寫入流程

寫入資料時會先建立每個 Segment 的主鍵索引，再更新 Delete Bitmap。主鍵索引的建立比較簡單，篇幅有限不再詳細描述，重點介紹一些比較複雜的 Delete Bitmap 更新流程：

1. DeltaWriter 會先將資料 Flush 到磁碟

2. 在 Publish 階段去批量的點查所有的 Key，並且更新被覆蓋的 Key 對應的 Bitmap。在下圖中，新寫入的 Rowset 版本是 8，它修改了 3 個 Rowset 中的資料，因此會產生 3 個 Bitmap 的修改記錄

3. 在 Publish 階段去更新 Bitmap，保證了批量點查 Key 和更新 Bitmap 期間不會有新增可見的Rowset，保證了Bitmap更新的正確性。

4. 如果某個 Segment 沒有被修改，則不會有對應版本的 Bitmap 記錄，比如 Rowset1 的 Segment1 就沒有 Version 8 對應的 Bitmap

讀取流程

Bitmap 的讀取流程如下圖所示，從圖片中我們可知：

1. 一個請求了版本 7 的 Query，只會看到版本 7 對應的資料

2. 讀取 Rowset5 的資料時，會將 v6 和 v7 對它的修改產生的 Bitmap 合併在一起，得到 Version7 對應的完整 DeleteBitmap，用來過濾資料

3. 在下圖的示例中，版本 8 的匯入覆蓋了 Rowset1 的 Segment2 一條資料，但請求版本 7 的 Query 仍然能讀到該條資料

在高頻匯入場景下，可能會存在大量版本的 Bitmap，合併這些 Bitmap 本身可能也有較大的 CPU 計算消耗。因此我們引入了一個LRUCache，每個版本的 Bitmap 只需要做一次合併操作。

Compaction 與寫衝突的處理

Compaction 正常流程

1. Compaction 在讀取資料時，獲取當前處理的 Rowset 的版本 Vx，會自動通過 Delete Bitmap 過濾掉被標記刪除的行（見前面的查詢層適配部分）
2. Compaction 結束後即可清理源 Rowset 上所有小於等於版本 Vx 的 DeleteBitmap

Compaction 與寫衝突的處理

1. 在 Compaction 的執行過程中，可能會有新的匯入任務提交，假設對應版本為 Vy。如果 Vy 對應的寫入有對 Compaction 源 Rowset 中的修改，則會更新到該 Rowset 的 DeleteBitmap 的Vy中
2. 在 Compaction 結束後，檢查該 Rowset 上所有大於 Vx 的 DeleteBitmap，將它們中的行號更新為新生成的 Rowset 中的 Segment 行號

如下圖所示，Compaction 選擇了[0-5], [6-6], [7-7]三個 Rowset， 在 Compaction 過程中，Version8 的匯入執行成功，在 Compaction Commit 階段，需要處理由 Version8 的資料匯入所生成的新 Bitmap

寫入效能優化

在最初設計時，DeltaWriter 不在寫入資料階段進行點查和 Delete Bitmap 更新，而是在 Publish 階段做，這樣能保證 Delete Bitmap 更新時可以看到該版本之前所有的資料，保證 Delete Bitmap 的正確性。但是在實際的高頻匯入測試中發現，Publish 階段序列對每個 Rowset 的資料進行全量點查和更新時，所引入的額外消耗會使得匯入吞吐出現較大幅度下降。

因此在最終設計中，我們將 Delete Bitmap 的更新改成兩階段的形式：第一階段可以並行執行，只查詢和標記刪除當時能看到的 Version；第二階段必須序列執行，將此前第一階段可能漏查的新匯入的 Rowset 中的資料再更新一遍。第二階段增量更新資料量很少，因此對整體的吞吐影響非常有限。

優化效果

新的 Merge-On-Write 實現通過在寫入的時候將舊的資料標記刪除的方式，能夠始終保證有效的主鍵只會出現在一個檔案中（即在寫入的時候保證了主鍵的唯一性），不需要在讀取的時候通過歸併排序來對主鍵進行去重，這對於高頻寫入的場景來說，大大減少了查詢執行時的額外消耗。

此外，新版實現還能夠支援謂詞下推，並能夠 很好 利用 ****Doris 豐富的索引，在資料 ********IO 層面就能夠進行充分的資料裁剪，大大減少資料的讀取量和計算量，因此在很多場景的查詢中都有比較明顯的效能提升 。

需要注意的是，如果使用者使用 Unique Key 的場景都是低頻的批量更新，則 Merge-On-Write 實現對於使用者查詢效果的提升不一定明顯，因為對於低頻的批量更新，Doris 的 Compaction 機制通常就能夠較快的將資料給 Compact 到比較好的狀態（也就是說 Compaction 完成了主鍵的去重），避免了查詢時的去重計算代價。

對於聚合分析的優化效果

我們使用 TPC-H 100 中資料量最大的 Lineitem 表進行了測試，為了模擬出多個持續寫入的場景，將資料切分了 100 份，並進行了 3 次的重複匯入。之後進行了 count(*)的查詢，效果對比如下：

分別對比了無 Cache 和有 Cache 的情形，在無Cache 的情況下由於從磁碟載入資料的耗時較多，整體上有大約4倍的效能提升；而排除掉磁碟讀取資料的開銷影響，在有Cache 的情況下新版實現的計算效率能夠有20多倍的效能提升。

Sum 的效果類似，篇幅有限就不再列舉。

SSB Flat

除了簡單的 Count 和 Sum，我們還對 SSB-Flat 資料集進行了測試，在 100G 資料集（切分成 10 份，多次匯入來模擬有資料更新的場景）上的優化效果如下圖所示：

關於測試結果的說明：

• 在 32C64GB 的典型配置下，所有查詢跑完的總耗時，在新版實現上是 4.5 秒，舊版實現為 126.4 秒，速度相差近 30倍。進一步分析，我們發現在舊版實現的表上的查詢執行時，32核CPU全部打滿。因此更換了配置更高的機型來測試計算資源充足時舊版實現的表上的查詢耗時

• 在 64C128GB 的配置下，舊版實現總耗時 49.9s，最高約跑滿了48 個核。在計算資源充足的情況下，舊版實現仍然與新版實現有12倍的效能差距

由此可見，新版實現不僅大大提升了查詢速度，而且能夠顯著減少 CPU 的消耗。

對資料匯入的影響

新版的 Merge-On-Write 實現主要是為了優化資料的查詢效能，如前所述也取得了不錯的效果。不過這些優化效果是通過在寫入時做了一些額外工作換取的，因此，新版 Merge-On-Write 實現會使得資料匯入效率有小程度的變慢，但由於存在併發並且多個批次之間的匯入可以形成 Pipeline 的效應，整體的吞吐沒有明顯的下降

使用方式

在 1.2 版本中，作為一個新的 Feature，寫時合併預設關閉，使用者可以通過在建表時新增下面的 Property 來開啟：

“enable_unique_key_merge_on_write” = “true”

另外新版本 Merge-on-Write 資料更新模式與舊版本 Merge-on-Read 實現方式存在差異，因此已經建立的 Unique Key 表無法直接通過 Alter Table 新增 Property 來支援，只能在新建表的時候指定。如果使用者需要將舊錶轉換到新表，可以使用 insert into new_table select * from old_table 的方式來實現。

未來的規劃

新版的 Merge-On-Write 實現能夠相容之前 Unique Key 的所有功能，包括條件更新（使用 Sequence 列在亂序寫入中保證資料更新的正確性）、通過 Delete Sign 進行批量刪除、Schema Change、UPDATE 語句等。

從使用者的反饋來看，Unique Key 模型目前對如下幾個需求的支援水平還需要進一步提升，這也是我們下一步工作的重點：

1. 部分列更新。 目前 Unique Key主要支援的是 Upsert 操作（也就是整行更新），暫時不支援 Update操作（也就是每次只更新一部分列的資料）。但在訂單、畫像等場景中，存在大量的需求，需要頻繁且實時的更新一部分狀態列，當前只能通過 Aggregate Key 模型的 REPLACE_IF_NOT_NULL功能來實現部分列更新。未來在 Doris 1.3 版本中，我們計劃支援完整的 Unique Key 模型的部分列更新。

2. 提高點查效能。 Doris 採用的是列式儲存，資料按列組織，列存系統天然在大規模資料分析中具有優勢，在按行點查上存在劣勢（因為一次讀取一行需要進行 N 次磁碟檔案的訪問，相比行存系統來說存在非常大的 IO 放大問題）。隨著 Doris 在訂單、畫像等對實時資料更新有強需求的領域的廣泛使用，越來越多的使用者提出了希望 Doris 支援高效能點查，以替代 HBase 等系統，來簡化運維。這方面我們已經有了初步方案，正在開發中，預計在 2023 年上半年的新版本中可以釋出。

目前 Apache Doris 1.2 版本已經發布，歡迎大家下載使用！新版本特性全面瞭解：全面進化！Apache Doris 1.2.0 Release 版本正式釋出｜版本通告，也歡迎有興趣的開發者可以一起參與到社群的開發中。