LRUキャッシュとは？仕組み・コード・計算量を解説

LRUキャッシュが解決する問題

キャッシュは、データベースのクエリ、Webリクエスト、重い計算のような遅い処理の結果を保存し、同じリクエストにすばやく答えられるようにします。メモリには限りがあるため、キャッシュは満杯になったときに何を捨てるかを決めなければなりません。LRUは、最近使われたデータはすぐにまた使われ、長い間触られていないデータはおそらく使われない、という賭けをします。この賭けは多くの実際のワークロードでうまくいくので、LRUとその近似は、CPUキャッシュ、OSのページキャッシュ、データベース、Webサーバー、CDNに登場します。

考え方：2つの構造が協力する

速くしたいことが2つあります。キーを見つけることと、どのキーが最も長く使われていないかを知ることです。ハッシュマップだけでは順序がありません。リストだけでは検索が遅くなります。2つを組み合わせれば、両方を実現できます。

get(key)では、マップでノードを検索し、先頭に移動して、その値を返します。put(key, value)では、ノードを更新または新規作成して先頭に置きます。キャッシュが容量を超えたら、末尾のノードを削除し、そのキーをマップからも削除します。

具体例：容量2の場合

ゼロから作るPython実装

番兵（sentinel）として先頭ノードと末尾ノードを置くと、空のリストの特殊ケースがなくなります。実データのノードは、必ず前後にノードを持つからです。

class Node:
    __slots__ = ("key", "value", "prev", "next")

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

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.map = {}
        self.head, self.tail = Node(), Node()   # sentinels
        self.head.next, self.tail.prev = self.tail, self.head

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

    def _push_front(self, node):
        node.prev, node.next = self.head, self.head.next
        self.head.next.prev = node
        self.head.next = node

    def get(self, key):
        node = self.map.get(key)
        if node is None:
            return None
        self._unlink(node)
        self._push_front(node)
        return node.value

    def put(self, key, value):
        if key in self.map:
            self._unlink(self.map[key])
        node = self.map[key] = Node(key, value)
        self._push_front(node)
        if len(self.map) > self.capacity:
            lru = self.tail.prev
            self._unlink(lru)
            del self.map[lru.key]

cache = LRUCache(2)
cache.put(1, "a")
cache.put(2, "b")
print(cache.get(1))   # a
cache.put(3, "c")     # evicts key 2
print(cache.get(2))   # None
cache.put(1, "A")
cache.put(4, "d")     # evicts key 3
print(cache.get(3), cache.get(1), cache.get(4))  # None A d

OrderedDictを使った短い版

collections.OrderedDictは、それ自体がハッシュマップと双方向連結リストの組み合わせで、move_to_endとpopitem(last=False)はO(1)です。このため、オブジェクトとしてLRUキャッシュが必要なときの、Pythonらしい選択になります。

from collections import OrderedDict

class LRU:
    def __init__(self, capacity):
        self.capacity = capacity
        self.data = OrderedDict()

    def get(self, key):
        if key not in self.data:
            return None
        self.data.move_to_end(key)          # mark as most recent
        return self.data[key]

    def put(self, key, value):
        self.data[key] = value
        self.data.move_to_end(key)
        if len(self.data) > self.capacity:
            self.data.popitem(last=False)   # drop least recent

c = LRU(2)
c.put("x", 1)
c.put("y", 2)
c.get("x")
c.put("z", 3)
print(list(c.data))  # ['x', 'z']

functools.lru_cacheで関数の結果をキャッシュする

関数の戻り値をキャッシュするには、functools.lru_cacheデコレータを使います。引数は辞書のキーになるため、ハッシュ可能でなければなりません。cache_info()で、ヒット数、ミス数、現在のサイズが分かります。

from functools import lru_cache

@lru_cache(maxsize=128)
def fib(n):
    return n if n < 2 else fib(n - 1) + fib(n - 2)

print(fib(80))           # 23416728348467685
print(fib.cache_info())
# CacheInfo(hits=78, misses=81, maxsize=128, currsize=81)

maxsize=Noneにすると上限のないキャッシュになります。functools.cache（Python 3.9以降）がこれに当たります。fib.cache_clear()を呼ぶと、キャッシュが空になります。

時間計算量と空間計算量

変種、間違い、LRUを使う場面

• LFU（Least Frequently Used）は、アクセス回数が最も少ない要素を追い出します。1回限りのスキャンから人気のある要素を守れますが、より複雑です。
• 近似LRU：Redisのようなシステムは、正確なリストを保持する代わりに、いくつかのキーをサンプリングし、その中で最も古いものを追い出します。メモリを節約できます。
• TTLキャッシュは、一定時間が過ぎたエントリを期限切れにします。サイズの上限と組み合わせることが多いです。
• getのとき、または既存のキーのputのときに、エントリを先頭に移動し忘れると、LRUがFIFOになってしまいます。
• 追い出したキーをハッシュマップから削除し忘れると、宙に浮いたエントリが残り、メモリリークになります。
• LRUキャッシュをスレッド間で共有するには、各操作をロックで囲む必要があります。functools.lru_cacheは、複数のスレッドから呼んでも安全です。

最近の使用が将来の使用を予測できるなら、LRUは良いデフォルトです。大きな1回限りのスキャンで、頻繁に使われるデータが押し出されると、性能が悪くなります。そのようなワークロードには、LFUやスキャン耐性のあるポリシーが向いています。O(1)の操作を持つLRUキャッシュの設計は、ハッシュマップと連結リストを同時に試せるため、コーディング面接で最もよく出る問題の1つでもあります。