Tapahtui muutama päivä sitten Hydra-konferenssi. JUG.ru Groupin kaverit kutsuivat unelmakaiuttimet (Leslie Lamport! Cliff Click! Martin Kleppmann!) ja omistivat kaksi päivää hajautetuille järjestelmille ja tietojenkäsittelylle. Kontur oli yksi konferenssin kolmesta yhteistyökumppanista. Juttelimme osastolla, puhuimme jaetuista varastoistamme, pelasimme bingoa ja ratkoimme arvoituksia.

Tämä on tekstin kirjoittajan postaus, jossa analysoidaan Kontur-osaston tehtäviä. Kuka oli Hydrassa - tämä on syysi muistaa miellyttävä kokemus, kuka ei ollut - mahdollisuus venyttää aivojasi iso O-merkintä.

Jotkut osallistujat jopa purkivat fläppitaulun dioiksi kirjoittaakseen päätöksensä muistiin. En vitsaile - he luovuttivat tämän paperipinon varmennettavaksi:

Tehtäviä oli yhteensä kolme:

• kopioiden valitsemisesta painojen mukaan kuormituksen tasapainotusta varten
• kyselytulosten lajittelusta muistissa olevan tietokannan mukaan
• tilansiirrossa hajautetussa järjestelmässä, jossa on rengastopologia

Tehtävä 1. ClusterClient

Oli tarpeen ehdottaa algoritmi K:n tehokkaaseen valintaan hajautetun järjestelmän N painotetusta kopiosta:

Ryhmäsi tehtävänä on kehittää asiakaskirjasto massiivisesti hajautetulle N solmun klusterille. Kirjasto pitää kirjaa erilaisista solmuihin liittyvistä metatiedoista (esim. niiden latenssit, 4xx/5xx vastenopeudet jne.) ja määrittäisi niille liukulukupainot W1...WN. Samanaikaisen suoritusstrategian tukemiseksi kirjaston tulisi pystyä valitsemaan K N:stä solmusta satunnaisesti – valinnan mahdollisuuden tulee olla verrannollinen solmun painoon.

Ehdota algoritmia solmujen valitsemiseksi tehokkaasti. Arvioi sen laskennallinen monimutkaisuus käyttämällä suurta O-merkintää.

Miksi kaikki on englanniksi?

Koska tässä muodossa konferenssin osallistujat taistelivat heidän kanssaan ja koska englanti oli Hydran virallinen kieli. Tehtävät näyttivät tältä:

Ota paperia ja kynä, mieti, älä kiirehdi heti avaamaan spoilereita 🙂

Ratkaisun analyysi (video)

Alkaen 5:53, vain 4 minuuttia:

Ja tässä on, miten fläppitaulun käyttäneet kaverit esittivät ratkaisunsa:

Ratkaisun analyysi (teksti)

Pinnalla on seuraava ratkaisu: summaa kaikkien replikoiden painot, generoi satunnaisluku 0:sta kaikkien painojen summaan ja valitse sitten i-replika siten, että replikoiden summa on 0:sta (i-1)th:een. on pienempi kuin satunnaisluku, ja replikoiden painojen summa 0: sta i:nneen - suurempi kuin se. Joten on mahdollista valita yksi replika, ja valitaksesi seuraavan, sinun on toistettava koko toimenpide ottamatta huomioon valittua kopiota. Tällaisella algoritmilla yhden replikan valinnan monimutkaisuus on O(N), K replikan valinnan monimutkaisuus on O(N K) ~ O(N2).

Kvadraattinen monimutkaisuus on huono, mutta sitä voidaan parantaa. Tätä varten rakennamme segmenttipuu painojen summalle. Saadaan puu, jonka syvyys on lg N, jonka lehdissä on kopiopainot ja muissa solmuissa - osittaiset summat, kaikkien puun juuren painojen summaan asti. Seuraavaksi luomme satunnaisluvun 0:sta kaikkien painojen summaan, etsimme i:nnen replikan, poistamme sen puusta ja toistamme toimenpiteen jäljellä olevien replikoiden löytämiseksi. Tällä algoritmilla puun rakentamisen monimutkaisuus on O(N), i:nnen replikan löytämisen ja puusta poistamisen monimutkaisuus on O(lg N), K replikan valinnan monimutkaisuus on O(N + K lgN)~O(N lgN) .

Lineaarinen logaritminen monimutkaisuus on mukavampaa kuin neliöllinen kompleksisuus, erityisesti suurille K:lle.

Se on tämä algoritmi toteutettu koodissa ClusterClient-kirjastot projektista "itään". (Siinä puu on rakennettu O(N lg N), mutta tämä ei vaikuta algoritmin lopulliseen monimutkaisuuteen.)

Tehtävä 2. Seepra

Oli tarpeen ehdottaa algoritmi muistissa olevien asiakirjojen tehokkaaseen lajitteluun mielivaltaisen indeksoimattoman kentän mukaan:

Ryhmäsi tehtävänä on kehittää sirpaloitu muistissa oleva dokumenttitietokanta. Yleinen työmäärä olisi valita N suosituinta asiakirjaa, jotka on lajiteltu mielivaltaisen (indeksoimattoman) numerokentän mukaan M-koon joukosta (yleensä N < 100 << M). Hieman harvinaisempi työkuormitus olisi valita top N sen jälkeen, kun ylin S-asiakirjat on ohitettu (S ~ N).

Ehdota algoritmia tällaisten kyselyjen suorittamiseksi tehokkaasti. Arvioi sen laskennallinen monimutkaisuus käyttämällä suurta O-merkintää keskimääräisessä tapauksessa ja pahimmassa tapauksessa.

Ratkaisun analyysi (video)

Alkaen 34:50, vain 6 minuuttia:

Ratkaisun analyysi (teksti)

Pintaratkaisu: lajittele kaikki asiakirjat (esim pikalajittelu), ota sitten N+S-asiakirjat. Tässä tapauksessa lajittelun monimutkaisuus on keskimäärin O(M lg M), pahimmillaan O(M2).

On selvää, että kaikkien M-asiakirjojen lajittelu ja sitten vain pienen osan ottaminen niistä on tehotonta. Jotta kaikkia asiakirjoja ei järjestettäisi, algoritmi on sopiva pikavalinta, joka valitsee N + S haluttuja asiakirjoja (ne voidaan lajitella millä tahansa algoritmilla). Tässä tapauksessa monimutkaisuus pienenee keskimäärin O(M):iin, kun taas pahin tapaus pysyy samana.

Voit kuitenkin tehdä sen vielä tehokkaammin - käytä algoritmia binäärikeon suoratoisto. Tässä tapauksessa ensimmäiset N+S-asiakirjat lisätään min- tai max-keoon (riippuen lajittelusuunnasta), ja sitten jokaista seuraavaa dokumenttia verrataan puun juureen, joka sisältää nykyisen minimi- tai maksimiasiakirjan, ja lisätään tarvittaessa puuhun. Tässä tapauksessa monimutkaisuus pahimmassa tapauksessa, kun joudut jatkuvasti rakentamaan puuta uudelleen, on O(M lg M), monimutkaisuus on keskimäärin O(M), kuten Quickselectissä.

Keon suoratoisto osoittautuu kuitenkin tehokkaammaksi, koska käytännössä suurin osa asiakirjoista voidaan hylätä ilman, että kasa rakennetaan uudelleen yhden vertailun jälkeen sen juurielementtiin. Tällainen lajittelu on toteutettu Konturissa kehitetyssä ja käytössä olevassa Zebra in-memory -asiakirjatietokannassa.

Tehtävä 3. Valtionvaihdot

Oli tarpeen ehdottaa tehokkain algoritmi tilojen vaihtamiseen:

Ryhmäsi tehtävänä on kehittää hieno tilanvaihtomekanismi hajautetulle N solmun klusterille. I:nnen solmun tila tulee siirtää (i+1)-solmuun, N:nnen solmun tila ensimmäiseen solmuun. Ainoa tuettu operaatio on tilanvaihto, kun kaksi solmua vaihtavat tilat atomisesti. Tiedetään, että tilanvaihto kestää M millisekuntia. Jokainen solmu voi osallistua yhteen tilanvaihtoon minä tahansa hetkenä.

Kuinka kauan klusterin kaikkien solmujen tilojen siirtäminen kestää?

Ratkaisun analyysi (teksti)

Pintaratkaisu: vaihda ensimmäisen ja toisen elementin tilat, sitten ensimmäisen ja kolmannen, sitten ensimmäisen ja neljännen ja niin edelleen. Jokaisen vaihdon jälkeen yhden elementin tila on halutussa paikassa. Sinun täytyy tehdä O(N) permutaatioita ja käyttää O(N M) aikaa.

Lineaarinen aika on pitkä, joten voit vaihtaa elementtien tilat pareittain: ensimmäinen toisen kanssa, kolmas neljännen kanssa ja niin edelleen. Jokaisen tilanvaihdon jälkeen joka toinen elementti on oikeassa paikassa. Sinun täytyy tehdä O(lg N) permutaatioita ja käyttää O(M lg N) aikaa.

On kuitenkin mahdollista tehdä siirrosta entistä tehokkaampi - ei lineaarisessa, vaan vakioajassa. Tätä varten sinun on ensimmäisessä vaiheessa vaihdettava ensimmäisen elementin tila viimeiseen, toisen toiseksi viimeiseen ja niin edelleen. Viimeisen elementin tila on oikeassa paikassa. Ja nyt meidän on vaihdettava toisen elementin tila viimeiseen, kolmannen toiseksi viimeiseen ja niin edelleen. Tämän vaihtokierroksen jälkeen kaikkien elementtien tilat ovat oikeassa asennossa. Permutaatioita on yhteensä O(2M) ~ O(1).

Tällainen ratkaisu ei yllätä yhtään matemaatikkoa, joka vielä muistaa, että rotaatio on kahden aksiaalisymmetrian koostumus. Muuten, se on triviaalisti yleistetty siirrolle ei yhdellä, vaan K < N paikalla. (Kirjoita kommentteihin kuinka tarkalleen.)

Piditkö arvoimista? Tiedätkö muita ratkaisuja? Jaa kommenteissa.

Ja tässä lopuksi hyödyllisiä linkkejä:

• oppia lisää infrastruktuurin kehittäminen ääriviivassa
• katso sisäiset tiedot lehtinen raporteilla hajautetuista järjestelmistä
• katso videoluentosarjaEpätavallisia algoritmeja tavallisille ihmisille»
• tilaa meidän kanava Telegramissa

Lähde: will.com