[發(fā)明專利]基于虛擬節(jié)點存儲優(yōu)化的Swift負(fù)載均衡方法

有效

• 申請?zhí)枺?/td>: 201610171589.0
• 申請日: 2016-03-24
• 公開（公告）號: CN105657064B
• 公開（公告）日: 2019-03-12
• 發(fā)明（設(shè)計）人: 楊鵬;趙丹丹;袁志偉;劉旋
• 申請（專利權(quán)）人: 東南大學(xué)
• 主分類號: H04L29/08
• 分類號: H04L29/08
• 代理公司: 南京蘇高專利商標(biāo)事務(wù)所(普通合伙) 32204
• 代理人: 李玉平

1.一種基于虛擬節(jié)點存儲優(yōu)化的Swift負(fù)載均衡方法，其特征在于，包括如下步驟：

(1)與虛擬節(jié)點相關(guān)參數(shù)的初始化；為了達(dá)到存儲負(fù)載均衡的效果，Swift存儲系統(tǒng)需要記錄虛擬節(jié)點的相關(guān)參數(shù)，包括虛擬節(jié)點的相對空閑度、虛擬節(jié)點所屬類別、虛擬節(jié)點類別鏈表、虛擬節(jié)點的組別數(shù)、虛擬節(jié)點所屬組別號；在Swift存儲系統(tǒng)開始運(yùn)行時，需要對這些參數(shù)進(jìn)行初始化；

(2)對象的存儲過程；該過程將主要根據(jù)系統(tǒng)中虛擬節(jié)點是否已經(jīng)進(jìn)行過分組，而分情況實施；若系統(tǒng)中虛擬節(jié)點尚未進(jìn)行過分組，緊接著判斷采用虛擬節(jié)點分組時間點判別方法，判斷當(dāng)前時刻是否需要對虛擬節(jié)點進(jìn)行分組；如果無需分組，直接進(jìn)行對象存儲；如果需要分組，則先按照虛擬節(jié)點的分組過程對虛擬節(jié)點進(jìn)行分組；一旦系統(tǒng)中虛擬節(jié)點進(jìn)行過分組，判斷對象被映射到的分組是否能夠存儲該對象；如果能夠存儲，將對象存儲在合適的存儲服務(wù)器；否則，先按照分組合并過程將對象被映射到的分組與另一個分組進(jìn)行合并，然后在合并后的分組中完成對象存儲；

(3)對象的檢索過程；當(dāng)系統(tǒng)收到讀取某一對象的請求時，首先根據(jù)Swift中的Ring環(huán)找到該對象對應(yīng)的虛擬節(jié)點，然后查詢該虛擬節(jié)點所對應(yīng)的存儲服務(wù)器；如果在存儲服務(wù)器中找到所請求的對象，則直接讀取；否則，先找出該虛擬節(jié)點所在的分組，然后遍歷分組內(nèi)所有虛擬節(jié)點對應(yīng)的存儲服務(wù)器，直至找到所請求的對象；

系統(tǒng)運(yùn)行時需要設(shè)置與虛擬節(jié)點的相關(guān)參數(shù)，這些參數(shù)主要包括：虛擬節(jié)點的相對空閑度、虛擬節(jié)點所屬類別、虛擬節(jié)點類別鏈表、虛擬節(jié)點的組別數(shù)、虛擬節(jié)點所屬組別號；

虛擬節(jié)點的相對空閑度；設(shè)Ring環(huán)上共有n個虛擬節(jié)點，編號為i,0≤i≤n-1的虛擬節(jié)點Vn_i的相對空閑度RF_i是指其剩余空間占總存儲空間的百分比，取值范圍為區(qū)間[0％,100％]；具體采用公式1進(jìn)行計算：

其中，表示編號為i的虛擬節(jié)點Vn_i的存儲空間大小，m_i表示編號為i的虛擬節(jié)點目前已存儲的對象個數(shù)，M_j表示編號為i的虛擬節(jié)點存儲的第j個對象的大小，0≤j≤m_i；當(dāng)編號為i的虛擬節(jié)點新增一個大小為a的存儲對象時，則其相對空閑度RF_i采用公式2進(jìn)行更新：

用長度為n的數(shù)組Vnode_left_percentage來記錄Ring環(huán)上n個虛擬節(jié)點的相對空閑度，其中Vnode_left_percentage[i]表示編號為i的虛擬節(jié)點的相對空閑度，初始化時將該數(shù)組所有元素初值設(shè)為100％；

虛擬節(jié)點所屬類別；設(shè)類別數(shù)目為cn，首先將相對空閑度取值區(qū)間[0％，100％]劃分成cn個等間隔的子區(qū)間，得到cn個子區(qū)間，記為子區(qū)間cn-1、子區(qū)間cn-2、…、子區(qū)間0；相對空閑度落在同一子區(qū)間中的所有虛擬節(jié)點視為同一類別，則總共得到cn個類別，記為類別cn-1、類別cn-2、…、類別0；用長度為cn的數(shù)組Vnode_counts_by_key來記錄屬于某一類別的虛擬節(jié)點個數(shù)；該數(shù)組在初始化時Vnode_counts_by_key[cn-1]＝n，其余數(shù)組元素全為0；

虛擬節(jié)點類別鏈表；用cn個鏈表List₀，List₁，…存儲屬于對應(yīng)類別號下的所有虛擬節(jié)點編號；在初始化時，List_cn-1中存儲虛擬節(jié)點編號0、1、2、…、n-1，其他cn-1個鏈表均初始化為空表；

虛擬節(jié)點的組別數(shù)；用參數(shù)gn表示所有虛擬節(jié)點的當(dāng)前分組總數(shù)，在初始時其值設(shè)為0，表示初始時尚未進(jìn)行虛擬節(jié)點分組；某一時刻系統(tǒng)中所有g(shù)n個組別記為分組0、分組1、…、分組gn-1，并且用VNG₀、VNG₁、…、VNG_gn-1表示屬于這些分組的虛擬節(jié)點編號集合；

虛擬節(jié)點所屬組別號；用長度為n的數(shù)組Vnode_map記錄各虛擬節(jié)點所屬的組別號，Vnode_map[i]代表編號為i的虛擬節(jié)點所屬的組別號；該數(shù)組在初始化時將所有元素置為-1；

在對象的存儲過程中，若系統(tǒng)中虛擬節(jié)點尚未進(jìn)行過分組，需要判斷當(dāng)前時刻是否是對虛擬節(jié)點進(jìn)行分組的時間點；

確定虛擬節(jié)點分組時間點的標(biāo)準(zhǔn)是：保證每個分組至少包含兩種類別的虛擬節(jié)點，并且在同一分組中屬于一種類別的虛擬節(jié)點只有1個；在系統(tǒng)開始運(yùn)行后的短期內(nèi)，所有虛擬節(jié)點的相對空閑度值將集中在一個子區(qū)間，即所有虛擬節(jié)點都屬于一個類別，此時不滿足虛擬節(jié)點分組時間點的鑒別標(biāo)準(zhǔn)；在系統(tǒng)運(yùn)行一段時間之后，當(dāng)系統(tǒng)收到對象存儲請求時，采用如下方法判別當(dāng)前時刻是否是對虛擬節(jié)點進(jìn)行分組的合理時間點：

(1)創(chuàng)建與Vnode_counts_by_key相同的數(shù)組Vnode_counts_by_key_bk，將當(dāng)前Vnode_counts_by_key中的值復(fù)制到Vnode_counts_by_key_bk中；

(2)遍歷數(shù)組Vnode_counts_by_key_bk，選出非零的最小值Min_count，然后將Vnode_counts_by_key_bk中所有非零元素都減去Min_count；

(3)若此時數(shù)組所有元素都為0，則返回True，結(jié)束；若此時數(shù)組只有一個元素不為0，其余都為0，則返回False，結(jié)束；否則轉(zhuǎn)至步驟(2)；

若上述步驟(3)返回True，表示當(dāng)前時刻是對虛擬節(jié)點進(jìn)行分組的時間點，則按照以下的虛擬節(jié)點分組過程進(jìn)行分組；若返回False，則意味著當(dāng)前時刻不需要為虛擬節(jié)點分組；

在對象的存儲過程中，一旦當(dāng)前時刻被判定為虛擬節(jié)點分組時間點，就需要對虛擬節(jié)點進(jìn)行分組；分組的具體過程如下：

(1)定義長度為cn的布爾型數(shù)組CBool，其cn個元素均初始化為0；

(2)從數(shù)組Vnode_counts_by_key中選出非零最小值，賦給臨時變量mc；同時對于該數(shù)組中每一個值非零的元素所對應(yīng)的類別j，0≤j≤cn-1，設(shè)置CBool[j]＝1；

(3)建立mc個字典結(jié)構(gòu)G_gn，G_gn+1，…，G_gn+mc-1，它們代表新增加的mc個分組；每個字典結(jié)構(gòu)包含多個字典元素，每個字典元素是一個“key:value”對，“key:value”對為鍵值對，其中鍵為類別號，值為與該類別號對應(yīng)的虛擬節(jié)點類別鏈表；

(4)遍歷布爾型數(shù)組CBool，對于其中每一個值為1的數(shù)組元素CBool[k]，進(jìn)行如下操作：首先建立mc個字典元素DE_(k,0)，DE_(k,1)，…，DE_(k,mc-1)；然后從虛擬節(jié)點類別鏈表List_k中依次取出mc個虛擬節(jié)點編號，不妨記為Vn₀、Vn₁、…Vn_mc-1，將它們分別加入字典元素DE_(k,0)，DE_(k,1)，…，DE_(k,mc-1)中，即在每個字典元素的虛擬節(jié)點編號鏈表中加入1個虛擬節(jié)點編號；最后將這mc個字典元素對應(yīng)加入到mc個字典結(jié)構(gòu)G_gn，G_gn+1，…，G_gn+mc-1中，即把編號為Vn_t，0≤t≤mc-1的虛擬節(jié)點加入新的分組gn+t，同時對數(shù)組Vnode_map進(jìn)行更新，Vnode_map[Vn_t]＝gn+t；

(5)對數(shù)組Vnode_counts_by_key進(jìn)行更新，使該數(shù)組中所有非零元素的值都減去mc；

(6)對虛擬節(jié)點組別數(shù)gn進(jìn)行更新，gn＝gn+mc；

(7)若此時Vnode_counts_by_key數(shù)組中元素不全為0，則跳轉(zhuǎn)至步驟(2)；否則，結(jié)束分組，同時保存由gn個字典結(jié)構(gòu)組成的集合G＝{G₀，G₁，…，G_gn-1}，它的元素包含了gn個分組的信息；

在存儲對象的過程中會導(dǎo)致分組合并；當(dāng)某個分組內(nèi)所有虛擬節(jié)點的相對空閑度都比較低時，需要在所有分組中選出一個負(fù)載較低的分組，與該分組進(jìn)行合并；設(shè)在當(dāng)前時刻，分組m，0≤m≤gn-1，該分組由字典結(jié)構(gòu)G_m描述，對應(yīng)虛擬節(jié)點編號集合VNG_m，需要與另一個分組進(jìn)行合并，具體方法如下：

(1)遍歷除分組m外的所有分組，找出其中包含有當(dāng)前相對空閑度最大的虛擬節(jié)點的一個分組k，0≤k≤gn-1且k≠m；

(2)將分組m中的所有虛擬節(jié)點都加入分組k，相對應(yīng)地將字典結(jié)構(gòu)G_m中所有字典元素并入字典結(jié)構(gòu)G_k；在并入時，若兩個字典元素的key值相同，則只保留一個字典元素，并且需要將它們的value部分進(jìn)行合并；

(3)刪除G_m，并將組別號大于m的所有分組的組別號減去1，同時對數(shù)組Vnode_map中虛擬節(jié)點所屬組別號進(jìn)行對應(yīng)更新；

(4)最后對虛擬節(jié)點組別數(shù)gn進(jìn)行更新，gn＝gn–1。