Mini-challenge — consistent hashing ring có virtual node

Bạn đang xây phần lõi của một distributed cache gồm N node vật lý. Mỗi key cần được ánh xạ đến đúng node — và khi cluster scale (thêm hoặc bớt node), tỷ lệ key phải di chuyển phải nhỏ nhất có thể để tránh cache stampede và data migration tốn kém.

Bài toán này xuất hiện trong:

• Distributed cache (Memcached, Redis Cluster) — tìm node lưu key mà không cần coordinator tập trung.
• Cassandra token ring — mỗi node sở hữu một đoạn trên vòng tròn hash; thêm node chỉ lấy key từ node kế tiếp.
• CDN edge selection — ánh xạ URL đến edge server gần nhất theo consistent hashing để cache hit rate cao.

Dành 20–25 phút tự implement trước khi xem gợi ý.

🎯 Đề bài

Viết ba hàm tạo thành một hash ring có virtual node:

Hàm 1 — buildRing(nodes, vnodeCount)

• Input: danh sách tên node nodes (ví dụ ["A", "B", "C"]), số virtual node mỗi node vật lý vnodeCount (ví dụ 100).
• Output: cấu trúc ring — mảng các cặp (position, nodeName) đã sắp xếp theo position tăng dần trên vòng tròn [0, 2^32).
• position tính bằng hash(nodeName + "#" + vnodeIndex) với vnodeIndex từ 0 đến vnodeCount - 1.

Hàm 2 — lookup(ring, key)

• Input: ring đã build, chuỗi key.
• Output: tên node vật lý chịu trách nhiệm cho key — là node vật lý của virtual node đầu tiên trên ring có position >= hash(key) (wrap-around về node đầu nếu không tìm thấy).
• Yêu cầu độ phức tạp: O(log(N × vnodeCount)) — dùng binary search.

Hàm 3 — measureMigration(nodes, addNode, vnodeCount, sampleKeys)

• Input: danh sách node ban đầu, tên node mới thêm vào, số vnode, danh sách key mẫu.
• Output: tỷ lệ key phải di chuyển (số key đổi node / tổng key).
• Tính bằng cách so sánh lookup trước và sau khi thêm node.

🔍 Input-Process-Output

📦 Concept mapping

📋 Test cases

Test case modulo baseline: với hash(key) % 3, thêm node thứ 4 làm hash(key) % 4 cho kết quả khác hoàn toàn — gần như mọi key đổi bucket. Consistent hashing chỉ dời key trong đoạn [predecessor_của_node_mới, node_mới].

▶️ Starter pseudocode

function buildRing(nodes, vnodeCount):
    ring <- []
    for each node trong nodes:
        for v from 0 to vnodeCount - 1:
            pos <- hash(node + "#" + v)   -- position trên vòng tròn [0, 2^32)
            ring.append((pos, node))
    -- TODO: sắp xếp ring theo pos tăng dần
    return ring

function lookup(ring, key):
    target <- hash(key)
    -- TODO: binary search tìm vị trí đầu tiên trong ring có pos >= target
    -- Nếu không tìm thấy (target vượt qua pos lớn nhất): wrap về ring[0]
    return ring[idx][1]                   -- ring[i] = (pos, node), [1] = node

function measureMigration(nodes, addNode, vnodeCount, sampleKeys):
    ringBefore <- buildRing(nodes, vnodeCount)
    ringAfter  <- buildRing(nodes + [addNode], vnodeCount)
    moved <- 0
    for each key trong sampleKeys:
        if lookup(ringBefore, key) != lookup(ringAfter, key):
            moved <- moved + 1
    return moved / sampleKeys.length

💡 Gợi ý

-- Lower bound binary search
lo <- 0
hi <- ring.length
while lo < hi:
    mid <- (lo + hi) / 2
    if ring[mid][0] < target:             -- ring[i] = (pos, node), [0] = pos
        lo <- mid + 1
    else:
        hi <- mid
-- lo là vị trí đầu tiên có ring[lo][0] >= target

✅ Lời giải

function buildRing(nodes, vnodeCount):
    ring <- []
    for each node trong nodes:
        for v from 0 to vnodeCount - 1:
            label <- node + "#" + toString(v)
            pos   <- hash32(label)        -- hash 32-bit, kết quả trong [0, 2^32)
            ring.append((pos, node))
    sort ring theo pos tăng dần           -- O(N × vnodeCount × log(N × vnodeCount))
    return ring
// Time: O(N·V·log(N·V))  Space: O(N·V)  với V = vnodeCount

function lookup(ring, key):
    target <- hash32(key)
    lo <- 0
    hi <- ring.length

    while lo < hi:                        -- lower bound binary search
        mid <- (lo + hi) / 2
        if ring[mid][0] < target:         -- ring[i] = (pos, node), [0] = pos
            lo <- mid + 1
        else:
            hi <- mid

    if lo = ring.length:                  -- wrap-around: target vượt pos cuối
        return ring[0][1]                 -- [1] = node
    return ring[lo][1]
// Time: O(log(N·V))  Space: O(1)

Ring (đã sort): [(120, "B"), (450, "C"), (800, "A")]

lookup(ring, "user:42"):
    target <- hash32("user:42") = 300
    Binary search → lo = 1  (ring[1][0] = 450 >= 300)
    return "C"

lookup(ring, "user:99"):
    target <- hash32("user:99") = 850
    Binary search → lo = 3 (vượt cuối) → wrap
    return ring[0][1] = "B"

function measureMigration(nodes, addNode, vnodeCount, sampleKeys):
    ringBefore <- buildRing(nodes, vnodeCount)
    ringAfter  <- buildRing(nodes + [addNode], vnodeCount)

    moved <- 0
    for each key trong sampleKeys:
        nodeBefore <- lookup(ringBefore, key)
        nodeAfter  <- lookup(ringAfter,  key)
        if nodeBefore != nodeAfter:
            moved <- moved + 1

    return moved / sampleKeys.length
// Time: O(K × log(N·V))  với K = sampleKeys.length

-- Khởi tạo cluster 3 node
nodes <- ["NodeA", "NodeB", "NodeC"]
ring  <- buildRing(nodes, vnodeCount=150)

-- Lookup key
node <- lookup(ring, "user:12345")        -- O(log 450)

-- Đo migration khi thêm NodeD
sampleKeys <- ["key_0", "key_1", ..., "key_9999"]
rate <- measureMigration(nodes, "NodeD", 150, sampleKeys)
-- Kỳ vọng: rate ≈ 0.25 (25%)

🎓 Mở rộng

So sánh định lượng với modulo hashing:

-- Modulo hashing 3 → 4 node
moved <- 0
for each key trong sampleKeys:
    if hash32(key) % 3 != hash32(key) % 4:
        moved <- moved + 1
-- Kỳ vọng: ~75% key đổi bucket

Consistent hashing ~25% so với modulo ~75% khi 3→4 node. Khi 9→10 node: consistent ~10% so với modulo ~90%. Độ chênh lệch tăng mạnh khi cluster lớn — đây là lý do hệ thống như Cassandra, Redis Cluster không dùng modulo.

Weighted node — node mạnh hơn nhận nhiều vnodes hơn:

-- Node A có 4 CPU → 200 vnode
-- Node B có 2 CPU → 100 vnode
ring <- buildRing([("A", 200), ("B", 100)], ...)
-- Node A nhận ~67% key, Node B nhận ~33%

Xóa node — remove tất cả vnode của node đó khỏi ring (lọc), lookup còn lại vẫn đúng ngay lập tức. Key của node bị xóa tự động chuyển sang node kế tiếp trên ring.

Replication factor R — thay vì lookup 1 node, tìm R node kế tiếp trên ring (bỏ qua vnode cùng node vật lý). Cassandra dùng cơ chế này để đặt replica trên R node vật lý khác nhau.

✨ Điều bạn vừa làm được

• Cài hash ring với virtual node, lookup O(log N) bằng binary search trên sorted array.
• Xử lý đúng wrap-around khi hash(key) vượt qua position lớn nhất trên ring.
• Đo định lượng tỷ lệ key di chuyển: consistent hashing ~K/N so với modulo ~100%.
• Nhận ra tại sao vnodeCount cao hơn giúp phân bố đều hơn — đổi lấy bộ nhớ lưu ring lớn hơn.
• Thấy nền tảng để hiểu Cassandra token ring trong case study tiếp theo.

Bài tiếp theo: Case study — Cassandra ring & etcd Raft