最近被負載均衡這個問題搞得很難受，我遇到的是最簡單的均衡問題，并不是服務器集群，多core等高級負載均衡的問題。
我們的問題簡單描述就是:通過網(wǎng)卡接收數(shù)據(jù)包，然后把數(shù)據(jù)包放入N個隊列。要求:1.每個隊列里數(shù)據(jù)包的數(shù)量差不多相等。2.同一會話的包放入同一個隊列。
下面對考慮過的一些算法作一個總結。
一.輪回調(diào)度 顧名思義就是把數(shù)據(jù)包一個一個地放入N個隊列中。第1個包放入0號隊列，第2個包放入1號隊列，放完N個隊列，再從0號隊列開始放。
二.取余 解出數(shù)據(jù)包的sip和dip.隊列索引index=(sip+dip)%N.很明了，沒什么要說的。
三.異或取余 解聘數(shù)據(jù)包的sip和dip.隊列索引index=((sip+dip)^sip^dip)%N.據(jù)說分散程度會比方法二要好。但找不到數(shù)學依據(jù)。
四.依照RSS. RSS是一種網(wǎng)卡多隊列技術，要完整介紹它，需要寫一篇論文。這里用到的是symmetric rss即對稱RSS。網(wǎng)卡內(nèi)部大致是這樣做的:利用數(shù)據(jù)包的二元/四元/五元組和一個40字節(jié)的固定值，通過一種hash算法，算出一個hash值。然后取這個hash值的低7位，這個低7位與隊列索引號形成一張RETA表，通過這張表，只要知道hash值的低7位就能知道數(shù)據(jù)包要放入哪個隊列。至于為什么是低7位呢？我猜測這是一個適中的值，如果取8位或9位，表的數(shù)據(jù)量就會比較大，查詢相對耗時，如果取少了，隨機程度就得不到保證。根據(jù)上面的知識，就可以得出隊列索引 index=hash_value%N.這里對N取余相對于維護了一張
(0,1,2....N-1,0,1,2...N-1,0,1,2....N-1)的表。如果要修改表的排列，可自己新建一張自定義的表.
五.仿一致性hash 至于為什么有一個“仿”字，那是因為我們這里的應用場景與其真正的定義不一樣，只是運用其思想。一致性hash沒有圖我是表達不清楚了，可自行百度。反正對于我這里的場景，相當于自定義了一張第四步中的RETA表，定義格式如下
default_tbl[128]=
{0,0,0,...
1,1,1,...
2,2,2,...
...,...
N-1,N-1,N-1...}
與第四步的表相比，只不過是形式不同。
所以這種方法的做法就是通過sip和dip求出hash值，通過hash值的低7位，找到表中對應的隊列序號，把數(shù)據(jù)包放入該隊列。
對于以上幾種算法，第一種雖然說最均勻，但不行，因為確保不了同一會話的數(shù)據(jù)包在同一隊列。
第三種的散列度比第二種要好。
第四種和第五種基本差不多，就是RETA表中的對應關系不一樣，如果是確定的流量，通過修改那張表，一定能做到負載均衡的。就算是未知的流量，也能做到大致均勻，但要是同一會話的量太大了，愛因斯坦也沒辦法，現(xiàn)在遇到的就是這種情況，好煩。
晚安。
