一種基於副本響應時間預測的副本選擇方法

2023-11-03 03:32:32 1

一種基於副本響應時間預測的副本選擇方法
【專利摘要】本發明公開了一種基於副本響應時間預測的副本選擇方法，相比現有的副本響應時間預測算法，本發明提出的方法著重考慮不同時刻的副本響應時間的取樣值對於副本響應時間的預測影響度是不同的。離預測點越近的樣本的權重值越大，反之，權重值越小。這樣的模型解決了影響因素在不同的時期對副本響應時間的影響程度不同的問題，提高了預測的精度。
【專利說明】一種基於副本響應時間預測的副本選擇方法

【技術領域】
[0001] 本發明涉及雲環境中的副本選擇方法，尤其涉及一種基於副本響應時間預測的副 本選擇方法。

【背景技術】
[0002] 隨著Internet技術的快速發展，網際網路上數據如海嘯般迎面撲來，這直接反映出 人類處理數據能力的相對匾乏。當前，面對異常龐大的數據需要有效的管理辦法。這一問 題的核心是無法控制的數據增長和低下的資源利用率。
[0003] 雲存儲（cloud storage)是在雲計算（cloud computing)的概念上延伸和發展出 來的一個新概念，從一出現就一直是研究的熱點。下一代網際網路給存儲提出了更高的要求， 存儲系統面臨了以下幾個方面新的挑戰。（1)存儲容量需求更大；（2)存儲系統的性能更 強；（3)存儲系統安全性級別要求更高；(4)存儲系統進一步智能化。雲存儲在這樣的環境 下被提出。在雲存儲系統中，數據副本是其重要的組成部分。副本的引入一方面提高了數 據的安全性和可用性，另一方面，也帶來了副本訪問時最優副本的選擇問題。
[0004] 副本選擇過程中需要考慮的幾個因素：
[0005] 1)距離：副本請求者距離副本所在宿主之間的距離（hops);
[0006] 2)宿主節點的訪問速度：宿主節點（host node)具有可用性（availability)，能 夠穩定的為副本請求者提供服務；這裡的可用性包括宿主節點的被訪問時的反應速度，用 戶在進行訪問時，要先從存有數據副本的存儲節點上將文件讀取出來，在進行下一步的處 理，所以存儲節點的訪問速度是非常重要的。
[0007] 3)帶寬：計算機網絡的帶寬是指網絡可通過的最高數據率，即每秒多少比特。數 據副本所在宿主節點和用戶之間的帶寬。帶寬是數據副本選擇的首要因素。在進行數據副 本選擇時，一般是選擇延遲最小的鏈路進行數據訪問。
[0008] 4)計算節點的計算速度：在進行副本選擇時，計算節點通過計算查詢副本位置， 進行任務調度時，均需要計算節點的處理能力。
[0009] 5)宿主節點的負載情況：當存在多個用戶訪問某一雲存儲節點上的相同數據副 本時，該節點的負載也是影響用戶訪問速度的又一因素。負載比較低時可能儘快的為用戶 提供服務，當訪問的節點負載比較重時，則需要用戶的訪問請求進行排隊等待。
[0010] 由此可見副本的選擇影響因素眾多，要一一考慮過程也是相當複雜的一件事。上 述五個影響因素，在雲環境中我們可以簡化為一個考量點：數據副本的響應時間（Replica Response Time)，即從請求者發出請求信息開始到最終用戶請求得到滿足的這一段時間。 因此，如果可以通過預測未來第N+1次的副本響應時間，N表示副本已經有歷史N次的訪問 記錄，用戶便可以參照副本的響應時間，選擇副本響應最短的副本進行訪問。
[0011]目前，研究者也有對副本的響應時間進行預測的實例，其通過副本定位的方式發 現用戶所需的所有可選的數據副本。用戶節點動態整理可選數據副本最近N次的歷史訪問 信息，通過建立最簡單的灰色預測模型來預測第N+1次的副本響應時間。然而這樣的方式 並沒有充分考慮每一次的副本響應時間對於預測的影響程度的不同，整個預測不嚴密。因 為越靠近預測點的副本響應時間樣本值對於用戶行為的預測的影響程度是越大的，不能一 概而論。


【發明內容】

[0012] 為解決上述技術問題，本發明採用如下技術方案：
[0013] 一種基於副本響應時間預測的副本選擇方法，其包含如下步驟：
[0014] 步驟一、對於用戶請求過的同一個數據副本，判斷伺服器中是否有n*N次的數據 副本的訪問記錄，η為取樣樣本的所在的總時間段數，N為每個取樣時間段中的取得N次副 本響應時間值。如果有，轉步驟二；否則轉步驟五；
[0015] 步驟二、取主伺服器端的η個不同時間段，每一個時間段取Ν次副本響應時間，計 算每一次對同一副本的響應時間，得到{ti.j.u+pti.j.u、…、ti.j.mhti.j.u表示對文件i的 數據塊j的副本R的第N次訪問的副本響應時間；
[0016] 步驟三、使用預測算法計算t時刻取得N次樣本的每一次的權值β f(t)，f表示副 本第f次被訪問，f e {1，2,3...，N}。根據公式（1)計算yt，即預測點t時刻第N+1次的副 本響應時間。
[0017] yt = β 〇 (t) + β ! (t) Xi+ β 2 (t) x2+,... + β f (t) xf (1)
[0018] 在不同的f下，β的取值不同。xf表示副本SFp DBj. Replica1?在第f次被訪問時 的副本響應時間。N表示每個取樣時間段共取N次副本響應時間值，y t表示預測點t時刻 的被訪問副本的副本響應時間。
[0019] 離預測點t時刻越近的副本響應時間取樣值對預測影響越大，否則，影響相對小 些。其中公式（2)中的w(t)來調節權重，以衡量不同時間段的取樣值對預測點的影響程度。 加權最小二乘估計就是求β ο, β u . . .，β f，使得公式（2)尚差平方和Qt最小。
[0020]

【權利要求】
1. 一種基於副本響應時間預測的副本選擇方法，其包含如下步驟： 步驟一、對於用戶請求過的同一個數據副本，判斷伺服器中是否有n*N次的數據副本 的訪問記錄，η為取樣樣本的所在的總時間段數，N為每個取樣時間段中的取得N次副本響 應時間值；如果有，轉步驟二；否則轉步驟五； 步驟二、取主伺服器端的η個不同時間段，每一個時間段取Ν次副本響應時間，計算每 一次對同一副本的響應時間，得到{ti.j.mti.j.p、…、ti.j.mhti.j.u表示對文件i的數據 塊j的副本R的第N次訪問的副本響應時間； 步驟三、使用預測算法計算t時刻取得N次樣本的每一次的權值β f(t)，f表示副本第 f次被訪問，f e {1，2, 3. . .，N};根據公式⑴計算yt，即預測點t時刻第N+1次的副本響 應時間； yt = β 〇 (t) + β ! (t) Xi+ β a (t) χ2+,... + β f (t) xf (1) 在不同的f下，β的取值不同；xf表示副本SFp DBj. Replica1?在第f次被訪問時的副 本響應時間；N表示每個取樣時間段共取N次副本響應時間值，yt表示預測點t時刻的被訪 問副本的副本響應時間； 離預測點t時刻越近的副本響應時間取樣值對預測影響越大，否則，影響相對小些；其 中公式（2)中的w(t)來調節權重，以衡量不同時間段的取樣值對預測點的影響程度；加權 最小二乘估計就是求β ο, β u . . .，β f，使得公式（2)尚差平方和Qt最小；
(2) Xnf表示副本副本在第η個取樣時間段第f次副本被訪問時的副本響應時間取值；β f 表示副本第f次被訪問時的副本響應時間對預測點的第N+1次副本的響應時間的影響權 值； 步驟四、以上步驟一?三，針對某一個源數據SFi.DBj的某一個數據副本SFi.DBj. ReplicaK，取歷史η個時間段的進行取樣，每個時間段取N次的副本響應時間值，求預測點t 時刻的第N+1次副本響應時間;重複以上步驟一?三，計算出同一源數據的不同副 本的副本響應時間 ti.j」-N+1，ti.j.2-N+1，…，ti.j.K- N+1,…，ti.j.r-N+1，R e {1，2,…，r}，r 為 SFi. DBj的副本總數；從中挑選出tmN+1最小的副本進行訪問； 步驟五、若主伺服器中沒有此副本，則創建副本並進行訪問；否則選擇被訪問最頻繁的 副本進行訪問，即主伺服器的時間戳記錄中出現最頻繁的副本。
2. 根據權利要求1所述的一種基於副本響應時間預測的副本選擇方法，其步驟二中的 副本響應時間計算方法如下： 步驟1、用戶向伺服器發出對於文件i的數據塊j的請求消息messagei.D^ju^^，X表 示用戶對數據塊SFy DBj第X次訪問，消息的時間戳就此生成：TimestamPi. j_x(rapressage;); 步驟2、伺服器接到用戶請求消息，將請求消息的時間戳記錄下來；分析請求消息並查 詢到相應源數據的副本，查詢完畢後便循著原路徑向用戶回復消息message^^^，消息 中附有相關副本的詳細信息； 步驟3、用戶接收到伺服器發回的反饋，便選擇伺服器上的宿主節點進行訪問，訪問完 畢後，向伺服器發出確認消息message^, x(_eived);此時伺服器再一次將相應的時間戳記錄 卜 Τ----θstiinip]· _ u Y; 步驟4、伺服器端將每個副本對應的每一次被訪問時TimestamPi. j_x(Mqme;ssage;)和 Timestampi j K x(received琴）求其差值，便得到副本的響應時間ti j K x : ti.j.R-X Τ--ΙΙΘβ?ΒΠ?ρ^ j E x(receivedmessage) Τ--ΙΙΘβ?ΒΠ?ρ^ j_s(reqmessage) ? (3) 步驟5、基於以上的步驟，同一個數據塊的不同副本歷史N次的副本響應時間便被記錄 下來在伺服器端；tmx表示第X次訪問SFy DBj. Replica1?的響應時間。
3. 根據權利要求1所述的一種基於副本響應時間預測的副本選擇方法，其步驟三的具 體求解過程如下：
(4) 貝lj X β = Y, A = ⑴，Y為取樣的η個時間段每個時間段第N+1次副本響應時間 的實際值的列矩陣；免表示t時刻副本第Ν+1次副本響應時間的估計值f e {1，2, 3...，Ν}， X(t)為X在t時刻的觀察值，β (t)表示t時刻N次的副本被訪問時副本響應時間對預測 點t時刻第N+1次副本的響應時間的影響權值；
(5) Qt表示公式（2)的離差平方和，xnf表示副本在第η個取樣時間段中第f次副本被訪問 時的副本響應時間值；β f表示第f次副本被訪問時副本響應時間對預測點的第N+1次副本 響應時間的權值； 由
(6) δ β (t)表示t時刻副本取樣值的偏差
表示對S β (t)求一階導數； 可得方程 XTff(t)X^ (t) = XTff(t)Y (7) 方程有不唯一的解，其任一解就是/?)，表示t時刻所取的f次副本響應時間權值矩 陣；
得到 (8) (9) 滬表示η個取樣時間段的平均離差平方和。
4. 根據權利要求3所述的一種基於副本響應時間預測的副本選擇方法步驟三中不同 取樣時間段權重的計算方法如下： W(t) = diaghjt)，w2(t),. . .，wn(t))，W(t)表示所取的η個副本取樣時間段每個時間 段的取樣值對預測點副本響應時間的影響權重矩陣，具體過程如下：

此處利用以下方法法求取 1) 假定Θ為定量 2) 由公式⑶計算
Y(quf)為 X，Y去除第f行數據後的數據；根據公式（1)可以得到夕=1(/)*戌/), X(t)為X的第t行 向量，實際值與預測值的誤差我們表示為
3) 計算
?表示實際值與預測值的差值； 4) 計算Θ，使得CV( Θ ) = min(CV)，即使得實際值與預測的誤差最小的情況下，求取此 時的Θ值。
【文檔編號】H04L29/08GK104113590SQ201410305765
【公開日】2014年10月22日 申請日期:2014年6月30日 優先權日:2014年6月30日
【發明者】徐小龍, 邵軍, 章韻 申請人:南京郵電大學