Raft सहमति एल्गोरिद्म (2015)

 (raft.github.io)
3 पॉइंट द्वारा GN⁺ 2023-09-04 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • वितरित सिस्टम में कई servers को एक ही निर्णय तक पहुँचाने वाली consensus problem को अधिक समझने योग्य बनाने के लिए Raft डिज़ाइन किया गया था, और इसका लक्ष्य Paxos के बराबर fault tolerance और performance है
  • Raft, leader election, log replication और safety जैसी उप-समस्याओं में संरचना को बाँटकर replicated state machine लागू करने के लिए ज़रूरी निर्णय-बिंदुओं को स्पष्ट करता है
  • अगर servers का majority चालू है तो सिस्टम आगे बढ़ सकता है, और majority गायब होने पर रुक भी जाए तो गलत परिणाम न देकर safety बनाए रखता है
  • साइट पर browser-based RaftScope और The Secret Lives of Data visualization, Raft paper, TLA+ specification, verification/analysis papers और talks की सामग्री इकट्ठी है
  • Rust, Go, Java, C++, C#, Python आदि कई भाषाओं की implementations सूचीबद्ध हैं, और हर implementation में leader election/log replication, persistence, membership change और log compaction के support का दायरा अलग है

Raft जिस consensus problem को लक्ष्य करता है

  • Raft को इसलिए डिज़ाइन किया गया कि consensus algorithm को अधिक व्यापक पाठक वर्ग समझ सके
  • Fault tolerance और performance का लक्ष्य Paxos के बराबर स्तर का है
  • मुख्य अंतर संरचना में है
    • समस्या को अपेक्षाकृत स्वतंत्र उप-समस्याओं में बाँटना
    • वास्तविक सिस्टम implementation के लिए ज़रूरी components को अलग-अलग संभालना
  • लक्ष्य यह है कि consensus-based systems को समझना आसान हो और उन्हें अधिक गुणवत्ता के साथ implement किया जा सके

Consensus और replicated state machine

  • Consensus fault-tolerant distributed systems की बुनियादी समस्या है
  • कई servers एक value पर सहमत होते हैं, और एक बार तय हुई value अंतिम स्थिति बन जाती है
  • सामान्य consensus algorithms तब आगे बढ़ते हैं जब servers का majority उपलब्ध हो
    • 5 servers वाले cluster में 2 servers fail होने पर भी वह चलता रह सकता है
    • अगर इससे ज़्यादा servers fail हों तो progress रुक जाती है
    • तब भी गलत परिणाम return न करना महत्वपूर्ण है
  • Consensus का उपयोग आमतौर पर replicated state machine बनाने में होता है
    • हर server के पास एक state machine और log होता है
    • State machine, hash table जैसे किसी ऐसे component के रूप में हो सकता है जिसे fault tolerance देना हो
    • Client इसे ऐसे देख सकता है जैसे वह कुछ servers fail होने पर भी एक भरोसेमंद state machine से interact कर रहा हो
  • हर state machine अपने log से commands को input के रूप में लेती है
    • Hash table उदाहरण में set x to 3 जैसी command log में जाती है
    • Consensus algorithm तय करता है कि server logs में कौन-सी commands किस क्रम में डाली जाएँ
    • अगर किसी state machine ने set x to 3 को nवीं command के रूप में apply किया है, तो यह सुनिश्चित करना होगा कि दूसरी state machine उसी position पर कोई दूसरी command apply न करे
  • नतीजतन सभी state machines commands की वही sequence process करती हैं, और results तथा states की वही sequences तक पहुँचती हैं

Raft को समझने के लिए visualization

  • Browser में चलने वाले Raft cluster visualization को सीधे manipulate किया जा सकता है
    • बाईं ओर 5 servers दिखते हैं
    • दाईं ओर हर server का log दिखता है
    • User interact करके Raft का behavior देख सकता है
  • RaftScope में अभी सुधार की काफी गुंजाइश है और Pull Requests का स्वागत है
  • The Secret Lives of Data Raft को अलग तरीके से दिखाने वाला visualization है
    • यह ज्यादा guided है और interaction कम है
    • पहली बार पढ़ने वालों के लिए यह अधिक सहज शुरुआती बिंदु हो सकता है

Papers, specifications और verification सामग्री

Talks और educational material

  • Raft introduction के लिए talks की सूची भी साथ में整理 की गई है
    • John Ousterhout का CS@Illinois Distinguished Lecture Series talk, अगस्त 2016
    • Jin Li का Dr. TLA+ Series में Raft और TLA+ specification पर talk, जुलाई 2016
    • Diego Ongaro के Build Stuff 2015, CoreOS Fest 2015, Sourcegraph meetup, LinkedIn, USENIX ATC 2014, CraftConf 2014, RICON West 2013 talks
    • Ben Johnson का Strange Loop 2013 talk
    • John Ousterhout का Raft User Study lecture, मार्च 2013
  • Universities और educational courses में भी Raft को lecture या programming assignment के रूप में इस्तेमाल किया जाता है
    • University of Copenhagen, Czech Technical University in Prague, The University of Hong Kong, University of Virginia, UC San Diego, Technical University of Munich, UIUC आदि कई courses शामिल हैं
    • कुछ courses Go, Java, Erlang आदि में Raft programming assignments देते हैं
    • MIT 6.824 में Raft lecture notes शामिल हैं, और Jon Gjengset के instructors/students के लिए Raft लेखों की ओर भी मार्गदर्शन है
  • अतिरिक्त courses को site repository में Pull Request या issue के जरिए update किया जा सकता है

Question channels और implementations की सूची

  • Raft और implementations पर questions के लिए raft-dev Google group को उपयुक्त जगह बताया गया है
  • कुछ implementations की अपनी mailing lists हैं, इसलिए हर README देखना ज़रूरी है
  • Public source code वाली Raft implementations की सूची भी दी गई है
    • लोकप्रिय या हाल में update हुई implementations को table के ऊपर रखा गया है
    • जानकारी समय के साथ पुरानी हो सकती है, इसलिए Pull Request या issue के जरिए update की जा सकती है
  • Table में हर implementation के Stars, name, main author, language, license और feature support की तुलना की गई है
    • Feature items हैं leader election और log replication, persistence, membership change, log compaction
  • शीर्ष implementation examples इस प्रकार हैं
    • TiKV: Rust, Apache-2.0, 16,751★, leader election/log replication/persistence/membership change/log compaction सभी supported
    • RethinkDB: C++, Apache-2.0, 27,000★, सभी मुख्य features supported
    • Seastar Raft: C++20, AGPL, 15,624★, सभी मुख्य features supported
    • hashicorp/raft: Go, MPL-2.0, 9,048★, सभी मुख्य features supported
    • hazelcast-raft: Java, Apache-2.0, 6,579★, सभी मुख्य features supported
  • सूची में Rust, Go, Java, C++, C, Erlang, Python, Scala, C#, JavaScript, Haskell, OCaml, Kotlin, Zig, TypeScript, Elixir, F#, Shell आदि कई भाषाओं की implementations शामिल हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2023-09-04
Hacker News की राय

  • Jepsen के निर्माता का distributed systems सीखने के लिए बनाया गया वर्कबेंच Maelstrom Raft का एक सरल model-checking implementation और implementation tutorial अच्छी तरह शामिल करता है: https://github.com/jepsen-io/maelstrom/
    Raft एक सरल algorithm है, लेकिन मूल paper में correctness से जुड़ी बहुत-सी details हैं जिन्हें toy implementations में अक्सर छोड़ दिया जाता है
    असली hardware में memory/disk corruption और gray failures, कड़े latency SLA, flexible quorum और dynamic cluster membership तक को ध्यान में रखें तो production implementation लंबा और बोझिल काम बन जाता है
    सिर्फ etcd और hashicorp/raft की commit history देखने से भी पता चलता है कि सबसे ज्यादा verify किए गए open source Raft implementations में भी नियमित रूप से correctness bugs सामने आते रहते हैं
    TigerBeetle टीम imperfect hardware और abstraction-रहित system model में distributed systems की वास्तविकता को विस्तार से समझाती है, और यह भी बताती है कि उन्होंने Paxos से पुराना, लेकिन Raft से ज्यादा मिलता-जुलता दिखने वाला Viewstamped Replication क्यों चुना: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...

    • “Viewstamped Replication Paxos से पुराना है लेकिन Raft से ज्यादा मिलता-जुलता दिखता है” वाले हिस्से के संदर्भ में, Heidi Howard और Richard Mortier का Paxos vs Raft paper multi-consensus Paxos और Raft को बहुत करीब दिखाने के लिए साथ-साथ व्यवस्थित करके समझाता है: https://doi.org/10.1145/3380787.3393681
      implementation से जुड़ी चिंताओं पर इसका क्या असर पड़ता है, यह मुझे ठीक से नहीं पता, लेकिन paper खुद शानदार है, इसलिए recommend करना चाहूंगा
      एक talk भी है, लेकिन आगे-पीछे references देखकर पढ़ने के लिए मुझे text बेहतर लगता है: https://www.youtube.com/watch?v=0K6kt39wyH0
    • Viewstamped Replication paper आश्चर्यजनक रूप से पढ़ने में आसान था
      मैंने consensus algorithms पहले कभी नहीं देखे थे, फिर भी कुछ बार पढ़ने के बाद मैं कुछ हद तक follow कर पाया: https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
    • विषम network topology और यह तथ्य भी भूलना नहीं चाहिए कि कुछ members को leader बनाया जाए तो वे सचमुच बेहद खराब साबित होते हैं

  • हाल ही में मैंने Raft का leader election और log replication implement करके देखा; snapshots/checkpoints तक नहीं पहुंच पाया, लेकिन अब तक किए गए projects में यह सबसे कठिन में से एक था
    Raft paper पढ़ने में आसान है और intuition अच्छी तरह देता है
    सीधे implement न भी करें, तो संभव है कि आप पहले से ही etcd, Consul, CockroachDB, TiDB जैसे Raft-based software इस्तेमाल कर रहे हों
    implementation के दौरान काम आए resources मैंने यहां इकट्ठे किए हैं: https://github.com/eatonphil/goraft#references
    इसमें Diego Ongaro की PhD thesis और TLA+ specification भी शामिल हैं
    कुछ लोग कहते हैं “Raft paper का Figure 2 ही काफी है”, लेकिन TLA+ specification से तुलना करें तो वह कहीं ज्यादा ambiguous है, इसलिए मुझे यह बात सही नहीं लगती

    • देखने में अच्छा है, लेकिन सच में comprehensive test suite न हो तो subtle bugs बहुत ज्यादा होने ही हैं
      MIT distributed systems course के Raft tests से जोड़कर देखने की सलाह दूंगा: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
      कम से कम leader election और log replication वाले हिस्से थोड़ी refactoring से संभव लगते हैं
    • undergraduate network programming class में हमें Raft implement करना पड़ा था, और paper पढ़ने में आसान है—इस पर मेरा भी वही अनुभव रहा
      खासकर distributed algorithms पहली बार सीखने वालों के लिए यह सचमुच recommend करने लायक है
      implementation quality बहुत शानदार नहीं होगी, लेकिन interested लोगों के लिए यहां डाल रखा है: https://github.com/skowalak/fastapi-raft/
    • Figure 2 शानदार है, लेकिन मैं सहमत हूं कि Raft implement करने के लिए पूरा paper चाहिए
      implementation के लिए जरूरी कुछ और specific details paper में मौजूद हैं

  • अगर consensus algorithms में रुचि है, तो distributed systems theory class में इस्तेमाल की गई Reasoning about Knowledge नाम की किताब भी देखने लायक है: https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...
    modal logic सीखने में थोड़ा investment चाहिए, लेकिन वह हिस्सा पार करने के बाद Raft या Paxos क्यों काम करते हैं, इसके proofs बहुत intuitive और simple हो जाते हैं
    यह proof की complexity को proof में इस्तेमाल होने वाले logical structure के भीतर धकेलने का तरीका है, और इसने consensus को देखने का मेरा नजरिया बदल दिया

  • “Raft Consensus Algorithm Failure”, Théodore Géricault, 1819: https://classicprogrammerpaintings.com/post/6141087496359280...

    • Raft के पास TLA+ proof है, तो “bug-free” होना चाहिए; मजाक है यह समझता हूं, लेकिन सच में इसमें कोई error है क्या, यह जानने की उत्सुकता है

  • अगर आपको समझ नहीं आ रहा कि visualization क्या दिखा रहा है, तो बस यह देखिए कि आप किसी एक node पर क्लिक करके उसमें failure पैदा कर सकते हैं
    खास तौर पर मौजूदा leader पर आज़माना अच्छा है, जो सभी packets भेजता और प्राप्त करता है
    पहले slider के बगल में छोटे pause icon को दबाकर उसे फिर से clock में बदल दें, तो simulation फिर से शुरू हो जाता है
    दाईं ओर वाली spreadsheet क्या है, यह अभी नहीं पता; वह हमेशा खाली रहती है, इसलिए टूटी हुई लगती है
    अब तक जो clickable elements मिले हैं वे हैं दो sliders, clock/pause icon, और अलग-अलग servers

    • दाईं ओर की table हर replica की log state दिखाती है
      leader पर क्लिक करके request चुनें, तो command भेजने का simulation किया जा सकता है
      किसी एक replica को offline कर दें, तो वह पीछे रह जाता है, और वापस आने पर उसे catch up करते हुए देखा जा सकता है

  • कुछ साल पहले मैं ऐसे माहौल में था जहाँ बहुत भारी load में भी मजबूत Chubby जैसा system बेहद महत्वपूर्ण था, और तब failure बर्दाश्त न हो तो ZooKeeper इस्तेमाल किया जाता था
    लेकिन अब मेरी समझ है कि लोग सालों से etcd, Consul जैसे Raft-based विकल्पों पर बहुत भारी workloads चला रहे हैं
    जिज्ञासा है कि क्या इनमें से कोई अब default choice बन गया है
    Raft की conceptual clarity और elegance शायद performance और reliability में बदलती होगी, लेकिन इस क्षेत्र की मेरी समझ पुरानी हो चुकी है
    2023 में, जो लोग Google या GCP से बंधे नहीं हैं, वे high-criticality systems में default best practice के तौर पर क्या इस्तेमाल करते हैं, यह जानना चाहूँगा
    लगता है TikV वालों ने production-grade Rust Raft implementation बनाई थी, और एक मजबूत, high-performance lock server Rust के लिए काफी उपयुक्त क्षेत्र लगता है; यह भी जानना चाहूँगा कि क्या वह वास्तव में इस्तेमाल हो रहा है

  • अगर “Raft क्या है?” का जवाब यह है, तो पढ़ने के बाद भी मुझे अभी तक समझ नहीं आया
    “Raft एक consensus algorithm है जिसे समझने में आसान बनाने के लिए design किया गया है। fault tolerance और performance के मामले में यह Paxos के बराबर है। फर्क यह है कि इसे अपेक्षाकृत independent subproblems में तोड़ा गया है, और practical systems के लिए जरूरी मुख्य हिस्सों को साफ़-सुथरे ढंग से संभालता है। हमें उम्मीद है कि Raft consensus को व्यापक पाठक-वर्ग तक पहुँचाएगा, और वह पाठक-वर्ग आज की तुलना में अधिक विविध, high-quality consensus-based systems बना सकेगा”
    इस तरह की बात सिर्फ इन्हीं की समस्या नहीं है, लेकिन मुझे अफसोस है कि लोग अपने काम को ठीक से समझाने में और समय नहीं लगाते

    • यह explanation उल्टा अच्छी explanation भी हो सकती है
      क्योंकि यह उन readers को अपने-आप filter कर देती है जिन्हें इसका मतलब नहीं पता
      जो लोग distributed systems बनाते हुए कई consensus algorithms की तुलना कर रहे हैं, उनके लिए यह सरल और स्पष्ट explanation है; और अगर ऐसा नहीं है, तो शायद यह algorithm आपके लिए relevant वैसे भी नहीं है
      आम तौर पर consensus algorithms उस समस्या को हल करने की कोशिश करते हैं जहाँ कई physical devices पर data store की replicas होती हैं, और जब कुछ devices या connections किसी तरीके से fail हो जाते हैं तो क्या करना है, यह तय करना होता है
      इसे “consensus” इसलिए कहा जाता है क्योंकि failure की स्थिति में data के किसी हिस्से के बारे में machines को सहमत होना पड़ता है कि क्या decision लिया जाए
      उदाहरण के लिए, अगर तीन servers एक ही SQL database को replicate कर रहे हैं और उनका रूप (A) - (B) - (C) है, तो C और बाकी दोनों के बीच network connection टूटने पर A और B यह जानकर B को primary node के रूप में promote कर सकते हैं
      लेकिन C को पता नहीं कि क्या हुआ है और वह कुछ writes लेते रह सकता है
      connection restore होने पर A, B, C को अब तय करना होगा कि आगे क्या करना है
      क्योंकि B और C ने अलग-अलग write sets स्वतंत्र रूप से लिए हैं, servers को data handle करने के तरीके पर consensus बनाना होगा
      Raft, Paxos वगैरह यही समस्या consistent और performant तरीके से हल करने की कोशिश करते हैं
    • जिज्ञासा है कि क्या आपने अगला paragraph, “रुकिए, consensus क्या है?” तक पढ़ा था
      कुछ concepts इतने बड़े होते हैं कि बिना किसी background knowledge वाले व्यक्ति को एक paragraph में introduce नहीं किए जा सकते
      फिर भी, linked article को आगे पढ़ें तो यह बेहतरीन introductory material लगता है

  • consensus protocols के researcher के तौर पर, मेरा मानना है कि पिछले 10 साल की blockchain research की वजह से consensus कहीं ज्यादा समझने लायक हो गया है
    उसकी तुलना में Raft, खासकर subtle हिस्सों सहित, Greek जैसा पढ़ा और implement किया जाता है
    अगर कोई अभी consensus protocols पहली बार सीख रहा हो, तो मैं उसे Bitcoin से शुरू कराकर Paxos, Tendermint, Simplex तक ले जाऊँगा, और Raft को पूरी तरह skip करवाऊँगा
    Simplex मेरा लिखा paper है, जो PBFT का simplified version है

    • मैं consensus protocol researcher नहीं हूँ, लेकिन blockchain बहुत सारे extra elements, complexity और cost लाती दिखती है
      Raft अपेक्षाकृत सरल लगता है
      “leader चुनो और log replicate करो” की तुलना में blockchain ऐसा क्या देती है जो maintain करना आसान और गलती करना मुश्किल बनाता है, यह जानना चाहूँगा

  • मुझे यह site पसंद है
    distributed systems की class में Raft सीखते और implement करते समय यह page सचमुच उपयोगी था
    paper खुद भी काफी पढ़ने में आसान है

    • मैं distributed systems की class पढ़ाता हूँ, और इस site को reference materials में से एक के तौर पर इस्तेमाल करता हूँ
      Raft को इतना स्पष्ट बनाने के लिए धन्यवाद

  • क्या ऐसे consensus algorithms हैं जिनमें बदलावों को अनिवार्य रूप से leader के जरिए ही जाना न पड़े—यह जिज्ञासा है
    कई distributed systems में input processing को भी distribute करना चाहते हैं

    • कुछ algorithms high fault tolerance को प्राथमिकता देते हैं, और इसके लिए leaders की संख्या या query data की copies रखने वाले minimum nodes की संख्या बढ़ाते हैं
      उनमें से एक Chord है: https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)
      Chord एक P2P ring है जिसमें nodes consistent hashing से values को आपस में बाँटते हैं
      network “finger table” नाम की चीज़ का उपयोग करता है, जो मूल रूप से replication information को table के रूप में store करती है
      इस table की जानकारी गलत या पुरानी हो सकती है, और जिस peer को access किया गया है वह आपको किसी दूसरे peer—आमतौर पर next node या successor node—के पास जाने को कह सकता है, और यह तब तक चलता है जब तक value मिल न जाए या यह तय न हो जाए कि वह नहीं मिली
      यह algorithm “leader” के बिना भी इस्तेमाल हो सकता है क्योंकि यह सिर्फ किसी एक node पर जाकर सभी nodes को linear तरीके से scan करने पर भी काम करता है
      queries को तेज़ करने के लिए finger table अनिवार्य नहीं है
    • literature में leaderless protocols मौजूद हैं: EPaxos, Caesar, Tempo आदि
      ऐसे systems में आम तौर पर हर transaction के लिए एक “leader” होता है, लेकिन normal operation में उस role के लिए competition नहीं होती
      transaction coordinator खुद को declare करता है, इसलिए election केवल तब होती है जब coordinator किसी कारण से fail हो जाए
      किसी खास data या key के लिए कई leaders एक साथ मौजूद भी हो सकते हैं
      Cassandra अभी Accord विकसित कर रहा है, जो इसी category का leaderless protocol है
      दरअसल Cassandra पहले से ही LWT में leaderless protocol का इस्तेमाल कर रहा है
      यह classic single-consensus Paxos का optimized variant है, लेकिन अगर same key के लिए competing transactions एक साथ declare हों, तो overhead काफी अधिक होता है
    • leader चुनना और changes को leader के जरिए भेजना system को सरल बनाता है, और contention होने पर throughput और predictability बेहतर होती है
      अगर transactions independent topics में बँटे हों, तो leaders को shard करके load distribute किया जा सकता है
      इसमें key-space ranges को अलग-अलग leaders को assign किया जाता है और elections को इस तरह tune किया जाता है कि हर node के पास leadership का उचित हिस्सा हो
      अगर leaderless जाना हो, तो हर write को लगभग एक election की तरह structure किया जा सकता है
      tentative transaction या transaction बड़ी हो तो transaction request को सभी nodes पर broadcast करके, acceptance quorum मिलने पर जीतकर commit करने जैसा तरीका होता है
      लेकिन अगर कई nodes लगभग एक ही समय पर transaction करने की कोशिश करें, तो consensus में काफी समय लग सकता है
      अगर nodes बहुत हैं और सभी के पास same topic पर pending transactions हैं, तो leader चुनकर सभी transactions को leader के जरिए भेजना हर transaction के लिए अलग consensus बनाने की तुलना में बहुत तेज़ होता है
    • Paxos किसी भी node को दूसरे node से ज़्यादा preference नहीं देता
      लेकिन अगर मकसद throughput के लिए distribute करना है, तो Paxos द्वारा मांगे गए quorum की तुलना में केवल एक leader चाहिए वाला तरीका अधिक efficient हो सकता है
      यह हालांकि अनुमान है
      Paxos भी तब ज़्यादा efficient होता है जब calls हर बार उसी जगह जाएँ
      क्योंकि इससे contention और re-voting आदि से बचा जा सकता है
    • shard-wise Paxos और shardmaster का इस्तेमाल करने का तरीका भी है
      मूल रूप से हर shard का अपना Paxos consensus होता है