王海濤 李戰(zhàn)懷 張 曉 趙曉南

(西北工業(yè)大學(xué)計(jì)算機(jī)學(xué)院 西安 710129) (大數(shù)據(jù)存儲(chǔ)與管理工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室(西北工業(yè)大學(xué)) 西安 710129)

隨著Web 2.0和云計(jì)算的快速發(fā)展，現(xiàn)代社會(huì)已經(jīng)步入大數(shù)據(jù)時(shí)代，數(shù)據(jù)體量和訪問(wèn)量呈爆發(fā)式增長(zhǎng)，傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)逐漸難以適應(yīng)大量高并發(fā)的數(shù)據(jù)存儲(chǔ)和訪問(wèn)需求[1-2].在此場(chǎng)景下，鍵值(key-value, KV)存儲(chǔ)架構(gòu)應(yīng)運(yùn)而生.簡(jiǎn)而言之，KV存儲(chǔ)將一組鍵(key)映射到關(guān)聯(lián)的值(value)，用戶通過(guò)GET,PUT以及DELETE等簡(jiǎn)單的接口進(jìn)行操作，相對(duì)于傳統(tǒng)的關(guān)系型數(shù)據(jù)庫(kù)管理系統(tǒng)具有更好的性能、可伸縮性和可用性[3-4]，成為了眾多大數(shù)據(jù)應(yīng)用系統(tǒng)的關(guān)鍵組件，廣泛應(yīng)用在各種數(shù)據(jù)密集型的服務(wù)系統(tǒng)中，例如Web索引、電子商務(wù)和云存儲(chǔ)等.

目前流行的KV存儲(chǔ)系統(tǒng)大都基于日志結(jié)構(gòu)合并(log-structured merge, LSM)樹[5]而不是傳統(tǒng)的B樹索引結(jié)構(gòu)，如BigTable[6],Cassandra[7],HBase[8],LevelDB[9]以及RocksDB[10]等.主要原因是在眾多的大數(shù)據(jù)系統(tǒng)中，KV存儲(chǔ)的寫入性能非常關(guān)鍵，而LSM樹對(duì)數(shù)據(jù)的寫入操作進(jìn)行了優(yōu)化.其基本思路是首先在內(nèi)存中對(duì)寫請(qǐng)求進(jìn)行緩存和合并，然后再批量寫入到存儲(chǔ)設(shè)備中，從而將隨機(jī)寫操作轉(zhuǎn)換為順序?qū)懖僮?，提升用戶寫入性?但是這種KV存儲(chǔ)在處理頻繁的小塊數(shù)據(jù)更新負(fù)載時(shí)，寫性能開銷依舊很大.

LSM樹的寫性能開銷主要由2部分構(gòu)成：

1) 由數(shù)據(jù)壓縮(compaction)操作引入的開銷.數(shù)據(jù)壓縮是LSM樹必需的操作，其目的是保證KV數(shù)據(jù)的有序性以及進(jìn)行垃圾回收，使得用戶在進(jìn)行查詢操作的時(shí)候能夠迅速定位到所需的KV數(shù)據(jù)，提高用戶的讀性能.數(shù)據(jù)壓縮操作需要讀取多個(gè)key范圍有重合的數(shù)據(jù)文件，對(duì)數(shù)據(jù)進(jìn)行合并排序后再寫入到新的文件中，然后刪除舊的數(shù)據(jù)文件.這個(gè)過(guò)程中涉及大量數(shù)據(jù)的重復(fù)寫入，造成了數(shù)據(jù)的寫放大，增加了性能開銷.

2) 由KV存儲(chǔ)系統(tǒng)的日志機(jī)制引入的性能開銷.首先，KV存儲(chǔ)通常利用預(yù)寫日志(write-ahead log, WAL)來(lái)保證KV數(shù)據(jù)的可靠性，以確保在系統(tǒng)崩潰時(shí)能夠恢復(fù)正常數(shù)據(jù).因此，每次寫入操作的數(shù)據(jù)需要首先寫入WAL，然后才能寫入目標(biāo)文件.其次，基于LSM樹的KV存儲(chǔ)系統(tǒng)一般使用通用的文件系統(tǒng)(如Ext4)來(lái)存儲(chǔ)數(shù)據(jù)，文件系統(tǒng)本身也通過(guò)自帶的日志機(jī)制來(lái)保證數(shù)據(jù)一致性，因此造成了多重日志的問(wèn)題，進(jìn)一步增加了性能開銷.此外，通用文件系統(tǒng)中復(fù)雜的功能和軟件棧也會(huì)增加性能開銷.本文中將這些性能開銷統(tǒng)稱為日志開銷.對(duì)于插入密集型的小塊KV負(fù)載，WAL文件的更新將非常頻繁，從而導(dǎo)致嚴(yán)重的日志開銷，造成KV存儲(chǔ)系統(tǒng)寫入性能的劇烈下降.

本文針對(duì)上述性能問(wèn)題，提出了一個(gè)稱為RocksFS的優(yōu)化文件系統(tǒng)，避免了通用文件系統(tǒng)中復(fù)雜的功能和軟件棧引入的額外負(fù)載，同時(shí)通過(guò)優(yōu)化日志存儲(chǔ)結(jié)構(gòu)以及更新流程來(lái)減小日志更新引入的元數(shù)據(jù)負(fù)載，從而提升KV存儲(chǔ)系統(tǒng)寫性能.最終在業(yè)界廣泛應(yīng)用的KV存儲(chǔ)系統(tǒng)RocksDB上進(jìn)行了驗(yàn)證，結(jié)果表明相對(duì)于通用文件系統(tǒng)，RocksFS能夠有效提高KV存儲(chǔ)的寫入和更新性能，特別是對(duì)于插入密集型的小塊KV負(fù)載.

1 相關(guān)工作

基于LSM樹的KV存儲(chǔ)系統(tǒng)在大數(shù)據(jù)系統(tǒng)中應(yīng)用廣泛，受到了工業(yè)界和學(xué)術(shù)界的持續(xù)關(guān)注.針對(duì)這類KV存儲(chǔ)系統(tǒng)的寫性能問(wèn)題，國(guó)內(nèi)外的研究人員從不同的角度提出了一些優(yōu)化方案.

WiscKey[11]基于LevelDB實(shí)現(xiàn)了一種新的存儲(chǔ)機(jī)制，其核心思路是將key和value解耦并分開存儲(chǔ)，只對(duì)key進(jìn)行排序，而value則追加到獨(dú)立的日志中.該機(jī)制可避免數(shù)據(jù)排序時(shí)value的移動(dòng)，減小數(shù)據(jù)壓縮過(guò)程中的讀寫放大.但是由于沒(méi)有對(duì)value進(jìn)行排序，因此KV數(shù)據(jù)范圍檢索的性能降低，且需要有垃圾回收操作來(lái)處理日志中的舊數(shù)據(jù)，引入了額外的負(fù)載.

PebblesDB[12]實(shí)現(xiàn)了一種基于片段的日志結(jié)構(gòu)合并(fragmented log-structured merge, FLSM)樹，只維持片段之間的有序性，而片段內(nèi)部的不同文件之間無(wú)序，避免了KV數(shù)據(jù)壓縮過(guò)程中引入的同一層數(shù)據(jù)的重寫操作，從而減小了壓縮操作引入的數(shù)據(jù)寫放大.但是由于無(wú)法保證每一層數(shù)據(jù)完全有序，讀性能以及范圍檢索性能有所降低.

SkipStore[13]在LSM樹結(jié)構(gòu)基礎(chǔ)上實(shí)現(xiàn)了一個(gè)針對(duì)壓縮操作優(yōu)化的KV存儲(chǔ)系統(tǒng)，在KV數(shù)據(jù)壓縮的過(guò)程中跳過(guò)一些中間層，將相關(guān)的數(shù)據(jù)直接壓縮到不相鄰的組件中，從而加速數(shù)據(jù)壓縮流程，減少壓縮操作造成的寫放大，提高KV存儲(chǔ)系統(tǒng)寫入性能.但是由于增加了讀流程的復(fù)雜性，讀取性能有所下降.

這些研究工作能夠減小KV數(shù)據(jù)壓縮過(guò)程中引入的寫放大，從而提高寫入性能.然而讀性能以及范圍檢索性能有所損失，且忽略了本地文件系統(tǒng)以及多重日志引入的負(fù)載.FlashKV[14-15]在LevelDB的基礎(chǔ)上，利用Open-Channel SSD[16-17]實(shí)現(xiàn)了一個(gè)由用戶層直接管理閃存存儲(chǔ)空間的KV存儲(chǔ)系統(tǒng)，去除了文件系統(tǒng)層以及SSD內(nèi)部的閃存轉(zhuǎn)換層(flash translation layer, FTL)等功能有重合的層級(jí)，從而解決了多重日志的問(wèn)題，但是依賴于特定的硬件設(shè)備.

總之，現(xiàn)有研究工作主要關(guān)注KV存儲(chǔ)系統(tǒng)中的壓縮負(fù)載，忽略了多重日志以及文件系統(tǒng)引入的負(fù)載，或者是需要特定的硬件支持來(lái)降低多重日志開銷.本文主要關(guān)注在通用硬件基礎(chǔ)上，如何減小文件系統(tǒng)以及多重日志的開銷以提升KV存儲(chǔ)系統(tǒng)的寫入和更新性能.

2 研究背景和動(dòng)機(jī)

本節(jié)以流行的KV存儲(chǔ)系統(tǒng)RocksDB為例，簡(jiǎn)要介紹基于LSM樹的KV存儲(chǔ)系統(tǒng)的架構(gòu)以及基本操作，分析WAL文件引入的日志開銷問(wèn)題.

2.1 LSM樹的基本架構(gòu)和操作

LSM樹[3]是一種支持高效索引的數(shù)據(jù)持久性存儲(chǔ)結(jié)構(gòu)，其基本思路是通過(guò)聚合內(nèi)存中的多個(gè)更新操作并將其批量刷新到存儲(chǔ)中，從而將隨機(jī)寫轉(zhuǎn)換為順序?qū)懸蕴嵘龑懶阅?圖1以RocksDB為例，展示了典型的LSM樹架構(gòu).RocksDB是由Facebook開源的一個(gè)典型的基于LSM樹的KV存儲(chǔ)系統(tǒng)，目前廣泛用于Facebook等眾多大數(shù)據(jù)系統(tǒng)中.RocksDB包含6個(gè)基本組件：memtable,immutable memtable,sstfile,WAL,Manifest和Current.其中memtable和immutable memtable常駐內(nèi)存，而其他文件位于硬盤上.

Fig. 1 Typical architecture of LSM-tree[3]圖1 LSM樹的典型架構(gòu)[3]

插入KV數(shù)據(jù)時(shí)，首先將數(shù)據(jù)追加到WAL文件中，然后將其刷新到磁盤以保證數(shù)據(jù)的持久性和安全性，之后將數(shù)據(jù)插入memtable以方便KV數(shù)據(jù)的查找與合并.memtable中的KV數(shù)據(jù)按照key的順序進(jìn)行排序，方便對(duì)最近插入的KV進(jìn)行高效查找和掃描.當(dāng)memtable填滿時(shí)，將其轉(zhuǎn)化為只讀的immutable memtable，然后將其順序?qū)懭氲酱鎯?chǔ)設(shè)備上的有序字符串表文件(sorted string table file, sstfile)中.Manifest和Current是輔助文件，前者存儲(chǔ)sstfile的元數(shù)據(jù)；后者記錄當(dāng)前Manifest文件的名稱，方便數(shù)據(jù)的檢索.

RocksDB為每個(gè)Li層配置了數(shù)據(jù)量閾值，當(dāng)達(dá)到閾值時(shí)將啟動(dòng)壓縮(compaction)操作，選擇該層中的部分sstfile與Li+1中key范圍與之有重合的sstfile進(jìn)行合并排序，然后將排序好的數(shù)據(jù)順序?qū)懭隠i+1中新的sstfile中，再刪除相關(guān)的舊文件.因此memtable中包含最新的數(shù)據(jù)，然后依次是L0，L1，…層中的文件.由于L0層的數(shù)據(jù)是由內(nèi)存中的memtable直接刷新到磁盤生成的，因此L0層的不同sstfile中的key可能會(huì)有重合，而L0層以外的各層是通過(guò)壓縮操作生成的，具有相同key的數(shù)據(jù)已經(jīng)進(jìn)行了合并，因此沒(méi)有重合數(shù)據(jù).

LSM樹中數(shù)據(jù)的刪除操作通過(guò)插入刪除標(biāo)記的形式來(lái)處理，以利用插入操作的性能優(yōu)勢(shì).具體而言，當(dāng)需要?jiǎng)h除某個(gè)KV數(shù)據(jù)時(shí)，LSM樹首先在memtable中搜索key并為其設(shè)置刪除標(biāo)記以表示該KV數(shù)據(jù)已被刪除.如果memtable中找不到該key，則LSM樹只為該key創(chuàng)建索引并插入刪除標(biāo)記.在后續(xù)的壓縮操作中，所有包含刪除標(biāo)記的KV數(shù)據(jù)都不會(huì)合并到新的sstfile中.通過(guò)這種方法，隨機(jī)刪除操作轉(zhuǎn)換為順序插入從而提高了操作性能.

LSM樹的數(shù)據(jù)查找基本流程是，從內(nèi)存中的memtable開始，由上到下逐層搜索，直到找到所需的key或者確定其不在系統(tǒng)中.與B樹相比，LSM樹的點(diǎn)查詢操作可能需要多次的磁盤讀操作，從而導(dǎo)致讀取性能不高.因此，在實(shí)際中，LSM樹一般應(yīng)用于寫密集型的場(chǎng)景，并利用布隆過(guò)濾器(Bloom filter)[18]等方法加速查詢操作.

2.2 LSM樹的日志負(fù)載

LSM樹在進(jìn)行寫入操作時(shí)，數(shù)據(jù)首先持久化到WAL文件中，然后才可以寫入指定的文件，目的是保證數(shù)據(jù)的可靠性.雖然用戶可以選擇在RocksDB的配置中關(guān)閉WAL，或者設(shè)置WAL為非同步，即不及時(shí)將WAL中的數(shù)據(jù)刷新入磁盤.但是，對(duì)于許多云存儲(chǔ)系統(tǒng)或Web應(yīng)用的數(shù)據(jù)管理系統(tǒng)，確保數(shù)據(jù)的可靠性通常至關(guān)重要，這意味著必須盡快將WAL同步到磁盤.因此，本文關(guān)注于WAL同步的場(chǎng)景.

圖2展示了RocksDB中WAL的寫I/O路徑.一次WAL的寫入會(huì)觸發(fā)多個(gè)磁盤操作，因?yàn)槌薟AL中新加的數(shù)據(jù)需要及時(shí)寫入磁盤之外，WAL文件的元數(shù)據(jù)(主要是有效數(shù)據(jù)的大小)在每次數(shù)據(jù)更新之后都會(huì)發(fā)生變化，也必須同步到磁盤以保持文件系統(tǒng)的數(shù)據(jù)一致性.具體來(lái)說(shuō)，當(dāng)WAL寫請(qǐng)求到達(dá)時(shí)，將執(zhí)行5個(gè)步驟：①將新數(shù)據(jù)寫入WAL文件；②將新數(shù)據(jù)刷新到磁盤；③將WAL文件的元數(shù)據(jù)寫入到元數(shù)據(jù)文件中；④將元數(shù)據(jù)文件刷新到磁盤;⑤向用戶返回WAL寫入成功的消息.因此，小塊KV數(shù)據(jù)的頻繁更新會(huì)引入大量的WAL寫操作，造成嚴(yán)重的性能開銷.本文將這些由于WAL寫入造成的性能開銷稱為日志開銷.

具體來(lái)說(shuō)，日志開銷包括WAL數(shù)據(jù)寫入開銷及其引入的元數(shù)據(jù)更新開銷.WAL是保證數(shù)據(jù)可靠性所必需的，因此無(wú)法減小其數(shù)據(jù)寫入開銷.但是可以通過(guò)減少元數(shù)據(jù)更新來(lái)降低日志開銷.圖3展示了元數(shù)據(jù)更新引入的日志開銷的嚴(yán)重性.具體測(cè)試方法是調(diào)用RocksDB的PUT接口將具有不同value大小的KV數(shù)據(jù)(總量為256 MB)寫入RocksDB，并收集WAL文件的元數(shù)據(jù)更新數(shù)據(jù)量與實(shí)際寫入磁盤的數(shù)據(jù)量進(jìn)行對(duì)比.

Fig. 2 Write path of WAL in RocksDB圖2 RocksDB中WAL的寫I/O路徑

Fig. 3 Metadata overhead of WAL file圖3 WAL文件元數(shù)據(jù)負(fù)載

由圖3可以看到，寫入磁盤的元數(shù)據(jù)量遠(yuǎn)超原始的WAL寫入數(shù)據(jù)量.例如，當(dāng)value大小為16 B時(shí)，數(shù)據(jù)更新造成的元數(shù)據(jù)寫入量達(dá)到了35 GB，而實(shí)際寫入磁盤的元數(shù)據(jù)量超過(guò)了70 GB，超過(guò)了原始的WAL寫入量(256 MB)的200倍.主要原因是為了保證WAL文件的元數(shù)據(jù)及時(shí)更新到磁盤，RocksDB使用直接I/O(即寫入文件時(shí)設(shè)置O_DIRECT選項(xiàng))來(lái)同步元數(shù)據(jù)，每次寫入都必須與塊大小一致(在RocksDB中默認(rèn)為4 KB)，因此不足4 KB的元數(shù)據(jù)寫入請(qǐng)求需要進(jìn)行補(bǔ)零操作進(jìn)行塊對(duì)齊才能寫入磁盤.因此，在小塊數(shù)據(jù)頻繁更新的場(chǎng)景下，WAL的頻繁寫入會(huì)造成嚴(yán)重的寫放大，大幅降低寫性能.

在通用文件系統(tǒng)中，上層應(yīng)用無(wú)法細(xì)粒度地控制元數(shù)據(jù)更新，因而難以根據(jù)負(fù)載模式進(jìn)行元數(shù)據(jù)更新流程的優(yōu)化.同時(shí)，通用文件系統(tǒng)中的日志功能與KV存儲(chǔ)系統(tǒng)中的WAL機(jī)制在功能上有重疊，造成了多重日志的問(wèn)題.雖然通用文件系統(tǒng)中可能有一些配置選項(xiàng)可以關(guān)閉日志，但這樣會(huì)增大當(dāng)前系統(tǒng)中其他應(yīng)用的數(shù)據(jù)安全性風(fēng)險(xiǎn).

基于上述背景，本文提出了一個(gè)名為RocksFS的優(yōu)化文件系統(tǒng)，針對(duì)LSM樹的KV存儲(chǔ)系統(tǒng)的負(fù)載模式進(jìn)行優(yōu)化，只保留KV負(fù)載所需的功能和接口，并重新設(shè)計(jì)WAL的存儲(chǔ)結(jié)構(gòu)和更新流程以減小元數(shù)據(jù)負(fù)載，大幅提升了小塊KV數(shù)據(jù)的寫入和更新性能.

3 設(shè)計(jì)與實(shí)現(xiàn)

本節(jié)分析RocksFS的系統(tǒng)架構(gòu)以及WAL寫入流程的優(yōu)化方法.

3.1 RocksFS系統(tǒng)架構(gòu)

如圖4所示，RocksFS是一個(gè)用戶庫(kù)，RocksDB可通過(guò)RocksFS管理塊設(shè)備，繞過(guò)復(fù)雜的通用文件系統(tǒng)，從而去除不必要的文件系統(tǒng)開銷.RocksFS只有2種不同的磁盤結(jié)構(gòu)(即塊和文件)，存儲(chǔ)設(shè)備的第1個(gè)塊是版本塊(Version)，用于記錄此文件系統(tǒng)的版本信息；第2個(gè)塊是超級(jí)塊(Super Block)，用于記錄文件系統(tǒng)的元數(shù)據(jù)，例如設(shè)備路徑和元數(shù)據(jù)文件的位置等.元數(shù)據(jù)文件(metadata file)位于超級(jí)塊之后，用于記錄文件系統(tǒng)中的其他文件的元數(shù)據(jù).每次文件更新時(shí)，必須將相應(yīng)的元數(shù)據(jù)更新寫入元數(shù)據(jù)文件，并且同步到磁盤以確保數(shù)據(jù)一致性.當(dāng)RocksDB掛載RocksFS時(shí)，將會(huì)加載元數(shù)據(jù)文件到內(nèi)存中并重放，從而恢復(fù)RocksFS的所有元數(shù)據(jù).RocksFS中每個(gè)文件的元數(shù)據(jù)量很小(不超過(guò)128 B)，因此對(duì)于RocksFS這樣的輕量級(jí)文件系統(tǒng)，將所有元數(shù)據(jù)緩存在內(nèi)存中以提高性能是合理的.

Fig. 4 Architecture of RocksFS圖4 RocksFS架構(gòu)

需要注意的是，元數(shù)據(jù)文件由一塊連續(xù)空間加上元數(shù)據(jù)塊索引信息組成，以支持元數(shù)據(jù)文件的動(dòng)態(tài)變化.索引信息常駐內(nèi)存，可迅速定位到分布在硬盤其他位置的各個(gè)元數(shù)據(jù)塊以保證訪問(wèn)性能.由于元數(shù)據(jù)塊分布在硬盤的不同位置，因此一般不會(huì)造成硬盤某一位置成為熱點(diǎn).此外，對(duì)于目前流行的SSD來(lái)說(shuō)，設(shè)備內(nèi)部的閃存轉(zhuǎn)化層會(huì)將上層應(yīng)用的寫請(qǐng)求分散在不同的物理位置上，并且以異地更新的方式寫入新數(shù)據(jù)，同時(shí)預(yù)留空間、垃圾回收以及磨損均衡等技術(shù)放置某一物理位置的頻繁擦除.因此即使上層應(yīng)用對(duì)某塊元數(shù)據(jù)頻繁更新，對(duì)SSD的整體壽命也影響不大.

Fig. 5 Main data structures in RocksFS圖5 RocksFS主要數(shù)據(jù)結(jié)構(gòu)

圖5展示了RocksFS中的主要數(shù)據(jù)結(jié)構(gòu).RocksFS僅支持2層目錄，即目錄中只有文件但沒(méi)有子目錄.目錄映射表(dirmap)將目錄名稱映射到目錄結(jié)構(gòu)(dir)，目錄結(jié)構(gòu)中包含此目錄下的文件映射表(filemap)，而文件映射表將索引節(jié)點(diǎn)(inode)映射到具體文件結(jié)構(gòu)(file).文件結(jié)構(gòu)只包含5個(gè)成員，包括1個(gè)文件節(jié)點(diǎn)(fnode)、1個(gè)64 b文件引用計(jì)數(shù)(refs)，3個(gè)bool變量指示這個(gè)文件是否臟(dirty)、鎖定(locked)或刪除(deleted).fnode結(jié)構(gòu)封裝了文件的關(guān)鍵元數(shù)據(jù)，包括inode編號(hào)(ino)、數(shù)據(jù)大小(size)、修改時(shí)間(mtime)以及表示此文件磁盤空間映射表(extents).通過(guò)這些結(jié)構(gòu)，RocksFS能夠支持RocksDB所需的文件操作.

3.2 優(yōu)化WAL存儲(chǔ)結(jié)構(gòu)

圖6展示了RocksDB中的WAL文件格式.WAL文件由一系列不同長(zhǎng)度的記錄組成(即r0，r1等)，每條記錄中包含了一次寫請(qǐng)求對(duì)應(yīng)的數(shù)據(jù)以及校驗(yàn)信息，并按kBlockSize(默認(rèn)32 KB)的大小進(jìn)行分組，不足的空間用空(null)數(shù)據(jù)填充(即P).讀寫操作都以kBlockSize為單位進(jìn)行.

Fig. 6 Original WAL file format in RocksDB圖6 RocksDB中原始的WAL文件格式

Fig. 8 WAL write path in RocksFS圖8 RocksFS中的WAL寫流程

每個(gè)數(shù)據(jù)塊寫入WAL之后，首先將其刷新到底層磁盤，然后將元數(shù)據(jù)的更新寫入元數(shù)據(jù)文件，并及時(shí)將元數(shù)據(jù)文件寫入磁盤中以保證數(shù)據(jù)和元數(shù)據(jù)的一致性.通用的文件系統(tǒng)(如Ext4)必須在將新數(shù)據(jù)寫入WAL后及時(shí)將WAL的元數(shù)據(jù)(關(guān)鍵是有效數(shù)據(jù)量)寫入元數(shù)據(jù)文件，否則RocksDB將難以確定需要從WAL文件讀取的數(shù)據(jù)量，導(dǎo)致無(wú)法恢復(fù)正確的數(shù)據(jù).然而正如2.2節(jié)所述，這些頻繁的元數(shù)據(jù)更新操作造成了嚴(yán)重的日志負(fù)載.

為了解決這個(gè)問(wèn)題，RocksFS重新設(shè)計(jì)了WAL存儲(chǔ)結(jié)構(gòu)，如圖7所示.將來(lái)自RocksDB的記錄(即r0，r1等)封裝到事務(wù)中.每個(gè)事務(wù)都有一個(gè)頭字段(Head)來(lái)指示其開始，一個(gè)長(zhǎng)度字段(Len)記錄其數(shù)據(jù)量，以及一個(gè)尾部字段(Tail)包含數(shù)據(jù)校驗(yàn)信息并標(biāo)志事務(wù)的結(jié)束.由于事務(wù)中包含了記錄的長(zhǎng)度信息以及校驗(yàn)信息，因此不再需要頻繁地向元數(shù)據(jù)文件中更新WAL的元數(shù)據(jù)，而只需順序讀取WAL并解碼數(shù)據(jù)即可恢復(fù)有效事務(wù).RocksFS接收到上層傳來(lái)的寫請(qǐng)求之后，首先將其包裝為事務(wù)，然后將數(shù)據(jù)追加到WAL中，通過(guò)優(yōu)化后的WAL寫入流程(見3.3節(jié))有條件地更新元數(shù)據(jù)，能夠大幅降低元數(shù)據(jù)更新頻率，提升存儲(chǔ)性能.

Fig. 7 New WAL file format in RocksFS圖7 RocksFS中新的WAL格式

RocksFS中的kBlockSize參數(shù)是根據(jù)RocksDB的對(duì)應(yīng)參數(shù)設(shè)置的.RocksDB使用直接I/O讀寫WAL，因此I/O塊大小必須與磁盤塊(默認(rèn)4 KB)大小對(duì)齊.設(shè)置較大粒度的I/O塊(如32 KB)能夠提升WAL讀寫帶寬，但是也會(huì)造成數(shù)據(jù)可靠性的粒度增大，寫入失敗時(shí)可能丟失的數(shù)據(jù)會(huì)增多.因此根據(jù)實(shí)際應(yīng)用場(chǎng)景的權(quán)衡，RocksDB將其默認(rèn)值設(shè)置為32 KB.由于RocksFS文件系統(tǒng)是根據(jù)此參數(shù)格式化創(chuàng)建的，因此無(wú)法動(dòng)態(tài)調(diào)整該參數(shù).并且寫入性能主要取決于元數(shù)據(jù)更新負(fù)載，而kBlockSize對(duì)元數(shù)據(jù)的更新頻率影響不大，實(shí)現(xiàn)該參數(shù)的動(dòng)態(tài)調(diào)整難以提升寫入性能.

3.3 優(yōu)化WAL寫入流程

優(yōu)化后的WAL寫流程如圖8所示.當(dāng)一批來(lái)自RocksDB的WAL文件寫操作到達(dá)RocksFS時(shí)，執(zhí)行4個(gè)步驟：

1) 將寫請(qǐng)求編碼到事務(wù)中.

2) 檢查WAL文件的大小，確定是否可以容納當(dāng)前事務(wù).

3) 如果WAL中有足夠的空閑空間，則只需將事務(wù)追加到WAL中并將數(shù)據(jù)同步到磁盤.

4) 如果WAL中沒(méi)有足夠的空閑空間，為此WAL分配一塊新的空間(默認(rèn)為4 MB)，將事務(wù)寫入其中并將數(shù)據(jù)同步到磁盤，然后更新WAL文件的元數(shù)據(jù)并將其同步到磁盤.

由于RocksDB中memtable的默認(rèn)大小為4 MB，因此在將memtable寫入磁盤之前，系統(tǒng)會(huì)創(chuàng)建4 MB大小的WAL文件.默認(rèn)配置下，這種粒度的WAL足以承載memtable的所有更新，因此無(wú)須將其設(shè)置得更大.在RocksFS中，只要WAL文件有充足的可用空間，就不需要更新其元數(shù)據(jù)，從而消除了大量的元數(shù)據(jù)更新，尤其是對(duì)于寫密集型的小塊KV負(fù)載.

RocksFS利用直接I/O(direct I/O)實(shí)現(xiàn)文件讀寫.通用文件系統(tǒng)中，使用緩存I/O(buffered I/O)一般可以提升性能，但是會(huì)造成數(shù)據(jù)在多級(jí)緩存中重復(fù)拷貝，消耗大量?jī)?nèi)存的同時(shí)也引入了額外的數(shù)據(jù)拷貝開銷以及緩存一致性開銷.由于RocksDB中的WAL更新需要盡快同步到磁盤以保證數(shù)據(jù)可靠性，因此在這種情況下使用直接I/O更簡(jiǎn)單有效，并且能夠減小系統(tǒng)內(nèi)存消耗.

3.4 崩潰一致性保證

為了保證RocksFS的崩潰一致性(crash consist-ency)，RocksFS中提供2類恢復(fù)機(jī)制：數(shù)據(jù)恢復(fù)機(jī)制和元數(shù)據(jù)恢復(fù)機(jī)制.數(shù)據(jù)的寫入通過(guò)WAL文件來(lái)保證原子性和安全性，只有在WAL寫入完成后，才將更新的數(shù)據(jù)寫入實(shí)際的文件.如果在文件寫入過(guò)程中發(fā)生崩潰，則使用WAL文件重做寫入操作以替換損壞的數(shù)據(jù)，恢復(fù)正確的數(shù)據(jù).為了保證元數(shù)據(jù)的可靠性，元數(shù)據(jù)的更新以事務(wù)的形式同步到元數(shù)據(jù)文件，并立即將元數(shù)據(jù)文件刷新到磁盤中.如果在更新元數(shù)據(jù)的過(guò)程中發(fā)生崩潰，則在重新掛載RocksFS時(shí)，將元數(shù)據(jù)文件加載到內(nèi)存中并重放其中的有效事務(wù)以恢復(fù)元數(shù)據(jù)，保持?jǐn)?shù)據(jù)與元數(shù)據(jù)之間的一致性.

RocksFS基于Ceph[19]的本地存儲(chǔ)引擎文件系統(tǒng)BlueFS實(shí)現(xiàn)，通過(guò)Ceph中自帶的文件系統(tǒng)功能測(cè)試工具(bluefs_test)進(jìn)行了完備性檢查，證明了其功能的完備性.BlueFS是分布式存儲(chǔ)系統(tǒng)Ceph針對(duì)RocksDB開發(fā)的簡(jiǎn)化版文件系統(tǒng)，用于支持其本地存儲(chǔ)引擎的小塊數(shù)據(jù)以及元數(shù)據(jù)存儲(chǔ).與BlueFS類似，RocksFS僅支持RocksDB所必需的操作，從而降低文件系統(tǒng)開銷.不同之處在于，RocksFS同時(shí)優(yōu)化了WAL的存儲(chǔ)結(jié)構(gòu)以及事務(wù)寫入流程，大幅降低了元數(shù)據(jù)更新負(fù)載.此外，RocksFS以共享庫(kù)的方式實(shí)現(xiàn)，可脫離RocksDB獨(dú)立使用，方便其他應(yīng)用程序調(diào)用.

4 實(shí)驗(yàn)與分析

本節(jié)在RocksDB的場(chǎng)景下，對(duì)比了RocksFS以及其他4個(gè)典型通用文件系統(tǒng)的性能，證明了RocksFS能夠大幅提升小塊KV數(shù)據(jù)的寫入和更新性能.

4.1 實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)設(shè)置如表1所示，通過(guò)RocksDB自帶的db_bench基準(zhǔn)測(cè)試工具進(jìn)行性能測(cè)試，測(cè)試的負(fù)載模式包括fillseq,fillrandom,readseq,readrandom,overwrite以及updaterandom.在配置不同文件系統(tǒng)的前提下，使用16個(gè)線程進(jìn)行壓力測(cè)試，對(duì)比RocksDB的性能.由于在典型的KV存儲(chǔ)應(yīng)用場(chǎng)景中，絕大部分的key大小不超過(guò)16 B，而value大小不超過(guò)1 KB[20]，因此實(shí)驗(yàn)中設(shè)置key的大小為16 B，value的大小分別設(shè)置為16 B,64 B,256 B,1 KB,4 KB以及16 KB，這可以代表大多數(shù)場(chǎng)景下的KV工作負(fù)載.實(shí)驗(yàn)中開啟了RocksDB的WAL同步選項(xiàng)，以測(cè)試在高數(shù)據(jù)可靠性要求場(chǎng)景下的KV存儲(chǔ)性能.

Table 1 Experiment Settings表1 實(shí)驗(yàn)設(shè)置

由于每輪測(cè)試中value大小都是常量，因此可以使用每次基準(zhǔn)測(cè)試的IOPS(即每秒完成的I/O操作)中位數(shù)統(tǒng)計(jì)值來(lái)代表各個(gè)文件系統(tǒng)下RocksDB的性能.每項(xiàng)測(cè)試中進(jìn)行100萬(wàn)次KV數(shù)據(jù)操作，每次測(cè)試之前首先清空系統(tǒng)緩存，然后按順序執(zhí)行6個(gè)基準(zhǔn)測(cè)試：

1) fillseq.隨機(jī)生成key和value，并按照key的順序插入KV數(shù)據(jù).

2) readseq.從已有KV數(shù)據(jù)庫(kù)中按照key的順序讀取value.

3) readrandom.從已有KV數(shù)據(jù)庫(kù)中以隨機(jī)的key序列讀取value.

4) overwrite.以異步的方式，通過(guò)隨機(jī)的key序列重寫已有KV數(shù)據(jù)庫(kù)中的value.

5) updaterandom.以讀改寫的方式，通過(guò)隨機(jī)的key序列修改已有KV數(shù)據(jù)庫(kù)中的value.

6) fillrandom.以異步的方式，通過(guò)隨機(jī)的key序列向已有KV數(shù)據(jù)庫(kù)中寫入KV數(shù)據(jù).

需要注意的是，在進(jìn)行SSD上的性能測(cè)試時(shí)，隨著寫入數(shù)據(jù)量的增加，可能會(huì)觸發(fā)SSD內(nèi)部的垃圾回收操作，導(dǎo)致性能突然下降.因此，在每輪文件系統(tǒng)測(cè)試之前，首先擦除整個(gè)SSD，以最大限度地減小前一輪測(cè)試的影響，從而獲得公平的性能.測(cè)試結(jié)果通過(guò)Ext4上的性能數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化以方便對(duì)比.

4.2 HDD上的性能對(duì)比

本節(jié)對(duì)比了HDD上采用不同文件系統(tǒng)后端時(shí)RocksDB在典型負(fù)載下的性能，結(jié)果如圖9所示:

如圖9所示，對(duì)于KV數(shù)據(jù)的寫入(即fillseq和fillrandom)或者更新(即updaterandom和overwrite)負(fù)載，RocksFS的性能遠(yuǎn)高于其他文件系統(tǒng)，特別是對(duì)于小塊的KV數(shù)據(jù).例如，當(dāng)value大小為16 B時(shí)，RocksFS的寫入和更新性能比Ext4高5倍以上，比BlueFS高約1倍.主要原因是RocksFS通過(guò)優(yōu)化WAL存儲(chǔ)結(jié)構(gòu)以及寫入流程，大幅減小了日志開銷，從而提升了KV數(shù)據(jù)的寫入和更新性能.相反，通用的文件系統(tǒng)無(wú)法減少WAL文件更新引入的日志開銷以及其他不必要的文件系統(tǒng)開銷.而BlueFS雖然通過(guò)去除不必要的文件系統(tǒng)功能，減少了額外的文件系統(tǒng)開銷，同時(shí)提高了文件讀寫的順序性，但是日志開銷仍然很嚴(yán)重.因此，在BlueFS上，RocksDB的小塊KV寫入和更新性能比通用文件系統(tǒng)高，但是比RocksFS低.

Fig. 10 Performance comparison on SSD圖10 SSD上的性能對(duì)比

至于讀取性能，RocksFS和BlueFS通常略低于通用文件系統(tǒng).具體來(lái)說(shuō)，在順序讀取KV數(shù)據(jù)(即readseq)的負(fù)載下，RocksFS的性能基本與通用文件系統(tǒng)持平(差距小于10%)，而BlueFS的性能最多比通用文件系統(tǒng)低20%.主要原因是在順序讀取KV數(shù)據(jù)時(shí)，RocksDB中的memtable緩存的效果較好，大部分的KV數(shù)據(jù)可以在緩存中命中.因此雖然RocksFS以及BlueFS沒(méi)有文件系統(tǒng)緩存，但是順序讀取KV數(shù)據(jù)的性能與通用文件系統(tǒng)相比差距較小，特別是在value較小(如value小于1 KB時(shí))的情況下.在隨機(jī)讀取KV數(shù)據(jù)(即readrandom)的負(fù)載下，RocksFS與BlueFS的小塊KV(如value小于1 KB時(shí))隨機(jī)讀取性能基本與通用文件系統(tǒng)持平，而大塊KV隨機(jī)讀取性能則低于通用文件系統(tǒng)(不超過(guò)50%).主要是因?yàn)镽ocksDB中設(shè)置的memtable緩存有限，因此value越小，能夠緩存到的數(shù)據(jù)項(xiàng)越多，讀取操作的緩存命中率越高.當(dāng)KV數(shù)據(jù)塊較大(如value大于1 KB)時(shí)，內(nèi)存中的memtable不足以容納大量的KV數(shù)據(jù)項(xiàng)，降低了緩存命中率.但是通用文件系統(tǒng)依然可通過(guò)文件系統(tǒng)緩存來(lái)提升讀取性能，而RocksFS以及BlueFS采用直接I/O操作塊設(shè)備，在文件系統(tǒng)級(jí)別上沒(méi)有緩存機(jī)制，因此隨機(jī)讀取性能有所降低.

總之，與傳統(tǒng)文件系統(tǒng)相比，RocksFS能夠大幅提高RocksDB在HDD上的寫性能，并保持小塊KV數(shù)據(jù)的讀性能基本不受損失，但是大塊KV數(shù)據(jù)的讀性能有所降低.

4.3 SSD上的性能對(duì)比

本節(jié)對(duì)比了SSD上采用不同文件系統(tǒng)后端時(shí)RocksDB在典型負(fù)載下的性能，圖10展示了性能對(duì)比結(jié)果.每輪測(cè)試之前將整個(gè)SSD擦除以避免垃圾回收操作對(duì)后一輪測(cè)試造成的干擾.性能對(duì)比的總體結(jié)果與HDD上的結(jié)果類似.

如圖10所示，RocksFS的數(shù)據(jù)寫入(即fillseq和fillrandom)和更新(即updaterandom和overwrite)性能遠(yuǎn)高于其他文件系統(tǒng)，尤其是在KV數(shù)據(jù)塊較小的場(chǎng)景下.例如當(dāng)執(zhí)行隨機(jī)更新KV數(shù)據(jù)的負(fù)載(即updaterandom)且value為16 B時(shí)，RocksFS的性能可達(dá)其他文件系統(tǒng)的8倍.而BlueFS在寫性能方面幾乎沒(méi)有提升.這主要是因?yàn)镾SD上的隨機(jī)I/O操作的性能與順序I/O操作的性能差異很小，因此寫入和更新性能的高低主要取決于日志負(fù)載的大小，而BlueFS無(wú)法減小日志負(fù)載，因此難以有效提升寫入和更新性能.

至于SSD上的讀取(即readseq和readrandom)性能，在value比較小(例如小于1 KB)時(shí)，RocksFS和BlueFS的讀取性能與通用文件系統(tǒng)基本持平；而當(dāng)value比較大(達(dá)到1 KB以上)時(shí)，RocksFS和BlueFS的讀取性能低于(最低約50%)通用文件系統(tǒng).這主要因?yàn)閭鹘y(tǒng)文件系統(tǒng)的文件系統(tǒng)緩存機(jī)制有助于提高讀取性能，而BlueFS和RocksFS利用直接I/O讀寫數(shù)據(jù)，因而沒(méi)有文件系統(tǒng)緩存機(jī)制，且RocksDB的memtable緩存有限，無(wú)法緩存大量的大塊KV數(shù)據(jù)項(xiàng)，因此memtable的緩存命中率較低，降低了讀性能.

總之，在SSD上，RocksFS作為RocksDB的后端文件系統(tǒng)的寫入和更新性能也遠(yuǎn)高于BlueFS以及Ext4等通用文件系統(tǒng)，讀性能基本與通用文件系統(tǒng)持平，大塊KV數(shù)據(jù)的讀性能有所降低.因此，RocksFS非常適用于插入密集型的工作負(fù)載，特別是小塊的KV數(shù)據(jù)操作.

5 結(jié)果與討論

KV存儲(chǔ)已經(jīng)成為大數(shù)據(jù)系統(tǒng)中的關(guān)鍵組件，其中基于LSM樹的KV存儲(chǔ)系統(tǒng)獲得了廣泛的應(yīng)用.針對(duì)這些KV存儲(chǔ)系統(tǒng)中的文件系統(tǒng)開銷以及日志開銷引入的性能下降問(wèn)題，本文提出了RocksFS，一個(gè)針對(duì)LSM樹優(yōu)化的文件系統(tǒng)，去除通用文件系統(tǒng)中不必要的開銷，并優(yōu)化日志存儲(chǔ)結(jié)構(gòu)和更新流程以減少日志開銷，從而提高數(shù)據(jù)寫入和更新性能.實(shí)驗(yàn)結(jié)果表明，與通用文件系統(tǒng)相比，RocksFS可以將RocksDB的小塊KV寫入和更新性能提高8倍左右，同時(shí)保證讀性能基本不受損失.

對(duì)于基于LSM樹的KV存儲(chǔ)系統(tǒng)，數(shù)據(jù)壓縮負(fù)載也是一個(gè)重要的問(wèn)題，一些現(xiàn)有的研究試圖通過(guò)提高壓縮操作的性能加快存儲(chǔ)系統(tǒng)的寫操作.這些工作與本文是互補(bǔ)的，未來(lái)的研究工作可嘗試將這2種方法結(jié)合起來(lái)以進(jìn)一步提高KV存儲(chǔ)系統(tǒng)的性能.