分布式缓存系统中一种优化缓存部署的图算法  

Graph-Based Optimal Cache Deployment Algorithm for Distributed Caching Systems

作　　者：李文中[1,2] 陈道蓄[1,2] 陆桑璐[1,2] 

机构地区：[1]南京大学计算机软件新技术国家重点实验室,江苏南京210093 [2]南京大学计算机科学与技术系,江苏南京210093

出　　处：《软件学报》2010年第7期1524-1535,共12页Journal of Software

基　　金：国家自然科学基金Nos.60803111;90718031;60721002;国家高技术研究发展计划(863)No.2006AA01Z199;国家重点基础研究发展计划(973)No.2009CB320705;江苏省自然科学基金No.BK2009100~~

摘　　要：数据缓存技术可以有效地减少网络拥塞,减轻服务器负载,加快信息访问速度.通过部署一组地域分布的缓存节点相互协作处理用户请求,可以进一步提高系统性能.在分布式缓存系统中,一个值得关注的问题是优化缓存的放置,使访问开销最小化.首先建立了一个理论模型来分析缓存副本放置对系统访问开销的影响.基于这个模型,缓存放置问题可以形式化地描述成一个最优化问题,提出了一种图算法来解决该问题.图算法使用修改的Dijkstra算法在访问代价图中寻找一条最短路径,该路径对应一种最优的缓存部署.理论上证明了图算法的正确性,并使用仿真实验对其性能进行评估.实验结果表明,图算法的性能优于大部分现有的分布式缓存机制.Data caching has emerged as an effective way to reduce network traffic, alleviate server load and accelerate information access. Deploying a group of distributed caching nodes to cooperate with each other in serving client requests will further improve the system performance. One of the important issues in distributed caching system is coordinating cache placement to achieve access cost minimization. In this paper, a theoretical model is introduced to analyze the access cost of placing a set of data objects in distributed caching systems. In this model, the cache placement problem is formulated as an optimization problem. A graph-based algorithm is proposed to solve the problem. The algorithm applies a modified Dijkstra＇s algorithm to look for the shortest path in the access cost graph, which corresponds to an optimal cache deployment for the system. The correctness of the graph-based algorithm is proved theoretically and its performance is evaluated by simulations. Experimental results show that the graph-based algorithm outperforms most existing distributed caching schemes.

关 键 词：分布式缓存系统 缓存放置 图算法 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]