PDM 中基于負(fù)載信息的文件讀取均衡算法

夏秀峰，張 羽

（1.沈陽(yáng)航空航天大學(xué) 遼寧省通用航空重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽(yáng)110136；2.沈陽(yáng)航空航天大學(xué) 計(jì)算機(jī)學(xué)院，遼寧 沈陽(yáng)110136）

0 引 言

目前，PDM （product data management）系統(tǒng)均采用基于RDB （relational database）實(shí)現(xiàn)，且采用獨(dú)立文件服務(wù)器存儲(chǔ)產(chǎn)品數(shù)據(jù)。隨著制造企業(yè)產(chǎn)品數(shù)據(jù)的不斷積累，面對(duì)海量數(shù)據(jù)高效存儲(chǔ)與訪問要求，傳統(tǒng)存儲(chǔ)方式成為制約PDM 系統(tǒng)性能的瓶頸之一。另一方面，RDB 橫向擴(kuò)展性差，且隨MBD （model based definition）／MBE （model based enterprise）技術(shù)的實(shí)施，PDM 數(shù)據(jù)的結(jié)構(gòu)特征越來(lái)越弱，因此使用NOSQL 數(shù)據(jù)庫(kù)存儲(chǔ)文件元數(shù)據(jù)信息，將云存儲(chǔ)技術(shù)應(yīng)用于PDM，構(gòu)建企業(yè)私有云環(huán)境下的PDM文件系統(tǒng)，在提升PDM 文件讀寫性能的同時(shí)，使PDM 文件系統(tǒng)具有更好的健壯性和擴(kuò)展性。

Hadoop［1，2］是一個(gè)優(yōu)秀的開源云計(jì)算平臺(tái)，以HDFS（Hadoop distributed file system）和MapReduce分布式計(jì)算框架為核心。其中，HDFS作為GFS （Google file system）的開源實(shí)現(xiàn)是Hadoop數(shù)據(jù)存儲(chǔ)的基礎(chǔ)。針對(duì)HDFS負(fù)載均衡的研究已經(jīng)取得一些成果?，F(xiàn)有研究多是基于數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)空間的負(fù)載均衡，通過合理的數(shù)據(jù)塊分布實(shí)現(xiàn)數(shù)據(jù)節(jié)點(diǎn)的負(fù)載均衡。在PDM 中，由于用戶對(duì)歷史產(chǎn)品數(shù)據(jù)的訪問大大少于對(duì)新產(chǎn)品數(shù)據(jù)的訪問，因此可能會(huì)出現(xiàn)數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)數(shù)據(jù)量相同，但數(shù)據(jù)節(jié)點(diǎn)用戶請(qǐng)求量相差較大的現(xiàn)象，使某些數(shù)據(jù)節(jié)點(diǎn)處于過載狀態(tài)，而其它數(shù)據(jù)節(jié)點(diǎn)處于低載或空載狀態(tài)。

本文提出一種基于負(fù)載信息的文件讀取均衡算法，算法使用動(dòng)態(tài)負(fù)載均衡技術(shù)，即客戶端根據(jù)數(shù)據(jù)節(jié)點(diǎn)負(fù)載信息動(dòng)態(tài)創(chuàng)建文件讀取請(qǐng)求，避免用戶請(qǐng)求過度集中于某些數(shù)據(jù)節(jié)點(diǎn)，較好實(shí)現(xiàn)數(shù)據(jù)節(jié)點(diǎn)負(fù)載均衡，并使用戶等待時(shí)間明顯縮短。

1 負(fù)載評(píng)價(jià)

通常，集群負(fù)載均衡可分為靜態(tài)和動(dòng)態(tài)兩種方式。靜態(tài)負(fù)載均衡算法無(wú)需根據(jù)集群運(yùn)行狀態(tài)進(jìn)行任務(wù)的調(diào)整；動(dòng)態(tài)負(fù)載均衡在系統(tǒng)運(yùn)行過程中根據(jù)各節(jié)點(diǎn)的資源利用情況，動(dòng)態(tài)調(diào)整分配給各節(jié)點(diǎn)的任務(wù)。文獻(xiàn) ［3］對(duì)集群文件服務(wù)系統(tǒng)中常見的負(fù)載均衡算法進(jìn)行了詳細(xì)介紹。

靜態(tài)負(fù)載均衡不考慮當(dāng)前所有連接狀態(tài)及各節(jié)點(diǎn)之間當(dāng)前的負(fù)載情況。由于無(wú)需額外獲取服務(wù)器負(fù)載信息，任務(wù)分配與系統(tǒng)當(dāng)前狀態(tài)無(wú)關(guān)，造成任務(wù)分配具有盲目性的特點(diǎn)，因而導(dǎo)致負(fù)載均衡效果不理想。文獻(xiàn) ［4］對(duì)負(fù)載均衡算法進(jìn)行了詳細(xì)介紹并對(duì)比優(yōu)缺點(diǎn)。

動(dòng)態(tài)負(fù)載均衡根據(jù)集群各節(jié)點(diǎn)當(dāng)前狀態(tài)進(jìn)行任務(wù)的動(dòng)態(tài)分配，負(fù)載均衡效果明顯優(yōu)于靜態(tài)負(fù)載均衡方式，但如果算法設(shè)計(jì)不合理容易導(dǎo)致負(fù)載均衡失敗并增加集群的額外開銷。文獻(xiàn) ［5］利用自適應(yīng)的反饋機(jī)制，有效降低獲取負(fù)載信息的額外開銷。文獻(xiàn) ［6］提出一種改進(jìn)的基于反饋的負(fù)載均衡算法，在考慮服務(wù)節(jié)點(diǎn)真實(shí)負(fù)載，處理能力的基礎(chǔ)上，盡量簡(jiǎn)化負(fù)載均衡器的任務(wù)分配算法。

文獻(xiàn) ［7，8］分別對(duì)Hadoop默認(rèn)負(fù)載均衡算法進(jìn)行改進(jìn)，經(jīng)實(shí)驗(yàn)對(duì)比數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)空間使用更加平均，實(shí)現(xiàn)了數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)空間的負(fù)載均衡。文獻(xiàn) ［9］建立基于控制變量的數(shù)據(jù)負(fù)載均衡數(shù)學(xué)模型，通過控制變量動(dòng)態(tài)分配網(wǎng)絡(luò)帶寬以實(shí)現(xiàn)數(shù)據(jù)負(fù)載均衡。文獻(xiàn) ［10］提出基于結(jié)點(diǎn)網(wǎng)絡(luò)距離與數(shù)據(jù)負(fù)載計(jì)算每個(gè)結(jié)點(diǎn)的調(diào)度評(píng)價(jià)值，實(shí)現(xiàn)數(shù)據(jù)放置負(fù)載均衡的同時(shí)保證了良好的數(shù)據(jù)傳輸性能。

本文選用動(dòng)態(tài)負(fù)載均衡方式進(jìn)行請(qǐng)求分配，為確定某一時(shí)刻數(shù)據(jù)節(jié)點(diǎn)的負(fù)載大小，需要對(duì)數(shù)據(jù)節(jié)點(diǎn)負(fù)載情況進(jìn)行計(jì)算。而負(fù)載評(píng)價(jià)因素的選取則直接影響動(dòng)態(tài)負(fù)載均衡性能的好壞。①由于本文以企業(yè)私有云環(huán)境下PDM 文件系統(tǒng)動(dòng)態(tài)負(fù)載均衡為研究背景，對(duì)數(shù)據(jù)節(jié)點(diǎn)的壓力負(fù)載主要是數(shù)據(jù)I／O 操作，所以將硬盤使用率作為第一個(gè)評(píng)價(jià)因素；②由于數(shù)據(jù)節(jié)點(diǎn)需要執(zhí)行MapReduce任務(wù)，因此將CPU做為第二個(gè)評(píng)價(jià)因素；③分布式文件系統(tǒng)通過網(wǎng)絡(luò)為用戶提供服務(wù)，網(wǎng)絡(luò)帶寬的使用率影響著數(shù)據(jù)節(jié)點(diǎn)響應(yīng)時(shí)間，因此將網(wǎng)絡(luò)帶寬作為最后一個(gè)評(píng)價(jià)因素。由此得出數(shù)據(jù)節(jié)點(diǎn)負(fù)載評(píng)價(jià)函數(shù)如式 （1）所示

式中：U（Disk）——硬盤使用率，U（CPU）——CPU 使用率，U（Net）——上行網(wǎng)絡(luò)帶寬使用率。U（Node）——負(fù)載大小，U（Node）數(shù)值越大代表數(shù)據(jù)節(jié)點(diǎn)負(fù)載越重。其中λ1、λ2、λ3為各評(píng)價(jià)因素的權(quán)重因子，且λ1＋λ2＋λ3＝1。

2 負(fù)載均衡算法

HDFS自帶的讀取算法 （以下簡(jiǎn)稱默認(rèn)算法）中，選擇某個(gè)數(shù)據(jù)節(jié)點(diǎn)提供服務(wù)需要通過排序與選擇兩個(gè)階段完成。通過循環(huán)執(zhí)行排序算法和選擇算法，為文件的每個(gè)數(shù)據(jù)塊選擇合適的數(shù)據(jù)節(jié)點(diǎn)向用戶提供服務(wù)。默認(rèn)排序算法沒有考慮數(shù)據(jù)節(jié)點(diǎn)的實(shí)際負(fù)載情況，僅能隨機(jī)選擇某個(gè)數(shù)據(jù)節(jié)點(diǎn)提供服務(wù)，因而負(fù)載均衡效果較差。同時(shí)默認(rèn)算法使用順序讀取方式限制了數(shù)據(jù)節(jié)點(diǎn)的選擇范圍，導(dǎo)致用戶請(qǐng)求的過度集中造成數(shù)據(jù)節(jié)點(diǎn)過載現(xiàn)象的出現(xiàn)。

針對(duì)上述問題，提出一種基于負(fù)載信息的文件讀取均衡算法。該算法采用動(dòng)態(tài)負(fù)載均衡方式，使用數(shù)據(jù)節(jié)點(diǎn)負(fù)載評(píng)價(jià)函數(shù)為動(dòng)態(tài)分配請(qǐng)求提供依據(jù)，并且通過非順序請(qǐng)求方式打破對(duì)數(shù)據(jù)節(jié)點(diǎn)選擇的限制，擴(kuò)大數(shù)據(jù)節(jié)點(diǎn)選擇范圍。算法將動(dòng)態(tài)負(fù)載均衡技術(shù)與非順序請(qǐng)求相結(jié)合，最終實(shí)現(xiàn)集群的動(dòng)態(tài)負(fù)載均衡。

2.1 算法基本思想

面對(duì)用戶大量并發(fā)請(qǐng)求，順序讀取方式限制了數(shù)據(jù)節(jié)點(diǎn)選擇范圍，導(dǎo)致請(qǐng)求集中于保存某些數(shù)據(jù)塊副本的節(jié)點(diǎn)上。而非順序請(qǐng)求方式可以擴(kuò)大數(shù)據(jù)節(jié)點(diǎn)的選擇范圍，存儲(chǔ)文件數(shù)據(jù)塊副本的所有節(jié)點(diǎn)均是選擇對(duì)象。PDM 系統(tǒng)中，用戶的一次訪問要求獲得文件的整體，并不關(guān)心文件數(shù)據(jù)塊的讀取順序，這種特點(diǎn)使非順序讀取成為可能。

算法的基本思想是，通過非順序請(qǐng)求方式增加數(shù)據(jù)節(jié)點(diǎn)的選擇對(duì)象之后，使用負(fù)載評(píng)價(jià)函數(shù)確定各數(shù)據(jù)節(jié)點(diǎn)負(fù)載大小，根據(jù)負(fù)載信息優(yōu)先選擇低負(fù)載數(shù)據(jù)節(jié)點(diǎn)提供服務(wù)，從而實(shí)現(xiàn)集群的負(fù)載均衡。

2.2 算法描述

根據(jù)算法的基本思想，下面給出基于負(fù)載信息的文件讀取均衡算法描述：

（1）根據(jù)用戶請(qǐng)求獲取請(qǐng)求文件信息，信息包括文件數(shù)據(jù)塊與數(shù)據(jù)節(jié)點(diǎn)存儲(chǔ)關(guān)系、文件長(zhǎng)度。

（2）根據(jù)文件系統(tǒng)元信息為保存有請(qǐng)求文件數(shù)據(jù)塊的節(jié)點(diǎn)建立臨時(shí)映射，映射記錄數(shù)據(jù)節(jié)點(diǎn)自身與存儲(chǔ)請(qǐng)求文件數(shù)據(jù)塊的關(guān)系。

（3）使用集合結(jié)構(gòu)記錄文件數(shù)據(jù)塊，用于判斷文件所有數(shù)據(jù)塊是否讀取完成。

（4）判斷文件數(shù)據(jù)塊是否全部讀取，如果是則轉(zhuǎn)（11）。

（5）獲取保存有文件數(shù)據(jù)塊節(jié)點(diǎn)的負(fù)載信息，使用集合記錄節(jié)點(diǎn)負(fù)載信息。

（6）計(jì)算節(jié)點(diǎn)平均負(fù)載，從負(fù)載信息集合中刪除大于平均負(fù)載的數(shù)據(jù)節(jié)點(diǎn)。

（7）從負(fù)載信息集合中選擇一個(gè)數(shù)據(jù)節(jié)點(diǎn)提供服務(wù)。

（8）通過數(shù)據(jù)節(jié)點(diǎn)與數(shù)據(jù)塊的臨時(shí)映射，選擇一個(gè)數(shù)據(jù)塊為目標(biāo)進(jìn)行數(shù)據(jù)讀取。

（9）將讀取數(shù)據(jù)塊從所在數(shù)據(jù)節(jié)點(diǎn)的臨時(shí)映射中刪除。

（10）從數(shù)據(jù)塊讀取記錄中刪除讀取完成的數(shù)據(jù)塊，跳至 （4）。

（11）文件讀取結(jié)束。

算法的偽代碼如下。

輸入：文件路徑src

初始化：

3 實(shí)驗(yàn)結(jié)果分析

為驗(yàn)證算法的有效性，實(shí)驗(yàn)使用一臺(tái)曙光A620r－G 服務(wù)器、兩臺(tái)曙光A840r－G 高性能服務(wù)器搭建分布式環(huán)境，存儲(chǔ)設(shè)備為曙光DS200－N10 磁盤陣列，Hadoop 版本為1.2.1。利用虛擬化技術(shù)創(chuàng)建8個(gè)數(shù)據(jù)節(jié)點(diǎn)，各數(shù)據(jù)節(jié)點(diǎn)網(wǎng)絡(luò)帶寬為100 Mbps。使用PC 作為客戶端模擬用戶并發(fā)請(qǐng)求文件，每個(gè)用戶網(wǎng)絡(luò)帶寬為10 Mbps，請(qǐng)求文件大小為271 MB。

圖1為用戶平均等待時(shí)間的對(duì)比，不難看出，隨著用戶并發(fā)訪問數(shù)量的不斷增加，所提算法的性能優(yōu)勢(shì)逐漸體現(xiàn)出來(lái)。模擬20 個(gè)用戶并發(fā)請(qǐng)求時(shí)，集群處于低負(fù)載狀態(tài)。此時(shí)兩種算法的用戶平均等待時(shí)間區(qū)別較小。當(dāng)模擬80個(gè)用戶并發(fā)請(qǐng)求時(shí)，集群處于高負(fù)載狀態(tài)。由于默認(rèn)算法負(fù)載均衡效果不理想，未能充分利用集群中數(shù)據(jù)節(jié)點(diǎn)資源，與所提算法相比用戶平均等待時(shí)間明顯增加。

圖1 用戶平均等待時(shí)間對(duì)比

模擬20個(gè)用戶并發(fā)請(qǐng)求文件時(shí)默認(rèn)算法數(shù)據(jù)節(jié)點(diǎn)負(fù)載信息如圖2所示。由于默認(rèn)算法順序請(qǐng)求文件數(shù)據(jù)塊，用戶請(qǐng)求集中在存儲(chǔ)數(shù)據(jù)塊副本的3個(gè)數(shù)據(jù)節(jié)點(diǎn)上。由于用戶請(qǐng)求數(shù)量較少集群各數(shù)據(jù)節(jié)點(diǎn)處于低負(fù)載狀態(tài)，因此并未出現(xiàn)數(shù)據(jù)節(jié)點(diǎn)過載現(xiàn)象。

模擬20個(gè)用戶并發(fā)請(qǐng)求時(shí)所提算法數(shù)據(jù)節(jié)點(diǎn)負(fù)載信息如圖3所示。所提算法根據(jù)數(shù)據(jù)節(jié)點(diǎn)負(fù)載信息動(dòng)態(tài)分配用戶請(qǐng)求，從而提高集群數(shù)據(jù)節(jié)點(diǎn)利用率。與默認(rèn)算法相比新算法能夠充分利用多個(gè)數(shù)據(jù)節(jié)點(diǎn)，因此降低了數(shù)據(jù)節(jié)點(diǎn)的負(fù)載，但低負(fù)載情況下兩種算法用戶平均等待時(shí)間差別較小。

圖2 默認(rèn)算法數(shù)據(jù)節(jié)點(diǎn)負(fù)載信息

圖3 所提算法數(shù)據(jù)節(jié)點(diǎn)負(fù)載信息

模擬80個(gè)用戶并發(fā)請(qǐng)求時(shí)默認(rèn)算法數(shù)據(jù)節(jié)點(diǎn)負(fù)載信息如圖4所示。集群處于高負(fù)載狀態(tài)下數(shù)據(jù)節(jié)點(diǎn)負(fù)載相差較大，集群數(shù)據(jù)節(jié)點(diǎn)多處于空載狀態(tài)。由于數(shù)據(jù)節(jié)點(diǎn)系統(tǒng)資源嚴(yán)重浪費(fèi)，因此用戶平均等待時(shí)間大幅增加。

圖4 默認(rèn)算法數(shù)據(jù)節(jié)點(diǎn)負(fù)載信息

模擬80個(gè)用戶并發(fā)請(qǐng)求時(shí)新算法數(shù)據(jù)節(jié)點(diǎn)負(fù)載信息如圖5所示。集群處于高負(fù)載狀態(tài)下，所提算法充分利用集群數(shù)據(jù)節(jié)點(diǎn)資源實(shí)現(xiàn)了集群的負(fù)載均衡。與默認(rèn)算法相比用戶平均等待時(shí)間明顯縮短。

由于PDM 是裝備制造企業(yè)的核心軟件，在每個(gè)時(shí)刻，往往有幾百個(gè)用戶同時(shí)訪問，此時(shí)，所提算法的優(yōu)勢(shì)將更加明顯。

圖5 所提算法數(shù)據(jù)節(jié)點(diǎn)負(fù)載信息

4 結(jié)束語(yǔ)

本文分析了PDM 文件請(qǐng)求的特點(diǎn)，并提出一種基于負(fù)載信息的文件讀取均衡算法。該算法將動(dòng)態(tài)負(fù)載均衡技術(shù)與非順序請(qǐng)求方式有效結(jié)合，增加了用戶請(qǐng)求節(jié)點(diǎn)的數(shù)量，避免因用戶請(qǐng)求集中而導(dǎo)致的數(shù)據(jù)節(jié)點(diǎn)過載問題的發(fā)生，從而實(shí)現(xiàn)集群的負(fù)載均衡。通過實(shí)驗(yàn)對(duì)比，在低負(fù)載和中度負(fù)載情況下負(fù)載均衡效果比默認(rèn)算法有所提高，在高負(fù)載情況下負(fù)載均衡效果提升明顯，解決了PDM 數(shù)據(jù)高并發(fā)條件下存儲(chǔ)與訪問效率低下的問題。

［1］Borthaur D.The Hadoop distributed file system：Architecture and design ［EB／OL］.［2013－04－08］.http：／／hadoop.apche.org／docs／r1.2.1／hdfs＿design.html.

［2］Jeffrey Shafer，Scott Rixner，Alan L Cox.The Hadoop distributed filesystem：Balancing portability and performance ［C］／／Proc of ISPASS.Piscataway，NJ：IEEE，2010：122－133.

［3］LIU Enhai，LI Wei，ZHANG Suqi，et al.Research of load balancing algorithm in cluster file service system ［J］.Computer Engineering and Design，2013，34 （8）：2755－2758（in Chinese）.［劉恩海，李偉，張素琪，等.集群文件服務(wù)系統(tǒng)中的負(fù)載均衡算法的研究［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2013，34 （8）：2755－2758.］

［4］LI Kun，WANG Baijie.Research on load balancing of web server system and comparison of algorithms［J］.Computer and Modernization，2009，25 （8）：7－10 （in Chinese）.［李坤，王百杰.服務(wù)器集群負(fù)載均衡技術(shù)研究及算法比較 ［J］.計(jì)算機(jī)與現(xiàn)代化，2009，25 （8）：7－10.］

［5］ZHANG Congping，YIN Jianwei.Dynamic load balancing algorithm of distributed file system ［J］.Journal of Chinese Computer Systems，2011，32 （7）：1424－1426 （in Chinese）. ［張聰萍，尹建偉.分布式文件系統(tǒng)的動(dòng)態(tài)負(fù)載均衡算法 ［J］.小型微型計(jì)算機(jī)系統(tǒng)，2011，32 （7）：1424－1426.］

［6］TIAN Shaoliang，ZUO Ming，WU Shaowei.Improved dynamic load balancing algorithm based on feed＿back ［J］.Computer Engineering and Design，2007，28 （3）：572－574 （in Chinese）.［田紹亮，左明，吳紹偉.一種改進(jìn)的基于動(dòng)態(tài)反饋的負(fù)載均衡算法 ［J］.計(jì)算機(jī)工程與設(shè)計(jì)，2007，28 （3）：572－574.］

［7］LIU Kun，XIAO Lin，ZHAO Haiyan.Research and optimize of cloud data load balancing in Hadoop ［J］.Microelectronics＆Computer，2012，29 （9）：18－21 （in Chinese）. ［劉琨，肖琳，趙海燕.Hadoop中云數(shù)據(jù)負(fù)載均衡算法的研究及優(yōu)化［J］.微電子學(xué)與計(jì)算機(jī)，2012，29 （9）：18－21.］

［8］LIU Kun，NIU Wenliang.An improved data load balancing algorithm for Hadoop ［J］.Journal of Henan Polytechnic University （Natural Science），2013，32 （3）：332－336 （in Chi－nese）.［劉琨，鈕文良.一種改進(jìn)的Hadoop數(shù)據(jù)負(fù)載均衡算法 ［J］.河南理工大學(xué)學(xué)報(bào) （自然科學(xué)版），2013，32 （3）：332－336.］

［9］LIN Weiwei，LIU Bo.Hadoop data load balancing method based on dynamic bandwidth ［J］.Journal of South China University of Technology （Natural Science Edition），2012，40（9）：42－47 （in Chinese）. ［林偉偉，劉波.基于動(dòng)態(tài)帶寬分配的Hadoop數(shù)據(jù)負(fù)載均衡方法 ［J］.華南理工大學(xué)學(xué)報(bào) （自然科學(xué)版），2012，40 （9）：42－47.］

［10］LIN Weiwei.KNN query technology of mobile terminals in highway networks［J］.Journal of South China University of Technology （Natural Science Edition），2012，40 （1）：152－158 （in Chinese）.［林偉偉.一種改進(jìn)的Hadoop數(shù)據(jù)放置策略 ［J］.華南理工大學(xué)學(xué)報(bào)（自然科學(xué)版），2012，40 （1）：152－158.］