分布式存儲系統中的數據高效緩存方法

楊青霖，吳桂勇，張廣艷

清華大學計算機科學與技術系，北京 100084

1 引言

分布式存儲系統是由多個存儲設備或者服務器（統稱為節點）通過I/O總線或者互聯網絡連接而成的，并通過節點間的數據分散布局實現高效、低廉的數據存儲。分布式存儲系統因其強大的橫向擴展能力在大數據場景中得到廣泛應用[1]。然而，以Ceph為代表的分布式存儲系統存在以下幾個問題。

● 寫放大。為了支持寫事務，需要將數據先寫入日志，然后再應用到本地文件系統中，這導致了雙倍的數據寫入量，降低了寫入性能，且后端文件系統的寫入容易成為性能瓶頸。

● I/O路徑過長，響應時延較高。一個完整的I/O過程需要經過多種相關線程和模塊協同，部分模塊之間還需要進行網絡傳輸或內存復制，且過程中存在多處排隊等待，這些排隊等待有可能阻塞讀寫請求，過長的I/O路徑增大了讀寫操作的響應時延，降低了存儲系統的讀寫性能。

現有技術中普遍將內存或固態硬盤（solid state disk，SSD）等快速設備作為底層存儲系統的緩存，利用數據分層機制提高存儲系統的讀寫性能，如Memcache分布式緩存系統、Flashcache混合磁盤技術，或者在磁盤陣列上層支持SSD客戶端緩存等。因此，為了解決分布式存儲系統中的性能問題，在以磁盤為介質的存儲系統中引入以固態硬盤為介質的緩存是一種可行的途徑。

對于單機系統中的SSD緩存技術，現有的研究和應用已經比較成熟。但是，運行在分布式存儲系統上的大規模任務通常會被分割為許多小任務分散執行，這就導致數據訪問模式呈現弱局部性，若采用傳統的緩存機制，容易造成緩存污染的問題。另外，由于分布式場景下緩存管理的粒度通常較大，對數據塊的緩存操作需要大量的網絡帶寬和磁盤讀寫開銷，在傳統的緩存機制中，緩存操作會落在I/O的關鍵路徑上，增大I/O請求的響應時延。由于容錯需要，緩存層和存儲層還需要做數據冗余，導致數據緩存和臟數據回刷的開銷更大。因此，在分布式場景下，傳統的緩存機制并不完全適用，不能發揮SSD等快速設備的優秀特性，不能充分提升分布式存儲系統的讀寫性能。

本文提出一種分布式存儲系統中數據高效緩存方法——基于熱點檢測（hot spot detection，HOSD）的緩存方法，該方法通過充分利用分布式系統訪問模式信息來提高緩存池中數據的命中率，最終提高緩存系統的讀寫性能。首先，HOSD采用讀寫旁路和懶惰緩存的方法降低了緩存操作對I/O時延的影響，且避免了緩存污染；其次，HOSD采用高效的緩存管理機制及緩存替換策略降低了緩存管理開銷，提高了對緩存中冷數據的識別精度，使得更多的熱數據得以保留在緩存中，提高了緩存效率和分布式場景下弱局部性訪問的I/O性能；最后，HOSD通過跟蹤前臺工作負載的變化情況自適應地調整主動回刷臟數據的速率，以避免在發生緩存替換時密集回刷數據對系統I/O性能造成很大影響。

2 系統架構設計

HOSD的基本思想是冷熱數據分離，用相對快速的固態存儲設備組成一個熱數據緩存池，后端用相對慢速的磁盤設備組建冷數據存儲池（如圖1所示）。HOSD在分布式存儲系統內部支持數據緩存，數據在緩存池與存儲池之間的遷移由HOSD軟件模塊控制，這個過程對客戶端透明，因此無須在提供塊接口、文件接口或對象接口的客戶端上進行改動。

圖1 緩存方法的軟件邏輯架構

HOSD主要包括以下軟件模塊（如圖2所示）。

● Objecter模塊：屬于客戶端，負責將讀寫請求路由到緩存池或存儲池。

● Filter模塊：根據數據的訪問熱度，判斷是否將數據調入緩存池。

● Promotion模塊：負責將存儲池中的數據調入緩存池。

● Agent模塊：負責將臟數據適時回刷到存儲池，或者將冷數據從緩存池中剔除出去。

分布式存儲系統中數據緩存方法HOSD的工作流程如下。當客戶端要讀寫的數據在緩存池命中時，則直接在緩存池進行讀寫，不會訪問相對慢速的存儲池。若未命中，則旁路讀寫請求，將請求轉發給存儲池，讓客戶端在存儲池中進行讀寫。另外，由Filter模塊負責熱數據發現，判斷該數據是否被頻繁訪問，若是，則由Promotion模塊將數據遷移到緩存池；否則，該數據進入緩存候選狀態，暫不調入緩存池。當緩存池的占用率達到一定閾值時，Agent模塊負責將臟數據回刷到存儲池，或者將冷數據剔除出緩存池。

圖2 緩存方法的軟件模塊設計

由上述HOSD緩存方法的工作流程可以看出，其緩存管理主要涉及3種數據交換操作，分別如下。

● 調入緩存池：客戶端讀寫時，依據HOSD調入算法將數據從存儲池遷移到緩存池中。

● 臟數據回刷：對于寫入緩存池中的數據，經過一定的時間，HOSD Agent模塊會將這部分數據回刷到存儲池中，以免緩存池中臟數據過多。

● 冷數據替換：在緩存池裝滿的情況下，HOSD Agent模塊會將緩存池中的一些數據塊剔除出去，讓新的數據可以調入進來。

上述數據交換操作會帶來大量存儲和網絡開銷，因此希望通過設計高效的緩存機制來提高緩存效率，并減少這種數據流動開銷。

3 分布式存儲系統緩存方法

本文提出的分布式存儲系統中數據高效緩存方法HOSD主要包括如下3個技術點：

● 通過讀寫旁路和懶惰緩存相結合的方法，避免緩存操作落在I/O路徑上，增大I/O請求的響應時延，且通過熱點數據發現的方法來選擇性地將數據調入緩存，提高緩存中的數據質量，避免緩存污染；

● 通過高效的緩存管理機制，減少緩存管理操作帶來的額外磁盤訪問和計算開銷，并采用兼顧最近訪問時間和歷史訪問頻率的緩存替換策略來提高替換操作的準確性，使得更多的熱數據得以保留在緩存中，提高數據訪問的緩存命中率；

● 通過跟蹤前臺工作負載的輕重程度，自適應地調整主動回刷臟數據的速率，減少緩存替換時的臟數據回刷，并減輕數據回刷操作對系統讀寫性能的影響。

前兩個技術點保證了緩沖池中的數據質量，提高了緩存命中率和系統讀寫性能；第三個技術點保證了緩存方法能夠盡可能地使用富余的網絡和磁盤帶寬來管理緩存，降低緩存管理操作對系統性能的影響。

3.1 讀寫旁路與懶惰緩存

傳統的緩存機制采用按需調入策略，即一旦發現緩存缺失，就將對應的數據調入緩存，再響應客戶端的讀寫請求。這樣做，一方面會使緩存操作落到I/O路徑上，增加I/O時延；另一方面，該數據塊可能只是被偶發性地訪問，后續不會被頻繁地訪問，那么，將該數據塊調入緩存就會造成緩存污染，且帶來大量開銷，還會導致一些原本在緩存中較熱的數據塊被替換出去。因此，HOSD緩存方法采用讀寫旁路和懶惰緩存相結合的方法來解決上述問題，從而保證緩存池中的數據質量。

HOSD處理讀寫請求的主要流程如圖3所示，當一個I/O請求達到時，如果對應數據塊在緩存池中，則由緩存池直接響應用戶請求；如果對應數據塊不在緩沖池中，則HOSD會將該請求轉發給存儲池，筆者把這種處理請求的方式叫作讀寫旁路。對于緩存缺失的數據塊，HOSD采用懶惰緩存策略。具體來講，就是預先定義一個數據重用距離和緩存閾值，當該數據塊在重用距離內被訪問的次數超過了設定的緩存閾值時，將其調入緩存。另外，數據重用距離也可以根據緩存的命中情況來動態調整。

通過讀寫旁路和懶惰緩存的方法，HOSD讓緩存操作異步進行，避免了緩存操作對I/O時延的影響，同時減少了緩存池和存儲池之間的數據流動開銷。事實上，按需的緩存調入策略相當于緩存閾值為1的特例，HOSD通過增大遷移閾值來延緩對數據塊的緩存，最終提高緩存池中數據塊的命中潛力。

3.2 高效的緩存管理機制和替換策略

HOSD緩存管理機制的工作流程如圖4所示，通過在內存中維護一個將訪問熱度作為優先級的序列來對緩存池中的數據進行排列，當緩存的占用率達到一定的閾值時，通過緩存替換，將訪問熱度較低的數據塊從緩存池中剔除出去。同時，當發生讀寫請求時，需要對數據塊序列進行更新，為了避免這部分開銷對I/O時延造成影響，需要對緩存中的數據做邏輯劃分，也就是在內存中維護多個緩存序列，以此來減小鎖粒度，降低緩存管理帶來的額外開銷。

緩存信息維護在內存中，如果發生節點故障，會造成緩存信息的丟失。因此，HOSD周期性地將緩存信息打包成一個對象，通過存儲系統現成的寫入邏輯，將緩存信息以檢查點的形式持久化到存儲系統中。對于檢查點之間丟失的緩存信息，HOSD也可以通過存儲系統的變更操作的日志信息將其重建出來。通過上述方法，保證HOSD緩存方法在節點故障的情況下仍能正常工作，保證了存儲系統的容錯能力。

當進行緩存替換時，需要選擇訪問熱度最低的數據塊，將其從緩存中剔除，以便為即將調入緩存中的數據塊騰出空間。HOSD緩存方法采用基于訪問歷史的替換策略，綜合考慮數據塊的歷史訪問頻率和最近訪問時間，并構造了兩級緩存，一級緩存完整的數據，另一級僅緩存元數據，避免了由緩存量不足導致的緩存預測不準確的問題，保證了從緩沖池中替換出去的數據塊都具有較低的命中潛力。

圖3 HOSD 緩存方法讀寫流程

圖4 HOSD 緩存管理機制工作流程

圖5 HOSD 緩存方法替換策略

HOSD緩存替換策略的主要數據結構由4個鏈表構成（如圖5所示）：MRU（most recently used）鏈表、MFU（most frequently used）鏈表、MRUG（MRU ghost）鏈表、MFUG（MFU ghost）鏈表。其核心思想如下。

● 當數據塊進入緩存時，HOSD先將數據放入MRU鏈表中。MRU鏈表是依據數據塊的訪問時間進行排序的一個有限序列。當一個新的數據塊進入MRU鏈表時，隊列LRU（least recently used）端的數據塊將被替換出去。如果MRU鏈表中的某個數據塊在被替換之前被二次訪問，那么將該數據塊放入MFU鏈表中的MFU端。MFU鏈表也是依據數據塊的訪問時間進行排序的一個有限序列。不同的是，每發生一次二次命中，都是把MFU鏈表中的對應數據塊放到MFU鏈表頭部。

● 如果有數據需要進入緩存中，而此時緩存中的數據塊數目已經到了設定的閾值，HOSD會從LRU和LFU（least frequently used）端刪除元素，并將對應的元數據信息送入ghost鏈表中，即MFUG鏈表和MRUG鏈表。MFUG鏈表和MRUG鏈表不存儲數據，只存儲數據塊的訪問記錄。將MFU鏈表的數據送入MFUG鏈表中，同時釋放該數據塊在MFU鏈表中占用的存儲空間；如果釋放的數據塊在MRU鏈表中，那么將該元素從中刪除，并送入MRUG鏈表中。

● 當再次訪問該數據塊時，數據如果在MRUG鏈表或者MFUG鏈表中，那么從存儲池讀取該元素，并重新將其插入MRU鏈表或MFU鏈表中。HOSD會根據MRUG鏈表或者MFUG鏈表中發生偽命中次數的多少，動態地調整MRU或MFU兩個鏈表應包含的元素的個數。

HOSD緩存替換策略在傳統算法上構造了一層元數據緩存，能夠較快地讀取剛被替換的緩存，并兼顧數據塊的最近訪問時間和歷史訪問頻率信息，可以準確識別出緩存中訪問熱度較低的數據塊，將其替換出緩存池，從而保證緩存中的數據塊都具有較高的命中潛力。此外，在真實系統中實現的HOSD緩存策略支持多線程訪問。

3.3 自適應的主動回刷機制

分布式存儲系統中的數據回刷操作和前臺應用會競爭系統中的I/O、網絡和CPU等資源。為了減小對前臺性能的影響，HOSD采用主動回刷的策略，并根據應用負載自適應地調整回刷速率。目標包括兩個方面：一是讓系統將緩存池中的臟數據盡快回刷到存儲池，二是減少回刷操作過程對前臺應用的影響。

當緩存中的數據量達到一定的閾值時，HOSD周期性地主動將緩存中較冷的臟數據回刷到存儲池，而不是等到替換發生時再回刷。自適應的主動回刷機制需要跟蹤系統中的應用負載，進而動態調整數據回刷的速率，實現回刷操作快速完成，并對前臺應用性能影響較小。

在回刷速率控制方面，HOSD采用一個開/關邏輯閥來進行調控（如圖6所示）。是否在下一時間周期內執行數據回刷操作取決于當前時間周期內負載的輕重。如果當前時間周期內負載較輕，則下一時間周期執行數據回刷操作；反之，下一周期不執行數據回刷操作。也就是說，利用當前周期內的負載來近似估算下一周期的負載，因此時間周期不能設置得太長。

4 性能測試

4.1 測試環境及方法

HOSD是基于Ceph 0.94.2開發的緩存管理系統，為了測試HOSD原型系統的性能，本文構建了一個分布式存儲系統。其中，存儲服務器通過專用的高速存儲網絡連接起來。每臺機器都有一定數量的硬盤驅動器（hard disk drive，HDD）用于構建存儲池，以及一定數量的固態硬盤用于構建緩存池。

實驗所用的測試環境描述如下：實驗過程中共使用了3臺機器，每臺機器配有2個E5-2609V2 CPU、4個 DDR3 RECC 8 GB內存、6塊ST2000NM0033 2T SASA磁盤、2塊Intel S3500 480 GB固態硬盤、一塊Intel S3500 120 GB固態硬盤、一塊LSI 9260-8IRAID卡以及一塊Intel X520-SR2萬兆網卡，每臺機器均安裝了Redhat 7.0操作系統。這些機器通過萬兆光纖交換機連接起來，形成一個高速集群存儲系統。

通過對比HOSD和Ceph自帶的分布式緩存系統Cache Tiering的性能，評價HOSD的性能。通過播放有代表性的讀寫請求trace，收集系統的每秒輸入輸出量（input/output per second，IOPS）和讀寫帶寬等數據。實驗采用典型的I/O測試工具FIO（flexible I/O tester）生成有代表性的工作負載。FIO能生成具有不同特征的工作負載，特征參數包括讀寫比例、傳輸請求大小和同時發出請求的最大數目等。

4.2 測試結果

4.2.1 人工負載下的性能

第一組實驗使用FIO默認的均衡隨機負載進行測試。實驗中磁盤存儲池大小為200 GB，SSD緩存池大小為40 GB，Ceph對象大小設置為1 MB，FIO播放負載所用的iodepth參數值設為128。分別將請求大小參數設置為4 KB、1 MB和4 MB，分別測試Cache Tiering和HOSD的IOPS及讀寫帶寬。

圖6 HOSD 緩存臟數據回刷控制機制

圖7 FIO 隨機負載下的I/O 性能

圖7統計了每種情況下HOSD相對于Cache Tiering的加速比，加速比在2.52和5.96之間波動。為了統計HOSD的平均加速效果，筆者計算了各個加速比的幾何平均值，以減小極端數據對平均值的影響。可以得到，HOSD帶來高達3.48的平均加速比。因此，相對于Cache Tiering，HOSD帶來了明顯的性能提高。這種性能提升的原因是：Cache Tiering將大量冷數據調入緩存，既占用了緩存空間，又增加了系統的I/O開銷；HOSD則通過懶惰緩存的方法，保證了緩沖池中的數據具有較高的命中率，并通過自適應的主動回刷機制，保證了分布式緩存系統具有較低的維護開銷。

4.2.2 真實負載下的性能

為了在真實的磁盤I/O 負載下比較Cache Tiering和HOSD的性能，第二組實驗使用FIO同時播放多個trace進行測試。實驗中磁盤存儲池大小為100 GB，SSD緩存池大小為8 GB，Ceph對象大小設置為1 MB，FIO播放負載所用的iodepth參數值設為64。同時播放的trace包括prxy_1、wdev_0、prxy_0、webmail和hm_0，分別測試Cache Tiering和HOSD的IOPS。

表1統計了第二組實驗中每種情況下HOSD相對于Cache Tiering的加速比，加速比在1.01和1.13之間波動。為了統計HOSD的平均加速效果，筆者計算了各個加速比的幾何平均值。可以看出，HOSD帶來高達1.08的平均加速比。因此，相對于Cache Tiering，HOSD帶來了一定的性能提高。

第二組實驗的平均加速比相對第一組實驗明顯下降，原因分析如下：筆者統計了實驗所用的5個I/O trace，發現每個trace的訪問都局限在一個較小的地址空間。這樣帶來的結果是無論使用Cache Tiering還是HOSD，絕大多數I/O請求會在SSD緩存區命中。在命中的情況下，二者性能幾乎沒有差距。不同的是，HOSD維護緩存區中數據的數據交換操作成本要比Cache Tiering低一些，且對訪問時間序列的維護更加精確，因此帶來了8%的性能提高。

表1 播放真實trace 負載下的I/O 性能

5 相關工作

隨著閃存的日益普及，無論是工程師還是研究人員，都對將其集成到存儲棧中表現出較大興趣。硬盤制造商支持混合磁盤已有多年。主流操作系統上也已經有如ReadyBoost和bcache的軟件實現。Facebook將固態盤作為數據中心磁盤進行高速緩存。Solaris ZFS支持使用固態盤作為二級緩存[2]。NetApp公司也使用固態硬盤來加速存儲系統[3]。

早期的一些研究主要關注如何改進基于閃存的高速緩存。Kgil T等人[4]提出將閃存作為內存擴展或磁盤緩存來減少功耗。他們采用能夠改變糾錯碼（error correction code，ECC）強度和閃存芯片單元存儲密度的可編程閃存控制器，能夠在保證性能犧牲不到5%的情況下延長閃存使用壽命。Mesnier M P等人[5]利用從文件系統和數據庫管理系統獲得的語義信息改進基于SSD的磁盤緩存，通過對元數據塊和小文件賦予更高的優先級，能夠獲得比不考慮語義的緩存算法更好的性能。Pritchett T等人[6]將SSD作為多個服務器的全局高速緩存，以便最大化它的利用率。他們用更少的SSD設備獲得更高的命中率，比為每個服務器單獨配置緩存更加高效。同時他們還通過懶惰緩存機制來延長SSD設備的壽命。

近期的研究工作[7]利用內部垃圾回收行為提高了固態硬盤的緩存性能。垃圾回收操作對SSD的性能和壽命有較大的影響。研究人員將SSD分為3個區域（未使用區域、讀區域和寫區域），動態調整這些區域的大小，在提高命中率的同時，減少了擦除操作次數。同時，SSD也可以作為數據庫管理系統的擴展緩沖池。參考文獻[8]提出了基于訪問頻率的替換策略——溫度感知緩存（temperature-aware caching，TAC）。參考文獻[9]在Microsoft SQL Server上實現了一個專用模型，作者還評估了3個不同的將臟頁替換出內存緩存池的策略。

除了緩存，存儲分層[10-12]是另一個熱門的混合存儲技術。一個分層存儲系統會動態選擇熱門的數據子集，并將它們移動到速度更快但容量較小的設備上。這項技術被廣泛應用于企業級存儲陣列，以滿足大容量、高性能與低成本的需求。一個典型例子是，蘋果公司通過Fusion Drive推出了消費級分層存儲產品。

緩存和分層存儲都屬于分級存儲。作為替代，橫向混合存儲系統使用SSD存儲數據的特定部分，以更好地利用SSD和HDD。這種體系結構背后的想法是一個塊的訪問模式取決于它存儲了什么樣的數據。例如，元數據占用的存儲空間極小，但是其訪問頻率較高[13]。因此，將它們固定存儲在SSD中可以提高總體性能，同時避免了來回移動數據塊的開銷。這種架構的例子包括ChunkStash[14]和I-CASH[15]。Wang S C等人[16]發現了HDD讀寫性能的波動性，從而設計了調度器，在HDD和SSD的混合存儲中根據HDD的波動情況將I/O調度至HDD或者SSD，在節省SSD存儲空間的同時，降低了尾部時延。

Liu Z X等人[17]指出，在大規模分布式存儲系統中，負載均衡是影響服務等級目標（service-level objective，SLO）的關鍵因素，而一個快速的緩存可以保證負載均衡。由此設計了一個兩層的緩存系統DistCache，通過兩個不同的哈希函數將熱數據分散在不同的緩存層，從而提升緩存性能。Zhang Y等人[18]通過記錄存儲集群中各節點的緩存命中情況來動態調整集群中的緩存分配情況，從而提升總體緩存命中率，減少與底層存儲系統的數據交換總量。Berger D S等人[19]針對用戶的網絡服務存在的長尾時延問題，提出了RobinHood方法，該方法可以動態地將緩存從富余的地方分配至緊張的地方，有效地降低了尾部時延。在糾刪碼被越來越多地應用于現代存儲集群中的情況下，Luo T Q等人[20]提出了使用編碼緩存來減少峰值數據傳輸量的方法。

6 結束語

本文提出了一種分布式存儲系統中數據高效緩存方法HOSD，采用讀寫旁路和懶惰緩存的辦法，降低了緩存操作對I/O時延的影響，并減少了對冷數據的緩存，避免了緩存污染情況的發生。同時，采用高效的緩存管理機制降低了緩存管理對存儲系統讀寫性能的影響，并通過兼顧最近訪問時間和歷史訪問頻率的緩存替換策略，提高了對緩存中冷數據的識別精度，使得更多的熱數據得以保留在緩存中，提高了緩存的效率和分布式場景下弱局部性訪問的I/O性能。另外，通過跟蹤應用負載輕重而自適應地主動回刷臟數據，減輕了數據回刷操作對系統性能的影響。最后，通過定期對內存中維護的緩存信息進行持久化來保證存儲系統和緩存方法的容錯能力。實驗表明，相對于Ceph自帶的Cache Tiering緩存系統，本文所提分布式緩存方法HOSD實現了3.48的平均加速比，帶來了明顯的性能提升。未來，將進一步探索本文提出的緩存策略在大規模存儲集群及糾刪碼存儲系統中的應用。