Blog - Trang 1

LRU Cache là gì?

LRU (Least Recently Used) là thuật toán loại bỏ dữ liệu ít được sử dụng gần đây nhất khi bộ nhớ cache đầy.

Use cases thực tế

1. Browser Cache

Khi bạn lướt web, trình duyệt lưu trữ các tài nguyên (JS, CSS, images). Khi cache đầy, LRU quyết định xóa resource nào không còn cần thiết.

2. Database Query Cache

MySQL và PostgreSQL dùng LRU để cache kết quả truy vấn, giúp truy vấn lặp lại nhanh hơn đáng kể.

3. Redis Memory Management

Khi maxmemory đạt giới hạn, Redis dùng LRU policy để evict keys:

maxmemory 256mb
maxmemory-policy allkeys-lru
4. Operating System Page Cache

OS dùng LRU để quyết định page nào giữ trong RAM, page nào swap ra disk.

Thuật toán đằng sau

Tại sao cần HashMap + Doubly Linked List?

Để implement LRU cache hiệu quả, chúng ta cần 2 operations chính:

  1. Tìm kiếm theo key - O(1)
  2. Xác định và xóa item ít dùng nhất - O(1)

Nếu chỉ dùng 1 cấu trúc dữ liệu:

Cấu trúc get(key) evict LRU
Array/List O(n) O(1)
HashMap O(1) O(n)
Linked List O(n) O(1)

=> HashMap + Doubly Linked List cho ta O(1) cho cả 2 operations!

Cách hoạt động
  • HashMap: Map key -> node trong linked list (tìm kiếm nhanh)
  • Doubly Linked List: Lưu thứ tự sử dụng, node gần đầu = mới dùng, gần đuôi = cũ nhất

Khi access một key:

  1. HashMap tìm node trong O(1)
  2. Move node lên đầu linked list (xóa khỏi vị trí cũ, thêm vào đầu)
  3. Khi cache đầy, xóa node cuối cùng (tail.prev)
Implementation
class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = {}  # key -> node
        self.head = Node()  # dummy head
        self.tail = Node()  # dummy tail
        self.head.next = self.tail
        self.tail.prev = self.head

    def get(self, key):
        if key in self.cache:
            node = self.cache[key]
            self._move_to_front(node)
            return node.value
        return -1

    def put(self, key, value):
        if key in self.cache:
            node = self.cache[key]
            node.value = value
            self._move_to_front(node)
        else:
            node = Node(key, value)
            self.cache[key] = node
            self._add_to_front(node)
            if len(self.cache) > self.capacity:
                lru = self.tail.prev
                self._remove(lru)
                del self.cache[lru.key]

    def _move_to_front(self, node):
        self._remove(node)
        self._add_to_front(node)

Độ phức tạp: O(1) cho cả get và put

Cách 2: Ordered Dict (Python)
from collections import OrderedDict

class LRUCache:
    def __init__(self, capacity):
        self.capacity = capacity
        self.cache = OrderedDict()

    def get(self, key):
        if key in self.cache:
            self.cache.move_to_end(key)
            return self.cache[key]
        return -1

    def put(self, key, value):
        if key in self.cache:
            self.cache.move_to_end(key)
        self.cache[key] = value
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)

So sánh các variant

Algorithm Pros Cons
LRU Tối ưu cho temporal locality Overhead cao
LFU Tối ưu cho frequency Không adapt được với pattern thay đổi
FIFO Đơn giản, nhanh Không consider usage
Random Rất đơn giản Không predict được

Khi nào dùng LRU?

  • Session data: User sessions, shopping cart
  • API response cache: Kết quả API không thay đổi thường xuyên
  • Pagination cache: Cache các trang đã duyệt
  • Computation cache: Kết quả tính toán nặng
Hoàng Đức Khải
o3, Tháng 3, 2026, 6:53 7