聊聊 memcached 1.4 的 LRU 算法

栏目: 数据库 · 发布时间: 5年前

内容简介:Memcached 是完全基于内存,而内存总会被用完的,如果在 set 操作的时候发现内存不足了,它会怎么办?它采用 Least Recently Used (LRU) 算法,理解 LRU 算法对于使用 memcached 非常关键。从 memcached1.5 开始,为了进一步优化内存使用和提高性能,memcached 采取了新的 LRU 算法,我会分三篇文章说说新旧版本的 LRU 算法,今天描述 memcached1.4 以前版本的 LRU 算法的原理,相对简单一点。在 memcached1.4 以前的

Memcached 是完全基于内存,而内存总会被用完的,如果在 set 操作的时候发现内存不足了,它会怎么办?它采用 Least Recently Used (LRU) 算法,理解 LRU 算法对于使用 memcached 非常关键。

从 memcached1.5 开始,为了进一步优化内存使用和提高性能,memcached 采取了新的 LRU 算法,我会分三篇文章说说新旧版本的 LRU 算法,今天描述 memcached1.4 以前版本的 LRU 算法的原理,相对简单一点。

在 memcached1.4 以前的版本中,如果一个 item 过期了,memcached 并不会主动回收内存空间;也没有异步的线程在后台回收。它的内存回收策略完全是 同步 的,对于一个 set 操作来说,如果 memcacheed 发现内存不够了,它会采用一种算法进行内存操作,从而为新的 item 腾出空间。

它采取的不是 FIFO 这种先进先出的内存淘汰算法,它采用的是更高级的内存淘汰算法,这就是 LRU,如果一个 item 长时间没有使用且已经过期了,会优先清空它们的内存空间,当然这个算法也不是那么智能,假设两个 item 的过期时间一样,在清理的时候,不会优先清理相对较大的 item。

甚至 不同 的 Slab-class 其 LRU 淘汰策略也是完全独立的,互不影响。

在 set 的时候,如果没有过期的 item 被淘汰,那怎么办?这个时候 memcached 只好根据 LRU 算法淘汰尚未过期的 item,这个操作也叫做 evict

memcached 本质上是缓存软件,如果你存储的数据不能丢失(非缓存),那需要好好进行内存容量规划,避免数据被 evict。想想看,假设 session 数据使用 memcached 存储,如果一个正常用户对应的 session 被 evict 了,那么这个用户就 logout 了,影响可大可小。

那么 memcached 内部是如何实现 LRU 算法的呢?我没有 看源代码 ,完全通过 wiki 和官方博客学习,如果描述有问题或模棱两可,还请见谅。

在 memcached 中,每个 item 对象被创建的时候,它维护一个计数器,item 对象计数器的值就是 unix 当前时间戳,当一个 item 被 FETCHED 的时候(get、set、replace),这个计数器的值就会更新为当前时间(表示被使用了)。

如果 memcached 在遇到 set 操作的时候,发现内存不够,就会淘汰计数器值最小的 item(过期的优先淘汰),本质上就是这么简单:如果某个 item 没被使用就优先淘汰。

听上去是不是很简单?我们再稍微深入一点,每个 Slab-class 的 LRU 由一个双向链表维护,如下图:

聊聊 memcached 1.4 的 LRU 算法

当一个新 item 被 set 的时候,它会进入链表的 head,如果发生 evict,那么在链表 tail 尾的 item 会从内存中释放。

当 get 一个 item,它会从链表中 unlink,然后重新 link 到链表的 head,这个过程叫做 bump

由于 bump 会有锁(mutex locks and mutations),频繁发生对性能有非常大的影响,所以 memcached 做了一个优化,在 60 秒内同一个 item 只会产生一次 bump。

活跃的 item 即使没有频繁产生 bump,但如果 get 操作非常多,也会产生很多的锁竞争,导致某些 get 延时不一致,甚至导致 cpu 负载在某个时间过高,也就是多线程的扩展性受制于 memcached 的 LRU lock。什么意思呢?对于老的 URL 实现来说,memcached 开启的工作线程建议不要超过 8 个。

为了进一步提升 LRU 的效率和减少内存的使用,后续我会描述最新的 memcached LRU 算法。

再补充一点,一个 item 什么时候会释放内存呢?通常下面几个步骤会释放:

  • 主动 del 操作。

  • set 覆盖操作。

  • 一个过期 item 进行 get,add,replace 操作的时候。

  • evict 操作发生的时候,优先回收 tail 尾部过期的 item。

观察 evict 和内存回收情况对于评估 memcached 非常实用,可以通过 stats 和 stats items 命令了解详细的情况。相关参数解释如下:

1:reclaimed:表示有多少过过期的 item 被回收了。

2:evicted:查看有多少个 item 在过期前发生了 evict

3:evicted_nonzero:查看有多少个明确设置了过期时间的 item 在过期前。相对来说明确设置过期时间的 item 被 evict,那么可能会影响业务。

4:evicted_time:上一次运行 evict 到现在的时间。

5:expired_unfetched:查看有多少 item 被 set 后,从来没访问过,然后因为过期被回收的数量。

6:evicted_unfetched:查看有多少 item 被 set 后,从来没访问过,然后被 evict 的数量。

7:evicted_active:查看有多少 item 被 set 后,最近被访问过(但没来得及达到 LRU head),然后被 evict 的数量。

memcached 相关文章:

欢迎大家关注我的公众号(ID:yudadanwx,虞大胆的叽叽喳喳),所有文章都是原创,主要来源于平时工作中遇到的问题和学习中的一些想法。

聊聊 memcached 1.4 的 LRU 算法


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

C语言程序开发范例宝典

C语言程序开发范例宝典

2010-1 / 59.00元

《C语言程序开发范例宝典》全面介绍了应用C语言进行开发的各种技术和技巧,全书共分12章,内容包括基础知识、指针、数据结构、算法、数学应用、文件操作、库函数应用、图形图像、系统调用、加解密与安全性、游戏、综合应用等。全书共提供300个实例,每个实例都突出了其实用性。 《C语言程序开发范例宝典》既可作为C程序的初学者学习用书,也可作为程序开发人员、相关培训机构老师和学生的参考用书。一起来看看 《C语言程序开发范例宝典》 这本书的介绍吧!

JS 压缩/解压工具
JS 压缩/解压工具

在线压缩/解压 JS 代码

CSS 压缩/解压工具
CSS 压缩/解压工具

在线压缩/解压 CSS 代码

JSON 在线解析
JSON 在线解析

在线 JSON 格式化工具