Fil-ħarifa tal-2019, seħħ avveniment tant mistenni fit-tim Mail.ru Cloud iOS. Id-database prinċipali għall-ħażna persistenti tal-istat tal-applikazzjoni saret eżotika ħafna għad-dinja mobbli Bażi tad-Database tal-Memorja tas-Sajjetti (LMDB). Taħt il-qatgħa noffrulek reviżjoni dettaljata tagħha f'erba 'partijiet. L-ewwel, ejja nitkellmu dwar ir-raġunijiet għal tali għażla mhux trivjali u diffiċli. Imbagħad se ngħaddu biex nikkunsidraw it-tliet pilastri fil-qalba tal-arkitettura LMDB: fajls mappjati bil-memorja, siġra B+, approċċ ta 'kopja fuq kitba għall-implimentazzjoni tat-tranżazzjoni u l-multiverżjoni. Fl-aħħarnett, għad-deżerta - il-parti prattika. Fiha se nħarsu lejn kif tiddisinja u timplimenta skema ta 'database b'diversi tabelli, inkluża waħda ta' indiċi, fuq l-API ta 'valur ewlieni ta' livell baxx.

Kontenut

1. Motivazzjoni għall-implimentazzjoni
2. Pożizzjonament LMDB
3. Tliet pilastri tal-LMDB
   3.1. Balieni #1. Fajls mappjati bil-memorja
   3.2. Balieni #2. B+-siġra
   3.3. Balieni #3. Kopja fuq il-kitba
4. Iddisinjar ta' skema tad-dejta fuq l-API tal-valur ewlieni
   4.1. Astrazzjonijiet bażiċi
   4.2. Immudellar tal-mejda
   4.3. Immudellar ta' relazzjonijiet bejn it-tabelli

1. Motivazzjoni għall-implimentazzjoni

Sena fl-2015, ħadna l-inkwiet biex inkejlu kemm-il darba l-interface tal-applikazzjoni tagħna jonqos. Għamilna dan għal raġuni. Irċevejna ilmenti aktar frekwenti li xi drabi l-applikazzjoni tieqaf tirrispondi għall-azzjonijiet tal-utent: il-buttuni ma jistgħux jiġu ppressati, il-listi ma jiskrolljawx, eċċ. Dwar il-mekkanika tal-kejl qal fuq AvitoTech, għalhekk hawn nagħti biss l-ordni tan-numri.

Ir-riżultati tal-kejl saru doċċa kiesħa għalina. Irriżulta li hemm ħafna aktar problemi kkawżati mill-iffriżar minn kwalunkwe oħra. Jekk qabel ma rrealizzaw dan il-fatt l-indikatur tekniku ewlieni tal-kwalità kien ħieles mill-ħabta, imbagħad wara l-fokus imċaqlaq fuq freeze free.

Wara li bnew dashboard bl-iffriżar u wara l-infiq kwantitattivi и kwalità analiżi tar-raġunijiet tagħhom, l-għadu ewlieni sar ċar - loġika tan-negozju tqil esegwiti fil-ħajt prinċipali tal-applikazzjoni. Ir-reazzjoni naturali għal din l-għajb kienet xewqa taħraq li titfagħha fil-flussi tax-xogħol. Biex insolvu din il-problema b'mod sistematiku, irrikorrejna għal arkitettura b'ħafna kamini bbażata fuq atturi ħfief. Iddedikajtha għall-adattament tagħha għad-dinja tal-iOS żewġ ħjut fuq Twitter kollettiv u artiklu dwar Habré. Bħala parti min-narrattiva attwali, irrid nenfasizza dawk l-aspetti tad-deċiżjoni li influwenzaw l-għażla tad-database.

Il-mudell tal-attur tal-organizzazzjoni tas-sistema jassumi li l-multithreading isir it-tieni essenza tiegħu. Oġġetti mudell fiha jħobbu jaqsmu l-konfini tan-nixxiegħa. U jagħmlu dan mhux kultant u hawn u hemm, iżda kważi kontinwament u kullimkien.​

Id-database hija waħda mill-komponenti tal-pedament fid-dijagramma ppreżentata. Il-kompitu ewlieni tiegħu huwa li jimplimenta l-makromudell Database Kondiviża. Jekk fid-dinja tal-intrapriża tintuża biex torganizza s-sinkronizzazzjoni tad-dejta bejn is-servizzi, allura fil-każ tal-arkitettura tal-attur - data bejn il-ħjut. Għalhekk, kellna bżonn database li lanqas ma tikkawża diffikultajiet minimi meta naħdmu magħha f'ambjent multi-threaded. B'mod partikolari, dan ifisser li l-oġġetti miksuba minnu għandhom ikunu mill-inqas siguri għall-ħajt, u idealment kompletament mhux mutevoli. Kif tafu, dan tal-aħħar jista 'jintuża simultanjament minn diversi ħjut mingħajr ma jirrikorru għal xi qfil, li għandu effett ta' benefiċċju fuq il-prestazzjoni.

It-tieni fattur sinifikanti li influwenza l-għażla tad-database kien l-API tal-cloud tagħna. Kien ispirat mill-approċċ ta 'sinkronizzazzjoni adottat minn git. Bħalu, immirajna offline-ewwel API, li jidher aktar minn xieraq għall-klijenti tal-cloud. Ġie preżunt li kienu se jippompjaw l-istat sħiħ tas-sħab darba biss, u mbagħad is-sinkronizzazzjoni fil-maġġoranza assoluta tal-każijiet isseħħ permezz tat-tnedija tal-bidliet. Alas, din l-opportunità għadha biss fiż-żona teoretika, u l-klijenti ma tgħallmux kif jaħdmu bl-irqajja fil-prattika. Hemm numru ta’ raġunijiet oġġettivi għal dan, li, biex ma tittardmux l-introduzzjoni, se nħallu warajhom parentesi. Issa, dak li huwa ta 'ħafna aktar interess huma l-konklużjonijiet istruttivi tal-lezzjoni dwar x'jiġri meta API tgħid "A" u l-konsumatur tagħha ma jgħidx "B".

Għalhekk, jekk timmaġina git, li, meta tesegwixxi kmand tal-ġibda, minflok tapplika irqajja għal snapshot lokali, tqabbel l-istat sħiħ tagħha mal-istat sħiħ tas-server, allura jkollok idea pjuttost preċiża ta’ kif isseħħ is-sinkronizzazzjoni fil-cloud klijenti. Huwa faċli li taqta 'li biex timplimentaha, trid talloka żewġ siġar DOM fil-memorja b'meta-informazzjoni dwar is-server u l-fajls lokali kollha. Jirriżulta li jekk utent jaħżen 500 elf fajl fis-sħaba, allura biex tissinkronizzaha huwa meħtieġ li terġa 'tinħoloq u teqred żewġ siġar b'1 miljun nodi. Iżda kull node huwa aggregat li fih graff ta 'suboġetti. F'dan id-dawl, ir-riżultati tal-profiling kienu mistennija. Irriżulta li anki mingħajr ma jittieħed kont tal-algoritmu tal-għaqda, il-proċedura stess tal-ħolqien u sussegwentement tal-qerda ta 'numru kbir ta' oġġetti żgħar tiswa Penny pjuttost Is-sitwazzjoni hija aggravata mill-fatt li l-operazzjoni bażika ta 'sinkronizzazzjoni hija inkluża f'numru kbir. ta' skripts tal-utent. Bħala riżultat, aħna niffissaw it-tieni kriterju importanti fl-għażla ta 'database - il-kapaċità li timplimenta operazzjonijiet CRUD mingħajr allokazzjoni dinamika ta' oġġetti.

Rekwiżiti oħra huma aktar tradizzjonali u l-lista kollha tagħhom hija kif ġej.

1. Sigurtà tal-ħajt.
2. Multiproċessar. Dettat mix-xewqa li tuża l-istess bażi tad-database biex tissinkronizza l-istat mhux biss bejn il-ħjut, iżda wkoll bejn l-applikazzjoni ewlenija u l-estensjonijiet tal-iOS.
3. Il-ħila li tirrappreżenta entitajiet maħżuna bħala oġġetti mhux mutevoli.​
4. L-ebda allokazzjonijiet dinamiċi fi ħdan l-operazzjonijiet CRUD.
5. Appoġġ ta 'tranżazzjoni għal proprjetajiet bażiċi ACID: atomiċità, konsistenza, iżolament u affidabbiltà.
6. Veloċità fuq l-aktar każijiet popolari.

B'dan is-sett ta 'rekwiżiti, SQLite kien u jibqa' għażla tajba. Madankollu, bħala parti mill-istudju tal-alternattivi, iltqajt ma’ ktieb "Nibdew b'LevelDB". Taħt it-tmexxija tagħha, inkiteb benchmark li jqabbel il-veloċità tax-xogħol ma 'databases differenti f'xenarji ta' cloud reali. Ir-riżultat qabeż l-aktar aspettattivi selvaġġi tagħna. Fil-każijiet l-aktar popolari - jkollna cursor fuq lista magħżula tal-fajls kollha u lista magħżula tal-fajls kollha għal direttorju partikolari - LMDB irriżulta li kien 10 darbiet aktar mgħaġġel minn SQLite. L-għażla saret ovvja.

2. Pożizzjonament LMDB

LMDB hija librerija żgħira ħafna (10K ringieli biss) li timplimenta l-iktar saff fundamentali baxx ta 'databases - ħażna.

Id-dijagramma t'hawn fuq turi li t-tqabbil ta 'LMDB ma' SQLite, li jimplimenta wkoll livelli ogħla, ġeneralment mhuwiex aktar korrett minn SQLite b'Dejta Core. Ikun aktar ġust li jiġu kkwotati l-istess magni tal-ħażna bħal kompetituri ugwali - BerkeleyDB, LevelDB, Sophia, RocksDB, eċċ Hemm ukoll żviluppi fejn LMDB jaġixxi bħala komponent tal-magna tal-ħażna għal SQLite. L-ewwel esperiment bħal dan kien fl-2012 jintefqu minn LMDB Howard Chu. Sejbiet rriżulta li kien tant intriganti li l-inizjattiva tiegħu ttieħdet mid-dilettanti tal-OSS, u sabet il-kontinwazzjoni tagħha fil-persuna LumoSQL. F'Jannar 2020, l-awtur ta' dan il-proġett kien Den Shearer ippreżentati hija fuq LinuxConfAu.

LMDB jintuża prinċipalment bħala magna għal databases ta 'applikazzjoni. Il-librerija għandha d-dehra tagħha lill-iżviluppaturi OpenLDAP, li ma kinux sodisfatti ħafna b'BerkeleyDB bħala l-bażi għall-proġett tagħhom. Nibda minn librerija modesta btree, Howard Chu kien kapaċi joħloq waħda mill-aktar alternattivi popolari ta 'żmienna. Huwa ddedika r-rapport sabiħ ħafna tiegħu għal din l-istorja, kif ukoll għall-istruttura interna tal-LMDB. "Id-Database tal-Mappa tal-Memorja Lightning". Eżempju tajjeb ta 'konkwista ta' faċilità ta 'ħażna kien maqsum minn Leonid Yuryev (magħruf ukoll bħala yleo) minn Positive Technologies fir-rapport tiegħu f'Highload 2015 "Il-magna LMDB hija champion speċjali". Fiha, huwa jitkellem dwar LMDB fil-kuntest ta 'kompitu simili ta' implimentazzjoni ta 'ReOpenLDAP, u LevelDB diġà kien soġġett għal kritika komparattiva. Bħala riżultat tal-implimentazzjoni, Teknoloġiji Pożittivi saħansitra kellhom furketta li qed tiżviluppa b'mod attiv MDBX b'karatteristiċi fit-togħma ħafna, ottimizzazzjonijiet u bugfixes.

L-LMDB spiss jintuża bħala ħażna kif inhi. Per eżempju, Mozilla Firefox browser għażel hija għal numru ta 'bżonnijiet, u, li jibda mill-verżjoni 9, Xcode preferut SQLite tagħha għall-ħażna ta 'indiċi.

Il-magna għamlet ukoll il-marka tagħha fid-dinja tal-iżvilupp mobbli. It-traċċi tal-użu tiegħu jistgħu jkunu biex issib fil-klijent iOS għal Telegram. LinkedIn mar aktar 'il quddiem u għażel l-LMDB bħala l-ħażna awtomatika għall-qafas ta' caching tad-dejta homegrown tiegħu Rocket Data, li dwaru qal fl-artiklu tiegħu fl-2016.

LMDB qed jiġġieled b'suċċess għal post fix-xemx fin-niċċa li ħalla BerkeleyDB wara li ġiet taħt il-kontroll ta 'Oracle. Il-librerija hija maħbuba għall-veloċità u l-affidabbiltà tagħha, anke meta mqabbla ma 'sħabha. Kif tafu, m'hemm l-ebda ikliet b'xejn, u nixtieq nenfasizza l-kompromess li ser ikollok tiffaċċja meta tagħżel bejn LMDB u SQLite. Id-dijagramma t'hawn fuq turi biċ-ċar kif tinkiseb veloċità akbar. L-ewwel, ma nħallsux għal saffi addizzjonali ta 'estrazzjoni fuq il-ħażna tad-disk. Huwa ċar li arkitettura tajba għadha ma tistax tgħaddi mingħajrhom, u inevitabbilment se jidhru fil-kodiċi tal-applikazzjoni, iżda se jkunu ħafna aktar sottili. Mhux se jkun fihom karatteristiċi li mhumiex meħtieġa minn applikazzjoni speċifika, pereżempju, appoġġ għal mistoqsijiet fil-lingwa SQL. It-tieni, isir possibbli li jiġi implimentat bl-aħjar mod l-immappjar tal-operazzjonijiet tal-applikazzjoni fuq talbiet għall-ħażna tad-disk. Jekk SQLite fil-ħidma tiegħi huwa bbażat fuq il-ħtiġijiet statistiċi medji ta 'applikazzjoni medja, allura inti, bħala żviluppatur ta' applikazzjoni, tkun konxju sew tax-xenarji ewlenin ta 'tagħbija tax-xogħol. Għal soluzzjoni aktar produttiva, ser ikollok tħallas prezz miżjud kemm għall-iżvilupp tas-soluzzjoni inizjali kif ukoll għall-appoġġ sussegwenti tagħha.

3. Tliet pilastri tal-LMDB

Wara li ħares lejn l-LMDB minn għajn ta' għasfur, kien wasal iż-żmien li nidħlu aktar fil-fond. It-tliet taqsimiet li ġejjin se jkunu ddedikati għal analiżi tal-pilastri ewlenin li fuqhom tistrieħ l-arkitettura tal-ħażna:

1. Fajls mappjati bil-memorja bħala mekkaniżmu biex taħdem mad-disk u tissinkronizza strutturi interni tad-dejta.
2. B+-siġra bħala organizzazzjoni tal-istruttura tad-dejta maħżuna.
3. Kopja fuq il-kitba bħala approċċ biex tipprovdi proprjetajiet ta 'tranżazzjoni ACID u multiversion.

3.1. Balieni #1. Fajls mappjati bil-memorja

Fajls mappjati bil-memorja huma element arkitettoniku tant importanti li saħansitra jidhru fl-isem tar-repożitorju. Kwistjonijiet ta 'caching u sinkronizzazzjoni ta' aċċess għall-informazzjoni maħżuna jitħallew kompletament għas-sistema operattiva. LMDB ma fih l-ebda caches fih innifsu. Din hija deċiżjoni konxja mill-awtur, peress li l-qari tad-dejta direttament minn fajls mapep jippermettilek li tnaqqas ħafna kantunieri fl-implimentazzjoni tal-magna. Hawn taħt hawn lista 'l bogħod milli kompluta ta' xi wħud minnhom.

1. Iż-żamma tal-konsistenza tad-data fil-ħażna meta taħdem magħha minn diversi proċessi ssir ir-responsabbiltà tas-sistema operattiva. Fit-taqsima li jmiss, din il-mekkanika hija diskussa fid-dettall u bi stampi.
2. In-nuqqas ta 'caches jelimina kompletament l-LMDB mill-overhead assoċjat ma' allokazzjonijiet dinamiċi. Il-qari tad-dejta fil-prattika jfisser li jistabbilixxi pointer għall-indirizz korrett fil-memorja virtwali u xejn aktar. Jidher bħal fantaxjenza, iżda fil-kodiċi tas-sors tal-ħażna is-sejħiet kollha lil calloc huma kkonċentrati fil-funzjoni tal-konfigurazzjoni tal-ħażna.
3. In-nuqqas ta 'caches tfisser ukoll in-nuqqas ta' serraturi assoċjati mas-sinkronizzazzjoni tal-aċċess tagħhom. Qarrejja, li minnhom jista 'jkun hemm numru arbitrarju ta' qarrejja fl-istess ħin, ma jiltaqgħux ma 'mutex wieħed fi triqthom lejn id-dejta. Minħabba dan, il-veloċità tal-qari għandha skalabbiltà lineari ideali bbażata fuq in-numru ta 'CPUs. Fl-LMDB, l-operazzjonijiet ta 'modifika biss huma sinkronizzati. Jista’ jkun hemm biss kittieb wieħed kull darba.
4. Minimu ta 'caching u loġika ta' sinkronizzazzjoni jelimina t-tip estremament kumpless ta 'żbalji assoċjati max-xogħol f'ambjent b'ħafna kamini. Kien hemm żewġ studji ta 'database interessanti fil-konferenza Usenix OSDI 2014: "Is-Sistemi kollha tal-Fajls Mhumiex Maħluqin Indaqs: Dwar il-Kumplessità ta' Crafting Applikazzjonijiet Konsistenti għall-Ħbit" и "Databases ta' Tortura għall-Pjaċir u l-Qligħ". Minnhom tista 'tiġbor informazzjoni kemm dwar l-affidabbiltà bla preċedent ta' LMDB kif ukoll l-implimentazzjoni kważi bla difetti tal-proprjetajiet tat-tranżazzjonijiet ACID, li hija superjuri għal dik ta 'SQLite.
5. Il-minimalism ta 'LMDB jippermetti li r-rappreżentazzjoni tal-magna tal-kodiċi tagħha tkun kompletament lokalizzata fil-cache L1 tal-proċessur bil-karatteristiċi tal-veloċità li jirriżultaw.

Sfortunatament, fl-iOS, b'fajls mappjati għall-memorja, kollox mhuwiex bla sħab kif nixtiequ. Biex titkellem dwar in-nuqqasijiet assoċjati magħhom b'mod aktar konxju, huwa meħtieġ li tiftakar il-prinċipji ġenerali tal-implimentazzjoni ta 'dan il-mekkaniżmu fis-sistemi operattivi.

Informazzjoni ġenerali dwar fajls mappjati bil-memorja

Ma 'kull applikazzjoni li taħdem, is-sistema operattiva tassoċja entità msejħa proċess. Kull proċess huwa allokat firxa kontigwi ta 'indirizzi li fihom iqiegħed dak kollu li jeħtieġ biex jopera. Fl-indirizzi l-aktar baxxi hemm sezzjonijiet b'kodiċi u data u riżorsi hard-coded. Wara jiġi blokka dejjem tikber ta 'spazju ta' indirizzi dinamiku, magħrufa sew lilna taħt l-isem heap. Fih l-indirizzi tal-entitajiet li jidhru waqt it-tħaddim tal-programm. Fuq nett hemm iż-żona tal-memorja użata mill-munzell tal-applikazzjoni. Hija jew tikber jew tikkuntratta; fi kliem ieħor, id-daqs tiegħu għandu wkoll natura dinamika. Biex jipprevjenu l-munzell u l-munzell milli jimbuttaw u jinterferixxu ma 'xulxin, jinsabu fi truf differenti tal-ispazju tal-indirizz.​ Hemm toqba bejn iż-żewġ sezzjonijiet dinamiċi fil-parti ta' fuq u t'isfel. Is-sistema operattiva tuża indirizzi f'din it-taqsima tan-nofs biex tassoċja varjetà ta 'entitajiet mal-proċess. B'mod partikolari, tista 'tassoċja ċertu sett kontinwu ta' indirizzi ma 'fajl fuq id-diska. Fajl bħal dan jissejjaħ memory-mapped.​

L-ispazju tal-indirizzi allokat għall-proċess huwa enormi. Teoretikament, in-numru ta 'indirizzi huwa limitat biss mid-daqs tal-pointer, li huwa determinat mill-kapaċità tal-bit tas-sistema. Kieku l-memorja fiżika tiġi mmappjata lilha 1-to-1, allura l-ewwel proċess jitla' r-RAM kollha, u ma jkunx hemm diskors dwar xi multitasking.

Madanakollu, mill-esperjenza tagħna nafu li s-sistemi operattivi moderni jistgħu simultanjament jeżegwixxu proċessi kemm mixtieq. Dan huwa possibbli minħabba l-fatt li jallokaw ħafna memorja biss għal proċessi fuq il-karta, iżda fir-realtà jgħabbu fil-memorja fiżika prinċipali biss dik il-parti li hija mitluba hawn u issa. Għalhekk, il-memorja assoċjata ma 'proċess tissejjaħ virtwali.

Is-sistema operattiva torganizza memorja virtwali u fiżika f'paġni ta 'ċertu daqs. Hekk kif ċerta paġna ta 'memorja virtwali tkun mitluba, is-sistema operattiva tagħbha fil-memorja fiżika u tqabbelhom f'tabella speċjali. Jekk ma jkunx hemm slots b'xejn, allura waħda mill-paġni mgħobbija qabel tiġi kkupjata fuq id-diska, u dik fid-domanda tieħu postha. Din il-proċedura, li se nerġgħu lura għaliha dalwaqt, tissejjaħ skambju. Il-figura hawn taħt turi l-proċess deskritt. Fuqha, il-paġna A bl-indirizz 0 ġiet mgħobbija u mqiegħda fuq il-paġna tal-memorja prinċipali bl-indirizz 4. Dan il-fatt kien rifless fit-tabella ta’ korrispondenza fiċ-ċellula numru 0.​

L-istorja hija eżattament l-istess b'fajls mappjati għall-memorja. Loġikament, huma allegatament jinsabu kontinwament u kompletament fl-ispazju tal-indirizz virtwali. Madankollu, jidħlu fil-memorja fiżika paġna b'paġna u biss fuq talba. Modifika ta 'paġni bħal dawn hija sinkronizzata mal-fajl fuq disk. B'dan il-mod, tista 'twettaq I/O tal-fajl billi sempliċement taħdem b'bytes fil-memorja - il-bidliet kollha jiġu trasferiti awtomatikament mill-qalba tas-sistema operattiva għall-fajl sors.​
​
L-immaġni hawn taħt turi kif LMDB jissinkronizza l-istat tiegħu meta jaħdem mad-database minn proċessi differenti. Billi nimmappjaw il-memorja virtwali ta' proċessi differenti fl-istess fajl, aħna de facto nobbligaw lis-sistema operattiva biex tissinkronizza b'mod tranżittiv ċerti blokki tal-ispazji tal-indirizzi tagħhom ma' xulxin, fejn jidher l-LMDB.​
​

Sfumatura importanti hija li LMDB, b'mod awtomatiku, jimmodifika l-fajl tad-dejta permezz tal-mekkaniżmu tas-sejħa tas-sistema tal-kitba, u juri l-fajl innifsu f'modalità ta 'qari biss. Dan l-approċċ għandu żewġ konsegwenzi importanti.

L-ewwel konsegwenza hija komuni għas-sistemi operattivi kollha. L-essenza tagħha hija li żżid protezzjoni kontra ħsara mhux intenzjonata lid-database b'kodiċi żbaljat. Kif tafu, l-istruzzjonijiet eżekutibbli ta 'proċess huma ħielsa li jaċċessaw id-dejta minn kullimkien fl-ispazju tal-indirizz tiegħu. Fl-istess ħin, kif għadna kif ftakarna, il-wiri ta 'fajl fil-modalità read-write ifisser li kwalunkwe istruzzjoni tista' wkoll timmodifikah. Jekk hi tagħmel dan bi żball, tipprova, pereżempju, li fil-fatt tikteb element ta 'firxa f'indiċi ineżistenti, allura hi tista' aċċidentalment tbiddel il-fajl immappjat għal dan l-indirizz, li jwassal għal korruzzjoni tad-database. Jekk il-fajl jintwera fil-modalità ta 'qari biss, allura tentattiv biex jinbidel l-ispazju tal-indirizz korrispondenti se jwassal għal terminazzjoni ta' emerġenza tal-programm b'sinjal. SIGSEGV, u l-fajl jibqa' intatt.

It-tieni konsegwenza hija diġà speċifika għall-iOS. La l-awtur u lanqas xi sorsi oħra ma jsemmuha b'mod espliċitu, iżda mingħajrha l-LMDB ma jkunx adattat biex jaħdem fuq din is-sistema operattiva mobbli. It-taqsima li jmiss hija ddedikata għall-konsiderazzjoni tagħha.

Speċifiċitajiet ta 'fajls mappjati bil-memorja fl-iOS

Kien hemm rapport mill-isbaħ fil-WWDC fl-2018 "Memorja iOS Deep Dive". Jgħidilna li fl-iOS, il-paġni kollha li jinsabu fil-memorja fiżika huma wieħed minn 3 tipi: maħmuġin, kompressati u nodfa.

Memorja nadifa hija ġabra ta’ paġni li jistgħu jinħattu mingħajr tbatija mill-memorja fiżika. Id-dejta li jkun fihom tista’ terġa’ tiġi mgħobbija kif meħtieġ mis-sorsi oriġinali tagħha. Fajls mappjati bil-memorja li jinqraw biss jaqgħu f'din il-kategorija. iOS ma jibżax li jħottu l-paġni mmappjati għal fajl mill-memorja fi kwalunkwe ħin, peress li huma garantiti li jkunu sinkronizzati mal-fajl fuq disk.
​
Il-paġni kollha modifikati jispiċċaw f'memorja maħmuġa, irrispettivament minn fejn kienu oriġinarjament jinsabu. B'mod partikolari, fajls mappjati bil-memorja modifikati bil-kitba fil-memorja virtwali assoċjata magħhom se jiġu kklassifikati b'dan il-mod. Ftuħ LMDB bil-bandiera MDB_WRITEMAP, wara li tagħmel bidliet fiha, tista' tivverifika dan personalment.​

Hekk kif applikazzjoni tibda tieħu wisq memorja fiżika, iOS jissuġġettaha għal kompressjoni tal-paġna maħmuġa. Il-memorja totali okkupata minn paġni maħmuġin u kkompressati tikkostitwixxi l-hekk imsejħa footprint tal-memorja tal-applikazzjoni. Ladarba jilħaq ċertu valur limitu, id-daemon tas-sistema tal-qattiel OOM jiġi wara l-proċess u jtemmha bil-forza. Din hija l-partikolarità tal-iOS meta mqabbla mas-sistemi operattivi tad-desktop. B'kuntrast, it-tnaqqis tal-footprint tal-memorja billi tiskambja l-paġni mill-memorja fiżika għad-diska mhix ipprovduta fl-iOS.Ir-raġunijiet jistgħu biss jiġu guessed. Forsi l-proċedura li tiċċaqlaq b'mod intensiv il-paġni lejn id-diska u lura tikkonsma wisq enerġija għal apparati mobbli, jew iOS jiffranka r-riżors ta 'kitba mill-ġdid taċ-ċelloli fuq drives SSD, jew forsi d-disinjaturi ma kinux sodisfatti bil-prestazzjoni ġenerali tas-sistema, fejn kollox huwa kontinwament skambjati. Kemm hu hekk, il-fatt jibqa’ fatt.

L-aħbar it-tajba, diġà msemmija qabel, hija li l-LMDB awtomatikament ma jużax il-mekkaniżmu mmap biex jaġġorna l-fajls. Dan ifisser li d-dejta murija hija kklassifikata minn iOS bħala memorja nadifa u ma tikkontribwixxix għall-impronta tal-memorja. Tista' tivverifika dan billi tuża għodda Xcode imsejħa VM Tracker. Il-screenshot hawn taħt turi l-istat tal-memorja virtwali tal-iOS tal-applikazzjoni Cloud waqt it-tħaddim. Fil-bidu, 2 istanzi LMDB ġew inizjalizzati fiha. L-ewwel tħalla juri l-fajl tiegħu fuq 1GiB ta 'memorja virtwali, it-tieni - 512MiB. Minkejja l-fatt li ż-żewġ ħażniet jokkupaw ċertu ammont ta 'memorja residenti, l-ebda wieħed minnhom ma jikkontribwixxi daqs maħmuġ.

U issa wasal iż-żmien għal aħbar ħażina. Grazzi għall-mekkaniżmu ta 'skambju f'sistemi operattivi desktop ta' 64-bit, kull proċess jista 'jokkupa spazju ta' indirizz virtwali daqs kemm jippermetti l-ispazju liberu tal-hard disk għat-tpartit potenzjali tiegħu. Is-sostituzzjoni tat-tpartit bil-kompressjoni fl-iOS tnaqqas radikalment il-massimu teoretiku. Issa l-proċessi kollha ħajjin iridu jidħlu fil-memorja prinċipali (aqra RAM), u dawk kollha li ma jidħlux għandhom jiġu sfurzati li jtemmu. Dan huwa ddikjarat kif imsemmi hawn fuq tirrapporta, u fi dokumentazzjoni uffiċjali. Bħala konsegwenza, iOS jillimita severament l-ammont ta 'memorja disponibbli għall-allokazzjoni permezz ta' mmap. Hawn hawn Tista 'tħares lejn il-limiti empiriċi tal-ammont ta' memorja li jista 'jiġi allokat fuq apparati differenti bl-użu ta' din is-sejħa tas-sistema. Fuq l-aktar mudelli moderni ta 'smartphone, iOS sar ġeneruż b'2 gigabytes, u fuq verżjonijiet ta' fuq tal-iPad - minn 4. Fil-prattika, ovvjament, trid tiffoka fuq l-iktar mudelli ta 'apparat appoġġjati, fejn kollox huwa imdejjaq ħafna. Saħansitra agħar, billi tħares lejn l-istat tal-memorja tal-applikazzjoni f'VM Tracker, issib li LMDB huwa 'l bogħod mill-uniku wieħed li jallega li huwa mmappjat bil-memorja. Bċejjeċ tajbin jittieklu minn allokaturi tas-sistema, fajls tar-riżorsi, oqfsa tal-immaġni, u predaturi iżgħar oħra.

Ibbażat fuq ir-riżultati ta 'esperimenti fil-Cloud, wasalna għall-valuri ta' kompromess li ġejjin għall-memorja allokata mill-LMDB: 384 megabytes għal apparati 32-bit u 768 għal apparati 64-bit. Wara li dan il-volum ikun użat, kwalunkwe operazzjoni ta 'modifika tibda tispiċċa bil-kodiċi MDB_MAP_FULL. Aħna nosservaw żbalji bħal dawn fil-monitoraġġ tagħna, iżda huma żgħar biżżejjed li f'dan l-istadju jistgħu jiġu traskurati.

Raġuni mhux ovvja għal konsum eċċessiv tal-memorja mill-ħażna jistgħu jkunu tranżazzjonijiet li jservu għal żmien twil. Biex nifhmu kif dawn iż-żewġ fenomeni huma konnessi, se nkunu megħjunin billi nikkunsidraw iż-żewġ pilastri li fadal tal-LMDB.

3.2. Balieni #2. B+-siġra

Biex timita tabelli fuq ħażna ta' valur ewlieni, l-operazzjonijiet li ġejjin għandhom ikunu preżenti fl-API tagħha:

1. Daħħal element ġdid.
2. Fittex għal element b'ċavetta partikolari.
3. Tneħħija ta' element.
4. Itteri fuq intervalli ta 'ċwievet fl-ordni li huma magħżula.

L-istruttura tad-dejta l-aktar sempliċi li tista 'faċilment timplimenta l-erba' operazzjonijiet kollha hija siġra ta 'tfittxija binarja. Kull wieħed min-nodi tiegħu jirrappreżenta ċavetta li jaqsam is-subsett kollu ta 'ċwievet tfal f'żewġ subtrees. Ix-xellug fih dawk li huma iżgħar mill-ġenitur, u dak tal-lemin fih dawk li huma akbar. Il-ksib ta' sett ordnat ta' ċwievet jinkiseb permezz ta' waħda mill-traverses klassiċi tas-siġar.​

Is-siġar binarji għandhom żewġ difetti fundamentali li jipprevjenuhom milli jkunu effettivi bħala struttura tad-dejta bbażata fuq disk. L-ewwelnett, il-grad tal-bilanċ tagħhom huwa imprevedibbli. Hemm riskju konsiderevoli li jinkisbu siġar li fihom l-għoli ta 'fergħat differenti jistgħu jvarjaw ħafna, li jaggrava b'mod sinifikanti l-kumplessità algoritmika tat-tfittxija meta mqabbla ma' dak li huwa mistenni. It-tieni nett, l-abbundanza ta 'cross-links bejn in-nodi ċċaħħad is-siġar binarji mill-lokalità fil-memorja.Nodi mill-qrib (f'termini ta' konnessjonijiet bejniethom) jistgħu jinstabu fuq paġni kompletament differenti fil-memorja virtwali. Bħala konsegwenza, anke sempliċi traversal ta 'diversi nodi ġirien f'siġra jista' jeħtieġ li jżuru numru komparabbli ta 'paġni. Din hija problema anke meta nitkellmu dwar l-effettività tas-siġar binarji bħala struttura tad-dejta fil-memorja, peress li l-paġni li jduru kontinwament fil-cache tal-proċessur mhuwiex pjaċir irħis. Meta niġu għall-irkupru ta 'spiss paġni assoċjati ma' nodi mid-disk, is-sitwazzjoni ssir kompletament deplorevoli.

Is-siġar B, li huma evoluzzjoni ta 'siġar binarji, isolvu l-problemi identifikati fil-paragrafu preċedenti. L-ewwelnett, huma awto-ibbilanċjar. It-tieni nett, kull nodi tagħhom jaqsam is-sett ta 'ċwievet tat-tfal mhux f'2, iżda f'sottogruppi M ordnati, u n-numru M jista' jkun pjuttost kbir, fuq l-ordni ta 'diversi mijiet, jew saħansitra eluf.

B'hekk:

1. Kull node fih numru kbir ta 'ċwievet diġà ordnati u s-siġar huma qosra ħafna.
2. Is-siġra takkwista l-proprjetà tal-lokalità tal-post fil-memorja, peress li ċwievet li huma qrib fil-valur jinsabu b'mod naturali ħdejn xulxin fuq l-istess nodi jew ġirien.
3. In-numru ta' nodi ta' transitu meta jinżlu siġra waqt operazzjoni ta' tfittxija jitnaqqas.
4. In-numru ta 'nodi fil-mira li jinqraw waqt il-mistoqsijiet tal-medda huwa mnaqqas, peress li kull wieħed minnhom diġà fih numru kbir ta' ċwievet ordnati.

LMDB juża varjazzjoni tas-siġra B imsejħa siġra B + biex jaħżen id-dejta. Id-dijagramma ta’ hawn fuq turi t-tliet tipi ta’ nodi li jeżistu fiha:

1. Fuq nett hemm l-għerq. Ma jimmaterjalizza xejn aktar mill-kunċett ta 'database ġewwa maħżen. F'istanza LMDB waħda, tista' toħloq diversi databases li jaqsmu spazju ta' indirizz virtwali mmappjat. Kull wieħed minnhom jibda mill-għerq tiegħu stess.
2. Fl-iktar livell baxx hemm il-weraq. Huma u huma biss fihom il-pari ewlenin-valur maħżuna fid-database. Mill-mod, din hija l-partikolarità tas-siġar B +. Jekk siġra B regolari taħżen partijiet ta 'valur f'nodi tal-livelli kollha, allura l-varjazzjoni B + hija biss fl-iktar waħda baxxa. Wara li ffissaw dan il-fatt, aħna se nsejħu aktar is-sottotip tas-siġra użata f'LMDB sempliċement siġra B.
3. Bejn l-għerq u l-weraq hemm 0 jew aktar livelli tekniċi b'nodi tan-navigazzjoni (fergħa). Il-kompitu tagħhom huwa li jaqsmu s-sett ta 'ċwievet magħżul bejn il-weraq.

Fiżikament, in-nodi huma blokki ta 'memorja ta' tul predeterminat. Id-daqs tagħhom huwa multiplu tad-daqs tal-paġni tal-memorja fis-sistema operattiva, li ddiskutejna hawn fuq. L-istruttura tan-nodi tidher hawn taħt. L-intestatura fiha meta informazzjoni, l-aktar ovvja li pereżempju hija ċ-checksum. Sussegwentement tiġi informazzjoni dwar l-offsets li fihom jinsabu ċ-ċelloli bid-dejta. Id-dejta tista’ tkun jew ċwievet, jekk qed nitkellmu dwar nodi tan-navigazzjoni, jew pari sħaħ ta’ valuri ewlenin fil-każ ta’ weraq.​ Tista’ taqra aktar dwar l-istruttura tal-paġni fix-xogħol "Evalwazzjoni ta' Ħażniet b'Valur Ewlenin ta' Prestazzjoni Għolja".

Wara li ttrattati l-kontenut intern tan-nodi tal-paġna, aħna se nirrappreżentaw aktar is-siġra B LMDB b'mod simplifikat fil-forma li ġejja.

Paġni b'nodi jinsabu sekwenzjali fuq disk. Paġni b'numri ogħla jinsabu lejn l-aħħar tal-fajl. L-hekk imsejħa paġna meta fiha informazzjoni dwar l-offsets li bihom jistgħu jinstabu l-għeruq tas-siġar kollha. Meta tiftaħ fajl, LMDB jiskenja l-fajl paġna b'paġna minn tarf sal-bidu biex ifittex meta paġna valida u permezz tagħha jsib databases eżistenti.​

Issa, wara li jkollna idea tal-istruttura loġika u fiżika tal-organizzazzjoni tad-dejta, nistgħu ngħaddu biex nikkunsidraw it-tielet pilastru tal-LMDB. Huwa bl-għajnuna tagħha li l-modifiki kollha tal-ħażna jseħħu transazzjonali u iżolati minn xulxin, u jagħtu lid-database kollha kemm hi l-proprjetà ta 'multiversion.

3.3. Balieni #3. Kopja fuq il-kitba

Xi operazzjonijiet tas-siġra B jinvolvu li tagħmel serje ta 'bidliet fin-nodi tagħha. Eżempju wieħed huwa li żżid ċavetta ġdida għal nodu li diġà laħaq il-kapaċità massima tiegħu. F'dan il-każ, huwa meħtieġ, l-ewwelnett, li n-nodu jinqasam fi tnejn, u t-tieni, li żżid link man-node tifel ġdid li jibża fil-ġenitur tiegħu. Din il-proċedura hija potenzjalment perikoluża ħafna. Jekk għal xi raġuni (ħabta, qtugħ tad-dawl, eċċ.) iseħħu biss parti mill-bidliet mis-serje, allura s-siġra tibqa 'fi stat inkonsistenti.

Soluzzjoni tradizzjonali waħda biex tagħmel database tolleranti għall-ħsarat hija li żżid struttura ta 'dejta addizzjonali fuq id-disk ħdejn is-siġra B - reġistru tat-tranżazzjonijiet, magħruf ukoll bħala reġistru ta' write-ahead (WAL). Huwa fajl li fit-tmiem tiegħu l-operazzjoni maħsuba tinkiteb strettament qabel ma timmodifika s-siġra B innifsu. Għalhekk, jekk tinstab korruzzjoni tad-dejta waqt l-awtodijanjosi, id-database tikkonsulta l-ġurnal biex tpoġġi lilha nnifisha fl-ordni.

L-LMDB għażel metodu differenti bħala mekkaniżmu ta' tolleranza ta' ħsarat, imsejjaħ copy-on-write. L-essenza tagħha hija li minflok taġġorna d-dejta fuq paġna eżistenti, l-ewwel tikkopjaha kompletament u tagħmel il-modifiki kollha fil-kopja.

Sussegwentement, sabiex id-dejta aġġornata tkun disponibbli, huwa meħtieġ li tinbidel il-link man-node li sar kurrenti fin-nodu prinċipali tiegħu. Peress li jeħtieġ ukoll li jiġi modifikat għal dan, huwa kkupjat ukoll minn qabel. Il-proċess ikompli b'mod rikkursiv sa l-għerq. L-aħħar ħaġa li trid tinbidel hija d-dejta fuq il-meta page.​​

Jekk f'daqqa waħda l-proċess jiġġarraf waqt il-proċedura ta 'aġġornament, allura jew meta paġna ġdida ma tinħoloqx, jew ma tinkiteb kompletament fuq id-diska, u s-checksum tagħha ma tkunx korretta. F'wieħed minn dawn iż-żewġ każijiet, paġni ġodda ma jkunux jistgħu jintlaħqu, iżda dawk qodma mhux se jiġu affettwati. Dan jelimina l-ħtieġa li l-LMDB jikteb bil-quddiem biex iżżomm il-konsistenza tad-dejta. De facto, l-istruttura tal-ħażna tad-data fuq id-diska deskritta hawn fuq simultanjament tieħu l-funzjoni tagħha. In-nuqqas ta' reġistru espliċitu tat-tranżazzjonijiet hija waħda mill-karatteristiċi tal-LMDB li tipprovdi veloċità għolja ta' qari tad-dejta.​

Id-disinn li jirriżulta, imsejjaħ append-only B-tree, naturalment jipprovdi iżolament tat-tranżazzjonijiet u multi-versioning. Fl-LMDB, kull tranżazzjoni miftuħa hija assoċjata mal-għerq tas-siġra rilevanti bħalissa. Sakemm titlesta t-tranżazzjoni, il-paġni tas-siġra assoċjati magħha qatt ma se jinbidlu jew jerġgħu jintużaw għal verżjonijiet ġodda tad-dejta.Għalhekk, tista 'taħdem għal kemm tixtieq bis-sett ta' dejta li kien rilevanti f'dak iż-żmien. it-tranżazzjoni nfetħet, anke jekk il-ħażna tkompli tiġi aġġornata b'mod attiv f'dan il-ħin. Din hija l-essenza tal-multiversion, li tagħmel l-LMDB sors ta 'dejta ideali għall-maħbubin tagħna UICollectionView. Wara li fetaħ tranżazzjoni, m'hemmx bżonn li tiżdied il-footprint tal-memorja tal-applikazzjoni billi tippumpja bil-għaġla data kurrenti f'xi struttura fil-memorja, minħabba l-biża' li titħalla mingħajr xejn. Din il-karatteristika tiddistingwi LMDB mill-istess SQLite, li ma jistax jiftaħar b'tali iżolament totali. Wara li fetaħ żewġ tranżazzjonijiet f'din tal-aħħar u ħassar ċertu rekord f'waħda minnhom, ma jkunx aktar possibbli li jinkiseb l-istess rekord fit-tieni wieħed li jkun fadal.

In-naħa ta 'wara tal-munita hija l-konsum potenzjalment ogħla b'mod sinifikanti tal-memorja virtwali. Is-slide turi kif se tidher l-istruttura tad-database jekk tiġi modifikata simultanjament bi 3 transazzjonijiet ta' qari miftuħa li tħares lejn verżjonijiet differenti tad-database. Peress li l-LMDB ma jistax jerġa' juża nodi li jistgħu jintlaħqu mill-għeruq assoċjati ma' tranżazzjonijiet kurrenti, il-maħżen m'għandux għażla ħlief li jalloka r-raba' għerq ieħor fil-memorja u għal darb'oħra jikklona l-paġni modifikati taħtu.

Hawnhekk ikun utli li wieħed ifakkar it-taqsima dwar il-fajls mappjati bil-memorja. Jidher li l-konsum addizzjonali tal-memorja virtwali m'għandux jinkwieta ħafna, peress li ma jikkontribwixxix għall-impronta tal-memorja tal-applikazzjoni. Madankollu, fl-istess ħin, ġie nnutat li iOS huwa stingy ħafna fl-allokazzjoni tiegħu, u ma nistgħux, bħal fuq server jew desktop, nipprovdu reġjun LMDB ta 'terabyte 1 u ma naħsbu xejn dwar din il-karatteristika. Jekk possibbli, għandek tipprova tagħmel il-ħajja tat-tranżazzjonijiet qasir kemm jista' jkun.

4. Iddisinjar ta' skema tad-dejta fuq l-API tal-valur ewlieni

Ejja nibdew l-analiżi tal-API tagħna billi nħarsu lejn l-astrazzjonijiet bażiċi pprovduti mill-LMDB: ambjent u databases, ċwievet u valuri, transazzjonijiet u cursors.

Nota dwar il-listi tal-kodiċi

Il-funzjonijiet kollha fl-API pubblika LMDB jirritorna r-riżultat tax-xogħol tagħhom fil-forma ta’ kodiċi ta’ żball, iżda fil-listi sussegwenti kollha l-verifika tagħha titħalla barra għal raġunijiet ta’ qosor.​ Fil-prattika, aħna saħansitra użajna tagħna stess biex jinteraġixxu mar-repożitorju furketta tgeżwir C++ lmdbxx, li fihom l-iżbalji huma mmaterjalizzati bħala eċċezzjonijiet C++.

Bħala l-aktar mod mgħaġġel biex tikkonnettja l-LMDB ma' proġett għal iOS jew macOS, nissuġġerixxi l-CocoaPod tiegħi POSLMDB.

4.1. Astrazzjonijiet bażiċi

Ambjent

Struttura MDB_env huwa r-repożitorju tal-istat intern tal-LMDB. Familja ta' funzjoni prefissata mdb_env jippermettilek tikkonfigura xi wħud mill-proprjetajiet tagħha. Fl-aktar każ sempliċi, l-inizjalizzazzjoni tal-magna tidher bħal din.

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

Fl-applikazzjoni Mail.ru Cloud, biddilna l-valuri awtomatiċi ta 'żewġ parametri biss.

L-ewwel waħda hija d-daqs tal-ispazju tal-indirizz virtwali li l-fajl tal-ħażna huwa mmappjat għalih. Sfortunatament, anke fuq l-istess apparat, il-valur speċifiku jista 'jvarja b'mod sinifikanti minn ġirja għal oħra. Biex tqis din il-karatteristika ta 'iOS, il-volum massimu tal-ħażna jintgħażel b'mod dinamiku. Jibda minn ċertu valur, huwa sekwenzjali bin-nofs sal-funzjoni mdb_env_open mhux se jirritorna riżultat differenti minn ENOMEM. Fit-teorija, hemm ukoll il-mod oppost - l-ewwel talloka minimu ta 'memorja għall-magna, u mbagħad, meta jiġu riċevuti żbalji, MDB_MAP_FULL, żidha. Madankollu, huwa ħafna aktar xewk. Ir-raġuni hija li l-proċedura għall-allokazzjoni mill-ġdid tal-memorja (remappa) bl-użu tal-funzjoni mdb_env_set_map_size jinvalida l-entitajiet kollha (kursuri, tranżazzjonijiet, ċwievet u valuri) preċedentement riċevuti mill-magna. Meta wieħed iqis dan it-tibdil tal-avvenimenti fil-kodiċi se jwassal għall-kumplikazzjoni sinifikanti tiegħu. Jekk, madankollu, il-memorja virtwali hija importanti ħafna għalik, allura din tista 'tkun raġuni biex tagħti ħarsa aktar mill-qrib lejn il-furketta li marret 'il quddiem. MDBX, fejn fost il-karatteristiċi mħabbra hemm "aġġustament awtomatiku tad-daqs tad-database fuq il-fly".

It-tieni parametru, li l-valur default tiegħu ma kienx adattat għalina, jirregola l-mekkanika biex tiġi żgurata s-sigurtà tal-ħajt. Sfortunatament, mill-inqas iOS 10 għandu problemi bl-appoġġ għall-ħażna lokali tal-ħajt. Għal din ir-raġuni, fl-eżempju ta 'hawn fuq, ir-repożitorju jinfetaħ bil-bandiera MDB_NOTLS. Minbarra dan, kien meħtieġ ukoll furketta tgeżwir C++ lmdbxxbiex maqtugħa varjabbli ma 'dan l-attribut u fiha.

Databases

Id-database hija eżempju separat tas-siġra B, li ddiskutejna hawn fuq. Il-ftuħ tiegħu jseħħ ġewwa tranżazzjoni, li għall-ewwel tista' tidher ftit stramba.

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

Tabilħaqq, tranżazzjoni f'LMDB hija entità ta' ħażna, mhux entità ta' database speċifika. Dan il-kunċett jippermettilek li twettaq operazzjonijiet atomiċi fuq entitajiet li jinsabu f'databases differenti. Fit-teorija, dan jiftaħ il-possibbiltà ta 'immudellar ta' tabelli fil-forma ta 'databases differenti, iżda f'ħin wieħed ħadt triq differenti, deskritta fid-dettall hawn taħt.

Ċwievet u valuri

Struttura MDB_val jimmudella l-kunċett kemm taċ-ċavetta kif ukoll tal-valur. Ir-repożitorju m'għandu l-ebda idea dwar is-semantika tagħhom. Għaliha, xi ħaġa oħra hija biss firxa ta 'bytes ta' daqs partikolari. Id-daqs massimu taċ-ċavetta huwa 512 bytes.

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

Bl-użu ta 'komparatur, il-maħżen jagħżel iċ-ċwievet f'ordni axxendenti. Jekk ma tissostitwihax ma' tiegħek, allura tintuża dik default, li tissortjahom byte b'byte f'ordni lessikografika.​

Tranżazzjonijiet

L-istruttura tat-tranżazzjoni hija deskritta fid-dettall fi kapitolu preċedenti, allura hawnhekk ser nirrepeti fil-qosor il-proprjetajiet ewlenin tagħhom:

1. Jappoġġja l-proprjetajiet bażiċi kollha ACID: atomiċità, konsistenza, iżolament u affidabbiltà. Ma nistax ma ninnota li hemm bug f'termini ta 'durabilità fuq macOS u iOS li ġie ffissat f'MDBX. Tista 'taqra aktar fil tagħhom README.
2. L-approċċ għall-multithreading huwa deskritt mill-iskema ta '"kittieb wieħed / qarrejja multipli". Il-kittieba jimblukkaw lil xulxin, imma ma jimblukkawx lill-qarrejja. Il-qarrejja ma jimblukkawx lill-kittieba jew lil xulxin.
3. Appoġġ għal transazzjonijiet nested.
4. Appoġġ multiversion.

Multiversion fl-LMDB hija tant tajba li nixtieq nuriha fl-azzjoni. Mill-kodiċi ta 'hawn taħt tista' tara li kull tranżazzjoni taħdem eżattament mal-verżjoni tad-database li kienet kurrenti fiż-żmien li nfetħet, tkun iżolata kompletament mill-bidliet sussegwenti kollha. L-inizjalizzazzjoni tal-ħażna u ż-żieda ta 'rekord tat-test magħha ma tirrappreżenta xejn interessanti, għalhekk dawn ir-ritwali jitħallew taħt l-ispoiler.

Żieda ta' dħul tat-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);

Nirrakkomanda li tipprova l-istess trick ma 'SQLite u tara x'jiġri.

Multiversion ġġib vantaġġi sbieħ ħafna għall-ħajja ta 'żviluppatur iOS. Billi tuża din il-proprjetà, tista 'taġġusta faċilment u b'mod naturali r-rata ta' aġġornament tas-sors tad-dejta għall-formoli tal-iskrin, ibbażata fuq konsiderazzjonijiet tal-esperjenza tal-utent. Pereżempju, ejja nieħdu karatteristika tal-applikazzjoni tal-Mail.ru Cloud bħal kontenut awtoloading mill-gallerija tal-midja tas-sistema. B'konnessjoni tajba, il-klijent huwa kapaċi jżid diversi ritratti kull sekonda mas-server. Jekk taġġorna wara kull download UICollectionView b'kontenut tal-midja fis-sħaba tal-utent, tista 'tinsa madwar 60 fps u scrolling bla xkiel matul dan il-proċess. Biex tipprevjeni aġġornamenti frekwenti tal-iskrin, trid b'xi mod tillimita r-rata li biha d-dejta tinbidel fis-sottostanti UICollectionViewDataSource.

Jekk id-database ma tappoġġjax multiversion u tippermettilek taħdem biss ma 'l-istat attwali attwali, allura biex toħloq stampa stabbli fil-ħin tad-data għandek bżonn tikkopjaha jew għal xi struttura ta' data fil-memorja jew għal tabella temporanja. Kwalunkwe minn dawn l-approċċi jiswa ħafna flus. Fil-każ ta 'ħażna fil-memorja, nikbru spejjeż kemm fil-memorja, ikkawżati mill-ħażna ta' oġġetti mibnija, kif ukoll fil-ħin, assoċjati ma 'trasformazzjonijiet ORM żejda. Fir-rigward tal-mejda temporanja, dan huwa pjaċir saħansitra aktar għali, li jagħmel sens biss f'każijiet mhux trivjali.

Is-soluzzjoni multiverżjoni ta 'LMDB issolvi l-problema taż-żamma ta' sors ta 'dejta stabbli b'mod eleganti ħafna. Huwa biżżejjed li tiftaħ tranżazzjoni u voila - sakemm tlestiha, is-sett tad-dejta huwa garantit li jiġi ffissat. Il-loġika għall-veloċità tal-aġġornament tagħha issa hija kompletament f'idejn is-saff tal-preżentazzjoni, mingħajr ebda overhead ta 'riżorsi sinifikanti.

Kursuri

Il-kursuri jipprovdu mekkaniżmu għall-iterazzjoni ordnata fuq pari ta' valuri ewlenin permezz ta' traversal tas-siġra B. Mingħajrhom, ikun impossibbli li jiġu mmudellati b'mod effettiv it-tabelli fid-database, li issa nduru għalihom.

4.2. Immudellar tal-mejda

Il-proprjetà ta 'ordnijiet ewlenin tippermettilek li tibni astrazzjoni ta' livell għoli bħal tabella fuq quċċata ta 'estrazzjonijiet bażiċi. Ejja nikkunsidraw dan il-proċess billi tuża l-eżempju tat-tabella prinċipali ta 'klijent tas-sħab, li tiġbor l-informazzjoni dwar il-fajls u l-folders kollha tal-utent.

Tabella schema

Wieħed mix-xenarji komuni li għalih għandha titfassal struttura ta' tabella b'siġra ta' folders hija l-għażla tal-elementi kollha li jinsabu f'direttorju partikolari. Mudell tajjeb ta' organizzazzjoni tad-dejta għal mistoqsijiet effiċjenti ta' dan it-tip huwa Lista ta 'Adjaċenza. Biex timplimentaha fuq il-ħażna tal-valur taċ-ċavetta, huwa meħtieġ li tissortja ċ-ċwievet tal-fajls u l-folders b'tali mod li jkunu miġbura skont is-sħubija tagħhom fid-direttorju prinċipali. Barra minn hekk, sabiex jintwera l-kontenut tad-direttorju fil-forma familjari għal utent tal-Windows (l-ewwel folders, imbagħad fajls, it-tnejn magħżula alfabetikament), huwa meħtieġ li jiġu inklużi l-oqsma addizzjonali korrispondenti fiċ-ċavetta.

L-istampa t'hawn taħt turi kif, abbażi tal-kompitu li jkun hemm, tista' tidher rappreżentazzjoni ta 'ċwievet fil-forma ta' firxa ta 'byte. Il-bytes bl-identifikatur tad-direttorju ġenitur (aħmar) jitqiegħdu l-ewwel, imbagħad bit-tip (aħdar) u fid-denb bl-isem (blu). Billi jiġu magħżula mill-komparatur LMDB default f'ordni lessikografika, huma ordnati fil- mod meħtieġ. It-traversing sekwenzjali taċ-ċwievet bl-istess prefiss aħmar jagħtina l-valuri assoċjati tagħhom fl-ordni li għandhom jintwerew fl-interface tal-utent (fuq il-lemin), mingħajr ma jeħtieġ ebda post-ipproċessar addizzjonali.

Serializing Keys u Valuri

Ġew ivvintati fid-dinja ħafna metodi għas-serjelizzazzjoni ta 'oġġetti. Peress li ma kellna l-ebda rekwiżit ieħor ħlief il-veloċità, għażilna l-aktar veloċi possibbli għalina - dump tal-memorja okkupata minn eżempju tal-istruttura tal-lingwa C. Għalhekk, iċ-ċavetta ta 'element tad-direttorju tista' tiġi mmudellata bl-istruttura li ġejja NodeKey.

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

Issalva NodeKey fil-ħażna meħtieġa fl-oġġett MDB_val poġġi l-pointer tad-data għall-indirizz tal-bidu tal-istruttura, u kkalkula d-daqs tagħhom bil-funzjoni sizeof.

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

Fl-ewwel kapitolu dwar il-kriterji tal-għażla tad-database, semmejt il-minimizzazzjoni tal-allokazzjonijiet dinamiċi fi ħdan l-operazzjonijiet CRUD bħala fattur importanti tal-għażla. Kodiċi tal-funzjoni serialize juri kif fil-każ tal-LMDB jistgħu jiġu evitati kompletament meta jiddaħħlu rekords ġodda fid-database. Il-firxa tal-byte li tidħol mis-server l-ewwel tiġi ttrasformata fi strutturi ta 'munzell, u mbagħad jintremew b'mod trivjali fil-ħażna. Meta wieħed iqis li hemm ukoll l-ebda allokazzjonijiet dinamiċi ġewwa LMDB, tista 'tikseb sitwazzjoni meraviljuża mill-istandards tal-iOS - uża biss memorja tal-munzell biex taħdem bid-dejta tul il-mogħdija kollha min-netwerk għad-diska!

Ordna ċwievet b'komparatur binarju

Ir-relazzjoni tal-ordni ewlenija hija speċifikata minn funzjoni speċjali msejħa komparatur. Peress li l-magna ma taf xejn dwar is-semantika tal-bytes li fihom, il-komparatur default m'għandux għażla ħlief li jirranġa ċ-ċwievet f'ordni lessikografika, billi jirrikorri għal paragun byte b'byte. Li tużaha biex torganizza strutturi hija simili għal tqaxxir b'mannara tat-tqattigħ. Madankollu, f'każijiet sempliċi nsib dan il-metodu aċċettabbli. L-alternattiva hija deskritta hawn taħt, iżda hawnhekk ser ninnota ftit rakes imxerrda tul din it-triq.

L-ewwel ħaġa li għandek tiftakar hija r-rappreżentazzjoni tal-memorja ta 'tipi ta' data primittivi. Għalhekk, fuq il-mezzi kollha tat-tuffieħ, varjabbli interi huma maħżuna fil-format Little Endian. Dan ifisser li l-byte l-inqas sinifikanti se jkun fuq ix-xellug, u mhux se jkun possibbli li jiġu ssortjati n-numri interi bl-użu ta 'paragun byte b'byte. Pereżempju, jekk tipprova tagħmel dan b'sett ta' numri minn 0 sa 511 se tipproduċi r-riżultat li ġej.

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

Biex issolvi din il-problema, in-numri interi għandhom jinħażnu fiċ-ċavetta f'format adattat għall-komparatur byte-byte. Funzjonijiet mill-familja jgħinuk twettaq it-trasformazzjoni meħtieġa hton* (partikolarment htons għal numri double-byte mill-eżempju).

Il-format għar-rappreżentazzjoni tal-kordi fl-ipprogrammar huwa, kif tafu, sħiħ istorja. Jekk is-semantika tal-kordi, kif ukoll il-kodifikazzjoni użata biex tirrappreżentahom fil-memorja, tissuġġerixxi li jista 'jkun hemm aktar minn byte wieħed għal kull karattru, allura huwa aħjar li immedjatament tabbanduna l-idea li tuża komparatur default.

It-tieni ħaġa li għandek iżżomm f'moħħok hija prinċipji ta' allinjament kompilatur tal-qasam tal-istruttura. Minħabba dawn, bytes b'valuri ta 'żibel jistgħu jiġu ffurmati fil-memorja bejn l-oqsma, li, ovvjament, tkisser l-għażla byte-byte. Biex telimina ż-żibel, trid jew tiddikjara l-oqsma f'ordni strettament definita, filwaqt li żżomm f'moħħok ir-regoli tal-allinjament, jew tuża l-attribut fid-dikjarazzjoni tal-istruttura packed.

Ordna ċwievet b'komparatur estern

Il-loġika tat-tqabbil ewlieni tista' tkun kumplessa wisq għal komparatur binarju. Waħda mill-ħafna raġunijiet hija l-preżenza ta 'oqsma tekniċi fi ħdan l-istrutturi. Se nispjega l-okkorrenza tagħhom billi tuża l-eżempju ta 'ċavetta għal element tad-direttorju li diġà huwa familjari għalina.

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

Minkejja s-sempliċità tagħha, fil-maġġoranza l-kbira tal-każijiet tikkonsma wisq memorja. Il-buffer għall-isem jieħu 256 bytes, għalkemm bħala medja l-ismijiet tal-fajls u l-folders rarament jaqbżu l-20-30 karattru.

Waħda mit-tekniki standard għall-ottimizzazzjoni tad-daqs ta 'rekord hija li "titnaqqas" għad-daqs attwali. L-essenza tagħha hija li l-kontenut tal-oqsma kollha ta 'tul varjabbli jinħażnu f'buffer fit-tarf tal-istruttura, u t-tulijiet tagħhom huma maħżuna f'varjabbli separati.​ Skont dan l-approċċ, iċ-ċavetta NodeKey tiġi trasformata kif ġej.

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

Barra minn hekk, meta ssir serje, id-daqs tad-dejta mhuwiex speċifikat sizeof l-istruttura kollha, u d-daqs tal-oqsma kollha huwa tul fiss flimkien mad-daqs tal-parti attwalment użata tal-buffer.

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

Bħala riżultat tar-refactoring, irċevejna tfaddil sinifikanti fl-ispazju okkupat minn ċwievet. Madankollu, minħabba l-qasam tekniku nameLength, il-komparatur binarju default m'għadux adattat għall-paragun ewlieni. Jekk ma nibdlux ma 'tagħna, allura t-tul tal-isem ikun fattur ta' prijorità ogħla fl-issortjar mill-isem innifsu.

LMDB jippermetti li kull database jkollha l-funzjoni ta 'tqabbil taċ-ċavetta tagħha stess. Dan isir bl-użu tal-funzjoni mdb_set_compare strettament qabel ma tiftaħ. Għal raġunijiet ovvji, ma tistax tinbidel matul il-ħajja tad-database. Il-komparatur jirċievi żewġ ċwievet f'format binarju bħala input, u fl-output jirritorna r-riżultat tat-tqabbil: inqas minn (-1), akbar minn (1) jew ugwali għal (0). Psewdokodiċi għal NodeKey qisu hekk.

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

Sakemm iċ-ċwievet kollha fid-database huma tal-istess tip, it-tidwir bla kundizzjoni tar-rappreżentazzjoni tal-byte tagħhom għat-tip tal-istruttura taċ-ċavetta tal-applikazzjoni hija legali. Hemm sfumatura waħda hawnhekk, iżda se tiġi diskussa hawn taħt fis-subtaqsima "Rekords tal-Qari".

Serializing Valuri

LMDB jaħdem b'mod estremament intensiv maċ-ċwievet tar-rekords maħżuna. It-tqabbil tagħhom ma 'xulxin iseħħ fil-qafas ta' kwalunkwe operazzjoni applikata, u l-prestazzjoni tas-soluzzjoni sħiħa tiddependi fuq il-veloċità tal-komparatur. F'dinja ideali, il-komparatur binarju default għandu jkun biżżejjed biex iqabbel iċ-ċwievet, imma jekk kellek tuża tiegħek, allura l-proċedura għad-deserializing taċ-ċwievet fiha għandha tkun malajr kemm jista 'jkun.

Id-database mhijiex partikolarment interessata fil-parti tal-valur tar-rekord (valur). Il-konverżjoni tiegħu minn rappreżentazzjoni ta 'byte għal oġġett iseħħ biss meta jkun diġà meħtieġ mill-kodiċi tal-applikazzjoni, pereżempju, biex juriha fuq l-iskrin. Peress li dan iseħħ relattivament rari, ir-rekwiżiti tal-veloċità għal din il-proċedura mhumiex daqshekk kritiċi, u fl-implimentazzjoni tagħha aħna ħafna aktar liberi li niffukaw fuq il-konvenjenza.Per eżempju, biex nisserielizzaw metadata dwar fajls li għadhom ma ġewx imniżżla, nużaw NSKeyedArchiver.

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

Madankollu, hemm drabi meta l-prestazzjoni għadha importanti. Pereżempju, meta nsalvaw metainformazzjoni dwar l-istruttura tal-fajl ta 'sħaba tal-utent, nużaw l-istess dump tal-memorja ta' oġġetti. Il-qofol tal-kompitu li tiġġenera rappreżentazzjoni serjali tagħhom hija l-fatt li l-elementi ta 'direttorju huma mmudellati minn ġerarkija ta' klassijiet.

Biex timplimentaha fil-lingwa C, oqsma speċifiċi tal-werrieta jitqiegħdu fi strutturi separati, u l-konnessjoni tagħhom ma 'dak bażi hija speċifikata permezz ta' qasam ta 'unjoni tat-tip. Il-kontenut attwali tal-unjoni huma speċifikati permezz tat-tip ta 'attribut tekniku.

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

Żieda u aġġornament tar-rekords

Iċ-ċavetta u l-valur serialized jistgħu jiġu miżjuda mal-maħżen. Biex tagħmel dan, uża l-funzjoni mdb_put.

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

Fl-istadju ta 'konfigurazzjoni, il-ħażna tista' tkun permessa jew ipprojbita milli taħżen rekords multipli bl-istess ċavetta.Jekk id-duplikazzjoni taċ-ċwievet hija pprojbita, allura meta ddaħħal rekord, tista 'tiddetermina jekk l-aġġornament ta' rekord eżistenti huwiex permess jew le. Jekk it-tifrik jista' jseħħ biss bħala riżultat ta' żball fil-kodiċi, allura tista' tipproteġi lilek innifsek minnu billi tispeċifika l-bandiera NOOVERWRITE.

Qari ta' daħliet

Biex taqra r-rekords fl-LMDB, uża l-funzjoni mdb_get. Jekk il-par ewlieni-valur huwa rappreżentat minn strutturi li qabel kienu ddampjati, allura din il-proċedura tidher bħal din.

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

Il-lista ppreżentata turi kif is-serialization permezz ta 'dump tal-istruttura tippermettilek teħles mill-allokazzjonijiet dinamiċi mhux biss meta tikteb, iżda meta taqra d-dejta. Derivat mill-funzjoni mdb_get il-pointer iħares eżattament lejn l-indirizz tal-memorja virtwali fejn id-database taħżen ir-rappreżentazzjoni tal-byte tal-oġġett. Fil-fatt, aħna tikseb tip ta 'ORM li jipprovdi veloċità għolja ħafna tal-qari tad-dejta kważi mingħajr ħlas. Minkejja s-sbuħija kollha tal-approċċ, huwa meħtieġ li tiftakar diversi karatteristiċi assoċjati magħha.

1. Għal tranżazzjoni readonly, il-pointer għall-istruttura tal-valur huwa ggarantit li jibqa' validu biss sakemm it-tranżazzjoni tingħalaq. Kif innutat qabel, il-paġni tas-siġra B li fuqhom jinsab oġġett, grazzi għall-prinċipju tal-kopja fuq il-kitba, jibqgħu mhux mibdula sakemm ikunu referenzjati minn tal-inqas transazzjoni waħda. Fl-istess ħin, hekk kif titlesta l-aħħar transazzjoni assoċjata magħhom, il-paġni jistgħu jerġgħu jintużaw għal data ġdida. Jekk ikun meħtieġ li l-oġġetti jibqgħu ħajjin it-tranżazzjoni li ġġenerathom, allura xorta jridu jiġu kkupjati.
2. ​​Għal transazzjoni ta’ readwrite, il-pointer għall-istruttura tal-valur li tirriżulta se jkun validu biss sal-ewwel proċedura ta’ modifika (kitba jew tħassir ta’ data).
3. Anke jekk l-istruttura NodeValue mhux sħiħ, iżda mirqum (ara s-subsezzjoni "Ordna ċwievet bl-użu ta 'paragun estern"), tista' taċċessa l-oqsma tagħha b'mod sikur permezz tal-pointer. Il-ħaġa prinċipali hija li ma dereference dan!
4. Taħt l-ebda ċirkostanza m'għandha tiġi modifikata l-istruttura permezz tal-pointer riċevut. Il-bidliet kollha għandhom isiru biss permezz tal-metodu mdb_put. Madankollu, tkun kemm trid tagħmel dan, mhux se jkun possibbli, peress li ż-żona tal-memorja fejn tinsab din l-istruttura hija mmappjata fil-modalità readonly.
5. Erġa' mmappja fajl fl-ispazju tal-indirizz tal-proċess bl-iskop li, pereżempju, jiżdied id-daqs massimu tal-ħażna bl-użu tal-funzjoni mdb_env_set_map_size jinvalida kompletament it-tranżazzjonijiet kollha u l-entitajiet relatati b'mod ġenerali u jindika ċerti oġġetti b'mod partikolari.

Fl-aħħarnett, karatteristika oħra hija tant insidjuża li tiżvela l-essenza tagħha ma tidħolx f'paragrafu ieħor biss. Fil-kapitolu dwar is-siġra B, tajt dijagramma ta 'kif il-paġni tagħha huma rranġati fil-memorja. Minn dan jirriżulta li l-indirizz tal-bidu tal-buffer b'dejta serializzata jista 'jkun assolutament arbitrarju. Minħabba dan, il-pointer għalihom irċieva fl-istruttura MDB_val u mnaqqsa għal pointer għal struttura, jirriżulta li mhux allinjat fil-każ ġenerali. Fl-istess ħin, l-arkitetturi ta 'xi ċipep (fil-każ ta' iOS dan huwa armv7) jeħtieġu li l-indirizz ta 'kwalunkwe data jkun multiplu tad-daqs tal-kelma tal-magna jew, fi kliem ieħor, id-daqs tal-bit tas-sistema ( għal armv7 huwa 32 bit). Fi kliem ieħor, operazzjoni bħal *(int *foo)0x800002 fuqhom hija ekwivalenti għal ħarba u twassal għall-eżekuzzjoni b’verdett EXC_ARM_DA_ALIGN. Hemm żewġ modi kif tevita destin daqshekk imdejjaq.

L-ewwel jonqos għall-ikkupjar preliminari tad-data fi struttura allinjata ovvjament. Pereżempju, fuq komparatur tad-dwana dan se jkun rifless kif ġej.

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

Mod alternattiv huwa li jinnotifika lill-kompilatur minn qabel li l-istrutturi tal-valur ewlieni jistgħu ma jkunux allinjati mal-attributi. aligned(1). Fuq ARM jista' jkollok l-istess effett tikseb u bl-użu tal-attribut ippakkjat. Meta wieħed iqis li jgħin ukoll biex jiġi ottimizzat l-ispazju okkupat mill-istruttura, dan il-metodu jidher preferibbli għalija, għalkemm приводит għal żieda fl-ispiża tal-operazzjonijiet tal-aċċess għad-dejta.

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

Firxa mistoqsijiet

Biex itenni fuq grupp ta 'rekords, LMDB jipprovdi astrazzjoni tal-cursor. Ejja nħarsu lejn kif taħdem magħha billi tuża l-eżempju ta 'tabella b'metadata tas-sħab tal-utent diġà familjari għalina.

Bħala parti mill-wiri ta 'lista ta' fajls f'direttorju, huwa meħtieġ li ssib iċ-ċwievet kollha li magħhom il-fajls u l-folders tat-tfal tagħha huma assoċjati. Fis-subsezzjonijiet preċedenti aħna magħżula ċ-ċwievet NodeKey tali li huma primarjament ordnati mill-ID tad-direttorju prinċipali. Għalhekk, teknikament, il-kompitu li jiġi rkuprat il-kontenut ta 'folder jaqa' biex jitqiegħed il-cursor fuq il-limitu ta 'fuq tal-grupp ta' ċwievet bi prefiss partikolari u mbagħad itertu sal-konfini t'isfel.

Il-limitu ta' fuq jista' jinstab direttament permezz ta' tfittxija sekwenzjali. Biex tagħmel dan, il-cursor jitqiegħed fil-bidu tal-lista sħiħa ta 'ċwievet fid-database u jiżdied aktar sakemm ċavetta bl-identifikatur tad-direttorju ġenitur tidher taħtha. Dan l-approċċ għandu 2 żvantaġġi ovvji:

1. Il-kumplessità tat-tfittxija lineari, għalkemm, kif inhu magħruf, fis-siġar b'mod ġenerali u f'siġra B b'mod partikolari tista' ssir f'ħin logaritmiku.
2. Għalxejn, il-paġni kollha ta' qabel dik li qed tiġi mfittxija jitneħħew mill-fajl għall-memorja prinċipali, li tiswa ħafna flus.

Fortunatament, l-API LMDB tipprovdi mod effettiv biex inizjalment jitqiegħed il-cursor. Biex tagħmel dan, għandek bżonn tiġġenera ċavetta li l-valur tagħha huwa ovvjament inqas minn jew ugwali għaċ-ċavetta li tinsab fil-limitu ta 'fuq tal-intervall. Per eżempju, fir-rigward tal-lista fil-figura ta 'hawn fuq, nistgħu nagħmlu ċavetta li fiha l-qasam parentId se jkun ugwali għal 2, u l-bqija kollha huma mimlija b'żerijiet. Tali ċavetta parzjalment mimlija hija fornuta lill-input tal-funzjoni mdb_cursor_get li jindika l-operazzjoni 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);

Jekk jinstab il-konfini ta’ fuq ta’ grupp ta’ ċwievet, allura ngħaddu fuqha sakemm jew niltaqgħu jew iċ-ċavetta tiltaqa’ ma’ oħra parentId, jew iċ-ċwievet ma jispiċċaw xejn.​

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

X'inhu sabiħ huwa li bħala parti mill-iterazzjoni bl-użu ta 'mdb_cursor_get, irridu mhux biss iċ-ċavetta, iżda wkoll il-valur. Jekk, sabiex tissodisfa l-kundizzjonijiet tat-teħid tal-kampjuni, għandek bżonn tiċċekkja, fost affarijiet oħra, l-oqsma mill-parti tal-valur tar-rekord, allura huma pjuttost aċċessibbli mingħajr ġesti addizzjonali.

4.3. Immudellar tar-relazzjonijiet bejn it-tabelli

Sa issa, irnexxielna nikkunsidraw l-aspetti kollha tat-tfassil u l-ħidma ma 'database ta' tabella waħda. Nistgħu ngħidu li tabella hija sett ta 'rekords magħżula li jikkonsistu mill-istess tip ta' pari ta 'key-value. Jekk turi ċavetta bħala rettangolu u l-valur assoċjat bħala parallelepiped, ikollok dijagramma viżwali tad-database.

​

Madankollu, fil-ħajja reali huwa rari possibbli li tgħaddi b'daqshekk ftit tixrid ta 'demm. Ħafna drabi f'database huwa meħtieġ, l-ewwelnett, li jkun hemm diversi tabelli, u t-tieni, li jsiru selezzjonijiet fihom f'ordni differenti miċ-ċavetta primarja. Din l-aħħar taqsima hija ddedikata għall-kwistjonijiet tal-ħolqien u l-interkonnessjoni tagħhom.

Tabelli tal-indiċi

L-applikazzjoni tas-sħab għandha taqsima "Gallerija". Hija turi kontenut tal-midja mill-sħaba kollu, magħżula skond id-data. Biex timplimenta għażla bħal din bl-aħjar mod, ħdejn it-tabella prinċipali għandek bżonn toħloq waħda oħra b'tip ġdid ta 'ċwievet. Se jkun fihom qasam bid-data li fiha nħoloq il-fajl, li se jaġixxi bħala l-kriterju primarju ta' għażla. Minħabba li ċ-ċwievet il-ġodda jirreferu għall-istess dejta bħaċ-ċwievet fit-tabella prinċipali, jissejħu ċwievet tal-indiċi. Fl-istampa hawn taħt huma enfasizzati bl-oranġjo.

Sabiex jiġu separati ċ-ċwievet ta' tabelli differenti minn xulxin fl-istess database, ġie miżjud tabellaId tal-field tekniku addizzjonali magħhom kollha. Billi nagħmluha l-ogħla prijorità għall-issortjar, se niksbu raggruppament taċ-ċwievet l-ewwel skont it-tabelli, u fi ħdan it-tabelli - skont ir-regoli tagħna stess.​

Iċ-ċavetta tal-indiċi tirreferi għall-istess dejta bħaċ-ċavetta primarja. Implimentazzjoni sempliċi ta 'din il-proprjetà billi tiġi assoċjata magħha kopja tal-parti tal-valur taċ-ċavetta primarja mhix l-aħjar minn diversi punti di vista:

1. F'termini ta 'spazju meħud, il-metadata tista' tkun pjuttost rikka.
2. Mil-lat tal-prestazzjoni, peress li meta taġġorna l-metadata ta 'node, ikollok terġa' tiktebha billi tuża żewġ ċwievet.
3. Mil-lat tal-appoġġ tal-kodiċi, jekk ninsew li naġġornaw id-dejta għal waħda miċ-ċwievet, se nġibu bug elużiv ta 'inkonsistenza tad-dejta fil-ħażna.

Sussegwentement, se nikkunsidraw kif neliminaw dawn in-nuqqasijiet.

Jorganizza relazzjonijiet bejn it-tabelli

Il-mudell huwa adattat tajjeb biex jgħaqqad it-tabella tal-indiċi mat-tabella prinċipali "ċavetta bħala valur". Kif jissuġġerixxi isimha, il-parti tal-valur tar-rekord tal-indiċi hija kopja tal-valur taċ-ċavetta primarja. Dan l-approċċ jelimina l-iżvantaġġi kollha msemmija hawn fuq assoċjati mal-ħażna ta 'kopja tal-parti tal-valur tar-rekord primarju. L-unika spiża hija li biex tikseb valur permezz taċ-ċavetta tal-indiċi, trid tagħmel 2 mistoqsijiet fid-database minflok waħda. Skematikament, l-iskema tad-database li tirriżulta tidher bħal din.

Mudell ieħor għall-organizzazzjoni tar-relazzjonijiet bejn it-tabelli huwa "ċavetta żejda". L-essenza tagħha hija li żżid attributi addizzjonali maċ-ċavetta, li huma meħtieġa mhux għall-issortjar, iżda biex tinħoloq mill-ġdid iċ-ċavetta assoċjata.Fl-applikazzjoni Mail.ru Cloud hemm eżempji reali tal-użu tagħha, madankollu, sabiex tiġi evitata adsa fil-fond. il-kuntest ta' oqfsa speċifiċi ta' iOS, se nagħti eżempju fittizju, iżda iżda aktar ċar.​

Il-klijenti tal-mowbajl tas-Cloud għandhom paġna li turi l-fajls u l-folders kollha li l-utent ikun qasam ma’ nies oħra. Peress li hemm relattivament ftit tali fajls, u hemm ħafna tipi differenti ta 'informazzjoni speċifika dwar il-pubbliċità assoċjata magħhom (min jingħata aċċess, b'liema drittijiet, eċċ.), mhux se jkun razzjonali li tiġi mgħobbija l-parti tal-valur tal- irreġistra fit-tabella prinċipali magħha. Madankollu, jekk trid turi tali fajls offline, xorta trid taħżenha x'imkien. Soluzzjoni naturali hija li tinħoloq tabella separata għaliha. Fid-dijagramma t'hawn taħt, iċ-ċavetta tagħha hija prefissata b'"P", u l-placeholder "propname" jista' jiġi sostitwit bil-valur aktar speċifiku "informazzjoni pubblika".​

Il-metadejta unika kollha, għall-fini tal-ħażna li nħolqot it-tabella l-ġdida, titqiegħed fil-parti tal-valur tar-rekord. Fl-istess ħin, ma tridx tidduplika d-dejta dwar fajls u folders li diġà huma maħżuna fit-tabella prinċipali. Minflok, id-dejta żejda hija miżjuda maċ-ċavetta "P" fil-forma tal-oqsma "ID tan-node" u "timestamp". Bis-saħħa tagħhom, tista 'tibni ċavetta ta' indiċi, li minnha tista 'tikseb ċavetta primarja, li minnha, finalment, tista' tikseb metadejta tan-nodi.

Konklużjoni

Aħna nivvalutaw ir-riżultati tal-implimentazzjoni tal-LMDB b'mod pożittiv. Wara dan, in-numru ta 'iffriżar ta' applikazzjoni naqas bi 30%.

Ir-riżultati tax-xogħol li sar resonaw lil hinn mit-tim tal-iOS. Bħalissa, waħda mit-taqsimiet ewlenin tal-"Fajls" fl-applikazzjoni tal-Android inbidel ukoll għall-użu tal-LMDB, u partijiet oħra qegħdin fi triqithom. Il-lingwa C, li fiha l-maħżen tal-valur ewlieni huwa implimentat, kienet ta 'għajnuna tajba biex inizjalment jinħoloq qafas ta' applikazzjoni madwarha cross-platform f'C++. Ġeneratur tal-kodiċi ntuża biex jgħaqqad bla xkiel il-librerija C++ li tirriżulta mal-kodiċi tal-pjattaforma f'Objettiv-C u Kotlin Djinni minn Dropbox, iżda dik hija storja kompletament differenti.

Sors: www.habr.com