कोडिंग इंटरव्यू: एक Hashed Timing Wheel टाइमर लागू करें

प्रॉम्प्ट और संदर्भ

यह प्रश्न परीक्षण करता है कि क्या आप कई अनुमानित टाइमरों के लिए एक उपयुक्त डेटा संरचना चुन सकते हैं। एक बाइनरी हीप डेडलाइनों को क्रमबद्ध करता है, इसलिए इंसर्शन और डिलीशन हीप क्रम बनाए रखते हैं; एक टाइमिंग व्हील डेडलाइनों को बकेट्स में मैप करता है और नेटवर्क टाइमआउट, पुनः प्रयास (retries) और कनेक्शन कीपअलाइव के लिए उपयुक्त होता है जहाँ सटीक समय की आवश्यकता नहीं होती है। प्रिसिजन, जटिलता, कैंसलेशन सिमेंटिक्स, लंबे विलंब और निष्पादन-थ्रेड सीमा की व्याख्या करें।

साक्षात्कारकर्ता क्या मूल्यांकन कर रहा है

क्या आप टिक, बकेट गणना, कवर्ड स्पैन और टास्क डेडलाइन को सटीक रूप से जोड़ते हैं।
क्या आप रोटेशन पार करने वाले कार्यों, वर्तमान बकेट में कार्य, देर से आने वाले टिक्स और जल्दी निष्पादन को संभालते हैं।
क्या कैंसलेशन सस्ता है और कैंसल किए गए नोड्स गलती से निष्पादित नहीं हो सकते हैं।
क्या आप थ्रेड सुरक्षा, कॉलबैक आइसोलेशन, क्लॉक का चयन और ओवरलोड व्यवहार की व्याख्या कर सकते हैं।

पहले पूछे जाने वाले स्पष्टीकरण प्रश्न

टास्क की मात्रा, अनुमत न्यूनतम और अधिकतम त्रुटि, न्यूनतम और अधिकतम विलंब, कैंसलेशन अनुपात और कॉलबैक अवधि की पुष्टि करें। क्या कार्यों को ड्यूरेबल होना चाहिए, और क्या उन्हें प्रोसेस रीस्टार्ट के बाद भी बने रहना चाहिए? क्या एकाधिक थ्रेड्स schedule और cancel को कॉल कर सकते हैं? क्या कॉलबैक ब्लॉक हो सकते हैं? यदि एक टिक में बहुत सारे देय कार्य हैं, तो क्या निष्पादन में देरी की जानी चाहिए, कम प्राथमिकता वाले कार्य को छोड़ दिया जाना चाहिए, या बैकप्रेशर लागू किया जाना चाहिए? ये उत्तर निर्धारित करते हैं कि एक व्हील पर्याप्त है या आपको एक श्रेणीबद्ध व्हील (hierarchical wheel) या बाहरी पर्सिस्टेंस की आवश्यकता है।

30-सेकंड का उत्तर ढांचा

मैं एक मोनोटोनिक क्लॉक के साथ सापेक्ष डेडलाइनों की गणना करूँगा और एक निश्चित टिक पर कर्सर को आगे बढ़ाऊँगा। प्रत्येक कार्य के लिए, एक बकेट इंडेक्स और शेष राउंड की गणना करूँगा, फिर इसे एक डबली लिंक्ड लिस्ट में संग्रहीत करूँगा। प्रत्येक टिक पर, केवल वर्तमान बकेट को स्कैन करूँगा: शेष राउंड वाले कार्यों को घटाऊँगा और बनाए रखूँगा, और राउंड शून्य होने पर निष्पादन के लिए देय कार्यों को हटा दूँगा। एक हैंडल cancel को नोड को चिह्नित करने और अनलिंक करने की अनुमति देता है। व्हील कार्य को शेड्यूल करता है लेकिन टिक थ्रेड पर कभी भी उपयोगकर्ता कॉलबैक नहीं चलाता है; परीक्षणों और मेट्रिक्स के साथ प्रिसिजन, कॉनकूरेंसी और ओवरलोड व्यवहार का सत्यापन किया जाता है।

चरण-दर-चरण गहन विश्लेषण

1. व्हील पैरामीटर और त्रुटि परिभाषित करें

मान लें कि tickDuration टिक है और wheelSize बकेट्स की संख्या है; एक रोटेशन tickDuration × wheelSize को कवर करता है। डेडलाइन को सापेक्ष टिक्स में बदलें, फिर (currentTick + remainingTicks) mod wheelSize की गणना करें। टिक न्यूनतम रिज़ॉल्यूशन निर्धारित करता है, जबकि रोटेशन स्पैन यह निर्धारित करता है कि कौन से विलंब सीधे फिट होते हैं। एक बड़ी सीमा के लिए, एक श्रेणीबद्ध व्हील का उपयोग करें या शेष-राउंड का मान तब तक रखें जब तक कि कार्य को अधिक सटीक रूप से नहीं रखा जा सके।

2. टास्क नोड्स और बकेट संरचना चुनें

प्रत्येक नोड एक डेडलाइन, remainingRounds, कॉलबैक, कैंसलेशन फ़्लैग, और पिछले और अगले पॉइंटर्स को संग्रहीत करता है। एक डबली लिंक्ड लिस्ट नोड ज्ञात होने पर कॉन्स्टेंट-टाइम इंसर्शन और रिमूवल प्रदान करती है; एक हैंडल सीधे इसे इंगित कर सकता है, इसलिए cancel को खोजना नहीं पड़ता है। प्रत्येक कार्य को एक ऐरे में न रखें और प्रत्येक टिक पर उन सभी को स्कैन न करें, क्योंकि लागत कुल कार्य संख्या के साथ बढ़ती है।

3. टिक्स आगे बढ़ाएं और रोटेशन संभालें

मोनोटोनिक क्लॉक और कर्सर को आगे बढ़ाएं, फिर वर्तमान बकेट को अलग करें। यदि remainingRounds धनात्मक है, तो इसे घटाएं और नोड को फिर से डालें। अन्यथा वास्तविक डेडलाइन की तुलना करें: उस कार्य को फिर से बकेट करें जो अभी भी जल्दी है और केवल वही कार्य सबमिट करें जो देय है। यदि कोई थ्रेड पॉज़ कई टिक्स को छोड़ देता है, तो कैच-अप कार्य को सीमित करें और विलंब रिकॉर्ड करें ताकि रिकवरी असीमित समय के लिए ब्लॉक न हो।

4. schedule, cancel और रेस कंडीशंस को संभालें

एक प्रोड्यूसर कतार एक टिक थ्रेड को schedule और cancel अनुरोध भेज सकती है, जिससे बकेट-लॉक विवाद कम हो जाता है। Cancel अनलिंक करने का प्रयास करने से पहले फ़्लैग सेट करता है; टिक थ्रेड द्वारा बकेट से नोड लेने के बाद, यह फ़्लैग की फिर से जाँच करता है ताकि कोई रेस कैंसल किए गए कॉलबैक को न चला सके। वर्तमान से पहले की डेडलाइन को "अगले उपलब्ध टिक पर चलाएं" के रूप में परिभाषित किया जाना चाहिए, न कि ऋणात्मक मॉड्यूलो के साथ किसी मनमाने भविष्य के बकेट में परिवर्तित किया जाना चाहिए।

5. कॉलबैक और ओवरलोड को अलग करें

टिक थ्रेड केवल नोड्स को स्थानांतरित करता है और कार्य सबमिट करता है; एक बाउंडेड एक्ज़ीक्यूटर उपयोगकर्ता कॉलबैक चलाता है। जब यह भरा हो, तो कतार सीमा, प्राथमिकता के आधार पर छोड़े जाने योग्य कार्य को हटाना, गैर-महत्वपूर्ण कार्य में देरी करना, या ओवरलोड त्रुटि वापस करने जैसी नीति परिभाषित करें। यह निर्धारित करने के लिए कि क्या व्हील या डाउनस्ट्रीम एक्ज़ीक्यूटर बाधा है, समाप्ति विलंब, बकेट-स्कैन समय, कैंसलेशन, एक्ज़ीक्यूटर कतार की लंबाई और कॉलबैक विफलताओं को ट्रैक करें।

6. स्यूडोकोड के साथ मुख्य इनवेरिएंट को ठीक करें

मुख्य लूप को निम्नानुसार व्यक्त किया जा सकता है; लॉकिंग और थ्रेड का स्वामित्व कार्यान्वयन भाषा पर निर्भर करता है:

text

schedule(task, deadline):
    ticks = ceil((deadline - now) / tickDuration)
    ticks = max(ticks, 0)
    node.rounds = ticks / wheelSize
    node.bucket = (currentTick + ticks) % wheelSize
    buckets[node.bucket].append(node)
    return node.handle

advance(now):
    while currentTick <= floor(now / tickDuration):
        bucket = buckets[currentTick % wheelSize]
        for node in bucket.detachAll():
            if node.cancelled: continue
            if node.rounds > 0:
                node.rounds -= 1
                bucket.append(node)
            elif node.deadline <= now:
                executor.submit(node.callback)
            else:
                schedule(node, node.deadline)
        currentTick += 1

मॉडल उच्च-गुणवत्ता वाला उत्तर

मैं पहले त्रुटि सहनशीलता, विलंब सीमा, कैंसलेशन अनुपात, ड्यूरेबिलिटी और कॉलबैक ब्लॉकिंग की पुष्टि करूँगा। मैं एक मोनोटोनिक क्लॉक और फिक्स्ड टिक्स का उपयोग करूँगा, जिसमें डबली लिंक्ड बकेट सूचियाँ होंगी जिनके नोड्स डेडलाइन, शेष राउंड, कैंसलेशन फ़्लैग और हैंडल संग्रहीत करते हैं। Schedule बकेट और राउंड की गणना करता है; cancel हैंडल के माध्यम से अनलिंक करता है और फ़्लैग सेट करता है। टिक थ्रेड केवल वर्तमान बकेट को प्रोसेस करता है, भविष्य के रोटेशन के लिए राउंड घटाता है, और देय कॉलबैक को एक बाउंडेड एक्ज़ीक्यूटर को सबमिट करता है। छूटे हुए टिक्स के बाद कैच-अप को सीमित और मापा जाता है; एक्ज़ीक्यूटर ओवरलोड में कतार, प्राथमिकता और विफलता नीतियां होती हैं। परीक्षण सीमा डेडलाइनों, लंबे विलंबों, बार-बार कैंसलेशन, समवर्ती schedule/cancel, क्लॉक जंप, कॉलबैक अपवादों और लाखों नोड्स के साथ स्कैन लागत को कवर करते हैं। यदि सख्त त्रुटि या व्यापक सीमा की आवश्यकता है, तो व्हील हमेशा तेज़ होने का दावा करने के बजाय एक श्रेणीबद्ध व्हील या एक हीप जोड़ें।

सामान्य गलतियाँ

सापेक्ष विलंब के लिए वॉल-क्लॉक समय का उपयोग करना और सिस्टम-क्लॉक समायोजन की अनदेखी करना।
remainingRounds को भूल जाना, जिससे कोई कार्य पहले रोटेशन पर ही ट्रिगर हो जाए।
वर्तमान-बकेट के उस कार्य को निष्पादित करना या बिना सूचना खो देना जो अभी तक देय नहीं है।
नोड लेने के बाद दोबारा जांच किए बिना कैंसलेशन बूलियन सेट करना।
टिक थ्रेड पर सिंक्रोनस रूप से उपयोगकर्ता कॉलबैक चलाना और व्हील को रोकना।
प्रत्येक कार्य के एक निश्चित ऐरे को स्कैन करना और विरल शेड्यूलिंग दक्षता खोना।
छूटे हुए टिक्स, ओवरलोड, रीस्टार्ट रिकवरी और कॉलबैक विफलताओं के व्यवहार को छोड़ना।

फॉलो-अप प्रश्न और उत्तर

min-heap का उपयोग क्यों नहीं करते?

एक min-heap छोटे वर्कलोड या सख्त डेडलाइन ऑर्डरिंग के लिए उपयुक्त है, लेकिन प्रत्येक इंसर्शन या डिलीशन हीप ऑर्डर बनाए रखता है। एक टाइमिंग व्हील कॉन्स्टेंट-टाइम बकेट प्लेसमेंट और रिमूवल के लिए सटीकता का त्याग करता है, जो कई अनुमानित टाइमरों के अनुकूल है। व्हील हमेशा तेज़ होने का दावा करने के बजाय त्रुटि बजट और ऑपरेशन वितरण से चयन करें।

क्या होगा यदि टिक थ्रेड कई सेकंड के लिए रुक जाए?

बीत चुके टिक्स की गणना करने के लिए मोनोटोनिक समय का उपयोग करें, एक कैच-अप पास में प्रोसेस किए जाने वाले बकेट्स या कार्यों की संख्या को सीमित करें, और बाकी को बाद के लिए छोड़ दें। शेड्यूलिंग विलंब को मापें; यदि अचानक वृद्धि अस्वीकार्य है, तो रिकवरी के दौरान प्रत्येक कॉलबैक को सिंक्रोनस रूप से चलाने के बजाय बैचिंग को बैकप्रेशर के साथ जोड़ें।

आप यह कैसे सुनिश्चित करते हैं कि cancel किसी कार्य को निष्पादित नहीं कर सकता है?

हैंडल नोड को इंगित करता है। Cancel अनलिंक करने से पहले इसे एटॉमिक रूप से चिह्नित करता है, और टिक थ्रेड इसे अलग करने के बाद फिर से फ़्लैग की जाँच करता है। यदि कॉलबैक पहले ही सबमिट किया जा चुका है, तो कैंसलेशन लीनियरलाइज़ेशन पॉइंट को परिभाषित करें और कॉलबैक को शुरू होने से पहले टास्क स्थिति की जाँच करने दें।

आपको श्रेणीबद्ध टाइमिंग व्हील की आवश्यकता कब होती है?

जब एक रोटेशन सबसे बड़ी डेडलाइन को कवर नहीं कर सकता है या टास्क विलंब कई परिमाणों में फैले होते हैं, तो इसका उपयोग करें। प्रत्येक स्तर की सटीकता, गिरावट और माइग्रेशन लागत को परिभाषित करते हुए, मोटे ऊपरी स्तर जोड़ें और कार्यों को नीचे की ओर कैस्केड करें। ड्यूरेबिलिटी और क्रैश रिकवरी के लिए अभी भी व्हील को विश्वसनीय स्टोरेज या मैसेजिंग से अलग करने की आवश्यकता होती है।