Andmemudeli disaini omadused NoSQL jaoks

Sissejuhatus

„Peab olema kõikide jõududega jooksma, et lihtsalt kohapeal püsida,
ja et kuhugi jõuda, tuleb joosta vähemalt kahekordselt kiiremini!“
(c) Alice Imedemaal

Mõni aeg tagasi paluti mul pidada loeng meie ettevõtte analüütikutele teemal andmemudelite projekteerimine, sest pikaajaliste projektide (mõnikord mitu aastat) jooksul unustame, mis IT-tehnoloogiate maailmas toimub. Meie ettevõttes (nüüd nii juhtunud) ei kasutata paljudes projektides NoSQL andmebaase (vähemalt seni), seega pidasin oma loengus põhitähelepanu sellele, kasutades HBase'i näidet, ja püüdsin suunata materjali esitust neile, kes pole nendega kunagi töötanud. Eriliselt tõin välja andmemudeli projekteerimise mõned eripärad näite põhjal, mille lugesin paar aastat tagasi artiklist „Introduction to HBase Schema Design“ autoriks Amandeep Khurana. Analüüsides näiteid, võrdsustasin omavahel mitmeid lahenduste variante sama probleemi käsitlemiseks, et paremini edastada kuulajatele põhiteemasid.Hiljuti, „igavusest“, küsisin endalt, kuivõrd teoreetilised järeldused vastavad praktikale? Tegelikult sündiski selle artikli idee. Arendaja, kes on juba pikka aega töötanud NoSQL-iga, ei pruugi siit midagi uut leida (ja seetõttu võib kohe artikli keskelt edasi kerida). Aga

analüütikutele, kes pole veel NoSQL-iga tihedalt töötanud, arvan, et see artikkel annab kasulikke baasteadmisi HBase'i andmemudelite projekteerimise eripäradest.Näite analüüs

Näide analüüs

Minu arvates tuleks enne NoSQL andmebaaside kasutamise alustamist hoolikalt mõelda ja kaaluda "pooli" ja "vastu". Sageli saab ülesande lahendada ka traditsiooniliste relationaalsete andmebaasidega. Seega on parem vältida NoSQL-i kasutamist ilma oluliste põhjusteta. Kui otsus kasutada siiski NoSQL andmebaasi on tehtud, tuleb arvestada, et projekteerimispõhimõtted on siin veidi erinevad. Eriti võivad mõned neist olla harjumatud neile, kes on varem töötanud ainult relationaalsete andmebaasidega (minu vaatluste kohaselt). Nii et "relationaalses" maailmas lähtume tavaliselt aineala mudeldamisest, ja alles siis, vajadusel, teeme mudeli denormaliseerimise. NoSQL-i puhul peame järele mõtlema eeldatavad stsenaariumid andmete töötlemiseks ja algselt andmeid denormaliseerima. Lisaks on veel mitmeid teisi erinevusi, millest allpool räägitakse.

Kaalume järgmise "sünteetilise" ülesande, millega edaspidi töötame:

On vajalik kujundada struktuur kasutajate sõprade nimekirja salvestamiseks mingisuguses abstraktses sotsiaalses võrgustikus. Lihtsuse huvides eeldame, et kõik sidemed on suunatud (nagu Instagramis, mitte LinkedInis). Struktuur peaks võimaldama tõhusalt:

• Vastata küsimusele, kas kasutaja A loeb kasutaja B postitusi (lugemise mall)
• Lubada lisada/rahuldada sidemed juhul, kui kasutaja A jälgib/kui kasutaja A loobub kasutaja B jälgimisest (andmete muutmise mall)

Muidugi on ülesande lahendamiseks palju võimalusi. Tavalises relationaalses andmebaasis teeksime tõenäoliselt lihtsalt sidemete tabeli (võimalik, et tüpiseeritud, kui näiteks on vaja salvestada kasutajarühm: pere, töö jne, kuhu kuulub see "sõber"), ning juurdepääsu kiirusel optimeerimiseks lisaksime indeksid/partitsioneerimise. Tõenäoliselt näeks lõpptabel välja umbes selline:

user_id
friend_id

Vasya
Petja

Vasya
Olya

siin ja edaspidi kasutan selguse ja parema arusaamise nimel ID-de asemel nimed

HBase-i puhul teame, et:

• efektiivne otsing, mis ei vii full table scan'ini, on võimalik ainult võtme järgi
  • Just for this reason, writing familiar SQL queries for such databases is a bad idea; technically, of course, you can send an SQL query with Joins and other logic from Impala to HBase, but how effective it would be...

Therefore, we are forced to use the user ID as a key. The first thought on where and how to store friend IDs may be the idea of storing them in columns. This most obvious and 'naive' option would look something like this (let's call it Option 1 (default), so we can refer to it later):

RowKey
Columns

Vasya
1: Petya
2: Olya
3: Dasha

Petja
1: Masha
2: Vasya

Here, each row corresponds to one user of the network. The columns are named: 1, 2, … — according to the number of friends, and the friend IDs are stored in the columns. It is important to note that each row will have a different number of columns. In the example above, one row has three columns (1, 2, and 3), while the second one has only two (1 and 2) — here we utilized two properties of HBase that relational databases do not have:

• the ability to dynamically change the composition of columns (add a friend -> add a column, remove a friend -> remove a column)
• different rows can have a different composition of columns

Let's check our structure against the task requirements:

• Andmete lugemine: in order to understand whether Vasya is subscribed to Olya, we need to read the entire row by the RowKey = 'Vasya' and iterate through the column values until we 'meet' Olya in them. Or iterate through the values of all columns, not 'meeting' Olya and return False;
• Data modification: adding a friend: for such a task, we will also need to read the entire row by RowKey = 'Vasya' to count the total number of his friends. This total number of friends is necessary for us to determine the column number where we need to record the ID of the new friend.
• Data modification: deleting a friend:
  • It is necessary to read the entire row by RowKey = 'Vasya' and iterate through the columns to find the one where the friend to be deleted is recorded;
  • Then, after deleting the friend, we need to 'shift' all the data in one column to avoid 'gaps' in their numbering.

Now let’s evaluate how efficient the algorithms we need to implement on the side of the 'conditional application' will be, using O-symbol. Märgime meie hüpoteetilise sotsiaalvõrgu suuruseks n. Siis võib ühe kasutaja maksimaalne sõprade arv olla (n-1). Selle (-1) võime meie eesmärkide jaoks edaspidi eirata, kuna O-sümboolika kontekstis ei oma see tähtsust.

• Andmete lugemine: on vajalik lugeda välja kogu rida ja uurida piiril kõiki selle veerge. Seega on ligikaudne kulude ülemine hind umbes O(n)
• Data modification: adding a friend: sõprade arvu määramiseks on vajalik uurida kõiki rea veerge, pärast mida tuleb lisada uus veerg => O(n)
• Data modification: deleting a friend:
  • Sarnaselt lisamisega - on vajalik piiril uurida kõiki veerge => O(n)
  • Pärast veergude eemaldamist peame need "liigutama". Kui teostame seda "otseselt", siis on lõppkokkuvõttes vaja veel kuni (n-1) toimingut. Kuid me rakendame siin ja edaspidi praktikas teistsugust lähenemist, mis teostab "pseudo-liikumise" fikseeritud hulk operatsioone – st selle jaoks kulutatakse konstantne aeg olenemata n-st. Selle konstantse aja (kui olla täpne, siis O(2)) võib võrreldes O(n) ignoreerida. Lähenemist illustreeritakse alloleval joonisel: kopeerime lihtsalt andmed "viimase" veeru seest sinna, millest tuleb andmed kustutada, pärast mida eemaldame viimase veeru:
    

Kokkuvõttes, kõikides stsenaariumides saavutame asümptootilise arvutuskompleksuse O(n).
Tõenäoliselt olete juba märganud, et peame peaaegu alati välja lugema kogu rea tervikuna, kusjuures kahes kolmandikus juhtudest ainult selleks, et uurida kõiki veerge ja arvutada sõprade koguarv. Seetõttu optimeerimise katse raames saame lisada veeru "count", kus salvestada iga sotsiaalvõrgu kasutaja üldine sõprade arv. Sel juhul ei pea me kogu rida tervikuna sõprade koguarvu arvutamiseks välja lugema, vaid saame lugeda ainult veeru "count". Peamine on mitte unustada uuendada "count" andmete manipuleerimisel. Seega saame paremuse. Variant 2 (count):

RowKey
Columns

Vasya
1: Petya
2: Olya
3: Dasha
count: 3

Petja
1: Masha
2: Vasya

count: 2

Esimese variandi võrdluses:

• Andmete lugemine: küsimusele "Kas Vasja loeb Oljat?" pole midagi muutunud => O(n)
• Data modification: adding a friend: Oleme lihtsustanud uue sõbra lisamist, sest nüüd ei pea me kogu rida läbi vaatama ja selle veerge järjestama, vaid saame lihtsalt kätte veeru „count“ väärtuse ja seega määrata uue sõbra lisamise veeru numbri. See vähendab arvutuskohustuse keerukust O(1)-ni.
• Data modification: deleting a friend: Sõbra kustutamisel saame samuti kasutada seda veergu, et vähendada sisse- ja väljundoperatsioonide arvu, kui „nihutame“ andmeid ühe lahtri võrra vasakule. Kuid veergude läbivaatamise vajadus kustutatava leidmiseks jääb alles, seega => O(n)
• Teisest küljest, nüüd peame andmete värskendamisel iga kord ka veeru „count“ uuendama, kuid sellele kulub konstantne aeg, mida O-keerukuse kontekstis saab tähelepanuta jätta.

Kokkuvõttes tundub variant 2 natuke optimaalsem, kuid see on pigem „evolutsioon, mitte revolutsioon“. „Revolutsiooni“ elluviimiseks vajame... Variant 3 (col).
Käime kõik „peapeale“: määrame veergu kasutaja identifikaatorina! Mida sellele veerule salvestatakse, ei ole meie jaoks enam oluline, olgu seal number 1 (üldiselt võib seal hoida näiteks grupi „pere/sõbrad/jne.“). See lähenemine võib üllatada ettevalmistamata „tavalist“ inimest, kes pole varem NoSQL-andmebaasidega töötanud, kuid just see võimaldab HBase potentsiaali selles ülesandes palju tõhusamalt kasutada:

RowKey
Columns

Vasya
Petja: 1
Olia: 1
Dasha: 1

Petja
Masha: 1
Vasia: 1

Siin saame kohe mitu eelist. Et neid mõista, analüüsime uut struktuuri ja hindame arvutuskohustuse keerukust:

• Andmete lugemine: selleks, et vastata küsimusele, kas Vasia on Olias, piisab, kui lugeda veergu „Olia“: kui see on olemas, siis vastus True, kui ei, siis False => O(1)
• Data modification: adding a friend: Sõbra lisamiseks: piisab lihtsalt uue veeru „Sõbra ID“ lisamisest => O(1)
• Data modification: deleting a friend: piisab lihtsalt veeru „Sõbra ID“ eemaldamisest => O(1)

Nagu näeme, on sellise säilitamise mudeli oluliseks eeliseks see, et kõigis vajalikes stsenaariumides opereerime ainult ühe veeruga, vältides kogu rea lugemist andmebaasist ja veelgi enam, selle rea kõigi veergude läbivaatamist. Sellega võiks lõpetada, kuid…

Saame uurida ja minna veel veidi kaugemale jõudluse optimeerimise ja andmebaasi sisendi-väljundi operatsioonide vähendamise teel. Mida kui hoida kogu teave seose kohta otse faili rea võtmises? St. teha võtmega koostisosast, näiteks userID.friendID? Sellisel juhul ei pea me mingil juhul isegi ridade veerge lugema.Variant 4 (rida)):

RowKey
Columns

Vassja.Petja
Petja: 1

Vassja.Olja
Olia: 1

Vassja.Dasha
Dasha: 1

Petja.Masha
Masha: 1

Petja.Vassja
Vasia: 1

Kliir, et sellise struktuuri andmetega kõigi manipuleerimise stsenaariumide hindamine on samuti O(1), nagu eelmine variant. Erinevus kolmandast variandist on ainult sisendi-väljundi operatsioonide efektiivsuses andmebaasis.

Ja viimane "sildike". Kergesti võib märgata, et variandi 4 korral on meie ridade võtmel muutuv pikkus, mis võib tõenäoliselt mõjutada jõudlust (siin tasub meeles pidada, et HBase salvestab andmeid baitide kogumina ja read tabelites on võtme järgi sorteeritud). Samuti on meil eraldaja, mida mõnedes stsenaariumides tuleb töödelda. Selle mõju kõrvaldamiseks on võimalik kasutada userID ja friendID räsimärke, ja kuna mõlemal räsil on stabiilne pikkus, saab neid lihtsalt ühendada ilma eraldajata. Siis näeb andmestik tabelis välja selline.Variant 5 (räsimärk)):

RowKey
Columns

dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Petja: 1

dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Olia: 1

dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Dasha: 1

1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Masha: 1

1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Vasia: 1

Ilmselt on algoritmilise keerukuse töö selle struktuuriga arvestatavate stsenaariumide puhul sama, mis variandi 4 puhul – st O(1).
Kokkuvõtteks, koondame kõik meie arvutusi tabelisse:

Sõbra lisamine
Sõbra kontrollimine
Sõbra kustutamine

Option 1 (default)
O(n)
O(n)
O(n)

Variant 2 (loendus)
O(1)
O(n)
O(n)

Variant 3 (veerg)
O(1)
O(1)
O(1)

Variant 4 (rida)
O(1)
O(1)
O(1)

Variant 5 (räsimärk)
O(1)
O(1)
O(1)

Nagu näha, on variandid 3-5 kõige eelistatumad ja teoreetiliselt tagavad kõik vajalikud andmete manipuleerimise stsenaariumid konstantse ajaga. Meie ülesande tingimustes ei ole otsest nõuet, et saada kasutaja kõigi sõprade nimekirja, kuid reaalses projektitöös oleks meil kui headel analüütikutel hea "ette näha", et selline ülesanne võib tekkida ja "alauku panna". Seetõttu on minu toetused variandi 3 poole. Kuid on täiesti võimalik, et reaalses projektis on see päring juba lahendatud muude vahenditega, seega ilma üldise visioonita kogu ülesandest pole parem teha lõplikke järeldusi.

Katseseadmete ettevalmistamine

Ülaltoodud teoreetilisi mõtisklusi tahaksin praktikas kontrollida – see oli ka pika nädalavahetuse mõtte eesmärk. Selleks on vajalik hinnata meie "teoreetilise rakenduse" töö kiirus kõigis kirjeldatud andmebaasi kasutamise stsenaariumites, samuti selle aja kasvu koos sotsiaalvõrgustiku (n) suuruse kasvuga. Sihtnäitaja, mis meid huvitab ja mida me eksperimendi käigus mõõdame, on aeg, mille "teoreetiline rakendus" kulutab ühe "äritegevuse" täitmiseks. "Äritegevusena" mõistame me ühte järgmistest:

• Uue sõbra lisamine
• Kontrollimine, kas kasutaja A on kasutaja B sõber
• Ühe sõbra eemaldamine

Seega, arvestades algsetes tingimustes märgitud nõudeid, kujuneb kontrollimise stsenaarium järgmiseks:

• Andmete salvestamine. Juhuslikult genereerida algne võrk suurusega n. Suuremaks lähenemiseks "reaalsele maailmale" on iga kasutaja sõprade arv samuti juhuslik suurus. Mõõta aeg, mille jooksul meie "teoreetiline rakendus" salvestab HBase kõik genereeritud andmed. Seejärel jagame saadud aja kõigi lisatud sõprade koguarvuga – nii saame keskmise aja ühe "äritegevuse" kohta.
• Andmete lugemine. Iga kasutaja jaoks koostada nimekiri „isikutest”, kelle kohta tuleb kontrollida, kas kasutaja on neile tellinud või mitte. Nimekirja pikkus = umbes kasutaja sõprade arv, kusjuures pooltel kontrollitavatest sõpradest peab vastus olema „Jah”, ja teisel poolel – „Ei”. Kontrollimine toimub sellises järjekorras, et „Jah” ja „Ei” vahelduvad (st igal teisel juhul peame kõiki veerge rida 1 ja 2 kontrollima). Üldine kontrollimise aeg jagada seejärel kontrollitavate sõprade arvuga, et saada keskmine aeg ühe subjekti kontrollimiseks.
• Andmete eemaldamine. Eemaldada kasutajalt kõik sõbrad. Eemaldamise järjekord peab olema juhuslik (st „segame” algse nimekirja, mida andmete salvestamiseks kasutati). Üldine kontrollimise aeg jagada seejärel eemaldatavate sõprade arvuga, et saada keskmine aeg ühe kontrolli jaoks.

Skeeme tuleb jooksutada iga 5 andmemudeli variandi ja erineva sotsiaalvõrgu suuruse jaoks, et näha, kuidas aeg muutub selle kasvades. Ühe n sideme raames peavad võrgu ja kontrollitavate kasutajate nimekirjad olema loomulikult kõikide 5 variandi jaoks samad.
Selle paremiseks mõistmiseks toon allpool näite genereeritud andmetest n= 5. Kirjutatud „generaator” annab väljundina kolm ID-sõnastikku:

• esimene – sisestamiseks
• teine – kontrollimiseks
• kolmas – eemaldamiseks

{0: [1], 1: [4, 5, 3, 2, 1], 2: [1, 2], 3: [2, 4, 1, 5, 3], 4: [2, 1]} # kokku 15 sõpra

{0: [1, 10800], 1: [5, 10800, 2, 10801, 4, 10802], 2: [1, 10800], 3: [3, 10800, 1, 10801, 5, 10802], 4: [2, 10800]} # kokku 18 kontrollitavat subjekt

{0: [1], 1: [1, 3, 2, 5, 4], 2: [1, 2], 3: [4, 1, 2, 3, 5], 4: [1, 2]} # kokku 15 sõpra

Kuidas võib märgata, et kõik ID-d, mis ületavad 10 000 kontrollimise sõnastikus – need on just need, mis kindlasti annavad vastuse False. Sõprade sisestamine, kontrollimine ja eemaldamine toimuvad täpselt sõnastikus näidatud järjekorras.

Eksperiment viidi läbi sülearvutis, mis töötas Windows 10 all, kus ühes Docker konteineris töötas HBase andmebaas ja teises – Python Jupyter Notebookiga. Dockerile eraldati 2 CPU tuuma ja 2 GB RAM-i. Kogu loogika, nii „tinglikku rakendust” simuleerimine kui ka testandmete genereerimise ja aja mõõtmise „ümberringi” kirjutati Pythonis. HBase’i töötlemiseks kasutati teeki happybase, et hashide (MD5) arvutamiseks variandi 5 — hashlib

Arvesse võttes konkreetse sülearvuti arvutusvõimsust, valiti katse käivitamine eksperimentaalselt n = 10, 30, … 170 – kui kogu testimise tsükli (kõik stsenaariumid kõigi variantide jaoks kõikide n-de jaoks) koguaeg oli veel enam-vähem mõistlik ja mahtus ühe teejoomise ajal (keskmiselt 15 minutit).

Siin on vajalik teha märkida, et selles eksperimendis hindame esmajoones mitte absoluutseid jõudluse numbreid. Isegi kahe erineva variandi suhteline võrdlemine ei pruugi olla täiesti korrektne. Praegu huvitab meid eelkõige aja muutumise iseloom sõltuvalt n-st, kuna eespool nimetatud 'katse seade' konfigureerimisega on ajahinnangute saamine, mis on 'puhastatud' juhuslike ja muude tegurite mõjust, väga keeruline (ja sellist eesmärki pole seadnud).

Eksperimenti tulemus

Esimene test – kuidas muutub aeg, mis kulub sõprade nimekirja täitmiseks. Tulemus – alloleval graafikul.

Variandid 3-5 näitavad oodatult peaaegu konstantset 'äritegevuse' aega, mis ei sõltu võrgu suuruse kasvust ega ole eristuv erinevus jõudluses.
Variant 2 näitab samuti konstanti, kuid veidi halvemad tulemused, olles praktiliselt 2 korda madalam variantide 3-5 suhtes. See ei saa mitte rõõmustada, sest see vastab teooriale – selles variandis on operatsioonide arv HBase'i sisse-/väljal 2 korda suurem. See võib olla kaudne tõend, et meie testimisseade annab põhimõtteliselt head täpsust.
Variant 1 osutub samuti oodatult kõige aeglasemaks ja näitab võrgu suuruse osas lineaarset aja kasvu, mis kulub ühe sõbra lisamiseks.
Vaatame nüüd teise testi tulemusi.

Variandid 3-5 käituvad taas oodatult – konstantne aeg, mis ei sõltu võrgu suurusest. Variandid 1 ja 2 näitavad lineaarset aelae tõusu võrgu suuruse suurenedes ja sarnast jõudlust. Lisaks on variant 2 pisut aeglasem – ilmselt seetõttu, et tuleb lugeda ja töödelda täiendavat veergu "count", mis suurenedes n muutub silmatorkavamaks. Kuid ma siiski hoidun igasugustest järeldustest, kuna selle võrgu täpsus on suhteliselt madal. Lisaks muutusid need suhted (milline variant, 1 või 2, on kiirem) käivituse kaupa (samas säilitades sõltuvuse iseloomu ja "minnes ninapidi koos").

Ja viimane diagramm – testimise tulemused kustutamise kohta.

Siin pole jälle üllatusi. Variandid 3-5 teostavad kustutamise konstantse aja jooksul.
Mis on huvitav, variandid 4 ja 5, erinevalt eelmistest stsenaariumitest, näitavad veidi halvemana jõudlust võrreldes variant 3-ga. Ilmselt on rea kustutamine kulukam kui veeru kustutamine, mis on üldiselt mõistlik.

Variandid 1 ja 2 näitavad ootuspäraselt lineaarset aja kasvu. Samuti on variant 2 pidevalt aeglasem variant 1-st – tänu täiendavale sisend-väljund operatsioonile veeru count "hooldamiseks".

Katse üldised järeldused:

• Variandid 3-5 näitavad suuremat efektiivsust, kuna nad kasutavad HBase eeliseid; nende jõudlus erineb üksteisest konstantse arvu võrra ja ei sõltu võrgu suurusest.
• Variantide 4 ja 5 vahel ei olnud erinevust fikseeritud. Kuid see ei tähenda, et variant 5 ei ole kasutamiseks sobiv. On üsna tõenäoline, et katse stsenaarium koos testseina tehniliste omadustega ei võimaldanud selle tuvastamist.
• Aja kasvamise iseloom, mis on vajalik andmete "äriprotsesside" teostamiseks, kinnitas üldiselt varasemate teoreetiliste järelduste kehtivust kõigi variantide puhul.

Epilog

Tehtud karmid eksperimendid ei tohiks olla absoluutse tõena. On palju tegureid, mis ei olnud arvesse võetud ning mis moonutasid tulemusi (eriti hästi on need kõikumised nähtavad graafikutes väikese võrgu suuruse puhul). Näiteks thrift'i töökiirus, mida kasutab happybase, loogika maht ja rakendamise viis, mis mul oli kirjutatud Pythonis (ei julge väita, et kood oli optimaalselt kirjutatud ja kasutas kõigi komponentide võimalusi efektiivselt), võimalikud HBase'i puhverdamise eripärad, Windows 10 taustategevus minu sülearvutis jne. Üldiselt võib öelda, et kõik teoreetilised järeldused on eksperimentaalselt oma pädevust näidanud. Või vähemalt ei olnud võimalik neid sel viisil „otsesel rünnakul” ümber lükata.

Kokkuvõttes — soovitused kõigile, kes alles alustavad andmemudelite kavandamist HBase'is: abstraheerige end varasemast kogemusest relatsiooniliste andmebaasidega ja pidage meeles „kümmet käsku”:

• Kavandades alustame ülesandest ja andmete manipulatsiooni mustritest, mitte ainevaldkonna mudelist.
• Tõhus juurdepääs (ilma täieliku tabeli skannimiseta) – ainult võtme kaudu.
• Denormaliseerimine.
• Erinevad read võivad sisaldada erinevaid veerge.
• Dünaamiline veergude koosseis.

Allikas: habr.com