Ylalaşyk algoritmleri

1) Ylalaşyk näme we näme üçin zerur?

Konsensus - şowsuzlyklar we gijikdirmeler ýüze çykan mahalynda birnäçe düwünleriň arasyndaky şol bir manynyň/yzygiderliliginiň ylalaşylmagy. Adatça ýagdaýy köpeltmek meselesi çözülýär (State Machine Replication, SMR): ýagdaýlaryň kesgitlenen maşyny we amallaryň umumy tertibi bar.

• Ylalaşyk (SMR): buýruklaryň bitewi umumy tertibi → lineirlenýän ammar/reýestr, klaster meta-maglumatlary, geleşik koordinatorlary.
• Umumy tertibi bolmadyk kworum amallary (Dynamo-meňzeş, CRDT): diwergensiýa we soňraky birleşmäge mümkinçilik berýär; global serializasiýa zerur bolan ýerlerde ylalaşygyň ornuny tutmaýar.

2) Wagt we şowsuzlyk modeli

2. 1 Wagt modeli

Asinhron ulgamy: gijikdirmeler çäksiz; FLP teoremasy ⇒ goşmaça çaklamalar bolmazdan howpsuzlyk we durmuş kepillendirip bolmaýar.
Bölekleýin sinhronly (köplenç iş ýüzünde): näbelli T-den soň ulgam sinhronly hereket edýär - algoritmleriň köpüsi (Raft, Paxos) muňa bil baglaýar.
Sinhron: kanallara berk wagt çäkleri (seýrek ýagdaýda, ýörite torlardan/PTP-den başga).

2. 2 Şowsuzlyk modeli

Crash-fault tolerant (CFT): düwünler ýykylyp/asylyp biler, ýöne erbet hereket etmeýär.
Byzantine-fault tolerant (BFT): düwünler habarlary ýalan/galp edip biler. Wizantiýa çydamlylygy üçin 3f + 1 düwün gerek.

3) Ylalaşygyň häsiýetleri

Howpsuzlyk: gapma-garşylyksyz (iki sany dogry düwün dürli manylary çözüp bilmez).
Liveness (diri galmak): eger tor "sagdyn" bolsa, çözgüt gazanylýar.
Linearizasiýa (çyzyklylyk): amallar bir tertipde atom ýaly "görünýär".
Dowamlylygy: kabul edilen kararlar yzyna gaýtarylmaýar (magazineurnal/kworum bilen goralýar).

4) Kworumlar, köplük we kesişmeler

CFT dünýäsinde klassika: kworum> N/2. Lideriň ýazgylary we saýlawlary kworumlaryň kesişmegini ulanýar, şonuň üçin iki sany "walid" amallary gapma-garşy bolmaýar.
BFT-dünýäde: 3f + 1-den 2f + 1 kworumlary azyndan f + 1 dogruçyl düwünleriň geçmegini üpjün edýär.

Kesişmek düzgüni: islendik iki kworumda ≥ 1 umumy dogruçyl düwün (CFT) ýa-da ≥ f + 1 (BFT) bolmaly.

5) Ýagdaýyň göçürilmegi (jurnal + ulanmak)

• Snapshotlar (ýagdaýyň kesilmegi, şondan soň irki ýazgylar aýrylyp/birleşdirilip bilner).
• Magazineurnalyň kompaksiýasy we log-triim.
• Determinizmi barlamak (kod/konfigurasiýalaryň birmeňzeş görnüşi).

6) Ýolbaşçy we gollanma däl shemalar

Leadershipolbaşçylar (Raft, Multi-Paxos, ZAB): bir lider ýazgylary seriallaşdyrýar → aňsat akyl we operasiýa, durnukly liderde has gowy latency.
Lidersiz/multilider (EPaxos, Caesar): lidere has parallelizm we çydamlylyk, ýöne durmuşa geçirmek we gapma-garşylyk çözmek has kyn; toparlaryň ownuk gapma-garşylyklarynda girdeji görünýär.

7) Nusgawy CFT algoritmleri

7. 1 Paxos/Multi-Paxos (we amallar)

Ideýa: iki faza (prepare/propose), akseptorlaryň wadalary, majoritar kworumlar. Multi-Paxos "durnukly lider" galdyrýar we "gyzdyrylandan" soň amallary bir tapgyra (täze ýazgylar üçin) öwürýär.

• Çeýe, ýöne durmuşa geçirmek üçin kyn model.
• Specialörite ýazgylar (joint consensus) arkaly gaýtadan konfigurasiýa.
• Iş ýüzünde - kitaphanalar/hereketlendirijiler (Chubby/Spanner-nesil).

7. 2 Raft

Okamak üçin dekompozirlenen: lider saýlamak, ýazgylary köpeltmek, re-konfigurasiýa.

Election: tötänleýin wagtlar, şertler boýunça ses bermek; möhletine bir lider.
AppendEntries: giriş akymynyň lideri, prefiksiň (indeks/term), majoritar fiksasiýa boýunça kommitiň gabat gelmegine gözegçilik edýär.
Read-path: lease-reads (güýçli lider bilen) ýa-da çyzykly okamak üçin read-index.
Reconfig: "bilelikdäki konfigurasiýa" (joint) - düwünler geçişden öň iki toparda ses berýär.

Artykmaçlyklary: ösüş/debag üçin has aňsat, tertipiň güýçli üýtgemegi. Minuslar: lider - basyş nokady.

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

ZAB: Lider amallary, dikeldiş tapgyryny, zxid (döwür + indeks) giňeldýär.
VRR: "görnüşler" (views) ilkinji replikaly, ruhy taýdan Multi-Paxos-a meňzeýär.

8) Nolider/multilider CFT

8. 1 EPaxos

Hemişelik lider ýok: islendik düwün buýrugy döredip biler.
Gapma-garşylykly toparlar bölekleýin tertip alýarlar; gapma-garşylyksyz - 1-2 RTT-e ýerli birleşýär.
Pes gapma-garşylykda geodeziýada ýeňiş gazanmak, ýöne garaşlylygyň/grafanyň çylşyrymly kodlary.

8. 2 Caesar, Mencius

Gijikdirmeleri/deňagramlylygy we WAN-da işlemegi optimizirleýän üýtgeşmeler.

9) BFT algoritmleri we PoS maşgalasy

9. 1 PBFT (Practical BFT)

Üç faza (pre-prepare/prepare/commit), 3f + 1 düwün talap edýär.
Lokal ulgamlarda pes gizlinlik, köp ädimli we O (N ²) habarlar bilen gymmat.

9. 2 Tendermint (BFT-PoS stili)

Proposal we iki ses berişlik bilen tapgyrlar (prevote/precommit).
Determinirlenen walidator-teklip, wagt-autlar, bölekleýin sinhronlylyk.
Onlarça/ýüzlerçe tassyklaýjy bilen permissioned/PoS-torlar üçin amatly.

9. 3 HotStuff (we emele gelenler)

Kworum şahadatnamalary (QC) bolan "paketlere" üç fazaly shema birleşdirildi.
Aragatnaşyklaryň çyzykly çylşyrymlylygy, paketlemegi we paralel paýlanyşy goldamak, blokçeýnlerde durmuşa geçirmek üçin amatly (mysal üçin, Diem/Move-ekosistem).
Bosagaly gollar bilen (threshold signatures) traffik azalýar.

9. 4 PoW/jemleýji ylalaşyk (gysgaça)

Gaty manyda BFT däl, ähtimal konwergensiýa (iň köp işleýän zynjyr). Artykmaçlyklary: ýönekeýlik/açyklyk; kemçilikler: energiýa, ~ sekunt-minut.

10) Okamak: çyzykly, yzygiderli we kesilen

Çyzykly okamak: işjeň lease ýa-da read-index (Raft) arkaly lider → kworum arkaly tassyklamak.
Yzygiderli: islendik düwünden okap bilersiňiz, ýöne täzeligiň kepili bolmazdan.
Follower reads: gowşak talaplar üçin kabul ederlikli; keş üçin - ok.

11) Re-konfigurasiýa (klaster düzüminiň üýtgemegi)

Iki gapma-garşylykly konfigurasiýa (joint consensus) talap edýär: islendik kombinasiýa iki konfigurasiýanyň kworumlaryndan geçýär → "deşiksiz".
Birden goşuň/aýyryň, kworum mukdaryny berjaý ediň.
Leadership transferi arakesmäni azaldar.

12) Öndürijilik we sazlama

12. 1 Gijikdirmeler

Liderlik algoritmleri: Ýazga 1 RTT (durnukly lider bilen) + köpeltmek.
Geo-paýlaýyş: WAN RTT agdyklyk edýär → ýerli sebitleri + kross-sebitleýin proplikasiýany ýa-da EPaxos/HotStuff çemeleşmelerini ulanyň.

12. 2 Geçiş

Batching (toparlar topary), parallel AppendEntries, magazineurnalyň page-keshi, parallel ulanmak (amallar kommutasiýa edilende).
Diskler: NVMe/Aýry-aýry enjamdaky magazine, 'O _ DIRECT '/AIO, uly' fsync '- SLA çäklendirmeleri bilen interwal (durability/latency ylalaşygy).

12. 3 Guýruklar p99

Gyzgyn düwünlerden gaça duruň (lider hemişe ýeke): wagtal-wagtal aýlanmak ýa-da yzarlaýjylara read-offload.
GC-arakesmelere (JVM/Go), CPU pinlerine, NUMA gözegçilik ediň.

13) Geografiýa we topologiýalar

1 sebit, 3 zona: nusgawy CFT-klaster (N = 3/5).
2 sebitler: gaça duruň - 1-1 bölünende ygtybarly kworum netije bermeýär.
3 sebitler: "ortada" lider ýa-da lidersiz algoritmler; asinhron magazineurnaly bilen sebitleýin proxy/ýerli frontlar bolup biler.

14) Peýdalanmagyň amaly meseleleri

14. 1 Snapshotlar we dikeldiş

Magazineurnalyň ululygy/amallaryň sany boýunça çäk.
Snapşoty täze düwünlere geçirmek; gözegçilik pullaryny barlamak.

14. 2 Gözegçilik

Liderlik: kim lider, näçe möhlet (term/epoch) üýtgedi.
Лаги: `append_latency`, `commit_index - applied_index`.

Kworum-saglyk: "köplük dirimi/2f + 1?"

Magazineurnalyň ululygy/kompaksiýanyň tizligi, snapşotlaryň nobaty.
BFT üçin: sesleriň paýy, gol çekenleriň yzyna alynmagy, QC-iň gijikdirilmegi.

14. 3 Koduň howpsuzlygy/sazlaşygy

Simdäki teswirnamanyň wersiýasy, magazinesurnallaryň laýyklygy bilen migrasiýa.
Daşarky täsirlerde fencing bellikleri ("Paýlanan bloklara" serediň): Liderlik möhleti (term) CRON/joblara geçirmek.

15) Anti-patternler

Bir DBB ýa-da seriýallaşdyrmazdan kworum okamak ýeterlik bolan ýerlerde "moda üçin" ylalaşyk goýmak.
CP we AP-ni anyk çäkler bolmazdan garyşdyrmak (CAP) → öňünden aýdyp bolmajak UX.
Onlarça düwünli korporatiw meseleler üçin PoW/PoS-e aşa baha bermek (kyn/gymmat).
Kompozisiýa üýtgänsoň, re-konfigurasiýany we "kesişýän kworumlary" äsgermezlik et.
read-barrier (lease/read-index) → "hapa" okamagyň ýoklugy.
2 düwünli klasterleri başla (köplük ýok).
Disklere we fsync kembaha garamak: "ýadymda hemme zat uçýar" - ilkinji täzeden başlamazdan ozal.

16) Saýlamagyň çek-sanawy

1. Şowsuzlyk modeli: CFT (boýag) ýa-da BFT (zyýanly)?
2. Geografiýa: bir sebit/üç zolak ýa-da WAN? RTT karar berýär.
3. Okamak semantikasy: çyzykly okamak zerurmy? Lease/read-index/yzarlaýjy-ridler.
4. Ýük: p50/p99, throughput üçin garaşmak; köp liderlige mätäçmi?
5. Iş çylşyrymlylygy: kitaphana/taýýar hereketlendiriji (etcd/ZK/Consul/Raft-liby) vs öz durmuşa geçirilmegi.
6. Täzelenmek: ýygy-ýygydan? Bize joint consensus we migrasiýa gurallary gerek.
7. Integrasiýa: daşarky zyýanly täsirleri - epoch/term boýunça fencing barmy?
8. Howpsuzlyk: düwünleri tassyklamak, kanaly şifrlemek, teswirnamanyň wersiýalaryna gözegçilik etmek.
9. Synag pleýbuklary: partition, GC-stop, lider kill, slow disk, clock skew.
10. Syn edilişi: lideriň/laglaryň/magazineurnalyň metrikleri we alertler sazlanýar.

17) Kiçi gollanma: haçan näme almaly

etcd/DC içindäki konfigurasiýa/blokirleme/utgaşdyrmak üçin Raft-klaster.
ZooKeeper/ZAB eýýäm ZK bilen baglanyşykly hyzmatlar üçin (köne akymlar, nobatlar, liderlik).
Dar hünärli ulgamlarda taýýar hyzmat/kitaphananyň üsti bilen Multi-Paxos.
EPaxos geo-paýlanyşda we pes gapma-garşylykda.
Tendermint/HotStuff permissioned networks/PoS-leýer üçin onlarça-ýüzlerçe tassyklaýjy we gutarnykly talaplar bilen.
Dynamo-şuňa meňzeş/CRDT konsensusa mätäç däl, ýöne elýeterlilik/masştab, soň birleşmek möhümdir.

18) Interfeýsleriň mysallary (psevdo)

18. 1 Kommit ýazgylar (Raft stili)

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 Çyzykly okamak üçin okamak indeksi (Raft)

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 Bilelikdäki konfigurasiýa

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

18. 4 BFT (HotStuff-takmynan)

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

19) FAQ

Q: Näme üçin iki düwün we tai breýker ulanmaly däl?
A: Üçünji eminsiz iki düwün bölünende kworum bermeýär. 3 (CFT) ýa-da 3f + 1 (BFT) ≥ gerek.

Q: Raft "Paxos" näme üçin aňsat?
A: Düşnükli dekompozisiýa, logyň we konfigurasiýanyň düşnükli üýtgemeleri; durmuşa geçirmek we ýoldaşlyk etmek has aňsat.

S: Lideri ýüklemezden nädip çalt okamaly?
A: çyzykly däl üçin follower-reads (yzygiderli) ýa-da çyzykly üçin lease-reads/read-index; kesmek.

S: p99 näme öldürýär?
A: WAN-RTT, disk fsync, GC-aýaklar, aşa gyzdyrylan lider, "gyssagly sagatda" uly snapshotlar.

Q: Kesmek/katalog üçin ylalaşyk gerekmi?
A: Eger eventual consistency ýeterlik bolsa - ýok. Eger geleşik üýtgemeleri talap edilse - hawa.

20) Netijeler

Ylalaşyk berk utgaşdyrmak we tertipleşdirmek üçin guraldyr. Algoritmi ret ediş modeline we geografiýa esaslanyp saýlaň; kworum kesişmelerini, dogry re-konfigurasiýany, möhüm bolan ýerlerde çyzykly okalmagy we synlanmagy üpjün ediň. Daşarky täsirler, snapshotlar we magazinesurnallaryň tertibi üçin fencing hakda ýatdan çykarmaň. Şonda ýagdaýyň köpelmegi öňünden aýdyp bolar we hadysalar seýrek we düşnükli bolar.