一種可動態配置的分布式內存池緩存一致性機制

段卓輝 劉海坤 趙金瑋 劉一航 廖小飛 金 海

（大數據技術與系統國家地方聯合工程研究中心（華中科技大學） 武漢 430074）

（服務計算技術與系統教育部重點實驗室（華中科技大學） 武漢 430074）

（集群與網格計算湖北省重點實驗室（華中科技大學）武漢 430074）

（華中科技大學計算機科學與技術學院 武漢 430074）

（zhduan@hust.edu.cn）

隨著大數據、云計算、人工智能等技術的不斷發展，計算機需要存儲和處理的數據呈指數級增長.傳統的單機節點已經無法滿足這些應用對計算資源和存儲資源的需求，分布式內存系統成為解決擴展性問題的一個有效途徑[1].隨著新型非易失性存儲器（non-volatile memory,NVM）[2-3]和遠程直接內存訪問（remote direct memory access,RDMA）技術在數據中心的廣泛應用，為分布式內存系統的設計帶來了新的契機.基于NVM/DRAM（dynamic random access memory）異構內存和RDMA 技術的分布式內存系統已成為國際研究的熱點[4-6].

為了提高分布式內存系統的性能，數據往往會被客戶端緩存以加速遠程讀寫操作，從而減輕服務器端的訪存壓力[7].然而，緩存機制的引入也會帶來分布式系統中緩存不一致的問題[8].當一個客戶端緩存了共享的存儲對象后，另一個客戶端執行對該共享存儲對象的更新操作就會導致緩存不一致的問題.因此，在分布式環境中，當存儲對象的源節點更新時，需要確保緩存的副本也被更新.然而，保證緩存一致性往往帶來較大的性能開銷.分布式系統不僅需要同步節點之間的緩存副本[9]，還需要降低確保緩存一致性所帶來的開銷，否則使用緩存帶來的性能提升將會被抵消.

新興的RDMA 技術使得遠端內存的高速訪問成為可能.在高速Infiniband（IB）網絡下，遠端節點的讀寫延遲能接近本地讀寫延遲[10].直接通過網絡進行遠程讀寫操作是解決緩存一致性開銷問題的一種直接方法[7].

表1 展示了本地DRAM 和RDMA 訪問遠端的性能對比.QDR,FDR,EDR 和HDR 是不同規格的IB 網絡.即使使用了RDMA 技術，通常情況下遠程讀寫的延遲仍然比直接讀寫本地DRAM 要高[8].因此，分布式系統不能簡單地舍棄客戶端緩存，設計和實現緩存一致性機制在分布式異構內存系統中仍然至關重要.由于確保緩存一致性必然會帶來一定的開銷，因此高效的分布式緩存一致性算法必須權衡緩存帶來的性能提升和確保緩存一致性所帶來的開銷，以達到系統在保證緩存一致性的前提下，依然能夠比無客戶端緩存的情況下獲得更高的性能.

Table 1 Performance Comparison of Local DRAM and RDMA表1 本地DRAM 和RDMA 性能對比

傳統的緩存一致性解決方案有3 種不同的方法.首先，基于時間戳的租約機制[11]是一種常用的保證共享對象并發訪問一致性的方法.該機制在租約期內授予緩存數據的客戶端對相應數據的讀寫權力.基于租約的緩存一致性機制需要考慮許多使用問題，例如時間參數的平衡問題[12].分布式系統應該慎重考慮頒發的租約時間長短.如果租約時間過長，會影響系統同步的效率，使其他節點等待時間過長；相反，如果租約時間過短，往往需要頻繁進行續約，增加續約的通信開銷，導致整體分布式系統效率降低.此外，時鐘同步也是需要考慮的因素[13].由于，不同節點的時間可能存在誤差，基于租約的一致性機制就會出現問題.另外，還需要考慮單節點故障問題.租約機制依賴于某個服務器節點頒發的租約時間戳，如果該節點出現故障，將會影響整個系統的使用，導致系統故障.

其次，基于目錄的緩存一致性保證機制多用于數據更新比較頻繁的場景[14].該機制需要維護一個全局公共目錄，目錄中保存了緩存的元數據信息，包括緩存是否為臟數據等.當客戶端讀取數據時，需要查詢相應節點的目錄以確定緩存的狀態，從而獲取緩存是否可用的信息.當某個客戶端節點更新數據時，需要更新緩存的目錄狀態，以供其他節點查詢.基于目錄的緩存一致性保證機制也存在一些問題.一方面，目錄的維護需要額外的存儲空間，增加了存儲開銷；另一方面，對于讀取數據的節點來說，每次操作都需要查詢遠端目錄來確定緩存狀態，增加了時間開銷，降低了系統效率[15].

最后，基于廣播方式實現的緩存一致性保證機制多用于數據讀操作多、更新不頻繁的場景[16].在RDMA 通信環境下，這種機制面臨著新的挑戰.當一個客戶端節點需要更新數據時，需要向其他共享節點廣播相應的信息.當其他節點監聽到更新信息后，將當前緩存數據標記為不可用，并在后續階段進行刷新.基于廣播方式的一致性保證機制具有較高的效率.當某個客戶端需要讀取數據時，在緩存中存在此數據的情況下，只需要進行本地緩存讀取即可.然而，在RDMA 網絡中，廣播通信是不可靠的，而在RDMA網絡中建立可靠的廣播機制成本較高，而且該廣播機制可能會造成比較嚴重的網絡擁塞問題[8].

綜上所述，傳統的緩存一致性保證機制各有利弊.在實際應用中，需要對這些方法進行改進和完善，并根據不同情況決定使用哪些緩存一致性保證機制.本文基于NVM 和RDMA 技術，試圖在分布式異構內存池中實現一種全新的緩存一致性保證機制，為大數據時代的分布式應用提供更高效的分布式內存系統.

本文面向分布式異構內存池系統，提出了一種目錄和廣播相結合的緩存一致性保證機制，并且可在運行時動態切換緩存一致性保證機制，以有效提升緩存一致性保證的效率.我們通過四象限矩陣分析方法對每個數據塊進行訪問模式的判定分析，并將其轉換為適合的緩存一致性保證策略，從而提高了數據同步效率和性能優勢.實驗結果表明，相對于使用單一基于目錄或基于廣播的緩存一致性保證機制，采用可動態轉換的緩存一致性保證機制的分布式異構內存池系統平均讀寫性能分別提升了32.31%和31.20%.此外，在客戶端數量不斷增加的情況下，可動態轉換的緩存一致性保證機制表現出良好的擴展性能.

1 國內外研究現狀

在分布式環境中，當多個客戶端共享同一存儲對象時，分布式系統往往采用租約、目錄或廣播等緩存一致性保證機制來確保客戶端的緩存副本與服務器的存儲數據版本保持一致.近年來，國內外對于緩存一致性保證機制的研究主要集中在對傳統機制的實現和改進上，同時也涌現出一些利用新型硬件或軟件加速緩存一致性機制的研究成果.

1）多核處理器的緩存一致性協議.在多核系統中，緩存一致性問題是普遍存在的.當多個緩存同時訪問同一塊數據時，讀寫操作可能導致緩存的不一致性，這個問題在現代多核處理器中尤為突出.為了提高CPU 對內存的訪問速度，多級緩存被引入到CPU 和內存之間.每個多核處理器的核心都有自己的緩存，當進行讀寫操作時就會引發緩存不一致性的問題.MESI（modified exclusive shared invalid）協議是一種廣泛使用的緩存一致性協議[17-19]，它將緩存狀態劃分為4 種，并通過讀寫事件相互轉換.在進行寫操作之前，必須獲得獨占權限，在進行讀操作之前至少要保證是共享狀態.MESI 協議本身是基于MSI 協議的發展而來，MSI 協議只有3 種狀態，缺少了獨占狀態E.此外，還有許多擴展的協議基于MESI，例如加入了O 狀態的MOESI 協議[20-21]，其中O 狀態表示所屬狀態，類似于E 狀態，但該狀態允許共享狀態為臟的緩存行而無需寫回內存.

多核系統中的緩存一致性協議MESI 本質上是一種基于監聽的協議，各個處理器除了要處理自己的緩存，還要監聽其它處理器的活動，這與分布式下基于廣播的協議的原理類似.在分布式異構內存池系統中，服務器在基于廣播的機制下也要監聽客戶端的緩存狀態.此外，MESI 協議對緩存的4 種狀態設計和觸發事件導致的狀態轉換對于分布式內存池中緩存狀態的設計也有一定的借鑒意義.

2）分布式系統的緩存一致性保證機制.在分布式存儲系統中，確保緩存一致性的機制旨在保持緩存副本與服務器中存儲的數據一致.因此，當對緩存數據或存儲數據進行更新時，必須確保這些修改被同步到緩存的共享節點.

基于時間的租賃機制通過服務器向客戶端頒發鎖來實現數據一致性保證，但面臨單節點故障和控制租約時間的參數問題.以色列研究人員提出了自適應租約[22]，采用優化的租約機制，對不同類型的數據對象采用不同的租約，從而減少了網絡延遲.為了解決單節點故障問題，來自加州大學洛杉磯分校的研究人員提出了Paxos 協議[23]，通過多輪投票確定數據的一致性節點.在此基礎上，微軟研究人員對Paxos進一步優化[24-25].來自國防科技大學的研究人員提出了DCC 協議[26]，結合了優化的Lease 和Fast-Paxos機制，通過Paxos 算法選舉主節點，解決了單節點故障問題，并引入同步組的概念，使組內節點可以直接訪問數據，并定義了確保數據最終一致性的數據寫回過程.麻省理工大學的研究人員提出了邏輯租約技術[19]，通過動態調整操作順序以減少沖突的發生，從而提升分布式共享并行系統的擴展性和性能.邏輯租約技術結合了物理上和邏輯上的時間，形成了一種新的時間方式，更加靈活高效.

對于基于目錄的機制來實現緩存一致性保證方案，系統需要維護一個全局目錄，并通常需要一個元數據服務器節點.來自新加坡國立大學的研究人員提出的GAM 系統采用目錄方式保持緩存一致性[6]，將數據節點分為home 節點、remote 節點、request 節點和sharing 節點、owner 節點5 種類型，緩存節點分為Shared、Unshared 和Dirty 這3 種類型.不同的讀寫操作會導致狀態之間的轉換，最終實現了系統的緩存一致性保證機制，并對該機制下的系統進行了擴展性、局部性和延遲等方面的測試.新加坡國立大學和微軟的研究人員合作提出的Pegasus 系統通過目錄方式保證緩存一致性[27]，利用可編程交換機來平衡存儲服務器之間的負載，改進了基于目錄的緩存一致性協議，僅在交換機數據平面中存儲和轉發元數據.以色列研究人員提出了COMBINE[28]，這是一種基于目錄的共享對象一致性協議，利用覆蓋樹數據結構，將系統節點作為覆蓋樹的葉子節點，將通過同一節點的請求合并在一起.COMBINE 利用覆蓋樹提高了最近鄰搜索的效率，并減少了競爭，將服務請求的成本與覆蓋樹中請求節點和服務節點之間的最短路徑成本關聯起來.

基于監聽廣播的緩存一致性保證機制是一種高效的機制.在這種機制下，某個節點的讀寫操作會被廣播給其他節點，不同節點中的緩存控制器會進行相同的處理操作，以確保在接收到相同廣播后不同節點處于相同的狀態，最終實現一致性[29].相比基于目錄的緩存一致性保證機制，基于廣播的機制不需要引入和維護目錄，更加簡單.此外，基于廣播的機制不需要像基于目錄的一致性保證機制那樣傳遞大量的控制消息.然而，在大規模系統中，基于廣播的機制在帶寬和延遲等性能方面通常較差，因此只適用于小規模的分布式系統.來自上海交通大學的研究人員在RDMA 網絡下實現了基于廣播的分布式共享內存[30]，對讀請求處理和寫請求處理進行了適應性設計和實現，并確保不同緩存控制器對讀寫請求的順序相對一致性，最終測試表明，與傳統分布式系統相比，其性能有顯著提升.

3）混合的緩存一致性保證機制.為了提高一致性保證機制的效率，現有研究采用了混合緩存一致性機制，該機制能夠進一步減小網絡開銷.克萊門森大學研究人員在其研究中提出了一種混合的緩存一致性保證機制[31]，其結合了更新傳播和失效策略.當對目標存儲資源進行讀寫訪問時，根據系統設計的策略，決定采用更新傳播或失效策略.類似地，印度學者[19]也提出了類似的算法，該策略結合了傳播和失效2 種策略以實現強一致性.對于寫更新操作，該算法首先執行寫的無效操作，然后在節點訪問該存儲資源之前更新緩存副本.這種策略顯著減少了存儲資源的訪問延遲.這些緩存一致性保證機制都是結合了更新傳播和失效策略，類似于直接廣播模式和緩存副本失效模式，以實現一致性.

上述機制都是在元數據服務器節點上進行的，當多個節點進行寫入時，會增加元數據服務器的負擔.因此，一些研究提出同時利用客戶端來確保存儲系統的數據一致性.例如，來自西南大學的研究人員提出了一種自適應的細粒度緩存更新策略[5]，將緩存一致性的更新操作移至客戶端節點，針對不同的存儲資源，該自適應策略結合應用的訪問行為，采用不同的緩存一致性更新策略.這種自適應的混合緩存一致性保證機制顯著降低了系統的存儲資源訪問延遲.另外，印度學者提出了一種基于自適應目錄的緩存一致性模型[32]，該模型能夠顯著優化分布式應用中的網絡帶寬.該工作在分層設計的分布式系統中實現了基于目錄的緩存一致性模型，并添加了自適應特性以優化該模型，實驗證明相比非自適應策略，自適應策略在性能上有很大改善和提升.

除了對傳統機制的實現和改進，還有研究利用新的硬件加速緩存一致性.例如，清華大學的研究人員提出的Concordia 系統利用可編程交換機加速緩存一致性協議[33].該系統的核心是FLOWCC，一種寫無效協議，該協議在交換機和服務器之間劃分一致性責任，通過序列化沖突請求并通過鎖定檢查轉發管道，并將它們多播到正確的緩存代理.

綜上所述，緩存一致性的保證機制本質上是通過各種方式通知緩存了相同數據副本的節點，以實現各節點的緩存數據一致性.目前對緩存一致性保證機制的研究主要集中在對傳統機制的適應性實現和改進，或者將多種機制混合以實現更好的緩存一致性保證機制，以降低系統的遠程訪問延遲.然而，緩存一致性協議的性能很大程度取決于協議與當前訪問模式和行為的匹配程度.對于整體系統的訪存行為的預測往往存在很大的不確定性，這就要求緩存一致性協議能夠靈活地根據當前系統狀態進行切換.傳統的緩存一致性協議不能很好地適配動態變化的應用需求，因此亟需一種可動態配置的緩存一致性保證機制來適配不同應用動態變化的訪存特征.

2 動態轉換的緩存一致性保證機制的設計

本文面向分布式異構內存池系統，設計并實現了可動態轉換的混合緩存一致性保證機制.首先，我們實現了分布式異構內存池的多客戶端共享機制和客戶端緩存機制.然后，設計并實現了可動態轉換的混合緩存一致性保證機制.該機制根據應用的不同讀寫訪問特征，提供相應的緩存一致性保證策略，以降低緩存一致性保證機制的開銷，提高使用客戶端緩存時的系統性能.分布式異構內存池系統的整體架構如圖1 所示，采用客戶端/服務器模型，為客戶端提供遠程內存資源.客戶端節點通過DRAM 實現了緩存模塊.客戶端維護緩存目錄條目，其中保存了每個緩存使用的緩存策略.服務器端同樣維護存儲對象的目錄條目，其中將每個客戶端的緩存信息作為一個節點串成鏈表.該系統架構為實現我們提出的混合緩存一致性保證機制奠定了基礎.系統主要分為3 個功能模塊，即分布式異構內存池中多客戶端共享讀寫機制、混合的緩存一致性保證機制以及緩存一致性保證策略的動態轉換機制，下面分別進行詳細介紹.

Fig.1 The system architecture of distributed heterogeneous memory pool圖1 分布式異構內存池系統架構

2.1 分布式異構內存池的多客戶端共享讀寫機制

分布式異構內存池中多客戶端共享讀寫機制的實現原理如圖2 所示.我們在服務器端維護一個哈希表，其中鍵為唯一值ID，值為內存資源的全局地址和內存注冊信息.為了實現多客戶端共享讀寫，我們為客戶端應用提供了函數接口.當客戶端調用接口申請遠端內存資源時，需要提供一個唯一的ID 值.服務器收到請求后，首先在哈希表中根據ID 值進行查找.如果沒有查找結果，則說明該請求是非共享的，即簡單的申請遠程內存資源.服務器會檢查自身的NVM 資源是否足夠分配，并將分配的內存注冊信息和生成的全局地址返回給客戶端.同時，服務器需要將該ID 作為鍵，將該內存資源的全局地址和內存注冊信息作為值插入到服務器端的哈希表中.如果根據ID 值查找到了結果，說明該請求是對已共享的遠程內存資源的訪問，此時無需進行新的NVM 內存資源分配，直接將查找到的內存資源的全局地址和內存注冊信息返回給客戶端即可.

Fig.2 The implementation principle of object sharing mechanism圖2 對象共享機制實現原理

當使用RDMA 單邊原語Read/Write 進行操作時，需要使用相應的內存注冊信息.當申請內存的時候，由于客戶端在初始節點就已經進行了內存的預申請和分配，客戶端的共享內存管理程序直接返回一個地址映射信息，并向在服務器節點端標記當前內存已被共享.因此，客戶端節點獲得同一個NVM 內存資源的內存注冊信息，從而實現多客戶端共享該遠程內存資源.由于共享接口的請求需要由客戶端發起，并需要服務器進行處理，因此設計中采用了RDMA雙邊原語Send/Recv 來進行通信.當內存資源不夠的時候，客戶端共享內存管理程序無法找到空余的地址映射表，直接返回OOM 錯誤，該內存申請請求由于超過系統內存容量而失敗.

此外，當多個客戶端對共享內存進行同時寫入操作時可能會出現并發問題.為了避免這種情況，服務器的目錄中增加了寫標志位.當有一個客戶端對共享內存進行寫入訪問時，將寫標志位置為真，從而阻止其他客戶端同時進行寫入操作，避免系統出現問題.

2.2 基于目錄和基于廣播的緩存一致性保證機制

為了滿足不同應用的訪問模式需求，我們采用了一種混合的緩存一致性保證機制.該機制依賴于服務器和客戶端中目錄信息的設計，并根據不同策略采取相應的讀寫處理方式.

當使用基于目錄實現的緩存一致性保證機制時，在讀取遠程客戶端數據時，首先要查詢目錄，并根據緩存是否臟決定是進行遠程讀取還是讀取緩存.在進行寫操作時，在數據寫入服務器后，需要更新服務器上相應緩存的臟標志位.當采用基于廣播實現的緩存一致性機制時，可以直接從客戶端的緩存讀取數據，而在進行寫操作時，寫入服務器后需要廣播通知其他客戶端更新緩存.我們實現了這2 種機制的混合應用，并且客戶端和服務器共同維護緩存一致性.

混合緩存一致性保證機制的實現依賴于分布式內存共享系統中服務器的目錄和客戶端的緩存設計.服務器端的目錄結構，其中每個目錄項包括唯一ID、NVM 內存注冊信息以及特殊的鏈表節點.鏈表節點記錄了緩存該內存對象的每個客戶端的信息，包括采用的緩存一致性保證機制、緩存臟位和緩存的DRAM 內存注冊信息.客戶端的緩存采用LRU 緩存策略實現，并使用雙向哈希鏈表進行管理.哈希表的鍵是全局唯一地址，其值包含緩存的DRAM 信息、緩存采用的一致性保證機制以及讀寫次數計數等信息.如果緩存被淘汰，客戶端需要向服務器發起請求以更新相應的目錄，因此我們采用RDMA Send/Recv進行設計.

我們實現了客戶端可調用的上層應用讀寫接口，通過這些接口實現了緩存一致性保證機制.首先，客戶端發起讀請求，該請求被封裝為讀工作請求并交由工作處理器處理.在識別為讀請求后，工作處理器將其交給專門的處理器處理.然后，客戶端根據LRU緩存策略判斷是否命中緩存.如果未命中，則進行普通的RDMA 讀操作，并將緩存目錄中的臟位設置為非臟.最后，增加讀計數并按照LRU 策略更新緩存.如果命中緩存，則判斷目錄中緩存采用的一致性保證策略.如果是廣播機制，則無需進行遠程讀取，直接讀取客戶端緩存即可；如果是目錄機制，則使用RDMA 雙邊原語發送查詢臟位的請求，并由服務器進行回應.當緩存非臟時，可以直接在本地客戶端緩存中讀取數據；當緩存為臟時，需要進行遠程RDMA讀取，并進行相應的后續處理.

對于需要修改共享內存的客戶端應用，可以調用寫接口.首先，客戶端發起寫請求，該請求被封裝為寫工作請求并交由工作處理器處理.在識別為寫請求后，工作處理器將其交給專門的處理器處理.然后，調用RDMA 寫操作進行遠程存儲資源的更新，客戶端發送請求刷新其他客戶端的緩存.當服務器收到刷新緩存的請求后，根據ID 找到相應的內存對象，根據不同的鏈表節點采取不同的措施，根據其緩存一致性保證策略進行處理.如果是廣播策略，服務器需要調用RDMA 寫操作更新緩存；如果是目錄策略，只需修改鏈表節點中的臟位.最后，客戶端在完成寫操作后，增加寫計數并利用LRU 策略更新緩存.

LRU 緩存更新算法是一種簡單且高效的緩存更新算法，每次將最新訪問的對象放在緩存雙鏈表的頭部，確保對象不被淘汰.在我們的系統中，由各個客戶端進行LRU 緩存更新.由于寫接口設計中，采用廣播實現的緩存一致性保證機制需要服務器對遠程緩存進行RDMA 寫操作，因此服務器端需要記錄客戶端DRAM 緩存的內存注冊信息.每次進行緩存更新時，需要通知服務器有關新加入緩存和刪除失效緩存的信息.對于新加入的緩存，需要向服務器發送緩存的內存注冊信息，以在服務器目錄中添加相應的鏈表節點.對于刪除失效的緩存，需要通知服務器從鏈表中刪除相應的客戶端緩存信息.因此，系統設計了相應的消息類型，并使用RDMA Send/Recv 進行與服務器的目錄保持一致的更新通信.

2.3 緩存一致性保證策略的動態轉換機制

經過2.1～2.2 節的設計，分布式異構內存池系統已經具備了緩存一致性保證機制.但我們需要考慮如何進行緩存一致性保證策略之間的轉換.首先，系統需要分析應用何時需要何種緩存一致性保證機制.不同應用或同一應用在不同運行節點的主要訪問模式是不同的，有的應用主要是讀，而有的應用主要是寫.

對于目錄實現的緩存一致性保證機制，每次在客戶端進行讀時需要到服務器查詢目錄的臟位置，而在寫時不需要逐個更新客戶端緩存，只需要修改服務器目錄的臟位置，因此較為適合寫比較多的訪問模式.對于廣播實現的緩存一致性保證機制，每次在客戶端進行寫時，在進行寫之后需要逐個更新相應客戶端的緩存，而在讀時可以直接進行客戶端緩存讀，不需要去遠程查詢服務器目錄，因此適合讀比較多的訪問模式.綜上所述，系統需要統計每個共享內存對象的讀寫次數，從而分析該應用的訪問模式是寫主要還是讀主要的.

在客戶端共享對象的緩存目錄中，可以通過讀寫計數得到一個向量（Wi，Ri），其中i表示某個共享對象，Wi表示該共享對象的寫次數，Ri表示該共享對象的讀次數.通過計算客戶端全部共享對象的平均值同樣可以得到另外一組向量（W*，R*），其中W*表示該客戶端的所有共享對象的寫次數平均值，R*表示該客戶端的所有共享對象的讀次數平均值.為了減小個別值的影響，采取縮尾均值法去計算平均值.寫次數縮尾均值的計算方式如式（1）所示，讀次數的縮尾均值與寫次數類似.式（1）中Wnα+1～Wn-nα表示將寫次數進行從小到大排序后的結果，α表示縮尾系數，n表示寫次數，其計算方法即去掉的數據個數除以數據總個數，縮尾均值即在計算平均值時去掉若干個最大的值和若干個最小的值，最后得到的平均值結果會減小個別極端數據的影響.

根據讀次數和寫次數的向量（Wi，Ri）和（W*，R*）組成的2×2 矩陣，我們采用矩陣分析法來進行應用訪問模式的判斷和分類.根據讀次數和寫次數的多少，可以將應用的訪問模式分為4 類：

1）當Wi

2）當WiR*時，屬于讀負載多的狀態，應用此時屬于讀多寫少的訪問模式，因此采取基于廣播的緩存一致性保證機制.在此情況下系統可以將過多遠程讀轉化為本地的緩存讀，從而提升系統的性能.

3）當Wi>W*但Ri

4）當Wi>W*且Ri>R*時，說明應用此時處于I/O 密集的階段，應用對數據對象的讀寫訪問都比較多，此時服務器的負擔較重，因此默認采取基于目錄的緩存一致性保證機制.該機制下對于過多的讀請求可以由客戶端查詢目錄后進行本地的緩存讀；而對于過多的寫請求，服務器不用進行過多的廣播刷新，只需要修改服務器上的目錄信息，從而減輕服務器的負擔.

綜上所述，利用2×2 矩陣可進行應用訪問模式的分析判定，并為不同的數據采用不同的緩存一致性保證機制.1）和4）兩種情況，分別代表低訪問和密集訪問的模式，系統在判定后，默認保持之前的緩存一致性保證策略.這2 種情況下，2 種緩存一致性保證策略對性能影響不大.對于基于目錄的緩存一致性保證機制和基于廣播的緩存一致性保證機制，其分別適用于寫操作較多和讀操作較多的模式.在低訪問和密集訪問的模式下，這2 種機制各有利弊，因此性能改變不大，默認保持之前的緩存一致性保證機制.

緩存一致性保證機制的轉換應在客戶端進行，但是當策略進行轉變時需要通知相應服務器，因此需要使用RDMA Send/Recv 來設計實現相關功能.利用客戶端的緩存目錄中的讀寫次數構建矩陣，并利用以上分析方法進行計算決策，得到需要轉換的緩存一致性策略.如果需要發送改變，則還需要通知服務器進行相應修改，以保證目錄的一致性.為了保證各個機制的正確性，還需要重新刷新緩存.具體來說，如果從廣播策略變為目錄策略，由于廣播策略可保證當前客戶端緩存是最新的，因此只需要將服務器端臟位置更新為非臟即可.如果從目錄策略變為廣播策略，由于目錄策略下不能保證客戶端緩存是最新的，因此需要在數據寫狀態為臟的情況下重新刷新其緩存，以確保在廣播策略下的正確性.

3 實驗測試與結果分析

3.1 實驗環境

本文的所有實驗都在真實的硬件環境中進行.客戶端緩存模塊使用DRAM 內存，而服務器采用DRAM 和NVM 混合內存.在每個服務器節點上，NVM和DRAM 都被配置為NUMA 架構進行分配.我們在4 臺服務器上進行性能測試，這些服務器均配置了NVM 和Infiniband RDMA 網卡.每臺機器的具體硬件配置如表2 所示.NVM 是Intel 公司推出的Optane DCPMM，該存儲器與傳統DRAM 的通道接口一致，可以直接插入主板的內存插槽.實驗中的NVM 和DRAM 均被配置為NUMA 架構，即每個存儲資源和CPU 核心都被分配給不同的節點.用于測試的服務器都通過IB 網絡進行RDMA 通信.

Table 2 Server Hardware Configuration表2 服務器硬件配置

為了測試系統在加入客戶端緩存機制和緩存一致性保證機制后的讀寫性能是否提升，本文設計了多種微基準測試來評估系統的性能.微基準測試包括申請內存對象、讀操作、寫操作和釋放內存對象等基本操作.我們針對不同的應用訪問模式，設計了9 種包含不同基本操作的微基準測試，并根據不同應用的訪問程度設置了不同的對象大小和讀寫比例，如表3 所示.

Table 3 Operating Ratios of Nine MicroBenchmarks Test表3 9 種微基準測試的操作比例 %

3.2 分布式異構內存池性能測試

首先，我們對實現了緩存一致性保證機制的分布式異構內存池系統進行了詳盡的性能測試.這些測試包括對比不同緩存一致性保證機制的測試、不同粒度對象的測試、不同讀寫比例負載的測試以及應用測試.

1）不同緩存一致性保證機制的性能測試.我們在分布式異構內存池中實現了客戶端緩存機制和可動態轉換的緩存一致性保證機制.引入緩存機制后，系統的性能理論上會有顯著提升.我們通過對系統性能進行測試來驗證這一點.首先，測試了基于目錄和基于廣播的單一緩存一致性保證機制在系統性能上的差異.接下來，進行了動態轉換的緩存一致性保證機制與現有單一機制的性能對比實驗.在表3 中，對9 種不同讀寫比例的微基準測試集進行了測試.分別測試了存儲對象大小分別為128 KB，256 KB 和512 KB 的粒度.關于對象的訪問模型，采用了均勻分布和Zipfian 分布2 種訪問模型進行測試，每組測試都進行了3 次重復實驗，并取平均值來計算延遲性能的提升百分比.

為了測試不同緩存一致性保證機制對系統性能的影響，我們分別測試了系統在使用基于目錄的緩存一致性保證機制和基于廣播的緩存一致性保證機制時的性能提升效率，本文中分別用DIC 和SNOOP代表2 種機制.圖3 展示了在均勻訪問模式下，系統使用單一緩存一致性保證機制時的性能提升情況，其中包括3 種大小不同的對象.圖3 中縱坐標表示使用一致性協議的系統相對于不使用一致性協議系統的性能提升比例.所有工作負載都取得了正向性能提升，平均性能提升比例達到了2.087.其中，對于讀操作多于寫操作的負載A，D和E，性能提升比例最大.由于系統在讀取時可以直接從緩存中讀取，而不必去遠程讀取，因此這些讀多寫少的負載可以獲得較大的性能提升.然而，在寫操作時，系統不僅需要寫入遠程節點，還需要發送請求來刷新緩存.

Fig.3 System performance for workloads under uniform accesses using a single cache consistency mechanism圖3 均勻訪問模式下使用單一緩存一致性保證機制的負載的系統性能

因此，對于寫操作較多的負載如負載B和負載G，由于寫操作較多，讀緩存帶來的性能提升被過多的寫操作削弱，系統性能提升較小.這些寫操作較多的負載在2 種機制下的性能提升比例相差不大，這是因為這2 種機制下都需要進行遠程寫入并返回，并由客戶端發起緩存刷新請求，因此客戶端的負載運行時間差別不大.此外，對于讀操作多于寫操作的負載如負載A，D和F，使用基于廣播的緩存一致性保證機制帶來的性能提升大于使用基于目錄的緩存一致性保證機制帶來的提升，這與本文設計部分中所述的機制設置特點是一致的，即廣播機制更適用于讀操作多于寫操作的負載，而目錄機制更適用于寫操作多于讀操作的負載.

圖4 展示了在Zipfian 訪問模式下，系統使用基于目錄的緩存一致性保證機制和基于廣播的緩存一致性保證機制時的性能提升情況.在Zipfian 訪問模式下，訪問更加集中于某幾個熱點數據，因此相比于均勻訪問模式，大多數負載的性能提升比例更大，平均性能提升比例達到了2.395.在均勻訪問模式下，大多數工作負載會進行一半的遠程讀取和一半的本地緩存讀取，而在Zipfian 訪問模式下，這些負載會進行更多的本地緩存讀取，而其需要更新的緩存數據較少，因此性能提升較為顯著.此外，由于系統的客戶端緩存采用了簡單的LRU 緩存而不是熱點緩存，因此在Zipfian 訪問模式下，個別負載如負載B和G的性能提升效果并不理想.這2 個負載都涉及較多的寫操作，它們對于熱數據并不敏感；無論是否緩存，對于寫操作都需要進行遠程寫入，導致它們的系統性能提升相對較小，相比均勻訪問模式沒有顯著差異.

Fig.4 System performance of workloads under Zipfian accesses using a single cache consistency mechanism圖4 Zipfian 訪問模式下使用單一緩存一致性保證機制的負載的系統性能

為了測試混合緩存一致性保證機制與不可轉換的單一緩存一致性保證機制的性能差異，我們在可動態轉換的緩存一致性保證機制下進行了相關測試，并將其與使用基于目錄的緩存一致性保證機制的系統以及使用基于廣播的緩存一致性保證機制的系統進行了性能對比，計算了性能提升率.系統中動態切換時機會影響系統性能.若轉換周期較短，會對系統增加更多的判斷和轉換的開銷，會降低動態轉換帶來的性能優勢；若轉換周期較長，則會降低用于轉換決策的統計數據的時效性，降低轉換策略本身性能提升幅度.因此，通過對數據集的先驗測試，本文將默認的調整周期設置為1 000 次共享數據的訪存操作.系統每隔1 000 次操作進行1 次緩存一致性保證機制的轉換判定.我們用“MIXED”代表可動態轉換的緩存一致性保證策略下的實驗結果.

與基于目錄機制的系統對比的實驗結果如圖5所示，可動態轉換的緩存一致性保證機制在所有負載下都取得了更好的性能提升.所有實驗結果的讀寫性能平均提升了32.3%.在基于目錄機制的緩存一致性保證機制下，系統每次讀取操作都需要進行遠程查詢臟位置或遠程讀取，而在進行機制轉換后，系統可以在讀取較多的負載中采用基于廣播的緩存一致性保證機制，從而避免了大量的遠程臟目錄查詢，直接進行本地緩存讀取并返回結果，因此對于讀取較多、寫入較少的負載，如負載A和負載D，系統的性能提升比例較大.此外，由于我們采用的微基準測試負載都是連續地讀取和連續地寫入操作，因此系統進行緩存一致性保證機制轉換的次數相對較少，僅在調用接口后進行了幾次機制的轉換.因此，對于均勻讀寫的負載，其性能提升程度一般.可以預測，在真實應用中，系統根據不同的運行時間段選擇更合適的緩存一致性保證機制，將能夠獲得更優秀的系統性能.

Fig.5 System performance under dynamic conversion mechanism compared with the directory mechanism圖5 相比于目錄機制的動態轉換機制下的系統性能

圖6 展示了可動態轉換的緩存一致性保證機制與基于廣播的緩存一致性保證機制的系統性能對比結果.我們可以觀察到，在所有負載類型下，可動態轉換機制的系統都表現出比基于廣播機制的系統更好的性能.具體而言，所有結果的讀寫性能平均提升了31.2%.在基于廣播的緩存一致性保證機制下，寫操作需要刷新所有客戶端的緩存，因此對于寫操作較多的負載，如負載B和負載G，采用可動態轉換的緩存一致性保證機制的系統獲得了更好的性能.此外，對于讀寫均勻的負載，由于這些負載是連續的讀寫操作，因此系統進行緩存一致性保證機制轉換的次數較少，導致性能提升較小.

綜上所述，相較于未實現客戶端緩存機制和緩存一致性保證機制的系統，動態轉換的緩存一致性機制可大幅度提升緩存的性能，尤其對于讀操作較多的負載，系統性能提升更為顯著.與基于目錄的和基于廣播的緩存一致性機制相比，本文實現的可動態轉換的混合緩存一致性保證機制進一步提升了系統性能.

2）對象粒度對性能的影響.為了進一步研究對象粒度對性能的影響，我們進行了基于目錄、基于廣播和可動態轉換的緩存一致性保證機制下不同對象粒度的實驗.本文設置了從8 KB 到1 MB 共8 個梯度的對象，并對負載A，B和C進行性能測試.實驗結果如圖7 所示，最上面的3 條結果是負載A的性能提升比例，中間3 條結果是負載C的性能提升比例，最下面的3 條結果是負載B的性能提升比例.負載A是讀操作較多、寫操作較少的負載，負載B是讀操作較少、寫操作較多的負載，負載C是讀操作、寫操作各占一半的負載.可以觀察到，無論采用哪種策略，由于本地緩存讀取速度更快，都帶來了顯著的性能提升.負載A具有最多的讀操作，因此性能提升最為顯著；負載B具有最多的寫操作，因此性能提升較小；對于負載C，其讀寫操作均衡，因此性能提升介于A和B之間.

Fig.7 System performance at different object sizes圖7 不同對象粒度下系統性能

對于不同的緩存一致性保證機制，基于廣播的機制提升效果大于基于目錄的機制，這是因為基于目錄的緩存一致性保證機制在讀取時需要進行遠端臟目錄查詢，導致讀操作較慢.然而，對于寫操作，基于目錄的緩存一致性保證機制無需更新大量客戶端緩存，只需修改目錄，從而減輕了服務器負載.此外，隨著對象粒度逐漸增大，系統的性能提升逐漸減小.這是因為當系統對象變大后，本地緩存容量不足，導致本地客戶端緩存失效，從而增加了遠程讀操作的次數，降低了系統的性能提升率.

3）負載的讀寫比例對性能的影響.根據以上結果我們初步得出結論，負載的讀寫比例對系統性能有較大的影響.為了具體研究負載的讀寫比例對系統性能的影響，我們在不同讀寫比例的負載下進行了均勻訪問模式的系統測試.每個實驗負載的讀寫操作總數為10 萬次，根據讀寫比例的不同進行了分梯度的測試，涵蓋了從全讀到全寫的情況.同時，對使用基于目錄、基于廣播和可動態轉換的緩存一致性保證機制的系統進行了3 種對象大小的測試.

根據圖8 可知，隨著讀寫比例中讀的比例下降、寫的比例上升，系統的運行延遲逐漸增大.由于讀操作可以利用本地客戶端緩存，對于讀操作較多的負載，其運行時間較短.然而，本文系統中的寫操作仍需進行遠程寫，因此對于寫操作較多的負載，其運行時間較長.此外，相較于使用基于目錄的緩存一致性保證機制的系統，使用基于廣播的緩存一致性保證機制的系統具有較小的運行延遲.這是由于基于廣播的系統在讀操作時減少了1 次遠程目錄查詢操作，因此性能更佳.與單一的緩存一致性保證機制相比，可動態轉換的緩存一致性保證機制取得了更好的性能.通過對比9 組結果，可以觀察到對象大小越大，系統的運行延遲也越大.這不僅因為大對象的讀寫操作更耗時，還因為大對象可能更快地占用完緩存，從而觸發緩存淘汰策略，進一步增加系統的運行延遲.

Fig.8 System performance under different read/write ratios圖8 不同讀寫比例負載下系統性能

綜上所述，負載的讀寫比例對系統性能有顯著影響.基于廣播的緩存一致性保證機制相較于基于目錄的機制具有更低的運行延遲，而可動態轉換的緩存一致性保證機制在各方面均表現更優.此外，對象大小的增加導致系統運行延遲增大，既因為大對象的讀寫操作更耗時，又因為大對象更容易觸發緩存淘汰策略，進而增加系統的運行延遲.

4）真實應用的性能測試.以上測試均采用了微基準測試中的9 種負載.這些微基準測試中的讀寫操作都是連續進行的，并且訪問模式較為單一.因此，本文針對PageRank 算法，采用wordassociation-2011數據集進行了真實應用的測試.該數據集包含10 617個節點和72 172 條邊.實驗測試PageRank 算法達到收斂所需的運行時間.由圖9 可以觀察到，實現了客戶端緩存的系統性能遠高于無緩存的系統.與未實現緩存的系統相比，基于目錄的緩存一致性保證機制和基于廣播的緩存一致性保證機制分別提升了PageRank 應用性能的1.7 倍和2.6 倍.而可動態轉換的混合緩存一致性保證機制相較于單一的目錄機制和廣播機制，分別提升了72.9%和31.6%的性能.由此可見，所提出的混合緩存一致性保證機制在真實的應用場景也取得了顯著的性能提升，具有很好的適用性.

Fig.9 Running time of PageRank圖9 PageRank 應用的運行時間

3.3 分布式異構內存池擴展性測試

我們在實現緩存一致性保證機制的分布式異構內存池中進行了擴展性測試.實驗分別運行了1～16個客戶端，并測試了負載A、負載B和負載C在這些情況下的運行時間.實驗中對象粒度大小設置為128 KB，對象訪問模式為均勻訪問，并采用了可動態轉換的緩存一致性保證機制.

如圖10 所示，隨著分布式異構內存池系統中共享客戶端數量的增加，系統性能逐漸下降，運行延遲不斷增加.然而，系統的擴展性仍然較好.特別是對于負載A，隨著共享客戶端數量的增加，運行延遲的增加并不明顯.這是因為負載A主要是讀操作，每個客戶端都可以讀取自己本地的客戶端緩存，各個客戶端之間沒有性能影響.對于負載B，該負載主要由寫操作組成，隨著客戶端數量的增加，運行延遲明顯上升.這是因為對于寫操作，每次寫操作都需要客戶端向服務器發送緩存刷新請求，服務器會將最新的緩存數據發送給客戶端，從而增加了服務器的負擔.此外，由于實驗資源的限制，一個實測機器在實驗中運行了多個客戶端程序，這也對性能產生了影響，進而導致延遲的增加.

Fig.10 System scalability test圖10 系統的擴展性測試

綜上所述，在實現了客戶端緩存機制和多客戶端共享機制后，系統的多客戶端擴展性較好.然而，對于寫操作較多的負載，擴展性仍有改善的空間.

4 總結

本文提出了一種可動態轉換的分布式異構內存池中的緩存一致性保證機制以提高效率.在該機制中，通過多客戶端共享機制實現多客戶端對遠端存儲對象的讀寫操作.采用基于目錄和基于廣播相結合的混合緩存一致性保證機制，并根據緩存數據塊的訪問模式動態轉換使用不同的機制.通過矩陣分析判定每個數據塊的訪問模式，并選擇適合的緩存一致性保證策略：對于讀多寫少的數據塊，選擇基于廣播的機制；對于寫多讀少的數據塊，選擇基于目錄的機制.這種方式提高了數據同步效率，進一步提升了使用緩存的性能優勢.實驗結果表明，相較于使用單一基于目錄或基于廣播的緩存一致性保證機制的分布式異構內存池系統，采用可動態轉換的機制分別提升了32.31%和31.20%的系統平均讀寫性能.此外，在多客戶端環境下，可動態轉換的緩存一致性保證機制展現出良好的擴展性能.

作者貢獻聲明：段卓輝和劉海坤提出了設計思路和實現方案；趙金瑋和劉一航負責實現并撰寫論文；廖小飛和金海提出指導意見并修改論文.