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

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

या लेखात, मी तुम्हाला वितरित प्रणालींच्या जगाचा सैद्धांतिक घटक आणि त्यांच्या ऑपरेशनच्या तत्त्वांबद्दल सोप्या भाषेत सांगेन. मी पॉक्सोसच्या अंतर्निहित मुख्य कल्पनेचे वरवरचे परीक्षण करेन.

जेव्हा डेव्हलपर क्लाउड इन्फ्रास्ट्रक्चर्स, विविध डेटाबेसेस वापरतात आणि मोठ्या संख्येने नोड्सच्या क्लस्टरमध्ये काम करतात तेव्हा त्यांना खात्री असते की डेटा पूर्ण, सुरक्षित आणि नेहमी उपलब्ध असेल. पण हमीभाव कुठे आहेत?

मूलत:, आमच्याकडे असलेल्या हमी पुरवठादार हमी आहेत. त्यांचे वर्णन दस्तऐवजीकरणात खालीलप्रमाणे केले आहे: "ही सेवा बर्‍यापैकी विश्वासार्ह आहे, तिला दिलेला SLA आहे, काळजी करू नका, सर्व काही तुमच्या अपेक्षेप्रमाणे वितरित केले जाईल."

आम्ही सर्वोत्कृष्ट गोष्टींवर विश्वास ठेवतो, कारण मोठ्या कंपन्यांच्या हुशार लोकांनी आम्हाला आश्वासन दिले की सर्व काही ठीक होईल. आम्ही प्रश्न विचारत नाही: खरं तर, हे अजिबात का काम करू शकते? अशा प्रणालींच्या योग्य कार्यासाठी कोणतेही औपचारिक औचित्य आहे का?

मी अलीकडे गेलो होतो स्कूल ऑफ डिस्ट्रिब्युटेड कॉम्प्युटिंग आणि या विषयावरून खूप प्रेरित झाले. शाळेतील व्याख्याने संगणक प्रणालीशी संबंधित असलेल्या गोष्टींपेक्षा कॅल्क्युलस क्लाससारखे होते. पण आपण दररोज वापरत असलेले सर्वात महत्त्वाचे अल्गोरिदम, अगदी नकळत हे एका वेळी कसे सिद्ध झाले.

बहुतेक आधुनिक वितरण प्रणाली पॅक्सोस कन्सेन्सस अल्गोरिदम आणि त्यातील विविध बदल वापरतात. सर्वात छान गोष्ट अशी आहे की या अल्गोरिदमची वैधता आणि तत्त्वतः अस्तित्वाची शक्यता पेन आणि कागदाच्या सहाय्याने सिद्ध केली जाऊ शकते. सराव मध्ये, अल्गोरिदम ढगांमध्ये मोठ्या संख्येने नोड्सवर चालणार्‍या मोठ्या प्रणालींमध्ये वापरला जातो.

पुढे काय चर्चा केली जाईल याचे हलके चित्र: दोन सेनापतींचे कार्यचला वॉर्म-अपसाठी एक नजर टाकूया दोन सेनापतींचे कार्य.

आमच्याकडे दोन सैन्य आहेत - लाल आणि पांढरा. पांढऱ्या सैन्याने वेढा घातलेल्या शहरात स्थित आहेत. जनरल ए 1 आणि ए 2 च्या नेतृत्वाखालील लाल सैन्य शहराच्या दोन बाजूला आहेत. रेडहेड्सचे कार्य पांढर्या शहरावर हल्ला करणे आणि जिंकणे आहे. तथापि, प्रत्येक लाल सेनापतीचे सैन्य वैयक्तिकरित्या पांढऱ्या सैन्यापेक्षा लहान असते.

लाल लोकांसाठी विजयाची परिस्थिती: गोर्‍यांवर संख्यात्मक फायदा मिळवण्यासाठी दोन्ही सेनापतींनी एकाच वेळी हल्ला केला पाहिजे. हे करण्यासाठी, जनरल A1 आणि A2 एकमेकांशी करार करणे आवश्यक आहे. जर प्रत्येकाने स्वतंत्रपणे हल्ला केला तर रेडहेड्स गमावतील.

करारावर पोहोचण्यासाठी, जनरल A1 आणि A2 पांढर्या शहराच्या प्रदेशातून एकमेकांना संदेशवाहक पाठवू शकतात. मेसेंजर यशस्वीरित्या सहयोगी जनरलपर्यंत पोहोचू शकतो किंवा शत्रूने त्याला रोखले जाऊ शकते. प्रश्न: लाल-केस असलेल्या जनरल्समध्ये (A1 ते A2 आणि त्याउलट A2 ते A1 पर्यंत संदेशवाहक पाठवण्याचा क्रम) यांच्यात संवादाचा असा क्रम आहे का, ज्यामध्ये ते X वाजताच्या हल्ल्यावर सहमती दर्शवतात. येथे, हमींचा अर्थ असा आहे की दोन्ही सेनापतींना अस्पष्ट पुष्टी मिळेल की एक सहयोगी (दुसरा जनरल) निश्चितपणे नियुक्त वेळी एक्स वर हल्ला करेल.

समजा A1 ने A2 ला मेसेंजर पाठवला: "चला आज मध्यरात्री हल्ला करू!" जनरल A1 जनरल A2 च्या पुष्टीशिवाय हल्ला करू शकत नाही. जर A1 मधील मेसेंजर आला असेल, तर जनरल A2 संदेशासह पुष्टीकरण पाठवते: "होय, आज गोर्‍यांना मारू." पण आता जनरल A2 ला माहित नाही की त्याचा मेसेंजर आला आहे की नाही, तो हल्ला एकाच वेळी होईल की नाही याची शाश्वती नाही. आता जनरल A2 पुन्हा पुष्टीकरण आवश्यक आहे.

जर आपण त्यांच्या संप्रेषणाचे आणखी वर्णन केले तर हे स्पष्ट होते की कितीही संदेश विनिमय चक्र असले तरीही, दोन्ही जनरल्सना त्यांचे संदेश प्राप्त झाले आहेत याची हमी देण्याचा कोणताही मार्ग नाही (एकतर मेसेंजरला रोखले जाऊ शकते असे गृहीत धरून).

टू जनरल प्रॉब्लेम हे अतिशय सोप्या वितरण प्रणालीचे उत्कृष्ट उदाहरण आहे जेथे अविश्वसनीय संप्रेषणासह दोन नोड्स आहेत. याचा अर्थ आमच्याकडे 100% हमी नाही की ते समक्रमित आहेत. तत्सम समस्यांबद्दल लेखात नंतर मोठ्या प्रमाणावर चर्चा केली जाईल.

आम्ही वितरित प्रणालीची संकल्पना सादर करतो

डिस्ट्रिब्युटेड सिस्टीम म्हणजे संगणकांचा समूह (यापुढे आम्ही त्यांना नोड म्हणू) जे संदेशांची देवाणघेवाण करू शकतात. प्रत्येक वैयक्तिक नोड ही एक प्रकारची स्वायत्त संस्था असते. नोड स्वतःच कार्यांवर प्रक्रिया करू शकतो, परंतु इतर नोड्सशी संवाद साधण्यासाठी, त्याला संदेश पाठवणे आणि प्राप्त करणे आवश्यक आहे.

संदेश नेमके कसे अंमलात आणले जातात, कोणते प्रोटोकॉल वापरले जातात - हे या संदर्भात आम्हाला स्वारस्य नाही. हे महत्वाचे आहे की वितरित प्रणालीचे नोड्स संदेश पाठवून एकमेकांशी डेटाची देवाणघेवाण करू शकतात.

व्याख्या स्वतःच फार क्लिष्ट दिसत नाही, परंतु आपण हे लक्षात घेतले पाहिजे की वितरित प्रणालीमध्ये अनेक गुणधर्म आहेत जे आपल्यासाठी महत्त्वपूर्ण असतील.

वितरित प्रणालीचे गुणधर्म

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

वितरित प्रणालींमधील नोड्समधील संप्रेषणाचे मॉडेल

सिंक्रोनस मॉडेल - आम्हाला निश्चितपणे माहित आहे की एक मर्यादित ज्ञात डेल्टा आहे ज्या दरम्यान संदेश एका नोडमधून दुसर्‍या नोडपर्यंत पोहोचण्याची हमी दिली जाते. जर ही वेळ निघून गेली असेल आणि संदेश आला नसेल, तर आम्ही सुरक्षितपणे म्हणू शकतो की नोड अयशस्वी झाला आहे. या मॉडेलमध्ये आमच्याकडे अंदाजे प्रतीक्षा वेळा आहेत.

असिंक्रोनस मॉडेल - असिंक्रोनस मॉडेल्समध्ये आम्ही विचार करतो की प्रतीक्षा वेळ मर्यादित आहे, परंतु वेळेचा असा कोणताही डेल्टा नाही ज्यानंतर आम्ही हमी देऊ शकतो की नोड अयशस्वी झाला आहे. त्या. नोडमधून संदेशासाठी प्रतीक्षा वेळ अनियंत्रितपणे लांब असू शकतो. ही एक महत्त्वाची व्याख्या आहे आणि आम्ही त्याबद्दल पुढे बोलू.

वितरित प्रणालींमध्ये सहमतीची संकल्पना

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

आमच्याकडे काही वितरित लॉग आहेत. आम्हाला ते सुसंगत आणि वितरित प्रणालीच्या सर्व नोड्सवर एकसारखे डेटा असावे असे वाटते. जेव्हा नोड्सपैकी एकाला नवीन व्हॅल्यू कळते की ते लॉगवर लिहायचे आहे, तेव्हा त्याचे कार्य हे मूल्य इतर सर्व नोड्सना ऑफर करणे बनते जेणेकरून लॉग सर्व नोड्सवर अद्यतनित होईल आणि सिस्टम नवीन सुसंगत स्थितीत जाईल. या प्रकरणात, नोड्स आपापसात सहमत असणे महत्वाचे आहे: सर्व नोड्स सहमत आहेत की प्रस्तावित नवीन मूल्य योग्य आहे, सर्व नोड्स हे मूल्य स्वीकारतात आणि केवळ या प्रकरणात प्रत्येकजण लॉगवर नवीन मूल्य लिहू शकतो.

दुसऱ्या शब्दांत: कोणत्याही नोड्सने आक्षेप घेतला नाही की त्यात अधिक संबंधित माहिती आहे आणि प्रस्तावित मूल्य चुकीचे आहे. नोड्समधील करार आणि एकाच योग्य स्वीकृत मूल्यावरील करार म्हणजे वितरित प्रणालीमध्ये एकमत. पुढे, आम्ही अल्गोरिदमबद्दल बोलू जे वितरित सिस्टमला सहमती मिळण्याची हमी देतात.

अधिक औपचारिकपणे, आम्ही एक विशिष्ट कार्य म्हणून एक सहमती अल्गोरिदम (किंवा फक्त एक सहमती अल्गोरिदम) परिभाषित करू शकतो जे एक वितरित प्रणाली राज्य A मधून B मध्ये स्थानांतरित करते. शिवाय, ही स्थिती सर्व नोड्सद्वारे स्वीकारली जाते आणि सर्व नोड्स त्याची पुष्टी करू शकतात. हे दिसून येते की हे कार्य पहिल्या दृष्टीक्षेपात दिसते तितके क्षुल्लक नाही.

एकमत अल्गोरिदमचे गुणधर्म

एकमत अल्गोरिदममध्ये तीन गुणधर्म असणे आवश्यक आहे जेणेकरुन सिस्टम अस्तित्वात राहण्यासाठी आणि राज्यातून दुसर्‍या राज्यात जाण्यासाठी काही प्रगती करा:

1. करार - सर्व योग्यरित्या कार्यरत नोड्सने समान मूल्य घेतले पाहिजे (लेखांमध्ये या मालमत्तेला सुरक्षा मालमत्ता म्हणून देखील संबोधले जाते). सर्व नोड्स जे सध्या कार्यरत आहेत (अयशस्वी झाले नाहीत किंवा इतरांशी संपर्क तुटला नाही) त्यांनी करार केला पाहिजे आणि काही अंतिम सामान्य मूल्य स्वीकारले पाहिजे.

   येथे हे समजून घेणे महत्त्वाचे आहे की आम्ही विचार करत असलेल्या वितरित प्रणालीमधील नोड्स सहमत होऊ इच्छित आहेत. म्हणजेच, आम्ही आता अशा प्रणालींबद्दल बोलत आहोत ज्यामध्ये काहीतरी अयशस्वी होऊ शकते (उदाहरणार्थ, काही नोड अयशस्वी होतात), परंतु या प्रणालीमध्ये निश्चितपणे असे कोणतेही नोड्स नाहीत जे जाणूनबुजून इतरांविरुद्ध कार्य करतात (बायझेंटाईन जनरलचे कार्य). या गुणधर्मामुळे, प्रणाली सुसंगत राहते.

2. सचोटी — जर सर्व योग्यरित्या कार्यरत नोड्स समान मूल्य देतात v, ज्याचा अर्थ प्रत्येक योग्यरित्या कार्यरत नोडने हे मूल्य स्वीकारले पाहिजे v.
3. संपुष्टात आणले - सर्व योग्यरित्या कार्यरत नोड्स शेवटी एक विशिष्ट मूल्य (लाइव्हनेस प्रॉपर्टी) घेतील, जे अल्गोरिदमला सिस्टममध्ये प्रगती करण्यास अनुमती देते. प्रत्येक व्यक्तीने योग्यरीत्या कार्यरत नोडला लवकर किंवा नंतर अंतिम मूल्य स्वीकारले पाहिजे आणि त्याची पुष्टी केली पाहिजे: "माझ्यासाठी, हे मूल्य खरे आहे, मी संपूर्ण सिस्टमशी सहमत आहे."

एकमत अल्गोरिदम कसे कार्य करते याचे उदाहरण

अल्गोरिदमचे गुणधर्म पूर्णपणे स्पष्ट नसू शकतात. म्हणून, सिंक्रोनस मेसेजिंग मॉडेल असलेल्या सिस्टीममध्ये सर्वात सोपा कॉन्सेन्सस अल्गोरिदम कोणत्या टप्प्यांमधून जातो, ज्यामध्ये सर्व नोड अपेक्षेप्रमाणे कार्य करतात, संदेश गमावले जात नाहीत आणि काहीही खंडित होत नाही (हे खरोखर घडते का?) आम्ही उदाहरणासह स्पष्ट करू.

1. हे सर्व लग्नाच्या प्रस्तावाने (प्रपोज) सुरू होते. गृहीत धरू की क्लायंटने "नोड 1" नावाच्या नोडशी कनेक्ट केले आहे आणि नोड - O ला नवीन मूल्य देऊन व्यवहार सुरू केला आहे. आतापासून, आम्ही "नोड 1" म्हणू. ऑफर. एक प्रस्तावक म्हणून, “नोड 1” ने आता संपूर्ण सिस्टमला सूचित केले पाहिजे की त्याच्याकडे नवीन डेटा आहे आणि ते इतर सर्व नोड्सना संदेश पाठवते: “बघा! “O” चा अर्थ माझ्याकडे आला आणि मला तो लिहायचा आहे! कृपया खात्री करा की तुम्ही तुमच्या लॉगमध्ये “O” देखील रेकॉर्ड कराल.”

   

2. पुढील टप्पा म्हणजे प्रस्तावित मूल्यासाठी मतदान (मतदान). ते कशासाठी आहे? असे होऊ शकते की इतर नोड्सना अधिक अलीकडील माहिती प्राप्त झाली आहे आणि त्यांच्याकडे समान व्यवहाराचा डेटा आहे.

   
   
   जेव्हा नोड “नोड 1” त्याचा प्रस्ताव पाठवतो, तेव्हा इतर नोड्स या इव्हेंटवरील डेटासाठी त्यांचे लॉग तपासतात. कोणतेही विरोधाभास नसल्यास, नोड्स घोषित करतात: “होय, माझ्याकडे या कार्यक्रमासाठी इतर कोणताही डेटा नाही. “O” मूल्य ही आमच्यासाठी पात्र असलेली नवीनतम माहिती आहे.”

   इतर कोणत्याही परिस्थितीत, नोड्स “नोड 1” ला प्रतिसाद देऊ शकतात: “ऐका! माझ्याकडे या व्यवहारावरील अधिक अलीकडील डेटा आहे. 'ओ' नाही, पण काहीतरी चांगले."

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

3. जर मतदान फेरी यशस्वी झाली आणि प्रत्येकजण त्याच्या बाजूने असेल, तर सिस्टम नवीन टप्प्यावर जाईल - मूल्य स्वीकारणे. “नोड 1” इतर नोड्समधील सर्व प्रतिसाद गोळा करतो आणि अहवाल देतो: “प्रत्येकजण “O” मूल्यावर सहमत होता! आता मी अधिकृतपणे घोषित करतो की “O” हा आमचा नवीन अर्थ आहे, प्रत्येकासाठी समान आहे! ते तुमच्या छोट्या पुस्तकात लिहा, विसरू नका. ते तुमच्या लॉगमध्ये लिहा!”

   

4. उर्वरित नोड्स पुष्टीकरण (स्वीकारलेले) पाठवतात की त्यांनी "O" मूल्य लिहून ठेवले आहे; या काळात नवीन काहीही आलेले नाही (एक प्रकारचा द्वि-चरण कमिट). या महत्त्वपूर्ण घटनेनंतर, आम्ही विचार करतो की वितरित व्यवहार पूर्ण झाला आहे.
   

अशा प्रकारे, एका साध्या प्रकरणात सहमती अल्गोरिदममध्ये चार चरण असतात: प्रस्ताव, मत (मतदान), स्वीकार (स्वीकार), स्वीकृतीची पुष्टी (स्वीकारलेली).

जर काही टप्प्यावर आम्ही करारावर पोहोचू शकलो नाही, तर प्रस्तावित मूल्याची पुष्टी करण्यास नकार देणाऱ्या नोड्सद्वारे प्रदान केलेली माहिती विचारात घेऊन अल्गोरिदम पुन्हा सुरू होईल.

असिंक्रोनस सिस्टममध्ये एकमत अल्गोरिदम

याआधी, सर्व काही गुळगुळीत होते, कारण आम्ही सिंक्रोनस मेसेजिंग मॉडेलबद्दल बोलत होतो. परंतु आपल्याला माहित आहे की आधुनिक जगात आपल्याला सर्व काही असिंक्रोनसपणे करण्याची सवय आहे. असिंक्रोनस मेसेजिंग मॉडेलसह सिस्टीममध्ये समान अल्गोरिदम कसे कार्य करते, जिथे आम्हाला विश्वास आहे की नोडच्या प्रतिसादाची प्रतीक्षा वेळ अनियंत्रितपणे लांब असू शकते (तसे, नोडचे अपयश देखील एक उदाहरण म्हणून मानले जाऊ शकते जेव्हा नोड अनियंत्रितपणे दीर्घकाळ प्रतिसाद देऊ शकतो).

आता आम्हाला माहित आहे की सहमती अल्गोरिदम तत्त्वतः कसे कार्य करते, त्या जिज्ञासू वाचकांसाठी एक प्रश्न ज्यांनी हे आतापर्यंत केले आहे: असिंक्रोनस संदेश मॉडेलसह N नोड्सच्या सिस्टममध्ये किती नोड्स अयशस्वी होऊ शकतात जेणेकरून सिस्टम अद्याप एकमतापर्यंत पोहोचू शकेल?

योग्य उत्तर आणि औचित्य बिघडवणाऱ्याच्या मागे आहे.बरोबर उत्तर: 0. असिंक्रोनस सिस्टीममधील एक नोड देखील अयशस्वी झाल्यास, सिस्टम एकमतापर्यंत पोहोचण्यास सक्षम होणार नाही. हे विधान FLP प्रमेयामध्ये सिद्ध झाले आहे, काही मंडळांमध्ये सुप्रसिद्ध आहे (1985, फिशर, लिंच, पॅटरसन, लेखाच्या शेवटी मूळचा दुवा): “किमान एक नोड अयशस्वी झाल्यास वितरित एकमत साध्य करणे अशक्य आहे. .”

मित्रांनो, मग आम्हाला एक समस्या आहे, आम्हाला सर्वकाही असिंक्रोनस असण्याची सवय आहे. आणि इथे आहे. कसे जगायचे?

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

हे वर वर्णन केलेल्या जिवंतपणाच्या मालमत्तेचे उल्लंघन आहे. आमच्याकडे सामायिक करार नाही आणि आमच्याकडे सर्व नोड्सकडून प्रतिसाद नसताना प्रणालीमध्ये प्रगती होऊ शकत नाही (मर्यादित वेळेत पूर्ण होऊ शकत नाही). कारण अॅसिंक्रोनस सिस्टीममध्ये आमच्याकडे अंदाजे प्रतिसाद वेळ नसतो आणि आम्हाला कळू शकत नाही की नोड क्रॅश झाला आहे किंवा प्रतिसाद देण्यासाठी बराच वेळ घेत आहे.

पण व्यवहारात आपण त्यावर उपाय शोधू शकतो. अयशस्वी झाल्यास आमचे अल्गोरिदम दीर्घकाळ कार्य करण्यास सक्षम होऊ द्या (संभाव्यपणे ते अनिश्चित काळासाठी कार्य करू शकते). परंतु बर्‍याच परिस्थितींमध्ये, जेव्हा बहुतेक नोड्स योग्यरित्या कार्य करत असतात, तेव्हा आम्हाला सिस्टममध्ये प्रगती होईल.

सराव मध्ये, आम्ही अंशतः सिंक्रोनस संप्रेषण मॉडेल हाताळतो. आंशिक सिंक्रोनी खालीलप्रमाणे समजली जाते: सर्वसाधारणपणे, आमच्याकडे एक असिंक्रोनस मॉडेल आहे, परंतु विशिष्ट वेळेच्या "जागतिक स्थिरीकरण वेळ" ची एक विशिष्ट संकल्पना औपचारिकपणे सादर केली जाते.

हा क्षण कितीही काळासाठी येत नसला तरी तो एक दिवस यायलाच हवा. व्हर्च्युअल अलार्म घड्याळ वाजेल, आणि त्या क्षणापासून आम्ही संदेश कोणत्या वेळेसाठी येईल याचा अंदाज लावू शकतो. या क्षणापासून, सिस्टम एसिंक्रोनसमधून सिंक्रोनसमध्ये वळते. सराव मध्ये, आम्ही तंतोतंत अशा प्रणाली हाताळतो.

पॅक्सोस अल्गोरिदम सर्वसहमतीच्या समस्यांचे निराकरण करते

पॉक्सोस हे अल्गोरिदमचे एक कुटुंब आहे जे अंशतः सिंक्रोनस सिस्टीमसाठी एकमत समस्या सोडवते, काही नोड्स अयशस्वी होण्याची शक्यता असते. पॉक्सोसचे लेखक आहेत लेस्ली लॅम्पोर्ट. त्यांनी 1989 मध्ये अल्गोरिदमच्या अस्तित्वाचा आणि अचूकतेचा औपचारिक पुरावा प्रस्तावित केला.

पण पुरावा क्षुल्लक पासून लांब निघाला. अल्गोरिदमचे वर्णन करणारे पहिले प्रकाशन केवळ 1998 (33 पृष्ठे) मध्ये प्रसिद्ध झाले. हे समजणे अत्यंत अवघड होते आणि 2001 मध्ये लेखाचे स्पष्टीकरण प्रकाशित झाले, ज्यात 14 पृष्ठे होती. खरं तर सहमतीची समस्या अजिबात सोपी नाही आणि अशा अल्गोरिदमच्या मागे हुशार लोकांचे खूप मोठे काम आहे हे दर्शविण्यासाठी प्रकाशनांचा खंड दिला जातो.

हे मनोरंजक आहे की लेस्ली लॅम्पपोर्टने स्वतः त्यांच्या व्याख्यानात नमूद केले आहे की दुसर्‍या स्पष्टीकरणात्मक लेखात एक विधान आहे, एक ओळ (त्याने कोणती ते निर्दिष्ट केले नाही), ज्याचा वेगवेगळ्या प्रकारे अर्थ लावला जाऊ शकतो. आणि यामुळे, मोठ्या संख्येने आधुनिक पॉक्सोस अंमलबजावणी पूर्णपणे योग्यरित्या कार्य करत नाहीत.

पॉक्सोसच्या कार्याचे तपशीलवार विश्लेषण करण्यासाठी एकापेक्षा जास्त लेख लागतील, म्हणून मी अल्गोरिदमची मुख्य कल्पना अगदी थोडक्यात सांगण्याचा प्रयत्न करेन. माझ्या लेखाच्या शेवटी असलेल्या दुव्यांमध्ये तुम्हाला या विषयात आणखी डुबकी मारण्यासाठी साहित्य सापडेल.

पॉक्सोस येथे भूमिका

पॉक्सोस अल्गोरिदममध्ये भूमिकांची संकल्पना आहे. चला तीन मुख्य गोष्टींचा विचार करूया (अतिरिक्त भूमिकांसह बदल आहेत):

1. प्रस्तावक (अटी देखील वापरल्या जाऊ शकतात: नेते किंवा समन्वयक). हे असे लोक आहेत जे वापरकर्त्याकडून काही नवीन मूल्यांबद्दल शिकतात आणि नेत्याची भूमिका स्वीकारतात. नवीन मूल्यासाठी प्रस्तावांची फेरी सुरू करणे आणि नोड्सच्या पुढील क्रियांचे समन्वय साधणे हे त्यांचे कार्य आहे. शिवाय, पॉक्सोस विशिष्ट परिस्थितींमध्ये अनेक नेत्यांच्या उपस्थितीची परवानगी देतो.
2. स्वीकारणारे (मतदार). हे नोड्स आहेत जे विशिष्ट मूल्य स्वीकारण्यासाठी किंवा नाकारण्यासाठी मत देतात. त्यांची भूमिका खूप महत्त्वाची आहे, कारण निर्णय त्यांच्यावर अवलंबून आहे: एकमत अल्गोरिदमच्या पुढील टप्प्यानंतर सिस्टम कोणत्या स्थितीत जाईल (किंवा करणार नाही).
3. शिकणारे. नोड्स जे सिस्टीमची स्थिती बदलल्यावर नवीन स्वीकृत मूल्य स्वीकारतात आणि लिहितात. ते निर्णय घेत नाहीत, ते फक्त डेटा प्राप्त करतात आणि अंतिम वापरकर्त्याला देऊ शकतात.

एक नोड वेगवेगळ्या परिस्थितींमध्ये अनेक भूमिका एकत्र करू शकतो.

कोरमची संकल्पना

आम्ही असे गृहीत धरतो की आमच्याकडे एक प्रणाली आहे N नोडस् आणि त्यापैकी जास्तीत जास्त F नोड्स अयशस्वी होऊ शकतात. F नोड्स अयशस्वी झाल्यास, आमच्याकडे किमान असणे आवश्यक आहे 2F+1 स्वीकारकर्ता नोड्स.

हे आवश्यक आहे जेणेकरुन आमच्याकडे नेहमीच बहुसंख्य, अगदी वाईट परिस्थितीतही, "चांगले" नोड्स आहेत जे योग्यरित्या कार्य करतात. ते आहे F+1 "चांगले" नोड्स जे सहमत आहेत आणि अंतिम मूल्य स्वीकारले जाईल. अन्यथा, अशी परिस्थिती असू शकते की आमचे भिन्न स्थानिक गट भिन्न अर्थ घेतात आणि आपापसात सहमत होऊ शकत नाहीत. त्यामुळे आम्हाला मताधिक्य मिळवण्यासाठी पूर्ण बहुमताची गरज आहे.

पॉक्सोस कॉन्सेन्सस अल्गोरिदम कसे कार्य करते याची सामान्य कल्पना

पॉक्सोस अल्गोरिदममध्ये दोन मोठे टप्पे समाविष्ट आहेत, जे प्रत्येकी दोन चरणांमध्ये विभागले गेले आहेत:

1. टप्पा 1a: तयार करा. तयारीच्या टप्प्यात, नेता (प्रस्तावक) सर्व नोड्सना सूचित करतो: “आम्ही मतदानाचा एक नवीन टप्पा सुरू करत आहोत. आमच्याकडे एक नवीन फेरी आहे. या फेरीची संख्या n आहे. आता आम्ही मतदान सुरू करू." आत्तासाठी, ते फक्त नवीन चक्र सुरू झाल्याचा अहवाल देते, परंतु नवीन मूल्याची तक्रार करत नाही. या टप्प्याचे कार्य एक नवीन फेरी सुरू करणे आणि प्रत्येकाला त्याच्या अद्वितीय क्रमांकाची माहिती देणे आहे. राउंड नंबर महत्त्वाचा आहे, ते आधीच्या सर्व नेत्यांच्या सर्व मतदान क्रमांकांपेक्षा मोठे असणे आवश्यक आहे. कारण गोल क्रमांकामुळे सिस्टीममधील इतर नोड्स लीडरचा डेटा किती अलीकडील आहे हे समजतील. अशी शक्यता आहे की इतर नोड्समध्ये आधीच नंतरच्या फेऱ्यांमधून मतदानाचे निकाल आहेत आणि ते नेत्याला सांगतील की तो वेळेच्या मागे आहे.
2. टप्पा 1 ब: वचन. जेव्हा स्वीकारणाऱ्या नोड्सना नवीन मतदान स्टेजची संख्या प्राप्त होते, तेव्हा दोन परिणाम शक्य आहेत:
   • नवीन मताची संख्या n ही पूर्वीच्या कोणत्याही मताच्या संख्येपेक्षा जास्त आहे ज्यामध्ये स्वीकारकर्त्याने भाग घेतला होता. मग स्वीकारणारा नेत्याला वचन पाठवतो की तो n पेक्षा कमी असलेल्या अधिक मतांमध्ये भाग घेणार नाही. जर स्वीकारणार्‍याने आधीच एखाद्या गोष्टीसाठी मत दिले असेल (म्हणजेच, दुसर्‍या टप्प्यात काही मूल्य आधीच स्वीकारले असेल), तर ते स्वीकारलेले मूल्य आणि ज्या मतात सहभागी झाले होते त्याची संख्या जोडते.
   • अन्यथा, जर स्विकारकर्त्याला आधीच उच्च-संख्येच्या मताबद्दल माहिती असेल, तर तो फक्त तयारीच्या टप्प्याकडे दुर्लक्ष करू शकतो आणि नेत्याला प्रतिसाद देऊ शकत नाही.
3. फेज 2a: स्वीकारा. नेत्याला कोरम (सिस्टममधील बहुसंख्य नोड्स) कडून प्रतिसादाची प्रतीक्षा करणे आवश्यक आहे आणि आवश्यक संख्येने प्रतिसाद मिळाल्यास, त्याच्याकडे इव्हेंटच्या विकासासाठी दोन पर्याय आहेत:
   • स्वीकारणाऱ्यांपैकी काहींनी आधीच मत दिलेली मूल्ये पाठवली. या प्रकरणात, नेता जास्तीत जास्त संख्येसह मतांमधून मूल्य निवडतो. या व्हॅल्यूला x म्हणू या, आणि ते सर्व नोड्सला संदेश पाठवते जसे: “स्वीकार (n, x)”, जिथे पहिले मूल्य हे स्वतःच्या प्रपोज स्टेपमधील मतदान क्रमांक आहे, आणि दुसरे मूल्य प्रत्येकाने ज्यासाठी एकत्र केले आहे, म्हणजे ज्या मूल्यासाठी आपण प्रत्यक्षात मतदान करतो.
   • जर स्वीकारणार्‍यांपैकी कोणीही मूल्ये पाठवली नाहीत, परंतु त्यांनी या फेरीत मत देण्याचे वचन दिले असेल, तर नेता त्यांना त्यांच्या मूल्यासाठी मतदान करण्यासाठी आमंत्रित करू शकतो, ज्या मूल्यासाठी तो प्रथम स्थानावर नेता बनला. याला y म्हणू या. हे सर्व नोड्सना संदेश पाठवते जसे: “स्वीकारा (n, y)”, मागील निकालाप्रमाणेच.
4. टप्पा 2b: स्वीकारले. पुढे, स्वीकारकर्ता नोड्स, नेत्याकडून "स्वीकारा(...)" संदेश प्राप्त झाल्यावर, त्याच्याशी सहमत आहेत (सर्व नोड्सना ते नवीन मूल्याशी सहमत असल्याचे पुष्टीकरण पाठवा) जर त्यांनी काही (इतर) वचन दिले नसेल तरच. फेरी क्रमांकासह मतदानात सहभागी होण्यासाठी नेता n' > n, अन्यथा ते पुष्टीकरण विनंतीकडे दुर्लक्ष करतात.

   जर बहुसंख्य नोड्स नेत्याला प्रतिसाद दिला आणि त्या सर्वांनी नवीन मूल्याची पुष्टी केली, तर नवीन मूल्य स्वीकारले जाते. हुर्रे! जर बहुमत गाठले नाही किंवा नवीन मूल्य स्वीकारण्यास नकार देणारे नोड्स असतील तर सर्वकाही पुन्हा सुरू होईल.

अशा प्रकारे पॉक्सोस अल्गोरिदम कार्य करते. या प्रत्येक टप्प्यात अनेक बारकावे आहेत, आम्ही व्यावहारिकरित्या विविध प्रकारचे अपयश, अनेक नेत्यांच्या समस्या आणि बरेच काही विचारात घेतले नाही, परंतु या लेखाचा उद्देश केवळ वाचकांना उच्च स्तरावर वितरित संगणनाच्या जगाची ओळख करून देणे आहे.

हे देखील लक्षात घेण्यासारखे आहे की पॉक्सोस हा त्याच्या प्रकारचा एकमेव नाही, इतर अल्गोरिदम आहेत, उदाहरणार्थ, राफ्ट, परंतु हा दुसर्‍या लेखाचा विषय आहे.

पुढील अभ्यासासाठी साहित्याचे दुवे

नवशिक्या पातळी:

• वितरित एकमत कसे कार्य करते?, प्रीथी कासिरेड्डी , माध्यमावरील ब्लॉग लेख
• Paxos सोपे केले. वास्तविक साठी, आदि कंचेरला , माध्यमावरील ब्लॉग लेख
• विकेंद्रित विचार, इत्ताई अब्राहम, ब्लॉग
• सिंक्रोनी, असिंक्रोनी आणि आंशिक सिंक्रोनी, इत्ताई अब्राहम, ब्लॉग लेख

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

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

स्त्रोत: www.habr.com