Jeseni 2019 se je v ekipi Mail.ru Cloud iOS zgodil dolgo pričakovan dogodek. Glavna zbirka podatkov za trajno shranjevanje stanja aplikacije je postala precej eksotična za mobilni svet Baza podatkov Lightning Memory-Mapped Database (LMDB). Pod rezom vas vabi k njegovemu podrobnemu pregledu v štirih delih. Najprej se pogovorimo o razlogih za tako nepomembno in težko izbiro. Nato preidimo na obravnavo treh kitov v središču arhitekture LMDB: pomnilniško preslikane datoteke, B + drevo, pristop kopiranja ob pisanju za implementacijo transakcij in večrazličic. Za konec pa še za sladico – praktični del. V njem si bomo ogledali, kako oblikovati in implementirati osnovno shemo z več tabelami, vključno z indeksno, poleg API-ja ključ-vrednost na nizki ravni.​

Vsebina

1. Motivacija za izvajanje
2. Pozicioniranje LMDB
3. Trije kiti LMDB
   3.1. Kit #1. Datoteke, preslikane v pomnilnik
   3.2. Kit #2. B+-drevo
   3.3. Kit #3. kopiranje ob pisanju
4. Oblikovanje podatkovne sheme na vrhu API-ja ključ-vrednost
   4.1. Osnovne abstrakcije
   4.2. Modeliranje miz
   4.3. Modeliranje odnosov med tabelami

1. Izvedbena motivacija

V letu 2015 smo enkrat letno poskrbeli za meritev, kako pogosto zaostaja vmesnik naše aplikacije. Nismo samo naredili tega. Vedno več pritožb imamo zaradi dejstva, da se včasih aplikacija neha odzivati ​​na dejanja uporabnikov: gumbi niso pritisnjeni, seznami se ne pomikajo itd. O mehaniki meritev povedal na AvitoTech, zato tukaj podajam samo vrstni red številk.

Rezultati meritev so za nas postali hladen tuš. Izkazalo se je, da je težav, ki jih povzročajo zamrznitve, veliko več kot katere koli druge. Če je bil pred spoznanjem tega dejstva glavni tehnični kazalnik kakovosti brez padca, potem po fokusu premaknjen brez zamrzovanja.

Zgrajena armaturna plošča z zamrzovalniki in ob porabi kvantitativno и kakovost analizi njihovih vzrokov je postal jasen glavni sovražnik - težka poslovna logika, ki se izvaja v glavni niti aplikacije. Naravna reakcija na to sramoto je bila goreča želja, da bi jo potisnili v delovne tokove. Za sistematično rešitev tega problema smo se zatekli k večnitni arhitekturi, ki temelji na lahkih akterjih. Njene prilagoditve sem posvetil svetu iOS dve niti v skupnem twitterju in članek na Habréju. V okviru trenutne zgodbe želim poudariti tiste vidike odločitve, ki so vplivali na izbiro baze.​

Akterski model organizacije sistema predpostavlja, da večnitnost postane njegovo drugo bistvo. Modelni objekti v njem radi prestopajo meje niti. In to ne počnejo včasih in ponekod, ampak skoraj nenehno in povsod.

Podatkovna baza je ena od temeljnih komponent v predstavljenem diagramu. Njegova glavna naloga je implementacija makro vzorca Skupna zbirka podatkov. Če se v poslovnem svetu uporablja za organizacijo sinhronizacije podatkov med storitvami, potem v primeru igralske arhitekture podatkov med nitmi. Zato smo potrebovali takšno bazo podatkov, delo s katero v večnitnem okolju ne povzroča niti minimalnih težav. To zlasti pomeni, da morajo biti predmeti, izpeljani iz njega, vsaj varni za niti in v idealnem primeru sploh ne smeti biti spremenljivi. Kot veste, je slednje mogoče uporabiti hkrati iz več niti, ne da bi se zatekli k kakršnim koli ključavnicam, kar ugodno vpliva na zmogljivost.

Drugi pomemben dejavnik, ki je vplival na izbiro baze podatkov, je bil naš oblak API. Navdihnil ga je git pristop k sinhronizaciji. Kot nanj smo ciljali prvi API brez povezave, kar je videti več kot primerno za odjemalce v oblaku. Predpostavljeno je bilo, da bodo samo enkrat izčrpali celotno stanje oblaka, nato pa bi se sinhronizacija v veliki večini primerov zgodila s tekočimi spremembami. Žal je ta možnost še vedno le v teoretični coni, v praksi pa se stranke niso naučile delati s popravki. Za to obstaja vrsta objektivnih razlogov, ki jih bomo, da ne bomo odlašali s predstavitvijo, izpustili iz oklepaja. Zdaj so veliko bolj zanimivi poučni rezultati lekcije o tem, kaj se zgodi, ko API reče "A" in njegov potrošnik ne reče "B".

Torej, če si predstavljate git, ki pri izvajanju ukaza pull namesto popravkov na lokalnem posnetku primerja njegovo polno stanje s polnim strežnikom, potem boste imeli dokaj natančno predstavo o tem, kako poteka sinhronizacija se pojavi v odjemalcih v oblaku. Zlahka je uganiti, da je za njegovo izvedbo potrebno v pomnilniku dodeliti dve drevesi DOM z metainformacijami o vseh strežniških in lokalnih datotekah. Izkazalo se je, da če uporabnik shrani 500 tisoč datotek v oblaku, potem je za njegovo sinhronizacijo potrebno ponovno ustvariti in uničiti dve drevesi z 1 milijonom vozlišč. Toda vsako vozlišče je agregat, ki vsebuje graf podobjektov. V tej luči so bili rezultati profiliranja pričakovani. Izkazalo se je, da tudi brez upoštevanja algoritma spajanja sam postopek ustvarjanja in nato uničenja ogromnega števila majhnih objektov stane precej peni.Položaj poslabša dejstvo, da je osnovna operacija sinhronizacije vključena v veliko število uporabniških skriptov. Posledično popravimo drugo pomembno merilo pri izbiri baze podatkov - zmožnost izvajanja operacij CRUD brez dinamične dodelitve objektov.

Druge zahteve so bolj tradicionalne in njihov celoten seznam je naslednji.

1. Varnost niti.
2. Večprocesiranje. Narekuje ga želja po uporabi istega primerka baze podatkov za sinhronizacijo stanja ne samo med nitmi, temveč tudi med glavno aplikacijo in razširitvami iOS.
3. Sposobnost predstavitve shranjenih entitet kot nespremenljivih objektov.​
4. Pomanjkanje dinamičnih dodelitev znotraj operacij CRUD.
5. Transakcijska podpora za osnovne lastnosti KISLINAKljučne besede: atomičnost, konsistentnost, izolacija in zanesljivost.
6. Hitrost na najbolj priljubljenih primerih.

S tem sklopom zahtev je bil SQLite in je še vedno dobra izbira. Sem pa v okviru proučevanja alternativ naletel na knjigo "Kako začeti z LevelDB". Pod njenim vodstvom je bil napisan benchmark, ki primerja hitrost dela z različnimi bazami podatkov v realnih oblačnih scenarijih. Rezultat je presegel najbolj divja pričakovanja. V najbolj priljubljenih primerih - pridobivanje kazalca na razvrščenem seznamu vseh datotek in razvrščenem seznamu vseh datotek za določen imenik - se je izkazalo, da je LMDB 10-krat hitrejši od SQLite. Izbira je postala očitna.

2. Pozicioniranje LMDB

LMDB je knjižnica, zelo majhna (samo 10K vrstic), ki implementira najnižjo temeljno plast baz podatkov - shranjevanje.

Zgornji diagram kaže, da primerjava LMDB z SQLite, ki izvaja še višje ravni, na splošno ni bolj pravilna kot SQLite z osnovnimi podatki. Bolj pošteno bi bilo navesti iste motorje za shranjevanje kot enakovredne konkurente - BerkeleyDB, LevelDB, Sophia, RocksDB itd. Obstajajo celo dogodki, kjer LMDB deluje kot komponenta mehanizma za shranjevanje za SQLite. Prvi tak poskus leta 2012 porabljeno avtor LMDB Howard Chu. Ugotovitve se je izkazal za tako zanimivega, da so njegovo pobudo prevzeli navdušenci OSS in našli svoje nadaljevanje v obrazu LumoSQL. Januarja 2020 je avtor tega projekta Den Shearer predstavljeno na LinuxConfAu.

Glavna uporaba LMDB je kot motor za baze podatkov aplikacij. Knjižnica svoj videz dolguje razvijalcem OpenLDAP, ki so bili močno nezadovoljni z BerkeleyDB kot osnovo njihovega projekta. Odrivanje od skromne knjižnice btree, je Howard Chu uspel ustvariti eno najbolj priljubljenih alternativ našega časa. Svoje zelo kul poročilo je posvetil tej zgodbi, pa tudi notranji strukturi LMDB. "Baza podatkov, preslikana v spomin Lightning". Leonid Jurijev (aka yleo) iz Positive Technologies v svojem govoru na Highload 2015 "Motor LMDB je poseben prvak". V njem govori o LMDB v kontekstu podobne naloge implementacije ReOpenLDAP, LevelDB pa je bil že deležen primerjalnih kritik. Kot rezultat implementacije je Positive Technologies celo dobil aktivno razvijajočo se vilico MDBX z zelo okusnimi funkcijami, optimizacijami in Popravljene napake.

LMDB se pogosto uporablja tudi kot shramba. Na primer brskalnik Mozilla Firefox izbrala za številne potrebe in, začenši z različico 9, Xcode prednostno svoj SQLite za shranjevanje indeksov.

Motor se je prijel tudi v svetu mobilnega razvoja. Sledi njegove uporabe so lahko je bil v odjemalcu iOS za Telegram. LinkedIn je šel še korak dlje in izbral LMDB kot privzeto shrambo za svoj domači okvir za predpomnjenje podatkov, Rocket Data, o katerem povedal v članku leta 2016.

LMDB se uspešno bori za mesto pod soncem v niši, ki jo je po prehodu pod nadzor Oracle pustil BerkeleyDB. Knjižnica je priljubljena zaradi svoje hitrosti in zanesljivosti, tudi v primerjavi z lastno vrsto. Kot veste, brezplačnih kosil ni in rad bi poudaril kompromis, s katerim se boste morali soočiti pri izbiri med LMDB in SQLite. Zgornji diagram jasno prikazuje, kako se doseže povečana hitrost. Prvič, ne plačujemo za dodatne plasti abstrakcije poleg pomnilnika na disku. Seveda v dobri arhitekturi še vedno ne morete brez njih in se bodo neizogibno pojavili v kodi aplikacije, vendar bodo veliko tanjši. Ne bodo imeli funkcij, ki jih določena aplikacija ne zahteva, na primer podpore za poizvedbe v jeziku SQL. Drugič, postane mogoče optimalno implementirati preslikavo aplikacijskih operacij v zahteve v diskovni prostor. Če SQLite v mojem delu izhaja iz povprečnih potreb povprečne aplikacije, potem se kot razvijalec aplikacije dobro zavedate glavnih scenarijev obremenitve. Za bolj produktivno rešitev boste morali plačati višjo ceno tako za razvoj začetne rešitve kot za njeno kasnejšo podporo.

3. Trije kiti LMDB

Po ogledu LMDB iz ptičje perspektive je čas, da gremo globlje. Naslednji trije razdelki bodo namenjeni analizi glavnih kitov, na katerih sloni arhitektura shranjevanja:

1. Pomnilniško preslikane datoteke kot mehanizem za delo z diskom in sinhronizacijo notranjih podatkovnih struktur.
2. B+-drevo kot organizacija shranjene podatkovne strukture.
3. Copy-on-write kot pristop za zagotavljanje transakcijskih lastnosti ACID in večverzioniranja.

3.1. Kit #1. Datoteke, preslikane v pomnilnik

Datoteke s pomnilniško preslikavo so tako pomemben arhitekturni element, da se pojavijo celo v imenu skladišča. Težave predpomnjenja in sinhronizacije dostopa do shranjenih informacij so v celoti prepuščene na milost in nemilost operacijskemu sistemu. LMDB v sebi ne vsebuje nobenih predpomnilnikov. To je zavestna odločitev avtorja, saj branje podatkov neposredno iz preslikanih datotek omogoča, da zmanjšate veliko ovinkov pri izvajanju motorja. Spodaj je daleč nepopoln seznam nekaterih izmed njih.

1. Ohranjanje konsistentnosti podatkov v pomnilniku pri delu z njimi iz več procesov postane odgovornost operacijskega sistema. V naslednjem razdelku je ta mehanik podrobno obravnavan s slikami.
2. Odsotnost predpomnilnikov popolnoma razbremeni LMDB režijskih stroškov, povezanih z dinamičnimi dodelitvami. Branje podatkov je v praksi nastavitev kazalca na pravi naslov v virtualnem pomnilniku in nič več. Sliši se kot domišljija, toda v viru repozitorija so vsi klici calloc skoncentrirani v konfiguracijski funkciji repozitorija.
3. Odsotnost predpomnilnikov pomeni tudi odsotnost ključavnic, povezanih s sinhronizacijo za dostop do njih. Čitalniki, ki jih lahko hkrati obstaja poljubno število, na poti do podatkov ne srečajo niti enega muteksa. Zaradi tega ima hitrost branja idealno linearno razširljivost glede na število procesorjev. V LMDB so sinhronizirane samo operacije spreminjanja. Naenkrat je lahko samo en pisec.
4. Minimalna logika predpomnjenja in sinhronizacije reši kodo pred izjemno zapleteno vrsto napak, povezanih z delom v večnitnem okolju. Na konferenci Usenix OSDI 2014 sta bili zanimivi dve študiji baz podatkov: "Vsi datotečni sistemi niso ustvarjeni enaki: o kompleksnosti izdelave aplikacij, ki so skladne z zrušitvijo" и Mučenje baz podatkov za zabavo in dobiček. Od njih lahko dobite informacije tako o izjemni zanesljivosti LMDB kot o skoraj brezhibni implementaciji lastnosti ACID transakcij, ki jo presega v istem SQLite.
5. Minimalizem LMDB omogoča, da se strojna predstavitev njegove kode v celoti postavi v predpomnilnik L1 procesorja s posledičnimi hitrostnimi značilnostmi.

Na žalost v iOS-u pomnilniško preslikane datoteke niso tako rožnate, kot bi si želeli. Če želite bolj zavestno govoriti o pomanjkljivostih, povezanih z njimi, se je treba spomniti splošnih načel za izvajanje tega mehanizma v operacijskih sistemih.

Splošne informacije o pomnilniško preslikanih datotekah

Z vsako izvedljivo aplikacijo operacijski sistem poveže entiteto, imenovano proces. Vsakemu procesu je dodeljen sosednji obseg naslovov, v katerega postavi vse, kar potrebuje za delovanje. Najnižji naslovi vsebujejo razdelke s kodo in trdo kodiranimi podatki in viri. Sledi navzgor rastoči blok dinamičnega naslovnega prostora, ki nam je dobro znan kot kup. Vsebuje naslove entitet, ki se pojavljajo med delovanjem programa. Na vrhu je območje pomnilnika, ki ga uporablja sklad aplikacij. Ali raste ali se krči, z drugimi besedami, njegova velikost ima tudi dinamično naravo. Da se sklad in kopica ne potiskata in ne motita drug drugega, sta ločena na različnih koncih naslovnega prostora.Med dvema dinamičnima deloma na vrhu in na dnu je luknja. Naslove v tem srednjem delu operacijski sistem uporablja za povezavo s procesom različnih entitet. Zlasti lahko preslika določen neprekinjen nabor naslovov v datoteko na disku. Takšna datoteka se imenuje pomnilniško preslikana datoteka.​

Naslovni prostor, dodeljen procesu, je ogromen. Teoretično je število naslovov omejeno le z velikostjo kazalca, ki je določena z bitno globino sistema. Če bi mu fizični pomnilnik dodelili 1-v-1, bi prvi proces požrl celoten RAM in ne bi bilo govora o večopravilnosti.​

​Iz izkušenj pa vemo, da lahko sodobni operacijski sistemi izvajajo toliko procesov, kot želite hkrati. To je mogoče zaradi dejstva, da procesom dodelijo veliko pomnilnika le na papirju, v resnici pa v glavni fizični pomnilnik naložijo le tisti del, ki je potreben tukaj in zdaj. Zato se pomnilnik, povezan s procesom, imenuje navidezni.

Operacijski sistem organizira virtualni in fizični pomnilnik v strani določene velikosti. Takoj ko je zahtevana določena stran navideznega pomnilnika, jo operacijski sistem naloži v fizični pomnilnik in v posebno tabelo zapiše korespondenco med njimi. Če ni prostih mest, se ena od predhodno naloženih strani prekopira na disk in zahtevana prevzame njeno mesto. Ta postopek, ki se mu bomo kmalu vrnili, se imenuje zamenjava. Spodnja slika prikazuje opisani postopek. Na njej je bila stran A z naslovom 0 naložena in postavljena na glavno pomnilniško stran z naslovom 4. To dejstvo se je odrazilo v korespondenčni tabeli v celici številka 0.​

Pri pomnilniško preslikanih datotekah je zgodba popolnoma enaka. Logično naj bi bili neprekinjeno in v celoti umeščeni v virtualni naslovni prostor. Vendar pridejo v fizični pomnilnik stran za stranjo in le na zahtevo. Spreminjanje takih strani je sinhronizirano z datoteko na disku. Tako lahko izvedete I/O datoteke, preprosto delate z bajti v pomnilniku - vse spremembe bo jedro operacijskega sistema samodejno preneslo v izvirno datoteko.​
​,war
Spodnja slika prikazuje, kako LMDB sinhronizira svoje stanje pri delu z bazo podatkov iz različnih procesov. S preslikavo navideznega pomnilnika različnih procesov v isto datoteko de facto prisilimo operacijski sistem, da tranzitivno sinhronizira določene bloke njihovih naslovnih prostorov med seboj, kar je videti v LMDB.​
​,war

Pomemben odtenek je, da LMDB privzeto spremeni podatkovno datoteko prek mehanizma sistemskega klica pisanja, sama datoteka pa se prikaže v načinu samo za branje. Ta pristop ima dve pomembni posledici.

Prva posledica je skupna vsem operacijskim sistemom. Njegovo bistvo je dodati zaščito pred nenamerno poškodbo podatkovne baze z napačno kodo. Kot veste, lahko izvršljiva navodila procesa prosto dostopajo do podatkov od koder koli v njegovem naslovnem prostoru. Obenem, kot smo se pravkar spomnili, prikaz datoteke v načinu branja in pisanja pomeni, da jo lahko katero koli navodilo tudi dodatno spremeni. Če to stori po pomoti, ko poskuša na primer dejansko prepisati element polja na neobstoječem indeksu, potem lahko na ta način pomotoma spremeni datoteko, preslikano na ta naslov, kar bo povzročilo poškodbo baze podatkov. Če je datoteka prikazana v načinu samo za branje, bo poskus spremembe naslovnega prostora, ki ji ustreza, povzročil zrušitev programa s signalom SIGSEGVin datoteka bo ostala nedotaknjena.

Druga posledica je že specifična za iOS. Niti avtor niti noben drug vir ga izrecno ne omenja, a brez njega LMDB ne bi bil primeren za delovanje v tem mobilnem operacijskem sistemu. Naslednji razdelek je posvečen njegovi obravnavi.

Posebnosti pomnilniško preslikanih datotek v sistemu iOS

Leta 2018 je bilo na WWDC čudovito poročilo iOS Memory Deep Dive. Pove, da v sistemu iOS vse strani v fizičnem pomnilniku pripadajo eni od treh vrst: umazane, stisnjene in čiste.

Čisti pomnilnik je zbirka strani, ki jih je mogoče varno zamenjati iz fizičnega pomnilnika. Podatke, ki jih vsebujejo, je mogoče po potrebi znova naložiti iz izvirnih virov. Datoteke, preslikane v pomnilnik samo za branje, spadajo v to kategorijo. iOS se ne boji kadar koli odstraniti strani, preslikanih v datoteko, iz pomnilnika, saj je zagotovljeno, da so sinhronizirane z datoteko na disku.
​,war
Vse spremenjene strani pridejo v umazan pomnilnik, ne glede na to, kje se prvotno nahajajo. Zlasti pomnilniško preslikane datoteke, spremenjene s pisanjem v navidezni pomnilnik, povezan z njimi, bodo prav tako razvrščene na ta način. Odpiranje LMDB z zastavico MDB_WRITEMAP, potem ko ga spremenite, se lahko prepričate sami.​

​Takoj ko aplikacija začne zavzemati preveč fizičnega pomnilnika, iOS stisne svoje umazane strani. Zbirka pomnilnika, ki ga zasedajo umazane in stisnjene strani, je tako imenovani pomnilniški odtis aplikacije. Ko doseže določeno vrednost praga, sistemski demon OOM killer pride za procesom in ga prisilno prekine. To je posebnost iOS-a v primerjavi z namiznimi operacijskimi sistemi. Nasprotno pa zmanjševanje pomnilniškega odtisa z zamenjavo strani iz fizičnega pomnilnika na disk ni zagotovljeno v iOS-u. O razlogih lahko le ugibamo. Morda je postopek intenzivnega premikanja strani na disk in nazaj preveč energijsko potraten za mobilne naprave, ali iOS prihrani vir prepisovanja celic na SSD diske, ali pa načrtovalci niso bili zadovoljni s celotno zmogljivostjo sistema, kjer je vse nenehno menjavajo. Kakor koli že, dejstvo ostaja.

Dobra novica, omenjena že prej, je, da LMDB privzeto ne uporablja mehanizma mmap za posodabljanje datotek. Iz tega sledi, da iOS upodobljene podatke razvrsti kot čisti pomnilnik in ne prispevajo k odtisu pomnilnika. To je mogoče preveriti z orodjem Xcode, imenovanim VM Tracker. Spodnji posnetek zaslona prikazuje stanje navideznega pomnilnika aplikacije iOS Cloud med delovanjem. Na začetku sta bila v njem inicializirana 2 primerka LMDB. Prvemu je bilo dovoljeno preslikati svojo datoteko v 1GiB navideznega pomnilnika, drugemu - 512MiB. Kljub temu, da oba pomnilnika zasedata določeno količino rezidenčnega pomnilnika, nobeden od njiju ne prispeva k umazani velikosti.

Zdaj je čas za slabo novico. Zahvaljujoč mehanizmu zamenjave v 64-bitnih namiznih operacijskih sistemih lahko vsak proces zasede toliko navideznega naslovnega prostora, kolikor prosti prostor na trdem disku omogoča njegovo morebitno zamenjavo. Zamenjava swapa s stiskanjem v iOS-u drastično zmanjša teoretični maksimum. Zdaj se morajo vsi živi procesi prilegati v glavni (beri RAM) pomnilnik, vsi tisti, ki se ne prilegajo, pa so predmet prisilne prekinitve. Omenjeno je kot zgoraj poročilo, in v uradna dokumentacija. Posledično iOS močno omejuje količino pomnilnika, ki je na voljo za dodelitev prek mmap. Tukaj tukaj si lahko ogledate empirične omejitve količine pomnilnika, ki bi ga lahko dodelili različnim napravam s tem sistemskim klicem. Na najsodobnejših modelih pametnih telefonov je iOS postal radodaren za 2 gigabajta, na vrhunskih različicah iPada pa za 4. V praksi se morate seveda osredotočiti na najmlajše podprte modele naprav, kjer je vse zelo žalostno. Še huje, če pogledate stanje pomnilnika aplikacije v VM Trackerju, boste ugotovili, da LMDB še zdaleč ni edini, ki zahteva pomnilniško preslikan pomnilnik. Dobre dele pojedo sistemski alokatorji, datoteke virov, okviri slik in drugi manjši plenilci.

Kot rezultat poskusov v oblaku smo prišli do naslednjih kompromisnih vrednosti pomnilnika, ki ga dodeli LMDB: 384 megabajtov za 32-bitne naprave in 768 za 64-bitne. Ko je ta prostornina porabljena, se vse operacije spreminjanja začnejo dokončati s kodo MDB_MAP_FULL. Takšne napake opazimo pri našem spremljanju, vendar so dovolj majhne, ​​da jih na tej stopnji zanemarimo.

Neočiten razlog za čezmerno porabo pomnilnika s shranjevanjem so lahko dolgotrajne transakcije. Da bi razumeli, kako sta ta dva pojava povezana, nam bo pomagalo razmisliti o preostalih dveh kitih LMDB.

3.2. Kit #2. B+-drevo

Za posnemanje tabel na vrhu shrambe ključ-vrednost morajo biti v API-ju prisotne naslednje operacije:

1. Vstavljanje novega elementa.
2. Poiščite element z danim ključem.
3. Brisanje elementa.
4. Ponovite ključne intervale v njihovem vrstnem redu.

Najenostavnejša podatkovna struktura, ki zlahka izvaja vse štiri operacije, je binarno iskalno drevo. Vsako njegovo vozlišče je ključ, ki celotno podmnožico podrejenih ključev razdeli na dve poddrevesi. Na levi so tisti, ki so manjši od staršev, na desni pa tisti, ki so večji. Pridobitev urejenega nabora ključev se doseže z enim od klasičnih prehodov drevesa.​

Binarna drevesa imajo dve temeljni pomanjkljivosti, ki jim preprečujeta, da bi bila učinkovita kot podatkovna struktura diska. Prvič, stopnja njihovega ravnovesja je nepredvidljiva. Obstaja precejšnje tveganje, da dobimo drevesa, pri katerih se višina različnih vej lahko zelo razlikuje, kar bistveno poslabša algoritemsko zahtevnost iskanja v primerjavi s pričakovano. Drugič, obilica navzkrižnih povezav med vozlišči odvzema binarnim drevesom lokalnost v pomnilniku.Bližnja vozlišča (v smislu povezav med njimi) se lahko nahajajo na popolnoma različnih straneh v virtualnem pomnilniku. Posledično lahko celo preprosto prečkanje več sosednjih vozlišč v drevesu zahteva obisk primerljivega števila strani. To je problem tudi, ko govorimo o učinkovitosti binarnih dreves kot podatkovne strukture v pomnilniku, saj nenehno kroženje strani v predpomnilniku procesorja ni poceni. Ko gre za pogosto dvigovanje strani, povezanih z vozlišči, z diska, postanejo stvari zelo slabe. obžalovanja vredno.

B-drevesa, ki so evolucija binarnih dreves, rešujejo težave, opredeljene v prejšnjem odstavku. Prvič, sami se uravnotežijo. Drugič, vsako od njihovih vozlišč razdeli niz podrejenih ključev ne na 2, ampak na M urejenih podmnožic, število M pa je lahko precej veliko, reda velikosti nekaj sto ali celo tisoč.

S tem:

1. Vsako vozlišče ima veliko število že naročenih ključev in drevesa so zelo nizka.
2. Drevo pridobi lastnost lokalnosti v pomnilniku, saj so ključi, ki so blizu vrednosti, naravno nameščeni drug poleg drugega na enem ali sosednjih vozliščih.
3. Zmanjša število tranzitnih vozlišč pri spuščanju po drevesu med operacijo iskanja.
4. Zmanjša število prebranih ciljnih vozlišč za poizvedbe obsega, saj vsako od njih že vsebuje veliko število urejenih ključev.

LMDB za shranjevanje podatkov uporablja različico drevesa B, imenovano drevo B+. Zgornji diagram prikazuje tri vrste vozlišč, ki jih vsebuje:

1. Na vrhu je koren. Materializira nič drugega kot koncept baze podatkov v skladišču. Znotraj enega primerka LMDB lahko ustvarite več baz podatkov, ki si delijo preslikani virtualni naslovni prostor. Vsak od njih izhaja iz svoje korenine.
2. Na najnižji ravni so listi (list). Samo oni in samo oni vsebujejo pare ključ-vrednost, shranjene v bazi podatkov. Mimogrede, to je posebnost B+-dreves. Če normalno B-drevo shrani dele vrednosti na vozliščih vseh ravni, potem je B+-variacija le na najnižji. Ko smo to dejstvo odpravili, bomo v nadaljevanju podtip drevesa, uporabljenega v LMDB, imenovali preprosto B-drevo.
3. Med korenom in listi je 0 ali več tehničnih ravni z navigacijskimi (vejnimi) vozlišči. Njihova naloga je razdeliti razvrščeni niz ključev med liste.

Fizično so vozlišča bloki pomnilnika vnaprej določene dolžine. Njihova velikost je večkratnik velikosti pomnilniških strani v operacijskem sistemu, o katerih smo govorili zgoraj. Struktura vozlišča je prikazana spodaj. Glava vsebuje metainformacije, med katerimi je najbolj očitna na primer kontrolna vsota. Sledijo informacije o odmikih, vzdolž katerih se nahajajo celice s podatki. Vloga podatkov so lahko bodisi ključi, če govorimo o navigacijskih vozliščih, bodisi celotni pari ključ-vrednost v primeru listov.Več o strukturi strani si lahko preberete v delu "Vrednotenje visoko zmogljivih shramb ključ-vrednost".

Ko smo obravnavali notranjo vsebino vozlišč strani, bomo B-drevo LMDB nadalje predstavili na poenostavljen način v naslednji obliki.

Strani z vozlišči so na disku razvrščene zaporedno. Strani z višjo številko se nahajajo proti koncu datoteke. Tako imenovana meta stran (meta stran) vsebuje podatke o odmikih, s pomočjo katerih lahko poiščemo korenine vseh dreves. Ko je datoteka odprta, LMDB pregleda datoteko stran za stranjo od konca do začetka v iskanju veljavne meta strani in prek nje najde obstoječe baze podatkov.​

Zdaj, ko imamo idejo o logični in fizični strukturi organizacije podatkov, lahko nadaljujemo z obravnavo tretjega kita LMDB. Z njegovo pomočjo se vse spremembe shranjevanja dogajajo transakcijsko in ločeno druga od druge, kar daje bazi podatkov kot celoti tudi lastnost večrazličnosti.

3.3. Kit #3. kopiranje ob pisanju

Nekatere operacije B-drevesa vključujejo izvedbo cele vrste sprememb v njegovih vozliščih. En primer je dodajanje novega ključa vozlišču, ki je že doseglo največjo zmogljivost. V tem primeru je treba vozlišče najprej razdeliti na dva dela, nato pa dodati povezavo do novega odcepljenega podrejenega vozlišča v njegovem nadrejenem vozlišču. Ta postopek je potencialno zelo nevaren. Če se iz nekega razloga (zrušitev, izpad elektrike itd.) zgodi le del sprememb iz serije, bo drevo ostalo v nekonsistentnem stanju.

Ena od tradicionalnih rešitev za izdelavo zbirke podatkov, odporne na napake, je dodajanje dodatne podatkovne strukture na disku, dnevnika transakcij, znanega tudi kot dnevnik vnaprejšnjega pisanja (WAL), poleg drevesa B. Gre za datoteko, na koncu katere je strogo pred spremembo samega B-drevesa zapisana predvidena operacija. Če je torej med samodiagnozo zaznana poškodba podatkov, baza podatkov pregleda dnevnik, da se sama počisti.

LMDB je kot mehanizem za toleranco napak izbral drugačno metodo, ki se imenuje kopiranje ob pisanju. Njegovo bistvo je, da namesto posodobitve podatkov na obstoječi strani le-to najprej v celoti skopira in naredi vse spremembe že v kopiji.​

Nadalje, da bi bili posodobljeni podatki na voljo, je treba spremeniti povezavo do vozlišča, ki je postalo posodobljeno v nadrejenem vozlišču v zvezi z njim. Ker ga je za to treba tudi modificirati, je tudi predkopiran. Postopek se nadaljuje rekurzivno vse do korena. Podatki na meta strani se spremenijo zadnji.​​

Če se proces med postopkom posodabljanja nenadoma zruši, nova meta stran ne bo ustvarjena ali pa ne bo zapisana na disk do konca in njena kontrolna vsota bo napačna. V katerem koli od teh dveh primerov bodo nove strani nedosegljive, stare pa ne bodo prizadete. To odpravlja potrebo po vnaprejšnjem pisanju dnevnika LMDB za ohranjanje doslednosti podatkov. Zgoraj opisana struktura shranjevanja podatkov na disku de facto hkrati prevzame svojo funkcijo. Odsotnost eksplicitnega dnevnika transakcij je ena od značilnosti LMDB, ki zagotavlja visoko hitrost branja podatkov.​

Nastala konstrukcija, imenovana B-drevo samo za dodajanje, seveda zagotavlja izolacijo transakcij in večrazličico. V LMDB je vsaka odprta transakcija povezana s posodobljenim drevesnim korenom. Dokler transakcija ni dokončana, strani drevesa, povezane z njo, ne bodo nikoli spremenjene ali ponovno uporabljene za nove različice podatkov. Tako lahko delate, kolikor želite točno z naborom podatkov, ki je bil relevanten pri čas, ko je bila transakcija odprta, tudi če se shramba v tem času še naprej aktivno posodablja. To je bistvo multiverzioniranja, zaradi česar je LMDB idealen vir podatkov za naše ljubljene UICollectionView. Ko odprete transakcijo, vam ni treba povečati pomnilniškega odtisa aplikacije, naglo črpati trenutne podatke v neko strukturo v pomnilniku, saj se bojite, da boste ostali brez ničesar. Ta funkcija razlikuje LMDB od istega SQLite, ki se ne more pohvaliti s tako popolno izolacijo. Ob odprtju dveh transakcij v slednji in brisanju določenega zapisa v eni od njiju, istega zapisa ni več mogoče pridobiti v drugi preostali.

​Druga stran kovanca je potencialno znatno večja poraba virtualnega pomnilnika. Diapozitiv prikazuje, kako bo izgledala struktura baze podatkov, če jo spremenimo hkrati s 3 odprtimi transakcijami branja, ki gledajo na različne različice baze podatkov. Ker LMDB ne more ponovno uporabiti vozlišč, ki so dosegljiva iz korenin, povezanih z dejanskimi transakcijami, shramba nima druge izbire, kot da dodeli še en četrti koren v pomnilniku in znova klonira spremenjene strani pod njim.

Tukaj ne bo odveč, če se spomnimo razdelka o pomnilniško preslikanih datotekah. Zdi se, da nas dodatna poraba navideznega pomnilnika ne bi smela kaj dosti motiti, saj ne prispeva k pomnilniškemu odtisu aplikacije. Vendar pa je bilo hkrati ugotovljeno, da je iOS zelo škrt pri njegovem dodeljevanju in ne moremo zagotoviti 1 terabajtne regije LMDB na strežniku ali namizju z glavnega ramena in sploh ne razmišljati o tej funkciji. Kadar je mogoče, poskusite ohraniti življenjsko dobo transakcij čim krajšo.

4. Oblikovanje podatkovne sheme na vrhu API-ja ključ-vrednost

Začnimo razčlenjevati API z ogledom osnovnih abstrakcij, ki jih ponuja LMDB: okolje in baze podatkov, ključi in vrednosti, transakcije in kazalci.

Opomba o seznamih kod

Vse funkcije v javnem API-ju LMDB vrnejo rezultat svojega dela v obliki kode napake, vendar je v vseh nadaljnjih seznamih njeno preverjanje zaradi jedrnatosti izpuščeno.V praksi smo za interakcijo z repozitorijem uporabili lastno kodo. vilice Ovoji C++ lmdbxx, pri katerem se napake materializirajo kot izjeme C++.

Kot najhitrejši način za povezavo LMDB s projektom iOS ali macOS ponujam svoj CocoaPod POSLMDB.

4.1. Osnovne abstrakcije

okolje

Struktura MDB_env je repozitorij notranjega stanja LMDB. Družina predponskih funkcij mdb_env vam omogoča, da konfigurirate nekatere njegove lastnosti. V najpreprostejšem primeru je inicializacija motorja videti takole.

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

V aplikaciji Mail.ru Cloud smo spremenili privzete vrednosti samo za dva parametra.

Prva je velikost navideznega naslovnega prostora, v katerega je preslikana datoteka za shranjevanje. Na žalost se lahko tudi na isti napravi specifična vrednost močno razlikuje od postopka do postopka. Da bi upoštevali to funkcijo iOS-a, dinamično izberemo največjo količino prostora za shranjevanje. Od določene vrednosti se zaporedoma razpolovi do funkcije mdb_env_open ne bo vrnil drugega rezultata kot ENOMEM. V teoriji obstaja nasprotni način - najprej dodelite motorju najmanj pomnilnika in nato, ko prejmete napake MDB_MAP_FULL, povečajte. Je pa precej bolj trnova. Razlog je v tem, da postopek za ponovno preslikavo pomnilnika s funkcijo mdb_env_set_map_size razveljavi vse entitete (kurzorje, transakcije, ključe in vrednosti), prej prejete od mehanizma. Obračunavanje takšnega obrata dogodkov v kodi bo privedlo do njegovega znatnega zapleta. Če vam je kljub temu virtualni pomnilnik zelo drag, potem je to morda razlog, da pogledate vilice, ki so šle daleč naprej. MDBX, kjer je med deklariranimi lastnostmi tudi »samodejna sprotna prilagoditev velikosti baze podatkov«.

Drugi parameter, katerega privzeta vrednost nam ni ustrezala, ureja mehaniko zagotavljanja varnosti niti. Na žalost, vsaj v iOS 10, obstajajo težave s podporo za lokalno shranjevanje niti. Zaradi tega se v zgornjem primeru skladišče odpre z zastavico MDB_NOTLS. Poleg tega je zahteval tudi vilice C++ ovoj lmdbxxza rezanje spremenljivk z in v tem atributu.

Baze podatkov

Baza podatkov je ločen primerek B-drevesa, o katerem smo govorili zgoraj. Njegovo odpiranje se zgodi znotraj transakcije, kar se na prvi pogled morda zdi nekoliko nenavadno.

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

Dejansko je transakcija v LMDB entiteta za shranjevanje in ne posebna baza podatkov. Ta koncept vam omogoča izvajanje atomskih operacij na entitetah, ki se nahajajo v različnih zbirkah podatkov. Teoretično to odpira možnost modeliranja tabel v obliki različnih podatkovnih baz, vendar sem nekoč šel v drugo smer, ki je podrobno opisana v nadaljevanju.

Ključi in vrednosti

Struktura MDB_val modelira koncept ključa in vrednosti. Repozitorij nima pojma o njihovi semantiki. Zanjo je nekaj, kar je drugačno, le niz bajtov določene velikosti. Največja velikost ključa je 512 bajtov.

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

Trgovina uporablja primerjalnik za razvrščanje ključev v naraščajočem vrstnem redu. Če ga ne zamenjate s svojim, bo uporabljen privzeti, ki jih razvrsti bajt za bajtom v leksikografskem vrstnem redu.​

Posel

Transakcijska naprava je podrobno opisana v prejšnje poglavje, zato bom tukaj v kratkem ponovil njihove glavne lastnosti:

1. Podpora za vse osnovne lastnosti KISLINAKljučne besede: atomičnost, konsistentnost, izolacija in zanesljivost. Ne morem si kaj, da ne bi omenil, da je v zvezi z vzdržljivostjo v sistemih macOS in iOS v MDBX odpravljena napaka. Več si lahko preberete v njihovi README.
2. Pristop k večnitnosti je opisan s shemo "en pisec / več bralcev". Pisatelji blokirajo drug drugega, ne blokirajo pa bralcev. Bralci ne blokirajo piscev ali drug drugega.
3. Podpora za ugnezdene transakcije.
4. Podpora za več različic.

Multiverzioniranje v LMDB je tako dobro, da ga želim pokazati v akciji. Spodnja koda prikazuje, da vsaka transakcija deluje natanko s tisto različico baze podatkov, ki je bila relevantna v času njenega odprtja, in je popolnoma izolirana od vseh kasnejših sprememb. Inicializacija repozitorija in dodajanje testnega zapisa vanj ni zanimiva, zato so ti rituali ostali pod spojlerjem.

Dodajanje testnega vnosa

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 želji priporočam, da poskusite isti trik s SQLite in poglejte, kaj se zgodi.

Multiversioning prinaša zelo lepe prednosti v življenju razvijalca za iOS. Z uporabo te lastnosti lahko preprosto in naravno prilagodite hitrost posodabljanja podatkovnega vira za zaslonske obrazce na podlagi premislekov o uporabniški izkušnji. Za primer vzemimo takšno funkcijo aplikacije Mail.ru Cloud, kot je samodejno nalaganje vsebine iz sistemske medijske galerije. Z dobro povezavo lahko odjemalec na strežnik doda več fotografij na sekundo. Če posodobite po vsakem prenosu UICollectionView z medijsko vsebino v uporabnikovem oblaku lahko pozabite na 60 sličic na sekundo in gladko drsenje med tem postopkom. Če želite preprečiti pogoste posodobitve zaslona, ​​​​morate nekako omejiti hitrost spreminjanja podatkov v osnovi UICollectionViewDataSource.

Če zbirka podatkov ne podpira večrazličičnega delovanja in vam omogoča delo samo s trenutnim trenutnim stanjem, ga morate za ustvarjanje časovno stabilnega posnetka podatkov kopirati v neko podatkovno strukturo v pomnilniku ali v začasno tabelo. Vsak od teh pristopov je zelo drag. V primeru shranjevanja v pomnilniku dobimo tako stroške pomnilnika, ki jih povzroči shranjevanje konstruiranih objektov, kot tudi časovne stroške, povezane z redundantnimi transformacijami ORM. Kar zadeva začasno mizo, je to še dražji užitek, ki je smiseln le v nepomembnih primerih.

Multiversioning LMDB rešuje problem vzdrževanja stabilnega vira podatkov na zelo eleganten način. Dovolj je le odpreti transakcijo in voila – dokler je ne zaključimo, je nabor podatkov zagotovljeno popravljen. Logika hitrosti posodabljanja je zdaj v celoti v rokah predstavitvenega sloja, brez dodatnih stroškov pomembnih virov.

Kazalci

Kazalci zagotavljajo mehanizem za urejeno ponavljanje parov ključ-vrednost s prečkanjem drevesa B. Brez njih bi bilo nemogoče učinkovito modelirati tabele v podatkovni zbirki, ki jo zdaj obravnavamo.

4.2. Modeliranje miz

Lastnost vrstnega reda ključev vam omogoča, da zgradite abstrakcijo najvišje ravni, kot je tabela na vrhu osnovnih abstrakcij. Oglejmo si ta postopek na primeru glavne tabele odjemalca v oblaku, v kateri so predpomnjeni podatki o vseh datotekah in mapah uporabnika.

Shema tabele

Eden od pogostih scenarijev, za katerega je treba izostriti strukturo tabele z drevesom map, je izbira vseh elementov, ki se nahajajo znotraj danega imenika. Dober model organizacije podatkov za učinkovite tovrstne poizvedbe je Seznam sosednosti. Če ga želite implementirati na vrhu shrambe ključ-vrednost, je treba razvrstiti ključe datotek in map tako, da so razvrščeni glede na pripadnost nadrejenemu imeniku. Poleg tega je treba za prikaz vsebine imenika v obliki, ki jo pozna uporabnik Windows (najprej mape, nato datoteke, oboje je razvrščeno po abecedi), v ključ vključiti ustrezna dodatna polja.

​Spodnja slika prikazuje, kako lahko glede na nalogo izgleda predstavitev ključev kot niza bajtov. Najprej so postavljeni bajti z identifikatorjem nadrejenega imenika (rdeče), nato z vrsto (zeleno) in že v repu z imenom (modro).Ker so razvrščeni s privzetim primerjalnikom LMDB v leksikografskem vrstnem redu, so razvrščeni v zahtevani način. Zaporedno prečkanje tipk z isto rdečo predpono nam daje vrednosti, povezane z njimi, v vrstnem redu, v katerem naj bi bile prikazane v uporabniškem vmesniku (desno), ne da bi zahtevali kakršno koli dodatno naknadno obdelavo.

Serializiranje ključev in vrednosti

Obstaja veliko metod za serializacijo objektov po vsem svetu. Ker razen hitrosti nismo imeli nobene druge zahteve, smo zase izbrali najhitrejšo možno - izpis pomnilnika, ki ga zaseda primerek strukture jezika C. Torej je ključ elementa imenika mogoče modelirati z naslednjo strukturo: NodeKey.

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

Shraniti NodeKey v skladišču potrebujejo predmet MDB_val postavite kazalec na podatke na naslov začetka strukture in s funkcijo izračunajte njihovo velikost sizeof.

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

V prvem poglavju o kriterijih izbire baze podatkov sem omenil minimiziranje dinamičnih dodelitev kot del operacij CRUD kot pomemben dejavnik izbire. Koda funkcije serialize prikazuje, kako se jim je v primeru LMDB mogoče popolnoma izogniti, ko v bazo podatkov vnesemo nove zapise. Dohodni niz bajtov iz strežnika se najprej pretvori v strukture skladov, nato pa se trivialno vržejo v shrambo. Glede na to, da znotraj LMDB tudi ni dinamičnih dodelitev, lahko dobite fantastično situacijo po standardih iOS-a - uporabite samo skladovni pomnilnik za delo s podatki vse od omrežja do diska!

Naročanje ključev z binarnim primerjalnikom

Relacija ključnega reda je podana s posebno funkcijo, imenovano primerjalnik. Ker motor ne ve ničesar o semantiki bajtov, ki jih vsebujejo, privzeti primerjalnik nima druge izbire, kot da razporedi ključe v leksikografskem vrstnem redu in se zateče k njihovi primerjavi bajt za bajtom. Njegova uporaba za urejanje struktur je podobna britju s sekiro. Vendar se mi zdi ta metoda v preprostih primerih sprejemljiva. Druga možnost je opisana spodaj, tukaj pa bom opazil nekaj grabljic, raztresenih ob poti.

Prva stvar, ki jo morate upoštevati, je pomnilniška predstavitev primitivnih tipov podatkov. Torej so na vseh napravah Apple celoštevilske spremenljivke shranjene v formatu Mali Endian. To pomeni, da bo najmanj pomemben bajt na levi strani in ne boste mogli razvrstiti celih števil z njihovo primerjavo bajt za bajtom. Če na primer poskusite to narediti z nizom števil od 0 do 511, boste dobili naslednji rezultat.

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

Da bi rešili to težavo, morajo biti cela števila shranjena v ključu v obliki, primerni za bajtni primerjalnik. Funkcije iz družine bodo pomagale izvesti potrebno preobrazbo. hton* (še posebej htons za dvobajtna števila iz primera).

Format za predstavitev nizov v programiranju je, kot veste, celota Zgodovina. Če semantika nizov, kot tudi kodiranje, ki se uporablja za njihovo predstavitev v pomnilniku, nakazuje, da je morda več kot en bajt na znak, potem je bolje takoj opustiti zamisel o uporabi privzetega primerjalnika.

Druga stvar, ki jo morate upoštevati, je načela poravnave prevajalnik polja struct. Zaradi njih se lahko v pomnilniku med polji oblikujejo bajti z vrednostmi smeti, kar seveda prekine razvrščanje bajtov. Če želite odstraniti smeti, morate bodisi prijaviti polja v strogo določenem vrstnem redu, pri tem pa upoštevati pravila poravnave, ali uporabiti atribut v deklaraciji strukture packed.

Urejanje ključev z zunanjim primerjalnikom

Ključna primerjalna logika se lahko izkaže za preveč zapleteno za binarni primerjalnik. Eden od mnogih razlogov je prisotnost tehničnih področij znotraj struktur. Njihovo pojavljanje bom ilustriral na primeru nam že poznanega ključa za element imenika.

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

Kljub vsej svoji enostavnosti v veliki večini primerov porabi preveč pomnilnika. Naslovni medpomnilnik je 256 bajtov, čeprav imena datotek in map v povprečju redko presegajo 20-30 znakov.

​Ena od standardnih tehnik za optimizacijo velikosti zapisa je, da ga "obrežete", da ustreza dejanski velikosti. Njegovo bistvo je, da so vsebine vseh polj spremenljive dolžine shranjene v medpomnilniku na koncu strukture, njihove dolžine pa so shranjene v ločenih spremenljivkah.V skladu s tem pristopom je ključ NodeKey se preoblikuje na naslednji način.

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

Poleg tega med serializacijo ni podana kot velikost podatkov sizeof celotno strukturo, velikost vseh polj pa je fiksna dolžina plus velikost dejansko uporabljenega dela medpomnilnika.

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

Kot rezultat refactoringa smo dosegli znatne prihranke na prostoru, ki ga zasedajo tipke. Vendar zaradi tehničnega področja nameLength, privzeti binarni primerjalnik ni več primeren za ključno primerjavo. Če ga ne zamenjamo s svojim, potem bo dolžina imena pri razvrščanju bolj prednostna kot ime samo.

LMDB omogoča, da ima vsaka zbirka podatkov lastno funkcijo primerjave ključev. To se naredi s funkcijo mdb_set_compare strogo pred odprtjem. Iz očitnih razlogov podatkovne baze ni mogoče spreminjati v njeni življenjski dobi. Primerjalnik na vhodu prejme dva ključa v binarni obliki, na izhodu pa vrne rezultat primerjave: manj kot (-1), več kot (1) ali enako (0). Psevdokoda 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 // ...
}​

Dokler so vsi ključi v zbirki podatkov istega tipa, je zakonito brezpogojno pretvoriti njihovo bajtno predstavitev v vrsto strukture aplikacije ključa. Tukaj je en odtenek, vendar bo o tem razpravljal nekoliko nižje v pododdelku »Zapisi o branju«.

Serializacija vrednosti

S ključi shranjenih zapisov LMDB deluje izjemno intenzivno. Med seboj se primerjajo v okviru delovanja katere koli aplikacije, od hitrosti primerjalnika pa je odvisna zmogljivost celotne rešitve. V idealnem svetu bi moral privzeti binarni primerjalnik zadostovati za primerjavo ključev, a če bi res morali uporabiti svojega, bi moral biti postopek deserializacije ključev v njem čim hitrejši.

Baza podatkov se ne zanima posebej za Value-del zapisa (vrednost). Njegova pretvorba iz bajtne predstavitve v objekt se zgodi le, ko to že zahteva koda aplikacije, na primer, da se prikaže na zaslonu. Ker se to zgodi razmeroma redko, zahteve po hitrosti tega postopka niso tako kritične, pri njegovem izvajanju pa se lahko veliko bolj svobodno osredotočimo na udobje.Na primer, za serializacijo metapodatkov o datotekah, ki še niso bile prenesene, uporabljamo NSKeyedArchiver.

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

Vendar so časi, ko je uspešnost pomembna. Na primer, ko shranjujemo metainformacije o datotečni strukturi uporabniškega oblaka, uporabimo isti izpis pomnilnika objekta. Vrhunec naloge generiranja njihove serializirane predstavitve je dejstvo, da so elementi imenika modelirani s hierarhijo razredov.​

Za njegovo izvedbo v jeziku C so posebna polja dedičev izločena v ločene strukture, njihova povezava z osnovnim pa je določena s poljem tipa unije. Dejanska vsebina unije je podana prek tehničnega atributa tipa.

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

Dodajanje in posodabljanje vnosov

Serijski ključ in vrednost je mogoče dodati v trgovino. Za to se uporablja funkcija mdb_put.

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

V fazi konfiguracije lahko repozitoriju dovolite ali prepoveste shranjevanje več zapisov z istim ključem.​​ Če je podvajanje ključev prepovedano, lahko pri vstavljanju zapisa določite, ali je dovoljeno posodabljanje že obstoječega zapisa ali ne. Če do obrabe lahko pride samo zaradi napake v kodi, se lahko proti njej zavarujete tako, da navedete zastavico NOOVERWRITE.

Bralni zapisi

Funkcija za branje zapisov v LMDB je mdb_get. Če je par ključ-vrednost predstavljen s predhodno izpuščenimi strukturami, je ta postopek videti takole.

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

Predstavljeni seznam prikazuje, kako vam serializacija prek odlagališča struktur omogoča, da se znebite dinamičnih dodelitev ne le pri pisanju, ampak tudi pri branju podatkov. Izpeljano iz funkcije mdb_get kazalec pogleda točno na naslov navideznega pomnilnika, kjer baza podatkov shrani bajtno predstavitev objekta. Pravzaprav dobimo neke vrste ORM, ki skoraj brezplačno zagotavlja zelo visoko hitrost branja podatkov. Ob vsej lepoti pristopa se je treba spomniti več značilnosti, povezanih z njim.

1. Za transakcijo samo za branje je zajamčeno, da kazalec na vrednostno strukturo ostane veljaven le, dokler transakcija ni zaprta. Kot smo že omenili, ostanejo strani B-drevesa, na katerem se objekt nahaja, zaradi načela kopiranja ob pisanju nespremenjene, dokler se vsaj ena transakcija nanaša nanje. Hkrati je mogoče strani znova uporabiti za nove podatke, takoj ko je zaključena zadnja transakcija, povezana z njimi. Če je potrebno, da objekti preživijo transakcijo, ki jih je ustvarila, jih je vseeno treba kopirati.
2. Za transakcijo branja in pisanja bo kazalec na nastalo strukturno vrednost veljaven le do prvega postopka spreminjanja (zapisovanje ali brisanje podatkov).
3. Čeprav struktura NodeValue ni polnopraven, ampak obrezan (glejte pododdelek "Naročanje ključev z zunanjim primerjalnikom"), s kazalcem lahko preprosto dostopate do njegovih polj. Glavna stvar je, da ga ne razimenujete!
4. V nobenem primeru ne morete spremeniti strukture prek prejetega kazalca. Vse spremembe je treba opraviti samo z metodo mdb_put. Vendar z vso željo po tem ne bo delovalo, saj je pomnilniško območje, kjer se nahaja ta struktura, preslikano v načinu samo za branje.
5. Preslikajte datoteko v naslovni prostor procesa, da na primer povečate največjo velikost pomnilnika s funkcijo mdb_env_set_map_size popolnoma razveljavi vse transakcije in povezane entitete na splošno in še posebej kazalce za branje objektov.

Nazadnje, še ena lastnost je tako zahrbtna, da razkritje njenega bistva ne sodi samo v eno točko. V poglavju o drevesu B sem podal diagram organizacije njegovih strani v spominu. Iz tega sledi, da je naslov začetka vmesnega pomnilnika s serializiranimi podatki lahko popolnoma poljuben. Zaradi tega je kazalec na njih, pridobljen v strukturi MDB_val in predvajanje na kazalec na strukturo je na splošno neporavnano. Hkrati pa arhitektura nekaterih čipov (v primeru iOS-a je to armv7) zahteva, da je naslov katerega koli podatka večkratnik velikosti strojne besede ali, z drugimi besedami, bitnosti sistema. (za armv7 je to 32 bitov). Z drugimi besedami, operacija, kot je *(int *foo)0x800002 na njih se enači s pobegom in vodi v usmrtitev s sodbo EXC_ARM_DA_ALIGN. Obstajata dva načina, da se izognete tako žalostni usodi.

Prvi je predhodno kopiranje podatkov v znano poravnano strukturo. Na primer, na primerjalniku po meri se bo to odražalo na naslednji 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 // ...
}

Druga možnost je, da vnaprej obvestite prevajalnik, da strukture s ključem in vrednostjo morda ne bodo poravnane z uporabo atributa aligned(1). Na ARM je lahko enak učinek doseči in z uporabo atributa packed. Glede na to, da prispeva tudi k optimizaciji prostora, ki ga konstrukcija zaseda, se mi ta metoda zdi boljša, čeprav приводит povečati stroške operacij dostopa do podatkov.

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

Poizvedbe po območju

Za ponavljanje po skupini zapisov LMDB ponuja abstrakcijo kazalca. Poglejmo, kako delati z njim na primeru tabele z metapodatki uporabniškega oblaka, ki so nam že znani.

Kot del prikaza seznama datotek v imeniku morate najti vse ključe, s katerimi so povezane njegove podrejene datoteke in mape. V prejšnjih pododdelkih smo razvrstili ključe NodeKey tako da so najprej razvrščeni po ID-ju nadrejenega imenika. Tako je tehnično naloga pridobivanja vsebine mape zmanjšana na postavitev kazalca na zgornjo mejo skupine ključev z dano predpono, čemur sledi ponavljanje do spodnje meje.

Z zaporedno iskanjem lahko najdete zgornjo mejo "na čelu". Da bi to naredili, se kazalec postavi na začetek celotnega seznama ključev v bazi podatkov in se nato povečuje, dokler se pod njim ne prikaže ključ z identifikatorjem nadrejenega imenika. Ta pristop ima 2 očitni pomanjkljivosti:

1. Linearna kompleksnost iskanja, čeprav je, kot veste, v drevesih na splošno in še posebej v B-drevesu to mogoče izvesti v logaritemskem času.​
2. Zaman se vse strani pred želeno dvignejo iz datoteke v glavni pomnilnik, kar je izjemno drago.

Na srečo API LMDB zagotavlja učinkovit način za prvotno pozicioniranje kazalca.​ Če želite to narediti, morate oblikovati takšen ključ, katerega vrednost bo zagotovo manjša ali enaka ključu, ki se nahaja na zgornji meji intervala . Na primer, glede na seznam na zgornji sliki lahko naredimo ključ, v katerem je polje parentId bo enako 2, vse ostale pa so zapolnjene z ničlami. Tako delno izpolnjen ključ se dovaja na vhod funkcije mdb_cursor_get ki prikazuje delovanje 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);

Če je najdena zgornja meja skupine ključev, jo ponavljamo, dokler ne srečamo ali ključa z drugim parentId, sicer ključev sploh ne bo zmanjkalo.​

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

Kar je lepo, kot del iteracije z uporabo mdb_cursor_get ne dobimo le ključa, ampak tudi vrednost. Če je za izpolnjevanje izbirnih pogojev med drugim treba preveriti polja iz vrednostnega dela zapisa, potem so povsem dostopna sama sebi brez dodatnih potez.

4.3. Modeliranje odnosov med tabelami

Do danes smo uspeli upoštevati vse vidike oblikovanja in dela z enotabelno zbirko podatkov. Lahko rečemo, da je tabela niz razvrščenih zapisov, sestavljenih iz parov ključ-vrednost iste vrste. Če prikažete ključ kot pravokotnik in z njim povezano vrednost kot polje, dobite vizualni diagram baze podatkov.

​,war

Vendar pa je v resničnem življenju le redko mogoče preživeti s tako malo krvi. Pogosto je v zbirki podatkov potrebno, prvič, imeti več tabel, in drugič, izvesti izbore v njih v vrstnem redu, ki se razlikuje od primarnega ključa. Zadnji del je posvečen vprašanjem njihovega nastanka in povezovanja.

Indeksne tabele

Aplikacija v oblaku ima razdelek »Galerija«. Prikazuje medijske vsebine iz celotnega oblaka, razvrščene po datumu. Za optimalno izvedbo takšne izbire morate poleg glavne tabele ustvariti še eno z novo vrsto ključev. Vsebovale bodo polje z datumom, ko je bila datoteka ustvarjena, ki bo delovalo kot primarni kriterij razvrščanja. Ker se novi ključi nanašajo na iste podatke kot ključi v spodnji tabeli, se imenujejo indeksni ključi. Na spodnji sliki so označeni z oranžno barvo.

Za ločevanje ključev različnih tabel znotraj iste baze podatkov je bilo vsem dodano dodatno tehnično polje tableId. Če ga postavimo za najvišjo prioriteto za razvrščanje, bomo ključe najprej združili po tabelah in že znotraj tabel - po lastnih pravilih.​

Indeksni ključ se nanaša na iste podatke kot primarni ključ. Preprosta implementacija te lastnosti s povezovanjem kopije vrednostnega dela primarnega ključa z njo ni optimalna z več vidikov hkrati:​

1. Z vidika zasedenega prostora so lahko metapodatki precej bogati.
2. Z vidika zmogljivosti boste morali pri posodabljanju metapodatkov vozlišča prepisati dva ključa.
3. Z vidika podpore kode, če pozabimo posodobiti podatke za enega od ključev, bomo dobili subtilno napako nedoslednosti podatkov v pomnilniku.

Nato bomo razmislili, kako odpraviti te pomanjkljivosti.

Organizacija odnosov med tabelami

Vzorec je zelo primeren za povezovanje indeksne tabele z glavno "ključ kot vrednost". Kot pove že ime, je vrednostni del zapisa indeksa kopija vrednosti primarnega ključa. Ta pristop odpravi vse zgoraj naštete pomanjkljivosti, povezane s shranjevanjem kopije vrednostnega dela primarnega zapisa. Edina pristojbina je, da morate za pridobitev vrednosti po ključu indeksa opraviti 2 poizvedbi v bazi podatkov namesto ene. Shematično je nastala shema baze podatkov naslednja.

Drug vzorec za organiziranje odnosov med tabelami je "odvečen ključ". Njegovo bistvo je v dodajanju dodatnih atributov ključu, ki niso potrebni za razvrščanje, temveč za ponovno ustvarjanje povezanega ključa, vendar obstajajo resnični primeri njegove uporabe v aplikaciji Mail.ru Cloud, da bi se izognili globokemu potapljanju v kontekstu specifičnih ogrodij iOS, bom podal fiktiven, vendar bolj razumljiv primer.

Mobilni odjemalci v oblaku imajo stran, ki prikazuje vse datoteke in mape, ki jih je uporabnik delil z drugimi ljudmi. Ker je takšnih datotek razmeroma malo, z njimi pa je povezanih veliko specifičnih informacij o javnosti (komu je dovoljen dostop, s kakšnimi pravicami ipd.), jih ne bo smiselno obremenjevati z vrednostnim delom zapis v glavni tabeli. Vendar, če želite takšne datoteke prikazati brez povezave, jih morate še vedno nekje shraniti. Naravna rešitev je ustvariti ločeno mizo za to. V spodnjem diagramu ima njegov ključ predpono "P", nadomestno mesto "propname" pa je mogoče nadomestiti z natančnejšo vrednostjo "javne informacije".​

Vsi unikatni metapodatki, zaradi katerih je bila izdelana nova tabela, se premaknejo v vrednostni del zapisa. Hkrati pa ne želim podvajati podatkov o datotekah in mapah, ki so že shranjene v glavni tabeli. Namesto tega se odvečni podatki dodajo tipki "P" v obliki polj "ID vozlišča" in "časovni žig". Zahvaljujoč njim lahko sestavite indeksni ključ, s katerim lahko dobite primarni ključ, s katerim lahko končno dobite metapodatke vozlišča.

Zaključek

Rezultate implementacije LMDB ocenjujemo pozitivno. Po njem se je število zamrznitev aplikacij zmanjšalo za 30 %.

Rezultati opravljenega dela so našli odziv zunaj ekipe iOS. Trenutno je tudi eden od glavnih razdelkov »Datoteke« v aplikaciji za Android prešel na uporabo LMDB, drugi deli pa so na poti. Jezik C, v katerem je implementirana shramba ključ-vrednost, je bil dobra pomoč, da je bila aplikacija na začetku vezana na več platform v jeziku C++. Za brezhibno povezavo dobljene knjižnice C ++ s kodo platforme v Objective-C in Kotlin je bil uporabljen generator kode Djinni iz Dropboxa, a to je že druga zgodba.

Vir: www.habr.com