Chia một khóa thành 512 lối vẫn có bẫy: mỗi lần tính tổng lại đắt thêm 30 lần

Hình dung một siêu thị chỉ mở đúng một quầy thu ngân. Giờ cao điểm, ai cũng dồn về đó xếp một hàng dài dằng dặc — quầy càng đông, khách chờ càng lâu. Cách chữa hiển nhiên: mở nhiều quầy. Khách rải ra, mỗi quầy một hàng ngắn, tính tiền nhanh hẳn. Nhưng cuối ngày, khi quản lý muốn biết tổng doanh thu cả siêu thị, họ phải đi gom sổ từ từng quầy — càng nhiều quầy, việc gom tổng càng lâu. Đó chính xác là sharding: nó làm việc cục bộ nhanh lên, và lặng lẽ làm việc toàn cục chậm đi.

Xuyên suốt sê-ri, một kẻ thù trở đi trở lại: điểm ghi chung. Một bộ đếm, một map, một cấu trúc dùng chung bảo vệ bởi một khóa — mọi luồng tranh nhau đúng chỗ đó, và throughput sụp, convoy, dòng cache nảy. Sharding (chia phân vùng) là giải pháp tổng quát: đừng có một chỗ chung, hãy có nhiều phân vùng độc lập, để các luồng rải ra và hầu như không đụng nhau. Tôi đo nó, và thấy vừa sức mạnh vừa cái giá mà "cứ chia thật nhiều" bỏ qua.

Chia điểm nóng thành nhiều mảnh

Ý tưởng đơn giản: thay một bộ đếm chung (một khóa) bằng N shard, mỗi shard là một bộ đếm với khóa riêng — mỗi quầy thu ngân một cái sổ riêng. Khi một luồng cần cập nhật, nó băm khóa (key) của thao tác để chọn shard, rồi chỉ khóa shard đó. Vì các luồng băm vào các shard khác nhau, phần lớn thời gian chúng chạm các khóa khác nhau — không tranh chấp. Chỉ khi hai luồng tình cờ băm vào cùng shard mới có tranh chấp, và xác suất đó giảm khi số shard tăng.

Đây là nguyên lý nền của rất nhiều thứ: ConcurrentHashMap của Java (striped lock — chia map thành nhiều segment, mỗi segment một khóa), sharded counter (mỗi shard một biến, cộng lại khi cần tổng), phân vùng cơ sở dữ liệu (chia bảng theo khóa). Tôi đo trong container gcc:13 (10 lõi): các luồng tăng bộ đếm, băm mỗi thao tác vào một shard, mỗi shard nằm trên dòng cache riêng (_Alignas(64) để tránh false sharing).

Đo (a): một khóa sụp, sharding scale

So một bộ đếm chung (1 shard, 1 khóa) với sharded (64 shard), throughput theo số luồng:

NT | 1 khóa chung | 64 shard | sharded/chung
1  |  229 M/s     |  233 M/s |  1×
4  |   46 M/s     |  156 M/s |  3×
8  |   35,7 M/s   |  105 M/s |  3×

Ở 1 luồng, hai bên ngang nhau (không có ai để tranh — siêu thị vắng thì một quầy cũng đủ). Nhưng thêm luồng, một khóa chung sụp: 229 → 35,7 triệu op/giây — càng nhiều luồng càng chậm (đúng scale âm, tất cả tranh một khóa). Sharded thì giữ throughput cao: 233 → 105 triệu (giảm chút vì vẫn có va chạm ngẫu nhiên, nhưng không sụp). Ở 8 luồng, sharding nhanh hơn 3 lần. Sharding biến một điểm nóng thành nhiều điểm nguội.

Đo (b): nhiều shard hơn, ít tranh chấp hơn

Số shard ảnh hưởng thế nào? Đo throughput ở 8 luồng, tăng số shard:

   1 shard :  34 M/s
   8 shard :  54 M/s
  64 shard : 106 M/s
 512 shard : 175 M/s

Càng nhiều shard, throughput càng cao (34 → 175 triệu). Vì với 8 luồng chọn ngẫu nhiên trong S shard, xác suất hai luồng cùng shard (đụng nhau) giảm khi S lớn — kiểu nghịch lý ngày sinh ngược lại. Với 8 shard và 8 luồng, va chạm còn thường; với 512 shard, gần như mỗi luồng một shard riêng, tranh chấp gần biến mất. Nên có vẻ "càng nhiều shard càng tốt". Nhưng đó là chỗ đo hớ — vì có một cái giá không hiện trong bảng này.

Đo (c): thao tác toàn cục đắt dần theo số shard

Cái giá của sharding: khi bạn cần một thao tác toàn cục — tính tổng tất cả bộ đếm, duyệt toàn bộ map — bạn phải chạm mọi shard, đúng như quản lý phải đi gom sổ từng quầy. Đo chi phí tính tổng theo số shard:

     8 shard : ~0 µs
   512 shard :  0,1 µs
  4.096 shard :  2,0 µs
 65.536 shard : 32,8 µs

Chi phí tính tổng tăng tuyến tính theo số shard — O(số shard). Với 65.536 shard, mỗi lần lấy tổng mất 32,8 µs (phải đọc 65 nghìn ô). Đây là đánh đổi cốt lõi: nhiều shard làm ghi cục bộ rẻ (ít tranh chấp) nhưng làm đọc toàn cục đắt (chạm nhiều ô). Nếu bạn hiếm khi cần tổng, chia nhiều shard là tốt; nếu bạn thường xuyên cần tổng/duyệt, quá nhiều shard biến thao tác toàn cục thành nút thắt mới. Số shard tối ưu cân bằng hai chiều này — thường vài lần số luồng là đủ (đủ để tránh va chạm, không quá nhiều để đọc toàn cục còn rẻ), không phải "càng nhiều càng tốt".

(Môi trường đo: container gcc:13 trên host ARM AArch64, 10 lõi, mỗi shard _Alignas(64) tránh false sharing, số lấy sau warmup. Con số tuyệt đối đổi theo máy; điều bền vững là hình dạng: một khóa chung sụp khi đông luồng, sharding scale, và thao tác toàn cục đắt tuyến tính theo số shard.)

Hai niềm tin đối nghịch, cùng sai

Tôi vào đo với hai niềm tin. Thứ nhất: "một cấu trúc chung với một khóa là đủ, đơn giản mà". Sai — một khóa chung là điểm nóng, sụp khi đông luồng (35,7 so với 105 triệu); sharding cần thiết để scale. Thứ hai, sau khi thấy sharding tốt: "vậy càng nhiều shard càng tốt". Cũng sai — throughput ghi có tăng theo số shard, nhưng thao tác toàn cục (tổng, duyệt) đắt lên O(số shard), và băm lệch có thể gây shard nóng (mất cân bằng như cân bằng tải).

Hai niềm tin ngược nhau gặp nhau ở một sự thật: sharding không xóa chi phí, nó dời chi phí từ đường ghi cục bộ (giờ rẻ) sang đường đọc toàn cục (giờ đắt) — và bạn phải biết đường nào nóng hơn để chọn số shard. Đây là cùng một khuôn mẫu với RCU (đọc rẻ, thu hồi trễ) và mọi tối ưu đồng thời: không có bữa trưa miễn phí, chỉ có chuyển chi phí. Nếu workload của bạn 99% là cập nhật cục bộ và 1% là lấy tổng, sharding nhiều là tuyệt; nếu bạn lấy tổng liên tục, sharding nhiều tự bắn vào chân. Đúng tinh thần đo lường: đo cả hai đường (ghi cục bộ và đọc toàn cục) trước khi chọn số shard, đừng chỉ tối ưu throughput ghi rồi ngạc nhiên khi lấy tổng chậm.

Về đến code hằng ngày

Điều đầu tiên: khi một cấu trúc dùng chung là điểm nóng, hãy sharding nó. Bộ đếm nhiều luồng cùng tăng, map nhiều luồng cùng ghi, một hàng đợi công việc bị tranh — chia thành N phân vùng độc lập (mỗi cái khóa/counter riêng), băm khóa để chọn phân vùng. Nhớ đặt mỗi shard trên dòng cache riêng để tránh false sharing.

Điều thứ hai: chọn số shard theo tỉ lệ ghi-cục-bộ / đọc-toàn-cục, không phải max. Nếu thao tác chủ yếu là cập nhật cục bộ và hiếm khi cần toàn cục, nhiều shard tốt (giảm tranh chấp). Nếu thường xuyên cần tổng/duyệt toàn bộ, giữ số shard vừa phải (thao tác toàn cục là O(số shard)). Điểm khởi đầu hợp lý: số shard cỡ vài lần số lõi/luồng. Và coi chừng băm lệch — nếu một khóa "nóng" luôn rơi vào một shard, shard đó thành điểm nóng dù có nhiều shard khác.

Chỗ này cái khuôn "chia để bớt tranh, rồi trả giá lúc gom" lặp lại ở mọi tầng, và nhìn qua các ngôn ngữ/hệ thống thì rõ. Java làm ConcurrentHashMap bằng striped lock và LongAdder bằng mảng ô (mỗi luồng cộng vào ô riêng, sum() mới gộp) — chính là sharded counter, và sum() đắt hơn get() của AtomicLong đúng vì phải duyệt mọi ô. Ở tầng database, đây là sharding kinh điển (Vitess, Citus, Postgres partition): ghi/đọc trong một shard rẻ, nhưng một truy vấn cross-shard (JOIN hay COUNT toàn bảng) phải scatter-gather qua mọi shard — đúng O(số shard). Kafka chia topic thành partition để nhiều consumer chạy song song; Redis Cluster băm key vào 16.384 hash slot. Mẫu số chung: chia làm đường cục bộ nhanh, và mọi thao tác toàn cục trên đám shard đó là một cuộc gom sổ scatter-gather — thứ bạn phải đo, không phải đoán.

Muốn tự thấy thì tìm trong hệ của bạn một cấu trúc dùng chung mà nhiều luồng ghi vào — một bộ đếm thống kê, một cache, một map trạng thái. Hỏi: nó có phải một khóa/một điểm duy nhất không, và có bị tranh dưới tải không? Nếu có (nhiều luồng cùng cập nhật, throughput không scale), thử chia nó thành vài chục phân vùng, mỗi phân vùng khóa riêng, băm khóa để chọn — bạn rất có thể thấy throughput nhảy vọt vì tranh chấp tan ra. Nhưng rồi hỏi ngay câu thứ hai: bao lâu tôi cần một cái nhìn toàn cục (tổng, danh sách tất cả)? Nếu thường xuyên, đừng chia quá nhiều — mỗi lần toàn cục phải gộp mọi phân vùng. Vài phút cân "ghi cục bộ bao nhiêu" với "đọc toàn cục bao nhiêu" cho bạn số shard đúng — và nhắc rằng sharding, như mọi tối ưu đồng thời, không cho không thứ gì: nó đổi sự rẻ ở chỗ này lấy sự đắt ở chỗ khác, và việc của bạn là biết chỗ nào quan trọng hơn.