Consistent Hashing
Kỹ thuật phân phối dữ liệu được thiết kế để giảm thiểu sự thay đổi khi các nút (nodes) hoặc máy chủ (servers) được thêm vào hoặc xóa khỏi hệ thống
Khái niệm
Consistent Hashing là một kỹ thuật phân phối dữ liệu được thiết kế để giảm thiểu sự thay đổi khi các nút (nodes) hoặc máy chủ (servers) được thêm vào hoặc xóa khỏi hệ thống. Đây là một giải pháp hiệu quả trong các hệ thống phân tán như cache systems, distributed storage, hoặc load balancers.
Cách thức hoạt động
Vòng băm (Hash Ring)
Consistent Hashing ánh xạ không gian băm thành một vòng tròn (gọi là Hash Ring) có giá trị từ 0 đến 2^32 - 1 (hoặc một giới hạn khác tùy thuộc vào hàm băm).
Cả các nút và dữ liệu (key) đều được ánh xạ vào vòng băm này bằng cách sử dụng một hàm băm như SHA-1 hoặc MD5.
Ánh xạ dữ liệu tới node
Dữ liệu được ánh xạ tới một vị trí cụ thể trên vòng băm dựa trên giá trị băm của khóa dữ liệu (key).
Mỗi nút cũng được ánh xạ tới một vị trí cụ thể trên vòng băm dựa trên giá trị băm của ID nút.
Một dữ liệu (key) được gán cho nút đầu tiên trên vòng băm theo chiều kim đồng hồ từ vị trí của nó.
Xử lý thêm hoặc xóa node
Khi một nút mới được thêm vào hoặc một nút bị xóa, chỉ một phần dữ liệu cần phải được phân phối lại cho nút gần nhất trên vòng băm. Điều này khác với các kỹ thuật phân vùng truyền thống, nơi thay đổi các nút thường dẫn đến sự phân phối lại toàn bộ dữ liệu.
Các bước thực hiện
1. Tạo vòng băm (Hash Ring)
Mục đích: Biểu diễn không gian giá trị băm thành một vòng tròn logic (gọi là vòng băm hoặc hash ring).
Cách làm:
Sử dụng một hàm băm nhất định (ví dụ: MD5, SHA-256) để ánh xạ các giá trị đầu vào thành các số nguyên.
Giả định rằng không gian giá trị băm nằm trong khoảng từ 0 đến 2^m−1 (với m là độ dài của băm, ví dụ: m=32).
Tất cả các giá trị băm được coi như điểm trên vòng tròn.
2. Ánh xạ các máy chủ vào vòng băm
Mục đích: Gán các máy chủ hoặc nút (nodes) vào vị trí trên vòng băm.
Cách làm:
Mỗi máy chủ được ánh xạ thành một hoặc nhiều điểm trên vòng băm thông qua hàm băm.
Để phân phối đều, mỗi máy chủ có thể được ánh xạ nhiều lần bằng cách băm kèm theo một số thứ tự (ví dụ: “Node1-1”, “Node1-2”).
3. Ánh xạ dữ liệu vào vòng băm
Mục đích: Gán các đối tượng dữ liệu (keys) vào các vị trí trên vòng băm.
Cách làm:
Mỗi khóa dữ liệu (key) được băm thành một giá trị bằng cùng một hàm băm đã sử dụng cho các máy chủ.
Điểm của khóa trên vòng băm sẽ quyết định máy chủ chịu trách nhiệm lưu trữ dữ liệu đó.
4. Xác định máy chủ cho một khóa dữ liệu
Mục đích: Tìm máy chủ phù hợp để lưu trữ hoặc xử lý dữ liệu.
Cách làm:
Từ vị trí của khóa trên vòng băm, di chuyển theo chiều kim đồng hồ để tìm máy chủ đầu tiên. Máy chủ này là nơi lưu trữ hoặc xử lý dữ liệu.
Nếu không có máy chủ nào nằm sau khóa trên vòng, vòng băm sẽ quay lại điểm bắt đầu.
5. Xử lý thêm hoặc xóa máy chủ
Thêm máy chủ:
Khi một máy chủ mới được thêm vào:
Máy chủ này sẽ được ánh xạ vào một hoặc nhiều vị trí mới trên vòng băm.
Dữ liệu từ các máy chủ hiện tại, nằm gần các vị trí mới này (theo chiều ngược kim đồng hồ), sẽ được chuyển giao sang máy chủ mới.
Ưu điểm: Chỉ một phần nhỏ dữ liệu cần được di chuyển.
Xóa máy chủ:
Khi một máy chủ bị xóa:
Dữ liệu do máy chủ này chịu trách nhiệm sẽ được chuyển sang máy chủ gần nhất theo chiều kim đồng hồ.
Ưu điểm: Chỉ các dữ liệu liên quan đến máy chủ bị xóa cần được di chuyển.
Ưu điểm
Tái cân bằng dữ liệu hiệu quả:
Khi thêm hoặc xóa một máy chủ, chỉ một phần nhỏ dữ liệu cần di chuyển.
Phân phối đều:
Khi sử dụng cơ chế ánh xạ máy chủ hợp lý (như nhiều vị trí trên vòng), dữ liệu được phân phối đều giữa các máy chủ.
Tính mở rộng cao:
Phù hợp cho các hệ thống lớn, nơi số lượng máy chủ hoặc dữ liệu thay đổi liên tục.