Memcached内存替换算法研究

发布时间：2018-03-04 00:08

本文选题：Memcached　切入点：内存替换　出处：《华中科技大学》2016年硕士论文　论文类型：学位论文

【摘要】：随着数据量的增长及应用的扩大,基于内存的数据库在数据访问过程中扮演越来越重要的角色。内存数据库相对于普通持久型数据库有着访问速度快、轻量、易管理等特点,被广泛应用于各种大型数据中心。Memcached作为一种常见的内存数据库在Facebook、Twitter、Sina等中得到应用,然而Memcached在内存替换算法上仍存在无法有效地处理数据大小变化较大的不足,当发生“钙化”现象时,Memcached会出现命中率降低、访问延迟增大等结果,严重制约了各种依靠Memcahced作为数据缓存的系统的性能。本文对Memcached所处理数据的特点进行了研究与分析,发现不同大小的Item的访问对一个Slab是否成为一个热的Slab影响程度不同,而不是以前研究中所提到的固定关系,同时研究了Slab与Item的关系,提出了基于影响因子与淘汰代价的Memcached内存替换算法。影响因子是根据不同大小的Item对这个Item所在的Slab是否成为热的Slab影响程度不同而设计的,大的Item比小的Item更能使Slab成为一个热的Slab,进而免于淘汰。同时重新定义了Item平均访问频度这一概念:单个item所承受的访问请求而不是整个Slab;发现了不同顺序的访问对Slab是否成为热的Slab影响程度不同这一现象并采用“半衰期”方法量化这种影响,最后利用这两个因素动态地更新影响因子的大小。淘汰代价指的是淘汰一个Slab和Item的代价,在Memcached内存不足时,通过最近访问次数、访问时间、大小等计算淘汰一个Slab及Item的代价大小来确定是淘汰一个Slab还是Item,而不同于以前研究中提到简单的主动与被动Slab淘汰策略。改进的方法提高了Memcached在内存不足时处理数据访问的能力。测试结果表明,改进的方法在命中率上有5%左右的提升并将读写延迟降低了2%到4.5%。同时改进方案优化了Slab和Item淘汰数量,最后将改进的方法在pNFS中进行了应用,测试表明改进的方法降低了pNFS系统的读写延迟,最高可达5%。
[Abstract]:With the increase of data volume and the expansion of application, the memory-based database plays a more and more important role in the process of data access. Compared with the common persistent database, the memory database has the characteristics of fast access, light weight, easy management and so on. It is widely used in various large data centers. Memcached, as a common memory database, has been used in Facebook Twitter. However, Memcached still has some shortcomings in memory replacement algorithm, which can not effectively deal with large changes in data size. When "calcification" occurs, the hit rate and access delay will decrease, which seriously restricts the performance of various systems that rely on Memcahced as data cache. The characteristics of the data processed by Memcached are studied and analyzed in this paper. It is found that the access of Item of different sizes has different effects on whether a Slab becomes a hot Slab, rather than the fixed relationship mentioned in previous studies. The relationship between Slab and Item is also studied. A Memcached memory replacement algorithm based on the influence factor and the cost of elimination is proposed. The influence factor is designed according to the influence degree of different size Item on whether the Slab in which the Item is located is a hot Slab. Large Item makes Slab a hotter than a small Item and thus avoids elimination. At the same time, the concept of average access frequency of Item is redefined: the access request to a single item rather than the whole item; the discovery of different order visits. Asking whether there is a different degree of influence on whether Slab becomes a hot Slab and quantifying it using the "half-life" method, Finally, these two factors are used to dynamically update the size of the influencing factors. The elimination cost refers to the cost of eliminating a Slab and a Item. When the Memcached memory is out of memory, it can be accessed through the number of recent visits and the access time. The cost of eliminating an Slab and Item is calculated to determine whether to phase out an Slab or an item, as opposed to the simple active and passive Slab elimination strategies mentioned in previous studies. Ability to manage data access. Test results show that, The improved method improves the hit rate by about 5% and reduces the delay of reading and writing by 2% to 4.5. At the same time, the improved scheme optimizes the number of Slab and Item elimination. Finally, the improved method is applied in pNFS. The test results show that the improved method can reduce the delay of reading and writing of pNFS system, up to 5%.
【学位授予单位】：华中科技大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：TP311.13

【参考文献】