Barde in pear dagen lyn . De jonges fan 'e JUG.ru Group útnoege dreamsprekkers (Leslie Lamport! Cliff Click! Martin Kleppmann!) En wijden twa dagen oan ferdielde systemen en komputer. Kontur wie ien fan de trije partners fan de konferinsje. Wy prate by it hokje, praatten oer ús ferdielde opslach, spielden bingo en losten puzels op.
Dit is in post mei in analyze fan taken by de Kontur-stand fan 'e skriuwer fan har tekst. Wa wie op 'e Hydra - dit is jo reden om de noflike ûnderfining te ûnthâlden, wa wie net - in kâns om jo harsens te streken grutte O-notaasje.
Der wiene sels dielnimmers dy't de flipover yn dia's ûntmantele om harren beslút op te skriuwen. Ik meitsje gjin grap - se hawwe dizze stapel papier oerlevere foar ferifikaasje:
Yn totaal wiene der trije taken:
- oer selektearjen fan replika's troch gewichten foar load balancing
- oer it sortearjen fan queryresultaten tsjin in databank yn it ûnthâld
- op steat oerdracht yn in ferspraat systeem mei in ring topology
Taak 1. ClusterClient
It wie nedich om in algoritme foar te stellen foar de effisjinte seleksje fan K út N gewogen replika's fan in ferspraat systeem:
Jo team is opdroegen mei in ûntwikkeljen fan in klant bibleteek foar in massaal ferspraat kluster fan N knopen. De bibleteek soe folgje ferskate metadata ferbûn mei knopen (bgl. harren latencies, 4xx / 5xx antwurd tariven, ensfh) en tawize driuwende punt gewichten W1..WN oan harren. Om de simultane útfieringsstrategy te stypjen, moat de biblioteek K fan N knooppunten willekeurich kinne kieze - in kâns om selekteare te wurden moat evenredich wêze mei it gewicht fan in knooppunt.
Stel in algoritme foar om knopen effisjint te selektearjen. Skat de komputaasjekompleksiteit mei grutte O-notaasje.
Wêrom is alles yn it Ingelsk?
Om't yn dizze foarm de konferinsjedielnimmers mei har fochten en om't Ingelsk de offisjele taal fan Hydra wie. De taken seagen der sa út:
Nim papier en potlead, tink, net haasten te iepenjen spoilers direkt 🙂
Analyse fan 'e oplossing (fideo)
Begjin 5:53, mar 4 minuten:
En hjir is hoe't de jonges mei de flipover har oplossing pleatsten:
Analyse fan de oplossing (tekst)
De folgjende oplossing leit op it oerflak: som de gewichten fan alle replika's op, generearje in willekeurich getal fan 0 oant de som fan alle gewichten, kies dan in i-replika sadat de som fan replikagewichten fan 0 oant (i-1)th is minder as in willekeurich getal, en de som fan replika gewichten fan 0 oant i-th - mear as it. Sa sil it mooglik wêze om ien replika te selektearjen, en om de folgjende te selektearjen, moatte jo de heule proseduere werhelje sûnder de selekteare replika te beskôgjen. Mei sa'n algoritme is de kompleksiteit fan it kiezen fan ien replika O(N), de kompleksiteit fan it kiezen fan K-replika's is O(N K) ~ O(N2).
Kwadratyske kompleksiteit is min, mar it kin wurde ferbettere. Om dit te dwaan, sille wy bouwe foar sommen fan gewichten. In beam fan djipte lg N sil wurde krigen, yn 'e blêden wêrfan d'r replikagewichten sille wêze, en yn' e oerbleaune knopen - dielsommen, oant de som fan alle gewichten oan 'e woartel fan' e beam. Dêrnei generearje wy in willekeurich getal fan 0 oant de som fan alle gewichten, fine de i-e replika, fuortsmite fan 'e beam, en werhelje de proseduere om de oerbleaune replika's te finen. Mei dit algoritme is de kompleksiteit fan it bouwen fan in beam O(N), de kompleksiteit fan it finen fan de i-de replika en it fuortheljen fan 'e beam is O(lg N), de kompleksiteit fan it kiezen fan K-replika's is O(N + K lg N) ~ O(N lg N) .
Lineêre log kompleksiteit is moaier dan kwadratyske kompleksiteit, benammen foar grutte K.
It is dit algoritme ClusterClient-biblioteken fan it projekt "". (Dêr is de beam boud yn O(N lg N), mar dit hat gjin ynfloed op de definitive kompleksiteit fan it algoritme.)
Opdracht 2. Zebra
It wie nedich om in algoritme foar te stellen foar effisjint sortearjen fan dokuminten yn it ûnthâld troch in willekeurige net-yndeksearre fjild:
Jo team is opdroegen mei it ûntwikkeljen fan in ferdielde dokumintdatabase yn it ûnthâld. In mienskiplike wurkdruk soe wêze om top N dokuminten te selektearjen sortearre troch in willekeurige (net-yndeksearre) numerike fjild út in samling fan grutte M (meastentiids N <100 << M). In wat minder gewoane wurkdruk soe wêze om top N te selektearjen nei it oerslaan fan top S-dokuminten (S ~ N).
Stel in algoritme foar om sokke fragen effisjint út te fieren. Skatte de berekkeningskompleksiteit fan 'e grutte O-notaasje yn' e gemiddelde gefal en de minste gefal senario's.
Analyse fan 'e oplossing (fideo)
Begjin 34:50, mar 6 minuten:
Analyse fan de oplossing (tekst)
Oppervlakteoplossing: sortearje alle dokuminten (bygelyks mei ), nim dan N+S-dokuminten. Yn dit gefal is de kompleksiteit fan sortearjen gemiddeld O(M lg M), yn it slimste gefal O(M2).
It is fanselssprekkend dat it sortearjen fan alle M-dokuminten en dan mar in lyts part derfan nimme net effisjint is. Om net alle dokuminten te sortearjen, is in algoritme geskikt , dy't N + S sil selektearje fan 'e winske dokuminten (se kinne wurde sorteare troch elk algoritme). Yn dit gefal sil de kompleksiteit gemiddeld ôfnimme nei O(M), wylst it slimste gefal itselde bliuwt.
Jo kinne it lykwols noch effisjinter dwaan - brûk it algoritme . Yn dit gefal wurde de earste N+S-dokuminten tafoege oan min- of max-heap (ôfhinklik fan 'e sortearring), en dan wurdt elk folgjende dokumint fergelike mei de woartel fan' e beam, dy't it hjoeddeiske minimum of maksimum dokumint befettet, en wurdt tafoege oan 'e beam as it nedich is. . Yn dit gefal is de kompleksiteit yn it slimste gefal, as jo de beam hieltyd wer opbouwe moatte, O(M lg M), de kompleksiteit is gemiddeld O(M), lykas by quickselect.
Heapstreaming blykt lykwols effisjinter te wêzen fanwegen it feit dat yn 'e praktyk de measte dokuminten kinne wurde ferwidere sûnder de heap opnij op te bouwen nei ien fergeliking mei syn root-elemint. Sokke sortearring wurdt ymplementearre yn 'e Zebra in-memory dokumint databank ûntwikkele en brûkt yn Kontur.
Taak 3. State swaps
It wie nedich om it meast effisjinte algoritme foar te stellen foar it ferskowen fan steaten:
Jo team is opdroegen mei in ûntwikkeljen fan in fancy steat útwikseling meganisme foar in ferspraat kluster fan N knopen. De steat fan it i-de knooppunt moat wurde oerbrocht nei it (i+1)-ste knooppunt, de steat fan it N-de knooppunt moat wurde oerbrocht nei it earste knooppunt. De ienige stipe operaasje is de steatswikseling as twa knopen har steaten atomysk útwikselje. It is bekend dat in steat swap nimt M millisekonden. Elke knooppunt kin op elk momint meidwaan oan ien steatsruil.
Hoe lang duorret it om de steaten fan alle knopen yn in kluster oer te dragen?
Analyse fan de oplossing (tekst)
Surface oplossing: wikselje de steaten fan it earste en twadde elemint, dan de earste en tredde, dan de earste en fjirde, ensafuorthinne. Nei elke útwikseling sil de steat fan ien elemint yn 'e winske posysje wêze. Jo moatte O (N) permutaasjes meitsje en O (N M) tiid besteegje.
Lineêre tiid is lang, sadat jo de steaten fan eleminten yn pearen wikselje kinne: de earste mei de twadde, de tredde mei de fjirde, ensfh. Nei elke steatútwikseling sil elk twadde elemint yn 'e goede posysje wêze. Jo moatte O(lg N) permutaasjes meitsje en O(M lg N) tiid besteegje.
It is lykwols mooglik om de ferskowing noch effisjinter te meitsjen - net yn lineêr, mar yn konstante tiid. Om dit te dwaan, yn 'e earste stap, moatte jo de steat fan it earste elemint útwikselje mei de lêste, de twadde mei de foarlêste, ensafuorthinne. De steat fan it lêste elemint sil yn 'e juste posysje wêze. En no moatte wy de steat fan it twadde elemint útwikselje mei de lêste, de tredde mei de foarlêste, ensfh. Nei dizze rûnte fan útwikselingen sille de steaten fan alle eleminten yn 'e goede posysje wêze. D'r sille yn totaal O(2M) ~ O(1) permutaasjes wêze.
Sa'n oplossing sil net fernuverje in wiskundige dy't noch tinkt dat in rotaasje is in gearstalling fan twa axial symmetry. Troch de wei, it is trivial generalisearre foar in ferskowing net troch ien, mar troch K <N posysjes. (Skriuw yn 'e opmerkings hoe krekt.)
Hâldsto fan puzels? Witte jo oare oplossingen? Diel yn 'e kommentaren.
En hjir binne op it lêst wat nuttige keppelings:
- lear mear oer yn kontoeren
- sjoch records fan ynterne oer ferspraat systemen
- besjoch de searje fideolêzingen»
- ynskriuwe op ús
Boarne: www.habr.com