System DesignVấn đề với hash(key) % N: khi số node N thay đổi (thêm/bớt 1 server), gần như toàn bộ key bị remap sang node khác → cache miss hàng loạt, rebalance data khổng lồ.
Consistent Hashing: đặt cả node và key lên cùng một vòng tròn hash (0 → 2^32). Key thuộc về node đầu tiên gặp khi đi theo chiều kim đồng hồ.
- Thêm/bớt 1 node chỉ ảnh hưởng k/N key (phần nằm giữa node đó và node liền trước), không phải toàn bộ.
- Virtual nodes (vnodes): mỗi node vật lý ánh xạ thành nhiều điểm ảo trên vòng → phân bố đều hơn, tránh node mạnh/yếu lệch tải.
Hình dung: mặt đồng hồ tròn; mỗi server cắm vài cái đinh; mỗi key rơi xuống và lăn theo chiều kim đồng hồ tới cây đinh gần nhất.
Lưu ý: dùng trong distributed cache (Memcached client), DynamoDB/Cassandra ring, load balancer sticky. Vẫn có thể bị hot key nếu một key cụ thể quá nóng — consistent hashing chỉ giải bài toán phân bố, không giải hot key.