Caratteristiche progettuali del modello di dati per NoSQL

Introduzione

«Bisogna correre a perdifiato per restare fermi,
e per arrivare da qualche parte, bisogna correre almeno il doppio più veloce!»
(c) Alice nel Paese delle Meraviglie

Qualche tempo fa mi è stato chiesto di tenere una lezione agli analisti della nostra azienda sul tema della progettazione di modelli di dati, poiché sedendo a lungo su progetti (a volte per diversi anni) perdiamo di vista ciò che accade nel mondo delle tecnologie IT. Nella nostra azienda (così è andata) non vengono utilizzate nei molti progetti basi di dati NoSQL (almeno per ora), quindi nella mia lezione ho dedicato particolare attenzione a esse, utilizzando HBase come esempio, e ho cercato di orientare il materiale su coloro che non hanno mai lavorato con esse. In particolare, ho illustrato alcuni aspetti della progettazione del modello di dati prendendo spunto da un esempio che ho letto alcuni anni fa nell'articolo «Introduction to HBase Schema Design» di Amandeep Khurana. Analizzando gli esempi, ho confrontato tra loro diverse soluzioni per lo stesso problema, per comunicare meglio le idee principali agli ascoltatori.

Recentemente, «per noia», mi sono posto la domanda (i lunghi fine settimana di maggio in modalità quarantena sono particolarmente adatti a questo), quanto le teorie si allineano con la pratica? In effetti, è così che è nata l'idea di questo articolo. Uno sviluppatore che lavora da un po' con NoSQL potrebbe non trovare nulla di nuovo (e quindi potrebbe decidere di saltare metà articolo). Ma per gli analisti, che non hanno ancora lavorato a stretto contatto con NoSQL, penso possa essere utile per avere una comprensione di base delle caratteristiche della progettazione di modelli di dati per HBase.

Analisi dell'esempio

A mio avviso, prima di iniziare a utilizzare database NoSQL, è necessario riflettere bene e pesare i "pro" e i "contro". Spesso la questione può essere risolta anche con database relazionali tradizionali. Pertanto, è meglio non utilizzare NoSQL senza motivazioni valide. Se si decide comunque di utilizzare un database NoSQL, bisogna tenere presente che gli approcci alla progettazione qui differiscono leggermente. In particolare, alcuni di essi possono risultare insoliti per coloro che in precedenza hanno trattato solo con database relazionali (secondo le mie osservazioni). Così, nel mondo "relazionale" noi di solito partiamo dalla modellazione del dominio, per poi eseguire la denormalizzazione del modello se necessario. Con NoSQL, però, noi dobbiamo immediatamente considerare i possibili scenari di utilizzo dei dati e denormalizzare i dati sin dall'inizio. Inoltre, ci sono diverse altre differenze, di cui si parlerà più avanti.

Esaminiamo il seguente compito "sintetico", con il quale lavoreremo in seguito:

È necessario progettare la struttura di archiviazione dell'elenco degli amici degli utenti di un'ipotetica rete sociale astratta. Per semplificare, supporremo che tutte le relazioni siano direzionali (come in Instagram, e non in Linkedin). La struttura deve consentire di:

• Rispondere alla domanda se l'utente A stia seguendo l'utente B (modello di lettura)
• Consentire di aggiungere/rimuovere relazioni nel caso di iscrizione/disiscrizione dell'utente A dall'utente B (modello di modifica dei dati)

Naturalmente, ci sono molte soluzioni a questo problema. In un normale database relazionale probabilmente avremmo semplicemente creato una tabella delle relazioni (possibilmente tipizzata, se ad esempio è necessario archiviare un gruppo di utenti: famiglia, lavoro, ecc., che include questo "amico"), e per ottimizzare la velocità di accesso avremmo aggiunto indici/partizionamento. Probabilmente la tabella finale sarebbe apparsa più o meno così:

user_id
friend_id

Vasya
Petya

Vasya
Olya

qui e oltre, per chiarezza e migliore comprensione, userò nomi anziché ID

Nel caso di HBase, sappiamo che:

• una ricerca efficace che non porta a una scansione completa della tabella è possibile esclusivamente per chiave
  • In effetti, è per questo che scrivere normali query SQL per questi tipi di database è una cattiva idea; tecnicamente, certo, puoi inviare una query SQL con join e altra logica in HBase da Impala, ma quanto sarà efficace...

Pertanto, siamo costretti a utilizzare l'ID utente come chiave. E la prima idea su "dove e come memorizzare gli ID degli amici?" può essere quella di memorizzarli in colonne. Questa opzione è la più ovvia e "naïve" e apparirà più o meno così (chiamiamola Opzione 1 (default), per riferirci in seguito):

RowKey
Colonne

Vasya
1: Petya
2: Olya
3: Dasha

Petya
1: Masha
2: Vasya

Qui, ogni riga corrisponde a un utente della rete. Le colonne hanno nomi: 1, 2, … — a seconda del numero di amici, e all'interno delle colonne sono memorizzati gli ID degli amici. È importante notare che ogni riga avrà un numero diverso di colonne. Nell'esempio nell'immagine sopra, una riga ha tre colonne (1, 2 e 3), mentre la seconda ne ha solo due (1 e 2) – qui abbiamo sfruttato due proprietà di HBase che non hanno i database relazionali:

• la capacità di cambiare dinamicamente la composizione delle colonne (aggiungiamo un amico -> aggiungiamo una colonna, rimuoviamo un amico -> rimuoviamo una colonna)
• riga diverse possono avere composizioni diverse delle colonne

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 chiave RowKey = «Vasya» e scorrere i valori delle colonne finché non “incontriamo” Olya. Oppure, possiamo scorrere i valori di tutte le colonne, “non incontrare” Olya e restituire la risposta False;
• Modifica dei dati: aggiunta di un amico: per un compito simile, dovremo anche leggere l'intera riga con chiave RowKey = «Vasya», per contare il numero totale dei suoi amici. Questo numero totale di amici è necessario per determinare il numero di colonna in cui scrivere l'ID del nuovo amico.
• Modifica dei dati: rimozione di un amico:
  • È necessario leggere l'intera riga con chiave RowKey = «Vasya» e scorrere le colonne per trovare quella in cui è registrato l'amico da rimuovere;
  • Dopo aver rimosso l'amico, dobbiamo “spostare” tutti i dati di una colonna per evitare di avere “buchi” nella loro numerazione.

Ora valutiamo quanto siano efficienti gli algoritmi che dovremo implementare sul lato dell'“applicazione condizionale” usando O-simbolismo. Indichiamo la dimensione della nostra ipotetica rete sociale come n. Quindi, il numero massimo di amici per un utente può essere (n-1). Possiamo trascurare questo (-1) per i nostri scopi, poiché nell'ambito dell'uso della notazione O, è insignificante.

• Lettura dei dati: è necessario estrarre l'intera riga e analizzare tutte le sue colonne nel limite. Quindi, la stima superiore dei costi sarà circa O(n)
• Modifica dei dati: aggiunta di un amico: per determinare il numero di amici, è necessario analizzare tutte le colonne della riga e poi inserire una nuova colonna => O(n)
• Modifica dei dati: rimozione di un amico:
  • Analogamente all'aggiunta – è necessario esaminare tutte le colonne nel limite => O(n)
  • Dopo la rimozione delle colonne, dobbiamo «spostarle». Se implementiamo questo «in modo diretto», ci vorranno nel limite fino a (n-1) operazioni. Tuttavia, qui e in seguito nella parte pratica utilizzeremo un approccio diverso che realizzerà uno «spostamento pseudo» in un numero fisso di operazioni, ovvero richiederà un tempo costante indipendentemente da n. Questo tempo costante (per essere precisi, O(2)) rispetto a O(n) può essere trascurato. L'approccio è illustrato nell'immagine qui sotto: copiamo semplicemente i dati dall'«ultima» colonna in quella da cui dobbiamo rimuovere i dati, dopo di che eliminiamo l'ultima colonna:
    

In sintesi, in tutti gli scenari abbiamo ottenuto una complessità computazionale asintotica O(n).
Probabilmente hai già notato che dobbiamo quasi sempre estrarre l'intera riga dal database, e infatti in due casi su tre solo per analizzare 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 della rete. In questo caso possiamo evitare di estrarre l'intera riga per contare il numero totale di amici, ma leggere solo una colonna «count». È importante non dimenticare di aggiornare il «count» durante le operazioni con i 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 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 semplicemente ottenere il valore della colonna «count» e quindi determinare immediatamente il numero della colonna per inserire il nuovo amico. Questo porta a una riduzione della complessità computazionale a O(1)
• Modifica dei dati: rimozione di un amico: Quando rimuoviamo un amico, possiamo anche utilizzare questa colonna per ridurre il numero di operazioni di input-output durante il «trasloco» dei dati di una cella verso sinistra. Tuttavia, la necessità di scorrere le colonne per trovare quella da rimuovere rimane, quindi => O(n)
• D'altra parte, ora quando aggiorniamo i dati dobbiamo aggiornare ogni volta anche la colonna «count», ma questo richiede un tempo costante, che nell'ambito della notazione O può essere trascurato

Nel complesso, l'opzione 2 appare leggermente più ottimale, ma è più un'«evoluzione» che una «rivoluzione». Per compiere una «rivoluzione» avremo bisogno di Opzione 3 (col).
Rivoltiamo tutto «a testa in giù»: assegniamo il nome della colonna come identificatore dell'utente! Ciò che verrà registrato nella colonna stessa non ci importa, che sia il numero 1 (in generale, da lì si possono conservare informazioni utili, come un gruppo «famiglia/amici/ecc.»). Questo approccio potrebbe sorprendere un «cittadino comune» non preparato, che non aveva precedentemente esperienza con basi di dati NoSQL, ma è proprio questo che permette di sfruttare il potenziale di HBase in questa attività in modo molto più efficiente:

RowKey
Colonne

Vasya
Petya: 1
Olya: 1
Dasha: 1

Petya
Masha: 1
Vasya: 1

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

• Lettura dei dati: per rispondere alla domanda se Vasya è iscritto a Olya, è sufficiente leggere una colonna «Olya»: se esiste, la risposta è True, se non c'è – False => O(1)
• Modifica dei dati: aggiunta di un amico: Aggiunta di un amico: basta aggiungere una nuova colonna «ID amico» => O(1)
• Modifica dei dati: rimozione di un amico: basta semplicemente rimuovere la colonna «ID amico» => O(1)

Come vediamo, un notevole vantaggio di questo modello di archiviazione è che in tutti gli scenari di cui abbiamo bisogno operiamo solo su una colonna, evitando di leggere l'intera riga dal database e, tanto meno, di scorrere tutte le colonne di quella riga. A questo punto potremmo fermarci, ma…

Si può considerare anche di andare un po' oltre nel percorso di ottimizzazione delle prestazioni e riduzione delle operazioni di input/output quando si accede al database. E se si memorizzasse l'informazione completa sulla relazione direttamente nella chiave della riga? Cioè, si potrebbe fare una chiave composita del tipo userID.friendID? In questo caso, potremmo non dover nemmeno leggere le colonne della riga (Opzione 4 (row)):

RowKey
Colonne

Vasia.Petja
Petya: 1

Vasia.Olja
Olya: 1

Vasia.Dasha
Dasha: 1

Petja.Masha
Masha: 1

Petja.Vasia
Vasya: 1

È ovvio che la valutazione di tutti gli scenari di manipolazione dei dati in questa struttura sarà, proprio come nell'opzione precedente, O(1). La differenza con l'opzione 3 sarà esclusivamente nell'efficienza delle operazioni di input/output nel DB.

E infine l'ultimo "nastro". È facile notare che nell'opzione 4 la chiave della riga avrà una lunghezza variabile, il che potrebbe influire sulle prestazioni (ricordiamo che HBase memorizza i dati come un insieme di byte e le righe nelle tabelle sono ordinate per chiave). Inoltre, abbiamo un separatore che in alcuni scenari potrebbe richiedere di essere gestito. Per escludere questa influenza, si possono utilizzare gli hash di userID e friendID, e poiché entrambi gli hash avranno una lunghezza costante, possono essere semplicemente concatenati senza separatore. Allora, i dati nella tabella appariranno così (Opzione 5 (hash)):

RowKey
Colonne

dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Petya: 1

dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Olya: 1

dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Dasha: 1

1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Masha: 1

1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Vasya: 1

È ovvio che la complessità algoritmica del lavoro con questa struttura nei scenari considerati sarà la stessa dell'opzione 4: cioè O(1).
In conclusione, riassumiamo tutte le nostre valutazioni della complessità computazionale in una tabella:

Aggiunta di un amico
Verifica 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ò notare, le opzioni 3-5 sembrano essere le più preferibili e teoricamente garantiscono l'esecuzione di tutti gli scenari necessari di manipolazione dei dati in tempo costante. Nell'ambito della nostra attività non c'è un chiaro requisito per ottenere un elenco di tutti gli amici dell'utente, ma nella pratica progettuale reale, come buoni analisti, sarebbe utile 'prevedere' che un compito simile potrebbe sorgere e 'prepararsi'. Pertanto, sono favorevole all'opzione 3. Tuttavia, è probabile che in un progetto reale tale richiesta sia già stata risolta con altri mezzi, quindi senza una visione complessiva dell'intero compito, è meglio non trarre conclusioni definitive.

Preparazione dell'esperimento

Le riflessioni teoriche sopra esposte vorremmo metterle alla prova in pratica - questo è stato l'obiettivo dell'idea nata durante un lungo fine settimana. Per fare ciò, è necessario valutare la velocità del nostro 'applicativo ipotetico' in tutti gli scenari di utilizzo descritti del database, nonché la crescita di questo tempo all'aumentare delle dimensioni della rete sociale (n). Il parametro di interesse, che misureremo durante l'esperimento, è il tempo impiegato dal 'applicativo ipotetico' per eseguire una 'operazione aziendale'. Con 'operazione aziendale' 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 espressi nell'incarico originale, lo scenario di verifica si delineano come segue:

• Scrittura dei dati. Generare casualmente una rete iniziale di dimensione n. Per un maggior avvicinamento al 'mondo reale', il numero di amici di ciascun utente è anche una variabile casuale. Misurare il tempo impiegato dal nostro 'applicativo ipotetico' per scrivere in HBase tutti i dati generati. Successivamente, dividere il tempo ottenuto per il numero totale di amici aggiunti - in questo modo otterremo il tempo medio per una 'operazione aziendale'.
• Lettura dei dati. Per ogni utente, creare un elenco di "identità" per le quali controllare se l'utente è collegato o meno. La lunghezza dell'elenco è circa pari al numero di amici dell'utente, dove per metà degli amici controllati la risposta deve essere "Sì", e per l'altra metà - "No". Il controllo avviene in un modo tale che le risposte "Sì" e "No" si alternano (ovvero in ogni secondo caso dovremo esaminare tutte le colonne della riga per le varianti 1 e 2). Il tempo totale di controllo sarà poi diviso per il numero di amici controllati per ottenere il tempo medio di verifica di un soggetto.
• Rimozione dei dati. Rimuovere tutti gli amici dall'utente. L'ordine di rimozione deve essere casuale (cioè "mescolare" l'elenco originale utilizzato per registrare i dati). Il tempo totale di controllo sarà poi diviso per il numero di amici rimossi per ottenere il tempo medio per un controllo.

Gli scenari devono essere eseguiti per ognuno dei 5 modelli di dati e per diverse dimensioni del social network, 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 lo stesso per tutte le 5 varianti.
Per una migliore comprensione, di seguito fornisco un esempio di dati generati per n= 5. Il "generatore" scritto 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]} # complessivamente 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]} # complessivamente 18 soggetti controllati

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

Come si può notare, tutti gli ID superiori a 10.000 nel dizionario per il controllo sono proprio quelli che daranno sicuramente una risposta Falsa. L'inserimento, il controllo e la rimozione degli "amici" avvengono proprio nell'ordine indicato nel dizionario.

L'esperimento è stato condotto su un laptop con Windows 10, in cui in un contenitore Docker era in esecuzione un database HBase, mentre nell'altro un'istanza di Python con Jupyter Notebook. Sono stati assegnati a Docker 2 core CPU e 2 GB di RAM. Tutta la logica, sia per l'emulazione del funzionamento dell'"applicazione condizionale" sia per il "wrapper" per la generazione di dati di prova e la misurazione del tempo, è stata scritta in Python. Per lavorare con HBase è stata utilizzata la libreria happybase, per il calcolo degli hash (MD5) per l'opzione 5 — hashlib

Tenendo conto della potenza di calcolo del laptop specifico, è stata sperimentalmente scelta l'esecuzione per n = 10, 30, … 170 – quando il tempo totale di esecuzione dell'intero ciclo di test (tutti gli scenari per tutte le opzioni per tutti gli n) era ancora più o meno ragionevole e si adattava al tempo di una degustazione di tè (in media 15 minuti).

Qui è necessario fare una precisazione, in questo esperimento non stiamo valutando principalmente i numeri assoluti delle prestazioni. Anche il confronto relativo di due diverse opzioni può non essere del tutto corretto. Ci interessa in particolare il modo in cui cambia il tempo in base a n, poiché tenendo conto della configurazione sopra indicata del "banco di prova", ottenere stime temporali "pulite" dall'influenza di fattori casuali e altri è molto difficile (e non era questo l'obiettivo).

Risultato dell'esperimento

Il primo test – come varia il tempo impiegato per riempire la lista degli amici. Risultato – nel grafico qui sotto.

Le opzioni 3-5 mostrano ovviamente un tempo praticamente costante per l'"operazione commerciale", che non dipende dall'aumento della dimensione della rete e una differenza di prestazioni indistinguibile.
L'opzione 2 mostra prestazioni anch'esse costanti, ma leggermente inferiori, praticamente esattamente 2 volte rispetto alle opzioni 3-5. Questo non può non essere positivo, dato che si allinea con la teoria – in questa opzione il numero di operazioni di input-output in/da HBase è esattamente il doppio. Questo può servire come prova indiretta che il nostro banco di prova fornisce in linea di principio una buona precisione.
L'opzione 1 si dimostra anch'essa prevedibilmente la più lenta e dimostra una crescita lineare del tempo impiegato per aggiungere un amico in base alla dimensione della rete.
Vediamo ora i risultati del secondo test.

Le opzioni 3-5 si comportano di nuovo come previsto: tempo costante, indipendente dalla dimensione della rete. Le opzioni 1 e 2 mostrano una crescita lineare del tempo con l'aumento della dimensione della rete e prestazioni simili. Tuttavia, l'opzione 2 risulta essere leggermente più lenta, probabilmente a causa della necessità di leggere e trattare la colonna aggiuntiva "count", che diventa più evidente all'aumentare di n. Tuttavia, mi asterrò da qualsiasi conclusione, poiché l'accuratezza di questo confronto è relativamente bassa. Inoltre, queste relazioni (quale opzione, 1 o 2, è più veloce) cambiavano da esecuzione a esecuzione (pur mantenendo il carattere della dipendenza e "andando spalla a spalla").

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

Qui non ci sono sorprese. Le opzioni 3-5 eseguono l'eliminazione in tempo costante.
Peraltro, ciò che è interessante è che le opzioni 4 e 5, a differenza degli scenari precedenti, mostrano una prestazione leggermente peggiore rispetto all'opzione 3. Evidentemente, l'operazione di eliminazione di una riga è più costosa rispetto all'operazione di eliminazione di una colonna, il che è logico.

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

Conclusioni generali dell'esperimento:

• Le opzioni 3-5 mostrano una maggiore efficienza, poiché sfruttano i vantaggi di HBase; inoltre, la loro prestazione differisce l'una dall'altra di una costante e non dipende dalla dimensione della rete.
• La differenza tra le opzioni 4 e 5 non è stata registrata. Ma questo non significa che l'opzione 5 non debba essere utilizzata. È probabile che lo scenario sperimentale utilizzato, tenendo conto delle specifiche del banco di prova, non abbia permesso di evidenziarla.
• Il carattere della crescita del tempo necessario per eseguire le "operazioni commerciali" con i dati ha confermato in generale le teorie precedenti esposte per tutte le opzioni.

Epilogo

Gli esperimenti grezzi condotti non dovrebbero essere considerati come una verità assoluta. Ci sono molteplici fattori che non sono stati presi in considerazione e hanno alterato i risultati (soprattutto queste fluttuazioni sono ben visibili nei grafici con una piccola dimensione di rete). Ad esempio, la velocità di funzionamento di thrift, che viene utilizzato da happybase, la quantità e il modo in cui è stata implementata la logica, che avevo scritta in Python (non affermo che il codice fosse scritto in modo ottimale e utilizzasse efficacemente le capacità di tutti i componenti), forse le caratteristiche di caching di HBase, l'attività in background di Windows 10 sul mio laptop, ecc. In generale, si può considerare che tutte le deduzioni teoriche abbiano dimostrato sperimentalmente la loro validità. O almeno, dimostrare il contrario con un attacco frontale di questo tipo non è riuscito.

In conclusione — raccomandazioni a tutti coloro che iniziano a progettare modelli di dati in HBase: astrarsi dall'esperienza precedente con i database relazionali e tenere a mente i "comandamenti":

• Nella progettazione, partiamo dal compito e dai modelli di manipolazione dei dati, e non dal modello del dominio
• Accesso efficace (senza full table scan) - solo per chiave
• Denormalizzazione
• Righe diverse possono contenere colonne diverse
• Composizione delle colonne dinamica

Fonte: habr.com