Ալգորիթմներ
1) Ի՞ նչ է համաձայնությունը և ինչո՞ ւ է այն անհրաժեշտ։
Համաձայնությունը նույն արժեքն/արժեքների հաջորդականությունն է մի քանի հանգույցների միջև ձախողումների և ձերբակալությունների ժամանակ։ Ավանդաբար լուծվում է վիճակի վերարտադրման խնդիրը (State Machine Replant, SMR) 'կան դետերմինացված պետության մեքենա և վիրահատությունների ընդհանուր կարգ։
Տարբերեք
Համաձայնություն (SMR) 'թիմերի միակ տոտալ կարգը նշված է գծային պահարան/108, մետատվված բջիջներ, գործարքային կոորդինատորներ։
Կվորումի վիրահատությունները առանց տոտալ կարգի (Systo-նման, CRDT) թույլ են տալիս դիվերսիֆիկացիան և հաջորդ միաձուլումը։ չեն փոխարինում համաձայնությունը այնտեղ, որտեղ անհրաժեշտ է գլոբալ հեռուստացույցը։
2) Ժամանակի և ձախողումների մոդել
2. 1 Ժամանակի մոդել
Ասինխրոն ցանցը 'ուշացումները անսահմանափակ են։ FLP-ի թեորեմը անհնար է երաշխավորել ինչպես safety, այնպես էլ liveness առանց լրացուցիչ ենթադրությունների։
Մասամբ սինխրոն (հաճախ գործնականում), անհայտ T համակարգից հետո «պահում է» սինխրոն, ալգորիթմների մեծամասնությունը (Raft, Paxos) ապավինում է հենց դրան։
Սինխրոն 'կոշտ խաղային լիմիտներ ալիքների վրա (հազվադեպ երկարության մեջ, բացի հատուկ ցանցերից/PSA)։
2. 2 Մերժումների մոդել
Crash-frontoler.ru (CFT) ՝ միգրանտները կարող են ընկնել/կախվել, բայց չարամիտ չեն վարվում։
Byzantine-frontoler.ru (BFT) ՝ միգրանտները կարող են ստել/կեղծել հաղորդագրությունները։ Անհրաժեշտ է 3f + 1 հանգույց, որպեսզի հանդուրժողականության համար f վիզանտիկ։
3) Հատկություններ
Safety (անվտանգություն) 'ոչ հակասական (երկու ճիշտ հանգույցները չեն լուծի տարբեր արժեքներ)։
Liveness (կենդանի): Եթե «առողջ» ցանցը, լուծումը հասնում է։
Լինարիզացիան (գծայնությունը) 'վիրահատությունները «տեսնում են» որպես ատոմային միավորներ։
Երկարակեցություն ՝ վերջնական լուծումները չեն արձագանքում (պաշտպանություն ամսագրից/քվորումից)։
4) Քվորումները, մեծամասնությունը և հատումը
CFT-աշխարհում դասական 'quorum> N/2։ Առաջնորդի ձայնագրությունները և ընտրությունները օգտագործում են կվորումի հատումը, այնպես որ երկու «վալիդային» վիրահատությունները չեն հակամարտվում։
BFT-աշխարհում, 2.f + 1-ից 3f + 1-ը ապահովում է առնվազն f + 1 ազնիվ հանգույցների խաչմերուկը։
Փոխպատվաստման կանոնը 'ցանկացած երկու քվորումա պետք է ունենա 241 ընդհանուր ազնիվ հանգույց (CFT) կամ www.f + 1 (BFT)։
5) Պետության կրկնօրինակումը (ամսագիր + կիրառում)
Թիմերը տեղադրվում են ցուցիչների հետ (ինդեքսը/դարաշրջան)։ Սկզբունքը հետևյալն է. <<Սկզբում համակարգել ձայնագրությունը ամսագրում (commit), ապա դետերմինացված կիրառել վիճակի վրա>>։ Աճը վերահսկելու համար նրանք անում են
Կեղտաջրերը (վիճակը, որից հետո վաղ գրառումները կարելի է հեռացնել/սկոմպակացնել)։
Ամսագրի կոմպակտը և լոգ-տրիիմ։
Դեթերմինիզմի ստուգումները (կոդի/դելիգների նույն տարբերակը)։
6) Առաջնորդական և ոչ կրոնական սխեմաներ
Առաջնորդները (Raft, Multi-Paxos, ZAB). մեկ առաջնորդը սերիալիզացնում է կոմպոզիաների ձայնագրությունները ավելի հեշտ, ավելի լավ, քան latency կայուն առաջնորդի վրա։
Անբաժան/բազմաբնույթ (EPaxos, Caesar) 'ավելի շատ զուգահեռականություն և հանդուրժողականություն առաջնորդին, բայց ավելի բարդ է ռուսական և հակամարտական լուծումը։ շահույթը տեսանելի է փոքր թիմերի հակամարտություններում։
7) Դասական CFT ալգորիթմներ
7. 1 Paxos/Multi-Paxos (պրակտիկա)
Գաղափարը 'երկու փուլեր (wwww.pare/propose), acceptors խոստումները, magoraritic kworms։ Multi-Paxos-ը թողնում է «կայուն առաջնորդը» և վերածում է վիրահատությունները միակողմանի (նոր ձայնագրությունների համար) «տաքացումից» հետո։
Հատկություններ
Ճկուն, բայց բարդ մոդել իրականացման համար։
Ռե կազմաձևը հատուկ ձայնագրությունների միջոցով (joint consensus)։
Գործնականում գրադարաններ/շարժիչներ (Chubby/Spanner սերունդ)։
7. 2 Raft
Դեկոմոզացված է ուսուցման համար 'առաջնորդի ընտրություն, լոգարանների կրկնօրինակումը, ռենտգենյան կազմաձևումը։
Էլմս 'պատահական թայմաուտներ, քվեարկություն տերմիններով։ մեկ առաջնորդ ժամանակի ընթացքում։
AppendenTries: առաջնորդը սթրիմ է ձայնագրությունները, հետևում է նախածննդյան (ինդեքսը/term) համընկնմանը, որը հաշվում է մագնիսական ամրագրման միջոցով։
Read-path: least-reads (ուժեղ առաջնորդով) կամ read-index գծային ընթերցումների համար։
Reconfect: «Միասին կազմաձևը» (joint) - ռուսական քվեարկում են երկու կլաստերներում մինչև անցումը։
Պլյուսներ 'ավելի հեշտ զարգացման/դեբագայի, ուժեղ ինվարիատորների համար։ Մինուսները 'առաջնորդը ճնշման կետն է։
7. 3 ZAB (ZooKeeper Atomic Broadcast) / Viewstamped Replication (VRR)
ZAB: առաջնորդը հեռացնում է գործարքները, վերականգնում, zxid (դարաշրջան + ինդեքս)։
VRR: «տեսակներ» (views) առաջնային կրկնօրինակով, նման է Multi-Paxos ոգով։
8) Nelider/mulider CFT
8. 1 EPaxos
Չկա մշտական առաջնորդ, ցանկացած հանգույց կարող է ստեղծել թիմը։
Հակամարտական թիմերը ստանում են մասնակի կարգ։ Բեզոնֆինային համայնքները 1-2 RTT տեղական են։
Երկրաչափության հաղթանակը ցածր կոնֆլիկտով, բայց բարդ կախվածությունների/գրաֆիկների։
8. 2 Caesar, Mencius
Տատանումները, որոնք օպտիմիզացնում են ուշացումները/հավասարակշռությունը և աշխատում WAN-ում։
9) BFT ալգորիթմներ և PoS ընտանիք
9. 1 PBFT (Practical BFT)
Երեք փուլերը (pre-pare/www.pare/commit) պահանջում են 3f + 1 հանգույց։
Տեղական ցանցերում ցածր լատենտ, ճանապարհներ բազմաբնույթ և O (N) հաղորդագրությունների վրա։
9. 2 Tendermint (BFT-PoS ոճ)
Proposal-ով և երկու քվեարկությամբ (www.vote/precommit)։
Դետերմինացված վաիդատոր-առաջարկող, թայմ-աուտներ, մասնակի սինխրոն։
Լավ է permissioned/PoS ցանցերի համար տասնյակ/հարյուրավոր վալիդատորների հետ։
9. 3 HotStuff (և ածանցյալները)
Միավորված է եռաչափ սխեմա «փաթեթների» մեջ, որոնք ունեն քվորումային հավաստագրեր (QC)։
Հաղորդակցությունների գծային բարդությունը, փաթեթավորման և զուգահեռ պլայնիզացիայի աջակցությունը, հարմար է բլոկչեյններում իրականացումների համար (օրինակ ՝ Medem/Move էկոհամակարգը)։
Շեմի ստորագրություններով (threshold signatures) նվազում է։
9. 4 PoW/կուտակային համաձայնություն (կարճ)
Ոչ թե BFT-ը խիստ իմաստով, այլ հավանական փոխակերպումը (շղթան ամենամեծ աշխատանքով)։ Արժանապատվություն 'պարզություն/բացություն; թերությունները 'էներգիա, վերջնակետից մի քանի րոպե առաջ։
10) Ընթերցումներ ՝ գծային, հետևողական և քեշված։
Գծային ընթերցումներ 'առաջնորդը ակտիվ ձախ կամ read-index (Raft) միջոցով հաստատվում է քվորումի միջոցով։
Հետևողական 'կարելի է կարդալ ցանկացած հանգույցից, բայց առանց թարմության երաշխիքների։
Follower reads: Թույլատրելի է թույլ պահանջներով։ քեշի համար լավ է։
11) Ռե կազմաձևը (կոմպոզիցիայի փոփոխությունը)
Պահանջում է երկու արգելափակված միգրացիաներ (joint consensus), ցանկացած համայնքներ անցնում են երկու խմբակցությունների քվորմաններ առանց «ծխի»։
Ավելացրեք/հանեք մեկը, պահեք կվորումի չափը։
Առաջնորդության տեղափոխումը (leadership transfer) նվազեցնում է դադարները։
12) Արտադրողականությունը և թյունինգը
12. 1 Հետաձգում
Առաջնորդական ալգորիթմները ՝ 1 RTT ձայնագրման (կայուն առաջնորդով) + կրկնօրինակումը։
Երկրաչափություն ՝ WAN RTT-ն գերակշռում է տեղական շրջանները օգտագործեք + քրոս-երկրորդական ռեպլիկացիա կամ EPaxos/HotStuff մոտեցումներ։
12. 2 Անցումային
Batching (թիմերի խումբ), զուգահեռ AppendendEntries-ը, ամսագրի լանդշաֆտը, զուգահեռ օգտագործումը (երբ վիրահատությունները հաղորդակցվում են)։
Սկավառակներ ՝ NVMe/Ամսագիրը առանձին սարքի վրա, «O _ III »/AIO, մեծ« fsync »- ինտերվալ SLA սահմանափակումներով (փոխզիջում durability/latency)։
12. 3 Պոչեր p99
Խուսափեք տաք հանգույցներից (առաջնորդը միշտ մենակ է) 'պարբերական նավարկություն կամ read-ensload ֆոլլովերների վրա։
Վերահսկեք GC դադարները (JVM/Go), CPU, NUMA։
13) Երկրագրությունը և տեղաբանությունը
1 շրջան, 3 գոտի ՝ դասական CFT կլաստեր (N = 3/5)։
Երկու տարածաշրջաններ 'խուսափեք, չի ստացվում հուսալի քվորում, երբ բաժանվում է 1-1։
3 + տարածաշրջաններ 'առաջնորդը «մեջտեղում» կամ անթերի ալգորիթմներ; հնարավոր են տարածաշրջանային ֆորումներ/տեղական ճակատներ ասինխրոն ամսագրով։
14) Գործելու գործնական հարցեր
14. 1 Դիպուկահարներ և վերականգնումներ
Ամսագրի չափի շեմն/վիրահատությունների քանակը։
Սարքավորումների փոխանցումը նոր հանգույց է։ համապատասխան գումարների ստուգում։
14. 2 Lenta.ru
Առաջնորդությունը 'ով է առաջնորդը, որքան ռուսական (term/epoch) փոխվել է։
Лаги: `append_latency`, `commit_index - applied_index`.
Քվորումի առողջությունը '«արդյո՞ ք մեծամասնությունը/2f + 1»։
Ամսագրի չափսը/կոմպակտի արագությունը, դիպուկահարների հերթը։
BFT-ի համար, ձայների մասը, բաժանորդներին, QC-ի ուշացումները։
14. 3 Անվտանգություն/կոդի համաձայնություն
Սարքի տարբերությունը, որը կապված է ամսագրերի համատեղելիության հետ։
Fencing-հոսանքները արտաքին էֆեկտների վրա (տե՛ ս «Բաշխված արգելափակումները») 'առաջնորդական ժամանակահատվածը (term) փոխանցել CBS/ջոբի։
15) Anti-patterna
Ներդնել «հանուն նորաձևության» համաձայնությունը այնտեղ, որտեղ կա մեկ ենթաօրենսդրություն կամ կվորումի ընթերցումներ առանց շարադրության։
CP և AP խառնելը առանց հստակ սահմանների (CAP) բացատրվում է UX-ի անկանխատեսելի։
Գերագնահատել PoW/PoS-ը կորպորատիվ խնդիրների համար տասնյակ հանգույցների հետ (դժվար/թանկ)։
Անտեսել ռե-կազմաձևը և «հատվող կվորումները» կազմը փոխելիս։
Read-barrier (lead/read-index) բացակայությունը բացատրում է «կեղտոտ» կարդալը։
Սկսեք երկու հանգույց կլաստերներ (մեծամասնություն չկա)։
Սկավառակների և fsync-ի թերագնահատումը. <<հիշողության մեջ ամեն ինչ թռչում է>> 'մինչև առաջին վերականգնումը։
16) Ընտրության թուղթ
1. Ձախողումների մոդելը 'CFT (ներկեր) կամ BFT (չարամիտ)։
2. Երկրագրությունը 'մեկ տարածք/երեք գոտի կամ WAN։ RTT-ն լուծում է։
3. Ընթերցանության իմաստը 'արդյո՞ ք գծային ընթերցանության կարիք կա։ Least/read-index/follover-rids։
4. Մոսկվա: Սպասումներ p50/p99, throughput; արդյո՞ ք մուլտֆիլմի առաջնորդությունը անհրաժեշտ է։
5. Վիրահատական բարդություն 'գրադարան/պատրաստի շարժիչ (etcd/ZK/Consul/Raft-liba) սեփական շարժիչ։
6. Ռեքոնչիչենկո 'հաճախակի։ Անհրաժեշտ է joint consensus և միգրացիայի գործիքներ։
7. Տե՛ ս ՝ արտաքին կողմնակի ազդեցությունները 'արդյո՞ ք գոյություն ունի epoch/term։
8. Անվտանգությունը 'հանգույցների վավերացումը, ջրանցքի կոդավորումը, արձանագրության տարբերակների վերահսկումը։
9. Թեստային պլեյբուսները 'part.ru, GC-stop, kill առաջնորդը, slow skew, clock skew։
10. Դիտարկումն այն է, որ առաջնորդի/բայերի/ամսագրի և ալերտայի չափումները վճռական են։
17) Մինի-տեղեկատու, երբ ինչ-որ բան վերցնեք
etcd/Raft կլաստեր ներարկումների/բլոկների/համակարգման համար DC-ի ներսում։
ZooKeeper/ZAB ծառայությունների համար, որոնք արդեն կապված են ZK-ի վրա (հին ապակիներ, գծեր, առաջնորդություն)։
Multi-Paxos-ը պատրաստի ծառայության/գրադարանի միջոցով նեղ սպեցիզացված համակարգերում։
EPaxos-ը երկրաչափության և թիմերի ցածր կոնֆլիկտների ժամանակ։
Tendermint/HotStuff-ի համար permissioned ցանցերի/PoS-լեյերի համար տասնյակ հարյուրավոր վալիդատորների և վերջնական։
Systo-նման/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 phases19) FAQ
Q 'Ինչու՞ չօգտագործել երկու հանգույց և թայ-բրեյքերը։
A: Երկու հանգույց առանց երրորդ ռոտորի չի տալիս քվորումը բաժանման ժամանակ։ Անհրաժեշտ է 353 (CFT) կամ 3f + 1 (BFT)։
Q: Ինչպե՞ ս է Raft "ավելի հեշտ" Paxos "։
A 'Հստակ դեկոմոզիա, հասկանալի լոգոյի և կազմաձևի ինվարանտներ։ ավելի հեշտ է իրականացնել և ուղեկցել։
Q 'Ինչպե՞ ս արագ կարդալ առանց առաջնորդի ծանրաբեռնվածության։
A: Follower-reads (հետևողական) ոչ ռիթմիկ, կամ least-reads/read-index գծային համար; քողարկեք։
Q 'Ի՞ նչն է սպանում p99։
A: WAN-RTT, սկավառակի fsync, GC ոտքերը, ծանրաբեռնված առաջնորդը, մեծ սարքավորումները «մեկ ժամ» -ում։
Q 'Արդյո՞ ք դուք պետք է համաձայնվեք քեշի/փողի համար։
Ա 'Եթե բավականին eventium consistency - ոչ։ Եթե անհրաժեշտ են գործարքային ինվարանտներ, այո։
20) Արդյունքները
Համաձայնությունը խիստ ինտեգրման և պատվիրման գործիք է։ Ընտրեք ալգորիթմը 'հիմնվելով ձախողումների և աշխարհագրության մոդելի վրա։ ապահովեք կվորումի հատումները, ճիշտ ռեկտորը, գծային ընթերցումները, որտեղ դա քննադատական է, և դիտարկումը։ Մի մոռացեք արտաքին էֆեկտների, սարքավորումների և ամսագրերի կարգապահության մասին։ Այդ ժամանակ վիճակի կրկնապատկումը կանխատեսելի կլինի, իսկ միջադեպերը հազվադեպ և հասկանալի են։