title: Python3中的LRU缓存机制
subtitle: functools.lru_cache
date: 2020-12-15
author: NSX
catalog: true
tags:
- Python
- 缓存
- Cache

缓存是一种将定量数据加以保存以备迎合后续获取需求的处理方式。Python3中的functools.lru_cache 缓存机制通过哈希链表保存最近query对应的topic，命中后直接返回。

哈希链表是哈希表和链表的结合体，哈希表的每一个位置存放的实际上是一个链表的节点，这些节点又通过首尾相连形成双向链表。

前言

先来一个简单的例子以了解缓存机制的概念：

  1. # -*- coding: utf-8 -*-
  3. import random
  4. import datetime
  7. class MyCache:
  8.     """缓存类"""
  10.     def __init__(self):
  11.         # 用字典结构以 kv 的形式缓存数据
  12.         self.cache = {}
  13.         # 限制缓存的大小，因为缓存的空间有限
  14.         # 所以当缓存太大时，需要将旧的缓存舍弃掉
  15.         self.max_cache_size = 10
  17.     def __contains__(self, key):
  18.         """根据该键是否存在于缓存当中返回 True 或者 False"""
  19.         return key in self.cache
  21.     def get(self, key):
  22.         """从缓存中获取数据"""
  23.         data = self.cache[key]
  24.         data["date_accessed"] = datetime.datetime.now()
  25.         return data["value"]
  27.     def add(self, key, value):
  28.         """更新该缓存字典，如果缓存太大则先删除最早条目"""
  29.         if key not in self.cache and len(self.cache) >= self.max_cache_size:
  30.             self.remove_oldest()
  31.         self.cache[key] = {
  32.             'date_accessed': datetime.datetime.now(),
  33.             'value': value
  34.         }
  36.     def remove_oldest(self):
  37.         """删除具备最早访问日期的输入数据"""
  38.         oldest_entry = None
  40.         for key in self.cache:
  41.             if oldest_entry is None:
  42.                 oldest_entry = key
  43.                 continue
  44.             curr_entry_date = self.cache[key]['date_accessed']
  45.             oldest_entry_date = self.cache[oldest_entry]['date_accessed']
  46.             if curr_entry_date < oldest_entry_date:
  47.                 oldest_entry = key
  49.         self.cache.pop(oldest_entry)
  51.     @property
  52.     def size(self):
  53.         """返回缓存容量大小"""
  54.         return len(self.cache)
  57. if __name__ == '__main__':
  58.     # 测试缓存功能
  59.     cache = MyCache()
  60.     cache.add("test", sum(range(100000)))
  61.     assert cache.get("test") == cache.get("test")
  63.     keys = [
  64.         'red', 'fox', 'fence', 'junk', 'other', 'alpha', 'bravo', 'cal',
  65.         'devo', 'ele'
  66.     ]
  67.     s = 'abcdefghijklmnop'
  68.     for i, key in enumerate(keys):
  69.         if key in cache:
  70.             continue
  71.         else:
  72.             value = ''.join([random.choice(s) for i in range(20)])
  73.             cache.add(key, value)
  75.     assert "test" not in cache
  76.     print(cache.cache)

以上示例仅简单的展示了缓存机制的原理，通过用键值对的方式将数据放到字典中，如果下次需要取值时可以直接到字典中获取。该示例在删除旧数据时的实现并不高效，实际应用中可以用别的方式实现。

在 Python 的 3.2 版本中，引入了一个非常优雅的缓存机制，即 functool 模块中的 lru_cache 装饰器，可以直接将函数或类方法的结果缓存住，后续调用则直接返回缓存的结果。lru_cache 原型如下：

@functools.lru_cache(maxsize=None, typed=False)

使用 functools 模块的 lur_cache 装饰器，可以缓存最多 maxsize 个此函数的调用结果，从而提高程序执行的效率，特别适合于耗时的函数。参数 maxsize 为最多缓存的次数，如果为 None，则无限制，设置为 2 的幂 时，性能最佳；如果 typed=True（注意，在 functools32 中没有此参数），则不同参数类型的调用将分别缓存，例如 f(3) 和 f(3.0)。

LRU 算法介绍

LRU (Least Recently Used，最近最少使用) 算法是一种缓存淘汰策略。其根据数据的历史访问记录来进行淘汰，核心思想是，“如果数据最近被访问过，那么将来被访问的几率也更高”。该算法最初为操作系统中一种内存管理的页面置换算法，主要用于找出内存中较久时间没有使用的内存块，将其移出内存从而为新数据提供空间。其原理就如以上的简单示例。

那么问题来了，为什么LRU能提高性能？其实这个问题描述本身是错误的——LRU并不总 是能提高性能的，任何实用的缓存算法都不行。LRU基于这样一个前提：越久没被访 问的数据，以后被访问到的概率也越小。比方说，如果你的程序需要周期性地处 理不同数据，用LRU可能只会带来周期性的缓存miss从而增加处理器或者IO负担而已， 反而拖慢程序执行速度。

说到处理器负担，因为LRU要跟踪数据的访问时间/存活时间，通常涉及查找或者哈希 操作，所以需要更多处理器资源，有时候会很可观——

functools里的LRU实现

以下为一个简单的 lru_cache 的使用效果：

  1. from functools import lru_cache
  3. @lru_cache(maxsize=32)
  4. def add(x, y):
  5.     print("calculating: %s + %s" % (x, y))
  6.     return x + y
  8. print(add(1, 2))
  9. print(add(1, 2))
  10. print(add(2, 3))

@lru_cache(maxsize=32) 中的 maxsize 参数就是缓存大小了，如果设成None，LRU逻辑会被禁用，变成一个 无限大的缓存；而如果设成0，缓存逻辑会被禁用，变成简单的调用次数统计。

输出结果：

  1. calculating: 1 + 2
  2. 3
  3. 3
  4. calculating: 2 + 3
  5. 5

从结果可以看出，当第二次调用 add(1, 2) 时，并没有真正执行函数体，而是直接返回缓存的结果。

还有什么需要注意的？

  1. 目前的lru_cache是纯Python实现的。
  2. 底层数据结构是普通的list和dict. list用于实现LRU链表，dict用于 查找已缓存的数据。在缓存已满的情况下，每次调用被缓存的函数时，都要进行 两次字典查找操作和20次以内的列表访问。
  3. 对缓存的所有访问都是加了锁的，所以可以在多线程环境下使用。

  4. 被 lru_cache 装饰的函数会有 cache_clear 和 cache_info 两个方法，分别用于清除缓存和查看缓存信息。 

    1. >>> add.cache_info()          # 缓存信息
    2. CacheInfo(hits=0, misses=0, maxsize=10, currsize=0)
    3. >>> add.cache_clear()         # 清除所有缓存内容
    4. >>> add.__wrapped__           # 真正的 read_template 函数
    5. <function add at 0x7f9d0e9766a8>
    6. >>>


    返回访问数（hits）、未访问数（misses）和当前缓存使用量（currsize）、最大容量（maxsize）

  5. 缓存的使用场景：

    • 在缓存期内，数据不会更改。
    • 函数将始终为相同的参数返回相同的值（因此时间和随机对缓存没有意义）。
    • 函数没有副作用。如果缓存被访问，则永远不会调用该函数，因此请确保不更改其中的任何状态。
    • 函数不返回不同的可变对象。例如，返回列表的函数不适合缓存，因为将要缓存的是对列表的引用，而不是列表内容（实际使用时，缓存的可变对象内容正确，不知道为啥？）

参考

Python 缓存机制与 functools.lru_cache

Python3中的傻瓜式LRU缓存实现

如何让Python程序轻松加速，正确方法详解