Áp dụng Thuật toán vào Hệ thống Thực tế
Tổng hợp toàn bộ khoá học thành các thành phần hệ thống thực tế: LRU Cache, Rate Limiter, và Load Balancing algorithm — nối trực tiếp khoá Architecture & DevOps.
Đây là module cầu nối trực tiếp nhất giữa kiến thức thuật toán "thuần tuý" và công việc kỹ sư backend/ hệ thống hàng ngày — mọi thành phần hạ tầng bạn đã dùng ở các khoá Architecture/DevOps/Docker đều được xây dựng từ chính các cấu trúc dữ liệu và thuật toán đã học trong khoá này.
🎯 Mục tiêu học tập
- Triển khai LRU Cache từ đầu bằng Hash Table + Doubly Linked List
- Triển khai các thuật toán Rate Limiting phổ biến: Token Bucket, Sliding Window
- Hiểu thuật toán bên dưới Load Balancing đã học ở khoá Architecture qua góc nhìn cấu trúc dữ liệu
- Nhận diện được thuật toán/cấu trúc dữ liệu phù hợp khi thiết kế 1 thành phần hệ thống mới
LRU Cache — Hash Table + Doubly Linked List
LRU (Least Recently Used) Cache cần 2 thao tác O(1): get(key) và
put(key, value), và khi cache đầy, loại bỏ đúng phần tử lâu chưa được dùng nhất.
Không cấu trúc dữ liệu đơn lẻ nào (Module 2-5) làm được cả 2 việc này hiệu quả — lời giải kinh điển kết
hợp Hash Table (tra cứu O(1) — Module 4) với Doubly Linked List (di
chuyển node lên đầu O(1), xoá node cuối O(1) — mở rộng của Linked List, Module 2):
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> node, tra cứu O(1)
self.head = self.tail = None # doubly linked list theo thứ tự dùng gần đây nhất
def get(self, key):
if key not in self.cache:
return -1
self._move_to_front(key) # dùng xong -> đưa lên đầu (gần đây nhất)
return self.cache[key].value
def put(self, key, value):
if key in self.cache:
self.cache[key].value = value
self._move_to_front(key)
else:
if len(self.cache) >= self.capacity:
self._remove_tail() # xoá node lâu chưa dùng nhất (cuối list)
self._add_to_front(key, value)
Đây chính xác là cách OrderedDict/LinkedHashMap trong nhiều ngôn ngữ triển khai LRU bên
dưới, và là nguyên lý cache eviction phổ biến nhất trong thực tế (Redis hỗ trợ policy allkeys-lru
sẵn) — liên hệ trực tiếp chiến lược Caching đã học ở khoá Architecture Module 7.
Rate Limiting — Token Bucket & Sliding Window
# Token Bucket — mỗi request tiêu 1 token, token được "nạp lại" theo thời gian
class TokenBucket:
def __init__(self, capacity: int, refill_rate: float):
self.capacity = capacity
self.tokens = capacity
self.refill_rate = refill_rate # token/giây
self.last_refill = time.time()
def allow_request(self) -> bool:
now = time.time()
elapsed = now - self.last_refill
self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
self.last_refill = now
if self.tokens >= 1:
self.tokens -= 1
return True
return False
Token Bucket cho phép "burst" (dùng dồn nhiều token tích luỹ cùng lúc) trong khi vẫn giới hạn tốc độ trung bình dài hạn — phù hợp khi traffic tự nhiên có tính "dồn cục". Sliding Window (dùng Queue lưu timestamp các request gần nhất — Module 2, loại bỏ timestamp cũ hơn cửa sổ thời gian) chính xác hơn về mặt giới hạn tức thời nhưng tốn bộ nhớ hơn theo số request. Đây là 2 thuật toán đứng sau mọi hệ thống rate limiting bạn đã dùng ở khoá AI Engineer (Module 10) và Architecture (Module 9, phần Circuit Breaker liên quan).
Load Balancing dưới góc nhìn Thuật toán
Nhìn lại các thuật toán Load Balancing đã học ở khoá Architecture (Module 7) qua lăng kính thuật toán vừa học:
- Round Robin: đơn giản là 1 con trỏ (index) quay vòng qua danh sách server — O(1) mỗi lần chọn.
- Least Connections: cần biết nhanh "server nào đang có ít connection nhất" — chính là bài toán Priority Queue (Module 5)! Dùng Min-Heap theo số connection hiện tại, luôn lấy server ở đỉnh heap.
- Consistent Hashing: đã học chi tiết ở Module 4 — chính là thuật toán chọn server dựa trên vị trí trên hash ring.
Nhận ra được các thành phần hạ tầng quen thuộc thực chất là "bài toán thuật toán mặc áo khoác hệ thống" chính là mục tiêu cốt lõi của module này — và của cả khoá học.
🏋️ Bài tập thực hành
Triển khai đầy đủ LRU Cache với get/put đều O(1) thật sự (không dùng cấu trúc có sẵn của ngôn ngữ để "ăn gian" — tự viết Doubly Linked List). Triển khai cả Token Bucket và Sliding Window rate limiter, viết test case mô phỏng traffic có burst để so sánh hành vi khác nhau giữa 2 thuật toán. Tích hợp LRU Cache vào 1 API endpoint thật (từ khoá AI Engineer hoặc Docker) để cache kết quả truy vấn tốn kém.
📚 Tài nguyên học tập
-
Redis — LRU eviction policiesTài liệu chính thức các chính sách eviction của Redis, bao gồm LRUDocs
-
Cloudflare — Rate limiting algorithmsBài viết kỹ thuật về các thuật toán rate limiting thực tếBài viết
✅ Tự đánh giá hoàn thành
- Triển khai đúng LRU Cache với get/put O(1) thật sự
- Triển khai được cả Token Bucket và Sliding Window rate limiter
- Giải thích được thuật toán bên dưới Least Connections load balancing
- Nhận diện lại được các thành phần hạ tầng quen thuộc dưới góc nhìn cấu trúc dữ liệu/thuật toán