दो-चरण की प्रतिबद्धता और वितरित प्रणालियों का भविष्य

इस लेख में, हम टीएलए + का उपयोग करके दो-चरण प्रतिबद्ध प्रोटोकॉल का अनुकरण और जांच करते हैं।

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

बिपासे समस्या करते हैं

लेनदेन संसाधन प्रबंधकों (आरएम) से होकर गुजरता है। सभी आरएम को इस बात पर सहमत होना चाहिए कि क्या लेनदेन पूरा हो जाएगा या समाप्त हो जाएगा।

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

मॉडलिंग पर कुछ नोट्स

सादगी के लिए, हम एक संदेश प्रणाली में नहीं बल्कि एक साझा मेमोरी मॉडल में सिमुलेशन करते हैं। यह त्वरित मॉडल सत्यापन भी प्रदान करता है। संदेश भेजने के दौरान दिलचस्प व्यवहार को पकड़ने के लिए हम "पड़ोसी नोड से पढ़ने और राज्य को अपडेट करने" के लिए गैर-परमाणुता जोड़ेंगे।

RM केवल TM स्थिति पढ़ सकता है और अपनी स्थिति को पढ़ / अपडेट कर सकता है। यह दूसरे संसाधन प्रबंधक की स्थिति को नहीं पढ़ सकता है। एक टीएम सभी आरएम नोड्स की स्थिति को पढ़ सकता है और अपने स्वयं के राज्य को पढ़ / अपडेट कर सकता है।

परिभाषित

लाइनों 9-10 प्रत्येक आरएम के लिए working करने के लिए प्रारंभिक rmState सेट करें, और टीएम rmState ।

यदि सभी आरएम "तैयार" (प्रतिबद्ध होने के लिए तैयार) हैं, तो canCommit विधेय true । यदि RM अंतिम स्थिति में मौजूद है, तो canAbort विधेय canAbort हो जाता canAbort ।



मॉडलिंग टीएम सरल है। लेन-देन प्रबंधक एक प्रतिबद्ध या रद्द करने की संभावना की जांच करता है - और तदनुसार tmState अपडेट tmState ।

ऐसी संभावना है कि TM tmState "दुर्गम" बनाने में सक्षम नहीं होगा, लेकिन केवल तभी जब TMMAYFAIL स्थिरांक मॉडल सत्यापन शुरू होने से पहले true सेट हो। टीएलए + लेबल में परमाणु की डिग्री, अर्थात इसकी बारीकता निर्धारित करते हैं। एफ 1 और एफ 2 के लेबल के द्वारा हम निरूपित करते हैं कि संबंधित ऑपरेटरों को पिछले ऑपरेटरों के संबंध में गैर-व्यावहारिक रूप से (कुछ अनिश्चित समय के बाद) प्रदर्शन किया जाता है।

आरएम मॉडल

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

दो-चरण प्रतिबद्ध मॉडल

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

Completed विधेय सत्यापित करता है कि प्रोटोकॉल हमेशा के लिए लटका नहीं है: अंत में, प्रत्येक आरएम अंतिम रूप से committed या aborted ।

अब हम प्रोटोकॉल मॉडल का परीक्षण करने के लिए तैयार हैं। प्रारंभ में, हम तीन आरएम और एक टीएम के साथ प्रोटोकॉल को शुरू करने के लिए TMMAYFAIL=FALSE, RM=1..3 सेट TMMAYFAIL=FALSE, RM=1..3 , अर्थात, एक विश्वसनीय कॉन्फ़िगरेशन में। मॉडल का परीक्षण करने में 15 सेकंड लगते हैं और कहते हैं कि इसमें कोई त्रुटि नहीं है। Consistency और Completed दोनों आरएम कार्यों और टीएम क्रियाओं के किसी भी विकल्प के साथ किसी भी संभावित प्रोटोकॉल निष्पादन से संतुष्ट Completed ।



अब TMMAYFAIL=TRUE सेट करें और चेक को पुनः आरंभ करें। कार्यक्रम जल्दी से विपरीत परिणाम पैदा करता है, जहां आरएम एक अनुपलब्ध टीएम से प्रतिक्रिया की प्रतीक्षा में फंस गया।



हम देखते हैं कि State=4 आरएम 2 संक्रमणों से बाधित होता है, State=7 पर आरएम State=7 संक्रमण होता है, State=8 टीएम "हैंग" स्थिति में चला जाता है और State=9 गिर जाता है। State=10 सिस्टम जमा देता है क्योंकि RM1 एक तैयार अवस्था में हमेशा के लिए रहता है, एक गिरी हुई TM के निर्णय की प्रतीक्षा में।

बीटीएम सिमुलेशन

लेन-देन के जमाव से बचने के लिए, हम एक बैकअप TM (BTM) जोड़ते हैं, जो मुख्य TM अनुपलब्ध होने पर जल्दी से नियंत्रण में ले लेता है। बीटीएम निर्णय लेने के लिए टीएम के समान तर्क का उपयोग करता है। और सरलता के लिए, हम मानते हैं कि बीटीएम कभी भी दुर्घटनाग्रस्त नहीं होता है।



जब हम जोड़े गए बीटीएम प्रक्रिया के साथ मॉडल का परीक्षण करते हैं, तो हमें एक नया त्रुटि संदेश मिलता है।



BTM एक प्रतिबद्धता को स्वीकार नहीं कर सकता क्योंकि हमारी मूल स्थिति, canCommit कहती है कि सभी RMstates को "तैयार" होना चाहिए और इस शर्त को ध्यान में नहीं रखना चाहिए कि कुछ RM ने TMB के नियंत्रण से पहले ही मूल TM से एक प्रतिबद्ध निर्णय ले लिया है। इस स्थिति को ध्यान में canCommit हुए canCommit की शर्तों को फिर से लिखना आवश्यक है।



सफलता! जब हम मॉडल का परीक्षण करते हैं, तो हम स्थिरता और पूर्णता दोनों प्राप्त करते हैं, क्योंकि बीटीएम नियंत्रित होता है और यदि टीएम गिरता है तो लेनदेन पूरा करता है। यहाँ 2PCwithBTM मॉडल TLA + (BTM और कैनोमी की दूसरी पंक्ति शुरू में अप्रतिबंधित है) और संबंधित पीडीएफ है ।

अगर RM विफल भी हो जाए तो क्या होगा?

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





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

मॉडल की जाँच

जब हम मॉडल का परीक्षण करते हैं, तो असंगतता की समस्या होती है! यह कैसे हो सकता है? हम ट्रेस का पता लगाते हैं।

State=6 सभी आरएम एक तैयार स्थिति में हैं, टीएम ने लेनदेन को पूरा करने का निर्णय लिया, आरएम 1 ने इस निर्णय को देखा और आरसी लेबल पर स्विच किया, जिसका अर्थ है कि अपने राज्य को "पूरा" करने के लिए बदलने की तत्परता। (आरएम 1 को याद रखें, यह बंदूक अंतिम अधिनियम में आग लगा देगी)। दुर्भाग्य से, TM State=7 पर गिर जाता है, और RM2 State=8 पर अनुपलब्ध हो जाता है। नौवें चरण में, बैकअप बीटीएम नियंत्रण लेता है और तीन आरएम की स्थिति को "तैयार, अनुपलब्ध, तैयार" के रूप में पढ़ता है - और दसवें चरण में लेनदेन को रद्द करने का निर्णय लेता है। RM1 याद रखें? वह लेन-देन को पूरा करने का फैसला करता है क्योंकि उसे मूल टीएम से ऐसा निर्णय प्राप्त हुआ, और चरण 11 में committed राज्य में प्रवेश करता है। State=13 RM3 BTM से लेनदेन को निरस्त करने के निर्णय को पूरा करता है और aborted स्थिति में प्रवेश करता है - और अब हमने RM1 के साथ समन्वय को तोड़ दिया है।

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

एक अद्यतन TLA + मॉडल फ़ाइल यहां उपलब्ध है , साथ ही संबंधित पीडीएफ भी ।

असंभावना एफएलपी

तो क्या हुआ? हम विफलताओं के साथ एक अतुल्यकालिक प्रणाली में आम सहमति की असंभवता पर फिशर, लिंच, पैटर्सन (एफएलपी) की प्रमेय पर ठोकर खाई।

हमारे उदाहरण में, बीटीएम सही ढंग से यह तय नहीं कर सकता है कि आरएम 2 विफल स्थिति में है या नहीं - और गलत तरीके से लेनदेन को रद्द करने का फैसला करता है। यदि केवल मूल टीएम ने निर्णय लिया, तो विफलता को पहचानने में इस तरह की अशुद्धि एक समस्या नहीं होगी। RM किसी भी TM निर्णय का पालन करेगा, ताकि स्थिरता और प्रगति बनी रहे।

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

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

पाक्सोस दुनिया को एक बेहतर जगह बनाने की कोशिश कर रहा है।

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

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