HTTP服务器之嵌入式负载平衡路由器实战(3)

转送资讯表

　　当远端的客户端发出http要求至Web Switch时，Web Switch先决定该把这个封包丢给后端的哪台机器做处理，然后记下封包来源端的IP、port与即将送往目标的IP与port。在同一个要求里，来源为相同IP与port的封包再度来临时，则根据先前已建立在传送资料表里的资讯，决定该封包将丢给哪一台机器；同样的，当后端的机器将资讯处理完准备丢还给客户端时，也要查询传送资料表，以得知这个封包的来源为何实际上在实作时，我们用二种资料结构来做，取其中较好的结果做为最后采用的实作方式：

　　用阵列来实作 传送资料表：每当有一个封包进来，就先在传送资料表组成的阵列中循序地寻找是否有这个连线的资料(IP, port)，若没能找到对应的资料，则循序地寻找空的栏位纪录此连线。这个方法的优点是容易实作，而且做循序搜寻所需的负担并不高，但缺点是循序搜寻所需的时间复杂度是O(n)，当连线的数目愈来愈多时，搜寻表格可能会成为演算法的瓶颈。

　　用主二元树(main-binary tree)与次二元树(sub-binary tree)来实作 传送资料表：在主二元树内纪录连线的IP资讯(如图九)，且每个主二元树的节点(tree node)上还有一个次二元树用以纪录同一个IP但不同port的连线。每当有一个连线进来时，先在主二元树中寻找有没有相对应的IP：若连线IP大于目前寻找节点的IP，则往该节点右边的子节点(right child)找，反之往左边的子节点(left child)，若相等时，则进入该节点的次二元树，寻找是否有相同的port。若找到相同的port，则代表该连线先前已建立，反之则代表该连线不存在，而我们必须建立一个新节点来纪录此连线。这个方法在新增或移除连线时的负担都比前一个方式高，但搜寻所需的时间复杂度只须要O(logK．log(N-K))，K为目前的连线中不同IP的数目，N为总连线数目。当连线数目较高时，此方式将比前一个方式要有效率。

负载资讯表

　　负载资讯表(Load Table)最主要的工作是纪录后方伺服器的负载资讯，在Web Switch执行的过程中，负载资讯表会依照各种不同演算法的需求去更新后端伺服器的资讯。Web Switch在收到客户端http的要求后会执行负载平衡演算法，依照当时负载资讯表所纪录的资讯来决定此http要求应该交给后方的哪台Web Node处理。

　　负载资讯表的实作采阵列方式。选择阵列方式的原因是Web Switch 上的WAN端只有四个连接埠，意即后方的伺服器最多为四台，在此情况下用阵列实作最为简单且有效率。负载资讯表栏位如下。

栏位　　　　　　　　　　　　　　说明
response_t　　　　　　封包回应时间(response time)
numconnect　　　　　　该伺服器目前连线数目(number of connection)
up_b　　　　　　　　　区域表上限 注.用法见区域表
low_b　　　　　　　　　区域表下限 注.用法见区域表
p　　　　　　　　　　　递移机率 注.用法见区域表

负载平衡演算法

　　负载平衡演算法在Web Switch中扮演重要角色，其主要责任为分配客户端http要求至后端伺服器并确保其负载相近。以下列出三种负载平衡演算法

　　connect_few()：函式connect_few会在Web Switch接受客户端新的连线后，找出当时后端伺服器中连线数最少的一台，由此Web Node来负责该连线。

　　rp_fast()：函式rp_fast负责找出后端哪台伺服器回应速度最快。除了在客户端有要求来时需要rp_fast来决定处理要求的伺服器，此演算法还需要send_probe和check_probe两个函式。send_probe负责定期对后端伺服器送出测试的封包。check_probe负责检验伺服器传回的封包并更新负载资讯表中每台伺服器的回应时间(回应速度)。

　　domain_load()：函式domain_load会依据负载资讯表中每台伺服器所负责的区域上限和区域下限来分配http要求，详细说明见区域表。

区域表

　　区域表(Domain Table)专门负责提供负载资讯表中计算区域上限、区域下限和递移机率的资讯。简单的说，区域表会收集过去K笔要求分别来自哪个网域，经过计算后会给定每台伺服器负责的网域范围，让每台伺服器处理的封包总数趋近相同，以达到负载平衡的目的。

　　以图九为例子，分配约略相等的红色(左半)面积和蓝色(右半)面积(面积代表封包总数)，在红蓝交错的区域中会利用递移机率(server1.p)来决定来自此范围网域的要求应该给server1或是给server2。此区域表每K笔要求会更新一次，并同时更新负载资讯表中各伺服器所负责的区域上限与区域下限和递移机率。

四．实验结果

　　图十是我们的实验环境，在WAN端的是一台计算能力较弱的机器上面执行Specweb99来作为封包产生器。Specweb99是一个非常有名的http伺服器benchmark，这个程式会fork出一堆行程(Process)来对http伺服器狂送要求，并且有一个管理者的程式会比对从伺服器得回来的结果是否正确，并且计算一些统计数字，像是每秒完成的要求数目(ops/s)、平均每秒接收到的正确资料大小、总共完成的要求数目...等等。Specweb99不只是可以送出静态的html网页要求，也可以送出cgi程式或是php程式的动态要求。通常静态网页考验的是系统的I/O而动态网页则是需要大量的CPU计算。

　　后端的Web Node执行Apache 1.3.27及php 4。我们的实验假设后端Web Node的资料是完全相同的，所以在后端四台Web Server里有相同的档案集合。

　　首先我们套用第一个演算法：由连线数目最少的Web Node来处理目前的要求。我们首先测试此演算法的延展性(Scalability)，由图十一可以看到当后端的Web Node数目增加时，系统的Throughput也会随之有线性的上升，表示这个演算法有不错的延展性。

　　再来看看以回应时间最短的Web Node来处理目前的要求的效能。大致上也呈现不错的延展性。但是因为要计算后端每一台Web Node的回应时间，造成PowerNet-AP的负担较大，所以能负担的连线数目较上一个演算法少一点，导致Throughput在较小的连线数目时便已经开始下滑。