Въведение
«Трябва да бягам с всички сили, само за да остана на място,
а за да стигна някъде, трябва да бягам поне два пъти по-бързо!»
(с) Алиса в страната на чудесата
Няколко време назад ме помолиха да прочета лекция на анализаторите в нашата компания на тема проектиране на модели на данни, защото прекараваме дълго време в проекти (понякога по няколко години) и губим поглед над случващото се около нас в света на ИТ-технологиите. В нашата компания (така се случи) в много от проектите не се използват NoSQL бази данни (поне за сега), затова в лекцията си отделих известно внимание на тях, като използвах примера на HBase и се опитах да насоча съдържанието към тези, които никога не са работили с тях. По-специално, илюстрирах някои особености на проектирането на модели на данни чрез пример, който прочетох преди няколко години . Разглеждайки примери, сравнявах няколко варианта за решаване на една и съща задача, за да предам основните идеи на слушателите.
Наскоро, «от скука», си зададох въпроса (дългите майски празници в режим на карантина особено насърчават това), доколко теоретичните изводи ще съответстват на практиката? Всъщност така се роди идеята за тази статия. Разработчик, който работи с NoSQL от известно време, вероятно няма да научи нищо ново (и затова може веднага да пропусне половината от статията). Но за анализаторите, които все още не са работили подробно с NoSQL, вярвам, че тя ще бъде полезна за придобиване на основни познания за особеностите на проектиране на модели на данни за HBase.
Разбор на примера
Според мен, преди да започнете да използвате NoSQL бази данни, е необходимо да помислите добре и да прецените "за" и "против". Често задачата може да бъде решена и с традиционни релационни СУБД. Затова е по-добре да не използвате NoSQL без значителни основания. Ако все пак е взето решение да се използва NoSQL база данни, трябва да се има предвид, че подходите при проектирането тук са малко различни. Особено някои от тях могат да бъдат необичайни за тези, които преди това са работили само с релационни СУБД (по моите наблюдения). В "релационния" свят обикновено започваме с моделирането на предметната област, и след това, при необходимост, извършваме денормализация на модела. В NoSQL обаче веднага трябва да вземем предвид предвидените сценарии за работа с данни и първоначално да денормализираме данните. Освен това има и редица други разлики, за които ще бъде написано по-долу.
Нека разгледаме следната "синтетична" задача, с която ще работим по-нататък:
Необходимо е да проектираме структура за съхранение на списък с приятели на потребителите на някаква абстрактна социална мрежа. За опростяване ще приемем, че всички връзки са насочени (както в Instagram, а не в Linkedin). Структурата трябва да позволява ефективно:
- Да отговори на въпроса, чете ли потребител А потребител Б (шаблон за четене)
- Да позволява добавяне/премахване на връзки в случай на абониране/отпишане на потребител А от потребител Б (шаблон за промяна на данни)
Разбира се, има много варианти за решаване на задачата. В обикновена релационна БД, вероятно просто бихме направили таблица с връзки (възможно е да е типизирана, ако например е необходимо да се съхранява потребителска група: семейство, работа и т.н., в която влиза този "приятел"), а за оптимизация на скоростта на достъп бихме добавили индекси/партициониране. Вероятно финалната таблица би изглеждала приблизително така:
user_id
friend_id
Вася
Петя
Вася
Оля
тук и по-долу за яснота и по-добро разбиране, вместо ID ще посочвам имената
В случая с HBase знаем, че:
- ефективно търсене, което не води до full table scan, е възможно изключително по ключ
- Собствено, затова писането на познати на много SQL-запитвания към подобни бази е лоша идея; технически, разбира се, можете да изпратите SQL-запитване с Join-ове и друга логика в HBase от същата Impala, но колко ефективно ще бъде това...
Затова ID на потребителя сме принудени да използваме като ключ. А първата мисъл по темата "къде и как да съхраним ID на приятелите?" може да бъде идеята за съхранение на тях в колони. Този най-очевиден и "наивен" вариант ще изглежда по този начин (нека го наречем Вариант 1 (default), за да можем по-късно да се позоваваме на него):
RowKey
Колони
Вася
1: Петя
2: Оля
3: Даша
Петя
1: Маша
2: Вася
Тук всяка ред correspond на един потребител от мрежата. Колоните имат имена: 1, 2, … — колкото на приятелите, и в колоните се съхраняват ID на приятелите. Важно е да се отбележи, че всяка редица ще има различен брой колони. В примера на изображението по-горе, една редица има три колони (1, 2 и 3), а втората – само две (1 и 2) – тук самите ние използваме две свойства на HBase, които нямат релационните БД:
- възможността динамично да се променя съставът на колоните (добавяме приятел -> добавяме колона, изтриваме приятел -> изтриваме колона)
- различен състав на колоните за различни редици
Нека проверим нашата структура за съответствие на изискванията на задачата:
- Четене на данни: за да разберем дали Вася е абониран за Оля, ще трябва да извадим цялата редица по ключа RowKey = "Вася" и да прегледаме стойностите на колоните, докато не "срещнем" в тях Оля. Или да прегледаме стойностите на всички колони, "да не срещнем" Оля и да върнем отговор False;
- Промяна на данни: добавяне на приятел: за подобна задача ще ни трябва също да изтеглим цялата редица по ключа RowKey = "Вася", за да преброим общия брой на неговите приятели. Това общо количество приятели е необходимо, за да определим номера на колоната, в която да запишем ID на новия приятел.
- Промяна на данни: изтриване на приятел:
- Необходимо е да изтеглим цялата редица по ключа RowKey = "Вася" и да прегледаме колоните, за да намерим тази, в която е записан изтриваният приятел;
- След това, след изтриването на приятеля, трябва да "преместим" всичките данни с една колона, за да не получим "разриви" в тяхната нумерация.
Нека сега оценим, колко производителни ще бъдат данните алгоритми, които трябва да реализираме от страна на "условно приложение", използвайки . Нека обозначим размера на нашата хипотетична социална мрежа като n. Тогава максималният брой приятели на един потребител може да бъде (n-1). На (-1) можем да пренебрегнем за нашите цели, тъй като в контекста на използването на O-символиката това е незначително.
- Четене на данни: необходимо е да извадим цялата редица и да преминем през всичките й колони в предел. Следователно горната оценка на разходите ще бъде приблизително O(n)
- Промяна на данни: добавяне на приятел: за определяне на броя на приятелите е необходимо да преминем през всички колони на реда, след което да вставим нова колона => O(n)
- Промяна на данни: изтриване на приятел:
- По подобие на добавянето – необходимо е в предел да преминем през всички колони => O(n)
- След изтриване на колоните, трябва да ги „преместим“. Ако реализираме това „открито“, то в предел ще изисква още до (n-1) операции. Но ние тук и по-нататък в практическата част ще приложим различен подход, който ще реализира „псевдо-преместване“ за фиксирано количество операции – тоест времето, което ще отнеме, ще бъде константно независимо от n. Тази константна стойност (ако бъдем точни, то O(2)) в сравнение с O(n) може да се пренебрегне. Подходът е илюстриран на изображението по-долу: просто копираме данните от „последната“ колона в онова, от което трябва да изтрием данни, след което изтриваме последната колона:
В заключение, във всички сценарии получихме асимптотична изчислителна сложност O(n).
Вероятно вече сте забелязали, че почти винаги трябва да извадим от базата цялата редица, като в два от трите случая това се прави само, за да преминем през всички колони и да преброим общия брой приятели. Затова като опит за оптимизация можем да добавим колона „count“, в която да се съхранява общият брой приятели на всеки потребител на мрежата. В този случай можем да не извеждаме цялата редица за преброяване на общия брой приятели, а да прочетем само една колона „count“. Важно е да не забравяме да актуализираме „count“ при манипулация с данните. Така получаваме подобрено Опция 2 (count):
RowKey
Колони
Вася
1: Петя
2: Оля
3: Даша
count: 3
Петя
1: Маша
2: Вася
count: 2
В сравнение с първата опция:
- Четене на данни: за получаване на отговор на въпроса „Чита ли Васил Оля?“ нищо не се е променило => O(n)
- Промяна на данни: добавяне на приятел: Оптимизирахме добавянето на нов приятел, тъй като вече не е необходимо да изчитаме цял ред и да преминаваме през колоните, а можем да получим само стойността на колоната «count» и така веднага да определим номера на колоната за добавяне на нов приятел. Това води до намаляване на изчислителната сложност до O(1)
- Промяна на данни: изтриване на приятел: При изтриването на приятел също можем да се възползваме от тази колона, за да намалим броя на входно-изходните операции при «преместването» на данните с една клетка наляво. Но необходимостта от преминаване през колоните за търсене на онова, което трябва да бъде изтрито, все още остава, затова => O(n)
- От друга страна, сега, когато обновяваме данните, е необходимо всеки път да обновяваме и колоната «count», но за това се изразходва константно време, което в рамките на O-символиката може да бъде пренебрегнато
Като цяло вариант 2 изглежда малко по-оптимален, но това е по-скоро «еволюция вместо революция». За да реализираме «революция» ще ни трябва Вариант 3 (col).
Да обърнем всичко «с главата надолу»: да назначим имената на колоната идентификатор на потребителя! Какво ще бъде записано в самата колона – за нас вече не е от съществено значение, нека да е числото 1 (въобще, от полезните неща там може да се съхранява, например, група «семейство/приятели/и т.н.»). Този подход може да изненада неподготвения «обикновен човек», който до този момент не е имал опит с NoSQL бази, но именно той позволява използването на потенциала на HBase в тази задача много по-ефективно:
RowKey
Колони
Вася
Петя: 1
Оля: 1
Даша: 1
Петя
Маша: 1
Вася: 1
Тук получаваме няколко предимства. За да ги разберем, нека анализираме новата структура и оценим изчислителната сложност:
- Четене на данни: за да отговорим на въпроса, подписан ли е Вася за Оля, е достатъчно да прочетем една колона «Оля»: ако тя съществува, отговорът е True, ако не – False => O(1)
- Промяна на данни: добавяне на приятел: Добавяне на приятел: просто е достатъчно да добавим нова колона «ID на приятел» => O(1)
- Промяна на данни: изтриване на приятел: просто е достатъчно да изтрием колоната «ID на приятел» => O(1)
Както виждаме, съществено предимство на тази модел на съхранение е, че в всички необходими ни сценарии оперираме само с една колона, избягвайки изчитането на цял ред от базата и особено преминаването през всички колони на този ред. На това можеше да се спре, но…
Можете да се замислите и да отидете малко по-далече по пътя на оптимизацията на производителността и намаляването на операциите за вход-изход при обращение към базата. Какво ще стане, ако съхраняваме пълната информация за връзката директно в ключа на реда? Тоест да направим ключа съставен от вида userID.friendID? В този случай можем дори да не четем колоните на реда (Вариант 4(row)):
RowKey
Колони
Вася.Петя
Петя: 1
Вася.Оля
Оля: 1
Вася.Даша
Даша: 1
Петя.Маша
Маша: 1
Петя.Вася
Вася: 1
Очевидно е, че оценката на всички сценарии на манипулация с данни в такава структура, както и в предишния вариант, ще бъде O(1). Разликата с вариант 3 ще бъде изключително в ефективността на операциите за вход-изход в БД.
И последният "бантик". Лесно е да се забележи, че в вариант 4 ключът на реда ще има променлива дължина, което може да повлияе на производителността (тук си припомняме, че HBase съхранява данни като набор от байтове и редовете в таблиците са сортирани по ключ). Плюс имаме разделител, който в някои сценарии може да се наложи да обработваме. За да изключим това влияние, можем да използваме хешове от userID и friendID, и тъй като и двата хеша ще имат постоянна дължина, можем просто да ги конкатенираме, без разделител. Тогава данните в таблицата ще изглеждат така (Вариант 5(hash)):
RowKey
Колони
dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Петя: 1
dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Оля: 1
dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Даша: 1
1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Маша: 1
1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Вася: 1
Очевидно е, че алгоритмичната сложност на работата с такава структура по разглежданите от нас сценарии ще бъде същата като при вариант 4 – тоест O(1).
В заключение, нека сведем всички наши оценки на изчислителната сложност в една таблица:
Добавяне на приятел
Проверка на приятел
Изтриване на приятел
Вариант 1 (default)
O(n)
O(n)
O(n)
Вариант 2 (count)
O(1)
O(n)
O(n)
Вариант 3 (column)
O(1)
O(1)
O(1)
Вариант 4 (row)
O(1)
O(1)
O(1)
Вариант 5 (hash)
O(1)
O(1)
O(1)
Както се вижда, вариантите 3-5 изглеждат най-предпочитани и теоретично осигуряват изпълнението на всички необходими сценарии за манипулация с данни за константно време. В условията на нашата задача няма явно изискване за получаване на списък с всички приятели на потребителя, но в реалната проектна дейност, като добри анализатори, е добре да «предвидим», че може да възникне подобна задача и «да подстелим слама». Затова симпатизирам на вариант 3. Но съвсем вероятно е, че в реален проект този запитване може да е било решено с други средства, така че без обща представа за цялата задача е по-добре да не се правят окончателни изводи.
Подготовка на експеримента
Би било добре да проверим на практика изложените теоретични разсъждения – именно това беше целта на замисъла, появил се по време на дългите уикенди. За целта е необходимо да оценим скоростта на работа на нашето «условно приложение» при всички описани сценарии на използване на базата, както и увеличението на това време с нарастването на размера на социалната мрежа (n). Целевият параметър, който ни интересува и който ще измерваме по време на експеримента, е времето, което «условното приложение» изразходва за изпълнение на една «бизнес-операция». Под «бизнес-операция» разбираме едно от следните:
- Добавяне на един нов приятел
- Проверка дали потребител А е приятел на потребител Б
- Премахване на един приятел
Следователно, като имаме предвид обозначените в първоначалната задача изисквания, сценарият за проверка ще се представи по следния начин:
- Запис на данни. Генерирайте случаен начин на изходна мрежа с размер 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 приятели
Както може да се забележи, всички ID, по-големи от 10 000 в речника за проверка – са точно тези, които неминуемо ще дадат отговор False. Вмъкването, проверката и изтриването на "приятели" се извършват точно в указаната в речника последователност.
Експериментът беше проведен на лаптоп с Windows 10, където в един докер контейнер беше стартирана база HBase, а в друг – Python с Jupyter Notebook. На Docker бяха отпуснати 2 ядра CPU и 2 GB оперативна памет. Цялата логика, както и емулациите на работата на "условното приложение", така и "обвивката" за генериране на тестови данни и измерване на времето бяха написани на 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 се оказва малко по-бавна – вероятно поради необходимостта от четене и обработка на допълнителната колона „count“, което става все по-забележимо при нарастващ n. Но все пак ще се въздържа от каквито и да са изводи, тъй като точността на това сравнение е относително ниска. Освен това, тези съотношения (коя опция, 1 или 2, е по-бърза) се променяха от стартиране до стартиране (като същевременно запазваха характера на зависимостта и "вървяха рамо до рамо").
И последната графика – резултат от тестването на изтриването.
Тук отново без изненади. Опции 3-5 извършват изтриването за константно време.
Интересното е, че опции 4 и 5, в отличие от предишните сценарии, показват забележимо малко по-лоша производителност отколкото опция 3. Вероятно операцията по изтриване на ред е по-скъпа от операцията по изтриване на колона, което е напълно логично.
Опции 1 и 2, очаквано, демонстрират линейен растеж на времето. При това опция 2 стабилно е по-бавна от опция 1 – заради допълнителната операция по въвеждане-извеждане за „обслужване“ на колоната count.
Общите заключения на експеримента:
- Опции 3-5 демонстрират по-голяма ефективност, тъй като използват предимствата на HBase; при това производителността им се различава една от друга с константа и не зависи от размера на мрежата.
- Разликата между опции 4 и 5 не е била регистрирана. Но това не означава, че опция 5 не трябва да се използва. Възможно е използваният експериментален сценарий, като се отчитат ТТХ на тестовия стенд, да не е позволил тя да бъде установена.
- Характерът на растежа на времето, необходимо за изпълнение на „бизнес-операциите“ с данните, в общи линии потвърди предишните теоретични изводи за всички опции.
Епилог
Проведените груби експерименти не трябва да се приемат като абсолютна истина. Има много фактори, които не са били взети предвид и които влияят на резултатите (особено добре тези флуктуации могат да се видят на графиките при малък размер на мрежата). Например, скоростта на работа на thrift, който се използва в happybase, обемът и начинът на реализация на логиката, която бях написала на Python (не мога да кажа, че кодът е бил написан оптимално и е използвал ефективно възможностите на всички компоненти), възможно е особеностите на кеширането в HBase, фоновата активност на Windows 10 на моя лаптоп и т.н. В общи линии може да се смята, че всички теоретични изводи експериментално доказаха своята стойност. Или поне не успяхме да ги опровергаем с такъв „срещен удар“.
В заключение — препоръки към всички, които току-що започват да проектират модели от данни в HBase: абстрахирайте се от предишния опит с релационни бази и помнете „заповедите“:
- При проектиране, започваме от задачата и шаблоните за манипулация с данни, а не от модела на предметната област.
- Ефективен достъп (без full table scan) – само по ключ.
- Денормализация.
- Различни редове могат да съдържат различни колони.
- Динамичен състав на колоните.
Източник: habr.com
