论文部分内容阅读
摘 要:Web站点调度机制在保留Web服务器状态和必须能够线速处理大量的Web访问请求,这就要求Web调度机制简单和高性能。Web请求调度机制是Web访问请求处理流程中的重要环节,其实现效率是影响Web站点性能的重要因素。本文对Web请求调度技术进行研究,提出将Bloom Filter 应用于Web请求调度机制中,并对这种方法进行了深入分析,重点介绍应用Bloom Filter表示访问请求与目标服务器映射表,简化了Web服务器代理的实现,提高了Web代理的效率。
关键词:Web访问调度 Bloom Filter算法
中图分类号:TP393.08文献标识码:A文章编号:1672-8882(2011)07-082-02
一、Bloom Filter基本原理
Bloom Filter[1]是一种基于硬件的支持高速的网络安全的实现方法,采用的是多种hash共同作用的机制。它自1970 年提出以来,已经被广泛应用到各个领域,包括路由查找、串匹配、数据包的分类以及流状态信息的管理等。
Bloom Filter 的基本工作原理:Bloom Filter 支持三种操作模式,分别可以对数据进行插入、查找和删除。实现上述操作采用的是多hash 机制和一个固定长度的特征串,结构框架图如下所示[2]:
在插入阶段,对于给定的包含n个数据的数据集合,需要将其中的每个元素通过q个hash函数进行计算,得到q个大小介于1 和m 之间的数值,对应特征串中的q个比特位。若该位为0,则将其置1;若该位已被之前的元素置1,保持不变。以此为例将n 个数据都经过hash 函数的计算对应到特征串中。对于查找操作,与插入的过程基本相同。首先把输入的需要查询的数据经过hash函数的计算,得出q个索引值,如果特征串中对应位的值均为1,则表示输入的数据可能是数据集合中的成员。如果至少有一个值为0,则输入的数据肯定不在数据集合中。
删除操作比较简单。只需将q个索引值对应的特征串的值置0即可。
Hash 函数是一种常见的表示数据的方法,每个数据元素经过hash计算得到一定宽度的hash值,该值就代表了该数据元素。这种方法发生错误的概率很小。
Bloom Filter可以被看作是hash函数的一般化集合,它可以在每个数据元素平均占有的比特位和假阳性发生的概率之间寻找更好的平衡点。当一个Bloom Filter只拥有一个hash函数时,就相当于一个普通的hash计算。如果每个数据元素平均占有的比特数一定,那么Bloom Filter的假阳性的概率也是固定的。例如当m=8n时,假阳性概率仅仅高于0.02。在实际应用中,假阳性的概率大小是很值得研究和关注的。Bloom Filter中多hash 机制的运用在很大程度上解决了大容量数据集合的表示和查询问题,但是在使用过程中可以发现hash冲突是无法避免和消除的。目前对于hash冲突的有效解决方法主要从以下两个方面进行考虑:
首先选择随机性好的hash函数可以降低冲突率。另外hash表的合理组织和构建也能高效的处理hash冲突。Hash值的随机性是选取hash函数的主要依据。根据已有的hash算法归类可以分为两类:一种是直接使用报文中的标识字段,这种方法效率高,但是难以确保足够的hash值随机性;另一种方法是使用hash函数来生成hash值。Hash函数的选择是保证hash 值随机性和算法高效性的关键因素[57]。
目前大量研究工作是关注于提高hash查找性能的理论研究。有的提出使用两个不同的hash函数,然后选择拥有索引值最少的,这样就可以有效地减少冲突和探测序列长度;有的理论研究的是利用两个独立的hash 查找表实现连续的存取,不难发现适当的存放位置和存取策略将可以提高整体的性能。并行的hash同样在考虑的范围内。换句话说就是利用多个并行的索引值来降低冲突的次数和查找时间。如果硬件环境能够允许hash函数的并行计算和对不同存储块的读操作以实现查找能在一个存储周期内完成,那么应用多个hash函数来提高运算的性能被认为是一种理想的解决方案。
二、Web访问调度机制现面临的问题
多Web服务器并行处理模式中核心单元是Web服务器代理,Web服务器代理作为Web站点的接入点,接收大量的访问请求,并将它们合理的调度到后台服务器进行处理。Web访问请求调度机制是Web服务器代理的关键技术,决定了Web服务器代理的性能。Web服务器代理中调度机制的研究具有重要的意义,也面临很大的问题。
1.可扩展的调度机制是Web服务器代理应用的前提
在采用多服务器并行处理模式的Web站点中,通过不断地向服务池中增加高性能服务器来增强Web站点的性能,这就要求前台Web服务器代理能够感知后台服务器数量和状态的变化和客户访问数量的增加。在调度机制设计中就要考虑不同规模的访问请求和目标服务器,要能够适应不同的Web站点结构和流量特性,具有良好的扩展性。
2.线速处理是调度机制的基本要求
随着因特网技术和Web服务的发展,Web流量继续以指数增长, 造成网络带宽严重不足, 网络用户正面临着WWW访问速度慢、服务器负载重和网络阻塞等问题。在引入Web服务器代理后,增加了代理对报文的处理,也将增加Web站点处理报文的延迟。为了不影响Web站点处理,Web站点代理必须能够线速处理到达的请求报文,对他们进行分类,调度到合适的后台服务器。调度机制线速处理才能应对大量客户的访问,防止ddos 攻击等。同时,调度机制能够线速处理,并满足Web站点带宽要求,才能够保证Web服务器代理不会成为Web站点新的性能瓶颈。
3.保证后台服务器负载的均衡是调度机制的主要目标
后会使反向代理服务器成为服务的瓶颈。因此 已有的调度机制中前端的分配器作为到达请求的代理,负责集中地接收所有到达的HTTP请求,并且按照特定的负载均衡策略将客户的请求均衡的分配给急群中的后端服务器。不能做到为性能较好的服务器多分配请求,也不能了解到服务器的当前状态,甚至会出现客户请求集中在某一台服务器上的偶然情况。因此如何保证客户访问请求均衡地映射到若干后台服务器进行处理,是Web访问请求调度机制设计的主要目标。
三、Bloom Filter算法的优势
基于Bloom Filter的高效调度机制算法可以通过以下几种常用报文算法进行比较得出其高效化[3][4]:
下面将从时间复杂度、空间复杂度和更新复杂度三个方面对基于Bloom Filter的高效调度机制算法分析。
（1）时间复杂度
该指标用于定义执行分类所需要的步骤或循环的数目的最大边界,用于确定找到匹配结果所需要的顺序的步骤数。
（2）空间复杂度
该指标用于定义Web请求调度所需要保存分类器及其相关数据结构所需要的空间的最大边界。
（3）更新复杂度
该指标用于定义对分类器进行原子的插入、删除或更新所需要的步骤或循环数目的最大边界。为了便于与其他算法的比较,在此重新设置基于Bloom Filter的高效调度机制的算法中Bloom Filter映射规则个数为m,hash 函数个数为q,分派向量深度为n,宽度为w。从算法的描述中可以看到得到匹配结果主要经过hash计算、访问分派向量和动态链表三个部分组成。在理想的情况下,算法中的hash函数基于硬件实现,分派向量通过片内存储器存放,那么hash 计算和分派向量的访问均可在单个时钟周期内完成,对于动态链表的访问取决于其长度,在此等于计数器的数值。针对m个元素,共需要向分派向量产生mq 次映射。在hash key 均匀分布的前提下,每个计数器数值为mq/n,所以该算法的时间复杂度为O（2+mq/n）。基于Bloom Filter的高效调度机制算法的空间应用主要包括分派向量和动态链表两个方面,分派向量的空间大小与其深度m和宽度w有关,动态链表的大小与映射规则数m和q有关,所以其空间复杂度为O（mq+nw）。更新复杂度主要考虑到基于Bloom Filter 的负载均衡算法中映射规则添加和删除时所需要的步骤或循环数目的最大边界,根据基于Bloom Filter 的负载均衡算法的描述可以发现与查询时的时间复杂度情形基本相同。表1-1分别列出了基于Bloom Filter的高效调度机制算法与其他算法的各种复杂度,其中m代表映射规则数,h代表映射规则的维数,q 表示hash 函数的个数,n表示分派向量的深度,w表示分派向量的宽度,W表示映射规则的宽度。
表1-1
基于Bloom Filter的高效调度机制算法实现的重点分别为计数型Bloom Filter 和动态链表,两个部分均可利用硬件实现,方便简单,尤其对于片内存储器的合理利用将使得映射规则的查询快速,同时存储空间的利用率也相应的提高。由于Bloom Filter所支持查询的映射规则数n与映射规则查询的功耗的无关,所以基于Bloom Filter的高效调度机制算法可以支持大映射规则集合的查询。除了映射规则数n可以增大,不是限定在固定的数目以外,根据Bloom Filter采取多hash机制计算的特点,被查询映射规则的维数也可以变化,并非限定在固定的某几个字段上。最后该算法所支持的分类可包含多个层次,包括网络层、传输层等层次的字段。所以从总体而言基于Bloom Filter的高效调度机制算法具有很好的扩展性。
上面的内容从性能的角度将基于Bloom Filter的高效调度机制算法与其它几种算法作了比较,从结果可以看到基于Bloom Filter的高效调度机制算法的时间、空间和更新复杂度分别与参数m、n、q、w 有关。通过与其它算法的比较,可以发现基于Bloom Filter的高效调度机制算法在性能上具有优势。
对于Web请求调度算法而言,一般期望时间复杂度、空间复杂度和更新复杂度越小越好,并具有良好的可扩展性,不仅平均性能好,而且在最坏情况下的性能也良好。但在许多情况下,Web请求调度算法无法满足全部指标达到最优,而是要根据算法的使用场合加以折衷。
本章主要提出了基于Bloom Filter表示的高效调度机制,主要介绍了算法的基本思想、算法的具体描述以及与其它算法的性能比较,通过比较可以看到基于Bloom Filter表示的高效调度机制算法充分发挥和利用了Bloom Filter的优点,保证了Web请求调度的在Web访问请求处理过程中的高效性。
参考文献:
[1] B. Kruatrachue, T. G. Lewis. Grain Size Determination for Parallel Processing. IEEE Software, 1988, 5(1): 23~32.
[2] Andrei Broder, Michael Mitzenmacher, “Network Applications of Bloom Filters: A Survey”, Internet Mathematics Vol. 1, No. 4: pp.485-509.
[3]田立勤,林闯,报文分类技术的研究及其应用[J]计算机研究与发展,2003,Vol.40, No.6.
[4]尚凤军,潘英俊,基于XOR Hash 的快速IP 数据包分类算法研究[J] 计算机工程与应用.2005.
关键词:Web访问调度 Bloom Filter算法
中图分类号:TP393.08文献标识码:A文章编号:1672-8882(2011)07-082-02
一、Bloom Filter基本原理
Bloom Filter[1]是一种基于硬件的支持高速的网络安全的实现方法,采用的是多种hash共同作用的机制。它自1970 年提出以来,已经被广泛应用到各个领域,包括路由查找、串匹配、数据包的分类以及流状态信息的管理等。
Bloom Filter 的基本工作原理:Bloom Filter 支持三种操作模式,分别可以对数据进行插入、查找和删除。实现上述操作采用的是多hash 机制和一个固定长度的特征串,结构框架图如下所示[2]:
在插入阶段,对于给定的包含n个数据的数据集合,需要将其中的每个元素通过q个hash函数进行计算,得到q个大小介于1 和m 之间的数值,对应特征串中的q个比特位。若该位为0,则将其置1;若该位已被之前的元素置1,保持不变。以此为例将n 个数据都经过hash 函数的计算对应到特征串中。对于查找操作,与插入的过程基本相同。首先把输入的需要查询的数据经过hash函数的计算,得出q个索引值,如果特征串中对应位的值均为1,则表示输入的数据可能是数据集合中的成员。如果至少有一个值为0,则输入的数据肯定不在数据集合中。
删除操作比较简单。只需将q个索引值对应的特征串的值置0即可。
Hash 函数是一种常见的表示数据的方法,每个数据元素经过hash计算得到一定宽度的hash值,该值就代表了该数据元素。这种方法发生错误的概率很小。
Bloom Filter可以被看作是hash函数的一般化集合,它可以在每个数据元素平均占有的比特位和假阳性发生的概率之间寻找更好的平衡点。当一个Bloom Filter只拥有一个hash函数时,就相当于一个普通的hash计算。如果每个数据元素平均占有的比特数一定,那么Bloom Filter的假阳性的概率也是固定的。例如当m=8n时,假阳性概率仅仅高于0.02。在实际应用中,假阳性的概率大小是很值得研究和关注的。Bloom Filter中多hash 机制的运用在很大程度上解决了大容量数据集合的表示和查询问题,但是在使用过程中可以发现hash冲突是无法避免和消除的。目前对于hash冲突的有效解决方法主要从以下两个方面进行考虑:
首先选择随机性好的hash函数可以降低冲突率。另外hash表的合理组织和构建也能高效的处理hash冲突。Hash值的随机性是选取hash函数的主要依据。根据已有的hash算法归类可以分为两类:一种是直接使用报文中的标识字段,这种方法效率高,但是难以确保足够的hash值随机性;另一种方法是使用hash函数来生成hash值。Hash函数的选择是保证hash 值随机性和算法高效性的关键因素[57]。
目前大量研究工作是关注于提高hash查找性能的理论研究。有的提出使用两个不同的hash函数,然后选择拥有索引值最少的,这样就可以有效地减少冲突和探测序列长度;有的理论研究的是利用两个独立的hash 查找表实现连续的存取,不难发现适当的存放位置和存取策略将可以提高整体的性能。并行的hash同样在考虑的范围内。换句话说就是利用多个并行的索引值来降低冲突的次数和查找时间。如果硬件环境能够允许hash函数的并行计算和对不同存储块的读操作以实现查找能在一个存储周期内完成,那么应用多个hash函数来提高运算的性能被认为是一种理想的解决方案。
二、Web访问调度机制现面临的问题
多Web服务器并行处理模式中核心单元是Web服务器代理,Web服务器代理作为Web站点的接入点,接收大量的访问请求,并将它们合理的调度到后台服务器进行处理。Web访问请求调度机制是Web服务器代理的关键技术,决定了Web服务器代理的性能。Web服务器代理中调度机制的研究具有重要的意义,也面临很大的问题。
1.可扩展的调度机制是Web服务器代理应用的前提
在采用多服务器并行处理模式的Web站点中,通过不断地向服务池中增加高性能服务器来增强Web站点的性能,这就要求前台Web服务器代理能够感知后台服务器数量和状态的变化和客户访问数量的增加。在调度机制设计中就要考虑不同规模的访问请求和目标服务器,要能够适应不同的Web站点结构和流量特性,具有良好的扩展性。
2.线速处理是调度机制的基本要求
随着因特网技术和Web服务的发展,Web流量继续以指数增长, 造成网络带宽严重不足, 网络用户正面临着WWW访问速度慢、服务器负载重和网络阻塞等问题。在引入Web服务器代理后,增加了代理对报文的处理,也将增加Web站点处理报文的延迟。为了不影响Web站点处理,Web站点代理必须能够线速处理到达的请求报文,对他们进行分类,调度到合适的后台服务器。调度机制线速处理才能应对大量客户的访问,防止ddos 攻击等。同时,调度机制能够线速处理,并满足Web站点带宽要求,才能够保证Web服务器代理不会成为Web站点新的性能瓶颈。
3.保证后台服务器负载的均衡是调度机制的主要目标
后会使反向代理服务器成为服务的瓶颈。因此 已有的调度机制中前端的分配器作为到达请求的代理,负责集中地接收所有到达的HTTP请求,并且按照特定的负载均衡策略将客户的请求均衡的分配给急群中的后端服务器。不能做到为性能较好的服务器多分配请求,也不能了解到服务器的当前状态,甚至会出现客户请求集中在某一台服务器上的偶然情况。因此如何保证客户访问请求均衡地映射到若干后台服务器进行处理,是Web访问请求调度机制设计的主要目标。
三、Bloom Filter算法的优势
基于Bloom Filter的高效调度机制算法可以通过以下几种常用报文算法进行比较得出其高效化[3][4]:
下面将从时间复杂度、空间复杂度和更新复杂度三个方面对基于Bloom Filter的高效调度机制算法分析。
（1）时间复杂度
该指标用于定义执行分类所需要的步骤或循环的数目的最大边界,用于确定找到匹配结果所需要的顺序的步骤数。
（2）空间复杂度
该指标用于定义Web请求调度所需要保存分类器及其相关数据结构所需要的空间的最大边界。
（3）更新复杂度
该指标用于定义对分类器进行原子的插入、删除或更新所需要的步骤或循环数目的最大边界。为了便于与其他算法的比较,在此重新设置基于Bloom Filter的高效调度机制的算法中Bloom Filter映射规则个数为m,hash 函数个数为q,分派向量深度为n,宽度为w。从算法的描述中可以看到得到匹配结果主要经过hash计算、访问分派向量和动态链表三个部分组成。在理想的情况下,算法中的hash函数基于硬件实现,分派向量通过片内存储器存放,那么hash 计算和分派向量的访问均可在单个时钟周期内完成,对于动态链表的访问取决于其长度,在此等于计数器的数值。针对m个元素,共需要向分派向量产生mq 次映射。在hash key 均匀分布的前提下,每个计数器数值为mq/n,所以该算法的时间复杂度为O（2+mq/n）。基于Bloom Filter的高效调度机制算法的空间应用主要包括分派向量和动态链表两个方面,分派向量的空间大小与其深度m和宽度w有关,动态链表的大小与映射规则数m和q有关,所以其空间复杂度为O（mq+nw）。更新复杂度主要考虑到基于Bloom Filter 的负载均衡算法中映射规则添加和删除时所需要的步骤或循环数目的最大边界,根据基于Bloom Filter 的负载均衡算法的描述可以发现与查询时的时间复杂度情形基本相同。表1-1分别列出了基于Bloom Filter的高效调度机制算法与其他算法的各种复杂度,其中m代表映射规则数,h代表映射规则的维数,q 表示hash 函数的个数,n表示分派向量的深度,w表示分派向量的宽度,W表示映射规则的宽度。
表1-1
基于Bloom Filter的高效调度机制算法实现的重点分别为计数型Bloom Filter 和动态链表,两个部分均可利用硬件实现,方便简单,尤其对于片内存储器的合理利用将使得映射规则的查询快速,同时存储空间的利用率也相应的提高。由于Bloom Filter所支持查询的映射规则数n与映射规则查询的功耗的无关,所以基于Bloom Filter的高效调度机制算法可以支持大映射规则集合的查询。除了映射规则数n可以增大,不是限定在固定的数目以外,根据Bloom Filter采取多hash机制计算的特点,被查询映射规则的维数也可以变化,并非限定在固定的某几个字段上。最后该算法所支持的分类可包含多个层次,包括网络层、传输层等层次的字段。所以从总体而言基于Bloom Filter的高效调度机制算法具有很好的扩展性。
上面的内容从性能的角度将基于Bloom Filter的高效调度机制算法与其它几种算法作了比较,从结果可以看到基于Bloom Filter的高效调度机制算法的时间、空间和更新复杂度分别与参数m、n、q、w 有关。通过与其它算法的比较,可以发现基于Bloom Filter的高效调度机制算法在性能上具有优势。
对于Web请求调度算法而言,一般期望时间复杂度、空间复杂度和更新复杂度越小越好,并具有良好的可扩展性,不仅平均性能好,而且在最坏情况下的性能也良好。但在许多情况下,Web请求调度算法无法满足全部指标达到最优,而是要根据算法的使用场合加以折衷。
本章主要提出了基于Bloom Filter表示的高效调度机制,主要介绍了算法的基本思想、算法的具体描述以及与其它算法的性能比较,通过比较可以看到基于Bloom Filter表示的高效调度机制算法充分发挥和利用了Bloom Filter的优点,保证了Web请求调度的在Web访问请求处理过程中的高效性。
参考文献:
[1] B. Kruatrachue, T. G. Lewis. Grain Size Determination for Parallel Processing. IEEE Software, 1988, 5(1): 23~32.
[2] Andrei Broder, Michael Mitzenmacher, “Network Applications of Bloom Filters: A Survey”, Internet Mathematics Vol. 1, No. 4: pp.485-509.
[3]田立勤,林闯,报文分类技术的研究及其应用[J]计算机研究与发展,2003,Vol.40, No.6.
[4]尚凤军,潘英俊,基于XOR Hash 的快速IP 数据包分类算法研究[J] 计算机工程与应用.2005.