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 chuyển sang node khác (remap) khi N đổi. Consistent hashing giải quyết bằng cách đặt cả key lẫn node lên một vòng tròn (ring) có dải giá trị hash cố định; key thuộc về node đầu tiên gặp theo chiều kim đồng hồ. Thêm một node (thành N+1 node) chỉ dời cỡ K/(N+1) key thay vì toàn bộ K key; bớt một node chỉ dời đúng phần key của node đó. Virtual node (mỗi node vật lý giữ nhiều điểm trên ring) san đều tải, và khi một node chết thì phần tải của nó chia ra nhiều node. Amazon Dynamo, Apache Cassandra và nhiều CDN đều dựa vào cách này.

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 quyết định có xảy ra "cache stampede" (hàng loạt key miss cùng lúc, request đổ dồn xuống database) làm sập hệ thống hay không. Bài này cho thấy cách thêm node còn quan trọng hơn số node.

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

Cách đơn giản nhất để chia K key cho 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. Đó là cache stampede.

Hàng triệu cache miss đổ xuống database cùng lúc thì latency tăng vọt, request timeout rồi retry, và vòng lặp chết bắt đầu.