ProHoster > Blogs > Administrācija > Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

2019. gada rudenÄ« Mail.ru Cloud iOS komandā notika ilgi gaidÄ«ts notikums. Galvenā datu bāze pastāvÄ«gai lietojumprogrammu stāvokļa glabāŔanai ir kļuvusi diezgan eksotiska mobilajā pasaulē Zibens atmiņas kartēta datu bāze (LMDB). Zem griezuma jÅ«su uzmanÄ«ba tiek aicināta uz tā detalizētu apskatu četrās daļās. Pirmkārt, parunāsim par Ŕādas nenozÄ«mÄ«gas un sarežģītas izvēles iemesliem. Pēc tam pāriesim pie apsvērumiem par trim vaļiem, kas ir LMDB arhitektÅ«ras pamatā: ar atmiņu saistÄ«ti faili, B + koks, kopÄ“Å”anas un rakstÄ«Å”anas pieeja transakciju un vairāku versiju ievieÅ”anai. Visbeidzot, desertā - praktiskā daļa. Tajā mēs apskatÄ«sim, kā izveidot un ieviest bāzes shēmu ar vairākām tabulām, tostarp indeksu, papildus zema lÄ«meņa atslēgas vērtÄ«bas API.ā€‹

saturs

  1. ÄŖstenoÅ”anas motivācija
  2. LMDB pozicionēŔana
  3. Trīs vaļi LMDB
    3.1. Valis #1. Atmiņas kartētie faili
    3.2. Valis #2. B+-koks
    3.3. Valis #3. kopēŔana uz rakstīŔanas
  4. Datu shēmas izstrāde virs atslēgas vērtības API
    4.1. Pamata abstrakcijas
    4.2. Tabulu modelēŔana
    4.3. SakarÄ«bu modelÄ“Å”ana starp tabulām

1. ÄŖstenoÅ”anas motivācija

Reizi gadā, 2015. gadā, mēs parÅ«pējāmies par metriku, cik bieži mÅ«su lietojumprogrammas saskarne kavējas. Mēs ne tikai to izdarÄ«jām. Arvien biežāk mums ir sÅ«dzÄ«bas par to, ka dažkārt aplikācija pārstāj reaģēt uz lietotāja darbÄ«bām: netiek nospiestas pogas, netiek ritināti saraksti utt. Par mērÄ«jumu mehāniku stāstÄ«ja uz AvitoTech, tāpēc Å”eit es sniedzu tikai skaitļu secÄ«bu.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

MērÄ«jumu rezultāti mums kļuva par aukstu duÅ”u. IzrādÄ«jās, ka sasalÅ”anas radÄ«to problēmu ir daudz vairāk nekā jebkuras citas. Ja pirms Ŕī fakta apzināŔanās galvenais kvalitātes tehniskais rādÄ«tājs bija bez avārijām, tad pēc fokusa nobÄ«dÄ«ts bez iesaldÄ“Å”anas.

BÅ«vējis informācijas panelis ar sasalÅ”anu un iztērējis kvantitatÄ«vi Šø kvalitāte Analizējot to cēloņus, kļuva skaidrs galvenais ienaidnieks - smaga biznesa loÄ£ika, kas tiek izpildÄ«ta lietojumprogrammas galvenajā pavedienā. Dabiska reakcija uz Å”o apkaunojumu bija kvēla vēlme to iegrÅ«st darba plÅ«smās. Lai sistemātiski atrisinātu Å”o problēmu, mēs izmantojām daudzpavedienu arhitektÅ«ru, kuras pamatā ir vieglie aktieri. Es veltÄ«ju viņas pielāgojumus iOS pasaulei divi pavedieni kolektÄ«vā twitter un raksts par Habrē. Kā daļu no paÅ”reizējā stāsta es vēlos uzsvērt tos lēmuma aspektus, kas ietekmēja datu bāzes izvēli

Sistēmas organizācijas aktiera modelis pieņem, ka daudzpavedienu veidoÅ”ana kļūst par tā otro bÅ«tÄ«bu. Modeļa objektiem tajā patÄ«k Ŕķērsot pavedienu robežas. Un viņi to dara nevis dažreiz un dažviet, bet gandrÄ«z pastāvÄ«gi un visur.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Datubāze ir viens no stÅ«rakmens komponentiem parādÄ«tajā diagrammā. Tās galvenais uzdevums ir ieviest makro modeli Koplietota datu bāze. Ja uzņēmumu pasaulē to izmanto, lai organizētu datu sinhronizāciju starp pakalpojumiem, tad actor arhitektÅ«ras gadÄ«jumā dati starp pavedieniem. LÄ«dz ar to mums bija nepiecieÅ”ama tāda datu bāze, ar kuru darbs daudzpavedienu vidē nesagādā pat minimālas grÅ«tÄ«bas. Jo Ä«paÅ”i tas nozÄ«mē, ka no tā iegÅ«tajiem objektiem jābÅ«t vismaz pavedieniem droÅ”iem un ideālā gadÄ«jumā vispār nav maināmiem. Kā jÅ«s zināt, pēdējo var izmantot vienlaikus no vairākiem pavedieniem, neizmantojot nekādas slēdzenes, kas labvēlÄ«gi ietekmē veiktspēju.

Atslēgu vērtÄ«bu datu bāzes LMDB spožums un nabadzÄ«ba iOS lietojumprogrammāsOtrs nozÄ«mÄ«gais faktors, kas ietekmēja datu bāzes izvēli, bija mÅ«su mākoņa API. To iedvesmoja git pieeja sinhronizācijai. Tāpat kā viņu mēs mērķējām pirmā bezsaistes API, kas izskatās vairāk nekā piemērots mākoņu klientiem. Tika pieņemts, ka tie tikai vienu reizi izsÅ«knēs pilnu mākoņa stāvokli, un pēc tam vairumā gadÄ«jumu sinhronizācija notiks, veicot izmaiņas. Diemžēl Ŕī iespēja joprojām ir tikai teorētiskajā zonā, un praksē klienti nav iemācÄ«juÅ”ies strādāt ar ielāpiem. Tam ir vairāki objektÄ«vi iemesli, kurus, lai neaizkavētu ievadu, mēs atstāsim iekavās. Tagad daudz interesantāki ir nodarbÄ«bas pamācoÅ”ie rezultāti par to, kas notiek, kad API saka "A" un tā patērētājs neteica "B".

Tātad, ja jÅ«s iedomājaties git, kas, izpildot vilkÅ”anas komandu, tā vietā, lai lietotu ielāpus vietējam momentuzņēmumam, salÄ«dzina savu pilno stāvokli ar pilna servera stāvokli, tad jums bÅ«s diezgan precÄ«zs priekÅ”stats par sinhronizāciju. notiek mākoņa klientiem. Ir viegli uzminēt, ka tā ievieÅ”anai ir nepiecieÅ”ams atmiņā pieŔķirt divus DOM kokus ar metainformāciju par visiem serveriem un vietējiem failiem. Izrādās, ja lietotājs mākonÄ« glabā 500 tÅ«kstoÅ”us failu, tad, lai to sinhronizētu, ir nepiecieÅ”ams no jauna izveidot un iznÄ«cināt divus kokus ar 1 miljonu mezglu. Bet katrs mezgls ir kopums, kas satur apakÅ”objektu grafiku. Ņemot to vērā, tika gaidÄ«ti profilÄ“Å”anas rezultāti. IzrādÄ«jās, ka pat neņemot vērā sapludināŔanas algoritmu, pati procedÅ«ra, kā izveidot un pēc tam iznÄ«cināt milzÄ«gu skaitu mazu objektu, maksā diezgan santÄ«mu.Situāciju pasliktina fakts, ka sinhronizācijas pamatoperācija ir iekļauta lielā skaitā. lietotāju skripti. Rezultātā tiek fiksēts otrs svarÄ«gais kritērijs datu bāzes izvēlē - iespēja realizēt CRUD darbÄ«bas bez dinamiskas objektu pieŔķirÅ”anas.

Citas prasības ir tradicionālākas, un to pilns saraksts ir Ŕāds.

  1. Vītnes droŔība.
  2. Daudzkārtēja apstrāde. To noteica vēlme izmantot vienu un to paÅ”u datu bāzes gadÄ«jumu, lai sinhronizētu stāvokli ne tikai starp pavedieniem, bet arÄ« starp galveno lietojumprogrammu un iOS paplaÅ”inājumiem.
  3. Iespēja attēlot saglabātās entītijas kā nemaināmus objektus
  4. Dinamisko pieŔķīrumu trūkums CRUD operācijās.
  5. DarÄ«jumu atbalsts pamata Ä«paÅ”umiem ACIDAtslēgas vārdi: atomitāte, konsistence, izolācija un uzticamÄ«ba.
  6. Ātrums populārākajos gadījumos.

Ar Å”o prasÄ«bu kopumu SQLite bija un joprojām ir laba izvēle. Tomēr alternatÄ«vu izpētes ietvaros es tiku pie grāmatas "Darba sākÅ”ana ar LevelDB". Viņas vadÄ«bā tika uzrakstÄ«ts etalons, kas salÄ«dzina darba ātrumu ar dažādām datu bāzēm reālos mākoņa scenārijos. Rezultāts pārsniedza visdrosmÄ«gākās cerÄ«bas. Vispopulārākajos gadÄ«jumos - kursora iegÅ«Å”ana uz sakārtotu visu failu sarakstu un visu failu sakārtotu sarakstu konkrētam direktorijam - LMDB izrādÄ«jās 10 reizes ātrāks nekā SQLite. Izvēle kļuva acÄ«mredzama.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

2. LMDB pozicionēŔana

LMDB ir bibliotēka, ļoti maza (tikai 10K rindiņas), kas realizē zemāko fundamentālo datu bāzu slāni ā€“ krātuvi.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

IepriekÅ” redzamā diagramma parāda, ka LMDB salÄ«dzināŔana ar SQLite, kas ievieÅ” vēl augstākus lÄ«meņus, parasti nav pareizāka nekā SQLite ar pamatdatiem. GodÄ«gāk bÅ«tu minēt vienus un tos paÅ”us uzglabāŔanas dzinējus kā lÄ«dzvērtÄ«gus konkurentus - BerkeleyDB, LevelDB, Sophia, RocksDB utt. Ir pat izstrādnes, kurās LMDB darbojas kā SQLite uzglabāŔanas dzinēja sastāvdaļa. Pirmais Ŕāds eksperiments 2012. gadā iztērēts autors LMDB Hovards Ču. rezultātus izrādÄ«jās tik intriģējoÅ”a, ka viņa iniciatÄ«vu uztvēra OSS entuziasti un atrada savu turpinājumu, saskaroties ar LumoSQL. 2020. gada janvārÄ« Ŕī projekta autors ir Den Shearer prezentēts to LinuxConfAu.

Galvenais LMDB lietojums ir kā lietojumprogrammu datu bāzu dzinējs. Bibliotēka ir parādā savu izskatu izstrādātājiem OpenLDAP, kuri bija ļoti neapmierināti ar BerkeleyDB kā sava projekta pamatu. StÅ«mÅ”anās prom no pazemÄ«gās bibliotēkas btree, Hovards Ču spēja izveidot vienu no mÅ«su laika populārākajām alternatÄ«vām. Savu ļoti forÅ”o reportāžu viņŔ veltÄ«ja Å”im stāstam, kā arÄ« LMDB iekŔējai struktÅ«rai "zibens atmiņas kartētā datu bāze". LeonÄ«ds Jurijevs (aka yleo) no Positive Technologies savā runā Highload 2015 "LMDB dzinējs ir Ä«paÅ”s čempions". Tajā viņŔ stāsta par LMDB lÄ«dzÄ«ga ReOpenLDAP ievieÅ”anas uzdevuma kontekstā, un LevelDB jau izpelnÄ«jies salÄ«dzinoÅ”o kritiku. IevieÅ”anas rezultātā Positive Technologies ieguva pat aktÄ«vi attÄ«stoÅ”u dakÅ”iņu MDBX ar ļoti garŔīgām funkcijām, optimizācijām un kļūdu labojumi.

LMDB bieži tiek izmantota arÄ« kā krātuve. Piemēram, pārlÅ«kprogramma Mozilla Firefox izvēlējās to vairākām vajadzÄ«bām un, sākot no 9. versijas, Xcode vēlams tā SQLite indeksu glabāŔanai.

Dzinējs iekļuva arÄ« mobilo ierīču izstrādes pasaulē. Var bÅ«t tās lietoÅ”anas pēdas atrast iOS klientā Telegram. LinkedIn gāja soli tālāk un izvēlējās LMDB kā noklusējuma krātuvi savai paÅ”māju datu keÅ”atmiņas sistēmai Rocket Data, par kuru stāstÄ«ja rakstā 2016. gadā.

LMDB veiksmÄ«gi cÄ«nās par vietu saulē BerkeleyDB atstātajā niŔā pēc pārejas Oracle vadÄ«bā. Bibliotēka ir iemīļota tās ātruma un uzticamÄ«bas dēļ, pat salÄ«dzinot ar savu veidu. Kā zināms, brÄ«vpusdienu nav, un vēlos uzsvērt kompromisu, ar kuru nāksies saskarties, izvēloties starp LMDB un SQLite. IepriekÅ” redzamā diagramma skaidri parāda, kā tiek sasniegts palielinātais ātrums. Pirmkārt, mēs nemaksājam par papildu abstrakcijas slāņiem papildus diska krātuvei. Protams, labā arhitektÅ«rā bez tiem joprojām nevar iztikt, un tie neizbēgami parādÄ«sies lietojumprogrammas kodā, taču tie bÅ«s daudz plānāki. Viņiem nebÅ«s funkciju, kas nav nepiecieÅ”amas konkrētai lietojumprogrammai, piemēram, atbalsts vaicājumiem SQL valodā. Otrkārt, kļūst iespējams optimāli ieviest lietojumprogrammu operāciju kartÄ“Å”anu ar pieprasÄ«jumiem uz diska krātuvi. Ja SQLite manā darbā nāk no vidējas lietojumprogrammas vidējām vajadzÄ«bām, tad jÅ«s kā lietojumprogrammu izstrādātājs labi zināt galvenos ielādes scenārijus. Lai iegÅ«tu produktÄ«vāku risinājumu, jums bÅ«s jāmaksā paaugstināta cena gan par sākotnējā risinājuma izstrādi, gan tā turpmāko atbalstu.

3. Trīs vaļi LMDB

Apskatot LMDB no putna lidojuma, laiks iedziļināties. Nākamās trīs sadaļas tiks veltītas galveno vaļu analīzei, uz kuriem balstās uzglabāŔanas arhitektūra:

  1. Atmiņas kartētie faili kā mehānisms darbam ar disku un iekŔējo datu struktÅ«ru sinhronizÄ“Å”anai.
  2. B+-koks kā uzglabāto datu struktūras organizācija.
  3. KopÄ“Å”ana uz rakstÄ«Å”anas kā pieeja ACID darÄ«jumu Ä«paŔību nodroÅ”ināŔanai un vairāku versiju izveidei.

3.1. Valis #1. Atmiņas kartētie faili

Atmiņas kartētie faili ir tik svarÄ«gs arhitektÅ«ras elements, ka tie pat parādās repozitorija nosaukumā. Problēmas ar saglabātās informācijas saglabāŔanu keÅ”atmiņā un piekļuves sinhronizÄ“Å”anu ir pilnÄ«bā atkarÄ«gas no operētājsistēmas. LMDB nesatur keÅ”atmiņas sevÄ«. Tas ir apzināts autora lēmums, jo datu lasÄ«Å”ana tieÅ”i no kartētiem failiem ļauj samazināt dzinēja ievieÅ”anu. Tālāk ir sniegts tālu no pilnÄ«gs dažu no tiem saraksts.

  1. Datu konsekvences uzturÄ“Å”ana krātuvē, strādājot ar tiem no vairākiem procesiem, kļūst par operētājsistēmas atbildÄ«bu. Nākamajā sadaļā Å”is mehāniÄ·is ir detalizēti un ar attēliem apspriests.
  2. KeÅ”atmiņas trÅ«kums pilnÄ«bā atbrÄ«vo LMDB no pieskaitāmajām izmaksām, kas saistÄ«tas ar dinamisko pieŔķirÅ”anu. Datu lasÄ«Å”ana praksē ir rādÄ«tāja iestatÄ«Å”ana uz pareizo adresi virtuālajā atmiņā un nekas vairāk. Izklausās pēc fantāzijas, taču repozitorija avotā visi calloc izsaukumi ir koncentrēti repozitorija konfigurācijas funkcijā.
  3. KeÅ”atmiņas neesamÄ«ba nozÄ«mē arÄ« to, ka nav bloÄ·Ä“Å”anas, kas saistÄ«tas ar sinhronizāciju, lai tām piekļūtu. LasÄ«tāji, kuru patvaļīgs skaits var pastāvēt vienlaikus, ceļā uz datiem nesastopas ar vienu mutex. Sakarā ar to lasÄ«Å”anas ātrumam ir ideāla lineāra mērogojamÄ«ba CPU skaita ziņā. LMDB tiek sinhronizētas tikai modificÄ“Å”anas darbÄ«bas. VienlaicÄ«gi var bÅ«t tikai viens rakstnieks.
  4. KeÅ”atmiņas un sinhronizācijas loÄ£ikas minimums ietaupa kodu no ārkārtÄ«gi sarežģīta veida kļūdām, kas saistÄ«tas ar darbu daudzpavedienu vidē. Usenix OSDI 2014 konferencē bija divi interesanti datu bāzes pētÄ«jumi: "Visas failu sistēmas nav izveidotas vienādas: par avārijām konsekventu lietojumprogrammu izstrādes sarežģītÄ«bu" Šø Datu bāzu spÄ«dzināŔana jautrÄ«bas un peļņas gÅ«Å”anai. No tiem var iegÅ«t informāciju gan par LMDB nepieredzētu uzticamÄ«bu, gan gandrÄ«z nevainojamu transakciju ACID Ä«paŔību ievieÅ”anu, kas to pārspēj tajā paŔā SQLite.
  5. LMDB minimālisms ļauj tā koda maŔīnas attēlojumu pilnÄ«bā ievietot procesora L1 keÅ”atmiņā ar iegÅ«tajiem ātruma parametriem.

Diemžēl operētājsistēmā iOS atmiņas kartētie faili nav tik rožaini, kā mēs vēlētos. Lai apzinātāk runātu par ar tiem saistÄ«tajiem trÅ«kumiem, ir jāatgādina vispārÄ«gie principi Ŕī mehānisma ievieÅ”anai operētājsistēmās.

Vispārīga informācija par atmiņas kartētiem failiem

Atslēgu vērtÄ«bu datu bāzes LMDB spožums un nabadzÄ«ba iOS lietojumprogrammāsAr katru izpildāmo lietojumprogrammu operētājsistēma saista entÄ«tiju, ko sauc par procesu. Katram procesam tiek pieŔķirts blakus esoÅ”s adreÅ”u diapazons, kurā tas ievieto visu, kas nepiecieÅ”ams darbam. Zemākajās adresēs ir sadaļas ar kodu un cietkodētiem datiem un resursiem. Nākamais nāk uz augÅ”u augoÅ”ais dinamiskās adreÅ”u telpas bloks, kas mums labi zināms kā kaudze. Tajā ir to entÄ«tiju adreses, kas parādās programmas darbÄ«bas laikā. AugÅ”pusē ir atmiņas apgabals, ko izmanto lietojumprogrammu steka. Tas vai nu aug, vai sarÅ«k, citiem vārdiem sakot, tā izmēram ir arÄ« dinamisks raksturs. Lai kaudze un kaudze nespiestu un netraucētu viena otrai, tās ir atdalÄ«tas dažādos adreÅ”u telpas galos.Starp divām dinamiskajām sadaļām augŔā un apakŔā ir caurums. Å Ä«s vidējās sadaļas adreses operētājsistēma izmanto, lai tās saistÄ«tu ar dažādu entÄ«tiju procesu. Jo Ä«paÅ”i tas var kartēt noteiktu nepārtrauktu adreÅ”u kopu failam diskā. Šādu failu sauc par atmiņas kartētu failu

Procesam atvēlētā adreÅ”u telpa ir milzÄ«ga. Teorētiski adreÅ”u skaitu ierobežo tikai rādÄ«tāja lielums, ko nosaka sistēmas bitums. Ja tam tiktu pieŔķirta fiziskā atmiņa 1-in-1, tad pirmais process apēstu visu RAM, un nebÅ«tu runas par vairākuzdevumu veikÅ”anu.ā€‹

ā€‹Tomēr mēs no pieredzes zinām, ka modernās operētājsistēmas var vienlaikus darbināt tik daudz procesu, cik vēlaties. Tas ir iespējams tāpēc, ka viņi daudz atmiņas pieŔķir procesiem tikai uz papÄ«ra, bet patiesÄ«bā viņi ielādē galvenajā fiziskajā atmiņā tikai to daļu, kas ir pieprasÄ«ta Å”eit un tagad. Tāpēc ar procesu saistÄ«to atmiņu sauc par virtuālo.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Operētājsistēma sakārto virtuālo un fizisko atmiņu noteikta izmēra lapās. TiklÄ«dz noteikta virtuālās atmiņas lapa ir pieprasÄ«ta, operētājsistēma to ielādē fiziskajā atmiņā un ievieto to savstarpējo atbilstÄ«bu Ä«paŔā tabulā. Ja nav brÄ«vu vietu, viena no iepriekÅ” ielādētajām lapām tiek kopēta uz diska, un pieprasÄ«tā tiek aizstāta. Å o procedÅ«ru, pie kuras mēs drÄ«zumā atgriezÄ«simies, sauc par mijmaiņu. Zemāk redzamais attēls ilustrē aprakstÄ«to procesu. Tajā tika ielādēta lapa A ar adresi 0 un ievietota galvenajā atmiņas lapā ar adresi 4. Å is fakts tika atspoguļots atbilstÄ«bas tabulā Ŕūnā ar numuru 0.ā€‹

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Ar atmiņas kartētiem failiem stāsts ir tieÅ”i tāds pats. LoÄ£iski, ka tie it kā nepārtraukti un pilnÄ«bā atrodas virtuālajā adreÅ”u telpā. Tomēr tie nokļūst fiziskajā atmiņā lappusi pēc lapas un tikai pēc pieprasÄ«juma. Šādu lapu modifikācijas tiek sinhronizētas ar failu diskā. Tādējādi jÅ«s varat veikt failu I / O, vienkārÅ”i strādājot ar baitiem atmiņā - visas izmaiņas operētājsistēmas kodolā automātiski pārsÅ«tÄ«s uz sākotnējo failu.ā€‹
ā€‹
Zemāk redzamajā attēlā ir parādÄ«ts, kā LMDB sinhronizē savu stāvokli, strādājot ar datu bāzi no dažādiem procesiem. Kartējot dažādu procesu virtuālo atmiņu vienā failā, mēs de facto uzliekam operētājsistēmai pienākumu tranzitÄ«vi sinhronizēt noteiktus to adreÅ”u telpu blokus savā starpā, un tieÅ”i tur arÄ« izskatās LMDB.ā€‹
ā€‹

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

SvarÄ«ga nianse ir tā, ka LMDB pēc noklusējuma modificē datu failu, izmantojot rakstÄ«Å”anas sistēmas izsaukuma mehānismu, un pats fails tiek parādÄ«ts tikai lasÄ«Å”anas režīmā. Å ai pieejai ir divas svarÄ«gas sekas.

Pirmās sekas ir kopÄ«gas visām operētājsistēmām. Tās bÅ«tÄ«ba ir pievienot aizsardzÄ«bu pret nejauÅ”u datubāzes bojājumu ar nepareizu kodu. Kā jÅ«s zināt, procesa izpildāmās instrukcijas var brÄ«vi piekļūt datiem no jebkuras vietas adreÅ”u telpā. Tajā paŔā laikā, kā mēs tikko atcerējāmies, faila parādÄ«Å”ana lasÄ«Å”anas-rakstÄ«Å”anas režīmā nozÄ«mē, ka jebkura instrukcija to var arÄ« modificēt. Ja viņa to dara kļūdas pēc, mēģinot, piemēram, faktiski pārrakstÄ«t masÄ«va elementu neeksistējoŔā indeksā, tad Ŕādā veidā viņa var nejauÅ”i mainÄ«t uz Å”o adresi kartēto failu, kas novedÄ«s pie datu bāzes sabojāŔanas. Ja fails tiek parādÄ«ts tikai lasÄ«Å”anas režīmā, tad mēģinājums mainÄ«t tam atbilstoÅ”o adreÅ”u telpu novedÄ«s pie programmas avārijas ar signālu SIGSEGV, un fails paliks neskarts.

Otrās sekas jau ir raksturÄ«gas iOS. Ne autors, ne citi avoti to tieÅ”i nepiemin, taču bez tā LMDB bÅ«tu nederÄ«gs darbam ar Å”o mobilo operētājsistēmu. Nākamā sadaļa ir veltÄ«ta tās izskatÄ«Å”anai.

Atmiņai piesaistīto failu specifika operētājsistēmā iOS

2018. gadā WWDC bija brÄ«niŔķīgs ziņojums iOS Memory Deep Dive. Tas norāda, ka iOS visas fiziskajā atmiņā esoŔās lapas pieder vienam no 3 veidiem: netÄ«ras, saspiestas un tÄ«ras.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

TÄ«ra atmiņa ir lapu kolekcija, ko var droÅ”i nomainÄ«t no fiziskās atmiņas. Tajos ietvertos datus pēc vajadzÄ«bas var pārlādēt no to sākotnējiem avotiem. Å ajā kategorijā ietilpst tikai lasāmi atmiņas kartētie faili. iOS nebaidās jebkurā laikā izlādēt no atmiņas failā kartētās lapas, jo tās tiek garantētas sinhronizētas ar failu diskā.
ā€‹
Visas modificētās lapas nokļūst netÄ«rajā atmiņā neatkarÄ«gi no tā, kur tās sākotnēji atrodas. Konkrēti, Ŕādi tiks klasificēti arÄ« atmiņas kartētie faili, kas modificēti, ierakstot ar tiem saistÄ«to virtuālo atmiņu. LMDB atklāŔana ar karogu MDB_WRITEMAP, pēc izmaiņu veikÅ”anas tajā varēsiet pārliecināties.

TiklÄ«dz lietojumprogramma sāk aizņemt pārāk daudz fiziskās atmiņas, iOS saspiež tās netÄ«rās lapas. Atmiņas kolekcija, ko aizņem netÄ«rās un saspiestās lapas, ir tā sauktā lietojumprogrammas atmiņas nospiedums. Kad tas sasniedz noteiktu sliekŔņa vērtÄ«bu, OOM killer sistēmas dēmons nāk pēc procesa un piespiedu kārtā pārtrauc to. Tā ir iOS Ä«patnÄ«ba salÄ«dzinājumā ar galddatoru operētājsistēmām. Turpretim atmiņas apjoma samazināŔana, mainot lapas no fiziskās atmiņas uz disku, operētājsistēmā iOS nav nodroÅ”ināta. Par iemesliem var tikai minēt. VarbÅ«t procedÅ«ra intensÄ«vai lapu pārvietoÅ”anai uz disku un atpakaļ mobilajām ierÄ«cēm ir pārāk energoietilpÄ«ga, vai arÄ« iOS ietaupa resursus Ŕūnu pārrakstÄ«Å”anai SSD diskos, vai varbÅ«t dizaineri nebija apmierināti ar sistēmas kopējo veiktspēju, kur viss ir pastāvÄ«gi mainÄ«ts. Lai kā arÄ« bÅ«tu, fakts paliek fakts.

Labā ziņa, kas jau tika minēta iepriekÅ”, ir tāda, ka LMDB pēc noklusējuma neizmanto mmap mehānismu, lai atjauninātu failus. No tā izriet, ka atveidotos datus iOS klasificē kā tÄ«ru atmiņu un tie neveicina atmiņas nospiedumu. To var pārbaudÄ«t, izmantojot Xcode rÄ«ku VM Tracker. Tālāk esoÅ”ajā ekrānuzņēmumā ir redzams iOS Cloud lietojumprogrammas virtuālās atmiņas stāvoklis darbÄ«bas laikā. Sākumā tajā tika inicializēti 2 LMDB gadÄ«jumi. Pirmajam tika atļauts kartēt savu failu uz 1GiB virtuālās atmiņas, otrajam - 512MiB. Neskatoties uz to, ka abas krātuves aizņem noteiktu daudzumu pastāvÄ«gās atmiņas, neviena no tām neveicina netÄ«ro izmēru.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Tagad ir pienācis laiks sliktajām ziņām. Pateicoties mijmaiņas mehānismam 64 bitu galddatoru operētājsistēmās, katrs process var aizņemt tik daudz virtuālās adreses vietas, cik brÄ«vā vieta cietajā diskā ļauj veikt tā iespējamo mijmaiņas darÄ«jumu. Swap aizstāŔana ar saspieÅ”anu operētājsistēmā iOS krasi samazina teorētisko maksimumu. Tagad visiem dzÄ«vajiem procesiem ir jāiekļaujas galvenajā (lasÄ«t RAM) atmiņā, un visi tie, kas neietilpst, tiek pakļauti piespiedu pārtraukÅ”anai. Tas ir minēts tāpat kā iepriekÅ” Ziņotun iekŔā oficiālā dokumentācija. Tā rezultātā iOS ievērojami ierobežo atmiņas apjomu, kas pieejams pieŔķirÅ”anai, izmantojot mmap. Å eit Å”eit varat apskatÄ«t empÄ«riskos ierobežojumus atmiņas apjomam, ko var pieŔķirt dažādām ierÄ«cēm, izmantojot Å”o sistēmas zvanu. MÅ«sdienÄ«gākajos viedtālruņu modeļos iOS ir kļuvis dāsns par 2 gigabaitiem, bet iPad top versijās - par 4. Praksē, protams, jākoncentrējas uz jaunākajiem atbalstÄ«tajiem ierīču modeļiem, kur viss ir ļoti skumji. Vēl sliktāk, apskatot lietojumprogrammas atmiņas stāvokli VM Tracker, jÅ«s atklāsit, ka LMDB nebÅ«t nav vienÄ«gais, kas pieprasa atmiņas kartētu atmiņu. Labus gabalus noēd sistēmas sadalÄ«tāji, resursu faili, attēlu ietvari un citi mazāki plēsēji.

MākonÄ« veikto eksperimentu rezultātā mēs nonācām pie Ŕādām LMDB pieŔķirtās atmiņas kompromisa vērtÄ«bām: 384 megabaiti 32 bitu ierÄ«cēm un 768 megabaiti 64 bitu ierÄ«cēm. Kad Å”is apjoms ir iztērēts, visas modificÄ“Å”anas darbÄ«bas sāk pabeigt ar kodu MDB_MAP_FULL. Mēs novērojam Ŕādas kļūdas savā uzraudzÄ«bā, taču tās ir pietiekami mazas, lai Å”ajā posmā tās neņemtu vērā.

Nepārprotams iemesls pārmērÄ«gam atmiņas patēriņam krātuvē var bÅ«t ilgstoÅ”i darÄ«jumi. Lai saprastu, kā Ŕīs divas parādÄ«bas ir saistÄ«tas, mums palÄ«dzēs aplÅ«kot atlikuÅ”os divus LMDB vaļus.

3.2. Valis #2. B+-koks

Lai emulētu tabulas virs atslēgu vērtÄ«bu krātuves, tā API ir jābÅ«t Ŕādām darbÄ«bām:

  1. Jauna elementa ievietoŔana.
  2. Meklējiet elementu ar doto atslēgu.
  3. Elementa dzēŔana.
  4. Atkārtojiet taustiņu intervālus to kārtoÅ”anas secÄ«bā.

Atslēgu vērtÄ«bu datu bāzes LMDB spožums un nabadzÄ«ba iOS lietojumprogrammāsVienkārŔākā datu struktÅ«ra, ar kuru var viegli Ä«stenot visas četras darbÄ«bas, ir binārais meklÄ“Å”anas koks. Katrs no tā mezgliem ir atslēga, kas sadala visu bērnu atslēgu apakÅ”kopu divos apakÅ”kokos. Kreisajā pusē ir tie, kas ir mazāki par vecākiem, un labajā pusē - tie, kas ir lielāki. PasÅ«tÄ«tu atslēgu komplektu var iegÅ«t, izmantojot vienu no klasiskajiem koku ŔķērsoÅ”anas veidiem

Binārajiem kokiem ir divi bÅ«tiski trÅ«kumi, kas neļauj tiem darboties kā diska datu struktÅ«rai. Pirmkārt, to lÄ«dzsvara pakāpe ir neparedzama. Pastāv ievērojams risks iegÅ«t kokus, kuros dažādu zaru augstums var ļoti atŔķirties, kas bÅ«tiski pasliktina meklÄ“Å”anas algoritmisko sarežģītÄ«bu salÄ«dzinājumā ar sagaidāmo. Otrkārt, krustsaiÅ”u pārpilnÄ«ba starp mezgliem atņem binārajiem kokiem vietu atmiņā.Tuvie mezgli (saiÅ”u ziņā starp tiem) var atrasties uz pilnÄ«gi dažādām virtuālās atmiņas lapām. Tā rezultātā pat vienkārÅ”ai vairāku blakus esoÅ”o koka mezglu ŔķērsoÅ”anai var bÅ«t nepiecieÅ”ams apmeklēt salÄ«dzināmu lapu skaitu. Tā ir problēma pat tad, ja mēs runājam par bināro koku kā atmiņā esoÅ”as datu struktÅ«ras efektivitāti, jo nepārtraukta lapu rotÄ“Å”ana procesora keÅ”atmiņā nav lēta. Kad runa ir par biežu ar mezgliem saistÄ«tu lapu pacelÅ”anu no diska, viss kļūst ļoti slikti. nožēlojami.

Atslēgu vērtÄ«bu datu bāzes LMDB spožums un nabadzÄ«ba iOS lietojumprogrammāsB-koki, kas ir bināro koku evolÅ«cija, atrisina iepriekŔējā punktā norādÄ«tās problēmas. Pirmkārt, tie paÅ”i lÄ«dzsvaro. Otrkārt, katrs to mezgls sadala bērnu atslēgu kopu nevis 2, bet gan M sakārtotās apakÅ”kopās, un skaitlis M var bÅ«t diezgan liels, ap vairākiem simtiem vai pat tÅ«kstoÅ”iem.

Tādējādi:

  1. Katrā mezglā ir liels skaits jau pasūtītu atslēgu, un koki ir ļoti zemi.
  2. Koks iegÅ«st atraÅ”anās vietas Ä«paŔību atmiņā, jo atslēgas, kurām ir tuva vērtÄ«ba, dabiski atrodas blakus viena otrai vienā vai blakus esoÅ”ajā mezglā.
  3. Samazina tranzÄ«ta mezglu skaitu, meklÄ“Å”anas laikā nolaižoties pa koku.
  4. Samazina diapazona vaicājumiem nolasīto mērķa mezglu skaitu, jo katrā no tiem jau ir liels skaits sakārtotu atslēgu.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

LMDB datu glabāŔanai izmanto B koka variantu, ko sauc par B+ koku. IepriekÅ” redzamajā diagrammā ir parādÄ«ti trÄ«s tajā esoÅ”o mezglu veidi:

  1. AugÅ”pusē ir sakne. Tas neÄ«steno neko vairāk kā datu bāzes jēdzienu repozitorijā. Vienā LMDB instancē varat izveidot vairākas datu bāzes, kas koplieto kartēto virtuālo adreÅ”u telpu. Katrs no tiem sākas no savas saknes.
  2. Zemākajā lÄ«menÄ« ir lapas (lapa). TieÅ”i tie un tikai tie satur datu bāzē saglabātos atslēgu un vērtÄ«bu pārus. Starp citu, tā ir B+-koku Ä«patnÄ«ba. Ja normāls B koks saglabā vērtÄ«bu daļas visu lÄ«meņu mezglos, tad B+ variācija ir tikai zemākajā. Nofiksējot Å”o faktu, turpmāk LMDB izmantoto koka apakÅ”tipu sauksim vienkārÅ”i par B-koku.
  3. Starp sakni un lapām ir 0 vai vairāk tehnisko lÄ«meņu ar navigācijas (zaru) mezgliem. Viņu uzdevums ir sadalÄ«t Ŕķiroto atslēgu komplektu starp lapām.

Fiziski mezgli ir iepriekÅ” noteikta garuma atmiņas bloki. To lielums ir vairākkārtējs operētājsistēmas atmiņas lapu izmēram, par ko mēs runājām iepriekÅ”. Zemāk ir parādÄ«ta mezgla struktÅ«ra. Galvenē ir metainformācija, no kurām acÄ«mredzamākā, piemēram, ir kontrolsumma. Tālāk seko informācija par nobÄ«dēm, gar kurām atrodas Ŕūnas ar datiem. Datu loma var bÅ«t vai nu atslēgas, ja runājam par navigācijas mezgliem, vai veseli atslēgu-vērtÄ«bu pāri lapu gadÄ«jumā.Vairāk par lappuÅ”u struktÅ«ru var lasÄ«t darbā "Augstas veiktspējas atslēgas vērtÄ«bu veikalu novērtējums".

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

TikuÅ”i galā ar lapas mezglu iekŔējo saturu, LMDB B-koku turpmāk attēlosim vienkārÅ”otā veidā sekojoŔā formā.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Lapas ar mezgliem diskā tiek sakārtotas secÄ«gi. Lapas ar lielāku skaitu atrodas faila beigās. Tā sauktajā meta lapā (meta page) ir informācija par nobÄ«dēm, pēc kuras var atrast visu koku saknes. Kad fails tiek atvērts, LMDB skenē failu pa lappusei no beigām lÄ«dz sākumam, meklējot derÄ«gu meta lapu un caur to atrod esoŔās datu bāzes.ā€‹

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Tagad, apzinoties datu organizÄ“Å”anas loÄ£isko un fizisko struktÅ«ru, mēs varam turpināt apsvērt LMDB treÅ”o vali. TieÅ”i ar tās palÄ«dzÄ«bu visas krātuves modifikācijas notiek transakcijā un izolēti viena no otras, pieŔķirot datubāzei kopumā arÄ« vairāku versiju Ä«paŔību.

3.3. Valis #3. kopēŔana uz rakstīŔanas

Dažas B-koka darbÄ«bas ietver virkni izmaiņu veikÅ”anu tā mezglos. Viens piemērs ir jaunas atslēgas pievienoÅ”ana mezglam, kas jau ir sasniedzis maksimālo jaudu. Å ajā gadÄ«jumā, pirmkārt, ir jāsadala mezgls divās daļās un, otrkārt, jāpievieno saite uz jauno atdalÄ«to atvasināto mezglu tā vecākajā. Å Ä« procedÅ«ra ir potenciāli ļoti bÄ«stama. Ja kāda iemesla dēļ (avārija, strāvas padeves pārtraukums utt.) notiek tikai daļa no sērijas izmaiņām, koks paliks nekonsekventā stāvoklÄ«.

Viens tradicionāls risinājums, kā padarÄ«t datubāzi par defektu tolerantu, ir pievienot papildu uz diskiem balstÄ«tu datu struktÅ«ru, darÄ«jumu žurnālu, kas pazÄ«stams arÄ« kā ierakstÄ«Å”anas žurnāls (WAL), blakus B kokam. Tas ir fails, kura beigās, stingri pirms paÅ”a B-koka modifikācijas, tiek ierakstÄ«ta iecerētā darbÄ«ba. Tādējādi, ja paÅ”diagnostikas laikā tiek atklāts datu bojājums, datu bāze meklē žurnālu, lai sevi iztÄ«rÄ«tu.

LMDB kā kļūdu pielaides mehānismu ir izvēlējies citu metodi, ko sauc par kopÄ“Å”anu-rakstÄ«Å”anu. Tās bÅ«tÄ«ba ir tāda, ka tā vietā, lai atjauninātu esoŔās lapas datus, tā vispirms tos pilnÄ«bā kopē un veic visas kopijā jau esoŔās izmaiņas.ā€‹

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Turklāt, lai atjauninātie dati bÅ«tu pieejami, attiecÄ«bā uz to ir jāmaina saite uz mezglu, kas vecākmezglā ir kļuvis aktuāls. Tā kā tas arÄ« ir jāmaina Å”im nolÅ«kam, tas arÄ« ir iepriekÅ” kopēts. Process turpinās rekursÄ«vi lÄ«dz pat saknei. Dati meta lapā tiek mainÄ«ti pēdējie.ā€‹ā€‹

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Ja pēkŔņi process atjaunināŔanas procedÅ«ras laikā avarē, tad vai nu netiks izveidota jauna meta lapa, vai arÄ« tā netiks ierakstÄ«ta diskā lÄ«dz beigām, un tās kontrolsumma bÅ«s nepareiza. Nevienā no Å”iem diviem gadÄ«jumiem jaunās lapas nebÅ«s sasniedzamas, un vecās lapas netiks ietekmētas. Tas novērÅ” nepiecieÅ”amÄ«bu LMDB rakstÄ«t uz priekÅ”u žurnālu, lai saglabātu datu konsekvenci. Faktiski iepriekÅ” aprakstÄ«tā datu uzglabāŔanas struktÅ«ra diskā vienlaikus uzņemas savu funkciju. Skaidra darÄ«jumu žurnāla neesamÄ«ba ir viena no LMDB funkcijām, kas nodroÅ”ina lielu datu lasÄ«Å”anas ātrumu.ā€‹

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

IegÅ«tā konstrukcija, ko sauc par tikai pievienoÅ”anas B-koku, dabiski nodroÅ”ina darÄ«jumu izolāciju un vairāku versiju veidoÅ”anu. LMDB katram atvērtajam darÄ«jumam ir saistÄ«ta ar to jaunākā koka sakne. Kamēr darÄ«jums nav pabeigts, ar to saistÄ«tā koka lapas nekad netiks mainÄ«tas vai atkārtoti izmantotas jaunām datu versijām. Tādējādi jÅ«s varat strādāt tik ilgi, cik vēlaties tieÅ”i ar datu kopu, kas bija svarÄ«ga darÄ«juma atvērÅ”anas laiks, pat ja krātuve paÅ”laik tiek aktÄ«vi atjaunināta. Tā ir multiversijas bÅ«tÄ«ba, padarot LMDB par ideālu datu avotu mÅ«su mīļotajam UICollectionView. Atverot darÄ«jumu, jums nav jāpalielina lietojumprogrammas atmiņas apjoms, steidzÄ«gi izsÅ«knējot paÅ”reizējos datus kādā atmiņas struktÅ«rā, baidoties palikt bez nekā. Å Ä« funkcija atŔķir LMDB no tā paÅ”a SQLite, kas nevar lepoties ar Ŕādu pilnÄ«gu izolāciju. Atverot divus darÄ«jumus pēdējā un dzÄ“Å”ot noteiktu ierakstu vienā no tiem, to paÅ”u ierakstu vairs nevar iegÅ«t otrajā atlikuÅ”ajā.

Monētas otrā puse ir potenciāli ievērojami lielāks virtuālās atmiņas patēriņŔ. Slaids parāda, kā izskatÄ«sies datu bāzes struktÅ«ra, ja tā tiks vienlaikus modificēta ar 3 atvērtām lasÄ«Å”anas transakcijām, aplÅ«kojot dažādas datu bāzes versijas. Tā kā LMDB nevar atkārtoti izmantot mezglus, kas ir sasniedzami no saknēm, kas saistÄ«tas ar faktiskajām transakcijām, krātuvei nav citas izvēles, kā pieŔķirt atmiņā vēl vienu ceturto sakni un vēlreiz klonēt zem tās modificētās lapas.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Å eit nebÅ«s lieki atsaukt atmiņā sadaļu par failiem, kas kartēti. Å Ä·iet, ka papildu virtuālās atmiņas patēriņam nevajadzētu mÅ«s Ä«paÅ”i apgrÅ«tināt, jo tas neveicina lietojumprogrammas atmiņas nospiedumu. Taču tajā paŔā laikā tika atzÄ«mēts, ka iOS ir ļoti skops tās pieŔķirÅ”anā, un mēs nevaram nodroÅ”ināt 1 terabaita LMDB reÄ£ionu serverÄ« vai darbvirsmā no meistara pleca un par Å”o funkciju nedomāt vispār. Ja iespējams, mēģiniet saglabāt pēc iespējas Ä«sāku darÄ«jumu ilgumu.

4. Datu shēmas izstrāde virs atslēgas vērtÄ«bas API

Sāksim API parsÄ“Å”anu, aplÅ«kojot LMDB nodroÅ”inātās pamata abstrakcijas: vidi un datu bāzes, atslēgas un vērtÄ«bas, transakcijas un kursorus.

Piezīme par kodu sarakstiem

Visas funkcijas LMDB publiskajā API atgriež sava darba rezultātu kļūdas koda veidā, bet visos turpmākajos sarakstos tā pārbaude Ä«suma labad ir izlaista.Praksē, lai mijiedarbotos ar repozitoriju, izmantojām savu kodu. dakÅ”a C++ iesaiņojumi lmdbxx, kurā kļūdas izpaužas kā C++ izņēmumi.

Kā ātrāko veidu, kā savienot LMDB ar iOS vai macOS projektu, es piedāvāju savu CocoaPod POSLMDB.

4.1. Pamata abstrakcijas

Vide

StruktÅ«ra MDB_env is ir LMDB iekŔējā stāvokļa repozitorijs. Prefiksēto funkciju saime mdb_env ļauj konfigurēt dažus tā rekvizÄ«tus. VienkārŔākajā gadÄ«jumā dzinēja inicializācija izskatās Ŕādi.

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

Lietojumprogrammā Mail.ru Cloud mēs mainījām noklusējuma vērtības tikai diviem parametriem.

Pirmais ir virtuālās adreÅ”u telpas lielums, ar kuru tiek kartēts krātuves fails. Diemžēl pat tajā paŔā ierÄ«cē konkrētā vērtÄ«ba var ievērojami atŔķirties atkarÄ«bā no darbÄ«bas laika. Lai ņemtu vērā Å”o iOS funkciju, mēs dinamiski atlasām maksimālo krātuves apjomu. Sākot no noteiktas vērtÄ«bas, tā secÄ«gi samazinās uz pusi lÄ«dz funkcijai mdb_env_open neatgriezÄ«s citu rezultātu kā vien ENOMEM. Teorētiski ir pretējs veids - vispirms pieŔķiriet dzinējam minimālu atmiņu un pēc tam, kad tiek saņemtas kļūdas MDB_MAP_FULL, palieliniet to. Tomēr tas ir daudz ērkŔķaināks. Iemesls ir tāds, ka procedÅ«ra atmiņas pārkartÄ“Å”anai, izmantojot funkciju mdb_env_set_map_size anulē visas entÄ«tijas (kursorus, transakcijas, atslēgas un vērtÄ«bas), kas iepriekÅ” saņemtas no dzinēja. Šāda notikumu pavērsiena uzskaite kodā radÄ«s ievērojamu sarežģījumu. Ja tomēr virtuālā atmiņa jums ir ļoti dārga, tad tas var bÅ«t iemesls paskatÄ«ties uz tālu uz priekÅ”u aizgājuÅ”o dakÅ”iņu. MDBX, kur starp deklarētajām pazÄ«mēm ir ā€œautomātiska datu bāzes izmēra pielāgoÅ”ana lidojumāā€.

Otrs parametrs, kura noklusējuma vērtÄ«ba mums nebija piemērota, regulē vÄ«tnes droŔības nodroÅ”ināŔanas mehāniku. Diemžēl vismaz operētājsistēmā iOS 10 ir problēmas ar pavedienu vietējās krātuves atbalstu. Å Ä« iemesla dēļ iepriekÅ” minētajā piemērā repozitorijs tiek atvērts ar karogu MDB_NOTLS. Turklāt tas arÄ« prasÄ«ja dakÅ”a C++ iesaiņojums lmdbxxlai izgrieztu mainÄ«gos ar un Å”ajā atribÅ«tā.

Datu bāzes

Datubāze ir atseviŔķs B-koka gadÄ«jums, par kuru mēs runājām iepriekÅ”. Tās atvērÅ”ana notiek darÄ«juma ietvaros, kas sākumā var Ŕķist nedaudz dÄ«vaini.

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

PatieŔām, darÄ«jums LMDB ir krātuves entÄ«tija, nevis konkrēta datu bāze. Å Ä« koncepcija ļauj veikt atomu operācijas ar entÄ«tijām, kas atrodas dažādās datu bāzēs. Teorētiski tas paver iespēju modelēt tabulas dažādu datu bāzu veidā, taču savulaik es gāju citu ceļu, kas sÄ«kāk aprakstÄ«ts tālāk.

Atslēgas un vērtības

StruktÅ«ra MDB_val modelē gan atslēgas, gan vērtÄ«bas jēdzienu. Repozitorijai nav ne jausmas par to semantiku. Viņai kaut kas atŔķirÄ«gs ir tikai noteikta izmēra baitu masÄ«vs. Maksimālais atslēgas izmērs ir 512 baiti.

typedef struct MDB_val {ā€‹
    size_t mv_size;ā€‹
    void *mv_data;ā€‹
} MDB_val;ā€‹ā€‹

Veikals izmanto salÄ«dzinājumu, lai sakārtotu atslēgas augoŔā secÄ«bā. Ja neaizstāsiet to ar savu, tiks izmantots noklusējuma, kas tos sakārto pa baitiem leksikogrāfiskā secÄ«bā.ā€‹

Darījumi

DarÄ«juma ierÄ«ce ir detalizēti aprakstÄ«ta iepriekŔējā nodaļā, tāpēc Å”eit es atkārtoÅ”u to galvenās Ä«paŔības Ä«sā rindā:

  1. Atbalsts visām pamata Ä«paŔībām ACIDAtslēgas vārdi: atomitāte, konsistence, izolācija un uzticamÄ«ba. Es nevaru nepiezÄ«mēt, ka MacOS un iOS izturÄ«bas ziņā MDBX ir novērsta kļūda. JÅ«s varat lasÄ«t vairāk viņu README.
  2. Daudzpavedienu pieeja ir aprakstīta shēmā "viens rakstītājs / vairāki lasītāji". Rakstnieki bloķē viens otru, bet viņi nebloķē lasītājus. Lasītāji nebloķē ne rakstniekus, ne viens otru.
  3. Atbalsts ligzdotiem darījumiem.
  4. Daudzversiju atbalsts.

Multiversija LMDB ir tik laba, ka gribu to demonstrēt darbÄ«bā. Tālāk redzamais kods parāda, ka katrs darÄ«jums darbojas tieÅ”i ar to datu bāzes versiju, kas bija aktuāla tās atvērÅ”anas brÄ«dÄ«, pilnÄ«bā izolēta no visām turpmākajām izmaiņām. Repozitorija inicializācija un testa ieraksta pievienoÅ”ana tai neinteresē, tāpēc Å”ie rituāli tiek atstāti zem spoilera.

Testa ieraksta pievienoŔana

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

Pēc izvēles es iesaku izmēģināt to paÅ”u triku ar SQLite un redzēt, kas notiek.

Multiversiju izmantoÅ”ana sniedz ļoti jaukas priekÅ”rocÄ«bas iOS izstrādātāja dzÄ«vē. Izmantojot Å”o Ä«paÅ”umu, varat viegli un dabiski pielāgot datu avota atjaunināŔanas ātrumu ekrāna formām, pamatojoties uz lietotāja pieredzes apsvērumiem. Piemēram, ņemsim tādu Mail.ru Cloud lietojumprogrammas funkciju kā satura automātiska ielāde no sistēmas multivides galerijas. Ar labu savienojumu klients var pievienot serverim vairākas fotogrāfijas sekundē. Ja atjaunināsiet pēc katras lejupielādes UICollectionView ar multivides saturu lietotāja mākonÄ«, Ŕī procesa laikā varat aizmirst par 60 kadriem sekundē un vienmērÄ«gu ritināŔanu. Lai novērstu biežu ekrāna atjaunināŔanu, jums kaut kā jāierobežo datu izmaiņu ātrums bāzē UICollectionViewDataSource.

Ja datu bāze neatbalsta vairāku versiju izveidi un ļauj strādāt tikai ar paÅ”reizējo paÅ”reizējo stāvokli, tad, lai izveidotu laika stabilu datu momentuzņēmumu, tas ir jākopē vai nu uz kādu atmiņas datu struktÅ«ru, vai pagaidu tabulu. Jebkura no Ŕīm metodēm ir ļoti dārga. Atmiņas krātuves gadÄ«jumā mēs iegÅ«stam gan atmiņas izmaksas, ko rada konstruētu objektu glabāŔana, gan laika izmaksas, kas saistÄ«tas ar liekām ORM transformācijām. Kas attiecas uz pagaidu galdu, tas ir vēl dārgāks prieks, kam ir jēga tikai nenozÄ«mÄ«gos gadÄ«jumos.

Daudzversiju LMDB atrisina stabila datu avota uzturÄ“Å”anas problēmu ļoti elegantā veidā. Pietiek tikai atvērt darÄ«jumu un voila - kamēr mēs to nepabeigsim, datu kopa tiek garantēta. Tā atjaunināŔanas ātruma loÄ£ika tagad pilnÄ«bā ir prezentācijas slāņa rokās, bez ievērojamiem resursiem.

Kursori

Kursori nodroÅ”ina mehānismu sakārtotai atslēgu un vērtÄ«bu pāru iterācijai, Ŕķērsojot B-koku. Bez tiem nebÅ«tu iespējams efektÄ«vi modelēt tabulas datu bāzē, pie kuras mēs tagad vērÅ”amies.

4.2. Tabulu modelēŔana

Atslēgu secÄ«bas rekvizÄ«ts ļauj izveidot augstākā lÄ«meņa abstrakciju, piemēram, tabulu virs pamata abstrakcijām. ApskatÄ«sim Å”o procesu mākoņa klienta galvenās tabulas piemērā, kurā tiek saglabāta informācija par visiem lietotāja failiem un mapēm.

Tabulas shēma

Viens no izplatÄ«tākajiem scenārijiem, kam vajadzētu uzlabot tabulas ar mapju koku struktÅ«ru, ir atlasÄ«t visus elementus, kas atrodas dotajā direktorijā. Labs datu organizÄ“Å”anas modelis efektÄ«viem Ŕāda veida vaicājumiem ir BlakusparādÄ«bu saraksts. Lai to ieviestu virs atslēgu vērtÄ«bu krātuves, ir nepiecieÅ”ams kārtot failu un mapju atslēgas tā, lai tās bÅ«tu grupētas, pamatojoties uz piederÄ«bu vecākajam direktorijam. Turklāt, lai parādÄ«tu direktorijas saturu Windows lietotājam pazÄ«stamā formā (vispirms mapes, pēc tam faili, abi ir sakārtoti alfabētiskā secÄ«bā), atslēgā ir jāiekļauj atbilstoÅ”ie papildu lauki.

Tālāk esoÅ”ajā attēlā ir parādÄ«ts, kā, pamatojoties uz uzdevumu, var izskatÄ«ties atslēgu attēlojums kā baitu masÄ«vs. Vispirms tiek ievietoti baiti ar vecākdirektorija identifikatoru (sarkans), pēc tam ar tipu (zaļŔ), un jau aizmugurē ar nosaukumu (zils) Sakārtoti pēc noklusējuma LMDB salÄ«dzinājuma leksikogrāfiskā secÄ«bā, tie tiek sakārtoti Ŕādā secÄ«bā. vajadzÄ«gajā veidā. SecÄ«gi Ŕķērsojot atslēgas ar vienu un to paÅ”u sarkano prefiksu, mēs iegÅ«stam ar tām saistÄ«tās vērtÄ«bas tādā secÄ«bā, kādā tās jāparāda lietotāja interfeisā (pa labi), neprasot nekādu papildu pēcapstrādi.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Atslēgu un vērtÄ«bu serializÄ“Å”ana

Visā pasaulē ir daudz metožu objektu serializÄ“Å”anai. Tā kā mums nebija citu prasÄ«bu, izņemot ātrumu, mēs izvēlējāmies ātrāko iespējamo - atmiņas izgāztuvi, ko aizņem C valodas struktÅ«ras gadÄ«jums. Tātad direktorija elementa atslēgu var modelēt ar Ŕādu struktÅ«ru NodeKey.

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

Saglabāt NodeKey glabāŔanas nepiecieÅ”amÄ«ba objektā MDB_val novietojiet rādÄ«tāju uz datiem struktÅ«ras sākuma adresē un ar funkciju aprēķiniet to lielumu sizeof.

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

Pirmajā nodaļā par datu bāzes atlases kritērijiem kā svarÄ«gu atlases faktoru minēju dinamisko pieŔķīrumu minimizÄ“Å”anu kā daļu no CRUD operācijām. Funkcijas kods serialize parāda, kā LMDB gadÄ«jumā no tiem var pilnÄ«bā izvairÄ«ties, kad datu bāzē tiek ievietoti jauni ieraksti. No servera ienākoÅ”ais baitu masÄ«vs vispirms tiek pārveidots steka struktÅ«rās, un pēc tam tie tiek triviāli ievietoti krātuvē. Ņemot vērā, ka LMDB iekÅ”ienē nav arÄ« dinamisku pieŔķīrumu, varat iegÅ«t fantastisku situāciju pēc iOS standartiem - izmantojiet tikai steka atmiņu, lai strādātu ar datiem no tÄ«kla lÄ«dz diskam!

Atslēgu pasÅ«tÄ«Å”ana ar bināro komparatoru

Atslēgu secÄ«bas attiecÄ«bu nosaka Ä«paÅ”a funkcija, ko sauc par salÄ«dzinājumu. Tā kā dzinējs neko nezina par tajos ietverto baitu semantiku, noklusējuma salÄ«dzinātājam nav citas izvēles, kā sakārtot atslēgas leksikogrāfiskā secÄ«bā, izmantojot to salÄ«dzināŔanu pa baitiem. Tās izmantoÅ”ana konstrukciju sakārtoÅ”anai ir lÄ«dzÄ«ga skÅ«Å”anai ar grebuma cirvi. Tomēr vienkārÅ”os gadÄ«jumos Ŕī metode man Ŕķiet pieņemama. AlternatÄ«va ir aprakstÄ«ta zemāk, bet Å”eit es atzÄ«mÄ“Å”u pāris grābekļus, kas izkaisÄ«ti pa ceļam.

Pirmā lieta, kas jāpatur prātā, ir primitÄ«vo datu tipu attēlojums atmiņā. Tātad visās Apple ierÄ«cēs veseli skaitļu mainÄ«gie tiek saglabāti formātā Mazais Endians. Tas nozÄ«mē, ka vismazāk nozÄ«mÄ«gais baits bÅ«s kreisajā pusē, un jÅ«s nevarēsit kārtot veselus skaitļus, izmantojot to salÄ«dzinājumu pa baitiem. Piemēram, mēģinot to izdarÄ«t ar skaitļu kopu no 0 lÄ«dz 511, tiks parādÄ«ts Ŕāds rezultāts.

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

Lai atrisinātu Å”o problēmu, atslēgā ir jāsaglabā veseli skaitļi baitu salÄ«dzinājumam piemērotā formātā. Ä¢imenes funkcijas palÄ«dzēs veikt nepiecieÅ”amo transformāciju. hton* (it Ä«paÅ”i htons divbaitu numuriem no piemēra).

Virkņu attēloÅ”anas formāts programmÄ“Å”anā, kā jÅ«s zināt, ir vesels stāsts. Ja virkņu semantika, kā arÄ« to atveidoÅ”anai atmiņā izmantotais kodējums liecina, ka katrai rakstzÄ«mei var bÅ«t vairāk nekā viens baits, tad labāk ir nekavējoties atteikties no idejas par noklusējuma salÄ«dzinājuma izmantoÅ”anu.

Otra lieta, kas jāpatur prātā, ir saskaņoÅ”anas principi struct lauka kompilators. To dēļ atmiņā starp laukiem var tikt izveidoti baiti ar atkritumu vērtÄ«bām, kas, protams, pārtrauc baitu ŔķiroÅ”anu. Lai novērstu atkritumus, jums ir vai nu jādeklarē lauki stingri noteiktā secÄ«bā, paturot prātā lÄ«dzināŔanas noteikumus, vai arÄ« jāizmanto atribÅ«ts struktÅ«ras deklarācijā packed.

Atslēgu pasÅ«tÄ«Å”ana ar ārēju salÄ«dzinātāju

Atslēgu salÄ«dzināŔanas loÄ£ika var izrādÄ«ties pārāk sarežģīta bināram salÄ«dzinājumam. Viens no daudzajiem iemesliem ir tehnisko lauku klātbÅ«tne konstrukcijās. Es ilustrÄ“Å”u to raÅ”anos, izmantojot piemēru ar mums jau pazÄ«stamu direktorija elementa taustiņu.

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

Neskatoties uz savu vienkārŔību, vairumā gadÄ«jumu tas patērē pārāk daudz atmiņas. Virsraksta buferis ir 256 baiti, lai gan vidēji failu un mapju nosaukumi reti pārsniedz 20ā€“30 rakstzÄ«mes.

Viens no standarta paņēmieniem ieraksta lieluma optimizÄ“Å”anai ir tā apgrieÅ”ana, lai tas atbilstu tā faktiskajam izmēram. Tās bÅ«tÄ«ba ir tāda, ka visu mainÄ«ga garuma lauku saturs tiek glabāts buferÄ« struktÅ«ras beigās un to garumi tiek glabāti atseviŔķos mainÄ«gajos.Saskaņā ar Å”o pieeju atslēga NodeKey tiek pārveidots Ŕādā veidā.

typedef struct NodeKey {ā€‹
    EntityId parentId;ā€‹
    uint8_t type;ā€‹
    uint8_t nameLength;ā€‹
    uint8_t nameBuffer[256];ā€‹
} NodeKey;

Turklāt serializācijas laikā nav norādīts kā datu lielums sizeof visa struktūra, un visu lauku lielums ir fiksēts garums plus faktiski izmantotās bufera daļas lielums.

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

Refaktorizācijas rezultātā mēs panācām ievērojamu ietaupÄ«jumu atslēgu aizņemtajā telpā. Tomēr tehniskās jomas dēļ nameLength, noklusējuma binārais salÄ«dzinātājs vairs nav piemērots atslēgu salÄ«dzināŔanai. Ja mēs to neaizstāsim ar savu, tad nosaukuma garums bÅ«s prioritārāks faktors ŔķiroÅ”anā nekā pats nosaukums.

LMDB ļauj katrai datubāzei izmantot savu atslēgu salÄ«dzināŔanas funkciju. Tas tiek darÄ«ts, izmantojot funkciju mdb_set_compare stingri pirms atvērÅ”anas. AcÄ«mredzamu iemeslu dēļ datu bāzi nevar mainÄ«t tās darbÄ«bas laikā. Ievadē salÄ«dzinātājs saņem divus taustiņus binārā formātā, un izejā tas atgriež salÄ«dzināŔanas rezultātu: mazāks par (-1), lielāks par (1) vai vienāds (0). Pseidokods priekÅ” NodeKey izskatās tā.

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 // ...
}ā€‹

Kamēr visas atslēgas datu bāzē ir viena veida, ir likumÄ«gi bez nosacÄ«jumiem nodot to baitu attēlojumu atslēgas lietojumprogrammas struktÅ«ras veidam. Å eit ir viena nianse, bet par to tiks runāts nedaudz zemāk apakÅ”sadaļā ā€œLasÄ«Å”anas ierakstiā€.

Vērtību serializācija

Ar glabājamo ierakstu atslēgām LMDB strādā ārkārtÄ«gi intensÄ«vi. Tie tiek salÄ«dzināti viens ar otru jebkuras lietojumprogrammas darbÄ«bas ietvaros, un visa risinājuma veiktspēja ir atkarÄ«ga no salÄ«dzinājuma ātruma. Ideālā pasaulē ar noklusējuma bināro salÄ«dzinātāju vajadzētu pietikt, lai salÄ«dzinātu atslēgas, bet, ja jums patieŔām bija jāizmanto savs, tad tajā esoÅ”o atslēgu deserializācijas procedÅ«rai vajadzētu bÅ«t pēc iespējas ātrākai.

Datubāzi Ä«paÅ”i neinteresē ieraksta (vērtÄ«bas) daļa Value. Tā pārveidoÅ”ana no baitu attēlojuma par objektu notiek tikai tad, kad tas jau ir vajadzÄ«gs lietojumprogrammas kodam, piemēram, lai to parādÄ«tu ekrānā. Tā kā tas notiek salÄ«dzinoÅ”i reti, prasÄ«bas Ŕīs procedÅ«ras ātrumam nav tik kritiskas, un tās ievieÅ”anā daudz brÄ«vāk varam koncentrēties uz ērtÄ«bām, piemēram, lai serializētu metadatus par failiem, kas vēl nav lejupielādēti, mēs izmantojam NSKeyedArchiver.

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

Tomēr ir gadÄ«jumi, kad sniegumam ir nozÄ«me. Piemēram, saglabājot metainformāciju par lietotāja mākoņa failu struktÅ«ru, mēs izmantojam vienu un to paÅ”u objektu atmiņas izgāztuvi. Serializētā attēlojuma Ä£enerÄ“Å”anas uzdevums ir tas, ka direktorija elementus modelē klaÅ”u hierarhija.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Tās īstenoŔanai C valodā mantinieku specifiskie lauki tiek izdalīti atseviŔķās struktūrās, un to saikne ar pamatu tiek noteikta caur savienības tipa lauku. Apvienības faktiskais saturs tiek norādīts, izmantojot tipa tehnisko atribūtu.

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

Ierakstu pievienoŔana un atjaunināŔana

Serializēto atslēgu un vērtību var pievienot veikalam. Šim nolūkam tiek izmantota funkcija mdb_put.

// key Šø value ŠøŠ¼ŠµŃŽŃ‚ тŠøŠæ MDB_valā€‹
mdb_put(..., &key, &value, MDB_NOOVERWRITE);

Konfigurācijas stadijā repozitorija var atļaut vai aizliegt glabāt vairākus ierakstus ar vienu atslēgu.ā€‹ā€‹ Ja atslēgu dublÄ“Å”ana ir aizliegta, tad, ievietojot ierakstu, varat noteikt, vai ir atļauta jau esoÅ”a ieraksta atjaunināŔana. Ja nodilums var rasties tikai koda kļūdas rezultātā, tad pret to var apdroÅ”ināties, norādot karogu NOOVERWRITE.

Ierakstu lasīŔana

Ierakstu nolasÄ«Å”anas funkcija LMDB ir mdb_get. Ja atslēgu un vērtÄ«bu pāri attēlo iepriekÅ” izmestas struktÅ«ras, Ŕī procedÅ«ra izskatās Ŕādi.

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

Piedāvātais saraksts parāda, kā serializācija, izmantojot struktÅ«ru izgāztuvi, ļauj atbrÄ«voties no dinamiskiem pieŔķīrumiem ne tikai rakstot, bet arÄ« lasot datus. Atvasināts no funkcijas mdb_get rādÄ«tājs precÄ«zi aplÅ«ko virtuālās atmiņas adresi, kurā datu bāze glabā objekta baitu attēlojumu. Faktiski mēs iegÅ«stam sava veida ORM, gandrÄ«z bez maksas, nodroÅ”inot ļoti lielu datu lasÄ«Å”anas ātrumu. Ar visu pieejas skaistumu ir jāatceras vairākas ar to saistÄ«tas iezÄ«mes.

  1. Ja darÄ«jums ir tikai lasāms, rādÄ«tājs uz vērtÄ«bu struktÅ«ru tiek garantēts, ka tas paliks spēkā tikai lÄ«dz darÄ«juma slēgÅ”anai. Kā minēts iepriekÅ”, B koka lapas, kurās atrodas objekts, pateicoties kopÄ“Å”anas-uzrakstÄ«Å”anas principam, paliek nemainÄ«gas, kamēr uz tām attiecas vismaz viens darÄ«jums. Tajā paŔā laikā, tiklÄ«dz ir pabeigts pēdējais ar tām saistÄ«tais darÄ«jums, lapas var atkārtoti izmantot jauniem datiem. Ja ir nepiecieÅ”ams, lai objekti izdzÄ«votu darÄ«jumā, kas tos radÄ«ja, tad tie tomēr ir jākopē.
  2. LasÄ«Å”anas un rakstÄ«Å”anas transakcijai rādÄ«tājs uz iegÅ«to struktÅ«ras vērtÄ«bu bÅ«s derÄ«gs tikai lÄ«dz pirmajai modificÄ“Å”anas procedÅ«rai (datu rakstÄ«Å”anai vai dzÄ“Å”anai).
  3. Lai arÄ« struktÅ«ra NodeValue nevis pilnvērtÄ«gs, bet apgriezts (skat. apakÅ”sadaļu "Atslēgu pasÅ«tÄ«Å”ana ar ārēju salÄ«dzinātāju"), caur rādÄ«tāju var ērti piekļūt tā laukiem. Galvenais ir to neatsaukt!
  4. Nekādā gadÄ«jumā nevar modificēt struktÅ«ru, izmantojot saņemto rādÄ«tāju. Visas izmaiņas jāveic tikai ar metodi mdb_put. Tomēr ar visu vēlmi to darÄ«t, tas nedarbosies, jo atmiņas apgabals, kurā atrodas Ŕī struktÅ«ra, ir kartēts tikai lasÄ«Å”anas režīmā.
  5. Pārveidojiet failu procesa adreÅ”u telpā, lai, piemēram, palielinātu maksimālo krātuves lielumu, izmantojot funkciju mdb_env_set_map_size pilnÄ«bā padara nederÄ«gus visus darÄ«jumus un saistÄ«tās entÄ«tijas kopumā un jo Ä«paÅ”i norādes uz objektu lasÄ«Å”anu.

Visbeidzot, vēl viena iezÄ«me ir tik mānÄ«ga, ka tās bÅ«tÄ«bas izpauÅ”ana neietilpst vēl vienā punktā. Nodaļā par B-koku es sniedzu diagrammu par tā lappuÅ”u organizÄ“Å”anu atmiņā. No tā izriet, ka bufera sākuma adrese ar serializētiem datiem var bÅ«t absolÅ«ti patvaļīga. Sakarā ar to, rādÄ«tājs uz tiem, kas iegÅ«ti struktÅ«rā MDB_val un cast uz rādÄ«tāju uz struktÅ«ru parasti nav izlÄ«dzināts. Tajā paŔā laikā dažu mikroshēmu arhitektÅ«ra (iOS gadÄ«jumā tas ir armv7) pieprasa, lai jebkuru datu adresei ir jābÅ«t maŔīnas vārda lieluma reizinājumam vai, citiem vārdiem sakot, sistēmas bitumam. (armv7 tas ir 32 biti). Citiem vārdiem sakot, tāda operācija kā *(int *foo)0x800002 uz tiem tiek pielÄ«dzināts bēgÅ”anai un noved pie nāvessoda ar spriedumu EXC_ARM_DA_ALIGN. Ir divi veidi, kā izvairÄ«ties no tik bēdÄ«ga likteņa.

Pirmais ir iepriekÅ” kopēt datus zināmā saskaņotā struktÅ«rā. Piemēram, pielāgotā salÄ«dzinātājā tas tiks atspoguļots Ŕādi.

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

AlternatÄ«vs veids ir iepriekÅ” paziņot kompilatoram, ka struktÅ«ras ar atslēgu un vērtÄ«bu var netikt lÄ«dzinātas, izmantojot atribÅ«tu. aligned(1). Uz ARM var bÅ«t tāds pats efekts sasniegt un izmantojot packed atribÅ«tu. Ņemot vērā, ka tā arÄ« veicina struktÅ«ras aizņemtās telpas optimizāciju, Ŕī metode man Ŕķiet labāka, lai gan ŠæрŠøŠ²Š¾Š“Šøт palielināt datu piekļuves operāciju izmaksas.

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

Diapazona vaicājumi

Lai atkārtotu ierakstu grupu, LMDB nodroÅ”ina kursora abstrakciju. ApskatÄ«sim, kā ar to strādāt, izmantojot tabulas piemēru ar mums jau pazÄ«stamiem lietotāja mākoņa metadatiem.

Katalogā esoÅ”o failu saraksta parādÄ«Å”anas ietvaros ir jāatrod visas atslēgas, ar kurām ir saistÄ«ti tā pakārtotie faili un mapes. IepriekŔējās apakÅ”nodaļās mēs sakārtojām atslēgas NodeKey lai tie vispirms tiktu sakārtoti pēc vecāku direktorija ID. Tādējādi tehniski uzdevums iegÅ«t mapes saturu tiek samazināts lÄ«dz kursora novietoÅ”anai uz atslēgu grupas augŔējās robežas ar noteiktu prefiksu, kam seko iterācija lÄ«dz apakŔējai robežai.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

JÅ«s varat atrast augŔējo robežu "uz pieres", veicot secÄ«gu meklÄ“Å”anu. Lai to izdarÄ«tu, kursors tiek novietots visa datubāzes atslēgu saraksta sākumā un pēc tam tiek palielināts, lÄ«dz zem tā parādās atslēga ar vecākdirektorija identifikatoru. Å ai pieejai ir 2 acÄ«mredzami trÅ«kumi:

  1. MeklÄ“Å”anas lineārā sarežģītÄ«ba, lai gan, kā zināms, kokos kopumā un jo Ä«paÅ”i B-kokā to var veikt logaritmiskā laikā.
  2. Veltīgi visas lapas, kas ir pirms vēlamās, tiek pārceltas no faila uz galveno atmiņu, kas ir ārkārtīgi dārgi.

Par laimi, LMDB API nodroÅ”ina efektÄ«vu veidu, kā sākotnēji novietot kursoru. Lai to izdarÄ«tu, jums ir jāveido atslēga, kuras vērtÄ«ba, kā zināms, ir mazāka vai vienāda ar atslēgu, kas atrodas uz intervāla augŔējās robežas. Piemēram, attiecÄ«bā uz sarakstu attēlā iepriekÅ”, mēs varam izveidot atslēgu, kurā lauks parentId bÅ«s vienāds ar 2, un visi pārējie ir aizpildÄ«ti ar nullēm. Šāda daļēji aizpildÄ«ta atslēga tiek ievadÄ«ta funkcijas ievadā mdb_cursor_get kas norāda uz darbÄ«bu 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);

Ja tiek atrasta atslēgu grupas augŔējā robeža, mēs atkārtojam to, lÄ«dz tiekam vai nu atslēga ar citu parentId, vai arÄ« atslēgas vispār nebeigsies.

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ā€‹ā€‹

Kas ir jauki, iterācijas ietvaros, izmantojot mdb_cursor_get, mēs iegūstam ne tikai atslēgu, bet arī vērtību. Ja, lai izpildītu atlases nosacījumus, cita starpā ir jāpārbauda lauki no ieraksta vērtības daļas, tad tie ir diezgan pieejami bez papildu žestiem.

4.3. SakarÄ«bu modelÄ“Å”ana starp tabulām

LÄ«dz Å”im mums ir izdevies apsvērt visus aspektus, izstrādājot un strādājot ar vienas tabulas datubāzi. Var teikt, ka tabula ir sakārtotu ierakstu kopa, kas sastāv no viena veida atslēgu-vērtÄ«bu pāriem. Ja atslēgu parādāt kā taisnstÅ«ri un ar to saistÄ«to vērtÄ«bu kā lodziņu, tiek iegÅ«ta datu bāzes vizuāla diagramma.

ā€‹

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Tomēr reālajā dzÄ«vē ar tik mazu asiņu maz izdodas iztikt. Bieži vien datu bāzē, pirmkārt, ir nepiecieÅ”amas vairākas tabulas un, otrkārt, tajās jāveic atlase secÄ«bā, kas atŔķiras no primārās atslēgas. Å Ä« pēdējā sadaļa ir veltÄ«ta to izveides un savstarpējās savienojamÄ«bas jautājumiem.

Indeksu tabulas

Mākoņa lietotnē ir sadaļa "Galerija". Tas parāda multivides saturu no visa mākoņa, sakārtots pēc datuma. Šādas atlases optimālai ievieÅ”anai blakus galvenajai tabulai ir jāizveido cita ar jauna veida taustiņiem. Tajos bÅ«s lauks ar faila izveides datumu, kas darbosies kā galvenais ŔķiroÅ”anas kritērijs. Tā kā jaunās atslēgas attiecas uz tiem paÅ”iem datiem kā atslēgas pamatā esoÅ”ajā tabulā, tās sauc par indeksa atslēgām. Zemāk esoÅ”ajā attēlā tie ir izcelti oranžā krāsā.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Lai vienas datu bāzes ietvaros atdalÄ«tu dažādu tabulu atslēgas vienu no otras, tām visām ir pievienots papildu tehniskā lauka tableId. Padarot to par ŔķiroÅ”anas augstāko prioritāti, atslēgas grupēsim vispirms pa tabulām, bet jau tabulu iekÅ”pusē ā€“ saskaņā ar mÅ«su paÅ”u noteikumiem.ā€‹

Indeksa atslēga attiecas uz tiem paÅ”iem datiem kā primārā atslēga. Å Ä« Ä«paÅ”uma vienkārÅ”a ievieÅ”ana, saistot ar to primārās atslēgas vērtÄ«bas daļas kopiju, nav optimāla no vairākiem viedokļiem vienlaikus:ā€‹

  1. No vietas aizņemtā viedokļa metadati var būt diezgan bagāti.
  2. No veiktspējas viedokļa, jo, atjauninot mezgla metadatus, jums būs jāpārraksta divas atslēgas.
  3. Galu galā no koda atbalsta viedokļa, ja mēs aizmirstam atjaunināt datus vienai no atslēgām, mēs iegūsim smalku datu neatbilstības kļūdu krātuvē.

Tālāk mēs apsvērsim, kā novērst Å”os trÅ«kumus.

AttiecÄ«bu organizÄ“Å”ana starp tabulām

Modelis ir labi piemērots indeksa tabulas saistÄ«Å”anai ar galveno "atslēga kā vērtÄ«ba". Kā norāda nosaukums, indeksa ieraksta vērtÄ«bas daļa ir primārās atslēgas vērtÄ«bas kopija. Å Ä« pieeja novērÅ” visus iepriekÅ” uzskaitÄ«tos trÅ«kumus, kas saistÄ«ti ar primārā ieraksta vērtÄ«bas daļas kopijas saglabāŔanu. VienÄ«gā maksa ir tāda, ka, lai iegÅ«tu vērtÄ«bu pēc indeksa atslēgas, datu bāzei ir jāveic 2 vaicājumi, nevis viens. Shematiski iegÅ«tā datu bāzes shēma ir Ŕāda.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Cits modelis attiecÄ«bu organizÄ“Å”anai starp tabulām ir "lieka atslēga". Tās bÅ«tÄ«ba ir pievienot atslēgai papildu atribÅ«tus, kas nepiecieÅ”ami nevis ŔķiroÅ”anai, bet gan saistÄ«tās atslēgas atjaunoÅ”anai, taču Mail.ru Cloud lietojumprogrammā ir reāli tās izmantoÅ”anas piemēri, lai izvairÄ«tos no dziļas nirÅ”anas konkrētu iOS ietvaru kontekstā minÄ“Å”u fiktÄ«vu, bet saprotamāku piemēru.

Mākoņa mobilajiem klientiem ir lapa, kurā tiek parādÄ«ti visi faili un mapes, ko lietotājs ir kopÄ«gojis ar citiem cilvēkiem. Tā kā Ŕādu failu ir salÄ«dzinoÅ”i maz un ar tiem ir daudz specifiskas informācijas par publicitāti (kam tiek pieŔķirta piekļuve, ar kādām tiesÄ«bām utt.), nebÅ«tu racionāli to noslogot ar vērtÄ«bas daļu. rekords galvenajā tabulā. Tomēr, ja vēlaties Ŕādus failus parādÄ«t bezsaistē, jums tie joprojām ir kaut kur jāsaglabā. Dabisks risinājums ir tam izveidot atseviŔķu tabulu. Tālāk redzamajā diagrammā tās atslēgas prefikss ir ā€œPā€, un vietturi ā€œpropnameā€ var aizstāt ar konkrētāku vērtÄ«bu ā€œpubliskā informācijaā€.ā€‹

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Visi unikālie metadati, kuru dēļ tika izveidota jaunā tabula, tiek pārvietoti uz ieraksta vērtÄ«bu daļu. Tajā paŔā laikā es nevēlos dublēt datus par failiem un mapēm, kas jau ir saglabāti galvenajā tabulā. Tā vietā atslēgai "P" tiek pievienoti lieki dati lauku "mezgla ID" un "laikspiedola" veidā. Pateicoties viņiem, jÅ«s varat izveidot indeksa atslēgu, ar kuras palÄ«dzÄ«bu jÅ«s varat iegÅ«t primāro atslēgu, ar kuru visbeidzot jÅ«s varat iegÅ«t mezgla metadatus.

Secinājums

LMDB ievieÅ”anas rezultātus vērtējam pozitÄ«vi. Pēc tās pieteikumu iesaldÄ“Å”anas skaits samazinājās par 30%.

Atslēgu vērtību datu bāzes LMDB spožums un nabadzība iOS lietojumprogrammās

Paveiktā darba rezultāti ir atraduÅ”i atsaucÄ«bu ārpus iOS komandas. Å obrÄ«d uz LMDB lietoÅ”anu ir pārgājusi arÄ« viena no galvenajām sadaļām "Faili" Android aplikācijā, un ceļā ir arÄ« citas daļas. C valoda, kurā ir ieviesta atslēgas vērtÄ«bu krātuve, bija labs palÄ«gs, lai sākotnēji padarÄ«tu lietojumprogrammu saistoÅ”u ap to starpplatformu C ++ valodā. Nevainojamai iegÅ«tās C ++ bibliotēkas savienoÅ”anai ar platformas kodu objektos Objective-C un Kotlin tika izmantots kodu Ä£enerators. Džinni no Dropbox, bet tas ir cits stāsts.

Avots: www.habr.com

Pievieno komentāru