LVS集群調(diào)度算法的實現(xiàn)分析

王雪蓮，曹青媚

1.內(nèi)蒙古師范大學(xué)公共管理學(xué)院，內(nèi)蒙古 呼和浩特 010022

2.內(nèi)蒙古農(nóng)業(yè)大學(xué)職業(yè)技術(shù)學(xué)院，內(nèi)蒙古 呼和浩特 010022

0 引言

網(wǎng)絡(luò)的快速發(fā)展和網(wǎng)絡(luò)用戶的日益增加，致使服務(wù)器面臨著巨大的挑戰(zhàn)。單臺服務(wù)器即使有再好的性能也很難滿足當(dāng)前日益增加的客戶并發(fā)訪問的需求。而集群的出現(xiàn)緩解了這一問題，它不再是單一的服務(wù)器，而由多個服務(wù)器共同分擔(dān)多個客戶的請求。集群系統(tǒng)具有可伸縮性、高性價比、高可用性的特點，因此得到了廣泛的應(yīng)用[1]。而負載均衡是集群性能提高的關(guān)鍵因素之一，具有較高的研究價值和應(yīng)用前景。

1 LVS集群體系結(jié)構(gòu)及軟件層次結(jié)構(gòu)

LVS（Linux Virtual Server）全稱虛擬服務(wù)器，LVS集群由國防科技大學(xué)章文嵩博士研發(fā)的，主要解決的是集群的負載均衡。

1.1 體系結(jié)構(gòu)

LVS集群體系結(jié)構(gòu)一般采用三層結(jié)構(gòu)，由前端調(diào)度器層、中間服務(wù)器集群層和后端存儲系統(tǒng)層組成[2]。調(diào)度器是整個集群的前端機，是集群的唯一入口。當(dāng)有客戶請求時，首先要經(jīng)過調(diào)度器，它根據(jù)調(diào)度算法負責(zé)將客戶請求分配到服務(wù)器集群中的某一臺?？蛻舾杏X好像服務(wù)是來自一個集群IP地址，即所謂的虛擬IP，集群內(nèi)部對客戶是透明的。該集群中某一臺服務(wù)器執(zhí)行完請求后將數(shù)據(jù)返回給客戶。多臺服務(wù)器結(jié)構(gòu)緩減了集群的負載，體現(xiàn)了集群的可伸縮性。后端存儲系統(tǒng)為服務(wù)器集群提供相同的服務(wù)，使得服務(wù)器集群有相同的內(nèi)容。

1.2 軟件層次結(jié)構(gòu)

圖1是調(diào)度器上的內(nèi)部軟件層次結(jié)構(gòu)，在應(yīng)用層裝有一個ipvsadm管理軟件，該軟件由管理員進行設(shè)置，以達到對LVS集群的管理。對該軟件管理員可以設(shè)置LVS的工作模式、在內(nèi)核虛擬服務(wù)器表中增加或減少服務(wù)器IP地址、增加或刪除虛擬服務(wù)，可以設(shè)置服務(wù)器的固定權(quán)值，配置要選擇的調(diào)度算法，然后將管理員設(shè)置的信息傳到內(nèi)核層。ipvsadm管理軟件主要通過ipvsadm.c文件經(jīng)過編譯后生成可執(zhí)行文件。該文件通過getopt_long（）函數(shù)，獲取管理員從終端輸入的命令，并對輸入的命令進行解析，根據(jù)不同情況，將輸入的值賦給一個變量，通過變量將輸入命令傳到內(nèi)核，如果不設(shè)置權(quán)值，默認(rèn)的權(quán)值是1。

圖1 軟件層次結(jié)構(gòu)

在調(diào)度器的Linux內(nèi)核層有IPVS調(diào)度模塊，本文選取ipvs-1.0.9作為內(nèi)核調(diào)度補丁軟件[3]，調(diào)度模塊中有十種調(diào)度算法，分別是輪轉(zhuǎn)法（RR）、加權(quán)輪轉(zhuǎn)（WRR）、最小連接（LC）、加權(quán)最小連接（WLC）、基于局部性的最少鏈接調(diào)度（LBLC）、帶復(fù)制的基于局部性最少鏈接調(diào)度（LBCR），最短預(yù)期延時調(diào)度（SED）、源地址散列調(diào)度（SH），目標(biāo)地址散列調(diào)度（DH）、不排隊調(diào)度（NQ）。在ipvs-1.0.9中十種調(diào)度算法分別存在于十個.c文件中。這些調(diào)度算法都是以連接為粒度的。

2 內(nèi)核調(diào)度算法的實現(xiàn)

在調(diào)度模塊中每一種調(diào)度算法都存儲在一個結(jié)構(gòu)體類型相應(yīng)的變量中，10種調(diào)度算法有10個調(diào)度變量。本文介紹常用的4種調(diào)度算法:輪轉(zhuǎn)法（RR）、加權(quán)輪轉(zhuǎn)（WRR）、最小連接（LC）、加權(quán)最小連接（WLC）[4]。

輪轉(zhuǎn)法、加權(quán)輪轉(zhuǎn)、最小連接、加權(quán)最小連接調(diào)度算法開始以動態(tài)模塊加載到內(nèi)核，四個模塊分別是ip_vs_rr_init， ip_vs_wrr_init，ip_vs_lc_init，ip_vs_wlc_init，它們通過register_ip_vs_scheduler函數(shù)分別注冊到相應(yīng)調(diào)度算法的全局變量ip_vs_rr_scheduler、ip_vs_wrr_scheduler、ip_vs_lc_scheduler、ip_vs_wlc_scheduler中。這些都是ip_vs_scheduler結(jié)構(gòu)體類型的變量，為調(diào)度做準(zhǔn)備。ip_vs_scheduler數(shù)據(jù)結(jié)構(gòu)如表1所示：

struct ip_vs_scheduler struct list_head n_list； 所有負載調(diào)度算法鏈表頭char *name ； 調(diào)度算法名稱atomic_t refcnt； 引用計數(shù)struct module *module; 調(diào)度算法模塊int (*init_service)(struct ip_vs_service *svc)；調(diào)度算法初始化虛擬服務(wù)int (*done_service)(struct ip_vs_service *svc)； 調(diào)度算法終止服務(wù)int (*update_service)(struct ip_vs_service *svc)； 調(diào)度算法更新服務(wù)struct ip_vs_dest* (*schedule)(struct ip_vs_service *svc, struct iphdr *iph)；從所有目的服務(wù)器鏈表中選擇一個要執(zhí)行任務(wù)的服務(wù)器

注冊的4種調(diào)度算法變量的對應(yīng)值如表2所示：

結(jié)構(gòu)體類型 變量1 變量2 變量3 變量4 ip_vs_scheduler ip_vs_rr_scheduler ip_vs_wrr_scheduler ip_vs_lc_scheduler ip_vs_wlc_scheduler n_list {0} {0} {0} {0}name "rr" "wrr" "lc" "wlc"refcnt ATOMIC_INIT(0)ATOMIC_INIT(0)ATOMIC_INIT(0)ATOMIC_INIT(0)module THIS_MODULE THIS_MODULE THIS_MODULE THIS_MODULE init_service() ip_vs_rr_init_svc ip_vs_wrr_init_svc ip_vs_lc_init_svc ip_vs_wlc_done_svc update_service() ip_vs_rr_update_svc ip_vs_wlc_init_svc done_service() ip_vs_rr_done_svc ip_vs_wrr_done_svc ip_vs_lc_done_svc ip_vs_wlc_update_svc schedule() ip_vs_rr_schedule ip_vs_wrr_update_svc ip_vs_lc_update_svc ip_vs_wrr_schedule ip_vs_lc_schedule ip_vs_wlc_schedule

從表1和表2中可以看出四種調(diào)度算法中關(guān)鍵的是init_service()，done_service()，update_service()，schedule()幾個分量對應(yīng)算法的函數(shù)，算法的核心思想一般體現(xiàn)在schedule()分量。在調(diào)度模塊中有一個關(guān)鍵ip_vs_ctl.c文件，該文件用于控制各種調(diào)度算法，該文件中do_ip_set_ctl()函數(shù)主要用于添加、刪除虛擬服務(wù)和真實服務(wù)器。在do_ip_set_ctl()函數(shù)中有一個svc是ip_vs_service結(jié)構(gòu)體類型的變量，通過svc變量的操作實現(xiàn)對服務(wù)或服務(wù)器的管理。當(dāng)管理員進行設(shè)置，添加某個虛擬服務(wù)時，ipvs_add_service函數(shù)通過svc-＞ scheduler -＞init_service()調(diào)用某個算法對應(yīng)分量函數(shù)；編輯ip_vs_edit_service()或刪除ip_vs_edit()服務(wù)時，通過svc-＞ scheduler -＞done_service()調(diào)用某個算法對應(yīng)分量函數(shù)。添加新的服務(wù)器ip_vs_add_dest或修改服務(wù)器ip_vs_edit_dest時，通過svc-＞ scheduler-＞update_service()調(diào)用某個算法對應(yīng)分量函數(shù)。當(dāng)有請求時，調(diào)度器調(diào)用ip_vs_schedule()函數(shù)選擇某個算法，即通過該函數(shù)里的svc-＞ scheduler -＞schedule()選擇已配置好的調(diào)度算法處理請求。

3 結(jié)論

本文就LVS集群的體系結(jié)構(gòu)、軟件層次結(jié)構(gòu)做了介紹，分析了內(nèi)核調(diào)度模塊 IPVS-1.0.9源代碼中四種常用調(diào)度算法的實現(xiàn)過程，為研究LVS調(diào)度模塊提供了一些參考。

[1]朱璇，鄭緯民，汪東升，楊廣文.單一系統(tǒng)映象在機群管理中的實現(xiàn).計算機工程與應(yīng)用，2002.

[2]黃曦.Web服務(wù)器集群負載均衡技術(shù)的應(yīng)用研究[D].重慶大學(xué)，2004.

[3]章文嵩.http://www.linuxvirtualserver.org/.

[4]王霜，修保新，肖衛(wèi)東.Web服務(wù)器集群的負載均衡算法研究[J].計算機工程與應(yīng)用，2004，40(25)：78-80.