面向存算聯(lián)調(diào)的跨云糾刪碼自適應(yīng)數(shù)據(jù)訪問方法

張凱鑫 王意潔 包 涵 闞浚暉

（并行與分布計(jì)算全國重點(diǎn)實(shí)驗(yàn)室（國防科技大學(xué)） 長沙 410073）

（國防科技大學(xué)計(jì)算機(jī)學(xué)院 長沙 410073）

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

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

由于云間網(wǎng)絡(luò)帶寬通常遠(yuǎn)低于云內(nèi)網(wǎng)絡(luò)帶寬，而基于糾刪碼的跨云數(shù)據(jù)訪問方法需要跨多個(gè)云傳輸編碼塊.因此，基于糾刪碼的跨云數(shù)據(jù)訪問方法的編碼塊傳輸用時(shí)通常較長，使得其數(shù)據(jù)訪問速度較慢.

基于糾刪碼的跨云數(shù)據(jù)訪問方法主要可從2 個(gè)方面來縮短編碼塊傳輸用時(shí)：

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

2）合理緩存編碼塊[14-20].基于糾刪碼的跨云數(shù)據(jù)訪問方法可通過把常被訪問的編碼塊緩存在相應(yīng)的數(shù)據(jù)訪問節(jié)點(diǎn)附近，以縮短整體的編碼塊傳輸用時(shí).

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

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

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

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

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

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

然后，在框架IBCS 下，本文提出了一種面向存算聯(lián)調(diào)的跨云糾刪碼自適應(yīng)數(shù)據(jù)訪問方法（adaptive erasure-coded data access method for cross-cloud collaborative scheduling of storage and computation，AECAM），可通過協(xié)同優(yōu)化緩存管理與編碼數(shù)據(jù)訪問方案提高緩存命中量和緩存命中增效.具體提出2 個(gè)關(guān)鍵算法：

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

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

1 相關(guān)工作

1.1 糾刪碼數(shù)據(jù)訪問方案

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

1）直接數(shù)據(jù)訪問方案

如圖1 所示，直接數(shù)據(jù)訪問方案是指數(shù)據(jù)訪問節(jié)點(diǎn)直接獲取被訪問數(shù)據(jù)對象的k個(gè)數(shù)據(jù)塊，然后將它們重組成被訪問數(shù)據(jù)對象.直接訪問方式無需進(jìn)行解碼運(yùn)算且實(shí)現(xiàn)簡單，因而大部分分布式存儲(chǔ)系統(tǒng)（GFS（Google file system）[3]，Lustre[4]，Ceph[5]等）均默認(rèn)采用這種數(shù)據(jù)訪問方式.

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

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

2）降級數(shù)據(jù)訪問方案

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

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

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

1.2 廣域糾刪碼數(shù)據(jù)訪問技術(shù)

在廣域部署的基于糾刪碼的存儲(chǔ)系統(tǒng)（如基于糾刪碼的跨云存儲(chǔ)系統(tǒng)）進(jìn)行數(shù)據(jù)訪問時(shí)，通常需要在低帶寬鏈路上傳輸大量編碼塊，導(dǎo)致編碼塊傳輸速度成為了數(shù)據(jù)訪問的瓶頸.為此，研究者提出了一系列廣域糾刪碼數(shù)據(jù)訪問技術(shù)，主要分為基于數(shù)據(jù)訪問方案優(yōu)化的廣域糾刪碼數(shù)據(jù)訪問技術(shù)和基于緩存的廣域糾刪碼數(shù)據(jù)訪問技術(shù).

1）基于數(shù)據(jù)訪問方案優(yōu)化的廣域糾刪碼訪問技術(shù)

基于數(shù)據(jù)訪問方案優(yōu)化的廣域糾刪碼訪問技術(shù)的基本思想是：傳統(tǒng)分布式存儲(chǔ)系統(tǒng)默認(rèn)采用直接數(shù)據(jù)訪問方案，因?yàn)槠溆?jì)算量較小.然而，在廣域環(huán)境中，不同域的節(jié)點(diǎn)間的數(shù)據(jù)傳輸速度遠(yuǎn)低于域內(nèi)節(jié)點(diǎn)間的數(shù)據(jù)傳輸速度，且不同域節(jié)點(diǎn)的I/O 性能差異較大.如果數(shù)據(jù)訪問節(jié)點(diǎn)與大量數(shù)據(jù)塊存儲(chǔ)節(jié)點(diǎn)屬于不同的域或者大量數(shù)據(jù)塊存儲(chǔ)節(jié)點(diǎn)的I/O 性能較低，則會(huì)導(dǎo)致必須訪問數(shù)據(jù)塊的直接數(shù)據(jù)訪問方案的傳輸開銷大于某些降級數(shù)據(jù)訪問方案.因此，基于數(shù)據(jù)訪問方案優(yōu)化的廣域糾刪碼訪問技術(shù)會(huì)綜合評估各編碼塊存儲(chǔ)節(jié)點(diǎn)和客戶端間的帶寬、各編碼塊存儲(chǔ)節(jié)點(diǎn)的綜合性能，求得效率較高的數(shù)據(jù)訪問方案.

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

2）基于緩存的廣域糾刪碼數(shù)據(jù)訪問技術(shù)

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

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

整體而言，現(xiàn)有基于數(shù)據(jù)訪問方案優(yōu)化的廣域糾刪碼訪問技術(shù)和基于緩存的廣域糾刪碼數(shù)據(jù)訪問技術(shù)均可提高廣域環(huán)境（含跨云環(huán)境）下的糾刪碼數(shù)據(jù)訪問效率，但存在2 點(diǎn)不足：首先，現(xiàn)有工作中的緩存管理優(yōu)化與編碼數(shù)據(jù)訪問方案優(yōu)化結(jié)合不緊密，未同時(shí)做到根據(jù)緩存編碼塊分布情況決定數(shù)據(jù)訪問方案、根據(jù)數(shù)據(jù)訪問方案制定策略決定編碼塊緩存優(yōu)先級，導(dǎo)致其緩存命中量和緩存命中增效仍有待提高.此外，現(xiàn)有工作為優(yōu)化緩存管理與編碼數(shù)據(jù)訪問方案，通常需要耗費(fèi)較多額外的計(jì)算、網(wǎng)絡(luò)、存儲(chǔ)資源以采集、維護(hù)存儲(chǔ)節(jié)點(diǎn)狀態(tài)信息及各類節(jié)點(diǎn)間的網(wǎng)絡(luò)信息.

1.3 星際文件系統(tǒng)

星際文件系統(tǒng)是一個(gè)去中心化的分布式文件系統(tǒng)[21-23]，基于分布式哈希表（distributed Hash table，DHT）、BitTorrent 點(diǎn)對點(diǎn)文件共享協(xié)議、Git 分布式版本控制、Merkle DAG 等已有技術(shù)，實(shí)現(xiàn)了數(shù)據(jù)的分片存儲(chǔ)、內(nèi)容尋址及點(diǎn)對點(diǎn)（peer-to-peer，P2P）高速傳輸.

1）數(shù)據(jù)分片存儲(chǔ)

IPFS 將用戶數(shù)據(jù)分為若干個(gè)大小不超過256 KB的數(shù)據(jù)分片，并使用Merkle DAG 來組織各個(gè)存儲(chǔ)節(jié)點(diǎn)上的數(shù)據(jù)分片.如圖3 所示，Merkle DAG 的末端節(jié)點(diǎn)的內(nèi)容為各個(gè)數(shù)據(jù)分片，其他節(jié)點(diǎn)的內(nèi)容為其所有子節(jié)點(diǎn)的內(nèi)容組合的哈希值.

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

此外，Merkle DAG 的每個(gè)頂端節(jié)點(diǎn)對應(yīng)一個(gè)數(shù)據(jù)對象，該數(shù)據(jù)對象的內(nèi)容為其子孫節(jié)點(diǎn)中末端節(jié)點(diǎn)內(nèi)容（數(shù)據(jù)分片）的組合.

分片存儲(chǔ)數(shù)據(jù)并使用Merkle DAG 來維護(hù)數(shù)據(jù)對象和數(shù)據(jù)分片間的關(guān)系的主要優(yōu)點(diǎn)是：在同一IPFS存儲(chǔ)節(jié)點(diǎn)上，多份用戶數(shù)據(jù)對象均含有的數(shù)據(jù)分片只需要被實(shí)際存儲(chǔ)1 份，因而可顯著降低存儲(chǔ)開銷.

2）數(shù)據(jù)內(nèi)容尋址

在IPFS 中，每份用戶數(shù)據(jù)對象對應(yīng)于一個(gè)Merkle DAG 的根哈希，且每個(gè)數(shù)據(jù)分片的哈希也由Merkle DAG 維護(hù).此外，IPFS 采用了分布式哈希表，支持任意IPFS 節(jié)點(diǎn)通過哈希值定位到維護(hù)了指定用戶數(shù)據(jù)對象的Merkle DAG 的節(jié)點(diǎn)，以及存儲(chǔ)了指定數(shù)據(jù)分片的節(jié)點(diǎn).

因此，在IPFS 中，訪問數(shù)據(jù)的基本過程有4 個(gè)：

①數(shù)據(jù)訪問節(jié)點(diǎn)向IPFS 集群發(fā)送需訪問數(shù)據(jù)對象的根哈希，IPFS 集群通過查詢分布式哈希表定位到維護(hù)了被請求數(shù)據(jù)對象的Merkle DAG 的節(jié)點(diǎn)，并將相應(yīng)的Merkle DAG 傳輸?shù)綌?shù)據(jù)訪問節(jié)點(diǎn).

②數(shù)據(jù)訪問節(jié)點(diǎn)根據(jù)接收到的Merkle DAG 解析出被訪問數(shù)據(jù)的各數(shù)據(jù)分片的哈希.

③數(shù)據(jù)訪問節(jié)點(diǎn)向IPFS 集群發(fā)送需訪問數(shù)據(jù)對象的各數(shù)據(jù)分片的哈希，IPFS 集群通過查詢分布式哈希表定位到存儲(chǔ)了這些數(shù)據(jù)分片的節(jié)點(diǎn)，并將這些數(shù)據(jù)分片傳輸?shù)綌?shù)據(jù)訪問節(jié)點(diǎn).

④數(shù)據(jù)訪問節(jié)點(diǎn)根據(jù)接收到的Merkle DAG 和數(shù)據(jù)分片，構(gòu)造出被訪問的數(shù)據(jù).

3） P2P 高速傳輸

在IPFS 中，數(shù)據(jù)訪問節(jié)點(diǎn)會(huì)同時(shí)請求多個(gè)數(shù)據(jù)分片且可能有多個(gè)存儲(chǔ)節(jié)點(diǎn)上擁有部分或全部被請求的數(shù)據(jù)分片.因此，IPFS 采用以BitSwap[24]數(shù)據(jù)交換協(xié)議為核心的P2P 傳輸技術(shù)，根據(jù)節(jié)點(diǎn)信用分、性能、負(fù)載、網(wǎng)絡(luò)狀況等因素選擇各數(shù)據(jù)分片的提供節(jié)點(diǎn)，并從多個(gè)提供節(jié)點(diǎn)并行地向數(shù)據(jù)訪問節(jié)點(diǎn)發(fā)送其請求數(shù)據(jù)的各數(shù)據(jù)分片，從而顯著提高數(shù)據(jù)傳輸速度.

此外，IPFS 具有緩存機(jī)制，各節(jié)點(diǎn)會(huì)將請求過的數(shù)據(jù)分片緩存在本地一段時(shí)間.期間，如果其他節(jié)點(diǎn)請求這些數(shù)據(jù)分片，該節(jié)點(diǎn)仍能將緩存的數(shù)據(jù)分片提供出去，以提高其他節(jié)點(diǎn)的數(shù)據(jù)訪問速度.

最后，在IPFS 的BitSwap 協(xié)議中，引入了信用機(jī)制，根據(jù)各節(jié)點(diǎn)對外提供數(shù)據(jù)的情況為其評定信用分.對外提供數(shù)據(jù)越頻繁的節(jié)點(diǎn)的信用分越高，而信用分越高的節(jié)點(diǎn)需要數(shù)據(jù)時(shí)會(huì)有更多的節(jié)點(diǎn)向其提供數(shù)據(jù).在各節(jié)點(diǎn)屬于不同主體的場景下（如跨云存儲(chǔ)場景），這種信用機(jī)制可以促進(jìn)各主體積極對外提供數(shù)據(jù)，進(jìn)而提高IPFS 系統(tǒng)的整體數(shù)據(jù)訪問速度.

2 基于IPFS 的跨云存儲(chǔ)系統(tǒng)框架(IBCS)

本節(jié)提出了框架IBCS，可基于IPFS 的分片存儲(chǔ)、內(nèi)容尋址及P2P 傳輸?shù)燃夹g(shù)，實(shí)現(xiàn)細(xì)粒度緩存管理和高速編碼塊傳輸.

2.1 體系結(jié)構(gòu)

如圖4 所示，框架IBCS 由讀寫控制層、存儲(chǔ)傳輸層和數(shù)據(jù)服務(wù)層組成.

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

1）讀寫控制層包含協(xié)調(diào)節(jié)點(diǎn)和多個(gè)云代理節(jié)點(diǎn)，主要負(fù)責(zé)響應(yīng)客戶端請求，完成用戶數(shù)據(jù)的寫入和訪問，具體工作由協(xié)調(diào)節(jié)點(diǎn)上的協(xié)調(diào)組件、云代理節(jié)點(diǎn)上的代理組件和元數(shù)據(jù)管理組件完成：

①協(xié)調(diào)組件負(fù)責(zé)解析用戶命令，生成寫入、訪問過程的控制命令，并發(fā)往代理組件；

②代理組件負(fù)責(zé)執(zhí)行協(xié)調(diào)組件發(fā)送的命令，包括調(diào)用IPFS 組件向IPFS 集群寫入編碼塊或從IPFS集群讀取編碼塊、對編碼塊進(jìn)行解碼操作、將解碼編碼塊得到的數(shù)據(jù)上傳到各云存儲(chǔ)服務(wù)或傳輸?shù)皆仆庥?jì)算節(jié)點(diǎn)；

③元數(shù)據(jù)管理組件負(fù)責(zé)維護(hù)用戶、數(shù)據(jù)對象、編碼塊、云代理、云存儲(chǔ)服務(wù)等元數(shù)據(jù).

2）存儲(chǔ)傳輸層由各云代理節(jié)點(diǎn)構(gòu)成，主要負(fù)責(zé)在各云代理節(jié)點(diǎn)上的存儲(chǔ)空間中存儲(chǔ)管理用戶數(shù)據(jù)對象的編碼塊，并在各云代理節(jié)點(diǎn)之間傳輸這些編碼塊，具體工作由各云代理節(jié)點(diǎn)上的代理組件和IPFS組件完成：

①代理組件負(fù)責(zé)調(diào)用IPFS 組件，完成本節(jié)點(diǎn)上持久化存儲(chǔ)編碼塊及緩存編碼塊的讀出、寫入和狀態(tài)變更；

②各IPFS 組件及各云代理的存儲(chǔ)空間構(gòu)成了IPFS集群，負(fù)責(zé)持久化存儲(chǔ)或緩存編碼塊、執(zhí)行代理組件命令、從IPFS 集群中讀取編碼塊、向IPFS 集群寫入編碼塊、利用P2P 技術(shù)在不同云的代理節(jié)點(diǎn)間高效傳輸編碼塊.

3）數(shù)據(jù)服務(wù)層為各個(gè)云的云存儲(chǔ)服務(wù)（可被各云代理節(jié)點(diǎn)訪問），將用戶數(shù)據(jù)對象存儲(chǔ)到云存儲(chǔ)服務(wù)后，同一云上的計(jì)算節(jié)點(diǎn)才能正常訪問該數(shù)據(jù)對象.

2.2 工作原理

框架IBCS 的核心工作原理包括數(shù)據(jù)寫入原理、數(shù)據(jù)訪問原理、存儲(chǔ)狀態(tài)管理原理和緩存實(shí)現(xiàn)原理.

1）數(shù)據(jù)寫入

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

圖5 IBCS 數(shù)據(jù)寫入方案Fig.5 IBCS data write scheme

2）數(shù)據(jù)訪問

在框架IBCS 中，有2 種節(jié)點(diǎn)可能需要訪問數(shù)據(jù)：云內(nèi)計(jì)算節(jié)點(diǎn)和云外計(jì)算節(jié)點(diǎn).

如圖6 所示，云內(nèi)計(jì)算節(jié)點(diǎn)可高效訪問其所在云的云存儲(chǔ)服務(wù)中的數(shù)據(jù).云內(nèi)計(jì)算節(jié)點(diǎn)需要訪問數(shù)據(jù)的過程為：首先，客戶端向協(xié)調(diào)節(jié)點(diǎn)發(fā)送數(shù)據(jù)訪問請求；然后，協(xié)調(diào)節(jié)點(diǎn)根據(jù)客戶端請求，擬制數(shù)據(jù)訪問方案并生成控制命令發(fā)送云內(nèi)計(jì)算節(jié)點(diǎn)對應(yīng)的云代理節(jié)點(diǎn)；隨后，接收到命令的云代理節(jié)點(diǎn)從IPFS 集群讀出待訪問數(shù)據(jù)對象的編碼塊，解碼出原始數(shù)據(jù)，并上傳到對應(yīng)的云存儲(chǔ)服務(wù).

圖6 IBCS 數(shù)據(jù)訪問方案（云內(nèi)計(jì)算節(jié)點(diǎn)）Fig.6 IBCS data access scheme(in-cloud nodes)

云外計(jì)算節(jié)點(diǎn)無權(quán)限訪問或不可高效訪問云存儲(chǔ)服務(wù).如圖7 所示，云外計(jì)算節(jié)點(diǎn)訪問數(shù)據(jù)的過程為：首先，云外計(jì)算節(jié)點(diǎn)（運(yùn)行著客戶端）向協(xié)調(diào)節(jié)點(diǎn)發(fā)送請求，獲取其所需數(shù)據(jù)的編碼塊的云代理節(jié)點(diǎn)信息；然后，云外計(jì)算節(jié)點(diǎn)擬制數(shù)據(jù)訪問方案并向各代理節(jié)點(diǎn)請求編碼塊；隨后，各代理節(jié)點(diǎn)將編碼塊從IPFS 集群中讀出后，發(fā)送給云外計(jì)算節(jié)點(diǎn)；最后，云外計(jì)算節(jié)點(diǎn)將收到的編碼塊解碼為所需數(shù)據(jù).

圖7 IBCS 數(shù)據(jù)訪問方案（云外計(jì)算節(jié)點(diǎn)）Fig.7 IBCS data access scheme(nodes outside the cloud)

3）存儲(chǔ)狀態(tài)管理

在框架IBCS 中，各云代理節(jié)點(diǎn)上由IPFS 組件維護(hù)的存儲(chǔ)空間既是編碼塊的持久化存儲(chǔ)空間，又是編碼塊的緩存空間.

IPFS 組件維護(hù)的存儲(chǔ)空間中的編碼塊有長期存儲(chǔ)（pinned）和臨時(shí)存儲(chǔ)（tmp）兩種狀態(tài).處于tmp 狀態(tài)的編碼塊會(huì)被IPFS 組件的垃圾回收程序定時(shí)清理，處于pinned 狀態(tài)的編碼塊則不被垃圾回收程序清理.

代理組件向IPFS 集群寫入編碼塊時(shí)，為了最大化數(shù)據(jù)容錯(cuò)度，通常避免將一個(gè)條帶上的編碼塊及其副本分配至同一個(gè)云代理節(jié)點(diǎn)上，以確保單一節(jié)點(diǎn)失效時(shí)同一數(shù)據(jù)對象的編碼塊中最多一個(gè)編碼塊受到影響.圖8 說明了IBCS 編碼塊存儲(chǔ)狀態(tài)的變化，寫入的編碼塊會(huì)默認(rèn)以pinned 的狀態(tài)存儲(chǔ)在代理組件所在云代理節(jié)點(diǎn)的存儲(chǔ)空間中，直到維護(hù)該存儲(chǔ)空間的IPFS 組件接收到改變該編碼塊狀態(tài)的unpin命令.代理節(jié)點(diǎn)從IPFS 集群讀取的編碼塊，會(huì)以tmp的狀態(tài)存儲(chǔ)在代理組件所在代理節(jié)點(diǎn)的存儲(chǔ)空間中，直到維護(hù)該存儲(chǔ)空間的IPFS 組件啟動(dòng)垃圾回收策略.此外，如果某云代理節(jié)點(diǎn)上的IPFS 組件接收到請求某個(gè)編碼塊的pin 命令，IPFS 集群使用P2P 傳輸技術(shù)將該編碼塊傳輸?shù)皆撛拼砉?jié)點(diǎn)上的存儲(chǔ)空間中并設(shè)置為pinned 狀態(tài).

圖8 IBCS 編碼塊存儲(chǔ)狀態(tài)管理原理Fig.8 Principle of coding blocks storage state management in IBCS

因此，通過對各IPFS 組件發(fā)送pin 命令和unpin命令，可以實(shí)現(xiàn)編碼塊存儲(chǔ)狀態(tài)的靈活管理.

4）緩存實(shí)現(xiàn)

在框架IBCS 中，持久化存儲(chǔ)的編碼塊和緩存編碼塊均存儲(chǔ)在各云代理節(jié)點(diǎn)的存儲(chǔ)空間，如表1 所示.其中，持久化存儲(chǔ)的編碼塊一直處于pinned 狀態(tài)；緩存編碼塊可能處于pinned 狀態(tài)，也可能處于tmp 狀態(tài)，二者間的轉(zhuǎn)換由運(yùn)行的代理組件控制.

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

2.3 框架分析

框架IBCS 的主要特點(diǎn)有4 個(gè)方面：

1）利用IPFS 的數(shù)據(jù)分片管理機(jī)制實(shí)現(xiàn)了緩存數(shù)據(jù)的細(xì)粒度管理，可從2 個(gè)方面提高緩存命中量.一方面，利用IPFS 的數(shù)據(jù)分片管理機(jī)制避免在同一云代理節(jié)點(diǎn)上存儲(chǔ)重復(fù)的數(shù)據(jù)分片，因而能降低存儲(chǔ)開銷，進(jìn)而增加了各云代理節(jié)點(diǎn)可緩存的編碼塊數(shù)；另一方面，數(shù)據(jù)分片管理機(jī)制使得未命中緩存編碼塊中的命中數(shù)據(jù)分片可以被利用起來，如圖9 所示.

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

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

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

4）針對云內(nèi)計(jì)算節(jié)點(diǎn)和云外計(jì)算節(jié)點(diǎn)，分別設(shè)計(jì)了不同的數(shù)據(jù)訪問流程，適用范圍較廣.

3 面向存算聯(lián)調(diào)的跨云糾刪碼自適應(yīng)數(shù)據(jù)訪問方法(AECAM)

第2 節(jié)提出了一種基于IPFS 的跨云存儲(chǔ)系統(tǒng)框架(IBCS).基于IBCS，本節(jié)提出一種面向存算聯(lián)調(diào)的跨云糾刪碼自適應(yīng)數(shù)據(jù)訪問方法(AECAM)，可通過協(xié)同優(yōu)化緩存管理與數(shù)據(jù)訪問方案減少數(shù)據(jù)訪問過程中的編碼塊傳輸用時(shí).

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

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

3.1 編碼數(shù)據(jù)訪問方案自適應(yīng)制定算法(AFERS)

1）核心思想

算法AFERS 首先針對云內(nèi)計(jì)算節(jié)點(diǎn)訪問數(shù)據(jù)和云外計(jì)算節(jié)點(diǎn)訪問數(shù)據(jù)2 種場景，分別建模評估編碼塊傳輸速度.然后，AFERS 可根據(jù)各編碼塊傳輸速度的評估值制定編碼數(shù)據(jù)訪問方案.

①編碼塊傳輸速度評估

算法AFERS 將數(shù)據(jù)訪問節(jié)點(diǎn)區(qū)分為云內(nèi)計(jì)算節(jié)點(diǎn)和云外計(jì)算節(jié)點(diǎn)2 種，并根據(jù)框架IBCS 中將數(shù)據(jù)傳輸?shù)? 類數(shù)據(jù)訪問節(jié)點(diǎn)的具體過程，使用不同的模型來評估這2 類數(shù)據(jù)訪問節(jié)點(diǎn)訪問數(shù)據(jù)時(shí)的編碼塊傳輸速度.

(i)云內(nèi)計(jì)算節(jié)點(diǎn)訪問數(shù)據(jù)時(shí)的編碼塊傳輸速度評估

在框架IBCS 中，云內(nèi)計(jì)算節(jié)點(diǎn)需要訪問數(shù)據(jù)時(shí)，編碼塊通過P2P 傳輸技術(shù)被傳輸?shù)綌?shù)據(jù)訪問節(jié)點(diǎn)所對應(yīng)的云代理節(jié)點(diǎn)，然后該云代理節(jié)點(diǎn)會(huì)用接收到的編碼塊解碼出原始數(shù)據(jù)對象，并將原始數(shù)據(jù)對象上傳到需訪問數(shù)據(jù)的云內(nèi)計(jì)算節(jié)點(diǎn)（數(shù)據(jù)訪問節(jié)點(diǎn)）可訪問的云存儲(chǔ)服務(wù).

上述過程中，影響編碼塊傳輸速度的主要因素包括P2P 網(wǎng)絡(luò)中存儲(chǔ)了各編碼塊的云代理節(jié)點(diǎn)數(shù)，以及這些云代理節(jié)點(diǎn)與數(shù)據(jù)訪問節(jié)點(diǎn)對應(yīng)云代理節(jié)點(diǎn)間的實(shí)時(shí)帶寬.P2P 網(wǎng)絡(luò)中實(shí)際存儲(chǔ)待傳輸編碼塊的云代理節(jié)點(diǎn)數(shù)越多，編碼塊傳輸速度越快；這些云代理節(jié)點(diǎn)與數(shù)據(jù)訪問節(jié)點(diǎn)對應(yīng)云代理節(jié)點(diǎn)間的實(shí)時(shí)帶寬越高，編碼塊傳輸速度越快.

因此，若令b為待傳輸編碼塊，c為數(shù)據(jù)訪問節(jié)點(diǎn)對應(yīng)的云代理節(jié)點(diǎn)（編碼塊的傳輸目的地節(jié)點(diǎn)），Eb,c為將編碼塊b傳輸?shù)侥康牡毓?jié)點(diǎn)c的速度，qb為存儲(chǔ)編碼塊b的云代理節(jié)點(diǎn)數(shù)，xb,i(i∈[1,qb])為第i個(gè)存儲(chǔ)了編碼塊b的云代理節(jié)點(diǎn)的序號，Bc,xb,i為序號為xb,i的云代理節(jié)點(diǎn)與傳輸目的地節(jié)點(diǎn)c間的實(shí)時(shí)帶寬，則有

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

由于IPFS 會(huì)定時(shí)觸發(fā)垃圾回收任務(wù)刪除處于tmp 狀態(tài)的編碼塊，因此，若令I(lǐng)PFS 觸發(fā)垃圾回收任務(wù)的周期為T，節(jié)點(diǎn)Nodeyb,i上的編碼塊b處于tmp 狀態(tài)的時(shí)長為tb,yb,i，則該節(jié)點(diǎn)上編碼塊b未被回收（實(shí)際存在）的概率為

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

最后，由于測量節(jié)點(diǎn)間實(shí)時(shí)帶寬的開銷較大，算法AFERS 使用節(jié)點(diǎn)間延遲來估算帶寬，具體估算方法為：

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

因此，算法AFERS 在訪問數(shù)據(jù)前，用式（7）為各編碼塊評分，當(dāng)傳輸目的地云代理節(jié)點(diǎn)為c時(shí)，編碼塊b的傳輸速度評分為Sb,c：

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

（ii）云外計(jì)算節(jié)點(diǎn)訪問數(shù)據(jù)時(shí)的編碼塊傳輸速度評估

在框架IBCS 中，云外計(jì)算節(jié)點(diǎn)需要訪問數(shù)據(jù)時(shí)，編碼塊通過TCP 協(xié)議直接從特定云代理節(jié)點(diǎn)傳輸?shù)叫枰L問數(shù)據(jù)的云外計(jì)算節(jié)點(diǎn)（數(shù)據(jù)訪問節(jié)點(diǎn)），并由數(shù)據(jù)訪問節(jié)點(diǎn)將編碼塊解碼為原始數(shù)據(jù)對象.

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

此外，算法AFERS 使用節(jié)點(diǎn)間延遲來估算帶寬，具體估算方法為：

其中Do,zb,i為Nodezb,i與計(jì)算節(jié)點(diǎn)o間的傳輸延遲.綜上可得

因此，算法AFERS 在訪問數(shù)據(jù)前，用式(11)為各編碼塊評分，當(dāng)傳輸目的地計(jì)算節(jié)點(diǎn)為o時(shí)，編碼塊b的傳輸速度評分為Sb,o：

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

②編碼數(shù)據(jù)訪問方案制定

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

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

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

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

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

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

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

(iii)提供編碼塊的云代理節(jié)點(diǎn)選擇

當(dāng)數(shù)據(jù)訪問節(jié)點(diǎn)為云內(nèi)計(jì)算節(jié)點(diǎn)時(shí)，該計(jì)算節(jié)點(diǎn)對應(yīng)的云代理節(jié)點(diǎn)只需要提供各需傳輸編碼塊的根哈希，相應(yīng)的編碼塊即可通過P2P 傳輸技術(shù)傳輸?shù)皆撛拼砉?jié)點(diǎn)上，因而此時(shí)無需選擇提供各編碼塊的云代理節(jié)點(diǎn).

當(dāng)數(shù)據(jù)訪問節(jié)點(diǎn)為云外計(jì)算節(jié)點(diǎn)時(shí)，則需要從存儲(chǔ)了需傳輸編碼塊的各云代理節(jié)點(diǎn)中，選擇與計(jì)算節(jié)點(diǎn)間的網(wǎng)絡(luò)延遲最小的云代理節(jié)點(diǎn)作為提供該編碼塊的節(jié)點(diǎn).

2）算法描述

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

算法1.算法AFERS.

輸入：數(shù)據(jù)訪問節(jié)點(diǎn)accessNode，訪問數(shù)據(jù)IDdataID；

輸出：編碼數(shù)據(jù)訪問方案〈type,blocks〉，提供各編碼塊的云代理節(jié)點(diǎn)列表nodes.

若數(shù)據(jù)訪問節(jié)點(diǎn)為云內(nèi)計(jì)算節(jié)點(diǎn)（算法1 的行①），則算法AFERS 運(yùn)行于協(xié)調(diào)節(jié)點(diǎn)上的協(xié)調(diào)組件.首先，AFERS 從協(xié)調(diào)節(jié)點(diǎn)上的元數(shù)據(jù)管理組件獲取數(shù)據(jù)訪問節(jié)點(diǎn)對應(yīng)云代理節(jié)點(diǎn)與存儲(chǔ)被訪問數(shù)據(jù)的編碼塊的云代理節(jié)點(diǎn)間的延遲（各云代理節(jié)點(diǎn)定時(shí)檢測其與其他云代理節(jié)點(diǎn)間的延遲，并將檢測結(jié)果發(fā)往協(xié)調(diào)節(jié)點(diǎn)存儲(chǔ)），以及被訪問數(shù)據(jù)的編碼塊的信息，具體包括：存儲(chǔ)各編碼塊的節(jié)點(diǎn)、編碼塊在各節(jié)點(diǎn)上的存儲(chǔ)狀態(tài)tmp 或pinned、處于tmp 狀態(tài)的編碼塊的存入時(shí)間等（算法1 的行②③）.然后，AFERS 根據(jù)從元數(shù)據(jù)管理組件獲取的信息，計(jì)算各編碼塊的傳輸速度評分（如式（7）），并根據(jù)評分選擇編碼數(shù)據(jù)訪問方案的類型和用于重構(gòu)數(shù)據(jù)的編碼塊（算法1 的行④～⑥）.

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

3）算法分析

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

②算法AFERS 只需要測試各云代理節(jié)點(diǎn)和云外計(jì)算節(jié)點(diǎn)間的延遲，相較于現(xiàn)有的需要測試節(jié)點(diǎn)間實(shí)時(shí)帶寬、各節(jié)點(diǎn)實(shí)時(shí)性能的算法，AFERS 對各云代理節(jié)點(diǎn)的影響較低.

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

1）主要思想

算法CADA 首先以數(shù)據(jù)對象為單位進(jìn)行緩存管理，當(dāng)決定緩存或驅(qū)逐某個(gè)數(shù)據(jù)對象后，再對該數(shù)據(jù)對象的各編碼塊進(jìn)行差異化的操作， 各緩存編碼塊被切分為若干數(shù)據(jù)分片進(jìn)行管理，可節(jié)省緩存空間.

①數(shù)據(jù)對象級緩存管理

當(dāng)某個(gè)云代理節(jié)點(diǎn)對應(yīng)的云內(nèi)計(jì)算節(jié)點(diǎn)訪問數(shù)據(jù)時(shí)，算法CADA 會(huì)將該數(shù)據(jù)對象的部分編碼塊加入緩存，加入緩存的編碼塊的初始存儲(chǔ)狀態(tài)均為pinned.

此外，CADA 可適配任意用戶自定義的數(shù)據(jù)對象級緩存驅(qū)逐算法.當(dāng)觸發(fā)緩存驅(qū)逐操作后，CADA將使用用戶自定義的緩存驅(qū)逐算法初步?jīng)Q定驅(qū)逐哪些數(shù)據(jù)對象的編碼塊.緩存驅(qū)逐操作一方面會(huì)定時(shí)觸發(fā)，另一方面會(huì)在剩余緩存空間不足以緩存待緩存編碼塊時(shí)觸發(fā).

②編碼塊級緩存管理

緩存編碼塊在云代理節(jié)點(diǎn)的存儲(chǔ)空間內(nèi)有pinned 和tmp 這2 種狀態(tài).編碼塊狀態(tài)為pinned 時(shí)，存在緩存優(yōu)先級（取值包括0 或1）；編碼塊為tmp 狀態(tài)時(shí)，沒有緩存優(yōu)先級，且會(huì)被IPFS 組件的垃圾回收程序定時(shí)清理.tmp 狀態(tài)的編碼塊被回收之前仍保留在云代理節(jié)點(diǎn)上，可以作為緩存讀取.

當(dāng)某個(gè)云代理節(jié)點(diǎn)對應(yīng)的云內(nèi)計(jì)算節(jié)點(diǎn)訪問數(shù)據(jù)時(shí)，CADA 會(huì)選擇該數(shù)據(jù)對象的部分編碼塊加入緩存，并為這些編碼塊設(shè)置緩存優(yōu)先級.緩存驅(qū)逐時(shí)，首先由用戶自定義的數(shù)據(jù)對象級緩存驅(qū)逐算法決定待驅(qū)逐的數(shù)據(jù)對象，CADA 會(huì)根據(jù)緩存優(yōu)先級更改pinned 緩存編碼塊的狀態(tài).其中緩存優(yōu)先級為1 的編碼塊將被設(shè)為0，仍保留pinned 狀態(tài)；緩存優(yōu)先級為0 的編碼塊將被設(shè)為tmp 狀態(tài)，如圖10 所示.

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

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

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

③數(shù)據(jù)分片級緩存管理

加入緩存的編碼塊被劃分為若干個(gè)大小不超過256 KB 的數(shù)據(jù)分片并以Merkle DAG 組織存儲(chǔ)在云代理節(jié)點(diǎn)上，由IPFS 組件維護(hù).緩存編碼塊（以哈希值標(biāo)識）對應(yīng)Merkle DAG 的一個(gè)根節(jié)點(diǎn)，內(nèi)容為其葉節(jié)點(diǎn)所對應(yīng)數(shù)據(jù)分片的組合.

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

2）算法描述

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

算法2.算法CADA.

輸入：緩存量閾值Rthreshold，用戶選擇的數(shù)據(jù)對象級緩存驅(qū)逐算法F.

算法CADA 運(yùn)行于云內(nèi)計(jì)算節(jié)點(diǎn)對應(yīng)的云代理節(jié)點(diǎn)上，會(huì)不停阻塞讀取事件隊(duì)列中的事件（算法2的行①②），其中包括數(shù)據(jù)訪問事件和定時(shí)緩存回收事件等.

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

若讀取到定時(shí)緩存回收事件，則調(diào)用用戶選擇的數(shù)據(jù)對象級緩存驅(qū)逐算法F確定擬驅(qū)逐的數(shù)據(jù)對象，并調(diào)整擬驅(qū)逐數(shù)據(jù)對象的編碼塊的緩存優(yōu)先級（將緩存優(yōu)先級為1 的編碼塊的緩存優(yōu)先級調(diào)為0）并將緩存優(yōu)先級為0 的編碼塊設(shè)為tmp 狀態(tài)（算法2的行?～?）.

3）算法分析

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

②算法CADA 對實(shí)際傳輸用時(shí)相對較長的編碼塊（緩存優(yōu)先級為1）進(jìn)行了保護(hù)，使其需要經(jīng)歷2 次緩存驅(qū)逐操作且期間未被命中才會(huì)被清理，有利于提高緩存命中增效.

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

4 實(shí)驗(yàn)與結(jié)果

4.1 原型實(shí)現(xiàn)

為評估方法AECAM 的性能，我們實(shí)現(xiàn)了一個(gè)面向跨云存算聯(lián)調(diào)的存儲(chǔ)系統(tǒng)（cross-cloud storage system for collaborative scheduling of storage and computation，C2S2），并在該系統(tǒng)中實(shí)現(xiàn)了AECAM.

C2S2 遵循基于IPFS 的跨云存儲(chǔ)系統(tǒng)框架IBCS，該框架由協(xié)調(diào)組件、元數(shù)據(jù)組件、代理組件、IPFS 組件、客戶端組成，如圖11 所示.

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

為避免單點(diǎn)故障，協(xié)調(diào)組件有多個(gè)，運(yùn)行于多個(gè)協(xié)調(diào)節(jié)點(diǎn)上.各協(xié)調(diào)組件不斷阻塞讀取競爭消息隊(duì)列中的消息，并在成功讀取消息后將其解析執(zhí)行.其中，消息由客戶端寫入，包括文件寫入請求、訪問請求等.

每個(gè)云代理節(jié)點(diǎn)上運(yùn)行一個(gè)代理組件.代理組件不斷阻塞讀取其專有消息隊(duì)列中的消息，并在成功讀取消息后將其解析執(zhí)行.其中，消息由協(xié)調(diào)組件寫入，包括具體的編碼塊操作指令.此外，代理組件上運(yùn)行著gRPC（Google remote procedure call）服務(wù)，負(fù)責(zé)與客戶端進(jìn)行數(shù)據(jù)傳輸.

各協(xié)調(diào)節(jié)點(diǎn)元數(shù)據(jù)組件共同構(gòu)成mysql 集群，負(fù)責(zé)存儲(chǔ)系統(tǒng)中的各類元數(shù)據(jù)：存儲(chǔ)服務(wù)元數(shù)據(jù)、數(shù)據(jù)對象元數(shù)據(jù)、代理節(jié)點(diǎn)元數(shù)據(jù)、代理節(jié)點(diǎn)編碼塊元數(shù)據(jù)、云內(nèi)計(jì)算節(jié)點(diǎn)數(shù)據(jù)對象元數(shù)據(jù)、編碼塊元數(shù)據(jù).為保證元數(shù)據(jù)安全，該mysql 集群只能被協(xié)調(diào)組件通過mysql 指令訪問.

每個(gè)云代理節(jié)點(diǎn)上運(yùn)行一個(gè)IPFS 組件，各IPFS組件組成IPFS 集群.各IPFS 組件可被其所在云代理節(jié)點(diǎn)上的代理組件通過IPFS API 訪問，也可與IPFS集群中的其他IPFS 組件通過IPFS 協(xié)議共同完成編碼塊的P2P 傳輸.

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

實(shí)驗(yàn)環(huán)境包括阿里云和華為云在北京和上海的3 個(gè)云數(shù)據(jù)中心的6 個(gè)節(jié)點(diǎn)（云主機(jī)），各云數(shù)據(jù)中心間的帶寬如圖12 所示.華為云主機(jī)配備2 核第3 代Intel 至強(qiáng)3.0 GHz 處理器、4 GiB 內(nèi)存和40 GB 云硬盤；阿里云主機(jī)配備2 核第3 代Intel Xeon2.7 GHz 處理器，4 GiB 內(nèi)存和40 GB 云硬盤.其中，節(jié)點(diǎn)1～5 為云代理節(jié)點(diǎn)，同時(shí)充當(dāng)云內(nèi)計(jì)算節(jié)點(diǎn)；節(jié)點(diǎn)6 為協(xié)調(diào)節(jié)點(diǎn)，同時(shí)充當(dāng)云外計(jì)算節(jié)點(diǎn).其中，華為云主機(jī)對應(yīng)的云存儲(chǔ)服務(wù)為MinIO 對象存儲(chǔ)服務(wù)，阿里云主機(jī)對應(yīng)的云存儲(chǔ)服務(wù)為OSS 對象存儲(chǔ)服務(wù).

圖12 跨云實(shí)驗(yàn)環(huán)境示意圖Fig.12 Illustration of cross-cloud experimental environment

為評估C2S2 的性能，我們將其與2 個(gè)引入緩存的基于糾刪碼的存儲(chǔ)系統(tǒng)Agar 和POCache 進(jìn)行了對比測試.

Agar[16]默認(rèn)采取直接數(shù)據(jù)訪問方案，將編碼塊的全局訪問次數(shù)與各數(shù)據(jù)訪問節(jié)點(diǎn)獲取該編碼塊開銷的乘積作為各數(shù)據(jù)訪問節(jié)點(diǎn)緩存該編碼塊的預(yù)期收益，并將預(yù)期收益較高的編碼塊緩存到對應(yīng)的數(shù)據(jù)訪問節(jié)點(diǎn).

POCache[15]將校驗(yàn)塊緩存到數(shù)據(jù)訪問節(jié)點(diǎn)附近，在訪問數(shù)據(jù)時(shí)請求所有的數(shù)據(jù)塊.當(dāng)訪問的數(shù)據(jù)對象存在校驗(yàn)塊緩存時(shí)，POCache 同時(shí)從緩存節(jié)點(diǎn)請求校驗(yàn)塊，等待k個(gè)編碼塊到達(dá)后采取直接或降級數(shù)據(jù)訪問方案解碼計(jì)算重構(gòu)原始數(shù)據(jù)對象.

實(shí)驗(yàn)采用的參數(shù)及默認(rèn)值如表2 所示.

Table 2 Parameters in Experiments表2 實(shí)驗(yàn)參數(shù)

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

實(shí)驗(yàn)中，數(shù)據(jù)對象的訪問服從Zipfian 分布[25]，少數(shù)熱點(diǎn)數(shù)據(jù)的訪問次數(shù)占總數(shù)據(jù)訪問次數(shù)的比例越大，Zipfian 分布的參數(shù)a越大.

數(shù)據(jù)相似度Sf是指2 個(gè)數(shù)據(jù)對象在內(nèi)容上的相似程度.在本次實(shí)驗(yàn)中，按照數(shù)據(jù)相似度將每2 個(gè)數(shù)據(jù)對象劃分為一個(gè)小組，小組內(nèi)的2 個(gè)數(shù)據(jù)對象在內(nèi)容上相似，相似度為Sf；任意小組之間的數(shù)據(jù)對象數(shù)據(jù)相似度為0.

4.3 評價(jià)指標(biāo)

我們使用3 個(gè)指標(biāo)來評價(jià)面向跨云存算聯(lián)調(diào)的存儲(chǔ)系統(tǒng)C2S2 的性能.

1）緩存命中量

若存儲(chǔ)系統(tǒng)以編碼塊為粒度進(jìn)行緩存管理，則該存儲(chǔ)系統(tǒng)的緩存命中量HS為經(jīng)過多輪數(shù)據(jù)訪問操作后被命中的緩存編碼塊的總大小HSblock；若存儲(chǔ)系統(tǒng)以數(shù)據(jù)分片為粒度進(jìn)行緩存管理，則該存儲(chǔ)系統(tǒng)的緩存命中量HS為經(jīng)過多輪數(shù)據(jù)訪問操作后被命中的緩存數(shù)據(jù)分片的總大小HSslice.

2）跨云傳輸量

若存儲(chǔ)系統(tǒng)以編碼塊為粒度進(jìn)行緩存管理，則該存儲(chǔ)系統(tǒng)的跨云傳輸量CT為經(jīng)過多輪數(shù)據(jù)訪問操作后被跨云傳輸?shù)木幋a塊的總大小CTblock；若存儲(chǔ)系統(tǒng)以數(shù)據(jù)分片為粒度進(jìn)行緩存管理，則該存儲(chǔ)系統(tǒng)的跨云傳輸量CT為經(jīng)過多輪數(shù)據(jù)訪問操作后被跨云傳輸?shù)臄?shù)據(jù)分片的總大小CTslice.

3）數(shù)據(jù)訪問速度

若被訪問數(shù)據(jù)大小為M，且從用戶發(fā)起數(shù)據(jù)訪問命令到云內(nèi)計(jì)算節(jié)點(diǎn)對應(yīng)的云代理節(jié)點(diǎn)將數(shù)據(jù)重構(gòu)出來并上傳到對應(yīng)的云存儲(chǔ)服務(wù)上所消耗的時(shí)間為t1，則云內(nèi)計(jì)算節(jié)點(diǎn)訪問該數(shù)據(jù)的速度為M/t1；若被訪問數(shù)據(jù)大小為M，且從用戶發(fā)起數(shù)據(jù)訪問命令，到云外計(jì)算節(jié)點(diǎn)對應(yīng)的云代理節(jié)點(diǎn)上將數(shù)據(jù)重構(gòu)出來所消耗的時(shí)間為t2，則云外計(jì)算節(jié)點(diǎn)訪問該數(shù)據(jù)的速度為M/t2.

實(shí)驗(yàn)中的緩存命中量、跨云傳輸量由仿真實(shí)驗(yàn)測得，數(shù)據(jù)訪問用時(shí)由真實(shí)跨云環(huán)境下的實(shí)驗(yàn)測得.

4.4 緩存命中量

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

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

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

圖14 不同Zipfian 分布參數(shù)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 顯示了不同編碼參數(shù)下Agar，POCache，C2S2的緩存命中量.Agar 和C2S2 的緩存命中量對編碼參數(shù)的變化不敏感，而POCache 的緩存命中量對編碼參數(shù)的變化較為敏感且其緩存命中量除編碼參數(shù)（5，3）外均低于Agar 和C2S2.這是因?yàn)镻OCache 僅緩存校驗(yàn)塊，使得其對編碼塊中校驗(yàn)塊的占比較為敏感.校驗(yàn)塊占比越少，可緩存的編碼塊越少，進(jìn)而可命中的編碼塊越少.

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

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

總體而言，C2S2 的平均緩存命中量比Agar 和POCache 高了10.05% 和65.4%，主要原因?yàn)椋?）C2S2實(shí)現(xiàn)了細(xì)粒度的緩存管理；2）C2S2 為各已緩存的編碼塊設(shè)置了優(yōu)先級，可以更持久地保留數(shù)據(jù)訪問方案中傳輸效率低的編碼塊，有利于減少緩存抖動(dòng)，提高緩存命中量；3）C2S2 可以根據(jù)實(shí)際情況緩存各類編碼塊，而POCache 只能緩存校驗(yàn)塊且Agar 只能緩存數(shù)據(jù)塊.

4.5 跨云傳輸量

圖18 顯示了不同Zipfian 分布參數(shù)a下Agar，POCache，C2S2 的跨云傳輸量.Agar 和C2S2 的跨云傳輸量隨a的增大而顯著減少.這是因?yàn)閰?shù)a越大，熱點(diǎn)數(shù)據(jù)訪問次數(shù)占總數(shù)據(jù)訪問次數(shù)的比例越大，因而存儲(chǔ)系統(tǒng)緩存的熱點(diǎn)數(shù)據(jù)的編碼塊被命中的次數(shù)越多，進(jìn)而從緩存中直接獲取的數(shù)據(jù)的總量越大.然而，POCache 的跨云傳輸量受a的影響較小.這是由于POCache 在訪問數(shù)據(jù)時(shí)首先訪問所有的數(shù)據(jù)塊，然后舍棄最后到達(dá)的數(shù)據(jù)塊，使得其跨云傳輸量與緩存是否命中幾乎無關(guān).

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

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

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

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

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

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

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

總體而言，C2S2 的平均跨云傳輸量比Agar 和POCache 分別低了30.13% 和53.69%，主要原因?yàn)椋?）C2S2 只針對讀取到的數(shù)據(jù)進(jìn)行緩存，不產(chǎn)生額外的跨云傳輸量.2）C2S2 利用數(shù)據(jù)內(nèi)容尋址機(jī)制，可以讓相似數(shù)據(jù)對象從緩存中讀取一致的數(shù)據(jù)分片，減少跨云傳輸量.

4.6 數(shù)據(jù)訪問速度

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

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

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

整體而言，C2S2 的數(shù)據(jù)訪問速度平均比POCache和Agar 高75.22%～81.29%.主要原因?yàn)椋?/p>

1） C2S2 使用IPFS 集群從多個(gè)云代理節(jié)點(diǎn)以數(shù)據(jù)分片為單位并發(fā)傳輸編碼塊，能夠有效提高編碼塊傳輸速度；

2） C2S2 可以評估各編碼塊的傳輸速度，并自適應(yīng)制定編碼數(shù)據(jù)訪問方案以規(guī)避傳輸速度慢的編碼塊；

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

5 總 結(jié)

在框架創(chuàng)新方面，本文提出了一種基于IPFS 的跨云存儲(chǔ)系統(tǒng)框架(IBCS)，使用IPFS 集群存儲(chǔ)和緩存數(shù)據(jù)，并有效利用IPFS 的數(shù)據(jù)分片管理機(jī)制實(shí)現(xiàn)細(xì)粒度的緩存管理，因而能提高緩存命中率.

在技術(shù)創(chuàng)新方面，本文提出了一種面向存算聯(lián)調(diào)的跨云糾刪碼自適應(yīng)數(shù)據(jù)訪問方法(AECAM)，實(shí)現(xiàn)了糾刪碼編碼數(shù)據(jù)緩存管理策略與編碼數(shù)據(jù)訪問方案選擇策略深度協(xié)同優(yōu)化，在選擇編碼數(shù)據(jù)訪問方案時(shí)以各編碼塊的存儲(chǔ)和緩存情況為依據(jù)，在設(shè)置編碼數(shù)據(jù)緩存優(yōu)先級時(shí)以編碼數(shù)據(jù)訪問方案對各編碼塊的評估結(jié)果和實(shí)際傳輸時(shí)間為依據(jù)，可同時(shí)提高緩存命中量和命中增效.

在軟件實(shí)現(xiàn)方面，本文基于IPFS 的跨云存儲(chǔ)系統(tǒng)框架(IBCS)和面向存算聯(lián)調(diào)的跨云糾刪碼自適應(yīng)數(shù)據(jù)訪問方法(AECAM)，設(shè)計(jì)實(shí)現(xiàn)了一種面向跨云存算聯(lián)調(diào)的存儲(chǔ)系統(tǒng)(C2S2).與現(xiàn)有引入緩存的基于糾刪碼的存儲(chǔ)系統(tǒng)POCache 和Agar 相比，可將數(shù)據(jù)訪問速度提高75.22%～81.29%.

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

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