Consistent hashing & rebalancing — thêm/bớt node ít xáo trộn

TL;DR: Hash partition (bài trước) phân bố đều, nhưng cách hash ngây thơ hash(key) mod N (N = số node) có một tật nghiêm trọng: đổi N là gần như mọi khoá đổi partition — thêm một node phải di chuyển gần hết dữ liệu, làm nghẽn cả cụm. Consistent hashing sửa điều đó: đặt cả node lẫn khoá lên một "vòng" hash, mỗi khoá thuộc về node kế tiếp trên vòng; thêm/bớt một node chỉ ảnh hưởng phần khoá kề node đó, không đụng phần còn lại. Virtual node (mỗi node vật lý = nhiều điểm trên vòng) làm tải cân hơn và cho node mạnh/yếu gánh khác nhau. Rebalancing là quá trình di chuyển partition khi cụm co giãn — làm sao vừa cân tải vừa ít di chuyển vừa không chặn dịch vụ.

Chọn hash partition xong, câu hỏi vận hành lớn nhất là: cụm sẽ co giãn (thêm/bớt node), lúc đó dữ liệu xáo trộn thế nào? Nếu mỗi lần thêm một máy phải chép lại gần hết dữ liệu qua mạng, việc mở rộng trở thành ác mộng. Bài này giải đúng bài toán đó.

1. Analogy — chia khách theo vị trí trên một vòng tròn

Tưởng tượng các node đứng rải trên một vòng tròn, và mỗi khách (khoá) cũng được đặt vào một điểm trên vòng theo hash. Quy tắc: mỗi khách thuộc về node đầu tiên gặp khi đi theo chiều kim đồng hồ từ vị trí của khách.

Giờ một node rời đi: chỉ những khách ngay trước nó trên vòng cần chuyển sang node kế tiếp — mọi khách khác không đổi node. Một node mới vào giữa hai node cũ: nó chỉ nhận phần khách nằm trong cung nó vừa chen vào — phần còn lại yên vị. Đây là điểm khác biệt cốt lõi so với "chia theo số dư": ở đó, thêm/bớt một node đổi số dư của mọi khách.

flowchart LR
  subgraph MOD["hash mod N — them 1 node"]
    M1["N: 4 -> 5"] --> M2["GAN MOI khoa doi partition<br/>(di chuyen khong lo)"]
  end
  subgraph CH["Consistent hashing — them 1 node"]
    C1["Chen 1 diem tren vong"] --> C2["Chi khoa cung KE di chuyen<br/>(~1/N)"]
  end

2. Vì sao hash(key) mod N hỏng khi đổi N?

Cách hash ngây thơ: partition = hash(key) mod N. Khi N cố định, nó phân bố đều — ổn. Nhưng thêm một node (N → N+1) đổi số chia, nên hash(key) mod N và hash(key) mod (N+1) cho kết quả khác nhau với gần như mọi khoá.

hash(key)=116:
  mod 4 = 0  -> mod 5 = 1   <- DOI node!
hash(key)=117:
  mod 4 = 1  -> mod 5 = 2   <- DOI node!
hash(key)=118:
  mod 4 = 2  -> mod 5 = 3   <- DOI node!
hash(key)=119:
  mod 4 = 3  -> mod 5 = 4   <- DOI node!
hash(key)=120:
  mod 4 = 0  (node 0)
  mod 5 = 0  (node 0)  -> may man khong doi
=> 4/5 khoa (80%) roi vao truong hop doi -> di chuyen GAN HET du lieu.
Tong quat: mot khoa GIU nguyen bucket khi (h mod 4) == (h mod 5), va dieu
nay chi dung khi h ≡ 0,1,2,3 (mod 20, voi 20 = lcm(4,5)) -> 4/20 = 20% giu,
con lai 80% phai doi node.

Kết quả: thêm một node đáng lẽ chỉ cần "san bớt" một phần dữ liệu, nhưng mod N bắt di chuyển gần hết — băng thông mạng bùng nổ, dịch vụ chậm suốt quá trình. Đây là lý do không hệ phân tán thật nào dùng mod N trần.

3. Consistent hashing — chỉ di chuyển phần kề

Recall cho bạn kết luận; mục này dẫn lại cơ chế ngay tại chỗ vì đó chính là objective của bài — bài phải tự đứng được, không bắt người học nhảy sang track khác mới hiểu.

Đặt cả node lẫn khoá lên một vòng. Lấy một hàm hash có miền giá trị lớn (ví dụ 0 tới 2^32-1) rồi "uốn" miền đó thành vòng tròn (giá trị lớn nhất nối lại 0). Hash mỗi node (theo id/địa chỉ) ra một điểm trên vòng; hash mỗi khoá ra một điểm trên vòng. Quy tắc sở hữu: mỗi khoá thuộc node đầu tiên gặp khi đi theo chiều kim đồng hồ từ điểm của khoá — tức mỗi node "sở hữu" cung chạy từ node liền trước (ngược chiều kim) tới chính nó.

Vong hash (mien 0..2^32-1 uon thanh vong tron):
   ...A........B............C......D...   (roi quay lai A)
   khoa k1 roi trong cung (A..B]  -> thuoc B (node ke chieu kim dong ho)
   khoa k2 roi trong cung (B..C]  -> thuoc C
=> B so huu cung (A..B]; C so huu cung (B..C]; ...

Vì sao thêm một node chỉ di chuyển ~1/N khoá? Vị trí một node trên vòng chỉ phụ thuộc hash(node), không phụ thuộc N. Thêm node X = hash X ra một điểm mới rồi chèn vào giữa hai node cũ đang kề nhau, ví dụ giữa B và C. X chỉ "cướp" phần cung nằm giữa B và X (vốn thuộc C): chỉ các khoá rơi vào đoạn đó chuyển từ C sang X. Mọi cung khác — cung (A..B], phần (X..C] còn lại, cung (C..D]... — không đổi chủ. Với N node rải tương đối đều, mỗi node giữ trung bình ~1/N vòng, nên node mới cắt đúng một cung → trung bình chỉ ~1/N lượng khoá phải di chuyển, và chỉ một node cũ phải nhường. Bớt node đối xứng: xoá điểm của nó, cung của nó dồn sang node kế theo chiều kim.

Đây chính là cơ chế các store kiểu Dynamo/Cassandra dùng để chọn node giữ mỗi khoá (và cả các bản nhân của nó — nhớ replication + partition đi cùng nhau: R bản của một khoá thường là R node kế tiếp trên vòng, với R = replication factor, khác N = tổng số node cụm).

4. Virtual node — cân tải và xử lý node không đều

Consistent hashing thuần có hai vấn đề: (1) với ít node, các cung trên vòng không đều → tải lệch; (2) khi một node chết, toàn bộ cung của nó dồn sang một node kế — node đó đột ngột gánh gấp đôi.

Virtual node (vnode) sửa cả hai: mỗi node vật lý được đặt lên vòng ở nhiều điểm (ví dụ mỗi node = 100–200 vnode). Nhờ nhiều điểm rải khắp vòng, cung của mỗi node vật lý là tổng nhiều mảnh nhỏ rải đều → tải cân hơn; và khi một node chết, các mảnh của nó phân sang nhiều node kế khác nhau, không dồn một chỗ.

Khong vnode: node B chet -> toan bo cung B -> node C (C gap doi tai)
Co vnode   : B = {b1,b2,...,b100} rai khap vong
             B chet -> b1->C, b2->A, b3->D, ... -> tan deu, khong ai gap doi

Vnode còn cho node không đều: máy mạnh gấp đôi thì cấp gấp đôi số vnode → nhận gấp đôi tải, tự nhiên.

5. Rebalancing — di chuyển partition khi cụm co giãn

Rebalancing là quá trình chuyển partition giữa các node khi thêm/bớt. Mục tiêu: (a) tải cân sau khi xong, (b) di chuyển ít nhất có thể, (c) không chặn dịch vụ trong lúc chuyển. Một cách hay bị hiểu nhầm là "chia lại động theo mod N" — sai như mục 2.

Chiến lược phổ biến (và đơn giản đáng ngạc nhiên): cố định SỐ partition, chọn nhiều hơn số node hẳn (ví dụ 1000 partition cho 10 node = 100 partition/node). Mỗi khoá thuộc một partition cố định (partition không đổi khi thêm node); rebalancing chỉ là gán lại vài partition nguyên khối cho node mới. Thêm node thứ 11 → lấy bớt vài partition từ mỗi node cũ giao cho node mới, di chuyển đúng phần đó. Vì số partition không đổi, ánh xạ khoá→partition ổn định; chỉ ánh xạ partition→node thay đổi.

Đây là một chiến lược độc lập, song song với consistent hashing ở mục 3 — không phải cách "hiện thực hoá" consistent hashing, mà là một lối tiếp cận khác nhắm cùng mục tiêu ít-di-chuyển (hash trực tiếp node+khoá lên vòng, so với hash khoá vào B partition cố định rồi gán partition→node).

6. Pitfall — rebalancing tự động, toàn bộ, đúng lúc tải cao

❌ Dung hash(key) mod N cho phan partition -> them 1 node -> di chuyen gan het
   -> mang nghen, dich vu cham hang gio

❌ Rebalancing hoan toan tu dong + tuc thi khi phat hien node "cham"
   -> node chi tam cham (GC/mang) bi tuong chet -> tu dong chuyen du lieu di
   -> cham hon -> lai tuong chet node khac -> hieu ung domino

7. 📚 Deep Dive

8. Liên hệ các bài khác

• Bài 01 — Range vs hash: consistent hashing là cách hiện thực hash partition sao cho co giãn rẻ — nối thẳng từ đánh đổi bài trước.
• Module 2 — Leaderless: Dynamo dùng consistent hashing để chọn nhóm node giữ mỗi khoá (partition) + quorum để nhân bản — partition và replication gắn ở đây.
• Bài 04 — Request routing: khi partition di chuyển lúc rebalancing, client phải biết mapping mới — bài routing.
• Module 5 — Partial failure: rebalancing tự động dễ nhầm "chậm" với "chết" — vì sao co giãn cần kiểm soát.

9. Tóm tắt

• hash(key) mod N phân bố đều nhưng đổi N là gần mọi khoá đổi node → di chuyển khổng lồ; không dùng được cho cụm co giãn.
• Consistent hashing: node + khoá trên một vòng, khoá thuộc node kế; thêm/bớt node chỉ di chuyển phần kề (~1/N), không đụng phần còn lại.
• Virtual node: mỗi node = nhiều điểm trên vòng → tải cân hơn, node chết tán đều sang nhiều node, và node mạnh/yếu nhận tải khác nhau.
• Rebalancing: cân tải + ít di chuyển + không chặn dịch vụ; chiến lược thực dụng = cố định số partition (nhiều hơn số node), gán lại partition nguyên khối cho node mới.
• Anti-pattern: mod N (di chuyển khổng lồ) hoặc rebalancing tự động tức thì (nhầm chậm với chết → domino). Co giãn nên có kiểm soát.

10. Tự kiểm tra

Bài tiếp theo: Secondary index phân mảnh — local vs global