已发布·持续改进
LRU 缓存 指南 · 1/6
本章目前仅提供英文版。
A cache keeps copies of data that is expensive to fetch or compute in a smaller, faster place, so that the next request for the same data can be answered quickly. Because the fast place is small, a cache eventually fills up and has to decide what to throw away. The rule it uses is called an eviction policy, and LRU (least recently used) is the most widely taught and used one. This chapter introduces the vocabulary, compares LRU with other policies and explains when LRU is a good fit.
Every cache sits in front of something slower: a CPU cache in front of main memory, the OS page cache in front of the disk, Redis in front of a database, a CDN in front of an origin server. A lookup that finds the data is a hit; a lookup that has to go to the slow source is a miss. The fraction of lookups that hit is the hit ratio, and it is the number that decides whether a cache is worth having.
The simplest cache is a dictionary used for memoization. It never forgets anything, so it is only safe when the set of possible keys is small.
import time
slow_calls = 0
def slow_square(n):
global slow_calls
slow_calls += 1
time.sleep(0.01) # pretend this is a network call
return n * n
memo = {}
def cached_square(n):
if n in memo: # hit
return memo[n]
memo[n] = slow_square(n) # miss: compute and remember
return memo[n]
for n in [3, 4, 3, 3, 4, 5]:
cached_square(n)
print(slow_calls) # 3 misses, 3 hitsReal caches have a capacity: a number of entries, a number of bytes or a number of memory pages. When a new item arrives and the cache is full, one existing item must be evicted. A good policy evicts the item that is least likely to be needed again soon. Nobody knows the future, so every policy is a guess based on the past.
| Policy | Evicts | Strength | Weakness |
|---|---|---|---|
| FIFO | the oldest inserted item | trivial to implement | ignores how often or how recently an item is used |
| LRU | the item not used for the longest time | adapts to changing hot sets | a single large scan can flush the cache |
| LFU | the item used the fewest times | keeps long-term favourites | old popular items linger after they stop being used |
| TTL | items older than a fixed lifetime | bounds staleness | not a capacity policy on its own |
| Random |
| a random item |
| no bookkeeping |
| unpredictable hit ratio |
TTL (time to live) answers a different question from the others: not "what do we drop when full?" but "how long may data stay before it is considered stale?". Real systems often combine TTL with LRU or LFU.
A FIFO cache is easy to build with an ordered dictionary: insertion order is the eviction order, and lookups do not change it.
from collections import OrderedDict
class FIFOCache:
def __init__(self, capacity):
self.capacity = capacity
self.data = OrderedDict()
def get(self, key):
return self.data.get(key) # reading does not change the order
def put(self, key, value):
if key not in self.data and len(self.data) >= self.capacity:
self.data.popitem(last=False) # drop the oldest insertion
self.data[key] = value
fifo = FIFOCache(2)
fifo.put("a", 1); fifo.put("b", 2)
fifo.get("a")
fifo.put("c", 3) # evicts "a" even though it was just read
print(list(fifo.data)) # ['b', 'c']LRU relies on temporal locality: data used recently is likely to be used again soon. It keeps entries ordered by recency. Every successful get or put moves the entry to the "most recently used" end; when space is needed, the entry at the "least recently used" end is removed. Compared with FIFO, the only difference is that a read refreshes an entry. That one change makes the cache follow the current working set of a program, a user or a service.
Python ships an LRU cache as a decorator, which is the quickest way to see the policy at work.
from functools import lru_cache
@lru_cache(maxsize=2)
def load(key):
print("loading", key)
return key.upper()
load("a"); load("b")
load("a") # hit: "a" becomes most recent
load("c") # full: evicts "b", the least recently used
load("b") # miss again: prints "loading b"
print(load.cache_info()) # CacheInfo(hits=1, misses=4, maxsize=2, currsize=2)LRU works well when access is skewed toward a moving set of hot keys: user sessions, recently viewed pages, recently opened files. It does poorly in two situations. First, a sequential scan larger than the cache evicts everything and leaves only items that will not be reused. Second, if a few keys are popular over a long period but are touched less often than a stream of one-off keys, LFU or a hybrid such as 2Q, ARC or W-TinyLFU keeps them better. Many production systems therefore use LRU variants rather than textbook LRU.
0 条评论
登录 · 登录后即可发表评论。
来发表第一条评论吧。