PageRank在OA系统中的应用
2017-10-26潘仙张郭文平应国良
潘仙张 郭文平 应国良
摘要：改进了OA系统缓存替换算法。本文针对OA系统的http动态请求进行PageRank建模，极大提高了系统的响应速度。解决了超大量并发用户的动态请求响应瓶颈。本文的OA缓存替换算法依据每个用户连接的行为特征预测它下次请求的最大可能，并把用户下次可能操作所需的数据提前存储在内存中以求最大的响应性能，本文的OA性能超过了目前已有的OA。
关键词：缓存替换算法；OA系统；WEB服务性能优化；代理服务器
中图分类号：TP393.07文献标识码：A
Abstract：improving the cache replacement algorithm of OA.In this paper，using PageRank to model dynamic http request of OA，it greatly improves the systems response speed.Solving the problem of super large number of dynamic request.The cache replacement algorithm of OA is based on the behavior characteristics of each user connections to predict the next maximum possible request of the user，and the next time possible required data will be stored in memory in order to perform the maximum response performance.This paper performance is over the existing OA system.
Key words：cache replacement algorithm；OA system；WEB server performance optimization；proxy server
0引言
521031568web服务的主要功能是提供网上信息浏览服务[1-2]。学校的办公系统（OA）是基于web服务的开发方式。OA系统对服务器硬件和网络设备硬件资源的要求极其高，当数据处理功能复杂之后，把功能处理和网页表示层处理合为一体的方式已经不适合越来越复杂的MIS系统了，目前OA的研发过程中会把一些通用MIS系统的功能模块独立出来建立一个通用单独系统，比如事务处理、数据库连接、应用系统的安全性连接。这样OA系统就可以在这些中间件系统的基础上搭建自己的功能而不需要自己从头做起。为了使OA系统在上线后能使用户获得最大的使用体验，在OA系统的Web服务器前面搭建一个缓存服务器，它专门负责处理和用户浏览器之间的数据交换。
521031569学校的每年预算是非常有限的，因此，在有限的带宽和服务器资源的情况下，即在不增加额外硬件开销的情况下，非常需要通过缓存服务器的应用，提高OA系统的用户响应速度。缓存服务器采用的缓存软件一般有squid、Redis、Ngnix。目前流行的OA系统缓存服务采用squid方式。本文针对OA系统，只研究了和基于squid缓存服务器的区别。因squid、Redis、Ngnix [17]采用的LRU、LFU和FIFO算法对动态请求数据缓存效果并不是很好。本文针对高校OA数据请求特点，进行缓存替换算法研究，以此提高OA系统对用户的响应速度，提升用户对OA的体验。
OA 具有非常多文档、非常复杂的链接，但是用户使用web页面的内容具有很大的正态分布，从大数据的角度，OA系统的数据访问具有一定的规律性，符合hmm过程，很适合用PageRank建模。OA采用B/S结构，它整理和储存高校用户行政办公资源，服务器对用户的请求作出及时的响应 [1-2]。在UNIX和LINUX下使用apache、weblogic作为web服务器，而在Windows下使用IIS作为web服务器。在选择web服务器时考虑的因素有：性能、安全性、日志和统计、缓冲服务和集成应用程序等。目前OA系统普遍采用图1[1-2，6]，用户在浏览器通过http协议先请求缓存服务器，如果缓存服务器中存在请求的数据，则直接应答http请求，而不再转发http请求到web服务器，如果缓存服务器中没有所请求的数据，则直接把http请求转到web服务器。这种web服务架构的缺点是缓存服务器对所请求的静态数据命中率很高，而对动态数据却表现的并不很好，而OA的http请求好多是动态信息。图1中的缓存服务器是基于squid的服务器 ，squid是一种用来缓存Internet数据软件，它接受来自用户需要的目标请求并适当地处理这些请求后，squid会把用户请求的数据响应到客户端机器。Squid很适合静态数据缓存，当动态数据比较多时，squid的缓存就显得存储量大，缓存的命中率低。在图1的OA系统中，所有的服务器采用DL580 G9，web服務器采用weblogic11g，数据库采用oracle11g，当同时在线人数超过6500的时候，响应速度就很慢了，用户的体验就很差了。基于PageRank的缓存服务器（缓存服务器中的缓存替换算法采用PageRank）能解决这个问题，而不增加额外的硬件投资。
1相关研究
2005年上海交大刘宝锋在论文中提出采用缓存的办法来提高视频点播的性能[11]。周洲仪等在2010设计并实现了高速安全反向代理服务器 [8].他们用实验证明了用代理服务的缓存分担系统响应压力的可行性。陈兵等实现了哈希链表和时间链表的HTTP代理缓存机制[12]，在有限的带宽和服务器资源的情况下，极大的加快了用户的浏览速度。Squid的缓存替换机制主要有两类，它们分别是基于堆替换缓存机制和基于双向链表的缓存替换机制[16]。 陈爱林等把代理服务器应用在了智能变电站和调度主站无缝通信中[9]取得了极好的用户使用体验。廖建新、杨波采用了基于网络代价的流媒体缓存策略，该算法有效提高了缓存命中率，降低了传送流媒体所消耗的总体网络代价，特别适合在网络结构复杂、节目数量庞大的Internet流媒体。Xiaoming Jiang和Jingqiao Shi在2016年实现了以最低的web服务器资源消耗为代价的稳定的代理服务器[10]。P Cao，S Irani提出在代理服务器中采用GreedyDualSize算法替换缓存的策略，该策略应用在web系统大大减少了网络的拥堵和系统的响应时间[15]。目前已有的缓存替换算法主要有如下几种[17]：（1）Least-Recent-Used（LRU）算法，即缓存中只存在最近使用的数据。（2）Least-Freqquently-Used（LFU），即缓存中只存储最频繁使用的数据。（3）FIFO，先进先出算法，即一个数据最先进入缓存，则会最早被淘汰。针对OA系统的动态情况，以上算法都欠考虑了用户操作页面的互链接存在环的情况，以及动态http请求数据的不稳定，存在异方差。国内外学者很早就考虑到采用缓存来提升服务的性能，从理论到实践积累了丰富的经验，这些都为本文的工程实践带来了宝贵的参考价值。本文把PageRank做为缓存替换算法并应用到OA系统中，在本校OA系统产生的历史访问数据做为数据集，并在此数据集上对LRU、LFU、Size、PageRank的缓存命中率进行了比较（见表1）。表1的实验环境如下：图1和图2的所有服务器采用DL580 G9，web服务器采用weblogic11g，数据库采用oracle11g，图1和图2除了缓存服务器上的算法不同，其他软硬件配置都相同，其中LRU、LFU、Size算法在图1的缓存服务器上使用，PageRank在图2的缓存服务器上使用。
学校OA系统的每个用户就是高校中教职工的某个岗位，每个岗位具有固定的职责，每个职责在近几年中的变化特别的少，并且每个岗位每天工作的重复性很大，以及在时间序列上有很大的相关性，这些特性是PageRank在OA上应用成功的基础。PageRank算法能找出每个用户在使用OA中的数据的时间序列的相关性，预测用户在接下来的操作中最有可能的行为，并把最有可能供以后访问所使用的数据通过cache存储起来。极大提高了OA系统的用户响应性能。基于PageRank的OA系统（见图2）能支持同时在线人数6500人，极大地改善了目前已有的OA系统响应能力。在图2中，基于PageRank缓存服务器就是缓存服务器采用PageRank算法。
在图2中，用户在浏览器通过http协议先请求基于PageRank缓存服务器，它依据每个用户的id记录出每个用户的行为请求数据，当用户的行为数据积累到一定程度，用户的行为就会呈现明显的正态分布特性，它就会预测用户的下次请求最大的几个可能的内容，并提前预取这些可能数据，并存入缓存服务器中。当用户下次的数据在缓存服务器中时，则它直接响应用户的http请求，反之把该用户的http请求转到web服务器，web服务器接收到所需的动态数据，并组织成html返回给客户端浏览器，浏览器解析web服务器的结果，并显示给客户。
21基于PageRank建模
PageRank表示网页排名算法[17]， 通过PageRank计算每一个网页的PageRank值，然后根据这个值的大小对网页的重要性进行排序。它的思想是模拟一个悠闲的上网者，上网者首先随机选择一个网页打开，然后在这个网页上呆了几分钟后，跳转到该网页所指向的链接，这样无所事事、漫无目的地在网页上跳来跳去，PageRank就是估计这个悠闲的上网者分布在各个网页上的概率。本文用PageRank估计每个用户在OA系统上的行为在各个功能模块上的概率。并在PageRank缓存服务器中预存用户下次最大的几个可能的数据。高校OA系统的主要功能模块如表2。OA系统的高效、稳定运行关乎到每个用户的日常正常工作，关系到高校的日常办公正常运转。
定理1：（贝努力大数定律）在独立随机试验中，当实验次数n无限增加时，事件A的概率收敛某个确定的值。[18]
马尔可夫链平稳分布定义：如X=（x1，x2，L，xN）为一状态概率向量，P为状态转移概率矩阵。若XP=X，则称X为马尔可夫链的一个平稳分布。[18]
定理2：给定图灵机M和输入字符串W，M不在输入W上停机，为图灵不可判定问题[7]。
结论：依据用户对OA系统的历史操作行为集合W，预测用户的下几次操作行为集合W1，是图灵不可判定问题。
证明：按照用户对OA系统的历史操作行为集合W，W1的具体数值并不能确定，因为用户下几次对OA系统的操作集合W1受各个随机未知因素的影响，而W1并不包含在W中，按照定理2，用反正法，假设构造图灵机M判定W1，M=在输入
W1并不可判定，但W1在实际的工程中意义重要，处理的方法是依据定理1和马尔可夫链平稳分布定义，我们可以对W的统计分析，取极大拟然估计，取W1在W集合中会发生的最大概率做为PageRank缓存服务器缓存数据的依据。这样就极大的提高了OA系统对用户的响应速度。蔡伟鸿在2010年提出基于选择性马尔可夫模型的缓存预取策略[13]，该文获得了在最好情况下能达到60%的命中率。但是本文的用户操作页面的链接之间是存在环，单单用马尔可夫过程很难获得稳定的收敛结果。而PageRank能解决节点之间链接的环问题。
A（i）=∑j∈C（i）A（j）N（j）（1）
A（x）表示该用户操作页面x的PageRank值，C（x）表示所有指向x的用户操作页面，N（x）表示用户操作x页面能链接出去的页面数。OA系统中部分功能PageRank值计算过程如图3。
由于公式（1）是递归定义一个用户操作页面的PageRank值，就是要得到一个页面的PageRank值就要先知道另一些页面的PageRank值。因此需要设置合理的PageRank初始值。本文采用矩阵的观点解决使得无论怎样设置PageRank初始值，最后都会收敛到同一个值。OA系统的操作页面之间的链接关系通过大数定理统计出该页面转到接下来用户操作页面的概率，把高概率的几个页面做为该页面链接页面。
设邻接矩阵P表示这个图的顶点关系，如果頂点（用户的操作页面）x向顶点（用户的下个操作页面）y有链接情况，则Pij=1否则Pij=0。再将每行除以该行非零数字之和，就得到转移矩阵P，如果用户的操作页面总数为M，则这个操作页面的链接矩阵就是N*N矩阵，使用幂法求PageRank值，本文每个操作页面的PageRank值转化为求limAnX的值，其中A=q*P+（1-q）*eet/N。P为概率转移矩阵，et是n维的全1行，q为阻尼系数，取q=0.85，q是为了解决那些不链接任何其他用户操作页面的页面，即孤立用户操作页面。则
eet=1...1···1···1...1 （2）
X为任意的初始向量，本文设为1，不断的迭代AX，直到最后两次的结果近视或相同，最终收敛的向量值就是用户操作的各个页面的PageRank值。本文OA系统随着访问用户的增加，缓存的命中率也越来越高，如图4，A代表图1中采用LFU的基于squid的缓存服务器的命中率，B代表图2中采用PageRank的缓存服务器命中率。也说明了本文的OA系统的缓存服务器能通过自我学习调整服务响应的最大性能极限。
22响应速度理论分析
图1目的是在用户web访问的时候增加反向代理，它做为web服务器的替身和web服务器集群的负载均衡器。本文只讨论做为web服务器的替身，图2具有更高的http请求的响应速度。设web服务器的响应速度为a（a>0），即缓存服务器中没有用户所请求的数据时的OA系统响应速度；缓存服务器响应速度b（b>0），即web的代理服务器中存在用户所请求的数据时的OA系统响应速度； a>b，缓存服务器的命中率为X，则浏览器访问web系统的期望响应速度为：
E=bX+a（1-X）（3）
则X越大E越小，即OA系统对用户的响应速度越快。其中a的实验环境代表web服务器关闭了所有无用端口，操作系统采用freebsd等安全开源并内核经过定制的操作系统。Web服务器采用weblogic11g，weblogic服务器只开启授权的合法的web config供web服务器访问数据库的访问。b代表在同样的硬件型号DL580 G9服务器的情况下，采用squid开源软件做为缓存服务器，或采用weblogic二次开发的基于PageRank缓存算法（即本文的模式）。通过实验可得到本文的X比较高，故本文的响应速度比较快。
23实验设计
为了体现出本文的缓存算法的优越性，图1和图2除了缓存服务器上的替换算法不同，其他的软硬件都相同，服务器都采用DL580 G9，web服务器都采用weblogic11g，数据库都采用oracle11g，操作系统都采用freebsd 8.1，存储采用DMX-4。在表1中，LRU、LFU、Size这3个替换算法，LFU在OA系统中的命中率最高，故图1的基于squid的缓存服务器采用LFU算法，它用A表示。图2用B表示。
收集他们的http连接数。以每隔2小时为单位统计OA服务器http连接数。数据对比如表3和图5，通过表3和图5发现，本文的OA服务器http并发连接数和系统的响应性能都比较好。也说明了本文的缓存算法比较有优越性。
3结语
本文解决了OA系统中大量动态http请求并发瓶颈，极大地提高了web访问性能。OA系统的用户操作从数据的角度看有数据的读、存、删除、更新部分，本文只是在缓存服务器中考虑用户下次操作的预取数据读的部分，在接下来的工作把缓存服务器应用到数据的存、删除、更新部分，即在用户操作中先把数据的存、删除、更新在缓存服务器的内存中操作，再等用户操作OA系统闲的时候，通过缓存服务请求OA系统，进行真正的数据存、删除、更新操作。
参考文献
[1]刁维汉.基于web的信息服务OCLC FirstSerch服务分析[M].上海：上海科学技术文献出版社，2002，56-106.
[2]ABLAN J.Developing Intranet Applications with Java[M].Sams.net，1996，2-15.
[3]賈铁军.网络安全技术及应用[M].北京：机械工业出版社，2010，26-83.
[4]刘化君.网络安全技术[M].北京：机械工业出版社，2010，38-82.
[5]张文.基于Servlet的搜索引擎[J].软件，2011，32（2）：75-77.
[6]杨华甫.网络环境下数据库的一致性研究[J].计算机时代，2004，33（7）：3-4.
[7]LEWIS H R，PAPADIMITRIOU C H.计算理论基础[M].张立昂，刘田，译.清华大学出版社，2006.
[8]周洲仪、吴新松.一种高速安全反向代理服务器的设计与实现[J].计算机研究与发展，2010，46（z1）：332-336.
[9]陈爱林、乐全明 .代理服务器在智能变电站和调度主站无缝通信中的应用[J].电力系统自动化，2010，34（20）：99-105.
[10]JIANG Xiaoming，SHI Jingqiao.Proxisch：An Optimization Approach of LargeScale Unstable Proxy Servers Scheduling[J].International Journal of Computer，Electrical，Automation，Control and Information Engineering，2016，6（10）：1115-1120.
[11]刘宝锋、张文军、谷志奇.基于代理服务器缓存的Internet分层视频点播[J].上海交通大学学报.2005，39（4）：645-648.
[12]陈兵、王立松.基于哈希链表和时间链表的HTTP代理缓存机制的实现[J].南京航空航天大学学报.2002，34（1）：50-54.
[13]蔡伟鸿、 肖水.基于选择性马尔可夫模型的缓存预取策略[J].通信学报.2010，31（2）：58-66.
[14]廖建新 杨波.基于网络代价的流媒体缓存策略研究[J].电子与信息学报.2007，29（9）：2239-2243.
[15]CAO P，IRANI S.Costaware WWW proxy caching algorithms[C].Proceedings of the Usenix Symposium on Internet Technology & Systems.1997，56（1）：193—206.
[16]LANGVILLE A N，MEYER C O，et al.Googles PageRank and Beyond：The Science of Search Engine Rankings[M].Princeton University Press，2006.
[17]TATARINOV I，ROUSSKOV A.Static caching in Web servers[C].Computer Communications and Networks，Proceedings of Sixth International Conference on.1997.
[18]李时.应用统计学[M].北京，清华大学出版社，2005.
