A huge amount of video contents have been generated and spread in the Internet. More and more users would like to view online videos rather than downloading them to the local devices in advance. Hence, in the Content Delivery Networks (CDN), the speed of the users accessing to the videos is much crucial to the user experience, and then an efficient caching algorithm in reducing server load and latency can play a very significant role. In this paper, based on Pareto Least Recently Used (PLRU) algorithm and Least Recently Used-K (LRU-K) algorithm, we present an improved cache replacement strategy for online videos---Multi-level PLRU (MLPLRU) cache algorithm, which sets multi-level label indexes to the video contents in the cache list of the CDN node. Simulation results indicate that this algorithm can improve the cache hit ratio and relief the cache pollution problem under the certain conditions.