Konsensus algoritmlari

1) Konsensus nima va nima uchun zarur

Konsensus - nosozliklar va kechikishlarda bir necha uzellar o’rtasidagi bir xil ma’noni/ma’nolar ketma-ketligini kelishish. An’anaga ko’ra, holatni replikatsiya qilish vazifasi (State Machine Replication, SMR) hal qilinmoqda: holatlarning determinizatsiya qilingan mashinasi va operatsiyalarning umumiy tartibi mavjud.

• Konsensus (SMR): buyruqlarning yagona total tartibi → liniyalashtiriladigan ombor/reyestr, klaster meta-maʼlumotlari, tranzaksion koordinatorlar.
• Umumiy tartibsiz kvorum operatsiyalari (Dynamo-shunga o’xshash, CRDT): divergensiya va keyingi qo’shilishga yo’l qo’yadi; global seriallashtirish kerak bo’lgan joyda konsensus o’rnini bosmaydi.

2) Vaqt va nosozliklar modeli

2. 1 Vaqt modeli

Asinxron tarmoq: kechikishlar cheklanmagan; FLP teoremasi ⇒ safety va liveness ni qo’shimcha taxminlarsiz kafolatlash mumkin emas.
Qisman sinxron (ko’pincha amaliyotda): noma’lum T tizimidan so’ng tizim o’zini sinxron tutadi - aksariyat algoritmlar (Raft, Paxos) aynan shu narsaga tayanadi.
Sinxron: kanallarga qat’iy taym-limitlar (kamdan-kam hollarda, maxsus tarmoqlar/HPP bundan mustasno).

2. 2 Rad etish modeli

Crash-fault tolerant (CFT): tugunlar yiqilib tushishi mumkin, lekin yomon niyat qilmaydi.
Byzantine-fault tolerant (BFT): uzellar xabarlarni yolgʻon/qalbakilashtirishi mumkin. Vizantiyaliklarga nisbatan tolerantlik uchun 3f + 1 tugun talab qilinadi.

3) Konsensus xossalari

Safety (xavfsizlik): qarama-qarshilik (ikkita toʻgʻri tugun turli qiymatlarni hal qila olmaydi).
Liveness (omon qolish): agar tarmoq «sog’lom» bo’lsa, qaror qabul qilinadi.
Linearlashtiriluvchanlik (chiziqlilik): operatsiyalar atomar kabi yagona tartibda «ko’riladi».
Chidamlilik: qabul qilingan qarorlar qaytarilmaydi (jurnal/kvorum bilan himoya qilinadi).

4) Kvorumlar, ko’pchilik va kesishmalar

CFT dunyosida klassik: kvorum> N/2. Yozuvlar va rahbar saylovlari kvorumlarni kesib o’tishdan foydalanadi, shuning uchun ikkita «valid» operatsiyasi bir-biriga zid emas.
BFT-dunyoda: 3f + 1 dan 2f + 1 kvorumlari kamida f + 1 halol tugunlarni kesib o’tishni ta’minlaydi.

Kesishish qoidasi: har qanday ikkita kvorum ≥ 1 umumiy halol tugunga (CFT) yoki ≥ f + 1 (BFT) ega bo’lishi kerak.

5) Holat replikatsiyasi (jurnal + qo’llash)

• Snapshotlar (erta yozuvlarni olib tashlash/kompaktlash mumkin boʻlgan holatni kesish).
• Jurnal kompaksiyasi va log-triim.
• Determinizm tekshiruvi (kod/konfiguratsiyalarning bir xil versiyasi).

6) Yetakchilik va noliderlik sxemalari

Rahbarlik (Raft, Multi-Paxos, ZAB): bitta rahbar yozuvlarni seriallashtiradi → aqliy va operatsion jihatdan osonroq, barqaror rahbarda latency yaxshiroq.
Lidersiz/multilider (EPaxos, Caesar): yetakchiga nisbatan ko’proq parallellik va bag’rikenglik, ammo amalga oshirish va mojaro-yechim qiyinroq; foyda jamoalarning kichik to’qnashuvlarida ko’rinadi.

7) Klassik CFT algoritmlari

7. 1 Paxos/Multi-Paxos (va amaliyot)

G’oya: ikki faza (prepare/propose), akseptorlarning va’dalari, majoritar kvorumlar. Multi-Paxos «barqaror rahbar» ni qoldiradi va operatsiyalarni «isinishdan» keyin bir raundli (yangi yozuvlar uchun) operatsiyalarga aylantiradi.

• Moslashuvchan, ammo amalga oshirish qiyin model.
• Maxsus yozuvlar (joint consensus) orqali qayta konfiguratsiyalar.
• Amalda - kutubxonalar/dvigatellar (Chubby/Spanner-avlod).

7. 2 Raft

Ta’lim olish uchun dekompozatsiyalangan: etakchi tanlash, loglar replikatsiyasi, re-konfiguratsiya.

Election: tasodifiy taymautlar, shartlar bo’yicha ovoz berish; bir rahbar muddatga.
AppendEntries: yozuv strimitining etakchisi, prefiks (indeks/term), majoritar fiksatsiya bo’yicha kommitning mos kelishini kuzatadi.
Read-path: lease-reads (kuchli yetakchi) yoki chiziqli o’qish uchun read-index.
Reconfig: «qoʻshma konfiguratsiya» (joint) - tugunlar oʻtishdan oldin ikkita klasterda ovoz beradi.

Afzalliklari: ishlab chiqish/debaga osonroq, tartibning kuchli invariantlari. Kamchiliklar: etakchi - bosim nuqtasi.

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

ZAB: etakchi tranzaksiyalar, tiklanish fazasi, zxid (epoxa + indeks) haqida xabar beradi.
VRR: «ko’rinishlar» birlamchi replikasi bilan Multi-Paxosga o’xshaydi.

8) Nolider/multilider CFT

8. 1 EPaxos

Har qanday tugun buyruqni boshlashi mumkin.
Nizoli buyruqlar qisman tartib oladi; mojarosiz - lokal ravishda 1-2 RTTga o’tkaziladi.
Past ziddiyatli, ammo murakkab bog’liqlik/grafik kodlarida georayirishda yutuq.

8. 2 Caesar, Mencius

Kechikishlar/muvozanatlash va WANda ishlashni optimallashtiradigan o’zgarishlar.

9) BFT algoritmlari va PoS oilasi

9. 1 PBFT (Practical BFT)

Uch faza (pre-prepare/prepare/commit) 3f + 1 tugun talab qiladi.
Lokal tarmoqlarda past latentlik, ko’p bosqichli yo’llar va O (N ²) xabarlar.

9. 2 Tendermint (BFT-PoS uslubi)

Proposal va ikkita ovoz berish bilan raundlar (prevote/precommit).
Determinik validator-taklif, taym-autlar, qisman sinxronlik.
O’nlab/yuzlab validatorli permissioned/PoS tarmoqlari uchun yaxshi.

9. 3 HotStuff (va hosilalari)

Kvorum sertifikatlari (QC) boʻlgan «paketlar» ga uch fazali sxema birxillashtirildi.
Kommunikatsiyalarning chiziqli murakkabligi, paketlash va parallel payplaynizatsiyani qo’llab-quvvatlash blokcheynlarda amalga oshirish uchun qulaydir (masalan, Diem/Move-ekotizim).
Bosiq imzolar bilan (threshold signatures) trafik kamayadi.

9. 4 PoW/jamgʻarma konsensusi (qisqacha)

Qattiq ma’noda BFT emas, balki ehtimoliy konvergensiya (eng ko’p ishlaydigan zanjir). Afzalliklari: soddaligi/ochiqligi; kamchiliklar: energiya, oxirigacha ~ soniya-daqiqa.

10) O’qish: chiziqli, ketma-ket va keshlangan

Chiziqli oʻqishlar: faol lease yoki read-index (Raft) orqali yetakchi → kvorum orqali tasdiqlash.
Izchil: har qanday tugundan o’qish mumkin, ammo yangilik kafolatisiz.
Follower reads: zaif talablarga javob beradi; kesh uchun - ok.

11) Re-konfiguratsiya (klaster tarkibini o’zgartirish)

Ikkita bir-biriga mos keladigan konfiguratsiyani talab qiladi (joint consensus): har qanday kommitalar ikkala konfiguratsiyaning kvorumlaridan o’tadi → teshiklarsiz.
Bittadan qoʻshing/olib tashlang, kvorum miqdoriga rioya qiling.
Leadership transferi tanaffuslarni kamaytiradi.

12) Unumdorlik va tyuning

12. 1 Kechikishlar

Etakchilik algoritmlari: 1 ta RTT + replikatsiya.
Georayyorlash: WAN RTT ustunlik qiladi → mahalliy mintaqalar + kross-mintaqaviy replikatsiya yoki EPaxos/HotStuff yondashuvlaridan foydalaning.

12. 2 Ruxsatnoma

Batching (buyruqlar guruhlanishi), parallel AppendEntries, jurnal peyj keshi, parallel foydalanish (amallar kommutatsiya qilinganda).
Disklar: NVMe/Alohida qurilmadagi jurnal,’O _ DIRECT ’/AIO, katta’fsync’- SLA cheklovlari bilan interval (murosa durability/latency).

12. 3 p99

Issiq tugunlardan qoching (doimiy ravishda yolg’iz): vaqti-vaqti bilan rotatsiya yoki izdoshlarga read-offload.
GC pauzalarini (JVM/Go), CPU pinlarini, NUMAni nazorat qiling.

13) Geografiya va topologiyalar

1 mintaqa, 3 zona: klassik CFT klasteri (N = 3/5).
2 mintaqa: qoching - 1-1 bo’linganda ishonchli kvorum bo’lmaydi.
3 + mintaqalar: «o’rtada» yetakchi yoki lidersiz algoritmlar; asinxron jurnal bilan mintaqaviy proksi/mahalliy jabhalar bo’lishi mumkin.

14) Ekspluatatsiyaning amaliy masalalari

14. 1 Snapshotlar va tiklash

Jurnal hajmi/operatsiyalar soni bo’yicha chegara.
Snapshotni yangi uzellarga berish; nazorat summalarini tekshirish.

14. 2 Monitoring

Etakchilik: kim yetakchi, qancha muddat (term/epoch) o’zgargan.
Лаги: `append_latency`, `commit_index - applied_index`.

Kvorum-salomatlik: «ko’pchilik tirikmi/2f + 1?»

Jurnal hajmi/kompaksiya tezligi, snapshotlar navbati.
BFT uchun: ovoz ulushi, imzo chekuvchilar, QC kechikishlari.

14. 3 Kod xavfsizligi/muvofiqligi

Simdagi bayonnomaning versiyaliligi, migratsiya jurnallarning muvofiqligi.
Tashqi effektlardagi fencing-tokenlar («Taqsimlangan blokirovkalar» ga qarang): yetakchilik muddati (term) CRON/joblarga o’tkaziladi.

15) Anti-patternlar

«Moda uchun» konsensusni bitta DBMS yoki kvorum o’qish etarli bo’lganda qo’ying.
CP va AP ni aniq chegarasiz (CAP) → oldindan aytib boʻlmaydigan UX bilan aralashtirish.
O’nlab tugunli korporativ vazifalar uchun PoW/PoS’ni ortiqcha baholash (qiyin/qimmat).
Tarkibni oʻzgartirishda qayta konfiguratsiyani va «kesishuvchi kvorumlarni» eʼtiborsiz qoldirish.
read-barrier (lease/read-index) yo’qligi → «iflos» o’qish.
2 tugunli klasterlarni ishga tushirish (koʻpchilik yoʻq).
Disklarni notoʻgʻri baholash va fsync: «hamma narsa xotirada uchadi» - birinchi qayta ishga tushirilgunga qadar.

16) Tanlov chek-varaqasi

1. Muvaffaqiyatsizliklar modeli: CFT (krashlar) yoki BFT (zararli niyatlar)?
2. Geografiyasi: bitta hudud/uchta hudud yoki WAN? RTT hal qiladi.
3. Oʻqish semantikasi: chiziqli oʻqish kerakmi? Lease/read-index/follover-ridlar.
4. Yuk: p50/p99, throughput bo’yicha kutish; ko’p rahbarlik kerakmi?
5. Operatsion murakkablik: kutubxona/tayyor dvigatel (etcd/ZK/Consul/Raft-liblar) vs o’zi amalga oshirish.
6. Qayta konfiguratsiya: tez-tez? Bizga joint consensus va migratsiya vositalari kerak.
7. Integratsiyalar: tashqi nojo’ya ta’sirlar - epoch/term bo’yicha fencing bormi?
8. Xavfsizlik: uzellarni autentifikatsiya qilish, kanalni shifrlash, protokol versiyalarini boshqarish.
9. Test pleybuklari: partition, GC-stop, lider kill, slow disk, clock skew.
10. Kuzatish darajasi: lider/lag/jurnal metrikasi va alertlar sozlangan.

17) Mini-ma’lumotnoma: qachon nima olish kerak

etcd/DC ichidagi konfiguratsiyalar/blokirovkalar/muvofiqlashtirish uchun Raft klasteri.
ZooKeeper/ZAB allaqachon ZK bilan bog’langan xizmatlar uchun.
Multi-Paxos tor ixtisoslashgan tizimlarda tayyor servis/kutubxona orqali.
EPaxos georayyorlash va past ziddiyatli buyruqlarda.
Tendermint/HotStuff permissioned tarmoqlari/PoS-leyer uchun o’nlab-yuzlab validatorlar va yakuniy talablar bilan.
Dynamo/CRDT kabi konsensusga ehtiyoj bo’lmaganda, keyinchalik qo’shilish uchun foydalanish imkoniyati/ko’lami muhimdir.

18) Interfeyslar namunalari (psevdo)

18. 1 Kommit yozuv (Raft uslubi)

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 Chiziqli oʻqish uchun 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 Qo’shma konfiguratsiya

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

18. 4 BFT (HotStuff-taxminan)

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

19) FAQ

Q: Nega ikkita tugun va tay-breykerdan foydalanmaslik kerak?
A: Uchinchi hakamsiz ikki tugun ajratishda kvorum bermaydi. 3 (CFT) yoki 3f + 1 (BFT) ≥ kerak.

Q: Raft nima uchun Paxosga osonroq?
A: Aniq dekompozitsiya, logning va konfiguratsiyaning tushunarli invariantlari; amalga oshirish va kuzatib borish osonroq.

Q: Qanday qilib rahbarni yuklamasdan tez o’qish mumkin?
A: Follower-reads (ketma-ket) nekritik yoki lease-reads/read-index chiziqli; kesh qiling.

Q: p99 ni nima o’ldiradi?
A: WAN-RTT, diskli fsync, GC-oyoqlari, haddan tashqari qizib ketgan etakchi, «shoshilinch soat» dagi katta snapshotlar.

Q: Kesh/katalog uchun konsensus kerakmi?
A: Agar eventual consistency yetarli bo’lsa - yo’q. Agar tranzaksion invariantlar talab qilinsa - ha.

20) Yakunlar

Konsensus - qat’iy muvofiqlik va tartibga solish vositasi. Algoritmni nosozliklar va geografiya modelidan kelib chiqib tanlang; kvorum kesishmalarini, to’g "ri re-konfiguratsiyani, muhim bo’lgan joylarda chiziqli o’qishlarni va kuzatishni ta’minlang. Tashqi effektlar, snapshotlar va jurnallarning intizomi uchun fencing haqida unutmang. SHunda holat replikasi oldindan aytib bo’ladi, hodisalar esa kam uchraydi va tushunarli bo’ladi.