魏秀然，王 峰

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

0 概述

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

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

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

1 相關工作

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

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

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

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

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

2 系統(tǒng)模型與優(yōu)化目標

2.1 系統(tǒng)模型

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

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

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

圖2 協(xié)調器結構Fig.2 Structure of coordinator

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

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

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

4）當LRM 發(fā)現(xiàn)系統(tǒng)沒有處于與延遲和可用性有關的優(yōu)先級別時，該組件將通過接收來自于LRM 的消息開始工作?？捎眯院脱舆t系統(tǒng)（ADS）確定合適的數(shù)據(jù)節(jié)點以將圖再次放置在系統(tǒng)中，然后將該信息發(fā)送給系統(tǒng)。LRM 改變圖的主機，并同時通過接收來自于ADS 的信息來更新GDT。

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

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

2.2 可用性

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

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

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

2.3 延遲

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

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

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

2.4 目標函數(shù)

本文設計的目標函數(shù)如下：

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

1）副本選擇

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

2）副本放置

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

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

3 數(shù)據(jù)復制策略的實現(xiàn)

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

3.1 發(fā)送查詢的合適節(jié)點

查找要發(fā)送查詢的合適節(jié)點的具體過程如算法1所示。

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

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

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

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

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

3.2 系統(tǒng)的可用性和延遲

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

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

3.2.1 編碼

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

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

3.2.2 目標函數(shù)和選擇

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

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

3.2.3 交叉

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

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

3.2.4 變異

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

3.2.5 遺傳算法

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

4 仿真與性能評價

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

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

表2 LRM 的配置Table 2 LRM configuration

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

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

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

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

圖8 所示為在固定查詢數(shù)量時負荷分配與塊數(shù)量的關系?？梢钥闯?，與其他2 種策略相比，本文策略獲得的負荷分配更具魯棒性，這是由于本文策略采用LRM 來接收用戶的查詢和收集集群中數(shù)據(jù)節(jié)點的狀態(tài)，其他組成部分協(xié)作完成這些任務，以更均勻的方式分配負荷。

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

圖9 所示為3 種策略的可用性與塊數(shù)量的關系?？梢钥闯?，當系統(tǒng)中負荷變化時，本文策略考慮了系統(tǒng)中可用塊可用的概率以及圖（查詢）的可用性，所以在可用性方面的性能要分別優(yōu)于文獻［14，20］策略約12.3%和14.5%。

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

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

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

5 結束語

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