大规模视频点播磁盘cache替换算法

DISK CACHE REPLACEMENT ALGORITHMS FOR LARGE SCALE VIDEO ON DEMAND SYSTEM

大规模视频点播（ＬＳＶＯＤ）中ｃａｃｈｅ机制是提高系统效率的有效手段，是支持ＶＯＤ实用化的关键技术之一．由于连续媒体的数据量大，使用周期长等特点，传统的ｃａｃｈｅ替换算法不能直接应用于ＬＳＶＯＤ．文中根据ＶＯＤ的特点开发了两种基于访问频率的替换算法：ＬＦＲＵ（ｌｅａｓｔｆｒｅｑｕｅｎｃｙ ａｎｄ ｒｅｃｅｎｔｌｙ ｕｓｅｄ）和ＰＬＦＵ（ｐｅｒｉｏｄ ｌｅａｓｔｆｒｅ－ｑｕｅｎｃｙ ｕｓｅｄ）算法，它们都试图将访问频率大的视频数据保留在ｃａｃｈｅ中．ＬＦＲＵ 算法结合了数据的访问频率和访问时间信息，对访问模式的变化具有一定的适应性．ＰＬＦＵ 算法用周期法和预测法解决了ＬＦＵ 算法中的ｃａｃｈｅ“污染”问题．实验数据显示，新的替换算法比传统的替换算法效率高，更适合大规模的ＶＯＤ系统．

Cache schema is very important for LSVOD (large scale video on demand) system and it is one of the most important techniques to enable VOD to enter market. The disk cache is different from memory cache in several ways for the large volume and high bandwidth requirement of continuous media data. In this paper, two new cache replacement algorithms based on access frequency: LFRU(least frequency and recently used) and PLFU(period least frequency used) are developed. LFRU is a trade off between LRU and LFU, which has advantages of both algorithms. PLFU is an improved LFU algorithm, which solves the cache pollution problem of LFU algorithm. It is shown by means of simulation and experiments that the new algorithms are more effective and more suitable than others for LSVOD system.