莫文導(dǎo) 孫全忠

（廣東省公安廳科技信息化處，廣東廣州510050）

基于改進(jìn)的模糊時(shí)間序列預(yù)測模型的HDFS副本選擇策略

莫文導(dǎo) 孫全忠

（廣東省公安廳科技信息化處，廣東廣州510050）

隨著公安機(jī)關(guān)大數(shù)據(jù)計(jì)算和警務(wù)云平臺(tái)的建設(shè)、推廣，云存儲(chǔ)改變了以往數(shù)據(jù)本地存儲(chǔ)和處理的傳統(tǒng)模式，能夠通過網(wǎng)絡(luò)根據(jù)需求快捷訪問計(jì)算與存儲(chǔ)等服務(wù)。為了滿足云存儲(chǔ)系統(tǒng)的動(dòng)態(tài)性、復(fù)雜性以及實(shí)時(shí)性的要求，本文提出了基于改進(jìn)的模糊時(shí)間序列預(yù)測模型的HDFS副本選擇策略。對模糊時(shí)間序列預(yù)測模型進(jìn)行改進(jìn)，利用改進(jìn)后的模糊時(shí)間序列預(yù)測模型對副本讀取時(shí)間進(jìn)行預(yù)測，并在hadoop平臺(tái)的數(shù)據(jù)訪問實(shí)驗(yàn)，證明了改進(jìn)后的模糊時(shí)間序列預(yù)測模型相比于經(jīng)典模型能夠較好地刻畫云存儲(chǔ)數(shù)據(jù)副本讀取時(shí)間的變化，并在數(shù)據(jù)訪問耗時(shí)方面有明顯的性能提升。

云存儲(chǔ)副本選擇預(yù)測模型模糊時(shí)間序列

隨著大數(shù)據(jù)時(shí)代的到來，越來越多的公安業(yè)務(wù)應(yīng)用場景對數(shù)據(jù)的分析從離線轉(zhuǎn)向在線，而數(shù)據(jù)價(jià)值隨著時(shí)間的流逝而衰減的特點(diǎn)，導(dǎo)致對數(shù)據(jù)處理的實(shí)時(shí)性要求越來越高。云存儲(chǔ)系統(tǒng)作為大數(shù)據(jù)的主要存儲(chǔ)平臺(tái)，應(yīng)滿足大數(shù)據(jù)處理的高速訪問性能的需求。因此，提高云存儲(chǔ)平臺(tái)的數(shù)據(jù)訪問速率，是改進(jìn)大數(shù)據(jù)處理性能，保證數(shù)據(jù)處理和公安科技信息化應(yīng)用系統(tǒng)實(shí)時(shí)性的重要手段。

云存儲(chǔ)系統(tǒng)通過引入副本機(jī)制提高數(shù)據(jù)的可靠性并降低訪問延遲，以HDFS為代表的云存儲(chǔ)系統(tǒng)副本選擇決策機(jī)制，根據(jù)主控節(jié)點(diǎn)（NameNode）統(tǒng)一計(jì)算的結(jié)果，決定讀取哪個(gè)數(shù)據(jù)塊副本（一般為網(wǎng)絡(luò)距離最小的），沒有考慮數(shù)據(jù)節(jié)點(diǎn)負(fù)載、集群內(nèi)部帶寬變化、磁盤IO和多客戶端并發(fā)訪問等因素對數(shù)據(jù)讀取性能造成的影響。導(dǎo)致主控節(jié)點(diǎn)的計(jì)算負(fù)荷大幅度增加，難以控制客戶端的數(shù)據(jù)副本讀取性能和預(yù)測響應(yīng)時(shí)間變化。本文利用預(yù)測的方法來優(yōu)化HDFS副本的選擇策略，在客戶端訪問HDFS副本時(shí)，基于模糊時(shí)間序列預(yù)測模型來選擇HDFS副本，從而減少數(shù)據(jù)訪問時(shí)間和優(yōu)化數(shù)據(jù)訪問性能。

1 改進(jìn)的模糊時(shí)間序列預(yù)測模型

普通時(shí)間序列預(yù)測模型是建立在數(shù)據(jù)完整性、準(zhǔn)確性和確定性基礎(chǔ)上的一種規(guī)律分析方法，對應(yīng)用環(huán)境的要求高，并需要大量的歷史數(shù)據(jù)支撐。而實(shí)際應(yīng)用環(huán)境的復(fù)雜性使得觀測到的數(shù)據(jù)準(zhǔn)確性不高，存在大量無法用精確數(shù)據(jù)表示的模糊變量，導(dǎo)致普通時(shí)間序列預(yù)測模型的實(shí)用性不高。為了解決普通時(shí)間序列預(yù)測模型存在的不足，Song和Chissom［1］［2］在模糊集理論［3］的基礎(chǔ)上提出了第一個(gè)模糊時(shí)間序列預(yù)測模型，并衍生出大量的改進(jìn)模型，但這些模型要么過于復(fù)雜，要么沒有考慮實(shí)際應(yīng)用的數(shù)據(jù)動(dòng)態(tài)性，難以適應(yīng)復(fù)雜而多變的云存儲(chǔ)系統(tǒng)環(huán)境。

為了能在可接受的時(shí)間內(nèi)給出預(yù)測結(jié)果，使得預(yù)測過程的計(jì)算時(shí)間對副本響應(yīng)時(shí)間的影響降到最低，且能夠從新獲取到的訓(xùn)練數(shù)據(jù)里提取有用信息并逐步更新模糊計(jì)算邏輯關(guān)系。本文在Chen［4］模型的基礎(chǔ)上，結(jié)合文獻(xiàn)［5］提出的改進(jìn)方法，對經(jīng)典預(yù)測模型進(jìn)行優(yōu)化調(diào)整。

1.1 論域動(dòng)態(tài)調(diào)整

由于網(wǎng)絡(luò)狀態(tài)、磁盤IO速度、并發(fā)訪問數(shù)等因素均會(huì)對副本響應(yīng)時(shí)間產(chǎn)生影響，云存儲(chǔ)環(huán)境下，長期的數(shù)據(jù)特征穩(wěn)定性較差，經(jīng)典模糊時(shí)間序列預(yù)測模型并不適合對副本響應(yīng)時(shí)間進(jìn)行長期預(yù)測，因此，該模型的預(yù)測應(yīng)用重點(diǎn)應(yīng)放在副本響應(yīng)時(shí)間短期預(yù)測上。

將HDFS集群的副本響應(yīng)時(shí)間歷史數(shù)據(jù)窗口定義為W，大小為|W|=k，k個(gè)時(shí)刻上的時(shí)間序列為W(t)={w1(t),w2(t),…,wk(t)}。由于數(shù)據(jù)離群點(diǎn)（Outlier）會(huì)影響到確定論域、劃分模糊區(qū)間等過程，導(dǎo)致預(yù)測準(zhǔn)確性降低，因此確定論域前，需預(yù)先剔除捕獲訓(xùn)練數(shù)據(jù)的離群點(diǎn)。

本文使用3σ準(zhǔn)則剔除離群點(diǎn)，設(shè)歷史數(shù)據(jù)窗口為W，數(shù)據(jù)平均值為xˉ，標(biāo)準(zhǔn)差為σ，如果W的觀測值中有wp(t)滿足以下條件：wp(t)＜xˉ-3σ或者wp(t)＞xˉ＋3σ，則將滿足條件的wp(t)作為離群點(diǎn)進(jìn)行剔除預(yù)處理。如將預(yù)處理操作后的時(shí)間序列表示為：W′(t)={…,wi(t),wj(t),…,wm(t),…}，則歷史數(shù)據(jù)窗口W上的論域?yàn)閁W=[min(W′(t)),max(W′(t))]。

根據(jù)獲取到的新副本響應(yīng)時(shí)間，動(dòng)態(tài)調(diào)整歷史數(shù)據(jù)窗口W的大小。每當(dāng)獲取到新的響應(yīng)時(shí)間相關(guān)數(shù)據(jù)時(shí)，首先判斷該數(shù)據(jù)值是否處于UW的范圍內(nèi)，若新的響應(yīng)時(shí)間數(shù)據(jù)值處于論域UW內(nèi)，則在歷史數(shù)據(jù)窗口W的末端添加該數(shù)據(jù)值，窗口大小相應(yīng)增加1個(gè)單位，并利用模糊邏輯關(guān)系矩陣更新模型數(shù)據(jù)；若新的響應(yīng)時(shí)間數(shù)據(jù)值不處于論域UW內(nèi)，則從歷史數(shù)據(jù)窗口W中截取||Wmin個(gè)歷史數(shù)據(jù)，和新的響應(yīng)時(shí)間數(shù)據(jù)值共同構(gòu)成新的歷史數(shù)據(jù)窗口，其中，截取歷史數(shù)據(jù)的數(shù)量||Wmin，應(yīng)根據(jù)歷史數(shù)據(jù)窗口大小、論域范圍等具體情況進(jìn)行規(guī)定。新的歷史數(shù)據(jù)窗口確定后，重新執(zhí)行論域調(diào)整、模糊預(yù)測區(qū)間劃分、模糊關(guān)系矩陣生成和更新等過程。

1.2 模糊邏輯關(guān)系矩陣動(dòng)態(tài)更新

由于經(jīng)典預(yù)測模型對模糊邏輯關(guān)系不進(jìn)行多次（重復(fù)）計(jì)算，因此該類模型的模糊邏輯關(guān)系矩陣不能體現(xiàn)由模糊邏輯關(guān)系出現(xiàn)頻繁度產(chǎn)生的影響。本文在重新建立模糊邏輯關(guān)系的權(quán)重矩陣時(shí)，將模糊邏輯關(guān)系出現(xiàn)的頻繁程度作為重要計(jì)算參考因素。

經(jīng)調(diào)整后的模糊時(shí)間序列預(yù)測算法流程如圖1所示。首先，選取最小樣本數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，其中，應(yīng)根據(jù)不同系統(tǒng)規(guī)定的最小樣本個(gè)數(shù)，選取符合系統(tǒng)預(yù)測要求的樣本數(shù)量。其次，對訓(xùn)練數(shù)據(jù)做預(yù)處理，剔除對預(yù)測結(jié)果影響較大的離群數(shù)據(jù)；接著定義樣本論域并劃分模糊區(qū)間。與經(jīng)典模型不同，調(diào)整后的模糊時(shí)間序列預(yù)測算法根據(jù)LEM2規(guī)則［6］來生成模糊邏輯關(guān)系矩陣，并給出最后的預(yù)測結(jié)果，隨后執(zhí)行論域動(dòng)態(tài)調(diào)整過程（見“1.1論域動(dòng)態(tài)調(diào)整”）。

圖1 調(diào)整后的模糊時(shí)間序列預(yù)測算法流程圖

2 基于預(yù)測的副本選擇策略

在改進(jìn)的模糊時(shí)間序列預(yù)測模型算法的基礎(chǔ)上，重新設(shè)計(jì)分布式副本的選擇和讀取策略：

設(shè)R={r1,r2,…rn}表示HDFS集群的文件F中數(shù)據(jù)塊B的候選副本集，候選副本ri響應(yīng)時(shí)間為客戶端C選擇候選副本ri并將其讀取到內(nèi)存的時(shí)間。

當(dāng)安裝了副本選擇服務(wù)的客戶端向HDFS集群主控節(jié)點(diǎn)（NameNode）發(fā)出讀取請求時(shí)，NameNode將擬讀取的數(shù)據(jù)塊副本的位置信息反饋給客戶端，安裝在客戶端上的副本選擇服務(wù)根據(jù)反饋的數(shù)據(jù)塊副本位置信息，區(qū)分相同數(shù)據(jù)塊內(nèi)的不同副本，同時(shí)記錄所有成功訪問的副本響應(yīng)時(shí)間。則基于改進(jìn)的模糊時(shí)間序列預(yù)測模型重新設(shè)計(jì)的數(shù)據(jù)副本選擇和讀取策略如下：

（1）如果客戶端訪問數(shù)據(jù)時(shí)，候選副本集中有新創(chuàng)建的副本，此時(shí)，由于缺少副本響應(yīng)時(shí)間的歷史樣本數(shù)據(jù)，客戶端直接讀取新創(chuàng)建的副本并記錄響應(yīng)時(shí)間；

（2）若存在候選副本集響應(yīng)時(shí)間的歷史樣本數(shù)小于||Wmin的情況，則選擇并讀取訪問次數(shù)最少的副本，記錄響應(yīng)時(shí)間，并納入歷史樣本數(shù)進(jìn)行統(tǒng)計(jì)；

（3）在候選副本集響應(yīng)時(shí)間的歷史樣本數(shù)據(jù)充足的情況下，用調(diào)整后的模糊時(shí)間序列預(yù)測模型，預(yù)測候選副本集中所有副本的響應(yīng)時(shí)間，選擇并讀取預(yù)測響應(yīng)時(shí)間最小的副本，記錄實(shí)際的副本響應(yīng)時(shí)間；

（4）結(jié)合實(shí)際的應(yīng)用系統(tǒng)需求，設(shè)定一個(gè)訪問時(shí)間閥值，當(dāng)副本最近被訪問的時(shí)間超過了閥值，將該副本標(biāo)記為長時(shí)間未被訪問數(shù)據(jù)副本，并當(dāng)作新創(chuàng)建副本進(jìn)行處理。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)環(huán)境與配置

為了驗(yàn)證改進(jìn)的模糊時(shí)間序列預(yù)測模型及其副本選擇策略的有效性，設(shè)計(jì)了一個(gè)Hadoop集群實(shí)驗(yàn)環(huán)境，其中包括1個(gè)NameNode和4個(gè)DataNode，實(shí)驗(yàn)環(huán)境的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)如圖2所示。

圖2 Hadoop集群實(shí)驗(yàn)環(huán)境網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)

實(shí)驗(yàn)環(huán)境中的集群角色（NameNode、DataNode和Client等）使用1個(gè)路由器實(shí)現(xiàn)互聯(lián)，等同于所有節(jié)點(diǎn)均處于同一個(gè)機(jī)架內(nèi)。根據(jù)Hadoop集群的網(wǎng)絡(luò)距離計(jì)算模式，實(shí)驗(yàn)環(huán)境中的2個(gè)節(jié)點(diǎn)相互之間的網(wǎng)絡(luò)距離均為2，符合使用HDFS副本隨機(jī)選擇策略的條件和要求。Hadoop集群實(shí)驗(yàn)環(huán)境中NameNode與DataNode節(jié)點(diǎn)的配置參數(shù)如表1所示。

表1 Hadoop集群實(shí)驗(yàn)環(huán)境節(jié)點(diǎn)硬件配置參數(shù)

由于Hadoop沒有直接操作數(shù)據(jù)塊副本的接口，無法直接測量數(shù)據(jù)塊副本的響應(yīng)時(shí)間，因此，實(shí)驗(yàn)過程采用場景模擬的方式測量并收集副本響應(yīng)時(shí)間。先將實(shí)驗(yàn)環(huán)境中的Hadoop集群默認(rèn)副本因子設(shè)置為1，然后每次僅選擇1個(gè)且與上次不同的DataNode節(jié)點(diǎn)上傳目標(biāo)測試文件，目標(biāo)測試文件大小均為60MB，具有相同的數(shù)據(jù)內(nèi)容，分別命名為TestFiles0~3，重復(fù)4次上傳操作，歷遍所有DataNode節(jié)點(diǎn)后，同時(shí)啟動(dòng)4個(gè)DataNode節(jié)點(diǎn)，在不使用HDFS的Bal?ancer工具平衡各節(jié)點(diǎn)存儲(chǔ)空間利用率的情況下，確保每個(gè)DataNode節(jié)點(diǎn)中存在唯一的目標(biāo)測試文件。

在使用5個(gè)客戶端（Client）不間斷、隨機(jī)訪問集群文件，模擬現(xiàn)實(shí)的集群環(huán)境中網(wǎng)絡(luò)狀態(tài)、磁盤IO速度、并發(fā)訪問數(shù)等影響副本響應(yīng)時(shí)間的場景和因素的情況下，用另外1個(gè)獨(dú)立的客戶端，以2秒的時(shí)間間隔，讀取4個(gè)DataNode節(jié)點(diǎn)上的目標(biāo)測試文件（TestFiles0~3）并記錄響應(yīng)時(shí)間，重復(fù)讀取操作直到獲取足夠的實(shí)驗(yàn)數(shù)據(jù)。

3.2 經(jīng)步驟調(diào)整的模糊時(shí)間序列預(yù)測效果對比

本實(shí)驗(yàn)選取單個(gè)時(shí)間序列前20個(gè)（||Wmin=20）數(shù)據(jù)作為訓(xùn)練數(shù)據(jù)，應(yīng)用經(jīng)典模糊時(shí)間序列預(yù)測算法和調(diào)整后的預(yù)測模型，對從目標(biāo)測試文件（TestFiles0~3）的響應(yīng)時(shí)間序列中隨機(jī)選取的30個(gè)序列進(jìn)行預(yù)測，通過與實(shí)際副本讀取響應(yīng)時(shí)間進(jìn)行對比，得出兩者的預(yù)測效果如圖3、圖4所示。

圖3 經(jīng)典模糊時(shí)間序列模型預(yù)測結(jié)果

圖4 經(jīng)調(diào)整的模糊時(shí)間序列模型預(yù)測結(jié)果

由圖可知，經(jīng)典模糊時(shí)間序列預(yù)測模型難以反映真實(shí)響應(yīng)時(shí)間的趨勢。調(diào)整后的模糊時(shí)間序列預(yù)測模型的預(yù)測結(jié)果雖然具有一定的滯后性，但能夠較好地反映數(shù)據(jù)的變化趨勢，更適合云存儲(chǔ)環(huán)境下副本響應(yīng)時(shí)間的動(dòng)態(tài)預(yù)測。3.3基于預(yù)測的副本選擇策略與隨機(jī)選擇策略

的比較

使用重新設(shè)計(jì)的副本選擇策略，選擇目標(biāo)測試文件（TestFiles0~3）中，預(yù)測響應(yīng)時(shí)間最小的副本進(jìn)行讀取，其預(yù)測效果如圖5所示。

圖5 基于預(yù)測的讀取時(shí)間與隨機(jī)策略讀取時(shí)間對比

由圖可知，經(jīng)過30次的副本讀取比較，重新設(shè)計(jì)的模糊時(shí)間序列預(yù)測模型選取副本讀取時(shí)間為1093.7s，比隨機(jī)選擇副本所耗費(fèi)時(shí)間（1504.2s）減少了410.5s的時(shí)間，平均每個(gè)副本節(jié)省訪問時(shí)間約13.7s，說明重新設(shè)計(jì)的模糊時(shí)間序列預(yù)測模型的副本訪問性能得到了有效提升。

4 結(jié)語

本文針對HDFS在讀取文件時(shí)所采用的副本選擇策略的不足，對經(jīng)典模糊時(shí)間序列預(yù)測模型進(jìn)行了適當(dāng)調(diào)整，提出了基于模糊時(shí)間序列預(yù)測模型的副本選擇策略，并通過Hadoop集群上模擬實(shí)驗(yàn)環(huán)境，驗(yàn)證了基于改進(jìn)的模糊時(shí)間序列預(yù)測方法應(yīng)用在HDFS副本選擇策略時(shí)，可以更好地體現(xiàn)出用戶讀取數(shù)據(jù)的規(guī)律性，獲得更好的數(shù)據(jù)訪問性能，更加適合云存儲(chǔ)系統(tǒng)環(huán)境下動(dòng)態(tài)預(yù)測的需求。

［1］Song,Q.and B.S.Chissom,Forecasting enrollments with fuzzy time series—part I.Fuzzy sets and systems, 1993.54(1):p.1-9.

［2］Song,Q.and B.S.Chissom,Forecasting enrollments with fuzzy time series—part II.Fuzzy sets and systems, 1994.62(1):p.1-8.

［3］Zadeh,L.A.,B.Yuan,and G.J.Klir.Fuzzy sets,fuzzy logic,and fuzzy systems:selected papers by LotfiA.Za?deh.1996:World Scientific Publishing Co.,Inc.

［4］Chen,S.-M.Forecasting enrollments based on fuzzy time series.Fuzzy sets and systems,1996.81(3):p. 311-319.

［5］Teoh,H.J.,et al.,Fuzzy time series model based on probabilistic approach and rough set rule induction for empirical research in stock markets.Data&Knowl?edge Engineering,2008.67(1):p.103-117.

［6］Grzymala-Busse JW.A new version of the rule induc?tion system LERS[J].Fundamenta Informaticae,1997, 31(1):27-39.