Syksyllä 2019 Mail.ru Cloud iOS -tiimissä tapahtui kauan odotettu tapahtuma. Sovelluksen tilan jatkuvan tallennuksen päätietokanta on tullut erittäin eksoottiseksi mobiilimaailmalle Salaman muistikartoitettu tietokanta (LMDB). Leikkauksen alla tarjoamme sinulle yksityiskohtaisen katsauksen siitä neljässä osassa. Ensinnäkin puhutaan syistä tällaiseen ei-triviaaliseen ja vaikeaan valintaan. Sitten siirrymme tarkastelemaan kolmea LMDB-arkkitehtuurin ytimessä olevaa pilaria: muistikartoitetut tiedostot, B+-puu, kopiointi-kirjoitus-lähestymistapa transaktioiden toteuttamiseen ja moniversio. Lopuksi jälkiruoaksi - käytännön osa. Siinä tarkastellaan, kuinka suunnitella ja toteuttaa tietokantaskeema, jossa on useita taulukoita, mukaan lukien indeksi, matalan tason avainarvon API:n päällä.

Pitoisuus

1. Motivaatio toteuttamiseen
2. LMDB-paikannus
3. LMDB:n kolme pilaria
   3.1. Valas #1. Muistikartoitetut tiedostot
   3.2. Valas #2. B+-puu
   3.3. Valas #3. Kopiointi-kirjoitus
4. Tietoskeeman suunnittelu avainarvosovellusliittymän päälle
   4.1. Perusabstraktioita
   4.2. Taulukkomallinnus
   4.3. Taulukoiden välisten suhteiden mallintaminen

1. Toteutuksen motivaatio

Yhtenä vuonna 2015 vaivauduimme mittaamaan, kuinka usein sovelluksemme käyttöliittymä viivästyy. Teimme tämän syystä. Olemme saaneet useammin valituksia siitä, että joskus sovellus lakkaa vastaamasta käyttäjän toimiin: painikkeita ei voi painaa, luettelot eivät rullaa jne. Tietoja mittausten mekaniikasta kertonut AvitoTechissä, joten annan tässä vain numerojärjestyksen.

Mittaustuloksista tuli meille kylmä suihku. Kävi ilmi, että jäätymisen aiheuttamia ongelmia on paljon enemmän kuin mikään muu. Jos ennen tämän tosiasian ymmärtämistä tärkein tekninen laadun indikaattori oli kaatumaton, niin tarkennuksen jälkeen siirtynyt jäädytettynä ilmaiseksi.

Rakennettuaan kojelauta pakkasilla ja kulutuksen jälkeen määrällinen и laatu syiden analyysissä päävihollinen tuli selväksi - sovelluksen pääsäikeessä toteutettu raskas bisneslogiikka. Luonnollinen reaktio tähän häpeään oli palava halu työntää se työvirtoihin. Tämän ongelman systemaattisesti ratkaisemiseksi turvauduimme monisäikeiseen arkkitehtuuriin, joka perustuu kevyisiin näyttelijöihin. Omistan sen sen mukauttamiseen iOS-maailmaan kaksi lankaa kollektiivisessa Twitterissä ja artikkeli Habresta. Osana nykyistä kerrontaa haluan korostaa niitä päätöksen näkökohtia, jotka vaikuttivat tietokannan valintaan.​

Järjestelmän organisoinnin toimijamalli olettaa, että monisäikeisyydestä tulee sen toinen olemus. Siinä olevat malliobjektit ylittävät mielellään virtarajoja. Ja he eivät tee tätä joskus ja siellä täällä, vaan melkein jatkuvasti ja kaikkialla

Tietokanta on yksi esitetyn kaavion kulmakivikomponenteista. Sen päätehtävänä on toteuttaa makromalli Jaettu tietokanta. Jos yritysmaailmassa sitä käytetään järjestämään tietojen synkronointi palveluiden välillä, niin toimija-arkkitehtuurin tapauksessa - data säikeiden välillä. Tarvitsimme siis tietokannan, joka ei aiheuttaisi vähäisiäkään vaikeuksia työskennellessämme sen kanssa monisäikeisessä ympäristössä. Tämä tarkoittaa erityisesti sitä, että siitä saatujen esineiden on oltava vähintään säikeen turvallisia ja mieluiten täysin muuttumattomia. Kuten tiedät, jälkimmäistä voidaan käyttää samanaikaisesti useista säikeistä turvautumatta mihinkään lukitukseen, millä on suotuisa vaikutus suorituskykyyn.

Toinen merkittävä tietokannan valintaan vaikuttanut tekijä oli pilvisovellusliittymämme. Se sai inspiraationsa gitin hyväksymästä synkronointimenetelmästä. Hänen tavoin pyrimme offline-first API, joka näyttää enemmän kuin sopivalta pilviasiakkaille. Oletettiin, että ne pumppasivat pilven täyden tilan vain kerran, ja sitten synkronointi tapahtuisi suurimmassa osassa tapauksista muutosten käyttöönoton kautta. Valitettavasti tämä mahdollisuus on vielä vain teoreettisella alueella, eivätkä asiakkaat ole oppineet työskentelemään laastarien kanssa käytännössä. Tähän on useita objektiivisia syitä, jotka jätämme taaksemme suluissa, jotta käyttöönotto ei viivästyisi. Nyt paljon kiinnostavampaa ovat oppitunnin opettavat johtopäätökset siitä, mitä tapahtuu, kun API sanoo "A" ja sen kuluttaja ei sano "B".

Joten jos kuvittelet gitin, joka vetämiskomentoa suoritettaessa paikalliseen tilannekuvaan korjauksia käyttämisen sijaan vertaa täyttä tilaa palvelimen täyteen tilaan, sinulla on melko tarkka käsitys siitä, kuinka synkronointi tapahtuu pilvessä. asiakkaita. On helppo arvata, että sen toteuttamiseksi sinun on varattava muistiin kaksi DOM-puuta metatiedoilla kaikista palvelimesta ja paikallisista tiedostoista. Osoittautuu, että jos käyttäjä tallentaa 500 tuhatta tiedostoa pilveen, sen synkronoimiseksi on luotava uudelleen ja tuhottava kaksi puuta, joissa on miljoona solmua. Mutta jokainen solmu on aggregaatti, joka sisältää aliobjektien kaavion. Tässä valossa profiloinnin tuloksia odotettiin. Kävi ilmi, että vaikka yhdistämisalgoritmia ei otettaisi huomioon, itse valtavan määrän pieniä esineitä luominen ja tuhoaminen maksaa melkoisen pennin. Tilannetta pahentaa se, että perussynkronointitoiminto sisältyy suureen määrään käyttäjän skripteistä. Tämän seurauksena korjaamme toisen tärkeän kriteerin tietokannan valinnassa - kyvyn toteuttaa CRUD-operaatioita ilman dynaamista objektien allokointia.

Muut vaatimukset ovat perinteisempiä ja niiden koko luettelo on seuraava.

1. Langan turvallisuus.
2. Monikäsittely. Sanelee halu käyttää samaa tietokanta-instanssia tilan synkronoimiseen paitsi säikeiden välillä, myös pääsovelluksen ja iOS-laajennusten välillä.
3. Mahdollisuus esittää tallennettuja kokonaisuuksia ei-muuttuvina objekteina
4. Ei dynaamisia varauksia CRUD-toiminnoissa.
5. Tapahtumatuki perusominaisuuksille ACID: atomiteetti, johdonmukaisuus, eristys ja luotettavuus.
6. Nopeus suosituimmissa tapauksissa.

Näillä vaatimuksilla SQLite oli ja on edelleen hyvä valinta. Kuitenkin osana vaihtoehtojen tutkimusta törmäsin kirjan "LevelDB:n käytön aloittaminen". Hänen johdolla kirjoitettiin benchmark, jossa verrattiin työn nopeutta eri tietokantojen kanssa todellisissa pilviskenaarioissa. Tulos ylitti villeimmätkin odotuksemme. Suosituimmissa tapauksissa - saat kohdistimen kaikkien tiedostojen lajiteltuun luetteloon ja lajiteltuun luetteloon tietyn hakemiston kaikista tiedostoista - LMDB osoittautui 10 kertaa nopeammaksi kuin SQLite. Valinta tuli selväksi.

2. LMDB-paikannus

LMDB on hyvin pieni kirjasto (vain 10 XNUMX riviä), joka toteuttaa tietokantojen alimman peruskerroksen - tallennustilan.

Yllä oleva kaavio osoittaa, että LMDB:n vertaaminen SQLiteen, joka toteuttaa myös korkeampia tasoja, ei yleensä ole sen oikeampaa kuin SQLiten ja ydintietojen vertailu. Olisi oikeudenmukaisempaa mainita samat tallennusmoottorit tasavertaisina kilpailijoina - BerkeleyDB, LevelDB, Sophia, RocksDB jne. On jopa kehitystä, jossa LMDB toimii SQLiten tallennusmoottorikomponenttina. Ensimmäinen tällainen kokeilu oli vuonna 2012 käytetty kirjoittanut LMDB Howard Chu. Tulokset osoittautui niin kiehtovaksi, että OSS-harrastajat tarttuivat hänen aloitteeseensa ja löysivät jatkoa henkilöstä LumoSQL. Tammikuussa 2020 tämän projektin kirjoittaja oli Den Shearer esitetty se LinuxConfAussa.

LMDB:tä käytetään pääasiassa sovellustietokantojen moottorina. Kirjasto on ulkonäkönsä velkaa kehittäjille OpenLDAP, jotka olivat erittäin tyytymättömiä BerkeleyDB:hen projektinsa perustana. Aloitetaan vaatimattomasta kirjastosta btree, Howard Chu pystyi luomaan yhden aikamme suosituimmista vaihtoehdoista. Hän omisti erittäin hienon raporttinsa tälle tarinalle sekä LMDB:n sisäiselle rakenteelle. "Salama muistikartoitettu tietokanta". Hyvä esimerkki varastotilan valloittamisesta oli Leonid Jurjev (alias yleo) Positive Technologiesilta Highload 2015:n raportissaan "LMDB-moottori on erityinen mestari". Siinä hän puhuu LMDB:stä samanlaisen ReOpenLDAP-toteutustehtävän yhteydessä, ja LevelDB on jo saanut vertailevaa kritiikkiä. Toteutuksen seurauksena Positive Technologiesilla oli jopa aktiivisesti kehittyvä haarukka MDBX erittäin maukkailla ominaisuuksilla, optimoinnilla ja bugikorjauksia.

LMDB:tä käytetään usein sellaisenaan tallennustilana. Esimerkiksi Mozilla Firefox -selain valinnut se useisiin tarpeisiin, ja versiosta 9 alkaen Xcode mieluummin sen SQLite indeksien tallentamiseen.

Moottori on tehnyt jälkensä myös mobiilikehityksen maailmassa. Käytön jälkiä voi olla löytää iOS-asiakassovelluksessa Telegramille. LinkedIn meni vielä pidemmälle ja valitsi LMDB:n oletustallennuspaikaksi kotimaiselle datavälimuistikehykselleen Rocket Datalle, josta kertoi artikkelissaan vuonna 2016.

LMDB taistelee menestyksekkäästi paikasta auringossa BerkeleyDB:n jättämässä markkinarakossa sen jälkeen, kun se tuli Oraclen hallintaan. Kirjastoa rakastetaan nopeudestaan ​​ja luotettavuudestaan, jopa vertaisiinsa verrattuna. Kuten tiedät, ilmaisia ​​lounaita ei ole, ja haluan korostaa kompromissia, joka sinun on kohdattava valitessasi LMDB:n ja SQLiten välillä. Yllä oleva kaavio osoittaa selvästi, kuinka nopeus kasvaa. Ensinnäkin emme maksa ylimääräisistä abstraktiokerroksista levytallennustilan päällä. On selvää, että hyvä arkkitehtuuri ei silti tule toimeen ilman niitä, ja ne näkyvät väistämättä sovelluskoodissa, mutta ne ovat paljon hienovaraisempia. Ne eivät sisällä ominaisuuksia, joita tietty sovellus ei vaadi, esimerkiksi tuki SQL-kielen kyselyille. Toiseksi tulee mahdolliseksi toteuttaa optimaalisesti sovellustoimintojen kartoitus levytallennuspyyntöihin. Jos SQLite työssäni perustuu keskimääräisen sovelluksen keskimääräisiin tilastollisiin tarpeisiin, niin sinä sovelluskehittäjänä tiedät hyvin tärkeimmät työkuormitusskenaariot. Tuottavamman ratkaisun saamiseksi joudut maksamaan korotetun hintalapun sekä alkuperäisen ratkaisun kehittämisestä että sen myöhemmästä tuesta.

3. LMDB:n kolme pilaria

Kun katsottiin LMDB:tä lintuperspektiivistä, oli aika mennä syvemmälle. Seuraavat kolme osaa on omistettu tallennusarkkitehtuurin pääpilareiden analyysille:

1. Muistikartoitetut tiedostot mekanismina työskennellä levyn kanssa ja synkronoida sisäisiä tietorakenteita.
2. B+-puu tallennetun tiedon rakenteen organisaationa.
3. Kopioi kirjoittamisen yhteydessä tapa tarjota ACID-tapahtumaominaisuuksia ja moniversio.

3.1. Valas #1. Muistikartoitetut tiedostot

Muistikartoitetut tiedostot ovat niin tärkeä arkkitehtoninen elementti, että ne näkyvät jopa arkiston nimessä. Välimuistiin ja tallennettujen tietojen synkronointiin liittyvät ongelmat jätetään kokonaan käyttöjärjestelmälle. LMDB ei sisällä välimuistia itsessään. Tämä on kirjoittajan tietoinen päätös, koska tietojen lukeminen suoraan kartoitetuista tiedostoista antaa mahdollisuuden leikata monia kulmia moottorin toteutuksessa. Alla on kaikkea muuta kuin täydellinen luettelo joistakin niistä.

1. Tallennustietojen johdonmukaisuuden ylläpitäminen useista prosesseista käsiteltäessä tulee käyttöjärjestelmän vastuulle. Seuraavassa osiossa tätä mekaniikkaa käsitellään yksityiskohtaisesti ja kuvien kera.
2. Välimuistien puuttuminen eliminoi LMDB:n kokonaan dynaamisiin varauksiin liittyvistä yleiskustannuksista. Tietojen lukeminen tarkoittaa käytännössä osoittimen asettamista oikeaan osoitteeseen virtuaalimuistissa, eikä mitään muuta. Se kuulostaa tieteiskirjallisuudesta, mutta tallennuslähteen lähdekoodissa kaikki calloc-kutsut keskittyvät tallennusasetustoimintoon.
3. Välimuistien puuttuminen tarkoittaa myös niiden pääsyn synkronointiin liittyvien lukkojen puuttumista. Lukijat, joita voi olla mielivaltainen määrä lukijoita samaan aikaan, eivät kohtaa yhtäkään mutexia matkalla dataan. Tästä johtuen lukunopeudella on ihanteellinen lineaarinen skaalautuvuus suoritinten lukumäärän perusteella. LMDB:ssä vain muokkaustoiminnot synkronoidaan. Kirjoittaja voi olla vain yksi kerrallaan.
4. Vähäinen välimuisti- ja synkronointilogiikka eliminoi monisäikeisessä ympäristössä työskentelemiseen liittyvät erittäin monimutkaiset virheet. Usenix OSDI 2014 -konferenssissa oli kaksi mielenkiintoista tietokantatutkimusta: "Kaikki tiedostojärjestelmät eivät ole samanarvoisia: kaatumisyhdenmukaisten sovellusten luomisen monimutkaisuus" и "Tietokantojen kiduttaminen huvin ja voiton vuoksi". Niistä voit poimia tietoa sekä LMDB:n ennennäkemättömästä luotettavuudesta että ACID-tapahtumaominaisuuksien lähes virheettömästä toteutuksesta, joka on ylivoimainen SQLiteen.
5. LMDB:n minimalismi mahdollistaa sen, että sen koodin koneesitys sijoittuu kokonaan prosessorin L1-välimuistiin seuraavilla nopeusominaisuuksilla.

Valitettavasti iOS:ssä, muistikartoitettujen tiedostojen kanssa, kaikki ei ole niin pilvetöntä kuin haluaisimme. Jotta voidaan puhua niihin liittyvistä puutteista tietoisemmin, on muistettava yleiset periaatteet tämän mekanismin toteuttamisesta käyttöjärjestelmissä.

Yleistä tietoa muistikartoitetuista tiedostoista

Käyttöjärjestelmä liittää jokaiseen suoritettavaan sovellukseen kokonaisuuden, jota kutsutaan prosessiksi. Jokaiselle prosessille on varattu jatkuva osoitteiden valikoima, johon se sijoittaa kaiken, mitä se tarvitsee toimiakseen. Alimmissa osoitteissa on osiot, joissa on koodia ja kovakoodattua dataa ja resursseja. Seuraavaksi tulee kasvava dynaamisen osoiteavaruuden lohko, jonka tunnemme hyvin nimellä pino. Se sisältää ohjelman toiminnan aikana näkyvien entiteettien osoitteet. Yläosassa on sovelluspinon käyttämä muistialue. Se joko kasvaa tai supistuu, toisin sanoen sen koolla on myös dynaaminen luonne. Jotta pino ja pino eivät työntäisi ja häiritse toisiaan, ne sijaitsevat osoiteavaruuden eri päissä. Kahden dynaamisen osan välissä ylä- ja alaosassa on reikä. Käyttöjärjestelmä käyttää tämän keskiosan osoitteita liittääkseen prosessiin erilaisia ​​kokonaisuuksia. Erityisesti se voi liittää tietyn jatkuvan joukon osoitteita levyllä olevaan tiedostoon. Tällaista tiedostoa kutsutaan muistimapped.

Prosessille varattu osoitetila on valtava. Teoriassa osoitteiden määrää rajoittaa vain osoittimen koko, jonka määrää järjestelmän bittikapasiteetti. Jos fyysinen muisti yhdistettäisiin siihen 1-1, niin aivan ensimmäinen prosessi ahmiisi koko RAM-muistin, eikä mistään monitoimista puhuisi.​

Kokemuksemme perusteella tiedämme kuitenkin, että nykyaikaiset käyttöjärjestelmät voivat suorittaa samanaikaisesti niin monta prosessia kuin halutaan. Tämä on mahdollista, koska ne varaavat paljon muistia vain paperilla oleville prosesseille, mutta todellisuudessa he lataavat fyysiseen päämuistiin vain sen osan, jolla on kysyntää tässä ja nyt. Siksi prosessiin liittyvää muistia kutsutaan virtuaaliseksi.

Käyttöjärjestelmä järjestää virtuaalisen ja fyysisen muistin tietyn kokoisiksi sivuiksi. Heti kun tietylle virtuaalimuistisivulle on kysyntää, käyttöjärjestelmä lataa sen fyysiseen muistiin ja täsmäää ne erityiseen taulukkoon. Jos vapaita paikkoja ei ole, yksi aiemmin ladatuista sivuista kopioidaan levylle ja tilalle tulee kysytty. Tätä menettelyä, johon palaamme pian, kutsutaan vaihtamiseksi. Alla oleva kuva havainnollistaa kuvattua prosessia. Sille ladattiin sivu A osoitteella 0 ja sijoitettiin päämuistisivulle osoitteella 4. Tämä seikka näkyi vastaavuustaulukossa solussa numero 0.​

Tarina on täsmälleen sama muistiin yhdistettyjen tiedostojen kanssa. Loogisesti ne ovat oletettavasti jatkuvasti ja kokonaan virtuaalisessa osoiteavaruudessa. He kuitenkin syöttävät fyysiseen muistiin sivu sivulta ja vain pyynnöstä. Tällaisten sivujen muuttaminen synkronoidaan levyllä olevan tiedoston kanssa. Tällä tavalla voit suorittaa tiedoston I/O:n yksinkertaisesti käsittelemällä muistissa olevia tavuja - käyttöjärjestelmän ydin siirtää kaikki muutokset automaattisesti lähdetiedostoon.​
----
Alla oleva kuva osoittaa, kuinka LMDB synkronoi tilansa työskennellessään tietokannan kanssa eri prosesseista. Kartoittamalla eri prosessien virtuaalimuistin samaan tiedostoon velvoitamme käyttöjärjestelmän transitiivisesti synkronoimaan tietyt osoiteavaruuksiensa lohkot keskenään, mistä LMDB näyttää.​
----

Tärkeä vivahde on, että LMDB oletusarvoisesti muokkaa datatiedostoa kirjoitusjärjestelmän kutsumekanismin kautta ja näyttää itse tiedoston vain luku -tilassa. Tällä lähestymistavalla on kaksi tärkeää seurausta.

Ensimmäinen seuraus on yhteinen kaikille käyttöjärjestelmille. Sen ydin on lisätä suojausta tietokannan tahattomalta vahingoittamiselta väärän koodin avulla. Kuten tiedät, prosessin suoritettavat käskyt voivat käyttää tietoja vapaasti mistä tahansa sen osoiteavaruudesta. Samaan aikaan, kuten juuri muistimme, tiedoston näyttäminen luku-kirjoitustilassa tarkoittaa, että mikä tahansa käsky voi myös muokata sitä. Jos hän tekee tämän vahingossa ja yrittää esimerkiksi todella korvata taulukkoelementin olemattomassa indeksissä, hän voi vahingossa muuttaa tähän osoitteeseen yhdistetyn tiedoston, mikä johtaa tietokannan vioittumiseen. Jos tiedosto näytetään vain luku -tilassa, yritys muuttaa vastaavaa osoiteavaruutta johtaa ohjelman hätäkatkaisuun signaalilla SIGSEGV, ja tiedosto säilyy ennallaan.

Toinen seuraus on jo iOS-kohtainen. Kirjoittaja tai muut lähteet eivät mainitse sitä erikseen, mutta ilman sitä LMDB ei olisi sopiva käytettäväksi tässä mobiilikäyttöjärjestelmässä. Seuraava osa on omistettu sen tarkasteluun.

Muistikartoitettujen tiedostojen tiedot iOS:ssä

WWDC:ssä vuonna 2018 oli upea raportti "iOS Memory Deep Dive". Se kertoo meille, että iOS:ssä kaikki fyysisessä muistissa olevat sivut ovat yksi kolmesta tyypistä: likaiset, pakatut ja puhtaat.

Puhdas muisti on kokoelma sivuja, jotka voidaan poistaa kivuttomasti fyysisestä muistista. Niiden sisältämät tiedot voidaan tarvittaessa ladata uudelleen alkuperäisistä lähteistään. Vain luku -muistiin yhdistetyt tiedostot kuuluvat tähän luokkaan. iOS ei pelkää poistaa tiedostoon yhdistettyjä sivuja muistista milloin tahansa, koska ne taatusti synkronoidaan levyllä olevan tiedoston kanssa.
----
Kaikki muokatut sivut päätyvät likaiseen muistiin riippumatta siitä, missä ne alun perin sijaitsevat. Erityisesti muistiin yhdistetyt tiedostot, joita on muokattu kirjoittamalla niihin liittyvään virtuaalimuistiin, luokitellaan tällä tavalla. LMDB:n avaaminen lipulla MDB_WRITEMAP, kun olet tehnyt siihen muutoksia, voit varmistaa tämän henkilökohtaisesti

​Heti kun sovellus alkaa kuluttaa liikaa fyysistä muistia, iOS kohdistaa sen likaiselle sivupakkaukselle. Likaisen ja pakatun sivun kokonaismuisti muodostaa sovelluksen ns. muistijalanjäljen. Kun se saavuttaa tietyn kynnysarvon, OOM-killer-järjestelmän demoni tulee prosessin jälkeen ja lopettaa sen väkisin. Tämä on iOS:n erikoisuus työpöytäkäyttöjärjestelmiin verrattuna. Sitä vastoin iOS:ssä ei ole mahdollista vähentää muistin jalanjälkeä vaihtamalla sivuja fyysisestä muistista levylle. Syitä voidaan vain arvailla. Ehkä prosessi, jossa sivut siirretään intensiivisesti levylle ja takaisin, on liian energiaa vievää mobiililaitteille, tai iOS säästää resurssit solujen uudelleenkirjoittamiseen SSD-asemilla, tai ehkä suunnittelijat eivät olleet tyytyväisiä järjestelmän yleiseen suorituskykyyn, jossa kaikki on vaihdetaan jatkuvasti. Oli miten oli, tosiasia pysyy tosiasiana.

Hyvä uutinen, joka mainittiin jo aiemmin, on, että LMDB ei oletuksena käytä mmap-mekanismia tiedostojen päivittämiseen. Tämä tarkoittaa, että iOS luokittelee näytettävät tiedot puhtaaksi muistiksi, eivätkä ne vaikuta muistin jalanjälkeen. Voit tarkistaa tämän käyttämällä Xcode-työkalua nimeltä VM Tracker. Alla oleva kuvakaappaus näyttää pilvisovelluksen iOS-virtuaalimuistin tilan käytön aikana. Alussa siihen alustettiin 2 LMDB-instanssia. Ensimmäinen sai näyttää tiedostonsa 1 gigatavua virtuaalimuistia, toinen - 512 MB. Huolimatta siitä, että molemmat muistit vievät tietyn määrän pysyvää muistia, kumpikaan niistä ei vaikuta likaiseen kokoon.

Ja nyt on huonojen uutisten aika. 64-bittisten työpöytäkäyttöjärjestelmien vaihtomekanismin ansiosta jokainen prosessi voi varata niin paljon virtuaalista osoitetilaa kuin sen mahdollisen swapin vapaa kiintolevytila ​​sallii. Swapin korvaaminen pakkauksella iOS:ssä vähentää radikaalisti teoreettista maksimiarvoa. Nyt kaikkien elävien prosessien täytyy mahtua päämuistiin (lue RAM) ja kaikki, jotka eivät mahdu, on pakotettava lopettamaan. Tämä on todettu edellä mainitulla tavalla raportti, ja in virallinen dokumentaatio. Tämän seurauksena iOS rajoittaa voimakkaasti mmap:n kautta allokoitavissa olevan muistin määrää. Tässä täällä Voit tarkastella empiirisiä rajoja muistin määrälle, joka voidaan varata eri laitteille käyttämällä tätä järjestelmäkutsua. Modernimmissa älypuhelinmalleissa iOS on antelias 2 gigatavua ja iPadin huippuversioissa - 4. Käytännössä on tietysti keskityttävä alhaisimpiin tuettuihin laitemalleihin, joissa kaikki on hyvin surullista. Vielä pahempaa, kun tarkastelet sovelluksen muistitilaa VM Trackerissa, huomaat, että LMDB ei ole kaukana ainoasta, joka vaatii muistikartoitettua muistia. Hyvät palat syövät pois järjestelmäallokaattorit, resurssitiedostot, kuvakehykset ja muut pienemmät saalistajat.

Pilvessä suoritettujen kokeiden tulosten perusteella päädyimme seuraaviin kompromissiarvoihin LMDB:n varaaman muistin osalta: 384 megatavua 32-bittisille laitteille ja 768 megatavua 64-bittisille laitteille. Kun tämä tilavuus on käytetty loppuun, kaikki muokkaustoimenpiteet alkavat päättyä koodiin MDB_MAP_FULL. Havaitsemme tällaisia ​​virheitä seurannassamme, mutta ne ovat niin pieniä, että ne voidaan tässä vaiheessa jättää huomiotta.

Ei-ilmeinen syy tallennustilan liialliselle muistinkulutukselle voi olla pitkäikäiset tapahtumat. Ymmärtääksemme, miten nämä kaksi ilmiötä liittyvät toisiinsa, meitä autetaan ottamalla huomioon LMDB:n kaksi jäljellä olevaa pilaria.

3.2. Valas #2. B+-puu

Jotta avainarvovaraston päällä olevia taulukoita voidaan emuloida, sen API:ssa on oltava seuraavat toiminnot:

1. Uuden elementin lisääminen.
2. Etsi elementtiä annetulla avaimella.
3. Elementin poistaminen.
4. Toista näppäinten aikavälit niiden lajittelujärjestyksessä.

Yksinkertaisin tietorakenne, jolla voidaan helposti toteuttaa kaikki neljä toimintoa, on binäärihakupuu. Jokainen sen solmu edustaa avainta, joka jakaa koko lapsiavainten osajoukon kahdeksi alipuuksi. Vasen sisältää ne, jotka ovat pienempiä kuin vanhempi, ja oikea sisältää ne, jotka ovat suurempia. Tilatun avainsarjan saaminen onnistuu yhdellä klassisista puun läpikäymisestä.​

Binääripuilla on kaksi perusvirhettä, jotka estävät niitä toimimasta tehokkaina levypohjaisena tietorakenteena. Ensinnäkin niiden tasapainon aste on arvaamaton. On olemassa huomattava riski saada puita, joissa eri oksien korkeudet voivat vaihdella suuresti, mikä huonontaa merkittävästi haun algoritmista monimutkaisuutta odotettuihin verrattuna. Toiseksi solmujen välisten ristilinkkien runsaus vie binääripuilta paikallisuuden muistissa, ja läheiset solmut (niiden välisten yhteyksien suhteen) voivat sijaita täysin eri sivuilla virtuaalimuistissa. Tämän seurauksena jopa yksinkertainen puun useiden vierekkäisten solmujen läpikäynti voi vaatia käymistä vastaavalla määrällä sivuja. Tämä on ongelma myös silloin, kun puhutaan binääripuiden tehokkuudesta muistin sisäisenä tietorakenteena, koska sivujen jatkuva pyörittäminen prosessorin välimuistissa ei ole halpaa nautintoa. Kun on kyse solmuihin liittyvien sivujen usein noutamisesta levyltä, tilanne muuttuu täydelliseksi valitettavaa.

B-puut, jotka ovat binääripuiden evoluutio, ratkaisevat edellisessä kappaleessa tunnistetut ongelmat. Ensinnäkin ne tasapainottavat itsensä. Toiseksi, jokainen solmunsa jakaa lapsiavaimia ei kahdeksi, vaan M:ksi järjestetyksi osajoukoksi, ja luku M voi olla melko suuri, useiden satojen tai jopa tuhansien luokkaa.

Siten:

1. Jokainen solmu sisältää suuren määrän jo tilattuja avaimia ja puut ovat hyvin lyhyitä.
2. Puu hankkii sijainnin sijainnin ominaisuuden muistissa, koska arvoltaan lähellä olevat avaimet sijaitsevat luonnollisesti vierekkäin samoissa tai vierekkäisissä solmuissa.
3. Siirtosolmujen määrä laskettaessa puuta hakutoiminnon aikana vähenee.
4. Aluekyselyiden aikana luettavien kohdesolmujen määrä vähenee, koska jokainen niistä sisältää jo suuren määrän tilattuja avaimia.

LMDB käyttää B-puun muunnelmaa, jota kutsutaan B+-puuksi tietojen tallentamiseen. Yllä oleva kaavio näyttää siinä olevat kolmen tyyppiset solmut:

1. Yläosassa on juuri. Se ei konkretisoi muuta kuin käsitettä tietokannasta varaston sisällä. Yhdessä LMDB-ilmentymässä voit luoda useita tietokantoja, jotka jakavat kartoitetun virtuaalisen osoitetilan. Jokainen niistä alkaa omasta juurestaan.
2. Alimmalla tasolla ovat lehdet. Ne ja vain ne sisältävät tietokantaan tallennetut avainarvo-parit. Tämä on muuten B+-puiden erikoisuus. Jos tavallinen B-puu tallentaa arvoosia kaikkien tasojen solmuihin, niin B+-variaatio on vain alimmassa. Kun tämä tosiasia on korjattu, kutsumme edelleen LMDB:ssä käytettävää puun alatyyppiä yksinkertaisesti B-puuksi.
3. Juuren ja lehtien välissä on 0 tai useampia teknisiä tasoja navigointisolmuilla (haara). Heidän tehtävänsä on jakaa lajiteltu avainsarja lehtien kesken.

Fyysisesti solmut ovat ennalta määrätyn pituisia muistilohkoja. Niiden koko on moninkertainen käyttöjärjestelmän muistisivujen koon kanssa, josta keskustelimme edellä. Solmun rakenne on esitetty alla. Otsikko sisältää metatietoja, joista ilmeisin on esimerkiksi tarkistussumma. Seuraavaksi tulee tietoa siirtymistä, joissa dataa sisältävät solut sijaitsevat. Tiedot voivat olla joko avaimia, jos puhutaan navigointisolmuista, tai kokonaisia ​​avainarvopareja lehtien tapauksessa.​ Sivujen rakenteesta voit lukea lisää työstä "Tehokkaiden avainarvokauppojen arviointi".

Käsiteltyään sivusolmujen sisäistä sisältöä esitämme edelleen LMDB B-puun yksinkertaistetusti seuraavassa muodossa.

Sivut, joissa on solmuja, sijaitsevat peräkkäin levyllä. Suuremmat numeroidut sivut sijaitsevat tiedoston lopussa. Ns. metasivulla on tietoa siirtymistä, joilla kaikkien puiden juuret löytyvät. Tiedostoa avattaessa LMDB skannaa tiedoston sivulta sivulta alusta loppuun etsiessään kelvollista metasivua ja löytää sen kautta olemassa olevat tietokannat.​

Nyt, kun meillä on käsitys tiedon organisoinnin loogisesta ja fyysisestä rakenteesta, voimme siirtyä tarkastelemaan LMDB:n kolmatta pilaria. Sen avulla kaikki tallennusmuutokset tapahtuvat transaktiossa ja erillään toisistaan, mikä antaa tietokannalle kokonaisuutena moniversion ominaisuuden.

3.3. Valas #3. Kopiointi-kirjoitus

Jotkut B-puun toiminnot sisältävät useita muutoksia sen solmuihin. Yksi esimerkki on uuden avaimen lisääminen solmuun, joka on jo saavuttanut maksimikapasiteettinsa. Tässä tapauksessa on ensinnäkin tarpeen jakaa solmu kahteen osaan ja toiseksi lisätä linkki uuteen orastavaan alisolmuun sen yläosassa. Tämä menettely on mahdollisesti erittäin vaarallinen. Jos jostain syystä (onnettomuus, sähkökatkos jne.) vain osa sarjan muutoksista tapahtuu, puu pysyy epäjohdonmukaisessa tilassa.

Eräs perinteinen ratkaisu tietokannan vikasietoiseksi tekemiseen on lisätä levyllä oleva ylimääräinen tietorakenne B-puun viereen - tapahtumaloki, joka tunnetaan myös nimellä WAL (write-ahead log). Se on tiedosto, jonka loppuun aiottu operaatio kirjoitetaan tarkasti ennen itse B-puun muokkaamista. Jos siis itsediagnoosin aikana havaitaan tietojen vioittuminen, tietokanta etsii lokia saadakseen itsensä kuntoon.

LMDB on valinnut toisen menetelmän vikasietomekanismiksi, nimeltään kopiointi-kirjoitus. Sen olemus on, että olemassa olevan sivun tietojen päivittämisen sijaan se ensin kopioi sen kokonaan ja tekee kaikki muutokset kopioon.​

Seuraavaksi, jotta päivitetyt tiedot ovat saatavilla, on tarpeen vaihtaa linkki solmuun, joka on tullut ajankohtaiseksi sen pääsolmussa. Koska sitä on myös muokattava tätä varten, se myös kopioidaan etukäteen. Prosessi jatkuu rekursiivisesti aina juureen asti. Viimeinen muuttuva asia on metasivun tiedot.​​

Jos prosessi yhtäkkiä kaatuu päivityksen aikana, uutta metasivua ei joko luoda tai sitä ei kirjoiteta levylle kokonaan ja sen tarkistussumma on virheellinen. Kummassakaan näistä kahdesta tapauksesta uusille sivuille ei päästä, mutta vanhoihin sivuihin ei pääse. Tämä eliminoi LMDB:n tarpeen kirjoittaa eteenpäin lokia tietojen johdonmukaisuuden ylläpitämiseksi. Käytännössä edellä kuvattu levyn tallennusrakenne ottaa samalla tehtävänsä. Eksplisiittisen tapahtumalokin puuttuminen on yksi LMDB:n ominaisuuksista, joka tarjoaa suuren tiedonlukunopeuden.​

Tuloksena oleva malli, jota kutsutaan vain liittäviksi B-puuksi, tarjoaa luonnollisesti tapahtuman eristämisen ja moniversion. LMDB:ssä jokainen avoin tapahtuma liittyy kulloinkin asiaankuuluvaan puun juureen. Ennen kuin tapahtuma on suoritettu loppuun, siihen liitetyn puun sivuja ei koskaan muuteta tai käytetä uudelleen tietojen uusiin versioihin. Näin ollen voit työskennellä niin kauan kuin haluat juuri sillä datajoukolla, joka sillä hetkellä oli merkityksellistä. tapahtuma avattiin, vaikka tallennustilaa päivitetään aktiivisesti tällä hetkellä. Tämä on moniversion ydin, mikä tekee LMDB:stä ihanteellisen tietolähteen rakkaallemme UICollectionView. Kun tapahtuma on avattu, sovelluksen muistijalanjälkeä ei tarvitse kasvattaa pumppaamalla hätäisesti nykyiset tiedot johonkin muistirakenteeseen, koska pelkäävät jäävänsä ilman. Tämä ominaisuus erottaa LMDB:n samasta SQLitesta, joka ei voi ylpeillä tällaisesta täydellisestä eristäytymisestä. Kun olet avannut kaksi tapahtumaa jälkimmäisessä ja poistanut tietyn tietueen toisesta, ei ole enää mahdollista saada samaa tietuetta toisessa jäljellä olevassa tapahtumassa.

​Kolikon kääntöpuoli on mahdollisesti huomattavasti suurempi virtuaalimuistin kulutus. Dia näyttää miltä tietokantarakenne näyttää, jos sitä muokataan samanaikaisesti kolmen avoimen lukutapahtuman kanssa tarkasteltaessa tietokannan eri versioita. Koska LMDB ei voi käyttää uudelleen nykyisiin tapahtumiin liittyvistä juurista tavoitettavia solmuja, myymälällä ei ole muuta vaihtoehtoa kuin varata toinen neljäs juuri muistista ja kloonata muokatut sivut sen alle.​

Tässä olisi hyödyllistä palauttaa muistiin yhdistettyjä tiedostoja käsittelevä osio. Näyttää siltä, ​​​​että virtuaalimuistin lisäkulutuksen ei pitäisi huolestua meitä paljon, koska se ei vaikuta sovelluksen muistijalanjälkeen. Samalla kuitenkin todettiin, että iOS on erittäin niukka sen allokoinnissa, emmekä voi, kuten palvelimella tai työpöydällä, tarjota 1 teratavun LMDB-aluetta emmekä ajattele tätä ominaisuutta ollenkaan. Jos mahdollista, sinun tulee yrittää tehdä tapahtumien kesto mahdollisimman lyhyeksi.

4. Tietoskeeman suunnittelu avainarvosovellusliittymän päälle

Aloitetaan API-analyysi tarkastelemalla LMDB:n tarjoamia perusabstraktioita: ympäristö ja tietokannat, avaimet ja arvot, tapahtumat ja kursorit.

Huomautus koodiluetteloista

Kaikki julkisen LMDB API:n toiminnot palauttavat työnsä tuloksen virhekoodin muodossa, mutta kaikissa myöhemmissä listauksissa sen tarkistus on jätetty pois lyhyyden vuoksi.​ Käytämme jopa omiamme vuorovaikutuksessa arkiston kanssa. haarukka C++ kääreet lmdbxx, jossa virheet materialisoituvat C++-poikkeuksina.

Nopeimpana tapana yhdistää LMDB iOS- tai macOS-projektiin, suosittelen CocoaPodiani. POSLMDB.

4.1. Perusabstraktiot

Ympäristö

Rakenne MDB_env on LMDB:n sisäisen tilan arkisto. Etuliitteenä oleva toimintoperhe mdb_env voit määrittää joitakin sen ominaisuuksia. Yksinkertaisimmassa tapauksessa moottorin alustus näyttää tältä.

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

Mail.ru Cloud -sovelluksessa muutimme vain kahden parametrin oletusarvoja.

Ensimmäinen on virtuaalisen osoiteavaruuden koko, johon tallennustiedosto on yhdistetty. Valitettavasti jopa samassa laitteessa tietty arvo voi vaihdella merkittävästi ajon mukaan. Tämän iOS-ominaisuuden huomioon ottamiseksi enimmäistallennustilavuus valitaan dynaamisesti. Tietystä arvosta alkaen se puolitetaan peräkkäin funktioon asti mdb_env_open ei palauta erilaista tulosta kuin ENOMEM. Teoriassa on myös päinvastainen tapa - varaa ensin minimimuisti moottorille ja sitten, kun virheitä vastaanotetaan, MDB_MAP_FULL, lisää sitä. Se on kuitenkin paljon hankalampaa. Syynä on, että menettely muistin uudelleenallokoimiseksi (uudelleenkartoitus) funktion avulla mdb_env_set_map_size mitätöi kaikki entiteetit (kursorit, tapahtumat, avaimet ja arvot), jotka on aiemmin vastaanotettu moottorista. Tämän tapahtumien käänteen ottaminen huomioon koodissa johtaa sen merkittävään monimutkaisuuteen. Jos virtuaalimuisti on sinulle kuitenkin erittäin tärkeä, tämä voi olla syy katsoa lähemmin kauas eteenpäin mennyttä haarukkaa MDBX, jossa ilmoitettujen ominaisuuksien joukossa on "automaattinen tietokannan koon säätö lennossa".

Toinen parametri, jonka oletusarvo ei sopinut meille, säätelee kierteen turvallisuuden varmistamisen mekaniikkaa. Valitettavasti ainakin iOS 10:ssä on ongelmia säikeen paikallisen tallennustilan tuen kanssa. Tästä syystä yllä olevassa esimerkissä arkisto avataan lipulla MDB_NOTLS. Tämän lisäksi se oli myös välttämätöntä haarukka C++-kääre lmdbxxleikata pois muuttujia tällä määritteellä ja siinä.

tietokannat

Tietokanta on erillinen B-puu-instanssi, josta keskustelimme edellä. Sen avaaminen tapahtuu tapahtuman sisällä, mikä voi aluksi tuntua hieman oudolta.

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

Itse asiassa LMDB:n tapahtuma on tallennusyksikkö, ei tietty tietokantayksikkö. Tämän konseptin avulla voit suorittaa atomioperaatioita eri tietokannoissa sijaitseville entiteeteille. Teoriassa tämä avaa mahdollisuuden mallintaa taulukoita eri tietokantojen muodossa, mutta aikoinaan valitsin eri polun, jota kuvataan yksityiskohtaisesti alla.

Avaimet ja arvot

Rakenne MDB_val mallintaa sekä avaimen että arvon käsitettä. Arkistolla ei ole aavistustakaan niiden semantiikasta. Hänelle jokin muu on vain joukko tietyn kokoisia tavuja. Avaimen enimmäiskoko on 512 tavua.

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

Vertailun avulla kauppa lajittelee avaimet nousevaan järjestykseen. Jos et korvaa sitä omallasi, käytetään oletusarvoa, joka lajittelee ne tavu kerrallaan leksikografiseen järjestykseen.​

Liiketoimi

Tapahtuman rakenne on kuvattu yksityiskohtaisesti kohdassa edellinen luku, joten tässä toistan lyhyesti niiden tärkeimmät ominaisuudet:

1. Tukee kaikkia perusominaisuuksia ACID: atomiteetti, johdonmukaisuus, eristys ja luotettavuus. En voi olla huomaamatta, että macOS:ssä ja iOS:ssä on kestävyyteen liittyvä virhe, joka korjattiin MDBX:ssä. Niistä voit lukea lisää LUEMINUT.
2. Lähestymistapa monisäikeiseen on kuvattu "yksi kirjoittaja / useita lukijoita" -kaaviolla. Kirjoittajat estävät toisensa, mutta eivät lukijoita. Lukijat eivät estä kirjoittajia tai toisiaan.
3. Tuki sisäkkäisille tapahtumille.
4. Moniversion tuki.

LMDB:n moniversio on niin hyvä, että haluan esitellä sen käytännössä. Alla olevasta koodista näet, että jokainen tapahtuma toimii tarkalleen sen tietokannan version kanssa, joka oli voimassa sen avaushetkellä, ja se on täysin eristetty kaikista myöhemmistä muutoksista. Tallennuksen alustaminen ja testitietueen lisääminen siihen ei edusta mitään mielenkiintoista, joten nämä rituaalit jätetään spoilerin alle.

Testimerkinnän lisääminen

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

Suosittelen, että kokeilet samaa temppua SQLiten kanssa ja katsot mitä tapahtuu.

Moniversio tuo erittäin mukavia etuja iOS-kehittäjän elämään. Tämän ominaisuuden avulla voit helposti ja luonnollisesti säätää näyttölomakkeiden tietolähteen päivitysnopeutta käyttökokemuksen perusteella. Otetaan esimerkiksi Mail.ru Cloud -sovelluksen ominaisuus, kuten sisällön automaattinen lataaminen järjestelmän mediagalleriasta. Hyvällä yhteydellä asiakas pystyy lisäämään palvelimelle useita kuvia sekunnissa. Jos päivität jokaisen latauksen jälkeen UICollectionView Kun mediasisältö on käyttäjän pilvessä, voit unohtaa 60 fps ja sujuvan vierityksen tämän prosessin aikana. Toistuvien näyttöpäivitysten estämiseksi sinun on jotenkin rajoitettava tietojen muutosnopeutta taustalla UICollectionViewDataSource.

Jos tietokanta ei tue moniversiota ja voit työskennellä vain nykyisen tilan kanssa, sinun on kopioitava se joko johonkin muistissa olevaan tietorakenteeseen tai väliaikaiseen taulukkoon, jotta voit luoda aikastabiilin tilannevedoksen tiedoista. Mikä tahansa näistä lähestymistavoista on erittäin kallista. Muistiin tallennettaessa saamme sekä muistiin liittyviä kustannuksia, jotka aiheutuvat rakennettujen objektien tallentamisesta, että ajallisesti, jotka liittyvät redundanttisiin ORM-muunnoksiin. Mitä tulee väliaikaiseen pöytään, tämä on vielä kalliimpi ilo, mikä on järkevää vain ei-triviaalisissa tapauksissa.

LMDB:n moniversioratkaisu ratkaisee vakaan tietolähteen ylläpidon ongelman erittäin tyylikkäällä tavalla. Riittää, kun avaat tapahtuman ja voila - kunnes saamme sen valmiiksi, tietojoukko on taatusti korjattu. Sen päivitysnopeuden logiikka on nyt kokonaan esityskerroksen käsissä ilman merkittäviä resursseja.

Kohdistimet

Kohdistimet tarjoavat mekanismin avainarvo-parien järjelliseen iterointiin B-puun läpikäymisen kautta. Ilman niitä olisi mahdotonta mallintaa tehokkaasti tietokannan taulukoita, joihin nyt käännymme.

4.2. Taulukkomallinnus

Avainjärjestyksen ominaisuus mahdollistaa korkean tason abstraktion, kuten taulukon, rakentamisen perusabstrahojen päälle. Tarkastellaan tätä prosessia käyttämällä esimerkkiä pilviasiakkaan päätaulukosta, joka tallentaa välimuistiin tiedot kaikista käyttäjän tiedostoista ja kansioista.

Taulukkokaavio

Yksi yleisimmistä skenaarioista, joihin kansiopuulla varustettu taulukkorakenne tulisi räätälöidä, on kaikkien tietyssä hakemistossa olevien elementtien valinta. Adjacency-luettelo. Jotta se voidaan toteuttaa avainarvotallennustilan päällä, tiedostojen ja kansioiden avaimet on lajiteltava siten, että ne ryhmitellään emohakemistoon kuulumisensa perusteella. Lisäksi, jotta hakemiston sisältö näytetään Windows-käyttäjälle tutussa muodossa (ensin kansiot, sitten tiedostot, molemmat aakkosjärjestykseen), on avaimeen sisällytettävä vastaavat lisäkentät.

​Alla oleva kuva näyttää, miltä avainten esitys tavutaulukon muodossa voisi näyttää käsiteltävän tehtävän perusteella. Tavut emohakemiston tunnisteella (punainen) sijoitetaan ensin, sitten tyypin kanssa (vihreä) ja häntään nimen kanssa (sininen). Kun ne on lajiteltu oletusarvoisen LMDB-vertailijan mukaan leksikografiseen järjestykseen, ne järjestetään järjestykseen vaaditulla tavalla. Peräkkäiset avaimet samalla punaisella etuliitteellä antaa meille niihin liittyvät arvot siinä järjestyksessä, jossa ne pitäisi näyttää käyttöliittymässä (oikealla), ilman mitään ylimääräistä jälkikäsittelyä.

Avainten ja arvojen sarjoittaminen

Maailmassa on keksitty monia menetelmiä objektien sarjoittamiseksi. Koska meillä ei ollut muuta vaatimusta kuin nopeus, valitsimme itsellemme nopeimman mahdollisen - C-kielen rakenteen instanssin varaaman muistin, joten hakemistoelementin avain voidaan mallintaa seuraavalla rakenteella. NodeKey.

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

Pelastaa NodeKey esineessä tarvittavassa varastossa MDB_val aseta dataosoitin rakenteen alun osoitteeseen ja laske niiden koko funktiolla sizeof.

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

Ensimmäisessä luvussa tietokannan valintakriteereistä mainitsin dynaamisten allokaatioiden minimoimisen CRUD-toimintojen sisällä tärkeänä valintatekijänä. Toimintokoodi serialize osoittaa, kuinka LMDB:n tapauksessa ne voidaan täysin välttää lisättäessä uusia tietueita tietokantaan. Palvelimelta saapuva tavutaulukko muunnetaan ensin pinorakenteiksi ja sitten ne tyhjennetään triviaalisti varastoon. Ottaen huomioon, että LMDB:n sisällä ei myöskään ole dynaamisia varauksia, voit saada iOS-standardien mukaan fantastisen tilanteen - käytä vain pinomuistia tietojen käsittelyyn koko polulla verkosta levylle!

Avainten tilaaminen binäärivertailijalla

Avainjärjestyksen suhde määritellään erikoisfunktiolla, jota kutsutaan vertailijaksi. Koska kone ei tiedä mitään niiden sisältämien tavujen semantiikasta, oletusvertailijalla ei ole muuta vaihtoehtoa kuin järjestää avaimet leksikografiseen järjestykseen turvautuen tavukohtaiseen vertailuun. Sen käyttäminen rakenteiden järjestämiseen on samanlaista kuin parranajo silppuavalla kirveellä. Yksinkertaisissa tapauksissa pidän tätä menetelmää kuitenkin hyväksyttävänä. Vaihtoehto on kuvattu alla, mutta tässä huomaan muutaman haravan, jotka ovat hajallaan tällä polulla.

Ensimmäinen asia, joka tulee muistaa, on primitiivisten tietotyyppien muistiesitys. Siten kaikissa Apple-laitteissa kokonaislukumuuttujat tallennetaan muodossa Pikku Endian. Tämä tarkoittaa, että vähiten merkitsevä tavu on vasemmalla, eikä kokonaislukuja voida lajitella tavu tavu vertailulla. Esimerkiksi, jos yrität tehdä tämän joukolla numeroita 0-511, saadaan seuraava tulos.

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

Tämän ongelman ratkaisemiseksi kokonaisluvut on tallennettava avaimeen tavutavuvertailijalle sopivassa muodossa. Perheen toiminnot auttavat sinua toteuttamaan tarvittavan muutoksen hton* (erityisesti htons esimerkin kaksitavuisille numeroille).

Ohjelmoinnin merkkijonojen esittämisen muoto on, kuten tiedätte, kokonaisuus historia. Jos merkkijonojen semantiikka sekä niiden esittämiseen muistissa käytetty koodaus viittaa siihen, että merkkiä kohti voi olla enemmän kuin yksi tavu, on parempi hylätä heti ajatus oletusvertailijan käytöstä.

Toinen asia, joka on pidettävä mielessä, on linjausperiaatteet rakennekentän kääntäjä. Niiden ansiosta kenttien väliin voidaan muodostaa muistiin roskaarvoisia tavuja, mikä tietysti katkaisee tavu-lajittelun. Roskien poistamiseksi sinun on joko ilmoitettava kentät tiukasti määritellyssä järjestyksessä pitäen tasaussäännöt mielessä tai käytettävä attribuuttia rakennemäärityksessä packed.

Avainten tilaaminen ulkoisella vertailulaitteella

Avainten vertailulogiikka voi olla liian monimutkainen binäärivertailijalle. Yksi monista syistä on teknisten alojen läsnäolo rakenteissa. Havainnollistan niiden esiintymistä meille jo tutun hakemistoelementin avaimen esimerkillä.

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

Yksinkertaisuudestaan ​​huolimatta se kuluttaa useimmissa tapauksissa liikaa muistia. Nimen puskuri vie 256 tavua, vaikka keskimäärin tiedostojen ja kansioiden nimet ylittävät harvoin 20-30 merkkiä.

Yksi tietueen koon optimoinnin vakiotekniikoista on "leimaa" se todelliseen kokoon. Sen ydin on, että kaikkien muuttuvamittaisten kenttien sisältö tallennetaan puskuriin rakenteen lopussa ja niiden pituudet erillisiin muuttujiin.​ Tämän lähestymistavan mukaan avain NodeKey muunnetaan seuraavasti.

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

Lisäksi sarjoitettaessa datan kokoa ei määritellä sizeof koko rakenne, ja kaikkien kenttien koko on kiinteä pituus plus puskurin tosiasiallisesti käytetyn osan koko.

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

Refaktoroinnin tuloksena saimme merkittäviä säästöjä avainten käytössä. Kuitenkin teknisen alan takia nameLength, oletusbinäärivertailija ei enää sovellu avainten vertailuun. Jos emme korvaa sitä omallamme, niin nimen pituus on korkeampi prioriteettitekijä lajittelussa kuin itse nimi.

LMDB mahdollistaa jokaisen tietokannan oman avainvertailutoiminnon. Tämä tehdään funktiolla mdb_set_compare tarkasti ennen avaamista. Ilmeisistä syistä sitä ei voi muuttaa koko tietokannan käyttöiän ajan. Vertailija vastaanottaa kaksi avainta binäärimuodossa syötteenä, ja ulostulossa se palauttaa vertailutuloksen: pienempi kuin (-1), suurempi kuin (1) tai yhtä suuri kuin (0). Pseudokoodi for NodeKey näyttää siltä.

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

Niin kauan kuin tietokannan kaikki avaimet ovat samaa tyyppiä, niiden tavuesitysten ehdoittaminen sovelluksen avainrakenteen tyyppiin on laillista. Tässä on yksi vivahde, mutta sitä käsitellään jäljempänä kohdassa "Lukutietueet".

Arvojen sarjoittaminen

LMDB toimii erittäin intensiivisesti tallennettujen tietueiden avainten kanssa. Niiden vertailu keskenään tapahtuu minkä tahansa sovelletun toiminnon puitteissa, ja koko ratkaisun suorituskyky riippuu vertailijan nopeudesta. Ihanteellisessa maailmassa oletusarvoisen binäärivertailijan pitäisi riittää avaimien vertailuun, mutta jos joutuisi käyttämään omaasi, avainten sarjoittaminen tulisi suorittaa siinä mahdollisimman nopeasti.

Tietokanta ei ole erityisen kiinnostunut tietueen arvoosasta (arvosta). Sen muuntaminen tavuesityksestä objektiksi tapahtuu vain silloin, kun sovelluskoodi jo vaatii sitä esimerkiksi näyttämään se näytöllä. Koska tätä tapahtuu suhteellisen harvoin, tämän toimenpiteen nopeusvaatimukset eivät ole niin kriittisiä, ja sen toteutuksessa voimme keskittyä paljon vapaammin mukavuuteen. Esimerkiksi vielä lataamattomien tiedostojen metatietojen sarjoittamiseksi käytämme NSKeyedArchiver.

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

Toisinaan suorituskyvyllä on kuitenkin merkitystä. Esimerkiksi kun tallennamme metainformaatiota käyttäjäpilven tiedostorakenteesta, käytämme samaa objektien muistivedosta. Tehtävän kohokohta luoda niistä sarjamuotoinen esitys on se, että hakemiston elementit mallinnetaan luokkahierarkialla.​

Sen toteuttamiseksi C-kielellä perillisten tietyt kentät sijoitetaan erillisiin rakenteisiin ja niiden yhteys peruskenttiin määritetään tyyppiliiton kentän kautta. Liiton todellinen sisältö määritellään teknisen attribuutin tyypin kautta.

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

Tietueiden lisääminen ja päivittäminen

Serialisoitu avain ja arvo voidaan lisätä kauppaan. Voit tehdä tämän käyttämällä toimintoa mdb_put.

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

Konfigurointivaiheessa tallennus voidaan sallia tai kieltää useiden tietueiden tallentaminen samalla avaimella.Jos avaimien kopiointi on kielletty, tietuetta lisättäessä voidaan määrittää, onko olemassa olevan tietueen päivittäminen sallittua vai ei. Jos rispaantuminen voi tapahtua vain koodin virheen seurauksena, voit suojautua siltä määrittämällä lipun NOOVERWRITE.

Kirjoitusten lukeminen

Käytä toimintoa lukeaksesi tietueita LMDB:ssä mdb_get. Jos avain-arvo-paria edustavat aiemmin poistetut rakenteet, tämä menettely näyttää tältä.

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

Esitetty luettelo osoittaa, kuinka serialisointi rakennevedoksen avulla antaa sinun päästä eroon dynaamisista varauksista ei vain kirjoitettaessa, vaan myös dataa luettaessa. Toiminnasta johdettu mdb_get osoitin katsoo tarkalleen virtuaalimuistin osoitetta, johon tietokanta tallentaa kohteen tavuesityksen. Itse asiassa saamme eräänlaisen ORM:n, joka tarjoaa erittäin suuren tiedonlukunopeuden lähes ilmaiseksi. Lähestymistavan kaikesta kauneudesta huolimatta on tarpeen muistaa useita siihen liittyviä ominaisuuksia.

1. Vain luku -tapahtumassa arvorakenteen osoitin pysyy taatusti voimassa vain tapahtuman sulkemiseen asti. Kuten aiemmin todettiin, B-puun sivut, joilla objekti sijaitsee, pysyvät kopiointi päälle -periaatteen ansiosta ennallaan niin kauan kuin niihin viitataan ainakin yhdessä tapahtumassa. Samanaikaisesti, kun viimeinen niihin liittyvä tapahtuma on valmis, sivuja voidaan käyttää uudelleen uusien tietojen saamiseksi. Jos on välttämätöntä, että objektit selviävät ne luoneesta tapahtumasta, ne on silti kopioitava.
2. Readwrite-tapahtumassa osoitin tuloksena olevaan arvorakenteeseen on voimassa vain ensimmäiseen muokkaustoimenpiteeseen (tietojen kirjoittamiseen tai poistamiseen) asti.
3. Vaikka rakenne NodeValue ei täysimittaisesti, vaan leikattu (katso alaosa ”Avainten tilaaminen ulkoisella vertailulaitteella”), voit käyttää sen kenttiä turvallisesti osoittimen kautta. Pääasia on, että sitä ei kannata jättää huomiotta!
4. Rakennetta ei saa missään tapauksessa muuttaa vastaanotetun osoittimen kautta. Kaikki muutokset tulee tehdä vain menetelmän kautta mdb_put. Vaikka kuinka kovaa haluat tehdä tämän, se ei kuitenkaan ole mahdollista, koska muistialue, jossa tämä rakenne sijaitsee, on kartoitettu vain luku -tilassa.
5. Yhdistä tiedosto prosessin osoiteavaruuteen esimerkiksi tallennustilan enimmäiskoon kasvattamiseksi toiminnon avulla mdb_env_set_map_size mitätöi täysin kaikki tapahtumat ja niihin liittyvät entiteetit yleensä ja osoittimet tiettyihin objekteihin erityisesti.

Lopuksi toinen ominaisuus on niin salakavala, että sen olemuksen paljastaminen ei mahdu vain toiseen kappaleeseen. B-puuta käsittelevässä luvussa annoin kaavion siitä, kuinka sen sivut on järjestetty muistissa. Tästä seuraa, että sarjoitettua dataa sisältävän puskurin alun osoite voi olla täysin mielivaltainen. Tästä johtuen osoitin niihin sai rakenteessa MDB_val ja pelkistettynä osoittimeksi rakenteeseen, se osoittautuu yleisessä tapauksessa kohdistamattomaksi. Samaan aikaan joidenkin sirujen arkkitehtuurit (iOS:n tapauksessa tämä on armv7) edellyttävät, että minkä tahansa datan osoite on konesanan koon tai toisin sanoen järjestelmän bittikoon monikerta ( armv7:lle se on 32 bittiä). Toisin sanoen operaatio, kuten *(int *foo)0x800002 niihin vastaa pakoa ja johtaa teloitukseen tuomiolla EXC_ARM_DA_ALIGN. On kaksi tapaa välttää tällainen surullinen kohtalo.

Ensimmäinen tiivistyy tietojen alustavaan kopioimiseen selvästi kohdistettuun rakenteeseen. Esimerkiksi mukautetussa vertailussa tämä näkyy seuraavasti.

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

Vaihtoehtoinen tapa on ilmoittaa kääntäjälle etukäteen, että avainarvorakenteita ei ehkä kohdisteta attribuuttien mukaan. aligned(1). ARM:lla voi olla sama vaikutus saavuttaa ja käyttämällä pakattu attribuuttia. Koska se auttaa myös optimoimaan rakenteen viemää tilaa, tämä menetelmä vaikuttaa minusta paremmalta, vaikka приводит tiedonsaantioperaatioiden kustannusten nousuun.

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

Aluekyselyt

Tietueryhmän iterointia varten LMDB tarjoaa kohdistimen abstraktion. Katsotaanpa kuinka työskennellä sen kanssa esimerkkinä taulukosta, jossa on meille jo tuttuja käyttäjäpilvimetatietoja.

Osana tiedostoluettelon näyttämistä hakemistossa on löydettävä kaikki avaimet, joihin sen alatason tiedostot ja kansiot liittyvät. Edellisissä alaosissa lajittelimme avaimet NodeKey siten, että ne järjestetään ensisijaisesti päähakemiston tunnuksen mukaan. Siten teknisesti kansion sisällön hakemisen tehtävänä on asettaa kohdistin tietyllä etuliitteellä varustetun näppäinryhmän ylärajalle ja sitten iteroida alarajalle.

Yläraja löytyy suoraan peräkkäisellä haulla. Tätä varten kohdistin sijoitetaan tietokannan koko avainluettelon alkuun ja sitä kasvatetaan edelleen, kunnes sen alle ilmestyy avain, jossa on päähakemiston tunniste. Tällä lähestymistavalla on 2 ilmeistä haittaa:

1. Lineaarinen haun monimutkaisuus, vaikka, kuten tiedetään, puissa yleensä ja erityisesti B-puussa se voidaan suorittaa logaritmisessa ajassa.
2. Turhaan kaikki etsittävää sivua edeltävät sivut nostetaan tiedostosta päämuistiin, mikä on erittäin kallista.

Onneksi LMDB API tarjoaa tehokkaan tavan sijoittaa kohdistin aluksi. Tätä varten sinun on luotava avain, jonka arvo on selvästi pienempi tai yhtä suuri kuin välin ylärajalla sijaitseva avain. Esimerkiksi yllä olevan kuvan luettelon suhteen voimme tehdä avaimen, jossa kenttä parentId on yhtä suuri kuin 2, ja kaikki loput on täytetty nolilla. Tällainen osittain täytetty avain syötetään toimintotuloon mdb_cursor_get osoittaa operaatiota 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);

Jos näppäinryhmän yläraja löytyy, toistetaan sitä, kunnes joko kohtaamme tai avain kohtaa toisen parentIdtai avaimet eivät lopu ollenkaan.

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

Hienoa on, että osana iteraatiota mdb_cursor_get-komennolla saamme paitsi avaimen myös arvon. Jos näytteenottoehtojen täyttämiseksi sinun on tarkistettava muun muassa kentät tietueen arvo-osasta, niin ne ovat melko käytettävissä ilman lisäeleitä.

4.3. Taulukoiden välisten suhteiden mallintaminen

Tähän mennessä olemme onnistuneet ottamaan huomioon kaikki yhden taulukon tietokannan suunnittelun ja työskentelyn näkökohdat. Voimme sanoa, että taulukko on joukko lajiteltuja tietueita, jotka koostuvat samantyyppisistä avain-arvo-pareista. Jos näytät avaimen suorakulmiona ja siihen liittyvän arvon suuntaissärmiönä, saat tietokannan visuaalisen kaavion.

----

Todellisessa elämässä on kuitenkin harvoin mahdollista tulla toimeen näin pienellä verenvuodatuksella. Usein tietokannassa vaaditaan ensinnäkin useita taulukoita ja toiseksi niissä on tehtävä valinnat järjestyksessä, joka poikkeaa ensisijaisesta avaimesta. Tämä viimeinen osa on omistettu niiden luomisen ja yhteenliittämisen kysymyksiin.

Indeksitaulukot

Pilvisovelluksessa on "Galleria"-osio. Se näyttää mediasisällön koko pilvestä päivämäärän mukaan lajiteltuna. Tällaisen valinnan toteuttamiseksi optimaalisesti sinun on luotava päätaulukon viereen toinen, jossa on uudentyyppiset avaimet. Ne sisältävät kentän, jossa on tiedoston luontipäivämäärä, joka toimii ensisijaisena lajitteluperusteena. Koska uudet avaimet viittaavat samoihin tietoihin kuin päätaulukon avaimet, niitä kutsutaan indeksiavaimiksi. Alla olevassa kuvassa ne on korostettu oranssilla.

Eri taulukoiden avainten erottamiseksi toisistaan ​​saman tietokannan sisällä, niihin kaikkiin lisättiin ylimääräinen tekninen kenttä tableId. Asettamalla siitä lajittelun korkeimman prioriteetin saavutamme avainten ryhmittelyn ensin taulukoiden mukaan ja taulukoiden sisällä - omien sääntöjemme mukaan.​

Indeksiavain viittaa samoihin tietoihin kuin ensisijainen avain. Tämän ominaisuuden yksinkertainen toteutus yhdistämällä siihen primaariavaimen arvoosan kopio ei ole optimaalinen useista näkökulmista:

1. Viedyn tilan suhteen metadata voi olla melko rikas.
2. Suorituskyvyn näkökulmasta, koska päivitettäessä solmun metatietoja, sinun on kirjoitettava ne uudelleen kahdella avaimella.
3. Koodituen näkökulmasta, jos unohdamme päivittää jonkin avaimen tiedot, saamme vaikeasti havaittavan virheen tietojen epäjohdonmukaisuudesta tallennustilassa.

Seuraavaksi pohditaan, kuinka nämä puutteet voidaan poistaa.

Taulukoiden välisten suhteiden järjestäminen

Malli soveltuu hyvin linkittämään indeksitaulukko päätaulukkoon "avain arvona". Kuten nimestä voi päätellä, indeksitietueen arvo-osa on kopio ensisijaisen avaimen arvosta. Tämä lähestymistapa eliminoi kaikki edellä mainitut haitat, jotka liittyvät ensisijaisen tietueen arvoosan kopion tallentamiseen. Ainoa hinta on, että saadaksesi arvon indeksiavaimella sinun on tehtävä kaksi kyselyä tietokantaan yhden sijaan. Kaavamaisesti tuloksena oleva tietokantaskeema näyttää tältä.

Toinen malli taulukoiden välisten suhteiden järjestämiseen on "redundantti avain". Sen ydin on lisätä avaimeen lisäattribuutteja, joita ei tarvita lajitteluun, vaan siihen liittyvän avaimen uudelleenluomiseen. Mail.ru Cloud -sovelluksessa on kuitenkin todellisia esimerkkejä sen käytöstä, jotta vältytään syvältä sukelluksesta tiettyjen iOS-kehysten kontekstissa annan kuvitteellisen, mutta selkeämmän esimerkin.​

Pilvimobiiliasiakkailla on sivu, joka näyttää kaikki tiedostot ja kansiot, jotka käyttäjä on jakanut muiden kanssa. Koska tällaisia ​​tiedostoja on suhteellisen vähän ja niihin liittyy paljon erityyppistä erityistietoa julkisuudesta (kenelle on myönnetty käyttöoikeus, millä oikeuksilla jne.), ei ole järkevää rasittaa tiedostojen arvoa. tallentaa sen kanssa päätaulukkoon. Jos kuitenkin haluat näyttää tällaisia ​​tiedostoja offline-tilassa, sinun on silti tallennettava ne jonnekin. Luonnollinen ratkaisu on luoda sille erillinen pöytä. Alla olevassa kaaviossa sen avaimen edessä on "P" ja paikkamerkki "propname" voidaan korvata tarkemmalla arvolla "public info".​

Kaikki ainutlaatuiset metatiedot, joiden tallennusta varten uusi taulukko luotiin, sijoitetaan tietueen arvo-osaan. Samaan aikaan et halua kopioida tietoja tiedostoista ja kansioista, jotka on jo tallennettu päätaulukkoon. Sen sijaan "P"-avaimeen lisätään redundantteja tietoja "solmutunnus"- ja "aikaleima"-kenttien muodossa. Niiden ansiosta voit rakentaa indeksiavaimen, josta saat ensisijaisen avaimen, josta lopulta saada solmun metatiedot.

Johtopäätös

Arvostamme LMDB:n toteutuksen tuloksia positiivisesti. Sen jälkeen hakemusten jäädytysten määrä väheni 30 %.

Tehdyn työn tulokset resonoivat iOS-tiimin ulkopuolella. Tällä hetkellä Android-sovelluksen yksi tärkeimmistä "Tiedostot"-osioista on myös siirtynyt käyttämään LMDB:tä, ja muut osat ovat tulossa. C-kieli, jossa avainarvovarasto on toteutettu, auttoi aluksi luomaan sovelluskehystä sen ympärille cross-platform C++:ssa. Koodigeneraattoria käytettiin yhdistämään tuloksena oleva C++-kirjasto saumattomasti Objective-C:n ja Kotlinin alustakoodiin Djinni Dropboxista, mutta se on täysin eri tarina.

Lähde: will.com