Skjedde for noen dager siden Hydra-konferansen. Gutta fra JUG.ru Group inviterte drømmetalere (Leslie Lamport! Cliff Click! Martin Kleppmann!) og viet to dager til distribuerte systemer og databehandling. Kontur var en av konferansens tre partnere. Vi snakket på standen, snakket om våre distribuerte lager, spilte bingo og løste gåter.

Dette er et innlegg med en analyse av oppgaver på Kontur-standen fra forfatteren av deres tekst. Hvem var på Hydra - dette er din grunn til å huske den hyggelige opplevelsen, hvem var ikke - en sjanse til å strekke hjernen din stor O-notasjon.

Det var til og med deltakere som demonterte flipoveren til lysbilder for å skrive ned avgjørelsen. Jeg tuller ikke – de overleverte denne bunken med papir for verifisering:

Det var totalt tre oppgaver:

• om å velge kopier etter vekter for lastbalansering
• om sortering av søkeresultater mot en database i minnet
• på tilstandsoverføring i et distribuert system med ringtopologi

Oppgave 1. ClusterClient

Det var nødvendig å foreslå en algoritme for effektivt valg av K fra N vektede kopier av et distribuert system:

Teamet ditt har i oppgave å utvikle et klientbibliotek for en massivt distribuert klynge av N noder. Biblioteket vil holde styr på ulike metadata assosiert med noder (f.eks. deres latenser, 4xx/5xx responsrater, etc.) og tilordne flyttallvekter W1..WN til dem. For å støtte strategien for samtidig utførelse, bør biblioteket være i stand til å velge K av N noder tilfeldig - en sjanse for å bli valgt bør være proporsjonal med en nodes vekt.

Foreslå en algoritme for å velge noder effektivt. Estimer dens beregningsmessige kompleksitet ved å bruke stor O-notasjon.

Hvorfor er alt på engelsk?

Fordi konferansedeltakerne i denne formen kjempet med dem og fordi engelsk var det offisielle språket til Hydra. Oppgavene så slik ut:

Ta papir og blyant, tenk, ikke skynd deg å åpne spoilere med en gang 🙂

Analyse av løsningen (video)

Starter 5:53, bare 4 minutter:

Og her er hvordan gutta med flipover la ut løsningen sin:

Analyse av løsningen (tekst)

Følgende løsning ligger på overflaten: summer vektene til alle kopier, generer et tilfeldig tall fra 0 til summen av alle vekter, velg deretter en i-replika slik at summen av kopivekter fra 0 til (i-1) er mindre enn et tilfeldig tall, og summen av replika veier fra 0 til i-te - mer enn det. Så det vil være mulig å velge en kopi, og for å velge den neste, må du gjenta hele prosedyren uten å vurdere den valgte kopien. Med en slik algoritme er kompleksiteten ved å velge en kopi O(N), kompleksiteten ved å velge K-replika er O(N K) ~ O(N2).

Kvadratisk kompleksitet er dårlig, men den kan forbedres. For å gjøre dette skal vi bygge segmenttre for summer av vekter. Et tre med dybde lg N vil bli oppnådd, i bladene som det vil være replikavekter, og i de gjenværende nodene - delsummer, opp til summen av alle vekter ved roten av treet. Deretter genererer vi et tilfeldig tall fra 0 til summen av alle vekter, finner den i-te kopien, fjerner den fra treet og gjentar prosedyren for å finne de gjenværende kopiene. Med denne algoritmen er kompleksiteten ved å bygge et tre O(N), kompleksiteten ved å finne den i-te kopien og fjerne den fra treet er O(lg N), kompleksiteten ved å velge K-replikaer er O(N + K lg N) ~ O(N lg N) .

Lineær loggkompleksitet er bedre enn kvadratisk kompleksitet, spesielt for stor K.

Det er denne algoritmen implementert i kode ClusterClient-biblioteker fra prosjektet "øst". (Der er treet bygget i O(N lg N), men dette påvirker ikke den endelige kompleksiteten til algoritmen.)

Oppgave 2. Sebra

Det var nødvendig å foreslå en algoritme for effektiv sortering av dokumenter i minnet etter et vilkårlig ikke-indeksert felt:

Teamet ditt har i oppgave å utvikle en sønderdelt dokumentdatabase i minnet. En vanlig arbeidsbelastning vil være å velge topp N dokumenter sortert etter et vilkårlig (ikke-indeksert) numerisk felt fra en samling av størrelse M (vanligvis N < 100 << M). En litt mindre vanlig arbeidsbelastning vil være å velge topp N etter å ha hoppet over topp S-dokumenter (S ~ N).

Foreslå en algoritme for å utføre slike spørringer effektivt. Estimer dens beregningsmessige kompleksitet ved å bruke stor O-notasjon i gjennomsnittlig tilfelle og verste tilfelle.

Analyse av løsningen (video)

Starter kl 34:50, kun 6 minutter:

Analyse av løsningen (tekst)

Overflateløsning: sorter alle dokumenter (for eksempel med Quicksort), og ta deretter N+S-dokumenter. I dette tilfellet er kompleksiteten i sorteringen i gjennomsnitt O(M lg M), i verste fall O(M2).

Det er åpenbart at det er lite effektivt å sortere alle M-dokumenter og så ta bare en liten del av dem. For ikke å sortere alle dokumenter, er en algoritme egnet hurtigvalg, som vil velge N + S av de ønskede dokumentene (de kan sorteres etter hvilken som helst algoritme). I dette tilfellet vil kompleksiteten reduseres til O(M) i gjennomsnitt, mens det verste tilfellet forblir det samme.

Du kan imidlertid gjøre det enda mer effektivt - bruk algoritmen binær heap-streaming. I dette tilfellet legges de første N+S-dokumentene til min- eller maks-heap (avhengig av sorteringsretningen), og deretter sammenlignes hvert neste dokument med roten av treet, som inneholder gjeldende minimums- eller maksimumsdokument, og legges til treet om nødvendig. . I dette tilfellet er kompleksiteten i verste fall, når du hele tiden må bygge om treet, O(M lg M), kompleksiteten i gjennomsnitt er O(M), som med quickselect.

Heap-streaming viser seg imidlertid å være mer effektiv på grunn av det faktum at de fleste dokumentene i praksis kan forkastes uten å gjenoppbygge haugen etter en enkelt sammenligning med rotelementet. Slik sortering er implementert i Zebra in-memory dokumentdatabasen utviklet og brukt i Kontur.

Oppgave 3. Statsbytte

Det var nødvendig å foreslå den mest effektive algoritmen for skiftende tilstander:

Teamet ditt har i oppgave å utvikle en fancy statutvekslingsmekanisme for en distribuert klynge av N noder. Den i-te nodens tilstand skal overføres til (i+1)-noden, den N-te nodens tilstand skal overføres til den første noden. Den eneste støttede operasjonen er tilstandsbytte når to noder utveksler tilstander atomisk. Det er kjent at en tilstandsbytte tar M millisekunder. Hver node er i stand til å delta i en enkelt tilstandsbytte til enhver tid.

Hvor lang tid tar det å overføre tilstandene til alle noder i en klynge?

Analyse av løsningen (tekst)

Overflateløsning: bytt ut tilstandene til det første og andre elementet, deretter det første og tredje, deretter det første og fjerde, og så videre. Etter hver utveksling vil tilstanden til ett element være i ønsket posisjon. Du må gjøre O(N) permutasjoner og bruke O(N M) tid.

Lineær tid er lang, så du kan utveksle tilstandene til elementene i par: den første med den andre, den tredje med den fjerde, og så videre. Etter hver statutveksling vil hvert andre element være i riktig posisjon. Du må gjøre O(lg N) permutasjoner og bruke O(M lg N) tid.

Det er imidlertid mulig å gjøre skiftet enda mer effektivt – ikke lineært, men i konstant tid. For å gjøre dette, i det første trinnet, må du bytte tilstanden til det første elementet med det siste, det andre med det nest siste, og så videre. Tilstanden til det siste elementet vil være i riktig posisjon. Og nå må vi bytte tilstanden til det andre elementet med det siste, det tredje med det nest siste, og så videre. Etter denne utvekslingsrunden vil tilstandene til alle elementene være i riktig posisjon. Det vil være O(2M) ~ O(1) permutasjoner totalt.

En slik løsning vil slett ikke overraske en matematiker som fortsatt husker at en rotasjon er en sammensetning av to aksiale symmetrier. Forresten er det trivielt generalisert for et skifte ikke med én, men med K < N posisjoner. (Skriv i kommentarfeltet nøyaktig hvordan.)

Likte du gåter? Vet du andre løsninger? Del i kommentarene.

Og her er noen nyttige linker til slutt:

• lære mer om utvikling av infrastruktur i kontur
• se registreringer av interne flyer med rapporter om distribuerte systemer
• se serien med videoforelesningerUvanlige algoritmer for vanlige mennesker»
• abonner på vår kanal i Telegram

Kilde: www.habr.com