Algorithms & Applications
Trang chủ / Module 13
⚙️ Module 13 / 14 · 1 tuần

Á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.

Rate LimitingLRU Cache
📌 Vì sao module này quan trọng

Đâ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 LRU Cache & Rate Limiter hoàn chỉ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

✅ 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