Disa ditë më parë ndodhi . Djemtë nga JUG.ru Group ftuan folës të ëndrrave (Leslie Lamport! Cliff Click! Martin Kleppmann!) dhe i kushtuan dy ditë sistemeve të shpërndara dhe llogaritjeve. Kontur ishte një nga tre partnerët e konferencës. Ne biseduam në stendë, treguam për ruajtësit tanë të shpërndarë, luajtëm bingo dhe zgjidhëm detyra.
Ky Ă«shtĂ« njĂ« postim me analizĂ«n e detyrave nĂ« stendĂ«n e Konturit nga autori i tekstit. Ata qĂ« ishin nĂ« Hydra â kjo Ă«shtĂ« arsye pĂ«r t'u rikujtuar pĂ«rvojat e kĂ«ndshme, ata qĂ« nuk ishin â njĂ« mundĂ«si pĂ«r tĂ« ushtruar mendjen. big O-notacionit.
Ishte edhe njĂ« pjesĂ«marrĂ«s qĂ« ndau flipchart nĂ« slida pĂ«r tĂ« shkruar zgjidhjen e tij. Nuk po shaka â ata dorĂ«zuan pĂ«r kontroll njĂ« paketĂ« tĂ« tillĂ« letre:
Ishin gjithsej tre detyra:
- për zgjedhjen e replikave sipas peshave për balancimin e ngarkesës
- për renditjen e rezultateve të pyetjes në një bazë të dhënash in-memory
- për trajtimin e gjendjes në një sistem të shpërndarë me topologji rrethi
Detyra 1. ClusterClient
Duhej të ofronim një algoritëm efikas për zgjedhjen e K nga N replikave të peshkuara të një sistemi të shpërndarë:
Ekipa juaj ka detyrĂ«n tĂ« zhvillojĂ« njĂ« bibliotekĂ« klienti pĂ«r njĂ« grup masiv distribucioni me N nyje. Biblioteka do tĂ« mbajĂ« gjurmĂ«t e metadatatĂ« tĂ« ndryshme tĂ« lidhura me nyjet (p.sh., latencat e tyre, shkallĂ«t e pĂ«rgjigjeve 4xx/5xx, etj.) dhe do t'u japĂ« peshĂ« flotante W1..WN atyre. PĂ«r tĂ« mbĂ«shtetur strategjinĂ« e ekzekutimit njĂ«kohĂ«sisht, biblioteka duhet tĂ« jetĂ« nĂ« gjendje tĂ« zgjedhĂ« K nga N nyje rastĂ«sishtânjĂ« shans pĂ«r t'u zgjedhur duhet tĂ« jetĂ« proporcional me peshĂ«n e njĂ« nyjeje.
Propozoni një algoritëm për të seleksionuar nyje në mënyrë efikase. Vlerësoni kompleksitetin e tij kompjuterik duke përdorur notacionin e madh O.
Pse është gjithçka në anglisht?
Sepse në këtë formë u luftuan nga pjesëmarrësit e konferencës dhe sepse anglishtja ishte gjuha zyrtare e Hydra-s. Problemet dukej kështu:
Merrni njĂ« letĂ«r dhe njĂ« laps, mendoni, mos u nxehni pĂ«r tĂ« hapur menjĂ«herĂ« spoilerĂ«t đ
Analiza e zgjidhjes (video)
Fillimi në 5:53, gjithsej 4 minuta:
Këtu si e pitchuan zgjidhjen e tyre ata të njëjtit tip me flipchart:
Analiza e zgjidhjes (tekst)
NjĂ« zgjidhje qĂ« shfaqet Ă«shtĂ«: tĂ« pĂ«rmbledhim peshat e tĂ« gjitha replika, tĂ« gjenerojmĂ« njĂ« numĂ«r tĂ« rastĂ«sishĂ«m nga 0 deri nĂ« shumĂ«n e tĂ« gjitha peshave, pastaj tĂ« zgjedhim njĂ« replikĂ« i, nĂ« mĂ«nyrĂ« qĂ« shumĂ«n e peshave tĂ« replikave nga 0 deri nĂ« (i-1)-en tĂ« jetĂ« mĂ« pak se numri i rastĂ«sishĂ«m, ndĂ«rsa shumĂ«n e peshave tĂ« replikave nga 0 deri nĂ« i-tĂ« tĂ« jetĂ« mĂ« shumĂ« se ai. KĂ«shtu do tĂ« kemi zgjedhur njĂ« replikĂ«, dhe pĂ«r tĂ« zgjedhur tĂ« ardhshmen, duhet tĂ« pĂ«rsĂ«risim tĂ«rĂ« procedurĂ«n, pa marrĂ« parasysh replikĂ«n e zgjedhur. Me njĂ« algoritĂ«m tĂ« tillĂ«, kompleksiteti i zgjedhjes sĂ« njĂ« replike Ă«shtĂ« O(N), kompleksiteti i zgjedhjes sĂ« K replikave Ă«shtĂ« O(N·K) ~ O(NÂČ).
Kompleksiteti katror Ă«shtĂ« i keq, megjithatĂ« ai mund tĂ« pĂ«rmirĂ«sohet. PĂ«r kĂ«tĂ«, do tĂ« ndĂ«rtojmĂ« pĂ«r shumat e peshave. Do tĂ« rezultojĂ« njĂ« pemĂ« me thellĂ«si lg N, nĂ« gjethet e sĂ« cilĂ«s do tĂ« jenĂ« peshat e replikave, ndĂ«rsa nĂ« nodet e tjera â shumat pjesore, deri nĂ« shumĂ«n e tĂ« gjitha peshave nĂ« rrĂ«njĂ«n e pemĂ«s. MĂ« pas, gjenerojmĂ« njĂ« numĂ«r tĂ« rastĂ«sishĂ«m nga 0 deri nĂ« shumĂ«n e tĂ« gjitha peshave, gjejmĂ« replikĂ«n e i-tĂ«, e heqim atĂ« nga pema dhe pĂ«rsĂ«risim procedurĂ«n pĂ«r tĂ« kĂ«rkuar replikat e mbetura. Me njĂ« algoritĂ«m tĂ« tillĂ«, kompleksiteti i ndĂ«rtimit tĂ« pemĂ«s Ă«shtĂ« O(N), kompleksiteti i kĂ«rkimit tĂ« replikĂ«s sĂ« i-tĂ« dhe heqjes sĂ« saj nga pema Ă«shtĂ« O(lg N), kompleksiteti i zgjedhjes sĂ« K replikave Ă«shtĂ« O(N + K lg N) ~ O(N lg N).
Kompleksi linear-logarithmik është më i këndshëm se ai katror, veçanërisht për K të mëdha.
Ky algoritëm të bibliotekës ClusterClient nga projekti "". (Atje nd Build tree në O(N lg N), por kjo nuk ndikon në kompleksitetin përfundimtar të algoritmit.)
Detyra 2. Zebra
Duhej propozuar një algoritëm efikas për renditjen e dokumenteve në memorie sipas një fushe të rastësishme të pa indeksuar:
Ekipi juaj është i ngarkuar me zhvillimin e një baze të dhënash dokumentesh të ndara në memorie. Një ngarkesë e zakonshme do të ishte të zgjidhni N dokumentet më të mira të renditura sipas një fushe numerike (jo-indeksuar) të rastësishme nga një koleksion me madhësi M (zakonisht N < 100 << M). Një ngarkesë pak më pak të zakonshme do të ishte të zgjidhni N dokumentet më të mira pas skipping S dokumenteve të parë (S ~ N).
Propozoni një algoritëm për të ekzekutuar këto kërkesa në mënyrë efikase. Vlerësoni kompleksitetin e tij kompjuterik duke përdorur notacionin e madh O në rastin mesatar dhe në skenarët më të keq.
Analiza e zgjidhjes (video)
Fillimi në 34:50, gjithsej 6 minuta:
Analiza e zgjidhjes (tekst)
Zgjidhja është sipërfaqësore: renditni të gjithë dokumentet (për shembull, duke përdorur ), pastaj merrni dokumentet N+S. Në këtë rast kompleksiteti i renditjes në mesatar është O(M lg M), në më të keqin është O(M2).
E qartĂ«, se renditja e tĂ« gjithĂ« M dokumenteve, pĂ«r tĂ« marrĂ« pastaj vetĂ«m njĂ« pjesĂ« tĂ« vogĂ«l prej tyre â Ă«shtĂ« joefikase. PĂ«r tĂ« mos renditur tĂ« gjithĂ« dokumentet, do tĂ« pranohej algoritmi , i cili do tĂ« zgjedhĂ« N+S dokumentet e nevojshme (ato mund tĂ« grumbullohen pĂ«rmes çdo algoritmi). NĂ« kĂ«tĂ« rast, kompleksiteti mesatar do tĂ« zvogĂ«lohet nĂ« O(M), ndĂ«rsa rasti mĂ« i keq do tĂ« mbetet i njĂ«jtĂ«.
MegjithatĂ«, Ă«shtĂ« e mundur ta bĂ«ni edhe mĂ« efikas â duke pĂ«rdorur algoritmin . NĂ« kĂ«tĂ« rast, dokumentet e para N+S vendosen nĂ« min- ose max-heap (nĂ« varĂ«si tĂ« drejtimit tĂ« renditjes), dhe mĂ« pas çdo dokument tjetĂ«r krahasohet me rrĂ«njĂ«n e pemĂ«s, ku ndodhet dokumenti minimal ose maksimal pĂ«r momentin, dhe, nĂ«se Ă«shtĂ« e nevojshme, shtohet nĂ« pemĂ«. NĂ« kĂ«tĂ« rast, kompleksiteti nĂ« rastin mĂ« tĂ« keq, kur duhet tĂ« rindĂ«rtohet vazhdimisht pemĂ« â O(M lg M), kompleksiteti mesatar â O(M), ashtu siç ndodh me quickselect.
Megjithatë, heap streaming rezulton më efektiv për shkak se në praktikë shumicën e dokumenteve arrijmë t'i heqim dorë pa e rindërtuar grumbullin, pas një krahasimi të vetëm me elementin e saj rrënjësor. Kjo renditje është implementuar në bazën e të dhënave dokumentare in-memory Zebra, e cila është zhvilluar dhe përdorur në Kontur.
Detyra 3. KĂ«mbimet e gjendjeve
Duhej të propozohej algoritmi më efikas për zhvendosjen e gjendjeve:
Ekipa juaj Ă«shtĂ« ngarkuar me zhvillimin e njĂ« mekanizmi tĂ« avancuar tĂ« shkĂ«mbimit tĂ« gjendjes pĂ«r njĂ« grup tĂ« shpĂ«rndarĂ« prej N nodesh. Gjendja e nodit tĂ« i-tĂ« duhet tĂ« transferohet te nodi (i+1)-tĂ«, gjendja e nodit N duhet tĂ« transferohet te nodi i parĂ«. Operacioni i vetĂ«m i mbĂ«shtetur Ă«shtĂ« shkĂ«mbimi i gjendjes kur dy node shkĂ«mbejnĂ« gjendjet e tyre nĂ« mĂ«nyrĂ« atomike. Dihet se njĂ« shkĂ«mbim gjendje zgjat M milisekonda. Ădo nod Ă«shtĂ« nĂ« gjendje tĂ« marrĂ« pjesĂ« nĂ« njĂ« shkĂ«mbim gjendjeje nĂ« çdo moment tĂ« caktuar.
Sa kohë duhet për të transferuar gjendjet e të gjitha nodeve në një grup?
Analiza e zgjidhjes (tekst)
Zgjidhja në sipërfaqe: shkëmbimi i gjendjeve të elementit të parë dhe të dytë, pastaj të parit dhe të tretë, pastaj të parit dhe të katërt, dhe kështu me radhë. Pas çdo shkëmbimi, gjendja e një elementi do të jetë në pozitat e duhura. Do të duhen O(N) radhitje dhe do të shpenzohen O(N·M) kohë.
Koha lineare është shumë e gjatë, prandaj mund të shkëmbejmë gjendjet e elementeve çift: të parin me të dytin, të tretin me të katërtin dhe kështu me radhë. Pas çdo shkëmbimi, gjendja e çdo elementi të dytë do të jetë në pozitat e duhura. Do të duhen O(lg N) radhitje dhe do të shpenzohen O(M lg N) kohë.
Megjithatë, mund të bëni një zhvendosje edhe më efikase - jo në kohë lineare, por në kohë konstante. Për këtë, në hapin e parë, duhet të këmbeni gjendjen e elementit të parë me atë të fundit, të dytin me të parafundin dhe kështu me radhë. Gjendja e elementit të fundit do të përfundojë në pozitat e duhura. Tani duhet të këmbeni gjendjen e elementit të dytë me atë të fundit, të tretë me atë të parafundit dhe kështu me radhë. Pas këtij raundi të këmbimeve, gjendjet e të gjithë elementeve do të jenë në pozitat e duhura. Në total, do të bëhen O(2M) ~ O(1) shkëmbime.
Kjo zgjidhje nuk do ta befasojë fare matematikun që ende e mban mend se rrotullimi është një kompozim i dy simetrive aksiale. Për më tepër, ajo përshtatet në mënyrë triviale për zhvendosjen jo për një, por për K < N pozita. (Shkruani në komentet se si ndodhi.)
Ju pëlqyen këto detyra? Dini zgjidhje të tjera? Ndani në komente.
Ja disa lidhje të dobishme përfundimisht:
- mësoni më shumë rreth në Kontur
- shihni regjistrimet e brendshme për sistemet e shpërndara
- shihni ciklin e videove "»
- subskriboni në
Burimi: habr.com
