Python3中的傻瓜式LRU缓存实现

没事逛freenode的时候，遇到有人说觉得Pelican运行缓慢于是profile了一下，结果发现某个字符串处理函数超级慢，而且被执行了30W次以上，于是频道里另一位哥建议用functools.lru_cache做缓存——我也不知道这是神马，于是查了一下文档，看了一下源码，发现是Python 3.2以后增加的接口。

LRU算法

想必做过服务端/后端和底层开发的同学都用过——至少是听说过。LRU是最常用的缓存算法，没有之一；全称叫“Least Recently Used”，顾名思义，就是在缓存miss 并且缓存空间已满的时候，将最久没访问过的数据删除从而腾出空间。

实际上最高效的缓存算法是基于未来的访问行为的，也就是说，该从缓存中删除的数据应该是未来最长的一段时间内不会用到的数据。但是这样的算法在实践中注定只能用在像飞机航班等本身带有时效性信息的特殊数据上，程序对其他数据的访问行为基本上是无法准确预测的。

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

说到处理器负担，因为LRU要跟踪数据的访问时间/存活时间，通常涉及查找或者哈希操作，所以需要更多处理器资源，有时候会很可观——我之前在Erlang下用ets做的LRU，相同硬件条件下CPU占用要多近30%——这当然和我写的算法比较烂也有关系XD.

functools里的LRU实现

既然是“傻瓜式”，使用上是很简单的：

from functools import lru_cache

@lru_cache(maxsize=10)
def read_template(name):
    with open('templates/{}'.format(name), 'r') as f:
        return f.read()

这里maxsize参数就是缓存大小了，如果设成None，LRU逻辑会被禁用，变成一个无限大的缓存；而如果设成0，缓存逻辑会被禁用，变成简单的调用次数统计。被修饰的函数——这里是read_template(...)——会多出几个和缓存相关的属性：

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

要注意的是，lru_cache修饰的函数必须是没有副作用的，而且最好不要返回可变（mutable）对象——道理大家应该都懂，可是大概还是会出现很多类似这样的代码：

@lru_cache(maxsize=10)
def get_template(name):
    f = open('templates/{}'.format(name), 'r')
    return f

这里的f就是个可变对象，即使调用get_template(...)的代码没有把文件关闭，缓存中的文件对象也需要seek(0)才能用了。

需要注意的lru_cache实现细节

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

对应的源码在这里