सर्वसम्मति एल्गोरिदम

1) आम सहमति क्या है और इसकी आवश्यकता क्यों है

सर्वसम्मति - असफलताओं और देरी के लिए कई नोड्स के बीच समान मूल्य/मूल्यों के अनुक्रम पर बातचीत करें। परंपरागत रूप से, राज्य प्रतिकृति (राज्य मशीन प्रतिकृति, एसएमआर) की समस्या को हल किया जाता है: एक नियतात्मक राज्य मशीन और संचालन का एक सामान्य आदेश है।

• सर्वसम्मति (एसएमआर): आदेशों का एक एकल कुल क्रम - रैखिक भंडारण/रजिस्ट्री, क्लस्टर मेटाडेटा, लेन-देन समन्वयक।
• कुल आदेश के बिना कोरम संचालन (डायनामो-जैसे, सीआरडीटी): विचलन और बाद में विलय की अनुमति दें; जहां वैश्विक क्रमबद्धता की आवश्यकता है, वहां आम सहमति न बदलें।

2) समय और विफलता मॉडल

2. 1 समय मॉडल

अतुल्यकालिक नेटवर्क: देरी असीमित हैं; FLP प्रमेय - अतिरिक्त मान्यताओं के बिना सुरक्षा और जीवंतता दोनों की गारंटी देना असंभव है।

आंशिक रूप से तुल्यकालिक (अक्सर व्यवहार में): एक अज्ञात टी के बाद, सिस्टम "तुल्यकालिक रूप से" व्यवहार करता है - अधिकांश एल्गोरिदम (रफ, पैक्सोस) इस पर भरोसा करते हैं।

तुल्यकालिक: चैनलों के लिए सख्त समय सीमा (बिक्री में शायद ही कभी, विशेष नेटवर्क/पीआरटी को छोड़ कर)।

2. 2 विफलता मॉडल

क्रैश-फॉल्ट सहिष्णु (CFT): नोड्स गिर सकते हैं/लटक सकते हैं लेकिन दुर्भावनापूर्ण व्यवहार नहीं करते हैं।

बीजान्टिन-गलती सहिष्णु (BFT): नोड्स झूठ/स्पूफ संदेश दे सकते हैं। बीजान्टिन को सहिष्णुता के लिए 3f + 1 समुद्री मील की आवश्यकता होती है।

3) सर्वसम्मति के गुण

सुरक्षा: स्थिरता (दो सही नोड्स विभिन्न मानों को हल नहीं करेंगे)।

लाइवनेस: यदि नेटवर्क "स्वस्थ" है, तो एक समाधान प्राप्त किया जाता है

रैखिकता (रैखिकता): संचालन को एक ही क्रम में परमाणु के रूप में "देखा" जाता है।

स्थायित्व: किए गए निर्णय वापस लुढ़के नहीं हैं (लॉग/कोरम सुरक्षा)।

4) कोरम, प्रमुखता और चौराहे

सीएफटी दुनिया में, क्लासिक: कोरम> N/2। रिकॉर्ड और नेता चुनाव कोरम क्रॉसिंग का उपयोग करते हैं, इसलिए दो "वैध" संचालन संघर्ष नहीं करते हैं।

बीएफटी दुनिया में: 3f + 1 का कोरम 2f + 1 कम से कम f + 1 ईमानदार नोड्स का एक चौराहा प्रदान करता है।

क्रॉसिंग नियम: किसी भी दो कोरम में ≥1 सामान्य निष्पक्ष नोड (सीएफटी) या ≥f+1 (बीएफटी) होना चाहिए।

5) राज्य प्रतिकृति (लॉग + आवेदन)

पहचानकर्ता (सूचकांक/युग) के साथ लॉग में कमांड जोड़े जाते हैं। सिद्धांत: "पहले एक लॉग एंट्री (कमिट) पर सहमत होते हैं, फिर निर्धारित रूप से राज्य पर लागू होते हैं। "विकास को नियंत्रित करने के लिए, बना

स्नैपशॉट (राज्य का एक टुकड़ा जिसके बाद प्रारंभिक रिकॉर्ड हटाया/संकलित किया जा सकता है)।

जर्नल कंपेक्शन और लॉग ट्रायम।

निर्धारणवाद जाँच (समान कोड/कॉन्फिग संस्करण)।

6) नेतृत्व और गैर-नेतृत्व योजनाएं

नेतृत्व (बेड़ा, बहु-पैक्सोस, ZAB): एक नेता रिकॉर्ड को क्रमबद्ध करता है - मानसिक और परिचालन रूप से आसान, एक स्थिर नेता पर बेहतर विलंबता।

लीडरलेस/मल्टी-लीडर (EPaxos, सीज़र): नेता के लिए अधिक समानतावाद और सहिष्णुता, लेकिन अधिक कठिन कार्यान्वयन और संघर्ष-समाधान; लाभ टीमों के छोटे संघर्षों के साथ दिखाई देता है।

7) क्लासिक सीएफटी एल्गोरिदम

7. 1 पैक्सोस/मल्टी-पैक्सोस (और अभ्यास)

विचार: दो चरण (तैयारी/प्रस्ताव), स्वीकर्ताओं के वादे, बहुमत कोरम। मल्टी-पैक्सोस एक "स्थिर नेता" छोड़ देता है और "वार्मिंग अप" के बाद ऑपरेशन को एक दौर (नई प्रविष्टियों के लिए) में बदल देता है।

• मॉडल को लागू करने के लिए लचीला लेकिन मुश्किल।
• विशेष प्रविष्टियों (संयुक्त आम सहमति) के माध्यम से पुन: कॉन्फ़िगरे
• व्यवहार में, पुस्तकालय/इंजन (चुब्बी/स्पैनर पीढ़ी)।

7. 2 बेड़ा

सीखने के लिए विघटित: नेता चयन, लॉग प्रतिकृति, पुन: कॉन्फ़िगरेशन।

चुनाव: यादृच्छिक समय, शब्द मतदान; एक नेता प्रति कार्यकाल।

परिशिष्ट: नेता रिकॉर्ड करता है, उपसर्ग (सूचकांक/शब्द) के मैच की निगरानी करता है, बहुमत निर्धारण के लिए प्रतिबद्ध है।

पढ़ें-पथ: लीज-रीड (एक मजबूत नेता के साथ) या रैखिक पढ़ ने के लिए रीड-इंडेक्स।

Reconfig: "संयुक्त" - स्विच करने से पहले दो समूहों में नोड्स वोट करते हैं।

पेशेवर: विकसित/डिबग करने में आसान, मजबूत क्रम अपरिवर्तनीय। विपक्ष: नेता एक दबाव बिंदु है।

7. 3 ZAB (ज़ूकीपर परमाणु प्रसारण )/दृश्य प्रतिकृति (VRR)

ZAB: नेता लेनदेन, वसूली चरण, zxid (युग + सूचकांक) प्रसारित करता है।

वीआरआर: भावना में मल्टी-पैक्सोस के समान एक प्राथमिक प्रतिकृति के साथ "विचार"।

8) गैर-नेता/बहु-नेता सीएफटी

8. 1 EPaxos

कोई स्थायी नेता नहीं है: कोई भी नोड एक कमांड शुरू कर सकता है।

संघर्ष टीमों को आंशिक आदेश मिलता है; संघर्ष-मुक्त - स्थानीय रूप से 1-2 आरटीटी के लिए प्रतिबद्ध।

कम संघर्ष के साथ भू-वितरण में लाभ, लेकिन जटिल निर्भरता/ग्राफ कोड।

8. 2 सीज़र, मेन्कियस

विविधताएं जो विलंबता/संतुलन और वान संचालन का अनुकूलन करती हैं।

9) बीएफटी एल्गोरिदम और पीओएस परिवार

9. 1 PBFT (व्यावहारिक BFT)

तीन चरण (पूर्व-तैयारी/तैयारी/प्रतिबद्ध), 3f + 1 नोड्स की आवश्यकता होती है।

स्थानीय नेटवर्क, बहु-चरण सड़ कों और ओ (एन ²) संदेशों पर कम विलंबता।

9. 2 टेंडरमिंट (BFT-PoS शैली)

प्रस्ताव और दो वोटों के साथ राउंड (रोक/प्रीकमिट)।

नियतात्मक वेलिडेटर-प्रस्तावक, टाइमआउट, आंशिक तुल्यकालिकता।

दर्जनों/सैकड़ों सत्यापनकर्ताओं के साथ अनुमत/पीओएस नेटवर्क के लिए अच्छा है।

9. 3 हॉटस्टफ (और डेरिवेटिव)

तीन-चरण योजना कोरम प्रमाणपत्र (QC) के साथ "पैकेज" में एकीकृत है।

संचार की रैखिक जटिलता, पैकेजिंग के लिए समर्थन और समानांतर पाइपलाइनिंग, ब्लॉकचेन में कार्यान्वयन के लिए सुविधाजनक है (उदाहरण के लिए, डायम/मूव इकोसिस्टम)।

दहलीज हस्ताक्षर के साथ, यातायात कम हो जाता है।

9. 4 PoW/संचयी सहमति (संक्षेप में)

सख्त अर्थों में बीएफटी नहीं, बल्कि संभाव्य अभिसरण (सबसे अधिक काम के साथ श्रृंखला)। लाभ: सादगी/खुलेपन; नुकसान: ऊर्जा, ~ सेकंड-मिनट अंतिम रूप से।

10) पढ़ ता है: रैखिक, अनुक्रमिक और कैश

रैखिक पढ़ ता है: सक्रिय पट्टे के साथ नेता या रीड-इंडेक्स (रफ) के माध्यम से → कोरम के माध्यम से पुष्टि।

अनुक्रमिक: किसी भी नोड से पढ़ा जा सकता है, लेकिन ताजगी की गारंटी के बिना।

अनुयायी पढ़ ता है: कमजोर आवश्यकताओं के तहत अनुमत; कैश के लिए - ठीक है।

11) पुन: विन्यास (क्लस्टर संरचना का परिवर्तन)

दो ओवरलैपिंग कॉन्फ़िगरेशन (संयुक्त आम सहमति) की आवश्यकता होती है: कोई भी कॉन्फ़िगरेशन "छेद" के बिना - दोनों कॉन्फ़िगरेशन के कोरम पास करता है।

एक बार में एक जोड़ें/हटाएँ, कोरम आकार देखें।

नेतृत्व हस्तांतरण ठहराव को कम करता है।

12) प्रदर्शन और ट्यूनिंग

12. 1 देरी

नेतृत्व एल्गोरिदम: 1 आरटीटी प्रति लिखना (एक स्थिर नेता के साथ) + प्रतिकृति।

भौगोलिक वितरण: WAN RTT हावी है - स्थानीय क्षेत्रों + क्रॉस-रीजनल प्रतिकृति या EPaxos/HotStufe दृष्टिकोण का उपयोग करें।

12. 2 थ्रूपुट

बैचिंग (आदेशों का समूह), समानांतर परिशिष्ट, लॉग पृष्ठ कैश, समानांतर अनुप्रयोग (जब संचालन स्विच किए जाते हैं)।

डिस्क: एक अलग डिवाइस पर एनवीएमई/लॉग, 'ओ _ डायरेक्ट '/एआईओ, एसएलए प्रतिबंधों (स्थायित्व/विलंबता समझौता) के साथ बड़े' fsync 'अंतराल।

12. 3 p99 पूंछ

गर्म समुद्री मील से बचें (हमेशा एक नेता होता है): अनुयायियों पर आवधिक रोटेशन या रीड-ऑफ़लोड।

GC ठहराव (JVM/Go), CPU पिन, NUMA की निगरानी करें।

13) भूगोल और स्थलाकृति

1 क्षेत्र, 3 क्षेत्र: क्लासिक सीएफटी क्लस्टर (एन = 3/5)।

2 क्षेत्र: बचें - 1-1 विभाजन पर कोई विश्वसनीय कोरम नहीं।

3 + क्षेत्र: "मध्य" या नेतृत्वहीन एल्गोरिदम में नेता; अतुल्यकालिक लॉग के साथ क्षेत्रीय प्रॉक्सी/स्थानीय मोर्चे संभव हैं।

14) ऑपरेशन के व्यावहारिक मुद्दे

14. 1 स्नैपशॉट और रिकवरी

पत्रिका के आकार/लेनदेन की संख्या द्वारा सीमा।

नए नोड्स में स्नैपशॉट का स्थानांतरण; चेकसम की जाँच करें।

14. 2 निगरानी

नेतृत्व: कौन नेता है, कितने शब्द (शब्द/युग) बदल गए हैं।

Лаги: 'एपेंड _ लेटेंसी', 'कमिट _ इंडेक्स - applied_index'।

कोरम स्वास्थ्य: "क्या अधिकांश जीवित/2f + 1 हैं?"

लॉग आकार/संपीड़न गति, स्नैपशॉट कतार।

बीएफटी के लिए: वोट शेयर, डंप हस्ताक्षरकर्ता, क्यूसी देरी

14. 3 कोड सुरक्षा/निरंतरता

तार पर प्रोटोकॉल संस्करण, लॉग संगतता के साथ पलायन।

बाहरी प्रभावों पर तलवारबाजी टोकन ("वितरित ताले" देखें): CRON/नौकरियों में स्थानांतरित करने के लिए लीड टाइम (शब्द)।

15) एंटी-पैटर्न

"फैशन की खातिर" सर्वसम्मति रखें जहां एक डीबीएमएस या कोरम बिना क्रमबद्धता के पढ़ ता है।

स्पष्ट सीमाओं (सीएपी) → अप्रत्याशित यूएक्स के बिना सीपी और एपी मिलाएं।

दर्जनों नोड्स (मुश्किल/महंगा) के साथ उद्यम कार्यों के लिए PoW/PoS को ओवरस्टाइम करें।

जब रचना बदलती है तो पुनः कॉन्फ़िगरेशन और "प्रतिच्छेदन कोरम" को अनदेखा करें।

रीड-बैरियर (लीज/रीड-इंडेक्स) का अभाव → गंदा पढ़ ता है।

2-नोड क्लस्टर चलाएं (कोई बहुमत नहीं)।

डिस्क और fsync को कम आंकना: "सब कुछ मेमोरी में उड़ ता है" - पहला रिबूट तक।

16) चयन जाँच सूची

1. विफलता मॉडल: सीएफटी (क्रैश) या बीएफटी (दुर्भावनापूर्ण)?

2. भूगोल: एक क्षेत्र/तीन क्षेत्र या वान? आरटीटी तय करता है।

3. शब्दार्थ पढ़ ना: क्या रैखिक रीडिंग आवश्यक है? लीज/रीड-इंडेक्स/फॉलो-अप।

4. लोड: p50/p99 द्वारा उम्मीदें, थ्रूपुट; क्या बहु-नेतृत्व की आवश्यकता है।

5. परिचालन जटिलता: पुस्तकालय/ऑफ-द-शेल्फ इंजन (etcd/ZK/Consul/Raft-libs) बनाम देशी कार्यान्वयन।

6. पुनर्निर्माण: अक्सर? हमें संयुक्त सर्वसम्मति और प्रवासन उपकरण चाहिए।

7. एकीकरण: बाहरी दुष्प्रभाव - क्या युग/शब्द द्वारा बाड़ लगाना है?

8. सुरक्षा: होस्ट सत्यापन, चैनल एनक्रिप्शन, प्रोटोकॉल संस्करण नियंत्रण।

9. टेस्ट प्लेबुक: विभाजन, जीसी-स्टॉप, किल लीडर, धीमी डिस्क, घड़ी तिरछा।

10. अवलोकन: लीडर/लैग्स/जर्नल और अलर्ट मैट्रिक्स स्थापित किए जाते हैं।

17) मिनी-गाइड: कब लेना है

डीसी के भीतर कॉन्फ़िगरेशन/लॉक/समन्वय के लिए etcd/Raft क्लस्टर।

ZK (पुराने ढेर, कतार, नेतृत्व) से बंधी सेवाओं के लिए ZooKeeper/ZAB।

अत्यधिक विशिष्ट प्रणालियों में एक तैयार-निर्मित सेवा/पुस्तकालय के माध्यम से मल्टी-पैक्सोस।

भू-वितरण और कम कमांड संघर्ष के लिए EPaxos।

सैकड़ों वैध और अंतिम आवश्यकताओं के लिए दसियों के साथ अनुमत नेटवर्क/पीओएस-परत के लिए टेंडरमिंट/हॉटस्टफ।

डायनामो-लाइक/सीआरडीटी जब सर्वसम्मति की आवश्यकता नहीं होती है, लेकिन बाद के विलय के साथ पहुंच/पैमाने महत्वपूर्ण है।

18) इंटरफेस के उदाहरण (छद्म)

18. 1 कमिट रिकॉर्ड (बेड़ाशैली)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18. रैखिक पढ़ ने के लिए 2 पढ़ें-सूचकांक (बेड़ा)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18. 3 संयुक्त विन्यास

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18. 4 बीएफटी (हॉटस्टफ अनुमानित)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) एफएक्यू

प्रश्न: दो समुद्री मील और एक टाई-ब्रेकर का उपयोग क्यों नहीं करें?

A: तीसरे मध्यस्थ के बिना दो नोड्स विभाजन में कोरम नहीं देते हैं। आपको ≥3 (CFT) या 3f + 1 (BFT) की आवश्यकता है।

प्रश्न: बेड़ा "सरल" पैक्सोस क्या है?

A: स्पष्ट अपघटन, लॉग और कॉन्फ़िगरेशन के समझने योग्य अपरिवर्तनीय; लागू करने और बनाए रखने में आसान।

प्रश्न: आप नेता को लोड किए बिना तेजी से कैसे पढ़ ते हैं?

A: गैर-महत्वपूर्ण, या लीज-रीड/रीड-इंडेक्स के लिए फॉलोवर-रीड (लगातार); कैश।

प्रश्न: p99 को क्या मारता है?

A: WAN-RTT, डिस्क fsync, GC-stops, overheted नेता, भीड़ के घंटे में बड़े स्नैपशॉट।

प्रश्न: क्या कैश/कैटलॉग को सर्वसम्मति की आवश्यकता है?

A: यदि पर्याप्त अंतिम स्थिरता - नहीं। यदि ट्रांजेक्शनल इनवेरिएंट की आवश्यकता है, तो हाँ।

20) कुल

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