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

有效

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

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

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

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

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

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

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

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

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

虛擬節(jié)點所屬類別；設類別數目為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的數組Vnode_counts_by_key來記錄屬于某一類別的虛擬節(jié)點個數；該數組在初始化時Vnode_counts_by_key[cn-1]＝n，其余數組元素全為0；

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

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

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

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

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

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

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

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

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

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

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

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

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

(4)遍歷布爾型數組CBool，對于其中每一個值為1的數組元素CBool[k]，進行如下操作：首先建立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個字典元素對應加入到mc個字典結構G_gn，G_gn+1，…，G_gn+mc-1中，即把編號為Vn_t，0≤t≤mc-1的虛擬節(jié)點加入新的分組gn+t，同時對數組Vnode_map進行更新，Vnode_map[Vn_t]＝gn+t；

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

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

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

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

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

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

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

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