李潤輝 古 亮 喻之斌

1(中國科學(xué)院深圳先進技術(shù)研究院 深圳 518055)

2(深信服科技股份有限公司 深圳 518071)

1 引 言

近年來，隨著移動互聯(lián)網(wǎng)、人工智能及物聯(lián)網(wǎng)等新興技術(shù)的迅速發(fā)展，對海量數(shù)據(jù)的存儲需求也隨之變大，數(shù)據(jù)規(guī)模遠(yuǎn)超傳統(tǒng)業(yè)務(wù)。如，在安防領(lǐng)域，基于人工智能的人臉識別技術(shù)識別出視頻流中的人像，并以小文件/對象的形式保存在底層的文件/對象存儲系統(tǒng)中，從而產(chǎn)生每秒創(chuàng)建數(shù)千個文件/對象的業(yè)務(wù)流量峰值，遠(yuǎn)超傳統(tǒng)的監(jiān)控視頻存儲，這對存儲系統(tǒng)的元數(shù)據(jù)訪問性能和承載規(guī)模提出了嚴(yán)峻的考驗。在存儲系統(tǒng)中，元數(shù)據(jù)的訪問量遠(yuǎn)超數(shù)據(jù)，且提供了并發(fā)控制等復(fù)雜邏輯，因此，元數(shù)據(jù)的訪問性能和承載規(guī)模也決定了存儲系統(tǒng)的訪問性能和承載規(guī)模的上限。

鍵值存儲，是承載文件/對象存儲元數(shù)據(jù)等關(guān)鍵信息的存儲系統(tǒng)核心組件，對其訪問性能和承載規(guī)模提升的研究具有重要意義。

分布式鍵值存儲，具有更高的性能、更好的容錯性和擴展性，因而被廣泛使用。其將數(shù)據(jù)復(fù)制到多個存儲服務(wù)器的本地鍵值存儲引擎(簡稱“本地引擎”)上，并通過一致性協(xié)議來保證不同副本的一致性。在業(yè)界被廣泛應(yīng)用，且滿足強一致性的一致性協(xié)議(如 Paxos[1]、RAFT[2])，均基于日志復(fù)制。這類一致性協(xié)議(簡稱“一致性協(xié)議”)在處理寫請求時，各副本首先持久化請求到本地的日志中，當(dāng)足夠多的副本寫日志成功后，才將數(shù)據(jù)更新到存儲于本地引擎的狀態(tài)機中。基于日志結(jié)構(gòu)合并(Log-Structured Merge，LSM)樹的本地引擎(如 LevelDB[3]、RocksDB[4])，能夠?qū)⑿?I/O 轉(zhuǎn)化為順序追加寫操作，對于底層硬件更為友好，因而被廣泛使用。使用 RAFT 等強一致性協(xié)議，及 RocksDB 等基于 LSM 樹的本地鍵值存儲作為本地引擎，成為了多個主流開源分布式鍵值存儲系統(tǒng)(如TiKV[5]、Cassandra[6])的選擇。然而，為通用業(yè)務(wù)模型設(shè)計的本地引擎，其沒有充分適配一致性協(xié)議的訪問模式，所以還存在較大的優(yōu)化空間。本文在分布式鍵值存儲的實踐中，發(fā)現(xiàn)并歸納出了如下問題：

(1)基于 LSM 樹的本地引擎為了提供容錯性，會將請求先寫入在本地持久化的預(yù)寫式日志(Write-ahead log，WAL)中，再更新內(nèi)存數(shù)據(jù)。當(dāng)系統(tǒng)發(fā)生異常重啟時，本地引擎可以通過WAL 修復(fù)丟失的內(nèi)存數(shù)據(jù)。然而，一致性協(xié)議的日志，也具備通過回放修復(fù)狀態(tài)機至最新狀態(tài)的能力。此時，修復(fù)同一份數(shù)據(jù)，需要兩次持久化的保護，這一雙寫會帶來高達(dá) 47.5% 的性能損耗(見第 5.3 節(jié))。能否通過改造底層引擎，配合一致性協(xié)議，消除雙寫，來達(dá)到提升分布式鍵值存儲性能的目的呢？

(2)一致性協(xié)議的修復(fù)方法有兩種：通過重放日志進行增量修復(fù)，以及復(fù)制狀態(tài)機進行全量修復(fù)。其中，全量修復(fù)需要刪除舊狀態(tài)機，并從其他節(jié)點復(fù)制新狀態(tài)機。LSM 樹的刪除操作異步回收空間，導(dǎo)致新舊狀態(tài)機數(shù)據(jù)長期并存，直到舊狀態(tài)機數(shù)據(jù)全部被異步刪除，這樣會造成存儲空間浪費嚴(yán)重。在實驗中，全量修復(fù)會帶來超過 60% 的空間浪費(見第 5.3 節(jié))。為維持系統(tǒng)的正常運行，存儲服務(wù)器必須在物理設(shè)備尚余大量存儲空間的情況下，就停止服務(wù)，以防全量修復(fù)耗盡存儲空間，預(yù)留空間造成存儲容量的嚴(yán)重浪費。能否通過對底層引擎的改造，使得全量修復(fù)過程能夠?qū)崟r回收空間，消除空間放大，從而避免預(yù)留過多的空間呢？

為了解決以上兩個問題，本文提出了基于LSM 樹改進的 PheonixLSM 本地引擎。具體貢獻(xiàn)如下：(1)通過增加 LSM 樹的增刪改操作和內(nèi)存數(shù)據(jù)回刷順序的制約，并提供新的查詢接口，使得一致性協(xié)議日志能夠同時起到 WAL 的作用，恢復(fù)本地引擎的內(nèi)存數(shù)據(jù)，從而避免日志和WAL 的雙寫，同時可將上層分布式鍵值存儲吞吐提高 90% 以上，單位計算資源吞吐提高 20%以上。(2)通過改造 LSM 樹的底層數(shù)據(jù)組織形式和范圍刪除邏輯，使得在對舊狀態(tài)機的刪除操作中，能夠?qū)崟r回收空間，使全量修復(fù)過程中的空間放大從 65.6% 降低到 6.4%，并節(jié)省 72.3% 的修復(fù)時間。

本文后續(xù)內(nèi)容的組織如下：第 2 節(jié)列舉相關(guān)工作；第 3 節(jié)介紹技術(shù)背景；第 4 節(jié)說明PheonixLSM 的設(shè)計；第 5 節(jié)說明 PheonixLSM的原型實現(xiàn)和部署，實驗結(jié)果以及分析；第 6 節(jié)對本工作進行了討論分析；第 7 節(jié)總結(jié)全文。

2 相關(guān)工作

本節(jié)首先列舉了常見的本地鍵值存儲系統(tǒng)以及核心數(shù)據(jù)結(jié)構(gòu)，然后對 LSM 樹的優(yōu)化改造方向進行了歸納。

本地引擎有多種形態(tài)，有將數(shù)據(jù)存儲于內(nèi)存的 Redis[7]、Memcached[8]和 MemC3[9]等，也有將數(shù)據(jù)持久化于本地存儲(機械硬盤或固態(tài)硬盤)的 LevelDB[3]和 RocksDB[4]等。B＋ 樹[10]和 LSM樹是兩種常見的持久化引擎的核心數(shù)據(jù)結(jié)構(gòu)。B＋ 樹的數(shù)據(jù)全量存儲在首尾相連的葉子節(jié)點中，具有良好的讀和范圍查找性能，MySQL 的本地引擎 MyISAM[11]、InnoDB[12]等都基于 B＋樹。然而，B＋ 樹不適用于隨機插入操作，其會產(chǎn)生大量的隨機小 I/O。相比之下，LSM 樹能將隨機小 I/O 轉(zhuǎn)為連續(xù)大 I/O，寫性能較好，且能較好地平衡讀放大、寫放大和空間放大，近年來得到了廣泛應(yīng)用。LSM 樹最早應(yīng)用在 Google推出的 LevelDB[3]中，被用作核心數(shù)據(jù)結(jié)構(gòu)，F(xiàn)acebook 此后推出了 RocksDB[4]，該結(jié)構(gòu)在LevelDB 的基礎(chǔ)上針對固態(tài)盤做了許多優(yōu)化。

近年來，基于 LSM 樹的存儲引擎被廣泛應(yīng)用在 Facebook[13-14]等企業(yè)的諸多場景中。關(guān)于 LSM 樹的寫放大問題：PebblesDB[15]放寬了LSM 樹的約束，使 L1及更低層中，SST 文件的 key 范圍可以適度重合，從而降低寫放大；WiscKey[16]采用了鍵值分離的策略，解決大 value帶來的索引效率低，以及寫放大嚴(yán)重的問題。關(guān)于 LSM 樹如何適配新硬件：增加 NVMeSSD 作為緩存層提升性能[17]，使用 FPGA 卸載合并任務(wù)，減少對讀寫業(yè)務(wù)的影響[18]等。關(guān)于 LSM 樹讀性能：采用動態(tài)布隆過濾器減少磁盤 I/O[19]，針對 LSM 樹的數(shù)據(jù)結(jié)構(gòu)開發(fā)新緩存策略[20]，優(yōu)化范圍查詢中的讀放大[21]，調(diào)度后臺回刷合并工作以減少對上層業(yè)務(wù)的干擾，降低尾時延[22]等。

3 技術(shù)背景

本節(jié)首先介紹分布式鍵值存儲的主要組成部分，然后介紹 LSM 樹的基礎(chǔ)，最后以 RAFT 為例介紹基于日志復(fù)制的一致性協(xié)議。

分布式鍵值存儲將鍵值對存儲在通過網(wǎng)絡(luò)互相連接的存儲服務(wù)器上，從系統(tǒng)架構(gòu)上分為 3個主要組件：分布式路由、一致性協(xié)議和本地引擎。

圖 1 是一個典型的分布式鍵值存儲的架構(gòu)及請求處理流程。分布式路由模塊將 key 空間映射到多個復(fù)制組，任意 key 都會被映射到唯一的復(fù)制組。如，當(dāng)寫入鍵值對時，分布式路由模塊確定 foo 所屬的復(fù)制組，以及該復(fù)制組節(jié)點所在的服務(wù)器；之后，對應(yīng)的復(fù)制組通過一致性協(xié)議，將鍵值對寫入各復(fù)制組節(jié)點所在的服務(wù)器的本地引擎中。查詢操作也通過分布式路由模塊確定 key 所屬的復(fù)制組，之后再對應(yīng)復(fù)制組讀取數(shù)據(jù)。

圖1 分布式鍵值存儲架構(gòu)及請求處理流程Fig. 1 Architecture of distributed key-value storage and the request processing flow

3.1 LSM 樹的基礎(chǔ)

LSM 樹的結(jié)構(gòu)及鍵值對生命周期如圖 2所示，其主要由 3 部分組成：內(nèi)存數(shù)據(jù)結(jié)構(gòu)Memtables，以及持久化的 WAL 和 SST 文件。SST 文件被組織成不同的層(L0層、L1層等)。

圖2 LSM 樹以及鍵值對的生命周期Fig. 2 LSM-tree and lifecycle of key-value pairs

寫請求首先持久化到 WAL 中，之后鍵值對被插入全局唯一的可讀寫 Memtable 中，請求完成。當(dāng)可讀寫 Memtable 中的數(shù)據(jù)量超過一個閾值時，其轉(zhuǎn)為只讀，后續(xù)請求的鍵值對被寫入新的可讀寫 Memtable 中。只讀 Memtables 中的鍵值對會在后臺的回刷和合并操作中逐層下沉至底層。

合并操作選擇 Li－1(i≥1)層的某些 SST 文件，以及 Li層與該 SST 文件的 key 區(qū)間有重合的 SST 文件。合并后的鍵值對，將按 key 的字典序?qū)懭胄碌?Li層的 SST 文件中，當(dāng) Li－1及 Li層中都有某個 key 的鍵值對時，在合并操作后只有最新的鍵值對會被保留，SST 文件視圖更新，舊SST 文件被刪除。

查詢操作會按寫入從新至舊的順序依次查找 Memtables 和 L0中的各 SST 文件，然后從 L1開始逐層向下查找。當(dāng)查找到對應(yīng) key 的鍵值對時，查詢操作完成。若查詢至底層時仍沒有與之對應(yīng)的鍵值對時，則返回 key 不存在。

LSM 樹的刪除請求和寫請求流程相同，但是刪除請求插入的是一條存儲特殊 value 的墓碑鍵值對。當(dāng)查詢操作讀到墓碑鍵值對時，立即返回 key 不存在(如圖 2 中的 foo2)。范圍刪除采用同樣的方法，插入一個特殊的范圍刪除墓碑鍵值對，當(dāng)查詢的 key 在該墓碑標(biāo)記的范圍內(nèi)時，則返回 key 不存在(如圖 2 所示，當(dāng)查詢 foo6 時，由于其處于范圍刪除墓碑鍵值對[foo5, foo9]的范圍內(nèi)，因此查詢也會返回 key 不存在)。

3.2 基于日志復(fù)制的一致性協(xié)議

一致性協(xié)議為復(fù)制組提供了強一致性保證，使復(fù)制組即使在故障場景下，依然能夠?qū)ν馓峁┮恢碌臓顟B(tài)機視圖。本文以 RAFT 協(xié)議為例對一致性協(xié)議的基本原理作簡要說明①：本文雖然以 RAFT 作為一致性協(xié)議的代表進行說明，但本文中的技術(shù)同樣適用于其他的基于日志復(fù)制的一致性協(xié)議。。

RAFT 協(xié)議定義了一個復(fù)制組中若干節(jié)點的交互行為。在穩(wěn)定狀態(tài)下，復(fù)制組中有一個主節(jié)點和若干個從節(jié)點。每個節(jié)點中有一致性模塊、日志和狀態(tài)機 3 個主要組件。狀態(tài)機是一個抽象概念，其在分布式鍵值存儲中是本地引擎的鍵值對集合。

圖 3 為 RAFT 協(xié)議處理增刪改操作的流程。請求首先被發(fā)送至主節(jié)點(步驟 1)，主節(jié)點的一致性模塊為其分配一個系統(tǒng)生命周期遞增的日志索引，并將請求轉(zhuǎn)發(fā)至各從節(jié)點(步驟 2)。主節(jié)點和各從節(jié)點將請求持久化到日志中，并返回主節(jié)點的一致性模塊日志寫入成功(步驟 3)。當(dāng)大部分節(jié)點返回成功后，主節(jié)點會將請求應(yīng)用到狀態(tài)機上(步驟 4)，并返回請求處理成功(步驟 5)。主節(jié)點在后續(xù)和從節(jié)點的交互中，指示從節(jié)點異步應(yīng)用對應(yīng)日志(步驟 6)。

圖3 RAFT 協(xié)議處理增刪改操作的流程Fig. 3 Work flow of RAFT consensus algorithm

RAFT 協(xié)議通過保持各復(fù)制組中節(jié)點日志的一致性，達(dá)到各節(jié)點狀態(tài)機保持一致的目的。通過重放相同的日志，各復(fù)制組得到相同的狀態(tài)機。在實際系統(tǒng)中，狀態(tài)機會定時進行持久化，保存為一個狀態(tài)機快照，即快照操作。當(dāng)進行快照操作時，需要記錄快照索引，即狀態(tài)機最新應(yīng)用的日志索引。當(dāng)故障重啟時，一致性模塊加載狀態(tài)機快照，并順序重放索引大于快照索引的日志，修復(fù)出最新的狀態(tài)機，這一過程叫作增量修復(fù)。使用快照和大于快照索引的日志，便可修復(fù)出最新的狀態(tài)機，所以小于等于最新快照索引的日志均可以被安全截斷。

當(dāng)節(jié)點長期離線后再上線，或遷移到新的存儲服務(wù)器時，主節(jié)點的日志可能無法滿足其修復(fù)(或新建)狀態(tài)機的需求。如，某節(jié)點最新應(yīng)用的日志索引為 100，然而主節(jié)點維護的最舊日志索引為 110。那么，必須先從主節(jié)點同步其狀態(tài)機快照至本地，然后從主節(jié)點同步并順序重放索引大于快照索引的日志來修復(fù)狀態(tài)機。這一過程叫作全量修復(fù)。

此外，分布式鍵值存儲中，狀態(tài)機已經(jīng)持久化存儲在本地引擎中，所以快照操作并不需要額外持久化狀態(tài)機，只需要記錄快照索引即可，這種快照操作稱作隱式快照。

4 系統(tǒng)設(shè)計

本節(jié)將對 PheonixLSM 的系統(tǒng)設(shè)計進行介紹。針對前述的日志和 WAL 雙寫，以及全量修復(fù)時空間放大兩個問題，提出雙寫消除和過期數(shù)據(jù)實時清理兩項優(yōu)化。

4.1 雙寫消除

本小節(jié)說明如何使用 RAFT 日志進行狀態(tài)機的同步，同時在本地引擎中，起到重建由進程重啟導(dǎo)致丟失 Memtables 的作用。在滿足該前提的情況下，PheonixLSM 不需要 WAL 保護，所以可通過關(guān)閉 WAL 消除雙寫。

關(guān)閉 WAL 之后，本地引擎由于失去保護，重啟會導(dǎo)致所有的 Memtables 丟失且無法重建，只留下 SST 文件。本文歸納出使用日志修復(fù)Memtables 的充分條件：在任何時刻，已持久化的 SST 文件都能構(gòu)成一個狀態(tài)機快照。在滿足該充分條件的情況下，關(guān)掉 WAL 的本地引擎在任意時刻重啟后都存儲一個狀態(tài)機快照。根據(jù)一致性協(xié)議的性質(zhì)可知，只要大于該快照索引的日志沒有被刪除，那么在該快照的基礎(chǔ)上，就可以通過回放日志恢復(fù)狀態(tài)機。

為了關(guān)閉 WAL，需要解決以下兩個問題：(1)如何保證在任意時刻，已持久化的 SST 文件都能構(gòu)成一個狀態(tài)機快照；(2) 在滿足(1)的情況下，如何獲得上述狀態(tài)機快照的快照索引。從該快照索引對應(yīng)的下一條 RAFT Log 開始回放，就能夠重構(gòu)出狀態(tài)機。

為解決上述問題，PheonixLSM 改造了增刪改請求的應(yīng)用流程。原來的應(yīng)用流程：將每個增刪改請求產(chǎn)生的鍵值對提交到本地引擎；改造后的應(yīng)用流程：除增刪改請求產(chǎn)生的鍵值對之外，還需同時寫入一個特殊的哨兵鍵值對。哨兵鍵值對在一個復(fù)制組中有且僅有一個，其 value 是當(dāng)前最新被應(yīng)用的 RAFT 日志索引，能夠確定重啟時本地引擎中狀態(tài)機的快照索引。圖 4 為PheonixLSM 中哨兵鍵值對插入 Memtable 并持久化至 SST 文件的流程，由于關(guān)閉了 WAL，插入Memtable 時只需要內(nèi)存操作。

若僅依靠哨兵鍵值對，則無法保證重啟后已持久化的 SST 文件能夠構(gòu)成一個狀態(tài)機快照。所以 PheonixLSM 還對增刪改和回刷操作做了以下約束：

(1)一個請求的所有鍵值對(包括普通鍵值對、墓碑鍵值對和哨兵鍵值對)，必須更新至同一 Memtable 中；

(2)Memtables 必須按照其轉(zhuǎn)為只讀的時間順序順次進行回刷。

為了使 PheonixLSM 能夠指導(dǎo)狀態(tài)機日志的截斷操作，新增了 GetPersisted 接口，其可跨過Memtables，直接從 L0開始查找已持久化的鍵值對。通過 GetPersisted 接口查找哨兵鍵值對，返回的結(jié)果即是 SST 文件構(gòu)成的狀態(tài)機快照的快照索引。如圖 4 所示，GetPersisted 接口查找到的哨兵鍵值對的值為 700。這一返回結(jié)果表明，在沒有新回刷發(fā)生的情況下發(fā)生故障重啟，那么本地引擎中存儲的是快照索引為 700 的狀態(tài)機快照。因此，日志索引小于等于 700 的日志，此時都可以被安全地刪除。

圖4 PheonixLSM 中哨兵鍵值對插入 Memtable 并持久化至 SST 文件的流程Fig. 4 Sentinel key-value pairinserting into Memtable and persisted to SST files

本文通過實驗證明了上述雙寫消除方案的有效性。假設(shè)本地引擎采取了前述的寫操作和回刷操作約束，使用 GetPersisted 接口獲得哨兵值為idx，可以得出下述引理和定理。

引理1所有滿足日志索引index≤idx的請求數(shù)據(jù)都已經(jīng)持久化，所有日志索引index＞idx的請求數(shù)據(jù)重啟前在 Memtables 中，沒有回刷，已經(jīng)在重啟中丟失。

證明：首先使用反證法證明index≤idx的所有請求數(shù)據(jù)都已持久化。假如存在某日志索引index'＜idx的請求沒有持久化，那么，日志index'和idx的請求數(shù)據(jù)一定寫入了不同的 Memtables中，否則會被同時持久化②：Memtable 回刷的原子性：Memtable 持久化成一個 L0 層 SST 文件的過程并不是原子的，此時斷電可能導(dǎo)致只有 Memtable 中部分的數(shù)據(jù)刷入該 SST 中。然而，Memtable 回刷的過程是由(1)Memtable 數(shù)據(jù)寫入 SST 文件，(2)寫入新的 LSM 樹視圖文件(各 SST 文件的文件名、key 區(qū)間，以及 SST 文件的層次關(guān)系等信息)，(3)替換舊 LSM 樹視圖文件 3 個步驟完成的。上述斷電發(fā)生在步驟(1)，重啟之后，LSM 樹的視圖未被更新，被寫入一半的 SST 文件不在舊視圖中，會在初始化過程中被直接刪除。而步驟(3)的替換視圖文件是原子操作，因此，回刷操作中發(fā)生故障，一個 Memtable 中的數(shù)據(jù)，或者全部丟失，或者全部已經(jīng)持久化，顯示在新的視圖文件中，不會出現(xiàn)一個 Memtable 部分?jǐn)?shù)據(jù)持久化，部分?jǐn)?shù)據(jù)丟失的場景。；假設(shè)日志index'和idx的請求數(shù)據(jù)分別被寫入了 MemtablesMi和Mj，那么由于index'＜idx，一致性協(xié)議保證請求數(shù)據(jù)按日志索引從小到大的順序?qū)懭氡镜匾?，因此，日志index'的數(shù)據(jù)會早于idx的數(shù)據(jù)被寫入。由于任何時刻，本地引擎都只有唯一的可讀寫 Memtable，那么Mi早于Mj轉(zhuǎn)為只讀。索引日志index'的請求數(shù)據(jù)沒有持久化，而idx的已被持久化，說明Mi晚于Mj回刷，違反了前述的回刷順序約束。因此，假設(shè)不成立，所有日志索引index≤idx的請求數(shù)據(jù)都已持久化。

類似地，也可以證明所有日志索引index＞idx的日志尚沒有持久化。

定理1在滿足寫和回刷約束的前提下，如果發(fā)生重啟，重啟后的本地引擎中存儲的是快照日志索引為idx的狀態(tài)機快照。

證明：根據(jù)引理 1，當(dāng)發(fā)生故障重啟時，所有日志索引index≤idx的請求數(shù)據(jù)均已被持久化，而index＞idx的請求數(shù)據(jù)在重啟前，只是存儲在 Memtables 中沒有回刷，在重啟過程中已經(jīng)丟失。按照一致性協(xié)議的定義，所有日志索引index≤idx的請求數(shù)據(jù)，在本地引擎中，已經(jīng)全部被順序持久化，并且沒有多余的請求數(shù)據(jù)被寫入。所以，本地引擎中存儲的是快照索引為idx的狀態(tài)機快照。

4.2 過期數(shù)據(jù)實時清理

刪除舊狀態(tài)機是分布式鍵值存儲的常見操作。節(jié)點長期離線后再上線觸發(fā)全量修復(fù)，以及負(fù)載均衡過程中，復(fù)制組節(jié)點遷入新服務(wù)器時，都需要先刪除舊狀態(tài)機，以防污染新狀態(tài)機數(shù)據(jù)。為便于操作，分布式鍵值存儲通常將不同復(fù)制組的 key 轉(zhuǎn)換為不同前綴的底層格式。在本文的系統(tǒng)實現(xiàn)中，業(yè)務(wù)邏輯的 key 都使用其所屬的復(fù)制組編號作為前綴，然后再存入本地引擎(如圖 4 所示)。這種轉(zhuǎn)換使得相同復(fù)制組中的 key在底層引擎中具有相同的前綴，存儲在連續(xù)空間中，可以通過范圍刪除清理某復(fù)制組的狀態(tài)機。

原生本地引擎在刪除舊狀態(tài)機時，插入了一個表示范圍刪除的墓碑鍵值對，然后，將從主節(jié)點處復(fù)制來的新狀態(tài)機快照插入。如圖 5 所示，由于墓碑鍵值對通過逐層合并至最低層才能完全回收空間，所以在新狀態(tài)機插入后的較長時間內(nèi)，新舊狀態(tài)機數(shù)據(jù)在本地引擎中共存，將會造成存儲空間的浪費。PheonixLSM 針對這一問題，提出將各復(fù)制組的數(shù)據(jù)大致隔離在不同的 SST 文件中，從而使得刪除狀態(tài)機的操作可以通過同步刪除相關(guān)的 SST 文件完成，實時釋放空間。

圖5 原生本地引擎的全量修復(fù)流程和其造成的空間放大Fig. 5 Full-node repair with original local engine and the spatial amplification it caused

PheonixLSM 通過改造 LSM 樹的合并邏輯，來達(dá)成上述復(fù)制組數(shù)據(jù)的隔離。LSM 樹原有的合并邏輯，將 Li和 Li＋1層中的候選 SST 文件的鍵值對分別按順序讀取出來，并將兩層的鍵值對進行合并后寫入新的 Li＋1層的 SST 文件。PheonixLSM 修改后的合并流程中，會根據(jù)鍵值對 key 的前綴判斷其所屬的復(fù)制組，當(dāng)處理的復(fù)制組發(fā)生改變時(如，剛剛處理的 key 為 002_foo1，而正在處理的 key 為 003_foo2，說明復(fù)制組 002 的數(shù)據(jù)已經(jīng)被寫完，開始寫復(fù)制組 003 的數(shù)據(jù))，PheonixLSM 會將當(dāng)前 SST 文件關(guān)閉，并將當(dāng)前鍵值對寫入新的 SST 文件。從而保證，在L1及更低層的任何 SST 文件中，都只包含屬于某一個復(fù)制組的鍵值對。

圖 6 是使用 PheonixLSM 進行本地引擎的舊狀態(tài)機刪除，以及新狀態(tài)機快照的安裝流程。刪除舊狀態(tài)機時，首先強制回刷 Memtables，并在回刷后將 L0的 SST 文件合并至 L1。此時，所有屬于該狀態(tài)機的鍵值對都存儲在某個 SST 文件集合中，且該集合中的 SST 文件不包含其他復(fù)制組的狀態(tài)機數(shù)據(jù)。刪除操作可直接刪除復(fù)制組所有相關(guān)的 SST 文件。

PheonixLSM 在刪除狀態(tài)機時(圖 6(b)～(c))，遍歷 LSM 樹視圖中的 L1層及以下各 SST 文件，視圖中保存了每個 SST 文件的 key 區(qū)間。當(dāng)某SST 文件包含前綴為目標(biāo)復(fù)制組編號的 key 時，說明該 SST 文件中保存的都是目標(biāo)復(fù)制組中的數(shù)據(jù)，就可以進行刪除操作(圖 6(c))。刪除舊狀態(tài)機之后空間被完全回收，新狀態(tài)機快照在此時進行安裝(圖 6(d))。

圖6 使用 PheonixLSM 進行全量修復(fù)的舊狀態(tài)機刪除和新狀態(tài)機快照的安裝流程Fig. 6 Full-node repair process with PhoenixLSM, including deleting old state machine and instralling new one

一致性模塊的修復(fù)操作，需要先將狀態(tài)機快照安裝完畢，才能重放日志，因此，在刪除舊狀態(tài)機并插入新狀態(tài)機快照的過程中，本地引擎不會收到該復(fù)制組的請求。刪除流程可以確保在強制回刷合并至 L1之后，復(fù)制組的所有鍵值對都已經(jīng)在 L1或更低層。PheonixLSM 的刪除操作，能將舊的狀態(tài)機完全刪除，且其他復(fù)制組不受影響。

5 原型實現(xiàn)和實驗結(jié)果

5.1 原型實現(xiàn)和部署

PheonixLSM 的原型基于 RocksDB 5.18.0 實現(xiàn)，對 RocksDB 的代碼庫僅有約 200 行代碼的改動。具體的改造方法見第 4 節(jié)。

在實際部署中，PheonixLSM 作為自研分布式鍵值存儲系統(tǒng) PheonixKV 的本地引擎。如圖 7所示，PheonixKV 有 3 個主要組件：數(shù)據(jù)服務(wù)器KVAgent、元數(shù)據(jù)服務(wù)器 MetaServer 和客戶端。

圖7 PheonixKV 架構(gòu)Fig. 7 PheonixKV architecture

PheonixKV 將 key 空間映射到若干個使用 RAFT 協(xié)議維護一致性的復(fù)制組。復(fù)制組的節(jié)點分布在不同的 KVAgent 上，以提供容錯性。KVAgent 負(fù)責(zé)本地引擎和復(fù)制組節(jié)點的初始化，本地資源的分配和清理等，并定期心跳向 MetaServer 匯報健康狀況。MetaServer 根據(jù)集群健康和負(fù)載狀況，通過心跳回復(fù)指示對應(yīng) KVAgent 執(zhí)行節(jié)點遷移。KVAgent 通過GetPersisted 接口從 PheonixLSM 獲取最新持久化的日志索引，指導(dǎo)日志截斷。MetaServer 集群也使用 RAFT 協(xié)議來維護關(guān)鍵元數(shù)據(jù)的一致性。客戶端先向 MetaServer 請求路由信息，包括復(fù)制組所在的 KVAgent 列表，以及 key 到復(fù)制組的映射規(guī)則，之后根據(jù)路由信息將請求發(fā)至對應(yīng)的KVAgent 處理。

5.2 實驗環(huán)境與工具

本實驗是在一個三主機的集群環(huán)境上進行的，每臺主機配備一顆 14 核 2.40 GHz 的 Intel Xeon E5 2680 v4CPU，128 MiB 內(nèi)存，以及兩塊 480 GiB 的 Intel S4600 SATA SSD。3 臺主機通過 10 Gbps 的網(wǎng)絡(luò)連接。每臺主機運行兩個KVAgent 以及一個 MetaServer。每個 KVAgent 管理其獨占的 SSD，故單 SSD 故障只會影響一個KVAgent。PheonixKV 系統(tǒng)中有 256 個三副本復(fù)制組，其節(jié)點分布在不同主機的 KVAgent 上，提供主機級別的故障域。

本實驗使用 RocksDB 自帶的 db_bench 測試本地引擎，并使用自主研發(fā)的 PheonixKVTest 測試工具測試 PheonixKV 性能。PheonixKVTest 使用指定并發(fā)數(shù)執(zhí)行鍵值對的插入、刪除、讀取和校驗操作，同時可監(jiān)控性能，實時輸出當(dāng)前的時延和吞吐數(shù)據(jù)。PheonixKV 的目標(biāo)是承載新型視頻監(jiān)控系統(tǒng)產(chǎn)生的對象存儲元數(shù)據(jù)，該業(yè)務(wù)模型會高并發(fā)寫入約為 256 字節(jié)的鍵值對，讀請求較少。PheonixKVTest 模擬這一業(yè)務(wù)產(chǎn)生的元數(shù)據(jù)流量，但是也可以自行定義讀寫比例，以及讀寫鍵值對的大小和概率分布等。參考MemC3[9]，使用不同讀寫比例的業(yè)務(wù)流量來測試PheonixLSM 在不同流量模型下的性能表現(xiàn)。

5.3 實驗結(jié)果及分析討論

本地引擎測試。使用 db_bench 的隨機讀寫模式，對比 PheonixLSM 和 RocksDB 的讀寫時延和尾時延(99 分位時延)。每輪實驗使用 16 線程，共下發(fā) 1 000 萬條隨機讀寫請求。請求的key 和 value 為 128 字節(jié)的字符串，key 的選擇符合平均分布。調(diào)整讀寫請求的比例，圖 8 是不同本地引擎的讀寫時延對比結(jié)果。由圖 8 可知，PheonixLSM 和關(guān)掉 WAL 的 RocksDB 各項時延和尾時延差異均在 3% 之內(nèi)，說明 PheonixLSM的改造并沒有帶來性能損耗。當(dāng)讀寫時延不同時，與 RocksDB 相比，PheonixLSM 的寫時延降低 94.1%～95.2%，說明關(guān)閉 WAL 能帶來較大的性能提升。

圖8 不同本地引擎的讀寫時延(平均時延和99 分位時延)對比Fig. 8 Read/write latency (average and 99-percentile)comparison of local engines

雙寫消除。本文考察雙寫消除為 PheonixKV帶來的性能提升。本實驗使用 1/4/16/64 的并發(fā)數(shù)，分別向 PheonixKV 集群插入 1 000 萬條 key和 value，其均為 128 字節(jié)的隨機鍵值對。圖 9為使用 RocksDB 和 PheonixLSM 作底層引擎時，PheonixKV 的吞吐對比結(jié)果。由圖 9 可知，當(dāng)并發(fā)數(shù)不同時，與 RocksDB 相比，PheonixLSM的吞吐提升 32.0%～90.5%，其中，當(dāng)并發(fā)數(shù)為16 時，吞吐提升最大。增加并發(fā)數(shù)，RocksDB和 PheonixLSM 的單位計算資源吞吐均出現(xiàn)下降的情況，這是由于 CPU 需要處理更多的線程調(diào)度工作。在不同并發(fā)數(shù)下，PheonixLSM 能帶來8.0%～21.7% 的單位計算資源吞吐提升，且在并發(fā)數(shù)為 64 時的吞吐提升最大。

圖9 使用 RocksDB 和 PheonixLSM 作底層引擎時PheonixKV 的吞吐對比Fig. 9 Throughput comparison of PheonixKV with RocksDB and PheonixLSM, respectively

將并發(fā)數(shù)固定為 64，以請求的讀寫比例為自變量，對比不同讀寫比例下 PheonixKV 使用兩種底層引擎的性能。向 PheonixKV 下發(fā) 1 000 萬條請求，吞吐和讀寫時延(包括平均時延和 99 分位時延)的對比結(jié)果如圖 10 所示。對于同一種引擎，讀寫比對于讀寫時延影響較小；當(dāng)使用不同引擎時，讀時延差異較小，均在 8% 以內(nèi)。當(dāng)使用 PheonixLSM 時，PheonixKV 在不同讀寫比例下的平均寫時延和 99 分位寫時延分別降低 31.3%～35.5% 和 28.0%～37.8%。由圖 10 所示，PheonixLSM 將吞吐提升了 26.5%～50.3%。由于 PheonixLSM 主要改善寫性能，當(dāng)讀寫比為2∶8 時，寫請求占比最大，吞吐提升最多。

圖10 不同讀寫比業(yè)務(wù)流量下的吞吐和讀寫時延(平均時延和 99 分位時延)對比Fig. 10 Throughput and latency (average and 99-percentile) comparison of diあerent read/write ratio

本文驗證 PheonixLSM 的狀態(tài)機實時刪除優(yōu)化，對空間放大問題帶來的改善。首先在系統(tǒng)中寫入 5 億鍵值對，并結(jié)束一個 KVAgent 進程，當(dāng)繼續(xù)寫入 1 000 萬鍵值對后，重新開啟該KVAgent 進程。在修復(fù)過程中，以每秒一次的頻率對該 KVAgent 的磁盤空間使用情況進行采樣。圖 11 為全量修復(fù)過程中的空間放大對比結(jié)果。當(dāng) RocksDB 作本地引擎時，大量數(shù)據(jù)插入引發(fā)的合并操作，產(chǎn)生了較大的額外空間占用，即使在修復(fù)結(jié)束后，由于各層 SST 文件的分布還未穩(wěn)定，后臺仍在進行合并操作，所以額外空間的占用還在增加。此外，后臺的合并任務(wù)也影響了正常的數(shù)據(jù)寫入，導(dǎo)致修復(fù)時間變長。以修復(fù)后的穩(wěn)態(tài)空間占用為基準(zhǔn)，當(dāng) RocksDB 為本地引擎時，空間放大最多為 65.6%；而當(dāng) PheonixLSM 為本地引擎時，空間放大最多僅為 6.4%。由圖 11可知，PheonixLSM 將修復(fù)用時從 4 398 s 降低至1 217 s，節(jié)約了 72.3% 的修復(fù)用時。

圖11 全量修復(fù)過程中的空間放大對比Fig. 11 Comparison of spatial amplification during full-node repair

PheonixLSM 修改合并邏輯，潛在地增加SST 文件數(shù)目。圖 12 對比了隨著 PheonixKV 插入鍵值對數(shù)目的變化，不同底層引擎中 SST 文件數(shù)目及占用存儲空間的變化。當(dāng)鍵值對數(shù)目較少時，PheonixLSM 導(dǎo)致 SST 文件數(shù)目增加較多；當(dāng)鍵值對為 1 000 萬個時，RocksDB僅有 20 個 SST 文件，而 PheonixLSM 有 210個。然而，當(dāng)數(shù)據(jù)規(guī)模繼續(xù)擴大時，SST 文件的數(shù)目差異會減少，當(dāng)鍵值對為 10 億個時，RocksDB 和 PheonixLSM 分別有 2 161 和 2 176個 SST 文件，數(shù)目相差很小。綜合而言，PheonixLSM 帶來的 SST 文件數(shù)目增加，對于底層的文件系統(tǒng)來說，不會明顯增加處理壓力。當(dāng)鍵值對數(shù)目逐漸增加時，與原生 RocksDB 相比，PheonixLSM 占用的存儲空間均沒有增加，請求處理的性能也沒有因此發(fā)生下降(見圖 8)。

圖12 RocksDB 和 PheonixLSM 的 SST 文件數(shù)目和空間占用對比Fig. 12 Number of SST files and space usage for RocksDB and PheonixLSM

6 討論與分析

作為存儲系統(tǒng)的核心組件，分布式鍵值存儲的性能和承載規(guī)模至關(guān)重要。然而，本地引擎并沒有很好地適配分布式鍵值存儲的業(yè)務(wù)特征。本文提出了針對分布式業(yè)務(wù)優(yōu)化的底層引擎PheonixLSM，解決了一致性協(xié)議日志和本地引擎 WAL 雙寫問題，以及全量修復(fù)過程中的額外空間放大問題。據(jù)相關(guān)調(diào)查表明，PheonixLSM是第一個針對分布式鍵值存儲業(yè)務(wù)改造的底層引擎③：使用谷歌學(xué)術(shù)于 2021 年 5 月 26 日檢索英文關(guān)鍵字“distributed key-value storage; spatial amplification; extra synchronization”以及中文關(guān)鍵字“分布式鍵值存儲；空間放大；雙寫”的檢索結(jié)果中，均沒有相關(guān)的工作。，其有效解決了分布式鍵值存儲的痛點，能夠?qū)⑼掏绿嵘?90% 以上；還可將全量修復(fù)的空間放大由 65.6% 降低至 6.4%，效果明顯；此外，還有效提升了分布式鍵值存儲的業(yè)務(wù)和修復(fù)性能，以及承載規(guī)模。在后續(xù)的工作中，還將進一步結(jié)合分布式框架的業(yè)務(wù)模型，針對性優(yōu)化底層引擎，從引入新型索引數(shù)據(jù)結(jié)構(gòu)、底層文件組織，以及發(fā)揮新型硬件特征等角度，進一步提升分布式鍵值存儲的性能和承載規(guī)模。

分布式鍵值存儲的性能和承載規(guī)模，取決于底層引擎的能力，以及上層分布式路由模塊分發(fā)流量、均衡負(fù)載和存儲的能力。本文重點關(guān)注前者，后續(xù)基于 PheonixKV 的工作中，如何確保性能隨集群規(guī)模擴大線性提升，各底層引擎性能均能得到發(fā)揮也將是重點研究方向。

7 結(jié) 論

本文描述了 PheonixLSM 的設(shè)計與實現(xiàn)。PheonixLSM 是一個基于 LSM 樹的本地鍵值引擎，面向分布式鍵值存儲，進行了針對性的優(yōu)化。PheonixLSM 通過改造 LSM 樹的增刪改和回刷流程以及 SST 文件的組織形式，配合上層分布式邏輯，解決了分布式鍵值存儲系統(tǒng)中一致性協(xié)議的雙寫引發(fā)的性能問題，以及全量修復(fù)時的額外空間放大問題。本文在 RocksDB 的源代碼上進行改造實現(xiàn)了 PheonixLSM，并在三主機的分布式集群上進行了實驗。實驗結(jié)果證明，PheonixLSM帶來了性能改進，以及全量修復(fù)過程中空間放大問題的有效消除。與原生 RocksDB 的分布式鍵值存儲相比，PheonixLSM 的分布式鍵值存儲，吞吐提升 90% 以上，單位計算資源吞吐提升20% 以上。全量修復(fù)過程中的空間放大由 65.6%下降至 6.4%，并減少了 72.3% 的修復(fù)時間。