Programmering

TigerGraph: Den parallelle grafdatabase forklaret

Victor Lee er direktør for produktstyring hos TigerGraph.

Grafdatabaser udmærker sig ved at besvare komplekse spørgsmål om forhold i store datasæt. Men de rammer en mur - både hvad angår ydeevne og analysefunktioner - når datamængden bliver meget stor, og når svarene skal gives i realtid.

Det skyldes, at eksisterende grafteknologier har problemer med at indlæse store mængder data eller indtage data med hurtig ankomst i realtid. De kæmper også for at levere hurtig gennemgangshastighed. Mens dybere analyser kræver dybere gennemkørsel af grafen, sænkes dagens grafdatabaser typisk eller timeout efter to humle med traversal.

TigerGraph er en distribueret, indbygget grafberegningsplatform designet til at omgå disse begrænsninger. TigerGraphs native parallelle grafarkitektur og realtids dyblinkanalyser sigter mod at give følgende fordele:

  • Hurtigere dataindlæsning for at opbygge grafer hurtigt
  • Hurtigere udførelse af parallelle grafalgoritmer
  • Realtidsfunktion til streaming af opdateringer og indsatser ved hjælp af REST
  • Evne til at samle realtidsanalyser med offline offline databehandling
  • Evne til at skalere og skalere for distribuerede applikationer

I de efterfølgende afsnit vil vi tage et kort kig på, hvordan grafbearbejdning fungerer, undersøge fordelene ved dyblinkanalyser og løfte hætten på TigerGraph for at forstå, hvordan den kan levere dybe linkanalyser i realtid.

Grafgennemgang: Flere humle, mere indsigt

Hvorfor dyblinkanalyser? Fordi jo flere links du kan krydse (hop) i en graf, jo større indsigt opnår du. Overvej en hybrid viden og social graf. Hver node forbinder til hvad du kender og hvem du ved. Direkte links (et hop) afslører, hvad du ved. To humle afslører alt, hvad dine venner og bekendte ved. Tre humle? Du er på vej til at afsløre hvad alle sammen kender til.

Graffordelen er at kende forholdet mellem dataenhederne i datasættet, hvilket er hjertet i vidensopdagelse, modellering og forudsigelse. Hvert humle kan føre til en eksponentiel vækst i antallet af forbindelser og følgelig i mængden af ​​viden. Men deri ligger den teknologiske forhindring. Kun et system, der udfører humle effektivt og parallelt, kan levere realtids dyblink (multi-hop) analyser.

Et simpelt eksempel som personaliseret anbefaling i realtid afslører værdien og kraften ved at følge flere links i en graf:

"Kunder, der kunne lide det, du kunne lide, købte også disse varer."

Dette oversættes til en tre-hop-forespørgsel:

  1. Start med en person (dig), identificer varer, du har set / lide / købt.
  2. For det andet skal du finde andre mennesker, der har set / lide / købt disse varer.
  3. For det tredje skal du identificere yderligere varer købt af disse mennesker.

Person → produkt → (andre) personer → (andre) produkter

Ved hjælp af tidligere grafteknologi ville du kun være begrænset til to humle i større datasæt. TigerGraph udvider let forespørgslen til tre eller flere humle for at levere nøgleindsigt inden for meget store datasæt.

TigerGraphs realtids dyblinkanalyser

TigerGraph understøtter tre til mere end 10 humle gennemkørsel på tværs af en stor graf sammen med hurtig gennemgang af hastighed og dataopdateringer. Denne kombination af hastighed, dybe traversaler og skalerbarhed giver enorme fordele for flere brugssager.

En brugssag er forebyggelse af svig. En måde, hvorpå virksomheder opdager potentiel svig, er at finde forbindelser til kendte dårlige transaktioner. Start for eksempel fra en indgående kreditkorttransaktion, her er en vej til dårlige transaktioner:

Ny transaktion → kreditkort → kortindehaver → (andet) kreditkort → (andet) dårlige transaktioner

Som en grafforespørgsel bruger dette mønster fire humle til at finde forbindelser kun et kort væk fra den indgående transaktion. Dagens svindlere forsøger at skjule deres aktivitet gennem kredsløbssammenhæng mellem sig selv og kendt dårlig aktivitet eller dårlige skuespillere. For at opdage bedrageri nøjagtigt skal du udforske flere mulige mønstre og samle en mere holistisk opfattelse.

Med evnen til at afdække flere skjulte forbindelser er TigerGraph i stand til at minimere kreditkortsvindel. Dette gennemkørselsmønster gælder for mange andre brugssager - hvor du simpelthen kan erstatte kreditkorttransaktionen med en webklikhændelse, et telefonopkald eller en pengeoverførsel.

Oversigt over TigerGraph-systemet

Evnen til at trække dybe forbindelser mellem dataenheder i realtid kræver ny teknologi designet til skalering og ydeevne. Der er mange designbeslutninger, der arbejder sammen for at opnå TigerGraphs gennembrudshastighed og skalerbarhed. Nedenfor ser vi på disse designfunktioner og diskuterer, hvordan de fungerer sammen.

En indfødt graf

TigerGraph er en ren grafdatabase fra bunden. Dens datalager indeholder noder, links og deres attributter, periode. Nogle grafdatabaseprodukter på markedet er virkelig omslag bygget oven på et mere generisk NoSQL-datalager. Denne virtuelle grafstrategi har en dobbelt straf, når det kommer til ydeevne. For det første introducerer oversættelsen fra virtuel grafoperation til fysisk lageroperation noget ekstra arbejde. For det andet er den underliggende struktur ikke optimeret til grafoperationer.

Kompakt opbevaring med hurtig adgang

Vi beskriver ikke TigerGraph som en database i hukommelsen, fordi det at have data i hukommelsen er en præference, men ikke et krav. Brugere kan indstille parametre, der angiver, hvor meget af den tilgængelige hukommelse, der kan bruges til at holde grafen. Hvis den fulde graf ikke passer i hukommelsen, gemmes det overskydende på disken. Bedste ydeevne opnås, når den fulde graf naturligvis passer ind i hukommelsen.

Dataværdier gemmes i kodede formater, der effektivt komprimerer dataene. Kompressionsfaktoren varierer med grafstrukturen og dataene, men typiske kompressionsfaktorer er mellem 2x og 10x. Kompression har to fordele: For det første kan en større mængde grafdata passe i hukommelsen og i cachen. En sådan komprimering reducerer ikke kun hukommelsesfodaftrykket, men også CPU-cache-savner, hvilket fremskynder den samlede forespørgsel. For det andet reduceres hardwareomkostningerne for brugere med meget store grafer. For eksempel, hvis kompressionsfaktoren er 4x, kan en organisation muligvis tilpasse alle sine data i en maskine i stedet for fire.

Dekompression / dekodning er meget hurtig og gennemsigtig for slutbrugere, så fordelene ved kompression opvejer den lille tidsforsinkelse for kompression / dekompression. Generelt er dekompression kun nødvendig for at vise dataene. Når værdier bruges internt, kan de ofte forblive kodede og komprimerede.

Hash-indekser bruges til at henvise til noder og links. I Big-O-termer er vores gennemsnitlige adgangstid O (1), og vores gennemsnitlige indeksopdateringstid er også O (1). Oversættelse: adgang til en bestemt node eller et link i grafen er meget hurtig og forbliver hurtig, selv når grafen vokser i størrelse. Desuden er det meget hurtigt at opretholde indekset, når nye noder og links føjes til grafen.

Parallelisme og fælles værdier

Når hastighed er dit mål, har du to grundlæggende ruter: Udfør hver opgave hurtigere eller udfør flere opgaver på én gang. Den sidstnævnte vej er parallelisme. Mens han stræber efter at udføre hver opgave hurtigt, udmærker TigerGraph sig også ved parallelisme. Dens grafmotor bruger flere udførelsestråde til at krydse en graf.

Karakteren med grafforespørgsler er at "følge linkene." Start fra en eller flere noder. Se på de tilgængelige forbindelser fra disse noder, og følg disse forbindelser til nogle eller alle de tilstødende noder. Vi siger, at du lige har "krydset" et "hop". Gentag denne proces for at gå til den oprindelige nodes naboeres naboer, og du har krydset to humle. Da hver node kan have mange forbindelser, involverer denne to-hop-traversal mange stier for at komme fra startknudepunkterne til destinationsknudepunkterne. Grafer er en naturlig pasform til parallel, flertrådet udførelse.

En forespørgsel skal selvfølgelig gøre mere end bare at besøge en node. I et simpelt tilfælde kan vi tælle antallet af unikke to-hop naboer eller lave en liste over deres id'er. Hvordan beregner man et samlet antal, når du har flere parallelle tællere? Processen svarer til hvad du ville gøre i den virkelige verden: Bed hver tæller om at gøre sin del af verden, og kombiner derefter deres resultater til sidst.

Husk, at forespørgslen bad om antallet af enestående noder. Der er en mulighed for, at den samme node er blevet talt af to forskellige tællere, fordi der er mere end en sti til at nå den destination. Dette problem kan opstå, selv med design med enkelt gevind. Standardløsningen er at tildele en midlertidig variabel til hver node. Variablerne initialiseres til Falsk. Når en tæller besøger en node, indstilles denne nodes variabel til Sand, så andre tællere ikke ved at tælle den.

Lagrings- og behandlingsmotorer skrevet i C ++

Sprogvalg påvirker også ydeevne. TigerGraphs graflagermotor og processormotor er implementeret i C ++. Inden for familien af ​​processuelle sprog til generelle formål betragtes C og C ++ som lavere niveau sammenlignet med andre sprog som Java. Hvad dette betyder er, at programmører, der forstår, hvordan computerhardwaren udfører deres softwarekommandoer, kan træffe informerede valg for at optimere ydeevnen. TigerGraph er omhyggeligt designet til at bruge hukommelse effektivt og frigive ubrugt hukommelse. Omhyggelig hukommelsesstyring bidrager til TigerGraphs evne til at krydse mange links, både med hensyn til dybde og bredde, i en enkelt forespørgsel.

Mange andre grafdatabaseprodukter er skrevet i Java, som har fordele og ulemper. Java-programmer kører inde i en Java Virtual Machine (JVM). JVM tager sig af hukommelsesstyring og affaldsindsamling (frigør hukommelse, der ikke længere er nødvendig). Selvom dette er praktisk, er det svært for programmøren at optimere hukommelsesforbruget eller kontrollere, når ubrugt hukommelse bliver tilgængelig.

GSQL graf forespørgsel sprog

TigerGraph har også sit eget grafforespørgsel og opdateringssprog, GSQL. Mens der er mange gode detaljer om GSQL, vil jeg fokusere på to aspekter, der er nøglen til at understøtte effektiv parallel beregning: ACCUM-klausulen og akkumulatorvariabler.

Kernen i de fleste GSQL-forespørgsler er SELECT-sætningen, modelleret tæt efter SELECT-sætningen i SQL. SELECT-, FROM- og WHERE-klausulerne bruges til at vælge og filtrere et sæt links eller noder. Efter dette valg kan den valgfri ACCUM-sætning bruges til at definere et sæt handlinger, der skal udføres af hvert link eller tilstødende node. Jeg siger "udfør efter" snarere end "udfør videre", fordi konceptuelt er hvert grafobjekt en uafhængig beregningsenhed. Grafstrukturen fungerer som et massivt parallelt beregningsnet. Grafen er ikke kun din datalagring; det er også din forespørgsel eller analysemotor.

En ACCUM-klausul kan indeholde mange forskellige handlinger eller udsagn. Disse udsagn kan læse værdier fra grafobjekterne, udføre lokale beregninger, anvende betingede udsagn og planlægge opdateringer af grafen. (Opdateringer finder ikke sted, før forespørgslen er slut.)

For at understøtte disse distribuerede in-query beregninger giver GSQL-sproget akkumulatorvariabler. Akkumulatorer findes i mange varianter, men de er alle midlertidige (eksisterer kun under udførelse af forespørgsler), deles (tilgængelige for en hvilken som helst af udførelsestråde) og eksklusivt for hinanden (kun en tråd kan opdatere den ad gangen). For eksempel vil en simpel sumakkumulator blive brugt til at udføre optællingen af ​​alle ovennævnte naboers naboer. En sæt akkumulator ville blive brugt til at registrere ID'erne for alle disse naboers naboer. Akkumulatorer fås i to rækkevidde: global og per node. I det tidligere forespørgseleksempel nævnte vi behovet for at markere hver node som besøgt eller ej. Her vil akkumulatorer pr. Node blive brugt.

MPP beregningsmodel

For at gentage det, vi har afsløret ovenfor, er TigerGraph-grafen både en lagermodel og en beregningsmodel. Hver node og link kan tilknyttes en beregningsfunktion. Derfor fungerer TigerGraph som en parallel enhed til lagring og beregning samtidigt. Dette ville være uopnåeligt ved hjælp af et generisk NoSQL-datalager eller uden brug af akkumulatorer.

Automatisk opdeling

I nutidens big data-verden har virksomheder brug for deres databaseløsninger for at kunne skalere til flere maskiner, fordi deres data muligvis bliver for store til at blive lagret økonomisk på en enkelt server. TigerGraph er designet til automatisk at opdele grafdataene på tværs af en klynge af servere og stadig udføre hurtigt. Hash-indekset bruges til ikke kun at bestemme datalokaliseringen inden for serveren, men også hvilken server. Alle de links, der opretter forbindelse fra en given node, er gemt på den samme server. Computervidenskabsteori fortæller os, at det er meget langsomt at finde den bedste overordnede grafopdeling, hvis vi endda kunne definere "bedst", så vi prøver ikke. Vores standardtilstand er at bruge tilfældig hashing, som i de fleste tilfælde fungerer meget godt. TigerGraph-systemet understøtter også brugerstyret partitionering til brugere, der har et bestemt partitioneringsskema i tankerne.

Distribueret beregningstilstand