I efteråret 2019 fandt en længe ventet begivenhed sted i Mail.ru Cloud iOS-teamet. Hoveddatabasen for vedvarende lagring af applikationstilstand er blevet ret eksotisk for den mobile verden (LMDB). Under klippet inviteres din opmærksomhed til dens detaljerede anmeldelse i fire dele. Lad os først tale om årsagerne til et så ikke-trivielt og vanskeligt valg. Lad os derefter gå videre til overvejelserne om tre hvaler i hjertet af LMDB-arkitekturen: hukommelseskortede filer, B + træ, kopi-på-skriv-tilgang til implementering af transaktions- og multiversionering. Til sidst til dessert - den praktiske del. I den vil vi se på, hvordan man designer og implementerer et basisskema med flere tabeller, inklusive en indeks, oven på lav-niveau nøgleværdi API.
Indhold
3.1.
3.2.
3.3.
4.1.
4.2.
4.3.
1. Implementeringsmotivation
En gang om året, i 2015, sørgede vi for at tage en metrik, hvor ofte grænsefladen til vores applikation halter. Vi gjorde ikke bare dette. Vi har flere og flere klager over, at applikationen nogle gange holder op med at reagere på brugerhandlinger: knapper trykkes ikke, lister ruller ikke osv. Om målingernes mekanik på AvitoTech, så her giver jeg kun rækkefølgen af numre.
Måleresultaterne blev et koldt brusebad for os. Det viste sig, at problemerne forårsaget af fryse er meget mere end nogen anden. Hvis den vigtigste tekniske indikator for kvalitet var nedbrudsfri, før man indså dette faktum, så efter fokus på frysefri.
at have bygget og har brugt и analyse af deres årsager, blev hovedfjenden klar - tung forretningslogik, der udføres i programmets hovedtråd. En naturlig reaktion på denne skændsel var et brændende ønske om at skubbe det ind i arbejdsstrømmene. For en systematisk løsning af dette problem valgte vi en flertrådsarkitektur baseret på lette skuespillere. Jeg dedikerede hendes tilpasninger til iOS-verdenen i den kollektive twitter og . Som en del af den aktuelle historie vil jeg understrege de aspekter af beslutningen, der påvirkede valget af databasen
Aktørmodellen for systemorganisation antager, at multithreading bliver dens anden essens. Modelobjekter i den kan lide at krydse trådgrænser. Og det gør de ikke nogle gange og nogle steder, men næsten konstant og overalt.
Databasen er en af hjørnestenskomponenterne i det præsenterede diagram. Dens hovedopgave er at implementere et makromønster . Hvis det i virksomhedsverdenen bruges til at organisere datasynkronisering mellem tjenester, så i tilfælde af en aktørarkitektur, data mellem tråde. Derfor havde vi brug for en sådan database, at arbejde med som i et multi-threaded miljø ikke forårsager selv minimale vanskeligheder. Dette betyder især, at de objekter, der stammer fra det, skal være mindst trådsikre og ideelt set slet ikke kan ændres. Som du ved, kan sidstnævnte bruges samtidigt fra flere tråde uden at ty til nogen form for låse, hvilket har en gavnlig effekt på ydeevnen.
Den anden væsentlige faktor, der påvirkede valget af databasen, var vores cloud API. Det var inspireret af git-tilgangen til synkronisering. Ligesom ham sigtede vi mod , som ser mere end passende ud for cloud-klienter. Det blev antaget, at de kun én gang ville pumpe hele skyens tilstand ud, og så ville synkronisering i langt de fleste tilfælde ske gennem rullende ændringer. Ak, denne mulighed er stadig kun i den teoretiske zone, og i praksis har klienter ikke lært at arbejde med plastre. Det er der en række objektive grunde til, som vi, for ikke at forsinke indførelsen, vil udelade i parentes. Nu er meget mere interessant de lærerige resultater af lektionen om, hvad der sker, når API'en sagde "A", og dens forbruger ikke sagde "B".
Så hvis du forestiller dig git, som, når du udfører en pull-kommando, i stedet for at anvende patches på et lokalt snapshot, sammenligner dens fulde tilstand med den fulde server, så vil du have en ret præcis idé om, hvordan synkronisering forekommer i cloud-klienter. Det er let at gætte, at det til implementeringen er nødvendigt at allokere to DOM-træer i hukommelsen med metainformation om alle server- og lokale filer. Det viser sig, at hvis en bruger gemmer 500 tusinde filer i skyen, så er det nødvendigt at genskabe og ødelægge to træer med 1 million noder for at synkronisere det. Men hver node er et aggregat, der indeholder en graf over underobjekter. I dette lys var profileringsresultaterne forventet. Det viste sig, at selv uden at tage højde for flettealgoritmen, koster selve proceduren med at skabe og derefter ødelægge et stort antal små objekter en pæn krone. Situationen forværres af det faktum, at den grundlæggende synkroniseringsoperation er inkluderet i et stort antal af brugerscripts. Som et resultat fikser vi det andet vigtige kriterium ved valg af en database - evnen til at implementere CRUD-operationer uden dynamisk allokering af objekter.
Andre krav er mere traditionelle, og deres fulde liste er som følger.
- Trådsikkerhed.
- Multibearbejdning. Dikteret af ønsket om at bruge den samme databaseinstans til at synkronisere tilstand ikke kun mellem tråde, men også mellem hovedapplikationen og iOS-udvidelser.
- Evnen til at repræsentere lagrede enheder som ikke-mutable objekter
- Mangel på dynamiske allokeringer inden for CRUD-operationer.
- Transaktionsstøtte til grundlæggende egenskaber Nøgleord: atomicitet, konsistens, isolation og pålidelighed.
- Sæt fart på de mest populære sager.
Med dette sæt krav var og er SQLite stadig et godt valg. Men som en del af undersøgelsen af alternativer stødte jeg på en bog . Under hendes ledelse blev der skrevet et benchmark, der sammenligner arbejdshastigheden med forskellige databaser i rigtige skyscenarier. Resultatet oversteg de vildeste forventninger. I de mest populære tilfælde - at få en markør på en sorteret liste over alle filer og en sorteret liste over alle filer for en given mappe - viste LMDB sig at være 10 gange hurtigere end SQLite. Valget blev indlysende.
2. LMDB Positionering
LMDB er et bibliotek, meget lille (kun 10K linjer), som implementerer det laveste grundlæggende lag af databaser - storage.
Ovenstående diagram viser, at sammenligning af LMDB med SQLite, som implementerer endnu højere niveauer, generelt ikke er mere korrekt end SQLite med Core Data. Det ville være mere fair at nævne de samme storage-motorer som lige konkurrenter – BerkeleyDB, LevelDB, Sophia, RocksDB osv. Der er endda udviklinger, hvor LMDB fungerer som en storage-motor-komponent til SQLite. Det første sådan eksperiment i 2012 forfatter LMDB . viste sig at være så spændende, at hans initiativ blev opfanget af OSS-entusiaster, og fandt sin fortsættelse i lyset af . I januar 2020 er forfatteren til dette projekt Den Shearer det på LinuxConfAu.
Hovedanvendelsen af LMDB er som en motor til applikationsdatabaser. Biblioteket skylder udviklerne sit udseende , som var stærkt utilfredse med BerkeleyDB som grundlag for deres projekt. Trænger sig væk fra det ydmyge bibliotek , var Howard Chu i stand til at skabe et af vor tids mest populære alternativer. Han viede sin meget seje rapport til denne historie såvel som til den interne struktur i LMDB . Leonid Yuriev (aka ) fra Positive Technologies i hans foredrag på Highload 2015 . Heri taler han om LMDB i forbindelse med en lignende opgave med at implementere ReOpenLDAP, og LevelDB har allerede været udsat for sammenlignende kritik. Som et resultat af implementeringen fik Positive Technologies endda en aktivt udviklende gaffel med meget velsmagende funktioner, optimeringer og .
LMDB bruges også ofte som en as is storage. For eksempel Mozilla Firefox-browseren det til en række behov, og fra version 9 Xcode dens SQLite til at gemme indekser.
Motoren fik også fat i mobiludviklingens verden. Spor af dens brug kan være i iOS-klienten til Telegram. LinkedIn gik et skridt videre og valgte LMDB som standardlageret for dets hjemmelavede data-caching-ramme, Rocket Data, om hvilke i en artikel i 2016.
LMDB kæmper med succes om en plads i solen i den niche, som BerkeleyDB efterlod efter overgangen under Oracles kontrol. Biblioteket er elsket for dets hurtighed og pålidelighed, selv i sammenligning med sin egen slags. Der er som bekendt ingen gratis frokoster, og jeg vil gerne understrege den afvejning, du skal stå i øjnene, når du skal vælge mellem LMDB og SQLite. Diagrammet ovenfor viser tydeligt, hvordan den øgede hastighed opnås. For det første betaler vi ikke for yderligere lag af abstraktion oven på disklager. Selvfølgelig, i en god arkitektur, kan du stadig ikke undvære dem, og de vil uundgåeligt vises i applikationskoden, men de vil være meget tyndere. De vil ikke have funktioner, der ikke kræves af en specifik applikation, for eksempel understøttelse af forespørgsler i SQL-sproget. For det andet bliver det muligt optimalt at implementere kortlægningen af applikationsoperationer til anmodninger til disklager. Hvis SQLite kommer fra de gennemsnitlige behov for en gennemsnitlig applikation, så er du som applikationsudvikler godt klar over de vigtigste belastningsscenarier. For en mere produktiv løsning skal du betale en forhøjet pris for både udviklingen af den oprindelige løsning og dens efterfølgende support.
3. Tre hvaler LMDB
Efter at have set på LMDB fra et fugleperspektiv, er det tid til at gå dybere. De næste tre afsnit vil blive afsat til analysen af de vigtigste hvaler, som lagringsarkitekturen hviler på:
- Hukommelseskortede filer som en mekanisme til at arbejde med disk og synkronisering af interne datastrukturer.
- B+-træ som en organisation af den lagrede datastruktur.
- Kopier-på-skriv som en tilgang til at levere ACID-transaktionsegenskaber og multiversionering.
3.1. Hval #1. Hukommelseskortede filer
Hukommelseskortede filer er så vigtigt et arkitektonisk element, at de endda vises i navnet på depotet. Spørgsmål med caching og synkronisering af adgang til lagrede informationer er fuldstændigt prisgivet af operativsystemet. LMDB indeholder ingen caches i sig selv. Dette er en bevidst beslutning af forfatteren, da læsning af data direkte fra kortlagte filer giver dig mulighed for at skære en masse hjørner i implementeringen af motoren. Nedenfor er en langt fra komplet liste over nogle af dem.
- At opretholde konsistensen af data i lageret, når der arbejdes med det fra flere processer, bliver operativsystemets ansvar. I næste afsnit diskuteres denne mekaniker i detaljer og med billeder.
- Fraværet af caches fritager fuldstændigt LMDB for de overhead, der er forbundet med dynamiske tildelinger. At læse data i praksis er at sætte markøren til den korrekte adresse i den virtuelle hukommelse og intet mere. Det lyder som fantasi, men i lagerkilden er alle calloc-kald koncentreret i lagerkonfigurationsfunktionen.
- Fraværet af caches betyder også fraværet af låse forbundet med synkronisering for at få adgang til dem. Læsere, hvoraf et vilkårligt antal kan eksistere på samme tid, støder ikke på en eneste mutex på vej til dataene. På grund af dette har læsehastigheden en ideel lineær skalerbarhed i forhold til antallet af CPU'er. I LMDB synkroniseres kun ændringshandlinger. Der kan kun være én forfatter ad gangen.
- Et minimum af caching og synkroniseringslogik gemmer koden fra en ekstremt kompleks type fejl, der er forbundet med at arbejde i et multi-threaded miljø. Der var to interessante databaseundersøgelser på Usenix OSDI 2014-konferencen: и . Fra dem kan du få information om både den hidtil usete pålidelighed af LMDB og den næsten fejlfri implementering af ACID-egenskaberne for transaktioner, som overgår den i den samme SQLite.
- Minimalismen ved LMDB gør det muligt at placere maskinrepræsentationen af dens kode fuldstændigt i processorens L1-cache med de resulterende hastighedskarakteristika.
Desværre er hukommelseskortede filer i iOS ikke så rosenrøde, som vi gerne ville have. For at tale mere bevidst om de ulemper, der er forbundet med dem, er det nødvendigt at huske de generelle principper for implementering af denne mekanisme i operativsystemer.
Generel information om hukommelseskortede filer
Med hver eksekverbar applikation knytter operativsystemet en enhed kaldet en proces. Hver proces er tildelt en sammenhængende række af adresser, hvor den placerer alt, hvad der skal til for at fungere. De laveste adresser indeholder sektioner med kode og hårdkodede data og ressourcer. Dernæst kommer den opadgående blok af dynamisk adresserum, som er velkendt for os som dyngen. Den indeholder adresserne på enheder, der vises under programmets drift. Øverst er det hukommelsesområde, der bruges af applikationsstakken. Den enten vokser eller krymper, med andre ord har dens størrelse også en dynamisk karakter. For at stakken og heapen ikke skal skubbe og forstyrre hinanden, er de adskilt i forskellige ender af adresserummet.Der er et hul mellem de to dynamiske sektioner i top og bund. Adresserne i dette midterste afsnit bruges af operativsystemet til at associere med en proces af forskellige entiteter. Det kan især kortlægge et bestemt kontinuerligt sæt adresser til en fil på disken. Sådan en fil kaldes en memory-mapped fil
Adressepladsen, der er allokeret til en proces, er enorm. Teoretisk set er antallet af adresser kun begrænset af størrelsen af pointeren, som bestemmes af systemets bitdybde. Hvis fysisk hukommelse blev tildelt den 1-i-1, så ville den første proces sluge hele RAM'en, og der ville ikke være tale om multitasking.
Vi ved dog af erfaring, at moderne operativsystemer kan køre så mange processer, som du vil på samme tid. Dette er muligt på grund af det faktum, at de tildeler meget hukommelse til processer kun på papir, men i virkeligheden indlæser de kun den del, der er efterspurgt her og nu, i den fysiske hovedhukommelse. Derfor kaldes hukommelsen forbundet med processen virtuel.
Operativsystemet organiserer virtuel og fysisk hukommelse i sider af en vis størrelse. Så snart en bestemt side af virtuel hukommelse er efterspurgt, indlæser operativsystemet den i den fysiske hukommelse og lægger en korrespondance mellem dem i en speciel tabel. Hvis der ikke er nogen ledige pladser, kopieres en af de tidligere indlæste sider til disken, og den anmodede træder i stedet. Denne procedure, som vi snart vender tilbage til, kaldes bytte. Nedenstående figur illustrerer den beskrevne proces. På den blev side A med adresse 0 indlæst og placeret på hovedhukommelsessiden med adresse 4. Dette faktum blev afspejlet i korrespondancetabellen i celle nummer 0.
Med hukommelseskortede filer er historien nøjagtig den samme. Logisk set er de angiveligt kontinuerligt og fuldstændigt placeret i det virtuelle adresserum. De kommer dog ind i den fysiske hukommelse side for side og kun efter behov. Ændring af sådanne sider synkroniseres med filen på disken. Således kan du udføre fil I/O ved blot at arbejde med bytes i hukommelsen - alle ændringer vil automatisk blive overført af operativsystemets kerne til den originale fil.
â € <
Billedet nedenfor viser, hvordan LMDB synkroniserer sin tilstand, når der arbejdes med databasen fra forskellige processer. Ved at kortlægge den virtuelle hukommelse af forskellige processer på den samme fil forpligter vi de facto operativsystemet til transitivt at synkronisere visse blokke af deres adresserum med hinanden, hvilket er der, hvor LMDB ser ud.
â € <
En vigtig nuance er, at LMDB ændrer datafilen som standard gennem skrivesystemopkaldsmekanismen, og selve filen vises i skrivebeskyttet tilstand. Denne tilgang har to vigtige implikationer.
Den første konsekvens er fælles for alle operativsystemer. Dens essens er at tilføje beskyttelse mod utilsigtet beskadigelse af databasen med forkert kode. Som du ved, er de eksekverbare instruktioner for en proces fri til at få adgang til data fra hvor som helst i dens adresserum. På samme tid, som vi lige huskede, betyder visning af en fil i læse-skrivetilstand, at enhver instruktion også kan ændre den. Hvis hun gør dette ved en fejltagelse, f.eks. forsøger at overskrive et array-element ved et ikke-eksisterende indeks, kan hun på denne måde ved et uheld ændre filen, der er knyttet til denne adresse, hvilket vil føre til databasekorruption. Hvis filen vises i skrivebeskyttet tilstand, vil et forsøg på at ændre adresserummet, der svarer til den, føre til programnedbrud med signalet SIGSEGV, og filen forbliver intakt.
Den anden konsekvens er allerede specifik for iOS. Hverken forfatteren eller andre kilder nævner det eksplicit, men uden det ville LMDB være uegnet til at køre på dette mobile operativsystem. Det næste afsnit er viet til dets overvejelse.
Specifikationer for hukommelseskortede filer i iOS
I 2018 var der en vidunderlig rapport på WWDC . Den fortæller, at i iOS tilhører alle sider, der er placeret i fysisk hukommelse, én af 3 typer: beskidt, komprimeret og rene.
Ren hukommelse er en samling sider, der sikkert kan byttes ud af den fysiske hukommelse. De data, de indeholder, kan genindlæses fra deres originale kilder efter behov. Skrivebeskyttede hukommelseskortede filer falder ind under denne kategori. iOS er ikke bange for at fjerne siderne, der er knyttet til en fil, fra hukommelsen til enhver tid, da de med garanti er synkroniseret med filen på disken.
â € <
Alle ændrede sider kommer i beskidt hukommelse, uanset hvor de oprindeligt er placeret. Især vil hukommelseskortede filer, der er ændret ved at skrive til den virtuelle hukommelse, der er knyttet til dem, også blive klassificeret på denne måde. Åbning af LMDB med flag MDB_WRITEMAP, efter at have foretaget ændringer i det, kan du selv se.
Så snart en applikation begynder at optage for meget fysisk hukommelse, komprimerer iOS sine beskidte sider. Samlingen af hukommelse optaget af beskidte og komprimerede sider er applikationens såkaldte memory footprint. Når den når en vis tærskelværdi, kommer OOM-dræbersystemets dæmon efter processen og tvinger den til at afslutte den. Dette er det særlige ved iOS sammenlignet med desktop-operativsystemer. I modsætning hertil er sænkning af hukommelsesfodaftrykket ved at skifte sider fra fysisk hukommelse til disk ikke i iOS. Man kan kun gætte på årsagerne. Måske er proceduren for intensiv flytning af sider til disk og tilbage for energikrævende for mobile enheder, eller iOS sparer ressourcen til at omskrive celler på SSD-drev, eller måske var designerne ikke tilfredse med systemets overordnede ydeevne, hvor alt er konstant byttet. Hvorom alting er, så består faktum.
Den gode nyhed, allerede nævnt tidligere, er, at LMDB ikke bruger mmap-mekanismen til at opdatere filer som standard. Det følger heraf, at de gengivede data er klassificeret som ren hukommelse af iOS og ikke bidrager til hukommelsesfodaftrykket. Dette kan verificeres ved hjælp af Xcode-værktøjet kaldet VM Tracker. Skærmbilledet nedenfor viser den virtuelle hukommelsestilstand for iOS Cloud-applikationen under drift. I starten blev 2 LMDB-instanser initialiseret i den. Den første fik lov til at kortlægge sin fil til 1GiB virtuel hukommelse, den anden - 512MiB. På trods af det faktum, at begge lagerpladser optager en vis mængde af resident hukommelse, bidrager ingen af dem til den beskidte størrelse.
Nu er det tid til de dårlige nyheder. Takket være swap-mekanismen i 64-bit desktop-operativsystemer kan hver proces optage lige så meget virtuel adresseplads, som den ledige plads på harddisken tillader dens potentielle swap. Udskiftning af swap med komprimering i iOS reducerer det teoretiske maksimum drastisk. Nu skal alle levende processer passe ind i hovedhukommelsen (læs RAM), og alle dem, der ikke passer, er underlagt tvungen opsigelse. Det er nævnt som ovenfor , og i . Som en konsekvens begrænser iOS kraftigt mængden af tilgængelig hukommelse til tildeling via mmap. Her du kan se på de empiriske grænser for mængden af hukommelse, der kan allokeres på forskellige enheder ved hjælp af dette systemopkald. På de mest moderne modeller af smartphones er iOS blevet generøs med 2 gigabyte, og på topversioner af iPad - med 4. I praksis skal man selvfølgelig fokusere på de yngste understøttede enhedsmodeller, hvor alt er meget trist. Endnu værre, ser du på applikationens hukommelsestilstand i VM Tracker, vil du opdage, at LMDB langt fra er den eneste, der gør krav på hukommelseskortlagt hukommelse. Gode bidder bliver spist væk af systemallokatorer, ressourcefiler, billedrammer og andre mindre rovdyr.
Baseret på resultaterne af eksperimenter i skyen, kom vi frem til følgende kompromisværdier for hukommelse tildelt af LMDB: 384 megabyte for 32-bit enheder og 768 for 64-bit enheder. Når denne volumen er brugt op, begynder enhver ændringshandling at fuldføres med koden MDB_MAP_FULL. Vi observerer sådanne fejl i vores overvågning, men de er små nok til at blive forsømt på nuværende tidspunkt.
En ikke-oplagt årsag til overdreven hukommelsesforbrug ved lagring kan være transaktioner med lang levetid. For at forstå, hvordan disse to fænomener hænger sammen, vil det hjælpe os med at overveje de resterende to LMDB-hvaler.
3.2. Hval #2. B+-træ
For at emulere tabeller oven på et nøgleværdilager skal følgende handlinger være til stede i dets API:
- Indsættelse af et nyt element.
- Søg efter et element med en given nøgle.
- Sletning af et element.
- Gentag over nøgleintervaller i deres sorteringsrækkefølge.
Den enkleste datastruktur, der nemt kan implementere alle fire operationer, er et binært søgetræ. Hver af dens noder er en nøgle, der deler hele undergruppen af underordnede nøgler i to undertræer. Til venstre er dem, der er mindre end forælderen, og til højre - dem, der er større. At få et bestilt sæt nøgler opnås gennem en af de klassiske trægennemgange
Binære træer har to grundlæggende ulemper, der forhindrer dem i at være effektive som en diskdatastruktur. For det første er graden af deres balance uforudsigelig. Der er en betydelig risiko for at få træer, hvor højden af forskellige grene kan variere meget, hvilket væsentligt forværrer søgningens algoritmiske kompleksitet i forhold til det forventede. For det andet fratager overfloden af krydsforbindelser mellem noder binære træer lokalitet i hukommelsen.Tætte noder (med hensyn til links mellem dem) kan være placeret på helt forskellige sider i virtuel hukommelse. Som en konsekvens heraf kan selv en simpel gennemgang af flere naboknuder i et træ kræve besøg af et sammenligneligt antal sider. Dette er et problem, selv når vi taler om effektiviteten af binære træer som en datastruktur i hukommelsen, da konstant roterende sider i processorcachen ikke er billigt. Når det kommer til hyppigt at hæve node-relaterede sider fra disk, bliver tingene virkelig dårlige. .
B-træer, som er en udvikling af binære træer, løser problemerne identificeret i det foregående afsnit. For det første er de selvbalancerende. For det andet opdeler hver af deres noder sættet af underordnede nøgler, ikke i 2, men i M ordnede delmængder, og tallet M kan være ret stort, i størrelsesordenen flere hundrede eller endda tusinder.
Derved:
- Hver node har et stort antal allerede bestilte nøgler, og træerne er meget lave.
- Træet får egenskaben lokalitet i hukommelsen, da nøgler, der er tæt på i værdi, naturligt er placeret ved siden af hinanden på en eller naboknudepunkter.
- Reducerer antallet af transitknuder, når du går ned i træet under en søgeoperation.
- Reducerer antallet af målknudepunkter, der læses for områdeforespørgsler, da hver af dem allerede indeholder et stort antal ordnede nøgler.
LMDB bruger en variant af B-træet kaldet B+ træet til at gemme data. Diagrammet ovenfor viser de tre typer knudepunkter, som det indeholder:
- Øverst er roden. Det materialiserer intet andet end konceptet om en database i et depot. Inden for en enkelt LMDB-instans kan du oprette flere databaser, der deler det tilknyttede virtuelle adresserum. Hver af dem starter fra sin egen rod.
- På det laveste niveau er bladene (bladet). Det er dem og kun dem, der indeholder nøgle-værdi-parrene, der er gemt i databasen. Det er i øvrigt det særlige ved B+-træer. Hvis et normalt B-træ gemmer værdidelene ved noderne på alle niveauer, så er B+-variationen kun på den laveste. Efter at have rettet denne kendsgerning, vil vi i det følgende kalde undertypen af træet, der bruges i LMDB, simpelthen et B-træ.
- Mellem roden og bladene er der 0 eller flere tekniske niveauer med navigationsknuder (grene). Deres opgave er at dele det sorterede sæt nøgler mellem bladene.
Fysisk er noder hukommelsesblokke af en forudbestemt længde. Deres størrelse er et multiplum af størrelsen på hukommelsessiderne i operativsystemet, som vi talte om ovenfor. Nodestrukturen er vist nedenfor. Headeren indeholder meta-information, hvoraf den mest oplagte for eksempel er kontrolsummen. Dernæst kommer information om forskydninger, langs hvilke celler med data er placeret. Datas rolle kan enten være nøgler, hvis vi taler om navigationsknuder, eller hele nøgleværdi-par i tilfælde af blade Du kan læse mere om strukturen af sider i arbejdet .
Efter at have behandlet sideknudernes interne indhold, vil vi yderligere repræsentere LMDB B-træet på en forenklet måde i den følgende form.
Sider med noder er sekventielt arrangeret på disken. Sider med et højere nummer er placeret i slutningen af filen. Den såkaldte metaside (metaside) indeholder information om offsets, som kan bruges til at finde rødderne på alle træer. Når en fil åbnes, scanner LMDB filen side for side fra slutningen til begyndelsen for at søge efter en gyldig metaside og finder eksisterende databaser gennem den.
Nu, med en idé om den logiske og fysiske struktur af dataorganisation, kan vi fortsætte med at overveje den tredje hval af LMDB. Det er med dens hjælp, at alle lagermodifikationer sker transaktionelt og isoleret fra hinanden, hvilket giver databasen som helhed også multiversion-egenskaben.
3.3. Hval #3. kopi-på-skriv
Nogle B-træ operationer involverer at lave en hel række ændringer af dets noder. Et eksempel er at tilføje en ny nøgle til en node, der allerede har nået sin maksimale kapacitet. I dette tilfælde er det nødvendigt for det første at opdele noden i to, og for det andet at tilføje et link til den nye udvundne underordnede node i dens forælder. Denne procedure er potentielt meget farlig. Hvis der af en eller anden grund (nedbrud, strømafbrydelse osv.) kun sker en del af ændringerne fra serien, så vil træet forblive i en inkonsekvent tilstand.
En traditionel løsning til at gøre en database fejltolerant er at tilføje en ekstra disk-baseret datastruktur, transaktionsloggen, også kendt som WAL (Write-ahead log), ved siden af B-træet. Det er en fil, i slutningen af hvilken, strengt før ændringen af selve B-træet, den påtænkte operation skrives. Hvis datakorruption opdages under selvdiagnose, konsulterer databasen loggen for at rense sig selv.
LMDB har valgt en anden metode som sin fejltolerancemekanisme, som kaldes copy-on-write. Dens essens er, at i stedet for at opdatere dataene på en eksisterende side, kopierer den først det fuldstændigt og foretager alle ændringer, der allerede er i kopien.
Yderligere, for at de opdaterede data er tilgængelige, er det nødvendigt at ændre linket til den node, der er blevet opdateret i den overordnede node i forhold til den. Da det også skal modificeres til dette, er det også forhåndskopieret. Processen fortsætter rekursivt helt til roden. Dataene på metasiden er de sidste, der ændres.
Hvis processen pludselig går ned under opdateringsproceduren, vil der enten ikke blive oprettet en ny metaside, eller den bliver ikke skrevet til disken før slutningen, og dens kontrolsum vil være forkert. I begge disse to tilfælde vil de nye sider være utilgængelige, og de gamle vil ikke blive påvirket. Dette eliminerer behovet for, at LMDB skal skrive ahead-log for at opretholde datakonsistens. De facto overtager strukturen af datalagring på disken, beskrevet ovenfor, samtidig sin funktion. Fraværet af en eksplicit transaktionslog er en af funktionerne i LMDB, som giver høj datalæsningshastighed.
Den resulterende konstruktion, kaldet append-only B-tree, giver naturligvis transaktionsisolering og multiversionering. I LMDB har hver åben transaktion en opdateret trærod tilknyttet. Så længe transaktionen ikke er gennemført, vil siderne i træet, der er knyttet til den, aldrig blive ændret eller genbrugt til nye versioner af data. Du kan således arbejde lige så længe, du vil, præcis med det datasæt, der var relevant på tidspunkt, hvor transaktionen blev åbnet, selvom lageret fortsat er aktivt opdateret på dette tidspunkt. Dette er essensen af multiversion, hvilket gør LMDB til en ideel datakilde for vores elskede UICollectionView. Når du har åbnet en transaktion, behøver du ikke at øge applikationens hukommelsesfodaftryk, idet du hurtigt pumper de aktuelle data ud i en struktur i hukommelsen og er bange for at stå tilbage med ingenting. Denne funktion adskiller LMDB fra den samme SQLite, som ikke kan prale af en sådan total isolation. Efter at have åbnet to transaktioner i sidstnævnte og slettet en bestemt post i en af dem, kan den samme post ikke længere opnås inden for den anden tilbageværende.
Bagsiden af medaljen er det potentielt betydeligt højere forbrug af virtuel hukommelse. Diasset viser, hvordan databasestrukturen vil se ud, hvis den ændres på samme tid med 3 åbne læsetransaktioner, der ser på forskellige versioner af databasen. Da LMDB ikke kan genbruge noder, der er tilgængelige fra rødderne forbundet med de faktiske transaktioner, har lageret intet andet valg end at allokere endnu en fjerde rod i hukommelsen og igen klone de modificerede sider under den.
Her vil det ikke være overflødigt at genkalde afsnittet om hukommelseskortede filer. Det ser ud til, at det ekstra forbrug af virtuel hukommelse ikke burde genere os meget, da det ikke bidrager til applikationens hukommelsesfodaftryk. Men samtidig blev det bemærket, at iOS er meget nærig med at allokere det, og vi kan ikke levere en 1 terabyte LMDB-region på en server eller desktop fra masterens skulder og slet ikke tænke på denne funktion. Når det er muligt, bør du forsøge at holde transaktionernes levetid så kort som muligt.
4. Design af et dataskema oven på nøgleværdi-API'en
Lad os begynde at analysere API'et ved at se på de grundlæggende abstraktioner leveret af LMDB: miljø og databaser, nøgler og værdier, transaktioner og markører.
En note om kodelister
Alle funktioner i LMDB's offentlige API returnerer resultatet af deres arbejde i form af en fejlkode, men i alle efterfølgende lister er dens kontrol udeladt for kortheds skyld.I praksis brugte vi vores egen kode til at interagere med depotet. C++ indpakning , hvor fejl opstår som C++ undtagelser.
Som den hurtigste måde at forbinde LMDB til et iOS- eller macOS-projekt, tilbyder jeg min CocoaPod .
4.1. Grundlæggende abstraktioner
Miljø
Struktur MDB_env er er arkivet for den interne tilstand af LMDB. Familie af præfiksede funktioner mdb_env giver dig mulighed for at konfigurere nogle af dens egenskaber. I det enkleste tilfælde ser initialiseringen af motoren sådan ud.
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-applikationen ændrede vi standardværdierne for kun to parametre.
Den første er størrelsen på det virtuelle adresserum, som lagerfilen er knyttet til. Desværre, selv på den samme enhed, kan den specifikke værdi variere betydeligt fra kørsel til kørsel. For at tage højde for denne funktion i iOS vælger vi den maksimale mængde lagerplads dynamisk. Startende fra en bestemt værdi, halveres den successivt indtil funktionen mdb_env_open vil ikke returnere andet resultat end ENOMEM. I teorien er der en modsat vej - tildel først et minimum af hukommelse til motoren, og derefter, når der modtages fejl MDB_MAP_FULL, øge den. Det er dog meget mere tornet. Årsagen er, at proceduren for gentilknytning af hukommelse ved hjælp af funktionen mdb_env_set_map_size ugyldiggør alle enheder (markører, transaktioner, nøgler og værdier) modtaget fra motoren tidligere. At tage højde for en sådan vending i koden vil føre til dens betydelige komplikation. Hvis virtuel hukommelse ikke desto mindre er meget kær for dig, så kan dette være en grund til at se på den gaffel, der er gået langt foran. , hvor der blandt de erklærede funktioner er "automatisk on-the-fly databasestørrelsesjustering".
Den anden parameter, hvis standardværdi ikke passede os, regulerer mekanikken til at sikre gevindsikkerhed. Desværre, i det mindste i iOS 10, er der problemer med understøttelse af lokal lagring af tråde. Af denne grund, i eksemplet ovenfor, åbnes lageret med flaget MDB_NOTLS. Derudover krævede det også C++ indpakning at skære variabler med og i denne attribut.
Database
Databasen er en separat forekomst af B-træet, som vi talte om ovenfor. Dens åbning sker inde i en transaktion, som i starten kan virke lidt mærkelig.
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 transaktion i LMDB en lagringsenhed, ikke en specifik database. Dette koncept giver dig mulighed for at udføre atomoperationer på enheder placeret i forskellige databaser. I teorien åbner dette op for muligheden for at modellere tabeller i form af forskellige databaser, men på et tidspunkt gik jeg den anden vej, beskrevet i detaljer nedenfor.
Nøgler og værdier
Struktur MDB_val modellerer konceptet om både en nøgle og en værdi. Depotet har ingen idé om deres semantik. For hende er noget, der er anderledes, bare en række bytes af en given størrelse. Den maksimale nøglestørrelse er 512 bytes.
typedef struct MDB_val {
size_t mv_size;
void *mv_data;
} MDB_val;Butikken bruger en komparator til at sortere nøglerne i stigende rækkefølge. Hvis du ikke erstatter den med din egen, vil standarden blive brugt, som sorterer dem byte-for-byte i leksikografisk rækkefølge.
Transaktion
Transaktionsenheden er beskrevet detaljeret i , så her vil jeg gentage deres hovedegenskaber i en kort linje:
- Support til alle basale egenskaber Nøgleord: atomicitet, konsistens, isolation og pålidelighed. Jeg kan ikke undgå at bemærke, at med hensyn til holdbarhed på macOS og iOS er der en fejl rettet i MDBX. Du kan læse mere i deres .
- Tilgangen til multithreading er beskrevet af "enkelt forfatter / flere læsere"-skemaet. Forfattere blokerer hinanden, men de blokerer ikke læsere. Læsere blokerer ikke forfattere eller hinanden.
- Understøttelse af indlejrede transaktioner.
- Multiversion support.
Multiversion i LMDB er så godt, at jeg gerne vil demonstrere det i aktion. Koden nedenfor viser, at hver transaktion fungerer med præcis den version af databasen, der var relevant på tidspunktet for dens åbning, og er fuldstændig isoleret fra alle efterfølgende ændringer. Initialisering af depotet og tilføjelse af en testpost til det er ikke interessant, så disse ritualer er efterladt under spoileren.
Tilføjelse af en testindgang
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);Eventuelt anbefaler jeg at prøve det samme trick med SQLite og se, hvad der sker.
Multiversionering bringer meget gode fordele til livet for en iOS-udvikler. Ved at bruge denne egenskab kan du nemt og naturligt justere datakildeopdateringshastigheden for skærmformularer baseret på brugeroplevelsesovervejelser. Lad os for eksempel tage en sådan funktion i Mail.ru Cloud-applikationen som automatisk indlæsning af indhold fra systemets mediegalleri. Med en god forbindelse er klienten i stand til at tilføje flere billeder i sekundet til serveren. Hvis du opdaterer efter hver download UICollectionView med medieindhold i brugerens sky, kan du glemme alt om 60 fps og jævn scrolling under denne proces. For at forhindre hyppige skærmopdateringer skal du på en eller anden måde begrænse hastigheden af dataændringer i grundlaget UICollectionViewDataSource.
Hvis databasen ikke understøtter multiversionering og kun tillader dig at arbejde med den aktuelle aktuelle tilstand, skal du kopiere det enten til en datastruktur i hukommelsen eller til en midlertidig tabel for at oprette et tidsstabilt datasnapshot. Begge disse metoder er meget dyre. I tilfælde af lager i hukommelsen får vi både hukommelsesomkostningerne forårsaget af lagring af konstruerede objekter og tidsomkostningerne forbundet med redundante ORM-transformationer. Hvad angår det midlertidige bord, er dette en endnu dyrere fornøjelse, som kun giver mening i ikke-trivielle tilfælde.
Multiversion LMDB løser problemet med at opretholde en stabil datakilde på en meget elegant måde. Det er nok bare at åbne en transaktion og voila – indtil vi gennemfører den, er datasættet garanteret rettet. Logikken i dens opdateringshastighed er nu helt i hænderne på præsentationslaget, uden overhead af væsentlige ressourcer.
Markører
Markører giver en mekanisme til ordnet iteration over nøgle-værdi-par ved at krydse et B-træ. Uden dem ville det være umuligt effektivt at modellere tabellerne i databasen, som vi nu vender os til.
4.2. Bordmodellering
Nøglebestillingsegenskaben giver dig mulighed for at konstruere en abstraktion på øverste niveau, såsom en tabel oven på grundlæggende abstraktioner. Lad os overveje denne proces på eksemplet med skyklientens hovedtabell, hvor oplysninger om alle brugerens filer og mapper er cachelagret.
Tabelskema
Et af de almindelige scenarier, hvor strukturen af en tabel med et mappetræ bør skærpes, er at vælge alle elementer, der er placeret inde i en given mappe. En god dataorganisationsmodel for effektive forespørgsler af denne art er . For at implementere det oven på nøgleværdi-lageret, er det nødvendigt at sortere nøglerne til filer og mapper på en sådan måde, at de er grupperet baseret på tilhørsforhold til det overordnede bibliotek. Derudover, for at vise indholdet af mappen i den form, som en Windows-bruger kender (mapper først, derefter filer, begge sorteres alfabetisk), er det nødvendigt at inkludere de tilsvarende ekstra felter i nøglen.
Billedet nedenfor viser, hvordan repræsentationen af nøgler som et array af bytes, baseret på opgaven, kan se ud. Først placeres bytes med den overordnede mappe-id (rød), derefter med typen (grøn), og allerede i halen med navnet (blå). Ved at være sorteret efter standard LMDB-komparatoren i leksikografisk rækkefølge, er de sorteret i den nødvendige måde. Sekventiel gennemgang af nøgler med det samme røde præfiks giver os de værdier, der er knyttet til dem i den rækkefølge, de skal vises i brugergrænsefladen (til højre), uden at det kræver yderligere efterbehandling.
Serialisering af nøgler og værdier
Der er mange metoder til at serialisere objekter rundt om i verden. Da vi ikke havde andre krav end hastighed, valgte vi den hurtigst mulige for os selv - et hukommelsesdump optaget af en forekomst af C-sprogstrukturen. Så nøglen til et bibliotekselement kan modelleres efter følgende struktur NodeKey.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;At gemme NodeKey i opbevaringsbehov i objekt MDB_val placer markøren til dataene på adressen i begyndelsen af strukturen, og beregn deres størrelse med funktionen sizeof.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = sizeof(NodeKey),
.mv_data = (void *)key
};
}I det første kapitel om databaseudvælgelseskriterier nævnte jeg minimering af dynamiske tildelinger som en del af CRUD-operationer som en vigtig udvælgelsesfaktor. Funktionskode serialize viser, hvordan de i tilfælde af LMDB helt kan undgås, når nye poster indsættes i databasen. Det indkommende array af bytes fra serveren omdannes først til stakstrukturer, og derefter dumpes de trivielt ind i lageret. I og med at der heller ikke er nogen dynamiske tildelinger inde i LMDB, kan du få en fantastisk situation efter iOS-standarderne - brug kun stack-hukommelse til at arbejde med data hele vejen fra netværket til disken!
Bestilling af nøgler med en binær komparator
Nøgleordensrelationen er givet af en speciel funktion kaldet en komparator. Da motoren ikke ved noget om semantikken af de bytes, de indeholder, har standardkomparatoren intet andet valg end at arrangere nøglerne i leksikografisk rækkefølge ved at ty til deres byte-for-byte sammenligning. At bruge det til at arrangere strukturer er beslægtet med barbering med en udskæringsøkse. Men i simple tilfælde finder jeg denne metode acceptabel. Alternativet er beskrevet nedenfor, men her vil jeg notere et par river spredt undervejs.
Den første ting at huske på er hukommelsesrepræsentationen af primitive datatyper. Så på alle Apple-enheder gemmes heltalsvariabler i formatet . Dette betyder, at den mindst signifikante byte vil være til venstre, og du vil ikke være i stand til at sortere heltal ved at bruge deres byte-for-byte sammenligning. For eksempel vil forsøg på at gøre dette med et sæt tal fra 0 til 511 resultere i følgende resultat.
// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)For at løse dette problem skal heltalene lagres i nøglen i et format, der passer til byte-komparatoren. Funktioner fra familien vil hjælpe med at udføre den nødvendige transformation. hton* (i særdeleshed htons for dobbeltbyte-tal fra eksemplet).
Formatet til at repræsentere strenge i programmering er som bekendt en helhed . Hvis semantikken af strenge, såvel som den kodning, der bruges til at repræsentere dem i hukommelsen, antyder, at der kan være mere end én byte pr. tegn, er det bedre straks at opgive ideen om at bruge en standardkomparator.
Den anden ting at huske på er struct felt compiler. På grund af dem kan bytes med skraldværdier dannes i hukommelsen mellem felter, hvilket selvfølgelig bryder bytesorteringen. For at eliminere skrald skal du enten erklære felterne i en strengt defineret rækkefølge, holde justeringsreglerne i tankerne, eller bruge attributten i strukturdeklarationen packed.
Nøglebestilling af ekstern komparator
Nøglesammenligningslogikken kan vise sig at være for kompleks til en binær komparator. En af de mange grunde er tilstedeværelsen af tekniske felter inde i strukturerne. Jeg vil illustrere deres forekomst på eksemplet med en nøgle, som vi allerede kender til et bibliotekselement.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Trods al dens enkelthed, bruger den i langt de fleste tilfælde for meget hukommelse. Titelbufferen er 256 bytes, selvom fil- og mappenavne i gennemsnit sjældent overstiger 20-30 tegn.
En af standardteknikkerne til at optimere størrelsen af en post er at trimme den, så den passer til dens faktiske størrelse. Dens essens er, at indholdet af alle felter med variabel længde er lagret i en buffer i slutningen af strukturen, og deres længder gemmes i separate variabler. I overensstemmelse med denne tilgang er nøglen NodeKey omdannes på følgende måde.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Yderligere, under serialisering, ikke angivet som datastørrelsen sizeof hele strukturen, og størrelsen af alle felter er fast længde plus størrelsen af den faktisk brugte del af bufferen.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
.mv_data = (void *)key
};
}Som et resultat af refaktoreringen fik vi en betydelig besparelse i den plads, som tasterne optager. Dog på grund af det tekniske område nameLength, er den standard binære komparator ikke længere egnet til nøglesammenligning. Hvis vi ikke erstatter det med vores eget, så vil længden af navnet være en mere prioriteret faktor i sorteringen end selve navnet.
LMDB tillader hver database at have sin egen nøglesammenligningsfunktion. Dette gøres ved hjælp af funktionen mdb_set_compare strengt før åbning. Af indlysende årsager kan en database ikke ændres i hele dens levetid. Ved indgangen modtager komparatoren to nøgler i binært format, og ved udgangen returnerer den resultatet af sammenligningen: mindre end (-1), større end (1) eller lig med (0). Pseudokode til NodeKey ser sådan ud.
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å længe alle nøgler i databasen er af samme type, er det lovligt at ubetinget caste deres byte-repræsentation til typen af nøglens applikationsstruktur. Der er én nuance her, men den vil blive diskuteret lidt længere nede i underafsnittet "Læseoptegnelser".
Værdi serialisering
Med nøglerne til lagrede poster arbejder LMDB ekstremt intensivt. De sammenlignes med hinanden inden for rammerne af enhver applikationsoperation, og ydeevnen af hele løsningen afhænger af komparatorens hastighed. I en ideel verden burde den standard binære komparator være nok til at sammenligne nøgler, men hvis du virkelig skulle bruge dine egne, så skulle proceduren for at deserialisere nøgler i den være så hurtig som muligt.
Databasen er ikke specielt interesseret i værdi-delen af posten (værdi). Dets konvertering fra en byte-repræsentation til et objekt sker kun, når det allerede kræves af applikationskoden, for eksempel for at vise det på skærmen. Da dette sker relativt sjældent, er kravene til hastigheden af denne procedure ikke så kritiske, og i dens implementering er vi meget mere frie til at fokusere på bekvemmelighed. For eksempel til at serialisere metadata om filer, der endnu ikke er downloadet, bruger vi NSKeyedArchiver.
NSData *data = serialize(object);
MDB_val value = {
.mv_size = data.length,
.mv_data = (void *)data.bytes
};Men der er tidspunkter, hvor ydeevnen betyder noget. For eksempel, når vi gemmer metainformation om filstrukturen i brugerskyen, bruger vi det samme objekthukommelsesdump. Højdepunktet i opgaven med at generere deres serialiserede repræsentation er det faktum, at elementerne i en mappe er modelleret af et klassehierarki.
Til implementeringen på C-sproget er arvingernes specifikke felter taget ud i separate strukturer, og deres forbindelse med basisen er specificeret gennem et felt af fagforeningstypen. Det faktiske indhold af fagforeningen er angivet via den type tekniske attribut.
typedef struct NodeValue {
EntityId localId;
EntityType type;
union {
FileInfo file;
DirectoryInfo directory;
} info;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeValue;Tilføjelse og opdatering af poster
Den serialiserede nøgle og værdi kan tilføjes til butikken. Til dette bruges funktionen mdb_put.
// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);På konfigurationsstadiet kan depotet tillades eller forbydes at gemme flere poster med den samme nøgle. Hvis duplikering af nøgler er forbudt, kan du, når du indsætter en post, bestemme, om opdatering af en allerede eksisterende post er tilladt eller ej. Hvis flossning kun kan opstå som følge af en fejl i koden, så kan du forsikre dig mod det ved at angive flaget NOOVERWRITE.
Læsning af optegnelser
Funktionen til at læse poster i LMDB er mdb_get. Hvis nøgleværdi-parret er repræsenteret af tidligere dumpede strukturer, ser denne procedure sådan ud.
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 præsenterede liste viser, hvordan serialisering gennem et dump af strukturer giver dig mulighed for at slippe af med dynamiske tildelinger, ikke kun når du skriver, men når du læser data. Afledt af funktion mdb_get markøren ser nøjagtigt på den virtuelle hukommelsesadresse, hvor databasen gemmer byte-repræsentationen af objektet. Faktisk får vi en slags ORM, som næsten gratis giver en meget høj hastighed til at læse data. Med al skønheden i tilgangen er det nødvendigt at huske flere funktioner forbundet med det.
- For en skrivebeskyttet transaktion er en pegepind til en værdistruktur garanteret kun at forblive gyldig, indtil transaktionen lukkes. Som nævnt tidligere forbliver siderne i B-træet, som objektet ligger på, takket være copy-on-write-princippet, uændrede, så længe mindst én transaktion refererer til dem. Samtidig kan siderne genbruges til nye data, så snart den sidste transaktion tilknyttet dem er gennemført. Hvis det er nødvendigt for objekter at overleve den transaktion, der skabte dem, så skal de stadig kopieres.
- For en readwrite-transaktion vil markøren til den resulterende struktur-værdi kun være gyldig indtil den første ændringsprocedure (skrivning eller sletning af data).
- Selvom strukturen
NodeValueikke fuldgyldigt, men trimmet (se underafsnit "Bestilling af nøgler ved en ekstern komparator"), gennem markøren kan du nemt få adgang til dens felter. Det vigtigste er ikke at afvise det! - Du kan under ingen omstændigheder ændre strukturen gennem den modtagne markør. Alle ændringer må kun foretages gennem metoden
mdb_put. Men med al ønsket om at gøre dette, vil det ikke fungere, da hukommelsesområdet, hvor denne struktur er placeret, er kortlagt i skrivebeskyttet tilstand. - Ommap en fil til en process adresseområde for for eksempel at øge den maksimale lagerstørrelse ved hjælp af funktionen
mdb_env_set_map_sizeugyldiggør fuldstændigt alle transaktioner og relaterede enheder generelt og pointer til at læse objekter i særdeleshed.
Endelig er endnu en funktion så lumsk, at afsløringen af dens essens ikke passer ind i blot et punkt mere. I kapitlet om B-træet gav jeg et diagram over organiseringen af dets sider i hukommelsen. Det følger af det, at adressen på begyndelsen af bufferen med serialiserede data kan være absolut vilkårlig. På grund af dette, pointeren til dem, opnået i strukturen MDB_val og støbt til en pointer til en struktur er generelt ikke justeret. Samtidig kræver arkitekturen af nogle chips (i tilfælde af iOS er dette armv7), at adressen på alle data er et multiplum af størrelsen af et maskinord, eller med andre ord, systemets bithed (for armv7 er dette 32 bit). Med andre ord en operation som *(int *foo)0x800002 på dem sidestilles med flugt og fører til henrettelse med en dom EXC_ARM_DA_ALIGN. Der er to måder at undgå sådan en trist skæbne på.
Den første er at kopiere dataene til en kendt, justeret struktur på forhånd. For eksempel på en tilpasset komparator vil dette blive afspejlet 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åde er at give kompilatoren besked på forhånd om, at strukturer med en nøgle og værdi muligvis ikke justeres ved hjælp af en attribut aligned(1). På ARM kan den samme effekt være og bruge den pakket attribut. I betragtning af, at den også bidrager til optimering af den plads, strukturen optager, forekommer denne metode mig at foretrække, selvom at øge omkostningerne ved dataadgangsoperationer.
typedef struct __attribute__((packed)) NodeKey {
uint8_t parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Rækkeviddeforespørgsler
For at iterere over en gruppe poster giver LMDB en cursorabstraktion. Lad os se på, hvordan man arbejder med det ved at bruge eksemplet med en tabel med brugersky-metadata, som vi allerede kender.
Som en del af at vise en liste over filer i en mappe, skal du finde alle de nøgler, som dens underordnede filer og mapper er knyttet til. I de foregående underafsnit sorterede vi nøglerne NodeKey så de først er sorteret efter deres overordnede mappe-id. Teknisk set er opgaven med at få indholdet af en mappe reduceret til at placere markøren på den øvre grænse af en gruppe nøgler med et givet præfiks, efterfulgt af iteration til den nedre grænse.
Du kan finde den øvre grænse "på panden" ved sekventiel søgning. For at gøre dette placeres markøren i begyndelsen af hele listen over nøgler i databasen og derefter inkrementeres, indtil nøglen med den overordnede mappe-id vises under den. Denne tilgang har 2 åbenlyse ulemper:
- Den lineære kompleksitet af søgningen, selvom den, som du ved, i træer generelt og i et B-træ i særdeleshed, kan udføres i logaritmisk tid.
- Forgæves hæves alle sider, der går forud for den ønskede, fra filen til hovedhukommelsen, hvilket er ekstremt dyrt.
Heldigvis giver LMDB API en effektiv måde at placere markøren på i starten. . For eksempel kan vi i forhold til listen i figuren ovenfor lave en nøgle, hvori feltet parentId vil være lig med 2, og alle resten er fyldt med nuller. En sådan delvist udfyldt nøgle føres til funktionens indgang mdb_cursor_get angiver drift 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 grænse for gruppen af nøgler findes, så itererer vi over den, indtil vi enten mødes eller nøglen med en anden parentId, ellers vil nøglerne slet ikke løbe tør
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 groupHvad er rart, som en del af iteration ved hjælp af mdb_cursor_get, får vi ikke kun nøglen, men også værdien. Hvis det for at opfylde udvælgelsesbetingelserne er nødvendigt at kontrollere blandt andet felterne fra værdi-delen af posten, så er de ret tilgængelige for sig selv uden yderligere bevægelser.
4.3. Modellering af relationer mellem tabeller
Til dato har vi formået at overveje alle aspekter af design og arbejde med en enkelttabeldatabase. Vi kan sige, at en tabel er et sæt af sorterede poster, der består af nøgle-værdi-par af samme type. Hvis du viser en nøgle som et rektangel og dens tilhørende værdi som en boks, får du et visuelt diagram over databasen.
â € <
Men i det virkelige liv er det sjældent muligt at klare sig med så lidt blod. Ofte i en database kræves det for det første at have flere tabeller, og for det andet at udføre valg i dem i en rækkefølge, der er forskellig fra den primære nøgle. Dette sidste afsnit er viet til spørgsmålene om deres skabelse og sammenkobling.
Indeks tabeller
Cloud-appen har en "Galleri"-sektion. Det viser medieindhold fra hele skyen, sorteret efter dato. For den optimale implementering af et sådant valg, ved siden af hovedtabellen, skal du oprette en anden med en ny type nøgler. De vil indeholde et felt med den dato, filen blev oprettet, som vil fungere som det primære sorteringskriterium. Fordi de nye nøgler refererer til de samme data som nøglerne i den underliggende tabel, kaldes de indeksnøgler. De er fremhævet med orange på billedet nedenfor.
For at adskille nøglerne til forskellige tabeller fra hinanden i den samme database, er der tilføjet et yderligere teknisk felt tableId til dem alle. Ved at gøre det til den højeste prioritet for sortering, vil vi gruppere nøglerne først efter tabeller og allerede inde i tabellerne - i henhold til vores egne regler.
Indeksnøglen refererer til de samme data som den primære nøgle. Den ligefremme implementering af denne egenskab ved at tilknytte en kopi af værdidelen af den primære nøgle er suboptimal fra flere synspunkter på én gang:
- Fra et pladsoptaget synspunkt kan metadataene være ret rige.
- Fra et præstationssynspunkt, da du skal overskrive to nøgler, når du opdaterer nodens metadata.
- Fra et synspunkt om kodeunderstøttelse, hvis vi glemmer at opdatere dataene for en af nøglerne, vil vi trods alt få en subtil fejl med datainkonsekvens i lagringen.
Dernæst vil vi overveje, hvordan man fjerner disse mangler.
Organisering af relationer mellem tabeller
Mønsteret er velegnet til at forbinde en indekstabel med den primære "nøgle som værdi". Som navnet antyder, er værdidelen af indeksposten en kopi af den primære nøgleværdi. Denne tilgang eliminerer alle de ulemper, der er anført ovenfor, forbundet med lagring af en kopi af værdidelen af den primære post. Det eneste gebyr er, at for at få værdien med indeksnøglen, skal du lave 2 forespørgsler til databasen i stedet for én. Skematisk er det resulterende databaseskema som følger.
Et andet mønster til at organisere relationer mellem tabeller er "overflødig nøgle". Dens essens er at tilføje yderligere attributter til nøglen, som ikke er nødvendige for at sortere, men for at genskabe den tilknyttede nøgle. Der er dog reelle eksempler på dens brug i Mail.ru Cloud-applikationen for at undgå dyb dykning i sammenhæng med specifikke iOS-rammer, vil jeg give et fiktivt, men dog et mere forståeligt eksempel.
Cloud-mobilklienter har en side, der viser alle de filer og mapper, som brugeren har delt med andre mennesker. Da der er relativt få sådanne filer, og der er mange specifikke oplysninger om offentlighed forbundet med dem (hvem der gives adgang, med hvilke rettigheder osv.), vil det ikke være rationelt at belaste det med værdidelen af posten i hovedtabellen. Men hvis du vil vise sådanne filer offline, skal du stadig gemme dem et sted. En naturlig løsning er at lave et separat bord til det. I diagrammet nedenfor er dens nøgle foran med "P", og pladsholderen "propnavn" kan erstattes med den mere specifikke værdi "offentlig info".
Alle unikke metadata, for hvilke den nye tabel blev oprettet, flyttes til værdidelen af posten. Samtidig ønsker jeg ikke at duplikere data om filer og mapper, der allerede er gemt i hovedtabellen. I stedet tilføjes redundante data til "P"-nøglen i form af felterne "node ID" og "timestamp". Takket være dem kan du konstruere en indeksnøgle, hvormed du kan få den primære nøgle, hvormed du endelig kan få nodens metadata.
Konklusion
Vi vurderer resultaterne af LMDB-implementeringen positivt. Derefter faldt antallet af programfrysninger med 30%.
Resultaterne af det udførte arbejde har fundet et svar uden for iOS-teamet. I øjeblikket er en af de vigtigste "Filer"-sektioner i Android-applikationen også skiftet til at bruge LMDB, og andre dele er på vej. C-sproget, som nøgleværdi-lagringen er implementeret i, var en god hjælp til i første omgang at gøre applikationen bindende omkring den på tværs af platforme i C++-sproget. Til en problemfri forbindelse af det resulterende C++-bibliotek med platformskode i Objective-C og Kotlin blev der brugt en kodegenerator fra Dropbox, men det er en anden historie.
Kilde: www.habr.com