Cache Replacement Algorithms for YouTube

Abstract

In recent years, many social network systems like, YouTube, Facebook, Twitter, etc. have been a part of our everyday life. Among these systems, YouTube which plays video programs of different interesting themes for users has been one of the most attractive ones. Basically, when the space of Memcached in YouTube is full, the Least Recently Used algorithm (LRU for short) is employed to evict a least recently watched video. However, the LRU, due to its own property, may cause more miss counts of Memcached for YouTube, consequently increasing the network bandwidth and energy consumptions. To solve these problems, in this paper we proposed two cache replacement algorithms, the Pareto Least Recently Used algorithm (PLRU for short) and Pareto Least Frequently Used algorithm (PLFU for short), in which videos are classified into different popularity categories, and those videos in the top 10% and 20% of the top two popular categories of YouTube, based on Pareto principle, are then chosen to serve users\' requests without removing them from Memcached. The simulation results show that the PLFU algorithm can significantly reduce miss counts of Memcached compared with those when the LRU and Least Frequently Used algorithm (LFU for short) are employed, thus achieving great performance improvements for the top two popular categories of videos. Also, when a large space of Memcached is available, the miss counts of the PLRU are higher than those of the LRU. But when comparing them in a small available Memcached space, the miss counts of the LRU on the contrary is higher than those of the PLRU.