S-a întâmplat acum câteva zile . Băieții de la JUG.ru Group au invitat vorbitori de vis (Leslie Lamport! Cliff Click! Martin Kleppmann!) și au dedicat două zile sistemelor distribuite și calculului. Kontur a fost unul dintre cei trei parteneri ai conferinței. Am vorbit la stand, am vorbit despre stocarea noastră distribuită, am jucat bingo și am rezolvat puzzle-uri.
Aceasta este o postare cu o analiză a sarcinilor de la standul Kontur de la autorul textului lor. Cine a fost pe Hydra - acesta este motivul tău pentru a-ți aminti experiența plăcută, cine nu a fost - o șansă de a-ți întinde creierul O mare-notaţie.
Au existat chiar și participanți care au demontat flipchart-ul în diapozitive pentru a-și nota decizia. Nu glumesc - au predat acest teanc de hârtie pentru verificare:
Au fost trei sarcini în total:
- despre selectarea replicilor după ponderi pentru echilibrarea sarcinii
- despre sortarea rezultatelor interogărilor în raport cu o bază de date în memorie
- privind transferul de stare într-un sistem distribuit cu topologie inel
Sarcina 1. ClusterClient
A fost necesar să se propună un algoritm pentru selecția eficientă a K din N replici ponderate ale unui sistem distribuit:
Echipa ta are sarcina de a dezvolta o bibliotecă client pentru un cluster distribuit masiv de N noduri. Biblioteca ar ține evidența diferitelor metadate asociate nodurilor (de exemplu, latența acestora, ratele de răspuns 4xx/5xx etc.) și le-ar atribui ponderi în virgulă mobilă W1..WN. Pentru a sprijini strategia de execuție concomitentă, biblioteca ar trebui să poată alege aleatoriu K din N noduri - șansa de a fi selectată ar trebui să fie proporțională cu greutatea unui nod.
Propuneți un algoritm pentru a selecta eficient nodurile. Estimați complexitatea sa de calcul folosind notația mare O.
De ce este totul în engleză?
Pentru că în această formă participanții la conferință s-au luptat cu ei și pentru că engleza era limba oficială a Hydra. Sarcinile arătau astfel:
Luați hârtie și creion, gândiți-vă, nu vă grăbiți să deschideți spoilere imediat 🙂
Analiza soluției (video)
Începând cu ora 5:53, doar 4 minute:
Și iată cum băieții cu flipchart și-au propus soluția:
Analiza soluției (text)
Următoarea soluție se află la suprafață: însumați greutățile tuturor replicilor, generați un număr aleatoriu de la 0 la suma tuturor greutăților, apoi alegeți o i-replică astfel încât suma greutăților replicilor de la 0 la (i-1)-a este mai mic decât un număr aleator, iar suma greutăților replicilor de la 0 la i-a - mai mult decât aceasta. Deci, va fi posibil să selectați o replică, iar pentru a o selecta pe următoarea, trebuie să repetați întreaga procedură fără a lua în considerare replica selectată. Cu un astfel de algoritm, complexitatea alegerii unei replici este O(N), complexitatea alegerii K replicilor este O(N K) ~ O(N2).
Complexitatea patratică este proastă, dar poate fi îmbunătățită. Pentru a face acest lucru, vom construi pentru sume de greutăți. Se va obține un arbore de adâncime lg N, în frunzele căruia vor exista greutăți de replică, iar în nodurile rămase - sume parțiale, până la suma tuturor greutăților de la rădăcina arborelui. În continuare, generăm un număr aleatoriu de la 0 la suma tuturor greutăților, găsim replica i-a, o eliminăm din arbore și repetă procedura pentru a găsi replicile rămase. Cu acest algoritm, complexitatea construirii unui arbore este O(N), complexitatea găsirii i-a replică și îndepărtarea acesteia din arbore este O(lg N), complexitatea alegerii K replicilor este O(N + K lg N) ~ O(N lg N) .
Complexitatea liniar-log este mai plăcută decât complexitatea pătratică, în special pentru K mare.
Este acest algoritm Bibliotecile ClusterClient din proiect "". (Acolo, arborele este construit în O(N lg N), dar acest lucru nu afectează complexitatea finală a algoritmului.)
Sarcina 2. Zebră
A fost necesar să se propună un algoritm pentru sortarea eficientă a documentelor din memorie după un câmp arbitrar neindexat:
Echipa dvs. are sarcina de a dezvolta o bază de date de documente fragmentate în memorie. O sarcină de lucru obișnuită ar fi selectarea celor mai importante N documente sortate după un câmp numeric arbitrar (neindexat) dintr-o colecție de dimensiune M (de obicei N < 100 << M). O sarcină de lucru puțin mai puțin obișnuită ar fi să selectați top N după săriți peste documentele de top S (S ~ N).
Propuneți un algoritm care să execute astfel de interogări în mod eficient. Estimați complexitatea sa de calcul utilizând notația mare O în cazul mediu și în cel mai rău scenariu.
Analiza soluției (video)
Începând cu ora 34:50, doar 6 minute:
Analiza soluției (text)
Soluție de suprafață: sortați toate documentele (de exemplu, cu ), apoi luați documente N+S. În acest caz, complexitatea sortării este în medie O(M lg M), în cel mai rău caz O(M2).
Este evident că sortarea tuturor documentelor M și apoi preluarea doar a unei mici părți din ele este ineficientă. Pentru a nu sorta toate documentele, este potrivit un algoritm , care va selecta N + S din documentele dorite (pot fi sortate după orice algoritm). În acest caz, complexitatea va scădea în medie la O(M), în timp ce cel mai rău caz va rămâne același.
Cu toate acestea, o puteți face și mai eficient - utilizați algoritmul . În acest caz, primele documente N+S sunt adăugate la min- sau max-heap (în funcție de direcția de sortare), apoi fiecare document următor este comparat cu rădăcina arborelui, care conține documentul minim sau maxim curent, și se adaugă în arbore dacă este necesar. . În acest caz, complexitatea în cel mai rău caz, când trebuie să reconstruiți constant arborele, este O(M lg M), complexitatea în medie este O(M), ca și în cazul selecției rapide.
Cu toate acestea, fluxul heap se dovedește a fi mai eficient datorită faptului că, în practică, majoritatea documentelor pot fi aruncate fără a reconstrui heap-ul după o singură comparație cu elementul său rădăcină. O astfel de sortare este implementată în baza de date de documente în memorie Zebra dezvoltată și utilizată în Kontur.
Sarcina 3. Schimbări de stat
A fost necesar să se propună cel mai eficient algoritm pentru deplasarea stărilor:
Echipa ta are sarcina de a dezvolta un mecanism de schimb de stări fantastic pentru un cluster distribuit de N noduri. Starea celui de-al-lea nod ar trebui să fie transferată la cel de-al-lea nod (i+1), starea celui de-al-lea nod ar trebui să fie transferată la primul nod. Singura operație acceptată este schimbarea stărilor atunci când două noduri își schimbă stările atomic. Se știe că o schimbare de stare durează M milisecunde. Fiecare nod este capabil să participe la un singur schimb de stări în orice moment dat.
Cât durează transferul stărilor tuturor nodurilor dintr-un cluster?
Analiza soluției (text)
Soluție de suprafață: schimbă stările primului și celui de-al doilea element, apoi primul și al treilea, apoi primul și al patrulea și așa mai departe. După fiecare schimb, starea unui element va fi în poziția dorită. Trebuie să faceți permutări O(N) și să petreceți timp O(N M).
Timpul liniar este lung, așa că puteți schimba stările elementelor în perechi: prima cu a doua, a treia cu a patra și așa mai departe. După fiecare schimb de stat, fiecare al doilea element va fi în poziția corectă. Trebuie să faceți permutări O(lg N) și să petreceți timp O(M lg N).
Cu toate acestea, este posibil să faceți schimbarea și mai eficientă - nu în liniar, ci în timp constant. Pentru a face acest lucru, la primul pas, trebuie să schimbați starea primului element cu ultimul, al doilea cu penultimul și așa mai departe. Starea ultimului element va fi în poziția corectă. Și acum trebuie să schimbăm starea celui de-al doilea element cu ultimul, al treilea cu penultimul și așa mai departe. După această rundă de schimburi, stările tuturor elementelor vor fi în poziția corectă. Vor exista permutări O(2M) ~ O(1) în total.
O astfel de soluție nu va surprinde deloc un matematician care își amintește încă că o rotație este o compoziție a două simetrii axiale. Apropo, este generalizat trivial pentru o deplasare nu cu una, ci prin K < N poziții. (Scrieți în comentarii cum exact.)
Ți-au plăcut puzzle-urile? Cunoașteți și alte soluții? Distribuie in comentarii.
Și iată câteva link-uri utile până la urmă:
- află mai multe despre în contur
- vezi înregistrările interne despre sistemele distribuite
- urmăriți seria de prelegeri video»
- abonați-vă la noastre
Sursa: www.habr.com