一种适用于社交网站的缓存价值判定算法.doc


一种适用于社交网站的缓存价值判定算法#
章晖,林荣恒,邹华**
(北京邮电大学网络与交换技术国家重点实验室,北京 100876)
5
10
15
20
25
30
35
40
摘要:随着社交网站业务数量及规模的增长趋势,如何提高用户请求的响应速率成为一个研
究热点。为了提高此类网站的缓存命中率,通过研究社交网站的业务特征,提出了一种适用
于社交网站的缓存价值判定算法,算法中综合了用户中心性及 PageRank 值两个维度,并通
过计算权重和得出缓存价值,从而提高缓存命中率,加快社交网站的响应速率。
关键词:社交网站;中心性;PageRank;Web Cache
中图分类号:TP315
A Judging Algorithm of Web Cache Value Used in Social
Networking Site
ZHANG Hui, LIN Rongheng, ZOU Hua
(State Key Laboratory working and Switching Technology, Beijing University of Posts and
munications, Beijing 100876)
Abstract: With the development of working site, how to improve the respond rate has
been a research focus. A judging algorithm of Web-Cache value used in work Site was
proposed to improve the efficiency of Web Cache. The proposed bined users'
centrality and the PageRank of pages , and judged the cache value of the page.
Keywords: work Site; Centrality; PageRank; Web Cache
0 引言
SNS(work Site,即“社交网站”) [1],是依据六度理论建立的网站,通过互联网
的方式,将人际关系网的资源完全挖掘出来。在 SNS 的帮助下,用户可以轻松认识“朋友
的朋友”,通过认识的人找到需要的人,扩展自己的人脉,还可以更科学地管理人际网络资
源,为自己赢得更多的机会。[2]的本质是社会化的互联网,这使得 SNS 在 时
代飞速的发展。然而,随着用户的急剧增加及数据量指数型地增长,包括社交网站在内的许
多 web 业务都面临着访问速率的难题。近年来,社交网站业务爆发式地扩充,这一问题在
此类网站中显得尤为突出。
由于缓存的存储容量有限,当存储区被占满时,新对象将无法存储,这时需要按某种策
略将一部分当前不再具有存储价值的对象替换出去,因此 Web 缓存的性能在很大程度上依
赖于一个好的缓存替换策略。最佳的替换策略应该能够针对业务访问特性,灵活动态地调整
缓存对象,从而提高缓存命中率,加快系统响应速率。
然而由于社交网站较之其他网站具有特殊性,此类站点的用户之间存在着“关系”,并
且基于这种“关系”存在大量扩散性的信息转发和分享[3]。目前通用的缓存替换策略对于这
种业务特性缓存效果并不明显。
因此,在对社交网站的业务特征进行深入研究的基础上,本文提出了一种适用于社交网
站的缓存价值判断算法。该算法根据社交网络的拓扑结构及信息的“流行度”调整缓存对象,
可以有效地改善社交网站中现有缓存替换策略的性能。
基金项目:核高基项目(2009ZX01039-001-01)
作者简介:章晖,(1986-),女,硕士生,研究方向:下一代网络。
通信联系人:邹华,(1969-),女,教授,主要研究方向为“通信软件”和“下一代网络增值业务提供”。 E-mail:
******@bupt.
-1-

本文的内容安排如下,第 1 节给出 Web Cache 替换策略的理论描述;第 2 节对社会化
网络结构及网页流行度量化值进行研究,提出了“中心用户”、“热门页面”的概念;第 3
节提出了一种适用于社交网站的缓存替换算法;第 4 节给出算法效果分析。
1 相关研究工作
45
50
本节首先给出 Web Cache 的理论基础,然后描述了所存在的缓存替换问题,以及目前
的相关解决方法与策略。
Web Cache[4]的工作原理是基于程序访问的局部性,即把经常用到的数据放在一个高速
的 Cache 里。CPU 对存储器进行数据请