Beləliklə, təsəvvür edək. Otaqda 5 pişik kilidlənib və sahibini oyatmaq üçün hamı bu barədə razılığa gəlməlidir, çünki onlar yalnız beşi ilə ona söykənərək qapını aça bilərlər. Əgər pişiklərdən biri Şrödingerin pişiyidirsə və digər pişiklər onun qərarından xəbərsizdirlərsə, sual yaranır: “Onlar bunu necə edə bilərlər?”.
Bu yazıda mən sizə paylanmış sistemlər dünyasının nəzəri komponenti və onların iş prinsipləri haqqında sadə dillə məlumat verəcəyəm. Həm də Paxos'a yatan ana fikri səthi olaraq nəzərdən keçirək.
Tərtibatçılar bulud infrastrukturlarından, müxtəlif verilənlər bazalarından istifadə etdikdə, çoxlu sayda qovşaqların klasterlərində işlədikdə, məlumatların ardıcıl, təhlükəsiz və həmişə mövcud olacağına əmin olurlar. Bəs zəmanətlər haradadır?
Əslində, bizdə olan zəmanətlər təchizatçı zəmanətləridir. Onlar sənədlərdə aşağıdakı kimi təsvir edilmişdir: "Bu xidmət kifayət qədər etibarlıdır, verilmiş SLA-ya malikdir, narahat olmayın, hər şey gözlədiyiniz kimi paylanacaq."
Biz ən yaxşısına inanmağa meylliyik, çünki böyük şirkətlərin ağıllı əmiləri bizi hər şeyin yaxşı olacağına inandırırdılar. Biz özümüzə sual vermirik: niyə, əslində, bu ümumiyyətlə işləyə bilər? Belə sistemlərin düzgün işləməsi üçün hər hansı rəsmi əsaslandırma varmı?
Bu yaxınlarda getdim və bu mövzudan çox ilham aldı. Məktəbdəki mühazirələr kompüter sistemləri ilə əlaqəli hər şeydən daha çox riyazi analiz dərslərinə bənzəyirdi. Ancaq hər gün şübhə etmədən istifadə etdiyimiz ən vacib alqoritmlər bir anda məhz belə sübut olundu.
Müasir paylanmış sistemlərin əksəriyyəti Paxos konsensus alqoritmi və onun müxtəlif modifikasiyalarından istifadə edir. Ən maraqlısı odur ki, bu alqoritmin etibarlılığı və prinsipcə, mövcud olma ehtimalı sadəcə qələm və kağızla sübuta yetirilə bilər. Eyni zamanda, praktikada alqoritm buludlarda çox sayda qovşaqda işləyən böyük sistemlərdə istifadə olunur.
Bundan sonra nələrin müzakirə olunacağının yüngül təsviri: iki generalın problemiGəlin istiləşməyə nəzər salaq .
Bizim iki ordumuz var - qırmızı və ağ. Ağ qoşunlar mühasirəyə alınmış şəhərdə yerləşir. A1 və A2 generallarının başçılıq etdiyi qırmızı qoşunlar şəhərin iki tərəfində yerləşir. Qızılbaşların vəzifəsi ağ şəhərə hücum etmək və qalib gəlməkdir. Ancaq hər bir qırmızı generalın ordusu ayrı-ayrılıqda ağların ordusundan kiçikdir.
Qızılbaşlar üçün qələbə şərtləri: ağlar üzərində say baxımından üstün olmaq üçün hər iki general eyni anda hücuma keçməlidir. Bunun üçün A1 və A2 generallarının bir-biri ilə razılaşması lazımdır. Hamı ayrı-ayrılıqda hücuma keçsə, qızılbaşlar uduzacaqlar.
Danışıqlar aparmaq üçün A1 və A2 generalları ağ şəhərin ərazisi ilə bir-birinə elçilər göndərə bilərlər. Elçi müttəfiq generala uğurla çata bilər və ya düşmən tərəfindən tutula bilər. Sual: Qırmızı saçlı generallar arasında belə bir əlaqə ardıcıllığı varmı (xəbərçilərin A1-dən A2-yə və əksinə A2-dən A1-ə göndərilməsi ardıcıllığı), onların X saatında hücum barədə razılığa gəlmələrinə zəmanət verilir. Burada, zəmanətlərlə başa düşülür ki, hər iki general bir müttəfiqin (başqa bir generalın) təyin olunmuş X vaxtında hücum edəcəyini birmənalı şəkildə təsdiqləyəcəklər.
Tutaq ki, A1 A2-yə “Bu gün gecə yarısı hücum edək!” mesajı ilə messencer göndərir. General A1, General A2-dən təsdiq olmadan hücum edə bilməz. A1-dən gələn messencer çatdısa, general A2 mesajı ilə təsdiq göndərir: "Bəli, bu gün ağları dolduraq." Amma indi General A2 onun elçisinin çatıb-çatmadığından xəbərsizdir, hücumun eyni vaxtda olub-olmayacağına zəmanəti yoxdur. İndi General A2 yenidən təsdiq tələb edir.
Onların əlaqəsini daha ətraflı təsvir etsək, belə çıxır: nə qədər mesaj mübadiləsi dövriyyəsi olsa da, hər iki generala mesajlarının alındığına zəmanət vermək mümkün deyil (əgər hər hansı bir xəbərçinin ələ keçirilə biləcəyini nəzərə alsaq).
İki general problemi etibarsız rabitə ilə iki qovşağın olduğu çox sadə paylanmış sistemin əla təsviridir. Beləliklə, onların sinxronizasiyasına 100% zəmanətimiz yoxdur. Məqalənin sonrakı hissəsində daha geniş miqyasda oxşar problemlər haqqında.
Paylanmış sistemlər konsepsiyasının təqdim edilməsi
Paylanmış sistem mesaj mübadiləsi apara bilən kompüterlər qrupudur (bundan sonra qovşaqlar). Hər bir fərdi qovşaq hansısa muxtar varlıqdır. Bir qovşaq öz-özünə tapşırıqları emal edə bilər, lakin digər qovşaqlarla əlaqə yaratmaq üçün mesaj göndərmək və qəbul etmək lazımdır.
Mesajlar konkret olaraq necə həyata keçirilir, hansı protokollardan istifadə olunur - bu, bizi bu kontekstdə maraqlandırmır. Paylanmış sistemin qovşaqlarının mesaj göndərməklə bir-biri ilə məlumat mübadiləsi apara bilməsi vacibdir.
Tərifin özü çox mürəkkəb görünmür, lakin nəzərə alın ki, paylanmış sistem bizim üçün vacib olacaq bir sıra atributlara malikdir.
Paylanmış sistemlərin atributları
- Uyğunluq – sistemdə eyni vaxtda və ya rəqabətli hadisələrin baş vermə ehtimalı. Üstəlik, iki fərqli qovşaqda baş verən hadisələrin, bu hadisələrin baş verdiyi dəqiq bir sıraya sahib olana qədər potensial olaraq paralel olduğunu nəzərə alacağıq. Və adətən biz yox.
- Qlobal saat yoxdur. Qlobal saat olmadığı üçün hadisələrin dəqiq ardıcıllığımız yoxdur. Adi insanların dünyasında biz tamamilə saatlarımızın və vaxtımızın olmasına öyrəşmişik. Paylanmış sistemlərə gəldikdə hər şey dəyişir. Hətta son dərəcə dəqiq atom saatlarında sürüşmə var və elə vəziyyətlər var ki, iki hadisədən hansının birinci baş verdiyini deyə bilmirik. Ona görə də vaxta arxalana bilmərik.
- Sistem qovşaqlarının müstəqil nasazlığı. Başqa bir problem var: sadəcə olaraq qovşaqlarımız əbədi olmadığı üçün bir şey səhv ola bilər. Sərt disk uğursuz ola bilər, buluddakı virtual maşın yenidən işə düşə bilər, şəbəkə yanıb-sönə bilər və mesajlar itə bilər. Üstəlik, qovşaqların işlədiyi vəziyyətlər var, lakin eyni zamanda sistemə qarşı işləyirlər. Problemlərin son sinfi hətta ayrıca bir ad aldı: problem . Belə bir problemi olan paylanmış sistemin ən məşhur nümunəsi Blockchain-dir. Ancaq bu gün biz bu xüsusi sinif problemləri nəzərdən keçirməyəcəyik. Yalnız bir və ya daha çox qovşağın uğursuz ola biləcəyi vəziyyətlərlə maraqlanacağıq.
- Düyünlər arasında əlaqə modelləri (mesajlaşma modelləri).. Artıq qovşaqların mesaj mübadiləsi yolu ilə əlaqə qurduğunu öyrəndik. İki məşhur mesajlaşma modeli var: sinxron və asinxron.
Paylanmış sistemlərdə qovşaqlar arasında əlaqə modelləri
Sinxron model - biz dəqiq bilirik ki, mesajın bir qovşaqdan digərinə çatmasına zəmanət verən məhdud bir zaman deltası var. Bu vaxt bitibsə və mesaj gəlməyibsə, qovşağın uğursuz olduğunu əminliklə söyləyə bilərik. Belə bir modeldə gözlənilən gözləmə müddətimiz var.
Asinxron model – asinxron modellərdə gözləmə vaxtının sonlu olduğunu fərz edirik, lakin qovşağın uğursuz olduğuna zəmanət verilə bilən vaxt deltası yoxdur. Bunlar. bir qovşaqdan mesajın gözləmə müddəti özbaşına uzun ola bilər. Bu vacib bir tərifdir və bu barədə daha ətraflı danışacağıq.
Paylanmış sistemlərdə konsensus anlayışı
Konsensus anlayışını rəsmi şəkildə müəyyən etməzdən əvvəl, ehtiyac duyduğumuz bir vəziyyətin nümunəsini nəzərdən keçirin, yəni - Dövlət Maşın Replikasiyası.
Bəzi paylanmış jurnalımız var. Biz onun ardıcıl olmasını və paylanmış sistemin bütün qovşaqlarında eyni məlumatları ehtiva etməsini istərdik. Qovşaqlardan biri jurnala yazacağı yeni dəyəri öyrəndikdə, onun vəzifəsi bu dəyəri bütün digər qovşaqlara təklif etməkdir ki, jurnal bütün qovşaqlarda yenilənsin və sistem yeni ardıcıl vəziyyətə keçsin. Eyni zamanda, qovşaqların öz aralarında razı olması vacibdir: bütün qovşaqlar təklif olunan yeni dəyərin düzgün olması ilə razılaşır, bütün qovşaqlar bu dəyəri qəbul edir və yalnız bu halda hər kəs yeni bir dəyər daxil edə bilər.
Başqa sözlə: qovşaqların heç biri daha müasir məlumatlara sahib olduqlarına etiraz etmədi və təklif olunan dəyər səhv idi. Düyünlər arasında razılaşma və vahid düzgün qəbul edilmiş dəyər üzrə razılaşma paylanmış sistemdə konsensusdur. Sonra, paylanmış sistemin zəmanətli ilə konsensusa çatmasına imkan verən alqoritmlər haqqında danışacağıq.
Daha formal olaraq, biz konsensus alqoritmini (və ya sadəcə olaraq konsensus alqoritmini) paylanmış sistemi A vəziyyətindən B vəziyyətinə götürən bəzi funksiya kimi müəyyən edə bilərik. Üstəlik, bu vəziyyət bütün qovşaqlar tərəfindən qəbul edilir və bütün qovşaqlar bunu təsdiq edə bilər. Göründüyü kimi, bu vəzifə heç də ilk baxışdan göründüyü qədər əhəmiyyətsiz deyil.
Konsensus alqoritminin xassələri
Sistemin mövcudluğunu davam etdirməsi və vəziyyətdən vəziyyətə keçiddə müəyyən irəliləyiş əldə etməsi üçün konsensus alqoritmi üç xüsusiyyətə malik olmalıdır:
- Müqavilə – bütün düzgün işləyən qovşaqlar eyni dəyəri almalıdır (məqalələrdə bu xüsusiyyət təhlükəsizlik xüsusiyyəti kimi də tapılır). İndi fəaliyyət göstərən bütün qovşaqlar (sıradan çıxmamış və qalanlarla əlaqəni itirməmiş) razılığa gəlməli və bəzi yekun ümumi dəyəri qəbul etməlidir.
Burada başa düşmək vacibdir ki, nəzərdən keçirdiyimiz paylanmış sistemdəki qovşaqlar razılaşmaq istəyirlər. Yəni, indi bir şeyin sadəcə uğursuz ola biləcəyi sistemlərdən danışırıq (məsələn, bəzi node uğursuz olur), lakin bu sistemdə qəsdən başqalarına qarşı işləyən qovşaqlar mütləq yoxdur (Bizans generallarının vəzifəsi). Bu xüsusiyyətə görə sistem ardıcıl olaraq qalır.
- Bütünlük - bütün düzgün işləyən qovşaqlar eyni dəyəri təklif edərsə v, buna görə də hər düzgün işləyən node bu dəyəri qəbul etməlidir v.
- Xitam - bütün düzgün işləyən qovşaqlar nəticədə alqoritmin sistemdə irəliləyiş əldə etməsinə imkan verən müəyyən dəyər (canlılıq xüsusiyyəti) alacaq. Düzgün işləyən hər bir fərdi node gec-tez yekun dəyəri qəbul etməli və onu təsdiq etməlidir: "Mənim üçün bu dəyər doğrudur, mən bütün sistemlə razıyam".
Konsensus alqoritminin necə işlədiyinə bir nümunə
Alqoritmin xassələri tam aydın olmaya bilər. Buna görə də, bütün qovşaqların gözlənildiyi kimi işlədiyi, mesajların itmədiyi və heç bir şeyin pozulmadığı sinxron mesajlaşma modeli olan sistemdə ən sadə konsensus alqoritminin hansı mərhələdən keçdiyini nümunə ilə göstərəcəyik (bu, həqiqətən də baş verirmi?).
- Hər şey evlilik təklifi ilə başlayır (Təklif et). Tutaq ki, müştəri “Node 1” adlı qovşaqla əlaqə qurur və əməliyyata başlayır, qovşağına yeni dəyər – O ötürür. Bundan sonra biz “Node 1”i çağıracağıq. təklif etmək. Təklif edən "Node 1" indi necə olur ki, bütün sistemi təzə məlumatlara malik olduğunu bildirməlidir və o, bütün digər qovşaqlara mesaj göndərir: "Bax! Mən "O" qiymətini aldım və onu yazmaq istəyirəm! Lütfən, logunuzda "O"nu da qeyd edəcəyinizi təsdiqləyin."
- Növbəti mərhələ təklif olunan dəyər üçün səsvermədir (Səsvermə). Bu nə üçündür? Ola bilər ki, digər qovşaqlar daha son məlumat aldılar və eyni əməliyyat haqqında məlumat var.
"Node 1" qovşağı öz təklifini göndərdikdə, digər qovşaqlar bu hadisə haqqında məlumat üçün öz qeydlərini yoxlayırlar. Əgər münaqişə yoxdursa, qovşaqlar elan edir: “Bəli, bu hadisə ilə bağlı başqa məlumatım yoxdur. 'O' dəyəri layiq olduğumuz ən müasir məlumatdır."İstənilən başqa halda, qovşaqlar “Node 1”ə cavab verə bilər: “Qulaq asın! Məndə bu əməliyyatla bağlı daha yeni məlumatlar var. "Oh" deyil, daha yaxşı bir şey."
Səsvermə mərhələsində qovşaqlar bir qərara gəlir: ya hamısı eyni dəyəri qəbul edir, ya da onlardan biri onun daha yeni məlumatlara malik olduğunu bildirərək əleyhinə səs verir.
- Əgər səsvermə raundu uğurlu keçibsə və hamı lehinə olubsa, o zaman sistem yeni mərhələyə keçir - dəyərin qəbulu (Qəbul). "Node 1" digər qovşaqlardan gələn bütün cavabları toplayır və hesabat verir: "Hər kəs 'O' dəyəri ilə razılaşdı! İndi mən rəsmi olaraq bəyan edirəm ki, “O” bizim yeni mənamızdır, hamı üçün eynidir! Bunu dəftərinizə yazın, unutmayın. Jurnalınıza yazın!"
- Qalan qovşaqlar özləri üçün “O” dəyərini yazdıqlarına dair təsdiq (Qəbul edildi) göndərirlər, bu müddət ərzində yeni heç nə alınmayıb (bir növ iki fazalı öhdəlik). Bu əlamətdar hadisədən sonra hesab edirik ki, paylanmış əməliyyat başa çatıb.
Beləliklə, sadə halda konsensus alqoritmi dörd addımdan ibarətdir: təklif etmək, səs vermək (səs vermək), qəbul etmək (qəbul etmək), qəbulun təsdiqi (qəbul edilmişdir).
Əgər hansısa addımda razılığa gələ bilmədiksə, təklif olunan dəyəri təsdiqləməkdən imtina edən qovşaqların verdiyi məlumatları nəzərə alaraq alqoritm yenidən işə salınır.
Asinxron sistemdə konsensus alqoritmi
Bundan əvvəl hər şey rəvan idi, çünki söhbət sinxron mesajlaşma modelindən gedirdi. Ancaq bilirik ki, müasir dünyada biz hər şeyi asinxron etməyə öyrəşmişik. Bənzər bir alqoritm asinxron mesajlaşma modeli olan bir sistemdə necə işləyir, burada bir qovşaqdan cavab gözləmə müddətinin ixtiyari olaraq uzun ola biləcəyinə inanırıq (yeri gəlmişkən, node uğursuzluğu da nümunə kimi qəbul edilə bilər. özbaşına uzun cavab verə bilər).
İndi konsensus alqoritminin prinsipcə necə işlədiyini bildiyimizə görə, sual bu nöqtəyə çatmış maraqlanan oxucular üçündür: asinxron mesaj modeli olan N qovşaq sistemində neçə qovşaq aşağı düşə bilər ki, sistem hələ də konsensusa gələ bilsin. ?
Düzgün cavab və spoylerin arxasındakı əsaslandırma.Düzgün cavab: 0. Asinxron sistemdə hətta bir qovşaq aşağı düşərsə, sistem konsensusa gələ bilməyəcək. Bu ifadə məşhur FLP teoremində (1985, Fischer, Lynch, Paterson, məqalənin sonundakı orijinala keçid) sübut edilmişdir: "Ən azı bir qovşaq uğursuz olarsa, paylanmış konsensusun əldə edilməsinin mümkünsüzlüyü."
Uşaqlar, onda bir problemimiz var, hər şeyin bizimlə asinxron olmasına öyrəşmişik. Və budur. Necə yaşamağa davam etmək olar?
Bayaq nəzəriyyədən, riyaziyyatdan danışdıq. Riyazi dildən bizim dilimizə - mühəndisliyə çevirən "konsensus əldə edilə bilməz" nə deməkdir? Bu o deməkdir ki, "həmişə nail olmaq mümkün deyil", yəni. konsensusun əldə olunmadığı bir hal var. Və bu hal nədir?
Bu, yuxarıda təsvir edilən canlılıq mülkiyyətinin pozulmasıdır. Bizim ümumi razılığımız yoxdur və bütün qovşaqlardan cavab almadığımız halda sistem tərəqqi edə bilməz (sonlu vaxtda xitam verə bilməz). Çünki asinxron sistemdə bizim proqnozlaşdırıla bilən cavab vaxtımız yoxdur və bir qovşağın işləmədiyini və ya cavab vermək üçün çox vaxt tələb etdiyini bilə bilmərik.
Amma praktikada həllini tapa bilərik. Alqoritmimiz uğursuzluqlar halında uzun müddət işləyə bilsin (potensial olaraq qeyri-müəyyən işləyə bilər). Ancaq əksər hallarda, qovşaqların əksəriyyəti düzgün işlədikdə, sistemdə irəliləyiş olacaq.
Praktikada biz qismən sinxron rabitə modelləri ilə məşğul oluruq. Qismən sinxronizm belə başa düşülür: ümumi halda, bizdə asinxron bir model var, lakin müəyyən bir zamanın müəyyən bir "qlobal sabitləşmə vaxtı" anlayışı formal olaraq təqdim olunur.
Bu an özbaşına uzun müddət gəlməyə bilər, amma bir gün gəlməlidir. Virtual zəngli saat çalacaq və o andan etibarən mesajların çatacağı vaxt deltasını təxmin edə bilərik. Bu andan etibarən sistem asinxrondan sinxrona keçir. Praktikada biz belə sistemlərlə məşğul oluruq.
Paxos alqoritmi konsensus problemlərini həll edir
bəzi qovşaqların sıradan çıxması şərtilə qismən sinxron sistemlər üçün konsensus problemini həll edən alqoritmlər ailəsidir. Paxosun müəllifidir . O, 1989-cu ildə alqoritmin mövcudluğunun və düzgünlüyünün rəsmi sübutunu təklif etdi.
Lakin sübut heç də əhəmiyyətsiz olmadığı ortaya çıxdı. İlk nəşr yalnız 1998-ci ildə (33 səhifə) alqoritmi təsvir etdi. Məlum olub ki, bunu başa düşmək son dərəcə çətin olub və 2001-ci ildə 14 səhifəlik məqalənin izahı dərc olunub. Nəşrlərin cildləri əslində konsensus probleminin heç də sadə olmadığını və bu cür alqoritmlərin arxasında ən ağıllı insanların nəhəng işinin dayandığını göstərmək üçün verilmişdir.
Maraqlıdır ki, Lesli Lamporun özü mühazirəsində qeyd edib ki, ikinci məqalə-izahda bir ifadə, bir sətir (hansı olduğunu dəqiqləşdirməyib) var ki, bunu müxtəlif cür şərh etmək olar. Və buna görə də, çoxlu sayda müasir Paxos tətbiqləri tamamilə düzgün işləmir.
Paxos işinin ətraflı təhlili birdən çox məqalə tələb edəcək, ona görə də alqoritmin əsas fikrini çox qısa şəkildə çatdırmağa çalışacağam. Məqaləmin sonundakı bağlantılarda bu mövzuya daha çox dalmaq üçün materiallar tapa bilərsiniz.
Paxos-da rollar
Paxos alqoritmində rollar anlayışı var. Üç əsası nəzərdən keçirin (əlavə rollarla dəyişikliklər var):
- Təklifçilər (şərtlər də ola bilər: liderlər və ya koordinatorlar). Bunlar istifadəçidən bəzi yeni mənalar öyrənən və lider rolunu götürən uşaqlardır. Onların vəzifəsi yeni dəyər üçün bir sıra təkliflər təqdim etmək və qovşaqların gələcək hərəkətlərini əlaqələndirməkdir. Üstəlik, Paxos müəyyən vəziyyətlərdə bir neçə liderin olmasına imkan verir.
- Qəbul edənlər (Seçicilər). Bunlar müəyyən bir dəyəri qəbul etmək və ya rədd etmək üçün səs verən qovşaqlardır. Onların rolu çox vacibdir, çünki qərar onlardan asılıdır: konsensus alqoritminin növbəti mərhələsindən sonra sistemin hansı vəziyyətə gedəcəyi (ya da getməyəcəyi).
- Öyrənənlər. Sistemin vəziyyəti dəyişdikdə yeni qəbul edilmiş dəyəri sadəcə qəbul edən və yazan qovşaqlar. Onlar qərar qəbul etmirlər, sadəcə məlumatları alırlar və son istifadəçiyə verə bilərlər.
Bir node müxtəlif vəziyyətlərdə bir neçə rolu birləşdirə bilər.
Kvorum anlayışı
sistemimiz olduğunu güman edirik N qovşaqlar. Və onların əksəriyyəti F qovşaqlar uğursuz ola bilər. Əgər F qovşaqları uğursuz olarsa, onda ən azı olmalıdır 2F+1 qəbuledici qovşaqlar.
Bu, həmişə, hətta ən pis vəziyyətdə belə, "yaxşı", düzgün işləyən qovşaqların çoxluğa sahib olması üçün lazımdır. Yəni f+1 razılaşan "yaxşı" qovşaqlar və yekun dəyər qəbul ediləcək. Əks halda, müxtəlif yerli qrupların fərqli mənalar alacağı və öz aralarında razılığa gələ bilməyəcəyi vəziyyət yarana bilər. Deməli, səsi qazanmaq üçün mütləq çoxluğa ehtiyacımız var.
Paxos konsensus alqoritmi haqqında ümumi fikir
Paxos alqoritmi öz növbəsində hər biri iki addıma bölünən iki böyük mərhələni nəzərdə tutur:
- Mərhələ 1a: Hazırlayın. Hazırlıq mərhələsində lider (təklifçi) bütün qovşaqları məlumatlandırır: “Biz yeni səsvermə mərhələsinə başlayırıq. Yeni turumuz var. Bu turun sayı n-dir. İndi səsverməyə başlayacağıq”. İndiyə qədər o, sadəcə yeni dövrün başlanğıcını bildirir, lakin yeni dəyəri bildirmir. Bu mərhələnin vəzifəsi yeni raund başlamaq və onun unikal nömrəsini hər kəsə bildirməkdir. Dəyirmi nömrə vacibdir, o, bütün əvvəlki liderlərin bütün əvvəlki səsvermə nömrələrindən çox olmalıdır. Dəyirmi nömrə sayəsində sistemdəki digər qovşaqlar liderin məlumatlarının nə qədər təzə olduğunu başa düşəcəklər. Yəqin ki, digər qovşaqlar artıq çox sonrakı turların səsvermə nəticələrinə malikdirlər və sadəcə olaraq liderə zamanın geridə qaldığını söyləyəcəklər.
- Mərhələ 1b: Söz. Akseptor qovşaqları yeni səsvermə mərhələsinin nömrəsini aldıqda, iki nəticə mümkündür:
- Yeni səsin n sayı qəbul edənin iştirak etdiyi əvvəlki səslərin hər hansı birinin sayından çoxdur. Daha sonra qəbul edən liderə n-dən az rəqəmlə daha heç bir səsvermədə iştirak etməyəcəyinə dair söz göndərir. Əgər qəbul edən şəxs artıq bir şeyə səs veribsə (yəni ikinci mərhələdə artıq hansısa dəyəri qəbul edibsə), o zaman qəbul edilmiş dəyəri və iştirak etdiyi səsin sayını vədinə əlavə edir.
- Əks halda, əgər qəbul edən şəxs yüksək səsvermə haqqında artıq bilirsə, o, sadəcə olaraq hazırlıq addımına məhəl qoymayaraq liderə cavab verməyə bilər.
- Mərhələ 2a: Qəbul edin. Lider kvorumdan cavab gözləməlidir (sistemdəki qovşaqların əksəriyyəti) və lazımi sayda cavab alınarsa, hadisələrin inkişafı üçün onun iki variantı var:
- Qəbul edənlərdən bəziləri artıq səs verdikləri dəyərləri təqdim ediblər. Bu zaman lider ən çox səs toplayan səsdən dəyəri seçir. Gəlin bu dəyəri x adlandıraq və bütün qovşaqlara belə bir mesaj göndərək: "Qəbul et (n, x)", burada birinci dəyər öz Təklif addımından səsvermə nömrəsidir, ikinci dəyər isə hər kəsin topladığı şeydir, yəni. əslində səs verdiyimiz dəyər.
- Əgər qəbul edənlərdən heç biri hər hansı dəyər göndərməyibsə, lakin onlar sadəcə olaraq bu turda səs verəcəklərini vəd ediblərsə, lider onları öz dəyərlərinə, ümumiyyətlə lider olduğu dəyərə səs verməyə dəvət edə bilər. Gəlin onu y adlandıraq. Bütün qovşaqlara əvvəlki nəticəyə bənzətməklə "Qəbul et (n, y)" şəklində bir mesaj göndərir.
- Mərhələ 2b: Qəbul edildi. Bundan əlavə, qəbuledici qovşaqlar, rəhbərdən "Qəbul et (...)" mesajını aldıqdan sonra onunla razılaşırlar (bütün qovşaqlara yeni dəyərlə razılaşdıqlarını təsdiqləyirlər) yalnız bəzi (digər) vəd etmədikləri halda. turun nömrəsi ilə səsvermədə iştirak etmək üçün lider n' > nəks halda onlar təsdiq sorğusuna məhəl qoymurlar.
Əgər qovşaqların əksəriyyəti liderə cavab veribsə və onların hamısı yeni dəyəri təsdiqləyibsə, yeni dəyər qəbul edilmiş sayılır. Yaşasın! Əksəriyyət yazılmayıbsa və ya yeni dəyəri qəbul etməkdən imtina edən qovşaqlar varsa, hər şey yenidən başlayır.
Paxos alqoritmi belə işləyir. Bu mərhələlərin hər birinin bir çox incəlikləri var, biz praktiki olaraq müxtəlif növ uğursuzluqları, çoxsaylı liderlərin problemlərini və daha çoxunu nəzərdən keçirmədik, lakin bu məqalənin məqsədi oxucunu yalnız ən yüksək səviyyədə paylanmış hesablama dünyası ilə tanış etməkdir.
Onu da qeyd etmək lazımdır ki, Paxos bu növdə yeganə deyil, başqa alqoritmlər də var, məsələn, , lakin bu başqa məqalənin mövzusudur.
Əlavə tədqiqat üçün materiallara keçidlər
Təcrübə səviyyəsi:
- , Preethi Kasireddy, Medium-da blog məqaləsi
- , Adi Kancherla, Medium-da blog məqaləsi
- Ittai Abraham blogu
- , Ittai Abraham, blog məqaləsi
Leslie Lamport Səviyyəsi:
- Fischer, Lynch və Paterson, tədqiqat məqaləsi, 1985
- , Leslie Lamport, tədqiqat məqaləsi, 1998
- , Leslie Lamport, tədqiqat məqaləsi, 2001
Mənbə: www.habr.com