From Chaos to Control: Addressing Shard Distribution Challenges in M3DB with Subclusters

Uber · 2026 · 4. Điều chỉnh · Độ khó: Nâng cao — bài gốc

Bối cảnh

M3DB là DB time-series phân tán của Uber: dữ liệu chia shard, mỗi shard có RF bản sao; một thuật toán placement quyết định node nào giữ shard nào.
Thuật toán cũ chỉ có một ràng buộc cứng: hai bản sao của một shard không được nằm cùng một isolation group (rack/AZ). Ngoài ra shard được rải tự do, nên mọi node đều có thể chia sẻ shard với gần như mọi node khác.
Hậu quả ở cụm lớn:
- blast radius rộng: một node hỏng hoặc bảo trì thì việc bootstrap (chép lại dữ liệu) chạm tới tới (n−1)/n số node trong cụm. Ngay cả khi số group bằng RF (3 AZ với RF=3), mỗi node vẫn chia sẻ dữ liệu với tới ~66,67% cụm;
- không làm song song được: các thao tác bảo trì có thể ảnh hưởng lẫn nhau, nên phải làm tuần tự.

Thay đổi chính

Subcluster: chia node thành các nhóm kích thước cố định; mỗi nhóm sở hữu một lát shard riêng, không chồng lấn. Ví dụ 12 node, RF=3, 6 node/subcluster → 2 subcluster, mỗi cái giữ một nửa số shard. Ở trạng thái ổn định, không có shard nào được chia sẻ giữa hai subcluster.
Điều kiện: phần cứng đồng nhất; scale theo bội số của kích thước subcluster; số node mỗi subcluster là bội số của RF; không hỗ trợ đổi RF.
Vấn đề skew khi thêm subcluster: chọn ngẫu nhiên shard để nhường cho subcluster mới có thể làm lệch nội bộ (một node 50 shard, node khác 150), tức là tạo hot spot. Rebalance sau đó thì mỗi shard phải dời hai lần.
Thuật toán tham lam: với mỗi shard ứng viên, mô phỏng "nếu bỏ shard này thì skew còn bao nhiêu", rồi chọn shard để lại cụm cân bằng nhất trước. Độ phức tạp O(S log S). Tìm tối ưu tuyệt đối là bài toán mũ, không khả thi.
Chia sẻ shard giữa subcluster chỉ xảy ra tạm thời trong lúc scale, và mỗi lúc chỉ cho phép một subcluster dở dang.
Giữ interface cũ ở mức instance (AddInstances/RemoveInstances) thay vì thêm thao tác cấp subcluster. Lý do: tương thích với công cụ hiện có (chỉ đổi một cờ cấu hình), và tránh "bootstrapping storm" khi thêm cả subcluster một lúc.

Kết quả

Theo Uber:

lỗi được khoanh trong một subcluster;
bảo trì song song được giữa các subcluster;
số cặp node có thể chia sẻ shard giảm từ O(cụm) xuống O(subcluster).

Thuật toán cũ vẫn hợp với cụm nhỏ. Bài không có số đo trước/sau.

Vì sao

Theo Uber: thuật toán rải tự do ổn ở cụm vừa và nhỏ, nhưng khi cụm lớn thì chi phí vận hành và độ tin cậy xấu đi.

Bài học cho SWE

Rải đều tối đa không phải lúc nào cũng tốt. Rải tự do làm đồ thị phụ thuộc dày đặc, nên một lỗi chạm tới cả cụm. Ràng buộc thêm cấu trúc (cell/subcluster) đổi một chút linh hoạt lấy blast radius nhỏ.
Cùng ý tưởng với pod của Shopify (Shopify 2018), nhưng ở tầng storage thay vì tầng tenant.
Tránh di chuyển dữ liệu hai lần; chọn thứ tự di chuyển ngay từ đầu.
Giữ interface cũ để nâng cấp chỉ là đổi cấu hình, và để thay đổi được rải dần theo thời gian.