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 đó.

1
2
3
4
5
6
7

        0° (Server A)
       /
360°--Vòng--90°
       \        (Server B)
       180° (Server C)
        
Key "user:123" hash ra 45° → Đi theo chiều kim đồng hồ → Server đầu tiên = Server A (tại 0°/360°, vòng lại)

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

1
2
3
4

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)

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.

1
2

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)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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ạ

1
2
3
4
5
6

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