傳輸模式：
[直接路由方式]：直接查找路由表，以原始資料包的目的位址為查找鍵。本地配置的ip位址就是資料包的目的位址，資料既然已經到了本地為何還要查找，為何還要繼續路由？這是因為本地的目的地到達情景僅僅是一個假象，真正提供服務的機器還在後面，也就是說服務被負載均衡了。此時問題是，既然本地配置了一個目的地ip位址，其它機器還能配置這個ip位址嗎？那樣的話豈不ip沖突了嗎？
在直接路由模式中，負載均衡器和“後面”真正提供服務的機器都配置有同一個ip位址，在負載均衡器中，該ip配置在一個實體的真實網卡上，用來接收用戶端的資料包，很顯然，這些資料包最終肯定走到了ip_local_deliver這個函數中，接下來資料包要通過NF_IP_LOCAL_IN這個hook，恰好ipvs等在這裡，接着調用ip_vs_in這個hook函數，經過判斷發現資料包需要進行負載均衡後，會調用已經建立的到真實機器的連接配接ip_vs_conn這個資料結構的packet_xmit回調函數，在該函數中會以ip_vs_conn中的資訊來查找路由，ip_vs_conn中有三個字段很重要：caddr-用戶端的ip；vaddr-虛拟ip，也就是在負載均衡器實體網卡上配置的ip，同時該ip将綁定在所有提供真實服務的所謂均衡機器的loopback網卡上；daddr-這是均衡機器的實體網卡的ip，簡單點了解為負載均衡器直連。
資料從查找到的daddr路由的出口裝置發送了出去，最終資料到達了這個daddr，然後進入路由查找，看是local-in還是forward，在查找的時候會調用fib_lookup函數，它會查找各個路由表，或者它會周遊各個路由規則表--在配置了MULTIPLE_TABLES的情況下，最終它發現目的ip位址就是本機--綁定在loopback上的位址，也就是vaddr，然後資料被交由上層真正地被處理。之是以可以做到從一個網口進入的本地接收資料包的目的位址并沒有配置在該網口上是因為路由查找的預設政策是不檢查入口網卡的ip和目的地ip的關系的，這麼檢查也沒有多大意義，因為大多數的過路包的目的ip和本機網卡ip本來就沒有什麼關系，而在檢查路由的伊始還區分不出這是過路包還是本地接收包。不過想實作入口網口和路由的關系綁定也不是不能實作，辦法就是配置一條政策路由或者在MULTIPLE_TABLES的情況下添加一個新的規則表，将fib_rule的r_ifindex字段進行硬綁定即可，這樣的話fib_lookup中會對其進行檢查：(r->r_ifindex && r->r_ifindex != flp->iif)
為了将這些真實的處理機器徹底隐藏，需要隐藏它們的虛拟ip位址，由于所有的機器都配置了同樣的vaddr，那麼免費arp的發送會導緻大量的ip沖突，是以需要做的就是将這些ip隐藏，僅僅開放給進入包的協定棧路由查找。所謂的隐藏就是不讓本機協定棧以外的别人知道，由于任何的ip在以太網中都是通過arp來使别人知道自己存在的，你要ping一台區域網路的機器，首先要arp一下，得到回複後方知目的地的mac位址，這樣才能實際發送，是以隻要能夠抑制這個虛拟網址發送arp回應即可，它本身配置在loopback上，為了不使它響應外部的任何arp請求，隻需要配置一個核心參數即可--arp_ignore，這個參數控制對ip沒有配置在收到arp請求的網卡上的請求的回複政策，vaddr配置在loopback上，而arp請求肯定是由ethX進入的，是以這樣可以不回應任何arp請求，同時它自己也不會廣播免費arp，是以這個vaddr實際上是一個“無用”的ip，無用的意義在于它無法被尋址。
真實的伺服器監聽哪個ip位址呢？它監聽的就是vaddr，就是配置在loopback上的vaddr，這個位址除了負載均衡器可以連到，對于其它主機是不可見的，因為它無法響應arp請求(arp_ignoe)，然而你還是可以用vaddr去連接配接真實伺服器上的服務，前提是設定一條靜态路由指向特定的真實伺服器，實際上如果設定了靜态路由，ping之也是可以通的，之是以設定arp_ignore是怕真實伺服器回應arp請求和頻發arp廣播，很多情況下是沒有必要設定它的。
[NAT方式]：這種方式配置起來比較簡單，不需要配置虛拟ip以及arp核心參數之類的，但是性能較直接路由模式就有點不佳了，畢竟要做的事情多了。NAT模式很簡單，就是将ip位址和端口資訊修改成真實均衡機器們的ip和端口，這樣真實的服務機器就被隐藏在負載均衡器後面了，思想和普通的nat是一樣的。
[隧道模式]：隧道模式就是将資料重新打包成一個新的ip資料包，然後可以通過修改代碼實作發送到虛拟網卡，由應用程式來做負載均衡，也可以直接發送到一個ipip隧道中去。
排程算法：
[輪轉算法]：一個接着一個地提供服務...
[權重...]：主要是根據配置讓核心了解到各個伺服器的“能力”，不再平等的對待所有伺服器，而是盡可能讓處理能力強的伺服器盡可能多的處理多的請求
[...算法]：(排程本質上和程序排程是一緻的，略)
關鍵資料結構：
[struct ip_vs_app]：代表一個應用類型，也就是需要負載均衡的服務，其中port和protocol描述了其應用層資訊，另外該結構體包含了大量回調函數，這些函數和具體的應用相關聯。
[struct ip_vs_conn]：一個連接配接，這是一個負載均衡器和真實提供服務機器之間的連接配接，一個負載均衡器對于同一個ip_vs_app同時保持着多個連接配接，這就是負載均衡的意義。其中caddr代表需要服務的用戶端的ip位址，vaddr為負載均衡器的ip位址，在直接路由模式中 它還是真實機器的綁定于loopback的虛拟ip位址，daddr為目的ip位址，也就是真實提供服務機器的可路由可被尋址的ip位址，app為該連接配接綁定的ip_vs_app，packet_xmit為發送回調函數，對于不同的模式其實作不同。
[struct ip_vs_service]：一種服務的描述，上述的ip_vs_conn就是該ip_vs_service的一個連接配接。其addr代表一個虛拟的ip位址，也就是對外公開的服務ip位址，而實際上服務并不由該ip提供，而需要路由到另外的ip上，protocol和port的含義和addr相同，隻是它們是第四層的資訊。
[struct ip_vs_protocol]：四層協定标示。conn_schedule為其排程回調函數。注意，負載均衡排程是基于四層協定的，而發送是基于連接配接的。
代碼：
[在netfilter體系中注冊幾個鈎子]：
static struct nf_hook_ops ip_vs_in_ops = {
.hook = ip_vs_in,
.owner = THIS_MODULE,
.pf = PF_INET,
.hooknum = NF_IP_LOCAL_IN,
.priority = 100,
};
NF_IP_LOCAL_IN表明資料的目的地是該虛拟伺服器，ip_local_deliver中會調用該鈎子點，ip_vs_in是其處理函數：
static unsigned int ip_vs_in(...)
{
struct sk_buff *skb = *pskb;
struct iphdr *iph;
struct ip_vs_protocol *pp;
struct ip_vs_conn *cp;
...
pp = ip_vs_proto_get(iph->protocol); //得到注冊的可被負載均衡的四層協定
if (unlikely(!pp)) //如果沒有的話就按照正常方式被接收
return NF_ACCEPT;
ihl = iph->ihl << 2;
cp = pp->conn_in_get(skb, pp, iph, ihl, 0); //檢查該包是否屬于一個已經建立的ip_vs_conn
if (unlikely(!cp)) {
int v; //如果沒有找到這個ip_vs_conn，則初始化一個新的
if (!pp->conn_schedule(skb, pp, &v, &cp)) //排程，就是初始化一個cp
return v;
}
restart = ip_vs_set_state(cp, IP_VS_DIR_INPUT, skb, pp);
if (cp->packet_xmit) //在建立的連接配接或者舊的連接配接上發送資料
ret = cp->packet_xmit(skb, cp, pp);
else {
IP_VS_DBG_RL("warning: packet_xmit is null");
ret = NF_ACCEPT;
...
return ret;
}
既然資料發了出去，回複包肯定是要回來的，ipvs的實作中有一個不對稱性，就是說順向的包會被導入本地後作抉擇，可是真實伺服器的回應包卻直接被forward了，回應包并沒有被導入本地，因為在順向的包發送給真實服務期的時候并沒有做snat操作，頂多在NAT模式下做一下dnat操作，是以回應包的目的ip和端口仍然是原始用戶端的ip和端口，是以資料回到負載均衡器的時候，負載均衡器發現目的位址并不是自己，于是就forward了，這種沒有snat的不對稱實作對于效率是有提高的，但是要慎重自行設計此類架構，因為它有一個危險，那就是負載均衡器被繞過的情況，真實的伺服器到達用戶端并不一定非要經過負載均衡器，如果端口在ip_vs_in中被dnat改變了，那麼資料由真實伺服器不經負載均衡器回到用戶端時就會出現混亂(ipvs中是不會出現這類情況的，因為直接路由模式是不更改ip和端口資訊的)，但是一般情況下通過配置可以避免這種情況。下面看反向包的處理：
static struct nf_hook_ops ip_vs_out_ops = {
.hook = ip_vs_out,
.hooknum = NF_IP_FORWARD,
static unsigned int ip_vs_out(...)
struct sk_buff *skb = *pskb;
int ihl;
if (skb->nfcache & NFC_IPVS_PROPERTY)
pp = ip_vs_proto_get(iph->protocol);
if (unlikely(!pp)) //正常包--非負載均衡反向包
cp = pp->conn_out_get(skb, pp, iph, ihl, 0);
...//正常包--非負載均衡反向包
...//下面無論如何都要調用snat_handler，統一處理了直接路由模式和NAT模式，這是不對稱設計的結果
if (pp->snat_handler && !pp->snat_handler(pskb, pp, cp))
goto drop;
skb = *pskb;
skb->nh.iph->saddr = cp->vaddr; //無論如何更新源ip，雖然對于直接路由模式這是沒有必要的，這也是不對稱設計的結果
對于tcp協定，tcp_conn_schedule是ip_vs_protocol的排程函數：
static int tcp_conn_schedule(struct sk_buff *skb,
struct ip_vs_protocol *pp,
int *verdict, struct ip_vs_conn **cpp)
struct ip_vs_service *svc;
struct tcphdr _tcph, *th;
... //找到tcp的一個ip_vs_service，根據是虛拟服務的ip-vaddr和port
if (th->syn && (svc = ip_vs_service_get(skb->nfmark, skb->nh.iph->protocol,
skb->nh.iph->daddr, th->dest))) {
...
*cpp = ip_vs_schedule(svc, skb); //着手進行排程
return 1;
struct ip_vs_conn *ip_vs_schedule(struct ip_vs_service *svc, const struct sk_buff *skb)
struct ip_vs_conn *cp = NULL;
struct iphdr *iph = skb->nh.iph;
struct ip_vs_dest *dest;
__u16 _ports[2], *pptr;
if (svc->flags & IP_VS_SVC_F_PERSISTENT)
return ip_vs_sched_persist(svc, skb, pptr);
if (!svc->fwmark && pptr[1] != svc->port) {
dest = svc->scheduler->schedule(svc, skb); //根據排程算法選擇一個可用的真實伺服器
cp = ip_vs_conn_new(iph->protocol, //設定一個到真實伺服器的連接配接
iph->saddr, pptr[0],
iph->daddr, pptr[1],
dest->addr, dest->port?dest->port:pptr[1],
0,
dest); //其中的ip_vs_bind_dest更新了被選擇伺服器的負載情況
if (cp == NULL)
return NULL;
ip_vs_conn_stats(cp, svc); //更新計數
return cp;
對于直接路由模式，一個連接配接的packet_xmit是ip_vs_dr_xmit：
#define IP_VS_XMIT(skb, rt) /
do { /
(skb)->ipvs_property = 1; /
(skb)->ip_summed = CHECKSUM_NONE; /
NF_HOOK(PF_INET, NF_IP_LOCAL_OUT, (skb), NULL, /
(rt)->u.dst.dev, dst_output); /
} while (0)
int ip_vs_dr_xmit(struct sk_buff *skb, struct ip_vs_conn *cp,
struct ip_vs_protocol *pp)
if (!(rt = __ip_vs_get_out_rt(cp, RT_TOS(iph->tos))))
goto tx_error_icmp;
dst_release(skb->dst);
skb->dst = &rt->u.dst; //設定新的出口路由
IP_VS_XMIT(skb, rt); //将資料發送出去
[排程算法過程]：無非就是按照特定政策選擇一個真實的伺服器，然後将資料扔過去而已。可以考慮修改代碼實作真實伺服器定期向負載均衡器彙報自己的負載情況，這樣最好讓使用者态程序配合實作
[總的過程]：
1.資料包進入-
2.進入虛拟服務-
3.查找已有的到真實伺服器的連接配接-
4.若查到，到5-
5.發送-結束
6.若查不到-
7.挑選一個真實伺服器并初始化一個到該伺服器的連接配接，到5-
8.等待反向資料，找到已有連接配接，處理-
5.1.nat模式--修改目的位址到真實伺服器的位址，資料包變化
5.2.直接路由模式--直接以真實伺服器的一個實體網卡的ip為鍵值查找路由，資料包不變化
[總結]：ipvs實作的是一個一對多的映射，這個機制用一對一的nat技術是無法實作的，但是ipvs也是“幾乎”基于連接配接的負載均衡，但是可以通過設定逾時時間為很短的值來變通地實作基于多個包的負載均衡，不管怎樣，這仍然不是一個完全基于包的負載均衡方案。
本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1271757
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)