Sharding: retro

2.1 Come frammentare e rallentare N volte?

Puoi frammentare e rallentare esattamente N volte in questo modo:

• Invia richieste docs00...docs15 in sequenza , non in parallelo.
• Nelle query semplici, effettuare una selezione non per chiave , WHERE qualcosa=234.

In questo caso, la parte serializzata (seriale) occupa non l'1% e non il 5%, ma circa il 20% nei database moderni. Puoi anche ottenere il 50% della parte serializzata se accedi al database utilizzando un protocollo binario estremamente efficiente o lo colleghi come libreria dinamica in uno script Python.

Il resto del tempo di elaborazione di una semplice richiesta sarà occupato da operazioni non parallelizzabili di analisi della richiesta, preparazione del piano, ecc. Cioè, non leggere il record rallenta.

Se dividiamo i dati in 16 tabelle e li eseguiamo in sequenza, come è consuetudine nel linguaggio di programmazione PHP, ad esempio (non è molto bravo a lanciare processi asincroni), otterremo un rallentamento di 16 volte. E, forse, anche di più, perché si aggiungeranno anche i giri di rete.

All'improvviso, la scelta del linguaggio di programmazione è importante durante lo sharding.

Ricorda la scelta del linguaggio di programmazione, perché se invii query al database (o al server di ricerca) in sequenza, da dove viene l'accelerazione? Piuttosto, ci sarà un rallentamento.

2.2 A proposito di semiautomatico

In alcuni punti, la raffinatezza della tecnologia dell'informazione ispira orrore ctonio. Ad esempio, MySQL out of the box non aveva sicuramente l'implementazione dello sharding in determinate versioni, tuttavia le dimensioni dei database utilizzati in battaglia crescono a valori indecenti.

L'umanità sofferente di fronte ai singoli DBA è stata tormentata per anni e scrive diverse pessime soluzioni di sharding basate sul nulla. Successivamente, viene scritta una soluzione di sharding più o meno decente chiamata ProxySQL (MariaDB/Spider, PG/pg_shard/Citus, ...). Questo è un noto esempio di questa stessa macchia.

ProxySQL nel suo insieme è, ovviamente, una soluzione completa di classe enterprise per l'open source, per il routing e altro ancora. Ma uno dei compiti da risolvere è lo sharding per un database, che di per sé non può essere shard in modo umano. Vedi, non c'è l'opzione "shards = 16", o devi riscrivere ogni richiesta nell'applicazione, e ce ne sono molte in alcuni punti, o mettere uno strato intermedio tra l'applicazione e il database che sembra: "Hmm ... SELEZIONA * DA documenti? Sì, deve essere suddiviso in 16 piccoli SELECT * FROM server1.document1, SELECT * FROM server2.document2 - a questo server con tale login / password, a questo con un altro. Se uno non ha risposto, allora ... ", ecc. Esattamente questo può essere fatto da macchie intermedie. Sono leggermente inferiori rispetto a tutti i database. Per PostgreSQL, per quanto ho capito,

La configurazione di ciascuna patch specifica è un argomento gigante separato che non rientra in un rapporto, quindi discuteremo solo i concetti di base. Parliamo meglio un po' della teoria del ronzio.

2.3 Automazione assolutamente perfetta?

L'intera teoria di sballarsi nel caso dello sharding in questa lettera F() , il principio di base è sempre lo stesso all'incirca: shard_id = F(oggetto).

Sharding: di cosa si tratta? Abbiamo 2 miliardi di record (o 64). Vogliamo spezzarli in più pezzi. Sorge una domanda inaspettata: come? In base a quale principio dovrei disperdere i miei 2 miliardi di record (o 64) su 16 server a mia disposizione?

Il matematico latente in noi dovrebbe suggerire che alla fine c'è sempre qualche funzione magica che, per ogni documento (oggetto, linea, ecc.), determinerà in quale pezzo metterlo.

Andando più a fondo nella matematica, questa funzione dipende sempre non solo dall'oggetto stesso (la riga stessa), ma anche da impostazioni esterne come il numero totale di shard. Una funzione che per ogni oggetto deve dire dove metterlo, non può restituire un valore in più di quanti sono i server presenti nel sistema. E le funzioni sono leggermente diverse:

shard_func = F1(object); 
shard_id = F2(shard_func, ...); 
shard_id = F2(F1(object), current_num_shards, ...). 

Ma ulteriormente non scaveremo in queste terre selvagge di singole funzioni, parleremo solo di quali sono le funzioni magiche F ().

2.4 Cosa sono F()?

Possono inventare molti meccanismi di implementazione diversi e molti diversi. Esempio di riepilogo:

• F = rand() % nums_shards
• F = somehash(object.id) % num_shards
• F = object.date % num_shards
• F = object.user_id % num_shards
• ...
• F = tabella_shard [qualche hash() |… oggetto.data |… ]

Un fatto interessante - puoi naturalmente distribuire tutti i dati in modo casuale - gettiamo il record successivo su un server arbitrario, su un core arbitrario, in una tabella arbitraria. Non ci sarà molta felicità in questo, ma funzionerà.

Esistono metodi leggermente più intelligenti per eseguire il frammento mediante una funzione hash riproducibile o addirittura coerente o il frammento mediante qualche attributo. Esaminiamo ogni metodo.

F = rand()

Scattering in giro non è un metodo molto corretto. Un problema: abbiamo sparso i nostri 2 miliardi di record su un migliaio di server in modo casuale e non sappiamo dove sia il record. Dobbiamo estrarre l'utente_1, ma non sappiamo dove sia. Andiamo su un migliaio di server e sistemiamo tutto - in qualche modo questo è inefficiente.

F = qualche hash()

Disperdiamo gli utenti in modo adulto: calcoliamo la funzione hash riproducibile da user_id, prendiamo il resto della divisione per il numero di server e contattiamo immediatamente il server desiderato.

Perché stiamo facendo questo? E poi, che abbiamo un carico elevato e nient'altro si adatta a un server. Se si adatta, la vita sarebbe così semplice.

Ottimo, la situazione è già migliorata, per ottenere un record andiamo in anticipo su un server conosciuto. Ma se abbiamo un intervallo di chiavi, allora in questo intero intervallo dobbiamo esaminare tutti i valori delle chiavi e, al limite, andare a tanti frammenti quante sono le chiavi nell'intervallo, o anche a ciascun server. La situazione è migliorata, certo, ma non per tutte le richieste. Alcune query sono state interessate.

Sharding naturale (F = object.date % num_shards)

A volte, cioè spesso, il 95% del traffico e il 95% del carico sono richieste che hanno una sorta di sharding naturale. Ad esempio, il 95% delle query di analisi sociale condizionale influisce sui dati solo per gli ultimi 1 giorno, 3 giorni, 7 giorni e il restante 5% si riferisce agli ultimi anni. Ma il 95% delle richieste è quindi naturalmente frammentato per data, l'interesse degli utenti del sistema è concentrato sugli ultimi giorni.

In questo caso, puoi dividere i dati per data, ad esempio, per un giorno, e seguire la risposta alla richiesta di un rapporto per un giorno o un oggetto da questo giorno a questo frammento e andare.

La vita sta migliorando: ora non solo conosciamo la posizione di un particolare oggetto, ma conosciamo anche la portata. Se non ci viene chiesto un intervallo di date, ma un intervallo di altre colonne, allora, ovviamente, dovremo esaminare tutti i frammenti. Ma secondo le regole del gioco, abbiamo solo il 5% di tali richieste.

Sembra che abbiamo trovato una soluzione ideale per tutto, ma ci sono due problemi:

• Questa soluzione è su misura per un caso specifico, quando il 95% delle richieste riguarda solo l'ultima settimana.
• Poiché il 95% delle richieste tocca l'ultima settimana, cadranno tutte su uno shard che serve quest'ultima settimana. Questo frammento si scioglierà, mentre tutti gli altri saranno inattivi durante questo periodo. Allo stesso tempo, non puoi buttarli via, anche i dati di archivio devono essere archiviati.

Per non dire che questo è un cattivo schema di sharding: tagliamo i dati caldi, tuttavia, è necessario fare qualcosa con il frammento più caldo.

Il problema è risolto da buffonate, salti e impiastri, ovvero un aumento del numero di repliche per il giorno in corso in fiamme, quindi una graduale diminuzione del numero di repliche quando questo giorno diventa passato ed entra nell'archivio. Non esiste una soluzione ideale chiamata "devi solo diffondere i dati nel cluster con una funzione hash magica in modo sbagliato".

2.5 Prezzo da pagare

Formalmente, ora sappiamo di sapere "tutto". È vero, non conosciamo un mal di testa gigante e due mal di testa più piccoli.

1. Dolore semplice: gravemente spalmato

Questo è un esempio da un libro di testo, che non si verifica quasi mai in battaglia, ma all'improvviso.

• Ad esempio con una data, solo senza data!
• Distribuzione irregolare (percepibile) non intenzionale .

Hanno scelto il meccanismo di sharding e/o i dati sono cambiati e, ovviamente, il PM non ha trasmesso i requisiti (non abbiamo errori nel codice, il PM non riporta sempre i requisiti) e la distribuzione divenne mostruosamente irregolare. Cioè, hanno mancato il criterio.

Per catturare, devi guardare la dimensione dei frammenti. Vedremo sicuramente il problema nel momento in cui uno dei nostri frammenti si surriscalda o diventa 100 volte più grande degli altri. Puoi risolverlo semplicemente sostituendo la chiave o la funzione di sharding.

Questo è un problema semplice, a dire il vero, non credo che almeno una persona su cento si imbatterà in questo nella vita, ma all'improvviso aiuterà almeno qualcuno.

2. Dolore "invincibile": aggregazione, unione

Come effettuare selezioni che uniscono un miliardo di record da una tabella per un miliardo di record da un'altra tabella?

• Come calcolare "rapidamente"... WHERE randcol TRA aaa E bbb?
• Come fare in modo "intelligente"... users_32shards JOIN posts_1024 shards?

Risposta breve: assolutamente no, soffri!

Se hai distribuito un miliardo di record a mille server nella prima tabella in modo che funzionino più velocemente e hai fatto lo stesso nella seconda tabella, allora naturalmente da mille a mille server dovrebbero parlare tra loro in coppia. Un milione di connessioni non funzionerà bene. Se effettuiamo richieste al database (ricerca, archiviazione, archivio documenti o file system distribuito) che non si adattano bene allo sharding, queste richieste rallenteranno notevolmente.

Un punto importante è che alcune richieste saranno sempre imbrattate senza successo e rallenteranno . È importante cercare di ridurre al minimo la loro percentuale. Di conseguenza, non è necessario creare join giganteschi con un miliardo per miliardo di record. Se è possibile replicare una piccola tabella, relativa alla quale ci si sta unendo in una gigantesca tabella condivisa, a tutti i nodi, si dovrebbe farlo. Se i join sono effettivamente locali in qualche modo, ad esempio, è possibile posizionare l'utente e i suoi post uno accanto all'altro, partizionarli allo stesso modo e fare tutti i join all'interno della stessa macchina: devi fare proprio questo .

Questo è un corso separato di lezioni per tre giorni, quindi passiamo all'ultimo dolore infernale e ai diversi algoritmi per affrontarlo.

2.6. Dolore complesso/lungo: Resharding

Preparati: se hai condiviso i tuoi dati per la prima volta nella tua vita, in media li condividerai altre cinque volte.

Indipendentemente dal numero di cluster che configuri, devi comunque eseguire il resharding.

Se sei molto intelligente e fortunato, allora overshard almeno una volta. Ma una volta che sei sicuro, perché nel momento in cui pensi che 10 unità siano sufficienti per l'utente, qualcuno proprio in quel momento scrive una richiesta per 30 e prevede di avere una richiesta per 100 unità di risorse sconosciute. I frammenti non sono mai abbastanza. Con il primo schema di sharding, in ogni caso, ti mancherà - dovrai sempre aumentare il numero di server da aggiungere o fare qualcos'altro - in generale, in qualche modo riconfezionare i dati.

Va bene se abbiamo delle buone potenze di due: c'erano 16 frammenti di server, ora sono 32. È più divertente se fosse 17, è 23 - due numeri vasimalmente primi. Come fanno i database, forse hanno una sorta di magia dentro?

La risposta corretta è: no, non c'è magia dentro, hanno l'inferno dentro.

Successivamente, considereremo cosa si può fare "a mano", forse capiremo "come una macchina automatica".

Sulla fronte #1. Riposiziona tutto

Per tutti gli oggetti, consideriamo NewF(oggetto), passa a un nuovo frammento.

La possibilità di corrispondenza NewF()=OldF() è bassa.

Copriamo quasi tutto.

OH.

Spero che non esista un tale inferno come trasferire tutti i 2 miliardi di dischi dai vecchi frammenti a quelli nuovi. L'approccio ingenuo è comprensibile: c'erano 17 macchine, 6 macchine sono state aggiunte al cluster, 2 miliardi di record sono stati smistati, sono stati spostati da 17 macchine a 23 macchine. Una volta ogni 10 anni, probabilmente puoi persino farlo. Ma nel complesso è una mossa sbagliata.

Sulla fronte #2. Trasferisci la metà

Il prossimo ingenuo miglioramento - abbandoniamo uno schema così stupido - proibirà a 17 auto di rimodellarsi in 23, e rimosseremo sempre 16 auto in 32 auto! Quindi, secondo la teoria, dovremo spostare esattamente la metà dei dati, e in pratica possiamo anche farlo.

Per tutti gli oggetti, consideriamo NewF(oggetto), passa a un nuovo frammento.

Era rigorosamente 2^N, ora è rigorosamente 2^(N+1) frammenti.

La probabilità di trovare NewF()=OldF() è 0,5.

Trasferiamo circa il 50% dei dati.

Ottimale, ma funziona solo per potenze di due.

In linea di principio va tutto bene, tranne il legame alla potenza di due in termini di numero di auto. Questo approccio ingenuo, stranamente, può funzionare.

Si noti che anche la suddivisione aggiuntiva del cluster per potenze di due in questo caso è ottimale. In ogni caso, aggiungendo 16 macchine a un cluster di 16, siamo obbligati a spostare metà dei dati, esattamente metà e spostare.

Ok, ma l'umanità non ha davvero inventato nient'altro - la domanda nasce da una mente curiosa.

Più divertente #3. Hashing coerente

Naturalmente, qui è richiesta un'immagine con un cerchio sull'hashing coerente.

Se cerchi su Google "hashing coerente", verrà sicuramente fuori un cerchio, tutti i risultati sono popolati da cerchi.

Idea: disegniamo gli identificatori di shard (hash) su un cerchio e contrassegniamo gli identificatori del server con hash in alto. Quando è necessario aggiungere un server, inseriamo un nuovo punto nel cerchio e ciò che si è rivelato vicino ad esso (e solo ciò che si è rivelato vicino ad esso), lo trasferiamo.

Quando aggiungiamo un frammento: esaminiamo non tutto, ma solo 2 "vicini", spostiamo in media 1/n.

Quando eliminiamo un frammento: guardiamo solo il frammento che viene eliminato, lo spostiamo solo. Tipo di ottimale.

Molto efficace in termini di riduzione al minimo del traffico quando si aggiunge uno shard e assolutamente disgustoso in termini di normale bilanciamento dei dati. Perché quando eseguiamo l'hashing di tutti questi oggetti che distribuiamo a un gran numero di macchine, lo facciamo in modo relativamente irregolare: i punti attorno al cerchio sono distanziati in modo non uniforme e il carico di ogni particolare nodo può essere molto diverso dal resto.

Questo problema è risolto dall'ultima riga del nodo virtuale. Ogni nodo, ogni server sul cerchio è indicato da più di un punto. Aggiungendo un server, uno shard, ecc., stiamo aggiungendo alcuni punti. Ogni volta che rimuoviamo qualcosa, rimuoviamo di conseguenza alcuni punti e spostiamo una piccola parte dei dati.

Sto parlando di questo spazio con i cerchi, perché, ad esempio, un tale schema è all'interno di Cassandra. Cioè, quando ha iniziato a inseguire i record tra i nodi, sappi che il cerchio ti sta guardando e probabilmente non approva.

Tuttavia, rispetto ai primi metodi, la vita è migliorata: quando aggiungiamo / rimuoviamo un frammento, esaminiamo già non tutti i record, ma solo una parte e spostiamo solo una parte.

Attenzione, la domanda è: si può migliorare ulteriormente? E anche migliorare l'uniformità del caricamento dei frammenti? Dicono che è possibile!

Più divertente #4. Appuntamento/HRW

La prossima semplice idea (il materiale è educativo, quindi niente di complicato): shard_id = arg max hash(object_id, shard_id).

Perché si chiama Rendezvous hashing non lo so, ma so perché si chiama Highest Random Weight. È molto facile visualizzarlo in questo modo:

Abbiamo, ad esempio, 16 frammenti. Per ogni oggetto (stringa) che deve essere inserito da qualche parte, calcoliamo 16 hash a seconda dell'oggetto dal numero di shard. Vince chi ha il valore di hash più alto.

Questo è il cosiddetto HRW-hashing, noto anche come Rendezvous hashing. Stupido come un bastone, lo schema per calcolare il numero di un frammento, in primo luogo, è più facile da vedere rispetto ai cerchi e, d'altra parte, dà un carico uniforme.

L'unico aspetto negativo è che l'aggiunta di un nuovo frammento è peggiorato per noi. C'è il rischio che quando si aggiunge un nuovo shard, abbiamo ancora degli hash che cambieranno e potrebbe essere necessario rivedere tutto. La tecnologia di rimozione dei frammenti non è cambiata molto.

Un altro problema è che è computazionalmente pesante con un gran numero di frammenti.

Più divertente #5. Più tecniche

È interessante notare che la ricerca non si ferma e Google pubblica ogni anno alcune nuove tecnologie spaziali:

• Jump Hash - Google '2014.
• Sonda multipla—Google '2015.
• Maglev-Google '2016.

Se sei interessato all'argomento, puoi leggere molte dissertazioni. Presento questi dati per chiarire che il problema non è stato risolto, non esiste una super-soluzione che possa essere implementata in tutti i database. Fino ad ora, le persone difendono le dissertazioni.

conclusioni

Esiste un'importante tecnica di base chiamata sharding che prende il nome da Gallius Julius Caesar: "Dividi et impera, regola e dividi!". Se i dati non rientrano in un server, è necessario suddividerli in 20 server.

Dopo aver appreso tutto questo, si dovrebbe avere l'impressione che sarebbe meglio non shard. Se decidi che sarebbe meglio non shard, questa è la sensazione giusta. Se puoi aggiungere memoria al server per $ 100 e non partizionare nulla, allora dovresti farlo. Durante lo sharding, apparirà un complesso sistema distribuito con il trasferimento di dati avanti e indietro, impilando i dati in nessuno sa dove. Se può essere evitato, deve essere evitato.

È meglio non farlo a mano, è meglio che la "base" (ricerca, DFS, ...) possa shard da sola. In ogni caso, prima o poi, arriverà un carico elevato e in qualche modo i dati dovranno essere suddivisi. Non è un dato di fatto che anche se la base può farlo da sola, non incontrerai alcun problema. Ricorda il fondamentalismo algoritmico: devi capire come funziona tutto all'interno.

Quando imposti lo sharding per la prima volta, scegli attentamente F(), pensa a richieste, rete, ecc. Ma preparati, probabilmente dovrai scegliere 2 volte e almeno una volta dovrai rifare tutto.