Rendezvous Hashing, một thuật toán khác thay thế Consistent Hashing
Table of Contents
Khoan, Consistent Hashing là gì?
À, bài viết này nhằm mục đích giới thiệu Rendezvous Hashing (Highest Random Weight Hashing), một thuật toán có thể thay thế cho thuật toán “trứ danh” Consistent Hashing. Nếu bạn chưa từng nghe về Consistent Hashing và bài toán mà nó giải quyết thì có thể tham khảo qua bài viết dễ đọc và dễ hiểu này trước khi đi vào nội dung chính.
Phân chia dữ liệu cache trên cụm server với Consistent Hashing
Vậy Rendezvous Hashing là gì?
Sau khi đã “thông” qua vấn đề, mình xin giới thiệu thuật toán này.
Ý tưởng rất đơn giản, bạn hash key cùng với tên của server (hoặc IP hay bất cứ gì đặc trưng của server) được kết quả gọi là score rồi chọn server cho score lớn nhất. That’s it!
Thuật toán này đơn giản như cách nói vậy, đây là mã giả thể hiện “tinh thần” của thuật toán.
type router struct {
endpoints []*Endpoint
}
func (r *router) Get(key string) *Endpoint {
var ep *Endpoint
score := -INF
for _, e := range r.endpoints {
h = hash(key, e)
if h > score {
ep = e
score = h
}
}
return ep
}
//source: https://medium.com/i0exception/rendezvous-hashing-8c00e2fb58b0
Bình luận một chút.
Dễ thấy độ phức tạp của thuật toán là O(n) với n là số server (endpoint).
Thời gian thực thi sẽ phụ thuộc lớn vào thời gian thực thi của hàm hash. Vì vậy chúng ta sẽ ưu tiên những hàm hash thực hiện nhanh, hàm gì thì đọc tiếp nhé.
Nếu bạn thắc mắc làm sao mà thuật toán này có thể phân bố tải cân bằng được thì hãy nhớ lại tính chất của hàm hash (các khoá được phân bố đều trong bảng). Độ cân bằng của kết quả sẽ do phân phối của hàm hash quyết định. Các tác giả đã đề xuất hàm hash trong bài báo gốc nhưng bạn có thể sử dụng bất kì hàm nào yêu thích. Đương nhiên sẽ ưu tiên những hàm cho phân phối đều cũng như thực thi càng nhanh càng tốt, ví dụ như murmurhash3.
Weighted Rendezvous Hashing
Vậy còn trọng số thì sao? Một cách dễ thấy nhất để áp dụng cho các server có trọng số khác nhau là cho nó xuất hiện nhiều lần trong danh sách tương ứng với trọng số, tuy nhiên cách này có điểm không hay là tăng thời gian tính toán và không thể đáp ứng nếu trọng số là số “lẻ” ví dụ 69%.
May mắn là có một “phép thuật” giúp chúng ta kết hợp được trọng số vào kết quả score:
$$ score = {-weight \over log(h)} $$
Tadaa!
Không tin “phép thuật” này, bạn có thể xem chứng minh ở slide số 35 tại đây.
Mình đã hiện thực một phiên bản thuật toán này bằng ngôn ngữ Java. Các bạn có thể tham khảo mã nguồn đầy đủ ở repo github này.
Tham khảo thêm
Đây là những bài viết khác cho các bạn tham khảo thêm về thuật toán này nhé.