U jesen 2019. dogodio se dugo očekivani događaj u Mail.ru Cloud iOS timu. Glavna baza podataka za trajnu pohranu stanja aplikacije postala je prilično egzotična za mobilni svijet Lightning Memory mapirana baza podataka (LMDB). U rezu, pozornost se poziva na njegov detaljan prikaz u četiri dijela. Prvo, razgovarajmo o razlozima za takav netrivijalan i težak izbor. Zatim prijeđimo na razmatranje tri kita u srcu LMDB arhitekture: memorijsko mapirane datoteke, B + stablo, pristup kopiranja na pisanje za implementaciju transakcija i multiversioning. Za kraj, za desert – praktični dio. U njemu ćemo pogledati kako dizajnirati i implementirati osnovnu shemu s nekoliko tablica, uključujući onu indeksa, povrh API-ja ključ-vrijednost niske razine.​

sadržaj

1. Motivacija za provedbu
2. Pozicioniranje LMDB
3. Tri kita LMDB
   3.1. Kit #1. Memorijski mapirane datoteke
   3.2. Kit #2. B+-drvo
   3.3. Kit #3. kopiranje na pisanje
4. Dizajniranje podatkovne sheme povrh API-ja ključ-vrijednost
   4.1. Osnovne apstrakcije
   4.2. Modeliranje stolova
   4.3. Modeliranje odnosa između tablica

1. Motivacija za provedbu

Jednom godišnje, u 2015. godini, vodili smo računa o tome koliko često sučelje naše aplikacije kasni. Nismo samo ovo napravili. Imamo sve više pritužbi na činjenicu da ponekad aplikacija prestane reagirati na radnje korisnika: gumbi se ne pritisnu, popisi se ne pomiču itd. O mehanici mjerenja rekao na AvitoTechu, pa ovdje dajem samo redoslijed brojeva.

Rezultati mjerenja za nas su postali hladan tuš. Pokazalo se da je problema uzrokovanih smrzavanjem puno više nego bilo kojih drugih. Ako je prije spoznaje ove činjenice glavni tehnički pokazatelj kvalitete bio bez sudara, onda je nakon fokusa pomaknut bez zamrzavanja.

Sagradivši nadzorna ploča sa zamrzavanjem i pošto je proveo kvantitativni и kvaliteta analizom njihovih uzroka, postao je jasan glavni neprijatelj - teška poslovna logika koja se izvršava u glavnoj niti aplikacije. Prirodna reakcija na ovu sramotu bila je goruća želja da se to ugura u radne tokove. Za sustavno rješenje ovog problema pribjegli smo višenitnoj arhitekturi koja se temelji na lakim akterima. Posvetio sam joj adaptacije za iOS svijet dvije niti u kolektivnom twitteru i članak na Habréu. U sklopu trenutne priče želim naglasiti one aspekte odluke koji su utjecali na izbor baze podataka.​

Akterski model organizacije sustava pretpostavlja da višenitnost postaje njegova druga bit. Modelni objekti u njemu vole prelaziti granice niti. I to ne čine ponekad i ponegdje, nego gotovo stalno i posvuda.

Baza podataka jedna je od temeljnih komponenti u prikazanom dijagramu. Njegov glavni zadatak je implementacija makro uzorka Zajednička baza podataka. Ako se u poslovnom svijetu koristi za organiziranje sinkronizacije podataka između usluga, onda u slučaju arhitekture aktera, podataka između niti. Stoga nam je bila potrebna takva baza podataka, rad s kojom u višenitnom okruženju ne uzrokuje čak ni minimalne poteškoće. Konkretno, to znači da objekti izvedeni iz njega moraju biti barem niti sigurni, a idealno uopće ne smiju biti promjenjivi. Kao što znate, potonji se može koristiti istovremeno iz nekoliko niti bez pribjegavanja bilo kakvim zaključavanjima, što ima blagotvoran učinak na performanse.

Drugi značajan faktor koji je utjecao na odabir baze podataka bio je naš cloud API. Inspiriran je git pristupom sinkronizaciji. Kao na njega smo se namjerili izvanmrežni prvi API, što izgleda više nego prikladno za cloud klijente. Pretpostavljalo se da će samo jednom ispumpati puno stanje oblaka, a zatim će se sinkronizacija u velikoj većini slučajeva dogoditi kroz valjane promjene. Nažalost, ta je mogućnost još uvijek samo u teoretskoj zoni, au praksi klijenti nisu naučili kako raditi sa zakrpama. Postoji niz objektivnih razloga za to, koje ćemo, da ne bismo kasnili s predstavljanjem, izostaviti u zagradi. Sada su mnogo zanimljiviji poučni rezultati lekcije o tome što se događa kada API kaže "A", a njegov potrošač ne kaže "B".

Dakle, ako zamislite git, koji prilikom izvršavanja naredbe povlačenja, umjesto da primjenjuje zakrpe na lokalnu snimku, uspoređuje svoje puno stanje s punim poslužiteljskim, tada ćete imati prilično točnu ideju o tome kako se sinkronizira javlja se u klijentima u oblaku. Lako je pogoditi da je za njegovu implementaciju potrebno dodijeliti dva DOM stabla u memoriji s metainformacijama o svim poslužiteljskim i lokalnim datotekama. Ispostavilo se da ako korisnik pohranjuje 500 tisuća datoteka u oblaku, onda je za njegovu sinkronizaciju potrebno ponovno stvoriti i uništiti dva stabla s milijun čvorova. Ali svaki čvor je agregat koji sadrži graf podobjekata. U tom svjetlu rezultati profiliranja su očekivani. Pokazalo se da čak i bez uzimanja u obzir algoritma spajanja, sam postupak stvaranja i zatim uništavanja ogromnog broja malih objekata košta prilično peni.Situacija je pogoršana činjenicom da je osnovna operacija sinkronizacije uključena u veliki broj objekata. korisničkih skripti. Kao rezultat toga, popravljamo drugi važan kriterij pri odabiru baze podataka - mogućnost implementacije CRUD operacija bez dinamičke dodjele objekata.

Ostali zahtjevi su tradicionalniji, a njihov puni popis je sljedeći.

1. Sigurnost niti.
2. Višeprocesiranje. Diktirano željom da se koristi ista instanca baze podataka za sinkronizaciju stanja ne samo između niti, već i između glavne aplikacije i iOS proširenja.
3. Sposobnost predstavljanja pohranjenih entiteta kao nepromjenjivih objekata.​
4. Nedostatak dinamičkih dodjela unutar CRUD operacija.
5. Transakcijska podrška za osnovna svojstva ACIDKljučne riječi: atomičnost, konzistentnost, izolacija i pouzdanost.
6. Brzina na najpopularnijim slučajevima.

Uz ovaj skup zahtjeva, SQLite je bio i još uvijek jest dobar izbor. Međutim, u sklopu proučavanja alternativa naišla sam na jednu knjigu "Početak rada s LevelDB". Pod njezinim vodstvom napisan je benchmark koji uspoređuje brzinu rada s različitim bazama podataka u stvarnim scenarijima oblaka. Rezultat je premašio i najluđa očekivanja. U najpopularnijim slučajevima - dobivanje pokazivača na sortiranom popisu svih datoteka i sortiranom popisu svih datoteka za određeni direktorij - pokazalo se da je LMDB 10 puta brži od SQLitea. Izbor je postao očit.

2. LMDB pozicioniranje

LMDB je biblioteka, vrlo mala (samo 10K redaka), koja implementira najniži temeljni sloj baza podataka - pohranu.

Gornji dijagram pokazuje da usporedba LMDB sa SQLiteom, koji implementira još više razine, općenito nije ispravnija od SQLitea s Core Data. Bilo bi poštenije navesti iste motore za pohranu kao ravnopravne konkurente - BerkeleyDB, LevelDB, Sophia, RocksDB, itd. Postoje čak i razvoji gdje LMDB djeluje kao komponenta mehanizma za pohranu za SQLite. Prvi takav eksperiment 2012 potrošeno autor LMDB Howard Chu. Nalazi pokazalo se toliko intrigantnim da su njegovu inicijativu prihvatili entuzijasti OSS-a, te je našla svoj nastavak u lice LumoSQL. U siječnju 2020. autor ovog projekta je Den Shearer predstavili to na LinuxConfAu.

Glavna upotreba LMDB-a je kao motor za baze podataka aplikacija. Knjižnica svoj izgled duguje programerima OpenLDAP, koji su bili jako nezadovoljni BerkeleyDB-om kao osnovom svog projekta. Odgurujući se od skromne knjižnice btree, Howard Chu uspio je stvoriti jednu od najpopularnijih alternativa našeg vremena. Ovoj priči, kao i unutarnjem ustroju LMDB-a, posvetio je svoj vrlo cool izvještaj. "Baza podataka mapirana memorijom munje". Leonid Jurijev (aka yleo) iz Positive Technologies u svom govoru na Highloadu 2015 "LMDB motor je poseban prvak". U njemu govori o LMDB-u u kontekstu sličnog zadatka implementacije ReOpenLDAP-a, a LevelDB je već bio izložen komparativnoj kritici. Kao rezultat implementacije, Positive Technologies je čak dobio vilicu koja se aktivno razvija MDBX s vrlo ukusnim značajkama, optimizacijama i ispravke pogrešaka.

LMDB se često koristi i kao pohrana. Na primjer, preglednik Mozilla Firefox izabrao za brojne potrebe i, počevši od verzije 9, Xcode preferirano njegov SQLite za pohranjivanje indeksa.

Motor je također zaživio u svijetu mobilnog razvoja. Tragovi njegove uporabe mogu biti pronaći u iOS klijentu za Telegram. LinkedIn je otišao korak dalje i odabrao LMDB kao zadanu pohranu za svoj domaći okvir za predmemoriju podataka, Rocket Data, o kojem ispričao u članku iz 2016.

LMDB se uspješno bori za mjesto pod suncem u niši koju je ostavio BerkeleyDB nakon prelaska pod kontrolu Oraclea. Knjižnica je voljena zbog svoje brzine i pouzdanosti, čak iu usporedbi s vlastitom vrstom. Kao što znate, nema besplatnih ručkova, a želio bih naglasiti kompromis s kojim ćete se morati suočiti kada birate između LMDB i SQLite. Gornji dijagram jasno pokazuje kako se postiže povećana brzina. Prvo, ne plaćamo dodatne slojeve apstrakcije povrh diskovne pohrane. Naravno, u dobroj arhitekturi bez njih se i dalje ne može i neizbježno će se pojaviti u kodu aplikacije, ali će biti puno tanji. Neće imati značajke koje nisu potrebne za određenu aplikaciju, na primjer, podršku za upite u SQL jeziku. Drugo, postaje moguće optimalno implementirati mapiranje aplikacijskih operacija na zahtjeve za pohranu na disku. Ako SQLite u mom radu dolazi iz prosječnih potreba prosječne aplikacije, onda ste vi, kao programer aplikacije, dobro svjesni glavnih scenarija opterećenja. Za produktivnije rješenje, morat ćete platiti povećanu cijenu za razvoj početnog rješenja i njegovu naknadnu podršku.

3. Tri kita LMDB

Nakon pogleda na LMDB iz ptičje perspektive, vrijeme je da odemo dublje. Sljedeća tri odjeljka bit će posvećena analizi glavnih kitova na kojima počiva arhitektura pohrane:

1. Memorijsko mapirane datoteke kao mehanizam za rad s diskom i sinkronizaciju internih struktura podataka.
2. B+-stablo kao organizacija strukture pohranjenih podataka.
3. Copy-on-write kao pristup pružanju ACID transakcijskih svojstava i multiverzioniranja.

3.1. Kit #1. Memorijski mapirane datoteke

Memorijski mapirane datoteke toliko su važan arhitektonski element da se čak pojavljuju u nazivu repozitorija. Problemi predmemoriranja i sinkroniziranja pristupa pohranjenim informacijama u potpunosti su prepušteni na milost i nemilost operativnom sustavu. LMDB ne sadrži nikakve predmemorije u sebi. Ovo je svjesna odluka autora, jer čitanje podataka izravno iz mapiranih datoteka omogućuje vam da smanjite mnoge kutove u implementaciji motora. Ispod je daleko nepotpun popis nekih od njih.

1. Održavanje konzistentnosti podataka u pohrani pri radu s njima iz nekoliko procesa postaje odgovornost operativnog sustava. U sljedećem odjeljku, ovaj mehaničar se raspravlja detaljno i sa slikama.
2. Nepostojanje predmemorija potpuno oslobađa LMDB režijskih troškova povezanih s dinamičkim dodjelama. Čitanje podataka u praksi je postavljanje pokazivača na ispravnu adresu u virtualnoj memoriji i ništa više. Zvuči kao fantazija, ali u izvoru repozitorija svi calloc pozivi su koncentrirani u funkciji konfiguracije repozitorija.
3. Nepostojanje predmemorija također znači nepostojanje zaključavanja povezanih sa sinkronizacijom za pristup istima. Čitači, kojih može postojati proizvoljan broj u isto vrijeme, ne susreću niti jedan muteks na svom putu do podataka. Zbog toga brzina čitanja ima idealnu linearnu skalabilnost u smislu broja CPU-a. U LMDB-u se sinkroniziraju samo modificirajuće operacije. U isto vrijeme može postojati samo jedan pisac.
4. Minimum predmemoriranja i logike sinkronizacije spašava kod od iznimno složene vrste pogrešaka povezanih s radom u višenitnom okruženju. Na konferenciji Usenix OSDI 2014. bile su dvije zanimljive studije baza podataka: "Svi datotečni sustavi nisu stvoreni jednaki: o složenosti izrade aplikacija dosljednih rušenju" и Mučenje baza podataka radi zabave i zarade. Od njih možete dobiti informacije o neviđenoj pouzdanosti LMDB-a i gotovo besprijekornoj implementaciji ACID svojstava transakcija, koja ga nadmašuje u istom SQLiteu.
5. Minimalizam LMDB-a omogućuje da se strojna reprezentacija njegovog koda potpuno smjesti u L1 predmemoriju procesora s rezultirajućim karakteristikama brzine.

Nažalost, u iOS-u memorijsko mapirane datoteke nisu tako ružičaste koliko bismo željeli. Da bismo svjesnije govorili o nedostacima koji su s njima povezani, potrebno je podsjetiti na opća načela implementacije ovog mehanizma u operacijskim sustavima.

Opće informacije o memorijsko mapiranim datotekama

Sa svakom izvršnom aplikacijom operativni sustav pridružuje entitet koji se naziva proces. Svakom procesu dodijeljen je kontinuirani raspon adresa u koje smješta sve što mu je potrebno za rad. Najniže adrese sadrže odjeljke s kodom i tvrdo kodiranim podacima i resursima. Slijedi rastući blok dinamičkog adresnog prostora, koji nam je dobro poznat kao gomila. Sadrži adrese entiteta koji se pojavljuju tijekom rada programa. Na vrhu je područje memorije koje koristi hrpa aplikacija. Ili raste ili se smanjuje, drugim riječima, njegova veličina također ima dinamičnu prirodu. Kako se stog i hrpa ne bi gurali i smetali jedan drugome, odvojeni su na različitim krajevima adresnog prostora. Između dva dinamička odjeljka na vrhu i dnu nalazi se rupa. Adrese u ovom srednjem odjeljku operativni sustav koristi za povezivanje s procesom različitih entiteta. Konkretno, može mapirati određeni kontinuirani skup adresa u datoteku na disku. Takva se datoteka naziva memorijsko mapirana datoteka.​

Adresni prostor dodijeljen procesu je ogroman. Teoretski, broj adresa je ograničen samo veličinom pokazivača, koja je određena bitnošću sustava. Kad bi mu se fizička memorija dodijelila 1-u-1, tada bi prvi proces zauzeo cijeli RAM, i ne bi bilo govora o multitaskingu.​

​Međutim, iz iskustva znamo da moderni operativni sustavi mogu pokrenuti onoliko procesa koliko želite u isto vrijeme. To je moguće zbog činjenice da procesima dodjeljuju puno memorije samo na papiru, ali u stvarnosti u glavnu fizičku memoriju učitavaju samo onaj dio koji je ovdje i sada potreban. Stoga se memorija povezana s procesom naziva virtualnom.

Operativni sustav organizira virtualnu i fizičku memoriju u stranice određene veličine. Čim je određena stranica virtualne memorije zatražena, operativni sustav je učitava u fizičku memoriju i stavlja korespondenciju između njih u posebnu tablicu. Ako nema slobodnih mjesta, tada se jedna od prethodno učitanih stranica kopira na disk, a tražena zauzima njezino mjesto. Ovaj postupak, na koji ćemo se uskoro vratiti, naziva se zamjena. Slika u nastavku ilustrira opisani proces. Na njoj je stranica A s adresom 0 učitana i postavljena na glavnu memorijsku stranicu s adresom 4. Ta se činjenica odrazila u tablici korespondencije u ćeliji broj 0.​

S memorijsko mapiranim datotekama priča je potpuno ista. Logično, oni su navodno kontinuirano i u cijelosti smješteni u virtualnom adresnom prostoru. Međutim, oni ulaze u fizičku memoriju stranicu po stranicu i samo na zahtjev. Izmjena takvih stranica sinkronizirana je s datotekom na disku. Dakle, možete izvršiti I/O datoteke, jednostavno radeći s bajtovima u memoriji - sve promjene će automatski prenijeti kernel operativnog sustava u originalnu datoteku.​
â € <
Slika ispod pokazuje kako LMDB sinkronizira svoje stanje kada radi s bazom podataka iz različitih procesa. Preslikavanjem virtualne memorije različitih procesa na istu datoteku, mi de facto obvezujemo operativni sustav da tranzitivno sinkronizira određene blokove njihovih adresnih prostora jedan s drugim, što je mjesto gdje LMDB izgleda.​
â € <

Važna je nijansa da LMDB mijenja podatkovnu datoteku prema zadanim postavkama putem mehanizma sistemskog poziva pisanja, a sama se datoteka prikazuje u načinu rada samo za čitanje. Ovaj pristup ima dvije važne implikacije.

Prva posljedica je zajednička svim operativnim sustavima. Njegova je bit dodati zaštitu od nenamjernog oštećenja baze podataka netočnim kodom. Kao što znate, izvršne instrukcije procesa mogu slobodno pristupiti podacima s bilo kojeg mjesta u svom adresnom prostoru. U isto vrijeme, kao što smo se upravo sjetili, prikazivanje datoteke u načinu čitanja i pisanja znači da je bilo koja instrukcija može dodatno modificirati. Ako to učini greškom, pokušavajući, na primjer, zapravo prebrisati element niza na nepostojećem indeksu, onda na taj način može slučajno promijeniti datoteku mapiranu na ovu adresu, što će dovesti do oštećenja baze podataka. Ako je datoteka prikazana u načinu rada samo za čitanje, tada će pokušaj promjene adresnog prostora koji joj odgovara dovesti do pada programa sa signalom SIGSEGV, a datoteka će ostati netaknuta.

Druga je posljedica već specifična za iOS. Niti autor niti neki drugi izvori ga eksplicitno ne spominju, ali bez njega LMDB ne bi bio prikladan za rad na ovom mobilnom operativnom sustavu. Sljedeći odjeljak posvećen je njegovom razmatranju.

Specifičnosti memorijsko mapiranih datoteka u iOS-u

Godine 2018. na WWDC-u je bilo prekrasno izvješće iOS Memory Deep Dive. Govori da u iOS-u sve stranice smještene u fizičkoj memoriji pripadaju jednoj od 3 vrste: prljave, komprimirane i čiste.

Čista memorija je zbirka stranica koje se mogu sigurno zamijeniti iz fizičke memorije. Podaci koje sadrže mogu se prema potrebi ponovno učitati iz izvornih izvora. Datoteke mapirane memorije samo za čitanje spadaju u ovu kategoriju. iOS se ne boji isprazniti stranice preslikane na datoteku iz memorije u bilo kojem trenutku, jer je zajamčeno da će biti sinkronizirane s datotekom na disku.
â € <
Sve izmijenjene stranice ulaze u prljavu memoriju, bez obzira gdje se izvorno nalaze. Konkretno, memorijsko mapirane datoteke modificirane pisanjem u virtualnu memoriju koja je s njima povezana također će biti klasificirane na ovaj način. Otvaranje LMDB sa zastavom MDB_WRITEMAP, nakon što unesete izmjene u njega, možete se sami uvjeriti.​

​Čim neka aplikacija počne zauzimati previše fizičke memorije, iOS komprimira svoje prljave stranice. Kolekcija memorije koju zauzimaju prljave i komprimirane stranice je takozvani memorijski otisak aplikacije. Kada dosegne određenu vrijednost praga, demon OOM killer sustava dolazi nakon procesa i prisilno ga prekida. Ovo je posebnost iOS-a u usporedbi s operativnim sustavima za stolna računala. Nasuprot tome, smanjenje memorijskog otiska zamjenom stranica iz fizičke memorije na disk nije omogućeno u iOS-u. O razlozima se može samo nagađati. Možda postupak intenzivnog premještanja stranica na disk i natrag troši previše energije za mobilne uređaje, ili iOS štedi resurs prepisivanja ćelija na SSD diskovima, ili možda dizajneri nisu bili zadovoljni ukupnim performansama sustava, gdje je sve stalno izmjenjivali. Bilo kako bilo, činjenica ostaje.

Dobra vijest, već spomenuta ranije, je da LMDB ne koristi mmap mehanizam za ažuriranje datoteka prema zadanim postavkama. Slijedi da su prikazani podaci iOS-om klasificirani kao čista memorija i ne doprinose otisku memorije. To se može provjeriti pomoću Xcode alata pod nazivom VM Tracker. Snimak zaslona u nastavku prikazuje stanje virtualne memorije iOS Cloud aplikacije tijekom rada. U početku su u njemu inicijalizirane 2 LMDB instance. Prvom je dopušteno preslikati svoju datoteku na 1GiB virtualne memorije, drugom - 512MiB. Unatoč činjenici da obje pohrane zauzimaju određenu količinu rezidentne memorije, nijedna od njih ne pridonosi prljavoj veličini.

Sada je vrijeme za loše vijesti. Zahvaljujući mehanizmu zamjene u 64-bitnim desktop operativnim sustavima, svaki proces može zauzeti onoliko virtualnog adresnog prostora koliko slobodnog prostora na tvrdom disku dopušta za njegovu potencijalnu zamjenu. Zamjena swapa kompresijom u iOS-u drastično smanjuje teoretski maksimum. Sada svi živi procesi moraju stati u glavnu (čitaj RAM) memoriju, a svi oni koji ne stanu podliježu prisilnom prekidu. Spomenuto je kao gore izvješće, i u službena dokumentacija. Kao posljedica toga, iOS ozbiljno ograničava količinu memorije dostupnu za dodjelu putem mmap-a. Ovdje ovdje možete pogledati empirijska ograničenja količine memorije koja se može dodijeliti različitim uređajima pomoću ovog sistemskog poziva. Na najsuvremenijim modelima pametnih telefona, iOS je postao velikodušan za 2 gigabajta, a na vrhunskim verzijama iPada - za 4. U praksi se, naravno, morate usredotočiti na najmlađe podržane modele uređaja, gdje je sve vrlo tužno. Što je još gore, gledajući stanje memorije aplikacije u VM Trackeru, vidjet ćete da LMDB nije jedini koji zahtijeva memorijsko mapiranu memoriju. Dobre dijelove pojedu alokatori sustava, datoteke resursa, okviri slika i drugi manji predatori.

Kao rezultat eksperimenata u oblaku, došli smo do sljedećih kompromisnih vrijednosti memorije koju je dodijelio LMDB: 384 megabajta za 32-bitne uređaje i 768 za 64-bitne. Nakon što se ovaj volumen potroši, sve modificirajuće operacije počinju se dovršavati s kodom MDB_MAP_FULL. Primjećujemo takve pogreške u našem praćenju, ali one su dovoljno male da ih zanemarimo u ovoj fazi.

Neočit razlog za pretjeranu potrošnju memorije pohranom mogu biti dugotrajne transakcije. Da bismo razumjeli kako su ova dva fenomena povezana, pomoći će nam da razmotrimo preostala dva LMDB kita.

3.2. Kit #2. B+-drvo

Za emulaciju tablica na vrhu pohrane ključeva i vrijednosti, sljedeće operacije moraju biti prisutne u API-ju:

1. Umetanje novog elementa.
2. Traženje elementa s danim ključem.
3. Brisanje elementa.
4. Ponavljajte ključne intervale po njihovom redoslijedu.

Najjednostavnija podatkovna struktura koja može lako implementirati sve četiri operacije je binarno stablo pretraživanja. Svaki od njegovih čvorova je ključ koji cijeli podskup dječjih ključeva dijeli na dva podstabla. S lijeve strane su oni koji su manji od roditelja, a s desne - oni koji su veći. Dobivanje uređenog skupa ključeva postiže se jednim od klasičnih obilazaka stabla.​

Binarna stabla imaju dva osnovna nedostatka koja ih sprječavaju da budu učinkovite kao strukture podataka na disku. Prvo, stupanj njihove ravnoteže je nepredvidiv. Postoji znatan rizik dobivanja stabala u kojima visina različitih grana može jako varirati, što značajno pogoršava algoritamsku složenost pretrage u odnosu na očekivanu. Drugo, obilje unakrsnih veza između čvorova lišava binarna stabla lokaliteta u memoriji.Bliski čvorovi (u smislu veza između njih) mogu se nalaziti na potpuno različitim stranicama u virtualnoj memoriji. Kao posljedica toga, čak i jednostavno obilaženje nekoliko susjednih čvorova u stablu može zahtijevati posjet usporedivom broju stranica. To je problem čak i kada govorimo o učinkovitosti binarnih stabala kao strukture podataka u memoriji, budući da stalno rotiranje stranica u predmemorij procesora nije jeftino. Kada se radi o čestom podizanju stranica povezanih s čvorovima s diska, stvari postaju jako loše. žalosno,

B-stabla, kao evolucija binarnih stabala, rješavaju probleme identificirane u prethodnom paragrafu. Prvo, oni se sami uravnotežuju. Drugo, svaki od njihovih čvorova dijeli skup dječjih ključeva ne na 2, već na M poredanih podskupova, a broj M može biti prilično velik, reda veličine nekoliko stotina ili čak tisuća.

Time:

1. Svaki čvor ima velik broj već naručenih ključeva i stabla su vrlo niska.
2. Stablo dobiva svojstvo lokalnosti u memoriji, budući da su ključevi koji su bliski po vrijednosti prirodno smješteni jedan pored drugog na jednom ili susjednim čvorovima.
3. Smanjuje broj tranzitnih čvorova prilikom spuštanja niz stablo tijekom operacije pretraživanja.
4. Smanjuje broj ciljnih čvorova koji se čitaju za upite raspona, jer svaki od njih već sadrži velik broj uređenih ključeva.

LMDB koristi varijantu B-stabla koja se naziva B+ stablo za pohranu podataka. Gornji dijagram prikazuje tri vrste čvorova koje sadrži:

1. Na vrhu je korijen. Materijalizira ništa više od koncepta baze podataka unutar repozitorija. Unutar jedne LMDB instance možete stvoriti više baza podataka koje dijele mapirani virtualni adresni prostor. Svaki od njih kreće iz svog korijena.
2. Na najnižoj razini su listovi (list). Oni i samo oni sadrže parove ključ-vrijednost pohranjene u bazi podataka. Usput, to je osobitost B+-stabala. Ako normalno B-stablo pohranjuje vrijednosne dijelove u čvorovima svih razina, tada je B+-varijacija samo na najnižoj. Nakon što smo popravili ovu činjenicu, u nastavku ćemo podtip stabla koji se koristi u LMDB jednostavno nazvati B-stablom.
3. Između korijena i listova nalazi se 0 ili više tehničkih razina s navigacijskim (granastim) čvorovima. Njihova je zadaća razvrstati skup ključeva između listova.

Fizički, čvorovi su blokovi memorije unaprijed određene duljine. Njihova veličina višestruka je veličina memorijskih stranica u operativnom sustavu, o čemu smo govorili gore. Struktura čvora prikazana je u nastavku. Zaglavlje sadrži metainformacije, od kojih je najočitija, na primjer, kontrolni zbroj. Zatim dolaze informacije o odmacima, duž kojih se nalaze ćelije s podacima. Uloga podataka može biti ili ključ, ako je riječ o navigacijskim čvorovima, ili cijeli par ključ-vrijednost u slučaju listova. Više o strukturi stranica možete pročitati u radu "Procjena pohranjivanja ključeva i vrijednosti visokih performansi".

Nakon što smo se pozabavili unutarnjim sadržajem čvorova stranice, dalje ćemo predstaviti LMDB B-stablo na pojednostavljen način u sljedećem obliku.

Stranice s čvorovima sekvencijalno su raspoređene na disku. Stranice s većim brojem nalaze se prema kraju datoteke. Takozvana meta stranica (meta stranica) sadrži informacije o pomacima, pomoću kojih se mogu pronaći korijeni svih stabala. Kada se datoteka otvori, LMDB skenira datoteku stranicu po stranicu od kraja do početka u potrazi za valjanom meta stranicom i kroz nju pronalazi postojeće baze podataka.​

Sada, imajući predodžbu o logičkoj i fizičkoj strukturi organizacije podataka, možemo nastaviti s razmatranjem trećeg kita LMDB-a. Uz njegovu pomoć se sve modifikacije pohrane događaju transakcijski i izolirano jedna od druge, dajući bazi podataka kao cjelini i svojstvo viševerzije.

3.3. Kit #3. kopiranje na pisanje

Neke operacije B-stabla uključuju izradu čitavog niza promjena na njegovim čvorovima. Jedan primjer je dodavanje novog ključa čvoru koji je već dosegao svoj maksimalni kapacitet. U ovom slučaju, potrebno je, prvo, podijeliti čvor na dva, i drugo, dodati vezu na novi izdvojeni podređeni čvor u njegovom roditelju. Ovaj postupak je potencijalno vrlo opasan. Ako se iz nekog razloga (pad, nestanak struje i sl.) dogodi samo dio promjena iz niza, stablo će ostati u nekonzistentnom stanju.

Jedno tradicionalno rješenje za izradu baze podataka tolerantne na greške je dodavanje dodatne strukture podataka temeljene na disku, transakcijskog dnevnika, također poznatog kao zapis unaprijed (WAL), pored B-stabla. To je datoteka na čijem se kraju, striktno prije izmjene samog B-stabla, ispisuje namjeravana operacija. Stoga, ako se tijekom samodijagnostike otkrije oštećenje podataka, baza podataka pregledava dnevnik kako bi se sama očistila.

LMDB je odabrao drugačiju metodu kao svoj mehanizam za toleranciju grešaka, koji se zove kopiranje na pisanje. Njegova bit je da umjesto ažuriranja podataka na postojećoj stranici, prvo ju kopira u cijelosti i vrši sve izmjene koje su već u kopiji.​

Nadalje, kako bi ažurirani podaci bili dostupni, potrebno je promijeniti vezu na čvor koji je postao ažuran u nadređenom čvoru u odnosu na njega. Budući da ga također treba modificirati za to, također je unaprijed kopiran. Proces se nastavlja rekurzivno sve do korijena. Podaci na meta stranici posljednji se mijenjaju.​​

Ako se proces iznenada sruši tijekom postupka ažuriranja, tada ili nova meta stranica neće biti stvorena ili neće biti zapisana na disk do kraja, a njezin kontrolni zbroj bit će netočan. U bilo kojem od ova dva slučaja, nove stranice neće biti dostupne, a stare neće biti pogođene. Ovo eliminira potrebu da LMDB piše zapisnik unaprijed kako bi se održala dosljednost podataka. De facto, gore opisana struktura pohrane podataka na disku istovremeno preuzima i svoju funkciju. Nepostojanje eksplicitnog dnevnika transakcija jedna je od značajki LMDB-a, koja omogućuje veliku brzinu čitanja podataka.​

Rezultirajuća konstrukcija, nazvana B-stablo samo za dodavanje, prirodno osigurava izolaciju transakcije i multiverzioniranje. U LMDB-u svaka otvorena transakcija ima ažurirani korijen stabla koji je povezan s njom. Sve dok transakcija nije dovršena, stranice stabla povezane s njom nikada se neće promijeniti ili ponovno upotrijebiti za nove verzije podataka. Dakle, možete raditi koliko god želite točno sa skupom podataka koji je bio relevantan na vrijeme kada je transakcija otvorena, čak i ako se pohrana u ovom trenutku nastavlja aktivno ažurirati. Ovo je bit multiverzioniranja, što LMDB čini idealnim izvorom podataka za naše voljene UICollectionView. Nakon što ste otvorili transakciju, ne morate povećavati memorijski otisak aplikacije, žurno ispumpavajući trenutne podatke u neku strukturu u memoriji, bojeći se da ćete ostati bez ičega. Ova značajka razlikuje LMDB od istog SQLitea, koji se ne može pohvaliti takvom potpunom izolacijom. Otvaranjem dvije transakcije u potonjoj i brisanjem određenog zapisa unutar jedne od njih, isti se zapis više ne može dobiti unutar druge preostale.

​Obrnuta strana medalje je potencijalno značajno veća potrošnja virtualne memorije. Slajd pokazuje kako će struktura baze podataka izgledati ako se modificira u isto vrijeme s 3 otvorene transakcije čitanja koje gledaju različite verzije baze podataka. Budući da LMDB ne može ponovno koristiti čvorove koji su dostupni iz korijena povezanih sa stvarnim transakcijama, pohrana nema izbora nego dodijeliti još jedan četvrti korijen u memoriji i ponovno klonirati modificirane stranice ispod njega.

Ovdje neće biti suvišno prisjetiti se odjeljka o memorijsko mapiranim datotekama. Čini se da nas dodatna potrošnja virtualne memorije ne bi trebala previše smetati, budući da ne doprinosi memorijskom otisku aplikacije. Međutim, istodobno je primijećeno da je iOS vrlo škrt u dodjeli, a ne možemo pružiti 1 terabajtnu LMDB regiju na poslužitelju ili radnoj površini s majstorovog ramena i uopće ne razmišljati o ovoj značajci. Kad je moguće, trebali biste pokušati zadržati životni vijek transakcija što je moguće kraćim.

4. Dizajniranje sheme podataka povrh API-ja ključ-vrijednost

Počnimo analizirati API gledajući osnovne apstrakcije koje pruža LMDB: okruženje i baze podataka, ključevi i vrijednosti, transakcije i kursori.

Napomena o popisima kodova

Sve funkcije u LMDB javnom API-ju vraćaju rezultat svog rada u obliku koda greške, ali u svim kasnijim popisima njegova je provjera izostavljena radi sažetosti.U praksi smo za interakciju s repozitorijem koristili vlastiti kod. vilica C++ omotači lmdbxx, u kojem se pogreške materijaliziraju kao C++ iznimke.

Kao najbrži način povezivanja LMDB-a s iOS ili macOS projektom, nudim svoj CocoaPod POSLMDB.

4.1. Osnovne apstrakcije

Okoliš

Struktura MDB_env to je spremište internog stanja LMDB-a. Obitelj funkcija s prefiksom mdb_env omogućuje vam da konfigurirate neka od njegovih svojstava. U najjednostavnijem slučaju, inicijalizacija motora izgleda ovako.

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

U aplikaciji Mail.ru Cloud promijenili smo zadane vrijednosti za samo dva parametra.

Prvi je veličina virtualnog adresnog prostora u koji je mapirana datoteka za pohranu. Nažalost, čak i na istom uređaju, određena vrijednost može značajno varirati od izvođenja do izvođenja. Kako bismo uzeli u obzir ovu značajku iOS-a, dinamički odabiremo maksimalnu količinu pohrane. Počevši od određene vrijednosti, sukcesivno se prepolovljava do funkcije mdb_env_open neće vratiti rezultat osim ENOMEM. U teoriji, postoji suprotan način - prvo dodijelite minimum memorije motoru, a zatim, kada se primi greška MDB_MAP_FULL, povećajte ga. Međutim, mnogo je trnovitiji. Razlog je taj što postupak ponovnog mapiranja memorije pomoću funkcije mdb_env_set_map_size poništava sve entitete (kursore, transakcije, ključeve i vrijednosti) ranije primljene od motora. Uzimanje u obzir takvog razvoja događaja u kodu dovest će do njegove značajne komplikacije. Ako vam je ipak virtualna memorija jako draga, onda je to možda razlog da pogledate vilicu koja je otišla daleko naprijed. MDBX, gdje se među deklariranim značajkama nalazi i “automatsko podešavanje veličine baze podataka u hodu”.

Drugi parametar, čija nam zadana vrijednost nije odgovarala, regulira mehaniku osiguranja sigurnosti niti. Nažalost, barem u iOS-u 10, postoje problemi s podrškom za lokalnu pohranu niti. Iz tog razloga, u gornjem primjeru, spremište se otvara s oznakom MDB_NOTLS. Osim toga, također je potrebno vilica C++ omotač lmdbxxza rezanje varijabli s i u ovom atributu.

baze podataka

Baza podataka je zasebna instanca B-stabla o kojem smo govorili gore. Njegovo otvaranje događa se unutar transakcije, što se u početku može činiti malo čudnim.

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

Doista, transakcija u LMDB-u je entitet za pohranu, a ne određena baza podataka. Ovaj koncept vam omogućuje izvođenje atomskih operacija na entitetima koji se nalaze u različitim bazama podataka. U teoriji, to otvara mogućnost modeliranja tablica u obliku različitih baza podataka, ali ja sam svojedobno išao drugim putem, koji je detaljno opisan u nastavku.

Ključevi i vrijednosti

Struktura MDB_val modelira koncept i ključa i vrijednosti. Repozitorij nema pojma o njihovoj semantici. Za nju je nešto što je drugačije samo niz bajtova određene veličine. Maksimalna veličina ključa je 512 bajtova.

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

Trgovina koristi komparator za sortiranje ključeva uzlaznim redoslijedom. Ako ga ne zamijenite svojim, koristit će se zadani, koji ih razvrstava bajt po bajt leksikografskim redoslijedom.​

Transakcije

Transakcijski uređaj je detaljno opisan u prethodno poglavlje, pa ću ovdje ukratko ponoviti njihova glavna svojstva:

1. Podrška za sva osnovna svojstva ACIDKljučne riječi: atomičnost, konzistentnost, izolacija i pouzdanost. Ne mogu ne primijetiti da je u pogledu trajnosti na macOS-u i iOS-u ispravljena pogreška u MDBX-u. Više možete pročitati u njihovim README.
2. Pristup višenitnosti opisan je shemom "jedan pisac / više čitača". Pisci blokiraju jedni druge, ali ne blokiraju čitatelje. Čitatelji ne blokiraju pisce niti jedni druge.
3. Podrška za ugniježđene transakcije.
4. Podrška za više verzija.

Multiverzioniranje u LMDB-u je toliko dobro da ga želim demonstrirati na djelu. Kod u nastavku pokazuje da svaka transakcija radi upravo s onom verzijom baze podataka koja je bila relevantna u trenutku otvaranja, potpuno izolirana od svih naknadnih promjena. Inicijalizacija repozitorija i dodavanje testnog zapisa u njega nije od interesa, tako da su ovi rituali ostavljeni pod spojlerom.

Dodavanje testnog unosa

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

Po izboru, preporučujem isprobati isti trik sa SQLiteom i vidjeti što će se dogoditi.

Multiverzioniranje donosi vrlo lijepe prednosti životu iOS programera. Pomoću ovog svojstva možete jednostavno i prirodno prilagoditi stopu ažuriranja izvora podataka za zaslonske obrasce na temelju razmatranja korisničkog iskustva. Na primjer, uzmimo takvu značajku aplikacije Mail.ru Cloud kao automatsko učitavanje sadržaja iz galerije medija sustava. Uz dobru vezu, klijent je u mogućnosti dodati nekoliko fotografija u sekundi na poslužitelj. Ako ažurirate nakon svakog preuzimanja UICollectionView s medijskim sadržajem u korisničkom oblaku, možete zaboraviti na 60 fps i glatko pomicanje tijekom ovog procesa. Kako biste spriječili česta ažuriranja zaslona, ​​morate nekako ograničiti brzinu promjene podataka u bazi UICollectionViewDataSource.

Ako baza podataka ne podržava multiverzioniranje i dopušta vam rad samo s trenutnim trenutnim stanjem, tada da biste stvorili vremenski stabilnu snimku podataka, trebate je kopirati ili u neku strukturu podataka u memoriji ili u privremenu tablicu. Svaki od ovih pristupa je vrlo skup. U slučaju pohrane u memoriji, dobivamo i troškove memorije uzrokovane pohranjivanjem konstruiranih objekata i vremenske troškove povezane sa redundantnim ORM transformacijama. Što se tiče privremenog stola, ovo je još skuplje zadovoljstvo, koje ima smisla samo u ne-trivijalnim slučajevima.

Multiversioning LMDB rješava problem održavanja stabilnog izvora podataka na vrlo elegantan način. Dovoljno je samo otvoriti transakciju i voila - dok je ne završimo, skup podataka je zajamčeno fiksan. Logika stope ažuriranja sada je u potpunosti u rukama prezentacijskog sloja, bez dodatnih troškova značajnih resursa.

Pokazivači

Kursori pružaju mehanizam za urednu iteraciju preko parova ključ-vrijednost prelazeći B-stablo. Bez njih bi bilo nemoguće učinkovito modelirati tablice u bazi podataka, na što ćemo se sada osvrnuti.

4.2. Modeliranje stolova

Svojstvo redoslijeda ključeva omogućuje vam da konstruirate apstrakciju najviše razine kao što je tablica na vrhu osnovnih apstrakcija. Razmotrimo ovaj proces na primjeru glavne tablice klijenta u oblaku, u kojoj su predmemorirane informacije o svim datotekama i mapama korisnika.

Shema tablice

Jedan od uobičajenih scenarija za koje treba izoštriti strukturu tablice sa stablom mapa je odabir svih elemenata koji se nalaze unutar određenog direktorija. Dobar model organizacije podataka za učinkovite upite ove vrste je Popis susjedstva. Da biste ga implementirali povrh pohrane ključeva i vrijednosti, potrebno je sortirati ključeve datoteka i mapa na takav način da budu grupirani na temelju pripadnosti nadređenom direktoriju. Osim toga, kako bi se sadržaj direktorija prikazao u obliku poznatom korisniku Windowsa (prvo mape, zatim datoteke, obje su poredane abecednim redom), potrebno je uključiti odgovarajuća dodatna polja u ključu.

​Slika ispod pokazuje kako, na temelju zadatka, može izgledati prikaz ključeva kao niza bajtova. Prvo se postavljaju bajtovi s identifikatorom nadređenog direktorija (crveno), zatim s tipom (zeleno), a već u repu s imenom (plavo). Budući da su razvrstani pomoću zadanog LMDB komparatora u leksikografskom redoslijedu, poredani su u traženi način. Sekvencijalno prelaženje tipki s istim crvenim prefiksom daje nam vrijednosti koje su im pridružene redoslijedom kojim bi trebale biti prikazane u korisničkom sučelju (desno), bez potrebe za dodatnom naknadnom obradom.

Serializiranje ključeva i vrijednosti

Postoje mnoge metode za serijalizaciju objekata širom svijeta. Budući da nismo imali drugog zahtjeva osim brzine, odabrali smo najbrži mogući za sebe - memorijski dump zauzet instancom strukture jezika C. Dakle, ključ elementa direktorija može se modelirati sljedećom strukturom NodeKey.

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

Spremiti NodeKey u skladištu need in object MDB_val postaviti pokazivač na podatke na adresu početka strukture, te izračunati njihovu veličinu pomoću funkcije sizeof.

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

U prvom poglavlju o kriterijima odabira baze podataka spomenuo sam minimiziranje dinamičkih dodjela kao dio CRUD operacija kao važan faktor odabira. Kod funkcije serialize pokazuje kako se, u slučaju LMDB-a, mogu potpuno izbjeći kada se novi zapisi ubace u bazu podataka. Dolazni niz bajtova s ​​poslužitelja prvo se transformira u strukture stogova, a zatim se trivijalno bacaju u pohranu. S obzirom da također nema dinamičkih dodjela unutar LMDB-a, možete dobiti fantastičnu situaciju za standarde iOS-a - koristite samo stack memoriju za rad s podacima cijelim putem od mreže do diska!

Naručivanje ključeva s binarnim komparatorom

Odnos ključnog reda zadan je posebnom funkcijom koja se naziva komparator. Budući da motor ne zna ništa o semantici bajtova koje oni sadrže, zadani komparator nema drugog izbora nego složiti ključeve leksikografskim redoslijedom, pribjegavajući njihovoj usporedbi bajt po bajt. Njegova uporaba za uređenje struktura slična je brijanju sjekirom za rezbarenje. Međutim, u jednostavnim slučajevima, smatram da je ova metoda prihvatljiva. Alternativa je opisana u nastavku, ali ovdje ću zabilježiti nekoliko grablji razbacanih po putu.

Prvo što treba imati na umu je memorijska reprezentacija primitivnih tipova podataka. Dakle, na svim Apple uređajima cjelobrojne varijable pohranjene su u formatu Mali Endian. To znači da će bajt najmanjeg značaja biti s lijeve strane i nećete moći sortirati cijele brojeve pomoću njihove usporedbe bajt po bajt. Na primjer, pokušaj to učiniti sa skupom brojeva od 0 do 511 rezultirat će sljedećim rezultatom.

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

Da bi se riješio ovaj problem, cijeli brojevi moraju biti pohranjeni u ključu u formatu prikladnom za komparator bajtova. Funkcije iz obitelji pomoći će provesti potrebnu transformaciju. hton* (posebno htons za dvobajtne brojeve iz primjera).

Format za predstavljanje nizova u programiranju je, kao što znate, cjelina priča. Ako semantika nizova, kao i kodiranje koje se koristi za njihovo predstavljanje u memoriji, sugeriraju da može postojati više od jednog bajta po znaku, tada je bolje odmah odustati od ideje korištenja zadanog usporednika.

Druga stvar koju treba imati na umu je principi poravnanja struct field compiler. Zbog njih se bajtovi s vrijednostima smeća mogu formirati u memoriji između polja, što, naravno, prekida sortiranje bajtova. Da biste uklonili smeće, morate ili deklarirati polja u strogo definiranom redoslijedu, imajući na umu pravila poravnanja, ili koristiti atribut u deklaraciji strukture packed.

Redoslijed ključeva pomoću vanjskog komparatora

Logika ključne usporedbe može se pokazati presloženom za binarni komparator. Jedan od mnogih razloga je prisutnost tehničkih polja unutar struktura. Ilustrirat ću njihovu pojavu na primjeru već poznatog ključa za element imenika.

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

Uz svu svoju jednostavnost, u velikoj većini slučajeva troši previše memorije. Međuspremnik naslova je 256 bajtova, iako u prosjeku nazivi datoteka i mapa rijetko prelaze 20-30 znakova.

​Jedna od standardnih tehnika za optimizaciju veličine zapisa je njegovo skraćivanje kako bi odgovarao njegovoj stvarnoj veličini. Njegova bit je da se sadržaji svih polja varijabilne duljine pohranjuju u međuspremnik na kraju strukture, a njihove duljine pohranjuju u zasebne varijable.U skladu s ovim pristupom, ključ NodeKey se transformira na sljedeći način.

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

Nadalje, tijekom serijalizacije, nije navedeno kao veličina podataka sizeof cijele strukture, a veličina svih polja je fiksna duljina plus veličina stvarno korištenog dijela međuspremnika.

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

Kao rezultat refaktoriranja, dobili smo značajnu uštedu u prostoru koji zauzimaju tipke. Međutim, zbog tehničkog područja nameLength, zadani binarni komparator više nije prikladan za ključnu usporedbu. Ako ga ne zamijenimo svojim, onda će dužina imena biti prioritetniji faktor u sortiranju od samog naziva.

LMDB omogućuje svakoj bazi podataka da ima vlastitu funkciju usporedbe ključeva. To se radi pomoću funkcije mdb_set_compare strogo prije otvaranja. Iz očiglednih razloga, baza podataka ne može se mijenjati tijekom svog životnog vijeka. Na ulazu komparator prima dva ključa u binarnom formatu, a na izlazu vraća rezultat usporedbe: manje od (-1), veće od (1) ili jednako (0). Pseudokod za NodeKey izgleda tako.

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

Sve dok su svi ključevi u bazi podataka istog tipa, legalno je bezuvjetno prebaciti njihovu bajt reprezentaciju na tip strukture aplikacije ključa. Ovdje postoji jedna nijansa, ali o njoj će se raspravljati malo niže u pododjeljku "Zapisi o čitanju".

Serijalizacija vrijednosti

S ključevima pohranjenih zapisa LMDB radi izuzetno intenzivno. Oni se međusobno uspoređuju u okviru rada bilo koje aplikacije, a performanse cjelokupnog rješenja ovise o brzini komparatora. U idealnom svijetu, zadani binarni komparator trebao bi biti dovoljan za usporedbu ključeva, ali ako ste stvarno morali koristiti svoj, tada bi postupak za deserijalizaciju ključeva u njemu trebao biti što brži.

Baza podataka nije posebno zainteresirana za Value-dio zapisa (vrijednost). Njegova pretvorba iz prikaza bajta u objekt događa se samo kada to već zahtijeva aplikacijski kod, na primjer, da ga prikaže na zaslonu. Budući da se to događa relativno rijetko, zahtjevi za brzinom ovog postupka nisu toliko kritični, au njegovoj provedbi puno smo slobodniji fokusirati se na praktičnost. Na primjer, za serijalizaciju metapodataka o datotekama koje još nisu preuzete, koristimo NSKeyedArchiver.

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

Međutim, postoje trenuci kada je izvedba važna. Na primjer, kada spremamo meta-informacije o strukturi datoteke korisničkog oblaka, koristimo isti ispis memorije objekta. Vrhunac zadatka generiranja njihovog serijaliziranog prikaza je činjenica da su elementi direktorija modelirani hijerarhijom klasa.​

Za njegovu implementaciju u jeziku C, specifična polja nasljednika su izdvojena u zasebne strukture, a njihova veza s baznom specificirana je kroz polje tipa unije. Stvarni sadržaj unije specificiran je putem tehničkog atributa tipa.

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

Dodavanje i ažuriranje zapisa

Serializirani ključ i vrijednost mogu se dodati u pohranu. Za to se koristi funkcija mdb_put.

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

U fazi konfiguracije, repozitoriju se može dopustiti ili zabraniti pohranjivanje više zapisa s istim ključem.​​ Ako je dupliciranje ključeva zabranjeno, tada prilikom umetanja zapisa možete odrediti je li ažuriranje već postojećeg zapisa dopušteno ili ne. Ako do habanja može doći samo kao rezultat pogreške u kodu, tada se možete osigurati od toga navođenjem oznake NOOVERWRITE,

Zapisi o čitanju

Funkcija za čitanje zapisa u LMDB je mdb_get. Ako je par ključ-vrijednost predstavljen prethodno odbačenim strukturama, tada ovaj postupak izgleda ovako.

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

Prikazani popis pokazuje kako vam serijalizacija kroz dump struktura omogućuje da se riješite dinamičkih dodjela ne samo prilikom pisanja, već i prilikom čitanja podataka. Izvedeno iz funkcije mdb_get pokazivač gleda točno na adresu virtualne memorije gdje baza podataka pohranjuje bajtnu reprezentaciju objekta. Zapravo, dobivamo neku vrstu ORM-a, koji gotovo besplatno pruža vrlo veliku brzinu čitanja podataka. Uz svu ljepotu pristupa, potrebno je zapamtiti nekoliko značajki povezanih s njim.

1. Za transakciju samo za čitanje, zajamčeno je da će pokazivač na strukturu vrijednosti ostati valjan samo dok se transakcija ne zatvori. Kao što je ranije navedeno, stranice B-stabla na kojem se objekt nalazi, zahvaljujući principu kopiranja na pisanje, ostaju nepromijenjene sve dok se barem jedna transakcija odnosi na njih. U isto vrijeme, čim se posljednja transakcija povezana s njima završi, stranice se mogu ponovno koristiti za nove podatke. Ako je neophodno da objekti prežive transakciju koja ih je stvorila, tada se ipak moraju kopirati.
2. Za transakciju čitanja i pisanja, pokazivač na rezultirajuću strukturnu vrijednost bit će valjan samo do prve procedure modificiranja (pisanje ili brisanje podataka).
3. Iako struktura NodeValue nije punopravan, ali dotjeran (pogledajte pododjeljak "Naručivanje ključeva vanjskim komparatorom"), kroz pokazivač možete lako pristupiti njegovim poljima. Glavna stvar je ne dereferencirati ga!
4. Ni u kojem slučaju ne možete mijenjati strukturu putem primljenog pokazivača. Sve promjene moraju se izvršiti samo putem metode mdb_put. Međutim, uz svu želju da se to učini, neće uspjeti, jer je memorijsko područje u kojem se nalazi ova struktura mapirano u načinu samo za čitanje.
5. Ponovno mapirajte datoteku u adresni prostor procesa kako biste, na primjer, povećali maksimalnu veličinu pohrane pomoću funkcije mdb_env_set_map_size potpuno poništava sve transakcije i povezane entitete općenito, a posebno pokazivače za čitanje objekata.

Konačno, još jedna osobina je toliko podmukla da razotkrivanje njezine suštine ne stane samo u još jednu točku. U poglavlju o B-stablu dao sam dijagram organizacije njegovih stranica u memoriji. Iz toga slijedi da adresa početka međuspremnika sa serijaliziranim podacima može biti apsolutno proizvoljna. Zbog toga je pokazivač na njih, dobiven u strukturi MDB_val i bačen na pokazivač na strukturu općenito je neporavnat. U isto vrijeme, arhitekture nekih čipova (u slučaju iOS-a, to je armv7) zahtijevaju da adresa bilo kojeg podatka bude višestruka veličina strojne riječi, ili, drugim riječima, bitnost sustava (za armv7, ovo je 32 bita). Drugim riječima, operacija poput *(int *foo)0x800002 na njima se izjednačava s bijegom i vodi na izvršenje s presudom EXC_ARM_DA_ALIGN. Postoje dva načina da se izbjegne takva tužna sudbina.

Prvi je prethodno kopirati podatke u poznatu usklađenu strukturu. Na primjer, na prilagođenom komparatoru to će se odraziti na sljedeći način.

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

Alternativni način je unaprijed obavijestiti kompajler da strukture s ključem i vrijednošću možda neće biti usklađene pomoću atributa aligned(1). Na ARM može biti isti učinak postići i pomoću atributa upakirano. S obzirom da također doprinosi optimizaciji prostora koji zauzima konstrukcija, ova metoda mi se čini poželjnijom, iako приводит povećati troškove operacija pristupa podacima.

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

Upiti raspona

Za iteraciju preko grupe zapisa, LMDB pruža apstrakciju kursora. Pogledajmo kako raditi s njim na primjeru tablice s već poznatim metapodacima korisničkog oblaka.

Kao dio prikaza popisa datoteka u direktoriju, trebate pronaći sve ključeve s kojima su povezane njegove podređene datoteke i mape. U prethodnim pododjeljcima razvrstali smo ključeve NodeKey tako da su prvo poredani prema ID-u nadređenog imenika. Stoga se tehnički zadatak dobivanja sadržaja mape svodi na postavljanje pokazivača na gornju granicu skupine ključeva s danim prefiksom, nakon čega slijedi iteracija do donje granice.

Gornju granicu možete pronaći "na čelu" sekvencijalnim pretraživanjem. Da biste to učinili, pokazivač se postavlja na početak cijelog popisa ključeva u bazi podataka, a zatim se povećava dok se ključ s identifikatorom nadređenog direktorija ne pojavi ispod njega. Ovaj pristup ima 2 očita nedostatka:

1. Linearna složenost pretrage, iako se, kao što znate, u stablima općenito, a posebno u B-stablima, može izvršiti u logaritamskom vremenu.​
2. Uzalud se iz datoteke u glavnu memoriju dižu sve stranice koje prethode željenoj, što je iznimno skupo.

Srećom, LMDB API pruža učinkovit način za početno pozicioniranje pokazivača. Da biste to učinili, trebate formirati ključ čija je vrijednost manja ili jednaka ključu koji se nalazi na gornjoj granici intervala. Na primjer, u odnosu na popis na gornjoj slici, možemo napraviti ključ u kojem polje parentId bit će jednak 2, a svi ostali su popunjeni nulama. Takav djelomično ispunjen ključ dovodi se na ulaz funkcije mdb_cursor_get indikacija rada 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);

Ako se pronađe gornja granica grupe ključeva, ponavljamo je preko nje sve dok ne sretnemo ključ ili ključ s drugim parentId, ili ključevi uopće neće nestati.​

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

Ono što je lijepo, kao dio iteracije koristeći mdb_cursor_get, dobivamo ne samo ključ, već i vrijednost. Ako je za ispunjenje uvjeta odabira potrebno provjeriti, između ostalog, i polja iz vrijednosnog dijela zapisa, tada su sasvim dostupna sama sebi bez dodatnih gesta.

4.3. Modeliranje odnosa između tablica

Do danas smo uspjeli razmotriti sve aspekte projektiranja i rada s jednom tablicom baze podataka. Možemo reći da je tablica skup sortiranih zapisa koji se sastoje od parova ključ-vrijednost istog tipa. Ako ključ prikažete kao pravokutnik, a njegovu pridruženu vrijednost kao okvir, dobit ćete vizualni dijagram baze podataka.

â € <

Međutim, u stvarnom životu rijetko je moguće proći s tako malo krvi. Često je u bazi podataka potrebno, prvo, imati nekoliko tablica, i drugo, izvršiti odabire u njima redoslijedom koji se razlikuje od primarnog ključa. Ovaj posljednji odjeljak posvećen je pitanjima njihova stvaranja i međusobnog povezivanja.

Indeksne tablice

Aplikacija u oblaku ima odjeljak "Galerija". Prikazuje medijski sadržaj iz cijelog oblaka, poredan po datumu. Za optimalnu implementaciju takvog odabira, uz glavnu tablicu potrebno je kreirati još jednu s novom vrstom ključeva. Oni će sadržavati polje s datumom stvaranja datoteke, što će djelovati kao primarni kriterij sortiranja. Budući da se novi ključevi odnose na iste podatke kao i ključevi u temeljnoj tablici, nazivaju se indeksnim ključevima. Istaknuti su narančastom bojom na slici ispod.

Kako bi se razdvojili ključevi različitih tablica jedne od drugih unutar iste baze podataka, svima je dodano dodatno tehničko polje tableId. Postavljajući ga kao najviši prioritet za sortiranje, prvo ćemo grupirati ključeve po tablicama, a već unutar tablica - prema vlastitim pravilima.​

Ključ indeksa odnosi se na iste podatke kao i primarni ključ. Izravna implementacija ovog svojstva povezivanjem s njim kopije vrijednosnog dijela primarnog ključa je suboptimalna s nekoliko točaka gledišta odjednom:​

1. Sa stajališta zauzetog prostora, metapodaci mogu biti prilično bogati.
2. Sa stajališta performansi, budući da ćete prilikom ažuriranja metapodataka čvora morati prebrisati dva ključa.
3. Sa stajališta podrške kodu, uostalom, ako zaboravimo ažurirati podatke za jedan od ključeva, dobit ćemo suptilnu pogrešku nedosljednosti podataka u pohrani.

Zatim ćemo razmotriti kako ukloniti ove nedostatke.

Organizacija odnosa između tablica

Uzorak je prikladan za povezivanje indeksne tablice s glavnom "ključ kao vrijednost". Kao što naziv implicira, vrijednosni dio zapisa indeksa je kopija vrijednosti primarnog ključa. Ovaj pristup eliminira sve gore navedene nedostatke povezane s pohranjivanjem kopije vrijednosnog dijela primarnog zapisa. Jedina naknada je da za dobivanje vrijednosti prema ključu indeksa morate napraviti 2 upita bazi podataka umjesto jednog. Shematski, rezultirajuća shema baze podataka je sljedeća.

Drugi obrazac za organiziranje odnosa između tablica je "redundantni ključ". Njegova bit je dodavanje dodatnih atributa ključu, koji su potrebni ne za sortiranje, već za ponovno stvaranje pridruženog ključa. Međutim, postoje stvarni primjeri njegove upotrebe u aplikaciji Mail.ru Cloud, kako bi se izbjeglo duboko zaranjanje u kontekstu specifičnih iOS okvira, dat ću fiktivni, ali razumljiviji primjer.

Cloud mobilni klijenti imaju stranicu koja prikazuje sve datoteke i mape koje je korisnik podijelio s drugim ljudima. Budući da je takvih datoteka relativno malo, a uz njih postoji mnogo specifičnih informacija o publicitetu (kome je dopušten pristup, s kojim pravima itd.), neće biti racionalno opterećivati ​​je vrijednosnim dijelom unos u glavnu tablicu. Međutim, ako želite prikazati takve datoteke izvan mreže, svejedno ih morate negdje pohraniti. Prirodno rješenje je stvoriti zaseban stol za to. Na donjem dijagramu njegov ključ ima prefiks "P", a rezervirano mjesto "propname" može se zamijeniti specifičnijom vrijednošću "public info".​

Svi jedinstveni metapodaci, radi kojih je kreirana nova tablica, premještaju se u vrijednosni dio zapisa. U isto vrijeme, ne želim duplicirati podatke o datotekama i mapama koje su već pohranjene u glavnoj tablici. Umjesto toga, suvišni podaci dodaju se ključu "P" u obliku polja "ID čvora" i "vremenska oznaka". Zahvaljujući njima, možete konstruirati ključ indeksa, pomoću kojeg možete dobiti primarni ključ, pomoću kojeg, konačno, možete dobiti metapodatke čvora.

Zaključak

Rezultate implementacije LMDB-a ocjenjujemo pozitivno. Nakon toga, broj zamrzavanja aplikacija smanjio se za 30%.

Rezultati obavljenog rada naišli su na odjek izvan iOS tima. Trenutačno je jedan od glavnih odjeljaka "Datoteke" u Android aplikaciji također prešao na korištenje LMDB-a, a ostali dijelovi su na putu. Jezik C, u kojem je implementirana pohrana ključ-vrijednosti, bio je dobra pomoć kako bi se aplikacija u početku povezala oko više platformi u jeziku C++. Za besprijekorno povezivanje rezultirajuće C ++ biblioteke s kodom platforme u Objective-C i Kotlinu korišten je generator koda Djinni iz Dropboxa, ali to je druga priča.

Izvor: www.habr.com