Bài 96: Top-K & Count-Min Sketch — Frequency Estimation

• Giải thích được bài toán frequency estimation trên stream tốc độ cao và lý do Sorted Set exact-count không scale với 1M unique items.
• Mô tả trực giác thuật toán HeavyKeeper (Top-K) và cấu trúc 2D array của Count-Min Sketch.
• Dùng đúng commands TOPK.RESERVE, TOPK.ADD, TOPK.LIST, TOPK.QUERY và CMS.INITBYDIM, CMS.INITBYPROB, CMS.INCRBY, CMS.QUERY.
• Viết code Python cho ba use case: trending hashtag theo giờ, heavy hitter detection, streaming term frequency.
• Hiểu đặc tính over-estimate của CMS và tình huống nào over-estimate là chấp nhận được.
• Chọn đúng dimension (width × depth) dựa trên yêu cầu memory và error bound.
• Biết pattern combine Top-K + CMS và khi nào Sorted Set đơn giản hơn.

Hai bài toán xuất hiện thường xuyên trong hệ thống có stream dữ liệu cao:

• "Top 10 hashtag xuất hiện nhiều nhất trong 1 giờ qua" — trending feed.
• "URL nào bị request nhiều nhất? IP nào đang gửi request bất thường?" — heavy hitter detection, anti-DDoS.

Cả hai đều cần xử lý 1 triệu event/giây hoặc hơn trong khi vẫn trả lời real-time. Nếu dùng Sorted Set để đếm exact count:

• 1 triệu unique hashtag → Sorted Set ~100MB chỉ cho 1 metric.
• ZINCRBY throughput đạt ~100k ops/giây trên single thread Redis — đủ cho nhiều trường hợp nhưng memory sẽ là bottleneck khi unique items tăng.
• Nếu cần 10 metric song song hoặc window per-minute: 1GB+ RAM chỉ cho counting.

Top-K và Count-Min Sketch giải quyết bài toán này bằng cách chấp nhận một sai số nhỏ có thể định lượng, đổi lấy memory cố định và throughput cao hơn đáng kể:

• Top-K (K=100): memory O(K) — vài KB, không phụ thuộc số unique items.
• Count-Min Sketch (2000×5): ~80KB, không phụ thuộc N unique items — chỉ phụ thuộc cấu hình width và depth.

RedisBloom dùng thuật toán HeavyKeeper (Wang et al., 2018) thay vì SpaceSaving truyền thống. HeavyKeeper duy trì K candidate slot và sử dụng bảng hash nhiều chiều để giảm false promotion.

Cơ chế hoạt động:

1. Mỗi item đến được hash → ánh xạ vào các bucket trong bảng.
2. Nếu bucket đang chứa cùng item: counter tăng lên.
3. Nếu bucket đang chứa item khác: counter giảm theo decay (probabilistic). Xác suất giảm tỉ lệ với decay^counter — item có counter cao khó bị kicked hơn.
4. Khi counter về 0: bucket giải phóng, item mới chiếm slot.
5. K candidates có counter cao nhất luôn được maintain trong heap.

Kết quả: item thực sự frequent (heavy hitters) giữ được slot; item ít gặp bị kick ra khỏi bảng sau một thời gian. Memory: O(K × depth × width_per_bucket) — thường vài KB đến vài chục KB cho K=100.

Tham số decay (0 < decay ≤ 1) kiểm soát tốc độ "quên":

• decay=0.9: items cũ mất dần trọng lượng, hệ thống phản ứng nhanh hơn với xu hướng mới.
• decay=1.0: all-time count — không decay, item một khi có counter cao thì rất khó bị loại.

Count-Min Sketch (Cormode & Muthukrishnan, 2005) là một mảng 2 chiều depth × width gồm các counter nguyên. Cả ghi lẫn đọc đều dùng D hàm hash độc lập:

Ghi (increment):

1. Với mỗi hàng i trong 0..depth-1: tính j = hash_i(item) % width.
2. Tăng table[i][j] lên 1.

Đọc (query):

1. Với mỗi hàng i: tính j = hash_i(item) % width.
2. Lấy MIN của tất cả table[i][j] — đó là estimate count.

Tại sao dùng MIN? Vì các counter có thể bị "chia sẻ" (collision) với item khác, nên counter nào cũng có thể bị over-count. MIN trong D hàng độc lập cho xác suất cao nhất là estimate gần nhất với giá trị thực. CMS chỉ over-estimate (không bao giờ under-estimate).

Error bound lý thuyết: với probability ≥ 1 − δ, estimate ≤ true_count + ε × N, trong đó N là tổng số event. Tham số:

• width kiểm soát ε: width = ceil(e / ε) (e ≈ 2.718).
• depth kiểm soát δ: depth = ceil(ln(1/δ)).

Ví dụ: ε=0.001 (lỗi 0.1%), δ=0.01 (99% confident) → width≈2719, depth≈5 → ~54KB memory.

# Tạo Top-K structure
# TOPK.RESERVE key topk width depth decay
# topk: số lượng candidates (K)
# width, depth: dimension của bảng HeavyKeeper bên trong
# decay: hệ số decay (0 < decay <= 1)
TOPK.RESERVE trending:tags 50 8 7 0.9

# Thêm items (có thể nhiều cùng lúc)
# Trả về list item bị kick ra (nếu có) — dùng để biết rank shift
TOPK.ADD trending:tags "#worldcup" "#bitcoin" "#worldcup" "#ai"

# Kiểm tra item có trong top-K không (1 = có, 0 = không)
TOPK.QUERY trending:tags "#worldcup" "#unknown_tag"
# Output: 1) (integer) 1
#         2) (integer) 0

# Lấy danh sách tất cả top-K items hiện tại
TOPK.LIST trending:tags

# Lấy thông tin cấu hình
TOPK.INFO trending:tags
# Output: k=50, width=8, depth=7, decay=0.9

TOPK.ADD là command chính trong hot path. Nó trả về tên item bị kick ra khỏi top-K nếu có item mới vào — thông tin này hữu ích để log rank change events.

Lưu ý về TOPK.COUNT: command này (đếm approximate count cho item trong Top-K) đã bị deprecated trong các phiên bản RedisBloom gần đây. Nên dùng Count-Min Sketch song song nếu cần frequency value.

# Khởi tạo theo dimension trực tiếp
# width=2000, depth=5 → ~80KB, error ~0.1% của tổng event
CMS.INITBYDIM stream:terms:freq 2000 5

# Hoặc khởi tạo theo error bound (dễ reasoning hơn)
# error: max delta / total_events (0.001 = 0.1%)
# probability: xác suất giữ error bound (0.99 = 99%)
CMS.INITBYPROB stream:terms:freq 0.001 0.99

# Tăng counter cho items (batch)
# Trả về estimated count sau khi tăng
CMS.INCRBY stream:terms:freq redis 1 python 1 golang 3

# Query estimated count
CMS.QUERY stream:terms:freq redis python golang
# Output: 1) (integer) 142
#         2) (integer) 98
#         3) (integer) 47

# Thông tin cấu hình
CMS.INFO stream:terms:freq
# width, depth, count (total increments)

CMS.INITBYPROB thường dễ dùng hơn CMS.INITBYDIM khi bạn có requirement rõ ràng về error rate: truyền vào mức sai số chấp nhận được và độ tin cậy, Redis tự tính width/depth.

CMS.MERGE (nếu cần):

# Merge nhiều CMS vào một (dùng cho parallel worker)
CMS.MERGE destination numkeys src1 src2 [WEIGHTS w1 w2]

import redis
import time

r = redis.Redis(host="localhost", port=6379, decode_responses=True)


def current_hour_key() -> str:
    """Key per giờ: trending:tag:hour:{epoch_hour}"""
    epoch_hour = int(time.time()) // 3600
    return f"trending:tag:hour:{epoch_hour}"


def init_trending_period(key: str, k: int = 100) -> None:
    """Khởi tạo Top-K nếu chưa tồn tại.
    K=100, width=16, depth=8, decay=0.95
    """
    if not r.exists(key):
        r.topk().reserve(key, k, 16, 8, 0.95)
        # Hết giờ, key không cần nữa — TTL 2 giờ để an toàn
        r.expire(key, 7200)


def track_tweet(tags: list[str]) -> None:
    """Ghi nhận hashtags từ 1 tweet vào Top-K giờ hiện tại."""
    if not tags:
        return
    key = current_hour_key()
    init_trending_period(key)
    # TOPK.ADD nhận varargs; trả về items bị kick (có thể bỏ qua)
    r.topk().add(key, *tags)


def get_trending(k: int = 10) -> list[str]:
    """Trả về top K hashtags giờ hiện tại."""
    key = current_hour_key()
    if not r.exists(key):
        return []
    items = r.topk().list(key)
    # items là list, có thể có None nếu slot chưa đủ
    return [item for item in items if item][:k]


# --- Demo ---
track_tweet(["#worldcup", "#football", "#worldcup"])
track_tweet(["#bitcoin", "#crypto"])
track_tweet(["#worldcup", "#ai", "#ml"])

trending = get_trending(5)
print(trending)  # ['#worldcup', '#football', '#bitcoin', '#ai', '#crypto']

Điểm cần lưu ý:

• init_trending_period dùng r.exists() trước để tránh gọi TOPK.RESERVE nhiều lần — command này lỗi nếu key đã tồn tại.
• TTL 2 giờ đặt trên key giờ để Redis tự dọn sau khi window qua — không cần cron job.
• Trong production, track_tweet thường được gọi từ Kafka consumer hoặc stream processor, không từ web request trực tiếp.

Pattern này kết hợp Top-K để tìm IP xuất hiện nhiều nhất và CMS để ước tính count chính xác hơn cho candidate đó:

import redis

r = redis.Redis(host="localhost", port=6379, decode_responses=True)

TOPK_KEY = "heavy:ip:topk"
CMS_KEY = "ip:freq:cms"
REQUEST_THRESHOLD = 10_000  # 10k requests trong window


def setup_structures() -> None:
    """Gọi một lần khi khởi động (hoặc đầu mỗi window)."""
    if not r.exists(TOPK_KEY):
        # K=50 IPs, width=16, depth=8, decay=0.9
        r.topk().reserve(TOPK_KEY, 50, 16, 8, 0.9)
        r.expire(TOPK_KEY, 3600)  # reset mỗi giờ

    if not r.exists(CMS_KEY):
        # error 0.01% của tổng request, confidence 99%
        r.cms().initbyprob(CMS_KEY, 0.0001, 0.99)
        r.expire(CMS_KEY, 3600)


def track_request(client_ip: str) -> None:
    """Ghi nhận mỗi request — gọi trong middleware."""
    r.topk().add(TOPK_KEY, client_ip)
    r.cms().incrby(CMS_KEY, {client_ip: 1})


def check_heavy_hitter(client_ip: str) -> bool:
    """Trả về True nếu IP này là heavy hitter đáng chặn."""
    # Bước 1: TOPK.QUERY — nhanh O(1), check IP có trong top-50 không
    in_topk = r.topk().query(TOPK_KEY, client_ip)
    if not in_topk or not in_topk[0]:
        return False  # IP không nằm top → không phải heavy hitter

    # Bước 2: CMS.QUERY — lấy estimate count
    counts = r.cms().query(CMS_KEY, client_ip)
    estimated_count = counts[0] if counts else 0

    return estimated_count > REQUEST_THRESHOLD


def rate_limit_if_needed(client_ip: str) -> None:
    """Áp dụng rate limiting nếu heavy hitter."""
    track_request(client_ip)
    if check_heavy_hitter(client_ip):
        # Log + block
        print(f"[ALERT] Heavy hitter detected: {client_ip}")
        # rate_limit_aggressively(client_ip)  # implement theo hệ thống


def get_top_ips(n: int = 10) -> list[dict]:
    """Dashboard: top N IPs kèm count."""
    top_ips = r.topk().list(TOPK_KEY)
    top_ips = [ip for ip in top_ips if ip][:n]
    if not top_ips:
        return []
    counts = r.cms().query(CMS_KEY, *top_ips)
    return [{"ip": ip, "count": c} for ip, c in zip(top_ips, counts)]

Lý do kết hợp hai structure:

• Chỉ TOPK.QUERY một mình: biết IP có trong top không, nhưng không biết count để so sánh threshold.
• Chỉ CMS.QUERY một mình: phải query mọi IP — không có cách biết IP nào đáng query mà không có Top-K filter trước.
• Kết hợp: Top-K làm first filter (nhanh), CMS làm second check (có count).

Use case: NLP pipeline hoặc log analyzer cần biết term nào xuất hiện nhiều nhất trong stream log/text. CMS đếm tất cả terms; Top-K maintain top candidates; kết hợp để hiển thị cả rank lẫn count:

import redis
from collections import Counter

r = redis.Redis(host="localhost", port=6379, decode_responses=True)

TOPK_KEY = "logs:terms:topk"
CMS_KEY = "logs:terms:cms"


def setup_term_tracking(k: int = 200) -> None:
    if not r.exists(TOPK_KEY):
        r.topk().reserve(TOPK_KEY, k, 16, 8, 0.95)
    if not r.exists(CMS_KEY):
        # 5000 width × 7 depth = ~280KB, error ~0.054% của tổng terms
        r.cms().initbydim(CMS_KEY, 5000, 7)


def ingest_log_line(tokens: list[str]) -> None:
    """Xử lý một dòng log đã tokenize."""
    if not tokens:
        return
    # Batch: đếm trong local trước để giảm Redis calls
    freq = Counter(tokens)
    r.topk().add(TOPK_KEY, *tokens)                      # Top-K: từng token
    r.cms().incrby(CMS_KEY, freq)                         # CMS: batch với count


def get_top_terms(n: int = 20) -> list[dict]:
    """Top N terms kèm estimated frequency."""
    top = r.topk().list(TOPK_KEY)
    top = [t for t in top if t][:n]
    if not top:
        return []
    counts = r.cms().query(CMS_KEY, *top)
    result = [{"term": t, "count": c} for t, c in zip(top, counts)]
    # Sắp xếp theo count descending (CMS count chính xác hơn rank của Top-K)
    result.sort(key=lambda x: x["count"], reverse=True)
    return result


# --- Demo ---
setup_term_tracking()
ingest_log_line(["error", "connection", "timeout", "redis", "error", "error"])
ingest_log_line(["redis", "connection", "ok", "redis"])
print(get_top_terms(5))
# [{'term': 'redis', 'count': 3}, {'term': 'error', 'count': 3}, ...]

Trong ingest_log_line, Counter gom count local trước rồi một lần CMS.INCRBY với nhiều pairs — giảm đáng kể số Redis roundtrip so với gọi riêng từng term.

Hầu hết use case frequency estimation không cần all-time count — cần count trong window cụ thể (1 giờ, 1 ngày). Có hai cách tiếp cận:

1. TTL-based rotation (đơn giản):

import time
import redis

r = redis.Redis(host="localhost", port=6379, decode_responses=True)


def hour_key(prefix: str) -> str:
    epoch_hour = int(time.time()) // 3600
    return f"{prefix}:h{epoch_hour}"


def day_key(prefix: str) -> str:
    epoch_day = int(time.time()) // 86400
    return f"{prefix}:d{epoch_day}"


def track_event(event: str) -> None:
    hkey = hour_key("topk:events")
    dkey = day_key("topk:events")

    for key, ttl in [(hkey, 7200), (dkey, 172800)]:
        if not r.exists(key):
            r.topk().reserve(key, 100, 16, 8, 0.9)
            r.expire(key, ttl)
        r.topk().add(key, event)

2. Explicit rotation với archive: cuối mỗi window, gọi TOPK.LIST để lưu snapshot vào persistent store (PostgreSQL, S3) trước khi xóa key. Hữu ích khi cần lịch sử so sánh trending theo ngày.

def rotate_and_archive(key: str, archive_fn) -> None:
    """Lưu snapshot top-K rồi xóa key."""
    top_items = r.topk().list(key)
    top_items = [item for item in top_items if item]
    if top_items:
        archive_fn(key, top_items)   # ghi vào DB/S3
    r.delete(key)

Anti-pattern cần tránh: dùng all-time key mà không reset — Top-K sẽ bị "dominated" bởi items từ tháng trước, trending không còn phản ánh hiện tại dù có decay.

CMS chỉ over-estimate (không bao giờ trả về count thấp hơn thực tế) vì counter trong bảng chỉ được tăng, không giảm. Điều này có hệ quả thực tế quan trọng:

• "Item có count ≥ threshold?": nếu CMS trả về count ≥ threshold, có thể đúng hoặc over; nếu CMS trả về count < threshold, chắc chắn đúng item chưa đủ count. Nói cách khác: false positive có thể xảy ra, false negative không xảy ra.
• "Item có count = 0?": nếu CMS trả về 0, item chắc chắn chưa xuất hiện lần nào. Đây là guarantee mạnh.
• Anti-spam / rate limiting: over-estimate là chấp nhận được — thà block nhầm hơn bỏ sót kẻ spam.
• Billing / accounting: không phù hợp — cần exact count, sai số tài chính không chấp nhận được.

Over-estimate tệ nhất xảy ra khi dimension nhỏ và nhiều item có hash collision. Chọn width đủ lớn (theo công thức hoặc CMS.INITBYPROB) để kiểm soát.

Bảng ước tính memory và error bound cho Count-Min Sketch (mỗi counter là 4 byte, depth cố định 5):

Ví dụ thực tế: 100k unique terms, tổng 100 triệu event trong 1 giờ, dùng width=2000/depth=5 → error tối đa ~140,000 per item. Với item có count 50 triệu (xuất hiện nhiều nhất) thì 140k là sai số 0.28% — chấp nhận được cho dashboard trending.

Đối với Top-K: memory phụ thuộc K và cấu hình width/depth bên trong HeavyKeeper, không phải số unique items:

Ngay cả K=1000 vẫn chỉ vài chục KB — không đáng kể so với Sorted Set exact-count với 1M items (hàng trăm MB).

Top-K và CMS có vai trò bổ trợ nhau:

• Top-K: biết ai đang trending (candidate list), nhưng count bên trong Top-K không đủ chính xác để hiển thị.
• CMS: biết bao nhiêu lần bất kỳ item nào xuất hiện, nhưng không biết item nào đang top.

def get_top_with_counts(topk_key: str, cms_key: str, n: int = 10) -> list[dict]:
    """Lấy top-N items kèm estimated count từ CMS."""
    candidates = r.topk().list(topk_key)
    candidates = [c for c in candidates if c][:n]
    if not candidates:
        return []
    counts = r.cms().query(cms_key, *candidates)
    result = [{"item": item, "count": cnt}
              for item, cnt in zip(candidates, counts)]
    # Sort theo CMS count (chính xác hơn rank HeavyKeeper)
    result.sort(key=lambda x: x["count"], reverse=True)
    return result

Pattern này dùng trong dashboard display: TOPK.LIST cho candidate set (O(K)), CMS.QUERY batch cho toàn bộ candidate (1 roundtrip). Total: 2 Redis calls cho display top-N.

Trong hot path (per-event), chỉ cần:

pipeline = r.pipeline()
pipeline.topk().add(topk_key, item)
pipeline.cms().incrby(cms_key, {item: 1})
pipeline.execute()  # 1 roundtrip

Cùng module RedisBloom, TDigest giải quyết bài toán liên quan: ước tính percentile (p50, p95, p99) từ stream số liệu, không lưu toàn bộ values. Use case phổ biến là latency percentile dashboard:

# Tạo TDigest (compression càng cao thì càng chính xác ở tail)
TDIGEST.CREATE latency:api compression 100

# Thêm observation (ms)
TDIGEST.ADD latency:api 12.3 45.1 8.7 120.5

# Query quantile
TDIGEST.QUANTILE latency:api 0.5 0.95 0.99
# Output: 1) 12.3   (p50)
#         2) 45.1   (p95)
#         3) 120.5  (p99)

Khác biệt với Top-K/CMS:

• TDigest làm việc với giá trị số (float), không phải string item.
• Phù hợp: latency, request size, score phân phối.
• Không phù hợp: đếm tần suất xuất hiện string items.

Trong monitoring pipeline: CMS/Top-K cho throughput metrics (event/s per URL), TDigest cho latency distribution — hai loại structure khác nhau cho hai câu hỏi khác nhau.

Ngưỡng thực tế: nếu unique items < 10k và throughput < 50k/s, Sorted Set đơn giản hơn và không cần sai số. Trên ngưỡng đó hoặc khi memory là constraint, Top-K/CMS phù hợp hơn.

Anti-patterns

• Dùng Top-K khi cần exact rank: Top-K là probabilistic — nó có thể miss một item thực sự trong top-K (false negative). Nếu yêu cầu "chính xác hoàn toàn", dùng Sorted Set.
• CMS dimension quá nhỏ: width=100, depth=3 cho 1 triệu event → error 5%+ của tổng event, count estimate sai lệch lớn. Dùng CMS.INITBYPROB để tính dimension từ error requirement.
• Quên reset / rotate key theo window: Top-K không có built-in sliding window. Nếu không rotate, all-time items sẽ dominate, trending mất ý nghĩa.
• Combine Sorted Set exact + Top-K cho cùng metric: double memory, không thêm giá trị. Chọn một approach.
• Dùng cho dataset nhỏ (< 1k unique items): với dataset nhỏ, Sorted Set đơn giản hơn, không phức tạp hóa với probabilistic structures.
• Hiển thị count từ Top-K trực tiếp trên dashboard: Top-K count (nếu có) kém chính xác hơn CMS. Luôn dùng CMS.QUERY cho display count.

Best practices

• Top-K cho UI dashboard "trending" — cần tên items, không cần count chính xác.
• CMS cho frequency estimate trong stream pipeline — cần count, items đã biết từ nguồn khác.
• Combine TOPK.LIST + CMS.QUERY khi cần cả tên lẫn count trên dashboard.
• Time bucket với TTL tự động để không cần cron job dọn key.
• Document error rate trong dashboard UI: "~0.1% error, window: 1h" — người dùng cần biết đây là estimate.
• TDigest cho percentile metrics song song với Top-K/CMS cho count metrics.
• Trong Kafka/stream consumer: batch local (Counter) trước khi gọi CMS.INCRBY để giảm Redis roundtrip.

Tổng kết

• Top-K (HeavyKeeper) duy trì K candidate phổ biến nhất với memory O(K), không phụ thuộc số unique items. Tham số decay kiểm soát tốc độ "quên" item cũ.
• Count-Min Sketch dùng 2D array depth×width với D hash function; query trả MIN của D cells — luôn over-estimate. Memory O(W×D) cố định.
• Hai structure bổ trợ nhau: Top-K biết ai trending, CMS biết bao nhiêu lần. Combine TOPK.LIST + CMS.QUERY để có cả hai.
• Time bucketing với TTL là pattern chuẩn để implement sliding window mà không cần cron job.
• CMS over-estimate fit cho anti-spam/rate-limiting; không fit cho billing/accounting cần exact count.
• Dùng CMS.INITBYPROB để tính dimension từ error requirement thay vì đoán width/depth thủ công.

Quiz 5 câu

1. Tại sao Count-Min Sketch chỉ over-estimate mà không bao giờ under-estimate? Giải thích qua cơ chế counter trong bảng 2D.
2. Bạn cần Top-K 100 items từ stream 500k event/s, window 1 giờ, reset hàng giờ. Viết phác thảo code Python để init, track và rotate key.
3. Tham số decay trong Top-K ảnh hưởng như thế nào đến kết quả trending? Decay=1.0 và decay=0.7 khác nhau ra sao trong practice?
4. Khi nào nên dùng Sorted Set thay vì Top-K/CMS? Đưa ra ngưỡng cụ thể về số unique items và throughput.
5. Giải thích pattern combine Top-K + CMS: tại sao cần cả hai thay vì chỉ một trong hai? Hai Redis calls nào được dùng cho display dashboard?

Đáp án gợi ý

1. Counter trong bảng chỉ được tăng (INCRBY), không bao giờ giảm. Nhiều item có thể hash vào cùng cell (collision), làm counter cell đó cao hơn thực tế của bất kỳ item nào. Query lấy MIN trên D rows độc lập để giảm ảnh hưởng collision, nhưng MIN vẫn ≥ true count vì tất cả cells chỉ tăng. Do đó estimate ≥ true count (over) và không bao giờ < true count (không under).
2. Phác thảo: hàm hour_key() tạo key từ int(time.time()) // 3600; hàm init check r.exists(key) → gọi r.topk().reserve(key, 100, 16, 8, 0.9) + r.expire(key, 7200); hàm track gọi r.topk().add(key, item); rotation tự động qua TTL — key giờ cũ tự xóa sau 2 giờ.
3. Decay=1.0: counter không bao giờ giảm — item từ tháng trước nếu đã có counter cao thì rất khó bị kick; trending phản ánh all-time, chậm phản ứng với xu hướng mới. Decay=0.7: counter giảm nhanh hơn khi có collision — item trending hiện tại nhanh chóng thay thế item cũ; nhưng top-K kém ổn định hơn, có thể fluctuate nhiều trong stream ít dữ liệu.
4. Dùng Sorted Set khi: unique items < 10k VÀ throughput < 50k ops/s VÀ cần exact count. Trên các ngưỡng này, hoặc khi cần nhiều window song song, memory của Sorted Set trở thành bottleneck và Top-K/CMS phù hợp hơn.
5. Top-K biết items nào trong top nhưng không có count chính xác. CMS biết count cho bất kỳ item nào nhưng không biết item nào trong top. Kết hợp: TOPK.LIST lấy candidate list → CMS.QUERY batch lấy count cho tất cả candidates → sort theo count để hiển thị. Total: 2 Redis calls per dashboard refresh.

Bài tiếp theo

Bài 97 đi vào Cohort Analysis — Retention Phân Tầng: pattern phân tích nhóm người dùng theo thời điểm đăng ký và đo retention qua các khoảng thời gian tiếp theo.

Tham khảo

• Redis Docs — Top-K
• Redis Docs — Count-Min Sketch
• Redis Docs — Top-K Commands Reference
• Redis Docs — CMS Commands Reference
• redis-py — TOPKCommands API
• Wang et al. — HeavyKeeper: An Accurate Algorithm for Finding Top-k Elephant Flows (arXiv 2018)
• Cormode & Muthukrishnan — An Improved Data Stream Summary: The Count-Min Sketch (2005)