Đến nội dung chính
notes.vinhnq.com

Tìm kiếm

System DesignSenior15 phút đọc

Sharding trong system design: chọn shard key, bốn case study và resharding

Ôn 11 thẻ
Trong bài này

Cụm bài Dữ liệu trong system design: 1. Chọn database · 2. Sharding: shard key và resharding

Partition trong một server đã có ở bài JOIN và partition. Bài này đi tiếp lên nhiều server: khi nào shard, chọn shard key ra sao qua bốn bài toán thật, và làm sao tăng số shard mà không phải dừng hệ thống.

1. Khi nào cần shard

Ý chính: shard khi một node (kể cả đã có index tốt, cache, replica, partition) không chịu nổi tải ghi hoặc dung lượng. Đọc nhiều thì replica và cache thường đủ.

Ngưỡng gợi ý, không phải luật:

Tín hiệu Ngưỡng tham khảo
Số dòng một bảng ≥ 50M: partition; ≥ 200M: cân nhắc shard
Tải ghi ≥ 3.000 TPS kéo dài
Độ trễ p99 của truy vấn phổ biến > 120 ms dù đã tối ưu
Bảo trì VACUUM, tạo index, backup chạy hàng giờ

Sharding đổi lấy nhiều thứ: unique/foreign key toàn cục, transaction và join xuyên shard, index phụ toàn cục, định tuyến, rebalance. Danh sách đầy đủ trong bảng “Partition hay shard” ở bài partition.

2. Range, hash và consistent hashing

Ý chính: chiến lược shard quyết định hai thứ: dữ liệu có chia đều không, và truy vấn theo khoảng có còn rẻ không. Không chiến lược nào được cả hai.

Chiến lược Cách làm Ưu Nhược
Range created_at 2024 → shard 0, 2025 → shard 1… Đơn giản, khớp nghiệp vụ, truy vấn khoảng rẻ Phải tinh chỉnh để đều; điểm nóng
Hash hash(key) % N Chia đều cả dung lượng lẫn tải Truy vấn khoảng phải hỏi mọi shard; vẫn có key nóng bất thường
Directory Bảng tra key → shard Linh hoạt, di chuyển từng key Bảng tra là điểm lỗi và nút thắt, phải cache

Ví dụ điểm nóng của range: news feed partition bảng post theo created_date, 98% truy cập rơi vào partition mới nhất. Shard theo kiểu này thì một máy làm hết việc, các máy còn lại ngồi chơi.

Hash là lựa chọn mặc định, nhưng hash % N có lỗ hổng: thêm một shard (N → N+1) thì khoảng N/(N+1) số key đổi chỗ. Hai cách khắc phục:

  • Logical shard: chia sẵn rất nhiều shard logic (ví dụ 1.024), hash % 1024 không bao giờ đổi; chỉ bản đồ “shard logic → server vật lý” thay đổi khi thêm máy. Redis Cluster làm đúng như vậy với 16.384 slot.
  • Consistent hashing: đặt server và key trên một vòng băm; key thuộc server gần nhất theo chiều kim đồng hồ. Thêm server chỉ lấy key từ một đoạn vòng, khoảng 1/N số key di chuyển. Dùng nhiều virtual node mỗi server để chia đều. Cassandra, DynamoDB dùng ý tưởng này.
flowchart LR
  K[order user_id=42] --> H["hash(42) % 1024 = 517"]
  H --> M{Bản đồ logical → vật lý}
  M -->|0–255| D0[(DB 0)]
  M -->|256–511| D1[(DB 1)]
  M -->|512–767| D2[(DB 2)]
  M -->|768–1023| D3[(DB 3)]

3. Chọn shard key: ba tính chất

Ý chính: liệt kê truy vấn phổ biến nhất trước, rồi chọn key mà truy vấn đó luôn có. Key tốt thoả càng nhiều càng tốt ba tính chất dưới.

  1. Là thực thể gốc (reference entity): dữ liệu liên quan cùng nằm một shard, truy vấn chính không phải đi nhiều shard. Ví dụ đơn hàng và chi tiết đơn đều theo user_id.
  2. Nhỏ: key xuất hiện ở mọi bảng, mọi index, mọi lần định tuyến. bigint tốt hơn chuỗi dài.
  3. Nhiều giá trị khác nhau (high cardinality): để chia đều. country_code chỉ có ~200 giá trị, Việt Nam chiếm hết thì một shard quá tải.

Thêm một điều kiện thực tế: key không đổi theo thời gian. Shard theo city_id của user thì mỗi lần user chuyển nhà phải di chuyển dữ liệu.

4. Bốn case study

Ý chính: cùng một cách nghĩ (truy vấn chính → key → khoá chính) cho ra bốn lời giải khác nhau, kể cả lời giải “đừng shard”.

Hệ thống / bảng Truy vấn chính Chiến lược, key Khoá chính
E-commerce / order Tạo đơn, lịch sử đơn của user, chi tiết đơn HASH(user_id) (order_id, user_id)
Thanh toán / transaction Tạo giao dịch, lịch sử cả bên nợ lẫn bên có, chi tiết Không shard (tới khi buộc phải) transaction_id
Monitoring / metric_log Ghi metric thiết bị theo thời điểm, xem lịch sử một thiết bị, xoá dữ liệu cũ HASH(device_id) rồi RANGE(timestamp) lồng nhau, tốt hơn: time-series DB (device_id, timestamp)
Chat (Discord) / message Gửi tin, xem lịch sử một kênh HASH(channel_id) (channel_id, message_id), sắp theo message_id

Vài điểm cần giải thích:

  • Order: “chi tiết đơn” chỉ có order_id. Cách hay là nhúng shard key vào ID: vài bit của order_id chứa shard logic của user, đọc ID là biết shard, không cần tra.
  • Transaction: một giao dịch thuộc hai tài khoản. Shard theo bên nợ thì lịch sử bên có phải hỏi mọi shard. Lúc cần shard thật, mô hình bút toán kép giúp: mỗi giao dịch sinh hai dòng ledger_entry, mỗi dòng shard theo account_id của chính nó, ghi bằng saga/outbox thay vì một transaction.
  • Metric: partition lồng nhau làm được nhưng khó vận hành; TimescaleDB làm sẵn việc này (xem chọn database).
  • Discord: sắp theo message_id chứ không theo created_at, vì message_id là Snowflake ID: tăng theo thời gian, duy nhất, không trùng khi hai tin cùng mili giây.
Snowflake ID và nhúng shard vào ID

Snowflake ID là số 64 bit: 1 bit dấu, 41 bit mili giây tính từ một mốc (đủ ~69 năm), 10 bit máy (1.024 máy), 12 bit số thứ tự (4.096 ID mỗi ms mỗi máy). Hệ quả:

  • Sắp theo ID ≈ sắp theo thời gian, nên một index (channel_id, message_id) vừa định vị kênh vừa phân trang theo thời gian.
  • Không cần điều phối giữa các máy để cấp ID.
  • Đồng hồ máy chạy lùi (NTP chỉnh) có thể sinh trùng; cài đặt tốt sẽ chờ hoặc từ chối khi phát hiện.

Nhúng shard: thay 10 bit máy bằng 10 bit logical shard của user (Instagram từng làm kiểu này với PostgreSQL schema). Khi đó order_id tự mang theo shard, truy vấn “chi tiết đơn theo id” đi thẳng tới đúng shard.

Code Java tối giản:

long nextId(long logicalShard) {          // 0..1023
  long now = System.currentTimeMillis() - EPOCH;
  synchronized (this) {
    if (now == lastMs) {
      seq = (seq + 1) & 0xFFF;
      if (seq == 0) now = waitNextMs(lastMs);   // hết 4.096 ID trong ms này
    } else {
      seq = 0;
    }
    lastMs = now;
    return (now << 22) | (logicalShard << 12) | seq;
  }
}

5. Truy vấn xuyên shard và định tuyến

Ý chính: mọi truy vấn không mang shard key đều đắt. Thiết kế để truy vấn phổ biến luôn có key, và nhân bản dữ liệu cho truy vấn còn lại.

  • Định tuyến: trong ứng dụng (một ShardRouter chọn DataSource, ví dụ AbstractRoutingDataSource của Spring), hoặc qua proxy (Vitess vtgate, ShardingSphere-Proxy).
  • Scatter-gather: hỏi mọi shard rồi gộp. Chấp nhận được cho tác vụ admin hiếm, không cho API người dùng: độ trễ bằng shard chậm nhất, tải nhân N.
  • Index phụ toàn cục: muốn tìm đơn theo shop_id khi shard theo user_id → duy trì bảng order_by_shop shard theo shop_id, cập nhật bất đồng bộ qua outbox/CDC. Hoặc đẩy sang Elasticsearch.
  • Join: chỉ join trong một shard (cùng key). Bảng nhỏ ít đổi (danh mục, cấu hình) thì nhân bản lên mọi shard.
  • Phân trang toàn cục (top 20 đơn mới nhất của cả hệ): lấy top 20 mỗi shard rồi gộp; đắt, nên thường đọc từ kho phân tích.

6. Resharding không downtime

Ý chính: làm một lần cho vài năm (logical shard nhiều, vật lý ít), để về sau resharding chỉ là di chuyển nguyên khối logical shard sang máy mới, không phải băm lại từng dòng.

Ví dụ khởi đầu: 1.024 logical shard trên 16 database vật lý (64 logical/DB). Khi một DB quá tải, chuyển một nửa logical shard của nó sang DB mới:

  1. Copy nền: snapshot + bắt thay đổi (binlog/WAL, ví dụ Debezium hoặc VReplication của Vitess) để DB mới đuổi kịp.
  2. Kiểm tra: so số dòng và checksum từng logical shard.
  3. Cutover: chặn ghi vào các logical shard đó vài giây, chờ lag về 0, đổi bản đồ định tuyến, mở ghi.
  4. Dọn dẹp: giữ dữ liệu cũ một thời gian để quay lại, rồi xoá.

Mỗi shard vật lý nên có primary + replica như một database bình thường. Đọc từ replica phải tính replication lag: luồng “vừa ghi xong đọc lại” (read-your-writes) nên đọc primary, hoặc ghim user vào primary vài giây sau khi ghi.

Bài tập

Bài 1: Shard bảng chuyến đi của ứng dụng gọi xe

Đề: bảng trip 2 tỷ dòng, 4.000 chuyến mới/s giờ cao điểm. Truy vấn: (a) tài xế xem chuyến hiện tại và lịch sử, (b) khách xem lịch sử, (c) vận hành xem mọi chuyến đang chạy trong một thành phố, (d) tra chuyến theo trip_id từ hỗ trợ khách hàng. Chọn shard key, khoá chính và cách phục vụ cả bốn truy vấn.

Lời giải Bài 1
  • Hai “chủ” tự nhiên là khách và tài xế, giống bài thanh toán. Chọn HASH(rider_id) cho bảng chính vì lượng khách lớn, chia đều, và lịch sử khách là truy vấn nhiều nhất.
  • trip_id là Snowflake có nhúng logical shard của rider → (d) đi thẳng tới shard.
  • (a) Bảng phụ trip_by_driver(driver_id, trip_id, started_at, summary) shard theo driver_id, cập nhật qua outbox → Kafka. Chuyến hiện tại của tài xế nằm ở Redis (driver:{id}:current_trip), không cần DB.
  • (c) “Đang chạy theo thành phố” là dữ liệu nóng, nhỏ (vài chục nghìn chuyến): giữ trong Redis/stream theo city_id, hoặc một service theo dõi trạng thái chuyến; không scatter-gather DB.
  • Khoá chính bảng chính (rider_id, trip_id). 1.024 logical shard trên 8 DB lúc đầu: 4.000/8 = 500 TPS ghi mỗi DB, còn dư cho tăng trưởng 2–3 lần.

Ghi nhớ

  • Nói được các tín hiệu cho thấy cần shard và vì sao đọc nhiều thường chưa cần.
  • Giải thích được vì sao hash % N làm resharding đau, và logical shard / consistent hashing sửa thế nào.
  • Chọn được shard key cho order, transaction, metric, message và giải thích khoá chính.
  • Biết bốn cách xử lý truy vấn không có shard key.
  • Kể được các bước resharding không downtime.

Câu hỏi phỏng vấn

Mid

Partition và shard khác nhau thế nào?

Partition chia một bảng thành nhiều mảnh trên cùng một server; shard chia dữ liệu ra nhiều server.

Partition giúp đọc ít hơn và xoá dữ liệu cũ rẻ nhưng không tăng khả năng ghi vượt một máy. Shard tăng khả năng ghi và dung lượng nhưng mất transaction, join và unique toàn cục.

Range hay hash sharding, bạn chọn cái nào?

Mặc định hash, vì chia đều dung lượng và tải; chọn range khi truy vấn khoảng là chính và tải trải đều trên các khoảng.

Range theo thời gian gần như luôn tạo điểm nóng ở khoảng mới nhất. Hash mất truy vấn khoảng xuyên key, nên kết hợp: hash theo thực thể, trong shard sắp theo thời gian.

Shard key tốt có những tính chất gì?

Là thực thể gốc của truy vấn chính, nhỏ, nhiều giá trị khác nhau, và không đổi theo thời gian.

Ví dụ user_id cho đơn hàng: lịch sử đơn của user nằm một shard, bigint nhỏ, hàng triệu giá trị, user không bao giờ đổi id.

Senior

Bảng transaction của hệ thống thanh toán, bạn shard thế nào?

Hoãn shard lâu nhất có thể vì giao dịch thuộc hai tài khoản; khi buộc phải shard, chuyển sang bút toán kép và shard từng bút toán theo account_id của nó.

Mỗi giao dịch sinh hai ledger_entry (nợ, có), mỗi dòng nằm ở shard của tài khoản mình, nên lịch sử mọi tài khoản là truy vấn một shard. Hai lần ghi nằm ở hai shard nên dùng saga/outbox và đối soát, kèm idempotency key cho mỗi bút toán.

Bạn đang có 8 shard với hash % 8 và cần lên 12. Làm thế nào?

Đổi sang 8 → 12 bằng hash % N sẽ di chuyển khoảng 2/3 số dòng; nên chuyển sang logical shard (ví dụ 1.024) và chỉ di chuyển nguyên khối logical shard.

Bước: thêm cột/hàm tính logical shard, dựng bản đồ logical → vật lý tương ứng với 8 shard hiện tại, rồi chuyển dần một phần logical shard sang 4 máy mới bằng CDC, kiểm tra checksum, cutover từng nhóm với vài giây chặn ghi.

Discord lưu tin nhắn thế nào để đọc lịch sử kênh nhanh?

Partition theo channel_id, trong partition sắp theo message_id là Snowflake ID, nên lịch sử một kênh là một lần đọc tuần tự trên một node.

Kênh rất lớn làm partition quá to, nên thêm bucket thời gian vào partition key (channel_id, bucket), bucket là cửa sổ cố định (ví dụ 10 ngày). Họ từng đi từ Cassandra sang ScyllaDB vì độ trễ GC và compaction.

Tìm đơn theo shop_id khi bảng order shard theo user_id?

Không scatter-gather trên API; duy trì một bản sao dữ liệu theo shop_id (bảng phụ shard theo shop_id hoặc index Elasticsearch) cập nhật bất đồng bộ.

Nguồn sự thật vẫn là bảng shard theo user. Bản sao được cập nhật qua outbox/CDC → Kafka, chấp nhận trễ vài giây, có job đối soát. Shop rất lớn có thể cần shard phụ theo (shop_id, tháng).

Từ vựng tiếng Anh

Term Phát âm Nghĩa Ví dụ câu tiếng Anh dùng trong phỏng vấn
shard key /ʃɑːrd kiː/ khoá chia shard “The shard key must appear in every hot query.”
hot spot /hɑːt spɑːt/ điểm nóng “Range sharding by date creates a hot spot on the newest shard.”
scatter-gather /ˈskæt.ɚ ˈɡæð.ɚ/ hỏi mọi shard rồi gộp “Without the shard key, the query becomes a scatter-gather.”
consistent hashing /kənˈsɪs.tənt ˈhæʃ.ɪŋ/ băm nhất quán “Consistent hashing moves only about one N-th of the keys.”
logical shard /ˈlɑː.dʒɪ.kəl ʃɑːrd/ shard logic “We pre-split into 1,024 logical shards and move them as a whole.”
resharding /riːˈʃɑːr.dɪŋ/ chia lại shard “Resharding is a cutover, not a rehash of every row.”
cardinality /ˌkɑːr.dəˈnæl.ə.ti/ số giá trị khác nhau “Country code has too low cardinality to be a shard key.”
co-locate /ˌkoʊˈloʊ.keɪt/ đặt cùng chỗ “Orders and order items are co-located by user id.”
cutover /ˈkʌt.oʊ.vɚ/ thời điểm chuyển sang hệ mới “The cutover blocks writes for a few seconds.”
double-entry /ˈdʌb.əl ˈen.tri/ bút toán kép “Double-entry rows let us shard the ledger by account.”

Ghi chép dựa trên khoá System Design (Ronin Engineer), viết lại theo cách hiểu của mình.