摘 要：隨著Internet的飛速發(fā)展和其對(duì)人們生活的深入影響，越來(lái)越多的個(gè)人在互聯(lián)網(wǎng)上購(gòu)物、娛樂(lè)、休閑、與人溝通、獲取信息；越來(lái)越多的企業(yè)把他們與顧客和業(yè)務(wù)伙伴之間的聯(lián)絡(luò)搬到互聯(lián)網(wǎng)上，通過(guò)網(wǎng)絡(luò)來(lái)完成交易，建立與客戶之間的聯(lián)系?；ヂ?lián)網(wǎng)的用戶數(shù)和網(wǎng)絡(luò)流量正以幾何級(jí)數(shù)增長(zhǎng)，特別是文本、圖像、音樂(lè)、廣告、流媒體、動(dòng)畫等大量涌現(xiàn)，這對(duì)網(wǎng)絡(luò)服務(wù)的可伸縮性提出很高的要求。 另外，隨著電子商務(wù)等關(guān)鍵性應(yīng)用在網(wǎng)上運(yùn)行，任何例外的服務(wù)中斷都將造成不可估量的損失，服務(wù)的高可用性也越來(lái)越重要。研究如何緩解網(wǎng)絡(luò)擁塞，提高用戶獲取信息的速度，并設(shè)計(jì)合理的框架，建立高性能、高可伸縮、高可用的網(wǎng)絡(luò)服務(wù)。

關(guān)鍵詞：LVS集群技術(shù)；加權(quán)輪叫調(diào)度算法；CDN網(wǎng)絡(luò)技術(shù)

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-373X(2008)08-141-03

LVS Clustering and Dynamic Feedback Grouping Weighted RoundRobin

Scheduling Algorithmbased SAMCCDN Network System

HUANG Jianshe

(Zhejiang Business Technology Institute，Ningbo，315012，China)

Abstract：With the rapid development of Internet and their deep influence on our life，more and more activities are carried out on the Internet，such as shopping，entertaining，communicating，searching for information，and so on.More and more firms and companies complete their business on the Internet，like setting up business relationship with customers，contacting and transacting.The users′ number and network traffic are increasing in geometric series on the Internet.The emergence of great lot of applications especially on text，image，advertisement，streaming media and flash require higher flexibility on the network system services.In addition，with some key application like Ebusiness running over network，any unexpected interruption on the network service will bring immensurable loss due to some vital issues done on the internet.Therefore the reliability of network service become more and more important.In this paper，how to reduce the network congestion to improve the uses′ acquiring information speed，and how to design the reasonable framework to build network service with high performance，high flexibility and high reliability are discussed.

Keywords：LVS clustering technology;grouping weighted RoundRobin scheduling algorithm;CDN network technology

人類社會(huì)正在進(jìn)入以網(wǎng)絡(luò)為中心的信息時(shí)代，隨著Internet的飛速發(fā)展和對(duì)人們生活的深入影響，越來(lái)越多的個(gè)人在互聯(lián)網(wǎng)上購(gòu)物、娛樂(lè)、休閑、與人溝通、獲取信息；越來(lái)越多的企業(yè)把他們與顧客和業(yè)務(wù)伙伴之間的聯(lián)絡(luò)搬到互聯(lián)網(wǎng)上，通過(guò)網(wǎng)絡(luò)來(lái)完成交易，建立與客戶之間的聯(lián)系?；ヂ?lián)網(wǎng)的用戶數(shù)和網(wǎng)絡(luò)流量正以幾何級(jí)數(shù)增長(zhǎng)，特別是文本、圖像、音樂(lè)、廣告、流媒體、動(dòng)畫等大量涌現(xiàn)，這對(duì)網(wǎng)絡(luò)服務(wù)的可伸縮性提出很高的要求。 另外，隨著電子商務(wù)等關(guān)鍵性應(yīng)用在網(wǎng)上運(yùn)行，任何例外的服務(wù)中斷都將造成不可估量的損失，服務(wù)的高可用性也越來(lái)越重要。如何緩解網(wǎng)絡(luò)擁塞，提高用戶獲取信息的速度，成為困擾眾多企業(yè)和服務(wù)商的一大難題 ，因此CDN ^[1](Content Delivery Network)技術(shù)應(yīng)運(yùn)而生。如何給出合理的框架和有效的設(shè)計(jì)方法，建立高性能、高可伸縮、高可用的網(wǎng)絡(luò)服務(wù)，這是擺在系統(tǒng)設(shè)計(jì)者面前極富挑戰(zhàn)性的任務(wù)。本文研究和設(shè)計(jì)便是圍繞這一任務(wù)展開。

1 SAMCCND網(wǎng)絡(luò)技術(shù)簡(jiǎn)介

用硬件和軟件方法實(shí)現(xiàn)高可伸縮、高可用網(wǎng)絡(luò)服務(wù)的需求不斷增長(zhǎng)，這種需求可以歸結(jié)以下幾點(diǎn)：

(1) 可伸縮性（Scalability），當(dāng)服務(wù)的負(fù)載增長(zhǎng)時(shí)，系統(tǒng)能被擴(kuò)展來(lái)滿足需求，且不降低服務(wù)質(zhì)量；

(2) 高可用性（Availability），盡管部分硬件和軟件會(huì)發(fā)生故障，整個(gè)系統(tǒng)的服務(wù)必須是每天24小時(shí)每星期7天可用； 

(3) 可管理性（Manageability），整個(gè)系統(tǒng)可能在物理上很大，但應(yīng)該容易管理；

(4) 價(jià)格有效性（Costeffectiveness），整個(gè)系統(tǒng)實(shí)現(xiàn)是經(jīng)濟(jì)的、易支付的。 

可伸縮網(wǎng)絡(luò)服務(wù)是指網(wǎng)絡(luò)服務(wù)能隨著用戶數(shù)目的增長(zhǎng)而擴(kuò)展其性能，如在系統(tǒng)中增加服務(wù)器、內(nèi)存或硬盤等；整個(gè)系統(tǒng)很容易被擴(kuò)展，無(wú)需重新設(shè)置整個(gè)系統(tǒng)，無(wú)需中斷服務(wù)。換句話說(shuō)，系統(tǒng)管理員擴(kuò)展系統(tǒng)的操作對(duì)最終用戶是透明的，他們不會(huì)知道系統(tǒng)的改變。

可伸縮系統(tǒng)通常是高可用的系統(tǒng)。在部分硬件（如硬盤、服務(wù)器、子網(wǎng)絡(luò)）和部分軟件（如操作系統(tǒng)、服務(wù)進(jìn)程）的失效情況下，系統(tǒng)可以繼續(xù)提供服務(wù)，最終用戶不會(huì)感知到整個(gè)服務(wù)的中斷，除了正在失效點(diǎn)上處理請(qǐng)求的部分用戶可能會(huì)收到服務(wù)處理失敗，需要重新提交請(qǐng)求。Caching和復(fù)制是建立高可用系統(tǒng)的常用技術(shù)，建立多個(gè)副本會(huì)導(dǎo)致如何將原件的修改傳播到多個(gè)副本上的問(wèn)題。

實(shí)現(xiàn)可伸縮網(wǎng)絡(luò)服務(wù)的方法一般是通過(guò)一對(duì)多的映射機(jī)制，將服務(wù)請(qǐng)求流分而治之（Divide and Conquer）到多個(gè)結(jié)點(diǎn)上處理。一對(duì)多的映射可以在很多層次上存在，如主機(jī)名上的DNS系統(tǒng)、網(wǎng)絡(luò)層的TCP/IP、文件系統(tǒng)等。虛擬（virtual）是描述一對(duì)多映射機(jī)制的詞匯，將多個(gè)實(shí)體組成一個(gè)邏輯上的、虛擬的整體。例如，虛存（virtual memory）是現(xiàn)代操作系統(tǒng)中最典型的一對(duì)多映射機(jī)制，虛存建立一個(gè)虛擬內(nèi)存空間，將他映射到多個(gè)物理內(nèi)存上。

CDN的英文全稱是Content Delievery Network，即內(nèi)容分發(fā)傳送網(wǎng)絡(luò)。是建立在現(xiàn)有IP網(wǎng)絡(luò)基礎(chǔ)結(jié)構(gòu)之上的一種增值網(wǎng)絡(luò)。在傳統(tǒng)的IP網(wǎng)絡(luò)中，用戶請(qǐng)求直接指向基于網(wǎng)絡(luò)地址的原始服務(wù)器，而CDN業(yè)務(wù)供了一個(gè)服務(wù)層，補(bǔ)充和延伸了Internet網(wǎng)絡(luò)，把頻繁訪問(wèn)的內(nèi)容盡可能向用戶推進(jìn)，提供了處理基于內(nèi)容進(jìn)行流量轉(zhuǎn)發(fā)的新能力，把路由導(dǎo)引到最佳服務(wù)器上。他改變了分布到使用者信息的方式，從被動(dòng)的內(nèi)容恢復(fù)轉(zhuǎn)為主動(dòng)的內(nèi)容轉(zhuǎn)發(fā)。CDN技術(shù)是將多點(diǎn)負(fù)載均衡，路由或緩存技術(shù)等結(jié)合起來(lái)，利用智能分配策略，將內(nèi)容根據(jù)來(lái)訪用戶的地點(diǎn)，按照就近訪問(wèn)的原則分配到多個(gè)節(jié)點(diǎn)。

2 LVS^[2]集群的通用結(jié)構(gòu)

LVS（Linux Virtual Servers）即Linux虛擬服務(wù)器。LVS集群采用IP負(fù)載均衡技術(shù)和基于內(nèi)容請(qǐng)求分發(fā)技術(shù)。調(diào)度器具有很好的吞吐率，將請(qǐng)求均衡地轉(zhuǎn)移到不同的服務(wù)器上執(zhí)行，且調(diào)度器自動(dòng)屏蔽掉服務(wù)器的故障，從而將一組服務(wù)器構(gòu)成一個(gè)高性能的、高可用的虛擬服務(wù)器。

為此，在設(shè)計(jì)時(shí)需要考慮系統(tǒng)的透明性、可伸縮性、高可用性和易管理性。LVS集群的體系結(jié)構(gòu)如圖1所示，他有3個(gè)主要組成部分：

負(fù)載調(diào)度器（load balancer），他是整個(gè)集群對(duì)外面的前端機(jī)，負(fù)責(zé)將客戶的請(qǐng)求發(fā)送到一組服務(wù)器上執(zhí)行，而客戶認(rèn)為服務(wù)是來(lái)自一個(gè)IP地址上。他可以是用IP負(fù)載均衡技術(shù)的負(fù)載調(diào)度器，也可以是基于內(nèi)容請(qǐng)求分發(fā)的負(fù)載調(diào)度器，還可以是兩者的結(jié)合。

服務(wù)器池（server pool），是一組真正執(zhí)行客戶請(qǐng)求的服務(wù)器，執(zhí)行的服務(wù)有Web，MAIL，F(xiàn)TP和DNS等。 

后端存儲(chǔ)（backend storage），他為服務(wù)器池提供一個(gè)共享的存儲(chǔ)區(qū)，這樣很容易使得服務(wù)器池?fù)碛邢嗤膬?nèi)容，提供相同的服務(wù)。

調(diào)度器采用IP負(fù)載均衡技術(shù)、基于內(nèi)容請(qǐng)求分發(fā)技術(shù)或者兩者相結(jié)合。在IP負(fù)載均衡技術(shù)中，需要服務(wù)器池?fù)碛邢嗤膬?nèi)容提供相同的服務(wù)。當(dāng)客戶請(qǐng)求到達(dá)時(shí)，調(diào)度器只根據(jù)負(fù)載情況從服務(wù)器池中選出一個(gè)服務(wù)器，將該請(qǐng)求轉(zhuǎn)發(fā)到選出的服務(wù)器，并記錄這個(gè)調(diào)度；當(dāng)這個(gè)請(qǐng)求的其他報(bào)文到達(dá)，也會(huì)被轉(zhuǎn)發(fā)到前面選出的服務(wù)器。在基于內(nèi)容請(qǐng)求分發(fā)技術(shù)中，服務(wù)器可以提供不同的服務(wù)，當(dāng)客戶請(qǐng)求到達(dá)時(shí)，調(diào)度器可根據(jù)請(qǐng)求的內(nèi)容和服務(wù)器的情況選擇服務(wù)器執(zhí)行請(qǐng)求。因?yàn)樗械牟僮鞫际窃诓僮飨到y(tǒng)核心空間中將完成的，他的調(diào)度開銷很小，所以他具有很高的吞吐率。

服務(wù)器池的結(jié)點(diǎn)數(shù)目是可變的。當(dāng)整個(gè)系統(tǒng)收到的負(fù)載超過(guò)目前所有結(jié)點(diǎn)的處理能力時(shí)，可以在服務(wù)器池中增加服務(wù)器來(lái)滿足不斷增長(zhǎng)的請(qǐng)求負(fù)載。對(duì)大多數(shù)網(wǎng)絡(luò)服務(wù)，結(jié)點(diǎn)與結(jié)點(diǎn)間不存在很強(qiáng)的相關(guān)性，所以整個(gè)系統(tǒng)的性能可以隨著服務(wù)器池的結(jié)點(diǎn)數(shù)目增加而線性增長(zhǎng)。

后端存儲(chǔ)通常用容錯(cuò)的分布式文件系統(tǒng)，如NFS，AFS，GFS，Coda和Intermezzo等。分布式文件系統(tǒng)為各服務(wù)器提供共享的存儲(chǔ)區(qū)，他們?cè)L問(wèn)分布式文件系統(tǒng)就像訪問(wèn)本地文件系統(tǒng)一樣。同時(shí)，分布式文件系統(tǒng)提供良好的伸縮性和可用性。然而，當(dāng)不同服務(wù)器上的應(yīng)用程序同時(shí)訪問(wèn)分布式文件系統(tǒng)上同一資源時(shí)，應(yīng)用程序的訪問(wèn)沖突需要消解才能使得資源處于一致狀態(tài)。這需要一個(gè)分布式鎖管理器（Distributed Lock Manager），他可能是分布式文件系統(tǒng)內(nèi)部提供的，也可能是外部的。開發(fā)者在寫應(yīng)用程序時(shí)，可以使用分布式鎖管理器保證應(yīng)用程序在不同結(jié)點(diǎn)上并發(fā)訪問(wèn)的一致性。

負(fù)載調(diào)度器、服務(wù)器池和分布式文件系統(tǒng)通過(guò)高速網(wǎng)絡(luò)相連，如100 Mb/s交換機(jī)、1 000 Mb/s 等高速的網(wǎng)絡(luò)，主要為了避免當(dāng)系統(tǒng)規(guī)模擴(kuò)大時(shí)互聯(lián)網(wǎng)絡(luò)成為瓶頸。

3 動(dòng)態(tài)反饋分組加權(quán)輪叫調(diào)度算法^[3]概述

動(dòng)態(tài)反饋負(fù)載均衡算法考慮服務(wù)器的實(shí)時(shí)負(fù)載和響應(yīng)情況，不斷調(diào)整服務(wù)器間處理請(qǐng)求的比例，避免有些服務(wù)器超載時(shí)依然收到大量請(qǐng)求，從而提高整個(gè)系統(tǒng)的吞吐率。

加權(quán)輪叫調(diào)度算法（Weighted Round Robin Scheduling）就是以輪叫的方式同時(shí)考慮其目標(biāo)服務(wù)器的綜合負(fù)載權(quán)值等依次將請(qǐng)求調(diào)度不同[GK！9]的服務(wù)器，即每次調(diào)度執(zhí)行i = (i + 1) mod n，并選出第i臺(tái)服務(wù)器，再權(quán)衡該服務(wù)器的權(quán)值決定是否繼續(xù)輪叫下一臺(tái)服務(wù)器。 

在系統(tǒng)實(shí)現(xiàn)時(shí)，可以引入一個(gè)額外條件，當(dāng)服務(wù)器的權(quán)值為零時(shí)，表示該服務(wù)器不可用而不被調(diào)度。這樣做的目的是將服務(wù)器切出服務(wù)（如屏蔽服務(wù)器故障和系統(tǒng)維護(hù)）。 如果所有的服務(wù)器都是不是負(fù)責(zé)相同的功能，或者服務(wù)器都在同一個(gè)局域網(wǎng)內(nèi)，性能差別比較大時(shí)，就需要采用分組加權(quán)輪叫調(diào)度算法（Group Weighted RoundRobin Scheduling），既實(shí)現(xiàn)全局的服務(wù)器均衡，又可保持各組服務(wù)器的性能基本均衡。[HK]

4 動(dòng)態(tài)反饋分組加權(quán)輪叫調(diào)度算法流程

假設(shè)有一組服務(wù)器S = {S0，S1，…，Sn-1}，W(Si)表示服務(wù)器Si的權(quán)值，一個(gè)指示變量i表示上一次選擇的服務(wù)器；指示變量cw表示當(dāng)前調(diào)度的權(quán)值；max(S) 表示集合S中所有服務(wù)器的最大權(quán)值，gcd(S)表示集合S中所有服務(wù)器權(quán)值的最大公約數(shù)。變量i初始化為-1，cw初始化為零。



while (true) { 

i = (i + 1) mod n;

if (i == 0) { 

cw = cw -gcd(S); 

if (cw <= 0) { 

cw = max(S);

if (cw == 0) 

return NULL;

} }

if (W(Si) >= cw)

return Si;}

5 SAMCCDN網(wǎng)絡(luò)服務(wù)系統(tǒng)總體設(shè)計(jì)

內(nèi)容分發(fā)網(wǎng)絡(luò)^[4]（Content Distribution Network，CDN），有時(shí)也可以稱作內(nèi)容傳遞網(wǎng)絡(luò)（Content Delivery Network）。CDN的核心思想是將內(nèi)容從中心推到邊緣靠近用戶的地方，這樣，不但有效地提高了用戶訪問(wèn)內(nèi)容的服務(wù)質(zhì)量，而且還能減輕中心設(shè)備和骨干網(wǎng)絡(luò)的壓力。通過(guò)CDN，可以將內(nèi)容服務(wù)從原來(lái)的單一中心服務(wù)結(jié)構(gòu)變?yōu)榉植际椒?wù)結(jié)構(gòu)，提高用戶訪問(wèn)網(wǎng)站的響應(yīng)速度。因而，CDN可以提高網(wǎng)絡(luò)中信息流動(dòng)的效率，從技術(shù)上全面解決由于網(wǎng)絡(luò)帶寬小、用戶訪問(wèn)量大、網(wǎng)點(diǎn)分布不均等問(wèn)題，提高用戶訪問(wèn)的響應(yīng)速度。

總體上，CDN通常由3個(gè)部分構(gòu)成：內(nèi)容管理平臺(tái)、內(nèi)容路由系統(tǒng)、Cache節(jié)點(diǎn)網(wǎng)絡(luò)。如圖2所示是SAMCCDN網(wǎng)絡(luò)系統(tǒng)的總體組成示意圖。其中，內(nèi)容管理平臺(tái)主要負(fù)責(zé)整個(gè)CDN系統(tǒng)的管理，特別是內(nèi)容管理，如內(nèi)容的注入和發(fā)布、內(nèi)容的分發(fā)、內(nèi)容的審核、內(nèi)容的服務(wù)等。內(nèi)容路由系統(tǒng)負(fù)責(zé)將用戶的請(qǐng)求調(diào)度到適當(dāng)?shù)脑O(shè)備上，內(nèi)容路由通常通過(guò)負(fù)載均衡系統(tǒng)實(shí)現(xiàn)。Cache節(jié)點(diǎn)網(wǎng)絡(luò)是CDN的業(yè)務(wù)提供點(diǎn)，是面向最終用戶的內(nèi)容提供設(shè)備。 

6 結(jié) 語(yǔ) 

從整個(gè)互聯(lián)網(wǎng)寬帶應(yīng)用的角度看， CDN只是其中支撐業(yè)務(wù)和應(yīng)用的技術(shù)環(huán)節(jié)，需要包括內(nèi)容等在內(nèi)的整個(gè)價(jià)值鏈條各相關(guān)環(huán)節(jié)的協(xié)調(diào)發(fā)展，才能真正帶動(dòng)CDN技術(shù)的健康發(fā)展。

參 考 文 獻(xiàn)

［1］LinuxAid.CDN內(nèi)容分發(fā)網(wǎng)絡(luò)技術(shù)［EB/OL］.http://tech.ccidnet.com/article/c737a42014p1.html，200341.

［2］姚耀文，茹建斌，繆炯燁.基于Linux的服務(wù)器群集方案\\[J\\].計(jì)算機(jī)工程，2001，27(4):139141.

［3］Yong M T，Ayani R.Comparison of Load Balancing Strategies on Clusterbased Web Servers ［J］.Simulation，2001，7 7(56):185 195.

［4］張?jiān)骑w，陳常嘉.CDN:推進(jìn)網(wǎng)絡(luò)內(nèi)容傳送體系變革［N］.人民郵電報(bào)，20031231.

作者簡(jiǎn)介 黃建設(shè) 女，1968年出生，湖北人，教師，雙師型。主要研究方向?yàn)榫W(wǎng)絡(luò)、數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘。