基于Redis單位最大效益自適應遷移策略研究

韋 立，陳珊珊

(1.南京郵電大學 計算機學院，江蘇 南京 210003；2.江蘇省大數據安全與智能處理重點實驗室，江蘇 南京 210003)

1 概 述

為了應對海量數據帶來的挑戰和解決傳統數據庫訪問大規模數據的瓶頸問題，NoSQL[1]型數據庫應運而生。以MongoDB[2]、Redis[3]、Cassandra[4]為代表的NoSQL產品以其高性能、強擴展性和高容錯性受到了人們的青睞，并在數據庫領域掀起了一場新的革命。NoSQL數據庫常常以Key-Value形式存儲，Key-Value存儲技術為應用提供低延時、高可用、可伸縮的數據訪問服務。對于Key-Value存儲系統，數據遷移[5]是實現節點動態擴展與彈性負載均衡[6]的關鍵技術，而Key-Value常用的數據分布策略是一致哈希。一致性哈希可以達到很好的分布式均勻性，并且由于特殊的放置規則，其在節點數據發生變動時可以將影響控制在局部區間內，從而保證非常少的數據遷移。當然，必要的遷移代價必不可少，因此如何有效降低遷移代價、提高遷移效益[7]是Key-Value存儲需著力解決的問題。

Redis從3.0版本開始支持集群功能，集群采用無中心節點方式，實現客戶端直接與Redis集群的每個節點連接，節點之間通過Gossip協議交換互相的狀態和探測節點擴展、刪除信息(見圖1)。Redis集群中有一個長度為16 384的哈希槽，這個槽是虛擬的，并不是真正存在的。正常工作時，Redis集群中的每個節點都會負責一部分的槽，當有某個Key被映射到某個主節點負責的槽，那么這個主節點負責為這個Key提供服務，至于哪個主節點負責哪個槽，可以由用戶指定，也可以在初始化時自動生成。所以，當集群添加節點時，用戶可以從其他節點隨機各抽取一部分槽到新節點，也可以指定某些節點上的槽遷移到新節點。但是目前Redis集群數據遷移操作必須手動進行，而且隨機選擇的遷移方案也并不是最優的。為了實現數據有策略的遷移，文中提出了單位最大效益自適應遷移策略。

圖1 Redis集群無中心節點模式

秦秀磊等[8]提出基于面積的遷移代價模型和開銷敏感遷移算法來完善Key-Value遷移機制。他們用二維空間面積衡量遷移節點之間的遷移代價，任意的遷移代價可用對應的矩形面積來表示，因此將遷移代價選擇轉為矩形面積的選擇。開銷敏感遷移算法基于遷移代價模型，算法每次選擇代價最小的節點進行遷移，這樣選取的遷移策略確實減少了遷移代價，然而開銷敏感遷移算法并沒有考慮數據量的問題，因此選取的遷移方案并不是最優的。通過分析開銷敏感遷移算法存在的不足，文中基于面積遷移代價模型，提出的單位最大效益自適應遷移策略包含兩部分：負載自適應平衡策略和單位最大效益遷移方案。負載自適應平衡策略通過實時判斷集群系統負載情況解決Redis手動遷移的不足，有策略的數據遷移使其靜態存儲均衡化，從而實現系統之間的自適應調控；單位最大效益遷移方案每次優先選擇單位效益最大的節點進行遷移，直至遷移完成。單位最大效益自適應遷移策略主要實現三個過程：數據遷移時機的選擇，即在什么情況下觸發遷移；遷出節點和遷入節點的選擇，即遷出節點和遷入節點的判定；遷移效益的選取，即選取效益最大的遷移方案。

2 單位最大效益自適應遷移策略

2.1 系統負載

對于負載均衡的考慮，模型引入信息熵[9]的概念來衡量集群的負載。假設節點i的負載水平為li，標準化節點負載Pi見式1，平均負載見式2：

(1)

(2)

集群所需要的是節點負載的均勻程度，信息熵完全可以作為系統有序化和均勻程度的一個度量。因此，自適應遷移策略采用信息熵表示集群的負載分布情況，如式3：

(3)

熵值越高，表明負載分布越均勻。當各節點負載相等時，系統取得最大熵值H(P)max=logn。

為了更加直觀地表示負載分布情況，自適應遷移策略還構建了一個均衡度函數F∈(0,1)，即標準化熵值，見式4：

(4)

2.2 自適應平衡策略

為了實現Redis數據有策略的遷移，使其靜態存儲均衡化和負載均衡，構建了一個負載均衡的自適應的數據遷移框架，如圖2所示。

圖2 自適應負載平衡框架

數據信息通過哈希算法[10]將數據分布在各個虛擬節點實現數據的均勻分布；當數據更新時，RedisLive對集群進行實時監測并收集信息。如果整個系統的負載低于均衡度閾值就會觸發數據遷移操作，反之，仍然保持當前狀態；遷移方案的選擇尤為關鍵，遷出遷入節點的選擇和遷移代價的比較等因素都是衡量的重點，統籌這些因素，制定出遷移最大效益的方案；最后，執行數據遷移。

Redis集群通過哈希算法將數據分布在各個虛擬節點實現數據的均勻分布，因此數據可以維持數據平衡。然而，當Redis集群為實現橫向擴展而增加新節點時，平衡策略自適應地將進行有策略的數據遷移。算法1主要包含三個步驟：判斷、挑選、遷移。

Algorithm1：The checkRebalance procedure

procedure checkRebalance(add or remove nodes)

calculateF

ifF

engage(nodes)

do migrationS

return

Else

return

End

判斷：通過信息熵計算方法，集群計算出當前系統的均衡度函數，并預先設定一個閾值。開始階段整個集群系統比較穩定，但是隨著新節點的添加，當前負載平衡系統被打破，觸發節點進行數據遷移，這也是對應了遷移時機的考慮。當F小于閾值，CheckRebalance算法觸發數據遷移操作，自適應調節節點存儲情況。

選?。阂话銇碚f，數據遷移操作不會選擇整體節點進行操作，這樣做目標繁多，而且帶來的開銷也很巨大。因此，文中有目的性地選擇一些需要參加的節點進行數據遷移操作，以大大減少遷移代價。根據信息熵，每個節點i都會有各自的節點負載li和平均負載lavg。于是，所有參加操作的節點分成兩類，分別是遷入節點和遷出節點。當節點i的負載水平lilavg時，節點j歸于MO遷出節點。MI集合中的每個遷入節點會附帶一個排序信息，記錄遷出節點到該節點的單位遷移效益排序，這樣有利于最佳遷移方案遷移節點的選取。

遷移：上面已經確定遷移時機，并選取部分參加的節點進行遷移操作，接著就是選擇最大效益遷移方案。Redis集群數據遷移隨機選擇節點進行數據遷入或者需要手動遷移槽；開銷敏感數據遷移方案(CA)每次選取效益最大的節點遷移；單位效益最大遷移方案(Packet)選擇單位遷移數據量效益最大的節點遷移。通過三種方案的比較，單位最大效益遷移方案的遷移效益最高。

2.3 單位最大效益遷移方案

在數據遷移過程中，為了實現操作的規范性，每個節點的一系列操作可以表示成一個四元組，其中j和i分別表示遷出節點和遷入節點，T表示遷移分區，B表示遷移帶寬。秦秀磊等[8]提出的開銷敏感數據遷移算法計算出使遷移開銷代價最小的帶寬值B以及該節點的最小開銷代價，然后選取開銷代價最小的節點作為遷入節點。該算法雖然每次選擇代價最小的節點進行遷移，但是沒有考慮到數據量的問題，數據量的大小制約節點的重新選擇，局部開銷代價最小并不能保證整體開銷代價最小。因此，很容易將數據遷移節點選擇問題規約為一般背包[11]問題。

在開銷敏感數據遷移算法的基礎上，提出單位效益最大遷移算法。該算法運用貪心準則，每一次遷入節點優先選擇單位效益最大的遷出節點進行數據遷移。在固定遷移數據量的前提下，根據基于面積的遷移代價模型，首先計算節點j到節點i的遷移代價cost(j,i)，遷移代價越小則說明遷移效益越高，所以定義p(j,i)表示節點j到節點i的收益；其次，根據單位遷移效益p(j,i)/wj遞減排序，依次選擇遷出節點，每個遷入節點生成最優方案；最后，將MI集合中每個遷入節點方案匯總成最終數據遷移方案。

p(j,i)=k/cost(j,i)

(5)

圖3為9號遷入節點最優遷移方案生成過程。

圖3 9號遷入節點最佳遷入方案

(1)1～6號節點分配到MO，7～12號節點歸入MI集合。

(2)當9號節點需要數據遷入時，首先分別計算1～6號節點到9號節點的單位遷移效益，然后進行排序(3 1 6 4 5 2)。

(3)優先遷移3號節點數據到9號節點；當3號節點數據遷移完成后，遷移1號節點數據到9號節點；當1號節點遷移完成后，遷移6號節點一半數據到9號節點，至此9號節點飽和，6號節點仍有剩余一半數據遷移到其他節點。

(4)9號遷入節點選擇的遷出節點為(3 1 6)，分別遷入數據量為(1，1，1/2)。

不斷重復上述算法最終得到最優化的遷移方案，當負載均衡的信息熵高于特定閾值，數據遷移結束。

最優遷移方案如算法2所示。

Algorithm2:The optimal scheme for migration

Input:MI_set，MO_set;

Output:MigrationS

Initialize a migrationS,a temporary partition setsT

Letlavgbecome the average load

repeat

mi=lavg-li,i∈MI_set

AddmitoT

for each node inTdo

ifT≠? then

for each node in MI_set do

wj=lj-lavg,j∈MO_set

let cost(j,i)be the cost fromjtoi

p(j,i)=k/cost(j,i)

addp(j,i)/wjtosi

sortsi

update the state ofjandi

else

return

addsitoS

end

untilF>threshold

2.4 貪心法求解

問題描述：數據遷移問題的最優方案S={X1,X2,…,Xi}，n為節點數量，節點i遷移方案可以表示成一個n元組：Xi=(x0,x1,…,xn-1)，0≤xi≤1；mi表示遷入i節點需要遷入的數據量，即mi=lavg-li；wj表示遷出節點j需要遷出的數據量，即wj=lj-lavg；所以約束條件為：

(6)

最優化問題的目標函數用于衡量一個可行解是否是最優解，文中目的是使遷移效益最大，所以最優解使目標函數取最大值：

(7)

定理：如果p0/w0≥p1/w1≥…≥pn-1/wn-1，則式7求得的解是最優解[12]。

證明：設Xi=(x0,x1,…,xn-1)，0≤xi≤1是貪心算法的解。若節點i所有遷出數據量都能遷移到目標節點，即xi=1，則顯然是最優解。不然，則設m是使xm≠1的最小下標。從貪心算法可知，解的形式為：

Xi=(1,…,1,xm,0,…,0),0≤xm<1

(8)

如果Xi不是最優解，而另有可行解Yi=(y0,y1,…,yk,…,yn-1)是最優解，使得

(9)

設k是使得yk≠xk的最小下標，顯然這樣的下標必定存在。下面證明yk

(1)若k

(2)若k=m，則xk是第k個節點能遷入目標節點的最多數據量，從而yk>xk是不可能的。由于yk≠xk，必定有yk

(3)若k>m，這是不可能的，因為xi=0，m

綜上所述，必有xk。

假定以xk替換Yi=(y0,y1,…,yk,…,yn-1)中的yk，則Zi=(z0,z1,…,zk,zk+1,…,zn-1)，替換前zi=yi=xi，0≤i≤k-1，替換后zk=xk。為了保證Zi是可行解，必須滿足：

(10)

這意味著因為第k個節點遷入目標節點的數據由yk增加到xk(即zk)，則需要減少從Yi中第k+1到n-1節點遷入目標節點的數據量，減少的數據量必須等于增加的數據量，即應當滿足式10。經過這樣處理后得到的可行解Zi，其前k個分量均與Xi相同。式11計算說明可行解Zi的效益大于等于假定的最優解Yi的效益：

(11)

重復上面的替換過程，每替換一個分量得到的新可行解，與貪心法的解Xi相比，新增了一個值相等的分量，最終或者得到一個與Xi完全相等的解，或者表明Yi不是最優解。從式11可知，每一次分量得到的新的可行解的效益不小于前一步的可行解。所以，Xi的效益必定不小于Yi的效益，這就證明了貪心法求解得到的數據遷移方案的可行解必定是最優解。

3 實驗評估

在實驗中，采用RedisLive監測整個集群系統，收集節點性能信息以及負載情況。以Redis-3.2.8作為評估標準，探討擴展節點對Redis集群整體性能的影響。表1顯示了實驗的軟件和硬件的配置信息。在4臺服務器上分別部署2～8個Redis節點組，通過不斷增加節點來查看性能情況。單位最大效益遷移算法和Redis集群的遷移以及開銷敏感遷移算法分別從遷移時間、CPU使用率和吞吐量進行比較。采用YCSB(Yahoo! cloud serving benchmark)[13]進行測量。

表1 實驗配置信息

(1)遷移時間。

在實驗過程中，記錄不同數量節點的遷移的開始時間和負載平衡的結束時間，得到三種算法(Redis、CA和Packet)的平均遷移時間。圖4比較了三種算法的遷移時間。當節點數較少時，三種算法遷移時間大致相同，然而隨著節點數的增多，單位最大效益遷移算法越來越優于其他算法。和Redis相比，Packet遷移算法遷移時間優化了6.2%～14.1%，和CA相比，遷移時間減少了4.8%～10.9%?？梢韵胂螅敼濣c較少時，遷移策略節點的選擇基本差不多，導致遷移時間沒有明顯差異，但是當節點較多時，不同遷移策略的選擇會導致不同的遷移結果。

圖4 遷移固定數據量對應的遷移時間比較

(2)CPU使用。

Redis集群不斷添加新的節點，CPU的使用率逐漸加大。圖5給出了三種算法在遷移過程中CPU的使用情況?？梢钥闯?，無論是User使用率還是Idle使用率，單位最大效益遷移算法都是有優勢的。Packet遷移算法可以以最小的CPU使用率獲得最大的遷移效益。當然，隨著節點數的增加，Xu等[14]提到的CPU的使用可能會出現瓶頸，但是文中主要研究遷移策略的選擇，所以這方面不做考慮。

圖5 User和Idle CPU的使用情況

(3)吞吐量。

Redis采用基于內存的單線程KV數據庫，官方顯示吞吐量可以達到105左右[3]。圖6顯示了三種遷移算法吞吐量的對比。吞吐量和遷移時間相似，Packet遷移算法的吞吐量優于其他兩種算法?？梢钥闯?，Packet比Redis提高了4.9%～12.5%，比CA優化了1.8%～6.7%。隨著節點的擴展，Packet遷移算法會逐漸顯示它的優勢，節點越多優勢越明顯。

圖6 吞吐量的比較

4 相關工作

為了解決Key-Value高可擴展問題，Paiva等[15]通過利用本地模式優化副本放置，以減少節點通信代價，于是他們提出兩種新的技術。第一，每個節點以分散的方式優化最能產生數據位置的遠程操作；第二，一致哈希通過結合一種新的數據結構來提供有效的概率數據放置。而Miranda等[16]從數據分片入手，從基于表的、基于規則的和偽隨機的散列策略中吸取經驗，正確評估隨機分片策略，提出一種簡單而高效的大數據處理策略。這種隨機分片策略維護一個表，這個表里保存著之前存儲系統插入和刪除操作的信息，這樣做減少了傳遞完美負載分配時所需的隨機性數量。百萬兆級數據的訪問，更多的Key-Value存儲系統被應用在多核服務器上，常常導致可用帶寬的利用率不足，能源效率不高和重載響應時間變長。為了解決這些問題，Xu等[15]提出了Hippos，一種高吞吐量、低延遲和高效的Key-Value存儲模型。Hippos將KV移到操作系統內核中，從而消除了大量網絡開銷和系統調用。Hippos使用Netfilter框架快速處理UDP數據包，幾乎完全消除了UDP的請求開銷，并結合無鎖多線程數據訪問，Hippos消除了內部和外部的幾個性能瓶頸，大大提高了整體性能。

目前存在的數據庫，像關系型數據庫和Key-Value數據庫因缺少低代價的數據遷移技術，從而制約了數據庫的彈性擴展。Das等[17]提出一種遷移技術，稱為Albatross，該技術中持久的數據庫映像存儲在網絡連接的存儲中，Albatross遷移數據庫通過緩存和活動事物狀態來確保在允許事物時對事務執行的影響最小，同時保證在故障時的正確性。

云服務的普及使得虛擬機技術日益重要，一個重要的特點是虛擬機技術可以用于負載平衡。虛擬機遷移兩個評估標準是總體遷移時間和故障停機時間，目前大多數研究會在兩者之間做出權衡。Zhang等[18]從理論上分析了在保證遷移時間和故障停機時間情況下所需要的帶寬，接著假設一個確定性模型作為一個簡單的例子，這個例子服從伯努利分布，最后在虛擬機運行的工作負載中分析典型的統計特征，并構建基于互惠的工作負載模型，理論上給出滿足實時虛擬機遷移的性能指標所需要的帶寬值。對于負載管理、節能、日常服務器維護和服務設備質量來說，多層應用程序的實時遷移起著至關重要的作用。和單一虛擬機遷移相比，多個虛擬機遷移是緊密相關的，可能導致一系列相關的遷移問題。在云服務中，Liu等[19]設計并實現了一種遷移虛擬機相關好友的協調系統，該系統中提出了一種自適應網絡帶寬分配算法，在遷移完成時間、網絡阻塞和遷移故障時間方面減少遷移代價。

而Basin等[20]則更加系統詳細地介紹了負載均衡策略，提出了一種可以同時支持大規模scans和實時訪問的原子KV映射的KiWi模型。KiWi實現了scans無等待和put無鎖操作，大大提高了處理效率。同時，融入數據結構優化內存管理，通過chunks定期維護內存，改善內部組織和空間利用，實現了數據再平衡過程。KiWi負載再平衡策略分為七個步驟，通過兩個主要函數：rebalance和normalize，利用chunk的三種狀態：infant、normal和frozen，將不平衡數據實現再平衡。

5 結束語

Redis最大效益自適應遷移策略是一種提高Key-Value存儲擴展性的自適應策略，理論分析和實驗證明該策略可以完善Redis集群節點擴展所帶來的不足，提高Redis集群系統的性能。Redis單位最大效益自適應遷移策略有以下兩點優勢：第一，通過實時判斷集群系統負載情況解決Redis手動遷移的不足，有策略的數據遷移使其靜態存儲均衡化，實現系統之間的自適應調控；第二，提出單位效益最大遷移方案來優化遷移策略，此方案每次優先選擇單位效益最大的節點進行遷移，直至遷移完成。

但是，Redis是基于內存的存儲系統，遷移過程中不可避免產生一定的網絡開銷，而如何處理熱點數據是另一個難點。文中著重考慮遷移策略的改進，對于其他因素有待更深入的探究。