👨🏾‍⚕️ 👩🏿‍🤝‍👩🏼 👦🏿 बॉक्स के बिना श्रोडिंगर बिल्ली: वितरित प्रणालियों में आम सहमति की समस्या 👃🏾 👩🏾‍✈️ 🤸🏽

तो, कल्पना कीजिए। 5 बिल्लियों को कमरे में बंद कर दिया जाता है, और मालिक को जगाने के लिए, उन्हें सभी को एक साथ इस पर सहमत होने की आवश्यकता होती है, क्योंकि वे उनमें से केवल पांच पर झुककर ही दरवाजा खोल सकते हैं। यदि बिल्लियों में से एक श्रोडिंगर बिल्ली है, और बाकी बिल्लियों को इसके समाधान के बारे में नहीं पता है, तो सवाल उठता है: "वे ऐसा कैसे कर सकते हैं?"

इस लेख में, मैं आपको एक सरल भाषा में वितरित प्रणालियों की दुनिया के सैद्धांतिक घटक और उनके संचालन के सिद्धांतों के बारे में बताऊंगा। और सतही तौर पर पैक्सोस के अंतर्निहित मुख्य विचार पर भी विचार करें।

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

वास्तव में, हमारे पास जो गारंटी है वह आपूर्तिकर्ता की गारंटी है। उन्हें दस्तावेज़ीकरण में लगभग निम्नलिखित तरीके से वर्णित किया गया है: "यह सेवा काफी विश्वसनीय है, इसमें एक पूर्वनिर्धारित SLA है, चिंता न करें, सब कुछ वितरित तरीके से काम करेगा, जैसा कि आप उम्मीद करेंगे।"

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

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

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

आगे क्या चर्चा की जाएगी इसका हल्का चित्रण: दो जनरलों का कार्य

आइए दो जनरलों के कार्य को गर्म करने के लिए देखें।

हमारी दो सेनाएँ हैं - लाल और सफेद। सफेद सैनिक बगल के शहर में स्थित हैं। जनरलों A1 और A2 के नेतृत्व में लाल सेना शहर के दो किनारों पर स्थित है। रेडहेड्स का काम सफेद शहर पर हमला करना और जीतना है। हालाँकि, व्यक्तिगत रूप से प्रत्येक लाल सिर वाले सेना की सेना गोरों की सेना से छोटी होती है।

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

सहमत होने के लिए, जनरल ए 1 और ए 2 सफेद शहर के क्षेत्र के माध्यम से एक-दूसरे को दूत भेज सकते हैं। एक संदेशवाहक सफलतापूर्वक एक संबद्ध जनरल को मिल सकता है या एक विरोधी द्वारा इंटरसेप्ट किया जा सकता है। प्रश्न: क्या लाल जनरलों (A1 से A2 तक संदेशवाहक भेजने और A2 से A1 के विपरीत) भेजने का क्रम है, जिसमें उन्हें घंटे X पर एक हमले पर सहमत होने की गारंटी है। यहाँ, गारंटी के तहत यह समझा जाता है कि दोनों जनरलों में असमानता की पुष्टि होगी एक सहयोगी (एक अन्य सामान्य) नियत समय X पर सटीक हमला करता है।

मान लीजिए कि A1 संदेश के साथ A2 को संदेशवाहक भेजता है: "चलो आज आधी रात को हमला करते हैं!" जनरल A2 जनरल A2 से पुष्टि किए बिना हमला नहीं कर सकता। यदि संदेशवाहक A1 तक पहुँच गया है, तो General A2 संदेश के साथ एक पुष्टिकरण भेजता है: "हाँ, चलो आज गोरों को भरें।" लेकिन अब, जनरल ए 2 को नहीं पता है कि उसका दूत आ गया है या नहीं, उसके पास इस बात की कोई गारंटी नहीं है कि हमला एक साथ होगा या नहीं। अब जनरल ए 2 को फिर से पुष्टि की जरूरत है।

यदि हम उनके संचार को और समयबद्ध करते हैं, तो यह निम्नलिखित है: चाहे कितने भी संदेशवाहक चक्र हों, दोनों जनरलों को सूचित करने का कोई तरीका नहीं है कि उनके संदेश प्राप्त हुए हैं (बशर्ते कि किसी भी संदेशवाहक को रोका जा सके)।

दो जनरलों का कार्य एक बहुत ही सरल वितरित प्रणाली का एक उत्कृष्ट चित्रण है जहां अविश्वसनीय संचार के साथ दो नोड हैं। इसलिए हमारे पास 100% गारंटी नहीं है कि वे सिंक्रनाइज़ हैं। लेख में बाद में बड़े पैमाने पर समान समस्याओं के बारे में।

हम वितरित प्रणालियों की अवधारणा का परिचय देते हैं

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

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

परिभाषा स्वयं बहुत जटिल नहीं लगती है, लेकिन आपको यह विचार करने की आवश्यकता है कि एक वितरित प्रणाली में कई विशेषताएं हैं जो हमारे लिए महत्वपूर्ण होंगी।

वितरित प्रणाली विशेषताएँ

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

वितरित प्रणालियों में नोड्स के बीच संचार मॉडल

सिंक्रोनस मॉडल - हम यह सुनिश्चित करने के लिए जानते हैं कि एक परिमित ज्ञात समय डेल्टा है जिसके लिए एक संदेश को एक नोड से दूसरे तक पहुंचने की गारंटी है। यदि यह समय बीत चुका है, लेकिन संदेश नहीं आया है, तो हम सुरक्षित रूप से कह सकते हैं कि नोड विफल हो गया है। ऐसे मॉडल में, हमारे पास एक पूर्वानुमानित प्रतीक्षा समय होता है।

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

वितरित प्रणालियों में आम सहमति की अवधारणा

औपचारिक रूप से आम सहमति की अवधारणा को परिभाषित करने से पहले, हमें उस स्थिति का एक उदाहरण पर विचार करना चाहिए जब हमें इसकी आवश्यकता होती है, अर्थात्, स्टेट मशीन प्रतिकृति ।

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

दूसरे शब्दों में: किसी भी नोड ने इस बात पर आपत्ति नहीं की कि इसकी अधिक प्रासंगिक जानकारी है, और प्रस्तावित मूल्य गलत है। नोड्स और एकल सही मूल्य पर समझौते के बीच समझौता एक वितरित प्रणाली में आम सहमति है। इसके अलावा हम एल्गोरिदम के बारे में बात करेंगे जो एक वितरित प्रणाली को गारंटी के साथ आम सहमति प्राप्त करने की अनुमति देते हैं।

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

सर्वसम्मति एल्गोरिथ्म गुण

सर्वसम्मति एल्गोरिथ्म में तीन गुण होने चाहिए ताकि प्रणाली का अस्तित्व बना रहे और राज्य से राज्य में संक्रमण में किसी प्रकार की प्रगति हो:

समझौता - सभी सही ढंग से काम करने वाले नोड्स को समान मूल्य लेना चाहिए (लेखों में इस संपत्ति को सुरक्षा संपत्ति के रूप में भी पाया जाता है)। सभी नोड्स जो अब कार्य कर रहे हैं (आदेश से बाहर नहीं हैं और बाकी के साथ संपर्क नहीं खो चुके हैं) को एक समझौते पर आना चाहिए और किसी तरह का अंतिम सामान्य अर्थ लेना चाहिए।

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

सर्वसम्मति एल्गोरिथ्म उदाहरण

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

यह सब एक शादी के प्रस्ताव (प्रस्ताव) के साथ शुरू होता है। मान लीजिए कि "नोड 1" नामक एक नोड से जुड़ा एक ग्राहक और एक लेनदेन शुरू किया, नोड के लिए एक नया मूल्य पारित - ओ। अब से, "नोड 1" हम प्रस्तावक कहेंगे। एक प्रस्तावक के रूप में, "नोड 1" को अब पूरे सिस्टम को सूचित करना चाहिए कि इसमें ताज़ा डेटा है, और यह अन्य सभी नोड्स को संदेश भेजेगा: "देखो! मुझे मान "O" मिला और मैं इसे लिखना चाहता हूं! कृपया पुष्टि करें कि आप अपने लॉग में "O" भी लिखेंगे।
अगला चरण प्रस्तावित मूल्य (मतदान) के लिए मतदान है। इसके लिए क्या है? ऐसा हो सकता है कि अन्य नोड्स को हाल ही में अधिक जानकारी प्राप्त हुई हो, और उनके पास समान लेनदेन पर डेटा हो।

जब नोड "नोड 1" अपना संदेश भेजता है, तो शेष नोड्स अपने लॉग में इस घटना के लिए डेटा की जांच करते हैं। यदि कोई विरोधाभास नहीं हैं, तो नोड्स घोषणा करते हैं: “हां, मेरे पास इस घटना का कोई अन्य डेटा नहीं है। मान "O" नवीनतम जानकारी है जिसके हम हकदार हैं। "

किसी भी अन्य मामले में, नोड्स "नोड 1" का जवाब दे सकते हैं: "सुनो! मेरे पास इस लेन-देन का हालिया डेटा है। नहीं "ओह," लेकिन कुछ बेहतर।

मतदान के चरण में, नोड्स एक निर्णय पर आते हैं: या तो हर कोई एक ही मूल्य लेता है, या उनमें से एक के खिलाफ वोट करता है, यह दर्शाता है कि उसके पास अधिक हालिया डेटा है।
यदि मतदान का दौर सफल रहा, और हर कोई इसके पक्ष में था, तो सिस्टम एक नए चरण में चला जाता है - मूल्य की स्वीकृति (स्वीकार)। "नोड 1" अन्य नोड्स और रिपोर्टों की सभी प्रतिक्रियाओं को एकत्र करता है: "हर कोई मूल्य" ओ "से सहमत है! अब मैं आधिकारिक तौर पर घोषणा करता हूं कि "ओ" हमारा नया अर्थ है, सभी के लिए समान है! अपने आप को एक पुस्तिका में लिखें, मत भूलना। अपने लॉग में लिखें! ”
शेष नोड्स एक पुष्टिकरण (स्वीकृत) भेजते हैं कि उन्होंने मूल्य "ओ" लिखा है, इस समय के दौरान कुछ भी नया करने का प्रबंधन नहीं किया था (एक प्रकार की दो चरण की प्रतिबद्धता)। इस महत्वपूर्ण घटना के बाद, हम मानते हैं कि वितरित लेनदेन पूरा हो गया है।

इस प्रकार, साधारण मामले में सर्वसम्मति एल्गोरिथ्म में चार चरण होते हैं: प्रस्ताव, मतदान, स्वीकृति, स्वीकृति की पुष्टि।

यदि कुछ कदम पर हम समझौते पर नहीं पहुंच सकते हैं, तो प्रस्तावित मूल्य की पुष्टि करने से इनकार करने वाले नोड्स द्वारा प्रदान की गई जानकारी को ध्यान में रखते हुए एल्गोरिथ्म को फिर से शुरू किया जाता है।

एक अतुल्यकालिक प्रणाली में आम सहमति

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

अब जब हम जानते हैं कि सर्वसम्मति एल्गोरिथ्म मूल रूप से कैसे काम करता है, तो सवाल उन जिज्ञासु पाठकों के लिए है जो इस बिंदु पर पहुंच चुके हैं: एक अतुल्यकालिक संदेश मॉडल के साथ एन नोड्स की प्रणाली में कितने नोड विफल हो सकते हैं ताकि सिस्टम अभी भी आम सहमति तक पहुंच सके?

सही उत्तर और बिगाड़ने के पीछे तर्क।

सही उत्तर 0 है । यदि एसिंक्रोनस सिस्टम में कम से कम एक नोड विफल हो जाता है, तो सिस्टम आम सहमति तक नहीं पहुंच सकता है। एफएलपी प्रमेय में ज्ञात कुछ हलकों (1985, फिशर, लिंच, पैटर्सन, लेख के अंत में मूल से लिंक) में यह दावा साबित होता है: "कम से कम एक नोड के विफल होने पर वितरित आम सहमति प्राप्त करने में असमर्थता"।

दोस्तों, फिर हमारे पास एक समस्या है, हम इस तथ्य के लिए उपयोग किए जाते हैं कि सब कुछ हमारे साथ अतुल्यकालिक है। और यहाँ यह है। आगे कैसे जीना है?

हम अब सिद्धांत के बारे में, गणित के बारे में बात कर रहे हैं। इसका क्या मतलब है "आम सहमति तक नहीं पहुँचा जा सकता", एक गणितीय भाषा से हमारे में अनुवाद - इंजीनियरिंग? इसका मतलब है कि "हमेशा प्राप्त नहीं किया जा सकता है", अर्थात ऐसा मामला है जहां सर्वसम्मति प्राप्त नहीं है। और यह मामला क्या है?

यह केवल ऊपर वर्णित लीवर संपत्ति का उल्लंघन है। जब हम सभी नोड्स से उत्तर नहीं देते हैं, तो हमारे पास एक सामान्य समझौता नहीं होता है, और सिस्टम प्रगति नहीं कर सकता है (एक सीमित समय में पूरा नहीं हो सकता है)। क्योंकि एक एसिंक्रोनस सिस्टम में हमारे पास प्रेडिक्टेबल रिस्पांस टाइम नहीं होता है, और हमें पता नहीं चलता है कि क्या नोड डाउन है या जवाब देने में लंबा समय लगता है।

लेकिन व्यवहार में, हम एक समाधान पा सकते हैं। विफलताओं के मामले में हमारे एल्गोरिथ्म को लंबे समय तक काम करने दें (यह संभवतः अंतहीन काम कर सकता है)। लेकिन ज्यादातर स्थितियों में, जब अधिकांश नोड सही ढंग से कार्य करते हैं, तो हमारे पास सिस्टम में प्रगति होगी।

व्यवहार में, हम आंशिक रूप से तुल्यकालिक संचार मॉडल के साथ काम कर रहे हैं। आंशिक समकालिकता को निम्नानुसार समझा जाता है: सामान्य मामले में, हमारे पास एक अतुल्यकालिक मॉडल है, लेकिन औपचारिक रूप से हम समय में एक निश्चित समय के "वैश्विक स्थिरीकरण समय" की एक निश्चित अवधारणा को पेश करते हैं।

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

पैक्सोस एलगोरिदम सोल्वेस सर्वसम्मति मुद्दे

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

लेकिन सबूत किसी भी तरह से तुच्छ नहीं था। पहला प्रकाशन केवल एल्गोरिदम के विवरण के साथ 1998 (33 पृष्ठों) में जारी किया गया था। जैसा कि यह निकला, यह समझना बहुत मुश्किल था, और 2001 में लेख के लिए एक स्पष्टीकरण प्रकाशित किया गया था, जिसमें 14 पृष्ठ थे। प्रकाशनों के संस्करणों को यह दिखाने के लिए दिया जाता है कि वास्तव में, सर्वसम्मति की समस्या बिल्कुल सरल नहीं है, और इस तरह के एल्गोरिदम सबसे चतुर लोगों के विशाल कार्य के अधीन हैं।

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

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

पाक्सोस में भूमिकाएँ

पाक्सोस में भूमिकाओं की अवधारणा है। आइए तीन मुख्य बातों पर विचार करें (अतिरिक्त भूमिकाओं के साथ संशोधन हैं):

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

एक नोड विभिन्न स्थितियों में कई भूमिकाओं को जोड़ सकता है।

कोरम की अवधारणा

हम मानते हैं कि हमारे पास एन नोड्स की एक प्रणाली है। और उनमें से अधिकतम F नोड्स विफल हो सकते हैं। यदि F नोड्स विफल होते हैं, तो हमारे पास क्लस्टर में कम से कम 2F + 1 स्वीकर्ता नोड होना चाहिए।

यह आवश्यक है ताकि हम हमेशा, यहां तक कि सबसे खराब स्थिति में भी, एक "अच्छा" हो, सही ढंग से काम कर रहे नोड्स बहुमत। यही है, एफ + 1 "अच्छा" नोड्स जो सहमत हैं, और अंतिम मूल्य स्वीकार किया जाएगा। अन्यथा, ऐसी स्थिति हो सकती है जहां विभिन्न स्थानीय समूह अलग-अलग अर्थ ग्रहण करेंगे और आपस में सहमत नहीं हो पाएंगे। इसलिए हमें वोट जीतने के लिए पूर्ण बहुमत चाहिए।

पैक्सोस सर्वसम्मति एल्गोरिथ्म का सामान्य विचार

पैक्सोस एल्गोरिथ्म में दो बड़े चरण शामिल हैं, जो बदले में प्रत्येक में दो चरणों में विभाजित हैं:

चरण 1 ए: तैयार करें । तैयारी के चरण में, नेता (प्रस्तावक) सभी नोड्स को सूचित करता है: “हम एक नया मतदान चरण शुरू कर रहे हैं। हमारे पास एक नया दौर है। इस दौर की संख्या n है। अब हम मतदान करना शुरू करेंगे। ” अभी के लिए, यह केवल एक नए चक्र की शुरुआत की रिपोर्ट करता है, लेकिन एक नए मूल्य की रिपोर्ट नहीं करता है। इस चरण का कार्य एक नया दौर आरंभ करना और सभी को इसकी विशिष्ट संख्या बताना है। राउंड नंबर महत्वपूर्ण है, यह पिछले सभी नेताओं के सभी वोटिंग नंबरों से अधिक मूल्य होना चाहिए। चूंकि यह ठीक गोल संख्या के लिए धन्यवाद है कि सिस्टम में अन्य नोड्स समझेंगे कि नेता के पास डेटा कितना ताज़ा है। अन्य नोड्स में पहले से ही बहुत बाद के दौर से मतदान के परिणाम हैं और वे बस नेता को बताएंगे कि वह समय के पीछे है।
चरण 1 बी: वादा । जब स्वीकर्ता नोड्स को नए मतदान चरण की संख्या प्राप्त हुई, तो दो परिणाम संभव हैं:
- n , , acceptor. acceptor , , n. acceptor - (.. - ), , .
- , acceptor , .
Phase 2a: Accept . ( ) , , :
- acceptor' , . c . x, : «Accept (n, x)», – Propose, – , .. , , .
- acceptor' , , , , . y. : «Accept (n, y)», .
Phase 2b: Accepted . , -acceptor', «Accept(...)», ( , ) , - () n' > n , .

, , . ! , , .

Paxos. , , , .

, Paxos — , , , Raft , .

«»:

How Does Distributed Consensus Works? , Preethi Kasireddy, blog article on Medium
Paxos made simple. For real , Adi Kancherla, blog article on Medium
Decentralized Thoughts , Ittai Abraham, blog
समकालिकता, अतुल्यकालिक और आंशिक समकालिकता , इत्तई अब्राहम, ब्लॉग लेख

लेस्ली लामटेक स्तर:

एक दोषपूर्ण प्रक्रिया (FLP असंभव) , फिशर, लिंच और पैटरसन, अनुसंधान पत्र, 1985 के साथ वितरित सहमति की संभावना
द पार्ट-टाइम पार्लियामेंट , लेस्ली लामपोर्ट, रिसर्च पेपर, 1998
पैक्सोस ने सरल , लेस्ली लामपोर्ट, शोध पत्र, 2001 बनाया

बॉक्स के बिना श्रोडिंगर बिल्ली: वितरित प्रणालियों में आम सहमति की समस्या