Funksjoner ved å designe en datamodell for NoSQL

Innledning

"Du må løpe så fort du kan bare for å holde deg på plass,
og for å komme et sted må du løpe minst dobbelt så fort!»
(c) Alice i Eventyrland

For en tid tilbake ble jeg spurt om å holde et foredrag analytikere vårt selskap om temaet design av datamodeller, fordi når vi sitter på prosjekter i lang tid (noen ganger i flere år) mister vi av syne hva som skjer rundt oss i IT-teknologiens verden. I vårt selskap (det skjer så vidt) bruker mange prosjekter ikke NoSQL-databaser (i hvert fall foreløpig), så i forelesningen min ga jeg spesielt oppmerksomhet til dem ved å bruke eksemplet med HBase og prøvde å orientere presentasjonen av materialet til de som aldri har brukt dem har jobbet. Spesielt illustrerte jeg noen av funksjonene ved design av datamodeller ved å bruke et eksempel jeg leste for flere år siden i artikkelen "Introduction to HB ase Schema Design" av Amandeep Khurana. Når jeg analyserte eksempler, sammenlignet jeg flere alternativer for å løse det samme problemet for bedre å kunne formidle hovedideene til publikum.

Nylig, "ut av ingenting å gjøre," stilte jeg meg selv spørsmålet (den lange mai-helgen i karantene er spesielt gunstig for dette), hvor mye vil teoretiske beregninger samsvare med praksis? Det er faktisk slik ideen til denne artikkelen ble født. En utvikler som har jobbet med NoSQL i flere dager kan ikke lære noe nytt av det (og kan derfor umiddelbart hoppe over halve artikkelen). Men for analytikereFor de som ennå ikke har jobbet tett med NoSQL, tror jeg det vil være nyttig for å få en grunnleggende forståelse av funksjonene ved å designe datamodeller for HBase.

Eksempelanalyse

Etter min mening, før du begynner å bruke NoSQL-databaser, må du tenke nøye gjennom og veie fordeler og ulemper. Ofte kan problemet mest sannsynlig løses ved hjelp av tradisjonelle relasjonelle DBMS-er. Derfor er det bedre å ikke bruke NoSQL uten vesentlige grunner. Hvis du likevel bestemte deg for å bruke en NoSQL-database, bør du ta hensyn til at designtilnærmingene her er noe annerledes. Spesielt noen av dem kan være uvanlige for de som tidligere kun har beskjeftiget seg med relasjonelle DBMS-er (ifølge mine observasjoner). Så i den "relasjonelle" verden starter vi vanligvis med å modellere problemdomenet, og først da, om nødvendig, denormaliserer modellen. I NoSQL vi bør umiddelbart ta hensyn til forventede scenarier for arbeid med data og til å begynne med denormalisere dataene. I tillegg er det en rekke andre forskjeller, som vil bli diskutert nedenfor.

La oss vurdere følgende "syntetiske" problem, som vi vil fortsette å jobbe med:

Det er nødvendig å designe en lagringsstruktur for listen over venner til brukere av et abstrakt sosialt nettverk. For å forenkle, vil vi anta at alle våre forbindelser er rettet (som på Instagram, ikke Linkedin). Strukturen skal tillate deg å effektivt:

• Svar på spørsmålet om bruker A leser bruker B (lesemønster)
• Tillat å legge til/fjerne tilkoblinger ved abonnement/avmelding av bruker A fra bruker B (dataendringsmal)

Selvfølgelig er det mange alternativer for å løse problemet. I en vanlig relasjonsdatabase vil vi mest sannsynlig ganske enkelt lage en tabell over relasjoner (eventuelt typisk hvis vi for eksempel trenger å lagre en brukergruppe: familie, jobb osv., som inkluderer denne "vennen"), og for å optimalisere tilgangshastighet vil legge til indekser/partisjonering. Mest sannsynlig vil finalebordet se omtrent slik ut:

user_id
venn_id

Vasja
Petya

Vasja
Оля

heretter, for klarhet og bedre forståelse, vil jeg angi navn i stedet for ID-er

Når det gjelder HBase, vet vi at:

• effektivt søk som ikke resulterer i en full tabellskanning er mulig utelukkende med nøkkel
  • Faktisk er det derfor en dårlig idé å skrive SQL-spørringer som er kjent for mange til slike databaser; teknisk sett kan du selvfølgelig sende en SQL-spørring med Joins og annen logikk til HBase fra samme Impala, men hvor effektivt vil det være...

Derfor er vi tvunget til å bruke bruker-ID som nøkkel. Og min første tanke om emnet "hvor og hvordan lagre venners IDer?" kanskje en idé å lagre dem i kolonner. Dette mest åpenbare og "naive" alternativet vil se omtrent slik ut (la oss kalle det Alternativ 1 (standard)for videre referanse):

RowKey
høyttalere

Vasja
1: Petya
2: Olya
3: Dasha

Petya
1: Masha
2: Vasya

Her tilsvarer hver linje én nettverksbruker. Kolonnene har navn: 1, 2, ... - i henhold til antall venner, og ID-ene til venner lagres i kolonnene. Det er viktig å merke seg at hver rad vil ha et annet antall kolonner. I eksemplet i figuren over har den ene raden tre kolonner (1, 2 og 3), og den andre har kun to (1 og 2) - her brukte vi selv to HBase-egenskaper som relasjonsdatabaser ikke har:

• muligheten til å dynamisk endre sammensetningen av kolonner (legg til en venn -> legg til en kolonne, fjern en venn -> slett en kolonne)
• forskjellige rader kan ha forskjellige kolonnesammensetninger

La oss sjekke strukturen vår for samsvar med kravene til oppgaven:

• Leser data: for å forstå om Vasya abonnerer på Olya, må vi trekke fra hele linjen med nøkkelen RowKey = "Vasya" og sorter gjennom kolonneverdiene til vi "møter" Olya i dem. Eller iterer gjennom verdiene til alle kolonnene, "ikke møte" Olya og returner svaret False;
• Redigering av data: legger til en venn: for en lignende oppgave må vi også trekke fra hele linjen ved å bruke tasten RowKey = “Vasya” for å telle det totale antallet venner. Vi trenger dette totale antallet venner for å bestemme nummeret på kolonnen der vi må skrive ned IDen til den nye vennen.
• Endre data: sletter en venn:
  • Trenger å trekke fra hele linjen med tasten RowKey = “Vasya” og sorter gjennom kolonnene for å finne den der vennen som skal slettes er registrert;
  • Deretter, etter å ha slettet en venn, må vi "skifte" alle dataene til en kolonne for ikke å få "hull" i nummereringen.

La oss nå evaluere hvor produktive disse algoritmene, som vi må implementere på "betinget applikasjon"-siden, vil være ved å bruke O-symbolikk. La oss betegne størrelsen på vårt hypotetiske sosiale nettverk som n. Da er det maksimale antallet venner en bruker kan ha (n-1). Vi kan videre neglisjere dette (-1) for våre formål, siden det innenfor rammen av bruken av O-symboler er uviktig.

• Leser data: det er nødvendig å trekke fra hele linjen og iterere gjennom alle kolonnene i grensen. Dette betyr at det øvre kostnadsestimatet vil være omtrent O(n)
• Redigering av data: legger til en venn: for å bestemme antall venner, må du iterere gjennom alle kolonnene i raden, og deretter sette inn en ny kolonne => O(n)
• Endre data: sletter en venn:
  • I likhet med å legge til - du må gå gjennom alle kolonnene i grensen => O(n)
  • Etter å ha fjernet kolonnene, må vi "flytte" dem. Hvis du implementerer dette "head-on", vil du i grensen trenge opptil (n-1) operasjoner. Men her og videre i den praktiske delen vil vi bruke en annen tilnærming, som vil implementere et "pseudo-skift" for et fast antall operasjoner - det vil si at konstant tid vil bli brukt på det, uavhengig av n. Denne konstante tiden (O(2) for å være nøyaktig) kan neglisjeres sammenlignet med O(n). Tilnærmingen er illustrert i figuren nedenfor: vi kopierer ganske enkelt dataene fra den "siste" kolonnen til den som vi ønsker å slette data fra, og sletter deretter den siste kolonnen:
    

Totalt mottok vi i alle scenarier en asymptotisk beregningskompleksitet på O(n).
Du har sikkert allerede lagt merke til at vi nesten alltid må lese hele raden fra databasen, og i to tilfeller av tre, bare for å gå gjennom alle kolonnene og beregne det totale antallet venner. Derfor, som et forsøk på optimalisering, kan du legge til en "telling"-kolonne, som lagrer det totale antallet venner til hver nettverksbruker. I dette tilfellet kan vi ikke lese hele raden for å beregne det totale antallet venner, men bare lese en "telling"-kolonne. Det viktigste er ikke å glemme å oppdatere "telling" når du manipulerer data. At. vi blir forbedret Alternativ 2 (antall):

RowKey
høyttalere

Vasja
1: Petya
2: Olya
3: Dasha
teller: 3

Petya
1: Masha
2: Vasya

teller: 2

Sammenlignet med det første alternativet:

• Leser data: for å få svar på spørsmålet "Leser Vasya Olya?" ingenting har endret seg => O(n)
• Redigering av data: legger til en venn: Vi har forenklet innsettingen av en ny venn, siden vi nå ikke trenger å lese hele linjen og iterere over dens kolonner, men kan bare få verdien av "count"-kolonnen osv. umiddelbart bestemme kolonnenummeret for å sette inn en ny venn. Dette fører til en reduksjon i beregningskompleksitet til O(1)
• Endre data: sletter en venn: Når du sletter en venn, kan vi også bruke denne kolonnen til å redusere antall I/O-operasjoner når du "skifter" dataene én celle til venstre. Men behovet for å iterere gjennom kolonnene for å finne den som må slettes gjenstår fortsatt, så => ​​O(n)
• På den annen side, nå når vi oppdaterer data, må vi oppdatere "telling"-kolonnen hver gang, men dette tar konstant tid, noe som kan neglisjeres innenfor rammen av O-symboler

Generelt virker alternativ 2 litt mer optimalt, men det er mer som "evolusjon i stedet for revolusjon." For å gjøre en "revolusjon" trenger vi Alternativ 3 (kol.).
La oss snu alt "opp ned": vi tildeler kolonnenavn bruker-ID! Hva som skal skrives i selve spalten er ikke lenger viktig for oss, la det være tallet 1 (generelt sett kan nyttige ting lagres der, for eksempel gruppen "familie/venner/etc."). Denne tilnærmingen kan overraske den uforberedte "lekmannen" som ikke har noen tidligere erfaring med å jobbe med NoSQL-databaser, men det er nettopp denne tilnærmingen som lar deg bruke potensialet til HBase i denne oppgaven mye mer effektivt:

RowKey
høyttalere

Vasja
Petya: 1
Olya: 1
Dasha: 1

Petya
Masha: 1
Vasya: 1

Her får vi flere fordeler på en gang. For å forstå dem, la oss analysere den nye strukturen og estimere beregningskompleksiteten:

• Leser data: for å svare på spørsmålet om Vasya abonnerer på Olya, er det nok å lese en kolonne "Olya": hvis den er der, så er svaret sant, hvis ikke - usant => O(1)
• Redigering av data: legger til en venn: Legge til en venn: bare legg til en ny kolonne "Venne-ID" => O(1)
• Endre data: sletter en venn: bare fjern venne-ID-kolonnen => O(1)

Som du kan se, er en betydelig fordel med denne lagringsmodellen at vi i alle scenariene vi trenger, opererer med kun én kolonne, og unngår å lese hele raden fra databasen og dessuten telle opp alle kolonnene i denne raden. Vi kunne stoppet der, men...

Du kan bli forvirret og gå litt lenger langs veien for å optimalisere ytelsen og redusere I/O-operasjoner når du får tilgang til databasen. Hva om vi lagret den fullstendige relasjonsinformasjonen direkte i selve radtasten? Det vil si, gjøre nøkkelen til en sammensatt nøkkel som userID.friendID? I dette tilfellet trenger vi ikke engang å lese kolonnene på linjen i det hele tatt (Alternativ 4 (rad)):

RowKey
høyttalere

Vasya.Petya
Petya: 1

Vasya.Olya
Olya: 1

Vasya.Dasha
Dasha: 1

Petya.Masha
Masha: 1

Petya.Vasya
Vasya: 1

Selvsagt vil vurderingen av alle datamanipulasjonsscenarier i en slik struktur, som i forrige versjon, være O(1). Forskjellen med alternativ 3 vil utelukkende ligge i effektiviteten til I/O-operasjoner i databasen.

Vel, den siste "buen". Det er lett å se at i alternativ 4 vil radnøkkelen ha variabel lengde, noe som muligens kan påvirke ytelsen (her husker vi at HBase lagrer data som et sett med byte og rader i tabeller sorteres etter nøkkel). I tillegg har vi en separator som kanskje må håndteres i enkelte scenarier. For å eliminere denne påvirkningen kan du bruke hashes fra bruker-ID og friendID, og ​​siden begge hashene vil ha en konstant lengde, kan du enkelt sette dem sammen, uten separator. Da vil dataene i tabellen se slik ut (Alternativ 5 (hash)):

RowKey
høyttalere

dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Petya: 1

dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Olya: 1

dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Dasha: 1

1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Masha: 1

1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Vasya: 1

Det er klart at den algoritmiske kompleksiteten ved å jobbe med en slik struktur i scenariene vi vurderer vil være den samme som for alternativ 4 - det vil si O(1).
Til sammen, la oss oppsummere alle våre estimater av beregningskompleksitet i én tabell:

Legger til en venn
Sjekker en venn
Fjerner en venn

Alternativ 1 (standard)
O (n)
O (n)
O (n)

Alternativ 2 (telling)
O (1)
O (n)
O (n)

Alternativ 3 (kolonne)
O (1)
O (1)
O (1)

Alternativ 4 (rad)
O (1)
O (1)
O (1)

Alternativ 5 (hash)
O (1)
O (1)
O (1)

Som du kan se, ser alternativene 3-5 ut til å være de mest å foretrekke og sikrer teoretisk utførelse av alle nødvendige datamanipulasjonsscenarier på konstant tid. I vilkårene for oppgaven vår er det ikke noe eksplisitt krav om å få en liste over alle brukerens venner, men i reelle prosjektaktiviteter vil det være bra for oss som gode analytikere å "forutse" at en slik oppgave kan oppstå og "spre et sugerør." Derfor er mine sympatier på siden av alternativ 3. Men det er ganske sannsynlig at i et reelt prosjekt kunne denne forespørselen allerede vært løst på andre måter, derfor, uten en generell visjon om hele problemet, er det bedre å ikke gjøre endelige konklusjoner.

Forberedelse av eksperimentet

Jeg vil gjerne teste de ovennevnte teoretiske argumentene i praksis – dette var målet med ideen som oppsto i langhelgen. For å gjøre dette er det nødvendig å evaluere driftshastigheten til vår "betingede applikasjon" i alle beskrevne scenarier for bruk av databasen, samt økningen i denne tiden med økende størrelse på det sosiale nettverket (n). Målparameteren som interesserer oss og som vi vil måle i løpet av eksperimentet, er tiden som brukes av den "betingede applikasjonen" for å utføre én "forretningsoperasjon". Med "forretningstransaksjon" mener vi ett av følgende:

• Legger til en ny venn
• Sjekker om bruker A er en venn av bruker B
• Fjerner en venn

Med hensyn til kravene som er skissert i den første erklæringen, fremstår verifikasjonsscenarioet som følger:

• Dataregistrering. Generer tilfeldig et innledende nettverk av størrelse n. For å komme nærmere den "virkelige verden", er antallet venner hver bruker har også en tilfeldig variabel. Mål tiden vår "betingede applikasjon" skriver alle genererte data til HBase. Del deretter den resulterende tiden med det totale antallet venner som er lagt til - slik får vi gjennomsnittstiden for én "forretningsoperasjon"
• Leser data. For hver bruker, lag en liste over "personligheter" som du trenger for å få svar på om brukeren abonnerer på dem eller ikke. Lengden på listen = omtrentlig antall brukeres venner, og for halvparten av de sjekkede vennene skal svaret være "Ja", og for den andre halvparten - "Nei". Kontrollen utføres i en slik rekkefølge at svarene "Ja" og "Nei" veksler (det vil si at vi i hvert andre tilfelle må gå gjennom alle kolonnene på linjen for alternativene 1 og 2). Den totale screeningtiden deles deretter på antall venner som er testet for å få gjennomsnittlig screeningtid per fag.
• Sletter data. Fjern alle venner fra brukeren. Dessuten er slettingsrekkefølgen tilfeldig (det vil si at vi "blander" den opprinnelige listen som ble brukt til å registrere dataene). Den totale sjekktiden blir deretter delt på antall venner som er fjernet for å få gjennomsnittlig tid per sjekk.

Scenariene må kjøres for hvert av de 5 datamodellalternativene og for forskjellige størrelser på det sosiale nettverket for å se hvordan tiden endrer seg etter hvert som den vokser. Innen en n må tilkoblinger i nettverket og listen over brukere som skal sjekkes selvfølgelig være lik for alle 5 alternativene.
For en bedre forståelse, nedenfor er et eksempel på genererte data for n= 5. Den skrevne "generatoren" produserer tre ID-ordbøker som utdata:

• den første er for innsetting
• den andre er for kontroll
• tredje – for sletting

{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 друзей

Som du kan se, er alle IDer som er større enn 10 000 i ordboken for kontroll, nettopp de som helt sikkert vil gi svaret False. Innsetting, kontroll og sletting av "venner" utføres nøyaktig i den rekkefølgen som er spesifisert i ordboken.

Eksperimentet ble utført på en bærbar datamaskin som kjørte Windows 10, der HBase kjørte i en Docker-beholder, og Python med Jupyter Notebook kjørte i den andre. Docker ble tildelt 2 CPU-kjerner og 2 GB RAM. All logikken, som emuleringen av den "betingede applikasjonen" og "rørledningen" for generering av testdata og måling av tid, ble skrevet i Python. Biblioteket ble brukt til å jobbe med HBase happybase, for å beregne hashes (MD5) for alternativ 5 - hashlib

Med tanke på datakraften til en bestemt bærbar PC, ble en lansering for n = 10, 30, … eksperimentelt valgt. 170 – når den totale driftstiden for hele testsyklusen (alle scenarier for alle alternativer for alle n) var enda mer eller mindre rimelig og passe under ett teselskap (i gjennomsnitt 15 minutter).

Her er det nødvendig å bemerke at vi i dette forsøket ikke først og fremst vurderer absolutte ytelsestall. Selv en relativ sammenligning av forskjellige to alternativer er kanskje ikke helt riktig. Nå er vi interessert i arten av endringen i tid avhengig av n, siden man tar i betraktning ovennevnte konfigurasjon av "teststanden", er det veldig vanskelig å få tidsestimater "ryddet" for påvirkningen av tilfeldige og andre faktorer ( og en slik oppgave ble ikke satt).

Eksperimentresultat

Den første testen er hvordan tiden brukt på å fylle ut vennelisten endres. Resultatet er i grafen under.

Alternativer 3-5, som forventet, viser en nesten konstant "forretningstransaksjon"-tid, som ikke er avhengig av veksten i nettverksstørrelsen og en utydelig forskjell i ytelse.
Alternativ 2 viser også konstant, men litt dårligere ytelse, nesten nøyaktig 2 ganger i forhold til alternativene 3-5. Og dette kan ikke annet enn å glede seg, siden det korrelerer med teori - i denne versjonen er antallet I/O-operasjoner til/fra HBase nøyaktig 2 ganger større. Dette kan tjene som indirekte bevis på at vår testbenk i prinsippet gir god nøyaktighet.
Alternativ 1 viser seg også, som forventet, å være den tregeste og viser en lineær økning i tiden brukt på å legge hverandre til størrelsen på nettverket.
La oss nå se på resultatene av den andre testen.

Alternativ 3-5 oppfører seg igjen som forventet - konstant tid, uavhengig av størrelsen på nettverket. Alternativ 1 og 2 viser en lineær økning i tid ettersom nettverksstørrelsen øker og lignende ytelse. Dessuten viser alternativ 2 seg å være litt tregere - tilsynelatende på grunn av behovet for å korrekturlese og behandle den ekstra "telling"-kolonnen, som blir mer merkbar ettersom n vokser. Men jeg vil likevel avstå fra å trekke noen konklusjoner, siden nøyaktigheten i denne sammenligningen er relativt lav. I tillegg endres disse forholdstallene (hvilket alternativ, 1 eller 2, er raskere) fra løp til løp (samtidig som man opprettholder avhengighetens natur og "går nakke og nakke").

Vel, den siste grafen er resultatet av fjerningstesting.

Igjen, ingen overraskelser her. Alternativer 3-5 utfører fjerning i konstant tid.
Dessuten, interessant nok, viser alternativene 4 og 5, i motsetning til de tidligere scenariene, merkbart litt dårligere ytelse enn alternativ 3. Tilsynelatende er radslettingsoperasjonen dyrere enn kolonneslettingsoperasjonen, som generelt er logisk.

Alternativ 1 og 2 viser som forventet en lineær økning i tid. Samtidig er alternativ 2 konsekvent tregere enn alternativ 1 - på grunn av den ekstra I/O-operasjonen for å "vedlikeholde" tellekolonnen.

Generelle konklusjoner av eksperimentet:

• Alternativene 3-5 viser større effektivitet når de drar nytte av HBase; Dessuten er ytelsen deres forskjellig i forhold til hverandre med en konstant og avhenger ikke av størrelsen på nettverket.
• Forskjellen mellom alternativ 4 og 5 ble ikke registrert. Men dette betyr ikke at alternativ 5 ikke skal brukes. Det er sannsynlig at det eksperimentelle scenariet som ble brukt, tatt i betraktning ytelsesegenskapene til testbenken, ikke tillot det å bli oppdaget.
• Arten av økningen i tiden som kreves for å utføre "forretningsoperasjoner" med data bekreftet generelt de tidligere oppnådde teoretiske beregningene for alle alternativer.

Epilog

De grove eksperimentene som utføres bør ikke tas som absolutt sannhet. Det er mange faktorer som ikke ble tatt i betraktning og forvrengte resultatene (disse svingningene er spesielt synlige i grafene med liten nettverksstørrelse). For eksempel, hastigheten på sparsommelighet, som brukes av happybase, volumet og metoden for å implementere logikken som jeg skrev i Python (jeg kan ikke påstå at koden ble skrevet optimalt og effektivt brukte egenskapene til alle komponentene), kanskje funksjonene til HBase-bufring, bakgrunnsaktivitet til Windows 10 på min bærbare datamaskin, etc. Generelt kan vi anta at alle teoretiske beregninger eksperimentelt har vist sin gyldighet. Vel, eller i det minste var det ikke mulig å tilbakevise dem med et slikt "head-on-angrep".

Avslutningsvis, anbefalinger til alle som akkurat har begynt å designe datamodeller i HBase: Abstrakt fra tidligere erfaring med relasjonsdatabaser og husk "kommandoer":

• Når vi designer, går vi ut fra oppgaven og mønstrene for datamanipulering, og ikke fra domenemodellen
• Effektiv tilgang (uten full tabellskanning) – kun med nøkkel
• Denormalisering
• Ulike rader kan inneholde forskjellige kolonner
• Dynamisk sammensetning av høyttalere

Kilde: www.habr.com