Consistent Hashing cho Backend: Phân vùng dữ liệu và mở rộng cụm an toàn

Khi một backend chia key cho nhiều node bằng công thức hash(key) % N, việc thêm hoặc bớt chỉ một node có thể làm phần lớn key đổi đích. Cache miss tăng đột biến, database bị dồn tải, dữ liệu phải chuyển hàng loạt và một thao tác mở rộng tưởng như đơn giản có thể biến thành sự cố. Consistent hashing giải quyết phần định tuyến của bài toán bằng cách giữ ánh xạ của đa số key ổn định khi tập node thay đổi.

Bài viết này đi từ mô hình modulo đến hash ring, virtual node và rendezvous hashing; sau đó đặt thuật toán vào bối cảnh production gồm replication, topology, hot key, chuyển dữ liệu, quan sát và rollback. Mục tiêu không phải tự viết một cơ sở dữ liệu phân tán hoàn chỉnh, mà là hiểu rõ khi nào consistent hashing phù hợp, nó đảm bảo điều gì và những phần hệ thống nào vẫn phải được thiết kế riêng.

1. Vấn đề của phép chia dư khi số node thay đổi

Với ba node, một router đơn giản có thể chọn nodes[hash(key) % 3]. Nếu hàm băm phân bố tốt, tải ban đầu khá đều. Nhưng khi thêm node thứ tư, kết quả modulo đổi từ 3 sang 4. Một key chỉ giữ nguyên node nếu hai kết quả tình cờ trỏ cùng vị trí; rất nhiều key còn lại bị ánh xạ sang node khác dù node cũ vẫn khỏe mạnh.

before: owner = nodes[hash(key) % 3]
after:  owner = nodes[hash(key) % 4]

// Nằm đúng bucket không có nghĩa key đang tồn tại ở node mới.

Đối với cache, hậu quả là một đợt cold cache diện rộng. Request đồng thời xuyên qua cache và cùng truy vấn database, tạo cache stampede đúng lúc cụm vừa thay đổi. Đối với kho dữ liệu được sharding ở tầng ứng dụng, hậu quả nghiêm trọng hơn: router mới tìm key ở node mới nhưng bản ghi vẫn nằm ở node cũ. Hệ thống cần di chuyển dữ liệu, đọc từ hai nơi trong giai đoạn chuyển tiếp hoặc có một lớp ánh xạ ổn định khác.

Consistent hashing đặt cả key và node vào một không gian băm ổn định. Khi membership thay đổi, chỉ vùng thuộc node tham gia hoặc rời cụm cần đổi chủ. Lợi ích cốt lõi là giảm churn của ánh xạ; thuật toán không tự sao chép dữ liệu, phát hiện lỗi hay đảm bảo consistency.

2. Hash ring hoạt động như thế nào?

Hãy xem không gian băm như một vòng tròn từ 0 đến giá trị lớn nhất rồi quay lại 0. Mỗi node được băm thành một hoặc nhiều token trên vòng. Mỗi key cũng được băm vào cùng không gian. Một quy ước phổ biến là key thuộc node đầu tiên gặp khi đi theo chiều kim đồng hồ từ vị trí của key.

ring = sort(tokens)

function locate(key):
  point = hash(key)
  token = first ring token >= point
  if token does not exist:
    token = ring[0]
  return token.owner

Router có thể dùng binary search trên mảng token đã sắp xếp, nên tìm owner có độ phức tạp O(log V) với V là tổng số token. Khi thêm một token, chỉ key trong khoảng từ token liền trước đến token mới đổi chủ. Khi bỏ token, khoảng đó chuyển cho token kế tiếp. Các khoảng khác không cần ánh xạ lại.

Điểm vòng về đầu là chi tiết dễ gây lỗi. Nếu hash của key lớn hơn token cuối cùng, owner phải là token đầu tiên chứ không phải node cuối. Việc so sánh số nguyên có dấu và không dấu, chuyển byte sang chuỗi hoặc dùng encoding khác nhau giữa các client cũng có thể làm cùng một key đi tới hai node. Hash function, encoding, byte order và quy tắc chọn token phải là một contract được version hóa.

3. Một token cho mỗi node vẫn chưa đủ

Nếu mỗi node chỉ có một token ngẫu nhiên, kích thước các khoảng trên ring có thể rất chênh lệch. Một node vô tình sở hữu khoảng lớn sẽ giữ nhiều key và nhận nhiều traffic hơn. Khi node đó rời cụm, toàn bộ khoảng lớn thường dồn sang một hàng xóm, khiến cân bằng sau sự cố kém.

Virtual node hay vnode giải quyết vấn đề bằng cách cho mỗi node vật lý sở hữu nhiều token rải trên ring. Tải của một máy trở thành tổng nhiều khoảng nhỏ, vì vậy sai lệch thường giảm. Khi thêm máy, nó nhận các khoảng từ nhiều máy hiện có thay vì lấy phần lớn dữ liệu từ một hàng xóm. Bài báo Dynamo của Amazon mô tả biến thể gán nhiều vị trí cho mỗi node; tài liệu kiến trúc Cassandra cũng trình bày vnode trong mô hình consistent hashing.

Nhiều vnode không đồng nghĩa càng nhiều càng tốt. Số token quá lớn làm membership map nặng hơn, tăng số range nhỏ, phức tạp hóa repair và tạo nhiều luồng truyền dữ liệu. Hãy chọn từ quy mô cụm, độ lệch chấp nhận được, chi phí metadata và công cụ vận hành, rồi kiểm chứng bằng mô phỏng key thật.

4. Weighted ring cho node không đồng nhất

Cụm production thường không đồng nhất: máy mới có nhiều RAM hơn, một availability zone có giới hạn I/O khác, hoặc một nhóm node chỉ nên nhận một nửa tải. Ring cần hỗ trợ trọng số thay vì mặc định mọi node có năng lực bằng nhau. Cách trực tiếp là cấp số vnode tỷ lệ với capacity tương đối.

node-a: weight 1.0 -> 128 tokens
node-b: weight 2.0 -> 256 tokens
node-c: weight 0.5 ->  64 tokens

Trọng số phải dựa trên bottleneck thật của workload. Dung lượng RAM có thể phù hợp với cache, nhưng storage shard có thể bị giới hạn bởi IOPS hoặc network. Một node có gấp đôi disk không chắc phục vụ gấp đôi request nếu CPU mã hóa đã bão hòa. Thay đổi weight cũng là một lần rebalance; không nên để autoscaler liên tục điều chỉnh theo metric nhiễu.

Đặt ngưỡng, cooldown và tốc độ dịch chuyển tối đa. Nếu một node mới cần warm cache hoặc compact dữ liệu, hãy tăng trọng số theo từng bước. Capacity model nên phân biệt dữ liệu lưu trữ, request rate, kích thước object và chi phí của từng loại thao tác thay vì chỉ đếm số key.

5. Rendezvous hashing: lựa chọn không cần ring

Rendezvous hashing, còn gọi là highest-random-weight hashing, tính một score xác định cho mỗi cặp (key, node) rồi chọn node có score cao nhất. Khi node bị loại, node có score cao thứ hai trở thành owner. Cách này có thuộc tính ít xáo trộn tương tự nhưng không cần sắp token trên ring.

function locate(key, nodes):
  bestNode = null
  bestScore = -infinity
  for node in nodes:
    score = hash(key + stableNodeId(node))
    if score > bestScore:
      bestScore = score
      bestNode = node
  return bestNode

Bản cơ bản tốn O(N) phép tính cho mỗi lookup, phù hợp khi số node nhỏ hoặc routing map được cache. Ưu điểm là implementation rõ, dễ lấy danh sách node xếp hạng để chọn replica và không phải tinh chỉnh số vnode. Biến thể weighted rendezvous hỗ trợ năng lực khác nhau, nhưng công thức trọng số phải được lấy từ tài liệu đáng tin cậy và test phân bố; nhân score một cách tùy ý thường gây bias.

Hash ring và rendezvous hashing đều có thể đúng. Quyết định nên dựa trên số node, tần suất lookup, nhu cầu replica ranking, chi phí metadata và khả năng tương thích với hệ thống hiện có. Điều quan trọng hơn tên thuật toán là mọi router phải dùng cùng membership snapshot và cùng implementation.

6. Consistent hashing không thay thế replication

Ring chỉ trả lời owner nào chịu trách nhiệm cho một key. Nếu owner hỏng và không có bản sao, dữ liệu vẫn mất hoặc cache vẫn cold. Một thiết kế replicated thường đi tiếp trên ring để chọn các node vật lý khác nhau, hoặc lấy các ứng viên kế tiếp trong bảng xếp hạng rendezvous. Replica count phải là policy riêng.

Không nên chọn hai vnode thuộc cùng máy làm hai replica. Tương tự, ba máy nằm chung rack hoặc availability zone không tạo được khả năng chịu lỗi theo topology. Replica placement cần nhận biết host, rack và zone, đồng thời mô tả điều gì xảy ra khi cụm không đủ failure domain.

• Partitioning quyết định key nằm ở shard logic nào.
• Replication quyết định có bao nhiêu bản sao và đặt chúng ở đâu.
• Consistency quyết định số replica cần đọc/ghi và cách xử lý phiên bản xung đột.
• Failure detection quyết định khi nào một node bị xem là không phục vụ được.

Gộp bốn quyết định vào một hàm locate() khiến hệ thống khó kiểm thử. Hãy tách ring thuần túy khỏi health state và policy đọc/ghi. Với cùng snapshot, hàm định tuyến phải cho kết quả xác định; logic failover mới áp dụng trạng thái động.

7. Membership cần epoch và một nguồn sự thật

Sự cố nguy hiểm xuất hiện khi các router nhìn thấy hai phiên bản membership khác nhau. Router A đã biết node mới, router B chưa biết; cùng một key được ghi vào hai owner mà không có quy trình migration. Nếu mọi process tự thêm hoặc bỏ node chỉ dựa trên health check cục bộ, network partition có thể tạo hai ring hợp lệ theo hai góc nhìn.

Mỗi cấu hình ring nên có một epoch hoặc version tăng đơn điệu, danh sách node với ID ổn định, token/weight, trạng thái và checksum. Một control plane hoặc consensus-backed store công bố snapshot; data plane chỉ áp dụng snapshot hoàn chỉnh sau khi validation. Địa chỉ IP không nên là danh tính node vì IP có thể tái sử dụng.

{
  "epoch": 42,
  "hash_algorithm": "xxh3-64-v1",
  "nodes": [
    {"id": "cache-a", "state": "active", "weight": 1.0},
    {"id": "cache-d", "state": "joining", "weight": 0.25}
  ],
  "checksum": "..."
}

Router phải từ chối snapshot lùi version, log epoch đang dùng và xuất metric tỷ lệ instance theo epoch. Nếu rollout đổi hash algorithm hoặc key canonicalization, cần chạy song song hai phiên bản với quy trình migrate; thay trực tiếp sẽ tương đương remap toàn cụm.

8. Rebalance là một workflow dữ liệu, không phải một lệnh cấu hình

Thêm node vào ring chỉ xác định owner tương lai. Dữ liệu hiện tại vẫn nằm ở owner cũ. Quy trình an toàn thường có các trạng thái joining, streaming, dual-read hoặc dual-write, active, rồi leaving. Tên trạng thái có thể khác, nhưng quyền đọc và ghi ở từng bước phải rõ.

1. Tính trước range/slot sẽ chuyển và ước lượng byte, key, request rate.
2. Thêm node ở trạng thái chưa nhận toàn bộ traffic; kiểm tra disk, network và health.
3. Copy snapshot theo range, sau đó bắt kịp thay đổi phát sinh trong lúc copy.
4. Đọc đối chiếu hoặc checksum để xác nhận dữ liệu đích.
5. Chuyển routing theo từng phần, giới hạn tốc độ và quan sát lỗi, latency, cache miss.
6. Sau cửa sổ an toàn mới xóa bản cũ hoặc đưa node rời cụm.

Với cache có thể tái tạo, không phải lúc nào cũng cần copy toàn bộ. Nhưng cold start vẫn phải được kiểm soát bằng traffic ramp, request coalescing, TTL jitter và giới hạn tải xuống database. Với dữ liệu bền vững, không được xem cache-style lazy fill là migration.

Control plane đổi owner trong vài mili giây; data plane có thể mất nhiều giờ để chuyển byte. Thiết kế đúng phải thừa nhận khoảng cách này.

9. Hot key không được giải quyết bằng phân bố key đều

Hash function tốt giúp số key trên node khá đều, nhưng traffic không nhất thiết đều. Một key cấu hình toàn cục, sản phẩm đang viral hoặc tenant lớn có thể nhận hàng nghìn lần tải trung bình. Vì một key thường có một primary owner, consistent hashing vẫn dồn hot key vào một node.

Giải pháp phụ thuộc semantics: replicate key nóng để đọc, cache nhiều tầng, request coalescing, tách tenant lớn, salting key có kiểm soát cho dữ liệu cộng gộp, hoặc rate limit nguồn tải. Salting không phù hợp nếu thao tác cần đọc/ghi nguyên tử một object duy nhất. Việc tự động nhân bản hot key cũng cần TTL, invalidation và giới hạn để tránh biến một spike thành fan-out write.

Đừng chỉ quan sát key count. Cần đo request rate, byte/s, latency, error, CPU, memory, I/O và top key hoặc top tenant theo cách bảo vệ dữ liệu nhạy cảm. Metric phân bố nên có hệ số lệch giữa node cao nhất và trung vị, không chỉ average toàn cụm.

10. Hash slot thực dụng và bài học từ Redis Cluster

Thay vì đặt từng key trực tiếp lên ring node, một hệ thống có thể băm key vào số lượng slot cố định rồi ánh xạ slot sang node. Redis Cluster dùng 16.384 hash slot và công thức cơ sở CRC16(key) mod 16384. Khi reshard, hệ thống di chuyển slot giữa các node; client duy trì bảng slot-to-node và xử lý redirect trong giai đoạn cấu hình thay đổi.

Lớp slot tạo một mức gián tiếp hữu ích: số bucket logic ổn định dù số máy đổi, control plane có thể chuyển từng nhóm slot, và trạng thái migration dễ biểu diễn hơn so với thay toàn bộ hàm modulo. Redis còn có hash tag: phần nằm trong cặp {...} có thể được dùng để đưa những key liên quan vào cùng slot, phục vụ multi-key operation.

Colocation là một đánh đổi. Đưa mọi key của một tenant lớn vào cùng hash tag có thể tạo hot slot. Hãy chỉ colocate dữ liệu thực sự cần thao tác chung, đặt giới hạn tenant và kiểm tra phân bố slot từ key production đã ẩn danh.

11. Kiểm thử thuật toán và kế hoạch thay đổi cụm

Unit test vài key cố định chưa đủ. Hãy dùng hàng trăm nghìn hoặc hàng triệu key sinh xác định để đo phân bố, churn khi thêm/bớt node, ảnh hưởng của weight và tính ổn định giữa các ngôn ngữ. Golden vector nên chứa byte đầu vào, hash dạng hex, token và owner kỳ vọng để client Java, PHP, Go hay Node.js cho cùng kết quả.

tests:
  same key + same epoch -> same owner
  different clients -> same 64-bit hash
  add one node -> bounded movement
  remove one node -> only its ranges move
  weighted nodes -> observed share near target
  replicas -> distinct hosts and zones
  ring wrap-around -> first token selected
  stale epoch -> rejected or alerted

Fault test phải bao gồm node chết trong lúc streaming, router restart với snapshot cũ, control plane tạm mất kết nối, packet loss, disk đầy và rollback sau khi một phần range đã chuyển. Dữ liệu kiểm thử nên có phân bố size và popularity gần production; một triệu key cùng kích thước không phát hiện được shard chứa vài object rất lớn.

Checklist production

• Key canonicalization, encoding, hash algorithm và quy tắc token được version hóa.
• Node dùng ID ổn định; membership snapshot có epoch và checksum.
• Phân bố được kiểm tra bằng key và traffic đại diện, không chỉ dữ liệu ngẫu nhiên.
• Virtual node hoặc slot count được chọn từ benchmark và chi phí metadata.
• Replica placement tránh trùng host, rack hoặc zone theo failure model.
• Workflow joining/leaving tách rõ copy dữ liệu, bắt kịp ghi và chuyển routing.
• Rebalance có rate limit, pause, resume, rollback và progress metric.
• Hot key có cơ chế phát hiện và xử lý riêng.
• Dashboard hiển thị epoch, ownership, skew, migration throughput và lỗi redirect.
• Golden vector bảo đảm mọi client cho cùng owner với cùng snapshot.

Consistent hashing có giá trị vì nó giới hạn phạm vi xáo trộn khi topology thay đổi, không phải vì nó tự hoàn thiện một hệ thống phân tán. Một triển khai đáng tin cậy phải ghép thuật toán định tuyến xác định với membership có version, replication nhận biết topology và workflow migration có thể quan sát. Khi những phần này được thiết kế cùng nhau, việc thêm hoặc bỏ node trở thành một thay đổi dung lượng có kiểm soát thay vì một đợt remap gây bão cache và rủi ro dữ liệu.

Nguồn tham khảo

• Amazon Science: Dynamo—Amazon's Highly Available Key-value Store
• Redis Documentation: Redis Cluster Specification
• Apache Cassandra Documentation: Dynamo Architecture