1. प्रश्न
एक लॉगिंग सिस्टम प्रतिदिन अरबों यूज़र आइडेंटिफ़ायर प्राप्त करता है और उसे वास्तविक समय (real time) में दिन के लिए यूनिक यूज़र्स की संख्या का अनुमान लगाना होता है। मेमोरी बजट केवल कुछ KB है, और एक छोटी त्रुटि (error) स्वीकार्य है। एक स्ट्रीमिंग एल्गोरिदम डिज़ाइन करें और इसकी त्रुटि, शार्ड्स को मर्ज करने का तरीका, और यह सटीक डिडुप्लीकेशन (deduplication) को कहाँ प्रतिस्थापित नहीं कर सकता है, इसकी व्याख्या करें।
2. सीमाएं और स्पष्टीकरण
- इनपुट एक सतत आइडेंटिफ़ायर स्ट्रीम है; केवल एक पास (one pass) और फिक्स्ड मेमोरी का उपयोग करें।
- क्वेरी एक समय अंतराल (time window) में अनुमानित कार्डिनैलिटी (डिस्टिंक्ट काउंट) की मांग करती है।
- मान लें कि हैश समान रूप से वितरित (uniformly distributed) है और प्रत्येक शार्ड समान हैश एल्गोरिदम, रजिस्टर काउंट और एन्कोडिंग का उपयोग करता है।
- विलोपन (deletion) की आवश्यकता नहीं है; स्लाइडिंग विंडो, समय-समाप्ति (expiry), और स्ट्रॉन्गली कन्सिस्टेंट सटीक मानों के लिए अतिरिक्त संरचनाओं की आवश्यकता होती है।
3. मुख्य विचार
HyperLogLog (HLL) एक हैश को रजिस्टर इंडेक्स और शेष बिट्स में विभाजित करता है। m = 2^p रजिस्टरों के साथ, पहले p बिट्स एक रजिस्टर का चयन करते हैं; शेष बिट्स में, शुरुआती शून्यों की संख्या प्लस एक rho होती है। प्रत्येक रजिस्टर केवल अपने द्वारा देखे गए सबसे बड़े rho को संग्रहीत करता है।
इसके पीछे का अंतर्ज्ञान यह है कि किसी रजिस्टर में शुरुआती शून्यों की एक बहुत लंबी शृंखला इस बात का प्रमाण है कि सैंपल स्पेस में अधिक डिस्टिंक्ट तत्व सामने आए हैं। हार्मोनिक माध्य (harmonic mean) के साथ कार्डिनैलिटी का अनुमान लगाएं:
E = alpha_m * m^2 / sum(2^(-M[j]))
यहाँ M[j] रजिस्टर j है और alpha_m रजिस्टर काउंट पर आधारित एक सुधार स्थिरांक (correction constant) है। प्रोडक्शन इम्प्लीमेंटेशन्स छोटी कार्डिनैलिटी के लिए लीनियर-काउंटिंग सुधार और हैश-स्पेस सीमा के करीब लार्ज-रेंज सुधार का भी उपयोग करते हैं।
4. संदर्भ कार्यान्वयन
नीचे दिया गया छद्म-कोड अपडेट, अनुमान और मर्ज को दर्शाता है। एक वास्तविक कार्यान्वयन में फिक्स्ड-विड्थ इंटीजर्स, एक स्पष्ट हैश फ़ंक्शन और rho के लिए एक सीमा का उपयोग किया जाना चाहिए।
init(p):
m = 1 << p
M = array(m, fill=0)
add(x):
h = hash64(x)
j = high_bits(h, p)
w = remaining_bits(h, p)
r = leading_zero_count(w) + 1
M[j] = max(M[j], r)
estimate():
z = sum over j of 2^(-M[j])
e = alpha(m) * m * m / z
if e <= small_range_threshold(m) and zero_registers(M) != 0:
e = m * log(m / zero_registers(M))
return large_range_correction_if_needed(e)
merge(other):
require same p, hash function, and register encoding
for j in 0..m-1:
M[j] = max(M[j], other.M[j])5. जटिलता और शुद्धता
प्रत्येक तत्व के लिए एक हैश और एक रजिस्टर अपडेट की आवश्यकता होती है, इसलिए समय जटिलता (time complexity) O(1) है; स्पेस जटिलता (space complexity) O(m) है, जो स्ट्रीम की लंबाई से स्वतंत्र है। मानक HLL में सापेक्ष मानक त्रुटि (relative standard error) लगभग 1.04 / sqrt(m) होती है: m = 16,384 के लिए, यह लगभग 0.81% है। यह एक प्रायिकता आधारित अनुमान त्रुटि (probabilistic estimation error) है, न कि कोई गारंटी कि प्रत्येक क्वेरी एक निश्चित अंतराल में ही होगी।
चूंकि अपडेट्स मैक्सिमम मान लेते हैं, इसलिए एक ही तत्व को बार-बार जोड़ने से स्थिति में बदलाव नहीं होता रहता, जिससे आइडम्पोटेंस (idempotence) प्राप्त होती है। शार्ड्स को रजिस्टर-वार मैक्सिमम लेकर मर्ज किया जा सकता है, बशर्ते हैश फ़ंक्शन, p, और एन्कोडिंग समान हों; अन्यथा उनके सांख्यिकीय वितरण असंगत होंगे।
6. फॉलो-अप और संभावित गलतियाँ
- HLL एक अनुमान देता है; जब उत्पाद को प्रति-यूज़र सटीक सूची, ऑडिट ट्रेल या बिलिंग मात्रा की आवश्यकता होती है, तो यह सटीक सेट की जगह नहीं ले सकता।
- रजिस्टरों को साफ़ करना केवल एक नई विंडो को दर्शाता है। एक स्लाइडिंग विंडो के लिए टाइम बकेट्स, एकाधिक HLLs, या एक डिलीट करने योग्य वेरिएंट, साथ ही सीमा और स्टोरेज हैंडलिंग की आवश्यकता होती है।
- हैश टकराव (collisions) और इनपुट पूर्वाग्रह (bias) अनुमान को प्रभावित करते हैं। एक स्थिर 64-बिट या व्यापक हैश चुनें और इसे सेवा सीमाओं के पार मानकीकृत करें।
- रॉ हार्मोनिक एस्टीमेटर छोटी कार्डिनैलिटी के लिए पक्षपाती (biased) होता है; लीनियर काउंटिंग उस पूर्वाग्रह को कम करने के लिए शून्य रजिस्टरों की संख्या का उपयोग करती है।
7. अतिरिक्त पठन सामग्री
- Redis PFCOUNT और HyperLogLog डेटा प्रकार प्रलेखन।
- Snowflake अनुमानित कार्डिनैलिटी प्रलेखन।
- Presto में HyperLogLog का Meta Engineering अवलोकन।
8. साक्षात्कार स्कोरिंग बिंदु
स्टेट की व्याख्या कर सकते हैं
उम्मीदवार को m = 2^p रजिस्टरों, इंडेक्स, rho की उत्पत्ति, और प्रत्येक रजिस्टर केवल अधिकतम मान ही क्यों रखता है, इसकी व्याख्या करनी चाहिए।
त्रुटि और सुधारों को निकाल सकते हैं
उन्हें 1.04 / sqrt(m) परिमाण का क्रम देना चाहिए, स्मॉल-रेंज लीनियर काउंटिंग और लार्ज-रेंज सुधार की व्याख्या करनी चाहिए, और प्रायिकता आधारित त्रुटि को एक सटीक गारंटी से अलग समझना चाहिए।
डिस्ट्रीब्यूटेड मर्ज को संभाल सकते हैं
उन्हें यह स्पष्ट करना चाहिए कि मर्ज एक रजिस्टर-वार मैक्सिमम है और प्रत्येक शार्ड को समान हैश फ़ंक्शन, प्रिसिजन और एन्कोडिंग साझा करनी चाहिए।
उत्पाद सीमाओं की पहचान कर सकते हैं
उन्हें अनुमानित एनालिटिक्स को सटीक सूचियों, स्लाइडिंग विंडो, विलोपन और बिलिंग से अलग करना चाहिए, और यह समझाना चाहिए कि इन आवश्यकताओं के लिए अतिरिक्त डिज़ाइन की आवश्यकता क्यों होती है।