Uvod
"Moraš trčati što brže možeš samo da ostaneš na mjestu,
a da bi negdje stigao, moraš trčati barem duplo brže!”
(c) Alisa u zemlji čudesa
Prije nekog vremena zamoljen sam da održim predavanje analitičari našu tvrtku na temu dizajniranja podatkovnih modela, jer dugo (ponekad i nekoliko godina) sjedeći na projektima gubimo iz vida što se događa oko nas u svijetu IT tehnologija. U našoj tvrtki (slučajno) mnogi projekti ne koriste NoSQL baze podataka (barem za sada), pa sam im u svom predavanju posebno posvetio pozornost na primjeru HBase-a i pokušao prezentaciju materijala orijentirati na one koji ih nikada nisu koristili su radili. Konkretno, ilustrirao sam neke značajke dizajna podatkovnog modela pomoću primjera koji sam pročitao prije nekoliko godina . Prilikom analize primjera usporedio sam nekoliko opcija za rješavanje istog problema kako bih bolje prenio glavne ideje publici.
Nedavno sam se, “bez ičega posla”, zapitao (tome posebno pogoduje dugi svibanjski vikend u karanteni), koliko će teoretski izračuni odgovarati praksi? Zapravo, tako se rodila ideja za ovaj članak. Programer koji već nekoliko dana radi s NoSQL-om možda neće naučiti ništa novo iz njega (i stoga može odmah preskočiti pola članka). Ali za analitičariZa one koji još nisu blisko surađivali s NoSQL-om, mislim da će biti koristan za stjecanje osnovnog razumijevanja značajki dizajniranja modela podataka za HBase.
Analiza primjera
Po mom mišljenju, prije nego počnete koristiti NoSQL baze podataka, morate dobro razmisliti i odvagnuti prednosti i nedostatke. Često se problem najvjerojatnije može riješiti korištenjem tradicionalnih relacijskih DBMS-ova. Stoga je bolje ne koristiti NoSQL bez značajnih razloga. Ako ste ipak odlučili koristiti NoSQL bazu podataka, trebali biste uzeti u obzir da su pristupi dizajnu ovdje nešto drugačiji. Osobito neki od njih mogu biti neobični za one koji su se prethodno bavili samo relacijskim DBMS-ovima (prema mojim opažanjima). Dakle, u "relacijskom" svijetu obično počinjemo modeliranjem problemske domene, a tek onda, ako je potrebno, denormaliziramo model. U NoSQL mi treba odmah uzeti u obzir očekivane scenarije za rad s podacima i početno denormalizirati podatke. Osim toga, postoji niz drugih razlika, o kojima će biti riječi u nastavku.
Razmotrimo sljedeći "sintetički" problem s kojim ćemo nastaviti raditi:
Potrebno je osmisliti strukturu pohranjivanja popisa prijatelja korisnika neke apstraktne društvene mreže. Da pojednostavimo, pretpostavit ćemo da su sve naše veze usmjerene (kao na Instagramu, ne na Linkedinu). Struktura bi vam trebala omogućiti da učinkovito:
- Odgovorite na pitanje čita li korisnik A korisnika B (obrazac čitanja)
- Dopusti dodavanje/uklanjanje veza u slučaju pretplate/odjave korisnika A od korisnika B (predložak promjene podataka)
Naravno, postoji mnogo opcija za rješavanje problema. U običnoj relacijskoj bazi podataka najvjerojatnije bismo jednostavno napravili tablicu odnosa (po mogućnosti tipiziranu ako, na primjer, trebamo pohraniti korisničku grupu: obitelj, posao itd., koja uključuje ovog "prijatelja"), i optimizirati brzina pristupa dodala bi indekse/particioniranje. Najvjerojatnije bi finalni stol izgledao otprilike ovako:
user_id
prijatelj_id
Vasja
Petya
Vasja
Olya
u nastavku, radi jasnoće i boljeg razumijevanja, navodim imena umjesto ID-a
U slučaju HBase, znamo da:
- moguće je učinkovito pretraživanje koje ne rezultira skeniranjem cijele tablice isključivo po ključu
- zapravo, zato je pisanje SQL upita koji su mnogima poznati takvim bazama podataka loša ideja; tehnički, naravno, možete poslati SQL upit sa spojevima i drugom logikom u HBase iz iste Impale, ali koliko će to biti učinkovito...
Stoga smo prisiljeni koristiti ID korisnika kao ključ. I moja prva misao na temu "gdje i kako pohraniti ID prijatelja?" možda ideja da ih pohranim u stupce. Ova najočitija i "naivna" opcija izgledat će otprilike ovako (nazovimo to Opcija 1 (zadano)za daljnje reference):
RowKey
zvučnici
Vasja
1: Petja
2: Olja
3: Daša
Petya
1: Maša
2: Vasja
Ovdje svaki redak odgovara jednom korisniku mreže. Stupci imaju nazive: 1, 2, ... - prema broju prijatelja, au stupcima su pohranjeni ID-ovi prijatelja. Važno je napomenuti da će svaki redak imati različit broj stupaca. U primjeru na gornjoj slici jedan redak ima tri stupca (1, 2 i 3), a drugi samo dva (1 i 2) - ovdje smo sami koristili dva HBase svojstva koja nemaju relacijske baze podataka:
- mogućnost dinamičke promjene sastava stupaca (dodaj prijatelja -> dodaj stupac, ukloni prijatelja -> izbriši stupac)
- različiti redovi mogu imati različite sastave stupaca
Provjerimo usklađenost naše strukture sa zahtjevima zadatka:
- Čitanje podataka: da bismo razumjeli je li Vasya pretplaćen na Olyu, morat ćemo oduzeti cijela linija ključem RowKey = "Vasya" i sortirajte vrijednosti stupaca dok u njima ne "upoznamo" Olyu. Ili iterirajte kroz vrijednosti svih stupaca, "ne upoznajte" Olyu i vratite odgovor False;
- Uređivanje podataka: dodavanje prijatelja: za sličan zadatak također trebamo oduzeti cijela linija koristeći tipku RowKey = “Vasya” za izračun ukupnog broja njegovih prijatelja. Taj ukupan broj prijatelja treba nam da odredimo broj kolone u koju trebamo upisati ID novog prijatelja.
- Promjena podataka: brisanje prijatelja:
- Treba oduzeti cijela linija ključem RowKey = “Vasya” i sortirajte stupce kako biste pronašli onaj u kojem je zabilježen prijatelj kojeg želite izbrisati;
- Zatim, nakon brisanja prijatelja, moramo "prebaciti" sve podatke u jedan stupac kako ne bismo dobili "praznine" u njihovom numeriranju.
Procijenimo sada koliko će ti algoritmi, koje ćemo morati implementirati na strani "uvjetne aplikacije", biti produktivni, koristeći . Označimo veličinu naše hipotetske društvene mreže s n. Tada je najveći broj prijatelja koje jedan korisnik može imati (n-1). Ovo (-1) možemo dalje zanemariti za naše potrebe, budući da je u okviru upotrebe O-simbola nevažno.
- Čitanje podataka: potrebno je oduzeti cijeli red i iterirati kroz sve njegove stupce u limitu. To znači da će gornja procjena troškova biti približno O(n)
- Uređivanje podataka: dodavanje prijatelja: da biste odredili broj prijatelja, morate iterirati kroz sve stupce retka, a zatim umetnuti novi stupac => O(n)
- Promjena podataka: brisanje prijatelja:
- Slično zbrajanju - morate proći kroz sve stupce u ograničenju => O(n)
- Nakon uklanjanja stupaca, moramo ih "pomaknuti". Ako implementirate ovaj "head-on", tada ćete u ograničenju trebati do (n-1) operacija. Ali ovdje i dalje u praktičnom dijelu koristit ćemo drugačiji pristup, koji će implementirati "pseudo-pomak" za fiksni broj operacija - to jest, na to će se trošiti konstantno vrijeme, bez obzira na n. Ovo konstantno vrijeme (točnije O(2)) može se zanemariti u usporedbi s O(n). Pristup je ilustriran na slici ispod: jednostavno kopiramo podatke iz “zadnjeg” stupca u onaj iz kojeg želimo izbrisati podatke, a zatim izbrišemo zadnji stupac:
Ukupno smo u svim scenarijima dobili asimptotsku računsku složenost od O(n).
Vjerojatno ste već primijetili da gotovo uvijek moramo pročitati cijeli redak iz baze podataka, au dva od tri slučaja samo da prođemo kroz sve stupce i izračunamo ukupan broj prijatelja. Stoga, kao pokušaj optimizacije, možete dodati stupac “count” koji pohranjuje ukupan broj prijatelja svakog korisnika mreže. U ovom slučaju, ne možemo pročitati cijeli red kako bismo izračunali ukupan broj prijatelja, već samo jedan stupac “count”. Glavna stvar je ne zaboraviti ažurirati "count" kada manipulirate podacima. Da. poboljšavamo se Opcija 2 (broj):
RowKey
zvučnici
Vasja
1: Petja
2: Olja
3: Daša
brojati: 3
Petya
1: Maša
2: Vasja
brojati: 2
U usporedbi s prvom opcijom:
- Čitanje podataka: dobiti odgovor na pitanje "Čita li Vasja Olju?" ništa se nije promijenilo => O(n)
- Uređivanje podataka: dodavanje prijatelja: Pojednostavili smo umetanje novog prijatelja, budući da sada ne moramo čitati cijeli red i iterirati po njegovim stupcima, već možemo dobiti samo vrijednost stupca “count” itd. odmah odredite broj stupca za umetanje novog prijatelja. To dovodi do smanjenja računske složenosti na O(1)
- Promjena podataka: brisanje prijatelja: Kada brišete prijatelja, također možemo koristiti ovaj stupac za smanjenje broja I/O operacija kada "pomaknemo" podatke jednu ćeliju ulijevo. Ali i dalje postoji potreba za ponavljanjem kroz stupce kako bi se pronašao onaj koji treba izbrisati, tako da => O(n)
- S druge strane, sada kada ažuriramo podatke moramo svaki put ažurirati stupac "count", ali to zahtijeva konstantno vrijeme, što se može zanemariti u okviru O-simbola
Općenito, opcija 2 izgleda malo optimalnija, ali je više poput "evolucije umjesto revolucije". Da bismo napravili “revoluciju” trebat će nam Opcija 3 (u boji).
Okrenimo sve "naglavačke": imenovat ćemo naziv stupca korisnički ID! Ono što će biti napisano u samom stupcu više nam nije važno, neka to bude broj 1 (općenito, tamo se mogu pohraniti korisne stvari, na primjer, grupa "obitelj/prijatelji/itd."). Ovakav pristup može iznenaditi nespremnog “laika” koji nema prethodnog iskustva u radu s NoSQL bazama podataka, ali upravo vam ovaj pristup omogućuje puno učinkovitije korištenje potencijala HBase-a u ovom zadatku:
RowKey
zvučnici
Vasja
Petja: 1
Olja: 1
Daša: 1
Petya
Maša: 1
Vasja: 1
Ovdje dobivamo nekoliko prednosti odjednom. Da bismo ih razumjeli, analizirajmo novu strukturu i procijenimo računsku složenost:
- Čitanje podataka: da biste odgovorili na pitanje je li Vasya pretplaćen na Olyu, dovoljno je pročitati jednu kolonu "Olya": ako postoji, odgovor je Istina, ako nije - Netočno => O(1)
- Uređivanje podataka: dodavanje prijatelja: Dodavanje prijatelja: samo dodajte novi stupac “ID prijatelja” => O(1)
- Promjena podataka: brisanje prijatelja: samo uklonite stupac ID prijatelja => O(1)
Kao što možete vidjeti, značajna prednost ovog modela pohrane je ta što u svim scenarijima koji su nam potrebni, radimo sa samo jednim stupcem, izbjegavajući čitanje cijelog retka iz baze podataka i, štoviše, nabrajanje svih stupaca ovog retka. Tu bismo mogli stati, ali...
Možete biti zbunjeni i otići malo dalje na putu optimizacije performansi i smanjenja I/O operacija prilikom pristupa bazi podataka. Što ako smo pohranili potpunu informaciju o odnosu izravno u samom ključu reda? Odnosno, napraviti složeni ključ poput userID.friendID? U ovom slučaju uopće ne moramo čitati stupce retka (Opcija 4 (redak)):
RowKey
zvučnici
Vasya.Petya
Petja: 1
Vasja.Olja
Olja: 1
Vasja.Daša
Daša: 1
Petya.Masha
Maša: 1
Petya.Vasya
Vasja: 1
Očito je da će procjena svih scenarija manipulacije podacima u takvoj strukturi, kao u prethodnoj verziji, biti O(1). Razlika u odnosu na opciju 3 bit će isključivo u učinkovitosti I/O operacija u bazi podataka.
Pa, posljednji "naklon". Lako je vidjeti da će u opciji 4 ključ retka imati promjenjivu duljinu, što može utjecati na izvedbu (ovdje se sjećamo da HBase pohranjuje podatke kao skup bajtova, a retci u tablicama sortirani su po ključu). Osim toga, imamo separator s kojim će možda trebati rukovati u nekim scenarijima. Da biste eliminirali ovaj utjecaj, možete koristiti hashove iz userID-a i friendID-a, a budući da će oba hash-a imati konstantnu duljinu, možete ih jednostavno spojiti, bez separatora. Tada će podaci u tablici izgledati ovako (Opcija 5 (rasprskavanje)):
RowKey
zvučnici
dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Petja: 1
dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Olja: 1
dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Daša: 1
1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Maša: 1
1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Vasja: 1
Očito je da će algoritamska složenost rada s takvom strukturom u scenarijima koje razmatramo biti ista kao kod opcije 4 - to jest, O(1).
Ukupno, sažmimo sve naše procjene računske složenosti u jednu tablicu:
Dodavanje prijatelja
Provjeravam prijatelja
Uklanjanje prijatelja
Opcija 1 (zadano)
O (n)
O (n)
O (n)
Opcija 2 (broj)
O (1)
O (n)
O (n)
Opcija 3 (stupac)
O (1)
O (1)
O (1)
Opcija 4 (redak)
O (1)
O (1)
O (1)
Opcija 5 (rasprskavanje)
O (1)
O (1)
O (1)
Kao što vidite, čini se da su opcije 3-5 najpoželjnije i teoretski osiguravaju izvršenje svih potrebnih scenarija manipulacije podacima u konstantnom vremenu. U uvjetima našeg zadatka ne postoji izričit zahtjev za dobivanjem popisa svih korisnikovih prijatelja, no u stvarnim projektnim aktivnostima bilo bi dobro da kao dobri analitičari “predvidimo” da bi se takav zadatak mogao pojaviti i "raširi slamku." Stoga su moje simpatije na strani opcije 3. Ali vrlo je vjerojatno da je u stvarnom projektu ovaj zahtjev već mogao biti riješen drugim sredstvima, stoga je, bez opće vizije cjelokupnog problema, bolje ne postavljati konačni zaključci.
Priprema pokusa
Navedene teorijske argumente želio bih provjeriti u praksi – to je bio cilj ideje nastale tijekom produženog vikenda. Da bismo to učinili, potrebno je procijeniti brzinu rada naše “uvjetne aplikacije” u svim opisanim scenarijima korištenja baze podataka, kao i povećanje ovog vremena s povećanjem veličine društvene mreže (n). Ciljni parametar koji nas zanima i koji ćemo mjeriti tijekom eksperimenta je vrijeme koje “uvjetna aplikacija” utroši na jednu “poslovnu operaciju”. Pod "poslovnom transakcijom" mislimo na jedno od sljedećeg:
- Dodavanje jednog novog prijatelja
- Provjera je li korisnik A prijatelj korisnika B
- Uklanjanje jednog prijatelja
Stoga, uzimajući u obzir zahtjeve navedene u početnoj izjavi, scenarij provjere izgleda kako slijedi:
- Snimanje podataka. Nasumično generirajte početnu mrežu veličine n. Da bismo se približili "stvarnom svijetu", broj prijatelja koje svaki korisnik ima također je slučajna varijabla. Izmjerite vrijeme potrebno da naša "uvjetna aplikacija" zapiše sve generirane podatke u HBase. Zatim dobiveno vrijeme podijelite s ukupnim brojem dodanih prijatelja - tako dobivamo prosječno vrijeme za jednu “poslovnu operaciju”
- Čitanje podataka. Za svakog korisnika napravite popis “osobnosti” za koje trebate dobiti odgovor da li je korisnik pretplaćen na njih ili ne. Duljina liste = približno broju prijatelja korisnika, a za polovicu označenih prijatelja odgovor bi trebao biti “Da”, a za drugu polovicu – “Ne”. Provjera se provodi takvim redoslijedom da se izmjenjuju odgovori "Da" i "Ne" (to jest, u svakom drugom slučaju morat ćemo proći kroz sve stupce retka za opcije 1 i 2). Ukupno vrijeme pregleda se zatim dijeli s brojem testiranih prijatelja kako bi se dobilo prosječno vrijeme pregleda po subjektu.
- Brisanje podataka. Ukloni sve prijatelje od korisnika. Štoviše, redoslijed brisanja je slučajan (to jest, mi "miješamo" izvorni popis koji se koristi za bilježenje podataka). Ukupno vrijeme provjere zatim se dijeli s brojem uklonjenih prijatelja kako bi se dobilo prosječno vrijeme po provjeri.
Scenariji se moraju pokrenuti za svaku od 5 opcija podatkovnog modela i za različite veličine društvene mreže kako bi se vidjelo kako se vrijeme mijenja kako raste. Unutar jednog n, veze u mreži i popis korisnika za provjeru moraju, naravno, biti isti za svih 5 opcija.
Za bolje razumijevanje, u nastavku je primjer generiranih podataka za n= 5. Pisani "generator" proizvodi tri ID rječnika kao izlaz:
- prvi je za umetanje
- drugi je za provjeru
- treći – za brisanje
{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 друзей
Kao što vidite, svi ID-ovi veći od 10 u rječniku za provjeru su upravo oni koji će sigurno dati odgovor False. Umetanje, provjera i brisanje "prijatelja" provode se točno redoslijedom navedenim u rječniku.
Eksperiment je proveden na prijenosnom računalu sa sustavom Windows 10, gdje je HBase radio u jednom Docker spremniku, a Python s Jupyter Notebookom u drugom. Dockeru su dodijeljene 2 CPU jezgre i 2 GB RAM-a. Sva logika, i emulacija "uvjetne aplikacije" i "cijevovodi" za generiranje testnih podataka i mjerenje vremena, napisana je u Pythonu. Knjižnica je korištena za rad s HBase-om , za izračunavanje hasheva (MD5) za opciju 5 - hashlib
Uzimajući u obzir računalnu snagu određenog prijenosnog računala, eksperimentalno je odabrano pokretanje za n = 10, 30, …. 170 – kada je ukupno vrijeme rada punog ciklusa testiranja (svi scenariji za sve opcije za sve n) bilo više-manje razumno i prikladno tijekom jedne čajanke (u prosjeku 15 minuta).
Ovdje je potrebno napomenuti da u ovom eksperimentu primarno ne procjenjujemo apsolutne brojke učinka. Čak i relativna usporedba različitih dviju opcija možda neće biti sasvim točna. Sada nas zanima priroda promjene vremena ovisno o n, jer uzimajući u obzir gornju konfiguraciju "testnog postolja", vrlo je teško dobiti vremenske procjene "očišćene" od utjecaja slučajnih i drugih čimbenika ( a takav zadatak nije postavljen).
Rezultat eksperimenta
Prvi test je kako se mijenja vrijeme provedeno u ispunjavanju liste prijatelja. Rezultat je na grafikonu ispod.
Opcije 3-5, očekivano, pokazuju gotovo konstantno vrijeme "poslovne transakcije", koje ne ovisi o rastu veličine mreže i neprimjetnu razliku u performansama.
Opcija 2 također pokazuje konstantnu, ali nešto lošiju izvedbu, gotovo točno 2 puta u odnosu na opcije 3-5. I to ne može nego veseliti, jer je u korelaciji s teorijom - u ovoj verziji broj I/O operacija do/iz HBase-a je točno 2 puta veći. To može poslužiti kao neizravan dokaz da naš ispitni uređaj u načelu pruža dobru točnost.
Opcija 1 također se, očekivano, pokazala najsporijom i pokazuje linearno povećanje vremena utrošenog na međusobno dodavanje na veličinu mreže.
Pogledajmo sada rezultate drugog testa.
Opcije 3-5 ponovno se ponašaju prema očekivanjima - konstantno vrijeme, neovisno o veličini mreže. Opcije 1 i 2 pokazuju linearno povećanje vremena kako se povećava veličina mreže i slične performanse. Štoviše, opcija 2 pokazala se malo sporijom - očito zbog potrebe za lektoriranjem i obradom dodatnog stupca "count", koji postaje uočljiviji kako n raste. Ali ipak ću se suzdržati od donošenja bilo kakvih zaključaka, jer je točnost ove usporedbe relativno niska. Osim toga, ovi omjeri (koja je opcija, 1 ili 2, brža) mijenjali su se od trčanja do trčanja (uz zadržavanje prirode ovisnosti i "izjednačavanja").
Pa, posljednji grafikon je rezultat testiranja uklanjanja.
Opet, ovdje nema iznenađenja. Opcije 3-5 izvode uklanjanje u konstantnom vremenu.
Štoviše, zanimljivo je da opcije 4 i 5, za razliku od prethodnih scenarija, pokazuju osjetno nešto lošiju izvedbu od opcije 3. Navodno je operacija brisanja retka skuplja od operacije brisanja stupca, što je općenito logično.
Opcije 1 i 2, kao što se i očekivalo, pokazuju linearno povećanje vremena. U isto vrijeme, opcija 2 je dosljedno sporija od opcije 1 - zbog dodatne I/O operacije za "održavanje" stupca brojanja.
Opći zaključci eksperimenta:
- Opcije 3-5 pokazuju veću učinkovitost jer iskorištavaju HBase; Štoviše, njihova se izvedba međusobno razlikuje za konstantu i ne ovisi o veličini mreže.
- Razlika između opcija 4 i 5 nije zabilježena. Ali to ne znači da se opcija 5 ne smije koristiti. Vjerojatno je da korišteni eksperimentalni scenarij, uzimajući u obzir karakteristike performansi ispitnog stola, nije omogućio njegovo otkrivanje.
- Priroda povećanja vremena potrebnog za obavljanje “poslovnih operacija” s podacima općenito je potvrdila prethodno dobivene teorijske izračune za sve opcije.
Epilog
Provedene grube eksperimente ne treba uzeti kao apsolutnu istinu. Postoje mnogi čimbenici koji nisu uzeti u obzir i iskrivili su rezultate (ove fluktuacije su posebno vidljive na grafikonima s malom veličinom mreže). Na primjer, brzina štedljivosti, koju koristi happybase, obujam i način implementacije logike koju sam napisao u Pythonu (ne mogu tvrditi da je kod napisan optimalno i da je učinkovito koristio mogućnosti svih komponenti), možda značajke HBase predmemoriranja, pozadinske aktivnosti Windowsa 10 na mom prijenosnom računalu itd. Općenito, možemo pretpostaviti da su svi teorijski izračuni eksperimentalno pokazali svoju valjanost. Pa, ili ih barem nije bilo moguće opovrgnuti takvim "napadom u glavu".
Zaključno, preporuke za sve koji tek počinju dizajnirati podatkovne modele u HBase-u: apstrahirajte prethodno iskustvo rada s relacijskim bazama podataka i zapamtite “zapovijedi”:
- Pri projektiranju polazimo od zadaće i obrazaca manipulacije podacima, a ne od modela domene
- Učinkovit pristup (bez skeniranja cijele tablice) – samo ključem
- Denormalizacija
- Različiti redovi mogu sadržavati različite stupce
- Dinamički sastav zvučnika
Izvor: www.habr.com