ഒരു ബോക്സില്ലാത്ത ഷ്രോഡിംഗറുടെ പൂച്ച: വിതരണം ചെയ്ത സിസ്റ്റങ്ങളിലെ സമവായത്തിന്റെ പ്രശ്നം

അതിനാൽ, നമുക്ക് സങ്കൽപ്പിക്കാം. മുറിയിൽ 5 പൂച്ചകളെ പൂട്ടിയിട്ടിരിക്കുന്നു, ഉടമയെ ഉണർത്താൻ, എല്ലാവരും ഇത് പരസ്പരം സമ്മതിക്കേണ്ടതുണ്ട്, കാരണം അവയിൽ അഞ്ചെണ്ണം ചാരി മാത്രമേ അവർക്ക് വാതിൽ തുറക്കാൻ കഴിയൂ. പൂച്ചകളിൽ ഒന്ന് ഷ്രോഡിംഗറുടെ പൂച്ചയാണെങ്കിൽ, മറ്റ് പൂച്ചകൾക്ക് അവന്റെ തീരുമാനത്തെക്കുറിച്ച് അറിയില്ലെങ്കിൽ, ചോദ്യം ഉയർന്നുവരുന്നു: "അവർക്ക് അത് എങ്ങനെ ചെയ്യാൻ കഴിയും?"

ഈ ലേഖനത്തിൽ, വിതരണം ചെയ്ത സിസ്റ്റങ്ങളുടെ ലോകത്തിന്റെ സൈദ്ധാന്തിക ഘടകത്തെക്കുറിച്ചും അവയുടെ പ്രവർത്തനത്തിന്റെ തത്വങ്ങളെക്കുറിച്ചും ലളിതമായി ഞാൻ നിങ്ങളോട് പറയും. Paxos-ന്റെ അടിസ്ഥാന ആശയവും ഞാൻ ഉപരിപ്ലവമായി പരിശോധിക്കും.

ഡെവലപ്പർമാർ ക്ലൗഡ് ഇൻഫ്രാസ്ട്രക്ചറുകൾ, വിവിധ ഡാറ്റാബേസുകൾ എന്നിവ ഉപയോഗിക്കുകയും ധാരാളം നോഡുകളുടെ ക്ലസ്റ്ററുകളിൽ പ്രവർത്തിക്കുകയും ചെയ്യുമ്പോൾ, ഡാറ്റ പൂർണ്ണവും സുരക്ഷിതവും എല്ലായ്പ്പോഴും ലഭ്യവുമാകുമെന്ന് അവർക്ക് ഉറപ്പുണ്ട്. എന്നാൽ ഉറപ്പുകൾ എവിടെ?

അടിസ്ഥാനപരമായി, ഞങ്ങളുടെ പക്കലുള്ള ഗ്യാരണ്ടികൾ വിതരണക്കാരന്റെ ഗ്യാരന്റികളാണ്. അവ ഇനിപ്പറയുന്ന രീതിയിൽ ഡോക്യുമെന്റേഷനിൽ വിവരിച്ചിരിക്കുന്നു: "ഈ സേവനം തികച്ചും വിശ്വസനീയമാണ്, ഇതിന് നൽകിയിരിക്കുന്ന SLA ഉണ്ട്, വിഷമിക്കേണ്ട, നിങ്ങൾ പ്രതീക്ഷിക്കുന്നതുപോലെ എല്ലാം വിതരണം ചെയ്യും."

ഞങ്ങൾ മികച്ചതിൽ വിശ്വസിക്കുന്നു, കാരണം വലിയ കമ്പനികളിൽ നിന്നുള്ള മിടുക്കന്മാർ എല്ലാം ശരിയാകുമെന്ന് ഞങ്ങൾക്ക് ഉറപ്പുനൽകി. ഞങ്ങൾ ചോദ്യം ചോദിക്കുന്നില്ല: എന്തുകൊണ്ടാണ്, വാസ്തവത്തിൽ, ഇത് പ്രവർത്തിക്കാൻ കഴിയുക? അത്തരം സംവിധാനങ്ങളുടെ ശരിയായ പ്രവർത്തനത്തിന് എന്തെങ്കിലും ഔപചാരികമായ ന്യായീകരണമുണ്ടോ?

ഞാൻ അടുത്തിടെ പോയി സ്കൂൾ ഓഫ് ഡിസ്ട്രിബ്യൂട്ടഡ് കമ്പ്യൂട്ടിംഗ് ഈ വിഷയത്തിൽ നിന്ന് വളരെ പ്രചോദനം ഉൾക്കൊണ്ടിരുന്നു. സ്‌കൂളിലെ പ്രഭാഷണങ്ങൾ കമ്പ്യൂട്ടർ സംവിധാനങ്ങളുമായി ബന്ധപ്പെട്ടതിനേക്കാൾ കാൽക്കുലസ് ക്ലാസുകൾ പോലെയായിരുന്നു. എന്നാൽ നമ്മൾ അറിയാതെ തന്നെ ദിവസവും ഉപയോഗിക്കുന്ന ഏറ്റവും പ്രധാനപ്പെട്ട അൽഗരിതങ്ങൾ ഒരു കാലത്ത് തെളിയിക്കപ്പെട്ടത് ഇങ്ങനെയാണ്.

മിക്ക ആധുനിക വിതരണ സംവിധാനങ്ങളും Paxos കൺസെൻസസ് അൽഗോരിതവും അതിന്റെ വിവിധ പരിഷ്കാരങ്ങളും ഉപയോഗിക്കുന്നു. ഏറ്റവും രസകരമായ കാര്യം, സാധുതയും തത്വത്തിൽ, ഈ അൽഗോരിതം നിലനിൽക്കാനുള്ള സാധ്യതയും പേനയും പേപ്പറും ഉപയോഗിച്ച് തെളിയിക്കാനാകും. പ്രായോഗികമായി, മേഘങ്ങളിൽ ധാരാളം നോഡുകളിൽ പ്രവർത്തിക്കുന്ന വലിയ സിസ്റ്റങ്ങളിൽ അൽഗോരിതം ഉപയോഗിക്കുന്നു.

അടുത്തതായി ചർച്ച ചെയ്യപ്പെടുന്നതിന്റെ ഒരു ലഘുചിത്രം: രണ്ട് ജനറൽമാരുടെ ചുമതലഒരു സന്നാഹത്തിനായി നമുക്ക് നോക്കാം രണ്ട് ജനറൽമാരുടെ ചുമതല.

ഞങ്ങൾക്ക് രണ്ട് സൈന്യങ്ങളുണ്ട് - ചുവപ്പും വെള്ളയും. ഉപരോധിച്ച നഗരത്തിലാണ് വെള്ളക്കാരുടെ സേനയുടെ സ്ഥാനം. എ1, എ2 ജനറലുകളുടെ നേതൃത്വത്തിലുള്ള റെഡ് ട്രൂപ്പുകൾ നഗരത്തിന്റെ രണ്ട് വശങ്ങളിലായി സ്ഥിതി ചെയ്യുന്നു. വെളുത്ത നഗരത്തെ ആക്രമിച്ച് വിജയിക്കുക എന്നതാണ് റെഡ്ഹെഡുകളുടെ ചുമതല. എന്നിരുന്നാലും, ഓരോ റെഡ് ജനറലിന്റെയും സൈന്യം വ്യക്തിഗതമായി വെളുത്ത സൈന്യത്തേക്കാൾ ചെറുതാണ്.

ചുവപ്പുകാർക്കുള്ള വിജയ വ്യവസ്ഥകൾ: വെള്ളക്കാരെക്കാൾ സംഖ്യാപരമായ നേട്ടം ലഭിക്കുന്നതിന് രണ്ട് ജനറൽമാരും ഒരേ സമയം ആക്രമിക്കണം. ഇത് ചെയ്യുന്നതിന്, ജനറൽ A1 ഉം A2 ഉം പരസ്പരം ഒരു കരാറിൽ വരേണ്ടതുണ്ട്. എല്ലാവരും വെവ്വേറെ ആക്രമിച്ചാൽ, ചുവന്ന തലകൾ നഷ്ടപ്പെടും.

ഒരു കരാറിലെത്താൻ, ജനറൽമാരായ A1, A2 എന്നിവർക്ക് വെളുത്ത നഗരത്തിന്റെ പ്രദേശത്തിലൂടെ പരസ്പരം സന്ദേശവാഹകരെ അയയ്ക്കാൻ കഴിയും. ദൂതൻ ഒരു സഖ്യകക്ഷി ജനറലിലേക്ക് വിജയകരമായി എത്തിയേക്കാം അല്ലെങ്കിൽ ശത്രുവിനെ തടഞ്ഞേക്കാം. ചോദ്യം: ചുവന്ന മുടിയുള്ള ജനറലുകൾക്കിടയിൽ (A1-ൽ നിന്ന് A2-ലേയ്ക്കും തിരിച്ചും A2-ൽ നിന്ന് A1-ലേയ്ക്കും ദൂതന്മാരെ അയക്കുന്ന ക്രമം), X മണിക്കൂറിൽ അവർ ഒരു ആക്രമണത്തിന് സമ്മതിക്കുമെന്ന് ഉറപ്പുനൽകുന്ന അത്തരം ആശയവിനിമയങ്ങളുടെ ഒരു ശ്രേണി ഉണ്ടോ. ഇവിടെ, ഒരു സഖ്യകക്ഷി (മറ്റൊരു ജനറൽ) നിശ്ചിത സമയത്ത് X-ൽ ആക്രമണം നടത്തുമെന്ന് രണ്ട് ജനറൽമാർക്കും വ്യക്തമായ സ്ഥിരീകരണം ഉണ്ടായിരിക്കുമെന്നാണ് ഗ്യാരന്റികൾ അർത്ഥമാക്കുന്നത്.

“നമുക്ക് ഇന്ന് അർദ്ധരാത്രി ആക്രമിക്കാം!” എന്ന സന്ദേശവുമായി A1 ഒരു സന്ദേശവാഹകനെ A2-ലേക്ക് അയച്ചുവെന്ന് കരുതുക. ജനറൽ A1-ൽ നിന്നുള്ള സ്ഥിരീകരണമില്ലാതെ ജനറൽ A2-ന് ആക്രമിക്കാൻ കഴിയില്ല. A1-ൽ നിന്നുള്ള സന്ദേശവാഹകൻ എത്തിയിട്ടുണ്ടെങ്കിൽ, ജനറൽ A2, "അതെ, ഇന്ന് വെള്ളക്കാരെ കൊല്ലാം" എന്ന സന്ദേശത്തോടെ സ്ഥിരീകരണം അയയ്ക്കുന്നു. എന്നാൽ ഇപ്പോൾ ജനറൽ A2 ന് തന്റെ ദൂതൻ എത്തിയോ ഇല്ലയോ എന്ന് അറിയില്ല, ആക്രമണം ഒരേസമയം നടക്കുമോ എന്ന് അദ്ദേഹത്തിന് ഉറപ്പില്ല. ഇപ്പോൾ ജനറൽ A2 വീണ്ടും സ്ഥിരീകരണം ആവശ്യമാണ്.

അവരുടെ ആശയവിനിമയം ഞങ്ങൾ കൂടുതൽ വിവരിച്ചാൽ, എത്ര സന്ദേശ കൈമാറ്റ ചക്രങ്ങൾ ഉണ്ടായാലും, രണ്ട് ജനറൽമാർക്കും അവരുടെ സന്ദേശങ്ങൾ ലഭിച്ചുവെന്ന് ഉറപ്പ് നൽകാൻ ഒരു മാർഗവുമില്ലെന്ന് വ്യക്തമാകും (ഒന്നുകിൽ ദൂതനെ തടയാൻ കഴിയുമെന്ന് കരുതുക).

വിശ്വസനീയമല്ലാത്ത ആശയവിനിമയമുള്ള രണ്ട് നോഡുകളുള്ള വളരെ ലളിതമായ വിതരണ സംവിധാനത്തിന്റെ മികച്ച ചിത്രീകരണമാണ് ടു ജനറൽസ് പ്രശ്നം. ഇതിനർത്ഥം അവ സമന്വയിപ്പിച്ചിട്ടുണ്ടെന്ന് ഞങ്ങൾക്ക് 100% ഗ്യാരണ്ടി ഇല്ല എന്നാണ്. സമാനമായ പ്രശ്നങ്ങൾ പിന്നീട് ലേഖനത്തിൽ വലിയ അളവിൽ മാത്രമേ ചർച്ച ചെയ്യപ്പെടുകയുള്ളൂ.

വിതരണ സംവിധാനങ്ങൾ എന്ന ആശയം ഞങ്ങൾ അവതരിപ്പിക്കുന്നു

സന്ദേശങ്ങൾ കൈമാറാൻ കഴിയുന്ന ഒരു കൂട്ടം കമ്പ്യൂട്ടറുകളാണ് (ഇനിമുതൽ ഞങ്ങൾ അവയെ നോഡുകൾ എന്ന് വിളിക്കും) വിതരണം ചെയ്ത സിസ്റ്റം. ഓരോ വ്യക്തിഗത നോഡും ഒരുതരം സ്വയംഭരണ സ്ഥാപനമാണ്. ഒരു നോഡിന് സ്വന്തമായി ടാസ്‌ക്കുകൾ പ്രോസസ്സ് ചെയ്യാൻ കഴിയും, എന്നാൽ മറ്റ് നോഡുകളുമായി ആശയവിനിമയം നടത്തുന്നതിന്, സന്ദേശങ്ങൾ അയയ്‌ക്കേണ്ടതും സ്വീകരിക്കേണ്ടതും ആവശ്യമാണ്.

സന്ദേശങ്ങൾ എങ്ങനെയാണ് കൃത്യമായി നടപ്പിലാക്കുന്നത്, എന്ത് പ്രോട്ടോക്കോളുകളാണ് ഉപയോഗിക്കുന്നത് - ഈ സന്ദർഭത്തിൽ ഇത് ഞങ്ങൾക്ക് താൽപ്പര്യമുള്ള കാര്യമല്ല. ഒരു വിതരണം ചെയ്ത സിസ്റ്റത്തിന്റെ നോഡുകൾക്ക് സന്ദേശങ്ങൾ അയച്ചുകൊണ്ട് പരസ്പരം ഡാറ്റ കൈമാറാൻ കഴിയുന്നത് പ്രധാനമാണ്.

നിർവചനം തന്നെ വളരെ സങ്കീർണ്ണമായി തോന്നുന്നില്ല, എന്നാൽ ഒരു വിതരണം ചെയ്ത സിസ്റ്റത്തിന് നമുക്ക് പ്രധാനപ്പെട്ട നിരവധി ആട്രിബ്യൂട്ടുകൾ ഉണ്ടെന്ന് നാം കണക്കിലെടുക്കണം.

വിതരണം ചെയ്ത സിസ്റ്റങ്ങളുടെ ആട്രിബ്യൂട്ടുകൾ

1. Concurrency - സിസ്റ്റത്തിൽ ഒരേസമയം അല്ലെങ്കിൽ ഒരേസമയം സംഭവിക്കാനുള്ള സാധ്യത. മാത്രമല്ല, രണ്ട് വ്യത്യസ്ത നോഡുകളിൽ സംഭവിക്കുന്ന ഇവന്റുകൾ ഈ സംഭവങ്ങളുടെ വ്യക്തമായ ക്രമം ഇല്ലാത്തിടത്തോളം കാലം ഒരേസമയം സംഭവിക്കാൻ സാധ്യതയുള്ളതായി ഞങ്ങൾ പരിഗണിക്കും. പക്ഷേ, ഒരു ചട്ടം പോലെ, ഞങ്ങൾക്ക് അത് ഇല്ല.
2. ആഗോള ക്ലോക്ക് ഇല്ല. ഒരു ആഗോള ക്ലോക്കിന്റെ അഭാവം മൂലം നമുക്ക് സംഭവങ്ങളുടെ വ്യക്തമായ ക്രമം ഇല്ല. ആളുകളുടെ സാധാരണ ലോകത്ത്, നമുക്ക് ഘടികാരങ്ങളും സമയവും ഉണ്ട് എന്ന വസ്തുത നാം പരിചിതമാണ്. വിതരണ സംവിധാനങ്ങൾ വരുമ്പോൾ എല്ലാം മാറുന്നു. വളരെ കൃത്യമായ ആറ്റോമിക് ക്ലോക്കുകൾക്ക് പോലും ഡ്രിഫ്റ്റ് ഉണ്ട്, രണ്ട് സംഭവങ്ങളിൽ ഏതാണ് ആദ്യം സംഭവിച്ചതെന്ന് നമുക്ക് പറയാൻ കഴിയാത്ത സാഹചര്യങ്ങൾ ഉണ്ടാകാം. അതിനാൽ, നമുക്ക് സമയത്തെ ആശ്രയിക്കാൻ കഴിയില്ല.
3. സിസ്റ്റം നോഡുകളുടെ സ്വതന്ത്ര പരാജയം. മറ്റൊരു പ്രശ്നമുണ്ട്: നമ്മുടെ നോഡുകൾ ശാശ്വതമായി നിലനിൽക്കാത്തതിനാൽ എന്തെങ്കിലും തെറ്റ് സംഭവിക്കാം. ഹാർഡ് ഡ്രൈവ് പരാജയപ്പെടാം, ക്ലൗഡിലെ വെർച്വൽ മെഷീൻ റീബൂട്ട് ചെയ്യാം, നെറ്റ്‌വർക്ക് മിന്നുകയും സന്ദേശങ്ങൾ നഷ്ടപ്പെടുകയും ചെയ്യും. മാത്രമല്ല, നോഡുകൾ പ്രവർത്തിക്കുന്ന സാഹചര്യങ്ങൾ ഉണ്ടാകാം, എന്നാൽ അതേ സമയം സിസ്റ്റത്തിനെതിരെ പ്രവർത്തിക്കുന്നു. പ്രശ്‌നങ്ങളുടെ അവസാന ക്ലാസ്സിന് ഒരു പ്രത്യേക പേര് പോലും ലഭിച്ചു: പ്രശ്നം ബൈസന്റൈൻ ജനറൽമാർ. ഈ പ്രശ്നമുള്ള ഒരു വിതരണ സംവിധാനത്തിന്റെ ഏറ്റവും പ്രശസ്തമായ ഉദാഹരണം ബ്ലോക്ക്ചെയിൻ ആണ്. എന്നാൽ ഇന്ന് ഞങ്ങൾ ഈ പ്രത്യേക ക്ലാസ് പ്രശ്നങ്ങൾ പരിഗണിക്കില്ല. ഒന്നോ അതിലധികമോ നോഡുകൾ പരാജയപ്പെടാനിടയുള്ള സാഹചര്യങ്ങളിൽ ഞങ്ങൾക്ക് താൽപ്പര്യമുണ്ടാകും.
4. നോഡുകൾക്കിടയിലുള്ള ആശയവിനിമയ മോഡലുകൾ (മെസേജിംഗ് മോഡലുകൾ).. സന്ദേശങ്ങൾ കൈമാറുന്നതിലൂടെ നോഡുകൾ ആശയവിനിമയം നടത്തുന്നുവെന്ന് ഞങ്ങൾ ഇതിനകം സ്ഥാപിച്ചിട്ടുണ്ട്. രണ്ട് അറിയപ്പെടുന്ന സന്ദേശമയയ്‌ക്കൽ മോഡലുകളുണ്ട്: സിൻക്രണസ്, അസിൻക്രണസ്.

വിതരണം ചെയ്ത സിസ്റ്റങ്ങളിലെ നോഡുകൾ തമ്മിലുള്ള ആശയവിനിമയത്തിന്റെ മാതൃകകൾ

സിൻക്രണസ് മോഡൽ - ഒരു സന്ദേശം ഒരു നോഡിൽ നിന്ന് മറ്റൊന്നിലേക്ക് എത്തുമെന്ന് ഉറപ്പുനൽകുന്ന സമയത്തിന്റെ പരിമിതമായ ഒരു ഡെൽറ്റ ഉണ്ടെന്ന് ഞങ്ങൾക്ക് ഉറപ്പായും അറിയാം. ഈ സമയം കടന്ന് സന്ദേശം എത്തിയില്ലെങ്കിൽ, നോഡ് പരാജയപ്പെട്ടുവെന്ന് നമുക്ക് സുരക്ഷിതമായി പറയാൻ കഴിയും. ഈ മാതൃകയിൽ നമുക്ക് പ്രവചിക്കാവുന്ന കാത്തിരിപ്പ് സമയങ്ങളുണ്ട്.

അസിൻക്രണസ് മോഡൽ - അസിൻക്രണസ് മോഡലുകളിൽ, കാത്തിരിപ്പ് സമയം പരിമിതമാണെന്ന് ഞങ്ങൾ കരുതുന്നു, എന്നാൽ നോഡ് പരാജയപ്പെട്ടുവെന്ന് ഉറപ്പുനൽകാൻ കഴിയുന്ന അത്തരം സമയ ഡെൽറ്റ ഇല്ല. ആ. ഒരു നോഡിൽ നിന്നുള്ള സന്ദേശത്തിനായുള്ള കാത്തിരിപ്പ് സമയം ഏകപക്ഷീയമായി ദൈർഘ്യമേറിയതായിരിക്കും. ഇതൊരു പ്രധാന നിർവചനമാണ്, ഞങ്ങൾ അതിനെക്കുറിച്ച് കൂടുതൽ സംസാരിക്കും.

വിതരണ സംവിധാനങ്ങളിലെ സമവായം എന്ന ആശയം

സമവായം എന്ന ആശയം ഔപചാരികമായി നിർവചിക്കുന്നതിനുമുമ്പ്, നമുക്ക് അത് ആവശ്യമുള്ള ഒരു സാഹചര്യത്തിന്റെ ഒരു ഉദാഹരണം പരിഗണിക്കാം, അതായത് - സ്റ്റേറ്റ് മെഷീൻ റെപ്ലിക്കേഷൻ.

ഞങ്ങൾക്ക് വിതരണം ചെയ്ത ചില ലോഗ് ഉണ്ട്. വിതരണം ചെയ്ത സിസ്റ്റത്തിന്റെ എല്ലാ നോഡുകളിലും ഇത് സ്ഥിരതയുള്ളതും സമാനമായ ഡാറ്റ ഉൾക്കൊള്ളുന്നതും ഞങ്ങൾ ആഗ്രഹിക്കുന്നു. നോഡുകളിലൊന്ന് അത് ലോഗിലേക്ക് എഴുതാൻ പോകുന്ന ഒരു പുതിയ മൂല്യം മനസ്സിലാക്കുമ്പോൾ, അതിന്റെ ചുമതല മറ്റെല്ലാ നോഡുകളിലേക്കും ഈ മൂല്യം വാഗ്ദാനം ചെയ്യുന്നു, അങ്ങനെ ലോഗ് എല്ലാ നോഡുകളിലും അപ്‌ഡേറ്റ് ചെയ്യപ്പെടുകയും സിസ്റ്റം ഒരു പുതിയ സ്ഥിരതയുള്ള അവസ്ഥയിലേക്ക് നീങ്ങുകയും ചെയ്യുന്നു. ഈ സാഹചര്യത്തിൽ, നോഡുകൾ പരസ്പരം യോജിക്കുന്നത് പ്രധാനമാണ്: നിർദ്ദിഷ്ട പുതിയ മൂല്യം ശരിയാണെന്ന് എല്ലാ നോഡുകളും സമ്മതിക്കുന്നു, എല്ലാ നോഡുകളും ഈ മൂല്യം അംഗീകരിക്കുന്നു, ഈ സാഹചര്യത്തിൽ മാത്രമേ എല്ലാവർക്കും പുതിയ മൂല്യം ലോഗിൽ എഴുതാൻ കഴിയൂ.

മറ്റൊരു വിധത്തിൽ പറഞ്ഞാൽ: അതിൽ കൂടുതൽ പ്രസക്തമായ വിവരങ്ങൾ ഉണ്ടെന്ന് നോഡുകളൊന്നും എതിർത്തിട്ടില്ല, കൂടാതെ നിർദ്ദിഷ്ട മൂല്യം തെറ്റായിരുന്നു. നോഡുകൾ തമ്മിലുള്ള ഉടമ്പടിയും ഒരു ശരിയായ അംഗീകൃത മൂല്യത്തെക്കുറിച്ചുള്ള ഉടമ്പടിയും ഒരു വിതരണം ചെയ്ത സിസ്റ്റത്തിലെ സമവായമാണ്. അടുത്തതായി, ഒരു വിതരണ സംവിധാനത്തെ സമവായത്തിലെത്താൻ ഉറപ്പുനൽകാൻ അനുവദിക്കുന്ന അൽഗോരിതങ്ങളെക്കുറിച്ച് നമ്മൾ സംസാരിക്കും.

കൂടുതൽ ഔപചാരികമായി, ഒരു ഡിസ്ട്രിബ്യൂട്ടഡ് സിസ്റ്റത്തെ സ്റ്റേറ്റ് എയിൽ നിന്ന് ബിയിലേക്ക് മാറ്റുന്ന ഒരു നിശ്ചിത ഫംഗ്‌ഷനായി നമുക്ക് ഒരു കൺസെൻസസ് അൽഗോരിതം (അല്ലെങ്കിൽ ഒരു സമവായ അൽഗോരിതം) നിർവചിക്കാം. മാത്രമല്ല, ഈ അവസ്ഥ എല്ലാ നോഡുകളും അംഗീകരിക്കുന്നു, എല്ലാ നോഡുകൾക്കും ഇത് സ്ഥിരീകരിക്കാൻ കഴിയും. ഇത് മാറുന്നതുപോലെ, ഈ ചുമതല ഒറ്റനോട്ടത്തിൽ തോന്നുന്നത്ര നിസ്സാരമല്ല.

സമവായ അൽഗോരിതത്തിന്റെ സവിശേഷതകൾ

സിസ്റ്റം നിലനിൽക്കുന്നതിനും സംസ്ഥാനങ്ങളിൽ നിന്ന് സംസ്ഥാനങ്ങളിലേക്ക് നീങ്ങുന്നതിൽ കുറച്ച് പുരോഗതി നേടുന്നതിനും സമവായ അൽഗോരിതത്തിന് മൂന്ന് ഗുണങ്ങൾ ഉണ്ടായിരിക്കണം:

1. ഉടമ്പടി - ശരിയായി പ്രവർത്തിക്കുന്ന എല്ലാ നോഡുകളും ഒരേ മൂല്യം എടുക്കണം (ലേഖനങ്ങളിൽ ഈ പ്രോപ്പർട്ടി സുരക്ഷാ പ്രോപ്പർട്ടി എന്നും അറിയപ്പെടുന്നു). നിലവിൽ പ്രവർത്തിക്കുന്ന എല്ലാ നോഡുകളും (പരാജയപ്പെടുകയോ മറ്റുള്ളവരുമായുള്ള ബന്ധം നഷ്‌ടപ്പെടുകയോ ചെയ്‌തിട്ടില്ല) ഒരു കരാറിലെത്തി ചില അന്തിമ പൊതു മൂല്യം സ്വീകരിക്കണം.

   ഞങ്ങൾ പരിഗണിക്കുന്ന ഡിസ്ട്രിബ്യൂട്ടഡ് സിസ്റ്റത്തിലെ നോഡുകൾ അംഗീകരിക്കാൻ ആഗ്രഹിക്കുന്നുവെന്ന് ഇവിടെ മനസ്സിലാക്കേണ്ടത് പ്രധാനമാണ്. അതായത്, നമ്മൾ ഇപ്പോൾ സംസാരിക്കുന്നത് എന്തെങ്കിലും പരാജയപ്പെടാൻ കഴിയുന്ന സിസ്റ്റങ്ങളെക്കുറിച്ചാണ് (ഉദാഹരണത്തിന്, ചില നോഡുകൾ പരാജയപ്പെടുന്നു), എന്നാൽ ഈ സിസ്റ്റത്തിൽ തീർച്ചയായും മറ്റുള്ളവർക്കെതിരെ ബോധപൂർവ്വം പ്രവർത്തിക്കുന്ന നോഡുകളൊന്നുമില്ല (ബൈസന്റൈൻ ജനറലുകളുടെ ചുമതല). ഈ പ്രോപ്പർട്ടി കാരണം, സിസ്റ്റം സ്ഥിരമായി തുടരുന്നു.

2. നിർമലത - ശരിയായി പ്രവർത്തിക്കുന്ന എല്ലാ നോഡുകളും ഒരേ മൂല്യം വാഗ്ദാനം ചെയ്യുന്നുവെങ്കിൽ v, അതായത് ശരിയായി പ്രവർത്തിക്കുന്ന ഓരോ നോഡും ഈ മൂല്യം സ്വീകരിക്കണം v.
3. നിരാകരണം - ശരിയായി പ്രവർത്തിക്കുന്ന എല്ലാ നോഡുകളും ഒടുവിൽ ഒരു നിശ്ചിത മൂല്യം (ലൈവ്നെസ് പ്രോപ്പർട്ടി) എടുക്കും, ഇത് സിസ്റ്റത്തിൽ പുരോഗതി കൈവരിക്കാൻ അൽഗോരിതം അനുവദിക്കുന്നു. ഓരോ വ്യക്തിയും ശരിയായി പ്രവർത്തിക്കുന്ന നോഡും എത്രയും വേഗം അന്തിമ മൂല്യം സ്വീകരിക്കുകയും അത് സ്ഥിരീകരിക്കുകയും വേണം: "എനിക്ക്, ഈ മൂല്യം ശരിയാണ്, ഞാൻ മുഴുവൻ സിസ്റ്റത്തോടും യോജിക്കുന്നു."

സമവായ അൽഗോരിതം എങ്ങനെ പ്രവർത്തിക്കുന്നു എന്നതിന്റെ ഒരു ഉദാഹരണം

അൽഗോരിതത്തിന്റെ സവിശേഷതകൾ പൂർണ്ണമായും വ്യക്തമായിരിക്കണമെന്നില്ല. അതിനാൽ, ഒരു സിൻക്രണസ് സന്ദേശമയയ്‌ക്കൽ മോഡൽ ഉള്ള ഒരു സിസ്റ്റത്തിൽ ഏറ്റവും ലളിതമായ സമവായ അൽഗോരിതം ഏത് ഘട്ടങ്ങളിലൂടെയാണ് കടന്നുപോകുന്നതെന്ന് ഞങ്ങൾ ഒരു ഉദാഹരണത്തിലൂടെ വിശദീകരിക്കും, അതിൽ എല്ലാ നോഡുകളും പ്രതീക്ഷിച്ചതുപോലെ പ്രവർത്തിക്കുന്നു, സന്ദേശങ്ങൾ നഷ്‌ടപ്പെടില്ല, ഒന്നും തകരില്ല (ഇത് ശരിക്കും സംഭവിക്കുന്നുണ്ടോ?).

1. ഇതെല്ലാം ആരംഭിക്കുന്നത് ഒരു വിവാഹാലോചനയിൽ നിന്നാണ് (പ്രൊപ്പോസ്). "നോഡ് 1" എന്ന നോഡിലേക്ക് ഒരു ക്ലയന്റ് കണക്റ്റുചെയ്‌ത് ഒരു ഇടപാട് ആരംഭിച്ചു, നോഡിലേക്ക് ഒരു പുതിയ മൂല്യം കൈമാറുന്നുവെന്ന് നമുക്ക് അനുമാനിക്കാം - O. ഇനി മുതൽ, ഞങ്ങൾ "നോഡ് 1" എന്ന് വിളിക്കും. നിർദ്ദേശിക്കാൻ. ഒരു പ്രൊപ്പോസർ എന്ന നിലയിൽ, "നോഡ് 1" ഇപ്പോൾ പുതിയ ഡാറ്റയുണ്ടെന്ന് മുഴുവൻ സിസ്റ്റത്തെയും അറിയിക്കണം, കൂടാതെ ഇത് മറ്റെല്ലാ നോഡുകളിലേക്കും സന്ദേശങ്ങൾ അയയ്ക്കുന്നു: "നോക്കൂ! "O" എന്ന അർത്ഥം എനിക്ക് വന്നു, ഞാൻ അത് എഴുതാൻ ആഗ്രഹിക്കുന്നു! നിങ്ങളുടെ ലോഗിൽ "O" രേഖപ്പെടുത്തുമെന്ന് ദയവായി സ്ഥിരീകരിക്കുക."

   

2. അടുത്ത ഘട്ടം നിർദ്ദിഷ്ട മൂല്യത്തിനായുള്ള വോട്ടിംഗ് (വോട്ടിംഗ്) ആണ്. ഇതെന്തിനാണു? മറ്റ് നോഡുകൾക്ക് കൂടുതൽ സമീപകാല വിവരങ്ങൾ ലഭിച്ചിട്ടുണ്ടാകാം, അവയ്‌ക്ക് ഒരേ ഇടപാടിന്റെ ഡാറ്റയുണ്ട്.

   
   
   നോഡ് "നോഡ് 1" അതിന്റെ നിർദ്ദേശം അയയ്‌ക്കുമ്പോൾ, മറ്റ് നോഡുകൾ ഈ ഇവന്റിലെ ഡാറ്റയ്ക്കായി അവരുടെ ലോഗുകൾ പരിശോധിക്കുന്നു. വൈരുദ്ധ്യങ്ങളൊന്നുമില്ലെങ്കിൽ, നോഡുകൾ പ്രഖ്യാപിക്കുന്നു: “അതെ, ഈ ഇവന്റിനായി എനിക്ക് മറ്റ് ഡാറ്റകളൊന്നുമില്ല. "O" മൂല്യം ഞങ്ങൾ അർഹിക്കുന്ന ഏറ്റവും പുതിയ വിവരമാണ്."

   മറ്റേതെങ്കിലും സാഹചര്യത്തിൽ, നോഡുകൾക്ക് "നോഡ് 1" നോട് പ്രതികരിക്കാൻ കഴിയും: "കേൾക്കുക! ഈ ഇടപാടിനെക്കുറിച്ചുള്ള ഏറ്റവും പുതിയ ഡാറ്റ എന്റെ പക്കലുണ്ട്. 'ഓ' അല്ല, മറിച്ച് മെച്ചമായ ഒന്ന്."

   വോട്ടിംഗ് ഘട്ടത്തിൽ, നോഡുകൾ ഒരു തീരുമാനത്തിലെത്തുന്നു: ഒന്നുകിൽ അവയെല്ലാം ഒരേ മൂല്യം സ്വീകരിക്കുന്നു, അല്ലെങ്കിൽ അവരിൽ ഒരാൾ എതിർത്ത് വോട്ട് ചെയ്യുന്നു, ഇത് തന്റെ അടുത്തകാലത്തെ ഡാറ്റയുണ്ടെന്ന് സൂചിപ്പിക്കുന്നു.

3. വോട്ടിംഗ് റൗണ്ട് വിജയിക്കുകയും എല്ലാവരും അനുകൂലിക്കുകയും ചെയ്താൽ, സിസ്റ്റം ഒരു പുതിയ ഘട്ടത്തിലേക്ക് നീങ്ങുന്നു - മൂല്യം സ്വീകരിക്കുന്നു. "നോഡ് 1" മറ്റ് നോഡുകളിൽ നിന്നുള്ള എല്ലാ പ്രതികരണങ്ങളും റിപ്പോർട്ടുകളും ശേഖരിക്കുന്നു: "എല്ലാവരും "O" മൂല്യം അംഗീകരിച്ചു! "O" എന്നത് ഞങ്ങളുടെ പുതിയ അർത്ഥമാണെന്ന് ഇപ്പോൾ ഞാൻ ഔദ്യോഗികമായി പ്രഖ്യാപിക്കുന്നു, എല്ലാവർക്കും ഒരുപോലെയാണ്! നിങ്ങളുടെ ചെറിയ പുസ്തകത്തിൽ ഇത് എഴുതുക, മറക്കരുത്. അത് നിങ്ങളുടെ ലോഗിൽ എഴുതുക!

   

4. ശേഷിക്കുന്ന നോഡുകൾ "O" എന്ന മൂല്യം എഴുതിയിട്ടുണ്ടെന്ന് സ്ഥിരീകരണം (അംഗീകരിച്ചു) അയയ്ക്കുന്നു; ഈ സമയത്ത് പുതിയതായി ഒന്നും വന്നിട്ടില്ല (ഒരു തരം രണ്ട്-ഘട്ട പ്രതിബദ്ധത). ഈ സുപ്രധാന സംഭവത്തിന് ശേഷം, വിതരണം ചെയ്ത ഇടപാട് പൂർത്തിയായതായി ഞങ്ങൾ കരുതുന്നു.
   

അതിനാൽ, ഒരു ലളിതമായ കേസിൽ സമവായ അൽഗോരിതം നാല് ഘട്ടങ്ങൾ ഉൾക്കൊള്ളുന്നു: നിർദ്ദേശിക്കുക, വോട്ടുചെയ്യുക (വോട്ട് ചെയ്യുക), അംഗീകരിക്കുക (അംഗീകരിക്കുക), സ്വീകാര്യത സ്ഥിരീകരിക്കുക (അംഗീകരിച്ചു).

ചില ഘട്ടങ്ങളിൽ ഞങ്ങൾക്ക് കരാറിലെത്താൻ കഴിയുന്നില്ലെങ്കിൽ, നിർദ്ദിഷ്ട മൂല്യം സ്ഥിരീകരിക്കാൻ വിസമ്മതിച്ച നോഡുകൾ നൽകിയ വിവരങ്ങൾ കണക്കിലെടുത്ത് അൽഗോരിതം വീണ്ടും ആരംഭിക്കുന്നു.

ഒരു അസിൻക്രണസ് സിസ്റ്റത്തിലെ കൺസെൻസസ് അൽഗോരിതം

ഇതിന് മുമ്പ്, എല്ലാം സുഗമമായിരുന്നു, കാരണം ഞങ്ങൾ ഒരു സിൻക്രണസ് സന്ദേശമയയ്‌ക്കൽ മോഡലിനെക്കുറിച്ചാണ് സംസാരിക്കുന്നത്. എന്നാൽ ആധുനിക ലോകത്ത് നമ്മൾ എല്ലാം അസമന്വിതമായി ചെയ്യാറുണ്ടെന്ന് നമുക്കറിയാം. ഒരു അസിൻക്രണസ് സന്ദേശമയയ്‌ക്കൽ മോഡലുള്ള ഒരു സിസ്റ്റത്തിൽ സമാനമായ അൽഗോരിതം എങ്ങനെ പ്രവർത്തിക്കുന്നു, അവിടെ ഒരു നോഡിൽ നിന്നുള്ള പ്രതികരണത്തിനായുള്ള കാത്തിരിപ്പ് സമയം ഏകപക്ഷീയമായി ദൈർഘ്യമേറിയതായിരിക്കുമെന്ന് ഞങ്ങൾ വിശ്വസിക്കുന്നു (വഴി, ഒരു നോഡിന്റെ പരാജയവും ഒരു ഉദാഹരണമായി കണക്കാക്കാം. ഒരു നോഡിന് ഏകപക്ഷീയമായി വളരെക്കാലം പ്രതികരിക്കാൻ കഴിയും ).

സമവായ അൽഗോരിതം തത്വത്തിൽ എങ്ങനെ പ്രവർത്തിക്കുന്നുവെന്ന് ഇപ്പോൾ നമുക്കറിയാം, ഇത് ഇതുവരെ നേടിയ അന്വേഷണാത്മക വായനക്കാർക്കുള്ള ഒരു ചോദ്യം: ഒരു അസിൻക്രണസ് സന്ദേശ മോഡലുള്ള N നോഡുകളുടെ ഒരു സിസ്റ്റത്തിൽ എത്ര നോഡുകൾ പരാജയപ്പെടും, അങ്ങനെ സിസ്റ്റത്തിന് ഇപ്പോഴും സമവായത്തിലെത്താൻ കഴിയും?

ശരിയായ ഉത്തരവും ന്യായീകരണവുമാണ് സ്‌പോയിലറിന് പിന്നിലുള്ളത്.ശരിയായ ഉത്തരം: 0. ഒരു അസിൻക്രണസ് സിസ്റ്റത്തിലെ ഒരു നോഡ് പോലും പരാജയപ്പെടുകയാണെങ്കിൽ, സിസ്റ്റത്തിന് സമവായത്തിലെത്താൻ കഴിയില്ല. ഈ പ്രസ്താവന FLP സിദ്ധാന്തത്തിൽ തെളിയിക്കപ്പെട്ടതാണ്, ചില സർക്കിളുകളിൽ (1985, ഫിഷർ, ലിഞ്ച്, പാറ്റേഴ്സൺ, ലേഖനത്തിന്റെ അവസാനം ഒറിജിനലിലേക്കുള്ള ലിങ്ക്): "കുറഞ്ഞത് ഒരു നോഡെങ്കിലും പരാജയപ്പെടുകയാണെങ്കിൽ വിതരണം ചെയ്ത സമവായം കൈവരിക്കാനുള്ള അസാധ്യത. .”

സുഹൃത്തുക്കളേ, അപ്പോൾ ഞങ്ങൾക്ക് ഒരു പ്രശ്നമുണ്ട്, എല്ലാം അസമന്വിതമാണ്. അത് ഇതാ. എങ്ങനെ ജീവിക്കും?

ഞങ്ങൾ സിദ്ധാന്തത്തെക്കുറിച്ച്, ഗണിതത്തെക്കുറിച്ചാണ് സംസാരിച്ചത്. ഗണിതശാസ്ത്ര ഭാഷയിൽ നിന്ന് നമ്മുടേത് - എഞ്ചിനീയറിംഗ് എന്നതിലേക്ക് വിവർത്തനം ചെയ്യുന്നത് "സമവായം കൈവരിക്കാൻ കഴിയില്ല" എന്നതിന്റെ അർത്ഥമെന്താണ്? ഇതിനർത്ഥം "എല്ലായ്പ്പോഴും നേടിയെടുക്കാൻ കഴിയില്ല" എന്നാണ്, അതായത്. സമവായം സാധ്യമാകാത്ത സാഹചര്യമുണ്ട്. ഇത് എന്ത് തരത്തിലുള്ള കേസാണ്?

മുകളിൽ വിവരിച്ച ജീവനുള്ള വസ്തുവിന്റെ ലംഘനമാണിത്. ഞങ്ങൾക്ക് ഒരു പൊതു ഉടമ്പടി ഇല്ല, കൂടാതെ എല്ലാ നോഡുകളിൽ നിന്നും ഞങ്ങൾക്ക് പ്രതികരണം ലഭിക്കാത്ത സാഹചര്യത്തിൽ സിസ്റ്റത്തിന് പുരോഗതി കൈവരിക്കാൻ കഴിയില്ല (പരിമിതമായ സമയത്തിനുള്ളിൽ പൂർത്തിയാക്കാൻ കഴിയില്ല). കാരണം ഒരു അസിൻക്രണസ് സിസ്റ്റത്തിൽ നമുക്ക് പ്രവചിക്കാവുന്ന പ്രതികരണ സമയം ഇല്ല, കൂടാതെ ഒരു നോഡ് തകരാറിലാണോ അതോ പ്രതികരിക്കാൻ വളരെ സമയമെടുക്കുകയാണോ എന്ന് ഞങ്ങൾക്ക് അറിയാൻ കഴിയില്ല.

എന്നാൽ പ്രായോഗികമായി നമുക്ക് ഒരു പരിഹാരം കണ്ടെത്താൻ കഴിയും. പരാജയങ്ങളുടെ കാര്യത്തിൽ ഞങ്ങളുടെ അൽഗോരിതം വളരെക്കാലം പ്രവർത്തിക്കാൻ കഴിയട്ടെ (സാധ്യതയനുസരിച്ച് ഇത് അനിശ്ചിതമായി പ്രവർത്തിക്കാം). എന്നാൽ മിക്ക സാഹചര്യങ്ങളിലും, മിക്ക നോഡുകളും ശരിയായി പ്രവർത്തിക്കുമ്പോൾ, നമുക്ക് സിസ്റ്റത്തിൽ പുരോഗതി ഉണ്ടാകും.

പ്രായോഗികമായി, ഞങ്ങൾ ഭാഗികമായി സിൻക്രണസ് ആശയവിനിമയ മോഡലുകൾ കൈകാര്യം ചെയ്യുന്നു. ഭാഗിക സമന്വയം ഇനിപ്പറയുന്ന രീതിയിൽ മനസ്സിലാക്കുന്നു: പൊതുവായ സാഹചര്യത്തിൽ, ഞങ്ങൾക്ക് ഒരു അസിൻക്രണസ് മോഡൽ ഉണ്ട്, എന്നാൽ ഒരു നിശ്ചിത സമയത്തിന്റെ "ആഗോള സ്ഥിരത സമയം" എന്ന ഒരു പ്രത്യേക ആശയം ഔപചാരികമായി അവതരിപ്പിക്കപ്പെടുന്നു.

സമയത്തിന്റെ ഈ നിമിഷം ഒരു കാലയളവിനും വരണമെന്നില്ല, പക്ഷേ അത് ഒരു ദിവസം വരണം. വെർച്വൽ അലാറം ക്ലോക്ക് റിംഗ് ചെയ്യും, ആ നിമിഷം മുതൽ സന്ദേശങ്ങൾ എത്തുന്ന സമയ ഡെൽറ്റ നമുക്ക് പ്രവചിക്കാം. ഈ നിമിഷം മുതൽ, സിസ്റ്റം അസിൻക്രണസ് മുതൽ സിൻക്രണസ് വരെ മാറുന്നു. പ്രായോഗികമായി, അത്തരം സംവിധാനങ്ങൾ ഞങ്ങൾ കൃത്യമായി കൈകാര്യം ചെയ്യുന്നു.

Paxos അൽഗോരിതം സമവായ പ്രശ്നങ്ങൾ പരിഹരിക്കുന്നു

പാക്സോസ് ചില നോഡുകൾ പരാജയപ്പെടാനുള്ള സാധ്യതയ്ക്ക് വിധേയമായി, ഭാഗികമായി സിൻക്രണസ് സിസ്റ്റങ്ങൾക്കുള്ള സമവായ പ്രശ്നം പരിഹരിക്കുന്ന അൽഗോരിതങ്ങളുടെ ഒരു കുടുംബമാണ്. പാക്സോസിന്റെ രചയിതാവ് ലെസ്ലി ലാംപോർട്ട്. 1989-ൽ അൽഗോരിതത്തിന്റെ നിലനിൽപ്പിന്റെയും കൃത്യതയുടെയും ഔപചാരിക തെളിവ് അദ്ദേഹം നിർദ്ദേശിച്ചു.

എന്നാൽ തെളിവ് നിസ്സാരമല്ലെന്ന് തെളിഞ്ഞു. ആദ്യ പ്രസിദ്ധീകരണം 1998-ൽ (33 പേജുകൾ) അൽഗോരിതം വിവരിച്ചുകൊണ്ട് പുറത്തിറങ്ങി. ഇത് മനസ്സിലാക്കാൻ വളരെ ബുദ്ധിമുട്ടായിരുന്നു, 2001 ൽ ലേഖനത്തിന്റെ ഒരു വിശദീകരണം പ്രസിദ്ധീകരിച്ചു, അത് 14 പേജുകളെടുത്തു. വാസ്തവത്തിൽ സമവായത്തിന്റെ പ്രശ്നം ഒട്ടും ലളിതമല്ലെന്നും അത്തരം അൽഗോരിതങ്ങൾക്ക് പിന്നിൽ മിടുക്കരായ ആളുകളുടെ വലിയൊരു ജോലിയുണ്ടെന്നും കാണിക്കുന്നതിനാണ് പ്രസിദ്ധീകരണങ്ങളുടെ അളവ് നൽകിയിരിക്കുന്നത്.

ലെസ്ലി ലാംപോർട്ട് തന്നെ തന്റെ പ്രഭാഷണത്തിൽ രണ്ടാമത്തെ വിശദീകരണ ലേഖനത്തിൽ ഒരു പ്രസ്താവനയുണ്ട്, ഒരു വരി (ഏത് എന്ന് അദ്ദേഹം വ്യക്തമാക്കിയിട്ടില്ല), അത് വ്യത്യസ്ത രീതികളിൽ വ്യാഖ്യാനിക്കാം. ഇക്കാരണത്താൽ, ധാരാളം ആധുനിക പാക്സോസ് നടപ്പിലാക്കലുകൾ പൂർണ്ണമായും ശരിയായി പ്രവർത്തിക്കുന്നില്ല.

പാക്സോസിന്റെ സൃഷ്ടിയുടെ വിശദമായ വിശകലനത്തിന് ഒന്നിൽ കൂടുതൽ ലേഖനങ്ങൾ വേണ്ടിവരും, അതിനാൽ അൽഗോരിതത്തിന്റെ പ്രധാന ആശയം വളരെ ചുരുക്കമായി അറിയിക്കാൻ ഞാൻ ശ്രമിക്കും. എന്റെ ലേഖനത്തിന്റെ അവസാനത്തെ ലിങ്കുകളിൽ ഈ വിഷയത്തിലേക്ക് കൂടുതൽ ഡൈവിംഗ് ചെയ്യുന്നതിനുള്ള മെറ്റീരിയലുകൾ നിങ്ങൾ കണ്ടെത്തും.

പാക്സോസിലെ വേഷങ്ങൾ

Paxos അൽഗോരിതത്തിന് റോളുകളുടെ ഒരു ആശയമുണ്ട്. നമുക്ക് മൂന്ന് പ്രധാന കാര്യങ്ങൾ പരിഗണിക്കാം (അധിക റോളുകളുള്ള പരിഷ്കാരങ്ങളുണ്ട്):

1. പ്രൊപ്പോസർമാർ (നിബന്ധനകളും ഉപയോഗിക്കാം: നേതാക്കൾ അല്ലെങ്കിൽ കോർഡിനേറ്റർമാർ). ഉപയോക്താവിൽ നിന്ന് ചില പുതിയ മൂല്യങ്ങളെക്കുറിച്ച് പഠിക്കുകയും നേതാവിന്റെ റോൾ ഏറ്റെടുക്കുകയും ചെയ്യുന്നവരാണ് ഇക്കൂട്ടർ. ഒരു പുതിയ മൂല്യത്തിനായുള്ള നിർദ്ദേശങ്ങളുടെ ഒരു റൗണ്ട് സമാരംഭിക്കുകയും നോഡുകളുടെ തുടർ പ്രവർത്തനങ്ങൾ ഏകോപിപ്പിക്കുകയും ചെയ്യുക എന്നതാണ് അവരുടെ ചുമതല. കൂടാതെ, ചില സാഹചര്യങ്ങളിൽ നിരവധി നേതാക്കളുടെ സാന്നിധ്യം Paxos അനുവദിക്കുന്നു.
2. സ്വീകരിക്കുന്നവർ (വോട്ടർമാർ). ഒരു പ്രത്യേക മൂല്യം സ്വീകരിക്കുന്നതിനോ നിരസിക്കുന്നതിനോ വോട്ട് ചെയ്യുന്ന നോഡുകളാണിവ. അവരുടെ പങ്ക് വളരെ പ്രധാനമാണ്, കാരണം തീരുമാനം അവരെ ആശ്രയിച്ചിരിക്കുന്നു: സമവായ അൽഗോരിതത്തിന്റെ അടുത്ത ഘട്ടത്തിന് ശേഷം സിസ്റ്റം ഏത് അവസ്ഥയിലേക്ക് പോകും (അല്ലെങ്കിൽ പോകില്ല).
3. പഠിതാക്കൾ. സിസ്റ്റത്തിന്റെ അവസ്ഥ മാറുമ്പോൾ പുതിയ അംഗീകൃത മൂല്യം സ്വീകരിക്കുകയും എഴുതുകയും ചെയ്യുന്ന നോഡുകൾ. അവർ തീരുമാനങ്ങൾ എടുക്കുന്നില്ല, അവർ ഡാറ്റ സ്വീകരിക്കുകയും അന്തിമ ഉപയോക്താവിന് അത് നൽകുകയും ചെയ്യുന്നു.

ഒരു നോഡിന് വ്യത്യസ്ത സാഹചര്യങ്ങളിൽ നിരവധി റോളുകൾ സംയോജിപ്പിക്കാൻ കഴിയും.

കോറം എന്ന ആശയം

ഞങ്ങൾക്ക് ഒരു സംവിധാനം ഉണ്ടെന്ന് ഞങ്ങൾ അനുമാനിക്കുന്നു N നോഡുകൾ അവരിൽ പരമാവധി F നോഡുകൾ പരാജയപ്പെടാം. എഫ് നോഡുകൾ പരാജയപ്പെടുകയാണെങ്കിൽ, നമുക്ക് കുറഞ്ഞത് ഉണ്ടായിരിക്കണം 2F+1 സ്വീകരിക്കുന്ന നോഡുകൾ.

ഇത് ആവശ്യമാണ്, അതിനാൽ ഏറ്റവും മോശം സാഹചര്യത്തിൽ പോലും ശരിയായി പ്രവർത്തിക്കുന്ന "നല്ല" നോഡുകളുടെ ഭൂരിപക്ഷം ഞങ്ങൾക്ക് എല്ലായ്പ്പോഴും ഉണ്ടായിരിക്കും. അതാണ് എഫ് + 1 സമ്മതിച്ച "നല്ല" നോഡുകൾ, അന്തിമ മൂല്യം സ്വീകരിക്കപ്പെടും. അല്ലാത്തപക്ഷം, നമ്മുടെ വിവിധ പ്രാദേശിക ഗ്രൂപ്പുകൾ വ്യത്യസ്ത അർത്ഥങ്ങൾ സ്വീകരിക്കുകയും പരസ്പരം യോജിക്കാൻ കഴിയാത്ത സാഹചര്യം ഉണ്ടാകാം. അതുകൊണ്ട് തന്നെ വോട്ട് നേടണമെങ്കിൽ കേവല ഭൂരിപക്ഷം വേണം.

പാക്സോസ് സമവായ അൽഗോരിതം എങ്ങനെ പ്രവർത്തിക്കുന്നു എന്നതിനെക്കുറിച്ചുള്ള പൊതുവായ ആശയം

പാക്സോസ് അൽഗോരിതം രണ്ട് വലിയ ഘട്ടങ്ങൾ ഉൾക്കൊള്ളുന്നു, അവ ഓരോന്നും രണ്ട് ഘട്ടങ്ങളായി തിരിച്ചിരിക്കുന്നു:

1. ഘട്ടം 1 എ: തയ്യാറാക്കുക. തയ്യാറെടുപ്പ് ഘട്ടത്തിൽ, നേതാവ് (നിർദ്ദേശകൻ) എല്ലാ നോഡുകളേയും അറിയിക്കുന്നു: “ഞങ്ങൾ ഒരു പുതിയ വോട്ടിംഗ് ഘട്ടം ആരംഭിക്കുകയാണ്. ഞങ്ങൾക്ക് ഒരു പുതിയ റൗണ്ട് ഉണ്ട്. ഈ റൗണ്ടിന്റെ എണ്ണം n ആണ്. ഇനി നമ്മൾ വോട്ട് ചെയ്യാൻ തുടങ്ങും." ഇപ്പോൾ, ഇത് ഒരു പുതിയ സൈക്കിളിന്റെ ആരംഭം റിപ്പോർട്ട് ചെയ്യുന്നു, പക്ഷേ ഒരു പുതിയ മൂല്യം റിപ്പോർട്ട് ചെയ്യുന്നില്ല. ഈ ഘട്ടത്തിന്റെ ചുമതല ഒരു പുതിയ റൗണ്ട് ആരംഭിക്കുകയും അതിന്റെ അദ്വിതീയ നമ്പർ എല്ലാവരേയും അറിയിക്കുകയും ചെയ്യുക എന്നതാണ്. റൗണ്ട് നമ്പർ പ്രധാനമാണ്, അത് മുൻ നേതാക്കളിൽ നിന്നുള്ള എല്ലാ വോട്ടിംഗ് നമ്പറുകളേക്കാളും വലിയ മൂല്യമായിരിക്കണം. കാരണം, വൃത്താകൃതിയിലുള്ള നമ്പറിന് നന്ദി, സിസ്റ്റത്തിലെ മറ്റ് നോഡുകൾ ലീഡറുടെ ഡാറ്റ എത്രത്തോളം സമീപകാലമാണെന്ന് മനസ്സിലാക്കും. മറ്റ് നോഡുകൾക്ക് പിന്നീടുള്ള റൗണ്ടുകളിൽ നിന്ന് ഇതിനകം തന്നെ വോട്ടിംഗ് ഫലങ്ങൾ ഉണ്ടായിരിക്കാനും നേതാവിനോട് താൻ സമയത്തിന് പിന്നിലാണെന്ന് ലളിതമായി പറയാനും സാധ്യതയുണ്ട്.
2. ഘട്ടം 1 ബി: വാഗ്ദാനം. പുതിയ വോട്ടിംഗ് ഘട്ടത്തിന്റെ എണ്ണം സ്വീകരിക്കുന്ന നോഡുകൾക്ക് ലഭിക്കുമ്പോൾ, രണ്ട് ഫലങ്ങൾ സാധ്യമാണ്:
   • പുതിയ വോട്ടിന്റെ നമ്പർ n എന്നത് സ്വീകരിക്കുന്നയാൾ പങ്കെടുത്ത മുൻ വോട്ടിന്റെ എണ്ണത്തേക്കാൾ കൂടുതലാണ്. അപ്പോൾ സ്വീകരിക്കുന്നയാൾ നേതാവിന് n-നേക്കാൾ കുറഞ്ഞ സംഖ്യയുള്ള ഒരു വോട്ടിലും പങ്കെടുക്കില്ലെന്ന് ഒരു വാഗ്ദാനം അയയ്ക്കുന്നു. സ്വീകരിക്കുന്നയാൾ ഇതിനകം എന്തെങ്കിലും വോട്ട് ചെയ്‌തിട്ടുണ്ടെങ്കിൽ (അതായത്, അത് രണ്ടാം ഘട്ടത്തിൽ ഇതിനകം കുറച്ച് മൂല്യം സ്വീകരിച്ചിട്ടുണ്ട്), അത് അംഗീകരിച്ച മൂല്യവും അതിൽ പങ്കെടുത്ത വോട്ടിന്റെ എണ്ണവും അതിന്റെ വാഗ്ദാനവുമായി ബന്ധിപ്പിക്കുന്നു.
   • അല്ലാത്തപക്ഷം, ഉയർന്ന സംഖ്യയുള്ള വോട്ടിനെക്കുറിച്ച് സ്വീകരിക്കുന്നയാൾക്ക് ഇതിനകം അറിയാമെങ്കിൽ, അത് തയ്യാറാക്കുന്ന ഘട്ടം അവഗണിക്കുകയും നേതാവിനോട് പ്രതികരിക്കാതിരിക്കുകയും ചെയ്യാം.
3. ഘട്ടം 2a: അംഗീകരിക്കുക. കോറത്തിൽ നിന്നുള്ള പ്രതികരണത്തിനായി നേതാവ് കാത്തിരിക്കേണ്ടതുണ്ട് (സിസ്റ്റത്തിലെ ഭൂരിഭാഗം നോഡുകളും) കൂടാതെ, ആവശ്യമായ എണ്ണം പ്രതികരണങ്ങൾ ലഭിച്ചാൽ, ഇവന്റുകൾ വികസിപ്പിക്കുന്നതിന് അദ്ദേഹത്തിന് രണ്ട് ഓപ്ഷനുകൾ ഉണ്ട്:
   • സ്വീകരിക്കുന്നവരിൽ ചിലർ അവർ ഇതിനകം വോട്ട് ചെയ്ത മൂല്യങ്ങൾ അയച്ചു. ഈ സാഹചര്യത്തിൽ, നേതാവ് പരമാവധി സംഖ്യയുള്ള വോട്ടിൽ നിന്ന് മൂല്യം തിരഞ്ഞെടുക്കുന്നു. നമുക്ക് ഈ മൂല്യത്തെ x എന്ന് വിളിക്കാം, കൂടാതെ ഇത് എല്ലാ നോഡുകളിലേക്കും ഇത് പോലെയുള്ള ഒരു സന്ദേശം അയയ്‌ക്കുന്നു: “അംഗീകരിക്കുക (n, x)”, അവിടെ ആദ്യ മൂല്യം സ്വന്തം പ്രൊപ്പോസ് സ്റ്റെപ്പിൽ നിന്നുള്ള വോട്ടിംഗ് നമ്പറാണ്, രണ്ടാമത്തെ മൂല്യം എല്ലാവരും ഒത്തുകൂടി, അതായത് നമ്മൾ യഥാർത്ഥത്തിൽ വോട്ട് ചെയ്യുന്ന മൂല്യം.
   • സ്വീകരിക്കുന്നവരിൽ ആരും മൂല്യങ്ങളൊന്നും അയച്ചില്ലെങ്കിലും, ഈ റൗണ്ടിൽ വോട്ട് ചെയ്യാമെന്ന് അവർ വാഗ്ദാനം ചെയ്താൽ, നേതാവിന് അവരുടെ മൂല്യത്തിന് വോട്ടുചെയ്യാൻ അവരെ ക്ഷണിക്കാൻ കഴിയും, അവൻ ആദ്യം ഒരു നേതാവായി മാറിയ മൂല്യം. നമുക്ക് അതിനെ y എന്ന് വിളിക്കാം. എല്ലാ നോഡുകളിലേക്കും ഇത് ഒരു സന്ദേശം അയയ്ക്കുന്നു: "അംഗീകരിക്കുക (n, y)", മുമ്പത്തെ ഫലത്തിന് സമാനമായി.
4. ഘട്ടം 2b: അംഗീകരിച്ചു. കൂടാതെ, ലീഡറിൽ നിന്ന് "അംഗീകരിക്കുക(...)" സന്ദേശം ലഭിക്കുമ്പോൾ, സ്വീകരിക്കുന്ന നോഡുകൾ അത് അംഗീകരിക്കുന്നു (പുതിയ മൂല്യത്തോട് അവർ യോജിക്കുന്നുവെന്ന് എല്ലാ നോഡുകളിലേക്കും സ്ഥിരീകരണം അയയ്ക്കുക) അവർ ചിലത് (മറ്റുള്ളവ) വാഗ്ദാനം ചെയ്തിട്ടില്ലെങ്കിൽ മാത്രം ) റൗണ്ട് നമ്പർ ഉപയോഗിച്ച് വോട്ടിംഗിൽ പങ്കെടുക്കാൻ നേതാവ് n' > n, അല്ലെങ്കിൽ അവർ സ്ഥിരീകരണ അഭ്യർത്ഥന അവഗണിക്കുന്നു.

   ഭൂരിഭാഗം നോഡുകളും ലീഡറോട് പ്രതികരിക്കുകയും അവയെല്ലാം പുതിയ മൂല്യം സ്ഥിരീകരിക്കുകയും ചെയ്താൽ, പുതിയ മൂല്യം അംഗീകരിച്ചതായി കണക്കാക്കുന്നു. ഹൂറേ! ഭൂരിപക്ഷം എത്തിയില്ലെങ്കിലോ പുതിയ മൂല്യം സ്വീകരിക്കാൻ വിസമ്മതിച്ച നോഡുകൾ ഉണ്ടെങ്കിലോ, എല്ലാം ആരംഭിക്കുന്നു.

ഇങ്ങനെയാണ് പാക്സോസ് അൽഗോരിതം പ്രവർത്തിക്കുന്നത്. ഈ ഘട്ടങ്ങളിൽ ഓരോന്നിനും നിരവധി സൂക്ഷ്മതകളുണ്ട്, വിവിധ തരത്തിലുള്ള പരാജയങ്ങൾ, ഒന്നിലധികം നേതാക്കളുടെ പ്രശ്നങ്ങൾ എന്നിവയും അതിലേറെയും ഞങ്ങൾ പ്രായോഗികമായി പരിഗണിച്ചില്ല, എന്നാൽ ഈ ലേഖനത്തിന്റെ ലക്ഷ്യം വായനക്കാരനെ ഉയർന്ന തലത്തിൽ വിതരണം ചെയ്യുന്ന കമ്പ്യൂട്ടിംഗിന്റെ ലോകത്തേക്ക് പരിചയപ്പെടുത്തുക എന്നതാണ്.

പാക്സോസ് ഇത്തരത്തിലുള്ള ഒന്നല്ല എന്നതും ശ്രദ്ധിക്കേണ്ടതാണ്, മറ്റ് അൽഗോരിതങ്ങൾ ഉണ്ട്, ഉദാഹരണത്തിന്, തുഴയൽ, എന്നാൽ ഇത് മറ്റൊരു ലേഖനത്തിനുള്ള വിഷയമാണ്.

കൂടുതൽ പഠനത്തിനുള്ള മെറ്റീരിയലുകളിലേക്കുള്ള ലിങ്കുകൾ

തുടക്കക്കാരന്റെ നില:

• വിതരണം ചെയ്ത സമവായം എങ്ങനെയാണ് പ്രവർത്തിക്കുന്നത്?, പ്രീതി കാസിറെഡ്ഡി, മീഡിയത്തെക്കുറിച്ചുള്ള ബ്ലോഗ് ലേഖനം
• Paxos ലളിതമാക്കി. യഥാർത്ഥമായതിനായി, ആദി കാഞ്ചർള, മീഡിയത്തെക്കുറിച്ചുള്ള ബ്ലോഗ് ലേഖനം
• വികേന്ദ്രീകൃത ചിന്തകൾ, ഇട്ടായി എബ്രഹാം, ബ്ലോഗ്
• സമന്വയം, അസിൻക്രണി, ഭാഗിക സമന്വയം, ഇട്ടായി എബ്രഹാം, ബ്ലോഗ് ലേഖനം

ലെസ്ലി ലാംപോർട്ട് ലെവൽ:

• ഒരു തെറ്റായ പ്രക്രിയ ഉപയോഗിച്ച് വിതരണം ചെയ്ത സമവായത്തിന്റെ അസാധ്യത (FLP അസാധ്യം), ഫിഷർ, ലിഞ്ച് ആൻഡ് പാറ്റേഴ്സൺ, ഗവേഷണ പ്രബന്ധം, 1985
• പാർട്ട് ടൈം പാർലമെന്റ്, ലെസ്ലി ലാംപോർട്ട്, ഗവേഷണ പ്രബന്ധം, 1998
• Paxos ലളിതമാക്കി, ലെസ്ലി ലാംപോർട്ട്, ഗവേഷണ പ്രബന്ധം, 2001

അവലംബം: www.habr.com