一種基于文件支持度的動態副本管理機制

肖中正 陳寧江 賈炅昊 張文博

1（廣西大學計算機與電子信息學院 南寧 530004）2（中國科學院軟件研究所軟件工程技術研究開發中心 北京 100190）（village．fm＠hotmail．com）

一種基于文件支持度的動態副本管理機制

肖中正1陳寧江1賈炅昊1張文博2

1（廣西大學計算機與電子信息學院 南寧 530004）
2（中國科學院軟件研究所軟件工程技術研究開發中心 北京 100190）（village．fm＠hotmail．com）

在大規模分布式存儲系統的容錯技術中，數據副本管理是一種重要機制．針對網絡環境中的動態副本管理需求，建立一種文件支持度指標及其動態計算模型．該模型通過周期性數據采集，利用文件支持度的自相關性，結合文件上一采集周期訪問量、訪問量占比、被訪問數據量以及文件級別等參數，構建了能夠較準確描述文件的動態副本需求狀態模型．通過動態適應性的參數調整以適應變化的負載狀態，使副本管理決策盡可能反映系統實際狀態．在此基礎上設計了數據結點負載均衡、副本調整、副本清理等相關算法，實現了動態副本管理的目標．通過實驗驗證了所設計的動態副本管理機制的有效性．

分布式存儲；動態副本管理；負載均衡；文件支持度；容錯

面向大規模分布式存儲系統的容錯需求，基于冗余思想的數據副本管理是常見技術．靜態的副本管理通常在數據存儲系統初始化時，預先設定相應的副本數量，或簡單地根據文件屬性給出副本創建數量的評價，但這無法應對動態環境而做出有效的負載均衡．因此，動態的數據副本管理受到更多的關注，根據系統運行時的若干參數變化觸發文件副本調整，實現系統資源的有效分配．

IanFoster［1］討論了關于高性能層次狀數據網格的動態副本及緩存策略，實現并評估了3種副本管理策略——最優客戶（best client）、級聯復制（cascading replication）、快速傳播（fast spread）．網絡帶寬在副本創建、傳輸過程起到至關重要的作用［2］，以上策略卻沒有對網絡負載進行考慮．Ranganathan等人［3］建立了一種滿足去中心化P2P環境下的動態模型驅動的副本機制．該模型下的任何結點擁有為存儲于其上的文件創建副本的權限，并且需要事先計算在其他結點創建副本的代價和獲益．這種架構較難實現全局負載均衡，只考慮副本根據參數的動態創建，而未根據參數變化對副本數量進行裁剪，可能導致存儲資源浪費和負載不均衡．Anderson等人［4］提出一種數據網格下根據數據狀態自動維護數據的動態副本創建和放置算法，根據訪問次數以及訪問時序的評價模型符合Zipf定律，但僅依賴訪問次數和時間太片面，對存儲系統的訪問具有隨機性；該算法并未提供參數修正的相關機制以及結點負載均衡的調整機制．Ding等人［5］提出了一種基于全局存儲管理、全局并行任務調度框架下的副本創建和放置算法．該框架與Hadoop平臺［6］以及Google云計算平臺［7］相似，新數據對象的創建和放置位置是基于當前工作負載和可用存儲考慮的，提出一種自我調整的數據復制算法以適應集群結點資源和數據訪問模式的變化．Andronikou等人［8］提出了基于QoS感知的副本管理機制，考慮了基礎設施的局部性、代價、網絡帶寬、文件重要程度等因素．

現有動態數據副本管理機制主要考慮的因素包括以下方面：1）動態性；2）決策計算；3）底層基礎設施架構；4）副本創建代價．在動態的分布式大數據環境中，文件系統中的數據被訪問的概率具有隨機性和突發性，并且大部分數據訪問請求的持續在線時間很短，不會長時間占用目標數據的存取權限．雖然在存儲系統中存在大量文件，但是對整個系統而言并非所有的文件都會被頻繁地訪問，根據Carns等人［9］對文件系統的分析，90%的文件在最近30d之內沒有被訪問，而55%的文件在最近64d內未被訪問．因此也需要合理地評估文件的熱度．本文在前人工作基礎上，面向動態的數據副本管理需求，設計文件支持度（file support degree）評價指標，并建立合理的基于時序的周期性計算模型以動態評價文件支持度．通過引入文件支持度計算模型及其參數動態調整，實現副本管理涉及的數據結點負載均衡、細粒度副本調整和副本清理等過程，提供了一種具有良好效果的優化方案．

1 文件支持度動態評價模型

1．1 文件支持度計算模型

定義1．副本因子（replication factor）．表示對象（文件或條塊）的當前有效副本數量，記為γ．

定義2．最小副本因子（minimum replication factor）．是系統為文件設定的副本數量下限值，記為Γ．

當文件的副本因子減小到最小副本因子時，該文件的副本量將不會繼續減少．

定義3．文件支持度（file support degree）．是對在第i個周期文件f在系統中的熱門程度的評價，記為δ（i，f）．

定義4．文件級別（file grade）．是用戶為文件設置的一個評判其重要程度，記為G，且0≤G≤1．G越大，文件越重要．

定義5．文件訪問時段．對于文件f而言，第i－1次訪問與第i次訪問之間的時間間隔為文件f的一個時段．

定義6．相關系數調整周期．對文件支持度相關的數據進行采集和計算的周期，記為τ．

事實1．在時段［tm，tn］之間，對于文件f而言，i時段文件支持度δ（i，f）與i－1時段的文件支持度δ（i－1，f）相關，并且δ（i－1，f）對δ（i，f）影響程度跟i－1時段與i時段之間的時差呈反相關，即過去越久的文件支持度相關數據對當前的計算影響越小．其中n＞m且η≤n－m≤τ，i∈［m，n］，η為最低系數樣本量，τ為相關系數調整周期．

由事實1可知，過去一個時段的文件支持度對當前文件支持度有很大影響．但是由于時段的劃分不是等時間的，因此δ（i，f）與δ（i－1，f）直接的關聯必然不是線性相關．隨著時間跨度的逐漸增大，δ（i－1，f）對δ（i，f）的影響顯然會呈現降低的趨勢［10］．由事實1以及上述分析可得式（1）：

事實2．文件f的文件支持度與過去一個相關系數調整周期的訪問量H有關，并且跟H在該周期系統平均訪問量中的占比有關．

在Web應用系統中，頁面資源的熱門程度以及訪問量是服從Zipf定律［11］的．這就意味著根據訪問量進行的頁面排名可能出現如下狀況：排名第前k位的頁面量可能僅占總資源量的1?k，甚至更少．同樣地，在存儲系統中也存在這種規律［12］：當前熱門的數據集（文件支持度高）占系統總數據量較少的一部分．而描述數據集的熱門程度顯然不是單看其當前的訪問量，還要看其排名程度．若排名越前，其訪問量占比就越大．所以，文件支持度與訪問量占比有極大關系．并且通過與平均訪問量進行對比的簡單計算方式，避免了在大量的數據集里進行排序，將會節省系統資源．根據事實2及以上相關敘述，可以得出式（2）：

式（2）表明δ（i，f）與文件訪問量的排名具有正相關性，訪問量排名越大對文件支持度影響越大；但同時也受到支持度依賴因子的約束，這是由于訪問量的時效性問題引起的，即過去時間越久的訪問量數據的參考價值越低．因此需要該依賴因子進行時效性上的限制．

事實3．文件f的文件支持度與過去一個周期被訪問的數據量的比例有關，即如果被訪問的數據量越多，表明f的文件支持度可能越高．

存儲系統中的文件數據量大小波動極大．在用戶訪問過程中可能出現2種情形：1）某時刻可能存在大量用戶訪問某個文件極少部分數據（如僅16b的標記數據），而該文件可能在GB級別；2）用戶集中訪問某文件的1B數據，但該文件只有十幾字節．顯然，用數據訪問量的大小比例來評判δ（i，f）避免了僅通過訪問次數進行評判帶來的片面性：大量訪問可能是重復訪問極少的無關緊要的數據，而這些極少的數據量訪問不會對系統造成較大壓力．因此數據訪問量也是影響文件支持度的重要因素．根據事實3和上述結論，得出式（3）：

其中，δ（i，f）是文件f于i周期的文件支持度；Hi是文件f在i周期的訪問量；Vi是文件f在i周期訪問數據量，Vf是文件總數據量．式（3）表明δ（i，f）與訪問數據量正相關，與Vf，Hi之積負相關．

事實4．文件f的文件支持度受文件級別的影響，文件級別越高，文件支持度的影響越大．

當文件資源持續被大量訪問而產生過多副本并且系統資源吃緊時，可以通過文件級別進行調控，以避免文件資源過熱而導致系統資源過度消耗的情況．根據事實4相關結論，得出式（4）：

表明用戶設置的文件級別對δ（i，f）有影響．

由式（1）～（4）可知，δ（i，f）的上一周期文件支持度、文件訪問量、文件訪問數據量以及文件級別有正相關性．因此，為描述文件支持度的影響因素，構建向量z＝（ι，υ，φ，ζ），其中各元素表示為：其中，ρδi－1，δi是i周期文件支持度與i－1周期文件支持度之間的相關系數；ρV，δ是i周期數據訪問量與文件支持度的相關系數；ρH，δ是i周期文件被訪問次數與文件支持度的相關系數；ρg，δ是文件級別與文件支持度的相關系數．

對z各個分量進行歸一化處理，采用線性函數轉換進行歸一化處理方法，將各分量值映射到［0，1］區間．由于各個分量（各個影響因素）對文件支持度的作用大小不盡相同，因此還需對各個分量進行加權計算，以區分影響力．

對δ（i－1，f）影響因素分量的歸一化處理表示為：

其中，ιmin是用于計算的連續樣本時段集內ι的最小值，ιmax是ι的最大值，ωδ是分量的影響力權重．

對數據訪問量影響因素分量υ的歸一化處理表示為：

其中，υ是連續樣本時段集中當前的時段內數據訪問量影響評價值，υmin是最小的時段評價值，υmax是最大的時段評價值，ωV是分量影響權重值．

對訪問數量影響因素分量φ的歸一化處理表示為：

其中，φmin是連續樣本時段內φ的最小值，φmax是φ的最大值，ωH是分量影響權重值．

對文件級別影響因素分量ξ的歸一化處理表示為：

其中，ξ是文件級別影響因子，ωG是分量影響權重值．

最終，得到如下的δ（i，f）計算公式：

1．2 相關系數計算及動態修正

由于帶有隨機性和時序性，δ（i，f）與δ（i－1，f）、文件訪問次數、文件數據訪問量以及文件級別之間的極小可能服從高斯分布，但是根據式（1）～（4）可知，δ（i，f）與各個影響因素成正相關．文件支持度的相關計算公式中涉及3個相關系數：ρδi，δi－1，ρV，δ和ρH，δ，常用分析變量相關性的方法有Pearson法、Spearman等．其中，Spearman相關法不僅適用于線性相關，同時也適用于非線性相關，對樣本數據是否服從正態分布無嚴格要求，也容許異常數據出現．文件支持度模型的相關系數符合Spearman相關，因此采用斯皮爾曼等級相關系數［13］（Spearman rank correlative coefficient）對變量的相關性進行評價．由斯皮爾曼等級相關系數的計算公式可知，要計算3個文件支持度相關系數，需要對過去的時段數據進行保存用作樣本．但是由于數據量巨大，不可能對所有歷史數據進行保存，因此要設定限制點，對影響力小的久遠數據進行丟棄，降低系統計算開銷．算法1描述了樣本采集以及相關系數修正的時序過程．

在算法1中，通過不斷地對文件請求進行計算，收集請求與文件支持度相關的參數，以保持樣本數據最新．但在此過程中并不是每個請求都進行文件支持度相關系數的計算，這顯然會造成系統嚴重負載．本算法在兼顧系統壓力和相關系數精確度的基礎上，周期性地對相關系數進行調整；同時把系統負載作為參考依據，動態地修正相關系數．當文件經過計算并執行了副本管理之后，導致系統負載不均衡時，將會觸發重新計算新的相關系數，以恰當描述文件支持度與各個影響因素之間的相關性．

2 動態管理過程

2．1 Data Node負載均衡

當文件f在某個數據結點上的副本數據突然收到大量訪問請求時，該數據結點將會過載，可能導致結點失效等嚴重后果．數據結點的負載均衡顯得尤為重要，由此必須對各個結點的負載狀況進行收集．各個數據結點除了與元數據服務器（metadata server，MDS）保持心跳以及存儲狀態報告之外，還需要將自身的負載信息定期發送給副本管理器．數據結點DNi的負載狀態可使用計算資源、主存、網絡資源以及持久存儲資源權衡，表示為：

其中，f（χ）表示歸一化的計算資源狀態，g（ψ）表示歸一化的主存資源狀態，h（η）表示歸一化的網絡資源狀態，z（ν）則表示歸一化的持久存儲資源狀態．

副本管理器獲取到所有數據結點的負載信息之后，可以得到數據結點集群的平均負載，如式（5）：

根據各數據結點的負載信息和集群平均負載信息，即可構建數據結點負載分群．在實際應用中，雖然某時刻所有的數據結點中必然有負載排名較高的一些結點，但并不能表明這些結點一定處于重載狀態下，因為可能當前所有結點的請求量都很少．同樣地，負載排名較后的結點也并不能表明結點一定輕載，比如當系統極度繁忙時所有結點都接受到大量請求．即便是普通情況下，連續的數據結點可能負載均衡差別極小卻被分配到不同的結點群里．因此，不能單一以負載排名順序對各個數據結點進行劃分．根據數據結點負載信息，將結點劃分為3個結點群：保持群（holding）、接收群（acceptable）和請求群（begging），分別記為DGH，DGA，DGB．DGH里的結點不允許發出任何遷移請求，同時也不接收任何遷移請求；DGA里的結點可以接收遷移請求，但不允許發出遷移請求；DGB里的結點允許發出遷移請求，但不允許接收遷移請求．對3個結點群有如下約束：

約束1．DGA和DGB可以為空，但DGH任何情況下不允許為空，并且DGA∩DGB＝ ，DGA∩DGH＝ ，DGH∩DGB＝ ．

約束1可以有效避免極端情況下大量重載結點向重載結點遷移、輕載結點向輕載結點遷移的狀況．

算法2描述了數據結點根據負載狀況進行分群的過程．它并未采用簡單的根據負載量進行絕對的劃分，而是根據集群的平均負載狀況，從中間結點進行逐個分離．首先要對結點按負載進行排序，找到最接近平均負載狀況的結點DNa，將結點加入DGH．這種做法具有合理性：對于普通情況，DNa負載適中，自然屬于保持群；當出現所有結點均為重載的時候，各結點都無法接收遷移，而又沒有接收結點，因此DNa納入保持群；當所有結點均輕載時，各結點不需要請求遷移，同時也沒有請求結點，DNa同樣也納入保持群．確定了DNa后，向高負載的逐個篩選，考察其相對于前面結點負載變化率．如果負載變化率在可接受范圍，則將其納入DGH，否則將后續結點全部納入DGB．同樣地，向低負載結點逐個考察，直到得到DGA．

通過上述分析，明確了數據結點的負載劃分．信息，若發現本結點屬于DGB，則表明結點的負載過重，需要進行副本的遷移工作．遷移的主要步驟是：將文件支持度過高的文件選出，并在DGA中創建其副本，然后釋放本地資源．在選擇創建副本的結點過程中，可能從DGA選取多個結點，而不是單個．這樣避免了遷移后導致DGA中的結點負載突然加重的情況．圖1展示了數據結點上的周期性負載均衡調度過程．在數據結點上有3個周期性計算工作：周期性向MDS發送心跳信息和狀態報告（Theartbeat）、周期性向副本管理器發送負載信息（Trm＿report）、周期性接收副本管理器的調度信息（TLB）．在TLB周期內，副本管理器獲得了所有數據結點的負載信息，并依據負載信息對數據結點進行了分群．當前結點獲取到分群

Fig．1 Periodic computation of data node．圖1 數據結點上的周期性計算

2．2 副本調整

雖然在TLB周期內可以對DGB上的數據結點的文件支持度較大文件進行副本調整，但并未從每個文件的角度去考慮．有可能在DGA和DGH都存在大量文件支持度較高、但副本因子較小的文件，還需要建立以文件支持度為驅動的數據副本調整策略，更全面保障數據結點的負載均衡．

對于文件f在相關系數調整周期T下，其支持度為δ（T，f）．為了根據文件支持度和副本因子來調節f的副本數量，定義如下調節公式：

其中，γ＊是文件f預期副本因子，Γ是最小副本因子，W是單位支持度計算窗口．

式（16）使用支持度最小的W個文件的支持度均值作為單位支持度，這樣避免僅使用單個支持度（最小支持度文件）作為單位支持度的片面影響．

得到與支持度相關的預期副本因子后，即可對文件的副本進行相應調整．算法3描述了以文件支持度為驅動的副本調整策略，它周期性地執行基于文件支持度驅動的副本調整，這個周期通常是離線的，并且是長周期，因為這種調整會消耗較多系統資源．

算法3．ADJ－SP－DRIVEN．

輸入：文件集SF，計算周期Tadj，單位支持度計算窗口W，調整文件比例P，最小副本因子Γ；

輸出：總共調整的文件數量n．

①Def n＝0；

另外，算法3并不是對所有的文件進行副本調整，而是選取支持度較高的文件進行處理，因為這些文件在當前看來價值更大．由前文分析結論知道，存儲系統的訪問規律是滿足Zipf定律的，因此支持度很高的文件只占系統的少量，在一定程度上可降低調整過程中的不必要計算．

2．3 副本清理

在連續多個TLB周期內，可能出現DGB為空的情況，但此時可能存在許多文件的副本因子很大，但是其文件支持度卻一直處于較低狀態．這種情況在系統運行一定時間之后會非常多，導致存儲資源的浪費，并給系統帶來更大的維護開銷．因此需啟動周期性清理機制，如算法4所示．

算法4同樣通過周期性的掃描，僅對低支持度的文件進行處理．目標是對空閑因子（文件支持度與歸一化副本因子的比值）較大的文件進行副本清理．而當發現文件需要清理時，將其副本因子設置為當前清理比例下所有文件支持度的均值．由于選擇清理的這些文件均為低支持度文件，選擇均值作為新副本因子是合理的．

3 測 試

本文基于HDFS［14］的實驗平臺對本文方法進行原型實驗，實驗環境的配置部署如表1所示．我們主要測試新的動態副本管理機制對存儲系統的負載均衡、存儲資源利用率、響應時間等影響，以及分析動態副本創建的代價．

Table 1 Experimental Environment Configuration表1 實驗環境配置

如圖2所示，實驗設計了4種不同的模擬集群訪問場景：1）請求量在測試周期保持高壓狀態（Trace1），模擬系統在持續高負載狀態下的訪問過程；2）請求量持續增加（Trace2），模擬系統從空閑狀態開始，用戶請求量逐漸增加，工作負載逐漸增加，進入到高負載狀態；3）請求量持續減少（Trace3），模擬是用戶請求量逐漸減少，系統進入到相對空閑狀態；4）請求量跳躍性突變（Trace4），模擬短時間內大批量的任務同時完成或者同時啟動，導致系統負載抖動厲害．每種Trace運行時間遠大于數據結點調整周期TLB、副本調整周期Tadj和副本清理周期Tclear．

Fig．2 Four kinds of system requests traces．圖2 4種系統請求場景

實驗在以上配置基礎上作了如下假設：

1）假設實驗測試期間MDS結點都是可靠的，不會發生失效事件，也不會有新的結點加入MDS集群．同樣，數據結點集群結構也保持不變，所有網絡連接安全可靠，不會發生數據丟失．

2）默認副本數量為3，將2個副本放置同一機架，而第3個副本放置于不同的遠端機架，同機架副本可以保證較快數據讀取，而遠端機架副本則起到失效恢復作用．因此實驗中的靜態副本機制的副本數量也設置為3．而對于文件支持度模型而言，初始時候假設的訪問量都很低，因此文件讀寫量很少，從而設置2個副本保證到失效恢復即可，此時無需考慮讀寫性能．隨著模型逐漸進入穩定狀態，其副本量會自動調整，以適應不同支持度的可靠性和讀寫性能．

3）數據結點集群負載均衡度計算方法為其中，L（DNi）為第i個數據結點的工作負載量，Lavg（DN）為數據結點平均工作負載量．

4）讀密集型測試過程包含主要是讀操作，隨機加入少量寫操作（約5%）．寫操作一般需要先對元數據進行查詢操作，因此假設寫密集型測試過程包含約30%的讀操作．

3．1 副本管理測試

在仿真實驗過程中，通過考察文件支持度驅動的模型平均副本數量的變化，對動態副本調整的效果進行分析和評判．數據結點集群的負載均衡直接被動態副本調整影響．當文件支持度高的文件通過副本調整機制創建額外副本后，可以降低目標數據結點工作負載，從而平衡集群工作負載．

1）副本數量動態調整測試

圖3顯示了在4種實驗場景下平均副本數量的動態調整過程．由于Trace1整個過程都是處于高請求量的狀態（圖2（a）），因此在系統初始化后馬上收到大量的數據訪問請求，導致很多文件的支持度急劇上升．但根據算法1所描述的相關系數計算過程可知，系統在初始化時的樣本數據為空，雖然文件訪問量極大，但計算得到支持度無法反映實際情況．所以在Trace1開始的短時間內都呈現平均副本因子逐漸上升，而非跳躍上升的情況．

Fig．3 Effects of dynamic replication adjustment．圖3 動態副本調整效果

其他Trace情況也一樣，只是由于訪問量變化不同導致變化幅度不同．Trace1進入穩定階段后，平均副本因子保持在很小范圍波動．當時間線在0．6左右時，出現了迅速減少的現象．這是由于在該時刻啟動了周期為Tclear的副本清理過程，導致平均副本因子出現突然的減少．過了該周期后，由于密集的訪問量到來，使得平均副本因子又開始增加，但再次到達平穩階段的大小比副本清理前要小．Trace2過了初始化后一直處于緩慢增加狀態，然后由于前段的訪問量很少，平均副本因子波動略微減少．遇到副本清理周期迅速減少，但此后由于Trace2訪問量增到非常大，逐漸進入Trace1初始化后的過程．Trace3雖然開始就收到非常大的訪問量沖擊，但逐漸減少，根據式（2）可知，大訪問量對支持度影響越來越弱．所以Trace3初始化階段只有緩慢的增加，并且此后在Γ線附近浮動．Trace4顯示的是訪問量突變的情況，包含4個突變低谷，但是圖3顯示的Trace4平均副本因子動態調整過程并沒有因為訪問量的突變而呈現跳躍性變化，這是由于支持度計算模型依賴過去一定時段的數據，并且綜合Lδ，LV，LH，LG這4種因素進行評價．

2）數據結點負載均衡測試

仿真實驗以Trace1作為測試過程，對文件支持度模型驅動的動態調整策略（SPD）、靜態副本機制（static）和無副本機制進行數據結點負載均衡效果的比較，如圖4所示．無副本機制初始化后LBD較快增加，并且出現大幅波動；整個過程沒有一個相對平穩的階段，并且LBD相比其他2個大很多，負載均衡狀況受訪問變化的影響巨大．而靜態副本機制相比無副本狀態LBD小很多，顯然是因為有多個副本可以選擇使得熱點數據請求被系統負載均衡模塊均分了．靜態副本機制有相對平穩的時段，但也出現了較多突變的狀況．SPD在初始化階段由于計算得到的相關系數失實，LBD也快速增大，甚至超過靜態策略．此后Tadj和TLB調整周期的作用，由于LBD進入相對穩定的過程，并且LBD較小，系統沒有發生巨大的負載失衡狀況．

Fig．4 Dynamic load balancing of data nodes（Trace1）．圖4 數據結點動態負載均衡（Trace1）

3）存儲利用率測試

圖5顯示了實驗過程記錄的不同Trace下各個副本機制存儲利用率的比較．顯然無副本機制在4個Trace下的平均存儲利用率都較低，Trace1最大達到18%左右，Trace3只有10%不到．靜態副本機制則比無副本機制存儲利用率高很多達到40%～50%，而具有動態調節能力的SPD比靜態策略高．對比圖3可以看出，Trace1和Trace2的平均副本因子比Trace3，Trace4高出不少；Trace2和Trace3更接近靜態副本機制．所以Trace1和Trace4的存儲利用率SPD比靜態策略高約15%，而Trace2和Trace3則僅高出5%左右．

Fig．5 Comparison of storage usage．圖5 存儲利用率比較

3．2 響應時間測試

系統響應時間的仿真設計，是通過對Trace1～Trace4測試過程記錄系統負載量與響應時間，然后將系統負載歸一化處理，并計算4個Trace響應時間的均值．測試過程分為讀密集型測試和寫密集型測試，讀密集型測試90%以上的請求量是讀請求，而寫密集測試則是90%以上的測試為寫請求．如圖6所示，在讀密集型的測試Trace中，隨著系統工作負載逐步增加，靜態策略和無副本機制系統響應時間緩慢增加；而SPD策略在測試初始化后系統工作負載不大的情況下，系統響應時間就突然增大，超過了另外二者．這是由于此時SPD啟動了副本動態創建的機制，消耗了一定的系統資源，并且此時多數文件僅有2個副本，從而導致響應時間突然激增．當初始副本創建完畢，Tadj，TLB，Tclear等周期計算完全運行起來之后，系統響應時間逐漸下降，并且此后伴隨著小幅波動一直處于平穩狀態．而無副本機制在系統負載量達到臨界值之后，系統響應時間激增，直到系統響應超時．而靜態策略同樣存在這個臨界值，只是由于具有3個副本，其臨界值出現較晚．顯然，在系統負載不斷加大情況下，對于讀密集型Trace靜態方法沒有提供自適應機制，是無法滿足性能提升需求的．

圖7反映寫密集型的Trace測試結果，顯然比讀密集型的Trace響應時間大很多．同樣剛初始化后，對于SPD策略，由于啟動副本相關機制消耗一定系統資源而導致響應時間突然增大．此后隨著系統工作負載增加，SPD策略響應時間并非如同寫密集型Trace那樣減少，而是繼續保持增加，當增加到臨界值（本實驗條件下約為0．66）后開始激增，系統響應時間越來越大．對于靜態策略，在初始化后持續增加負載期間都保持較低的響應時間，直到達到臨界值；同樣無副本機制也是在臨界值前緩慢增加，只不過其臨界值大于寫密集型時的臨界值，較早地就進入了響應時間激增階段．

Fig．6 Response time of read－intensive systems．圖6 讀密集型系統響應時間

Fig．7 Response time of write－intensive systems．圖7 寫密集型系統響應時間

從上面分析可以看出，對于讀密集型應用場景，SPD策略具有良好的系統響應能力；對于寫密集型的應用場景，在系統工作負載達到臨界值之前，SPD策略具有良好的系統性能提升，而系統負載超過該值后，SPD策略會失效．這是因為系統工作負載達到極限情況下，連續大量的寫操作會導致帶寬、I?O以及存儲空間等資源極度緊張，而可能有的結點沒有足夠的資源進行副本調整，從而導致無法完成預期的動態調整．

3．3 模型動態調整測試

由3．2節和算法1的分析得出，相關系數調整周期Tρ＿adj對系統響應時間和數據結點的負載均衡具有很大的影響．如果Tρ＿adj過小，導致短時間內系統需要消耗大量的運算資源去計算相關系數以及調整文件副本因子；而如果Tρ＿adj過大，則會導致很長時間內相關系數無法更新，這樣就無法反映出當前的系統狀態，從而導致負載失衡、系統性能下降等一系列問題．

圖8顯示了在實驗環境下，Tρ＿adj在不同取值下對系統響應時間和數據結點集群負載均衡的影響．在Tρ＿adj很小時，最能反映最新的負載狀況，并且得到最佳的副本調整結果（因此LBD很小）；隨著Tρ＿adj增大，LBD逐漸增大，因為當前的相關系數預測的系統狀態與實際情況差距越來越大．對于系統響應時間，在Tρ＿adj很小時，由于頻繁地、過多地消耗系統資源，導致其值非常大；但隨著Tρ＿adj進一步增大時，響應時間迅速降低，并達到最佳響應時間；Tρ＿adj繼續增大會出現相關系統計算出現偏差越大，系統負載均衡效果不理想，從而使得響應時間逐步增大．在圖8中，a是LBD和系統響應時間的第1個交點，b是響應時間最低點，Tρ＿adj取值［a，b］之間的任意值可以得到負載均衡和響應時間的較好平衡點．

Fig．8 Effects of adjustment cycle．圖8 調整周期變化的影響

4 討論和分析

表2從架構、可擴展性等方面將本文方法（SPD）與其他副本管理相關工作進行了定性比較．典型的副本管理架構有P2P、多層次架構、兄弟樹、圖以及一般的數據網格結構．副本創建的決策主要有集中決策和分布式決策2種方式，集中式決策會消耗較多系統資源，可能導致系統瓶頸；而分布式決策將決策計算分散到多個結點，但可能導致重復的復制．

Table 2 Comparison of Replication Management Mechanisms表2 副本管理機制定性比較

大量的動態副本機制基于閾值決策，通常選擇的決策因素有文件訪問歷史記錄、存儲余量、I?O量等．Yuan［16］的工作以各結點存儲余量和帶寬可用量作為評判因子，實現局部訪問優化．PHFS［22］擴展了快速傳播策略，通過收集文件訪問記錄，然后使用分類和聚類等數據挖掘工具找出文件聚集信息，預測文件未來文件關聯程度，以進行副本調整．該方法需要的計算量巨大，實現復雜，故對于實時性要求高的系統不適用．基于文件訪問熱度的方法有Shorfuzzaman［23］，Chang等人［24］的工作，它們在基于文件訪問量越大、未來訪問概率越大的假設前提下，定期收集訪問信息并做分析計算，然后清除這些數據開始新的周期．僅依靠文件訪問歷史數據的挖掘來預測未來文件訪問概率的方法，對于訪問過程的模型穩定的系統非常適用；但若系統訪問的隨機性大，則它們會出現預測不準確、系統資源消耗大等問題．

本文提出的SPD模型針對這些缺陷進行改進，將訪問量、訪問數據量、文件基本以及前一周期指標作為當前評價指標參考因素，周期性地對模型參數進行調整，以適應當前時段內系統訪問的分布狀態．SPD模型計算資源開銷主要通過TLB，Tadj，Tρ＿adj，Tclear等4個參數集中體現．TLB，Tadj和Tclear通常設置為較大周期，對系統實時開銷要求較小；Tρ＿adj是影響開銷最敏感的參數．由于Tρ＿adj值設置極小時會使得系統開銷巨大，但是設置過大時對系統的優化效果則極差．在實際應用系統中，測試出Tρ＿adj的平衡點區間后，將使系統副本調整效果達到最佳效果．

基于網格或P2P的架構通常適合于模型穩定的存儲系統，因為這類系統的架構對于隨機性較大的系統預測準確性低．本文所提出的動態副本管理機制，在基于決策計算、空間利用率、系統響應時間和負載均衡等因素情況下，通過自適應調整實現動態副本調整策略．實驗表明該模型的負載均衡能力較好，能夠在多種應用場景下保持穩定副本調節能力并具有較好效果．對于讀密集型的應用場景，該模型系統響應能力較好；但對于寫密集型應用，極端情況下會導致失效．

5 結束語

本文在基于文件熱度的動態副本機制相關研究成果上，提出基于文件支持度的自適應副本管理機制．主要貢獻在于：1）建立了文件支持度的計算模型，在此基礎上，從數據結點層次提出了數據結點分群方法，以有助于提供副本數據結點的負載均衡能力；2）從文件的角度提出以文件支持度為驅動的副本調整、副本清理等副本管理算法，通過周期性對文件副本因子等因素進行優化，以達到更佳的效果．通過實驗驗證了本文提出的方法在讀密集型的應用場景下性能良好．未來的工作將針對寫密集型的應用表現欠佳的問題，將讀?寫操作量加入模型，研究根據讀?寫場景調整副本決策改進機制．

［1］IanFoster K R．Design and evaluation of dynamic replication strategies for a high－performance data grid［C］??Proc of Int Conf on Computing in High Energy and Nuclear Physics．Philadelphia，PA：IOP Publishing，2001：1 16

［2］Sashi K，Thanamani A S．A new replica creation and placement algorithm for data grid environment［C］??Proc of the 2010Int Conf on Data Storage and Data Engineering．Los Alamitos，CA：IEEE Computer Society，2010：265 269

［3］Ranganathan K，Iamnitchi A，Foster I．Improving data availability through dynamic model－driven replication in large peer－to－peer communities［C］??Proc of the 2nd IEEE?ACM Int Symp on Cluster Computing and the Grid．Los Alamitos，CA：IEEE Computer Society，2002：376 376

［4］Anderson E．Capture，Conversion，and Analysis of an Intense NFS Workload［C］??Proc of the 7th USENIX Conf on File and Storage Technologies．Berkeley，CA：USENIX，2009：139 152

［5］Ding Ying，Lu Ying．Automatic data placement and replication in grids［C］??Proc of the Int Conf on High Performance Computing．Los Alamitos，CA：IEEE Computer Society，2009：30 39

［6］Taylor R C．An overview of the Hadoop?MapReduce?HBase framework and its current applications in bioinformatics［J］．BMC Bioinformatics，2010，11（S1）：1 6

［7］Ghemawat S，Gobioff H，Leung S T．The Google file system［C］??Proc of the 19th ACM Symp on Operating Systems Principles．New York：ACM，2003：29 43

［8］Andronikou V，Mamouras K，Tserpes K，et al．Dynamic QoS－aware data replication in grid environments based on data“importance”［J］．Future Generation Computer Systems，2012，28（3）：544 553

［9］Carns P，Harms K，Allcock W，et al．Understanding and improving computational science storage access through continuous characterization［J］．ACM Trans on Storage，2011，7（3）：1 25

［10］Hua Y，Jiang H，Zhu Y，et al．SmartStore：A new metadata organization paradigm with semantic－awareness for nextgeneration file systems［C］??Proc of the Conf on High Performance Computing Networking，Storage and Analysis．New York：ACM，2009：1 12

［11］Almeida V，Bestavros A，Crovella M，et al．Characterizing reference locality in the WWW［C］??Proc of the 4th Int Conf on Parallel and Distributed Information Systems．Los Alamitos，CA：IEEE Computer Society，1996：92 103

［12］Rabinovich M，Rabinovich I，Rajaraman R，et al．A dynamic object replication and migration protocol for an Internet hosting service［C］??Proc of the 19th IEEE Int Conf on Distributed Computing Systems．Los Alamitos，CA：IEEE Computer Society，1999：101 113

［13］Gong Shuming，Zhu Hailing．Applied Statistics［M］．3rd ed．Beijing：China WaterPower Press，2010（in Chinese）（龔曙明，朱海玲．應用統計學［M］．3版．北京：中國水利水電出版社，2010）

［14］Kuang H，Radia S，Shvachko K．The Hadoop distributed file system［C］??Proc of 2010IEEE?NASA Goddard Conf on Mass Storage Systems and Technologies．Los Alamitos，CA：IEEE Computer Society，2010：1 10

［15］Abdullah A，Othman M，Ibrahim H，et al．Decentralized replication strategies for P2Pbased scientific data grid［C］?? Proc of the 2008Int Symp on Information Technology．Los Alamitos，CA：IEEE Computer Society，2008：1 8

［16］Yuan Yulai，Wu Yongwei，Yang Guangwen，et al．Dynamic data replication based on local optimization principle in data grid［C］??Proc of the 6th Int Conf on Grid and Cooperative Computing．Los Alamitos，CA：IEEE Computer Society，2007：815 822

［17］Rasool Q，Li Jianzhong，Zhang Shuo．Replica placement in multi－tier data grid［C］??Proc of the 8th IEEE Int Conf on Dependable，Autonomic and Secure Computing．Los Alamitos，CA：IEEE Computer Society，2009：103 108

［18］Lei Ming，Vrbsky S V，Hong Xiaoyan．An on－line replication strategy to increase availability in data grids［J］．Future Generation Computer Systems，2008，24（2）：85 98

［19］Pérez J M，García－Carballeira F，Carretero J，et al．Branch replication scheme：A new model for data replication in large scale data grids［J］．Future Generation Computer Systems，2010，26（1）：12 20

［20］Sashi K，Thanamani A S．Dynamic replication in a data grid using a modified BHR region based algorithm［J］．Future Generation Computer Systems，2011，27（2）：202 210

［21］Bsoul M，Al－Khasawneh A，Abdallah E E，et al．Enhanced fast spread replication strategy for data grid［J］．Journal of Network and Computer Applications，2011，34（2）：575 580

［22］Khanli L M，Isazadeh A，Shishavan T N．PHFS：A dynamic replication method，to decrease access latency in the multitier data grid［J］．Future Generation Computer Systems，2011，27（3）：233 244

［23］Shorfuzzaman M，Graham P，Eskicioglu R．Popularitydriven dynamic replica placement in hierarchical data grids［C］??Proc of the 9th Int Conf on Parallel and Distributed Computing，Applications and Technologies．Los Alamitos，CA：IEEE Computer Society，2008：524 531

［24］Chang R S，Chang H P．A dynamic data replication strategy using access－weights in data grids［J］．The Journal of Supercomputing，2008，45（3）：277 295

Xiao Zhongzheng，born in 1988．Received his bachelor degree in Guangxi University．His main research interests include distributed computing and software engineering．

Chen Ningjiang，born in 1975．Professor and PhD．His main research interests include distributed computing and software engineering．

Jia Jionghao，born in 1989．Received his bachelor degree in Taiyuan University of Technology．His main research interests include distributed computing and software engineering．

Zhang Wenbo，born in 1976．PhD．Professor and senior engineer．His main research interests include distributed computing and software engineering

A Dynamic Replica Management Mechanism Based on File Support Degree

Xiao Zhongzheng1，Chen Ningjiang1，Jia Jionghao1，and Zhang Wenbo21（School of Computer and Electronic Information，Guangxi University，Nanning530004）2（Technology Center of Software Engineering，Institute of Software，Chinese Academy of Sciences，Beijing100190）

Replication－based management schema is an important fault tolerance mechanism in large scale distributed storage systems．In response to the demand of dynamic replication management in distributed storage systems，a file popularity index named file support degree and its computation model are proposed．Within this model，file s parameters are periodically collected．By combination of self－correlation of file support degree，file hits in previous collection cycle，accessed data volume and file s grade，a model that exactly reflects files replication requirement is built．To adapt to the variable system load，the model dynamically adjusts its parameters，making the replication decisionmaking to reflect real system status．Based on these work，some algorithms like load balancing，replication adjustment and replication clearing are designed．To avoid a single data storage node being overloaded，a data storage nodes load－balance strategy is proposed．In this strategy，data storage nodes are divided into 3groups：a holding group，an acceptable group and a begging group．There are 2periodic procedures in the system，including replication adjusting procedure and replication clearing procedure．In replication adjusting procedure，top Pfiles are replicated to data storage nodes selected based on the load－balance strategy．Replication clearing procedure is a long－periodic procedure，because it needs many adjusting procedures to make the begging group be empty．This dynamic replication management mechanism is proven effective through the given experimentations．

distributed storage；dynamic replication management；load balancing；file support degree；fault tolerance

TP391

2014－12－08；

2015－03－19

國家自然科學基金項目（61063012，61363003）；國家科技支撐計劃基金項目（2015BAH55F02）；廣西自然科學基金項目（2012GXNSFAA053222）；廣西高校優秀人才資助計劃項目（［2011］40）；廣西科學研究與技術開發計劃項目（桂科軟13180015，桂科攻1348020－7）

This work was supported by the National Natural Science Foundation of China（61063012，61363003），the National Key Technology Research and Development Program of China（2015BAH55F02），the Natural Science Foundation of Guangxi（2012GXNSFAA053222），the Talents Grants Program in Colleges and Universities of Guangxi（［2011］40），and the Scientific Research and Technological Development Program of Guangxi（桂科軟13180015，桂科攻1348020－7）．

陳寧江（chnj＠gxu．edu．cn）