Design And Implementation Of Cache Algorithm For Ring Server For Crbt Service

With the rapid growth of Color Ring Back Tone services, there becomes an emerging problem of storing and managing large amount of ring data effectively and efficiently. This paper proposed a solution by adding ring server as a central storage node to the network and utilizing disk cache algorithm extensively to meet the requirement of system design capacity. First we built cache allocation model under ideal assumptions and provided an optimal solution by using dynamic programming, and then we found it a good approximation by using greedy algorithm for improved speed and reduced space. By analyzing ring subscription data and building mathematical models for ring popularity, we proved that ring playing popularity obeys Zipf distribution, under which we experimented on classical cache algorithm LRU(Least Recently Used) and LFU(Least Frequently Used). Based on the pros and cons of LRU and LFU and the context of ring server application, we proposed a new cache replacement algorithm LFU-EA(LFU with Exponential Aging), which adopts exponential smoothing as frequency aging mechanism, and it balances well the frequency feature and time feature of the resource access pattern. Experiments show that LFU-EA algorithm improves cache hit ratio over classical algorithms by 10%. To implement LFU-EA algorithm effectively, we introduced limited heap data structure to filter massive ring files efficiently and designed generic hash container with double hashing mechanism, which ensures stable performance even under heavy load for the most demanding real-time applications. Experiments show that the generic hash container we design has the advantage of higher speed and lower memory consumption over standard hash containers. Finally, we illustrated the load balancing policy, the rationale to apply Reactor Pattern and Leader/Followers Pattern as concurrent architecture, and the design of fault tolerance mechanism. The proposed popularity modeling technique and LFU-EA algorithm in the paper is a good reference to other disk caching systems.