कोडिंग इंटरव्यू: आप एक डिपेंडेंसी-अवेयर टास्क शेड्यूलर कैसे बनाएंगे?

प्रॉम्प्ट और दायरा

एक इन-मेमोरी TaskScheduler लागू करें। एक कॉलर टास्क ID, डिपेंडेंसी IDs और एक फ़ंक्शन सबमिट करता है। शेड्यूलर किसी टास्क पर केवल तभी दावा (claim) कर सकता है जब उसकी प्रत्येक डिपेंडेंसी सफल हो चुकी हो। submit, ready, complete, fail, और cancel जैसे ऑपरेशन्स प्रदर्शित करें, और ऐसी डिपेंडेंसी साइकिल की रिपोर्ट करें जो कभी नहीं चल सकतीं। डुप्लिकेट सबमिशन, विफलता प्रसार, कॉनकरेंसी सीमाएं, शटडाउन और रीस्टार्ट सीमाओं की व्याख्या करें।

यह समस्या ग्राफ़ ट्रैवर्सल को एक लाइव स्टेट मशीन के साथ जोड़ती है। एक सटीक उत्तर डेटा संरचनाओं को चुनने से पहले स्टेट और विफलता सेमेंटिक्स को स्पष्ट करता है, फिर इनडिग्री (indegrees), रिवर्स एजेस और एक रेडी क्यू (ready queue) बनाए रखता है। Python का TopologicalSorter उन नोड्स को प्रोसेस करने योग्य मानता है जिनके कोई अधूरे पूर्ववर्ती (predecessors) नहीं हैं और पहचानी गई साइकिल को डायग्नोस्टिक डेटा के रूप में प्रस्तुत करता है। वे सेमेंटिक्स अनुबंध (contract) को परिभाषित करने में मदद करते हैं, लेकिन केवल एक स्थिर टोपोलॉजिकल सॉर्ट अपर्याप्त है क्योंकि कार्य समय के साथ पूरे होते हैं, विफल होते हैं और रद्द होते हैं।

इंटरव्यूअर क्या जांच रहा है

pending, ready, running, succeeded, failed, blocked, और cancelled के बीच अंतर करना।
प्रत्येक टास्क को दोबारा स्कैन करने के बजाय इनडिग्री और रिवर्स-एडजेंसी इनवेरिएंट्स को बनाए रखना।
किसी डिपेंडेंसी के पूरा होने पर केवल प्रभावित आश्रितों (dependents) को रिलीज़ करना।
API चुनने से पहले साइकिल, विफलता और कैंसलेशन प्रसार को परिभाषित करना।
वर्कर्स को सीमित करना, प्रति टास्क संस्करण केवल एक क्लेम की गारंटी देना, और डुप्लिकेट सबमिशन को संभालना।
जटिलता सीमाएं (complexity bounds) और प्रतिकूल इंटरलीविंग (adversarial interleavings) के लिए परीक्षण प्रदान करना।

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

क्या ग्राफ़ स्थिर है या कार्यों को गतिशील रूप से जोड़ा जा सकता है? मान लें कि शेड्यूलिंग शुरू होने से पहले सभी संदर्भित कार्य सबमिट कर दिए गए हैं; चलने के दौरान केवल एक नया संस्करण सबमिट किया जा सकता है।
किसी डिपेंडेंसी के विफल होने के बाद वंशजों (descendants) का क्या होता है? यह उत्तर उन्हें blocked के रूप में चिह्नित करता है; पुनः प्रयास (retry) के लिए एक स्पष्ट नई पीढ़ी (generation) की आवश्यकता होती है।
क्या कैंसलेशन प्रत्येक वंशज तक जाता है? मान लें कि यह केवल उस कार्य को रद्द करता है; आवश्यक डिपेंडेंसी रद्द होने पर वंशज blocked बन जाते हैं।
क्या विफलताओं का स्वतः पुनः प्रयास किया जाता है? नहीं। कॉलर एक नई पीढ़ी सबमिट करता है और साइड इफेक्ट्स के लिए इडेम्पोटेंसी (idempotency) का स्वामित्व रखता है।
क्या ready() एक कार्य लौटाता है या एक बैच? नियतात्मक (deterministic) क्रम में अधिकतम maxConcurrency - running कार्य लौटाएं।

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

प्रत्येक टास्क की स्थिति, अधूरी-डिपेंडेंसी की संख्या और रिवर्स एडजेंसी लिस्ट को स्टोर करें। शेड्यूलिंग से पहले, Kahn का एल्गोरिदम या थ्री-कलर DFS चलाएं और यदि कोई साइकिल मौजूद है तो साइकिल पाथ लौटाएं। ज़ीरो-इनडिग्री वाले कार्यों को एक स्थिर रेडी क्यू में रखें। एक लॉक के तहत, ready को running में बदलकर कार्यों पर क्लेम करें; सफलता पर, प्रत्येक आश्रित की गिनती घटाएं और जो शून्य पर पहुंचें उन्हें कतारबद्ध (enqueue) करें। विफलता और कैंसलेशन प्रभावित वंशजों को blocked के रूप में चिह्नित करते हैं। प्रत्येक कॉलबैक में एक जेनरेशन होता है ताकि पुराने वर्कर्स आश्रितों को दो बार रिलीज़ न कर सकें। एक निश्चित वर्कर पूल या सेमाफोर कॉनकरेंसी लागू करता है।

चरण-दर-चरण समाधान

चरण 1: अवस्थाओं (States) और सीमाओं को परिभाषित करें

अवस्थाएं आगे बढ़ती हैं: pending से ready, फिर running, और अंत में succeeded या failed। कैंसलेशन pending या ready के दौरान हो सकता है; चल रहे फ़ंक्शन का कैंसलेशन सहयोगात्मक (cooperative) होता है। blocked का अर्थ है कि फ़ंक्शन नहीं चला क्योंकि एक आवश्यक डिपेंडेंसी अब सफल नहीं हो सकती। टर्मिनल अवस्थाएं कभी भी ready पर वापस नहीं लौटती हैं, जिससे डुप्लिकेट निष्पादन रुकता है।

प्रति टास्क ID एक generation स्टोर करें। एक डुप्लिकेट सबमिशन को अस्वीकार किया जा सकता है या एक नई पीढ़ी बनाई जा सकती है; यह उत्तर केवल तभी प्रतिस्थापन चुनता है जब पुराना संस्करण नहीं चल रहा हो। चल रहे संस्करण को चुपचाप अधिलेखित (overwrite) नहीं किया जा सकता; विरोध (conflict) लौटाएं या इसके टर्मिनल कॉलबैक की प्रतीक्षा करें।

चरण 2: इनडिग्री और रिवर्स एजेस का निर्माण करें

टास्क टेबल remainingDeps स्टोर करती है; एक रिवर्स मैप dependents[dependencyId] स्टोर करता है। प्रत्येक एज को एक बार रजिस्टर करें। इनिशियलाइज़ेशन के दौरान ज़ीरो-इनडिग्री टास्क रेडी क्यू में प्रवेश करते हैं, और बाद के परिवर्तन केवल प्रभावित काउंट्स को अपडेट करते हैं।

text

Task:
  id, generation, dependencies, dependents
  remainingDeps, state, fn, error

submit(task):
  validateUniqueDependencies(task)
  registerEdges(task)
  if task.remainingDeps == 0:
      task.state = READY
      readyQueue.push(task.id)

किसी अज्ञात डिपेंडेंसी को पहले से पूर्ण नहीं माना जाना चाहिए। सबमिट होने तक इसे waiting अवस्था में रखें, या यदि अनुबंध के लिए एक क्लोज्ड ग्राफ़ की आवश्यकता है तो इसे UnknownDependency त्रुटि के साथ अस्वीकार करें।

चरण 3: निष्पादन से पहले साइकिल की रिपोर्ट करें

एक स्थिर ग्राफ़ के लिए, Kahn का एल्गोरिदम इनडिग्री की कॉपी बनाता है, ज़ीरो-इनडिग्री नोड्स को प्रोसेस करता है और उनके आउटगोइंग एजेस को हटाता है। यदि सभी नोड्स से कम प्रोसेस होते हैं, तो शेष भाग में एक साइकिल होती है। केवल एक बूलियन ही नहीं, बल्कि A → B → C → A जैसा एक ठोस पाथ लौटाएं।

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

चरण 4: कार्यों पर क्लेम करें और कॉनकरेंसी लागू करें

ready() उपलब्ध स्लॉट की गणना करता है, स्थिर सबमिशन क्रम में कार्यों को हटाता है, और उसी क्रिटिकल सेक्शन में प्रत्येक स्थिति को running में बदलता है। एक बार लौटाए जाने के बाद, दूसरा कॉलर उस टास्क पर क्लेम नहीं कर सकता। complete(id, generation) जेनरेशन और स्टेट दोनों को मान्य करता है; किसी पुराने वर्कर का विलंबित कॉलबैक कन्फ्लिक्ट लौटाता है और आश्रितों को रिलीज़ नहीं कर सकता।

कॉनकरेंसी सीमा के लिए एक निश्चित वर्कर काउंट या सेमाफोर का उपयोग करें। कतार की लंबाई सक्रिय-टास्क गणना नहीं है: केवल running टास्क ही स्लॉट का उपभोग करते हैं। यदि अनुरोधित बैच उपलब्ध स्लॉट से अधिक है, तो चुपचाप कॉनकरेंसी बढ़ाने के बजाय उपलब्ध संख्या या CapacityExceeded लौटाएं।

चरण 5: सफलता, विफलता और कैंसलेशन का प्रसार करें

सफलता पर, सीधे आश्रितों को ट्रैवर्स करें। केवल लंबित (pending) संस्करणों के लिए remainingDeps घटाएं; जब काउंट शून्य तक पहुंच जाए तो नोड को कतारबद्ध करें। विफलता पर, यह अनुबंध प्रत्यक्ष और सकर्मक (transitive) वंशजों को blocked के रूप में चिह्नित करता है और पहले ब्लॉकिंग कारण को रिकॉर्ड करता है। वैकल्पिक-डिपेंडेंसी नीति केवल तभी मान्य होती है जब स्पष्ट रूप से बताई गई हो।

कैंसलेशन उन संस्करणों को प्रभावित करता है जो शुरू नहीं हुए हैं। चल रहे फ़ंक्शन को AbortSignal प्राप्त हो सकता है, लेकिन केवल फ़ंक्शन ही सहयोगात्मक निकास (cooperative exit) की पुष्टि कर सकता है। जब कोई आवश्यक डिपेंडेंसी विफल या रद्द हो जाती है, तो वंशज blocked बन जाते हैं; वे कभी भी यह दिखावा नहीं करते कि वह डिपेंडेंसी सफल हुई थी।

चरण 6: सबमिशन और कॉलबैक को इडेम्पोटेंट बनाएं

(taskId, generation) को इडेम्पोटेंसी कुंजी के रूप में उपयोग करें। बार-बार किए गए complete, fail, या cancel कॉल ज्ञात टर्मिनल अवस्था लौटाते हैं और आश्रितों को दो बार नहीं घटाते हैं। किसी पेंडिंग संस्करण को बदलते समय, नए एजेस रजिस्टर करने से पहले उसके पुराने रिवर्स एजेस को हटा दें; केवल ऑब्जेक्ट को ओवरराइट करने से पुराने एजेस छूट जाते हैं और एक आश्रित हमेशा के लिए प्रतीक्षा कर सकता है।

यदि अपडेट अनावश्यक हैं, तो डुप्लिकेट ID को अस्वीकार करना आसान है। ट्रेडऑफ़ बताएं: एक स्थिर बिल्डर डुप्लिकेट को अस्वीकार कर सकता है, जबकि लंबे समय तक चलने वाले वर्कफ़्लो को आमतौर पर पीढ़ियों (generations), ऑडिट रिकॉर्ड और स्पष्ट पुनः प्रयास संस्करणों की आवश्यकता होती है।

चरण 7: शटडाउन, पुनः प्रयास और रिकवरी

close() नए सबमिशन को अस्वीकार करता है, ready() को अधिक काम क्लेम करने से रोकता है, और चल रहे कॉलबैक या एक परिभाषित टाइमआउट की प्रतीक्षा करता है। कतारबद्ध कार्यों को अनुबंध के अनुसार रद्द या बनाए रखा जाता है; बिना कोई कारण रिकॉर्ड किए मेमोरी खाली करने से जानकारी नष्ट हो जाती है। एक पुनः प्रयास एक नई पीढ़ी बनाता है और failed को वापस ready में बदलने के बजाय डिपेंडेंसी स्नैपशॉट की फिर से जांच करता है।

एक इन-मेमोरी शेड्यूलर प्रोसेस क्रैश के बाद पुनर्प्राप्त नहीं हो सकता। पर्सिस्टेंस के लिए कार्यों, संस्करणों, अवस्थाओं, निर्भरताओं और लीज (leases) की आवश्यकता होती है। रिकवरी वर्कर्स सशर्त लेखन (conditional writes) के साथ कार्यों पर क्लेम करते हैं, और कार्य फ़ंक्शन इडेम्पोटेंट होने चाहिए। रिकवरी कम से कम एक बार निष्पादन (at-least-once execution) प्रदान कर सकती है, बिल्कुल-एक-बार साइड इफेक्ट्स (exactly-once side effects) नहीं।

चरण 8: जटिलता और परीक्षण

ग्राफ़ इनिशियलाइज़ेशन O(V + E) है। प्रत्येक पूर्णता केवल आउटगोइंग एजेस को स्कैन करती है, इसलिए संपूर्ण प्रसार पास O(V + E) रहता है; एक हीप-आधारित रेडी क्यू O(log V) में क्लेम करती है। स्पेस O(V + E) है।

एक खाली ग्राफ़, स्वतंत्र शाखाओं, एक लंबी श्रृंखला, साइकिल, अज्ञात निर्भरताएँ, एक साथ पूरी होने वाली दो निर्भरताएँ, विफलता प्रसार, वंशज कैंसलेशन, डुप्लिकेट कॉलबैक, डुप्लिकेट सबमिशन, शून्य क्षमता, शटडाउन रेस और पुरानी पीढ़ियों के विलंबित कॉलबैक का परीक्षण करें। एक छोटा स्टेट मॉडल प्रत्येक रेडी सेट की तुलना कर सकता है और प्रति संस्करण अधिकतम एक pending → running संक्रमण (transition) का दावा कर सकता है।

मॉडल उत्तर

मैं पहले ग्राफ़ को फ़्रीज़ करूंगा, फिर प्रत्येक कार्य के लिए स्टेट, जेनरेशन, शेष डिपेंडेंसी काउंट और रिवर्स एडजेंसी को स्टोर करूंगा। पैरेंट पॉइंटर्स के साथ Kahn का एल्गोरिदम एक ठोस साइकिल की रिपोर्ट करता है। बिना किसी डिपेंडेंसी वाले कार्य एक स्थिर रेडी क्यू में प्रवेश करते हैं। ready() एक लॉक के तहत शेष कॉनकरेंसी स्लॉट तक क्लेम करता है और तुरंत कार्यों को running के रूप में चिह्नित करता है। एक पूर्णता कॉलबैक जेनरेशन से मेल खाना चाहिए और केवल एक बार ट्रांज़िशन कर सकता है; सफलता डाउनस्ट्रीम काउंट्स को घटाती है और शून्य तक पहुंचने वाले नोड्स को कतारबद्ध करती है। विफलता और कैंसलेशन नकली सफलता के बजाय blocked वंशज उत्पन्न करते हैं। डुप्लिकेट कॉलबैक इडेम्पोटेंट होते हैं, पुनः प्रयास एक नई पीढ़ी बनाते हैं, और शटडाउन चल रहे कॉलबैक को ड्रेन करने से पहले नए काम को अस्वीकार कर देता है। पास O(V + E) है और परीक्षण कॉनकरेंसी और साइड-इफेक्ट सीमाओं को कवर करते हैं।

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

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

फॉलो-अप प्रश्न

आप ऐसे ग्राफ़ को कैसे संभालेंगे जो मेमोरी के लिए बहुत बड़ा है?

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

आश्रित नोड्स के रुकने के दौरान एक विफल शाखा कैसे जारी रह सकती है?

एजेस को आवश्यक (required) या वैकल्पिक (optional) के रूप में लेबल करें। एक कार्य केवल तभी तैयार होता है जब सभी आवश्यक निर्भरताएँ सफल हो जाती हैं और वैकल्पिक निर्भरताएँ टर्मिनल स्थिति में पहुँच जाती हैं। वैकल्पिक विफलताओं को चुपचाप हटाने के बजाय इनपुट सारांश और मेट्रिक्स में रिकॉर्ड करें; यह स्टेट मशीन और परीक्षणों का विस्तार करता है।

आप गतिशील रूप से निर्भरताएँ कैसे जोड़ेंगे?

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

आप असंबंधित शाखाओं को नुकसान पहुंचाए बिना किसी साझा निर्भरता को कैसे रद्द करेंगे?

केवल उस डिपेंडेंसी की टर्मिनल स्थिति बदलें, फिर रिवर्स एजेस के साथ आवश्यक-एज संबंधों का निरीक्षण करें। उस डिपेंडेंसी के बिना वाली शाखाएं जारी रहती हैं; प्रत्येक डाउनस्ट्रीम कार्य जिसे इसकी आवश्यकता होती है वह blocked बन जाता है। ऑडिट करें कि इसे किसने, कब और किस प्रसार पथ के साथ रद्द किया।

एकाधिक वर्कर प्रक्रियाएं दोहरे निष्पादन से कैसे बचती हैं?

परमाणु (atomic) डेटाबेस अपडेट या लीज के साथ क्लेम करें और स्थिति में जेनरेशन शामिल करें। एक लीज समाप्त हो सकता है और दूसरे क्लेम की अनुमति दे सकता है, इसलिए फ़ंक्शन इडेम्पोटेंट या प्रतिपूर्ति योग्य (compensatable) होना चाहिए। एक इन-मेमोरी लॉक केवल एक प्रक्रिया की सुरक्षा करता है।

कौन से ऑब्जर्वेबिलिटी सिग्नल मायने रखते हैं?

साइकिल काउंट, ब्लॉक काउंट, रेडी वेट टाइम, रन ड्यूरेशन, क्लेम कन्फ्लिक्ट्स, लीज एक्सपायरी, डुप्लिकेट कॉलबैक, और प्रति एज प्रोपेगेशन लेटेंसी को ट्रैक करें। टास्क प्रकार और टेनेंट द्वारा विभाजित करें ताकि औसत टेल बैकलॉग को न छिपाए, और ग्राफ़ कॉन्फ़िगरेशन त्रुटियों को फ़ंक्शन विफलताओं से अलग करें।

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

स्टेट चेकिंग, स्लॉट डिक्रिमेंट, और running राइट को एक क्रिटिकल सेक्शन या एटॉमिक कंडीशनल अपडेट में रखें, और कॉलबैक में जेनरेशन शामिल करें। एक मॉडल टेस्ट दो ready() कॉल्स को इंटरलीव कर सकता है और प्रति संस्करण अधिकतम एक pending → running ट्रांज़िशन का दावा कर सकता है; डुप्लिकेट पूर्णता ज्ञात टर्मिनल स्थिति लौटाती है।