Funzionalità di progettazione di un modello di dati per NoSQL

Introduzione

"Devi correre più veloce che puoi solo per rimanere sul posto,
e per arrivare da qualche parte devi correre almeno il doppio più veloce!”
(c) Alice nel Paese delle Meraviglie

Qualche tempo fa mi è stato chiesto di tenere una conferenza analisti la nostra azienda sul tema della progettazione di modelli di dati, perché sedendo su progetti per molto tempo (a volte per diversi anni) perdiamo di vista ciò che sta accadendo intorno a noi nel mondo delle tecnologie IT. Nella nostra azienda (si dà il caso) molti progetti non utilizzano database NoSQL (almeno per ora), quindi nella mia lezione ho prestato loro attenzione separatamente utilizzando l'esempio di HBase e ho cercato di orientare la presentazione del materiale a quelli chi non li ha mai usati ha funzionato. In particolare, ho illustrato alcune caratteristiche della progettazione del modello dati utilizzando un esempio letto diversi anni fa nell'articolo “Introduzione a HB ase Schema Design” di Amandeep Khurana. Analizzando gli esempi, ho confrontato diverse opzioni per risolvere lo stesso problema al fine di trasmettere meglio le idee principali al pubblico.

Di recente, “per niente da fare”, mi sono posto la domanda (il lungo fine settimana di maggio in quarantena è particolarmente favorevole a questo): quanto i calcoli teorici corrisponderanno alla pratica? In realtà è così che è nata l’idea di questo articolo. Uno sviluppatore che lavora con NoSQL da diversi giorni potrebbe non imparare nulla di nuovo da esso (e quindi saltare immediatamente metà dell'articolo). Ma per analistiPer coloro che non hanno ancora lavorato a stretto contatto con NoSQL, penso che sarà utile per acquisire una conoscenza di base delle funzionalità di progettazione di modelli di dati per HBase.

Analisi di esempio

Secondo me, prima di iniziare a utilizzare i database NoSQL, è necessario riflettere attentamente e valutare i pro e i contro. Spesso il problema può essere risolto molto probabilmente utilizzando i tradizionali DBMS relazionali. Pertanto è meglio non utilizzare NoSQL senza ragioni significative. Se tuttavia decidi di utilizzare un database NoSQL, dovresti tenere conto del fatto che gli approcci progettuali qui sono leggermente diversi. Soprattutto alcuni di essi potrebbero essere insoliti per coloro che in precedenza si sono occupati solo di DBMS relazionali (secondo le mie osservazioni). Quindi, nel mondo “relazionale”, di solito iniziamo modellando il dominio del problema e solo poi, se necessario, denormalizziamo il modello. In NoSQL noi dovrebbe immediatamente tenere conto degli scenari previsti per lavorare con i dati e inizialmente denormalizzare i dati. Inoltre, ci sono una serie di altre differenze, che verranno discusse di seguito.

Consideriamo il seguente problema “sintetico”, sul quale continueremo a lavorare:

È necessario progettare una struttura di archiviazione per l'elenco degli amici degli utenti di qualche social network astratto. Per semplificare, assumeremo che tutte le nostre connessioni siano dirette (come su Instagram, non su Linkedin). La struttura dovrebbe consentire di:

• Rispondi alla domanda se l'utente A legge l'utente B (modello di lettura)
• Consenti aggiunta/rimozione connessioni in caso di iscrizione/cancellazione dell'utente A dall'utente B (modello di modifica dati)

Naturalmente, ci sono molte opzioni per risolvere il problema. In un normale database relazionale, molto probabilmente faremo semplicemente una tabella di relazioni (eventualmente tipizzata se, ad esempio, dobbiamo memorizzare un gruppo di utenti: famiglia, lavoro, ecc., che include questo "amico"), e ottimizzare la velocità di accesso aggiungerebbe indici/partizionamento. Molto probabilmente il tavolo finale sarebbe simile a questo:

user_id
amico_id

Vasya
Петя

Vasya
Olya

di seguito, per chiarezza e migliore comprensione, indicherò i nomi al posto degli ID

Nel caso di HBase, sappiamo che:

• è possibile una ricerca efficiente che non dia luogo ad una scansione completa della tabella esclusivamente tramite chiave
  • infatti, è per questo che scrivere query SQL familiari a molti su tali database è una cattiva idea; tecnicamente, ovviamente, puoi inviare una query SQL con join e altra logica a HBase dallo stesso Impala, ma quanto sarà efficace...

Pertanto, siamo costretti a utilizzare l'ID utente come chiave. E il mio primo pensiero sull’argomento “dove e come archiviare gli ID degli amici?” forse un'idea per memorizzarli in colonne. Questa opzione più ovvia e “ingenua” sarà simile a questa (chiamiamola Opzione 1 (predefinita)per ulteriori riferimenti):

RowKey
altoparlanti

Vasya
1: Petya
2: Olja
3: Dasha

Петя
1: Maša
2: Vasia

Qui ogni riga corrisponde a un utente della rete. Le colonne hanno nomi: 1, 2, ... - in base al numero di amici e gli ID degli amici sono memorizzati nelle colonne. È importante notare che ogni riga avrà un numero diverso di colonne. Nell'esempio della figura sopra, una riga ha tre colonne (1, 2 e 3) e la seconda ne ha solo due (1 e 2): qui noi stessi abbiamo utilizzato due proprietà HBase che i database relazionali non hanno:

• la possibilità di modificare dinamicamente la composizione delle colonne (aggiungi un amico -> aggiungi una colonna, rimuovi un amico -> elimina una colonna)
• righe diverse possono avere composizioni di colonne diverse

Controlliamo la nostra struttura per verificare la conformità ai requisiti dell'attività:

• Lettura dei dati: per capire se Vasya è iscritto a Olya, dovremo sottrarre tutta la linea con la chiave RowKey = “Vasya” e ordina i valori delle colonne finché non “incontriamo” Olya in essi. Oppure scorrere i valori di tutte le colonne, "non soddisfare" Olya e restituire la risposta False;
• Modifica dei dati: aggiunta di un amico: per un compito simile dobbiamo anche sottrarre tutta la linea usando la chiave RowKey = “Vasya” per contare il numero totale dei suoi amici. Questo numero totale di amici ci serve per determinare il numero della colonna in cui dobbiamo annotare l'ID del nuovo amico.
• Modifica dati: eliminazione di un amico:
  • È necessario sottrarre tutta la linea con la chiave RowKey = “Vasya” e scorrere le colonne per trovare quella in cui è registrato l'amico da eliminare;
  • Successivamente, dopo aver eliminato un amico, dobbiamo "spostare" tutti i dati in una colonna in modo da non avere "lacune" nella loro numerazione.

Valutiamo ora quanto saranno produttivi questi algoritmi, che dovremo implementare lato “applicazione condizionale”, utilizzando Simbolismo della O. Indichiamo la dimensione del nostro ipotetico social network con n. Quindi il numero massimo di amici che un utente può avere è (n-1). Possiamo inoltre trascurare questo (-1) per i nostri scopi, poiché nell'ambito dell'uso dei simboli O non è importante.

• Lettura dei dati: è necessario sottrarre l'intera riga e scorrere tutte le sue colonne nel limite. Ciò significa che la stima superiore dei costi sarà pari a circa O(n)
• Modifica dei dati: aggiunta di un amico: per determinare il numero di amici, devi scorrere tutte le colonne della riga, quindi inserire una nuova colonna => O(n)
• Modifica dati: eliminazione di un amico:
  • Simile all'aggiunta: devi scorrere tutte le colonne nel limite => O(n)
  • Dopo aver rimosso le colonne, dobbiamo “spostarle”. Se implementi questo "frontalmente", nel limite avrai bisogno di fino a (n-1) operazioni. Ma qui e più avanti nella parte pratica utilizzeremo un approccio diverso, che implementerà uno "pseudo-shift" per un numero fisso di operazioni, ovvero verrà dedicato un tempo costante, indipendentemente da n. Questa costante di tempo (O(2) per l'esattezza) può essere trascurata rispetto a O(n). L'approccio è illustrato nella figura seguente: copiamo semplicemente i dati dalla colonna “ultima” a quella da cui vogliamo eliminare i dati, quindi eliminiamo l'ultima colonna:
    

In totale, in tutti gli scenari abbiamo ricevuto una complessità computazionale asintotica di O(n).
Probabilmente avrai già notato che dobbiamo quasi sempre leggere l'intera riga dal database e, in due casi su tre, solo scorrere tutte le colonne e calcolare il numero totale di amici. Pertanto, come tentativo di ottimizzazione, puoi aggiungere una colonna “count”, che memorizza il numero totale di amici di ciascun utente della rete. In questo caso non possiamo leggere l'intera riga per calcolare il numero totale di amici, ma leggere solo una colonna “conteggio”. La cosa principale è non dimenticare di aggiornare il "conteggio" durante la manipolazione dei dati. Quello. miglioriamo Opzione 2 (conteggio):

RowKey
altoparlanti

Vasya
1: Petya
2: Olja
3: Dasha
conteggio: 3

Петя
1: Maša
2: Vasia

conteggio: 2

Rispetto alla prima opzione:

• Lettura dei dati: per ottenere una risposta alla domanda "Vasya legge Olya?" non è cambiato nulla => O(n)
• Modifica dei dati: aggiunta di un amico: Abbiamo semplificato l'inserimento di un nuovo amico, poiché ora non abbiamo bisogno di leggere l'intera riga e scorrere le sue colonne, ma possiamo solo ottenere il valore della colonna "count", ecc. determinare immediatamente il numero della colonna per inserire un nuovo amico. Ciò porta ad una riduzione della complessità computazionale a O(1)
• Modifica dati: eliminazione di un amico: Quando elimini un amico, possiamo anche usare questa colonna per ridurre il numero di operazioni di I/O quando “sposti” i dati di una cella a sinistra. Ma rimane ancora la necessità di scorrere le colonne per trovare quella da eliminare, quindi => ​​O(n)
• D'altra parte, ora quando aggiorniamo i dati dobbiamo aggiornare ogni volta la colonna "count", ma ciò richiede tempo costante, che può essere trascurato nell'ambito dei simboli O

In generale, l’opzione 2 sembra un po’ più ottimale, ma assomiglia più a “evoluzione invece che rivoluzione”. Per fare una “rivoluzione” avremo bisogno Opzione 3 (col).
Ribaltiamo tutto: nomineremo nome della colonna ID utente! Ciò che verrà scritto nella colonna stessa non è più importante per noi, lascia che sia il numero 1 (in generale lì possono essere memorizzate cose utili, ad esempio il gruppo “famiglia/amici/ecc.”). Questo approccio potrebbe sorprendere il “profano” impreparato che non ha alcuna esperienza precedente di lavoro con i database NoSQL, ma è proprio questo approccio che consente di utilizzare il potenziale di HBase in questo compito in modo molto più efficace:

RowKey
altoparlanti

Vasya
Petya: 1
Olja: 1
Dasha: 1

Петя
Maša: 1
Vasia: 1

Qui otteniamo diversi vantaggi contemporaneamente. Per capirli, analizziamo la nuova struttura e stimiamo la complessità computazionale:

• Lettura dei dati: per rispondere alla domanda se Vasya è iscritto a Olya, è sufficiente leggere una colonna “Olya”: se è lì, la risposta è Vero, in caso contrario – Falso => ​​O(1)
• Modifica dei dati: aggiunta di un amico: Aggiunta di un amico: basta aggiungere una nuova colonna “ID amico” => O(1)
• Modifica dati: eliminazione di un amico: rimuovi semplicemente la colonna ID amico => O(1)

Come puoi vedere, un vantaggio significativo di questo modello di archiviazione è che in tutti gli scenari di cui abbiamo bisogno, operiamo con una sola colonna, evitando di leggere l'intera riga dal database e, inoltre, enumerando tutte le colonne di questa riga. Potremmo fermarci qui, ma...

Potresti rimanere perplesso e andare un po' oltre lungo il percorso di ottimizzazione delle prestazioni e riduzione delle operazioni di I/O quando si accede al database. Cosa succederebbe se memorizzassimo le informazioni complete sulla relazione direttamente nella chiave di riga stessa? Cioè, crea la chiave composta come userID.friendID? In questo caso non dobbiamo nemmeno leggere le colonne della riga (Opzione 4(riga)):

RowKey
altoparlanti

Vasya.Petya
Petya: 1

Vasya.Olya
Olja: 1

Vasya.Dasha
Dasha: 1

Petya.Masha
Maša: 1

Petya.Vasya
Vasia: 1

Ovviamente, la valutazione di tutti gli scenari di manipolazione dei dati in una tale struttura, come nella versione precedente, sarà O(1). La differenza con l'opzione 3 riguarderà esclusivamente l'efficienza delle operazioni di I/O nel database.

Ebbene, l'ultimo “inchino”. È facile vedere che nell'opzione 4 la chiave di riga avrà una lunghezza variabile, il che potrebbe influire sulle prestazioni (qui 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 potrebbe dover essere gestito in alcuni scenari. Per eliminare questa influenza, puoi utilizzare gli hash di userID e friendID e poiché entrambi gli hash avranno una lunghezza costante, puoi semplicemente concatenarli, senza separatore. Quindi i dati nella tabella appariranno così (Opzione 5(hash)):

RowKey
altoparlanti

dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Petya: 1

dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Olja: 1

dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Dasha: 1

1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Maša: 1

1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Vasia: 1

Ovviamente, la complessità algoritmica di lavorare con tale struttura negli scenari che stiamo considerando sarà la stessa dell'opzione 4, ovvero O(1).
In totale, riassumiamo tutte le nostre stime della complessità computazionale in un'unica tabella:

Aggiunta di un amico
Sto controllando un amico
Rimozione di un amico

Opzione 1 (predefinita)
O (n)
O (n)
O (n)

Opzione 2 (conteggio)
O (1)
O (n)
O (n)

Opzione 3 (colonna)
O (1)
O (1)
O (1)

Opzione 4 (riga)
O (1)
O (1)
O (1)

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

Come puoi vedere, le opzioni 3-5 sembrano essere le più preferibili e teoricamente garantiscono l'esecuzione di tutti gli scenari di manipolazione dei dati necessari in tempo costante. Nelle condizioni del nostro compito non esiste un obbligo esplicito di ottenere un elenco di tutti gli amici dell'utente, ma nelle attività di progetto reali sarebbe bene per noi, da buoni analisti, "anticipare" che tale compito potrebbe sorgere e "spargi una cannuccia." Pertanto, le mie simpatie sono dalla parte dell'opzione 3. Ma è molto probabile che in un progetto reale questa richiesta avrebbe già potuto essere risolta con altri mezzi, quindi, senza una visione generale dell'intero problema, è meglio non fare conclusioni finali.

Preparazione dell'esperimento

Vorrei mettere alla prova gli argomenti teorici di cui sopra nella pratica: questo era l'obiettivo dell'idea nata durante il lungo fine settimana. Per fare ciò, è necessario valutare la velocità operativa della nostra “domanda condizionale” in tutti gli scenari descritti per l'utilizzo del database, nonché l'aumento di questo tempo con l'aumentare delle dimensioni del social network (n). Il parametro target che ci interessa e che misureremo durante l'esperimento è il tempo impiegato dalla “domanda condizionale” per eseguire una “operazione commerciale”. Per “transazione commerciale” intendiamo una delle seguenti:

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

Pertanto, tenuto conto dei requisiti delineati nella proposizione iniziale, lo scenario di verifica emerge come segue:

• Registrazione dati. Genera casualmente una rete iniziale di dimensione n. Per avvicinarci al “mondo reale”, anche il numero di amici di ciascun utente è una variabile casuale. Misura il tempo durante il quale la nostra "applicazione condizionale" scrive tutti i dati generati su HBase. Quindi dividi il tempo risultante per il numero totale di amici aggiunti: ecco come otteniamo il tempo medio per una "operazione commerciale"
• Lettura dei dati. Per ciascun utente, crea un elenco di "personalità" per le quali è necessario ottenere una risposta indipendentemente dal fatto che l'utente sia iscritto o meno. La lunghezza dell’elenco = approssimativamente il numero degli amici dell’utente, e per metà degli amici selezionati la risposta dovrebbe essere “Sì”, e per l’altra metà – “No”. Il controllo viene eseguito in modo tale che le risposte “Sì” e “No” si alternino (ovvero, in ogni secondo caso dovremo scorrere tutte le colonne della riga per le opzioni 1 e 2). Il tempo totale di screening viene quindi diviso per il numero di amici testati per ottenere il tempo di screening medio per soggetto.
• Cancellazione dei dati. Rimuovi tutti gli amici dall'utente. Inoltre, l'ordine di cancellazione è casuale (ovvero “mischiamo” l'elenco originale utilizzato per registrare i dati). Il tempo totale del controllo viene poi diviso per il numero di amici rimossi per ottenere il tempo medio per controllo.

Gli scenari devono essere eseguiti per ciascuna delle 5 opzioni del modello dati e per le diverse dimensioni del social network per vedere come cambia il tempo man mano che cresce. Entro un n le connessioni in rete e l'elenco degli utenti da controllare devono ovviamente essere gli stessi per tutte e 5 le opzioni.
Per una migliore comprensione, di seguito è riportato un esempio di dati generati per n= 5. La scritta “generatore” produce come output tre dizionari ID:

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

{0: [1], 1: [4, 5, 3, 2, 1], 2: [1, 2], 3: [2, 4, 1, 5, 3], 4: [2, 1]} # всего 15 друзей

{0: [1, 10800], 1: [5, 10800, 2, 10801, 4, 10802], 2: [1, 10800], 3: [3, 10800, 1, 10801, 5, 10802], 4: [2, 10800]} # всего 18 проверяемых субъектов

{0: [1], 1: [1, 3, 2, 5, 4], 2: [1, 2], 3: [4, 1, 2, 3, 5], 4: [1, 2]} # всего 15 друзей

Come puoi vedere, tutti gli ID superiori a 10 presenti nel dizionario da verificare sono proprio quelli che daranno sicuramente la risposta Falso. L'inserimento, il controllo e l'eliminazione degli “amici” vengono eseguiti esattamente nella sequenza specificata nel dizionario.

L'esperimento è stato condotto su un laptop con Windows 10, dove HBase era in esecuzione in un contenitore Docker e Python con Jupyter Notebook nell'altro. A Docker sono stati assegnati 2 core CPU e 2 GB di RAM. Tutta la logica, come l'emulazione della "applicazione condizionale" e del "piping" per la generazione dei dati di test e la misurazione del tempo, è stata scritta in Python. La libreria è stata utilizzata per lavorare con HBase happybase, per calcolare gli hash (MD5) per l'opzione 5 - hashlib

Tenendo conto della potenza di calcolo di un particolare laptop, è stato selezionato sperimentalmente un lancio per n = 10, 30, …. 170 – quando il tempo operativo totale dell'intero ciclo di test (tutti gli scenari per tutte le opzioni per tutti gli n) era ancora più o meno ragionevole e adatto a un tea party (in media 15 minuti).

Qui è necessario osservare che in questo esperimento non valutiamo principalmente le prestazioni assolute. Anche un confronto relativo tra due diverse opzioni potrebbe non essere del tutto corretto. Ora siamo interessati alla natura del cambiamento nel tempo in funzione di n, poiché tenendo conto della suddetta configurazione del "banco di prova", è molto difficile ottenere stime temporali "liberate" dall'influenza di fattori casuali e di altro tipo ( e tale compito non è stato fissato).

Il risultato dell'esperimento

Il primo test è come cambia il tempo impiegato nella compilazione della lista amici. Il risultato è nel grafico qui sotto.

Le opzioni 3-5, come previsto, mostrano un tempo di “transazione commerciale” quasi costante, che non dipende dalla crescita delle dimensioni della rete e da una differenza indistinguibile nelle prestazioni.
Anche l'opzione 2 mostra prestazioni costanti, ma leggermente peggiori, quasi esattamente 2 volte rispetto alle opzioni 3-5. E questo non può che rallegrarsi, poiché è correlato alla teoria: in questa versione il numero di operazioni I/O da/verso HBase è esattamente 2 volte maggiore. Ciò può servire come prova indiretta che il nostro banco di prova, in linea di principio, fornisce una buona precisione.
Anche l'opzione 1, come previsto, risulta essere la più lenta e dimostra un aumento lineare del tempo impiegato per aggiungersi l'un l'altro alla dimensione della rete.
Vediamo ora i risultati del secondo test.

Le opzioni 3-5 si comportano nuovamente come previsto: tempo costante, indipendentemente dalle dimensioni della rete. Le opzioni 1 e 2 dimostrano un aumento lineare nel tempo all'aumentare delle dimensioni della rete e prestazioni simili. Inoltre, l'opzione 2 risulta essere un po' più lenta, apparentemente a causa della necessità di correggere ed elaborare la colonna aggiuntiva “count”, che diventa più evidente man mano che n cresce. Ma mi asterrò comunque dal trarre conclusioni, poiché l’accuratezza di questo confronto è relativamente bassa. Inoltre, questi rapporti (quale opzione, 1 o 2, è più veloce) sono cambiati da una corsa all'altra (pur mantenendo la natura della dipendenza e del "testa a testa").

Bene, l'ultimo grafico è il risultato del test di rimozione.

Ancora una volta, nessuna sorpresa qui. Le opzioni 3-5 eseguono la rimozione in tempo costante.
Inoltre, è interessante notare che le opzioni 4 e 5, a differenza degli scenari precedenti, mostrano prestazioni leggermente peggiori rispetto all'opzione 3. Apparentemente, l'operazione di eliminazione delle righe è più costosa dell'operazione di eliminazione delle colonne, che generalmente è logica.

Le opzioni 1 e 2, come previsto, dimostrano un aumento lineare nel tempo. Allo stesso tempo, l'opzione 2 è costantemente più lenta dell'opzione 1, a causa delle operazioni di I/O aggiuntive per "mantenere" la colonna di conteggio.

Conclusioni generali dell'esperimento:

• Le opzioni 3-5 dimostrano una maggiore efficienza poiché sfruttano HBase; Inoltre, le loro prestazioni differiscono tra loro in modo costante e non dipendono dalle dimensioni della rete.
• La differenza tra le opzioni 4 e 5 non è stata registrata. Ma ciò non significa che l’opzione 5 non debba essere utilizzata. È probabile che lo scenario sperimentale utilizzato, tenendo conto delle caratteristiche prestazionali del banco prova, non ne abbia consentito il rilevamento.
• La natura dell'aumento del tempo necessario per eseguire le “operazioni commerciali” con i dati ha generalmente confermato i calcoli teorici precedentemente ottenuti per tutte le opzioni.

Finale

Gli esperimenti approssimativi effettuati non dovrebbero essere presi come verità assoluta. Ci sono molti fattori che non sono stati presi in considerazione e che hanno distorto i risultati (queste fluttuazioni sono particolarmente visibili nei grafici con reti di piccole dimensioni). Ad esempio, la velocità del risparmio, utilizzata da happybase, il volume e il metodo di implementazione della logica che ho scritto in Python (non posso affermare che il codice sia stato scritto in modo ottimale e abbia utilizzato efficacemente le capacità di tutti i componenti), forse le funzionalità della memorizzazione nella cache HBase, l'attività in background di Windows 10 sul mio laptop, ecc. In generale, possiamo supporre che tutti i calcoli teorici abbiano dimostrato sperimentalmente la loro validità. Ebbene, o almeno non è stato possibile confutarli con un simile “attacco frontale”.

In conclusione, raccomandazioni per tutti coloro che hanno appena iniziato a progettare modelli di dati in HBase: astrarre dalle precedenti esperienze di lavoro con database relazionali e ricordare i "comandamenti":

• Durante la progettazione si procede dal compito e dai modelli di manipolazione dei dati e non dal modello di dominio
• Accesso efficiente (senza scansione completa della tabella) – solo tramite chiave
• Denormalizzazione
• Righe diverse possono contenere colonne diverse
• Composizione dinamica dei relatori

Fonte: habr.com