- Reservoir Sampling là một kỹ thuật độc đáo và hiệu quả để chọn mẫu ngẫu nhiên một cách công bằng khi không biết kích thước của dữ liệu
- Kỹ thuật này được ứng dụng trong nhiều lĩnh vực như thu thập log thời gian thực vì có thể giải quyết hiệu quả các tình huống mà phương pháp truyền thống không hỗ trợ
- Ý tưởng cốt lõi là mỗi khi một phần tử mới xuất hiện, cập nhật vùng lưu trữ với xác suất 1/n, từ đó mang lại cho mọi phần tử cơ hội được chọn như nhau
- Khi cần chọn nhiều mẫu, xác suất được mở rộng thành k/n và theo xác suất đó sẽ thay thế ngẫu nhiên một mẫu hiện có
- Thuật toán này đảm bảo lấy mẫu công bằng với mức sử dụng bộ nhớ thấp, đồng thời nâng cao hiệu quả và độ tin cậy của xử lý thời gian thực
Khái niệm và sự cần thiết của Reservoir Sampling
- Reservoir Sampling là một kỹ thuật hiệu quả để trích xuất mẫu một cách công bằng từ một tập dữ liệu có tổng kích thước không biết trước
- Trong trường hợp thông thường, khi biết kích thước dữ liệu, việc chọn chỉ số ngẫu nhiên là một cách hiệu quả, nhưng khi không biết kích thước thì phương pháp này không thể áp dụng
- Với lượng dữ liệu lớn đến theo dòng tuyến tính (ví dụ: luồng log), cần phải giới hạn mức sử dụng bộ nhớ, đồng thời vẫn phải đảm bảo mỗi dữ liệu có cùng xác suất được chọn
Lấy mẫu khi biết kích thước
- Với một tập hợp có kích thước cố định (ví dụ: 10 lá bài), cách xáo trộn toàn bộ rồi chọn số lượng mong muốn từ đầu là phương pháp phù hợp để đảm bảo tính công bằng
- Nếu tận dụng cấu trúc mảng trong máy tính, có thể trực tiếp chọn chỉ số ngẫu nhiên để trích xuất mẫu một cách nhanh chóng
- Tuy nhiên, với hàng triệu phần tử dữ liệu hoặc một luồng dữ liệu có kích thước không biết trước trong thực tế, cách này trở nên kém hiệu quả
Lấy mẫu khi không biết kích thước: vấn đề và nhu cầu
- Trong thực tế thường xuyên có những tình huống dữ liệu đến tuần tự từng phần tử, chỉ có thể lưu đúng 1 phần tử, và không thể quay lại dữ liệu đã đi qua
- Trong các hệ thống thu thập log, lưu lượng có thể tăng đột biến, vì vậy có những lúc phải chỉ lấy mẫu một phần để gửi đi nhằm tránh quá tải máy chủ
- Cách chọn ngẫu nhiên vài phần tử đầu tiên không mang lại cơ hội như nhau cho mọi phần tử, nên gây ra vấn đề thiếu tính công bằng
Nguyên lý của thuật toán Reservoir Sampling
- Mỗi khi có dữ liệu đi vào, ta tính số lượng n đã nhận đến thời điểm đó và để dữ liệu mới được chọn với xác suất 1/n
- Phần tử đầu tiên luôn được chọn, sau đó mỗi phần tử mới sẽ thay thế dữ liệu hiện có với xác suất ngày càng thấp hơn, nhờ đó duy trì xác suất được chọn như nhau
- Đến cuối cùng, bất kỳ phần tử nào trong toàn bộ tập dữ liệu được lưu lại cũng sẽ có xác suất ngang nhau
- Đây không phải là tung đồng xu mà là sử dụng xác suất 1/n để đảm bảo mọi dữ liệu đều có cơ hội công bằng
Trực giác toán học (giải thích bằng ví dụ lá bài)
- Dữ liệu thứ 1: luôn được chọn (xác suất là 1/1)
- Dữ liệu thứ 2: được chọn với xác suất 1/2, dữ liệu cũ chỉ còn xác suất 50% được giữ lại
- Dữ liệu thứ 3: dữ liệu mới được chọn với xác suất 1/3, còn dữ liệu cũ tích lũy xác suất sống sót theo phần bù của xác suất đó
- Tổng quát hóa ra, khi xét đến dữ liệu thứ n, mọi phần tử luôn có xác suất 1/n
Mở rộng để chọn nhiều mẫu (k-out-of-n)
- Để chọn k mẫu, dữ liệu mới được chọn với xác suất k/n, và nếu được chọn thì sẽ thay thế ngẫu nhiên một phần tử đang được lưu
- Cách này cũng giúp mọi phần tử được lưu đều có cùng xác suất còn lại trong mẫu
- Chỉ dùng bộ nhớ cố định (k phần tử) nhưng vẫn có thể lấy nhiều mẫu một cách công bằng từ các luồng dữ liệu lớn
Ứng dụng Reservoir Sampling trong dịch vụ thu thập log
- Trong số các log đổ vào mỗi giây, chỉ chọn tối đa k log (ví dụ: 5 log) bằng kỹ thuật Reservoir Sampling, rồi chỉ gửi các mẫu đó về máy chủ
- Khi dữ liệu ít, mọi log đều được gửi nên không bị mất mát; khi lưu lượng tăng vọt, hệ thống cũng không gửi quá k mẫu nên có thể đảm bảo tính ổn định của dịch vụ
- Việc gửi mẫu theo chu kỳ nhất định có thể tạo ra một chút độ trễ về thời gian thực, nhưng nhìn chung giúp cải thiện độ ổn định và hiệu quả chi phí
Ứng dụng bổ sung và tài liệu tham khảo
- Nếu một số dữ liệu (ví dụ: log lỗi) quan trọng hơn, có thể dùng biến thể Weighted Reservoir Sampling với trọng số được áp dụng
- Các khái niệm nâng cao có thể xem trong Wikipedia và các tài liệu bên ngoài, nhưng nguyên lý cơ bản vẫn là duy trì tính công bằng
Kết luận
- Reservoir Sampling là một thuật toán rất thanh lịch và thực tiễn, cho phép lấy mẫu công bằng và hiệu quả bộ nhớ từ luồng dữ liệu có kích thước không biết trước
- Trong xử lý dữ liệu thời gian thực, nhờ các ưu điểm về tốc độ, tính nhất quán và mức sử dụng tài nguyên thấp, nó có giá trị ứng dụng cao trong nhiều lĩnh vực
1 bình luận
Ý kiến Hacker News
Hồi còn nhỏ sống ở vùng quê, một người bạn của cha tôi có công việc mỗi năm phải đo số lượng cá thể ptarmigan (gà gô tuyết) trong núi
Cách làm là đi theo một tuyến đã định, cứ mỗi khoảng thời gian lại làm chim giật mình bay lên rồi đếm số lượng
Sau đó nộp con số đó cho văn phòng phụ trách, và văn phòng sẽ ước tính tổng quần thể
Có năm người bạn đó ở nước ngoài nên đã giải thích kỹ cách làm cho một người bạn khác và nhờ làm thay
Nhưng đến đúng ngày khảo sát thì người kia lại quên mất, thấy phiền nên gửi đại một con số trông có vẻ hợp lý
Năm sau, trang nhất báo địa phương chạy tiêu đề “Số lượng ptarmigan tăng kỷ lục”
Lý do sự thay đổi đột ngột này thành tin tức là vì con số đó được dùng làm căn cứ quyết định giấy phép săn bắn. Người bạn kia đã không nghĩ đến chuyện đó
Trước đây khi làm hệ thống đặt chỗ cho một khu nghỉ dưỡng trượt tuyết lớn, tôi từng phải hoàn thành báo cáo thống kê chính thức để nộp cho chính phủ, như số ngày lưu trú của khách
Vì thiếu thời gian và phải làm xuyên đêm, dữ liệu thống kê của năm đó khác khá nhiều so với giá trị thực
Xin chào! o/
Tôi là tác giả bài viết này. Rất hoan nghênh câu hỏi và phản hồi
Mã nguồn cho tất cả các bài viết đều được cung cấp theo giấy phép MIT tại https://github.com/samwho/visualisations, cứ tự nhiên sử dụng
Tôi nghĩ đây là một bài viết rất hay
Theo một hướng tối ưu khác cho reservoir sampling, thay vì rút số ngẫu nhiên cho từng phần tử để kiểm tra có thay thế hay không, có thể rút số bước nhảy từ phân phối Geometric
Điều này thú vị trong các trường hợp như tape drive, nơi có thể bỏ qua nhiều phần tử với chi phí thấp (dù không biết trước độ dài băng, nhưng trong lúc bỏ qua thì phần lớn hệ thống có thể ở trạng thái ngủ)
Để lấy mẫu k phần tử từ n phần tử, chỉ cần khoảng O(k * log(n/k)) lần lấy mẫu và bỏ qua
Một ý tưởng khác tôi thích là gán một mức ưu tiên ngẫu nhiên cho mỗi lá bài khi nó tới và giữ lại top k
Từ đó có một bài toán liên quan là: làm sao chọn chỉ top k phần tử từ một luồng không biết độ dài trong O(n) thời gian và O(k) bộ nhớ.
Chỉ cần nhét mọi thứ vào một bộ đệm chưa sắp xếp kích thước 2*k, và khi đầy thì dùng quickselect ngẫu nhiên hoặc median-of-medians để chỉ giữ lại top k
Làm như vậy n lần thì cần O(n) thời gian
Một kỹ thuật liên quan khác cũng thú vị là rendezvous hashing
Ngoài ra, alias method sẽ dễ hiểu hơn nếu xem bài này: https://www.keithschwarz.com/darts-dice-coins/
Tôi tự hỏi liệu có thể dùng cách này theo kiểu lồng nhau không
Ví dụ, nếu dịch vụ của tôi thực hiện reservoir sampling, còn dịch vụ thu thập log cũng thực hiện reservoir sampling, thì kết quả có tương đương với việc chỉ dùng reservoir sampling một lần ở dịch vụ thu thập log không
Tôi đặc biệt thích phần hoạt họa và giải thích
Nhất là các tương tác như trộn 100 lần trên đồ thị rất ấn tượng
Lúc đầu có chút bối rối vì bài đang nói về việc rút 3 lá từ 10 lá hoặc 436,234 lá, rồi đột nhiên chuyển sang ví dụ chỉ xem từng lá một và rút 1 lá
Ở đoạn “Bây giờ hãy ném một đường cong vào đây!” nếu có thêm một chỗ ngắt phần thì có lẽ sẽ dễ hiểu hơn.
Lúc này ta đang giả sử chỉ cầm 1 lá trên tay, và cũng không biết kích thước của bộ bài
Tôi đặc biệt thích thiết kế của trang web
Phần tương tác, nhân vật chú chó, phông chữ, màu sắc và bố cục tổng thể đều rất ổn
Cả blog giống như một kho báu vậy
Tôi rất vui vì đã tìm ra nó
Tôi thích phần đồ họa
Tuy vậy, tôi không chắc phương pháp này có hoàn toàn vững về mặt thống kê hay không. Mọi log trong cùng một khoảng thời gian đúng là có cùng xác suất được chọn, nhưng tôi lo rằng các log phát sinh trong những “giai đoạn chậm” có thể bị lấy mẫu quá mức trong thống kê tổng thể
Ví dụ, nếu muốn tìm endpoint nào trong toàn hệ thống dùng CPU nhiều nhất để tối ưu hóa, thì log của các endpoint có traffic tăng đột biến tạm thời có thể bị đại diện thiếu, khiến ta đánh giá sai endpoint nào thực sự được dùng nhiều nhất phải không
Hoặc trong bài toán lập kế hoạch dung lượng theo từng dịch vụ, các dịch vụ có burst traffic cũng có vẻ sẽ bị đại diện thiếu
Tôi muốn biết reservoir sampling phù hợp nhất với những trường hợp nào, và có thể làm loại phân tích thống kê nào với phương pháp này
Bài viết rất hay, toán hay thống kê mà được dạy kiểu này thì sẽ học thú vị hơn nhiều
Tôi có cảm giác khá giống https://distill.pub/
Câu “Sometimes the hand of fate must be forced” thật ấn tượng
Tôi đặc biệt thích cách tương tác
Tôi nghĩ thiết kế trang và cách giảng giải thật sự rất đẹp. Xin cảm ơn
Không biết blog này có RSS feed không
Đây là một bài viết rất rõ ràng và minh họa tốt
Nếu mở rộng ở mức nâng cao hơn, còn có các thuật toán tính luôn số lượng phần tử cần bỏ qua mỗi lần, thay vì dùng cách cơ bản
Có thể xem giải thích chi tiết tại https://richardstartin.github.io/posts/reservoir-sampling
Bài viết và phần giải thích rất tốt
Với việc thu thập log thực tế, tôi khuyên nên thử nhiều cách khác trước rồi chỉ dùng tính công bằng (fairness) như biện pháp cuối cùng
Ví dụ có thể gán mức ưu tiên cho log và loại bỏ trước những log priority thấp hơn (verbosity cao hơn)
Với các log cùng đại diện cho một hoạt động về mặt ngữ nghĩa, có thể giảm bớt các log lặp ở giữa và chỉ giữ lại lúc bắt đầu, kết thúc và các thay đổi trạng thái quan trọng
Nếu gom các log tương tự/trùng lặp lại thành bản tóm tắt để lưu, vừa giảm dung lượng tổng thể vừa thuận lợi hơn cho việc nắm bắt xu hướng
Gần đây tôi đang tìm hiểu khá nhiều về observability, và cách được nhắc tới ở đây là kiểu pha trộn giữa head/tail sampling.
Có thể tham khảo giải thích tại https://docs.honeycomb.io/manage-data-volume/sample/
Bài viết cũng có đề cập tới phần này
Thực ra điều quan trọng là áp dụng khái niệm “ngân sách” để giới hạn, thay vì đơn giản vứt bỏ toàn bộ log low priority
Tổng số log nói chung cũng có thể bị khống chế bằng một ngân sách cấp cao hơn riêng biệt
Reservoir sampling cũng xử lý tốt các ràng buộc như vậy
Bài viết và phần giải thích rất hay
Trong bài báo của Vitter có mô tả “Algorithm R”, chính là một dạng reservoir sampling.
Có thể tham khảo https://www.cs.umd.edu/~samir/498/vitter.pdf
Bài báo trước đó của Vitter tại https://dl.acm.org/doi/10.1145/358105.893 có trích dẫn tập 2 của Knuth trong TAOCP, nhưng ngay cả Knuth cũng không nêu xuất xứ rõ ràng
Bài viết được tổng hợp rất tốt, và nếu bạn tò mò về weighted reservoir sampling thì https://gregable.com/2007/10/reservoir-sampling.html có giải thích
Ngoài ra còn có cách áp dụng rất dễ trong môi trường phân tán kiểu map-reduce, cũng như cách rất đơn giản là gán một giá trị ngẫu nhiên cho mỗi phần tử rồi giữ Top N
Cách cơ bản là lấy độ ưu tiên cho mỗi phần tử bằng POW(RANDOM(), 1.0 / weight) rồi chọn Top N, nhưng cách này có vấn đề mất ổn định số khi weight quá lớn hoặc quá nhỏ
Ngoài ra, mẫu kết quả cũng có thể không phản ánh đủ tốt phân bố của toàn bộ quần thể gốc. Điều này đặc biệt rõ khi tổng weight tập trung vào một số ít phần tử
Dù vậy, trong hầu hết tình huống nó vẫn là một phép gần đúng đủ tốt
Xem thêm chi tiết tại https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html
Đọc bài này làm tôi nhớ đến cách quân Đồng minh trong Thế chiến II từng ước tính sản lượng xe tăng Đức từ số sê-ri
Khi đó nhân sự ngoài thực địa ước tính cao hơn sản lượng thực tế khoảng 5 lần, trong khi phương pháp dùng số sê-ri đạt độ chính xác hơn 90%
Bài đăng rất xuất sắc, và phần trực quan hóa cũng thật sự nổi bật
Trong dịch vụ thực tế, chúng tôi dùng một biến thể tương tự để ước tính theo thời gian thực các giá trị percentile thay đổi trên những luồng dữ liệu rất lớn
Giá trị percentile đôi khi thay đổi, nhưng thường giữ nguyên qua rất nhiều lần lặp. Dữ liệu nền là quasi-stationary
Nếu dùng splay tree để hỗ trợ, thì so với các phương pháp khác, biên độ sai số theo dung lượng RAM sẽ rộng hơn nhưng vẫn có thể ước tính với Amortized O(1) thời gian
Cũng có thể điều chỉnh xác suất thay thế để giảm “half-life” của dữ liệu, tức là làm cho ước tính thiên về dữ liệu gần đây hơn
Từ góc nhìn khoa học dữ liệu, tôi nghĩ chính lượng dữ liệu cũng mang thông tin quan trọng, nên nhất định phải ghi lại cả tỷ lệ lấy mẫu
Ví dụ nếu tỷ lệ lấy mẫu là 10% thì có thể ghi giá trị 10 cho mỗi mẫu, từ đó khôi phục và ước tính chính xác tổng số đếm, tổng, trung bình, v.v.
Bài đăng này cho thấy rất rõ các đánh đổi trong việc thu thập telemetry (trace, log, metrics)
Đây là một lĩnh vực phân tích dữ liệu có rào cản gia nhập cao và thường bị nhiều nhà phát triển bỏ qua
Ngay cả với dữ liệu trông giống nhau, đồ thị quan sát được có thể hoàn toàn khác nhau tùy vào cách lấy mẫu, và nhiều người bỏ sót điểm này