În toamna lui 2019, în echipa Mail.ru Cloud iOS a avut loc un eveniment mult așteptat. Principala bază de date pentru stocarea persistentă a stării aplicației a devenit destul de exotică pentru lumea mobilă (LMDB). Sub tăietură, atenția dumneavoastră este invitată la revizuirea sa detaliată în patru părți. În primul rând, să vorbim despre motivele unei astfel de alegeri netriviale și dificile. Apoi, să trecem la considerarea a trei balene în centrul arhitecturii LMDB: fișiere mapate în memorie, arbore B +, abordare copy-on-write pentru implementarea tranzacțională și multiversiune. În cele din urmă, pentru desert - partea practică. În acesta, vom analiza cum să proiectăm și să implementăm o schemă de bază cu mai multe tabele, inclusiv unul index, pe deasupra API-ului cheie-valoare de nivel scăzut.
Conținut
3.1.
3.2.
3.3.
4.1.
4.2.
4.3.
1. Motivația implementării
O dată pe an, în 2015, ne-am ocupat să luăm o metrică, cât de des întârzie interfața aplicației noastre. Nu doar am făcut asta. Avem din ce în ce mai multe plângeri cu privire la faptul că uneori aplicația nu mai răspunde la acțiunile utilizatorului: butoanele nu sunt apăsate, listele nu defilează etc. Despre mecanica măsurătorilor pe AvitoTech, așa că aici dau doar ordinea numerelor.
Rezultatele măsurătorilor au devenit pentru noi un duș rece. S-a dovedit că problemele cauzate de înghețuri sunt mult mai multe decât oricare altele. Dacă, înainte de a realiza acest fapt, principalul indicator tehnic al calității a fost fără accidente, atunci după focalizare pe freeze free.
După ce a construit și după ce a cheltuit и analiza cauzelor lor, principalul inamic a devenit clar - logica grea de afaceri care se execută în firul principal al aplicației. O reacție firească la această rușine a fost dorința arzătoare de a o împinge în fluxurile de muncă. Pentru o soluție sistematică a acestei probleme, am recurs la o arhitectură multi-threaded bazată pe actori ușori. I-am dedicat adaptările pentru lumea iOS în twitterul colectiv și . Ca parte a poveștii curente, vreau să subliniez acele aspecte ale deciziei care au influențat alegerea bazei de date.
Modelul actoric al organizării sistemului presupune că multithreadingul devine a doua sa esență. Obiectelor model din el le place să depășească granițele firelor. Și fac asta nu uneori și în unele locuri, ci aproape constant și peste tot.
Baza de date este una dintre componentele de bază din diagrama prezentată. Sarcina sa principală este de a implementa un model macro . Dacă în lumea întreprinderii se folosește pentru organizarea sincronizării datelor între servicii, atunci în cazul unei arhitecturi actori, date între fire. Astfel, aveam nevoie de o astfel de bază de date, lucru cu care într-un mediu multi-threaded nu cauzează nici măcar dificultăți minime. În special, aceasta înseamnă că obiectele derivate din acesta trebuie să fie cel puțin sigure pentru fire și, în mod ideal, să nu fie modificabile deloc. După cum știți, acesta din urmă poate fi folosit simultan din mai multe fire fără a recurge la niciun fel de încuietori, ceea ce are un efect benefic asupra performanței.
Al doilea factor semnificativ care a influențat alegerea bazei de date a fost API-ul nostru cloud. A fost inspirat de abordarea git a sincronizarii. La fel ca el spre care ne-am țintit , care pare mai mult decât potrivit pentru clienții cloud. S-a presupus că vor pompa doar o singură dată starea completă a norului, iar apoi sincronizarea în marea majoritate a cazurilor ar avea loc prin modificări repetate. Din păcate, această posibilitate este încă doar în zona teoretică și, în practică, clienții nu au învățat cum să lucreze cu patch-uri. Există o serie de motive obiective pentru aceasta, pe care, pentru a nu întârzia introducerea, le vom lăsa din paranteze. Acum, mult mai interesante sunt rezultatele instructive ale lecției despre ce se întâmplă când API-ul a spus „A” și consumatorul său nu a spus „B”.
Deci, dacă vă imaginați git, care, atunci când executați o comandă pull, în loc să aplice patch-uri unui instantaneu local, își compară starea completă cu cea completă a serverului, atunci veți avea o idee destul de precisă a modului de sincronizare. apare în clienții cloud. Este ușor de ghicit că pentru implementarea sa este necesară alocarea a doi arbori DOM în memorie cu metainformații despre toate fișierele server și locale. Se pare că, dacă un utilizator stochează 500 de mii de fișiere în cloud, atunci pentru a-l sincroniza, este necesar să recreați și să distrugeți doi copaci cu 1 milion de noduri. Dar fiecare nod este un agregat care conține un grafic de subobiecte. În această lumină, rezultatele profilării erau așteptate. S-a dovedit că, chiar și fără a lua în considerare algoritmul de îmbinare, însăși procedura de a crea și apoi a distruge un număr mare de obiecte mici costă un bănuț destul de.Situația este agravată de faptul că operația de sincronizare de bază este inclusă într-un număr mare. a scripturilor utilizatorului. Drept urmare, fixăm al doilea criteriu important în alegerea unei baze de date - capacitatea de a implementa operațiuni CRUD fără alocarea dinamică a obiectelor.
Alte cerințe sunt mai tradiționale, iar lista lor completă este următoarea.
- Siguranța firului.
- Multiprocesare. Dictată de dorința de a folosi aceeași instanță de bază de date pentru a sincroniza starea nu numai între fire, ci și între aplicația principală și extensiile iOS.
- Abilitatea de a reprezenta entitățile stocate ca obiecte nemutabile.
- Lipsa alocărilor dinamice în cadrul operațiunilor CRUD.
- Suport pentru tranzacții pentru proprietățile de bază Cuvinte cheie: atomicitate, consistență, izolare și fiabilitate.
- Viteză pe cele mai populare cazuri.
Cu acest set de cerințe, SQLite a fost și este încă o alegere bună. Cu toate acestea, ca parte a studiului alternativelor, am dat peste o carte . Sub conducerea ei, a fost scris un benchmark care compară viteza de lucru cu diferite baze de date în scenarii reale în cloud. Rezultatul a depășit cele mai sălbatice așteptări. În cele mai populare cazuri - obținerea unui cursor pe o listă sortată a tuturor fișierelor și o listă sortată a tuturor fișierelor pentru un anumit director - LMDB s-a dovedit a fi de 10 ori mai rapid decât SQLite. Alegerea a devenit evidentă.
2. Poziţionarea LMDB
LMDB este o bibliotecă, foarte mică (doar 10K linii) care implementează cel mai de jos strat fundamental al bazelor de date - stocarea.
Diagrama de mai sus arată că compararea LMDB cu SQLite, care implementează niveluri chiar mai înalte, nu este în general mai corectă decât SQLite cu Core Data. Ar fi mai corect să menționăm aceleași motoare de stocare ca și concurenți egali - BerkeleyDB, LevelDB, Sophia, RocksDB etc. Există chiar dezvoltări în care LMDB acționează ca o componentă a motorului de stocare pentru SQLite. Primul astfel de experiment a fost în 2012 autor LMDB . s-a dovedit a fi atât de intrigant încât inițiativa sa a fost preluată de entuziaștii OSS și și-a găsit continuarea în fața . În ianuarie 2020, autorul acestui proiect este Den Shearer pe LinuxConfAu.
Utilizarea principală a LMDB este ca motor pentru bazele de date de aplicații. Biblioteca își datorează aspectul dezvoltatorilor , care au fost puternic nemulțumiți de BerkeleyDB ca bază a proiectului lor. Îndepărtându-se de umila bibliotecă , Howard Chu a reușit să creeze una dintre cele mai populare alternative ale timpului nostru. El și-a dedicat raportul foarte cool acestei povești, precum și structurii interne a LMDB . Leonid Yuriev (alias ) de la Positive Technologies în discursul său la Highload 2015 . În ea, el vorbește despre LMDB în contextul unei sarcini similare de implementare a ReOpenLDAP, iar LevelDB a suferit deja critici comparative. Ca urmare a implementării, Positive Technologies a primit chiar și o furcă în curs de dezvoltare cu caracteristici foarte gustoase, optimizări și .
LMDB este adesea folosit ca și stocare așa cum este. De exemplu, browserul Mozilla Firefox pentru o serie de nevoi și, începând cu versiunea 9, Xcode SQLite-ul său pentru a stoca indecși.
Motorul a prins și în lumea dezvoltării mobile. Urmele utilizării sale pot fi în clientul iOS pentru Telegram. LinkedIn a făcut un pas mai departe și a ales LMDB ca stocare implicită pentru cadrul său de stocare în cache a datelor, Rocket Data, despre care într-un articol din 2016.
LMDB luptă cu succes pentru un loc la soare în nișa lăsată de BerkeleyDB după trecerea sub controlul Oracle. Biblioteca este iubită pentru viteza și fiabilitatea sa, chiar și în comparație cu propriul ei tip. După cum știți, nu există prânzuri gratuite și aș dori să subliniez compromisul cu care va trebui să vă confruntați atunci când alegeți între LMDB și SQLite. Diagrama de mai sus demonstrează clar cum se atinge viteza crescută. În primul rând, nu plătim pentru straturi suplimentare de abstractizare pe deasupra stocării pe disc. Desigur, într-o arhitectură bună, încă nu te poți descurca fără ele și vor apărea inevitabil în codul aplicației, dar vor fi mult mai subțiri. Nu vor avea caracteristici care nu sunt cerute de o anumită aplicație, de exemplu, suport pentru interogări în limbajul SQL. În al doilea rând, devine posibilă implementarea optimă a maparii operațiunilor aplicației la cererile de stocare pe disc. Dacă SQLite provine din nevoile medii ale unei aplicații medii, atunci tu, în calitate de dezvoltator de aplicații, cunoști bine scenariile de încărcare principale. Pentru o soluție mai productivă, va trebui să plătiți un preț mai mare atât pentru dezvoltarea soluției inițiale, cât și pentru suportul ulterior.
3. Trei balene LMDB
După ce ne uităm la LMDB din vedere de pasăre, este timpul să mergem mai adânc. Următoarele trei secțiuni vor fi dedicate analizei principalelor balene pe care se sprijină arhitectura de stocare:
- Fișierele mapate în memorie ca mecanism de lucru cu disc și sincronizarea structurilor de date interne.
- Arborele B+ ca organizare a structurii de date stocate.
- Copy-on-write ca abordare pentru a oferi proprietăți tranzacționale ACID și multiversioning.
3.1. Balena #1. Fișiere mapate în memorie
Fișierele mapate în memorie sunt un element arhitectural atât de important încât apar chiar și în numele depozitului. Problemele legate de stocarea în cache și sincronizarea accesului la informațiile stocate sunt în întregime la cheremul sistemului de operare. LMDB nu conține nicio memorie cache în sine. Aceasta este o decizie conștientă a autorului, deoarece citirea datelor direct din fișierele mapate vă permite să tăiați multe colțuri în implementarea motorului. Mai jos este o listă departe de a fi completă a unora dintre ele.
- Menținerea consistenței datelor din stocare atunci când lucrați cu acestea din mai multe procese devine responsabilitatea sistemului de operare. În secțiunea următoare, acest mecanic este discutat în detaliu și cu imagini.
- Absența cache-urilor scutește complet LMDB de suprasarcina asociată cu alocările dinamice. Citirea datelor în practică înseamnă setarea indicatorului către adresa corectă în memoria virtuală și nimic mai mult. Sună a fantezie, dar în sursa depozitului, toate apelurile calloc sunt concentrate în funcția de configurare a depozitului.
- Absența cache-urilor înseamnă și absența blocărilor asociate cu sincronizarea pentru a le accesa. Cititorii, dintre care un număr arbitrar poate exista în același timp, nu întâlnesc un singur mutex în drumul lor către date. Datorită acestui fapt, viteza de citire are o scalabilitate liniară ideală în ceea ce privește numărul de procesoare. În LMDB, numai operațiunile de modificare sunt sincronizate. Nu poate exista decât un singur scriitor la un moment dat.
- Un minim de memorare în cache și logica de sincronizare salvează codul de un tip extrem de complex de erori asociate cu lucrul într-un mediu cu mai multe fire. Au existat două studii interesante de baze de date la conferința Usenix OSDI 2014: и . De la ei puteți obține informații atât despre fiabilitatea fără precedent a LMDB, cât și despre implementarea aproape impecabilă a proprietăților ACID ale tranzacțiilor, care o depășește în același SQLite.
- Minimalismul LMDB permite ca reprezentarea mașinii codului său să fie complet plasată în memoria cache L1 a procesorului cu caracteristicile de viteză rezultate.
Din păcate, în iOS, fișierele mapate în memorie nu sunt atât de roz pe cât ne-am dori. Pentru a vorbi mai conștient despre dezavantajele asociate acestora, este necesar să reamintim principiile generale de implementare a acestui mecanism în sistemele de operare.
Informații generale despre fișierele mapate în memorie
Cu fiecare aplicație executabilă, sistemul de operare asociază o entitate numită proces. Fiecărui proces i se alocă o gamă contiguă de adrese în care plasează tot ce are nevoie pentru a funcționa. Cele mai mici adrese conțin secțiuni cu cod și date și resurse hardcoded. Urmează blocul în creștere al spațiului de adrese dinamice, bine cunoscut de noi sub numele de heap. Conține adresele entităților care apar în timpul funcționării programului. În partea de sus este zona de memorie utilizată de stiva de aplicații. Fie crește, fie se micșorează, cu alte cuvinte, dimensiunea sa are și o natură dinamică. Pentru ca stiva și grămada să nu se împingă și să interfereze una cu cealaltă, acestea sunt separate la capete diferite ale spațiului de adrese.Există o gaură între cele două secțiuni dinamice în partea de sus și de jos. Adresele din această secțiune din mijloc sunt folosite de sistemul de operare pentru a se asocia cu un proces de diferite entități. În special, poate mapa un anumit set continuu de adrese pe un fișier de pe disc. Un astfel de fișier se numește fișier mapat cu memorie.
Spațiul de adrese alocat unui proces este uriaș. Teoretic, numărul de adrese este limitat doar de dimensiunea pointerului, care este determinată de adâncimea de biți a sistemului. Dacă i-ar fi atribuită memorie fizică 1-în-1, atunci primul proces ar înghiți întreaga memorie RAM și nu s-ar pune problema vreunui multitasking.
Cu toate acestea, știm din experiență că sistemele de operare moderne pot rula câte procese doriți în același timp. Acest lucru este posibil datorită faptului că alocă multă memorie proceselor doar pe hârtie, dar în realitate încarcă în memoria fizică principală doar acea parte care este solicitată aici și acum. Prin urmare, memoria asociată procesului se numește virtuală.
Sistemul de operare organizează memoria virtuală și fizică în pagini de o anumită dimensiune. De îndată ce o anumită pagină de memorie virtuală este solicitată, sistemul de operare o încarcă în memoria fizică și pune o corespondență între ele într-un tabel special. Dacă nu există sloturi libere, atunci una dintre paginile încărcate anterior este copiată pe disc, iar cea solicitată îi ia locul. Această procedură, la care vom reveni în curând, se numește swapping. Figura de mai jos ilustrează procesul descris. Pe ea, pagina A cu adresa 0 a fost încărcată și plasată pe pagina de memorie principală cu adresa 4. Acest fapt a fost reflectat în tabelul de corespondență din celula numărul 0.
Cu fișierele mapate în memorie, povestea este exact aceeași. În mod logic, se presupune că sunt plasate continuu și în întregime în spațiul de adrese virtuale. Cu toate acestea, acestea intră în memoria fizică pagină cu pagină și numai la cerere. Modificarea unor astfel de pagini este sincronizată cu fișierul de pe disc. Astfel, puteți efectua I/O fișier, pur și simplu lucrând cu octeți din memorie - toate modificările vor fi transferate automat de către nucleul sistemului de operare în fișierul original.
Imaginea de mai jos demonstrează cum LMDB își sincronizează starea atunci când lucrează cu baza de date din diferite procese. Prin maparea memoriei virtuale a diferitelor procese pe același fișier, obligăm de facto sistemul de operare să sincronizeze tranzitiv anumite blocuri ale spațiilor lor de adrese între ele, care este locul în care arată LMDB.
O nuanță importantă este că LMDB modifică fișierul de date în mod implicit prin mecanismul de apel de sistem de scriere, iar fișierul în sine este afișat în modul numai citire. Această abordare are două implicații importante.
Prima consecință este comună tuturor sistemelor de operare. Esența sa este de a adăuga protecție împotriva deteriorării accidentale a bazei de date prin cod incorect. După cum știți, instrucțiunile executabile ale unui proces sunt libere pentru a accesa datele de oriunde în spațiul său de adrese. În același timp, așa cum tocmai ne-am amintit, afișarea unui fișier în modul citire-scriere înseamnă că orice instrucțiune îl poate modifica în plus. Dacă face acest lucru din greșeală, încercând, de exemplu, să suprascrie efectiv un element de matrice la un index inexistent, atunci în acest fel poate schimba accidental fișierul mapat la această adresă, ceea ce va duce la coruperea bazei de date. Dacă fișierul este afișat în modul doar citire, atunci o încercare de a schimba spațiul de adrese corespunzător acestuia va duce la blocarea programului cu semnalul SIGSEGV, iar fișierul va rămâne intact.
A doua consecință este deja specifică iOS. Nici autorul, nici alte surse nu o menționează în mod explicit, dar fără el, LMDB ar fi nepotrivit pentru rularea pe acest sistem de operare mobil. Următoarea secțiune este dedicată analizei sale.
Specificații fișierelor mapate cu memorie în iOS
În 2018, a existat un reportaj minunat la WWDC . Acesta spune că în iOS toate paginile aflate în memoria fizică aparțin unuia dintre cele 3 tipuri: murdar, comprimat și curat.
Memoria curată este o colecție de pagini care pot fi schimbate în siguranță din memoria fizică. Datele pe care le conțin pot fi reîncărcate din sursele lor originale, după cum este necesar. Fișierele mapate cu memorie doar pentru citire se încadrează în această categorie. iOS nu se teme să descarce oricând paginile mapate într-un fișier din memorie, deoarece acestea sunt garantate să fie sincronizate cu fișierul de pe disc.
Toate paginile modificate intră în memoria murdară, indiferent unde se află inițial. În special, fișierele mapate în memorie modificate prin scrierea în memoria virtuală asociată acestora vor fi, de asemenea, clasificate în acest fel. Deschiderea LMDB cu steag MDB_WRITEMAP, după ce ați făcut modificări, puteți vedea singur.
De îndată ce o aplicație începe să ocupe prea multă memorie fizică, iOS își comprimă paginile murdare. Colecția de memorie ocupată de pagini murdare și comprimate este așa-numita amprentă de memorie a aplicației. Când atinge o anumită valoare de prag, demonul sistemului OOM killer vine după proces și îl încheie forțat. Aceasta este particularitatea iOS în comparație cu sistemele de operare desktop. În schimb, reducerea amprentei de memorie prin schimbarea paginilor din memoria fizică pe disc nu este furnizată în iOS. Se poate doar ghici despre motive. Poate că procedura de mutare intensivă a paginilor pe disc și înapoi este prea consumatoare de energie pentru dispozitivele mobile sau iOS economisește resursa de rescriere a celulelor pe discuri SSD sau poate că designerii nu au fost mulțumiți de performanța generală a sistemului, unde totul este schimbat constant. Oricum ar fi, faptul rămâne.
Vestea bună, deja menționată mai devreme, este că LMDB nu folosește mecanismul mmap pentru a actualiza fișierele în mod implicit. Rezultă că datele redate sunt clasificate ca memorie curată de iOS și nu contribuie la amprenta memoriei. Acest lucru poate fi verificat folosind instrumentul Xcode numit VM Tracker. Captura de ecran de mai jos arată starea memoriei virtuale a aplicației iOS Cloud în timpul funcționării. La început, în el au fost inițializate 2 instanțe LMDB. Primului i s-a permis să mapeze fișierul la 1GiB de memorie virtuală, al doilea - 512MiB. În ciuda faptului că ambele stocări ocupă o anumită cantitate de memorie rezidentă, niciuna dintre ele nu contribuie la dimensiunea murdară.
Acum este timpul pentru veștile proaste. Datorită mecanismului de schimb din sistemele de operare desktop pe 64 de biți, fiecare proces poate ocupa atât spațiu de adresă virtuală cât permite spațiul liber de pe hard disk pentru potențialul său schimb. Înlocuirea schimbului cu compresie în iOS reduce drastic maximul teoretic. Acum, toate procesele vii trebuie să se încadreze în memoria principală (de citire RAM), iar toate cele care nu se potrivesc sunt supuse încetării forțate. Este menționat ca în cele de mai sus și în . În consecință, iOS limitează sever cantitatea de memorie disponibilă pentru alocarea prin mmap. Aici vă puteți uita la limitele empirice ale cantității de memorie care ar putea fi alocată pe diferite dispozitive folosind acest apel de sistem. Pe cele mai moderne modele de smartphone-uri, iOS a devenit generos cu 2 gigabytes, iar pe versiunile de top ale iPad-ului - cu 4. În practică, bineînțeles, trebuie să vă concentrați pe cele mai tinere modele de dispozitive suportate, unde totul este foarte trist. Și mai rău, privind starea memoriei aplicației în VM Tracker, veți descoperi că LMDB este departe de singurul care revendică memorie mapată cu memorie. Bucăți bune sunt mâncate de alocatorii de sistem, fișierele de resurse, cadrele de imagine și alți prădători mai mici.
Pe baza rezultatelor experimentelor în Cloud, am ajuns la următoarele valori de compromis ale memoriei alocate de LMDB: 384 megaocteți pentru dispozitivele pe 32 de biți și 768 pentru cele pe 64 de biți. După ce acest volum este epuizat, orice operațiuni de modificare încep să se finalizeze cu codul MDB_MAP_FULL. Observăm astfel de erori în monitorizarea noastră, dar sunt suficient de mici pentru a fi neglijate în această etapă.
Un motiv neevident pentru consumul excesiv de memorie prin stocare poate fi tranzacțiile de lungă durată. Pentru a înțelege cum sunt legate aceste două fenomene, ne va ajuta să luăm în considerare celelalte două balene LMDB.
3.2. Balena #2. B+-arborele
Pentru a emula tabele deasupra unui magazin cheie-valoare, următoarele operațiuni trebuie să fie prezente în API-ul său:
- Inserarea unui nou element.
- Căutați un element cu o cheie dată.
- Ștergerea unui element.
- Iterați pe intervale cheie în ordinea lor de sortare.
Cea mai simplă structură de date care poate implementa cu ușurință toate cele patru operațiuni este un arbore de căutare binar. Fiecare dintre nodurile sale este o cheie care împarte întregul subset de chei copil în doi subarbori. În stânga sunt cele care sunt mai mici decât părintele, iar în dreapta - cele care sunt mai mari. Obținerea unui set ordonat de chei se realizează printr-una dintre clasicele traversări ale arborilor.
Arborii binari au două dezavantaje fundamentale care îi împiedică să fie eficienți ca structură de date pe disc. În primul rând, gradul de echilibru al acestora este imprevizibil. Există un risc considerabil de a obține arbori în care înălțimea diferitelor ramuri poate varia foarte mult, ceea ce agravează semnificativ complexitatea algoritmică a căutării în comparație cu ceea ce se așteaptă. În al doilea rând, abundența legăturilor încrucișate între noduri privează arborii binari de localitate în memorie.Nodurile apropiate (în ceea ce privește legăturile dintre ele) pot fi localizate pe pagini complet diferite din memoria virtuală. În consecință, chiar și o simplă parcurgere a mai multor noduri învecinate dintr-un arbore poate necesita vizitarea unui număr comparabil de pagini. Aceasta este o problemă chiar și atunci când vorbim despre eficiența arborilor binari ca structură de date în memorie, deoarece rotirea constantă a paginilor din memoria cache a procesorului nu este ieftină. Când vine vorba de ridicarea frecventă a paginilor legate de noduri de pe disc, lucrurile devin foarte proaste. .
Arborii B, fiind o evoluție a arborilor binari, rezolvă problemele identificate în paragraful anterior. În primul rând, se autoechilibrează. În al doilea rând, fiecare dintre nodurile lor împarte setul de chei copil nu în 2, ci în M subseturi ordonate, iar numărul M poate fi destul de mare, de ordinul a câteva sute sau chiar mii.
Astfel:
- Fiecare nod are un număr mare de chei deja comandate și arborii sunt foarte mici.
- Arborele dobândește proprietatea localității în memorie, deoarece cheile care sunt apropiate ca valoare sunt situate în mod natural una lângă alta pe unul sau nodurile învecinate.
- Reduce numărul de noduri de tranzit la coborârea arborelui în timpul unei operațiuni de căutare.
- Reduce numărul de noduri țintă citite pentru interogări de interval, deoarece fiecare dintre ele conține deja un număr mare de chei ordonate.
LMDB folosește o variantă a arborelui B numită arborele B+ pentru a stoca date. Diagrama de mai sus prezintă cele trei tipuri de noduri pe care le conține:
- În partea de sus este rădăcina. Nu materializează nimic mai mult decât conceptul de bază de date în cadrul unui depozit. Într-o singură instanță LMDB, puteți crea mai multe baze de date care partajează spațiul de adrese virtuale mapat. Fiecare dintre ele pornește de la propria sa rădăcină.
- La cel mai de jos nivel sunt frunzele (frunza). Ei și numai ei sunt cei care conțin perechile cheie-valoare stocate în baza de date. Apropo, aceasta este particularitatea arborilor B+. Dacă un arbore B normal stochează părțile valorice la nodurile tuturor nivelurilor, atunci variația B+ este doar la cea mai mică. După ce am remediat acest fapt, în cele ce urmează vom numi subtipul arborelui utilizat în LMDB pur și simplu un arbore B.
- Între rădăcină și frunze, există 0 sau mai multe niveluri tehnice cu noduri de navigație (ramură). Sarcina lor este să împartă setul sortat de chei între frunze.
Din punct de vedere fizic, nodurile sunt blocuri de memorie cu o lungime predeterminată. Dimensiunea lor este un multiplu al dimensiunii paginilor de memorie din sistemul de operare, despre care am vorbit mai sus. Structura nodului este prezentată mai jos. Antetul conține metainformații, dintre care cea mai evidentă, de exemplu, este suma de control. Urmează informații despre decalaje, de-a lungul cărora se află celulele cu date. Rolul datelor poate fi fie chei, dacă vorbim de noduri de navigare, fie perechi cheie-valoare întregi în cazul frunzelor.Puteți citi mai multe despre structura paginilor în lucrare. .
După ce ne-am ocupat de conținutul intern al nodurilor paginii, vom reprezenta în continuare arborele B LMDB într-un mod simplificat în următoarea formă.
Paginile cu noduri sunt aranjate secvenţial pe disc. Paginile cu un număr mai mare sunt situate spre sfârșitul fișierului. Așa-numita pagina meta (meta pagina) conține informații despre compensații, care pot fi folosite pentru a găsi rădăcinile tuturor copacilor. Când un fișier este deschis, LMDB scanează fișierul pagină cu pagină de la sfârșit până la început în căutarea unei meta-pagini valide și găsește bazele de date existente prin intermediul acesteia.
Acum, având o idee despre structura logică și fizică a organizării datelor, putem continua să luăm în considerare a treia balenă a LMDB. Cu ajutorul lui, toate modificările de stocare au loc tranzacțional și izolat unele de altele, dând bazei de date în ansamblu și proprietatea multiversiune.
3.3. Balena #3. Copie pe scriere
Unele operațiuni B-tree implică efectuarea unei serii întregi de modificări la nodurile sale. Un exemplu este adăugarea unei noi chei la un nod care și-a atins deja capacitatea maximă. În acest caz, este necesar, în primul rând, să împărțiți nodul în două și, în al doilea rând, să adăugați o legătură la noul nod copil separat din părintele său. Această procedură este potențial foarte periculoasă. Dacă dintr-un anumit motiv (accident, întrerupere de curent etc.) are loc doar o parte din modificările din serie, atunci arborele va rămâne într-o stare inconsecventă.
O soluție tradițională pentru a face o bază de date tolerantă la erori este să adăugați o structură de date suplimentară bazată pe disc, jurnalul de tranzacții, cunoscut și sub numele de jurnal de scriere anticipată (WAL), lângă arborele B. Este un fișier, la sfârșitul căruia, strict înainte de modificarea arborelui B în sine, este scrisă operația intenționată. Astfel, dacă se detectează coruperea datelor în timpul autodiagnosticării, baza de date consultă jurnalul pentru a se curăța.
LMDB a ales o metodă diferită ca mecanism de toleranță la erori, care se numește copy-on-write. Esența sa este că, în loc să actualizeze datele de pe o pagină existentă, mai întâi le copiază în întregime și face toate modificările deja în copie.
În plus, pentru ca datele actualizate să fie disponibile, este necesar să se schimbe legătura către nodul care a devenit actualizat în nodul părinte în raport cu acesta. Deoarece trebuie modificat și pentru aceasta, este și pre-copiat. Procesul continuă recursiv până la rădăcină. Datele de pe meta-pagina sunt ultimele modificate.
Dacă procesul se blochează brusc în timpul procedurii de actualizare, atunci fie o nouă meta-pagină nu va fi creată, fie nu va fi scrisă pe disc până la sfârșit, iar suma de verificare va fi incorectă. În oricare dintre aceste două cazuri, noile pagini vor fi inaccesibile, iar cele vechi nu vor fi afectate. Acest lucru elimină necesitatea ca LMDB să scrie înainte jurnalul pentru a menține consistența datelor. De facto, structura de stocare a datelor pe disc, descrisă mai sus, își asumă simultan funcția. Absența unui jurnal explicit de tranzacții este una dintre caracteristicile LMDB, care oferă viteză mare de citire a datelor
Construcția rezultată, numită arbore B numai pentru adăugare, oferă în mod natural izolarea tranzacțiilor și multiversiune. În LMDB, fiecare tranzacție deschisă are asociată o rădăcină de arbore actualizată. Atâta timp cât tranzacția nu este finalizată, paginile arborelui asociat cu aceasta nu vor fi niciodată modificate sau reutilizate pentru versiuni noi de date. Astfel, puteți lucra atât timp cât doriți exact cu setul de date care a fost relevant la momentul în care tranzacția a fost deschisă, chiar dacă stocarea continuă să fie actualizată activ în acest moment. Aceasta este esența multiversiunii, făcând din LMDB o sursă de date ideală pentru iubitul nostru UICollectionView. După ce ați deschis o tranzacție, nu trebuie să creșteți amprenta de memorie a aplicației, pompând în grabă datele curente într-o structură în memorie, temându-vă să nu rămâneți fără nimic. Această caracteristică distinge LMDB de același SQLite, care nu se poate lăuda cu o astfel de izolare totală. După deschiderea a două tranzacții în acesta din urmă și ștergerea unei anumite înregistrări în cadrul uneia dintre ele, aceeași înregistrare nu mai poate fi obținută în a doua înregistrare rămasă.
Reversul monedei este consumul potențial semnificativ mai mare de memorie virtuală. Slide-ul arată cum va arăta structura bazei de date dacă este modificată în același timp cu 3 tranzacții de citire deschise uitându-se la diferite versiuni ale bazei de date. Deoarece LMDB nu poate reutiliza nodurile care sunt accesibile de la rădăcinile asociate cu tranzacțiile reale, stocarea nu are de ales decât să aloce o a patra rădăcină în memorie și să cloneze din nou paginile modificate de sub ea.
Aici nu va fi de prisos să amintim secțiunea despre fișierele mapate în memorie. Se pare că consumul suplimentar de memorie virtuală nu ar trebui să ne deranjeze prea mult, întrucât nu contribuie la amprenta de memorie a aplicației. Totuși, în același timp, s-a remarcat că iOS este foarte zgârcit în a-l aloca și nu putem oferi o regiune LMDB de 1 terabyte pe un server sau desktop de pe umărul maestrului și să nu ne gândim deloc la această caracteristică. Atunci când este posibil, ar trebui să încercați să mențineți durata de viață a tranzacțiilor cât mai scurtă posibil.
4. Proiectarea unei scheme de date deasupra API-ului cheie-valoare
Să începem să analizăm API-ul analizând abstracțiile de bază oferite de LMDB: mediu și baze de date, chei și valori, tranzacții și cursore.
O notă despre listele de coduri
Toate funcțiile din API-ul public LMDB returnează rezultatul muncii lor sub forma unui cod de eroare, dar în toate listele ulterioare verificarea sa este omisă din motive de concizie. În practică, am folosit propriul nostru cod pentru a interacționa cu depozitul. Învelișuri C++ , în care erorile se materializează ca excepții C++.
Ca cea mai rapidă modalitate de a conecta LMDB la un proiect iOS sau macOS, ofer CocoaPod-ul meu .
4.1. Abstracții de bază
Mediu inconjurator
Structura MDB_env este depozitul stării interne a LMDB. Familie de funcții prefixate mdb_env vă permite să configurați unele dintre proprietățile sale. În cel mai simplu caz, inițializarea motorului arată așa.
mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512)
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);În aplicația Mail.ru Cloud, am schimbat valorile implicite pentru doar doi parametri.
Prima este dimensiunea spațiului de adrese virtuale la care este mapat fișierul de stocare. Din păcate, chiar și pe același dispozitiv, valoarea specifică poate varia semnificativ de la o rulare la alta. Pentru a ține cont de această caracteristică a iOS, selectăm dinamic cantitatea maximă de stocare. Pornind de la o anumită valoare, se înjumătăţeşte succesiv până la funcţia mdb_env_open nu va returna un alt rezultat decât ENOMEM. În teorie, există o cale opusă - mai întâi alocați un minim de memorie motorului și apoi, atunci când sunt primite erori MDB_MAP_FULL, mărește-l. Cu toate acestea, este mult mai spinos. Motivul este că procedura de remapare a memoriei utilizând funcția mdb_env_set_map_size invalidează toate entitățile (cursori, tranzacții, chei și valori) primite de la motor anterior. Luarea în considerare a unei astfel de schimbări în cod va duce la o complicație semnificativă a acesteia. Dacă, totuși, memoria virtuală îți este foarte dragă, atunci acesta poate fi un motiv pentru a te uita la furculița care a mers mult înainte. , unde printre caracteristicile declarate se numără „ajustarea automată a dimensiunii bazei de date din mers”.
Al doilea parametru, a cărui valoare implicită nu ni se potrivea, reglează mecanica asigurării siguranței firului. Din păcate, cel puțin în iOS 10, există probleme cu suportul pentru stocarea locală a firelor. Din acest motiv, în exemplul de mai sus, depozitul este deschis cu steag MDB_NOTLS. În plus, a cerut și Wrapper C++ pentru a tăia variabile cu și în acest atribut.
Baze de date
Baza de date este o instanță separată a arborelui B despre care am vorbit mai sus. Deschiderea acestuia are loc în interiorul unei tranzacții, care la început poate părea puțin ciudat.
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);Într-adevăr, o tranzacție în LMDB este o entitate de stocare, nu o bază de date specifică. Acest concept vă permite să efectuați operații atomice asupra entităților aflate în diferite baze de date. În teorie, acest lucru deschide posibilitatea modelării tabelelor sub formă de diferite baze de date, dar la un moment dat am mers pe altă cale, descrisă în detaliu mai jos.
Chei și valori
Structura MDB_val modelează atât conceptul de cheie, cât și de valoare. Depozitul nu are idee despre semantica lor. Pentru ea, ceva care este diferit este doar o matrice de octeți de o dimensiune dată. Dimensiunea maximă a cheii este de 512 octeți.
typedef struct MDB_val {
size_t mv_size;
void *mv_data;
} MDB_val;Magazinul folosește un comparator pentru a sorta cheile în ordine crescătoare. Dacă nu îl înlocuiți cu al dvs., atunci va fi folosit cel implicit, care le sortează octet cu octet în ordine lexicografică.
Tranzacție
Dispozitivul de tranzacție este descris în detaliu în , așa că aici voi repeta proprietățile lor principale într-un scurt rând:
- Suport pentru toate proprietățile de bază Cuvinte cheie: atomicitate, consistență, izolare și fiabilitate. Nu pot să nu remarc că în ceea ce privește durabilitatea pe macOS și iOS există o eroare remediată în MDBX. Puteți citi mai multe în lor .
- Abordarea multithreading-ului este descrisă de schema „single writer / multiple readers”. Scriitorii se blochează reciproc, dar nu blochează cititorii. Cititorii nu se blochează pe scriitori sau unii pe alții.
- Suport pentru tranzacții imbricate.
- Suport multiversiune.
Multiversiune în LMDB este atât de bună încât vreau să o demonstrez în acțiune. Codul de mai jos arată că fiecare tranzacție funcționează exact cu versiunea bazei de date care era relevantă la momentul deschiderii acesteia, fiind complet izolată de toate modificările ulterioare. Inițializarea depozitului și adăugarea unei înregistrări de testare nu prezintă niciun interes, așa că aceste ritualuri sunt lăsate sub spoiler.
Adăugarea unei intrări de test
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);Opțional, recomand să încercați același truc cu SQLite și să vedeți ce se întâmplă.
Multiversioning aduce beneficii foarte frumoase vieții unui dezvoltator iOS. Folosind această proprietate, puteți ajusta cu ușurință și în mod natural rata de actualizare a sursei de date pentru formularele de ecran, pe baza considerentelor experienței utilizatorului. De exemplu, să luăm o astfel de caracteristică a aplicației Mail.ru Cloud ca încărcarea automată a conținutului din galeria media a sistemului. Cu o conexiune bună, clientul poate adăuga mai multe fotografii pe secundă pe server. Dacă actualizați după fiecare descărcare UICollectionView cu conținut media în cloud-ul utilizatorului, puteți uita aproximativ 60 de fps și derulare lină în timpul acestui proces. Pentru a preveni actualizările frecvente ale ecranului, trebuie să limitați cumva rata de modificare a datelor în bază UICollectionViewDataSource.
Dacă baza de date nu acceptă multiversiune și vă permite să lucrați numai cu starea curentă curentă, atunci pentru a crea un instantaneu de date stabil în timp, trebuie să îl copiați fie într-o structură de date în memorie, fie într-un tabel temporar. Oricare dintre aceste abordări este foarte costisitoare. În cazul stocării în memorie, obținem atât costurile de memorie cauzate de stocarea obiectelor construite, cât și costurile de timp asociate transformărilor ORM redundante. În ceea ce privește masa temporară, aceasta este o plăcere și mai scumpă, care are sens doar în cazuri non-triviale.
Multiversioning LMDB rezolvă problema menținerii unei surse de date stabile într-un mod foarte elegant. Este suficient doar să deschidem o tranzacție și voila - până când o completăm, setul de date este garantat a fi reparat. Logica ratei sale de actualizare este acum în întregime în mâinile stratului de prezentare, fără suprasolicitare a resurselor semnificative.
Cursore
Cursoarele oferă un mecanism de iterație ordonată peste perechi cheie-valoare prin parcurgerea unui arbore B. Fără ele, ar fi imposibil să modelăm eficient tabelele din baza de date, la care ne referim acum.
4.2. Modelarea tabelului
Proprietatea de ordonare a cheilor vă permite să construiți o abstracție de nivel superior, cum ar fi un tabel peste abstracțiile de bază. Să luăm în considerare acest proces pe exemplul tabelului principal al clientului cloud, în care sunt stocate în cache informații despre toate fișierele și folderele utilizatorului.
Schema tabelului
Unul dintre scenariile comune pentru care structura unui tabel cu un arbore de foldere ar trebui să fie clarificată este selectarea tuturor elementelor aflate în interiorul unui director dat.Un model bun de organizare a datelor pentru interogări eficiente de acest fel este . Pentru a o implementa peste stocarea cheie-valoare, este necesar să sortați cheile fișierelor și folderelor în așa fel încât acestea să fie grupate în funcție de apartenența la directorul părinte. În plus, pentru a afișa conținutul directorului în forma familiară unui utilizator Windows (mai întâi folderele, apoi fișierele, ambele sunt sortate alfabetic), este necesar să includeți câmpurile suplimentare corespunzătoare în cheie.
Imaginea de mai jos arată cum poate arăta, pe baza sarcinii, reprezentarea cheilor ca o matrice de octeți. Mai întâi sunt plasați octeții cu identificatorul directorului părinte (roșu), apoi cu tipul (verde), iar deja în coadă cu numele (albastru).Fiind sortați după comparatorul LMDB implicit în ordine lexicografică, aceștia sunt ordonați în modul cerut. Parcurgerea secvențială a tastelor cu același prefix roșu ne oferă valorile asociate acestora în ordinea în care ar trebui să fie afișate în interfața cu utilizatorul (dreapta), fără a necesita nicio post-procesare suplimentară.
Serializarea cheilor și valorilor
Există multe metode pentru serializarea obiectelor în întreaga lume. Deoarece nu aveam altă cerință decât viteza, am ales-o pe cea mai rapidă posibilă pentru noi înșine - un dump de memorie ocupat de o instanță a structurii limbajului C. Deci, cheia unui element de director poate fi modelată de următoarea structură NodeKey.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;A salva NodeKey în nevoie de depozitare în obiect MDB_val poziționați indicatorul către date la adresa începutului structurii și calculați dimensiunea acestora cu funcția sizeof.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = sizeof(NodeKey),
.mv_data = (void *)key
};
}În primul capitol despre criteriile de selecție a bazei de date, am menționat minimizarea alocărilor dinamice ca parte a operațiunilor CRUD ca un factor de selecție important. Codul funcției serialize arată cum, în cazul LMDB, acestea pot fi complet evitate atunci când sunt introduse noi înregistrări în baza de date. Matricea de octeți primită de la server este mai întâi transformată în structuri de stivă, apoi sunt aruncate trivial în stocare. Având în vedere că, de asemenea, nu există alocări dinamice în interiorul LMDB, puteți obține o situație fantastică conform standardelor iOS - utilizați doar memoria stivă pentru a lucra cu date de la rețea la disc!
Comandarea cheilor cu un comparator binar
Relația de ordine a cheilor este dată de o funcție specială numită comparator. Întrucât motorul nu știe nimic despre semantica octeților pe care îi conțin, comparatorul implicit nu are de ales decât să aranjeze cheile în ordine lexicografică, recurgând la comparația lor octet cu octet. Folosirea lui pentru a aranja structuri este asemănătoare cu bărbierirea cu un topor de sculptat. Cu toate acestea, în cazuri simple, găsesc această metodă acceptabilă. Alternativa este descrisă mai jos, dar aici voi nota câteva greble împrăștiate pe parcurs.
Primul lucru de reținut este reprezentarea în memorie a tipurilor de date primitive. Deci, pe toate dispozitivele Apple, variabilele întregi sunt stocate în format . Aceasta înseamnă că octetul cel mai puțin semnificativ va fi în stânga și nu veți putea sorta numerele întregi folosind comparația lor octet cu octet. De exemplu, încercarea de a face acest lucru cu un set de numere de la 0 la 511 va avea ca rezultat următorul rezultat.
// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)Pentru a rezolva această problemă, numerele întregi trebuie stocate în cheie într-un format potrivit pentru comparatorul de octeți. Funcțiile din familie vor ajuta la realizarea transformării necesare. hton* (în special htons pentru numere pe doi octeți din exemplu).
Formatul de reprezentare a șirurilor în programare este, după cum știți, un întreg . Dacă semantica șirurilor, precum și codificarea folosită pentru a le reprezenta în memorie, sugerează că poate exista mai mult de un octet pe caracter, atunci este mai bine să renunțați imediat la ideea de a folosi un comparator implicit.
Al doilea lucru de reținut este compilator de câmpuri struct. Datorită acestora, octeții cu valori de gunoi pot fi formați în memorie între câmpuri, ceea ce, desigur, întrerupe sortarea octeților. Pentru a elimina gunoiul, trebuie fie să declarați câmpurile într-o ordine strict definită, ținând cont de regulile de aliniere, fie să utilizați atributul în declarația structurii packed.
Comandarea cheilor de către un comparator extern
Logica de comparare a cheilor se poate dovedi a fi prea complexă pentru un comparator binar. Unul dintre numeroasele motive este prezența câmpurilor tehnice în interiorul structurilor. Voi ilustra apariția lor pe exemplul unei chei deja familiare pentru un element de director.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Cu toată simplitatea sa, în marea majoritate a cazurilor consumă prea multă memorie. Bufferul de titlu este de 256 de octeți, deși, în medie, numele fișierelor și folderelor depășesc rar 20-30 de caractere.
Una dintre tehnicile standard de optimizare a dimensiunii unei înregistrări este „decuparea” acesteia pentru a se potrivi cu dimensiunea reală. Esența sa este că conținutul tuturor câmpurilor cu lungime variabilă este stocat într-un buffer la sfârșitul structurii, iar lungimile lor sunt stocate în variabile separate.În conformitate cu această abordare, cheia NodeKey se transformă în felul următor.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;În plus, în timpul serializării, nu este specificată ca dimensiune a datelor sizeof întreaga structură, iar dimensiunea tuturor câmpurilor este lungime fixă plus dimensiunea părții utilizate efectiv din buffer.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
.mv_data = (void *)key
};
}Ca urmare a refactorizării, am obținut o economie semnificativă în spațiul ocupat de chei. Cu toate acestea, din cauza domeniului tehnic nameLength, comparatorul binar implicit nu mai este potrivit pentru compararea cheilor. Dacă nu îl înlocuim cu al nostru, atunci lungimea numelui va fi un factor mai prioritar în sortare decât numele în sine.
LMDB permite fiecărei baze de date să aibă propria funcție de comparare a cheilor. Acest lucru se face folosind funcția mdb_set_compare strict înainte de deschidere. Din motive evidente, o bază de date nu poate fi modificată pe toată durata de viață. La intrare, comparatorul primește două chei în format binar, iar la ieșire returnează rezultatul comparației: mai mic decât (-1), mai mare decât (1) sau egal (0). Pseudocod pentru NodeKey arata asa.
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 // ...
}Atâta timp cât toate cheile din baza de date sunt de același tip, este legal să aruncați necondiționat reprezentarea lor de octeți în tipul structurii aplicației cheii. Există o nuanță aici, dar va fi discutată puțin mai jos în subsecțiunea „Reading Records”.
Serializarea valorii
Cu cheile înregistrărilor stocate, LMDB lucrează extrem de intens. Ele sunt comparate între ele în cadrul oricărei operațiuni de aplicație, iar performanța întregii soluții depinde de viteza comparatorului. Într-o lume ideală, comparatorul binar implicit ar trebui să fie suficient pentru a compara cheile, dar dacă chiar a trebuit să le folosești pe ale tale, atunci procedura de deserializare a cheilor din el ar trebui să fie cât mai rapidă posibil.
Baza de date nu este interesată în mod deosebit de partea Valoare a înregistrării (valoare). Conversia sa dintr-o reprezentare de octeți într-un obiect are loc numai atunci când este deja solicitat de codul aplicației, de exemplu, pentru a-l afișa pe ecran. Deoarece acest lucru se întâmplă relativ rar, cerințele pentru viteza acestei proceduri nu sunt atât de critice, iar în implementarea ei suntem mult mai liberi să ne concentrăm pe comoditate. De exemplu, pentru a serializa metadatele despre fișierele care nu au fost încă descărcate, folosim NSKeyedArchiver.
NSData *data = serialize(object);
MDB_val value = {
.mv_size = data.length,
.mv_data = (void *)data.bytes
};Cu toate acestea, există momente în care performanța contează. De exemplu, atunci când salvăm metainformații despre structura fișierelor din cloudul utilizatorului, folosim același dump de memorie obiect. Punctul culminant al sarcinii de generare a reprezentării lor serializate este faptul că elementele unui director sunt modelate de o ierarhie de clasă.
Pentru implementarea lui în limbajul C, câmpurile specifice moștenitorilor sunt scoase în structuri separate, iar legătura lor cu cea de bază se precizează printr-un câmp de tip uniune. Conținutul real al uniunii este specificat prin intermediul atributului tehnic tip.
typedef struct NodeValue {
EntityId localId;
EntityType type;
union {
FileInfo file;
DirectoryInfo directory;
} info;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeValue;Adăugarea și actualizarea înregistrărilor
Cheia și valoarea serializate pot fi adăugate în magazin. Pentru aceasta se folosește funcția mdb_put.
// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);În etapa de configurare, depozitului poate fi permis sau interzis să stocheze mai multe înregistrări cu aceeași cheie. Dacă duplicarea cheilor este interzisă, atunci când inserați o înregistrare, puteți determina dacă actualizarea unei înregistrări deja existente este permisă sau nu. Dacă uzura poate apărea doar ca urmare a unei erori în cod, atunci vă puteți asigura împotriva acesteia specificând steag-ul NOOVERWRITE.
Citirea înregistrărilor
Funcția de citire a înregistrărilor în LMDB este mdb_get. Dacă perechea cheie-valoare este reprezentată de structuri de dumping anterior, atunci această procedură arată astfel.
NodeValue * const readNode(..., NodeKey * const key) {
MDB_val rawKey = serialize(key);
MDB_val rawValue;
mdb_get(..., &rawKey, &rawValue);
return (NodeValue * const)rawValue.mv_data;
}Lista prezentată arată cum serializarea printr-un dump de structuri vă permite să scăpați de alocările dinamice nu numai când scrieți, ci și când citiți date. Derivat din funcție mdb_get pointerul se uită exact la adresa memoriei virtuale unde baza de date stochează reprezentarea în octeți a obiectului. De fapt, obținem un fel de ORM, aproape gratuit, oferind o viteză foarte mare de citire a datelor. Cu toată frumusețea abordării, este necesar să ne amintim mai multe caracteristici asociate cu aceasta.
- Pentru o tranzacție numai în citire, un pointer către o structură de valori este garantat să rămână valabil doar până când tranzacția este închisă. După cum s-a menționat mai devreme, paginile arborelui B pe care se află obiectul, datorită principiului copy-on-write, rămân neschimbate atâta timp cât cel puțin o tranzacție se referă la ele. În același timp, de îndată ce ultima tranzacție asociată acestora este finalizată, paginile pot fi refolosite pentru date noi. Dacă este necesar ca obiectele să supraviețuiască tranzacției care le-a creat, atunci acestea trebuie totuși copiate.
- Pentru o tranzacție de rescriere, indicatorul către structura-valoare rezultată va fi valabil doar până la prima procedură de modificare (scrierea sau ștergerea datelor).
- Chiar dacă structura
NodeValuenu complet, ci decupat (vezi subsecțiunea „Comandarea cheilor de către un comparator extern”), prin indicator, puteți accesa cu ușurință câmpurile acestuia. Principalul lucru este să nu-l dereferiți! - În niciun caz nu puteți modifica structura prin indicatorul primit. Toate modificările trebuie făcute numai prin metoda
mdb_put. Cu toate acestea, cu toată dorința de a face acest lucru, nu va funcționa, deoarece zona de memorie în care se află această structură este mapată în modul doar citire. - Remapează un fișier la spațiul de adrese al unui proces pentru, de exemplu, a crește dimensiunea maximă de stocare folosind funcția
mdb_env_set_map_sizeinvalidează complet toate tranzacțiile și entitățile aferente în general și indicatorii pentru a citi obiectele în special.
În cele din urmă, încă o caracteristică este atât de insidioasă încât dezvăluirea esenței sale nu se încadrează doar într-un singur punct. În capitolul despre arborele B, am dat o diagramă a organizării paginilor sale în memorie. Din aceasta rezultă că adresa începutului buffer-ului cu date serializate poate fi absolut arbitrară. Din această cauză, indicatorul către ele, obținut în structură MDB_val iar turnarea către un pointer către o structură este în general nealiniată. În același timp, arhitecturile unor cipuri (în cazul iOS, acesta este armv7) necesită ca adresa oricăror date să fie un multiplu al mărimii unui cuvânt de mașină sau, cu alte cuvinte, bitness-ul sistemului (pentru armv7, acesta este 32 de biți). Cu alte cuvinte, o operațiune de genul *(int *foo)0x800002 asupra lor este echivalată cu evadarea și duce la executare cu un verdict EXC_ARM_DA_ALIGN. Există două moduri de a evita o soartă atât de tristă.
Prima este să copiați în prealabil datele într-o structură aliniată cunoscută. De exemplu, pe un comparator personalizat, acest lucru se va reflecta după cum urmează.
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 // ...
}O modalitate alternativă este de a notifica în avans compilatorului că structurile cu o cheie și o valoare nu pot fi aliniate folosind un atribut aligned(1). Pe ARM același efect poate fi și folosind atributul packed. Avand in vedere ca contribuie si la optimizarea spatiului ocupat de structura, aceasta metoda mi se pare de preferat, desi pentru a crește costul operațiunilor de acces la date.
typedef struct __attribute__((packed)) NodeKey {
uint8_t parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Interogări de interval
Pentru a itera peste un grup de înregistrări, LMDB oferă o abstractizare a cursorului. Să ne uităm la cum să lucrăm cu acesta folosind exemplul unui tabel cu metadate de utilizator cloud deja familiare.
Ca parte a afișării unei liste de fișiere dintr-un director, trebuie să găsiți toate cheile cu care sunt asociate fișierele și folderele sale secundare. În subsecțiunile anterioare, am sortat cheile NodeKey astfel încât acestea să fie mai întâi ordonate după ID-ul directorului părinte. Astfel, din punct de vedere tehnic, sarcina de a obține conținutul unui folder se reduce la plasarea cursorului pe granița superioară a unui grup de chei cu un prefix dat, urmată de iterație până la limita inferioară.
Puteți găsi limita superioară „pe frunte” prin căutare secvențială. Pentru a face acest lucru, cursorul este plasat la începutul întregii liste de chei din baza de date și apoi este incrementat până când cheia cu identificatorul directorului părinte apare sub ea. Această abordare are 2 dezavantaje evidente:
- Complexitatea liniară a căutării, deși, după cum știți, în copaci în general și într-un arbore B în special, se poate face în timp logaritmic.
- Degeaba, toate paginile premergătoare celei dorite sunt ridicate din fișier în memoria principală, ceea ce este extrem de costisitor.
Din fericire, API-ul LMDB oferă o modalitate eficientă de a poziționa inițial cursorul. Pentru a face acest lucru, trebuie să formați o astfel de cheie, a cărei valoare va fi cu siguranță mai mică sau egală cu cheia situată pe limita superioară a intervalului. . De exemplu, în raport cu lista din figura de mai sus, putem face o cheie în care câmpul parentId va fi egal cu 2, iar restul sunt umplute cu zerouri. O astfel de cheie parțial completată este alimentată la intrarea funcției mdb_cursor_get indicând funcționarea 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);Dacă este găsită limita superioară a grupului de chei, atunci repetăm peste ea până când ne întâlnim sau cheia cu alta parentId, sau cheile nu se vor epuiza deloc.
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 groupCe este frumos, ca parte a iterației folosind mdb_cursor_get, obținem nu numai cheia, ci și valoarea. Dacă, pentru a îndeplini condițiile de selecție, este necesar să se verifice, printre altele, câmpurile din partea de valoare a înregistrării, atunci acestea sunt destul de accesibile pentru ei înșiși fără gesturi suplimentare.
4.3. Modelarea relațiilor dintre tabele
Până în prezent, am reușit să luăm în considerare toate aspectele legate de proiectarea și lucrul cu o bază de date cu un singur tabel. Putem spune că un tabel este un set de înregistrări sortate format din perechi cheie-valoare de același tip. Dacă afișați o cheie ca dreptunghi și valoarea ei asociată ca o casetă, obțineți o diagramă vizuală a bazei de date.
Cu toate acestea, în viața reală, rareori este posibil să te descurci cu atât de puțin sânge. Adesea, într-o bază de date este necesar, în primul rând, să aibă mai multe tabele și, în al doilea rând, să se efectueze selecții în ele într-o ordine diferită de cheia primară. Această ultimă secțiune este dedicată problemelor de creare și interconectare a acestora.
Tabelele indexate
Aplicația cloud are o secțiune „Galerie”. Afișează conținut media din întregul nor, sortat după dată. Pentru implementarea optimă a unei astfel de selecții, lângă tabelul principal, trebuie să creați altul cu un nou tip de chei. Acestea vor conține un câmp cu data la care a fost creat fișierul, care va acționa ca criteriu principal de sortare. Deoarece noile chei se referă la aceleași date ca și cheile din tabelul de bază, ele sunt numite chei de index. Sunt evidențiate cu portocaliu în imaginea de mai jos.
Pentru a separa cheile diferitelor tabele unele de altele în cadrul aceleiași baze de date, a fost adăugat un câmp tehnic tableId suplimentar tuturor acestora. Făcându-l cea mai mare prioritate pentru sortare, vom grupa cheile mai întâi pe tabele și deja în interiorul tabelelor - conform propriilor noastre reguli.
Cheia index se referă la aceleași date ca și cheia primară. Implementarea simplă a acestei proprietăți prin asocierea cu ea a unei copii a părții valorice a cheii primare este suboptimă din mai multe puncte de vedere simultan:
- Din punct de vedere al spațiului ocupat, metadatele pot fi destul de bogate.
- Din punct de vedere al performanței, deoarece la actualizarea metadatelor nodului, va trebui să suprascrieți două chei.
- Din punct de vedere al suportului de cod, la urma urmei, dacă uităm să actualizăm datele pentru una dintre chei, vom obține un bug subtil de inconsecvență a datelor în stocare.
În continuare, vom analiza cum să eliminăm aceste deficiențe.
Organizarea relațiilor dintre tabele
Modelul este potrivit pentru a lega un tabel index cu cel principal "cheie ca valoare". După cum sugerează și numele, partea de valoare a înregistrării index este o copie a valorii cheii primare. Această abordare elimină toate dezavantajele enumerate mai sus asociate cu stocarea unei copii a părții valorice a înregistrării primare. Singura taxă este că pentru a obține valoarea prin cheia de index, trebuie să faceți 2 interogări la baza de date în loc de una. Schematic, schema bazei de date rezultată este după cum urmează.
Un alt model de organizare a relațiilor dintre tabele este "cheie redundanta". Esența sa este de a adăuga atribute suplimentare la cheie, care sunt necesare nu pentru sortare, ci pentru recrearea cheii asociate.Există exemple reale de utilizare a acesteia în aplicația Mail.ru Cloud, totuși, pentru a evita scufundarea profundă în contextul cadrelor iOS specifice, voi da un exemplu fictiv, dar mai ușor de înțeles.
Clienții mobile cloud au o pagină care afișează toate fișierele și folderele pe care utilizatorul le-a partajat altor persoane. Deoarece există relativ puține astfel de fișiere și există o mulțime de informații specifice despre publicitatea asociată cu ele (cui i se acordă accesul, cu ce drepturi etc.), nu va fi rațional să-i împovărăm cu partea de valoare a înregistrarea din tabelul principal. Cu toate acestea, dacă doriți să afișați astfel de fișiere offline, atunci trebuie totuși să le stocați undeva. O soluție naturală este să creați o masă separată pentru aceasta. În diagrama de mai jos, cheia este prefixată cu „P”, iar substituentul „propname” poate fi înlocuit cu valoarea mai specifică „public info”.
Toate metadatele unice, de dragul cărora a fost creat noul tabel, sunt mutate în partea de valoare a înregistrării. În același timp, nu vreau să dublez datele despre fișierele și folderele care sunt deja stocate în tabelul principal. În schimb, datele redundante sunt adăugate la cheia „P” sub forma câmpurilor „ID nod” și „marca temporală”. Datorită acestora, puteți construi o cheie index, prin care puteți obține cheia primară, prin care, în sfârșit, puteți obține metadatele nodului.
Concluzie
Evaluăm pozitiv rezultatele implementării LMDB. După aceasta, numărul de înghețari a aplicațiilor a scăzut cu 30%.
Rezultatele muncii depuse au găsit un răspuns în afara echipei iOS. În prezent, una dintre principalele secțiuni „Fișiere” din aplicația Android a trecut și la utilizarea LMDB, iar alte părți sunt pe drum. Limbajul C, în care este implementată stocarea cheie-valoare, a fost un ajutor bun pentru a face inițial legarea aplicației în jurul ei pe mai multe platforme în limbajul C++. Pentru o conexiune perfectă a bibliotecii C++ rezultate cu codul platformei în Objective-C și Kotlin, a fost folosit un generator de cod. din Dropbox, dar asta e altă poveste.
Sursa: www.habr.com