TiFlash 原始碼閱讀（五） DeltaTree 儲存引擎設計及實現分析 - Part 2

語言: CN / TW / HK
時間 2022-07-21 03:16:31
主題:

本文作者：施聞軒，TiFlash 資深研發工程師

背景

在 Part1 中我們主要對 DeltaTree 引擎的結構和寫入相關流程進行了介紹。本文對讀取流程進行介紹。若讀者尚未閱讀過 Part1 ，需要先閱讀 Part1 文章瞭解前置知識。

本文基於寫作時最新的 TiFlash v6.1.0 設計及原始碼進行分析。隨著時間推移，新版本中部分設計可能會發生變更，使得本文部分內容失效，請讀者注意甄別。TiFlash v6.1.0 的程式碼可在 TiFlash 的 git repo 中切換到 v6.1.0 tag 進行檢視。

讀

如 Part1 所述，寫入時，DeltaTree 引擎形成的結構如下：

資料首先在值域範圍上進行切分，分成了多個不同的 Segment，然後在時域範圍上進行切分，按照新老資料分為 Stable 層（絕大多數資料）和 Delta 層（剛寫入的資料）。其中，Delta 層又分為磁碟上的資料和記憶體中的 MemTable 資料。定期的 Flush 的機制會將記憶體資料寫入到磁碟中。

如果想了解這個結構的詳細情況，請參見 Part1 。

若要從這樣的結構中依次掃描資料，那麼需要對每個 Segment 的 Stable、磁碟上的 Delta 層、記憶體中的 MemTable 資料這三部分資料進行聯合掃描：

對 LSM Tree 比較熟悉的讀者會發現，單個 Segment 內類似於一個 2 層 LSM Tree，由於兩層的值域是重疊的，因此需要同時讀取，並結合 MVCC 版本號，以便得到一個最終結果。

快照讀

在實際實現中，TiFlash 並非直接對這三塊資料直接進行讀取，而是首先為它們構建快照，然後基於快照進行讀取。快照是一種抽象概念，被「快照」下來的資料在讀取的時候永遠不會發生變化，即使實際資料由於發生了並行寫入發生了變更。

快照讀機制提供了以下好處：

  • 可以提供一定的 ACID 隔離（快照隔離級別），例如不會讀出寫到一半的資料

  • 長時間的讀和寫不會互相阻塞，可以同時進行，對於讀大量資料的場景比較友好

從邏輯上來說，在讀之前拿個鎖阻塞寫、並複製一遍資料，就可以以最簡單的方式實現快照。但顯而易見的是，複製資料是一個非常耗時的操作（例如考慮要掃 1TB 資料）。以下詳細分析 TiFlash 各個部分資料是如何實現高效能快照的。

MemTableSet 的快照

對於 MemTable 中的 ColumnFileInMemory 資料，TiFlash 通過複製 Block 資料區指標的方式實現“快照”，不會複製它所包含的 Block 資料內容：

c++ for (const auto & file : column_files) { if (auto * m = file->tryToInMemoryFile(); m) { snap->column_files.push_back(std::make_shared<ColumnFileInMemory>(*m)); } else { snap->column_files.push_back(file); } total_rows += file->getRows(); total_deletes += file->getDeletes(); }

注意，快照後的 ColumnFileInMemory 實際上與被快照的 ColumnFileInMemory 共享了相同的 Block 資料區域，而 ColumnFileInMemory 資料區是會隨著新寫入發生變更的。因此這個 ColumnFileInMemory “快照”並不保證後續讀的時候不會遇到新資料，不是一個真正意義上的快照。在讀過程中，TiFlash 還額外進行了 TSO 的過濾來規避這些後續可能新寫入的資料。

磁碟上 Delta 層資料的快照

對於 ColumnFilePersistedSet，其各個 ColumnFile 的資料通過 PageStorage 儲存在了磁碟中。這些資料是 immutable 的，不會隨著新寫入發生修改，因此直接複製 ColumnFile 結構體指標（std::shared_ptr）、對其引用計數進行更新即可。

磁碟上 Stable 層資料的快照

在 Part1 中我們可以瞭解到 Stable 層的資料也是 immutable 的：整個 Stable 層的資料檔案不會被更改，只會在 Merge Delta 等過程中被整體替換成一個新的檔案。因此與 Delta 層資料類似，Stable 層也是通過智慧指標追蹤引用計數、直接增加引用即可。

通過這些分析大家可以發現，TiFlash 中的快照過程是非常輕量的，基本上都僅僅涉及到指標複製和引用計數的更新，因此其效率非常高。

Scan 實現

Scan 是各個 AP 分析引擎最重要的讀操作，TiFlash 也不例外。TiFlash 中 Scan() 實現的語義為：給定一個主鍵區間，流式地、按順序地返回在這個區間內指定列的所有資料。

TiFlash 的 Scan 是三個流（Stream）的組合：

  • 最底層 DeltaMergeBlockInputStream：返回合併自 MemTableSet、磁碟上的 Delta 層、磁碟上的 Stable 層這三個來源的資料流。這個流返回的資料是有序的，一定按照 (Handle, Version) 升序排列，但並不保證返回的資料一定符合給定的區間範圍。

  • DMRowKeyFilterBlockInputStream：依據 Handle 列的範圍進行過濾並返回

  • DMVersionFilterBlockInputStream：依據 Version 列的值進行 MVCC 過濾

DeltaMergeBlockInputStream

這個流有序地返回 MemTable、Delta、Stable 三層資料。在 Part1 中我們介紹過，MemTable 中可能存在多個值域重疊的 ColumnFileInMemory（每個 ColumnFile 內部是有序的），而 Delta 中也可能存在多個值域重疊的 ColumnFileTiny，Stable 層則比較簡單，只有一個 DMFile，且內部是有序的。

以下邊的圖片為例，假設 MemTable、Delta、Stable 中各自有一些資料，我們期望 DeltaMergeBlockInputStream 返回的結果如圖中最右側紅色表格所示：

由此可見，這個流本質是，對於多個有序流返回一個有序的合併後的流。這是一個標準的 K 路歸併問題（K-way Sort Merge），這也正是很多 LSM Tree 儲存引擎（如 RocksDB）等對於 N 層有序資料進行 Scan 的實現方式。K 路歸併的流可以通過一個最小堆實現：

  1. 從各個底層流中取一行，放入最小堆中

  2. 從最小堆中取出當前最小的這一行（這一行一定是步驟 1 中各行裡最小的），作為流輸出的第一行

  3. 從取走行的流中補充一行到最小堆中

  4. 重複步驟 2

K 路歸併實現簡單、使用廣泛，但它也存在一些問題：

  • 無論讀哪一列，都需要依據 Sort Key 作為最小堆的排序依據，換句話說 Sort Key 列總是需要被讀出來，哪怕它並不是使用者所請求的資料列

  • 基於堆的演算法只能以行為單位處理，有較多的分支判斷，無法充分利用 CPU 流水線

TiFlash 中這個流並沒有採用 K 路歸併的方式實現，而是採用了業界比較新的 Positional Index 方式。與 K 路歸併不同的是，Positional Index 並不是基於 Sort Key 進行排序合併，而是基於各個記錄的下標位置（即 Positional 名稱的來源）進行差分合並。

TiFlash 在寫入的時候並不會更新 Positional Index，而是在讀取的時候按需更新，這使得 TiFlash 得以維持高頻寫入效能。Positional Index 結構及演算法比較複雜，後續的原始碼解讀章節會單獨涵蓋，因而本文不作詳細展開。感興趣的讀者也可以自行閱讀 DeltaIndex.h 瞭解詳細實現。

DMRowKeyFilterBlockInputStream

這個流會按照給定的 Handle 列範圍對資料進行過濾。在 TiFlash 的實現中，雖然在從 Stable 讀資料的時候也會指定讀取的 Handle Range，但這個 Range 最終對映為了 Pack，返回的是以 Pack 為單位的流資料，因此還需要通過這個流對資料範圍進行進一步準確地限定。

DMVersionFilterBlockInputStream

這個流的目的是實現 MVCC 過濾，下圖展示了這個流的基本工作：接受一組包含 Version 及 Handle 列的資料（按 Handle, Version 排序），Handle 列可能存在多個 Version，並給定一個 MVCC 版本號，按序返回各個 Handle 不超過這個版本號最大的版本行。

由於整體資料是按 Handle, Version 有序排列的，因此這個流的演算法比較簡單，這裡也不做詳細展開，感興趣的讀者可以閱讀 DMVersionFilterBlockInputStream.h。

「」