Характеристики на проектиране на модел на данни за NoSQL

въведение

„Трябва да бягате възможно най-бързо, за да останете на място,
а за да стигнеш някъде, трябва да бягаш поне два пъти по-бързо!“
(в) Алиса в страната на чудесата

Преди време ме поканиха да изнеса лекция анализатори нашата компания по темата за проектиране на модели на данни, тъй като седейки върху проекти дълго време (понякога няколко години), губим от поглед какво се случва около нас в света на ИТ технологиите. В нашата компания (просто така се случва) много проекти не използват NoSQL бази данни (поне засега), така че в лекцията си отделно им обърнах внимание, използвайки примера на HBase и се опитах да ориентирам представянето на материала към тях които никога не са ги използвали са работили. По-специално, илюстрирах някои от характеристиките на дизайна на модела на данни, използвайки пример, който прочетох преди няколко години в статията „Въведение в дизайна на HB ase Schema“ от Amandeep Khurana. Когато анализирах примери, сравних няколко варианта за решаване на един и същ проблем, за да предам по-добре основните идеи на аудиторията.

Наскоро, „от нищо за правене“, си зададох въпроса (дългият майски уикенд в карантина е особено благоприятен за това), доколко теоретичните изчисления ще съответстват на практиката? Всъщност така се роди идеята за тази статия. Разработчик, който работи с NoSQL от няколко дни, може да не научи нищо ново от него (и следователно може веднага да пропусне половината статия). Но за анализаториЗа тези, които все още не са работили отблизо с NoSQL, мисля, че ще бъде полезно за придобиване на основно разбиране на характеристиките на проектирането на модели на данни за HBase.

Примерен анализ

Според мен, преди да започнете да използвате NoSQL бази данни, трябва да помислите внимателно и да претеглите плюсовете и минусите. Често проблемът най-вероятно може да бъде решен с помощта на традиционните релационни СУБД. Затова е по-добре да не използвате NoSQL без значителни причини. Ако все пак сте решили да използвате NoSQL база данни, тогава трябва да имате предвид, че подходите за проектиране тук са малко по-различни. Особено някои от тях може да са необичайни за тези, които преди това са се занимавали само с релационни СУБД (според моите наблюдения). Така че в „релационния“ свят обикновено започваме с моделиране на проблемната област и едва след това, ако е необходимо, денормализираме модела. В NoSQL ние трябва незабавно да вземе предвид очакваните сценарии за работа с данни и първоначално денормализиране на данните. Освен това има редица други разлики, които ще бъдат разгледани по-долу.

Нека разгледаме следния „синтетичен“ проблем, с който ще продължим да работим:

Необходимо е да се проектира структура за съхранение на списъка с приятели на потребителите на някаква абстрактна социална мрежа. За да опростим, ще приемем, че всички наши връзки са насочени (както в Instagram, а не в Linkedin). Структурата трябва да ви позволява ефективно да:

• Отговорете на въпроса дали потребител A чете потребител B (модел на четене)
• Разрешаване на добавяне/премахване на връзки в случай на абонамент/отписване на потребител A от потребител B (шаблон за промяна на данни)

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

user_id
friend_id

Вася
Петя

Вася
Оля

по-нататък за яснота и по-добро разбиране ще посочвам имена вместо идентификатори

В случая с HBase знаем, че:

• възможно е ефективно търсене, което не води до пълно сканиране на таблица изключително по ключ
  • всъщност, ето защо писането на познати на мнозина SQL заявки към такива бази данни е лоша идея; технически, разбира се, можете да изпратите SQL заявка с Joins и друга логика към HBase от същата Impala, но колко ефективно ще бъде...

Следователно сме принудени да използваме потребителския идентификатор като ключ. И първата ми мисъл по темата "къде и как да съхранявам личните карти на приятели?" може би идея да ги съхранявате в колони. Тази най-очевидна и „наивна“ опция ще изглежда нещо подобно (да го наречем Опция 1 (по подразбиране)за допълнителна справка):

RowKey
Високоговорители

Вася
1: Петя
2: Оля
3: Даша

Петя
1: Маша
2: Вася

Тук всеки ред отговаря на един мрежов потребител. Колоните имат имена: 1, 2, ... - според броя на приятелите, като в колоните се съхраняват идентификаторите на приятелите. Важно е да се отбележи, че всеки ред ще има различен брой колони. В примера на фигурата по-горе един ред има три колони (1, 2 и 3), а вторият има само две (1 и 2) - тук ние самите използвахме две свойства на HBase, които релационните бази данни нямат:

• възможност за динамична промяна на състава на колоните (добавяне на приятел -> добавяне на колона, премахване на приятел -> изтриване на колона)
• различните редове могат да имат различен състав на колони

Нека проверим нашата структура за съответствие с изискванията на задачата:

• Четене на данни: за да разберем дали Вася е абониран за Оля, ще трябва да извадим цялата линия чрез клавиша RowKey = „Вася“ и сортирайте стойностите на колоните, докато „срещнем“ Оля в тях. Или повторете стойностите на всички колони, „не отговарят“ на Оля и върнете отговора False;
• Редактиране на данни: добавяне на приятел: за подобна задача също трябва да извадим цялата линия използвайки клавиша RowKey = “Vasya”, за да изчислите общия брой на неговите приятели. Този общ брой приятели ни трябва, за да определим номера на колоната, в която трябва да запишем ID-то на новия приятел.
• Промяна на данни: изтриване на приятел:
  • Трябва да се извади цялата линия чрез клавиша RowKey = “Vasya” и сортирайте колоните, за да намерите тази, в която е записан приятелят, който трябва да бъде изтрит;
  • След това, след като изтрием приятел, трябва да „преместим“ всички данни в една колона, за да не получим „пропуски“ в тяхното номериране.

Нека сега оценим колко продуктивни ще бъдат тези алгоритми, които ще трябва да внедрим от страна на „условното приложение“, използвайки О-символизъм. Нека обозначим размера на нашата хипотетична социална мрежа като n. Тогава максималният брой приятели, които един потребител може да има, е (n-1). Можем допълнително да пренебрегнем това (-1) за нашите цели, тъй като в рамките на използването на О-символи това е маловажно.

• Четене на данни: необходимо е да извадите целия ред и да преминете през всички негови колони в лимита. Това означава, че горната оценка на разходите ще бъде приблизително O(n)
• Редактиране на данни: добавяне на приятел: за да определите броя на приятелите, трябва да преминете през всички колони на реда и след това да вмъкнете нова колона => O(n)
• Промяна на данни: изтриване на приятел:
  • Подобно на добавянето - трябва да преминете през всички колони в ограничението => O(n)
  • След като премахнем колоните, трябва да ги „преместим“. Ако приложите това „директно“, тогава в ограничението ще ви трябват до (n-1) операции. Но тук и по-нататък в практическата част ще използваме различен подход, който ще реализира „псевдоизместване“ за фиксиран брой операции - тоест за това ще се изразходва постоянно време, независимо от n. Това постоянно време (O(2), за да бъдем точни) може да бъде пренебрегнато в сравнение с O(n). Подходът е илюстриран на фигурата по-долу: просто копираме данните от „последната“ колона в тази, от която искаме да изтрием данни, и след това изтриваме последната колона:
    

Като цяло във всички сценарии получихме асимптотична изчислителна сложност от O(n).
Вероятно вече сте забелязали, че почти винаги трябва да прочетем целия ред от базата данни, а в два от три случая просто да преминем през всички колони и да изчислим общия брой приятели. Следователно, като опит за оптимизация, можете да добавите колона „брой“, която съхранява общия брой приятели на всеки потребител на мрежата. В този случай не можем да прочетем целия ред, за да изчислим общия брой приятели, а да прочетем само една колона „брой“. Основното нещо е да не забравяте да актуализирате „броя“ при манипулиране на данни. Че. ние се подобряваме Вариант 2 (брой):

RowKey
Високоговорители

Вася
1: Петя
2: Оля
3: Даша
брой: 3

Петя
1: Маша
2: Вася

брой: 2

В сравнение с първия вариант:

• Четене на данни: за да получите отговор на въпроса „Вася чете ли Оля?“ нищо не се е променило => O(n)
• Редактиране на данни: добавяне на приятел: Опростихме вмъкването на нов приятел, тъй като сега не е необходимо да четем целия ред и да обикаляме колоните му, а можем да получим само стойността на колоната „брой“ и т.н. веднага определете номера на колоната, за да вмъкнете нов приятел. Това води до намаляване на изчислителната сложност до O(1)
• Промяна на данни: изтриване на приятел: Когато изтриваме приятел, можем също да използваме тази колона, за да намалим броя на входно-изходните операции при „изместване“ на данните с една клетка наляво. Но необходимостта от итерация през колоните, за да се намери тази, която трябва да бъде изтрита, все още остава, така че => ​​O(n)
• От друга страна, сега, когато актуализираме данните, трябва да актуализираме колоната „count“ всеки път, но това отнема постоянно време, което може да бъде пренебрегнато в рамките на O-символите

Като цяло вариант 2 изглежда малко по-оптимален, но е по-скоро „еволюция вместо революция“. За да направим „революция“, ще ни трябват Вариант 3 (кол).
Нека обърнем всичко „с главата надолу“: ще назначим име на колона потребителски ИД! Какво ще бъде написано в самата колона вече не е важно за нас, нека бъде номер 1 (като цяло там могат да се съхраняват полезни неща, например групата „семейство/приятели/и т.н.“). Този подход може да изненада неподготвения „лаик“, който няма предишен опит в работата с NoSQL бази данни, но точно този подход ви позволява да използвате потенциала на HBase в тази задача много по-ефективно:

RowKey
Високоговорители

Вася
Петя: 1
Оля: 1
Даша: 1

Петя
Маша: 1
Вася: 1

Тук получаваме няколко предимства наведнъж. За да ги разберем, нека анализираме новата структура и оценим изчислителната сложност:

• Четене на данни: за да отговорите на въпроса дали Вася е абониран за Оля, достатъчно е да прочетете една колона „Оля“: ако има, тогава отговорът е True, ако не – False => O(1)
• Редактиране на данни: добавяне на приятел: Добавяне на приятел: просто добавете нова колона „ID на приятел“ => O(1)
• Промяна на данни: изтриване на приятел: просто премахнете колоната ID на приятел => O(1)

Както можете да видите, значително предимство на този модел на съхранение е, че във всички сценарии, от които се нуждаем, работим само с една колона, като избягваме да четем целия ред от базата данни и освен това изброяваме всички колони на този ред. Можем да спрем до тук, но...

Можете да бъдете озадачени и да отидете малко по-нататък по пътя на оптимизиране на производителността и намаляване на I/O операции при достъп до базата данни. Ами ако съхраним пълната информация за връзката директно в самия ключ на реда? Тоест, направете съставния ключ като userID.friendID? В този случай изобщо не е нужно да четем колоните на реда (Вариант 4 (ред)):

RowKey
Високоговорители

Вася.Петя
Петя: 1

Вася.Оля
Оля: 1

Вася.Даша
Даша: 1

Петя.Маша
Маша: 1

Петя.Вася
Вася: 1

Очевидно оценката на всички сценарии за манипулиране на данни в такава структура, както в предишната версия, ще бъде O(1). Разликата с вариант 3 ще бъде единствено в ефективността на I/O операциите в базата данни.

Е, последният „лък“. Лесно е да се види, че в опция 4 ключът на реда ще има променлива дължина, което може да повлияе на производителността (тук помним, че HBase съхранява данни като набор от байтове и редовете в таблиците са сортирани по ключ). Освен това имаме разделител, който може да се наложи да бъде обработен в някои сценарии. За да елиминирате това влияние, можете да използвате хешове от userID и friendID и тъй като и двата хеша ще имат постоянна дължина, можете просто да ги свържете, без разделител. Тогава данните в таблицата ще изглеждат така (Вариант 5 (хеш)):

RowKey
Високоговорители

dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Петя: 1

dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Оля: 1

dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Даша: 1

1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Маша: 1

1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Вася: 1

Очевидно алгоритмичната сложност на работа с такава структура в сценариите, които разглеждаме, ще бъде същата като тази на вариант 4 - тоест O(1).
Като цяло, нека обобщим всички наши оценки на изчислителната сложност в една таблица:

Добавяне на приятел
Проверявам приятел
Премахване на приятел

Опция 1 (по подразбиране)
О (п)
О (п)
О (п)

Вариант 2 (брой)
O (1)
О (п)
О (п)

Вариант 3 (колона)
O (1)
O (1)
O (1)

Вариант 4 (ред)
O (1)
O (1)
O (1)

Вариант 5 (хеш)
O (1)
O (1)
O (1)

Както можете да видите, варианти 3-5 изглеждат най-предпочитани и теоретично осигуряват изпълнението на всички необходими сценарии за манипулиране на данни в постоянно време. В условията на нашата задача няма изрично изискване за получаване на списък с всички приятели на потребителя, но при реални дейности по проекта би било добре ние, като добри анализатори, да „предвидим“, че може да възникне такава задача и „разстелете сламка“. Ето защо моите симпатии са на страната на вариант 3. Но е много вероятно в реален проект това искане да е вече решено с други средства, следователно, без обща визия за целия проблем, е по-добре да не се прави крайни заключения.

Подготовка на експеримента

Бих искал да тествам горните теоретични аргументи на практика - това беше целта на идеята, която се зароди през дългия уикенд. За да направите това, е необходимо да оцените скоростта на работа на нашето „условно приложение“ във всички описани сценарии за използване на базата данни, както и увеличаването на това време с увеличаване на размера на социалната мрежа (n). Целевият параметър, който ни интересува и който ще измерим по време на експеримента, е времето, прекарано от „условното приложение“ за извършване на една „бизнес операция“. Под „бизнес сделка“ имаме предвид едно от следните:

• Добавяне на един нов приятел
• Проверява се дали потребител A е приятел на потребител B
• Премахване на един приятел

По този начин, като се вземат предвид изискванията, посочени в първоначалното изявление, сценарият за проверка се очертава, както следва:

• Записване на данни. Произволно генерирайте първоначална мрежа с размер n. За да се доближим до „реалния свят“, броят на приятелите, които всеки потребител има, също е случайна променлива. Измерете времето, необходимо на нашето „условно приложение“ да запише всички генерирани данни в HBase. След това разделете полученото време на общия брой добавени приятели - така получаваме средното време за една „бизнес операция“
• Четене на данни. За всеки потребител създайте списък с „личности“, за които трябва да получите отговор дали потребителят е абониран за тях или не. Дължината на списъка = приблизително броя на приятелите на потребителя, като за половината от маркирани приятели отговорът трябва да е „Да“, а за другата половина – „Не“. Проверката се извършва в такъв ред, че отговорите „Да“ и „Не“ се редуват (т.е. във всеки втори случай ще трябва да преминем през всички колони на реда за опции 1 и 2). След това общото време за скрининг се разделя на броя на тестваните приятели, за да се получи средното време за скрининг за субект.
• Изтриване на данни. Премахнете всички приятели от потребителя. Освен това редът на изтриване е случаен (т.е. ние „разбъркваме“ оригиналния списък, използван за записване на данните). След това общото време за проверка се разделя на броя премахнати приятели, за да се получи средното време за проверка.

Сценариите трябва да се изпълняват за всяка от 5-те опции за модел на данни и за различни размери на социалната мрежа, за да се види как времето се променя, докато расте. В рамките на едно n връзките в мрежата и списъкът с потребители за проверка трябва, разбира се, да са еднакви за всичките 5 опции.
За по-добро разбиране по-долу е даден пример за генерирани данни за n= 5. Написаният „генератор“ произвежда три ID речника като изход:

• първият е за вмъкване
• второто е за проверка
• трето – за заличаване

{0: [1], 1: [4, 5, 3, 2, 1], 2: [1, 2], 3: [2, 4, 1, 5, 3], 4: [2, 1]} # всего 15 друзей

{0: [1, 10800], 1: [5, 10800, 2, 10801, 4, 10802], 2: [1, 10800], 3: [3, 10800, 1, 10801, 5, 10802], 4: [2, 10800]} # всего 18 проверяемых субъектов

{0: [1], 1: [1, 3, 2, 5, 4], 2: [1, 2], 3: [4, 1, 2, 3, 5], 4: [1, 2]} # всего 15 друзей

Както можете да видите, всички идентификатори над 10 000 в речника за проверка са точно тези, които със сигурност ще дадат отговор False. Вмъкването, проверката и изтриването на „приятели“ се извършва точно в последователността, посочена в речника.

Експериментът беше проведен на лаптоп, работещ под Windows 10, където HBase работеше в един Docker контейнер, а Python с Jupyter Notebook работеше в другия. На Docker бяха разпределени 2 процесорни ядра и 2 GB RAM. Цялата логика, като емулацията на „условното приложение“ и „тръбопровода“ за генериране на тестови данни и измерване на времето, е написана на Python. Библиотеката е използвана за работа с HBase щастлива база, за изчисляване на хешове (MD5) за опция 5 - hashlib

Като се вземе предвид изчислителната мощност на конкретен лаптоп, беше експериментално избрано стартиране за n = 10, 30, …. 170 – когато общото работно време на пълния цикъл на тестване (всички сценарии за всички опции за всички n) беше дори повече или по-малко разумно и подходящо за едно чаено парти (средно 15 минути).

Тук е необходимо да се отбележи, че в този експеримент ние не оценяваме основно абсолютните стойности на ефективността. Дори относително сравнение на различни две опции може да не е напълно правилно. Сега се интересуваме от естеството на промяната във времето в зависимост от n, тъй като като се вземе предвид горната конфигурация на „тестовия стенд“, е много трудно да се получат времеви оценки, „изчистени“ от влиянието на случайни и други фактори ( а такава задача не е поставена).

Резултат от експеримента

Първият тест е как се променя времето, прекарано в попълване на списъка с приятели. Резултатът е в графиката по-долу.

Варианти 3-5, както се очаква, показват почти постоянно време за „бизнес транзакция“, което не зависи от нарастването на размера на мрежата и незабележима разлика в производителността.
Вариант 2 също показва постоянно, но малко по-лошо представяне, почти точно 2 пъти спрямо варианти 3-5. И това не може да не радва, тъй като корелира с теорията - в тази версия броят на входно-изходните операции към/от HBase е точно 2 пъти по-голям. Това може да послужи като косвено доказателство, че нашият тестов стенд по принцип осигурява добра точност.
Вариант 1 също, както се очакваше, се оказва най-бавен и демонстрира линейно нарастване на времето, прекарано за взаимно добавяне към размера на мрежата.
Нека сега да разгледаме резултатите от втория тест.

Опции 3-5 отново се държат според очакванията - постоянно време, независимо от размера на мрежата. Опции 1 и 2 показват линейно увеличение на времето с увеличаване на размера на мрежата и подобна производителност. Освен това вариант 2 се оказва малко по-бавен - очевидно поради необходимостта от корекция и обработка на допълнителната колона „броене“, която става по-забележима с нарастването на n. Но все пак ще се въздържа от изводи, тъй като точността на това сравнение е сравнително ниска. В допълнение, тези съотношения (коя опция, 1 или 2, е по-бърза) се променят от цикъл на цикъл (като същевременно запазват естеството на зависимостта и „въртят врат и врат“).

Е, последната графика е резултат от тестване за премахване.

Тук отново няма изненади. Опции 3-5 извършват премахване в постоянно време.
Освен това, интересно е, че опции 4 и 5, за разлика от предишните сценарии, показват забележимо малко по-лоша производителност от опция 3. Очевидно операцията за изтриване на ред е по-скъпа от операцията за изтриване на колона, което като цяло е логично.

Варианти 1 и 2, както се очаква, демонстрират линейно увеличение на времето. В същото време опция 2 е постоянно по-бавна от опция 1 - поради допълнителната I/O операция за „поддържане“ на колоната за преброяване.

Общи изводи от експеримента:

• Опции 3-5 демонстрират по-голяма ефективност, тъй като се възползват от HBase; Освен това тяхната производителност се различава една спрямо друга с константа и не зависи от размера на мрежата.
• Разликата между опции 4 и 5 не е записана. Но това не означава, че опция 5 не трябва да се използва. Вероятно използваният експериментален сценарий, като се вземат предвид характеристиките на работата на тестовия стенд, не е позволил да бъде открит.
• Характерът на увеличаването на времето, необходимо за извършване на „бизнес операции“ с данни, като цяло потвърди получените по-рано теоретични изчисления за всички опции.

Епилог

Проведените груби експерименти не трябва да се приемат като абсолютна истина. Има много фактори, които не бяха взети под внимание и изкривиха резултатите (тези колебания са особено видими в графиките с малък размер на мрежата). Например скоростта на пестеливостта, която се използва от happybase, обемът и методът на внедряване на логиката, която написах в Python (не мога да твърдя, че кодът е написан оптимално и ефективно използва възможностите на всички компоненти), може би характеристиките на кеширането на HBase, фоновата активност на Windows 10 на моя лаптоп и др. Като цяло можем да приемем, че всички теоретични изчисления са доказали експериментално своята валидност. Е, или поне не беше възможно да ги опровергаем с такава „челна атака“.

В заключение, препоръки за всички, които тепърва започват да проектират модели на данни в HBase: абстрахирайте се от предишен опит в работата с релационни бази данни и запомнете „заповедите“:

• При проектирането ние изхождаме от задачата и моделите за манипулиране на данни, а не от модела на домейна
• Ефективен достъп (без пълно сканиране на таблица) – само по ключ
• Денормализация
• Различните редове могат да съдържат различни колони
• Динамичен състав на високоговорителите

Източник: www.habr.com