🥇Ottimizzazioni Go in VictoriaMetrics. Alexander Valiatkin

Ti invitiamo a dare un'occhiata alla trascrizione della relazione di fine 2019 di Aleksandr Valjalkin "Ottimizzazioni Go in VictoriaMetrics"

VictoriaMetrics — un DBMS veloce e scalabile per la memorizzazione e l'elaborazione di dati sotto forma di serie temporali (una registrazione crea un tempo e un insieme di valori corrispondenti a quel tempo, ad esempio, ottenuti tramite interrogazioni periodiche dello stato dei sensori o raccolta di metriche).

Ecco il link al video di questa relazione — https://youtu.be/MZ5P21j_HLE

Diapositive

Vi racconterò un po' di me. Io sono Aleksandr Valjalkin. Ecco il mio account GitHub. Sono appassionato di Go e ottimizzazione delle prestazioni. Ho scritto molte librerie utili e non. Iniziano tutte con fast, o con quick prefisso.

Attualmente lavoro su VictoriaMetrics. Che cos'è e cosa faccio lì? Di questo parlerò in questa presentazione.

Il piano della relazione è il seguente:

Inizialmente vi parlerò di cosa sia VictoriaMetrics.
Poi vi dirò cosa sono le serie temporali.
Poi vi spiegherò come funziona un database di serie temporali.
Successivamente parlerò dell'architettura del database: da cosa è composta.
E infine passeremo alle ottimizzazioni presenti in VictoriaMetrics. Si tratta dell'ottimizzazione dell'indice invertito e dell'ottimizzazione per l'implementazione di bitset in Go.

Qualcuno in aula sa cos'è VictoriaMetrics? Incredibile, già molte persone lo sanno. Questa è una buona notizia. Per chi non lo sa: è un database per le serie temporali. È basato sull'architettura di ClickHouse, su alcuni dettagli dell'implementazione di ClickHouse. Ad esempio, come: MergeTree, calcoli paralleli su tutti i core della CPU disponibili e ottimizzazione delle prestazioni lavorando su blocchi di dati che vengono memorizzati nella cache della CPU.

VictoriaMetrics offre una compressione dei dati migliore rispetto ad altri database per serie temporali.

Si scalano verticalmente — cioè, puoi aggiungere un numero maggiore di processori, un numero maggiore di RAM su un singolo computer. VictoriaMetrics utilizzerà efficacemente queste risorse disponibili e aumenterà le prestazioni lineari.

Inoltre, VictoriaMetrics si scala orizzontalmente — cioè, puoi aggiungere nodi aggiuntivi al cluster di VictoriaMetrics, e le sue prestazioni cresceranno quasi linearmente.

Come avrete capito, VictoriaMetrics è un database veloce, perché non posso scrivere di altri. E è scritto in Go, perciò ne parlo in questo meetup.

Chi sa cos'è una serie temporale? Anche molte persone lo sanno. Una serie temporale è una serie di coppie (timestamp, valore), dove queste coppie sono ordinate nel tempo. Il valore è un numero in virgola mobile – float64.

Ogni serie temporale è univocamente identificata da una chiave. Di cosa è composta questa chiave? È composta da un insieme non vuoto di coppie chiave-valore.

Ecco un esempio di una serie temporale. La chiave di questa serie è un elenco di coppie: __name__="cpu_usage" – questo è il nome della metrica, instance="my-server" – questo è il computer su cui è stata raccolta questa metrica, datacenter="us-east" – questo è il data center dove si trova questo computer.

Abbiamo ottenuto il nome della serie temporale, composto da tre coppie chiave-valore. A questa chiave corrisponde un elenco di coppie (timestamp, valore). t1, t3, t3, ..., tN – questi sono i timestamp, 10, 20, 12, ..., 15 – i valori corrispondenti. Questo è il cpu-usage in quel momento per questa serie.

Dove possono essere utilizzate le serie temporali? Qualcuno ha idee?

In DevOps si possono misurare i valori di utilizzo della CPU, RAM, rete, rps, numero di errori, ecc.
IoT – possiamo misurare temperatura, pressione, coordinate geografiche e altro.
Inoltre, nel settore finanziario – possiamo monitorare i prezzi delle azioni e delle valute.
In aggiunta, le serie temporali possono essere utilizzate per monitorare i processi produttivi nelle fabbriche. Abbiamo utenti che utilizzano VictoriaMetrics per monitorare turbine eoliche, per robot.
Le serie temporali sono anche utili per raccogliere informazioni da sensori di diversi dispositivi. Ad esempio, per i motori; per misurare la pressione nei pneumatici; per misurare velocità, distanza; per misurare il consumo di benzina, ecc.
Le serie temporali possono anche essere utilizzate per il monitoraggio degli aerei. Ogni aereo ha una scatola nera che raccoglie serie temporali su diversi parametri di salute dell'aereo. Le serie temporali sono anche utilizzate nell'industria aerospaziale.
In sanità – si tratta di pressione sanguigna, battito cardiaco, ecc.

Forse ci sono altre applicazioni che ho dimenticato, ma spero che abbiate capito che le serie temporali sono ampiamente utilizzate nel mondo moderno. E il loro utilizzo cresce di anno in anno.

A cosa serve un database per le serie temporali? Perché non è possibile utilizzare un normale database relazionale per memorizzare le serie temporali?

Perché nei serie temporali di solito c'è un grande volume di informazioni, che è difficile da conservare e elaborare in normali database. Ecco perché sono apparse banche dati specializzate per le serie temporali. Questi database conservano efficacemente i punti (timestamp, valore) con una chiave specificata. Forniscono un'API per leggere i dati salvati tramite la chiave, una coppia chiave-valore alla volta, oppure più coppie, oppure tramite regexp. Ad esempio, se vuoi trovare il carico della CPU di tutti i tuoi servizi nel data center in America, devi usare una pseudo-query del genere.

Di solito, i database per le serie temporali presentano linguaggi di query specializzati, poiché SQL per le serie temporali non si adatta molto bene. Anche se ci sono database che supportano SQL, non funziona molto bene. Linguaggi di query come PromQL, InfluxQL, Flux, Qsi adattano meglio. Spero che qualcuno abbia sentito parlare almeno uno di questi linguaggi. PromQL, probabilmente, è conosciuto da molti. Questo è il linguaggio di query di Prometheus.

Ecco come appare l'architettura di un moderno database per le serie temporali, prendendo come esempio VictoriaMetrics.

È composta da due parti. C'è uno storage per l'indice invertito e uno storage per i valori delle serie temporali. Questi storage sono separati.

Quando arriva una nuova registrazione nel database, prima di tutto ci rivolgiamo all'indice invertito per trovare l'identificativo della serie temporale in base al set di label=value per questa metrica. Troviamo questo identificativo e salviamo il valore nello storage dei dati.

Quando arriva una richiesta di estrazione dei dati dal TSDB, prima di tutto andiamo nell'indice invertito. Recuperiamo tutti i timeseries_ids record che corrispondono al set dato. label=valueE poi preleviamo tutti i dati necessari dallo storage dei dati, indicizzati per timeseries_ids.

Esaminiamo un esempio di come un database per serie temporali gestisce una richiesta di select in entrata.

Per prima cosa, recupera tutti gli timeseries_ids dall'indice invertito, che contengono le coppie specificate, label=valueoppure soddisfano l'espressione regolare data.
Poi recupera tutti i data points dallo storage dei dati in un intervallo di tempo specificato per quelli trovati. timeseries_ids.
Dopo di che, il database esegue alcuni calcoli su questi data points, secondo la richiesta dell'utente. Dopodiché restituisce la risposta.

In questa presentazione, parlerò della prima parte. Questa è la ricerca timeseries_ids secondo l'indice invertito. Puoi poi guardare la seconda e la terza parte sorgenti VictoriaMetrics, oppure aspettare che prepari altre relazioni 🙂

Iniziamo con l'indice invertito. A molti potrebbe sembrare semplice. Chi sa cos'è un indice invertito e come funziona? Oh, non ci sono più molte persone. Proviamo a capire di cosa si tratta.

In realtà è molto semplice. È solo un dizionario che mappa una chiave a un valore. Cos'è una chiave? Questa coppia label=value, dove label e value è costituita da stringhe. E i valori sono un insieme timeseries_ids, che include la coppia data label=value.

L'indice invertito consente di trovare rapidamente tutti timeseries_ids, che hanno le label=value.

Consente anche di trovare rapidamente timeseries_ids serie temporali per diverse coppie label=value, oppure per coppie label=regexp. Come funziona? Trovando l'intersezione di un insieme timeseries_ids per ogni coppia label=value.

Esaminiamo diverse implementazioni dell'indice invertito. Iniziamo con la più semplice, l'implementazione naive. Si presenta così.

La funzione getMetricIDs ottiene un elenco di stringhe. Ogni stringa contiene label=value. Questa funzione restituisce un elenco metricIDs.

Come funziona? Abbiamo una variabile globale chiamata invertedIndex. È un dizionario normale (map), che mappa la stringa su un slice di interi. La stringa contiene label=value.

Implementazione della funzione: estrae metricIDs per il primo label=value, poi esaminiamo tutti gli altri label=value, estraendo metricIDs per loro. E chiamiamo la funzione intersectInts, di cui si parlerà in seguito. E questa funzione restituisce l'intersezione di queste liste.

Come puoi vedere, l'implementazione dell'indice invertito non è molto complessa. Ma è un'implementazione naive. Quali sono i suoi svantaggi? Il principale svantaggio dell'implementazione naive è che tale indice invertito è memorizzato nella memoria volatile. Dopo il riavvio dell'applicazione, perdiamo questo indice. Non viene salvato su disco. Per un database, un tale indice invertito difficilmente sarà utile.

Il secondo svantaggio è anch'esso legato alla memoria. L'indice invertito deve adattarsi nella memoria volatile. Se supera la dimensione della memoria, è evidente che otterremo un errore di out of memory. E il programma non funzionerà.

Questo problema può essere risolto con soluzioni pronte, come LevelDB, oppure RocksDB.

In sintesi, abbiamo bisogno di un database che consenta di eseguire rapidamente tre operazioni.

La prima operazione è la registrazione chiave-valore in questo database. La esegue molto rapidamente, dove chiave-valore sono stringhe arbitrarie.
La seconda operazione è una ricerca rapida di un valore per chiave specificata.
E la terza operazione è una ricerca rapida di tutti i valori per un prefisso specificato.

LevelDB e RocksDB sono database sviluppati rispettivamente da Google e Facebook. Inizialmente è stato realizzato LevelDB. Successivamente, i ragazzi di Facebook hanno preso LevelDB e hanno iniziato a migliorarla, creando RocksDB. Attualmente, quasi tutti i database interni di Facebook sono basati su RocksDB, incluso MySQL, che è stato convertito in RocksDB. Lo hanno chiamato MyRocks.

Un indice invertito può essere implementato utilizzando LevelDB. Come si fa? Salviamo come chiave label=value. E come valore - l'identificativo di una serie temporale, dove è presente la coppia label=value.

Se abbiamo molte serie temporali con questa coppia label=value, ci saranno molte righe in questo database con la stessa chiave e valori diversi timeseries_ids. Per ottenere l'elenco di tutti i timeseries_ids, che iniziano con il dato label=prefix, facciamo una scansione di intervallo, per la quale questo database è ottimizzato. Cioè, selezioniamo tutte le righe che iniziano con label=prefix e otteniamo i necessari timeseries_ids.

Ecco un'implementazione approssimativa di come sarebbe su Go. Abbiamo un indice invertito. Questo è LevelDB.

La funzione è la stessa di quella per l'implementazione naive. Ripete quasi riga per riga l'implementazione naive. L'unico punto è che invece di interagire con map interagiamo con l'indice invertito. Recuperiamo tutti i valori per la prima label=value. Poi scorriamo tutte le coppie rimanenti label=value e otteniamo i corrispondenti set di metricIDs per esse. Poi troviamo l'intersezione.

Sembra tutto a posto, ma in questa soluzione ci sono svantaggi. VictoriaMetrics inizialmente implementava l'indice invertito basato su LevelDB. Ma alla fine hanno dovuto rinunciare ad esso.

Perché? Perché LevelDB è più lento dell'implementazione naive. Nell'implementazione naive, per una chiave specificata recuperiamo subito l'intero slice metricIDs. Questa è un'operazione molto veloce: l'intero slice è pronto per l'uso.

In LevelDB, ogni volta che chiamiamo la funzione GetValues , dobbiamo esaminare tutte le righe che iniziano con label=value. E per ogni riga recuperare il valore timeseries_ids. Da tali timeseries_ids costruire uno slice di essi. timeseries_idsÈ evidente che questo è molto più lento rispetto ad accedere semplicemente a una normale mappa per chiave.

Il secondo svantaggio è che LevelDB è scritto in C. L'interazione con le funzioni C da Go non è molto veloce. Ci vogliono centinaia di nanosecondi. Non è molto veloce, perché rispetto a una chiamata normale di una funzione scritta in Go, che impiega 1-5 nanosecondi, la differenza di prestazioni è anche di decine di volte. Per VictoriaMetrics, questo è stato un difetto fatale 🙂

Pertanto, ho scritto una mia implementazione dell'indice invertito. E l'ho chiamata mergeset.

Mergeset si basa su una struttura dati MergeTree. Questa struttura dati è stata presa in prestito da ClickHouse. È ovvio che mergeset deve essere ottimizzato per una ricerca rapida timeseries_ids per una chiave specificata. Mergeset è scritto interamente in Go. Puoi vedere il codice sorgente di VictoriaMetrics su GitHub. L'implementazione di mergeset si trova nella cartella /lib/mergeset. Puoi provare a capire cosa succede lì.

L'API di mergeset è molto simile a LevelDB e RocksDB. Cioè, permette di memorizzare rapidamente nuovi record e di selezionare rapidamente i record per un prefisso specificato.

Parleremo più tardi degli svantaggi di mergeset. Ora parliamo dei problemi che si sono presentati con VictoriaMetrics in produzione durante l'implementazione dell'indice invertito.

Perché sono emersi?

La prima ragione è l'alto tasso di turnover. Tradotto in italiano, significa un frequente cambio di serie temporali. Questo accade quando una serie temporale termina e inizia una nuova serie, oppure iniziano molte nuove serie temporali. E questo accade spesso.

La seconda ragione è il grande numero di serie temporali. Inizialmente, quando il monitoraggio ha guadagnato popolarità, il numero di serie temporali era ridotto. Ad esempio, per ogni computer è necessario monitorare il carico della CPU, della memoria, della rete e del disco. 4 serie temporali per ogni computer. Se hai, ad esempio, 100 computer, hai 400 serie temporali. Questo è molto poco.

Con il passare del tempo, le persone hanno trovato modi per misurare informazioni più dettagliate. Ad esempio, misurare il carico non dell'intera CPU, ma di ciascun core della CPU separatamente. Se hai 40 core della CPU, allora hai 40 volte più serie temporali per misurare il carico della CPU.

Ma non è tutto. Ogni core del processore può avere più stati, come idle, quando è inattivo. Così come il lavoro in user space, il lavoro in kernel space e altri stati. E ogni stato può essere misurato come una serie temporale separata. Questo aumenta ulteriormente il numero di serie di 7-8 volte.

Da una singola metrica abbiamo ottenuto 40 x 8 = 320 metriche solo per un computer. Moltiplichiamo per 100, otteniamo 32.000 anziché 400.

Poi è arrivato Kubernetes. E questo ha ulteriormente peggiorato la situazione, perché in Kubernetes possono essere ospitati molti servizi diversi. Ogni servizio in Kubernetes è composto da molti pod. E tutto questo deve essere monitorato. Inoltre, abbiamo un deployment costante di nuove versioni dei vostri servizi. Per ogni nuova versione è necessario creare nuove serie temporali. Di conseguenza, il numero di serie temporali cresce esponenzialmente e ci troviamo di fronte al problema di un gran numero di serie temporali, chiamato high-cardinality. VictoriaMetrics affronta con successo questo problema rispetto ad altri database per serie temporali.

Esaminiamo più nel dettaglio l'high churn rate. Cosa causa l'high churn rate in produzione? Perché alcuni valori delle etichette e dei tag cambiano costantemente.

Per esempio, prendiamo Kubernetes, in cui esiste il concetto deployment, cioè quando viene distribuita una nuova versione della vostra applicazione. Gli sviluppatori di Kubernetes hanno deciso di aggiungere l'id del deployment nell'etichetta.

A cosa ha portato questo? Al fatto che ad ogni nuovo deployment tutte le vecchie serie temporali vengono interrotte e al loro posto iniziano nuove serie temporali con un nuovo valore dell'etichetta deployment_id. Tali serie possono essere centinaia di migliaia e anche milioni.

L'aspetto importante di tutto questo è che il numero totale di serie temporali cresce, ma il numero di serie temporali attualmente attive, per le quali arrivano dati, rimane costante. Questo stato è chiamato high churn rate.

Il problema principale dell'high churn rate è garantire una velocità di ricerca costante per tutte le serie temporali in base a un dato insieme di etichette in un certo intervallo di tempo. Di solito, questo intervallo di tempo è l'ultima ora o l'ultimo giorno.

Come possiamo risolvere questo problema? Ecco la prima opzione. Si tratta di suddividere l'indice invertito in parti indipendenti nel tempo. Cioè, un certo intervallo di tempo passa, smettiamo di lavorare con l'indice invertito attuale. E creiamo un nuovo indice invertito. Passa un altro intervallo di tempo, creiamo ancora un altro e così via.

E durante la selezione di questi indici invertiti, troviamo un insieme di indici invertiti che rientrano nell'intervallo fornito. E, di conseguenza, selezioniamo da lì gli id delle serie temporali.

Questo consente di risparmiare risorse, perché non dobbiamo esaminare parti che non rientrano nell'intervallo fornito. Cioè, di solito, se selezioniamo i dati per l'ultima ora, saltiamo le richieste per gli intervalli temporali precedenti.

C'è un'altra opzione per risolvere questo problema. È memorizzare un elenco separato di id delle serie temporali per ogni giorno, che sono apparsi in quel giorno.

Il vantaggio di questa soluzione rispetto alla soluzione precedente è che non dupliciamo le informazioni sulle serie temporali che non scompaiono nel tempo. Rimangono costantemente e non cambiano.

Lo svantaggio è che tale soluzione è più complessa da implementare e più difficile da debug. E VictoriaMetrics ha scelto questa soluzione. È stato storico. Questa soluzione si è dimostrata anche abbastanza valida, rispetto alla precedente. Perché questa soluzione non è stata implementata a causa della necessità di duplicare i dati in ogni partizione per le serie temporali che non cambiano, cioè che non scompaiono nel tempo. VictoriaMetrics è stata prima di tutto ottimizzata per il consumo di spazio su disco, e la precedente implementazione peggiorava il consumo di spazio su disco. Mentre questa implementazione è più adatta per minimizzare il consumo di spazio su disco, perciò è stata scelta.

Abbiamo dovuto combattere con essa. La lotta consisteva nel fatto che in questa implementazione dovevamo comunque selezionare un numero molto maggiore timeseries_ids per i dati, rispetto a quando l'indice invertito è suddiviso nel tempo.

Come abbiamo risolto questo problema? L'abbiamo risolta in modo originale, memorizzando più identificatori di serie temporali in ogni registrazione dell'indice invertito invece di un singolo identificatore. Cioè, abbiamo una chiave label=value, che si verifica in ogni serie temporale. E ora stiamo salvando diversi timeseries_ids in un'unica registrazione.

Ecco un esempio. Prima avevamo N registrazioni, ora abbiamo un'unica registrazione, il cui prefisso è lo stesso di tutte le altre. La registrazione precedente conteneva tutti gli id delle serie temporali.

Questo ha permesso di aumentare la velocità di scansione di un tale indice invertito fino a 10 volte. E ha ridotto il consumo di memoria per la cache, perché ora memorizziamo la stringa label=value solo una volta nella cache insieme a N volte. E questa stringa può essere grande, se nei tag e nelle etichette hai stringhe lunghe che Kubernetes ama infilare.

Un'altra opzione per accelerare la ricerca attraverso l'indice invertito è lo sharding. Creare più indici invertiti invece di uno solo e shardare i dati tra di essi in base a una chiave. Questo è un insieme chiave=valore di coppie. Cioè, otteniamo diversi indici invertiti indipendenti, che possiamo interrogare in parallelo su più processori. Le implementazioni precedenti funzionavano solo in modalità single-core, cioè scansionando i dati su un solo core. Questa soluzione consente di scansionare i dati su più core contemporaneamente, come solitamente fa ClickHouse. Questo è ciò che pianifichiamo di implementare.

Ora torniamo ai nostri argomenti – alla funzione di intersezione timeseries_ids. Vediamo quali potrebbero essere le implementazioni. Questa funzione consente di trovare timeseries_ids per un set dato label=value.

La prima opzione è l'implementazione naif. Due cicli annidati. Ecco che riceviamo come input della funzione intersectInts due slice — a e b. In output dovrebbe restituirci l'intersezione di questi slice.

L'implementazione naif appare così. Scorriamo tutti i valori dallo slice a, all'interno di questo ciclo scorriamo tutti i valori dello slice b. E li confrontiamo. Se coincidono, significa che abbiamo trovato l'intersezione. E lo salviamo in risultato.

Quali sono gli svantaggi? La complessità quadratica è il suo principale svantaggio. Ad esempio, se hai dimensioni dello slice a e b di un milione, questa funzione non ti restituirà mai una risposta. Perché le dovrebbero essere fatte un trilione di iterazioni, che è davvero tante anche per i computer moderni.

La seconda implementazione è basata su una mappa. Creiamo una mappa. Inseriamo in questa mappa tutti i valori dello slice a. Poi facciamo un ciclo separato sullo slice b. E verifichiamo: esiste questo valore nello slice b in map. Se esiste, lo aggiungiamo al risultato.

Quali sono i vantaggi? Il vantaggio è che qui c'è solo complessità lineare. Cioè, la funzione sarà eseguita molto più velocemente per dimensioni maggiori degli slice. Per uno slice di dimensione milione, questa funzione sarà eseguita in 2 milioni di iterazioni, rispetto a un trilione di iterazioni, come nella funzione precedente.

E lo svantaggio è che questa funzione richiede più memoria per creare questa mappa.

Il secondo svantaggio è il grande overhead per l'hashing. Questo svantaggio non è molto ovvio. E per noi non è stato molto ovvio, quindi all'inizio nell'implementazione dell'intersezione in VictoriaMetrics era utilizzata una map. Ma poi il profiling ha mostrato che la maggior parte del tempo di CPU veniva speso nella scrittura nella map e nel controllo dell'esistenza di un valore in questa map.

Perché in questi casi viene speso tempo di CPU? Perché in queste righe Go esegue un'operazione di hashing. Cioè calcola l'hash della chiave per poi accedere all'indice specificato in HashMap. L'operazione di calcolo dell'hash viene eseguita in decine di nanosecondi. Questo è lento per VictoriaMetrics.

Ho deciso di implementare un bitset, ottimizzato appositamente per questo caso. Ecco come appare ora l'intersezione di due slice. Qui creiamo un bitset. Aggiungiamo gli elementi dal primo slice. Poi verifichiamo la presenza di questi elementi nel secondo slice. E li aggiungiamo al risultato. Cioè, quasi non si differenzia dall'esempio precedente. L'unica cosa che abbiamo qui è stata la sostituzione dell'accesso alla mappa con funzioni personalizzate. add e has.

A prima vista sembra che dovrebbe funzionare più lentamente, se prima si usava una mappa standard e qui vengono chiamate ulteriori funzioni, ma il profiling mostra che questa cosa funziona 10 volte più velocemente della mappa standard per il caso di VictoriaMetrics.

Inoltre, utilizza molta meno memoria rispetto all'implementazione su map. Perché qui conserviamo bit invece di valori a otto byte.

Lo svantaggio di tale implementazione è che non è così ovvia, non è banale.

Un altro svantaggio che molti potrebbero non notare è che questa implementazione potrebbe funzionare male in alcuni casi. Cioè, è ottimizzata per un caso specifico, per questo caso di intersezione degli ids delle serie temporali di VictoriaMetrics. Ciò non significa che sia adatta a tutti i casi. Se viene usata in modo errato, non otterremo un incremento delle prestazioni, ma un errore di out of memory e un rallentamento delle prestazioni.

Esaminiamo l'implementazione di questa struttura. Se vuoi darci un'occhiata, si trova nel codice sorgente di VictoriaMetrics, nella cartella lib/uint64set. È ottimizzata proprio per il caso di VictoriaMetrics, dove timeseries_id è un valore a 64 bit, dove i primi 32 bit sono principalmente costanti e cambiano solo gli ultimi 32 bit.

Questa struttura dati non viene memorizzata su disco, funziona solo in memoria.

Ecco la sua API. Non è molto complessa. L'API è adattata proprio per questo caso d'uso di VictoriaMetrics. Cioè, qui non ci sono funzioni superflue. Qui ci sono funzioni che vengono utilizzate esplicitamente da VictoriaMetrics.

Ci sono funzioni add, che aggiungono nuovi valori. C'è una funzione has, che verifica nuovi valori. E c'è una funzione del, che rimuove valori. C'è una funzione ausiliaria len, che restituisce la dimensione dell'insieme. La funzione clone clona l'insieme. E la funzione appendto trasforma questo set in uno slice timeseries_ids.

Ecco come appare l'implementazione di questa struttura dati. Nel set ci sono due elementi:

ItemsCount – è un campo ausiliario, per restituire rapidamente il numero di elementi nel set. Si potrebbe fare a meno di questo campo ausiliario, ma è stato necessario aggiungerlo qui, perché VictoriaMetrics interroga spesso nei suoi algoritmi la lunghezza del bitset.
Il secondo campo è buckets. Si tratta di uno slice della struttura bucket32. In ogni struttura è memorizzato hi un campo. Questi sono i 32 bit superiori. E due slice — b16his e buckets da bucket16 strutture.

Qui sono memorizzati i 16 bit superiori della seconda parte della struttura a 64 bit. E qui sono memorizzati i bitset per i 16 bit inferiori di ciascun byte.

Bucket64 è composto da un array uint64. La lunghezza è calcolata usando queste costanti. In un bucket16 può essere memorizzato al massimo 2^16=65536 bit. Se si divide per 8, si ottiene 8 kilobyte. Se si divide ancora per 8, si ottiene 1000 uint64 valori. Cioè, Bucket16 è una struttura da 8 kilobyte.

Esaminiamo come è implementato uno dei metodi di questa struttura per aggiungere un nuovo valore.

Tutto inizia con uint64 valori. Calcoliamo i 32 bit superiori, calcoliamo i 32 bit inferiori. Controlliamo tutti buckets. Confrontiamo i 32 bit superiori in ciascun bucket con il valore da aggiungere. E se sono uguali, chiamiamo la funzione add nella struttura b32 buckets. E vi aggiungiamo i 32 bit inferiori. E se ha restituito true, significa che abbiamo aggiunto quel valore lì e non avevamo già quel valore. Se restituisce false, significa che quel valore era già presente. Poi aumentiamo il numero di elementi nella struttura.

Se non abbiamo trovato il necessario bucket con il giusto valore hi, chiamiamo la funzione addAlloc, che alloca un nuovo bucket, aggiungendolo nella struttura del bucket.

Questa è l'implementazione della funzione b32.add. È simile all'implementazione precedente. Calcoliamo i 16 bit superiori e i 16 bit inferiori.

Poi controlliamo tutti i 16 bit superiori. Troviamo le corrispondenze. E in caso di corrispondenza chiamiamo il metodo add, che esamineremo nella pagina successiva per bucket16.

Ecco il livello più basso, che deve essere ottimizzato al massimo. Calcoliamo per uint64 id il valore nel bit slice, così come bitmask. Questa è la maschera per il dato valore a 64 bit, con la quale possiamo controllare la presenza di questo bit o impostarlo. Verifichiamo la presenza di questo bit, lo impostiamo e restituiamo la presenza. Ecco un'implementazione che ci ha permesso di accelerare l'operazione di intersezione degli ids delle serie temporali di 10 volte rispetto alle normali mappe.

In VictoriaMetrics, oltre a questa ottimizzazione, ci sono molte altre ottimizzazioni. Gran parte di queste ottimizzazioni non è stata aggiunta a caso, ma dopo aver profilato il codice in produzione.

Questa è la regola principale dell'ottimizzazione: non aggiungere ottimizzazione supponendo che qui ci sarà un collo di bottiglia, perché potrebbe rivelarsi che lì non ci sia. L'ottimizzazione di solito peggiora la qualità del codice. Perciò è meglio ottimizzare solo dopo aver profilato e idealmente in produzione, affinché si tratti di dati reali. Chi è interessato può dare un'occhiata ai sorgenti di VictoriaMetrics e studiare altre ottimizzazioni che ci sono.

Ho una domanda sul bitset. Sembra molto simile all'implementazione C++ vector bool, bitset ottimizzato. Avete preso l'implementazione da lì?

No, non è da lì. Nella realizzazione di questo bitset mi sono basato sulla comprensione della struttura di questi ids timeseries, che vengono utilizzati in VictoriaMetrics. La loro struttura è tale che i 32 bit superiori sono principalmente costanti. I 32 bit inferiori possono cambiare. Più il bit è basso, più frequentemente può cambiare. Pertanto, questa implementazione è ottimizzata per questa particolare struttura dati. L'implementazione in C++, per quanto ne so, è ottimizzata per il caso generale. Se si fa un'ottimizzazione per il caso generale, significa che non sarà la più ottimale per un caso specifico.

Ti consiglio di dare un'occhiata anche alla presentazione di Alexey Milovid. Circa un mese fa ha parlato delle ottimizzazioni in ClickHouse per specializzazioni specifiche. Spiega proprio che, in generale, l'implementazione in C++ o un'altra qualche implementazione è progettata per funzionare bene in media. Può funzionare peggio rispetto a un'implementazione specializzata per conoscenze specifiche, come nel nostro caso, quando sappiamo che i 32 bit superiori sono principalmente costanti.

Ho una seconda domanda. Qual è la differenza fondamentale rispetto a InfluxDB?

Le differenze fondamentali sono molte. Se consideriamo le prestazioni e l'utilizzo della memoria, InfluxDB nei test mostra un consumo di memoria dieci volte superiore per i time series ad alta cardinalità, quando ne hai molti, ad esempio milioni. Ad esempio, VictoriaMetrics consuma 1 GB per un milione di serie attive, mentre InfluxDB consuma 10 Gb. E questa è una grande differenza.

La seconda differenza fondamentale è che in InfluxDB ci sono linguaggi di query strani – Flux e InfluxQL. Non sono molto comodi per lavorare con le serie temporali rispetto a PromQL, che è supportato in VictoriaMetrics. PromQL è il linguaggio di query di Prometheus.

E un'altra differenza è che InfluxDB ha un modello dati un po' strano, in cui ogni riga può contenere più fields con diverse combinazioni di tags. Queste righe sono ulteriormente divise in diverse tabelle. Questi ulteriori complessità complicano il lavoro successivo con questo database. È difficile da mantenere e comprendere.

In VictoriaMetrics tutto è molto più semplice. Ogni serie temporale è rappresentata come una coppia chiave-valore. Il valore è un insieme di punti – (timestamp, valore), mentre la chiave è un insieme label=value. Non c'è alcuna divisione tra fields e measurements. Questo ti consente di selezionare qualsiasi dato e poi combinarlo, sommarlo, sottrarlo, moltiplicarlo, dividerlo, a differenza di InfluxDB, dove i calcoli tra righe diverse non sono ancora implementati, per quanto ne so. Anche se lo fossero, sarebbe complicato, poiché bisognerebbe scrivere un sacco di codice.

Ho una domanda di chiarimento. Ho capito correttamente che c'era qualche problema di cui parlavi, ossia che questo indice invertito non riesce a stare in memoria, quindi ci sono partizioni?

Inizialmente ho mostrato un'implementazione semplice dell'indice invertito su una standard map di Go. Tale implementazione non è adatta per i database, perché questo indice invertito non viene salvato su disco, e un database deve salvare su disco affinché questi dati siano accessibili dopo un riavvio. In questa implementazione, dopo il riavvio dell'applicazione, l'indice invertito andrà perso. E perderai l'accesso a tutti i dati, perché non riuscirai a trovarli.

Salve! Grazie per la presentazione! Mi chiamo Pavel. Vengo dall'azienda Wildberries. Ho alcune domande per te. Prima domanda. Cosa ne pensi, se avessi scelto un altro principio nella costruzione dell'architettura della tua applicazione e avessi partizionato i dati in base al tempo, forse saresti riuscito a incrociare i dati nella ricerca, basandoti solo sul fatto che in una partizione ci siano dati per un determinato intervallo di tempo, e quindi non dovresti preoccuparti del fatto che i tuoi dati siano disposti in maniera diversa? Seconda domanda: visto che stai implementando un algoritmo simile con bitset e altro, hai forse provato a utilizzare le istruzioni del processore? Potrebbe essere che tu abbia provato queste ottimizzazioni?

Risponderò subito alla seconda domanda. Non siamo ancora arrivati a questo punto. Ma se sarà necessario, ci arriveremo. E la prima, qual era la domanda?

Hai discusso di due scenari. E hai detto che hai scelto il secondo con un'implementazione più complessa. E non hai preferito il primo, dove i dati sono partizionati in base al tempo.

Sì. Nel primo caso, il volume complessivo dell'indice sarebbe stato maggiore, perché in ogni partizione avremmo dovuto memorizzare dati duplicati per quelle serie temporali che si estendono attraverso tutte queste partizioni. E se hai un churn rate basso per le serie temporali, cioè vengono utilizzate costantemente le stesse serie, nel primo caso avremmo perso molto di più in termini di spazio su disco rispetto al secondo caso.

Sì, la partizionamento per tempo è una buona opzione. È ciò che utilizza Prometheus. Ma in Prometheus c'è un altro svantaggio. Durante la fusione di questi pezzi di dati, deve mantenere in memoria le informazioni meta su tutte le etichette e le serie temporali. Pertanto, se i pezzi di dati che sta fondendo sono grandi, il consumo di memoria aumenta notevolmente durante la fusione, a differenza di VictoriaMetrics. Durante la fusione, VictoriaMetrics non consuma affatto memoria, consumando solo qualche kilobyte, indipendentemente dalle dimensioni dei pezzi di dati uniti.

L'algoritmo che stai usando utilizza memoria. In essa vengono contrassegnate le etichette delle serie temporali su cui ci sono valori. In questo modo controlli la presenza di coppie in un array di dati e in un altro. E capisci se c'è stata un'intersezione o meno. Di solito, nei database vengono implementati cursori, iteratori che mantengono il loro stato attuale e scorrono attraverso dati ordinati, consentendoti di avere una complessità semplice in quelle operazioni.

Perché non usiamo cursori per l'intersezione dei dati?

Sì.

Abbiamo in LevelDB o nel mergeset le righe ordinate. Possiamo usare un cursore per percorrerle e trovare l'intersezione. E perché non lo facciamo? Perché è lento. Perché i cursori presuppongono che per ogni riga debba essere chiamata una funzione. La chiamata di una funzione richiede 5 nanosecondi. E se hai 100.000.000 righe, significa che spendiamo mezzo secondo solo per chiamare la funzione.

C'è questo, sì. E l'ultima domanda che ho. La domanda, forse, suonerà un po' strana. Perché al momento dell'arrivo dei dati non si possono calcolare tutte le aggregazioni necessarie e salvarle nella forma necessaria? Perché salvare enormi volumi in sistemi come VictoriaMetrics, ClickHouse, ecc., per poi spendere molto tempo su di essi?

Porterò un esempio per chiarire. Supponiamo, come funziona un piccolo tachimetro giocattolo? Registra la distanza percorsa, aggiungendo continuamente un valore, e nell’altro valore – il tempo. E divide. E ottiene la velocità media. Puoi fare più o meno la stessa cosa. Sommare in corsa tutti i fatti necessari.

Bene, ho capito la domanda. Il tuo esempio è valido. Se sai quali aggregati ti servono, questa è la migliore implementazione. Ma il problema è che le persone salvano queste metriche, alcuni dati in ClickHouse e non sanno ancora come li aggregano, filtrano in futuro, quindi devono salvare tutti i dati grezzi. Ma se sai che devi calcolare qualcosa di medio, perché non farlo, invece di conservare lì un sacco di valori grezzi? Ma questo vale solo se sai esattamente di cosa hai bisogno.

A proposito, le basi per la conservazione di serie temporali supportano il conteggio degli aggregati. Ad esempio, Prometheus supporta le regole di registrazione. Cioè, questo può essere fatto, se sai quali aggregati ti serviranno. In VictoriaMetrics questo non è ancora presente, ma di solito c'è Prometheus prima, dove è possibile farlo nelle regole di registrazione.

Ad esempio, nel lavoro precedente era necessario contare il numero di eventi in una finestra mobile nell'ultimo ora. Il problema è stato che ho dovuto fare un'implementazione personalizzata in Go, cioè un servizio per contare questa cosa. Questo servizio è stato alla fine non banale, perché è difficile da calcolare. L'implementazione può essere semplice se devi contare alcuni aggregati su intervalli di tempo fissi. Se invece vuoi contare eventi in una finestra mobile, non è così semplice come sembra. Penso che non sia ancora realizzato in ClickHouse o nelle basi di dati temporali, perché è difficile da implementare.

E un'altra domanda. Abbiamo appena parlato di media, e mi sono ricordato che un tempo esisteva una cosa chiamata Graphite con backend Carbon. E lui sapeva diradare i dati vecchi, cioè lasciare un punto al minuto, un punto all'ora e così via. In effetti, è abbastanza comodo, se abbiamo bisogno di dati grezzi, per così dire, per un mese, mentre tutto il resto può essere diradato. Ma Prometheus e VictoriaMetrics non supportano questa funzionalità. È prevista in futuro? Se no, perché?

Grazie per la domanda. I nostri utenti la pongono periodicamente. Chiedono quando aggiungeremo il supporto al downsampling. Ci sono diversi problemi. Prima di tutto, ogni utente ha una propria interpretazione di downsampling : qualcuno desidera ottenere un valore arbitrario in un intervallo stabilito, qualcuno cerca i valori massimi, minimi, medi. Se nel tuo database scrivono dati molti sistemi, non puoi trattarli tutti allo stesso modo. Potrebbe risultare che per ogni sistema sia necessario utilizzare un downsampling differente. E questo è complicato da realizzare.

In secondo luogo, VictoriaMetrics, come ClickHouse, è ottimizzato per lavorare su grandi volumi di dati grezzi, quindi può elaborare un miliardo di righe in meno di un secondo, se hai molti core nel tuo sistema. La scansione dei punti della serie temporale in VictoriaMetrics arriva a 50.000.000 di punti al secondo per core. E questa prestazione si scala con i core disponibili. Cioè, se hai 20 core, ad esempio, puoi scansionare un miliardo di punti al secondo. E questa caratteristica di VictoriaMetrics e ClickHouse riduce la necessità di downsampling.

Un'altra caratteristica è che VictoriaMetrics comprime efficacemente questi dati. La compressione in media in produzione va da 0,4 a 0,8 byte per punto. Ogni punto corrisponde a timestamp + valore. E viene compresso a meno di un byte in media.

Sergei. Ho una domanda. Qual è il minimo quant di tempo per la registrazione?

Un millisecondo. Recentemente abbiamo avuto una conversazione con altri sviluppatori di database per serie temporali. Per loro, il minimo quant di tempo è di un secondo. Anche in Graphite, ad esempio, è un secondo. In OpenTSDB è anch'esso un secondo. In InfluxDB si tratta di precisione al nanosecondo. In VictoriaMetrics è di un millisecondo, poiché in Prometheus è di un millisecondo. E VictoriaMetrics è stata sviluppata inizialmente come remote storage per Prometheus. Ma ora può salvare dati anche da altri sistemi.

La persona con cui ho parlato dice che hanno una precisione al secondo — per loro è sufficiente, perché dipende dal tipo di dati che vengono conservati nel database della serie temporali. Se si tratta di dati DevOps o dati dell'infrastruttura, dove li raccogli con un intervallo di 30 secondi o un minuto, allora la precisione al secondo è sufficiente, meno non è necessario. Ma se raccogli questi dati da sistemi di trading ad alta frequenza, allora è necessaria una precisione al nanosecondo.

La precisione millisecondo in VictoriaMetrics è adatta sia per il caso DevOps, sia per la maggior parte dei casi che ho menzionato all'inizio della presentazione. L'unica cosa per cui potrebbe non essere adatta è per i sistemi di trading ad alta frequenza.

Grazie! E un'altra domanda. Qual è la compatibilità in PromQL?

Compatibilità retroattiva completa. VictoriaMetrics supporta completamente PromQL. Inoltre, aggiunge ulteriori funzionalità avanzate su PromQL, chiamata MetricsQL. Per quanto riguarda queste funzionalità estese, c'è una presentazione su YouTube. Ho parlato al Monitoring Meetup in primavera a San Pietroburgo.

Canale Telegram VictoriaMetrics.

Solo gli utenti registrati possono partecipare al sondaggio. Accedi, per favore.