Partition theo key-range vs hash — và bài toán hot spot

TL;DR: Có hai cách cơ bản chia dữ liệu ra partition. Key-range: mỗi partition giữ một dải khoá liền nhau (a–f, g–m, ...), giữ thứ tự nên range query nhanh — nhưng dễ hot spot khi ghi dồn vào một dải (ví dụ khoá là timestamp, mọi ghi mới rơi vào partition cuối). Hash: băm khoá rồi chia theo giá trị hash, phân bố đều nên chống hot spot — nhưng mất thứ tự, range query phải hỏi mọi partition. Không cách nào thắng tuyệt đối: range đổi phân bố đều lấy range query; hash đổi range query lấy phân bố đều. Và cả hai vẫn có thể skew nếu một khoá đơn lẻ quá nóng (một celebrity, một sản phẩm viral) — lúc đó phải xử riêng khoá đó.

Module trước giữ cùng dữ liệu trên nhiều bản. Giờ ta chia khác dữ liệu ra nhiều node — và quyết định đầu tiên, quan trọng nhất, là chia theo cái gì. Chọn sai làm một node gánh gần hết tải trong khi các node khác ngồi chơi (hot spot), phá tan lợi ích của việc chia.

Bài này so hai cách chia, chỉ ra đánh đổi cốt lõi (phân bố đều ↔ range query), và cảnh báo cái bẫy skew mà cả hai đều dính.

1. Analogy — thư viện xếp sách theo vần vs theo số ngẫu nhiên

Một thư viện lớn chia sách ra nhiều phòng. Cách A: xếp theo vần tên (phòng A–F, G–M, N–Z). Tìm một dải ("mọi sách vần L–N") cực nhanh — đi thẳng vào đúng phòng. Nhưng nếu tự dưng ai cũng mượn sách vần "H" (một tác giả nổi bật), phòng G–M quá tải trong khi các phòng khác vắng.

Cách B: mỗi sách dán một số ngẫu nhiên, chia phòng theo số. Lượng khách vào mỗi phòng đều nhau (không phòng nào bị dồn). Nhưng muốn "mọi sách vần L–N" thì chịu — chúng rải khắp mọi phòng, phải đi hỏi tất cả.

flowchart TB
  subgraph RANGE["Range partition (khoa tang dan)"]
    direction LR
    RW["Ghi moi"] --> RC["Partition cuoi<br/>HOT SPOT"]
  end
  subgraph HASH["Hash partition"]
    direction LR
    HW["Ghi moi"] --> H1["P1"]
    HW --> H2["P2"]
    HW --> H3["P3 (tai deu)"]
  end

2. Key-range partition — giữ thứ tự, nhưng dễ hot spot

Chia không gian khoá thành các dải liền nhau, mỗi partition giữ một dải: partition 1 giữ khoá a–f, partition 2 giữ g–m, ... Ranh giới dải chọn theo phân bố dữ liệu để mỗi partition cỡ nhau.

Điểm mạnh — range query. Vì khoá trong partition đã sắp xếp và các partition liền dải, một truy vấn WHERE key BETWEEN 'g' AND 'j' chỉ chạm đúng partition chứa dải đó, quét tuần tự. Đây là điều hash không làm được.

Điểm yếu — hot spot khi khoá không đều. Cạm bẫy kinh điển: khoá là timestamp (hoặc ID tăng dần). Mọi ghi mới đều có timestamp lớn nhất → rơi vào cùng một partition cuối. Kết quả: partition đó nhận toàn bộ tải ghi, còn các partition khác chỉ giữ dữ liệu cũ, hầu như không được ghi.

Khoa = timestamp, range partition:
  partition A: 00:00-08:00 (du lieu cu, it ghi)
  partition B: 08:00-16:00 (du lieu cu)
  partition C: 16:00-now   <- MOI ghi moi roi vao day -> HOT SPOT
=> chia ra nhieu node nhung chi 1 node nhan tai ghi.

Cách chữa thường là đổi khoá: ghép một tiền tố phân tán vào trước timestamp (ví dụ <sensor_id>-<timestamp>), để ghi rải theo sensor_id — nhưng lúc đó range query "mọi dữ liệu trong giờ qua" lại phải hỏi nhiều partition. Đánh đổi không biến mất, chỉ dời chỗ.

3. Hash partition — phân bố đều, nhưng mất range query

Áp một hàm hash lên khoá để ra một số phân bố đều, rồi chia partition theo dải giá trị hash (hoặc theo consistent hashing — bài sau). Vì hash rải khoá đều bất kể phân bố gốc, tải ghi/đọc phân bố đều — kể cả khi khoá gốc là timestamp tăng dần (hash của các timestamp liền nhau rơi rải rác).

Điểm mạnh — chống hot spot theo dải. Không còn "partition cuối" nhận mọi ghi mới; các khoá liền nhau về giá trị bị hash tán đi khắp nơi.

Điểm yếu — mất thứ tự. Chính vì hash phá thứ tự, hai khoá liền nhau (user1001, user1002) rơi vào hai partition cách xa. Một range query giờ không có "dải" để đi — phải hỏi mọi partition rồi gộp (scatter/gather), chậm và tốn.

Khoa = timestamp, hash partition:
  hash(16:00:01) -> partition A
  hash(16:00:02) -> partition C   <- ghi lien nhau tan ra -> DEU tai
  hash(16:00:03) -> partition B
  Nhung: "moi ban ghi 16:00-17:00" -> phai hoi CA A,B,C roi gop.

4. Skew — vì sao hash cũng không cứu được "celebrity key"?

Hash chia đều theo số lượng khoá, nhưng không đều theo tải trên một khoá. Nếu một khoá đơn lẻ cực nóng — tài khoản của một người nổi tiếng nhận hàng triệu tương tác, một sản phẩm viral — thì mọi thao tác lên khoá đó hash về cùng một partition. Partition đó nóng rực dù tổng thể phân bố "đều". Đây là skew ở mức khoá, và cả range lẫn hash đều dính.

5. Pitfall — chọn cách chia theo thói quen, không theo pattern truy vấn

❌ Bang su kien, truy van chinh: "moi su kien trong 24h qua"
   -> chon HASH partition (vi so hot spot)
   -> range query nay bien thanh scatter/gather MOI partition -> cham

❌ Bang ghi log theo thoi gian -> chon RANGE theo timestamp
   -> moi ghi don vao partition cuoi -> hot spot ghi

6. 📚 Deep Dive

7. Liên hệ các bài khác

• Module 2 — Nhân bản: partition không sống một mình — mỗi partition thường lại được nhân bản; "node giữ partition P" là "nhóm bản của P".
• Bài 02 — Consistent hashing: hash partition đặt ra câu hỏi "thêm/bớt node thì xáo dữ liệu thế nào" — consistent hashing trả lời.
• Bài 04 — Request routing: chia xong thì client tìm đúng partition ở đâu — bài routing.
• Module 1 — Scalability: partitioning chính là hình thức scale-out cho dữ liệu; hot spot là lý do "chia ra" không tự động "nhanh hơn".

8. Tóm tắt

• Partitioning chia dữ liệu lớn ra nhiều node; hai cách cơ bản: key-range và hash.
• Key-range: giữ thứ tự → range query nhanh; nhưng hot spot khi ghi dồn vào một dải (khoá timestamp/tăng dần).
• Hash: phân bố đều → chống hot spot theo dải; nhưng mất thứ tự → range query thành scatter/gather.
• Đánh đổi cốt lõi: phân bố đều (hash) ↔ range query (range) — chọn theo pattern truy vấn chi phối.
• Skew: cả hai vẫn hỏng nếu một khoá đơn lẻ quá nóng; hash không chia nhỏ được một khoá — phải thêm hậu tố tách riêng.
• Anti-pattern: hash mọi thứ (range query chậm) hoặc range theo timestamp (hot spot ghi) — chọn theo truy vấn thật.

9. Tự kiểm tra

Bài tiếp theo: Consistent hashing & rebalancing