PHP
首页 | 下载 | 博客 | 链接

查找 区域

工具

查看代码的工具推荐用Eclipse Platform,将includes文件路径设置好以后,查找原型/函数/结构相当方便,如果怕麻烦,lxr也是个不错的选择,比如lxr.linux.no


相关链接

启动中的ipvs
运行中的ipvs
ipvs的调度
ipvs的数据报转送

ipvs的hash算法
数据包结构/操作分析
[转]ipvs基本原理/框架


资源链接

netfilter官方指南(中文)
ipvs官方网站(中文)
developerWorks-cluster(中文)


说明

文章中出现的内核代码版本是linux-2.6.26,为了保证行号的一致性,中文的注释没有插入回车/换行符.可能会显得有些紧巴巴的.
由于个人能力有限,网站内容存在许多错误和不足,希望读者能踊跃给予批评指正或建议. 本人联系方式:yubo@yubo.org

ipvs的Hash表

net/ipv4/ipvs/ip_vs_ctl.c
  1.  /*
    2. 

  2.   *    Hash table: for virtual service lookups
    3. 

  3.   */
    4. 

  4.  #define IP_VS_SVC_TAB_BITS 8
    5. 

  5.  #define IP_VS_SVC_TAB_SIZE (1 << IP_VS_SVC_TAB_BITS)
    6. 

  6.  #define IP_VS_SVC_TAB_MASK (IP_VS_SVC_TAB_SIZE - 1)
    7. 

  7.   
    8. 

  8.  /* the service table hashed by <protocol, addr, port> */
    9. 

  9.  static struct list_head ip_vs_svc_table[IP_VS_SVC_TAB_SIZE];
    10. 

  10.  /* the service table hashed by fwmark */
    11. 

  11.  static struct list_head ip_vs_svc_fwm_table[IP_VS_SVC_TAB_SIZE];

ip_vs_svc_table[],ip_vs_svc_fwm_table[]是用来存放虚拟服务器信息的hash列表,每个桶都是一个双向链表结构,不同的hashkey的产生方式不一样

net/ipv4/ipvs/ip_vs_ctl.c
  1.  /*
    2. 

  2.   *    Returns hash value for virtual service
    3. 

  3.   */
    4. 

  4.  static __inline__ unsigned
    5. 

  5.  ip_vs_svc_hashkey(unsigned proto, __be32 addr, __be16 port)
    6. 

  6.  {
    7. 

  7.      register unsigned porth = ntohs(port);
    8. 

  8.   
    9. 

  9.      return (proto^ntohl(addr)^(porth>>IP_VS_SVC_TAB_BITS)^porth)
    10. 

  10.          & IP_VS_SVC_TAB_MASK;
    11. 

  11.  }
    12. 

  12.   
    13. 

  13.  /*
    14. 

  14.   *    Returns hash value of fwmark for virtual service lookup
    15. 

  15.   */
    16. 

  16.  static __inline__ unsigned ip_vs_svc_fwm_hashkey(__u32 fwmark)
    17. 

  17.  {
    18. 

  18.      return fwmark & IP_VS_SVC_TAB_MASK;
    19. 

  19.  }

ip_vs_svc_table是用过svc的协议/地址/端口来生成key,ip_vs_svc_fwm_table则是直接用firewall掩码于自己的IP_VS_SVC_TAB_MASK按位与获得

net/ipv4/ipvs/ip_vs_ctl.c
  1.  /*
    2. 

  2.   *    Hash table: for real service lookups
    3. 

  3.   */
    4. 

  4.  #define IP_VS_RTAB_BITS 4
    5. 

  5.  #define IP_VS_RTAB_SIZE (1 << IP_VS_RTAB_BITS)
    6. 

  6.  #define IP_VS_RTAB_MASK (IP_VS_RTAB_SIZE - 1)
    7. 

  7.   
    8. 

  8.  static struct list_head ip_vs_rtable[IP_VS_RTAB_SIZE];

这个是存放rs信息的ip_vs_rtable[]

net/ipv4/ipvs/ip_vs_ctl.c
  1.  /*
    2. 

  2.   *    Returns hash value for real service
    3. 

  3.   */
    4. 

  4.  static __inline__ unsigned ip_vs_rs_hashkey(__be32 addr, __be16 port)
    5. 

  5.  {
    6. 

  6.      register unsigned porth = ntohs(port);
    7. 

  7.   
    8. 

  8.      return (ntohl(addr)^(porth>>IP_VS_RTAB_BITS)^porth)
    9. 

  9.          & IP_VS_RTAB_MASK;
    10. 

  10.  }

使用地址/端口来得到hashkey,ntohs()是将网络地址转化成短的本地地址,ntohl将网络地址转化成长的本地地址

在系统实现中，我们多处用到Hash表，如连接的查找和虚拟服务的查找。选择Hash表优先Tree等复杂数据结构的原因是Hash表的插入和删除的复杂度为O(1)，而Tree的复杂度为O(log(n))。Hash表的查找复杂度为O(n/m)，其中n为Hash表中对象的个数，m为Hash表的桶个数。当对象在Hash表中均匀分布和Hash表的桶个数与对象个数一样多时，Hash表的查找复杂度可以接近O(1)。

因为连接的Hash表要容纳几百万个并发连接，并且连接的Hash表是系统使用最频繁的部分，任何一个报文到达都需要查找连接Hash表，所以如何选择一个高效的连接Hash函数直接影响到系统的性能。连接Hash函数的选择要考虑到两个因素，一个是尽可能地降低Hash表的冲突率，另一个是Hash函数的计算不是很复杂。

一个连接有客户的<PROTOCOL,ADDRESS,PORT>、虚拟服务的<ADDRESS,PORT>和目标服务器的<ADDRESS,PORT>等元素，其中客户的<PROTOCOL,ADDRESS,PORT>是每个连接都不相同的，后两者在不同的连接经常重叠。所以，我们选择客户的<PROTOCOL,ADDRESS,PORT>来计算Hash Key。在IPVS版本中，我们用以下快速的移位异或Hash函数来计算。

#define IP_VS_TAB_BITS  CONFIG_IP _VS_TAB_BITS
#define IP_VS_TAB_SIZE  (1 << IP_VS_TAB_BITS)
#define IP_VS_TAB_MASK  (IP_VS_TAB_SIZE - 1)
inline unsigned ip_vs_hash_key(unsigned proto, unsigned addr, unsigned port)
{
    return (proto ^ addr ^ (addr>>IP_VS_TAB_BITS) ^ port) 
         & IP_VS_TAB_MASK;
}

为了评价Hash函数的效率，我们从一个运行IPVS的真实站点上取当前连接的样本，它一共含有35652个并发连接。在有64K桶的Hash表中，连接分布如下：

桶的长度（Lj）	该长度桶的个数（Nj）
5	              16
4	              126
3	              980
2	              5614
1	              20900

通过以下公式算出所有连接查找一次的代价：

所有连接查找一次的代价为45122，每个连接查找的平均代价为1.266（即45122/35652）。我们对素数乘法Hash函数进行分析，素数乘法Hash函数是通过乘以素数使得Hash键值达到较均匀的分布。

inline unsigned ip_vs_hash_key(unsigned proto, unsigned addr, unsigned port)
{
    return ((proto+addr+port)* 2654435761UL) & IP_VS_TAB_MASK;
}

其中，2654435761UL是2到2^32间黄金分割的素数，

2654435761 / 4294967296 = 0.618033987

在有64K桶的Hash表中，素数乘法Hash函数的总查找代价为45287。可见，现在IPVS中使用的移位异或Hash函数还比较高效。

在最新的Linux内核2.4和2.6中，连接的Hash函数是使用Jenkins函数。

参考文献

 
Done in 0.102523088455 seconds