引言
數據庫系統為了高效地存儲、檢索和維護數據，採用了多種不同的數據組織結構。不同的組織結構有其特定的用途和優化點，比如提高查詢速度、優化寫入性能、減少存儲空間等。常見的數據庫記錄組織結構有：
- B-Tree
B-Tree是一種平衡的多路搜索樹，特別適合存儲在外部存儲器（如硬盤）中。它通過減少訪問磁盤的次數來優化讀寫操作。B-Tree廣泛應用於數據庫管理系統和文件系統中，用於存儲索引和數據。典型的代表有MySQL。 - LSM Tree
LSM Tree是一種適合寫入密集型場景的數據結構，通常用於NoSQL數據庫中。它將數據更新操作寫入內存中的結構，然後定期合併到磁盤上。這種設計充分利用了順序寫能力，大幅度優化了寫入性能。使用LSM Tree的佼佼者有LevelDB、HBase等。 - Heap Table
Heap Table是一種簡單的數據記錄組織方式。Heap Table的記錄以任意順序插入到表中，數據的寫入性能幾乎能達到磁盤寫入的上限。但是由於其無序性，數據查詢效率不如索引表。為了改進查詢性能，Heap Table通常還會搭配如B-Tree這樣的索引結構使用。典型的數據庫有PostgreSQL。 - Skip List跳錶
跳錶是一種概率性結構，它通過在多層鏈表上添加“快速通道”的方式來實現快速搜索，實現了平均複雜度為O(log n)的插入、刪除和查找操作。同樣用於某些版本的 NoSQL數據庫中，被用作內存索引的一種有效結構。
每種數據組織結構都有其優勢和應用場景。關係型數據庫OLTP業務對併發讀寫、MVCC、空間利用率、高效查找和範圍查詢、優化磁盤I/O、平衡性等等都要有均衡的訴求，目前PolarDB分佈式版採用了B-Tree的索引組織結構。
B-Tree索引中最常用到的是聚簇索引（即主鍵索引）。通過聚簇索引，查詢能夠直接找到對應數據行的所有數據。值得注意的是，阿里雲瑤池旗下的雲原生數據庫PolarDB分佈式版（PolarDB for Xscale，簡稱PolarDB-X）存儲引擎在聚簇索引上還放入數據行的版本信息。當查詢進行時，PolarDB分佈式版需要通過比對查詢的視圖信息以及聚簇索引上行記錄的版本信息，來確定查詢需要查找的版本記錄。當聚簇索引上的當前版本並不滿足要求時，需要通過Undo日誌把對應記錄的歷史版本構建出來。
聚簇索引對於主鍵查詢非常有效，然而如果查詢的條件並不由主鍵來決定時，查詢需要回退到全量掃描。為了解決這個問題，非聚簇索引被引入。非聚簇索引與聚簇索引很相似，但非聚簇索引有一個重要的區別：
非聚簇索引沒有版本信息，即通過非聚簇索引只能查找最新版本。當查找非聚簇索引時，需要首先確認該版本是否為本查詢所需要的版本。但由於非聚簇索引上沒有版本信息，所以進一步需要通過主鍵信息查找聚簇索引，以獲得版本信息。
通過非聚簇索引查找對應的聚簇索引記錄，這個過程通常被稱為回表。
下面展示了一個典型的非聚簇索引的使用案例：年級成績表（聚簇索引）：
班級-學生號索引（非聚簇索引）：
當查詢二班的所有學生號時，雖然只需要查找非聚簇索引即可，但是由於不能確定是否可見，還需要回查聚簇索引上對應的主鍵記錄，確定其真實的版本號信息。
非聚簇索引回表代價
一條SQL語句回表代價取決於回表的頻次以及回表本身的開銷。
回表本身開銷在於B-Tree查找，即一次非聚簇索引記錄的查詢，需要一次聚簇索引的查詢。
回表的頻次則取決於SQL語句的類型。特別是對於Range查詢：
SELECT sec FROM t1 WHERE sec BETWEEN ? AND ?當PolarDB分佈式版DN存儲引擎執行一條SQL時，需要經歷開表、B-Tree查找等等階段，Range查詢會顯著地增大回表開銷的佔比，如果每一行記錄都需要回表，則會造成嚴重的性能問題。
在我們的測試數據中發現，全回表相比於不回表，性能有10倍以上的差距。
索引回表操作還會對Buffer Pool造成衝擊，特別是當Buffer Pool資源緊張時，大量的回表操作會佔用了Buffer Pool的空閒頁，導致數據庫雪崩。
考慮極端情況，如果一張表上幾乎沒有修改，則因為要判斷可見性而帶來的回表操作幾乎是沒有意義的。
通過上面分析可以發現，因為判斷可見性而帶來的回表，代價是昂貴，且大多數情況下是無必要的。目前單機數據庫如MySQL通過引入最小活躍事務號，輔助非聚簇索引的可見性判斷，大幅度降低了因為可見性判斷而帶來的回表問題。
但是，對於PolarDB-X這樣的分佈式數據庫，情況會變得更復雜，這個方案將不再適用。為了解決這個問題，PolarDB分佈式版DN存儲引擎提出了CSM(Commit Snapshot Manager)方案。
下面會介紹單機數據庫MySQL的解決方案，並引申到PolarDB分佈式版針對分佈式場景設計的CSM方案。
單機MySQL非聚簇索引回表優化
為了解決這個問題，MySQL通過引入最小活躍事務號，輔助非聚簇索引的可見性判斷，大幅度避免了回表查詢的次數，大大降低了查找代價。
事務ID號唯一標識了一個事務。MySQL會維護一個事務ID號生成器。該事務ID號生成器會生成全局唯一單調遞增的事務ID號。當事務啓動時，都需要從該事務ID號生成器裏獲取一個事務ID號作為自己的事務標識。
同時，MySQL還維護了一個全局的狀態變量：min_active_trx_id。
min_active_trx_id表示所有活躍事務裏最小的事務ID號。這意味着，所有事務ID號比min_active_trx_id小的事務都已提交。
除此之外，還會在非聚簇索引的每一個數據頁上維護一個特殊的持久化信息：max_trx_id。max_trx_id表示本數據頁內所有修改過該數據頁的事務裏最大的事務ID號。
當查詢發起時，會構建一個視圖，該視圖需要獲取當前系統的min_active_trx_id作為視圖的up_limit_id。當查找非聚簇索引時，可以通過up_limit_id與數據頁的 max_trx_id做比較來確定可見性。相關流程圖如下所示：
分佈式數據庫的索引回表困境
對於分佈式數據庫，回表問題會被進一步放大。PolarDB分佈式版，分佈式查詢採用基於全局時間戳TSO的MVCC多版本查詢。即分佈式查詢視圖的版本號GCN是由外部的全局授時服務生成的TSO來指定，而並非從數據庫管理系統裏的本地事務系統最新狀態獲取。
由於網絡、系統調度等原因，當分佈式查詢真正發起時，節點內的事務系統狀態可能已經發生過多次變化，事務系統狀態最新的min_active_trx_id信息已經不再適用於本次分佈式查詢GCN視圖的構建。以下面例子為例：
對於上述發起的分佈式查詢，實際上由於（snapshot_GCN = 99）<（rec_GCN = 100），所以該記錄對於該視圖應該是不可見的。
之所以出現上述問題，其核心原因在於，所有的分佈式事務的提交順序並非由本地生成，而是由外部全局協調器統一生成。即多個分佈式事務的分支事務在各個節點上的實際提交順序可能是不同的。
這導致分佈式查詢的可見性要遠比本地單機查詢複雜，目前業界內基於單機查詢設計的非聚簇索引優化理論，在分佈式查詢上不再有效。
如何在分佈式數據庫管理系統裏，降低非聚簇索引因為查找版本信息而帶來的額外回表代價，是分佈式數據庫管理系統設計裏最關鍵的問題之一。
Commit Snapshot Manager方案
單機數據庫管理系統上非聚簇索引的優化方案，在分佈式場景下不再適用的原因是：分佈式查詢需要的是“彼時彼刻”的min_active_trx_id，但數據庫現有的設計只能提供“此時此刻”的min_active_trx_id。
上述説的“時刻”並不是物理時間上的時刻，而是GCN這樣的邏輯“時刻”。即：對於snapshot_GCN = 99的分佈式查詢，它需要的是DN節點處於GCN = 99時事務系統對應的min_active_trx_id。
一個直觀的設想是，如果事務系統維護了過去所有時間點的事務系統狀態信息，並且提供能力回查當時時刻的min_active_trx_id狀態，則可以解決分佈式場景下非聚簇索引因為無法判斷可見性而需要回表的問題。
當然這個代價是巨大的，以10萬TPS為例，每分鐘需要產生至少90 MB的數據。
PolarDB分佈式版存儲引擎採用了CSM方案來均衡了資源開銷與可用性，以極低的代價維護過去時間點的近似min_active_trx_id狀態，徹底解決了分佈式場景下非聚簇索引頻繁回表的問題。CSM是一個環形隊列，每間隔一定時間（如 1 秒）則會產生一個Commit Snapshot。更具體地説：
- CSM收集開始；
- 獲取系統當下的min_active_trx_id作為up_limit_id；
- 獲取系統當下的sys_GCN, sys_SCN為csm_GCN以及csm_SCN；
- 將 (up_limit_id， csm_GCN， csm_SCN) 作為一個Commit Snapshot，插入到CSM。
其中，sys_GCN是PolarDB分佈式版存儲引擎維護的本節點上的最大GCN號。其更新時機為：
- 分佈式查詢由外部協調者指定了snapshot_GCN作為分佈式查詢視圖的GCN，sys_GCN = max { sys_GCN, snapshot_GCN }。
- 分佈式事務提交由外部協調者指定了commit_GCN作為分佈式事務的提交號 GCN，sys_GCN = max { sys_GCN, commit_GCN }。
顯然，sys_GCN，min_active_trx_id均滿足單調遞增永不回退。這意味着：在CSM 環形隊列上，csm_GCN、up_limit_id總是有序的。
當分佈式查詢發起時，根據視圖的snapshot_GCN，從CSM尾部開始查找，直到找到 csm_GCN剛好不大於snapshot_GCN的CSM元素，取該元素的up_limit_id作為視圖的up_limit_id——我們就得到了我們想要的“彼時彼刻”的up_limit_id。值得注意的是，由於有序性的保證，上述查找可通過二分查找完成。
顯然，這個up_limit_id只是“彼時彼刻”真正的up_limit_id的近似值。但通過上述步驟，我們總是能夠拿到一個比真實值要小的近似值。幸運的是，當我們拿一個更小的up_limit_id去做可見性判斷時，並不會導致誤判。
可以看見，上述CSM中的Commit Snapshot還包括了csm_SCN。這是因為PolarDB分佈式版標準版還支持了閃回查詢AS OF語法。通過閃回查詢，可以輕鬆完成遊戲回檔、業務回滾、數據誤刪恢復等特性。有關PolarDB分佈式版DN存儲引擎的事務系統的設計，可參考過往文章《PolarDB分佈式版存儲引擎核心技術｜Lizard分佈式事務系統》。
SELECT sec FROM t1 AS OF SCN $SCN WHERE sec BETWEEN ? AND ?
SELECT sec FROM t1 AS OF TIMESTAMP $time WHERE sec BETWEEN ? AND ?測試結果顯示，對於分佈式事務的一致性查詢，開啓CSM（32KB內存資源 + 少量計算開銷）具有顯著的性能提升：
# 壓測SQL，模擬命中sec列的索引
SELECT sec FROM t1 WHERE sec BETWEEN ? AND ?
🎉 雲原生數據庫PolarDB分佈式版（PolarDB for Xscale，簡稱PolarDB-X）價格下調40%，最低至0.75元/小時，點擊👉「產品」即可瞭解詳情
