Как да обясните на вашия мениджър без индекс

Фигура 1: Обясняване на присъединяване без индекс с метафората на прякото съседно ходене - бързо търсене на физическа памет.

Съседство без индекс е най-важната концепция, която трябва да разберем, когато научаваме за родните графични бази данни. Нативните графики имат много различни случаи на използване от не-родните бази данни. Системите, които не са местни графики, обикновено са наслоени върху други бази данни, които не са оптимизирани за бързо преминаване на графиката. Наличието на ясен мисловен модел на тези различия е от съществено значение за съставянето на ясна бизнес обосновка на всеки проект за графика на знанието на предприятието. Не е достатъчно обаче да разберете само присъединяването без индекс: трябва да можете да го обясните на вашите нетехнически колеги и най-важното на вашия мениджър и на всеки друг, който ще разреши вашия проект. Разработихме метафора за обяснение на присъединяването без индекс, което изглежда работи. Наричаме го метафората на „прякото съседно ходене“. Ето, започваме:

Да предположим, че живеете до сладка съседка (нека я наречем Ан). А в деня на Пи искаш да й вземеш горещ ябълков пай, за да я впечатлиш. Изпращате текст на Ан и я питате дали харесва Apple Pie и тя казва „да!“, Така че я изпечете пай и сега искате да го занесете бързо в къщата си, докато пайът е още горещ. И така, ето стъпките (вижте фигура 1):

  1. Излизаш през вратата.
  2. Посочвате към къщата на Ан
  3. Отивате директно до къщата на Ан, която отнема около 30 секунди, и й давате горещия ябълков пай - и тя го обича! Щастлив край!

Ето как родните бази от графики търсят съседни възли в графиката. Правят директно разходка на паметта. Това се нарича скачане на показалец. Това е най-бързият начин, по който компютрите трябва да гледат на отношенията. За работа графиките имат директни физически RAM адреси от всеки възел, всички останали съседни възли в графиката. Най-важното е, че тези указатели се създават, когато зареждате данни, а не когато заявявате данни. Фигура 2 има „логична” диаграма на тази графика:

Фигура 2: Логически модел на две съседи.

Ключът е, че родните графични системи не трябва да работят с никакви други структури данни или индекси, за да преминат от който и да е възел към съседните възли. Когато проектирате вашата графика, изрично добавяте връзки между логически свързани възли. Тези връзки съдържат фиксирани адреси към вашите съседни възли.

Сега нека сравним архитектурата на нативните графики с начина, по който релационните бази данни или други не-местни бази данни могат да правят това. Това е описано на фигура 3.

Фигура 3: използване на централен индекс и търсене за намиране на адреса на съседната къща.
  1. Излизате през вратата, но в света на RDBMS ви е забранено да ходите до свързани предмети чрез указатели. Трябва да отидете на Централния индекс.
  2. Разходка в центъра на правителствената сграда, подобна на DMV, където те имат много дълга линия, простираща се за блокове.
  3. Когато станете на линия и изчакате своя ред. Времето за изчакване се изчислява на 6 часа.
  4. Когато стигнете до предната част на линията, отивате до брояча на агента за търсене.
  5. Търсачът има списък на всички хора във вашия град, сортирани по техния адрес (наречен индекс). Те търсят списъка (използвайки двоичен алгоритъм за търсене). Проблемът е, че във вашия град има много хора и колкото повече хора има, толкова по-дълго отнема търсенето. Търсенето се връща и най-накрая ви дават GPS координатите на къщата на вашия съсед.
  6. Вземете тези GPS координати, въведете ги в картата на мобилния си телефон и следвате инструкциите към къщата на Ан. Общо, отнема ви 1000 пъти хоп на показалеца (да речем 8 часа), за да стигнете до там.
  7. Когато стигнете до там пайът е студен. Тя ви дава нисък нетен резултат за промоутър в Neighborhood.com. Тя публикува: „Хубав човек, но му е нужно завинаги да доставя пайове“.

Тази история обобщава разликата между реализацията на собствена графика на графична база данни и не-родните вариации, които са наслоени върху други бази данни. Нативните графики вземат данни, които са логически свързани чрез дъги или взаимоотношения и твърдо пренасят физическите RAM адреси на тези елементи в възела. Търсенето на връзки става бързо! Свързаните възли понякога дори се съхраняват един до друг в паметта, което увеличава максимално шансовете, че данните вече са в кеша на вашия процесор! В резултат на това можете да "скачате" между около милион възли всяка секунда за всяко ядро, което имате на вашия сървър. Ако имате типичен сървър с 16 ядра, можете да оценявате 16 милиона скока в секунда. Ако използвате сървър на Amazon x1e.32xlarge с 128 ядра, можете да получите 128 милиона скока в секунда. А за тези от вас с бюджети в мащаб на NSA, можете да получите малко Cray Graph Engine с 8,192 ядра, което ще направи 12,8 милиарда (Giga) Traversal Edges per Second (GTEPS) на графичните показатели за SSSP Graph500.

Нещото, което трябва да запомните е, че релационните бази данни, по ирония на съдбата, са много бавни при търсене на връзки. Те понякога се наричат ​​„магазини за редове“, тъй като основната им цел на дизайна е бърз достъп до редица. Защо? Защото ранните COBOL системи, които четат от перфокарти, четат по една карта наведнъж. Те са проектирани да групират всички полета в техните редове заедно. В крайна сметка наследявахме дизайна на плоски файлове на COBOL и преоборудваме връзките за връзки по-късно като последваща мисъл. Така че, ако имате голям плосък файл без никакви взаимоотношения, магазините за редове наистина са бързи! А за прости плоски файлове не е нужно да търсите взаимоотношения с помощта на функция за търсене. По-лошото е, че всяка релационна операция JOIN е търсене, което обикновено се удвоява, докато удвоите размера на вашата база данни - това, което се нарича O (log (n)) двоична операция за търсене. И колкото повече се присъединявате, толкова по-бавно ставате. Релационните бази данни превъзхождат заявки на малки набори от данни, които имат еднаква плоска структура. Базите данни за родните графи включват Neo4j, ArangoDB, OrientDB (сега е собственост на SAS) и TigerGraph.

Не искаме да подсказваме, че тяхната стойност не е наслоени графики в горната част на други бази данни. Ако не търсите сложни модели в големи масиви от данни, все още може да бъде полезно да съхранявате графичните данни във вашата съществуваща инфраструктура и да използвате инструменти за визуализация на графики, за да видите структурата. Ако вашата компания има под 10 000 служители, отколкото да гледате организационни схеми с данни от RDBMS, е добре, стига да можете да напишете SQL заявки, за да направите това. Тема за бъдеща публикация в блога. Възможно е да има и други причини като проблеми със сигурността или разпределени данни, които могат да направят не-родните графични системи по-привлекателни.

За да обобщим: релационните бази данни (наречени магазини за редове) имат основна цел бърз достъп до единни данни по ред. Търсенето на взаимоотношения се счита за второстепенна цел. С графичната база данни бързото търсене на взаимоотношения винаги е основна цел. Взаимоотношенията са първокласен гражданин.

Тази разлика оказва влияние върху начина, по който проектираме графики. За разлика от RDBMS системите, ние не проектираме да минимизираме операциите JOIN. Ние проектираме графики, за да минимизираме RAM, така че всичките ни указатели да се вписват добре в RAM. Добавянето на много отношения е не само бързо, но и се насърчава!

И накрая, нека си спомним, че няма една идеална архитектура за съхранение на всички видове графични данни. Съседство без индекс също означава, че ако имате възли с много голям брой връзки (a.k.a. supernodes), има много връзки, които ще трябва да бъдат актуализирани, когато правите промени. Например социална мрежа с филмови звезди, които имат милиони последователи, ще изисква милиони актуализации, ако бъдат премахнати. Разбира се, това може да е рядко събитие в конкретен тип мрежа, но нещо, което трябва да се има предвид, когато се разглеждат компромиси.

Работи ли тази метафора? Имате ли друга метафора, която обяснява присъединяването без индекс? Уведомете ме в коментарите.