- Reservoir Sampling एक अनोखी और कुशल तकनीक है, जिससे डेटा का आकार पता न होने पर भी निष्पक्ष random sample चुना जा सकता है
- यह real-time log collection सहित कई क्षेत्रों में उपयोगी है, क्योंकि यह उन स्थितियों को भी कुशलता से संभाल सकता है जहाँ पारंपरिक तरीके काम नहीं करते
- इसका मुख्य विचार यह है कि हर नया element आने पर 1/n probability से storage को अपडेट किया जाए, ताकि सभी elements को चुने जाने का समान मौका मिले
- कई samples चुनने की स्थिति में probability को k/n तक बढ़ाया जाता है, और उस probability के अनुसार मौजूदा sample को random तरीके से replace किया जाता है
- यह algorithm कम memory उपयोग के साथ भी निष्पक्ष sampling सुनिश्चित करता है और real-time processing की दक्षता व विश्वसनीयता बढ़ाता है
Reservoir Sampling की अवधारणा और आवश्यकता
- Reservoir Sampling एक कुशल तकनीक है जो कुल आकार अज्ञात data set से निष्पक्ष रूप से sample निकालती है
- सामान्य स्थिति में, जब data का आकार पता हो, तब random index चुनने का तरीका प्रभावी होता है, लेकिन आकार अज्ञात होने पर यह संभव नहीं होता
- क्रमवार आने वाले बड़े data (जैसे log stream) में memory usage सीमित रखना पड़ता है, और साथ ही हर data item के चुने जाने की probability समान होनी चाहिए
आकार ज्ञात होने पर sampling
- सीमित आकार वाले set (जैसे 10 cards) में सभी items को मिलाकर सामने से इच्छित संख्या चुनने वाला shuffle तरीका निष्पक्षता सुनिश्चित करने के लिए उपयुक्त है
- कंप्यूटर की array संरचना का उपयोग करके सीधे random index चुनकर तेज़ी से sample निकाले जा सकते हैं
- लेकिन वास्तविक दुनिया में लाखों data points या अज्ञात आकार वाले stream के लिए यह तरीका अक्षम होता है
आकार अज्ञात होने पर sampling: समस्या और आवश्यकता
- अक्सर ऐसी स्थिति आती है जहाँ data एक-एक करके क्रम में आता है, केवल 1 item ही store किया जा सकता है, और पहले से गुजर चुके data को वापस नहीं देखा जा सकता
- log collection systems में अचानक traffic spike हो सकता है, और server overload से बचने के लिए केवल कुछ data को sample करके भेजना पड़ सकता है
- मनमाने ढंग से शुरुआती कुछ items चुनना सभी items को समान अवसर नहीं देता, इसलिए निष्पक्षता की समस्या पैदा होती है
Reservoir Sampling algorithm का सिद्धांत
- हर data item आने पर अब तक आए items की संख्या n गिनी जाती है, और नए data को 1/n probability से चुना जाता है
- पहला data हमेशा चुना जाता है, और उसके बाद आने वाला हर नया data धीरे-धीरे कम probability के साथ पुराने data को replace करता है, जिससे समान selection probability बनी रहती है
- अंत तक store किया गया data पूरे set के किसी भी item का समान probability वाला प्रतिनिधि होता है
- यह coin toss नहीं, बल्कि 1/n probability का उपयोग करने वाला तरीका है, जिससे हर data item को निष्पक्ष अवसर मिलता है
गणितीय सहज समझ (cards उदाहरण)
- पहला data: हमेशा चुना जाता है (probability 1/1)
- दूसरा data: 1/2 probability से चुना जाता है, और पहला data केवल 50% संभावना से बना रहता है
- तीसरा data: नया data 1/3 probability से चुना जाता है, और पुराने data की survival probability उसके पूरक मान के अनुसार जुड़ती है
- सामान्य रूप से, nवें data तक पहुँचने पर हर data की probability हमेशा 1/n रहती है
कई samples चुनने का विस्तार (k-out-of-n)
- अगर k samples चुनने हों, तो नया data k/n probability से चुना जाता है, और चुने जाने पर वर्तमान में store किए गए items में से किसी एक को random तरीके से replace किया जाता है
- इस तरीके में भी store किए गए सभी items समान probability से sample में बने रहते हैं
- स्थिर memory (सिर्फ k जितनी) का उपयोग करते हुए बड़े data stream से भी निष्पक्ष रूप से कई samples निकाले जा सकते हैं
log collection service में Reservoir Sampling का उपयोग
- हर second आने वाले logs में से अधिकतम k items (जैसे 5) Reservoir Sampling से चुने जाते हैं, और केवल वही sample server को भेजे जाते हैं
- जब data कम हो, तो सभी logs भेजे जाते हैं और कोई loss नहीं होता; traffic बढ़ने पर भी k से अधिक नहीं भेजे जाते, इसलिए service stability बनाए रखी जा सकती है
- निश्चित interval पर samples भेजने से real-time में थोड़ा delay हो सकता है, लेकिन कुल मिलाकर यह stability और cost efficiency बेहतर बनाता है
अतिरिक्त उपयोग और संदर्भ सामग्री
- अगर कुछ data (जैसे error logs) अधिक महत्वपूर्ण हों, तो Weighted Reservoir Sampling जैसे रूपांतर का उपयोग किया जा सकता है
- गहन अवधारणाएँ Wikipedia जैसी बाहरी सामग्री में मिल सकती हैं, लेकिन इसका मूल सिद्धांत निष्पक्षता बनाए रखना है
निष्कर्ष
- Reservoir Sampling एक बहुत elegant और practical algorithm है, जो अज्ञात आकार वाले data stream में memory-efficient और निष्पक्ष sampling संभव बनाता है
- real-time data processing में तेज़ी, consistency और कम resource usage जैसी खूबियों के कारण इसकी उपयोगिता कई क्षेत्रों में बहुत अधिक है
1 टिप्पणियां
Hacker News टिप्पणियाँ
जब मैं छोटा था और गाँव में रहता था, तब मेरे पिता के एक दोस्त को हर साल पेशेवर तौर पर पहाड़ों में ptarmigan (grouse) की आबादी मापनी होती थी
तरीका यह था कि तय किए गए रास्ते पर चलते हुए निश्चित समय-अंतराल पर पक्षियों को उड़ाया जाए और उनकी संख्या गिनी जाए
फिर वह संख्या संबंधित दफ़्तर में जमा की जाती थी, और दफ़्तर उससे कुल आबादी का अनुमान लगाता था
एक साल वह दोस्त विदेश में था, इसलिए उसने दूसरे दोस्त को तरीका विस्तार से समझाकर यह काम सौंप दिया
लेकिन असली सर्वे वाले दिन वह दोस्त इसे पूरी तरह भूल गया, और झंझट से बचने के लिए उसने बस कोई ठीक-ठाक लगने वाला आँकड़ा बना कर जमा कर दिया
अगले साल स्थानीय अख़बार के पहले पन्ने पर शीर्षक छपा: “ptarmigan आबादी में रिकॉर्ड बढ़ोतरी”
यह तेज़ बदलाव खबर इसलिए बना, क्योंकि वही आँकड़े शिकार परमिट तय करने के आधार के रूप में इस्तेमाल होते थे। दोस्त ने इस बारे में सोचा ही नहीं था
पहले मैं एक बड़े ski resort reservation system पर काम कर रहा था, और मुझे आधिकारिक statistical report पूरी करनी थी (जैसे guest-stay days आदि, जो सरकार को जमा किए जाते हैं)
समय बहुत कम था और रात भर काम करना पड़ा, और उस साल के statistical data वास्तविक मानों से काफ़ी अलग थे
नमस्ते! o/
मैं इस लेख का लेखक हूँ। सवाल या feedback का स्वागत है
सभी पोस्ट का code https://github.com/samwho/visualisations पर MIT license के तहत उपलब्ध है। बेझिझक इस्तेमाल करें
मुझे यह बहुत अच्छा पोस्ट लगा
Reservoir sampling को optimize करने की एक दूसरी दिशा यह है कि हर item के लिए replacement होगा या नहीं, यह देखने के लिए random number खींचने के बजाय Geometric distribution से skip खींचे जाएँ
यह तब दिलचस्प होता है जब tape drive जैसी स्थिति हो, जहाँ कई items को सस्ते में skip किया जा सके (tape की कुल लंबाई पहले से पता नहीं होती, लेकिन skip करते समय सिस्टम के ज़्यादातर हिस्से को sleep state में रखा जा सकता है)
n में से sample k निकालने के लिए लगभग O(k * log(n/k)) sampling और skip ही चाहिए
एक और concept जो मुझे पसंद है, वह है हर card के आने पर उसे random priority देना और top k को बनाए रखना
इससे जुड़ी एक समस्या यह भी है कि अज्ञात लंबाई की stream से केवल top k items को O(n) time और O(k) space में कैसे चुना जाए।
सब कुछ 2*k size के unsorted buffer में डालो, और जब वह भर जाए तो randomized quickselect या median-of-medians का इस्तेमाल कर top k ही रखो
इस प्रक्रिया को n बार चलाने पर O(n) time लगता है
इससे जुड़ी एक और technique rendezvous hashing भी दिलचस्प है
और alias method के लिए https://www.keithschwarz.com/darts-dice-coins/ वाला लेख मददगार है
मैं जानना चाहता हूँ कि क्या इस तरीके को nested तरीके से इस्तेमाल किया जा सकता है
उदाहरण के लिए, अगर मेरी service में reservoir sampling हो रही है, और log collector service में भी reservoir sampling हो रही है, तो क्या यह सिर्फ log collector को एक बार इस्तेमाल करने के बराबर होगा?
मुझे animation और explanation खास तौर पर पसंद आए
खासकर graph में 100 बार shuffle करने जैसी अलग-अलग interactions प्रभावशाली लगीं
शुरुआत में 10 या 436,234 cards में से 3 cards चुनने की बात थी, फिर अचानक सिर्फ 1 card देखते हुए 1 card चुनने वाले उदाहरण पर चले जाने से थोड़ा भ्रम हुआ
“अब थोड़ा curveball फेंकते हैं!” वाले हिस्से में अगर एक section break होता तो समझना और आसान होता।
अब मान लेते हैं कि आपके हाथ में सिर्फ 1 card है, और deck का size भी नहीं पता
मुझे साइट का design खास तौर पर बहुत पसंद आया
interactions, dog character, font और color palette, और पूरा layout — सब बहुत अच्छा था
पूरा blog किसी treasure trove जैसा लगता है
इसे खोजकर बहुत खुशी हुई
graphics अच्छे लगे
लेकिन मुझे पूरा भरोसा नहीं है कि यह तरीका सांख्यिकीय रूप से पूरी तरह sound है। किसी एक अवधि के भीतर सभी logs के चुने जाने की probability बराबर है, लेकिन क्या ‘धीमे periods’ में बने logs कुल statistics में overrepresent नहीं हो जाते?
उदाहरण के लिए, अगर पूरे सिस्टम में यह पता लगाना हो कि कौन-सा endpoint CPU सबसे ज़्यादा इस्तेमाल कर रहा है ताकि उसे optimize किया जा सके, तो क्या ऐसे endpoint के logs, जिन पर traffic अचानक spike करता है, underrepresent नहीं हो जाएँगे, और इस वजह से वास्तव में ज़्यादा इस्तेमाल होने वाले endpoint का ठीक से आकलन नहीं हो पाएगा?
या service-by-service capacity planning में भी burst traffic वाली services underrepresent लगेंगी
Reservoir sampling किन उपयोगों के लिए सही बैठता है, और इस तरीके से किस तरह का statistical analysis किया जा सकता है — यह जानने की उत्सुकता है
बहुत अच्छा लेख है, math या statistics ऐसे सिखाई जाए तो सीखना मज़ेदार हो जाएगा
इससे मुझे https://distill.pub/ जैसी feel आई
“Sometimes the hand of fate must be forced” यह पंक्ति काफ़ी प्रभावशाली लगी
interaction का तरीका खास तौर पर पसंद आया
मुझे लगता है साइट का design और पढ़ाने का तरीका सचमुच सुंदर है। धन्यवाद
क्या blog के लिए RSS feed है?
यह बहुत स्पष्ट और अच्छी तरह illustrated पोस्ट है
एक और advanced extension के रूप में ऐसे algorithms भी हैं जो बुनियादी तरीके की जगह एक-एक करके जाँचने के बजाय कितने items skip करने हैं, यह गणना करते हैं
विस्तार के लिए https://richardstartin.github.io/posts/reservoir-sampling देखना उपयोगी होगा
अच्छा लेख और अच्छी explanation
वास्तविक log collection में मैं सुझाव दूँगा कि fairness को आख़िरी उपाय की तरह इस्तेमाल करने से पहले कई और तरीकों को आज़माया जाए
उदाहरण के लिए, logs को priority दो और कम priority वाले (ज़्यादा verbose) logs को पहले drop करो
अर्थ की दृष्टि से एक ही activity से जुड़े logs में बीच के repetitive logs कम कर दो, और सिर्फ start, end, और major state changes को रखो
मिलते-जुलते/duplicate logs को aggregate करके summary के रूप में सहेजने से कुल volume भी घटता है और trends समझना भी आसान होता है
हाल में मैं observability के बारे में बहुत पढ़ रहा हूँ, और जो तरीका बताया गया है वह head/tail sampling का hybrid है।
https://docs.honeycomb.io/manage-data-volume/sample/ पर इससे जुड़ी जानकारी मिल सकती है
लेख में इस हिस्से पर बात की गई है
दरअसल सभी low priority logs को drop कर देने से ज़्यादा महत्वपूर्ण यह है कि ‘budget’ का concept लगाकर उन्हें सीमित किया जाए
कुल log count को भी एक अलग upper budget से सीमित किया जा सकता है
Reservoir sampling ऐसे constraints को भी अच्छी तरह handle कर सकता है
अच्छा लेख और explanation
Vitter के paper में “Algorithm R” समझाया गया है, जो reservoir sampling का तरीका है।
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 भी कोई स्पष्ट स्रोत नहीं देता
यह बहुत अच्छी तरह व्यवस्थित है, और अगर weighted reservoir sampling में रुचि हो तो https://gregable.com/2007/10/reservoir-sampling.html में इसका विवरण है
distributed environment में map-reduce के साथ आसानी से लागू होने वाला तरीका भी है, और एक बहुत सरल तरीका यह है कि हर item के साथ एक random value जोड़ दी जाए और Top N बनाए रखा जाए
हर item के लिए POW(RANDOM(), 1.0 / weight) से priority निकालकर Top N चुनने वाला बुनियादी तरीका, weight बहुत बड़ा या बहुत छोटा होने पर numerical stability खो देता है
और यह भी संभव है कि resulting sample मूल population के distribution को पर्याप्त रूप से reflect न करे। खासकर जब कुल weight कुछ गिने-चुने items में concentrated हो
फिर भी ज़्यादातर परिस्थितियों में यह काफ़ी अच्छा approximation है
विस्तार से https://blog.moertel.com/posts/2024-08-23-sampling-with-sql.html में समझाया गया है
यह पढ़कर मुझे वह तरीका याद आया जिसमें मित्र राष्ट्रों ने दूसरे विश्व युद्ध के दौरान serial number के आधार पर जर्मन tank production का अनुमान लगाया था
उस समय मैदान में मौजूद लोगों ने वास्तविक उत्पादन से लगभग 5 गुना ज़्यादा अनुमान लगाया था, लेकिन serial-number method की accuracy 90% से अधिक थी
शानदार पोस्ट है, और visualisation सचमुच बेहतरीन है
production service में हम एक मिलता-जुलता variant इस्तेमाल करते हैं, जिससे बदलते हुए percentile values का बहुत बड़े stream पर real-time estimation किया जाता है
percentile values कभी-कभी बदलती हैं, लेकिन आम तौर पर बहुत लंबे repetitions तक स्थिर रहती हैं। underlying data quasi-stationary होता है
splay tree का backup लेने पर, दूसरे तरीकों की तुलना में RAM usage के अनुपात में error bounds ज़्यादा चौड़े होते हैं, लेकिन amortized O(1) time में estimation संभव है
replacement probability को adjust करके data की ‘half-life’ भी घटाई जा सकती है, यानी estimation को हाल के data की ओर bias किया जा सकता है
data science के नज़रिए से, data की मात्रा स्वयं महत्वपूर्ण जानकारी होती है, इसलिए sampling ratio को साथ में record करना ज़रूरी है
उदाहरण के लिए, अगर sampling rate 10% है, तो हर sample के साथ 10 record किया जाए, ताकि कुल count, sum, average आदि को ठीक-ठीक reconstruct और estimate किया जा सके
यह पोस्ट telemetry (traces, logs, metrics) collection के trade-offs को अच्छी तरह दिखाती है
इस तरह का data analysis क्षेत्र प्रवेश के लिहाज़ से कठिन है, और बहुत से developers इसे नज़रअंदाज़ कर देते हैं
एक जैसा दिखने वाला data भी किस तरीके से sample किया गया है, उसके अनुसार देखे जाने वाले graphs पूरी तरह बदल सकते हैं, और बहुत से लोग इस बात को नज़रअंदाज़ कर देते हैं