--- title: "Consistent Hashing: Mô hình tư duy 'Phòng Tủ Khóa'" description: "Cassandra biết server nào giữ data của bạn thế nào? Hướng dẫn chuyên sâu về consistent hashing, virtual node và cách cache không bị vô hiệu khi scale." pubDate: "2023-05-21" lang: "vi" slug: "consistent-hashing-distributed-systems" url: "https://hoangyell.com/vi/consistent-hashing-distributed-systems/" author: "HoangYell" translation_en: "https://hoangyell.com/consistent-hashing-distributed-systems/" categories: ["System Design"] tags: ["system-design", "distributed-systems", "hashing"] heroImage: "https://raw.githubusercontent.com/HoangGeek/store/main/webp/photo-1637028253736-ccf0e0e2da47.webp" --- Bạn có 3 cache server. Dùng `server = hash(key) % 3` để quyết định server nào lưu mỗi key. Bạn thêm server thứ 4. Giờ `hash(key) % 4` cho kết quả khác. **Mọi key đã cache đều trỏ đến server mới.** Tỷ lệ cache hit giảm từ 90% xuống gần 0%. Database sụp đổ. Đây là lý do **hashing theo modulo đơn giản bị vỡ** khi scale. Consistent Hashing là giải pháp được Redis Cluster, Cassandra, DynamoDB và mọi CDN sử dụng. *** ## Phần 1: Nền tảng (Mô hình tư duy) ### Hashing đơn giản = Phân công Tủ khóa học sinh Tưởng tượng 1,000 học sinh và 10 tủ khóa. `tủ = student_id % 10`. Đơn giản. Đều. Hoạt động hoàn hảo. **Vấn đề**: Thêm một tủ mới (server). Giờ `student_id % 11`. Hầu hết học sinh bị phân vào tủ khác. Mọi người bị khóa ra khỏi tủ cũ của mình. **Hỗn loạn toàn trường.** ### Consistent Hashing = Vòng Đồng hồ Thay vì `% số server`, hãy tưởng tượng một **vòng đồng hồ khổng lồ** từ 0 đến 360 độ (hoặc 0 đến 2^32). 1. **Đặt server lên vòng**: Hash tên mỗi server → vị trí trên vòng. 2. **Đặt key lên vòng**: Hash mỗi key → vị trí trên vòng. 3. **Tìm server**: Đi theo chiều kim đồng hồ từ vị trí key. Server đầu tiên gặp là chủ của key đó. ```markdy scene type=constellation width=1100 height=700 theme: light=doodle dark=nebula service NodeA "Server Node A (0°)" focal=true service NodeB "Server Node B (120°)" service NodeC "Server Node C (240°)" cache CacheKey "Key 'user:123' (Hash: 45°)" beat ring_lookup "Duyệt Vòng Theo Chiều Kim Đồng Hồ" { show $nodes stagger=50ms CacheKey -> NodeB "đi theo chiều kim đồng hồ -> gán vào Node B" glow NodeB color=#38bdf8 } player: playback: loop true controls: speed true speeds "0.25" fullscreen true gif true theme true interaction: zoom true pan true click_to_play true double_click_to_reset true keyboard false chrome: badge true progress none ``` **Khi thêm/xóa một server**, chỉ những key nằm giữa nó và server kế trước trên vòng bị ảnh hưởng. Mọi thứ khác vẫn yên vị. **Cách cũ**: Thêm server → ~100% key bị ánh xạ lại. **Consistent Hashing**: Thêm server → ~1/N key bị ánh xạ lại (N = số server). *** ## Phần 2: Điều tra (Virtual Nodes) Vòng đơn giản có một vấn đề: **phân phối không đều**. Do ăn may về hash, một server có thể chỉ phủ 1° và server khác phủ 180°. **Virtual Nodes** giải quyết điều này. Thay vì mỗi server có 1 vị trí, nó có **100+ vị trí** trên vòng (với các seed hash khác nhau). ``` Server vật lý: A, B, C Virtual Nodes: Vòng: A₁ B₂ C₃ A₄ B₅ C₆ A₇ B₈ C₉ A₁₀ ... (100 virtual node mỗi cái, phân bố đều) ``` Mỗi key vẫn đi theo chiều kim đồng hồ để tìm server. Nhưng giờ mỗi server vật lý xử lý một phần vòng được phân bố tốt - kể cả khi server có năng lực khác nhau (server to hơn nhận nhiều virtual node hơn). *** ## Phần 3: Chẩn đoán (Vấn đề thường gặp) | Vấn đề | Nguyên nhân | Cách sửa | |:---|:---|:---| | **Tải không đều** | Ít server, hash va chạm | Thêm virtual node (100-150 mỗi server) | | **Điểm nóng (Hot spot)** | Một key chiếm 90% traffic | Phân mảnh key: `user:123:shard_{0-9}` | | **Server hỏng, mất key** | Không có replication | Replicate sang N server theo chiều kim đồng hồ | | **Đọc cũ sau khi thay đổi topology** | Client vẫn có trạng thái ring cũ | Dùng gossip protocol (Cassandra) hoặc config tập trung (Zookeeper) | *** ## Phần 4: Giải pháp (Consistent Hashing được dùng ở đâu?) ### 1. Redis Cluster Redis Cluster dùng **hash slot** (0–16383) - một biến thể consistent hashing đơn giản hóa. ``` redis-cli cluster info redis-cli cluster nodes # Xem server nào sở hữu hash slot nào ``` ### 2. Cassandra Dùng vòng consistent hash đầy đủ với virtual node ("vnode"). Token range của mỗi node quyết định nó lưu row nào. ### 3. Load Balancer của riêng bạn (Python) ```python import hashlib from bisect import bisect_right class ConsistentHashRing: def __init__(self, servers: list, replicas: int = 150): self.ring = {} self.sorted_keys = [] for server in servers: for i in range(replicas): # Tạo 150 virtual node cho mỗi server virtual_key = f"{server}:{i}" h = int(hashlib.md5(virtual_key.encode()).hexdigest(), 16) self.ring[h] = server self.sorted_keys.append(h) self.sorted_keys.sort() def get_server(self, key: str) -> str: h = int(hashlib.md5(key.encode()).hexdigest(), 16) idx = bisect_right(self.sorted_keys, h) % len(self.sorted_keys) return self.ring[self.sorted_keys[idx]] # Cách dùng ring = ConsistentHashRing(["server-a", "server-b", "server-c"]) print(ring.get_server("user:123")) # → "server-b" print(ring.get_server("user:456")) # → "server-a" # Thêm một server mới ring2 = ConsistentHashRing(["server-a", "server-b", "server-c", "server-d"]) # Chỉ ~25% key thay đổi server! ``` *** ## Mô hình tư duy chốt hạ ``` Hashing đơn giản (% N) -> Tủ khóa học sinh. Thêm 1 tủ: mọi người mất đồ. Consistent Hashing -> Vòng Đồng hồ. Thêm server: chỉ key gần đó bị ảnh hưởng. Virtual Nodes -> Mỗi server trên vòng 150 lần. Tải được phân bổ đều. hash(key) % N -> 100% bị ánh xạ lại khi N thay đổi. Consistent Hashing -> ~1/N bị ánh xạ lại khi N thay đổi. (Cực quan trọng cho cache lớn). ``` **Khi nào cần**: * Cache phân tán (Redis Cluster, Memcached). * Database phân tán (Cassandra, DynamoDB). * Load balancing kết nối stateful (sticky session không cần lookup table).