2019 metų rudenį Mail.ru Cloud iOS komandoje įvyko ilgai lauktas įvykis. Pagrindinė duomenų bazė, skirta nuolatiniam programos būsenos saugojimui, mobiliajame pasaulyje tapo gana egzotiška Žaibo atminties žemėlapių duomenų bazė (LMDB). Po pjūviu jūsų dėmesys kviečiamas į išsamią keturių dalių apžvalgą. Pirmiausia pakalbėkime apie tokio nebanalaus ir sunkaus pasirinkimo priežastis. Tada pereikime prie trijų banginių, kurie yra LMDB architektūros pagrindas: atminties susietų failų, B + medžio, kopijavimo ir rašymo metodo, skirto transakcijų ir kelių versijų įgyvendinimui. Galiausiai desertui – praktinė dalis. Jame apžvelgsime, kaip sukurti ir įdiegti bazinę schemą su keliomis lentelėmis, įskaitant indeksą, ant žemo lygio rakto vertės API.​

Turinys

1. Įgyvendinimo motyvacija
2. LMDB padėties nustatymas
3. Trys banginiai LMDB
   3.1. Banginis Nr.1. Su atmintimi susieti failai
   3.2. Banginis #2. B+-medis
   3.3. Banginis #3. kopijavimas-rašymas
4. Duomenų schemos kūrimas ant rakto vertės API
   4.1. Pagrindinės abstrakcijos
   4.2. Stalo modeliavimas
   4.3. Ryšių tarp lentelių modeliavimas

1. Įgyvendinimo motyvacija

Kartą per metus, 2015 m., pasirūpinome metrika, kaip dažnai atsilieka mūsų programos sąsaja. Mes ne tik tai padarėme. Sulaukiame vis daugiau priekaištų dėl to, kad kartais aplikacija nustoja reaguoti į vartotojo veiksmus: nespaudžiami mygtukai, neslenka sąrašai ir pan. Apie matavimų mechaniką pasakojo „AvitoTech“, todėl čia pateikiu tik skaičių tvarką.

Matavimo rezultatai mums tapo šaltu dušu. Paaiškėjo, kad problemų, kurias sukelia užšalimai, yra daug daugiau nei bet kurios kitos. Jei prieš suvokiant šį faktą pagrindinis techninis kokybės rodiklis buvo be gedimų, tai po fokusavimo pasislinko užšaldyti nemokamai.

Pastačiusi prietaisų skydelis su užšalimu ir išleidęs kiekybinis и kokybė išanalizavus jų priežastis, paaiškėjo pagrindinis priešas – sunki verslo logika, vykdoma pagrindinėje programos gijoje. Natūrali reakcija į šią gėdą buvo karštas noras įstumti ją į darbo srautus. Norėdami sistemingai išspręsti šią problemą, pasinaudojome kelių gijų architektūra, pagrįsta lengvais veikėjais. Jos adaptacijas skyriau iOS pasauliui du siūlai kolektyviniame Twitter ir straipsnis apie Habré. Kaip šios istorijos dalį noriu pabrėžti tuos sprendimo aspektus, kurie turėjo įtakos duomenų bazės pasirinkimui

Sistemos organizavimo veikėjo modelis daro prielaidą, kad daugiagija tampa antrąja jo esme. Jame esantys modelio objektai mėgsta kirsti gijų ribas. Ir tai daro ne kartais ir kai kur, o beveik nuolat ir visur.

Duomenų bazė yra vienas iš kertinių komponentų pateiktoje diagramoje. Pagrindinė jo užduotis yra įgyvendinti makrokomandą Bendrinama duomenų bazė. Jei verslo pasaulyje jis naudojamas duomenų sinchronizavimui tarp paslaugų organizuoti, tai veikėjo architektūros atveju duomenys tarp gijų. Taigi mums reikėjo tokios duomenų bazės, su kuria darbas kelių gijų aplinkoje nesukelia net minimalių sunkumų. Visų pirma, tai reiškia, kad iš jo gauti objektai turi būti bent jau saugūs siūlams ir idealiu atveju visai nekeičiami. Kaip žinote, pastarasis gali būti naudojamas vienu metu iš kelių gijų, nenaudojant jokių užraktų, o tai turi teigiamą poveikį veikimui.

Antras svarbus veiksnys, turėjęs įtakos duomenų bazės pasirinkimui, buvo mūsų debesies API. Jį įkvėpė git požiūris į sinchronizavimą. Kaip ir į jį mes siekėme Pirmoji neprisijungus API, kuri atrodo labiau nei tinkama debesų klientams. Buvo manoma, kad jie tik vieną kartą išpumpuos visą debesies būseną, o tada sinchronizavimas daugeliu atvejų įvyks per nuolatinius pakeitimus. Deja, tokia galimybė dar tik teorinėje zonoje, o praktiškai klientai taip ir neišmoko dirbti su pleistrais. Tam yra keletas objektyvių priežasčių, kurias, norėdami neužvilkinti įžangos, paliksime skliausteliuose. Dabar daug įdomesni yra pamokantys pamokos rezultatai apie tai, kas nutinka, kai API pasakė „A“, o jos vartotojas nepasakė „B“.

Taigi, jei įsivaizduojate git, kuris, vykdydamas traukos komandą, užuot taikęs pataisas vietiniam momentiniam vaizdui, lygina visą savo būseną su pilno serverio būsena, turėsite gana tikslią sinchronizavimo idėją. atsiranda debesų programose. Nesunku atspėti, kad jo įgyvendinimui atmintyje reikia skirti du DOM medžius su metainformacija apie visus serverio ir vietinius failus. Pasirodo, jei vartotojas debesyje saugo 500 tūkstančių failų, tai norint jį sinchronizuoti, reikia iš naujo sukurti ir sunaikinti du medžius su 1 milijonu mazgų. Bet kiekvienas mazgas yra agregatas, kuriame yra subobjektų grafikas. Atsižvelgiant į tai, buvo tikimasi profiliavimo rezultatų. Paaiškėjo, kad net neatsižvelgiant į sujungimo algoritmą, pati daugybės mažų objektų sukūrimo ir sunaikinimo procedūra kainuoja nemažą centą. Padėtį apsunkina tai, kad pagrindinė sinchronizavimo operacija yra įtraukta į didelį skaičių. vartotojo scenarijų. Dėl to fiksuojame antrą svarbų kriterijų renkantis duomenų bazę – galimybę įgyvendinti CRUD operacijas be dinaminio objektų paskirstymo.

Kiti reikalavimai yra labiau tradiciniai, o visas jų sąrašas yra toks.

1. Siūlų sauga.
2. Daugiafunkcis apdorojimas. Padiktuota dėl noro naudoti tą patį duomenų bazės egzempliorių, kad būtų galima sinchronizuoti būseną ne tik tarp gijų, bet ir tarp pagrindinės programos bei iOS plėtinių.
3. Galimybė vaizduoti saugomus objektus kaip nekintamus objektus
4. CRUD operacijose trūksta dinamiškų paskirstymų.
5. Pagrindinės nuosavybės sandorių palaikymas RŪGŠTISRaktažodžiai: atomiškumas, nuoseklumas, izoliacija ir patikimumas.
6. Greitis populiariausiuose atvejuose.

Atsižvelgiant į šį reikalavimų rinkinį, SQLite buvo ir vis dar yra geras pasirinkimas. Tačiau tyrinėdamas alternatyvas aptikau knygą „Pradžia su LevelDB“. Jai vadovaujant buvo parašytas etalonas, kuriame lyginamas darbo greitis su skirtingomis duomenų bazėmis realiuose debesų scenarijuose. Rezultatas pranoko drąsiausius lūkesčius. Populiariausiais atvejais - užvedus žymeklį ant surūšiuoto visų failų sąrašo ir surūšiuoto visų tam tikro katalogo failų sąrašo - LMDB pasirodė 10 kartų greitesnis nei SQLite. Pasirinkimas tapo akivaizdus.

2. LMDB pozicionavimas

LMDB yra biblioteka, labai maža (tik 10K eilučių), kuri realizuoja žemiausią pagrindinį duomenų bazių sluoksnį – saugyklą.

Aukščiau pateikta diagrama rodo, kad LMDB lyginimas su SQLite, kuris įgyvendina dar aukštesnius lygius, paprastai nėra teisingesnis nei SQLite su pagrindiniais duomenimis. Teisingiau būtų nurodyti tuos pačius saugojimo variklius kaip lygiaverčius konkurentus – BerkeleyDB, LevelDB, Sophia, RocksDB ir tt Yra netgi tokių patobulinimų, kai LMDB veikia kaip SQLite saugojimo variklio komponentas. Pirmasis toks eksperimentas 2012 m išleista autorius LMDB Howardas Chu. rezultatai pasirodė toks intriguojantis, kad jo iniciatyvą perėmė OSS entuziastai ir surado jos tąsą prieš LumoSQL. 2020 m. sausio mėn. šio projekto autorius yra Den Shearer pateikta tai „LinuxConfAu“.

Pagrindinis LMDB panaudojimas yra programų duomenų bazių variklis. Biblioteka už savo išvaizdą skolinga kūrėjams OpenLDAP, kurie buvo labai nepatenkinti BerkeleyDB kaip savo projekto pagrindu. Stūmimasis nuo kuklios bibliotekos btree, Howardas Chu sugebėjo sukurti vieną populiariausių mūsų laikų alternatyvų. Šiai istorijai, kaip ir LMDB vidinei struktūrai, jis skyrė savo labai šaunų reportažą „Žaibo atminties žemėlapių duomenų bazė“. Leonidas Jurjevas (dar žinomas kaip yleo) iš Positive Technologies savo kalboje Highload 2015 „LMDB variklis yra ypatingas čempionas“. Jame jis kalba apie LMDB panašios ReOpenLDAP diegimo užduoties kontekste, o LevelDB jau sulaukė lyginamosios kritikos. Įdiegę „Positive Technologies“ netgi gavo aktyviai besivystančią šakę MDBX su labai skaniomis funkcijomis, optimizavimu ir klaidų pataisymai.

LMDB taip pat dažnai naudojamas kaip saugykla. Pavyzdžiui, „Mozilla Firefox“ naršyklė pasirinko jis tinka daugeliui poreikių ir, pradedant nuo 9 versijos, Xcode pageidaujama savo SQLite indeksams saugoti.

Variklis taip pat įsitraukė į mobiliųjų telefonų kūrimo pasaulį. Gali būti jo naudojimo pėdsakų rasti „iOS“ kliente, skirtame „Telegram“. „LinkedIn“ žengė dar vieną žingsnį toliau ir pasirinko LMDB kaip numatytąją saugyklą savo vietinei duomenų talpyklos sistemai „Rocket Data“, apie kurią pasakojo straipsnyje 2016 m.

LMDB sėkmingai kovoja dėl vietos saulėje nišoje, kurią BerkeleyDB paliko po perėjimo valdant Oracle. Biblioteka mėgstama dėl savo greičio ir patikimumo, net palyginus su savo rūšimi. Kaip žinia, nemokamų pietų nebūna ir noriu pabrėžti kompromisą, su kuriuo teks susidurti renkantis tarp LMDB ir SQLite. Aukščiau pateikta diagrama aiškiai parodo, kaip pasiekiamas padidintas greitis. Pirma, mes nemokame už papildomus abstrakcijos sluoksnius ant disko saugyklos. Žinoma, geroje architektūroje be jų vis tiek neapsieisite ir jie neišvengiamai atsiras programos kode, tačiau jie bus daug plonesni. Jie neturės funkcijų, kurių nereikia konkrečiai programai, pavyzdžiui, užklausų SQL kalba palaikymas. Antra, tampa įmanoma optimaliai įgyvendinti programos operacijų susiejimą su užklausomis į disko saugyklą. Jei SQLite jo darbe kyla iš vidutinių vidutinės programos poreikių, tada jūs, kaip programų kūrėjas, puikiai žinote pagrindinius įkėlimo scenarijus. Kad sprendimas būtų produktyvesnis, turėsite sumokėti padidintą kainą ir už pradinio sprendimo kūrimą, ir už tolesnį jo palaikymą.

3. Trys banginiai LMDB

Pažvelgus į LMDB iš paukščio skrydžio, metas pasigilinti. Kiti trys skyriai bus skirti pagrindinių banginių, ant kurių remiasi saugojimo architektūra, analizei:

1. Atminties susiejimo failai kaip darbo su disku ir vidinių duomenų struktūrų sinchronizavimo mechanizmas.
2. B+-medis kaip saugomų duomenų struktūros organizacija.
3. Kopijavimas rašant kaip būdas suteikti ACID operacijų ypatybes ir kelių versijų kūrimą.

3.1. Banginis Nr.1. Su atmintimi susieti failai

Su atmintimi susieti failai yra toks svarbus architektūrinis elementas, kad jie netgi atsiranda saugyklos pavadinime. Talpyklos ir prieigos prie saugomos informacijos sinchronizavimo problemos visiškai priklauso nuo operacinės sistemos. LMDB savyje nėra talpyklos. Tai yra sąmoningas autoriaus sprendimas, nes duomenų skaitymas tiesiai iš susietų failų leidžia sumažinti variklio diegimo kampus. Žemiau pateikiamas toli gražu ne visas kai kurių iš jų sąrašas.

1. Duomenų nuoseklumo palaikymas saugykloje dirbant su jais iš kelių procesų tampa operacinės sistemos pareiga. Kitame skyriuje šis mechanikas aptariamas išsamiai ir su nuotraukomis.
2. Talpyklų nebuvimas visiškai atleidžia LMDB nuo pridėtinių išlaidų, susijusių su dinaminiu paskirstymu. Duomenų skaitymas praktiškai reiškia žymeklio nustatymą į teisingą adresą virtualioje atmintyje ir nieko daugiau. Skamba kaip fantazija, tačiau saugyklos šaltinyje visi calloc iškvietimai yra sutelkti saugyklos konfigūravimo funkcijoje.
3. Talpyklų nebuvimas taip pat reiškia, kad nėra užraktų, susijusių su sinchronizavimu, kad būtų galima juos pasiekti. Skaitytojai, kurių atsitiktinis skaičius gali egzistuoti tuo pačiu metu, pakeliui į duomenis nesusiduria su vienu mutexu. Dėl šios priežasties skaitymo greitis turi idealų tiesinį mastelį, atsižvelgiant į procesorių skaičių. LMDB sinchronizuojamos tik modifikavimo operacijos. Vienu metu gali būti tik vienas rašytojas.
4. Mažiausia talpyklos ir sinchronizavimo logika išsaugo kodą nuo itin sudėtingų klaidų, susijusių su darbu kelių gijų aplinkoje. Usenix OSDI 2014 konferencijoje buvo atlikti du įdomūs duomenų bazių tyrimai: „Visos failų sistemos nėra vienodos: dėl gedimų nuoseklių programų kūrimo sudėtingumo“ и Duomenų bazių kankinimas siekiant linksmybių ir pelno. Iš jų galite gauti informacijos ir apie precedento neturintį LMDB patikimumą, ir beveik nepriekaištingą operacijų ACID savybių įgyvendinimą, kuris jį pranoksta tame pačiame SQLite.
5. LMDB minimalizmas leidžia mašininio kodo atvaizdavimą visiškai patalpinti į procesoriaus L1 talpyklą su gautomis greičio charakteristikomis.

Deja, „iOS“ atmintyje susieti failai nėra tokie rožiniai, kaip norėtume. Norint sąmoningiau kalbėti apie su jais susijusius trūkumus, būtina prisiminti bendruosius šio mechanizmo diegimo operacinėse sistemose principus.

Bendra informacija apie atmintyje susietus failus

Su kiekviena vykdoma programa operacinė sistema susieja objektą, vadinamą procesu. Kiekvienam procesui priskiriamas gretimas adresų diapazonas, kuriame yra viskas, ko reikia darbui. Žemiausiuose adresuose yra skyriai su kodu ir užkoduotais duomenimis bei ištekliais. Toliau ateina vis didėjantis dinaminės adresų erdvės blokas, mums gerai žinomas kaip krūva. Jame yra objektų, kurie atsiranda programos veikimo metu, adresai. Viršuje yra programos krūvos naudojama atminties sritis. Jis arba auga, arba mažėja, kitaip tariant, jo dydis taip pat turi dinamišką pobūdį. Kad krūva ir krūva nestumtų ir netrukdytų vienas kitam, jie atskiriami skirtinguose adresų erdvės galuose.Tarp dviejų dinaminių sekcijų viršuje ir apačioje yra skylė. Šioje vidurinėje dalyje esančius adresus operacinė sistema naudoja susieti su įvairių objektų procesu. Visų pirma, jis gali susieti tam tikrą nuolatinį adresų rinkinį su failu diske. Toks failas vadinamas atminties susietu failu.​

Procesui skirta adresų erdvė yra didžiulė. Teoriškai adresų skaičių riboja tik rodyklės dydis, kurį lemia sistemos bitumas. Jei jam būtų priskirta fizinė atmintis „1-in-1“, pirmasis procesas suvalgytų visą RAM ir nekiltų kalbos apie bet kokį daugiafunkcinį darbą.

Tačiau iš patirties žinome, kad šiuolaikinės operacinės sistemos vienu metu gali vykdyti tiek procesų, kiek norite. Tai įmanoma dėl to, kad jie daug atminties skiria procesams tik popieriuje, tačiau realiai į pagrindinę fizinę atmintį įkelia tik tą dalį, kuri yra paklausi čia ir dabar. Todėl su procesu susijusi atmintis vadinama virtualia.

Operacinė sistema suskirsto virtualią ir fizinę atmintį į tam tikro dydžio puslapius. Kai tik tam tikras virtualios atminties puslapis yra paklausus, operacinė sistema įkelia jį į fizinę atmintį ir įrašo jų atitikimą specialioje lentelėje. Jei laisvų vietų nėra, vienas iš anksčiau įkeltų puslapių nukopijuojamas į diską, o jo vietą užima prašomas. Ši procedūra, prie kurios grįšime netrukus, vadinama keitimu. Toliau pateiktame paveikslėlyje parodytas aprašytas procesas. Jame buvo įkeltas puslapis A su adresu 0 ir patalpintas į pagrindinį atminties puslapį su adresu 4. Šis faktas atsispindėjo korespondencijos lentelėje 0 langelyje.​

Su atmintimi susietais failais istorija lygiai tokia pati. Logiškai mąstant, jie tariamai nuolat ir visiškai patalpinami virtualioje adresų erdvėje. Tačiau jie patenka į fizinę atmintį puslapis po puslapio ir tik pagal poreikį. Tokių puslapių modifikavimas sinchronizuojamas su diske esančiu failu. Taigi, galite atlikti failo I / O tiesiog dirbdami su baitais atmintyje - visus pakeitimus operacinės sistemos branduolys automatiškai perkels į pradinį failą.​
​
Toliau pateiktame paveikslėlyje parodyta, kaip LMDB sinchronizuoja savo būseną, kai dirba su skirtingų procesų duomenų baze. Skirtingų procesų virtualiąją atmintį susiedami į tą patį failą, mes de facto įpareigojame operacinę sistemą pereinamuoju būdu sinchronizuoti tam tikrus jų adresų erdvių blokus tarpusavyje, o būtent tai ir atrodo LMDB.​
​

Svarbus niuansas yra tai, kad LMDB pagal nutylėjimą modifikuoja duomenų failą per rašymo sistemos iškvietimo mechanizmą, o pats failas rodomas tik skaitymo režimu. Šis metodas turi dvi svarbias pasekmes.

Pirmoji pasekmė būdinga visoms operacinėms sistemoms. Jo esmė – papildyti apsaugą nuo netyčinio duomenų bazės sugadinimo dėl neteisingo kodo. Kaip žinote, proceso vykdomosios instrukcijos gali laisvai pasiekti duomenis iš bet kurios adresų erdvės vietos. Tuo pačiu metu, kaip ką tik prisiminėme, failo rodymas skaitymo ir rašymo režimu reiškia, kad bet kokia instrukcija taip pat gali jį papildomai modifikuoti. Jei ji tai padarys per klaidą, bandydama, pavyzdžiui, iš tikrųjų perrašyti masyvo elementą neegzistuojančiame indekse, tokiu būdu ji gali netyčia pakeisti šiuo adresu susietą failą, o tai sugadins duomenų bazę. Jei failas rodomas tik skaitymo režimu, bandymas pakeisti jį atitinkančią adreso erdvę sukels programos gedimą su signalu SIGSEGV, ir failas išliks nepakitęs.

Antroji pasekmė jau būdinga iOS. Nei autorius, nei kiti šaltiniai to aiškiai nemini, tačiau be jo LMDB būtų netinkama veikti šioje mobiliojoje operacinėje sistemoje. Kitas skyrius skirtas jo svarstymui.

Atminties susietų failų specifika iOS

2018 m. WWDC buvo puikus pranešimas iOS Memory Deep Dive. Jame nurodoma, kad iOS visi puslapiai, esantys fizinėje atmintyje, priklauso vienam iš 3 tipų: purvini, suspausti ir švarūs.

Švari atmintis yra puslapių rinkinys, kurį galima saugiai pakeisti iš fizinės atminties. Juose esantys duomenys gali būti iš naujo įkelti iš pirminių šaltinių, jei reikia. Į šią kategoriją patenka tik skaitomi atmintyje susieti failai. „iOS“ nebijo bet kuriuo metu iš atminties iškelti puslapius, susietus su failu, nes garantuojama, kad jie bus sinchronizuoti su diske esančiu failu.
​
Visi pakeisti puslapiai patenka į nešvarią atmintį, nesvarbu, kur jie buvo iš pradžių. Taip pat bus klasifikuojami atmintyje susieti failai, modifikuoti įrašant į su jais susietą virtualiąją atmintį. LMDB atidarymas su vėliava MDB_WRITEMAP, atlikę jo pakeitimus, tuo įsitikinsite patys

Kai tik programa pradeda užimti per daug fizinės atminties, „iOS“ suspaudžia nešvarius puslapius. Atminties, kurią užima nešvarūs ir suspausti puslapiai, kolekcija yra vadinamasis programos atminties pėdsakas. Kai jis pasiekia tam tikrą slenkstinę vertę, OOM žudikų sistemos demonas ateina po proceso ir priverstinai jį nutraukia. Tai iOS ypatumas, lyginant su stalinių kompiuterių operacinėmis sistemomis. Priešingai, sumažinti atminties kiekį keičiant puslapius iš fizinės atminties į diską iOS nenumatoma, galima tik spėlioti priežastis. Galbūt intensyvaus puslapių perkėlimo į diską ir atgal procedūra yra per daug energijos sunaudojanti mobiliesiems įrenginiams, arba iOS taupo SSD diskų ląstelių perrašymo išteklius, o gal dizaineriai nebuvo patenkinti bendru sistemos veikimu, kur viskas yra nuolat keičiamas. Kad ir kaip būtų, faktas išlieka.

Gera žinia, jau minėta anksčiau, yra ta, kad LMDB pagal numatytuosius nustatymus nenaudoja mmap mechanizmo failams atnaujinti. Iš to išplaukia, kad pateiktus duomenis iOS klasifikuoja kaip švarią atmintį ir jie neprisideda prie atminties ploto. Tai galima patikrinti naudojant Xcode įrankį, vadinamą VM Tracker. Žemiau esančioje ekrano kopijoje parodyta virtualios atminties būsena iOS Cloud programos veikimo metu. Pradžioje jame buvo inicijuoti 2 LMDB egzemplioriai. Pirmajam buvo leista susieti savo failą su 1GiB virtualios atminties, antrajam – 512MiB. Nepaisant to, kad abi saugyklos užima tam tikrą nuolatinės atminties kiekį, nė viena iš jų neprisideda prie nešvaraus dydžio.

Dabar atėjo laikas blogoms naujienoms. Dėl apsikeitimo mechanizmo 64 bitų darbalaukio operacinėse sistemose kiekvienas procesas gali užimti tiek virtualaus adreso vietos, kiek laisvos vietos standžiajame diske leidžia galimas apsikeitimas. Swap pakeitimas suspaudimu iOS drastiškai sumažina teorinį maksimumą. Dabar visi gyvi procesai turi tilpti į pagrindinę (skaitomąją RAM) atmintį, o visi, kurie netelpa, yra priverstinai nutraukiami. Jis paminėtas kaip aukščiau ataskaitair in oficialius dokumentus. Dėl to „iOS“ labai apriboja atminties kiekį, kurį galima paskirstyti per mmap. Čia čia galite pažvelgti į empirines atminties, kurią galima skirti įvairiuose įrenginiuose naudojant šį sistemos skambutį, apribojimus. Šiuolaikiškiausiuose išmaniųjų telefonų modeliuose „iOS“ tapo dosni 2 gigabaitais, o geriausiose „iPad“ versijose – 4. Praktiškai, žinoma, tenka orientuotis į jauniausius palaikomus įrenginių modelius, kur viskas labai liūdna. Dar blogiau, pažvelgę ​​į programos atminties būseną VM Tracker, pamatysite, kad LMDB toli gražu nėra vienintelė, kuri reikalauja atminties susietos atminties. Gerus gabalus suvalgo sistemos skirstytuvai, išteklių failai, vaizdų sistemos ir kiti mažesni plėšrūnai.

Atlikę eksperimentus debesyje, priėjome prie tokių kompromisinių LMDB skirtų atminties reikšmių: 384 megabaitai 32 bitų įrenginiams ir 768 megabaitai 64 bitų įrenginiams. Išnaudojus šį kiekį, visos modifikavimo operacijos pradedamos užbaigti su kodu MDB_MAP_FULL. Stebėdami tokias klaidas pastebime, tačiau jos yra pakankamai mažos, kad būtų nepaisoma šiame etape.

Neakivaizdi perteklinės atminties sunaudojimo saugykloje priežastis gali būti ilgalaikės operacijos. Norėdami suprasti, kaip šie du reiškiniai yra susiję, padės mums apsvarstyti likusius du LMDB banginius.

3.2. Banginis #2. B+-medis

Norint emuliuoti lenteles, esančias raktų verčių saugyklos viršuje, jos API turi būti atliekamos šios operacijos:

1. Naujo elemento įterpimas.
2. Ieškokite elemento naudodami nurodytą raktą.
3. Elemento ištrynimas.
4. Pakartokite raktinius intervalus jų rūšiavimo tvarka.

Paprasčiausia duomenų struktūra, kuri gali lengvai įgyvendinti visas keturias operacijas, yra dvejetainis paieškos medis. Kiekvienas jo mazgas yra raktas, padalinantis visą antrinių raktų poaibį į du pomedžius. Kairėje yra tie, kurie yra mažesni už tėvą, o dešinėje - tie, kurie yra didesni. Užsakytą raktų rinkinį galima gauti per vieną iš klasikinių medžių perėjimų

Dvejetainiai medžiai turi du esminius trūkumus, dėl kurių jie negali būti veiksmingi kaip disko duomenų struktūra. Pirma, jų pusiausvyros laipsnis yra nenuspėjamas. Yra didelė rizika gauti medžių, kuriuose skirtingų šakų aukštis gali labai skirtis, o tai žymiai pablogina paieškos algoritminį sudėtingumą, palyginti su tuo, ko tikimasi. Antra, dėl kryžminių nuorodų tarp mazgų gausa dvejetainiams medžiams atima lokalumą atmintyje.Arti mazgai (kalbant apie ryšius tarp jų) gali būti išdėstyti visiškai skirtinguose virtualiosios atminties puslapiuose. Dėl šios priežasties net paprastam kelių gretimų medžio mazgų perėjimui gali tekti aplankyti panašų skaičių puslapių. Tai yra problema net tada, kai kalbame apie dvejetainių medžių, kaip atmintyje esančios duomenų struktūros, efektyvumą, nes nuolat sukti puslapius procesoriaus talpykloje nėra pigu. Kai reikia dažnai pakelti su mazgais susijusius puslapius iš disko, viskas pasidaro labai blogai. apgailėtinas.

B-medžiai, būdami dvejetainių medžių evoliucija, išsprendžia ankstesnėje pastraipoje nurodytas problemas. Pirma, jie susibalansuoja. Antra, kiekvienas jų mazgas padalija vaikų raktų rinkinį ne į 2, o į M eilės poaibius, o skaičius M gali būti gana didelis, kelių šimtų ar net tūkstančių eilės.

Taigi:

1. Kiekvienas mazgas turi daug jau užsakytų raktų, o medžiai yra labai žemi.
2. Medis atmintyje įgyja vietos savybę, nes artimos vertės raktai natūraliai yra vienas šalia kito viename ar gretimuose mazguose.
3. Sumažina tranzitinių mazgų skaičių, kai paieškos operacijos metu nusileidžiate medžiu.
4. Sumažina diapazono užklausų nuskaitomų tikslinių mazgų skaičių, nes kiekviename iš jų jau yra daug užsakytų raktų.

Duomenims saugoti LMDB naudoja B-medžio variantą, vadinamą B+ medžiu. Aukščiau pateiktoje diagramoje parodyti trys joje esančių mazgų tipai:

1. Viršuje yra šaknis. Tai ne daugiau kaip duomenų bazės saugykloje koncepcija. Viename LMDB egzemplioriuje galite sukurti kelias duomenų bazes, kurios bendrina susietą virtualią adresų erdvę. Kiekvienas iš jų prasideda nuo savo šaknų.
2. Žemiausiame lygyje yra lapai (lapas). Būtent juose ir tik jose yra duomenų bazėje saugomos raktų ir reikšmių poros. Beje, tai B+-medžių ypatumas. Jei normalus B medis saugo verčių dalis visų lygių mazguose, tai B+ variacija yra tik žemiausiame. Ištaisę šį faktą, toliau LMDB naudojamą medžio potipį vadinsime tiesiog B medžiu.
3. Tarp šaknies ir lapų yra 0 ar daugiau techninių lygių su navigacijos (šakos) mazgais. Jų užduotis yra padalinti surūšiuotą raktų rinkinį tarp lapų.

Fiziškai mazgai yra iš anksto nustatyto ilgio atminties blokai. Jų dydis yra kartotinis operacinės sistemos atminties puslapių dydžio, apie kurį kalbėjome aukščiau. Mazgo struktūra parodyta žemiau. Antraštėje yra metainformacija, iš kurių akivaizdžiausia, pavyzdžiui, yra kontrolinė suma. Toliau pateikiama informacija apie poslinkius, išilgai kurių yra langeliai su duomenimis. Duomenų vaidmuo gali būti arba raktai, jei kalbame apie naršymo mazgus, arba ištisos raktų-reikšmių poros lapų atveju.Daugiau apie puslapių struktūrą galite paskaityti darbe „Aukšto našumo pagrindinės vertės parduotuvių įvertinimas“.

Išnagrinėję vidinį puslapio mazgų turinį, toliau supaprastintu būdu pavaizduosime LMDB B medį tokia forma.

Puslapiai su mazgais nuosekliai išdėstomi diske. Puslapiai su didesniu skaičiumi yra failo pabaigoje. Vadinamajame meta puslapyje (meta puslapyje) yra informacija apie poslinkius, pagal kuriuos galima rasti visų medžių šaknis. Kai failas atidaromas, LMDB nuskaito failą puslapis po puslapio nuo pabaigos iki pradžios, ieškodama tinkamo meta puslapio ir per jį suranda esamas duomenų bazes.​

Dabar, turėdami idėją apie loginę ir fizinę duomenų organizavimo struktūrą, galime pradėti svarstyti trečiąjį LMDB banginį. Būtent su jo pagalba visi saugojimo pakeitimai atliekami atliekant operaciją ir atskirai vienas nuo kito, suteikiant duomenų bazei kaip visumai ir kelių versijų savybę.

3.3. Banginis #3. kopijavimas-rašymas

Kai kurios B medžio operacijos apima daugybę pakeitimų jo mazguose. Vienas iš pavyzdžių yra naujo rakto pridėjimas prie mazgo, kuris jau pasiekė didžiausią talpą. Šiuo atveju būtina, pirma, padalinti mazgą į dvi dalis ir, antra, pridėti nuorodą į naują atskirtą antrinį mazgą jo pirminėje dalyje. Ši procedūra gali būti labai pavojinga. Jei dėl kokios nors priežasties (avarijos, elektros energijos tiekimo nutraukimo ir pan.) įvyksta tik dalis serijos pakeitimų, medis išliks nenuoseklios būsenos.

Vienas tradicinių sprendimų, kaip padaryti, kad duomenų bazė būtų atspari gedimams, yra pridėti papildomą diske pagrįstą duomenų struktūrą – operacijų žurnalą, dar žinomą kaip įrašymo į priekį žurnalas (WAL), šalia B medžio. Tai failas, kurio gale, griežtai prieš paties B medžio modifikaciją, rašoma numatyta operacija. Taigi, jei savidiagnostikos metu aptinkamas duomenų sugadinimas, duomenų bazė ieško žurnalo, kad išsivalytų.

LMDB pasirinko kitą metodą kaip savo gedimų tolerancijos mechanizmą, kuris vadinamas kopijavimu rašant. Jo esmė yra ta, kad užuot atnaujinusi esamo puslapio duomenis, jis pirmiausia nukopijuoja juos ir atlieka visus jau esančius pakeitimus.​

Be to, norint, kad atnaujinti duomenys būtų prieinami, būtina pakeisti nuorodą į mazgą, kuris pradiniame mazge tapo atnaujintas jo atžvilgiu. Kadangi jį taip pat reikia modifikuoti, jis taip pat yra iš anksto nukopijuotas. Procesas tęsiasi rekursyviai iki pat šaknies. Duomenys meta puslapyje keičiasi paskutiniai.​​

Jei procesas staiga užstringa atnaujinimo procedūros metu, tada naujas meta puslapis nebus sukurtas, arba jis nebus įrašytas į diską iki galo, o jo kontrolinė suma bus neteisinga. Bet kuriuo iš šių dviejų atvejų nauji puslapiai bus nepasiekiami, o senieji nebus paveikti. Tai pašalina poreikį LMDB rašyti į priekį žurnalą, kad būtų išlaikytas duomenų nuoseklumas. De facto, aukščiau aprašyta duomenų saugojimo diske struktūra kartu atlieka savo funkcijas. Aiškaus operacijų žurnalo nebuvimas yra viena iš LMDB funkcijų, užtikrinančių didelį duomenų nuskaitymo greitį.​

Gauta konstrukcija, vadinama tik papildomu B medžiu, natūraliai užtikrina operacijų izoliavimą ir kelių versijų sudarymą. LMDB kiekviena atidaryta operacija turi su ja susietą naujausią medžio šaknį. Kol operacija nebaigta, su ja susieti medžio puslapiai niekada nebus keičiami arba pakartotinai naudojami naujoms duomenų versijoms. Taigi galite dirbti tiek laiko, kiek norite tiksliai su duomenų rinkiniu, kuris buvo aktualus operacijos atidarymo laikas, net jei saugykla šiuo metu ir toliau aktyviai atnaujinama. Tai yra daugiaversijų kūrimo esmė, todėl LMDB yra idealus duomenų šaltinis mūsų mylimajam UICollectionView. Atidarius operaciją, nereikia didinti programos atminties, skubotai pumpuojant esamus duomenis į kokią nors atminties struktūrą, bijant likti be nieko. Ši savybė išskiria LMDB nuo tos pačios SQLite, kuri negali pasigirti tokia visiška izoliacija. Pastarojoje atidarius dvi operacijas ir vienoje iš jų ištrynus tam tikrą įrašą, to paties įrašo nebegalima gauti per antrąjį likusią.

Kita monetos pusė yra potencialiai žymiai didesnis virtualios atminties suvartojimas. Skaidrėje parodyta, kaip atrodys duomenų bazės struktūra, jei ji bus modifikuota vienu metu su 3 atviromis skaitymo operacijomis, žiūrint į skirtingas duomenų bazės versijas. Kadangi LMDB negali pakartotinai naudoti mazgų, kurie pasiekiami iš šaknų, susijusių su faktinėmis operacijomis, saugykla neturi kito pasirinkimo, kaip tik priskirti atmintyje kitą ketvirtą šaknį ir dar kartą klonuoti po ja pakeistus puslapius.

Čia nebus nereikalinga prisiminti skyrių apie atmintyje susietus failus. Atrodo, kad papildomas virtualios atminties suvartojimas neturėtų mūsų labai varginti, nes jis neprisideda prie programos atminties ploto. Tačiau tuo pačiu buvo pastebėta, kad iOS yra labai šykštus ją skirstydamas, o 1 terabaito LMDB regiono serveryje ar darbalaukyje iš meistro peties negalime pateikti ir apie šią funkciją visiškai negalvoti. Jei įmanoma, turėtumėte stengtis, kad sandorių trukmė būtų kuo trumpesnė.

4. Duomenų schemos kūrimas ant rakto vertės API

Pradėkime analizuoti API žiūrėdami į pagrindines LMDB teikiamas abstrakcijas: aplinką ir duomenų bazes, raktus ir reikšmes, operacijas ir žymeklius.

Pastaba apie kodų sąrašus

Visos funkcijos LMDB viešoje API grąžina savo darbo rezultatą klaidos kodo pavidalu, tačiau visuose tolesniuose sąrašuose jo tikrinimas glaustumo dėlei praleistas.Praktiškai sąveikaudami su saugykla naudojome savo kodą. šakutė C++ įvyniokliai lmdbxx, kuriame klaidos materializuojasi kaip C++ išimtis.

Kaip greičiausią būdą prijungti LMDB prie iOS arba MacOS projekto, siūlau savo CocoaPod POSLMDB.

4.1. Pagrindinės abstrakcijos

Aplinka

Struktūra MDB_env is yra LMDB vidinės būsenos saugykla. Priešdėlinių funkcijų šeima mdb_env leidžia konfigūruoti kai kurias jo savybes. Paprasčiausiu atveju variklio inicijavimas atrodo taip.

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“ programoje pakeitėme tik dviejų parametrų numatytąsias reikšmes.

Pirmasis yra virtualios adresų erdvės, su kuria susietas saugojimo failas, dydis. Deja, net ir tame pačiame įrenginyje konkreti vertė gali labai skirtis priklausomai nuo paleidimo. Norėdami atsižvelgti į šią „iOS“ funkciją, didžiausią saugyklos kiekį pasirenkame dinamiškai. Pradedant nuo tam tikros vertės, ji paeiliui mažėja iki funkcijos mdb_env_open negrąžins kito rezultato, išskyrus ENOMEM. Teoriškai yra priešingas būdas - pirmiausia paskirstykite varikliui mažiausiai atminties, o tada, kai bus gautos klaidos MDB_MAP_FULL, padidinkite jį. Tačiau tai daug spygliuotesnė. Priežastis ta, kad atminties pertvarkymo naudojant funkciją procedūra mdb_env_set_map_size panaikina visus anksčiau iš variklio gautus objektus (žymeklius, operacijas, raktus ir reikšmes). Atsižvelgus į tokį įvykių posūkį kode, jis labai apsunkins. Jei vis dėlto virtualioji atmintis jums labai brangi, tai gali būti priežastis pažvelgti į šakę, kuri nuėjo toli į priekį. MDBX, kur tarp deklaruojamų ypatybių yra „automatinis duomenų bazės dydžio reguliavimas skrydžio metu“.

Antrasis parametras, kurio numatytoji reikšmė mums netiko, reguliuoja siūlų saugos užtikrinimo mechaniką. Deja, bent jau „iOS 10“ yra problemų su gijų vietinės saugyklos palaikymu. Dėl šios priežasties aukščiau pateiktame pavyzdyje saugykla atidaroma su vėliavėle MDB_NOTLS. Be to, taip pat reikėjo šakutė C++ įvynioklis lmdbxxiškirpti kintamuosius su ir šiame atribute.

Duomenų bazės

Duomenų bazė yra atskiras B medžio, apie kurį kalbėjome aukščiau, pavyzdys. Jo atidarymas vyksta operacijos metu, o tai iš pradžių gali atrodyti šiek tiek keista.

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

Iš tiesų, operacija LMDB yra saugojimo objektas, o ne konkreti duomenų bazė. Ši koncepcija leidžia atlikti atomines operacijas su skirtingose ​​duomenų bazėse esančiais objektais. Teoriškai tai atveria galimybę modeliuoti lenteles skirtingų duomenų bazių pavidalu, tačiau vienu metu aš nuėjau kitu keliu, išsamiai aprašytu toliau.

Raktai ir vertybės

Struktūra MDB_val modeliuoja ir rakto, ir vertės sampratą. Saugykla neturi supratimo apie jų semantiką. Jai kažkas, kas skiriasi, yra tik tam tikro dydžio baitų masyvas. Maksimalus rakto dydis yra 512 baitų.

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

Parduotuvė naudoja lyginamąjį įrankį, kad rūšiuotų raktus didėjančia tvarka. Jei nepakeisite jo savo, bus naudojamas numatytasis, kuris juos surūšiuoja baitais po baitų leksikografine tvarka.​

Sandoriai

Operacijos įrenginys išsamiai aprašytas ankstesnis skyrius, todėl trumpoje eilutėje pakartosiu pagrindines jų savybes:

1. Visų pagrindinių savybių palaikymas RŪGŠTISRaktažodžiai: atomiškumas, nuoseklumas, izoliacija ir patikimumas. Negaliu nepastebėti, kad „MacOS“ ir „iOS“ patvarumo požiūriu MDBX ištaisyta klaida. Daugiau galite paskaityti jų SKAITYK MANE.
2. Požiūris į kelių gijų sudarymą apibūdinamas schema „vienas rašytojas / keli skaitytojai“. Rašytojai blokuoja vieni kitus, bet neblokuoja skaitytojų. Skaitytojai neblokuoja nei rašytojų, nei vieni kitų.
3. Įdėtųjų operacijų palaikymas.
4. Daugiaversijų palaikymas.

Daugiaversijų kūrimas LMDB yra toks geras, kad noriu tai parodyti praktiškai. Žemiau pateiktas kodas rodo, kad kiekviena operacija veikia su tiksliai ta duomenų bazės versija, kuri buvo aktuali jos atidarymo metu, ir yra visiškai izoliuota nuo visų vėlesnių pakeitimų. Saugyklos inicijavimas ir bandymo įrašo įtraukimas į ją neįdomu, todėl šie ritualai paliekami po spoileriu.

Pridedamas bandomasis įrašas

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

Pasirinktinai rekomenduoju išbandyti tą patį triuką su SQLite ir pažiūrėti, kas atsitiks.

Daugiaversijų naudojimas suteikia labai malonių privalumų iOS kūrėjo gyvenimui. Naudodami šią ypatybę galite lengvai ir natūraliai koreguoti duomenų šaltinio naujinimo dažnį ekrano formoms, atsižvelgdami į naudotojo patirtį. Pavyzdžiui, paimkime tokią Mail.ru Cloud programos funkciją kaip automatinis turinio įkėlimas iš sistemos medijos galerijos. Turėdamas gerą ryšį, klientas gali pridėti keletą nuotraukų per sekundę prie serverio. Jei atnaujinate po kiekvieno atsisiuntimo UICollectionView Turėdami medijos turinį vartotojo debesyje, šio proceso metu galite pamiršti apie 60 kadrų per sekundę greitį ir sklandų slinkimą. Kad išvengtumėte dažnų ekrano atnaujinimų, turite kažkaip apriboti duomenų pasikeitimo greitį bazėje UICollectionViewDataSource.

Jei duomenų bazė nepalaiko kelių versijų ir leidžia dirbti tik su esama dabartine būsena, tada norint sukurti laiko stabilų duomenų momentinį vaizdą, reikia nukopijuoti jį į kokią nors atmintyje esančią duomenų struktūrą arba į laikiną lentelę. Bet kuris iš šių būdų yra labai brangus. Atmintyje esančios saugyklos atveju gauname ir atminties sąnaudas, atsirandančias dėl sukonstruotų objektų saugojimo, ir laiko sąnaudas, susijusias su perteklinėmis ORM transformacijomis. Kalbant apie laikiną stalą, tai dar brangesnis malonumas, kuris prasmingas tik nereikšmingais atvejais.

Daugiaversijos LMDB išsprendžia stabilaus duomenų šaltinio palaikymo problemą labai elegantiškai. Užtenka tik atidaryti operaciją ir voila – kol jos neužbaigsime, duomenų rinkinys garantuotai bus sutvarkytas. Jo atnaujinimo greičio logika dabar visiškai priklauso nuo pristatymo sluoksnio, be didelių išteklių.

Kursoriai

Žymekliai suteikia mechanizmą, kaip tvarkingai iteruoti raktų ir reikšmių poras, kertant B medį. Be jų būtų neįmanoma efektyviai modeliuoti lenteles duomenų bazėje, į kurią dabar kreipiamės.

4.2. Stalo modeliavimas

Raktų išdėstymo ypatybė leidžia sukurti aukščiausio lygio abstrakciją, pvz., lentelę ant pagrindinių abstrakcijų. Panagrinėkime šį procesą pagrindinės debesies kliento lentelės pavyzdžiu, kurioje talpykloje saugoma informacija apie visus vartotojo failus ir aplankus.

Lentelės schema

Vienas iš įprastų scenarijų, kai reikia patobulinti lentelės su aplankų medžiu struktūrą, yra pasirinkti visus elementus, esančius tam tikrame kataloge. Geras duomenų organizavimo modelis tokio tipo užklausoms atlikti yra Adjacency sąrašas. Norint jį įdiegti ant raktų-reikšmių saugyklos, reikia surūšiuoti failų ir aplankų raktus taip, kad jie būtų sugrupuoti pagal priklausymą pirminiam katalogui. Be to, norint, kad katalogo turinys būtų rodomas Windows vartotojui pažįstama forma (pirmiausia aplankai, tada failai, abu rūšiuojami abėcėlės tvarka), į raktą būtina įtraukti atitinkamus papildomus laukus.

Toliau pateiktame paveikslėlyje parodyta, kaip, remiantis užduotimi, gali atrodyti raktų, kaip baitų masyvo, vaizdavimas. Pirmiausia dedami baitai su pirminio katalogo identifikatoriumi (raudona), po to su tipu (žalia), o jau uodegoje su pavadinimu (mėlyna) Surūšiuoti pagal numatytąjį LMDB lygintuvą leksikografine tvarka, jie surikiuojami į reikiamu būdu. Paeiliui pereinant raktus su tuo pačiu raudonu priešdėliu, gauname su jais susietas reikšmes tokia tvarka, kokia jos turėtų būti rodomos vartotojo sąsajoje (dešinėje), nereikalaujant jokio papildomo papildomo apdorojimo.

Raktų ir verčių nuoseklinimas

Visame pasaulyje yra daugybė objektų serijos metodų. Kadangi neturėjome kito reikalavimo, išskyrus greitį, pasirinkome sau greičiausią įmanomą - atminties išvaržą, kurią užima C kalbos struktūros egzempliorius, todėl katalogo elemento raktą galima modeliuoti pagal šią struktūrą. NodeKey.

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

Išsaugoti NodeKey saugojimo poreikis objekte MDB_val pastatykite rodyklę į duomenis struktūros pradžios adresu ir apskaičiuokite jų dydį naudodami funkciją sizeof.

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

Pirmajame skyriuje apie duomenų bazės atrankos kriterijus kaip svarbų atrankos veiksnį minėjau dinaminių paskirstymų sumažinimą kaip CRUD operacijų dalį. Funkcijos kodas serialize parodo, kaip LMDB atveju jų galima visiškai išvengti, kai į duomenų bazę įterpiami nauji įrašai. Iš serverio gaunamas baitų masyvas pirmiausia paverčiamas kamino struktūromis, o tada jie trivialiai iškeliami į saugyklą. Atsižvelgiant į tai, kad LMDB viduje taip pat nėra dinamiškų paskirstymų, galite gauti fantastišką situaciją pagal iOS standartus – naudokite tik kamino atmintį, kad dirbtumėte su duomenimis nuo tinklo iki disko!

Raktų užsakymas su dvejetainiu lygintuvu

Raktų eilės ryšį suteikia speciali funkcija, vadinama komparatoriumi. Kadangi variklis nieko nežino apie juose esančių baitų semantiką, numatytasis lygintuvas neturi kito pasirinkimo, kaip tik išdėstyti raktus leksikografine tvarka, naudojant jų palyginimą baitais po baitų. Jo naudojimas struktūroms sutvarkyti panašus į skutimąsi drožimo kirviu. Tačiau paprastais atvejais šis metodas man priimtinas. Alternatyva aprašyta žemiau, bet čia atkreipsiu dėmesį į keletą pakeliui išsibarsčiusių grėblių.

Pirmas dalykas, kurį reikia turėti omenyje, yra primityvių duomenų tipų atvaizdavimas atmintyje. Taigi visuose „Apple“ įrenginiuose sveikieji kintamieji saugomi tokiu formatu Mažasis Endianas. Tai reiškia, kad mažiausiai reikšmingas baitas bus kairėje ir negalėsite rūšiuoti sveikųjų skaičių naudodami jų palyginimą baitais po baitų. Pavyzdžiui, bandant tai padaryti su skaičių rinkiniu nuo 0 iki 511, bus gautas toks rezultatas.

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

Norint išspręsti šią problemą, sveikieji skaičiai turi būti saugomi rakte tokiu formatu, kuris tinka baitų lyginams. Funkcijos iš šeimos padės atlikti reikiamą transformaciją. hton* (ypač htons dvibaičiams numeriams iš pavyzdžio).

Stygų vaizdavimo programavimo formatas, kaip žinote, yra visuma istorija. Jei eilučių semantika, taip pat kodavimas, naudojamas joms atvaizduoti atmintyje, rodo, kad vienam simboliui gali būti daugiau nei vienas baitas, tada geriau nedelsiant atsisakyti idėjos naudoti numatytąjį lyginamąjį elementą.

Antras dalykas, kurį reikia nepamiršti, yra derinimo principai struct lauko kompiliatorius. Dėl jų atmintyje tarp laukų gali būti suformuoti baitai su šiukšlių reikšmėmis, o tai, žinoma, nutraukia baitų rūšiavimą. Norėdami pašalinti šiukšles, turite deklaruoti laukus griežtai nustatyta tvarka, atsižvelgdami į lygiavimo taisykles, arba naudoti atributą struktūros deklaracijoje packed.

Raktų užsakymas naudojant išorinį lygintuvą

Pagrindinė palyginimo logika gali pasirodyti per sudėtinga dvejetainiam lyginams. Viena iš daugelio priežasčių yra techninių laukų buvimas konstrukcijų viduje. Iliustruosiu jų atsiradimą mums jau žinomo katalogo elemento rakto pavyzdžiu.

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

Nepaisant viso savo paprastumo, daugeliu atvejų jis sunaudoja per daug atminties. Pavadinimo buferis yra 256 baitai, nors vidutiniškai failų ir aplankų pavadinimai retai viršija 20–30 simbolių.

Vienas iš standartinių įrašo dydžio optimizavimo būdų yra jį „iškirpti“, kad jis atitiktų tikrąjį dydį. Jo esmė ta, kad visų kintamo ilgio laukų turinys saugomas buferyje struktūros pabaigoje, o jų ilgiai – atskiruose kintamuosiuose. NodeKey transformuojamas tokiu būdu.

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

Be to, serializacijos metu nenurodytas kaip duomenų dydis sizeof visą struktūrą, o visų laukų dydis yra fiksuotas ilgis ir faktiškai naudojamos buferio dalies dydis.

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

Pertvarkymo dėka žymiai sutaupėme raktų užimamos vietos. Tačiau dėl techninės srities nameLength, numatytasis dvejetainis lygintuvas nebetinka raktų palyginimui. Jei nepakeisime jo savo, vadinasi, pavadinimo ilgis bus svarbesnis veiksnys rūšiuojant nei pats pavadinimas.

LMDB leidžia kiekvienai duomenų bazei turėti savo raktų palyginimo funkciją. Tai atliekama naudojant funkciją mdb_set_compare griežtai prieš atidarant. Dėl akivaizdžių priežasčių duomenų bazė negali būti keičiama per visą jos gyvavimo laikotarpį. Įvestyje lygintuvas gauna du raktus dvejetainiu formatu, o išvestyje grąžina palyginimo rezultatą: mažesnis nei (-1), didesnis nei (1) arba lygus (0). Pseudokodas skirtas NodeKey atrodo taip.

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

Kol visi raktai duomenų bazėje yra to paties tipo, leidžiama besąlygiškai perduoti jų baitų atvaizdą rakto taikomosios struktūros tipui. Čia yra vienas niuansas, tačiau jis bus aptartas šiek tiek žemiau poskyryje „Skaitymo įrašai“.

Vertės serializavimas

Su saugomų įrašų raktais LMDB dirba itin intensyviai. Jie lyginami vienas su kitu bet kurios programos operacijos metu, o viso sprendimo našumas priklauso nuo lyginamojo greičio. Idealiame pasaulyje raktams palyginti turėtų pakakti numatytojo dvejetainio lygintuvo, tačiau jei tikrai tektų naudoti savąjį, tada jame raktų deserializavimo procedūra turėtų būti kuo greitesnė.

Duomenų bazė ne itin domisi įrašo (reikšmės) dalimi. Jo konvertavimas iš baitų atvaizdavimo į objektą įvyksta tik tada, kai to jau reikalauja programos kodas, pavyzdžiui, kad jis būtų rodomas ekrane. Kadangi tai nutinka palyginti retai, šios procedūros spartos reikalavimai nėra tokie kritiški, o ją įgyvendindami galime daug laisviau orientuotis į patogumą, pavyzdžiui, norėdami serializuoti metaduomenis apie dar neatsisiųstus failus, naudojame NSKeyedArchiver.

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

Tačiau yra atvejų, kai našumas yra svarbus. Pavyzdžiui, išsaugodami metainformaciją apie vartotojo debesies failų struktūrą, naudojame tą patį objekto atminties išrašą. Svarbiausias uždavinys generuoti jų nuoseklųjį vaizdą yra tai, kad katalogo elementai yra modeliuojami pagal klasių hierarchiją.

Jo įgyvendinimui C kalba konkretūs įpėdinių laukai išskiriami į atskiras struktūras, o jų ryšys su bazine nurodomas per sąjungos tipo lauką. Tikrasis sąjungos turinys nurodomas per tipo techninį požymį.

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

Įrašų pridėjimas ir atnaujinimas

Serializuotas raktas ir vertė gali būti pridėti prie parduotuvės. Tam naudojama funkcija mdb_put.

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

Konfigūravimo etape saugyklai gali būti leidžiama arba uždrausta saugoti kelis įrašus su tuo pačiu raktu.​​Jei raktų dubliavimas draudžiamas, įterpdami įrašą galite nustatyti, ar leidžiama atnaujinti jau esamą įrašą, ar ne. Jei susidėvėjimas gali atsirasti tik dėl kodo klaidos, galite apsidrausti nuo to nurodydami vėliavėlę NOOVERWRITE.

Skaitymo įrašai

LMDB įrašų skaitymo funkcija yra mdb_get. Jei raktų ir reikšmių pora atstovaujama anksčiau išmestų struktūrų, ši procedūra atrodo taip.

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

Pateiktas sąrašas parodo, kaip serializavimas per struktūrų sąvartyną leidžia atsikratyti dinaminių paskirstymų ne tik rašant, bet ir skaitant duomenis. Išvesta iš funkcijos mdb_get rodyklė tiksliai žiūri į virtualiosios atminties adresą, kuriame duomenų bazėje saugomas objekto baitas. Tiesą sakant, mes gauname savotišką ORM, beveik nemokamai užtikrinantį labai didelį duomenų skaitymo greitį. Turint visą požiūrio grožį, būtina atsiminti keletą su juo susijusių ypatybių.

1. Tik skaitomai operacijai garantuojama, kad rodyklė į vertės struktūrą galios tik tol, kol operacija bus uždaryta. Kaip minėta anksčiau, B medžio puslapiai, kuriuose yra objektas, dėl kopijavimo ir rašymo principo išlieka nepakitę tol, kol bent viena operacija nurodo juos. Tuo pačiu metu, kai tik baigiama paskutinė su jais susijusi operacija, puslapiai gali būti pakartotinai naudojami naujiems duomenims gauti. Jei reikia, kad objektai išgyventų juos sukūrusį sandorį, juos vis tiek reikia nukopijuoti.
2. Atliekant skaitymo rašymo operaciją, rodyklė į gautą struktūros reikšmę galios tik iki pirmosios modifikavimo procedūros (duomenų įrašymo arba ištrynimo).
3. Nors struktūra NodeValue ne pilnavertis, o apkarpytas (žr. poskyrį „Raktų užsakymas naudojant išorinį lygintuvą“), per žymeklį lengvai pasieksite jo laukus. Svarbiausia to nepaisyti!
4. Jokiu būdu negalite keisti struktūros per gautą žymeklį. Visi pakeitimai turi būti atliekami tik naudojant metodą mdb_put. Tačiau norint tai padaryti, tai neveiks, nes atminties sritis, kurioje yra ši struktūra, yra susieta tik skaitymo režimu.
5. Perskirstykite failą į proceso adresų erdvę, kad, pavyzdžiui, padidintumėte maksimalų saugyklos dydį naudodami funkciją mdb_env_set_map_size visiškai panaikina visas operacijas ir susijusius objektus apskritai, o ypač nuorodas į objektų skaitymą.

Galiausiai, dar viena savybė tokia klastinga, kad jos esmės atskleidimas netelpa į dar vieną punktą. Skyriuje apie B medį pateikiau jo puslapių organizavimo atmintyje schemą. Iš to išplaukia, kad buferio su serijiniais duomenimis pradžios adresas gali būti visiškai savavališkas. Dėl to žymeklis į juos, gautas struktūroje MDB_val ir mesti į rodyklę į struktūrą paprastai yra nesulygiuoti. Tuo pačiu metu kai kurių lustų architektūra (iOS atveju tai yra armv7) reikalauja, kad bet kokių duomenų adresas būtų mašinos žodžio dydžio kartotinis arba, kitaip tariant, sistemos bitumas. (armv7 atveju tai yra 32 bitai). Kitaip tariant, tokia operacija kaip *(int *foo)0x800002 ant jų prilyginamas pabėgimui ir veda į egzekuciją su nuosprendžiu EXC_ARM_DA_ALIGN. Yra du būdai, kaip išvengti tokio liūdno likimo.

Pirmasis yra iš anksto nukopijuoti duomenis į žinomą suderintą struktūrą. Pavyzdžiui, pasirinktame lyginamajame įrenginyje tai atsispindės taip.

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

Alternatyvus būdas yra iš anksto pranešti kompiliatoriui, kad struktūros su raktu ir verte gali būti nesulygiuotos naudojant atributą aligned(1). Toks pat poveikis gali būti ir ARM pasiekti ir naudojant supakuotą atributą. Atsižvelgiant į tai, kad jis taip pat prisideda prie konstrukcijos užimamos erdvės optimizavimo, šis metodas man atrodo geresnis, nors приводит padidinti duomenų prieigos operacijų kainą.

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

Diapazono užklausos

Norėdami kartoti įrašų grupę, LMDB pateikia žymeklio abstrakciją. Pažiūrėkime, kaip su juo dirbti, naudodami mums jau žinomos lentelės su naudotojo debesies metaduomenimis pavyzdį.

Rodydami failų sąrašą kataloge, turite rasti visus raktus, su kuriais susieti antriniai failai ir aplankai. Ankstesniuose poskyriuose rūšiavome raktus NodeKey kad jie pirmiausia būtų išdėstyti pagal pirminio katalogo ID. Taigi techniškai aplanko turinio gavimo užduotis sumažinama iki žymeklio uždėjimo ant viršutinės raktų grupės su nurodytu priešdėliu ribos, o po to kartojama iki apatinės ribos.

Viršutinę ribą „ant kaktos“ galite rasti nuoseklia paieška. Norėdami tai padaryti, žymeklis įdedamas į viso duomenų bazės raktų sąrašo pradžią ir padidinamas tol, kol po juo pasirodys raktas su pirminio katalogo identifikatoriumi. Šis metodas turi 2 akivaizdžius trūkumus:

1. Linijinis paieškos sudėtingumas, nors, kaip žinote, medžiuose apskritai ir konkrečiai B medyje tai galima atlikti logaritminiu laiku.
2. Veltui visi puslapiai, esantys prieš norimą, iš failo perkeliami į pagrindinę atmintį, o tai yra labai brangu.

Laimei, LMDB API yra veiksmingas būdas iš pradžių nustatyti žymeklio padėtį. Norėdami tai padaryti, turite suformuoti raktą, kurio reikšmė yra mažesnė arba lygi raktui, esančiam viršutinėje intervalo riboje. Pavyzdžiui, atsižvelgiant į aukščiau esančiame paveikslėlyje pateiktą sąrašą, galime sukurti raktą, kuriame laukas parentId bus lygus 2, o visi kiti užpildyti nuliais. Toks iš dalies užpildytas raktas yra paduodamas į funkcijos įvestį mdb_cursor_get nurodant operaciją 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);

Jei randama viršutinė klavišų grupės riba, kartojame ją, kol susitinkame arba raktas su kitu parentId, arba raktai visai nesibaigs.

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

Puiku, kad iteracijos metu naudojant mdb_cursor_get gauname ne tik raktą, bet ir vertę. Jei norint įvykdyti atrankos sąlygas, be kita ko, reikia patikrinti laukelius iš įrašo vertės dalies, tada jie yra gana prieinami be papildomų gestų.

4.3. Ryšių tarp lentelių modeliavimas

Iki šiol mums pavyko apsvarstyti visus vienos lentelės duomenų bazės projektavimo ir darbo su ja aspektus. Galima sakyti, kad lentelė yra surūšiuotų įrašų rinkinys, susidedantis iš to paties tipo raktų-reikšmių porų. Jei rodote raktą kaip stačiakampį, o su juo susijusią reikšmę kaip langelį, gausite vaizdinę duomenų bazės diagramą.

​

Tačiau realiame gyvenime retai pavyksta išsiversti su tiek mažai kraujo. Dažnai duomenų bazėje reikalaujama, pirma, turėti kelias lenteles, antra, jose atlikti pasirinkimus kita tvarka nei pirminis raktas. Paskutinis skyrius skirtas jų kūrimo ir tarpusavio ryšio klausimams.

Rodyklės lentelės

Debesų programėlėje yra skyrius „Galerija“. Rodomas medijos turinys iš viso debesies, surūšiuotas pagal datą. Norint optimaliai įgyvendinti tokį pasirinkimą, šalia pagrindinės lentelės reikia sukurti kitą su naujo tipo klavišais. Juose bus laukas su failo sukūrimo data, kuris veiks kaip pagrindinis rūšiavimo kriterijus. Kadangi naujieji raktai nurodo tuos pačius duomenis kaip ir pagrindinės lentelės raktai, jie vadinami indekso raktais. Žemiau esančiame paveikslėlyje jie paryškinti oranžine spalva.

Siekiant atskirti skirtingų lentelių raktus vienas nuo kito toje pačioje duomenų bazėje, prie visų pridėtas papildomas techninis laukas tableId. Suteikdami jam didžiausią prioritetą rūšiuojant, raktus sugrupuosime pirmiausia pagal lenteles, o jau lentelių viduje – pagal savo taisykles.

Indekso raktas nurodo tuos pačius duomenis kaip ir pirminis raktas. Paprastas šios savybės įgyvendinimas, susiejant su ja pirminio rakto vertės dalies kopiją, yra neoptimalus iš karto keliais požiūriais:​

1. Kalbant apie užimtą erdvę, metaduomenys gali būti gana turtingi.
2. Našumo požiūriu, kadangi atnaujindami mazgo metaduomenis turėsite perrašyti du raktus.
3. Kodo palaikymo požiūriu, juk jei pamiršime atnaujinti vieno iš raktų duomenis, sulauksime subtilaus duomenų nenuoseklumo saugykloje.

Toliau mes apsvarstysime, kaip pašalinti šiuos trūkumus.

Ryšių tarp lentelių organizavimas

Šablonas puikiai tinka susieti rodyklės lentelę su pagrindine „raktas kaip vertė“. Kaip rodo pavadinimas, indekso įrašo vertės dalis yra pirminio rakto vertės kopija. Šis metodas pašalina visus aukščiau išvardytus trūkumus, susijusius su pirminio įrašo vertės dalies kopijos saugojimu. Vienintelis mokestis yra tas, kad norėdami gauti vertę pagal indekso raktą, turite pateikti 2 užklausas duomenų bazėje, o ne vieną. Schematiškai gauta duomenų bazės schema yra tokia.

Kitas santykių tarp lentelių organizavimo modelis yra "perteklinis raktas". Jo esmė – pridėti prie rakto papildomų atributų, kurių reikia ne rūšiavimui, o susietam raktui atkurti.. Jo panaudojimo Mail.ru Cloud aplikacijoje yra realių pavyzdžių, tačiau, norint išvengti gilaus nardymo konkrečių iOS karkasų kontekste pateiksiu fiktyvų, bet labiau suprantamą pavyzdį.

„Cloud Mobile“ klientai turi puslapį, kuriame rodomi visi failai ir aplankai, kuriuos vartotojas bendrino su kitais žmonėmis. Kadangi tokių failų yra palyginti nedaug, o su jomis susieta daug konkrečios informacijos apie viešumą (kam suteikiama prieiga, kokiomis teisėmis ir pan.), nebus racionalu apkrauti jos vertybine dalimi. įrašas pagrindinėje lentelėje. Tačiau jei norite tokius failus rodyti neprisijungę, vis tiek turite juos kažkur saugoti. Natūralus sprendimas – sukurti tam atskirą lentelę. Toliau pateiktoje diagramoje jo raktas yra priešdėlis „P“, o vietos rezervavimo ženklas „propname“ gali būti pakeistas konkretesne reikšme „public info“.​

Visi unikalūs metaduomenys, dėl kurių buvo sukurta nauja lentelė, perkeliami į įrašo vertės dalį. Tuo pačiu metu nenoriu kopijuoti duomenų apie failus ir aplankus, kurie jau yra saugomi pagrindinėje lentelėje. Vietoj to, pertekliniai duomenys pridedami prie „P“ rakto laukų „mazgo ID“ ir „laiko žyma“ pavidalu. Jų dėka galite sukurti indekso raktą, pagal kurį galite gauti pirminį raktą, pagal kurį galite gauti mazgo metaduomenis.

Išvada

LMDB įgyvendinimo rezultatus vertiname teigiamai. Po jo paraiškų užšaldymo skaičius sumažėjo 30%.

Atlikto darbo rezultatai sulaukė atsakymo už iOS komandos ribų. Šiuo metu viena iš pagrindinių „Failai“ skilčių „Android“ programoje taip pat perėjo prie LMDB naudojimo, o kitos dalys yra pakeliui. C kalba, kurioje įdiegta rakto vertės saugykla, buvo gera pagalba, kad iš pradžių programa būtų susieta su įvairiomis platformomis C ++ kalba. Norint sklandžiai sujungti gautą C ++ biblioteką su platformos kodu Objective-C ir Kotlin, buvo naudojamas kodų generatorius Džinni iš Dropbox, bet tai jau kita istorija.

Šaltinis: www.habr.com