Băm nhất quán (Consistent Hashing)

1. Tổng quan

A. Định nghĩa

Băm nhất quán (Consistent Hashing) là kỹ thuật phân phối dữ liệu phân tán, trong đó khóa (Key) và nút (máy chủ) được đặt trên cùng một vòng (Ring) của không gian băm, và mỗi khóa được gán cho nút đầu tiên gặp phải theo chiều kim đồng hồ, nhờ đó khi thêm hoặc xóa nút, số khóa bị tái phân bổ được giảm thiểu xuống mức trung bình K/N.

Băm nhất quán là thuật toán do David Karger và cộng sự tại MIT đề xuất năm 1997 nhằm cân bằng tải cho bộ nhớ đệm web, ngày nay được dùng rộng rãi từ các kho dữ liệu phân tán như Amazon DynamoDB, Apache Cassandra, Riak cho đến client memcached, CDN và logic chọn backend của bộ cân bằng tải. Giá trị cốt lõi là nó đưa ra câu trả lời cho câu hỏi căn bản "đặt dữ liệu ở máy chủ nào", sao cho giảm thiểu việc di chuyển dữ liệu ngay cả trong môi trường tập máy chủ thay đổi thường xuyên.

B. Bối cảnh ra đời và sự cần thiết

Cách phân phối đơn giản nhất là băm modulo (hash(key) % N). Khi có N nút, nếu xác định nút phụ trách bằng phần dư của giá trị băm khóa chia cho N thì phân bố đều, nhưng có một điểm yếu chí mạng. Chỉ cần số nút N thay đổi dù chỉ một (bị loại do sự cố hoặc tăng do mở rộng), mẫu số của phép chia thay đổi và nút phụ trách của gần như mọi khóa đều bị tính lại. Ví dụ, tăng từ N=4 lên N=5 thì về lý thuyết khoảng 80% khóa di chuyển sang nút khác. Với bộ nhớ đệm phân tán, ngay lúc đó tỷ lệ cache hit giảm mạnh và xảy ra cache stampede — yêu cầu dồn dập vào DB gốc; với DB phân tán thì gây ra di chuyển dữ liệu quy mô lớn.

Xét đến việc trong môi trường đám mây và microservice, nút tăng giảm liên tục do tự động mở rộng (autoscaling) và sự cố xảy ra thường ngày, "thay đổi nút = tái phân bổ toàn bộ" là chi phí không thể chấp nhận. Băm nhất quán làm cho khóa phụ thuộc vào vị trí băm của nút chứ không phải số lượng nút, nhờ đó cục bộ hóa ảnh hưởng để khi một nút thay đổi, chỉ các khóa thuộc đoạn mà nút đó phụ trách bị ảnh hưởng. Tức là lợi thế quyết định của kỹ thuật này là đối tượng tái phân bổ giảm từ toàn bộ xuống trung bình K/N khóa (K là số khóa, N là số nút).

2. Nguyên lý hoạt động — Vòng băm và gán theo chiều kim đồng hồ

Băm nhất quán hình dung không gian đầu ra của hàm băm (ví dụ: 0 ~ 2^32-1) như một vòng tròn mà điểm cuối nối liền với điểm đầu. Mỗi nút băm định danh của mình (IP, tên...) để được đặt tại một điểm trên vòng, và mỗi khóa cũng được đặt lên vòng bằng cùng hàm băm. Nút phụ trách của một khóa được xác định là nút đầu tiên gặp phải khi đi theo chiều kim đồng hồ từ vị trí khóa. Làm vậy thì mỗi nút chịu trách nhiệm cho cung "từ nút ngay trước nó đến chính nó".

flowchart TB
    subgraph Ring["Vòng băm(0 ~ 2^32-1, hình tròn)"]
      NA["Nút A(vị trí 40)"]
      NB["Nút B(vị trí 130)"]
      NC["Nút C(vị trí 220)"]
    end
    K1["Khóa1 → băm 25"] -->|"Nút đầu tiên theo chiều kim đồng hồ"| NA
    K2["Khóa2 → băm 95"] -->|"Nút đầu tiên theo chiều kim đồng hồ"| NB
    K3["Khóa3 → băm 200"] -->|"Nút đầu tiên theo chiều kim đồng hồ"| NC
    K4["Khóa4 → băm 250(→quay vòng)"] -->|"Nút đầu tiên theo chiều kim đồng hồ"| NA

Trong hình trên, khóa 4 có giá trị băm 250 đã đi qua nút C (220), nhưng vượt qua điểm cuối vòng (2^32-1) để quay vòng (wrap-around) về đầu (0), gặp nút A (40) nên A phụ trách. Nhờ cấu trúc vòng tròn này, dù khóa nằm ở điểm nào trên vòng thì luôn tồn tại nút phụ trách.

Điều gì xảy ra nếu nút B rời khỏi do sự cố? Chỉ các khóa trong đoạn mà B phụ trách (sau nút A ~ đến B) chuyển sang nút kế tiếp theo chiều kim đồng hồ là C, còn các khóa do A và C phụ trách hoàn toàn không bị ảnh hưởng. Ngược lại, khi thêm mới nút D, chỉ các khóa của đoạn ngay trước vị trí D di chuyển sang D, phần còn lại giữ nguyên. Việc ảnh hưởng của thay đổi được cục bộ hóa trong một đoạn liền kề như vậy là khác biệt bản chất so với băm modulo.

3. Vấn đề lệch dữ liệu và nút ảo (Virtual Node)

Cách cơ bản có hai điểm yếu. Thứ nhất, nếu đặt nút ngẫu nhiên trên vòng thì độ dài các đoạn không đều nên khóa có thể dồn vào một nút cụ thể (mất cân bằng tải). Thứ hai, khi một nút rời đi, tải của nó dồn trọn vào một nút kế tiếp duy nhất theo chiều kim đồng hồ, gây ra sự cố dây chuyền (cascading failure).

Kỹ thuật chuẩn để giải quyết vấn đề này là nút ảo (Virtual Node, vnode). Một nút vật lý không được đặt tại một điểm trên vòng mà được rải thành hàng chụchàng trăm điểm ảo tính bằng các hàm băm khác nhau. Ví dụ, nếu phân tán nút vật lý A thành 150 nút ảo như A#1, A#2, ..., A#150 khắp vòng, các cung mà mỗi nút vật lý phụ trách được rải nhỏ trên toàn vòng, và tính đồng đều của phân tải được cải thiện đáng kể về mặt thống kê. Thực tế, khi đặt số nút ảo ở mức 100200, độ lệch tải giữa các nút giảm từ vài chục % xuống một chữ số %.

flowchart LR
    subgraph Physical["Nút vật lý"]
      PA["Nút A"]
      PB["Nút B"]
    end
    subgraph VRing["Vòng rải các nút ảo"]
      VA1["A#1"]
      VB1["B#1"]
      VA2["A#2"]
      VB2["B#2"]
      VA3["A#3"]
      VB3["B#3"]
    end
    PA --> VA1
    PA --> VA2
    PA --> VA3
    PB --> VB1
    PB --> VB2
    PB --> VB3
    VA1 --> VB1 --> VA2 --> VB2 --> VA3 --> VB3 --> VA1

Lợi ích thứ hai của nút ảo là ứng phó với phần cứng không đồng nhất (heterogeneous capacity). Nếu cấp gấp đôi số nút ảo cho máy chủ có hiệu năng gấp đôi, nó sẽ phụ trách nhiều cung hơn tương ứng, phản ánh tự nhiên trọng số dung lượng (weighting). Ngoài ra, khi một nút chết, tải của nó được hấp thụ phân tán bởi nhiều nút vật lý nên rủi ro sự cố dây chuyền cũng giảm. Tuy nhiên tồn tại sự đánh đổi là bảng định tuyến để duy trì và tra cứu thông tin nút ảo lớn lên và độ phức tạp quản lý tăng.

4. So sánh với các kỹ thuật tương tự — Vì sao có khác biệt

So sánh băm nhất quán với băm modulo, cùng các kỹ thuật mới như băm nhảy (Jump Consistent Hash, Google, 2014) và băm hẹn gặp (Rendezvous / HRW) sẽ thấy mỗi kỹ thuật tối ưu hóa ở những điểm khác nhau.

Lý do băm modulo bị né tránh trong thực tiễn dù tính đồng đều tải là tốt nhất, như đã thấy, là vì chi phí tái phân bổ khi thay đổi nút quá lớn. Bối cảnh khiến băm nhất quán thắng thế là: điểm nghẽn thực chất không phải chỉ số tĩnh như tính đồng đều tải mà là chi phí thay đổi trong môi trường động nơi nút thay đổi liên tục. Băm nhảy đạt tái phân bổ tối thiểu với bộ nhớ O(1) mà không cần cấu trúc dữ liệu vòng, nhưng do cấu trúc gán số thứ tự tuần tự cho nút nên có hạn chế khó xóa nút tùy ý và gán trọng số, vì vậy phù hợp với môi trường shard mà "nút chỉ tăng giảm ở phía cuối". Băm hẹn gặp tính băm của mỗi khóa với mọi nút và chọn nút có giá trị lớn nhất, nên linh hoạt trong kiểm soát trọng số và ưu tiên nhưng tốn chi phí tính toán tỷ lệ với số nút N. Rốt cuộc, các kho lưu trữ phân tán quy mô lớn đòi hỏi đồng thời "giảm thiểu tái phân bổ + đồng đều + trọng số" chọn băm nhất quán có nút ảo làm tiêu chuẩn.

Về tình huống áp dụng thực tiễn, Amazon DynamoDB và Apache Cassandra đặt dữ liệu vào các đoạn token (vnode) trên vòng, và sao chép mỗi khóa sang N nút (replication factor N) theo chiều kim đồng hồ bắt đầu từ nút phụ trách. Khi đó băm nhất quán trở thành bộ khung định tuyến xác định "những nút nào giữ bản sao của khóa này", và ngay cả khi mở rộng nút, dữ liệu di chuyển được cục bộ hóa nên có thể mở rộng không gián đoạn. Discord dùng băm hẹn gặp để ngăn cơn bão tái dựng cache khi memcache gặp sự cố, còn bộ cân bằng tải Google Maglev dùng biến thể của băm nhất quán để duy trì kết nối — tức là nó cũng được dùng rộng rãi để đảm bảo tính gắn kết kết nối (connection affinity).

5. Các vấn đề cần cân nhắc và hàm ý

Từ góc độ Kỹ sư chuyên nghiệp (Professional Engineer), khi thiết kế và triển khai băm nhất quán cần xem xét tổng hợp những điểm sau.

• Điều chỉnh đánh đổi về số nút ảo: Tăng vnode làm tính đồng đều tải tốt hơn nhưng siêu dữ liệu định tuyến và chi phí cập nhật khi thay đổi thành viên tăng lên. Tinh chỉnh dựa trên đo đạc thực tế ở mức 100~vài trăm vnode trên mỗi nút vật lý, có tính đến quy mô nút, tính không đồng nhất của phần cứng và SLA.
• Lựa chọn hàm băm: Để phân bố đều trên vòng, nên dùng các hàm băm phi mật mã nhanh, ít va chạm và thiên lệch như MurmurHash, xxHash thay vì MD5, SHA-1, nhưng phải kiểm chứng trước chất lượng phân bố. Nếu không vì mục đích bảo mật thì ưu tiên hiệu năng.
• Liên kết với sao chép và tính nhất quán: Sao chép dựa trên vòng theo lý thuyết CAP thường đạt tính sẵn sàng và khả năng chịu phân vùng nhưng chấp nhận nhất quán cuối cùng (eventual consistency). Phải thiết kế cùng với đọc/ghi theo đa số (quorum) (R+W>N), hinted handoff, anti-entropy... thì tính nhất quán dữ liệu thực tế mới được đảm bảo.
• Rủi ro khóa nóng (hot key) và lệch còn tồn tại: Nếu lưu lượng tập trung vào một khóa phổ biến cụ thể thì vnode cũng không giải quyết được. Cần song hành phân shard theo tiền tố khóa, bổ sung tầng cache và phân tải ở mức ứng dụng.
• Quản lý thành viên và khả năng quan sát: Phải có đồng thời giao thức gossip hoặc cơ chế thành viên dựa trên đồng thuận để lan truyền việc tăng giảm nút cho toàn cụm, và hệ thống quan sát (observability) giám sát thường xuyên tiến độ tái phân bổ và độ lệch tải thì mới đảm bảo được sự ổn định vận hành.
• Triển vọng: Để đảm bảo tính cục bộ dữ liệu (data locality) và giảm thiểu độ trễ, băm nhận biết vị trí địa lý và rack (topology-aware) đang lan rộng, và khi phân tán các khối lượng công việc có trạng thái trong môi trường serverless và điện toán biên, đặc tính giảm thiểu tái phân bổ của băm nhất quán càng trở nên quan trọng.

Tóm tắt một câu: Băm nhất quán là kỹ thuật phân phối đặt khóa và nút trên cùng một vòng băm và gán khóa cho nút đầu tiên theo chiều kim đồng hồ, giảm thiểu tái phân bổ khi tăng giảm nút xuống trung bình K/N, và dùng nút ảo để đạt tính đồng đều tải và trọng số, được dùng làm nền tảng định tuyến tiêu chuẩn cho kho lưu trữ phân tán, bộ nhớ đệm và bộ cân bằng tải quy mô lớn.