Research On The Algorithm Of Memory Replacement In Memcached

With the increase of data and expansion in application, In-memory databases play a more and more important role in the access of data. Compared with persistent database, Inmemory database have the advantage of high speed in data access, light weight, easy to manage and so on, thus we can see it has been widely used in all kind of data center. Memcaced, as a common In-memory database, have been widely deployed in Facebook, Twitter, Sina etc. However, flaws still exist in Memcached that it can't deal well with data that vary sharply. When the phenomenon of calcification appears, we will see decriment in hit rate and incriment in read and write latency dramatically, which will undoubtedly impact performance of applicaions that use Memcached as cache.The paper have researched and analyzed the property of dataset that Memcached dealt with and find that items with different sizes actually have different influence on whether slab is hot or not, which is totally different from the previous research mentioned before that it is a fixed relationship. At the same time, we take the relationship between slabs and items into account and finally propose the algorithm of memory replacement based on impact factor and cost of eviction. Impact factor is based on the fact that item with diffent size will actually have diffent impact on whether the slab whom it contains is hot or not. Greater item will certainly have deeper influence on the slab, thus the slab will not evicted easily. At the same time, we redefine the concept of average visit frequency of item: total visit numbers on per item not on per slab. In the mean while, we find out the phenomenon that visit with different order will have distinct impact on the slab and use the half-life concept to quantize this influence, at last, we employ this two concept dynamically update the impact factor. The eviction cost refers to the cost of evicting a slab or item. By collecting the visit number recently, the last visit time, size of slab and item, we can easily calculate the cost and decicde whether we need to evict a slab or item when Memcached run out of memory. Via the method mentioned before, we can surely improve the capacility of handling data when memory is not enough in Memcached, which is not the same as active and passive slab eviction policy mentioned in others' papers.The method we have proposed can make Memcached have better ability to handle data when memory run out. Tests have proved that the method above can improve the hit rate by 5 percent and can achieve 2 to 4.5 percent decrease in the read and write latency compared to the method without optimization. In the mean while, it also optimizes the number of slabs and items that have been evicted when meomory is not enough. Finally, we take experiment in pNFS that adopt our method and result shows that read and write latency reduce by about 5 percent at most.