面向存算聯調的跨云糾刪碼自適應數據訪問方法

張凱鑫 王意潔 包 涵 闞浚暉

（并行與分布計算全國重點實驗室（國防科技大學） 長沙 410073）

（國防科技大學計算機學院 長沙 410073）

隨著數字經濟生態和云計算技術的蓬勃發展，用戶的云計算需求量迅速擴大且需求越發多樣化.由于單一云廠商服務能力有限，逐漸難以滿足用戶的全部需求.跨云調度計算任務可有效緩解單一云廠商服務能力不足以滿足用戶需求的問題.為此，研究者提出了云際計算技術，以云廠商之間的開放協作為基礎，有效破解云廠商鎖定問題，方便開發者通過軟件定義方式定制云服務，為計算任務跨云調度創造了基礎條件.

然而，由于跨云調度的計算任務通常需要跨云訪問數據（即跨云存算聯調），且在諸如機器學習、氣象預報、基因測序、粒子物理等領域的計算任務的數據集往往高達數百TB[1]，因而跨云調度后的計算任務的執行效率受到跨云數據訪問速度的嚴重制約.基于數據冗余（糾刪碼和多副本）技術的跨云數據訪問方法是提高數據跨云訪問速度的重要技術途徑之一.相較于多副本[2-5]，糾刪碼具有更高的數據容錯性和更低的數據冗余度[6-7].因此，基于糾刪碼的跨云數據訪問方法成為了當前的研究熱點.基于糾刪碼的跨云數據訪問方法的基本思想為：首先，把原始數據對象分為k個數據塊；然后，把k個數據塊編碼為n個編碼塊（這n個編碼塊中可能包含k個數據塊），使用這n個編碼塊中的任意n-d+1 個編碼塊均可重構出k個數據塊；接著，把n個編碼塊存儲到多個云上；當某個數據訪問節點需要訪問數據時，選擇若干云請求n-d+1 個編碼塊，用這些編碼塊重構出k個數據塊，并將這些數據塊重組為原始數據對象[8].

由于云間網絡帶寬通常遠低于云內網絡帶寬，而基于糾刪碼的跨云數據訪問方法需要跨多個云傳輸編碼塊.因此，基于糾刪碼的跨云數據訪問方法的編碼塊傳輸用時通常較長，使得其數據訪問速度較慢.

基于糾刪碼的跨云數據訪問方法主要可從2 個方面來縮短編碼塊傳輸用時：

1）合理制定編碼數據訪問方案[9-13].由于糾刪碼可使用任意n-d+1 個編碼塊重構出k個原始數據塊，因此基于糾刪碼的跨云數據訪問方法可選擇與數據訪問節點間延遲較低（或帶寬較高）的云上的編碼塊來重構數據，從而縮短編碼塊傳輸用時.

2）合理緩存編碼塊[14-20].基于糾刪碼的跨云數據訪問方法可通過把常被訪問的編碼塊緩存在相應的數據訪問節點附近，以縮短整體的編碼塊傳輸用時.

在引入編碼塊緩存的情況下，基于糾刪碼的跨云數據訪問方法的編碼塊傳輸用時顯著受到緩存命中量（從數據訪問節點對應的緩存中讀取的數據總量）、緩存命中增效（緩存命中時編碼塊傳輸用時的縮短量）、低傳輸速度編碼塊訪問量的影響.

然而，現有基于糾刪碼的跨云數據訪問方法存在2 個方面的不足，使得其緩存命中量和緩存命中增效較低且低傳輸速度編碼塊訪問量有待降低：

1）緩存管理粒度較粗.現有基于糾刪碼的跨云數據訪問方法以編碼塊為單位管理緩存，緩存編碼塊只存在命中和未命中2 種狀態，無法利用部分命中的緩存編碼塊，因而其緩存命中量較低.

2）未協同優化緩存管理與編碼數據訪問方案.現有基于糾刪碼的跨云數據訪問方法在選擇加入緩存的編碼塊時，未綜合考慮編碼數據訪問方案制定算法選擇各編碼塊用于重構數據的概率以及各編碼塊的實際傳輸速度，不利于提高緩存命中量和緩存命中增效；或者在制定編碼數據訪問方案時，未充分考慮緩存對各編碼塊傳輸速度的影響，不利于準確評估各編碼塊傳輸速度，因而難以有效減少低傳輸速度編碼塊訪問量.

現有基于糾刪碼的跨云數據訪問方法存在的緩存命中量低、緩存命中增效較低、低傳輸速度編碼塊訪問量大的問題，導致其編碼塊傳輸用時較長，進而使得其數據訪問效率仍有待提升.

為此，本文首先提出了一種基于星際文件系統（interplanetary file system，IPFS）的跨云存儲系統框架（IPFS-based cross-cloud storage system framework，IBCS）.IBCS 基于IPFS 的數據分片管理機制實現細粒度緩存管理，可提高緩存命中量.此外，在引入緩存后，同一編碼塊的多個副本可能同時存儲在多個云上，IBCS 可充分利用這些副本提高編碼塊的傳輸并行度，從而減少低傳輸速度編碼塊.

然后，在框架IBCS 下，本文提出了一種面向存算聯調的跨云糾刪碼自適應數據訪問方法（adaptive erasure-coded data access method for cross-cloud collaborative scheduling of storage and computation，AECAM），可通過協同優化緩存管理與編碼數據訪問方案提高緩存命中量和緩存命中增效.具體提出2 個關鍵算法：

1）編碼數據訪問方案自適應制定算法（adaptive formulating algorithm of erasure-coded data reconstruction scheme，AFERS）.AFERS 首先根據IPFS 集群的各個存儲節點與數據訪問節點間的傳輸延遲、各編碼塊在各存儲節點里的存儲狀態（含正常存儲、長期緩存、臨時緩存等）、數據訪問節點的類型（云內計算節點、云外計算節點），綜合評估指定節點訪問數據的過程中各編碼塊的傳輸速度.然后，根據各編碼塊傳輸速度的評估值，自適應制定可避免訪問傳輸速度評估值低的編碼塊的編碼數據訪問方案.

2）基于數據訪問過程感知的緩存管理算法（cache management algorithm based on data access process-aware，CADA）.CADA 根據數據訪問過程中AFERS 對各編碼塊傳輸速度的評估值，以及被傳輸的編碼塊的實際傳輸速度，決定各編碼塊的緩存優先級.優先在數據訪問節點附近緩存易被AFERS 選中（傳輸速度預估值高）且實際傳輸速度相對較低的編碼塊，因而能同時提高緩存命中量及緩存命中增效.

1 相關工作

1.1 糾刪碼數據訪問方案

糾刪碼數據訪問方案可由二元組〈type,blocks〉組成.其中type為數據訪問方案的類別，包括直接數據訪問方案和降級數據訪問方案；blocks為訪問數據時需獲取的編碼塊的列表.

1）直接數據訪問方案

如圖1 所示，直接數據訪問方案是指數據訪問節點直接獲取被訪問數據對象的k個數據塊，然后將它們重組成被訪問數據對象.直接訪問方式無需進行解碼運算且實現簡單，因而大部分分布式存儲系統（GFS（Google file system）[3]，Lustre[4]，Ceph[5]等）均默認采用這種數據訪問方式.

圖1 直接數據訪問方案示意圖Fig.1 Illustration of direct data access scheme

對于直接數據訪問方案，需獲取的編碼塊固定為k個數據塊.因此，直接數據訪問方案只有1 套.

2）降級數據訪問方案

如圖2 所示，降級數據訪問方案是指數據訪問節點獲取被訪問數據對象的任意n-d+1 個編碼塊，并將其解碼為k個數據塊，然后用解碼出的數據塊重組出原始數據對象.由于降級訪問會帶來額外的計算開銷，因此在大部分存儲系統中，僅當無法正常獲取數據塊時才會采用降級數據訪問方案[6].

圖2 降級數據訪問方案示意圖Fig.2 Illustration of degraded data access scheme

對于降級數據訪問方案，需獲取的編碼塊列表blocks的可能取值有組.因此，降級數據訪問方案共有套.

1.2 廣域糾刪碼數據訪問技術

在廣域部署的基于糾刪碼的存儲系統（如基于糾刪碼的跨云存儲系統）進行數據訪問時，通常需要在低帶寬鏈路上傳輸大量編碼塊，導致編碼塊傳輸速度成為了數據訪問的瓶頸.為此，研究者提出了一系列廣域糾刪碼數據訪問技術，主要分為基于數據訪問方案優化的廣域糾刪碼數據訪問技術和基于緩存的廣域糾刪碼數據訪問技術.

1）基于數據訪問方案優化的廣域糾刪碼訪問技術

基于數據訪問方案優化的廣域糾刪碼訪問技術的基本思想是：傳統分布式存儲系統默認采用直接數據訪問方案，因為其計算量較小.然而，在廣域環境中，不同域的節點間的數據傳輸速度遠低于域內節點間的數據傳輸速度，且不同域節點的I/O 性能差異較大.如果數據訪問節點與大量數據塊存儲節點屬于不同的域或者大量數據塊存儲節點的I/O 性能較低，則會導致必須訪問數據塊的直接數據訪問方案的傳輸開銷大于某些降級數據訪問方案.因此，基于數據訪問方案優化的廣域糾刪碼訪問技術會綜合評估各編碼塊存儲節點和客戶端間的帶寬、各編碼塊存儲節點的綜合性能，求得效率較高的數據訪問方案.

例如，Saeed[12]以傳輸開銷和服務延遲優化為目標，提出一種跨地域分布云環境下的糾刪碼訪問方法Sandooq.Sandooq 以編碼塊請求在各云數據中心的排隊時延，以及以數據訪問節點與存儲各編碼塊的云數據中心的物理距離為依據建立讀取優化函數，按照梯度下降的方法尋找最優數據訪問方案.Zhang等人[13]提出基于節點性能感知和精確距離估算的糾刪碼降級訪問方法NADE.NADE 首先收集存儲節點的容量、CPU 頻率、吞吐量、響應時間、時延等指標的歷史數據，并以此為依據構建各節點之間的歐氏距離.然后，根據各節點間歐氏距離估算客戶端獲取每個編碼塊的開銷，并以此為依據求出最優數據訪問方案.此外，Rashmi 等人[14]提出了一種延遲綁定的糾刪碼訪問方法LBA.采用LBA 的數據訪問節點會請求多個編碼塊，并選擇先傳輸到數據訪問節點的n-d+1 個編碼塊重構原始數據對象.

2）基于緩存的廣域糾刪碼數據訪問技術

基于緩存的廣域糾刪碼數據訪問技術的基本思想是：由于跨域傳輸編碼塊的開銷較大，因而把部分訪問頻率高、傳輸速度低的編碼塊緩存在數據訪問節點附近以提高后續數據訪問速度.

例如，Zhang 等人[15]提出了一種基于慢節點感知的編碼數據緩存系統POCache，用于提高廣域糾刪碼的數據訪問速度.POCache 將校驗塊緩存到數據訪問節點附近，并在訪問數據時優先請求數據塊.當數據塊的傳輸速度過低時，POCache 將選擇從緩存節點獲取校驗塊，并使用緩存校驗塊與訪問效率正常的數據塊重構原始數據對象.此外，POCache 可支持用戶自行選擇緩存引入算法和緩存驅逐算法.然而，POCache需要測出各數據塊傳輸速度后才能確定用于重構原始數據對象的編碼塊，對其數據訪問速度帶來不利影響.Halalai 等人[16]提出了一種基于緩存收益評估的編碼數據緩存系統Agar，將編碼塊的全局訪問次數與各數據訪問節點獲取該編碼塊的開銷的乘積作為各數據訪問節點緩存該編碼塊的預期收益，并將預期收益較高的編碼塊緩存到對應的數據訪問節點.

整體而言，現有基于數據訪問方案優化的廣域糾刪碼訪問技術和基于緩存的廣域糾刪碼數據訪問技術均可提高廣域環境（含跨云環境）下的糾刪碼數據訪問效率，但存在2 點不足：首先，現有工作中的緩存管理優化與編碼數據訪問方案優化結合不緊密，未同時做到根據緩存編碼塊分布情況決定數據訪問方案、根據數據訪問方案制定策略決定編碼塊緩存優先級，導致其緩存命中量和緩存命中增效仍有待提高.此外，現有工作為優化緩存管理與編碼數據訪問方案，通常需要耗費較多額外的計算、網絡、存儲資源以采集、維護存儲節點狀態信息及各類節點間的網絡信息.

1.3 星際文件系統

星際文件系統是一個去中心化的分布式文件系統[21-23]，基于分布式哈希表（distributed Hash table，DHT）、BitTorrent 點對點文件共享協議、Git 分布式版本控制、Merkle DAG 等已有技術，實現了數據的分片存儲、內容尋址及點對點（peer-to-peer，P2P）高速傳輸.

1）數據分片存儲

IPFS 將用戶數據分為若干個大小不超過256 KB的數據分片，并使用Merkle DAG 來組織各個存儲節點上的數據分片.如圖3 所示，Merkle DAG 的末端節點的內容為各個數據分片，其他節點的內容為其所有子節點的內容組合的哈希值.

圖3 Merkle DAG 示意圖Fig.3 Illustration of Merkle DAG

此外，Merkle DAG 的每個頂端節點對應一個數據對象，該數據對象的內容為其子孫節點中末端節點內容（數據分片）的組合.

分片存儲數據并使用Merkle DAG 來維護數據對象和數據分片間的關系的主要優點是：在同一IPFS存儲節點上，多份用戶數據對象均含有的數據分片只需要被實際存儲1 份，因而可顯著降低存儲開銷.

2）數據內容尋址

在IPFS 中，每份用戶數據對象對應于一個Merkle DAG 的根哈希，且每個數據分片的哈希也由Merkle DAG 維護.此外，IPFS 采用了分布式哈希表，支持任意IPFS 節點通過哈希值定位到維護了指定用戶數據對象的Merkle DAG 的節點，以及存儲了指定數據分片的節點.

因此，在IPFS 中，訪問數據的基本過程有4 個：

①數據訪問節點向IPFS 集群發送需訪問數據對象的根哈希，IPFS 集群通過查詢分布式哈希表定位到維護了被請求數據對象的Merkle DAG 的節點，并將相應的Merkle DAG 傳輸到數據訪問節點.

②數據訪問節點根據接收到的Merkle DAG 解析出被訪問數據的各數據分片的哈希.

③數據訪問節點向IPFS 集群發送需訪問數據對象的各數據分片的哈希，IPFS 集群通過查詢分布式哈希表定位到存儲了這些數據分片的節點，并將這些數據分片傳輸到數據訪問節點.

④數據訪問節點根據接收到的Merkle DAG 和數據分片，構造出被訪問的數據.

3） P2P 高速傳輸

在IPFS 中，數據訪問節點會同時請求多個數據分片且可能有多個存儲節點上擁有部分或全部被請求的數據分片.因此，IPFS 采用以BitSwap[24]數據交換協議為核心的P2P 傳輸技術，根據節點信用分、性能、負載、網絡狀況等因素選擇各數據分片的提供節點，并從多個提供節點并行地向數據訪問節點發送其請求數據的各數據分片，從而顯著提高數據傳輸速度.

此外，IPFS 具有緩存機制，各節點會將請求過的數據分片緩存在本地一段時間.期間，如果其他節點請求這些數據分片，該節點仍能將緩存的數據分片提供出去，以提高其他節點的數據訪問速度.

最后，在IPFS 的BitSwap 協議中，引入了信用機制，根據各節點對外提供數據的情況為其評定信用分.對外提供數據越頻繁的節點的信用分越高，而信用分越高的節點需要數據時會有更多的節點向其提供數據.在各節點屬于不同主體的場景下（如跨云存儲場景），這種信用機制可以促進各主體積極對外提供數據，進而提高IPFS 系統的整體數據訪問速度.

2 基于IPFS 的跨云存儲系統框架(IBCS)

本節提出了框架IBCS，可基于IPFS 的分片存儲、內容尋址及P2P 傳輸等技術，實現細粒度緩存管理和高速編碼塊傳輸.

2.1 體系結構

如圖4 所示，框架IBCS 由讀寫控制層、存儲傳輸層和數據服務層組成.

圖4 IBCS 示意圖Fig.4 Illustration of IBCS

1）讀寫控制層包含協調節點和多個云代理節點，主要負責響應客戶端請求，完成用戶數據的寫入和訪問，具體工作由協調節點上的協調組件、云代理節點上的代理組件和元數據管理組件完成：

①協調組件負責解析用戶命令，生成寫入、訪問過程的控制命令，并發往代理組件；

②代理組件負責執行協調組件發送的命令，包括調用IPFS 組件向IPFS 集群寫入編碼塊或從IPFS集群讀取編碼塊、對編碼塊進行解碼操作、將解碼編碼塊得到的數據上傳到各云存儲服務或傳輸到云外計算節點；

③元數據管理組件負責維護用戶、數據對象、編碼塊、云代理、云存儲服務等元數據.

2）存儲傳輸層由各云代理節點構成，主要負責在各云代理節點上的存儲空間中存儲管理用戶數據對象的編碼塊，并在各云代理節點之間傳輸這些編碼塊，具體工作由各云代理節點上的代理組件和IPFS組件完成：

①代理組件負責調用IPFS 組件，完成本節點上持久化存儲編碼塊及緩存編碼塊的讀出、寫入和狀態變更；

②各IPFS 組件及各云代理的存儲空間構成了IPFS集群，負責持久化存儲或緩存編碼塊、執行代理組件命令、從IPFS 集群中讀取編碼塊、向IPFS 集群寫入編碼塊、利用P2P 技術在不同云的代理節點間高效傳輸編碼塊.

3）數據服務層為各個云的云存儲服務（可被各云代理節點訪問），將用戶數據對象存儲到云存儲服務后，同一云上的計算節點才能正常訪問該數據對象.

2.2 工作原理

框架IBCS 的核心工作原理包括數據寫入原理、數據訪問原理、存儲狀態管理原理和緩存實現原理.

1）數據寫入

如圖5 所示，客戶端首先向協調節點發起數據寫入請求后，協調節點為用戶數據分配云代理節點；然后，客戶端會將原用戶數據分割為k個數據塊，并對這k個數據塊進行編碼計算后得到n個編碼塊；最后，客戶端將n個編碼塊傳輸至協調節點分配的云代理節點，各云代理節點的代理組件會接收這些編碼塊，并調用IPFS 組件將編碼塊按照IPFS 的數據組織格式（分片后以Merkle DAG 組織）存儲到本節點的存儲空間.

圖5 IBCS 數據寫入方案Fig.5 IBCS data write scheme

2）數據訪問

在框架IBCS 中，有2 種節點可能需要訪問數據：云內計算節點和云外計算節點.

如圖6 所示，云內計算節點可高效訪問其所在云的云存儲服務中的數據.云內計算節點需要訪問數據的過程為：首先，客戶端向協調節點發送數據訪問請求；然后，協調節點根據客戶端請求，擬制數據訪問方案并生成控制命令發送云內計算節點對應的云代理節點；隨后，接收到命令的云代理節點從IPFS 集群讀出待訪問數據對象的編碼塊，解碼出原始數據，并上傳到對應的云存儲服務.

圖6 IBCS 數據訪問方案（云內計算節點）Fig.6 IBCS data access scheme(in-cloud nodes)

云外計算節點無權限訪問或不可高效訪問云存儲服務.如圖7 所示，云外計算節點訪問數據的過程為：首先，云外計算節點（運行著客戶端）向協調節點發送請求，獲取其所需數據的編碼塊的云代理節點信息；然后，云外計算節點擬制數據訪問方案并向各代理節點請求編碼塊；隨后，各代理節點將編碼塊從IPFS 集群中讀出后，發送給云外計算節點；最后，云外計算節點將收到的編碼塊解碼為所需數據.

圖7 IBCS 數據訪問方案（云外計算節點）Fig.7 IBCS data access scheme(nodes outside the cloud)

3）存儲狀態管理

在框架IBCS 中，各云代理節點上由IPFS 組件維護的存儲空間既是編碼塊的持久化存儲空間，又是編碼塊的緩存空間.

IPFS 組件維護的存儲空間中的編碼塊有長期存儲（pinned）和臨時存儲（tmp）兩種狀態.處于tmp 狀態的編碼塊會被IPFS 組件的垃圾回收程序定時清理，處于pinned 狀態的編碼塊則不被垃圾回收程序清理.

代理組件向IPFS 集群寫入編碼塊時，為了最大化數據容錯度，通常避免將一個條帶上的編碼塊及其副本分配至同一個云代理節點上，以確保單一節點失效時同一數據對象的編碼塊中最多一個編碼塊受到影響.圖8 說明了IBCS 編碼塊存儲狀態的變化，寫入的編碼塊會默認以pinned 的狀態存儲在代理組件所在云代理節點的存儲空間中，直到維護該存儲空間的IPFS 組件接收到改變該編碼塊狀態的unpin命令.代理節點從IPFS 集群讀取的編碼塊，會以tmp的狀態存儲在代理組件所在代理節點的存儲空間中，直到維護該存儲空間的IPFS 組件啟動垃圾回收策略.此外，如果某云代理節點上的IPFS 組件接收到請求某個編碼塊的pin 命令，IPFS 集群使用P2P 傳輸技術將該編碼塊傳輸到該云代理節點上的存儲空間中并設置為pinned 狀態.

圖8 IBCS 編碼塊存儲狀態管理原理Fig.8 Principle of coding blocks storage state management in IBCS

因此，通過對各IPFS 組件發送pin 命令和unpin命令，可以實現編碼塊存儲狀態的靈活管理.

4）緩存實現

在框架IBCS 中，持久化存儲的編碼塊和緩存編碼塊均存儲在各云代理節點的存儲空間，如表1 所示.其中，持久化存儲的編碼塊一直處于pinned 狀態；緩存編碼塊可能處于pinned 狀態，也可能處于tmp 狀態，二者間的轉換由運行的代理組件控制.

Table 1 Classification of Coding Blocks in IBCS表1 IBCS 中編碼塊的分類

2.3 框架分析

框架IBCS 的主要特點有4 個方面：

1）利用IPFS 的數據分片管理機制實現了緩存數據的細粒度管理，可從2 個方面提高緩存命中量.一方面，利用IPFS 的數據分片管理機制避免在同一云代理節點上存儲重復的數據分片，因而能降低存儲開銷，進而增加了各云代理節點可緩存的編碼塊數；另一方面，數據分片管理機制使得未命中緩存編碼塊中的命中數據分片可以被利用起來，如圖9 所示.

圖9 IBCS 的細粒度緩存管理示意圖Fig.9 Illustration of fine-grained cache management in IBCS

2）基于IPFS 的P2P 傳輸技術，可充分利用系統中持久化數據和緩存數據來提高編碼塊的傳輸并行度，通過減少低傳輸速度編碼塊從而有效提高編碼塊傳輸速度.此外，IPFS 的P2P 傳輸技術引入了信用機制，可以促進各云主體提升自身對外提供數據的能力，有助于不斷提高跨云存儲系統的編碼塊傳輸速度.

3）得益于IPFS 的內容尋址機制，讀寫控制層只需要管理各個編碼塊的根哈希即可，無需管理各個數據分片信息，因而數據分片管理機制、P2P 傳輸過程對讀寫控制層而言是透明的，這大大降低了元數據管理開銷和系統實現難度.

4）針對云內計算節點和云外計算節點，分別設計了不同的數據訪問流程，適用范圍較廣.

3 面向存算聯調的跨云糾刪碼自適應數據訪問方法(AECAM)

第2 節提出了一種基于IPFS 的跨云存儲系統框架(IBCS).基于IBCS，本節提出一種面向存算聯調的跨云糾刪碼自適應數據訪問方法(AECAM)，可通過協同優化緩存管理與數據訪問方案減少數據訪問過程中的編碼塊傳輸用時.

具體而言，首先提出一種編碼數據訪問方案自適應制定算法(AFERS)，可根據IPFS 集群的各個存儲節點與數據訪問節點的傳輸延遲、各編碼塊在各存儲節點里的存儲情況、數據訪問節點的類型，綜合評估數據訪問過程中各編碼塊的傳輸速度，并以此為依據自適應制定可避免訪問傳輸速度評估值低的編碼塊的編碼數據訪問方案，從而縮短數據訪問過程中的編碼塊傳輸用時.

然后，提出了一種基于數據訪問過程感知的緩存管理算法(CADA)，可優先在數據訪問節點緩存易被編碼數據訪問方案自適應制定算法AFERS 選中（傳輸速度預估值高）且實際傳輸速度相對較低的編碼塊，以同時提高緩存命中量及緩存命中增效，進而縮短數據訪問過程中的編碼塊傳輸用時.

3.1 編碼數據訪問方案自適應制定算法(AFERS)

1）核心思想

算法AFERS 首先針對云內計算節點訪問數據和云外計算節點訪問數據2 種場景，分別建模評估編碼塊傳輸速度.然后，AFERS 可根據各編碼塊傳輸速度的評估值制定編碼數據訪問方案.

①編碼塊傳輸速度評估

算法AFERS 將數據訪問節點區分為云內計算節點和云外計算節點2 種，并根據框架IBCS 中將數據傳輸到2 類數據訪問節點的具體過程，使用不同的模型來評估這2 類數據訪問節點訪問數據時的編碼塊傳輸速度.

(i)云內計算節點訪問數據時的編碼塊傳輸速度評估

在框架IBCS 中，云內計算節點需要訪問數據時，編碼塊通過P2P 傳輸技術被傳輸到數據訪問節點所對應的云代理節點，然后該云代理節點會用接收到的編碼塊解碼出原始數據對象，并將原始數據對象上傳到需訪問數據的云內計算節點（數據訪問節點）可訪問的云存儲服務.

上述過程中，影響編碼塊傳輸速度的主要因素包括P2P 網絡中存儲了各編碼塊的云代理節點數，以及這些云代理節點與數據訪問節點對應云代理節點間的實時帶寬.P2P 網絡中實際存儲待傳輸編碼塊的云代理節點數越多，編碼塊傳輸速度越快；這些云代理節點與數據訪問節點對應云代理節點間的實時帶寬越高，編碼塊傳輸速度越快.

因此，若令b為待傳輸編碼塊，c為數據訪問節點對應的云代理節點（編碼塊的傳輸目的地節點），Eb,c為將編碼塊b傳輸到目的地節點c的速度，qb為存儲編碼塊b的云代理節點數，xb,i(i∈[1,qb])為第i個存儲了編碼塊b的云代理節點的序號，Bc,xb,i為序號為xb,i的云代理節點與傳輸目的地節點c間的實時帶寬，則有

此外，由于框架IBCS 中各云代理節點上的編碼塊的狀態包括2 類pinned 和tmp，且處于tmp 狀態的編碼塊有一定概率已經被回收（狀態為pinned 的編碼塊沒被回收的概率為1），所以，若令Qb為可能存儲編碼塊b的云代理節點數（存儲了處于pinned 狀態或tmp 狀態的編碼塊b的云代理節點數），yb,i（i∈[1,Qb])為第i個可能存儲編碼塊b的云代理節點Nodeyb,i的序號，Bc,yb,i為Nodeyb,i與傳輸目的地節點c間的實時帶寬，pyb,i為Nodeyb,i實際存儲了編碼塊b的概率，則有

由于IPFS 會定時觸發垃圾回收任務刪除處于tmp 狀態的編碼塊，因此，若令IPFS 觸發垃圾回收任務的周期為T，節點Nodeyb,i上的編碼塊b處于tmp 狀態的時長為tb,yb,i，則該節點上編碼塊b未被回收（實際存在）的概率為

因此，Nodeyb,i中編碼塊b未被回收的概率為

最后，由于測量節點間實時帶寬的開銷較大，算法AFERS 使用節點間延遲來估算帶寬，具體估算方法為：

其中Dc,yb,i為Nodeyb,i與傳輸目的地節點c間的傳輸延遲.通常情況下，2 個節點間的傳輸延遲越大意味著在2 個節點間傳輸數據時的數據轉發的次數越多，而數據轉發次數的增加將導致數據傳輸途經低帶寬鏈路的概率增加、丟包率提升，進而導致傳輸帶寬降低，因此延遲通常與帶寬呈負相關.此外，實際測試中發現，傳輸延遲少于1ms 時（如2 個節點處于同一云中）節點間帶寬將大幅度提高（同云內節點間帶寬遠高于不同云節點間帶寬）.式（5）符合上述2 項規律.綜上，可得

因此，算法AFERS 在訪問數據前，用式（7）為各編碼塊評分，當傳輸目的地云代理節點為c時，編碼塊b的傳輸速度評分為Sb,c：

通常而言，評分越高，編碼塊相對傳輸速度越高.

（ii）云外計算節點訪問數據時的編碼塊傳輸速度評估

在框架IBCS 中，云外計算節點需要訪問數據時，編碼塊通過TCP 協議直接從特定云代理節點傳輸到需要訪問數據的云外計算節點（數據訪問節點），并由數據訪問節點將編碼塊解碼為原始數據對象.

上述過程中，影響編碼塊的傳輸速度的主要因素為存儲了編碼塊的云代理節點與需訪問數據的計算節點間的實時帶寬的最大值.因此，若令o為數據訪問節點（編碼塊傳輸目的地節點），Eb,o為將編碼塊b傳輸到計算節點o的速度，Wb為以pinned 狀態存儲編碼塊b的云代理節點數，zb,i(i∈[1,wb])為第i個存儲編碼塊b的云代理節點Nodezb,i的序號，Bo,zb,i為Nodezb,i與數據訪問節點o間的實時帶寬，則有

此外，算法AFERS 使用節點間延遲來估算帶寬，具體估算方法為：

其中Do,zb,i為Nodezb,i與計算節點o間的傳輸延遲.綜上可得

因此，算法AFERS 在訪問數據前，用式(11)為各編碼塊評分，當傳輸目的地計算節點為o時，編碼塊b的傳輸速度評分為Sb,o：

通常而言，評分越高，編碼塊相對傳輸速度越高.

②編碼數據訪問方案制定

在跨云環境下，數據訪問過程中最耗時的步驟通常為傳輸編碼塊.因此，編碼數據訪問方案制定的主要思想是根據編碼塊的傳輸速度評分，為不同編碼數據訪問方案〈type,blocks〉的編碼塊傳輸速度評分，其中type為編碼數據訪問方案類型，blocks為訪問數據時需獲取的編碼塊的列表，并以〈type,blocks〉為主要依據確定編碼數據訪問方案以及編碼訪問方案中各編碼塊的提供節點.

(i)編碼數據訪問方案的編碼塊傳輸速度評分

通常而言，各節點的數據接收能力遠高于跨云節點間的數據傳輸能力，且同一節點可并行接收不同節點發來的編碼塊.因此，編碼數據訪問方案〈type,blocks〉的編碼塊傳輸速度為blocks中各編碼塊的傳輸速度的最小值.

由于直接數據訪問方案需要傳輸k個數據塊，因此該類方案編碼塊傳輸速度評分Edir為k個數據塊的傳輸速度評分的最小值；由于降級數據訪問方案需要傳輸任意n-d+1 個編碼塊，因此該類方案的編碼塊傳輸速度評分Eun為傳輸速度評分第n-d+1 高的編碼塊的傳輸速度評分.

(ii)編碼數據訪問方案選擇

算法AFERS 結合各類數據訪問方案的編碼塊傳輸速度評分及計算開銷確定數據訪問方案類型type.由于直接數據訪問方案的計算開銷較小，所以將其編碼塊傳輸速度評分Edir乘上一個權值s后與降級數據訪問方案的編碼塊傳輸速度評分Eun比較.若sEdir＞Eun，則采用直接數據訪問方案，反之采用降級數據訪問方案.假設Ddir為直接訪問方案中k個數據塊的傳輸速度評分的最小值所對應的代理節點與云外計算節點間的延遲，Dun為降級訪問方案中傳輸速度評分第n-d+1 高的編碼塊所對應的代理節點與云外計算節點間的延遲，將式（10）帶入選擇直接數據訪問的條件sEdir＞Eun，可得Ddir＜.換言之，當且僅當Ddir＜時，選擇直接數據訪問方案，反之選擇降級數據訪問方案.因此，當s≤1 時，滿足Ddir≥Dun即選擇降級數據訪問方案，此時忽略了降級數據訪問方案帶來的額外計算開銷，因而s≤1 不合理；當s≥2 時，至少滿足Ddir≥才選擇降級數據訪問方案，由于滿足不等式Ddir≥的Dun通常遠小于Ddir，這將造成數據傳輸開銷遠低于直接訪問方案的降級數據訪問方案被放棄，因而s≥2 不合理.因此s的合理取值范圍為1＜s＜2，本文實驗中取s=1.5.

若采用直接數據訪問方案，需要傳輸的編碼塊blocks為k個數據塊.若采用降級數據訪問方案，為了盡可能提高整體編碼塊傳輸速度，需要傳輸的編碼塊blocks為傳輸速度評分最高的n-d+1 個編碼塊.

(iii)提供編碼塊的云代理節點選擇

當數據訪問節點為云內計算節點時，該計算節點對應的云代理節點只需要提供各需傳輸編碼塊的根哈希，相應的編碼塊即可通過P2P 傳輸技術傳輸到該云代理節點上，因而此時無需選擇提供各編碼塊的云代理節點.

當數據訪問節點為云外計算節點時，則需要從存儲了需傳輸編碼塊的各云代理節點中，選擇與計算節點間的網絡延遲最小的云代理節點作為提供該編碼塊的節點.

2）算法描述

算法AFERS 的具體工作流程如算法1 所示.

算法1.算法AFERS.

輸入：數據訪問節點accessNode，訪問數據IDdataID；

輸出：編碼數據訪問方案〈type,blocks〉，提供各編碼塊的云代理節點列表nodes.

若數據訪問節點為云內計算節點（算法1 的行①），則算法AFERS 運行于協調節點上的協調組件.首先，AFERS 從協調節點上的元數據管理組件獲取數據訪問節點對應云代理節點與存儲被訪問數據的編碼塊的云代理節點間的延遲（各云代理節點定時檢測其與其他云代理節點間的延遲，并將檢測結果發往協調節點存儲），以及被訪問數據的編碼塊的信息，具體包括：存儲各編碼塊的節點、編碼塊在各節點上的存儲狀態tmp 或pinned、處于tmp 狀態的編碼塊的存入時間等（算法1 的行②③）.然后，AFERS 根據從元數據管理組件獲取的信息，計算各編碼塊的傳輸速度評分（如式（7）），并根據評分選擇編碼數據訪問方案的類型和用于重構數據的編碼塊（算法1 的行④～⑥）.

若數據訪問節點為云外計算節點（算法1 的行⑧），則算法AFERS 運行于數據訪問節點.首先，AFERS 從協調節點的元數據管理組件獲取被訪問數據對應編碼塊的信息，主要包括：存儲了被訪問數據對應pinned 狀態編碼塊的節點ID（算法1 的行⑨）.然后，如果數據訪問節點未初始化，則數據訪問節點先測試其與被訪問數據對應pinned 狀態編碼塊所在云代理節點間的延遲，并存于本地內存；如果數據訪問節點已初始化，則直接從本地內存獲得其與各pinned 狀態編碼塊所在節點間的延遲（算法1 的行⑩～?）.接著，AFERS 計算各編碼塊的傳輸速度評分（如式（11）），并根據評分選擇編碼數據訪問方案的類型type和用于重構數據的編碼塊blocks（算法1 的行?～?）.最后，AFERS 依據數據訪問節點與被訪問數據對應pinned 狀態編碼塊所在云代理節點間的延遲，選擇提供blocks中編碼塊的云代理節點（算法1的行?）.

3）算法分析

①算法AFERS 針對2 種不同類型數據訪問節點訪問數據的過程，分別設計了編碼塊傳輸速度評估模型，且評估各編碼塊傳輸速度時考慮了各緩存編碼塊的分布情況，能較為準確地評估框架IBCS 下不同類型數據訪問節點訪問數據時各編碼塊的速度.同時，AFERS 能以編碼塊傳輸速度評估值為依據制定編碼塊傳輸速度較高的編碼數據訪問方案，從而能提高不同訪問節點訪問數據的速度.

②算法AFERS 只需要測試各云代理節點和云外計算節點間的延遲，相較于現有的需要測試節點間實時帶寬、各節點實時性能的算法，AFERS 對各云代理節點的影響較低.

3.2 基于數據訪問過程感知的緩存管理算法(CADA)

1）主要思想

算法CADA 首先以數據對象為單位進行緩存管理，當決定緩存或驅逐某個數據對象后，再對該數據對象的各編碼塊進行差異化的操作， 各緩存編碼塊被切分為若干數據分片進行管理，可節省緩存空間.

①數據對象級緩存管理

當某個云代理節點對應的云內計算節點訪問數據時，算法CADA 會將該數據對象的部分編碼塊加入緩存，加入緩存的編碼塊的初始存儲狀態均為pinned.

此外，CADA 可適配任意用戶自定義的數據對象級緩存驅逐算法.當觸發緩存驅逐操作后，CADA將使用用戶自定義的緩存驅逐算法初步決定驅逐哪些數據對象的編碼塊.緩存驅逐操作一方面會定時觸發，另一方面會在剩余緩存空間不足以緩存待緩存編碼塊時觸發.

②編碼塊級緩存管理

緩存編碼塊在云代理節點的存儲空間內有pinned 和tmp 這2 種狀態.編碼塊狀態為pinned 時，存在緩存優先級（取值包括0 或1）；編碼塊為tmp 狀態時，沒有緩存優先級，且會被IPFS 組件的垃圾回收程序定時清理.tmp 狀態的編碼塊被回收之前仍保留在云代理節點上，可以作為緩存讀取.

當某個云代理節點對應的云內計算節點訪問數據時，CADA 會選擇該數據對象的部分編碼塊加入緩存，并為這些編碼塊設置緩存優先級.緩存驅逐時，首先由用戶自定義的數據對象級緩存驅逐算法決定待驅逐的數據對象，CADA 會根據緩存優先級更改pinned 緩存編碼塊的狀態.其中緩存優先級為1 的編碼塊將被設為0，仍保留pinned 狀態；緩存優先級為0 的編碼塊將被設為tmp 狀態，如圖10 所示.

圖10 CADA 編碼塊緩存狀態管理原理Fig.10 Principle of coding blocks cache state management in CADA

設置編碼塊緩存優先級的主要策略為：優先緩存易被算法AFERS 選中的編碼塊（本次訪問數據時已被AFERS 選中的編碼塊）以提高緩存的命中量；優先緩存實際傳輸速度遠低于所有被訪問編碼塊實際傳輸速度平均值的編碼塊，使得緩存命中時可通過大幅度提高各編碼塊傳輸速度的下限而大幅度縮短編碼塊傳輸用時（即緩存命中增效較大）.

因此，具體的緩存優先級設置過程為：首先，獲取被AFERS 選中的各編碼塊的實際傳輸用時，并計算出各編碼塊的實際傳輸用時的平均值和標準差 σ.然后，得到實際傳輸用時大于的編碼塊（j為經驗常量，即使用j-sigma 原則進行緩存決策），并將這些編碼塊加入緩存，其中，傳輸用時最長的編碼塊的緩存優先級將被設為1，其他編碼塊的優先級將被設為0.

③數據分片級緩存管理

加入緩存的編碼塊被劃分為若干個大小不超過256 KB 的數據分片并以Merkle DAG 組織存儲在云代理節點上，由IPFS 組件維護.緩存編碼塊（以哈希值標識）對應Merkle DAG 的一個根節點，內容為其葉節點所對應數據分片的組合.

算法CADA 通過IPFS 獲取待緩存編碼塊哈希在Merkle DAG 上末端節點的各數據分片哈希值，與本地已有分片的哈希進行比對，以判斷數據分片的命中情況.利用IPFS 的數據分片管理機制，在緩存空間中內容完全相同的數據分片僅存儲1 份，該數據分片在Merkle DAG 中指向多個包含該數據分片的頂端節點，對應不同的緩存編碼塊.數據分片級緩存管理可節省緩存空間，增加云代理節點上可緩存的編碼塊數.

2）算法描述

算法CADA 的工作流程如算法2 所示.

算法2.算法CADA.

輸入：緩存量閾值Rthreshold，用戶選擇的數據對象級緩存驅逐算法F.

算法CADA 運行于云內計算節點對應的云代理節點上，會不停阻塞讀取事件隊列中的事件（算法2的行①②），其中包括數據訪問事件和定時緩存回收事件等.

若讀取到數據訪問事件，則從事件中獲取被算法AFERS 選中的編碼塊信息，以及各編碼塊的實際傳輸用時（算法2 的行③～⑤）.然后，根據獲得的信息得到被AFERS 選中的編碼塊中傳輸用時較長的編碼塊列表slowBlocks，傳輸用時較長的編碼塊指實際傳輸用時大于的編碼塊，其中tˉ， σ分別為各編碼塊傳輸用時的平均值和標準差（算法2 的行⑥），j為經驗常量.接著，將slowBlocks中的編碼塊加入緩存，并將其中傳輸用時最長的編碼塊的緩存優先級設為1，其他編碼塊的緩存優先級設為0（算法2 的行⑦）.隨后，如果當前緩存的總數據量超過閾值，則調用用戶選擇的數據對象級緩存驅逐算法F確定擬驅逐的數據對象（算法2 的行⑧～⑩）.最后，調整擬驅逐數據對象的編碼塊的緩存優先級（將緩存優先級為1 的編碼塊的緩存優先級調為0）并將緩存優先級為0 的編碼塊設為tmp 狀態（算法2 的行?）.

若讀取到定時緩存回收事件，則調用用戶選擇的數據對象級緩存驅逐算法F確定擬驅逐的數據對象，并調整擬驅逐數據對象的編碼塊的緩存優先級（將緩存優先級為1 的編碼塊的緩存優先級調為0）并將緩存優先級為0 的編碼塊設為tmp 狀態（算法2的行?～?）.

3）算法分析

①算法CADA 選擇緩存被算法AFERS 選中且實際傳輸用時較長的編碼塊，可以提高緩存命中量和緩存命中增效，從而縮短編碼塊傳輸用時，進而提高數據訪問速度.

②算法CADA 對實際傳輸用時相對較長的編碼塊（緩存優先級為1）進行了保護，使其需要經歷2 次緩存驅逐操作且期間未被命中才會被清理，有利于提高緩存命中增效.

③不同數據對象級緩存驅逐算法適用于不同的場景，由于算法CADA 可適配用戶自定義的數據對象級緩存驅逐算法，故其適用場景較為豐富.

4 實驗與結果

4.1 原型實現

為評估方法AECAM 的性能，我們實現了一個面向跨云存算聯調的存儲系統（cross-cloud storage system for collaborative scheduling of storage and computation，C2S2），并在該系統中實現了AECAM.

C2S2 遵循基于IPFS 的跨云存儲系統框架IBCS，該框架由協調組件、元數據組件、代理組件、IPFS 組件、客戶端組成，如圖11 所示.

圖11 C2S2 各組件間消息交互示意圖Fig.11 Illustration of communications between C2S2 modules

為避免單點故障，協調組件有多個，運行于多個協調節點上.各協調組件不斷阻塞讀取競爭消息隊列中的消息，并在成功讀取消息后將其解析執行.其中，消息由客戶端寫入，包括文件寫入請求、訪問請求等.

每個云代理節點上運行一個代理組件.代理組件不斷阻塞讀取其專有消息隊列中的消息，并在成功讀取消息后將其解析執行.其中，消息由協調組件寫入，包括具體的編碼塊操作指令.此外，代理組件上運行著gRPC（Google remote procedure call）服務，負責與客戶端進行數據傳輸.

各協調節點元數據組件共同構成mysql 集群，負責存儲系統中的各類元數據：存儲服務元數據、數據對象元數據、代理節點元數據、代理節點編碼塊元數據、云內計算節點數據對象元數據、編碼塊元數據.為保證元數據安全，該mysql 集群只能被協調組件通過mysql 指令訪問.

每個云代理節點上運行一個IPFS 組件，各IPFS組件組成IPFS 集群.各IPFS 組件可被其所在云代理節點上的代理組件通過IPFS API 訪問，也可與IPFS集群中的其他IPFS 組件通過IPFS 協議共同完成編碼塊的P2P 傳輸.

4.2 實驗設置

實驗環境包括阿里云和華為云在北京和上海的3 個云數據中心的6 個節點（云主機），各云數據中心間的帶寬如圖12 所示.華為云主機配備2 核第3 代Intel 至強3.0 GHz 處理器、4 GiB 內存和40 GB 云硬盤；阿里云主機配備2 核第3 代Intel Xeon2.7 GHz 處理器，4 GiB 內存和40 GB 云硬盤.其中，節點1～5 為云代理節點，同時充當云內計算節點；節點6 為協調節點，同時充當云外計算節點.其中，華為云主機對應的云存儲服務為MinIO 對象存儲服務，阿里云主機對應的云存儲服務為OSS 對象存儲服務.

圖12 跨云實驗環境示意圖Fig.12 Illustration of cross-cloud experimental environment

為評估C2S2 的性能，我們將其與2 個引入緩存的基于糾刪碼的存儲系統Agar 和POCache 進行了對比測試.

Agar[16]默認采取直接數據訪問方案，將編碼塊的全局訪問次數與各數據訪問節點獲取該編碼塊開銷的乘積作為各數據訪問節點緩存該編碼塊的預期收益，并將預期收益較高的編碼塊緩存到對應的數據訪問節點.

POCache[15]將校驗塊緩存到數據訪問節點附近，在訪問數據時請求所有的數據塊.當訪問的數據對象存在校驗塊緩存時，POCache 同時從緩存節點請求校驗塊，等待k個編碼塊到達后采取直接或降級數據訪問方案解碼計算重構原始數據對象.

實驗采用的參數及默認值如表2 所示.

Table 2 Parameters in Experiments表2 實驗參數

緩存容量Sc是指緩存空間大小與待讀取數據對象總大小之比.

實驗中，數據對象的訪問服從Zipfian 分布[25]，少數熱點數據的訪問次數占總數據訪問次數的比例越大，Zipfian 分布的參數a越大.

數據相似度Sf是指2 個數據對象在內容上的相似程度.在本次實驗中，按照數據相似度將每2 個數據對象劃分為一個小組，小組內的2 個數據對象在內容上相似，相似度為Sf；任意小組之間的數據對象數據相似度為0.

4.3 評價指標

我們使用3 個指標來評價面向跨云存算聯調的存儲系統C2S2 的性能.

1）緩存命中量

若存儲系統以編碼塊為粒度進行緩存管理，則該存儲系統的緩存命中量HS為經過多輪數據訪問操作后被命中的緩存編碼塊的總大小HSblock；若存儲系統以數據分片為粒度進行緩存管理，則該存儲系統的緩存命中量HS為經過多輪數據訪問操作后被命中的緩存數據分片的總大小HSslice.

2）跨云傳輸量

若存儲系統以編碼塊為粒度進行緩存管理，則該存儲系統的跨云傳輸量CT為經過多輪數據訪問操作后被跨云傳輸的編碼塊的總大小CTblock；若存儲系統以數據分片為粒度進行緩存管理，則該存儲系統的跨云傳輸量CT為經過多輪數據訪問操作后被跨云傳輸的數據分片的總大小CTslice.

3）數據訪問速度

若被訪問數據大小為M，且從用戶發起數據訪問命令到云內計算節點對應的云代理節點將數據重構出來并上傳到對應的云存儲服務上所消耗的時間為t1，則云內計算節點訪問該數據的速度為M/t1；若被訪問數據大小為M，且從用戶發起數據訪問命令，到云外計算節點對應的云代理節點上將數據重構出來所消耗的時間為t2，則云外計算節點訪問該數據的速度為M/t2.

實驗中的緩存命中量、跨云傳輸量由仿真實驗測得，數據訪問用時由真實跨云環境下的實驗測得.

4.4 緩存命中量

圖13 顯示了緩存命中量隨編碼塊緩存決策所采取的j-sigma 原則中經驗常量j的變化而變化.隨著j的增加，緩存命中量逐漸上升.當j增加到3 后，緩存命中量基本上不再隨j的增加而顯著增加.因此，本文實驗中取j=3.

圖13 緩存命中量隨緩存決策j-sigma 原則的參數j 的變化Fig.13 Variation of cache hit volume with parameter j of the j-sigma caching decision principle

圖14 顯示了不同Zipfian 分布參數a下Agar，POCache，C2S2 的緩存命中量.Agar，POCache，C2S2的緩存命中量隨a的增大而增加.這是由于a越大，熱點數據訪問次數占總數據訪問次數的比例越大，因而存儲系統緩存的熱點數據的編碼塊被命中的次數越多.

圖14 不同Zipfian 分布參數a 下緩存命中量對比Fig.14 Comparison of cache hit volume under different Zipfian distribution parameter a

圖15 顯示了不同緩存容量下Agar，POCache，C2S2的緩存命中量.Agar，POCache，C2S2 的緩存命中量均隨著緩存容量的增加而增加，這是由于緩存容量越大，可緩存的編碼塊越多.

圖15 不同緩存容量下緩存命中量對比Fig.15 Comparison of cache hit volume under different cache sizes

圖16 顯示了不同編碼參數下Agar，POCache，C2S2的緩存命中量.Agar 和C2S2 的緩存命中量對編碼參數的變化不敏感，而POCache 的緩存命中量對編碼參數的變化較為敏感且其緩存命中量除編碼參數（5，3）外均低于Agar 和C2S2.這是因為POCache 僅緩存校驗塊，使得其對編碼塊中校驗塊的占比較為敏感.校驗塊占比越少，可緩存的編碼塊越少，進而可命中的編碼塊越少.

圖16 不同編碼參數下緩存命中量對比Fig.16 Comparison of cache hit volume under different encoding parameters

圖17 顯示了不同數據相似度下Agar，POCache，C2S2 的緩存命中量.C2S2 的緩存命中量隨著數據相似度的增加而增加，而Agar 和POCache 的緩存命中量幾乎不受數據相似度影響.這是由于C2S2 實現了數據分片級的緩存管理，相似數據的編碼塊中的相同數據分片僅被存儲了1 次，因而數據相似度越大，緩存空間中能存儲的編碼塊越多，使得緩存命中量越大.

總體而言，C2S2 的平均緩存命中量比Agar 和POCache 高了10.05% 和65.4%，主要原因為：1）C2S2實現了細粒度的緩存管理；2）C2S2 為各已緩存的編碼塊設置了優先級，可以更持久地保留數據訪問方案中傳輸效率低的編碼塊，有利于減少緩存抖動，提高緩存命中量；3）C2S2 可以根據實際情況緩存各類編碼塊，而POCache 只能緩存校驗塊且Agar 只能緩存數據塊.

4.5 跨云傳輸量

圖18 顯示了不同Zipfian 分布參數a下Agar，POCache，C2S2 的跨云傳輸量.Agar 和C2S2 的跨云傳輸量隨a的增大而顯著減少.這是因為參數a越大，熱點數據訪問次數占總數據訪問次數的比例越大，因而存儲系統緩存的熱點數據的編碼塊被命中的次數越多，進而從緩存中直接獲取的數據的總量越大.然而，POCache 的跨云傳輸量受a的影響較小.這是由于POCache 在訪問數據時首先訪問所有的數據塊，然后舍棄最后到達的數據塊，使得其跨云傳輸量與緩存是否命中幾乎無關.

圖18 不同Zipfian 分布參數a 下跨云傳輸量對比Fig.18 Comparison of cross-cloud transfer volume under different Zipfian distribution parameter a

圖19 顯示了不同緩存容量Sc下Agar，POCache，C2S2 的跨云傳輸量.隨著緩存容量的增大，C2S2 的跨云傳輸量有明顯下降，這是由于緩存容量越大，可緩存的編碼塊越多，緩存命中量越大.然而，POCache和Agar 的跨云傳輸量并沒有隨著緩存容量的增加而明顯下降.這是因為Agar 需要定期進行預緩存和緩存調整，帶來了額外的跨云傳輸量，而POCache 在每次訪問數據時都會請求所有的數據塊.

圖19 不同緩存容量下跨云傳輸量Fig.19 Comparison of cross-cloud transfer volume under different cache sizes

圖20 顯示了不同編碼參數下Agar，POCache，C2S2 的跨云傳輸量.三者跨云傳輸量基本上不受編碼參數的影響.這是由于C2S2，Agar 的緩存命中量對編碼參數不敏感，且POCache 在任何編碼參數下訪問數據時都會請求所有的數據塊.

圖20 不同編碼參數下跨云傳輸量對比Fig.20 Comparison of cross-cloud transfer volume under different encoding parameters

圖21 顯示了不同數據相似度Sf下Agar，POCache，C2S2 的跨云傳輸量.C2S2 的跨云傳輸量隨著數據相似度的增加而減少；Agar，POCache 的跨云傳輸量幾乎不受數據相似度影響.這是由于C2S2 實現了細粒度的緩存管理，在訪問數據時可以利用相似數據的編碼塊緩存來減少跨云傳輸量.

圖21 不同數據相似度下跨云傳輸量對比Fig.21 Comparison of cross-cloud transfer volume under different data similarity

總體而言，C2S2 的平均跨云傳輸量比Agar 和POCache 分別低了30.13% 和53.69%，主要原因為：1）C2S2 只針對讀取到的數據進行緩存，不產生額外的跨云傳輸量.2）C2S2 利用數據內容尋址機制，可以讓相似數據對象從緩存中讀取一致的數據分片，減少跨云傳輸量.

4.6 數據訪問速度

圖22 顯示了不同數據相似度下Agar，POCache，C2S2 的數據訪問速度.當數據相似度為0 時，C2S2 與POCache 和Agar 相比，可將數據訪問速度提升28.58%～33.04%.這是由于C2S2 的緩存命中量更高、緩存命中增效高，可有效降低低帶寬云間的數據傳輸量.

圖22 不同數據相似度下平均數據訪問速度Fig.22 Comparison of average data access speed under different data similarity

此外，當數據相似度為30%，60%，90%時，C2S2的數據訪問速度逐漸升高.這是由于C2S2 支持細粒度的緩存管理，在訪問數據時可以利用相似數據的編碼塊緩存來減少跨云傳輸量.

整體而言，C2S2 的數據訪問速度平均比POCache和Agar 高75.22%～81.29%.主要原因為：

1） C2S2 使用IPFS 集群從多個云代理節點以數據分片為單位并發傳輸編碼塊，能夠有效提高編碼塊傳輸速度；

2） C2S2 可以評估各編碼塊的傳輸速度，并自適應制定編碼數據訪問方案以規避傳輸速度慢的編碼塊；

3） C2S2 的緩存管理算法可對數據訪問過程進行感知，并通過設置優先級，更為持久地保留數據訪問方案中傳輸效率最低的瓶頸編碼塊，提高緩存命中增效.

5 總 結

在框架創新方面，本文提出了一種基于IPFS 的跨云存儲系統框架(IBCS)，使用IPFS 集群存儲和緩存數據，并有效利用IPFS 的數據分片管理機制實現細粒度的緩存管理，因而能提高緩存命中率.

在技術創新方面，本文提出了一種面向存算聯調的跨云糾刪碼自適應數據訪問方法(AECAM)，實現了糾刪碼編碼數據緩存管理策略與編碼數據訪問方案選擇策略深度協同優化，在選擇編碼數據訪問方案時以各編碼塊的存儲和緩存情況為依據，在設置編碼數據緩存優先級時以編碼數據訪問方案對各編碼塊的評估結果和實際傳輸時間為依據，可同時提高緩存命中量和命中增效.

在軟件實現方面，本文基于IPFS 的跨云存儲系統框架(IBCS)和面向存算聯調的跨云糾刪碼自適應數據訪問方法(AECAM)，設計實現了一種面向跨云存算聯調的存儲系統(C2S2).與現有引入緩存的基于糾刪碼的存儲系統POCache 和Agar 相比，可將數據訪問速度提高75.22%～81.29%.

未來，我們計劃進一步研究框架IBCS 的數據修復和數據更新性能優化問題.具體研究如何通過合理管理緩存編碼塊來縮短數據修復用時，以及如何利用框架IBCS 的數據分片管理機制降低數據更新開銷.

作者貢獻聲明：張凱鑫提出主要研究思路，完成實驗并撰寫論文；王意潔提出指導意見，修改和審核論文；包涵提出實驗方案，參與修改論文；闞浚暉協助完成實驗.