👙 🤺 🕋 वितरित प्रणालियों में सहमति। Paxos 🐥 🌝 🧑

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

इस लेख में मैं इस स्थिति को ठीक करने की कोशिश करूंगा और इस एल्गोरिथम के बारे में स्पष्ट भाषा में बताऊंगा, जैसा कि एल्गोरिथ्म के लेखक लेस्ली लामपोर्ट ने एक बार इसे बनाने की कोशिश की थी ।

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

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

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

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

क्लस्टर कंप्यूटिंग में, गलती सहिष्णुता को आमतौर पर घटक विफलताओं को पूरा करने के लिए सिस्टम के प्रतिरोध के रूप में समझा जाता है। ऐसी प्रणालियों में आम सहमति प्राप्त करने के लिए, पैक्सोस एल्गोरिथ्म का उपयोग किया जाता है। एल्गोरिथ्म का प्रस्ताव लेस्ली लामपोर्ट ने पिछली शताब्दी के 90 के दशक में रखा था और संसद के काम को व्यवस्थित करने की एक काल्पनिक प्रणाली के साथ पाक्सोस के ग्रीक द्वीप के नाम पर रखा गया था। सर्वसम्मति प्राप्त करने के लिए, इस एल्गोरिथ्म के लिए आवश्यक है कि 2N + 1 नोड्स की प्रणाली में कम से कम N + 1 नोड्स फ़ंक्शन, इन N + 1 नोड्स को "कोरम" कहा जाता है।

निम्नलिखित भूमिकाओं के साथ एजेंटों की बातचीत में एल्गोरिथ्म का सार:

ग्राहक - एक वितरित प्रणाली का एक ग्राहक जो अनुरोध भेज सकता है और उस पर प्रतिक्रिया प्राप्त कर सकता है
प्रस्तावक - मतदान प्रक्रिया के आयोजन के लिए जिम्मेदार एक वितरित प्रणाली का एक घटक
स्वीकर्ता - एक वितरित प्रणाली का एक घटक जिसमें प्रस्तावक से एक विशेष प्रस्ताव की स्वीकृति या अस्वीकृति के लिए वोट देने का अधिकार होता है
लर्नर - सिस्टम का एक घटक जो निर्णय को याद रखता है

मूल Paxos एल्गोरिथ्म में निम्न चरण होते हैं:

1 क। तैयार करें ("प्रस्ताव")। इस चरण में, प्रस्तावक अनुक्रम संख्या N के साथ एक "वाक्य" उत्पन्न करता है और इसे सभी स्वीकर्ता को भेजता है। निम्नलिखित "प्रस्तावों" में से प्रत्येक के लिए, संख्या N पहले से चयनित से अधिक होनी चाहिए

1b। वादा ("वादा")। प्रत्येक स्वीकर्ता को क्रम संख्या N और मान V के साथ एक "प्रस्ताव" मिलता है । यदि "स्वीकर्ता" की संख्या इस स्वीकर्ता द्वारा पहले स्वीकार किए गए सभी से अधिक है, तो वह इस संदेश को "वादे" के साथ उत्तर देने के लिए बाध्य है कि वह "ऑफ़र" से अधिक नहीं स्वीकार करता है, एक अनुक्रम संख्या एन से कम है । यदि दिए गए स्वीकर्ता ने पहले ही किसी प्रकार का "ऑफ़र" स्वीकार कर लिया है, तो उसे इस "ऑफ़र" के नंबर _I और V के मान को वापस करना होगा, अन्यथा यह एक खाली मान लौटाता है

2 ए। स्वीकार करें! ( "लो")। यदि एक प्रस्तावक को स्वीकर्ता कोरम से "वादे" मिले हैं, तो यह आगे की प्रक्रिया के लिए तैयार अनुरोध पर विचार करता है। इस घटना में कि स्वीकर्ता से "वादे" के साथ भी N _i और V _i के मूल्य आए थे, प्रस्तावक अधिकतम N _{i के} साथ "वादे" के मान V _{i के} बराबर V को चुनता है। फिर, प्रस्तावक सभी स्वीकारकर्ता को एक "स्वीकार" अनुरोध भेजता है, जिसमें एन और वी के मूल्य शामिल हैं

2 बी। स्वीकार कर लिया । जब कोई स्वीकारकर्ता N और V के मानों के साथ "स्वीकार" संदेश प्राप्त करता है, तो वह इसे तभी स्वीकार करता है जब उसने N के मुकाबले कड़ाई से अधिक संख्या वाले प्रस्तावों को स्वीकार करने के लिए "वादा" नहीं किया हो । अन्यथा, यह मान लेता है और सभी शिक्षार्थी को "स्वीकार" संदेश के साथ प्रतिक्रिया करता है

शिक्षार्थी का कार्य सरल है - वी के मान के साथ "स्वीकृत" संदेश प्राप्त करें और इसे याद रखें

एल्गोरिथ्म के कामकाज का एक उदाहरण:

Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | |<---------X--X--X | | Promise(1,{Va,Vb,Vc}) | X--------->|->|->| | | Accept!(1,Vn=last(Va,Vb,Vc)) | |<---------X--X--X------>|->| Accepted(1,Vn) |<---------------------------------X--X Response | | | | | | |

यदि वितरित सिस्टम का कोई भी घटक विफल हो जाता है तो क्या होगा?

विफलता स्वीकर्ता:

 Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | | | | ! | | !! FAIL !! | |<---------X--X | | Promise(1,{null,null, null}) | X--------->|->| | | Accept!(1,V) | |<---------X--X--------->|->| Accepted(1,V) |<---------------------------------X--X Response | | | | | |

चूंकि सिस्टम में 3 स्वीकर्ता नोड हैं, उनमें से एक विफल हो सकता है, क्योंकि इस मामले में कोरम दो है

सीखने में विफलता:

 Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | |<---------X--X--X | | Promise(1,{null,null,null}) | X--------->|->|->| | | Accept!(1,V) | |<---------X--X--X------>|->| Accepted(1,V) | | | | | | ! !! FAIL !! |<---------------------------------X Response | | | | | |

विफलता प्रस्तावक:

 Client Proposer Acceptor Learner | | | | | | | X----->| | | | | | Request | X------------>|->|->| | | Prepare(1) | |<------------X--X--X | | Promise(1,{null, null, null}) | | | | | | | | | | | | | | !! Leader fails during broadcast !! | X------------>| | | | | Accept!(1,Va) | ! | | | | | | | | | | | | !! NEW LEADER !! | X--------->|->|->| | | Prepare(2) | |<---------X--X--X | | Promise(2,{null, null, null}) | X--------->|->|->| | | Accept!(2,V) | |<---------X--X--X------>|->| Accepted(2,V) |<---------------------------------X--X Response | | | | | | |

एक प्रस्तावक की विफलता की स्थिति में, सिस्टम को एक नए प्रस्तावक का चयन करना चाहिए, आमतौर पर समय समाप्त होने के बाद मतदान करने से पुराने प्रस्तावक के लौटने की प्रतीक्षा में। इस घटना में कि नया प्रस्तावक चुनने के बाद पुराना वापस जीवन में आता है, नेताओं के बीच संघर्ष पैदा हो सकता है, जिससे सिस्टम का लूप हो सकता है:

 Client Leader Acceptor Learner | | | | | | | X----->| | | | | | Request | X------------>|->|->| | | Prepare(1) | |<------------X--X--X | | Promise(1,{null,null,null}) | ! | | | | | !! LEADER FAILS | | | | | | | !! NEW LEADER (knows last number was 1) | X--------->|->|->| | | Prepare(2) | |<---------X--X--X | | Promise(2,{null,null,null}) | | | | | | | | !! OLD LEADER recovers | | | | | | | | !! OLD LEADER tries 2, denied | X------------>|->|->| | | Prepare(2) | |<------------X--X--X | | Nack(2) | | | | | | | | !! OLD LEADER tries 3 | X------------>|->|->| | | Prepare(3) | |<------------X--X--X | | Promise(3,{null,null,null}) | | | | | | | | !! NEW LEADER proposes, denied | | X--------->|->|->| | | Accept!(2,Va) | | |<---------X--X--X | | Nack(3) | | | | | | | | !! NEW LEADER tries 4 | | X--------->|->|->| | | Prepare(4) | | |<---------X--X--X | | Promise(4,{null,null,null}) | | | | | | | | !! OLD LEADER proposes, denied | X------------>|->|->| | | Accept!(3,Vb) | |<------------X--X--X | | Nack(4) | | | | | | | | ... and so on ...

एल्गोरिदम के व्यावहारिक कार्यान्वयन में इसे रोकने के लिए, प्रत्येक प्रस्तावक के पास एक सीरियल नंबर होता है और, जब एक नए प्रस्तावक का चयन किया जाता है, तो यह संख्या एक से बढ़ जाती है। स्वीकार करने वाला कोई भी व्यक्ति पुराने प्रस्तावक के संदेशों को स्वीकार नहीं करता है।

कार्यान्वयन के एक उदाहरण के रूप में, मैं जीथब रिपॉजिटरी में से एक के लिए थोड़ा संशोधित अजगर कोड दूंगा:

 class Proposer (object): # 1a.    proposal_id (     "N") #   ""  acceptor def prepare(self): self.promises_rcvd = 0 self.proposal_id = self.next_proposal_number self.next_proposal_number += 1 self.messenger.send_prepare(self.proposal_id) # 2a.  "".      - .   "" #    acceptor  -      . #    ""  ,   "" def recv_promise(self, proposal_id, prev_accepted_id, prev_accepted_value): if proposal_id != self.proposal_id: return if prev_accepted_id > self.last_accepted_id: self.last_accepted_id = prev_accepted_id if prev_accepted_value is not None: self.proposed_value = prev_accepted_value self.promises_rcvd += 1 if self.promises_rcvd == self.quorum_size: if self.proposed_value is not None: self.messenger.send_accept(self.proposal_id, self.proposed_value) class Acceptor (object): # 1b. Acceptor  ""  proposer.  ,       , #     .        ,  #        (  )  "" def recv_prepare(self, proposal_id): if proposal_id == self.promised_id: self.messenger.send_promise(proposal_id, self.accepted_id, self.accepted_value) elif proposal_id > self.promised_id: self.promised_id = proposal_id self.messenger.send_promise(proposal_id, self.accepted_id, self.accepted_value) # 2b.   "".          ,  #         "" def recv_accept_request(self, from_uid, proposal_id, value): if proposal_id >= self.promised_id: self.promised_id = proposal_id self.accepted_id = proposal_id self.accepted_value = value self.messenger.send_accepted(proposal_id, self.accepted_value) class Learner (object): # 3. Learner   "",        def recv_accepted(self, from_uid, proposal_id, accepted_value): self.final_value = accepted_value self.messenger.on_resolution( proposal_id, accepted_value )

संदर्भ:

वितरित प्रणालियों में सहमति। Paxos

More articles: