Reservoir sampling — mẫu ngẫu nhiên từ stream

TL;DR: Bài toán: chọn k phần tử ngẫu nhiên từ stream độ dài n chưa biết trước, chỉ dùng O(k) bộ nhớ. Algorithm R (Vitter 1985): giữ k phần tử đầu làm "reservoir"; với phần tử thứ i (i > k), nhận vào reservoir với xác suất k/i, thay thế ngẫu nhiên 1 trong k slot. Cuối stream, mỗi phần tử đều có xác suất đúng k/n nằm trong reservoir — đều xác suất (uniform random). Ứng dụng rộng: log sampling, A/B test routing, random page từ database cursor, distributed sampling không cần biết tổng size.

Hệ thống monitoring của bạn nhận 10 triệu event mỗi giờ. Bạn cần lấy 1000 event đại diện để phân tích — nhưng không thể lưu tất cả. Giải pháp đơn giản: lấy 1000 event đầu tiên? Sai — sẽ thiên vị về buổi sáng, bỏ qua spike buổi chiều. Lấy mỗi event thứ 10.000? Sai — bỏ qua burst ngắn giữa các checkpoint. Bạn cần mẫu đều xác suất (uniform random sample): mỗi event có cùng xác suất được chọn, bất kể vị trí nào trong stream.

Reservoir sampling giải quyết bài toán này với O(k) bộ nhớ mà không cần biết n — ngay cả khi stream chưa kết thúc, sample hiện tại luôn là uniform random sample của những gì đã thấy.

1. Phát biểu bài toán chính xác

Input: stream vô tận (hoặc độ dài n chưa biết) các phần tử x_1, x_2, ..., x_n.

Output: tập k phần tử sao cho mỗi phần tử trong stream có xác suất đúng bằng k/n nằm trong kết quả cuối.

Ràng buộc: bộ nhớ làm việc O(k) — không được lưu cả stream.

Nếu biết n trước, có thể dùng Fisher-Yates shuffle rồi lấy k phần tử đầu — O(n) thời gian, O(n) bộ nhớ. Reservoir sampling phá bỏ ràng buộc bộ nhớ O(n) mà vẫn đảm bảo tính chất xác suất đồng đều.

2. Algorithm R — Vitter 1985

function reservoirSample(stream, k):
    reservoir <- []

    -- Bước 1: điền k phần tử đầu vào reservoir
    for i từ 0 đến k-1:
        reservoir[i] <- stream[i]

    -- Bước 2: xử lý phần còn lại
    for i từ k đến n-1:                 -- i là chỉ số 0-based
        j <- randomInt(0, i)            -- j ngẫu nhiên trong [0..i] đều
        if j < k:                       -- xác suất k/(i+1) ~ k/i khi i lớn
            reservoir[j] <- stream[i]   -- thay thế slot j

    return reservoir
// Time: O(n)  Space: O(k)

Lưu ý: randomInt(0, i) sinh số nguyên đều trong đoạn [0, i] — tổng i+1 giá trị. Xác suất phần tử thứ i (0-based, i >= k) được chọn = k / (i+1).

2.1 Trace với k=2, n=5

Stream: [A, B, C, D, E]

Sau i=4, mỗi phần tử trong tập [A,B,C,D,E] có xác suất 2/5 = k/n nằm trong reservoir.

flowchart LR
    S(["Stream x_1..x_n\n(n chưa biết)"])
    FILL["Điền k phần tử đầu\nvào reservoir"]
    PROC{"i >= k?\n(còn phần tử)"}
    RAND["j = rand(0, i)\nj < k?"]
    SWAP["reservoir[j] <- x_i\n(thay thế)"]
    SKIP["Bỏ qua x_i"]
    NEXT["i++"]
    OUT(["Reservoir k phần tử\n(uniform sample)"])

    S --> FILL --> PROC
    PROC -->|"còn"| RAND
    RAND -->|"j < k"| SWAP --> NEXT --> PROC
    RAND -->|"j >= k"| SKIP --> NEXT --> PROC
    PROC -->|"hết"| OUT

3. Chứng minh xác suất đồng đều

Mệnh đề: sau khi xử lý n phần tử, mỗi phần tử x_i (1 <= i <= n) có xác suất đúng k/n nằm trong reservoir.

Chứng minh bằng quy nạp trên n.

Cơ sở: n = k. Cả k phần tử đều trong reservoir → xác suất k/k = 1. Đúng.

Bước quy nạp: Giả sử sau n-1 phần tử, mọi phần tử x_i (i ≤ n-1) có xác suất k/(n-1) trong reservoir. Ta cần chứng minh sau khi xử lý x_n, mọi phần tử (kể cả x_n) có xác suất k/n.

Xác suất x_n được chọn:

P(x_n vào reservoir) = k/n

Vì j = randomInt(0, n-1) trong [0, n-1] (n giá trị), xác suất j < k = k/n.

Xác suất phần tử cũ x_i (i < n) vẫn còn trong reservoir:

P(x_i còn lại) = P(x_i trong reservoir sau n-1 bước) × P(x_i không bị thay khi xử lý x_n)
               = k/(n-1) × (1 - P(x_n chọn đúng slot của x_i))
               = k/(n-1) × (1 - (k/n) × (1/k))
               = k/(n-1) × (1 - 1/n)
               = k/(n-1) × (n-1)/n
               = k/n

Dòng thứ ba: khi x_n được chọn (xác suất k/n), slot bị thay là 1 trong k slot đều nhau → xác suất chọn đúng slot x_i là 1/k.

Vậy mọi phần tử có xác suất đúng k/n. QED.

4. Weighted reservoir sampling

Algorithm R giả định mọi phần tử có trọng số đều nhau. Thực tế, log của transaction $100 quan trọng hơn log click thông thường. Weighted reservoir sampling (Efraimidis & Spirakis 2006) gán key u^(1/w_i) cho mỗi phần tử (u là số ngẫu nhiên uniform (0,1], w_i là trọng số), rồi giữ k phần tử có key lớn nhất.

function weightedReservoirSample(stream, k):
    H <- MaxHeap()                          -- heap theo key

    for each phần tử (x_i, weight_i) trong stream:
        key_i <- random(0, 1) ^ (1.0 / weight_i)  -- ^ là lũy thừa
        if H.size() < k:
            H.push((key_i, x_i))
        else if key_i > H.min():            -- min-heap của key để pop nhỏ nhất
            H.pop()
            H.push((key_i, x_i))

    return H.elements()
// Time: O(n log k)  Space: O(k)

Xác suất phần tử i được chọn tỉ lệ với weight_i — chứng minh xem Efraimidis & Spirakis (2006).

5. Ứng dụng thực tế

Log sampling hệ thống: Nginx/Envoy giữ reservoir 10.000 request để phân tích latency. Mỗi request đến: quyết định keep/drop theo algorithm R. Kết quả: sample uniform theo thời gian, không bias burst hay idle.

A/B test routing: Khi cần chọn ngẫu nhiên 5% user vào group B từ user stream, reservoir sampling đảm bảo 5% đều xác suất không phụ thuộc tổng số user.

Random sample từ database cursor: Thay vì SELECT * FROM logs ORDER BY RANDOM() LIMIT 1000 (scan toàn bảng + sort — O(n log n)), dùng reservoir sampling qua cursor: O(n) scan, O(k) memory, không cần sort.

Distributed sampling: Mỗi node giữ reservoir k phần tử của mình. Để merge m reservoir thành reservoir k phần tử tổng: dùng weighted reservoir với weight tỉ lệ kích thước stream của mỗi node — đảm bảo tính đồng đều trên toàn distributed stream.

6. Pitfall

Pitfall 1 — Dùng random() < k/n thay vì randomInt(0, i)

-- SAI: nếu không biết n, tính k/n impossible
-- Nếu biết n thì cũng sai vì xác suất mỗi phần tử không đồng đều theo vị trí

-- ĐÚNG: randomInt(0, i) — i là chỉ số hiện tại, tăng dần
-- Xác suất k/(i+1) tự động điều chỉnh theo vị trí trong stream

Pitfall 2 — Chọn slot thay thế không đều

-- SAI: luôn thay slot cuối cùng được thêm vào
reservoir[lastInserted] <- stream[i]    -- bias: slot cuối bị thay nhiều nhất

-- ĐÚNG: chọn slot ngẫu nhiên đều trong [0, k-1]
j <- randomInt(0, i)
if j < k:
    reservoir[j] <- stream[i]          -- j đều trong k slot

Pitfall 3 — Quên trường hợp stream ngắn hơn k

-- SAI: code giả định stream luôn có >= k phần tử
-- → index out of bounds hoặc trả về reservoir chưa đầy

-- ĐÚNG: trả về min(k, n) phần tử
function reservoirSample(stream, k):
    ...
    return reservoir[0 .. min(k, đã_đọc) - 1]

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

• Hash function: weighted reservoir sampling dùng random key u^(1/w) — ý tưởng tương tự consistent hashing: mapping ngẫu nhiên có cấu trúc. Hash function tốt cũng là nền của nhiều probabilistic algorithm trong module này.
• Amortized analysis: chi phí amortized của mỗi phần tử trong stream là O(1) (chỉ gọi randomInt + có thể 1 swap) — tổng O(n) thời gian, mặc dù phần tử đầu (điền reservoir) và phần tử sau (test + thay) có chi phí khác nhau.
• HyperLogLog: cùng lớp thuật toán streaming probabilistic — reservoir lưu mẫu đại diện (exact k phần tử), HyperLogLog ước lượng cardinality. Hiểu cả hai cho thấy tradeoff: exact vs approximate, sample vs sketch.
• Count-Min Sketch: probabilistic data structure khác cho streaming — đếm tần suất xấp xỉ thay vì lấy mẫu. Cross-reference để thấy cả hệ sinh thái "big data structures".
• Mini-challenge: Top-K: reservoir sampling là công cụ cho bài top-k — sampling trước rồi tìm top-k trên sample, khi n quá lớn để exact top-k.

📚 Deep Dive

Tóm tắt

• Reservoir sampling giải bài toán uniform random sample từ stream độ dài chưa biết, O(k) bộ nhớ.
• Algorithm R: giữ k phần tử đầu; với phần tử ở chỉ số i (0-based, i >= k — khớp pseudocode mục 2), nhận vào reservoir với xác suất k/(i+1) bằng cách sinh j = randomInt(0, i) và thay slot j nếu j < k. (Phần chứng minh dùng quy ước 1-based nên ghi k/n cho phần tử cuối.)
• Chứng minh bằng quy nạp: sau n phần tử, mọi phần tử có xác suất đúng k/n — không bias theo vị trí.
• Weighted variant: key u^(1/w), giữ k phần tử key lớn nhất — phần tử trọng số cao hơn có xác suất chọn cao hơn tỉ lệ.
• Ứng dụng: log sampling, A/B routing, database cursor sample, distributed sampling merge.
• Pitfall chính: dùng xác suất cố định k/n (không biết n trước), chọn slot thay thế không đều, bỏ sót stream ngắn hơn k.

Tự kiểm tra

Bài tiếp theo: HyperLogLog — đếm distinct xấp xỉ