Sharding

Sharding là gì

Sharding là chia một tập dữ liệu lớn thành nhiều phần, mỗi phần nằm trên một máy database riêng. Mỗi phần gọi là một shard (hoặc partition). Mỗi shard chỉ giữ một phần dữ liệu và chỉ nhận phần tải tương ứng.¹²

Có hai cách chia:

• Vertical (chia dọc): tách theo bảng hoặc theo cột. Bảng users ở máy A, bảng orders ở máy B. Hoặc cột ảnh đại diện, mô tả dài tách ra bảng riêng. Grokking ch.9 gọi đây là vertical sharding, thường dùng để tăng tốc đọc bảng có cột văn bản rất dài hoặc blob, và lưu ý nó hợp với phân chia thủ công, còn horizontal sharding hợp để tự động hóa.³
• Horizontal (chia ngang): cùng một bảng, các dòng khác nhau nằm ở máy khác nhau. User 1 tới 1 triệu ở shard 1, user 1 triệu tới 2 triệu ở shard 2. Grokking mô tả: bảng quá lớn làm ảnh hưởng độ trễ đọc/ghi thì chia theo dòng, mỗi phần gọi là một shard.⁴ Khi người ta nói "sharding" trong phỏng vấn, gần như luôn là chia ngang.

Tách mỗi service một database trong microservices cũng là một dạng chia dọc: Grokking nói chuyển các bảng sang các database khác nhau cũng là vertical sharding.³ Nó giảm tải cho từng database nhưng không giúp được khi riêng một bảng đã quá lớn cho một máy (nhận xét của khoá học).

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

Sharding giải quyết ba giới hạn của một máy (cách nêu của khoá học; Grokking nói chung là chia dữ liệu để xử lý tải đọc, ghi và lượng dữ liệu tăng, còn replication một mình khó đạt cùng lúc khả dụng, scale và hiệu năng):¹⁵

1. Dung lượng: dữ liệu vượt quá vài TB, ổ đĩa và backup trở nên khó quản.
2. Ghi: replica chỉ giúp đọc. Mọi lần ghi vẫn dồn vào một primary. Khi ghi vượt sức một máy, chỉ còn cách chia. Grokking: primary-secondary hợp với tải đọc nhiều, không hợp với tải ghi nhiều, và nhiều follower có thể biến primary thành nút nghẽn.⁵
3. Working set: index và dữ liệu nóng không còn vừa RAM, query bắt đầu đọc đĩa và chậm hẳn. MongoDB TDG cũng nêu mục đích "tăng tài nguyên hệ thống" (ví dụ thêm RAM cho mỗi GB dữ liệu) bằng cách giữ working set nhỏ.⁶

Trong phỏng vấn, sharding thường xuất hiện ở bước deep dive khi bạn tính ra dữ liệu 50 TB hoặc 100.000 write/s. Người phỏng vấn muốn nghe ba thứ: shard key là gì và vì sao, query chính có chạm một shard hay tất cả, và thêm shard thì dữ liệu di chuyển thế nào. Họ cũng muốn thấy bạn không shard quá sớm.

Cách hoạt động

Ứng dụng (hoặc một lớp router) nhận request, lấy shard key từ request, tính ra shard, rồi gửi query tới đúng máy. Grokking nêu ba cách để client biết đi đâu: gọi node bất kỳ rồi node đó chuyển tiếp, qua một routing tier, hoặc client tự biết ánh xạ partition tới node.⁷

Router có thể là thư viện trong app, một proxy riêng, hoặc nằm sẵn trong database. Ví dụ trong sách: mongos của MongoDB là tiến trình router giữ "mục lục" cho biết shard nào chứa dữ liệu nào, chuyển request tới shard phù hợp và gộp kết quả trả về.² Vitess, Citus, Cassandra, DynamoDB là ví dụ ngoài thư viện.⁸ Mỗi shard vẫn có replica riêng để chịu lỗi. Sharding và replication là hai việc độc lập, hệ thống lớn dùng cả hai: replication tạo bản sao y hệt, còn mỗi shard chứa một tập con dữ liệu khác nhau.²⁵

Query có shard key được gửi tới một shard, gọi là targeted query. Query không có shard key phải hỏi mọi shard rồi gộp kết quả, MongoDB gọi đây là scatter-gather.² Thiết kế tốt là thiết kế mà các query thường gặp nhất đều là targeted.

Chọn shard key

Shard key là quyết định khó sửa nhất: MongoDB TDG viết khi đã có hơn vài shard thì gần như không thể đổi shard key.⁶ Một key tốt có ba đặc điểm (tổng hợp của khoá học từ ch.15 của sách):

• Cardinality cao: đủ nhiều giá trị khác nhau để chia nhỏ. Sách ví dụ khóa logLevel chỉ có ba giá trị thì không chia được quá ba chunk.⁹ Shard theo country cũng vậy, và Việt Nam một mình có thể chiếm phần lớn dữ liệu (ví dụ giả định).
• Phân bố đều cả dữ liệu lẫn tải: không có giá trị nào nhận phần lớn lượt ghi. Grokking: partition mất cân bằng tạo hotspot và nút thắt.¹
• Khớp với query chính: query hay gặp nhất mang theo shard key. Sách: khi cụm lớn không nên lập kế hoạch cho query chạm mọi shard, nên gần như mọi query phải có shard key.⁶

Bẫy key tăng dần

MongoDB TDG ch.15 phân tích kỹ trường hợp shard theo key tăng dần như ngày tạo hay ObjectId. Mọi bản ghi mới đều có giá trị lớn hơn bản trước, nên luôn rơi vào chunk cuối cùng (max chunk), chunk chứa khoảng tới $maxKey. Kết quả: toàn bộ lượt ghi được định tuyến tới một shard, chunk đó là chunk duy nhất lớn lên và tách ra, và MongoDB phải liên tục chuyển chunk sang shard khác thay vì chỉ chỉnh các lệch nhỏ.¹⁰ Sách kết luận: nếu không có server hiệu năng cao để "firehose" vào hoặc không dùng tagging thì đừng dùng khóa tăng dần, vì mọi lượt ghi đi vào một shard.¹¹ Hệ quả "thêm shard không tăng throughput ghi" là suy ra của khoá học từ đó.

Cách sửa thường gặp:

• Hash key: hash ObjectId hay user ID trước khi chia. Sách: hashed shard key là lựa chọn tốt nhất để nạp dữ liệu nhanh, làm ghi phân bố ngẫu nhiên, nhưng không bao giờ có range query targeted.¹²
• Key ghép: (user_id, created_at). Sách gọi đây là chiến lược multi-hotspot: dùng compound shard key, phần đầu là giá trị gần ngẫu nhiên với cardinality vừa phải, phần sau là khóa tăng dần, để ghi rải đều giữa các shard còn trong mỗi shard thì tăng dần. Sách lưu ý nên có vài chunk nóng mỗi shard (để còn chỗ mở rộng), nhưng nếu có cả nghìn thì tương đương ghi ngẫu nhiên. Ví dụ (user_id, created_at) là áp dụng của khoá học.¹³

Ví dụ chọn key

Bảng là ví dụ do khoá học tự chọn, áp các nguyên tắc ở trên (cardinality, hotspot, key tăng dần).⁹¹⁰

Range, hash và directory

Hai dòng đầu theo Grokking ch.9: key-range cho mỗi partition một dải key liên tục, dễ range query theo partition key nhưng có thể lệch tải nếu chọn key không tốt; hash-based phân bố khóa đều nhưng không range query được.¹⁴¹⁵ Dòng directory dựa trên kỹ thuật trong Grokking: một bảng ánh xạ partition key sang shard, ứng dụng đọc bảng này để biết gửi query đi đâu.¹⁴ Nhận xét "bảng tra là điểm nghẽn" và cột "Hệ thống dùng" là của khoá học; tên HBase, MongoDB có trong Grokking mục "Dynamic partitioning".¹⁶ Các hệ thống khác (Spanner, Cassandra, DynamoDB, Vitess) đã bỏ khỏi bảng vì thư viện không có đoạn tương ứng cho cách chia của chúng.⁸

Resharding và thêm shard

Tránh hash mod N.

Nếu chọn shard bằng hash(key) % N, đổi N từ 4 lên 5 làm gần như mọi key đổi chỗ. Grokking ch.9 lấy ví dụ một key ở node 0 khi có 5 node chuyển sang node 5 khi có 6 node, và nói với hash mod n thì số partition của mọi node đổi, nhiều dữ liệu phải chuyển nên rebalancing tốn kém.¹⁶ Di chuyển gần toàn bộ dữ liệu khi đang chạy là thảm họa (nhận xét của khoá học).

Ba cách thay thế.

Nội dung bảng theo Grokking ch.9 mục "Rebalance the partitions" (Fixed number of partitions, Dynamic partitioning) và mục "Consistent hashing"; con số 1.024 partition cho 8 node là ví dụ của khoá học.¹⁶

Quy trình chuyển dữ liệu khi đang chạy (quy trình thực hành của khoá học):¹⁷

1. Bật ghi kép: ghi vào cả vị trí cũ và mới.
2. Copy dữ liệu cũ sang nền, giới hạn tốc độ để không ảnh hưởng production.
3. So sánh, đối soát hai bên.
4. Chuyển đọc sang vị trí mới, theo dõi lỗi.
5. Tắt ghi vào vị trí cũ, dọn dẹp.

Query và transaction xuyên shard

Query không có shard key phải scatter-gather. Độ trễ bằng shard chậm nhất, và tải nhân lên theo số shard. Grokking nói với secondary index cục bộ, query phải hỏi mọi partition và độ trễ bị giới hạn bởi partition kém nhất.¹⁸ Cách xử lý:

• Thêm một bảng index phụ shard theo cột khác. Ví dụ shard orders theo user_id, thêm bảng orders_by_merchant shard theo merchant_id. Đổi lại là ghi hai lần và có thể lệch tạm thời.
• Đẩy dữ liệu sang hệ thống khác cho query phân tích hoặc tìm kiếm: Elasticsearch, data warehouse, qua CDC.

Grokking ch.9 gọi hai cách này là secondary index theo document (index cục bộ mỗi partition, đọc phải hỏi tất cả) và secondary index theo term (index toàn cục, đọc hiệu quả hơn nhưng một lần ghi chạm nhiều partition).¹⁸ Ví dụ orders_by_merchant ở trên là minh họa của khoá học.

Join xuyên shard gần như không làm được hiệu quả. Grokking: nên giữ các bảng hay join cùng một shard, và với các bảng liên kết bằng khóa ngoại thì partition theo cùng một partition key để chúng nằm chung shard.³¹⁴ Áp dụng: user và đơn của user dùng chung user_id, hoặc denormalize.

Transaction xuyên shard cần two-phase commit hoặc saga. Building Microservices ch.5: 2PC dễ treo khi transaction manager chết hoặc một cohort không phản hồi, và giữ khóa gây tranh chấp làm scale khó hơn.¹⁹ Microservices Patterns §4.1: 2PC không phải lựa chọn khả thi cho ứng dụng hiện đại; saga là thay thế nhưng thiếu tính isolation của ACID và phức tạp hơn.²⁰ Cách tốt nhất là chọn shard key để transaction quan trọng nằm gọn trong một shard. Xem Quy trình nhiều bước cho saga.

ID toàn cục: auto-increment theo từng shard sẽ trùng. Grokking ch.12: auto-increment của database không dùng được khi nhiều node tự sinh id; dùng UUID, Snowflake ID hoặc một bộ sinh ID.²¹

Khi nào chưa nên shard

Sharding thêm độ phức tạp cho mọi phần của hệ thống: deploy, backup, migration schema, debug, báo cáo (nhận xét của khoá học; Grokking cũng nêu các vấn đề rebalance, định tuyến, index phụ ở trên).¹⁶⁷ Thử các bước sau trước (thứ tự ưu tiên là của khoá học):

1. Thêm index đúng và sửa query chậm. Rẻ nhất, thường hiệu quả nhất. Xem Database index.
2. Nâng cấp máy. Máy 32 vCPU · 256 GB RAM vẫn là một máy, không đổi code.
3. Thêm read replica. Giải quyết tải đọc, phần lớn bài đều đọc nhiều hơn ghi.⁵
4. Thêm cache. Xem Caching.
5. Lưu trữ dữ liệu cũ. Đơn hàng trên 2 năm chuyển sang kho lạnh, bảng nóng nhỏ lại.
6. Partition trong một máy. Postgres declarative partitioning theo tháng giúp index nhỏ và xóa dữ liệu cũ nhanh, chưa cần nhiều máy.²²
7. Chia dọc theo service. Mỗi service một database.

Một Postgres chịu được tới đâu

Con số dưới đây là ước lượng để nói trong phỏng vấn, không phải benchmark (quy tắc ước lượng của khoá học; Grokking ch.5 chỉ cho mốc khoảng 1.000 QPS cho MySQL).²³²⁴

Ví dụ: 10 triệu user hoạt động mỗi ngày, mỗi người tạo 5 bản ghi một ngày. Ghi trung bình = 50 triệu / 86.400 ≈ 580 write/s, đỉnh ×5 ≈ 3.000 write/s. Mỗi bản ghi 1 KB thì một năm ≈ 18 TB. Ghi vẫn trong sức một primary lớn, nhưng dung lượng thì không, nên cần lưu trữ dữ liệu cũ hoặc shard. Phép tính ở trên là số học từ giả định của khoá học (10 triệu user, 5 bản ghi, 1 KB, đỉnh ×5). Grokking ch.9 đưa cách tính tương tự: 10 TB dữ liệu, mỗi shard giữ tối đa 50 GB thì cần 200 shard; kích thước một shard nên xác định bằng thực nghiệm.¹⁵

Sai lầm hay gặp

• Chọn shard key không khớp query chính. Mọi request thành scatter-gather, chậm hơn cả khi chưa shard.²⁶
• Dùng hash % N. Thêm một node là phải di chuyển gần hết dữ liệu.¹⁶
• Quên khách hàng hoặc user cực lớn. Một tenant chiếm 30% dữ liệu sẽ làm một shard quá tải. Cho khách lớn shard riêng qua directory (giải pháp của khoá học).
• Shard trước khi cần. Tốn công vận hành cho một hệ thống một máy là đủ.
• Nghĩ replica và shard là một. Replica nhân bản toàn bộ dữ liệu để đọc và chịu lỗi. Shard chia dữ liệu để tăng dung lượng và ghi. Sách MongoDB nói nhiều người nhầm hai khái niệm này.²
• Không tính transaction xuyên shard. Chuyển tiền giữa hai user ở hai shard cần thiết kế riêng, nói rõ ngay khi chọn key.¹⁹²⁰

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

Bảng dưới tóm cách khoá học áp sharding vào từng bài; lý thuyết nền là các mục Grokking ch.9 và MongoDB TDG ch.15 ở trên.¹⁶

Đọc tiếp: Consistent hashing cho cách chia key khi thêm bớt node, Scale ghi cho các kỹ thuật khác ngoài sharding, Chọn database và PostgreSQL cho giới hạn của từng loại.

Nguồn trích dẫn

1. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Sharding". ↩ ↩² ↩³ ↩⁴

2. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.13 Introduction to Sharding · mục "Introduction to Sharding" và "A One-Minute Test Setup" (tr. 236–240). ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

3. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Vertical sharding". ↩ ↩² ↩³

4. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Horizontal sharding". ↩

5. Grokking Modern System Design · ch.9 Databases · bài "Data Replication", mục "Replication" và "Single leader/primary-secondary replication". ↩ ↩² ↩³ ↩⁴

6. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.15 Choosing a Shard Key · mục "Taking Stock of Your Usage" (tr. 257–258). ↩ ↩² ↩³ ↩⁴ ↩⁵

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

8. Chưa có nguồn trong thư viện: thư viện không có sách về Vitess, Citus, Spanner, Cassandra hay DynamoDB ở mức cơ chế chia dữ liệu; chỉ nêu tên như ví dụ. ↩ ↩²

9. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.15 Choosing a Shard Key · mục "Shard Key Cardinality" (tr. 271). ↩ ↩²

10. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.15 Choosing a Shard Key · mục "Picturing Distributions", "Ascending Shard Keys" (tr. 258–261). ↩ ↩² ↩³

11. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.15 Choosing a Shard Key · mục "The Firehose Strategy" (tr. 267–268). ↩ ↩²

12. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.15 Choosing a Shard Key · mục "Shard Key Strategies", "Hashed Shard Key" (tr. 264–266). ↩

13. MongoDB: The Definitive Guide 2e (file .zip, tải về giải nén) · ch.15 Choosing a Shard Key · mục "Multi-Hotspot" (tr. 268–270). ↩

14. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Key-range based sharding" (gồm sharding nhiều bảng cùng partition key). ↩ ↩² ↩³

15. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Hash-based sharding" (gồm Note "How many shards per database?"). ↩ ↩²

16. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Consistent hashing" và "Rebalance the partitions" (Avoid hash mod n, Fixed number of partitions, Dynamic partitioning, Partition proportionally to nodes). ↩ ↩² ↩³ ↩⁴ ↩⁵ ↩⁶

17. Chưa có nguồn trong thư viện: quy trình ghi kép rồi chuyển đọc là thực hành phổ biến, chưa có đoạn sách tương ứng. ↩

18. Grokking Modern System Design · ch.9 Databases · bài "Data Partitioning", mục "Partitioning and secondary indexes". ↩ ↩²

19. Building Microservices (file .zip, tải về giải nén) · ch.5 Splitting the Monolith · mục "Distributed Transactions" (tr. 92). ↩ ↩²

20. Microservices Patterns (file .zip, tải về giải nén) · ch.4 Managing transactions with sagas · §4.1.2 The trouble with distributed transactions và §4.1.3 Using the Saga pattern to maintain data consistency. ↩ ↩²

21. Grokking Modern System Design · ch.12 Sequencer · bài "Design of a Unique ID Generator", mục "Motivation" và các giải pháp UUID, Twitter Snowflake. ↩

22. Chưa có nguồn trong thư viện: thư viện không có sách về PostgreSQL partitioning. ↩

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

24. Grokking Modern System Design · ch.5 Back-of-the-envelope Calculations · mục "Standard numbers to remember", bảng "Important Rates". ↩