Trong thế giới lập trình và tối ưu hệ thống, caching là một yếu tố then chốt để cải thiện performance. Trong rất nhiều thuật toán caching, Least Recently Used (LRU) chính là một trong nhiều cơ chế được sử dụng nhiều và rộng rãi nhất.
LRU là cái chi?
Hồi làm việc ở công ty cũ (giờ ở công ty mới thì không có, hơi bất tiện… ) tôi được cấp một tủ đựng đồ với 3 ngăn nhỏ và tôi phải sắp xếp đồ dùng sao cho dễ lấy nhất. Mỗi khi xách thêm đồ lên, hoặc mua thêm gì đó, tôi sẽ cất những đồ lâu không dùng nhất đi để nhường chỗ. LRU chính là như vậy, nó ưu tiên giữ lại những dữ liệu được truy cập gần đây nhất, đảm bảo những thông tin quan trọng và thường dùng luôn sẵn sàng trong tầm tay.
LRU quản lý một bộ nhớ cache cố định và sắp xếp dữ liệu dựa theo tần suất truy cập. Mỗi lần truy cập, dữ liệu đó sẽ được đánh dấu là “mới nhất”. Nếu bộ nhớ đầy hoặc vượt ngưỡng được define trước đó và có dữ liệu mới cần thêm vào, LRU sẽ loại bỏ dữ liệu ít được dùng nhất để dọn chỗ.
Code tí ví dụ bằng Python
class LRUCache:
def __init__(self, capacity):
self.capacity = capacity
self.cache = {}
self.order = []
def get(self, key):
if key in self.cache:
# Đưa key vừa truy cập lên cuối để đánh dấu mới nhất
self.order.remove(key)
self.order.append(key)
return self.cache[key]
return -1
def put(self, key, value):
if key in self.cache:
# Cập nhật value và đưa key lên cuối
self.cache[key] = value
self.order.remove(key)
self.order.append(key)
else:
if len(self.cache) >= self.capacity:
# Xóa key ít dùng nhất (phần tử đầu tiên trong order)
lru_key = self.order.pop(0)
del self.cache[lru_key]
self.cache[key] = value
self.order.append(key)
Đoạn code đơn giản này sử dụng một dictionary “cache” để lưu trữ các cặp key-value và một list “order” để quản lý thứ tự truy cập. Phương thức get tìm kiếm giá trị dựa trên key, còn phương thức put thêm hoặc cập nhật dữ liệu trong cache.
Ứng dụng của LRU trong thực tế:
LRU được sử dụng rộng rãi trong các hệ thống cơ sở dữ liệu, web server, hệ điều hành và nhiều nơi khác cần truy cập dữ liệu nhanh chóng và hiệu quả. Ví dụ, trình duyệt web sử dụng LRU để lưu trữ các trang web đã truy cập gần đây, giúp việc truy cập lại nhanh hơn đáng kể.
Ở đây, tôi sẽ lấy một ví dụ về LRU mà tôi đã sử dụng trong thực tế như sau: Trong một trang web thương mại điện tử, tôi sử dụng LRU để cache danh sách các chương trình khuyến mại đang diễn ra. Khi khách hàng truy cập trang web, hệ thống sẽ kiểm tra xem chương trình khuyến mại mà khách hàng đang quan tâm có được lưu trữ trong bộ nhớ cache hay không. Nếu có, hệ thống sẽ trả về chương trình khuyến mại từ bộ nhớ cache mà không cần query database. Điều này giúp cải thiện thời gian phản hồi của trang web và giảm tải cho cơ sở dữ liệu.
Ngoài ra, LRU cũng có thể được sử dụng để cache các thông tin chi tiết về từng chương trình khuyến mại, chẳng hạn như nội dung chương trình, thời gian bắt đầu và kết thúc, điều kiện áp dụng, v.v. Điều này giúp hệ thống truy xuất thông tin về chương trình khuyến mại nhanh chóng và chính xác hơn.
Vậy nó có nhược điểm gì không?
- Không hiệu quả trong các trường hợp dữ liệu được truy cập theo thứ tự ngẫu nhiên: Trong trường hợp này, LRU có thể loại bỏ những dữ liệu quan trọng và thường dùng, khiến hệ thống phải truy cập dữ liệu từ database, khiến việc caching không có hiệu quả. Như ví dụ ở trên, LRU chỉ hiệu quả khi sàn e-commerce đó có nhiều promotions và có một nhóm promotions hot – được người dùng sử dụng, kiểm tra rất nhiều. Tất nhiên là trong trường hợp lượng cache hạn hẹp, thông thường, với một sàn e-commerce thì lượng dữ liệu promotions sẽ không quá lớn, LRU trên memory có thể chứa được.
- Có thể dẫn đến việc truy cập dữ liệu cũ: Nếu dữ liệu mới được truy cập nhiều lần, dữ liệu sẽ nằm rất lâu trong cache, điều đó sẽ làm dữ liệu bị outdate. Trường hợp này người lập trình viên cần implement thêm các cơ chế khác như expired time, refresh cache v.v để giữ cho data trong cache luôn được cập nhật.
Túm lại:
LRU là một giải pháp mạnh mẽ và hiệu quả để quản lý bộ nhớ cache hạn chế, ưu tiên dữ liệu thường xuyên được sử dụng. Sự đơn giản và tính hiệu quả của LRU khiến nó trở thành một nền tảng quan trọng trong việc tối ưu hóa hiệu suất hệ thống trong nhiều lĩnh vực khác nhau. Tuy nhiên, LRU cũng có những nhược điểm riêng của nó, điều đó đòi hỏi người lập trình viên phải hiểu rõ được yêu cầu, yếu tố cần thiết của sản phẩm để đưa ra quyết định đúng đắn.
