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:
- Tìm kiếm theo key - O(1)
- 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:
- HashMap tìm node trong O(1)
- Move node lên đầu linked list (xóa khỏi vị trí cũ, thêm vào đầu)
- 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