Jak vysvětlit svému manažérovi bezindexovou blízkost

Obrázek 1: Vysvětlení bezindexové blízkosti metaforou přímého souseda - rychlé vyhledávání fyzické paměti.

Bezindexová sousednost je nejdůležitější koncept, kterému musíme porozumět při učení o nativních grafových databázích. Nativní grafy mají velmi odlišné případy použití než nepřirozené databáze grafů. Nepřirozené grafové systémy jsou obvykle vrstveny nad jinými databázemi, které nejsou optimalizovány pro rychlý průchod grafů. Mít jasný mentální model těchto rozdílů je zásadní pro napsání jasného obchodního zdůvodnění jakéhokoli projektu Enterprise Knowledge Graph. Nestačí však jen pochopit bezindexovou přilehlost: musíte to vysvětlit svým netechnickým kolegům a hlavně svému manažerovi a komukoli jinému, kdo váš projekt schválí. Vyvinuli jsme metaforu pro vysvětlení bezindexové blízkosti, která se zdá být funkční. Říkáme tomu metafora „přímého souseda“. Tady to jde:

Předpokládejme, že žijete vedle roztomilého souseda (nechá jí říkat Ann). A v den Pi budete chtít vzít horký jablečný koláč, aby na ni zapůsobil. Napíšete Ann a zeptáte se jí, jestli má ráda Apple Pie a řekne „ano!“, Takže jí péct koláč a teď ho chcete rychle dostat do svého domu, zatímco je koláč ještě horký. Zde jsou kroky (viz obrázek 1):

  1. Vyjdeš ze dveří.
  2. Nasměrujete na Annin dům.
  3. Jdete přímo k Annině domu, což trvá asi 30 sekund, a dáte jí horký jablečný koláč - a ona to miluje! Šťastný konec!

Takto nativní databáze grafů vyhledávají sousední uzly v grafu. Dělají přímou procházku paměti. Tomu se říká poskakování ukazatele. Je to nejrychlejší způsob, jak se počítače musí dívat na vztahy. Pro práci s grafy mají přímé fyzické adresy RAM z každého uzlu všechny ostatní sousední uzly v grafu. Nejdůležitější je, že tyto ukazatele jsou vytvářeny při načítání dat, nikoli při dotazování dat. Obrázek 2 má „logický“ diagram tohoto grafu:

Obrázek 2: Logický model dvou sousedů.

Klíčem je to, že nativní grafové systémy nemusejí spolupracovat s jinými datovými strukturami nebo indexy, aby skákaly z jakéhokoli uzlu do sousedních uzlů. Při návrhu grafu explicitně přidáváte odkazy mezi logicky souvisejícími uzly. Tyto odkazy obsahují pevné adresy do sousedních uzlů.

Nyní porovnejme nativní grafickou architekturu s tím, jak by to mohly udělat relační databáze nebo jiné nenativní grafové databáze. To je popsáno na obrázku 3.

Obrázek 3: pomocí centrálního indexu a vyhledávání vyhledejte adresu sousedního domu.
  1. Vycházíte ze dveří, ale ve světě RDBMS máte zakázáno chodit po souvisejících položkách pomocí ukazatelů. Musíte jít do centrálního indexu.
  2. Procházka do centra do vládní budovy typu DMV, kde mají velmi dlouhou linii, táhnoucí se po blocích.
  3. Až se dostanete do řady a počkejte, až na vás přijde řada. Čekací doby se odhadují na 6 hodin.
  4. Když se dostanete na začátek řádku, jdete k čítači vyhledávacího agenta.
  5. Vyhledávací agent má seznam všech lidí ve vašem městě seřazených podle jejich adresy (nazývané index). Prohledávají seznam (pomocí algoritmu binárního vyhledávání). Problém je v tom, že ve vašem městě je spousta lidí a čím více lidí, tím déle vyhledávání trvá. Hledání se vrátí a konečně vám poskytnou GPS souřadnice domu vašeho souseda.
  6. Vezmete tyto GPS souřadnice, zadáte je do mapy svého mobilního telefonu a budete postupovat podle pokynů k Annině domu. Celkově se k vám dostanete 1 000krát ukazatelovým skokem (řekněme 8 hodin).
  7. Když se tam dostanete, koláč je studený. Na webu Neighbor.com vám dává nízké skóre čistého promotéra. Ona příspěvky: "Milý chlap, ale to trvá ho navždy doručit koláče".

Tento příběh shrnuje rozdíl mezi implementací grafové databáze v nativním grafu a nepřirozenými variacemi, které jsou vrstveny nad jinými databázemi. Nativní grafy berou data, která jsou logicky spojena pomocí oblouků nebo vztahů, a pevně připojují fyzické adresy RAM těchto položek do uzlu. Vyhledávání vztahů je rychlé! Související uzly jsou někdy dokonce uloženy vedle sebe v paměti, což maximalizuje šance, že data jsou již v mezipaměti CPU! Výsledkem je, že můžete „hopovat“ mezi zhruba milionem uzlů každou sekundu pro každé jádro, které máte na serveru. Pokud máte typický server se 16 jádry, můžete vyhodnotit 16 milionů chmele za sekundu. Pokud používáte server Amazon x1e.32xlarge s 128 jádry, můžete získat 128 milionů chmele za sekundu. A pro ty z vás, kteří mají rozpočty na úrovni NSA, můžete získat malý Cray Graph Engine s 8 192 jádry, které udělá 12,8 miliardy (Giga) Traversal Edges za sekundu (GTEPS) na benchmarku s grafem 500 SSSP.

Je třeba si uvědomit, že relační databáze jsou ironicky velmi pomalé při vyhledávání vztahů. Někdy se nazývají „řádkové obchody“, protože jejich primárním návrhovým cílem je rychlý přístup z jednoho řádku do druhého. Proč? Protože prvotní systémy COBOL, které čtou z děrných karet, čtou najednou jednu kartu. Byly navrženy tak, aby seskupily všechna pole ve svých řadách dohromady. Nakonec jsme zděděli návrhy plochých souborů COBOL a později jsme doplnili vyhledávání vztahů. Pokud tedy máte velký plochý soubor bez jakýchkoli vztahů, řádkové obchody jsou opravdu rychlé! A pro jednoduché ploché soubory nemusíte hledat vztahy pomocí funkce vyhledávání. Horší je, že každá relační operace JOIN je vyhledávání, které se obvykle zdvojnásobí, když zdvojnásobíte velikost databáze - což se nazývá operace O (log (n)) binárního vyhledávání. A čím více spojení, tím pomaleji se dostanete. Relační databáze vynikají při dotazech na malé datové sady, které mají jednotnou rovnou strukturu. Nativní grafové databáze zahrnují Neo4j, ArangoDB, OrientDB (nyní ve vlastnictví SAS) a TigerGraph.

Nechceme naznačovat, že jejich hodnota není pro vrstvení grafů v horní části jiných databází. Pokud nehledáte složité vzory ve velkých souborech dat, může být stále užitečné ukládat grafická data do vaší stávající infrastruktury a pomocí nástrojů vizualizace grafů zobrazit strukturu. Pokud má vaše společnost méně než 10 000 zaměstnanců, je prohlížení organizačních diagramů s daty z RDBMS v pořádku, pokud můžete psát dotazy SQL. Téma pro budoucí blogový příspěvek. Mohou existovat i jiné důvody, jako jsou problémy se zabezpečením nebo distribuovanými daty, které mohou zvýšit přitažlivost nepůvodních grafových systémů.

Abychom to shrnuli: relační databáze (nazývané řádkové obchody) mají primární cíl rychlý přístup k jednotným datům z jednoho řádku na druhý. Vyhledávání vztahů je považováno za sekundární cíl. U databáze grafů je rychlé vyhledávání vztahů vždy hlavním cílem. Vztahy jsou prvotřídním občanem.

Tento rozdíl má vliv na to, jak navrhujeme grafy. Na rozdíl od systémů RDBMS nenavrhujeme minimalizaci operací JOIN. Navrhujeme grafy, abychom minimalizovali RAM, takže všechny naše ukazatele se pěkně hodí do RAM. Přidávání spousty vztahů je nejen rychlé, ale také podporované!

Nakonec si pamatujeme, že neexistuje žádná ideální architektura pro ukládání všech typů grafických dat. Bezindexová sousednost také znamená, že pokud máte uzly s velmi velkým počtem vztahů (a.k.a. supernody), existuje mnoho odkazů, které bude třeba aktualizovat, když provedete změny. Například sociální síť s filmovými hvězdami, které mají miliony sledujících, bude vyžadovat miliony aktualizací, pokud budou odstraněny. Je pravda, že to může být vzácná událost na konkrétním typu sítě, ale něco, co je třeba zvážit při pohledu na kompromisy.

Funguje tato metafora? Máte další metaforu, která vysvětluje bezindexovou blízkost? Dejte mi vědět v komentářích.