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

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

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

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

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

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

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

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

आगे क्या चर्चा की जाएगी इसका एक हल्का चित्रण: दो जनरलों का कार्यआइए वार्म-अप पर एक नज़र डालें दो जनरलों का कार्य.

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

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

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

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

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

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

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

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

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

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

वितरित प्रणालियों के गुण

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

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

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

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

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

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

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

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

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

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

सिस्टम के अस्तित्व को जारी रखने और एक राज्य से दूसरे राज्य में जाने में कुछ प्रगति के लिए सर्वसम्मति एल्गोरिदम में तीन गुण होने चाहिए:

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

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

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

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

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

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

   

2. अगला चरण प्रस्तावित मूल्य के लिए मतदान (वोटिंग) है। यह किस लिए है? ऐसा हो सकता है कि अन्य नोड्स को अधिक हालिया जानकारी प्राप्त हुई हो, और उनके पास उसी लेनदेन पर डेटा हो।

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

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

   मतदान के चरण में, नोड्स एक निर्णय पर आते हैं: या तो वे सभी समान मूल्य स्वीकार करते हैं, या उनमें से एक इसके खिलाफ वोट करता है, यह दर्शाता है कि उसके पास अधिक हालिया डेटा है।

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

   

4. शेष नोड्स पुष्टिकरण (स्वीकृत) भेजते हैं कि उन्होंने "O" मान लिख लिया है; इस दौरान कुछ भी नया नहीं आया है (एक प्रकार की दो-चरण प्रतिबद्धता)। इस महत्वपूर्ण घटना के बाद, हम मानते हैं कि वितरित लेनदेन पूरा हो गया है।
   

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

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

एक अतुल्यकालिक प्रणाली में सर्वसम्मति एल्गोरिथ्म

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

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

स्पॉइलर के पीछे सही उत्तर और औचित्य है।सही उत्तर है: 0. यदि एसिंक्रोनस सिस्टम में एक भी नोड विफल हो जाता है, तो सिस्टम आम सहमति तक पहुंचने में सक्षम नहीं होगा। यह कथन एफएलपी प्रमेय में सिद्ध है, जो कुछ हलकों में प्रसिद्ध है (1985, फिशर, लिंच, पैटरसन, लेख के अंत में मूल से लिंक): "यदि कम से कम एक नोड विफल हो जाता है तो वितरित सर्वसम्मति प्राप्त करने की असंभवता ।”

दोस्तों, फिर हमारे पास एक समस्या है, हम हर चीज के अतुल्यकालिक होने के आदी हैं। और यह यहाँ है. कैसे जीना जारी रखें?

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

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

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

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

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

पैक्सोस एल्गोरिथ्म सर्वसम्मति की समस्याओं को हल करता है

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

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

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

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

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

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

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

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

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

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

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

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

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

1. चरण 1ए: तैयारी करें. तैयारी चरण के दौरान, नेता (प्रस्तावक) सभी नोड्स को सूचित करता है: “हम एक नया मतदान चरण शुरू कर रहे हैं। हमारे पास एक नया दौर है. इस राउंड की संख्या n है. अब हम मतदान शुरू करेंगे।” अभी के लिए, यह केवल एक नए चक्र की शुरुआत की रिपोर्ट करता है, लेकिन एक नए मूल्य की रिपोर्ट नहीं करता है। इस चरण का कार्य एक नए दौर की शुरुआत करना और सभी को उसके विशिष्ट नंबर से अवगत कराना है। राउंड नंबर महत्वपूर्ण है, इसका मूल्य पिछले सभी नेताओं के सभी वोटिंग नंबरों से अधिक होना चाहिए। क्योंकि यह राउंड नंबर के लिए धन्यवाद है कि सिस्टम में अन्य नोड्स समझेंगे कि नेता का डेटा कितना ताज़ा है। यह संभव है कि अन्य नोड्स के पास पहले से ही बहुत बाद के दौर के मतदान परिणाम हों और वे नेता को बस यह बता देंगे कि वह समय से पीछे है।
2. चरण 1बी: वादा. जब स्वीकर्ता नोड्स को नए मतदान चरण की संख्या प्राप्त होती है, तो दो परिणाम संभव होते हैं:
   • नए वोट की संख्या n किसी भी पिछले वोट की संख्या से अधिक है जिसमें स्वीकारकर्ता ने भाग लिया था। फिर स्वीकारकर्ता नेता को एक वादा भेजता है कि वह n से कम संख्या वाले किसी भी अधिक वोट में भाग नहीं लेगा। यदि स्वीकारकर्ता ने पहले ही किसी चीज़ के लिए मतदान कर दिया है (अर्थात, उसने पहले ही दूसरे चरण में कुछ मूल्य स्वीकार कर लिया है), तो वह स्वीकृत मूल्य और उस वोट की संख्या को अपने वादे से जोड़ देता है जिसमें उसने भाग लिया था।
   • अन्यथा, यदि स्वीकारकर्ता को पहले से ही अधिक संख्या वाले वोट के बारे में पता है, तो वह तैयारी के कदम को अनदेखा कर सकता है और नेता को जवाब नहीं दे सकता है।
3. चरण 2ए: स्वीकार करें. नेता को कोरम (सिस्टम में अधिकांश नोड्स) से प्रतिक्रिया की प्रतीक्षा करने की आवश्यकता होती है और, यदि आवश्यक संख्या में प्रतिक्रियाएँ प्राप्त होती हैं, तो उसके पास घटनाओं के विकास के लिए दो विकल्प होते हैं:
   • कुछ स्वीकारकर्ताओं ने वे मूल्य भेजे जिनके लिए वे पहले ही मतदान कर चुके थे। इस मामले में, नेता अधिकतम संख्या वाले वोट से मूल्य का चयन करता है। आइए इस मान को x पर कॉल करें, और यह सभी नोड्स को एक संदेश भेजता है जैसे: "स्वीकार करें (n, x)", जहां पहला मान अपने स्वयं के प्रस्ताव चरण से वोटिंग संख्या है, और दूसरा मान वह है जिसके लिए सभी एकत्र हुए थे, अर्थात। वह मूल्य जिसके लिए हम वास्तव में वोट देते हैं।
   • यदि किसी भी स्वीकारकर्ता ने कोई मूल्य नहीं भेजा है, लेकिन उन्होंने इस दौर में वोट देने का वादा किया है, तो नेता उन्हें उनके मूल्य के लिए वोट करने के लिए आमंत्रित कर सकता है, वह मूल्य जिसके लिए वह पहले स्थान पर नेता बना था। चलिए इसे y कहते हैं। यह सभी नोड्स को एक संदेश भेजता है जैसे: "स्वीकार करें (एन, वाई)", पिछले परिणाम के समान।
4. चरण 2बी: स्वीकृत. इसके अलावा, स्वीकर्ता नोड्स, नेता से "स्वीकार करें(...)" संदेश प्राप्त करने पर, इससे सहमत होते हैं (सभी नोड्स को पुष्टि भेजते हैं कि वे नए मूल्य से सहमत हैं) केवल अगर उन्होंने कुछ (अन्य) का वादा नहीं किया है) नेता को राउंड नंबर के साथ मतदान में भाग लेना होगा एन' > एन, अन्यथा वे पुष्टिकरण अनुरोध को अनदेखा कर देते हैं।

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

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

यह भी ध्यान देने योग्य है कि पैक्सोस अपनी तरह का एकमात्र एल्गोरिदम नहीं है, उदाहरण के लिए, अन्य एल्गोरिदम भी हैं, बेड़ा, लेकिन यह एक अन्य लेख का विषय है।

आगे के अध्ययन के लिए सामग्री के लिंक

शुरुआती स्तर:

• वितरित आम सहमति कैसे काम करती है?, प्रीति कासिरेड्डी, मीडियम पर ब्लॉग लेख
• पैक्सोस को सरल बनाया गया। वास्तव में, आदि कंचेरला, मीडियम पर ब्लॉग लेख
• विकेंद्रीकृत विचार, इत्तई अब्राहम, ब्लॉग
• समकालिक, अतुल्यकालिक और आंशिक समकालिक, इत्तई अब्राहम, ब्लॉग लेख

लेस्ली लामपोर्ट स्तर:

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

स्रोत: www.habr.com