Консенсус алгоритмдери

1) Консенсус деген эмне жана ал эмне үчүн керек

Консенсус - бир эле маанини/мүчүлүштүктөр жана кечигүүлөр учурунда бир нече түйүндөрдүн ортосундагы маанилердин ырааттуулугун макулдашуу. Салттуу түрдө мамлекеттин репликация маселеси (State Machine Replication, SMR) чечилет: шарттардын аныктоочу машинасы жана операциялардын жалпы тартиби бар.

• Консенсус (SMR): командалардын бирдиктүү жалпы тартиби → линиялануучу сактоо/реестр, кластердин метадерилери, транзакциялык координаторлор.
• Жалпы тартиби жок кворум иштери (Dynamo-окшош, CRDT): дивергенцияга жана андан кийинки биригүүгө жол берет; дүйнөлүк сериалдаштыруу зарыл болгон жерде консенсусту алмаштыра албайт.

2) Убакыт жана мүчүлүштүктөрдүн модели

2. 1 Убакыт модели

Асинхрондук тармак: кечигүү чексиз; FLP теоремасы ⇒ кошумча божомолдор жок коопсуздук жана жашоо кепилдик берүү мүмкүн эмес.
Жарым-жартылай синхрондуу (көбүнчө практикада): белгисиз T системасынан кийин "өзүн синхрондуу алып жүрөт" - көпчүлүк алгоритмдер (Raft, Paxos) ушуга таянат.
Синхрондуу: каналдарга катуу тайм-лимиттер (атайын тармактарды/ПТПны кошпогондо, сейрек кездешет).

2. 2 мүчүлүштүктөр модели

Crash-fault tolerant (CFT): түйүндөр жыгылып/илинип, бирок жаман эмес.
Byzantine-fault tolerant (BFT): түйүндөр жалган/жасалма билдирүүлөр болот. Талап кылынат 3f + 1 узел үчүн толеранттуулук f византиялык.

3) Консенсустун касиеттери

Коопсуздук (коопсуздук): карама-каршылыксыздык (эки туура түйүндөр ар кандай маанилерди чече албайт).
Жашоо (жашоо): тармак "дени сак" болсо, чечим кабыл алынат.
Сызыктуулук (сызыктуулук): операциялар атомдук катары бир тартипте "көрүнөт".
Бышыктыгы: кабыл алынган чечимдер артка кайтарылбайт (журнал/кворум менен коргоо).

4) Кворумдар, көпчүлүк жана кесилиштер

CFT дүйнөсүндө классика: кворум> N/2. Жазуулар жана лидерди шайлоо кворумдардын кесилишин колдонот, ошондуктан эки "валиддик" операция карама-каршы келбейт.
BFT дүйнөсүндө: 2f + 1 3f + 1 кворумдары жок дегенде f + 1 чынчыл түйүндөрдүн кесилишин камсыз кылат.

кесилиштеринин эрежеси: ар кандай эки quorum ≥ болушу керек 1 жалпы чынчыл түйүн (CFT) же ≥ f + 1 (BFT).

5) Мамлекеттик репликация (журнал + колдонуу)

• Snapshots (алгачкы жазууларды алып салуу/компакт-кийин абалын кесип).
• Журнал компакциясы жана лог-триим.
• Детерминизмди текшерүү (коддун/конфигурациялардын бирдей версиясы).

6) Лидердик жана лидердик эмес схемалар

Leadership (Raft, Multi-Paxos, ZAB): бир лидер жазууларды сериалдаштырат → психикалык жана операциялык жактан оңой, туруктуу лидерге жакшыраак.
Лидерсиз/мультилидердик (EPaxos, Caesar): лидерге көбүрөөк параллелизм жана толеранттуулук, бирок ишке ашыруу жана чыр-чатакты чечүү кыйыныраак; пайда командалардын майда чыр-чатактарынан көрүнүп турат.

7) Классикалык CFT-алгоритмдер

7. 1 Paxos/Multi-Paxos (жана практикасы)

Идея: эки этап (prepare/propose), акцептордун убадалары, мажоритардык кворумдар. Multi-Paxos "туруктуу лидер" калтырат жана "жылытуу" кийин (жаңы жазуулар үчүн) бир айлампага айлантат.

• Ийкемдүү, бирок ишке ашыруу үчүн татаал модель.
• Атайын жазуулар аркылуу кайра конфигурациялар (joint consensus).
• Иш жүзүндө - китепканалар/кыймылдаткычтар (Chubby/Spanner-муун).

7. 2 Raft

Окуу үчүн декомпозицияланган: лидерди тандоо, логдорду репликациялоо, кайра конфигурациялоо.

Election: туш келди тайм, шарттары боюнча добуш берүү; бир лидер.
AppendEntries: Strimit Records лидери, префикстин дал келүүсүн (индекс/терм), мажоритардык бекитүү боюнча коммитти көзөмөлдөйт.
Read-path: сызыктуу окуу үчүн lease-reads (күчтүү лидер менен) же read-index.
Reconfig: "биргелешкен конфигурация" (joint) - түйүндөр өтүүгө чейин эки кластерде добуш берет.

Артыкчылыктары: иштеп чыгуу үчүн жеңил/дебаг, күчтүү инварианттар тартиби. Кемчиликтери: лидер - басым чекити.

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

ZAB: лидер бүтүм, калыбына этабы, zxid (доору + индекси).
VRR: "түрлөрү" (views) баштапкы репликация менен, рух боюнча Multi-Paxos окшош.

8) Эмес/Multilider 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 стили)

proposal жана эки добуш менен тегерек (prevote/precommit).
Determinated validator сунуш, убакыт, жарым-жартылай синхрондоштуруу.
Ондогон/жүздөгөн валидаторлор менен permissioned/PoS тармактары үчүн жакшы.

9. 3 HotStuff (жана туундулары)

Кворум сертификаттары (QC) менен "пакеттерге" үч фазалуу схема бириктирилди.
Коммуникациялардын сызыктуу татаалдыгы, пакеттөөнү жана параллелдүү пайплайнизацияны колдоо, блокчейндерде ишке ашыруу үчүн ыңгайлуу (мисалы, Diem/Move-экосистема).
босого кол менен (threshold signatures) трафик азаят.

9. 4 PoW/сактоо консенсус (кыскача)

катуу мааниде BFT эмес, ыктымалдык конвергенция (эң көп иштеген чынжыр). Артыкчылыктары: жөнөкөйлүк/ачыктык; кемчиликтери: энергия, акыркы чейин ~ секунд-мүнөт.

10) Окуу: сызыктуу, ырааттуу жана кэш

Сызыктуу окуулар: активдүү lease же read-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/latency).

12. 3 куйруктары p99

Hot түйүндөрдү качуу (лидер дайыма жалгыз): мезгил-мезгили менен айлануу же жолдоочуларынын боюнча read-offload.
Контролдоо GC-тыныгуу (JVM/Go), PIN CPU, NUMA.

13) География жана топология

1 аймак, 3 зоналар: классикалык CFT кластер (N = 3/5).
2 Региондор: качуу - 1-1 бөлүү боюнча ишенимдүү кворум жок.
3 + аймактар: лидер "орто" же лидерсиз алгоритмдер; асинхрондук журнал менен аймактык прокси/жергиликтүү фронттор болушу мүмкүн.

14) Практикалык иштөө маселелери

14. 1 Snapshots жана калыбына келтирүү

Журналдын өлчөмү/операциялардын саны боюнча босого.
Снапшотту жаңы түйүндөргө өткөрүп берүү; контролдук суммаларды текшерүү.

14. 2 Мониторинг жүргүзүү

Лидерлик: ким лидер, канча убакыт (term/epoch) өзгөрдү.
Лаги: `append_latency`, `commit_index - applied_index`.

Quorum ден соолук: "көпчүлүк/2f + 1 тирүү?"

Журнал көлөмү/компакция ылдамдыгы, снапшот кезеги.
BFT үчүн: добуштардын үлүшү, кол койгондорду четке кагуу, QC кечиктирүү.

14. 3 Код коопсуздугу/шайкештиги

Зымдардагы протоколдун версиясы, журналдардын шайкештиги менен миграция.
тышкы таасирлер боюнча Fencing токендер (кара "бөлүштүрүлгөн блоктор"): лидерлик мөөнөтү (term) CRON/Jobs өткөрүп берүү.

15) Анти-үлгүлөрү

"Мода үчүн" консенсусту коюңуз, анда бир СУБД же сериалдаштыруусуз кворум окуу жетиштүү.
так чек жок CP жана AP аралаштыруу (CAP) → күтүлбөгөн UX.
PoW/PoS ондогон түйүндөр менен юридикалык максаттар үчүн баалоо (кыйын/кымбат).
Курамын өзгөртүүдө кайра конфигурацияны жана "кесилишкен кворумдарды" көз жаздымда калтыруу.
Жок 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-liby) vs өздүк ишке ашыруу.
6. реконфигурация: тез-тез? Бизге joint consensus жана миграция куралдары керек.
7. Интеграциялар: тышкы терс таасирлери - epoch/term боюнча fencing барбы?
8. Коопсуздук: түйүндөрдү аутентификациялоо, каналды шифрлөө, протоколдун версияларын көзөмөлдөө.
9. Test Playbook: partition, GC-stop, лидер kill, slow disk, clock skew.
10. Байкоо: лидердин/лагдардын/журналдын метриктери жана тобокелчиликтер орнотулган.

17) Мини-колдонмо: качан алуу керек

etcd/DC ичинде конфигурациялар/блоктор/координациялар үчүн Raft кластери.
ZooKeeper/ZAB буга чейин ZK менен байланышкан кызматтар үчүн (эски үйүлгөн, кезек, лидерлик).
Multi-Paxos жогорку адистештирилген системаларда даяр кызмат/китепкана аркылуу.
Гео-бөлүштүрүү жана командалардын аз карама-каршылыгы менен EPaxos.
Tendermint/HotStuff permissioned тармактар ​ ​ үчүн/PoS-лейер ондогон же жүздөгөн валидаторлор жана финалдык талаптар менен.
Dynamo-окшош/CRDT консенсус зарыл эмес, жана маанилүү жеткиликтүүлүгү/масштабы кийинки биригүү менен.

18) Interface мисалдар (псевдо)

18. 1 Коммит жазуу (Raft стили)

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-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 Биргелешкен конфигурация

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: Эмне Raft "жөнөкөй" Paxos?
A: Так декомпозиция, Логдун жана конфигурациянын түшүнүктүү инварианттары; ишке ашыруу жана коштоп жүрүү оңой.

Q: Кантип тез лидер жүктөп туруп окуп?
A: Follower-reads (ырааттуу) үчүн критикалык эмес, же сызыктуу үчүн lease-reads/read-index; кэш.

Q: эмне p99 өлтүрөт?
A: WAN-RTT, дисктик fsync, GC-бут, ысып кеткен лидер, "шашылыш саатта" чоң снапшоттор.

Q: кэш/каталог үчүн консенсус керекпи?
A: eventual consistency жетиштүү болсо - жок. Эгерде транзакциялык инварианттар талап кылынса - ооба.

20) Жыйынтыктар

Консенсус - катуу ырааттуулук жана тартипке келтирүү үчүн курал. Ийгиликсиздиктин моделине жана географияга негизделген алгоритмди тандаңыз; кворум кесилиштерин, туура ре-конфигурациясын, сызыктуу окууларды критикалык жерде жана байкоого жөндөмдүүлүгүн камсыз кылуу. тышкы таасирлер, snapshot жана журналдардын тартип үчүн fencing жөнүндө унутпа. Анда мамлекеттин репликациясын алдын ала айтууга болот, ал эми окуялар сейрек жана түшүнүктүү болот.