ඉතින්, අපි හිතමු. කාමරයේ බළලුන් 5 දෙනෙකු අගුලු දමා ඇති අතර, අයිතිකරු අවදි කිරීමට නම්, ඔවුන් සියල්ලන්ම මේ පිළිබඳව එකඟ විය යුතුය, මන්ද ඔවුන්ට දොර විවෘත කළ හැක්කේ ඔවුන්ගෙන් පස් දෙනෙකුට පමණක් හේත්තු වී සිටින බැවිනි. එක් බළලුන් ෂ්‍රොඩිංගර්ගේ බළලා නම් සහ අනෙක් බළලුන් ඔහුගේ තීරණය ගැන නොදන්නේ නම්, ප්‍රශ්නය පැන නගී: “ඔවුන් එය කරන්නේ කෙසේද?”
මෙම ලිපියෙන්, බෙදා හරින ලද පද්ධතිවල ලෝකයේ න්‍යායාත්මක සංරචකය සහ ඒවායේ ක්‍රියාකාරිත්වයේ මූලධර්ම පිළිබඳව සරල වචන වලින් මම ඔබට කියමි. Paxos යටින් පවතින ප්රධාන අදහස ද මම මතුපිටින් සලකා බලමි.
සංවර්ධකයින් වලාකුළු යටිතල ව්‍යුහයන්, විවිධ දත්ත සමුදායන් භාවිතා කරන විට සහ නෝඩ් විශාල සංඛ්‍යාවක පොකුරුවල වැඩ කරන විට, දත්ත සම්පුර්ණ, ආරක්ෂිත සහ සැමවිටම ලබා ගත හැකි බවට ඔවුන් විශ්වාස කරයි. නමුත් සහතික කොහෙද?
අත්යවශ්යයෙන්ම, අප සතුව ඇති ඇපකර සැපයුම්කරුගේ ඇපකර වේ. ඒවා ප්‍රලේඛනයේ පහත පරිදි විස්තර කර ඇත: "මෙම සේවාව තරමක් විශ්වාසදායක ය, එයට ලබා දී ඇති SLA ඇත, කරදර නොවන්න, ඔබ අපේක්ෂා කරන පරිදි සියල්ල බෙදා හරිනු ඇත."
අපි හොඳම දේ විශ්වාස කිරීමට නැඹුරු වෙමු, මන්ද විශාල සමාගම්වල දක්ෂ පුද්ගලයින් සියල්ල හොඳින් සිදුවන බවට අපට සහතික විය. අපි ප්‍රශ්නය අසන්නේ නැත: ඇත්ත වශයෙන්ම මෙය කිසිසේත් ක්රියාත්මක විය හැක්කේ ඇයි? එවැනි පද්ධතිවල නිවැරදි ක්‍රියාකාරිත්වය සඳහා විධිමත් සාධාරණීකරණයක් තිබේද?
මම ළඟදී ගියා සහ මෙම මාතෘකාවෙන් බොහෝ ආභාෂය ලැබීය. පාසැලේ දේශන පරිගණක පද්ධති හා සම්බන්ධ දෙයකට වඩා කලනය පන්ති වලට සමාන විය. නමුත් අපි නොදැනුවත්වම අපි එදිනෙදා භාවිතා කරන වැදගත්ම ඇල්ගොරිතම එකවරම ඔප්පු වූයේ එලෙසයි.
බොහෝ නවීන බෙදා හරින ලද පද්ධති Paxos සම්මුති ඇල්ගොරිතම සහ එහි විවිධ වෙනස් කිරීම් භාවිතා කරයි. සිසිල්ම දෙය නම් වලංගු භාවය සහ ප්‍රතිපත්තිමය වශයෙන්, මෙම ඇල්ගොරිතමයේ පැවැත්මේ හැකියාව පෑනකින් සහ කඩදාසියකින් සරලව ඔප්පු කළ හැකි වීමයි. ප්රායෝගිකව, වලාකුළු වල නෝඩ් විශාල සංඛ්යාවක් මත ධාවනය වන විශාල පද්ධතිවල ඇල්ගොරිතම භාවිතා වේ.
ඊළඟට සාකච්ඡා කෙරෙන දේ පිළිබඳ සැහැල්ලු නිදර්ශනයක්: ජෙනරාල්වරුන් දෙදෙනෙකුගේ කාර්යයඋණුසුම් කිරීමක් සඳහා අපි බලමු .
අපට හමුදාවන් දෙකක් ඇත - රතු සහ සුදු. වටලනු ලැබූ නගරයේ සුදු හමුදා පදනම් වී ඇත. A1 සහ A2 ජෙනරාල්වරුන්ගේ නායකත්වයෙන් යුත් රතු භට පිරිස් නගරයේ දෙපස පිහිටා ඇත. රතු හෙඩ්ස්ගේ කාර්යය වන්නේ සුදු නගරයට පහර දී ජයග්රහණය කිරීමයි. කෙසේ වෙතත්, එක් එක් රතු ජෙනරාල්ගේ හමුදාව තනි තනිව සුදු හමුදාවට වඩා කුඩා වේ.
රතු අයට ජයග්‍රාහී කොන්දේසි: සුදු ජාතිකයින්ට වඩා සංඛ්‍යාත්මක වාසියක් ලබා ගැනීම සඳහා ජෙනරාල්වරුන් දෙදෙනාම එකවර පහර දිය යුතුය. මෙය සිදු කිරීම සඳහා, A1 සහ A2 ජෙනරාල්වරුන් එකිනෙකා සමඟ එකඟතාවයකට පැමිණිය යුතුය. හැමෝම වෙන වෙනම පහර දුන්නොත්, රතු හිස් අහිමි වනු ඇත.
එකඟතාවයක් ඇති කර ගැනීම සඳහා, A1 සහ A2 ජෙනරාල්වරුන්ට සුදු නගරයේ භූමිය හරහා එකිනෙකා වෙත පණිවිඩකරුවන් යැවිය හැකිය. පණිවිඩකරු මිත්‍ර හමුදාපතිවරයෙකු වෙත සාර්ථකව ළඟා විය හැකිය, නැතහොත් සතුරාට බාධා කළ හැකිය. ප්‍රශ්නය: රතු හිසකෙස් ඇති ජෙනරාල්වරුන් අතර එවැනි සන්නිවේදන අනුපිළිවෙලක් තිබේද (A1 සිට A2 දක්වා සහ අනෙක් අතට A2 සිට A1 දක්වා පණිවිඩකරුවන් යැවීමේ අනුපිළිවෙල), එහිදී ඔවුන් X පැයේදී ප්‍රහාරයකට එකඟ වන බවට සහතික වේ. මෙහි, සහතිකය යන්නෙන් අදහස් කරන්නේ නියමිත X වේලාවේදී මිත්‍රයෙකු (තවත් ජෙනරාල්) නියත වශයෙන්ම ප්‍රහාර එල්ල කරන බවට ජෙනරාල්වරුන් දෙදෙනාටම නොපැහැදිලි තහවුරු කිරීමක් ඇති බවයි.
“අපි අද මධ්‍යම රාත්‍රියේ පහර දෙමු!” යන පණිවිඩය සමඟ A1 විසින් A2 වෙත පණිවිඩකරුවෙකු යවයි යැයි සිතමු. ජෙනරාල් A1 ගේ තහවුරු කිරීමකින් තොරව ජෙනරල් A2 ට පහර දිය නොහැක. A1 හි පණිවිඩකරු පැමිණ තිබේ නම්, ජෙනරාල් A2 පණිවිඩය සමඟ තහවුරු කිරීමක් යවයි: "ඔව්, අපි අද සුදු ජාතිකයන් මරා දමමු." නමුත් දැන් ජෙනරාල් A2 ඔහුගේ පණිවිඩකරු පැමිණ තිබේද නැද්ද යන්න දන්නේ නැත, ප්‍රහාරය එකවර සිදුවේද යන්න ගැන ඔහුට සහතිකයක් නැත. දැන් General A2 නැවත තහවුරු කිරීම අවශ්ය වේ.
අපි ඔවුන්ගේ සන්නිවේදනය තවදුරටත් විස්තර කරන්නේ නම්, කොපමණ පණිවිඩ හුවමාරු චක්‍ර තිබුණත්, ජෙනරාල්වරුන් දෙදෙනාටම ඔවුන්ගේ පණිවිඩ ලැබී ඇති බවට සහතික වීමට ක්‍රමයක් නොමැති බව පැහැදිලි වේ (එක්කෝ පණිවිඩකරුවෙකුට බාධා කළ හැකි යැයි උපකල්පනය කළ හැකිය).
ටූ ජෙනරල් ගැටළුව යනු විශ්වාස කළ නොහැකි සන්නිවේදනයක් සහිත නෝඩ් දෙකක් ඇති ඉතා සරල බෙදාහැරීමේ පද්ධතියක විශිෂ්ට නිදර්ශනයකි. මෙයින් අදහස් කරන්නේ ඒවා සමමුහුර්ත කර ඇති බවට අපට 100% සහතිකයක් නොමැති බවයි. සමාන ගැටළු පසුව ලිපියේ විශාල පරිමාණයෙන් පමණක් සාකච්ඡා කෙරේ.
අපි බෙදාහැරීමේ පද්ධති සංකල්පය හඳුන්වා දෙන්නෙමු
බෙදා හරින ලද පද්ධතියක් යනු පණිවිඩ හුවමාරු කර ගත හැකි පරිගණක සමූහයකි (මින් ඉදිරියට අපි ඒවා නෝඩ් ලෙස හඳුන්වමු). සෑම තනි නෝඩයක්ම යම් ආකාරයක ස්වාධීන ආයතනයකි. නෝඩයකට තනිවම කාර්යයන් සැකසිය හැක, නමුත් වෙනත් නෝඩ් සමඟ සන්නිවේදනය කිරීම සඳහා, එය පණිවිඩ යැවීමට සහ ලැබීමට අවශ්ය වේ.
පණිවිඩ නිවැරදිව ක්රියාත්මක කරන්නේ කෙසේද, කුමන ප්‍රොටෝකෝල භාවිතා කරන්නේද - මෙය මෙම සන්දර්භය තුළ අපට උනන්දුවක් නොදක්වයි. බෙදා හරින ලද පද්ධතියක නෝඩ් පණිවිඩ යැවීමෙන් එකිනෙකා සමඟ දත්ත හුවමාරු කර ගත හැකි බව වැදගත් වේ.
නිර්වචනය ඉතා සංකීර්ණ බවක් නොපෙනේ, නමුත් බෙදා හරින ලද පද්ධතියකට අපට වැදගත් වන ගුණාංග ගණනාවක් ඇති බව අප සැලකිල්ලට ගත යුතුය.
බෙදා හරින ලද පද්ධතිවල ගුණාංග
- සමගාමී මුදල් - පද්ධතිය තුළ එකවර හෝ සමගාමී සිදුවීම් ඇතිවීමේ හැකියාව. එපමනක් නොව, මෙම සිදුවීම්වල පැහැදිලි අනුපිළිවෙලක් නොමැති තාක් දුරට විවිධ නෝඩ් දෙකක සිදුවන සිදුවීම් සමගාමී විය හැකි බව අපි සලකමු. නමුත්, නීතියක් ලෙස, අපට එය නැත.
- ගෝලීය ඔරලෝසුවක් නැත. ගෝලීය ඔරලෝසුවක් නොමැතිකම නිසා අපට පැහැදිලි සිදුවීම් අනුපිළිවෙලක් නොමැත. සාමාන්‍ය මිනිසුන්ගේ ලෝකය තුළ, අපට නියත වශයෙන්ම ඔරලෝසු සහ වේලාව ඇති බවට අපි පුරුදු වී සිටිමු. බෙදා හරින ලද පද්ධති සම්බන්ධයෙන් සෑම දෙයක්ම වෙනස් වේ. අතිශය නිරවද්‍ය පරමාණුක ඔරලෝසු පවා ප්ලාවිතය ඇති අතර, සිදුවීම් දෙකෙන් මුලින්ම සිදුවූයේ කුමක්දැයි අපට පැවසිය නොහැකි අවස්ථා තිබිය හැක. එමනිසා, අපට කාලය මත විශ්වාසය තැබිය නොහැක.
- පද්ධති නෝඩ් වල ස්වාධීන අසාර්ථකත්වය. තවත් ගැටළුවක් තිබේ: අපගේ නෝඩ් සදහටම නොපවතින නිසා යමක් වැරදී යා හැක. දෘඪ තැටිය අසාර්ථක විය හැක, වලාකුළෙහි ඇති අථත්ය යන්ත්රය නැවත ආරම්භ විය හැක, ජාලය ඇසිපිය හෙළීම සහ පණිවිඩ අහිමි වනු ඇත. එපමනක් නොව, නෝඩ් වැඩ කරන අවස්ථා තිබිය හැක, නමුත් ඒ සමඟම පද්ධතියට එරෙහිව ක්රියා කරයි. අවසාන පන්තියේ ගැටළු වලට වෙනම නමක් පවා ලැබුණි: ගැටලුව . මෙම ගැටළුව සමඟ බෙදා හරින ලද පද්ධතියක වඩාත්ම ජනප්රිය උදාහරණය වන්නේ Blockchain වේ. නමුත් අද අපි මෙම විශේෂ පන්ති ගැටළු සලකා බලන්නේ නැත. නෝඩ් එකක් හෝ කිහිපයක් අසමත් විය හැකි තත්වයන් ගැන අපි උනන්දු වනු ඇත.
- නෝඩ් අතර සන්නිවේදන ආකෘති (පණිවිඩකරණ ආකෘති).. පණිවිඩ හුවමාරු කර ගැනීමෙන් නෝඩ් සන්නිවේදනය කරන බව අපි දැනටමත් තහවුරු කර ඇත. සුප්‍රසිද්ධ පණිවිඩකරණ ආකෘති දෙකක් තිබේ: සමමුහුර්ත සහ අසමමුහුර්ත.
බෙදා හරින ලද පද්ධතිවල නෝඩ් අතර සන්නිවේදනයේ ආකෘති
සමමුහුර්ත ආකෘතිය - පණිවිඩයක් එක් නෝඩයකින් තවත් නෝඩයකට ළඟා වන බවට සහතික වන සීමිත දන්නා ඩෙල්ටාවක් ඇති බව අපි නිසැකවම දනිමු. මෙම කාලය ගෙවී ගොස් ඇති අතර පණිවිඩය පැමිණ නොමැති නම්, නෝඩය අසාර්ථක වී ඇති බව අපට ආරක්ෂිතව පැවසිය හැකිය. මෙම ආකෘතිය තුළ අපට පුරෝකථනය කළ හැකි පොරොත්තු කාලයන් ඇත.
අසමමුහුර්ත ආකෘතිය - අසමමුහුර්ත ආකෘති වලදී අපි බලා සිටින කාලය සීමිත බව සලකමු, නමුත් නෝඩය අසාර්ථක වී ඇති බවට සහතික විය හැකි එවැනි කාල ඩෙල්ටාවක් නොමැත. එම. නෝඩයකින් පණිවිඩයක් සඳහා පොරොත්තු කාලය අත්තනෝමතික ලෙස දිගු විය හැක. මෙය වැදගත් නිර්වචනයක් වන අතර, අපි එය තවදුරටත් කතා කරමු.
බෙදා හරින ලද පද්ධතිවල සම්මුතිය පිළිබඳ සංකල්පය
සම්මුතිය පිළිබඳ සංකල්පය විධිමත් ලෙස අර්ථ දැක්වීමට පෙර, අපට එය අවශ්ය වන තත්වයක් පිළිබඳ උදාහරණයක් සලකා බලමු, එනම් - රාජ්ය යන්ත්ර අනුකරණය.
අප සතුව බෙදා හරින ලද ලොග් කිහිපයක් තිබේ. බෙදා හරින ලද පද්ධතියේ සියලුම නෝඩ් වල එය ස්ථාවර වීමට සහ සමාන දත්ත අඩංගු වීමට අපි කැමතියි. එක් නෝඩයක් එය ලඝු-සටහනට ලිවීමට යන නව අගයක් ඉගෙන ගත් විට, එහි කාර්යය වන්නේ අනෙකුත් සියලුම නෝඩ් වෙත මෙම අගය ලබා දීමයි, එවිට ලොගය සියලු නෝඩ් වල යාවත්කාලීන වන අතර පද්ධතිය නව ස්ථාවර තත්වයකට ගමන් කරයි. මෙම අවස්ථාවෙහිදී, නෝඩ් තමන් අතර එකඟ වීම වැදගත්ය: යෝජිත නව අගය නිවැරදි බව සියලුම නෝඩ් එකඟ වේ, සියලුම නෝඩ් මෙම අගය පිළිගනී, සහ මෙම අවස්ථාවේදී පමණක් සෑම කෙනෙකුටම නව අගය ලොගයට ලිවිය හැකිය.
වෙනත් වචන වලින් කිවහොත්: කිසිදු නෝඩයක් එයට වඩා අදාළ තොරතුරු ඇති බවට විරුද්ධ නොවූ අතර යෝජිත අගය වැරදිය. නෝඩ් අතර ගිවිසුම සහ තනි නිවැරදි පිළිගත් අගයක් පිළිබඳ එකඟතාවය බෙදාහැරීමේ පද්ධතියක සම්මුතියකි. ඊළඟට, අපි බෙදා හරින ලද පද්ධතියකට සම්මුතිය සහතික කර ගැනීමට ඉඩ සලසන ඇල්ගොරිතම ගැන කතා කරමු.
වඩාත් විධිමත් ලෙස, අපට සම්මුති ඇල්ගොරිතමයක් (හෝ සරලව සම්මුති ඇල්ගොරිතමයක්) යම් කාර්යයක් ලෙස අර්ථ දැක්විය හැක, එය බෙදා හරින ලද පද්ධතියක් A සිට තත්වයට B දක්වා මාරු කරයි. එපමණක් නොව, මෙම තත්වය සියලුම නෝඩ් විසින් පිළිගනු ලබන අතර, සියලුම නෝඩ් වලට එය තහවුරු කළ හැක. එය පෙනෙන පරිදි, මෙම කාර්යය මුලින්ම බැලූ බැල්මට පෙනෙන තරම් සුළු දෙයක් නොවේ.
සම්මුති ඇල්ගොරිතමයේ ගුණාංග
පද්ධතිය අඛණ්ඩව පැවතීමට සහ ප්‍රාන්තයෙන් රාජ්‍යයට ගමන් කිරීමේදී යම් ප්‍රගතියක් ලබා ගැනීමට සම්මුති ඇල්ගොරිතමයට ගුණාංග තුනක් තිබිය යුතුය:
- ගිවිසුම - නිවැරදිව ක්රියාත්මක වන සියලුම නෝඩ් එකම අගයක් ගත යුතුය (ලිපි වල මෙම දේපල ආරක්ෂිත දේපල ලෙසද හැඳින්වේ). දැනට ක්රියාත්මක වන සියලුම නෝඩ් (අසාර්ථක වී හෝ අනෙක් ඒවා සමඟ සම්බන්ධතා නැති වී නැත) එකඟතාවයකට පැමිණ අවසාන පොදු අගයක් පිළිගත යුතුය.
අප සලකා බලන බෙදාහැරීමේ පද්ධතියේ නෝඩ් එකඟ වීමට අවශ්ය බව මෙහිදී තේරුම් ගැනීම වැදගත්ය. එනම්, අපි දැන් කතා කරන්නේ යමක් සරලව අසමත් විය හැකි පද්ධති ගැන ය (උදාහරණයක් ලෙස, සමහර නෝඩය අසමත් වේ), නමුත් මෙම පද්ධතියේ අනිවාර්යයෙන්ම අනෙක් අයට එරෙහිව හිතාමතා ක්රියා කරන නෝඩ් නොමැත (බයිසැන්තියානු ජෙනරාල්වරුන්ගේ කාර්යය). මෙම ගුණාංගය නිසා, පද්ධතිය ස්ථාවරව පවතී.
- අඛණ්ඩතාව - නිවැරදිව වැඩ කරන සියලුම නෝඩ් එකම අගයක් ලබා දෙන්නේ නම් v, එනම් සෑම නිවැරදිව ක්රියාත්මක වන නෝඩයක්ම මෙම අගය පිළිගත යුතුය v.
- අවසන් කිරීම - නිවැරදිව ක්රියාත්මක වන සියලුම නෝඩ් අවසානයේ යම් අගයක් (සජීවී ගුණ) ලබා ගනී, එමඟින් ඇල්ගොරිතමයට පද්ධතියේ ප්‍රගතියක් ලබා ගත හැකිය. එක් එක් පුද්ගලයා නිවැරදිව ක්රියාත්මක වන නෝඩය ඉක්මනින් හෝ පසුව අවසාන අගය පිළිගෙන එය තහවුරු කළ යුතුය: "මට, මෙම අගය සත්‍ය වේ, මම සමස්ත පද්ධතිය සමඟ එකඟ වෙමි."
සම්මුති ඇල්ගොරිතම ක්රියා කරන ආකාරය පිළිබඳ උදාහරණයක්
ඇල්ගොරිතමයේ ගුණාංග සම්පූර්ණයෙන්ම පැහැදිලි නොවිය හැක. එබැවින්, සියලු නෝඩ් අපේක්ෂා කළ පරිදි ක්රියා කරන, පණිවිඩ නැති නොවන සහ කිසිවක් කැඩී නොයන (මෙය ඇත්ත වශයෙන්ම සිදුවන්නේද?) සමමුහුර්ත පණිවිඩකරණ ආකෘතියක් සහිත පද්ධතියක් තුළ සරලම සම්මුති ඇල්ගොරිතම කුමන අදියර හරහා ගමන් කරන්නේ දැයි අපි උදාහරණයකින් පැහැදිලි කරන්නෙමු.
- ඒ සියල්ල ආරම්භ වන්නේ විවාහ යෝජනාවකින් (යෝජනා කරන්න). අපි හිතමු සේවාදායකයෙක් "Node 1" කියන node එකට සම්බන්ධ වෙලා ගණුදෙනුවක් ආරම්භ කරලා, node එකට නව අගයක් ලබාදීලා - O. මෙතැන් පටන් අපි "Node 1" කියලා කියමු. යෝජනා කිරීමට. යෝජකයෙකු ලෙස, "Node 1" දැන් මුළු පද්ධතියටම නැවුම් දත්ත ඇති බව දැනුම් දිය යුතු අතර, එය අනෙකුත් සියලුම නෝඩ් වෙත පණිවිඩ යවයි: "බලන්න! "O" යන අර්ථය මා වෙත පැමිණි අතර මට එය ලිවීමට අවශ්යයි! ඔබ ඔබේ ලොගයේ "O" ද සටහන් කරන බව කරුණාකර තහවුරු කරන්න."
- මීලඟ අදියර වන්නේ යෝජිත අගය (ඡන්දය) සඳහා ඡන්දය දීමයි. එය කුමක් සදහාද? වෙනත් නෝඩ් වලට වඩාත් මෑත කාලීන තොරතුරු ලැබී ඇති අතර, එකම ගනුදෙනුව පිළිබඳ දත්ත ඔවුන් සතුව තිබීම සිදුවිය හැක.
නෝඩය "Node 1" එහි යෝජනාව යවන විට, අනෙකුත් නෝඩ් මෙම සිදුවීම පිළිබඳ දත්ත සඳහා ඔවුන්ගේ ලොග් පරීක්ෂා කරයි. ප්රතිවිරෝධතා නොමැති නම්, නෝඩ් නිවේදනය කරයි: "ඔව්, මෙම සිදුවීම සඳහා මට වෙනත් දත්ත නොමැත. "O" අගය අපට ලැබිය යුතු නවතම තොරතුරු වේ.වෙනත් ඕනෑම අවස්ථාවක, නෝඩ් වලට "Node 1" වෙත ප්රතිචාර දැක්විය හැක: "සවන් දෙන්න! මෙම ගනුදෙනුව පිළිබඳ වඩාත් මෑත දත්ත මා සතුව ඇත. 'ඕ' නොවේ, නමුත් වඩා හොඳ දෙයක්."
ඡන්දය ප්‍රකාශ කිරීමේ අදියරේදී, නෝඩ් තීරණයකට පැමිණේ: එක්කෝ ඔවුන් සියල්ලෝම එකම අගය පිළිගනිති, නැතහොත් ඔවුන්ගෙන් එක් අයෙක් විරුද්ධව ඡන්දය ප්‍රකාශ කරයි, එයින් පෙන්නුම් කරන්නේ ඔහුට වඩාත් මෑත දත්ත ඇති බවයි.
- ඡන්ද වටය සාර්ථක වූ අතර සෑම කෙනෙකුම පක්ෂව සිටියේ නම්, පද්ධතිය නව අදියරකට ගමන් කරයි - වටිනාකම පිළිගැනීම (පිළිගන්න). "Node 1" අනෙකුත් නෝඩ් වලින් සියලුම ප්රතිචාර එකතු කර වාර්තා කරයි: "O" අගයට සියල්ලෝම එකඟ වූහ! දැන් මම නිල වශයෙන් ප්‍රකාශ කරන්නේ “O” යනු අපගේ නව අර්ථයයි, සෑම කෙනෙකුටම එක හා සමානයි! ඔබේ කුඩා පොතේ එය ලියන්න, අමතක කරන්න එපා. එය ඔබේ ලොගයේ ලියාගන්න!”
- ඉතිරි නෝඩ් "O" අගය ලියා ඇති බවට තහවුරු කිරීමක් (පිළිගත්) යවයි; මෙම කාලය තුළ අලුත් කිසිවක් පැමිණ නැත (අදියර දෙකක කැපවීමක්). මෙම වැදගත් සිදුවීමෙන් පසුව, බෙදා හරින ලද ගනුදෙනුව අවසන් වී ඇති බව අපි සලකමු.
මේ අනුව, සරල නඩුවක සම්මුති ඇල්ගොරිතම පියවර හතරකින් සමන්විත වේ: යෝජනා කිරීම, ඡන්දය දීම (ඡන්දය දීම), පිළිගැනීම (පිළිගැනීම), පිළිගැනීම තහවුරු කිරීම (පිළිගත්).
යම් පියවරකදී අපට එකඟතාවයකට පැමිණීමට නොහැකි වූවා නම්, යෝජිත අගය තහවුරු කිරීම ප්‍රතික්ෂේප කළ නෝඩ් මගින් සපයන ලද තොරතුරු සැලකිල්ලට ගනිමින් ඇල්ගොරිතම නැවත ආරම්භ වේ.
අසමමුහුර්ත පද්ධතියක සම්මුති ඇල්ගොරිතම
මෙයට පෙර, අපි සමමුහුර්ත පණිවිඩ යැවීමේ ආකෘතියක් ගැන කතා කළ නිසා සියල්ල සුමට විය. නමුත් නූතන ලෝකයේ අපි සෑම දෙයක්ම අසමමිතික ලෙස කිරීමට පුරුදු වී සිටින බව අපි දනිමු. අසමමුහුර්ත පණිවිඩකරණ ආකෘතියක් සහිත පද්ධතියක සමාන ඇල්ගොරිතමයක් ක්රියා කරන්නේ කෙසේද, එහිදී නෝඩයකින් ප්‍රතිචාරයක් සඳහා පොරොත්තු කාලය අත්තනෝමතික ලෙස දිගු විය හැකි බව අපි විශ්වාස කරමු (මාර්ගය වන විට, නෝඩයක අසාර්ථකත්වය ද උදාහරණයක් ලෙස සැලකිය හැකිය නෝඩයකට අත්තනෝමතික ලෙස දිගු කාලයක් ප්රතිචාර දැක්විය හැක ).
සම්මුති ඇල්ගොරිතම ප්‍රතිපත්තිමය වශයෙන් ක්රියා කරන ආකාරය දැන් අපි දනිමු, එය මෙතරම් දුරක් ගෙන ඇති ගවේෂණශීලී පාඨකයින්ට ප්‍රශ්නයක්: අසමමුහුර්ත පණිවිඩ ආකෘතියක් සහිත N නෝඩ් පද්ධතියක නෝඩ් කීයක් අසමත් විය හැකිද, එවිට පද්ධතියට තවමත් සම්මුතියකට ළඟා විය හැකිද?
නිවැරදි පිළිතුර සහ සාධාරණීකරණය spoiler පිටුපස ඇත.නිවැරදි පිළිතුර: 0. අසමමුහුර්ත පද්ධතියක එක් නෝඩයක් හෝ අසමත් වුවහොත්, පද්ධතියට සම්මුතියකට පැමිණීමට නොහැකි වනු ඇත. මෙම ප්‍රකාශය FLP ප්‍රමේයය තුළ ඔප්පු වී ඇත, සමහර කවයන් තුළ ප්‍රසිද්ධය (1985, ෆිෂර්, ලින්ච්, පැටර්සන්, ලිපියේ අවසානයේ මුල් පිටපතට සබැඳිය): “අවම වශයෙන් එක් නෝඩයක් අසමත් වුවහොත් බෙදා හරින ලද සම්මුතියක් සාක්ෂාත් කර ගැනීමේ නොහැකියාව .”
යාලුවනේ, එතකොට අපිට ප්‍රශ්නයක් තියෙනවා, අපි හැම දෙයක්ම අසමමුහුර්ත වීමට පුරුදු වී සිටිමු. මෙන්න එයයි. දිගටම ජීවත් වෙන්නේ කොහොමද?
අපි කතා කළේ න්‍යාය ගැන, ගණිතය ගැන විතරයි. "සම්මුතිය සාක්ෂාත් කරගත නොහැක" යන්නෙන් අදහස් කරන්නේ ගණිතමය භාෂාවෙන් අපගේ - ඉංජිනේරු විද්‍යාවට පරිවර්තනය කිරීම? මෙයින් අදහස් කරන්නේ "සෑම විටම සාක්ෂාත් කරගත නොහැකි" බවයි, i.e. සම්මුතියක් ඇති කර ගත නොහැකි අවස්ථාවක් තිබේ. මේක මොන වගේ කේස් එකක්ද?
මෙය හරියටම ඉහත විස්තර කර ඇති සජීවී දේපල උල්ලංඝනය කිරීමකි. අපට පොදු එකඟතාවයක් නොමැති අතර, සියලුම නෝඩ් වලින් ප්‍රතිචාරයක් නොමැති අවස්ථාවක පද්ධතියට ප්‍රගතියක් ලබා ගත නොහැක (සීමිත කාලයකින් සම්පූර්ණ කළ නොහැක). අසමමුහුර්ත පද්ධතියක අපට අනාවැකි කිව හැකි ප්රතිචාර කාලයක් නොමැති අතර node එකක් කඩා වැටී තිබේද නැතහොත් ප්රතිචාර දැක්වීමට බොහෝ කාලයක් ගතවේදැයි අපට දැනගත නොහැක.
නමුත් ප්රායෝගිකව අපට විසඳුමක් සොයාගත හැකිය. අපගේ ඇල්ගොරිතම අසාර්ථක වීම් වලදී දිගු කාලයක් වැඩ කිරීමට ඉඩ දෙන්න (විභවය එය දින නියමයක් නොමැතිව වැඩ කළ හැක). නමුත් බොහෝ අවස්ථාවන්හිදී, බොහෝ නෝඩ් නිවැරදිව ක්රියාත්මක වන විට, අපට පද්ධතියේ ප්‍රගතියක් ලැබෙනු ඇත.
ප්රායෝගිකව, අපි අර්ධ වශයෙන් සමමුහුර්ත සන්නිවේදන ආකෘති සමඟ කටයුතු කරමු. අර්ධ සමමුහුර්තකරණය පහත පරිදි වටහාගෙන ඇත: සාමාන්‍ය අවස්ථාවෙහිදී, අපට අසමමුහුර්ත ආකෘතියක් ඇත, නමුත් යම් කාල පරිච්ඡේදයක “ගෝලීය ස්ථායීකරණ කාලය” පිළිබඳ නිශ්චිත සංකල්පයක් විධිමත් ලෙස හඳුන්වා දෙනු ලැබේ.
මේ මොහොත කිසිඳු කාලයකට නොපැමිණෙන නමුත් එය යම් දිනක පැමිණිය යුතුය. අතථ්‍ය අනතුරු ඇඟවීමේ ඔරලෝසුව නාද වනු ඇත, එම මොහොතේ සිට අපට පණිවිඩ පැමිණෙන කාල ඩෙල්ටාව පුරෝකථනය කළ හැකිය. මේ මොහොතේ සිට, පද්ධතිය අසමමුහුර්ත සිට සමමුහුර්ත වෙත හැරේ. ප්රායෝගිකව, අපි හරියටම එවැනි පද්ධති සමඟ කටයුතු කරමු.
Paxos ඇල්ගොරිතම සම්මුති ගැටළු විසඳයි
සමහර නෝඩ් අසමත් වීමේ හැකියාවට යටත්ව, අර්ධ වශයෙන් සමමුහුර්ත පද්ධති සඳහා සම්මුති ගැටළුව විසඳන ඇල්ගොරිතම පවුලකි. Paxos හි කතුවරයා වේ . ඔහු 1989 දී ඇල්ගොරිතමයේ පැවැත්ම සහ නිවැරදි බව පිළිබඳ විධිමත් සාක්ෂියක් යෝජනා කළේය.
නමුත් සාක්ෂිය සුළුපටු නොවේ. ඇල්ගොරිතම විස්තර කරමින් පළමු ප්‍රකාශනය නිකුත් කරන ලද්දේ 1998 දී පමණි (පිටු 33). එය සිදු වූ පරිදි, එය තේරුම් ගැනීම අතිශයින් දුෂ්කර වූ අතර, 2001 දී ලිපිය පිළිබඳ පැහැදිලි කිරීමක් ප්‍රකාශයට පත් කරන ලද අතර එය පිටු 14 කින් සමන්විත විය. ප්‍රකාශන පරිමාව ලබා දී ඇත්තේ ඇත්ත වශයෙන්ම සම්මුතියේ ගැටලුව කිසිසේත් සරල නොවන බවත්, එවැනි ඇල්ගොරිතම පිටුපස බුද්ධිමත් පුද්ගලයින්ගේ විශාල වැඩ ප්‍රමාණයක් ඇති බවත් පෙන්වීම සඳහා ය.
දෙවන පැහැදිලි කිරීමේ ලිපියේ එක් ප්‍රකාශයක්, එක් පේළියක් (ඔහු කුමන එකක්ද යන්න සඳහන් කර නැත) විවිධ ආකාරවලින් අර්ථ දැක්විය හැකි බව ලෙස්ලි ලැම්පෝට් සිය දේශනයේදී සඳහන් කිරීම සිත්ගන්නා කරුණකි. මේ නිසා, නවීන Paxos ක්රියාත්මක කිරීම් විශාල සංඛ්යාවක් සම්පූර්ණයෙන්ම නිවැරදිව ක්රියා නොකරයි.
Paxos ගේ කාර්යය පිළිබඳ සවිස්තරාත්මක විශ්ලේෂණයක් එක් ලිපියකට වඩා ගත වනු ඇත, එබැවින් මම ඇල්ගොරිතමයේ ප්රධාන අදහස ඉතා කෙටියෙන් ඉදිරිපත් කිරීමට උත්සාහ කරමි. මගේ ලිපියේ අවසානයේ ඇති සබැඳි වලින් ඔබට මෙම මාතෘකාවට තවදුරටත් කිමිදීම සඳහා ද්‍රව්‍ය සොයාගත හැකිය.
Paxos හි භූමිකාවන්
Paxos ඇල්ගොරිතමයේ භූමිකාවන් පිළිබඳ සංකල්පය ඇත. අපි ප්රධාන තුනක් සලකා බලමු (අමතර භූමිකාවන් සහිත වෙනස් කිරීම් තිබේ):
- යෝජනා කරන්නන් (කොන්දේසි ද භාවිතා කළ හැක: නායකයින් හෝ සම්බන්ධීකාරක). මේ අය පරිශීලකයාගෙන් යම් නව වටිනාකමක් ගැන ඉගෙන ගෙන නායකයාගේ භූමිකාව භාර ගනී. ඔවුන්ගේ කර්තව්යය වන්නේ නව අගයක් සඳහා යෝජනා වටයක් දියත් කිරීම සහ නෝඩ් වල ඉදිරි ක්රියාවන් සම්බන්ධීකරණය කිරීමයි. එපමණක් නොව, ඇතැම් අවස්ථාවලදී නායකයින් කිහිප දෙනෙකුගේ පැමිණීම සඳහා Paxos ඉඩ ලබා දේ.
- පිළිගන්නන් (ඡන්දදායකයින්). මේවා යම් අගයක් පිළිගැනීමට හෝ ප්‍රතික්ෂේප කිරීමට ඡන්දය දෙන නෝඩ් වේ. ඔවුන්ගේ කාර්යභාරය ඉතා වැදගත් වේ, මන්ද තීරණය ඔවුන් මත රඳා පවතී: සම්මුති ඇල්ගොරිතමයේ ඊළඟ අදියරෙන් පසු පද්ධතිය (හෝ නොයනු ඇත) කුමන තත්වයට යන්නේද යන්නයි.
- ඉගෙන ගන්නන්. පද්ධතියේ තත්ත්වය වෙනස් වූ විට නව පිළිගත් අගය සරලව පිළිගෙන ලියන නෝඩ්. ඔවුන් තීරණ ගන්නේ නැත, ඔවුන් දත්ත ලබා ගන්නා අතර එය අවසාන පරිශීලකයාට ලබා දිය හැකිය.
එක් නෝඩයක් විවිධ අවස්ථාවන්හිදී භූමිකාවන් කිහිපයක් ඒකාබද්ධ කළ හැකිය.
ගණපූරණය පිළිබඳ සංකල්පය
අපි හිතමු අපිට ක්‍රමයක් තියෙනවා කියලා N නෝඩ් සහ ඔවුන්ගෙන් උපරිම F නෝඩ් අසමත් විය හැක. F නෝඩ් අසමත් වුවහොත්, අපට අවම වශයෙන් තිබිය යුතුය 2F+1 පිළිගැනීමේ නෝඩ්.
මෙය අවශ්ය වන අතර එමඟින් අපට සෑම විටම බහුතරයක්, නරකම තත්වයේදී පවා නිවැරදිව ක්රියා කරන “හොඳ” නෝඩ් තිබේ. එනම් F+1 එකඟ වූ "හොඳ" නෝඩ්, සහ අවසාන අගය පිළිගනු ලැබේ. නොඑසේ නම් අපේ විවිධ ප්‍රාදේශීය කණ්ඩායම් විවිධ අරුත් ගෙන එකිනෙකාට එකඟ විය නොහැකි තත්ත්වයක් ඇති විය හැකිය. ඒ නිසා අපිට ඡන්දය දිනන්න පරම බහුතරයක් අවශ්යයි.
Paxos සම්මුති ඇල්ගොරිතම ක්රියා කරන ආකාරය පිළිබඳ සාමාන්‍ය අදහස
Paxos ඇල්ගොරිතමයට විශාල අදියර දෙකක් ඇතුළත් වන අතර, ඒවා එක් එක් පියවර දෙකකට බෙදා ඇත:
- අදියර 1a: සූදානම් කරන්න. සූදානම් වීමේ අදියරේදී, නායකයා (යෝජකයා) සියලු නෝඩ් වෙත දැනුම් දෙයි: "අපි නව ඡන්ද අදියරක් ආරම්භ කරමු. අපිට අලුත් වටයක් තියෙනවා. මෙම වටයේ අංකය n වේ. දැන් අපි ඡන්දය දෙන්න පටන් ගමු." දැනට, එය හුදෙක් නව චක්‍රයක ආරම්භය වාර්තා කරයි, නමුත් නව අගයක් වාර්තා නොකරයි. මෙම අදියරෙහි කර්තව්යය වන්නේ නව වටයක් ආරම්භ කිරීම සහ එහි අද්විතීය අංකය සෑම කෙනෙකුටම දැනුම් දීමයි. වට අංකය වැදගත් වේ, එය පෙර සිටි සියලුම නායකයින්ගේ පෙර ඡන්ද අංකවලට වඩා වැඩි අගයක් විය යුතුය. මක්නිසාද යත්, නායකයාගේ දත්ත කෙතරම් මෑත කාලීන දැයි පද්ධතියේ අනෙකුත් නෝඩ් තේරුම් ගන්නා වට අංකයට ස්තූතිවන්ත වන බැවිනි. බොහෝ පසුකාලීන වට වලින් වෙනත් නෝඩ් දැනටමත් ඡන්ද ප්‍රතිඵල ලබා ඇති අතර නායකයාට ඔහු කාලය පිටුපස සිටින බව සරලව පවසනු ඇත.
- අදියර 1b: පොරොන්දුව. ග්‍රාහක නෝඩ්වලට නව ඡන්ද වේදිකාවේ අංකය ලැබුණු විට, ප්‍රතිඵල දෙකක් ලැබිය හැකිය:
- නව ඡන්දයේ n අංකය, පිළිගන්නා සහභාගි වූ ඕනෑම පෙර ඡන්ද සංඛ්‍යාවට වඩා වැඩිය. එවිට පිළිගන්නා නායකයාට පොරොන්දුවක් යවයි එය n ට වඩා අඩු සංඛ්යාවක් සහිත තවත් ඡන්දයකට සහභාගී නොවන බවට. ප්‍රතිග්‍රාහකයා දැනටමත් යම් දෙයකට ඡන්දය ප්‍රකාශ කර ඇත්නම් (එනම්, එය දැනටමත් දෙවන අදියරේදී යම් වටිනාකමක් පිළිගෙන තිබේ නම්), එය පිළිගත් වටිනාකම සහ ඔහු සහභාගී වූ ඡන්ද සංඛ්‍යාව එහි පොරොන්දුවට අමුණයි.
- එසේ නොමැති නම්, ඉහළ-සංඛ්‍යාත ඡන්දය ගැන පිළිගන්නා දැනටමත් දන්නේ නම්, එය සූදානම් කිරීමේ පියවර නොසලකා හැර නායකයාට ප්රතිචාර නොදැක්විය හැකිය.
- අදියර 2a: පිළිගන්න. නායකයාට ගණපූරණයෙන් (පද්ධතියේ ඇති නෝඩ් වලින් බහුතරයක්) ප්‍රතිචාරයක් එනතෙක් බලා සිටිය යුතු අතර, අවශ්ය ප්රතිචාර සංඛ්‍යාව ලැබෙන්නේ නම්, ඔහුට සිදුවීම් වර්ධනය සඳහා විකල්ප දෙකක් තිබේ:
- සමහර පිළිගන්නන් ඔවුන් දැනටමත් ඡන්දය දී ඇති අගයන් එවා ඇත. මෙම අවස්ථාවෙහිදී, නායකයා උපරිම අංකය සහිත ඡන්දයෙන් වටිනාකම තෝරා ගනී. අපි මෙම අගය x ලෙස හඳුන්වමු, එය සියලුම නෝඩ් වෙත පණිවිඩයක් යවයි: “පිළිගන්න (n, x)”, එහිදී පළමු අගය වන්නේ එහි යෝජිත පියවරෙන් ලැබෙන ඡන්ද අංකය වන අතර දෙවන අගය වන්නේ සියලු දෙනා රැස් වූ දෙයයි, i.e. අපි ඇත්තටම ඡන්දය දෙන වටිනාකම.
- පිළිගන්නා කිසිවෙක් කිසිදු වටිනාකමක් නොයවා, නමුත් ඔවුන් මෙම වටයේදී ඡන්දය දීමට පොරොන්දු වූවා නම්, නායකයාට ඔවුන්ගේ වටිනාකම සඳහා ඡන්දය දීමට ඔවුන්ට ආරාධනා කළ හැකිය, ඔහු මුලින්ම නායකයෙකු බවට පත් වූ වටිනාකම. අපි ඒකට y කියමු. එය පෙර ප්‍රතිඵලයට සමානව, “පිළිගන්න (n, y)” වැනි සියලුම නෝඩ් වෙත පණිවිඩයක් යවයි.
- අදියර 2b: පිළිගෙන ඇත. තවද, පිළිගන්නා නෝඩ්, නායකයාගෙන් “පිළිගන්න (...)” පණිවිඩය ලැබීමෙන් පසු, එයට එකඟ වේ (නව අගය සමඟ එකඟ වන බවට සියලුම නෝඩ් වෙත තහවුරු කිරීමක් යවන්න) ඔවුන් සමහරක් (වෙනත්) පොරොන්දු වී නොමැති නම් පමණි) වට අංකය සමඟ ඡන්දය සඳහා සහභාගී වීමට නායකයා n' > n, එසේ නොමැති නම් ඔවුන් තහවුරු කිරීමේ ඉල්ලීම නොසලකා හරිති.
නෝඩ් බහුතරයක් නායකයාට ප්රතිචාර දැක්වූයේ නම් සහ ඒවා සියල්ලම නව අගය තහවුරු කළේ නම්, නව අගය පිළිගත් ලෙස සලකනු ලැබේ. හුරේ! බහුතරයට ළඟා නොවන්නේ නම් හෝ නව අගය පිළිගැනීම ප්‍රතික්ෂේප කළ නෝඩ් තිබේ නම්, සියල්ල නැවත ආරම්භ වේ.
Paxos algorithm එක ක්රියා කරන්නේ මෙහෙමයි. මෙම සෑම අදියරකටම බොහෝ සියුම්කම් ඇත, අපි ප්රායෝගිකව විවිධ ආකාරයේ අසාර්ථකත්වයන්, බහු නායකයින්ගේ ගැටළු සහ තවත් බොහෝ දේ සලකා බැලුවේ නැත, නමුත් මෙම ලිපියේ පරමාර්ථය වන්නේ ඉහළ මට්ටමක බෙදා හරින ලද පරිගණක ලෝකයට පාඨකයාට හඳුන්වා දීම පමණි.
Paxos යනු මේ ආකාරයේ එකම එකක් නොවන බව සඳහන් කිරීම වටී, වෙනත් ඇල්ගොරිතම ඇත, උදාහරණයක් ලෙස, , නමුත් මෙය වෙනත් ලිපියක් සඳහා මාතෘකාවකි.
වැඩිදුර අධ්‍යයනය සඳහා ද්‍රව්‍ය වෙත සබැඳි
ආරම්භක මට්ටම:
- , Preethi Kasireddy, Blog article on Medium
- , Adi Kancherla, Blog article on Medium
- , Ittai Abraham, බ්ලොග්
- , Ittai Abraham, බ්ලොග් ලිපිය
ලෙස්ලි ලැම්පෝට් මට්ටම:
- , ෆිෂර්, ලින්ච් සහ පැටර්සන්, පර්යේෂණ පත්‍රිකාව, 1985
- , ලෙස්ලි ලැම්පෝට්, පර්යේෂණ පත්‍රිකාව, 1998
- , ලෙස්ලි ලැම්පෝට්, පර්යේෂණ පත්‍රිකාව, 2001
මූලාශ්රය: www.habr.com