डिस्ट्रिब्यूटेड-सिस्टम्स इंटरव्यू: Lamport clocks कब विफल होते हैं, और आपको vector clocks की आवश्यकता कब होती है?

प्रॉम्प्ट और उपयोग के मामले (Use cases)

Replicas विलंबित संदेशों (delayed messages) द्वारा संचार करते हैं और wall-clock क्रम पर निर्भर नहीं हो सकते। व्याख्या करें कि इवेंट causality के बारे में कैसे तर्क किया जाए, एक स्केलर Lamport टाइमस्टैम्प एक सुसंगत क्रम क्यों देता है लेकिन एक पूर्ण causality परीक्षण क्यों नहीं है, और एक vector clock अपनी मेटाडेटा लागत के लायक कब होती है। मुख्य श्रेणी general है: डिस्ट्रिब्यूटेड-सिस्टम्स रीजनिंग और स्पष्ट ट्रेड-ऑफ, न कि कोई विशिष्ट डेटाबेस या प्रोग्रामिंग भाषा।

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

क्या आप टाइमस्टैम्प को भौतिक समय मानने के बजाय happened-before को परिभाषित करते हैं।
क्या आप लोकल इवेंट्स, सेंड्स और रिसीव्स पर Lamport clock को सही ढंग से अपडेट करते हैं।
क्या आप एकतरफा गारंटी का उल्लेख करते हैं: a -> b का अर्थ L(a) < L(b) है, लेकिन इसका उल्टा गारंटीकृत नहीं है।
क्या आप वैक्टर की घटक-दर-घटक (component by component) तुलना करते हैं और समवर्ती घटनाओं (concurrent events) की पहचान करते हैं।
क्या आप प्रोसेस मेंबरशिप, वेक्टर साइज, मैसेज ओवरहेड, और रेप्लिकेट मंथन (replica churn) पर चर्चा करते हैं।
क्या आप क्लॉक के चयन को कॉन्फ्लिक्ट रिज़ॉल्यूशन या ट्रेस विश्लेषण जैसी किसी ठोस आवश्यकता से जोड़ते हैं।

उत्तर देने से पहले स्पष्टीकरण

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

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

“happened-before को लोकल प्रोग्राम ऑर्डर प्लस सेंड-बिफोर-रिसीव के रूप में परिभाषित करें, जो सकर्मक रूप से संवृत (transitively closed) हो। एक Lamport clock प्रत्येक लोकल या सेंड इवेंट से पहले बढ़ती है; रिसीव पर यह max(local, received) + 1 सेट करती है। यह causality को सुरक्षित रखता है, इसलिए a -> b का तात्पर्य L(a) < L(b) है, लेकिन एक छोटा स्केलर असंबंधित समवर्ती घटनाओं से भी आ सकता है। एक vector clock प्रति प्रोसेस एक काउंटर स्टोर करती है, अपनी स्वयं की एंट्री बढ़ाती है, और रिसीव पर घटक-वार अधिकतम (component-wise maximum) द्वारा मर्ज करती है। घटक-वार V(a) < V(b) का अर्थ causality है; अतुलनीय (incomparable) वैक्टर का अर्थ concurrency है। कॉम्पैक्ट डिटर्मिनिस्टिक ऑर्डर के लिए Lamport clocks का उपयोग करें और जब समवर्ती अपडेट्स में अंतर करना आवश्यक हो तो वैक्टर का उपयोग करें।”

चरण-दर-चरण गहन उत्तर

चरण 1: संबंध को परिभाषित करें।

a -> b लिखें जब a एक ही प्रोसेस में b से पहले आता है, a एक सेंड है और b इसका रिसीव है, या एक सकर्मक श्रृंखला उन्हें जोड़ती है। Wall-clock रीडिंग इस परिभाषा का हिस्सा नहीं हैं।

चरण 2: Lamport clock लागू करें।

text

onLocalOrSend:
  clock = clock + 1
  attach clock to an outgoing message when sending

onReceive(messageClock):
  clock = max(clock, messageClock) + 1
  process the message

एक डिटर्मिनिस्टिक टोटल ऑर्डर के लिए, (clock, processId) की तुलना करें। प्रोसेस आईडी एक टाई-ब्रेकर है; यह कोई कारणात्मक (causal) जानकारी नहीं जोड़ता है।

चरण 3: गारंटी और जवाबी उदाहरण बताएं।

यदि a -> b है, तो Lamport नियम L(a) < L(b) को लागू करते हैं। इसका विलोम विफल हो जाता है: दो स्वतंत्र प्रोसेस मान 4 और 7 के साथ इवेंट्स उत्पन्न कर सकते हैं, भले ही किसी भी इवेंट ने दूसरे को प्रभावित न किया हो। एक स्केलर यह नहीं बता सकता कि अंतर causality को दर्शाता है या असंबंधित स्थानीय कार्य को।

चरण 4: एक vector clock लागू करें।

text

onLocalOrSend:
  vector[me] = vector[me] + 1
  attach a copy of vector to the message

onReceive(remote):
  for each process p:
    vector[p] = max(vector[p], remote[p])
  vector[me] = vector[me] + 1

वैक्टर A और B के लिए, A <= B का अर्थ है कि A का प्रत्येक घटक B से बड़ा नहीं है; A < B को अतिरिक्त रूप से एक सख्त घटक की आवश्यकता होती है। A < B दर्शाता है A -> B। यदि कोई भी वेक्टर दूसरे से कम नहीं है, तो इवेंट्स दर्शाए गए प्रोसेस सेट के तहत समवर्ती हैं।

चरण 5: लागत और मेंबरशिप की तुलना करें।

Lamport मेटाडेटा एक स्केलर प्लस एक वैकल्पिक टाई-ब्रेकर है। Vector मेटाडेटा ट्रैक किए गए प्रोसेस सेट के समानुपाती होता है और प्रत्येक संदेश में बढ़ता है। डायनेमिक मेंबरशिप के लिए एक epoch, स्पार्स रिप्रेजेंटेशन, dotted version vectors, या किसी अन्य स्पष्ट नीति की आवश्यकता होती है; प्रोसेस आईडी का चुपचाप पुन: उपयोग करने से असंबंधित इतिहास मर्ज हो सकते हैं।

चरण 6: एक उपयोग का मामला चुनें।

एक लॉग व्यूअर के लिए जिसे केवल एक दोहराने योग्य क्रम की आवश्यकता होती है, Lamport टाइमस्टैम्प प्लस एक स्थिर टाई-ब्रेकर अक्सर पर्याप्त होते हैं। मल्टी-राइटर रेप्लिकेशन के लिए, वैक्टर का उपयोग तब करें जब समवर्ती राइट्स को अलग प्रस्तुति या डोमेन मर्ज की आवश्यकता हो। एक vector clock स्वयं टकराव (conflict) को हल नहीं करती है; यह साक्ष्य प्रदान करती है जिसे रिज़ॉल्वर को संभालना होता है।

चरण 7: विफलता और रिकवरी व्यवहार को परिभाषित करें।

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

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

“Happened-before स्थानीय क्रम, सेंड-बिफोर-रिसीव और ट्रांज़िटिविटी से प्राप्त आंशिक क्रम (partial order) है। Lamport clocks स्थानीय/सेंड इवेंट्स पर बढ़ती हैं और रिसीव पर max(local, received)+1 का उपयोग करती हैं। वे गारंटी देती हैं कि a -> b का अर्थ L(a) < L(b) है, लेकिन समान या क्रमित स्केलर मान यह साबित नहीं कर सकते कि दो इवेंट्स कारणात्मक रूप से संबंधित हैं। एक vector clock प्रेषक के घटक को बढ़ाती है और रिसीवर के घटक को बढ़ाने से पहले घटक-वार अधिकतम द्वारा वैक्टर को मर्ज करती है। यदि एक वेक्टर घटक-वार सख्ती से छोटा है, तो वह इवेंट दूसरे से पहले हुआ था; अतुलनीय वैक्टर समवर्ती हैं। मैं कॉम्पैक्ट डिटर्मिनिस्टिक ऑर्डरिंग के लिए Lamport clocks चुनता हूं, कॉन्फ्लिक्ट डिटेक्शन के लिए वैक्टर, और डिज़ाइन को पूरा मानने से पहले मैं वेक्टर मेटाडेटा प्लस एक मेंबरशिप/epoch नीति का बजट तय करता हूं।”

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

Wall-clock समय के अनुसार सॉर्ट करना → क्लॉक स्क्यू और विलंब causality को उलट सकते हैं → happened-before को स्पष्ट रूप से परिभाषित करें।
यह दावा करना कि L(a) < L(b) साबित करता है a -> b → स्केलर घड़ियाँ केवल एकतरफा निहितार्थ प्रदान करती हैं → समवर्ती प्रति-उदाहरण दें।
रिसीव इंक्रीमेंट भूल जाना → बाद की स्थानीय घटनाएं संदेश से पुरानी दिखाई दे सकती हैं → प्रोसेसिंग से पहले max + 1 लागू करें।
जोड़ द्वारा वैक्टर को मर्ज करना → काउंटर ज्ञान का प्रतिनिधित्व करते हैं, जोड़ने के लिए मात्रा का नहीं → घटक-वार अधिकतम लें।
लेक्सिकोग्राफ़िक रूप से वैक्टर की तुलना करना → लेक्सिकोग्राफ़िक क्रम concurrency को छुपाता है → घटक-वार तुलना का उपयोग करें।
एक vector clock को कॉन्फ्लिक्ट रिज़ॉल्यूशन के रूप में मानना → यह concurrency का पता लगाती है लेकिन डोमेन शब्दार्थ नहीं चुन सकती → एक मर्ज या उपयोगकर्ता निर्णय को परिभाषित करें।
मेंबरशिप और रीस्टार्ट को अनदेखा करना → पुन: उपयोग की गई आईडी इतिहासों को मिला सकती हैं → epochs या एक स्पष्ट मेंबरशिप नीति का उपयोग करें।

अनुवर्ती प्रश्न और उत्तर

अनुवर्ती 1: क्या Lamport clocks concurrency का पता लगा सकती हैं?

नहीं। वे यह साबित कर सकती हैं कि एक घटना दूसरी से पहले होती है जब स्केलर क्रम एक ज्ञात कारणात्मक पथ से प्राप्त होता है, लेकिन स्केलर मानों की एक क्रमित जोड़ी असंबंधित प्रक्रियाओं से भी संबंधित हो सकती है।

अनुवर्ती 2: Lamport टाइमस्टैम्प में प्रोसेस आईडी क्यों जोड़ें?

आईडी एक डिटर्मिनिस्टिक टोटल ऑर्डर उत्पन्न करने के लिए टाई को तोड़ती है। यह कारणात्मक ज्ञान में सुधार नहीं करती है और इसे vector-clock के विकल्प के रूप में प्रस्तुत नहीं किया जाना चाहिए।

अनुवर्ती 3: एक अतुलनीय (incomparable) वेक्टर का क्या अर्थ है?

ट्रैक किए गए प्रोसेस सेट के भीतर किसी भी घटना का दूसरे पर प्रभाव नहीं माना जाता है, इसलिए वे समवर्ती हैं। एप्लिकेशन अभी भी यह तय करता है कि मर्ज करना है, दोनों को बनाए रखना है, या किसी एक को अस्वीकार करना है।

अनुवर्ती 4: जब कोई संदेश डुप्लिकेट हो जाता है तो क्या होता है?

रिसीवर घटक-वार अधिकतम लेता है, इसलिए उसी वेक्टर को दोबारा चलाने से ज्ञान कम नहीं होता है। एप्लिकेशन को अभी भी इडेम्पोटेंट साइड इफेक्ट्स के लिए संदेश आईडी की आवश्यकता हो सकती है।

अनुवर्ती 5: आप वेक्टर मेटाडेटा को कैसे सीमित करते हैं?

सक्रिय सदस्यों को ट्रैक करें, स्पार्स या डॉटेड अभ्यावेदन का उपयोग करें, या दस्तावेजी सन्निकटन के साथ गारंटी को कमजोर करें। एक निश्चित सीमा जो चुपचाप सदस्यों को हटा देती है, गलत concurrency या गलत ordering उत्पन्न कर सकती है।

अनुवर्ती 6: क्या सिंक्रोनाइज़्ड भौतिक घड़ियाँ तार्किक घड़ियों (logical clocks) को अनावश्यक बनाती हैं?

नहीं। सिंक्रोनाइज़ेशन में त्रुटि सीमाएं और विफलताएं होती हैं; भौतिक टाइमस्टैम्प प्रदर्शन और प्रतिधारण में मदद कर सकते हैं, जबकि तार्किक घड़ियाँ संदेश-व्युत्पन्न causality को एनकोड करती हैं।

अनुवर्ती 7: आप कार्यान्वयन का परीक्षण कैसे करेंगे?

लोकल, सेंड, रिसीव, विलंबित, डुप्लिकेट और समवर्ती घटनाओं के साथ निशान (traces) उत्पन्न करें। पुष्टि करें कि प्रत्येक ज्ञात happened-before एज क्रमित है, प्रत्येक वेक्टर मर्ज मोनोटोनिक है, और जानबूझकर समवर्ती जोड़े अतुलनीय बने रहते हैं।

डिस्ट्रिब्यूटेड-सिस्टम्स इंटरव्यू: Lamport clocks कब विफल होते हैं, और आपको vector clocks की आवश्यकता कब होती है?

प्रश्न