一、概述

       LRU（Least Recently Used），翻译为“最近最少使用”，也就是说，LRU算法认为，在最近使用的数据在未来的时间内大概率还会再次使用，最近没有使用或者很少使用的数据在未来的时间内大概率也不会使用，据此，来进行数据的分类。

       对于缓存来说，通过策略选择保留较热的数据，淘汰较冷的数据，以期获取到更高的命中率是衡量缓存功能的重要指标之一，其设计思想与LRU算法非常契合，故在实际应用中，缓存常使用LRU算法进行数据淘汰。

二、原理

       在Linux内核的PageCache实现中，使用inactive list和active list这样一对双向链表作为LRU机制在缓存中使用的载体。顾名思义，inactive list为不活跃链表，存放较冷的页面，active list为活跃链表，存放较热的页面，通过链表之间的元素移动，使链表上元素尽量按照预想的冷热程度来排序，从而使LRU思想得到实际的应用。

      在缓存中，LRU机制主要有如下两个方面的作用：

• 达到回收水位时，尽量扫描到的页面为可回收页面，避免无效扫描，使回收流程正常进行，维护缓存页面正常流转。
• 尽量保留热数据在缓存中，使缓存获得尽可能高的命中率。

三、实现

        除了链表间的移动外，在Linux内核中，还采用了PG_referenced、PG_active两个标记来进一步描述了热度的区分。这两个标记和inactive list、active list两个链表之间的流转机制如下：

        inactive list, PG_referenced=0 <-> inactive list, PG_reference=1

        inactive list, PG_reference=1 <-> active list, PG_referenced=0

        active list, PG_referenced=0 <-> active list, PG_referenced=1

        PG_active标记的设置与清除，与页面是否转移至active list同步。

        下图可以直观的看到缓存如何使用active list和inactive list两个链表，实现内部页面按照LRU思想流转。

四、应用思路

（一）热度机制的选择

        热度提升还是降低，需要与具体的使用场景配合，方可发挥出LRU机制的最大作用。例如，在缓存中，在下述场景下，可以考虑提升页面热度：

        1、用户写操作。用户访问，可认为是热数据，且此时页面正在使用，大概率是无法回收的，故提升热度使回收尽量不扫描到此页面，避免回收无效扫描。

        2、用户读命中缓存。缓存中存在且用户再次访问，可认为是热数据。

        3、用户读访问未命中缓存。此时，是否进行热度的提升，可根据缓存大小，业务策略来综合考虑。

        下述场景可考虑降低页面热度：

        1、回收流程扫描到此页面。例如，若扫描到active链表且无PG_reference标记的页面，将其转移至inactive链表，同时设置PG_reference标记。

（二）影响缓存LRU机制的因素

1、缓存大小，IO压力影响。例如，若缓存较小，IO压力较大，缓存中的数据处于高速迭代中，那么缓存中的数据可能都是新数据，此时，LRU机制可能只可以维护缓存的正常运转，获取到尽可能高的命中率的目的可能无法达到。

2、业务模型影响，是否有频繁访问的数据。在实际业务中，若有频繁访问的数据，那么缓存可以将这些热数据保留下来，使之可以命中，提高读效率；反之，若业务模型全随机，LRU机制带来的命中率提升就微乎其微了。