Thuật toán 8 — Thuật toán thực chiến cho dữ liệu lớn

Khi dữ liệu không chịu nằm yên trong RAM

Cả loạt bài trước, chúng ta ngầm giả định một điều: dữ liệu có thể nạp hết vào bộ nhớ, và ta được quét nó bao nhiêu lần tuỳ thích. Sort được vì mảng nằm gọn trong RAM. Dựng set để đối soát được vì cả hai danh sách vừa với bộ nhớ. Nhưng trong thực chiến data engineering, có một lớp bài toán mà cả hai giả định đó sụp đổ:

• Dữ liệu quá lớn — bảng log 500GB, không máy nào nạp hết vào RAM.
• Dữ liệu vô tận (stream) — luồng giao dịch, click, sự kiện Kafka chảy liên tục, không có điểm kết thúc để bạn "quét lần hai".
• Cần trả lời trong thời gian thực — không đợi được một job batch chạy qua đêm.

Khi cả ba điều này gặp nhau, các thuật toán "sách giáo khoa" trở nên vô dụng. Bạn không thể sort một luồng không có điểm cuối. Bạn không thể set(toàn_bộ_dữ_liệu) khi "toàn bộ" là hàng tỷ dòng thay đổi mỗi giây. Cần một họ thuật toán khác, xây trên hai nguyên lý:

1. One-pass (một lượt): mỗi phần tử chỉ được nhìn đúng một lần, rồi bỏ đi. Không quay lại.
2. Xấp xỉ (approximate): chấp nhận đánh đổi độ chính xác lấy bộ nhớ và tốc độ. Câu trả lời "khoảng 4,7 triệu khách, sai số ±1%" mà tốn 12KB thường hữu ích hơn con số tuyệt đối chính xác mà tốn 40GB.

Nghe qua tưởng là thoả hiệp tồi, nhưng hãy nghĩ kỹ: khi sếp hỏi "hôm nay có bao nhiêu khách duy nhất truy cập app?", con số 4.712.388 và 4.7 triệu ±1% dẫn tới cùng một quyết định kinh doanh. Cái giá để có chữ số cuối cùng chính xác có thể là gấp nghìn lần bộ nhớ — một cái giá phi lý. Bài này nối tiếp tư duy độ phức tạp: ở đó ta tối ưu thời gian; ở đây ta tối ưu bộ nhớ và số lượt quét — chiều kích quyết định khi dữ liệu lớn thật sự.

1. Streaming / one-pass: thống kê chạy

Bài toán mở màn đơn giản nhất: tính trung bình của một luồng số. Cách ngây thơ là cộng dồn tất cả rồi chia — nhưng để làm vậy bạn phải giữ hoặc quét lại tất cả. Với luồng vô tận thì bất khả thi. Lời giải one-pass: giữ tổng chạy và đếm chạy, cập nhật từng phần tử. Bộ nhớ O(1) — chỉ hai biến, bất kể luồng dài bao nhiêu.

Trung bình thì dễ. Nhưng phương sai (variance) mới là cái bẫy. Công thức "sách giáo khoa" E[x²] − E[x]² khi tính one-pass đòi cộng dồn cả sum(x) lẫn sum(x²), và với số lớn nó mất ổn định số học nghiêm trọng (trừ hai số khổng lồ gần bằng nhau → sai số làm tròn nuốt hết kết quả, thậm chí ra phương sai âm). Đây là chỗ thuật toán Welford toả sáng: nó cập nhật mean và variance chạy một cách ổn định, chỉ giữ vài biến.

# (minh hoạ) — Welford: mean & variance chạy, one-pass, O(1) bộ nhớ
class RunningStats:
    def __init__(self):
        self.n = 0
        self.mean = 0.0
        self.M2 = 0.0        # tổng bình phương độ lệch so với mean chạy
        self.min = float("inf")
        self.max = float("-inf")

    def update(self, x: float) -> None:
        self.n += 1
        delta = x - self.mean
        self.mean += delta / self.n          # cập nhật mean
        delta2 = x - self.mean               # độ lệch so với mean MỚI
        self.M2 += delta * delta2            # tích luỹ ổn định
        if x < self.min: self.min = x
        if x > self.max: self.max = x

    @property
    def variance(self) -> float:
        return self.M2 / self.n if self.n else 0.0

    @property
    def std(self) -> float:
        return self.variance ** 0.5

# Dùng: nạp từng dòng, không giữ toàn bộ
stats = RunningStats()
for gia_tri in doc_luong_giao_dich():   # generator, đọc từng dòng
    stats.update(gia_tri)
print(f"n={stats.n} mean={stats.mean:.2f} std={stats.std:.2f} "
      f"min={stats.min} max={stats.max}")

Điểm mấu chốt: RunningStats chiếm vài chục byte dù bạn nạp 10 dòng hay 10 tỷ dòng. Đó là bản chất one-pass.

Sliding window — thống kê trên cửa sổ trượt

Nhiều bài toán không cần "toàn bộ lịch sử" mà cần N sự kiện gần nhất hoặc T phút gần nhất. Ví dụ kinh điển trong ngân hàng: AML velocity — "một tài khoản thực hiện quá bao nhiêu giao dịch trong 10 phút qua thì cảnh báo?". Cấu trúc phù hợp là collections.deque với maxlen, hoặc deque tự loại phần tử hết hạn (nối Cấu trúc dữ liệu — deque cho thêm/xoá hai đầu O(1)):

# (minh hoạ) — velocity: đếm giao dịch trong cửa sổ 10 phút trượt
from collections import deque

class VelocityWindow:
    def __init__(self, window_seconds: float):
        self.window = window_seconds
        self.events = deque()        # chứa timestamp, cũ ở đầu

    def add_and_count(self, now: float) -> int:
        self.events.append(now)
        limit = now - self.window
        while self.events and self.events[0] < limit:
            self.events.popleft()    # loại giao dịch đã ra khỏi cửa sổ
        return len(self.events)      # số giao dịch trong 10 phút qua

Bộ nhớ ở đây là O(số sự kiện trong cửa sổ) — không phải toàn bộ lịch sử. Ta sẽ gặp lại đúng ý tưởng này ở phần rate limiting.

2. Reservoir sampling — lấy mẫu ngẫu nhiên từ luồng không biết trước độ dài

Bài toán: bạn muốn lấy k mẫu ngẫu nhiên đều từ một luồng, nhưng không biết luồng dài bao nhiêu và không thể giữ hết. Ví dụ: lấy 1.000 giao dịch ngẫu nhiên trong ngày để đội QA kiểm thử, hoặc lấy mẫu log để phân tích — trong khi log vẫn đang chảy và bạn không biết cuối ngày sẽ có 2 triệu hay 200 triệu dòng.

Nếu biết trước tổng số n, bài toán tầm thường: random.sample(range(n), k). Nhưng không biết n thì sao? Đây là lúc Algorithm R (Vitter, 1985) vào cuộc, với một mẹo đẹp đến bất ngờ:

• Giữ k phần tử đầu tiên vào "hồ chứa" (reservoir).
• Với phần tử thứ i (i > k): sinh số ngẫu nhiên j trong [0, i). Nếu j < k, thay phần tử thứ j trong hồ bằng phần tử mới.

Kết quả: sau khi xử lý xong m phần tử, mỗi phần tử đã thấy đều có xác suất đúng bằng k/m nằm trong hồ — tức mẫu hoàn toàn đều, dù ta chỉ đi một lượt và dùng bộ nhớ O(k).

# (minh hoạ) — Reservoir sampling (Algorithm R): k mẫu đều, một lượt, O(k)
import random
from typing import Iterable, TypeVar

T = TypeVar("T")

def reservoir_sample(stream: Iterable[T], k: int) -> list[T]:
    reservoir: list[T] = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)          # đổ đầy hồ k phần tử đầu
        else:
            j = random.randint(0, i)        # j trong [0, i]
            if j < k:
                reservoir[j] = item          # thay chỗ j bằng phần tử mới
    return reservoir

# Lấy 1.000 dòng log ngẫu nhiên mà không cần biết tổng số dòng
mau = reservoir_sample(doc_log_stream(), k=1000)

Tại sao xác suất ra đúng k/m? Trực giác: khi phần tử thứ i tới, nó được vào hồ với xác suất k/i; và mỗi phần tử đang trong hồ "sống sót" qua các bước sau với xác suất bù trừ vừa đủ để mọi phần tử cân bằng về k/m ở cuối. Cái hay là bạn không cần chứng minh lại mỗi lần — chỉ cần tin và dùng. Đây chính là lý do bài này dặn: hiểu thuật toán để chọn đúng, còn phần cài đặt tinh vi thì dùng thư viện đã kiểm chứng.

3. Ước lượng gần đúng — họ thuật toán "sketch"

Đây là phần lõi và cũng là phần "ảo diệu" nhất. Sketch là những cấu trúc dữ liệu nhỏ tí xíu, tổng hợp thông tin từ luồng khổng lồ, trả lời một câu hỏi cụ thể với sai số có kiểm soát.

3.1. HyperLogLog — đếm số phần tử phân biệt (cardinality)

Câu hỏi: "Có bao nhiêu khách duy nhất hôm nay?" Cách chính xác: set() mọi user_id rồi đếm — nhưng với 500 triệu sự kiện, cái set đó ngốn hàng chục GB RAM. HyperLogLog (HLL) trả lời câu này với sai số ~1-2% mà chỉ tốn cỡ vài KB.

Ý tưởng cốt lõi dựa trên xác suất: hash mỗi phần tử ra một chuỗi bit ngẫu nhiên đều. Trong các hash ngẫu nhiên, khoảng một nửa bắt đầu bằng bit 0, một phần tư bằng 00, một phần tám bằng 000... Nếu bạn từng thấy một hash có 10 số 0 dẫn đầu, khả năng cao bạn đã xử lý cỡ 2¹⁰ ≈ 1024 phần tử phân biệt. HLL chia dữ liệu vào m "register", theo dõi số 0 dẫn đầu lớn nhất ở mỗi register, rồi lấy trung bình điều hoà để ước lượng — cách chia này giảm phương sai so với dùng một biến duy nhất.

Sai số chuẩn của HLL là 1.04 / √m. Redis dùng m = 16.384 register mặc định → sai số ~0,81%, tốn khoảng 12KB, mà đếm được cardinality tới hàng tỷ. Con số then chốt cần nhớ: bộ nhớ gần như cố định, không tăng theo số phần tử — trái ngược hoàn toàn với set.

Thực chiến, bạn hầu như không tự cài HLL. Nó có sẵn khắp nơi:

-- (minh hoạ) — BigQuery: đếm khách duy nhất bằng HLL, cực rẻ trên tỷ dòng
SELECT
  DATE(event_time)              AS ngay,
  APPROX_COUNT_DISTINCT(user_id) AS khach_duy_nhat   -- HLL++ bên dưới
FROM `project.dataset.events`
GROUP BY ngay;

APPROX_COUNT_DISTINCT của BigQuery dùng HLL++ ở tầng dưới, rẻ hơn COUNT(DISTINCT ...) chính xác cả về chi phí quét lẫn bộ nhớ shuffle — chi tiết tối ưu chi phí ở bài BigQuery chi phí & hiệu năng. Redis (PFADD/PFCOUNT), Spark, Presto đều có HLL sẵn.

3.2. Count-Min Sketch — ước lượng tần suất (heavy hitters)

HLL đếm có bao nhiêu loại khác nhau. Count-Min Sketch (CMS) trả lời câu khác: "Phần tử X xuất hiện bao nhiêu lần?" và mở rộng ra "Top phần tử xuất hiện nhiều nhất là gì?" (heavy hitters) — ví dụ: top IP gọi API nhiều nhất, top mã giao dịch bị lặp, top sản phẩm được xem.

CMS là một mảng 2 chiều d × w (depth × width), khởi tạo 0, kèm d hàm hash độc lập. Khi phần tử tới: với mỗi hàng, hash phần tử ra một cột rồi tăng ô đó lên 1. Khi truy vấn tần suất: hash phần tử ra d ô, lấy giá trị nhỏ nhất trong đó (vì va chạm chỉ làm ô phồng lên, nên min là ước lượng gần nhất).

Đặc tính quan trọng: CMS chỉ ước lượng thừa, không bao giờ thiếu (over-estimate, never under). Sai số bị chặn bởi ε·N với xác suất ≥ 1 − δ, trong đó chọn w = ⌈e/ε⌉ và d = ⌈ln(1/δ)⌉.

# (minh hoạ) — Count-Min Sketch tối giản
import hashlib

class CountMinSketch:
    def __init__(self, width: int, depth: int):
        self.w, self.d = width, depth
        self.table = [[0] * width for _ in range(depth)]

    def _hashes(self, key: str):
        for i in range(self.d):
            h = hashlib.md5(f"{i}:{key}".encode()).hexdigest()
            yield int(h, 16) % self.w

    def add(self, key: str, count: int = 1) -> None:
        for row, col in enumerate(self._hashes(key)):
            self.table[row][col] += count

    def estimate(self, key: str) -> int:
        return min(self.table[row][col]
                   for row, col in enumerate(self._hashes(key)))  # min = ước lượng

Với dữ liệu thật, dùng thư viện như datasketches (Apache) đã tối ưu — cài tay chỉ để hiểu bản chất.

3.3. Bloom filter — kiểm tra thành viên (nhắc lại)

Đã bàn kỹ ở Strings & hashing: Bloom filter trả lời "phần tử X đã từng xuất hiện chưa?" với bộ nhớ nhỏ, chấp nhận false positive (có thể báo "có" nhầm) nhưng không bao giờ false negative (đã báo "chưa" thì chắc chắn chưa). Cùng triết lý với HLL/CMS: đánh đổi độ chính xác lấy bộ nhớ. Use case: chặn duplicate, kiểm tra "khách này đã thấy quảng cáo chưa" trước khi tra CSDL đắt tiền.

Chọn sketch nào? Nhớ theo câu hỏi cần trả lời:

4. Rate limiting — kiểm soát tần suất bằng thuật toán

Rate limiting là thuật toán streaming "trá hình": mỗi request là một sự kiện trong luồng, và ta phải quyết định cho qua hay chặn ngay lập tức, với bộ nhớ tối thiểu cho mỗi client. Use case: chống lạm dụng API (nối API ingestion & rate limit), bảo vệ hệ thống khỏi bị dội, kiểm soát tần suất giao dịch nghi vấn.

Token bucket — lựa chọn mặc định

Mô hình: mỗi client có một "xô" chứa tối đa capacity token. Token được đổ thêm đều đặn với tốc độ refill_rate token/giây. Mỗi request tiêu 1 token; hết token thì bị chặn. Điểm hay: cho phép burst (xô đầy → chịu được một đợt dồn dập tới capacity request), nhưng về lâu dài giới hạn ở đúng refill_rate. Bộ nhớ mỗi client chỉ hai số: token hiện tại và mốc thời gian đổ gần nhất.

# (minh hoạ) — Token bucket rate limiter
import time

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity          # số token tối đa (kích thước burst)
        self.refill_rate = refill_rate    # token nạp mỗi giây (throughput bền)
        self.tokens = capacity
        self.last = time.monotonic()

    def allow(self, cost: float = 1.0) -> bool:
        now = time.monotonic()
        # nạp token theo thời gian đã trôi, không vượt capacity
        self.tokens = min(self.capacity,
                          self.tokens + (now - self.last) * self.refill_rate)
        self.last = now
        if self.tokens >= cost:
            self.tokens -= cost
            return True                    # cho qua
        return False                       # chặn (429 Too Many Requests)

# 10 request/giây, chịu burst tối đa 20
bucket = TokenBucket(capacity=20, refill_rate=10)
if bucket.allow():
    handle_request()
else:
    return_429()

Chú ý token bucket không lưu danh sách timestamp — nó chỉ tính token nạp thêm theo thời gian trôi. Đó là lý do nó siêu tiết kiệm và là default mạnh nhất cho API.

Sliding window log — chính xác nhưng đắt

Cách khác: lưu timestamp của từng request (giống VelocityWindow ở mục 1), loại các timestamp đã ra khỏi cửa sổ, rồi đếm. Chính xác tuyệt đối nhưng tốn O(số request trong cửa sổ) bộ nhớ mỗi client. Chỉ dùng khi thật sự cần đếm chính xác và cần audit trail (ví dụ endpoint thanh toán/xác thực). Còn lại, token bucket gần như luôn thắng về chi phí.

Trong hệ phân tán, state của rate limiter thường đặt ở Redis (nhiều instance API chia sẻ chung) — nhưng thuật toán bên dưới vẫn là token bucket hoặc sliding window bạn vừa thấy.

5. Tự viết hay dùng có sẵn?

Đây là câu hỏi thực dụng nhất, và câu trả lời trung thực là: đa số trường hợp, ĐỪNG tự viết.

Nên dùng có sẵn khi:

• Sort, hash, index, join, COUNT(DISTINCT) — CSDL và thư viện chuẩn đã tối ưu hơn bất cứ thứ gì bạn viết tay, qua hàng chục năm. Cần cardinality xấp xỉ? APPROX_COUNT_DISTINCT của BigQuery. Cần sketch? datasketches. Cần rate limit phân tán? Redis. Tự cài lại = tự chuốc bug.
• Bài toán đã có lời giải chuẩn — reservoir sampling, HLL, CMS đều nằm sẵn trong thư viện đã kiểm chứng thống kê cẩn thận. Bản tự viết dễ sai xác suất một cách âm thầm (chạy được, ra số, nhưng lệch mà bạn không biết).

Nên tự viết (hoặc ít nhất hiểu sâu) khi:

• Ràng buộc đặc thù thư viện không đáp ứng — ví dụ velocity theo logic AML riêng của ngân hàng, cửa sổ trượt theo múi giờ nghiệp vụ.
• Streaming realtime cần tích hợp chặt vào pipeline (Flink/Spark Structured Streaming, consumer Kafka) mà thư viện ngoài không ghép vào được sạch sẽ.
• Cần hiểu để chọn và tối ưu đúng — ngay cả khi dùng thư viện, bạn phải hiểu HLL sai số 1.04/√m để chọn m, hiểu CMS chỉ thừa-không-thiếu để đọc kết quả đúng, hiểu token bucket khác sliding window để chọn cho endpoint phù hợp. Đây mới là giá trị thật của việc học thuật toán: không phải để gõ lại, mà để quyết định đúng và tối ưu đúng chỗ (nối tư duy tối ưu CSDL, Spark, Kafka).

Nói gọn: hiểu thuật toán ở mức chọn được, đọc được kết quả, và tinh chỉnh được tham số — rồi để thư viện làm phần cài đặt.

Use case thực tế

1. Đếm khách duy nhất trên dữ liệu khổng lồ. Bảng event 500 triệu dòng/ngày. COUNT(DISTINCT user_id) chính xác tốn shuffle khổng lồ và tiền. Thay bằng APPROX_COUNT_DISTINCT (HLL++): sai số ~1% nhưng rẻ hơn nhiều lần — và với dashboard đếm khách, sai số 1% không đổi quyết định nào cả. Đây là đánh đổi đúng đắn, không phải cẩu thả.

2. Rate limit API ingestion. Cổng nhận dữ liệu từ đối tác dễ bị dội request (cố ý hoặc do bug retry của họ). Đặt token bucket capacity=100, refill_rate=50/s cho mỗi API key: chịu được burst hợp lý, nhưng chặn kẻ dội hàng nghìn request/giây bằng 429 trước khi chúng làm sập backend. State đặt ở Redis để nhiều instance dùng chung.

3. Lấy mẫu log để phân tích. Log lỗi production chảy hàng triệu dòng/giờ; không thể lưu hết, cũng không muốn chỉ lấy "1000 dòng đầu" (thiên lệch về đầu giờ). Reservoir sampling lấy 1000 dòng ngẫu nhiên đều trong cả giờ, một lượt, O(k) bộ nhớ — mẫu này đại diện đúng cho toàn bộ luồng để đội SRE phân tích.

Ghi nhớ

• Khi dữ liệu vô tận hoặc quá lớn, các thuật toán one-pass/xấp xỉ thay thế cho "nạp hết + quét nhiều lần". Nguyên lý: mỗi phần tử nhìn một lần, chấp nhận sai số để đổi lấy bộ nhớ/tốc độ.
• Welford tính mean/variance chạy ổn định, O(1) bộ nhớ — đừng dùng E[x²]−E[x]² với số lớn (mất ổn định số học).
• Reservoir sampling lấy k mẫu đều từ luồng không biết độ dài, một lượt, O(k) — xác suất mỗi phần tử vào hồ là k/m.
• HyperLogLog đếm cardinality xấp xỉ, sai số ~1.04/√m, bộ nhớ gần cố định — dùng APPROX_COUNT_DISTINCT/Redis, đừng tự cài.
• Count-Min Sketch ước lượng tần suất, chỉ thừa không thiếu; Bloom filter kiểm tra thành viên, không false negative. Chọn sketch theo câu hỏi cần trả lời.
• Token bucket là default mạnh cho rate limit (cho burst, tốn 2 số/client); sliding window log chính xác hơn nhưng tốn O(n) bộ nhớ.
• Đa số nên dùng thư viện/CSDL; tự viết chỉ khi ràng buộc đặc thù hoặc streaming realtime. Hiểu thuật toán để chọn đúng và tinh chỉnh tham số, không phải để gõ lại.

Tổng kết series "Thuật toán & Cấu trúc dữ liệu ứng dụng"

Cả loạt bài xoay quanh một câu hỏi duy nhất: làm sao chọn giải pháp đúng theo bài toán và quy mô?

• Độ phức tạp cho ta thước đo — biết trước một thiết kế sẽ "chết" ở quy mô nào.
• Cấu trúc dữ liệu cho ta công cụ — set/dict O(1) là vũ khí hạ O(n²) xuống O(n).
• Sorting, searching, đệ quy, đồ thị cho ta các mẫu giải kinh điển, đã được chứng minh tối ưu.
• Strings & hashing và bài này mở rộng sang quy mô thực chiến: khi dữ liệu không nằm gọn trong RAM, ta chuyển từ "chính xác + nhiều lượt" sang "một lượt + xấp xỉ có kiểm soát".

Tư duy xuyên suốt không phải là thuộc lòng thuật toán, mà là phản xạ đặt đúng câu hỏi trước khi viết dòng code đầu tiên: Dữ liệu lớn cỡ nào? Nó có nằm vừa RAM không? Mình được quét mấy lần? Mình cần chính xác tuyệt đối hay xấp xỉ là đủ? Trả lời được bốn câu đó, bạn sẽ tự biết nên dùng set, dùng sort, hay rút HyperLogLog ra — và quan trọng hơn, biết khi nào để CSDL/thư viện làm thay mình. Đó chính là ranh giới giữa người viết được code chạy và người thiết kế được hệ thống chịu tải.