Consistent Hashing: Hệ Thống Phân Tán Định Tuyến Dữ Liệu Mà Không Cần Xáo Trộn Toàn Bộ

Vấn đề với modulo hashing

Cách phân tán dữ liệu đơn giản nhất trên N node là hash(key) % N. Cách này hoạt động cho đến khi bạn thay đổi N. Thêm một node vào cluster 10 node và hầu hết mọi key sẽ ánh xạ sang node khác — bạn phải rebalance gần như tất cả. Với cache, điều đó tạo ra thundering herd. Với database, đó là một migration mất nhiều giờ.

Consistent hashing giải quyết điều này. Khi N thay đổi, chỉ 1/N key cần di chuyển, không phải tất cả.

The Ring

Hãy tưởng tượng một vòng tròn với 2^32 điểm. Bạn hash identifier của mỗi node để đặt nó trên ring. Để tìm node nào sở hữu một key, hash key đó và đi theo chiều kim đồng hồ cho đến khi gặp một node.

Ring (0 → 2^32):

  Node A tại vị trí 100
  Node B tại vị trí 300
  Node C tại vị trí 700

  Key K hash thành 250 → đi theo chiều kim đồng hồ → thuộc Node B

Khi thêm Node D tại vị trí 400, chỉ các key từ 300 đến 400 (trước đây thuộc C) chuyển sang D. Mọi thứ khác vẫn ở chỗ cũ.

Virtual Nodes

Ring đơn giản sẽ phân phối không đều. Nếu ba vị trí node tình cờ cluster lại, một node nhận hầu hết keyspace. Giải pháp là virtual node (vnode): mỗi node vật lý nhận nhiều vị trí trên ring.

Node A → vị trí 100, 520, 800
Node B → vị trí 200, 450, 900
Node C → vị trí 300, 600, 1000

Với 100–200 virtual node mỗi node vật lý, keyspace phân phối gần như đều. Khi thêm node vật lý mới, nó nhận một phần từ virtual range của mỗi node hiện có thay vì một khối lớn liên tục.

Replication

Hầu hết các hệ thống replicate mỗi key sang N node tiếp theo theo chiều kim đồng hồ. Cassandra sử dụng cách này: mỗi key có replication factor (RF) và được ghi vào primary node và RF-1 replica.

Nơi thấy điều này trong production

Amazon DynamoDB sử dụng consistent hashing nội bộ để phân vùng dữ liệu. Apache Cassandra để lộ ring trực tiếp — lệnh nodetool ring hiển thị vị trí token của mỗi node. Redis Cluster sử dụng 16.384 slot cố định. Memcached với thư viện ketama triển khai consistent hashing ở phía client.

Những gì consistent hashing không giải quyết

• Hot key: nếu một key nhận traffic không cân xứng, consistent hashing không giúp được.
• Cross-node transaction: phân tán key qua nhiều node làm cho atomic operation trên nhiều key trở nên tốn kém.

Kết luận thực tế

Consistent hashing là cơ chế cho phép cluster mở rộng và thu hẹp mà không cần reshuffle toàn bộ. Bạn không cần tự triển khai nó — mọi datastore phân tán lớn đều cung cấp. Điều bạn cần hiểu là đánh đổi: chấp nhận di chuyển một lượng nhỏ key (một node) để không phải di chuyển tất cả.