შრედინგერის კატა ყუთის გარეშე: კონსენსუსის პრობლემა განაწილებულ სისტემებში

ასე რომ, წარმოვიდგინოთ. ოთახში 5 კატაა ჩაკეტილი და პატრონის გასაღვიძებლად ყველა უნდა შეთანხმდნენ ამაზე, რადგან კარის გაღება მხოლოდ ხუთზე დაყრდნობილს შეუძლიათ. თუ ერთ-ერთი კატა შრედინგერის კატაა, ხოლო მეორე კატამ არ იცის მისი გადაწყვეტილების შესახებ, ჩნდება კითხვა: "როგორ შეუძლიათ ამის გაკეთება?"

ამ სტატიაში მე გეტყვით მარტივი სიტყვებით განაწილებული სისტემების სამყაროს თეორიული კომპონენტისა და მათი მუშაობის პრინციპების შესახებ. მე ასევე ზედაპირულად განვიხილავ პაქსოსის ძირითად იდეას.

როდესაც დეველოპერები იყენებენ ღრუბლოვან ინფრასტრუქტურას, სხვადასხვა მონაცემთა ბაზებს და მუშაობენ კვანძების დიდი რაოდენობის კლასტერებში, ისინი დარწმუნებულნი არიან, რომ მონაცემები იქნება სრული, უსაფრთხო და ყოველთვის ხელმისაწვდომი. მაგრამ სად არის გარანტიები?

არსებითად, გარანტიები, რომლებიც ჩვენ გვაქვს, არის მიმწოდებლის გარანტიები. ისინი აღწერილია დოკუმენტაციაში შემდეგნაირად: ”ეს სერვისი საკმაოდ საიმედოა, მას აქვს მოცემული SLA, არ ინერვიულოთ, ყველაფერი იმუშავებს განაწილებულად, როგორც თქვენ მოელით.”

ჩვენ გვჯერა საუკეთესოების, რადგან ჭკვიანი ბიჭები დიდი კომპანიებიდან გვარწმუნებდნენ, რომ ყველაფერი კარგად იქნება. ჩვენ არ ვსვამთ კითხვას: რატომ შეიძლება, სინამდვილეში, ეს საერთოდ იმუშაოს? არსებობს რაიმე ფორმალური გამართლება ასეთი სისტემების სწორად ფუნქციონირებას?

ცოტა ხნის წინ წავედი განაწილებული გამოთვლების სკოლა და ძალიან შთაგონებული იყო ამ თემით. სკოლაში ლექციები უფრო ჰგავდა გაანგარიშების გაკვეთილებს, ვიდრე კომპიუტერულ სისტემებს. მაგრამ ზუსტად ასე დადასტურდა ერთ დროს ყველაზე მნიშვნელოვანი ალგორითმები, რომლებსაც ყოველდღიურად ვიყენებთ, არც კი ვიცით.

თანამედროვე განაწილებული სისტემების უმეტესობა იყენებს პაქსოსის კონსენსუსის ალგორითმს და მის სხვადასხვა მოდიფიკაციას. ყველაზე მაგარი ის არის, რომ ამ ალგორითმის ნამდვილობა და, პრინციპში, არსებობის შესაძლებლობა უბრალოდ კალმით და ქაღალდით შეიძლება დადასტურდეს. პრაქტიკაში, ალგორითმი გამოიყენება დიდ სისტემებში, რომლებიც მუშაობენ ღრუბლებში კვანძების დიდ რაოდენობაზე.

მსუბუქი ილუსტრაცია იმისა, რასაც შემდეგ განვიხილავთ: ორი გენერლის დავალებამოდით შევხედოთ დათბობას ორი გენერლის დავალება.

ჩვენ გვყავს ორი ჯარი - წითელი და თეთრი. ალყაში მოქცეულ ქალაქში თეთრი ჯარები არიან დაფუძნებული. ქალაქის ორ მხარეს განლაგებულია წითელი ჯარები გენერლების A1 და A2 მეთაურობით. წითურების ამოცანაა თეთრ ქალაქზე თავდასხმა და გამარჯვება. თუმცა, თითოეული წითელი გენერლის ჯარი ინდივიდუალურად უფრო მცირეა ვიდრე თეთრი არმია.

წითელებისთვის გამარჯვების პირობები: ორივე გენერალმა ერთდროულად უნდა შეუტიოს, რათა თეთრებზე რიცხობრივი უპირატესობა ჰქონდეს. ამისათვის გენერლები A1 და A2 უნდა შეთანხმდნენ ერთმანეთთან. თუ ყველა ცალ-ცალკე შეუტევს, წითურები წააგებენ.

შეთანხმების მისაღწევად, გენერლებს A1 და A2 შეუძლიათ ერთმანეთს გაუგზავნონ მესინჯერები თეთრი ქალაქის ტერიტორიის გავლით. მესინჯერმა შეიძლება წარმატებით მიაღწიოს მოკავშირეთა გენერალს ან შეიძლება მტერმა დააკავოს. კითხვა: არის თუ არა კომუნიკაციების ისეთი თანმიმდევრობა წითურ გენერლებს შორის (მესინჯერების გაგზავნის თანმიმდევრობა A1-დან A2-მდე და პირიქით A2-დან A1-მდე), რომელშიც გარანტირებული იქნება შეთანხმება შეტევაზე X საათზე. აქ, გარანტიები ნიშნავს, რომ ორივე გენერალს ექნება ცალსახა დადასტურება, რომ მოკავშირე (სხვა გენერალი) აუცილებლად თავს დაესხმება დანიშნულ დროს X.

დავუშვათ, რომ A1 აგზავნის მესინჯერს A2-ზე შეტყობინებით: "მოდით, შეტევა დღეს შუაღამისას!" გენერალი A1 არ შეუძლია შეტევა გენერალ A2-ის დადასტურების გარეშე. თუ მესინჯერი ჩამოვიდა A1-დან, მაშინ გენერალი A2 აგზავნის დადასტურებას მესიჯით: „დიახ, მოდი, დღეს დავხოცოთ თეთრები“. მაგრამ ახლა გენერალმა A2-მა არ იცის, ჩამოვიდა თუ არა მისი მესინჯერი, მას არ აქვს გარანტია, იქნება თუ არა თავდასხმა ერთდროულად. ახლა გენერალ A2-ს კვლავ სჭირდება დადასტურება.

თუ ჩვენ უფრო დეტალურად აღვწერთ მათ კომუნიკაციას, ცხადი ხდება, რომ რამდენიც არ უნდა იყოს შეტყობინებების გაცვლის ციკლი, არ არსებობს გარანტია იმისა, რომ ორივე გენერალმა მიიღო მათი შეტყობინებები (დავარაუდეთ, რომ რომელიმე მესინჯერის ჩაჭრა შესაძლებელია).

ორი გენერალის პრობლემა არის ძალიან მარტივი განაწილებული სისტემის შესანიშნავი ილუსტრაცია, სადაც არის ორი კვანძი არასანდო კომუნიკაციით. ეს ნიშნავს, რომ ჩვენ არ გვაქვს 100% გარანტია, რომ ისინი სინქრონიზებულია. მსგავსი პრობლემები განიხილება მხოლოდ უფრო ფართო მასშტაბით მოგვიანებით სტატიაში.

ჩვენ წარმოგიდგენთ განაწილებული სისტემების კონცეფციას

განაწილებული სისტემა არის კომპიუტერების ჯგუფი (შემდგომში მათ ვუწოდებთ კვანძებს), რომლებსაც შეუძლიათ შეტყობინებების გაცვლა. თითოეული ინდივიდუალური კვანძი არის ერთგვარი ავტონომიური ერთეული. კვანძს შეუძლია დამოუკიდებლად დაამუშაოს ამოცანები, მაგრამ სხვა კვანძებთან კომუნიკაციისთვის საჭიროა შეტყობინებების გაგზავნა და მიღება.

კონკრეტულად როგორ ხდება შეტყობინებების დანერგვა, რა პროტოკოლები გამოიყენება - ეს ჩვენთვის ამ კონტექსტში არ არის საინტერესო. მნიშვნელოვანია, რომ განაწილებული სისტემის კვანძებს შეუძლიათ მონაცემთა გაცვლა ერთმანეთთან შეტყობინებების გაგზავნით.

თავად განმარტება არ გამოიყურება ძალიან რთული, მაგრამ უნდა გავითვალისწინოთ, რომ განაწილებულ სისტემას აქვს მთელი რიგი ატრიბუტები, რომლებიც ჩვენთვის მნიშვნელოვანი იქნება.

განაწილებული სისტემების ატრიბუტები

1. Concurrency - სისტემაში ერთდროული ან ერთდროული მოვლენების შესაძლებლობა. უფრო მეტიც, ჩვენ განვიხილავთ მოვლენებს, რომლებიც ხდება ორ განსხვავებულ კვანძზე, პოტენციურად ერთდროულად, სანამ არ გვაქვს ამ მოვლენების წარმოშობის მკაფიო რიგი. მაგრამ, როგორც წესი, არ გვაქვს.
2. არ არის გლობალური საათი. ჩვენ არ გვაქვს მოვლენების მკაფიო თანმიმდევრობა გლობალური საათის არარსებობის გამო. ადამიანთა ჩვეულებრივ სამყაროში ჩვენ მიჩვეულები ვართ იმ ფაქტს, რომ ჩვენ გვაქვს საათი და დრო აბსოლუტურად. ყველაფერი იცვლება, როდესაც საქმე ეხება განაწილებულ სისტემებს. ულტრაზუსტ ატომურ საათებსაც კი აქვთ დრიფტი და შეიძლება იყოს სიტუაციები, როდესაც ჩვენ ვერ გავიგებთ, ორი მოვლენადან რომელი მოხდა პირველი. შესაბამისად, ჩვენც ვერ ვენდობით დროს.
3. სისტემის კვანძების დამოუკიდებელი მარცხი. არის კიდევ ერთი პრობლემა: რაღაც შეიძლება არასწორედ წარიმართოს მხოლოდ იმიტომ, რომ ჩვენი კვანძები სამუდამოდ არ გრძელდება. მყარი დისკი შეიძლება გაფუჭდეს, ღრუბელში არსებული ვირტუალური მანქანა შეიძლება გადაიტვირთოს, ქსელი შეიძლება ციმციმდეს და შეტყობინებები დაიკარგოს. უფრო მეტიც, შეიძლება იყოს სიტუაციები, როდესაც კვანძები მუშაობენ, მაგრამ ამავე დროს მუშაობენ სისტემის წინააღმდეგ. პრობლემების ბოლო კლასმა ცალკე სახელიც კი მიიღო: პრობლემა ბიზანტიელი გენერლები. ამ პრობლემის მქონე განაწილებული სისტემის ყველაზე პოპულარული მაგალითია ბლოკჩეინი. მაგრამ დღეს ჩვენ არ განვიხილავთ პრობლემების ამ განსაკუთრებულ კლასს. ჩვენ დავინტერესდებით სიტუაციებით, რომლებშიც შეიძლება უბრალოდ ერთი ან მეტი კვანძი ჩავარდეს.
4. კვანძებს შორის კომუნიკაციის მოდელები (შეტყობინებების მოდელები).. ჩვენ უკვე დავადგინეთ, რომ კვანძები ურთიერთობენ შეტყობინებების გაცვლით. არსებობს შეტყობინებების ორი ცნობილი მოდელი: სინქრონული და ასინქრონული.

კვანძებს შორის კომუნიკაციის მოდელები განაწილებულ სისტემებში

სინქრონული მოდელი - ჩვენ ზუსტად ვიცით, რომ არსებობს დროის სასრული ცნობილი დელტა, რომლის დროსაც შეტყობინება გარანტირებულია ერთი კვანძიდან მეორეზე. თუ ეს დრო გავიდა და შეტყობინება არ მოსულა, თამამად შეგვიძლია ვთქვათ, რომ კვანძი ვერ მოხერხდა. ამ მოდელში ჩვენ გვაქვს პროგნოზირებადი ლოდინის დრო.

ასინქრონული მოდელი – ასინქრონულ მოდელებში მიგვაჩნია, რომ ლოდინის დრო სასრულია, მაგრამ არ არსებობს დროის ისეთი დელტა, რის შემდეგაც ჩვენ შეგვიძლია გარანტირებული ვიყოთ, რომ კვანძი ვერ მოხერხდა. იმათ. კვანძიდან შეტყობინების მოლოდინის დრო შეიძლება იყოს თვითნებურად ხანგრძლივი. ეს მნიშვნელოვანი განმარტებაა და ამაზე შემდგომში ვისაუბრებთ.

კონსენსუსის კონცეფცია განაწილებულ სისტემებში

სანამ კონსენსუსის ცნებას ოფიციალურად განვსაზღვრავთ, მოდით განვიხილოთ სიტუაციის მაგალითი, როდესაც ის გვჭირდება, კერძოდ - სახელმწიფო მანქანის რეპლიკაცია.

ჩვენ გვაქვს განაწილებული ჟურნალი. ჩვენ გვინდა, რომ ის იყოს თანმიმდევრული და შეიცავდეს იდენტურ მონაცემებს განაწილებული სისტემის ყველა კვანძზე. როდესაც ერთ-ერთი კვანძი გაიგებს ახალ მნიშვნელობას, რომლის ჩაწერასაც აპირებს ჟურნალში, მისი ამოცანა ხდება ამ მნიშვნელობის შეთავაზება ყველა სხვა კვანძისთვის, რათა ჟურნალი განახლდეს ყველა კვანძზე და სისტემა გადავიდეს ახალ თანმიმდევრულ მდგომარეობაში. ამ შემთხვევაში, მნიშვნელოვანია, რომ კვანძები ერთმანეთს შეთანხმდნენ: ყველა კვანძი თანხმდება, რომ შემოთავაზებული ახალი მნიშვნელობა სწორია, ყველა კვანძი იღებს ამ მნიშვნელობას და მხოლოდ ამ შემთხვევაში შეუძლია ყველას ჩაწეროს ახალი მნიშვნელობა ჟურნალში.

სხვა სიტყვებით რომ ვთქვათ: არცერთი კვანძი არ აპროტესტებდა, რომ მას ჰქონდა უფრო შესაბამისი ინფორმაცია და შემოთავაზებული მნიშვნელობა არასწორი იყო. კვანძებს შორის შეთანხმება და შეთანხმება ერთ სწორ მიღებულ მნიშვნელობაზე არის კონსენსუსი განაწილებულ სისტემაში. შემდეგი, ჩვენ ვისაუბრებთ ალგორითმებზე, რომლებიც საშუალებას აძლევს განაწილებულ სისტემას გარანტირებული იყოს კონსენსუსის მიღწევაში.

უფრო ფორმალურად, შეგვიძლია განვსაზღვროთ კონსენსუსის ალგორითმი (ან უბრალოდ კონსენსუსის ალგორითმი), როგორც გარკვეული ფუნქცია, რომელიც გადასცემს განაწილებულ სისტემას A მდგომარეობიდან B მდგომარეობაში. უფრო მეტიც, ეს მდგომარეობა მიღებულია ყველა კვანძის მიერ და ყველა კვანძს შეუძლია დაადასტუროს იგი. როგორც ირკვევა, ეს ამოცანა სულაც არ არის ისეთი ტრივიალური, როგორც ერთი შეხედვით ჩანს.

კონსენსუსის ალგორითმის თვისებები

კონსენსუსის ალგორითმს უნდა ჰქონდეს სამი თვისება, რათა სისტემამ განაგრძოს არსებობა და ჰქონდეს გარკვეული პროგრესი მდგომარეობიდან მდგომარეობაზე გადასვლისას:

1. შეთანხმება - ყველა სწორად მომუშავე კვანძმა უნდა მიიღოს იგივე მნიშვნელობა (სტატიებში ეს თვისება ასევე მოიხსენიება როგორც უსაფრთხოების თვისება). ყველა კვანძი, რომელიც ამჟამად ფუნქციონირებს (არ დაკარგა ან არ დაკარგა კონტაქტი სხვებთან) უნდა მიაღწიოს შეთანხმებას და მიიღოს საბოლოო საერთო მნიშვნელობა.

   აქ მნიშვნელოვანია გვესმოდეს, რომ ჩვენს მიერ განხილულ განაწილებულ სისტემაში კვანძებს სურთ შეთანხმება. ანუ, ჩვენ ახლა ვსაუბრობთ სისტემებზე, რომლებშიც რაღაც უბრალოდ შეიძლება ჩავარდეს (მაგალითად, ზოგიერთი კვანძი ვერ ხერხდება), მაგრამ ამ სისტემაში ნამდვილად არ არის კვანძები, რომლებიც განზრახ მუშაობენ სხვების წინააღმდეგ (ბიზანტიელი გენერლების ამოცანა). ამ თვისებიდან გამომდინარე, სისტემა რჩება თანმიმდევრული.

2. მთლიანობის აღდგენის - თუ ყველა სწორად მომუშავე კვანძი ერთსა და იმავე მნიშვნელობას გვთავაზობს v, რაც ნიშნავს, რომ ყველა სწორად მომუშავე კვანძმა უნდა მიიღოს ეს მნიშვნელობა v.
3. შეწყვეტა – ყველა სწორად მოქმედი კვანძი საბოლოოდ მიიღებს გარკვეულ მნიშვნელობას (სიცოცხლის თვისება), რაც ალგორითმს აძლევს სისტემაში პროგრესის საშუალებას. თითოეულმა ინდივიდუალურმა სწორად მოქმედმა კვანძმა ადრე თუ გვიან უნდა მიიღოს საბოლოო მნიშვნელობა და დაადასტუროს იგი: „ჩემთვის ეს მნიშვნელობა მართალია, მე ვეთანხმები მთელ სისტემას“.

მაგალითი იმისა, თუ როგორ მუშაობს კონსენსუსის ალგორითმი

მიუხედავად იმისა, რომ ალგორითმის თვისებები შეიძლება არ იყოს სრულიად ნათელი. მაშასადამე, ჩვენ მაგალითით განვმარტავთ, რა ეტაპებს გადის უმარტივესი კონსენსუსის ალგორითმი სისტემაში სინქრონული შეტყობინებების მოდელით, რომელშიც ყველა კვანძი ფუნქციონირებს ისე, როგორც მოსალოდნელია, შეტყობინებები არ იკარგება და არაფერი იშლება (ეს მართლა ხდება?).

1. ყველაფერი იწყება ქორწინების წინადადებით (Propose). დავუშვათ, რომ კლიენტი დაუკავშირდა კვანძს სახელწოდებით "Node 1" და დაიწყო ტრანზაქცია, გადასცა კვანძს ახალი მნიშვნელობა - O. ამიერიდან ჩვენ მოვუწოდებთ "Node 1"-ს. შეთავაზება. როგორც შემოთავაზებულმა, „Node 1“-მა ახლა უნდა აცნობოს მთელ სისტემას, რომ მას აქვს ახალი მონაცემები და აგზავნის შეტყობინებებს ყველა სხვა კვანძზე: „ნახე! მნიშვნელობა „ო“ მომივიდა და მინდა დავწერო! გთხოვთ, დაადასტუროთ, რომ თქვენ ასევე ჩაიწერთ "O"-ს თქვენს ჟურნალში."

   

2. შემდეგი ეტაპი არის შემოთავაზებული მნიშვნელობის კენჭისყრა (Voting). Რისთვის არის? შეიძლება მოხდეს, რომ სხვა კვანძებმა მიიღეს უახლესი ინფორმაცია და მათ აქვთ მონაცემები იმავე ტრანზაქციის შესახებ.

   
   
   როდესაც კვანძი „Node 1“ აგზავნის თავის შეთავაზებას, სხვა კვანძები ამოწმებენ თავიანთ ჟურნალებს ამ მოვლენის შესახებ მონაცემებისთვის. თუ წინააღმდეგობები არ არის, კვანძები აცხადებენ: ”დიახ, მე არ მაქვს სხვა მონაცემები ამ მოვლენისთვის. "O" მნიშვნელობა არის უახლესი ინფორმაცია, რომელსაც ჩვენ ვიმსახურებთ."

   ნებისმიერ სხვა შემთხვევაში, კვანძებს შეუძლიათ უპასუხონ „Node 1“-ს: „მოისმინე! მე მაქვს უახლესი მონაცემები ამ ტრანზაქციის შესახებ. არა "ო", არამედ რაღაც უკეთესი."

   ხმის მიცემის ეტაპზე კვანძები მიიღებენ გადაწყვეტილებას: ან ყველა ეთანხმება ერთსა და იმავე მნიშვნელობას, ან ერთ-ერთი მათგანი ხმას აძლევს წინააღმდეგ, რაც მიუთითებს იმაზე, რომ მას აქვს უახლესი მონაცემები.

3. თუ ხმის მიცემის რაუნდი წარმატებული იყო და ყველა მომხრე იყო, მაშინ სისტემა გადადის ახალ ეტაპზე - ღირებულების მიღებაზე. "Node 1" აგროვებს ყველა პასუხს სხვა კვანძებიდან და აცნობებს: "ყველა შეთანხმდა "O" მნიშვნელობაზე! ახლა მე ოფიციალურად ვაცხადებ, რომ "O" არის ჩვენი ახალი მნიშვნელობა, იგივე ყველასთვის! ჩაწერეთ ეს თქვენს პატარა წიგნში, არ დაგავიწყდეთ. ჩაწერეთ ეს თქვენს ჟურნალში!”

   

4. დარჩენილი კვანძები აგზავნიან დადასტურებას (მიღებულია), რომ მათ ჩაწერეს მნიშვნელობა "O"; ამ დროის განმავლობაში არაფერი ახალი არ მოსულა (ერთგვარი ორფაზიანი ჩაბარება). ამ მნიშვნელოვანი მოვლენის შემდეგ მიგვაჩნია, რომ განაწილებული ტრანზაქცია დასრულებულია.
   

ამრიგად, კონსენსუსის ალგორითმი მარტივ შემთხვევაში შედგება ოთხი საფეხურისაგან: შეთავაზება, ხმის მიცემა (კენჭისყრა), მიღება (მიღება), მიღების დადასტურება (მიღებული).

თუ რაღაც ეტაპზე ვერ მივაღწიეთ შეთანხმებას, მაშინ ალგორითმი ხელახლა იწყება, იმ კვანძების მიერ მოწოდებული ინფორმაციის გათვალისწინებით, რომლებმაც უარი განაცხადეს შემოთავაზებული მნიშვნელობის დადასტურებაზე.

კონსენსუსის ალგორითმი ასინქრონულ სისტემაში

მანამდე ყველაფერი გამართულად იყო, რადგან სინქრონული შეტყობინებების მოდელზე ვსაუბრობდით. მაგრამ ჩვენ ვიცით, რომ თანამედროვე სამყაროში ჩვენ მიჩვეული ვართ ყველაფრის ასინქრონულად კეთებას. როგორ მუშაობს მსგავსი ალგორითმი ასინქრონული შეტყობინებების მოდელის სისტემაში, სადაც მიგვაჩნია, რომ კვანძიდან პასუხის მოლოდინის დრო შეიძლება იყოს თვითნებურად დიდი (სხვათა შორის, კვანძის უკმარისობა ასევე შეიძლება ჩაითვალოს მაგალითად, როდესაც კვანძს შეუძლია თვითნებურად დიდი ხნის განმავლობაში რეაგირება).

ახლა, როდესაც ჩვენ ვიცით, როგორ მუშაობს კონსენსუსის ალგორითმი პრინციპში, კითხვაა იმ ცნობისმოყვარე მკითხველისთვის, ვინც აქამდე მიაღწია: რამდენი კვანძი N კვანძების სისტემაში ასინქრონული შეტყობინების მოდელით შეიძლება ჩავარდეს ისე, რომ სისტემამ მაინც მიაღწიოს კონსენსუსს?

სწორი პასუხი და დასაბუთება დგას სპოილერის უკან.სწორი პასუხია: 0. თუ ასინქრონულ სისტემაში ერთი კვანძიც კი ჩაიშლება, სისტემა ვერ შეძლებს კონსენსუსს. ეს განცხადება დადასტურებულია FLP თეორემაში, რომელიც კარგად არის ცნობილი გარკვეულ წრეებში (1985, Fischer, Lynch, Paterson, ბმული ორიგინალთან სტატიის ბოლოს): „განაწილებული კონსენსუსის მიღწევის შეუძლებლობა, თუ ერთი კვანძი მაინც ვერ ხერხდება. .”

ბიჭებო, მაშინ პრობლემა გვაქვს, მიჩვეული ვართ ყველაფერი ასინქრონულად იყოს. და აი ეს არის. როგორ გავაგრძელო ცხოვრება?

ჩვენ მხოლოდ თეორიაზე ვსაუბრობდით, მათემატიკაზე. რას ნიშნავს „კონსენსუსის მიღწევა შეუძლებელია“ მათემატიკური ენიდან ჩვენს ენაზე - ინჟინერიაში თარგმნისას? ეს ნიშნავს, რომ „ყოველთვის ვერ მიიღწევა“, ე.ი. არის შემთხვევა, როცა კონსენსუსი ვერ მიიღწევა. ეს რა შემთხვევაა?

ეს არის ზუსტად ზემოთ აღწერილი სიცოცხლისუნარიანობის დარღვევა. ჩვენ არ გვაქვს საერთო შეთანხმება და სისტემას არ შეუძლია ჰქონდეს პროგრესი (ვერ სრულდება სასრულ დროში) იმ შემთხვევაში, როდესაც ჩვენ არ გვაქვს პასუხი ყველა კვანძიდან. იმის გამო, რომ ასინქრონულ სისტემაში ჩვენ არ გვაქვს პროგნოზირებადი რეაგირების დრო და ჩვენ არ შეგვიძლია ვიცოდეთ, კვანძი გაფუჭდა თუ უბრალოდ დიდი დრო სჭირდება რეაგირებას.

მაგრამ პრაქტიკაში ჩვენ შეგვიძლია ვიპოვოთ გამოსავალი. დაე, ჩვენმა ალგორითმმა შეძლოს დიდი ხნის განმავლობაში მუშაობა წარუმატებლობის შემთხვევაში (პოტენციურად მას შეუძლია განუსაზღვრელი ვადით იმუშაოს). მაგრამ უმეტეს სიტუაციებში, როდესაც კვანძების უმეტესობა სწორად ფუნქციონირებს, ჩვენ გვექნება პროგრესი სისტემაში.

პრაქტიკაში საქმე გვაქვს ნაწილობრივ სინქრონულ კომუნიკაციის მოდელებთან. ნაწილობრივი სინქრონიზაცია ასე იგულისხმება: ზოგადად, ჩვენ გვაქვს ასინქრონული მოდელი, მაგრამ ფორმალურად არის შემოღებული დროის გარკვეული პერიოდის "გლობალური სტაბილიზაციის დროის" გარკვეული კონცეფცია.

დროში ეს მომენტი შეიძლება დიდი ხნის განმავლობაში არ დადგეს, მაგრამ ის ერთ დღეს უნდა დადგეს. ვირტუალური მაღვიძარა დარეკავს და ამ მომენტიდან ჩვენ შეგვიძლია ვიწინასწარმეტყველოთ დროის დელტა, რომლისთვისაც მოვა შეტყობინებები. ამ მომენტიდან სისტემა ასინქრონულიდან სინქრონულში გადადის. პრაქტიკაში სწორედ ასეთ სისტემებთან გვაქვს საქმე.

პაქსოსის ალგორითმი წყვეტს კონსენსუსის პრობლემებს

პაქსი არის ალგორითმების ოჯახი, რომელიც წყვეტს კონსენსუსის პრობლემას ნაწილობრივ სინქრონული სისტემებისთვის, ზოგიერთი კვანძის ჩავარდნის შესაძლებლობის გათვალისწინებით. პაქსოსის ავტორია ლესლი ლამპორტი. მან შესთავაზა ალგორითმის არსებობისა და სისწორის ოფიციალური მტკიცებულება 1989 წელს.

მაგრამ მტკიცებულება შორს იყო ტრივიალურისგან. პირველი პუბლიკაცია გამოიცა მხოლოდ 1998 წელს (33 გვერდი), სადაც აღწერილია ალგორითმი. როგორც აღმოჩნდა, უკიდურესად რთული გასაგები იყო და 2001 წელს გამოქვეყნდა სტატიის განმარტება, რომელსაც 14 გვერდი დასჭირდა. პუბლიკაციების მოცულობა მოცემულია იმისთვის, რომ აჩვენოს, რომ სინამდვილეში კონსენსუსის პრობლემა სულაც არ არის მარტივი და ასეთი ალგორითმების მიღმა იმალება ყველაზე ჭკვიანი ადამიანების დიდი სამუშაო.

საინტერესოა, რომ თავად ლესლი ლამპორტმა თავის ლექციაში აღნიშნა, რომ მეორე განმარტებით სტატიაში არის ერთი დებულება, ერთი სტრიქონი (მას არ დაუკონკრეტებია რომელი), რომელიც შეიძლება სხვადასხვაგვარად იქნას განმარტებული. და ამის გამო, თანამედროვე Paxos-ის იმპლემენტაციის დიდი რაოდენობა მთლად სწორად არ მუშაობს.

პაქსოსის მუშაობის დეტალური ანალიზი დასჭირდება ერთზე მეტ სტატიას, ამიტომ შევეცდები ძალიან მოკლედ გადმოგცეთ ალგორითმის მთავარი იდეა. ჩემი სტატიის ბოლოს მოცემულ ბმულებზე ნახავთ მასალებს ამ თემის შემდგომი ჩაძირვისთვის.

როლები პაქსოსში

პაქსოსის ალგორითმს აქვს როლების კონცეფცია. მოდით განვიხილოთ სამი მთავარი (არსებობს ცვლილებები დამატებითი როლებით):

1. წინადადებები (ტერმინები ასევე შეიძლება გამოყენებულ იქნას: ლიდერები ან კოორდინატორები). ეს ის ბიჭები არიან, რომლებიც მომხმარებლისგან იგებენ რაღაც ახალ ღირებულებას და იღებენ ლიდერის როლს. მათი ამოცანაა წამოიწყონ წინადადებების რაუნდი ახალი მნიშვნელობისთვის და კოორდინაცია გაუწიონ კვანძების შემდგომ მოქმედებებს. უფრო მეტიც, პაქსოსი გარკვეულ სიტუაციებში რამდენიმე ლიდერის არსებობის საშუალებას იძლევა.
2. მიმღებები (ამომრჩევლები). ეს არის კვანძები, რომლებიც ხმას აძლევენ კონკრეტული მნიშვნელობის მიღებას ან უარყოფას. მათი როლი ძალზე მნიშვნელოვანია, რადგან გადაწყვეტილება მათზეა დამოკიდებული: რა მდგომარეობაში წავა (ან არა) სისტემა კონსენსუსის ალგორითმის შემდეგი ეტაპის შემდეგ.
3. მოსწავლეთა. კვანძები, რომლებიც უბრალოდ იღებენ და წერენ ახალ მიღებულ მნიშვნელობას, როდესაც სისტემის მდგომარეობა შეიცვალა. ისინი არ იღებენ გადაწყვეტილებებს, ისინი უბრალოდ იღებენ მონაცემებს და შეუძლიათ საბოლოო მომხმარებლისთვის გადაცემა.

ერთ კვანძს შეუძლია გააერთიანოს რამდენიმე როლი სხვადასხვა სიტუაციაში.

კვორუმის ცნება

ჩვენ ვვარაუდობთ, რომ გვაქვს სისტემა N კვანძები და მათგან მაქსიმუმი F კვანძები შეიძლება ჩავარდეს. თუ F კვანძები ჩავარდება, მაშინ მაინც უნდა გვქონდეს 2F+1 მიმღები კვანძები.

ეს აუცილებელია იმისათვის, რომ ჩვენ ყოველთვის გვქონდეს უმეტესობა, თუნდაც ყველაზე ცუდ სიტუაციაში, "კარგი" კვანძების, რომლებიც სწორად მუშაობენ. ანუ F+1 "კარგი" კვანძები, რომლებიც შეთანხმდნენ და საბოლოო მნიშვნელობა მიიღება. წინააღმდეგ შემთხვევაში, შეიძლება შეიქმნას სიტუაცია, როდესაც ჩვენი სხვადასხვა ადგილობრივი ჯგუფები სხვადასხვა მნიშვნელობას იძენენ და ვერ შეთანხმდებიან ერთმანეთთან. ამიტომ ხმების მოსაპოვებლად გვჭირდება აბსოლუტური უმრავლესობა.

ზოგადი იდეა იმის შესახებ, თუ როგორ მუშაობს პაქსოსის კონსენსუსის ალგორითმი

პაქსოსის ალგორითმი მოიცავს ორ დიდ ფაზას, რომლებიც თავის მხრივ იყოფა ორ საფეხურად:

1. ფაზა 1a: მომზადება. მომზადების ფაზაში ლიდერი (განმცხადებელი) აცნობებს ყველა კვანძს: „ვიწყებთ ხმის მიცემის ახალ ფაზას. ახალი ტური გვაქვს. ამ რაუნდის რიცხვია n. ახლა ჩვენ დავიწყებთ კენჭისყრას“. ამ დროისთვის ის უბრალოდ აცნობებს ახალი ციკლის დაწყებას, მაგრამ არ აცნობებს ახალ მნიშვნელობას. ამ ეტაპის ამოცანაა ახალი რაუნდის წამოწყება და მისი უნიკალური ნომრის შესახებ ყველას ინფორმირება. რაუნდის რიცხვი მნიშვნელოვანია, ის უნდა იყოს უფრო დიდი მნიშვნელობა, ვიდრე ყველა წინა ხმის მიცემის ნომერი ყველა წინა ლიდერისგან. იმის გამო, რომ მრგვალი ნომრის წყალობით, სისტემის სხვა კვანძები გაიგებენ, რამდენად ახალია ლიდერის მონაცემები. სავარაუდოა, რომ სხვა კვანძებს უკვე აქვთ ხმის მიცემის შედეგები გაცილებით გვიან რაუნდებიდან და უბრალოდ ეტყვიან ლიდერს, რომ ის ჩამორჩება დროს.
2. ფაზა 1b: დაპირება. როდესაც მიმღებმა კვანძებმა მიიღეს ხმის მიცემის ახალი ეტაპის ნომერი, შესაძლებელია ორი შედეგი:
   • ახალი ხმის n რიცხვი მეტია ნებისმიერი წინა ხმის რაოდენობაზე, რომელშიც მიმღები მონაწილეობდა. შემდეგ მიმღები პირობას უგზავნის ლიდერს, რომ ის აღარ მიიღებს მონაწილეობას n-ზე დაბალი რიცხვით კენჭისყრაში. თუ მიმღებმა უკვე მისცა ხმა რაღაცას (ანუ მეორე ფაზაში მან უკვე მიიღო გარკვეული მნიშვნელობა), მაშინ ის მიღებულ მნიშვნელობას და იმ ხმების რაოდენობას ანიჭებს თავის დაპირებას.
   • წინააღმდეგ შემთხვევაში, თუ მიმღებმა უკვე იცის უფრო მაღალი ნომრის შესახებ ხმების შესახებ, მას შეუძლია უბრალოდ უგულებელყოს მოსამზადებელი ეტაპი და არ უპასუხოს ლიდერს.
3. ფაზა 2a: მიღება. ლიდერი უნდა დაელოდოს პასუხს კვორუმისგან (სისტემის კვანძების უმრავლესობა) და, თუ მიღებული პასუხების საჭირო რაოდენობა, მას აქვს მოვლენების განვითარების ორი ვარიანტი:
   • ზოგიერთმა მიმღებმა გაგზავნა მნიშვნელობები, რომლებსაც უკვე მისცეს ხმა. ამ შემთხვევაში ლიდერი ირჩევს მნიშვნელობას ხმებიდან მაქსიმალური რაოდენობით. მოდით ვუწოდოთ ამ მნიშვნელობას x და ის უგზავნის შეტყობინებას ყველა კვანძს, როგორიცაა: „მიიღე (n, x)“, სადაც პირველი მნიშვნელობა არის ხმის მიცემის ნომერი მისი საკუთარი შეთავაზების ნაბიჯიდან, ხოლო მეორე მნიშვნელობა არის ის, რისთვისაც შეიკრიბა ყველა, ე.ი. ღირებულება, რომელსაც ჩვენ რეალურად ვაძლევთ ხმას.
   • თუ არცერთ მიმღებს არ გაუგზავნია რაიმე მნიშვნელობა, მაგრამ მათ უბრალოდ დაჰპირდნენ ხმის მიცემას ამ რაუნდში, ლიდერს შეუძლია მოიწვიოს ისინი ხმის მისაცემად მათი ღირებულებისთვის, ღირებულებისთვის, რისთვისაც იგი გახდა ლიდერი პირველ რიგში. მოდით დავარქვათ y. ის აგზავნის შეტყობინებას ყველა კვანძს, როგორიცაა: "მიღება (n, y)", წინა შედეგის მსგავსად.
4. ფაზა 2b: მიღებულია. გარდა ამისა, მიმღები კვანძები, როდესაც მიიღებენ "მიღება(...)" შეტყობინებას ლიდერისგან, ეთანხმებიან მას (გაუგზავნეთ დადასტურება ყველა კვანძს, რომ ისინი ეთანხმებიან ახალ მნიშვნელობას) მხოლოდ იმ შემთხვევაში, თუ ისინი არ დაჰპირდნენ ზოგიერთს (სხვას) ) ლიდერი კენჭისყრაში მონაწილეობას მრგვალი ნომრით n' > n, წინააღმდეგ შემთხვევაში ისინი უგულებელყოფენ დადასტურების მოთხოვნას.

   თუ კვანძების უმრავლესობამ უპასუხა ლიდერს და ყველამ დაადასტურა ახალი მნიშვნელობა, მაშინ ახალი მნიშვნელობა მიღებულად ითვლება. ჰოო! თუ უმრავლესობა არ არის მიღწეული ან არის კვანძები, რომლებმაც უარი თქვეს ახალი მნიშვნელობის მიღებაზე, მაშინ ყველაფერი თავიდან იწყება.

ასე მუშაობს პაქსოსის ალგორითმი. თითოეულ ამ ეტაპს აქვს მრავალი დახვეწილობა, ჩვენ პრაქტიკულად არ განვიხილეთ სხვადასხვა სახის წარუმატებლობები, მრავალი ლიდერის პრობლემები და მრავალი სხვა, მაგრამ ამ სტატიის მიზანია მხოლოდ მკითხველს გააცნოს განაწილებული გამოთვლის სამყარო მაღალ დონეზე.

აღსანიშნავია ისიც, რომ პაქსოსი არ არის ერთადერთი ასეთი, არსებობს სხვა ალგორითმები, მაგალითად, რაფტინგი, მაგრამ ეს სხვა სტატიის თემაა.

მასალების ბმულები შემდგომი შესწავლისთვის

დამწყები დონე:

• როგორ მუშაობს განაწილებული კონსენსუსი?, Preethi Kasireddy, ბლოგის სტატია Medium-ზე
• Paxos დამზადებული მარტივი. Დანამდვილებით, ადი კანჩერლა, ბლოგის სტატია მედიუმზე
• დეცენტრალიზებული აზრები, Ittai Abraham, ბლოგი
• სინქრონული, ასინქრონული და ნაწილობრივი სინქრონიზაცია, Ittai Abraham, ბლოგის სტატია

ლესლი ლამპორტის დონე:

• განაწილებული კონსენსუსის შეუძლებლობა ერთი გაუმართავი პროცესით (FLP შეუძლებლობა)ფიშერი, ლინჩი და პატერსონი, კვლევითი ნაშრომი, 1985 წ
• ნახევარ განაკვეთზე პარლამენტილესლი ლამპორტი, კვლევითი ნაშრომი, 1998 წ
• Paxos დამზადებული მარტივილესლი ლამპორტი, კვლევითი ნაშრომი, 2001 წ

წყარო: www.habr.com