簡介：?隨著非易失內存產品的商業化推廣，我們對于其在云原生數據庫中大規模推廣的潛力越來越有興趣。X-Engine是阿里云數據庫產品事業部PolarDB新型存儲引擎團隊研發的一個LSM-tree存儲引擎，目前在阿里云PolarDB產品上提供對外服務。我們以X-Engine為基礎結合非易失內存的優勢與限制，重新設計并實現了存儲引擎的主要內存數據結構、事務處理和持久化內存分配器等基礎組件，最終實現了不需要記錄預寫式日志的高性能事務處理，降低了整體系統的寫入放大并提高了存儲引擎的故障恢復速度。

作者 | 百葉
來源 | 阿里技術公眾號

引言：隨著非易失內存產品的商業化推廣，我們對于其在云原生數據庫中大規模推廣的潛力越來越有興趣。X-Engine是阿里云數據庫產品事業部PolarDB新型存儲引擎團隊研發的一個LSM-tree存儲引擎，目前在阿里云PolarDB產品上提供對外服務。我們以X-Engine為基礎結合非易失內存的優勢與限制，重新設計并實現了存儲引擎的主要內存數據結構、事務處理和持久化內存分配器等基礎組件，最終實現了不需要記錄預寫式日志的高性能事務處理，降低了整體系統的寫入放大并提高了存儲引擎的故障恢復速度。該研究成果以論文《Revisiting the Design of LSM-tree Based OLTP Storage Engine with Persistent Memory》發表到VLDB2021。論文容量較大，無論是對于后續的研究還是應用落地都具有較高的參考價值。作為一個持續深耕數據庫基礎技術的團隊，我們在事務存儲引擎/高性能事務處理/新型存儲器件/異構計算設備/AIforDB上均有涉獵及研究，歡迎海內外有志之士加盟或交流。

一 背景介紹

1 持久化內存簡介

PM在提供相比DRAM更大容量、更低功耗的同時，還具備字節尋址等諸多特點，旨在大幅度提升設備內存容量以及降低設備靜態功耗的同時，提供可持久化字節尋址等特性以簡化系統的設計，為數據庫存儲引擎的設計帶來了新的契機。Optane DCPMM采用DDR4 DIMM的產品形態，亦被稱之為“持久內存模組”Persistent Memory Module/PMM。當前DCPMM單條容量提供三種選擇128GB、256GB、512GB，實際可用容量分別為126.4GiB、252.4GiB、502.5GiB。Optane DCPMM當前僅適用于Intel Cascade Lake處理器，其和傳統的的DRAM類似，通過Intel iMC（integrated Memory Controller）連接到處理器。DCPMM雖然提供和DRAM相同的字節尋址能力，但其I/O表現與DRAM存在較大差異，主要體現在介質訪問粒度、cache控制、并發訪問以及跨NUMA節點訪問等方面。感興趣的讀者可以參考本文后續的文獻[1,2]。

2 X-Engine簡介

X-Engine是一種基于LSM-tree架構的OLTP數據庫存儲引擎，其實現架構如圖2所示，其中單個數據庫可由多個LSM-tree實例組成（稱為subtable），每個實例存儲一個表或者索引或者分區表（table/index/table-partition），具體可參考2019年SIGMOD的論文[3]。LSM-tree將數據分為多個按照一定比例增長的層（level），分別位于內存以及磁盤，數據從上層到下層通過合并（compaction）的方式流動。鑒于DRAM是掉電易失的，其采用寫前日志（WAL）的方式將要寫入的數據提前寫入到磁盤中持久化，在內存中的數據刷入（flush）或者合并到磁盤后再清除對應的WAL。在典型的設計中，內存中的數據通常采用跳表（skiplist）實現，在大小超過限制后會被凍結（圖中Swtich操作以及immutable內存表）并轉儲到磁盤中并創建新的內存表。磁盤中的每層數據采用多個有序字符串表（SST，Sorted String Table）存儲，每個SST相當于一顆B樹。通常情況下同一層中的不同SST的鍵值對的范圍不發生交疊。但實際的系統中為了加速內存表的刷盤操作，通常允許部分層的SST存在范圍交疊，如LevelDB，RocksDB等均允許Level0存在交疊，但亂序的Level0層數據布局會降低讀取效率。

圖 2 X-Engine主要架構

3 機遇與挑戰

現有的基于LSM-tree架構的OLTP存儲引擎的設計通常存在以下幾個問題：（1）WAL位于寫入關鍵路徑中，尤其是為了滿足事務的ACID屬性，WAL通常以同步的方式寫入到磁盤，因而拖慢寫入的速度。此外，由于DRAM的易失性，設置過大的內存表雖然會提高系統的性能，但會導致WAL過大，影響系統的恢復時間。（2）level0數據塊通常允許亂序，以加快內存中數據的刷盤速度。但亂序的數據塊如果堆積過多，會嚴重影響讀取性能，尤其是范圍讀取性能。直觀上，可持久化字節尋址的PM可以用來實現持久化內存表，代替DRAM中的易失性內存表，從而減少維護WAL的開銷。然而實際上，由于PM本身的特性，實現高效的持久化索引依然存在較大挑戰，包括相應的PM內存管理。另外，當前PM硬件僅能保持8字節原子寫入，導致為了實現原子寫入語義，傳統方法依然需要引入額外的日志（又稱為PM內部日志）。

為了應對這些挑戰，該論文設計針對LSM-tree專用優化的高效PM內存管理器Halloc，提出了優化的基于PM的半持久化內存表用以替換傳統方案DRAM中的內存表，使用ROR無鎖免日志算法去除傳統方案依賴WAL保持事務的ACID屬性，設計全局有序的Global Index持久化索引層以及存內合并策略替換傳統方案的Level0層，提高查詢效率以及降低Level0數據維護的CPU和I/O開銷。論文中主要改進點如圖3所示，其中mem表示active memtable，imm表示immutable memtable，sp-前綴表示半持久化。這些設計主要帶來以下三點好處：（1）避免了WAL寫入以及PM編程庫引入額外內部日志，實現更快速的寫入；（2）PM中的數據直接持久化，避免了頻繁的刷盤以及level0的合并操作，且容量可以設置更大而不用擔心恢復時間；（3）level0數據全局有序，不必擔心level0的數據堆積問題。

圖 3 論文中的主要方案和傳統方案的對比

二 半持久化內存表

持久化索引的更新以及添加操作通常涉及PM中多個超過8字節的小的隨機寫入，因此引入用于維護一致性的開銷以及隨機寫入導致的寫放大問題。實際上，基于PM的索引的設計可以分為上表中的三類。無持久化是指將PM當作DRAM使用，此種方法可以保證索引處于最高的性能，但掉電數據即丟失。第二類是采用全持久化的方式，即索引所有的數據（索引節點以及葉子節點等）做持久化，如BzTree, wBtree等。該種方式可做到極速恢復，但持久化的開銷一般較大，性能通常較低。一個比較折中的方法是僅持久化必要的數據以換取性能和恢復時間的折中，例如NV-Tree和FPTree僅持久化葉子節點，索引節點在重啟時重建。而在LSM-tree結構中，內存表通常較小，因此采用半持久化的索引設計思想較為合適。論文中采用兩種方法用以降低維護持久化索引的維護開銷。

圖4 半持久化內存表結構圖

僅持久化葉子結點。在實際的應用場景中，云上基于LSM-tree的OLTP引擎通常不會設計較大的內存表，通常為256MB，這主要是由于以下兩個原因：（1）云上用戶通常會購買較小內存的數據庫實例；（2）LSM-tree需要維持小的內存表以保證快速的刷盤操作。對于256MB的內存表，我們發現將僅持久化葉子結點時重啟恢復非葉子結點的開銷小于10毫秒，其恢復時間相對于所研究的數據庫系統已足夠快。其次，該索引的設計中采用序列號以及用戶鍵分離的方式用于加速鍵的查找以及滿足內存表的MVCC (Multi-Version Concurrent Control)并發控制約束。如圖4所示，對于僅有一個版本的值（9）將直接在索引中存儲一個指向PM具體位置的指針，對于有多個版本的值，設計中使用可伸縮的數組用于存儲多版本序列號及其具體的指針。由于索引是易失的，鍵并不顯式存儲在索引中，且索引在重啟時通過掃描PM中的鍵值對重建。

批量順序寫入以降低寫放大。在PM中，小的隨機寫會被硬件控制器轉換成隨機的256字節的大塊寫，導致寫放大問題，進而消耗PM硬件的帶寬資源。鑒于內存表設計為順序追加的寫入方式，為了避免該問題，半持久化內存表通過將小的寫打包成大塊的寫（WriteBatch），并且順序地將該WriteBatch寫入到PM中，之后分別將其中的記錄寫入到易失性索引中。如圖4所示，batch表示一個大塊的WriteBatch寫入，slot用于記錄從Halloc分配器中分配的zone對象的ID。

三 ROR無鎖免日志事務提交算法

由于本文中memtable中的索引無需持久化，因此僅需保證數據的原子持久化即可。PM雖然可以提供字節尋址的可久化寫入，但其僅能提供8字節的原子化寫入（僅指intel optane DCPMM）。因此大于8字節的寫入操作存在部分寫（torn write）的風險。傳統的方案是采用數據即日志（log-as-data）保證原子寫入，如圖5所示，日志項順序寫入，且每個日志項寫入完成后更新8字節的head指針。由于head的更新總能由硬件保證原子性，因此head之前的日志項可以看作成功寫入；head之后的日志項存在部分寫風險，重啟時被丟棄。

該種方案存在兩個問題：（1）日志僅能順序寫入，不利于發揮多核系統的并行寫的能力；（2）日志項中存在不同生命周期的數據，導致日志項的回收較為困難。如圖5所示，log1中的數據寫入3個LSM-tree實例中，而其中不同的LSM-tree實例中memtable刷盤的時間不同，可能會導致某個LSM-tree實例寫入較少，進而刷盤周期較長，導致對應的log1長時間不能有效回收，降低PM的內存空間的利用率。

圖 5 傳統方案存在的問題

為了解決這些問題，文章提出ROR算法，其使用ChainLog數據結構分離數據生命周期，利用無鎖環（lock-free ring）實現日志的并發寫入。其中，為了進一步減針對PM的隨機寫入提高寫入的性能，ROR算法中采用batch的方式將小的ChainLog合并成更大的數據塊。如圖6所示，ChainLog保證任意大小數據寫入PM的原子性；batching用于聚合小的事務緩存批量寫入PM以減少PM的隨機寫；并發環提供針對ChainLog無鎖的流水線化寫入到PM中以提高多核系統的伸縮性。

圖 6 ROR算法整體框架

對于一個待提交的事務，其首先被封裝成一個WriteBatch。一個或者多個WriteBatch被進一步封裝成一個ChainLog，以批量寫入到PM中。本文中沿用LSM-tree原初的兩階段鎖2PL以及MVCC的事務并發控制策略。如圖6所示，ROR使用固定可調大小并發桶（bucket）用于控制并發寫入，其中第一個進入某個bucket的線程成為leader線程用于執行具體的寫入，其余進入該bucket的線程成為follow線程。Leader將自己以及屬于該bucket的所有follow線程的WriteBatch聚合成一個更大的WriteBatch用于實際的寫入。

ROR重點之一是ChainLog，其通過在8字節的head中加入識別日志生命周期的域以及標識寫入位置的域。可以通過標識寫入位置的域信息，定位到哪些ChainLog發生了部分寫，從而在重啟時丟棄。通過日志生命周期的域信息，可以使得ChainLog中寫入不同LSM-tree實例中的數據寫入到不同的內存空間相互隔離。另外，ChainLog在高層視角上總是串行的寫入，即一個ChainLog項僅當所有以前的ChainLogs都已持久化在PM中時才會被持久化。串行化的提交使得在系統恢復期間僅需檢查最后一個ChainLog項，以確保最后一個ChainLog的寫入是否發生部分寫。

首先考慮數據生命周期的分離，一種較為直觀的做法是針對每個LSM-tree實例設置單獨的head指針，如圖7所示，每個head負責指示其對應的內存空間的寫入位置。不同的內存空間相互分離，具有獨立的生命周期，其對應的LSM-tree中的memtable刷盤后可以立即回收而不需要等待其他LSM-tree實例。但該種做法存在一個明顯的問題，單個事務可能會寫入到多個LSM-tree，因此導致單次更新涉及到多個head的更新，進而硬件上無法保證寫入的原子性。

圖 7 日志項生命周期示例

為了解決這個問題，ROR在每個LSM-tree實例中用于指示寫入位置的8字節的head中加入如下的位置信息，圖8中的gidx即對應原始的8字節head指針。gidx指針中高4字節用于記錄上次寫入的位置，低4字節用于記錄當前寫入的位置。每4字節中6bit用于記錄memtable的slot，26字節用于記錄對應slot的偏移，總共可以尋址4GB的空間。一個ChainLog項寫入的數據分為n個子項，每個子項分別寫入對應的LSM-tree實例。每個子項中均記錄子項的個數以及當前ChainLog的LSN。

圖 8 gidx的結構示意圖

圖 9 中的例子展示了該過程，其中ChainLog2（R2）已經被成功提交，R3等待被提交。但在R3提交的過程中系統發生異常掉電，導致R3中子項r31被成功提交，但r32未能成功提交。在系統恢復時，通過掃描所有LSM-tree實例中的最后一個ChainLog子項，可以獲知當前最大的LSN為3。而r31已經成功提交，但其記錄的子項數為2，但r32未能成功寫入，因此其LSM-tree實例1的gidx會被回滾（通過簡單快速的右移運算）。回滾后r31被丟棄，LSN回退到2，此時系統恢復到全局一致性狀態。

圖 9 斷電恢復示意圖

由于ChainLog需要滿足串行化寫入語義，進而保證在重啟恢復時僅需掃描所有LSM-tree的最后一個ChainLog子項即可正確建立全局一致的狀態。保證串行化寫入語義的一種方法是串行寫入，但該方式無法利用多核平臺的高并發寫入的特性，其本質上是先建序后寫入的思想。ROR算法中采用寫入后建序，即每個線程在寫入的時候不關注序的問題。ROR算法會在此過程中動態的選擇主線程收集當前已寫完的ChainLog并建序。由于建序僅涉及到ChainLog元數據的更新，因此顯著提高寫入性能。主線程建完序后退出，ROR算法繼續動態選擇其他主線程進行該過程。該過程由lock-free ring以及lock-free的動態選主算法控制，具體細節讀者可以參考原始論文中的描述。

四 Global Index與輕量級存內合并

GI（Global Index）主要用于在PM中維護一個可變索引化的數據層用以替換磁盤中無序化的level0層數據。為了簡化實現，GI采用和內存表相同的易失性索引，并將數據放置在PM中。由于內存表同樣將數據放置在索引中，因此內存表的數據轉移到GI時無需數據拷貝，僅需更新GI索引中的指針指向內存表中的數據。值得注意的是，GI可以采用任意的范圍索引，或者持久化索引用以提高系統的恢復速度。鑒于GI的更新并不需要設計多個KV更新以及寫入的事務性需求，現有的無鎖免日志的范圍索引均可以應用到GI中。

存內合并：存內合并是指從內存表到GI的合并。GI采用和內存表相同的索引設計，即將鍵值對存儲到PM中，葉子結點采用伸縮的帶數據版本的數組用于存儲來自同一個鍵的數據。在存內合并時，如果在GI中不存在相同的鍵，則直接將該鍵插入到GI中；如果已存在，則需要在GI中檢查屬于該鍵多個版本并在需要時執行多版本清除操作，以節省內存空間。由于PM中的鍵值對都由Halloc管理，因此鍵值對粒度的內存釋放是不允許的。完成存內合并時，僅釋放內存表的內存。僅當GI中的所有鍵值對合并到磁盤時才批量釋放GI中的PM內存。

快照：通過快照技術，可以確保在GI合并到磁盤時，存內合并操作可以同時進行，以避免阻塞前段的操作。在快照的實現中，GI會凍結當前的數據并在內部創建一個新的索引用以吸收來自內存表的合并數據。該種設計避免了阻塞前端的操作，但由于查詢可能會涉及到兩個索引，導致額外的查詢開銷。

PM到磁盤的compaction：由于合并到磁盤的GI數據是不可變且全局有序的，因此PM到磁盤的合并操作并不會阻礙前端的操作。而且由于GI的全局有序性，合并操作可以通過范圍且分并行化，進而加快PM到磁盤的合并速度。

數據一致性：PM到磁盤的合并涉及到數據庫狀態的改變，可能在系統宕機時出現數據一致性問題。針對該問題，本文通過在磁盤中維護描述日志（manifest log）的方式保證數據庫狀態改變的數據一致性。由于描述日志不在前端寫入的關鍵路徑中，因此并不會影響系統寫入的性能。

五 Halloc內存分配器

Halloc是針對LSM-tree專用的PM內存分配器，其通過三個關鍵技術以解決傳統通用PM內存分配器存在的效率低、碎片化等問題，基于對象池的內存預留方案、應用親和的內存管理以及統一化地址空間管理。其主要架構如圖10所示，halloc通過直接創建DAX文件劃分自己的內存地址以及管理自己內部的元數據信息，在地址空間上劃分為四個區域分別存儲Halloc元數據信息、subtable元數據信息、內存表元數據信息以及若干內存快用于具體的內存使用。

圖 10 Halloc內存分配器總體架構圖

基于對象池的內存預技術。Halloc通過靜態預留固定大小的對象池且內存地址互不交疊的地址空間以減少PM管理中存在的內存碎片問題。每個對象池包含元數據區用于記錄對象的分配情況，freelist持久化鏈表用于追蹤空閑的對象，固定大小的對象區且其大小由創建對象池時顯式指定。由于對持久化鏈表的操作設計到多個不連續的大于8字節的PM寫入操作，因此存在數據不一致的風險。傳統的方案使用PMDK以及Mnemosyne等內部日志保證操作的事務性，但改種方案會引入額外的日志開銷。為了消除該日志開銷，本文提出以下方案保證freelist操作的數據一致性。

圖 11 freelist內部結構圖

如圖11所示，對于一個freelist，其在內存空間上是連續存儲的，包括元數據區用于記錄分配情況，通過索引區用于索引空閑的對象，以及對象區用于存儲具體的對象。每個對象對應一個8字節的索引，每個索引的最高位用于標記該對象的持久化情況以確保原子化的對象分配與釋放。Freelist提供四個接口用于完成一個對象的分配與釋放：Get用于從freelist中獲取一個對象，Commit用于通知Halloc該對象已完成初始化可以從freelist中移除，Check用于檢測某個對象是否已被持久化避免故障重啟時出現對象錯誤引用，Release用于釋放一個對象。核心思想是通過在對象的索引設置持久化標志，已在重啟時通過掃描識別出泄漏的對象。

對于對象池的啟動恢復，Halloc首先掃描freelist的對象并在bitmap中標記，之后在掃描index域確認該對象是否在freelist中可達。對于不可達的對象將被回收。該種設計一定程度上增加了重啟的開銷，但實際上該過程掃描很快，實驗中掃描數百萬個對象僅花費幾毫秒時間。重啟開銷在所研究的系統中可以忽略不計。

應用親和的內存管理。Halloc對于LSM-tree提供兩種對象池服務：自定義對象池以及zone對象池。該種設計主要基于LSM-tree對于內存使用的獨有的追加寫以及批量回收的方式，對于內存的管理有較大的簡化。對于自定義對象池，如圖 8 所示，Halloc維護了memtable以及subtable池分別用于存儲引擎中的內存表元數據和subtable元數據。一個subtable對象包含一個鏈表用于記錄其所有擁有的memtable對象（通過memlist鏈接），其中第一個memtable對象為活動內存表，其余為凍結內存表。每個memtable對象索引有限個zone對象，每個zone對象記錄具體的memtable數據。zone對象池是Halloc內建的對象池用于應用自己按照自己的方式管理內存，該設計主要是因為自定義對象池僅能存儲有限的且固定大小的對象。鑒于Halloc并非針對于通用PM內存分配，對于可變大小且為止數量對象的管理，應用需要自己基于zone對象池實現自己的內存管理方案。

統一化地址空間管理。 為了便于易失性以及可持久性內存的聯合管理，Halloc在單一DAX文件地址空間上同時支持持久化內存分配以及易失性內存分配，從而大大簡化了PM資源使用。類似于libmemkind，Halloc同樣適用jemalloc用于接管具體可變大小的易失性內存的分配。不同的是，Halloc使用zone作為jemalloc的基本內存管理單元，即jemalloc總是從zone pool中獲取zone對象并進一步細化管理。其從zone pool中分配的對象不再調用Commit，從而其所有分配的zone對象在系統重啟后將全部被回收。該種設計方案的一個較大的限制是用戶分配的易失性內存大小不能超過單個zone的大小，因為zone對象池僅能保證單個的zone的內存地址的連續性。然而對于較大的內存分配，用戶可以選擇拆分的方式多次分配，或者如果對象大小固定且數量有限使用自定義對象池進行靜態分配。

六 實驗評估

實驗平臺。實驗采用阿里云實例規格為ecs.ebmre6p.26xlarg。該實例具有兩顆Intel(R) Xeon(R) Platinum 8269CY CPUs，每個CPU具有52個核心，共104核心。每個核心有一個32KB的L1緩存，一個1MB的L2緩存。每個CPU上所有的核心共享一個32MB的L2緩存。實例另有187GB的DRAM以及1TB的PM。PM被平均分配到兩顆CPU，即每個CPU裝備512GB的PM。實例總共配置2TB的ESSD作為云硬盤。實驗中將所有的PM配置為兩個linux設備，每個設備分別屬于一個CPU。所有的實驗運行的linux內核版本為4.19.81。

參數配置。如無特別說明，實驗中設置單個內存表的大小為256MB，單個subtable的GI的最大為8GB，單個subtable的level1為8GB。改進前的系統配置256MB的level0。所有的實驗均采用同步的WAL，使用Direct I/O以旁路掉page cache對系統的影響，關閉壓縮以盡量評測系統的最大性能表現。

1 綜合評估

該實驗首先采用YCSB標準的測試基準，共預先在數據庫中加載80億記錄，平均分配到16的subtable，每個記錄有8字節的key以及500字節的value，總共約500GB的數據量。實驗中配置了4種配置：（1）基準系統且所有數據均放置到ESSD中（標記為XS），（2）改進的方案且配置使用200GB的PM空間由Halloc管理（標記為XP），（3）基準系統且將所有的數據放置在速度更快的PM中（標記為XS-PM），（4）改進的方案且將原先放置于ESSD中的數據放在PM中（標記為XP-PM）。配置（1）以及配置（2）是系統實際使用時的標準配置；而配置（3）以及配置（4）是主要用于評估移除ESSD后的系統性能表現。每個實驗使用32個client線程，設置50GB row cache以及50GB的block cache，且運行30分鐘以保證系統compaction得到及時的運行。

圖 12 YCSB實驗結果

實驗結果如圖12所示，對于寫密集型的負載A且隨機請求下，XP/XP-PM的性能是XS/XS-PM的3.8以及2.3倍；在寫密集型的負載F且隨機請求下，XP/XP-PM的性能是XS/XS-PM的2.7以及2.2倍。且在圖10中顯示，XP的平均訪問延遲要比XS低36%。在負載傾斜的情況下（Zipf=1），XP與XS性能表現接近，并且XP-PM表現要比XS-PM更低。這些結果表明，本文的方案對比基準系統在整體上性能表現更優異且產生更少的磁盤I/O。然而XP-PM的表現和XS-PM的表現差距不大，尤其是在負載傾斜下，XP-PM表現的不如基準系統XS-PM。但實際上該配置將數據全部放置于PM中，因為成本較為高昂，實際中不會采用。

對于讀密集型的應用（B，C，D，E），在負載B且隨機請求下，XP/XP-PM比XS/XS-PM性能分別高1.7倍及1.2倍，在負載D中分別高1.4倍以及1.1倍，并且擁有更低的延遲，負載B的平均延遲降低39%，負載D的平均延遲降低26%。這主要是因為XP不需要寫WAL日志，因此具有更低的寫入延遲。負載傾斜時，XP的性能收益降低。在負載B中，XP/XP-PM性能對比XS/XS-PM僅提高1.1倍以及1.5倍。在負載C以及負載E中，由于寫入較少，此時數據全部被合并到ESSD中，因此XP/XP-PM對比XS/XS-PM性能表現相似。

圖 12（續） 系統延遲以及CPU、IO開銷

CPU以及I/O消耗。圖12(c)中展示了在運行YCSB load以及A負載時的CPU消耗以及累積I/O情況。結果展示，XP擁有更好的CPU使用效率，且在運行A負載時，其I/O的消耗相對基線系統降低了94%。主要原因為XP采用更大的GI用于緩存更多的更新在PM中，因而減少數據的刷盤操作。

圖 13 系統延遲以及CPU、IO開銷

數據庫大小敏感性。為了測試改進系統的性能收益與數據庫大小的關系，實驗分別注入100-600GB大小的數據，之后運行D負載。結果表明，如圖13所示，數據庫大小從100GB增大到600GB時，基線系統XS的性能下降了88%，而XP僅下降27%。主要是因為負載D盡可能讀取最近的更新，而XP會將熱數據放置在高速的持久化的PM中，而基線系統XS在每次啟動系統進行測試時均需要從慢速磁盤中讀取數據。

圖 14 單LSM-tree實例的實驗結果（40GB dataset）

單個LSM-tree實例測試。為了同現有的最新的使用PM改進LSM-tree的方案進行對比，實驗中選擇SLMDB以及NoveLSM進行對比。鑒于SLMDB以及NoveLSM均不支持同一個數據庫中運行多個LSM-tree實例，本次僅設置單個subtable。實驗中使用4個client且加載40GB的數據。測試結果表明，如圖14所示，XP擁有更高的數據加載性能，為SLMDB的22倍，NoveLSM的7倍。主要是因為SLMDB以及NoveLSM雖然使用持久化skiplist作為內存表，但涉及到事務處理時，仍然依賴WAL以保證事務的原子性，另外兩者均不支持并發寫入。SLMDB使用單層的結構以及全局的持久化B+tree用于索引磁盤上具體的數據。該種設計雖然能夠提高數據的讀取性能，但寫入時涉及到磁盤以及PM中持久化索引的一致性維護，因而寫入性能較低。NoveLSM僅引入持久化內存表，因此性能提升較為有限（PS：不是很novel）。

圖 15 TPC-C實驗評估結果

TPC-C性能表現。實驗中將改進的方案集成到MySQL中作為一個存儲引擎的插件，并預先加載80GB的初始數據庫大小，之后啟動TPC-C測試30分鐘。實驗結果顯示（如圖15），XP相對XS的TPS性能提高到2x，且P95延遲降低了62%。主要是因為XP避免了WAL的寫入，且擁有更大的PM以緩存更多的數據。然而XP在TPS的表現上相對于XS抖動更大，主要是因為XP更傾向于執行level0到level1的all-to-all compaction策略，從而導致更劇烈的cache淘汰行為。如何平衡compaction和cache的淘汰策略是未來一個比較重要的方向。

2 半持久化內存表評估

為了評估改進的方案中半持久化內存表的性能，實驗中關閉系統所有后臺的flush以及compaction操作，設置ROR的batch=50以盡量旁路掉ROR的影響（batch=50已接近PM硬件性能極限）。實驗中主要對以下索引方案：（1）基于DRAM的skiplist，基線系統默認的內存表索引類型（標記為SLM）；（2）基于FAST&FAIR實現持久化內存表（標記為FFM）；（3）基于FPTree的變種（本實驗中采用OLC實現并發操作，原始的FPTree采用HTM以及leaf lock實現并發操作）實現的半持久化內存表（標記為FPM）；（4）本文方案，且使DRAM存儲索引節點（標記為SPM-D）；（5）本文方案，且使用PM存儲索引節點（標記為SPM-P）。方案（4）以及（5）用于檢測將PM作為非持久化使用時的內存表性能表現。FAST&FAIR以及FPTree是一種針對PM優化的持久化B+tree，其中FPTree僅持久化葉子結點，因而同樣為半持久化索引的一種。由于FAST&FAIR以及FPTree均不支持可變大小的key，因此本實驗對于這兩種內存表添加一個運行時KV解析的流程，即索引中僅存儲固定大小的KV對的指針。實驗中插入3000萬個KV對，8字節key，32字節value，總計約1.5GB數據。KV對在內存表中將被轉換成17字節的key，以及33字節的value。

圖 16 內存表性能評估結果

insert性能：圖16(a)(b)展示了不同內存表在并發線程從1增加到32時的寫入性能表現。結果顯示，在寫入時SPM-D以及SPM-P的差別很小，即使SPM-P將索引節點放置在速度更慢的PM中，主要是因為持久化開銷相對較大，是主要影響因素。另外，對于SLM/FFM/FPM，SPM-D在順序寫入上分別提升5.9x/5.8x/8.3x，在隨機寫入上分別提升2.9x/5.7x/6.0x。即使LSM將索引放置在速度更快的DRAM中，SPM-D/SPM-P相比依然具有較大的性能提升，主要是因為SPM采用基數樹索引，具有更好的讀寫效率。即使FPM同樣將索引節點放置在速度更快的DRAM中，但其在本文實現中依賴運行時的KV解析以從速度更慢的PM中加載具體的KV數據。

lookup性能：表16(c)展示了點讀的性能表現，在該實驗中SPM-D相對SLM/FFM/FPM性能提升分別達到最高2.7x/14x/16x。對于點讀場景，SPM采用前綴匹配，然而SLM/FFM/FPM均采用二分查找的方式。對于key普遍較短的場景下，基數樹顯然具備更高的讀取效率。雖然FPM在葉子結點中采用基于哈希的指紋標識技術以加速點讀性能，實際在內存表中，點讀會被轉換成短的范圍查詢用以獲取對應key的最新的版本，因此FPM中的指紋技術難以發揮作用。此外，FPM葉子結點采用亂序存放的策略以犧牲一定的讀取效率換取寫入速度的提升。SPM-D在點讀場景下比SPM-P更高，其主要因為SPM-P將索引節點放置在速度更慢的PM中，在讀取時，索引性能受限于PM的讀取帶寬限。對于范圍查詢性能（圖16(d)），SPM-D以及SPM-P表現均不如SLM。雖然在DRAM中基數樹的范圍查詢性能普遍不高，但在本次實驗中發現其性能更多是受限于PM的讀取帶寬。實際上，在進行系統分析表明，在范圍查詢時，SPM-D從PM讀取數據消耗了70%的時間占比。

3 ROR評估

ROR主要影響系統的寫入性能。為了減少系統后臺任務的干擾，實驗中關閉所有的flush以及compaction操作，關閉內存表中的建索引操作。每個線程寫入100萬個大小為24字節的KV對。實驗通過設定不同的線程數以及batch的大小用以評估這些參數對系統寫入性能的影響。

圖 17 ROR算法評估結果

batch的影響：在表17(a)對應的實驗中，通過固定線程數為32，改變batch size的大小以測試batch size對系統寫入性能以及延遲的影響。結果表明，調節batch size從1到90時，系統的寫入吞吐增長到49x，而平均延遲以及P99延遲分別凈增加1.3x以及1.7x。在batch size=90時，其寫入的吞吐量甚至超過PM硬件的隨機寫入24字節的吞吐，主要是因為ROR總是盡量采用順序寫的方式。當batch size從50增加到90時，其性能收益增長較為緩慢，而延遲增加較大，主要是因為此時PM的硬件接近飽和。當batch size大于90時，系統的吞吐量不升反降，這主要是由于大的batch會導致ROR阻塞，進而影響寫入的吞吐。

線程數的影響：實驗中固定batch size=50，調節線程數從1增加到64。圖17(b)中的結果表明，在線程數從1增加到16時，其吞吐量呈線性增加。但當線程數大于16時，性能增長較為緩慢，比如線程數從16增加到64時，吞吐增加到1.1x，但P99延遲上升到2.9x。主要是因為較多的線程并發寫入導致對PM硬件的訪問競爭加大。實際中，選取合適的線程數以及batch size需要根據具體的硬件設備以及工作負載。

4 Global Index評估

圖 18 全局索引GI評估結果

實驗中關閉level0到level1的compaction，以評估GI相對于XS的亂序level0的優勢，其中XS-PM表示將基線系統的level0以及WAL放入PM中。實驗首先隨機寫入不同大小的KV對，大小從64字節到4KB，總計50GB的數據，并測試隨機點讀以及范圍查詢的性能表現。圖15(a)表明，對于不同大小的KV對的隨機寫，XP都優于XS以及XS-PM。在圖18(b)(c)中，XP相對于XS以及XS-PM有巨大提升，隨機讀性能為XS-PM的113x，隨機范圍查詢是XS-PM的21x。其主要是因為實驗中關閉了level0到level1的compaction，導致level0堆積過多的亂序的數據塊（實驗中觀測超過58的亂序數據塊）。由于XP中GI是全局有序的，因此具備較高的查詢性能。

另一個實驗使用32個client線程采用讀寫比為1:1的方式高壓力寫入數據，運行10分鐘并觀察系統性能隨時間的變化。圖18(d)并表明，XP相對于XS/XS-PM性能提升高達15x，并且性能表現更穩定。在實驗中，XS以及XS-PM性能降低了85%，而XP僅降低35%。雖然XS-PM將數據放在速度更快的PM中（將PM用作普通磁盤），但其性能表現相對于XP仍具有較大差距，并且level0數據堆積依然會產生較大的影響。而XP采用全局有序的GI以及更高效的in-memory compaction，大大降低level0的數據堆積的影響。

5 Halloc評估

圖 19 Halloc評估結果

本實驗通過對比Ralloc以及pmemobj以評估Halloc的持久化內存分配性能。Halloc將非持久化內存的管理托管到jemalloc中，因此其性能表現與同類方法相似。讀者可以進一步參考文獻[4]以了解更多將PM用作非持久化內存的分配器的性能表現。實驗運行在單線程下，通過執行100萬次內存分配計算單次分配的延遲，分配對象的大小從128字節到16KB。由于Halloc并非通用內存分配器，實驗中通過從對象池中分配（Halloc-pool）以及通過grant（Halloc-zone）分別模擬通用內存分配的malloc操作。圖19表明，Halloc-pool以及Halloc-zone在所有的測試中分配對象的延遲均小于1us，主要是因為Halloc對每次分配僅使用一個flush以及fence指令。但Halloc僅被設計用來支持基于LSM-tree的系統，通用性不如Ralloc以及pmemobj。

6 重啟恢復表現

圖 20 重啟恢復性能表現評

為了評估系統的恢復性能，實驗中寫入32GB的數據，其中key/value的大小分別為8字節/500字節，總計7000萬個KV對。實驗中GI采用非持久化索引，并保持數據全部落在GI。非持久化的GI使得系統重新啟動時需要恢復GI中的所有索引，因而等價于需要恢復32GB的內存表。對于基線系統XS以及XS-PM（將WAL放置在PM中），系統關閉flush，因而保證至少32GB的有效WAL。由于XP可以并行的重建索引，實驗中設置恢復線程的數量從1逐漸增加到104（所有的CPU core）。圖20表明，XP通過并行重建索引可以實現近秒級啟動，然而XS以及XS-PM均需要耗費數分鐘級的時間，其中一個比較重要的原因是基線系統僅支持單線程恢復。由于XP可以并行恢復，因此可以在系統啟動時利用全部的CPU資源以加快啟動速度。實際的應用場景中，內存表的大小通常遠小于32GB，因此恢復時間可達秒級以下。極速的數據庫可恢復性也許可以改變現有的通過主備等方式實現HA的方案，進而省略備用節點，具備降低一半的ECS實例潛能。

七 后記

本文僅僅是應用PM等新硬件，針對基于LSM-tree的OLTP存儲引擎進行優化探索而邁出的一小步。實際上實現一個可用的工業級存儲引擎涉及很多方面，如可靠性、可用性、穩定性、性價比等，更多是尋找多方面因素的一個平衡的過程。而就本文中的方案，在實際的工業落地中依然存在以下亟待解決的問題。

• 數據可靠性問題。對于數據庫系統，數據可靠性處于極其重要的位置。PM雖然能夠提供持久化的字節尋址能力，但其依然存在設備寫入磨損、硬件失效等影響數據可靠性的問題。云上數據庫實例中，傳統的持久化存儲層通過多副本及分布式共識協議等方式實現高可靠性的數據存儲，因此將PM作為持久化存儲時依然需要解決該問題。一種可期望的解決方案是構建基于PM的高可靠的分布式持久化內存池，但分布式化的PM內存池如何設計，可能具有何種I/O特性等仍需要進一步探索。面對工業化落地時，在OLTP存儲引擎設計中針對單機PM硬件優化持久化索引意義可能不是很大。
• PM內存使用效率問題。在該論文中，PM的內存可以用于持久化目的以及非持久化目的，但在固定PM容量下，如何確定多少內存空間分配給持久化使用，多少空間用于非持久化目的等是一個值得進一步探索的問題。例如，根據負載自動調節空間的分配比例，在寫密集的負載中分配更多的PM內存用于持久化存儲，在讀密集型負載分配更多的內存用于cache等非持久化目的。
• 性能抖動問題。對于基于LSM-tree的存儲引擎，一個讓人頭疼的問題就是性能抖動問題，而產生抖動的一個重要原因是后臺compaction導致的cache批量劇烈的失效。在分布式場景中可以通過smart cache[5]等方式緩解該問題，在單機情況下，是否可以通過在PM中分配單獨的緩存空間用于臨時緩存compaction的舊數據，之后緩慢的執行cache的替換？

延伸閱讀

[1] J. Yang, J. Kim, M. Hoseinzadeh, J. Izraelevitz, and S. Swanson, “An empirical guide to the behavior and use of scalable persistent memory,” in Proceedings of the 18th USENIX Conference on File and Storage Technologies (FAST ’20), 2020, pp. 169–182.

[2] B. Daase, L. J. Bollmeier, L. Benson, and T. Rabl, “Maximizing Persistent Memory Bandwidth Utilization for OLAP Workloads,” Sigmod, no. 1, p. 13, 2021.

[3] G. Huang et al., “X-Engine: An optimized storage engine for large-scale e-commerce transaction processing,” in Proceedings of the ACM SIGMOD International Conference on Management of Data, Jun. 2019, pp. 651–665.

[4] D. Waddington, M. Kunitomi, C. Dickey, S. Rao, A. Abboud, and J. Tran, “Evaluation of intel 3D-Xpoint NVDIMM technology for memory-intensive genomic workloads,” in ACM International Conference Proceeding Series, Sep. 2019, pp. 277–287.

[5] M. Y. Ahmad and B. Kemme, “Compaction management in distributed keyvalue datastores,” Proc. VLDB Endow., vol. 8, no. 8, pp. 850–861, 2015.

原文鏈接
本文為阿里云原創內容，未經允許不得轉載。?

總結

以上是生活随笔為你收集整理的如何将一棵LSM-Tree塞进NVM的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。