没事逛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实现

既然是“傻瓜式”,使用上是很简单的:

1
2
3
4
5
6
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(...)——会多出几个和缓存相关的属性:

1
2
3
4
5
6
>>> 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)对象——道理大家应该都懂,可是大概还是会出现很多类似这样的 代码:

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

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

需要注意的lru_cache实现细节

  1. 目前的lru_cache是纯Python实现的。

  2. 底层数据结构是普通的listdict. list用于实现LRU链表,dict用于 查找已缓存的数据。在缓存已满的情况下,每次调用被缓存的函数时,都要进行 两次字典查找操作和20次以内的列表访问。

  3. 对缓存的所有访问都是加了锁的,所以可以在多线程环境下使用。

对应的源码在这里