| 摘要: |
| 数据缓存技术可以有效地减少网络拥塞,减轻服务器负载,加快信息访问速度.通过部署一组地域分布的缓存节点相互协作处理用户请求,可以进一步提高系统性能.在分布式缓存系统中,一个值得关注的问题是优化缓存的放置,使访问开销最小化.首先建立了一个理论模型来分析缓存副本放置对系统访问开销的影响.基于这个模型,缓存放置问题可以形式化地描述成一个最优化问题,提出了一种图算法来解决该问题.图算法使用修改的Dijkstra算法在访问代价图中寻找一条最短路径,该路径对应一种最优的缓存部署.理论上证明了图算法的正确性,并使用仿真实验对其性能进行评估.实验结果表明,图算法的性能优于大部分现有的分布式缓存机制. |
| 关键词: 分布式缓存系统 缓存放置 图算法 |
| DOI： |
| 分类号: |
| 基金项目:Supported by the National Natural Science Foundation of China under Grant Nos.60803111, 90718031, 60721002 (国家自然科学基金); the National High-Tech Research and Development Plan of China under Grant No.2006AA01Z199 (国家高技术研究发展计划(863)); the National Basic Research Program of China under Grant No.2009CB320705 (国家重点基础研究发展计划(973)); the Jiangsu Provincial Natural Science Foundation of China under Grant No.BK2009100 (江苏省自然科学基金) |
|
| Graph-Based Optimal Cache Deployment Algorithm for Distributed Caching Systems |
|
LI Wen-Zhong,CHEN Dao-Xu,LU Sang-Lu
|
| Abstract: |
| 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. |
| Key words: distributed caching system cache placement graph-based algorithm |
