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

1) რა არის კონსენსუსი და რატომ არის ეს საჭირო

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

• კონსენსუსი (SMR): ბრძანებების ერთიანი სრული რიგი, ხაზოვანი საცავი/რეესტრი, კლასტერის მეტამონაცემები, გარიგების კოორდინატორები.
• კვორუმის ოპერაციები ტოტალური წესრიგის გარეშე (Dynamo მსგავსი, CRDT): დაიშვება დივერგენცია და შემდგომი შერწყმა; ისინი არ შეცვლიან კონსენსუსს, სადაც საჭიროა გლობალური სერიალიზაცია.

2) დროისა და უარის თქმის მოდელი

2. 1 დროის მოდელი

ასინქრონული ქსელი: შეფერხებები შეუზღუდავია; FLP თეორემა შეუძლებელია უსაფრთხოებისა და ცხოვრების გარანტია დამატებითი ვარაუდების გარეშე.
ნაწილობრივ სინქრონიზებული (ხშირად პრაქტიკაში): უცნობი T სისტემის შემდეგ, სისტემა „იქცევა“ სინქრონულად - ალგორითმების უმეტესობა (რაფტი, პაქსოსი) ამას ეყრდნობა.
სინქრონული: მყარი დროის ლიმიტები არხებზე (იშვიათად გაყიდვაში, გარდა სპეციალური ქსელებისა/PTP).

2. 2 უარის თქმის მოდელი

Crash-fault tolerant (CFT): კვანძები შეიძლება დაეცეს/ჩამოიხრჩო, მაგრამ არ იქცევიან მავნე.
Byzantine-fault tolerant (BFT): კვანძებს შეუძლიათ მოტყუება/გაყალბება შეტყობინებები. ბიზანტიური ტოლერანტობისთვის საჭიროა 3f + 1 კვანძი.

3) კონსენსუსის თვისებები

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

4) კვორუმი, უმეტესობა და კვეთა

CFT სამყაროში კლასიკა: კვორუმი> N/2. ლიდერის ჩანაწერები და არჩევნები იყენებენ კვორუმის კვეთას, ამიტომ ორი „მოქმედი“ ოპერაცია არ ეწინააღმდეგება.
BFT სამყაროში: კვორუმები 2f + 1 - დან 3f + 1 - დან უზრუნველყოფს მინიმუმ f + 1 გულწრფელი კვანძების კვეთას.

კვეთა წესი: ნებისმიერ ორ კვორუმს უნდა ჰქონდეს 1 საერთო გულწრფელი კვანძი (CFT) ან f + 1 (BFT).

5) სახელმწიფოს რეპლიკაცია (ჟურნალი + გამოყენება)

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

6) ლიდერული და არაწრფივი სქემები

ლიდერი (Raft, Multi-Paxos, ZAB): ერთი ლიდერი სერიალებს უწევს ჩანაწერებს, უფრო ადვილია გონებრივად და ოპერატიულად, უკეთესია სტაბილური ლიდერის ლატენტობა.
შეუზღუდავი/ანიმაციური (EPaxos, Caesar): უფრო პარალელიზმი და ლიდერის ტოლერანტობა, მაგრამ განხორციელება და კონფლიქტი-გადაწყვეტა უფრო რთულია; მოგება ჩანს გუნდების მცირე კონფლიქტებში.

7) კლასიკური CFT ალგორითმები

7. 1 Paxos/Multi-Paxos (და პრაქტიკა)

იდეა: ორი ეტაპი (prepare/propose), მიმღების დაპირებები, უმრავლესობის კვორუმი. Multi-Paxos ტოვებს „სტაბილურ ლიდერს“ და ოპერაციებს ერთ რაუნდად აქცევს (ახალი ჩანაწერებისთვის) „დათბობის“ შემდეგ.

• მოქნილი, მაგრამ რთული მოდელი განსახორციელებლად.
• R- კონფიგურაცია სპეციალური ჩანაწერების საშუალებით (joint consensus).
• პრაქტიკაში - ბიბლიოთეკები/ძრავები (Chubby/Spanner თაობა).

7. 2 Raft

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

Election: შემთხვევითი ტაიმაუტები, ხმის მიცემა ტერმინებზე; ერთი ლიდერი დროულად.
AppendEntries: ლიდერი წერს ჩანაწერს, აკონტროლებს პრეფიქსი (ინდექსი/თერმი), კომუნას უმრავლესობის ფიქსაციაში.
Read-path: lease-reads (ძლიერი ლიდერის ქვეშ) ან read-index ხაზოვანი კითხვებისთვის.
Reconfig: „ერთობლივი კონფიგურაცია“ (joint) - კვანძები ხმას იღებენ ორ მტევანში გადასვლამდე.

დადებითი: უფრო ადვილია განვითარება/რბოლა, ძლიერი რიგის ინვარიანტები. უარყოფითი: ლიდერი - წნევის წერტილი.

7. 3 ZAB (ZooKeeper Atomic Broadcast) / Viewstamped Replication (VRR)

ZAB: ლიდერი ავრცელებს გარიგებებს, აღდგენის ფაზას, zxid (ერა + ინდექსი).
VRR: „სახეობები“ (views) პირველადი რეპლიკით, მსგავსია სულისკვეთებით Multi-Paxos.

8) არაწრფივი/ანიმაციური CFT

8. 1 EPaxos

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

8. 2 Caesar, Mencius

ვარიაციები, რომლებიც ოპტიმიზაციას ახდენენ შეფერხებებს/დაბალანსებას და მუშაობას WAN- ში.

9) BFT ალგორითმები და PoS ოჯახი

9. 1 PBFT (Practical BFT)

სამი ფაზა (pre-prepare/prepare/commit), მოითხოვს 3f + 1 კვანძს.
დაბალი ლატენტობა ადგილობრივ ქსელებზე, მრავალსაფეხურიანი გზები და O (N ²) შეტყობინებები.

9. 2 Tendermint (BFT-PoS სტილი)

რაუნდი პრო-ფოსტით და ორი ხმით (prevote/precommit).
დეტერმინის დამადასტურებელი, დროული, ნაწილობრივი სინქრონიზაცია.
კარგია Permissioned/PoS ქსელებისთვის ათეულობით/ასეული წამყვანით.

9. 3 HotStuff (და წარმოებულები)

სამფაზიანი სქემა გაერთიანებულია „პაკეტებში“ კვორუმის სერთიფიკატებით (QC).
კომუნიკაციების ხაზოვანი სირთულე, პაკეტის მხარდაჭერა და პარალელური დალაგება მოსახერხებელია ბლოკჩეინებში განხორციელებისთვის (მაგალითად, Diem/Move ეკოსისტემა).
ბარიერი ხელმოწერებით (threshold signatures) ტრეფიკი მცირდება.

9. 4 PoW/დაფინანსებული კონსენსუსი (მოკლედ)

არა BFT მკაცრი გაგებით, არამედ სავარაუდო კონვერგენცია (ჯაჭვი ყველაზე მაღალი შრომით). უპირატესობები: სიმარტივე/ღიაობა; ნაკლოვანებები: ენერგია, ~ წამი-წუთი დასრულებამდე.

10) კითხვები: ხაზოვანი, თანმიმდევრული და ქეშირებული

ხაზოვანი კითხვები: ლიდერი აქტიური lease ან Raad index- ის საშუალებით (Raft) არის დადასტურება კვორუმის საშუალებით.
თანმიმდევრული: შეგიძლიათ წაიკითხოთ ნებისმიერი კვანძიდან, მაგრამ სიახლის გარანტიების გარეშე.
Follower reads: დასაშვებია სუსტი მოთხოვნებით; კეშისთვის - კარგი.

11) Re- კონფიგურაცია (კლასტერის შემადგენლობის შეცვლა)

მას სჭირდება ორი გადახურვის კონფიგურაცია (joint consensus): ნებისმიერი კომუნა გადის ორივე კონფიგურაციის კვორუმებს - „ხვრელების“ გარეშე.
დაამატეთ/ამოიღეთ ერთი, დააკვირდით კვორუმის ზომას.
ლიდერობის გადაცემა (leadership transfer) ამცირებს პაუზებს.

12) პროდუქტიულობა და ტიუნინგი

12. 1 შეფერხებები

ლიდერობის ალგორითმები: 1 RTT თითო ჩანაწერი (სტაბილური ლიდერის ქვეშ) + რეპლიკაცია.
განაწილება: WAN RTT დომინირებს - გამოიყენეთ ადგილობრივი რეგიონები + ჯვარედინი რეპლიკაცია ან EPaxos/HotStuff მიდგომები.

12. 2 გამშვები

Batching (გუნდური ჯგუფი), პარალელურად AppendEntries, ჟურნალის პეიჯის ქეში, პარალელური გამოყენება (როდესაც ოპერაციები გადის).
დისკები: NVMe/ჟურნალი ცალკეულ მოწყობილობაზე, 'O _ DIRECT '/AIO, დიდი' fsync '- ინტერვაცია SLA- ს შეზღუდვებით (კომპრომისი durability/latence).

12. 3 კუდები p99

თავიდან აიცილეთ ცხელი კვანძები (ლიდერი მუდმივად ერთია): პერიოდული როტაცია ან read-offload მიმდევრებზე.
აკონტროლეთ GC პაუზები (JVM/Go), CPU, NUMA ქაფები.

13) გეოგრაფია და ტოპოლოგია

1 რეგიონი, 3 ზონა: კლასიკური CFT კასეტა (N = 3/5).
2 რეგიონი: მოერიდეთ - არ მუშაობს საიმედო კვორუმი 1-1 გაყოფისას.
3 + რეგიონები: ლიდერი „შუაში“ ან შეუზღუდავი ალგორითმები; შესაძლებელია რეგიონალური მარიონეტული/ადგილობრივი ფრონტები ასინქრონული ჟურნალით.

14) პრაქტიკული ოპერაცია

14. 1 Snaphots და აღდგენა

ბარიერი ჟურნალის ზომით/ოპერაციების რაოდენობა.
Snapshot- ის გადაცემა ახალ კვანძებზე; ტესტის თანხების შემოწმება.

14. 2 მონიტორინგი

ლიდერობა: ვინ არის ლიდერი, რამდენი ვადა (term/epoch) შეიცვალა.
Лаги: `append_latency`, `commit_index - applied_index`.

კვორუმის ჯანმრთელობა: „ცოცხალია უმრავლესობა/2f + 1?“

ჟურნალის ზომა/კომპაქტური სიჩქარე, Snaphots- ის ხაზი.
BFT- სთვის: ხმების წილი, ხელმოწერილი ხელმოწერები, QC შეფერხებები.

14. 3 უსაფრთხოება/კოდის შესაბამისობა

ოქმის ვერსია მავთულზე, მიგრაცია ჟურნალების თავსებადობასთან.
Fencing ნიშნები გარე ეფექტებზე (იხ. „განაწილებული ბლოკები“): ლიდერობის ვადა (term) გადაეცემა CRON/joba- ს.

15) ანტი შაბლონები

კონსენსუსის დადება „მოდის გულისთვის“ იქ, სადაც საკმარისია ერთი DBMS ან კვორუმის კითხვა სერიალიზაციის გარეშე.
შერეული CP და AP მკაფიო საზღვრების გარეშე (CAP) არის არაპროგნოზირებადი UX.
გადაჭარბებული PoW/PoS კორპორატიული დავალებებისთვის ათობით კვანძით (რთული/ძვირი).
უგულებელყოს R- კონფიგურაცია და „კვეთა კვორუმი“ კომპოზიციის შეცვლისას.
Read-barrier- ის (lease/read-index) არარსებობა არის „ბინძური“ კითხვა.
დაიწყეთ 2-კვანძოვანი მტევანი (უმრავლესობა არ არის).
დისკების და fsync- ის დაქვეითება: „ყველაფერი დაფრინავს მეხსიერებაში“ - პირველ გადატვირთვამდე.

16) შერჩევის სია

1. უარის თქმის მოდელი: CFT (კრაშები) ან BFT (მავნე)?
2. გეოგრაფია: ერთი რეგიონი/სამი ზონა თუ WAN? RTT გადაწყვეტს.
3. კითხვის სემანტიკა: საჭიროა ხაზოვანი კითხვა? Lease/read-index/ფოლკლორული რიდები.
4. დატვირთვა: მოლოდინი p50/p99, throughput; საჭიროა მულტფილმის ხელმძღვანელობა.
5. ოპერაციული სირთულე: ბიბლიოთეკა/მზა ძრავა (etcd/ZK/Consul/Raft-libs) საკუთარი განხორციელება.
6. რეკონსტრუქცია: ხშირი? ჩვენ გვჭირდება joint consensus და მიგრაციის ინსტრუმენტები.
7. ინტეგრაცია: გარე გვერდითი მოვლენები - არის თუ არა ფოკუსირება ეპოკის/ტერმზე?
8. უსაფრთხოება: კვანძების ავთენტიფიკაცია, არხის დაშიფვრა, პროტოკოლის ვერსიების კონტროლი.
9. ტესტის ფლეიბუკები: წვეულება, GC-stop, kill ლიდერი, slow disk, clock skew.
10. დაკვირვება: ლიდერის/ლაგების/ჟურნალების მეტრიკა და ალერტები მორგებულია.

17) მინი სახელმძღვანელო: როდის უნდა მიიღოთ რა

etcd/Raft მტევანი კონფიგურაციის/საკონტროლო/კოორდინაციისთვის DC- ში.
ZoKeeper/ZAB ZK- ზე უკვე დაკავშირებული მომსახურებისთვის (ძველი მინები, ხაზები, ხელმძღვანელობა).
Multi-Paxos მზა სერვისის/ბიბლიოთეკის მეშვეობით უაღრესად სპეციალიზებულ სისტემებში.
EPaxos გუნდების განაწილებით და დაბალი კონფლიქტით.
Tendermint/HotStuff სრულფასოვანი ქსელებისთვის/PoS ლეიერი ათეულობით წამყვანით და საბოლოო მოთხოვნებით.
დინამოს მსგავსი/CRDT როდესაც კონსენსუსი არ არის საჭირო, ხელმისაწვდომობა/მასშტაბი მნიშვნელოვანია შემდგომი შერწყმით.

18) ინტერფეისის მაგალითები (ფსევდო)

18. 1 ჩაწერის კომიტი (რაფტის სტილი)

pseudo client -> leader: Propose(cmd)
leader. appendLog(cmd)
leader. replicateToQuorum()
if quorum_acked:
leader. commit(index)
leader. apply(index)
leader. reply(client, ok)

18. 2 Read ინდექსი ხაზოვანი კითხვისთვის (რაფტი)

pseudo client -> any: LinearizableRead node -> leader: ReadIndex?
leader -> quorum: Heartbeat (barrier)
leader -> node: ReadIndex=commit_index node. wait_until(applied_index >= ReadIndex)
node. reply(client, state_at(ReadIndex))

18. 3 ერთობლივი კონფიგურაცია

pseudo old_conf + new_conf # quorums must intersect commit (entries under joint)
switch_to(new_conf)

18. 4 BFT (HotStuff სავარაუდოა)

pseudo propose(block)
collect votes -> QC lock on highest QC commit when have consecutive QCs across phases

19) FAQ

Q: რატომ არ გამოიყენოთ ორი კვანძი და ტაი-ბრეიკერი?
A: ორი კვანძი მესამე არბიტრის გარეშე არ იძლევა კვორუმს განცალკევების დროს. საჭიროა 3 (CFT) ან 3f + 1 (BFT).

Q: რა არის რაფტი „უფრო ადვილია“ Paxos?
A: მკაფიო დაშლა, ლოგოსა და კონფიგურაციის გასაგები ინვარიანტები; უფრო ადვილია განხორციელება და თანმხლები.

Q: როგორ წაიკითხოთ სწრაფად ლიდერის დატვირთვის გარეშე?
A: Follower-reads (თანმიმდევრული) არაკრიტიკული, ან lease-reads/read-index ხაზოვანი; ქაშიშირით.

Q: რა კლავს p99?
A: WAN-RTT, დისკი fsync, GC გაჩერებები, გადაჭარბებული ლიდერი, დიდი სლაიდები „პიკის საათში“.

Q: საჭიროა კონსენსუსი ქეში/კატალოგისთვის?
A: თუ საკმარისია საღამოს კონსულტაცია - არა. თუ საჭიროა გარიგების ინვარიანტები - დიახ.

20) შედეგები

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