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 co giãn (thêm hoặc bớt node), số key phải chuyển sang node khác càng ít càng tốt, để tránh cache stampede và việc chuyển dữ liệu tốn kém.

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

• Distributed cache (client Memcached kiểu ketama): tìm node lưu key mà không cần coordinator tập trung. Redis Cluster chọn cách khác một chút: chia sẵn 16384 hash slot cố định rồi gán slot cho node.
• Cassandra token ring: mỗi node sở hữu các đoạn trên vòng tròn hash; thêm node chỉ nhận lại một phần key từ các node hiện có.
• CDN cache cluster: ánh xạ URL tới một server cache trong cụm bằng consistent hashing, để cùng một URL luôn về cùng một server và cache hit rate cao.

Hãy dành 20 đến 25 phút tự cài trước khi xem gợi ý. Cơ chế ring và virtual node nằm ở bài 01, cần thì mở lại. Trước khi gõ code, thử vẽ tay một ring 3 node với vài key số nhỏ như trace ở phần lời giải; thói quen này được dạy ở Làm tay trước khi làm máy.

Đề bài

Viết bốn hàm tạo thành một hash ring có virtual node. Hash cố định và test vector có đáp án nằm ở mục "Hàm hash cố định và ca kiểm thử".

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.

Hàm 4: loadSkew(ring, sampleKeys)

• Input: ring đã build, danh sách key mẫu.
• Output: độ lệch tải = (số key của node vật lý nhiều key nhất) / (số key trung bình mỗi node vật lý). Bằng 1,0 là chia đều hoàn hảo; bằng 2,0 nghĩa là node nặng nhất gánh gấp đôi mức trung bình.
• Node không nhận key nào vẫn tính vào mẫu số (chia cho số node vật lý trong ring, không phải số node có key).