Høsten 2019 skjedde en etterlengtet hendelse i Mail.ru Cloud iOS-teamet. Hoveddatabasen for vedvarende lagring av applikasjonstilstand har blitt veldig eksotisk for mobilverdenen Lightning Memory-Mapped Database (LMDB). Under kuttet tilbyr vi deg en detaljert gjennomgang av den i fire deler. Først, la oss snakke om årsakene til et så ikke-trivielt og vanskelig valg. Deretter vil vi gå videre til å vurdere de tre pilarene i hjertet av LMDB-arkitekturen: minnetilordnede filer, B+-tre, kopi-på-skriv-tilnærming for implementering av transaksjonalitet og multiversjon. Til slutt, til dessert - den praktiske delen. I den vil vi se på hvordan du designer og implementerer et databaseskjema med flere tabeller, inkludert en indeks, på toppen av lavnivå nøkkelverdi API.

Innhold

1. Motivasjon for gjennomføring
2. LMDB posisjonering
3. Tre søyler i LMDB
   3.1. Hval #1. Minnetilordnede filer
   3.2. Hval #2. B+ tre
   3.3. Hval #3. Kopier-på-skriv
4. Utforme et dataskjema på toppen av nøkkelverdi-API
   4.1. Grunnleggende abstraksjoner
   4.2. Tabellmodellering
   4.3. Modellering av forhold mellom tabeller

1. Motivasjon for gjennomføring

Ett år i 2015 tok vi oss bryet med å måle hvor ofte grensesnittet til applikasjonen vår henger. Vi gjorde dette av en grunn. Vi har mottatt hyppigere klager på at applikasjonen noen ganger slutter å svare på brukerhandlinger: knapper kan ikke trykkes, lister ruller ikke osv. Om mekanikken til målinger fortalte på AvitoTech, så her gir jeg bare rekkefølgen på tallene.

Måleresultatene ble en kalddusj for oss. Det viste seg at det er mange flere problemer forårsaket av fryser enn noen annen. Hvis før du innså dette faktum, var den viktigste tekniske kvalitetsindikatoren krasjfri, så etter fokuset forskjøvet på frysefri.

Etter å ha bygget dashbord med fryser og etter å ha brukt kvantitativ и kvalitet analyse av årsakene deres, ble hovedfienden klar - tung forretningslogikk utført i hovedtråden til applikasjonen. Den naturlige reaksjonen på denne skammen var et brennende ønske om å skyve den inn i arbeidsstrømmene. For systematisk å løse dette problemet, brukte vi en flertrådsarkitektur basert på lette skuespillere. Jeg dedikerte den til tilpasningen for iOS-verdenen to tråder på kollektiv Twitter og artikkel om Habré. Som en del av den nåværende fortellingen ønsker jeg å understreke de aspektene ved avgjørelsen som påvirket valget av databasen.

Aktørmodellen for systemorganisasjon antar at multithreading blir dens andre essens. Modellobjekter i den liker å krysse bekkegrenser. Og de gjør dette ikke noen ganger og her og der, men nesten konstant og overalt...

Databasen er en av hjørnesteinskomponentene i det presenterte diagrammet. Hovedoppgaven er å implementere makromønsteret Delt database. Hvis det i bedriftsverdenen brukes til å organisere datasynkronisering mellom tjenester, så i tilfelle av aktørarkitektur - data mellom tråder. Derfor trengte vi en database som ikke ville forårsake selv minimale problemer når vi arbeider med den i et flertrådsmiljø. Spesielt betyr dette at gjenstander hentet fra den må være minst trådsikre, og ideelt sett fullstendig ikke-foranderlige. Som du vet, kan sistnevnte brukes samtidig fra flere tråder uten å ty til noen låsing, noe som har en gunstig effekt på ytelsen.

Den andre viktige faktoren som påvirket valget av database var vår cloud API. Den var inspirert av synkroniseringstilnærmingen tatt i bruk av git. I likhet med ham siktet vi mot offline-første API, som ser mer enn passende ut for skyklienter. Det ble antatt at de bare ville pumpe ut hele tilstanden til skyen én gang, og da ville synkronisering i det overveldende flertallet av tilfellene skje gjennom utrulling av endringer. Akk, denne muligheten er fortsatt bare i den teoretiske sonen, og klientene har ikke lært hvordan de skal jobbe med lapper i praksis. Det er en rekke objektive årsaker til dette, som vi, for ikke å forsinke innføringen, vil etterlate parentes. Nå, det som er av mye mer interesse, er de lærerike konklusjonene fra leksjonen om hva som skjer når en API sier "A" og forbrukeren ikke sier "B".

Så hvis du forestiller deg git, som, når du utfører en pull-kommando, i stedet for å bruke patcher på et lokalt øyeblikksbilde, sammenligner dens fulle tilstand med den fullstendige servertilstanden, vil du ha en ganske nøyaktig ide om hvordan synkronisering skjer i skyen klienter. Det er lett å gjette at for å implementere det, må du tildele to DOM-trær i minnet med metainformasjon om alle server- og lokale filer. Det viser seg at hvis en bruker lagrer 500 tusen filer i skyen, er det nødvendig å gjenskape og ødelegge to trær med 1 million noder for å synkronisere dem. Men hver node er et aggregat som inneholder en graf over underobjekter. I dette lyset var profileringsresultatene forventet. Det viste seg at selv uten å ta hensyn til sammenslåingsalgoritmen, koster selve prosedyren for å lage og deretter ødelegge et stort antall små objekter en pen penny. Situasjonen forverres av det faktum at den grunnleggende synkroniseringsoperasjonen er inkludert i et stort antall av brukerskript. Som et resultat fikser vi det andre viktige kriteriet ved valg av database - muligheten til å implementere CRUD-operasjoner uten dynamisk tildeling av objekter.

Andre krav er mer tradisjonelle og hele listen deres er som følger.

1. Trådsikkerhet.
2. Multiprosessering. Diktert av ønsket om å bruke samme databaseforekomst for å synkronisere tilstanden ikke bare mellom tråder, men også mellom hovedapplikasjonen og iOS-utvidelser.
3. Evnen til å representere lagrede enheter som objekter som ikke kan endres
4. Ingen dynamiske tildelinger innenfor CRUD-operasjoner.
5. Transaksjonsstøtte for grunnleggende egenskaper ACID: atomitet, konsistens, isolasjon og pålitelighet.
6. Hastighet på de mest populære sakene.

Med dette settet med krav var og forblir SQLite et godt valg. Men som en del av studiet av alternativer kom jeg over en bok "Komme i gang med LevelDB". Under hennes ledelse ble det skrevet en benchmark som sammenlignet hastigheten på arbeidet med forskjellige databaser i ekte skyscenarier. Resultatet overgikk våre villeste forventninger. I de mest populære tilfellene - å få en markør på en sortert liste over alle filer og en sortert liste over alle filer for en gitt katalog - viste LMDB seg å være 10 ganger raskere enn SQLite. Valget ble åpenbart.

2. LMDB Posisjonering

LMDB er et veldig lite bibliotek (bare 10K rader) som implementerer det laveste grunnleggende laget av databaser - lagring.

Diagrammet ovenfor viser at å sammenligne LMDB med SQLite, som også implementerer høyere nivåer, generelt sett ikke er mer korrekt enn SQLite med Core Data. Det ville være mer rettferdig å sitere de samme lagringsmotorene som like konkurrenter – BerkeleyDB, LevelDB, Sophia, RocksDB, etc. Det er til og med utviklinger der LMDB fungerer som en lagringsmotorkomponent for SQLite. Det første slike eksperiment var i 2012 brukt av LMDB Howard Chu. Funn viste seg å være så spennende at initiativet hans ble plukket opp av OSS-entusiaster, og fant fortsettelsen i personen LumoSQL. I januar 2020 var forfatteren av dette prosjektet Den Shearer presentert det på LinuxConfAu.

LMDB brukes hovedsakelig som en motor for applikasjonsdatabaser. Biblioteket skylder utviklerne sitt utseende OpenLDAP, som var svært misfornøyd med BerkeleyDB som grunnlag for prosjektet deres. Starter fra et beskjedent bibliotek btree, var Howard Chu i stand til å lage et av de mest populære alternativene i vår tid. Han dedikerte sin veldig kule rapport til denne historien, så vel som til den interne strukturen til LMDB. "The Lightning Memory-mapped Database". Et godt eksempel på å erobre et lagringsanlegg ble delt av Leonid Yuryev (aka yleo) fra Positive Technologies i rapporten hans på Highload 2015 "LMDB-motoren er en spesiell mester". I den snakker han om LMDB i sammenheng med en lignende oppgave med å implementere ReOpenLDAP, og LevelDB har allerede vært utsatt for komparativ kritikk. Som et resultat av implementeringen hadde Positive Technologies til og med en gaffel i aktivt utvikling MDBX med svært velsmakende funksjoner, optimaliseringer og feilrettinger.

LMDB brukes ofte som en slik lagring. For eksempel nettleseren Mozilla Firefox valgte det for en rekke behov, og fra og med versjon 9, Xcode foretrukket sin SQLite for lagring av indekser.

Motoren har også markert seg i verden av mobilutvikling. Spor av bruken kan være finne i iOS-klienten for Telegram. LinkedIn gikk enda lenger og valgte LMDB som standardlagring for sitt hjemmelagde databufringsrammeverk Rocket Data, om hvilke fortalte i sin artikkel i 2016.

LMDB kjemper med suksess om en plass i solen i nisjen etterlatt av BerkeleyDB etter at den kom under kontroll av Oracle. Biblioteket er elsket for sin hastighet og pålitelighet, selv sammenlignet med jevnaldrende. Som du vet, er det ingen gratis lunsjer, og jeg vil gjerne understreke avveiningen du må møte når du skal velge mellom LMDB og SQLite. Diagrammet ovenfor viser tydelig hvordan økt hastighet oppnås. For det første betaler vi ikke for ekstra lag med abstraksjon på toppen av disklagring. Det er klart at en god arkitektur fortsatt ikke kan klare seg uten dem, og de vil uunngåelig vises i applikasjonskoden, men de vil være mye mer subtile. De vil ikke inneholde funksjoner som ikke kreves av en spesifikk applikasjon, for eksempel støtte for spørringer i SQL-språket. For det andre blir det mulig å optimalt implementere kartlegging av applikasjonsoperasjoner på forespørsler til disklagring. Hvis SQLite i jobben min er basert på gjennomsnittlig statistisk behov for en gjennomsnittlig applikasjon, så er du som applikasjonsutvikler godt klar over de viktigste arbeidsbelastningsscenariene. For en mer produktiv løsning, må du betale en økt prislapp både for utviklingen av den første løsningen og for den påfølgende støtten.

3. Tre pilarer i LMDB

Etter å ha sett på LMDB fra et fugleperspektiv, var det på tide å gå dypere. De neste tre avsnittene vil bli viet til en analyse av hovedpilarene som lagringsarkitekturen hviler på:

1. Minnetilordnede filer som en mekanisme for arbeid med disk og synkronisering av interne datastrukturer.
2. B+-tre som en organisering av strukturen til lagrede data.
3. Kopier-på-skriv som en tilnærming for å gi ACID-transaksjonsegenskaper og multiversjon.

3.1. Hval #1. Minnetilordnede filer

Minnetilordnede filer er et så viktig arkitektonisk element at de til og med vises i navnet på depotet. Spørsmål om caching og synkronisering av tilgang til lagret informasjon er helt overlatt til operativsystemet. LMDB inneholder ingen cacher i seg selv. Dette er en bevisst beslutning av forfatteren, siden lesing av data direkte fra kartlagte filer lar deg kutte mange hjørner i motorimplementeringen. Nedenfor er en langt fra fullstendig liste over noen av dem.

1. Å opprettholde konsistensen av data i lagringen når du arbeider med dem fra flere prosesser blir operativsystemets ansvar. I neste avsnitt diskuteres denne mekanikken i detalj og med bilder.
2. Fraværet av cacher eliminerer LMDB fullstendig fra overhead knyttet til dynamiske tildelinger. Å lese data betyr i praksis å sette en peker til riktig adresse i virtuelt minne og ingenting mer. Det høres ut som science fiction, men i lagringskildekoden er alle anrop til calloc konsentrert i lagringskonfigurasjonsfunksjonen.
3. Fravær av cacher betyr også fravær av låser knyttet til synkronisering av tilgangen deres. Lesere, som det kan eksistere et vilkårlig antall av samtidig, møter ikke en eneste mutex på vei til data. På grunn av dette har lesehastigheten ideell lineær skalerbarhet basert på antall CPUer. I LMDB er det bare endringsoperasjoner som synkroniseres. Det kan bare være én forfatter om gangen.
4. Et minimum av caching og synkroniseringslogikk eliminerer den ekstremt komplekse typen feil knyttet til arbeid i et flertrådsmiljø. Det var to interessante databasestudier på Usenix OSDI 2014-konferansen: "Alle filsystemer er ikke skapt like: Om kompleksiteten ved å lage krasj-konsistente applikasjoner" и "Torturere databaser for moro skyld og profitt". Fra dem kan du hente informasjon om både den enestående påliteligheten til LMDB og den nesten feilfrie implementeringen av ACID-transaksjonsegenskaper, som er overlegen SQLite.
5. Minimalismen til LMDB lar maskinrepresentasjonen av koden sin være fullstendig plassert i L1-cachen til prosessoren med de påfølgende hastighetsegenskapene.

Dessverre, i iOS, med minnetilordnede filer, er ikke alt så skyfritt som vi ønsker. For å snakke mer bevisst om manglene knyttet til dem, er det nødvendig å huske de generelle prinsippene for implementering av denne mekanismen i operativsystemer.

Generell informasjon om minnetilordnede filer

Med hver applikasjon som kjører, knytter operativsystemet til en enhet som kalles en prosess. Hver prosess er tildelt et sammenhengende område med adresser der den plasserer alt den trenger for å fungere. På de laveste adressene er det seksjoner med kode og hardkodede data og ressurser. Deretter kommer en voksende blokk med dynamisk adresserom, godt kjent for oss under navnet heap. Den inneholder adressene til enheter som vises under driften av programmet. Øverst er minneområdet som brukes av applikasjonsstakken. Den enten vokser eller trekker seg sammen, med andre ord har størrelsen også en dynamisk natur. For å forhindre at stabelen og haugen skyver og forstyrrer hverandre, er de plassert i forskjellige ender av adressefeltet. Det er et hull mellom de to dynamiske seksjonene øverst og nederst. Operativsystemet bruker adresser i denne midtseksjonen for å knytte en rekke enheter til prosessen. Spesielt kan den knytte et visst kontinuerlig sett med adresser til en fil på disken. En slik fil kalles minnetilordnet

Adresseplassen som er tildelt prosessen er enorm. Teoretisk er antallet adresser bare begrenset av størrelsen på pekeren, som bestemmes av systemets bitkapasitet. Hvis fysisk minne ble kartlagt til det 1-til-1, ville den aller første prosessen sluke opp hele RAM-en, og det ville ikke være snakk om multitasking.

Fra vår erfaring vet vi imidlertid at moderne operativsystemer kan kjøre så mange prosesser som ønskelig samtidig. Dette er mulig på grunn av det faktum at de bare allokerer mye minne til prosesser på papir, men i virkeligheten laster de inn i det fysiske hovedminnet bare den delen som er etterspurt her og nå. Derfor kalles minnet knyttet til en prosess virtuelt.

Operativsystemet organiserer virtuelt og fysisk minne i sider av en viss størrelse. Så snart en bestemt side med virtuelt minne er etterspurt, laster operativsystemet den inn i det fysiske minnet og matcher dem i en spesiell tabell. Hvis det ikke er ledige spor, blir en av de tidligere lastede sidene kopiert til disken, og den etterspurte tar sin plass. Denne prosedyren, som vi kommer tilbake til om kort tid, kalles bytte. Figuren nedenfor illustrerer prosessen beskrevet. På den ble side A med adresse 0 lastet og plassert på hovedminnesiden med adresse 4. Dette faktum ble reflektert i korrespondansetabellen i celle nummer 0.​

Historien er nøyaktig den samme med filer kartlagt til minnet. Logisk sett er de visstnok kontinuerlig og fullstendig plassert i det virtuelle adresserommet. Imidlertid legger de inn fysisk minne side for side og kun på forespørsel. Endring av slike sider synkroniseres med filen på disken. På denne måten kan du utføre fil-I/O ved ganske enkelt å jobbe med byte i minnet - alle endringer vil automatisk overføres av operativsystemkjernen til kildefilen.​
â € <
Bildet nedenfor viser hvordan LMDB synkroniserer sin tilstand når du arbeider med databasen fra forskjellige prosesser. Ved å kartlegge det virtuelle minnet til forskjellige prosesser til den samme filen, forplikter vi de facto operativsystemet til transitivt å synkronisere visse blokker av adresserommene deres med hverandre, der LMDB ser.​
â € <

En viktig nyanse er at LMDB, som standard, modifiserer datafilen gjennom skrivesystemanropsmekanismen, og viser selve filen i skrivebeskyttet modus. Denne tilnærmingen har to viktige konsekvenser.

Den første konsekvensen er felles for alle operativsystemer. Essensen er å legge til beskyttelse mot utilsiktet skade på databasen med feil kode. Som du vet, er de kjørbare instruksjonene til en prosess gratis for å få tilgang til data fra hvor som helst i adresseområdet. Samtidig, som vi nettopp husket, betyr visning av en fil i lese-skrivemodus at enhver instruksjon også kan endre den. Hvis hun gjør dette ved en feiltakelse, og prøver for eksempel å faktisk overskrive et array-element ved en ikke-eksisterende indeks, kan hun ved et uhell endre filen som er tilordnet denne adressen, noe som vil føre til korrupsjon av databasen. Hvis filen vises i skrivebeskyttet modus, vil et forsøk på å endre det tilsvarende adresserommet føre til en nødavslutning av programmet med et signal SIGSEGV, og filen forblir intakt.

Den andre konsekvensen er allerede spesifikk for iOS. Verken forfatteren eller andre kilder nevner det eksplisitt, men uten det ville ikke LMDB vært egnet for å kjøre på dette mobile operativsystemet. Den neste delen er viet dens behandling.

Spesifikasjoner for minnetilordnede filer i iOS

Det var en fantastisk rapport på WWDC i 2018 "iOS Memory Deep Dive". Den forteller oss at i iOS er alle sider som ligger i det fysiske minnet en av tre typer: skitne, komprimerte og rene.

Rent minne er en samling sider som smertefritt kan lastes ut fra det fysiske minnet. Dataene de inneholder kan lastes inn på nytt etter behov fra originalkildene. Skrivebeskyttede minnetilordnede filer faller inn i denne kategorien. iOS er ikke redd for å laste ut sidene som er tilordnet en fil fra minnet når som helst, siden de garantert vil bli synkronisert med filen på disken.
â € <
Alle endrede sider havner i skittent minne, uansett hvor de opprinnelig var plassert. Spesielt vil minnetilordnede filer som er endret ved å skrive til det virtuelle minnet knyttet til dem, bli klassifisert på denne måten. Åpning LMDB med flagg MDB_WRITEMAP, etter å ha gjort endringer i den, kan du bekrefte dette personlig.​

Så snart en applikasjon begynner å ta opp for mye fysisk minne, utsetter iOS den for skitten sidekomprimering. Det totale minnet som opptas av skitne og komprimerte sider utgjør programmets såkalte minneavtrykk. Når den når en viss terskelverdi, kommer OOM-killer-systemdaemonen etter prosessen og tvangsavslutter den. Dette er det særegne ved iOS sammenlignet med stasjonære operativsystemer. I motsetning er det ikke gitt i iOS å redusere minneavtrykket ved å bytte sider fra fysisk minne til disk. Årsakene kan bare gjettes på. Kanskje prosedyren med å intensivt flytte sider til disk og tilbake er for energikrevende for mobile enheter, eller iOS sparer ressursen med å omskrive celler på SSD-stasjoner, eller kanskje designerne ikke var fornøyd med den generelle ytelsen til systemet, der alt er stadig byttet. Uansett så forblir faktum et faktum.

Den gode nyheten, allerede nevnt tidligere, er at LMDB som standard ikke bruker mmap-mekanismen til å oppdatere filer. Dette betyr at de viste dataene er klassifisert av iOS som rent minne og bidrar ikke til minneavtrykket. Du kan bekrefte dette ved å bruke et Xcode-verktøy kalt VM Tracker. Skjermbildet nedenfor viser tilstanden til det virtuelle iOS-minnet til Cloud-applikasjonen under drift. Ved starten ble 2 LMDB-forekomster initialisert i den. Den første fikk vise filen sin på 1GiB virtuelt minne, den andre - 512MiB. Til tross for at begge lagringene opptar en viss mengde internminne, bidrar ingen av dem med skitten størrelse.

Og nå er det på tide med dårlige nyheter. Takket være swap-mekanismen i 64-bits stasjonære operativsystemer, kan hver prosess oppta så mye virtuell adresseplass som ledig harddiskplass for potensiell swap tillater. Å erstatte swap med komprimering i iOS reduserer det teoretiske maksimumet radikalt. Nå må alle levende prosesser passe inn i hovedminnet (les RAM), og alle de som ikke passer må tvinges til å avslutte. Dette er oppgitt som i ovennevnte rapportere, og i offisiell dokumentasjon. Som en konsekvens begrenser iOS kraftig mengden minne som er tilgjengelig for tildeling via mmap. Her her Du kan se på de empiriske grensene for mengden minne som kan tildeles forskjellige enheter ved å bruke dette systemanropet. På de mest moderne smarttelefonmodellene har iOS blitt generøse med 2 gigabyte, og på toppversjoner av iPad - med 4. I praksis må du selvfølgelig fokusere på de lavest støttede enhetsmodellene, der alt er veldig trist. Enda verre, ved å se på applikasjonens minnetilstand i VM Tracker, vil du finne at LMDB langt fra er den eneste som hevder å være minnekart. Gode ​​biter blir spist bort av systemallokatorer, ressursfiler, bilderammeverk og andre mindre rovdyr.

Basert på resultatene av eksperimenter i skyen, kom vi til følgende kompromissverdier for minnet tildelt av LMDB: 384 megabyte for 32-bits enheter og 768 for 64-bits enheter. Etter at dette volumet er brukt opp, begynner alle endringsoperasjoner å slutte med koden MDB_MAP_FULL. Vi observerer slike feil i vår overvåking, men de er små nok til at de på dette stadiet kan neglisjeres.

En ikke åpenbar årsak til overdreven minneforbruk av lagringen kan være langvarige transaksjoner. For å forstå hvordan disse to fenomenene henger sammen, vil vi bli hjulpet ved å vurdere de resterende to pilarene i LMDB.

3.2. Hval #2. B+ tre

For å emulere tabeller på toppen av en nøkkelverdilagring, må følgende operasjoner være til stede i API-en:

1. Setter inn et nytt element.
2. Søk etter et element med en gitt nøkkel.
3. Fjerne et element.
4. Iterer over intervaller av nøkler i den rekkefølgen de er sortert.

Den enkleste datastrukturen som enkelt kan implementere alle fire operasjonene er et binært søketre. Hver av nodene representerer en nøkkel som deler hele undersettet av undernøkler i to undertrær. Den venstre inneholder de som er mindre enn forelderen, og den høyre inneholder de som er større. Å skaffe et bestilt sett med nøkler oppnås gjennom en av de klassiske treovergangene

Binære trær har to grunnleggende feil som hindrer dem i å være effektive som en diskbasert datastruktur. For det første er graden av deres balanse uforutsigbar. Det er en betydelig risiko for å skaffe trær hvor høyden på ulike grener kan variere sterkt, noe som forverrer søkets algoritmiske kompleksitet betydelig sammenlignet med det som forventes. For det andre fratar overfloden av krysskoblinger mellom noder binære trær lokalitet i minnet.Tette noder (når det gjelder forbindelser mellom dem) kan lokaliseres på helt forskjellige sider i virtuelt minne. Som en konsekvens kan selv en enkel kryssing av flere nabonoder i et tre kreve å besøke et sammenlignbart antall sider. Dette er et problem selv når vi snakker om effektiviteten til binære trær som en datastruktur i minnet, siden konstant roterende sider i prosessorens cache ikke er en billig fornøyelse. Når det gjelder å ofte hente sider knyttet til noder fra disk, blir situasjonen fullstendig beklagelig.

B-trær, som er en utvikling av binære trær, løser problemene identifisert i forrige avsnitt. For det første er de selvbalanserende. For det andre deler hver av deres noder settet med barnenøkler ikke i 2, men i M-ordnede delsett, og tallet M kan være ganske stort, i størrelsesorden flere hundre, eller til og med tusenvis.

Derved:

1. Hver node inneholder et stort antall allerede bestilte nøkler og trærne er veldig korte.
2. Treet får egenskapen lokalisering av plassering i minnet, siden nøkler som er nære i verdi, naturlig ligger ved siden av hverandre på samme eller nærliggende noder.
3. Antall transittnoder når du går ned i et tre under en søkeoperasjon, reduseres.
4. Antall målnoder som leses under rekkeviddespørringer reduseres, siden hver av dem allerede inneholder et stort antall ordnede nøkler.

LMDB bruker en variant av B-treet kalt et B+-tre for å lagre data. Diagrammet ovenfor viser de tre typene noder som finnes i den:

1. På toppen er roten. Det materialiserer ingenting mer enn konseptet med en database inne i et lager. Innenfor én LMDB-forekomst kan du opprette flere databaser som deler et tilordnet virtuelt adresserom. Hver av dem begynner fra sin egen rot.
2. På det laveste nivået er bladene. De og bare de inneholder nøkkel-verdi-parene som er lagret i databasen. Dette er forresten det særegne ved B+-trær. Hvis et vanlig B-tre lagrer verdideler i noder på alle nivåer, er B+-variasjonen bare på den laveste. Etter å ha fikset dette faktum, vil vi videre kalle undertypen til treet som brukes i LMDB ganske enkelt et B-tre.
3. Mellom roten og bladene er det 0 eller flere tekniske nivåer med navigasjons (gren) noder. Deres oppgave er å dele det sorterte settet med nøkler mellom bladene.

Fysisk er noder minneblokker med en forhåndsbestemt lengde. Størrelsen deres er et multiplum av størrelsen på minnesider i operativsystemet, som vi diskuterte ovenfor. Nodestrukturen er vist nedenfor. Overskriften inneholder metainformasjon, den mest åpenbare er for eksempel kontrollsummen. Deretter kommer informasjon om forskyvningene som cellene med data befinner seg i. Dataene kan enten være nøkler, hvis vi snakker om navigasjonsnoder, eller hele nøkkelverdi-par når det gjelder blader.​ Du kan lese mer om strukturen til sider i arbeidet "Evaluering av nøkkelverdibutikker med høy ytelse".

Etter å ha behandlet det interne innholdet i sidenoder, vil vi ytterligere representere LMDB B-treet på en forenklet måte i følgende skjema.

Sider med noder er plassert sekvensielt på disken. Høyere nummererte sider er plassert mot slutten av filen. Den såkalte metasiden inneholder informasjon om forskyvningene som kan brukes til å finne røttene til alle trær. Når du åpner en fil, skanner LMDB filen side for side fra ende til begynnelse for å søke etter en gyldig metaside og gjennom den finner eksisterende databaser.

Nå, med en ide om den logiske og fysiske strukturen til dataorganisasjon, kan vi gå videre til å vurdere den tredje søylen i LMDB. Det er med dens hjelp at alle lagringsmodifikasjoner skjer transaksjonelt og isolert fra hverandre, noe som gir databasen som helhet egenskapen til multiversjon.

3.3. Hval #3. Kopier-på-skriv

Noen B-tre operasjoner innebærer å gjøre en rekke endringer i nodene. Et eksempel er å legge til en ny nøkkel til en node som allerede har nådd sin maksimale kapasitet. I dette tilfellet er det for det første nødvendig å dele noden i to, og for det andre å legge til en kobling til den nye spirende barnenoden i dens overordnede. Denne prosedyren er potensielt svært farlig. Hvis av en eller annen grunn (krasj, strømbrudd osv.) bare en del av endringene fra serien skjer, vil treet forbli i en inkonsekvent tilstand.

En tradisjonell løsning for å gjøre en database feiltolerant er å legge til en ekstra datastruktur på disken ved siden av B-treet - en transaksjonslogg, også kjent som en WAL (Write-ahead Log). Det er en fil på slutten som den tiltenkte operasjonen er skrevet strengt før du endrer selve B-treet. Derfor, hvis datakorrupsjon oppdages under selvdiagnose, konsulterer databasen loggen for å sette seg selv i orden.

LMDB har valgt en annen metode som en feiltoleransemekanisme, kalt copy-on-write. Essensen er at i stedet for å oppdatere data på en eksisterende side, kopierer den først den fullstendig og gjør alle endringer i kopien.

Deretter, for at de oppdaterte dataene skal være tilgjengelige, er det nødvendig å endre koblingen til noden som har blitt gjeldende i sin overordnede node. Siden den også må modifiseres for dette, blir den også kopiert på forhånd. Prosessen fortsetter rekursivt helt til roten. Den siste tingen å endre er dataene på metasiden.​

Hvis prosessen plutselig krasjer under oppdateringsprosedyren, vil enten en ny metaside ikke bli opprettet, eller den vil ikke bli skrevet til disken fullstendig, og kontrollsummen vil være feil. I begge disse to tilfellene vil nye sider være utilgjengelige, men gamle vil ikke bli berørt. Dette eliminerer behovet for LMDB å skrive frem logg for å opprettholde datakonsistens. De facto tar strukturen til datalagring på disken beskrevet ovenfor samtidig sin funksjon. Fraværet av en eksplisitt transaksjonslogg er en av funksjonene til LMDB som gir høy datalesehastighet

Det resulterende designet, kalt append-only B-tree, gir naturligvis transaksjonsisolasjon og multiversjon. I LMDB er hver åpne transaksjon knyttet til den aktuelle treroten. Inntil transaksjonen er fullført, vil sidene i treet som er knyttet til det aldri bli endret eller gjenbrukt til nye versjoner av dataene. Dermed kan du jobbe så lenge du vil med akkurat det settet med data som var relevant på det tidspunktet transaksjonen ble åpnet, selv om lagringen fortsetter å være aktivt oppdatert på dette tidspunktet. Dette er essensen av multiversjon, noe som gjør LMDB til en ideell datakilde for vår elskede UICollectionView. Etter å ha åpnet en transaksjon, er det ikke nødvendig å øke minnefotavtrykket til applikasjonen ved å raskt pumpe ut gjeldende data inn i en eller annen struktur i minnet, i frykt for å sitte igjen med ingenting. Denne funksjonen skiller LMDB fra den samme SQLite, som ikke kan skryte av slik total isolasjon. Etter å ha åpnet to transaksjoner i sistnevnte og slettet en viss post i en av dem, vil det ikke lenger være mulig å få samme post i den andre gjenværende.

Baksiden av medaljen er det potensielt betydelig høyere forbruket av virtuelt minne. Lysbildet viser hvordan databasestrukturen vil se ut hvis den modifiseres samtidig med 3 åpne lesetransaksjoner som ser på ulike versjoner av databasen. Siden LMDB ikke kan gjenbruke noder tilgjengelig fra røtter knyttet til gjeldende transaksjoner, har butikken ikke noe annet valg enn å allokere en annen fjerde rot i minnet og igjen klone de modifiserte sidene under den.

Her vil det være nyttig å huske avsnittet om minnetilordnede filer. Det ser ut til at det ekstra forbruket av virtuelt minne ikke bør bekymre oss mye, siden det ikke bidrar til minneavtrykket til applikasjonen. Men samtidig ble det bemerket at iOS er veldig gjerrig med å tildele det, og vi kan ikke, som på en server eller skrivebord, gi en LMDB-region på 1 terabyte og ikke tenke på denne funksjonen i det hele tatt. Hvis mulig, bør du prøve å gjøre transaksjoners levetid så kort som mulig.

4. Utforme et dataskjema på toppen av nøkkelverdi-API

La oss starte API-analysen vår ved å se på de grunnleggende abstraksjonene fra LMDB: miljø og databaser, nøkler og verdier, transaksjoner og markører.

En merknad om kodeoppføringer

Alle funksjoner i det offentlige LMDB API returnerer resultatet av arbeidet sitt i form av en feilkode, men i alle påfølgende oppføringer er verifiseringen utelatt for korthets skyld.​ I praksis brukte vi til og med vårt eget til å samhandle med depotet. gaffel C++-omslag lmdbxx, der feil blir materialisert som C++-unntak.

Som den raskeste måten å koble LMDB til et prosjekt for iOS eller macOS, foreslår jeg min CocoaPod POSLMDB.

4.1. Grunnleggende abstraksjoner

Miljø

Struktur MDB_env er depotet for den interne tilstanden til LMDB. Prefiks funksjonsfamilie mdb_env lar deg konfigurere noen av egenskapene. I det enkleste tilfellet ser motorinitialisering slik ut.

mdb_env_create(env);​
mdb_env_set_map_size(*env, 1024 * 1024 * 512)​
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);

I Mail.ru Cloud-applikasjonen endret vi standardverdiene for bare to parametere.

Den første er størrelsen på den virtuelle adresseplassen som lagringsfilen er tilordnet til. Dessverre, selv på samme enhet, kan den spesifikke verdien variere betydelig fra kjøring til kjøring. For å ta hensyn til denne funksjonen til iOS, velges det maksimale lagringsvolumet dynamisk. Med utgangspunkt i en viss verdi, halveres den sekvensielt frem til funksjonen mdb_env_open vil ikke returnere et annet resultat enn ENOMEM. I teorien er det også motsatt vei - først alloker et minimum av minne til motoren, og deretter, når feil mottas, MDB_MAP_FULL, øke den. Imidlertid er det mye mer tornete. Årsaken er at prosedyren for å omallokere minne (remap) ved hjelp av funksjonen mdb_env_set_map_size ugyldiggjør alle enheter (markører, transaksjoner, nøkler og verdier) tidligere mottatt fra motoren. Å ta hensyn til denne hendelsen i koden vil føre til betydelig komplikasjon. Men hvis virtuelt minne er veldig viktig for deg, kan dette være en grunn til å se nærmere på gaffelen som har gått langt foran MDBX, hvor blant de annonserte funksjonene er det "automatisk on-the-fly databasestørrelsesjustering".

Den andre parameteren, hvis standardverdi ikke passet oss, regulerer mekanikken for å sikre gjengesikkerhet. Dessverre har minst iOS 10 problemer med støtte for lokal trådlagring. Av denne grunn, i eksemplet ovenfor, åpnes depotet med flagget MDB_NOTLS. I tillegg til dette var det også nødvendig gaffel C++-omslag lmdbxxå kutte ut variabler med denne attributten og i den.

databaser

Databasen er en egen B-tre-forekomst, som vi diskuterte ovenfor. Åpningen skjer i en transaksjon, noe som kan virke litt rart i begynnelsen.

MDB_txn *txn;​
MDB_dbi dbi;​
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);​
mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);​
mdb_txn_abort(txn);

Faktisk er en transaksjon i LMDB en lagringsenhet, ikke en spesifikk databaseenhet. Dette konseptet lar deg utføre atomoperasjoner på enheter som ligger i forskjellige databaser. I teorien åpner dette for muligheten for å modellere tabeller i form av forskjellige databaser, men på et tidspunkt tok jeg en annen vei, beskrevet i detalj nedenfor.

Nøkler og verdier

Struktur MDB_val modellerer konseptet både nøkkel og verdi. Depotet har ingen anelse om semantikken deres. For henne er noe annet bare en rekke byte av en gitt størrelse. Maksimal nøkkelstørrelse er 512 byte.

typedef struct MDB_val {​
    size_t mv_size;​
    void *mv_data;​
} MDB_val;​​

Ved hjelp av en komparator, sorterer butikken nøklene i stigende rekkefølge. Hvis du ikke erstatter den med din egen, vil standarden bli brukt, som sorterer dem byte-for-byte i leksikografisk rekkefølge.

Transaksjonen

Transaksjonsstrukturen er beskrevet i detalj i forrige kapittel, så her vil jeg kort gjenta hovedegenskapene deres:

1. Støtter alle grunnleggende egenskaper ACID: atomitet, konsistens, isolasjon og pålitelighet. Jeg kan ikke la være å merke meg at det er en feil når det gjelder holdbarhet på macOS og iOS som ble fikset i MDBX. Du kan lese mer i deres README.
2. Tilnærmingen til multithreading er beskrevet av ordningen "enkelt forfatter / flere lesere". Forfattere blokkerer hverandre, men blokkerer ikke lesere. Lesere blokkerer ikke forfattere eller hverandre.
3. Støtte for nestede transaksjoner.
4. Multiversjonsstøtte.

Multiversjon i LMDB er så bra at jeg vil demonstrere det i aksjon. Fra koden nedenfor kan du se at hver transaksjon fungerer med nøyaktig versjonen av databasen som var gjeldende på tidspunktet den ble åpnet, og er fullstendig isolert fra alle påfølgende endringer. Å initialisere lagringen og legge til en testpost til den representerer ikke noe interessant, så disse ritualene blir liggende under spoileren.

Legger til en testoppføring

MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;

mdb_env_create(&env);
mdb_env_open(env, "./testdb", MDB_NOTLS, 0664);

mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);

char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;

int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;

mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);

MDB_txn *txn1, *txn2, *txn3;
MDB_val val;

// Открываем 2 транзакции, каждая из которых смотрит
// на версию базы данных с одной записью.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only

// В рамках первой транзакции удаляем из базы данных существующую в ней запись.
mdb_del(txn1, dbi, &key, NULL);
// Фиксируем удаление.
mdb_txn_commit(txn1);

// Открываем третью транзакцию, которая смотрит на
// актуальную версию базы данных, где записи уже нет.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Убеждаемся, что запись по искомому ключу уже не существует.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Завершаем транзакцию.
mdb_txn_abort(txn3);

// Убеждаемся, что в рамках второй транзакции, открытой на момент
// существования записи в базе данных, её всё ещё можно найти по ключу.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
assert(*(int *)val.mv_data == 997);
// Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
mdb_txn_abort(txn2);

Jeg anbefaler at du prøver det samme trikset med SQLite og ser hva som skjer.

Multiversion gir veldig fine fordeler til livet til en iOS-utvikler. Ved å bruke denne egenskapen kan du enkelt og naturlig justere oppdateringshastigheten til datakilden for skjermskjemaer, basert på brukeropplevelsesbetraktninger. La oss for eksempel ta en funksjon i Mail.ru Cloud-applikasjonen, for eksempel automatisk lasting av innhold fra systemets mediegalleri. Med en god tilkobling kan klienten legge til flere bilder per sekund på serveren. Hvis du oppdaterer etter hver nedlasting UICollectionView med medieinnhold i brukerens sky, kan du glemme 60 fps og jevn rulling under denne prosessen. For å forhindre hyppige skjermoppdateringer, må du på en eller annen måte begrense hastigheten med hvilken data endres i det underliggende UICollectionViewDataSource.

Hvis databasen ikke støtter multiversjon og lar deg jobbe bare med gjeldende tilstand, må du kopiere dem enten til en datastruktur i minnet eller til en midlertidig tabell for å lage et tidsstabilt øyeblikksbilde av dataene. Enhver av disse tilnærmingene er svært kostbare. Ved lagring i minnet får vi kostnader både i minnet, forårsaket av lagring av konstruerte objekter, og i tid, forbundet med redundante ORM-transformasjoner. Når det gjelder det midlertidige bordet, er dette en enda dyrere glede, som bare gir mening i ikke-trivielle tilfeller.

LMDBs multiversjonsløsning løser problemet med å opprettholde en stabil datakilde på en meget elegant måte. Det er nok bare å åpne en transaksjon og voila - til vi fullfører den, er datasettet garantert fikset. Logikken for oppdateringshastigheten er nå helt i hendene på presentasjonslaget, uten overhead av betydelige ressurser.

Pekere

Markører gir en mekanisme for ordnet iterasjon over nøkkelverdi-par gjennom B-tre-traversering. Uten dem ville det være umulig å effektivt modellere tabellene i databasen, som vi nå vender oss til.

4.2. Tabellmodellering

Egenskapen til nøkkelbestilling lar deg konstruere en abstraksjon på høyt nivå, for eksempel en tabell på toppen av grunnleggende abstraksjoner. La oss vurdere denne prosessen ved å bruke eksemplet på hovedtabellen til en skyklient, som cacher informasjon om alle brukerens filer og mapper.

Tabellskjema

Et av de vanlige scenariene som en tabellstruktur med et mappetre bør skreddersys for, er valg av alle elementer som ligger innenfor en gitt katalog En god dataorganisasjonsmodell for effektive spørringer av denne typen er Tilknytningsliste. For å implementere det på toppen av nøkkelverdilagringen, er det nødvendig å sortere nøklene til filer og mapper på en slik måte at de er gruppert basert på deres medlemskap i den overordnede katalogen. I tillegg, for å vise innholdet i katalogen i formen som er kjent for en Windows-bruker (først mapper, deretter filer, begge sortert alfabetisk), er det nødvendig å inkludere de tilsvarende tilleggsfeltene i nøkkelen.

​Bildet nedenfor viser hvordan, basert på oppgaven, en representasjon av nøkler i form av en byte-array kan se ut. Bytene med identifikatoren til den overordnede katalogen (rød) plasseres først, deretter med typen (grønn) og i halen med navnet (blå). Når de er sortert etter standard LMDB-komparator i leksikografisk rekkefølge, er de sortert i nødvendig måte. Sekvensielt kryssing av nøkler med samme røde prefiks gir oss deres tilknyttede verdier i den rekkefølgen de skal vises i brukergrensesnittet (til høyre), uten å kreve ytterligere etterbehandling.

Serialisering av nøkler og verdier

Mange metoder for å serialisere objekter har blitt oppfunnet i verden. Siden vi ikke hadde andre krav enn hastighet, valgte vi det raskest mulig for oss selv - en dump av minnet som er okkupert av en forekomst av språkstrukturen C. Dermed kan nøkkelen til et katalogelement modelleres med følgende struktur NodeKey.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Å redde NodeKey i lagring nødvendig i objekt MDB_val plasser datapekeren til adressen til begynnelsen av strukturen, og beregn størrelsen med funksjonen sizeof.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = sizeof(NodeKey),
        .mv_data = (void *)key
    };
}

I det første kapittelet om databaseutvelgelseskriterier nevnte jeg å minimere dynamiske allokeringer innenfor CRUD-operasjoner som en viktig utvelgelsesfaktor. Funksjonskode serialize viser hvordan de i tilfellet med LMDB kan unngås helt ved innsetting av nye poster i databasen. Den innkommende byte-arrayen fra serveren blir først transformert til stabelstrukturer, og deretter blir de trivielt dumpet inn i lagring. Med tanke på at det heller ikke er noen dynamiske allokeringer inne i LMDB, kan du få en fantastisk situasjon etter iOS-standarder - bruk kun stackminne for å jobbe med data langs hele veien fra nettverket til disken!

Bestilling av nøkler med en binær komparator

Nøkkelordreforholdet er spesifisert av en spesiell funksjon kalt en komparator. Siden motoren ikke vet noe om semantikken til bytene de inneholder, har standardkomparatoren ikke noe annet valg enn å ordne nøklene i leksikografisk rekkefølge, og ty til en byte-for-byte-sammenligning. Å bruke den til å organisere strukturer er beslektet med barbering med en hoggeøks. Men i enkle tilfeller finner jeg denne metoden akseptabel. Alternativet er beskrevet nedenfor, men her vil jeg legge merke til et par raker spredt langs denne stien.

Det første du må huske er minnerepresentasjonen av primitive datatyper. På alle Apple-enheter lagres således heltallsvariabler i formatet Lille Endian. Dette betyr at den minst signifikante byten vil være til venstre, og det vil ikke være mulig å sortere heltall ved hjelp av en byte-for-byte sammenligning. For eksempel, å prøve å gjøre dette med et sett med tall fra 0 til 511 vil gi følgende resultat.

// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)

For å løse dette problemet må heltallene lagres i nøkkelen i et format som passer for byte-byte-komparatoren. Funksjoner fra familien vil hjelpe deg med å utføre den nødvendige transformasjonen hton* (spesielt htons for dobbelbyte tall fra eksemplet).

Formatet for å representere strenger i programmering er som du vet en helhet historie. Hvis semantikken til strenger, så vel som kodingen som brukes for å representere dem i minnet, antyder at det kan være mer enn én byte per tegn, er det bedre å umiddelbart forlate ideen om å bruke en standard komparator.

Den andre tingen å huske på er innrettingsprinsipper strukturfeltkompilatoren. På grunn av dem kan bytes med søppelverdier dannes i minnet mellom felt, noe som selvfølgelig bryter byte-byte-sortering. For å eliminere søppel, må du enten deklarere felt i en strengt definert rekkefølge, med justeringsregler i tankene, eller bruke attributtet i strukturdeklarasjonen packed.

Bestilling av nøkler med ekstern komparator

Nøkkelsammenligningslogikken kan være for kompleks for en binær komparator. En av mange årsaker er tilstedeværelsen av tekniske felt innenfor strukturer. Jeg vil illustrere deres forekomst ved å bruke eksemplet på en nøkkel for et katalogelement som allerede er kjent for oss.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameBuffer[256];​
} NodeKey;

Til tross for sin enkelhet, bruker den i de aller fleste tilfeller for mye minne. Bufferen for navnet tar opp 256 byte, selv om fil- og mappenavn i gjennomsnitt sjelden overstiger 20-30 tegn.

En av standardteknikkene for å optimalisere størrelsen på en post er å "trimme" den til den faktiske størrelsen. Essensen er at innholdet i alle felt med variabel lengde lagres i en buffer på slutten av strukturen, og lengdene deres lagres i separate variabler.​ Ifølge denne tilnærmingen er nøkkelen NodeKey omdannes som følger.

typedef struct NodeKey {​
    EntityId parentId;​
    uint8_t type;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeKey;

Videre, ved serialisering er ikke datastørrelsen spesifisert sizeof hele strukturen, og størrelsen på alle feltene er en fast lengde pluss størrelsen på den faktisk brukte delen av bufferen.

MDB_val serialize(NodeKey * const key) {
    return MDB_val {
        .mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
        .mv_data = (void *)key
    };
}

Som et resultat av refaktoriseringen fikk vi betydelige besparelser i plassen som ble okkupert av nøkler. Men på grunn av det tekniske feltet nameLength, er standard binær komparator ikke lenger egnet for nøkkelsammenligning. Hvis vi ikke erstatter det med vårt eget, vil lengden på navnet være en høyere prioritert faktor i sorteringen enn selve navnet.

LMDB lar hver database ha sin egen nøkkelsammenligningsfunksjon. Dette gjøres ved hjelp av funksjonen mdb_set_compare strengt tatt før åpning. Av åpenbare grunner kan den ikke endres gjennom hele databasens levetid. Komparatoren mottar to nøkler i binært format som input, og ved utgangen returnerer den sammenligningsresultatet: mindre enn (-1), større enn (1) eller lik (0). Pseudokode for NodeKey ser sånn ut.

int compare(MDB_val * const a, MDB_val * const b) {​
    NodeKey * const aKey = (NodeKey * const)a->mv_data;​
    NodeKey * const bKey = (NodeKey * const)b->mv_data;​
    return // ...
}​

Så lenge alle nøklene i databasen er av samme type, er det lovlig å ubetinget caste deres byte-representasjon til typen applikasjonsnøkkelstruktur. Det er én nyanse her, men den vil bli diskutert nedenfor i underavsnittet "Leseposter".

Serialisering av verdier

LMDB jobber ekstremt intensivt med nøklene til lagrede poster. Deres sammenligning med hverandre skjer innenfor rammen av enhver anvendt operasjon, og ytelsen til hele løsningen avhenger av hastigheten til komparatoren. I en ideell verden bør standard binær komparator være nok til å sammenligne nøkler, men hvis du måtte bruke dine egne, bør prosedyren for å deserialisere nøkler i den være så rask som mulig.

Databasen er ikke spesielt interessert i verdidelen av posten (verdi). Konverteringen fra en byte-representasjon til et objekt skjer bare når det allerede kreves av applikasjonskoden, for eksempel for å vise den på skjermen. Siden dette skjer relativt sjelden, er ikke hastighetskravene for denne prosedyren så kritiske, og i implementeringen står vi mye friere til å fokusere på bekvemmelighet.For å serialisere metadata om filer som ennå ikke er lastet ned, bruker vi for eksempel NSKeyedArchiver.

NSData *data = serialize(object);​
MDB_val value = {​
    .mv_size = data.length,​
    .mv_data = (void *)data.bytes​
};

Det er imidlertid tider når ytelse fortsatt betyr noe. For eksempel, når vi lagrer metainformasjon om filstrukturen til en brukersky, bruker vi den samme minnedumpen av objekter. Høydepunktet i oppgaven med å generere en serialisert representasjon av dem er det faktum at elementene i en katalog er modellert av et hierarki av klasser.

For å implementere det på C-språket, plasseres spesifikke felt til arvingene i separate strukturer, og deres forbindelse med basisen er spesifisert gjennom et felt av typeforening. Det faktiske innholdet i fagforeningen spesifiseres via den tekniske attributttypen.

typedef struct NodeValue {​
    EntityId localId;​
    EntityType type;​
    union {​
        FileInfo file;​
        DirectoryInfo directory;​
    } info;​
    uint8_t nameLength;​
    uint8_t nameBuffer[256];​
} NodeValue;​

Legge til og oppdatere poster

Den serialiserte nøkkelen og verdien kan legges til butikken. For å gjøre dette, bruk funksjonen mdb_put.

// key и value имеют тип MDB_val​
mdb_put(..., &key, &value, MDB_NOOVERWRITE);

På konfigurasjonsstadiet kan lagringen tillates eller forbys å lagre flere poster med samme nøkkel. Hvis duplisering av nøkler er forbudt, kan du når du setter inn en post bestemme om oppdatering av en eksisterende post er tillatt eller ikke. Hvis frynsing bare kan oppstå som et resultat av en feil i koden, kan du beskytte deg mot det ved å spesifisere flagget NOOVERWRITE.

Lese oppføringer

For å lese poster i LMDB, bruk funksjonen mdb_get. Hvis nøkkelverdi-paret er representert av tidligere dumpede strukturer, ser denne prosedyren slik ut.

NodeValue * const readNode(..., NodeKey * const key) {​
    MDB_val rawKey = serialize(key);​
    MDB_val rawValue;​
    mdb_get(..., &rawKey, &rawValue);​
    return (NodeValue * const)rawValue.mv_data;​
}

Den presenterte oppføringen viser hvordan serialisering gjennom strukturdump lar deg bli kvitt dynamiske tildelinger, ikke bare når du skriver, men når du leser data. Avledet fra funksjon mdb_get pekeren ser nøyaktig på den virtuelle minneadressen der databasen lagrer byte-representasjonen av objektet. Faktisk får vi en slags ORM som gir svært høy datalesehastighet nesten gratis. Til tross for all skjønnheten i tilnærmingen, er det nødvendig å huske flere funksjoner knyttet til den.

1. For en skrivebeskyttet transaksjon er pekeren til verdistrukturen garantert kun gyldig til transaksjonen er avsluttet. Som nevnt tidligere forblir B-tresidene som et objekt befinner seg på, takket være kopier-på-skriv-prinsippet, uendret så lenge de refereres til av minst én transaksjon. Samtidig, så snart den siste transaksjonen knyttet til dem fullføres, kan sidene gjenbrukes til nye data. Hvis det er nødvendig for objekter å overleve transaksjonen som genererte dem, må de fortsatt kopieres.
2. ​​For en readwrite-transaksjon vil pekeren til den resulterende verdistrukturen bare være gyldig frem til den første endringsprosedyren (skriving eller sletting av data).
3. Selv om strukturen NodeValue ikke fullverdig, men trimmet (se underavsnittet "Bestille nøkler ved hjelp av en ekstern komparator"), kan du trygt få tilgang til feltene gjennom pekeren. Det viktigste er ikke å avvise det!
4. Under ingen omstendigheter skal strukturen modifiseres gjennom den mottatte pekeren. Alle endringer må kun gjøres gjennom metoden mdb_put. Men uansett hvor hardt du vil gjøre dette, vil det ikke være mulig, siden minneområdet der denne strukturen er plassert er kartlagt i skrivebeskyttet modus.
5. Tilordne en fil på nytt til prosessadresseområdet for for eksempel å øke den maksimale lagringsstørrelsen ved å bruke funksjonen mdb_env_set_map_size ugyldiggjør fullstendig alle transaksjoner og relaterte enheter generelt og pekere til bestemte objekter spesielt.

Til slutt, en annen funksjon er så lumsk at å avsløre essensen ikke passer inn i bare et annet avsnitt. I kapittelet om B-treet ga jeg et diagram over hvordan sidene er ordnet i minnet. Det følger av dette at adressen til begynnelsen av bufferen med serialiserte data kan være helt vilkårlig. På grunn av dette mottok pekeren til dem i strukturen MDB_val og redusert til en peker til en struktur, viser det seg å være ujustert i det generelle tilfellet. Samtidig krever arkitekturen til noen brikker (i tilfellet med iOS er dette armv7) at adressen til alle data er et multiplum av størrelsen på maskinordet eller, med andre ord, bitstørrelsen til systemet ( for armv7 er det 32 ​​bits). Med andre ord, en operasjon som *(int *foo)0x800002 på dem tilsvarer rømning og fører til henrettelse med en dom EXC_ARM_DA_ALIGN. Det er to måter å unngå en så trist skjebne på.

Den første koker ned til foreløpig kopiering av data til en åpenbart justert struktur. For eksempel, på en tilpasset komparator vil dette gjenspeiles som følger.

int compare(MDB_val * const a, MDB_val * const b) {
    NodeKey aKey, bKey;
    memcpy(&aKey, a->mv_data, a->mv_size);
    memcpy(&bKey, b->mv_data, b->mv_size);
    return // ...
}

En alternativ måte er å varsle kompilatoren på forhånd om at nøkkelverdistrukturer kanskje ikke er attributtjustert aligned(1). På ARM kan du ha samme effekt oppnå og bruke det pakket attributtet. Tatt i betraktning at det også bidrar til å optimere plassen som opptas av strukturen, virker denne metoden å foretrekke for meg, selv om приводит til en økning i kostnadene for datatilgangsoperasjoner.

typedef struct __attribute__((packed)) NodeKey {
    uint8_t parentId;
    uint8_t type;
    uint8_t nameLength;
    uint8_t nameBuffer[256];
} NodeKey;

Områdesøk

For å iterere over en gruppe poster, gir LMDB en markørabstraksjon. La oss se på hvordan du jobber med det ved å bruke eksempelet på en tabell med brukerskymetadata som vi allerede er kjent med.

Som en del av å vise en liste over filer i en katalog, er det nødvendig å finne alle nøklene som underordnede filer og mapper er knyttet til. I de forrige underavsnittene sorterte vi nøklene NodeKey slik at de primært er sortert etter ID-en til overordnet katalog. Teknisk sett kommer oppgaven med å hente innholdet i en mappe ned til å plassere markøren på den øvre grensen til gruppen av nøkler med et gitt prefiks og deretter iterere til den nedre grensen.

Den øvre grensen kan bli funnet direkte ved sekvensielt søk. For å gjøre dette plasseres markøren i begynnelsen av hele listen over nøkler i databasen og økes ytterligere til en nøkkel med identifikatoren til overordnet katalog vises under den. Denne tilnærmingen har 2 åpenbare ulemper:

1. Lineær søkekompleksitet, selv om den, som kjent, i trær generelt og i et B-tre spesielt kan utføres i logaritmisk tid.
2. Forgjeves løftes alle sidene foran den som søkes fra filen til hovedminnet, noe som er ekstremt kostbart.

Heldigvis gir LMDB API en effektiv måte å plassere markøren på. For å gjøre dette må du generere en nøkkel hvis verdi åpenbart er mindre enn eller lik nøkkelen som er plassert ved den øvre grensen av intervallet. For eksempel, i forhold til listen i figuren over, kan vi lage en nøkkel hvor feltet parentId vil være lik 2, og alle resten er fylt med nuller. En slik delvis fylt nøkkel leveres til funksjonsinngangen mdb_cursor_get som indikerer operasjonen MDB_SET_RANGE.

NodeKey upperBoundSearchKey = {​
    .parentId = 2,​
    .type = 0,​
    .nameLength = 0​
};​
MDB_val value, key = serialize(upperBoundSearchKey);​
MDB_cursor *cursor;​
mdb_cursor_open(..., &cursor);​
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);

Hvis den øvre grensen til en gruppe nøkler blir funnet, itererer vi over den til enten vi møtes eller nøkkelen møter en annen parentId, ellers går ikke nøklene tom i det hele tatt

do {​
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);​
    // processing...​
} while (MDB_NOTFOUND != rc && // check end of table​
         IsTargetKey(key));    // check end of keys group​​

Det som er fint er at som en del av iterasjonen ved å bruke mdb_cursor_get, får vi ikke bare nøkkelen, men også verdien. Hvis du, for å oppfylle prøvetakingsvilkårene, må sjekke blant annet feltene fra verdidelen av posten, er de ganske tilgjengelige uten ekstra bevegelser.

4.3. Modellering av forhold mellom tabeller

Nå har vi klart å vurdere alle aspekter ved design og arbeid med en enkelttabellsdatabase. Vi kan si at en tabell er et sett med sorterte poster som består av samme type nøkkel-verdi-par. Hvis du viser en nøkkel som et rektangel og den tilhørende verdien som et parallellepiped, får du et visuelt diagram av databasen.

â € <

Men i det virkelige liv er det sjelden mulig å klare seg med så lite blodsutgytelse. Ofte i en database kreves det for det første å ha flere tabeller, og for det andre å gjøre valg i dem i en annen rekkefølge enn primærnøkkelen. Denne siste delen er viet spørsmålene om deres opprettelse og sammenkobling.

Indekstabeller

Skyapplikasjonen har en "Galleri"-seksjon. Den viser medieinnhold fra hele skyen, sortert etter dato. For å implementere et slikt valg optimalt, ved siden av hovedtabellen må du opprette en annen med en ny type nøkler. De vil inneholde et felt med datoen filen ble opprettet, som vil fungere som det primære sorteringskriteriet. Fordi de nye nøklene refererer til samme data som nøklene i hovedtabellen, kalles de indeksnøkler. På bildet nedenfor er de uthevet i oransje.

For å skille nøklene til forskjellige tabeller fra hverandre i samme database, ble det lagt til et ekstra teknisk felt tableId til alle. Ved å gjøre det til høyeste prioritet for sortering, vil vi oppnå gruppering av nøkler først etter tabeller, og innenfor tabeller - i henhold til våre egne regler.

Indeksnøkkelen refererer til de samme dataene som primærnøkkelen. En enkel implementering av denne egenskapen ved å knytte til den en kopi av verdidelen av primærnøkkelen er ikke optimal fra flere synspunkter:

1. Når det gjelder plass tatt opp, kan metadataene være ganske rike.
2. Fra et ytelsessynspunkt, siden når du oppdaterer metadataene til en node, må du skrive den om med to nøkler.
3. Fra synspunkt av kodestøtte, hvis vi glemmer å oppdatere dataene for en av nøklene, vil vi få en unnvikende feil med datainkonsekvens i lagringen.

Deretter vil vi vurdere hvordan vi kan eliminere disse manglene.

Organisere relasjoner mellom tabeller

Mønsteret egner seg godt for å koble sammen indekstabellen med hovedtabellen "nøkkel som verdi". Som navnet antyder, er verdidelen av indeksposten en kopi av primærnøkkelverdien. Denne tilnærmingen eliminerer alle de ovennevnte ulempene forbundet med å lagre en kopi av verdidelen av den primære posten. Den eneste kostnaden er at for å få en verdi etter indeksnøkkel, må du gjøre 2 spørringer til databasen i stedet for ett. Skjematisk ser det resulterende databaseskjemaet slik ut.

Et annet mønster for å organisere relasjoner mellom tabeller er "overflødig nøkkel". Essensen er å legge til flere attributter til nøkkelen, som ikke er nødvendige for å sortere, men for å gjenskape den tilknyttede nøkkelen. I Mail.ru Cloud-applikasjonen er det virkelige eksempler på bruken av den, for å unngå et dypdykk i konteksten av spesifikke iOS-rammeverk, vil jeg gi et fiktivt, men et klarere eksempel

Cloud mobile klienter har en side som viser alle filene og mappene som brukeren har delt med andre. Siden det er relativt få slike filer, og det er knyttet mange ulike typer spesifikk informasjon om offentlighet til dem (hvem som gis tilgang, med hvilke rettigheter osv.), vil det ikke være rasjonelt å belaste verdidelen av ta opp i hovedtabellen med den. Men hvis du vil vise slike filer offline, må du fortsatt lagre dem et sted. En naturlig løsning er å lage et eget bord for det. I diagrammet nedenfor er nøkkelen prefikset med "P", og plassholderen "propname" kan erstattes med den mer spesifikke verdien "public info".​

Alle unike metadata, av hensyn til å lagre som den nye tabellen ble opprettet, plasseres i verdidelen av posten. Samtidig vil du ikke duplisere dataene om filer og mapper som allerede er lagret i hovedtabellen. I stedet legges redundante data til "P"-nøkkelen i form av feltene "node ID" og "tidsstempel". Takket være dem kan du konstruere en indeksnøkkel, som du kan få en primærnøkkel fra, som du til slutt kan få nodemetadata fra.

Konklusjon

Vi vurderer resultatene av implementeringen av LMDB positivt. Etter det ble antallet programfrysinger redusert med 30%.

Resultatene av arbeidet som ble gjort ga gjenklang utenfor iOS-teamet. For øyeblikket har også en av hoveddelene "Filer" i Android-applikasjonen gått over til å bruke LMDB, og andre deler er på vei. C-språket, som nøkkelverdilageret er implementert i, var en god hjelp til i utgangspunktet å lage et applikasjonsrammeverk rundt det på tvers av plattformer i C++. En kodegenerator ble brukt til å sømløst koble det resulterende C++-biblioteket med plattformkode i Objective-C og Kotlin Jinni fra Dropbox, men det er en helt annen historie.

Kilde: www.habr.com