[發(fā)明專利]一種基于訪問熱度的時空數(shù)據(jù)服務(wù)調(diào)度方法

有效

• 申請?zhí)枺?/td>: 201410848528.4
• 申請日: 2014-12-29
• 公開（公告）號: CN104580447B
• 公開（公告）日: 2019-04-09
• 發(fā)明（設(shè)計）人: 郭旦懷;杜一;周園春;黎建輝
• 申請（專利權(quán)）人: 中國科學(xué)院計算機網(wǎng)絡(luò)信息中心
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 北京君尚知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11200
• 代理人: 余長江

1.一種基于訪問熱度的時空數(shù)據(jù)服務(wù)調(diào)度方法，其步驟包括：

1)采集服務(wù)系統(tǒng)中各存儲介質(zhì)的參數(shù)，以及服務(wù)系統(tǒng)中各計算節(jié)點的參數(shù)；

2)根據(jù)步驟1)采集的數(shù)據(jù)，編制服務(wù)系統(tǒng)的網(wǎng)絡(luò)拓?fù)鋱D，包括網(wǎng)絡(luò)的結(jié)構(gòu)、網(wǎng)絡(luò)之間的鏈接方式、交換機效率、網(wǎng)絡(luò)各存儲介質(zhì)在網(wǎng)絡(luò)的位置、各計算節(jié)點在網(wǎng)絡(luò)中的位置；

3)根據(jù)所述網(wǎng)絡(luò)拓?fù)鋱D，把時空數(shù)據(jù)進行時空分片，采集并記錄每個時空區(qū)塊的訪問數(shù)據(jù)的訪問熱度；

4)根據(jù)訪問熱度調(diào)整時空數(shù)據(jù)的分布位置，并對計算節(jié)點進行調(diào)度；

步驟4)采用如下的數(shù)據(jù)分布優(yōu)化策略實現(xiàn)：

①集群主計算節(jié)點獲取計算任務(wù)，分析計算任務(wù)所需的數(shù)據(jù)，按照數(shù)據(jù)特征劃分為多個數(shù)據(jù)塊；

②把計算任務(wù)分解為和數(shù)據(jù)塊對應(yīng)的子任務(wù)，每個子任務(wù)完成時間由每個計算節(jié)點完成子任務(wù)的計算時間和數(shù)據(jù)傳輸時間決定；

③根據(jù)數(shù)據(jù)在整個資源放置矩陣中的位置，計算數(shù)據(jù)的遷移所消耗的時間，所需數(shù)據(jù)的遷移時間為：

TTi＝v_i/(r_i+s_i)，

其中v_i為遷移到計算節(jié)點i處的數(shù)據(jù)量，r_i為到計算節(jié)點i處的存儲介質(zhì)的讀寫速率，s_i為數(shù)據(jù)抵達(dá)計算節(jié)點i的傳輸速率；

④獲取每個計算節(jié)點的計算資源情況，計算節(jié)點i處理等量數(shù)據(jù)的執(zhí)行時間為：

式中：V表示要處理的數(shù)據(jù)量，fi表示計算節(jié)點計算核心頻率，ci表示總線速度，mi表示主存儲器速率，IOi表示I/O速率，CCi表示計算節(jié)點核心數(shù)；TCi越小，表示處理數(shù)據(jù)的耗時越短，此計算節(jié)點計算性能越強；計算節(jié)點i的計算性能表示為：

⑤每個計算節(jié)點完成子任務(wù)的時間為計算時間和數(shù)據(jù)傳輸時間的和：

Ti＝TTi+TCi，

計算任務(wù)所分解的子任務(wù)為并行運行，所以完成任務(wù)的時間為耗時最長的子任務(wù)的執(zhí)行時間：

T＝max(Ti)；

⑥計算每個計算節(jié)點計算性能占所有參與計算任務(wù)的計算節(jié)點計算性能的比率，以及每個計算節(jié)點的數(shù)據(jù)傳輸?shù)膸捤嫉谋嚷剩瑸橛嬎阈阅茌^強和傳輸速率較快的計算節(jié)點分配相對較多的數(shù)據(jù)，為計算性能較弱和傳輸速率較慢的計算節(jié)點分配相對較少的數(shù)據(jù)；計算節(jié)點i的性能比率為：

式中：PRi表示計算節(jié)點i的性能比率，k表示所有參與任務(wù)計算的計算節(jié)點數(shù)量；同理計算每個計算節(jié)點傳輸速率占所有計算節(jié)點傳輸速率的傳輸比率：

式中：TRi表示計算節(jié)點i傳輸數(shù)據(jù)的傳輸比率，k表示所有參與任務(wù)計算的計算節(jié)點數(shù)量；TT(i)表示傳輸速率；

⑦使所有子任務(wù)能夠同時完成，即為計算節(jié)點分配的數(shù)據(jù)量占整個計算任務(wù)所需數(shù)據(jù)量的比例等于計算節(jié)點性能比率，也即保證計算節(jié)點的性能比率PRi等于傳輸比率TRi。

2.如權(quán)利要求1所述的方法，其特征在于：所述訪問熱度是指不同的時空區(qū)塊內(nèi)用戶訪問某些服務(wù)的頻度，包括訪問次數(shù)。

3.如權(quán)利要求2所述的方法，其特征在于：通過日志記錄的方法獲得所述訪問熱度。

4.如權(quán)利要求1所述的方法，其特征在于：步驟1)所述存儲介質(zhì)的參數(shù)包括：ID、品牌、介質(zhì)性質(zhì)，容量大小、讀取速度，讀取方式、存儲粒度、可靠性、能耗、使用年限、地理位置、網(wǎng)絡(luò)節(jié)點位置。

5.如權(quán)利要求1所述的方法，其特征在于：步驟1)所述計算節(jié)點的參數(shù)包括：ID、品牌、主頻，CPU個數(shù)、內(nèi)存，本地硬盤大小、硬盤個數(shù)、硬盤性質(zhì)、能耗、使用年限、地理位置、網(wǎng)絡(luò)節(jié)點位置。

6.如權(quán)利要求5所述的方法，其特征在于：對于PRi不等于TRi的情況，采用改進的輪循算法求解最優(yōu)分配：比較性能比率和傳輸比率，以它們的最小值為每個計算節(jié)點分配數(shù)據(jù)量，設(shè)定剩余數(shù)據(jù)量的閾值，此閾值是數(shù)據(jù)的最小單元或者數(shù)據(jù)總量的百分比，比較剩余數(shù)據(jù)量和此閾值的大小，如果剩余數(shù)據(jù)量大于這個閾值則將剩余數(shù)據(jù)重新進行下一輪分配；如果剩余數(shù)據(jù)量小于此閾值，則將剩余數(shù)據(jù)分配給執(zhí)行效率最快的一個或多個計算節(jié)點。

7.如權(quán)利要求6所述的方法，其特征在于，所述求解最優(yōu)分配的具體方法是：

首先，計算每個計算節(jié)點分配的數(shù)據(jù)量：

n_i1＝n₀·min(PRi，TRi)，

式中n_i1為計算節(jié)點i在第一輪中分配的數(shù)據(jù)量，n₀為計算過程所需的數(shù)據(jù)總量，經(jīng)過第一輪的分配，剩余的數(shù)據(jù)量為：

式中k表示所有參與任務(wù)計算的計算節(jié)點數(shù)量；

然后，比較剩余數(shù)據(jù)量n_r1和閾值的大小，如果小于閾值，則停止輪循，將剩余數(shù)據(jù)分配給min(PRi，TRi)最大的一個或者多個計算節(jié)點；如果大于閾值則按照第一輪分配方法進行第二輪分配，每個計算節(jié)點分配數(shù)據(jù)量為：

n_i2＝n_r1·min(PRi，TRi)，

比較剩余數(shù)據(jù)量n_r2和閾值的大小，以此類推，直到剩余數(shù)據(jù)量小于閾值為止；每個計算節(jié)點分配的數(shù)據(jù)量n_i為每一輪數(shù)據(jù)分配數(shù)據(jù)量的和：

n_i＝n_i1+n_i2+…+n_ic，

式中c為數(shù)據(jù)分配輪循次數(shù)。