HTAP 資料庫“必修課”：PolarDB-X Online Schema Change

作者：墨城

引言

關系型資料庫，随着業務發展，經常需要加表加列來滿足新的業務需求，或者增加索引以提升查詢性能，這些操作都需要通過資料定義語言 (Data Definition Language, DDL) 來完成。

DDL 是結構化查詢語言(Structured Query Language, SQL) 的一部分，1974 年 IBM 研究人員設計 SQL 的前身 Sequel 時有兩個目标，允許使用者通過 Sequel 來操縱和定義資料。當時發表的兩篇論文，一篇是廣為人知的 "SEQUEL: A Structured English Query Language"，介紹如何查詢和修改資料，另一篇則專門介紹了 DDL1,2，可以看出，從一開始 DDL 就是 SQL 最重要的組成部分。

随後的幾十年中，學術界對 DDL 要解決的核心問題“模式演化”(Schema Evolution) ，也就是“不丢失資料内容的前提下，改變資料的定義”，進行了大量研究3,4。如今 Schema Evolution 相關研究的結果已經廣泛應用在關系型、對象、文檔資料庫産品中，其中 Online Schema Change 能力已經成為 OLTP 資料庫的标準配置，主流單機 OLTP 資料庫都有自己的實作。

Online Schema Change

關系型資料庫中資料以表為機關存儲，讀寫操作依賴表的模式(Schema)和資料(Data)。DDL 通常需要同時修改模式和資料，為了避免并發問題，早期的資料庫實作會在 DDL 過程中禁止目标表上的讀寫操作（簡稱鎖表）。鎖表保證了對模式和資料的修改是原子操作。但某些 DDL 操作涉及複制資料（比如索引建構）執行時間可能在幾分鐘甚至數小時。OLTP 資料庫中長時間鎖表會對業務産生不可預知的影響，生産環境中不可接受，是以“能夠與讀寫操作并行執行”是 OLTP 使用者對 DDL 的核心需求，也是 Online Schema Change 要解決的問題。

單機資料庫

MySQL 從 5.6 版本開始提供 Online Schema Change(Online DDL)5 特性，允許大多數 DDL 語句與 DML 并行執行。DDL 執行分為 Initialization, Execution, Commit Table Definition 三個階段，通過 MDL(Metadata Lock)6 保護中繼資料，下面以 CREATE INDEX 為例簡單介紹 MySQL Online DDL 的實作。

Initialization 階段主要分析 DDL 語句，确定執行政策，過程中會持有目标表上的 shared MDL；
Execution 階段會擷取 exclusive MDL，等待目前表上的事務結束後完成建立 RowLog 等準備工作。之後降級為 shared MDL，允許讀寫操作并行執行，新事務中涉及索引的變更寫入 RowLog，RowLog 切分為多個小塊，增量資料始終寫入最後一塊。同時開始索引建構流程，将全量資料排序後填充到索引中。全量填充完成後按順序應用RowLog，應用最後一塊 RowLog 時禁止目标表上的寫入操作；

HTAP 資料庫“必修課”：PolarDB-X Online Schema Change

Commit Table Definition 階段再次擷取 exclusive MDL，完成中繼資料更新後釋放 MDL，流程結束，索引對查詢可見。

MySQL Online DDL 的特點

Schema 隻有一個版本，通過 MDL 保證同一時刻運作的事務都使用相同的中繼資料；
僅在幾個關鍵時間點加鎖，降低對上層應用的影響；

- Execution 初期和 Commit 階段短暫擷取 exclusive MDL，禁止目标表上的讀寫操作
- Execution 階段應用最後一塊 RowLog 時，禁止目标表上的寫操作

需要注意的是 MDL 作為一種鎖的實作，通過隊列來保證公平性，是以額外實作了死鎖檢測功能解決死鎖問題。

分布式資料庫

問題

分布式資料庫通常是一個叢集，出于性能考慮，每個節點需要緩存一份 Schema。如果繼續采用單機資料庫的 DDL 流程，則需要通過分布式鎖來保證加載新版本 Schema 過程中沒有讀寫操作進行，代價極高，并且當叢集内節點不能夠互相感覺時将變為無法完成的任務。

讨論解決方案之前，以 CREATE INDEX 為例，看看叢集節點使用不同版本 Schema 執行讀寫操作，帶來的具體問題。

上圖展示的是一個存儲計算分離架構的分布式資料庫，叢集由 CN(計算節點) 和 DN(存儲節點) 構成，每個 CN 中緩存一份 Schema。由于 CN0 和 CN1 異步加載 Schema，添加索引過程中可能存在一個時刻，CN0 認為有索引而 CN1 認為沒有，此時産生兩種異常：

索引上有多餘資料(Orphan Data Anomaly): CN0 執行了 INSERT，在表和索引上插入資料，随後 CN1 執行 DELETE。由于 CN1 認為沒有索引，僅删除了表上的資料；
索引上缺少資料(Integrity Anomaly): CN1 執行 INSERT，由于 CN1 認為沒有索引，僅在表上插入資料，沒有寫相關的增量日志，導緻索引建立完成後缺少這次 INSERT 的資料。

可以看到，如果同一時刻存在兩個 Schema 版本的情況無法避免，繼續沿用單機資料庫一步完成 Schema 版本切換的方案，會導緻資料問題。那麼如果“一步”切換不可行，“多步”能否解決問題？VLDB 2013 上 Google 工程師給出了一種新的 Schema Change 流程，通過增加兩個中間狀态來解決這個問題7。

解決方案 & 業界實作

Google F1 的方案引入了兩個中間狀态，delete_only 狀态的對象上僅執行删除操作，write_only 狀态的對象上支援寫入，但不允許讀取。依然以 CREATE INDEX 為例：

解決 Orphan Data Anomaly：CN0 認為索引處于 delete_only 狀态，僅在表上插入資料，CN1 認為沒有索引，僅在表上删除資料。最終索引和表上都沒有 id = 0 的資料；
解決 Integrity Anomaly：CN1 認為索引處于 delete_only 狀态，僅在表上插入資料，沒有寫相關的增量日志，但由于還有節點沒有更新到 V2 版本，資料回填沒有開始。當所有節點都更新 V2 版本後，資料回填操作會在索引中填入這一條資料。

以上兩個具體場景為例，說明了方案的有效性，論文7中對整體問題和方案做了形式化證明，網上有不少資料，團隊同學之前也有過分享8，這裡不再展開，隻列舉結論。

Google F1 的方案，包含兩個關鍵點：

增加兩個中間狀态(delete_only，write_only)，允許叢集中的事務同時使用至多兩個最近的中繼資料版本；
增加租約(lease)的概念，保證在一個租約周期内，沒有拿到最新版本 Schema 的節點，無法送出事務。

第一個關鍵點，将保證 Schema Change 正确性的條件，從“隻能有一個版本”，降低為“最多可以有兩個版本”。第二個關鍵點，給出了 F1 系統“保證最多兩個版本”的實作思路。

簡單來說，Google F1 的方案，成功将問題“在分布式資料庫系統上實作 Online Schema Change”轉化為“設計一種保證系統中最多有兩個 Schema 版本的協定”，并且給出了一種基于租約的協定實作。

協定内容可以概括為，以租約周期作為時間機關，協調了三個操作的節奏。

Schema 重新整理的間隔：每個節點需要在租約過期前，擷取一次最新版本 Schema，如果無法擷取，則主動退出，由托管服務重新拉起；
DDL 的最小時長：每次更新 Schema 版本後，需要等待一個租約周期，保證所有節點都讀到最新版本的中繼資料；
事務的最大時長：執行時間超過一個租約周期的事務将被復原，確定事務僅使用了一個 Schema 版本。

原始版本的協定十分簡潔，易于描述和驗證，但由于将 DDL 執行的最小時長和事務執行的最大時長綁定在一起，使用體驗上與單機資料庫有差別。對此，業界也給出了多種改進方案，比如：

CockroachDB 重新設計了 schema lease9，在兩方面做出改進：

- 降低 DDL 執行的最小時長：通過在事務開始時擷取一個包含版本資訊的租約，事務結束時釋放，使得更新 Schema 版本後能夠立即确認舊版本是否還在被使用，僅在有長事務或者節點異常（比如網絡斷開）時才需要等滿一個租約周期。由于通過在存儲中插入記錄來擷取租約，會增加事務的執行耗時。
- 隻在 DDL 執行過程中限制事務的最大時長：具體做法是，使用 Schema 版本變更開始的時間作為邊界，産生一個 [Tv,Tv+2) 的時間視窗。起始時間在視窗内，結束時間在視窗外的事務将被復原。如果有 DDL 正在執行，則視窗最大為兩個租約周期。如果沒有 DDL 執行，則不存在 v+2 版本，可以認為是一個無限大的視窗 [Tv,+∞)

TiDB 的實作中通過 PD 來實時判斷是否所有節點都完成了 Schema 版本更新10，部分節點失效的情況下需要等待一個租約周期。目前實作中，Schema 版本更新與事務執行沒有互動，執行期間有 Schema 版本變化的事務需要被復原。5.0 版本中對加減列、加減索引等 DDL 類型，支援在事務送出時修改變更的資料來适應 Schema 變化，避免復原事務。
OceanBase 的每個 ObServer 都同時具備存儲和計算的功能，儲存有一份中繼資料拷貝，可以在任務轉發過程中判斷兩端的中繼資料版本是否一緻，整體方案有所不同，總結如下11：

- 中繼資料分為多個版本
- 一個事務内的所有 SQL 都發到相同 ObServer，避免語句級别的中繼資料版本回退導緻資料不一緻的問題
- 事務中的語句需要通路的 ObServer 的中繼資料版本與 RootService 不同時對語句進行重試

從公開資料可以看出，使用存儲分離架構的産品對 F1 方案的改進主要集中在縮短 DDL 執行周期，DDL 執行導緻部分長事務被復原的問題并沒有解決。PolarDB-X 在使用體驗上高度相容 MySQL，需要設計自己的改進協定。

改進方案

回顧一下要解決的問題，“保證系統中最多有兩個 Schema 版本”，隐含的意思是 Schema 在系統中存在多個拷貝，且每個拷貝的版本可能不同。協定要做的，就是協調每個拷貝的更新操作，給出舊版本從系統中消失的可靠時間點。

分布式資料庫中有兩個地方會緩存 Schema：

出于性能考慮，每個節點會緩存一份 Schema，避免每個操作都需要從存儲讀取 Schema；
同一個事務中的語句需要使用相同的 Schema，是以在事務開始時也會緩存一份 Schema。

節點上緩存的 Schema，通常由每個節點上的背景線程定時重新整理，重新整理間隔為一個租約周期。如果節點重新整理 Schema 失敗，則復原所有未完成的事務，停止提供服務，直到擷取到最新版本的 Schema。這樣 Schema 從 V0 變更為 V1 後，隻需要等待一個租約周期，就可以保證所有節點要麼已經在使用 V1 版本，要麼復原了所有使用 V0 的事務，并停止提供服務。

HTAP 資料庫“必修課”：PolarDB-X Online Schema Change

事務中緩存的 Schema 版本無法更新，是以協定需要協調事務和 DDL 執行的順序，確定使用 V0 版本的事務全部 commit/rollback 之後才繼續執行 V1 到 V2 的版本變更。也就是說，對于執行過程中有 Schema 版本變更發生的事務，有兩種直覺的處理：

事務 rollback：版本變更無需等待，DDL 執行時間最短。缺點是，報錯的事務數量和業務吞吐量正相關，不符合 Online Schema Change 的初衷；
等待事務 commit：避免了事務報錯，缺點是如果存在異常節點，無法判斷事務結束時間，DDL 執行會被阻塞。

Google F1 的實作中，通過限制每個事務的最大執行時長為一個租約周期，簡化判斷事務結束時間的邏輯。引入租約周期的限制後，按照起止時間的不同，可以将事務分為下面幾類：

可以看到，F1 會保證執行時間在一個租約周期内的事務 T4 不受影響，但也影響了無 DDL 執行時的事務 T1, T3，同時會導緻 DDL 執行時長也至少為一個租約周期。CockroachDB 在此基礎上增加了事務結束釋放租約的機制，将切換為 V2 版本的時間限制為最後一個 V0 版本租約的過期時間，僅當有 V2 版本寫入時才判斷租約是否失效。這樣縮短了 DDL 的執行時間，并且僅在有 DDL 執行時限制事務的最大執行時長。

仔細分析可以發現，租約其實有兩用途，确定使用舊版本的事務結束和保證異常節點上使用舊版本的事務無法送出。PolarDB-X 在節點内部增加 MDL，通過短暫擷取舊版本 Schema 上的 exclusive MDL，排空使用舊版本的事務，将切換為 V2 版本的時間限制為 T5, T6 結束之後。同時，如果 GMS 元件确認節點異，标記舊版本 Schema 失效，等待一個租約周期後可以保證異常節點上使用舊版本的事務無法送出。

從使用者角度出發，理想 Online Schema Change 方案應該滿足下面三個特點，沒有 DDL 流程執行時不對事務增加過多額外開銷；DDL 流程中，事務不會被強制復原；DDL 的執行時間盡可能短。MySQL Online DDL 基本符合上述特點，而存儲分離架構的産品都有一些取舍，以下從這三個角度出發，對比現有方案和 PolarDB-X 的實作：

可以看到，PolarDB-X 方案有如下特點：

事務開始階段在記憶體中記錄 Schema，擷取節點内的 MDL，不引入資料讀寫開銷；
DDL 執行過程中，正常節點上事務執行不受影響，異常節點上限制事務執行的最大時長為一個租約周期；
正常情況下 DDL 毫秒級完成，存在異常節點時退化為分鐘級；
在節點内部實作了 MDL，通過多版本 Schema 避免排隊取鎖導緻使用新版本的 DML 被阻塞。

PolarDB-X Online Schema Change 實作

PolarDB-X 是一個分布式 HTAP 資料庫，采用存儲分離架構，高度相容 MySQL 生态，支援 Online Schema Change。

DDL 執行流程

收到使用者的 DDL 語句後，首先由接受語句的 CN 節點進行校驗，并生成 DDL Job 送出到 Global Meta Service (GMS) 的任務隊列中，随後 GMS 通知 CN 節點中的 DDL Worker 領取任務，開始推進 DDL 流程和 Schema 版本變更。

上圖展示 CREATE GLOBAL INDEX 的執行過程。DDL Worker 發起 Schema 版本變更時，首先通過 GMS 的 Sync 機制嘗試通知其他幾點加載新版本并排空使用舊版本的事務。如果 GMS 判定有節點異常，則等待一個租約周期後設定舊版本 Schema 為失效狀态，繼續推進 Schema 版本變更。事務送出時判斷節點是否正常重新整理了 Schema Cache，以及自己使用的 Schema 是否依然有效，如果不滿足則事務復原。

Schema 版本變更流程

收到更新中繼資料版本的通知後，首先檢查目前是否已經加載了該版本的 Schema，若尚未加載，加載新版本 Schema，之後嘗試擷取舊版本上的 MDL，若擷取 MDL 成功，代表節點上使用舊版本 Schema 的事務已經結束，該節點上的 Schema 版本變更完成，傳回成功。若擷取 MDL 失敗（逾時），傳回錯誤，交給上層重試。

同時，事務的第一條查詢執行前，擷取最新 Schema 版本上的 MDL，目前隻有S鎖和X鎖，通過隊列保證公平性，但不需要死鎖檢測等 MySQL MDL 的元件。MDL 為記憶體中的鎖，不落盤，節點重新開機時清空。

總結

Online Schema Change 是 HTAP 資料庫的必選功能。單機資料庫中，Schema 隻有一個版本，通過加鎖來避免 DDL 和 DML 并發導緻資料問題，通過縮小加鎖的範圍來實作 Online Schema Change。分布式資料庫通過引入中間狀态，允許同時存在至多兩個 Schema 版本，避免加鎖，支援 Online Schema Change 的關鍵點轉化為，設計一種節點互動協定，保證系統中至多同時存在兩個 Schema 版本。PolarDB-X 實作的協定，結合 MDL 和租約，不對事務執行引入額外開銷；無異常節點的情況下，Schema 版本變更不影響事務執行，無資料回填的 DDL 操作毫秒級完成；存在異常節點時，僅阻止異常節點上的事務送出，無資料回填的 DDL 操作分鐘級完成，與業界方案保持一緻。