కాబట్టి, ఊహించుకుందాం. గదిలో 5 పిల్లులు లాక్ చేయబడ్డాయి మరియు యజమానిని మేల్కొలపడానికి, వారందరూ తమలో తాము ఈ విషయాన్ని అంగీకరించాలి, ఎందుకంటే వారు ఐదుగురు దానిపై వాలుతూ మాత్రమే తలుపు తెరవగలరు. పిల్లులలో ఒకటి ష్రోడింగర్ యొక్క పిల్లి అయితే, మరియు ఇతర పిల్లులకు అతని నిర్ణయం గురించి తెలియకపోతే, ప్రశ్న తలెత్తుతుంది: "అవి ఎలా చేయగలవు?"
ఈ ఆర్టికల్లో, పంపిణీ చేయబడిన వ్యవస్థల ప్రపంచం యొక్క సైద్ధాంతిక భాగం మరియు వాటి ఆపరేషన్ సూత్రాల గురించి నేను మీకు సరళంగా చెబుతాను. నేను పాక్సోస్‌లో ఉన్న ప్రధాన ఆలోచనను కూడా ఉపరితలంగా పరిశీలిస్తాను.
డెవలపర్‌లు క్లౌడ్ ఇన్‌ఫ్రాస్ట్రక్చర్‌లను, వివిధ డేటాబేస్‌లను ఉపయోగించినప్పుడు మరియు పెద్ద సంఖ్యలో నోడ్‌ల క్లస్టర్‌లలో పని చేసినప్పుడు, డేటా పూర్తిగా, సురక్షితంగా మరియు ఎల్లప్పుడూ అందుబాటులో ఉంటుందని వారు విశ్వసిస్తారు. అయితే హామీలు ఎక్కడివి?
ముఖ్యంగా, మా వద్ద ఉన్న హామీలు సరఫరాదారు హామీలు. అవి ఈ క్రింది విధంగా డాక్యుమెంటేషన్‌లో వివరించబడ్డాయి: "ఈ సేవ చాలా నమ్మదగినది, దీనికి ఇచ్చిన SLA ఉంది, చింతించకండి, మీరు ఆశించిన విధంగా ప్రతిదీ పంపిణీ చేయబడుతుంది."
మేము ఉత్తమమైన వాటిని నమ్ముతాము, ఎందుకంటే పెద్ద కంపెనీల నుండి తెలివైన వ్యక్తులు ప్రతిదీ చక్కగా ఉంటుందని మాకు హామీ ఇచ్చారు. మేము ప్రశ్న అడగము: వాస్తవానికి, ఇది ఎందుకు పని చేయగలదు? అటువంటి వ్యవస్థల యొక్క సరైన ఆపరేషన్ కోసం ఏదైనా అధికారిక సమర్థన ఉందా?
నేను ఇటీవల వెళ్ళాను మరియు ఈ అంశం ద్వారా చాలా ప్రేరణ పొందారు. పాఠశాలలో ఉపన్యాసాలు కంప్యూటర్ సిస్టమ్‌లకు సంబంధించిన వాటి కంటే కాలిక్యులస్ తరగతుల లాగా ఉంటాయి. కానీ మనకు తెలియకుండానే మనం ప్రతిరోజూ ఉపయోగించే అతి ముఖ్యమైన అల్గారిథమ్‌లు ఒకప్పుడు ఎలా నిరూపించబడ్డాయి.
చాలా ఆధునిక పంపిణీ వ్యవస్థలు పాక్సోస్ ఏకాభిప్రాయ అల్గోరిథం మరియు దాని వివిధ మార్పులను ఉపయోగిస్తాయి. చక్కని విషయం ఏమిటంటే చెల్లుబాటు మరియు సూత్రప్రాయంగా, ఈ అల్గోరిథం యొక్క ఉనికి యొక్క సంభావ్యత కేవలం పెన్ మరియు కాగితంతో నిరూపించబడుతుంది. ఆచరణలో, అల్గోరిథం మేఘాలలో భారీ సంఖ్యలో నోడ్లపై నడుస్తున్న పెద్ద వ్యవస్థలలో ఉపయోగించబడుతుంది.
తరువాత చర్చించబడే దాని యొక్క తేలికపాటి ఉదాహరణ: ఇద్దరు జనరల్స్ యొక్క పనిఒక వేడెక్కడం కోసం చూద్దాం .
మాకు రెండు సైన్యాలు ఉన్నాయి - ఎరుపు మరియు తెలుపు. ముట్టడి చేయబడిన నగరంలో తెల్ల దళాలు ఉన్నాయి. జనరల్స్ A1 మరియు A2 నేతృత్వంలోని రెడ్ దళాలు నగరం యొక్క రెండు వైపులా ఉన్నాయి. రెడ్‌హెడ్‌ల పని తెల్ల నగరంపై దాడి చేసి గెలవడమే. ఏదేమైనా, ప్రతి ఎర్ర సైన్యం వ్యక్తిగతంగా తెల్ల సైన్యం కంటే చిన్నది.
ఎరుపు రంగు వారికి విజయ పరిస్థితులు: శ్వేతజాతీయులపై సంఖ్యాపరమైన ప్రయోజనాన్ని పొందడానికి జనరల్‌లు ఇద్దరూ ఒకే సమయంలో దాడి చేయాలి. దీన్ని చేయడానికి, జనరల్స్ A1 మరియు A2 పరస్పరం ఒక ఒప్పందానికి రావాలి. అందరూ విడివిడిగా దాడి చేస్తే, ఎర్రగడ్డలు నష్టపోతారు.
ఒక ఒప్పందాన్ని చేరుకోవడానికి, జనరల్స్ A1 మరియు A2 తెల్లటి నగరం యొక్క భూభాగం ద్వారా ఒకరికొకరు దూతలను పంపుకోవచ్చు. మెసెంజర్ విజయవంతంగా మిత్రరాజ్యాల జనరల్‌ని చేరుకోవచ్చు లేదా శత్రువు ద్వారా అడ్డగించబడవచ్చు. ప్రశ్న: రెడ్ హెయిర్డ్ జనరల్స్ (A1 నుండి A2కి మెసెంజర్‌లను పంపే క్రమం మరియు A2 నుండి A1కి వైస్ వెర్సా) మధ్య కమ్యూనికేషన్‌ల యొక్క అటువంటి క్రమం ఉందా, దీనిలో వారు గంట X వద్ద దాడికి అంగీకరిస్తారని హామీ ఇవ్వబడింది. ఇక్కడ, హామీలు అంటే మిత్రుడు (మరొక జనరల్) నిర్ణీత సమయంలో X వద్ద ఖచ్చితంగా దాడి చేస్తారని ఇద్దరు జనరల్‌లు నిస్సందేహంగా నిర్ధారిస్తారు.
“ఈ రోజు అర్ధరాత్రి దాడి చేద్దాం!” అనే సందేశంతో A1 ఒక మెసెంజర్‌ను A2కి పంపిందని అనుకుందాం. జనరల్ A1 నుండి నిర్ధారణ లేకుండా జనరల్ A2 దాడి చేయదు. A1 నుండి మెసెంజర్ వచ్చినట్లయితే, జనరల్ A2 సందేశంతో ధృవీకరణను పంపుతుంది: "అవును, ఈ రోజు శ్వేతజాతీయులను చంపుదాం." కానీ ఇప్పుడు జనరల్ A2కి తన మెసెంజర్ వచ్చాడో లేదో తెలియదు, దాడి ఏకకాలంలో జరుగుతుందా అనే గ్యారెంటీ అతనికి లేదు. ఇప్పుడు జనరల్ A2కి మళ్లీ నిర్ధారణ అవసరం.
మేము వారి కమ్యూనికేషన్‌ను మరింతగా వివరిస్తే, ఎన్ని సందేశ మార్పిడి చక్రాలు ఉన్నప్పటికీ, జనరల్‌లు ఇద్దరూ తమ సందేశాలను అందుకున్నారని హామీ ఇవ్వడానికి మార్గం లేదని స్పష్టమవుతుంది (మెసెంజర్‌ను అడ్డగించవచ్చని ఊహిస్తే).
టూ జనరల్స్ సమస్య చాలా సులభమైన పంపిణీ వ్యవస్థ యొక్క గొప్ప ఉదాహరణ, ఇక్కడ అవిశ్వసనీయమైన కమ్యూనికేషన్‌తో రెండు నోడ్‌లు ఉన్నాయి. దీనర్థం అవి సమకాలీకరించబడినట్లు మాకు 100% హామీ లేదు. ఇలాంటి సమస్యలు వ్యాసంలో తరువాత పెద్ద స్థాయిలో మాత్రమే చర్చించబడతాయి.
మేము పంపిణీ వ్యవస్థల భావనను పరిచయం చేస్తున్నాము
పంపిణీ చేయబడిన వ్యవస్థ అనేది సందేశాలను మార్పిడి చేయగల కంప్యూటర్ల సమూహం (ఇకపై వాటిని నోడ్స్ అని పిలుస్తాము). ప్రతి వ్యక్తి నోడ్ ఒక రకమైన స్వయంప్రతిపత్త సంస్థ. ఒక నోడ్ దాని స్వంత పనులను ప్రాసెస్ చేయగలదు, కానీ ఇతర నోడ్‌లతో కమ్యూనికేట్ చేయడానికి, అది సందేశాలను పంపడం మరియు స్వీకరించడం అవసరం.
సందేశాలు ఎలా సరిగ్గా అమలు చేయబడతాయి, ఏ ప్రోటోకాల్‌లు ఉపయోగించబడతాయి - ఈ సందర్భంలో ఇది మాకు ఆసక్తి లేదు. పంపిణీ చేయబడిన సిస్టమ్ యొక్క నోడ్‌లు సందేశాలను పంపడం ద్వారా ఒకదానితో ఒకటి డేటాను మార్పిడి చేసుకోగలవు.
నిర్వచనం చాలా క్లిష్టంగా కనిపించడం లేదు, కానీ పంపిణీ చేయబడిన వ్యవస్థ మనకు ముఖ్యమైన అనేక లక్షణాలను కలిగి ఉందని మనం పరిగణనలోకి తీసుకోవాలి.
పంపిణీ వ్యవస్థల లక్షణాలు
- అనుకూలత - వ్యవస్థలో ఏకకాలంలో లేదా ఏకకాలిక సంఘటనలు సంభవించే అవకాశం. అంతేకాకుండా, ఈ ఈవెంట్‌ల సంభవించే స్పష్టమైన క్రమం లేనంత వరకు రెండు వేర్వేరు నోడ్‌లలో సంభవించే ఈవెంట్‌లను సమర్ధవంతంగా ఉండేలా మేము పరిగణిస్తాము. కానీ, ఒక నియమంగా, మాకు అది లేదు.
- ప్రపంచ గడియారం లేదు. గ్లోబల్ క్లాక్ లేకపోవడం వల్ల మాకు ఈవెంట్‌ల స్పష్టమైన క్రమం లేదు. సాధారణ ప్రజల ప్రపంచంలో, మనకు గడియారాలు మరియు సమయం ఖచ్చితంగా ఉన్నాయని మనం అలవాటు పడ్డాము. పంపిణీ వ్యవస్థల విషయానికి వస్తే ప్రతిదీ మారుతుంది. అత్యంత ఖచ్చితమైన పరమాణు గడియారాలు కూడా డ్రిఫ్ట్ కలిగి ఉంటాయి మరియు రెండు సంఘటనలలో ఏది మొదట జరిగిందో చెప్పలేని పరిస్థితులు ఉండవచ్చు. అందువల్ల, మనం కూడా సమయంపై ఆధారపడలేము.
- సిస్టమ్ నోడ్స్ యొక్క స్వతంత్ర వైఫల్యం. మరొక సమస్య ఉంది: మా నోడ్‌లు శాశ్వతంగా ఉండవు కాబట్టి ఏదో తప్పు జరగవచ్చు. హార్డ్ డ్రైవ్ విఫలం కావచ్చు, క్లౌడ్‌లోని వర్చువల్ మెషీన్ రీబూట్ కావచ్చు, నెట్‌వర్క్ బ్లింక్ కావచ్చు మరియు సందేశాలు పోతాయి. అంతేకాకుండా, నోడ్స్ పని చేసే పరిస్థితులు ఉండవచ్చు, కానీ అదే సమయంలో సిస్టమ్కు వ్యతిరేకంగా పని చేస్తాయి. సమస్యల యొక్క చివరి తరగతికి ప్రత్యేక పేరు కూడా వచ్చింది: సమస్య . ఈ సమస్యతో పంపిణీ చేయబడిన వ్యవస్థ యొక్క అత్యంత ప్రజాదరణ పొందిన ఉదాహరణ Blockchain. కానీ ఈ రోజు మనం ఈ ప్రత్యేక తరగతి సమస్యలను పరిగణించము. ఒకటి లేదా అంతకంటే ఎక్కువ నోడ్‌లు విఫలమయ్యే పరిస్థితులపై మేము ఆసక్తి కలిగి ఉంటాము.
- నోడ్‌ల మధ్య కమ్యూనికేషన్ మోడల్‌లు (మెసేజింగ్ మోడల్‌లు).. సందేశాలను మార్పిడి చేయడం ద్వారా నోడ్‌లు కమ్యూనికేట్ చేస్తాయని మేము ఇప్పటికే నిర్ధారించాము. రెండు ప్రసిద్ధ సందేశ నమూనాలు ఉన్నాయి: సింక్రోనస్ మరియు అసమకాలిక.
పంపిణీ వ్యవస్థలలో నోడ్‌ల మధ్య కమ్యూనికేషన్ యొక్క నమూనాలు
సిన్క్రోనస్ మోడల్ - ఒక సందేశం ఒక నోడ్ నుండి మరొక నోడ్‌కు చేరుకోవడానికి హామీ ఇవ్వబడే పరిమిత డెల్టా సమయం ఉందని మాకు ఖచ్చితంగా తెలుసు. ఈ సమయం గడిచిపోయి, సందేశం రాకపోతే, నోడ్ విఫలమైందని మేము సురక్షితంగా చెప్పగలం. ఈ మోడల్‌లో మేము ఊహించదగిన నిరీక్షణ సమయాలను కలిగి ఉన్నాము.
అసమకాలిక నమూనా - అసమకాలిక నమూనాలలో నిరీక్షణ సమయం పరిమితం అని మేము పరిగణిస్తాము, అయితే నోడ్ విఫలమైందని మేము హామీ ఇవ్వగల సమయం యొక్క డెల్టా లేదు. ఆ. నోడ్ నుండి సందేశం కోసం వేచి ఉండే సమయం ఏకపక్షంగా ఎక్కువ కాలం ఉంటుంది. ఇది ఒక ముఖ్యమైన నిర్వచనం, మరియు మేము దాని గురించి మరింత మాట్లాడతాము.
పంపిణీ వ్యవస్థలలో ఏకాభిప్రాయం యొక్క భావన
ఏకాభిప్రాయ భావనను అధికారికంగా నిర్వచించే ముందు, మనకు అవసరమైన పరిస్థితి యొక్క ఉదాహరణను పరిశీలిద్దాం, అవి - స్టేట్ మెషిన్ రెప్లికేషన్.
మా వద్ద కొంత పంపిణీ లాగ్ ఉంది. పంపిణీ చేయబడిన సిస్టమ్ యొక్క అన్ని నోడ్‌లలో ఇది స్థిరంగా మరియు ఒకే డేటాను కలిగి ఉండాలని మేము కోరుకుంటున్నాము. నోడ్‌లలో ఒకటి లాగ్‌కు వ్రాయబోయే కొత్త విలువను తెలుసుకున్నప్పుడు, దాని పని అన్ని ఇతర నోడ్‌లకు ఈ విలువను అందించడం అవుతుంది, తద్వారా లాగ్ అన్ని నోడ్‌లలో నవీకరించబడుతుంది మరియు సిస్టమ్ కొత్త స్థిరమైన స్థితికి వెళుతుంది. ఈ సందర్భంలో, నోడ్‌లు తమలో తాము అంగీకరించడం ముఖ్యం: ప్రతిపాదిత కొత్త విలువ సరైనదని అన్ని నోడ్‌లు అంగీకరిస్తాయి, అన్ని నోడ్‌లు ఈ విలువను అంగీకరిస్తాయి మరియు ఈ సందర్భంలో మాత్రమే ప్రతి ఒక్కరూ లాగ్‌కు కొత్త విలువను వ్రాయగలరు.
మరో మాటలో చెప్పాలంటే: నోడ్‌లలో ఏదీ అది మరింత సంబంధిత సమాచారాన్ని కలిగి ఉందని అభ్యంతరం చెప్పలేదు మరియు ప్రతిపాదిత విలువ తప్పు. నోడ్‌ల మధ్య ఒప్పందం మరియు ఒకే సరైన ఆమోదించబడిన విలువపై ఒప్పందం పంపిణీ వ్యవస్థలో ఏకాభిప్రాయం. తరువాత, పంపిణీ చేయబడిన వ్యవస్థ ఏకాభిప్రాయాన్ని చేరుకోవడానికి హామీ ఇవ్వడానికి అనుమతించే అల్గారిథమ్‌ల గురించి మేము మాట్లాడుతాము.
మరింత అధికారికంగా, మేము ఏకాభిప్రాయ అల్గారిథమ్‌ను (లేదా కేవలం ఏకాభిప్రాయ అల్గారిథమ్) ఒక నిర్దిష్ట విధిగా నిర్వచించవచ్చు, ఇది పంపిణీ చేయబడిన సిస్టమ్‌ను స్థితి A నుండి స్థితి Bకి బదిలీ చేస్తుంది. అంతేకాకుండా, ఈ స్థితి అన్ని నోడ్‌లచే ఆమోదించబడుతుంది మరియు అన్ని నోడ్‌లు దానిని నిర్ధారించగలవు. ఇది ముగిసినట్లుగా, ఈ పని మొదటి చూపులో కనిపించేంత చిన్నవిషయం కాదు.
ఏకాభిప్రాయ అల్గోరిథం యొక్క లక్షణాలు
ఏకాభిప్రాయ అల్గోరిథం వ్యవస్థ ఉనికిలో కొనసాగడానికి మరియు రాష్ట్రం నుండి రాష్ట్రానికి వెళ్లడంలో కొంత పురోగతిని కలిగి ఉండటానికి మూడు లక్షణాలను కలిగి ఉండాలి:
- ఒప్పందం - సరిగ్గా పనిచేసే అన్ని నోడ్‌లు తప్పనిసరిగా ఒకే విలువను తీసుకోవాలి (వ్యాసాలలో ఈ ఆస్తిని భద్రతా ఆస్తిగా కూడా సూచిస్తారు). ప్రస్తుతం పనిచేస్తున్న అన్ని నోడ్‌లు (ఇతరులతో విఫలమవ్వలేదు లేదా సంబంధాన్ని కోల్పోలేదు) తప్పనిసరిగా ఒక ఒప్పందానికి వచ్చి కొంత తుది సాధారణ విలువను అంగీకరించాలి.
మేము పరిశీలిస్తున్న డిస్ట్రిబ్యూషన్ సిస్టమ్‌లోని నోడ్‌లు అంగీకరించాలని ఇక్కడ అర్థం చేసుకోవడం ముఖ్యం. అంటే, మనం ఇప్పుడు ఏదో విఫలమయ్యే వ్యవస్థల గురించి మాట్లాడుతున్నాము (ఉదాహరణకు, కొన్ని నోడ్ విఫలమవుతుంది), కానీ ఈ వ్యవస్థలో ఉద్దేశపూర్వకంగా ఇతరులకు వ్యతిరేకంగా పనిచేసే నోడ్‌లు ఖచ్చితంగా లేవు (బైజాంటైన్ జనరల్స్ యొక్క పని). ఈ ఆస్తి కారణంగా, సిస్టమ్ స్థిరంగా ఉంటుంది.
- <span style="font-family: Mandali; "> సమగ్రత </span> — సరిగ్గా పని చేసే అన్ని నోడ్‌లు ఒకే విలువను అందిస్తే v, అంటే సరిగ్గా పనిచేసే ప్రతి నోడ్ తప్పనిసరిగా ఈ విలువను అంగీకరించాలి v.
- తొలగింపులు - సరిగ్గా పనిచేసే అన్ని నోడ్‌లు చివరికి ఒక నిర్దిష్ట విలువను (లైవ్‌నెస్ ప్రాపర్టీ) తీసుకుంటాయి, ఇది అల్గోరిథం సిస్టమ్‌లో పురోగతిని సాధించడానికి అనుమతిస్తుంది. ప్రతి వ్యక్తి సరిగ్గా పనిచేసే నోడ్ త్వరగా లేదా తరువాత తుది విలువను అంగీకరించాలి మరియు దానిని నిర్ధారించాలి: "నాకు, ఈ విలువ నిజం, నేను మొత్తం సిస్టమ్‌తో అంగీకరిస్తున్నాను."
ఏకాభిప్రాయ అల్గోరిథం ఎలా పని చేస్తుందో ఉదాహరణ
అల్గోరిథం యొక్క లక్షణాలు పూర్తిగా స్పష్టంగా ఉండకపోవచ్చు. అందువల్ల, సింక్రోనస్ మెసేజింగ్ మోడల్‌తో సిస్టమ్‌లో సరళమైన ఏకాభిప్రాయ అల్గోరిథం ఏ దశల్లో వెళుతుందో మేము ఉదాహరణతో వివరిస్తాము, దీనిలో అన్ని నోడ్‌లు ఆశించిన విధంగా పనిచేస్తాయి, సందేశాలు కోల్పోవు మరియు ఏమీ విచ్ఛిన్నం కాదు (ఇది నిజంగా జరుగుతుందా?).
- ఇదంతా వివాహ ప్రతిపాదన (ప్రపోజ్)తో మొదలవుతుంది. ఒక క్లయింట్ "నోడ్ 1" అనే నోడ్‌కి కనెక్ట్ అయ్యి, లావాదేవీని ప్రారంభించి, నోడ్ - Oకి కొత్త విలువను పాస్ చేసిందని అనుకుందాం. ఇప్పటి నుండి, మేము "నోడ్ 1" అని పిలుస్తాము. ఆఫర్. ప్రపోజర్‌గా, “నోడ్ 1” ఇప్పుడు పూర్తి సిస్టమ్కు తాజా డేటాను కలిగి ఉందని తెలియజేయాలి మరియు ఇది అన్ని ఇతర నోడ్‌లకు సందేశాలను పంపుతుంది: “చూడండి! "ఓ" అనే అర్థం నాకు వచ్చింది మరియు నేను దానిని వ్రాయాలనుకుంటున్నాను! దయచేసి మీరు మీ లాగ్‌లో "O"ని కూడా రికార్డ్ చేస్తారని నిర్ధారించండి."
- తదుపరి దశ ప్రతిపాదిత విలువ (ఓటింగ్) కోసం ఓటు వేయడం. అది దేనికోసం? ఇతర నోడ్‌లు ఇటీవలి సమాచారాన్ని స్వీకరించడం మరియు అదే లావాదేవీకి సంబంధించిన డేటాను కలిగి ఉండటం జరగవచ్చు.
నోడ్ “నోడ్ 1” దాని ప్రతిపాదనను పంపినప్పుడు, ఇతర నోడ్‌లు ఈ ఈవెంట్‌పై డేటా కోసం తమ లాగ్‌లను తనిఖీ చేస్తాయి. వైరుధ్యాలు లేకుంటే, నోడ్‌లు ఇలా ప్రకటిస్తాయి: “అవును, ఈ ఈవెంట్ కోసం నా దగ్గర ఇతర డేటా లేదు. "O" విలువ మేము అర్హులైన తాజా సమాచారం."ఏదైనా ఇతర సందర్భంలో, నోడ్‌లు “నోడ్ 1”కి ప్రతిస్పందించగలవు: “వినండి! ఈ లావాదేవీకి సంబంధించి నా దగ్గర ఇటీవలి డేటా ఉంది. 'ఓ' కాదు, కానీ ఏదో బెటర్."
ఓటింగ్ దశలో, నోడ్‌లు ఒక నిర్ణయానికి వస్తాయి: అవన్నీ ఒకే విలువను అంగీకరిస్తాయి, లేదా వారిలో ఒకరు వ్యతిరేకంగా ఓటు వేస్తారు, అతని వద్ద మరింత ఇటీవలి డేటా ఉందని సూచిస్తుంది.
- ఓటింగ్ రౌండ్ విజయవంతమై మరియు ప్రతి ఒక్కరూ అనుకూలంగా ఉంటే, అప్పుడు వ్యవస్థ కొత్త దశకు వెళుతుంది - విలువను అంగీకరించడం. “నోడ్ 1” ఇతర నోడ్‌లు మరియు నివేదికల నుండి అన్ని ప్రతిస్పందనలను సేకరిస్తుంది: “అందరూ “O” విలువను అంగీకరించారు! ఇప్పుడు నేను అధికారికంగా “ఓ” అనేది మా కొత్త అర్థం, అందరికీ ఒకటే! మీ చిన్న పుస్తకంలో వ్రాయండి, మర్చిపోవద్దు. మీ లాగ్‌లో రాసుకోండి!"
- మిగిలిన నోడ్‌లు "O" విలువను వ్రాసినట్లు నిర్ధారణ (అంగీకరించబడినవి) పంపుతాయి; ఈ సమయంలో కొత్తది ఏమీ రాలేదు (ఒక రకమైన రెండు-దశల కమిట్). ఈ ముఖ్యమైన సంఘటన తర్వాత, పంపిణీ చేయబడిన లావాదేవీ పూర్తయినట్లు మేము భావిస్తున్నాము.
అందువల్ల, ఒక సాధారణ సందర్భంలో ఏకాభిప్రాయ అల్గోరిథం నాలుగు దశలను కలిగి ఉంటుంది: ప్రతిపాదించడం, ఓటు వేయడం (ఓటింగ్), అంగీకరించడం (అంగీకరించడం), అంగీకారాన్ని నిర్ధారించడం (అంగీకరించబడింది).
ఏదో ఒక దశలో మేము ఒప్పందాన్ని చేరుకోలేకపోతే, ప్రతిపాదిత విలువను నిర్ధారించడానికి నిరాకరించిన నోడ్‌లు అందించిన సమాచారాన్ని పరిగణనలోకి తీసుకుని, అల్గోరిథం మళ్లీ ప్రారంభమవుతుంది.
అసమకాలిక వ్యవస్థలో ఏకాభిప్రాయ అల్గోరిథం
దీనికి ముందు, ప్రతిదీ సజావుగా ఉంది, ఎందుకంటే మేము సింక్రోనస్ మెసేజింగ్ మోడల్ గురించి మాట్లాడుతున్నాము. కానీ ఆధునిక ప్రపంచంలో మనం ప్రతిదీ అసమకాలికంగా చేయడం అలవాటు చేసుకున్నామని మనకు తెలుసు. అసమకాలిక మెసేజింగ్ మోడల్‌తో కూడిన సిస్టమ్‌లో ఇలాంటి అల్గోరిథం ఎలా పని చేస్తుంది, ఇక్కడ నోడ్ నుండి ప్రతిస్పందన కోసం వేచి ఉండే సమయం ఏకపక్షంగా ఉంటుందని మేము విశ్వసిస్తున్నాము (మార్గం ద్వారా, నోడ్ యొక్క వైఫల్యాన్ని కూడా ఉదాహరణగా పరిగణించవచ్చు ఒక నోడ్ ఏకపక్షంగా చాలా కాలం పాటు ప్రతిస్పందిస్తుంది ).
ఏకాభిప్రాయ అల్గారిథమ్ సూత్రప్రాయంగా ఎలా పనిచేస్తుందో ఇప్పుడు మనకు తెలుసు, ఇంత దూరం చేసిన పరిశోధనాత్మక పాఠకులకు ఒక ప్రశ్న: అసమకాలిక సందేశ నమూనాతో N నోడ్‌ల సిస్టమ్‌లో ఎన్ని నోడ్‌లు విఫలమవుతాయి, తద్వారా సిస్టమ్ ఇప్పటికీ ఏకాభిప్రాయాన్ని చేరుకోగలదు?
సరైన సమాధానం మరియు సమర్థన స్పాయిలర్ వెనుక ఉన్నాయి.సరైన సమాధానం: 0. అసమకాలిక సిస్టమ్‌లో ఒక నోడ్ కూడా విఫలమైతే, సిస్టమ్ ఏకాభిప్రాయాన్ని చేరుకోలేకపోతుంది. ఈ ప్రకటన FLP సిద్ధాంతంలో నిరూపించబడింది, ఇది కొన్ని సర్కిల్‌లలో బాగా ప్రసిద్ది చెందింది (1985, ఫిషర్, లించ్, పాటర్సన్, కథనం చివరిలో అసలైన దానికి లింక్): “కనీసం ఒక నోడ్ విఫలమైతే పంపిణీ చేయబడిన ఏకాభిప్రాయాన్ని సాధించడం అసంభవం ."
గైస్, అప్పుడు మాకు సమస్య ఉంది, మేము ప్రతిదానికీ అసమకాలికంగా అలవాటు పడ్డాము. మరియు ఇక్కడ ఉంది. జీవించడం ఎలా కొనసాగించాలి?
మేము కేవలం సిద్ధాంతం గురించి, గణితం గురించి మాట్లాడుకుంటున్నాము. "ఏకాభిప్రాయం సాధించలేము" అంటే గణిత భాష నుండి మన భాషలోకి - ఇంజనీరింగ్‌లోకి అనువదించడం అంటే ఏమిటి? దీని అర్థం "ఎల్లప్పుడూ సాధించలేము", అనగా. ఏకాభిప్రాయం సాధించలేని సందర్భం ఉంది. ఇది ఎలాంటి కేసు?
ఇది ఖచ్చితంగా పైన వివరించిన లైవ్‌నెస్ ప్రాపర్టీ యొక్క ఉల్లంఘన. మాకు సాధారణ ఒప్పందం లేదు మరియు సిస్టమ్ అన్ని నోడ్‌ల నుండి ప్రతిస్పందన లేని సందర్భంలో (పరిమిత సమయంలో పూర్తి చేయలేము) పురోగతిని కలిగి ఉండదు. ఎందుకంటే అసమకాలిక సిస్టమ్‌లో మనకు ఊహించదగిన ప్రతిస్పందన సమయం ఉండదు మరియు నోడ్ క్రాష్ అయిందా లేదా ప్రతిస్పందించడానికి చాలా సమయం తీసుకుంటుందా అని మనం తెలుసుకోలేము.
కానీ ఆచరణలో మనం పరిష్కారం కనుగొనవచ్చు. వైఫల్యాల విషయంలో మా అల్గోరిథం చాలా కాలం పాటు పని చేయగలదు (సంభావ్యత అది నిరవధికంగా పని చేస్తుంది). కానీ చాలా సందర్భాలలో, చాలా నోడ్‌లు సరిగ్గా పని చేస్తున్నప్పుడు, మేము సిస్టమ్‌లో పురోగతిని కలిగి ఉంటాము.
ఆచరణలో, మేము పాక్షికంగా సింక్రోనస్ కమ్యూనికేషన్ మోడల్‌లతో వ్యవహరిస్తాము. పాక్షిక సమకాలీకరణ ఈ క్రింది విధంగా అర్థం చేసుకోబడింది: సాధారణ సందర్భంలో, మనకు అసమకాలిక నమూనా ఉంది, కానీ నిర్దిష్ట సమయం యొక్క "గ్లోబల్ స్టెబిలైజేషన్ సమయం" యొక్క నిర్దిష్ట భావన అధికారికంగా పరిచయం చేయబడింది.
ఈ క్షణకాలం ఎంతకాలమైనా రాకపోవచ్చు, కానీ ఒకరోజు తప్పక వస్తుంది. వర్చువల్ అలారం గడియారం రింగ్ అవుతుంది మరియు ఆ క్షణం నుండి మనం సందేశాలు వచ్చే సమయ డెల్టాను అంచనా వేయవచ్చు. ఈ క్షణం నుండి, సిస్టమ్ అసమకాలిక నుండి సింక్రోనస్‌కు మారుతుంది. ఆచరణలో, మేము ఖచ్చితంగా అలాంటి వ్యవస్థలతో వ్యవహరిస్తాము.
Paxos అల్గోరిథం ఏకాభిప్రాయ సమస్యలను పరిష్కరిస్తుంది
కొన్ని నోడ్‌లు విఫలమయ్యే అవకాశం ఉన్నందున, పాక్షికంగా సమకాలీకరణ వ్యవస్థల కోసం ఏకాభిప్రాయ సమస్యను పరిష్కరించే అల్గారిథమ్‌ల కుటుంబం. పాక్సోస్ రచయిత . అతను 1989లో అల్గోరిథం యొక్క ఉనికి మరియు ఖచ్చితత్వానికి అధికారిక రుజువును ప్రతిపాదించాడు.
కానీ రుజువు చాలా చిన్నది కాదు. మొదటి ప్రచురణ 1998లో మాత్రమే విడుదల చేయబడింది (33 పేజీలు) అల్గోరిథంను వివరిస్తుంది. ఇది ముగిసినప్పుడు, అర్థం చేసుకోవడం చాలా కష్టం, మరియు 2001 లో వ్యాసం యొక్క వివరణ ప్రచురించబడింది, ఇది 14 పేజీలను తీసుకుంది. వాస్తవానికి ఏకాభిప్రాయం యొక్క సమస్య అంత సులభం కాదని మరియు అటువంటి అల్గారిథమ్‌ల వెనుక తెలివైన వ్యక్తుల భారీ మొత్తంలో పని ఉందని చూపించడానికి ప్రచురణల వాల్యూమ్ ఇవ్వబడింది.
లెస్లీ లాంపోర్ట్ స్వయంగా తన ఉపన్యాసంలో రెండవ వివరణాత్మక కథనంలో ఒక ప్రకటన, ఒక లైన్ (అతను ఏది పేర్కొనలేదు), దానిని వివిధ మార్గాల్లో అర్థం చేసుకోవచ్చని పేర్కొన్నాడు. మరియు దీని కారణంగా, పెద్ద సంఖ్యలో ఆధునిక పాక్సోస్ అమలులు పూర్తిగా సరిగ్గా పనిచేయవు.
Paxos యొక్క పని యొక్క వివరణాత్మక విశ్లేషణ ఒకటి కంటే ఎక్కువ కథనాలను తీసుకుంటుంది, కాబట్టి నేను అల్గోరిథం యొక్క ప్రధాన ఆలోచనను చాలా క్లుప్తంగా తెలియజేయడానికి ప్రయత్నిస్తాను. నా వ్యాసం చివరిలో ఉన్న లింక్‌లలో మీరు ఈ అంశంపై మరింత డైవింగ్ చేయడానికి పదార్థాలను కనుగొంటారు.
పాక్సోస్‌లో పాత్రలు
Paxos అల్గోరిథం పాత్రల భావనను కలిగి ఉంది. మూడు ప్రధానమైన వాటిని పరిశీలిద్దాం (అదనపు పాత్రలతో మార్పులు ఉన్నాయి):
- ప్రతిపాదకులు (నిబంధనలను కూడా ఉపయోగించవచ్చు: నాయకులు లేదా సమన్వయకర్తలు). వినియోగదారు నుండి కొంత కొత్త విలువ గురించి తెలుసుకుని, నాయకుడి పాత్రను పోషించే అబ్బాయిలు వీరు. వారి పని కొత్త విలువ కోసం ఒక రౌండ్ ప్రతిపాదనలను ప్రారంభించడం మరియు నోడ్స్ యొక్క తదుపరి చర్యలను సమన్వయం చేయడం. అంతేకాకుండా, పాక్సోస్ కొన్ని పరిస్థితులలో అనేక మంది నాయకుల ఉనికిని అనుమతిస్తుంది.
- అంగీకరించేవారు (ఓటర్లు). ఇవి నిర్దిష్ట విలువను అంగీకరించడానికి లేదా తిరస్కరించడానికి ఓటు వేసే నోడ్‌లు. వారి పాత్ర చాలా ముఖ్యమైనది, ఎందుకంటే నిర్ణయం వారిపై ఆధారపడి ఉంటుంది: ఏకాభిప్రాయ అల్గోరిథం యొక్క తదుపరి దశ తర్వాత సిస్టమ్ ఏ స్థితికి వెళ్తుంది (లేదా కాదు).
- లెర్నర్స్. సిస్టమ్ స్థితి మారినప్పుడు కొత్త ఆమోదించబడిన విలువను అంగీకరించి వ్రాసే నోడ్‌లు. వారు నిర్ణయాలు తీసుకోరు, వారు డేటాను స్వీకరిస్తారు మరియు తుది వినియోగదారుకు ఇవ్వగలరు.
ఒక నోడ్ వివిధ పరిస్థితులలో అనేక పాత్రలను మిళితం చేస్తుంది.
కోరం యొక్క భావన
మనకు ఒక వ్యవస్థ ఉందని మేము అనుకుంటాము N నోడ్స్ మరియు వాటిలో గరిష్టంగా F నోడ్స్ విఫలం కావచ్చు. F నోడ్‌లు విఫలమైతే, మనం కనీసం కలిగి ఉండాలి 2F+1 అంగీకార నోడ్స్.
ఇది అవసరం కాబట్టి మనం ఎల్లప్పుడూ మెజారిటీని కలిగి ఉంటాము, చెత్త పరిస్థితిలో కూడా సరిగ్గా పని చేసే "మంచి" నోడ్‌లు. అంటే F+1 అంగీకరించిన "మంచి" నోడ్‌లు మరియు తుది విలువ ఆమోదించబడుతుంది. లేకపోతే, మన వివిధ స్థానిక సమూహాలు వేర్వేరు అర్థాలను పొంది తమలో తాము ఏకీభవించలేని పరిస్థితి ఏర్పడవచ్చు. అందువల్ల, ఓట్లను గెలవడానికి మాకు పూర్తి మెజారిటీ అవసరం.
పాక్సోస్ ఏకాభిప్రాయ అల్గోరిథం ఎలా పని చేస్తుందనే సాధారణ ఆలోచన
పాక్సోస్ అల్గోరిథం రెండు పెద్ద దశలను కలిగి ఉంటుంది, అవి ఒక్కొక్కటి రెండు దశలుగా విభజించబడ్డాయి:
- దశ 1a: సిద్ధం. తయారీ దశలో, నాయకుడు (ప్రతిపాదకుడు) అన్ని నోడ్‌లకు తెలియజేస్తాడు: “మేము కొత్త ఓటింగ్ దశను ప్రారంభిస్తున్నాము. మాకు కొత్త రౌండ్ ఉంది. ఈ రౌండ్ సంఖ్య n. ఇప్పుడు మేము ఓటింగ్ ప్రారంభిస్తాము." ప్రస్తుతానికి, ఇది కేవలం కొత్త చక్రం యొక్క ప్రారంభాన్ని నివేదిస్తుంది, కానీ కొత్త విలువను నివేదించదు. ఈ దశ యొక్క పని కొత్త రౌండ్‌ను ప్రారంభించడం మరియు దాని ప్రత్యేక సంఖ్యను అందరికీ తెలియజేయడం. రౌండ్ నంబర్ ముఖ్యం, ఇది మునుపటి నాయకులందరి కంటే మునుపటి అన్ని ఓటింగ్ నంబర్‌ల కంటే ఎక్కువగా ఉండాలి. ఎందుకంటే రౌండ్ నంబర్‌కు ధన్యవాదాలు, సిస్టమ్‌లోని ఇతర నోడ్‌లు లీడర్ డేటా ఎంత ఇటీవలిదో అర్థం చేసుకుంటాయి. ఇతర నోడ్‌లు ఇప్పటికే చాలా తర్వాత రౌండ్‌ల నుండి ఓటింగ్ ఫలితాలను కలిగి ఉండే అవకాశం ఉంది మరియు నాయకుడికి తాను సమయం వెనుక ఉన్నానని చెప్పే అవకాశం ఉంది.
- దశ 1b: ప్రామిస్. అంగీకార నోడ్‌లు కొత్త ఓటింగ్ దశ సంఖ్యను స్వీకరించినప్పుడు, రెండు ఫలితాలు సాధ్యమే:
- కొత్త ఓటు యొక్క సంఖ్య n అనేది అంగీకరించే వ్యక్తి పాల్గొన్న మునుపటి ఓటు సంఖ్య కంటే ఎక్కువ. అప్పుడు అంగీకరించేవారు n కంటే తక్కువ సంఖ్యతో ఎక్కువ ఓట్లలో పాల్గొనరని నాయకుడికి వాగ్దానాన్ని పంపుతారు. అంగీకరించే వ్యక్తి ఇప్పటికే దేనికైనా ఓటు వేసి ఉంటే (అంటే, అది ఇప్పటికే రెండవ దశలో కొంత విలువను అంగీకరించింది), అప్పుడు అది ఆమోదించబడిన విలువను మరియు దాని వాగ్దానానికి పాల్గొందిన ఓటు సంఖ్యను జతచేస్తుంది.
- అలా కాకుండా, అధిక సంఖ్యలో ఉన్న ఓటు గురించి అంగీకరించేవారికి ఇప్పటికే తెలిసి ఉంటే, అది ప్రిపరేషన్ దశను విస్మరించవచ్చు మరియు నాయకుడికి ప్రతిస్పందించకపోవచ్చు.
- దశ 2a: అంగీకరించండి. నాయకుడు కోరం (సిస్టమ్‌లోని మెజారిటీ నోడ్‌లు) నుండి ప్రతిస్పందన కోసం వేచి ఉండాలి మరియు అవసరమైన సంఖ్యలో ప్రతిస్పందనలను స్వీకరించినట్లయితే, ఈవెంట్‌ల అభివృద్ధికి అతనికి రెండు ఎంపికలు ఉన్నాయి:
- ఆమోదించిన వారిలో కొందరు వారు ఇప్పటికే ఓటు వేసిన విలువలను పంపారు. ఈ సందర్భంలో, నాయకుడు గరిష్ట సంఖ్యతో ఓటు నుండి విలువను ఎంచుకుంటాడు. ఈ విలువను x అని పిలుద్దాం మరియు ఇది అన్ని నోడ్‌లకు ఇలా సందేశాన్ని పంపుతుంది: “అంగీకరించు (n, x)”, ఇక్కడ మొదటి విలువ దాని స్వంత ప్రపోజ్ స్టెప్‌లోని ఓటింగ్ నంబర్ మరియు రెండవ విలువ ప్రతి ఒక్కరూ సేకరించినది, అనగా మనం నిజంగా ఓటు వేసే విలువ.
- అంగీకరించేవారిలో ఎవరూ ఎటువంటి విలువలను పంపకపోయినా, వారు ఈ రౌండ్‌లో ఓటు వేస్తామని వాగ్దానం చేస్తే, నాయకుడు వారి విలువకు ఓటు వేయమని వారిని ఆహ్వానించవచ్చు, అతను మొదటి స్థానంలో నాయకుడిగా మారిన విలువ. దానిని y అని పిలుద్దాం. ఇది అన్ని నోడ్‌లకు సందేశాన్ని పంపుతుంది: "అంగీకరించు (n, y)", మునుపటి ఫలితం వలె.
- దశ 2b: ఆమోదించబడింది. ఇంకా, అంగీకరించే నోడ్‌లు, లీడర్ నుండి “అంగీకరించు(...)” సందేశాన్ని స్వీకరించిన తర్వాత, దానితో అంగీకరిస్తాయి (కొత్త విలువతో వారు అంగీకరిస్తున్నట్లు అన్ని నోడ్‌లకు ధృవీకరణ పంపండి) వారు కొన్ని (ఇతర) వాగ్దానం చేయకపోతే మాత్రమే ) రౌండ్ నంబర్‌తో ఓటింగ్‌లో పాల్గొనడానికి నాయకుడు n' > n, లేకుంటే వారు నిర్ధారణ అభ్యర్థనను విస్మరిస్తారు.
మెజారిటీ నోడ్‌లు నాయకుడికి ప్రతిస్పందించి, అవన్నీ కొత్త విలువను నిర్ధారించినట్లయితే, కొత్త విలువ ఆమోదించబడినదిగా పరిగణించబడుతుంది. హుర్రే! మెజారిటీని చేరుకోకపోతే లేదా కొత్త విలువను అంగీకరించడానికి నిరాకరించిన నోడ్‌లు ఉంటే, అప్పుడు ప్రతిదీ మళ్లీ ప్రారంభమవుతుంది.
పాక్సోస్ అల్గోరిథం ఈ విధంగా పనిచేస్తుంది. ఈ దశల్లో ప్రతిదానికి అనేక సూక్ష్మబేధాలు ఉన్నాయి, మేము ఆచరణాత్మకంగా వివిధ రకాల వైఫల్యాలు, బహుళ నాయకుల సమస్యలు మరియు మరెన్నో పరిగణించలేదు, అయితే ఈ వ్యాసం యొక్క ఉద్దేశ్యం పాఠకులను అధిక స్థాయిలో పంపిణీ చేయబడిన కంప్యూటింగ్ ప్రపంచానికి పరిచయం చేయడం మాత్రమే.
పాక్సోస్ ఈ రకమైనది మాత్రమే కాదు, ఇతర అల్గోరిథంలు ఉన్నాయి, ఉదాహరణకు, , కానీ ఇది మరొక కథనానికి సంబంధించిన అంశం.
తదుపరి అధ్యయనం కోసం మెటీరియల్‌లకు లింక్‌లు
ప్రారంభ స్థాయి:
- , ప్రీతి కసిరెడ్డి, మీడియంపై బ్లాగ్ కథనం
- , ఆది కంచెర్ల, మీడియంపై బ్లాగ్ కథనం
- , ఇత్తై అబ్రహం, బ్లాగ్
- , ఇత్తై అబ్రహం, బ్లాగ్ వ్యాసం
లెస్లీ లాంపోర్ట్ స్థాయి:
- , ఫిషర్, లించ్ మరియు ప్యాటర్సన్, పరిశోధనా పత్రం, 1985
- , లెస్లీ లాంపోర్ట్, పరిశోధనా పత్రం, 1998
- , లెస్లీ లాంపోర్ట్, పరిశోధనా పత్రం, 2001
మూలం: www.habr.com