摘要：基本邏輯一條數(shù)據(jù)在結(jié)構(gòu)中的旅程，從寫(xiě)入開(kāi)始，然后進(jìn)入，這是整個(gè)生命周期的第一處落腳點(diǎn)。每一層數(shù)據(jù)按排序，層與層之間的會(huì)交疊。上面是宏觀邏輯結(jié)構(gòu)，如果具體來(lái)論讀寫(xiě)操作和如何進(jìn)行，就需要探討每一層的數(shù)據(jù)組織方式每個(gè)變種的實(shí)現(xiàn)各不相同。

阿里妹導(dǎo)讀：數(shù)據(jù)庫(kù)存儲(chǔ)引擎是一個(gè)有歷史的技術(shù)，經(jīng)過(guò)數(shù)十年的發(fā)展，已經(jīng)出現(xiàn)很多優(yōu)秀成熟的產(chǎn)品。阿里巴巴 X-Engine 團(tuán)隊(duì)撰寫(xiě)的論文 "X-Engine: An Optimized Storage Engine for Large-scale E-Commerce Transaction Processing"，詳細(xì)講述了團(tuán)隊(duì)在數(shù)據(jù)庫(kù)存儲(chǔ)引擎上所做的原創(chuàng)性工作，今年早些時(shí)候已經(jīng)被 SIGMOD"19 Industrial Track 接收（SIGMOD 是數(shù)據(jù)庫(kù)領(lǐng)域最重要也是最有影響力的會(huì)議之一）。本文將對(duì)這篇論文做一個(gè)前導(dǎo)性分析。

X-Engine 是阿里數(shù)據(jù)庫(kù)產(chǎn)品事業(yè)部自研的 OLTP 數(shù)據(jù)庫(kù)存儲(chǔ)引擎，作為自研數(shù)據(jù)庫(kù)POLARDB X 的存儲(chǔ)引擎，已經(jīng)廣泛應(yīng)用在阿里集團(tuán)內(nèi)部諸多業(yè)務(wù)系統(tǒng)中，其中包括交易歷史庫(kù)，釘釘歷史庫(kù)等核心應(yīng)用，為業(yè)務(wù)大幅縮減了成本，同時(shí)也作為雙十一大促的關(guān)鍵數(shù)據(jù)庫(kù)技術(shù)，挺過(guò)了數(shù)百倍平時(shí)流量的沖擊。

數(shù)據(jù)庫(kù)存儲(chǔ)引擎是一個(gè)有歷史的技術(shù)，經(jīng)過(guò)數(shù)十年的發(fā)展，已經(jīng)出現(xiàn)很多優(yōu)秀成熟的產(chǎn)品。各式存儲(chǔ)引擎已經(jīng)在索引組織，緩存管理，事務(wù)處理，查詢優(yōu)化方方面面都做過(guò)細(xì)致的研究。即便如此，這個(gè)領(lǐng)域的演進(jìn)仍在持續(xù)，每年都會(huì)涌現(xiàn)很多的新技術(shù)。

近年來(lái)，LSM (Log-Structured Merge-Tree)結(jié)構(gòu)受到越來(lái)越多的關(guān)注，雖然這個(gè)技術(shù)本身出現(xiàn)很多年了，不算什么新事物，不過(guò)早先在 KV 存儲(chǔ)系統(tǒng)中被應(yīng)用的更多一些，近年開(kāi)始在數(shù)據(jù)庫(kù)存儲(chǔ)引擎領(lǐng)域嶄露頭角，RocksDB 即是典型代表。

LSM 之所以變得流行，一是因?yàn)槠浜?jiǎn)單，二是特點(diǎn)鮮明。寫(xiě)入模型是簡(jiǎn)單的追加，不會(huì)更新既有的數(shù)據(jù)，數(shù)據(jù)組織為簡(jiǎn)單的邏輯排序，由此帶來(lái)的特點(diǎn)是寫(xiě)強(qiáng)而讀弱，持久化數(shù)據(jù)只讀的特點(diǎn)便于壓縮。但是大多數(shù)數(shù)據(jù)庫(kù)的應(yīng)用場(chǎng)景其實(shí)都是讀多寫(xiě)少的，直接使用 LSM 結(jié)構(gòu)未必合適，想要另辟蹊徑，須得揚(yáng)長(zhǎng)辟短。

X-Engine 使用了 LSM 作為基礎(chǔ)架構(gòu)，目標(biāo)是作為一個(gè)通用的高性能低成本存儲(chǔ)引擎，追求讀寫(xiě)性能更為均衡，因此在其上做了大量的改進(jìn)，主要圍繞幾個(gè)方向進(jìn)行：

利用先天優(yōu)勢(shì)，持續(xù)優(yōu)化寫(xiě)性能。

優(yōu)化 compaction 降低對(duì)系統(tǒng)性能的沖擊，使得系統(tǒng)性能表現(xiàn)趨于平穩(wěn)。

利用持久化數(shù)據(jù)層只讀特點(diǎn)，發(fā)揮壓縮優(yōu)勢(shì)降低成本。

利用天然分層結(jié)構(gòu)，結(jié)合硬件能力使用冷熱分層結(jié)構(gòu)，降低綜合成本。

利用精細(xì)化訪問(wèn)機(jī)制和緩存技術(shù)，彌補(bǔ)讀性能短板。

X-Engine 的整體架構(gòu)如下圖，根據(jù)數(shù)據(jù)冷熱進(jìn)行分層代替 LSM 本身的持久化數(shù)據(jù)分層，熱數(shù)據(jù)層和數(shù)據(jù)更新使用內(nèi)存存儲(chǔ)，利用了大量?jī)?nèi)存數(shù)據(jù)庫(kù)的技術(shù)(Lock-Free index structure/append only)提高事務(wù)處理的性能，設(shè)計(jì)了一套事務(wù)處理流水線處理機(jī)制，把事務(wù)處理的幾個(gè)階段并行起來(lái)，提升吞吐。而訪問(wèn)頻度低的冷(溫)數(shù)據(jù)逐漸淘汰或是合并到持久化的存儲(chǔ)層次中，結(jié)合當(dāng)前豐富的存儲(chǔ)設(shè)備層次體系(NVM/SSD/HDD)進(jìn)行存儲(chǔ)。

我們對(duì)性能影響比較大的 compaction 過(guò)程做了大量?jī)?yōu)化，主要是拆分?jǐn)?shù)據(jù)存儲(chǔ)粒度，利用數(shù)據(jù)更新熱點(diǎn)較為集中的特征，盡可能的在合并過(guò)程中復(fù)用數(shù)據(jù)，精細(xì)化控制 LSM 的形狀，減少 I/O 和計(jì)算代價(jià)，并同時(shí)極大的減少了合并過(guò)程中的空間放大。同時(shí)使用更細(xì)粒度的訪問(wèn)控制和緩存機(jī)制，優(yōu)化讀的性能。

既然 X-Engine 是以 LSM 為基礎(chǔ)架構(gòu)的，所以一切還要從 LSM 本身說(shuō)起。

一條數(shù)據(jù)在 LSM 結(jié)構(gòu)中的旅程，從寫(xiě)入 WAL(Write Ahead Log) 開(kāi)始，然后進(jìn)入MemTable，這是 Ta 整個(gè)生命周期的第一處落腳點(diǎn)。隨后，flush 操作將 Ta 刻在更穩(wěn)固的介質(zhì)上，compaction 操作將Ta帶往更深遠(yuǎn)的去處，或是在途中丟棄，取決于 Ta 的繼任者何時(shí)到來(lái)。

LSM 的本質(zhì)是，所有寫(xiě)入操作并不做原地更新，而是以追加的方式寫(xiě)入內(nèi)存。每次寫(xiě)到一定程度，即凍結(jié)為一層(Level)，寫(xiě)入持久化存儲(chǔ)。所有寫(xiě)入的行，都以主鍵(Key)排序好后存放，無(wú)論是在內(nèi)存中，還是持久化存儲(chǔ)中。在內(nèi)存中即為一個(gè)排序的內(nèi)存數(shù)據(jù)結(jié)構(gòu)(Skiplist, B-Tree, etc.)，在持久化存儲(chǔ)也作為一個(gè)只讀的全排序持久化存儲(chǔ)結(jié)構(gòu)。

普通的存儲(chǔ)系統(tǒng)若要支持事務(wù)處理，尤其是ACI，需要加入一個(gè)時(shí)間維度，借此為每個(gè)事務(wù)構(gòu)造出一個(gè)不受并發(fā)干擾的獨(dú)立視域。存儲(chǔ)引擎會(huì)對(duì)每個(gè)事務(wù)定序并賦予一個(gè)全局單調(diào)遞增的事務(wù)版本號(hào)(SN)，每個(gè)事務(wù)中的記錄會(huì)存儲(chǔ)這個(gè) SN 以判斷獨(dú)立事務(wù)之間的可見(jiàn)性，從而實(shí)現(xiàn)事務(wù)的隔離機(jī)制。

如果 LSM 存儲(chǔ)結(jié)構(gòu)持續(xù)寫(xiě)入，不做其他的動(dòng)作，那么最終會(huì)成為如下結(jié)構(gòu)：

注意這里每一層的 SN 范圍標(biāo)識(shí)了事務(wù)寫(xiě)入的先后順序，已經(jīng)持久化的數(shù)據(jù)不再會(huì)被修改。每一層數(shù)據(jù)按 Key 排序，層與層之間的 Key range 會(huì)交疊。

這種結(jié)構(gòu)對(duì)于寫(xiě)入是非常友好的，只要追加到最新的內(nèi)存表中即完成，為實(shí)現(xiàn) crash recovery，只需記錄 WAL(Redo Log)，因?yàn)樾聰?shù)據(jù)不會(huì)覆蓋舊版本，追加記錄會(huì)形成天然的多版本結(jié)構(gòu)。

可以想見(jiàn)，如此累積凍結(jié)的持久化層次越來(lái)越多，會(huì)對(duì)查詢會(huì)產(chǎn)生不利的影響，對(duì)同一個(gè) key 不同事務(wù)提交產(chǎn)生的多版本記錄會(huì)散落在各個(gè)層次中，不同的 key 也會(huì)散落在不同層次中，讀操作諸如順序掃描便需要查找各個(gè)層并合并產(chǎn)生最終結(jié)果。

LSM 引入了一個(gè) compaction 的操作解決這個(gè)問(wèn)題，這個(gè)操作不斷的把相鄰層次的數(shù)據(jù)合并，并寫(xiě)入這個(gè)更低層次。而合并的過(guò)程實(shí)際上就是把要合并的相鄰兩層(或是多層)數(shù)據(jù)讀出來(lái)，按 key 排序，相同的 key 如果有多個(gè)版本，只保留新(比當(dāng)前正在執(zhí)行的活躍事務(wù)中最小版本號(hào)新)的版本，丟掉舊版本數(shù)據(jù)，然后寫(xiě)入新的層?？梢韵胍?jiàn)這個(gè)操作非常耗費(fèi)資源。

LSM compaction 操作，有幾種作用，一是為了丟棄不再被使用的舊版本數(shù)據(jù)，二是為了控制 LSM 層次形狀，一般的 LSM 形狀都是層次越低，數(shù)據(jù)量越大(倍數(shù)關(guān)系)，這樣放置的目的主要是為了提升讀性能。

一般來(lái)講，任何存儲(chǔ)系統(tǒng)的數(shù)據(jù)訪問(wèn)都有局部性，大量的訪問(wèn)都集中在少部分?jǐn)?shù)據(jù)上，這也是緩存系統(tǒng)能有效工作的基本前提，在 LSM 存儲(chǔ)結(jié)構(gòu)中，如果我們把訪問(wèn)頻率高的數(shù)據(jù)盡可能放在較高的層次上，保持這部分?jǐn)?shù)據(jù)量規(guī)模，可以存放在快速存儲(chǔ)設(shè)備中(比如 NVM,DRAM)，而把訪問(wèn)頻率低的數(shù)據(jù)放在較低層次中，使用廉價(jià)慢速存儲(chǔ)設(shè)備存儲(chǔ)。這就是 X-Engine 的根據(jù)冷熱分層概念。

要達(dá)到這種效果，核心問(wèn)題是如何挑選合適的數(shù)據(jù)合并到更低的層次，這是compaction 調(diào)度策略首先要解決的問(wèn)題，根據(jù)冷熱分層的邏輯，就是優(yōu)先合并冷數(shù)據(jù)(訪問(wèn)頻率相對(duì)低)。

識(shí)別冷數(shù)據(jù)有很多方法，對(duì)于不同的業(yè)務(wù)不盡然相同，對(duì)于很多流水型業(yè)務(wù)(如交易，日志系統(tǒng))，新近寫(xiě)入的數(shù)據(jù)會(huì)有更多的概率被讀到，冷熱按寫(xiě)入時(shí)間順序即可區(qū)分，也有很多應(yīng)用的訪問(wèn)特征跟寫(xiě)入的時(shí)間不一定有關(guān)系，這個(gè)就要根據(jù)實(shí)際的訪問(wèn)頻率去識(shí)別冷數(shù)據(jù)或是熱數(shù)據(jù)。

除了數(shù)據(jù)熱度以外，挑選合并數(shù)據(jù)還有其他一些維度，會(huì)對(duì)讀性能產(chǎn)生影響，比如數(shù)據(jù)的更新頻率，大量的多版本數(shù)據(jù)在查詢的時(shí)候會(huì)浪費(fèi)更多的I/O和CPU，因此需要優(yōu)先進(jìn)行合并以減少記錄的版本數(shù)量，X-Engine 綜合考慮了各種策略形成自己的compaction 調(diào)度機(jī)制。

上面是 LSM 宏觀邏輯結(jié)構(gòu)，如果具體來(lái)論讀寫(xiě)操作和 compaction 如何進(jìn)行，就需要探討每一層的數(shù)據(jù)組織方式, 每個(gè) LSM 變種的實(shí)現(xiàn)各不相同。

X-Engine 的 memtable 使用了 Locked-free SkipList. 求的是簡(jiǎn)單，而且并發(fā)讀寫(xiě)的性能都比較高。當(dāng)然有更高效的數(shù)據(jù)結(jié)構(gòu)，或者同時(shí)使用多種索引技術(shù)。這個(gè)部分X-Engine 沒(méi)有做過(guò)多優(yōu)化，原因在事務(wù)處理的邏輯比較復(fù)雜，寫(xiě)入內(nèi)存表還沒(méi)有成為其瓶頸。

持久化層如何組織更顯高效，這就需要討論每層的細(xì)微結(jié)構(gòu)。

數(shù)據(jù)組織

簡(jiǎn)單來(lái)說(shuō)，X-Engine 的每層都劃分成固定大小的 Extent，存放每個(gè)層次中的數(shù)據(jù)的一個(gè)連續(xù)片段(Key Range). 為了快速定位 Extent，為每層 Extents 建立了一套索引(Meta Index)，所有這些索引，加上所有的 memory tables(active/immutable)一起組成了一個(gè)元數(shù)據(jù)樹(shù)(Metadata Tree)，root 節(jié)點(diǎn)為"Metadata Snapshot", 這個(gè)樹(shù)結(jié)構(gòu)類似于 B-Tree，當(dāng)然不盡相同。

需要注意的是，X-Engine 中除了當(dāng)前的正在寫(xiě)入的 active memtable 以外，其他結(jié)構(gòu)都是只讀的，不會(huì)被修改。給定某個(gè)時(shí)間點(diǎn), 比如 LSN=1000, 上圖中的 "Metadata Snapshot1" 引用到的結(jié)構(gòu)即包含了(LSN=1000)時(shí)刻的所有的數(shù)據(jù)的快照(這也是為什么這個(gè)結(jié)構(gòu)被稱為 Snapshot 的原因)。

即便是 Metadata 結(jié)構(gòu)本身，也是一旦生成就不會(huì)修改。所有的讀都是以這個(gè)" Snapshot "結(jié)構(gòu)為入口，這個(gè)是 X-Engine 實(shí)現(xiàn) SI 隔離級(jí)別的基礎(chǔ)。之前講過(guò)隨著數(shù)據(jù)寫(xiě)入，累積數(shù)據(jù)越多，需要對(duì) memtable 凍結(jié)，flush, 以及層與層的compaction. 這些操作都會(huì)修改每層的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)，所有這些操作，都是用 copy-on-write 來(lái)實(shí)現(xiàn)，方法就是每次都將修改(switch/flush/compaction)產(chǎn)生的結(jié)果寫(xiě)入新的 Extent，然后依次生成新的"Meta Index"結(jié)構(gòu)，乃至新的"Metadata Snapshot"，以一次 compaction 操作為例：

可以看到"Metadata Snapshot 2"相對(duì)于"Metadata Snapshot 1"并沒(méi)有太多的變化，僅僅修改了發(fā)生變更的一些葉子節(jié)點(diǎn)以及索引節(jié)點(diǎn)。這個(gè)技術(shù)頗有些類似"B-trees, Shadowing, and Clones"（https://liw.fi/larch/ohad-btrees-shadowing-clones.pdf），如果你讀過(guò)那篇論文，會(huì)對(duì)理解這個(gè)過(guò)程有所幫助。

事務(wù)處理

得益于 LSM 輕量化寫(xiě)機(jī)制，寫(xiě)入操作固然是其明顯的優(yōu)勢(shì)，但是事務(wù)處理遠(yuǎn)不只是把更新的數(shù)據(jù)寫(xiě)入系統(tǒng)那么簡(jiǎn)單，這里要保證 ACID，涉及到一整套復(fù)雜的流程。X-Engine 將整個(gè)事務(wù)處理過(guò)程分為兩個(gè)階段：讀寫(xiě)階段和提交階段。

讀寫(xiě)階段需要校驗(yàn)事務(wù)的寫(xiě)寫(xiě)沖突，讀寫(xiě)沖突，判斷事務(wù)是否可以執(zhí)行或回滾重試，或是等鎖。如果事務(wù)沖突校驗(yàn)通過(guò)，則把修改的所有數(shù)據(jù)寫(xiě)入"Transaction Buffer", 提交階段包括寫(xiě) WAL，寫(xiě)內(nèi)存表，以及提交并返回給用戶結(jié)果的整個(gè)過(guò)程，這里面既有 I/O 操作(寫(xiě)日志，返回消息)，也有 CPU 操作(拷貝日志，寫(xiě)內(nèi)存表)。

為了提高事務(wù)處理吞吐，系統(tǒng)內(nèi)會(huì)有大量事務(wù)并發(fā)執(zhí)行，單個(gè)I/O操作比較昂貴，大部分存儲(chǔ)引擎會(huì)傾向于聚集一批事務(wù)一起提交，稱為"Group Commit"，能夠合并I/O操作，但是一組事務(wù)提交的過(guò)程中，還是有大量等待過(guò)程的，比如寫(xiě)入日志到磁盤(pán)過(guò)程中，除了等待落盤(pán)無(wú)所事事。

X-Engine 為了進(jìn)一步提升事務(wù)處理的吞吐，采用了一種流水線的技術(shù)：把提交階段分為四個(gè)獨(dú)立的更細(xì)的階段：拷貝日志到緩沖區(qū)(Log Buffer)，日志落盤(pán)(Log Flush)，寫(xiě)內(nèi)存表(Write memtable)，提交返回(Commit)。我們的事務(wù)提交線程到了處理階段，都可以自由選擇執(zhí)行流水線中任意一個(gè)階段，這樣每個(gè)階段都可以并行起來(lái)，只要流水線任務(wù)的大小劃分得當(dāng)，就能充分并行起來(lái)，流水線處于接近滿載狀態(tài)。

另外，利用的是事務(wù)處理的線程，而非后臺(tái)線程，每個(gè)線程在執(zhí)行的時(shí)候，要么選擇了流水線中的一個(gè)階段干活，要么逛了一圈發(fā)現(xiàn)無(wú)事可做，干脆回去接收更多的請(qǐng)求，這里沒(méi)有等待，也無(wú)需切換，充分的調(diào)動(dòng)了每個(gè)線程的能力。

讀操作

LSM 在處理多版本數(shù)據(jù)的方式是新版本數(shù)據(jù)記錄會(huì)追加在老版本數(shù)據(jù)后面，從物理上看，一條記錄不同的版本可能存放在不同的層，在查詢的時(shí)候需要找到合適的版本(根據(jù)事務(wù)的隔離級(jí)別定義的可見(jiàn)性規(guī)則)，一般查詢都是查找最新的數(shù)據(jù)，總是由新的層次(最新寫(xiě)入)往老的層次方向找。

對(duì)于單條記錄的查找而言，一旦找到便可終止，如果記錄還在比較靠上的層次，比如memtable，很快便返回；如果記錄不幸已經(jīng)落入了很低的層次(可能是很隨機(jī)的讀)，那就得經(jīng)歷逐層查找的漫漫旅途，也許 bloomfilter 可以跳過(guò)某些層次加快這個(gè)旅程，但畢竟還是有更多的I/O操作。

X-Engine 針對(duì)單記錄查詢引入了 Row Cache，在所有持久化的層次的數(shù)據(jù)之上做了一個(gè)緩存，在 memtable 中沒(méi)有命中的單行查詢，在 Row Cache 之中也會(huì)被捕獲。Row Cache 需要保證緩存了所有持久化層次中最新版本的記錄，而這個(gè)記錄是可能發(fā)生變化的，比如每次 flush 將只讀的 memtable 寫(xiě)入持久化層次時(shí)，就需要恰當(dāng)?shù)母?Row Cache 中的緩存記錄，這個(gè)操作比較微妙，需要小心的設(shè)計(jì)。

范圍掃描的操作就沒(méi)這么幸運(yùn)了。因?yàn)闆](méi)法確定一個(gè)范圍的key在哪個(gè)層次中有數(shù)據(jù)，也許是每層都有，只能掃描所有的層次做合并之后才能返回最終的結(jié)果。X- Engine 同樣采用了一系列的手段：比如 Surf(SIGMOD"18 best paper)提供 range scan filter 減少掃描層數(shù)；還有異步 I/O 與預(yù)取對(duì)大范圍掃描也有顯著的提升。

讀操作中最核心的是緩存設(shè)計(jì)，Row Cache 來(lái)應(yīng)付單行查詢，Block Cache 負(fù)責(zé)Row Cache miss 的漏網(wǎng)之魚(yú)，也用來(lái)應(yīng)付 scan；由于 LSM 的 compaction 操作會(huì)一次大批量更新大量的 Data Block，導(dǎo)致 Block Cache 中大量數(shù)據(jù)短時(shí)間內(nèi)失效，帶來(lái)性能的急劇抖動(dòng)。

X-Engine 同樣做了很多的處理：

減少 Compaction 的粒度；

減少 compaction 過(guò)程中改動(dòng)的數(shù)據(jù)(見(jiàn)稍后章節(jié)) ；

compaction 過(guò)程中針對(duì)已有的cache數(shù)據(jù)做定點(diǎn)更新，由此可以基本將 cache 失效帶來(lái)的抖動(dòng)降到最低的水平。

X-Engine 中的緩存比較多樣，memtable 也可算做其中一種。以有限的內(nèi)存，如何恰當(dāng)?shù)姆峙浣o每一種緩存，才能實(shí)現(xiàn)價(jià)值最大化，是一個(gè)還未被妥善解決的問(wèn)題，X-Engine 也在探索當(dāng)中。

當(dāng)然，LSM 對(duì)讀帶來(lái)的也并非全是壞處，除了 memtable 以外的只讀的結(jié)構(gòu)，在讀取路徑上可以做到完全無(wú)鎖( memtable 也可設(shè)計(jì)成讀無(wú)鎖)。

Compaction

compaction 操作是比較重的。需要把相鄰層次交叉的 key range 數(shù)據(jù)讀出來(lái)，合并，然后寫(xiě)到新的位置。這是為前面簡(jiǎn)單的寫(xiě)入操作不得不付出的代價(jià)。X-Engine 為優(yōu)化這個(gè)操作重新設(shè)計(jì)了存儲(chǔ)結(jié)構(gòu)。

如前所述，X-Engine 將每一層的數(shù)據(jù)劃分為固定大小的" Extent"，一個(gè) Extent 相當(dāng)于一個(gè)小的完整的 SSTable, 存儲(chǔ)了一個(gè)層次中的一個(gè)連續(xù)片段，其中又會(huì)被進(jìn)一步劃分一個(gè)個(gè)連續(xù)的更小的片段"Data Block"，相當(dāng)于傳統(tǒng)數(shù)據(jù)庫(kù)中的"Page"，只不過(guò)是只讀的，而且是不定長(zhǎng)的。

回看數(shù)據(jù)組織一節(jié)中"合并操作對(duì)元數(shù)據(jù)的改變", 對(duì)比"Metadata Snapshot2"和"Metadata Snapshot1"的區(qū)別，可以發(fā)現(xiàn) Extent 的設(shè)計(jì)意圖。是的，每次修改對(duì)結(jié)構(gòu)的調(diào)整并不是全部來(lái)過(guò)，而是只需要修改少部分有交疊的數(shù)據(jù)，以及涉及到的"Meta Index"節(jié)點(diǎn)。

兩個(gè)"Metadata Snapshot"結(jié)構(gòu)實(shí)際上共用了大量的數(shù)據(jù)結(jié)構(gòu)。這個(gè)被稱為數(shù)據(jù)復(fù)用技術(shù)(Data Reuse)，而 Extent 大小正是影響數(shù)據(jù)復(fù)用率的關(guān)鍵，Extent 作為一個(gè)完整的被復(fù)用的物理結(jié)構(gòu)，需要盡可能的小，這樣與其他 Extent 數(shù)據(jù)交叉點(diǎn)會(huì)變少，但又不能非常小，否則需要索引過(guò)多，管理成本太大。

X-Engine 中 compaction 的數(shù)據(jù)復(fù)用是非常徹底的，假設(shè)選取兩個(gè)相鄰層次(Level1, Level2)中的交叉的 Key Range 所涵蓋的 Extents 進(jìn)行合并，合并算法會(huì)逐行進(jìn)行掃描，只要發(fā)現(xiàn)任意的"物理結(jié)構(gòu)"(包括 Data Block 和 Extent )與其他層中的數(shù)據(jù)沒(méi)有交疊，則可以進(jìn)行復(fù)用。只不過(guò)，Extent的復(fù)用可以修改 Meta Index，而 Data Block 的復(fù)用只能拷貝，即便如此也可以節(jié)省大量的 CPU.

一個(gè)典型的數(shù)據(jù)復(fù)用在 compaction 中的過(guò)程可以參考下圖：

可以看出，對(duì)于數(shù)據(jù)復(fù)用的過(guò)程是在逐行迭代的過(guò)程中完成的，不過(guò)這種精細(xì)的數(shù)據(jù)復(fù)用帶來(lái)另一個(gè)副作用，即數(shù)據(jù)的碎片化，所以在實(shí)際操作的過(guò)程中也需要根據(jù)實(shí)際情況進(jìn)行折中。

數(shù)據(jù)復(fù)用不僅給 compaction 操作本身帶來(lái)了好處，降低操作過(guò)程中的 I/O 與 CPU消耗，更對(duì)系統(tǒng)的綜合性能產(chǎn)生了一系列的影響。比如 compaction 過(guò)程中數(shù)據(jù)不用完全重寫(xiě)，大大減少了寫(xiě)入空間放大；更因?yàn)榇蟛糠謹(jǐn)?shù)據(jù)保持原樣，數(shù)據(jù)緩存不會(huì)因?yàn)閿?shù)據(jù)更新而失效，減少合并過(guò)程中因緩存失效帶來(lái)的讀性能抖動(dòng)。

實(shí)際上，優(yōu)化 compaction 的過(guò)程只是 X-Engine 工作的一部分，還有更重要的，就是優(yōu)化 compaction 調(diào)度的策略，選什么樣的 Extent，定義 compaction 任務(wù)的粒度，執(zhí)行的優(yōu)先級(jí)，都會(huì)對(duì)整個(gè)系統(tǒng)性能產(chǎn)生影響，可惜并不存在什么完美的策略，X-Engine 積累了一些經(jīng)驗(yàn)，定義了很多規(guī)則，而探索如何合理的調(diào)度策略是未來(lái)一個(gè)重要方向。

X-Engine 是阿里云智能事業(yè)群-數(shù)據(jù)庫(kù)產(chǎn)品事業(yè)部的重要核心技術(shù)之一。

作為兼容 MySQL 的數(shù)據(jù)庫(kù) POLARDB X 的存儲(chǔ)引擎，之前是在服務(wù)阿里集團(tuán)業(yè)務(wù)中逐漸打磨成熟，今年下半年，我們將在阿里云平臺(tái)上推出 MySQL(X-Engine) 的RDS 公有云服務(wù)，為阿里云上的公有云客戶提供低成本高性能的數(shù)據(jù)庫(kù)服務(wù)。

本文來(lái)自云棲社區(qū)合作伙伴“阿里技術(shù)”，如需轉(zhuǎn)載請(qǐng)聯(lián)系原作者。