TigerGraph: spiegazione del database a grafi paralleli

Victor Lee è direttore della gestione del prodotto presso TigerGraph.

I database a grafo eccellono nel rispondere a domande complesse sulle relazioni in grandi set di dati. Ma incontrano un muro, sia in termini di prestazioni che di capacità di analisi, quando il volume dei dati cresce molto e quando le risposte devono essere fornite in tempo reale.

Questo perché le tecnologie grafiche esistenti hanno problemi a caricare grandi quantità di dati o a importare dati che arrivano rapidamente, in tempo reale. Faticano anche a fornire una velocità di attraversamento veloce. Sebbene un'analisi più approfondita richieda un attraversamento più profondo del grafico, i database dei grafici odierni in genere rallentano o vanno in timeout dopo due salti di attraversamento.

TigerGraph è una piattaforma di elaborazione grafica distribuita e nativa progettata per aggirare queste limitazioni. L'architettura a grafi paralleli nativi di TigerGraph e l'analisi dei collegamenti diretti in tempo reale mirano a fornire i seguenti vantaggi:

  • Caricamento dei dati più veloce per creare grafici rapidamente
  • Esecuzione più rapida di algoritmi a grafi paralleli
  • Funzionalità in tempo reale per aggiornamenti e inserimenti in streaming utilizzando REST
  • Capacità di unificare l'analisi in tempo reale con l'elaborazione dei dati offline su larga scala
  • Capacità di scalabilità verticale e orizzontale per applicazioni distribuite

Nelle sezioni che seguono, daremo una breve occhiata al funzionamento dell'elaborazione dei grafici, esploreremo i vantaggi dell'analisi dei collegamenti profondi e solleveremo il cofano su TigerGraph per capire come sia in grado di fornire analisi dei collegamenti profondi in tempo reale.  

Attraversamento del grafico: più salti, più informazioni

Perché l'analisi dei link diretti? Perché più collegamenti puoi attraversare (saltare) in un grafico, maggiore è la visione che ottieni. Considera una conoscenza ibrida e un grafico sociale. Ogni nodo si collega a ciò che conosci e a chi conosci. I collegamenti diretti (un salto) rivelano ciò che sai. Due salti rivelano tutto ciò che sanno i tuoi amici e conoscenti. Tre luppoli? Stai per rivelare ciò che tutti sanno.

Il vantaggio del grafico è conoscere le relazioni tra le entità di dati nel set di dati, che è il cuore della scoperta della conoscenza, della modellazione e della previsione. Ogni salto può portare a una crescita esponenziale del numero di connessioni e, di conseguenza, della quantità di conoscenza. Ma qui sta l'ostacolo tecnologico. Solo un sistema che esegue i salti in modo efficiente e in parallelo può fornire analisi di deep link (multi-hop) in tempo reale.

Un semplice esempio come la raccomandazione personalizzata in tempo reale rivela il valore e il potere di seguire più collegamenti in un grafico:

"Anche i clienti a cui è piaciuto ciò che ti è piaciuto hanno acquistato questi articoli."

Questo si traduce in una query a tre hop:

  1. Partendo da una persona (tu), identifica gli oggetti che hai visto / apprezzato / acquistato.
  2. In secondo luogo, trova altre persone che hanno visualizzato / apprezzato / acquistato quegli articoli.
  3. Terzo, identificare gli articoli aggiuntivi acquistati da quelle persone.

Persona → prodotto → (altre) persone → (altri) prodotti

Utilizzando la tecnologia dei grafici precedente, saresti limitato a solo due salti in set di dati più grandi. TigerGraph estende facilmente la query a tre o più hop per fornire informazioni chiave all'interno di set di dati molto grandi.

Analisi dei collegamenti profondi in tempo reale di TigerGraph

TigerGraph supporta da tre a più di 10 salti di attraversamento su un grande grafico, insieme a una rapida velocità di attraversamento del grafico e aggiornamenti dei dati. Questa combinazione di velocità, attraversamenti profondi e scalabilità offre enormi vantaggi per diversi casi d'uso.

Un caso d'uso è la prevenzione delle frodi. Un modo in cui le aziende rilevano potenziali frodi è trovare collegamenti a transazioni errate note. Ad esempio, a partire da una transazione con carta di credito in entrata, ecco un percorso per transazioni errate:

Nuova transazione → carta di credito → titolare della carta → (altre) carte di credito → (altre) transazioni non valide

Come query di un grafico, questo modello utilizza quattro hop per trovare connessioni a una sola carta di distanza dalla transazione in entrata. I truffatori di oggi cercano di mascherare la loro attività attraverso collegamenti tortuosi tra loro e noti cattive attività o cattivi attori. Per rilevare le frodi in modo accurato, è necessario esplorare più modelli possibili e assemblare una visione più olistica.

Con la capacità di scoprire più connessioni nascoste, TigerGraph è in grado di ridurre al minimo le frodi con carte di credito. Questo modello di attraversamento si applica a molti altri casi d'uso, in cui puoi semplicemente sostituire la transazione con carta di credito con un evento di clic web, un record di telefonata o un trasferimento di denaro.

Panoramica del sistema TigerGraph

La capacità di tracciare connessioni profonde tra entità di dati in tempo reale richiede una nuova tecnologia progettata per la scalabilità e le prestazioni. Ci sono molte decisioni di progettazione che lavorano in modo cooperativo per raggiungere la velocità e la scalabilità rivoluzionarie di TigerGraph. Di seguito esamineremo queste caratteristiche di progettazione e discuteremo come funzionano insieme.

Un grafico nativo

TigerGraph è un database grafico puro, da zero. Il suo archivio dati contiene nodi, collegamenti e i loro attributi, punto. Alcuni prodotti di database a grafo sul mercato sono in realtà wrapper costruiti su un archivio dati NoSQL più generico. Questa strategia del grafico virtuale ha una doppia penalità quando si tratta di prestazioni. Innanzitutto, la conversione dall'operazione del grafico virtuale all'operazione di archiviazione fisica introduce del lavoro extra. In secondo luogo, la struttura sottostante non è ottimizzata per le operazioni sui grafici.

Archiviazione compatta con accesso rapido

Non descriviamo TigerGraph come un database in memoria, perché avere dati in memoria è una preferenza ma non un requisito. Gli utenti possono impostare parametri che specificano quanta memoria disponibile può essere utilizzata per conservare il grafico. Se il grafico completo non si adatta alla memoria, l'eccesso viene archiviato su disco. Le migliori prestazioni si ottengono quando l'intero grafico si adatta alla memoria, ovviamente. 

I valori dei dati vengono memorizzati in formati codificati che comprimono efficacemente i dati. Il fattore di compressione varia in base alla struttura e ai dati del grafico, ma i fattori di compressione tipici sono compresi tra 2x e 10x. La compressione ha due vantaggi: in primo luogo, una maggiore quantità di dati del grafico può essere contenuta nella memoria e nella cache. Tale compressione riduce non solo l'ingombro della memoria, ma anche i problemi di cache della CPU, accelerando le prestazioni complessive delle query. In secondo luogo, per gli utenti con grafici molto grandi, i costi dell'hardware sono ridotti. Ad esempio, se il fattore di compressione è 4x, un'organizzazione potrebbe essere in grado di adattare tutti i suoi dati in una macchina invece di quattro.

La decompressione / decodifica è molto veloce e trasparente per gli utenti finali, quindi i vantaggi della compressione superano il piccolo ritardo di compressione / decompressione. In generale, la decompressione è necessaria solo per visualizzare i dati. Quando i valori vengono utilizzati internamente, spesso possono rimanere codificati e compressi.

Gli indici hash vengono utilizzati per fare riferimento a nodi e collegamenti. In termini Big-O, il nostro tempo di accesso medio è O (1) e anche il nostro tempo medio di aggiornamento dell'indice è O (1). Traduzione: l'accesso a un particolare nodo o collegamento nel grafico è molto veloce e rimane veloce anche se il grafico aumenta di dimensioni. Inoltre, anche il mantenimento dell'indice quando vengono aggiunti nuovi nodi e collegamenti al grafico è molto veloce.

Parallelismo e valori condivisi

Quando la velocità è il tuo obiettivo, hai due percorsi di base: eseguire ogni attività più velocemente o eseguire più attività contemporaneamente. L'ultima strada è il parallelismo. Pur sforzandosi di svolgere rapidamente ogni attività, TigerGraph eccelle anche nel parallelismo. Il suo motore grafico utilizza più thread di esecuzione per attraversare un grafico.

La natura delle query sui grafici è "seguire i link". Inizia da uno o più nodi. Guarda le connessioni disponibili da quei nodi e segui quelle connessioni ad alcuni o tutti i nodi vicini. Diciamo che hai appena "attraversato" un "salto". Ripeti il ​​processo per andare ai vicini del nodo originale e hai attraversato due salti. Poiché ogni nodo può avere molte connessioni, questo attraversamento a due hop coinvolge molti percorsi per arrivare dai nodi di inizio ai nodi di destinazione. I grafici sono una scelta naturale per l'esecuzione parallela e multithread.

Una query ovviamente dovrebbe fare di più che visitare un nodo. In un caso semplice, possiamo contare il numero di vicini a due hop univoci o fare un elenco dei loro ID. Come si calcola un conteggio totale, quando si hanno più contatori paralleli? Il processo è simile a quello che faresti nel mondo reale: chiedi a ogni contatore di fare la sua parte di mondo, quindi combina i risultati alla fine.

Ricorda che la query richiedeva il numero di nodi univoci . Esiste la possibilità che lo stesso nodo sia stato contato da due contatori diversi, perché c'è più di un percorso per raggiungere quella destinazione. Questo problema può verificarsi anche con la progettazione a thread singolo. La soluzione standard è assegnare una variabile temporanea a ciascun nodo. Le variabili vengono inizializzate su False. Quando un contatore visita un nodo, la variabile di quel nodo è impostata su True, in modo che gli altri contatori sappiano di non contarla.

Motori di archiviazione ed elaborazione scritti in C ++

Anche le scelte linguistiche influiscono sulle prestazioni. Il motore di memorizzazione dei grafici e il motore di elaborazione di TigerGraph sono implementati in C ++. All'interno della famiglia dei linguaggi procedurali per scopi generali, C e C ++ sono considerati di livello inferiore rispetto ad altri linguaggi come Java. Ciò significa che i programmatori che comprendono come l'hardware del computer esegue i loro comandi software possono fare scelte informate per ottimizzare le prestazioni. TigerGraph è stato accuratamente progettato per utilizzare la memoria in modo efficiente e per liberare la memoria inutilizzata. Un'attenta gestione della memoria contribuisce alla capacità di TigerGraph di attraversare molti collegamenti, sia in termini di profondità che di ampiezza, in una singola query.

Molti altri prodotti di database a grafo sono scritti in Java, che ha pro e contro. I programmi Java vengono eseguiti all'interno di una Java Virtual Machine (JVM). La JVM si occupa della gestione della memoria e della garbage collection (liberando la memoria che non è più necessaria). Sebbene ciò sia conveniente, è difficile per il programmatore ottimizzare l'utilizzo della memoria o controllare quando la memoria inutilizzata diventa disponibile.

Linguaggio di query del grafico GSQL

TigerGraph ha anche un proprio linguaggio di interrogazione e aggiornamento dei grafici, GSQL. Sebbene ci siano molti dettagli interessanti su GSQL, mi concentrerò su due aspetti che sono fondamentali per supportare un calcolo parallelo efficiente: la clausola ACCUM e le variabili dell'accumulatore.

Il nucleo della maggior parte delle query GSQL è l'istruzione SELECT, modellata strettamente dopo l'istruzione SELECT in SQL. Le clausole SELECT, FROM e WHERE vengono utilizzate per selezionare e filtrare un insieme di collegamenti o nodi. Dopo questa selezione, la clausola ACCUM opzionale può essere utilizzata per definire un insieme di azioni che devono essere eseguite da ciascun collegamento o nodo adiacente. Dico "esegui per" piuttosto che "esegui" perché concettualmente, ogni oggetto grafico è un'unità di calcolo indipendente. La struttura del grafico si comporta come una mesh computazionale massicciamente parallela. Il grafico non è solo l'archiviazione dei dati; è anche il tuo motore di query o di analisi.

Una clausola ACCUM può contenere molte azioni o dichiarazioni differenti. Queste istruzioni possono leggere i valori dagli oggetti del grafico, eseguire calcoli locali, applicare istruzioni condizionali e pianificare gli aggiornamenti del grafico. (Gli aggiornamenti non vengono eseguiti fino al termine della query.)

Per supportare questi calcoli distribuiti in query, il linguaggio GSQL fornisce variabili di accumulazione. Gli accumulatori sono disponibili in molte versioni, ma sono tutti temporanei (esistenti solo durante l'esecuzione della query), condivisi (disponibili per qualsiasi thread di esecuzione) e si escludono a vicenda (solo un thread può aggiornarlo alla volta). Ad esempio, un semplice accumulatore di somma verrebbe utilizzato per eseguire il conteggio di tutti i vicini dei vicini menzionati sopra. Un set accumulator verrebbe utilizzato per registrare gli ID di tutti i vicini di questi vicini. Gli accumulatori sono disponibili in due ambiti: globale e per nodo. Nell'esempio di query precedente, abbiamo menzionato la necessità di contrassegnare ogni nodo come visitato o meno. Qui verrebbero utilizzati accumulatori per nodo.

Modello computazionale MPP

Per ribadire quanto abbiamo rivelato sopra, il grafo TigerGraph è sia un modello di archiviazione che un modello computazionale. Ogni nodo e collegamento può essere associato a una funzione di calcolo. Pertanto, TigerGraph agisce simultaneamente come unità parallela di archiviazione e calcolo. Ciò sarebbe irrealizzabile utilizzando un archivio dati NoSQL generico o senza l'uso di accumulatori.

Partizionamento automatico

Nel mondo dei big data di oggi, le aziende hanno bisogno delle loro soluzioni di database per essere in grado di scalare su più macchine, perché i loro dati potrebbero diventare troppo grandi per essere archiviati in modo economico su un singolo server. TigerGraph è progettato per partizionare automaticamente i dati del grafico su un cluster di server e continuare a funzionare rapidamente. L'indice hash viene utilizzato per determinare non solo la posizione dei dati all'interno del server, ma anche quale server. Tutti i collegamenti che si connettono da un dato nodo sono memorizzati sullo stesso server. La teoria dell'informatica ci dice che trovare il miglior partizionamento complessivo dei grafi, se potessimo anche definirlo "migliore", di solito è molto lento, quindi non ci proviamo. La nostra modalità predefinita consiste nell'utilizzare l'hashing casuale, che funziona molto bene nella maggior parte dei casi. Il sistema TigerGraph supporta anche il partizionamento diretto dall'utente per gli utenti che hanno in mente un particolare schema di partizionamento.

Modalità di calcolo distribuito