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

1) Консенсус дегеніміз не және ол не үшін қажет

Консенсус - іркілістер мен кідірістер кезінде бірнеше тораптар арасындағы мәндердің бір мәнін/бірізділігін келісу. Дәстүрлі түрде жағдайды репликалау міндеті шешіледі (State Machine Replication, SMR): жағдайлардың детерминирленген машинасы және операциялардың жалпы тәртібі бар.

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

2) Уақыт пен істен шығу моделі

2. 1 Уақыт үлгісі

Асинхронды желі: кідірістер шектелмейді; FLP теоремасы ⇒ қосымша болжамдарсыз safety және liveness кепілдендіру мүмкін емес.
Жартылай синхронды (практикада жиі): белгісіз T жүйесінен кейін жүйе «өзін синхронды» жүргізеді - көптеген алгоритмдер (Raft, Paxos) дәл осыған сүйенеді.
Синхронды: каналдарға қатаң тайм-лимиттер (арнайы желілерден/ТҚП-дан басқа, азық-түлікте сирек).

2. 2 Істен шығу моделі

Crash-fault tolerant (CFT): түйіндер құлауы/ілінуі мүмкін, бірақ өздерін қасақана ұстамайды.
Byzantine-fault tolerant (BFT): тораптар хабарларды жалған/қолдан жасай алады. Византиялықтарға төзімділік үшін 3f + 1 торап талап етіледі.

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

Safety (қауіпсіздік): қарама-қайшы емес (екі дұрыс торап әртүрлі мәндерді шешпейді).
Liveness (өміршеңдік): егер желі «сау» болса, шешімге қол жеткізіледі.
Сызықтанушылық (сызықтық): операциялар бірыңғай тәртіппен атомарлық ретінде «көрінеді».
Ұзақтығы: қабылданған шешімдер қайтарылмайды (журналмен/кворуммен қорғау).

4) Кворумдар, көпшілік және қиылыстар

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

Қиылысу ережесі: кез келген екі кворумда ≥ 1 ортақ адал торап (CFT) немесе ≥ f + 1 (BFT) болуы тиіс.

5) Жай-күйді репликалау (журнал + қолдану)

• Snapshots (күйді кесу, одан кейін ерте жазбаларды жоюға/компактылауға болады).
• Журнал компакциясы және лог-трим.
• Детерминизмді тексеру (кодтың/конфигурацияның бірдей нұсқасы).

6) Көшбасшылық және көшбасшылық емес схемалар

Көшбасшылар (Raft, Multi-Paxos, ZAB): бір көшбасшы жазбаларды сериалдайды → ментальді және операциялық оңай, тұрақты көшбасшыда latency жақсы.
Лидерсіз/мультилидерлік (EPaxos, Caesar): көшбасшыға көбірек параллелизм мен толеранттылық, бірақ іске асыру және жанжал-шешу қиынырақ; пайда командалардың шағын қайшылықтары кезінде көрінеді.

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

7. 1 Paxos/Multi-Paxos (және практикалар)

Идея: екі фаза (prepare/propose), акцепторлардың уәделері, мажоритарлық кворумдар. Multi-Paxos «тұрақты көшбасшыны» қалдырады және «жылытудан» кейін операцияларды бір кезеңді (жаңа жазбалар үшін) айналдырады.

• Икемді, бірақ іске асыру үшін күрделі модель.
• Ерекше жазбалар арқылы қайта конфигурациялау (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 стиль)

Proposal және екі дауыс беру раундтары (prevote/precommit).
Детерминирленген ұсынушы валидатор, тайм-ауттар, ішінара синхрондау.
Permissioned/PoS-жүйелері үшін ондаған/жүздеген валидаторлары бар.

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

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

9. 4 PoW/жинақтау консенсусы (қысқаша)

Қатаң мағынада BFT емес, ықтималдық конвергенциясы (ең үлкен жұмыс тізбегі). Қасиеттері: қарапайымдылық/ашықтық; кемшіліктері: энергия, ~ секунд-минут.

10) Оқу: сызықтық, тізбекті және кэштелген

Сызықтық оқу: белсенді lease немесе read-index арқылы көшбасшы (Raft) → кворум арқылы растау.
Дәйекті: кез келген тораптан оқи аласыз, бірақ жаңалық кепілдіксіз.
Follower reads: әлсіз талаптар кезінде жарамды; кэштер үшін - ok.

11) Ре-конфигурация (кластер құрамын ауыстыру)

Екі жабылатын конфигурацияны (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 қалдықтары

Ыстық түйіндерден аулақ болыңыз (көшбасшы үнемі жалғыз): мерзімдік ротация немесе фолловерлерге read-offload.
GC-үзілісті (JVM/Go), CPU, NUMA шыңдарын бақылаңыз.

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

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

14) Пайдаланудың практикалық мәселелері

14. 1 Снапшоттар және қалпына келтіру

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

14. 2 Мониторинг

Көшбасшылық: кім көшбасшы, қанша мерзім (term/epoch) өзгерді.
Лаги: `append_latency`, `commit_index - applied_index`.

Кворум-денсаулық: «көпшілігі тірі ме/2f + 1?»

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

14. 3 Кодтың қауіпсіздігі/келісілуі

Журналдардың үйлесімділігімен сым, көші-қон хаттамасының нұсқалығы.
Сыртқы әсерлердегі Fencing-токендер («Таратылған блоктарды» қараңыз): көшбасшылық мерзім (term) CRON/джобқа беріледі.

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. Тест-плейбуктер: 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) Интерфейстердің мысалдары (жалған)

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: Неге екі түйін және тай-брейкер пайдаланбаңыз?
А: Үшінші төрешісіз екі торап бөлу кезінде кворум бермейді. 3 (CFT) немесе 3f + 1 (BFT) ≥ қажет.

Q: Raft Paxos «оңай» деген не?
А: Анық декомпозиция, логтың және конфигурацияның түсінікті инварианттары; іске асыру және сүйемелдеу оңай.

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

Q: p99 өлтіреді?
A: WAN-RTT, дискілік fsync, GC-табандар, қызған көшбасшы, «қарбалас сағатта» үлкен снарядтар.

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

20) Қорытынды

Консенсус - қатаң келісуге және реттеуге арналған құрал. Бас тарту үлгісі мен географияға сүйене отырып, алгоритмді таңдаңыз; кворумды қиылысуды, дұрыс ре-конфигурацияны, сызықтық оқуларды, бұл өте қиын жерде және бақылау мүмкіндігін қамтамасыз етіңіз. Сыртқы әсерлер, снапшоттар және журналдардың тәртібі үшін fencing туралы ұмытпаңыз. Сонда жағдайды репликалауды болжауға болады, ал оқыс оқиғалар - сирек және түсінікті болады.