Consistent hashing

Consistent hashing là gì

Khi dữ liệu hoặc request phải chia cho nhiều node, bạn cần một hàm trả lời câu hỏi: key này thuộc node nào? Cách dễ nghĩ nhất là node = hash(key) % N. Cách này chạy tốt cho tới ngày bạn thêm hoặc bớt một node.

Consistent hashing là một cách gán key cho node có tính chất sau: khi số node thay đổi, chỉ khoảng 1/N số key phải đổi chỗ. Các key còn lại vẫn nằm yên ở node cũ. Grokking nói tương tự: khi node vào hoặc ra, chỉ một phần nhỏ key cần di chuyển, và đây là lợi ích chính.¹ Ý tưởng chính gồm ba phần:

• Đặt cả node và key lên cùng một vòng tròn giá trị hash, ví dụ từ 0 tới 2^32 - 1.
• Mỗi key thuộc về node đầu tiên gặp được khi đi theo chiều kim đồng hồ từ vị trí của key.
• Mỗi node vật lý xuất hiện ở nhiều vị trí trên vòng (virtual node) để tải chia đều hơn.

Trong thư viện, kỹ thuật này xuất hiện trong thiết kế key-value store dựa trên Dynamo (Grokking ch.10), trong cache client của distributed cache (ch.16) và trong load balancer không giữ trạng thái (ch.8).¹²³ Việc Cassandra, Memcached client hay Redis dùng nó như thế nào thì thư viện chưa có sách.⁴

Vì sao quan trọng trong phỏng vấn

Mỗi khi bạn nói "shard theo user_id" hoặc "dùng nhiều node cache", người phỏng vấn có thể hỏi tiếp: thêm node thì sao, một node chết thì sao? Nếu bạn dùng modulo, câu trả lời thật là "gần như toàn bộ cache bị miss cùng lúc" hoặc "phải di chuyển gần hết dữ liệu": Grokking ch.9 nói với hash mod n, thêm hoặc bớt node làm số partition của mọi node đổi và nhiều dữ liệu phải chuyển.⁵ Đó là điểm yếu dễ bị bắt.

Biết consistent hashing giúp bạn:

• Giải thích cách scale cache hoặc kho key-value mà không gây bão miss vào database.
• Nói được vì sao dùng virtual node, và replica được đặt ở đâu.
• So sánh với cách chia theo số partition cố định hoặc partition động.⁶ Redis Cluster slot và partition được quản lý của DynamoDB là ví dụ ngoài thư viện.⁴

Bạn không cần thuộc thuật toán chi tiết. Bạn cần nói được vấn đề, cách vòng hash giải quyết, và cái giá phải trả.

Vấn đề của hash modulo

Giả sử có 4 node cache, gán key bằng hash(key) % 4. Thêm node thứ 5, công thức thành hash(key) % 5. Một key chỉ giữ nguyên node khi h % 4 == h % 5, xác suất khoảng 1/5. Nghĩa là khoảng 80% key đổi node. Đây là phép tính xác suất từ giả định hash phân bố đều; Grokking dùng ví dụ cụ thể hash 1235 chuyển từ node 0 (5 node) sang node 5 (6 node).⁵

Cột consistent hashing là xấp xỉ 1/(N+1) theo tính chất "chỉ phần nhỏ key di chuyển" của Grokking.¹ Với cache, 80% key đổi node tương đương 80% cache miss trong vài phút, toàn bộ tải dội về database (suy luận của khoá học). Với kho dữ liệu, đó là việc chép lại gần hết dữ liệu qua mạng. Cả hai đều không chấp nhận được ở quy mô lớn.

Cách hoạt động: hash ring và virtual node

Vòng hash

Hash ID của mỗi node ra một số trong khoảng [0, 2^32) và đặt lên vòng. Với mỗi key, hash ra một số, rồi đi theo chiều kim đồng hồ tới node đầu tiên. Node đó sở hữu đoạn vòng nằm giữa nó và node đứng trước. Grokking mô tả: vòng hash từ 0 tới n-1, hash ID của node và của request đặt lên vòng, request do node đầu tiên gặp theo chiều kim đồng hồ phục vụ.¹ Khoảng 2^32 là ví dụ của khoá học; sách nói Dynamo dùng MD5 sinh khóa 128 bit.⁷

Khi thêm node E vào giữa B và C, chỉ những key nằm trong đoạn từ B tới E chuyển từ C sang E. A, B, D không bị ảnh hưởng. Sách: khi node mới vào vòng, node kế tiếp ngay sau nó bị ảnh hưởng và chia dữ liệu cho node mới, các node khác không bị ảnh hưởng.¹ Khi C chết, các key của C chuyển sang node kế tiếp là D (suy ra từ cùng quy tắc).

Hotspot và virtual node

Với vài node đặt ngẫu nhiên, các đoạn trên vòng có độ dài rất chênh lệch. Một node có thể giữ 40% key trong khi node khác giữ 10% (số minh họa). Grokking nói tải trong thực tế không chia đều và gọi đây là hotspot: một node nhận phần lớn dữ liệu và request, làm giảm hiệu năng cả hệ thống.⁸

Cách sửa là virtual node (vnode). Mỗi node vật lý được hash ra nhiều vị trí, ví dụ nodeA#0, nodeA#1, ... nodeA#127. Vòng bây giờ có hàng trăm điểm, mỗi node vật lý sở hữu nhiều đoạn nhỏ rải khắp vòng. Sách dùng nhiều hàm hash cho cùng một node (ví dụ ba hàm cho ba vị trí) thay vì thêm hậu tố #i; kết quả như nhau.⁹ Lợi ích:

• Tải đều hơn. Sách: với virtual node, mỗi server có nhiều vị trí nên tải request đồng đều hơn.⁹ Con số "độ lệch giảm theo căn bậc hai số vnode" và "100–200 vnode còn lệch 5–10%" là ước lượng của khoá học, cần đo lại.¹⁰
• Node mạnh nhận nhiều hơn. Máy có gấp đôi RAM thì cho gấp đôi số vnode. Sách: node mạnh gấp đôi có thể nhận nhiều vnode hơn.¹¹
• Node chết thì tải chia cho nhiều node. Sách: khi node hỏng hoặc bảo trì, tải được chia đều cho các node khác.¹¹

Replication dọc vòng

Để chịu được node chết, mỗi key được lưu ở n node. Node sở hữu key là coordinator, nó chép key sang n - 1 node kế tiếp theo chiều kim đồng hồ. Danh sách này gọi là preference list. Vì có vnode, hai vị trí liền nhau có thể thuộc cùng một máy vật lý, nên khi dựng preference list phải bỏ qua các vnode thuộc máy đã có trong danh sách. Cả ba ý này theo mục "Data replication" của Grokking ch.10.¹²

Trong thực tế, preference list còn bỏ qua node nằm cùng rack hoặc cùng availability zone để một sự cố hạ tầng không lấy mất cả ba bản sao (khuyến nghị của khoá học; Grokking chỉ nói cần replicate qua nhiều data center để chịu sự cố cả data center).¹³ Khi một node trong danh sách tạm chết, kho kiểu Dynamo ghi tạm sang node kế tiếp kèm gợi ý (hinted handoff) rồi trả lại khi node cũ sống lại: sách gọi đây là sloppy quorum cộng hinted handoff.¹³ Phần đọc ghi theo quorum trên các bản sao này được giải thích trong bài CAP và nhất quán.

Cài đặt ngắn bằng TypeScript

Ring được lưu dưới dạng mảng các điểm đã sắp xếp. Tìm node cho một key là tìm nhị phân điểm đầu tiên có hash lớn hơn hoặc bằng hash của key, quay về đầu mảng nếu vượt cuối. Phần cài đặt là minh họa của khoá học, hiện thực quy tắc "node đầu tiên theo chiều kim đồng hồ" trong Grokking ch.10.¹ Grokking ch.16 nhắc tìm key theo consistent hashing có độ phức tạp O(log N) với N là số shard, khớp với tìm nhị phân.¹⁴

import { createHash } from "node:crypto";

const hash32 = (s: string) =>
  createHash("md5").update(s).digest().readUInt32BE(0);

class HashRing {
  private points: { h: number; node: string }[] = [];

  constructor(nodes: string[], private vnodes = 128) {
    nodes.forEach((n) => this.add(n));
  }

  add(node: string) {
    for (let i = 0; i < this.vnodes; i++) {
      this.points.push({ h: hash32(`${node}#${i}`), node });
    }
    this.points.sort((a, b) => a.h - b.h);
  }

  remove(node: string) {
    this.points = this.points.filter((p) => p.node !== node);
  }

  private indexOf(key: string): number {
    const h = hash32(key);
    let lo = 0, hi = this.points.length;
    while (lo < hi) {
      const mid = (lo + hi) >> 1;
      if (this.points[mid].h < h) lo = mid + 1;
      else hi = mid;
    }
    return lo === this.points.length ? 0 : lo;
  }

  get(key: string): string {
    return this.points[this.indexOf(key)].node;
  }

  // preference list: n node vật lý khác nhau theo chiều kim đồng hồ
  replicas(key: string, n: number): string[] {
    const total = new Set(this.points.map((p) => p.node)).size;
    const out: string[] = [];
    let i = this.indexOf(key);
    while (out.length < Math.min(n, total)) {
      const node = this.points[i].node;
      if (!out.includes(node)) out.push(node);
      i = (i + 1) % this.points.length;
    }
    return out;
  }
}

Kiểm tra nhanh số key phải di chuyển khi thêm node:

const ring = new HashRing(["a", "b", "c", "d"]);
const keys = Array.from({ length: 100_000 }, (_, i) => `user:${i}`);
const before = keys.map((k) => ring.get(k));
ring.add("e");
const moved = keys.filter((k, i) => ring.get(k) !== before[i]).length;
console.log(moved / keys.length); // khoảng 0.2

Thay ring.get(k) bằng hash32(k) % 4 rồi % 5, kết quả sẽ khoảng 0,8. Đây là thí nghiệm nhỏ nên làm một lần để nhớ con số.

So sánh các cách chia key

Các dòng modulo, hash ring, slot cố định (số partition cố định) và range theo Grokking ch.9 và ch.10.⁵⁶¹ Với DynamoDB, Microservices Patterns §7.4.2 nói partition key được dùng để chọn partition lưu item.¹⁶ Cột ưu và nhược là tóm tắt của khoá học; riêng dòng HRW và Redis Cluster 16.384 slot chưa có sách.¹⁵

Hai cách "slot cố định" và "hash ring" giải quyết cùng một vấn đề. Slot cố định thực chất là chia vòng thành S đoạn bằng nhau ngay từ đầu, rồi gán đoạn cho node (nhận xét của khoá học). Trong phỏng vấn, nói được điểm chung này là đủ.

Con số và kích thước

Các con số dưới đây là giả định và ước lượng của khoá học, không phải số trong sách; Grokking cũng không đưa số vnode cụ thể.¹⁷⁹

• Số vnode mỗi node: 64–256 là khoảng hay gặp (ước lượng, cần đo lại).¹⁰
• Bộ nhớ của ring: 100 node × 128 vnode = 12.800 điểm, mỗi điểm vài chục byte. Toàn bộ ring dưới 1 MB, tra cứu bằng tìm nhị phân mất khoảng 14 bước (số học từ giả định).
• Dữ liệu phải chuyển khi thêm node: khoảng tổng dữ liệu ÷ (N + 1). Cụm 10 node giữ 20 TB, thêm 1 node thì chuyển khoảng 1,8 TB. Ở tốc độ giới hạn 100 MB/s để không ảnh hưởng tải chính, mất khoảng 5 giờ (ước lượng).
• Cache cluster: thêm 1 node vào cụm 10 node cache với tỷ lệ hit 95% thì tạm thời khoảng 9% key bị miss. Database phải chịu thêm lượng đọc đó trong vài phút cho tới khi cache ấm lại. Với modulo, gần như toàn bộ đọc dội xuống database (suy luận của khoá học từ tính chất di chuyển ít key).¹
• Replication factor: 3 là mặc định phổ biến (Grokking dùng n = 3 trong ví dụ, và nói n là tham số cấu hình được).¹² Dung lượng thô cần = dữ liệu × 3 ÷ mức lấp đầy mục tiêu (thường 50–70% để còn chỗ compaction và rebalance, giả định của khoá học).

Sai lầm hay gặp

• Quên vnode. Ring chỉ có 4 điểm thì độ lệch tải rất lớn. Luôn nói kèm virtual node.⁸⁹
• Đặt các bản sao lên cùng một máy vật lý. Preference list phải bỏ qua vnode trùng máy, tốt hơn nữa là trùng zone.¹²
• Đổi hàm hash hoặc cách đặt tên vnode giữa chừng. Mọi client phải dùng cùng hàm hash và cùng danh sách node. Nếu hai client có hai view khác nhau về ring, chúng sẽ đọc ghi ở hai node khác nhau. Grokking ch.9 cũng nêu thách thức chính của routing là các thành phần biết được cập nhật phân vùng, và dùng ZooKeeper để theo dõi.¹⁹
• Không tính chi phí di chuyển dữ liệu. "Chỉ 1/N key di chuyển" vẫn có thể là vài TB. Cần giới hạn băng thông rebalance và theo dõi tiến độ.
• Dùng hash ring khi cần truy vấn theo khoảng. Hash làm mất thứ tự key. Nếu cần "lấy mọi đơn hàng từ ngày A tới ngày B", cần range partition hoặc index phụ.²⁰

Khi nào nhắc tới trong phỏng vấn

Câu nói mẫu: "Tôi chia key cho các node bằng consistent hashing với khoảng 128 vnode mỗi node, replication factor 3, replica nằm ở 3 zone khác nhau. Thêm node chỉ di chuyển khoảng 1/N dữ liệu. Key nóng tôi xử lý riêng bằng cache cục bộ."

Bảng và câu mẫu trên là tóm tắt của khoá học; nền tảng lý thuyết là Grokking ch.10 và ch.16.¹²

Đọc tiếp: Sharding để chọn shard key, Cassandra và DynamoDB để xem hai hệ thống thật dùng ý tưởng này, Caching cho phần cache.

Nguồn trích dẫn

1. Grokking Modern System Design · ch.10 Key-value Store · bài "Ensure Scalability and Replication", mục "Consistent hashing". ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶ ↩⁷ ↩⁸ ↩⁹

2. Grokking Modern System Design · ch.16 Distributed Cache · bài "Detailed Design of a Distributed Cache" (cache client dùng consistent hashing để chọn cache server). ↩ ↩²

3. Grokking Modern System Design · ch.8 Load Balancers · bài "Load Balancers" (stateless load balancing dùng consistent hashing) và "Advanced Details of Load Balancers" (Tier-2 LBs). ↩

4. Chưa có nguồn trong thư viện: cách Cassandra, Memcached client, Redis Cluster, DynamoDB chia key không có trong sách của thư viện; chỉ nêu tên như ví dụ. ↩ ↩²

5. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Rebalance the partitions" → "Avoid hash mod n". ↩ ↩² ↩³

6. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Rebalance the partitions" (Fixed number of partitions, Dynamic partitioning) và "Consistent hashing". ↩ ↩²

7. Grokking Modern System Design · ch.10 Key-value Store · phần mở đầu thiết kế, Note về MD5 và Dynamo. ↩

8. Grokking Modern System Design · ch.10 Key-value Store · bài "Ensure Scalability and Replication", mục "Consistent hashing" (đoạn về hotspot). ↩ ↩²

9. Grokking Modern System Design · ch.10 Key-value Store · bài "Ensure Scalability and Replication", mục "Use virtual nodes". ↩ ↩² ↩³ ↩⁴

10. Chưa có nguồn trong thư viện: số vnode điển hình và độ lệch tải theo số vnode là ước lượng của khoá học, sách không đưa số cụ thể. ↩ ↩²

11. Grokking Modern System Design · ch.10 Key-value Store · bài "Ensure Scalability and Replication", mục "Advantages of virtual nodes". ↩ ↩²

12. Grokking Modern System Design · ch.10 Key-value Store · bài "Ensure Scalability and Replication", mục "Data replication" (coordinator, preference list). ↩ ↩² ↩³

13. Grokking Modern System Design · ch.10 Key-value Store · bài về fault tolerance, mục "Handle temporary failures" (sloppy quorum, hinted handoff). ↩ ↩²

14. Grokking Modern System Design · ch.16 Distributed Cache · bài "Evaluation of a Distributed Cache Design", mục "High performance". ↩

15. Chưa có nguồn trong thư viện: rendezvous hashing và số slot của Redis Cluster không có trong các sách của thư viện. ↩ ↩²

16. Microservices Patterns (file .zip, tải về giải nén) · ch.7 · §7.4.2 Data modeling and query design with DynamoDB (tr. 245–246). ↩

17. Quy tắc ước lượng của khoá học, xem bài Chọn server. ↩

18. Grokking Modern System Design · ch.16 Distributed Cache · bài "Evaluation of a Distributed Cache Design", mục "Scalability" (hotkeys). ↩

19. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Request routing" và "ZooKeeper". ↩

20. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Hash-based sharding" (Disadvantages: không range query). ↩