Memcached LRU策略

从 Memcached1.5 开始，实现了一个改良的 LRU 算法，也叫做分段 LRU（Segmented LRU）算法，新算法主要是为了更好的利用内存，并提升性能。包含了二个重要的线程:maintainer 线程、crawler 线程。

maintainer线程

每个 Slab-class 有一个 LRU，每个 LRU 又由四个子 LRU 组成，每个子 LRU 维护独立的锁（mutex lock），所有的 LRU 由一个独立的线程维护（这和旧的 LRU 算法有很大的不同），称之为 LRU maintainer 线程。

每个 item 有一个 flag，存储在其元数据中，标识其活跃程度：

• FETCHED：如果一个 item 有请求操作，其 flag 等于 FETCHED。

• ACTIVE：如果一个 item 第二次被请求则会标记为 ACTIVE；当一个 item 发生 bump 或被移动了，flag 会被清空。

• INACTIVE：不活跃状态。

这四个子 LRU 包含了四个独立的 queue，相关的 queue 可能会迁移到其他的 queue，这么设计就是为了减少 bump 的产生.

• （1）HOT queue：如果一个 item 的过期时间（TTL）很短，会进入该队列，在 HOT queue 中不会发生 bump，如果一个 item 到达了 queue 的 tail，那么会进入到 WARM 队列（如果 item 是 ACTIVE 状态）或者 COLD 队列（如果 item 处于不活跃状态）。

• （2）WARM queue：如果一个 item 不是 FETCHED，永远不会进入这个队列，该队列里面的 item TTL 时间相对较长，这个队列的 lock 竞争会很少。该队列 tail 处的一个 item 如果再一次被访问，会 bump 回到 head，否则移动到 COLD 队列。

• （3）COLD queue：包含了最不活跃的 item，一旦该队列内存满了，该队列 tail 处的 item 会被 evict。如果一个 item 被激活了，那么会异步移动到 WARM 队列，如果某个时间段内大量的 COLD item 被激活了，bump 操作可能会处于满负载，这个时候它会什么也不做（不移动到 WARM queue），避免影响工作线程的性能。

• （4）TEMP queue：该队列中的 item TTL 通常只有几秒，该列队中的 item 永远不会发生 bump，也不会进入其他队列，节省了 CPU 时间，也避免了 lock 竞争。

HOT 和 WARM LAU queue 有内存使用的限制，而 COLD 和 TEMP 队列没有内存使用限制，这主要是为了避免一些不经常使用的 item 长期占据在相对活跃的队列中。

crawler线程

虽然 LRU Maintainer解决了很多问题，但结合 Memcached 内存分配机制，它还有一些潜在的问题，比如说很难动态调整内存的大小；再比如某些 Slab-class 可能存储了很少的 item（和 item 的大小有关系）；再比如一个空间很大的过期 item 其实可以存储几百个小空间 item；还有 LRU Maintainer 并没有过期 item 回收的功能。

为了解决这些问题，memcached1.5 版本引进了 LRU crawler, 它是一个异步的后台线程，扫描 LRU 中的所有 item，然后回收过期 item，或者检查整个 Slab-class，进行相应的调整。

crawler 在每个 Slab-class 的每个子 LRU 的 tail 部插入一个特别的 crawler items，然后从子 LRU 的 tail 到 head 不断进行扫描，如果发现有过期的 item，就进行回收。

它在给每个子 LRU 进行扫描的时候，会构建一个直方图，通过直方图决定下一次何时扫描，举个例子：

      1.假如 Slab-class 1 有 100 万个 item，过期时间都是 0（也就是不过期），那么最多每小时扫描一次（因为再扫描也回收不了多少内存）。
      2.假如 Slab-class 5 有 10万个 item，其中 1% 的 item 5分钟后过期，那么 crawler 将智能的在五分钟后再一次扫描，因为能够回收很多内存。

crawler 还有很多的智能调度策略，比如 Slab-class 越高，代表存储的单个 item 空间更大，尽快回收能够释放更多的内存。

结合分段 LRU 机制，crawler 也有很多好的调度策略，比如 HOT queue 如果有很多 item （TTL 较短），那么应该频繁的扫描，同时避免频繁扫描 COLD queue。

这些调度策略都是为了减少不必要的 crawler 工作。

LRU算法

在LRU高速缓存中，哈希映射使快速访问高速缓存的对象成为可能。LRU通过标记过期的或所谓的最近最少使用的对象来避免缓存无限增长。接下来，我们从较高的角度来看LRU是如何工作的。

什么是LRU？
LRU，Least Recently Used 最近最少使用的一种页面置换算法。算法根据数据的历史访问记录的时间来进行淘汰数据，其核心思想是 如果最近没有被访问过，那么将来被访问的概率也比较低，所以被删除的几率就更大

另外，除了 LRU 还有另外两种常用的缓存 页面置换算法：FIFO（先进先出，先来先服务）、LFU（最近最少使用算法，跟 LRU 的区别为 LFU是按照访问次数进行处理 而 LRU是访问时间）

LRU的实现原理比较简单：维护一个链表，INPUT操作的时候如果对应元素在链表已经存在，则把UPDATE后将该元素放到链表顶端，如果不存在则INSERT后将元素放到链表顶端；SELECT操作的后将查询到的元素移动到链表顶端；这样就能确保不常用的数据在链表底端。
memcached的LRU可没有这么简单。

memcached的LRU

memcached 的 LRU 机制其实不止单纯的 LRU，它是由几种策略组成的一种机制：

    惰性删除：memcached 一般不主动积极删除过期，当被访问的时候才根据时间判断是否过期

    flush_all：flush 命令专门用来清理所有数据，但是实际代码逻辑中也并不是一次清理了所有数据，一般在申请内存的时候或者查询的时候进行清理，这样保证了效率

    创建的时候检查：需要 set/add 的时候，需要申请一个新的 item，这个时候会检查同一个 slabs 里面的过期数据；另外一种情况，当没有内存分配给新的item，memcached 会从 LRU链表的尾部进行释放，即使还没有到 item 的过期时间

    LRU爬虫机制 LRU爬虫机制 实际是由多个爬虫联合组合而成的完整机制：item爬虫、lru爬虫、slab爬虫

        item爬虫: memcached 是惰性删除机制的，但是如果有些 item 一直未被 get 呢，对应资源就只能一直被占用而无法释放，所以才有启动单独的 辅助线程，独立进行过期item 的清理

        lru爬虫: 维护每个 slabclass 对应的 HOT_LRU( 热数据 ) 、WARM_LRU( 暖数据 ) 、COLD_LRU ( 冷数据 ) 三个队列，不断的调整三个队列下的item链表，当需要申请一个新的item的时候，如果没有内存可以分配，则从这三个队列里面进行淘汰item，所以需要维护队列数据，保证经常访问的不被淘汰，不经常访问或者过期的item优先被淘汰

            - 新的item会被添加至 HOT_LRU 队列头部
            - 超过 HOT_LRU 队列长度阀值的，添加至 COLD_LRU 队列
            - 超过 WARM_LRU 队列长度阀值的，添加至 COLD_LRU 队列
            - 如果 COLD_LRU 队列数据被访问，则转移到 WARM_LRU 队列
            - 如果 HOT_LRU 队列 或者 WARM_LRU 队列 数据被访问，则转移到 WARM_LRU 队列头部
            - 如果内存不够需要淘汰 item，则优先回收 COLD_LRU 队列的内存

        以上三个队列都有可能 item 被 删除 或者 强制过期 而回收`

        slab爬虫: 用来维护 slabclass 的空间，举个栗子,我们都知道存储 slabclass -> chunk -> item 的三级概念，每个 slabclass区域 ( slabclass[1] = 96K, slabclass[2] = 120K … ) 存放不同大小的 item，但是如果存储的一直都是 96K 以内的 item，一直存储在 slabclass[1] 这个内存空间，那么就会一直申请 chunk (每次1M ) ，直到内存申请完毕，但是万一后续需要存储 120K 规格的 item，则会出现无法申请内存的情况，那么就不能存储 120K 规格的item，所以 slab爬虫 就是用来处理这一尴尬情况的。

老版本的LRU算法
在 memcached 中，每个 item 对象被创建的时候，它维护一个计数器，item 对象计数器的值就是 unix 当前时间戳，当一个 item 被 FETCHED 的时候（get、set、replace），这个计数器的值就会更新为当前时间（表示被使用了）。

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

听上去是不是很简单？我们再稍微深入一点，每个 Slab-class 的 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 个。