標題: Pareto-based cache replacement for YouTube
作者: Lee, Ming-Chang
Leu, Fang-Yie
Chen, Ying-ping
資訊工程學系
Department of Computer Science
關鍵字: YouTube;Memcached;Pareto principle;Cache replacement;Least recently used;Least frequently used
公開日期: 1-十一月-2015
摘要: Recently, YouTube, which plays diverse video programs for worldwide users, has been one of the most attractive social-networking systems. YouTube employs a distributed memory caching system called Memcached to cache videos, and utilizes the Least Recently Used algorithm (LRU for short) to evict the least recently watched video when Memcached runs out of space. However, LRU may cause a high miss count, which is the number of times that a video requested by users cannot be found in Memcached. This might not only increase network overhead, but also cause a poor service quality for YouTube since those videos need to be retrieved from the remote back-end database. To solve these problems, in this paper, we classify videos into popular and unpopular videos and propose two cache replacement algorithms based on the Pareto principle. One is Pareto-based Least Frequently Used algorithm (PLFU for short), and the other is Pareto-based Least Recently Used algorithm (PLRU for short). The two algorithms always keep several top popular videos of each video category in Memcached to reduce miss count. However, when Memcached has insufficient space to hold a video requested by a user, PLFU and PLRU repeatedly evicts an unpopular video from Memcached based on LFU and LRU so as to hold the video. Our simulation results based on a real-world YouTube trace show that PLFU performs the best among all tested algorithms in terms of miss count and video-retrieval time. The results also indicate that when PLRU is used for a longer time, it provides the second best performance.
URI: http://dx.doi.org/10.1007/s11280-014-0318-9
http://hdl.handle.net/11536/128218
ISSN: 1386-145X
DOI: 10.1007/s11280-014-0318-9
期刊: WORLD WIDE WEB-INTERNET AND WEB INFORMATION SYSTEMS
Volume: 18
起始頁: 1523
結束頁: 1540
顯示於類別:期刊論文