Programování

TigerGraph: Vysvětlení databáze paralelních grafů

Victor Lee je ředitelem produktového managementu ve společnosti TigerGraph.

Databáze grafů vynikají v odpovídání na složité otázky týkající se vztahů ve velkých souborech dat. Ale narazí na zeď - z hlediska výkonu i analytických schopností - když objem dat velmi vzroste a když odpovědi musí být poskytnuty v reálném čase.

Je to proto, že stávající technologie grafů mají potíže s načítáním velkého množství dat nebo s přijímáním rychle přicházejících dat v reálném čase. Rovněž se snaží dosáhnout vysoké rychlosti pojezdu. Zatímco hlubší analýzy vyžadují hlubší procházení grafu, dnešní databáze grafů obvykle zpomalí nebo vyprší po dvou pokusech o procházení.

TigerGraph je distribuovaná, nativní platforma pro výpočet grafů navržená tak, aby obešla tato omezení. Cílem nativní paralelní architektury grafů TigerGraph a analýzy přímých odkazů v reálném čase je poskytnout následující výhody:

  • Rychlejší načítání dat pro rychlé vytváření grafů
  • Rychlejší provádění algoritmů paralelního grafu
  • Možnost streamování aktualizací a vkládání pomocí REST v reálném čase
  • Schopnost sjednotit analytiku v reálném čase s rozsáhlým offline zpracováním dat
  • Schopnost škálovat a škálovat pro distribuované aplikace

V následujících částech se stručně podíváme na to, jak zpracování grafů funguje, prozkoumáme výhody analýzy přímých odkazů a zvedneme kapotu na TigerGraph, abychom pochopili, jak je schopna poskytovat analýzu přímých odkazů v reálném čase.

Traversal graph: More hops, more insight

Proč analýza přímých odkazů? Protože čím více odkazů můžete v grafu procházet (přeskakovat), tím větší přehled získáte. Zvažte hybridní znalostní a sociální graf. Každý uzel se připojuje k co víš a SZO víš. Přímé odkazy (jeden směr) odhalují, co víte. Dva chmele odhalí vše, co vaši přátelé a známí vědí. Tři chmele? Jste na cestě odhalit co každý ví.

Výhodou grafu je znalost vztahů mezi datovými entitami v datové sadě, což je jádro objevování znalostí, modelování a predikce. Každý skok může vést k exponenciálnímu nárůstu počtu spojení a odpovídajícím způsobem i množství znalostí. Ale v tom spočívá technologická překážka. Pouze systém, který provádí chmel efektivně a paralelně, může poskytovat analýzu hlubokých odkazů (multi-hop) v reálném čase.

Jednoduchý příklad, jako je osobní doporučení v reálném čase, odhaluje hodnotu a sílu sledování více odkazů v grafu:

"Zákazníci, kteří měli rádi to, co se vám líbilo, si také zakoupili tyto položky."

To se promítá do třískokového dotazu:

  1. Počínaje osobou (vámi) identifikujte položky, které jste si prohlíželi / lajkovali / koupili.
  2. Zadruhé, najděte další lidi, kteří si tyto položky prohlíželi / lajkovali / koupili.
  3. Za třetí, identifikujte další položky zakoupené těmito lidmi.

Osoba → produkt → (ostatní) osoby → (jiné) produkty

Při použití předchozí technologie grafů byste byli omezeni pouze na dva chmele ve větších souborech dat. TigerGraph snadno rozšiřuje dotaz na tři nebo více chmelů, aby poskytoval klíčové poznatky z velmi velkých datových sad.

Analýza přímých odkazů TigerGraph v reálném čase

TigerGraph podporuje tři až více než 10 přechodů přes velký graf, spolu s rychlou rychlostí procházení grafů a aktualizací dat. Tato kombinace rychlosti, hlubokých pohybů a škálovatelnosti nabízí obrovské výhody pro několik případů použití.

Jedním z případů použití je prevence podvodů. Jedním ze způsobů, jak podniky detekují potenciální podvody, je najít spojení se známými špatnými transakcemi. Například od příchozí transakce kreditní kartou je zde jedna cesta ke špatným transakcím:

Nová transakce → kreditní karta → držitel karty → (jiné) kreditní karty → (jiné) špatné transakce

Jako grafový dotaz používá tento vzor čtyři chmele k vyhledání spojení pouze jednu kartu od příchozí transakce. Dnešní podvodníci se pokoušejí maskovat svou činnost prostřednictvím souvislých spojení mezi sebou a známou špatnou činností nebo špatnými herci. Chcete-li přesně detekovat podvody, musíte prozkoumat několik možných vzorů a sestavit komplexnější pohled.

Díky schopnosti odhalit více skrytých připojení dokáže TigerGraph minimalizovat podvod s kreditní kartou. Tento vzor přechodu platí pro mnoho dalších případů použití - kde můžete transakci kreditní kartou jednoduše nahradit událostí kliknutí na webu, záznamem telefonního hovoru nebo převodem peněz.

Přehled systému TigerGraph

Schopnost vytvářet hluboká spojení mezi datovými entitami v reálném čase vyžaduje novou technologii určenou pro měřítko a výkon. Existuje mnoho návrhových rozhodnutí, která spolupracují na dosažení průlomové rychlosti a škálovatelnosti TigerGraph. Níže se podíváme na tyto designové funkce a probereme jejich vzájemnou spolupráci.

Nativní graf

TigerGraph je od základu čistá databáze grafů. Jeho úložiště dat obsahuje uzly, odkazy a jejich atributy, tečka. Některé produkty grafové databáze na trhu jsou skutečně obaly postavené na obecnějším úložišti dat NoSQL. Tato strategie virtuálních grafů má dvojí trest, pokud jde o výkon. Nejprve překlad z operace virtuálního grafu do operace fyzického úložiště přináší nějakou práci navíc. Za druhé, podkladová struktura není optimalizována pro operace grafů.

Kompaktní úložiště s rychlým přístupem

TigerGraph nepopisujeme jako databázi v paměti, protože mít data v paměti je preference, ale ne požadavek. Uživatelé mohou nastavit parametry, které určují, kolik dostupné paměti lze použít k uložení grafu. Pokud se celý graf nevejde do paměti, přebytek se uloží na disk. Nejlepšího výkonu se dosáhne, když se celý graf samozřejmě vejde do paměti.

Hodnoty dat jsou uloženy v kódovaných formátech, které data účinně komprimují. Faktor komprese se liší podle struktury grafu a dat, ale typické faktory komprese se pohybují mezi 2x a 10x. Komprese má dvě výhody: Za prvé, větší množství dat grafu se vejde do paměti a do mezipaměti. Taková komprese snižuje nejen paměťovou stopu, ale také vynechává mezipaměť CPU a zrychluje celkový výkon dotazu. Zadruhé, pro uživatele s velmi velkými grafy jsou sníženy náklady na hardware. Například pokud je faktor komprese 4x, pak organizace může být schopna umístit všechna svá data do jednoho stroje namísto čtyř.

Dekomprese / dekódování je pro koncové uživatele velmi rychlé a transparentní, takže výhody komprese převažují nad malým časovým zpožděním komprese / dekomprese. Dekomprese je obecně nutná pouze pro zobrazení dat. Pokud se hodnoty používají interně, často mohou zůstat kódované a komprimované.

Hash indexy se používají k odkazování na uzly a odkazy. Z hlediska Big-O je náš průměrný čas přístupu O (1) a náš průměrný čas aktualizace indexu je také O (1). Překlad: přístup ke konkrétnímu uzlu nebo odkazu v grafu je velmi rychlý a zůstává rychlý i při zvětšování velikosti grafu. Kromě toho je také velmi rychlé udržovat index při přidávání nových uzlů a odkazů do grafu.

Paralelismus a sdílené hodnoty

Když je vaším cílem rychlost, máte dvě základní trasy: Proveďte každý úkol rychleji nebo proveďte více úkolů najednou. Druhou možností je paralelismus. Zatímco se snaží rychle zvládnout každý úkol, TigerGraph také vyniká paralelismem. Jeho grafový modul používá k procházení grafu více podprocesů provádění.

Povahou grafových dotazů je „následovat odkazy“. Začněte od jednoho nebo více uzlů. Podívejte se na dostupná připojení z těchto uzlů a postupujte podle těchto připojení k některým nebo všem sousedním uzlům. Říkáme, že jste právě „prošli“ jedním „hopem“. Opakujte tento postup, abyste se dostali k sousedům sousedního původního uzlu, a vy jste překročili dva chmele. Vzhledem k tomu, že každý uzel může mít mnoho připojení, zahrnuje tento dvouskokový přechod mnoho cest, jak se dostat z počátečních uzlů do cílových uzlů. Grafy se přirozeně hodí pro paralelní provádění s více vlákny.

Dotaz by samozřejmě neměl dělat víc než jen navštívit uzel. V jednoduchém případě můžeme spočítat počet jedinečných sousedních dvou hopů nebo vytvořit seznam jejich ID. Jak lze vypočítat celkový počet, když máte více paralelních čítačů? Proces je podobný tomu, co byste dělali ve skutečném světě: Požádejte každý pult, aby udělal svůj podíl na světě, a nakonec výsledky zkombinujte.

Připomeňme, že dotaz požadoval počet unikátní uzly. Existuje možnost, že stejný uzel byl spočítán dvěma různými čítači, protože k dosažení tohoto cíle existuje více než jedna cesta. K tomuto problému může dojít i při návrhu s jedním závitem. Standardní řešení je přiřadit každému uzlu dočasnou proměnnou. Proměnné jsou inicializovány na False. Když jeden čítač navštíví uzel, proměnná tohoto uzlu je nastavena na True, aby ostatní čítače věděli, že jej nepočítají.

Úložiště a procesory napsané v C ++

Volba jazyka také ovlivňuje výkon. Nástroj pro ukládání grafů a modul pro zpracování grafů TigerGraph jsou implementovány v C ++. V rámci rodiny procedurálních jazyků pro všeobecné účely jsou C a C ++ považovány za nižší úrovně ve srovnání s jinými jazyky, jako je Java. To znamená, že programátoři, kteří rozumějí tomu, jak hardware počítače provádí jejich softwarové příkazy, mohou činit informovaná rozhodnutí k optimalizaci výkonu. TigerGraph byl pečlivě navržen tak, aby efektivně využíval paměť a uvolňoval nepoužívanou paměť. Pečlivá správa paměti přispívá k schopnosti TigerGraph procházet mnoho odkazů, a to jak z hlediska hloubky, tak šířky, v jediném dotazu.

Mnoho dalších grafických databázových produktů je napsáno v jazyce Java, který má klady i zápory. Programy Java běží uvnitř Java Virtual Machine (JVM). JVM se stará o správu paměti a uvolňování paměti (uvolnění paměti, která již není potřeba). I když je to pohodlné, je pro programátora obtížné optimalizovat využití paměti nebo řídit, kdy bude k dispozici nevyužitá paměť.

Dotazovací jazyk grafu GSQL

TigerGraph má také svůj vlastní jazyk pro dotazování a aktualizaci grafů, GSQL. I když existuje mnoho pěkných podrobností o GSQL, zaměřím se na dva aspekty, které jsou klíčem k podpoře efektivního paralelního výpočtu: klauzule ACCUM a proměnné akumulátoru.

Jádrem většiny dotazů GSQL je příkaz SELECT, který je modelován těsně po příkazu SELECT v SQL. Klauzule SELECT, FROM a WHERE se používají k výběru a filtrování sady odkazů nebo uzlů. Po tomto výběru lze volitelnou klauzuli ACCUM použít k definování sady akcí, které má provést každý odkaz nebo sousední uzel. Říkám spíše „provést“ než „provést“, protože koncepčně je každý objekt grafu samostatnou výpočetní jednotkou. Struktura grafu funguje jako masivně paralelní výpočetní síť. Graf není jen vaše úložiště dat; je to také váš dotaz nebo analytický modul.

Klauzule ACCUM může obsahovat mnoho různých akcí nebo příkazů. Tyto příkazy mohou číst hodnoty z objektů grafu, provádět místní výpočty, používat podmíněné příkazy a plánovat aktualizace grafu. (K aktualizaci nedojde, dokud dotaz neskončí.)

Pro podporu těchto distribuovaných výpočtů v dotazu poskytuje jazyk GSQL akumulační proměnné. Akumulátory přicházejí v mnoha příchutích, ale všechny jsou dočasné (existující pouze během provádění dotazu), sdílené (dostupné kterémukoli z podprocesů provádění) a vzájemně se vylučující (aktualizovat je může vždy pouze jedno vlákno). Například k výpočtu počtu všech sousedů sousedů uvedených výše by se použil jednoduchý akumulátor. Sada akumulátorů by se používala k zaznamenávání ID sousedů všech sousedů. Akumulátory jsou k dispozici ve dvou oborech: globální a na uzel. V dřívějším příkladu dotazu jsme zmínili potřebu označit každý uzel jako navštívený nebo ne. Zde by se používaly akumulátory na uzel.

MPP výpočetní model

Abychom zopakovali, co jsme odhalili výše, graf TigerGraph je jak úložný model, tak výpočetní model. Každý uzel a odkaz lze přidružit k výpočetní funkci. Proto TigerGraph funguje jako paralelní jednotka úložiště a výpočtu současně. To by bylo nemožné pomocí obecného úložiště dat NoSQL nebo bez použití akumulátorů.

Automatické rozdělení na oddíly

V dnešním světě velkých dat potřebují podniky svá databázová řešení, aby mohly škálovat na více počítačů, protože jejich data mohou růst příliš velká na to, aby byla ekonomicky uložena na jednom serveru. TigerGraph je navržen tak, aby automaticky rozdělil data grafu na klastr serverů a stále rychle fungoval. Index hash se používá k určení nejen datového umístění v rámci serveru, ale také který-server. Všechny odkazy, které se připojují z daného uzlu, jsou uloženy na stejném serveru. Teorie počítačové vědy nám říká, že nalezení nejlepšího celkového rozdělení grafů, pokud bychom mohli definovat „nejlepší“, je obvykle velmi pomalé, takže se o to nepokoušíme. Náš výchozí režim je použití náhodného hašování, které ve většině případů funguje velmi dobře. Systém TigerGraph podporuje také uživatelsky řízené dělení pro uživatele, kteří mají na mysli konkrétní schéma dělení.

Režim distribuovaného výpočtu

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