Victor Lee er direktør for produktadministrasjon hos TigerGraph.
Grafdatabaser utmerker seg ved å svare på komplekse spørsmål om forhold i store datasett. Men de treffer en vegg - når det gjelder både ytelses- og analysefunksjoner - når datamengden blir veldig stor, og når svarene må gis i sanntid.
Det er fordi eksisterende grafteknologier har problemer med å laste inn store mengder data eller innta sanntidsdata i sanntid. De sliter også med å levere rask gjennomgangshastighet. Mens dypere analyser krever dypere traversering av grafen, reduseres dagens grafdatabaser vanligvis eller går ut etter to hopp med traversal.
TigerGraph er en distribuert, innfødt grafberegningsplattform designet for å omgå disse begrensningene. TigerGraphs integrerte parallelle grafarkitektur og sanntids dypkoblingsanalyse har som mål å gi følgende fordeler:
- Raskere datainnlasting for å bygge grafer raskt
- Raskere gjennomføring av parallelle grafalgoritmer
- Sanntidsfunksjon for streamingoppdateringer og innsatser ved hjelp av REST
- Evne til å forene sanntidsanalyse med storskala offline databehandling
- Evne til å skalere opp og skalere for distribuerte applikasjoner
I avsnittene som følger vil vi ta en kort titt på hvordan grafbehandlingen fungerer, utforske fordelene med dypkoblingsanalyse og løfte hetten på TigerGraph for å forstå hvordan den kan gi dypkoblingsanalyser i sanntid.
Grafgjennomgang: Mer humle, mer innsikt
Hvorfor dyplink-analyse? Fordi jo flere lenker du kan krysse (hopp) i en graf, jo større innsikt får du. Vurder en hybrid kunnskap og sosial graf. Hver node kobles til hva du vet og WHO du vet. Direkte lenker (ett humle) avslører hva du vet. To humler avslører alt det vennene dine og bekjente vet om. Tre humle? Du er på vei til å avsløre hva alle sammen vet.
Graffordelen er å kjenne forholdet mellom dataenhetene i datasettet, som er hjertet av oppdagelse, modellering og prediksjon av kunnskap. Hvert humle kan føre til en eksponentiell vekst i antall forbindelser og følgelig i mengden kunnskap. Men der ligger den teknologiske hindringen. Bare et system som utfører humle effektivt og parallelt, kan levere sanntids dypkoblingsanalyse (multi-hop).
Et enkelt eksempel som personlig tilpasset anbefaling i sanntid avslører verdien og kraften ved å følge flere lenker i en graf:
"Kunder som likte det du likte, kjøpte også disse varene."
Dette oversettes til et trehopp-spørsmål:
- Start fra en person (deg), identifiser gjenstander du så / likte / kjøpte.
- For det andre, finn andre personer som har sett på / likt / kjøpt varene.
- For det tredje, identifiser flere gjenstander som er kjøpt av disse menneskene.
Person → produkt → (andre) personer → (andre) produkter
Ved å bruke tidligere grafteknologi vil du være begrenset til bare to humle i større datasett. TigerGraph utvider spørringen enkelt til tre eller flere humle for å levere nøkkelinnblikk fra veldig store datasett.
TigerGraphs sanntids dyplinkanalyser
TigerGraph støtter tre til mer enn 10 hopp med traversal over en stor graf, sammen med rask traversal hastighet og dataoppdateringer. Denne kombinasjonen av hastighet, dype traversaler og skalerbarhet gir store fordeler for flere brukssaker.
En brukssak er forebygging av svindel. En måte som bedrifter oppdager potensiell svindel er å finne forbindelser til kjente dårlige transaksjoner. Start for eksempel fra en innkommende kredittkorttransaksjon, her er en vei til dårlige transaksjoner:
Ny transaksjon → kredittkort → kortinnehaver → (annet) kredittkort → (annet) dårlige transaksjoner
Som et diagramspørsmål bruker dette mønsteret fire humle for å finne forbindelser bare ett kort fra den innkommende transaksjonen. Dagens svindlere prøver å skjule aktiviteten deres gjennom sirkulære forbindelser mellom seg selv og kjent dårlig aktivitet eller dårlige skuespillere. For å oppdage svindel nøyaktig, må du utforske flere mulige mønstre og sette sammen et mer helhetlig syn.
Med muligheten til å avdekke flere skjulte forbindelser, er TigerGraph i stand til å minimere kredittkortsvindel. Dette gjennomkjøringsmønsteret gjelder mange andre brukstilfeller - der du ganske enkelt kan erstatte kredittkorttransaksjonen med en hendelse på nettklikk, en telefonsamtale eller en pengeoverføring.
Oversikt over TigerGraph-systemet
Evnen til å trekke dype forbindelser mellom dataenheter i sanntid krever ny teknologi designet for skalering og ytelse. Det er mange designbeslutninger som samarbeider for å oppnå TigerGraphs gjennombruddshastighet og skalerbarhet. Nedenfor vil vi se på disse designfunksjonene og diskutere hvordan de fungerer sammen.
En innfødt graf
TigerGraph er en ren grafdatabase, fra grunnen av. Datalageret har noder, lenker og attributter, periode. Noen grafdatabaseprodukter på markedet er virkelig omslag bygget på toppen av en mer generisk NoSQL-datalager. Denne virtuelle grafstrategien har en dobbel straff når det gjelder ytelse. For det første introduserer oversettelsen fra virtuell grafoperasjon til fysisk lagringsoperasjon litt ekstra arbeid. For det andre er den underliggende strukturen ikke optimalisert for grafoperasjoner.
Kompakt lagring med rask tilgang
Vi beskriver ikke TigerGraph som en database i minnet, fordi det å ha data i minnet er en preferanse, men ikke et krav. Brukere kan angi parametere som angir hvor mye av tilgjengelig minne som kan brukes til å holde grafen. Hvis den komplette grafen ikke passer i minnet, lagres det overskytende på disken. Beste ytelse oppnås selvfølgelig når hele grafen passer i minnet.
Dataverdiene lagres i kodede formater som effektivt komprimerer dataene. Kompresjonsfaktoren varierer med grafstrukturen og dataene, men typiske kompresjonsfaktorer er mellom 2x og 10x. Kompresjon har to fordeler: For det første kan en større mengde grafdata passe inn i minnet og i hurtigbufferen. Slik komprimering reduserer ikke bare minnefotavtrykket, men også CPU-hurtigbuffer, noe som øker den generelle spørringsytelsen. For det andre reduseres maskinvarekostnadene for brukere med veldig store grafer. For eksempel, hvis kompresjonsfaktoren er 4 ganger, kan en organisasjon være i stand til å plassere alle dataene på en maskin i stedet for fire.
Dekompresjon / dekoding er veldig rask og gjennomsiktig for sluttbrukere, så fordelene med komprimering oppveier den lille tidsforsinkelsen for komprimering / dekompresjon. Generelt sett er dekompresjon bare nødvendig for å vise dataene. Når verdier brukes internt, kan de ofte forbli kodet og komprimert.
Hash-indekser brukes til å referere til noder og lenker. I Big-O-termer er vår gjennomsnittlige tilgangstid O (1) og vår gjennomsnittlige indeksoppdateringstid er også O (1). Oversettelse: tilgang til en bestemt node eller lenke i grafen er veldig rask og forblir rask selv når grafen vokser i størrelse. Dessuten er det veldig raskt å opprettholde indeksen når nye noder og lenker legges til i grafen.
Parallelisme og delte verdier
Når hastighet er målet ditt, har du to grunnleggende ruter: Gjør hver oppgave raskere, eller gjør flere oppgaver samtidig. Sistnevnte vei er parallellisme. Mens du prøver å gjøre hver oppgave raskt, utmerker TigerGraph seg også med parallellitet. Grafmotoren bruker flere utføringstråder for å krysse en graf.
Karakteren til grafspørsmål er å "følge lenkene." Start fra en eller flere noder. Se på tilgjengelige tilkoblinger fra disse nodene, og følg disse tilkoblingene til noen eller alle nabolandene. Vi sier at du nettopp har "krysset" en "hop". Gjenta prosessen for å gå til den opprinnelige nodenes naboer, og du har gått gjennom to humle. Siden hver node kan ha mange forbindelser, involverer denne to-hopp-traversalen mange baner for å komme fra startnodene til destinasjonsnodene. Grafer passer naturlig for parallell, flertrådet utførelse.
Et spørsmål bør selvfølgelig gjøre mer enn bare å besøke en node. I et enkelt tilfelle kan vi telle antall unike tohopps naboer eller lage en liste over deres ID. Hvordan beregner man et totalt antall når du har flere parallelle tellere? Prosessen ligner på hva du ville gjort i den virkelige verden: Be hver teller gjøre sin del av verden, og kombiner deretter resultatene til slutt.
Husk at spørringen ba om antall unik noder. Det er en mulighet for at den samme noden er blitt talt av to forskjellige tellere, fordi det er mer enn en vei for å nå dette målet. Dette problemet kan oppstå selv med enkelttrådet design. Standardløsningen er å tilordne en midlertidig variabel til hver node. Variablene initialiseres til False. Når en teller besøker en node, settes den nodens variabel til True, slik at andre tellere ikke vet om å telle den.
Lagrings- og prosesseringsmotorer skrevet i C ++
Språkvalg påvirker også ytelse. TigerGraphs graflagringsmotor og prosesseringsmotor er implementert i C ++. Innenfor familien med prosessuelle språk for generelle formål, betraktes C og C ++ som lavere nivå sammenlignet med andre språk som Java. Hva dette betyr er at programmerere som forstår hvordan maskinvaren utfører programvarekommandoer, kan ta informerte valg for å optimalisere ytelsen. TigerGraph er nøye designet for å bruke minne effektivt og for å frigjøre ubrukt minne. Forsiktig minnehåndtering bidrar til TigerGraphs evne til å krysse mange lenker, både når det gjelder dybde og bredde, i et enkelt spørsmål.
Mange andre grafdatabaseprodukter er skrevet på Java, som har fordeler og ulemper. Java-programmer kjøres på en Java Virtual Machine (JVM). JVM tar seg av minnestyring og søppeloppsamling (frigjør minne som ikke lenger er nødvendig). Selv om dette er praktisk, er det vanskelig for programmereren å optimalisere minnebruk eller å kontrollere når ubrukt minne blir tilgjengelig.
GSQL graf spørringsspråk
TigerGraph har også sitt eget grafforespørsel og oppdateringsspråk, GSQL. Selv om det er mange fine detaljer om GSQL, vil jeg fokusere på to aspekter som er nøkkelen til å støtte effektiv parallell beregning: ACCUM-leddet og akkumulatorvariabler.
Kjernen i de fleste GSQL-spørsmål er SELECT-setningen, modellert nøye etter SELECT-setningen i SQL. SELECT, FROM og WHERE-leddene brukes til å velge og filtrere et sett med lenker eller noder. Etter dette valget kan den valgfrie ACCUM-setningen brukes til å definere et sett med handlinger som skal utføres av hver lenke eller tilstøtende node. Jeg sier "utfør etter" i stedet for "utfør på" fordi begrepsmessig er hvert grafobjekt en uavhengig beregningsenhet. Grafstrukturen fungerer som et massivt parallelt beregningsnett. Grafen er ikke bare datalagringen din; det er også spørringen eller analysemotoren din.
En ACCUM-klausul kan inneholde mange forskjellige handlinger eller utsagn. Disse utsagnene kan lese verdier fra grafobjektene, utføre lokale beregninger, bruke betingede utsagn og planlegge oppdateringer av grafen. (Oppdateringer finner ikke sted før spørringen er over.)
For å støtte disse distribuerte beregningene i spørringen, gir GSQL-språket akkumulatorvariabler. Akkumulatorer finnes i mange smaker, men de er alle midlertidige (eksisterer bare under spørringskjøring), deles (tilgjengelig for alle kjøringstrådene) og gjensidig utelukkende (bare en tråd kan oppdatere den om gangen). For eksempel vil en enkel sumakkumulator brukes til å utføre tellingen av alle naboens naboer nevnt ovenfor. En angitt akkumulator ville bli brukt til å registrere ID-ene til alle naboene. Akkumulatorer er tilgjengelige i to omfang: global og per node. I det tidligere spørreeksemplet nevnte vi behovet for å merke hver node som besøkt eller ikke. Her vil per-node akkumulatorer bli brukt.
MPP beregningsmodell
For å gjenta det vi har avslørt ovenfor, er TigerGraph-grafen både en lagringsmodell og en beregningsmodell. Hver node og lenke kan assosieres med en beregningsfunksjon. Derfor fungerer TigerGraph som en parallell enhet for lagring og beregning samtidig. Dette ville være uoppnåelig ved å bruke en generisk NoSQL-datalager eller uten bruk av akkumulatorer.
Automatisk partisjonering
I dagens store dataverden trenger bedriftene sine databaseløsninger for å kunne skalere ut til flere maskiner, fordi dataene deres kan bli for store til å kunne lagres økonomisk på en enkelt server. TigerGraph er designet for automatisk å partisjonere grafdataene over en klynge servere, og fremdeles utføre raskt. Hash-indeksen brukes til å bestemme ikke bare datalokasjonen innenfor serveren, men også hvilken server. Alle koblingene som kobles fra en gitt node, lagres på samme server. Informatikkteori forteller oss at det å finne den beste generelle grafdelingen, hvis vi til og med kunne definere "best", vanligvis er veldig treg, så vi prøver ikke. Vår standardmodus er å bruke tilfeldig hashing, som fungerer veldig bra i de fleste tilfeller. TigerGraph-systemet støtter også brukerstyrt partisjonering for brukere som har et bestemt partisjoneringsskjema i tankene.
