Programiranje

TigerGraph: Razložena baza vzporednih grafov

Victor Lee je direktor upravljanja izdelkov v podjetju TigerGraph.

Grafične zbirke podatkov se odlikujejo pri odgovarjanju na zapletena vprašanja o odnosih v velikih naborih podatkov. A udarijo v zid - tako glede zmogljivosti kot tudi pri zmožnostih analize - ko se količina podatkov zelo poveča in ko je treba odgovore posredovati sproti.

Razlog za to je, da imajo obstoječe tehnologije grafov težave z nalaganjem velikih količin podatkov ali s hitrim vnosom podatkov v realnem času. Prav tako se trudijo zagotoviti hitrost prečka. Medtem ko globlja analitika zahteva globlje prečkanje grafa, se današnje baze grafov po dveh preskokih običajno upočasnijo ali iztečejo.

TigerGraph je porazdeljena nativna grafična računalniška platforma, zasnovana za premagovanje teh omejitev. Izvorna arhitektura vzporednih grafov TigerGraph in analitika globokih povezav v realnem času želita zagotoviti naslednje prednosti:

  • Hitrejše nalaganje podatkov za hitro izdelavo grafov
  • Hitrejše izvajanje algoritmov vzporednih grafov
  • Zmogljivost v realnem času za pretakanje posodobitev in vstavkov z uporabo REST
  • Sposobnost poenotenja sprotne analitike z obsežno obdelavo podatkov brez povezave
  • Sposobnost razširitve in razširitve za porazdeljene aplikacije

V naslednjih razdelkih si bomo na kratko ogledali, kako deluje obdelava grafov, raziskali prednosti analitike globokih povezav in dvignili pokrov TigerGraph, da bomo razumeli, kako lahko v realnem času zagotavlja analitiko globokih povezav.

Grafični prehod: več hmelja, več vpogleda

Zakaj analitika globokih povezav? Ker več povezav, ki jih lahko prečkate (preskočite) v grafu, večji vpogled dosežete. Razmislite o hibridnem grafu znanja in družbe. Vsako vozlišče se poveže z kaj veste in WHO ti veš. Neposredne povezave (en skok) razkrivajo, kaj veste. Dva hmelja razkrijeta vse, kar znajo vaši prijatelji in znanci. Trije hmelj? Ste na poti, da razkrijete kaj vsi ve.

Prednost grafa je poznavanje odnosov med podatkovnimi entitetami v naboru podatkov, ki je jedro odkrivanja, modeliranja in predvidevanja znanja. Vsak poskok lahko privede do eksponentne rasti števila povezav in s tem tudi količine znanja. Toda v tem je tehnološka ovira. Samo sistem, ki izvaja hmelj učinkovito in vzporedno, lahko zagotavlja analitiko globokih povezav (multi-hop) v realnem času.

Preprost primer, kot je osebno priporočilo v realnem času, razkriva vrednost in moč sledenja več povezavam v grafu:

"Te izdelke so kupili tudi kupci, ki jim je bilo všeč, kar vam je bilo všeč."

To pomeni poizvedbo s tremi skoki:

  1. Od osebe (vas) določite predmete, ki ste si jih ogledali / všečkali / kupili.
  2. Drugič, poiščite druge, ki so si te izdelke ogledali / jih všečkali / kupili.
  3. Tretjič, določite dodatne izdelke, ki so jih kupili ti ljudje.

Oseba → izdelek → (drugi) osebe → (drugi) izdelki

Z uporabo prejšnje tehnologije grafov bi bili v večjih naborih podatkov omejeni na samo dva preskoka. TigerGraph poizvedbo enostavno razširi na tri ali več skokov, da zagotovi ključne vpoglede iz zelo velikih naborov podatkov.

Analiza globokih povezav TigerGraph v realnem času

TigerGraph podpira tri do več kot 10 skokov prečka čez velik graf, skupaj s hitro hitrostjo prečka grafa in posodobitvami podatkov. Ta kombinacija hitrosti, globokih prehodov in razširljivosti ponuja ogromne prednosti za več primerov uporabe.

Primer uporabe je preprečevanje goljufij. Eden od načinov, kako podjetja zaznajo morebitne prevare, je iskanje povezav do znanih slabih transakcij. Na primer, od dohodne transakcije s kreditno kartico je tu ena pot do slabih transakcij:

Nova transakcija → kreditna kartica → imetnik kartice → (druge) kreditne kartice → (druge) slabe transakcije

Kot graf poizvedbe ta vzorec uporablja štiri skoke, da najde povezave le eno kartico od dohodne transakcije. Današnji goljufi skušajo prikriti svojo dejavnost s krožnimi povezavami med seboj in znanimi slabimi dejavnostmi ali slabimi akterji. Če želite natančno odkriti goljufije, morate raziskati več možnih vzorcev in sestaviti bolj celovit pogled.

Z možnostjo odkrivanja več skritih povezav lahko TigerGraph zmanjša goljufije s kreditnimi karticami. Ta prehodni vzorec velja za številne druge primere uporabe - kjer lahko transakcijo s kreditno kartico preprosto nadomestite z dogodkom spletnega klika, zapisom telefonskega klica ali denarnim nakazilom.

Pregled sistema TigerGraph

Za sprotno globoko povezovanje podatkovnih entitet je potrebna nova tehnologija, zasnovana za obseg in zmogljivost. Obstaja veliko oblikovalskih odločitev, ki sodelujejo pri doseganju prebojne hitrosti in razširljivosti TigerGraph. Spodaj si bomo ogledali te oblikovne značilnosti in razpravljali o njihovem sodelovanju.

Izvorni graf

TigerGraph je čista zbirka podatkov o grafih od začetka. Njegova shramba podatkov vsebuje vozlišča, povezave in njihove atribute, obdobje. Nekateri izdelki podatkovnih baz grafov na trgu so res ovijalci, zgrajeni na podlagi bolj splošne shrambe podatkov NoSQL. Ta strategija virtualnega grafa ima dvojno kazen, ko gre za uspešnost. Prvič, prevajanje iz navidezne operacije grafa v operacijo fizičnega shranjevanja uvede nekaj dodatnega dela. Drugič, osnovna struktura ni optimizirana za grafične operacije.

Kompaktna shramba s hitrim dostopom

TigerGraph ne opisujemo kot zbirko podatkov v pomnilniku, ker je imeti podatke v pomnilniku prednost, ne pa tudi zahteva. Uporabniki lahko nastavijo parametre, ki določajo, koliko razpoložljivega pomnilnika se lahko uporabi za držanje grafa. Če celoten graf ne ustreza pomnilniku, se presežek shrani na disk. Najboljše rezultate dosežemo, ko se celoten graf seveda prilega v spomin.

Podatkovne vrednosti so shranjene v kodiranih oblikah, ki učinkovito stisnejo podatke. Faktor stiskanja se razlikuje glede na strukturo grafa in podatke, vendar so tipični faktorji stiskanja med 2x in 10x. Stiskanje ima dve prednosti: Prvič, večja količina grafičnih podatkov se lahko prilega v pomnilnik in v predpomnilnik. Takšno stiskanje zmanjša ne le odtis pomnilnika, temveč tudi napake v predpomnilniku CPU, kar pospeši splošno zmogljivost poizvedbe. Drugič, za uporabnike z zelo velikimi grafi se stroški strojne opreme zmanjšajo. Če je na primer faktor stiskanja 4x, potem bo organizacija morda lahko namesto v štirih postavila vse svoje podatke v en stroj.

Dekompresija / dekodiranje je zelo hitro in pregledno za končne uporabnike, zato so koristi stiskanja večje od majhne časovne zakasnitve za stiskanje / dekompresijo. Na splošno je dekompresija potrebna samo za prikaz podatkov. Kadar se vrednosti uporabljajo interno, lahko pogosto ostanejo kodirane in stisnjene.

Hash indeksi se uporabljajo za sklicevanje na vozlišča in povezave. V smislu Big-O je naš povprečni čas dostopa O (1) in tudi naš povprečni čas posodobitve indeksa je O (1). Prevod: dostop do določenega vozlišča ali povezave v grafu je zelo hiter in ostane hiter, tudi ko graf narašča. Poleg tega je tudi vzdrževanje indeksa, ko se na graf dodajo nova vozlišča in povezave, zelo hitro.

Vzporednost in skupne vrednote

Ko je vaš cilj hitrost, imate dve osnovni poti: vsako nalogo opravite hitreje ali več nalog hkrati. Slednja pot je paralelizem. Čeprav si prizadeva vsako nalogo opraviti hitro, se TigerGraph odlikuje tudi z vzporednostjo. Njegov grafski mehanizem za prečkanje grafa uporablja več izvedbenih niti.

Narava poizvedb v grafu je, da sledimo povezavam. Začnite z enim ali več vozlišči. Oglejte si razpoložljive povezave iz teh vozlišč in sledite tem povezavam z nekaterimi ali vsemi sosednjimi vozlišči. Pravimo, da ste pravkar "prevozili" en "skok". Ta postopek ponovite, da greste do sosedov sosedov prvotnega vozlišča in prešli ste dva hmelja. Ker ima lahko vsako vozlišče veliko povezav, ta dvosmerni prehod vključuje veliko poti do začetnih vozlišč do ciljnih vozlišč. Grafi so naravno primerni za vzporedno, večnitno izvajanje.

Poizvedba seveda ne bi smela narediti več kot le obisk vozlišča. V preprostem primeru lahko preštejemo število unikatnih sosedov z dvema skokoma ali sestavimo seznam njihovih osebnih dokumentov. Kako izračunamo skupno število, če imamo več vzporednih števcev? Postopek je podoben tistemu, kar bi počeli v resničnem svetu: prosite vsakega števca, naj naredi svoj del sveta, nato pa na koncu združite njihove rezultate.

Spomnimo se, da je poizvedba zahtevala število edinstven vozlišča. Obstaja možnost, da sta isto vozlišče štela dva različna števca, ker je do tega cilja več kot ena pot. Ta težava se lahko pojavi tudi pri enonitni izvedbi. Standardna rešitev je dodelitev začasne spremenljivke vsakemu vozlišču. Spremenljivke so inicializirane na False. Ko en števec obišče vozlišče, je spremenljivka tega vozlišča nastavljena na True, tako da drugi števci vedo, da ga ne štejejo.

Stroji za shranjevanje in obdelavo, napisani v jeziku C ++

Izbira jezika vpliva tudi na uspešnost. Mehanizem za shranjevanje grafov in mehanizem za obdelavo TigerGraph sta implementirana v jeziku C ++. V družini splošnih procesnih jezikov se C in C ++ štejeta za nižjo v primerjavi z drugimi jeziki, kot je Java. To pomeni, da lahko programerji, ki razumejo, kako računalniška strojna oprema izvaja njihove programske ukaze, sprejemajo premišljene odločitve za optimizacijo delovanja. TigerGraph je bil skrbno zasnovan za učinkovito uporabo pomnilnika in sprostitev neuporabljenega pomnilnika. Previdno upravljanje pomnilnika prispeva k sposobnosti TigerGraph-a, da v eni poizvedbi prečka številne povezave, tako po globini kot po širini.

Številni drugi izdelki z bazami grafov so napisani v Javi, ki ima dobre in slabe strani. Programi Java se izvajajo v navideznem računalniku Java (JVM). JVM skrbi za upravljanje pomnilnika in zbiranje smeti (sprostitev pomnilnika, ki ni več potreben). Čeprav je to priročno, programer težko optimizira porabo pomnilnika ali nadzoruje, kdaj bo na voljo neuporabljeni pomnilnik.

Jezik poizvedb grafov GSQL

TigerGraph ima tudi lasten jezik za poizvedovanje in posodabljanje grafov, GSQL. Čeprav obstaja veliko lepih podrobnosti o GSQL, se bom osredotočil na dva vidika, ki sta ključna za podpiranje učinkovitega vzporednega izračuna: stavek ACCUM in spremenljivke akumulatorja.

Jedro večine poizvedb GSQL je stavek SELECT, ki je natančno oblikovan po stavku SELECT v SQL. Določila SELECT, FROM in WHERE se uporabljajo za izbiro in filtriranje nabora povezav ali vozlišč. Po tej izbiri se lahko neobvezna klavzula ACCUM uporabi za določanje nabora dejanj, ki jih mora izvesti vsaka povezava ali sosednje vozlišče. Jaz rečem »izvedite z« in ne »izvedite naprej«, ker je konceptualno vsak objekt grafa neodvisna računska enota. Struktura grafa deluje kot masivno vzporedna računska mreža. Graf ni samo vaše shranjevanje podatkov; to je tudi vaš mehanizem za poizvedbe ali analitiko.

Klavzula ACCUM lahko vsebuje veliko različnih dejanj ali izjav. Ti stavki lahko berejo vrednosti iz objektov grafa, izvajajo lokalne izračune, uporabljajo pogojne stavke in načrtujejo posodobitve grafa. (Posodobitve se izvedejo šele, ko je poizvedba končana.)

Da bi podprl te porazdeljene izračune poizvedbe, jezik GSQL zagotavlja akumulatorske spremenljivke. Akumulatorji so različnih okusov, vendar so vsi začasni (obstajajo samo med izvajanjem poizvedbe), so v skupni rabi (na voljo kateri koli izvedbeni niti) in se medsebojno izključujejo (naenkrat ga lahko posodobi samo ena nit). Na primer, s preprostim akumulatorjem vsote se bo izvedlo štetje vseh zgoraj omenjenih sosedov sosedov. Za zbiranje ID-jev vseh sosedov teh sosedov bi uporabili nastavljeni akumulator. Akumulatorji so na voljo v dveh področjih: globalni in na vozlišče. V prejšnjem primeru poizvedbe smo omenili, da je treba vsako vozlišče označiti kot obiskano ali ne. Tu bi bili uporabljeni akumulatorji na vozlišče.

MPP računski model

Da ponovimo, kar smo razkrili zgoraj, je graf TigerGraph hkrati model shranjevanja in računski model. Vsako vozlišče in povezavo je mogoče povezati z računsko funkcijo. Zato TigerGraph deluje hkrati kot vzporedna enota za shranjevanje in računanje. To bi bilo nemogoče doseči z uporabo splošne shrambe podatkov NoSQL ali brez uporabe akumulatorjev.

Samodejna particija

V današnjem svetu velikih podatkov podjetja potrebujejo svoje rešitve baz podatkov, da se lahko razširijo na več strojev, ker lahko njihovi podatki postanejo preveliki, da bi jih lahko varčno shranili na enem strežniku. TigerGraph je zasnovan tako, da samodejno razdeli podatke grafa med skupino strežnikov in še vedno deluje hitro. Razpršeni indeks se uporablja ne samo za določanje lokacije podatkov znotraj strežnika, temveč tudi za kateri strežnik. Vse povezave, ki se povežejo z določenega vozlišča, so shranjene na istem strežniku. Teorija računalništva nam pove, da je iskanje najboljše splošne particije grafov, če bi sploh lahko opredelili "najboljšo", običajno zelo počasno, zato ne poskušamo. Naš privzeti način je uporaba naključnega razprševanja, ki v večini primerov deluje zelo dobro. Sistem TigerGraph podpira tudi uporabniško usmerjeno particioniranje za uporabnike, ki imajo v mislih določeno shemo particioniranja.

Način porazdeljenega računanja

$config[zx-auto] not found$config[zx-overlay] not found