எனவே, கற்பனை செய்யலாம். அறையில் 5 பூனைகள் பூட்டப்பட்டுள்ளன, உரிமையாளரை எழுப்ப, அவர்கள் அனைவரும் தங்களுக்குள் இதை ஒப்புக் கொள்ள வேண்டும், ஏனென்றால் அவர்களில் ஐந்து பேர் மட்டுமே கதவைத் திறக்க முடியும். பூனைகளில் ஒன்று ஷ்ரோடிங்கரின் பூனையாக இருந்தால், மற்ற பூனைகளுக்கு அவரது முடிவைப் பற்றி தெரியவில்லை என்றால், கேள்வி எழுகிறது: "அவர்கள் அதை எப்படிச் செய்ய முடியும்?"
இந்த கட்டுரையில், விநியோகிக்கப்பட்ட அமைப்புகளின் உலகின் கோட்பாட்டு கூறு மற்றும் அவற்றின் செயல்பாட்டின் கொள்கைகள் பற்றி நான் உங்களுக்கு எளிமையான சொற்களில் கூறுவேன். Paxos அடிப்படையிலான முக்கிய யோசனையையும் மேலோட்டமாக ஆராய்வேன்.
டெவலப்பர்கள் கிளவுட் உள்கட்டமைப்புகள், பல்வேறு தரவுத்தளங்கள் மற்றும் அதிக எண்ணிக்கையிலான முனைகளின் கிளஸ்டர்களில் பணிபுரியும் போது, தரவு முழுமையானதாகவும், பாதுகாப்பாகவும் மற்றும் எப்போதும் கிடைக்கும் என்று அவர்கள் நம்புகிறார்கள். ஆனால் உத்தரவாதங்கள் எங்கே?
அடிப்படையில், எங்களிடம் உள்ள உத்தரவாதங்கள் சப்ளையர் உத்தரவாதங்கள். அவை ஆவணத்தில் பின்வருமாறு விவரிக்கப்பட்டுள்ளன: "இந்த சேவை மிகவும் நம்பகமானது, இது கொடுக்கப்பட்ட SLA ஐக் கொண்டுள்ளது, கவலைப்பட வேண்டாம், நீங்கள் எதிர்பார்ப்பது போல் அனைத்தும் விநியோகிக்கப்படும்."
நாங்கள் சிறந்ததை நம்புகிறோம், ஏனென்றால் பெரிய நிறுவனங்களின் புத்திசாலிகள் எல்லாம் சரியாகிவிடும் என்று எங்களுக்கு உறுதியளித்தனர். நாங்கள் கேள்வி கேட்கவில்லை: ஏன், உண்மையில், இது வேலை செய்ய முடியுமா? அத்தகைய அமைப்புகளின் சரியான செயல்பாட்டிற்கு ஏதேனும் முறையான நியாயம் உள்ளதா?
சமீபத்தில் சென்றிருந்தேன் மற்றும் இந்த தலைப்பால் மிகவும் ஈர்க்கப்பட்டது. பள்ளியில் விரிவுரைகள் கணினி அமைப்புகளுடன் தொடர்புடையதை விட கால்குலஸ் வகுப்புகளைப் போலவே இருந்தன. ஆனால், நாம் அன்றாடம் பயன்படுத்தும் மிக முக்கியமான அல்காரிதம்கள், நமக்குத் தெரியாமல், ஒரு காலத்தில் இப்படித்தான் நிரூபிக்கப்பட்டன.
பெரும்பாலான நவீன விநியோகிக்கப்பட்ட அமைப்புகள் Paxos ஒருமித்த வழிமுறை மற்றும் அதன் பல்வேறு மாற்றங்களைப் பயன்படுத்துகின்றன. சிறந்த விஷயம் என்னவென்றால், செல்லுபடியாகும் தன்மை மற்றும் கொள்கையளவில், இந்த வழிமுறையின் இருப்புக்கான சாத்தியக்கூறுகள் ஒரு பேனா மற்றும் காகிதத்துடன் வெறுமனே நிரூபிக்கப்படலாம். நடைமுறையில், மேகங்களில் அதிக எண்ணிக்கையிலான முனைகளில் இயங்கும் பெரிய அமைப்புகளில் அல்காரிதம் பயன்படுத்தப்படுகிறது.
அடுத்து என்ன விவாதிக்கப்படும் என்பதற்கான ஒளி விளக்கம்: இரண்டு ஜெனரல்களின் பணிஒரு வார்ம்-அப்பைப் பார்ப்போம் .
எங்களிடம் இரண்டு படைகள் உள்ளன - சிவப்பு மற்றும் வெள்ளை. முற்றுகையிடப்பட்ட நகரத்தில் வெள்ளை துருப்புக்கள் உள்ளன. ஜெனரல்கள் A1 மற்றும் A2 தலைமையிலான சிவப்பு துருப்புக்கள் நகரின் இரண்டு பக்கங்களிலும் அமைந்துள்ளன. வெள்ளை நகரத்தைத் தாக்கி வெற்றி பெறுவதே செங்குட்டுவன்களின் பணி. இருப்பினும், ஒவ்வொரு சிவப்பு ஜெனரலின் இராணுவமும் தனித்தனியாக வெள்ளை இராணுவத்தை விட சிறியது.
சிவப்பு நிறத்தினருக்கான வெற்றி நிலைமைகள்: வெள்ளையர்களை விட எண்ணியல் நன்மையைப் பெற இரண்டு தளபதிகளும் ஒரே நேரத்தில் தாக்க வேண்டும். இதைச் செய்ய, ஜெனரல்கள் A1 மற்றும் A2 ஒருவருக்கொருவர் உடன்படிக்கைக்கு வர வேண்டும். எல்லோரும் தனித்தனியாக தாக்கினால், செங்குட்டுவர்கள் இழக்க நேரிடும்.
ஒரு உடன்பாட்டை எட்ட, ஜெனரல்கள் A1 மற்றும் A2 வெள்ளை நகரத்தின் எல்லை வழியாக ஒருவருக்கொருவர் தூதர்களை அனுப்பலாம். தூதர் வெற்றிகரமாக ஒரு நேச நாட்டு ஜெனரலை அடையலாம் அல்லது எதிரியால் தடுக்கப்படலாம். கேள்வி: சிவப்பு ஹேர்டு ஜெனரல்களுக்கு இடையே இதுபோன்ற தொடர் தொடர்பு உள்ளதா (A1 இலிருந்து A2 க்கும், A2 இலிருந்து A1 க்கும் தூதர்களை அனுப்பும் வரிசை), இதில் அவர்கள் X மணிநேரத்தில் தாக்குதலை ஒப்புக்கொள்வது உறுதி. இங்கே, உத்தரவாதங்கள் என்பது, இரண்டு ஜெனரல்களும் ஒரு கூட்டாளி (மற்றொரு ஜெனரல்) கண்டிப்பாக நியமிக்கப்பட்ட நேரத்தில் X இல் தாக்குவார்கள் என்பதை தெளிவற்ற உறுதிப்படுத்தலைக் கொண்டிருப்பார்கள்.
“இன்று நள்ளிரவில் தாக்குவோம்!” என்ற செய்தியுடன் A1 ஒரு தூதரை A2 க்கு அனுப்புகிறது என்று வைத்துக்கொள்வோம். ஜெனரல் A1 இன் உறுதிப்படுத்தல் இல்லாமல் ஜெனரல் A2 தாக்க முடியாது. A1 இலிருந்து தூதர் வந்திருந்தால், ஜெனரல் A2 உறுதிப்படுத்தல் செய்தியை அனுப்புகிறது: "ஆம், இன்று வெள்ளையர்களைக் கொல்வோம்." ஆனால் இப்போது ஜெனரல் A2 க்கு அவரது தூதர் வந்தாரா இல்லையா என்பது தெரியவில்லை, தாக்குதல் ஒரே நேரத்தில் நடக்குமா என்பதற்கு அவருக்கு எந்த உத்தரவாதமும் இல்லை. இப்போது ஜெனரல் A2 மீண்டும் உறுதிப்படுத்தல் தேவை.
அவர்களின் தகவல்தொடர்புகளை நாம் மேலும் விவரித்தால், எத்தனை செய்தி பரிமாற்ற சுழற்சிகள் இருந்தாலும், இரண்டு ஜெனரல்களும் தங்கள் செய்திகளைப் பெற்றுள்ளனர் என்பதற்கு உத்தரவாதம் அளிக்க வழி இல்லை என்பது தெளிவாகிறது (எந்த தூதரையும் இடைமறிக்க முடியும் என்று வைத்துக்கொள்வோம்).
இரண்டு ஜெனரல்கள் சிக்கல் என்பது மிகவும் எளிமையான விநியோகிக்கப்பட்ட அமைப்பின் சிறந்த விளக்கமாகும், அங்கு நம்பகத்தன்மையற்ற தகவல்தொடர்புடன் இரண்டு முனைகள் உள்ளன. அதாவது, அவை ஒத்திசைக்கப்பட்டுள்ளன என்பதற்கு எங்களிடம் 100% உத்தரவாதம் இல்லை. இதே போன்ற சிக்கல்கள் கட்டுரையில் பெரிய அளவில் மட்டுமே விவாதிக்கப்படும்.
விநியோகிக்கப்பட்ட அமைப்புகளின் கருத்தை நாங்கள் அறிமுகப்படுத்துகிறோம்
விநியோகிக்கப்பட்ட அமைப்பு என்பது செய்திகளைப் பரிமாறிக்கொள்ளக்கூடிய கணினிகளின் குழுவாகும் (இனிமேல் நாம் அவற்றை முனைகள் என்று அழைப்போம்). ஒவ்வொரு தனிப்பட்ட முனையும் ஒருவித தன்னாட்சி நிறுவனமாகும். ஒரு முனை தானாகவே பணிகளைச் செயல்படுத்த முடியும், ஆனால் மற்ற முனைகளுடன் தொடர்பு கொள்ள, அது செய்திகளை அனுப்பவும் பெறவும் வேண்டும்.
செய்திகள் எவ்வாறு சரியாக செயல்படுத்தப்படுகின்றன, என்ன நெறிமுறைகள் பயன்படுத்தப்படுகின்றன - இந்த சூழலில் இது எங்களுக்கு ஆர்வமாக இல்லை. ஒரு விநியோகிக்கப்பட்ட அமைப்பின் முனைகள் செய்திகளை அனுப்புவதன் மூலம் ஒருவருக்கொருவர் தரவைப் பரிமாறிக்கொள்ள முடியும் என்பது முக்கியம்.
வரையறை மிகவும் சிக்கலானதாகத் தெரியவில்லை, ஆனால் விநியோகிக்கப்பட்ட அமைப்பில் நமக்கு முக்கியமான பல பண்புக்கூறுகள் உள்ளன என்பதை நாம் கணக்கில் எடுத்துக்கொள்ள வேண்டும்.
விநியோகிக்கப்பட்ட அமைப்புகளின் பண்புக்கூறுகள்
- ஒருங்கிணைவு - அமைப்பில் ஒரே நேரத்தில் அல்லது ஒரே நேரத்தில் நிகழும் நிகழ்வுகளின் சாத்தியம். மேலும், இந்த நிகழ்வுகளின் தெளிவான வரிசை இல்லாத வரையில், இரண்டு வெவ்வேறு முனைகளில் நிகழும் நிகழ்வுகள் ஒரே நேரத்தில் சாத்தியமானதாக இருக்கும் என்று கருதுவோம். ஆனால், ஒரு விதியாக, எங்களிடம் அது இல்லை.
- உலகளாவிய கடிகாரம் இல்லை. உலகளாவிய கடிகாரம் இல்லாததால் நிகழ்வுகளின் தெளிவான வரிசை எங்களிடம் இல்லை. மனிதர்களின் சாதாரண உலகில், நம்மிடம் கடிகாரங்களும் நேரமும் முற்றிலும் உள்ளன என்ற உண்மைக்கு நாம் பழக்கமாகிவிட்டோம். விநியோகிக்கப்பட்ட அமைப்புகளுக்கு வரும்போது எல்லாம் மாறுகிறது. மிகத் துல்லியமான அணுக் கடிகாரங்கள் கூட சறுக்கலைக் கொண்டிருக்கின்றன, மேலும் இரண்டு நிகழ்வுகளில் எது முதலில் நடந்தது என்று சொல்ல முடியாத சூழ்நிலைகள் இருக்கலாம். எனவே, நாம் நேரத்தையும் நம்ப முடியாது.
- கணினி முனைகளின் சுயாதீன தோல்வி. மற்றொரு சிக்கல் உள்ளது: நமது கணுக்கள் என்றென்றும் நிலைக்காது என்பதால் ஏதோ தவறு ஏற்படலாம். ஹார்ட் டிரைவ் தோல்வியடையலாம், மேகக்கணியில் உள்ள மெய்நிகர் இயந்திரம் மறுதொடக்கம் செய்யப்படலாம், பிணையம் சிமிட்டலாம் மற்றும் செய்திகள் இழக்கப்படும். மேலும், முனைகள் வேலை செய்யும் சூழ்நிலைகள் இருக்கலாம், ஆனால் அதே நேரத்தில் கணினிக்கு எதிராக வேலை செய்கிறது. கடைசி வகுப்பு சிக்கல்கள் ஒரு தனி பெயரைப் பெற்றன: சிக்கல் . இந்த சிக்கலுடன் விநியோகிக்கப்பட்ட அமைப்பின் மிகவும் பிரபலமான உதாரணம் Blockchain ஆகும். ஆனால் இன்று நாம் இந்த சிறப்பு வகை பிரச்சனைகளை கருத்தில் கொள்ள மாட்டோம். ஒன்று அல்லது அதற்கு மேற்பட்ட முனைகள் தோல்வியடையும் சூழ்நிலைகளில் நாங்கள் ஆர்வமாக இருப்போம்.
- முனைகளுக்கு இடையே தொடர்பு மாதிரிகள் (செய்தி அனுப்பும் மாதிரிகள்).. செய்திகளைப் பரிமாறிக் கொள்வதன் மூலம் முனைகள் தொடர்பு கொள்கின்றன என்பதை நாங்கள் ஏற்கனவே நிறுவியுள்ளோம். இரண்டு நன்கு அறியப்பட்ட செய்தியிடல் மாதிரிகள் உள்ளன: ஒத்திசைவான மற்றும் ஒத்திசைவற்ற.
விநியோகிக்கப்பட்ட அமைப்புகளில் முனைகளுக்கு இடையிலான தொடர்பு மாதிரிகள்
ஒத்திசைவான மாதிரி - ஒரு செய்தி ஒரு முனையிலிருந்து மற்றொரு முனைக்கு சென்றடையும் என்று உத்தரவாதம் அளிக்கப்படும் ஒரு வரையறுக்கப்பட்ட டெல்டா நேரம் இருப்பதை நாங்கள் உறுதியாக அறிவோம். இந்த நேரம் கடந்து, செய்தி வரவில்லை என்றால், முனை தோல்வியடைந்தது என்று நாம் பாதுகாப்பாக சொல்லலாம். இந்த மாதிரியில் நாம் கணிக்கக்கூடிய காத்திருப்பு நேரங்கள் உள்ளன.
ஒத்திசைவற்ற மாதிரி - ஒத்திசைவற்ற மாதிரிகளில், காத்திருப்பு நேரம் வரையறுக்கப்பட்டுள்ளது என்று நாங்கள் கருதுகிறோம், ஆனால் அத்தகைய நேரத்தின் டெல்டா எதுவும் இல்லை, அதன் பிறகு முனை தோல்வியடைந்தது என்று உத்தரவாதம் அளிக்க முடியும். அந்த. ஒரு முனையிலிருந்து ஒரு செய்திக்காக காத்திருக்கும் நேரம் தன்னிச்சையாக நீண்டதாக இருக்கும். இது ஒரு முக்கியமான வரையறை, அதைப் பற்றி மேலும் பேசுவோம்.
விநியோகிக்கப்பட்ட அமைப்புகளில் ஒருமித்த கருத்து
ஒருமித்த கருத்தை முறையாக வரையறுக்கும் முன், நமக்குத் தேவைப்படும் சூழ்நிலையின் உதாரணத்தைக் கருத்தில் கொள்வோம், அதாவது - மாநில இயந்திர பிரதிபலிப்பு.
எங்களிடம் சில விநியோகிக்கப்பட்ட பதிவு உள்ளது. விநியோகிக்கப்பட்ட அமைப்பின் அனைத்து முனைகளிலும் ஒரே மாதிரியான தரவை இது சீராக இருக்க வேண்டும் என்று நாங்கள் விரும்புகிறோம். ஒரு முனையில் ஒரு புதிய மதிப்பை அது பதிவில் எழுதப் போகிறது என்பதை அறியும்போது, அதன் பணி மற்ற எல்லா முனைகளுக்கும் இந்த மதிப்பை வழங்குவதாகும், இதனால் பதிவு அனைத்து முனைகளிலும் புதுப்பிக்கப்பட்டு கணினி ஒரு புதிய நிலையான நிலைக்கு நகரும். இந்த விஷயத்தில், முனைகள் தங்களுக்குள் ஒத்துப்போவது முக்கியம்: முன்மொழியப்பட்ட புதிய மதிப்பு சரியானது என்பதை அனைத்து முனைகளும் ஒப்புக்கொள்கின்றன, எல்லா முனைகளும் இந்த மதிப்பை ஏற்றுக்கொள்கின்றன, மேலும் இந்த விஷயத்தில் மட்டுமே எல்லோரும் புதிய மதிப்பை பதிவில் எழுத முடியும்.
வேறு வார்த்தைகளில் கூறுவதானால்: எந்த முனைகளும் இது மிகவும் பொருத்தமான தகவலைக் கொண்டிருப்பதை எதிர்க்கவில்லை, மேலும் முன்மொழியப்பட்ட மதிப்பு தவறானது. முனைகளுக்கு இடையிலான ஒப்பந்தம் மற்றும் ஒரு சரியான ஏற்றுக்கொள்ளப்பட்ட மதிப்பின் மீதான ஒப்பந்தம் விநியோகிக்கப்பட்ட அமைப்பில் ஒருமித்த கருத்து. அடுத்து, விநியோகிக்கப்பட்ட அமைப்பு ஒருமித்த கருத்தை அடைய உத்தரவாதம் அளிக்க அனுமதிக்கும் வழிமுறைகளைப் பற்றி பேசுவோம்.
இன்னும் முறைப்படி, நாம் ஒருமித்த வழிமுறையை (அல்லது ஒருமித்த வழிமுறை) ஒரு குறிப்பிட்ட செயல்பாடாக வரையறுக்கலாம், இது ஒரு விநியோகிக்கப்பட்ட அமைப்பை நிலை A இலிருந்து மாநில B க்கு மாற்றுகிறது. மேலும், இந்த நிலை அனைத்து முனைகளாலும் ஏற்றுக்கொள்ளப்படுகிறது, மேலும் அனைத்து முனைகளும் அதை உறுதிப்படுத்த முடியும். அது மாறிவிடும், இந்த பணி முதல் பார்வையில் தோன்றும் அளவுக்கு அற்பமானது அல்ல.
ஒருமித்த அல்காரிதத்தின் பண்புகள்
ஒருமித்த அல்காரிதம் அமைப்பு தொடர்ந்து இருப்பதற்கும், மாநிலத்திலிருந்து மாநிலத்திற்குச் செல்வதில் சில முன்னேற்றங்களைப் பெறுவதற்கும் மூன்று பண்புகளைக் கொண்டிருக்க வேண்டும்:
- ஒப்பந்தம் - சரியாக செயல்படும் அனைத்து முனைகளும் ஒரே மதிப்பை எடுக்க வேண்டும் (கட்டுரைகளில் இந்த சொத்து பாதுகாப்பு சொத்து என்றும் குறிப்பிடப்படுகிறது). தற்போது செயல்படும் அனைத்து முனைகளும் (தோல்வி அடையவில்லை அல்லது மற்றவற்றுடன் தொடர்பை இழக்கவில்லை) ஒரு உடன்பாட்டிற்கு வந்து சில இறுதி பொதுவான மதிப்பை ஏற்க வேண்டும்.
நாம் பரிசீலிக்கும் விநியோகிக்கப்பட்ட அமைப்பில் உள்ள முனைகள் ஒப்புக்கொள்ள விரும்புகின்றன என்பதை இங்கே புரிந்து கொள்ள வேண்டியது அவசியம். அதாவது, நாம் இப்போது ஏதாவது தோல்வியடையக்கூடிய அமைப்புகளைப் பற்றி பேசுகிறோம் (எடுத்துக்காட்டாக, சில முனைகள் தோல்வியடைகின்றன), ஆனால் இந்த அமைப்பில் மற்றவர்களுக்கு எதிராக வேண்டுமென்றே செயல்படும் முனைகள் நிச்சயமாக இல்லை (பைசண்டைன் ஜெனரல்களின் பணி). இந்த பண்பு காரணமாக, அமைப்பு சீராக உள்ளது.
- நேர்மை - சரியாக வேலை செய்யும் அனைத்து முனைகளும் ஒரே மதிப்பை வழங்கினால் v, அதாவது சரியாக செயல்படும் ஒவ்வொரு முனையும் இந்த மதிப்பை ஏற்க வேண்டும் v.
- முடித்தல் - சரியாக இயங்கும் அனைத்து முனைகளும் இறுதியில் ஒரு குறிப்பிட்ட மதிப்பை (உயிர்நிலை சொத்து) எடுக்கும், இது வழிமுறையை கணினியில் முன்னேற்றம் செய்ய அனுமதிக்கிறது. ஒவ்வொரு தனிநபரும் சரியாக இயங்கும் முனை விரைவில் அல்லது பின்னர் இறுதி மதிப்பை ஏற்றுக்கொண்டு அதை உறுதிப்படுத்த வேண்டும்: "என்னைப் பொறுத்தவரை, இந்த மதிப்பு உண்மைதான், முழு அமைப்புடன் நான் உடன்படுகிறேன்."
ஒருமித்த அல்காரிதம் எவ்வாறு செயல்படுகிறது என்பதற்கான எடுத்துக்காட்டு
அல்காரிதத்தின் பண்புகள் முற்றிலும் தெளிவாக இல்லாமல் இருக்கலாம். எனவே, ஒரு சின்க்ரோனஸ் மெசேஜிங் மாடலைக் கொண்ட அமைப்பில் எளிமையான ஒருமித்த அல்காரிதம் எந்த நிலைகளில் செல்கிறது என்பதை எடுத்துக்காட்டுடன் விளக்குவோம், இதில் அனைத்து முனைகளும் எதிர்பார்த்தபடி செயல்படும், செய்திகள் இழக்கப்படாது மற்றும் எதுவும் உடைக்கப்படாது (இது உண்மையில் நடக்குமா?).
- இது அனைத்தும் திருமண முன்மொழிவுடன் தொடங்குகிறது (முன்மொழிதல்). ஒரு கிளையன்ட் "நோட் 1" எனப்படும் முனையுடன் இணைக்கப்பட்டு, ஒரு பரிவர்த்தனையைத் தொடங்கினார் என்று வைத்துக்கொள்வோம், ஒரு புதிய மதிப்பை நோட் - ஓ. முன்மொழிய. ஒரு முன்மொழிபவராக, “நோட் 1” ஆனது புதிய தரவுகளைக் கொண்டிருப்பதை முழு கணினிக்கும் தெரிவிக்க வேண்டும், மேலும் அது மற்ற எல்லா முனைகளுக்கும் செய்திகளை அனுப்புகிறது: “பாருங்கள்! "ஓ" என்ற அர்த்தம் எனக்கு வந்தது, நான் அதை எழுத விரும்புகிறேன்! உங்கள் பதிவில் "O" ஐயும் பதிவுசெய்வீர்கள் என்பதை உறுதிப்படுத்தவும்."
- அடுத்த கட்டம் முன்மொழியப்பட்ட மதிப்பிற்கு வாக்களிப்பது (வாக்களிப்பது). இது எதற்காக? பிற கணுக்கள் மிக சமீபத்திய தகவல்களைப் பெற்றிருக்கலாம், மேலும் அவை அதே பரிவர்த்தனையின் தரவைக் கொண்டுள்ளன.
முனை "நோட் 1" அதன் முன்மொழிவை அனுப்பும் போது, மற்ற முனைகள் இந்த நிகழ்வின் தரவுக்காக தங்கள் பதிவுகளை சரிபார்க்கும். முரண்பாடுகள் இல்லை என்றால், முனைகள் அறிவிக்கின்றன: “ஆம், இந்த நிகழ்விற்கான வேறு தரவு என்னிடம் இல்லை. "O" மதிப்பு என்பது எங்களுக்குத் தகுதியான சமீபத்திய தகவல்."வேறு எந்த சந்தர்ப்பத்திலும், முனைகள் "நோட் 1" க்கு பதிலளிக்கலாம்: "கேளுங்கள்! இந்த பரிவர்த்தனை குறித்த சமீபத்திய தரவு என்னிடம் உள்ளது. 'ஓ' அல்ல, ஆனால் ஏதோ சிறந்தது."
வாக்களிக்கும் கட்டத்தில், முனைகள் ஒரு முடிவுக்கு வருகின்றன: ஒன்று அவை அனைத்தும் ஒரே மதிப்பை ஏற்றுக்கொள்கின்றன, அல்லது அவர்களில் ஒருவர் எதிராக வாக்களிக்கிறார், இது அவரிடம் சமீபத்திய தரவு இருப்பதைக் குறிக்கிறது.
- வாக்களிப்பு சுற்று வெற்றிகரமாக இருந்தது மற்றும் அனைவருக்கும் ஆதரவாக இருந்தால், அமைப்பு ஒரு புதிய கட்டத்திற்கு நகர்கிறது - மதிப்பை ஏற்றுக்கொள்வது. "நோட் 1" மற்ற முனைகளில் இருந்து அனைத்து பதில்களையும் சேகரிக்கிறது மற்றும் அறிக்கைகள்: "எல்லோரும் "O" மதிப்பை ஒப்புக்கொண்டனர்! இப்போது நான் அதிகாரப்பூர்வமாக “ஓ” என்பது எங்கள் புதிய அர்த்தம், அனைவருக்கும் ஒரே மாதிரியாக இருக்கும் என்று அறிவிக்கிறேன்! உங்கள் சிறிய புத்தகத்தில் எழுதுங்கள், மறந்துவிடாதீர்கள். அதை உங்கள் பதிவில் எழுதி வையுங்கள்!”
- மீதமுள்ள முனைகள் "O" மதிப்பை எழுதிவிட்டதாக உறுதிப்படுத்தல் (ஏற்றுக்கொள்ளப்பட்டது) அனுப்புகிறது; இந்த நேரத்தில் புதிதாக எதுவும் வரவில்லை (ஒரு வகையான இரண்டு-கட்ட உறுதிமொழி). இந்த குறிப்பிடத்தக்க நிகழ்வுக்குப் பிறகு, விநியோகிக்கப்பட்ட பரிவர்த்தனை முடிந்ததாக நாங்கள் கருதுகிறோம்.
எனவே, ஒரு எளிய வழக்கில் ஒருமித்த வழிமுறை நான்கு படிகளைக் கொண்டுள்ளது: முன்மொழிதல், வாக்களிப்பது (வாக்களிப்பது), ஏற்றுக்கொள்வது (ஏற்றுக்கொள்வது), ஏற்றுக்கொள்வதை உறுதிப்படுத்துவது (ஏற்றுக்கொள்ளப்பட்டது).
சில கட்டத்தில் எங்களால் உடன்பாட்டை எட்ட முடியவில்லை என்றால், முன்மொழியப்பட்ட மதிப்பை உறுதிப்படுத்த மறுத்த முனைகள் வழங்கிய தகவலை கணக்கில் எடுத்துக்கொண்டு, வழிமுறை மீண்டும் தொடங்குகிறது.
ஒத்திசைவற்ற அமைப்பில் ஒருமித்த அல்காரிதம்
இதற்கு முன், எல்லாம் சீராக இருந்தது, ஏனென்றால் நாங்கள் ஒரு ஒத்திசைவான செய்தி மாதிரியைப் பற்றி பேசுகிறோம். ஆனால் நவீன உலகில் நாம் எல்லாவற்றையும் ஒத்திசைவின்றி செய்யப் பழகிவிட்டோம் என்பதை நாம் அறிவோம். ஒத்திசைவற்ற செய்தியிடல் மாதிரியைக் கொண்ட கணினியில் இதேபோன்ற வழிமுறை எவ்வாறு செயல்படுகிறது, அங்கு ஒரு முனையிலிருந்து பதிலுக்கான காத்திருப்பு நேரம் தன்னிச்சையாக நீண்டதாக இருக்கும் என்று நாங்கள் நம்புகிறோம் (இதன் மூலம், ஒரு முனையின் தோல்வியும் ஒரு உதாரணமாகக் கருதப்படலாம். ஒரு முனை தன்னிச்சையாக நீண்ட நேரம் பதிலளிக்க முடியும் ).
ஒருமித்த அல்காரிதம் கொள்கையளவில் எவ்வாறு செயல்படுகிறது என்பதை இப்போது நாம் அறிவோம், அதை இதுவரை செய்த ஆர்வமுள்ள வாசகர்களுக்கு ஒரு கேள்வி: ஒத்திசைவற்ற செய்தி மாதிரியுடன் கூடிய N முனைகளின் அமைப்பில் எத்தனை முனைகள் தோல்வியடையும், இதனால் கணினி இன்னும் ஒருமித்த கருத்தை அடைய முடியும்?
ஸ்பாய்லருக்குப் பின்னால் சரியான பதில் மற்றும் நியாயம் உள்ளது.சரியான பதில்: 0. ஒத்திசைவற்ற அமைப்பில் ஒரு முனை கூட தோல்வியுற்றால், கணினி ஒருமித்த கருத்தை அடைய முடியாது. இந்த அறிக்கை FLP தேற்றத்தில் நிரூபிக்கப்பட்டுள்ளது, சில வட்டாரங்களில் நன்கு அறியப்பட்ட (1985, பிஷ்ஷர், லிஞ்ச், பேட்டர்சன், கட்டுரையின் முடிவில் அசல் இணைப்பு): ."
நண்பர்களே, எங்களுக்கு ஒரு சிக்கல் உள்ளது, நாம் எல்லாமே ஒத்திசைவற்றதாக இருக்கப் பழகிவிட்டோம். இதோ அது. எப்படி தொடர்ந்து வாழ்வது?
நாங்கள் கோட்பாட்டைப் பற்றி, கணிதத்தைப் பற்றி பேசிக் கொண்டிருந்தோம். "ஒருமித்த கருத்தை அடைய முடியாது" என்றால், கணித மொழியிலிருந்து நமது - பொறியியல் -க்கு மொழிபெயர்ப்பது என்ன? இதன் பொருள் "எப்போதும் அடைய முடியாது", அதாவது. ஒருமித்த கருத்து ஏற்படாத வழக்கு உள்ளது. இது என்ன மாதிரியான வழக்கு?
இது மேலே விவரிக்கப்பட்ட வாழ்வாதாரச் சொத்தின் மீறலாகும். எங்களிடம் பொதுவான ஒப்பந்தம் இல்லை, மேலும் கணினியில் முன்னேற்றம் இருக்க முடியாது (ஒரு வரையறுக்கப்பட்ட நேரத்தில் முடிக்க முடியாது) எல்லா முனைகளிலிருந்தும் எங்களுக்கு பதில் இல்லை. ஏனெனில் ஒரு ஒத்திசைவற்ற அமைப்பில் எங்களிடம் கணிக்கக்கூடிய மறுமொழி நேரம் இல்லை, மேலும் ஒரு முனை செயலிழந்ததா அல்லது பதிலளிக்க நீண்ட நேரம் எடுக்கிறதா என்பதை எங்களால் அறிய முடியாது.
ஆனால் நடைமுறையில் நாம் தீர்வு காணலாம். தோல்விகள் ஏற்பட்டால் எங்கள் அல்காரிதம் நீண்ட நேரம் வேலை செய்யட்டும் (சாத்தியமாக அது காலவரையின்றி வேலை செய்யும்). ஆனால் பெரும்பாலான சூழ்நிலைகளில், பெரும்பாலான முனைகள் சரியாகச் செயல்படும் போது, கணினியில் முன்னேற்றம் ஏற்படும்.
நடைமுறையில், நாங்கள் ஓரளவு ஒத்திசைவான தொடர்பு மாதிரிகளைக் கையாளுகிறோம். பகுதி ஒத்திசைவு பின்வருமாறு புரிந்து கொள்ளப்படுகிறது: பொது வழக்கில், எங்களிடம் ஒரு ஒத்திசைவற்ற மாதிரி உள்ளது, ஆனால் ஒரு குறிப்பிட்ட நேரத்தின் "உலகளாவிய நிலைப்படுத்தல் நேரம்" என்ற ஒரு குறிப்பிட்ட கருத்து முறையாக அறிமுகப்படுத்தப்பட்டது.
இந்த தருணம் எந்த நேரத்திலும் வராது, ஆனால் அது ஒரு நாள் வர வேண்டும். மெய்நிகர் அலாரம் கடிகாரம் ஒலிக்கும், அந்த தருணத்திலிருந்து செய்திகள் வரும் நேர டெல்டாவை நாம் கணிக்க முடியும். இந்த தருணத்திலிருந்து, கணினி ஒத்திசைவற்றதாக இருந்து ஒத்திசைவாக மாறுகிறது. நடைமுறையில், துல்லியமாக அத்தகைய அமைப்புகளை நாங்கள் கையாளுகிறோம்.
Paxos அல்காரிதம் ஒருமித்த பிரச்சனைகளை தீர்க்கிறது
சில கணுக்கள் தோல்வியடையும் சாத்தியக்கூறுகளுக்கு உட்பட்டு, பகுதியளவு ஒத்திசைவான அமைப்புகளுக்கான ஒருமித்த சிக்கலை தீர்க்கும் அல்காரிதம்களின் குடும்பமாகும். பாக்சோஸின் ஆசிரியர் . அவர் 1989 இல் அல்காரிதத்தின் இருப்பு மற்றும் சரியான தன்மைக்கான முறையான ஆதாரத்தை முன்மொழிந்தார்.
ஆனால் ஆதாரம் அற்பமானது அல்ல. முதல் வெளியீடு 1998 இல் (33 பக்கங்கள்) அல்காரிதத்தை விவரிக்கிறது. அது முடிந்தவுடன், புரிந்துகொள்வது மிகவும் கடினமாக இருந்தது, மேலும் 2001 இல் கட்டுரையின் விளக்கம் வெளியிடப்பட்டது, இது 14 பக்கங்களை எடுத்தது. பிரசுரங்களின் அளவு உண்மையில் ஒருமித்த பிரச்சனை எளிமையானது அல்ல என்பதைக் காட்டுவதற்காக கொடுக்கப்பட்டுள்ளது, மேலும் அத்தகைய வழிமுறைகளுக்குப் பின்னால் புத்திசாலித்தனமான நபர்களால் ஒரு பெரிய அளவு வேலை உள்ளது.
லெஸ்லி லாம்போர்ட் தனது விரிவுரையில் இரண்டாவது விளக்கக் கட்டுரையில் ஒரு அறிக்கை, ஒரு வரி (எதை அவர் குறிப்பிடவில்லை) வெவ்வேறு வழிகளில் விளக்கலாம் என்று குறிப்பிட்டது சுவாரஸ்யமானது. இதன் காரணமாக, அதிக எண்ணிக்கையிலான நவீன பாக்சோஸ் செயலாக்கங்கள் முற்றிலும் சரியாக வேலை செய்யவில்லை.
பாக்ஸோஸின் பணியின் விரிவான பகுப்பாய்வு ஒன்றுக்கு மேற்பட்ட கட்டுரைகளை எடுக்கும், எனவே வழிமுறையின் முக்கிய யோசனையை மிக சுருக்கமாக தெரிவிக்க முயற்சிப்பேன். எனது கட்டுரையின் முடிவில் உள்ள இணைப்புகளில் இந்த தலைப்பில் மேலும் டைவிங் செய்வதற்கான பொருட்களை நீங்கள் காணலாம்.
Paxos இல் பாத்திரங்கள்
பாக்ஸோஸ் அல்காரிதம் பாத்திரங்களின் கருத்தைக் கொண்டுள்ளது. மூன்று முக்கியவற்றைக் கருத்தில் கொள்வோம் (கூடுதல் பாத்திரங்களுடன் மாற்றங்கள் உள்ளன):
- முன்மொழிபவர்கள் (விதிமுறைகளும் பயன்படுத்தப்படலாம்: தலைவர்கள் அல்லது ஒருங்கிணைப்பாளர்கள்). பயனரிடமிருந்து சில புதிய மதிப்பைப் பற்றி அறிந்துகொண்டு தலைவரின் பாத்திரத்தை ஏற்கும் தோழர்களே இவர்கள். ஒரு புதிய மதிப்புக்கான ஒரு சுற்று முன்மொழிவுகளைத் தொடங்குவதும் முனைகளின் மேலும் செயல்களை ஒருங்கிணைப்பதும் அவர்களின் பணி. மேலும், பாக்ஸோஸ் சில சூழ்நிலைகளில் பல தலைவர்களின் இருப்பை அனுமதிக்கிறது.
- ஏற்பாளர்கள் (வாக்காளர்கள்). இவை ஒரு குறிப்பிட்ட மதிப்பை ஏற்க அல்லது நிராகரிக்க வாக்களிக்கும் முனைகளாகும். அவர்களின் பங்கு மிகவும் முக்கியமானது, ஏனென்றால் முடிவு அவர்களைப் பொறுத்தது: ஒருமித்த வழிமுறையின் அடுத்த கட்டத்திற்குப் பிறகு கணினி எந்த நிலைக்குச் செல்லும் (அல்லது செல்லாது).
- கற்கும். கணினியின் நிலை மாறும்போது புதிய ஏற்றுக்கொள்ளப்பட்ட மதிப்பை வெறுமனே ஏற்றுக்கொண்டு எழுதும் முனைகள். அவர்கள் முடிவுகளை எடுப்பதில்லை, அவர்கள் தரவைப் பெறுகிறார்கள் மற்றும் இறுதிப் பயனருக்குக் கொடுக்க முடியும்.
ஒரு முனை வெவ்வேறு சூழ்நிலைகளில் பல பாத்திரங்களை இணைக்க முடியும்.
குழுமத்தின் கருத்து
எங்களிடம் ஒரு அமைப்பு இருப்பதாக நாங்கள் கருதுகிறோம் N முனைகள் மற்றும் அவற்றில் அதிகபட்சம் F முனைகள் தோல்வியடையலாம். எஃப் கணுக்கள் தோல்வியுற்றால், குறைந்தபட்சம் நம்மிடம் இருக்க வேண்டும் 2F+1 ஏற்பி முனைகள்.
இது அவசியமானது, அதனால் நாம் எப்போதும் பெரும்பான்மையாக இருக்க வேண்டும், மோசமான சூழ்நிலையில் கூட, சரியாக வேலை செய்யும் "நல்ல" முனைகள். அது எஃப் + 1 ஒப்புக்கொண்ட "நல்ல" முனைகள் மற்றும் இறுதி மதிப்பு ஏற்றுக்கொள்ளப்படும். இல்லையெனில், நமது வெவ்வேறு உள்ளூர் குழுக்கள் வெவ்வேறு அர்த்தங்களை எடுத்துக்கொண்டு தங்களுக்குள் ஒத்துப்போக முடியாத சூழ்நிலை ஏற்படலாம். எனவே, வாக்குகளை வெல்ல அறுதிப் பெரும்பான்மை வேண்டும்.
Paxos ஒருமித்த வழிமுறை எவ்வாறு செயல்படுகிறது என்பது பற்றிய பொதுவான யோசனை
பாக்ஸோஸ் அல்காரிதம் இரண்டு பெரிய கட்டங்களை உள்ளடக்கியது, அவை ஒவ்வொன்றும் இரண்டு படிகளாக பிரிக்கப்படுகின்றன:
- கட்டம் 1a: தயார். தயாரிப்பு கட்டத்தில், தலைவர் (முன்மொழிபவர்) அனைத்து முனைகளுக்கும் தெரிவிக்கிறார்: “நாங்கள் ஒரு புதிய வாக்களிப்பு கட்டத்தைத் தொடங்குகிறோம். எங்களிடம் ஒரு புதிய சுற்று உள்ளது. இந்த சுற்றின் எண் n. இப்போது நாங்கள் வாக்களிக்கத் தொடங்குவோம்." இப்போதைக்கு, இது ஒரு புதிய சுழற்சியின் தொடக்கத்தைப் புகாரளிக்கிறது, ஆனால் புதிய மதிப்பைப் புகாரளிக்காது. இந்த கட்டத்தின் பணியானது ஒரு புதிய சுற்றைத் தொடங்கி அதன் தனித்துவமான எண்ணை அனைவருக்கும் தெரிவிப்பதாகும். சுற்று எண் முக்கியமானது, இது அனைத்து முந்தைய தலைவர்களின் முந்தைய வாக்கு எண்களை விட அதிகமாக இருக்க வேண்டும். ஏனென்றால், வட்ட எண்ணுக்கு நன்றி, தலைவரின் தரவு எவ்வளவு சமீபத்தியது என்பதை கணினியில் உள்ள மற்ற முனைகள் புரிந்து கொள்ளும். பிற கணுக்கள் ஏற்கனவே மிகவும் பிந்தைய சுற்றுகளிலிருந்து வாக்களிப்பு முடிவுகளைப் பெற்றிருக்கலாம், மேலும் அவர் காலத்திற்குப் பின்தங்கியிருப்பதைத் தலைவருக்குச் சொல்லும்.
- கட்டம் 1b: வாக்குறுதி. ஏற்பி முனைகள் புதிய வாக்களிப்பு கட்டத்தின் எண்ணிக்கையைப் பெற்றால், இரண்டு முடிவுகள் சாத்தியமாகும்:
- புதிய வாக்கின் எண் n என்பது, ஏற்றுக்கொள்பவர் பங்கு பெற்ற முந்தைய வாக்குகளின் எண்ணிக்கையை விட அதிகமாக உள்ளது. பின்னர் ஏற்றுக்கொள்பவர், n ஐ விடக் குறைவான எண்ணிக்கையில் இனி எந்த வாக்குகளிலும் பங்கேற்க மாட்டோம் என்ற உறுதிமொழியை தலைவருக்கு அனுப்புகிறார். ஏற்றுக்கொள்பவர் ஏற்கனவே ஏதோவொன்றிற்கு வாக்களித்திருந்தால் (அதாவது, அது ஏற்கனவே இரண்டாவது கட்டத்தில் சில மதிப்பை ஏற்றுக்கொண்டது), பின்னர் அது ஏற்றுக்கொள்ளப்பட்ட மதிப்பையும் அவர் பங்குபெற்ற வாக்குகளின் எண்ணிக்கையையும் அதன் வாக்குறுதியுடன் இணைக்கிறது.
- இல்லையெனில், ஏற்றுக்கொள்பவர் ஏற்கனவே அதிக எண்ணிக்கையிலான வாக்குகளைப் பற்றி அறிந்திருந்தால், அது தயாரிப்புப் படியை வெறுமனே புறக்கணித்து, தலைவருக்கு பதிலளிக்காது.
- கட்டம் 2a: ஏற்றுக்கொள். குழுவிலிருந்து (அமைப்பில் உள்ள பெரும்பாலான முனைகள்) பதிலுக்காக தலைவர் காத்திருக்க வேண்டும், மேலும் தேவையான எண்ணிக்கையிலான பதில்கள் பெறப்பட்டால், நிகழ்வுகளின் வளர்ச்சிக்கு அவருக்கு இரண்டு விருப்பங்கள் உள்ளன:
- ஏற்றுக்கொள்பவர்களில் சிலர் தாங்கள் ஏற்கனவே வாக்களித்த மதிப்புகளை அனுப்பியுள்ளனர். இந்த வழக்கில், தலைவர் அதிகபட்ச எண்ணைக் கொண்ட வாக்கிலிருந்து மதிப்பைத் தேர்ந்தெடுக்கிறார். இந்த மதிப்பை x என்று அழைப்போம், மேலும் இது அனைத்து முனைகளுக்கும் ஒரு செய்தியை அனுப்புகிறது: “ஏற்றுக்கொள்ளுங்கள் (n, x)”, அங்கு முதல் மதிப்பு அதன் சொந்த முன்மொழிவு படியிலிருந்து வாக்களிக்கும் எண்ணாகும், மேலும் இரண்டாவது மதிப்பு அனைவரும் ஒன்றுகூடியது, அதாவது நாம் உண்மையில் வாக்களிக்கும் மதிப்பு.
- ஏற்றுக்கொள்பவர்களில் யாரும் எந்த மதிப்புகளையும் அனுப்பவில்லை, ஆனால் அவர்கள் இந்த சுற்றில் வாக்களிப்பதாக உறுதியளித்திருந்தால், தலைவர் அவர்களின் மதிப்புக்கு வாக்களிக்க அவர்களை அழைக்கலாம், அவர் முதலில் ஒரு தலைவராக ஆனார். y என்று அழைப்போம். முந்தைய முடிவைப் போலவே, "ஏற்றுக்கொள் (n, y)" போன்ற அனைத்து முனைகளுக்கும் இது ஒரு செய்தியை அனுப்புகிறது.
- கட்டம் 2b: ஏற்றுக்கொள்ளப்பட்டது. மேலும், ஏற்பு முனைகள், தலைவரிடமிருந்து “ஏற்றுக்கொள்(...)” செய்தியைப் பெற்றவுடன், அதை ஏற்றுக்கொள்கின்றன (அவர்கள் புதிய மதிப்புடன் உடன்படுகிறார்கள் என்று அனைத்து முனைகளுக்கும் உறுதிப்படுத்தல் அனுப்பவும்) அவர்கள் சில (வேறு) உறுதியளிக்கவில்லை என்றால் மட்டுமே ) வட்ட எண்ணுடன் வாக்களிப்பில் பங்கேற்க தலைவர் n' > n, இல்லையெனில் அவர்கள் உறுதிப்படுத்தல் கோரிக்கையை புறக்கணிப்பார்கள்.
பெரும்பாலான முனைகள் தலைவருக்கு பதிலளித்தால், அவை அனைத்தும் புதிய மதிப்பை உறுதிப்படுத்தினால், புதிய மதிப்பு ஏற்றுக்கொள்ளப்பட்டதாகக் கருதப்படுகிறது. ஹூரே! பெரும்பான்மையை அடையவில்லை அல்லது புதிய மதிப்பை ஏற்க மறுத்த முனைகள் இருந்தால், எல்லாம் மீண்டும் தொடங்குகிறது.
Paxos அல்காரிதம் இப்படித்தான் செயல்படுகிறது. இந்த நிலைகள் ஒவ்வொன்றிலும் பல நுணுக்கங்கள் உள்ளன, நடைமுறையில் பல்வேறு வகையான தோல்விகள், பல தலைவர்களின் பிரச்சினைகள் மற்றும் பலவற்றை நாங்கள் கருத்தில் கொள்ளவில்லை, ஆனால் இந்த கட்டுரையின் நோக்கம் வாசகரை உயர் மட்டத்தில் விநியோகிக்கப்பட்ட கணினி உலகிற்கு அறிமுகப்படுத்துவது மட்டுமே.
பாக்ஸோஸ் அதன் வகையானது மட்டுமல்ல, பிற வழிமுறைகள் உள்ளன என்பதும் குறிப்பிடத்தக்கது, எடுத்துக்காட்டாக, , ஆனால் இது மற்றொரு கட்டுரைக்கான தலைப்பு.
மேலதிக ஆய்வுக்கான பொருட்களுக்கான இணைப்புகள்
தொடக்க நிலை:
- , ப்ரீத்தி காசிரெட்டி, மீடியம் பற்றிய வலைப்பதிவு கட்டுரை
- , ஆதி கஞ்சர்லா, மீடியம் பற்றிய வலைப்பதிவு கட்டுரை
- , Ittai Abraham, blog
- , Ittai Abraham, blog article
லெஸ்லி லாம்போர்ட் நிலை:
- , பிஷ்ஷர், லிஞ்ச் மற்றும் பேட்டர்சன், ஆய்வுக் கட்டுரை, 1985
- , லெஸ்லி லம்போர்ட், ஆய்வுக் கட்டுரை, 1998
- , லெஸ்லி லம்போர்ட், ஆய்வுக் கட்டுரை, 2001
ஆதாரம்: www.habr.com