讨论一个高性能的查找方法

duanjigang

结构体

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. }
    

复制代码

会以每秒超过5万的速率发送到一个处理程序，处理程序需要做的是在一分钟内江将所有这些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
   

复制代码

这7元组进行合并，大概估算下，每分钟有300万个数据单元。
我起初的做法是开一个哈希表，哈希key值生成算法为

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

复制代码

但是发现不能完全处理，要完全处理300万个节点，大概需要快300秒时间（包括合并完成后遍历哈希表写入数据到内存），也就是快5分钟。
后来打印了详细信息，发现哈希表有些节点的冲突链长度为600以上，一分钟查找次数达到二十几万。肯定是这些节点的查找合并影响到性能了。
不知道有什么好的方法完成这类节点的合并，而且高效，尽量在一分钟之内完成。谢谢！
########################
11月13日，解决了，见23楼，请指出可能问题和看法。谢谢

dreamice

回复 1# duanjigang


    你的hash size有多大？
是不是因为hash冲突太多造成的性能损失问题？

duanjigang

回复  duanjigang


    你的hash size有多大？
是不是因为hash冲突太多造成的性能损失问题？
dreamice 发表于 2010-11-10 14:44

    一开始设置2K，后来改成上万了，也不怎么凑效。
哈希表过长的话，数据汇报时性能也会影响吧？

dreamice

一开始设置2K，后来改成上万了，也不怎么凑效。
哈希表过长的话，数据汇报时性能也会影响吧？
duanjigang 发表于 2010-11-10 14:53

    那你这个问题，明显是hash的问题了

duanjigang

那你这个问题，明显是hash的问题了
dreamice 发表于 2010-11-10 14:56

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

dreamice

你看看现在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. }
    

复制代码

解决hash冲突问题，可以极大的提高性能。

duanjigang

你看看现在linux里面，路由，nf_conntrack，都用了这个hash算法：
static inline u32 jhash_3words(u32 a, ...
dreamice 发表于 2010-11-10 14:58

    好，多谢高手！我去试试

duanjigang

感谢江总，虽然没用到那个算法，但是却从中得到了启发。
首先去掉很影响性能的 %操作符号。
其次把

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

复制代码

改成

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

复制代码

效率无比疯狂啊。
从原来的200多秒降低到20秒以内了。13-19秒。
呵呵，谢谢！

duanjigang

标注下，多多讨论，只要处理时间在一分钟内，都很好！

dreamice

感谢江总，虽然没用到那个算法，但是却从中得到了启发。
首先去掉很影响性能的 %操作符号。
其次把改成效 ...
duanjigang 发表于 2010-11-10 17:50

    你这个要多测试一下，有可能IP地址和端口分布不一样，hash冲突不一样，最终的效果就不一样了。
用移位取代%操作，肯定能提高效率，但如果能更好的解决hash冲突问题，效率可以再上一个档次。