孫 輝 婁本冬 黃建忠 趙雨虹 符 松

1(安徽大學計算機科學與技術學院 合肥 230601)

2(華中科技大學武漢光電國家研究中心 武漢 430074)

3(中國科學院信息工程研究所 北京 100093)

4(北德克薩斯大學計算機科學與工程系 美國德克薩斯州登頓 76203)

國際數(shù)據(jù)公司在報告“Data Age 2025”[1]中預測，從2018—2025年，全球數(shù)據(jù)總量將從33 ZB躍升到175 ZB，其中非結構化數(shù)據(jù)將占數(shù)據(jù)總量的80%以上.傳統(tǒng)關系型數(shù)據(jù)庫已無法滿足高效組織與管理大規(guī)模非結構化數(shù)據(jù)的需求以及數(shù)據(jù)庫高并發(fā)和易擴展性的愿望[2-3]，關系型數(shù)據(jù)庫旨在管理結構化數(shù)據(jù)或與預定義數(shù)據(jù)類型對齊的數(shù)據(jù)，從而使其易于分類和搜索，面對海量非結構化數(shù)據(jù)，更改關系型數(shù)據(jù)庫中的結構可能會非常昂貴且耗時，并且通常會導致停機或服務中斷.另一方面，關系型數(shù)據(jù)庫難以進行橫向擴展[4]，這與關系模型旨在確保一致性有關，要在多臺服務器上水平擴展關系型數(shù)據(jù)庫，則很難確保其一致性.

針對傳統(tǒng)關系型數(shù)據(jù)庫已不能勝任管理海量非結構化數(shù)據(jù)的問題[3]，人們開始著眼基于日志歸并樹(log structured merge tree, LSM-tree)的鍵值存儲系統(tǒng)來管理海量非結構化數(shù)據(jù)，如Apache的HBase[5]和Cassandra[6]、Google的BigTable[7]和LevelDB[8]以及Facebook的RocksDB[9]等.LSM-tree鍵值存儲通過對寫入操作進行順序化實現(xiàn)性能提升，具有高寫入性、易擴展等優(yōu)勢.LSM-tree包括內存組件和硬盤組件2部分，其將隨機寫緩存在內存組件(MemTable)中，待內存組件寫滿時再轉儲到硬盤組件上，將隨機寫轉化為批量順序寫.隨著數(shù)據(jù)的持續(xù)寫入，硬盤組件數(shù)量越來越多，讀取數(shù)據(jù)時需要查詢的文件數(shù)量增多，同時舊的組件中會有很多過期的數(shù)據(jù)，所以需要整理和合并大量文件，將上層數(shù)據(jù)轉儲到下層：一方面是為了減少文件的數(shù)量以提高讀性能；另一方面則是為了刪除過期數(shù)據(jù)，釋放存儲空間，這一過程被稱為compaction.compaction是一個后臺線程，會持續(xù)將達到預定閾值的上層文件轉移到下層.在隨機寫密集型負載下，compaction任務會頻繁發(fā)生，引起數(shù)據(jù)壓縮/解壓、拷貝和字符串比較等操作，消耗大量計算資源，同時讀寫操作也會占用大量硬盤I/O，引起系統(tǒng)寫放大，降低系統(tǒng)性能.

隨著存儲設備內計算能力的提升，基于近數(shù)據(jù)計算(near-data processing, NDP)的計算模型重新受到了廣泛關注[10]，數(shù)據(jù)處理模式從以傳統(tǒng)計算為中心的方式轉變?yōu)橐詳?shù)據(jù)為中心.近數(shù)據(jù)計算模型的核心是讓“計算接近數(shù)據(jù)”，改變存儲設備獲取數(shù)據(jù)后再傳輸?shù)街鳈C端處理的方式，而是直接在存儲設備內計算，主機端接收計算結果[10-11].該模型減少了數(shù)據(jù)移動開銷，如前文提到的compaction操作，有效減少主機與存儲設備之間的I/O負擔并提高系統(tǒng)性能.面對基于LSM-tree的鍵值存儲中存在compaction的問題，在近數(shù)據(jù)計算模型下，實現(xiàn)compaction的多級并行優(yōu)化方法(CoPro)，降低compaction所帶來的性能損失，提升鍵值存儲系統(tǒng)吞吐量.CoPro具有4個優(yōu)點：1)利用系統(tǒng)并行與流水線提高compaction性能；2)為了平衡資源消耗與性能提升，在CoPro內部實現(xiàn)了決策組件，用于從線性方式和流水線方式中動態(tài)選擇compaction的執(zhí)行方式，即動態(tài)改變系統(tǒng)整體的并行度；3)在具有不同大小值的負載下進行compaction優(yōu)化，讓CoPro在更趨于真實的復雜負載下依舊可以發(fā)揮較好的效果；4)具有良好的可擴展性，該方案不僅適用于compaction任務的靜態(tài)卸載，同樣適用于compaction任務的動態(tài)卸載.使用db_bench與YCSB-C對CoPro進行了大量的實驗驗證CoPro的優(yōu)勢，CoPro分別將主機端和設備端的compaction帶寬提高了2.34倍和1.64倍，與此同時，兩端的吞吐量增加了約2倍.主機端和設備端的CPU使用率分別增加了74.0%和54.0%.

1 背景介紹與研究動機

1.1 研究背景

LSM-tree作為一種可以延遲更新且批量寫入硬盤的日志型數(shù)據(jù)結構，利用順序寫來提高寫性能，但其分層的設計會犧牲小部分讀性能換來提高寫性能.

LSM-tree包含2個或2個以上的存儲數(shù)據(jù)結構.在有2個以上部件的LSM-tree中，通常由大小連續(xù)增加的C0，C1，…，Cn-1，Cn組件組成，如圖1所示.C0在內存，而C1～Cn通常在硬盤內，但內存會緩存C1，C2，…，Cn-1，Cn中常被讀取的數(shù)據(jù).

1) 日志文件.當有新的數(shù)據(jù)需要被寫入時，首先向存放在硬盤的寫前日志文件中寫入此次操作的日志.當系統(tǒng)發(fā)生故障時，可以通過寫前日志來恢復數(shù)據(jù).當內存組件中的數(shù)據(jù)轉儲到硬盤后，對應的寫前日志也就失效，可以刪除來釋放存儲空間.

2) 內存組件(C0).根據(jù)新數(shù)據(jù)的索引將該數(shù)據(jù)添加到C0中.因為C0設置在內存中，所以這一過程與硬盤I/O無關.但內存的數(shù)據(jù)存儲成本要高于硬盤，所以需要為C0的大小設定閾值.每當C0的大小即將超出閾值時，C0就會把部分數(shù)據(jù)滾動合并到硬盤組件的C1中，以此緩解內存與硬盤之間存儲成本的差異.

3) 硬盤組件(C1，C2，…，Cn-1，Cn).隨著數(shù)據(jù)的持續(xù)添加，當Ci-1的大小達到其閾值后，滾動合并就會在相鄰的2個部件Ci-1和Ci之間發(fā)生，數(shù)據(jù)會從小部件Ci-1轉儲到大部件Ci中.即數(shù)據(jù)一開始會插入到C0中，之后隨著不停地滾動合并，最終數(shù)據(jù)會寫入到Cn中.

本文研究內容主要優(yōu)化鍵值存儲中的compaction.接下來用一個典型的鍵值存儲數(shù)據(jù)庫——LevelDB為例，介紹compaction的具體流程.LevelDB有2種compaction操作：小compaction和大compaction，如圖1所示:

Fig. 1 LSM-tree and compaction of LevelDB圖1 LSM-tree和LevelDB compaction流程

小compaction將內存中不可修改的內存表(immutable memtable)持久化為SSTable.小compaction主要負責：1)構造SSTable；2)決定新的SSTable文件寫入哪一層.當內存中出現(xiàn)immutable memtable時即觸發(fā)小compaction，將immutable memtable構造為SSTable，根據(jù)該SSTable文件與下面level層文件的重疊情況決定該表的具體寫入層數(shù).因后臺只有一個線程負責compaction任務，所以當小compaction觸發(fā)時，則暫停大compaction，待小compaction操作處理完后再繼續(xù)執(zhí)行.

大compaction指的是SSTable之間的compaction操作.大compaction又有3種情況：1)手動compaction，由人工觸發(fā)的compaction任務，通過外部接口調用compaction任務具體的level與鍵范圍，符合條件的SSTable參與compaction操作.這種compaction操作在LevelDB內部是不會自動觸發(fā)調用的.2)容量compaction，如在Li層，當超出該層的大小閾值時，則觸發(fā)compaction，通過輪詢Li中SSTable的元信息(FileMetaData)選取SSTable參與compaction任務.然后，比較Li+1中的所有元信息，找出與Li選中的SSTable鍵范圍重疊的文件加入到compaction任務中.對所有選中參與compaction任務的SSTable進行歸并排序，生成新的SSTable寫入Li+1，同時刪除參與過compaction任務的舊SSTable.容量compaction是LevelDB的核心compaction過程.3)查詢compaction，當某一SSTable的無效查找次數(shù)達到了閾值，則對該表進行compaction操作，同時在該表的下一層查找與其鍵范圍重疊的文件加入compaction任務，執(zhí)行歸并排序操作.生成的新文件寫入下一層并刪除舊文件.該過程中會造成寫入硬盤的數(shù)據(jù)量大于用戶需求數(shù)據(jù)量，這一現(xiàn)象被稱為寫放大[8].

當前，近數(shù)據(jù)計算NDP的研究方向存在2種類型：1)內存計算(processing in-memory, PIM)，其將處理器或加速器與主存儲器并置[12]；2)存儲計算(in-storage computing, ISC)，其將處理器或加速器與持久性存儲(如HDD或SSD)并置[13].近數(shù)據(jù)計算是計算機體系結構研究的一個非?；钴S的領域[13-14]，涉及有存內計算原型的研究[15-17]以及專用體系結構的研究[18-19]等.Balasubramonian等人[10]提出了對近數(shù)據(jù)計算研究熱情重新興起的原因，例如基礎技術的成熟以及當前架構無法滿足的用戶需求等.三星[11]在其SSD設備內部控制器集成了用戶可編程的通用ARM處理器內核[20]，采用特定的編程模型或框架，可將代碼卸載到SSD上執(zhí)行.

圖2(a)描述了傳統(tǒng)的計算模型.CPU與內存在結構的最頂層，且為任務的唯一處理位置.主機端響應應用任務請求，從存儲盤中讀取數(shù)據(jù)并執(zhí)行相應任務.在該模型中存儲盤僅用于存儲數(shù)據(jù).在圖2(b)中，是一個基于近數(shù)據(jù)計算模型的存儲盤：該存儲盤具有處理任務的能力，可接收從主機端卸載來的數(shù)據(jù)密集型任務(如數(shù)據(jù)檢索).存儲盤將數(shù)據(jù)讀取到設備端內存中，交由ARM處理器執(zhí)行任務，任務處理結束后將任務結果反饋給主機端即可.該模型可顯著降低主機端接口的I/O壓力，提高系統(tǒng)性能.近數(shù)據(jù)計算的基本思想是使計算能力接近數(shù)據(jù)存儲的位置，從而減少數(shù)據(jù)在存儲器層次結構中的移動.

Fig. 2 Traditional computing model and near-data processing model圖2 傳統(tǒng)計算模型與基于近數(shù)據(jù)計算模型

1.2 研究動機

針對compaction操作會影響到鍵值存儲系統(tǒng)性能的問題，在主機端并行優(yōu)化方案中，PCP[21]使用流水線技術提高compaction性能和系統(tǒng)吞吐量，但帶來較大的寫放大.這是因為想要保證較高的compaction性能，PCP需選取更多的SSTable參與compaction，這增加了額外的數(shù)據(jù)寫入，從而增加了寫放大.這對于基于閃存的存儲設備而言，會縮短其使用壽命.現(xiàn)有面向LSM-tree鍵值存儲的近數(shù)據(jù)計算優(yōu)化方案主要關注于主機端與NDP設備端之間的系統(tǒng)級并行性，或NDP設備本身所具有的并行性，較少將近數(shù)據(jù)計算架構中兩者的并行性都充分利用起來，如Co-KV[22].基于上述問題，在近數(shù)據(jù)計算模型下，本文提出了基于compaction數(shù)據(jù)級-流水級的多級并行優(yōu)化方法(CoPro).

2 CoPro系統(tǒng)概覽

CoPro系統(tǒng)的架構如圖3所示，主要分為2個部分，即主機端子系統(tǒng)和設備端子系統(tǒng).主機端子系統(tǒng)負責接收鍵值存儲應用的API指令(如put,get,delete等)，同時負責與設備端子系統(tǒng)之間進行信息交互，協(xié)同處理鍵值存儲應用的讀寫與compaction任務.設備端子系統(tǒng)負責接收從主機端子系統(tǒng)傳來的指令，解析后執(zhí)行相應的操作并向主機端返回結果.compaction任務被分割成2個子任務后由主機端子系統(tǒng)和設備端子系統(tǒng)協(xié)同處理，實現(xiàn)數(shù)據(jù)并行.CoPro在主機端與設備端內部實現(xiàn)對compaction子任務的流水線處理，增加了流水線并行.在CoPro中實現(xiàn)同時采用數(shù)據(jù)并行與流水線并行加速compaction任務.下面詳細介紹主機端與設備端模塊與處理流程.

Fig. 3 Architecture of CoPro圖3 CoPro系統(tǒng)架構圖

2.1 主機端子系統(tǒng)

主機端子系統(tǒng)主要接收處理2部分的指令信息：1)主機端鍵值存儲操作指令信息；2)設備端執(zhí)行結果的反饋信息.與設備端子系統(tǒng)之間的信息交互，需要主機端的語義管理模塊支持.主機端子系統(tǒng)連接起了鍵值存儲應用與設備端子系統(tǒng)，實現(xiàn)compaction任務的主機端數(shù)據(jù)并行，以及compaction流水線并行.

任務卸載調度模塊.當大compaction觸發(fā)時，由任務卸載調度模塊依據(jù)調度策略對此次compaction任務進行分割，然后通過主機端語義管理模塊將此次分割好的任務卸載到主機端和設備端，該模塊是數(shù)據(jù)并行中對compaction數(shù)據(jù)進行分割的模塊.至于任務卸載的調度策略，可以搭載靜態(tài)調度策略，或動態(tài)調度策略.

主機端compaction管理模塊.主機端compaction子任務的執(zhí)行模塊，負責處理compaction任務數(shù)據(jù)并行中主機端部分.該模塊包括線程管理、讀操作、歸并排序、寫操作、結果反饋等功能.該模塊包含2種compaction子任務執(zhí)行方式：一是傳統(tǒng)的線性compaction處理方式，讀操作、歸并排序、寫操作這3個階段以順序方式執(zhí)行；二是流水線compaction處理方式，將讀操作、歸并排序、寫操作這3個階段按流水線方式組織，compaction數(shù)據(jù)在這3個階段間依次傳遞.通過線程管理組織線程去執(zhí)行這3個階段，實現(xiàn)了對compaction子任務的流水線處理，同時保留了傳統(tǒng)線性compaction方式.

考慮到NDP設備的計算和內存資源可能有受限的情況，添加了決策組件用于決定采用何種compaction子任務執(zhí)行方式，以適應不同的資源使用需求.度量分析器負責收集決策組件所需的判斷依據(jù)(如CPU使用率、內存使用率等)，然后按照語義協(xié)議封裝信息，傳遞給決策組件，決策組件對這些信息進行處理，最后決定使用哪種compaction執(zhí)行方式.決策依據(jù)可根據(jù)實際需求來采集不同的決策信息，使用相應的決策算法.

compaction子任務完成后，將反饋信息(如metadata等)由主機端語義管理模塊交給任務卸載調度模塊，其會整合主機端與設備端的compaction子任務反饋結果.運行時庫為主機端compaction管理模塊提供必要的compaction操作支持.

主機端語義管理模塊.主機端語義管理模塊保障了主機端子系統(tǒng)內部模塊之間、主機端與設備端之間的通信.信息交互按照如下格式封裝消息：[數(shù)據(jù)包頭，數(shù)據(jù)包長度，類型，標志，序列化數(shù)據(jù)，校驗碼].其中數(shù)據(jù)包頭表明該消息所代表的操作類型，如任務卸載、打開文件等，類型表明了該消息是由主機端(0x00)還是設備端(0x01)發(fā)出，如圖4所示.此外，決策功能實現(xiàn)所需的信息通信，也由主機通過語義管理模塊將所需度量信息發(fā)送給度量分析器，由其進行數(shù)據(jù)收集.消息按如下格式封裝：[大小，標志，長度，度量信息，校驗碼]，詳見3.2節(jié).

Fig. 4 Semantics transfer protocol of CoPro圖4 CoPro傳輸協(xié)議語義

2.2 設備端子系統(tǒng)

設備端子系統(tǒng)是鍵值存儲應用讀寫請求的實際執(zhí)行者.所有的讀寫操作都是由設備端子系統(tǒng)來執(zhí)行，設備端子系統(tǒng)與存儲介質進行直接的數(shù)據(jù)交互.同樣，設備端實現(xiàn)compaction任務的設備端數(shù)據(jù)并行，以及compaction流水線并行.

設備端compaction管理模塊.設備端compaction子任務的執(zhí)行模塊.因為其對compaction子任務的處理過程與主機端相同，同樣是將讀操作、歸并排序、寫操作這3個階段按流水線方式組織以實現(xiàn)流水線并行，同時保留線性方式，故不再贅述.需要指出的是：設備端compaction管理模塊的決策組件與主機端并無依賴關系，也就是說，可以在主機端與設備端同時執(zhí)行不同的決策方案.同樣地，運行時庫為設備端compaction管理模塊提供必要的compaction操作支持.

設備端語義管理模塊.設備端語義管理模塊與主機端語義管理模塊功能類似，其接收來自主機端子系統(tǒng)的指令并解析(類型為0x00)，之后交由設備端子系統(tǒng)執(zhí)行并將結果按既定語義封裝反饋給主機端子系統(tǒng)(類型為0x01).如接收設備端compaction子任務信息，將其解析后交給設備端compaction管理模塊執(zhí)行，任務完成后將反饋信息封裝發(fā)送給主機端子系統(tǒng).

設備端需要收集的度量信息也是設備端通過語義管理模塊將消息發(fā)送給其內部的度量分析器，由其完成度量信息的收集.

從系統(tǒng)整體看，任務卸載調度模塊對compaction任務進行分割，主機端與設備端子系統(tǒng)協(xié)同處理compaction任務，實現(xiàn)對compaction任務的數(shù)據(jù)并行；從系統(tǒng)內部看，主機端與設備端子系統(tǒng)用流水線方式處理compaction子任務，實現(xiàn)對compaction任務的流水線并行.

3 2級CoPro并行動態(tài)調度策略

Co-KV系統(tǒng)利用NDP模型，采用傳統(tǒng)的線性compaction流程.Co-KV中，在除了第0層以外的其他層中，SSTable的鍵范圍不存在重疊的情況，compaction子任務之間也沒有數(shù)據(jù)依賴關系.基于這個特點，主機端和設備端進行compaction子任務時可以將其并行執(zhí)行.本文利用流水線并行的compaction優(yōu)化方式，與Co-KV原有的數(shù)據(jù)并行方式結合，提高compaction任務的執(zhí)行效率，提升主機端與設備端的資源利用率，優(yōu)化系統(tǒng)性能.改進的同時并不會產(chǎn)生額外的寫放大.

3.1 2級compaction并行

對SSTable進行compaction，主要包括讀SSTable、將SSTable中的鍵值對歸并排序、寫SSTable.在現(xiàn)有近數(shù)據(jù)計算下的鍵值存儲系統(tǒng)中，這3個操作是按順序線性執(zhí)行的.在主機端，首先對compaction任務用調度策略進行分割，主機端對compaction子任務依次執(zhí)行讀、歸并排序、寫操作，設備端同樣對分配給自己的compaction子任務執(zhí)行上述操作.待2個子任務完成時，均將結果反饋給主機端進行整合操作，各階段執(zhí)行過程如圖5(a)所示.主機端與設備端子系統(tǒng)協(xié)同處理同一個compaction任務，但是各自處理該任務的不同數(shù)據(jù)，實現(xiàn)對compaction任務的數(shù)據(jù)并行.

現(xiàn)在還是以讀SSTable—歸并排序—寫SSTable的順序來執(zhí)行compaction子任務，不同的是，利用子任務數(shù)據(jù)間的無依賴關系，可以將這3個不同的操作并行執(zhí)行，以流水線的方式執(zhí)行.具體的方法為：創(chuàng)建2個新線程用于處理鍵值對的合并排序和寫SSTable操作.首先是讀取SSTable內容，該操作依然由原本的compaction處理線程來執(zhí)行，在CoPro中，每當讀取了一定量的鍵值對后，就將其交給歸并排序處理線程進行歸并排序，同時compaction線程繼續(xù)讀取后面的內容；歸并排序處理線程對鍵值對歸并排序，保留有效的數(shù)據(jù)，刪除過期數(shù)據(jù)，完成后再將有序的鍵值對交給寫線程，之后繼續(xù)處理compaction線程后續(xù)傳來的鍵值對；寫線程中設置有一塊緩沖區(qū)，緩存從歸并排序處理線程傳來的鍵值對，當數(shù)據(jù)量達到SSTable的大小時(默認為2MB)，寫線程會生成新的SSTable與metadata，并將新的SSTable寫入硬盤中.這樣就實現(xiàn)了流水線的并行.

Table 1 Workloads for the Proportion Threshold

這樣，在一次compaction任務中，剛開始依舊是執(zhí)行任務分割，將任務卸載到主機端和設備端分別處理.在compaction子任務的處理過程中，將讀、歸并排序、寫操作按照流水線的方式組織，形成了3段流水線.子任務結束后，主機端與設備端分別將各自的執(zhí)行結果反饋并由主機端進行整合.各階段過程如圖5(b)所示.

Fig. 5 Sequential and pipelined compaction modes圖5 線性與流水線compaction模式

在compaction任務執(zhí)行過程中，主機端與設備端子系統(tǒng)并行地處理各自的compaction子任務，實現(xiàn)compaction任務的數(shù)據(jù)級并行；在主機端與設備端compaction子任務中，compaction的讀、歸并排序與寫操作也并行執(zhí)行，實現(xiàn)compaction任務的流水線并行.

3.2 CoPro決策組件

通過3.1節(jié)中的方法，引入流水線compaction處理方式，進一步提升了系統(tǒng)處理compaction的性能，但是流水線方式是利用多線程實現(xiàn)的，在提升性能的同時也會增長資源消耗.NDP設備存在異構性，其計算能力也有差異，從能耗角度考慮，設備端的計算能力可能會受到限制.此外，設備端的資源不可能全部用于服務compaction子任務，還需要保證其他任務的正常執(zhí)行，這對如何利用好計算資源提出了挑戰(zhàn)，尤其是否要使用多線程來開啟流水線處理模塊加速compaction，以及何時需要開啟與關閉多線程功能，判斷的依據(jù)是什么.需要盡可能發(fā)揮資源受限設備的計算能力，減少對其他應用的影響.因此本文提出基于CPU使用率、內存使用率等參數(shù)的決策組件來根據(jù)實際需求，決策是否開啟compaction流水線處理方式.

Fig. 6 Decision-making process in CoPro圖6 CoPro決策流程圖

由圖6所示，首先通過度量分析器收集系統(tǒng)運行過程中需要關心的資源情況，然后將消息按照語義格式封裝.消息頭部由消息大小構成，消息大小為本次消息的總大小.消息體由標志、長度、度量信息和校驗碼組成，標志記錄其后的度量信息是什么類型的度量信息，而長度則記錄著這個度量信息所占用的長度，方便度量信息的讀取.最后對所有信息計算校驗碼，將校驗碼封裝進消息中.封裝好后交由語義接口傳給決策組件，決策組件收到信息后，通過計算公式?jīng)Q定本次compaction子任務的處理方式.

f=α×Ccost+β×Musage+φ×Vsize,

(1)

式(1)用于決策數(shù)值f的計算，其中Ccost表示CPU使用率，Musage表示內存使用率，Vsize表示鍵值對中值大小，α,β,φ則為各參數(shù)的權重.這樣，可以根據(jù)實際環(huán)境設置適合的決策公式，如系統(tǒng)對CPU資源比較敏感，可以相應地增加Ccost的權重.計算結果f與預設的閾值fthreshold進行比較，根據(jù)結果選擇相應的compaction處理策略.

決策組件的加入，可以緩解性能與資源消耗之間的矛盾，盡可能地在性能提升與資源消耗之間找到平衡.例如當CoPro的CPU使用率超出了既定的閾值，決策組件就可以通過關閉流水線來降低CoPro的CPU使用率，待檢測到系統(tǒng)的CPU資源充足時，此時決策組件就可以開啟流水線來加速compaction過程.

在實際的執(zhí)行過程中，compaction子任務是采取傳統(tǒng)線性流程還是流水線流程由決策組件決定，在后續(xù)的實驗中，為了測試數(shù)據(jù)與流水線并行和決策組件的效果，并且為了方便區(qū)分，本文中的CoPro均指代主機端與設備端都默認采用流水線處理方式，即決策組件不生效，CoPro+均指代主機端與設備端的compaction處理方式由決策組件決定，即compaction處理方式是動態(tài)變化的.

3.3 CoPro決策閾值(Vsize)

3.2節(jié)提到的Ccost和Musage比較好確定閾值選取，因為流水線compaction的啟用與否直接會反映到CPU和內存使用率上，這樣根據(jù)系統(tǒng)的實際需求可以很容易地設置其具體值.而對于Vsize的確定則有些困難，因為不清楚流水線compaction與負載鍵值對中值大小的關系.最為常見的是大小劃分，即對不同大小的值采取決策，本文稱為值大小的閾值.由于流水線是作用于compaction整體過程而不是單一的鍵值對，所以確定了值大小閾值后，還需要確定不同大小值在整個compaction過程中所占的比例，達到多少比例就需要觸發(fā)決策，在本文中稱為比例閾值.下面通過實驗，從compaction帶寬與CPU使用率分別代表性能與資源的角度來確定這2個閾值，其中compaction帶寬為單位時間內compaction處理的數(shù)據(jù)量.

1)Vsize——鍵值對中值大小閾值的確定

需要分別確定主機端與設備端的值大小閾值，原因在于主機端與設備端內均有決策組件，需要分別確定兩端各自的閾值.

其次，在NDP架構下，主機端和設備端的計算、存儲等資源不同，主機端和設備端執(zhí)行數(shù)據(jù)級并行的compaction子任務時，執(zhí)行特征也有所不同，兩端環(huán)境的不同造成了需要分別確定閾值.本節(jié)使用compaction帶寬增長率與CPU使用率的增長率比值作為參考依據(jù)，該比值為1時，表示compaction帶寬增長率與CPU使用率的增長率相同，即CPU使用率100%轉化為compaction帶寬，也就是CPU資源的消耗全部用于compaction性能的提升.下面利用負載db_bench進行實驗，研究值大小對流水線compaction的影響，實驗結果如圖7所示.

Fig. 7 Host-side and device-side threshold of record size圖7 主機端與設備端record大小閾值

如圖7(a)所示，在主機端，值大小為16 KB,32 KB,64 KB時的比值分別為1.10,0.97,0.88.可以看到當值大小達到32 KB時compaction帶寬增長率低于CPU增長率.主機端，鍵值對中值為64 KB時的compaction帶寬增長幅度已經(jīng)開始低于CPU使用率的增長幅度，說明此時更多的CPU消耗并不能帶來等量的性能提升.與32 KB時接近1的比值對比，表明從32 KB開始，繼續(xù)增加值的大小，相同的CPU使用率增長已不能獲取等量的compaction帶寬提升，所以主機端選擇32 KB作為值大小的閾值.因此本文定義，在主機端超過32 KB的值被認為是大鍵值對.在設備端該比值普遍低于1，值大小為4 KB,16 KB,32 KB,64 KB時，比值分別為0.53,0.45,0.40,0.28，如圖7(b)所示.從16 KB開始比值低于0.5，意味著1倍的compaction帶寬增長需要2倍以上的CPU消耗，所以設備端選擇16 KB作為鍵值對中值大小的閾值，即對于設備端來說值超過16 KB的鍵值對認為是大鍵值對.至此，主機端與設備端值大小的閾值已確定.

2)Vsize——比例閾值的確定

使用compaction帶寬增長率與CPU使用率增長率的比值作為參考依據(jù)，負載如表1所示：

Fig. 8 The host-side and device-side growth rate ratio圖8 主機端與設備端增長率比值

如圖8所示，在主機端，除了SW5，其余負載比值基本重合于60%和70%，在70%后，100%寫負載繼續(xù)下降，讀寫混合負載數(shù)值上升.SW5總體也是隨著大鍵值對比例增大，比值呈下降趨勢.80%是所有負載的平均最低點，往左右橫跨一個區(qū)間，70%～90%是實驗中平均比值最低的區(qū)間，所以主機端選擇70%這一比例作為決策觸發(fā)的比例閾值.在設備端，所有負載在70%前保持整體下降趨勢，在70%后部分繼續(xù)下降，比值低于1，部分負載緩慢的上升，70%～90%同樣是設備端所有負載平均比值最低的區(qū)間，所以設備端同樣選擇70%作為決策觸發(fā)的比例閾值.在本節(jié)中，當大鍵值對在負載中的比例達到70%時，使用流水線compaction將難以獲得理想的性能提升，還會占用大量的計算資源，形成資源浪費，因此，將70%設置為比例閾值.

4 實驗與結果

CoPro結合了數(shù)據(jù)并行和流水并行的優(yōu)勢，利用2種并行結合的方式進一步提高系統(tǒng)的總體性能.在本節(jié)進行大量實驗來評估CoPro的compaction性能.在4.3節(jié)、4.4節(jié)與4.5節(jié)中，CoPro采用靜態(tài)卸載方案(Co-KV)，主機端與設備端各處理一半的compaction任務數(shù)據(jù).在Co-KV的實驗中已經(jīng)證實Co-KV性能較PCP更優(yōu)，寫放大更小，所以本節(jié)僅與Co-KV進行實驗對比，探究在不同類型負載下寫放大、吞吐量、compaction帶寬、帶寬利用率和CPU使用率的差異.即使用Co-KV作為本節(jié)實驗的評估基準.

4.1 實驗環(huán)境

基于近數(shù)據(jù)計算架構的鍵值存儲系統(tǒng)CoPro需要可執(zhí)行近數(shù)據(jù)計算的存儲設備作為支撐，需要增加專用硬件.由于缺乏真實基于近數(shù)據(jù)計算的SSD，所以搭建了一個模擬近數(shù)據(jù)計算環(huán)境的測試平臺，用來測試Co-KV與CoPro的性能.主機端與設備端通過千兆以太網(wǎng)接口交互數(shù)據(jù).

測試程序由主機端和設備端組成，主機端子系統(tǒng)運行在雙核Pentium?Dual-Core, E6700 CPU,4 GB內存的計算機上，操作系統(tǒng)是Ubuntu 16.04.利用主機端的計算資源，構建基于近數(shù)據(jù)架構的新型鍵值存儲軟件.設備端需要額外增加專用硬件，本工作采用的是一種基于ARM的開發(fā)板Firefly作為計算單元.設備端運行在ARM開發(fā)板上，配置4GB運行內存，開發(fā)板連接256GB Intel 545S SATA SSD作為存儲介質，開發(fā)板和SATA盤模擬為近數(shù)據(jù)計算盤，操作系統(tǒng)是輕量級嵌入式Ubuntu系統(tǒng)，設計CoPro設備端子系統(tǒng)的鍵值存儲軟件棧.

4.2 測試負載

負載的詳細配置如表2和表3所示.CoPro主要在compaction流程上進行優(yōu)化，而隨機寫又是引起compaction的主要原因之一，所以本節(jié)的測試負載主要集中于隨機寫方面.Co-KV和CoPro使用相同的默認配置，即4 MB MemTable,2 MB SSTable,4 KB data block.鍵值對中的值為16 B.本節(jié)使用DB_Bench(LevelDB默認的測試工具)和YCSB-C(YCSB的C++版本)作為測試工具，測試Co-KV和CoPro的寫放大、吞吐量和CPU使用率等參數(shù).使用YCSB-C作為測試真實環(huán)境下密集型隨機寫負載的測試工具，配置不同的數(shù)據(jù)量和記錄大小，這些都是對compaction有較大影響的參數(shù).請求分布使用zipfian和uniform分布.

Table 2 Workload Characteristics in DB_Bench

Table 3 Workload Characteristics in YCSB-C

4.3 基于DB_Bench負載的測試

在本節(jié)，使用DB_Bench測試Co-KV與CoPro在不同數(shù)據(jù)量、不同大小值的負載下寫放大、吞吐量、compaction帶寬和CPU使用率，并分析實驗數(shù)據(jù)，如圖9所示.

Fig. 9 Results of CoPro and Co-KV under fillrandom- and fillseq-based DB_bench with various data volume圖9 CoPro與Co-KV在DB_Bench順序與隨機寫負載下的實驗結果

寫放大.不管是Co-KV還是CoPro，寫放大主要來自于主機端的寫前日志與主機端的compaction子任務操作.由圖9(a)(b)可知，在隨機寫負載下，當值的大小不變時，隨著數(shù)據(jù)量的增加，兩者寫放大也均在增大(例如在數(shù)據(jù)量10 GB和值為100 B時，Co-KV寫放大為6.16，CoPro寫放大為6.38；在數(shù)據(jù)量50 GB和值為100 B時，Co-KV寫放大為8.49，CoPro寫放大為8.86)；而當數(shù)據(jù)量不變時，隨著鍵值對中值的增大，兩者寫放大均在減小，例如在數(shù)據(jù)量10 GB和值64 KB時，Co-KV寫放大為4.68，CoPro寫放大為4.72.這是由于數(shù)據(jù)量的增加帶來的compaction次數(shù)增加，造成了寫放大的增大；而數(shù)據(jù)量一定的情況下，值的增大導致總的鍵值對減少，compaction次數(shù)減少，寫放大減小.

可以看出，在隨機寫的情況下，CoPro與Co-KV的寫放大差別不大，變化范圍在±5%以內.這是因為CoPro改變Co-KV的compaction的流程，將其中的讀、歸并排序、寫操作按流水線方式組織，但是在SSTable選取時不傾向于選取更多的文件參與，所以在加快compaction速度的同時并不會帶來額外的寫放大.在順序寫負載下，CoPro與Co-KV的寫放大基本相同，這是因為順序寫不涉及大compaction，也就不涉及本文所做的優(yōu)化部分，CoPro與Co-KV處理方式相同，所以寫放大一致.

吞吐量.吞吐量是評價數(shù)據(jù)庫性能優(yōu)劣的重要指標.由圖9(c)(d)可以看出，在隨機寫情況下，不論是何種負載，CoPro的吞吐量都是要大于Co-KV的.這是因為CoPro不僅數(shù)據(jù)并行compaction任務，還流水線并行compaction子任務，加快了compaction子任務的處理效率，最直觀的體現(xiàn)就是在吞吐量上.在實驗最好情況下(數(shù)據(jù)量20 GB和值為100 B)，Co-KV為0.4 MBps,CoPro為0.8 MBps,吞吐量提升了95%.但是隨著值的增大，吞吐量的提升趨勢逐漸下降.在實驗最差情況下(數(shù)據(jù)量20 GB和值64 KB)，Co-KV為1.7 MBps,CoPro為1.9 MBps,吞吐量提升僅為7%.這是因為，當數(shù)據(jù)量一定，值增大時，總的鍵值對減少，導致一次compaction任務中的鍵值對數(shù)量下降，流水線處理方式的優(yōu)勢被大大降低，所以總體的性能提升效果不明顯，與3.3節(jié)的結果一致.通過不同負載的實驗數(shù)據(jù)可以看出，CoPro在處理較小值的負載時能最大程度上發(fā)揮流水線處理方式的優(yōu)勢，而在值增大后，優(yōu)勢逐漸減小，總體性能的提升逐漸降低.

由于順序寫不涉及compaction中的歸并排序操作，所以在順序寫情況下CoPro與Co-KV吞吐量大致相同，沒有太大的變化.

compaction帶寬.本文對主機端與設備端的com-paction子任務處理流程進行優(yōu)化，使用compaction帶寬作為compaction操作性能評測指標.圖9(e)(f)展示的是隨機寫情況下，主機端和設備端的com-paction帶寬變化，由于順序寫不涉及compaction操作，所以不記錄compaction帶寬，本實驗僅針對隨機負載情況.當值大小不變時，隨著數(shù)據(jù)量的增長，主機端和設備端compaction帶寬總體呈現(xiàn)下降的趨勢，這是由于數(shù)據(jù)量增長導致SSTable變多，compaction操作的數(shù)據(jù)量和耗時同時增加，從實驗結果來看，耗時的增長幅度要大于數(shù)據(jù)量的增長幅度，導致了compaction帶寬下降.當數(shù)據(jù)量一定，值增大時，主機端的compaction帶寬逐漸上升，這是因為鍵值對的減少縮短了compaction的處理時間.在設備端，情況更為復雜一些.Co-KV的compaction帶寬隨著值增大而增大，CoPro卻沒有太過明顯的變化規(guī)律.從吞吐量的實驗結果分析中可以看出隨著值增大CoPro的性能提升效果逐漸降低，不管在主機端還是設備端，值增大時CoPro與Co-KV的compaction帶寬也在逐漸接近.

Table 4 Workloads for Scalability Evaluation

Table 5 Compaction Performance and CPU Growth Rate for Co-KV, CoPro and CoPro+ Under YCSB-C

在實驗數(shù)據(jù)的最好情況下(數(shù)據(jù)量20 GB和值為100 B)，Co-KV主機端compaction帶寬為2.09 MBps，設備端帶寬為25.68 MBps；CoPro主機端和設備端compaction帶寬分別為4.90 MBps,42.10 MBps，分別提升134%和64%.在實驗數(shù)據(jù)的最壞情況下(數(shù)據(jù)量20 GB和值64 KB)，Co-KV主機端compaction帶寬為8.42 MBps，設備端帶寬為41.36 MBps；CoPro主機端和設備端compaction帶寬分別為9.87 MBps,45.03 MBps，僅分別提升17%和9%.

CPU使用率.使用流水線方式處理compaction，性能提升的同時不可避免的也增加了資源的消耗，所以測試了主機端與設備端CPU的使用情況來統(tǒng)計CoPro對計算資源的消耗.

由圖9(g)(h)可知，在隨機寫負載下，不論主機端還是設備端，CoPro要比Co-KV的CPU使用率高，最高是在數(shù)據(jù)量20 GB和值為100 B時，Co-KV主機端CPU使用率為10.1%，設備端CPU使用率為42.1%；CoPro主機端CPU使用率為17.6%，設備端使用率為64.8%.CPU使用率分別提高了74%和54%.這是因為CoPro在compaction子任務的處理過程中使用流水線方式，而為了實現(xiàn)流水線方式，新增了2個線程分別處理歸并排序和寫操作，增加了CPU資源的消耗.順序寫情況下不涉及大compaction歸并排序操作，新增線程不參與處理過程，處于睡眠狀態(tài)，所以兩者CPU使用率差別不大.例如在數(shù)據(jù)量20 GB和值為100 B情況下，Co-KV主機端CPU使用率為25.9%，設備端CPU使用率為32.4%；CoPro主機端CPU使用率為26.5%，設備端使用率為33.1%.

4.4 基于YCSB-C負載的測試

在YCSB-C下，首先測試了在不同負載情況下record大小對性能的影響，結果如圖10所示.

Fig. 10 Results of CoPro and Co-KV under zipfian- and uniform-based in YCSB-C with various record size圖10 YCSB-C zipfian和uniform不同record大小負載下CoPro和Co-KV的實驗結果

由圖10(a)所示，在zipfian與uniform負載下CoPro的寫放大與Co-KV差別不大，因為CoPro對compaction的處理流程做了優(yōu)化，并不會帶來額外的寫放大.例如在record size為512 B時，在zipfian負載下，Co-KV寫放大為4.21，CoPro為4.33；在uniform負載下，Co-KV寫放大為6.44，CoPro為6.38.

隨著record增大吞吐量下降，是因為record增大的同時增加了寫入和compaction處理的時間，降低了系統(tǒng)的吞吐量，見圖10(b).在record為1 KB時，Zipfian負載下Co-KV為830.66 ops/s，CoPro為1 533.63 ops/s，uniform負載下Co-KV為441.43 ops/s，CoPro為817.66 ops/s，吞吐量均提升了85%.與在db_bench下的測試結果相同，隨著record增大，CoPro的性能提升效果也逐漸下降.在record為64 KB時CoPro吞吐量僅僅提升11%.

由圖10(c)(d)可知，不論在主機端還是設備端，CoPro的compaction吞吐量均要高于Co-KV，record為1 KB時，zipfian負載下Co-KV與CoPro主機端compaction帶寬分別為2.51 MBps和5.85 MBps，設備端compaction帶寬分別為41.53 MBps和60.14 MBps，帶寬分別提升133%和45%.uniform負載下Co-KV與CoPro主機端compaction帶寬分別為2.29 MBps和5.12 MBps，設備端compaction帶寬分別為34.56 MBps和48.80 MBps，帶寬分別提升124%和41%.這是因為CoPro增加線程加速了compaction過程，相同時間內compaction的數(shù)據(jù)量更多.

在zipfian負載下，record為1 KB時CoPro CPU使用率增長最高，此時Co-KV主機端CPU使用率為8.6%，設備端CPU使用率為36.4%，CoPro主機端CPU使用率為14.9%，設備端CPU使用率為53%，分別增長73%和47%；在uniform負載下，同樣是record為1 KB時CoPro CPU使用率增長最高，此時Co-KV主機端CPU使用率為7.2%，設備端CPU使用率為36.6%，CoPro主機端CPU使用率為12.5%，設備端CPU使用率為54.7%，分別增長74%和49%.具體結果參見圖10(e)(f).

此外，我們在實驗中還測試了數(shù)據(jù)量對各項性能指標的影響，如圖11所示:

Fig. 11 Results of CoPro and Co-KV under YCSB-C with various data volume圖11 CoPro與Co-KV在YCSB-C不同數(shù)據(jù)量實驗結果

隨著數(shù)據(jù)量的增加寫放大呈緩慢上升的趨勢，當數(shù)據(jù)量達到25 GB時，zipfian負載下Co-KV與CoPro寫放大分別為4.6和4.4，uniform負載下Co-KV與CoPro寫放大分別為6.7和6.6.由圖11(a)可知，Co-KV與CoPro寫放大差別不大.

盡管數(shù)據(jù)量變化的同時吞吐量的變化趨勢不明顯，但總體上來說還是隨著數(shù)據(jù)量的增加吞吐量呈下降趨勢，如圖11(b)所示.當數(shù)據(jù)量為5 GB時，zipfian負載下Co-KV與CoPro分別為667.40 ops/s和1 181.95 ops/s.在uniform負載下，Co-KV與CoPro分別為392.22 ops/s和711.12 ops/s.當數(shù)據(jù)量為25 GB時，zipfian負載下Co-KV與CoPro分別為663.82 ops/s和1 155.49 ops/s.在uniform負載下，Co-KV與CoPro分別為385.57 ops/s和682.48 ops/s.

如圖11(c)(d)所示，compaction帶寬的變化趨勢隨數(shù)據(jù)量變化相對來說不明顯，但可以看到，不論是主機端還是設備端，CoPro的compaction帶寬都是要大于Co-KV的，在zipfian負載下，主機端與設備端compaction帶寬分別平均提升126%和55%；在uniform負載下，分別平均提升110%和39%.

CPU使用率基本不受數(shù)據(jù)量變化的影響，因為compaction次數(shù)會隨著數(shù)據(jù)量的增加而增加，但系統(tǒng)總的運行時間也在增加，一段時間內CPU的使用量還是相同的，如圖11(e)(f)所示.

Fig. 12 Results of Co-KV, CoPro, and CoPro+ under YCSB-C at run stage圖12 Co-KV, CoPro, CoPro+在YCSB-C不同負載run階段的實驗結果

4.5 擴展實驗

1) CoPro+實驗

本節(jié)研究CoPro+(具有決策組件的CoPro)在不同工作負載下的性能.由于在3.3節(jié)Vsize的確定實驗中，發(fā)現(xiàn)流水線compaction對值大小敏感，為了簡單測試決策組件的效果，本節(jié)決策組件在決策公式中僅設置Vsize，即閾值與比例閾值，其中值大小的閾值，主機端為32 KB，設備端為16 KB，比例閾值為70%(原因見3.3節(jié))，Ccost與Musage參數(shù)暫未啟用.即CoPro+的決策組件計算公式完全以Vsize為導向，此時的φ=1，α=β=0，fthreshold=1×Vsize=0.7.通過這種配置可以更直觀地展現(xiàn)負載鍵值對中值的大小變化過程中決策組件的作用.表4顯示了此次實驗中配置的4種工作負載.負載W1,W3,W4分別對應工作負載早期、中期和后期出現(xiàn)大鍵值對(大鍵值對的定義見3.3節(jié)).

如圖12所示，其中decision number為系統(tǒng)運行時的檢測點，每個檢測點決策組件會進行一次決策.決策組件初始狀態(tài)默認使用流水線compaction方式.圖12中陰影部分表示運行過程中大鍵值對占比超過70%.當占比小于70%時，決策組件開啟流水線compaction模式，否則，將使用線性compaction模式.當發(fā)生動態(tài)決策時，主機端和設備端中，CoPro+的CPU使用率介于CoPro與Co-KV之間，運行過程中達到閾值時，CoPro+關閉了流水線處理方式，使得CPU使用率下降.compaction帶寬CoPro+更接近于CoPro，因無法保持一段時間內檢測點的數(shù)值均高于閾值，短時間內反復開啟流水線方式，這使得CoPro+對compaction帶寬的影響不是很直觀.

根據(jù)表5的實驗數(shù)據(jù)可知，在大多數(shù)情況下，CoPro+比CoPro用更低的CPU使用率帶來了更高compaction帶寬.這主要歸功于CoPro+在負載中大鍵值對占比較大時關閉了流水線，避免了更多的資源消耗.表5中的CPU與compaction帶寬增長率是相對于Co-KV的增長率，符號MBpCPU表示compaction帶寬除以CPU使用率的值，其表示每1%CPU使用率所帶來的compaction帶寬，CoPro+不論在主機端還是設備端均高于CoPro.與Co-KV相比，主機端基本持平甚至略優(yōu)(負載W1：Co-KV為0.81，CoPro+為0.82)，而設備端則要低于Co-KV(負載W1下Co-KV為0.73，CoPro+為0.70)，由4.3節(jié)和4.4節(jié)的實驗可知，當record大小增大時設備端的處理耗時相比主機端要增加更多，所以CoPro+在設備端的優(yōu)化效果要次于主機端.另外從負載W3實驗結果可知，在寫多讀少的混合負載下，CoPro+依然可以發(fā)揮作用.

CoPro+的作用體現(xiàn)在負載中record大小動態(tài)變化時，其可以降低因流水線compaction而導致的在負載中大鍵值對占比較大時不必要的CPU資源消耗.換句話說，CoPro+能夠以小于CoPro的CPU使用率換來接近于CoPro的compaction帶寬增長.但還是需要根據(jù)實際的情況選擇，要想獲得最好的性能提升效果當然是使用CoPro，但想要節(jié)省CPU資源并不降低太多性能的話，就使用CoPro+.

2) CoPro在讀寫混合負載下的實驗

如圖13所示，我們還分析了不同讀寫比例下Co-KV和CoPro的吞吐量、尾延遲、平均響應時間及主機端和設備端CPU使用率.我們選擇了YCSB作為負載程序，并且設定了2種負載參數(shù)YCSB-A(讀寫混合):load 10 GB,run 10 GB,50%read,50%write.YCSB-B(讀密集)load 10 GB,run 10 GB,90%read,10%write.

Fig. 13 Performance of CoPro under mixed-read-write workloads圖13 讀寫混合負載下的CoPro性能

在YCSB-A負載下，CoPro吞吐量和平均延遲都比Co-KV優(yōu)化了約23.3%；在CPU使用率上我們分別統(tǒng)計了主機端CPU使用率和設備端CPU使用率.發(fā)現(xiàn)CoPro的主機端使用率超過50%，相比Co-KV，提高了2.78倍，說明主機端compaction加入流水線技術后對CPU使用率影響很大，因此我們在CoPro增加了可以對流水線進行控制的機制.而CoPro設備端CPU使用率與CoKV相近.我們測量了CoPro和Co-KV的尾延遲P99，實驗結果表明，CoPro的P99比Co-KV優(yōu)化了10.6%.P99的優(yōu)化主要來自于CoPro對寫操作的優(yōu)化，提高了99%的響應時間.

在YCSB-B負載下，CoPro的吞吐量和平均延遲都比Co-KV下降了約3.2%；同樣我們也發(fā)現(xiàn)CoPro的主機端CPU使用率超過50%，相比Co-KV的10%提高了6.1倍，說明主機端compaction加入流水線技術后密集的讀操作對CPU使用率影響較大，而CoPro設備端CPU使用率與Co-KV相近.對于長尾延遲，實驗結果表明，CoPro的尾延遲P99比Co-KV下降了19%.前面提到CoPro在長尾延遲的優(yōu)化可能來自于寫操作的優(yōu)化，但是在讀密集操作下，這種優(yōu)化無法體現(xiàn)，另外可以看出讀密集負載下CoPro的性能有所下降，主要在于流水線compaction操作消耗了主機CPU資源，由此驗證了主機CPU資源被compaction占用較多時，會影響讀性能.

5 相關工作

5.1 基于LSM-tree的鍵值存儲相關工作

基于LSM-tree的鍵值存儲系統(tǒng)吞吐量高、擴展性強，適用于時延敏感的互聯(lián)網(wǎng)服務，被廣泛應用于大規(guī)模數(shù)據(jù)密集型互聯(lián)網(wǎng)應用中，并逐漸替代傳統(tǒng)關系型數(shù)據(jù)庫，迅速成為研究熱點.

PCP[21]從compaction處理流程入手，提出了一種流水線compaction方法，以更好地利用CPU和I/O并行性來提高compaction性能.為了更好地利用CPU和I/O并行性，文獻[21]將讀、歸并排序、寫階段的執(zhí)行流水線化，以此實現(xiàn)并行compaction操作來改善compaction的性能，但是為了提高流水線的效果，PCP傾向于讓更多的SSTable參與compaction，增加了寫放大.WiscKey[23]提出鍵值分離的方案，將鍵值分開存儲，可以大幅降低LSM-tree的大小與compaction后的讀寫放大.HashKV[24]基于鍵值分離的基礎上，根據(jù)鍵將值散列到多個分區(qū)中，并獨立地對每個分區(qū)進行垃圾回收.GearDB[25]利用疊瓦盤垃圾回收的特點，利用compaction的消除數(shù)據(jù)操作來減少垃圾回收操作.SEALDB[26]通過避免隨機寫入和SMR驅動器上相應的寫入放大來專門為SMR驅動器優(yōu)化.NoveLSM[27]是NVM上LSM-tree的實現(xiàn)，添加了一個基于NVM的內存組件，利用I/O并行性來同時搜索多層以減少查找延遲.SLM-DB[28]在新型字節(jié)型存儲器件Persistent Memory上利用PM的特性使用B+tree作為索引與使用PM進行緩沖寫入，加速讀取時的數(shù)據(jù)檢索并省略了寫前日志的寫開銷.

上述LSM-tree鍵值存儲系統(tǒng)的相關工作均有效地提升了存儲系統(tǒng)性能與吞吐量.但是，以上方案均沒有考慮利用存儲設備所具有的計算資源.隨著近數(shù)據(jù)計算模型研究的深入，學者開始利用具有一定計算能力的存儲設備來處理部分數(shù)據(jù)密集型應用任務，以提升系統(tǒng)性能.

5.2 近數(shù)據(jù)計算相關工作

1) 近數(shù)據(jù)計算基本架構

隨著技術發(fā)展，存儲設備內部的計算資源日益增長，其內部帶寬與外部帶寬日漸懸殊，于是學者們開始研究如何把數(shù)據(jù)密集型應用的部分任務卸載到存儲設備內部進行處理來減少數(shù)據(jù)移動消耗.Kang等人[29]在真實的固態(tài)硬盤上驗證近數(shù)據(jù)計算模型，并將其在SSD固件中實現(xiàn)，通過有效利用SSD內部并行性而提高主機端處理性能.中國科學院計算技術研究所提出了Cognitive SSD[30]，這是一種基于深度學習的非結構化數(shù)據(jù)檢索的節(jié)能引擎，以實現(xiàn)近數(shù)據(jù)深度學習和圖形搜索.不僅是閃存訪問加速器，以FPGA為代表的多功能可編程硬件加速器也逐漸流行起來[31].INSIDER[32]引入了基于FPGA的可重配置驅動控制器作為存儲計算單元，極大提高了使用的靈活性.

2) 近數(shù)據(jù)計算鍵值系統(tǒng)

Co-KV首次利用ARM開發(fā)板將LevelDB的部分compaction任務通過以太網(wǎng)接口發(fā)送到設備端執(zhí)行，主機端處理剩余的compaction任務，實現(xiàn)了compaction任務的靜態(tài)卸載.驗證了近數(shù)據(jù)計算模型可以有效解決LSM-tree寫放大的問題，并且提高了寫操作的吞吐量，減輕了主機端計算任務的壓力.在Co-KV的基礎上，Sun等人又提出動態(tài)卸載方案TStore[33]與DStore[34].分別將NDP設備的執(zhí)行時間和計算資源作為卸載條件，以此為依據(jù)來動態(tài)調整compaction任務的分割比例，從而進一步提高了compaction的執(zhí)行速度，同時有效合理的分割任務，使主機端和設備端的計算資源都能夠充分利用，使系統(tǒng)性能進一步提高.nKV[35]是一個利用本機計算存儲與近數(shù)據(jù)計算的鍵值存儲系統(tǒng)，將讀操作、搜索操作和復雜的圖形處理算法卸載到存儲設備處理.nKV消除了兼容層并利用了NDP上的計算資源，所以有較好的性能表現(xiàn).

上述研究方案很好地展現(xiàn)出近數(shù)據(jù)計算模型的可行性和性能優(yōu)勢，將數(shù)據(jù)密集型應用的部分計算和I/O任務卸載到基于近數(shù)據(jù)計算模型的存儲設備上進行處理，可以有效地利用NDP存儲設備內部的高帶寬，提升任務整體的處理效率.然而上述研究方案大多是直接將應用的某個或多個任務全部卸載到NDP存儲設備上，沒有考慮到主機端計算資源也可參與任務處理，可能會造成主機端資源的空閑與浪費.或者是簡單利用主機端與NDP設備端之間的系統(tǒng)并行性，沒有充分發(fā)揮NDP設備端的并行資源.

6 結 語

本文提出了近數(shù)據(jù)計算架構下compaction的流水并行優(yōu)化方法，CoPro.與Co-KV相比，CoPro分別將主機端和設備端的compaction帶寬提高了2.34倍和1.64倍.與此同時，主機端和設備端的吞吐量均增加了約2倍，CPU使用率分別增加了74.0%和54.0%.在擴展實驗中，與CoPro相比，在不明顯降低性能的同時Co-Pro+將CPU使用率的增長率降低了16.0%.CoPro實現(xiàn)了compaction操作的數(shù)據(jù)并行與流水并行共存，使用流水方式執(zhí)行compaction的同時減小了寫放大.同一compaction任務被主機端與設備端并行執(zhí)行，而在主機端和設備端內部compaction子任務按流水的方式組織并行執(zhí)行.在主機端子系統(tǒng)中，CoPro重新設計了任務卸載調度模塊，使其可以同時支持compaction任務的靜態(tài)卸載方案，增強了可擴展性.增加了度量收集器用于收集主機端子系統(tǒng)運行時的度量信息，為決策組件提供數(shù)據(jù)以實現(xiàn)對系統(tǒng)整體并行度的動態(tài)調整.在設備端子系統(tǒng)中同樣增加了度量收集器以及決策組件，用于收集設備端子系統(tǒng)運行時的度量信息.主機端與設備端的決策組件相互獨立，可以根據(jù)不同的度量信息確定不同的決策，例如可以緩解因值增大造成的性能提升下降與資源消耗上升的問題，使CoPro具有一定程度上的環(huán)境感知功能.通過真實硬件模擬近數(shù)據(jù)計算環(huán)境進行驗證實驗和擴展實驗，實驗結果顯示CoPro在不帶來額外寫放大的前提下進一步提升了compaction性能.

作者貢獻聲明：孫輝、婁本冬負責工作思路、系統(tǒng)搭建、實現(xiàn)及測試；黃建忠、趙雨虹、符松主要負責思路及實驗討論.