Увод
„Морате да трчите што је брже могуће само да бисте остали на месту,
а да бисте негде стигли, морате трчати најмање дупло брже!“
(ц) Алиса у земљи чуда
Пре неког времена су ме замолили да одржим предавање аналитичари нашу компанију на тему пројектовања модела података, јер седећи на пројектима дуго (некад и по неколико година) губимо из вида шта се дешава око нас у свету ИТ технологија. У нашој компанији (тако се дешава) многи пројекти не користе НоСКЛ базе података (бар за сада), па сам им у свом предавању посебно посветио пажњу на примеру ХБасе-а и покушао да оријентишем презентацију материјала на оне који их никада нису користили су радили. Посебно сам илустровао неке од карактеристика дизајна модела података користећи пример који сам прочитао пре неколико година . Приликом анализе примера, упоредио сам неколико опција за решавање истог проблема како бих боље пренео главне идеје публици.
Недавно сам се „нема шта да радим“ запитао (дуги мајски викенд у карантину је посебно погодан за то), колико ће теоретски прорачуни одговарати пракси? Заправо, тако се родила идеја за овај чланак. Програмер који ради са НоСКЛ-ом неколико дана можда неће научити ништа ново из њега (и стога може одмах прескочити половину чланка). Али за аналитичариЗа оне који још увек нису блиско сарађивали са НоСКЛ-ом, мислим да ће бити корисно за стицање основног разумевања карактеристика дизајнирања модела података за ХБасе.
Пример анализе
По мом мишљењу, пре него што почнете да користите НоСКЛ базе података, морате добро размислити и одмерити предности и недостатке. Често се проблем највероватније може решити коришћењем традиционалних релационих ДБМС-а. Због тога је боље не користити НоСКЛ без значајних разлога. Ако сте ипак одлучили да користите НоСКЛ базу података, онда треба да узмете у обзир да су приступи дизајну овде нешто другачији. Поготово неки од њих могу бити необични за оне који су се раније бавили само релационим ДБМС-овима (према мојим запажањима). Дакле, у „релационом“ свету обично почињемо моделирањем проблематичног домена, а тек онда, ако је потребно, денормализујемо модел. У НоСКЛ-у ми треба одмах узети у обзир очекиване сценарије за рад са подацима и иницијално денормализовати податке. Поред тога, постоји низ других разлика, о којима ће бити речи у наставку.
Хајде да размотримо следећи „синтетички“ проблем, са којим ћемо наставити да радимо:
Неопходно је осмислити структуру складиштења за листу пријатеља корисника неке апстрактне друштвене мреже. Да поједноставимо, претпоставићемо да су све наше везе усмерене (као на Инстаграму, а не на Линкедину). Структура треба да вам омогући да ефикасно:
- Одговорите на питање да ли корисник А чита корисника Б (образац читања)
- Дозволи додавање/уклањање веза у случају претплате/отказивање претплате корисника А од корисника Б (шаблон промене података)
Наравно, постоји много опција за решавање проблема. У редовној релационој бази података, највероватније бисмо једноставно направили табелу односа (могуће типизовану ако, на пример, треба да сачувамо корисничку групу: породица, посао, итд., која укључује овог „пријатеља“) и да оптимизујемо брзина приступа би додала индексе/партиционирање. Највероватније би финална табела изгледала отприлике овако:
усер_ид
фриенд_ид
Васја
Петиа
Васја
Оля
у даљем тексту, ради јасноће и бољег разумевања, навешћу имена уместо личних докумената
У случају ХБасе-а, знамо да:
- могућа је ефикасна претрага која не доводи до потпуног скенирања табеле искључиво по кључу
- у ствари, зато је писање СКЛ упита познатих многим таквим базама података лоша идеја; технички, наравно, можете послати СКЛ упит са Јоинс-ом и другом логиком на ХБасе са исте Импале, али колико ће то бити ефикасно...
Због тога смо принуђени да користимо кориснички ИД као кључ. И моја прва мисао на тему „где и како чувати личне карте пријатеља?“ можда идеја да их чувате у колонама. Ова најочигледнија и „наивна“ опција ће изгледати отприлике овако (назовимо је Опција 1 (подразумевано)за даљу референцу):
РовКеи
Звучници
Васја
1: Петја
2: Оља
3: Даша
Петиа
1: Маша
2: Васја
Овде свака линија одговара једном кориснику мреже. Колоне имају називе: 1, 2, ... - према броју пријатеља, а ИД-ови пријатеља се чувају у колонама. Важно је напоменути да ће сваки ред имати различит број колона. У примеру на слици изнад, један ред има три колоне (1, 2 и 3), а други само две (1 и 2) – овде смо сами користили два ХБасе својства која немају релационе базе података:
- могућност динамичке промене састава колона (додај пријатеља -> додај колону, уклони пријатеља -> избриши колону)
- различити редови могу имати различите саставе колона
Хајде да проверимо нашу структуру да ли је у складу са захтевима задатка:
- Читање података: да бисмо разумели да ли је Васја претплаћен на Ољу, мораћемо да одузмемо цела линија помоћу кључа РовКеи = „Васиа“ и сортирајте вредности колона док у њима не „упознамо“ Ољу. Или поновите кроз вредности свих колона, „не упознајте“ Ољу и вратите одговор Нетачно;
- Уређивање података: додавање пријатеља: за сличан задатак такође треба да одузмемо цела линија користећи кључ РовКеи = „Васиа“ да израчуна укупан број његових пријатеља. Овај укупан број пријатеља нам је потребан да бисмо одредили број колоне у коју треба да упишемо ИД новог пријатеља.
- Промена података: брисање пријатеља:
- Треба одузети цела линија помоћу кључа РовКеи = “Васиа” и сортирај колоне како би пронашао ону у којој је забележен пријатељ којег треба избрисати;
- Затим, након брисања пријатеља, морамо да „померимо“ све податке у једну колону како не бисмо добили „празнине“ у њиховој нумерацији.
Хајде сада да проценимо колико ће ови алгоритми, које ћемо морати да имплементирамо на страни „условне апликације“, бити продуктивни, користећи . Означимо величину наше хипотетичке друштвене мреже са н. Тада је максимални број пријатеља који један корисник може имати (н-1). Ово (-1) можемо даље занемарити за наше потребе, пошто је у оквиру употребе О-симбола неважно.
- Читање података: потребно је одузети цео ред и итерирати кроз све његове колоне у граници. То значи да ће горња процена трошкова бити приближно О(н)
- Уређивање података: додавање пријатеља: да бисте одредили број пријатеља, потребно је да прођете кроз све колоне у реду, а затим убаците нову колону => О(н)
- Промена података: брисање пријатеља:
- Слично додавању - потребно је да прођете кроз све колоне у ограничењу => О(н)
- Након уклањања колона, морамо их „померити“. Ако примените ово „хеад-он“, онда ће вам у ограничењу бити потребно до (н-1) операција. Али овде и даље у практичном делу користићемо другачији приступ, који ће применити „псеудо-померање” за фиксни број операција – то јест, на то ће се трошити константно време, без обзира на н. Ово константно време (тачније О(2)) може се занемарити у поређењу са О(н). Приступ је илустрован на слици испод: једноставно копирамо податке из „последње“ колоне у ону из које желимо да избришемо податке, а затим избришемо последњу колону:
Укупно, у свим сценаријима добили смо асимптотичку рачунску сложеност од О(н).
Вероватно сте већ приметили да скоро увек морамо да прочитамо цео ред из базе, а у два од три случаја само да бисмо прошли кроз све колоне и израчунали укупан број пријатеља. Стога, као покушај оптимизације, можете додати колону „број“ која чува укупан број пријатеља сваког корисника мреже. У овом случају, не можемо да прочитамо цео ред да бисмо израчунали укупан број пријатеља, већ да прочитамо само једну колону „број“. Главна ствар је да не заборавите да ажурирате „број“ када манипулишете подацима. То. побољшавамо се Опција 2 (број):
РовКеи
Звучници
Васја
1: Петја
2: Оља
3: Даша
број: 3
Петиа
1: Маша
2: Васја
број: 2
У поређењу са првом опцијом:
- Читање података: да добијете одговор на питање "Да ли Васја чита Ољу?" ништа се није променило => О(н)
- Уређивање података: додавање пријатеља: Поједноставили смо уметање новог пријатеља, јер сада не морамо да читамо цео ред и да итерујемо његове колоне, већ можемо да добијемо само вредност колоне „цоунт” итд. одмах одредите број колоне за убацивање новог пријатеља. Ово доводи до смањења сложености рачунара на О(1)
- Промена података: брисање пријатеља: Када бришемо пријатеља, такође можемо да користимо ову колону да смањимо број И/О операција при „померању“ података за једну ћелију улево. Али и даље остаје потреба за понављањем колона да бисте пронашли ону коју треба избрисати, тако да => О(н)
- С друге стране, сада приликом ажурирања података морамо сваки пут да ажурирамо колону „број“, али то захтева константно време, што се може занемарити у оквиру О-симбола
Генерално, опција 2 изгледа мало оптималнија, али више личи на „еволуцију уместо револуције“. Требаће нам да направимо „револуцију“. Опција 3 (боја).
Хајде да све окренемо наопачке: доделићемо име колоне ИД корисника! За нас више није важно шта ће писати у самој колони, нека то буде број 1 (уопштено говорећи, корисне ствари се могу чувати тамо, на пример, група „породица/пријатељи/итд.”). Овај приступ може изненадити неспремног „лаика“ који нема претходног искуства у раду са НоСКЛ базама података, али управо овај приступ вам омогућава да искористите потенцијал ХБасе-а у овом задатку много ефикасније:
РовКеи
Звучници
Васја
Петја: 1
Оља: 1
Даша: 1
Петиа
Маша: 1
Васја: 1
Овде добијамо неколико предности одједном. Да бисмо их разумели, анализирајмо нову структуру и проценимо сложеност рачунара:
- Читање података: да бисте одговорили на питање да ли је Васја претплаћен на Ољу, довољно је прочитати једну колону „Оља“: ако постоји, онда је одговор Тачно, ако није – Нетачно => О(1)
- Уређивање података: додавање пријатеља: Додавање пријатеља: само додајте нову колону „ИД пријатеља“ => О(1)
- Промена података: брисање пријатеља: само уклоните колону ИД пријатеља => О(1)
Као што видите, значајна предност овог модела складиштења је то што у свим сценаријима који су нам потребни, радимо само са једном колоном, избегавајући читање целог реда из базе података и, штавише, набрајање свих колона овог реда. Могли бисмо ту стати, али...
Можете бити збуњени и отићи мало даље на путу оптимизације перформанси и смањења И/О операција приликом приступа бази података. Шта ако смо комплетне информације о односима сачували директно у самом кључу реда? То јест, направити композитни кључ као што је усерИД.фриендИД? У овом случају, уопште не морамо да читамо колоне реда (Опција 4 (ред)):
РовКеи
Звучници
Васиа.Петиа
Петја: 1
Васиа.Олиа
Оља: 1
Васиа.Дасха
Даша: 1
Петиа.Масха
Маша: 1
Петиа.Васиа
Васја: 1
Очигледно, процена свих сценарија манипулације подацима у таквој структури, као у претходној верзији, биће О(1). Разлика са опцијом 3 биће искључиво у ефикасности И/О операција у бази података.
Па, последњи „наклон“. Лако је видети да ће у опцији 4 кључ реда имати променљиву дужину, што може да утиче на перформансе (овде се сећамо да ХБасе складишти податке као скуп бајтова, а редови у табелама су сортирани по кључу). Осим тога, имамо сепаратор који ће можда морати да се обради у неким сценаријима. Да бисте елиминисали овај утицај, можете користити хешове из ИД-а корисника и ФриендИД-а, а пошто ће оба хеша имати константну дужину, можете их једноставно спојити, без сепаратора. Тада ће подаци у табели изгледати овако (Опција 5 (хеш)):
РовКеи
Звучници
dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Петја: 1
dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Оља: 1
dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Даша: 1
1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Маша: 1
1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Васја: 1
Очигледно је да ће алгоритамска сложеност рада са таквом структуром у сценаријима које разматрамо бити иста као код опције 4 – односно О(1).
Укупно, хајде да сумирамо све наше процене сложености рачунара у једној табели:
Додавање пријатеља
Проверавам пријатеља
Уклањање пријатеља
Опција 1 (подразумевано)
Он)
Он)
Он)
Опција 2 (број)
О (1)
Он)
Он)
Опција 3 (колона)
О (1)
О (1)
О (1)
Опција 4 (ред)
О (1)
О (1)
О (1)
Опција 5 (хеш)
О (1)
О (1)
О (1)
Као што видите, чини се да су опције 3-5 најпожељније и теоретски обезбеђују извршење свих неопходних сценарија манипулације подацима у сталном времену. У условима нашег задатка не постоји изричит захтев за добијање листе свих пријатеља корисника, али би у стварним пројектним активностима било добро да ми, као добри аналитичари, „предвидимо“ да би се такав задатак могао појавити и "прошири сламку." Дакле, моје симпатије су на страни опције 3. Али врло је вероватно да је у реалном пројекту овај захтев већ могао бити решен другим средствима, па је, без опште визије целокупног проблема, боље не правити коначни закључци.
Припрема експеримента
Желео бих да проверим горе наведене теоријске аргументе у пракси – то је био циљ идеје која је настала током дугог викенда. Да бисмо то урадили, потребно је проценити брзину рада наше „условне апликације“ у свим описаним сценаријима коришћења базе података, као и повећање овог времена са повећањем величине друштвене мреже (н). Циљни параметар који нас занима и који ћемо мерити током експеримента је време које „условна апликација“ потроши да изврши једну „пословну операцију“. Под „пословном трансакцијом“ подразумевамо једно од следећег:
- Додавање једног новог пријатеља
- Провера да ли је корисник А пријатељ корисника Б
- Уклањање једног пријатеља
Дакле, узимајући у обзир захтеве наведене у почетној изјави, сценарио верификације се појављује на следећи начин:
- Снимање података. Насумично генеришите почетну мрежу величине н. Да бисмо се приближили „стварном свету“, број пријатеља који сваки корисник има такође је случајна варијабла. Измерите време током којег наша „условна апликација“ уписује све генерисане податке у ХБасе. Затим поделите добијено време са укупним бројем додатих пријатеља - овако добијамо просечно време за једну „пословну операцију“
- Читање података. За сваког корисника направите листу „личности“ за које треба да добијете одговор да ли је корисник претплаћен на њих или не. Дужина листе = приближно број пријатеља корисника, а за половину проверених пријатеља одговор треба да буде „Да“, а за другу половину – „Не“. Провера се врши таквим редоследом да се одговори „Да“ и „Не“ смењују (то јест, у сваком другом случају мораћемо да прођемо кроз све колоне реда за опције 1 и 2). Укупно време скрининга се затим дели са бројем тестираних пријатеља да би се добило просечно време скрининга по субјекту.
- Брисање података. Уклоните све пријатеље од корисника. Штавише, редослед брисања је насумичан (то јест, „промешамо“ оригиналну листу која се користи за снимање података). Укупно време провере се затим дели са бројем уклоњених пријатеља да би се добило просечно време по провери.
Потребно је покренути сценарије за сваку од 5 опција модела података и за различите величине друштвене мреже да би се видело како се време мења како расте. У оквиру једног н, везе у мрежи и листа корисника за проверу морају, наравно, бити исти за свих 5 опција.
За боље разумевање, испод је пример генерисаних података за н= 5. Написани „генератор“ производи три ИД речника као излаз:
- први је за уметање
- други је за проверу
- треће – за брисање
{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 у речнику за проверу су управо они који ће сигурно дати одговор Нетачно. Уметање, провера и брисање „пријатеља“ врши се тачно у редоследу који је наведен у речнику.
Експеримент је спроведен на лаптопу који ради под оперативним системом Виндовс 10, где је ХБасе радио у једном Доцкер контејнеру, а Питхон са Јупитер Нотебоок-ом у другом. Доцкер-у су додељена 2 ЦПУ језгра и 2 ГБ РАМ-а. Сва логика, и емулација „условне апликације“ и „цевовода“ за генерисање тестних података и мерење времена, написана је у Питхон-у. Библиотека је коришћена за рад са ХБасе-ом , за израчунавање хешева (МД5) за опцију 5 - хасхлиб
Узимајући у обзир рачунарску снагу одређеног лаптопа, експериментално је одабрано лансирање за н = 10, 30, …. 170 – када је укупно време рада пуног циклуса тестирања (сви сценарији за све опције за све н) било чак мање или више разумно и одговарало током једне чајанке (у просеку 15 минута).
Овде је потребно напоменути да у овом експерименту не оцењујемо првенствено апсолутне бројке перформанси. Чак и релативно поређење две различите опције можда није сасвим тачно. Сада нас интересује природа промене времена у зависности од н, пошто је, узимајући у обзир горњу конфигурацију „испитног штанда“, веома тешко добити процене времена „очишћене“ од утицаја случајних и других фактора ( а такав задатак није био постављен).
Резултат експеримента
Први тест је како се мења време проведено на попуњавању листе пријатеља. Резултат је на графикону испод.
Опције 3-5, као што се и очекивало, показују скоро константно време „пословне трансакције“, које не зависи од раста величине мреже и неразлучиве разлике у перформансама.
Опција 2 такође показује константне, али нешто лошије перформансе, скоро тачно 2 пута у односу на опције 3-5. И ово не може а да не радује, пошто је у корелацији са теоријом - у овој верзији број И/О операција ка/из ХБасе-а је тачно 2 пута већи. Ово може послужити као индиректан доказ да наш тестни сто у принципу пружа добру тачност.
Опција 1 се такође, као што се и очекивало, показује као најспорија и показује линеарно повећање времена утрошеног на међусобно додавање на величину мреже.
Погледајмо сада резултате другог теста.
Опције 3-5 се опет понашају како се очекује - константно време, независно од величине мреже. Опције 1 и 2 показују линеарно повећање времена како се величина мреже повећава и сличне перформансе. Штавише, опција 2 се испостави да је мало спорија - очигледно због потребе да се лекторише и обради додатна колона „број“, која постаје уочљивија како н расте. Али ипак ћу се уздржати од извођења било каквих закључака, пошто је тачност овог поређења релативно ниска. Поред тога, ови односи (која опција, 1 или 2, је бржа) су се мењали од трчања до трчања (исто задржавајући природу зависности и „покретање врата и врата“).
Па, последњи графикон је резултат тестирања уклањања.
Опет, овде нема изненађења. Опције 3-5 врше уклањање у сталном времену.
Штавише, занимљиво, опције 4 и 5, за разлику од претходних сценарија, показују приметно нешто лошије перформансе од опције 3. Очигледно, операција брисања редова је скупља од операције брисања колоне, што је генерално логично.
Опције 1 и 2, како се очекивало, показују линеарно повећање времена. У исто време, опција 2 је константно спорија од опције 1 - због додатне И/О операције за „одржавање“ колоне за бројање.
Општи закључци експеримента:
- Опције 3-5 показују већу ефикасност јер користе предности ХБасе-а; Штавише, њихове перформансе се разликују једна у односу на другу за константу и не зависе од величине мреже.
- Разлика између опција 4 и 5 није забележена. Али то не значи да опцију 5 не треба користити. Вероватно је да експериментални сценарио који је коришћен, узимајући у обзир карактеристике перформанси испитног стола, није дозволио да се открије.
- Природа повећања времена потребног за обављање „пословних операција“ са подацима генерално је потврдила претходно добијене теоријске прорачуне за све опције.
Епилог
Грубе експерименте који су спроведени не треба узимати као апсолутну истину. Много је фактора који нису узети у обзир и који су искривили резултате (ове флуктуације су посебно видљиве на графиконима са малом величином мреже). На пример, брзина штедљивости коју користи хаппибасе, обим и начин имплементације логике коју сам написао у Питхон-у (не могу да тврдим да је код написан оптимално и да је ефикасно користио могућности свих компоненти), можда карактеристике ХБасе кеширања, позадинске активности Виндовс 10 на мом лаптопу итд. Генерално, можемо претпоставити да су сви теоријски прорачуни експериментално показали своју валидност. Па, или их барем није било могуће оповргнути таквим „нападом у главу“.
У закључку, препоруке за све који тек почињу да дизајнирају моделе података у ХБасе-у: апстрахујте из претходног искуства рада са релационим базама података и запамтите „заповести“:
- Приликом пројектовања полазимо од задатка и образаца манипулације подацима, а не од модела домена
- Ефикасан приступ (без комплетног скенирања табеле) – само помоћу кључа
- Денормализација
- Различити редови могу садржати различите колоне
- Динамичка композиција говорника
Извор: ввв.хабр.цом