Caratteristiche della progettazione del modello dati per NoSQL

Introduzione

«Devi correre a tutta velocità per rimanere fermo,
e per andare da qualche parte devi correre almeno il doppio più veloce!»
(c) Alice nel Paese delle Meraviglie

Tempo fa, mi è stato chiesto di tenere una lezione agli analisti della nostra azienda sul tema della progettazione dei modelli dati, poiché passiamo molto tempo su progetti (a volte per anni) e perdiamo di vista ciò che accade nel mondo delle tecnologie IT. Nella nostra azienda (così è andata) molte volte non utilizziamo database NoSQL (almeno per ora), quindi nella mia lezione ho dedicato particolare attenzione a questo aspetto prendendo come esempio HBase e ho cercato di orientare l'esposizione del materiale a chi non ha mai lavorato con essi. In particolare, ho illustrato alcune peculiarità della progettazione del modello dati utilizzando l'esempio di un articolo che ho letto alcuni anni fa nell'articolo «Introduction to HBase Schema Design» di Amandeep Khurana. Analizzando gli esempi, ho confrontato diverse soluzioni per lo stesso problema, per trasmettere meglio ai partecipanti le idee principali.

Recentemente, "per passare il tempo", mi sono chiesto (lungo il lungo weekend di maggio in regime di quarantena, questo si addice particolarmente) quanto le considerazioni teoriche corrispondano alla pratica. In effetti, così è nata l'idea di questo articolo. Un sviluppatore che lavora da un po' con NoSQL potrebbe non trarre nulla di nuovo da questo (e quindi può scrollare verso il basso per metà articolo). Tuttavia, per analysts, coloro che non hanno mai lavorato a stretto contatto con NoSQL, credo che sarà utile per avere una comprensione di base delle peculiarità nella progettazione dei modelli di dati per HBase.

Analisi di un esempio

A mio avviso, prima di iniziare a utilizzare i database NoSQL, è necessario riflettere attentamente e ponderare i pro e i contro. Spesso, il problema può essere risolto anche con i tradizionali database relazionali. Perciò, è meglio evitare di utilizzare NoSQL senza motivazioni sostanziali. Se la decisione di utilizzare un database NoSQL è già stata presa, va considerato che gli approcci alla progettazione sono leggermente diversi. Soprattutto alcuni di essi possono risultare insoliti per coloro che hanno avuto a che fare solo con database relazionali (secondo le mie osservazioni). Nel mondo "relazionale", di solito partiamo dalla modellazione del dominio e poi, se necessario, denormalizziamo il modello. Nel NoSQL, invece, noi dobbiamo subito considerare i potenziali scenari di utilizzo dei dati e denormalizzare i dati fin dall'inizio. Inoltre, ci sono altre differenze di cui si parlerà in seguito.

Esaminiamo il seguente compito "sintetico" con cui lavoreremo in seguito:

È necessario progettare una struttura di archiviazione per l'elenco degli amici degli utenti di un'astratta rete sociale. Per semplificare, consideriamo che tutte le relazioni siano unidirezionali (come su Instagram, e non su LinkedIn). La struttura deve consentire di:

• Rispondere alla domanda se l'utente A segua l'utente B (modello di lettura)
• Consentire di aggiungere/rimuovere relazioni nel caso in cui l'utente A si iscriva/disiscriva dall'utente B (modello di modifica dei dati)

Naturalmente, ci sono molteplici modi per risolvere il problema. In un normale database relazionale, probabilmente useremmo una tabella delle relazioni (magari tipizzata, se ad esempio è necessario memorizzare un gruppo di utenti: famiglia, lavoro, ecc., che include questo "amico"), e per ottimizzare la velocità di accesso, potremmo aggiungere indici/partizionamento. Probabilmente, la tabella finale apparirebbe più o meno in questo modo:

user_id
friend_id

Vasya
Petya

Vasya
Olya

qui e oltre utilizzerò i nomi anziché gli ID per chiarezza e migliore comprensione

Nel caso di HBase, sappiamo che:

• una ricerca efficace, che non porta a una scansione completa della tabella, è possibile esclusivamente per chiave
  • In effetti, scrivere le solite query SQL per questi tipi di database è una cattiva idea; tecnicamente, potete inviare una query SQL con JOIN e altra logica in HBase da Impala, ma sarà veramente efficace?

Pertanto, siamo costretti a usare l'ID utente come chiave. Un primo pensiero su "dove e come memorizzare gli ID degli amici?" potrebbe essere l'idea di memorizzarli in colonne. Questa soluzione ovvia e "naïve" apparirà all'incirca così (chiamiamola Opzione 1 (default), per riferirsi in seguito):

RowKey
Colonne

Vasya
1: Petya
2: Olya
3: Dasha

Petya
1: Masha
2: Vasya

Qui ogni riga corrisponde a un singolo utente della rete. Le colonne hanno nomi: 1, 2, … — a seconda del numero di amici, e negli slot delle colonne sono memorizzati gli ID degli amici. È importante notare che ogni riga avrà un numero diverso di colonne. Nell'esempio qui sopra, una riga ha tre colonne (1, 2 e 3), e l'altra solo due (1 e 2) – qui abbiamo sfruttato due proprietà di HBase che non si trovano nei database relazionali:

• la possibilità di cambiare dinamicamente la composizione delle colonne (aggiungendo un amico -> aggiungendo una colonna, rimuovendo un amico -> rimuovendo una colonna)
• le diverse righe possono avere composizioni di colonne differenti

Verifichiamo la nostra struttura rispetto ai requisiti del compito:

• Lettura dei dati: per capire se Vasya è iscritto a Olya, dovremo leggere l'intera riga con la chiave RowKey = «Vasya» e scorrere i valori delle colonne finché non troviamo Olya. Oppure controllare i valori di tutte le colonne, non trovare Olya e restituire la risposta False;
• Modifica dei dati: aggiunta di un amico: per un compito simile, avremo bisogno di leggere l'intera riga con la chiave RowKey = «Vasya» per contare il numero totale dei suoi amici. Questo numero totale ci serve per determinare il numero della colonna in cui записare l'ID del nuovo amico.
• Modifica dei dati: rimozione di un amico:
  • Dobbiamo leggere l'intera riga con la chiave RowKey = «Vasya» e scorrere le colonne per trovare quella specifica in cui è registrato l'amico da rimuovere;
  • Dopo la rimozione dell'amico, dobbiamo «spostare» tutti i dati di una colonna per evitare di avere «lacune» nella loro numerazione.

Ora valutiamo quanto siano efficienti gli algoritmi che dovremo implementare nel «ipotetico applicativo» utilizzando O-simbolismo. Denotiamo la dimensione della nostra ipotetica rete sociale come n. Pertanto, il numero massimo di amici per un utente può essere (n-1). Possiamo trascurare questo (-1) per i nostri scopi, poiché nell'ambito dell'utilizzo dell'O-simbolismo risulta trascurabile.

• Lettura dei dati: è necessario esaminare l'intera riga ed esplorare in limite tutte le sue colonne. Quindi la valutazione superiore dei costi sarà approssimativamente O(n)
• Modifica dei dati: aggiunta di un amico: per determinare il numero di amici è necessario esaminare tutte le colonne della riga, dopo di che inserire una nuova colonna => O(n)
• Modifica dei dati: rimozione di un amico:
  • Analogamente all'aggiunta – è richiesto esplorare in limite tutte le colonne => O(n)
  • Dopo aver rimosso le colonne, dobbiamo "spostarle". Se affrontiamo questo "di petto", potremmo aver bisogno fino a (n-1) operazioni. Tuttavia, qui e in seguito, nella parte pratica, applicheremo un approccio diverso, che realizzerà uno "spostamento fittizio" in un numero fisso di operazioni – il che significa che richiederà un tempo costante a prescindere da n. Questo tempo constante (per essere precisi, O(2)) rispetto a O(n) può essere trascurato. L'approccio è illustrato nell'immagine sottostante: copiamo semplicemente i dati dall'ultima colonna in quella da cui dobbiamo rimuovere i dati, e poi rimuoviamo l'ultima colonna:
    

In sintesi, in tutti gli scenari abbiamo ottenuto una complessità computazionale asintotica O(n).
Probabilmente avrai già notato che quasi sempre siamo costretti a leggere l'intera riga dal database, e in due casi su tre solo per scorrere tutte le colonne e contare il numero totale di amici. Pertanto, come tentativo di ottimizzazione, possiamo aggiungere una colonna «count» in cui memorizzare il numero totale di amici di ciascun utente nella rete. In questo modo possiamo evitare di leggere l'intera riga per contare il numero totale di amici, leggendo solo una colonna «count». La cosa principale è non dimenticare di aggiornare «count» durante le manipolazioni dei dati. Così otteniamo un miglioramento. Opzione 2 (count):

RowKey
Colonne

Vasya
1: Petya
2: Olya
3: Dasha
count: 3

Petya
1: Masha
2: Vasya

count: 2

Rispetto alla prima opzione:

• Lettura dei dati: per ottenere una risposta alla domanda «Legge Olya Vasya?» nulla è cambiato => O(n)
• Modifica dei dati: aggiunta di un amico: Abbiamo semplificato l'inserimento di un nuovo amico, poiché ora non dobbiamo più leggere l'intera riga e scorrere le sue colonne, ma possiamo ottenere solo il valore della colonna «count» e così determinare subito il numero della colonna per inserire un nuovo amico. Questo porta a una riduzione della complessità computazionale a O(1).
• Modifica dei dati: rimozione di un amico: Rimuovendo un amico, possiamo anche utilizzare questa colonna per ridurre il numero di operazioni di input/output durante lo “spostamento” dei dati di una cella a sinistra. Tuttavia, la necessità di scorrere le colonne per trovare quella da eliminare rimane, pertanto => O(n)
• D'altra parte, ora dobbiamo aggiornare ogni volta anche la colonna “count” quando aggiorniamo i dati, ma questo richiede tempo costante, che nel contesto della notazione O può essere trascurato.

In generale, la seconda opzione appare leggermente più ottimale, ma è più un'“evoluzione piuttosto che una rivoluzione”. Per effettuare una “rivoluzione” avremo bisogno di Opzione 3 (col).
Invertiamo tutto “sottosopra”: assegniamo come nome della colonna l'identificativo utente.! Ciò che verrà memorizzato nella colonna stessa non è per noi di particolare importanza, potrebbe essere il numero 1 (in realtà, potrebbe essere utile conservare, ad esempio, un gruppo come “famiglia/amici/ecc.”). Questo approccio potrebbe sorprendere un “cittadino” impreparato, che non ha mai avuto esperienza con database NoSQL, ma è proprio questo che consente di sfruttare il potenziale di HBase in modo molto più efficace per questo compito:

RowKey
Colonne

Vasya
Petr: 1
Olga: 1
Dasha: 1

Petya
Masha: 1
Vasya: 1

Qui otteniamo diversi vantaggi. Per comprenderli, analizziamo la nuova struttura e valutiamo la complessità computazionale:

• Lettura dei dati: per rispondere alla domanda se Vasya sia iscritto a Olya, basta leggere una colonna "Olya": se è presente, la risposta è True, altrimenti False => O(1)
• Modifica dei dati: aggiunta di un amico: Aggiungere un amico: è sufficiente aggiungere una nuova colonna "ID amico" => O(1)
• Modifica dei dati: rimozione di un amico: basta semplicemente eliminare la colonna "ID amico" => O(1)

Come vediamo, un vantaggio significativo di questo modello di archiviazione è che in tutti gli scenari necessari operiamo solo su un'unica colonna, evitando di leggere l'intera riga dal database e ancor di più, di esaminare tutte le colonne di quella riga. Si potrebbe fermarsi qui, ma...

Si può pensare di andare ancora un po' oltre nel percorso di ottimizzazione delle prestazioni e riduzione delle operazioni di I/O nell'accesso al database. E se memorizzassimo le informazioni complete sui legami direttamente nella chiave della riga? In altre parole, rendere la chiave composta del tipo userID.friendID? In questo caso, non avremmo nemmeno bisogno di leggere le colonne della riga (Opzione 4(row)):

RowKey
Colonne

Vasya.Petya
Petr: 1

Vasya.Olya
Olga: 1

Vasya.Dasha
Dasha: 1

Petya.Masha
Masha: 1

Petya.Vasya
Vasya: 1

È ovvio che la valutazione di tutti gli scenari di manipolazione dei dati in questa struttura sarà, come nel caso precedente, O(1). La differenza con la variante 3 riguarderà esclusivamente l'efficienza delle operazioni di input-output nel database.

E infine, l'ultimo 'fiocco'. È facile notare che nella variante 4 la chiave della stringa avrà una lunghezza variabile, il che potrebbe influenzare le prestazioni (qui ricordiamo che HBase memorizza i dati come un insieme di byte e che le stringhe nelle tabelle sono ordinate per chiave). Inoltre, abbiamo un delimitatore che potrebbe aver bisogno di essere gestito in alcuni scenari. Per escludere questo impatto, si possono utilizzare gli hash di userID e friendID; poiché entrambi gli hash avranno una lunghezza costante, sarà possibile concatenarli senza delimitatore. In tal modo, i dati nella tabella appariranno così:Variante 5(hash)):

RowKey
Colonne

dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Petr: 1

dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Olga: 1

dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Dasha: 1

1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Masha: 1

1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Vasya: 1

È chiaro che la complessità algoritmica di lavorare con una struttura come quella che stiamo considerando nei nostri scenari sarà la stessa rispetto all'opzione 4, ovvero O(1).
In sintesi, riassumiamo tutte le nostre stime sulla complessità computazionale in una tabella:

Aggiunta di un amico
Controllo di un amico
Rimozione di un amico

Opzione 1 (default)
O(n)
O(n)
O(n)

Opzione 2 (count)
O(1)
O(n)
O(n)

Opzione 3 (column)
O(1)
O(1)
O(1)

Opzione 4 (row)
O(1)
O(1)
O(1)

Opzione 5 (hash)
O(1)
O(1)
O(1)

Come si può vedere, le opzioni 3-5 sembrano le più preferibili e teoricamente garantiscono l'esecuzione di tutti gli scenari necessari di manipolazione dei dati in tempo costante. Nella condizione del nostro compito non c'è un'esplicita richiesta di ottenere un elenco di tutti gli amici dell'utente, ma nel lavoro progettuale reale, come buoni analisti, sarebbe utile "prevedere" che una tale richiesta potrebbe sorgere e "mettere in sicurezza" le cose. Pertanto, ho una preferenza per l'opzione 3. Tuttavia, è molto probabile che nel progetto reale questa richiesta possa essere già stata risolta con altri mezzi, quindi senza una visione d'insieme di tutto il compito, è meglio non trarre conclusioni definitive.

Preparazione dell'esperimento

Le considerazioni teoriche sopra citate vorremmo testarle nella pratica – questo è stato l'obiettivo dell'idea nata nel lungo week-end. Per fare ciò, è necessario valutare la velocità di esecuzione della nostra "applicazione ipotetica" in tutti gli scenari di utilizzo descritti, così come l'aumento di questo tempo con l'aumento delle dimensioni della rete sociale (n). Il parametro target che ci interessa e che misureremo durante l'esperimento è il tempo impiegato dall'"applicazione ipotetica" per completare una "operazione commerciale". Con "operazione commerciale" intendiamo una delle seguenti:

• Aggiunta di un nuovo amico
• Verifica se l'utente A è amico dell'utente B
• Rimozione di un amico

Pertanto, tenendo conto dei requisiti delineati nella formulazione iniziale, lo scenario di verifica si delinea come segue:

• Registrazione dei dati. Generare in modo casuale una rete di dimensioni n. Per avvicinarsi maggiormente al "mondo reale", il numero di amici di ciascun utente è anch'esso una variabile casuale. Misurare il tempo necessario affinché la nostra "applicazione fittizia" registri in HBase tutti i dati generati. Poi dividere il tempo ottenuto per il numero totale di amici aggiunti, così otteniamo il tempo medio per una "operazione commerciale".
• Lettura dei dati. Per ogni utente, redigere un elenco di "identità" per le quali è necessario ottenere una risposta, se l'utente è o meno un loro seguace. La lunghezza dell'elenco sarà pari a circa il numero di amici dell'utente, con la metà degli amici controllati che deve dare risposta "Sì" e l'altra metà "No". La verifica deve avvenire in modo tale che le risposte "Sì" e "No" si alternino (cioè nel secondo caso dovremo esaminare tutte le colonne della riga per le opzioni 1 e 2). Il tempo totale della verifica deve poi essere diviso per il numero di amici controllati per ottenere il tempo medio per verificare un soggetto.
• Eliminazione dei dati. Rimuovere tutti gli amici dell'utente. Inoltre, l'ordine di rimozione è casuale (ovvero, mescoliamo l'elenco originale utilizzato per la registrazione dei dati). Il tempo totale di controllo deve quindi essere diviso per il numero di amici rimossi per ottenere il tempo medio per ogni controllo.

I test devono essere eseguiti per ciascuna delle 5 varianti dei modelli di dati e per diverse dimensioni della rete sociale, per osservare come cambia il tempo con la sua crescita. All'interno di una connessione n nella rete, l'elenco degli utenti da controllare deve essere, naturalmente, identico per tutte e 5 le varianti.
Per una migliore comprensione, riporto di seguito un esempio di dati generati per n= 5. Il 'generatore' fornito restituisce in uscita tre dizionari di ID:

• primo – per l'inserimento
• secondo – per il controllo
• terzo – per la rimozione

{0: [1], 1: [4, 5, 3, 2, 1], 2: [1, 2], 3: [2, 4, 1, 5, 3], 4: [2, 1]} # totale 15 amici

{0: [1, 10800], 1: [5, 10800, 2, 10801, 4, 10802], 2: [1, 10800], 3: [3, 10800, 1, 10801, 5, 10802], 4: [2, 10800]} # totale 18 soggetti controllati

{0: [1], 1: [1, 3, 2, 5, 4], 2: [1, 2], 3: [4, 1, 2, 3, 5], 4: [1, 2]} # totale 15 amici

Come si può notare, tutti gli ID superiori a 10.000 nel dizionario per il controllo sono precisamente quelli che sicuramente daranno una risposta False. L'inserimento, la verifica e la rimozione dei “friend” avvengono proprio nell'ordine specificato nel dizionario.

L'esperimento è stato condotto su un laptop con Windows 10, dove in un container Docker era in esecuzione un database HBase e in un altro – Python con Jupyter Notebook. Al Docker sono stati assegnati 2 core CPU e 2 GB di RAM. Tutta la logica, sia l'emulazione del funzionamento dell'“applicazione condizionale” che il “wrapper” per la generazione di dati di test e la misurazione del tempo, è stata scritta in Python. Per interagire con HBase è stata utilizzata la libreria happybase, per calcolare gli hash (MD5) per la variante 5 – hashlib.

Considerando la potenza di calcolo del laptop specifico, è stata scelta sperimentalmente l'esecuzione per n = 10, 30, …. 170 – quando il tempo totale di esecuzione dell'intero ciclo di test (tutti gli scenari per tutte le varianti per tutti gli n) era ancora più o meno ragionevole e rientrava nel tempo di un tè (in media 15 minuti).

È importante notare che in questo esperimento stiamo valutando principalmente non i numeri assoluti delle performance. Anche il confronto relativo tra due diverse opzioni potrebbe non essere del tutto corretto. Attualmente, ci interessa soprattutto il modo in cui il tempo varia in base a n, poiché, considerando la configurazione del "banco di test" sopra menzionata, è molto difficile ottenere valutazioni temporali "pulite" dall'influenza di fattori casuali e altri elementi (e tale obiettivo non era stato nemmeno formulato).

Risultato dell'esperimento

Il primo test – come cambia il tempo impiegato per compilare l'elenco degli amici. Risultato – nel grafico sottostante.

Le varianti 3-5 mostrano, come previsto, praticamente un tempo costante per l'"operazione commerciale", che non dipende dalla crescita della rete e una differenza di prestazioni indistinguibile.
L'opzione 2 mostra anch'essa prestazioni costanti, ma leggermente inferiori, contribuendo a un aumento quasi esattamente del doppio rispetto alle opzioni 3-5. Questo è un aspetto positivo, poiché si allinea alla teoria: in questa opzione, il numero di operazioni di input/output in/da HBase è infatti il doppio. Ciò può essere un'indicazione indiretta che il nostro banco di prova fornisce in generale una precisione soddisfacente.
L'opzione 1 si rivela come previsto la più lenta, mostrando un incremento lineare del tempo impiegato per aggiungere un elemento in relazione alla dimensione della rete.
Esaminiamo ora i risultati del secondo test.

Le opzioni 3-5 continuano a comportarsi come previsto: tempo costante, indipendente dalle dimensioni della rete. Le opzioni 1 e 2 mostrano una crescita lineare del tempo all'aumentare delle dimensioni della rete e una prestazione simile. L'opzione 2 risulta leggermente più lenta, probabilmente a causa della necessità di leggere e elaborare una colonna aggiuntiva "count", che diventa più evidente con l'aumento di n. Tuttavia, mi asterrò dal trarre conclusioni, poiché la precisione di questo confronto è relativamente bassa. Inoltre, i rapporti (quale opzione, 1 o 2, sia più veloce) sono cambiati da esecuzione a esecuzione (pur mantenendo la caratteristica di dipendenza e "andando di pari passo").

E infine, l'ultimo grafico: il risultato del test di eliminazione.

Qui, di nuovo, nessuna sorpresa. Le opzioni 3-5 eseguono l'eliminazione in tempo costante.
E ciò che è interessante è che le opzioni 4 e 5, a differenza degli scenari precedenti, mostrano prestazioni leggermente inferiori rispetto all'opzione 3. A quanto pare, l'operazione di eliminazione di una riga è più dispendiosa rispetto all'operazione di eliminazione di una colonna, il che ha senso.

Le opzioni 1 e 2 mostrano un aumento lineare del tempo come previsto. Tuttavia, l'opzione 2 è costantemente più lenta dell'opzione 1, a causa dell'operazione di input/output aggiuntiva per la "gestione" della colonna count.

Conclusioni generali dell'esperimento:

• Le opzioni 3-5 dimostrano un'efficacia maggiore, in quanto sfruttano i vantaggi di HBase; la loro performance differisce tra di loro di una costante e non dipende dalla dimensione della rete.
• La differenza tra le opzioni 4 e 5 non è stata registrata. Ciò non significa che l'opzione 5 non debba essere utilizzata. È del tutto possibile che lo scenario sperimentale, tenendo conto delle specifiche tecniche del banco di prova, non l'abbia potuta rilevare.
• La natura della crescita del tempo necessario per eseguire "operazioni di business" con i dati ha complessivamente confermato le conclusioni teoriche precedentemente ottenute per tutte le opzioni.

Epilogo

Gli esperimenti grezzi condotti non dovrebbero essere considerati come verità assoluta. Esistono molteplici fattori che non sono stati presi in considerazione e che hanno introdotto distorsioni nei risultati (queste fluttuazioni sono particolarmente visibili nei grafici quando le dimensioni della rete sono ridotte). Ad esempio, la velocità di funzionamento di Thrift, utilizzata da HappyBase, il volume e il modo in cui è stata implementata la logica che ho scritto in Python (non posso affermare che il codice sia stato scritto in modo ottimale e sfrutti efficacemente tutte le componenti), forse le caratteristiche di caching di HBase, l'attività di background di Windows 10 sul mio laptop, e così via. In generale, si può considerare che tutte le deduzioni teoriche abbiano dimostrato la loro validità. O almeno, non è stato possibile confutarle con un approccio così diretto.

In conclusione, ecco alcuni consigli per chi inizia a progettare modelli di dati in HBase: astrarsi dall'esperienza precedente con i database relazionali e ricordare i "comandamenti":

• Progettando, partiamo dal compito e dai modelli di manipolazione dei dati, anziché dal modello del dominio applicativo.
• Accesso efficace (senza full table scan) – solo tramite chiave.
• Denormalizzazione
• Le righe diverse possono contenere colonne diverse
• Composizione dinamica delle colonne

Fonte: habr.com