È successo pochi giorni fa . 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 all'informatica. Kontur è stato uno dei tre partner della conferenza. Abbiamo parlato allo stand, parlato dei nostri magazzini distribuiti, giocato a bingo e risolto enigmi.
Questo è un post con un'analisi dei compiti presso lo stand Kontur dell'autore del loro testo. Chi era sull'Idra - questa è la tua ragione per ricordare la piacevole esperienza, chi no - un'opportunità per allungare il cervello grande O-notazione.
Ci sono stati persino partecipanti che hanno smontato la lavagna a fogli mobili in diapositive per scrivere la loro decisione. Non sto scherzando: hanno consegnato questa risma di carta per la verifica:
C'erano tre compiti in totale:
- sulla selezione delle repliche in base al peso per il bilanciamento del carico
- sull'ordinamento dei risultati delle query rispetto a un database in memoria
- sul trasferimento di stato in un sistema distribuito con topologia ad anello
Attività 1. ClusterClient
Era necessario proporre un algoritmo per la selezione efficiente di K da N repliche pesate di un sistema distribuito:
Il tuo team ha il compito di sviluppare una libreria client per un cluster distribuito in maniera massiccia di N nodi. La libreria terrà traccia di vari metadati associati ai nodi (ad esempio, le loro latenze, velocità di risposta 4xx/5xx, ecc.) e assegnerà loro pesi in virgola mobile W1..WN. Per supportare la strategia di esecuzione concorrente, la libreria dovrebbe essere in grado di scegliere casualmente K di N nodi: la possibilità di essere selezionata dovrebbe essere proporzionale al peso di un nodo.
Proponi un algoritmo per selezionare i nodi in modo efficiente. Stima la sua complessità computazionale usando la notazione O grande.
Perché è tutto in inglese?
Perché in questa forma i partecipanti alla conferenza hanno combattuto con loro e perché l'inglese era la lingua ufficiale di Hydra. I compiti sembravano così:
Prendi carta e matita, pensa, non affrettarti ad aprire subito spoiler 🙂
Analisi della soluzione (video)
A partire dalle 5:53, solo 4 minuti:
Ed ecco come i ragazzi con la lavagna a fogli mobili hanno presentato la loro soluzione:
Analisi della soluzione (testo)
La seguente soluzione si trova in superficie: somma i pesi di tutte le repliche, genera un numero casuale da 0 alla somma di tutti i pesi, quindi scegli una i-replica tale che la somma dei pesi delle repliche da 0 a (i-1)esimo è inferiore a un numero casuale e la somma dei pesi della replica da 0 a i-esimo è maggiore di esso. Sarà quindi possibile selezionare una replica e per selezionare quella successiva è necessario ripetere l'intera procedura senza considerare la replica selezionata. Con un tale algoritmo, la complessità della scelta di una replica è O(N), la complessità della scelta di K repliche è O(N K) ~ O(N2).
La complessità quadratica è negativa, ma può essere migliorata. Per fare questo, costruiremo per somme di pesi. Si otterrà un albero di profondità lg N, nelle cui foglie ci saranno pesi replica, e nei restanti nodi - somme parziali, fino alla somma di tutti i pesi alla radice dell'albero. Successivamente, generiamo un numero casuale da 0 alla somma di tutti i pesi, troviamo la replica i-esima, la rimuoviamo dall'albero e ripetiamo la procedura per trovare le repliche rimanenti. Con questo algoritmo, la complessità di costruire un albero è O(N), la complessità di trovare la i-esima replica e rimuoverla dall'albero è O(lg N), la complessità di scegliere K repliche è O(N + K lg N) ~ O(N lg N) .
La complessità logaritmica lineare è migliore della complessità quadratica, specialmente per grandi K.
È questo algoritmo Librerie ClusterClient dal 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 l'ordinamento efficiente dei documenti in memoria mediante un campo arbitrario non indicizzato:
Il tuo team ha il compito di sviluppare un database di documenti in memoria frammentati. Un carico di lavoro comune consiste nel selezionare i primi N documenti ordinati in base a un campo numerico arbitrario (non indicizzato) da una raccolta di dimensioni M (in genere N < 100 << M). Un carico di lavoro leggermente meno comune sarebbe selezionare i primi N dopo aver saltato i primi documenti S (S ~ N).
Proponi un algoritmo per eseguire tali query in modo efficiente. Stimare la sua complessità computazionale utilizzando la notazione O grande nel caso medio e negli scenari peggiori.
Analisi della soluzione (video)
A partire dalle 34:50, solo 6 minuti:
Analisi della soluzione (testo)
Soluzione di superficie: ordina tutti i documenti (ad esempio con ), quindi prendi i documenti N+S. In questo caso, la complessità dell'ordinamento è in media O(M lg M), nel peggiore dei casi O(M2).
È ovvio che ordinare tutti i documenti M e poi prenderne solo una piccola parte è inefficiente. Per non ordinare tutti i documenti, è adatto un algoritmo , che selezionerà N + S dei documenti desiderati (possono essere ordinati con qualsiasi algoritmo). In questo caso, la complessità scenderà in media a O(M), mentre il caso peggiore rimarrà lo stesso.
Tuttavia, puoi farlo in modo ancora più efficiente: usa l'algoritmo . In questo caso, i primi documenti N+S vengono aggiunti a min- o max-heap (a seconda della direzione di ordinamento), quindi ogni documento successivo viene confrontato con la radice dell'albero, che contiene il documento minimo o massimo corrente, e viene aggiunto all'albero se necessario. . In questo caso, la complessità nel caso peggiore, quando devi ricostruire costantemente l'albero, è O (M lg M), la complessità in media è O (M), come con quickselect.
Tuttavia, l'heap streaming risulta essere più efficiente grazie al fatto che in pratica la maggior parte dei documenti può essere scartata senza ricostruire l'heap dopo un solo confronto con il suo elemento root. Tale ordinamento è implementato nel database di documenti in memoria Zebra sviluppato e utilizzato in Kontur.
Attività 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 sofisticato meccanismo di scambio di stato per un cluster distribuito di N nodi. Lo stato dell'i-esimo nodo dovrebbe essere trasferito al (i+1)-esimo nodo, lo stato dell'n-esimo nodo dovrebbe essere trasferito al primo nodo. L'unica operazione supportata è lo scambio di stato quando due nodi scambiano i loro stati in modo atomico. È noto che uno scambio di stato richiede M millisecondi. Ogni nodo è in grado di partecipare a un singolo scambio di stato 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 sarà nella posizione desiderata. Devi fare O(N) permutazioni e spendere O(N M) tempo.
Il tempo lineare è lungo, quindi puoi scambiare gli stati degli elementi a coppie: il primo con il secondo, il terzo con il quarto e così via. Dopo ogni scambio di stato, ogni secondo elemento sarà nella giusta posizione. Devi fare O(lg N) permutazioni e spendere O(M lg N) tempo.
Tuttavia, è possibile rendere lo spostamento ancora più efficiente, non in modo lineare, ma in tempo costante. Per fare ciò, al primo passaggio, è necessario scambiare lo stato del primo elemento con l'ultimo, del secondo con il penultimo e così via. Lo stato dell'ultimo elemento sarà nella posizione corretta. E ora dobbiamo scambiare lo stato del secondo elemento con l'ultimo, del terzo con il penultimo e così via. Dopo questo giro di scambi, gli stati di tutti gli elementi saranno nella giusta posizione. Ci saranno permutazioni O(2M) ~ O(1) in totale.
Una tale soluzione non sorprenderà affatto un matematico che ricordi ancora che una rotazione è una composizione di due simmetrie assiali. A proposito, è banalmente generalizzato per uno spostamento non di uno, ma di K <N posizioni. (Scrivi nei commenti come esattamente.)
Ti sono piaciuti i puzzle? Conosci altre soluzioni? Condividi nei commenti.
Ed ecco alcuni link utili alla fine:
- impara di più riguardo di contorno
- vedere i record di interno sui sistemi distribuiti
- guarda la serie di videolezioni»
- iscriviti al nostro
Fonte: habr.com