歡迎來到Linux教程網
Linux教程網
Linux教程網
Linux教程網
您现在的位置: Linux教程網 >> UnixLinux >  >> Linux編程 >> Linux編程

IPVS基於應用層任意偏移字段HASH值的負載均衡算法

在比較早的那些年,我曾經寫了一個負載均衡調度算法模塊,是基於應用層協議包任意偏移量開始的一段固定長度的數據計算一個值,然後將這個值hash到不同的服務器。那時覺得沒啥用,就沒有再繼續,直到前一段時間的一段思考以及前幾天的一次預研。我決定作文以記之,以後說不定能用得著。

1.UDP服務的負載均衡

以前使用UDP的服務很少,雖然HTTP並沒有說一定要是TCP,但事實上幾乎沒有UDP上的HTTP。但是隨著網絡可靠性的增加,網絡集中控制機制與分布式優化技術的日益成熟,使用UDP的場合越來越多。

使用UDP就意味著你必須在應用層做傳輸控制,其實這還不是主要的,主要的問題是現在沒有什麼熟知的UDP服務,比如你不能指望在負載均衡器上內置一個關於OpenVPN服務的負載均衡,但是對於基於TCP的HTTP服務幾乎總是被內置於任何網關內部。因為作為一個著名的應用層協議,HTTP在各個層面都擁有自己的一套成熟的標准,大家均認可這些標准。使用UDP你必須實現一個符合常理的連接過期機制,由於在UDP層面根本就不可能識別一個"連接"的斷開,這就意味著要麼在應用層識別,比如發送一個特殊的UDP包表示要“斷開”了,要麼就是對一個UDP“連接”設置一個超時。

雖然存在這麼多的問題,但是在移動時代,有些問題還真必須使用UDP作為傳輸協議才能解決。

2.移動網絡的問題

如果使用手機或PAD訪問服務,由於這些移動終端時刻處於移動中,其IP地址也會不斷變化(請不要考慮LISP,這只是個理想),如果使用TCP作為服務的承載協議,那就意味著TCP會不斷地斷開再重連-TCP和IP是相關的,如果使用UDP,就沒有這個問題,代價只是在應用層記錄連接信息。這是一個會話層缺失的問題,雖然有人不太認同,但是畢竟鍵盤黨噴子說再多也沒有用,實現一個這樣的機制跑出來效果才是王道。鑒於此,我給OpenVPN做了手術。

OpenVPN也是用5元組來識別一個特定客戶端的,但是由於存在終端移動IP地址變化的問題,這會導致OpenVPN服務端頻繁斷開和客戶端的連接然後等待重連,雖然這不是由於TCP導致的,但是卻道出了一個問題的本質,只要是用5元組來識別連接,IP地址的變化都會導致連接斷開。因此我在OpenVPN協議的頭裡面加了一個服務器內部唯一的4個字節的所謂sessionID用以補充缺失的會話層。以後OpenVPN服務端不再用5元組來識別到一個客戶端的連接了,而是使用這個唯一的sessionID來識別,這樣對於UDP的情況,即便是客戶端的IP地址發生變化,服務端也不會斷開連接,因為sessionID沒有變化。注意,這個對於TCP模式的服務是沒有用的,因為TCP處在傳輸層,在OpenVPN識別到sessionID以前,TCP本身就先斷開了,除非在accept調用之上再封裝一層,做到雖然TCP連接(TCP連接)在不斷的斷開/重連,但是OpenVPN連接(會話層連接)始終不會斷。但是由於工作量比較大,作罷。

在強大的功能展現的效果面前,任何的唧唧歪歪都是蒼白的。通過引入一個很小的字段(4字節或者2字節),完美解決了“UDP長連接”(還真不能用TCP,除非引入LISP)時IP地址切換的問題,這就是UDP的力量。OpenVPN如此,為何別的就不行。事實上,任何的應用層協議都可以用UDP來封裝,將連接控制(連接,排序,重傳,斷開等)等操縱進行標准化置於上層即可。然而,如果客戶端的IP地址不斷變化,負載均衡器還能基於源IP做負載均衡嗎?

很顯然是可以的,但是卻是有問題的。因為有可能在同一客戶端變化了IP地址之後,負載均衡器會將其分發到不同的服務器上,然而實際上,它們的sessionID並沒有變化,因為將不能再根據源IP地址做負載均衡了。那怎麼辦?答案就是基於sessionID做負載均衡。

3.基於UDP協議應用層的sessionID做負載均衡

一步一步地,我們就走到了這裡,現在必須回答的問題是如何做。sessionID是什麼?它並非標准協議的一部分。首先你必須保證數據包中一定要有這個字段,這個一般可以保證,我肯定知道我在配置什麼東西,其次,問題是這個sessionID在什麼地方?這決不能強行規定。事實上,所謂的sessionID就是在一次連接中,數據包中不會變化的那個部分,僅此。因此,最好的辦法就是讓配置者自己決定它在什麼地方以及它的長度是多少。

有了相對應用層開始的偏移和長度,取字段和算HASH就猶如探囊取物了,幾乎和取源IP一樣,只是多了幾個計算而已,IPVS的代碼如下:

net/netfilter/ipvs/ip_vs_offh.c:

/* 
 * IPVS:        Layer7 payload Hashing scheduling module 
 * 
 * Authors:    ZHAOYA 
 *              基於ip_vs_sh/dh修改而來,詳細注釋請參見: 
 *              net/netfilter/ipvs/ip_vs_sh.c 
 *              net/netfilter/ipvs/ip_vs_dh.c 
 */ 
 
#include <linux/ip.h> 
#include <linux/tcp.h> 
#include <linux/module.h> 
#include <linux/kernel.h> 
#include <linux/skbuff.h> 
#include <linux/ctype.h> 
 
#include <net/ip.h> 
#include <net/ip_vs.h> 
 
struct ip_vs_offh_bucket { 
    struct ip_vs_dest      *dest;   
}; 
 
struct ip_vs_offh_data { 
    struct ip_vs_offh_bucket *tbl; 
    u32 offset; 
    u32 offlen; 
}; 
 
#define IP_VS_OFFH_TAB_BITS              8 
#define IP_VS_OFFH_TAB_SIZE              (1 << IP_VS_OFFH_TAB_BITS) 
#define IP_VS_OFFH_TAB_MASK              (IP_VS_OFFH_TAB_SIZE - 1) 
 
/* 
 * 全局變量 
 * offset:Layer7計算hash值的payload偏移量(相對於Layer7頭) 
 * offlen:Layer7計算hash值的payload長度 
 */ 
static u32 offset, offlen; 
 
static int skip_atoi(char **s) 

    int i=0; 
 
    while (isdigit(**s)) 
        i = i*10 + *((*s)++) - '0'; 
    return i; 

 
static inline struct ip_vs_dest * 
ip_vs_offh_get(struct ip_vs_offh_bucket *tbl, const char *payload, u32 length) 

    __be32 v_fold = 0; 
    /* 算法有待優化 */ 
    v_fold = (payload[0]^payload[length>>2]^payload[length])*2654435761UL; 
 
    return (tbl[v_fold & IP_VS_OFFH_TAB_MASK]).dest; 

 
static int 
ip_vs_offh_assign(struct ip_vs_offh_bucket *tbl, struct ip_vs_service *svc) 

    int i; 
    struct ip_vs_offh_bucket *b; 
    struct list_head *p; 
    struct ip_vs_dest *dest; 
 
    b = tbl; 
    p = &svc->destinations; 
    for (i=0; i<IP_VS_OFFH_TAB_SIZE; i++) { 
        if (list_empty(p)) { 
            b->dest = NULL; 
        } else { 
            if (p == &svc->destinations) 
                p = p->next; 
 
            dest = list_entry(p, struct ip_vs_dest, n_list); 
            atomic_inc(&dest->refcnt); 
            b->dest = dest; 
 
            p = p->next; 
        } 
        b++; 
    } 
    return 0; 

 
static void ip_vs_offh_flush(struct ip_vs_offh_bucket *tbl) 

    int i; 
    struct ip_vs_offh_bucket *b; 
 
    b = tbl; 
    for (i=0; i<IP_VS_OFFH_TAB_SIZE; i++) { 
        if (b->dest) { 
            atomic_dec(&b->dest->refcnt); 
            b->dest = NULL; 
        } 
        b++; 
    } 

 
static int ip_vs_offh_init_svc(struct ip_vs_service *svc) 

    struct ip_vs_offh_data *pdata; 
    struct ip_vs_offh_bucket *tbl; 
 
    pdata = kmalloc(sizeof(struct ip_vs_offh_data), GFP_ATOMIC); 
    if (pdata == NULL) { 
        pr_err("%s(): no memory\n", __func__); 
        return -ENOMEM; 
    } 
 
    tbl = kmalloc(sizeof(struct ip_vs_offh_bucket)*IP_VS_OFFH_TAB_SIZE, 
              GFP_ATOMIC); 
    if (tbl == NULL) { 
        kfree(pdata); 
        pr_err("%s(): no memory\n", __func__); 
        return -ENOMEM; 
    } 
 
    pdata->tbl = tbl; 
    pdata->offset = 0; 
    pdata->offlen = 0; 
 
    svc->sched_data = pdata; 
 
    ip_vs_offh_assign(tbl, svc); 
 
    return 0; 

 
static int ip_vs_offh_done_svc(struct ip_vs_service *svc) 

    struct ip_vs_offh_data *pdata = svc->sched_data; 
    struct ip_vs_offh_bucket *tbl = pdata->tbl; 
 
    ip_vs_offh_flush(tbl); 
 
    kfree(tbl); 
    kfree(pdata); 
 
    return 0; 

 
static int ip_vs_offh_update_svc(struct ip_vs_service *svc) 

    struct ip_vs_offh_bucket *tbl = svc->sched_data; 
 
    ip_vs_offh_flush(tbl); 
    ip_vs_offh_assign(tbl, svc); 
 
    return 0; 

 
static inline int is_overloaded(struct ip_vs_dest *dest) 

    return dest->flags & IP_VS_DEST_F_OVERLOAD; 

 
static struct ip_vs_dest * 
ip_vs_offh_schedule(struct ip_vs_service *svc, const struct sk_buff *skb) 

    struct ip_vs_dest *dest; 
    struct ip_vs_offh_data *pdata; 
    struct ip_vs_offh_bucket *tbl; 
    struct iphdr *iph; 
    void *transport_hdr; 
    char *payload; 
    u32 hdrlen = 0; 
    u32 _offset = 0; 
    u32 _offlen = 0; 
 
    iph = ip_hdr(skb); 
    hdrlen = iph->ihl*4; 
    if (hdrlen > skb->len) { 
        return NULL; 
    } 
    transport_hdr = (void *)iph + hdrlen; 
 
    switch (iph->protocol) { 
        case IPPROTO_TCP: 
            hdrlen += (((struct tcphdr*)transport_hdr)->doff)*4; 
            break; 
        case IPPROTO_UDP: 
            hdrlen += sizeof(struct udphdr); 
            break; 
        default: 
            return NULL; 
    } 
#if 0 
    { 
        int i = 0; 
        _offset = offset; 
        _offlen = offlen; 
        payload = (char *)iph + hdrlen + _offset; 
        printk("begin:iplen:%d  \n", hdrlen); 
        for (i = 0; i < _offlen; i++) { 
            printk("%02X ", payload[i]); 
        } 
        printk("\nend\n"); 
        return NULL; 
 
    } 
#endif 
 
    pdata = (struct ip_vs_offh_datai *)svc->sched_data; 
 
    tbl = pdata->tbl; 
    _offset = offset;//pdata->offset; 
    _offlen = offlen;//pdata->offlen; 
    if (_offlen + _offset > skb->len - hdrlen) { 
        IP_VS_ERR_RL("OFFH: exceed\n"); 
        return NULL; 
    } 
 
    payload = (char *)iph + hdrlen + _offset; 
 
    dest = ip_vs_offh_get(tbl, payload, _offlen); 
    if (!dest 
        || !(dest->flags & IP_VS_DEST_F_AVAILABLE) 
        || atomic_read(&dest->weight) <= 0 
        || is_overloaded(dest)) { 
        IP_VS_ERR_RL("OFFH: no destination available\n"); 
        return NULL; 
    } 
 
    return dest; 

 
static struct ip_vs_scheduler ip_vs_offh_scheduler = 

    .name =        "offh", 
    .refcnt =      ATOMIC_INIT(0), 
    .module =      THIS_MODULE, 
    .n_list  =      LIST_HEAD_INIT(ip_vs_offh_scheduler.n_list), 
    .init_service =    ip_vs_offh_init_svc, 
    .done_service =    ip_vs_offh_done_svc, 
    .update_service =  ip_vs_offh_update_svc, 
    .schedule =    ip_vs_offh_schedule, 
}; 
 
static ssize_t ipvs_sch_offset_read(struct file *file, char __user *buf, size_t count, loff_t *ppos) 

    int ret = 0; 
    ret = sprintf(buf, "offset:%u;offlen:%u\n", offset, offlen); 
    return ret; 

 
/* 
 * 設置offset/offset length 
 * echo offset:$value1  offlen:$value2 >/proc/net/ipvs_sch_offset 
 */ 
static int ipvs_sch_offset_write(struct file *file, const char __user *buf, size_t count, loff_t *ppos) 

    int ret = count; 
    char *p = buf, *pstart; 
    if ((p = strstr(p, "offset:")) == NULL) { 
        ret = -EINVAL; 
        goto out; 
    } 
    p += strlen("offset:"); 
    pstart = p; 
    if ((p = strstr(p, " ")) == NULL) { 
        ret = -EINVAL; 
        goto out; 
    } 
    p[0] = 0; 
    offset = skip_atoi(&pstart); 
    if (offset == 0 && strcmp(pstart, "0")) { 
        ret = -EINVAL; 
        goto out; 
    } 
    p += strlen(";"); 
    if ((p = strstr(p, "offlen:")) == NULL) { 
        ret = -EINVAL; 
        goto out; 
    } 
    p  += strlen("offlen:"); 
    pstart = p; 
    offlen = skip_atoi(&pstart); 
    if (offlen == 0 && strcmp(pstart, "0")) { 
        ret = -EINVAL; 
        goto out; 
    } 
out: 
    return ret; 

 
/* 
 * 由於不想修改用戶態的配置接口,還是覺得procfs這種方式比較靠普 
 **/ 
static const struct file_operations ipvs_sch_offset_file_ops = { 
    .owner          = THIS_MODULE, 
    .read          = ipvs_sch_offset_read, 
    .write          = ipvs_sch_offset_write, 
}; 
 
struct net *net = &init_net; 
static int __init ip_vs_offh_init(void) 

    int ret = -1; 
    if (!proc_create("ipvs_sch_offset", 0644, net->proc_net, &ipvs_sch_offset_file_ops)) { 
        printk("OFFH: create proc entry failed\n"); 
        goto out; 
    } 
    return register_ip_vs_scheduler(&ip_vs_offh_scheduler); 
out: 
    return ret; 

 
static void __exit ip_vs_offh_cleanup(void) 

    remove_proc_entry("ipvs_sch_offset", net->proc_net); 
    unregister_ip_vs_scheduler(&ip_vs_offh_scheduler); 

 
 
module_init(ip_vs_offh_init); 
module_exit(ip_vs_offh_cleanup); 
MODULE_LICENSE("GPL"); 

實際上,很多高大上的負載均衡實現都不是基於內核協議棧的,它們要麼是直接用硬卡來做,要麼是用戶態協議棧,所以本文的原則也是可以用到那些方面的,只不過,我所能為力的並且簡單的只有Linux IPVS,畢竟先把代碼跑起來要比長篇大論好的多,起碼我是這麼認為的。

4.問題在哪裡-連接緩存

我認為IPVS機制該改了,同時我覺得nf_conntrack也該改了。

我們知道,在IPVS中,可能只有一個流的第一個數據包才會去調用“特定協議”的conn_schedule回調,選出一個destination,即real server之後,這些信息就會被保存在“特定協議‘的conn緩存中。如果你看一下這個所謂的“特定協議”,就會發現它事實上是“第四層協議”,即傳輸層協議,TCP或者UDP,而在這一層,很顯然,一個連接就是一個5元組。那麼,即便我針對第一個數據包,即一個流的首包選擇了一個real server,並將其存入了conn緩存,那麼該流的客戶端在IP地址變化了之後,顯然conn緩存中找不到了,那麼就會自動進入conn_schedule,由於使用固定偏移的paylaod進行schedule,那麼肯定還是原來的那個real server被選擇,此時會在conn緩存中增加一條新的條目用於以後的匹配,老的那條conn緩存沒有用了,等待過期,只要客戶端不改變IP地址且新的這個conn緩存項不過期,這個緩存將會一直命中,一旦客戶端改變了IP地址,一切重新開始。可見,這是一個自動且正確的過程。但是,最好有一個針對舊五元組的刪除通知機制,而不是等待它自己過期。

如果等待它自己過期,那麼試想一種超時時間很久的情況。客戶端A五元組為tuple1使用sessionID1匹配到了一個real server1,設置了conn緩存conn1,過了一些時間,客戶端A更換了IP地址,此時理所當然地,它不會再匹配到conn1,緩存不命中,依靠不變的sessionID1它在conn_schedule中選擇了同樣的real server1,設置了新的conn2緩存項,然後conn1就變成僵屍了,等待超時刪除。過了很久,客戶端2攜帶接管了客戶端1的老的IP地址和UDP端口,訪問了同樣的UDP服務,此時客戶端2的五元組為tuple1,攜帶sessionID2,由sessionID2計算得到的real server本應該是real server2,但是由於命中了僵屍conn1,它將被負載到real server1,此時客戶端2更改了IP地址,它的五元組變成了tuple2',經過conn_schedule計算後,它匹配到了real server2,由於為它服務的初始real server為real server1,這將導致連接切換。這就是沒有刪除通知機制導致的問題。

問題的解決似乎比較簡單,辦法有二,第一種辦法就是為ip_vs_protocol結構體增加一個五元組變更通知的回調函數,比如叫做conn_in_update/conn_out_update,或者直接增加一個conn_in_delete/conn_out_delete,要麼就是一種更加徹底的解決方案,即直接用sessionID來記錄連接。而這後者正是我正准備為Linux的nf_conntrack所做的一個外科手術。

當然,我不會走火入魔到徹底放棄五元組的連接跟蹤方式,我只是為nf_conntrack增加了一種選擇,正如conntrack增加了zone的支持一樣。我相信,即便我不動手,過一個一年半載,肯定會有人這麼做的,以往的事實預示了這一點。

Copyright © Linux教程網 All Rights Reserved