Partitioning Strategies — Hash & Key-Range Partitioning, Secondary Indexes (DDIA) | Blog

Mở đầu

Ảnh: panumas nikhomkhai — Pexels

Tiếp nối series về cuốn "Designing Data-Intensive Applications" của Martin Kleppmann, hôm nay chúng ta sẽ đi sâu vào một trong những chủ đề quan trọng nhất với backend engineer: partitioning (sharding).

Nếu replication là cách nhân bản dữ liệu lên nhiều node để chịu lỗi, thì partitioning là cách chia nhỏ dữ liệu ra nhiều node để mỗi node chỉ xử lý một phần — giúp hệ thống scale ngang (horizontal scaling). Ý tưởng thì đơn giản, nhưng cách chia dữ liệu thế nào cho hiệu quả mới là bài toán khó.

Bài này sẽ tập trung vào 2 chiến lược partitioning phổ biến cho key-value data: key-range partitioning và hash partitioning, kèm theo câu chuyện về secondary indexes trong hệ thống phân tán.

Key-Range Partitioning — Chia theo khoá có thứ tự

Cách đơn giản nhất: bạn assign mỗi partition một range liên tục của keys, sắp xếp theo thứ tự. Ví dụ, nếu bạn có dữ liệu người dùng với key là tên (A-Z), thì partition 0 chứa A–F, partition 1 chứa G–M, partition 2 chứa N–Z.

Ưu điểm lớn nhất của cách này là range scan rất hiệu quả. Nếu bạn cần query "tất cả users có tên bắt đầu bằng B", bạn chỉ cần query đúng partition chứa B rồi scan tuần tự — giống như bạn đọc một cuốn từ điển, mở đúng trang có chữ B và đọc tiếp.

Chính vì tính chất này, key-range partitioning rất phù hợp cho workload có nhiều range scan. HBase, Bigtable, MongoDB (trước phiên bản 4.0) và CockroachDB dùng chiến lược này.

Tuy nhiên, nhược điểm lớn là nguy cơ hotspot. Nếu key là timestamp và bạn partition theo ngày, thì tất cả writes trong ngày hôm nay đều đổ vào partition của ngày hôm nay — các partition khác rảnh rỗi. Đây là lý do mà Cassandra hay MongoDB dùng hash key thay vì timestamp làm partition key.

Hash Partitioning — Phân phối đều, mất range scan

Ảnh: Jakub Zerdzicki — Pexels

Để giải quyết vấn đề hotspot, nhiều hệ thống dùng hash function lên partition key: bạn hash key và dùng modulo (hoặc consistent hashing) để quyết định partition nào chứa dữ liệu đó.

Ví dụ: hash("user:12345") % 3 = 1 → dữ liệu của user 12345 nằm ở partition 1. Một hash function tốt (MD5, Murmur3) sẽ phân phối keys đều đặn, giúp mỗi partition nhận lượng dữ liệu và traffic tương đương nhau.

Cassandra, DynamoDB, Redis Cluster, và Kafka dùng hash partitioning. DynamoDB dùng hash của partition key để quyết định partition, nhưng cho phép bạn thêm sort key (range) bên trong mỗi partition — thông minh!

Tuy nhiên, hash partitioning mất đi khả năng range scan hiệu quả. Muốn query "tất cả users có tên bắt đầu bằng A"? Bạn phải query tất cả partitions rồi gom kết quả — vì hash function đã trộn đều dữ liệu, A không còn nằm cùng chỗ nữa.

Consistent Hashing — Không phải giải pháp toàn năng

Một hash partitioning đặc biệt là consistent hashing, được dùng bởi Cassandra, Riak, và Dynamo (original). Ý tưởng: hash function map mỗi partition lên một vòng tròn (ring), và mỗi node quản lý một cung trên vòng tròn. Khi thêm/bớt node, chỉ cần di chuyển dữ liệu giữa các node lân cận — giảm lượng dữ liệu cần re-partition so với modulo thông thường.

Nhưng consistent hashing cũng có vấn đề: phân phối có thể không đều, và khi thêm node mới, node đó dễ bị quá tải vì phải nhận dữ liệu từ các node bên cạnh. Cassandra giải quyết bằng cách dùng virtual nodes — mỗi physical node tương ứng với nhiều points trên ring.

Skewed Workloads & Hotspot Mitigation

Cả hai chiến lược đều có vấn đề với skewed workloads — khi một số keys nóng hơn hẳn phần còn lại. Điển hình là celebrity problem trên Twitter: dữ liệu của Justin Bieber nhận nhiều requests hơn tất cả users còn lại cộng lại.

Giải pháp thường dùng:

Thêm random prefix/suffix vào key nóng. VD: thay vì "justinbieber" làm key, dùng "1_justinbieber", "2_justinbieber"... — mỗi key rơi vào partition khác nhau. Khi đọc thì phải query tất cả partitions có chứa các key phụ — đánh đổi giữa read amplification và write throughput.
Application-level sharding: cho phép một số keys có cơ chế hot-key riêng.
Dùng compound key: kết hợp hash partition key + range sort key.

Secondary Indexes trong Partitioned Database

Ảnh: Vjanodic WERSOV — Pexels

Secondary indexes là nơi partitioning trở nên phức tạp. Có 2 cách tiếp cận chính:

Local Secondary Index (Document-Based)

Mỗi partition tự quản lý secondary index riêng cho dữ liệu của nó (còn gọi là "scatter-gather"). Khi bạn query trên secondary index, hệ thống phải gửi request đến tất cả partitions rồi gom kết quả.

Dễ implement, writes nhanh (chỉ cần update index trong partition của mình), nhưng reads chậm vì phải fan-out. MongoDB dùng cách này.

Global Secondary Index (Term-Based)

Secondary index được partition riêng biệt, dùng một partition key khác với primary data. Index terms (giá trị của column được index) được hash hoặc range-partition ra các node khác nhau.

Reads nhanh hơn (chỉ cần gửi đến 1 partition chứa term đang cần), nhưng writes chậm hơn và phức tạp hơn: một write có thể ảnh hưởng đến nhiều partitions của index. DynamoDB và Cassandra dùng cách này.

Key Takeaways

Key-range partitioning — range scan nhanh, nhưng dễ hotspot nếu key có tính tuần tự (VD: timestamp)
Hash partitioning — phân phối đều, mất khả năng range scan, phù hợp cho workload có nhiều writes
Skewed workloads — cả 2 cách đều không tự xử lý được "celebrity keys", cần can thiệp ở application layer
Secondary indexes — local index (scatter-gather) vs global index: đánh đổi giữa write performance vs read performance
Không có chiến lược nào tối ưu cho mọi trường hợp — tuỳ vào workload mà chọn

Glossary

Partition (Shard)	Phân mảnh dữ liệu — mỗi mảnh là một phần nhỏ của dataset được gán cho một node riêng
Key-Range Partitioning	Chia partition dựa trên range liên tục của keys theo thứ tự
Hash Partitioning	Dùng hash function để map key vào partition, giúp phân phối đều
Consistent Hashing	Kỹ thuật hash partitioning trên vòng tròn, giảm lượng di chuyển dữ liệu khi thêm/bớt node
Hotspot	Một partition nhận quá nhiều traffic hoặc dữ liệu so với các partition khác
Secondary Index	Index trên field không phải primary key, cho phép query theo nhiều điều kiện khác
Scatter-Gather	Query gửi đến tất cả partitions rồi gom kết quả — local secondary index pattern

Kết

Partitioning là một trong những kỹ năng quan trọng nhất khi thiết kế hệ thống phân tán. Không có giải pháp one-size-fits-all — tuỳ vào workload của bạn mà chọn:

Nhiều range scan → key-range
Nhiều writes, cần phân phối đều → hash
Có keys siêu nóng → thêm random prefix hoặc compound key

Bài tiếp theo sẽ nói về rebalancing partitions — làm sao để thêm/bớt node mà không downtime? Cùng với request routing — làm sao client biết partition nào chứa dữ liệu cần query?