Trong các hệ thống phân tán, khi nào chúng ta nên sử dụng Consistent Hashing thay vì thuật toán băm modulo truyền thống (Modulo Hashing) và cơ chế hoạt động của nó giải quyết bài toán gì?

Question

Accepted Answer

Trong các hệ thống phân tán, Modulo Hashing sử dụng công thức hash(key) % N (với N là số lượng node máy chủ). Khi một node chết đi hoặc thêm node mới (N thay đổi), hầu như toàn bộ các khóa (keys) phải được tính toán lại và di chuyển sang node khác, gây ra hiện tượng cache stampede và quá tải hệ thống.
Consistent Hashing giải quyết triệt để vấn đề này bằng cách:

Cấu trúc vòng tròn (Hash Ring): Không gian giá trị của hàm băm được ánh xạ thành một vòng tròn khép kín từ 0 đến $2^{32}-1$.
Định vị Node và Key: Cả các node server và các key dữ liệu đều được băm qua cùng một hàm để đặt lên vòng tròn. Một key sẽ được lưu trữ tại node đầu tiên gặp phải khi đi theo chiều kim đồng hồ kể từ vị trí của key đó.
Giảm thiểu di chuyển dữ liệu: Khi thêm hoặc xóa một node, chỉ một lượng nhỏ dữ liệu (nằm giữa node đó và node lân cận) cần phải được định tuyến lại, các phần còn lại của vòng tròn giữ nguyên.

Ứng dụng thực chiến: Thường được áp dụng trong các cụm Distributed Caching (như Memcached, Redis Cluster) hoặc hệ thống Load Balancer để đảm bảo tính ổn định và khả năng mở rộng ngang (horizontal scaling) cực cao.

Trong các hệ thống phân tán, khi nào chúng ta nên sử dụng Consistent Hashing thay vì thuật toán băm modulo truyền thống (Modulo Hashing) và cơ chế hoạt động của nó giải quyết bài toán gì?

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi hash tables liên quan cùng chủ đề