Funktioner ved at designe en datamodel til NoSQL

Indledning

"Du skal løbe så hurtigt som muligt bare for at blive på din plads,"
og for at komme et sted hen, skal man løbe mindst dobbelt så hurtigt!”
(c) Alice i Eventyrland

For noget tid siden blev jeg bedt om at holde et foredrag analytikere vores virksomhed om emnet design af datamodeller, fordi når vi sidder i projekter i lang tid (nogle gange i flere år), mister vi overblikket over, hvad der sker omkring os i IT-teknologiernes verden. I vores virksomhed (det sker bare sådan) bruger mange projekter ikke NoSQL-databaser (i hvert fald ikke endnu), så i mit foredrag lagde jeg særlig vægt på dem ved hjælp af HBase som eksempel og forsøgte at fokusere præsentationen af ​​materialet på dem, der aldrig har arbejdet med dem. Jeg illustrerede især nogle af funktionerne i datamodeldesign ved hjælp af et eksempel, jeg læste for flere år siden. i artiklen “Introduktion til HB ase Schema Design” af Amandeep Khurana. Når jeg analyserede eksempler, sammenlignede jeg flere løsninger på det samme problem for bedre at formidle hovedideerne til publikum.

For nylig, "af kedsomhed", spurgte jeg mig selv (de lange majferier i karantænetilstand er særligt befordrende for dette), i hvilken grad vil teoretiske beregninger stemme overens med praksis? Det er faktisk sådan, ideen til denne artikel opstod. En udvikler, der har arbejdet med NoSQL i et stykke tid, lærer måske ikke noget nyt af det (og springer måske derfor halvdelen af ​​artiklen over). Men for analytikere, som endnu ikke har arbejdet tæt med NoSQL, tror jeg, at det vil være nyttigt til at få en grundlæggende forståelse af de specifikke forhold ved design af datamodeller til HBase.

Eksempelanalyse

Efter min mening, før du begynder at bruge NoSQL-databaser, skal du tænke dig grundigt om og afveje fordele og ulemper. Ofte kan problemet højst sandsynligt løses ved hjælp af traditionel relationel DBMS. Derfor er det bedre ikke at bruge NoSQL uden gode grunde. Hvis der er truffet en beslutning om at bruge en NoSQL-database, skal det tages i betragtning, at designtilgangene her er noget forskellige. Nogle af dem kan være særligt ukendte for dem, der tidligere kun har beskæftiget sig med relationelle DBMS'er (ud fra mine observationer). Så i den "relationelle" verden starter vi normalt med at modellere emneområdet, og først derefter, om nødvendigt, denormaliserer vi modellen. I NoSQL vi skal straks tage højde for de forventede scenarier for arbejde med data og i første omgang denormalisere dataene. Derudover er der en række andre forskelle, som vil blive beskrevet nedenfor.

Lad os betragte følgende "syntetiske" problem, som vi vil fortsætte med at arbejde med:

Det er nødvendigt at designe en struktur til lagring af en liste over venner hos brugere af et abstrakt socialt netværk. For enkelhedens skyld antager vi, at alle vores forbindelser er dirigerede (ligesom på Instagram, ikke på Linkedin). Strukturen skal muliggøre effektiv:

• Besvar spørgsmålet om bruger A læser bruger B (læsemønster)
• Tillad tilføjelse/fjernelse af links, når bruger A abonnerer/afmelder sig fra bruger B (skabelon til dataændring)

Der er selvfølgelig mange muligheder for at løse problemet. I en normal relationel database ville vi højst sandsynligt bare lave en tabel med links (muligvis typebestemte, hvis vi f.eks. har brug for at gemme en brugergruppe: familie, arbejde osv., som inkluderer en given "ven"), og for at optimere adgangshastigheden ville vi tilføje indeks/partitionering. Mest sandsynligt vil finaletabellen se nogenlunde sådan ud:

user_id
ven_id

Vasya
Petya

Vasya
Olya

her og videre for klarhedens skyld og bedre forståelse i stedet for ID vil jeg angive navne

I tilfældet med HBase ved vi, at:

• effektiv søgning, der ikke resulterer i en fuld tabelscanning, er mulig udelukkende via nøgle
  • Faktisk er det derfor, det er en dårlig idé at skrive de SQL-forespørgsler, som mange er vant til til sådanne databaser; Teknisk set kan du selvfølgelig sende en SQL-forespørgsel med Joins og anden logik til HBase fra den samme Impala, men hvor effektivt vil det være...

Derfor er vi tvunget til at bruge bruger-ID'et som nøgle. Og den første tanke om emnet "hvor og hvordan man opbevarer venners ID'er?" Måske en idé at gemme dem i kolonner. Denne mest oplagte og "naive" mulighed vil se nogenlunde sådan ud (lad os kalde den Mulighed 1 (standard), til fremtidig reference):

Rækkenøgle
højtalere

Vasya
1: Petja
2: Olya
3: Dasha

Petya
1: Masha
2: Vasja

Her svarer hver linje til én netværksbruger. Kolonnerne har navne: 1, 2, … — i henhold til antallet af venner, og kolonnerne gemmer vennernes ID'er. Det er vigtigt at bemærke, at hver række vil have et forskelligt antal kolonner. I eksemplet i figuren ovenfor har én række tre kolonner (1, 2 og 3), og den anden kun to (1 og 2) - her udnyttede vi selv to egenskaber ved HBase, som relationelle databaser ikke har:

• muligheden for dynamisk at ændre sammensætningen af ​​kolonner (tilføj en ven -> tilføj en kolonne, fjern en ven -> fjern en kolonne)
• Forskellige rækker kan have forskellige kolonnesammensætninger

Lad os kontrollere, om vores struktur overholder opgavekravene:

• Læser dataFor at forstå, om Vasya abonnerer på Olya, skal vi læse hele linjen med nøglen RowKey = "Vasya" og iterer gennem kolonneværdierne, indtil vi "møder" Olya i dem. Eller iterer over værdierne i alle kolonner, "mød ikke" Olya og returner svaret Falsk;
• Rediger detaljer: tilføj ven: for et lignende problem skal vi også trække fra hele linjen med nøglen RowKey = "Vasya" for at tælle det samlede antal af hans venner. Vi skal bruge dette samlede antal venner for at bestemme kolonnenummeret, hvor den nye vens ID skal skrives.
• Ændre oplysninger: slet ven:
  • Det er nødvendigt at trække fra hele linjen ved hjælp af nøglen RowKey = "Vasya" og gå gennem kolonnerne for at finde den, hvor den ven, der slettes, er registreret;
  • Dernæst, efter at vi har slettet en ven, skal vi "flytte" alle dataene til én kolonne for at undgå "huller" i deres nummerering.

Lad os nu evaluere, hvor produktive disse algoritmer, som vi skal implementere på siden af ​​den "betingede applikation", vil være ved at bruge O-symbolik. Lad os betegne størrelsen af ​​vores hypotetiske sociale netværk som n. Så er det maksimale antal venner, som en bruger kan have, (n-1). Vi kan se bort fra dette (-1) i vores efterfølgende tilfælde, da det ikke er essentielt inden for rammerne af brugen af ​​O-symboler.

• Læser dataDet er nødvendigt at trække hele linjen fra og gennemgå alle dens kolonner inden for grænsen. Det betyder, at det øvre omkostningsestimat vil være omtrent O(n)
• Rediger detaljer: tilføj venFor at bestemme antallet af venner skal du iterere gennem alle kolonnerne i rækken og derefter indsætte en ny kolonne => O(n)
• Ændre oplysninger: slet ven:
  • Ligesom ved at lægge til - det er nødvendigt at gennemgå alle kolonner i limit => O(n)
  • Efter at have slettet kolonnerne, skal vi "flytte" dem. Hvis vi implementerer dette "frontalt", vil vi i grænsen have brug for op til (n-1) flere operationer. Men her og videre i den praktiske del vil vi anvende en anden tilgang, som vil implementere "pseudoskiftet" i et fast antal operationer – det vil sige, at det vil tage en konstant tid uanset n. Denne konstante tid (for at være præcis, O(2)) kan negligeres i forhold til O(n). Fremgangsmåden er illustreret i figuren nedenfor: Vi kopierer blot dataene fra den "sidste" kolonne til den, hvorfra vi skal slette data, og sletter derefter den sidste kolonne:
    

Som følge heraf opnåede vi i alle scenarier en asymptotisk beregningskompleksitet på O(n).
Du har sikkert allerede bemærket, at vi næsten altid er nødt til at læse hele linjen fra databasen, og i to ud af tre tilfælde, bare for at gennemgå alle kolonnerne og tælle det samlede antal venner. Derfor kan du, som et forsøg på optimering, tilføje en "antal"-kolonne, hvor du kan gemme det samlede antal venner for hver netværksbruger. I dette tilfælde kan vi undgå at læse hele linjen for at beregne det samlede antal venner og kun læse én kolonne, “antal”. Det vigtigste er ikke at glemme at opdatere "tællingen", når man manipulerer data. At. vi får en forbedret en Mulighed 2 (antal):

Rækkenøgle
højtalere

Vasya
1: Petja
2: Olya
3: Dasha
antal: 3

Petya
1: Masha
2: Vasja

antal: 2

Sammenlignet med den første mulighed:

• Læser data: for at få svar på spørgsmålet "Læser Vasya Olya?" intet har ændret sig => O(n)
• Rediger detaljer: tilføj venVi har forenklet indsættelsen af ​​en ny ven, da vi nu ikke behøver at læse hele linjen og iterere gennem dens kolonner, men kun kan få værdien af ​​kolonnen "count" osv. og straks bestemme kolonnenummeret for indsættelse af en ny ven. Dette resulterer i en reduktion i beregningskompleksitet til O(1)
• Ændre oplysninger: slet venNår vi sletter en ven, kan vi også bruge denne kolonne til at reducere antallet af I/O-operationer, når vi "flytter" data én celle til venstre. Men behovet for at iterere gennem kolonnerne for at finde den, der skal slettes, er stadig til stede, så => O(n)
• På den anden side, når vi nu opdaterer data, skal vi opdatere "count"-kolonnen hver gang, men dette tager konstant tid, hvilket kan negligeres inden for den O-symbolske ramme.

Samlet set virker mulighed 2 en smule mere optimal, men den minder mere om "evolution i stedet for revolution". For at lave en "revolution" har vi brug for Mulighed 3 (kolonne).
Lad os vende alt på hovedet: lad os udnævne kolonnenavn bruger-id! Hvad der vil blive skrevet i selve kolonnen er ikke vigtigt for os, lad det være nummer 1 (generelt kan nyttige ting gemmes der, for eksempel gruppen "familie/venner/osv."). Denne tilgang kan måske overraske en uforberedt "lægmand", der ikke har erfaring med at arbejde med NoSQL-databaser før, men det er denne tilgang, der gør det muligt at udnytte HBases potentiale i denne opgave meget mere effektivt:

Rækkenøgle
højtalere

Vasya
Petya: 1
Olya: 1
Dasha: 1

Petya
Masha: 1
Vasja: 1

Her får vi flere fordele på én gang. For at forstå dem, lad os analysere den nye struktur og estimere den beregningsmæssige kompleksitet:

• Læser dataFor at besvare spørgsmålet om, hvorvidt Vasya abonnerer på Olya, er det nok at læse én kolonne "Olya": hvis ja, så er svaret sandt, hvis ikke – falsk => O(1)
• Rediger detaljer: tilføj venTilføjelse af en ven: tilføj blot en ny kolonne "ven-ID" => O(1)
• Ændre oplysninger: slet ven: fjern blot kolonnen "ven-ID" => O(1)

Som vi kan se, er en betydelig fordel ved denne lagringsmodel, at vi i alle de scenarier, vi har brug for, kun opererer med én kolonne, hvilket undgår at læse hele rækken fra databasen og, endnu mere, at gennemgå alle kolonnerne i denne række. Vi kunne stoppe her, men...

Du kan blive forvirret og gå lidt videre ad vejen med at optimere ydeevnen og reducere I/O-operationer, når du tilgår databasen. Hvad hvis vi gemte alle relationsoplysningerne direkte i selve rækkenøglen? Det vil sige, lav nøglesammensætningen som userID.friendID? I dette tilfælde behøver vi ikke engang at læse kolonnerne i rækken (Mulighed 4 (række)):

Rækkenøgle
højtalere

Vasya.Petya
Petya: 1

Vasya.Olya
Olya: 1

Vasya.Dasha
Dasha: 1

Petya.Masha
Masha: 1

Petya.Vasya
Vasja: 1

Det er klart, at evalueringen af ​​alle datamanipulationsscenarier i en sådan struktur, som i den tidligere version, vil være O(1). Forskellen i forhold til mulighed 3 vil udelukkende ligge i effektiviteten af ​​input/output-operationer i databasen.

Nå, og den sidste "bue". Det er let at se, at i mulighed 4 vil vores rækkenøgle have en variabel længde, hvilket muligvis kan påvirke ydeevnen (husk at HBase gemmer data som et sæt bytes, og rækkerne i tabellerne er sorteret efter nøgle). Plus vi har en separator, der muligvis skal håndteres i visse scenarier. For at eliminere denne indflydelse kan du bruge hashes fra bruger-ID og ven-ID, og ​​da begge hashes vil have en konstant længde, kan du blot sammenkæde dem uden en separator. Så vil dataene i tabellen se sådan ud (Mulighed 5 (hash)):

Rækkenøgle
højtalere

dc084ef00e94aef49be885f9b01f51c01918fa783851db0dc1f72f83d33a5994
Petya: 1

dc084ef00e94aef49be885f9b01f51c0f06b7714b5ba522c3cf51328b66fe28a
Olya: 1

dc084ef00e94aef49be885f9b01f51c00d2c2e5d69df6b238754f650d56c896a
Dasha: 1

1918fa783851db0dc1f72f83d33a59949ee3309645bd2c0775899fca14f311e1
Masha: 1

1918fa783851db0dc1f72f83d33a5994dc084ef00e94aef49be885f9b01f51c0
Vasja: 1

Den algoritmiske kompleksitet ved at arbejde med en sådan struktur i henhold til de scenarier, vi overvejer, vil naturligvis være den samme som for mulighed 4 – det vil sige O(1).
Så lad os samle alle vores estimater for beregningskompleksitet i én tabel:

Tilføjelse af en ven
Tjekker en ven
Fjernelse af en ven

Mulighed 1 (standard)
O (n)
O (n)
O (n)

Mulighed 2 (antal)
O (1)
O (n)
O (n)

Mulighed 3 (kolonne)
O (1)
O (1)
O (1)

Mulighed 4 (række)
O (1)
O (1)
O (1)

Mulighed 5 (hash)
O (1)
O (1)
O (1)

Som det kan ses, ser mulighed 3-5 ud til at være de mest foretrukne og sikrer teoretisk set udførelsen af ​​alle nødvendige datamanipulationsscenarier i konstant tid. I vores problemformulering er der ikke noget eksplicit krav om at indhente en liste over alle brugerens venner, men i virkelige projektaktiviteter ville vi som gode analytikere gøre klogt i at "forudse", at en sådan opgave kan opstå, og "lægge halmstrå ud". Derfor har jeg sympati for mulighed 3. Men det er meget muligt, at denne anmodning i et rigtigt projekt allerede kunne være blevet løst på andre måder, så uden en generel vision for hele opgaven er det bedre ikke at drage endelige konklusioner.

Forberedelse af eksperimentet

Jeg vil gerne teste ovenstående teoretiske overvejelser i praksis – det var målet med den idé, der opstod i løbet af den forlængede weekend. For at gøre dette er det nødvendigt at evaluere hastigheden af ​​vores "betingede anvendelse" i alle de beskrevne scenarier for brug af databasen, samt væksten af ​​denne tid med væksten i størrelsen af ​​det sociale netværk (n). Den målparameter, der interesserer os, og som vi vil måle under eksperimentet, er den tid, som den "betingede applikation" bruger på at udføre én "forretningsoperation". Med "forretningstransaktion" mener vi en af ​​følgende:

• Tilføjelse af én ny ven
• Tjek om bruger A er ven med bruger B
• Fjerner én ven

Under hensyntagen til kravene angivet i den indledende erklæring er verifikationsscenariet således som følger:

• Dataoptagelse. Generer et tilfældigt initialt netværk af størrelse n. For at gøre det tættere på den "virkelige verden" er antallet af venner, som hver bruger har, også en tilfældig værdi. Mål den tid det tager for vores "betingede applikation" at skrive alle genererede data til HBase. Divider derefter den resulterende tid med det samlede antal tilføjede venner - dette vil give os den gennemsnitlige tid for én "forretningsoperation".
• Læser data. For hver bruger skal du oprette en liste over "personligheder", som du har brug for at få svar på, om brugeren abonnerer på dem eller ej. Listens længde = omtrent antallet af brugerens venner, og for halvdelen af ​​de markerede venner skal svaret være "Ja", og for den anden halvdel - "Nej". Kontrollen udføres på en sådan måde, at svarene "Ja" og "Nej" skiftevis vises (dvs. at vi i hvert andet tilfælde skal gennemgå alle kolonnerne i rækken for mulighed 1 og 2). Den samlede verifikationstid divideres derefter med antallet af venner, der verificeres, for at få den gennemsnitlige tid, det tager at verificere ét emne.
• Sletning af data. Slet alle venner fra en bruger. Desuden er rækkefølgen af ​​sletningen tilfældig (dvs. vi "blander" den oprindelige liste, der blev brugt til at registrere dataene). Den samlede verifikationstid divideres derefter med antallet af venner, der fjernes, for at få den gennemsnitlige tid pr. verifikation.

Scenarierne skal køres for hver af de 5 datamodelvarianter og for forskellige størrelser af det sociale netværk for at se, hvordan tiden ændrer sig, efterhånden som den vokser. Inden for én n forbindelser i netværket skal listen over brugere, der skal kontrolleres, naturligvis være den samme for alle 5 muligheder.
For bedre forståelse er nedenfor et eksempel på genererede data for n = 5. Den skrevne "generator" producerer tre ID-ordbøger ved outputtet:

• den første er til indsættelse
• den anden er til kontrol
• den tredje er til fjernelse

{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 ID'er større end 10 i ordbogen til verifikation præcis dem, der tydeligvis vil give et falsk svar. Indsættelse, kontrol og sletning af "venner" udføres i den nøjagtige rækkefølge, der er angivet i ordbogen.

Eksperimentet blev udført på en bærbar computer, der kørte Windows 10, hvor HBase kørte i én Docker-container, og Python med Jupyter Notebook kørte i en anden. Docker fik tildelt 2 CPU-kerner og 2 GB RAM. Al logik, inklusive simuleringen af ​​"dummy-applikationen" og frameworket til generering af testdata og måling af tid, blev skrevet i Python. Biblioteket gladbase, for at beregne hashværdier (MD5) for mulighed 5 - hashlib

Under hensyntagen til en bestemt bærbar computers computerkraft blev der eksperimentelt valgt en lancering for n = 10, 30, …. 170 – når den samlede løbetid for den fulde testcyklus (alle scenarier for alle muligheder for alle n) stadig var mere eller mindre rimelig og passede ind i én teselskabsrunde (i gennemsnit 15 minutter).

Her er det nødvendigt at bemærke, at vi i dette eksperiment primært ikke evaluerer absolutte præstationstal. Selv en relativ sammenligning af to forskellige muligheder er måske ikke helt korrekt. Nu er vi interesserede i arten af ​​ændringen i tid afhængigt af n, da det, under hensyntagen til den ovennævnte konfiguration af "teststanden", er meget vanskeligt at opnå tidsestimater, der er "ryddet" fra påvirkningen af ​​tilfældige og andre faktorer (og en sådan opgave blev ikke stillet).

Resultat af eksperimentet

Den første test er, hvordan den tid, det tager at udfylde vennelisten, ændrer sig. Resultatet er vist i grafen nedenfor.

Mulighed 3-5 forventes at vise en stort set konstant "driftstid", som ikke afhænger af væksten i netværksstørrelsen, og en identisk forskel i ydeevne.
Mulighed 2 viser også konstant, men lidt dårligere ydeevne, næsten præcis 2 gange sammenlignet med muligheder 3-5. Og dette kan ikke andet end glæde, da det korrelerer med teorien - i denne version er antallet af input-output-operationer til/fra HBase præcis 2 gange større. Dette kan tjene som indirekte bevis på, at vores testbænk i princippet giver god nøjagtighed.
Mulighed 1 forventes også at være den langsomste og viser en lineær stigning i den tid, det tager at tilføje én ven, afhængigt af netværkets størrelse.
Lad os nu se på resultaterne af den anden test.

Mulighed 3-5 opfører sig igen som forventet - konstant tid, uafhængigt af netværksstørrelsen. Mulighed 1 og 2 viser lineær tidsmæssig vækst med stigende netværksstørrelse og lignende ydeevne. Desuden viser mulighed 2 sig at være en smule langsommere – tilsyneladende på grund af behovet for at korrekturlæse og behandle den ekstra "tælling"-kolonne, som bliver mere mærkbar, efterhånden som n vokser. Jeg vil dog stadig afstå fra at drage nogen konklusioner, da nøjagtigheden af ​​denne sammenligning er relativt lav. Derudover ændrede disse forhold (hvilken mulighed, 1 eller 2, er hurtigere) sig fra lancering til lancering (samtidig med at afhængighedens karakter og "gåen hals ved hals" blev opretholdt).

Nå, den sidste graf er resultatet af fjernelsestesten.

Her igen, ingen overraskelser. Mulighed 3-5 udfører fjernelse i konstant tid.
Desuden er det interessant, at mulighed 4 og 5, i modsætning til de tidligere scenarier, viser mærkbart en smule dårligere ydeevne end mulighed 3. Tilsyneladende er rækkesletning dyrere end kolonnesletning, hvilket generelt er logisk.

Mulighed 1 og 2 viser som forventet en lineær stigning i tid. Samtidig er mulighed 2 konsekvent langsommere end mulighed 1 – på grund af den ekstra input/output-operation, der skal "servicere" tællerkolonnen.

Generelle konklusioner af eksperimentet:

• Mulighed 3-5 viser større effektivitet, da de udnytter HBase; Desuden adskiller deres ydeevne sig fra hinanden med en konstant og afhænger ikke af netværkets størrelse.
• Der blev ikke registreret nogen forskel mellem mulighed 4 og 5. Men det betyder ikke, at mulighed 5 ikke bør anvendes. Det er meget muligt, at det anvendte eksperimentelle scenarie, under hensyntagen til teststandens ydeevnekarakteristika, ikke tillod at identificere det.
• Karakteren af ​​den øgede tid, der kræves for at udføre "forretningsaktiviteter" med data, bekræftede generelt de tidligere opnåede teoretiske beregninger for alle muligheder.

Epilog

Disse grove eksperimenter bør ikke tages som absolut sandhed. Der er mange faktorer, der ikke blev taget i betragtning og som har forvrænget resultaterne (disse udsving er især synlige i graferne for små netværksstørrelser). For eksempel hastigheden af ​​thrift, som bruges af happybase, volumen og implementeringsmetoden for den logik, jeg skrev i Python (jeg kan ikke påstå, at koden blev skrevet optimalt eller effektivt udnyttede alle komponenter), muligvis HBase-cachingfunktioner og baggrundsaktivitet. Windows 10 På min bærbare computer osv. Samlet set kan det konkluderes, at alle teoretiske antagelser eksperimentelt er blevet bevist at være gyldige. Eller i det mindste var det ikke muligt at modbevise dem med et sådant direkte angreb.

Afslutningsvis er her nogle anbefalinger til alle, der lige er begyndt at designe datamodeller i HBase: Læg din tidligere erfaring med at arbejde med relationelle databaser til side, og husk "budene":

• Når vi designer, går vi ud fra opgave- og datamanipulationsmønstre og ikke fra emneområdemodellen
• Effektiv adgang (uden fuld tabelscanning) - kun med nøgle
• Denormalisering
• Forskellige rækker kan indeholde forskellige kolonner.
• Dynamisk sammensætning af kolonner

Kilde: www.habr.com