討論一個高性能的查找方法

duanjigang

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

1. 
   
2. struct node
   
3. {
   
4.      u_int32_t srcaddr
   
5.      u_int16_t srcport;
   
6.      u_int32_t dstaddr;
   
7.      u_int16_t dstport;
   
8.      u_int8_t   proto;
   
9.      u_int8_t   input;
   
10.      u_int8_t   output
    
11.      xxxxx
    
12.     xxxxxxx
    
13. }
    

復(fù)制代碼

會以每秒超過5萬的速率發(fā)送到一個處理程序，處理程序需要做的是在一分鐘內(nèi)江將所有這些node按照

1. 
   
2. u_int32_t srcaddr
   
3.      u_int16_t srcport;
   
4.      u_int32_t dstaddr;
   
5.      u_int16_t dstport;
   
6.      u_int8_t   proto;
   
7.      u_int8_t   input;
   
8.      u_int8_t   output
   

復(fù)制代碼

這7元組進(jìn)行合并，大概估算下，每分鐘有300萬個數(shù)據(jù)單元。
我起初的做法是開一個哈希表，哈希key值生成算法為

1. 
   
2.   (srcaddr|dstaddr|srcport|dstport)%HASH_TABLE_SIZE;
   

復(fù)制代碼

但是發(fā)現(xiàn)不能完全處理，要完全處理300萬個節(jié)點，大概需要快300秒時間（包括合并完成后遍歷哈希表寫入數(shù)據(jù)到內(nèi)存），也就是快5分鐘。
后來打印了詳細(xì)信息，發(fā)現(xiàn)哈希表有些節(jié)點的沖突鏈長度為600以上，一分鐘查找次數(shù)達(dá)到二十幾萬�？隙ㄊ沁@些節(jié)點的查找合并影響到性能了。
不知道有什么好的方法完成這類節(jié)點的合并，而且高效，盡量在一分鐘之內(nèi)完成。謝謝！
########################
11月13日，解決了，見23樓，請指出可能問題和看法。謝謝

dreamice

回復(fù) 1# duanjigang


    你的hash size有多大？
是不是因為hash沖突太多造成的性能損失問題？

duanjigang

回復(fù)  duanjigang


    你的hash size有多大？
是不是因為hash沖突太多造成的性能損失問題？
dreamice 發(fā)表于 2010-11-10 14:44

    一開始設(shè)置2K，后來改成上萬了，也不怎么湊效。
哈希表過長的話，數(shù)據(jù)匯報時性能也會影響吧？

dreamice

一開始設(shè)置2K，后來改成上萬了，也不怎么湊效。
哈希表過長的話，數(shù)據(jù)匯報時性能也會影響吧？
duanjigang 發(fā)表于 2010-11-10 14:53

    那你這個問題，明顯是hash的問題了

duanjigang

那你這個問題，明顯是hash的問題了
dreamice 發(fā)表于 2010-11-10 14:56

    是啊，哈希算法不知道哪個更好了，就是想求助一個更好的哈希算法

dreamice

你看看現(xiàn)在linux里面，路由，nf_conntrack，都用了這個hash算法：

1. static inline u32 jhash_3words(u32 a, u32 b, u32 c, u32 initval)
   
2. {
   
3.         a += JHASH_GOLDEN_RATIO;
   
4.         b += JHASH_GOLDEN_RATIO;
   
5.         c += initval;
   
6. 
   
7.         __jhash_mix(a, b, c);
   
8. 
   
9.         return c;
   
10. }
    
11. 
    
12. 
    
13. #define __jhash_mix(a, b, c) \
    
14. { \
    
15.   a -= b; a -= c; a ^= (c>>13); \
    
16.   b -= c; b -= a; b ^= (a<<8); \
    
17.   c -= a; c -= b; c ^= (b>>13); \
    
18.   a -= b; a -= c; a ^= (c>>12);  \
    
19.   b -= c; b -= a; b ^= (a<<16); \
    
20.   c -= a; c -= b; c ^= (b>>5); \
    
21.   a -= b; a -= c; a ^= (c>>3);  \
    
22.   b -= c; b -= a; b ^= (a<<10); \
    
23.   c -= a; c -= b; c ^= (b>>15); \
    
24. }
    

復(fù)制代碼

解決hash沖突問題，可以極大的提高性能。

duanjigang

你看看現(xiàn)在linux里面，路由，nf_conntrack，都用了這個hash算法：
static inline u32 jhash_3words(u32 a, ...
dreamice 發(fā)表于 2010-11-10 14:58

    好，多謝高手！我去試試

duanjigang

感謝江總，雖然沒用到那個算法，但是卻從中得到了啟發(fā)。
首先去掉很影響性能的 %操作符號。
其次把

1. 
   
2. u_int32_t key = (srcaddr | dstaddr | srcport | dstport)%HASH_SIZE;
   

復(fù)制代碼

改成

1. 
   
2. u_int16_t key = (srcaddr | dstaddr | (srcport << 16 | dstport));
   

復(fù)制代碼

效率無比瘋狂啊。
從原來的200多秒降低到20秒以內(nèi)了。13-19秒。
呵呵，謝謝！

duanjigang

標(biāo)注下，多多討論，只要處理時間在一分鐘內(nèi)，都很好！

dreamice

感謝江總，雖然沒用到那個算法，但是卻從中得到了啟發(fā)。
首先去掉很影響性能的 %操作符號。
其次把改成效 ...
duanjigang 發(fā)表于 2010-11-10 17:50

    你這個要多測試一下，有可能IP地址和端口分布不一樣，hash沖突不一樣，最終的效果就不一樣了。
用移位取代%操作，肯定能提高效率，但如果能更好的解決hash沖突問題，效率可以再上一個檔次。