Hàm băm ổn định

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

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 K/n khóa, trong đó K là số khóa còn n là số khối dữ liệu.

Lịch sử[sửa | sửa mã nguồn]

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 (ra 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 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[sửa | sửa mã nguồn]

  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. Truy cập ngày 17 tháng 6 năm 2008. 

Liên kết ngoài[sửa | sửa mã nguồn]