Nitranga andro vitsivitsy lasa izay . Nanasa ireo mpandahateny nofinofy (Leslie Lamport! Cliff Click! Martin Kleppmann!) ry zalahy avy ao amin'ny Vondrona JUG.ru ary nanokana roa andro ho an'ny rafitra fizarana sy ny informatika. Iray amin'ireo mpiara-miombon'antoka telo tamin'ny fihaonambe i Kontur. Niresaka tao amin'ny trano heva izahay, niresaka momba ny fitahirizana nozarainay, nilalao bingo, ary namaha piozila.
Ity dia lahatsoratra misy famakafakana ny asa ao amin'ny toeran'ny Kontur avy amin'ny mpanoratra ny lahatsorany. Iza no tao amin'ny Hydra - izany no antony hahatsiarovanao ny traikefa nahafinaritra, iza no tsy - fahafahana haninjitra ny atidohanao lehibe O-notation.
Nisy mihitsy aza ireo mpandray anjara nandrava ny flipchart ho sary mihetsika mba hanoratana ny fanapahan-keviny. Tsy mivazivazy aho - natolotr'izy ireo ho fanamarinana ity antontam-taratasy ity:
Nisy asa telo tamin'ny fitambarany:
- momba ny fisafidianana kopia amin'ny lanja ho an'ny fifandanjana entana
- momba ny fanasokajiana valim-panontaniana amin'ny angon-drakitra ao anaty fitadidiana
- amin'ny famindrana fanjakana amin'ny rafitra mizara miaraka amin'ny topologie peratra
Asa 1. ClusterClient
Ilaina ny manolotra algorithm ho an'ny fifantenana mahomby amin'ny K avy amin'ny N replica lanja amin'ny rafitra mizara:
Ny ekipanao dia manana andraikitra amin'ny famolavolana tranomboky mpanjifa ho an'ny vondrona N node miparitaka be. Ny tranomboky dia hanara-maso ireo metadata isan-karazany mifandray amin'ny nodes (ohatra, ny fahataranany, 4xx/5xx ny tahan'ny valiny, sns.) ary hanome azy ireo lanja mitsingevana W1..WN. Mba hanohanana ny paikadin'ny famonoana miaraka, ny tranomboky dia tokony ho afaka misafidy K amin'ny N nodes kisendrasendra β ny vintana ho voafantina dia tokony hifanaraka amin'ny lanjan'ny node.
Soso-kevitra algorithm hisafidianana nodes mahomby. Tombantombana ny fahasarotan'ny kajy amin'ny alalan'ny fanondro O lehibe.
Nahoana no amin'ny teny anglisy ny zava-drehetra?
Satria tamin'ity endrika ity dia niady tamin'izy ireo ireo mpandray anjara tamin'ny fihaonambe ary satria ny teny anglisy no fiteny ofisialin'i Hydra. Toy izao ny asa:
MakΓ taratasy sy pensilihazo, mieritrereta, aza maika hanokatra spoiler avy hatrany π
Famakafakana ny vahaolana (video)
Manomboka amin'ny 5:53, 4 minitra monja:
Ary izao no fomba nametrahan'ireo lehilahy manana flipchart ny vahaolana:
Famakafakana ny vahaolana (soratra)
Ity vahaolana manaraka ity dia mipetraka eny ambonin'ny tany: ampifanaraho ny lanjan'ny replika rehetra, mamorona isa kisendrasendra manomboka amin'ny 0 ka hatramin'ny fitambaran'ny lanja rehetra, avy eo mifidiana i-replica mba hahatonga ny fitambaran'ny lanjan'ny replica manomboka amin'ny 0 ka hatramin'ny (i-1) th dia latsaky ny isa kisendrasendra, ary ny fitambaran'ny lanjan'ny dika mitovy amin'ny 0 ka hatramin'ny i-th - mihoatra noho izany. Noho izany dia ho azo atao ny mifidy kopia iray, ary ny mifidy ny manaraka dia mila mamerina ny dingana manontolo ianao nefa tsy mandinika ny kopia voafantina. Miaraka amin'ny algorithm toy izany, ny fahasarotana amin'ny fisafidianana kopia iray dia O(N), ny fahasarotan'ny fisafidianana K replika dia O(N K) ~ O(N2).
Ratsy ny fahasarotan'ny quadratic, saingy azo hatsaraina izany. Mba hanaovana izany, dia hanorina ho an'ny fitambaran'ny lanja. Hazo lalina lg N dia ho azo, ao amin'ny raviny dia hisy replica lanja, ary ao amin'ny nodes sisa - ampahany ampahany, hatramin'ny fitambaran'ny lanja rehetra eo amin'ny fototry ny hazo. Manaraka, mamorona isa kisendrasendra manomboka amin'ny 0 ka hatramin'ny fitambaran'ny lanja rehetra, tadiavo ny kopia i-th, esory amin'ny hazo, ary avereno ny fomba hahitana ireo kopia sisa. Miaraka amin'ity algorithm ity, ny fahasarotan'ny fananganana hazo dia O(N), ny fahasarotan'ny fitadiavana ny kopia i-th ary ny fanesorana azy amin'ny hazo dia O (lg N), ny fahasarotan'ny fisafidianana K replica dia O (N + K lg N) ~ O(N lg N) .
Ny fahasarotan'ny linear-log dia tsara kokoa noho ny fahasarotan'ny quadratic, indrindra ho an'ny K lehibe.
Io algorithm io Tranomboky ClusterClient avy amin'ny tetikasa "". (Ao, ny hazo dia naorina amin'ny O(N lg N), saingy tsy misy fiantraikany amin'ny fahasarotana farany amin'ny algorithm izany.)
Asa 2. Zebra
Ilaina ny nanolotra algorithm ho an'ny fanasokajiana ireo antontan-taratasy amin'ny fitadidiana amin'ny alΓ lan'ny saha tsy misy indexed:
Ny ekipanao dia manana andraikitra amin'ny famolavolana angon-drakitra antontan-taratasy ao anaty fitadidiana sharded. Ny enta-mavesatra mahazatra dia ny fisafidianana ireo antontan-taratasy N ambony nalahatra amin'ny sehatra isa tsy misy dikany (tsy misy fanondroana) avy amin'ny fanangonana habe M (matetika N <100 << M). Ny enta-mavesatry ny asa tsy dia mahazatra loatra dia ny fisafidianana ny N ambony aorian'ny fandalovana ny antontan-taratasy S ambony (S ~ N).
Soso-kevitra ny algorithm mba hanatanterahana ireo fanontaniana ireo amin'ny fomba mahomby. Tombantombana ny fahasarotan'ny kajy amin'ny alalan'ny fanamarihana O lehibe amin'ny tranga antonony sy ny tranga ratsy indrindra.
Famakafakana ny vahaolana (video)
Manomboka amin'ny 34:50, 6 minitra monja:
Famakafakana ny vahaolana (soratra)
Vahaolana amin'ny Surface: alaharo ny antontan-taratasy rehetra (ohatra amin'ny ), dia alao ny antontan-taratasy N+S. Amin'ity tranga ity, ny fahasarotan'ny fanasokajiana dia amin'ny salan'isa O (M lg M), amin'ny ratsy indrindra O (M2).
Mazava ho azy fa tsy mahomby ny fanasokajiana ny antontan-taratasy M rehetra ary avy eo maka ampahany kely amin'izy ireo. Mba tsy handaminana ny antontan-taratasy rehetra dia mety ny algorithm , izay hifidy N + S amin'ireo antontan-taratasy ilaina (azo alaina amin'ny algorithm rehetra izy ireo). Amin'ity tranga ity, hihena ho O(M) ny fahasarotana amin'ny antsalany, fa ny tranga ratsy indrindra kosa dia tsy miova.
Na izany aza, afaka manao izany ianao amin'ny fomba mahomby kokoa - ampiasao ny algorithm . Amin'ity tranga ity, ny antontan-taratasy N+S voalohany dia ampiana amin'ny min- na max-heap (miankina amin'ny lalana fanasokajiana), ary avy eo ny antontan-taratasy manaraka dia ampitahaina amin'ny fakan'ny hazo, izay misy ny antontan-taratasy farany ambany na ambony indrindra, ary ampiana amin'ny hazo raha ilaina. Amin'ity tranga ity, ny fahasarotana amin'ny tranga ratsy indrindra, rehefa tsy maintsy manangana tsy tapaka ny hazo ianao, dia O (M lg M), ny fahasarotana amin'ny ankapobeny dia O (M), toy ny amin'ny quickselect.
Na izany aza, hita fa mahomby kokoa ny fampitana an-tsarimihetsika noho ny zava-misy fa amin'ny fampiharana ny ankamaroan'ny antontan-taratasy dia azo ariana nefa tsy manangana indray ny antontan-taratasy aorian'ny fampitahana tokana amin'ny singa fototra. Ny fanasokajiana toy izany dia ampiharina ao amin'ny angon-drakitra antontan-taratasy ao anaty fitadidiana Zebra novolavolaina sy nampiasaina tao amin'ny Kontur.
Asa 3. Fifanakalozana fanjakana
Ilaina ny manolotra ny algorithm mahomby indrindra amin'ny fanovana fanjakana:
Ny ekipanao dia manana andraikitra amin'ny famolavolana mekanika fifanakalozam-panjakana ho an'ny vondrona N node zaraina. Tokony hafindra any amin'ny node (i+1)-th ny fanjakan'ny i-th, tokony hafindra any amin'ny node voalohany ny fanjakan'ny N-th. Ny hany asa tohana dia ny fifandimbiasam-panjakana rehefa mifanakalo atomika ny node roa. Fantatra fa mila M milisegondra ny fifanakalozam-panjakana. Ny node tsirairay dia afaka mandray anjara amin'ny swap fanjakana tokana amin'ny fotoana rehetra.
Hafiriana no hamindrana ny toetry ny node rehetra ao anaty cluster?
Famakafakana ny vahaolana (soratra)
Vahaolana ambonin'ny tany: mifanakalo ny toetry ny singa voalohany sy faharoa, avy eo ny voalohany sy fahatelo, avy eo ny voalohany sy fahefatra, sy ny sisa. Aorian'ny fifanakalozana tsirairay dia ho eo amin'ny toerana irina ny toetry ny singa iray. Tsy maintsy manao permutation O(N) ianao ary mandany fotoana O(N M).
Lava ny fotoana Linear, ka azonao atao ny manakalo ny toetry ny singa tsiroaroa: ny voalohany amin'ny faharoa, ny fahatelo amin'ny fahefatra, sy ny sisa. Aorian'ny fifanakalozam-panjakana tsirairay, ny singa faharoa dia ho eo amin'ny toerana mety. Tsy maintsy manao permutation O(lg N) ianao ary mandany fotoana O(M lg N).
Na izany aza, azo atao ny manao ny fanovana ho mahomby kokoa - tsy amin'ny linear, fa amin'ny fotoana tsy tapaka. Mba hanaovana izany, amin'ny dingana voalohany dia mila manakalo ny toetry ny singa voalohany amin'ny farany, ny faharoa amin'ny penultimate, sy ny sisa. Ny toetry ny singa farany dia ho eo amin'ny toerana mety. Ary ankehitriny dia mila manakalo ny toetry ny singa faharoa amin'ny farany, ny fahatelo amin'ny penultimate, sy ny sisa. Aorian'ity fifanakalozam-barotra ity dia ho eo amin'ny toerana mety ny fanjakan'ny singa rehetra. Hisy O(2M) ~ O(1) permutation amin'ny fitambarany.
Ny vahaolana toy izany dia tsy hahagaga ny mpahay matematika izay mbola mahatsiaro fa ny fihodinana dia fitambaran'ny axial symmetrie roa. Amin'ny lafiny iray, dia azo atao amin'ny ankapobeny izany ho an'ny fiovana tsy amin'ny iray, fa amin'ny toeran'ny K <N. (Soraty ao amin'ny commentaire ny tena marina.)
Tia piozila ve ianao? Mahafantatra vahaolana hafa ve ianao? Zarao amin'ny fanehoan-kevitra.
Ary ireto misy rohy mahasoa amin'ny farany:
- mianatra bebe kokoa momba ny amin'ny contour
- jereo ny rakitsoratry ny anatiny momba ny rafitra zaraina
- jereo ny andiana lahateny videoΒ»
- misoratra anarana aminay
Source: www.habr.com