Haustið 2019 átti sér stað langþráður atburður í Mail.ru Cloud iOS teyminu. Aðalgagnagrunnurinn fyrir viðvarandi geymslu á umsóknarstöðu er orðinn frekar framandi fyrir farsímaheiminn Lightning Memory-Mapped Database (LMDB). Undir klippingunni er athygli þinni boðið að ítarlegri endurskoðun hennar í fjórum hlutum. Í fyrsta lagi skulum við tala um ástæðurnar fyrir slíku óléttu og erfiðu vali. Þá skulum við halda áfram að íhuga þrjá hvali í hjarta LMDB arkitektúrsins: minniskortaðar skrár, B + tré, afrita-í-skrifa nálgun til að útfæra viðskipta- og fjölútgáfu. Að lokum, í eftirrétt - verklega hluti. Í henni munum við skoða hvernig á að hanna og innleiða grunnskema með nokkrum töflum, þar á meðal vísitölu, ofan á lág-stigi lykilgildi API.​

efni

1. Framkvæmd Hvatning
2. Staðsetning LMDB
3. Þrír hvalir LMDB
   3.1. Hvalur #1. Minniskortaðar skrár
   3.2. Hvalur #2. B+-tré
   3.3. Hvalur #3. copy-on-write
4. Að hanna gagnaskema ofan á lykilgildi API
   4.1. Grunnabstraktanir
   4.2. Borðlíkön
   4.3. Líkönun á tengslum milli taflna

1. Innleiðingarhvatning

Einu sinni á ári, árið 2015, sáum við um að taka mælikvarða á hversu oft viðmót forritsins okkar tefjast. Við gerðum þetta ekki bara. Við höfum sífellt fleiri kvartanir yfir því að stundum hættir forritið að bregðast við aðgerðum notenda: ekki er ýtt á hnappa, listar fletta ekki o.s.frv. Um vélfræði mælinga sagði á AvitoTech, svo hér gef ég aðeins upp röð talna.

Mælingarniðurstöðurnar urðu að kaldri sturtu fyrir okkur. Í ljós kom að vandamálin af völdum frosts eru mun meiri en nokkur önnur. Ef, áður en þú áttaði þig á þessari staðreynd, var aðal tæknivísirinn um gæði hrunlaus, þá eftir fókusinn færst til á frystingu.

Búin að byggja mælaborð með frosti og hafa eytt magnbundið и gæði greining á orsökum þeirra, aðal óvinurinn varð ljós - þungur viðskiptarökfræði framkvæmd í meginþræði forritsins. Eðlileg viðbrögð við þessari svívirðingu voru brennandi löngun til að troða því í vinnustrauma. Til kerfisbundinnar lausnar á þessu vandamáli gripum við til margþráða arkitektúr sem byggðist á léttum leikurum. Ég tileinkaði aðlögun hennar fyrir iOS heiminn tveir þræðir í sameiginlegu twitter og grein um Habré. Sem hluti af núverandi sögu vil ég leggja áherslu á þá þætti ákvörðunarinnar sem höfðu áhrif á val á gagnagrunninum

Leikaralíkan kerfisskipulags gerir ráð fyrir að fjölþráður verði annar kjarni þess. Líkanhlutir í henni fara gjarnan yfir þráðamörk. Og þetta gera þeir ekki stundum og sums staðar, heldur nánast stöðugt og alls staðar.

Gagnagrunnurinn er einn af hornsteinsþáttunum í skýringarmyndinni sem er kynnt. Meginverkefni þess er að útfæra makró mynstur Sameiginlegur gagnagrunnur. Ef í fyrirtækjaheiminum er það notað til að skipuleggja gagnasamstillingu milli þjónustu, þá þegar um er að ræða leikaraarkitektúr, gögn á milli þráða. Þess vegna þurftum við slíkan gagnagrunn sem að vinna með í fjölþráðu umhverfi veldur ekki einu sinni lágmarkserfiðleikum. Sérstaklega þýðir þetta að hlutir sem fengnir eru úr því verða að vera að minnsta kosti þráðlausir og helst alls ekki breytanlegir. Eins og þú veist er hægt að nota hið síðarnefnda samtímis úr nokkrum þráðum án þess að grípa til hvers konar læsinga, sem hefur jákvæð áhrif á frammistöðu.

Annar mikilvægi þátturinn sem hafði áhrif á val á gagnagrunninum var ský API okkar. Það var innblásið af git nálguninni við samstillingu. Eins og hann sem við stefndum á fyrsta forritaskil án nettengingar, sem lítur út fyrir að vera meira en viðeigandi fyrir viðskiptavini skýja. Gert var ráð fyrir að þeir myndu aðeins einu sinni dæla út öllu ástandi skýsins og þá myndi samstilling í langflestum tilfellum eiga sér stað með rúllandi breytingum. Því miður er þessi möguleiki enn aðeins á fræðilegu svæði og í reynd hafa viðskiptavinir ekki lært hvernig á að vinna með plástra. Fyrir því eru ýmsar málefnalegar ástæður sem við sleppum út fyrir sviga til að tefja ekki kynninguna. Nú eru miklu áhugaverðari lærdómsríkar niðurstöður kennslustundarinnar um hvað gerist þegar API sagði „A“ og neytandinn sagði ekki „B“.

Svo ef þú ímyndar þér git, sem, þegar þú framkvæmir pull skipun, í stað þess að nota plástra á staðbundna skyndimynd, ber saman heildarstöðu þess við fullan netþjóninn, þá munt þú hafa nokkuð nákvæma hugmynd um hvernig samstillingu er háttað. á sér stað í skýjabiðlara. Það er auðvelt að giska á að fyrir framkvæmd þess sé nauðsynlegt að úthluta tveimur DOM tré í minni með meta-upplýsingum um allar netþjóna og staðbundnar skrár. Það kemur í ljós að ef notandi geymir 500 þúsund skrár í skýinu, þá er nauðsynlegt að endurskapa og eyðileggja tvö tré með 1 milljón hnúta til að samstilla það. En hver hnút er samansafn sem inniheldur graf yfir undirhluti. Í þessu ljósi var búist við niðurstöðum prófílsins. Það kom í ljós að jafnvel án þess að taka tillit til samruna reikniritsins kostar sjálf aðferðin við að búa til og eyðileggja gríðarlegan fjölda lítilla hluta ansi eyri. Ástandið versnar af því að grunnsamstillingaraðgerðin er innifalin í miklum fjölda af notendaforskriftum. Fyrir vikið lagum við annað mikilvæga viðmiðið við val á gagnagrunni - getu til að innleiða CRUD aðgerðir án kraftmikillar úthlutunar hluta.

Aðrar kröfur eru hefðbundnari og heildarlisti þeirra er sem hér segir.

1. Þráðaröryggi.
2. Fjölvinnsla. Ráðist af lönguninni til að nota sama gagnagrunnstilvikið til að samstilla ástand, ekki aðeins á milli þráða, heldur einnig á milli aðalforritsins og iOS viðbætur.
3. Hæfni til að tákna geymdar einingar sem óbreytanlega hluti
4. Skortur á kraftmiklum úthlutunum innan CRUD starfsemi.
5. Viðskiptastuðningur fyrir grunneiginleika ACIDLykilorð: atómvirkni, samkvæmni, einangrun og áreiðanleiki.
6. Hraði á vinsælustu málum.

Með þessu setti af kröfum var SQLite og er enn góður kostur. Hins vegar, sem hluti af rannsókninni á valkostum, rakst ég á bók „Byrjað með LevelDB“. Undir stjórn hennar var skrifað viðmið sem ber saman hraða vinnu við mismunandi gagnagrunna í raunverulegum skýjaatburðum. Niðurstaðan fór fram úr björtustu vonum. Í vinsælustu tilfellunum - að fá bendil á flokkaðan lista yfir allar skrár og flokkaðan lista yfir allar skrár fyrir tiltekna möppu - reyndist LMDB vera 10 sinnum hraðari en SQLite. Valið varð augljóst.

2. LMDB staðsetning

LMDB er bókasafn, mjög lítið (aðeins 10K línur) sem útfærir lægsta grunnlag gagnagrunna - geymslu.

Skýringarmyndin hér að ofan sýnir að samanburður á LMDB við SQLite, sem útfærir enn hærri stig, er almennt ekki réttari en SQLite með Core Data. Það væri sanngjarnara að nefna sömu geymsluvélar sem jafna keppinauta - BerkeleyDB, LevelDB, Sophia, RocksDB o.s.frv. Það er jafnvel þróun þar sem LMDB virkar sem geymsluvélarhluti fyrir SQLite. Fyrsta slíka tilraunin árið 2012 eytt höfundur LMDB Howard Chu. Niðurstöður reyndist svo forvitnilegt að framtak hans var tekið upp af OSS-áhugamönnum og fann framhaldið í ljósi LumoSQL. Í janúar 2020 er höfundur þessa verkefnis Den Shearer fram það á LinuxConfAu.

Aðalnotkun LMDB er sem vél fyrir forritagagnagrunna. Bókasafnið á útlit sitt að þakka hönnuðum OpenLDAP, sem voru mjög óánægð með BerkeleyDB sem grundvöll verkefnis síns. Að ýta af sér hógværa bókasafninu btré, Howard Chu gat búið til einn vinsælasta valkost okkar tíma. Hann helgaði mjög flotta skýrslu sína þessari sögu, sem og innri uppbyggingu LMDB. "The Lightning Memory-kortlagður gagnagrunnur". Leonid Yuriev (aka yleo) frá Positive Technologies í ræðu sinni á Highload 2015 „LMDB vélin er sérstakur meistari“. Þar talar hann um LMDB í samhengi við svipað verkefni við innleiðingu ReOpenLDAP og hefur LevelDB þegar sætt samanburðargagnrýni. Sem afleiðing af innleiðingunni fékk Positive Technologies meira að segja virkan þróun gaffal MDBX með mjög bragðgóðum eiginleikum, hagræðingum og villuleiðréttingar.

LMDB er oft notað sem geymsla eins og er. Til dæmis Mozilla Firefox vafrinn valdi það fyrir ýmsar þarfir, og frá útgáfu 9, Xcode valinn SQLite þess til að geyma vísitölur.

Vélin tók einnig við sér í heimi farsímaþróunar. Ummerki um notkun þess geta verið finna í iOS biðlaranum fyrir Telegram. LinkedIn gekk einu skrefi lengra og valdi LMDB sem sjálfgefna geymslu fyrir heimaræktaða gagnageymsluramma sína, Rocket Data, um sagði í grein árið 2016.

LMDB er farsællega að berjast fyrir stað í sólinni í sess sem BerkeleyDB skildi eftir sig eftir umskipti undir stjórn Oracle. Bókasafnið er elskað fyrir hraða og áreiðanleika, jafnvel í samanburði við sína eigin tegund. Eins og þú veist, þá eru engir ókeypis hádegisverðir og ég vil undirstrika þá málamiðlun sem þú verður að horfast í augu við þegar þú velur á milli LMDB og SQLite. Skýringarmyndin hér að ofan sýnir greinilega hvernig auknum hraða er náð. Í fyrsta lagi borgum við ekki fyrir viðbótarlag af útdrætti ofan á diskgeymslu. Auðvitað, í góðum arkitektúr, geturðu samt ekki verið án þeirra, og þeir munu óhjákvæmilega birtast í forritskóðanum, en þeir verða miklu þynnri. Þeir munu ekki hafa eiginleika sem ekki er krafist af sérstöku forriti, til dæmis stuðningur við fyrirspurnir á SQL tungumálinu. Í öðru lagi verður mögulegt að innleiða kortlagningu forritsaðgerða á sem bestan hátt á beiðnir um diskgeymslu. Ef SQLite í starfi mínu kemur frá meðalþörfum meðalforrita, þá ertu, sem forritari, vel meðvitaður um helstu álagssviðsmyndir. Fyrir afkastameiri lausn verður þú að borga hærra verðmiða fyrir bæði þróun upphafslausnarinnar og síðari stuðning hennar.

3. Þrír hvalir LMDB

Eftir að hafa skoðað LMDB frá fuglasjónarhorni er kominn tími til að fara dýpra. Næstu þrír hlutar verða helgaðir greiningu á helstu hvölum sem geymsluarkitektúrinn hvílir á:

1. Minniskortaðar skrár sem vélbúnaður til að vinna með diska og samstilla innri gagnaskipulag.
2. B+-tré sem skipulag geymdra gagnaskipulags.
3. Afrita-í-skrifa sem aðferð til að veita ACID viðskiptaeiginleika og fjölútgáfu.

3.1. Hvalur #1. Minniskortaðar skrár

Minniskortaðar skrár eru svo mikilvægur byggingarþáttur að þær birtast jafnvel í nafni geymslunnar. Mál sem varða skyndiminni og samstillingu aðgangs að geymdum upplýsingum eru algjörlega á valdi stýrikerfisins. LMDB inniheldur engin skyndiminni í sjálfu sér. Þetta er meðvituð ákvörðun höfundar, þar sem lestur gagna beint úr kortlagðum skrám gerir þér kleift að skera mikið úr í útfærslu vélarinnar. Hér að neðan er langt frá því að vera tæmandi listi yfir sum þeirra.

1. Að viðhalda samræmi gagna í geymslunni þegar unnið er með þau úr nokkrum ferlum verður á ábyrgð stýrikerfisins. Í næsta kafla er fjallað ítarlega um þennan vélvirkja og með myndum.
2. Skortur á skyndiminni losar LMDB algjörlega við kostnaðinn sem tengist kraftmikilli úthlutun. Að lesa gögn í reynd er að stilla bendilinn á rétt heimilisfang í sýndarminni og ekkert annað. Hljómar eins og fantasía, en í geymsluuppsprettunni eru öll calloc símtöl einbeitt í geymslustillingaraðgerðinni.
3. Skortur á skyndiminni þýðir einnig skortur á læsingum sem tengjast samstillingu til að fá aðgang að þeim. Lesendur, þar sem handahófskenndur fjöldi getur verið til á sama tíma, lenda ekki í einu mutex á leið sinni að gögnunum. Vegna þessa hefur leshraðinn ákjósanlega línulegan sveigjanleika hvað varðar fjölda örgjörva. Í LMDB eru aðeins breytingaraðgerðir samstilltar. Það getur aðeins verið einn rithöfundur í einu.
4. Lágmarks skyndiminni og samstillingarrökfræði bjargar kóðanum frá afar flókinni tegund villna sem tengjast vinnu í fjölþráðu umhverfi. Það voru tvær áhugaverðar gagnagrunnsrannsóknir á Usenix OSDI 2014 ráðstefnunni: „Öll skráarkerfi eru ekki búin til jöfn: Um flókið þess að búa til hrunsamræmd forrit“ и Að pynta gagnagrunna sér til skemmtunar og gróða. Frá þeim er hægt að fá upplýsingar um bæði áður óþekktan áreiðanleika LMDB og næstum gallalausa útfærslu á ACID eiginleikum viðskipta, sem er umfram það í sama SQLite.
5. Naumhyggja LMDB gerir kleift að setja framsetningu vélarinnar á kóða sínum algjörlega í L1 skyndiminni örgjörvans með þeim hraðaeiginleikum sem af því koma.

Því miður, í iOS, eru minniskortaðar skrár ekki eins bjartar og við viljum. Til að tala meira meðvitað um ókostina sem tengjast þeim, er nauðsynlegt að muna almennar reglur um innleiðingu þessa kerfis í stýrikerfum.

Almennar upplýsingar um minniskortaðar skrár

Við hvert keyranlegt forrit tengir stýrikerfið einingu sem kallast ferli. Hvert ferli er úthlutað samfelldu úrvali heimilisfönga, þar sem það setur allt sem það þarf til að virka. Lægstu vistföngin innihalda hluta með kóða og harðkóðun gögn og tilföng. Næst kemur upp vaxandi blokk af kraftmiklu netfangarými, sem okkur er vel þekkt sem haugurinn. Það inniheldur heimilisföng aðila sem birtast meðan á rekstri forritsins stendur. Efst er minnissvæðið sem forritastokkurinn notar. Hann ýmist vex eða minnkar, með öðrum orðum, stærð hans hefur líka kraftmikið eðli. Svo að staflan og hrúgan ýti ekki og trufli hvort annað, eru þeir aðskildir á mismunandi endum heimilisfangsrýmisins. Það er gat á milli tveggja kraftmikilla hlutanna efst og neðst. Heimilisföngin í þessum miðhluta eru notuð af stýrikerfinu til að tengja við ferli ýmissa aðila. Sérstaklega getur það kortlagt ákveðið samfellt sett af vistföngum í skrá á diski. Slík skrá er kölluð minniskortuð skrá

Heimilisfangsrýmið sem er úthlutað ferli er gríðarstórt. Fræðilega séð er fjöldi vistfönga aðeins takmarkaður af stærð bendilsins, sem ræðst af bitleika kerfisins. Ef líkamlegt minni væri úthlutað 1-í-1, þá myndi fyrsta ferlið gleypa allt vinnsluminni og það væri engin spurning um fjölverkavinnsla.

Hins vegar vitum við af reynslu að nútíma stýrikerfi geta keyrt eins mörg ferli og þú vilt á sama tíma. Þetta er mögulegt vegna þess að þeir úthluta miklu minni til ferla eingöngu á pappír, en í raun hlaða þeir inn í aðal líkamlegt minni aðeins þann hluta sem er eftirsóttur hér og nú. Þess vegna er minnið sem tengist ferlinu kallað sýndar.

Stýrikerfið skipuleggur sýndar- og líkamlegt minni í síður af ákveðinni stærð. Um leið og eftirspurn er eftir ákveðinni síðu af sýndarminni hleður stýrikerfið henni inn í líkamlegt minni og setur samsvörun á milli þeirra í sérstaka töflu. Ef það eru engar lausar raufar, þá er ein af síðunum sem áður var hlaðið afrituð á diskinn og sú sem óskað er eftir kemur í staðinn. Þessi aðferð, sem við munum snúa aftur til fljótlega, kallast skipti. Myndin hér að neðan sýnir ferlinu sem lýst er. Á henni var síðu A með heimilisfangi 0 hlaðið inn og sett á aðalminnissíðu með heimilisfangi 4. Þessi staðreynd endurspeglaðist í samsvörunartöflunni í reit númer 0.​

Með minniskortuðum skrám er sagan nákvæmlega sú sama. Rökrétt er talið að þeir séu stöðugt og að öllu leyti settir í sýndar heimilisfangsrýmið. Hins vegar komast þeir inn í líkamlegt minni síðu fyrir síðu og aðeins eftir beiðni. Breytingar á slíkum síðum eru samstilltar við skrána á disknum. Þannig geturðu framkvæmt skrá I / O, einfaldlega að vinna með bæti í minni - allar breytingar verða sjálfkrafa fluttar af stýrikerfiskjarnanum í upprunalegu skrána.​
​
Myndin hér að neðan sýnir hvernig LMDB samstillir ástand sitt þegar unnið er með gagnagrunninn frá mismunandi ferlum. Með því að kortleggja sýndarminni mismunandi ferla á sömu skrána, skyldum við í reynd stýrikerfið til að samstilla ákveðna blokka af vistfangarýmum sínum innbyrðis, sem er þar sem LMDB lítur út.
​

Mikilvægur blæbrigði er að LMDB breytir gagnaskránni sjálfgefið í gegnum skrifakerfiskallabúnaðinn og skráin sjálf birtist í skrifvarandi ham. Þessi nálgun hefur tvær mikilvægar afleiðingar.

Fyrsta afleiðingin er sameiginleg öllum stýrikerfum. Kjarni þess er að bæta við vernd gegn óviljandi skemmdum á gagnagrunninum með röngum kóða. Eins og þú veist eru keyranlegar leiðbeiningar ferlis frjálsar til að fá aðgang að gögnum hvar sem er í vistfangarými þess. Á sama tíma, eins og við minntumst nýlega, þýðir það að birta skrá í lestur-skrifa ham að hvaða kennsla sem er getur einnig breytt henni til viðbótar. Ef hún gerir þetta fyrir mistök, reynir td að skrifa yfir fylkisþátt í vísitölu sem ekki er til, þá getur hún óvart breytt skránni sem var varpað á þetta heimilisfang, sem mun leiða til spillingar á gagnagrunni. Ef skráin er birt í skrifvarandi ham, þá mun tilraun til að breyta vistfangarýminu sem samsvarar henni leiða til þess að forritið hrynur með merkinu SIGSEGV, og skráin verður ósnortinn.

Önnur afleiðingin er nú þegar sérstök fyrir iOS. Hvorki höfundur né aðrar heimildir nefna það beinlínis, en án þess væri LMDB óhæft til að keyra á þessu farsímastýrikerfi. Næsti kafli er helgaður umfjöllun þess.

Upplýsingar um minniskortaðar skrár í iOS

Árið 2018 var dásamleg skýrsla á WWDC iOS Memory Deep Dive. Það segir að í iOS tilheyra allar síður sem staðsettar eru í líkamlegu minni einni af 3 gerðum: óhreinum, þjöppuðum og hreinum.

Hreint minni er safn af síðum sem hægt er að skipta á öruggan hátt úr líkamlegu minni. Gögnin sem þau innihalda má endurhlaða úr upprunalegum heimildum eftir þörfum. Skrifvarðar skrár með minnisminni falla í þennan flokk. iOS er ekki hræddur við að afhlaða síðurnar sem eru kortlagðar á skrá úr minni hvenær sem er, þar sem tryggt er að þær séu samstilltar við skrána á disknum.
​
Allar breyttar síður komast í skítugt minni, sama hvar þær eru upphaflega staðsettar. Einkum munu minniskortaðar skrár sem breyttar eru með því að skrifa í sýndarminni sem tengjast þeim einnig flokkast á þennan hátt. Opnun LMDB með fána MDB_WRITEMAP, eftir að hafa gert breytingar á því geturðu séð það sjálfur.​

Um leið og forrit byrjar að taka of mikið líkamlegt minni þjappar iOS saman óhreinum síðum sínum. Safn minnis sem er upptekið af óhreinum og þjöppuðum síðum er svokallað minnisfótspor forritsins. Þegar það nær ákveðnu þröskuldsgildi kemur OOM-drápskerfispúkinn á eftir ferlinu og slítur því með valdi. Þetta er sérkenni iOS miðað við skrifborðsstýrikerfi. Aftur á móti er ekki hægt að lækka minnisfótsporið með því að skipta um síður úr líkamlegu minni yfir á disk í iOS. Það er aðeins hægt að giska á ástæðurnar. Kannski er aðferðin við að færa síður á disk og til baka of orkufrekt fyrir farsíma, eða iOS sparar auðlindina við að endurskrifa frumur á SSD diskum, eða kannski voru hönnuðirnir ekki ánægðir með heildarframmistöðu kerfisins, þar sem allt er stöðugt skipt um. Hvað sem því líður þá er staðreyndin eftir.

Góðu fréttirnar, sem þegar eru nefndar áðan, eru þær að LMDB notar ekki mmap vélbúnaðinn til að uppfæra skrár sjálfgefið. Af þessu leiðir að gögnin eru flokkuð sem hreint minni af iOS og stuðla ekki að minnisfótsporinu. Þetta er hægt að staðfesta með Xcode tólinu sem kallast VM Tracker. Skjámyndin hér að neðan sýnir sýndarminnisstöðu iOS Cloud forritsins meðan á notkun stendur. Í upphafi voru 2 LMDB tilvik frumstillt í henni. Sá fyrri var leyft að kortleggja skrána sína í 1GiB af sýndarminni, sá síðari - 512MiB. Þrátt fyrir þá staðreynd að báðar geymslurnar taka tiltekið magn af vistminni, stuðlar hvorug þeirra að skítugu stærðinni.

Nú er kominn tími á slæmu fréttirnar. Þökk sé skiptibúnaðinum í 64-bita skrifborðsstýrikerfum getur hvert ferli tekið upp eins mikið sýndarvistfangapláss og laust pláss á harða disknum gerir ráð fyrir hugsanlegum skipti. Að skipta út swap fyrir þjöppun í iOS dregur verulega úr fræðilegu hámarki. Nú verða allir lifandi ferlar að passa inn í aðal (lesið vinnsluminni) minni og allir þeir sem passa ekki eru háðir þvinguðum uppsögn. Það er nefnt eins og að ofan skýrslu, og í opinber skjöl. Þar af leiðandi takmarkar iOS verulega magn af minni sem er tiltækt til úthlutunar í gegnum mmap. Hérna hér þú getur skoðað reynslutakmarkanir á magni minnis sem hægt er að úthluta á mismunandi tækjum með því að nota þetta kerfiskall. Á nýjustu gerðum snjallsíma er iOS orðið örlátt um 2 gígabæt og á toppútgáfum af iPad - um 4. Í reynd þarf auðvitað að einbeita sér að yngstu studdu tækjagerðunum þar sem allt er mjög sorglegt. Jafnvel verra, þegar þú horfir á minnisstöðu forritsins í VM Tracker, muntu komast að því að LMDB er langt frá því að vera sú eina sem gerir tilkall til minniskortsminni. Góðir bitar eru étnir af kerfisúthlutunaraðilum, auðlindaskrám, myndramma og öðrum smærri rándýrum.

Byggt á niðurstöðum tilrauna í skýinu komumst við að eftirfarandi málamiðlunargildum minni sem LMDB úthlutar: 384 megabæti fyrir 32-bita tæki og 768 fyrir 64-bita tæki. Eftir að þetta bindi er notað byrja allar breytingaraðgerðir að klárast með kóðanum MDB_MAP_FULL. Við sjáum slíkar villur í eftirliti okkar, en þær eru nógu litlar til að vera vanrækt á þessu stigi.

Óljós ástæða fyrir of mikilli minnisnotkun með geymslu getur verið langlíf viðskipti. Til að skilja hvernig þessi tvö fyrirbæri tengjast, mun það hjálpa okkur að íhuga tvo LMDB hvali sem eftir eru.

3.2. Hvalur #2. B+-tré

Til að líkja eftir töflum ofan á lykilgildageymslu verða eftirfarandi aðgerðir að vera til staðar í API þess:

1. Að setja inn nýjan þátt.
2. Leitaðu að þætti með tilteknum lykli.
3. Að eyða einingu.
4. Endurtekið yfir lykilbil í flokkunarröð þeirra.

Einfaldasta gagnauppbyggingin sem getur auðveldlega útfært allar fjórar aðgerðir er tvíundarleitartré. Hver hnútur hans er lykill sem skiptir öllu undirmengi barnalykla í tvö undirtré. Vinstra megin eru þeir sem eru minni en foreldrið og til hægri - þeir sem eru stærri. Að fá pantað sett af lyklum er náð með einni af klassísku trjáferðunum

Tvöfaldur tré hafa tvo grundvallargalla sem koma í veg fyrir að þau virki sem gagnauppbygging disks. Í fyrsta lagi er hversu jafnvægi þeirra er ófyrirsjáanlegt. Töluverð hætta er á að fá tré þar sem hæð mismunandi greinar getur verið mjög mismunandi, sem versnar verulega flókið reiknirit leitarinnar miðað við það sem búist er við. Í öðru lagi, gnægð krosstengsla milli hnúta sviptir tvöfalda tré staðsetningar í minni. Lokaðir hnútar (hvað varðar tengsl á milli þeirra) geta verið staðsettir á gjörólíkum síðum í sýndarminni. Afleiðingin er sú að jafnvel einföld ferð yfir nokkra nálæga hnúta í tré gæti þurft að heimsækja sambærilegan fjölda síðna. Þetta er vandamál jafnvel þegar við tölum um skilvirkni tvíundirtrjáa sem gagnauppbyggingar í minni, þar sem sífellt að snúa síðum í skyndiminni örgjörva er ekki ódýrt. Þegar það kemur að því að hækka oft hnúttengdar síður af diski, þá verða hlutirnir mjög slæmir. ömurlegt.

B-tré, sem eru þróun tvöfaldra trjáa, leysa vandamálin sem tilgreind eru í fyrri málsgrein. Í fyrsta lagi eru þeir í jafnvægi. Í öðru lagi skiptir hver hnútur þeirra hópnum af undirlykla ekki í 2, heldur í M raðað undirmengi, og talan M getur verið nokkuð stór, af stærðargráðunni nokkur hundruð eða jafnvel þúsundir.

Þar með:

1. Hver hnút hefur mikinn fjölda þegar pantaða lykla og trén eru mjög lág.
2. Tréð öðlast eign staðsetningar í minni, þar sem lyklar sem eru nálægt verðgildi eru náttúrulega staðsettir við hliðina á öðrum á einum eða nálægum hnútum.
3. Fækkar fjölda flutningshnúta þegar farið er niður tréð meðan á leitaraðgerð stendur.
4. Fækkar fjölda markhnúta sem lesnir eru fyrir sviðsfyrirspurnir, þar sem hver þeirra inniheldur nú þegar mikinn fjölda raðaðra lykla.

LMDB notar afbrigði af B-trénu sem kallast B+ tréð til að geyma gögn. Skýringarmyndin hér að ofan sýnir þrjár tegundir hnúta sem hún inniheldur:

1. Efst er rótin. Það er ekkert annað að veruleika en hugmyndina um gagnagrunn innan geymslu. Innan eins LMDB tilviks geturðu búið til marga gagnagrunna sem deila hinu kortlagða sýndarvistfangarými. Hver þeirra byrjar á sinni eigin rót.
2. Á neðsta stigi eru blöðin (blaðið). Það eru þeir og aðeins þeir sem innihalda lykilgildapörin sem eru geymd í gagnagrunninum. Við the vegur, þetta er sérkenni B+-tré. Ef venjulegt B-tré geymir gildishlutana á hnútum allra stiga, þá er B+-afbrigðið aðeins við það lægsta. Eftir að hafa lagað þessa staðreynd, í því sem hér á eftir kemur, munum við kalla undirgerð trésins sem notuð er í LMDB einfaldlega B-tré.
3. Á milli rótar og laufblaða eru 0 eða fleiri tæknistig með siglinga- (grein)hnútum. Verkefni þeirra er að skipta flokkuðu lyklasettinu á milli laufanna.

Líkamlega eru hnútar minnisblokkir af fyrirfram ákveðinni lengd. Stærð þeirra er margfeldi af stærð minnisblaðanna í stýrikerfinu, sem við ræddum um hér að ofan. Uppbygging hnútsins er sýnd hér að neðan. Hausinn inniheldur meta-upplýsingar, þær augljósustu eru til dæmis tékksumman. Næst koma upplýsingar um frávik, þar sem frumur með gögn eru staðsettar. Hlutverk gagna getur verið annað hvort lyklar, ef við erum að tala um leiðsöguhnúta, eða heil lykilgildapör ef um blöð er að ræða. Lesa má meira um uppbyggingu síðna í verkinu "Mat á afkastamiklum lykilgildum verslunum".

Eftir að hafa tekist á við innra innihald síðuhnúðanna munum við tákna LMDB B-tréð frekar á einfaldaðan hátt á eftirfarandi formi.

Síðum með hnútum er raðað í röð á diski. Síður með hærri tölu eru staðsettar í lok skráarinnar. Svokölluð metasíða (meta síða) inniheldur upplýsingar um frávik, sem hægt er að nota til að finna rætur allra trjáa. Þegar skrá er opnuð skannar LMDB skrána síðu fyrir síðu frá lokum til upphafs í leit að gildri metasíðu og finnur núverandi gagnagrunna í gegnum hana.

Nú, með hugmynd um rökrétta og líkamlega uppbyggingu gagnaskipulags, getum við haldið áfram að íhuga þriðja hvalinn af LMDB. Það er með hjálp hennar sem allar breytingar á geymslu eiga sér stað í viðskiptum og í einangrun hver frá annarri, sem gefur gagnagrunninum í heild sinni einnig fjölútgáfueiginleikann.

3.3. Hvalur #3. copy-on-write

Sumar B-tré aðgerðir fela í sér að gera fjölda breytinga á hnútum þess. Eitt dæmi er að bæta nýjum lykli við hnút sem hefur þegar náð hámarksgetu. Í þessu tilviki er nauðsynlegt, í fyrsta lagi, að skipta hnútnum í tvennt, og í öðru lagi að bæta við tengli við nýja spunna barnhnútinn í foreldri hans. Þessi aðferð er hugsanlega mjög hættuleg. Ef af einhverjum ástæðum (hrun, rafmagnsleysi o.s.frv.) verður aðeins hluti breytinganna úr seríunni, þá verður tréð áfram í ósamræmi.

Ein hefðbundin lausn til að gera gagnagrunn bilanaþolinn er að bæta við viðbótar gagnauppbyggingu sem byggir á diski, viðskiptaskránni, einnig þekktur sem WAL, við hlið B-trésins. Það er skrá, í lok hennar, nákvæmlega áður en B-trénu sjálfu er breytt, er fyrirhuguð aðgerð skrifuð. Þannig að ef gagnaspilling greinist við sjálfsgreiningu, leitar gagnagrunnurinn í annálinn til að hreinsa sig upp.

LMDB hefur valið aðra aðferð sem bilanaþolskerfi, sem kallast copy-on-write. Kjarni þess er að í stað þess að uppfæra gögnin á núverandi síðu, afritar það þau fyrst að öllu leyti og gerir allar breytingar sem þegar eru til í afritinu.

Ennfremur, til þess að uppfærð gögn séu tiltæk, er nauðsynlegt að breyta hlekknum á hnútinn sem er orðinn uppfærður í móðurhnútnum í tengslum við hann. Þar sem það þarf líka að breyta fyrir þetta er það líka forafritað. Ferlið heldur áfram endurkvæmt alla leið að rótinni. Gögnin á meta síðunni eru þau síðustu sem breytast.​

Ef ferlið hrynur skyndilega meðan á uppfærsluferlinu stendur, þá verður annað hvort ekki ný metasíða búin til, eða hún verður ekki skrifuð á diskinn fyrr en í lokin og eftirlitssumman hennar verður röng. Í öðru hvoru þessara tveggja tilvika verða nýju síðurnar óaðgengilegar og þær gömlu verða ekki fyrir áhrifum. Þetta útilokar þörfina fyrir LMDB að skrifa framundan annál til að viðhalda samkvæmni gagna. Reyndar tekur uppbygging gagnageymslu á disknum, sem lýst er hér að ofan, samtímis hlutverki sínu. Skortur á skýrri viðskiptaskrá er einn af eiginleikum LMDB, sem veitir mikinn gagnalestrarhraða.

Byggingin sem myndast, sem kallast append-only B-tree, veitir náttúrulega viðskiptaeinangrun og fjölútgáfu. Í LMDB hefur hver opin viðskipti uppfærða trjárót sem tengist henni. Svo lengi sem viðskiptunum er ekki lokið verður síðum trésins sem tengist því aldrei breytt eða endurnotað fyrir nýjar útgáfur af gögnum. Þannig geturðu unnið eins lengi og þú vilt nákvæmlega með gagnasettið sem átti við á þegar viðskiptin voru opnuð, jafnvel þó að geymslan haldi áfram að vera virkur uppfærður á þessum tíma. Þetta er kjarninn í fjölútgáfu, sem gerir LMDB að kjörnum gagnagjafa fyrir ástvini okkar UICollectionView. Eftir að hafa opnað viðskipti er engin þörf á að auka minnisfótspor forritsins, dæla í flýti núverandi gögnum út í einhverja uppbyggingu í minni, vera hræddur við að sitja eftir með ekkert. Þessi eiginleiki greinir LMDB frá sama SQLite, sem getur ekki státað af slíkri algjörri einangrun. Eftir að hafa opnað tvær færslur í þeirri síðarnefndu og eytt ákveðinni færslu innan annarrar þeirra, er ekki lengur hægt að fá sömu færsluna í þeirri seinni sem eftir er.

Bakhliðin á peningnum er hugsanlega verulega meiri neysla sýndarminnis. Skyggnan sýnir hvernig gagnagrunnsbyggingin mun líta út ef henni er breytt á sama tíma með 3 opnum lesfærslum sem skoða mismunandi útgáfur af gagnagrunninum. Þar sem LMDB getur ekki endurnýtt hnúta sem eru aðgengilegir frá rótum sem tengjast raunverulegum viðskiptum, hefur geymslan ekkert val en að úthluta annarri fjórðu rót í minni og enn og aftur klóna breyttu síðurnar undir henni.

Hér mun ekki vera óþarfi að rifja upp kaflann um minniskortaðar skrár. Svo virðist sem aukin neysla sýndarminnis ætti ekki að trufla okkur mikið, þar sem það stuðlar ekki að minnisfótspori forritsins. Hins vegar, á sama tíma, var tekið fram að iOS er mjög snjall við að úthluta því og við getum ekki veitt 1 terabæta LMDB svæði á netþjóni eða skjáborði frá öxl húsbóndans og alls ekki hugsað um þennan eiginleika. Þegar mögulegt er ættir þú að reyna að halda líftíma viðskipta eins stuttan og mögulegt er.

4. Hönnun gagnaskema ofan á lykilgildi API

Við skulum byrja að flokka API með því að skoða helstu útdrætti sem LMDB býður upp á: umhverfi og gagnagrunna, lykla og gildi, viðskipti og bendila.

Athugasemd um kóðaskráningar

Allar aðgerðir í LMDB public API skila niðurstöðu vinnu sinnar í formi villukóða, en í öllum síðari skráningum er eftirliti þess sleppt vegna hnitmiðunar.Í reynd notuðum við okkar eigin kóða til að hafa samskipti við geymsluna. gaffal C++ umbúðir lmdbxx, þar sem villur verða að veruleika sem C++ undantekningar.

Sem fljótlegasta leiðin til að tengja LMDB við iOS eða macOS verkefni, býð ég upp á CocoaPod minn POSLMDB.

4.1. Grunnabstraktanir

Umhverfi

Uppbygging MDB_env er geymsla innra ástands LMDB. Fjölskylda forskeytafalla mdb_env gerir þér kleift að stilla suma eiginleika þess. Í einfaldasta tilvikinu lítur frumstilling vélarinnar svona út.

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

Í Mail.ru Cloud forritinu breyttum við sjálfgefnum gildum fyrir aðeins tvær breytur.

Sú fyrsta er stærð sýndarvistfangarýmisins sem geymsluskránni er varpað á. Því miður, jafnvel á sama tæki, getur sértækt gildi verið verulega breytilegt frá keyrslu til keyrslu. Til að taka tillit til þessa eiginleika iOS veljum við hámarks geymslupláss á virkan hátt. Byrjað er á ákveðnu gildi, það helmingast í röð þar til fallið er mdb_env_open mun ekki skila niðurstöðu öðruvísi en ENOMEM. Fræðilega séð er öfug leið - úthlutaðu fyrst lágmarks minni til vélarinnar og síðan þegar villur berast MDB_MAP_FULL, auka það. Hins vegar er það miklu þyrnirameira. Ástæðan er sú að aðferðin við að endurkorta minni með því að nota aðgerðina mdb_env_set_map_size ógildir allar einingar (bendlar, færslur, lyklar og gildi) sem berast frá vélinni fyrr. Að gera grein fyrir slíkum atburðarásum í kóðanum mun leiða til verulegs flækjustigs hans. Ef sýndarminni er þér samt sem áður mjög kært, þá gæti þetta verið ástæða til að líta á gaffalinn sem hefur gengið langt á undan. MDBX, þar sem meðal yfirlýstra eiginleika er „sjálfvirk gagnagrunnsstærðarstilling á flugi“.

Önnur færibreytan, sjálfgefið gildi sem hentaði okkur ekki, stjórnar vélbúnaðinum til að tryggja þráðöryggi. Því miður, að minnsta kosti í iOS 10, eru vandamál með staðbundna geymslustuðning þráðar. Af þessum sökum, í dæminu hér að ofan, er geymslan opnuð með fánanum MDB_NOTLS. Að auki þurfti það líka gaffal C++ umbúðir lmdbxxað skera breytur með og í þessum eiginleikum.

Gagnagrunna

Gagnagrunnurinn er sérstakt tilvik af B-trénu sem við ræddum um hér að ofan. Opnun þess á sér stað inni í viðskiptum, sem í fyrstu kann að virðast svolítið skrítið.

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

Reyndar eru viðskipti í LMDB geymslueining, ekki sérstakur gagnagrunnur. Þetta hugtak gerir þér kleift að framkvæma atómaðgerðir á einingar sem eru staðsettar í mismunandi gagnagrunnum. Fræðilega séð opnar þetta möguleika á að búa til töflur í formi mismunandi gagnagrunna, en á sínum tíma fór ég í hina áttina, lýst í smáatriðum hér að neðan.

Lyklar og gildi

Uppbygging MDB_val mótar hugmyndina um bæði lykil og gildi. Geymslan hefur ekki hugmynd um merkingarfræði þeirra. Fyrir hana er eitthvað sem er öðruvísi bara fylki af bætum af ákveðinni stærð. Hámarks lykilstærð er 512 bæti.

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

Verslunin notar samanburðartæki til að flokka lyklana í hækkandi röð. Ef þú skiptir ekki út fyrir þitt eigið, þá verður sjálfgefið notað, sem raðar þeim bæti fyrir bæti í orðasafnsröð.

Viðskipti

Viðskiptatækinu er lýst í smáatriðum í fyrri kafla, svo hér mun ég endurtaka helstu eiginleika þeirra í stuttri línu:

1. Stuðningur við allar helstu eignir ACIDLykilorð: atómvirkni, samkvæmni, einangrun og áreiðanleiki. Ég get ekki annað en tekið fram að hvað varðar endingu á macOS og iOS þá er villa lagfærð í MDBX. Þú getur lesið meira í þeim README.
2. Nálgunin að fjölþráðum er lýst með kerfinu „einn rithöfundur / margir lesendur“. Rithöfundar loka hver öðrum, en þeir loka ekki fyrir lesendur. Lesendur loka hvorki á rithöfunda né hvern annan.
3. Stuðningur við hreiður viðskipti.
4. Multiversion stuðningur.

Multiversioning í LMDB er svo góð að ég vil sýna það í verki. Kóðinn hér að neðan sýnir að hver viðskipti virka með nákvæmlega þeirri útgáfu af gagnagrunninum sem átti við þegar hann var opnaður, algjörlega einangruð frá öllum síðari breytingum. Það skiptir engu máli að frumstilla geymsluna og bæta prófunarskrá við hana, þannig að þessar helgisiðir eru skildir eftir undir spoilernum.

Bætir við próffærslu

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

Valfrjálst mæli ég með að prófa sama bragðið með SQLite og sjá hvað gerist.

Multiversioning færir líf iOS forritara mjög góðan ávinning. Með því að nota þessa eign geturðu auðveldlega og náttúrulega stillt uppfærsluhraða gagnagjafa fyrir skjáform út frá notendaupplifun. Til dæmis, við skulum taka slíkan eiginleika Mail.ru Cloud forritsins sem sjálfvirkt hleðslu efni úr kerfismiðalasafninu. Með góðri tengingu getur viðskiptavinurinn bætt nokkrum myndum á sekúndu við netþjóninn. Ef þú uppfærir eftir hvert niðurhal UICollectionView með fjölmiðlaefni í skýi notandans geturðu gleymt um 60 ramma á sekúndu og sléttri flettu meðan á þessu ferli stendur. Til að koma í veg fyrir tíðar skjáuppfærslur þarftu einhvern veginn að takmarka hraða gagnabreytinga í grunninum UICollectionViewDataSource.

Ef gagnagrunnurinn styður ekki fjölútgáfu og leyfir þér að vinna aðeins með núverandi ástandi, þá þarftu að afrita það annaðhvort í einhverja gagnauppbyggingu í minni eða í tímabundna töflu til að búa til tímastöðug gagnamynd. Hvort tveggja þessara aðferða er mjög dýrt. Ef um er að ræða geymslu í minni, fáum við bæði minniskostnaðinn sem stafar af geymslu smíðaðra hluta og tímakostnaðinn í tengslum við óþarfa ORM umbreytingar. Hvað bráðabirgðaborðið varðar, þá er þetta enn dýrari ánægja, sem er skynsamleg aðeins í óléttum tilvikum.

Multiversioning LMDB leysir vandamálið við að viðhalda stöðugum gagnagjafa á mjög glæsilegan hátt. Það er nóg að opna færslu og voila - þar til við ljúkum því er tryggt að gagnasettið sé lagað. Rökfræði uppfærsluhraða þess er nú alfarið í höndum kynningarlagsins, án kostnaðar af umtalsverðu fjármagni.

Bendlar

Bendlar veita kerfi fyrir skipulegan endurtekningu yfir lykilgildapör með því að fara yfir B-tré. Án þeirra væri ómögulegt að móta töflurnar í gagnagrunninum á áhrifaríkan hátt, sem við snúum okkur nú að.

4.2. Borðlíkön

Lyklaröðunareiginleikinn gerir þér kleift að smíða útdrátt á efstu stigi eins og töflu ofan á grunnútdrætti. Við skulum íhuga þetta ferli á dæmi um aðaltöflu skýjaforritsins, þar sem upplýsingar um allar skrár og möppur notandans eru í skyndiminni.

Tafla Schema

Ein af algengustu atburðarásunum sem skerpa ætti uppbyggingu töflu með möpputré fyrir er að velja alla þætti sem eru staðsettir inni í tiltekinni möppu. Gott gagnaskipulagslíkan fyrir skilvirkar fyrirspurnir af þessu tagi er Aðgöngulisti. Til að útfæra það ofan á lykilgildisgeymsluna er nauðsynlegt að raða lyklum skráa og möppu þannig að þær séu flokkaðar út frá því að tilheyra móðurskránni. Að auki, til þess að birta innihald möppunnar á því formi sem Windows notandi kannast við (möppur fyrst, síðan skrár, báðar eru flokkaðar í stafrófsröð), er nauðsynlegt að innihalda samsvarandi viðbótarreiti í lyklinum.

Myndin hér að neðan sýnir hvernig, byggt á verkefninu, getur framsetning lykla sem fylkis bæta litið út. Fyrst eru bætin með auðkenni móðurskrár (rautt) sett, síðan með gerðinni (grænt), og þegar í skottinu með nafninu (bláu). Þar sem þau eru flokkuð eftir sjálfgefnum LMDB samanburðarröð í orðasafnsröð, eru þau raðað í nauðsynlega leið. Að fara yfir lykla í röð með sama rauða forskeytinu gefur okkur gildin sem tengjast þeim í þeirri röð sem þeir ættu að birtast í notendaviðmótinu (til hægri), án þess að þurfa frekari eftirvinnslu.

Serializing lykla og gildi

Það eru margar aðferðir til að raðgreina hluti um allan heim. Þar sem við höfðum enga aðra kröfu nema hraða, völdum við hraðasta mögulega fyrir okkur sjálf - minnishaugur sem er upptekinn af tilviki af C tungumálaskipaninni. Þannig að lykill möppuþáttar er hægt að móta með eftirfarandi uppbyggingu NodeKey.

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

Til að spara NodeKey í geymsluþörf í hlut MDB_val staðsetja bendilinn á gögnin á heimilisfangi upphafs byggingarinnar og reikna stærð þeirra með fallinu sizeof.

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

Í fyrsta kafla um gagnagrunnsvalsviðmið nefndi ég að lágmarka kraftmikla úthlutun sem hluta af CRUD-aðgerðum sem mikilvægan valþátt. Aðgerðarkóði serialize sýnir hvernig hægt er að forðast þær algjörlega í tilfelli LMDB þegar nýjar skrár eru settar inn í gagnagrunninn. Komandi fylki bæta frá þjóninum er fyrst umbreytt í staflabyggingar og síðan er þeim léttilega hent í geymsluna. Í ljósi þess að það eru líka engar dýnamískar úthlutanir inni í LMDB, geturðu fengið frábærar aðstæður samkvæmt stöðlum iOS - notaðu aðeins staflaminni til að vinna með gögn alla leið frá netinu til disksins!

Að panta lykla með tvíundarsamanburði

Lyklaröðunartengslin eru gefin af sérstakri aðgerð sem kallast samanburður. Þar sem vélin veit ekkert um merkingarfræði bæti sem þau innihalda, hefur sjálfgefinn samanburðaraðili ekkert val en að raða lyklunum í orðasafnsröð og grípa til samanburðar bæti fyrir bæti. Að nota það til að raða mannvirkjum er svipað og að raka með útskurðaröxi. Hins vegar, í einföldum tilvikum, finnst mér þessi aðferð ásættanleg. Valkostinum er lýst hér að neðan, en hér mun ég taka eftir nokkrum hrífum á víð og dreif á leiðinni.

Það fyrsta sem þarf að hafa í huga er minnisframsetning frumstæðra gagnategunda. Þannig að á öllum Apple tækjum eru heiltölubreytur geymdar á sniðinu Litla Endian. Þetta þýðir að minnst marktæka bætið verður vinstra megin og þú munt ekki geta flokkað heiltölur með því að nota bæti-fyrir-bæta samanburð. Til dæmis, að reyna að gera þetta með mengi af tölum frá 0 til 511 mun leiða til eftirfarandi niðurstöðu.

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

Til að leysa þetta vandamál verður að geyma heiltölurnar í lyklinum á sniði sem hentar bætasamanburðarkerfinu. Aðgerðir frá fjölskyldunni munu hjálpa til við að framkvæma nauðsynlega umbreytingu. hton* (sérstaklega htons fyrir tvöfalda bæta tölur úr dæminu).

Snið til að tákna strengi í forritun er eins og þú veist ein heild Saga. Ef merkingarfræði strengja, sem og kóðun sem notuð er til að tákna þá í minni, bendir til þess að það geti verið meira en eitt bæti á hvern staf, þá er betra að hætta strax við hugmyndina um að nota sjálfgefinn samanburðaraðila.

Annað sem þarf að hafa í huga er aðlögunarreglum struct reit þýðanda. Vegna þeirra er hægt að mynda bæti með sorpgildum í minni á milli reita, sem auðvitað brýtur bætaflokkun. Til að útrýma sorpi verður þú annaðhvort að lýsa yfir reitina í strangt skilgreindri röð, hafa jöfnunarreglurnar í huga, eða nota eigindina í byggingaryfirlýsingunni packed.

Lyklapöntun eftir utanaðkomandi samanburðaraðila

Lyklasamanburðarrökfræðin gæti reynst of flókin fyrir tvíundarsamanburð. Ein af mörgum ástæðum er tilvist tæknisviða inni í mannvirkjunum. Ég mun útskýra tilvik þeirra með dæmi um lykil sem okkur er þegar kunnur fyrir möppuþátt.

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

Þrátt fyrir einfaldleikann eyðir það í langflestum tilfellum of mikið minni. Titilbiðminnið er 256 bæti, þó að meðaltali skráa- og möppuheiti fara sjaldan yfir 20-30 stafi.

Ein af stöðluðu aðferðunum til að hámarka stærð færslu er að klippa hana til að passa raunverulega stærð hennar. Kjarni þess er að innihald allra reita með breytilegri lengd er geymt í biðminni í lok skipulagsins og lengd þeirra geymd í aðskildum breytum. Í samræmi við þessa nálgun er lykillinn NodeKey er umbreytt á eftirfarandi hátt.

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

Ennfremur, meðan á serialization stendur, ekki tilgreint sem gagnastærð sizeof allt skipulagið og stærð allra reita er föst lengd plús stærð raunverulegs notaðs hluta biðminni.

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

Vegna endurnýjunarinnar fengum við verulegan sparnað í plássinu sem lyklarnir taka. Hins vegar vegna tæknisviðs nameLength, sjálfgefna tvíundarsamanburðurinn hentar ekki lengur fyrir lyklasamanburð. Ef við skiptum því ekki út fyrir okkar eigin, þá mun lengd nafnsins vera meiri forgangsþáttur í flokkun en nafnið sjálft.

LMDB gerir hverjum gagnagrunni kleift að hafa sína eigin lykilsamanburðaraðgerð. Þetta er gert með því að nota aðgerðina mdb_set_compare stranglega fyrir opnun. Af augljósum ástæðum er ekki hægt að breyta gagnagrunni allan líftíma hans. Við inntakið fær samanburðartækið tvo lykla á tvíundarsniði og við úttakið skilar hann niðurstöðu samanburðarins: minni en (-1), stærri en (1) eða jafn (0). Gervikóði fyrir NodeKey lítur þannig ú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 // ...
}​

Svo framarlega sem allir lyklar í gagnagrunninum eru af sömu gerð er löglegt að varpa byte framsetningu þeirra skilyrðislaust á gerð forritsuppbyggingar lykilsins. Það er einn blæbrigði hér, en það verður fjallað aðeins neðar í undirkaflanum „Lesturskrár“.

Gildi Serialization

Með lyklum geymdra skráa vinnur LMDB afar ákaft. Þau eru borin saman við hvert annað innan ramma hvers kyns forritsaðgerða og árangur allrar lausnarinnar fer eftir hraða samanburðartækisins. Í hugsjónum heimi ætti sjálfgefinn tvöfaldur samanburður að vera nóg til að bera saman lykla, en ef þú þyrftir virkilega að nota þína eigin, þá ætti aðferðin við að afseríða lykla í honum að vera eins hröð og mögulegt er.

Gagnagrunnurinn hefur ekki sérstakan áhuga á Value-hluta færslunnar (gildi). Umbreyting þess úr bætaframsetningu yfir í hlut á sér stað aðeins þegar það er þegar krafist af forritskóðanum, til dæmis til að birta hann á skjánum. Þar sem þetta gerist tiltölulega sjaldan eru kröfurnar um hraða þessa málsmeðferðar ekki svo mikilvægar og við framkvæmd hennar erum við miklu frjálsari að einbeita okkur að þægindum. Til dæmis, til að raðgreina lýsigögn um skrár sem ekki hefur enn verið hlaðið niður, notum við NSKeyedArchiver.

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

Hins vegar eru tímar þegar frammistaða skiptir máli. Til dæmis, þegar við vistum meta-upplýsingar um skráarbyggingu notendaskýsins, notum við sama hlutminnisafnið. Hápunktur verkefnisins við að búa til raðmyndagerð þeirra er sú staðreynd að þættir möppu eru gerðir af stéttastigveldi.

Fyrir útfærslu þess á C-málinu eru tilteknir reitir erfingjanna teknir út í aðskilin mannvirki og tengsl þeirra við grunninn eru tilgreind í reit af stéttarfélagsgerð. Raunverulegt innihald sambandsins er tilgreint með tegund tæknieiginleika.

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

Bæta við og uppfæra skrár

Hægt er að bæta raðlyklinum og gildi við verslunina. Til þess er aðgerðin notuð mdb_put.

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

Á stillingarstigi er hægt að leyfa eða banna geymslunni að geyma margar færslur með sama lyklinum.​Ef fjölföldun lykla er bönnuð, þá geturðu þegar þú setur færslu inn, ákvarðað hvort uppfærsla á færslu sem þegar er til sé leyfð eða ekki. Ef slit getur aðeins átt sér stað vegna villu í kóðanum, þá geturðu tryggt þig gegn því með því að tilgreina fánann NOOVERWRITE.

Að lesa færslur

Aðgerðin til að lesa færslur í LMDB er mdb_get. Ef lykilgildi parið er táknað með mannvirkjum sem áður hafa verið varpað, þá lítur þessi aðferð svona út.

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

Framsett skráning sýnir hvernig raðgreining í gegnum sorphauga mannvirkja gerir þér kleift að losna við kraftmikla úthlutun, ekki aðeins þegar þú skrifar, heldur þegar þú lest gögn. Afleidd af virkni mdb_get bendillinn lítur nákvæmlega á sýndarminnisfangið þar sem gagnagrunnurinn geymir bætaframsetningu hlutarins. Reyndar fáum við eins konar ORM, nánast ókeypis sem veitir mjög mikinn hraða á lestri gagna. Með allri fegurð nálgunarinnar er nauðsynlegt að muna nokkra eiginleika sem tengjast henni.

1. Fyrir skrifvarinn færslu er tryggt að bendill á gildisskipulag haldist aðeins gildur þar til færslunni er lokað. Eins og áður hefur komið fram eru síðurnar í B-trénu sem hluturinn er á, þökk sé afrita-í-skrifa meginreglunni, óbreyttar svo framarlega sem að minnsta kosti ein viðskipti vísar til þeirra. Jafnframt, um leið og síðustu færslu tengd þeim er lokið, er hægt að endurnýta síðurnar fyrir ný gögn. Ef það er nauðsynlegt fyrir hluti til að lifa af viðskiptin sem skapaði þá, þá þarf samt að afrita þá.
2. Fyrir endurskrifafærslu mun bendillinn á uppbyggingargildið sem myndast aðeins gilda fram að fyrstu breytingaferli (skrifa eða eyða gögnum).
3. Jafnvel þótt uppbyggingin NodeValue ekki fullgildur, en klipptur (sjá undirkafla „Pöntun lykla eftir ytri samanburðaraðila“), í gegnum bendilinn geturðu auðveldlega nálgast reiti hans. Aðalatriðið er að gera ekki lítið úr því!
4. Í engu tilviki er hægt að breyta uppbyggingunni í gegnum móttekna bendilinn. Allar breytingar verða aðeins að gera með aðferðinni mdb_put. Hins vegar, með alla löngun til að gera þetta, mun það ekki virka, þar sem minnissvæðið þar sem þessi uppbygging er staðsett er kortlagt í skrifvarið ham.
5. Endurvarpa skrá á vistfangarými ferlis til að auka td hámarksgeymslustærð með því að nota aðgerðina mdb_env_set_map_size ógildir algjörlega allar færslur og tengdar einingar almennt og ábendingar um að lesa hluti sérstaklega.

Að lokum, enn einn eiginleiki er svo skaðlegur að birting kjarna hans passar ekki inn í aðeins einn punkt í viðbót. Í kaflanum um B-tréð gaf ég skýringarmynd af skipulagi síðna þess í minni. Það leiðir af því að heimilisfang upphafs biðminni með raðnúmeruðum gögnum getur verið algjörlega handahófskennt. Vegna þessa, bendilinn til þeirra, fengin í uppbyggingu MDB_val og steypa á bendil á mannvirki er almennt ójafnað. Á sama tíma krefst arkitektúr sumra flísa (í tilfelli iOS, þetta er armv7) að vistfang hvers kyns gagna sé margfeldi af stærð vélarorðs, eða, með öðrum orðum, bitleiki kerfisins. (fyrir armv7 er þetta 32 bita). Með öðrum orðum, aðgerð eins og *(int *foo)0x800002 á þeim er jafnað til flótta og leiðir til afplánunar með dómi EXC_ARM_DA_ALIGN. Það eru tvær leiðir til að forðast svona sorgleg örlög.

Sú fyrsta er að afrita gögnin í þekkta samræmda uppbyggingu fyrirfram. Til dæmis, á sérsniðnum samanburðartæki, mun þetta endurspeglast sem hér segir.

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

Önnur leið er að tilkynna þýðandanum fyrirfram um að mannvirki með lykil og gildi megi ekki samræma með því að nota eigind aligned(1). Á ARM geta sömu áhrif verið afreka og nota pakkaða eiginleikann. Með hliðsjón af því að hún stuðlar einnig að hagræðingu á rýminu sem mannvirkið tekur, finnst mér þessi aðferð æskileg, þó að приводит til að auka kostnað við gagnaaðgangsrekstur.

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

Range Queries

Til að endurtaka yfir hóp skráa, býður LMDB upp bendilútdrátt. Við skulum skoða hvernig á að vinna með það með því að nota dæmið um töflu með lýsigögnum notendaskýs sem við þekkjum nú þegar.

Sem hluti af því að sýna lista yfir skrár í möppu þarftu að finna alla lykla sem undirskrár og möppur hennar eru tengdar við. Í fyrri undirköflum flokkuðum við lyklana NodeKey þannig að þeim er fyrst raðað eftir auðkenni foreldraskrár. Þannig, tæknilega séð, minnkar verkefnið við að fá innihald möppu niður í að setja bendilinn á efri mörk lyklahóps með tilteknu forskeyti, fylgt eftir með endurtekningu á neðri mörkin.

Þú getur fundið efri mörkin "á enni" með raðleit. Til að gera þetta er bendillinn settur í byrjun alls lyklalistans í gagnagrunninum og síðan hækkaður þar til lykillinn með auðkenni móðurskrár birtist fyrir neðan hann. Þessi aðferð hefur 2 augljósa galla:

1. Línuleg margbreytileiki leitarinnar, þó, eins og þú veist, í trjám almennt og í B-tré sérstaklega, þá er hægt að gera það á lógaritmískum tíma.
2. Til einskis eru allar síður á undan þeirri sem óskað er eftir hækkaðar úr skránni í aðalminnið, sem er mjög dýrt.

Sem betur fer býður LMDB API upp á skilvirka leið til að staðsetja bendilinn í upphafi. . Til dæmis, í tengslum við listann á myndinni hér að ofan, getum við búið til lykil þar sem reiturinn parentId verður jafnt og 2, og allir hinir eru fylltir með núllum. Slíkur lykill sem er að hluta til er færður í inntak aðgerðarinnar mdb_cursor_get gefur til kynna aðgerð 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);

Ef efri mörk lyklahópsins finnast, endurtekum við það þar til annað hvort við hittumst eða lykillinn með öðrum parentId, eða lyklarnir klárast alls ekki.​

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

Það sem er gott, sem hluti af endurtekningu með því að nota mdb_cursor_get, fáum við ekki aðeins lykilinn heldur einnig gildið. Ef, til að uppfylla valskilyrðin, þarf að athuga meðal annars reiti úr gildishluta skrárinnar, þá eru þeir sjálfir aðgengilegir án viðbótarbendinga.

4.3. Líkönun á tengslum milli taflna

Hingað til hefur okkur tekist að huga að öllum þáttum við hönnun og vinnu með gagnagrunni með einni töflu. Við getum sagt að tafla sé sett af flokkuðum færslum sem samanstanda af lykilgildapörum af sömu gerð. Ef þú sýnir lykil sem rétthyrning og tilheyrandi gildi hans sem kassa færðu sjónrænt skýringarmynd af gagnagrunninum.

​

Hins vegar, í raunveruleikanum, er sjaldan hægt að komast af með svo lítið blóð. Oft þarf í gagnagrunni í fyrsta lagi að hafa nokkrar töflur og í öðru lagi að framkvæma val í þeim í annarri röð en aðallykillinn. Þessi síðasti hluti er helgaður spurningum um sköpun þeirra og samtengingu.

Vísitölutöflur

Skýforritið er með „Gallerí“ hluta. Það sýnir fjölmiðlaefni úr öllu skýinu, raðað eftir dagsetningu. Til að útfæra slíkt val sem best, við hliðina á aðaltöflunni, þarftu að búa til annan með nýrri gerð lykla. Þeir munu innihalda reit með dagsetningunni sem skráin var búin til, sem mun virka sem aðal flokkunarviðmiðun. Þar sem nýju lyklarnir vísa til sömu gagna og lyklarnir í undirliggjandi töflu eru þeir kallaðir vísitölulyklar. Þau eru auðkennd með appelsínugult á myndinni hér að neðan.

Til þess að aðgreina lykla mismunandi taflna frá hver öðrum innan sama gagnagrunns hefur viðbótar tæknisviði tableId verið bætt við þær allar. Með því að setja það í hæsta forgang fyrir flokkun, munum við flokka lyklana fyrst eftir töflum og þegar inni í töflunum - samkvæmt okkar eigin reglum.

Vísilykillinn vísar til sömu gagna og aðallykillinn. Einföld útfærsla þessarar eignar með því að tengja við hana afrit af gildishluta aðallykilsins er óákjósanlegur frá nokkrum sjónarhornum í einu:​

1. Frá sjónarhóli upptekins rýmis geta lýsigögnin verið ansi rík.
2. Frá sjónarhóli frammistöðu, þar sem þegar þú uppfærir lýsigögn hnútsins verður þú að skrifa yfir tvo lykla.
3. Frá sjónarhóli kóðastuðnings, eftir allt saman, ef við gleymum að uppfæra gögnin fyrir einn af lyklunum, munum við fá lúmskur villu af ósamræmi gagna í geymslunni.

Næst munum við íhuga hvernig á að útrýma þessum göllum.

Skipulag tengsla milli taflna

Mynstrið hentar vel til að tengja vísitölutöflu við þá helstu "lykill sem gildi". Eins og nafnið gefur til kynna er gildishluti vísitöluskrárinnar afrit af aðallykilsgildinu. Þessi nálgun útilokar alla ókosti sem taldir eru upp hér að ofan í tengslum við að geyma afrit af gildishluta aðalskrárinnar. Eina gjaldið er að til að fá gildið með vísitölulyklinum þarftu að gera 2 fyrirspurnir í gagnagrunninn í stað einnar. Skematískt séð er gagnagrunnsskema sem myndast sem hér segir.

Annað mynstur til að skipuleggja tengsl milli borða er "óþarfi lykill". Kjarni þess er að bæta við viðbótareiginleikum við lykilinn, sem þarf ekki til að flokka, heldur til að endurskapa tengdan lykil. Það eru hins vegar raunveruleg dæmi um notkun hans í Mail.ru Cloud forritinu til að forðast djúpt kafa í samhengi tiltekinna iOS ramma, mun ég gefa uppskáldað, en þó skiljanlegra dæmi.

Cloud farsímaviðskiptavinir eru með síðu sem sýnir allar skrár og möppur sem notandinn hefur deilt með öðru fólki. Þar sem slíkar skrár eru tiltölulega fáar og mikið af sértækum upplýsingum um kynningu tengdar þeim (hverjum er veittur aðgangur, með hvaða réttindum o.s.frv.), er ekki skynsamlegt að íþyngja þeim með gildishlutanum. færslan í aðaltöflunni. Hins vegar, ef þú vilt sýna slíkar skrár án nettengingar, þá þarftu samt að geyma þær einhvers staðar. Eðlileg lausn er að búa til sérstakt borð fyrir það. Á skýringarmyndinni hér að neðan er lykill þess með „P“ í forskeytinu og hægt er að skipta út „propname“ staðgengilnum fyrir nákvæmara gildið „public info“.​

Öll einstök lýsigögn, fyrir þá sök sem nýja taflan var búin til, eru færð í gildishluta færslunnar. Á sama tíma vil ég ekki afrita gögnin um skrár og möppur sem eru þegar geymdar í aðaltöflunni. Þess í stað er óþarfi gögnum bætt við „P“ lykilinn í formi „hnútauðkennis“ og „tímastimpils“ reitanna. Þökk sé þeim geturðu smíðað vísitölulykil, þar sem þú getur fengið aðallykilinn, sem að lokum geturðu fengið lýsigögn hnútsins.

Niðurstaða

Við metum niðurstöður LMDB innleiðingar jákvætt. Eftir hana fækkaði frystingu umsókna um 30%.

Niðurstöður vinnunnar hafa fundið viðbrögð utan iOS teymisins. Eins og er, hefur einn af helstu "skrár" hlutunum í Android forritinu einnig skipt yfir í að nota LMDB og aðrir hlutar eru á leiðinni. C tungumálið, sem lykilgildi geymslan er útfærð á, var góð hjálp til að gera forritið bindandi í kringum það í upphafi á C ++ tungumálinu. Fyrir óaðfinnanlega tengingu C ++ bókasafnsins sem myndast við vettvangskóða í Objective-C og Kotlin var kóðarafall notaður Djinni frá Dropbox, en það er önnur saga.

Heimild: www.habr.com