一種基于通配規(guī)則的服務(wù)器動態(tài)負載均衡設(shè)計

夏仕俊

（國網(wǎng)上海市電力公司信息通信公司，上海 200120）

搜索引擎、Web網(wǎng)站、社交網(wǎng)絡(luò)等大型的在線網(wǎng)站經(jīng)常需要使用多臺服務(wù)器以滿足大量用戶的并發(fā)訪問，同時提高服務(wù)可靠性，對于這些網(wǎng)站來講，負載均衡幾乎是一種必不可少的技術(shù)。目前使用的負載均衡常使用使用的方案有：均等地轉(zhuǎn)發(fā)客戶端請求［1，2］；記錄服務(wù)器狀態(tài)，并根據(jù)服務(wù)器負載動態(tài)分配請求轉(zhuǎn)發(fā)。這種負載均衡機制都增加了額外的硬件成本并缺少可定制性。

本文提出的優(yōu)化方案可降低單一負載均衡設(shè)備的成本和復雜性，在不需要調(diào)整服務(wù)器的基礎(chǔ)上，該方案允許網(wǎng)絡(luò)拓撲的靈活性配置，其計算復雜度與客戶端請求的數(shù)量成線性比例。

OpenFlow［3，4］作為高速網(wǎng)絡(luò)下的流量轉(zhuǎn)發(fā)解決方案，吸引了很多服務(wù)商的關(guān)注。OpenFlow最初的設(shè)計和實現(xiàn)使用一個單一的控制器來保證較低的復雜度。通過在控制器中運行的控制層程序，它可以控制交換機在高速數(shù)據(jù)層的基礎(chǔ)上轉(zhuǎn)發(fā)數(shù)據(jù)流量。通過運用OpenFlow，嵌入式服務(wù)系統(tǒng)［5］能夠自適應(yīng)地根據(jù)當前的網(wǎng)絡(luò)和服務(wù)器負載分發(fā)客戶端請求，該系統(tǒng)攔截每一個客戶端請求的第一個數(shù)據(jù)包，匹配獨立的獨立轉(zhuǎn)發(fā)規(guī)則，并將后續(xù)的數(shù)據(jù)包做響應(yīng)轉(zhuǎn)發(fā)。雖然嵌入式服務(wù)系統(tǒng)根據(jù)當前的負載狀態(tài)提供了自適應(yīng)的靈活性，但它擴展性有限，每一個客戶端連接安裝了轉(zhuǎn)發(fā)規(guī)則程序的方案將帶來其它開銷及延遲。隨著轉(zhuǎn)發(fā)規(guī)則的增多，這種開銷將越發(fā)嚴重。

本文設(shè)計的可擴展網(wǎng)絡(luò)負載均衡器主動地收集服務(wù)器負載數(shù)據(jù)，并在轉(zhuǎn)換器上自動生成配置通配規(guī)則，不需引入控制器的前提下實現(xiàn)應(yīng)答高并發(fā)的客戶端請求，重新分配網(wǎng)絡(luò)負載也不復雜。這樣使用的通配規(guī)則解決了兩個問題：針對目標網(wǎng)絡(luò)分配流量負載生成一組有效的規(guī)則集，以及保證在相同TCP連接下，經(jīng)過規(guī)則變化調(diào)整，數(shù)據(jù)包可被傳送至同一個服務(wù)器上。本文設(shè)計的負載均衡屬于集中式控制程序，因此可確定其最優(yōu)的通配規(guī)則［6］。在分發(fā)流量方面提供高轉(zhuǎn)發(fā)速率，具備一定的靈活性，并且在不調(diào)整客戶端或服務(wù)器的前提下，支持根據(jù)網(wǎng)絡(luò)負載分配情況進行定制化設(shè)置。

1 方案介紹

如圖1所示，數(shù)據(jù)中心由多臺服務(wù)器和連接客戶端的路由網(wǎng)關(guān)組成，每一臺服務(wù)器對外提供相同服務(wù)。每一臺服務(wù)器擁有獨立IP，并被賦予處理客戶端請求的權(quán)重比例。例如，圖1中的初始配置S1，S2所占權(quán)重為1／4，S3服務(wù)器處理3／8的請求，S4處理1／8請求。客戶端通過網(wǎng)關(guān)只需要訪問一個對外IP以獲取相應(yīng)服務(wù)。負載均衡器根據(jù)權(quán)重客請求數(shù)據(jù)轉(zhuǎn)發(fā)至目標的服務(wù)器時，會重寫目標IP地址。同時通配規(guī)則更新模塊會收集服務(wù)器的CPU使用率情況，動態(tài)更新轉(zhuǎn)發(fā)規(guī)則中的服務(wù)器的處理請求比例。本節(jié)首先描述OpenFlow的特征；接著闡述生成通配規(guī)則的分隔算法，該算法用以平衡負載；然后解釋該算法的優(yōu)點；最后展示了實現(xiàn)該算法的原型系統(tǒng)。

圖1 OpenFlow實現(xiàn)負載均衡架構(gòu)

OpenFlow提供了一套與其它路由器交互控制程序的API接口，路由器僅包含一個加載了流表的轉(zhuǎn)發(fā)層，一個流表中就包含了一系列定義某個數(shù)據(jù)流中的數(shù)據(jù)包如何轉(zhuǎn)發(fā)的規(guī)則。這些規(guī)則可以配置與數(shù)據(jù)包頭特定域相匹配的（例如MAC地址、IP地址等），并在匹配的數(shù)據(jù)包上執(zhí)行特定行為（例如轉(zhuǎn)發(fā)、重寫、丟棄等）。規(guī)則也可設(shè)置超時屬性，路由器在一段固定時間間隔后（硬超時）或一段指定的非活動時間間隔后（軟超時）刪除規(guī)則。當數(shù)據(jù)流中的包頭無法匹配相應(yīng)規(guī)則，這個數(shù)據(jù)包頭信息就會發(fā)給通配規(guī)則控制模塊，有它來計算合適的路由方式。此外，路由器為匹配規(guī)則的數(shù)據(jù)包字節(jié)數(shù)設(shè)置計數(shù)器，程序根據(jù)計數(shù)值進行投票。

本文提出的負載均衡解決方案中，首先通用規(guī)則生成模塊收集所有服務(wù)器的CPU負載情況，并更新通配規(guī)則。此規(guī)則由控制模塊加載，路由器重寫服務(wù)器的IP地址，將數(shù)據(jù)請求按端口轉(zhuǎn)發(fā)至目標服務(wù)器上。依靠microflow規(guī)則，通配規(guī)則根據(jù)客戶端IP地址，將請求進行轉(zhuǎn)發(fā)；超時參數(shù)允許microflow規(guī)則在一個客戶請求連接結(jié)束后進行自我式消除。針對每一個通配規(guī)則，該方案使用計數(shù)器以識別網(wǎng)絡(luò)負載情況，根據(jù)實時負載動態(tài)調(diào)整規(guī)則以重新分配負載。

OpenFlow存在一些不足之處，它當前不支持多條路徑下擴展負載的哈希式路由，OpenFlow只支持排序無關(guān)的情況，而本次提出的算法根據(jù)通配規(guī)則匹配客戶端IP地址，由于IP地址的低階排序bit較高階排序big有更高的熵值，本算法基于客戶端IP地址的低階排序bit位實現(xiàn)負載分流。OpenFlow的另一個限制是它不支持TCP標簽，后者有助于區(qū)分新到來的網(wǎng)絡(luò)連接和已持續(xù)連上的網(wǎng)絡(luò)連接，這種算法就可以應(yīng)對Open-Flow這一點的不足。

為支持來自同一個TCP連接的數(shù)據(jù)包被轉(zhuǎn)發(fā)至同一個服務(wù)器上進行處理，本算法設(shè)置的規(guī)則根據(jù)客戶端的IP地址進行配置。不同的IP請求量可能不同，因此主要目標是為整個客戶端IP地址空間集生成一個較小的通配規(guī)則結(jié)果集，同時使得所有服務(wù)器副本的CPU負載較均衡。負載分配的重新調(diào)整需要新的通配規(guī)則，并要求變化最小化。

如圖2所示，二叉樹可較直觀地展現(xiàn)IP地址的前綴，樹上每一個節(jié)點對應(yīng)一個IP前綴，距葉子節(jié)點越近，對應(yīng)表明IP前綴長度越長。葉子節(jié)點的個數(shù)等于冪次方（例如，如圖2所示，3個前綴情況下的二叉樹擁有8個葉子節(jié)點）。每一個服務(wù)器副本與多個葉子節(jié)點相關(guān)聯(lián)（例如，在初始狀態(tài)，S1和S2服務(wù)器各對應(yīng)2個葉子節(jié)點，其他服務(wù)器各對應(yīng)一個流量節(jié)點）。但在實際情況中，aj的值不一定等于冪次方值，同時每個節(jié)點對應(yīng)的流量和請求計算量也未必平均。本文提出的方案設(shè)定的值約等于冪次方并相應(yīng)地設(shè)置權(quán)重正態(tài)化。權(quán)重值與實際分布十分接近，可簡易有效地分配IP地址空間。

1.1 通配規(guī)則合并節(jié)點

為每一個葉子節(jié)點創(chuàng)建通配規(guī)則的策略生成的規(guī)則數(shù)量十分巨大。本算法通過聚合關(guān)聯(lián)至同一服務(wù)器的兄弟節(jié)點以降低規(guī)則的數(shù)量，如圖2所示，單一的通配規(guī)則00＊可以同時代表關(guān)聯(lián)服務(wù)器S1的葉子節(jié)點000＊和001＊。類似地，01＊可以同時代表關(guān)聯(lián)服務(wù)器R2的葉子節(jié)點010＊和011＊，通配規(guī)則的數(shù)量從8減少至5。

1.2 通配規(guī)則動態(tài)調(diào)整

二叉圖中每一條邊的權(quán)重值說明了如何最好地將葉子節(jié)點分配給服務(wù)器，如圖2所示，S3對應(yīng)權(quán)重a3=3，生成一個帶兩個葉子節(jié)點的規(guī)則和另一個帶一個葉子節(jié)點的規(guī)則，但是由于服務(wù)器群中的部分服務(wù)器需要不定期進行維護，并且各個客戶端IP的請求并不均勻，且所需要消耗的服務(wù)器計算量也不盡相同。因此隨著時間變化，服務(wù)器的CPU消耗會出現(xiàn)不平衡的狀態(tài)，在圖2中S2和S3的CPU負載就偏大，而S1和S4的計算量偏小。

針對這種情況，通配規(guī)則生成模塊會定時從服務(wù)器集群獲取CPU負載數(shù)據(jù)。并按照二叉樹向上檢索是否有葉子節(jié)點所處服務(wù)器的CPU較低，處于非均衡狀態(tài)。這里采用服務(wù)器CPU負載的信息熵作為判斷均衡的標準：

其中p1，p2分別代表此節(jié)點左右兩邊所有服務(wù)器的平均CPU負載，CPU負載越加不均衡的二叉樹子節(jié)點，其熵值越小，如圖2各節(jié)點中所示。對于低于一定閾值的節(jié)點，可以調(diào)整｛aj｝的權(quán)重，將負載較高的服務(wù)器部分流量分給負載較低的服務(wù)器，并重新生成通配規(guī)則。生成規(guī)則集的算法應(yīng)該能夠最小化根據(jù)IP地址空間碎片以適應(yīng)服務(wù)器的變化調(diào)整，如果服務(wù)器關(guān)聯(lián)的葉子節(jié)點沒有發(fā)生變化，對應(yīng)的規(guī)則集也就無需調(diào)整

（見圖3）。

圖3 流量負載發(fā)生變化后的二叉樹模型

在圖3中，由于11＊，0＊兩個節(jié)點熵值過小，將其下S3的部分流量重新分到S4，S1下部分流量分給S2，而原本00＊和10＊兩個規(guī)則集不需改變，而通配置規(guī)則010＊需要轉(zhuǎn)變至新的服務(wù)器上，重新分配后由于負載有所均衡，所有各節(jié)點的熵值均上升到閾值以上。

由于S4的兩個規(guī)則集可以合并，而S1需要生成一個新的規(guī)則集，所以整體規(guī)則集數(shù)量依然為5。

1.3 通配規(guī)則切換

表1為數(shù)據(jù)包包頭各域值。

表1 數(shù)據(jù)包包頭各域值

控制器不能因更改路由器配置而破壞已有的TCP連接，后者至少需要向客戶端請求返回應(yīng)答后再斷開。新的請求連接將TCP同步標簽設(shè)置在第一個數(shù)據(jù)包中，所以本文設(shè)計的算法利用TCP同步標記來區(qū)分新的請求連接和已有的請求連接。OpenFlow路由器無法匹配TCP標記，控制器可以檢查數(shù)據(jù)包的同步位并相應(yīng)配置規(guī)則。識別一個連接的結(jié)束符更加復雜，因為FIN或RST標簽無法清晰標識網(wǎng)絡(luò)連接的結(jié)束符；異常中斷連接的客戶端并不并發(fā)送FIN或RST標簽。基于以上因素，通過客戶端在一段指定的時間（比如60s）內(nèi)無活動來推斷連接斷開。

本文采用兩套算法來遷移流量到新的服務(wù)器：第一套算法將數(shù)據(jù)包轉(zhuǎn)發(fā)至控制器以交換更快的數(shù)據(jù)包傳遞；第二套算法允許路由器處理所有的數(shù)據(jù)包，但轉(zhuǎn)換速率比第一種算法低。為了減少路由器中額外規(guī)則集的數(shù)量，可以同時限制IP地址空間的傳遞碎片率。例如，可以分階段地將規(guī)則111＊從服務(wù)器R3轉(zhuǎn)移至R1，首先傳遞規(guī)則1110＊，再傳遞規(guī)則1111＊。

2 原型實現(xiàn)和評估

利用OpenVswitc和OSE（OpenFlow控制器平臺）實現(xiàn)本文解決方案的原型并運行在MNet執(zhí)行測試，使用MNet構(gòu)建圖1中的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，包含3個服務(wù)器、2個路由器以及一系列客戶端。服務(wù)器運行在 Mongoose［8］的web服務(wù)器上。原型中的OSE應(yīng)用程序在兩個路由器中配置規(guī)則，其中一個路由器充當網(wǎng)關(guān)的角色，負責分發(fā)客戶端請求負載的轉(zhuǎn)發(fā)工作，另一個路由器承擔將請求轉(zhuǎn)發(fā)至目標的服務(wù)器上的角色。本文的性能評估展現(xiàn)了該原型系統(tǒng)滿足了負載均衡的自適應(yīng)變化原則。

適應(yīng)新的負載均衡權(quán)重值：原型使用的4個服務(wù)器主機硬盤均擁有16MB大小的文件空間，36個客戶端在有效的單一地址突然間內(nèi)被隨機分配IP地址。每一個客戶端發(fā)出wget命令請求以從服務(wù)器下載文件；在下載文件完成后，客戶端在發(fā)送新請求之前需要隨機地等待0至10秒。參照圖2，原型假定a1=2，a2=2，a3=3，a4=1。75秒過去后，系統(tǒng)將a3從3更改成0，以模仿服務(wù)器S3從服務(wù)器群中拆除。當客戶端開始發(fā)送請求，網(wǎng)絡(luò)吞吐量上升，服務(wù)器S3處理了大多數(shù)的請求。負載的分發(fā)十分接近于2∶2∶3∶1，小部分客戶端請求會產(chǎn)生可分析的偏差，網(wǎng)絡(luò)負載的波動也隨著時間而變化。75s后，S3上的流量開始下降，所以的請求被轉(zhuǎn)發(fā)至S1，S2和S4上。60秒后，控制器配置新的通配規(guī)則。S3上的負載最終隨著少量的已有連接中斷后而下降至0。S3未被拆除前，系統(tǒng)配置了5個通配規(guī)則；S3拆除后，系統(tǒng)重新調(diào)整生成3個通配規(guī)則，其中4個聚合至一個單獨的通配規(guī)則，原來為S2設(shè)置的規(guī)則同時被消除。

3 結(jié)語

目前實現(xiàn)的原型中，假定網(wǎng)絡(luò)中只有兩個路由器和均勻分布的客戶端IP地址空間。在后續(xù)的研究工作中，還可以將算法進行延展，以解決非均勻的網(wǎng)絡(luò)負載以及任意的網(wǎng)絡(luò)拓撲結(jié)構(gòu)，已有的分割和轉(zhuǎn)換算法是開展后續(xù)研究工作的基石。

網(wǎng)絡(luò)中的在線有服務(wù)依賴于負載均衡以有效利用所有主機服務(wù)器，本文設(shè)計的負載均衡架構(gòu)將源IP地址映射至服務(wù)器上，客戶端的請求可以通過負載均衡器以最小成本被轉(zhuǎn)發(fā)。本文提出的分割算法可以動態(tài)調(diào)整流量負載，并生成一套最小通配規(guī)則集，傳遞算法負責調(diào)整規(guī)則以適應(yīng)服務(wù)器群的變化。本文實現(xiàn)的原型系統(tǒng)展現(xiàn)了算法可以最低吞吐量的影響變化而自適應(yīng)網(wǎng)絡(luò)拓撲結(jié)構(gòu)和流量負載的調(diào)整變化。

［1］ Foundry ServerIron load balancer.http：／／www.foundrynet.com／products／webswitches／serveriron／.

［2］ Microsoft network load balancing.http：／／technet／microsoft.com／en-us／library／bb742455.aspx.

［3］ The OpenFlow Switch Consortium.http：／／www.openflowswitch.org.

［4］ MCKEOWN N，ANDERSON T，BALAKRISHNAN H，et al.Openflow：Enabling innovation in campus networks.ACM SIGCOMM Computer Communications Review，38（2）：69-74，2008.

［5］ HANDIGOL N，SEETHARAMAN S，F(xiàn)LAJSLIK M，et al.Plug-n-Serve：Load-balancing web traffic using Open-Flow，Aug.2009.Demo at ACM SIGCOMM.

［6］ MOGUL J C，TOURRILHES J，YALAGANDULA P，et al.Devoflow：Cost-effective flow management for high performance enterprise networks.In ACM SIGCOMM Hot-Nets Workshop，Monterey，CA.

［7］ LANTZ B，HELLER B，MCKEOWN N.A network in a laptop：Rapid prototyping for software-defined networks.In ACM SIGCOMM HotNets Workshop，2010.

［8］ SCHLANSKER M，TURNER Y，TOURRILHES J，et al.Ensemble routing for datacenter networks.In ACM ANCS，La Jolla，CA，2010.

［9］ Mongoose-easy to use web server.http：／／code.google.com／p／mongoose／.