सर्वर एक-दूसरे के साथ कैसे बातचीत करते हैं: रफ़ ने आम सहमति एल्गोरिथम वितरित किया

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

लेख लेखक: दिमित्री पावलुशिन (डेवलपर डोडो पिज्जा इंजीनियरिंग)।

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

रफ क्लस्टर द्वारा परोसा गया डेटा एक लॉग इन रिकॉर्ड है। जब कोई उपयोगकर्ता किसी क्लस्टर में संग्रहीत डेटा को बदलना चाहता है, तो वह कमांड के साथ लॉग में एक नया रिकॉर्ड जोड़ने की कोशिश करता है:


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

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

मूल अवधारणाएँ

1. सर्वर बताता है रफ़ट क्लस्टर में, किसी भी समय प्रत्येक सर्वर तीन राज्यों में से एक में होता है:
   
   • लीडर (नेता) - सभी क्लाइंट अनुरोधों को संसाधित करता है, लॉग में सभी डेटा की सच्चाई का स्रोत है, अनुयायी लॉग का समर्थन करता है।
   • अनुयायी (अनुयायी) एक निष्क्रिय सर्वर है जो केवल नेता से नई लॉग प्रविष्टियों को सुनता है और ग्राहकों से नेता के लिए आने वाले सभी अनुरोधों को पुनर्निर्देशित करता है। वास्तव में, यह नेता का हॉट-स्टैंडबाय प्रतिकृति है।
   • उम्मीदवार (उम्मीदवार) सर्वर का एक विशेष राज्य है, जो एक नए नेता के चयन के दौरान ही संभव है।
   
   एक क्लस्टर में सामान्य ऑपरेशन के दौरान, केवल एक सर्वर ही लीडर होता है, बाकी सभी उसके अनुयायी होते हैं।
   
   
   अतुल्यकालिकता के बारे में

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

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

कार्य एल्गोरिथ्म

1. एक नेता चुनें

यह निर्धारित करने के लिए कि एक नया चुनाव शुरू करने का समय है, रफ दिल की धड़कन पर निर्भर करता है। अनुयायी तब तक अनुयायी बना रहता है जब तक कि उसे वर्तमान नेता या उम्मीदवार के संदेश नहीं मिलते हैं। नेता समय-समय पर अन्य सभी सर्वरों को दिल की धड़कन भेजता है।

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

चुनाव शुरू करने के लिए, अनुयायी अपना पद संख्या बढ़ाता है, "उम्मीदवार" राज्य में जाता है, स्वयं के लिए वोट करता है, और फिर अन्य सभी सर्वरों को "RequestVote" अनुरोध भेजता है। उसके बाद, उम्मीदवार तीन घटनाओं में से एक का इंतजार करता है:

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

2. हम लॉग को दोहराते हैं

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

जब अधिकांश सर्वर पर रिकॉर्ड को सफलतापूर्वक दोहराया जाता है, तो नेता रिकॉर्ड को बंद करने पर विचार करना शुरू कर देता है और ग्राहक को जवाब देता है। नेता इस बात पर नज़र रखता है कि कौन सा रिकॉर्ड आखिरी है। यह इस रिकॉर्ड की संख्या को AppendEntries (दिल की धड़कन सहित) भेजता है ताकि अनुयायी रिकॉर्ड को खुद कर सकें।

यदि नेता कुछ अनुयायियों तक नहीं पहुंच सकता है, तो वह परिशिष्ट में अनंतता को वापस कर देगा। निम्न चित्र दिखाता है कि लॉग्स को बेड़ा समूह में कैसे व्यवस्थित किया जाता है:



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

3. हम एल्गोरिथ्म की विश्वसनीयता की गारंटी देते हैं

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

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

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

  निम्नलिखित स्थिति पर विचार करें: एक क्लस्टर में तीन सर्वर। सर्वर S1 वर्तमान पहले कार्यकाल का नेता है। सभी सर्वर में तीन लॉग एंट्री होती हैं।
  
  
  
  लीडर S1 क्लाइंट से एक अनुरोध प्राप्त करता है और अपने लॉग में एक नया रिकॉर्ड जोड़ता है, अन्य S2 और S3 सर्वरों को AppendEntries भेजता है।
  
  
  
  रिकॉर्ड सफलतापूर्वक S2 तक पहुंच जाता है, लेकिन S1 और S3 के बीच का नेटवर्क ब्लिंक हो जाता है, और अनुरोध खो जाता है। चूंकि S1 जानता है कि रिकॉर्ड तीन में से दो सर्वर पर मौजूद है, इसलिए यह निर्धारित कर सकता है कि रिकॉर्ड प्रतिबद्ध है और क्लाइंट को सफलतापूर्वक जवाब देता है।
  
  S1 भी S3 में एक प्रविष्टि जोड़कर पुन: प्रयास करेगा जब तक कि यह सफल नहीं हो जाता। लेकिन क्या होता है अगर S1 विफल हो जाता है और यह बंद हो जाता है? इसके अलावा, अगर S3 प्रतीक्षा से थक गया है और यह एक उम्मीदवार बन गया तो क्या होगा? S2 इसके लिए मतदान करेगा, S3 दूसरे कार्यकाल का नेता बनेगा, और एक रिकॉर्ड जोड़ने के अगले अनुरोध पर, S3 हमारे रिकॉर्ड किए गए रिकॉर्ड को अधिलेखित कर देगा?
  
  
  
  वास्तव में, यह स्थिति रफ क्लस्टर में नहीं हो सकती है। यहां पकड़ यह है कि S2 S3 को वोट नहीं देगा। क्यों? क्योंकि मतदान के समय S3 सर्वर लॉग S2 सर्वर लॉग की तुलना में कम प्रासंगिक होता है। इस तंत्र को चुनाव प्रतिबंध कहा जाता है - सर्वर किसी अन्य सर्वर के लिए तभी मतदान करेगा जब उम्मीदवार का लॉग मतदाता के लॉग से कम प्रासंगिक न हो।
  
  बेड़ा दो तरह से लॉग की प्रासंगिकता की तुलना करता है:
  
  

  • अंतिम रिकॉर्ड तिथि संख्या
  • लॉग की लंबाई

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

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

• द रफ़ल कंसिस्टेंस एलगोरिदम
• एक सर्वसम्मति से सहमति एल्गोरिथ्म की खोज में
• सहमति: सिद्धांत और व्यवहार को पूरा करना
• बॉक्स के बिना श्रोडिंगर बिल्ली: वितरित प्रणालियों में आम सहमति की समस्या