Hösten 2019 inträffade en efterlängtad händelse i Mail.ru Cloud iOS-teamet. Huvuddatabasen för beständig lagring av applikationstillstånd har blivit mycket exotisk för den mobila världen Lightning Memory-mappad databas (LMDB). Nedanför snittet erbjuder vi dig en detaljerad recension av den i fyra delar. Låt oss först prata om orsakerna till ett sådant icke-trivialt och svårt val. Sedan kommer vi att gå vidare med att överväga de tre pelarna i hjärtat av LMDB-arkitekturen: minneskartade filer, B+-träd, kopiera-på-skriv-metoden för implementering av transaktionalitet och multiversion. Slutligen, till efterrätt - den praktiska delen. I den kommer vi att titta på hur man designar och implementerar ett databasschema med flera tabeller, inklusive en index, ovanpå lågnivå nyckel-värde API.

Innehåll

1. Motivation för genomförande
2. LMDB positionering
3. Tre pelare i LMDB
   3.1. Val #1. Minnesmappade filer
   3.2. Val #2. B+-träd
   3.3. Val #3. Kopiera-på-skriva
4. Designa ett dataschema ovanpå nyckel-värde API
   4.1. Grundläggande abstraktioner
   4.2. Tabellmodellering
   4.3. Modellering av relationer mellan tabeller

1. Motivation för genomförande

Ett år 2015 gjorde vi oss besväret att mäta hur ofta gränssnittet i vår applikation släpar efter. Vi gjorde detta av en anledning. Vi har fått fler klagomål om att applikationen ibland slutar svara på användaråtgärder: knappar kan inte tryckas, listor rullar inte, etc. Om mekaniken i mätningarna berättade på AvitoTech, så här ger jag bara siffrornas ordning.

Mätresultaten blev en kalldusch för oss. Det visade sig att det finns många fler problem som orsakas av frysningar än någon annan. Om innan man insåg detta faktum var den viktigaste tekniska kvalitetsindikatorn kraschfri, så efter fokus ändrad på frysfritt.

Att ha byggt instrumentbräda med frysningar och efter att ha spenderat kvantitativ и kvalitet analys av deras skäl blev huvudfienden tydlig - tung affärslogik exekveras i programmets huvudtråd. Den naturliga reaktionen på denna skam var en brinnande önskan att trycka in den i arbetsströmmar. För att systematiskt lösa detta problem tog vi till en flertrådig arkitektur baserad på lättviktsskådespelare. Jag ägnade den åt dess anpassning för iOS-världen två trådar på kollektiva Twitter och artikel om Habré. Som en del av den aktuella berättelsen vill jag betona de aspekter av beslutet som påverkade valet av databasen.

​Aktormodellen för systemorganisation antar att multithreading blir dess andra väsen. Modellobjekt i den korsar gärna strömgränser. Och det gör de inte ibland och här och där, utan nästan konstant och överallt

Databasen är en av hörnstenskomponenterna i det presenterade diagrammet. Dess huvudsakliga uppgift är att implementera makromönstret Delad databas. Om det i företagsvärlden används för att organisera datasynkronisering mellan tjänster, då i fallet med aktörsarkitektur - data mellan trådar. Därför behövde vi en databas som inte skulle orsaka ens minimala svårigheter när vi arbetade med den i en flertrådig miljö. I synnerhet betyder detta att föremål som erhålls från den måste vara åtminstone gängsäkra och helst helt oföränderliga. Som du vet kan den senare användas samtidigt från flera trådar utan att tillgripa någon låsning, vilket har en gynnsam effekt på prestandan.

Den andra viktiga faktorn som påverkade valet av databas var vårt moln-API. Det var inspirerat av synkroniseringsmetoden som antogs av git. Liksom honom siktade vi på offline-första API, vilket ser mer än lämpligt ut för molnklienter. Det antogs att de bara skulle pumpa ut hela molnets tillstånd en gång, och sedan skulle synkronisering i den överväldigande majoriteten av fallen ske genom utrullning av ändringar. Tyvärr, denna möjlighet är fortfarande bara i den teoretiska zonen, och klienter har inte lärt sig hur man arbetar med patchar i praktiken. Det finns ett antal objektiva skäl till detta, som vi, för att inte fördröja införandet, lämnar bakom parentes. Vad som nu är av mycket mer intresse är de lärorika slutsatserna från lektionen om vad som händer när ett API säger "A" och dess konsument inte säger "B".

Så om du föreställer dig git, som, när du kör ett pull-kommando, istället för att applicera patchar på en lokal ögonblicksbild, jämför dess fullständiga tillstånd med det fullständiga servertillståndet, då kommer du att ha en ganska exakt uppfattning om hur synkronisering sker i molnet kunder. Det är lätt att gissa att för att implementera det måste du allokera två DOM-träd i minnet med metainformation om alla server- och lokala filer. Det visar sig att om en användare lagrar 500 tusen filer i molnet, är det nödvändigt att återskapa och förstöra två träd med 1 miljon noder för att synkronisera det. Men varje nod är ett aggregat som innehåller en graf över subobjekt. Mot denna bakgrund förväntades profileringsresultaten. Det visade sig att även utan att ta hänsyn till sammanslagningsalgoritmen kostar själva proceduren att skapa och därefter förstöra ett stort antal små objekt en ganska slant. Situationen förvärras av det faktum att den grundläggande synkroniseringsoperationen ingår i ett stort antal av användarskript. Som ett resultat fixar vi det andra viktiga kriteriet vid val av databas - förmågan att implementera CRUD-operationer utan dynamisk tilldelning av objekt.

Andra krav är mer traditionella och hela listan är som följer.

1. Trådsäkerhet.
2. Multiprocessing. Dikteras av önskan att använda samma databasinstans för att synkronisera tillstånd inte bara mellan trådar, utan också mellan huvudapplikationen och iOS-tillägg.
3. Möjligheten att representera lagrade enheter som icke-föränderliga objekt
4. Inga dynamiska tilldelningar inom CRUD-operationer.
5. Transaktionsstöd för basfastigheter SYRA: atomicitet, konsistens, isolering och tillförlitlighet.
6. Hastighet på de mest populära fallen.

Med denna uppsättning krav var och förblir SQLite ett bra val. Men som en del av studiet av alternativ kom jag över en bok "Komma igång med LevelDB". Under hennes ledning skrevs ett riktmärke som jämförde arbetshastigheten med olika databaser i riktiga molnscenarier. Resultatet överträffade våra vildaste förväntningar. I de mest populära fallen - att få en markör på en sorterad lista över alla filer och en sorterad lista över alla filer för en given katalog - visade sig LMDB vara 10 gånger snabbare än SQLite. Valet blev självklart.

2. LMDB Positionering

LMDB är ett mycket litet bibliotek (endast 10K rader) som implementerar det lägsta grundläggande lagret av databaser - lagring.

Diagrammet ovan visar att att jämföra LMDB med SQLite, som också implementerar högre nivåer, i allmänhet inte är mer korrekt än SQLite med Core Data. Det skulle vara mer rättvist att nämna samma lagringsmotorer som likvärdiga konkurrenter - BerkeleyDB, LevelDB, Sophia, RocksDB, etc. Det finns till och med utvecklingar där LMDB fungerar som en lagringsmotorkomponent för SQLite. Det första sådana experimentet var 2012 spenderat av LMDB Howard Chu. Resultat visade sig vara så spännande att hans initiativ togs upp av OSS-entusiaster och fann sin fortsättning i personen LumoSQL. I januari 2020 var författaren till detta projekt Den Shearer presenteras det på LinuxConfAu.

LMDB används främst som en motor för applikationsdatabaser. Biblioteket är skyldigt utvecklarna sitt utseende OpenLDAP, som var mycket missnöjda med BerkeleyDB som grund för sitt projekt. Med utgångspunkt från ett blygsamt bibliotek btree, Howard Chu kunde skapa ett av vår tids mest populära alternativ. Han dedikerade sin mycket coola rapport till den här historien, såväl som till den interna strukturen i LMDB. "The Lightning Memory-mapped Database". Ett bra exempel på att erövra en lagringsanläggning delades av Leonid Yuryev (aka yleo) från Positive Technologies i sin rapport vid Highload 2015 "LMDB-motorn är en speciell mästare". I den talar han om LMDB i samband med en liknande uppgift att implementera ReOpenLDAP, och LevelDB har redan varit föremål för jämförande kritik. Som ett resultat av implementeringen hade Positive Technologies till och med en aktivt utvecklande gaffel MDBX med mycket läckra funktioner, optimeringar och Bug fixar.

LMDB används ofta som en befintlig lagring. Till exempel webbläsaren Mozilla Firefox valde det för ett antal behov, och från och med version 9, Xcode föredraget dess SQLite för att lagra index.

Motorn har även gjort sina avtryck i världen av mobil utveckling. Spår av dess användning kan vara hitta i iOS-klienten för Telegram. LinkedIn gick ännu längre och valde LMDB som standardlagring för sitt hemodlade ramverk för datacachning Rocket Data, om vilket berättade i sin artikel 2016.

LMDB kämpar framgångsrikt för en plats i solen i den nisch som BerkeleyDB lämnade efter att den kom under Oracles kontroll. Biblioteket är älskat för sin snabbhet och tillförlitlighet, även jämfört med sina kamrater. Som ni vet finns det inga gratis luncher, och jag skulle vilja betona den avvägning som du kommer att behöva möta när du väljer mellan LMDB och SQLite. Diagrammet ovan visar tydligt hur ökad hastighet uppnås. För det första betalar vi inte för ytterligare lager av abstraktion ovanpå disklagring. Det är uppenbart att en bra arkitektur fortfarande inte klarar sig utan dem, och de kommer oundvikligen att visas i applikationskoden, men de kommer att vara mycket subtilare. De kommer inte att innehålla funktioner som inte krävs av en specifik applikation, till exempel stöd för frågor i SQL-språket. För det andra blir det möjligt att optimalt implementera mappning av applikationsoperationer på förfrågningar till disklagring. Om SQLite i mitt jobb baseras på genomsnittliga statistiska behov för en genomsnittlig applikation, då är du som applikationsutvecklare väl medveten om de huvudsakliga arbetsbelastningsscenarierna. För en mer produktiv lösning måste du betala en högre prislapp både för utvecklingen av den initiala lösningen och för dess efterföljande support.

3. Tre pelare i LMDB

Efter att ha tittat på LMDB från fågelperspektiv var det dags att gå djupare. De följande tre avsnitten kommer att ägnas åt en analys av de huvudpelare som lagringsarkitekturen vilar på:

1. Minnesmappade filer som en mekanism för att arbeta med disk och synkronisering av interna datastrukturer.
2. B+-träd som en organisation av strukturen för lagrad data.
3. Kopiera-på-skriv som ett tillvägagångssätt för att tillhandahålla ACID-transaktionsegenskaper och multiversion.

3.1. Val #1. Minnesmappade filer

Minneskartade filer är ett så viktigt arkitektoniskt element att de till och med visas i förvarets namn. Frågor om cachelagring och synkronisering av åtkomst till lagrad information är helt överlåtna på operativsystemet. LMDB innehåller inga cacher i sig själv. Detta är ett medvetet beslut av författaren, eftersom genom att läsa data direkt från mappade filer kan du skära många hörn i motorimplementeringen. Nedan är en långt ifrån komplett lista över några av dem.

1. Att upprätthålla konsistensen av data i lagringen när man arbetar med den från flera processer blir operativsystemets ansvar. I nästa avsnitt diskuteras denna mekanik i detalj och med bilder.
2. Frånvaron av cacher eliminerar helt LMDB från de overhead som är förknippade med dynamiska tilldelningar. Att läsa data i praktiken innebär att ställa in en pekare till rätt adress i det virtuella minnet och inget mer. Det låter som science fiction, men i lagringskällkoden är alla anrop till calloc koncentrerade i lagringskonfigurationsfunktionen.
3. Frånvaron av cachar betyder också frånvaron av lås som är associerade med synkronisering av deras åtkomst. Läsare, som det kan finnas ett godtyckligt antal läsare av samtidigt, stöter inte på en enda mutex på väg till datan. På grund av detta har läshastigheten idealisk linjär skalbarhet baserat på antalet processorer. I LMDB är endast modifieringsoperationer synkroniserade. Det kan bara finnas en författare åt gången.
4. Ett minimum av cachning och synkroniseringslogik eliminerar den extremt komplexa typen av fel som är förknippade med att arbeta i en flertrådig miljö. Det fanns två intressanta databasstudier vid Usenix OSDI 2014-konferensen: "Alla filsystem är inte skapade lika: om komplexiteten i att skapa kraschkonsistenta applikationer" и "Tortera databaser för skojs skull och vinst". Från dem kan du hämta information om både den oöverträffade tillförlitligheten hos LMDB och den nästan felfria implementeringen av ACID-transaktionsegenskaper, som är överlägsen den för SQLite.
5. Minimalismen hos LMDB gör att maskinrepresentationen av dess kod kan placeras helt i processorns L1-cache med de efterföljande hastighetsegenskaperna.

Tyvärr, i iOS, med minneskartade filer, är allt inte så molnfritt som vi skulle vilja. För att prata om de brister som är förknippade med dem mer medvetet är det nödvändigt att komma ihåg de allmänna principerna för att implementera denna mekanism i operativsystem.

Allmän information om minneskartade filer

Till varje applikation som körs associerar operativsystemet en enhet som kallas en process. Varje process tilldelas ett sammanhängande antal adresser där den placerar allt den behöver för att fungera. På de lägsta adresserna finns sektioner med kod och hårdkodade data och resurser. Därefter kommer ett växande block av dynamiskt adressutrymme, välkänt för oss under namnet heap. Den innehåller adresserna till enheter som visas under driften av programmet. Överst finns minnesområdet som används av programstacken. Antingen växer den eller drar ihop sig, med andra ord har dess storlek också en dynamisk natur. För att förhindra att stapeln och högen trycker på och stör varandra är de placerade i olika ändar av adressutrymmet. Det finns ett hål mellan de två dynamiska sektionerna upptill och nedtill. Operativsystemet använder adresser i denna mittsektion för att associera en mängd olika enheter med processen. I synnerhet kan den associera en viss kontinuerlig uppsättning adresser med en fil på disken. En sådan fil kallas minnesmappad

Adressutrymmet som allokeras till processen är enormt. Teoretiskt sett begränsas antalet adresser endast av storleken på pekaren, som bestäms av systemets bitkapacitet. Om fysiskt minne mappades till det 1-till-1, skulle den allra första processen sluka upp hela RAM-minnet, och det skulle inte vara tal om någon multitasking.

​Men av vår erfarenhet vet vi att moderna operativsystem kan köra så många processer som önskas samtidigt. Detta är möjligt på grund av det faktum att de bara allokerar mycket minne till processer på papper, men i verkligheten laddar de i det fysiska huvudminnet bara den del som efterfrågas här och nu. Därför kallas minnet som är associerat med en process virtuellt.

Operativsystemet organiserar virtuellt och fysiskt minne i sidor av en viss storlek. Så snart en viss sida av virtuellt minne efterfrågas, laddar operativsystemet in den i det fysiska minnet och matchar dem i en speciell tabell. Om det inte finns några lediga platser, kopieras en av de tidigare laddade sidorna till disken och den efterfrågade tar dess plats. Denna procedur, som vi återkommer till inom kort, kallas byte. Figuren nedan illustrerar processen som beskrivs. På den laddades sida A med adress 0 och placerades på huvudminnessidan med adress 4. Detta faktum återspeglades i korrespondenstabellen i cell nummer 0.​

Historien är exakt densamma med filer mappade till minnet. Logiskt sett antas de vara kontinuerligt och helt placerade i det virtuella adressutrymmet. Däremot anger de fysiskt minne sida för sida och endast på begäran. Ändring av sådana sidor synkroniseras med filen på disken. På detta sätt kan du utföra fil-I/O genom att helt enkelt arbeta med bytes i minnet - alla ändringar kommer automatiskt att överföras av operativsystemets kärna till källfilen.
â € <
Bilden nedan visar hur LMDB synkroniserar sitt tillstånd när man arbetar med databasen från olika processer. Genom att mappa det virtuella minnet för olika processer till samma fil, tvingar vi de facto operativsystemet att transitivt synkronisera vissa block av deras adressutrymmen med varandra, där LMDB ser ut.​
â € <

En viktig nyans är att LMDB, som standard, modifierar datafilen genom skrivsystemanropsmekanismen och visar själva filen i skrivskyddat läge. Detta tillvägagångssätt har två viktiga konsekvenser.

Den första konsekvensen är gemensam för alla operativsystem. Dess kärna är att lägga till skydd mot oavsiktlig skada på databasen genom felaktig kod. Som du vet är de körbara instruktionerna för en process fria att komma åt data från var som helst i dess adressutrymme. Samtidigt, som vi precis kom ihåg, innebär visning av en fil i läs-skrivläge att alla instruktioner också kan ändra den. Om hon gör detta av misstag och försöker, till exempel, att faktiskt skriva över ett array-element vid ett obefintligt index, kan hon av misstag ändra filen som är mappad till denna adress, vilket kommer att leda till korruption av databasen. Om filen visas i skrivskyddat läge kommer ett försök att ändra motsvarande adressutrymme att leda till en nödavslutning av programmet med en signal SIGSEGV, och filen förblir intakt.

Den andra konsekvensen är redan specifik för iOS. Varken författaren eller några andra källor nämner det uttryckligen, men utan det skulle LMDB inte vara lämpligt att köra på detta mobila operativsystem. Nästa avsnitt ägnas åt dess övervägande.

Detaljer om minneskartade filer i iOS

Det var en underbar rapport på WWDC 2018 "iOS Memory Deep Dive". Det säger oss att i iOS är alla sidor som finns i det fysiska minnet en av tre typer: smutsiga, komprimerade och rena.

Rent minne är en samling sidor som smärtfritt kan laddas ur från det fysiska minnet. Data de innehåller kan laddas om efter behov från dess ursprungliga källor. Skrivskyddade minneskartade filer faller i denna kategori. iOS är inte rädd för att ladda ner sidorna som är mappade till en fil från minnet när som helst, eftersom de garanterat kommer att synkroniseras med filen på disken.
â € <
Alla modifierade sidor hamnar i smutsigt minne, oavsett var de ursprungligen fanns. I synnerhet kommer minneskartade filer som modifierats genom att skriva till det virtuella minnet som är associerade med dem att klassificeras på detta sätt. Öppnande LMDB med flagga MDB_WRITEMAP, efter att ha gjort ändringar i den kan du verifiera detta personligen.​

Så snart en applikation börjar ta upp för mycket fysiskt minne utsätter iOS den för smutsig sidkomprimering. Det totala minnet som upptas av smutsiga och komprimerade sidor utgör programmets så kallade minnesavtryck. När den når ett visst tröskelvärde kommer OOM-mördarsystemets daemon efter processen och tvångsavbryter den. Detta är det speciella med iOS jämfört med stationära operativsystem. Däremot finns det inte i iOS att minska minnesfotavtrycket genom att byta sidor från fysiskt minne till disk. Orsakerna kan bara gissas till. Kanske är proceduren för att intensivt flytta sidor till disk och tillbaka för energikrävande för mobila enheter, eller så sparar iOS resursen att skriva om celler på SSD-enheter, eller så var designarna inte nöjda med systemets övergripande prestanda, där allt är ständigt bytt. Hur det än må vara så förblir faktum ett faktum.

Den goda nyheten, som redan nämnts tidigare, är att LMDB som standard inte använder mmap-mekanismen för att uppdatera filer. Detta innebär att de visade data klassificeras av iOS som rent minne och bidrar inte till minnesavtrycket. Du kan verifiera detta med ett Xcode-verktyg som heter VM Tracker. Skärmdumpen nedan visar tillståndet för det virtuella iOS-minnet för molnapplikationen under drift. I början initialiserades 2 LMDB-instanser i den. Den första fick visa sin fil på 1GiB virtuellt minne, den andra - 512MiB. Trots att båda lagringarna upptar en viss mängd internminne, bidrar ingen av dem med smutsig storlek.

Och nu är det dags för dåliga nyheter. Tack vare växlingsmekanismen i 64-bitars skrivbordsoperativsystem kan varje process uppta så mycket virtuellt adressutrymme som det lediga hårddiskutrymmet för dess potentiella växling tillåter. Att ersätta swap med komprimering i iOS minskar radikalt det teoretiska maximumet. Nu måste alla levande processer passa in i huvudminnet (läs RAM) och alla de som inte passar måste tvingas avsluta. Detta anges som i ovan nämnda Rapportera, och i officiell dokumentation. Som en konsekvens begränsar iOS kraftigt mängden tillgängligt minne för tilldelning via mmap. Här här Du kan titta på de empiriska gränserna för mängden minne som kan allokeras på olika enheter med hjälp av detta systemanrop. På de modernaste smartphonemodellerna har iOS blivit generös med 2 gigabyte, och på toppversioner av iPad - med 4. I praktiken måste man förstås fokusera på de lägsta stödda enhetsmodellerna, där allt är väldigt tråkigt. Ännu värre, genom att titta på applikationens minnestillstånd i VM Tracker kommer du att upptäcka att LMDB långt ifrån är den enda som påstår sig vara minnesmappad. Goda bitar äts upp av systemfördelare, resursfiler, bildramar och andra mindre rovdjur.

Baserat på resultaten av experiment i molnet kom vi fram till följande kompromissvärden för minnet som tilldelats av LMDB: 384 megabyte för 32-bitarsenheter och 768 för 64-bitarsenheter. När denna volym är slut börjar alla modifieringsåtgärder sluta med koden MDB_MAP_FULL. Vi observerar sådana fel i vår övervakning, men de är så små att de i detta skede kan försummas.

En icke-uppenbar orsak till överdriven minnesförbrukning av lagringen kan vara långlivade transaktioner. För att förstå hur dessa två fenomen hänger ihop, kommer vi att få hjälp genom att överväga de återstående två pelarna i LMDB.

3.2. Val #2. B+-träd

För att emulera tabeller ovanpå en nyckel-värdelagring måste följande operationer finnas i dess API:

1. Infoga ett nytt element.
2. Sök efter ett element med en given nyckel.
3. Ta bort ett element.
4. Iterera över intervall av nycklar i den ordning de är sorterade.

Den enklaste datastrukturen som enkelt kan implementera alla fyra operationerna är ett binärt sökträd. Var och en av dess noder representerar en nyckel som delar upp hela delmängden av underordnade nycklar i två underträd. Den vänstra innehåller de som är mindre än föräldern, och den högra innehåller de som är större. Att erhålla en beställd uppsättning nycklar uppnås genom en av de klassiska trädövergångarna

Binära träd har två grundläggande brister som hindrar dem från att vara effektiva som en diskbaserad datastruktur. För det första är graden av deras balans oförutsägbar. Det finns en avsevärd risk att få tag på träd där höjderna på olika grenar kan skilja sig mycket åt, vilket avsevärt försämrar den algoritmiska komplexiteten i sökningen jämfört med vad som förväntas. För det andra berövar överflöden av tvärlänkar mellan noder binära träd lokalitet i minnet.Nära noder (när det gäller kopplingar mellan dem) kan placeras på helt olika sidor i virtuellt minne. Som en konsekvens kan även en enkel genomgång av flera närliggande noder i ett träd kräva att man besöker ett jämförbart antal sidor. Detta är ett problem även när vi talar om effektiviteten hos binära träd som en datastruktur i minnet, eftersom att ständigt rotera sidor i processorcachen inte är ett billigt nöje. När det kommer till att ofta hämta sidor associerade med noder från disk blir situationen helt beklaglig.

B-träd, som är en utveckling av binära träd, löser problemen som identifierats i föregående stycke. För det första är de självbalanserande. För det andra delar var och en av deras noder uppsättningen av barnnycklar inte i 2, utan i M-ordnade delmängder, och antalet M kan vara ganska stort, i storleksordningen flera hundra eller till och med tusentals.

Därigenom:

1. Varje nod innehåller ett stort antal redan beställda nycklar och träden är mycket korta.
2. Trädet får egenskapen lokalisering av plats i minnet, eftersom nycklar som är nära i värde naturligt är placerade bredvid varandra på samma eller närliggande noder.
3. Antalet transitnoder när du går ner i ett träd under en sökoperation minskas.
4. Antalet målnoder som läses under intervallförfrågningar reduceras, eftersom var och en av dem redan innehåller ett stort antal ordnade nycklar.

LMDB använder en variant av B-trädet som kallas ett B+-träd för att lagra data. Diagrammet ovan visar de tre typerna av noder som finns i den:

1. Överst är roten. Det materialiserar inget annat än konceptet med en databas inuti ett lager. Inom en LMDB-instans kan du skapa flera databaser som delar ett mappat virtuellt adressutrymme. Var och en av dem börjar från sin egen rot.
2. På den lägsta nivån finns löven. De och bara de innehåller nyckel-värdeparen lagrade i databasen. Detta är förresten B+-trädens egenhet. Om ett vanligt B-träd lagrar värdedelar i noder på alla nivåer, är B+-variationen endast på den lägsta. Efter att ha fixat detta faktum kommer vi vidare att kalla subtypen av trädet som används i LMDB helt enkelt ett B-träd.
3. Mellan roten och bladen finns 0 eller fler tekniska nivåer med navigeringsnoder (grennoder). Deras uppgift är att dela upp den sorterade uppsättningen nycklar mellan bladen.

Fysiskt sett är noder minnesblock med en förutbestämd längd. Deras storlek är en multipel av storleken på minnessidor i operativsystemet, vilket vi diskuterade ovan. Nodstrukturen visas nedan. Rubriken innehåller metainformation, varav den mest uppenbara till exempel är kontrollsumman. Därefter kommer information om förskjutningarna i vilka cellerna med data finns. Data kan vara antingen nycklar, om vi pratar om navigeringsnoder, eller hela nyckel-värdepar när det gäller löv.​ Du kan läsa mer om strukturen på sidor i arbetet "Utvärdering av högpresterande nyckel-värdebutiker".

Efter att ha behandlat det interna innehållet i sidnoder, kommer vi ytterligare att representera LMDB B-trädet på ett förenklat sätt i följande form.

Sidor med noder finns sekventiellt på disken. Högre numrerade sidor finns i slutet av filen. Den så kallade metasidan innehåller information om de förskjutningar med vilka rötterna till alla träd kan hittas. När du öppnar en fil skannar LMDB filen sida för sida från början till början för att söka efter en giltig metasida och genom den hittar befintliga databaser.

Nu, med en uppfattning om den logiska och fysiska strukturen för dataorganisation, kan vi gå vidare och överväga den tredje pelaren i LMDB. Det är med dess hjälp som alla lagringsmodifieringar sker transaktionellt och isolerat från varandra, vilket ger databasen som helhet egenskapen multiversion.

3.3. Val #3. Kopiera-på-skriva

Vissa B-trädoperationer innebär att man gör en serie ändringar av dess noder. Ett exempel är att lägga till en ny nyckel till en nod som redan har nått sin maximala kapacitet. I det här fallet är det nödvändigt för det första att dela noden i två, och för det andra att lägga till en länk till den nya spirande barnnoden i dess förälder. Denna procedur är potentiellt mycket farlig. Om av någon anledning (krasch, strömavbrott, etc.) bara en del av ändringarna från serien inträffar, kommer trädet att förbli i ett inkonsekvent tillstånd.

En traditionell lösning för att göra en databas feltolerant är att lägga till ytterligare en datastruktur på disken bredvid B-trädet - en transaktionslogg, även känd som en WAL (Write-ahead Log). Det är en fil i slutet av vilken den avsedda operationen skrivs strikt innan själva B-trädet ändras. Således, om datakorruption upptäcks under självdiagnos, konsulterar databasen loggen för att göra sig i ordning.

LMDB har valt en annan metod som en feltoleransmekanism, som kallas copy-on-write. Dess kärna är att istället för att uppdatera data på en befintlig sida, kopierar den först den helt och hållet och gör alla ändringar i kopian.

Därefter, för att den uppdaterade datan ska vara tillgänglig, är det nödvändigt att ändra länken till den nod som har blivit aktuell i sin modernod. Eftersom den också behöver modifieras för detta, kopieras den också i förväg. Processen fortsätter rekursivt ända till roten. Det sista att ändra är data på metasidan.​

Om processen plötsligt kraschar under uppdateringsproceduren, kommer antingen inte en ny metasida att skapas, eller så kommer den inte att skrivas till disken helt, och dess kontrollsumma blir felaktig. I något av dessa två fall kommer nya sidor att vara oåtkomliga, men gamla kommer inte att påverkas. Detta eliminerar behovet för LMDB att skriva framåt-logg för att upprätthålla datakonsistens. De facto tar strukturen för datalagring på skivan som beskrivs ovan samtidigt sin funktion. Frånvaron av en explicit transaktionslogg är en av funktionerna i LMDB som ger hög dataläshastighet

Den resulterande designen, kallad append-only B-tree, ger naturligtvis transaktionsisolering och multiversion. I LMDB är varje öppen transaktion associerad med den aktuella trädroten. Tills transaktionen är slutförd kommer sidorna i trädet som är kopplade till den aldrig att ändras eller återanvändas för nya versioner av data. Du kan alltså arbeta så länge du vill med exakt den uppsättning data som var relevant vid den tidpunkten transaktionen öppnades, även om lagringen fortsätter att vara aktivt uppdaterad vid denna tidpunkt. Detta är kärnan i multiversion, vilket gör LMDB till en idealisk datakälla för vår älskade UICollectionView. Efter att ha öppnat en transaktion, finns det inget behov av att öka applikationens minnesfotavtryck genom att hastigt pumpa ut aktuell data till någon struktur i minnet, av rädsla för att bli kvar med ingenting. Denna funktion skiljer LMDB från samma SQLite, som inte kan skryta med sådan total isolering. Efter att ha öppnat två transaktioner i den senare och raderat en viss post inom en av dem, kommer det inte längre att vara möjligt att få samma post inom den andra återstående.

Baksidan av myntet är den potentiellt betydligt högre förbrukningen av virtuellt minne. Bilden visar hur databasstrukturen kommer att se ut om den modifieras samtidigt med 3 öppna lästransaktioner som tittar på olika versioner av databasen. Eftersom LMDB inte kan återanvända noder som kan nås från rötter associerade med aktuella transaktioner, har butiken inget annat val än att allokera ytterligare en fjärde rot i minnet och återigen klona de modifierade sidorna under den.

Här skulle det vara användbart att återkalla avsnittet om minneskartade filer. Det verkar som att den extra konsumtionen av virtuellt minne inte borde oroa oss mycket, eftersom det inte bidrar till applikationens minnesavtryck. Men samtidigt noterades det att iOS är väldigt snål med att allokera det, och vi kan inte, som på en server eller skrivbord, tillhandahålla en LMDB-region på 1 terabyte och inte tänka på den här funktionen alls. Om möjligt bör du försöka göra transaktionernas livslängd så kort som möjligt.

4. Designa ett dataschema ovanpå nyckel-värde API

Låt oss börja vår API-analys med att titta på de grundläggande abstraktionerna som tillhandahålls av LMDB: miljö och databaser, nycklar och värden, transaktioner och markörer.

En notering om kodlistor

Alla funktioner i det offentliga LMDB API returnerar resultatet av sitt arbete i form av en felkod, men i alla efterföljande listor utelämnas dess verifiering för korthetens skull.​ I praktiken använde vi till och med vårt eget för att interagera med arkivet gaffel C++ omslag lmdbxx, där fel materialiseras som C++-undantag.

Som det snabbaste sättet att ansluta LMDB till ett projekt för iOS eller macOS, föreslår jag min CocoaPod POSLMDB.

4.1. Grundläggande abstraktioner

Miljö

Struktur MDB_env är arkivet för LMDB:s interna tillstånd. Prefixerad funktionsfamilj mdb_env låter dig konfigurera några av dess egenskaper. I det enklaste fallet ser motorinitieringen ut så här.

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 ändrade vi standardvärdena för endast två parametrar.

Den första är storleken på det virtuella adressutrymmet som lagringsfilen är mappad till. Tyvärr, även på samma enhet, kan det specifika värdet variera avsevärt från körning till körning. För att ta hänsyn till denna funktion i iOS väljs den maximala lagringsvolymen dynamiskt. Utgående från ett visst värde halveras det sekventiellt fram till funktionen mdb_env_open kommer inte att returnera ett annat resultat än ENOMEM. I teorin finns det också det motsatta sättet - tilldela först ett minimum av minne till motorn och sedan, när fel tas emot, MDB_MAP_FULL, öka den. Den är dock mycket mer taggig. Anledningen är att proceduren för att omallokera minne (ommappa) med funktionen mdb_env_set_map_size ogiltigförklarar alla enheter (markörer, transaktioner, nycklar och värden) som tidigare tagits emot från motorn. Att ta hänsyn till denna vändning i koden kommer att leda till dess betydande komplikation. Om det virtuella minnet däremot är väldigt viktigt för dig, så kan detta vara en anledning att titta närmare på gaffeln som har gått långt fram MDBX, där bland de annonserade funktionerna finns "automatisk on-the-fly databasstorleksjustering".

Den andra parametern, vars standardvärde inte passade oss, reglerar mekaniken för att säkerställa gängsäkerhet. Tyvärr har åtminstone iOS 10 problem med stöd för lokal trådlagring. Av denna anledning, i exemplet ovan, öppnas förvaret med flaggan MDB_NOTLS. Utöver detta var det också nödvändigt gaffel C++ omslag lmdbxxatt skära ut variabler med detta attribut och i det.

Databas

Databasen är en separat B-tree-instans, som vi diskuterade ovan. Dess öppning sker i en transaktion, vilket kan verka lite konstigt till en början.

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);

Faktum är att en transaktion i LMDB är en lagringsenhet, inte en specifik databasenhet. Detta koncept låter dig utföra atomoperationer på enheter som finns i olika databaser. I teorin öppnar detta för möjligheten att modellera tabeller i form av olika databaser, men vid ett tillfälle tog jag en annan väg, beskriven i detalj nedan.

Nycklar och värderingar

Struktur MDB_val modellerar begreppet både nyckel och värde. Förvaret har ingen aning om deras semantik. För henne är något annat bara en uppsättning byte av en given storlek. Den maximala nyckelstorleken är 512 byte.

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

Med hjälp av en komparator sorterar butiken nycklarna i stigande ordning. Om du inte ersätter den med din egen, kommer standarden att användas, som sorterar dem byte-för-byte i lexikografisk ordning.

Transaktioner

Transaktionsstrukturen beskrivs i detalj i föregående kapitel, så här kommer jag kort att upprepa deras huvudsakliga egenskaper:

1. Stöder alla grundläggande egenskaper SYRA: atomicitet, konsistens, isolering och tillförlitlighet. Jag kan inte låta bli att notera att det finns en bugg när det gäller hållbarhet på macOS och iOS som fixades i MDBX. Du kan läsa mer i deras README.
2. Tillvägagångssättet för multithreading beskrivs av schemat "enskild skribent / flera läsare". Författare blockerar varandra, men blockerar inte läsare. Läsare blockerar inte författare eller varandra.
3. Stöd för kapslade transaktioner.
4. Stöd för multiversion.

Multiversion i LMDB är så bra att jag vill visa det i aktion. Från koden nedan kan du se att varje transaktion fungerar med exakt den version av databasen som var aktuell när den öppnades, helt isolerad från alla efterföljande ändringar. Att initiera lagringen och lägga till en testpost till den representerar inget intressant, så dessa ritualer lämnas under spoilern.

Lägger till en testpost

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);

Jag rekommenderar att du provar samma knep med SQLite och ser vad som händer.

Multiversion ger mycket trevliga förmåner till livet för en iOS-utvecklare. Med den här egenskapen kan du enkelt och naturligt justera uppdateringshastigheten för datakällan för skärmformulär, baserat på överväganden om användarupplevelse. Låt oss till exempel ta en funktion i Mail.ru Cloud-applikationen, som att automatiskt ladda innehåll från systemets mediagalleri. Med en bra anslutning kan klienten lägga till flera bilder per sekund till servern. Om du uppdaterar efter varje nedladdning UICollectionView med mediainnehåll i användarens moln kan du glömma bort 60 fps och smidig rullning under denna process. För att förhindra frekventa skärmuppdateringar måste du på något sätt begränsa hastigheten med vilken data ändras i det underliggande UICollectionViewDataSource.

Om databasen inte stöder multiversion och tillåter dig att bara arbeta med det aktuella tillståndet, måste du kopiera den antingen till någon datastruktur i minnet eller till en temporär tabell för att skapa en tidsstabil ögonblicksbild av data. Någon av dessa metoder är mycket dyr. När det gäller lagring i minnet får vi kostnader både i minnet, orsakade av lagring av konstruerade objekt, och i tid, förknippade med redundanta ORM-transformationer. När det gäller det tillfälliga bordet är detta ett ännu dyrare nöje, som bara är vettigt i icke-triviala fall.

LMDB:s multiversionslösning löser problemet med att upprätthålla en stabil datakälla på ett mycket elegant sätt. Det räcker att bara öppna en transaktion och voila - tills vi slutför den är datamängden garanterat fixad. Logiken för dess uppdateringshastighet ligger nu helt i händerna på presentationslagret, utan några betydande resurser.

Markörer

Markörer tillhandahåller en mekanism för ordnad iteration över nyckel-värde-par genom B-trädet. Utan dem skulle det vara omöjligt att effektivt modellera tabellerna i databasen, som vi nu vänder oss till.

4.2. Tabellmodellering

Egenskapen för nyckelordning låter dig konstruera en abstraktion på hög nivå, såsom en tabell ovanpå grundläggande abstraktioner. Låt oss överväga denna process med exemplet på huvudtabellen för en molnklient, som cachar information om alla användarens filer och mappar.

Tabellschema

Ett av de vanligaste scenarierna som en tabellstruktur med ett mappträd ska skräddarsys för är valet av alla element som finns inom en given katalog En bra dataorganisationsmodell för effektiva frågor av detta slag är Angränsningslista. För att implementera det ovanpå nyckel-värdelagringen är det nödvändigt att sortera nycklarna till filer och mappar på ett sådant sätt att de grupperas baserat på deras medlemskap i den överordnade katalogen. Dessutom, för att visa innehållet i katalogen i den form som är bekant för en Windows-användare (först mappar, sedan filer, båda sorterade alfabetiskt), är det nödvändigt att inkludera motsvarande ytterligare fält i nyckeln.

​Bilden nedan visar hur, baserat på den aktuella uppgiften, en representation av nycklar i form av en byte-array kan se ut. Byten med identifieraren för den överordnade katalogen (röd) placeras först, sedan med typen (grön) och i svansen med namnet (blå). Eftersom de är sorterade efter standard LMDB-jämföraren i lexikografisk ordning, ordnas de i erforderligt sätt. Att sekventiellt korsa nycklar med samma röda prefix ger oss deras tillhörande värden i den ordning de ska visas i användargränssnittet (till höger), utan att det krävs någon ytterligare efterbearbetning.

Serialisera nycklar och värden

Många metoder för att serialisera objekt har uppfunnits i världen. Eftersom vi inte hade några andra krav än hastighet, valde vi det snabbaste möjliga för oss själva - en dump av minnet som upptas av en instans av språkstrukturen C. Således kan nyckeln till ett katalogelement modelleras med följande struktur NodeKey.

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

Att spara NodeKey i förvaring som behövs i objekt MDB_val placera datapekaren till adressen till början av strukturen och beräkna deras storlek med funktionen sizeof.

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

I det första kapitlet om databasurvalskriterier nämnde jag att minimera dynamiska tilldelningar inom CRUD-operationer som en viktig urvalsfaktor. Funktionskod serialize visar hur de i fallet med LMDB helt kan undvikas när nya poster infogas i databasen. Den inkommande byte-arrayen från servern omvandlas först till stackstrukturer och sedan dumpas de trivialt i lagringen. Med tanke på att det inte heller finns några dynamiska tilldelningar inuti LMDB kan du få en fantastisk situation med iOS-standarder - använd endast stackminne för att arbeta med data längs hela vägen från nätverket till disken!

Beställa nycklar med binär komparator

Nyckelordningsrelationen specificeras av en speciell funktion som kallas en komparator. Eftersom motorn inte vet någonting om semantiken för de bytes de innehåller, har standardkomparatorn inget annat val än att ordna nycklarna i lexikografisk ordning, med hjälp av en byte-för-byte-jämförelse. Att använda det för att organisera strukturer är som att raka sig med en hugg yxa. Men i enkla fall finner jag denna metod acceptabel. Alternativet beskrivs nedan, men här kommer jag att notera ett par krattor utspridda längs denna väg.

Det första att komma ihåg är minnesrepresentationen av primitiva datatyper. Således, på alla Apple-enheter, lagras heltalsvariabler i formatet Lilla Endian. Detta innebär att den minst signifikanta byten kommer att vara till vänster, och det kommer inte att vara möjligt att sortera heltal med hjälp av en byte-för-byte-jämförelse. Om du till exempel försöker göra detta med en uppsättning siffror från 0 till 511 får du följande resultat.

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

För att lösa detta problem måste heltalen lagras i nyckeln i ett format som är lämpligt för byte-byte-jämföraren. Funktioner från familjen hjälper dig att utföra den nödvändiga omvandlingen hton* (särskilt htons för dubbelbytenummer från exemplet).

Formatet för att representera strängar i programmering är som bekant en helhet historia. Om semantiken för strängar, såväl som kodningen som används för att representera dem i minnet, antyder att det kan finnas mer än en byte per tecken, är det bättre att omedelbart överge idén om att använda en standardkomparator.

Den andra saken att tänka på är anpassningsprinciper strukturfältkompilator. På grund av dem kan bytes med skräpvärden bildas i minnet mellan fält, vilket naturligtvis bryter byte-byte-sortering. För att eliminera skräp måste du antingen deklarera fält i en strikt definierad ordning, med justeringsregler i åtanke, eller använda attributet i strukturdeklarationen packed.

Beställning av nycklar med extern komparator

Nyckeljämförelselogiken kan vara för komplex för en binär komparator. En av många anledningar är förekomsten av tekniska områden inom strukturer. Jag kommer att illustrera deras förekomst med hjälp av exemplet på en nyckel för ett katalogelement som redan är bekant för oss.

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

Trots sin enkelhet förbrukar den i de allra flesta fall för mycket minne. Bufferten för namnet tar upp 256 byte, även om fil- och mappnamn i genomsnitt sällan överstiger 20-30 tecken.

En av standardteknikerna för att optimera storleken på en post är att "trimma" den till den faktiska storleken. Dess kärna är att innehållet i alla fält med variabel längd lagras i en buffert i slutet av strukturen, och deras längder lagras i separata variabler.​ Enligt detta tillvägagångssätt är nyckeln NodeKey omvandlas enligt följande.

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

Vid serialisering anges inte datastorleken sizeof hela strukturen, och storleken på alla fält är en fast längd plus storleken på den faktiskt använda delen av bufferten.

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

Som ett resultat av omstruktureringen fick vi betydande besparingar i utrymmet som upptas av nycklar. Dock på grund av det tekniska området nameLength, är den förinställda binära komparatorn inte längre lämplig för nyckeljämförelse. Om vi ​​inte ersätter det med vårt eget kommer namnets längd att vara en högre prioriterad faktor vid sortering än själva namnet.

LMDB tillåter varje databas att ha sin egen nyckeljämförelsefunktion. Detta görs med hjälp av funktionen mdb_set_compare strikt före öppning. Av förklarliga skäl kan den inte ändras under hela databasens livslängd. Komparatorn tar emot två nycklar i binärt format som indata, och vid utgången returnerar den jämförelseresultatet: mindre än (-1), större än (1) eller lika med (0). Pseudokod för NodeKey ser ut så.

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 som alla nycklar i databasen är av samma typ är det lagligt att villkorslöst casta deras byte-representation till typen av applikationsnyckelstruktur. Det finns en nyans här, men den kommer att diskuteras nedan i underavsnittet "Reading Records".

Serialisera värden

LMDB arbetar extremt intensivt med nycklarna till lagrade poster. Deras jämförelse med varandra sker inom ramen för varje tillämpad operation, och prestandan för hela lösningen beror på komparatorns hastighet. I en idealisk värld borde den förinställda binära komparatorn räcka för att jämföra nycklar, men om du var tvungen att använda dina egna, borde proceduren för att deserialisera nycklar i den vara så snabb som möjligt.

Databasen är inte särskilt intresserad av värdedelen av posten (värde). Dess konvertering från en byte-representation till ett objekt sker endast när det redan krävs av applikationskoden, till exempel för att visa den på skärmen. Eftersom detta sker relativt sällan är hastighetskraven för denna procedur inte så kritiska, och i dess implementering är vi mycket mer fria att fokusera på bekvämlighet. För att till exempel serialisera metadata om filer som ännu inte har laddats ner använder vi NSKeyedArchiver.

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

Men det finns tillfällen då prestanda fortfarande spelar roll. När vi till exempel sparar metainformation om filstrukturen för ett användarmoln använder vi samma minnesdump av objekt. Höjdpunkten i uppgiften att skapa en serialiserad representation av dem är det faktum att elementen i en katalog är modellerade av en hierarki av klasser.

För att implementera det på C-språket placeras arvingarnas specifika fält i separata strukturer, och deras koppling till basen specificeras genom ett fält av typunion. Det faktiska innehållet i förbundet anges via den tekniska attributtypen.

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

Lägga till och uppdatera poster

Den serialiserade nyckeln och värdet kan läggas till i butiken. För att göra detta, använd funktionen mdb_put.

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

I konfigurationsstadiet kan lagringen tillåtas eller förbjudas från att lagra flera poster med samma nyckel. Om duplicering av nycklar är förbjuden, då när du infogar en post, kan du avgöra om uppdatering av en befintlig post är tillåten eller inte. Om fransning endast kan uppstå som ett resultat av ett fel i koden, kan du skydda dig från det genom att ange flaggan NOOVERWRITE.

Läser inlägg

För att läsa poster i LMDB, använd funktionen mdb_get. Om nyckel-värdeparet representeras av tidigare dumpade strukturer, ser denna procedur ut så här.

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 presenterade listan visar hur serialisering genom strukturdump gör att du kan bli av med dynamiska tilldelningar inte bara när du skriver, utan när du läser data. Härledd från funktion mdb_get pekaren tittar exakt på den virtuella minnesadressen där databasen lagrar byte-representationen av objektet. Faktum är att vi får en sorts ORM som ger väldigt hög dataläshastighet nästan gratis. Trots all skönhet i tillvägagångssättet är det nödvändigt att komma ihåg flera funktioner som är förknippade med det.

1. För en skrivskyddad transaktion är pekaren till värdestrukturen garanterad att vara giltig endast tills transaktionen avslutas. Som nämnts tidigare förblir B-trädsidorna på vilka ett objekt finns, tack vare kopiera-på-skriv-principen, oförändrade så länge som de refereras av minst en transaktion. Samtidigt kan sidorna återanvändas för ny data så snart den sista transaktionen som är kopplad till dem slutförs. Om det är nödvändigt för objekt att överleva transaktionen som genererade dem, måste de fortfarande kopieras.
2. För en lässkrivningstransaktion kommer pekaren till den resulterande värdestrukturen att vara giltig endast tills den första modifieringsproceduren (skriver eller raderar data).
3. Även om strukturen NodeValue inte fullfjädrad, men trimmad (se underavsnittet "Beställa nycklar med en extern komparator"), kan du säkert komma åt dess fält genom pekaren. Det viktigaste är att inte förakta det!
4. Under inga omständigheter får strukturen modifieras genom den mottagna pekaren. Alla ändringar får endast göras genom metoden mdb_put. Men oavsett hur hårt du vill göra detta kommer det inte att vara möjligt, eftersom minnesområdet där denna struktur finns är mappat i skrivskyddat läge.
5. Mappa om en fil till processadressutrymmet i syfte att till exempel öka den maximala lagringsstorleken med funktionen mdb_env_set_map_size ogiltigförklarar helt alla transaktioner och relaterade enheter i allmänhet och pekare till vissa objekt i synnerhet.

Slutligen, en annan funktion är så lömsk att avslöja dess väsen inte passar in i bara ett annat stycke. I kapitlet om B-trädet gav jag ett diagram över hur dess sidor är ordnade i minnet. Det följer av detta att adressen till början av bufferten med serialiserade data kan vara absolut godtycklig. På grund av detta fick pekaren till dem i strukturen MDB_val och reducerat till en pekare till en struktur, visar det sig vara oinriktat i det allmänna fallet. Samtidigt kräver arkitekturen för vissa chip (i fallet med iOS är detta armv7) att adressen till alla data är en multipel av storleken på maskinordet eller, med andra ord, systemets bitstorlek ( för armv7 är det 32 ​​bitar). Med andra ord en operation som *(int *foo)0x800002 på dem motsvarar rymning och leder till avrättning med en dom EXC_ARM_DA_ALIGN. Det finns två sätt att undvika ett sådant sorgligt öde.

Den första handlar om preliminär kopiering av data till en uppenbart anpassad struktur. Till exempel, på en anpassad komparator kommer detta att återspeglas enligt följande.

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 // ...
}

Ett alternativt sätt är att meddela kompilatorn i förväg att nyckel-värdestrukturer kanske inte är attributjusterade aligned(1). På ARM kan du ha samma effekt uppnå och använder det packade attributet. Med tanke på att det också hjälper till att optimera utrymmet som upptas av strukturen, förefaller denna metod att föredra, även om приводит till en ökning av kostnaderna för dataåtkomstverksamhet.

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

Områdesfrågor

För att iterera över en grupp poster tillhandahåller LMDB en markörabstraktion. Låt oss titta på hur man arbetar med det med hjälp av exemplet på en tabell med användarmolnmetadata som vi redan känner till.

Som en del av att visa en lista med filer i en katalog är det nödvändigt att hitta alla nycklar som dess underordnade filer och mappar är associerade med. I de föregående underavsnitten sorterade vi nycklarna NodeKey så att de i första hand ordnas efter den överordnade katalogens ID. Tekniskt sett handlar uppgiften om att hämta innehållet i en mapp alltså till att placera markören på den övre gränsen för gruppen av nycklar med ett givet prefix och sedan iterera till den nedre gränsen.

Den övre gränsen kan hittas direkt genom sekventiell sökning. För att göra detta placeras markören i början av hela listan med nycklar i databasen och ökas ytterligare tills en nyckel med identifieraren för den överordnade katalogen visas under den. Detta tillvägagångssätt har två uppenbara nackdelar:

1. Linjär sökningskomplexitet, även om den, som bekant, i träd i allmänhet och i ett B-träd i synnerhet kan utföras i logaritmisk tid.
2. Förgäves lyfts alla sidor som föregår den sökta från filen till huvudminnet, vilket är extremt dyrt.

Lyckligtvis tillhandahåller LMDB API ett effektivt sätt att initialt placera markören. För att göra detta måste du generera en nyckel vars värde uppenbarligen är mindre än eller lika med nyckeln som ligger vid den övre gränsen för intervallet. Till exempel, i förhållande till listan i figuren ovan, kan vi göra en nyckel där fältet parentId kommer att vara lika med 2, och alla övriga är fyllda med nollor. En sådan delvis fylld nyckel levereras till funktionsingången mdb_cursor_get som indikerar operationen 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);

Om den övre gränsen för en grupp nycklar hittas, itererar vi över den tills antingen vi möts eller nyckeln möter en annan parentId, annars tar nycklarna inte slut alls

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​​

Vad som är trevligt är att som en del av iterationen med mdb_cursor_get får vi inte bara nyckeln utan också värdet. Om du, för att uppfylla urvalsvillkoren, bland annat behöver kontrollera fälten från värdedelen av posten, är de ganska tillgängliga utan ytterligare gester.

4.3. Modellera relationer mellan tabeller

Vid det här laget har vi lyckats överväga alla aspekter av att designa och arbeta med en entabellsdatabas. Vi kan säga att en tabell är en uppsättning sorterade poster som består av samma typ av nyckel-värdepar. Om du visar en nyckel som en rektangel och det tillhörande värdet som en parallellepiped får du ett visuellt diagram över databasen.

â € <

Men i verkliga livet är det sällan möjligt att klara sig med så lite blodsutgjutelse. Ofta krävs det i en databas dels att ha flera tabeller, dels att göra urval i dem i en annan ordning än primärnyckeln. Det här sista avsnittet ägnas åt frågorna om deras skapande och sammankoppling.

Indextabeller

Molnapplikationen har en "Galleri"-sektion. Den visar medieinnehåll från hela molnet, sorterat efter datum. För att implementera ett sådant val optimalt, bredvid huvudtabellen måste du skapa en annan med en ny typ av nycklar. De kommer att innehålla ett fält med datumet då filen skapades, vilket kommer att fungera som det primära sorteringskriteriet. Eftersom de nya nycklarna refererar till samma data som nycklarna i huvudtabellen, kallas de indexnycklar. På bilden nedan är de markerade i orange.

För att separera nycklarna för olika tabeller från varandra inom samma databas, lades ytterligare ett tekniskt fält tableId till dem alla. Genom att göra det till högsta prioritet för sortering, kommer vi att uppnå gruppering av nycklar först efter tabeller och inom tabeller - enligt våra egna regler.

Indexnyckeln refererar till samma data som primärnyckeln. En enkel implementering av denna egenskap genom att associera med den en kopia av värdedelen av primärnyckeln är inte optimal ur flera synpunkter:

1. När det gäller utrymme som tas upp kan metadata vara ganska rik.
2. Ur prestandasynpunkt, eftersom när du uppdaterar metadata för en nod, måste du skriva om den med två nycklar.
3. Ur kodsupportens synvinkel, om vi glömmer att uppdatera data för en av nycklarna, kommer vi att få en svårfångad bugg av datainkonsekvens i lagringen.

Därefter kommer vi att överväga hur man eliminerar dessa brister.

Organisera relationer mellan tabeller

Mönstret lämpar sig väl för att länka samman indextabellen med huvudtabellen "nyckel som värde". Som namnet antyder är värdedelen av indexposten en kopia av det primära nyckelvärdet. Detta tillvägagångssätt eliminerar alla ovan nämnda nackdelar som är förknippade med att lagra en kopia av värdedelen av den primära posten. Den enda kostnaden är att för att få ett värde per indexnyckel måste du göra 2 frågor till databasen istället för en. Schematiskt ser det resulterande databasschemat ut så här.

Ett annat mönster för att organisera relationer mellan tabeller är "överflödig nyckel". Dess kärna är att lägga till ytterligare attribut till nyckeln, som inte behövs för att sortera, utan för att återskapa den associerade nyckeln. I Mail.ru Cloud-applikationen finns det riktiga exempel på dess användning, för att undvika en djupdykning i I samband med specifika iOS-ramverk kommer jag att ge ett fiktivt, men ett tydligare exempel

Molnmobilklienter har en sida som visar alla filer och mappar som användaren har delat med andra personer. Eftersom det finns relativt få sådana filer, och det finns en mängd olika typer av specifik information om publicitet förknippad med dem (vem som beviljas tillgång, med vilka rättigheter etc.), kommer det inte att vara rationellt att belasta värdedelen av spela in i huvudtabellen med den. Men om du vill visa sådana filer offline måste du fortfarande lagra dem någonstans. En naturlig lösning är att skapa ett separat bord för det. I diagrammet nedan har dess nyckel prefixet "P", och platshållaren "propname" kan ersättas med det mer specifika värdet "public info".​

All unik metadata, för att lagra vilken den nya tabellen skapades, placeras i värdedelen av posten. Samtidigt vill du inte duplicera data om filer och mappar som redan finns lagrade i huvudtabellen. Istället läggs redundant data till "P"-nyckeln i form av fälten "nod-ID" och "tidsstämpel". Tack vare dem kan du konstruera en indexnyckel, från vilken du kan få en primärnyckel, från vilken du slutligen kan få nodmetadata.

Slutsats

Vi bedömer resultaten av implementeringen av LMDB positivt. Därefter minskade antalet programstopp med 30 %.

Resultaten av det utförda arbetet gav resonans utanför iOS-teamet. För närvarande har en av huvudsektionerna "Filer" i Android-applikationen också gått över till att använda LMDB, och andra delar är på väg. C-språket, i vilket nyckel-värdelagret är implementerat, var en bra hjälp för att initialt skapa ett applikationsramverk kring det plattformsoberoende i C++. En kodgenerator användes för att sömlöst ansluta det resulterande C++-biblioteket med plattformskod i Objective-C och Kotlin Jinni från Dropbox, men det är en helt annan historia.

Källa: will.com