Hàm băm ổn định

Hàm băm ổn định (tiếng Anh: consistent hash function) là hàm băm mà việc thêm hoặc bớt một khối dữ liệu (slot) không làm thay đổi đáng kể ánh xạ từ khóa tới các khối dữ liệu. Khác với các hàm băm ổn định, trong hầu hết các bảng băm truyền thống, việc thay đổi số khối dữ liệu trong mảng dẫn đến việc ánh xạ lại toàn bộ khóa. Đối với hàm băm ổn định, trung bình chỉ phải ánh xạ lại ${\displaystyle K/n}$ khóa, trong đó ${\displaystyle K}$ là số khóa còn ${\displaystyle n}$ là số khối dữ liệu.

Lịch sử

Khái niệm băm ổn định được đưa ra năm 1997 với vai trò một phương pháp phân phối các yêu cầu cho một quần thế biến động gồm các web server. Khi đó, mỗi khối dữ liệu được biểu diễn bằng một nút trong một hệ thống phân tán. Việc thêm (gia nhập) và bớt (rời/hỏng) nút, nghĩa là khi số khối dữ liệu/nút thay đổi, chỉ đòi hỏi phải sắp xếp lại ${\displaystyle K/n}$ đối tượng. Gần đây, loại hàm băm này được dùng để giảm hậu quả của việc hỏng hóc một phần hệ thống trong các ứng dụng web lớn, nhằm tạo điều kiện cho việc lưu cache hiệu quả cao mà không gây ra tình trạng sập cả hệ thống do hỏng hóc^{[1] [2]}.

Các hàm băm ổn định còn được áp dụng trong thiết kế các bảng băm phân tán (DHT). DHT dùng loại hàm băm này để phân hoạch không gian khóa giữa một tập các nút phân tán, và ngoài ra còn cung cấp một mạng overlay kết nối các nút với nhau sao cho có thể định vị nút chịu trách nhiệm cho một khóa nào đó một cách hiệu quả.

Tham khảo

1. Karger, D.; Lehman, E.; Leighton, T.; Panigrahy, R.; Levine, M.; Lewin, D. (1997). “Consistent hashing and random trees”. Proceedings of the twenty-ninth annual ACM symposium on Theory of computing. ACM Press New York, NY, USA: 654–663. doi:10.1145/258533.258660. Truy cập ngày 17 tháng 6 năm 2008.
2. Karger, D.; Sherman, A.; Berkheimer, A.; Bogstad, B.; Dhanidina, R.; Iwamoto, K.; Kim, B.; Matkins, L.; Yerushalmi, Y. (1999). “Web caching with consistent hashing”. COMPUT. NETWORKS. 31 (11): 1203–1213. doi:10.1016/S1389-1286(99)00055-9. Bản gốc lưu trữ ngày 21 tháng 7 năm 2008. Truy cập ngày 17 tháng 6 năm 2008.

Liên kết ngoài

• Understanding Consistent hashing Lưu trữ 2009-02-27 tại Wayback Machine
• Consistent hashing Lưu trữ 2011-10-07 tại Wayback Machine by Tom White, including implementation in Java