Det skete for et par dage siden . Drengene fra JUG.ru Group inviterede drømmetalere (Leslie Lamport! Cliff Click! Martin Kleppmann!) og brugte to dage til distribuerede systemer og computing. Kontur var en af konferencens tre partnere. Vi talte ved standen, talte om vores distribuerede opbevaring, spillede bingo og løste gåder.
Dette er et indlæg med en analyse af opgaver på Kontur-standen fra forfatteren til deres tekst. Hvem var på Hydra - dette er din grund til at huske den behagelige oplevelse, hvem var ikke - en chance for at strække din hjerne stor O-notation.
Der var endda deltagere, som afmonterede flipoveren i slides for at skrive deres beslutning ned. Jeg spøger ikke - de afleverede denne stak papir til verifikation:
Der var i alt tre opgaver:
- om udvælgelse af replikaer efter vægte til lastbalancering
- om sortering af forespørgselsresultater mod en database i hukommelsen
- om tilstandsoverførsel i et distribueret system med en ringtopologi
Opgave 1. ClusterClient
Det var nødvendigt at foreslå en algoritme til effektiv udvælgelse af K fra N vægtede replikaer af et distribueret system:
Dit team har til opgave at udvikle et klientbibliotek til en massivt distribueret klynge af N noder. Biblioteket vil holde styr på forskellige metadata, der er forbundet med noder (f.eks. deres latenser, 4xx/5xx svarfrekvenser osv.) og tildele flydende kommavægte W1..WN til dem. For at understøtte strategien for samtidig udførelse bør biblioteket være i stand til at vælge K af N noder tilfældigt - en chance for at blive valgt bør være proportional med en nodes vægt.
Foreslå en algoritme til at vælge noder effektivt. Estimer dens beregningsmæssige kompleksitet ved hjælp af big O-notation.
Hvorfor er alt på engelsk?
Fordi konferencedeltagerne i denne form kæmpede med dem, og fordi engelsk var Hydras officielle sprog. Opgaverne så således ud:
Tag papir og blyant, tænk, skynd dig ikke at åbne spoilere med det samme 🙂
Analyse af løsningen (video)
Starter kl. 5:53, kun 4 minutter:
Og her er, hvordan fyrene med flipoveren pitchede deres løsning:
Analyse af løsningen (tekst)
Følgende løsning ligger på overfladen: summer vægten af alle replikaer, generer et tilfældigt tal fra 0 til summen af alle vægte, vælg derefter en i-replika, således at summen af replikavægte fra 0 til (i-1)th er mindre end et tilfældigt tal, og summen af replika vejer fra 0 til i-te - mere end det. Så det vil være muligt at vælge en replika, og for at vælge den næste skal du gentage hele proceduren uden at overveje den valgte replika. Med en sådan algoritme er kompleksiteten ved at vælge en replika O(N), kompleksiteten ved at vælge K-replikaer er O(N K) ~ O(N2).
Kvadratisk kompleksitet er dårlig, men den kan forbedres. For at gøre dette vil vi bygge for summer af vægte. Et træ med dybden lg N vil blive opnået, i hvis blade der vil være replikavægte, og i de resterende noder - delsummer, op til summen af alle vægte ved roden af træet. Dernæst genererer vi et tilfældigt tal fra 0 til summen af alle vægte, finder den i-te replika, fjerner den fra træet og gentager proceduren for at finde de resterende replikaer. Med denne algoritme er kompleksiteten ved at bygge et træ O(N), kompleksiteten ved at finde den i-te replika og fjerne den fra træet er O(lg N), kompleksiteten ved at vælge K-replikaer er O(N + K Ig N) ~ O(N Ig N) .
Lineær log kompleksitet er pænere end kvadratisk kompleksitet, især for store K.
Det er denne algoritme ClusterClient-biblioteker fra projektet "". (Der er træet bygget i O(N lg N), men dette påvirker ikke den endelige kompleksitet af algoritmen.)
Opgave 2. Zebra
Det var nødvendigt at foreslå en algoritme til effektiv sortering af dokumenter i hukommelsen efter et vilkårligt ikke-indekseret felt:
Dit team har til opgave at udvikle en sharded in-memory dokumentdatabase. En almindelig arbejdsbyrde ville være at vælge top N dokumenter sorteret efter et vilkårligt (ikke-indekseret) numerisk felt fra en samling af størrelse M (normalt N < 100 << M). En lidt mindre almindelig arbejdsbyrde ville være at vælge top N efter at have sprunget top S dokumenter over (S ~ N).
Foreslå en algoritme til at udføre sådanne forespørgsler effektivt. Estimer dens beregningsmæssige kompleksitet ved hjælp af big O-notation i gennemsnitsscenarier og worst case-scenarier.
Analyse af løsningen (video)
Starter kl. 34:50, kun 6 minutter:
Analyse af løsningen (tekst)
Overfladeløsning: sorter alle dokumenter (f.eks. med ), og tag derefter N+S-dokumenter. I dette tilfælde er kompleksiteten af sorteringen i gennemsnit O(M lg M), i værste fald O(M2).
Det er indlysende, at det er ineffektivt at sortere alle M dokumenter og derefter kun tage en lille del af dem. For ikke at sortere alle dokumenter er en algoritme velegnet , som vil vælge N + S af de ønskede dokumenter (de kan sorteres efter enhver algoritme). I dette tilfælde vil kompleksiteten i gennemsnit falde til O(M), mens worst case forbliver den samme.
Du kan dog gøre det endnu mere effektivt - brug algoritmen . I dette tilfælde føjes de første N+S-dokumenter til min- eller max-heap (afhængigt af sorteringsretningen), og derefter sammenlignes hvert næste dokument med roden af træet, som indeholder det aktuelle minimum eller maksimum dokument, og føjes til træet om nødvendigt. . I dette tilfælde er kompleksiteten i værste fald, når man hele tiden skal genopbygge træet, O(M lg M), kompleksiteten er i gennemsnit O(M), som ved quickselect.
Heap-streaming viser sig dog at være mere effektiv på grund af det faktum, at de fleste dokumenter i praksis kan kasseres uden at genopbygge heapen efter en enkelt sammenligning med dets rodelement. En sådan sortering er implementeret i Zebra in-memory dokumentdatabasen udviklet og brugt i Kontur.
Opgave 3. Statsbytte
Det var nødvendigt at foreslå den mest effektive algoritme til skiftende tilstande:
Dit team har til opgave at udvikle en fancy tilstandsudvekslingsmekanisme for en distribueret klynge af N noder. Den i-te knudes tilstand skal overføres til den (i+1)-te knude, den N-te knudes tilstand skal overføres til den første knude. Den eneste understøttede operation er tilstandsswap, når to noder udveksler deres tilstande atomisk. Det er kendt, at en tilstandsswap tager M millisekunder. Hver node er i stand til at deltage i en enkelt tilstandsswap på ethvert givet tidspunkt.
Hvor lang tid tager det at overføre tilstandene for alle noder i en klynge?
Analyse af løsningen (tekst)
Overfladeløsning: udskift tilstanden for det første og andet element, så det første og tredje, så det første og det fjerde, og så videre. Efter hver udveksling vil tilstanden af et element være i den ønskede position. Du skal lave O(N) permutationer og bruge O(N M) tid.
Lineær tid er lang, så du kan udveksle elementernes tilstande parvis: den første med den anden, den tredje med den fjerde, og så videre. Efter hver statsudveksling vil hvert andet element være i den rigtige position. Du skal lave O(lg N) permutationer og bruge O(M lg N) tid.
Det er dog muligt at gøre skiftet endnu mere effektivt - ikke lineært, men i konstant tid. For at gøre dette skal du på det første trin udveksle tilstanden for det første element med det sidste, det andet med det næstsidste og så videre. Tilstanden af det sidste element vil være i den korrekte position. Og nu skal vi udveksle tilstanden for det andet element med det sidste, det tredje med det næstsidste og så videre. Efter denne udvekslingsrunde vil tilstanden for alle elementer være i den rigtige position. Der vil være O(2M) ~ O(1) permutationer i alt.
En sådan løsning vil slet ikke overraske en matematiker, der stadig husker, at en rotation er en sammensætning af to aksiale symmetrier. Forresten er det trivielt generaliseret for et skift ikke med én, men med K < N positioner. (Skriv i kommentarerne hvordan præcist.)
Kunne du lide puslespil? Kender du andre løsninger? Del i kommentarerne.
Og her er nogle nyttige links til sidst:
- Lær mere om i kontur
- se registreringer af interne om distribuerede systemer
- se serien af videoforedrag»
- abonnere på vores
Kilde: www.habr.com