2019. aasta sügisel toimus Mail.ru pilveteenuste iOS meeskonnas kauaoodatud sündmus. Peamiseks andmebaasiks rakenduse oleku püsivaks salvestamiseks sai üsna eksootiline lahendus mobiilimaailmas. Lightning Memory-Mapped Database (LMDB). Allpool on teie tähelepanu vääriv detailne ülevaade neljas osas. Esiteks arutame, miks selline ebatavaline ja keeruline valik tehti. Seejärel liigume edasi LMDB arhitektuuri kolme põhikonkreetse asja juurde: mällu kaardistatud failid, B+-puu, copy-on-write lähenemine tehingute ja mitme versiooni rakendamiseks. Lõpuks, magus osa — praktiline osa. Selles vaatleme, kuidas madalamale tasemele vastava key-value API põhjal projekteerida ja ellu viia andmeskeem mitme tabeliga, sealhulgas indeksi.

Sisukord

1. Rakendamise motivatsioon
2. LMDB positsioneerimine
3. Kolm põhitõde LMDB-s
   3.1. Tõde nr 1. Mällu kaardistatud failid
   3.2. Tõde nr 2. B+-puu
   3.3. Tõde nr 3. Copy-on-write
4. Andmeskeemi projekteerimine key-value API peal
   4.1. Põhistruktuurid
   4.2. Tabelite modelleerimine
   4.3. Tabelitevaheliste seoste modelleerimine

1. Rakendamise motivatsioon

Kord umbes 2015. aastal tekkis meil mure, et meie rakenduse liides laguneb liiga sageli. Me ei teinud seda lihtsalt niisama. Me saime rohkem kaebusi selle üle, et rakendus mõnikord ei reageeri kasutaja toimingutele: nupud ei tööta, nimekirjad ei kerita jne. Kui palju selliseid mõõtmisi tehti, on sellest, AvitoTechis, seega toon siin esile vaid numbreid.

Mõõtmise tulemused olid meie jaoks külm dušš. Tuli välja, et külmusest tingitud probleeme on palju rohkem kui mingeid teisi. Kui enne selle fakti teadvustamist oli peamine tehniline kvaliteedi näitaja crash free, siis pärast fookus liikus freeze free-ile.

Kasutades jääke ja tehes kvantitatiivset ja kvalitatiivset analüüsi, sai selgeks, kes on peamine vaenlane — raske äri loogika, mis töötas rakenduse põhijoonel. Loomulik reaktsioon sellele segadusele oli tungiv soov see ära jagada töövoogudesse. Sellise probleemi süsteemseks lahendamiseks kasutasime kergekaaluliste näitlejate põhjal mitme lõime arhitektuuri. Selle rakendust iOS maailmas ma pühendasin kahele teemale kollektiivses Twitteris ja artiklile Habras. Praeguses jutustuses soovin rõhutada neid lahenduse aspekte, mis mõjutasid andmebaasi valikut.

Aktaormodeli süsteemi korralduses eeldab, et mitme lõime kasutamine saab selle teiseks olemuseks. Mudeli objektid armastavad ületada lõimede piire. Ja nad teevad seda mitte aeg-ajalt ja kuskil, vaid peaaegu pidevalt ja igal pool.

Andmebaas on üks peamisi komponente esitatud skeemis. Selle peamine ülesanne on makropatterni rakendamine Jagatud andmebaas. Kui ettevõtlusmaailmas korraldatakse selle abiga andmete sünkroniseerimist teenuste vahel, siis aktorite arhitektuuri puhul – lõimede vahel. Seetõttu vajasime sellist andmebaasi, mille kasutamine mitme lõime keskkonnas ei tekitaks isegi minimaalset keerukust. Eelkõige tähendab see, et saadud objektid peavad olema vähemalt lõimede ohutud ja ideaalis täiesti muutumatud. Nagu teada, saab viimaseid kasutada samaaegselt mitmest lõimest, vajamata mitte mingeid lukustusi, mis avaldab soodsat mõju jõudlusele.

Teine oluline tegur, mis mõjutas andmebaasi valikut, oli meie pilve API. See sai inspiratsiooni sünkroniseerimise lähenemisviisist, mida rakendati git'is. Nagu tema, sihime offline-first API, mis pilveklientide jaoks tundub rohkem kui sobiv. Eeldati, et nad laevad ainult kord täisolekusse pilve ja seejärel toimub sünkroniseerimine enamikus juhtudest muudatuste rakendamise kaudu. Kahjuks on see võimalus endiselt alles teoreetilises piirkonnas, ja praktikas ei ole kliendid patch'idega töötamist veel õppinud. Sellel on mitmeid objektiivseid põhjusi, mille me, et mitte viivitada sissejuhatusega, jätame kõrvale. Praegu on palju huvitavamad õpetlikud järeldused õppetundi kohta, mis toimub, kui API ütles "A", ja selle tarbija ei öelnud "B".

Nii et, kui te kujutate ette git'i, mis käsu pull täitmisel rakendab plaastrite asemel täieliku seisundi võrdlemist kohaliku ja serveri vahel, siis on teil piisavalt täpne arusaam sellest, kuidas toimub sünkroonimine pilveteenustes. Ei ole raske arvata, et selleks, et see toimuks, tuleb mälu allokeerida kahe DOM-puust, mis sisaldavad metaandmeid kõikide serveri ja kohalike failide kohta. Tulemuseks on see, et kui kasutaja hoiab pilves 500 000 faili, tuleb sünkroonimiseks taastada ja hävitada kaks puud, milles on 1 miljon sõlme. Iga sõlm on seotud objektrühmaga. Selle valguses olid profiliseerimise tulemused ootuspärased. Selgus, et isegi ilma sulandumise algoritmi arvestamata on juba tohutu hulga väikeste objektide loomine ja edasine hävitamine kulukas. Olukorda halvendab asjaolu, et põhisünkroonimise operatsioon on paljude kasutajaskenaaride osa. Tulemuseks fikseerime teise olulise kriteeriumi andmebaasi valikul — CRUD-operatsioonide teostamise võimaluse ilma dünaamilise objekti allokatsioonita.

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

1. Konteinerite ohutus.
2. Mugav mitme protsessi kasutamine. See on tingitud soovist kasutada sama andmebaasi instantsi staatuse sünkroonimiseks mitte ainult protsesside vahel, vaid ka peamise rakenduse ja iOS laienemiste vahel.
3. Võimalus esitada salvestatud entiteedid kui muutumatuid objekte.
4. CRUD-operatsioonide raames puudub dünaamiline allokatsioon.
5. Toetatakse tehingute põhiomadusi ACID: aatomilisus, järjepidevus, isoleeritus ja usaldusväärsus.
6. Kiirus kõige populaarsemates kasutusjuhtudes.

Hea valik selliste nõudmistega oli ja jääb SQLite. Olles uurinud alternatiive, sattusin ma raamatule «Getting Started with LevelDB». Tema juhtimisel kirjutati benchmark, mis võrdles erinevate andmebaaside töösuunatavuse kiirusetulemusi reaalses pilveskenaaris. Tulemused ületasid isegi kõige julgemad ootused. Kõige populaarsemates juhtumites - kursori saamine sorteeritud nimekirjas kõigist failidest ja sorteeritud nimekirjas kõikidest failidest antud kataloogis - osutus LMDB 10 korda kiiremaks kui SQLite. Valik osutus ilmseks.

2. LMDB positsioneerimine

LMDB on väike (ainult 10K rida) raamatukogu, mis rakendab andmebaaside kõige madalamat aluskihi - salvestust.

Esitatud skeem näitab, et LMDB võrdlemine SQLite-ga, mis rakendab ka kõrgemaid tasemeid, ei ole eriti korrektne, võrreldes SQLite-d Core Data-ga. Üks ühtekuuluvate konkurentide toommine oleks õiglasem võrrelda selliste salvestusmootoritega nagu BerkeleyDB, LevelDB, Sophia, RocksDB jne. On isegi arendusi, kus LMDB toimib SQLite storage engine'i komponendina. Esimese sellise eksperimentaalse katse viis 2012. aastal läbi autor LMDB Howard Chu , mille tulemused olid nii intrigeerivad, et tema algatus haarasid OSS-entusiastid ja leidis edasiarendust. tulemused näitasid ainult nelja ebaolulise koodibloki kattuvust, mis olid tingitud POSIX ja ANSI C nõuetest. LumoSQL . 2020. aasta jaanuaris esitas selle projekti autor Den Shearerselle LinuxConfAu. esitanud LMDB-d kasutatakse peamiselt rakenduslike andmebaaside mootori rollis. Selle raamatukogu ilmumine on seotud arendajatega

, kes ei olnud BerkeleyDB-st oma projekti aluseks eriti rahul. Alustades tagasihoidlikust raamatukogust OpenLDAPbtree , suutis Howard Chu luua ühe populaarseima alternatiivi tänapäeval. Sellele ajaloole ja ka LMDB sisemisele ülesehitusele pühendas ta oma väga laheda ettekande«The Lightning Memory-mapped Database» . Hea näitena salvestuse vallutamisest jagas Leonid Jurjev (akayleo ) Positive Technologies esitluses Highload 2015«LMDB mootori — eriline meister» . Seal räägib ta LMDB-st sarnase ülesande kontekstis ReOpenLDAP-i rakendamisel, samas kui LevelDB-d on eelnevalt võrreldud kriitika alla. Positive Technologiesi rakenduse tulemusena ilmnes isegi aktiivselt arenev forkMDBX maitsvate funktsioonide, optimeerimiste ja bugide parandamisega. LMDB-d kasutatakse sageli ka salvestusena as it is. Näiteks valis Mozilla Firefox.

selle mitmete vajaduste jaoks, ja alates 9. versioonist eelistas Xcode seda SQLite-le indeksite salvestamiseks. Mootor on nähtavale tulnud ka mobiiliarenduse maailmas. Selle kasutamise jälgi on võimalik leida. Džínd. Džínd.

Džínd. leida iOS klient Telegramile. LinkedIn läks veelgi kaugemale, valides vaikimisi andmete vahemäluks LMDB, mis on kodumaine andmete vahemälu raamistik Rocket Data, millest rääkis räägiti tema artiklis 2016. aastal.

LMDB võitleb edukalt oma koha eest päikese all, olles jätnud BerkeleyDB, mille Oracle on kontrolli alla võtnud. Raamatukogu on tuntud oma kiirus ja usaldusväärsus võrreldes teistega. Nagu teada, tasuta lõunaid ei ole, ja tahaksin rõhutada trade-off'i, millega tuleb silmitsi seista, valides LMDB ja SQLite vahel. Ülaltoodud skeem näitab selgelt, kuidas saavutatakse kõrgem kiirus. Esiteks, me ei maksa lisakihi abstraktsioonide eest, mis katab ketta salvestamist. Loomulikult ei saa head arhitektuur ilma nendeta hakkama, ja need ilmuvad kindlasti rakenduse koodis, kuid need on palju õhemad. Neil ei ole funktsioone, mis ei ole konkreetse rakenduse jaoks vajalikud, näiteks SQL-i päringute tugi. Teiseks, tekib võimalus rakendada optimaalselt rakenduslike operatsioonide kaardistamine kettasalvestuse päringutele. Kui SQLite oma töös toetub keskmiste rakenduste keskmistele vajadustele, siis te, kui rakenduse arendaja, olete hästi kursis peamiste koormusstsenaariumitega. Tõhusama lahenduse eest tuleb maksta kõrgemat hinda nii algse lahenduse väljatöötamisel kui ka selle edasises toetuses.

3. Kolm LMDB alustala

Vaadates LMDB-d linnulennult, on aeg sügavamale laskuda. Järgmised kolm peatükki keskenduvad peamistele alustaladele, millest salvestus arhitektuur koosneb:

1. Mälu kaardistatud failid kui ketta töötlemise ja sisemiste andmestruktuuride sünkroniseerimise mehhanism.
2. B+-puu andmete salvestamise struktuuri organiseerimise meetodina.
3. Copy-on-write lähenemisviisina ACID-omaduste ja mitme versiooni tagamise jaoks.

3.1. Alustala №1. Mälu kaardistatud failid

Mälule salvestatud failid on nii olulised arhitektuuri element, et need on isegi salvestuse nime osaks. Vahemälu ja salvestatud teabele juurdepääsu sünkroniseerimise küsimused on täielikult usaldatud operatsioonisüsteemile. LMDB ei sisalda endas mingeid vahemälu. See on autori teadlik otsus, kuna andmete lugemine otse mälust võimaldab rakenduse töötlemisel mitmeid nurki kärpida. Allpool toome välja vaid osalise loendi mõnest neist.

1. Andmete järjepidevuse säilitamine salvestuses, kui sellega tegeleb mitu protsessi, muutub operatsioonisüsteemi kohustuseks. Järgmises jaotises käsitletakse seda mehhanismi üksikasjalikult ja koos piltidega.
2. Vahemälu puudumine vabastab LMDB täielikult dünaamiliste jaotuste seotud kuludest. Andmete lugemine on praktikas lihtsalt õigesse virtuaalse mälu aadressi seadmine ja mitte midagi enamat. See kõlab nagu ulme, kuid salvestuse lähtekoodis on kõik salloc'i kutsed koondatud salvestuse konfigureerimise funktsiooni.
3. Vahemälu puudumine tähendab ka lukustuste puudumist, mis on seotud nende juurde pääsemise sünkroniseerimisega. Lugusid, keda võib samal ajal eksisteerida piiramatult, ei kohtu oma teel andmetele ühegi mutex-iga. Selle tõttu on lugemise kiirus ideaalne lineaarne skaleeritavus CPU arvu poolest. LMDB-s on sünkroniseeritud vaid muutvad operatsioonid. Kirjutaja võib olla igal hetkel vaid üks.
4. Minimum vahemälu ja sünkroniseerimise loogikat vabastab koodi äärmiselt keerulistest vigadest, mis on seotud mitme lõime keskkonnas töötamisega. Usenix OSDI 2014 konverentsil oli kaks huvitavat andmebaasi uurimistööd: „Kõik failisüsteemid ei ole loodud võrdselt: rakenduste lahingukindlate kujundamise keerukusest” ja „Andmebaaside piinamine lõbu ja kasu nimel”. Nendest võib leida teavet nii LMDB ületamatust usaldusväärsusest kui ka ACID-omaduste peaaegu veatust rakendamisest, mis ületab seda samas SQLite-s.
5. LMDB minimalism võimaldab masina esitusel oma koodi täielikult paikneda protsessori L1-vahemälus koos sealt tulenevate kiirusomadustega.

Kahjuks ei ole iOS-is mälu kaardistatud failidega kõik nii roosiline, nagu võiks loota. Et arutada nende puudusi teadlikumalt, tuleb meenutada selle mehhanismi rakendamise üldpõhimõtteid operatsioonisüsteemides.

Ülevaade mälu kaardistatud failidest

Iga käivitatava rakendusega seondub operatsioonisüsteemis üksus, mille nimi on protsess. Iga protsessile eraldatakse pidev aadressivahemik, kuhu paigutatakse kõik, mis on vajalik tema tööks. Madalamates aadressides asuvad koodi ja kõvadest andmetest koosnevad sektsioonid ning ressursside osad. Järgneb ülespoole kasvav dünaamilise aadressiruumi plokk, mida me paremini tunneme kui heap. Selles asuvad nende üksuste aadressid, mis ilmnevad rakenduse käitamise käigus. Ülal asub mälu osa, mida kasutab rakenduse virn. See laieneb ja tõmbub kokku, teisisõnu, selle suurus on samuti dünaamiline. Selleks, et virn ja heap omavahel ei seguneks ja ei häiriks, on nad eraldatud aadressiruumi erinevatesse otsadesse. Kaks dünaamilist sektsiooni ülemises ja alumises osas jätavad vahe. Operatsioonisüsteem kasutab selle keskmise osa aadresse, et siduda protsessidega eri üksusi. Eriti võib see seostada mingile pidevale aadresside kogumile - faili kettal. Sellist faili nimetatakse mälu kaardistatud failiks.

Protsessile eraldatud aadressiruumi maht on tohutu. Teoreetiliselt on aadresside arv piiratud vaid süsteemi bititasemega määratud näitaja suurusega. Kui sellel oleks 1-1 seos füüsilise mäluga, siis esimene protsess neelaks kogu RAM-i ning mitme ülesande täitmisest ei võikski juttu olla.

Kuid meie kogemuse põhjal teame, et tänapäevased operatsioonisüsteemid suudavad samaaegselt käitada piiramatult palju protsesse. See on võimalik, kuna nad eraldavad protsessidele mälu ainult paberi peal, kuid tegelikult laadivad põhifüüsilisse mällu vaid selle osa, mis on tänasel hetkel nõutud. Seetõttu nimetatakse protsessiga seotud mälu virtuaalseks.

Operatsioonisüsteem korraldab virtuaalset ja füüsilist mälu kindla suurusega lehtedena. Kui mõni virtuaalse mälu leht on nõutud, laadib operatsioonisüsteem selle füüsilisse mällu ja seab nende vahel vastavuse spetsiaalsesse tabelisse. Kui vabad kohad puuduvad, kopeeritakse üks varasemalt laaditud leht kettale ja nõutud leht asub selle kohale. Seda protseduuri, millega me varsti tagasi tuleme, nimetatakse vahetuseks (swapping). Allolev joonis illustreerib kirjeldatud protsessi. Sel on leht A, mille aadress on 0, laaditud ja paigutatud põhiketta lehele, mille aadress on 4. See fakt kajastub vastavustabelis lahtris number 0.

Kuvatud failide mälu ajalugu on täpselt sama. Loogiliselt need näiliselt pidevalt ja terviklikult asetsevad virtuaalses aadressiruumis. Kuid füüsilisse mällu jõuavad nad lehtedena ja vaid nõudmisel. Selliste lehtede muutmine sünkroniseeritakse kettafailiga. Nii on võimalik teostada failide sisendi/väljundi operatsioone, töötades lihtsalt mälus baitidega — kõik muudatused kantakse automaatselt operatsioonisüsteemi tuuma poolt algsete failideni.
​
Allolev pilt näitab, kuidas LMDB sünkroniseerib oma seisundit töötades andmebaasiga erinevate protsesside vahel. Kaardistades erinevate protsesside virtuaalse mälu ühe ja sama failiga, kohustame de facto operatsioonisüsteemi sünkroniseerima teatud nende aadressiruumide blokke, kuhu LMDB vaatab.
​

Oluline nüanss on see, et LMDB muudab andmefaili vaikimisi süsteemi kutse write kaudu, samas kui fail ise on avatud ainult lugemiseks. Selle lähenemisviisi on kaks olulist tagajärge.

Esimene tagajärg on kõigile operatsioonisüsteemidele ühine. Selle põhiolemus on kaitse andmebaasi tahtmatu kahjustamise eest vale koodi poolt. Nagu on teada, võivad protsessi täidetavad käsud vabalt pääseda ligi mis tahes andmetele selle aadressiruumi mis tahes kohas. Samas, nagu me just mainisime, tähendab faili kuvamine lugemise ja kirjutamise režiimis, et iga käsk võib seda ka muuta. Kui ta teeb seda ekslikult, näiteks püüdes tegelikult ümber kirjutada massiivi elementi mitteseksist indeksiga, võib see kogemata muuta sellele aadressile kaardistatud faili, mis viib andmebaasi riknemiseni. Kui aga fail on kaardistatud lugemiseks, siis katse muuta vastavat aadressiruumi toob kaasa programmi ootamatu lõpetamise signaaliga SIGSEGV, ja fail jääb terviklikuks.

Teine tagajärg on juba spetsiifiline iOS-ile. Ei autor ega ükski teine allikas ei maini seda otseselt, kuid ilma selleta ei oleks LMDB selles mobiiloperatsioonisüsteemis kasutatav. Selle käsitlemiseks on pühendatud järgmine jaotis.

Kuvatud mälufailide spetsiifika iOS-is

2018. aastal oli WWDC-l suurepärane ettekande „iOS Memory Deep Dive“. Sellega räägitakse, et iOS-is kuuluvad kõik füüsilises mälus asuvad lehed ühte kolmest tüübid: dirty, compressed ja clean.

Clean memory on lehtede kogum, mis võib probleemideta füüsilisest mälust välja laadida. Nendes asuvaid andmeid saab vajadusel uuesti laadida nende algsetest allikatest. Lugemiseks mõeldud kaardistatud failid kuuluvad just sellesse kategooriasse. iOS ei karda igal ajal kaardistatud lehti mälust välja laadida, kuna need on garanteeritult sünkroonitud failiga kettal.
​
Dirty memory sisaldab kõiki muudetud lehti, olenemata sellest, kus nad esialgu asusid. Eelkõige liigitatakse sellesse ka kaardistatud failid, mida on muudetud kirjutamise kaudu neile seotud virtuaalsesse mällu. Avades LMDB flagiga MDB_WRITEMAP, saate pärast muudatuste tegemist sellega ise veenduda.

Kui rakendus hakkab tarbima liiga palju füüsilist mälu, allutab iOS selle dirty leheküljed kompressioonile. Rakenduse mälu jalajälg koosneb dirty ja kompressitud lehekülgedest. Kui see saavutab teatud künnise, sekkub süsteemne demon OOM killer ja lõpetab protsessi sunniviisil. See on iOS-i eripära võrreldes lauaarvutite operatsioonisüsteemidega. Erinevalt neist ei ole iOS-is lehekülgede vahetamiseks füüsilisest mälust kettale memory footprint'i vähendamine ette nähtud. Põhjustest saab vaid spekuleerida. Võib-olla on lehekülgede intensiivne liigutamine kettale ja tagasi liiga energiakulukas mobiildevice'ide jaoks või iOS säästab SSD-de lahtrite üle kirjutamise ressursse, või polnud disainerite rahul süsteemi üldise jõudlusega, kus kõik pidevalt vahetub. Kuidas iganes see ka poleks, fakt jääb faktiks.

Hea uudis, nagu juba mainitud, on see, et LMDB ei kasuta vaikimisi mmap mehhanismi failide värskendamiseks. Seega klassifitseeritakse kuvatavad andmed iOS-i poolt kui puhas mälu ja need ei suurenda memory footprint'i. Seda saab kontrollida Xcode'i tööriista VM Tracker abil. Alloleval ekraanipildil on näidatud iOS-i rakenduse Oblaak virtuaalmälu olek töö ajal. Alguses oli sellel initsialiseeritud 2 LMDB instantsi. Esimesele lubati oma faili kuvada 1GiB virtuaalses mälus, teisele – 512MiB. Kuigi mõlemad andmehoidlad võtavad teatud hulga residentset mälu, ei aita kumbki dirty size'i suurendada.

Ja nüüd on aeg halbadeks uudisteks. 64-bitiste lauaarvutite operatsioonisüsteemides võimaldab vahetusmehhanism iga protsessile võtta niipalju virtuaalset aadressiruumi, kui lubab vaba ruum kõvakettal tema potentsiaalse vahetuse jaoks. Vahetuse asendamine kompressiooniga iOS-is vähendab teoreetilist maksimaali radikaalselt. Nüüd peavad kõik elavad protsessid mahtuma põhimenüüsse (loe: operatiivmälu), ja kõik, mis ei mahu, tuleb sunniviisiliselt lõpetada. Sellest räägitakse ka eelnevas. ettekandes, kui ka ametlikust dokumentatsioonistSeetõttu piirab iOS rangelt mälu suurust, mis on saadaval mmap-i kaudu eraldamiseks. Siin on siit Saame vaadata empiirilisi piire mälu mahtude osas, mida on võimalik eraldada erinevatele seadmetele selle süsteemi kõne abil. Kõige kaasaegsematel iOS-i nutitelefonidel on eraldatud 2 gigabaidi, samas kui tipptasemel iPad'i mudelitel on see 4. Praktiliselt tuleb siiski orienteeruda kõige madalama klassi toetamiste seadmetele, kus olukord on väga halb. Veel hullem, kui vaadata rakenduse mälu olekut VM Trackeris, võib avastada, et LMDB ei ole kaugeltki ainus, kes taotleb memory-mapped mälu. Suured osad mälu kasutavad süsteemi jaotajad, ressursifailid, pilditöötluse raamistikud ja teised väiksemad röövlid.

Eksperimentide tulemuste põhjal pilves jõudsime järgmiste kompromisssete väärtusteni eraldatud LMDB mälu osas: 384 megabaiti 32-bitiste seadmete jaoks ja 768 megabaiti 64-bitiste jaoks. Pärast selle mahu kasutamist lõpetavad kõik muudatustega seotud toimingud koodi MDB_MAP_FULL. Selliseid vigu oleme jälginud meie monitooringus, kuid neid on piisavalt vähe, et neid praeguses etapis saaks ignoreerida.

Mälu üleliigse tarbimise mitteilmne põhjuse võib olla pikaajalised tehingud. Et mõista, kuidas need kaks nähtust on seotud, aitab meil kahe ülejäänud LMDB 'hiigla' vaatamine.

3.2. Hiiglane nr 2. B+-puu

Key-value andmehoidla kohal tabelite emuleerimiseks peab selle API-s olema järgmised toimingud:

1. Uue elemendi sisestamine.
2. Elemendi otsimine antud võtme alusel.
3. Elemendi eemaldamine.
4. Võtmepaaride sorteeritud järjekorras läbimine.

Lihtsaim andmestruktuur, mille abil on võimalik hõlpsasti teostada kõiki nelja toimingut, on binaarne otsingupuu. Iga sõlm esindab key, jagades kogu alamkomplekti alamvõtmete vahel kaheks alampuuks. Vasakul on need, mis on väiksemad vanemast, ja paremal need, mis on suuremad. Korrastatud võtmete kogumi saamine saavutatakse ühe klassikalise puu läbimisega.

Binaarpuudel on kaks fundamentaalset puudust, mis takistavad neil olla tõhusad diskistruktuuride andmestruktuuridena. Esiteks on nende tasakaalu aste ettearvamatu. On suur risk saada puid, mille erinevate harude kõrgus võib oluliselt erineda, mis halvendab oluliselt otsingu algoritmilist keerukust võrreldes ootustega. Teiseks, sõlmede vaheliste ristviidete rohkus kaotab binaarpuude mälus paiknemise lokaalsuse. Lähedased sõlmed (seoses nendevaheliste sidemetega) võivad asuda täiesti erinevates lehtedes virtuaalses mälus. Selle tagajärjel võib isegi mõne naabersõlme lihtne läbimine nõuda võrreldavat hulka lehti. See on probleem isegi siis, kui räägime binaarpuude efektiivsusest in-memory andmestruktuuridena, kuna pidev lehtede rotatsioon protsessori mälus on kulukas. Kui aga jutt käib seotud sõlmede lehtede sagedasest tõstmisest kettalt, muutub olukord tõeliselt kehv. halb.

B-puud, olles binaarpuude evolutsioon, lahendavad eespool nimetatud probleemid. Esiteks, nad on isetasakaaluvad. Teiseks, iga nende sõlm jagab hulga alamvõtmeid mitte 2, vaid M järjekorras alarühmaks, kusjuures M-i arv võib olla üsna suur, ulatudes mitmesaja või isegi tuhande piirini.

Selle tulemusel:

1. Igas sõlmes on suur hulk juba järjestatud võtmeid ja puud osutuvad väga madalaks.
2. Puul on mälus paiknemise lokaalsuse omadus, kuna sarnaste väärtustega võtmed paiknevad loomulikult üksteise kõrval samas või naaber sõlmedes.
3. Otsinguoperatsiooni käigus väheneb puu allapoole liikudes ülemineku sõlmede arv.
4. Piiratud on loetavate sihtsõlmede arv vahemiku päringutes, kuna igas neist on juba suur hulk järjestatud võtmeid.

LMDB-s andmete salvestamiseks kasutatakse B-puu ühte variatsiooni, mida nimetatakse B+-puuks. Ülaltoodud joonisel on kujutatud kolme tüüpi sõlmi, mis selles esinevad:

1. Tipus asub juur (root). See materialiseerib enamasti vaid andmebaasi kontseptsiooni salvestuses. Ühes LMDB instantsis on võimalik luua mitu andmebaasi, mis jagavad omavahel kaardistatud virtuaalset aadressiruumi. Igaüks neist algab omaenda juurest.
2. Kõige alumisel tasemel asuvad lehed (leaf). Need sisaldavad ainult andmebaasis hoitavaid võtme-väärtus paare. See on B+-puu eripära. Kui tavaline B-puu salvestab väärtusosad kõigi tasemete sõlmedes, siis B+-variatsioon ainult kõige alumisel tasandil. Pidades seda fakti meeles, nimetame edasi LMDB-s kasutatavat puu alamtüüp lihtsalt B-puuks.
3. Juurte ja lehtede vahele asub 0 või enam tehnilist taset navigeerimis (branch) sõlmedega. Nende ülesanne on jagada sorteeritud võtmete kogumit lehtede vahel.

Füüsiliselt on sõlmed eelnevalt määratud pikkusega mälublokid. Nende suurus on mälulehtede suuruse korrutis, millest rääkisime varem. Allpool on kujutatud sõlme struktuuri. Pealkirjas asub meta-informatsioon, kõige ilmekam näide on kontrollsummal. Seejärel on info ofsettidest, mille järgi asuvad andmepesad. Andmetena võivad esindada kas võtmed, kui räägime navigeerimis-sõlmedest, või täielikud võtme-väärtus paarid lehtede puhul. Rohkem lehtede struktuuri kohta saab lugeda tööst „Evaluation of High Performance Key-Value Stores“.

Pärast sisemist sõlmede-lehtede sisu selgitamist esitame LMDB B-puude lihtsalt järgmise kujuga.

Sõlmedega lehed asuvad järkjärgult kettal. Suuremalt numbritelt sõlmed asuvad faili lõpupoole. Nii-öelda meta-leht (meta page) sisaldab teavet ofsettidest, mille järgi saab leida kõigi puude juured. LMDB faili avamisel skaneerib see lehekaupa faili lõpust algusse valideeritud meta-lehe leidmiseks ja juba selle kaudu leiab olemasolevad andmebaasid.

Nüüd, kui on loodud ettekujutus andmete korralduse loogilisest ja füüsilisest struktuurist, saab edasi liikuda LMDB kolmanda toe käsitlemise juurde. Just selle abil toimuvad kõik muudatused salvestuses tehinguliselt ja üksteisest isoleeritult, andes andmebaasile tervikuna ka mitme versiooni omaduse.

3.3. Tugi №3. Copy-on-write

Mõned B-puu operatsioonid hõlmavad mitme muudatuse tegemist selle sõlmedes. Üks näide on uue võtme lisamine sõlmele, kus on juba saavutatud maksimaalne mahutavus. Sellisel juhul tuleb esmalt jagada sõlm kaheks ja teiseks lisada viide uuele eraldunud tütarsõlmele selle vanemasõlmes. See protseduur on potentsiaalselt väga ohtlik. Kui mingil põhjusel (krahh, voolukatkestus jne) toimub ainult osa muudatusi seeriast, jääb puu konsistentsi seisundisse.

Üks traditsioonilisi lahendusi andmebaasi töökindluse tagamiseks on B-puu kõrval lisadiskistruktuuri — tehingute logi, mida tuntakse ka kui write-ahead log (WAL). See on fail, kuhu kirjutatakse enne B-puu enda muutmist soovitud operatsioon. Nii, kui enesediagnoosi käigus tuvastatakse andmete rikkumine, konsultatsioon andmebaasi logiga, et ennast korda seada.

LMDB on vigade tagamise mehhanismi valimisel valinud teise meetodi, mida nimetatakse copy-on-write. Selle põhiolemus on see, et andmeid olemasolevas lehes ei uuendata, vaid need kopeeritakse täielikult ja kõik muudatused tehakse juba koopia peale.

Edasi, et uuendatud andmed oleksid kättesaadavad, tuleb muuta viiteid nimeka sõlme suhtes tema vanemasõlmes. Kuna selleks tuleb ka seda modifitseerida, kopeeritakse see ka eelnevalt. Protsess jätkub rekursiivselt juureni. Viimaks muudetakse andmed meta-lehe peal.

Kui uuendamise protseduuri ajal peaks toimuma ootamatu protsessi lõpetamine, siis kas uut meta-lehte ei luleta üldse või ei salvestata seda kettale lõpuni, mille tulemuseks on vale kontrollsumma. Ühes nendes kahest olukorrast ei ole uued lehed kättesaadavad ja vanad jäävad terveks. See vabastab LMDB vajadusest pidada write ahead log'i andmete konsistentsi tagamiseks. Ülaltoodud kettastruktuur täidab samal ajal ka selle funktsiooni. Tehingulogide puudumine otseselt on üks LMDB omadusi, mis tagab kiire andme lugemise.

Saadud struktuur, mida nimetatakse append-only B-puuks, tagab loomulikult tehingute isolatsiooni ja mitu versiooni. LMDB-s seondub iga avatud tehinguga ajakohane puu juur. Kuni tehing pole lõpetatud, ei muudetud ega kasutatud seonduvaid lehti uute andme versioonide jaoks kunagi. Nii on võimalik töötada lõpmatult täpselt nende andmete kogumiga, mis oli avamise hetkel kehtiv, isegi kui salvestus jätkab aktiivset uuendamist. See on mitme versiooni olemus, mis teeb LMDB-st ideaalse andmeallika meie armastatud UICollectionView. Tehingu avamisel ei ole vaja suurendada rakenduse mälu jalajälge, kiirustades asjakohaste andmete väljavõtmisega mingisse in-memory struktuuri, kartes end surnud nurka jääda. See omadus eristab LMDB-d SQLite-st, millel ei ole sellist täielikku isolatsiooni. Avades viimases kaks tehingut ja kustutades ühe kirje, ei saa seda kirjet enam teises allesolevas tehingus kätte.

Vastuvõtu tagaküljeks on potentsiaalselt oluliselt suurem virtuaalmälu kasutamine. Kaldkriipsul on näidatud, kuidas andmebaasi struktuur välja näeb, kui selle modifitseerimist tehakse samal ajal kolme avatud lugemise tehinguga, mis vaatavad erinevaid andmebaasi versioone. Kuna LMDB ei saa taaskasutada juuri, mis on seotud aktiivsete tehingutega, ei jää salvestamisele muud teha, kui mälus luua veel üks neljas juur ja taas kord kloonida selle alla modifitseeritavad lehed.

Siin on sobilik meenutada mälu kaardistatud failide osa. Tundub, et täiendav virtuaalmälu kasutamine ei tohiks meid liiga häirida, kuna see ei mõjuta rakenduse mälu jalajälge. Kuid samas on märgitud, et iOS on selle jaotamise osas väga kitsi ning me ei saa nagu serveris või lauaarvutis LMDB-le ühe terabaidi piirkonda vabatahtlikult anda ja sellest omadusest üldse mitte mõelda. Vaja on püüda hoida tehingute eluaeg võimalikult lühikesena.

4. Andmeskeemi kavandamine key-value API peal

API analüüsi alustame LMDB poolt pakutavate põhistruktuuride uurimisega: keskkond ja andmebaasid, võtmed ja väärtused, tehingud ja kursorid.

Märkus koodiloendite kohta

Kõik LMDB avaliku API funktsioonid tagastavad oma töö tulemuse veakoodina, kuid järgnevatel loenditel on selle kontrollimise osa lohakam plaan, et hoida kokku teksti. Praktikas kasutasime me salvestussüsteemiga suhtlemiseks oma fork C++ ümbermõõtjat lmdbxx, milles vead materialiseeruvad C++ eranditena.

Kiireim viis LMDB projekti integreerimiseks iOS või macOS jaoks on minu CocoaPod POSLMDB.

4.1. Põhistruktuurid

Keskkond (environment)

Struktuur MDB_env on LMDB sisemiste olekute hoidla. Funktsioonide kogum eessõnaga mdb_env võimaldab konfigureerida mõningaid selle omadusi. Kõige lihtsamal juhul näeb mootori initsialiseerimine 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 Cloud rakenduses muutsime vaikimisi ainult kaht parameetrit.

Esimene neist on virtuaalse aadressiruumi suurus, millele salvestusfail kaardistatakse. Kahjuks võib isegi samal seadmel konkreetne väärtus oluliselt erineda käivituse kaupa. Selle iOS-i eripära arvessevõtmiseks valitakse maksimaalne salvestusruum dünaamiliselt. Alustades mingist väärtusest, vähendatakse seda järk-järgult poole võrra seni, kuni funktsioon mdb_env_open tagastab tulemuse, mis erineb ENOMEM. Teoorias on olemas ka vastupidine tee — kõigepealt eraldada mootorile minimaalne mälu ja seejärel, kui vigu tekib, suurendada seda. Kuid see on palju keerulisem. Põhjus on selles, et mälu taasalustamise protseduur (remap) funktsiooni MDB_MAP_FULLmdb_env_set_map_size abil kehtetuks kõik entiteedid (kursused, tehingud, võtmed ja väärtused), mis on eelnevalt mootorilt saadud. Sellise sündmuste käigu arvesse võtmine koodis muudab selle oluliselt keerulisemaks. Kui aga virtuaalne mälu on teile tõeliselt oluline, siis võib see olla põhjus tutvuda kaugele arenenud forkiga , kus üks lubatud funktsioone on «automaatne andmebaasi suuruse kõva reguleerimine». maitsvate funktsioonide, optimeerimiste jaTeine parameeter, mille põhiväärtus meile ei sobinud, reguleerib lõimede ohutuse tagamise mehhanismi. Kahjuks on vähemalt iOS 10-s probleeme lõimede kohaliku salvestuse toetamisega. Seetõttu avatakse eespool toodud näites salvestus lipu

MDB_NOTLS . Lisaks oli vajalik kaforkida C++ ümbris , et selle atribuudi muutujad seal välja lõigata. lmdbxxAndmebaas on eraldi B-puu instants, millest me eelnevalt rääkisime. Selle avamine toimub tehingu raames, mis võib alguses tunduda veidi kummaline.

Andmebaasid

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, tehing LMDB-s on salvestuse entiteet, mitte konkreetne andmebaas. Selline kontseptsioon võimaldab teostada aatomseid operatsioone entiteetide üle, mis asuvad erinevates andmebaasides. Teoorias avab see võimaluse modelleerida tabeleid erinevate andmebaasidena, kuid mina valisin sel ajal teistsuguse tee, mis on allpool põhjalikult kirjeldatud.

Võtmed ja väärtused

MDB_val

Struktuur MDB_val mudelib kontseptsiooni nii võtme kui ka väärtusena. Salvestus ei oma vähimatki arusaama nende semantikat. Tema jaoks on midagi teist lihtsalt määratletud suurusega baitide massiiv. Maksimaalne võtme suurus on 512 baiti.

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

Komparaatori abil järjestab salvestus võtmed kasvavas järjestuses. Kui seda enda omaga ei asendata, kasutatakse vaikimisi, mis järjestab need baitide kaupa leksikograafilises järjekorras.

Tehingud

Tehingute mehhanism on detailne kirjeldus eelnevas peatükis, seetõttu kordaksin siin lühidalt nende peamisi omadusi:

1. Kõigi põhiosade tugi ACID: atomaarne, järjepidevus, isoleeritus ja usaldusväärsus. Pean märkima, et osas durability on macOS-il ja iOS-il olemas viga, mis on parandatud MDBX-is. Täiendavalt saab lugeda nende näiteks, mis kuvatakse armatuurlaudade peal koos Prometheuse päringutega, mis täidavad armatuure..
2. Lähenemine mitme niidi toetusele on kirjeldatud skeemiga „üks kirjutaja / mitu lugejat“. Kirjutajad blokeerivad üksteist, kuid ei blokeeri lugejaid. Lugejad ei blokeeri ei kirjutajaid ega üksteist.
3. Sisseehitatud tehingute tugi.
4. Mitme versiooni toetamine.

Mitme versiooni tugi LMDB-s on nii hea, et soovin seda näidata tegevuses. Allpool olevast koodist on näha, et iga tehing töötab just selle andmebaasi versiooniga, mis oli avamise ajal aktuaalne, olles täielikult isoleeritud kõigist järgnevatest muudatustest. Salvestuse initsialiseerimine ja testandme salvestamine ei paku midagi huvitavat, seega on need rituaalid jäetud spoilerisse.

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

// Avame 2 tehingut, millest igaüks vaatab
// andmebaasi versiooni, kus on üks kirje.
mdb_txn_begin(env, NULL, 0, &txn1); // lugemis-kirjutamine
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // ainult lugemine

// Esiteks tehingus eemaldame andmebaasist olemasoleva kirje.
mdb_del(txn1, dbi, &key, NULL);
// Kinnitage eemaldamine.
mdb_txn_commit(txn1);

// Avame kolmanda tehingu, mis vaatab
// andmebaasi aktuaalset versiooni, kus kirje ei ole enam.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Veendume, et otsitud võtmega seonduvat kirjet enam ei eksisteeri.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Lõpetame tehingu.
mdb_txn_abort(txn3);

// Veendume, et teise tehingu raames, mis avati kirje olemasolu ajal
// andmebaasis, on kirje endiselt leitav võtme järgi.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Kontrollime, et võtme järgi saame mitte lihtsalt rämpsdata, vaid kehtivad andmed.
assert(*(int *)val.mv_data == 997);
// Lõpetame tehingu, mis töötab ehkki aegunud, kuid konsistentse andmebaasiga.
mdb_txn_abort(txn2);

Soovitan proovida sama trikki SQLite'iga ja vaadata, mis välja tuleb.

Mitme versiooni olemasolu toob iOS arendaja ellu väga meeldivaid boonuseid. Selle omaduse abil saab andmeallika (data source) värskendamise kiirusest mugavalt ja lihtsalt reguleerida ekraanivormide jaoks, lähtudes kasutajakogemusest. Näiteks võtame Mail.ru pilve rakenduse funktsiooni, kus sisu laadimine toimub süsteemi meediagalerii kaudu. Headel ühendustel suudab klient serverisse lisada mitu fotot sekundis. Kui iga laadimise järel ajakohastada UICollectionView kasutaja pilves oleva meediasisuga, siis võib 60 fps-st ja sujuvast kerimisest selle protsessi ajal unustada. Et vältida sagedasi ekraani värskendusi, on vajalik kuidagi piirata andmete muutmise kiirusel aluse. UICollectionViewDataSource.

Kui andmebaas ei toeta mitme versiooni kasutamist ja võimaldab töötada vaid praeguse kehtiva olekuga, tuleb stabiilse ajas säiliva andmesnapshooti loomiseks see kopeerida kas mingisse mälustruktuuri või ajutisse tabelisse. Mõlemad lähenemisviisid on väga kulukad. Mälus hoidmise puhul kaasnevad kulud mäluga, mis on seotud konstrueeritud objektide hoidmisega, samuti ajaga, mis on seotud liigsete ORM-muutmistega. Mis puudutab ajutist tabelit, siis see on veelgi kallim lahendus, millel on mõttekus vaid keerukates juhtumites.

LMDB mitme versiooni kasutamine lahendab stabiilse andmeallika säilitamise ülesande väga elegantselt. Piisab lihtsalt tehingu avamisest ja voilà – seni, kuni me selle ei lõpeta, on andmestik meil garanteeritult fikseeritud. Selle värskendamise kiirus on nüüd täielikult ja täielikult esitluskihti kontrolli all, ilma igasuguste oluliste ressursside kuludeta.

Kursorid

Kursorid pakuvad mehhanismi paigutatud iteratsiooniks võtme-väärtuse paaride üle, läbides B-puude. Ilma nendeta oleks võimatu tõhusalt modelleerida andmebaasi tabeleid, mille arutlemiseks me liikume.

4.2. Tabelite modelleerimine

Võtmepaaride järjekorra omadus võimaldab ehitada põhiabstraktsiooni peal kõrgetasemelisi nagu tabel. Vaatleme seda protsessi pilguga, võtame näiteks põhiteabe tabeli pilveklientidest, kus on vahemällu salvestatud teave kõigi kasutaja failide ja kaustade kohta.

Tabeli skeem

Üks sagedasi stsenaariume, mille jaoks peab kaustade puu struktuur olema kohandatud, on kõikide elementide valimine, mis asuvad määratud kaustas. Hea andmete korraldamise mudel tõhusate taotluste jaoks sellise ülesande jaoks on Adjacency List. Selle elluviimiseks võtme-väärtuse hoidlal tuleb sorteerida failide ja kaustade võtmed nii, et need rühmitatakse vastavalt vanemkausta kuuluvusele. Lisaks, et kuvada kausta sisu kasutaja Windowsi tuttavas vaates (kõigepealt kaustad, seejärel failid, ja mõlemad on sorteeritud tähestikulises järjekorras), tuleb võtmesse lisada vastavad täiendavad väljad.

Allpool on esitatud, kuidas lähtudes antud ülesandest võivad võtmed välja näha baitide massiivina. Esiteks asetatakse vanem directory identifikaatorid (punased), siis tüüp (rohelised) ja lõpuks nimi (sinised). Markeeritud LMDB vaikimisi võrdleja poolt leksikograafilises järjekorras, need asetatakse nõutud viisil. Ühe ja sama punase prefiksiga võtmete järjestikune läbikäik annab meile seotud väärtused selles järjekorras, milles need peavad kasutajaliideses (paremal) olema välja toodud, ilma et oleks vaja veel mingit täiendavat järeltöötlemist.

Võtmete ja väärtuste serialiseerimine

Maailmas on välja mõeldud palju objekti serialiseerimise meetodeid. Kuna meil ei olnud muid nõudeid peale kiirus, valisime enda jaoks kõige kiirema — C keele struktuuri meenutava mälu dumpimise. Nii saab kausta elemendi võtit modelleerida järgmise struktuuriga NodeKey.

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

Säilitamiseks NodeKey salvestusruumis tuleb objektis MDB_val paigutada andmete viit algstruktuuri aadressile ja nende suurus arvutada funktsiooniga sizeof.

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

Esimeses peatükis andmebaasi valimise kriteeriumitest mainisin olulise valikufaktorina dünaamiliste eraldamiste vähendamist CRUD operatsioonide raames. Funktsiooni koodi serialize näitab, kuidas LMDB puhul saab uusi kirjeid andmebaasi sisestamisel need täielikult vältida. Serverist saabunud baitide massiiv muudetakse esmalt virnastavateks struktuurideks, seejärel dumpitakse need triviaalsetel viisidel salvestusse. Arvestades, et LMDB sees ei ole samuti dünaamilisi eraldamisi, saame fantastilise olukorra iOS-i mõõtkavas - andmete töötlemiseks nende teel võrgust kettani kasutatakse ainult virramälu!

Võtmete järjestamine binaarse võrdlejaga

Võtmete järjekord määratakse spetsiaalse funktsiooni, mida nimetatakse võrdlejaks. Kuna mootori jaoks ei ole mingit teavet nende sees olevate baitide semantika kohta, peab vaikimisi võrdleja rahulduma võtmete järjekorra määramisega leksikograafilises järjekorras, tuginedes nende baitide võrdlemisele. Selle kasutamine struktuuride järjestamiseks on sarnane liha lõikamisega puu nahaga. Siiski leian, et lihtsates olukordades on see meetod vastuvõetav. Alternatiiv on kirjeldatud allpool, kuid siinkohal mainin paar hajutatud takistust sellel teel.

Esimene asi, mida meeles pidada, on primitiivsete andmetüüpide edastamine mälus. Nii et kõik Apple'i seadmed salvestavad täisarvulised muutujaid formaadis Little Endian. See tähendab, et kõige vähem olulised bait asub vasakul ja täisarve ei saa nende baitide võrdlemisel sortida. Näiteks proovides sortida numbrite kogum alates 0 kuni 511, saadakse järgmine tulemus.

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

Selle probleemi lahendamiseks peavad täisarvud olema salvestatud võtmes sobivas formaadis, mida saab kasutada baitide võrdlejaga. Vajalikku konverteerimist aitavad funktsioonid perede hulgast hton* (eriti htons kahe baitide numbrite jaoks, mille üle me räägime).

Programmeerimises on stringide esitamistunne, see on, nagu teate, terviklik ajalugu. Kui stringide semantika ja nende mälus esitatav kodeering eeldab, et sümbol võib koosneda rohkem kui ühest baitist, siis on parem kohe loobuda vaikimisi võrdleja kasutamisest.

Teine asi, mida meeles pidada — struktuuri väljaade kvaliteedi kompilaatorite printsiibid. Nende tõttu võivad mälus väljaede vahel tekkida rämpsväärtused, mis muidugi rikub baitide sortimist. Rämpsu kõrvaldamiseks tuleb kas väljaede kuulutada kindlas järjestuses, meeles pidada allakirjutatud printsiibu reegleid, või kasutada struktuuri kuulutamisel atribuuti packed.

Võtmete järjestamine välist võrdlejaga

Võtmete võrdlemise loogika võib osutada liiga keeruliseks binaarsele võrdlejale. Üks paljusid põhjuseid on see, et struktuurides on tehnilised väljaed. Illustreerin nende esinemist juba tuntud võtme näitel kaustade elemendi jaoks.

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

Kuigi see on väga lihtne, tarbib see enamikul juhtudel liiga palju mälu. Puhver nime jaoks võtab 256 baiti, kuigi keskmiselt ületavad failide ja kaustade nimed harva 20-30 tähemärki.

Üks standardseid võtme suuruse optimeerimise meetodeid on selle "lõikamine" tegeliku suuruse järgi. Selle olemus seisneb selles, et kõik muutuva pikkusega väljade sisu salvestatakse struktuuri lõppu puhvris ja nende pikkused on eraldi muutujaid. Vastavalt sellele lähenemisele võtme NodeKey muudetakse järgmiselt.

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

Edasi seriaalimise korral määratakse andmete suuruseks mitte sizeof kogu struktuur, vaid kõik fikseeritud pikkusega väljad pluss reaalselt kasutatud puhvri osa suurus.

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

Refaktoreerimise tulemusena saavutame võtmete puhul märkimisväärse ruumi kokkuhoiu. Kuid tehnilise välja tõttu nameLength, ei sobi vaikimisi binaarne võrdleja enam võtmete võrdlemiseks. Kui me seda ei asenda oma omaga, siis nimi pikkus on sorteerimisel olulisem tegur kui nimi ise.

LMDB võimaldab igale andmebaasile määrata oma võtmete võrdlemise funktsiooni. Seda tehakse funktsiooni mdb_set_compare kaudu, rangelt enne andmebaasi avamist. Ilmselgetel põhjustel ei saa seda andmebaasi elu jooksul muuta. Võrdleja saab kaks binaarset võtit ja tagastab võrdlemise tulemuse: vähem (-1), rohkem (1) või võrdsed (0). Pseudokood NodeKey näeb välja järgmiselt.

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

Nii kaua, kui kõik andmebaasi võtmed on sama tüüpi, on nende baitide esituse tingimusteta teisendamine rakenduse võtmestruktuuri tüübiks seaduslik. Siin on üks nüanss, kuid selle käsitleme hiljem jaotises "Kirjete lugemine".

Väärtuste seriaalimine

LMDB salvestatud rekordite võtmed töötavad äärmiselt intensiivselt. Nende omavaheline võrdlemine toimub igas rakendusoperatsioonis, ja võrdleja töökiirus mõjutab kogu lahenduse jõudlust. Ideaalmaailmas piisaks võtmete võrdlemiseks vaikesissetatud binaarsest võrdlejast, kuid kui on vaja kasutada omaenda, peaks võtmete deserialiseerimise protseduur olema nii kiire kui võimalik.

Andmevälja (value) osas ei huvita andmebaasi eriti. Selle muutmine baitide representatsioonist objektiks toimub ainult siis, kui seda rakenduskoodis tõeliselt vajatakse, näiteks selle kuvamiseks ekraanil. Kuna seda juhtub suhteliselt harva, ei ole kiirusnõuded selle protseduuri jaoks nii kriitilised ja selle rakendamisel saame me palju vabamalt mugavuse poole püüelda. Näiteks kasutame metafailide, mis veel ei ole laaditud, serialiseerimiseks NSKeyedArchiver.

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

Siiski on juhtumeid, kus jõudlus on siiski oluline. Näiteks kasutame kasutaja pilve failistruktuuri metaandmete salvestamisel ikka sama objekti mälu dumpi. Ülesande eripära nende serialiseeritud esitusviisi genereerimisel on see, et katalooge modelleeritakse klasside hierarhiaga.

C keeles rakendades kantakse erikuuluvused eristruktuuridesse ja nende seos põhistruktuuriga määratakse unioni välja kaudu. Liidu praegune sisu määratakse tehnilise atribuudi kaudu type.

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

Salvestuste lisamine ja uuendamine

Serialiseeritud võti ja väärtus saab salvestustesse lisada. Selleks kasutatakse funktsiooni mdb_put.

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

Konfiguratsioonietapis võib salvestusele lubada või keelata mitme sama võtmega kirje salvestamise. Kui võtmete dubleerimine on keelatud, siis kirje sisestamise ajal saab määrata, kas olemasolevat kirjet on lubatud uuendada või mitte. Kui kattumine võib toimuda vaid koodi vea tõttu, siis saab seda ennetada, määrates lipu. NOOVERWRITE.

Kirjete lugemine

Kirjete lugemiseks on LMDB-s ette nähtud funktsioon mdb_get. Kui võtme-väärtuse paar on varem dump-struktuurides esitatud, siis näeb see protseduur välja järgmiselt.

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 koodinäide näitab, kuidas struktuuride dumpimise kaudu serialiseerimine võimaldab vabaneda dünaamilistest allokatsioonidest mitte ainult salvestamise, vaid ka andmete lugemise ajal. Funktsioonist saadud mdb_get pöördub otse sinna aadressi, kus andmebaas hoiab objekti baitpõhiseid representatsioone. Tegelikult saame millegi ORM-i, mis praktiliselt tasuta tagab väga kõrge andmete lugemiskiirus. Kogu selle lähenemise ilu juures tuleb siiski meeles pidada mitu seotud omadust.

1. Readonly tehingu puhul jääb viide struktuuri-väärtusele kehtivaks vaid seni, kuni tehing on suletud. Nagu eelnevalt mainitud, jäävad B-puu lehed, kus objekt asub, copy-on-write põhimõtte tõttu muutumatuks, kuni vähemalt üks tehing viitab neile. Samas, kui viimane nendega seotud tehing lõppeb, võivad lehed uuesti andmete jaoks kasutada. Kui on vajalik, et objektid ellu jääksid nende sünnitehingust, tuleb need siiski kopeerida.
2. Readwrite tehingu puhul on viide saadud struktuuri-väärtusele kehtiv vaid kuni esimese muudatuse (andmete kirjutamine või kustutamine) tegemiseni.
3. Hoolimata sellest, et struktuur NodeValue ei ole täieõiguslik, vaid kärbitud (vt alajaotist „Võtmete järjestamine välise võrdlejaga“), võib viidatud kaudu rahulikult selle väljadele juurde pääseda. Peamine on seda mitte dereferenseerida!
4. Struktuuri ei tohi mingil juhul muudetud viisil läbi saadud näitaja. Kõik muudatused peavad toimuma ainult meetodi kaudu mdb_put. Siiski, hoolimata soovist seda teha, ei õnnestu see, kuna selle struktuuri asukoha mälupiirkond on seotud readonly-režiimis.
5. Faili remapimine protsessi aadressiruumi, näiteks maksimaalse salvestusmahu suurendamiseks funktsiooni kaudu abil kehtetuks kõik entiteedid (kursused, tehingud, võtmed ja väärtused), mis on eelnevalt mootorilt saadud. Sellise sündmuste käigu arvesse võtmine koodis muudab selle oluliselt keerulisemaks. Kui aga virtuaalne mälu on teile tõeliselt oluline, siis võib see olla põhjus tutvuda kaugele arenenud forkiga keelab kõik tehingud ja nendega seotud entiteedid üldiselt ning näitajad loetud objektide puhul eraldi.

Lõpuks on veel üks omadus nii petlik, et selle olemuse avamine ei mahtu lihtsalt veel ühte punkti. B-puu peatükis tõin ma välja skeemi selle lehtede paigutusest mälus. Sealt järeldub, et serialiseeritud andmete puhvri alguse aadress võib olla täiesti meelevaldne. Seetõttu saadud näitaja nendele, mis on struktuuris MDB_val ja mis on muudetud struktuuri näitajaks, osutub üldiselt mittesobivaks. Samas mõne kiibi arhitektuurid (iOS-i puhul armv7) nõuavad, et mis tahes andmete aadress oleks sõna suuruse või teisisõnu, süsteemi bitisuse järgi (armv7 puhul on see 32 bitti). Teisisõnu, selline operatsioon nagu *(int *foo)0x800002 moodustab põgenemise ja viib surmaotsuseni EXC_ARM_DA_ALIGN. Sellise kurva saatuse vältimiseks on kaks viisi.

Esimene seisneb andmete eelnevas kopeerimises selgelt sobivasse struktuuri. Näiteks kajastub see järgmises kohandatud võrdlejas.

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

Alternatiivne tee on eelnevalt teavitada kompilaatorit, et võtme ja väärtuse struktuurid ei pruugi olla sobivad, kasutades atribuudina aligned(1). ARM-is on sama efekti võimalik saavutada kasutades atribuudina packed. Arvestades, et see toetab ka struktuuri mahukuse optimeerimist, näen seda meetodit eelistatavana, kuigi see kaasa toob kaasa andmete juurde pääsemise kulude suurenemise.

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

Vahemiku päringud

LMDB-s on ette nähtud kursori abstraktsioon, et itereerida üle rekordigruppide. Kuidas sellega töötada, vaatame juba tuttava kasutaja pilve metaandmete tabeli näitel.

Failide loetelu kuvamise raames on vaja leida kõik võtmed, millega on seotud tema alamfailid ja kaustad. Varasemates alajaotustes oleme võtnud võtmed sorteeritud NodeKey nii, et need oleksid esmalt järjestatud vanema katalooge identifikaatori järgi. Seega tehniliselt ülesanne kausta sisu saamisest tõlgendub kursori paigaldamiseks võtme prefiksiga rühma ülemisse piirini ning seejärel itereerida allapoole.

Ülemise piiri saab "otseselt" järjestikuse otsingu abil leida. Selleks paigaldatakse kursori algus kogu võtme nimekirja ja siis inkremeeritakse nii kaua, kuni selle all on vanema katalooge identifikaator. Selle lähenemisviisi on kaks ilmset puudust:

1. Otsingu lineaarne keerukus, kuigi on teada, et puudes ja eelkõige B-puudes saab seda teha logaritmilise ajaga.
2. Mitte asjata tõstetakse failist peamise mälusse kõik leheküljed, mis eelnevad otsitavale, mis on äärmiselt kulukas.

Õnneks on LMDB API-s ette nähtud efektiivne viisi kursori algseks paigutamiseks. Selleks tuleb moodustada selline võti, mille väärtus on kindlasti väiksem või võrdne võtmega, mis asub vahemiku ülemisel piiril. Näiteks rakendades ülaltoodud joonisel olevale nimekirjale, saame luua sellise võtme, mille väli parentId on võrdne 2, ja kõik ülejäänud on täidetud nullidega. Selline osaliselt täidetud võti edastatakse funktsiooni mdb_cursor_get operatsiooniga MDB_SET_RANGE.

NodeKey upperBoundSearchKey = {@n    .parentId = 2,@n    .type = 0,@n    .nameLength = 0@n};@nMDB_val value, key = serialize(upperBoundSearchKey);@nMDB_cursor *cursor;@nmdb_cursor_open(..., &cursor);@nmdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);

Kui võtmete grupi ülemine piir on leitud, itereerime selle üle seni, kuni kas kohtame kas võtme, mis on erinev parentId, või võtmed lõppevad täielikult.

do {@n    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);@n    // töötlemine...@n} while (MDB_NOTFOUND != rc && // tabeli lõpu kontroll@n         IsTargetKey(key));    // võtmete grupi lõpu kontroll

Mugav on see, et itereerimise raames mdb_cursor_get kaudu saame mitte ainult võti, vaid ka väärtus. Kui valikutingimuste täitmiseks on vaja kontrollida ka väärtuse osa väljade põhjal, siis on need täiesti kergesti kättesaadavad ilma täiendavate pingutusteta.

4.3. Suhete modelleerimine tabelite vahel

Siiani oleme suutnud käsitleda kõiki aspekte, mis puudutavad ühe tabeli andmebaasi projekteerimist ja kasutamist. Ütleks, et tabel on järjestatud kirje kogum, mis koosneb ühesugustest võti-väärtus paaridest. Kui kujutada võtme ristkülikuna ja sellega seotud väärtust paralleelpindana, saame andmebaasi visuaalse skeemi.

​

Kuid reaalelus harva õnnestub sedavõrd vähe, põhjustamata suuri probleeme. Tihti on andmebaasis vajalik, esiteks, mitu tabelit, ja teiseks, teostada valikuid muul viisil kui esmase võtme järgi. Selle viimase jaotise eesmärk on just nende loomine ja omavaheline sidumine.

Indekseerimise tabelid

Pilve rakenduses on jaotus 'Galerii'. Seal kuvatakse meedia sisu kogu pilves, sorteeritud kuupäeva järgi. Selle valiku optimaalseks teostamiseks on lisaks põhitaabelile vaja luua veel üks tabel uue võtme tüübiga. Sellest leiab välja loomise kuupäeva välja, mis on peamine sorteerimise kriteerium. Kuna uued võtmed viitavad neile samadele andmetele, mis on põhitaabelis, nimetatakse neid indekseerivateks. Alloleval pildil on need esitatud oranžiga.

Selleks, et ühes andmebaasis eristada erinevate tabelite võtmeid, on kõigile lisatud täiendav tehniline väli tableId. Kui teha see kõige olulisemaks sortimise aluseks, saavutame võtmete grupi esmalt tabelite kaupa ja seejärel oma reeglite järgi tabelite sees.

Indekseeriv võti viitab samadele andmetele nagu esmamine. Selle omaduse sirgjooneline teostamine esmase võtme väärtuse osa koopiaga seondudes on mitmest vaatenurgast ebatõhus.

1. Kohandatud ruumi kasutamise seisukohalt, arvestades, et metainformatsioon võib olla üsna rikkalik.
2. Töötamise efektiivsuse seisukohalt, kuna metainfot värskendades tuleb kahe võtme järgi kirjutada.
3. Koodi toetuse seisukohalt, kui me unustame ühe võtme andmed ajakohastada, saame me raskesti jälgitava andmete järjepidevuse vea andmehoidlas.

Edasi vaatame, kuidas neid puudusi likvideerida.

Seoste loomine tabelite vahel

Ajakohase tabeli seostamiseks põhitabletiga sobib hästi muster „võti väärtusena“. Nagu nimigi ütleb, toimib väärtusena indeksikande koopia primaarvõtme väärtusest. See lähenemine likvideerib kõik eelnevalt loetletud puudused, mis on seotud primaarandme väärtuse koopia salvestamisega. Ainsaks tasuks on see, et indeksivõtme järgi väärtuse saamiseks tuleb teha 2 päringut andmebaasi asemel 1. Saadud andmebaasi skeem näeb välja järgnev.

Ehkki teiseks tabelitevaheliste seadete korraldamise mustriks on „liigne võti“. Selle põhisisu seisneb võtme täiendavate atribuutide lisamises, mis ei ole vajalikud sorteerimiseks, vaid seotud võtme taastamiseks. Mail.ru pilve rakenduses on selle kasutamiseks reaalsed näited, kuid sügavale iOS raamistikku tungimise vältimiseks toon välja väljamõeldud, kuid rohkem arusaadava näite.

Pilve mobiiliklientides on leht, kus kuvatakse kõik failid ja kaustad, millele kasutaja on teistele inimestele ligipääsu andnud. Kuna selliseid faile on suhteliselt vähe, ja erinevat tüüpi sellega seotud spetsiifiline teave avalikkuse kohta on palju (kellele on antud juurdepääs, milliste õigustega jne), oleks ebatõhus koormata peamise tabeli väärtusosa selle teabega. Siiski, kui soovitakse selliseid faile ekraanil kuvada, tuleb neid mingil viisil siiski hoida. Loomulik lahendus on selle jaoks eraldi tabeli loomine. Alloleval skeemil on selle võtme eesliide „P“, samas kui kohatäitja „propname“ võib asendada konkreetsema väärtusega „avalik teave“.

Kõik unikaalsed metaandmed, mille jaoks uus tabel loodi, kantakse kirje value-osasse. Samas ei soovi dubleerida andmeid failide ja kaustade kohta, mis juba põhitoimingutesse talletatud on. Selle asemel lisatakse võtmesse "P" liialdatud andmed nagu "node ID" ja "timestamp". Just nende abil saab konstrueerida indeksivõtme, mille kaudu leida primaarvõti, mille kaudu lõpuks saada node'i metaandmed.

Kokkuvõte

Hindame LMDB rakenduse elluviimist positiivselt. Pärast selle kasutuselevõttu vähenes rakenduse hangumise arv 30%.

Tehttud töö tulemused said vastukaja ka väljaspool iOS meeskonda. Praegu on üks peamisi jaotisi „Failid“ Androidi rakenduses samuti üle läinud LMDB kasutamisele ja teised komponendid on samuti teel. C keel, milles key-value andmehoidla on rakendatud, on olnud suureks abiks, et esialgu teha rakenduslik sidumine selle ümber platvormideüleselt C++ keeles. Sujuv ühendamine saadud C++ raamatukoguga Objective-C ja Kotlin platvormikoodiga saavutas koodigeneratsiooni tööriist. Djinni Dropboxist, kuid see on juba hoopis teine lugu.

Allikas: habr.com