神马文学网IP虚拟服务器的实现和性能测试(1)
来源：百度文库 编辑：神马文学网 时间：2024/05/15 20:43:11
系统实现的基本框架
我们分别在Linux 内核2.0和内核2.2中修改了TCP/IP协议栈，在IP层截取和改写/转发IP报文，实现了三种IP负载均衡技术，并提供了一个ipvsadm程序进 行虚拟服务器的配置和管理。在Linux 内核2.4和2.6中，我们把它实现为NetFilter的一个模块，很多代码作了改写和进一步优化，目前版本已在网上发布，根据反馈信息该版本已经较稳 定。
图5.1：系统的主要功能模块
系统的主要功能模块如图5.1所示，“VS Schedule & Control Module”是虚拟服务器的主控模块，它挂接在IP报文遍历的LOCAL_IN链和IP_FORWARD链两处，用于截取/改写IP报文；“VS Rules Table”用于存放虚拟服务器的规则，“Connections Hash Table”表是用于记录当前连接的Hash表；“Stale Connection Collector”模块用于回收已经过时的连接；“Statistics Data”表记录IPVS的统计信息。用户空间的ipvsadm管理程序通过setsockopt()函数将虚拟服务器的规则写入“VS Rules Table”表中，通过/proc文件系统把“VS Rules Table”表中的规则读出。
当一个IP报文到达时，若报文的目标地址是本地的IP地址，IP报文会转到LOCAL_IN链上，否则转到IP_FORWARD链上。IPVS模块 主要挂接在LOCAL_IN链和IP_FORWARD链两处。当一个目标地址为Virtual IP Address的报文到达时，该报文会被挂接在LOCAL_IN链上的IPVS程序捕获，若该报文属于在连接Hash表中一个已建立的连接，则根据连接的 信息将该报文发送到目标服务器，否则该报文为SYN时，根据连接调度算法从一组真实服务器中选出一台服务器，根据IP负载调度设置的规则将报文发送给选出 的服务器，并在连接Hash表中记录这个连接。挂接在IP_FORWARD链上的IPVS程序是改写VS/NAT中服务器响应报文的地址。
连接的Hash表可以容纳几百万个并发连接，在Linux内核2.2和内核2.4的IP虚拟服务器版本中每个连接只占用128Bytes有效内存， 例如一个有256M可用内存的调度器就可调度两百万个并发连接。连接Hash表的桶个数可以由用户根据实际应用来设定，来降低Hash的冲突率。
在每个连接的结构中有连接的报文发送方式、状态和超时等。报文发送方式有VS/NAT、VS/TUN、VS/DR和本地结点，报文会被以连接中设定 的方式发送到目标服务器。这意味着在一个服务器集群中，我们可以用不同的方式（VS/NAT、VS/TUN或VS/DR）来调度不同的服务器。连接的状态 和超时用于记录连接当前所在的状态，如SYN_REC、ESTABLISHED和FIN_WAIT等，不同的状态有不同的超时值。
系统实现的若干问题
本节讲述实现时所遇到的若干主要问题和它们的解决方法或者优化处理。Hash表
在系统实现中，我们多处用到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函数的计算不是很复杂。
一个连接有客户的
、虚拟服务的
和目标服务器的
等元素，其中客户的
是每个连接都不相同的，后两者在不同的连接经常重叠。所以，我们选择客户的
来计算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函数。
垃圾回收
为了将不再被使用的连接单元回收，我们在连接上设置一个定时器，当连接超时，将该连接回收。因为系统中有可能存在几百万个并发连接，若使用内核中的 定时器，几百万个连接单元系统的定时器的列表中，系统每隔1/100秒进行单元的迁移和回收已超时的连接单元，这会占用很多系统的开销。
因为连接的回收并不需要很精确，我们可以让系统的定时器每隔1秒启动连接回收程序来回收那些超时的连接。为此，我们设计了一个慢定时器，连接的定时 都是以1秒钟为单位。用三个时间大转盘，第一个转盘有1024个刻度，定时在1024秒钟之内的连接都挂接在第一个转盘的各个刻度上；第二个转盘有256 个刻度，定时在[210, 218)区间的落在第二个转盘上；第三个转盘有256个刻度，定时在[218, 226)区间的落在第三个转盘上。
慢定时器处理程序每隔1秒由系统定时器启动运行一次，将第一个转盘当前指针上的连接进行回收，再将指针顺时针转一格。若指针正好转了一圈，则对第二 个转盘当前指针上的连接进行操作，根据他们的定时迁移到第一个转盘上，再将指针顺时针转一格。若第二个转盘的指针正好转了一圈，则对第三个转盘当前指针上 的连接进行操作，根据他们的定时迁移到第二个转盘上。
使用这种慢定时器极大地提高了过期连接的回收问题。在最初的版本中，我们是直接使用系统的定时器进行超时连接的回收，但是当并发连接数增加到500,000时，系统的CPU使用率已接近饱和，所以我们重新设计了这种高效的垃圾回收机制。
ICMP处理
负载调度器需要实现虚拟服务的ICMP处理，这样进来的虚拟服务ICMP报文会被改写或者转发给正确的后端服务器，出去的ICMP报文也会被正确地改写和发送给客户。ICMP处理对于客户和服务器间的错误和控制通知是非常重要的。
ICMP消息可以发现在客户和服务器间的MTU（Maximum Transfer Unit）值。在客户的请求被VS/DR调度到一台服务器执行，服务器将执行结果直接返回给客户。例如响应报文的MTU为1500个字节，在服务器到客户 的路径中有一段线路的MTU值为512个字节，这时路由器会向报文的源地址（即虚拟服务的地址）发送一个需要分段为512个字节的ICMP消息。该 ICMP消息会到达调度器，调度器需要将ICMP消息中原报文的头取出，再在Hash表中找到相应的连接，然后将该ICMP消息转发给对应的服务器。这 样，服务器就会将原有的报文分段成512个字节进行发送，客户得到服务的响应。
可装卸的调度模块
为了提高系统的灵活性，我们将连接调度做成可装卸的模块（Loadable Modules），如ip_vs_rr.o、ip_vs_wrr.o、ip_vs_lc.o、ip_vs_wlc.o、ip_vs_lblc.o、 ip_vs_lblcr.o、ip_vs_dh.o、ip_vs_sh.o、ip_vs_sed.o和ip_vs_nq.o。当虚拟服务设置时，会将相应 的模块调到内核中。这样，有助于提高系统的使用效率，不装载不被使用的资源。锁的处理和优化
在系统中虚拟服务规则的读和写需要锁来保证处理的一致性。在连接的Hash表中，同样需要锁来保证连接加入和删除的一致性。连接的Hash表是系统使用最 频繁的资源，任何一个报文到达都需要查找连接Hash表。如果只有一个锁来管理连接Hash表的操作，锁的冲突率会很高。为此，我们引入有n个元素的锁数 组，每个锁分别控制1/n的连接Hash表，增加锁的粒度，降低锁的冲突率。在两个CPU的SMP机器上，假设CPU操作Hash表的部位是随机分布的， 则两个CPU同时操作同一区域的概率为1/n。在系统中n的缺省值为16。连接的相关性
到现在为止，我们假设每个连接都相互独立的，所以每个连接被分配到一个服务器，跟过去和现在的分配没有任何关系。但是，有时由于功能或者性能方面的原因，一些来自同一用户的不同连接必须被分配到同一台服务器上。
FTP是一个因为功能设计导致连接相关性的例子。在FTP使用中，客户需要建立一个控制连接与服务器交互命令，建立其他数据连接来传输大量的数据。 在主动的FTP模式下，客户通知FTP服务器它所监听的端口，服务器主动地建立到客户的数据连接，服务器的端口一般为20。IPVS调度器可以检查报文的 内容，可以获得客户通知FTP服务器它所监听的端口，然后在调度器的连接Hash表中建立一个相应的连接，这样服务器主动建立的连接可以经过调度器。但 是，在被动的FTP模式下，服务器告诉客户它所监听的数据端口，服务器被动地等待客户的连接。在VS/TUN或VS/DR下，IPVS调度器是在从客户到 服务器的半连接上，服务器将响应报文直接发给客户，IPVS调度器不可能获得服务器告诉客户它所监听的数据端口。
SSL（Secure Socket Layer）是一个因为性能方面原因导致连接相关性的例子。当一个SSL连接请求建立时，一个SSL的键值（SSL Key）必须要在服务器和客户进行选择和交换，然后数据的传送都要经过这个键值进行加密，来保证数据的安全性。因为客户和服务器协商和生成SSL Key是非常耗时的，所以SSL协议在SSL Key的生命周期内，以后的连接可以用这个SSL Key和服务器交换数据。如果IPVS调度器将以后的连接调度到其他服务器，这会导致连接的失败。
我们现在解决连接相关性的方法是持久服务（Persistent Service）的处理。使用两个模板来表示客户和服务器之间的持久服务，模板〈protocol, client_ip, 0, virtual_ip, virtual_port, dest_ip, dest_port〉表示来自同一客户client_ip到虚拟服务〈virtual_ip, virtual_port〉的任何连接都会被转发到目标服务器〈dest_ip, dest_port〉，模板〈protocol, client_ip, 0, virtual_ip, 0 dest_ip, 0〉表示来自同一客户client_ip到虚拟服务器virtual_ip的任何连接都会被转发到目标服务器dest_ip，前者用于单一的持久服务，后 者用于所有端口的持久服务。当一个客户访问一个持久服务时，IPVS调度器会在连接Hash表中建立一个模板，这个模板会在一个可设置的时间内过期，如果 模板有所控制的连接没有过期，则这个模板不会过期。在这个模板没有过期前，所有来自这个客户到相应服务的任何连接会被发送到同一台服务器。
持久服务还可设置持久的粒度，即可设置将来自一个C类地址范围的所有客户请求发送到同一台服务器。这个特征可以保证当使用多个代理服务器的客户访问集群时，所有的连接会被发送到同一服务器。
虽然持久服务可能会导致服务器间轻微的负载不平衡，因为持久服务的一般调度粒度是基于每个客户机的，但是这有效地解决连接相关性问题，如FTP、SSL和HTTP Cookie等。