Konsensus alqoritmləri

1) Konsensus nədir və niyə lazımdır

Konsensus - uğursuzluqlar və gecikmələr zamanı bir neçə düyün arasında eyni dəyər/dəyər ardıcıllığının əlaqələndirilməsi. Ənənəvi olaraq State Machine Replication (SMR) vəzifəsi həll olunur: determinated state Machine və əməliyyatların ümumi qaydası var.

• Konsensus (SMR): komandaların vahid ümumi qaydası → lineer saxlama/reyestr, klaster meta məlumatları, əməliyyat koordinatorları.
• Ümumi sifarişsiz kvorum əməliyyatları (Dynamo-oxşar, CRDT): divergensiya və sonrakı birləşməyə imkan verir; qlobal serializasiyanın lazım olduğu yerdə konsensusu əvəz etmir.

2) Zaman və uğursuzluq modeli

2. 1 Zaman modeli

Asinxron şəbəkə: gecikmələr məhdudiyyətsizdir; FLP teoremi ⇒ əlavə fərziyyələr olmadan həm safety, həm də liveness təmin etmək mümkün deyil.
Qismən sinxron (tez-tez praktikada): naməlum T sistemindən sonra sistem sinxron davranır - əksər alqoritmlər (Raft, Paxos) məhz buna güvənir.
Sinxron: kanallara sərt vaxt limitləri (nadir hallarda xüsusi şəbəkələr/PTP istisna olmaqla).

2. 2 Uğursuzluq modeli

Crash-fault tolerant (CFT): düyünlər yıxıla/asıla bilər, lakin zərərli davranmayın.
Byzantine-fault tolerant (BFT): qovşaqlar yalan/saxta mesajlar ola bilər. Bizans f tolerantlığı üçün 3f + 1 düyün tələb olunur.

3) Konsensusun xüsusiyyətləri

Təhlükəsizlik (təhlükəsizlik): ardıcıllıq (iki düzgün düyün fərqli dəyərləri həll etməyəcək).
Liveness (canlılıq): şəbəkə «sağlam» olarsa, qərar əldə edilir.
Linearizable (linear): əməliyyatlar vahid qaydada atom kimi «görünür».
Davamlılıq: Qəbul edilmiş qərarlar geri qaytarılmır (jurnal/kvorum tərəfindən qorunur).

4) Kvorumlar, çoxluq və kəsişmələr

CFT dünyasında klassik: kvorum> N/2. Liderin qeydləri və seçkiləri kvorumların kəsişməsindən istifadə edir, buna görə də iki «valid» əməliyyatı ziddiyyət təşkil etmir.
BFT dünyasında: 3f + 1-dən 2f + 1 kvorumları ən azı f + 1 dürüst düyün keçidini təmin edir.

Kəsişmə qaydası: hər iki kvorum ≥ 1 ümumi ədalətli qovşaq (CFT) və ya ≥ f + 1 (BFT) olmalıdır.

5) Hal replikasiyası (jurnal + tətbiq)

• Snapshotlar (erkən qeydlərin silinməsi/kompakt edilməsi mümkün olan vəziyyətin kəsilməsi).
• Jurnalın kompaksiyası və log-triim.
• Determinizm yoxlamaları (kod/konfiqurasiya eyni versiyası).

6) Liderlik və qeyri-liderlik sxemləri

Liderlik (Raft, Multi-Paxos, ZAB): bir lider yazıları seriallaşdırır → daha asan zehni və əməliyyat, sabit bir liderdə daha yaxşı latency.
Lidersiz/multilider (EPaxos, Caesar): liderə daha çox paralellik və dözümlülük, lakin həyata keçirilməsi və münaqişə həlli daha çətindir; mənfəət komandaların kiçik qarşıdurmalarında görünür.

7) Klassik CFT alqoritmləri

7. 1 Paxos/Multi-Paxos (və təcrübələr)

Fikir: iki mərhələ (prepare/propose), akseptorların vədləri, majoritar kvorumlar. Multi-Paxos «sabit lider» buraxır və «istiləşmədən» sonra əməliyyatları bir raundlu (yeni qeydlər üçün) çevirir.

• Çevik, lakin həyata keçirmək üçün çətin model.
• Xüsusi qeydlər (joint consensus) vasitəsilə yenidən konfiqurasiya.
• Praktikada - kitabxanalar/mühərriklər (Chubby/Spanner-nəsil).

7. 2 Raft

Öyrənmə üçün dekompozasiya: lider seçimi, log replikasiyası, yenidən konfiqurasiya.

Election: təsadüfi vaxtlar, şərtlər üzrə səsvermə; müddətinə bir lider.
AppendEntries: lider axın qeydlər, prefiks (indeks/term), majoritar fiksasiya kommit uyğunluğu izləyir.
Read-path: lease-reads (güclü lider ilə) və ya lineer oxu üçün read-index.
Reconfig: «birgə konfiqurasiya» (joint) - keçiddən əvvəl iki klasterdə düyünlər səs verir.

Artıları: inkişaf/debag, güclü invariant sifariş üçün daha asan. Mənfi cəhətləri: lider - təzyiq nöqtəsi.

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

ZAB: Lider əməliyyatlar, bərpa mərhələsi, zxid (epoxa + indeks).
VRR: «views» (views) ilkin replikası ilə, ruh Multi-Paxos bənzəyir.

8) Qeyri-lider/multilider CFT

8. 1 EPaxos

Daimi lider yoxdur: hər hansı bir qovşaq komandanı işə sala bilər.
Münaqişə komandaları qismən sifariş alır; münaqişəsiz - 1-2 RTT-yə yerli olaraq birləşdirilir.
Aşağı konflikt, lakin mürəkkəb asılılıq/qrafik kodları ilə geo-paylama qazanmaq.

8. 2 Caesar, Mencius

Gecikmələri/balansı və WAN-da işləməyi optimallaşdıran variasiyalar.

9) BFT alqoritmləri və PoS ailəsi

9. 1 PBFT (Practical BFT)

Üç faza (pre-prepare/prepare/commit), 3f + 1 düyün tələb edir.
Lokal şəbəkələrdə aşağı gizlilik, çox addımlı və O (N ²) mesajlarla bahalı.

9. 2 Tendermint (BFT-PoS stil)

Proposal və iki səsvermə ilə raundlar (prevote/precommit).
Determinik validator-təklif, zaman-aut, qismən sinxronizasiya.
Onlarla/yüzlərlə validatorla permissioned/PoS şəbəkələri üçün yaxşıdır.

9. 3 HotStuff (və törəmələri)

Kvorum sertifikatları (QC) olan «paketlərə» üç fazalı sxem birləşdirilmişdir.
Kommunikasiyaların xətti mürəkkəbliyi, paketləşdirmə və paralel paylayışa dəstək blokçeynlərdə (məsələn, Diem/Move-ekosistem) həyata keçirmək üçün əlverişlidir.
Eşik imzaları (threshold signatures) ilə trafik azalır.

9. 4 PoW/yığım konsensusu (qısaca)

Ciddi mənada BFT deyil, ehtimal yaxınlaşması (ən böyük iş zənciri). Üstünlüklər: sadəlik/açıqlıq; çatışmazlıqlar: enerji, final üçün ~ saniyə-dəqiqə.

10) Oxu: xətti, ardıcıl və cached

Lineer oxu: aktiv lease və ya read-index vasitəsilə lider (Raft) → kvorum vasitəsilə təsdiq.
Ardıcıl: hər hansı bir qovşaqdan oxuya bilərsiniz, lakin təravət zəmanəti olmadan.
Follower reads: zəif tələblər üçün icazə verilir; cache üçün - ok.

11) Re-konfiqurasiya (klaster tərkibinin dəyişdirilməsi)

İki üst-üstə düşən konfiqurasiya (joint consensus) tələb edir: hər hansı bir kommit hər iki konfiqurasiyanın kvorumlarından keçir → «deşik» olmadan.
Bir-bir əlavə edin/silin, kvorum ölçüsünə riayət edin.
Liderliyin ötürülməsi (leadership transfer) fasilələri azaldır.

12) Performans və sazlama

12. 1 Gecikmələr

Liderlik alqoritmləri: Qeyddə 1 RTT (sabit lider ilə) + replikasiya.
Geography: WAN RTT dominant → yerli bölgələr + xaç-regional replikasiya və ya EPaxos/HotStuff yanaşmalar istifadə edin.

12. 2 Keçid

Batching (komanda qruplaşması), paralel AppendEntries, page cache jurnalı, paralel tətbiq (əməliyyatlar kommutasiya edildikdə).
Disklər: Ayrı bir cihazda NVMe/Jurnal, 'O _ DIRECT '/AIO, böyük' fsync '-SLA məhdudiyyətləri ilə interval (durability/latency kompromis).

12. 3 quyruqları p99

Qaynar düyünlərdən qaçın (lider daim təkdir): ardıcıllara dövri rotasiya və ya read-offload.
GC fasilələri (JVM/Go), CPU pinləri, NUMA nəzarət edin.

13) Coğrafiya və topologiyalar

1 region, 3 zona: klassik CFT klasteri (N = 3/5).
2 bölgələr: çəkinin - 1-1 bölünməsində etibarlı kvorum alınmır.
3 + regionlar: «ortada» lider və ya lidersiz alqoritmlər; asinxron jurnal ilə regional proxy/yerli cəbhələr mümkündür.

14) Praktiki əməliyyat məsələləri

14. 1 Snapshotlar və bərpa

Jurnalın ölçüsünə/əməliyyatların sayına görə eşik.
Snapshot yeni qovşaqlara ötürülməsi; nəzarət məbləğlərinin yoxlanılması.

14. 2 Monitorinq

Liderlik: kim lider, neçə müddət (term/epoch) dəyişdi.
Лаги: `append_latency`, `commit_index - applied_index`.

Kvorum sağlamlığı: «əksəriyyət/2f + 1 sağ?»

Jurnalın ölçüsü/kompaksiya sürəti, snapshot növbəsi.
BFT üçün: səslərin payı, abunəçilərin geri çəkilməsi, QC gecikmələri.

14. 3 Kod təhlükəsizliyi/uyğunluğu

Məftildə protokol versiyası, jurnalların uyğunluğu ilə miqrasiya.
Xarici effektlərdə fencing tokenləri («Paylanmış kilidlər» -ə baxın): CRON/joblara keçid üçün liderlik müddəti (term).

15) Anti-nümunələr

Bir DBB və ya serializasiya olmadan kvorum oxunuşları olan yerdə «moda üçün» konsensus qoyun.
CP və AP-ni dəqiq sərhədlər olmadan qarışdırın (CAP) → gözlənilməz UX.
Onlarla düyün ilə korporativ tapşırıqlar üçün PoW/PoS qiymətləndirmək (çətin/bahalı).
Tərkibi dəyişdikdə yenidən konfiqurasiyaya və «kəsişən kvorumlara» məhəl qoymayın.
Heç bir read-barrier (lease/read-index) → «çirkli» oxunuşlar.
2 qovşaqlı klasterləri işə salın (çoxluq yoxdur).
Disklərin qiymətləndirilməməsi və fsync: «yaddaşda hər şey uçur» - ilk yenidən başlamazdan əvvəl.

16) Check-list seçimi

1. Uğursuzluq modeli: CFT (boyalar) və ya BFT (zərərli)?
2. Coğrafiya: bir region/üç zona və ya WAN? RTT qərar verir.
3. Oxu semantikası: xətti oxu lazımdır? Lease/read-index/izləyici-rides.
4. Yük: p50/p99, throughput üçün gözləntilər; çox liderliyə ehtiyacınız var.
5. Əməliyyat mürəkkəbliyi: kitabxana/hazır mühərrik (etcd/ZK/Consul/Raft-liby) vs öz həyata.
6. Reconfiguration: tez-tez? joint consensus və miqrasiya alətləri lazımdır.
7. Inteqrasiya: xarici yan təsirləri - epoch/term ilə fencing var?
8. Təhlükəsizlik: qovşaqların identifikasiyası, kanal şifrələməsi, protokol versiyalarının monitorinqi.
9. Test playbook: partition, GC-stop, lider kill, slow disk, clock skew.
10. Müşahidə: lider/lag/jurnalın metrikləri və alertlər konfiqurasiya edilmişdir.

17) Mini məlumat: nə zaman almaq lazımdır

etcd/DC daxilində konfiqurasiya/bloklama/koordinasiya üçün Raft-klaster.
ZooKeeper/ZAB artıq ZK bağlı xidmətlər üçün (köhnə yığınlar, növbələr, liderlik).
Multi-Paxos yüksək ixtisaslaşmış sistemlərdə hazır xidmət/kitabxana vasitəsilə.
Geo-paylama və komandaların aşağı konfliktində EPaxos.
permissioned şəbəkələr/PoS-layer üçün Tendermint/HotStuff onlarla və yüzlərlə validator və final tələbləri ilə.
Dynamo-oxşar/CRDT konsensusa ehtiyac olmadıqda, lakin daha sonra birləşmə ilə əlçatanlıq/miqyasda vacibdir.

18) Interfeys nümunələri (psevdo)

18. 1 Kommit qeydlər (Raft-stil)

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 Lineer oxu üçün Read-index (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 Birgə konfiqurasiya

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

18. 4 BFT (HotStuff-yaxın)

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

19) FAQ

Q: Niyə iki düyün və tay braker istifadə etmirsiniz?
A: Üçüncü hakim olmadan iki düyün ayrılma zaman kvorum vermir. 3 (CFT) və ya 3f + 1 (BFT) ≥ lazımdır.

Q: Paxos Raft «asan» nədir?
A: Aydın dekompozisiya, başa düşülən giriş və konfiqurasiya invariantları; həyata keçirmək və müşayiət etmək daha asandır.

Q: Bir lider yükləmədən necə tez oxumaq olar?
A: qeyri-kritik üçün Follower-reads (ardıcıl), və ya lineer üçün lease-reads/read-index; cache.

Q: p99 öldürür?
A: WAN-RTT, disk fsync, GC-stop, həddindən artıq qızdırılmış lider, «pik saat» böyük snapshot.

Q: Cache/kataloq üçün konsensus lazımdır?
A: eventual consistency kifayətdirsə - yox. Əgər əməliyyat invariantları tələb olunursa - bəli.

20) Nəticələr

Konsensus - ciddi uyğunluq və nizam üçün vasitədir. Alqoritmi uğursuzluq modeli və coğrafiya əsasında seçin; kvorum kəsişmələri, düzgün re-konfiqurasiya, kritik olduğu yerlərdə xətti oxunmalar və müşahidə olunma təmin edin. Xarici effektlər, snapshot və jurnal intizamı üçün fencing haqqında unutmayın. Sonra vəziyyətin replikasiyası proqnozlaşdırıla bilər və hadisələr nadir və başa düşüləndir.