Hè accadutu uni pochi di ghjorni fà . I picciotti di JUG.ru Group anu invitatu i parraturi di sognu (Leslie Lamport! Cliff Cliff! Martin Kleppmann!) È dedicatu dui ghjorni à i sistemi distribuiti è l'informatica. Kontur era unu di i trè partenarii di cunferenza. Avemu parlatu à u stand, parlatu di u nostru almacenamentu distribuitu, ghjucatu à bingo è risolve i prublemi.
Questu hè un postu cù una analisi di i travaglii in u stand Kontur da l'autore di u so testu. Per quelli chì sò stati in Hydra, questa hè a vostra chance di ricurdà esperienze piacevuli; per quelli chì ùn anu micca, questa hè una chance per allungà u vostru cervellu. grande O-nutazione.
Ci era ancu i participanti chì anu disassemblatu u flipchart in slides per scrive a so suluzione. Ùn sò micca scherzu - anu mandatu sta pila di carta per l'ispezione:
Ci era trè compiti in totale:
- nantu à a selezzione di repliche per pesi per l'equilibriu di carica
- circa l'ordine di i risultati di una dumanda à una basa di dati in memoria
- nantu à u trasferimentu di u statu in un sistema distribuitu cù una topologia anellu
Task 1. ClusterClient
Era necessariu di prupone un algoritmu per selezziunà in modu efficiente K da N repliche ponderate di un sistema distribuitu:
A vostra squadra hè incaricata di sviluppà una biblioteca di clientella per un cluster massivamente distribuitu di N nodi. A libreria mantene a traccia di diversi metadati assuciati cù i nodi (per esempiu, e so latenza, i tassi di risposta 4xx / 5xx, etc.) è assignà pesi in virgule flottante W1..WN à elli. Per sustene a strategia di esecuzione simultanea, a biblioteca deve esse capace di sceglie K di N nodi aleatoriu - a chance di esse sceltu deve esse proporzionale à u pesu di un node.
Proponi un algoritmu per selezziunà i nodi in modu efficiente. Stima a so cumplessità computazionale utilizendu a notazione O grande.
Perchè tuttu hè in inglese?
Perchè hè cusì chì i participanti di a cunferenza li battevanu è perchè l'inglese era a lingua ufficiale di Hydra. I prublemi parevanu cusì:
Pigliate carta è matita, pensate, ùn affrettate micca à apre spoilers subitu :)
Analisi di a suluzione (video)
Accumincia à 5:53, solu 4 minuti:
È eccu cumu quelli stessi picciotti cù u flipchart presentavanu a so suluzione:
Analisi di a suluzione (testu)
A suluzione seguente si trova nantu à a superficia: somma i pesi di tutte e rèpliche, generà un numeru aleatoriu da 0 à a summa di tutti i pesi, dopu selezziunate una i-replica cusì chì a somma di i pesi di e rèpliche da 0 à u ( i-1)th hè menu di u numeru aleatoriu, è a summa di i pesi di e rèpliche da 0 à i-th - più di questu. Questu modu pudete selezziunate una replica, è per selezziunà u prossimu, avete bisognu di ripetiri tutta a prucedura senza cunsiderà a replica scelta. Cù un tali algoritmu, a cumplessità di sceglie una replica hè O (N), a cumplessità di sceglie K replica hè O (N · K) ~ O (N2).
A cumplessità quadratica hè male, ma pò esse migliurata. Per questu avemu da custruisce per a somma di pesi. U risultatu hè un arbulu di prufundità lg N, e foglie chì cuntenenu i pesi di e rèpliche, è i nodi restanti cuntenenu sume parziali, finu à a summa di tutti i pesi à a radica di l'arbulu. In seguitu, generà un numeru aleatoriu da 0 à a summa di tutti i pesi, truvate a replica i-th, sguassate da l'arbulu è ripetite a prucedura per truvà e rèpliche restante. Cù un tale algoritmu, a cumplessità di custruisce un arbulu hè O (N), a cumplessità di truvà a replica i-th è caccià da l'arbulu hè O (lg N), a cumplessità di sceglie K répliques hè O (N +). K lg N) ~ O(N lg N) .
A cumplessità lineari-logaritmica hè più bella di a cumplessità quadratica, in particulare per i grandi K.
Hè stu algoritmu Biblioteche ClusterClient da u prughjettu "" (Ci l'arbulu hè custruitu in O (N lg N), ma questu ùn affetta micca a cumplessità finali di l'algoritmu.)
Prublemu 2. Zebra
Hè statu necessariu di prupone un algoritmu per l'ordinamentu efficiente di documenti in memoria per un campu arbitrariu non indexatu:
A vostra squadra hè incaricata di sviluppà una basa di dati di documenti in memoria sharded. Una carica di travagliu cumuna seria di selezziunà i primi N documenti ordinati da un campu numericu arbitrariu (non indexatu) da una cullizzioni di taglia M (di solitu N < 100 << M). Una carica di travagliu un pocu menu cumuna seria di selezziunà u top N dopu à saltà i principali documenti S (S ~ N).
Proponi un algoritmu per eseguisce tali dumande in modu efficiente. Stima a so cumplessità computazionale utilizendu a notazione O grande in u casu mediu è u peghju scenariu.
Analisi di a suluzione (video)
Accumincia à 34:50, solu 6 minuti:
Analisi di a suluzione (testu)
Soluzione nantu à a superficia: sorte tutti i documenti (per esempiu, usendu ), poi pigliate documenti N+S. In questu casu, a cumplessità di a classificazione in media hè O (M lg M), à u peghju hè O (M2).
Ovviamente, l'ordine di tutti i documenti M è poi piglià solu una piccula parte di elli hè inefficiente. Per ùn sorte tutti i documenti, un algoritmu farà , chì selezziunà N + S documenti richiesti (pò esse ordinati da qualsiasi algoritmu). In questu casu, a cumplessità serà ridutta à O (M) in media, è u peghju casu ferma u listessu.
Tuttavia, pudete fà ancu più efficacemente - utilizate l'algoritmu . In questu casu, i primi documenti N + S sò aghjuntu à un min- o max-heap (secondu a direzzione di sorte), è dopu ogni documentu sussegwente hè paragunatu cù a radica di l'arbulu, chì cuntene u documentu minimu o massimu attuale. , è, se ne necessariu, hè aghjuntu à l'arbulu. In questu casu, a cumplessità in u peghju casu, quandu avete a ricustruisce constantemente l'arbulu, hè O (M lg M), a cumplessità in media hè O (M), cum'è quandu si usa quickselect.
In ogni casu, u heap streaming hè più efficau per u fattu chì in pratica a maiò parte di i ducumenti ponu esse scartate senza ricustruisce u munzeddu, dopu una sola paraguni cù u so elementu radicali. Questa classificazione hè implementata in a basa di dati di documenti in memoria di Zebra, sviluppata è utilizata in Kontur.
Prublemu 3. Scambi di Statu
Hè statu necessariu di prupone l'algoritmu più efficaci per i stati cambianti:
A vostra squadra hè incaricata di sviluppà un mecanismu di scambiu di statu di fantasia per un cluster distribuitu di N nodi. U statu di u node i-esimu deve esse trasferitu à u nodu (i + 1)-esimu, u statu di u nodu N-esimu deve esse trasferitu à u primu nodu. L'unica operazione supportata hè u scambiu di statu quandu dui nodi scambianu i so stati atomicamente. Hè cunnisciutu chì un scambiu di statu pigghia M millisecondi. Ogni nodu hè capaci di participà à un unicu swap di statu in ogni mumentu.
Quantu tempu ci vole à trasfiriri i stati di tutti i nodi in un cluster?
Analisi di a suluzione (testu)
A suluzione nantu à a superficia: scambià i stati di u primu è u sicondu elementi, dopu u primu è u terzu, u primu è u quartu, è cusì. Dopu ogni scambiu, u statu di un elementu serà in a pusizione desiderata. Avete da fà permutazioni O (N) è passà O (N·M) tempu.
U tempu lineale hè longu, cusì pudete scambià i stati di elementi in parechje: u primu cù u sicondu, u terzu cù u quartu, è cusì. Dopu ogni scambiu di statu, ogni secondu elementu serà in a pusizione desiderata. Avete da fà permutazioni O (lg N) è passà O (M lg N) tempu.
Tuttavia, pudete fà u cambiamentu ancu più efficiente - micca in lineari, ma in tempu constante. Per fà questu, in u primu passu avete bisognu di scambià u statu di u primu elementu cù l'ultimu, u sicondu cù u penultimu, è cusì. U statu di l'ultimu elementu serà in a pusizione desiderata. È avà avemu bisognu di scambià u statu di u sicondu elementu cù l'ultimu, u terzu cù u penultimu, è cusì. Dopu à sta volta di scambii, i stati di tutti l'elementi seranu in a pusizione desiderata. In totale, permutazioni O(2M) ~ O (1) seranu fatte.
Una tale suluzione ùn sorprenderà micca un matematicu, chì si ricorda sempre chì a rotazione hè una cumpusizioni di dui simmetrii assiali. A strada, hè trivially generalizata per cambià micca da unu, ma da K <N pusizioni. (Scrivi in i cumenti esattamente cumu.)
Ti piacenu i puzziche ? Sapete altre suluzioni ? Condividi in i cumenti.
Eccu alcuni ligami utili finali:
- scopre più nantu in Kontur
- fighjate à i registri interni nantu à i sistemi distribuiti
- fighjate a serie di video lectures "»
- abbonate à u nostru
Source: www.habr.com