基于協調器與遺傳算法的云存儲數據復制策略

魏秀然，王 峰

（1.河南農業大學 信息與管理科學學院，鄭州 450046；2.華北水利水電大學 信息工程學院，鄭州 450045）

0 概述

云計算利用互聯網提供計算資源和可伸縮存儲［1-2］功能，用戶可以通過云計算在任何地點使用這些服務。目前不同的學科領域都使用到大量的數據，因此，云服務憑借其靈活性和透明性被廣泛用于數據管理和基于數據的服務功能。對于如數據云這種大規模分布式環境，有效的數據管理是一個關鍵問題［3］，這可以通過復制數據來實現。在許多學科中，數據容量以兆字節和千兆字節表示，數據復制是管理這種大數據一種有效的技術。數據復制有許多優勢，如對數據的更多訪問、更小的訪問延遲和更高的可用性。

為獲得有效的數據復制，需要解決以下2 個重要問題：第1 個問題是在每個數據中應生成多少副本來滿足系統的需要，副本數量越大，系統存儲和使用所需的空間和能量就越多，并且固定數量的副本并不是獲得數據有效復制的合適選擇，如Google 文件系統（Google File System，GFS）、Hadoop 分布式文件系統（Hadoop Distributed File System，HDFS）、Amazon 簡單存儲服務（Amazon Simple Storing Service，S3）等云存儲系統都采用3 份數據副本；第2 個問題是每個副本應放置在何處，以便更快地執行任務，并確保負荷以平衡的方式分配。上述2 個問題構成了數據復制問題。

現有數據復制策略大多存在數據可用性低、副本數量多、請求時延高等不足。對此，本文基于數據功能，提出一種高效的數據復制策略，在考慮服務質量（Quality of Service，QoS）功能需求的同時，還考慮一個查詢中數據塊的物理位置，以獲得更好的復制參數，即更少的副本數量、更高的可用性和更快的響應。

1 相關工作

目前針對數據復制問題的諸多研究，較少有針對一次查詢數據塊的物理鄰接問題，多數集中于可用性、快速響應和有效功能等參數上，為獲得這些參數的最優值，應考慮用戶所使用數據的物理位置。然而，很多研究忽略了需要存儲的副本數量。系統中一個數據集的副本數量越大，所使用的資源（如存儲容量和能量）就越多。因此，應盡量減少系統中的副本數量，以避免資源浪費。

復制在萬維網（World Wide Web，WWW）［4］、對等網絡［5］、Ad Hoc 和傳感器網絡中的應用被得到廣泛研究［6-8］。近年來，隨著諸如網格［9］、云［10-11］等大規模分布式系統的出現，復制已成為一個新的研究主題。

數據復制技術可分為靜態和動態兩大類。在靜態復制中，主機的副本和節點數量是預先確定的；而在動態復制中，副本的數量和位置則根據用戶的資源需求和智能訪問模式的變化來確定。

文獻［12］提出一種用于分布式復制的靜態算法。該算法考慮了決策中的3 個重要因素，首先選擇一些服務提供商來承載副本，然后考慮此類服務提供商的數據副本較少，最后考慮負荷的分配，即選擇服務提供商的方式是將副本分發到整個機架上。文獻［13］提出的靜態副本放置算法通過優化平均響應時間將副本放置到站點上，并提出一種動態副本維護算法，如果性能指標在最后K個時間段內顯著下降，則將副本重新分配給新的候選站點。

文獻［14］介紹各種數據中心的選擇和復制策略，在此基礎上提出一種數據中心選擇和動態數據復制的兩階段系統模型，目的是有效提高數據的可用性，減少用戶等待時間。文獻［15］為實現減少能耗和縮短任務執行時間的綠色云計算目標，將遺傳算法（Genetic Algorithm，GA）和蟻群算法相結合，提出一種兩者動態融合的任務調度算法。該文利用遺傳算法全局搜索能力強的優點尋找任務調度的較優解，并將較優解轉化為蟻群的初始信息，再通過蟻群算法的蟻群信息交流和正反饋機制尋找任務調度問題的最優解。文獻［16］針對移動云計算中的虛擬機（Virtual Machine，VM）調度問題，考慮無線帶寬限制對VM 調度的影響，以云提供商的系統效益為目標函數，根據拍賣機制提出一種帶寬受限的VM 動態調度（Bandwidth-constrainted VM Dynamic Scheduling，BVMDS）算法。該算法首先根據用戶的出價來判定拍賣成功方，然后根據拍賣成功方對計算資源的需求來配置VM，最后采用臨界支付的方式來計算拍賣成功方的實際支付價格。實驗結果表明，BVMDS 算法能夠有效提高云提供商的系統效益和資源利用率。文獻［17］提出一種動態合成協議，以高效的方式合成具有樹結構的網格網絡，并基于樹的高度、深度和每個節點中的滑塊數創建一個靈活的拓撲結構。在該協議中，為保持數據的兼容性，可以很容易地恢復讀/寫和寫/寫的行為。文獻［18］引入了一種可靠經濟的數據管理機制，通過控制活躍副本來減少系統中的副本數量，從而減少使用的緩存空間。文獻［19］提出一種將數據項放置在最好的服務提供商中的方法，其中每個客戶端都可以查閱最近的服務中心來訪問其數據。文獻［20］提出2 個探索性算法來逐步刪除和添加數據副本，同時考慮了每個查詢QoS，并且通過忽略數據中心所使用的能量優化了系統的效率，但該文沒有考慮系統中所使用的能量。

2 系統模型與優化目標

2.1 系統模型

本文模型的數據存儲由一些集群構成，集群以高效的方式共享資源，這些資源的主要組成部分是分布式文件系統，如Hadoop 分布式文件系統、Amazon S3 和Google 文件系統。本文將圖1 所示的HDFS 體系結構用于復制管理。假設每個文件由一些塊構成，這些塊分布在該文件系統的數據節點中，以Name 節點作為復制管理中的協調器。

圖1 HDFS 體系結構Fig.1 HDFS architecture

協調器結構如圖2 所示，其由位置復制管理器（Locality Replication Manager，LRM）、圖目錄表（Graph Directory Table，GDT）、圖構造器（Graph Constructor，GC）和可用性和延遲系統（Availability and Delay System，ADS）組成。

圖2 協調器結構Fig.2 Structure of coordinator

1）位置復制管理器（LRM）的主要任務是接收用戶的查詢，收集集群中數據節點的狀態，最終確定放置塊的最佳主機。LRM 與其他組成部分協作完成這些任務，換句話說，LRM 是最終的決策者。

2）圖目錄表（GDT）是由LRM 管理的表，包括來自系統非常重要的信息，如塊及其圖、圖中每個塊的訪問次數、每個圖的主機以及訪問每個圖的最大延遲。

3）圖構造器（GC）從每個查詢中的可用塊構建一個完整的圖，并將其發送給LRM 以進行放置決策。

4）當LRM 發現系統沒有處于與延遲和可用性有關的優先級別時，該組件將通過接收來自于LRM 的消息開始工作。可用性和延遲系統（ADS）確定合適的數據節點以將圖再次放置在系統中，然后將該信息發送給系統。LRM 改變圖的主機，并同時通過接收來自于ADS 的信息來更新GDT。

下文所使用的參數符號及其含義如表1 所示。

表1 參數符號及其含義Table 1 Parameter symbols and their implications

2.2 可用性

云存儲集群的第一個目標是為塊及其圖提供最高的可用性。假設如果Bi位于mj的數據節點上，則判決變量θ（i，j）為1，否則為0。

將Pj確定為數據節點mj（1≤j≤M）的可能故障，數據節點的故障是隨機出現的。每個塊可以存在于多個查詢中，每個查詢被視為是一個完整的圖，且分布在多個節點上。如果一個節點（塊）在圖（查詢）中不可用，則塊就不可用，當一個圖的所有塊不可用時，則一個圖就不可用。因此，系統中可用塊可用的概率為：

由于一個圖中全部塊的可用性比一個塊的可用性更重要，因此一個圖（查詢）的可用性表示為：

2.3 延遲

最小化每個存儲系統的延遲是云存儲數據過程中的關鍵問題，這個延遲取決于存儲盤的帶寬和傳輸速率。因此，如果將這些塊放置在具有最大帶寬和較高傳輸速率的數據節點上，則數據訪問延遲較小。由于每個塊都有多個副本，因此Bi的延遲計算為：

其中，A（i，j）是由數據節點mj中的帶寬和數據傳輸引起的延遲。

由于一組塊的延遲（查詢圖）比一個塊的延遲更重要，因此有：

2.4 目標函數

本文設計的目標函數如下：

首先將用戶的每個查詢發送到LRM，通過LRM將查詢發送給GC 單元，然后以完整圖的形式接收結果。之后，LRM 進入到復制管理階段。為管理數據云中的復制，應執行以下2 個步驟：

1）副本選擇

為每個查詢選擇最好的副本。為選擇一個副本，將用戶的查詢以圖形的形式提交給LRM。LRM尋找一個已經有該圖的節點，或者新圖是否是該圖中現存一個圖的子集。在找到所需的節點后，采用找到的任何一個節點來檢查新查詢的QoS。能夠滿足查詢圖QoS 的第一個節點是由LRM 選取的，且由查詢圖引出該節點。但是，如果不存在查詢圖一個副本的節點，或者一個節點存在，但它的查詢圖不能滿足其QoS，則將以如下方式工作：首先，LRM 列出具有該新圖一部分的全部節點，并根據它們能夠滿足的QoS 來排列；然后，選取多個覆蓋查詢圖中全部節點的節點，并測量出由這些節點提供的平均QoS。如果得到的平均QoS 能夠滿足查詢圖的QoS，則將這些節點記錄在GDT 中作為新圖的宿主組；如果沒有任何副本選擇方法可以選擇一個或多個節點作為新圖的宿主，則嘗試副本放置。

2）副本放置

副本放置是指將副本放置在最佳數據節點中。如果LRM 采用副本選擇方法無法找到查詢的QoS節點，則從滿足式（5）的其他節點中選擇一個節點。

式（5）作為本文提出的目標函數，有2 個值得注意的項，分別是Sj·α-lj和可使負荷分布在數據云中得到平衡，則選擇一個能夠滿足查詢圖的QoS 的節點，并將其作為最大容許延遲。通過式（5）中的|S（Gnew）∩S（mj）|項，選擇一個節點作為查詢圖的放置，且該節點與目標圖有最大的共性。采用這一項可使來自每個塊的現有副本數量達到最小。

3 數據復制策略的實現

上述分析表明，LRM 是數據復制管理的核心，其主要目標為：1）接收查詢并將其發送給合適的節點，以滿足用戶期望的質量；2）考慮系統的可用性和延遲，并將其保持在期望的水平。本節將介紹具體實現過程。

3.1 發送查詢的合適節點

查找要發送查詢的合適節點的具體過程如算法1所示。

算法1 將文件塊隨機放置在物理節點上，在接收到塊的每個查詢后，執行以下步驟：

協調器首先接收查詢，然后為其生成一個新圖（Gnew）。協調器在GDT 中查找一個節點或一組節點，其中GDT 包括圖或圖的一部分，并能滿足查詢的QoS（算法第5 行和第6 行）。此搜索結果可以是一個節點或一組節點，如果搜索的結果是一個節點（算法第8 行和第10 行），則協調器將查詢引導到該節點，如果結果是一組節點（算法第10 行～第16 行），則協調器首先基于它們能滿足的QoS 按升序排列它們，然后從列表的開始選擇節點，直至物理節點覆蓋全部新圖的節點。

在覆蓋全部圖節點后，如果選擇節點的平均QoS 能夠滿足查詢的QoS，則將這組物理節點記錄為協調器中新圖的宿主。選擇副本后，最后一步是更改圖中節點的訪問字段，并刪去副本（算法第20行～第22 行）。由于對圖的訪問不同，有可能一些節點被訪問得較多，一些節點被訪問得較少，而一些節點從不被訪問。協調器中每個節點的訪問字段隨對該節點的每次訪問而增加，而且沒有任何訪問會導致該字段減小，以至于當該字段為0 時，則意味著該節點在圖訪問中無效，且應當由協調器從圖中刪去。在刪除副本之前，協調器檢查塊是否是原始塊的最后一個副本，如果是，則協調器將阻止刪除該塊。圖3 所示為發送一個查詢給LRM、創建查詢的一個圖和刪除副本的示例。

圖3 GDT 管理示例Fig.3 Example of GDT management

如果協調器不能從云中現有的圖中找到任何圖（算法第5 行和第6 行），則它將來自于圖中的每個現有塊的一個新副本放置在節點上，以使式（5）最小化。在找到節點后，將新圖與相關節點一起記錄在協調器中（算法第24 行～第26 行）。

3.2 系統的可用性和延遲

為將系統的可用性和延遲保持在期望水平，如果查詢的δ中不符合目標QoS，則LRM 命令ADS 重新構建系統。重構意味著再次將圖查詢放置在物理節點上，以使系統的可用性和延遲保持在期望的水平上。ADS還通過接收這個命令來響應算法2。從算法2 可以看出，ADS 采用了遺傳互補算法來實現這一目標。

遺傳算法在大量的數據空間中反復搜索以獲得接近最優的解，其中每個可能解都是以染色體的形式編碼的。把這組染色體稱為“種群”。首先形成一個初始種群，這個初始種群是隨機構建的，在初始種群形成之后，開始選擇步驟。在選擇中，根據染色體的質量為下一個種群選擇或丟棄染色體，下一步就是“交叉”。在這一步中，從種群中選擇多對染色體，并對它們的一些參數進行交換，以創建一對有效的染色體。“交叉”之后就是“變異”。在“變異”中，每個染色體從種群中變成一個有效的染色體。在這些步驟之后，對新的種群進行檢查，通過目標函數為每個染色體分配一個合適的值，目標是尋找一個最優適應值的染色體。如果該值不滿足，則重復上述步驟，以生成新的種群。這樣的過程一直持續到找到該值為止。下文給出使用遺傳算法的具體步驟和方法。

3.2.1 編碼

生成每個染色體的編碼實現如圖4 所示。一個染色體是為有限數量的圖和物理節點而生成的，并表示為一組整數。

圖4 從物理節點和圖生成染色體的編碼實現Fig.4 Coding implementation of creation of a chromosome from physical nodes and graphs

3.2.2 目標函數和選擇

染色體的適應性取決于種群中的選擇，如式（6）所示，該式表明了整個云系統的延遲與可用性之比。

如果Q是初始種群中染色體的總數量，則有最高適應性的Q-K個染色體根據一些條件來選擇并傳遞到下一個種群。下一個種群的K個染色體是隨機生成的，以防止快速收斂的出現，并避免陷入局部極小。

3.2.3 交叉

從下一代選擇的Q-K個染色體中，通過交叉將L個染色體（L

圖5 兩點交叉示意圖Fig.5 Schematic diagram of two-point cross-over

3.2.4 變異

變異步驟是在傳遞率為0.5 時完成的。為變異步驟選擇的每個指標的記錄（表示圖的物理節點）被替換為另一個隨機獲取的物理節點。

3.2.5 遺傳算法

算法2 給出了遺傳算法所需的全部步驟，用于將系統的可用性和延遲保持在期望的水平。

4 仿真與性能評價

仿真中將文獻［14，20］中2 種典型的數據復制策略與本文提出的復制策略在多個性能指標上進行比較。

表2 所示為數據節點中采用的配置、采用的算法和輸入到系統的查詢，設置25 個節點，其中一些節點隨機放置在機架上。假設數據云遵循“一次寫，多次讀”的策略。

表2 LRM 的配置Table 2 LRM configuration

圖6 所示為3 種策略的復制因子（代表副本數量）與塊數量的關系。可以看出，本文策略在不同塊數量的情況下得到的副本數量均小于其他2 種策略，這主要是由于本文策略采用了圖構造器，使其從每個查詢中的可用塊構建一個完整的圖，并選擇一個節點作為查詢圖的放置，且該節點與目標圖有最大的共性，從而使得來自每個塊的現有副本數量達到最小。這樣不僅可以優化資源使用，而且還能提高數據云系統的效率。

圖6 不同策略的復制因子Fig.6 Replication factors of different strategies

圖7 所示為3 種策略的訪問節點數目與考慮請求塊的位置特征，即請求塊數量的關系。可以看出，隨著動態查詢數量的增加，3 種策略的訪問節點數都隨之增加，但本文策略訪問的物理節點數的增加要小得多，這是因為本文策略將查詢視為一個完整的圖，且考慮了圖和圖中每個塊的訪問次數、以及訪問每個圖和圖中每個塊的最大延遲。這也意味著則查詢的速度越快，延遲越小。

圖7 不同策略訪問的物理節點數Fig.7 Number of physical nodes accessed by different strategies

圖8 所示為在固定查詢數量時負荷分配與塊數量的關系。可以看出，與其他2 種策略相比，本文策略獲得的負荷分配更具魯棒性，這是由于本文策略采用LRM 來接收用戶的查詢和收集集群中數據節點的狀態，其他組成部分協作完成這些任務，以更均勻的方式分配負荷。

圖8 不同策略物理節點的負荷分配Fig.8 Load allocation of physical nodes in different strategies

圖9 所示為3 種策略的可用性與塊數量的關系。可以看出，當系統中負荷變化時，本文策略考慮了系統中可用塊可用的概率以及圖（查詢）的可用性，所以在可用性方面的性能要分別優于文獻［14，20］策略約12.3%和14.5%。

圖9 不同策略系統的平均可用率Fig.9 Average system availability in different strategies

圖10 所示為3 種策略在滿足請求時的平均延遲與塊數量的關系。由于本文策略將這些可用塊放置在具有最大帶寬和較高傳輸速率的數據節點上，并考慮每個塊的副本數，所以數據訪問有較小的延遲，從而降低了整個系統的延遲，顯然，與文獻［14，20］策略相比，分別降低了約30.5%和18.3%。

圖10 不同策略在滿足請求時的平均延遲Fig.10 Average delay of different strategies when meeting requests

5 結束語

本文研究數據云文件中塊的復制管理問題，提出一種高效的數據復制策略，將Hadoop 分布式文件體系結構用于復制管理。以“Name 節點”作為復制管理中的協調器，通過為塊復制提供一個高效的管理器來優化系統中的資源分配、可用性、延遲等因素，并基于數據塊的可用性和存儲系統的延遲建立目標函數，采用遺傳算法進行實現。實驗結果表明，本文策略可有效提高系統的資源和能量使用、可用性、延遲等方面性能。下一步將針對不同的成本模型研究在線數據移動方法，以應對訪問塊模式中的動態變化。