2019. aasta sügisel toimus Mail.ru Cloud iOS meeskonnas kauaoodatud sündmus. Rakenduse oleku püsiva salvestamise põhiandmebaas on muutunud mobiilimaailma jaoks väga eksootiliseks Välkmäluga kaardistatud andmebaas (LMDB). Lõike all pakume teile selle üksikasjalikku ülevaadet neljas osas. Kõigepealt räägime sellise mittetriviaalse ja raske valiku põhjustest. Seejärel käsitleme LMDB arhitektuuri keskmes olevaid kolme sammast: mälukaardiga failid, B+-puu, kopeerimine-kirjutamisel lähenemisviis tehingute ja mitmeversiooni rakendamiseks. Lõpetuseks magustoiduks – praktiline osa. Selles vaatleme, kuidas kujundada ja rakendada mitme tabeliga, sealhulgas indeksiga andmebaasi skeemi madala taseme võtmeväärtuse API peal.

Sisu

1. Motivatsioon rakendamiseks
2. LMDB positsioneerimine
3. LMDB kolm sammast
   3.1. Vaal nr 1. Mäluga kaardistatud failid
   3.2. Vaal nr 2. B+-puu
   3.3. Vaal nr 3. Kopeerimine-kirjutamine
4. Andmeskeemi kujundamine võtmeväärtuse API peal
   4.1. Põhilised abstraktsioonid
   4.2. Tabeli modelleerimine
   4.3. Seoste modelleerimine tabelite vahel

1. Motivatsioon rakendamiseks

Ühel aastal 2015 võtsime vaevaks mõõta, kui sageli meie rakenduse liides viibib. Tegime seda põhjusega. Sagedamini oleme saanud kaebusi, et mõnikord lakkab rakendus kasutaja toimingutele reageerimast: nuppe ei saa vajutada, nimekirjad ei keri jne. Mõõtmiste mehaanika kohta rääkis AvitoTechis, seega annan siin ainult numbrite järjekorra.

Mõõtmistulemused kujunesid meie jaoks külmaks dušiks. Selgus, et külmumistest tingitud probleeme on palju rohkem kui ükski teine. Kui enne selle fakti mõistmist oli peamine tehniline kvaliteedinäitaja krahhivaba, siis pärast keskendumist nihkunud külmutatult.

Olles ehitanud külmutusega armatuurlaud ja pärast kulutamist kvantitatiivne и kvaliteet nende põhjuste analüüsimisel selgus peamine vaenlane - rakenduse põhilõimes teostatud raske äriloogika. Loomulik reaktsioon sellele häbusele oli põletav soov see töövoogudesse suruda. Selle probleemi süstemaatiliseks lahendamiseks kasutasime kergetel näitlejatel põhinevat mitme keermega arhitektuuri. Pühendasin selle iOS-i maailma jaoks kohandamiseks kaks niiti kollektiivses Twitteris ja artikkel Habré kohta. Käesoleva narratiivi osana tahan rõhutada neid otsuse aspekte, mis mõjutasid andmebaasi valikut.​

Süsteemi organiseerimise näitlejamudel eeldab, et mitme lõimega ühendamisest saab selle teine ​​olemus. Selles olevatele mudelobjektidele meeldib ületada oja piire. Ja nad ei tee seda mitte mõnikord ja siin ja seal, vaid peaaegu pidevalt ja igal pool

Andmebaas on esitatud diagrammi üks nurgakivikomponente. Selle põhiülesanne on makromustri rakendamine Jagatud andmebaas. Kui ettevõtlusmaailmas kasutatakse seda andmete sünkroonimise korraldamiseks teenuste vahel, siis actor arhitektuuri puhul - lõimedevahelised andmed. Seega vajasime andmebaasi, mis ei tekitaks sellega mitme lõimega keskkonnas töötades minimaalseid raskusi. Eelkõige tähendab see, et sealt saadud objektid peavad olema vähemalt niidikindlad ja ideaalis täiesti mittemuutuvad. Nagu teate, saab viimast kasutada üheaegselt mitmest niidist ilma lukustamist kasutamata, millel on jõudlusele kasulik mõju.

Teine oluline tegur, mis andmebaasi valikut mõjutas, oli meie pilve API. See oli inspireeritud giti poolt kasutusele võetud sünkroonimismeetodist. Nagu tema, sihisime ka meie võrguühenduseta esimene API, mis tundub pilveklientide jaoks enam kui sobiv. Eeldati, et nad pumpavad pilve kogu oleku välja ainult üks kord ja seejärel toimub sünkroonimine enamikul juhtudel muudatuste käivitamise kaudu. Paraku on see võimalus alles teoreetilises tsoonis ja kliendid pole praktikas plaastritega töötamist õppinud. Sellel on mitmeid objektiivseid põhjuseid, mille sissejuhatusega mitte viivitama jätame sulgude taha. Nüüd pakuvad palju rohkem huvi õppetunni õpetlikud järeldused selle kohta, mis juhtub siis, kui API ütleb "A" ja selle tarbija ei ütle "B".

Seega, kui kujutate ette giti, mis tõmbab tõmbekäsu täitmisel kohaliku hetktõmmise paikade rakendamise asemel selle täisolekut serveri täisolekuga, siis on teil üsna täpne ettekujutus sellest, kuidas sünkroonimine pilves toimub. kliendid. Lihtne on arvata, et selle rakendamiseks peate eraldama mällu kaks DOM-puud koos metateabega kõigi serveri- ja kohalike failide kohta. Selgub, et kui kasutaja salvestab pilve 500 tuhat faili, siis selle sünkroonimiseks on vaja uuesti luua ja hävitada kaks 1 miljoni sõlmega puud. Kuid iga sõlm on agregaat, mis sisaldab alamobjektide graafikut. Selles valguses olid profileerimise tulemused oodatud. Selgus, et isegi ilma liitmisalgoritmi arvesse võtmata maksab juba tohutu hulga väikeste objektide loomise ja hilisema hävitamise protseduur päris senti. Olukorda raskendab asjaolu, et põhiline sünkroonimisoperatsioon sisaldub suures hulgas kasutaja skriptidest. Selle tulemusena fikseerime teise olulise kriteeriumi andmebaasi valimisel - võime teostada CRUD toiminguid ilma objektide dünaamilise jaotamiseta.

Muud nõuded on traditsioonilisemad ja nende loetelu on järgmine.

1. Keerme ohutus.
2. Multitöötlus. Selle põhjuseks on soov kasutada sama andmebaasi eksemplari oleku sünkroonimiseks mitte ainult lõimede vahel, vaid ka põhirakenduse ja iOS-i laienduste vahel.
3. Võimalus esitada salvestatud üksusi muutumatute objektidena
4. CRUD-operatsioonides dünaamilisi jaotamist pole.
5. Põhiomaduste tehingutugi ACID: aatomilisus, konsistents, isolatsioon ja töökindlus.
6. Kiirus kõige populaarsematel juhtudel.

Selle nõuete kogumiga oli ja jääb SQLite heaks valikuks. Alternatiivide uurimise raames sattusin aga ühe raamatuni "LevelDB-ga alustamine". Tema eestvedamisel pandi kirja etalon, milles võrreldi töö kiirust erinevate andmebaasidega päris pilvestsenaariumites. Tulemus ületas meie kõige metsikumad ootused. Kõige populaarsematel juhtudel - kursori saamine kõigi failide sorteeritud loendile ja antud kataloogi kõigi failide sorteeritud loendile - osutus LMDB 10 korda kiiremaks kui SQLite. Valik sai ilmseks.

2. LMDB positsioneerimine

LMDB on väga väike raamatukogu (ainult 10 XNUMX rida), mis rakendab andmebaaside madalaimat põhikihti – salvestusruumi.

Ülaltoodud diagramm näitab, et LMDB võrdlemine SQLite'iga, mis rakendab ka kõrgemaid tasemeid, ei ole üldiselt õigem kui SQLite'i põhiandmetega. Ausam oleks nimetada samu salvestusmootoreid võrdseteks konkurentideks – BerkeleyDB, LevelDB, Sophia, RocksDB jne. On isegi arendusi, kus LMDB toimib SQLite’i salvestusmootori komponendina. Esimene selline eksperiment oli 2012. aastal kulutatud LMDB poolt Howard Chu. Järeldused osutus nii intrigeerivaks, et tema initsiatiiv võtsid OSS-i entusiastid üles ja leidis oma jätku inimeses LumoSQL. Jaanuaris 2020 oli selle projekti autor Den Shearer esitati see LinuxConfAus.

LMDB-d kasutatakse peamiselt rakenduste andmebaaside mootorina. Raamatukogu võlgneb oma välimuse arendajatele OpenLDAP, kes ei olnud BerkeleyDB-ga oma projekti alusena väga rahul. Alustades tagasihoidlikust raamatukogust btree, suutis Howard Chu luua meie aja ühe populaarseima alternatiivi. Ta pühendas oma väga laheda reportaaži sellele loole, aga ka LMDB sisemisele struktuurile. "Välkmäluga kaardistatud andmebaas". Hea näide laohoone vallutamisest jagas Leonid Jurjev (aka yleo) Positive Technologiesilt oma Highload 2015. aasta aruandes "LMDB mootor on eriline meister". Selles räägib ta LMDB-st sarnase ReOpenLDAP-i juurutamise ülesande kontekstis ning LevelDB on juba saanud võrdleva kriitika osaliseks. Rakendamise tulemusena oli Positive Technologiesil isegi aktiivselt arenev kahvel MDBX väga maitsvate funktsioonide, optimeerimiste ja veaparandused.

LMDB-d kasutatakse sageli sellisena, nagu see on. Näiteks Mozilla Firefox brauser valinud seda paljude vajaduste jaoks ja alates versioonist 9 Xcode'ist eelistatud selle SQLite indeksite salvestamiseks.

Mootor on oma jälje teinud ka mobiiliarenduse maailmas. Võib esineda kasutamise jälgi leidma iOS-i kliendis Telegrami jaoks. LinkedIn läks veelgi kaugemale ja valis oma koduse andmete vahemälu raamistiku Rocket Data vaikesalvestuseks LMDB, mille kohta rääkis oma artiklis 2016. aastal.

LMDB võitleb edukalt koha eest päikese käes nišis, mille BerkeleyDB jättis pärast Oracle'i kontrolli alla sattumist. Raamatukogu on armastatud oma kiiruse ja töökindluse pärast, isegi võrreldes eakaaslastega. Nagu teate, tasuta lõunaid pole olemas ja tahaksin rõhutada kompromissi, millega peate silmitsi seisma, kui valite LMDB ja SQLite'i vahel. Ülaltoodud diagramm näitab selgelt, kuidas kiirust suurendatakse. Esiteks ei maksa me kettamälu peal täiendavate abstraktsioonikihtide eest. On selge, et hea arhitektuur ei saa ikkagi ilma nendeta hakkama ja need ilmuvad paratamatult rakenduse koodi, kuid need on palju peenemad. Need ei sisalda funktsioone, mida konkreetne rakendus ei nõua, näiteks SQL-keeles päringute tugi. Teiseks on võimalik optimaalselt rakendada rakenduste toimingute kaardistamist kettamälu päringutele. Kui SQLite minu töös põhineb keskmise rakenduse keskmistel statistilistel vajadustel, siis olete rakenduste arendajana hästi kursis peamiste töökoormuse stsenaariumidega. Tootlikuma lahenduse eest peate maksma kõrgendatud hinnasilti nii esialgse lahenduse väljatöötamise kui ka selle hilisema toe eest.

3. LMDB kolm sammast

Olles vaadanud LMDB-d linnulennult, oli aeg süveneda. Järgmised kolm osa on pühendatud peamiste tugisammaste analüüsile, millel salvestusarhitektuur toetub:

1. Mäluga kaardistatud failid kui mehhanism kettaga töötamiseks ja sisemiste andmestruktuuride sünkroonimiseks.
2. B+-puu kui salvestatud andmete struktuuri korraldus.
3. Kopeerimine kirjutamisel kui lähenemisviis ACID-tehingu omaduste ja mitmeversiooni pakkumiseks.

3.1. Vaal nr 1. Mäluga kaardistatud failid

Mäluga kaardistatud failid on nii oluline arhitektuuriline element, et need ilmuvad isegi hoidla nimes. Vahemällu salvestamise ja salvestatud teabele juurdepääsu sünkroonimise probleemid on täielikult jäetud operatsioonisüsteemile. LMDB ei sisalda enda sees vahemälu. See on autori teadlik otsus, kuna andmete otse kaardistatud failidest lugemine võimaldab mootori rakendamisel palju nurki kärpida. Allpool on mõnede neist kaugeltki täielik loetelu.

1. Salves olevate andmete järjepidevuse säilitamine mitme protsessi käigus töötamisel muutub operatsioonisüsteemi kohustuseks. Järgmises jaotises käsitletakse seda mehaanikat üksikasjalikult ja piltidega.
2. Vahemälu puudumine välistab LMDB dünaamiliste jaotustega seotud üldkuludest täielikult. Andmete lugemine tähendab praktikas kursori seadmist õigele aadressile virtuaalmälus ja ei midagi enamat. See kõlab nagu ulme, kuid salvestusallika lähtekoodis on kõik calloc-i kõned koondunud salvestuse konfiguratsioonifunktsiooni.
3. Vahemälu puudumine tähendab ka nende juurdepääsu sünkroonimisega seotud lukkude puudumist. Lugejad, keda võib korraga olla suvaliselt palju lugejaid, ei kohta oma teel andmeteni ühtki muteksit. Tänu sellele on lugemiskiirusel CPU-de arvu põhjal ideaalne lineaarne mastaapsus. LMDB-s sünkroonitakse ainult muutmistoimingud. Korraga saab olla ainult üks kirjanik.
4. Minimaalne vahemällu salvestamise ja sünkroonimise loogika välistab mitme lõimega keskkonnas töötamisega seotud äärmiselt keerulised vead. Usenix OSDI 2014 konverentsil toimus kaks huvitavat andmebaasiuuringut: "Kõik failisüsteemid ei ole võrdsed: krahhiga järjekindlate rakenduste loomise keerukus" и "Andmebaaside piinamine lõbu ja kasumi nimel". Nendest saate koguda teavet nii LMDB enneolematu töökindluse kui ka ACID-i tehinguomaduste peaaegu veatu rakendamise kohta, mis on parem kui SQLite.
5. LMDB minimalism võimaldab selle koodi masinesitusel täielikult paikneda protsessori L1 vahemälus koos sellest tulenevate kiirusomadustega.

Kahjuks pole iOS-is mälukaardistatud failidega kõik nii pilvitu, kui me tahaksime. Nendega seotud puudustest teadlikumaks rääkimiseks on vaja meeles pidada selle mehhanismi operatsioonisüsteemides rakendamise üldpõhimõtteid.

Üldteave mäluga kaardistatud failide kohta

Iga töötava rakendusega seostab operatsioonisüsteem olemi, mida nimetatakse protsessiks. Igale protsessile eraldatakse külgnev aadresside vahemik, kuhu see paigutab kõik, mida ta tööks vajab. Madalaimatel aadressidel on jaotised koodi ja kõvakodeeritud andmete ja ressurssidega. Järgmiseks tuleb kasvav dünaamilise aadressiruumi plokk, mis on meile hästi tuntud hunniku nime all. See sisaldab programmi töö ajal ilmuvate üksuste aadresse. Ülaosas on rakenduste virna kasutatav mäluala. See kas kasvab või tõmbub kokku; teisisõnu on selle suurusel ka dünaamiline iseloom. Selleks, et virn ja hunnik ei suruks ja segaksid üksteist, asuvad need aadressiruumi erinevates otstes. Kahe dünaamilise sektsiooni vahel on auk üleval ja all. Operatsioonisüsteem kasutab selles keskmises jaotises olevaid aadresse, et seostada protsessiga mitmesuguseid üksusi. Eelkõige võib see kettal oleva failiga siduda kindla pideva aadresside komplekti. Sellist faili nimetatakse mälukaardiks.​

Protsessile eraldatud aadressiruum on tohutu. Teoreetiliselt piirab aadresside arvu ainult kursori suurus, mille määrab süsteemi bitimaht. Kui füüsiline mälu kaardistataks sellega üks-ühele, siis ahmiks juba esimene protsess kogu RAM-i ja mingist multitegumtööst poleks juttugi.

​Oma kogemuse põhjal teame aga, et kaasaegsed operatsioonisüsteemid suudavad üheaegselt täita nii palju protsesse, kui soovitakse. See on võimalik tänu sellele, et nad eraldavad palju mälu ainult paberil olevatele protsessidele, kuid tegelikkuses laadivad nad põhifüüsilisse mällu ainult selle osa, mis on siin ja praegu nõutud. Seetõttu nimetatakse protsessiga seotud mälu virtuaalseks.

Operatsioonisüsteem korraldab virtuaalse ja füüsilise mälu teatud suurusega lehtedeks. Niipea, kui teatud virtuaalmälu leht on nõutud, laadib operatsioonisüsteem selle füüsilisse mällu ja sobitab need spetsiaalses tabelis. Kui vabu pesasid pole, kopeeritakse üks varem laaditud lehtedest kettale ja selle asemele tuleb nõutav. Seda protseduuri, mille juurde peagi tagasi tuleme, nimetatakse vahetamiseks. Allolev joonis illustreerib kirjeldatud protsessi. Sellele laaditi leht A aadressiga 0 ja paigutati põhimälu lehele aadressiga 4. See asjaolu kajastus vastavustabelis lahtris number 0.​

Mällu kaardistatud failidega on lugu täpselt sama. Loogiliselt võttes asuvad nad väidetavalt pidevalt ja täielikult virtuaalses aadressiruumis. Füüsilisse mällu sisenevad nad aga lehekülgede kaupa ja ainult nõudmisel. Selliste lehtede muutmine sünkroonitakse kettal oleva failiga. Sel viisil saate teha faili sisend-/väljundi, töötades lihtsalt mälus baitidega – operatsioonisüsteemi tuum kannab kõik muudatused automaatselt üle lähtefaili.​
​
Allolev pilt näitab, kuidas LMDB sünkroonib oma olekut erinevate protsesside andmebaasiga töötamisel. Kaardistades erinevate protsesside virtuaalmälu samasse faili, kohustume operatsioonisüsteemi de facto transitiivselt sünkroonima oma aadressiruumide teatud plokke, kuhu LMDB välja näeb.​
​

Oluline nüanss on see, et LMDB muudab vaikimisi andmefaili kirjutamissüsteemi kutsumismehhanismi kaudu ja kuvab faili ennast kirjutuskaitstud režiimis. Sellel lähenemisviisil on kaks olulist tagajärge.

Esimene tagajärg on ühine kõikidele operatsioonisüsteemidele. Selle olemus on lisada kaitse andmebaasi tahtmatu kahjustamise eest vale koodiga. Nagu teate, pääsevad protsessi käivitatavad käsud andmetele vabalt juurde kõikjalt selle aadressiruumis. Samal ajal, nagu me just mäletasime, tähendab faili kuvamine lugemis-kirjutamisrežiimis seda, et iga käsk võib seda ka muuta. Kui ta teeb seda kogemata, proovides näiteks massiivi elementi tegelikult olematu indeksi juures üle kirjutada, võib ta kogemata muuta sellele aadressile vastendatud faili, mis viib andmebaasi rikkumiseni. Kui faili kuvatakse kirjutuskaitstud režiimis, viib katse vastavat aadressiruumi muuta programmi hädaolukorra lõpetamiseni signaaliga SIGSEGV, ja fail jääb puutumata.

Teine tagajärg on juba iOS-i spetsiifiline. Autor ega ka ükski teine ​​allikas seda otseselt ei maini, kuid ilma selleta ei sobiks LMDB sellel mobiilioperatsioonisüsteemil töötamiseks. Järgmine osa on pühendatud selle käsitlemisele.

Mäluga kaardistatud failide eripära iOS-is

2018. aasta WWDC-l oli suurepärane raport "iOS-i mälu sügav sukeldumine". See ütleb meile, et iOS-is on kõik füüsilises mälus asuvad lehed üks kolmest tüübist: määrdunud, tihendatud ja puhtad.

Puhas mälu on lehtede kogum, mida saab füüsilisest mälust valutult maha laadida. Nendes sisalduvaid andmeid saab vastavalt vajadusele algallikatest uuesti laadida. Sellesse kategooriasse kuuluvad kirjutuskaitstud mäluga kaardistatud failid. iOS ei karda failiga vastendatud lehti igal ajal mälust maha laadida, kuna need sünkroonitakse kindlasti kettal oleva failiga.
​
Kõik muudetud lehed satuvad määrdunud mällu, olenemata nende algsest asukohast. Eelkõige klassifitseeritakse sel viisil mäluga kaardistatud failid, mida on muudetud nendega seotud virtuaalmällu kirjutades. LMDB avamine lipuga MDB_WRITEMAP, saate pärast selles muudatuste tegemist seda isiklikult kontrollida.​

Niipea, kui rakendus hakkab liiga palju füüsilist mälu hõivama, surub iOS selle määrdunud lehtede tihendamisele. Määrdunud ja tihendatud lehtedega hõivatud kogumälu moodustab rakenduse nn mälumahu. Kui see jõuab teatud läviväärtuseni, tuleb OOM-i tapmissüsteemi deemon pärast protsessi ja lõpetab selle sunniviisiliselt. See on iOS-i eripära võrreldes lauaarvuti operatsioonisüsteemidega. Seevastu mälumahu vähendamist lehekülgede vahetamise teel füüsiliselt mälult kettale iOS-is ette nähtud ei ole.Põhjuseid võib vaid oletada. Võib-olla on lehtede intensiivse kettale ja tagasi teisaldamise protseduur mobiilseadmete jaoks liiga energiakulukas või iOS säästab SSD-draividel lahtrite ümberkirjutamise ressurssi või ei olnud disainerid rahul süsteemi üldise jõudlusega, kus kõik on pidevalt vahetatud. Olgu kuidas on, fakt jääb faktiks.

Hea uudis, mida juba varem mainiti, on see, et LMDB ei kasuta failide värskendamiseks vaikimisi mmap-mehhanismi. See tähendab, et iOS klassifitseerib kuvatavad andmed puhtaks mäluks ja need ei mõjuta mälumahtu. Saate seda kontrollida, kasutades Xcode'i tööriista nimega VM Tracker. Allolev ekraanipilt näitab pilverakenduse iOS-i virtuaalmälu olekut töötamise ajal. Alguses initsialiseeriti selles 2 LMDB eksemplari. Esimesel lubati oma faili kuvada 1GiB virtuaalmälus, teisel 512MiB. Hoolimata asjaolust, et mõlemad salvestusruumid hõivavad teatud hulga püsimälu, ei anna kumbki neist määrdunud suurust.

Ja nüüd on aeg halbade uudiste jaoks. Tänu vahetusmehhanismile 64-bitistes töölaua operatsioonisüsteemides võib iga protsess hõivata nii palju virtuaalset aadressiruumi, kui palju vaba kõvakettaruumi selle võimaliku vahetamise jaoks võimaldab. Vahetuse asendamine pakkimisega iOS-is vähendab radikaalselt teoreetilist maksimumi. Nüüd peavad kõik elusprotsessid mahtuma põhimällu (loe RAM) ja kõik, mis ei mahu, tuleb sundida lõpetama. See on öeldud nagu eespool mainitud aruanneja sisse ametlik dokumentatsioon. Selle tulemusena piirab iOS tõsiselt mmapi kaudu eraldamiseks saadaoleva mälu mahtu. Siin siin Saate vaadata selle süsteemikõne abil erinevatele seadmetele eraldatava mälumahu empiirilisi piire. Kõige moodsamatel nutitelefonimudelitel on iOS muutunud heldeks 2 gigabaidi võrra ja iPadi tippversioonidel - 4. Praktikas tuleb muidugi keskenduda kõige madalama toetatud seadmemudelitele, kus kõik on väga kurb. Veelgi hullem, vaadates rakenduse mälu olekut VM Trackeris, leiate, et LMDB pole kaugeltki ainus, mis nõuab mälukaardistatud mälu. Head tükid söövad ära süsteemijagajad, ressursifailid, pildiraamistikud ja muud väiksemad röövloomad.

Pilves tehtud katsete tulemuste põhjal jõudsime LMDB eraldatud mälu jaoks järgmistele kompromissväärtustele: 384 megabaiti 32-bitiste seadmete jaoks ja 768 megabaiti 64-bitiste seadmete jaoks. Pärast selle mahu ammendumist hakkavad kõik muutmistoimingud koodiga lõppema MDB_MAP_FULL. Me täheldame selliseid vigu oma jälgimisel, kuid need on piisavalt väikesed, et praeguses etapis võib neid tähelepanuta jätta.

Salvestusruumi liigse mälutarbimise mitteilmne põhjus võivad olla pikaajalised tehingud. Et mõista, kuidas need kaks nähtust on omavahel seotud, aitab meil kaaluda LMDB ülejäänud kahte sammast.

3.2. Vaal nr 2. B+-puu

Võtmeväärtuste salvestusruumi peal olevate tabelite emuleerimiseks peavad selle API-s olema järgmised toimingud.

1. Uue elemendi sisestamine.
2. Otsige elementi antud võtmega.
3. Elemendi eemaldamine.
4. Korrake klahvide intervalle nende sortimise järjekorras.

Lihtsaim andmestruktuur, millega saab hõlpsasti rakendada kõiki nelja toimingut, on binaarne otsingupuu. Iga selle sõlm esindab võtit, mis jagab kogu alamvõtmete alamhulga kaheks alampuuks. Vasakpoolne sisaldab neid, mis on vanemast väiksemad, ja parempoolsed need, mis on suuremad. Tellitud võtmete komplekti saab ühe klassikalise puu läbimise kaudu

Binaarsetel puudel on kaks põhilist viga, mis takistavad nende tõhusust kettapõhise andmestruktuurina. Esiteks on nende tasakaalu aste ettearvamatu. On märkimisväärne oht saada puid, mille erinevate okste kõrgused võivad oluliselt erineda, mis halvendab oluliselt otsingu algoritmilist keerukust võrreldes eeldatuga. Teiseks, ristsidemete rohkus sõlmede vahel jätab binaarpuud ilma lokaalsusest mälus.Lähedased sõlmed (nendevaheliste ühenduste poolest) võivad paikneda virtuaalmälus täiesti erinevatel lehtedel. Selle tulemusena võib isegi mitme puu naabersõlme läbimine nõuda võrreldava arvu lehtede külastamist. See on probleem isegi siis, kui räägime binaarpuude kui mälusisese andmestruktuuri efektiivsusest, kuna protsessori vahemälus lehtede pidev pöörlemine pole just odav nauding. Kui tegemist on sõlmedega seotud lehtede sagedase hankimisega kettalt, muutub olukord täielikult kahetsusväärne.

B-puud, mis on kahendpuude evolutsioon, lahendavad eelmises lõigus tuvastatud probleemid. Esiteks tasakaalustavad nad ise. Teiseks jagab iga nende sõlm alamvõtmete komplekti mitte 2-ks, vaid M järjestatud alamhulgaks ja arv M võib olla üsna suur, suurusjärgus mitusada või isegi tuhat.

Seeläbi:

1. Iga sõlm sisaldab suurel hulgal juba tellitud võtmeid ja puud on väga lühikesed.
2. Puu omandab mälus lokaalsuse omaduse, kuna väärtuselt lähedased võtmed asuvad loomulikult üksteise kõrval samadel või naabersõlmedel.
3. Transiidisõlmede arv puu alla laskumisel otsinguoperatsiooni ajal väheneb.
4. Vahepäringute ajal loetavate sihtsõlmede arv väheneb, kuna igaüks neist sisaldab juba suurt hulka järjestatud võtmeid.

LMDB kasutab andmete salvestamiseks B-puu variatsiooni, mida nimetatakse B+ puuks. Ülaltoodud diagramm näitab kolme tüüpi sõlme, mis selles on:

1. Ülaosas on juur. See ei realiseeri midagi enamat kui laos oleva andmebaasi kontseptsioon. Ühes LMDB eksemplaris saate luua mitu andmebaasi, mis jagavad kaardistatud virtuaalset aadressiruumi. Igaüks neist saab alguse oma juurtest.
2. Madalaimal tasemel on lehed. Need ja ainult need sisaldavad andmebaasi salvestatud võtme-väärtuste paare. Muide, see on B+-puude eripära. Kui tavaline B-puu salvestab väärtusosad kõikide tasemete sõlmedesse, siis B+ variatsioon on ainult kõige madalamal. Olles selle fakti fikseerinud, nimetame LMDB-s kasutatavat puu alamtüüpi lihtsalt B-puuks.
3. Juure ja lehtede vahel on 0 või enam tehnilist taset koos navigatsiooni (haru) sõlmedega. Nende ülesanne on sorteeritud võtmete komplekt lehtede vahel jagada.

Füüsiliselt on sõlmed etteantud pikkusega mäluplokid. Nende suurus on mitmekordne operatsioonisüsteemi mälulehtede suurusest, mida me eespool käsitlesime. Sõlme struktuur on näidatud allpool. Päis sisaldab metateavet, millest kõige ilmsem on näiteks kontrollsumma. Järgmisena tuleb teave nihkete kohta, milles asuvad andmetega lahtrid. Andmed võivad olla kas võtmed, kui räägime navigeerimissõlmedest, või lehtede puhul terved võtme-väärtuste paarid.​ Lehekülgede struktuuri kohta saate täpsemalt lugeda tööst "Kõrge jõudlusega võtmeväärtusega kaupluste hindamine".

Olles käsitlenud lehe sõlmede sisemist sisu, esitame LMDB B-puud edaspidi lihtsustatud kujul järgmisel kujul.

Sõlmedega lehed asuvad kettal järjestikku. Kõrgema numbriga leheküljed asuvad faili lõpus. Nn metaleht sisaldab infot nihkete kohta, mille järgi on võimalik leida kõikide puude juured. Faili avamisel skannib LMDB faili lehekülgede kaupa otsast alguseni, otsides õiget metalehte ja selle kaudu otsides üles olemasolevad andmebaasid.​

Nüüd, omades ettekujutust andmekorralduse loogilisest ja füüsilisest struktuurist, saame liikuda edasi LMDB kolmanda samba juurde. Just tema abiga toimuvad kõik salvestusmuudatused tehinguliselt ja üksteisest eraldatult, andes andmebaasile tervikuna multiversiooni omaduse.

3.3. Vaal nr 3. Kopeerimine-kirjutamine

Mõned B-puu toimingud hõlmavad selle sõlmedes muudatuste tegemist. Üks näide on uue võtme lisamine sõlmele, mis on juba saavutanud oma maksimaalse mahu. Sel juhul on vaja esiteks sõlm kaheks jagada ja teiseks lisada link uue lootustandva alamsõlme juurde selle vanemas. See protseduur on potentsiaalselt väga ohtlik. Kui mingil põhjusel (avarii, elektrikatkestus vms) toimub ainult osa seeria muudatustest, jääb puu ebajärjekindlasse olekusse.

Üks traditsiooniline lahendus andmebaasi tõrketaluvaks muutmiseks on lisada B-puu kõrvale täiendav kettal olev andmestruktuur – tehingulogi, mida tuntakse ka ettekirjutamise logina (WAL). See on fail, mille lõppu kirjutatakse rangelt enne B-puu enda muutmist kavandatud toiming. Seega, kui enesediagnostika käigus tuvastatakse andmete riknemine, uurib andmebaas end korda seadmiseks logi.

LMDB on valinud oma tõrketaluvuse mehhanismiks teistsuguse meetodi, mida nimetatakse kopeerimiseks kirjutamisel. Selle olemus seisneb selles, et olemasoleva lehe andmete värskendamise asemel kopeerib see esmalt need täielikult ja teeb koopias kõik muudatused.​

Järgmiseks, et uuendatud andmed oleksid kättesaadavad, on vaja muuta linki sõlmele, mis on muutunud selle vanemsõlmes aktuaalseks. Kuna see vajab ka selleks muutmist, siis kopeeritakse ka see eelnevalt. Protsess jätkub rekursiivselt kuni juureni. Viimane asi, mida muuta, on metalehe andmed.​​

Kui protsess värskendusprotseduuri ajal ootamatult jookseb kokku, siis uut metalehte ei looda või seda ei kirjutata täielikult kettale ja selle kontrollsumma on vale. Mõlemal juhul ei pääse uutele lehtedele ligi, kuid see ei mõjuta vanu lehti. See välistab vajaduse LMDB-l andmete järjepidevuse säilitamiseks logi ette kirjutada. De facto võtab ülalkirjeldatud andmesalvestuse struktuur kettal samaaegselt oma funktsiooni. Selgesõnalise tehingulogi puudumine on üks LMDB omadusi, mis tagab suure andmelugemiskiiruse

Saadud kujundus, mida nimetatakse ainult lisamiseks mõeldud B-puuks, pakub loomulikult tehingute isoleerimist ja mitme versiooni koostamist. LMDB-s on iga avatud tehing seotud parajasti asjakohase puujuurega. Kuni tehingu lõpuleviimiseni sellega seotud puu lehti ei muudeta ega kasutata uuesti andmete uute versioonide jaoks. Seega saate töötada nii kaua kui soovite täpselt nende andmetega, mis sel ajal olid olulised. tehing avati, isegi kui salvestusruumi aktiivne värskendamine praegu jätkub. See on multiversiooni olemus, mis muudab LMDB ideaalseks andmeallikaks meie armastatule UICollectionView. Pärast tehingu avamist pole enam vaja rakenduse mälumahtu suurendada, pumbates kiirustades jooksvaid andmeid mõnda mälusisesesse struktuuri, kartes, et ei jää midagi. See funktsioon eristab LMDB-d samast SQLite'ist, mis ei saa kiidelda sellise täieliku isolatsiooniga. Kui viimases on avatud kaks tehingut ja ühes neist teatud kirje kustutatud, ei ole enam võimalik teisest allesjäänud kirjest sama kirjet hankida.

Mündi tagumine külg on potentsiaalselt oluliselt suurem virtuaalmälu tarbimine. Slaid näitab, milline näeb välja andmebaasi struktuur, kui seda muudetakse samaaegselt kolme avatud lugemistehinguga, vaadates andmebaasi erinevaid versioone. Kuna LMDB ei saa praeguste tehingutega seotud juurtest kättesaadavaid sõlmi uuesti kasutada, ei jää poel muud üle, kui eraldada mällu veel neljas juur ning selle alla veel kord kloonida muudetud lehed.​

Siin oleks kasulik meenutada mälukaardistatud failide jaotist. Tundub, et virtuaalmälu täiendav tarbimine ei tohiks meid eriti muretseda, kuna see ei aita kaasa rakenduse mälujäljele. Kuid samal ajal märgiti, et iOS on selle eraldamisel väga ihne ja me ei saa, nagu serveris või töölaual, pakkuda 1 terabaidist LMDB piirkonda ja sellele funktsioonile üldse mitte mõelda. Võimalusel tuleks püüda tehingute eluiga võimalikult lühikeseks muuta.

4. Andmeskeemi kujundamine võtmeväärtuse API peal

Alustame oma API analüüsi, vaadates LMDB pakutavaid põhilisi abstraktsioone: keskkond ja andmebaasid, võtmed ja väärtused, tehingud ja kursorid.

Märkus koodiloendite kohta

Kõik avaliku LMDB API funktsioonid tagastavad oma töö tulemuse veakoodina, kuid kõigis järgnevates loendites jäetakse selle kontrollimine lühiduse huvides ära. Praktikas kasutasime hoidlaga suhtlemiseks isegi enda oma kahvel C++ ümbrised lmdbxx, milles vead realiseeritakse C++ eranditena.

Kiireima viisina LMDB ühendamiseks iOS-i või macOS-i projektiga soovitan oma CocoaPodi POSLMDB.

4.1. Põhilised abstraktsioonid

Keskkond

Struktuur MDB_env on LMDB sisemise oleku hoidla. Eesliitega funktsioonide perekond mdb_env võimaldab konfigureerida mõningaid selle omadusi. Kõige lihtsamal juhul näeb mootori lähtestamine välja selline.

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

Mail.ru pilverakenduses muutsime ainult kahe parameetri vaikeväärtusi.

Esimene on virtuaalse aadressiruumi suurus, millega salvestusfail on vastendatud. Kahjuks võib konkreetne väärtus isegi samas seadmes käitamise lõikes oluliselt erineda. Selle iOS-i funktsiooni arvessevõtmiseks valitakse maksimaalne salvestusmaht dünaamiliselt. Alates teatud väärtusest jagatakse see järjestikku pooleks kuni funktsioonini mdb_env_open ei tagasta tulemust, mis erineb ENOMEM. Teoreetiliselt on ka vastupidine viis - kõigepealt eraldage mootorile minimaalne mälu ja seejärel, kui vead saavad, MDB_MAP_FULL, suurendage seda. See on aga palju okkalisem. Põhjus on selles, et funktsiooni abil toimub mälu ümberjaotamise protseduur (remap). mdb_env_set_map_size tühistab kõik varem mootorist saadud olemid (kursorid, tehingud, võtmed ja väärtused). Selle sündmuste pöörde koodis arvessevõtmine toob kaasa selle olulise komplikatsiooni. Kui aga virtuaalmälu on sinu jaoks väga oluline, siis võib see olla põhjus, miks kaugele ette läinud kahvlit lähemalt vaadata MDBX, kus väljakuulutatud funktsioonide hulgas on "andmebaasi suuruse automaatne kohandamine lennu ajal".

Teine parameeter, mille vaikeväärtus meile ei sobinud, reguleerib keerme ohutuse tagamise mehaanikat. Kahjuks on vähemalt iOS 10-l probleeme lõime kohaliku salvestusruumi toega. Sel põhjusel avatakse ülaltoodud näites hoidla lipuga MDB_NOTLS. Lisaks sellele oli see ka vajalik kahvel C++ ümbris lmdbxxselle atribuudiga muutujate välja lõikamiseks ja selles.

Andmebaasid

Andmebaas on eraldiseisev B-puu eksemplar, mida me eespool käsitlesime. Selle avamine toimub tehingu sees, mis võib alguses tunduda pisut kummaline.

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

Tõepoolest, LMDB-s olev tehing on salvestusüksus, mitte konkreetne andmebaasi üksus. See kontseptsioon võimaldab teha aatomioperatsioone erinevates andmebaasides asuvate üksustega. Teoreetiliselt avab see võimaluse modelleerida tabeleid erinevate andmebaaside kujul, kuid omal ajal läksin teist teed, mida kirjeldatakse üksikasjalikult allpool.

Võtmed ja väärtused

Struktuur MDB_val modelleerib nii võtme kui väärtuse mõistet. Hoidlal pole nende semantikast aimugi. Tema jaoks on midagi muud lihtsalt teatud suurusega baitide massiiv. Võtme maksimaalne suurus on 512 baiti.

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

Võrdleja abil sorteerib pood võtmed kasvavas järjekorras. Kui te seda enda omaga ei asenda, kasutatakse vaikimisi, mis sorteerib need bait-baidi haaval leksikograafilises järjekorras.​

Tehingud

Tehingu struktuuri kirjeldatakse üksikasjalikult artiklis eelmine peatükk, seega kordan siin lühidalt nende peamisi omadusi:

1. Toetab kõiki põhiomadusi ACID: aatomilisus, konsistents, isolatsioon ja töökindlus. Ma ei saa jätta märkimata, et MacOS-i ja iOS-i vastupidavuses on viga, mis parandati MDBX-is. Lisateavet saate nendest lugeda README.
2. Mitme lõimega töötlemise lähenemisviisi kirjeldab skeem "üks kirjutaja / mitu lugejat". Kirjutajad blokeerivad üksteist, kuid ei blokeeri lugejaid. Lugejad ei blokeeri kirjanikke ega üksteist.
3. Pesastatud tehingute tugi.
4. Multiversiooni tugi.

Multiversioon LMDB-s on nii hea, et tahan seda ka tegevuses demonstreerida. Allolevast koodist näete, et iga tehing töötab täpselt selle andmebaasi versiooniga, mis selle avamise ajal kehtis, olles täielikult isoleeritud kõigist järgnevatest muudatustest. Salvestusruumi lähtestamine ja sellele testkirje lisamine ei kujuta endast midagi huvitavat, seega jäävad need rituaalid spoileri alla.

Testi kirje lisamine

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

Soovitan proovida sama trikki SQLite'iga ja vaadata, mis juhtub.

Multiversioon toob iOS-i arendaja ellu väga toredaid eeliseid. Seda atribuuti kasutades saate hõlpsalt ja loomulikult kohandada ekraanivormide andmeallika värskenduskiirust, lähtudes kasutajakogemuse kaalutlustest. Võtame näiteks Mail.ru pilverakenduse funktsiooni, näiteks sisu automaatse laadimise süsteemi meediumigaleriist. Hea ühenduse korral on kliendil võimalik serverisse lisada mitu fotot sekundis. Kui värskendate pärast iga allalaadimist UICollectionView kui meediumisisu on kasutaja pilves, võite selle protsessi käigus unustada umbes 60 kaadrit sekundis ja sujuva kerimise. Et vältida sagedasi ekraanivärskendusi, peate kuidagi piirama andmete muutumise kiirust aluseks olevates andmetes UICollectionViewDataSource.

Kui andmebaas ei toeta multiversiooni ja võimaldab töötada ainult hetkeseisuga, siis tuleb andmetest ajastabiilse hetktõmmise loomiseks need kopeerida kas mõnda mälusiseste andmestruktuuri või ajutisse tabelisse. Ükskõik milline neist lähenemisviisidest on väga kallis. Mälusisese salvestuse puhul saame kulusid nii mällu, mis on põhjustatud konstrueeritud objektide salvestamisest, kui ka ajas, mis on seotud üleliigsete ORM-teisendustega. Mis puutub ajutisse lauda, ​​siis see on veelgi kallim rõõm, mis on mõttekas ainult mittetriviaalsetel juhtudel.

LMDB mitmeversiooniline lahendus lahendab stabiilse andmeallika säilitamise probleemi väga elegantsel viisil. Piisab vaid tehingu avamisest ja voila - kuni selle lõpule viimiseni on andmekogum garanteeritud. Selle värskenduskiiruse loogika on nüüd täielikult esitluskihi kätes, ilma märkimisväärsete ressurssideta.

Kursorid

Kursorid pakuvad mehhanismi võtme-väärtuste paaride korrapäraseks itereerimiseks B-puu läbimise kaudu. Ilma nendeta oleks võimatu tõhusalt modelleerida andmebaasis olevaid tabeleid, mille poole nüüd pöördume.

4.2. Tabeli modelleerimine

Võtmete järjestamise omadus võimaldab teil põhiabstraktsioonide peale luua kõrgetasemelise abstraktsiooni, näiteks tabeli. Vaatleme seda protsessi pilvekliendi põhitabeli näitel, mis salvestab vahemällu teavet kõigi kasutaja failide ja kaustade kohta.

Tabeliskeem

Üks levinumaid stsenaariume, mille jaoks tuleks kohandada kaustapuuga tabelistruktuuri, on kõigi antud kataloogis asuvate elementide valimine. Hea andmekorraldusmudel selliste tõhusate päringute jaoks on Adjacency nimekiri. Selle rakendamiseks võtmeväärtuste salvestusruumi peal on vaja failide ja kaustade võtmed sorteerida nii, et need rühmitataks nende kuuluvuse alusel ülemkataloogi. Lisaks on selleks, et kuvada kataloogi sisu Windowsi kasutajale tuttaval kujul (kõigepealt kaustad, seejärel failid, mõlemad järjestatud tähestikulises järjekorras), on vaja võtmesse lisada vastavad lisaväljad.

Alloleval pildil on näha, kuidas võtmete esitus baitimassiivi kujul võib vaadeldava ülesande põhjal välja näha. Algkataloogi identifikaatoriga baidid (punane), seejärel tüübiga (roheline) ja sabas koos nimega (sinine). Olles sorditud vaikimisi LMDB komparaatoriga leksikograafilises järjekorras, on need järjestatud nõutud viisil. Sama punase eesliitega võtmete järjestikune läbimine annab meile nendega seotud väärtused selles järjekorras, nagu need kasutajaliideses (paremal) kuvatakse, ilma täiendavat järeltöötlust nõudmata.

Võtmete ja väärtuste järjestamine

Maailmas on leiutatud palju meetodeid objektide serialiseerimiseks. Kuna meil polnud peale kiiruse muud nõuet, siis valisime enda jaoks kiireima võimaliku - C-keelestruktuuri eksemplari hõivatud mälumahu, seega saab kataloogielemendi võtit modelleerida järgmise struktuuriga. NodeKey.

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

Päästma NodeKey objektil vajalik laos MDB_val asetage andmekursor struktuuri alguse aadressile ja arvutage funktsiooniga nende suurus sizeof.

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

Esimeses andmebaasi valikukriteeriumide peatükis mainisin olulise valikutegurina dünaamiliste jaotuste minimeerimist CRUD-i operatsioonides. Funktsiooni kood serialize näitab, kuidas LMDB puhul saab neid uute kirjete andmebaasi lisamisel täielikult vältida. Serverist sissetulev baidimassiv teisendatakse esmalt virnastruktuurideks ja seejärel kantakse need triviaalselt salvestusruumi. Arvestades, et LMDB-s puuduvad ka dünaamilised jaotused, saate iOS-i standardite järgi fantastilise olukorra - kasutage andmetega töötamiseks ainult virnamälu kogu võrgust kettani ulatuval teel!

Võtmete tellimine binaarse komparaatoriga

Võtmejärjestuse seos määratakse spetsiaalse funktsiooniga, mida nimetatakse komparaatoriks. Kuna mootor ei tea neis sisalduvate baitide semantikast midagi, ei jää vaikimisi komparaatoril muud üle, kui korraldada võtmed leksikograafilises järjekorras, kasutades bait-baidi võrdlust. Selle kasutamine struktuuride korrastamiseks on sarnane hakkimiskirvega raseerimisele. Kuid lihtsatel juhtudel pean seda meetodit vastuvõetavaks. Alternatiivi kirjeldatakse allpool, kuid siin märgin paar reha, mis on sellel teel laiali.

Esimene asi, mida meeles pidada, on primitiivsete andmetüüpide mäluesitus. Seega salvestatakse kõigis Apple'i seadmetes täisarvulised muutujad vormingus Väike Endian. See tähendab, et kõige vähem oluline bait jääb vasakule ja täisarve ei ole võimalik bait-bait-võrdluse abil sortida. Näiteks kui proovite seda teha numbrite komplektiga vahemikus 0 kuni 511, saate järgmise tulemuse.

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

Selle probleemi lahendamiseks tuleb võtmesse salvestada täisarvud baitide-baitide komparaatori jaoks sobivas vormingus. Perekonna funktsioonid aitavad teil vajaliku ümberkujundamise läbi viia hton* (eriti htons näites toodud kahebaidiliste numbrite jaoks).

Stringide esitamise formaat programmeerimisel on, nagu teate, tervik lugu. Kui stringide semantika ja nende mälus esitamiseks kasutatav kodeering viitab sellele, et tähemärgi kohta võib olla rohkem kui üks bait, siis on parem vaikekomparaatori kasutamise ideest kohe loobuda.

Teine asi, mida meeles pidada, on joondamise põhimõtted struktuurivälja kompilaator. Nende tõttu saab väljade vahel mällu moodustada prügiväärtustega baite, mis loomulikult katkestab bait-bait-sortimise. Prügi kõrvaldamiseks peate kas deklareerima väljad rangelt määratletud järjekorras, pidades silmas joondusreegleid, või kasutama atribuuti struktuurideklaratsioonis packed.

Võtmete tellimine välise komparaatoriga

Võtmete võrdlemise loogika võib olla binaarse komparaatori jaoks liiga keeruline. Üks paljudest põhjustest on tehniliste valdkondade olemasolu struktuurides. Illustreerin nende esinemist meile juba tuttava kataloogielemendi võtme näitel.

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

Vaatamata oma lihtsusele kulutab see enamikul juhtudel liiga palju mälu. Nime puhver võtab enda alla 256 baiti, kuigi keskmiselt ületavad faili- ja kaustanimed harva 20–30 tähemärki.

Üks standardseid tehnikaid kirje suuruse optimeerimiseks on selle "kärpimine" tegelikule suurusele. Selle olemus seisneb selles, et kõigi muutuva pikkusega väljade sisu salvestatakse puhvrisse struktuuri lõpus ja nende pikkused eraldi muutujatesse.​ Selle lähenemisviisi kohaselt on võti NodeKey teisendatakse järgmiselt.

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

Lisaks ei määrata serialiseerimisel andmete suurust sizeof kogu struktuur ja kõigi väljade suurus on fikseeritud pikkusega pluss tegelikult kasutatud puhvri osa suurus.

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

Ümbertöötamise tulemusena saime võtmetega hõivatud ruumis oluliselt kokkuhoidu. Küll aga tehnikavaldkonnast tulenevalt nameLength, ei sobi vaikebinaarne komparaator enam võtmete võrdlemiseks. Kui me seda enda omaga ei asenda, on nime pikkus järjestamisel tähtsam tegur kui nimi ise.

LMDB võimaldab igal andmebaasil olla oma võtmete võrdlusfunktsioon. Seda tehakse funktsiooni abil mdb_set_compare rangelt enne avamist. Arusaadavatel põhjustel ei saa seda andmebaasi kogu kasutusaja jooksul muuta. Võrdleja saab sisendiks kaks binaarvormingus võtit ja väljundis tagastab võrdlustulemuse: väiksem kui (-1), suurem kui (1) või võrdne (0). Pseudokood jaoks NodeKey näeb välja selline.

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

Kuni kõik andmebaasi võtmed on sama tüüpi, on nende baitide esituse tingimusteta ülekandmine rakenduse võtmestruktuuri tüübile seaduslik. Siin on üks nüanss, kuid sellest tuleb juttu allpool alajaotises “Lugemiskirjed”.

Väärtuste järjestamine

LMDB töötab äärmiselt intensiivselt salvestatud kirjete võtmetega. Nende võrdlemine üksteisega toimub mis tahes rakendatud toimingu raames ja kogu lahenduse jõudlus sõltub komparaatori kiirusest. Ideaalses maailmas peaks võtmete võrdlemiseks piisama vaikimisi binaarsest komparaatorist, kuid kui pidite kasutama oma, siis peaks võtmete deserialiseerimise protseduur selles olema võimalikult kiire.

Kirje väärtusosa (väärtuse) andmebaasi eriti ei huvita. Selle teisendamine baitesitusest objektiks toimub ainult siis, kui rakenduse kood seda juba nõuab, näiteks selle kuvamiseks ekraanil. Kuna seda juhtub suhteliselt harva, ei ole selle protseduuri kiirusnõuded nii kriitilised ning selle rakendamisel saame palju vabamalt keskenduda mugavusele Näiteks veel alla laadimata failide metaandmete serialiseerimiseks kasutame NSKeyedArchiver.

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

Siiski on aegu, mil jõudlus on endiselt oluline. Näiteks kasutaja pilve failistruktuuri kohta metainfo salvestamisel kasutame sama objektide mälumälu. Nende serialiseeritud esituse loomise ülesande tipphetk on asjaolu, et kataloogi elemendid modelleeritakse klasside hierarhia abil.

Selle rakendamiseks C-keeles paigutatakse pärijate kindlad väljad eraldi struktuuridesse ning nende seos põhilisega täpsustatakse tüübiliidu välja kaudu. Liidu tegelik sisu täpsustatakse tehnilise atribuudi tüübi kaudu.

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

Kirjete lisamine ja uuendamine

Jadavõtit ja väärtust saab poodi lisada. Selleks kasutage funktsiooni mdb_put.

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

Seadistamise etapis saab salvestusele lubada või keelata mitme kirje salvestamise sama võtmega Kui võtmete dubleerimine on keelatud, siis kirje sisestamisel saab määrata, kas olemasoleva kirje uuendamine on lubatud või mitte. Kui narmendamine võib tekkida ainult koodi vea tõttu, saate end selle eest kaitsta lipu määramisega NOOVERWRITE.

Kirjete lugemine

LMDB-s kirjete lugemiseks kasutage funktsiooni mdb_get. Kui võtme-väärtuse paari esindavad varem kustutatud struktuurid, näeb see protseduur välja selline.

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

Esitatud loend näitab, kuidas serialiseerimine struktuuritõmmise kaudu võimaldab teil vabaneda dünaamilistest jaotustest mitte ainult kirjutamisel, vaid ka andmete lugemisel. Tuletatud funktsioonist mdb_get kursor vaatab täpselt virtuaalmälu aadressi, kuhu andmebaas salvestab objekti baidi esituse. Tegelikult saame omamoodi ORM-i, mis tagab väga suure andmelugemiskiiruse peaaegu tasuta. Hoolimata lähenemise kogu ilust on vaja meeles pidada mitmeid sellega seotud funktsioone.

1. Kirjutuskaitstud tehingu puhul jääb väärtusstruktuuri osuti kehtima vaid tehingu sulgemiseni. Nagu varem märgitud, jäävad B-puu lehed, millel objekt asub, tänu kopeerimise-kirjutamisel põhimõttele muutumatuks seni, kuni neile viitab vähemalt üks tehing. Samal ajal, niipea kui viimane nendega seotud tehing on lõppenud, saab lehti uuesti kasutada uute andmete jaoks. Kui objektid peavad neid tekitanud tehingu üle elama, tuleb need siiski kopeerida.
2. Readwrite tehingu puhul kehtib kursor tulemuseks olevale väärtusstruktuurile ainult kuni esimese muutmisprotseduuri (andmete kirjutamine või kustutamine).
3. Kuigi struktuur NodeValue mitte täisväärtuslik, vaid kärbitud (vt alajaotist “Võtmete tellimine välise komparaatori abil”), pääsed selle väljadele kursori kaudu turvaliselt juurde. Peaasi, et seda ei viidata!
4. Mitte mingil juhul ei tohi vastuvõetud kursori kaudu struktuuri muuta. Kõik muudatused tuleb teha ainult meetodi kaudu mdb_put. Kuid hoolimata sellest, kui kõvasti soovite seda teha, pole see võimalik, kuna mäluala, kus see struktuur asub, on kaardistatud kirjutuskaitstud režiimis.
5. Jaotage fail ümber protsessi aadressiruumi, et näiteks funktsiooni abil maksimaalset salvestusmahtu suurendada mdb_env_set_map_size tühistab täielikult kõik tehingud ja seotud olemid üldiselt ning osutab konkreetsetele objektidele.

Lõpuks on veel üks omadus nii salakaval, et selle olemuse paljastamine ei mahu lihtsalt järjekordsesse lõiku. B-puud käsitlevas peatükis andsin skeemi selle kohta, kuidas selle leheküljed on mälus paigutatud. Sellest järeldub, et serialiseeritud andmetega puhvri alguse aadress võib olla täiesti suvaline. Seetõttu sai nendele osutav osuti struktuuris MDB_val ja taandatuna struktuurile osutavaks osutiks, osutub see üldjuhul joondamata. Samal ajal nõuavad mõne kiibi arhitektuurid (iOS-i puhul armv7), et mis tahes andmete aadress oleks masinasõna suuruse kordne või teisisõnu süsteemi biti suurus ( armv7 jaoks on see 32 bitti). Teisisõnu, operatsioon nagu *(int *foo)0x800002 nende kohta on samaväärne põgenemisega ja viib hukkamiseni koos kohtuotsusega EXC_ARM_DA_ALIGN. Sellise kurva saatuse vältimiseks on kaks võimalust.

Esimene taandub andmete esialgsele kopeerimisele ilmselgelt joondatud struktuuri. Näiteks kohandatud võrdlusseadmes kajastub see järgmiselt.

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

Teine võimalus on teavitada kompilaatorit eelnevalt, et võtmeväärtuste struktuurid ei pruugi olla atribuutidega joondatud aligned(1). ARM-is saate sama efekti saavutada ja kasutades pakitud atribuuti. Arvestades, et see aitab optimeerida ka struktuuri poolt hõivatud ruumi, tundub see meetod mulle eelistatavam, kuigi приводит andmetele juurdepääsu toimingute kulude suurenemisele.

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

Vahemiku päringud

Kirjete rühma itereerimiseks pakub LMDB kursori abstraktsiooni. Vaatame, kuidas sellega töötada, kasutades meile juba tuttava kasutaja pilve metaandmetega tabeli näidet.

Kataloogis olevate failide loendi kuvamise osana on vaja leida kõik võtmed, millega selle alamfailid ja kaustad on seotud. Eelmistes alajaotistes sorteerisime võtmeid NodeKey nii, et need on peamiselt järjestatud ülemkataloogi ID järgi. Seega tehniliselt taandub kausta sisu allalaadimise ülesanne kursori asetamisele etteantud prefiksiga võtmete rühma ülemisele piirile ja seejärel itereerimisele alumisele piirile.

Ülemise piiri saab otse otsida järjestikuse otsinguga. Selleks asetatakse kursor kogu andmebaasi võtmete loendi algusesse ja suurendatakse seda edasi, kuni selle alla ilmub võti koos põhikataloogi identifikaatoriga. Sellel meetodil on kaks ilmset puudust:

1. Lineaarse otsingu keerukus, kuigi, nagu on teada, saab puude puhul üldiselt ja eriti B-puu puhul seda teha logaritmilises ajas.
2. Asjata, kõik otsitavale eelnevad leheküljed tõstetakse failist põhimällu, mis on äärmiselt kallis.

Õnneks pakub LMDB API tõhusat viisi kursori esmaseks positsioneerimiseks, selleks tuleb genereerida võti, mille väärtus on ilmselgelt väiksem või võrdne intervalli ülemisel piiril asuva võtmega. Näiteks ülaltoodud joonisel oleva loendi suhtes saame teha võtme, milles väli parentId on võrdne 2-ga ja kõik ülejäänud on täidetud nullidega. Selline osaliselt täidetud klahv antakse funktsiooni sisendisse mdb_cursor_get mis näitab operatsiooni 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);

Kui leitakse klahvirühma ülemine piir, siis kordame seda üle, kuni me kohtume või võti kohtub mõne teisega parentIdvõi võtmed ei saa üldse otsa.

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

Tore on see, et osana iteratsioonist, kasutades mdb_cursor_get, saame mitte ainult võtme, vaid ka väärtuse. Kui proovivõtutingimuste täitmiseks on vaja kontrollida muuhulgas kirje väärtuste osa välju, siis on need ilma täiendavate liigutusteta üsna kättesaadavad.

4.3. Seoste modelleerimine tabelite vahel

Nüüdseks oleme suutnud läbi mõelda kõik ühetabelilise andmebaasi kujundamise ja sellega töötamise aspektid. Võime öelda, et tabel on sorteeritud kirjete kogum, mis koosneb sama tüüpi võtme-väärtuste paaridest. Kui kuvate võtme ristkülikuna ja sellega seotud väärtust rööptahukana, saate andmebaasi visuaalse diagrammi.

​

Päriselus on aga harva võimalik nii vähese verevalamisega läbi saada. Sageli nõutakse andmebaasis esiteks mitme tabeli olemasolu ja teiseks nendes valikute tegemist primaarvõtmest erinevas järjekorras. See viimane osa on pühendatud nende loomise ja vastastikuse sidumise küsimustele.

Indeksi tabelid

Pilverakendusel on jaotis "Galerii". See kuvab meediumisisu kogu pilvest, sorteerituna kuupäeva järgi. Sellise valiku optimaalseks rakendamiseks peate põhitabeli kõrvale looma teise uut tüüpi klahvidega. Need sisaldavad välja faili loomise kuupäevaga, mis toimib peamise sortimise kriteeriumina. Kuna uued võtmed viitavad samadele andmetele nagu põhitabeli võtmed, nimetatakse neid registrivõtmeteks. Alloleval pildil on need oranžiga esile tõstetud.

Erinevate tabelite võtmete üksteisest eraldamiseks samas andmebaasis lisati neile kõigile täiendav tehniline väli tableId. Muutes selle sortimisel kõrgeimaks prioriteediks, saavutame võtmete rühmitamise esmalt tabelite kaupa ja tabelisiseselt – vastavalt meie enda reeglitele.​

Indeksi võti viitab samadele andmetele, mis primaarvõti. Selle atribuudi lihtne rakendamine primaarvõtme väärtuse osa koopia seostamise kaudu ei ole mitmest vaatenurgast optimaalne:

1. Kasutatava ruumi osas võivad metaandmed olla üsna rikkalikud.
2. Toimivuse seisukohalt, kuna sõlme metaandmete värskendamisel peate need kahe klahvi abil ümber kirjutama.
3. Kooditoe seisukohalt, kui unustame mõne võtme andmeid värskendada, saame salvestusruumis tabamatu andmete ebaühtluse vea.

Järgmisena kaalume, kuidas need puudused kõrvaldada.

Tabelite vaheliste suhete korraldamine

Muster sobib hästi indekstabeli sidumiseks põhitabeliga "võti väärtusena". Nagu nimigi ütleb, on indeksikirje väärtuse osa esmase võtme väärtuse koopia. See lähenemisviis kõrvaldab kõik ülalnimetatud puudused, mis on seotud esmase kirje väärtuse osa koopia salvestamisega. Ainus hind on see, et indeksivõtme järgi väärtuse saamiseks peate tegema andmebaasi ühe päringu asemel kaks päringut. Skemaatiliselt näeb saadud andmebaasiskeem välja selline.

Teine tabelitevaheliste suhete korraldamise muster on "liigne võti". Selle olemus on lisada võtmele täiendavaid atribuute, mida pole vaja sorteerimiseks, vaid seotud võtme taasloomiseks. Mail.ru pilverakenduses on selle kasutamise kohta tõelisi näiteid, et vältida sügavat sukeldumist konkreetsete iOS-i raamistike kontekstis toon fiktiivse, kuid selgema näite.​

Pilve mobiiliklientidel on leht, kus kuvatakse kõik failid ja kaustad, mida kasutaja on teiste inimestega jaganud. Kuna selliseid faile on suhteliselt vähe ja nendega on seotud palju erinevat tüüpi spetsiifilist teavet avalikustamise kohta (kellele antakse juurdepääs, milliste õigustega jne), ei ole mõistlik koormata faili väärtuse osa. salvestada sellega põhitabelisse. Kui aga soovite selliseid faile võrguühenduseta kuvada, peate need siiski kuhugi salvestama. Loomulik lahendus on luua selle jaoks eraldi tabel. Alloleval diagrammil on selle võtme eesliide "P" ja kohatäite "propname" saab asendada täpsema väärtusega "avalik teave".​

Kõik unikaalsed metaandmed, mille salvestamiseks uus tabel loodi, paigutatakse kirje väärtuste osasse. Samal ajal ei soovi te dubleerida andmeid failide ja kaustade kohta, mis on juba põhitabelisse salvestatud. Selle asemel lisatakse P-klahvile üleliigsed andmed väljade "sõlme ID" ja "ajatempel" kujul. Tänu neile saate koostada indeksivõtme, millest saate esmase võtme, millest lõpuks saate sõlme metaandmeid.

Järeldus

Hindame LMDB rakendamise tulemusi positiivselt. Pärast seda vähenes rakenduste külmutamise arv 30%.

Tehtud töö tulemused kõlasid iOS-i meeskonnast kaugemale. Praegu on Androidi rakenduse üks peamisi jaotisi "Failid" samuti LMDB kasutamisele üle läinud ja muud osad on teel. C-keel, milles on realiseeritud võtmeväärtuste pood, oli heaks abiks, et algselt luua selle ümber C++-s platvormiülene rakendusraamistik. Saadud C++ teegi sujuvaks ühendamiseks Objective-C ja Kotlini platvormikoodiga kasutati koodigeneraatorit. Djinni Dropboxist, aga see on hoopis teine ​​lugu.

Allikas: www.habr.com