基于蟻群算法的數(shù)據(jù)副本放置策略

摘 要：提出了基于蟻群算法的副本放置策略，充分利用了蟻群算法在目標(biāo)優(yōu)化問題中的優(yōu)勢(shì)，用OptorSim模擬實(shí)驗(yàn)結(jié)果表明該算法可以有效地減少作業(yè)對(duì)文件請(qǐng)求的響應(yīng)時(shí)間，從而提高整個(gè)系統(tǒng)的性能。

關(guān)鍵詞：網(wǎng)格； 蟻群算法； 復(fù)制； 放置策略； 虛擬組織

中圖分類號(hào)：TP301.6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：1001-3695(2007)06-0082-03

0 引言

網(wǎng)格計(jì)算的目的是提供一個(gè)地理上分布

的虛擬組織并允許有效共享計(jì)算資源和存儲(chǔ)資源。當(dāng)今，許多國際項(xiàng)目正在研究數(shù)據(jù)網(wǎng)格的實(shí)現(xiàn)。為了通過計(jì)算密集型應(yīng)用來分析大量分布的數(shù)據(jù)。在數(shù)據(jù)網(wǎng)格中，數(shù)據(jù)可以存儲(chǔ)在不同種類的存儲(chǔ)系統(tǒng)中，如分布式文件系統(tǒng)（AFS或NFS）、Mass Storage System、傳統(tǒng)的關(guān)系型數(shù)據(jù)庫和面向?qū)ο蟮臄?shù)據(jù)庫［1］。為了提高性能、有用性和可靠性，通常使用復(fù)制技術(shù)來創(chuàng)建數(shù)據(jù)文件的多個(gè)副本。因此，副本的放置，即文件副本存放的位置節(jié)點(diǎn)是數(shù)據(jù)網(wǎng)格中非常重要的基礎(chǔ)。

Internet中主要的挑戰(zhàn)是支持快速數(shù)據(jù)讀取；而在網(wǎng)格中支持快速數(shù)據(jù)讀取的主要阻礙是廣域網(wǎng)的高延遲性。為了實(shí)現(xiàn)快速數(shù)據(jù)讀取，大量數(shù)據(jù)需要復(fù)制多個(gè)拷貝在世界各地分布的節(jié)點(diǎn)上。一個(gè)數(shù)據(jù)網(wǎng)格應(yīng)該提供有一系列服務(wù)的虛擬組織。這些服務(wù)包括資源的動(dòng)態(tài)讀取，滿足用戶的需求（最小化用戶作業(yè)的執(zhí)行代價(jià)）和最大化網(wǎng)格資源的利用率。然而，存儲(chǔ)系統(tǒng)的數(shù)量和大小是有限的，需要一個(gè)好的復(fù)制策略來分析和預(yù)測(cè)用戶的需求，并負(fù)責(zé)找出多個(gè)副本中的最優(yōu)副本、復(fù)制數(shù)據(jù)和替換不經(jīng)常使用的數(shù)據(jù)［2］。

數(shù)據(jù)是數(shù)據(jù)網(wǎng)格中最重要的資源［3］，用戶的作業(yè)需要讀取大量的數(shù)據(jù)，而數(shù)據(jù)存儲(chǔ)在網(wǎng)格中各個(gè)分布的節(jié)點(diǎn)上。為了提高系統(tǒng)的性能，當(dāng)數(shù)據(jù)的讀取次數(shù)超過一定的閾值時(shí)，就采用復(fù)制策略來復(fù)制文件到適當(dāng)?shù)墓?jié)點(diǎn)上；沒有超過閾值時(shí)，就從已存在的文件多個(gè)副本中選擇一個(gè)最優(yōu)的副本來滿足用戶作業(yè)的需求。

復(fù)制系統(tǒng)的性能依靠很多因素，如數(shù)據(jù)的放置、數(shù)據(jù)的大小、網(wǎng)絡(luò)的帶寬和延遲、系統(tǒng)可靠性等。本文提出了一種基于蟻群算法的副本放置方法，利用神經(jīng)網(wǎng)絡(luò)中的蟻群算法有效地在網(wǎng)格系統(tǒng)多個(gè)節(jié)點(diǎn)中選擇最優(yōu)的副本放置節(jié)點(diǎn)，以實(shí)現(xiàn)副本管理系統(tǒng)的全局最優(yōu)性。

1 數(shù)據(jù)網(wǎng)格中的復(fù)制

Globus Tookit［4］是一個(gè)開放源碼的網(wǎng)格

基礎(chǔ)平臺(tái)；它基于開放結(jié)構(gòu)、開放服務(wù)資源的

軟件庫，并支持網(wǎng)格和網(wǎng)格應(yīng)用。其目的是為構(gòu)建網(wǎng)格應(yīng)用提供中間件服務(wù)和程序庫。Globus提供四個(gè)主要組成部分，即網(wǎng)格安全架構(gòu)、Globus資源管理架構(gòu)、Globus信息管理和數(shù)據(jù)管理架構(gòu)。其中數(shù)據(jù)管理架構(gòu)為數(shù)據(jù)網(wǎng)格提供基本工具：一個(gè)通用的數(shù)據(jù)傳輸協(xié)議——GridFTP和副本管理架構(gòu)。其中副本管理架構(gòu)包括副本目錄和為了管理多個(gè)數(shù)據(jù)副本的副本管理服務(wù)。其中副本目錄提供了文件的一個(gè)全局的唯一的邏輯文件名到一個(gè)或多個(gè)物理文件的位置映射。副本管理服務(wù)提供可靠的創(chuàng)建、刪除和管理副本功能。

2 副本放置服務(wù)設(shè)計(jì)

復(fù)制技術(shù)已經(jīng)被廣泛地研究，并且許多分布的副本管理策略已經(jīng)提出，如文獻(xiàn)[3]。由于網(wǎng)格是一個(gè)動(dòng)態(tài)環(huán)境，副本的數(shù)量和位置也是動(dòng)態(tài)變化的。副本管理服務(wù)解決資源復(fù)制的三個(gè)基本問題，即復(fù)制哪個(gè)資源、何時(shí)復(fù)制及復(fù)制到何處。當(dāng)文件被訪問的次數(shù)達(dá)到一定的閾值時(shí)，就對(duì)文件進(jìn)行復(fù)制。本文文件復(fù)制的位置由副本管理服務(wù)根據(jù)蟻群算法來決定副本放置的節(jié)點(diǎn)。

2.1 基于虛擬組織（VO）的副本位置架構(gòu)

一個(gè)虛擬組織（Virtual Organization）指有一部分網(wǎng)格資源的節(jié)點(diǎn)集合；這些節(jié)點(diǎn)通過局域網(wǎng)連接在一起。多個(gè)VO通過廣域網(wǎng)連接，相互之間可以共享網(wǎng)絡(luò)中的資源。本文采用文獻(xiàn)[5]中的樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。圖1為四個(gè)VO組成的基于樹的拓?fù)浣Y(jié)構(gòu)。

圖1 包含VO的樹型網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

2.2 蟻群算法的原理

蟻群算法［6］是通過模擬自然界螞蟻搜索路徑的行為提出的一種新型的模擬進(jìn)化算法。該方法求解TSP（旅行商問題）、分配問題、JobShop調(diào)度問題，取得了較好的實(shí)驗(yàn)結(jié)果。現(xiàn)在的研究顯示出，蟻群算法在求解復(fù)雜優(yōu)化問題（特別是離散化優(yōu)化問題）方面有一定的優(yōu)勢(shì)。

螞蟻的個(gè)體行為極其簡(jiǎn)單，但群體卻表現(xiàn)出類似某種集體智能的復(fù)雜行為。螞蟻之間依靠外激素(Pheromone)進(jìn)行信息傳遞實(shí)現(xiàn)復(fù)雜的合作。螞蟻對(duì)外激素本能的傾向性使得大量螞蟻在搜尋食物的集體行為中表現(xiàn)出一種正反饋過程：某條路徑越短，走過的螞蟻越多，留下的外激素濃度越高，則其他螞蟻選擇走這條路的幾率越大。最終，借助這種信息交流，蟻群就能找到一條從蟻穴到食物的最短路徑。

2.3 數(shù)學(xué)模型

數(shù)據(jù)網(wǎng)格中，節(jié)點(diǎn)m想訪問數(shù)據(jù)i；而數(shù)據(jù)i的多個(gè)副本存儲(chǔ)在分散的不同的地理位置。選擇通信代價(jià)最小的副本來滿足節(jié)點(diǎn)m對(duì)數(shù)據(jù)i的讀取請(qǐng)求，以減小網(wǎng)絡(luò)帶寬，提高系統(tǒng)的整體性能。由于廣域網(wǎng)的延遲性，對(duì)訪問量過多的那些數(shù)據(jù)，可以在適當(dāng)?shù)墓?jié)點(diǎn)上放置數(shù)據(jù)副本來減少數(shù)據(jù)讀取時(shí)間，用盡量少的時(shí)間滿足用戶需求，假定用戶規(guī)定的期限為D［7］。

其中，α代表了在復(fù)制數(shù)據(jù)時(shí)，存儲(chǔ)代價(jià)的重要程度在整體中所占的比重；β代表了在復(fù)制數(shù)據(jù)時(shí)，通信代價(jià)要求在整體中所占的比重；θ代表了在復(fù)制數(shù)據(jù)時(shí)，對(duì)傳輸帶寬要求在整體中所占的比重。

2.4 副本放置算法

初始的蟻群算法是基于圖的蟻群算法（GraphBased Ant System，GBAS）。算法步驟如：

3 算法分析與測(cè)試

數(shù)據(jù)網(wǎng)格中數(shù)據(jù)副本的放置與刪除是高度動(dòng)態(tài)的，數(shù)據(jù)副本的放置問題是一個(gè)優(yōu)化問題。蟻群算法是群智能研究領(lǐng)域中的一種主要算法。研究結(jié)果表明，蟻群算法在求解復(fù)雜優(yōu)化問題（特別是離散優(yōu)化問題）方面有一定的優(yōu)勢(shì)。

OptorSim用來研究各種副本優(yōu)化算法的數(shù)據(jù)網(wǎng)格模擬器。在網(wǎng)格環(huán)境中，選擇一個(gè)較優(yōu)的節(jié)點(diǎn)來放置副本，可提高以后用戶作業(yè)的運(yùn)行時(shí)間，從而提高整個(gè)系統(tǒng)的性能。本文假設(shè)文件大小為100 MB，網(wǎng)絡(luò)拓?fù)淙鐖D2所示。為了簡(jiǎn)化模擬，假設(shè)沒有競(jìng)爭(zhēng)的網(wǎng)絡(luò)流量。實(shí)驗(yàn)?zāi)康氖亲C明基于蟻群算法的優(yōu)化副本放置算法可以優(yōu)化以后作業(yè)的運(yùn)行時(shí)間。

第1列表示每個(gè)節(jié)點(diǎn)上CE的個(gè)數(shù)；第2列表示每個(gè)節(jié)點(diǎn)上SE的個(gè)數(shù)；第3列表示每個(gè)節(jié)點(diǎn)上SE的大小，單位為MB，以后表示各個(gè)節(jié)點(diǎn)之間的帶寬矩陣。假定各節(jié)點(diǎn)間的帶寬均為50 MBps。令initial file distribution =1，說明開始時(shí)文件的副本在節(jié)點(diǎn)1上。用戶作業(yè)請(qǐng)求文件順序由作業(yè)的讀取方式?jīng)Q定，考慮以下方式，即順序方式（所有文件按預(yù)先規(guī)定的順序訪問）。模擬運(yùn)行作業(yè)為1－100個(gè)，每隔5s提交一個(gè)作業(yè)。

比較基于蟻群的副本放置算法與LRU（Least Recently Used）算法。LRU中文件總是被復(fù)制到作業(yè)執(zhí)行的節(jié)點(diǎn)。如果節(jié)點(diǎn)上的存儲(chǔ)空間滿，則刪除最近最少讀取的文件。圖3顯示作業(yè)數(shù)變化時(shí)，兩種算法的平均作業(yè)執(zhí)行時(shí)間。圖4顯示文件大小變化時(shí)，對(duì)文件請(qǐng)求的平均響應(yīng)時(shí)間。

實(shí)驗(yàn)結(jié)果顯示，雖然在放置文件的副本時(shí)蟻群算法比LRU花費(fèi)的時(shí)間要長(zhǎng)；但由于蟻群算法放置的節(jié)點(diǎn)是傳輸代價(jià)和存儲(chǔ)代價(jià)最小的，對(duì)后繼作業(yè)的運(yùn)行時(shí)間大大減少。因此，提高了系統(tǒng)的整體性能。

4 結(jié)束語

本文討論了基于蟻群算法的副

本放置策略。通過動(dòng)態(tài)調(diào)整網(wǎng)格中數(shù)據(jù)副本的位置和數(shù)量，并使用優(yōu)化程序來減小數(shù)據(jù)讀取的時(shí)間和代價(jià)。首先介紹了數(shù)據(jù)網(wǎng)格中的復(fù)制結(jié)構(gòu)，進(jìn)而引入蟻群算法對(duì)副本進(jìn)行放置，有效地減少用戶作業(yè)讀取數(shù)據(jù)的時(shí)間，提高系統(tǒng)的整體性能。模擬結(jié)果顯示了該算法是有效的。

本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文。