缓存替换策略之 MRU（Most Recently Used）解析

缓存替换策略概述

在后端开发的缓存设计中，缓存替换策略起着至关重要的作用。缓存作为一种高速存储，其容量有限，当缓存空间已满且有新的数据需要存入时，就需要决定淘汰哪些旧数据，这便是缓存替换策略要解决的问题。常见的缓存替换策略有多种，如先进先出（FIFO）、最近最少使用（LRU）、最不经常使用（LFU）等，而本文重点探讨的是最近最常使用（MRU，Most Recently Used）策略。

MRU 策略原理

MRU 策略的核心思想是，当缓存已满且需要替换数据时，选择最近最常使用的那个数据进行淘汰。与 LRU 淘汰最近最少使用的数据相反，MRU 认为那些最近频繁被访问的数据在未来继续被访问的概率相对较低，而较少被访问的数据可能在未来更有用。这一理念基于对数据访问模式的一种假设，在某些特定的应用场景下具有独特的优势。

想象一个缓存系统，它像一个书架，缓存中的数据项就如同书架上的书籍。当书架满了，要放入一本新书时，MRU 策略就会把最近经常被取下来阅读（类比数据被频繁访问）的那本书拿走，给新书腾出空间。这样做的逻辑是，这本书既然已经被频繁阅读，可能短期内不会再读，而那些长时间没动过的书，说不定下一次就会被用到。

MRU 策略适用场景

热点数据快速更替场景：在一些互联网应用中，数据热点变化非常快。例如新闻资讯类平台，新的热点新闻不断涌现，旧的热点新闻热度迅速下降。对于这类应用的缓存，如果采用 LRU 策略，可能在旧热点新闻热度还未完全消退时就将其淘汰，导致频繁从后端存储获取数据。而 MRU 策略可以让新热点新闻在缓存中停留更长时间，同时及时淘汰旧热点新闻，提高缓存命中率。
资源敏感且数据使用模式特殊场景：某些嵌入式系统或资源受限的环境中，缓存容量极其有限。在这些场景下，如果数据的访问模式呈现出短期内某些数据被高度集中访问，随后这些数据不再被需要的特点，MRU 策略可以有效地利用有限的缓存资源。比如一些物联网设备，它们在特定时间段内可能只与某些特定的传感器数据交互频繁，MRU 策略能够根据这种特殊的数据使用模式，合理管理缓存。

MRU 策略实现方式

基于链表的实现
- 数据结构设计：实现 MRU 策略可以使用双向链表结合哈希表的数据结构。双向链表用于维护数据的访问顺序，哈希表用于快速定位链表中的节点。双向链表的节点结构应包含数据本身、前驱节点指针和后继节点指针。哈希表则以数据的键作为索引，值为对应双向链表节点的指针。
- 操作流程：
  - 插入操作：当有新数据要插入缓存时，如果缓存已满，首先找到双向链表的头节点（根据 MRU 策略，头节点为最近最常使用的数据），删除该节点，并从哈希表中移除对应的键值对。然后创建新的双向链表节点，将新数据放入节点，并将该节点插入到双向链表的尾部（因为新插入的数据是最近使用的），同时在哈希表中添加新键值对，键为新数据的键，值为新节点的指针。
  - 访问操作：当访问缓存中的数据时，通过哈希表快速找到对应的双向链表节点。如果找到，将该节点移动到双向链表的尾部（表示该数据是最近最常使用的）。如果未找到，则表示数据不在缓存中，需要从后端存储获取，获取后按照插入操作的流程将数据插入缓存。

以下是用 Python 实现基于链表的 MRU 缓存的代码示例：

class DoubleListNode:
    def __init__(self, key, value):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None


class MRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.head = DoubleListNode(0, 0)
        self.tail = DoubleListNode(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0

    def move_to_tail(self, node):
        self.remove(node)
        self.add_to_tail(node)

    def add_to_tail(self, node):
        node.prev = self.tail.prev
        node.next = self.tail
        self.tail.prev.next = node
        self.tail.prev = node

    def remove(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def remove_head(self):
        if self.head.next == self.tail:
            return
        node = self.head.next
        self.remove(node)
        return node

    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self.move_to_tail(node)
            return node.value
        return -1

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self.move_to_tail(node)
        else:
            new_node = DoubleListNode(key, value)
            self.cache[key] = new_node
            self.add_to_tail(new_node)
            self.size += 1
            if self.size > self.capacity:
                removed = self.remove_head()
                self.cache.pop(removed.key)
                self.size -= 1

基于队列的实现
- 数据结构设计：可以使用队列结合哈希表来实现 MRU 策略。队列用于记录数据的访问顺序，哈希表用于快速判断数据是否在队列中。队列可以使用普通的数组队列或更高效的双端队列（deque）。哈希表同样以数据的键作为索引，值可以是数据在队列中的位置信息。
- 操作流程：
  - 插入操作：当有新数据要插入缓存时，如果缓存已满，从队列头部取出数据（队列头部为最近最常使用的数据），并从哈希表中移除对应的键值对。然后将新数据添加到队列尾部，并在哈希表中添加新键值对，记录新数据在队列中的位置。
  - 访问操作：当访问缓存中的数据时，通过哈希表找到数据在队列中的位置。如果找到，将该数据从队列中移除，并添加到队列尾部。如果未找到，则从后端存储获取数据，获取后将数据添加到队列尾部，并在哈希表中记录其位置。

以下是用 Python 实现基于队列的 MRU 缓存的代码示例：

from collections import deque


class MRUQueueCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}
        self.queue = deque()

    def get(self, key):
        if key in self.cache:
            self.queue.remove(key)
            self.queue.append(key)
            return self.cache[key]
        return -1

    def put(self, key, value):
        if key in self.cache:
            self.queue.remove(key)
        elif len(self.queue) == self.capacity:
            removed_key = self.queue.popleft()
            self.cache.pop(removed_key)
        self.queue.append(key)
        self.cache[key] = value

MRU 策略性能分析

时间复杂度：
- 基于链表的实现：插入操作、访问操作在理想情况下，通过哈希表定位节点的时间复杂度为 O(1)，在链表中移动节点等操作的时间复杂度也为 O(1)，所以整体时间复杂度为 O(1)。但在极端情况下，如果哈希表发生严重冲突，时间复杂度可能会退化为 O(n)，n 为链表长度。
- 基于队列的实现：插入操作和访问操作，在哈希表查找和更新位置信息时间复杂度为 O(1)，在队列中添加、移除元素时间复杂度也为 O(1)，总体时间复杂度一般为 O(1)。同样，哈希表冲突可能导致时间复杂度上升。
空间复杂度：
- 基于链表的实现：除了缓存数据本身占用的空间，双向链表节点额外占用空间，每个节点除了数据外还需要存储前驱和后继指针，空间复杂度为 O(n)，n 为缓存中数据项数量。哈希表也需要占用一定空间存储键值对，空间复杂度同样为 O(n)。
- 基于队列的实现：队列本身占用空间存储数据键，空间复杂度为 O(n)，哈希表用于存储键值对和位置信息，空间复杂度也为 O(n)。

MRU 策略与其他策略对比

与 LRU 对比：
- 访问模式适应性：LRU 适用于数据访问具有时间局部性，即最近访问的数据在未来大概率会再次被访问的场景。例如操作系统的页面缓存，程序的局部性原理使得 LRU 策略能有效提高缓存命中率。而 MRU 适用于热点数据快速更替的场景，如前文提到的新闻资讯类应用。在这种场景下，LRU 可能会保留一些即将过期的热点数据，而 MRU 能及时淘汰它们。
- 实现复杂度：LRU 和 MRU 都可以通过双向链表结合哈希表实现，实现复杂度相近。但在基于队列的实现方式上，MRU 相对简单，因为 LRU 需要额外记录每个数据的访问时间等信息来判断是否为最近最少使用。
与 FIFO 对比：
- 淘汰逻辑：FIFO 策略按照数据进入缓存的先后顺序淘汰数据，不考虑数据的访问频率。而 MRU 根据最近的访问情况淘汰数据。例如在一个缓存系统中，FIFO 会淘汰最早进入缓存的数据，即使该数据在进入后被频繁访问。而 MRU 会淘汰最近最常使用的数据，这在某些场景下能更好地利用缓存资源。
- 缓存命中率：在一些数据访问模式不规则的场景下，FIFO 的缓存命中率可能较低，因为它不区分数据的重要性。MRU 由于考虑了数据的近期访问情况，在热点数据快速更替等场景下，可能会有更高的缓存命中率。

MRU 策略在实际项目中的应用案例

电商推荐系统缓存：在电商平台的推荐系统中，用户的浏览行为变化迅速。新的热门商品不断出现，旧的热门商品可能很快就无人问津。MRU 策略可以用于缓存推荐结果，将最近被大量用户查看的推荐结果及时淘汰，为新的推荐结果腾出空间。这样可以保证缓存中的推荐结果始终与当前的热门趋势相符，提高推荐的准确性和实时性。
游戏服务器缓存：在多人在线游戏中，玩家的游戏状态数据会不断更新。例如，玩家在游戏中的位置、任务进度等信息。游戏服务器可以使用 MRU 策略缓存这些数据，当缓存满时，淘汰最近频繁更新的玩家状态数据，因为这些数据可能是由于玩家在游戏中的频繁操作产生的，短期内再次被使用的可能性相对较低。而一些相对稳定的玩家数据，如角色创建信息等，可以在缓存中保留更长时间。

MRU 策略的优化方向

结合其他策略：可以将 MRU 策略与其他缓存替换策略结合使用。例如，先使用 MRU 策略进行初步淘汰，然后对于被 MRU 淘汰的数据，再使用 LFU 策略进行二次筛选。这样可以综合利用不同策略的优势，在不同的数据访问模式下都能提高缓存命中率。
动态调整参数：根据系统的运行情况动态调整 MRU 缓存的容量。例如，当系统负载较低时，可以适当减小缓存容量，释放更多资源给其他任务；当系统负载较高且缓存命中率较低时，增加缓存容量，以提高缓存的处理能力。同时，也可以动态调整 MRU 策略中关于数据淘汰的判定参数，以适应不同的工作负载。

在后端开发的缓存设计中，MRU 策略作为一种独特的缓存替换策略，在特定场景下有着显著的优势。通过合理的实现和优化，能够有效地提高缓存的性能，为后端系统的高效运行提供有力支持。开发人员在实际应用中，应根据具体的业务需求和数据访问模式，灵活选择和运用 MRU 策略或与其他策略相结合，以达到最佳的缓存管理效果。