Bài 29: Chọn Đúng Data Structure — Problem → Structure Mapping

• Đọc mô tả bài toán và xác định được Redis data structure phù hợp, kèm lý do cụ thể.
• Nắm bộ câu hỏi quyết định (thứ tự, unique, score, count, spatial, reliability) để lọc ra structure đúng.
• Tra cứu nhanh bảng mapping bài toán → structure.
• Phân tích trade-off khi cùng 1 bài toán có nhiều cách giải: accuracy, memory, khả năng list member.
• Nhận biết các anti-pattern chọn sai structure và hậu quả trong production.
• Áp dụng pattern kết hợp nhiều structure cho 1 feature phức tạp.

Module 2 đi từ String đến GEO, mỗi bài giải thích bản chất và use case của từng structure. Nhưng trong thực tế, bạn không bắt đầu bằng "hôm nay tôi muốn dùng Sorted Set" — bạn bắt đầu bằng một bài toán cụ thể: "cần đếm unique visitor", "cần leaderboard theo điểm", "cần tìm tài xế gần nhất".

Quy trình đúng:

1. Mô tả rõ bài toán: access pattern là gì, query nào cần chạy, data có dạng gì.
2. Hỏi bộ câu hỏi quyết định (mục 3) để lọc ra tập structure ứng viên.
3. Đối chiếu trade-off về memory, accuracy, khả năng list member, độ phức tạp vận hành.
4. Chọn structure phù hợp nhất với ràng buộc thực tế của hệ thống.

Một bài toán thường có nhiều cách giải bằng Redis. Việc chọn đúng không phải là tìm cách duy nhất — mà là tìm cách phù hợp nhất với access pattern, memory budget và consistency requirement của hệ thống đang xây dựng.

Trả lời tuần tự các câu hỏi dưới đây. Câu trả lời đầu tiên phân loại được thường đủ để chọn structure:

Câu hỏi bổ sung sau khi có ứng viên:

• Memory budget? — HyperLogLog (12KB cố định) vs Set (linear theo cardinality) vs Bitmap (linear theo max offset).
• Cần liệt kê member không? — HyperLogLog và Bitmap không trả về danh sách member; Set thì có.
• Cần exact count hay approximate? — HyperLogLog approximate (~0.81% error); Bitmap và Set exact.
• TTL cần đặt ở đâu? — String và top-level key có TTL; Hash field TTL chỉ từ Redis 7.4.
• Scale về số element? — Sorted Set với hàng triệu member vẫn O(log N) per operation; Hash với hàng triệu field cần cẩn thận HGETALL.

Bài toán?
├── Cần spatial (lat/lng nearby)? ─────────────────→ GEO
├── Cần count cardinality lớn + chấp nhận error? ──→ HyperLogLog
├── Cần boolean flag theo integer ID dense? ────────→ Bitmap
├── Cần sort / rank theo score? ────────────────────→ Sorted Set
│     ├── Leaderboard / ranking
│     ├── Delayed queue (score = timestamp)
│     ├── Priority queue (score = priority)
│     └── Sliding window rate limit
├── Cần object có nhiều field, update lẻ? ──────────→ Hash
│     ├── User profile / session state
│     └── Nhiều counter liên quan (HINCRBY)
├── Cần unique + set operations? ───────────────────→ Set
│     ├── Tags, permissions, RBAC
│     └── Mutual friends (SINTER), union (SUNION)
├── Cần ordered sequence, duplicate OK? ────────────→ List
│     ├── Timeline / feed (capped)
│     └── Simple FIFO queue (at-most-once)
├── Counter atomic / cache đơn giản / token? ───────→ String
│     ├── INCR / INCRBY
│     ├── SET key value EX ttl
│     └── BITFIELD (compact multi-integer)
└── Reliable messaging, replay, consumer group? ────→ Stream (Module 5)

Bài toán: mỗi bài viết có lượt xem. Cần tăng count mỗi khi có request, đọc count để hiển thị.

Câu hỏi quyết định:

• Cần spatial? Không. Cần count unique lớn? Không (đây là total count, không phải unique). Cần sort? Không. Cần boolean? Không. Cần object field? Không.
• Cần counter atomic đơn lẻ → String INCR.

INCR post:123:views          -- tăng 1, atomic
GET  post:123:views          -- đọc count
INCRBY post:123:views 5      -- tăng batch (nếu gom lại)

Mở rộng: nếu bài viết cần theo dõi nhiều metric (views, likes, shares, comments) và hay đọc tất cả cùng lúc → chuyển sang Hash HINCRBY.

HINCRBY post:123:stats views  1
HINCRBY post:123:stats likes  1
HGETALL post:123:stats
-- → {views: "1024", likes: "87", shares: "12", comments: "34"}

Lý do dùng Hash khi nhiều metric: gom cùng 1 key, 1 lần HGETALL lấy hết thay vì nhiều lần GET riêng lẻ, tiết kiệm round-trip và key namespace.

Bài toán: mỗi khi có đơn hàng, tăng score của sản phẩm. Cần truy vấn top 10 sản phẩm bán chạy nhất bất cứ lúc nào, realtime.

Câu hỏi quyết định:

• Cần sort / rank theo điểm số (số đơn bán) → Sorted Set.

-- Mỗi khi có đơn hàng sản phẩm pid
ZINCRBY sales:daily 1 "product:{pid}"

-- Truy vấn top 10 (score cao nhất trước)
ZREVRANGE sales:daily 0 9 WITHSCORES

-- Truy vấn rank của 1 sản phẩm cụ thể
ZREVRANK sales:daily "product:{pid}"

def record_sale(pid: str) -> None:
    r.zincrby("sales:daily", 1, f"product:{pid}")

def top_products(n: int = 10) -> list[tuple[str, float]]:
    # ZREVRANGE trả về [(member, score), ...]
    return r.zrevrange("sales:daily", 0, n - 1, withscores=True)

def product_rank(pid: str) -> int | None:
    # ZREVRANK: rank 0-based từ cao xuống thấp
    return r.zrevrank("sales:daily", f"product:{pid}")

Tại sao không dùng Hash + sort phía application? Với hàng chục nghìn sản phẩm, HGETALL rồi sort ở application tốn memory transfer và CPU. Sorted Set giữ thứ tự sẵn trong Redis, ZREVRANGE O(log N + K) với K là số phần tử lấy ra.

Bài toán: hệ thống có 50 triệu registered user. Mỗi ngày cần đếm Daily Active Users (DAU). user_id là integer sequential bắt đầu từ 1.

Câu hỏi quyết định:

• Cần count unique — không phải count tổng, mà đếm distinct user.
• Cần chính xác hay approximate? → Cần chính xác (báo cáo tài chính).
• Cần biết user nào active hay chỉ cần count? → Chỉ cần count.
• user_id là integer sequential dense? → Có.
• → Bitmap: exact, dense ID, 50M user = 6.25MB/ngày.

-- User 42 active hôm nay
SETBIT dau:2026-05-28 42 1

-- Đếm DAU
BITCOUNT dau:2026-05-28
-- → (integer) số user active ngày đó

-- Đặt TTL 90 ngày
EXPIRE dau:2026-05-28 7776000

Nếu cần biết user nào active (ví dụ: gửi notification targeting) → Set, nhưng 50M member × ~40 bytes/member ≈ 2GB/ngày — đắt hơn Bitmap ~320 lần.

Nếu user_id là UUID (sparse, không thể làm Bitmap offset) và chỉ cần count xấp xỉ → HyperLogLog: 12KB cố định, ~0.81% error.

Bài toán: hành khách ở tọa độ (lat, lng), cần tìm 10 tài xế gần nhất trong bán kính 5km.

Câu hỏi quyết định:

• Cần tìm kiếm theo vị trí địa lý → GEO.

-- Cập nhật vị trí tài xế realtime
GEOADD drivers:online 106.6297 10.8231 "driver:101"
GEOADD drivers:online 106.6352 10.8180 "driver:205"

-- Tìm 10 tài xế gần nhất trong 5km, sort theo khoảng cách
GEOSEARCH drivers:online
  FROMMEMBER "passenger:request:xyz"
  BYRADIUS 5 km
  ASC
  COUNT 10
  WITHCOORD WITHDIST

GEO dùng Sorted Set nội bộ với score là geohash 52-bit — đây là lý do GEOADD có syntax giống ZADD. Nhưng semantics khác hoàn toàn: không dùng ZADD trực tiếp để thêm tọa độ (score không phải geohash đúng format).

def update_driver_location(driver_id: str, lng: float, lat: float) -> None:
    r.geoadd("drivers:online", [lng, lat, f"driver:{driver_id}"])

def find_nearby_drivers(
    passenger_lng: float,
    passenger_lat: float,
    radius_km: float = 5.0,
    count: int = 10,
) -> list:
    # GEOSEARCH với điểm tham chiếu là tọa độ cụ thể
    return r.geosearch(
        "drivers:online",
        longitude=passenger_lng,
        latitude=passenger_lat,
        radius=radius_km,
        unit="km",
        sort="ASC",
        count=count,
        withcoord=True,
        withdist=True,
    )

Bài toán: sau khi user đăng ký, hệ thống đẩy job "gửi welcome email" vào queue. Worker xử lý. Yêu cầu: không được mất job, nếu worker crash phải xử lý lại.

Câu hỏi quyết định:

• Cần reliable (at-least-once), không được mất → không phải List.
• Cần replay khi worker crash → cần Pending Entries List.
• → Stream + Consumer Group (Module 5), không phải List.

List LPUSH/BRPOP là at-most-once: khi consumer BRPOP lấy message ra, message bị xóa khỏi List ngay lập tức. Nếu consumer crash trước khi xử lý xong → message mất vĩnh viễn.

Stream với consumer group: message chỉ thực sự "done" khi consumer gọi XACK. Cho đến đó, message còn trong Pending Entries List (PEL). Consumer khác có thể XCLAIM / XAUTOCLAIM để nhận lại các message bị stuck.

-- Producer đẩy job
XADD email:queue * user_id 42 template welcome

-- Consumer đọc (chưa ACK = chưa done)
XREADGROUP GROUP email-workers worker-1
  COUNT 10 BLOCK 0
  STREAMS email:queue >

-- Sau khi xử lý thành công
XACK email:queue email-workers <message-id>

Nội dung chi tiết về Stream: Module 5.

"Unique visitor count"

Ba structure đều giải được bài toán này, với trade-off khác nhau:

Câu hỏi quyết định thực tế:

• Cần biết "user nào" active? → Set (dù tốn RAM hơn nhiều).
• user_id là integer sequential dense + cần exact → Bitmap.
• user_id là UUID / IP / bất kỳ + chỉ cần count + error dưới 1% OK → HyperLogLog.

"Queue"

Ba cách implement queue với Redis, yêu cầu khác nhau:

* Sorted Set cũng at-most-once vì ZPOPMIN/ZPOPMAX xóa message khỏi set ngay khi pop.

Một feature thực tế thường dùng nhiều structure đồng thời, mỗi structure đảm nhiệm một vai trò khác nhau. Đây là điều bình thường — không phải dấu hiệu của thiết kế phức tạp thừa.

Feature: Realtime Leaderboard

• Sorted Set leaderboard:season:5: lưu điểm và rank của tất cả player. ZINCRBY khi có điểm mới, ZREVRANGE cho top N.
• Hash player:{id}:profile: lưu tên, avatar URL, level. Khi render top N, lấy score từ ZSet rồi HGETALL profile để hiển thị đầy đủ.
• HyperLogLog leaderboard:viewers:season:5: đếm số unique viewer của bảng xếp hạng (analytics, không cần exact).

Feature: API Rate Limiting + Caching

• String cache:response:{hash}: cache response của request, TTL ngắn (10s–60s).
• Sorted Set ratelimit:{user_id}:{endpoint}: sliding window rate limit (score = timestamp mili giây).
• Hash session:{token}: session state (user_id, role, last_active). TTL theo sliding expiry.

Nguyên tắc

• Mỗi structure đảm nhiệm đúng vai trò nó giỏi nhất. Không cố nhồi tất cả vào 1 structure.
• Key namespace phải tách biệt rõ ràng: leaderboard:, player:, session:.
• Xác định TTL cho từng loại key độc lập — leaderboard season có thể không TTL (xóa thủ công khi kết season), session có TTL theo inactivity, cache response có TTL ngắn.

Trả lời các câu hỏi này trước khi commit vào 1 structure:

• Access pattern: read/write ratio là bao nhiêu? Query chính là gì (HGETALL toàn bộ, HGET field lẻ, ZREVRANGE top N, SISMEMBER...)?
• Thứ tự / unique / sort: dữ liệu cần ordered không? Member cần unique không? Cần rank theo score không?
• Memory budget: estimate số element tối đa và size per element. Dùng MEMORY USAGE key trên dữ liệu thực sau khi chọn.
• Cardinality và scale: số phần tử hiện tại và dự báo 1 năm tới. Structure có encoding threshold không (listpack → skiplist khi >128 member)?
• Accuracy requirement: exact count hay approximate (<1% error) đủ?
• Cần enumerate member không: cần liệt kê/export member hay chỉ cần count và membership check?
• TTL strategy: key-level TTL đủ không, hay cần field-level TTL (Hash field TTL từ Redis 7.4)?
• Reliability: nếu là queue — at-most-once OK hay cần at-least-once với replay?

Tổng kết

• Bắt đầu từ bài toán và access pattern, không từ command. Câu hỏi đầu tiên: "cần spatial / count unique / sort / membership / object / ordered / counter"?
• Cùng 1 bài toán có nhiều cách giải. Chọn dựa trên: memory budget, cần exact hay approximate, cần list member, cần reliability.
• "Unique visitor" → Set (exact + member), Bitmap (exact + dense int ID, compact), HyperLogLog (approximate + bất kỳ ID type, 12KB).
• "Queue" → List (simple, at-most-once), Sorted Set (delayed/priority), Stream (reliable, at-least-once, replay).
• 1 feature thường dùng nhiều structure: Sorted Set cho ranking, Hash cho profile, HyperLogLog cho analytics.
• Anti-pattern nguy hiểm nhất: List cho reliable queue, Set cho cardinality hàng chục triệu, KEYS * để query, Bitmap với sparse ID.

Quiz 5 câu

1. Bài toán: "kiểm tra xem user X có permission P không, trong hệ thống RBAC". Structure nào phù hợp và tại sao? Time complexity của operation chính?
2. Hệ thống có 100 triệu user (UUID), cần đếm DAU hàng ngày, báo cáo nội bộ chấp nhận sai số dưới 1%. Chọn structure nào? Nếu yêu cầu thay đổi thành "cần biết user nào active để gửi notification", chọn lại như thế nào?
3. Giải thích tại sao dùng List cho "email queue không được mất" là anti-pattern. Structure đúng là gì và cơ chế nào đảm bảo at-least-once?
4. Dữ liệu: tọa độ GPS của 200.000 xe delivery cập nhật mỗi 5 giây. Query: tìm 5 xe gần nhất trong 3km từ điểm giao hàng. Structure nào và lệnh nào?
5. Feature "top 100 sản phẩm bán chạy trong 7 ngày" cần reset hàng tuần. Thiết kế key schema và giải thích cách reset (xóa key cũ, tạo key mới) mà không gián đoạn query đang chạy.

Đáp án gợi ý

1. Set: SISMEMBER user:{uid}:permissions "P", O(1). Set phù hợp vì permissions là tập unique, cần membership check nhanh, có thể dùng SINTER để kiểm tra nhiều permission cùng lúc.
2. 100M UUID → HyperLogLog: 12KB cố định, PFADD dau:2026-05-28 {uuid}, PFCOUNT dau:2026-05-28. Nếu cần biết user nào → Set: 100M UUID × ~40 bytes ≈ 4GB/ngày, cần đánh giá memory budget có cho phép không.
3. List BRPOP xóa message ngay khi pop, nếu consumer crash trước khi xử lý xong thì message mất. Stream + Consumer Group: message vào Pending Entries List (PEL) sau XREADGROUP, chỉ ra khỏi PEL sau XACK. Consumer khác có thể XCLAIM message stuck trong PEL → at-least-once delivery.
4. GEO: GEOADD vehicles:live {lng} {lat} "vehicle:{id}" mỗi lần cập nhật. Query: GEOSEARCH vehicles:live FROMLONLAT {lng} {lat} BYRADIUS 3 km ASC COUNT 5 WITHCOORD WITHDIST.
5. Key pattern theo tuần: sales:top:2026-W22. Trong suốt tuần: ZINCRBY vào key này. Khi sang tuần mới: tạo key sales:top:2026-W23 và tiếp tục write. Key cũ set TTL 7 ngày để tự expire. Rename atomic (RENAME) không cần thiết ở đây vì đang append vào key mới, không replace key cũ đang dùng.

Bài tiếp theo

Bài 30 đi vào checklist và anti-patterns Data Structure chi tiết hơn — trong đó có incident story thực tế về HGETALL trên một Hash 5 triệu field gây block event loop và spike p99.

Tham khảo

• Redis Docs — Data Types Overview
• Redis Docs — Sorted Sets
• Redis Docs — HyperLogLog
• Redis Docs — Bitmaps
• Redis Docs — Geospatial
• Redis Docs — Streams
• Redis Docs — Patterns & Use Cases