Bộ nhớ đệm LRU (LRU cache): cách hoạt động, code và độ phức tạp

Bộ nhớ đệm LRU giải quyết vấn đề gì

Bộ nhớ đệm giữ kết quả của các thao tác chậm, như truy vấn cơ sở dữ liệu, yêu cầu web hoặc phép tính tốn kém, để các yêu cầu lặp lại được trả lời nhanh. Bộ nhớ có hạn, nên bộ đệm phải quyết định bỏ gì khi đầy. LRU đặt cược rằng dữ liệu vừa dùng gần đây sẽ sớm được dùng lại, còn dữ liệu lâu không đụng tới có lẽ sẽ không. Cược này hiệu quả với nhiều khối lượng công việc thực tế, nên LRU và các xấp xỉ của nó xuất hiện trong cache CPU, page cache của hệ điều hành, cơ sở dữ liệu, máy chủ web và CDN.

Ý tưởng: hai cấu trúc phối hợp với nhau

Ta cần hai việc phải nhanh: tìm một khóa, và biết khóa nào ít được dùng gần đây nhất. Bảng băm một mình không có thứ tự. Danh sách một mình thì tìm chậm. Kết hợp lại thì làm được cả hai:

Với get(key), tra node trong map, chuyển nó lên đầu và trả về giá trị. Với put(key, value), cập nhật hoặc tạo node ở đầu; nếu bộ đệm giờ vượt dung lượng, xóa node ở cuối và xóa khóa của nó khỏi map.

Ví dụ minh họa với dung lượng 2

Cài đặt từ đầu bằng Python

Các node sentinel đầu và đuôi loại bỏ các trường hợp đặc biệt cho danh sách rỗng: mọi node thật luôn có node đứng trước và sau.

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

Phiên bản ngắn với OrderedDict

collections.OrderedDict tự nó là bảng băm kết hợp danh sách liên kết đôi, và move_to_end cùng popitem(last=False) đều O(1). Điều đó làm nó thành lựa chọn đúng chất Python khi bạn cần một bộ nhớ đệm LRU dưới dạng đối tượng.

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']

Lưu kết quả hàm bằng functools.lru_cache

Để lưu giá trị trả về của một hàm, hãy dùng decorator functools.lru_cache. Các đối số phải băm được, vì chúng trở thành khóa của dictionary. cache_info() cho biết số hit, miss và kích thước hiện tại.

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 cho bộ đệm không giới hạn, đúng là việc functools.cache (Python 3.9 trở lên) làm. Gọi fib.cache_clear() để làm rỗng nó.

Độ phức tạp thời gian và không gian

Biến thể, lỗi và khi nào dùng LRU

• LFU (least frequently used - ít được dùng thường xuyên nhất) loại bỏ phần tử có ít lượt truy cập nhất; nó bảo vệ các phần tử phổ biến khỏi những lượt quét một lần nhưng phức tạp hơn.
• LRU xấp xỉ: các hệ thống như Redis lấy mẫu vài khóa và loại bỏ khóa cũ nhất trong đó thay vì giữ danh sách chính xác, nhờ vậy tiết kiệm bộ nhớ.
• Bộ đệm TTL cho các mục hết hạn sau một khoảng thời gian cố định, thường kết hợp với giới hạn kích thước.
• Quên chuyển mục lên đầu khi get, hoặc khi put một khóa đã tồn tại, sẽ biến LRU thành FIFO.
• Quên xóa khóa bị loại bỏ khỏi bảng băm sẽ để lại các mục treo và rò rỉ bộ nhớ.
• Chia sẻ bộ nhớ đệm LRU giữa các luồng cần khóa (lock) quanh mỗi thao tác; functools.lru_cache an toàn khi gọi từ nhiều luồng.

LRU là lựa chọn mặc định tốt khi việc dùng gần đây dự đoán được việc dùng trong tương lai. Nó hoạt động kém khi một lượt quét lớn một lần đẩy dữ liệu hay dùng ra ngoài; những khối lượng công việc như vậy hưởng lợi từ LFU hoặc các chính sách chống quét. Thiết kế bộ nhớ đệm LRU với các thao tác O(1) cũng là một trong những câu hỏi phỏng vấn lập trình phổ biến nhất, vì nó kiểm tra cả bảng băm lẫn danh sách liên kết.