બોક્સ વિના શ્રોડિંગરની બિલાડી: વિતરિત સિસ્ટમોમાં સર્વસંમતિની સમસ્યા

તેથી, ચાલો કલ્પના કરીએ. રૂમમાં 5 બિલાડીઓ બંધ છે, અને માલિકને જગાડવા માટે, તેઓ બધાએ આ અંગે સંમત થવું જરૂરી છે, કારણ કે તેઓ ફક્ત તેમાંથી પાંચ જ તેના પર ઝૂકીને દરવાજો ખોલી શકે છે. જો બિલાડીઓમાંની એક શ્રોડિંગરની બિલાડી છે, અને અન્ય બિલાડીઓ તેના નિર્ણય વિશે જાણતી નથી, તો પ્રશ્ન ઊભો થાય છે: "તેઓ તે કેવી રીતે કરી શકે?"

આ લેખમાં, હું તમને વિતરિત પ્રણાલીઓની દુનિયાના સૈદ્ધાંતિક ઘટક અને તેમની કામગીરીના સિદ્ધાંતો વિશે સરળ શબ્દોમાં કહીશ. હું Paxos અંતર્ગત મુખ્ય વિચારને પણ સુપરફિસિયલ રીતે તપાસીશ.

જ્યારે ડેવલપર્સ ક્લાઉડ ઈન્ફ્રાસ્ટ્રક્ચર્સ, વિવિધ ડેટાબેઝનો ઉપયોગ કરે છે અને મોટી સંખ્યામાં નોડ્સના ક્લસ્ટરમાં કામ કરે છે, ત્યારે તેમને વિશ્વાસ હોય છે કે ડેટા સંપૂર્ણ, સુરક્ષિત અને હંમેશા ઉપલબ્ધ રહેશે. પરંતુ ગેરંટી ક્યાં છે?

આવશ્યકપણે, અમારી પાસે જે બાંયધરી છે તે સપ્લાયર ગેરંટી છે. તેઓનું વર્ણન દસ્તાવેજીકરણમાં આ રીતે કરવામાં આવ્યું છે: "આ સેવા તદ્દન વિશ્વસનીય છે, તેમાં આપેલ SLA છે, ચિંતા કરશો નહીં, તમારી અપેક્ષા મુજબ બધું વિતરિત રીતે કાર્ય કરશે."

અમે શ્રેષ્ઠમાં વિશ્વાસ કરીએ છીએ, કારણ કે મોટી કંપનીઓના સ્માર્ટ લોકોએ અમને ખાતરી આપી હતી કે બધું સારું થઈ જશે. અમે પ્રશ્ન પૂછતા નથી: શા માટે, હકીકતમાં, આ બિલકુલ કામ કરી શકે છે? શું આવી સિસ્ટમોના યોગ્ય સંચાલન માટે કોઈ ઔપચારિક સમર્થન છે?

હું તાજેતરમાં ગયો હતો વિતરિત કોમ્પ્યુટીંગ શાળા અને આ વિષયથી ખૂબ જ પ્રેરિત હતા. શાળામાં પ્રવચનો કોમ્પ્યુટર સિસ્ટમ્સ સાથે સંબંધિત કંઈક કરતાં કેલ્ક્યુલસ વર્ગો જેવા હતા. પરંતુ આ જ રીતે સૌથી મહત્વપૂર્ણ અલ્ગોરિધમ્સ જેનો આપણે દરરોજ ઉપયોગ કરીએ છીએ, તે જાણ્યા વિના પણ, એક સમયે સાબિત થયા હતા.

મોટાભાગની આધુનિક વિતરિત પ્રણાલીઓ Paxos સર્વસંમતિ અલ્ગોરિધમનો અને તેના વિવિધ ફેરફારોનો ઉપયોગ કરે છે. સૌથી સરસ બાબત એ છે કે માન્યતા અને, સૈદ્ધાંતિક રીતે, આ અલ્ગોરિધમના અસ્તિત્વની સંભાવનાને ફક્ત પેન અને કાગળથી સાબિત કરી શકાય છે. વ્યવહારમાં, એલ્ગોરિધમનો ઉપયોગ વાદળોમાં મોટી સંખ્યામાં ગાંઠો પર ચાલતી મોટી સિસ્ટમ્સમાં થાય છે.

આગળ શું ચર્ચા કરવામાં આવશે તેનું આછું ઉદાહરણ: બે સેનાપતિઓનું કાર્યચાલો વોર્મ-અપ માટે એક નજર કરીએ બે સેનાપતિઓનું કાર્ય.

અમારી પાસે બે સૈન્ય છે - લાલ અને સફેદ. સફેદ સૈનિકો ઘેરાયેલા શહેરમાં સ્થિત છે. સેનાપતિઓ A1 અને A2 ની આગેવાની હેઠળની લાલ ટુકડીઓ શહેરની બે બાજુઓ પર સ્થિત છે. રેડહેડ્સનું કાર્ય સફેદ શહેર પર હુમલો કરવાનું અને જીતવાનું છે. જો કે, દરેક લાલ જનરલની સેના વ્યક્તિગત રીતે સફેદ સેના કરતા નાની હોય છે.

લાલ લોકો માટે વિજયની શરતો: ગોરાઓ પર સંખ્યાત્મક લાભ મેળવવા માટે બંને સેનાપતિઓએ એક જ સમયે હુમલો કરવો જોઈએ. આ કરવા માટે, સેનાપતિઓ A1 અને A2 ને એકબીજા સાથે કરાર પર આવવાની જરૂર છે. જો દરેક વ્યક્તિ અલગથી હુમલો કરે છે, તો રેડહેડ્સ ગુમાવશે.

કરાર સુધી પહોંચવા માટે, જનરલો A1 અને A2 સફેદ શહેરના પ્રદેશ દ્વારા એકબીજાને સંદેશવાહક મોકલી શકે છે. સંદેશવાહક સફળતાપૂર્વક સાથી જનરલ સુધી પહોંચી શકે છે અથવા દુશ્મન દ્વારા અટકાવવામાં આવી શકે છે. પ્રશ્ન: શું લાલ વાળવાળા સેનાપતિઓ વચ્ચે સંદેશાવ્યવહારનો આવો ક્રમ છે (A1 થી A2 અને તેનાથી વિપરીત A2 થી A1 સુધી સંદેશવાહક મોકલવાનો ક્રમ), જેમાં તેઓ X કલાકે હુમલા પર સંમત થવાની ખાતરી આપવામાં આવે છે. અહીં, બાંયધરીનો અર્થ એ છે કે બંને સેનાપતિઓ પાસે અસ્પષ્ટ પુષ્ટિ હશે કે સાથી (અન્ય જનરલ) નિશ્ચિત સમયે X પર હુમલો કરશે.

ધારો કે A1 એ સંદેશ સાથે A2 ને સંદેશવાહક મોકલે છે: "ચાલો આજે મધ્યરાત્રિએ હુમલો કરીએ!" જનરલ A1 જનરલ A2 ની પુષ્ટિ વિના હુમલો કરી શકતો નથી. જો A1 નો સંદેશવાહક આવી ગયો હોય, તો જનરલ A2 સંદેશ સાથે પુષ્ટિ મોકલે છે: "હા, ચાલો આજે ગોરાઓને મારી નાખીએ." પરંતુ હવે જનરલ એ2ને ખબર નથી કે તેનો મેસેન્જર આવ્યો છે કે નહીં, તેની પાસે કોઈ ગેરંટી નથી કે હુમલો એક સાથે થશે કે કેમ. હવે જનરલ A2 ને ફરીથી પુષ્ટિની જરૂર છે.

જો આપણે તેમના સંદેશાવ્યવહારનું વધુ વર્ણન કરીએ, તો તે સ્પષ્ટ થઈ જાય છે કે ભલે ગમે તેટલા સંદેશા વિનિમય ચક્ર હોય, બંને સેનાપતિઓએ તેમના સંદેશા પ્રાપ્ત કર્યા છે તેની ખાતરી આપવાનો કોઈ રસ્તો નથી (ધારી લઈએ કે મેસેન્જરને અટકાવી શકાય છે).

બે જનરલ્સ પ્રોબ્લેમ એ ખૂબ જ સરળ વિતરિત સિસ્ટમનું ઉત્તમ ઉદાહરણ છે જ્યાં અવિશ્વસનીય સંચાર સાથે બે ગાંઠો છે. આનો અર્થ એ છે કે અમારી પાસે 100% ગેરેંટી નથી કે તેઓ સમન્વયિત છે. સમાન સમસ્યાઓની ચર્ચા પછીથી લેખમાં મોટા પાયે કરવામાં આવી છે.

અમે વિતરિત પ્રણાલીઓનો ખ્યાલ રજૂ કરીએ છીએ

વિતરિત સિસ્ટમ એ કમ્પ્યુટર્સનું જૂથ છે (ત્યારબાદ આપણે તેમને નોડ્સ કહીશું) જે સંદેશાઓની આપ-લે કરી શકે છે. દરેક વ્યક્તિગત નોડ અમુક પ્રકારની સ્વાયત્ત એન્ટિટી છે. નોડ તેના પોતાના પર કાર્યો પર પ્રક્રિયા કરી શકે છે, પરંતુ અન્ય નોડ્સ સાથે વાતચીત કરવા માટે, તેને સંદેશા મોકલવા અને પ્રાપ્ત કરવાની જરૂર છે.

સંદેશાઓનો બરાબર અમલ કેવી રીતે થાય છે, કયા પ્રોટોકોલનો ઉપયોગ થાય છે - આ સંદર્ભમાં આ અમને રસ નથી. તે મહત્વનું છે કે વિતરિત સિસ્ટમના ગાંઠો સંદેશા મોકલીને એકબીજા સાથે ડેટાનું વિનિમય કરી શકે છે.

વ્યાખ્યા પોતે ખૂબ જટિલ લાગતી નથી, પરંતુ આપણે ધ્યાનમાં લેવું જોઈએ કે વિતરિત સિસ્ટમમાં સંખ્યાબંધ લક્ષણો છે જે આપણા માટે મહત્વપૂર્ણ હશે.

વિતરિત પ્રણાલીઓના લક્ષણો

1. સંમતિ - સિસ્ટમમાં એક સાથે અથવા સહવર્તી ઘટનાઓની સંભાવના. તદુપરાંત, જ્યાં સુધી અમારી પાસે આ ઘટનાઓની ઘટનાનો સ્પષ્ટ ક્રમ ન હોય ત્યાં સુધી અમે બે અલગ-અલગ ગાંઠો પર બનતી ઘટનાઓને સંભવિત રીતે સહવર્તી ગણીશું. પરંતુ, એક નિયમ તરીકે, અમારી પાસે તે નથી.
2. વૈશ્વિક ઘડિયાળ નથી. વૈશ્વિક ઘડિયાળના અભાવને કારણે અમારી પાસે ઘટનાઓનો સ્પષ્ટ ક્રમ નથી. લોકોની સામાન્ય દુનિયામાં, આપણે એ હકીકતથી ટેવાયેલા છીએ કે આપણી પાસે ઘડિયાળો અને સમય સંપૂર્ણપણે છે. જ્યારે વિતરિત સિસ્ટમની વાત આવે છે ત્યારે બધું બદલાય છે. અતિ-ચોક્કસ અણુ ઘડિયાળો પણ વહી જાય છે, અને એવી પરિસ્થિતિઓ હોઈ શકે છે કે જ્યાં આપણે કહી શકતા નથી કે બેમાંથી કઈ ઘટના પ્રથમ બની હતી. તેથી, આપણે સમય પર પણ આધાર રાખી શકતા નથી.
3. સિસ્ટમ નોડ્સની સ્વતંત્ર નિષ્ફળતા. ત્યાં બીજી સમસ્યા છે: કંઈક ખોટું થઈ શકે છે કારણ કે અમારા ગાંઠો કાયમ માટે ટકી શકતા નથી. હાર્ડ ડ્રાઈવ નિષ્ફળ થઈ શકે છે, ક્લાઉડમાં વર્ચ્યુઅલ મશીન રીબૂટ થઈ શકે છે, નેટવર્ક ઝબકશે અને સંદેશાઓ ખોવાઈ જશે. તદુપરાંત, એવી પરિસ્થિતિઓ હોઈ શકે છે કે જ્યાં નોડ્સ કામ કરે છે, પરંતુ તે જ સમયે સિસ્ટમ સામે કામ કરે છે. સમસ્યાઓના છેલ્લા વર્ગને એક અલગ નામ પણ મળ્યું: સમસ્યા બાયઝેન્ટાઇન સેનાપતિઓ. આ સમસ્યા સાથે વિતરિત સિસ્ટમનું સૌથી લોકપ્રિય ઉદાહરણ બ્લોકચેન છે. પરંતુ આજે આપણે સમસ્યાઓના આ વિશેષ વર્ગને ધ્યાનમાં લઈશું નહીં. અમને એવી પરિસ્થિતિઓમાં રસ હશે જેમાં ફક્ત એક અથવા વધુ ગાંઠો નિષ્ફળ થઈ શકે છે.
4. નોડ્સ વચ્ચે કોમ્યુનિકેશન મોડલ્સ (મેસેજિંગ મોડલ્સ).. અમે પહેલેથી જ સ્થાપિત કર્યું છે કે નોડ્સ સંદેશાઓની આપલે દ્વારા વાતચીત કરે છે. ત્યાં બે જાણીતા મેસેજિંગ મોડલ છે: સિંક્રનસ અને અસિંક્રોનસ.

વિતરિત પ્રણાલીઓમાં નોડ્સ વચ્ચે સંચારના નમૂનાઓ

સિંક્રનસ મોડલ - અમે ખાતરીપૂર્વક જાણીએ છીએ કે સમયનો મર્યાદિત જાણીતો ડેલ્ટા છે જે દરમિયાન સંદેશ એક નોડથી બીજા સુધી પહોંચવાની ખાતરી આપવામાં આવે છે. જો આ સમય પસાર થઈ ગયો હોય અને સંદેશ આવ્યો નથી, તો અમે સુરક્ષિત રીતે કહી શકીએ કે નોડ નિષ્ફળ ગયો છે. આ મોડેલમાં અમારી પાસે અનુમાનિત પ્રતીક્ષા સમય છે.

અસુમેળ મોડેલ - અસુમેળ મોડેલોમાં અમે માનીએ છીએ કે રાહ જોવાનો સમય મર્યાદિત છે, પરંતુ સમયનો એવો કોઈ ડેલ્ટા નથી કે જેના પછી અમે ખાતરી આપી શકીએ કે નોડ નિષ્ફળ ગયો છે. તે. નોડમાંથી સંદેશ માટે રાહ જોવાનો સમય આપખુદ રીતે લાંબો હોઈ શકે છે. આ એક મહત્વપૂર્ણ વ્યાખ્યા છે, અને અમે તેના વિશે આગળ વાત કરીશું.

વિતરિત પ્રણાલીઓમાં સર્વસંમતિનો ખ્યાલ

સર્વસંમતિની વિભાવનાને ઔપચારિક રીતે વ્યાખ્યાયિત કરતાં પહેલાં, ચાલો એવી પરિસ્થિતિનું ઉદાહરણ ધ્યાનમાં લઈએ કે જ્યાં આપણને તેની જરૂર હોય, એટલે કે - રાજ્ય મશીન પ્રતિકૃતિ.

અમારી પાસે કેટલાક વિતરિત લોગ છે. અમે ઇચ્છીએ છીએ કે તે સુસંગત હોય અને વિતરિત સિસ્ટમના તમામ નોડ્સ પર સમાન ડેટા ધરાવતો હોય. જ્યારે નોડ્સમાંથી એક નવી કિંમત શીખે છે કે તે લોગ પર લખવા જઈ રહ્યું છે, ત્યારે તેનું કાર્ય અન્ય તમામ નોડ્સને આ મૂલ્ય પ્રદાન કરવાનું બને છે જેથી કરીને લોગ તમામ નોડ્સ પર અપડેટ થાય અને સિસ્ટમ નવી સુસંગત સ્થિતિમાં જાય. આ કિસ્સામાં, તે મહત્વનું છે કે ગાંઠો એકબીજા સાથે સંમત થાય: બધા ગાંઠો સંમત થાય છે કે સૂચિત નવી કિંમત સાચી છે, બધા ગાંઠો આ મૂલ્યને સ્વીકારે છે, અને ફક્ત આ કિસ્સામાં દરેક જણ લોગ પર નવું મૂલ્ય લખી શકે છે.

બીજા શબ્દોમાં કહીએ તો: નોડ્સમાંથી કોઈએ વાંધો ઉઠાવ્યો નથી કે તેની પાસે વધુ સુસંગત માહિતી છે, અને સૂચિત મૂલ્ય ખોટું હતું. નોડ્સ વચ્ચેનો કરાર અને એક યોગ્ય સ્વીકૃત મૂલ્ય પરનો કરાર એ વિતરિત સિસ્ટમમાં સર્વસંમતિ છે. આગળ, અમે એલ્ગોરિધમ્સ વિશે વાત કરીશું જે વિતરિત સિસ્ટમને સર્વસંમતિ સુધી પહોંચવાની ખાતરી આપે છે.

વધુ ઔપચારિક રીતે, અમે સર્વસંમતિ અલ્ગોરિધમ (અથવા ફક્ત સર્વસંમતિ અલ્ગોરિધમ) ને ચોક્કસ કાર્ય તરીકે વ્યાખ્યાયિત કરી શકીએ છીએ જે રાજ્ય A થી રાજ્ય B માં વિતરિત સિસ્ટમને સ્થાનાંતરિત કરે છે. વધુમાં, આ સ્થિતિ તમામ ગાંઠો દ્વારા સ્વીકારવામાં આવે છે, અને તમામ ગાંઠો તેની પુષ્ટિ કરી શકે છે. જેમ જેમ તે તારણ આપે છે, આ કાર્ય એટલું તુચ્છ નથી જેટલું તે પ્રથમ નજરમાં લાગે છે.

સર્વસંમતિ અલ્ગોરિધમના ગુણધર્મો

સિસ્ટમ અસ્તિત્વમાં રહે તે માટે સર્વસંમતિ અલ્ગોરિધમમાં ત્રણ ગુણધર્મો હોવા આવશ્યક છે અને રાજ્યથી રાજ્યમાં ખસેડવામાં થોડી પ્રગતિ થાય છે:

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 અમલીકરણો સંપૂર્ણપણે યોગ્ય રીતે કામ કરતા નથી.

પૉક્સોસના કાર્યનું વિગતવાર વિશ્લેષણ એક કરતાં વધુ લેખ લેશે, તેથી હું અલ્ગોરિધમનો મુખ્ય વિચાર ખૂબ જ ટૂંકમાં જણાવવાનો પ્રયત્ન કરીશ. મારા લેખના અંતે લિંક્સમાં તમને આ વિષયમાં વધુ ડાઇવિંગ માટે સામગ્રી મળશે.

Paxos ખાતે ભૂમિકાઓ

Paxos અલ્ગોરિધમમાં ભૂમિકાઓનો ખ્યાલ છે. ચાલો ત્રણ મુખ્ય મુદ્દાઓને ધ્યાનમાં લઈએ (વધારાની ભૂમિકાઓ સાથે ફેરફારો છે):

1. પ્રસ્તાવકો (શબ્દોનો ઉપયોગ પણ થઈ શકે છે: નેતાઓ અથવા સંયોજકો). આ એવા લોકો છે જેઓ વપરાશકર્તા પાસેથી કેટલાક નવા મૂલ્ય વિશે શીખે છે અને નેતાની ભૂમિકા નિભાવે છે. તેમનું કાર્ય નવા મૂલ્ય માટે દરખાસ્તોનો રાઉન્ડ શરૂ કરવાનું અને નોડ્સની આગળની ક્રિયાઓનું સંકલન કરવાનું છે. તદુપરાંત, પોક્સોસ અમુક પરિસ્થિતિઓમાં ઘણા નેતાઓની હાજરી માટે પરવાનગી આપે છે.
2. સ્વીકારનારા (મતદારો). આ એવા ગાંઠો છે જે કોઈ ચોક્કસ મૂલ્યને સ્વીકારવા અથવા નકારવા માટે મત આપે છે. તેમની ભૂમિકા ખૂબ જ મહત્વપૂર્ણ છે, કારણ કે નિર્ણય તેમના પર નિર્ભર છે: સર્વસંમતિ અલ્ગોરિધમના આગલા તબક્કા પછી સિસ્ટમ કઈ સ્થિતિમાં જશે (અથવા નહીં).
3. શીખનારા. નોડ્સ કે જે સિસ્ટમની સ્થિતિ બદલાઈ ગઈ હોય ત્યારે નવી સ્વીકૃત કિંમતને સરળ રીતે સ્વીકારે છે અને લખે છે. તેઓ નિર્ણય લેતા નથી, તેઓ માત્ર ડેટા મેળવે છે અને અંતિમ વપરાશકર્તાને આપી શકે છે.

એક નોડ વિવિધ પરિસ્થિતિઓમાં ઘણી ભૂમિકાઓને જોડી શકે છે.

કોરમનો ખ્યાલ

અમે ધારીએ છીએ કે અમારી પાસે એક સિસ્ટમ છે N ગાંઠો અને તેમાંથી મહત્તમ F ગાંઠો નિષ્ફળ થઈ શકે છે. જો F નોડ્સ નિષ્ફળ જાય, તો અમારી પાસે ઓછામાં ઓછું હોવું જોઈએ 2F+1 સ્વીકારનાર ગાંઠો.

આ જરૂરી છે જેથી અમારી પાસે હંમેશા બહુમતી હોય, સૌથી ખરાબ પરિસ્થિતિમાં પણ, "સારા" નોડ્સ કે જે યોગ્ય રીતે કાર્ય કરે છે. તે જ F+1 "સારા" નોડ્સ કે જે સંમત થયા છે, અને અંતિમ મૂલ્ય સ્વીકારવામાં આવશે. નહિંતર, એવી પરિસ્થિતિ આવી શકે છે કે જ્યાં અમારા વિવિધ સ્થાનિક જૂથો જુદા જુદા અર્થો લે છે અને એકબીજા સાથે સંમત થઈ શકતા નથી. તેથી, મત જીતવા માટે અમારે સંપૂર્ણ બહુમતીની જરૂર છે.

Paxos સર્વસંમતિ અલ્ગોરિધમ કેવી રીતે કાર્ય કરે છે તેનો સામાન્ય વિચાર

પૉક્સોસ અલ્ગોરિધમમાં બે મોટા તબક્કાઓનો સમાવેશ થાય છે, જે બદલામાં દરેકને બે તબક્કામાં વિભાજિત કરવામાં આવે છે:

1. તબક્કો 1a: તૈયાર કરો. તૈયારીના તબક્કા દરમિયાન, નેતા (પ્રસ્તાવક) તમામ ગાંઠોને જાણ કરે છે: “અમે મતદાનનો નવો તબક્કો શરૂ કરી રહ્યા છીએ. અમારી પાસે એક નવો રાઉન્ડ છે. આ રાઉન્ડની સંખ્યા n છે. હવે અમે મતદાન શરૂ કરીશું." હમણાં માટે, તે ફક્ત નવા ચક્રની શરૂઆતની જાણ કરે છે, પરંતુ નવા મૂલ્યની જાણ કરતું નથી. આ તબક્કાનું કાર્ય એક નવો રાઉન્ડ શરૂ કરવાનું અને દરેકને તેના અનન્ય નંબરની જાણ કરવાનું છે. રાઉન્ડ નંબર મહત્વપૂર્ણ છે, તે અગાઉના તમામ નેતાઓના તમામ અગાઉના મતદાન નંબરો કરતાં વધુ મૂલ્ય હોવું આવશ્યક છે. કારણ કે તે રાઉન્ડ નંબરને આભારી છે કે સિસ્ટમમાં અન્ય ગાંઠો સમજી શકશે કે નેતાનો ડેટા કેટલો તાજેતરનો છે. સંભવ છે કે અન્ય નોડ્સમાં પહેલાથી જ ઘણા પછીના રાઉન્ડના મતદાન પરિણામો છે અને તે ફક્ત નેતાને કહેશે કે તે સમયની પાછળ છે.
2. તબક્કો 1b: વચન. જ્યારે સ્વીકારનાર નોડ્સ નવા મતદાન તબક્કાની સંખ્યા પ્રાપ્ત કરે છે, ત્યારે બે પરિણામો શક્ય છે:
   • નવા મતની સંખ્યા n એ અગાઉના કોઈપણ મતની સંખ્યા કરતાં મોટી છે જેમાં સ્વીકારનારએ ભાગ લીધો હતો. પછી સ્વીકારનાર નેતાને વચન મોકલે છે કે તે n થી ઓછી સંખ્યા સાથે વધુ મતોમાં ભાગ લેશે નહીં. જો સ્વીકારનાર પહેલાથી જ કંઈક માટે મત આપે છે (એટલે ​​​​કે, તેણે પહેલાથી જ બીજા તબક્કામાં અમુક મૂલ્ય સ્વીકાર્યું છે), તો તે સ્વીકૃત મૂલ્ય અને મતની સંખ્યાને જોડે છે જેમાં તેણે તેના વચનમાં ભાગ લીધો હતો.
   • નહિંતર, જો સ્વીકારનાર પહેલાથી જ ઉચ્ચ-નંબરવાળા મત વિશે જાણે છે, તો તે ફક્ત તૈયારીના પગલાને અવગણી શકે છે અને નેતાને પ્રતિસાદ આપી શકશે નહીં.
3. તબક્કો 2a: સ્વીકારો. નેતાને કોરમ (સિસ્ટમમાં મોટાભાગના નોડ્સ) ના પ્રતિસાદની રાહ જોવાની જરૂર છે અને, જો જરૂરી સંખ્યામાં પ્રતિસાદો પ્રાપ્ત થાય, તો તેની પાસે ઇવેન્ટ્સના વિકાસ માટે બે વિકલ્પો છે:
   • કેટલાક સ્વીકારકોએ એવા મૂલ્યો મોકલ્યા કે જેના માટે તેઓ પહેલાથી જ મત આપી ચૂક્યા છે. આ કિસ્સામાં, નેતા મહત્તમ સંખ્યા સાથે મતમાંથી મૂલ્ય પસંદ કરે છે. ચાલો આ મૂલ્યને x કહીએ, અને તે તમામ નોડ્સને સંદેશ મોકલે છે જેમ કે: “સ્વીકારો (n, x)”, જ્યાં પ્રથમ મૂલ્ય એ તેના પોતાના પ્રપોઝ સ્ટેપમાંથી મતદાન નંબર છે, અને બીજું મૂલ્ય તે છે જેના માટે દરેક ભેગા થયા હતા, એટલે કે મૂલ્ય કે જેના માટે આપણે ખરેખર મત આપીએ છીએ.
   • જો સ્વીકારનારાઓમાંથી કોઈએ કોઈ મૂલ્યો મોકલ્યા ન હોય, પરંતુ તેઓએ આ રાઉન્ડમાં મત આપવાનું વચન આપ્યું હોય, તો નેતા તેમને તેમના મૂલ્ય માટે મત આપવા માટે આમંત્રિત કરી શકે છે, જે મૂલ્ય માટે તેઓ પ્રથમ સ્થાને નેતા બન્યા હતા. ચાલો તેને y કહીએ. તે બધા નોડ્સને સંદેશ મોકલે છે જેમ કે: “સ્વીકારો (n, y)”, અગાઉના પરિણામની જેમ.
4. તબક્કો 2b: સ્વીકાર્યું. આગળ, સ્વીકારનાર નોડ્સ, નેતા તરફથી "સ્વીકારો(...)" સંદેશ પ્રાપ્ત કર્યા પછી, તેની સાથે સંમત થાય છે (બધા નોડ્સને પુષ્ટિ મોકલો કે તેઓ નવા મૂલ્ય સાથે સંમત છે) માત્ર જો તેઓએ અમુક (અન્ય) વચન આપ્યું ન હોય તો જ નેતા રાઉન્ડ નંબર સાથે મતદાનમાં ભાગ લેશે n' > n, અન્યથા તેઓ પુષ્ટિકરણ વિનંતીને અવગણે છે.

   જો મોટાભાગના ગાંઠો નેતાને પ્રતિસાદ આપે છે, અને તે બધાએ નવા મૂલ્યની પુષ્ટિ કરી છે, તો પછી નવું મૂલ્ય સ્વીકૃત માનવામાં આવે છે. હુરે! જો બહુમતી સુધી પહોંચી ન હોય અથવા એવા ગાંઠો હોય કે જેણે નવા મૂલ્યને સ્વીકારવાનો ઇનકાર કર્યો હોય, તો પછી બધું શરૂ થાય છે.

આ રીતે Paxos અલ્ગોરિધમ કામ કરે છે. આમાંના દરેક તબક્કામાં ઘણી સૂક્ષ્મતા છે, અમે વ્યવહારીક રીતે વિવિધ પ્રકારની નિષ્ફળતાઓ, બહુવિધ નેતાઓની સમસ્યાઓ અને ઘણું બધું ધ્યાનમાં લીધું નથી, પરંતુ આ લેખનો હેતુ ફક્ત વાચકને ઉચ્ચ સ્તરે વિતરિત કમ્પ્યુટિંગની દુનિયા સાથે પરિચય આપવાનો છે.

તે નોંધવું પણ યોગ્ય છે કે પૉક્સોસ તેના પ્રકારનો એકમાત્ર નથી, અન્ય ગાણિતીક નિયમો છે, ઉદાહરણ તરીકે, રફટ, પરંતુ આ બીજા લેખ માટેનો વિષય છે.

વધુ અભ્યાસ માટે સામગ્રીની લિંક્સ

પ્રારંભિક સ્તર:

• વિતરિત સર્વસંમતિ કેવી રીતે કાર્ય કરે છે?, પ્રીતિ કાસિરેડ્ડી, માધ્યમ પર બ્લોગ લેખ
• Paxos સરળ બનાવી. વાસ્તવિકતા માટે, આદિ કાંચેરલા , માધ્યમ પરનો બ્લોગ લેખ
• વિકેન્દ્રિત વિચારો, ઇત્તાઇ અબ્રાહમ, બ્લોગ
• સિંક્રોની, અસિંક્રોની અને આંશિક સિંક્રોની, ઇત્તાઇ અબ્રાહમ, બ્લોગ લેખ

લેસ્લી લેમપોર્ટ સ્તર:

• એક ખામીયુક્ત પ્રક્રિયા સાથે વિતરિત સર્વસંમતિની અશક્યતા (FLP અશક્યતા), ફિશર, લિન્ચ અને પેટરસન, સંશોધન પેપર, 1985
• પાર્ટ-ટાઇમ સંસદ, લેસ્લી લેમપોર્ટ, સંશોધન પેપર, 1998
• Paxos સરળ બનાવી, લેસ્લી લેમપોર્ટ, સંશોધન પેપર, 2001

સોર્સ: www.habr.com