Qualche giorno fa si è svolta . I ragazzi di JUG.ru Group hanno invitato relatori da sogno (Leslie Lamport! Cliff Click! Martin Kleppmann!) e hanno dedicato due giorni ai sistemi distribuiti e al calcolo. Contur è stata uno dei tre partner della conferenza. Abbiamo interagito al nostro stand, parlato delle nostre memorie distribuite, giocato a bingo e risolto dei problemi.
Questo è un post che analizza i problemi presentati allo stand di Contur, scritto dall'autore del testo. Chi era presente a Hydra ha ora l'opportunità di ricordare piacevoli esperienze, mentre chi non c'era ha la possibilità di esercitare la mente. big O-notazione.
Ci sono stati anche partecipanti che hanno smontato una lavagna per fare slides e annotare la propria soluzione. Non sto scherzando — hanno consegnato per la revisione un tale fascicolo di carta:
In totale c'erano tre problemi:
- sulla scelta delle repliche in base ai pesi per il bilanciamento del carico
- sulla ordinazione dei risultati di una query su un database in-memory
- sulla trasmissione dello stato in un sistema distribuito con topologia ad anello
Problema 1. ClusterClient
E' stato richiesto di proporre un algoritmo efficace per la scelta di K da N repliche pesate in un sistema distribuito:
Il tuo team ha il compito di sviluppare una libreria client per un cluster massivamente distribuito di N nodi. La libreria dovrebbe tenere traccia di vari metadati associati ai nodi (ad esempio, le loro latenze, i tassi di risposta 4xx/5xx, ecc.) e assegnare pesi in virgola mobile W1..WN a ciascuno di essi. Per supportare la strategia di esecuzione concorrente, la libreria dovrebbe essere in grado di selezionare K di N nodi in modo casuale, con la probabilità di essere selezionati proporzionale al peso di un nodo.
Proponi un algoritmo per selezionare i nodi in modo efficiente. Stima la sua complessità computazionale utilizzando la notazione big O.
Why is everything in English?
Because in this form it was contested by the conference participants and because English was the official language of Hydra. The problems looked like this:
Prendi carta e penna, pensa, non avere fretta di aprire subito gli spoiler 🙂
Analisi della soluzione (video)
Inizio alle 5:53, durata totale 4 minuti:
Ecco come hanno presentato la loro soluzione quei ragazzi con il flipchart:
Analisi della soluzione (testo)
Una soluzione semplice è la seguente: sommare i pesi di tutte le repliche, generare un numero casuale da 0 a somma di tutti i pesi, quindi selezionare la i-esima replica tale che la somma dei pesi delle repliche da 0 a (i-1) sia minore del numero casuale, mentre la somma dei pesi delle repliche da 0 a i-esima sia maggiore. In questo modo si ottiene una replica. Per selezionare la successiva, si deve ripetere l'intera procedura, escludendo la replica già scelta. Con questo algoritmo, la complessità della scelta di una replica è O(N), la complessità della scelta di K repliche è O(N·K) ~ O(N²).
La complessità quadratica è un problema, ma può essere migliorata. Per questo costruiamo per le somme dei pesi. Si ottiene un albero di profondità lg N, le cui foglie contengono i pesi delle repliche, mentre negli altri nodi ci sono somme parziali, fino alla somma di tutti i pesi nella radice dell'albero. Successivamente generiamo un numero casuale da 0 alla somma di tutti i pesi, troviamo la i-esima replica, la rimuoviamo dall'albero e ripetiamo la procedura per cercare le repliche rimanenti. Con questo algoritmo, la complessità di costruzione dell'albero è O(N), la complessità per trovare la i-esima replica e rimuoverla dall'albero è O(lg N), la complessità della selezione di K repliche è O(N + K lg N) ~ O(N lg N).
La complessità lineare-logaritmica è preferibile a quella quadratica, specialmente per grandi K.
Questo algoritmo della libreria ClusterClient del progetto «». (Lì l'albero è costruito in O(N lg N), ma ciò non influisce sulla complessità finale dell'algoritmo.)
Compito 2. Zebra
Era necessario proporre un algoritmo per la corretta ordinazione dei documenti in memoria su un campo arbitrario non indicizzato:
Il tuo team ha il compito di sviluppare un database di documenti in memoria suddiviso in partizioni. Un carico di lavoro comune sarebbe selezionare i primi N documenti ordinati per un campo numerico arbitrario (non indicizzato) da una collezione di dimensione M (di solito N < 100 << M). Un carico di lavoro leggermente meno comune sarebbe selezionare i primi N dopo aver saltato i primi S documenti (S ~ N).
Proponi un algoritmo per eseguire tali query in modo efficiente. Stima la sua complessità computazionale utilizzando la notazione big O nei casi medi e peggiori.
Analisi della soluzione (video)
Inizio a 34:50, durando in totale 6 minuti:
Analisi della soluzione (testo)
La soluzione è evidente: ordinare tutti i documenti (ad esempio, usando ), poi prendere N+S documenti. In tal caso, la complessità di ordinamento in media è di O(M lg M), nel peggiore dei casi è O(M2).
È ovvio che ordinare tutti i M documenti per poi prendere solo una piccola parte di essi è inefficiente. Per evitare di ordinare tutti i documenti, si adatta l'algoritmo , che selezionerà i documenti N+S necessari (che potranno essere ordinati secondo qualsiasi algoritmo). In questo caso, la complessità si ridurrà in media a O(M), mentre il caso peggiore rimarrà lo stesso.
Tuttavia, si può fare anche meglio — utilizzando l'algoritmo . In questo caso, i primi N+S documenti vengono inseriti in un min- o max-heap (a seconda della direzione dell'ordinamento), e poi ogni documento successivo viene confrontato con la radice dell'albero, dove si trova il documento attualmente minimo o massimo, e, se necessario, viene aggiunto all'albero. In questo caso, la complessità nel caso peggiore, quando sarà necessario ricostruire costantemente l'albero, è O(M lg M), mentre la complessità in media è O(M), proprio come usando il quickselect.
Tuttavia, lo heap streaming si dimostra più efficiente poiché, nella pratica, è possibile scartare la maggior parte dei documenti senza ricostruire la heap, dopo un'unica comparazione con il suo elemento radice. Questo tipo di ordinamento è implementato nel database in-memory Zebra, sviluppato e usato in Kontur.
Compito 3. Scambi di stato
Era necessario proporre l'algoritmo più efficiente per lo spostamento degli stati:
Il tuo team ha il compito di sviluppare un meccanismo di scambio di stati per un cluster distribuito di N nodi. Lo stato del nodo i deve essere trasferito al nodo (i+1), mentre lo stato del nodo N deve essere trasferito al primo nodo. L'unica operazione supportata è lo scambio di stati, quando due nodi scambiano i loro stati in modo atomico. È noto che uno scambio di stati richiede M millisecondi. Ogni nodo può partecipare a un singolo scambio di stati in un dato momento.
Quanto tempo ci vuole per trasferire gli stati di tutti i nodi in un cluster?
Analisi della soluzione (testo)
Soluzione superficiale: scambiare gli stati del primo e del secondo elemento, poi del primo e del terzo, poi del primo e del quarto e così via. Dopo ogni scambio, lo stato di un elemento si troverà nella posizione corretta. Sarà necessario effettuare O(N) permutazioni e impiegare O(N·M) tempo.
Il tempo lineare è lungo, quindi si possono scambiare gli stati degli elementi a coppie: il primo con il secondo, il terzo con il quarto e così via. Dopo ogni scambio, lo stato di ciascun secondo elemento si troverà nella posizione corretta. Sarà necessario effettuare O(lg N) permutazioni e impiegare O(M lg N) tempo.
Tuttavia, è possibile rendere lo spostamento ancora più efficiente — non in tempo lineare, ma in tempo costante. Per fare questo, nel primo passo bisogna scambiare lo stato del primo elemento con l'ultimo, del secondo con il penultimo e così via. Lo stato dell'ultimo elemento si troverà nella posizione corretta. Ora bisogna scambiare lo stato del secondo elemento con l'ultimo, del terzo con il penultimo e così via. Dopo questo turno di scambi, lo stato di tutti gli elementi si troverà nelle posizioni desiderate. In totale verranno effettuate O(2M) ~ O(1) permutazioni.
Questa soluzione non sorprenderà affatto un matematico, che ricorda ancora che una rotazione è una composizione di due simmetrie assiali. Tra l'altro, è facilmente generalizzabile per uno spostamento non di una, ma di K < N posizioni. (Scrivete nei commenti come esattamente.)
Ti sono piaciuti gli esercizi? Conosci altre soluzioni? Condividi nei commenti.
Ecco alcuni link utili alla fine:
- scopri di più su in Kontur
- guarda le registrazioni delle sui sistemi distribuiti
- guarda il ciclo di videolezioni "»
- iscriviti al nostro
Fonte: habr.com
