Consistent hashing — thêm/bớt node ít xáo trộn

TL;DR: Modulo hashing thông thường (hash(key) % N) buộc gần như toàn bộ key phải remap khi N thay đổi. Consistent hashing giải quyết bằng cách chiếu cả key lẫn node lên một vòng tròn (ring) có không gian hash cố định; key thuộc về node đầu tiên gặp theo chiều kim đồng hồ. Thêm hoặc bớt một node chỉ ảnh hưởng đến ~K/N key thay vì toàn bộ K key. Virtual node (mỗi node vật lý giữ nhiều điểm trên ring) san đều tải và xử lý rebalance khi node chết. Đây là nền tảng của Amazon Dynamo, Apache Cassandra, và nhiều CDN.

Bạn đang thiết kế cache layer cho một trang thương mại điện tử phục vụ 50 triệu request/ngày. Cache cluster ban đầu có 4 node. Khi traffic tăng đột biến dịp sale, team muốn thêm node 5 — nhưng cách thêm node xác định liệu có xảy ra "cache stampede" làm sập hệ thống hay không. Bài này giải thích tại sao cách thêm node quan trọng hơn số node.

1. Vấn đề của modulo hashing

Cách đơn giản nhất để phân phối K key vào N node là: node = hash(key) % N. Với N=4:

Hoạt động tốt khi N cố định. Nhưng khi team thêm node thứ 5 (N trở thành 5):

• "user:1001": hash % 5 = 3 → vẫn node3 (may mắn)
• "order:555": hash % 5 = 3 → đổi từ node0 sang node3 (cache miss!)
• "cart:888": hash % 5 = 1 → đổi từ node3 sang node1 (cache miss!)

Phân tích tổng quát: khi N đổi thành N+1, xác suất hash(key) % N = hash(key) % (N+1) rất thấp — trung bình khoảng N/(N+1) key phải remap, tức ~80% khi N=4. Với 50 triệu key trong cache, 40 triệu request đột ngột đánh thẳng vào database — đây là cache stampede.

2. Consistent hashing — ánh xạ lên vòng tròn

Ý tưởng cốt lõi: thay vì ánh xạ key vào một trong N bucket cố định, ta ánh xạ cả key lẫn node lên một không gian hash vòng tròn (thường là [0, 2^32-1] hoặc [0, 2^64-1]).

Gọi không gian này là ring. Cả key và node identifier đều được hash vào ring:

• Node được đặt tại vị trí hash(node_id) trên ring.
• Key k thuộc về node đầu tiên theo chiều kim đồng hồ từ vị trí hash(k).

flowchart LR
    subgraph Ring["Vòng tròn hash (0 → 2^32-1)"]
        direction TB
        N0(["Node A\n(vị trí 12°)"])
        N1(["Node B\n(vị trí 120°)"])
        N2(["Node C\n(vị trí 240°)"])
        K1["key1\n(hash=15°)"]
        K2["key2\n(hash=130°)"]
        K3["key3\n(hash=250°)"]
    end
    K1 -->|"→ Node A"| N0
    K2 -->|"→ Node C"| N2
    K3 -->|"→ Node A\n(wrap around)"| N0

Khi thêm Node D tại vị trí 200° trên ring, chỉ key nằm trong cung từ 120° đến 200° (tức vùng vừa được Node D "phủ") cần chuyển từ Node C sang Node D. Mọi key khác không bị ảnh hưởng.

Khi bớt Node B (tại 120°), chỉ key của Node B chuyển sang node kế tiếp theo chiều kim đồng hồ (Node C). Phần còn lại của ring bất biến.

3. Pseudocode — cấu trúc dữ liệu ring

Ring cần hỗ trợ hai thao tác hiệu quả: (1) thêm/bớt node, (2) tra node chủ của key. Cả hai đều thực hiện tốt với sorted array hoặc balanced BST lưu các vị trí trên ring.

-- Khởi tạo ring rỗng
function initRing():
    ring <- SortedMap()        -- position -> node_id
    return ring

-- Thêm một node vật lý vào ring
function addNode(ring, node_id):
    pos <- hash(node_id) mod RING_SIZE    -- vị trí trên ring
    ring.insert(pos, node_id)
    -- Kết quả: key trong cung (predecessor(pos), pos] chuyển sang node_id

-- Bớt một node vật lý
function removeNode(ring, node_id):
    pos <- hash(node_id) mod RING_SIZE
    ring.delete(pos)
    -- Kết quả: key của node_id chuyển sang successor(pos)

-- Tra node chủ của key
function lookup(ring, key):
    pos <- hash(key) mod RING_SIZE
    successor <- ring.ceilingEntry(pos)   -- node đầu tiên >= pos
    if successor = null:
        return ring.firstEntry().node_id   -- wrap around về đầu ring
    return successor.node_id
// Time: O(log N) mỗi thao tác  Space: O(N)

ceilingEntry(pos) trả về entry nhỏ nhất không nhỏ hơn pos — đây là thao tác "tìm successor" trên sorted map, O(log N) với balanced BST.

3.1 Phân tích số key bị ảnh hưởng

Với K key phân phối đều và N node, mỗi node giữ trung bình K/N key. Khi thêm node mới (N → N+1), nó "chiếm" cung từ predecessor đến vị trí của nó — trung bình 1/(N+1) tổng số key (ring chia đều thành N+1 phần, mỗi phần chiếm 1/(N+1)). Xấp xỉ thực tế: ~K/N key dời (vì các node hiện tại giữ K/N, node mới "lấy" từ người hàng xóm), nhưng con số chính xác là K/(N+1). So với modulo hashing remap ~N/(N+1) ≈ 83% key (với N=5), consistent hashing chỉ remap ~1/(N+1) ≈ 17%.

4. Virtual node — cân bằng tải và xử lý heterogeneous cluster

Ring thuần túy có hai vấn đề:

1. Phân bố không đều: hash function không đảm bảo N node chia đều ring thành N cung bằng nhau — một node có thể giữ 30%, node khác chỉ giữ 5%.
2. Hot spot khi node chết: khi Node B chết, toàn bộ tải của nó đổ về đúng một node kế tiếp thay vì trải đều.

Virtual node (còn gọi là vnodes) giải quyết cả hai: mỗi node vật lý được ánh xạ vào V điểm trên ring thay vì 1 điểm, bằng cách hash "node_id#0", "node_id#1", ..., "node_id#(V-1)".

-- Thêm node với V virtual nodes
function addNodeWithVnodes(ring, node_id, V):
    for i <- 0 to V-1:
        vnode_id <- node_id + "#" + i
        pos <- hash(vnode_id) mod RING_SIZE
        ring.insert(pos, node_id)          -- lưu node vật lý, không phải vnode
// Time: O(V log N)  Space: O(V*N) trên ring

Với V lớn (Cassandra bản cũ mặc định 256 vnode/node; từ Cassandra 4.0 năm 2021 giảm còn 16 — xem CASSANDRA-13701 — vì 256 gây overhead repair/bootstrap), mỗi node vật lý chiếm ~V/tổng-vnode phần ring — xấp xỉ phân phối đều theo luật số lớn.

flowchart TB
    subgraph Ring2["Ring với virtual nodes (V=3)"]
        direction LR
        A0["A#0"] --> B0["B#0"] --> C0["C#0"] --> A1["A#1"] --> B1["B#1"] --> C1["C#1"] --> A2["A#2"] --> B2["B#2"] --> C2["C#2"] --> A0
    end
    A0 & A1 & A2 -->|"vật lý"| NA(["Node A"])
    B0 & B1 & B2 -->|"vật lý"| NB(["Node B"])
    C0 & C1 & C2 -->|"vật lý"| NC(["Node C"])

Khi Node B chết, các vnode của nó (B#0, B#1, B#2) phân tán trên ring — tải của chúng chuyển sang A và C xen kẽ, không dồn hết vào một node.

Heterogeneous cluster: node mạnh hơn (RAM cao hơn) được gán V lớn hơn, nhận nhiều key hơn tỉ lệ với sức mạnh.

5. Pitfall

Pitfall 1 — Quên wrap-around khi tìm successor

-- SAI: chỉ tìm tiến, bỏ sót trường hợp key nằm sau node cuối cùng trên ring
function lookupBuggy(ring, key):
    pos <- hash(key) mod RING_SIZE
    return ring.ceilingEntry(pos).node_id   -- null nếu không có node nào >= pos

-- ĐÚNG: nếu không có node nào >= pos, wrap về node đầu tiên
function lookupCorrect(ring, key):
    pos <- hash(key) mod RING_SIZE
    node <- ring.ceilingEntry(pos)
    if node = null:
        node <- ring.firstEntry()   -- wrap around
    return node.node_id

Bỏ sót wrap-around khiến ~1/N key (những key nằm sau node cuối trên ring) không được phục vụ — silent bug rất khó debug vì chỉ xảy ra với một phần nhỏ key.

Pitfall 2 — Hash node bằng địa chỉ IP thay vì tên ổn định

-- SAI: dùng IP, thay IP (scale-in/out trên cloud) → node hash sang vị trí khác
addNode(ring, "10.0.1.5")

-- ĐÚNG: dùng tên logic ổn định (hostname, node_id cố định)
addNode(ring, "cache-node-3")

Nếu node được thay thế bằng máy mới có IP khác, hash vào vị trí khác trên ring → vị trí cũ bị orphan, vị trí mới thêm như node mới → không nhận lại đúng key cũ.

Pitfall 3 — V quá nhỏ → phân bố vẫn lệch

-- V=1 (không có virtual node) với N=4 node:
-- Một node có thể chiếm 40% ring, node khác chỉ 10% — phụ thuộc vào hash
-- V=100 trở lên mới đạt phân bố tương đối đều theo CLT

Với V=1, xác suất cao có node bị "hot" (chiếm cung dài). Cassandra dùng V=16 (mặc định từ 4.0; bản cũ 256); memcached clients thường dùng V=150-200. Đánh đổi: V lớn hơn → phân bố đều hơn nhưng bộ nhớ ring lớn hơn O(V*N) và repair/bootstrap chậm hơn.

6. Liên hệ các bài khác

• Hash function: consistent hashing xây trên hash function phân phối đều (MurmurHash3, xxHash thường dùng trong production). Hiểu collision rate và avalanche effect giúp chọn hash đúng cho ring.
• Quorum — nhất quán đọc/ghi: trong thực tế, consistent hashing quyết định key nào vào node nào; quorum quyết định cần bao nhiêu node xác nhận để đảm bảo consistency. Hai kỹ thuật cùng nhau tạo nền tảng của Dynamo.
• Gossip protocol: Cassandra dùng gossip để các node tự phát hiện topology ring thay đổi (node join/leave) mà không cần coordinator trung tâm.
• Case study Cassandra & etcd: xem cách Cassandra triển khai consistent hashing + vnodes trong thực tế, kể cả cách handle node failure và repair.
• Crypto hash: khác với hash function thông thường, crypto hash (SHA-256) đảm bảo collision-resistance mạnh hơn nhưng chậm hơn — không phù hợp cho ring lookup hot path; dùng cho data integrity (Merkle tree).

📚 Deep Dive

Tóm tắt

• Modulo hashing hash(key) % N remap ~N/(N+1) key khi N thay đổi — gây cache stampede ở scale lớn.
• Consistent hashing chiếu key và node lên ring; mỗi key thuộc node đầu tiên theo chiều kim đồng hồ.
• Thêm/bớt node chỉ ảnh hưởng ~K/N key (chỉ cung lân cận), không phải toàn bộ K key.
• Lookup dùng ceilingEntry trên sorted map: O(log N). Bắt buộc xử lý wrap-around.
• Virtual node (V điểm/node vật lý) giải quyết phân bố lệch và hot spot khi node chết.
• Nền tảng của Amazon Dynamo, Apache Cassandra, ketama (memcached), nhiều CDN.

Tự kiểm tra

Bài tiếp theo: Quorum — nhất quán đọc/ghi với R+W>N