Алгоритмҳои консенсус

1) Консенсус чист ва чаро он лозим аст

Консенсус - Арзиши якхела/пайдарҳамии арзишҳоро дар байни гиреҳҳои сершумор барои нокомӣ ва таъхирҳо гуфтушунид кунед. Чун анъана, масъалаи такрори давлатӣ (Такрори давлатии мошин, SMR) ҳал карда мешавад: мошини детерминистии давлатӣ ва тартиби умумии амалиёт мавҷуд аст.

• Консенсус (SMR): тартиби ягонаи умумии фармонҳо → нигоҳдорӣ/бақайдгирии хаттӣ, метамаълумоти кластерӣ, ҳамоҳангсозони транзаксионӣ.
• Амалиёти кворум бидуни фармоиши умумӣ (ба монанди Динамо, CRDT): имкон медиҳад, ки фарқият ва якҷояшавии минбаъда; консенсусро дар ҷое, ки сериализатсияи глобалӣ лозим аст, иваз накунед.

2) Модели вақт ва нокомӣ

2. 1 Модели вақт

Шабакаи асинхронӣ: таъхирҳо номаҳдуданд; теоремаи FLP ⇒ бидуни фарзияҳои иловагӣ ҳам бехатарӣ ва ҳам зиндагиро кафолат додан ғайриимкон аст.
Қисман синхронӣ (аксар вақт дар амал): пас аз T номаълум, система "ҳамоҳанг" мекунад - аксари алгоритмҳо (Raft, Paxos) ба ин такя мекунанд.
Синхронӣ: маҳдудиятҳои қатъии каналҳо (кам дар фурӯш, ба истиснои шабакаҳои махсус/PRT).

2. 2 Модели нокомӣ

Таҳаммулпазирии садама (CFT): Гиреҳҳо метавонанд афтанд/овезанд, аммо бадгӯӣ намекунанд.
Таҳаммулпазирии Византия (BFT): Гиреҳҳо метавонанд паёмҳои дурӯғ/ғалат дошта бошанд. Барои таҳаммулпазирӣ ба f Византия 3f + 1 гиреҳҳоро талаб мекунад.

3) Хусусиятҳои консенсус

Бехатарӣ: пайдарҳамӣ (ду гиреҳи дуруст арзишҳои гуногунро ҳал карда наметавонанд).
Зиндагӣ: Агар шабака "солим" бошад, ҳалли он ба даст меояд.
Linearizability (linearity): амалиётҳо дар як тартиб ҳамчун "атом" дида мешаванд.
Давомнокӣ: қарорҳои қабулшуда баргардонида намешаванд (ҳифзи лог/кворум).

4) Кворумҳо, аксарият ва чорроҳаҳо

Дар ҷаҳони CFT, классикӣ: кворум> N/2. Сабтҳо ва интихоботи пешво убури кворумро истифода мебаранд, аз ин рӯ ду амалиёти "дуруст" ихтилоф надоранд.
Дар ҷаҳони BFT: кворумҳо 2f + 1 аз 3f + 1 буриши ҳадди аққал f + 1 гиреҳҳои ростқавлро таъмин мекунанд.

Қоидаи убур: Ҳар ду кворум бояд ≥ 1 гиреҳи одилона (CFT) ё ≥ f + 1 (BFT) дошта бошанд.

5) Такрори давлатӣ (log + ариза)

• Суратҳо (як буридаи давлат, ки пас аз он сабтҳои барвақтро нест кардан/тартиб додан мумкин аст).
• Фишурдани журнал ва триеми журнал.
• Санҷишҳои детерминизм (ҳамон рамз/нусхаи конфигуратсия).

6) Схемаҳои роҳбарӣ ва роҳбарӣ

Роҳбарият (Raft, Multi-Paxos, ZAB): як пешво сабтҳоро ба осонӣ аз ҷиҳати ақлӣ ва амалиётӣ сабт мекунад, дертар ба раҳбари устувор.
Пешво/пешвои бисёрҷониба (EP axos, қайсар): параллелизм ва таҳаммулпазирии бештар ба роҳбар, аммо татбиқи душвортар ва ҳалли низоъ; фоида бо муноқишаҳои хурди дастаҳо намоён аст.

7) Алгоритмҳои классикии CFT

7. 1 Paxos/Multi-Paxos (ва амалия)

Идея: ду марҳила (омода/пешниҳод кунед), ваъдаҳои қабулкунандагон, кворумҳои аксарият. Multi-Paxos пас аз "гарм шудан" як "пешвои устувор" -ро тарк мекунад ва амалиётро ба як давр (барои вурудоти нав) табдил медиҳад.

• Татбиқи модел тағйирпазир, вале душвор аст.
• Конфигуратсияҳо тавассути вурудоти махсус (ризоияти муштарак).
• Дар амал китобхонаҳо/муҳаррикҳо (насли Chubby/Spanner).

7. 2 Рафт

Барои омӯзиш ҷудо карда шудааст: интихоби пешво, нусхабардории журнал, конфигуратсияи дубора.

Интихобот: танаффуси тасодуфӣ, овоздиҳии мӯҳлатӣ; як пешво дар як мӯҳлат.
Замимаҳо: пешво сабтҳоро ҷараён медиҳад, мувофиқати префиксро (индекс/истилоҳ) назорат мекунад, ба аксарияти ислоҳот вогузор мекунад.
Роҳи хондан: хониши иҷора (бо пешвои қавӣ) ё индекси хондан барои хондани хатӣ.
Reconfig: "муштарак" - гиреҳҳо пеш аз гузариш дар ду гурӯҳ овоз медиҳанд.

Тарафдор: таҳия/ислоҳ кардан осонтар, инвариантҳои қавӣ. Омӯз: Роҳбар нуқтаи фишор аст.

7. 3 ZAB (Пахши атомии зоопарк )/Такрори намоишӣ (VRR)

ZAB: роҳбар транзаксияҳо, марҳилаи барқароршавӣ, zxid (epoch + index) -ро пахш мекунад.
VRR: "нуқтаи назар" бо нусхаи ибтидоӣ, ки ба Multi-Paxos дар рӯҳ монанд аст.

8) CFT-ҳои пешво/бисёр пешво

8. 1 ДМ axos

Роҳбари доимӣ вуҷуд надорад: ягон гиреҳ метавонад фармонро оғоз кунад.
Гурӯҳҳои муноқиша қисман фармоиш мегиранд; бидуни низоъ - ба 1-2 РТТ дар маҳал ӯҳдадор шавед.
Фоида дар тақсимоти гео бо муноқишаҳои кам, аммо вобастагии мураккаб/рамзҳои графикӣ.

8. 2 қайсар, Менсиюс

Тағиротҳое, ки таъхир/мувозинат ва амалиёти WAN-ро оптимизатсия мекунанд.

9) Алгоритмҳои BFT ва оилаи POS

9. 1 PBFT (BFT амалӣ)

Се марҳила (пешакӣ тайёр кардан/тайёр кардан/содир кардан), 3f + 1 гиреҳро талаб мекунад.
Таъхири кам дар шабакаҳои маҳаллӣ, роҳҳои бисёрқабата ва паёмҳои O (N ²).

9. 2 Tendermint (услуби BFT-POS)

Давраҳо бо пешниҳод ва ду овоз (пешгирӣ/пешакӣ).
Пешниҳоди муайянкунандаи валидатор, вақтҳо, синхронизатсияи қисман.
Хуб барои шабакаҳои иҷозатдодашуда/POS бо даҳҳо/садҳо валидаторҳо.

9. 3 Stuff (ва ҳосилаҳои)

Нақшаи се марҳила ба "бастаҳо" бо шаҳодатномаҳои кворум (QC) муттаҳид карда шудааст.
Мураккабии хаттии алоқа, дастгирии бастабандӣ ва қубурҳои мувозӣ барои татбиқ дар blockchains қулай аст (масалан, экосистемаи Diem/Move).
Бо имзои ҳадди аксар, трафик кам мешавад.

9. 4 Консенсуси ПВт/кумулятивӣ (мухтасар)

На BFT ба маънои қатъӣ, балки конвергенсияи эҳтимолӣ (занҷир бо кори бештар). Афзалиятҳо: содда/ошкоро; камбудиҳо: энергия, ~ сонияҳо то ба охир.

10) мехонад: хатӣ, пайдарпай ва кэш

Хондани хатӣ: пешво бо иҷораи фаъол ё тавассути индекси хониш (Raft) → тасдиқ тавассути кворум.
Пайдарпаӣ: аз ҳар гиреҳ хонда мешавад, аммо бидуни кафолати тару тоза.
Пайрав мехонад: мувофиқи талаботи заиф иҷозат дода мешавад; барои кэш - хуб.

11) Конфигуратсияи дубора (тағир додани таркиби кластер)

Ду конфигуратсияи такрорӣ (консенсуси муштарак) -ро талаб мекунад: ҳама гуна кворумҳои ҳарду конфигуратсияро бидуни "сӯрохиҳо" иҷро мекунанд.
Дар як вақт илова/хориҷ кунед, андозаи кворумро риоя кунед.
Интиқоли роҳбарӣ таваққуфро коҳиш медиҳад.

12) Иҷро ва танзими

12. 1 Таъхирҳо

Алгоритмҳои роҳбарӣ: 1 РТТ барои навиштан (бо пешвои устувор) + нусхабардорӣ.
Тақсимоти ҷуғрофӣ: WAN RTT бартарӣ дорад → истифодаи минтақаҳои маҳаллӣ + нусхабардории байниминтақавӣ ё равишҳои EP axos/Fuff.

12. 2 Гузариш

Бастабандӣ (гурӯҳбандии фармонҳо), параллелии замимаҳо, ҳофизаи саҳифа, замимаи параллелӣ (ҳангоми ба кор даровардани амалиёт).
Дискҳо: NVM .e/Log дар дастгоҳи алоҳида, 'O _ DIRECT '/AIO, фосилаи калони' fsync 'бо маҳдудиятҳои SLA (созиш/дарозмуддат).

12. 3 думи p99

Аз гиреҳҳои гарм канорагирӣ кунед (ҳамеша як пешво ҳаст): гардиши даврӣ ё бори хондан ба пайравон.
Монитор GC таваққуф мекунад (JVM/Go), pins CPU, NUMA.

13) Ҷуғрофия ва топологияҳо

1 минтақа, 3 минтақа: кластери классикии CFT (N = 3/5).
2 минтақа: канорагирӣ кунед - дар тақсимоти 1-1 кворуми боэътимод мавҷуд нест.
3 + минтақаҳо: пешво дар алгоритмҳои "миёна" ё пешво; проксиҳои минтақавӣ/ҷабҳаҳои маҳаллӣ бо сабти асинхронӣ имконпазиранд.

14) Масъалаҳои амалии фаъолият

14. 1 Сурат ва барқароршавӣ

Ҳадди ниҳоӣ аз рӯи андозаи маҷалла/шумораи амалиётҳо.
Гузаронидани сурат ба гиреҳҳои нав; Санҷиши чекҳо.

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

Роҳбарият: кӣ пешво аст, чанд истилоҳ (истилоҳ/давра) тағир ёфтааст.
Лаги: 'замима _ дермонӣ', 'overit _ index - applied_index'.

Саломатии кворум: "аксарият зиндаанд/2f + 1?"

Андозаи журнал/суръати фишурдасозӣ, навбати лаҳзаҳо.

Барои BFT: ҳиссаи овозҳо, имзокунандагони партовҳо, таъхири QC

14. 3 Амният/Мувофиқати Кодекс

Интиқоли протокол дар сим, муҳоҷират бо мутобиқати журнал.
Нишонаҳои тавораҳо ба эффектҳои беруна (нигаред ба "Қулфҳои тақсимшуда"): вақти пешбар (мӯҳлат) барои гузариш ба CRON/ҷойҳои корӣ.

15) Анти-намунаҳо

Консенсусро "ба хотири мӯд" гузоред, ки дар он як DBMS ё кворум бидуни сериализатсия мехонад.
Омезиши CP ва AP бидуни ҳудуди дақиқ (CAP) → UX пешгӯинашаванда.
Барои вазифаҳои корхона бо даҳҳо гиреҳҳо (душвор/гарон) аз ҳад зиёд баҳо диҳед.
Ҳангоми тағйир ёфтани таркиб, конфигуратсия ва "кворумҳои ҳамҷояшаванда" -ро нодида гиред.
Набудани монеаи хондан (иҷора/хондан-индекс) → хондани ифлос.
Кластерҳои 2-гиреҳро иҷро кунед (аксарият нестанд).
Баҳодиҳии дискҳо ва fsync: "ҳама чиз дар хотира парвоз мекунад" - то бозоғозии аввал.

16) Рӯйхати назоратӣ

1. Модели нокомӣ: CFT (суқут) ё BFT (зараровар)?
2. Ҷуғрофия: як минтақа/се минтақа ё WAN? РТТ қарор медиҳад.
3. Хондани семантика: оё хонишҳои хатӣ заруранд? Иҷора/хондан-индекс/пайгирӣ.
4. Сарборӣ: интизориҳо аз ҷониби p50/p99, интиқол; оё роҳбарии бисёрҷониба лозим аст.
5. Мураккабии амалиётӣ: муҳаррики китобхона/берун аз раф (etcd/ZK/Consul/Raft-libs) против татбиқи маҳаллӣ.
6. Бозсозӣ: Зуд-зуд? Мо ба ризоияти муштарак ва воситаҳои муҳоҷират ниёз дорем.
7. Интегратсияҳо: Таъсири тарафҳои беруна - оё деворҳо аз рӯи давра/истилоҳ вуҷуд доранд?
8. Амният: аутентификатсияи мизбон, рамзгузории канал, назорати версияи протокол.
9. Китобҳои санҷишӣ: қисм, GC-stop, куштани пешво, диски суст, skew соат.
10. Мушоҳида: Нишондиҳандаҳои пешво/қафо/журнал ва ҳушдор муқаррар карда мешаванд.

17) Мини-роҳнамо: кай бояд чӣ кор кард

кластери etcd/Raft барои конфигуратсияҳо/қуфлҳо/ҳамоҳангсозӣ дар доираи DC.
Зоопарк/ZAB барои хидматҳое, ки аллакай ба ZK пайвастанд (стекҳои кӯҳна, навбатҳо, роҳбарӣ).
Multi-Paxos тавассути хидмати/китобхонаи тайёр дар системаҳои баландихтисос.
EP axos барои тақсимоти гео ва муноқишаи ками фармондеҳӣ.
Tendermint/Hotstuff барои шабакаҳои иҷозатдодашуда/қабати POS бо даҳҳо то садҳо валидаторҳо ва талаботҳои ниҳоӣ.
Вақте ки консенсус лозим нест, ба монанди динамо/CRDT, аммо дастрасӣ/миқёс бо якҷояшавии минбаъда муҳим аст.

18) Намунаҳои интерфейсҳо (псевдо)

18. 1 Сабти супоришҳо (услуби Рафт)

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 Индекси хондан барои хониши хатӣ (Рафт)

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

Савол: Чаро ду гиреҳ ва галстукро истифода набаред?
A: Ду гиреҳ бе ҳаками сеюм дар тақсимшавӣ кворум намедиҳанд. Ба шумо ≥ 3 (CFT) ё 3f + 1 (BFT) лозим аст.

Савол: Raft Paxos "соддатар" чист?
A: Ҷудошавии тоза, инвариантҳои фаҳмо аз журнал ва конфигуратсия; татбиқ ва нигоҳдорӣ осонтар аст.

Савол: Шумо бе бор кардани роҳбар чӣ гуна зуд мехонед?
A: Пайравони (пайдарпай) барои танқидӣ ё иҷора-хондан/хондан-индекс барои хатӣ; кэш.

Савол: Чӣ p99-ро мекушад?
A: WAN-RTT, fsync диск, GC-истгоҳҳо, пешвои аз ҳад зиёд гармшуда, лаҳзаҳои калон дар соати шитоб.

Савол: Оё кэш/каталог ба консенсус ниёз дорад?
Ҷ: Агар мувофиқати воқеии кофӣ - не. Агар инвариантҳои транзаксионӣ талаб карда шаванд, ҳа.

20) Натиҷаҳо

Консенсус воситаи мутобиқати қатъӣ ва фармоиш мебошад. Алгоритмро дар асоси модели нокомӣ ва ҷуғрофия интихоб кунед; таъмин намудани убури кворум, конфигуратсияи дуруст, хонишҳои хатӣ, ки дар куҷо танқидӣ ва мушоҳидашаванда мебошанд. Дар бораи тавораҳо барои эффектҳои беруна, лаҳзаҳо ва интизоми маҷалла фаромӯш накунед. Он гоҳ такрори давлатӣ пешгӯишаванда хоҳад буд ва ҳодисаҳо нодир ва фаҳмо хоҳанд буд.