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

त्यसोभए, कल्पना गरौं। कोठामा 5 वटा बिरालाहरू बन्द छन्, र मालिकलाई जगाउनको लागि, तिनीहरू सबैले यो कुरामा आपसमा सहमत हुन आवश्यक छ, किनभने तिनीहरूमध्ये पाँचवटा बिरालाहरू झुकेर मात्र ढोका खोल्न सक्छन्। यदि बिरालाहरू मध्ये एक श्रोडिंगरको बिरालो हो, र अन्य बिरालाहरूलाई उसको निर्णयको बारेमा थाहा छैन भने, प्रश्न उठ्छ: "तिनीहरूले यो कसरी गर्न सक्छन्?"

यस लेखमा, म तपाईंलाई वितरित प्रणालीहरूको संसारको सैद्धान्तिक घटक र तिनीहरूको सञ्चालनका सिद्धान्तहरूको बारेमा सरल शब्दहरूमा बताउनेछु। म पाक्सोसको मुख्य विचारलाई सतही रूपमा जाँच गर्नेछु।

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

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

हामी सबै भन्दा राम्रोमा विश्वास गर्छौं, किनकि ठूला कम्पनीहरूका स्मार्ट केटाहरूले हामीलाई सबै कुरा ठीक हुनेछ भनी आश्वासन दिए। हामी प्रश्न सोध्दैनौं: किन, वास्तवमा, यो सबै काम गर्न सक्छ? के त्यहाँ त्यस्ता प्रणालीहरूको सही सञ्चालनको लागि कुनै औपचारिक औचित्य छ?

म भर्खरै गएको थिएँ वितरित कम्प्युटिङ स्कूल र यो विषयबाट धेरै प्रेरित थियो। विद्यालयमा व्याख्यानहरू कम्प्युटर प्रणालीसँग सम्बन्धित केही भन्दा बढी क्यालकुलस कक्षाहरू जस्तै थिए। तर यो ठ्याक्कै कसरी हामीले हरेक दिन प्रयोग गर्ने सबैभन्दा महत्त्वपूर्ण एल्गोरिदमहरू, यो जानी नजानी, एक पटकमा प्रमाणित भयो।

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

अर्को के छलफल गरिनेछ को एक हल्का दृष्टान्त: दुई जनरल को कार्यवार्म-अपको लागि हेरौं दुई जनरलको काम.

हामीसँग दुईवटा सेनाहरू छन् - रातो र सेतो। सेतो सेना घेरिएको शहरमा आधारित छ। जनरल A1 र A2 को नेतृत्वमा रातो सेनाहरू शहरको दुई छेउमा अवस्थित छन्। रेडहेड्सको कार्य सेतो शहरमा आक्रमण गर्ने र जित्नु हो। यद्यपि, प्रत्येक रातो जनरलको सेना व्यक्तिगत रूपमा सेतो सेना भन्दा सानो छ।

रातोहरूका लागि विजय अवस्था: गोराहरूमा संख्यात्मक फाइदा लिन दुवै सेनापतिहरूले एकै समयमा आक्रमण गर्नुपर्छ। यो गर्न, जनरल A1 र A2 एक अर्कासँग सम्झौता गर्न आवश्यक छ। यदि सबैले अलग-अलग आक्रमण गरे भने, रेडहेडहरू हराउनेछन्।

सम्झौतामा पुग्नको लागि, जनरल A1 र A2 ले सेतो शहरको क्षेत्र मार्फत एक अर्कालाई सन्देशवाहकहरू पठाउन सक्छन्। सन्देशवाहक सफलतापूर्वक एक सहयोगी जनरलमा पुग्न सक्छ वा शत्रु द्वारा अवरोध हुन सक्छ। प्रश्न: के त्यहाँ रातो कपाल भएका जनरलहरू (A1 बाट A2 र यसको विपरीत A2 बाट A1 मा सन्देशवाहकहरू पठाउने क्रम) बीचको सञ्चारको यस्तो क्रम छ, जसमा तिनीहरू X घण्टामा आक्रमणमा सहमत हुने ग्यारेन्टी छन्। यहाँ, ग्यारेन्टी भनेको दुबै जनरलहरूले अस्पष्ट पुष्टि गर्नेछन् कि एक सहयोगी (अर्को जनरल) निश्चित समय X मा आक्रमण गर्नेछ।

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

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

दुई जनरल समस्या एक धेरै सरल वितरण प्रणाली को एक महान दृष्टान्त हो जहाँ अविश्वसनीय संचार संग दुई नोडहरू छन्। यसको मतलब हामीसँग 100% ग्यारेन्टी छैन कि तिनीहरू सिङ्क्रोनाइज छन्। यस्तै समस्याहरू लेखमा पछि ठूलो मात्रामा मात्र छलफल गरिन्छ।

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

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

सन्देशहरू कसरी लागू हुन्छन्, कुन प्रोटोकलहरू प्रयोग गरिन्छ - यो यस सन्दर्भमा हामीलाई चासोको विषय होइन। यो महत्त्वपूर्ण छ कि वितरित प्रणालीका नोडहरूले सन्देशहरू पठाएर एकअर्कासँग डाटा आदानप्रदान गर्न सक्छन्।

परिभाषा आफैंमा धेरै जटिल देखिँदैन, तर हामीले ध्यानमा राख्नुपर्छ कि वितरित प्रणालीमा धेरै विशेषताहरू छन् जुन हाम्रो लागि महत्त्वपूर्ण हुनेछ।

वितरण प्रणाली को विशेषताहरु

1. कन्सर्ट - प्रणालीमा एक साथ वा समवर्ती घटनाहरू हुने सम्भावना। यसबाहेक, हामी दुई फरक नोडहरूमा हुने घटनाहरूलाई सम्भावित रूपमा समवर्ती हुन विचार गर्नेछौं जबसम्म हामीसँग यी घटनाहरूको घटनाको स्पष्ट क्रम छैन। तर, नियमको रूपमा, हामीसँग छैन।
2. विश्वव्यापी घडी छैन। विश्वव्यापी घडी नभएको कारण हामीसँग घटनाहरूको स्पष्ट क्रम छैन। मानिसहरूको साधारण संसारमा, हामी यस तथ्यमा अभ्यस्त छौं कि हामीसँग घडी र समय पूर्ण रूपमा छ। सबै कुरा परिवर्तन हुन्छ जब यो वितरण प्रणाली को लागी आउँछ। अति-सटीक आणविक घडीहरू पनि बगेका छन्, र त्यहाँ परिस्थितिहरू हुन सक्छ जहाँ हामी दुई घटनाहरू मध्ये कुन पहिलो भयो भनेर बताउन सक्दैनौं। त्यसैले हामी पनि समयमा भर पर्न सक्दैनौं।
3. प्रणाली नोडहरूको स्वतन्त्र विफलता। त्यहाँ अर्को समस्या छ: केहि गलत हुन सक्छ किनभने हाम्रो नोडहरू सधैंभरि रहँदैन। हार्ड ड्राइभ असफल हुन सक्छ, क्लाउडमा भर्चुअल मेसिन रिबुट हुन सक्छ, नेटवर्क झिम्काउन सक्छ र सन्देशहरू हराउन सक्छ। यसबाहेक, त्यहाँ परिस्थितिहरू हुन सक्छ जहाँ नोडहरू काम गर्छन्, तर एकै समयमा प्रणाली विरुद्ध काम गर्दछ। समस्याहरूको अन्तिम वर्गले पनि छुट्टै नाम प्राप्त गर्यो: समस्या बाइजान्टिन जनरलहरू। यस समस्याको साथ वितरण प्रणालीको सबैभन्दा लोकप्रिय उदाहरण Blockchain हो। तर आज हामी समस्याहरूको यो विशेष वर्गलाई विचार गर्दैनौं। हामी केवल एक वा बढी नोडहरू असफल हुन सक्ने अवस्थाहरूमा रुचि राख्नेछौं।
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, Fischer, Lynch, Paterson, लेख को अन्त मा मूल लिङ्क): "कम्तिमा एक नोड असफल भएमा एक वितरित सहमति प्राप्त गर्न असम्भव। ।"

साथीहरू, त्यसोभए हामीसँग समस्या छ, हामी सबै कुरा एसिन्क्रोनस हुने बानी परेका छौं। र यो यहाँ छ। कसरी बाँच्न जारी राख्न?

हामी केवल सिद्धान्तको बारेमा कुरा गर्दै थियौं, गणितको बारेमा। "सहमति हासिल गर्न सकिँदैन" भनेको के हो, गणितीय भाषाबाट हाम्रो - इन्जिनियरिङमा अनुवाद गर्नु? यसको मतलब "सधैं हासिल गर्न सकिँदैन", अर्थात्। सहमति हुन नसक्ने अवस्था छ । यो कस्तो मामला हो?

यो माथि वर्णन गरिएको जीवन्तता सम्पत्ति को ठीक उल्लङ्घन हो। हामीसँग साझा सम्झौता छैन, र प्रणालीमा प्रगति हुन सक्दैन (सीमित समयमा पूरा हुन सक्दैन) जहाँ हामीसँग सबै नोडहरूबाट प्रतिक्रिया छैन। किनभने एक एसिन्क्रोनस प्रणालीमा हामीसँग कुनै अनुमानित प्रतिक्रिया समय छैन र हामी जान्न सक्दैनौं कि नोड क्र्यास भएको छ वा प्रतिक्रिया गर्न लामो समय लिइरहेको छ।

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

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

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

Paxos एल्गोरिथ्मले सहमति समस्याहरू समाधान गर्दछ

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

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

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

Paxos को काम को एक विस्तृत विश्लेषण एक भन्दा बढी लेख लाग्नेछ, त्यसैले म एल्गोरिथ्म को मुख्य विचार धेरै छोटकरीमा व्यक्त गर्ने प्रयास गर्नेछु। मेरो लेखको अन्त्यमा लिङ्कहरूमा तपाईंले यस विषयमा थप डाइभिङका लागि सामग्रीहरू पाउनुहुनेछ।

Paxos मा भूमिकाहरू

Paxos एल्गोरिथ्ममा भूमिकाहरूको अवधारणा छ। तीन मुख्य विचार गरौं (अतिरिक्त भूमिकाहरूसँग परिमार्जनहरू छन्):

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

एउटा नोडले विभिन्न परिस्थितिहरूमा धेरै भूमिकाहरू संयोजन गर्न सक्छ।

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

हामी मान्छौं कि हामीसँग एउटा प्रणाली छ N नोडहरू र ती मध्ये अधिकतम F नोडहरू असफल हुन सक्छ। यदि F नोडहरू असफल भएमा, हामीसँग कम्तिमा हुनुपर्छ 2F+1 स्वीकारकर्ता नोडहरू।

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

Paxos सहमति एल्गोरिथ्म कसरी काम गर्दछ भन्ने सामान्य विचार

Paxos एल्गोरिथ्मले दुई ठूला चरणहरू समावेश गर्दछ, जुन बारीमा प्रत्येक दुई चरणहरूमा विभाजित हुन्छन्:

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

   यदि अधिकांश नोडहरूले नेतालाई प्रतिक्रिया दिए, र ती सबैले नयाँ मान पुष्टि गरे, त्यसपछि नयाँ मान स्वीकार गरिएको मानिन्छ। हुर्रे! यदि बहुमत पुगेको छैन वा नयाँ मान स्वीकार गर्न अस्वीकार गर्ने नोडहरू छन्, त्यसपछि सबै कुरा सुरु हुन्छ।

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

यो पनि ध्यान दिन लायक छ कि Paxos यसको प्रकारको एक मात्र होइन, त्यहाँ अन्य एल्गोरिदमहरू छन्, उदाहरणका लागि, Raft, तर यो अर्को लेखको लागि विषय हो।

थप अध्ययनको लागि सामग्रीको लिङ्कहरू

प्रारम्भिक स्तर:

• वितरित सहमतिले कसरी काम गर्छ?, प्रीति कासिरेड्डी, माध्यममा ब्लग लेख
• Paxos सरल बनायो। वास्तविक लागि, आदि कंचेर्ला, मध्यममा ब्लग लेख
• विकेन्द्रीकृत विचार, Ittai अब्राहम, ब्लग
• सिंक्रोनी, एसिन्क्रोनी र आंशिक सिंक्रोनी, Ittai अब्राहम, ब्लग लेख

Leslie Lamport स्तर:

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

स्रोत: www.habr.com