कोडिंग इंटरव्यू: एक Resumable Batched Iterator को कैसे डिज़ाइन करें?

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

एक ऐसा इटरेटर डिज़ाइन करें जो किसी पेजिनेटेड रिमोट API को एक समय में एक आइटम करके पार (walk) करता है। प्रत्येक पेज में अधिकतम 100 आइटम होते हैं और यह एक pageToken का उपयोग करता है; अनुरोध विफल हो सकते हैं या डुप्लिकेट लौटा सकते हैं, और कॉलर बाद में फिर से शुरू करने के लिए मनमाने बिंदुओं पर एक कर्सर सहेजता है। इंटरफ़ेस, इनवेरिएंट्स, बफरिंग, डिडुप्लीकेशन, रिकवरी सेमेंटिक्स, जटिलता और परीक्षणों की व्याख्या करें।

इटरेटर डिज़ाइन सार्वजनिक इंटरव्यू सामग्री में दिखाई देता है; Java API hasNext() को किसी अन्य तत्व की जाँच करने के रूप में और next() को इसे लौटाने या कुछ भी न बचने पर फेंकने (throw) के रूप में परिभाषित करता है। यह प्रश्न परिचित इन-मेमोरी पैटर्न को एक रिज़्यूमेबल, बैचेड रिमोट इटरेटर तक विस्तारित करता है और स्टेट बाउंड्रीज़ पर ध्यान केंद्रित करता है।

इंटरव्यूअर्स क्या आकलन करते हैं

एक औसत उत्तर एक ऐरे इंडेक्स लिखता है। एक मजबूत उत्तर पेज टोकन, इन-पेज इंडेक्स, डिलीवर किए गए आइटम और कॉलर द्वारा पावती (acknowledged) किए गए चेकपॉइंट को अलग करता है, फिर बताता है कि पुनः प्रयास (retries) चुपचाप स्किप या डुप्लिकेट क्यों नहीं कर सकते। फॉलो-अप में डुप्लिकेट पेज, पेजिनेशन के दौरान डेटा बदलना, hasNext() के बाद क्रैश और समवर्ती (concurrent) कॉल शामिल हैं।

मुख्य संकेत रिमोट पेजिनेशन को स्थानीय ऐरे की तरह मानने के बजाय बाहरी साइड इफ़ेक्ट को नियंत्रित करने के लिए इनवेरिएंट्स का उपयोग करना है।

स्पष्टीकरण के प्रश्न

• क्या क्रम स्थिर (stable) है? एक अपरिवर्तनीय (createdAt, id) क्रम मान लें; इसके बिना, सटीक रिकवरी का वादा नहीं किया जा सकता है।
• क्या रिकवरी at-least-once है या exactly-once? at-least-once रीड्स चुनें और कॉलर को स्थिर ID द्वारा डिडुप्लीकेट करने दें; रिमोट सेवा में कोई क्रॉस-रिक्वेस्ट ट्रांजेक्शन नहीं है।
• क्या पंक्तियाँ सम्मिलित या हटाई जा सकती हैं? मान लें कि एक स्नैपशॉट या कंसिस्टेंसी टोकन परिणाम सेट को ठीक करता है; अन्यथा केवल एक कमजोर ट्रैवर्सल का वादा करें।
• क्या समवर्ती कॉल की अनुमति है? सिंगल-थ्रेडेड उपयोग को डिफ़ॉल्ट रखें; समवर्ती कॉल के लिए लॉक या स्पष्ट स्टेट त्रुटि की आवश्यकता होती है।
• क्या विफलता के बाद पुनरावृत्ति जारी रह सकती है? एक सीमा के भीतर क्षणिक (transient) नेटवर्क त्रुटियों का पुनः प्रयास करें; प्रमाणीकरण, पैरामीटर और समाप्त स्नैपशॉट त्रुटियों को तुरंत आगे भेजें।

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

“मैं कर्सर को एक स्नैपशॉट संस्करण, अगले-पेज टोकन और इन-पेज इंडेक्स में विभाजित करता हूँ। इटरेटर एक पेज को कैश करता है; hasNext() डिलीवरी स्थिति को आगे नहीं बढ़ाता है, जबकि next() एक आइटम का उपभोग करता है और इंडेक्स को आगे बढ़ाता है। पर्सिस्ट किया गया कर्सर कॉलर द्वारा स्वीकार किए गए अंतिम डिलीवर किए गए आइटम का प्रतिनिधित्व करता है, इसलिए रिकवरी एक बाउंड्री को दोहरा सकती है और at-least-once है; डाउनस्ट्रीम कोड स्थिर ID द्वारा डिडुप्लीकेट करता है। API को स्थिर क्रम और एक स्नैपशॉट की आवश्यकता होती है, अन्यथा मैं कमजोर निरंतरता (consistency) बताता हूँ। नेटवर्क विफलताओं में सीमित पुनः प्रयास होते हैं और स्थायी त्रुटियां आगे बढ़ाई जाती हैं।”

चरण-दर-चरण उत्तर

चरण 1: स्टेट और इंटरफ़ेस अनुबंध को परिभाषित करें

इंटरफ़ेस hasNext(), next(), checkpoint() और close() को प्रदर्शित कर सकता है। hasNext() बफर का निरीक्षण कर सकता है या एक पेज को प्रीफ़ेच कर सकता है, लेकिन इसे किसी आइटम को डिलीवर के रूप में चिह्नित नहीं करना चाहिए। next() एक आइटम लौटाता है और index को आगे बढ़ाता है। checkpoint() एक सीरियलाइज़ेबल टोकन बनाता है; कॉलर तय करता है कि उस प्रगति को कब स्वीकार किया जाए।

चरण 2: इनवेरिएंट्स स्थापित करें

0 <= index <= len(buffer)
next() returns buffer[index], then increments index
replace buffer and pageToken only after a whole page succeeds
the recovery token represents only the caller-acknowledged prefix
permanent errors are never swallowed by a retry loop

यदि अगले-पेज का अनुरोध विफल हो जाता है, तो पुराना बफर और डिलीवरी स्थिति बनाए रखें। यदि कोई नया पेज सफल होता है लेकिन चेकपॉइंट सहेजने से पहले प्रक्रिया क्रैश हो जाती है, तो रिकवरी एक प्रत्यय (suffix) को दोहराती है, जो कि at-least-once है। डिलीवरी से पहले चेकपॉइंट को सहेजने से कोई आइटम छूट सकता है, इसलिए क्रम मायने रखता है।

चरण 3: पेज रीड्स और बाउंडेड रिट्राइज़ लागू करें

class ResumableIterator:
    def __init__(self, client, checkpoint=None, page_size=100):
        self.client = client
        self.page_size = page_size
        self.snapshot = checkpoint.snapshot if checkpoint else None
        self.token = checkpoint.page_token if checkpoint else None
        self.index = checkpoint.index if checkpoint else 0
        self.buffer = []
        self.done = False

    def has_next(self):
        self._ensure_buffer()
        return self.index < len(self.buffer)

    def next(self):
        self._ensure_buffer()
        if self.index == len(self.buffer):
            raise StopIteration
        item = self.buffer[self.index]
        self.index += 1
        return item

    def checkpoint(self):
        return Checkpoint(self.snapshot, self.token, self.index)

_ensure_buffer() वर्तमान पेज समाप्त होने पर अगले पेज का अनुरोध करता है, जिसमें एक्सपोनेंशियल बैकऑफ़ और अधिकतम प्रयास गणना का उपयोग किया जाता है। एक सफल सर्वर-साइड अनुरोध के बाद टाइमआउट हो सकता है, इसलिए पुनः प्रयास में उसी स्नैपशॉट/टोकन का उपयोग होना चाहिए और सर्वर को एक स्थिर पेज या एक अवलोकनीय डुप्लिकेट बाउंड्री लौटानी चाहिए।

चरण 4: डुप्लिकेट्स, इंसर्ट्स और डिलीट्स को संभालें

पुनः प्रयास के बाद केवल एक पेज टोकन डुप्लिकेट डेटा को नहीं रोक सकता है। यदि API एक स्थिर id लौटाता है, तो रिकवरी बाउंड्री पर उस प्रीफ़िक्स को छोड़ दें जहाँ id <= lastId; कंपाउंड सॉर्ट के लिए, पूरे (createdAt, id) कर्सर की तुलना करें। एक असीमित डिडुप्लीकेशन सेट न बढ़ाएँ; एक सर्वर स्नैपशॉट और बाउंड्री टोकन डिडुप्लीकेशन को रिकवरी विंडो तक स्थानीय रखते हैं।

बिना स्नैपशॉट के, वर्तमान पेज से पहले एक नई पंक्ति दिखाई दे सकती है और डिलीट करने से अगला पेज किसी आइटम को छोड़ सकता है। दृश्यमान परिणाम के केवल सर्वश्रेष्ठ प्रयास (best-effort) ट्रैवर्सल का वादा करें, exactly-once या मजबूत कंसिस्टेंसी का नहीं। एक इंटरव्यू में, गारंटी को स्पष्ट रूप से कम करें या स्नैपशॉट संस्करण की आवश्यकता रखें।

चरण 5: चेकपॉइंट और रिकवरी सेमेंटिक्स को परिभाषित करें

एक चेकपॉइंट में संस्करण, स्नैपशॉट, टोकन, इन-पेज इंडेक्स, अंतिम स्थिर ID, एक फ़िल्टर डाइजेस्ट और समाप्ति समय होना चाहिए। फ़िल्टर डाइजेस्ट एक क्वेरी के कर्सर को दूसरी क्वेरी में रिस्टोर होने से रोकता है; समाप्ति सर्वर द्वारा स्नैपशॉट को पुनः प्राप्त करने के बाद किसी भिन्न परिणाम को चुपचाप पढ़ने से रोकती है।

चेकपॉइंट से इटरेटर का पुनर्निर्माण करें। यदि कॉलर item का उपभोग करने के तुरंत बाद सहेजता है, तो रिकवरी उस आइटम को दोहरा सकती है, इसलिए डाउनस्ट्रीम राइट्स स्थिर ID द्वारा इडेम्पोटेंट होने चाहिए। यदि व्यवसाय को किसी डुप्लिकेट की आवश्यकता नहीं है, तो प्रगति और व्यावसायिक परिणाम को एक ट्रांजेक्शन साझा करना चाहिए या डाउनस्ट्रीम स्टोर को एक डिडुप्लीकेशन तालिका प्रदान करनी चाहिए; इटरेटर अपने आप exactly-once नहीं बना सकता है।

चरण 6: जटिलता, बैकप्रेशर, और बंद करना

बफर स्पेस O(page_size) है और स्थानीय उन्नति प्रति आइटम O(1) है। पुनः प्रयासों को छोड़कर, रिमोट रीड्स लगभग ceil(N / page_size) हैं। hasNext() एक नेटवर्क अनुरोध जारी कर सकता है, इसलिए कॉलर्स को इसे मुफ़्त नहीं मानना चाहिए। प्रीफ़ेच विलंबता (latency) को छिपा सकता है लेकिन इसे एक पेज या बाइट बजट पर सीमित होना चाहिए।

close() बकाया काम को रद्द करता है और कनेक्शन जारी करता है; सर्वर स्नैपशॉट को TTL की आवश्यकता होती है। यदि कोई उपभोक्ता उत्पादक की तुलना में धीमा है, तो API को स्नैपशॉट को हमेशा के लिए बढ़ाने के बजाय दर-सीमित (rate-limit) करना चाहिए या समाप्त-स्नैपशॉट त्रुटि लौटानी चाहिए। समवर्ती कॉल को अस्वीकार या क्रमबद्ध (serialized) किया जाना चाहिए, अन्यथा दो next() कॉल एक ही इंडेक्स का निरीक्षण कर सकते हैं।

उच्च गुणवत्ता वाला नमूना उत्तर

“मैं रिमोट इटरेटर को snapshot, pageToken, buffer, index और lastId के साथ एक छोटे स्टेट मशीन के रूप में मॉडल करूँगा। hasNext() केवल यह सुनिश्चित करता है कि एक बफर आइटम मौजूद है; next() index को आगे बढ़ाता है; checkpoint() कॉलर द्वारा स्वीकृत प्रीफ़िक्स को संग्रहीत करता है। पूरे पेज के सफल होने के बाद ही बफर को बदलें, एक सीमा के साथ क्षणिक टाइमआउट का पुनः प्रयास करें, और स्थायी त्रुटियों को आगे बढ़ाएं।

“रिकवरी के लिए मुझे स्थिर क्रम और एक स्नैपशॉट टोकन की आवश्यकता होती है। चेकपॉइंट में क्वेरी डाइजेस्ट, इन-पेज इंडेक्स, अंतिम स्थिर ID और समाप्ति भी शामिल है। रिकवरी सीमा को दोहरा सकती है, इसलिए मैं at-least-once का वादा करता हूँ और डाउनस्ट्रीम राइट्स को ID द्वारा इडेम्पोटेंट बनाता हूँ। बिना स्नैपशॉट के, इंसर्ट और डिलीट गारंटी को कमजोर करते हैं।

“बफर O(pagesize) है, प्रत्येक next O(1) है, और रिमोट पेज लगभग ceil(N/pagesize) हैं। परीक्षण खाली पेजों, डुप्लिकेट पेजों, समाप्त टोकन, सर्वर की सफलता के बाद टाइमआउट, चेकपॉइंट क्रैश, म्यूटेशन, दोहराई गई रिकवरी, समवर्ती next, बैकप्रेशर और क्लोज़ को कवर करते हैं। Exactly-once के लिए एक साझा ट्रांजेक्शन या एक डिडुप्लीकेशन स्टोर की आवश्यकता होती है।”

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

• लक्षण → रिमोट API को एक ऐरे की तरह मानना और एक पूर्णांक इंडेक्स को रिस्टोर करना → यह विफल क्यों होता है → पेज की सीमाएँ और म्यूटेशन उस इंडेक्स को अलग-अलग आइटम पर इंगित करते हैं → सुधार → स्नैपशॉट, टोकन, इन-पेज इंडेक्स और स्थिर ID को पर्सिस्ट करें।
• लक्षण → hasNext() में टोकन को आगे बढ़ाना → यह विफल क्यों होता है → एक कॉलर बिना उपभोग किए निरीक्षण कर सकता है और फिर क्रैश हो सकता है, जिससे डेटा छूट जाता है → सुधार → केवल next() द्वारा आइटम लौटाए जाने के बाद ही डिलीवरी स्थिति को आगे बढ़ाएं।
• लक्षण → टाइमआउट के बाद अगले पेज पर जाना → यह विफल क्यों होता है → एक पूरा पेज खो सकता है या एक सफल अनुरोध डुप्लिकेट हो सकता है → सुधार → उसी टोकन का पुनः प्रयास करें और स्थिर ID द्वारा डिडुप्लीकेट करें।
• लक्षण → इटरेटर से exactly-once का दावा करना → यह विफल क्यों होता है → चेकपॉइंट पर्सिस्टेंस और व्यावसायिक साइड इफ़ेक्ट एक परमाणु (atomic) ट्रांजेक्शन नहीं हैं → सुधार → at-least-once का वादा करें और सिंक को इडेम्पोटेंट या ट्रांजैक्शनल बनाएं।
• लक्षण → असीमित प्रीफ़ेच और पुनः प्रयास → यह विफल क्यों होता है → धीमे उपभोक्ता मेमोरी समाप्त कर देते हैं और आउटेज हमेशा के लिए ब्लॉक कर देते हैं → सुधार → बफ़र्स, प्रयासों, टाइमआउट और स्नैपशॉट TTL को सीमित करें।

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

क्या होगा यदि सर्वर केवल एक पेज नंबर प्रदान करता है, स्नैपशॉट टोकन नहीं?

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

क्या होगा यदि सिंक प्रत्येक आइटम को केवल एक बार स्वीकार करता है और डिडुप्लीकेट नहीं कर सकता है?

इटरेटर अकेले exactly-once की गारंटी नहीं दे सकता है। प्रगति, व्यावसायिक राइट और चेकपॉइंट को एक ट्रांजेक्शन में रखें, या एक इडेम्पोटेंट सिंक की आवश्यकता रखें; अन्यथा अनुबंध में संभावित डुप्लिकेट लिखें।

क्या होगा यदि एक पेज पर बार-बार टाइमआउट होता रहे?

पुराना बफर बनाए रखें और टोकन को आगे न बढ़ाएं। पुनः प्रयास सीमा के बाद, एक वर्गीकृत त्रुटि उत्पन्न करें ताकि कॉलर रुकने, छोड़ने या पुनरारंभ करने का चयन कर सके। एक स्किप को एक अंतराल (gap) रिकॉर्ड करना चाहिए और चुपचाप अगले पेज पर नहीं जा सकता।