U jesen 2019. u Mail.ru Cloud iOS timu dogodio se dugo očekivani događaj. Glavna baza podataka za trajno skladištenje stanja aplikacije postala je prilično egzotična za mobilni svijet Lightning memorija mapirana baza podataka (LMDB). Ispod reza, vaša pažnja je pozvana na njegovu detaljnu recenziju u četiri dijela. Prvo, hajde da razgovaramo o razlozima za tako netrivijalan i težak izbor. Zatim pređimo na razmatranje tri kita u srcu LMDB arhitekture: memorijski mapirani fajlovi, B+ stablo, pristup kopiranja na upisivanje za implementaciju transakcijskog i multiverzionog. Za kraj, za desert - praktični dio. U njemu ćemo pogledati kako dizajnirati i implementirati osnovnu shemu s nekoliko tabela, uključujući jednu indeksnu, na vrhu API-ja ključ/vrijednost niske razine.​

Sadržaj

1. Motivacija za implementaciju
2. Pozicioniranje LMDB
3. Tri kita LMDB
   3.1. Kit #1. Memorijski mapirani fajlovi
   3.2. Kit #2. B+-stablo
   3.3. Kit #3. kopiraj-na-piši
4. Dizajniranje šeme podataka na vrhu API-ja ključ/vrijednost
   4.1. Osnovne apstrakcije
   4.2. Modeliranje tablica
   4.3. Modeliranje odnosa između tabela

1. Motivacija za implementaciju

Jednom godišnje, 2015. godine, vodili smo računa o tome koliko često interfejs naše aplikacije zaostaje. Nismo samo ovo uradili. Imamo sve više pritužbi na činjenicu da ponekad aplikacija prestane da reaguje na radnje korisnika: tasteri se ne pritiskaju, liste se ne pomeraju itd. O mehanici mjerenja rekao na AvitoTech-u, pa ovdje dajem samo redoslijed brojeva.

Rezultati mjerenja su za nas postali hladan tuš. Pokazalo se da su problemi uzrokovani smrzavanjem mnogo veći od bilo kojih drugih. Ako je prije spoznaje ove činjenice glavni tehnički pokazatelj kvalitete bio bez sudara, onda nakon fokusa pomaknut bez zamrzavanja.

Sagradivši kontrolna tabla sa zamrzavanjem i potrošivši kvantitativno и kvalitet 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 ona gurne u radne tokove. Za sistematsko rješenje ovog problema pribjegli smo arhitekturi s više niti zasnovanoj na lakim akterima. Posvetio sam njene adaptacije za iOS svijet dvije niti u kolektivnom twitteru i članak o Habréu. U okviru aktuelne priče želim da istaknem one aspekte odluke koji su uticali na izbor baze podataka.​

Akterski model organizacije sistema pretpostavlja da multithreading postaje njegova druga suština. Objekti modela u njemu vole da prelaze granice niti. I to ne rade ponekad i ponegdje, već skoro stalno i svuda.

Baza podataka je jedna od temeljnih komponenti u predstavljenom dijagramu. Njegov glavni zadatak je implementacija makrouzorca Zajednička baza podataka. Ako se u poslovnom svijetu koristi za organiziranje sinhronizacije podataka između usluga, onda u slučaju arhitekture aktera, podaci između niti. Dakle, bila nam je potrebna takva baza podataka, rad s kojom u okruženju s više niti ne izaziva čak ni minimalne poteškoće. Konkretno, to znači da objekti izvedeni iz njega moraju biti barem sigurni u niti, a u idealnom slučaju uopće ne promjenjivi. Kao što znate, potonji se može koristiti istovremeno iz nekoliko niti bez pribjegavanja bilo kakvoj vrsti brave, što ima blagotvoran učinak na performanse.

Drugi značajan faktor koji je uticao na izbor baze podataka bio je naš cloud API. Inspirisan je git pristupom sinhronizaciji. Na njega smo ciljali offline prvi API, što izgleda više nego prikladno za klijente u oblaku. Pretpostavljalo se da će oni samo jednom ispumpati puno stanje oblaka, a zatim će do sinhronizacije u ogromnoj većini slučajeva doći kroz uvođenje promjena. Nažalost, ova prilika je još samo u teorijskoj zoni, a klijenti u praksi nisu naučili raditi sa zakrpama. Za to postoji niz objektivnih razloga, koje ćemo, kako ne bismo odlagali uvod, ostaviti iza zagrada. Ono što je mnogo više interesantno su poučni zaključci lekcije o tome šta se dešava kada API kaže „A“, a njegov potrošač ne kaže „B“.

Dakle, ako zamislite git, koji prilikom izvršavanja naredbe za povlačenje, umjesto primjene zakrpa na lokalni snimak, uspoređuje svoje puno stanje s punim stanjem servera, tada ćete imati prilično tačnu ideju o tome kako se sinhronizacija događa u oblaku klijentima. Lako je pretpostaviti da da biste ga implementirali, morate dodijeliti dva DOM stabla u memoriji s meta-informacijama o svim serverskim i lokalnim datotekama. Ispostavilo se da ako korisnik skladišti 500 hiljada fajlova u oblaku, da bi ga sinhronizovao potrebno je ponovo kreirati i uništiti dva stabla sa milion čvorova. Ali svaki čvor je agregat koji sadrži graf podobjekata. U tom svjetlu očekivani su rezultati profiliranja. Ispostavilo se da čak i bez uzimanja u obzir algoritma spajanja, sama procedura kreiranja i naknadnog uništavanja ogromnog broja malih objekata košta prilično peni. Situaciju pogoršava činjenica da je osnovna operacija sinhronizacije uključena u veliki broj korisničkih skripti. Kao rezultat toga, popravljamo drugi važan kriterij pri odabiru baze podataka - mogućnost implementacije CRUD operacija bez dinamičke alokacije objekata.

Ostali zahtjevi su tradicionalniji, a njihova potpuna lista je sljedeća.

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 ekstenzija.
3. Sposobnost predstavljanja pohranjenih entiteta kao nepromjenjivih objekata.​
4. Nedostatak dinamičkih alokacija unutar CRUD operacija.
5. Transakciona 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 je dobar izbor. Međutim, kao dio proučavanja alternativa, naišao sam na knjigu "Početak rada s LevelDB". Pod njenim vodstvom napisan je benchmark koji upoređuje brzinu rada s različitim bazama podataka u realnim cloud scenarijima. Rezultat je premašio i najluđa očekivanja. U najpopularnijim slučajevima - dobivanje kursora na sortiranoj listi svih datoteka i sortiranoj listi svih datoteka za dati direktorij - LMDB se pokazao 10 puta bržim od SQLite-a. Izbor je postao očigledan.

2. LMDB pozicioniranje

LMDB je biblioteka, vrlo mala (samo 10K linija) koja implementira najniži temeljni sloj baza podataka - skladište.

Gornji dijagram pokazuje da poređenje LMDB-a sa SQLite-om, koji također implementira više razine, općenito nije ispravnije od SQLite-a sa Core Data. Bilo bi poštenije navesti iste mašine za skladištenje kao jednake konkurente - BerkeleyDB, LevelDB, Sophia, RocksDB, itd. Postoje čak i razvoji u kojima LMDB deluje kao komponenta mašine za skladištenje za SQLite. Prvi takav eksperiment bio je 2012 potrošen by LMDB Howard Chu. Rezulʹtaty pokazalo se toliko intrigantno da su njegovu inicijativu pokupili entuzijasti OSS-a, i našla je svoj nastavak u suočavanju sa LumoSQL. U januaru 2020. autor ovog projekta je Den Shearer predstavljeno to na LinuxConfAu.

LMDB se uglavnom koristi kao mehanizam za baze podataka aplikacija. Biblioteka svoj izgled duguje programerima OpenLDAP, koji su bili izrazito nezadovoljni BerkeleyDB-om kao osnovom njihovog projekta. Odgurivanje od skromne biblioteke btree, Howard Chu je uspio stvoriti jednu od najpopularnijih alternativa našeg vremena. Svoj vrlo cool izvještaj posvetio je ovoj priči, kao i internoj strukturi LMDB-a "The Lightning Memory-mapped Database". Leonid Yuriev (aka yleo) iz Positive Technologies u svom govoru na Highload 2015 "LMDB motor je poseban šampion". U njemu on govori o LMDB-u u kontekstu sličnog zadatka implementacije ReOpenLDAP-a, a LevelDB je već bio podvrgnut komparativnoj kritici. Kao rezultat implementacije, Positive Technologies je čak dobio i viljušku koja se aktivno razvija MDBX sa vrlo ukusnim karakteristikama, optimizacijama i popravljanje grešaka.

LMDB se često koristi i kao skladište. Na primjer, pretraživač Mozilla Firefox izabrao to za brojne potrebe i, počevši od verzije 9, Xcode preferirano njegov SQLite za pohranjivanje indeksa.

Motor se također uhvatio u svijetu razvoja mobilnih uređaja. Tragovi njegove upotrebe 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 keširanje podataka, Rocket Data, o čemu rekao u članku iz 2016.

LMDB se uspješno bori za mjesto na suncu u niši koju je BerkeleyDB ostavio nakon prelaska pod kontrolu Oraclea. Biblioteku vole zbog svoje brzine i pouzdanosti, čak iu poređenju sa svojom 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 na vrhu diskovne memorije. Naravno, u dobroj arhitekturi još uvijek ne možete bez njih i oni će se neizbježno pojaviti u kodu aplikacije, ali će biti mnogo tanji. Neće imati funkcije koje nisu potrebne za određenu aplikaciju, na primjer, podršku za upite u SQL jeziku. Drugo, postaje moguće optimalno implementirati mapiranje operacija aplikacije na zahtjeve za pohranu na disku. Ako SQLite u mom radu proizlazi iz prosječnih potreba prosječne aplikacije, tada ste vi, kao programer aplikacija, dobro svjesni glavnih scenarija učitavanja. Za produktivnije rješenje, morat ćete platiti veću cijenu kako za razvoj početnog rješenja tako i za njegovu kasniju podršku.

3. Tri kita LMDB

Nakon što pogledate LMDB iz ptičje perspektive, vrijeme je da idemo dublje. Sljedeća tri odjeljka bit će posvećena analizi glavnih kitova na kojima počiva arhitektura skladištenja:

1. Memorijski mapirani fajlovi kao mehanizam za rad sa diskom i sinhronizaciju internih struktura podataka.
2. B+-stablo kao organizacija pohranjene strukture podataka.
3. Copy-on-write kao pristup za pružanje ACID transakcijskih svojstava i multiverzioniranja.

3.1. Kit #1. Memorijski mapirani fajlovi

Memorijski mapirani fajlovi su toliko važan arhitektonski element da se čak pojavljuju u nazivu spremišta. Pitanja keširanja i sinhronizacije pristupa pohranjenim informacijama su u potpunosti na milosti operativnog sistema. LMDB ne sadrži nikakve keš memorije u sebi. Ovo je svjesna odluka autora, budući da čitanje podataka direktno iz mapiranih datoteka omogućava vam da odsiječete mnogo uglova u implementaciji motora. Ispod je daleko od potpune liste nekih od njih.

1. Održavanje konzistentnosti podataka u skladištu pri radu s njima iz nekoliko procesa postaje odgovornost operativnog sistema. U sljedećem odjeljku, ova mehanika je razmotrena detaljno i sa slikama.
2. Odsustvo keš memorije u potpunosti oslobađa LMDB troškova povezanih s dinamičkim alokacijama. Čitanje podataka u praksi je postavljanje pokazivača na ispravnu adresu u virtuelnoj memoriji i ništa više. Zvuči kao fantazija, ali u izvoru spremišta, svi calloc pozivi su koncentrisani u funkciji konfiguracije spremišta.
3. Odsustvo predmemorije također znači i odsustvo zaključavanja povezanih sa sinhronizacijom za pristup njima. Čitači, čiji proizvoljan broj može postojati u isto vrijeme, ne nailaze na jedan mutex 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. Može postojati samo jedan pisac istovremeno.
4. Minimum keširanja i logike sinhronizacije štedi kod od izuzetno složene vrste grešaka povezanih sa radom u okruženju sa više niti. Na konferenciji Usenix OSDI 2014. bile su dvije zanimljive studije baze podataka: "Svi sistemi datoteka nisu kreirani jednaki: o složenosti izrade aplikacija koje su usklađene s padovima" и Mučenje baza podataka za zabavu i profit. Od njih možete dobiti informacije kako o neviđenoj pouzdanosti LMDB-a, tako io gotovo besprijekornoj implementaciji ACID svojstava transakcija, koja ga nadmašuje u istom SQLite-u.
5. Minimalizam LMDB-a omogućava da se strojna reprezentacija njegovog koda u potpunosti smjesti u L1 keš memoriju procesora sa rezultujućim karakteristikama brzine.

Nažalost, u iOS-u, sa memorijskim mapiranim datotekama, sve nije tako bez oblaka kako bismo željeli. Da bismo svjesnije govorili o nedostacima povezanim s njima, potrebno je zapamtiti opća načela implementacije ovog mehanizma u operativne sisteme.

Opće informacije o memorijskim mapiranim datotekama

Sa svakom izvršnom aplikacijom, operativni sistem pridružuje entitet koji se zove proces. Svakom procesu se dodjeljuje neprekinuti raspon adresa u koje smješta sve što mu je potrebno za rad. Najniže adrese sadrže sekcije sa kodom i tvrdo kodiranim podacima i resursima. Zatim dolazi blok dinamičkog adresnog prostora koji raste naviše, koji nam je dobro poznat kao hrpa. Sadrži adrese entiteta koji se pojavljuju tokom rada programa. Na vrhu je područje memorije koje koristi stek aplikacija. Ili raste ili se smanjuje, drugim riječima, njegova veličina također ima dinamičnu prirodu. Kako se stek i hrpa ne bi gurali i ometali jedni druge, oni su razdvojeni na različitim krajevima adresnog prostora.Postoji rupa između dva dinamička odjeljka na vrhu i dnu. Adrese u ovom srednjem dijelu operativni sistem koristi za povezivanje s procesom različitih entiteta. Konkretno, može mapirati određeni kontinuirani skup adresa u datoteku na disku. Takav fajl se naziva memorijski mapirani fajl.​

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

Međutim, iz našeg iskustva znamo da moderni operativni sistemi mogu istovremeno izvršiti onoliko procesa koliko želite. To je moguće zbog činjenice da oni samo izdvajaju mnogo memorije procesima na papiru, ali u stvarnosti u glavnu fizičku memoriju učitavaju samo onaj dio koji je ovdje i sada tražen. Stoga se memorija povezana s procesom naziva virtualna.

Operativni sistem organizira virtuelnu i fizičku memoriju u stranice određene veličine. Čim je potrebna određena stranica virtuelne memorije, operativni sistem je učitava u fizičku memoriju i upisuje korespondenciju između njih u posebnu tabelu. Ako nema slobodnih slotova, tada se jedna od prethodno učitanih stranica kopira na disk, a tražena zauzima njeno mjesto. Ovaj postupak, na koji ćemo se uskoro vratiti, naziva se zamjena. Slika ispod ilustruje opisani proces. Na njoj je učitana stranica A sa adresom 0 i stavljena na stranicu glavne memorije sa adresom 4. Ova činjenica se odrazila u tabeli korespondencije u ćeliji broj 0.​

Sa memorijskim mapiranim datotekama, priča je potpuno ista. Logično, oni su navodno kontinuirano i u potpunosti smješteni u virtuelni adresni prostor. Međutim, oni ulaze u fizičku memoriju stranicu po stranicu i samo na zahtjev. Izmjena takvih stranica se sinhronizuje sa fajlom na disku. Dakle, možete izvršiti U/I fajl, jednostavno radeći sa bajtovima u memoriji - sve promjene će automatski prenijeti kernel operativnog sistema u originalni fajl.​
​
Slika ispod pokazuje kako LMDB sinkronizira svoje stanje kada radi s bazom podataka iz različitih procesa. Preslikavanjem virtuelne memorije različitih procesa u istu datoteku, mi de facto obavezujemo operativni sistem da tranzitivno sinhronizuje određene blokove njihovih adresnih prostora jedan s drugim, što je mjesto gdje izgleda LMDB.​
​

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

Prva posljedica je zajednička za sve operativne sisteme. Njegova suština je dodati zaštitu od nenamjernog oštećenja bazi podataka neispravnim kodom. Kao što znate, izvršne instrukcije procesa su slobodne za pristup podacima s bilo kojeg mjesta u njegovom adresnom prostoru. Istovremeno, kao što smo se upravo prisjetili, prikazivanje datoteke u načinu čitanja i pisanja znači da ga bilo koja instrukcija može modificirati. Ako to učini greškom, pokušavajući, na primjer, da zapravo prepiše element niza na nepostojećem indeksu, onda 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 samo za čitanje, tada će pokušaj promjene odgovarajućeg adresnog prostora dovesti do hitnog prekida programa sa signalom SIGSEGV, a datoteka će ostati netaknuta.

Druga posljedica je već specifična za iOS. Ni autor ni drugi izvori to eksplicitno ne spominju, ali bez njega LMDB ne bi bio pogodan za rad na ovom mobilnom operativnom sistemu. Sljedeći dio je posvećen njegovom razmatranju.

Specifičnosti memorijskih mapiranih datoteka u iOS-u

U 2018., na WWDC-u je bio divan izvještaj iOS Memory Deep Dive. To nam govori da su u iOS-u sve stranice koje se nalaze u fizičkoj memoriji jedne od 3 vrste: prljave, komprimirane i čiste.

Čista memorija je zbirka stranica koje se mogu bezbedno zameniti iz fizičke memorije. Podaci koje sadrže mogu se ponovo učitati iz originalnih izvora po potrebi. U ovu kategoriju spadaju datoteke samo za čitanje mapirane memorije. iOS se ne plaši da u bilo kom trenutku isprazni stranice mapirane u fajl iz memorije, jer je zagarantovano da će biti sinhronizovane sa fajlom na disku.
​
Sve izmijenjene stranice ulaze u prljavu memoriju, bez obzira gdje se izvorno nalaze. Konkretno, memorijsko mapirane datoteke modificirane upisivanjem u virtualnu memoriju pridruženu njima također će biti klasifikovane na ovaj način. Otvaranje LMDB sa zastavicom MDB_WRITEMAP, nakon što izvršite izmjene, možete se uvjeriti sami.​

​Čim aplikacija počne da zauzima previše fizičke memorije, iOS komprimira svoje prljave stranice. Kolekcija memorije koju zauzimaju prljave i komprimirane stranice je takozvani memorijski otisak aplikacije. Kada dostigne određenu graničnu vrijednost, sistemski demon OOM ubojica dolazi nakon procesa i prisilno ga prekida. Ovo je posebnost iOS-a u poređenju sa desktop operativnim sistemima. Nasuprot tome, smanjenje memorijskog otiska zamjenom stranica s fizičke memorije na disk nije predviđeno u iOS-u, a o razlozima se može samo nagađati. Možda je postupak intenzivnog premeštanja stranica na disk i nazad previše energetski zahtjevan za mobilne uređaje, ili iOS štedi resurse ponovnog pisanja ćelija na SSD diskovima, ili možda dizajneri nisu bili zadovoljni ukupnim performansama sistema, gdje je sve stalno menjaju. Kako god bilo, činjenica ostaje.

Dobra vijest, već spomenuta ranije, je da LMDB ne koristi mehanizam mmap po defaultu za ažuriranje datoteka. Slijedi da su renderirani podaci klasifikovani kao čista memorija od strane iOS-a i da ne doprinose memorijskom otisku. Ovo se može provjeriti pomoću alata Xcode koji se zove VM Tracker. Snimak ekrana ispod prikazuje stanje virtuelne memorije iOS Cloud aplikacije tokom rada. Na početku su u njemu inicijalizirane 2 LMDB instance. Prvom je bilo dozvoljeno da mapira svoj fajl na 1GiB virtuelne memorije, drugom - 512MiB. Uprkos činjenici da oba skladišta zauzimaju određenu količinu rezidentne memorije, nijedna od njih ne doprinosi prljavoj veličini.

A sada je vrijeme za loše vijesti. Zahvaljujući swap mehanizmu u 64-bitnim desktop operativnim sistemima, svaki proces može zauzeti onoliko virtuelnog adresnog prostora koliko slobodan prostor na hard disku za njegovu potencijalnu zamjenu dozvoljava. Zamjena swap-a kompresijom u iOS-u radikalno smanjuje teoretski maksimum. Sada svi živi procesi moraju stati u glavnu (čitaj RAM) memoriju, a svi oni koji se ne uklapaju moraju biti prisiljeni da se prekinu. Ovo je navedeno kao u gore navedenom izveštaj, i službena dokumentacija. Kao posljedica toga, iOS ozbiljno ograničava količinu memorije dostupne za dodjelu putem mmap-a. Evo ovdje možete pogledati empirijska ograničenja količine memorije koja se može dodijeliti različitim uređajima koristeći ovaj sistemski poziv. Na najsavremenijim modelima pametnih telefona iOS je postao izdašan za 2 gigabajta, a na vrhunskim verzijama iPada - za 4. U praksi, naravno, morate se fokusirati na najmlađe podržane modele uređaja, gdje je sve jako tužno. Što je još gore, gledajući stanje memorije aplikacije u VM Trackeru, otkrit ćete da LMDB nije jedini koji traži memoriju mapiranu memoriju. Dobre komade pojedu sistemski alokatori, fajlovi resursa, okviri slika i drugi manji grabežljivci.

Na osnovu rezultata eksperimenata u Cloud-u, 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 uređaje. Nakon što se ovaj volumen potroši, sve operacije modifikacije počinju da se završavaju sa kodom MDB_MAP_FULL. Takve greške uočavamo u našem praćenju, ali su one dovoljno male da ih se u ovoj fazi zanemari.

Neočigledan razlog za prekomjernu potrošnju memorije od strane skladišta 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+-stablo

Da biste emulirali tablice na vrhu skladišta ključ/vrijednost, sljedeće operacije moraju biti prisutne u njegovom API-ju:

1. Umetanje novog elementa.
2. Potražite element sa datim ključem.
3. Brisanje elementa.
4. Iterirajte ključne intervale u njihovom redoslijedu sortiranja.

Najjednostavnija struktura podataka koja može lako implementirati sve četiri operacije je binarno stablo pretraživanja. Svaki od njegovih čvorova je ključ koji dijeli cijeli podskup podređenih ključeva u dva podstabla. Na lijevoj strani su oni koji su manji od roditelja, a na desnoj - oni koji su veći. Dobijanje uređenog seta ključeva postiže se jednim od klasičnih obilazaka stabala.​

Binarna stabla imaju dvije fundamentalne mane koje ih sprečavaju da budu efikasna kao struktura podataka zasnovana na disku. Prvo, stepen njihove ravnoteže je nepredvidiv. Postoji znatan rizik od dobivanja stabala u kojima se visine različitih grana mogu jako razlikovati, što značajno pogoršava algoritamsku složenost pretraživanja u odnosu na očekivanu. Drugo, obilje unakrsnih veza između čvorova lišava binarna stabla lokacije 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 prelaženje nekoliko susjednih čvorova u stablu može zahtijevati posjetu uporedivog broja stranica. Ovo je problem čak i kada govorimo o efikasnosti binarnih stabala kao strukture podataka u memoriji, jer stalno rotiranje stranica u kešu procesora nije jeftino zadovoljstvo. Kada je riječ o čestom preuzimanju stranica povezanih s čvorovima s diska, situacija postaje potpuno žalosno.

B-stabla, kao evolucija binarnih stabala, rješavaju probleme identificirane u prethodnom paragrafu. Prvo, oni se samouravnotežuju. Drugo, svaki njihov čvor dijeli skup podređenih ključeva ne na 2, već na M uređene podskupove, a broj M može biti prilično velik, reda nekoliko stotina ili čak hiljada.

na taj način:

1. Svaki čvor ima veliki broj već naručenih ključeva i stabla su vrlo niska.
2. Stablo dobija svojstvo lokaliteta u memoriji, pošto se ključevi koji su bliske vrednosti prirodno nalaze jedan pored drugog na jednom ili susednim čvorovima.
3. Broj tranzitnih čvorova prilikom spuštanja stabla tokom operacije pretraživanja je smanjen.
4. Smanjuje broj čitanih ciljnih čvorova za upite opsega, budući da svaki od njih već sadrži veliki broj naručenih ključeva.

LMDB koristi varijantu B-stabla zvanog B+ stablo za pohranjivanje podataka. Gornji dijagram prikazuje tri tipa čvorova koje sadrži:

1. Na vrhu je korijen. On materijalizuje ništa više od koncepta baze podataka unutar spremišta. Unutar jedne LMDB instance, možete kreirati više baza podataka koje dijele mapirani virtuelni adresni prostor. Svaki od njih polazi od svog korijena.
2. Na najnižem nivou su listovi (list). Oni i samo oni sadrže parove ključ/vrijednost pohranjene u bazi podataka. Inače, to je posebnost B+-stabala. Ako normalno B-stablo pohranjuje dijelove vrijednosti na čvorovima svih nivoa, onda je B+-varijacija samo na najnižoj. Pošto smo popravili ovu činjenicu, u nastavku ćemo podtip stabla koji se koristi u LMDB jednostavno zvati B-stablo.
3. Između korijena i listova, postoji 0 ili više tehničkih nivoa s navigacijskim (granama) čvorovima. Njihov zadatak je podijeliti sortirani set ključeva između listova.

Fizički, čvorovi su blokovi memorije unaprijed određene dužine. Njihova veličina je višestruka od veličine memorijskih stranica u operativnom sistemu, o čemu smo govorili gore. Struktura čvora je prikazana ispod. Zaglavlje sadrži meta-informacije, od kojih je najočitija, na primjer, kontrolni zbroj. Slijede informacije o pomacima, duž kojih se nalaze ćelije s podacima. Uloga podataka može biti ili ključeva, ako je riječ o navigacijskim čvorovima, ili cijeli parovi ključ/vrijednost u slučaju listova. Više o strukturi stranica možete pročitati u radu "Evaluacija high-performance key-value prodavnica".

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

Stranice sa čvorovima su uzastopno raspoređene na disku. Stranice sa većim brojem nalaze se na kraju datoteke. Takozvana meta stranica (meta stranica) sadrži informacije o pomacima, koji se mogu koristiti za pronalaženje korijena svih stabala. Kada se datoteka otvori, LMDB skenira datoteku stranicu po stranicu od kraja do početka u potrazi za važećom meta stranicom i preko nje pronalazi postojeće baze podataka.​

Sada, imajući ideju o logičkoj i fizičkoj strukturi organizacije podataka, možemo preći na razmatranje trećeg kita LMDB. Uz njegovu pomoć se sve modifikacije skladišta dešavaju transakcijski i izolovano jedna od druge, dajući bazi podataka kao celini i svojstvo multiverzije.

3.3. Kit #3. kopiraj-na-piši

Neke operacije B-stabla uključuju unošenje čitavog niza promjena na njegovim čvorovima. Jedan primjer je dodavanje novog ključa čvoru koji je već dostigao svoj maksimalni kapacitet. U ovom slučaju, potrebno je, prvo, podijeliti čvor na dva, a 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, itd.) dogodi samo dio promjena iz serije, tada će stablo ostati u nekonzistentnom stanju.

Jedno tradicionalno rešenje za stvaranje otpornosti na greške u bazi podataka je dodavanje dodatne strukture podataka zasnovane na disku, dnevnika transakcija, takođe poznatog kao dnevnik upisivanja unapred (WAL), pored B-stabla. To je datoteka na čijem se kraju, striktno prije modifikacije samog B-stabla, upisuje namjeravana operacija. Stoga, ako se otkrije oštećenje podataka tokom samodijagnoze, baza podataka konsultuje dnevnik da bi se očistila.

LMDB je odabrao drugačiju metodu kao svoj mehanizam tolerancije grešaka, koji se zove kopiranje na pisanje. Njegova suština je da umjesto ažuriranja podataka na postojećoj stranici, prvo ih u potpunosti kopira i izvrši sve izmjene koje su već u kopiji.​

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

Ako se iznenada proces sruši tokom procedure ažuriranja, tada ili neće biti kreirana nova meta stranica, ili neće biti zapisana na disk do kraja, a njen kontrolni zbroj će biti netačan. U bilo kojem od ova dva slučaja, nove stranice će biti nedostupne, a stare neće biti pogođene. Ovo eliminiše potrebu da LMDB piše unapred dnevnik radi održavanja konzistentnosti podataka. De facto, struktura skladištenja podataka na disku, opisana gore, istovremeno preuzima svoju funkciju. Odsustvo eksplicitnog dnevnika transakcija jedna je od karakteristika LMDB-a, koja omogućava veliku brzinu čitanja podataka.​

Rezultirajuća konstrukcija, nazvana B-stablo samo za dodavanje, prirodno obezbjeđuje izolaciju transakcija i više verzija. U LMDB, svaka otvorena transakcija ima ažurirani korijen stabla koji je povezan s njom. Sve dok transakcija nije dovršena, stranice stabla povezane s njom se nikada neće mijenjati ili ponovo koristiti za nove verzije podataka. Dakle, možete raditi koliko god želite tačno sa skupom podataka koji je bio relevantan u vrijeme kada je transakcija otvorena, čak i ako se skladište i dalje aktivno ažurira u ovom trenutku. Ovo je suština multiverzioniranja, što LMDB čini idealnim izvorom podataka za naše voljene UICollectionView. Nakon otvaranja transakcije, ne morate povećavati memorijski otisak aplikacije, žurno pumpajući trenutne podatke u neku strukturu u memoriji, bojeći se da ćete ostati bez ičega. Ova karakteristika razlikuje LMDB od istog SQLite-a, koji se ne može pohvaliti takvom potpunom izolacijom. Nakon otvaranja dvije transakcije u potonjoj i brisanja određenog zapisa unutar jedne od njih, isti zapis se više ne može dobiti u drugom preostalom.

Druga strana medalje je potencijalno znatno veća potrošnja virtuelne memorije. Slajd pokazuje kako će izgledati struktura baze podataka ako se modificira u isto vrijeme sa 3 otvorene transakcije čitanja gledajući različite verzije baze podataka. Budući da LMDB ne može ponovo koristiti čvorove koji su dostupni iz korijena povezanih sa stvarnim transakcijama, skladište nema izbora osim da dodijeli još jedan četvrti korijen u memoriji i još jednom klonira izmijenjene stranice ispod njega.

Ovdje neće biti suvišno prisjetiti se odjeljka o memorijskim mapiranim datotekama. Čini se da nam dodatna potrošnja virtualne memorije ne bi trebala puno smetati, jer ne doprinosi memorijskom otisku aplikacije. Međutim, u isto vrijeme je primjećeno da je iOS vrlo škrt u dodjeli, te ne možemo dati LMDB regiju od 1 terabajta na serveru ili desktopu sa ramena gospodara i uopće ne razmišljati o ovoj funkciji. Kada je to moguće, trebali biste pokušati da vek trajanja transakcija bude što kraći.

4. Dizajniranje šeme podataka na vrhu API-ja ključ/vrijednost

Započnimo raščlanjivanje API-ja gledajući osnovne apstrakcije koje pruža LMDB: okruženje i baze podataka, ključevi i vrijednosti, transakcije i kursori.

Napomena o listi kodova

Sve funkcije u LMDB javnom API-ju vraćaju rezultat svog rada u obliku koda greške, ali u svim narednim listama njegova provjera je izostavljena radi sažetosti.U praksi smo koristili vlastiti kod za interakciju sa spremištem. viljuška C++ omoti lmdbxx, u kojem se greške materijaliziraju kao C++ izuzeci.

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

4.1. Osnovne apstrakcije

Životna sredina

struktura MDB_env je spremište internog stanja LMDB-a. Porodica funkcija s prefiksom mdb_env omogućava vam da konfigurišete 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 na koji je mapirana datoteka za pohranu. Nažalost, čak i na istom uređaju, specifična vrijednost može značajno varirati od pokretanja do pokretanja. Da bismo uzeli u obzir ovu značajku iOS-a, dinamički biramo maksimalnu količinu prostora za pohranu. Počevši od određene vrijednosti, ona se sukcesivno prepolovi 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 u tome što je procedura za ponovno mapiranje memorije pomoću funkcije mdb_env_set_map_size poništava sve entitete (kurzore, transakcije, ključeve i vrijednosti) prethodno primljene od motora. Uzimanje u obzir ovakvog razvoja događaja u kodeksu će dovesti do njegove značajne komplikacije. Međutim, ako vam je virtuelna memorija jako važna, onda bi to mogao biti razlog da bolje pogledate račvu koja je otišla daleko naprijed MDBX, gdje je među deklariranim karakteristikama „automatsko prilagođavanje veličine baze podataka u hodu“.

Drugi parametar, čija nam zadana vrijednost nije odgovarala, regulira mehaniku osiguravanja 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 sa zastavicom MDB_NOTLS. Osim toga, to je također zahtijevalo viljuška C++ omot lmdbxxda isečete varijable sa i u ovom atributu.

Baze podataka

Baza podataka je zasebna instanca B-stabla o kojem smo gore govorili. Njegovo otvaranje se dešava unutar transakcije, što u početku može izgledati malo čudno.

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

Zaista, transakcija u LMDB je skladišni entitet, a ne određena baza podataka. Ovaj koncept vam omogućava da izvodite atomske operacije nad entitetima koji se nalaze u različitim bazama podataka. U teoriji, ovo otvara mogućnost modeliranja tabela u obliku različitih baza podataka, ali sam jednom otišao drugim putem, detaljno opisanim u nastavku.

Ključevi i vrijednosti

struktura MDB_val modelira koncept i ključa i vrijednosti. Repozitorijum nema pojma o njihovoj semantici. Za nju, nešto što je drugačije je 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;​​

Prodavnica koristi komparator za sortiranje ključeva u rastućem redoslijedu. Ako ga ne zamijenite svojim, tada će se koristiti zadani, koji ih sortira bajt po bajt po leksikografskom redoslijedu.​

Transakcije

Transakcioni uređaj je detaljno opisan u prethodno poglavlje, pa ću ovdje ponoviti njihova glavna svojstva u kratkom redu:

1. Podrška za sva osnovna svojstva ACIDKljučne riječi: atomičnost, konzistentnost, izolacija i pouzdanost. Ne mogu a da ne primijetim da je u pogledu izdržljivosti na macOS-u i iOS-u ispravljena greška u MDBX-u. Više možete pročitati u njihovoj README.
2. Pristup multithreadingu opisan je shemom "jedan pisac / više čitača". Pisci blokiraju jedni druge, ali ne blokiraju čitaoce. Čitaoci ne blokiraju pisce ili jedni druge.
3. Podrška za ugniježđene transakcije.
4. Podrška za više verzija.

Multiverzioniranje u LMDB-u je toliko dobro da želim da ga demonstriram na delu. Kod u nastavku pokazuje da svaka transakcija radi s upravo onom verzijom baze podataka koja je bila relevantna u trenutku njenog otvaranja, potpuno izolirana od svih narednih promjena. Inicijalizacija spremišta i dodavanje test zapisa u njega nije od interesa, tako da su ovi rituali ostavljeni ispod spojlera.

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

Opciono, preporučujem da isprobate isti trik sa SQLite-om i vidite šta će se dogoditi.

Multiverzioniranje donosi veoma lepe prednosti u životu iOS programera. Koristeći ovo svojstvo, možete lako i prirodno prilagoditi stopu ažuriranja izvora podataka za obrasce na ekranu na osnovu razmatranja korisničkog iskustva. Na primjer, uzmimo takvu značajku aplikacije Mail.ru Cloud kao što je automatsko učitavanje sadržaja iz galerije sistemskih medija. Uz dobru vezu, klijent može dodati nekoliko fotografija u sekundi na server. Ako ažurirate nakon svakog preuzimanja UICollectionView sa medijskim sadržajem u korisničkom oblaku, možete zaboraviti na 60 fps i glatko skrolovanje tokom ovog procesa. Da biste spriječili česta ažuriranja ekrana, morate nekako ograničiti brzinu promjene podataka u bazi UICollectionViewDataSource.

Ako baza podataka ne podržava više verzija i dozvoljava vam da radite samo sa trenutnim trenutnim stanjem, tada da biste kreirali vremenski stabilan snimak podataka, morate ga kopirati ili u neku strukturu podataka u memoriji ili u privremenu tabelu. Bilo koji od ovih pristupa je veoma skup. U slučaju skladištenja u memoriji, dobijamo i troškove memorije uzrokovane skladištenjem konstruisanih 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 netrivijalnim slučajevima.

Multiverzioniranje 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 će garantirano biti fiksiran. Logika njegove brzine ažuriranja sada je u potpunosti u rukama sloja prezentacije, bez dodatnih troškova značajnih resursa.

Kursori

Kursori pružaju mehanizam za uredno ponavljanje parova ključ/vrijednost prelazeći B-stablo. Bez njih, bilo bi nemoguće efikasno modelirati tabele u bazi podataka, čemu se sada okrećemo.

4.2. Modeliranje tablica

Svojstvo redosleda ključeva vam omogućava da konstruišete apstrakciju najvišeg nivoa kao što je tabela na vrhu osnovnih apstrakcija. Razmotrimo ovaj proces na primjeru glavne tablice klijenta u oblaku, u kojoj se keširaju informacije o svim datotekama i mapama korisnika.

Shema tabele

Jedan od uobičajenih scenarija za koji treba izoštriti strukturu tabele sa stablom foldera je odabir svih elemenata koji se nalaze unutar datog direktorija.Dobar model organizacije podataka za efikasne upite ove vrste je Lista susjedstva. Da biste ga implementirali na vrh memorije ključ/vrijednost, potrebno je sortirati ključeve datoteka i mapa na takav način da su grupisani na osnovu pripadnosti roditeljskom direktoriju. Osim toga, da bi se sadržaj direktorija prikazao u formi poznatom korisniku Windows-a (prvo mape, a zatim datoteke, oba se sortiraju po abecednom redu), potrebno je u ključ uključiti odgovarajuća dodatna polja.

Slika ispod pokazuje kako, na osnovu zadatka, može izgledati reprezentacija ključeva kao niz bajtova. Prvo se postavljaju bajtovi sa identifikatorom roditeljskog direktorijuma (crveni), zatim sa tipom (zeleno), a već u repu sa imenom (plavo).Stvrđeni po podrazumevanom LMDB komparatoru u leksikografskom redosledu, poredani su po traženi način. Uzastopno prelaženje ključeva s istim crvenim prefiksom daje nam vrijednosti koje su im povezane redoslijedom kojim bi se trebale prikazati u korisničkom interfejsu (desno), bez potrebe za dodatnom naknadnom obradom.

Serijalizacija ključeva i vrijednosti

Postoji mnogo metoda za serijalizaciju objekata širom svijeta. Pošto nismo imali nikakav drugi zahtjev osim brzine, za sebe smo odabrali najbrži mogući - memorijski dump koji zauzima instanca 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;

Da spasim NodeKey u skladištu potreba u objektu MDB_val postavite pokazivač na podatke na adresu početka strukture i izračunajte 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 alokacija kao dio CRUD operacija kao važan faktor odabira. Kôd 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 sa servera se prvo transformiše u strukture steka, a zatim se trivijalno izbacuju u skladište. S obzirom da također nema dinamičkih alokacija unutar LMDB-a, možete dobiti fantastičnu situaciju po standardima iOS-a - koristite samo stack memoriju za rad s podacima sve od mreže do diska!

Naručivanje ključeva sa binarnim komparatorom

Relacija ključnog reda je data specijalnom funkcijom koja se zove komparator. Budući da mašina ne zna ništa o semantici bajtova koje sadrže, zadani komparator nema izbora nego da rasporedi ključeve po leksikografskom redoslijedu, pribjegavajući njihovoj usporedbi bajt po bajt. Korištenje za uređenje struktura slično 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 primijetiti nekoliko grabulja razbacanih po putu.

Prva stvar koju treba imati na umu je memorijsko predstavljanje primitivnih tipova podataka. Dakle, na svim Apple uređajima, cjelobrojne varijable su pohranjene u formatu Mali Endian. To znači da će najmanji bajt biti na lijevoj strani i nećete moći sortirati cijele brojeve koristeći njihovo poređenje bajt po bajt. Na primjer, pokušaj da to učinite 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 porodice pomoći će da se izvrši neophodna transformacija. hton* (posebno htons za dvobajtne brojeve iz primjera).

Format za predstavljanje stringova u programiranju je, kao što znate, cjelina istorija. Ako semantika nizova, kao i kodiranje koje se koristi za njihovo predstavljanje u memoriji, sugerira da može biti više od jednog bajta po karakteru, onda je bolje odmah napustiti ideju korištenja zadanog komparatora.

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

Naručivanje ključeva pomoću eksternog komparatora

Logika poređenja ključeva može se pokazati previše složenom za binarni komparator. Jedan od mnogih razloga je prisustvo tehničkih polja unutar konstrukcija. Ilustrirat ću njihovu pojavu na primjeru ključa koji nam je već poznat za element direktorija.

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. Bafer 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 da ga skrate tako da odgovara njegovoj stvarnoj veličini. Njegova suština je da se sadržaj svih polja promenljive dužine čuva u baferu na kraju strukture, a njihove dužine u posebnim varijablama.U skladu sa ovim pristupom ključ NodeKey transformiše se na sledeći način.

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

Nadalje, tokom serijalizacije, nije navedena kao veličina podataka sizeof cijelu strukturu, a veličina svih polja je fiksna dužina plus veličina stvarno korištenog dijela bafera.

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čajne uštede u prostoru koji zauzimaju ključevi. Međutim, zbog tehničke oblasti nameLength, zadani binarni komparator više nije prikladan za poređenje ključa. Ako ga ne zamijenimo svojim, tada će dužina imena biti prioritetniji faktor u sortiranju od samog imena.

LMDB omogućava svakoj bazi podataka da ima svoju funkciju poređenja ključeva. Ovo se radi pomoću funkcije mdb_set_compare strogo pre otvaranja. Iz očiglednih razloga, baza podataka se ne može mijenjati tokom svog životnog vijeka. Na ulazu, komparator prima dva ključa u binarnom formatu, a na izlazu vraća rezultat poređenja: 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 bezuslovno prebaciti njihovu bajtsku reprezentaciju na tip strukture aplikacije ključa. Ovdje postoji jedna nijansa, ali će o njoj biti riječi malo niže u pododjeljku „Zapisi o čitanju“.

Serijalizacija vrijednosti

Sa ključevima pohranjenih zapisa, LMDB radi izuzetno intenzivno. One se međusobno uspoređuju u okviru bilo koje operacije aplikacije, a performanse cjelokupnog rješenja zavise od brzine komparatora. U idealnom svijetu, zadani binarni komparator bi trebao biti dovoljan za upoređivanje ključeva, ali ako zaista morate koristiti svoj vlastiti, onda bi procedura za deserializaciju ključeva u njemu trebala biti što brža.

Baza podataka nije posebno zainteresirana za vrijednost-dio zapisa (vrijednost). Njegova konverzija iz bajt reprezentacije u objekt se dešava samo kada je već potrebno kod aplikacije, na primjer, da se prikaže na ekranu. Budući da se to dešava relativno rijetko, zahtjevi za brzinom ove procedure nisu toliko kritični, a u njenoj implementaciji smo mnogo slobodniji da se fokusiramo na praktičnost.Na primjer, za serijalizaciju metapodataka o fajlovima koji još nisu preuzeti koristimo NSKeyedArchiver.

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

Međutim, postoje trenuci kada su performanse bitne. Na primjer, kada spremamo meta-informacije o strukturi datoteka korisničkog oblaka, koristimo isti dump memorije objekta. Vrhunac zadatka generiranja njihovog serijaliziranog predstavljanja je činjenica da su elementi direktorija modelirani hijerarhijom klasa.

Za njegovu implementaciju u jeziku C, specifična polja nasljednika izdvajaju se u posebne strukture, a njihova veza sa osnovnim se specificira kroz polje tipa sindikata. Stvarni sadržaj sindikata je specificiran preko 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

Serijski ključ i vrijednost mogu se dodati u prodavnicu. Za to se koristi funkcija mdb_put.

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

U fazi konfiguracije, spremištu se može dozvoliti ili zabraniti pohranjivanje više zapisa sa istim ključem.​​ Ako je dupliranje ključeva zabranjeno, tada prilikom umetanja zapisa možete odrediti da li je ažuriranje već postojećeg zapisa dozvoljeno ili ne. Ako se habanje može dogoditi samo kao rezultat greške u kodu, tada se možete osigurati od toga tako što ćete navesti zastavicu NOOVERWRITE.

Reading Records

Za čitanje zapisa u LMDB koristite funkciju mdb_get. Ako je par ključ/vrijednost predstavljen prethodno izbačenim strukturama, onda ova procedura 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 listing pokazuje kako vam serijalizacija kroz dump strukture omogućava da se riješite dinamičkih alokacija ne samo prilikom pisanja, već i prilikom čitanja podataka. Izvedeno iz funkcije mdb_get pokazivač gleda tačno na adresu virtuelne memorije gde baza podataka pohranjuje bajt reprezentaciju objekta. U stvari, dobijamo neku vrstu ORM-a, gotovo besplatno pružajući vrlo veliku brzinu čitanja podataka. Uz svu ljepotu pristupa, potrebno je zapamtiti nekoliko karakteristika povezanih s njim.

1. Za transakciju samo za čitanje, pokazivač na strukturu vrijednosti garantirano će ostati važeći samo dok se transakcija ne zatvori. Kao što je ranije napomenuto, stranice B-stabla na kojem se nalazi objekat, zahvaljujući principu kopiraj-na-piši, ostaju nepromijenjene sve dok se barem jedna transakcija odnosi na njih. U isto vrijeme, čim se završi posljednja transakcija povezana s njima, stranice se mogu ponovo koristiti za nove podatke. Ako je potrebno da objekti prežive transakciju koja ih je stvorila, onda ih i dalje treba kopirati.
2. Za transakciju readwrite, pokazivač na rezultirajuću strukturnu vrijednost bit će važeći samo do prve procedure modifikacije (upisivanje ili brisanje podataka).
3. Iako je struktura NodeValue nije punopravan, ali skraćen (pogledajte pododjeljak "Naručivanje ključeva pomoću vanjskog komparatora"), preko pokazivača možete lako pristupiti njegovim poljima. Glavna stvar je ne dereferencirati!
4. Ni pod kojim okolnostima struktura se ne smije mijenjati putem primljenog pokazivača. Sve promjene se moraju izvršiti samo putem metode mdb_put. Međutim, uz svu želju da se to učini, to 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 memorije koristeći funkciju mdb_env_set_map_size potpuno poništava sve transakcije i povezane entitete općenito i pokazivače za čitanje objekata posebno.

Konačno, još jedna karakteristika je toliko podmukla da se razotkrivanje njene suštine ne uklapa samo u još jednu tačku. U poglavlju o B-stablu dao sam dijagram organizacije njegovih stranica u memoriji. Iz toga proizilazi da adresa početka bafera sa serijalizovanim podacima može biti apsolutno proizvoljna. Zbog toga, pokazivač na njih, dobijen u strukturi MDB_val i prebačeno na pokazivač na strukturu općenito nije poravnato. Istovremeno, arhitekture nekih čipova (u slučaju iOS-a, ovo je armv7) zahtijevaju da adresa bilo kojeg podatka bude višekratnik veličine strojne riječi, ili, drugim riječima, bitnosti sistema (za armv7, ovo je 32 bita). Drugim riječima, operacija poput *(int *foo)0x800002 na njima se izjednačava sa bekstvom i dovodi do pogubljenja sa presudom EXC_ARM_DA_ALIGN. Postoje dva načina da se izbjegne ovakva tužna sudbina.

Prvi je da prethodno kopirate podatke u poznatu poravnatu 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 da unaprijed obavijestite kompajler da strukture s ključem i vrijednošću možda neće biti poravnate pomoću atributa aligned(1). Na ARM-u isti efekat može biti postići i korištenje atributa packed. S obzirom na to da doprinosi i optimizaciji prostora koji konstrukcija zauzima, ovaj metod mi se čini poželjnijim, iako privodit za povećanje troškova operacija pristupa podacima.

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

Opseg upita

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

Kao dio prikaza liste datoteka u direktoriju, potrebno je pronaći sve ključeve s kojima su pridružene njegove podređene datoteke i mape. U prethodnim pododjeljcima sortirali smo ključeve NodeKey tako da su prvo poređani prema ID-u roditeljskog direktorija. Dakle, tehnički, zadatak dobijanja sadržaja fascikle se svodi na postavljanje kursora na gornju granicu grupe ključeva sa datim prefiksom, nakon čega sledi iteracija do donje granice.

Gornju granicu "na čelu" možete pronaći sekvencijalnom pretragom. Da biste to učinili, kursor se postavlja na početak cijele liste ključeva u bazi podataka, a zatim se povećava sve dok se ispod njega ne pojavi ključ sa identifikatorom roditeljskog direktorija. Ovaj pristup ima 2 očigledna nedostatka:

1. Linearna složenost pretraživanja, iako, kao što znate, u drveću općenito, a posebno u B-stablu, može se obaviti u logaritamskom vremenu.​
2. Uzalud, sve stranice koje prethode željenoj se dižu iz datoteke u glavnu memoriju, što je izuzetno skupo.

Srećom, LMDB API pruža efikasan način za početno pozicioniranje kursora.​ Da biste to učinili, morate formirati takav ključ čija će vrijednost sigurno biti manja ili jednaka ključu koji se nalazi na gornjoj granici intervala . Na primjer, u odnosu na listu na gornjoj slici, možemo napraviti ključ u kojem je polje parentId će biti jednako 2, a svi ostali su ispunjeni nulama. Takav djelomično popunjen ključ se dovodi na ulaz funkcije mdb_cursor_get koji označava rad 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 je pronađena gornja granica grupe ključeva, prelazimo preko nje dok se ne sretnemo ili ključ s drugim parentId, ili se ključevi uopće neće potrošiti.​

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 pomoću mdb_cursor_get, dobijamo ne samo ključ, već i vrijednost. Ako je za ispunjavanje uslova odabira potrebno provjeriti, između ostalog, polja iz vrijednosnog dijela zapisa, onda su ona sama sebi sasvim dostupna bez dodatnih pokreta.

4.3. Modeliranje odnosa između tabela

Do danas smo uspjeli razmotriti sve aspekte dizajniranja i rada sa jednom tabelom bazom podataka. Možemo reći da je tabela skup sortiranih zapisa koji se sastoji od parova ključ/vrijednost istog tipa. Ako prikažete ključ kao pravougaonik i njegovu pridruženu vrijednost kao okvir, dobićete vizuelni dijagram baze podataka.

​

Međutim, u stvarnom životu rijetko je moguće proći sa tako malo krvi. Često je u bazi podataka potrebno, prvo, imati nekoliko tabela, a drugo, izvršiti selekcije u njima po redoslijedu različitom od primarnog ključa. Ovaj posljednji odjeljak posvećen je pitanjima njihovog stvaranja i međusobnog povezivanja.

Indeksne tabele

Aplikacija u oblaku ima odjeljak "Galerija". Prikazuje medijski sadržaj iz cijelog oblaka, sortiran po datumu. Za optimalnu implementaciju takvog odabira, pored glavne tabele potrebno je kreirati još jednu sa novom vrstom ključeva. Oni će sadržavati polje s datumom kreiranja datoteke, koje će služiti kao primarni kriterij sortiranja. Budući da se novi ključevi odnose na iste podatke kao i ključevi u osnovnoj tabeli, oni se nazivaju indeksni ključevi. Na donjoj slici su istaknute narandžastom bojom.

Kako bi se ključevi različitih tabela međusobno odvojili unutar iste baze podataka, dodato je dodatno tehničko polje tableId u sve njih. Postavljajući ga najvišim prioritetom za sortiranje, ključeve ćemo grupirati prvo po tabelama, a već unutar tabela - prema našim pravilima.​

Indeksni ključ se odnosi na iste podatke kao i primarni ključ. Jednostavna implementacija ovog svojstva povezivanjem kopije vrijednosnog dijela primarnog ključa je neoptimalna s nekoliko gledišta odjednom:​

1. U smislu zauzetog prostora, metapodaci mogu biti prilično bogati.
2. Sa stanovišta performansi, pošto ćete prilikom ažuriranja metapodataka čvora morati prepisati dva ključa.
3. Sa stanovišta podrške kodu, na kraju krajeva, ako zaboravimo ažurirati podatke za jedan od ključeva, dobićemo suptilnu grešku nedosljednosti podataka u memoriji.

Zatim ćemo razmotriti kako ukloniti ove nedostatke.

Organizacija relacija između tabela

Obrazac je vrlo prikladan za povezivanje indeksne tablice s glavnom "ključ kao vrijednost". Kao što njegovo ime implicira, dio vrijednosti indeksnog zapisa je kopija vrijednosti primarnog ključa. Ovaj pristup eliminiše sve gore navedene nedostatke povezane sa pohranjivanjem kopije vrijednosnog dijela primarnog zapisa. Jedina naknada je da da biste dobili vrijednost po ključu indeksa, trebate napraviti 2 upita bazi podataka umjesto jednog. Šematski, rezultujuća shema baze podataka je sljedeća.

Drugi obrazac za organiziranje odnosa između tabela je "suvišni ključ". Njegova suština je da se ključu dodaju dodatni atributi koji su potrebni ne za sortiranje, već za ponovno kreiranje pridruženog ključa. Postoje stvarni primjeri njegove upotrebe u aplikaciji Mail.ru Cloud, međutim, kako bi se izbjeglo dublje uranjanje u kontekstu konkretnih iOS okvira, dat ću izmišljen, ali razumljiviji primjer.

Cloud mobilni klijenti imaju stranicu koja prikazuje sve datoteke i mape koje je korisnik podijelio s drugim ljudima. Budući da takvih datoteka ima relativno malo, a uz njih se vezuje mnogo konkretnih informacija o publicitetu (kome se odobrava pristup, s kojim pravima itd.), neće biti racionalno opterećivati ​​ih vrijednosnim dijelom unos u glavnu tabelu. Međutim, ako želite da prikažete takve datoteke van mreže, i dalje ih morate negdje pohraniti. Prirodno rješenje je napraviti zasebnu tablicu za to. U dijagramu ispod, njegov ključ ima prefiks "P", a čuvar mjesta "propname" može se zamijeniti specifičnijom vrijednošću "javne informacije".​

Svi jedinstveni metapodaci, radi kojih je kreirana nova tabela, se pomeraju u vrednostni deo zapisa. Istovremeno, ne želim da dupliram podatke o datotekama i folderima koji su već pohranjeni u glavnoj tabeli. Umjesto toga, redundantni podaci se dodaju ključu "P" u obliku polja "ID čvora" i "vremenska oznaka". Zahvaljujući njima, možete konstruisati indeksni ključ, pomoću kojeg možete dobiti primarni ključ, po kojem, konačno, možete dobiti metapodatke čvora.

Zaključak

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

Rezultati obavljenog posla naišli su na odgovor izvan iOS tima. Trenutno je jedan od glavnih odjeljaka "Files" u Android aplikaciji također prešao na korištenje LMDB, a ostali dijelovi su na putu. Jezik C, u kojem je implementirano skladištenje ključ/vrijednost, bio je dobra pomoć kako bi se u početku aplikacija povezala oko njega na 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 sa Dropboxa, ali to je druga priča.

izvor: www.habr.com