Victor Lee je riaditeľom produktového manažmentu v spoločnosti TigerGraph.
Databázy grafov vynikajú pri zodpovedaní zložitých otázok o vzťahoch vo veľkých množinách údajov. Narazili však na múr - pokiaľ ide o výkon aj analytické možnosti -, keď objem dát veľmi stúpne a keď musia byť odpovede poskytnuté v reálnom čase.
Je to tak preto, lebo existujúce technológie grafov majú problémy s načítaním veľkého množstva údajov alebo s prijímaním rýchlo prichádzajúcich údajov v reálnom čase. Tiež sa snažia dosiahnuť vysokú rýchlosť pojazdu. Zatiaľ čo hlbšia analýza vyžaduje hlbší prechod grafu, dnešné databázy grafov sa zvyčajne po dvoch prechodoch prechodom spomalia alebo vypršia.
TigerGraph je distribuovaná natívna platforma na výpočet grafov, ktorá je navrhnutá na prekonanie týchto obmedzení. Cieľom natívnej architektúry paralelného grafu TigerGraph a analýzy hlbokých odkazov v reálnom čase je poskytnúť nasledujúce výhody:
- Rýchlejšie načítanie údajov na rýchle vytváranie grafov
- Rýchlejšie vykonávanie algoritmov paralelného grafu
- Schopnosť streamovať aktualizácie a vloženia pomocou REST v reálnom čase
- Schopnosť zjednotiť analytiku v reálnom čase s rozsiahlym offline spracovaním údajov
- Schopnosť zväčšiť a zväčšiť pre distribuované aplikácie
V nasledujúcich častiach sa pozrieme na to, ako funguje spracovanie grafov, preskúmame výhody analýzy priamych odkazov a zdvihneme kapotu na TigerGraph, aby sme pochopili, ako dokáže analyzovať priame odkazy v reálnom čase.
Traversal graph: More hops, more insight
Prečo analýza priamych odkazov? Pretože čím viac odkazov môžete v grafe prechádzať (skákať), tým väčší prehľad získate. Zvážte hybridný znalostný a sociálny graf. Každý uzol sa pripája k čo vieš a SZO vieš. Priame odkazy (jeden krok) odhalia, čo viete. Dva chmele prezradia všetko, čo vaši priatelia a známi vedia. Tri chmele? Ste na ceste k odhaleniu čoho každý vie.
Výhodou grafu je poznanie vzťahov medzi dátovými entitami v množine údajov, ktoré je jadrom objavovania, modelovania a predpovedania znalostí. Každý skok môže viesť k exponenciálnemu rastu počtu spojení a podľa toho aj množstva vedomostí. V tom však spočíva technologická prekážka. Iba systém, ktorý vykonáva chmeľ efektívne a paralelne, môže poskytovať analytiku hlbokých odkazov (multi-hop) v reálnom čase.
Jednoduchý príklad, ako napríklad odporúčanie v reálnom čase, odhalí hodnotu a silu sledovania viacerých odkazov v grafe:
"Zákazníci, ktorým sa páčilo to, čo sa vám páčilo, si tieto položky aj kúpili."
To sa premieta do trojskokového dotazu:
- Počnúc osobou (vami) identifikujte položky, ktoré ste si prezerali / páčili / kúpili.
- Po druhé, nájdite ďalších ľudí, ktorí si tieto položky pozreli, obľúbili / kúpili.
- Po tretie, identifikujte ďalšie položky, ktoré títo ľudia kúpili.
Osoba → produkt → (iné) osoby → (iné) výrobky
Pri použití predchádzajúcej technológie grafov by ste boli obmedzený na iba dva chmele vo väčších množinách údajov. TigerGraph ľahko rozšíri dopyt na tri alebo viac skokov, aby priniesol kľúčové poznatky z veľmi veľkých súborov údajov.
Analýza priamych odkazov spoločnosti TigerGraph v reálnom čase
TigerGraph podporuje tri až viac ako 10 prechodov veľkého grafu spolu s vysokou rýchlosťou prechádzania grafu a aktualizáciou údajov. Táto kombinácia rýchlosti, hlbokých pohybov a škálovateľnosti ponúka obrovské výhody pre niekoľko prípadov použitia.
Jedným z prípadov použitia je prevencia podvodov. Jedným zo spôsobov, ako podniky odhalia potenciálne podvody, je nájsť spojenie so známymi zlými transakciami. Napríklad od prichádzajúcej transakcie kreditnou kartou je tu jedna cesta k zlým transakciám:
Nová transakcia → kreditná karta → držiteľ karty → (iné) kreditné karty → (iné) zlé transakcie
Ako grafový dopyt používa tento vzor štyri chmele na nájdenie spojení iba jednu kartu od prichádzajúcej transakcie. Dnešní podvodníci sa snažia zamaskovať svoju činnosť prostredníctvom vzájomných kontaktov medzi sebou a známymi zlými činnosťami alebo zlými aktérmi. Ak chcete podvod odhaliť presne, musíte preskúmať viac možných vzorov a získať holistickejší pohľad.
Vďaka schopnosti odhaliť viac skrytých spojení dokáže TigerGraph minimalizovať podvody s kreditnými kartami. Tento vzor prechodu sa týka mnohých ďalších prípadov použitia - keď môžete jednoducho nahradiť transakciu kreditnou kartou udalosťou kliknutia na webe, záznamom o telefonickom hovore alebo prevodom peňazí.
Prehľad systému TigerGraph
Schopnosť nadväzovať hlboké spojenia medzi dátovými entitami v reálnom čase si vyžaduje novú technológiu určenú pre rozsah a výkon. Existuje veľa dizajnových rozhodnutí, ktoré spolupracujú na dosiahnutí prielomovej rýchlosti a škálovateľnosti TigerGraph. Ďalej sa pozrieme na tieto dizajnové prvky a rozoberieme, ako spolupracujú.
Natívny graf
TigerGraph je od základu čistá databáza grafov. Jeho dátové úložisko obsahuje uzly, odkazy a ich atribúty, bodka. Niektoré produkty grafovej databázy na trhu sú skutočne obaly postavené na vrchu všeobecnejšieho úložiska údajov NoSQL. Táto stratégia virtuálnych grafov má dvojitý trest, pokiaľ ide o výkon. Po prvé, preklad z operácie virtuálneho grafu na operáciu fyzického ukladania prináša nejaké ďalšie práce. Po druhé, podkladová štruktúra nie je optimalizovaná pre operácie s grafmi.
Kompaktné úložisko s rýchlym prístupom
TigerGraph neopisujeme ako databázu v pamäti, pretože mať dáta v pamäti je preferencia, ale nie požiadavka. Používatelia môžu nastaviť parametre, ktoré určujú, koľko dostupnej pamäte sa môže použiť na uchovanie grafu. Ak sa celý graf nezmestí do pamäte, prebytok sa uloží na disk. Najlepší výkon sa dosiahne, keď sa celý graf samozrejme zmestí do pamäte.
Hodnoty údajov sú uložené v kódovaných formátoch, ktoré efektívne komprimujú údaje. Kompresný faktor sa líši podľa štruktúry grafu a údajov, ale typické kompresné faktory sú medzi 2 a 10 x. Kompresia má dve výhody: Po prvé, väčšie množstvo údajov grafu sa zmestí do pamäte a do medzipamäte. Takáto kompresia znižuje nielen pamäťovú stopu, ale aj vynechanie medzipamäte procesora a urýchľuje celkový výkon dotazu. Po druhé, pre používateľov s veľmi veľkými grafmi sa znižujú náklady na hardvér. Napríklad ak je kompresný faktor 4-násobný, potom môže byť organizácia schopná vložiť všetky svoje údaje do jedného zariadenia namiesto štyroch.
Dekompresia / dekódovanie je pre koncových používateľov veľmi rýchle a transparentné, takže výhody kompresie prevažujú nad malým časovým oneskorením kompresie / dekompresie. Dekompresia je vo všeobecnosti potrebná iba na zobrazenie údajov. Keď sa hodnoty používajú interne, často môžu zostať kódované a komprimované.
Hašovacie indexy sa používajú na odkazovanie na uzly a odkazy. Z hľadiska Big-O je náš priemerný čas prístupu O (1) a náš priemerný čas aktualizácie indexu je tiež O (1). Preklad: prístup ku konkrétnemu uzlu alebo odkazu v grafe je veľmi rýchly a zostáva rýchly aj pri zväčšovaní grafu. Okrem toho je tiež veľmi rýchle udržiavanie indexu pri pridávaní nových uzlov a odkazov do grafu.
Paralelizmus a spoločné hodnoty
Ak je vaším cieľom rýchlosť, máte k dispozícii dve základné trasy: Robte každú úlohu rýchlejšie alebo robte viac úloh naraz. Poslednou cestou je paralelizmus. Aj keď sa TigerGraph snaží rýchlo zvládnuť každú úlohu, vyniká tiež paralelizmom. Jeho grafický modul používa na prechádzanie grafom viac vlákien na vykonávanie.
Grafické dotazy majú povahu „nasledovania odkazov“. Začnite od jedného alebo viacerých uzlov. Pozrite sa na dostupné spojenia z týchto uzlov a postupujte podľa týchto spojení k niektorým alebo všetkým susedným uzlom. Hovoríme, že ste práve „prekonali“ jeden „hop“. Opakujte tento postup, aby ste sa dostali k susedom susedných objektov pôvodného uzla, a vy ste prešli dvoma chmeľmi. Pretože každý uzol môže mať veľa pripojení, tento dvojskokový prechod zahŕňa mnoho ciest na získanie zo začiatočných uzlov do cieľových uzlov. Grafy sa prirodzene hodia na paralelné, viacvláknové vykonávanie.
Dotaz by samozrejme nemal obsahovať iba návštevu uzla. V jednoduchom prípade môžeme spočítať počet jedinečných dvojskokových susedov alebo vytvoriť zoznam ich ID. Ako sa dá vypočítať celkový počet, keď máte viac paralelných počítadiel? Proces je podobný tomu, čo by ste robili v skutočnom svete: Požiadajte každý pult, aby určil svoj podiel na svete, a potom na konci skombinujte ich výsledky.
Pripomeňme, že v dotaze bol požadovaný počet jedinečný uzly. Existuje možnosť, že ten istý uzol bol spočítaný dvoma rôznymi počítadlami, pretože k uvedenému cieľu existuje viac ako jedna cesta. Tento problém sa môže vyskytnúť aj pri dizajne s jedným závitom. Štandardným riešením je priradiť dočasnú premennú každému uzlu. Premenné sú inicializované na hodnotu False. Keď jeden čítač navštívi uzol, premenná tohto uzla je nastavená na hodnotu True, aby ostatní počítadlá vedeli, že ju nemá počítať.
Stroje na ukladanie a spracovanie napísané v C ++
Možnosti jazyka majú tiež vplyv na výkon. Nástroj na ukladanie grafov a procesor spoločnosti TigerGraph sú implementované v C ++. V rámci rodiny procedurálnych jazykov na všeobecné účely sa jazyky C a C ++ považujú za úrovne nižšej úrovne v porovnaní s inými jazykmi, ako je Java. To znamená, že programátori, ktorí rozumejú tomu, ako hardvér počítača vykonáva ich softvérové príkazy, môžu robiť informované rozhodnutia na optimalizáciu výkonu. TigerGraph bol starostlivo navrhnutý tak, aby efektívne využíval pamäť a uvoľňoval nepoužívanú pamäť. Starostlivá správa pamäte prispieva k schopnosti TigerGraphu prechádzať mnohými odkazmi, čo sa týka hĺbky aj šírky, v jednom dotaze.
Mnoho ďalších grafických databázových produktov je napísaných v jazyku Java, ktorý má klady aj zápory. Programy Java bežia vo vnútri Java Virtual Machine (JVM). JVM sa stará o správu pamäte a odvoz odpadu (uvoľňuje pamäť, ktorá už nie je potrebná). Aj keď je to pohodlné, pre programátora je ťažké optimalizovať využitie pamäte alebo riadiť, keď bude k dispozícii nevyužitá pamäť.
Jazyk dotazu grafu GSQL
TigerGraph má tiež svoj vlastný jazyk pre dopytovanie a aktualizáciu grafov, GSQL. Aj keď existuje veľa pekných podrobností o GSQL, zameriam sa na dva aspekty, ktoré sú kľúčové pre podporu efektívneho paralelného výpočtu: klauzula ACCUM a premenné akumulátora.
Jadrom väčšiny dotazov GSQL je príkaz SELECT, ktorý je modelovaný tesne za príkazom SELECT v jazyku SQL. Klauzuly SELECT, FROM a WHERE sa používajú na výber a filtrovanie množiny odkazov alebo uzlov. Po tomto výbere sa môže voliteľná klauzula ACCUM použiť na definovanie súboru akcií, ktoré sa majú vykonať každým spojom alebo susedným uzlom. Hovorím skôr „vykonať“, ako „vykonať ďalej“, pretože koncepčne je každý objekt grafu samostatnou výpočtovou jednotkou. Štruktúra grafu funguje ako masívne paralelná výpočtová sieť. Graf nie je len vaše úložisko dát; je to tiež váš dopyt alebo analytický nástroj.
Klauzula ACCUM môže obsahovať veľa rôznych akcií alebo príkazov. Tieto príkazy môžu čítať hodnoty z objektov grafu, vykonávať lokálne výpočty, aplikovať podmienené príkazy a plánovať aktualizácie grafu. (Aktualizácie sa uskutočnia až po ukončení dotazu.)
Na podporu týchto distribuovaných výpočtov v dotaze poskytuje jazyk GSQL akumulačné premenné. Akumulátory majú veľa príchutí, ale všetky sú dočasné (existujú iba počas vykonávania dotazu), zdieľané (dostupné pre ktorékoľvek z vykonávacích vlákien) a navzájom sa vylučujú (aktualizovať ich môže naraz iba jedno vlákno). Napríklad na vykonanie počtu všetkých susedov susedov uvedených vyššie by sa použil jednoduchý akumulátor. Sada akumulátorov by sa použila na zaznamenanie ID všetkých susedov týchto susedov. Akumulátory sú k dispozícii v dvoch rozsahoch: globálny a na uzol. V predchádzajúcom príklade dotazu sme spomenuli potrebu označiť každý uzol ako navštívený alebo nie. Tu by sa použili akumulátory na každý uzol.
MPP výpočtový model
Aby sme zopakovali, čo sme odhalili vyššie, graf TigerGraph je ako úložný model, tak aj výpočtový model. Každý uzol a odkaz je možné priradiť k výpočtovej funkcii. Preto TigerGraph funguje ako paralelná jednotka ukladania a výpočtu súčasne. To by bolo nemožné pri použití všeobecného úložiska dát NoSQL alebo bez použitia akumulátorov.
Automatické rozdelenie na oddiely
V dnešnom svete veľkých dát potrebujú podniky svoje databázové riešenia, aby boli schopné škálovať na viac počítačov, pretože ich dáta môžu narásť príliš veľké na to, aby sa dali ekonomicky uložiť na jednom serveri. TigerGraph je navrhnutý tak, aby automaticky rozdelil dáta grafu na klaster serverov a stále rýchlo fungoval. Hašovací index sa používa na určenie nielen umiestnenia údajov v rámci servera, ale aj servera. Všetky odkazy, ktoré sa pripájajú z daného uzla, sú uložené na rovnakom serveri. Teória počítačovej vedy nám hovorí, že hľadanie najlepšieho celkového rozdelenia grafov, ak by sme mohli definovať aj to najlepšie, je zvyčajne veľmi pomalé, takže sa o to nepokúšame. Náš predvolený režim je použitie náhodného hashovania, ktoré vo väčšine prípadov funguje veľmi dobre. Systém TigerGraph podporuje tiež oddiely zamerané na používateľa pre používateľov, ktorí majú na mysli konkrétnu schému rozdelenia.
