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

TL;DR: Bài toán: bạn cần lấy ra một nhúm nhỏ — ví dụ 1000 — phần tử ngẫu nhiên từ một dòng dữ liệu chảy mãi, nhưng không biết trước dòng đó dài bao nhiêu và không thể lưu cả dòng để bốc thăm. Mẹo của reservoir sampling: luôn giữ sẵn k "chỗ" trong tay; khi phần tử thứ i đi qua, cho nó một cơ hội nhỏ (giảm dần khi dòng dài ra) giành lấy một chỗ đang giữ — đổi chỗ thì ngẫu nhiên. Kết quả: dừng lúc nào cũng được, và mỗi phần tử đã thấy đều có cơ hội ngang nhau lọt vào nhúm cuối cùng — không thiên vị phần tử đến sớm hay đến muộn. Redis, Spark, log sampler đều dùng cách này. (Tên kỹ thuật của "k chỗ giữ trong tay" là reservoir.)

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ả. Lấy 1000 event đầu tiên? Sai — 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 mốc lấy mẫu. Bạn cần một mẫu mà mỗi event có cùng cơ hội được chọn, bất kể nó nằm chỗ nào trong dòng — gọi là mẫu đều xác suất (uniform random sample).

Reservoir sampling giải đúng bài này, chỉ tốn bộ nhớ đủ chứa k phần tử và không cần biết dòng dài bao nhiêu. Hay hơn: dừng lúc nào, nhúm đang giữ trong tay đã là một mẫu đều của tất cả những gì đã thấy tới lúc đó.

1. Trực giác — người gác cửa phát vé

Trước khi đụng công thức, hãy hình dung một cảnh quen. Bạn đứng ở cửa một sự kiện, dòng người đi qua liên tục, không ai biết tối nay sẽ có bao nhiêu người — có thể vài trăm, có thể vài nghìn. Nhiệm vụ: chọn ra ngẫu nhiên 1 người (hoặc k người) để tặng quà, sao cho ai đi qua cũng có cơ hội trúng ngang nhau. Bạn không thể bắt cả dòng người đứng lại xếp hàng để đếm rồi mới bốc thăm — dòng cứ chảy.

Mẹo của người gác cửa: luôn giữ một tấm vé trong tay. Người đầu tiên đi qua, bạn đưa vé cho họ. Người thứ i đi qua, bạn cho họ một cơ hội đúng bằng 1/i để giành lấy tấm vé đang giữ — nếu giành được, vé đổi sang tay người mới; nếu không, vé ở yên. Cơ hội này nhỏ dần khi dòng dài ra (người thứ 1000 chỉ có 1/1000 cơ hội). Điều kỳ diệu: dừng ở bất cứ ai, người đang cầm vé là một lựa chọn công bằng tuyệt đối — ai đi qua cũng từng có cơ hội đúng như nhau.

Reservoir sampling làm đúng trò này, chỉ khác là giữ k vé thay vì 1:

Điểm cốt lõi: cơ hội k/i nhỏ dần khi dòng dài ra, vừa khéo để cân bằng — người đến sớm có nhiều lần đối mặt rủi ro bị thay, người đến muộn ít lần hơn nhưng cơ hội vào ban đầu cao hơn; hai phía triệt tiêu nhau thành cơ hội cuối cùng bằng nhau cho tất cả. Phần "vì sao bằng nhau" có chứng minh gọn ở mục 3.

1.1 Phát biểu bài toán

Nói lại cho chặt:

• Đầu vào: một dòng phần tử x_1, x_2, ..., x_n chảy vào lần lượt; độ dài n chưa biết trước (có thể vô tận).
• Đầu ra: một nhúm k phần tử, sao cho mỗi phần tử trong dòng có cơ hội đúng bằng k/n nằm trong nhúm cuối.
• Ràng buộc: chỉ được giữ đủ chỗ cho k phần tử — không lưu cả dòng (bộ nhớ O(k)).

Nếu biết n trước, bài này dễ: trộn ngẫu nhiên cả dòng (Fisher-Yates shuffle) rồi lấy k phần tử đầu — nhưng cách đó cần giữ cả dòng trong bộ nhớ (O(n)). Reservoir sampling bỏ được ràng buộc "phải biết n" và "phải lưu cả dòng" mà vẫn giữ tính công bằng.

2. Algorithm R — Waterman (phổ biến qua 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)

Đọc thuật toán theo trực giác mục 1: hai dòng đầu phát đủ k vé cho k người đầu tiên. Từ người thứ k trở đi, ta tung một con số ngẫu nhiên j; nếu nó "rơi trúng" một trong k chỗ đang giữ (j < k) thì người mới giành được chỗ đó. Khi dòng càng dài, j rải trên càng nhiều giá trị nên cơ hội trúng càng nhỏ — đúng như cơ hội k/i giảm dần.

Lưu ý kỹ thuật: randomInt(0, i) sinh một số nguyên đều trong đoạn [0, i] — tổng i+1 giá trị khả dĩ. Vậy cơ hội phần tử thứ i (đánh số từ 0, với i >= k) lọt vào nhúm đúng bằng 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.

3. Vì sao mọi phần tử lại có cơ hội bằng nhau?

Mục 1 đã hứa: dừng lúc nào, ai cũng có cơ hội ngang nhau. Đây là phần chứng minh điều đó — phần duy nhất cần công thức. Nếu chỉ muốn dùng thuật toán, bạn có thể đọc lướt; nhưng với dòng dữ liệu khổng lồ (n hàng tỷ), thử nghiệm không thể kiểm hết mọi trường hợp, nên một chứng minh ngắn cho ta yên tâm thuật toán đúng với mọi n.

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ạy số thật cho k = 2, n = 5 thì phép màu k/n hiện nguyên hình là một tích triệt tiêu: mẫu số của thừa số này chính là tử số của thừa số kế. Phép triệt tiêu đó không phụ thuộc n — đó là lý do dừng dòng ở đâu cũng ra k/n, và cũng là cốt lõi của chứng minh quy nạp dưới đây.

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 coi mọi phần tử quan trọng như nhau. Nhưng thực tế thì không: một log giao dịch 100 đô đáng giữ lại để phân tích hơn một log click thông thường. Ta muốn phần tử quan trọng hơn dễ được chọn hơn, nhưng phần tử nhỏ vẫn còn cơ hội — chứ không phải cứ to là chắc chắn vào. Cách làm: gán cho mỗi phần tử một trọng số (weight — con số nói nó quan trọng đến đâu), rồi để trọng số đẩy cơ hội chọn lên theo tỉ lệ. Đây là weighted reservoir sampling (Efraimidis & Spirakis 2006).

Mẹo của họ: với mỗi phần tử, tính một "điểm xếp hạng" bằng công thức u^(1/w_i) — trong đó u là một số ngẫu nhiên đều trong khoảng (0, 1], còn w_i là trọng số của phần tử. Trọng số càng lớn thì điểm này có xu hướng càng cao. Cuối cùng chỉ giữ lại k phần tử có điểm cao nhất.

Để luôn biết phần tử nào trong nhúm đang có điểm thấp nhất (ứng viên sẽ bị loại đầu tiên), ta dùng min-heap — một cấu trúc dữ liệu giúp lấy ra phần tử nhỏ nhất tức thì mà không phải dò lại cả nhúm:

function weightedReservoirSample(stream, k):
    H <- MinHeap()                          -- min-heap theo điểm: gốc luôn là điểm nhỏ nhất đang giữ

    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; điểm xếp hạng của phần tử
        if H.size() < k:
            H.push((key_i, x_i))
        else if key_i > H.min():            -- điểm mới cao hơn điểm thấp nhất đang giữ?
            H.pop()                         -- loại phần tử điểm thấp nhất
            H.push((key_i, x_i))

    return H.elements()
// Time: thời gian tỉ lệ n nhân logarit của k.  Space: bộ nhớ đủ chứa k phần tử.

Kết quả: cơ hội một phần tử được giữ lại tỉ lệ với trọng số của nó — phần tử nặng gấp đôi thì cơ hội cũng cao hơn tương ứng. Phần chứng minh tỉ lệ này xem Efraimidis & Spirakis (2006).

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

Lấy mẫu log hệ thống: Nginx hay Envoy giữ một nhúm 10.000 request để phân tích độ trễ (latency — thời gian từ lúc nhận request đến lúc trả lời). Mỗi request đến, thuật toán quyết định giữ lại hay bỏ đi theo Algorithm R. Kết quả là một mẫu trải đều theo thời gian, không thiên về lúc dồn dập (burst) cũng không bỏ sót lúc vắng (idle).

Chia nhóm A/B test: Khi cần chọn ngẫu nhiên 5% người dùng vào nhóm B từ một dòng người dùng, reservoir sampling đảm bảo đúng 5% với cơ hội đều nhau, không phụ thuộc tổng số người dùng là bao nhiêu.

Lấy hàng ngẫu nhiên từ database: Câu lệnh SELECT * FROM logs ORDER BY RANDOM() LIMIT 1000 bắt cơ sở dữ liệu quét cả bảng rồi sắp xếp toàn bộ theo số ngẫu nhiên — thời gian tăng theo n nhân logarit của n, rất tốn khi bảng lớn. Đọc bảng tuần tự rồi áp reservoir sampling thay thế: chỉ quét một lần (thời gian tỉ lệ thẳng với n), bộ nhớ đủ chứa k hàng, không cần sắp xếp.

Gộp mẫu từ nhiều máy (distributed sampling): Mỗi máy giữ nhúm k phần tử của riêng nó. Để gộp nhiều nhúm thành một nhúm k phần tử chung mà vẫn công bằng, dùng weighted reservoir với trọng số tỉ lệ kích thước dòng dữ liệu của từng máy — nhờ vậy phần tử từ máy có dòng lớn không bị thiệt so với máy có dòng nhỏ.

6. Pitfall

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

-- SAI: nếu chưa biết n thì không thể tính k/n
-- Mà nếu biết n thì cách này vẫn sai: cơ hội mỗi phần tử lệch theo vị trí

-- ĐÚNG: randomInt(0, i) — i là chỉ số hiện tại, tăng dần theo dòng
-- Cơ hội k/(i+1) tự điều chỉnh theo vị trí phần tử trong dòng

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

-- SAI: luôn thay đúng chỗ vừa thêm gần nhất
reservoir[lastInserted] <- stream[i]    -- thiên vị: chỗ này bị thay nhiều nhất

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

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 tính điểm xếp hạng ngẫu nhiên u^(1/w) — ý tưởng giống hàm băm (hash): biến dữ liệu thành một con số ngẫu nhiên nhưng có quy luật. Hàm băm tốt cũng là nền của nhiều thuật toán dựa trên xác suất trong module này.
• Amortized analysis: tính bình quân, mỗi phần tử trong dòng chỉ tốn một lượng công việc cố định (gọi randomInt và có thể một lần đổi chỗ) — tổng thời gian tỉ lệ thẳng với n, dù phần tử đầu (điền nhúm) và phần tử sau (thử rồi thay) tốn công khác nhau.
• HyperLogLog: cùng nhóm thuật toán xử lý dòng dữ liệu dựa trên xác suất — reservoir giữ lại một mẫu đại diện thật (đúng k phần tử), còn HyperLogLog ước lượng số lượng phần tử khác nhau. Đọc cả hai để thấy đánh đổi: giữ mẫu thật so với ước lượng gần đúng.
• Count-Min Sketch: một cấu trúc dữ liệu dựa trên xác suất khác cho dòng dữ liệu — đếm xấp xỉ số lần xuất hiện thay vì lấy mẫu. Đọc thêm để thấy cả họ "cấu trúc dữ liệu cho dữ liệu lớn".
• Mini-challenge: Top-K: reservoir sampling là công cụ cho bài tìm k phần tử phổ biến nhất — lấy mẫu trước rồi tìm top-k trên mẫu, khi n quá lớn để tìm chính xác.

📚 Deep Dive

Tóm tắt

• Algorithm R: giữ k phần tử đầu; từ phần tử thứ k+1 trở đi, cơ hội k/(i+1) — O(k) bộ nhớ, dừng lúc nào cũng cho mẫu công bằng.
• Chứng minh quy nạp: sau n phần tử, mỗi phần tử có cơ hội đúng bằng k/n — không thiên vị theo vị trí.
• Bản có trọng số: điểm xếp hạng u^(1/w) + min-heap giữ k điểm cao nhất — phần tử nặng hơn có cơ hội được chọn cao hơn theo tỉ lệ.
• Ba lỗi hay gặp: dùng xác suất cố định k/n khi chưa biết n; chọn slot thay thế không đều; quên xử lý dòng ngắn hơn k.

Tự kiểm tra

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