Frammentazione

1.1 Cos'è lo sharding?

Se cerchi costantemente su Google, si scopre che esiste un confine piuttosto sfocato tra il cosiddetto partizionamento e il cosiddetto sharding. Ognuno chiama come vuole, come vuole. Alcune persone distinguono tra partizionamento orizzontale e sharding. Altri dicono che lo sharding è un certo tipo di partizionamento orizzontale.

Non ho trovato un solo standard terminologico che fosse approvato dai padri fondatori e certificato dall'ISO. La convinzione interiore personale è qualcosa del genere: la divisione in media è "tagliare la base in pezzi" in modo arbitrario.

• Partizionamento verticale - per colonna. Ad esempio, c'è una tabella gigante con un paio di miliardi di record in 60 colonne. Invece di mantenere una di queste tabelle giganti, conserviamo almeno 60 tabelle giganti di 2 miliardi di record ciascuna - e questa non è una base di colonna, ma un partizionamento verticale (come esempio di terminologia).
• Partizionamento orizzontale : tagliamo riga per riga, magari all'interno del server.

Il momento imbarazzante qui è la sottile differenza tra il partizionamento orizzontale e lo sharding. Posso essere tagliato a pezzi, ma non posso dirti con certezza cosa sia. C'è la sensazione che lo sharding e il partizionamento orizzontale siano più o meno la stessa cosa.

Lo sharding è, in generale, quando una grande tabella in termini di database o una raccolta professionale di documenti, oggetti, se non si dispone di un database, ma di un archivio di documenti, viene tagliata esattamente dagli oggetti. Cioè, da 2 miliardi di oggetti, i pezzi vengono selezionati indipendentemente dalle dimensioni. Gli oggetti stessi all'interno di ogni oggetto non vengono tagliati a pezzi, non li disponiamo in colonne separate, ovvero li disponiamo in lotti in luoghi diversi.

Ci sono sottili differenze terminologiche. Ad esempio, relativamente parlando, gli sviluppatori di Postgres possono dire che il partizionamento orizzontale è quando tutte le tabelle in cui è divisa la tabella principale si trovano nello stesso schema e quando su macchine diverse, questo è già partizionamento.

In senso generale, senza essere legati alla terminologia di un database specifico e di uno specifico sistema di gestione dei dati, si ha la sensazione che lo sharding stia semplicemente tagliando riga per riga / documento per documento e così via - tutto qui.

Sottolineo tipico. Nel senso che stiamo facendo tutto questo non solo per tagliare 2 miliardi di documenti in 20 tabelle, ognuna delle quali sarebbe più gestibile, ma per distribuirlo su tanti core, tanti dischi o tanti server fisici o virtuali diversi.

1.2 Dividere l'indivisibile

Resta inteso che lo facciamo in modo che ogni frammento - ogni pezzo di dati - venga replicato molte volte. Ma davvero no.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

Infatti, se esegui una tale suddivisione dei dati e da una gigantesca tabella SQL su MySQL sul tuo valoroso laptop, genererai 16 piccole tabelle, senza andare oltre un singolo laptop, non un singolo schema, non un singolo database, ecc. . e così via. - ecco fatto, hai già lo sharding.

Ciò si traduce in quanto segue:

• La larghezza di banda aumenta.
• La latenza non cambia, cioè ognuno, per così dire, lavoratore o consumatore in questo caso, ottiene il suo. Richieste diverse vengono soddisfatte all'incirca nello stesso momento.
• O entrambi, e un altro, e anche alta disponibilità (replica).

Perché larghezza di banda? A volte possiamo avere tali volumi di dati che non si adattano - non è chiaro dove, ma non si adattano - su 1 {kernel | disco | servitore | ...}. Non ci sono abbastanza risorse, tutto qui. Per lavorare con questo set di dati di grandi dimensioni, è necessario tagliarlo.

Perché la latenza? Su un core, la scansione di una tabella di 2 miliardi di righe è 20 volte più lenta della scansione di 20 tabelle su 20 core, eseguita in parallelo. I dati vengono elaborati troppo lentamente su una singola risorsa.

Perché alta disponibilità? Oppure tagliamo i dati per fare entrambe le cose contemporaneamente e allo stesso tempo diverse copie di ogni frammento: la replica garantisce un'elevata disponibilità.

1.3 Un semplice esempio "come farlo a mano"

Lo sharding condizionale può essere eliminato utilizzando la tabella di test test.documents per 32 documenti e generando 16 tabelle di test da questa tabella, circa 2 documenti ciascuna test.docs00, 01, 02, ..., 15.

INSERT INTO docs00 
SELECT * FROM documents WHERE (id%16)=0 
... 
 
INSERT INTO docs15 
SELECT * FROM documents WHERE (id%16)=15 

Perché circa? Perché a priori non sappiamo come sono distribuiti gli id, se da 1 a 32 inclusi, allora ci saranno esattamente 2 documenti ciascuno, altrimenti no.

Lo facciamo qui perché. Dopo aver realizzato 16 tabelle, possiamo "prendere" 16 di ciò di cui abbiamo bisogno. Indipendentemente da ciò che colpiamo, possiamo parallelizzare queste risorse. Ad esempio, se non c'è abbastanza spazio su disco, avrebbe senso scomporre queste tabelle su dischi separati.

Tutto questo, purtroppo, non è gratuito. Sospetto che nel caso dello standard SQL canonico (non rileggo lo standard SQL da molto tempo, forse non è stato aggiornato da molto tempo), non esiste una sintassi standardizzata ufficiale per dire a qualsiasi server SQL : "Caro server SQL, creami 32 frammenti e dividili in 4 dischi. Ma nelle singole implementazioni, c'è spesso una sintassi specifica per fare fondamentalmente la stessa cosa. PostgreSQL ha meccanismi per il partizionamento, MySQL ha MariaDB, Oracle probabilmente ha fatto tutto questo molto tempo fa.

Tuttavia, se lo facciamo a mano, senza il supporto del database e nell'ambito dello standard, paghiamo in modo condizionale con la complessità dell'accesso ai dati . Dove c'era un semplice SELECT * FROM documenti WHERE id=123, ora 16 x SELECT * FROM docsXX. Ed è positivo se proviamo a ottenere il record per chiave. Molto più interessante se stessimo cercando di ottenere una prima serie di dischi. Ora (se, sottolineo, siamo, per così dire, sciocchi e rimaniamo nell'ambito dello standard), i risultati di questi 16 SELECT * FROM dovranno essere combinati nell'applicazione.

Quale cambiamento di prestazioni puoi aspettarti?

• Intuitivamente - lineare.
• Teoricamente - sublineare, perché legge Amdahl.
• Praticamente, forse quasi linearmente, forse no.

In effetti, la risposta corretta è sconosciuta. Con un'applicazione intelligente della tecnica di sharding, puoi ottenere un significativo degrado super lineare delle prestazioni della tua applicazione e persino il DBA verrà eseguito con un poker rovente.

Vediamo come questo può essere raggiunto. È chiaro che impostare semplicemente l'impostazione su PostgreSQL shards=16, e poi decolla da solo, non è interessante. Pensiamo a come possiamo assicurarci di rallentare dallo sharding di 16 volte per 32: questo è interessante dal punto di vista di come non farlo.

I nostri tentativi di accelerare o rallentare si imbatteranno sempre nei classici: la buona vecchia legge Amdahl, che afferma che non esiste una perfetta parallelizzazione di alcuna richiesta, c'è sempre una parte coerente.

1.4 Legge Amdahl

C'è sempre una parte serializzata.

C'è sempre una parte dell'esecuzione della query che è parallelizzata e c'è sempre una parte che non è parallelizzata. Anche se ti sembra che una query perfettamente parallela, almeno la raccolta della riga del risultato che invierai al client dalle righe ricevute da ogni shard è sempre lì, ed è sempre sequenziale.

C'è sempre una parte consistente. Può essere minuscolo, completamente invisibile sullo sfondo generale, può essere gigantesco e, di conseguenza, influenzare fortemente la parallelizzazione, ma esiste sempre.

Inoltre, la sua influenza sta cambiando e può crescere in modo significativo, ad esempio, se riduciamo il nostro tavolo - alziamo la posta in gioco - da 64 record a 16 tavoli da 4 record, questa parte cambierà. Ovviamente, a giudicare da una quantità di dati così gigantesca, stiamo lavorando su un telefono cellulare e un processore da 2 MHz 86 e non abbiamo abbastanza file che possono essere tenuti aperti contemporaneamente. Apparentemente, con tali input, apriamo un file alla volta.

• Era Total = Serial + Parallel . Dove, ad esempio, parallelo è tutto il lavoro all'interno del DB e seriale invia il risultato al client.
• È diventato Total2 = Serial + Parallel/N + Xserial . Ad esempio, quando l'ordine generale ORDER BY, Xserial>0.

Con questo semplice esempio, sto cercando di mostrare che appare qualche Xserial. Oltre al fatto che c'è sempre una parte serializzata e al fatto che stiamo cercando di lavorare con i dati in parallelo, c'è una parte aggiuntiva per fornire questa suddivisione dei dati. In parole povere, potremmo aver bisogno di:

• trovare queste 16 tabelle nel dizionario interno del database;
• file aperti;
• allocare memoria;
• memoria non allocata;
• unire i risultati;
• sincronizzare tra i core.

Appaiono ancora alcuni effetti non sincronizzati. Possono essere insignificanti e occupare un miliardesimo del tempo totale, ma sono sempre diversi da zero e sempre presenti. Con il loro aiuto, possiamo perdere drasticamente le prestazioni dopo lo sharding.

Questa è un'immagine standard della legge di Amdahl. La cosa importante qui è che le linee, che idealmente dovrebbero essere diritte e crescere linearmente, incontrino un asintoto. Ma poiché il grafico da Internet è illeggibile, ho realizzato, a mio avviso, più tabelle visive con i numeri.

Supponiamo di avere una parte serializzata dell'elaborazione della richiesta che richiede solo il 5%: serial = 0.05 = 1/20 .

Intuitivamente, sembrerebbe che con una parte serializzata che richiede solo 1/20 dell'elaborazione della richiesta, se parallelizziamo l'elaborazione della richiesta per 20 core, diventerà circa 20, nel peggiore dei casi 18, volte più veloce.

In effetti, la matematica è una cosa senza cuore :

wall = 0.05 + 0.95/num_cores, speedup = 1 / (0.05 + 0.95/num_cores)

Si scopre che se si calcola attentamente, con una parte serializzata del 5%, l'accelerazione sarà di 10 volte (10,3), ovvero del 51% rispetto all'ideale teorico.

Avendo utilizzato 20 core (20 dischi, se preferisci) per l'attività su cui si lavorava, non otterremo mai nemmeno teoricamente un'accelerazione superiore a 20 volte, ma in pratica - molto meno. Inoltre, all'aumentare del numero di paralleli, l'inefficienza aumenta notevolmente.

Quando rimane solo l'1% del lavoro serializzato e il 99% è parallelizzato, i valori di accelerazione migliorano leggermente:

Per una query perfettamente termonucleare, che naturalmente richiede ore per essere completata, e il lavoro preparatorio e l'assemblaggio del risultato richiedono pochissimo tempo (seriale = 0,001), vedremo già una buona efficienza:

Tieni presente che non vedremo mai il 100% . In casi particolarmente buoni, puoi vedere, ad esempio, 99,999%, ma non esattamente 100%.