Bài 8: Sharding & Consistent Hashing

Bài 7 giải quyết tầng đọc rất rẻ. Nhưng nó không giúp gì cho hai thứ: throughput ghi — mọi lệnh ghi vẫn dồn về một primary — và dung lượng — mọi replica đều chứa trọn bộ dữ liệu. Khi một trong hai thứ đó vượt giới hạn một máy, không còn cách nào ngoài chia dữ liệu ra: sharding.

Đây là bước đắt nhất trong toàn bộ series, và cái giá không phải tiền mà là độ phức tạp vĩnh viễn: mất transaction xuyên shard, mất JOIN, phân trang trở nên khó, và mọi truy vấn không mang shard key đều thành quét toàn bộ.

Hai phép đo trong bài đáng chú ý. Thứ nhất, tỉ lệ dữ liệu phải di trú khi thêm một shard: modulo hashing từ 4 lên 5 shard làm 79,97% dữ liệu phải chuyển chỗ, còn consistent hashing chỉ 18,78% — và cả hai khớp gần như hoàn hảo với công thức lý thuyết. Thứ hai, một shard key lệch làm p99 tệ hơn 10,3 lần trong khi p50 lại tốt hơn — hotspot sống hoàn toàn ở phần đuôi.

8.1 Khi nào buộc phải shard — và vì sao nên là bước cuối

Thứ tự ưu tiên đúng, từ rẻ tới đắt. Mỗi bước chỉ nên đi khi bước trước đã hết tác dụng:

Ba dấu hiệu cho thấy bạn thật sự cần shard, chứ không phải chỉ cảm thấy cần:

8.2 Chọn shard key — và một phép đo suýt cho kết luận ngược

Shard key tốt phải đạt cả ba điều, và điều thứ ba là điều hay bị bỏ qua nhất:

Đo thật: shard key tốt so với shard key lệch

Lab dựng hai shard PostgreSQL độc lập hoàn toàn — không replication, không biết gì về nhau — và một router trong app quyết định key nào đi shard nào. Chế độ skew mô phỏng đúng tình huống "một tenant khổng lồ": 95% request dùng cùng một shard key.

24 kết nối, 12 giây, 20.000 key khác nhau, mỗi shard giới hạn 1 CPU, hai lần lặp:

Shard key tốt cho +32% throughput. Nhưng hãy đọc kỹ ba dòng percentile: shard key lệch có p50 và p95 tốt hơn, rồi p99 đột ngột tệ hơn 10,3 lần. Hotspot không làm chậm phần lớn request — nó dồn toàn bộ thiệt hại vào phần đuôi.

Đây là lần thứ ba trong series cùng một hình mẫu xuất hiện: ở Bài 3 round robin cho biểu đồ cân bằng nhưng p95 tệ hơn 340 lần; ở Bài 5 single-flight làm p50 tệ hơn nhưng cắt đuôi 11 lần; ở đây shard key lệch thắng ở p50 và p95 rồi thua 10 lần ở p99. Nếu dashboard của bạn chỉ có trung bình và p95 thì cả ba lần bạn đều kết luận ngược.

Router shard trong lab, đầy đủ như mã đang chạy:

// FNV-1a, then mixed with MurmurHash3's fmix32.
// Why the mixing step is needed: FNV-1a has POOR avalanche for short, similar strings
// ('user:1', 'user:2'...), so consecutive keys land on the same shard in clumps.
// The fmix32 step is cheap and removes that effect entirely.
function shardHash(key) {
  let h = 2166136261;
  for (let i = 0; i < key.length; i++) {
    h ^= key.charCodeAt(i);
    h = Math.imul(h, 16777619);
  }
  h ^= h >>> 16;
  h = Math.imul(h, 2246822507);
  h ^= h >>> 13;
  h = Math.imul(h, 3266489909);
  h ^= h >>> 16;
  return h >>> 0;
}

// WARNING: this is modulo hashing. Simple, but read section 8.3 before using it for
// real — adding one shard means migrating nearly all of the data.
function pickShard(shardKey) {
  return shardHash(String(shardKey)) % pgShards.length;
}

8.3 Modulo hashing và thảm hoạ resharding

Cách chia đơn giản nhất là hash(key) % N với $N$ là số shard. Nó ngắn, dễ hiểu, phân bố đều, và chính là cách router trong lab đang làm. Vấn đề xuất hiện đúng vào ngày bạn thêm shard thứ $N+1$.

Một key chỉ giữ nguyên chỗ nếu $h \bmod N = h \bmod (N+1)$. Theo định lý số dư Trung Hoa, khi $N$ và $N+1$ nguyên tố cùng nhau — mà hai số liên tiếp thì luôn vậy — cặp $(h \bmod N,\ h \bmod (N+1))$ phân bố đều trên $N(N+1)$ khả năng. Số cặp thoả điều kiện giữ nguyên là $N$, nên:

$$P(\text{stay}) = \frac{N}{N(N+1)} = \frac{1}{N+1} \quad\Rightarrow\quad P(\text{move}) = \frac{N}{N+1}$$

Lưu ý con số này là $N/(N+1)$, không phải $(N-1)/N$ như thường bị trích dẫn. Chạy thật với 100.000 key, so cả hai thuật toán, consistent hashing dùng 150 virtual node:

Modulo khớp lý thuyết tới hai chữ số thập phân ở mọi hàng. Và con số đáng nhớ nằm ở hàng 4 → 5: thêm một shard vào một hệ thống bốn shard buộc 80% dữ liệu phải chuyển chỗ. Với 16 shard thì con số là 94% — càng nhiều shard, thêm một shard càng tệ.

Consistent hashing sát với $1/(N+1)$ nhưng lệch rõ hơn ở $N$ nhỏ (37,19% so với 33,33% lý thuyết khi 2 → 3). Lý do: với ít node, vị trí các điểm băm trên vòng có phương sai lớn, nên tỉ lệ thực tế dao động quanh giá trị kỳ vọng. Càng nhiều node và càng nhiều virtual node thì càng khớp.

8.4 Consistent hashing và virtual node

Ý tưởng: thay vì băm key ra chỉ số shard, hãy băm cả key và cả tên shard ra cùng một không gian — một vòng tròn 32 bit. Mỗi key thuộc về shard đầu tiên gặp được khi đi theo chiều kim đồng hồ. Thêm một shard chỉ chiếm lấy phần cung nằm ngay trước nó, nên chỉ những key trong cung đó phải di trú.

Bảng đầy đủ, cùng 8 node và 100.000 key (lý tưởng là 12.500 key mỗi node):

Hàng đầu tiên là lý do virtual node tồn tại: với một điểm băm mỗi node, một shard nhận 66 key trong khi một shard khác nhận 25.465 — chênh 386 lần cho một thuật toán vẫn thường được giới thiệu là "phân bố đều".

Toàn bộ hai bảng trên chạy lại được trong vài giây, không cần Docker. Lưu ý nhỏ để khỏi hoảng: Node sẽ in trước một cảnh báo MODULE_TYPELESS_PACKAGE_JSON — đó chỉ là vì package.json của repo không khai "type": "module", kết quả bên dưới vẫn đúng.

# No Docker needed — just node
cd blog/sysdesign
node --input-type=module -e "
import { compareAddNode, makeKeys, HashRing } from './sysdesign-hashring.js';
const keys = makeKeys(100000);
for (const n of [2,3,4,8,16]) {
  const nodes = Array.from({length:n},(_,i)=>'s'+(i+1));
  const r = compareAddNode(keys, nodes, 's'+(n+1), 150);
  console.log(n+'->'+(n+1),
    'modulo', (r.modulo.ratio*100).toFixed(2)+'%',
    '(theory', ((n/(n+1))*100).toFixed(2)+'%)',
    '| consistent', (r.consistent.ratio*100).toFixed(2)+'%',
    '(theory', ((1/(n+1))*100).toFixed(2)+'%)');
}
for (const v of [1,2,10,150,500]) {
  const ring = new HashRing({ vnodes: v });
  for (const n of ['s1','s2','s3','s4','s5','s6','s7','s8']) ring.addNode(n);
  const d = ring.loadDistribution(keys);
  console.log(v+' vnode: min', d.min, 'max', d.max,
    'spread', (d.spread*100).toFixed(1)+'%');
}
"

# And the self-test suite of 42 assertions, which covers the hash ring too
node sysdesign-engine-selftest.mjs

8.5 Hệ quả ở tầng ứng dụng — phần đắt thật sự

Chọn được shard key tốt và dùng consistent hashing chỉ giải quyết phần hạ tầng. Cái đắt nằm ở tầng ứng dụng, vì bốn thứ bạn vẫn coi là hiển nhiên nay không còn nữa.

Còn một việc nữa mà không có lời khuyên nào làm cho dễ: phân trang xuyên shard. Muốn lấy "20 dòng mới nhất" trên 8 shard, bạn phải lấy 20 dòng mới nhất từ mỗi shard (160 dòng), gộp, sắp xếp, rồi cắt 20. Trang thứ hai thì phải lấy 40 mỗi shard, và trang thứ 100 thì mỗi shard phải trả 2.000 dòng để cuối cùng dùng 20. Chi phí tăng theo số trang, không theo số dòng cần.

Cách thoát thông thường là bỏ phân trang theo số trang và chuyển sang phân trang theo con trỏ (cursor/keyset): "cho tôi 20 dòng sau mốc này". Nó cắt được chi phí tăng theo trang, nhưng đổi lại người dùng không nhảy tới trang 100 được nữa — một thay đổi sản phẩm, không chỉ là thay đổi kỹ thuật. Đây là dạng đánh đổi rất đặc trưng của sharding: giới hạn hạ tầng đi ngược lên và định hình cả tính năng.

Tự làm lại phép đo shard

cd blog/sysdesign/sysdesign-lab
docker compose --profile shard up -d   # two INDEPENDENT PostgreSQL shards + the app router

# Check that the router really does distribute
for k in a b c d e f; do curl -s "http://localhost:3001/shard?key=$k&mode=good"; echo; done

# --- GOOD shard key ---
./tools/cache-stats.sh reset
docker compose run --rm loadgen loadgen.js --url "http://lb:8080/shard?mode=good" \
  -c 24 -d 12 -w 2 --json --key-space 20000
./tools/cache-stats.sh          # look at the SHARD line + the spread

# --- SKEWED shard key (95% of requests share one shard key) ---
./tools/cache-stats.sh reset
docker compose run --rm loadgen loadgen.js --url "http://lb:8080/shard?mode=skew" \
  -c 24 -d 12 -w 2 --json --key-space 20000
./tools/cache-stats.sh

# IMPORTANT: if you drop the `cpus: '1.0'` limit on the two shards in docker-compose.yml
# the result INVERTS — the skewed key will look faster. The reason is in section 8.2.

Tóm lại

Sharding là bước cuối vì nó là bước duy nhất có chi phí vĩnh viễn: mất JOIN, mất transaction xuyên shard, phân trang thành bài toán riêng. Trước nó còn bốn bước rẻ hơn, và câu hỏi kiểm tra luôn là "bạn đã đo và biết chính xác cái gì đang bão hoà chưa".

Modulo hashing đơn giản nhưng thêm một shard buộc $N/(N+1)$ dữ liệu di trú — đo được 79,97% khi đi từ 4 lên 5 shard, khớp lý thuyết tới hai chữ số. Consistent hashing hạ con số đó xuống 18,78%, nhưng chỉ khi có virtual node: không có vnode, một shard nhận 66 key trong khi shard khác nhận 25.465.

Và bài học về đo lường lặp lại lần thứ ba trong series: shard key lệch có p50 và p95 tốt hơn shard key tốt, rồi p99 tệ hơn 10,3 lần. Cộng thêm một bài học mới: lần đo đầu tiên của mục 8.2 cho kết quả ngược hoàn toàn, vì hai shard dùng chung CPU của một máy — môi trường đo đã triệt tiêu đúng hiện tượng cần đo.

Bài 9 hình thức hoá câu hỏi mà mục 7.4 để ngỏ: khi mạng bị chia, và không node nào biết bên kia đã chết hay chỉ mất liên lạc, thì phải chọn gì? Đó là CAP — và phần quan trọng hơn CAP mà ít người nói tới: lựa chọn bạn gặp hằng ngày, khi mạng hoàn toàn bình thường.