- Reservoir sampling एक sampling तकनीक है जो कुल आकार अज्ञात data stream में भी केवल तय संख्या के items को memory में रखकर हर item को चुने जाने का समान मौका देती है
- आकार ज्ञात array के लिए shuffle करना या random index selection काफ़ी है, लेकिन ऐसे stream में जहाँ एक बार आगे निकल जाने के बाद पुराने item पर वापस नहीं जा सकते, वहाँ अलग approach चाहिए
- एक item चुनने के मामले में nवें item को 1/n probability से अपनाया जाता है, ताकि नए item के चुने जाने की संभावना और मौजूदा item के बचे रहने की संभावना संतुलित रहे
- कई items चुनते समय रखे जाने वाले items की संख्या k के अनुसार नए item को k/n probability से अपनाया जाता है, और ज़रूरत पड़ने पर अभी रखे गए items में से किसी एक को random तरीके से replace किया जाता है
- log collection में इसे लागू करने पर processing cap जैसे प्रति सेकंड अधिकतम 5 items की सीमा पार किए बिना, शांत अवधि में log loss और memory usage दोनों घटाए जा सकते हैं
आकार ज्ञात set में sampling
- अगर 10 कार्डों में से 3 कार्ड random तरीके से चुनने हों, तो पूरे deck को shuffle करके शुरुआती 3 कार्ड चुनना ही हर कार्ड को समान probability देने के लिए पर्याप्त है
- अगर कार्ड 10 लाख हो जाएँ, तो सीधे shuffle करना मुश्किल होगा, लेकिन array जैसी ऐसी structure में जहाँ index से access संभव हो, random index 3 चुनकर वही उद्देश्य हासिल किया जा सकता है
- memory में मौजूद array में किसी खास index तक पहुँचना आसान है, लेकिन कार्डों के ढेर में 436,234वाँ कार्ड गिनना व्यावहारिक रूप से बहुत समय लेगा
आकार अज्ञात stream में आने वाली सीमाएँ
- अगर आप एक बार में केवल 1 कार्ड देख सकते हों, एक समय में केवल 1 कार्ड ही पकड़ सकते हों, और गुज़र चुके कार्ड पर वापस नहीं जा सकते हों, तो कुल संख्या जाने बिना अंत में 1 कार्ड चुनना होगा
- log collection service में भी इसी तरह की समस्या आती है
- यह दूसरी services से log messages लेकर उन्हें एक जगह store करती है
- खराब release या traffic spike की वजह से logs अचानक बढ़ जाएँ, तो collection service पर ज़्यादा load पड़ सकता है
- उदाहरण वाली log collection service के पास प्रति सेकंड 5 logs process करने की threshold है
- केवल 10% logs भेजने का तरीका spike के दौरान threshold पार होने से बचाता है, लेकिन शांत अवधि में भी बेवजह 90% logs फेंक देता है
- वांछित behavior यह है कि शांत अवधि में सभी logs भेजे जाएँ, और spike के दौरान प्रति सेकंड अधिकतम 5 logs ही भेजे जाएँ
- अगर हर सेकंड दिखने वाले पहले 5 logs ही भेज दिए जाएँ, तो बाद में आने वाले logs को चुने जाने का मौका नहीं मिलेगा, इसलिए यह निष्पक्ष नहीं है
एक item के लिए reservoir sampling
- Reservoir sampling कुल संख्या जाने बिना भी अब तक देखे गए items में से निष्पक्ष sample बनाए रखता है
- सभी messages को memory में store करके बाद में चुनना भी संभव है, लेकिन spike का आकार पता न हो तो ज़रूरी memory का अनुमान लगाना मुश्किल होता है
- यह तरीका मांगे गए sample count से ज़्यादा memory इस्तेमाल किए बिना वही समस्या हल करता है
- एक कार्ड चुनने का नियम सरल है
- पहला कार्ड हमेशा रखा जाता है
- nवाँ नया कार्ड 1/n probability से रखा जाता है
- अगर नया कार्ड रखने का निर्णय हो, तो पहले रखा कार्ड हटा दिया जाता है
- अगर हर कार्ड पर 50% probability से replace करें, तो बाद के कार्डों को फ़ायदा मिलेगा और तरीका निष्पक्ष नहीं रहेगा
- पहला कार्ड 10वें कार्ड के बाद भी बचा रहे, इसके लिए उसे replace होने के कई मौकों से बचना होगा
- आख़िरी कार्ड को केवल एक बार चुना जाना हो, तो वह हाथ में रह सकता है
- 1/n नियम केवल नए कार्ड के चुने जाने की probability ही नहीं, बल्कि पुराने कार्ड के बचे रहने की probability भी संतुलित करता है
- पहला कार्ड 1/1 यानी 100% probability से रखा जाता है
- दूसरे कार्ड पर नया कार्ड 1/2 probability से चुना जाता है, और पहला कार्ड भी 1/2 probability से बचा रहता है
- तीसरे कार्ड पर नया कार्ड 1/3 probability से चुना जाता है, और पहले से रखा कार्ड भी 50% × 2/3 के हिसाब से 1/3 probability पर आ जाता है
- सामान्य रूप से nवें चरण पर पुराने कार्ड के बने रहने की probability
1/(n-1) * (1-(1/n))होती है, और नए कार्ड के चुने जाने की probability1/nहोती है, इसलिए दोनों बराबर हो जाती हैं
कई items चुनने तक विस्तार
- एक item चुनने की प्रक्रिया को कई items चुनने तक बढ़ाया जा सकता है
- k items चुनने के लिए दो नियम बदलते हैं
- नया item
1/nनहीं बल्कि k/n probability से चुना जाता है - अगर replacement की ज़रूरत हो, तो अभी रखे गए k items में से किसी एक को random तरीके से चुनकर नए item से बदल दिया जाता है
- नया item
- मौजूदा item के चुने जाने की probability
k/(n-1)के रूप में व्यक्त की जा सकती है, और उसके नए item से replace न होने की probability को गुणा करने पर निष्पक्षता बनी रहती है - क्योंकि रखे गए सभी items के replace होने की probability समान होती है, हर चरण पर हर item के बने रहने की संभावना भी समान रहती है
- implementation को size k की array से व्यवस्थित किया जा सकता है
- हर नए item पर 0 से n के बीच एक random number generate किया जाता है
- अगर random number k से छोटा हो, तो उस index के item को नए item से replace किया जाता है
- वरना नए item को discard कर दिया जाता है
log collection service में लागू करना
- log collection के उदाहरण में
k=5सेट किया जाता है, ताकि एक समय में अधिकतम 5 log messages ही रखे जाएँ - हर सेकंड चुने गए logs को log collection service में भेजा जाता है, फिर size 5 वाली array खाली करके प्रक्रिया दोबारा शुरू की जाती है
- यह तरीका real-time log stream की जगह तय अंतराल पर logs के bundles भेजने वाला chunked pattern बनाता है
- इसके बदले भेजे गए logs की संख्या threshold से ऊपर नहीं जाती, और शांत अवधि में कुल logs और भेजे गए logs लगभग साथ-साथ चलते हैं
- शांत अवधि में logs नहीं खोते, spike के दौरान प्रति सेकंड threshold से ज़्यादा logs नहीं भेजे जाते, और storage भी
k=5logs से ज़्यादा नहीं होता
जब weight की ज़रूरत हो
- कुछ logs दूसरे logs की तुलना में अधिक मूल्यवान हो सकते हैं
- उदाहरण के लिए, आप सभी error logs को रखना चाह सकते हैं
- ऐसे मामलों में weighted reservoir sampling का variant इस्तेमाल किया जा सकता है
- Reservoir sampling एक ऐसा algorithm है जो शुरुआत में असंभव लगने वाली stream sampling समस्या को कम memory में हल करने में मदद करता है
1 टिप्पणियां
Hacker News की टिप्पणियाँ
बचपन में मैं गांव में रहता था, और सुना था कि मेरे पिता के एक दोस्त को अपने काम के तहत हर साल पहाड़ों में rock ptarmigan की आबादी गिननी पड़ती थी
वे एक तय रास्ते पर चलते, नियमित अंतराल पर पक्षियों को चौंकाकर उड़ाते और उनकी संख्या गिनते, फिर कुल संख्या सरकारी दफ्तर में जमा करते, जिसका इस्तेमाल पूरी आबादी का अनुमान लगाने में होता था
एक साल सर्वे के समय उन्हें विदेश जाना पड़ा, तो उन्होंने एक दोस्त को तरीका विस्तार से समझाकर अपने बदले करने को कहा, लेकिन वह दोस्त उस दिन भूल गया और काम झंझट भरा भी लगा, इसलिए उसने बस कोई plausible संख्या जमा कर दी
अगले साल स्थानीय अखबार के पहले पन्ने पर rock ptarmigan की आबादी में रिकॉर्ड बढ़ोतरी शीर्षक छपा; उस दोस्त ने यह नहीं सोचा था कि वही अनुमान शिकार की अनुमति की मात्रा तय करने में इस्तेमाल होता है
https://en.wikipedia.org/wiki/Rock_ptarmigan
पहले मैंने कुछ काफी बड़े ski resorts के लिए reservation system बनाए थे, और schedule लेट होने की वजह से रात भर काम करते हुए आखिरी चीज़ों में से एक सरकारी official statistics report थी, जैसे ठहरने वाले मेहमानों की संख्या
बस इतना कहूंगा कि उस साल के आंकड़ों का वास्तविकता से लगभग कोई संबंध नहीं था
मैं इस लेख का लेखक हूं। अगर सवाल हों तो जवाब दे सकता हूं, और feedback भी स्वागत है
सभी लेखों का code https://github.com/samwho/visualisations पर है और MIT license के तहत है, इसलिए बेझिझक इस्तेमाल कर सकते हैं
reservoir sampling का एक और दिलचस्प विस्तार यह है कि हर item के लिए random number निकालकर replacement करना है या नहीं और किसे replace करना है यह तय करने के बजाय, geometric distribution से value निकालकर यह तय किया जा सकता है कि अगले replacement से पहले कितने items सुरक्षित रूप से skip किए जा सकते हैं
यह खासकर तब उपयोगी है जब बहुत सारे items को सस्ते में skip किया जा सकता हो, जैसे tape drive को fast-forward कर सकते हों लेकिन कुल लंबाई नहीं जानते हों, या skip करते समय system के बड़े हिस्से को power-saving state में रखा जा सकता हो
n में से k चुनते समय यह तरीका लगभग O(k * log (n/k)) बार sampling और skipping करता है
conceptually, मुझे reservoir sampling का वह version ज्यादा पसंद है जिसमें हर card आने पर उसे एक fixed random priority दी जाती है और केवल priority वाले top k cards रखे जाते हैं
यहां से अगली समस्या है: अज्ञात लंबाई वाली stream में top k items को O(n) time और O(k) space में चुनना। सरल तरीके से min heap बनाए रखने पर O(k) space तो मिलता है, लेकिन O(n log k) time लगता है
इसके बजाय अधिकतम 2k capacity वाला unordered buffer रखें और items जोड़ते रहें; जब वह भर जाए तो randomized quickselect या median-of-medians से O(k) में केवल top k बचा लें। कुल n items के लिए हर k items पर O(2k) काम होगा, इसलिए O(n) running time मिलता है
संबंधित विषय के रूप में rendezvous hashing भी है: https://en.wikipedia.org/wiki/Rendezvous_hashing
एक side note के तौर पर, discrete probability distribution से sampling करने की alias method पर एक अच्छा लेख भी है: https://www.keithschwarz.com/darts-dice-coins/
हालांकि शुरुआत में बात 10 या 436,234 cards की deck से 3 cards random चुनने की थी, फिर अचानक बात सिर्फ 1 card चुनने पर बदल गई, जिससे थोड़ी देर के लिए confusion हुआ
“अब से हम 3 cards नहीं बल्कि सिर्फ 1 card हाथ में रखते हैं, और deck size भी नहीं जानते—ऐसे simplified assumption पर जा रहे हैं” जैसा कोई section title “Now let me throw you a curveball...” से पहले हो तो ज्यादा स्पष्ट लगेगा
हालांकि मुझे नहीं पता कि मैंने इस approach की statistical validity ठीक से समझी है या नहीं। यह समझ आता है कि किसी खास अवधि के सभी logs के शामिल होने की probability समान है, लेकिन क्या इसका मतलब यह नहीं कि “धीमे समय” में बने logs overall metrics में overrepresented होंगे?
उदाहरण के लिए अगर आप पूरे fleet की total cost (CPU-seconds आदि) घटाने के लिए जानना चाहते हैं कि कौन सा endpoint सबसे ज्यादा time लेता है, तो bursty traffic पाने वाला endpoint steady traffic पाने वाले endpoint की तुलना में underrepresented हो सकता है, इसलिए यह तरीका अनुपयुक्त लगता है
तब आप असल में ज्यादा traffic न पाने वाले endpoint को optimize करने में समय बर्बाद कर सकते हैं
service-wise capacity planning में भी, क्या bursty traffic पाने वाली service का underrepresented होना सही है—यह जानना चाहूंगा
मैं जानना चाहता हूं कि reservoir sampling किन use cases के लिए उपयुक्त है, और लौटाए गए data से किस तरह की statistical analysis की जा सकती है
लेख और व्याख्या शानदार हैं
व्यावहारिक नज़रिए से देखें तो फिर भी log collection में मैं इस तरीके को शायद सबसे आख़िर में इस्तेमाल करूँगा। समझता हूँ कि spike आने पर कुछ न कुछ छोड़ना ही पड़ेगा, लेकिन असली बात यह है कि क्या छोड़ा जाए
क्या छोड़ना है, यह “निष्पक्ष” तरीके से तय करने में मुझे बहुत बड़ा अर्थ नहीं दिखता
कम priority वाले logs पहले छोड़ना बेहतर है, और अगर debug/info/warning/error जैसे log levels हैं, तो ज़्यादा गंभीर events को priority दी जा सकती है और बहुत verbose debug logs पहले छोड़े जा सकते हैं
एक और तरीका यह है कि log sequences को किसी activity के हिस्से के रूप में group किया जाए: सफल activities के लिए सिर्फ़ start और end, या मुख्य state changes ही record किए जाएँ और दोहराए जाने वाले बीच के logs हटाए जाएँ
spike के समय हर log line store करने के बजाय मिलते-जुलते या duplicate messages को aggregate/summary कर दिया जाए, तो volume भी घटता है और trends भी बेहतर दिखते हैं
और collect होने वाली कुल log lines को भी एक बड़े budget के अंदर limit करना चाहते हैं। reservoir sampling इन सब चीज़ों को handle कर सकती है
निष्पक्ष reservoir sampling को भी controlled तरीके से unfair बनाया जा सकता है। उदाहरण के लिए, जिन items का content ख़ास तौर पर interesting है, उनके रखे जाने की probability बढ़ाई जा सकती है
आख़िरी उपाय के तौर पर यह कम सिद्धांतवादी biased random selection, या ऐसे selection algorithms से compete करने वाली technique है जो random भी नहीं हैं
सच में बहुत अच्छी तरह लिखा और visualize किया गया लेख है
advanced extension के तौर पर ऐसे algorithms हैं जो हर record पर trial चलाने के बजाय कितने records skip करने हैं यह calculate करते हैं। इस पर एक अच्छा लेख यहाँ है: https://richardstartin.github.io/posts/reservoir-sampling
weighted reservoir sampling का variant ReSTIR (real-time ray tracing के लिए spatiotemporal reservoir resampling) में इस्तेमाल होता है। यह built-in spatiotemporal denoising वाला probabilistic light transport estimator है
light transport estimator scene से होकर गुजरने वाली light की मात्रा calculate करने की कोशिश करता है(https://en.wikipedia.org/wiki/Radiance). इसके लिए energy conservation बनाए रखते हुए उन सभी paths की radiance integrate करनी पड़ती है जिनसे light जा सकती है(https://en.wikipedia.org/wiki/Rendering_equation)
बेहद सरल मामलों को छोड़ दें तो rendering equation के इस integral का कोई आसान closed-form solution नहीं होता, इसलिए इसे probabilistically solve करना पड़ता है
मूल idea Monte Carlo method(https://en.wikipedia.org/wiki/Monte_Carlo_method) है, जिसमें possible paths को random तरीके से बहुत बार sample करके average लिया जाता है
इसके बाद कई दशकों में ज़्यादा refined strategies विकसित हुईं, जैसे importance sampling (IS), multiple importance sampling (MIS), sample importance resampling (SIR), resampling importance sampling (RIS), weighted reservoir sampling (WRS), और RIS व WRS को combine करने वाला ReSTIR
विस्तार से पढ़ने के लिए लेख यहाँ है: https://agraphicsguynotes.com/posts/understanding_the_math_b...
इसे देखकर लगा कि Allies ने serial numbers से German tanks की संख्या estimate करने के लिए जो algorithm इस्तेमाल किया था, उसके बारे में और सोचना चाहिए
field estimate असली production का लगभग 5 गुना था, लेकिन serial number वाली technique 90% से ज़्यादा accurate थी
अच्छा लेख है और explanation भी शानदार है। यह Vitter द्वारा शायद सबसे पहले explain किए गए Algorithm R को cover करता दिखता है: https://www.cs.umd.edu/~samir/498/vitter.pdf
Vitter का पुराना paper https://dl.acm.org/doi/10.1145/358105.893 Knuth की TAOCP volume 2 को cite करता है, और Knuth में फिर कोई citation नहीं है
data science के नज़रिए से data की मात्रा खुद भी बहुत महत्वपूर्ण information रखती है, इसलिए हर data point कितनों को represent करता है, यह भी log में रखना अच्छा रहेगा
उदाहरण के लिए, अगर sampling ratio 10% है, तो 10 रखने वाला field हो, जिससे count, sum, average जैसे ज़्यादातर statistics को फिर से reconstruct और estimate किया जा सकता है
संरचना अच्छी है और समझाया भी अच्छी तरह गया है। अगर weighted version में दिलचस्पी हो, तो मैंने यहाँ थोड़ा समझाया था: https://gregable.com/2007/10/reservoir-sampling.html
MapReduce से आसानी से बनाया जा सकने वाला distributed version भी है
एक बहुत सरल algorithm यह भी हो सकता है कि stream के हर item के लिए एक random pair बनाया जाए और उस random value के आधार पर top N को रखा जाए
पहला,
POW(RANDOM(), 1.0 / weight)से rank देकर top N चुनने वाला intuitive implementation, weight बहुत बड़ा या छोटा होने पर numerical stability की समस्या रखता हैदूसरा, result sample expected value के लिहाज़ से भी मूल population जैसी distribution नहीं रखता। total weight जितना अधिक population के कुछ ही elements में केंद्रित होता है, यह बात उतनी ही खास तौर पर दिखती है, लेकिन कई मामलों में यह usable approximation है
इन समस्याओं पर यहाँ और चर्चा की गई है: https://blog.moertel.com/posts/2024-08-23-sampling-with-sql....
बेहतरीन लेख है, approachable है और visualizations भी शानदार हैं
$WORK में हम इससे मिलते-जुलते variant का इस्तेमाल करके running stream में किसी percentile का अनुमान लगाने वाली related problem हल कर रहे हैं
जिस percentile को चुनना है वह कभी-कभी बदलता है, लेकिन आम तौर पर 1 trillion से ज़्यादा iterations तक fixed रहता है, और underlying data quasi-stationary होने की constraint है
इस process को splay tree से support करने पर amortized O(1) percentile estimation संभव है। समान RAM usage पर error range कई दूसरी techniques से बड़ी है, लेकिन यह बहुत तेज़ है
replacement probability को adjust करके time या count आधारित “data half-life” रखी जा सकती है और estimation को हाल की events की तरफ bias किया जा सकता है; कुछ problems के लिए यह ज्यादा उपयुक्त होता है