Database hay gặpKhi phân dữ liệu ra N node, cách ngây thơ là hash(key) % N. Vấn đề: khi thêm/bớt một node (N đổi), gần như mọi khóa bị ánh xạ lại sang node khác → phải di chuyển gần hết dữ liệu, cache miss hàng loạt ("rehash storm"). Rất tệ cho hệ có node vào/ra thường xuyên (cache cluster, DB phân tán).
Consistent hashing giải quyết bằng cách đặt cả khóa và node lên một vòng băm (hash ring). Một khóa thuộc về node đầu tiên gặp khi đi theo chiều kim đồng hồ từ vị trí của nó.
- Thêm node: chỉ các khóa nằm giữa node mới và node kế trước bị chuyển → trung bình chỉ ~K/N khóa di chuyển thay vì gần như tất cả.
- Bớt node: khóa của node đó chuyển sang node kế tiếp trên vòng; phần còn lại không đổi.
Virtual nodes (vnodes): mỗi node vật lý đặt ở nhiều điểm trên vòng để phân bố đều tải và tránh lệch khi node ít.
Ứng dụng: phân vùng của Cassandra, DynamoDB, các distributed cache (memcached client, Redis Cluster dùng biến thể hash slot). Đây là câu system-design kinh điển vì giải đúng bài toán "scale cụm mà không xáo trộn toàn bộ dữ liệu".