2019 őszén egy régóta várt eseményre került sor a Mail.ru Cloud iOS csapatában. Az alkalmazás állapotának állandó tárolására szolgáló fő adatbázis meglehetősen egzotikussá vált a mobil világ számára Lightning memória-leképezett adatbázis (LMDB). A vágás alatt a négy részből álló részletes áttekintésre hívjuk fel a figyelmet. Először is beszéljünk egy ilyen nem triviális és nehéz választás okairól. Ezután térjünk át az LMDB architektúra középpontjában álló három bálna megfontolására: memória-leképezett fájlok, B + fa, másolás írásra megközelítés a tranzakciós és többverziós megvalósításhoz. Végül desszertnek - a gyakorlati rész. Ebben megvizsgáljuk, hogyan lehet megtervezni és megvalósítani egy alapsémát több táblával, beleértve az indexet is, az alacsony szintű kulcsértékű API-n felül.​

Tartalom

1. Megvalósítási motiváció
2. LMDB pozicionálása
3. Három bálna LMDB
   3.1. Bálna #1. Memória-leképezett fájlok
   3.2. Bálna #2. B+-fa
   3.3. Bálna #3. másolás-írásra
4. Adatséma tervezése a kulcsérték API-n
   4.1. Alapvető absztrakciók
   4.2. Táblázat modellezés
   4.3. Táblázatok közötti kapcsolatok modellezése

1. Megvalósítási motiváció

Évente egyszer, 2015-ben gondoskodtunk arról, hogy mérőszámot vegyünk, hogy milyen gyakran késik az alkalmazásunk felülete. Nem csak ezt csináltuk. Egyre több panaszunk van arra, hogy néha az alkalmazás nem reagál a felhasználói műveletekre: nem nyomják meg a gombokat, nem gördülnek a listák stb. A mérések mechanikájáról mondta az AvitoTech-en, ezért itt csak a számok sorrendjét adom meg.

A mérési eredmények hidegzuhany lettek számunkra. Kiderült, hogy a fagyok okozta problémák sokkal többek, mint bármely más. Ha ennek felismerése előtt a minőség fő műszaki mutatója összeomlásmentes volt, akkor a fókusz után eltolódott fagymentesen.

Miután épített műszerfal fagyokkal és miután költött mennyiségi и minőség Az okok elemzése során világossá vált a fő ellenség: az alkalmazás fő szálában végrehajtott nehéz üzleti logika. A szégyenre adott természetes reakció az égő vágy volt, hogy a munkafolyamatokba taszítsa. A probléma szisztematikus megoldásához egy többszálú, könnyű szereplőkre épülő architektúrát alkalmaztunk. Az ő adaptációit az iOS világának szenteltem két szál a kollektív twitterben és cikk Habréról. A mostani történet részeként szeretném hangsúlyozni a döntés azon szempontjait, amelyek befolyásolták az adatbázis kiválasztását

A rendszerszervezés aktormodellje feltételezi, hogy a többszálúság lesz a második lényege. A benne lévő modellobjektumok szeretnek átlépni a szálhatárokat. És ezt nem néha és helyenként teszik, hanem szinte folyamatosan és mindenhol.

Az adatbázis a bemutatott diagram egyik sarokköve. Fő feladata egy makróminta megvalósítása Megosztott adatbázis. Ha a vállalati világban a szolgáltatások közötti adatszinkronizálás megszervezésére szolgál, akkor az actor architektúra esetén a szálak közötti adatok. Így szükségünk volt egy olyan adatbázisra, amellyel a többszálú környezetben való munka minimális nehézséget sem okoz. Ez különösen azt jelenti, hogy az ebből származó objektumoknak legalább szálbiztosaknak kell lenniük, és ideális esetben egyáltalán nem változtathatók. Mint ismeretes, ez utóbbi egyidejűleg több szálból is használható, mindenféle zárolás nélkül, ami jótékony hatással van a teljesítményre.

A második jelentős tényező, amely befolyásolta az adatbázis kiválasztását, a felhő API volt. A szinkronizálás git megközelítése ihlette. Akárcsak ő, akit megcéloztunk offline első API, amely több mint megfelelőnek tűnik a felhőkliensek számára. Feltételezték, hogy csak egyszer pumpálják ki a felhő teljes állapotát, majd a szinkronizálás az esetek túlnyomó többségében gördülő változtatásokon keresztül történik. Sajnos ez a lehetőség még mindig csak az elméleti zónában van, és a gyakorlatban az ügyfelek nem tanulták meg, hogyan kell dolgozni a foltokkal. Ennek számos objektív oka van, amelyeket, hogy a bevezetést ne késleltesse, a zárójelből kihagyjuk. Most sokkal érdekesebbek a lecke tanulságos eredményei arról, hogy mi történik, ha az API „A”-t mond, a fogyasztója pedig nem „B”-t.

Tehát, ha elképzeli a git-et, amely egy pull parancs végrehajtásakor ahelyett, hogy javításokat alkalmazna egy helyi pillanatképhez, összehasonlítja a teljes állapotát a teljes szerver állapotával, akkor meglehetősen pontos elképzelése lesz a szinkronizálás módjáról. felhőkliensekben fordul elő. Könnyen kitalálható, hogy megvalósításához két DOM-fát kell lefoglalni a memóriában metainformációkkal az összes szerverről és helyi fájlról. Kiderült, hogy ha egy felhasználó 500 ezer fájlt tárol a felhőben, akkor a szinkronizáláshoz két, 1 millió csomóponttal rendelkező fát kell újra létrehozni és megsemmisíteni. De minden csomópont egy aggregátum, amely alobjektumok gráfját tartalmazza. Ennek fényében a profilalkotási eredmények várhatóak voltak. Kiderült, hogy az egyesítési algoritmus figyelembevétele nélkül is, maga a hatalmas számú kis objektum létrehozásának, majd megsemmisítésének eljárása szép fillérekbe kerül. A helyzetet súlyosbítja, hogy az alapvető szinkronizálási művelet nagy számban szerepel felhasználói szkriptek közül. Ennek eredményeként rögzítjük az adatbázis kiválasztásának második fontos kritériumát - a CRUD műveletek végrehajtásának képességét az objektumok dinamikus kiosztása nélkül.

A többi követelmény hagyományosabb, teljes listájuk pedig a következő.

1. Menetbiztonság.
2. Többszörös feldolgozás. Az a vágy diktálja, hogy ugyanazt az adatbázispéldányt használják az állapot szinkronizálására nemcsak a szálak között, hanem a fő alkalmazás és az iOS-bővítmények között is.
3. A tárolt entitások nem változtatható objektumként való megjelenítésének képessége
4. A dinamikus allokációk hiánya a CRUD műveleteken belül.
5. Tranzakciók támogatása az alapvető tulajdonságokhoz SAVKulcsszavak: atomitás, konzisztencia, izoláció és megbízhatóság.
6. Gyorsaság a legnépszerűbb eseteken.

Ezzel a követelményrendszerrel az SQLite jó választás volt és továbbra is az. Az alternatívák tanulmányozása részeként azonban kezembe került egy könyv "Kezdő lépések a LevelDB-vel". Irányítása alatt készült egy benchmark, amely összehasonlítja a munka sebességét a különböző adatbázisokkal valós felhő forgatókönyvekben. Az eredmény a legmerészebb várakozásokat is felülmúlta. A legnépszerűbb esetekben - amikor a kurzort az összes fájl rendezett listájára és egy adott könyvtár összes fájljának rendezett listájára helyezzük - az LMDB 10-szer gyorsabbnak bizonyult, mint az SQLite. A választás nyilvánvalóvá vált.

2. LMDB pozicionálás

Az LMDB egy nagyon kicsi könyvtár (csak 10 XNUMX sor), amely az adatbázisok legalacsonyabb alapvető rétegét – a tárolást – valósítja meg.

A fenti diagram azt mutatja, hogy az LMDB és az SQLite összehasonlítása, amely még magasabb szinteket valósít meg, általában nem helyesebb, mint az SQLite az alapadatokkal. Igazságosabb lenne ugyanazokat a tárolómotorokat egyenrangú versenytársakként említeni – BerkeleyDB, LevelDB, Sophia, RocksDB stb. Vannak olyan fejlesztések is, ahol az LMDB az SQLite tárolómotor-komponenseként működik. Az első ilyen kísérlet 2012-ben költött szerző LMDB Howard Chu. Álláspontja annyira érdekesnek bizonyult, hogy kezdeményezését az OSS-rajongók felkapták, és az LumoSQL. 2020 januárjában ennek a projektnek a szerzője Den Shearer bemutatott a LinuxConfAu-n.

Az LMDB fő felhasználása az alkalmazás adatbázisok motorja. A könyvtár a fejlesztőknek köszönheti megjelenését OpenLDAP, akik erősen elégedetlenek voltak a BerkeleyDB-vel, mint projektjük alapjával. Lelökni a szerény könyvtárat btree, Howard Chu meg tudta alkotni korunk egyik legnépszerűbb alternatíváját. Nagyon klassz riportját ennek a történetnek, valamint az LMDB belső felépítésének szentelte. "A villám memória-leképezett adatbázis". Leonyid Jurjev (más néven yleo) a Positive Technologies részéről a Highload 2015-ben tartott előadásában "Az LMDB motor különleges bajnok". Ebben az LMDB-ről beszél a ReOpenLDAP megvalósításának hasonló feladatával összefüggésben, és a LevelDB-t már összehasonlító kritika érte. A megvalósítás eredményeként a Positive Technologies még egy aktívan fejlődő villát is kapott MDBX nagyon ízletes funkciókkal, optimalizációkkal és hibajavítások.

Az LMDB-t gyakran tárolóként is használják. Például a Mozilla Firefox böngésző választotta számos igényre, és a 9-es verziótól kezdve az Xcode-ra előnyben részesített az SQLite az indexek tárolására.

A motor a mobilfejlesztés világában is megfogott. Használatának nyomai lehetnek talál a Telegram iOS-kliensében. A LinkedIn egy lépéssel tovább ment, és az LMDB-t választotta alapértelmezett tárhelynek a saját fejlesztésű adatgyorsítótárazási keretrendszeréhez, a Rocket Data-hoz, amelyről mondta egy cikkben 2016-ban.

Az LMDB sikeresen harcol a napfényes helyért a BerkeleyDB által az Oracle irányítása alá történő átmenet után hagyott résben. A könyvtárat gyorsasága és megbízhatósága miatt szeretik, még a maga fajtájához képest is. Mint tudják, nincs ingyen ebéd, és szeretném hangsúlyozni azt a kompromisszumot, amellyel szembe kell néznie, amikor az LMDB és az SQLite között választ. A fenti diagram jól szemlélteti, hogyan érhető el a megnövelt sebesség. Először is, nem fizetünk a lemeztáron felül további absztrakciós rétegekért. Természetesen egy jó architektúrában továbbra sem nélkülözheti őket, és elkerülhetetlenül megjelennek az alkalmazás kódjában, de sokkal vékonyabbak lesznek. Nem rendelkeznek olyan szolgáltatásokkal, amelyeket egy adott alkalmazás nem igényel, például az SQL nyelvű lekérdezések támogatása. Másodszor, lehetővé válik az alkalmazásműveletek leképezése a lemeztárra vonatkozó kérésekhez. Ha SQLite munkámban egy átlagos alkalmazás átlagos igényeiből származik, akkor Ön, mint alkalmazásfejlesztő, jól ismeri a fő betöltési forgatókönyveket. A termelékenyebb megoldás érdekében megemelt árat kell fizetnie mind a kezdeti megoldás fejlesztéséért, mind a későbbi támogatásáért.

3. Három bálna LMDB

Miután megnéztük az LMDB-t madártávlatból, ideje mélyebbre menni. A következő három rész a főbb bálnák elemzésének lesz szentelve, amelyeken a tárolási architektúra alapul:

1. A memória-leképezett fájlok a lemezzel való munkavégzés és a belső adatstruktúrák szinkronizálásának mechanizmusaként.
2. A B+-fa, mint a tárolt adatstruktúra szervezete.
3. Másolás írásra, mint megközelítés az ACID tranzakciós tulajdonságok és a többverziós megoldás biztosítására.

3.1. Bálna #1. Memória-leképezett fájlok

A memória-leképezett fájlok olyan fontos építészeti elemet jelentenek, hogy még a tároló nevében is megjelennek. A tárolt információk gyorsítótárazásával és szinkronizálásával kapcsolatos problémák teljes mértékben az operációs rendszer kiszolgáltatottjai. Az LMDB önmagában nem tartalmaz gyorsítótárakat. Ez a szerző tudatos döntése, hiszen az adatok közvetlenül leképezett fájlokból történő kiolvasása sok sarkot enged a motor megvalósításán. Az alábbiakban ezek közül néhány korántsem teljes listája található.

1. A tárolóban lévő adatok konzisztenciájának fenntartása, ha több folyamatból dolgozunk, az operációs rendszer felelőssége lesz. A következő részben ezt a szerelőt részletesen és képekkel tárgyaljuk.
2. A gyorsítótárak hiánya teljesen mentesíti az LMDB-t a dinamikus kiosztással járó többletterhelés alól. Az adatok beolvasása a gyakorlatban annyi, hogy a mutatót a virtuális memóriában a megfelelő címre állítja, és semmi több. Úgy hangzik, mint a képzelet, de a lerakatforrásban az összes calloc hívás a lerakatkonfigurációs funkcióban összpontosul.
3. A gyorsítótárak hiánya a szinkronizáláshoz kapcsolódó zárak hiányát is jelenti a hozzáférésükhöz. Az olvasók, amelyekből tetszőleges számú egyidejűleg létezhet, egyetlen mutex-szel sem találkoznak az adatok felé vezető úton. Ennek köszönhetően az olvasási sebesség ideális lineáris skálázhatósággal rendelkezik a CPU-k számát tekintve. Az LMDB-ben csak a módosító műveletek szinkronizálódnak. Egyszerre csak egy író lehet.
4. A minimális gyorsítótárazási és szinkronizálási logika megmenti a kódot a többszálú környezetben végzett munka során felmerülő rendkívül összetett típusú hibáktól. A Usenix OSDI 2014 konferencián két érdekes adatbázis-tanulmány hangzott el: "Nem minden fájlrendszert egyenlőnek hoznak létre: az összeomlásokkal konzisztens alkalmazások létrehozásának bonyolultságáról" и Adatbázisok kínzása szórakozás és haszon érdekében. Tőlük mind az LMDB példátlan megbízhatóságáról, mind a tranzakciók ACID tulajdonságainak szinte hibátlan megvalósításáról lehet tájékozódni, ami ugyanabban az SQLite-ban felülmúlja azt.
5. Az LMDB minimalizmusa lehetővé teszi, hogy a kódjának gépi reprezentációja teljes mértékben a processzor L1 gyorsítótárába kerüljön a kapott sebességi jellemzőkkel.

Sajnos iOS-ben a memórialeképezett fájlok nem olyan rózsásak, mint szeretnénk. Ahhoz, hogy tudatosabban beszélhessünk a velük kapcsolatos hátrányokról, fel kell idéznünk e mechanizmus operációs rendszerekben való megvalósításának általános elveit.

Általános információk a memóriakártyás fájlokról

Az operációs rendszer minden végrehajtható alkalmazáshoz egy folyamatnak nevezett entitást társít. Minden folyamathoz egy összefüggő címtartomány tartozik, amelyben mindent elhelyez, ami a működéséhez szükséges. A legalacsonyabb címek kóddal és keménykódolt adatokkal és erőforrásokkal rendelkező szakaszokat tartalmaznak. Következik a dinamikus címtér felfelé ívelő blokkja, amelyet jól ismerünk kupacként. A program működése során megjelenő entitások címeit tartalmazza. A tetején található az alkalmazásverem által használt memóriaterület. Vagy nő, vagy zsugorodik, vagyis a mérete is dinamikus természetű. Annak érdekében, hogy a verem és a kupac ne nyomja és ne zavarja egymást, a címtér különböző végein el vannak választva, a két dinamikus szakasz között felül és alul egy lyuk van. Az ebben a középső részben található címeket az operációs rendszer különféle entitások folyamataihoz való társításra használja. Konkrétan egy bizonyos folyamatos címkészletet képes leképezni egy lemezen lévő fájlra. Az ilyen fájlt memória-leképezett fájlnak nevezik

A folyamathoz lefoglalt címterület hatalmas. Elméletileg a címek számát csak a mutató mérete korlátozza, amit a rendszer bitessége határoz meg. Ha a fizikai memóriát 1 az 1-ben rendelnék hozzá, akkor az első folyamat felemésztené a teljes RAM-ot, és szó sem lenne többfeladatos működésről.

​Tapasztalatból tudjuk azonban, hogy a modern operációs rendszerek tetszőleges számú folyamatot képesek futtatni egyszerre. Ez annak köszönhető, hogy csak papíron foglalnak le sok memóriát a folyamatokhoz, de a valóságban csak azt a részt töltik be a fő fizikai memóriába, amelyre itt és most szükség van. Ezért a folyamathoz tartozó memóriát virtuálisnak nevezzük.

Az operációs rendszer a virtuális és fizikai memóriát meghatározott méretű oldalakba rendezi. Amint a virtuális memória egy bizonyos oldalára igény van, az operációs rendszer betölti azt a fizikai memóriába, és egy speciális táblázatba írja le a köztük lévő megfelelést. Ha nincsenek szabad helyek, akkor a korábban betöltött oldalak egyike a lemezre másolódik, és a kért oldal kerül a helyére. Ezt az eljárást, amelyre hamarosan visszatérünk, cserének nevezzük. Az alábbi ábra szemlélteti a leírt folyamatot. Ezen a 0-ás címû A oldal betöltõdött, és a 4-es címû fõ memórialapra került. Ezt a tényt a 0-s cellaszámú megfelelõségi táblázat is tükrözte.​

A memóriakártyás fájlokkal a történet pontosan ugyanaz. Logikailag állítólag folyamatosan és teljes egészében a virtuális címtérben helyezkednek el. A fizikai memóriába azonban oldalanként és csak igény szerint kerülnek be. Az ilyen oldalak módosítása szinkronizálva van a lemezen lévő fájllal. Így elvégezheti a fájl I/O-t, egyszerűen csak a memóriában lévő bájtokkal dolgozva – az operációs rendszer kernelje minden változtatást automatikusan átmásol az eredeti fájlba.​
.
Az alábbi kép bemutatja, hogy az LMDB hogyan szinkronizálja állapotát, amikor különböző folyamatokból származó adatbázissal dolgozik. A különböző folyamatok virtuális memóriájának ugyanabba a fájlba való leképezésével de facto kötelezzük az operációs rendszert, hogy tranzitív módon szinkronizálja egymással a címtereik egyes blokkjait, ahová az LMDB néz ki.​
.

Fontos árnyalat, hogy az LMDB alapértelmezés szerint módosítja az adatfájlt az írási rendszerhívási mechanizmuson keresztül, és maga a fájl csak olvasható módban jelenik meg. Ennek a megközelítésnek két fontos következménye van.

Az első következmény minden operációs rendszerre jellemző. Lényege, hogy védelmet adjon az adatbázisnak a hibás kód által okozott véletlen károsodás ellen. Mint ismeretes, egy folyamat végrehajtható utasításai szabadon hozzáférhetnek az adatokhoz bárhonnan a címterében. Ugyanakkor, mint az imént emlékeztünk, egy fájl írás-olvasás módban való megjelenítése azt jelenti, hogy bármely utasítás módosíthatja is azt. Ha ezt tévedésből teszi, például megpróbálja felülírni egy tömbelemet egy nem létező indexnél, akkor így véletlenül megváltoztathatja az erre a címre leképezett fájlt, ami az adatbázis sérüléséhez vezet. Ha a fájl csak olvasható módban jelenik meg, akkor a neki megfelelő címtér megváltoztatásának kísérlete a program összeomlásához vezet a jellel SIGSEGV, és a fájl érintetlen marad.

A második következmény már iOS-re jellemző. Sem a szerző, sem más forrás nem említi kifejezetten, de enélkül az LMDB alkalmatlan lenne ezen a mobil operációs rendszeren való futtatásra. A következő rész ennek megfontolásáról szól.

A memória-leképezett fájlok jellemzői az iOS rendszerben

2018-ban csodálatos riport készült a WWDC-n iOS Memory Deep Dive. Azt mondja, hogy iOS rendszerben a fizikai memóriában található összes oldal a 3 típus valamelyikéhez tartozik: piszkos, tömörített és tiszta.

A tiszta memória olyan oldalak gyűjteménye, amelyek biztonságosan kicserélhetők a fizikai memóriából. A bennük lévő adatok szükség szerint újratölthetők eredeti forrásukból. Ebbe a kategóriába tartoznak a csak olvasható memória-leképezett fájlok. Az iOS nem fél attól, hogy a fájlra leképezett oldalakat bármikor kirakja a memóriából, hiszen azok garantáltan szinkronizálva lesznek a lemezen lévő fájllal.
.
Minden módosított oldal bekerül a piszkos memóriába, függetlenül attól, hogy eredetileg hol található. Különösen a hozzájuk tartozó virtuális memóriába írással módosított memórialeképezett fájlok is ilyen módon kerülnek besorolásra. LMDB megnyitása zászlóval MDB_WRITEMAP, a változtatások elvégzése után Ön is meggyőződhet róla

Amint egy alkalmazás túl sok fizikai memóriát kezd lefoglalni, az iOS tömöríti a piszkos oldalait. A piszkos és tömörített oldalak által elfoglalt memóriagyűjtemény az alkalmazás úgynevezett memórialábnyoma. Amikor elér egy bizonyos küszöbértéket, az OOM killer rendszer démonja a folyamat után jön, és erőszakkal leállítja azt. Ez az iOS sajátossága az asztali operációs rendszerekhez képest. Ezzel szemben az iOS-ben nem lehetséges a memóriaterület csökkentése a fizikai memóriáról a lemezre cseréléssel, az okokról csak találgatni lehet. Lehetséges, hogy az oldalak intenzív lemezre és vissza mozgatása túl energiaigényes a mobileszközök számára, vagy az iOS megtakarítja az SSD-lemezeken lévő cellák újraírásának erőforrásait, vagy a tervezők nem voltak elégedettek a rendszer általános teljesítményével, ahol minden folyamatosan cserélve. Bárhogy is legyen, a tény marad.

A korábban már említett jó hír az, hogy az LMDB alapértelmezés szerint nem használja az mmap mechanizmust a fájlok frissítésére. Ebből következik, hogy a megjelenített adatokat az iOS tiszta memóriának minősíti, és nem járul hozzá a memóriaterülethez. Ezt a VM Tracker nevű Xcode eszközzel ellenőrizheti. Az alábbi képernyőkép az iOS Cloud alkalmazás virtuális memória állapotát mutatja működés közben. Kezdetben 2 LMDB példányt inicializáltak benne. Az elsőnek engedélyezték, hogy a fájlját 1 GiB virtuális memóriára képezze le, a másodiknak 512 MiB. Annak ellenére, hogy mindkét tároló bizonyos mennyiségű rezidens memóriát foglal el, egyik sem járul hozzá a piszkos mérethez.

Most eljött a rossz hír ideje. A 64 bites asztali operációs rendszerek cseremechanizmusának köszönhetően minden folyamat annyi virtuális címterületet foglalhat el, amennyit a merevlemezen lévő szabad hely lehetővé tesz az esetleges cseréhez. A csere lecserélése tömörítésre az iOS rendszerben drasztikusan csökkenti az elméleti maximumot. Most minden élő folyamatnak bele kell férnie a fő (olvasó RAM) memóriába, és minden, ami nem fér bele, kényszerlezárás alá esik. Úgy van megemlítve, mint a fentiekben jelentésés be hivatalos dokumentáció. Ennek következtében az iOS erősen korlátozza az mmap-on keresztüli kiosztáshoz rendelkezésre álló memória mennyiségét. Itt itt megtekintheti a különböző eszközökön lefoglalható memória empirikus korlátait ezzel a rendszerhívással. Az okostelefonok legmodernebb modelljein az iOS 2 gigabájttal, az iPad legjobb verzióinál pedig 4 gigabájttal lett bőkezű. A gyakorlatban természetesen a legfiatalabb támogatott eszközmodellekre kell koncentrálni, ahol minden nagyon szomorú. Még rosszabb, ha az alkalmazás memóriaállapotát a VM Trackerben megnézi, azt találja, hogy az LMDB messze nem az egyetlen, amely memórialeképezett memóriát igényel. A jó darabokat megeszik a rendszerelosztók, az erőforrásfájlok, a képkeretrendszerek és más kisebb ragadozók.

A felhőben végzett kísérletek eredményeként az LMDB által lefoglalt memória következő kompromisszumos értékeit kaptuk: 384 megabájt a 32 bites eszközöknél és 768 megabájt a 64 biteseknél. Miután ez a kötet elhasználódott, a kóddal minden módosítási művelet befejeződik MDB_MAP_FULL. Ilyen hibákat megfigyelünk megfigyelésünk során, de ezek elég kicsik ahhoz, hogy ebben a szakaszban figyelmen kívül hagyjuk őket.

A tárolás túlzott memóriafelhasználásának nem nyilvánvaló oka a hosszú élettartamú tranzakciók. Ahhoz, hogy megértsük, hogy ez a két jelenség hogyan kapcsolódik egymáshoz, segít a fennmaradó két LMDB bálnának figyelembe vételében.

3.2. Bálna #2. B+-fa

A kulcsérték-tároló tetején lévő táblák emulálásához a következő műveleteknek jelen kell lenniük az API-ban:

1. Új elem beszúrása.
2. Keressen egy elemet adott kulccsal.
3. Elem törlése.
4. Ismételje meg a kulcsintervallumokat rendezési sorrendjükben.

A legegyszerűbb adatstruktúra, amely mind a négy műveletet könnyen megvalósíthatja, egy bináris keresési fa. Mindegyik csomópontja egy kulcs, amely a gyermekkulcsok teljes részhalmazát két részfára osztja. A bal oldalon vannak azok, amelyek kisebbek, mint a szülő, és a jobb oldalon - azok, amelyek nagyobbak. A rendezett kulcskészlet beszerzése a klasszikus fabejárások egyikével érhető el

A bináris fáknak két alapvető hátrányuk van, amelyek megakadályozzák, hogy hatékonyak legyenek lemezadat-struktúraként. Először is, egyensúlyuk mértéke megjósolhatatlan. Jelentős a kockázata annak, hogy olyan fákat kapunk, amelyekben a különböző ágak magassága erősen eltérhet, ami jelentősen rontja a keresés algoritmikus bonyolultságát a várthoz képest. Másodszor, a csomópontok közötti kereszthivatkozások bősége megfosztja a bináris fákat a memória helyétől. Következésképpen egy fa több szomszédos csomópontjának egyszerű bejárása is hasonló számú oldal meglátogatását teheti szükségessé. Ez még akkor is probléma, ha a bináris fák, mint memórián belüli adatstruktúra hatékonyságáról beszélünk, hiszen a processzor gyorsítótárában nem olcsó az oldalak állandó forgatása. A csomópontokhoz kapcsolódó oldalak lemezről való gyakori felemelése esetén a dolgok nagyon rosszra fordulnak. siralmas.

A B-fák, mint bináris fák evolúciója, megoldják az előző bekezdésben azonosított problémákat. Először is, önkiegyensúlyozóak. Másodszor, mindegyik csomópontjuk nem 2-re, hanem M rendezett részhalmazra bontja a gyermekkulcsok halmazát, és az M szám meglehetősen nagy, több száz vagy akár ezres nagyságrendű is lehet.

Ezáltal:

1. Minden csomópontban nagyszámú már megrendelt kulcs van, és a fák nagyon alacsonyak.
2. A fa a memóriában szerzi meg a lokalitás tulajdonságát, mivel a közeli értékű kulcsok természetesen egymás mellett helyezkednek el az egyik vagy a szomszédos csomópontokon.
3. Csökkenti a tranzit csomópontok számát, amikor a keresési művelet során lefelé halad a fán.
4. Csökkenti a tartománylekérdezésekhez beolvasott célcsomópontok számát, mivel mindegyik már nagyszámú rendezett kulcsot tartalmaz.

Az LMDB a B-fa egy változatát, a B+ fát használja az adatok tárolására. A fenti diagram a három csomóponttípust mutatja, amelyeket tartalmaz:

1. A tetején a gyökér. Nem valósítja meg mást, mint az adatbázis fogalmát egy tárhelyen belül. Egyetlen LMDB-példányon belül több olyan adatbázist is létrehozhat, amelyek megosztják a leképezett virtuális címteret. Mindegyik a saját gyökeréből indul ki.
2. A legalsó szinten a levelek (levél). Ők és csakis ők tartalmazzák az adatbázisban tárolt kulcs-érték párokat. Ez egyébként a B+-fák sajátossága. Ha egy normál B-fa minden szint csomópontjában tárolja az értékrészeket, akkor a B+-variáció csak a legalacsonyabbon van. Ezt a tényt kijavítva a következőkben az LMDB-ben használt fa altípusát egyszerűen B-fának nevezzük.
3. A gyökér és a levelek között 0 vagy több technikai szint található navigációs (elágazó) csomópontokkal. Feladatuk a rendezett kulcskészlet felosztása a levelek között.

Fizikailag a csomópontok előre meghatározott hosszúságú memóriablokkok. Méretük többszöröse az operációs rendszer memórialapjai méretének, amiről fentebb beszéltünk. A csomópont szerkezete az alábbiakban látható. A fejléc metainformációkat tartalmaz, amelyek közül a legnyilvánvalóbb például az ellenőrző összeg. Ezután jönnek az eltolásokról szóló információk, amelyek mentén az adatokat tartalmazó cellák találhatók. Az adatok szerepe lehet akár kulcsok, ha navigációs csomópontokról beszélünk, akár teljes kulcs-érték párok levelek esetében.Az oldalak szerkezetéről bővebben a műben olvashat "A nagy teljesítményű kulcsértékű üzletek értékelése".

Miután foglalkoztunk az oldal csomópontjainak belső tartalmával, a továbbiakban az LMDB B-fát leegyszerűsített formában a következő formában ábrázoljuk.

A csomópontokkal rendelkező oldalak egymás után vannak elrendezve a lemezen. A nagyobb számú oldalak a fájl vége felé helyezkednek el. Az úgynevezett meta oldal (meta page) az eltolásokról tartalmaz információkat, amelyek segítségével minden fa gyökerét megtalálhatjuk. Fájl megnyitásakor az LMDB oldalanként átvizsgálja a fájlt a végétől az elejéig, keresve egy érvényes metaoldalt, és azon keresztül megkeresi a meglévő adatbázisokat.​

Most, ha van elképzelésünk az adatszervezés logikai és fizikai struktúrájáról, áttérhetünk az LMDB harmadik bálnájára. Segítségével minden tárolómódosítás tranzakciónként és egymástól elszigetelten történik, így az adatbázis egésze a multiverziós tulajdonságot is megadja.

3.3. Bálna #3. írásra másolás

Egyes B-fa műveletek a csomópontjain egy egész sor változtatást tartalmaznak. Az egyik példa egy új kulcs hozzáadása egy olyan csomóponthoz, amely már elérte a maximális kapacitását. Ebben az esetben először is két részre kell osztani a csomópontot, másodszor pedig hozzá kell adni egy hivatkozást az új kicsavart gyermekcsomóponthoz a szülőjében. Ez az eljárás potenciálisan nagyon veszélyes. Ha valamilyen okból (összeomlás, áramszünet, stb.) a sorozat változásainak csak egy része következik be, akkor a fa inkonzisztens állapotban marad.

Az adatbázisok hibatűrővé tételének egyik hagyományos megoldása egy további lemezalapú adatstruktúra, a tranzakciós napló, más néven írási napló (WAL) hozzáadása a B-fa mellé. Ez egy fájl, aminek a végére, szigorúan a B-fa módosítása előtt, a kívánt műveletet írják. Így, ha az öndiagnózis során adatsérülést észlel, az adatbázis lekérdezi a naplót, hogy megtisztítsa magát.

Az LMDB egy másik módszert választott hibatűrési mechanizmusként, amit íráson-másolásnak neveznek. Lényege, hogy ahelyett, hogy egy meglévő oldalon frissítené az adatokat, először teljesen lemásolja azokat, és a másolaton már minden módosítást végrehajt.​

Továbbá ahhoz, hogy a frissített adatok elérhetőek legyenek, meg kell változtatni a szülőcsomópontban hozzá kapcsolódóan a csomópontra mutató hivatkozást. Mivel ehhez is módosítani kell, ezért az is előre másolt. A folyamat rekurzív módon folytatódik egészen a gyökérig. A metaoldalon lévő adatok változnak utoljára.​​

Ha a folyamat hirtelen összeomlik a frissítési eljárás során, akkor vagy nem jön létre új metaoldal, vagy nem kerül kiírásra a lemezre a végéig, és az ellenőrző összege hibás lesz. E két esetben az új oldalak elérhetetlenek lesznek, és a régi oldalakat ez nem érinti. Ez kiküszöböli annak szükségességét, hogy az LMDB előre naplót írjon az adatok konzisztenciájának fenntartásához. De facto a lemezen való adattárolás fent leírt szerkezete egyidejűleg betölti funkcióját. Az explicit tranzakciós napló hiánya az LMDB egyik jellemzője, amely nagy adatolvasási sebességet biztosít.​

Az eredményül kapott konstrukció, amelyet csak hozzáfűző B-fának neveznek, természetesen biztosítja a tranzakciók elkülönítését és a többverziós változatot. Az LMDB-ben minden nyitott tranzakcióhoz egy naprakész fagyökér tartozik. Mindaddig, amíg a tranzakció nem fejeződik be, a hozzá tartozó fa oldalai soha nem változnak meg, és nem használjuk fel újra az adatok új verzióihoz. Így ameddig csak akar, pontosan azzal az adatkészlettel dolgozhat, amelyik releváns volt a tranzakció megnyitásának időpontja, még akkor is, ha a tárhely jelenleg aktívan frissül. Ez a multiverziós lényege, ami ideális adatforrássá teszi az LMDB-t kedvesünk számára UICollectionView. A tranzakció megnyitása után nem kell növelni az alkalmazás memóriaterületét, sietve kiszivattyúzni az aktuális adatokat valamilyen memórián belüli struktúrába, félve, hogy semmi sem marad. Ez a tulajdonság különbözteti meg az LMDB-t ugyanattól az SQLite-től, amely nem büszkélkedhet ilyen teljes elszigeteltséggel. Ha az utóbbiban két tranzakciót nyitottunk meg, és az egyiken belül törölünk egy bizonyos rekordot, a másikban már nem érhető el ugyanaz a rekord.

Az érem másik oldala a virtuális memória potenciálisan jelentősen magasabb fogyasztása. A dia megmutatja, hogyan fog kinézni az adatbázis-struktúra, ha egyidejűleg módosítják 3 nyitott olvasási tranzakcióval, amelyek az adatbázis különböző verzióit nézik. Mivel az LMDB nem tudja újra felhasználni azokat a csomópontokat, amelyek a tényleges tranzakciókhoz társított gyökerekből elérhetők, a tárolónak nincs más választása, mint egy másik negyedik gyökérkönyvtárat lefoglalni a memóriában, és ismét klónozni alá a módosított oldalakat.

Itt nem lesz felesleges felidézni a memória-leképezett fájlokról szóló részt. Úgy tűnik, hogy a virtuális memória többletfogyasztása nem zavarhat bennünket, mivel nem járul hozzá az alkalmazás memóriaterületéhez. Ugyanakkor leszögezték, hogy az iOS nagyon fukar az allokációban, és nem tudunk a mester válláról egy 1 terabájtos LMDB régiót biztosítani szerveren vagy asztalon, és egyáltalán nem gondolni erre a funkcióra. Ha lehetséges, próbálja meg a tranzakciók élettartamát a lehető legrövidebbre tartani.

4. Adatséma tervezése a kulcsérték API-n

Kezdjük az API elemzésével az LMDB által biztosított alapvető absztrakciókkal: környezet és adatbázisok, kulcsok és értékek, tranzakciók és kurzorok.

Megjegyzés a kódlistákkal kapcsolatban

Az LMDB nyilvános API-ban minden függvény hibakód formájában adja vissza munkája eredményét, de minden további listázásnál a tömörség kedvéért kimarad ennek ellenőrzése, a gyakorlatban saját kódot használtunk a repository-val való interakcióhoz. Villa C++ wrapperek lmdbxx, amelyben a hibák C++ kivételként jelentkeznek.

Az LMDB iOS vagy macOS projekthez való csatlakoztatásának leggyorsabb módjaként felajánlom a CocoaPod-omat. POSLMDB.

4.1. Alapvető absztrakciók

Környezet

Szerkezet MDB_env is az LMDB belső állapotának tárháza. Előtagú függvénycsalád mdb_env lehetővé teszi bizonyos tulajdonságainak konfigurálását. A legegyszerűbb esetben a motor inicializálása így néz ki.

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

A Mail.ru Cloud alkalmazásban csak két paraméter alapértelmezett értékeit változtattuk meg.

Az első a virtuális címtér mérete, amelyhez a tárolófájl hozzá van rendelve. Sajnos még ugyanazon az eszközön is jelentősen eltérhet a konkrét érték futásonként. Az iOS ezen funkciójának figyelembevétele érdekében dinamikusan választjuk ki a tárhely maximális mennyiségét. Egy bizonyos értéktől kezdve egymás után felezi a függvényt mdb_env_open nem ad vissza más eredményt, mint ENOMEM. Elméletileg ennek ellenkezője van - először foglaljon le egy minimális memóriát a motornak, majd, amikor hiba érkezik MDB_MAP_FULL, növelje meg. Ez azonban sokkal tövisesebb. Ennek az az oka, hogy a memória újraleképezése a függvény segítségével történik mdb_env_set_map_size érvényteleníti a motortól korábban kapott összes entitást (kurzorokat, tranzakciókat, kulcsokat és értékeket). Az események ilyen fordulatának a kódban való figyelembevétele annak jelentős bonyolításához vezet. Ha ennek ellenére a virtuális memória nagyon kedves számodra, akkor ez ok lehet arra, hogy megnézd azt a villát, amely messze előre ment. MDBX, ahol a deklarált jellemzők között van „automatikus on-the-fly adatbázis méretbeállítás”.

A második paraméter, amelynek alapértelmezett értéke nem felelt meg nekünk, a menetbiztonság biztosításának mechanikáját szabályozza. Sajnos, legalábbis az iOS 10-ben, problémák vannak a szál helyi tárolásának támogatásával. Emiatt a fenti példában az adattárat a zászlóval nyitjuk meg MDB_NOTLS. Ezen kívül az is szükséges volt Villa C++ wrapper lmdbxxváltozók vágásához ebben az attribútumban és az attribútumban.

adatbázisok

Az adatbázis a B-fa külön példánya, amelyről fentebb beszéltünk. Megnyitása egy tranzakción belül történik, ami elsőre kissé furcsának tűnhet.

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

Valójában egy tranzakció az LMDB-ben egy tárolási entitás, nem pedig egy konkrét adatbázis. Ez a koncepció lehetővé teszi atomi műveletek végrehajtását különböző adatbázisokban található entitásokon. Elméletileg ez megnyitja a táblák modellezésének lehetőségét különböző adatbázisok formájában, de egy időben én másfelé jártam, az alábbiakban részletesen leírom.

Kulcsok és értékek

Szerkezet MDB_val modellezi a kulcs és az érték fogalmát. Az adattárnak fogalma sincs a szemantikájukról. Számára valami, ami más, csak egy adott méretű bájtok tömbje. A maximális kulcsméret 512 bájt.

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

Az üzlet összehasonlító eszközt használ a kulcsok növekvő sorrendbe rendezésére. Ha nem cseréli ki a sajátjával, akkor az alapértelmezett lesz, amely lexikográfiai sorrendben bájtonként rendezi őket.​

ügyletek

A tranzakciós eszköz részletes leírása a előző fejezet, ezért itt egy rövid sorban megismétlem főbb tulajdonságaikat:

1. Minden alapvető tulajdonság támogatása SAVKulcsszavak: atomitás, konzisztencia, izoláció és megbízhatóság. Nem tehetek róla, de megjegyzem, hogy a MacOS és az iOS tartósságát illetően egy hiba javítva van az MDBX-ben. Bővebben náluk olvashat README.
2. A többszálú kezelés megközelítését az "egy író / több olvasó" séma írja le. Az írók blokkolják egymást, de nem blokkolják az olvasókat. Az olvasók nem blokkolják sem az írókat, sem egymást.
3. Beágyazott tranzakciók támogatása.
4. Több verzió támogatása.

A multiverzió az LMDB-ben annyira jó, hogy szeretném gyakorlatban is bemutatni. Az alábbi kód azt mutatja, hogy minden tranzakció pontosan azzal az adatbázisverzióval működik, amely a megnyitásakor releváns volt, és teljesen el van szigetelve minden későbbi változástól. A repository inicializálása és a tesztrekord hozzáadása nem érdekes, ezért ezek a rituálék a spoiler alatt maradnak.

Teszt bejegyzés hozzáadása

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

Opcionálisan azt javaslom, hogy próbálja ki ugyanezt a trükköt az SQLite-tal, és nézze meg, mi történik.

A multiverzió nagyon szép előnyökkel jár az iOS fejlesztők életében. Ezzel a tulajdonsággal egyszerűen és természetesen módosíthatja a képernyő-űrlapok adatforrás-frissítési arányát a felhasználói élmény megfontolásai alapján. Vegyük például a Mail.ru Cloud alkalmazás egy olyan funkcióját, mint a tartalom automatikus betöltése a rendszer médiagalériájából. Jó kapcsolat esetén a kliens másodpercenként több fényképet is képes hozzáadni a szerverhez. Ha minden letöltés után frissít UICollectionView a felhasználó felhőjében lévő médiatartalommal elfelejtheti a 60 fps-t és a sima görgetést a folyamat során. A gyakori képernyőfrissítések elkerülése érdekében valamilyen módon korlátozni kell az adatok változásának sebességét az alapban UICollectionViewDataSource.

Ha az adatbázis nem támogatja a többverziót, és csak az aktuális állapottal teszi lehetővé a munkát, akkor az időstabil adatpillanatkép létrehozásához vagy valamilyen memórián belüli adatstruktúrába, vagy ideiglenes táblába kell másolni. Ezen módszerek bármelyike ​​nagyon drága. A memórián belüli tárolás esetén megkapjuk mind a konstruált objektumok tárolása okozta memóriaköltségeket, mind a redundáns ORM-transzformációkhoz kapcsolódó időköltségeket. Ami az ideiglenes asztalt illeti, ez még drágább öröm, aminek csak nem triviális esetekben van értelme.

Az LMDB többverziós változata nagyon elegáns módon oldja meg a stabil adatforrás fenntartásának problémáját. Elég csak megnyitni egy tranzakciót, és íme - amíg nem fejezzük be, az adatkészlet garantáltan rögzítve lesz. A frissítési sebesség logikája most teljes mértékben a prezentációs réteg kezében van, jelentős erőforrások nélkül.

Kurzorok

A kurzorok mechanizmust biztosítanak a kulcs-érték párok rendezett iterációjához egy B-fa bejárásával. Nélkülük lehetetlen lenne hatékonyan modellezni a táblákat az adatbázisban, amelyre most rátérünk.

4.2. Táblázat modellezés

A kulcssorrend tulajdonság lehetővé teszi, hogy legfelső szintű absztrakciót hozzon létre, például táblázatot az alapvető absztrakciók tetejére. Tekintsük ezt a folyamatot a felhőkliens fő táblázatának példáján, amelyben a felhasználó összes fájljával és mappájával kapcsolatos információk gyorsítótárazásra kerülnek.

Táblázat séma

Az egyik gyakori forgatókönyv, amikor a mappafát tartalmazó tábla szerkezetét élesíteni kell, az az, hogy az adott könyvtáron belül található összes elemet ki kell jelölni. Szomszédsági lista. A kulcsérték tároló tetejére való megvalósításához a fájlok és mappák kulcsait úgy kell rendezni, hogy azok a szülőkönyvtárhoz való tartozás alapján legyenek csoportosítva. Ezenkívül ahhoz, hogy a könyvtár tartalma a Windows-felhasználó számára ismert formában jelenjen meg (először a mappák, majd a fájlok, mindkettő ábécé szerint van rendezve), szükséges a megfelelő további mezők szerepeltetése a kulcsban.

Az alábbi képen látható, hogy a feladat alapján hogyan nézhet ki a kulcsok bájttömbként való megjelenítése. Először a szülőkönyvtár azonosítóval (piros), majd a típussal (zöld) és már a farokban a névvel (kék) kerül a bájtok elhelyezése. a szükséges módon. Az azonos piros előtaggal ellátott kulcsok szekvenciális bejárása a hozzájuk tartozó értékeket abban a sorrendben adja meg, ahogyan azokat a felhasználói felületen (jobbra) meg kell jeleníteni, további utófeldolgozás nélkül.

Kulcsok és értékek sorba rendezése

Világszerte számos módszer létezik az objektumok sorozatosítására. Mivel a sebességen kívül nem volt más követelményünk, ezért a lehető leggyorsabbat választottuk magunknak - egy memóriakiírást, amelyet a C nyelvi szerkezet egy példánya foglal el, így egy könyvtárelem kulcsát a következő szerkezettel modellezhetjük NodeKey.

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

Menteni NodeKey tárolási igény tárgyban MDB_val helyezzük a mutatót az adatokra a struktúra elejének címére, és számítsuk ki a méretüket a függvénnyel sizeof.

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

Az adatbázis-kiválasztási kritériumokról szóló első fejezetben fontos kiválasztási tényezőként említettem a dinamikus allokációk minimalizálását a CRUD műveletek részeként. Funkció kód serialize bemutatja, hogy az LMDB esetében hogyan lehet ezeket teljesen elkerülni, ha új rekordok kerülnek be az adatbázisba. A szerverről bejövő bájttömb először veremstruktúrákká alakul, majd triviálisan bekerül a tárolóba. Tekintettel arra, hogy az LMDB-n belül sincsenek dinamikus kiosztások, az iOS szabványai szerint fantasztikus helyzetbe kerülhet - csak veremmemóriát használjon az adatokkal való munkavégzés során a hálózattól a lemezig!

Kulcsrendelés bináris komparátorral

A kulcssorrend relációt egy speciális függvény, az úgynevezett összehasonlító adja meg. Mivel a motor semmit sem tud a bennük lévő bájtok szemantikájáról, az alapértelmezett összehasonlítónak nincs más dolga, mint lexikográfiai sorrendbe rendezni a kulcsokat, és a bájtonkénti összehasonlításhoz folyamodik. Használata szerkezetek elrendezésére hasonlít a faragó fejszével való borotválkozáshoz. Egyszerű esetekben azonban ezt a módszert elfogadhatónak tartom. Az alternatívát az alábbiakban ismertetjük, de itt megjegyzek pár, útközben szétszórt gereblyét.

Az első dolog, amit szem előtt kell tartani, a primitív adattípusok memória-reprezentációja. Tehát minden Apple-eszközön az egész változókat a formátumban tárolják Kis Endian. Ez azt jelenti, hogy a legkisebb jelentőségű bájt a bal oldalon lesz, és nem tudja majd rendezni az egész számokat a bájtonkénti összehasonlításukkal. Például, ha ezt egy 0 és 511 közötti számkészlettel próbálja megtenni, a következő eredményt kapja.

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

A probléma megoldásához az egész számokat a kulcsban a bájt-összehasonlítónak megfelelő formátumban kell tárolni. A családtól származó funkciók segítik a szükséges átalakítást. hton* (különösen htons a példából származó kétbájtos számokhoz).

A karakterláncok programozási ábrázolásának formátuma, mint tudod, egy egész история. Ha a karakterláncok szemantikája, valamint a memóriában való megjelenítésükre használt kódolás azt sugallja, hogy karakterenként egynél több bájt lehet, akkor jobb, ha azonnal elhagyja az alapértelmezett összehasonlító használatának ötletét.

A második dolog, amit szem előtt kell tartani igazítási elvek struct mező fordító. Emiatt a memóriában a mezők között szemétértékű bájtok képződhetnek, ami természetesen megszakítja a bájtrendezést. A szemét eltávolításához vagy deklarálnia kell a mezőket egy szigorúan meghatározott sorrendben, az igazítási szabályokat szem előtt tartva, vagy használja az attribútumot a szerkezet deklarációjában packed.

Kulcsrendelés külső összehasonlító segítségével

A kulcs-összehasonlító logika túl bonyolultnak bizonyulhat egy bináris összehasonlító számára. Ennek egyik oka a műszaki mezők jelenléte a szerkezeteken belül. Előfordulásukat egy számunkra már ismerős kulcs példáján illusztrálom egy címtárelemhez.

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

Egyszerűsége ellenére az esetek túlnyomó többségében túl sok memóriát fogyaszt. A címpuffer 256 bájt, bár a fájl- és mappanevek átlagosan ritkán haladják meg a 20-30 karaktert.

A rekord méretének optimalizálásának egyik szabványos technikája a „kivágás”, hogy illeszkedjen a tényleges mérethez. Lényege, hogy az összes változó hosszúságú mező tartalma a struktúra végén található pufferben, hosszuk pedig külön változókban kerül tárolásra.E megközelítésnek megfelelően a kulcs NodeKey a következő módon alakul át.

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

Továbbá a szerializálás során nincs megadva adatméretként sizeof a teljes struktúra, és az összes mező mérete rögzített hosszúságú plusz a puffer ténylegesen használt részének mérete.

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

A refaktorálás eredményeként jelentős megtakarítást értünk el a kulcsok által elfoglalt területen. A műszaki terület miatt azonban nameLength, az alapértelmezett bináris összehasonlító már nem alkalmas kulcs-összehasonlításra. Ha nem cseréljük le a sajátunkkal, akkor a név hossza fontosabb tényező lesz a rendezésben, mint maga a név.

Az LMDB lehetővé teszi, hogy minden adatbázisnak saját kulcs-összehasonlító funkciója legyen. Ez a funkció segítségével történik mdb_set_compare szigorúan felnyitás előtt. Nyilvánvaló okokból az adatbázis nem változtatható meg teljes élettartama alatt. A bemeneten a komparátor két kulcsot kap bináris formátumban, a kimeneten pedig az összehasonlítás eredményét adja vissza: kisebb, mint (-1), nagyobb, mint (1) vagy egyenlő (0). Pseudocode for NodeKey úgy néz ki.

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

Mindaddig, amíg az adatbázisban lévő összes kulcs azonos típusú, törvényes, hogy a bájtábrázolásukat feltétel nélkül a kulcs alkalmazási szerkezetének típusára adja át. Van itt egy árnyalat, de erről egy kicsit lejjebb, az „Reading Records” alfejezetben lesz szó.

Értékek sorosítása

A tárolt rekordok kulcsaival az LMDB rendkívül intenzíven dolgozik. Bármely alkalmazási művelet keretein belül összehasonlításra kerülnek egymással, és a teljes megoldás teljesítménye a komparátor sebességétől függ. Egy ideális világban az alapértelmezett bináris komparátornak elegendőnek kell lennie a kulcsok összehasonlításához, de ha valóban a sajátját kellett használnia, akkor a kulcsok deszerializálásának folyamata a lehető leggyorsabb legyen.

Az adatbázist nem különösebben érdekli a rekord Érték része (érték). Átalakítása bájtábrázolásból objektummá csak akkor történik meg, ha az alkalmazás kódja már megköveteli, például a képernyőn való megjelenítéséhez. Mivel ez viszonylag ritkán fordul elő, ennek az eljárásnak a sebességével szemben támasztott követelmények nem annyira kritikusak, és megvalósítása során sokkal szabadabban tudunk a kényelemre koncentrálni.Például a még nem letöltött fájlok metaadatainak szerializálásához használjuk NSKeyedArchiver.

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

Vannak azonban olyan esetek, amikor a teljesítmény számít. Például a felhasználói felhő fájlstruktúrájával kapcsolatos metainformációk mentésekor ugyanazt az objektummemóriakiíratást használjuk. A szerializált reprezentáció létrehozásának feladatának csúcspontja az a tény, hogy egy könyvtár elemeit osztályhierarchia modellezi.​

A C nyelvű megvalósításhoz az örökösök konkrét mezőit külön struktúrákba szedjük, és az alaphoz való kapcsolatukat egy unió típusú mezőn keresztül határozzuk meg. A szakszervezet tényleges tartalmát a típustechnikai attribútum határozza meg.

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

Bejegyzések hozzáadása és frissítése

A soros kulcs és érték hozzáadható az áruházhoz. Ehhez a funkciót használják mdb_put.

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

A konfigurációs szakaszban engedélyezhető vagy megtiltható a repository több rekord tárolása ugyanazzal a kulccsal.​​ Ha a kulcsok többszörözése tilos, akkor rekord beillesztésekor meghatározhatja, hogy egy már meglévő rekord frissítése engedélyezett-e vagy sem. Ha a kopás csak a kód hibája miatt következhet be, akkor ez ellen a zászló megadásával lehet biztosítani NOOVERWRITE.

Feljegyzések olvasása

Az LMDB rekordok olvasásának funkciója a mdb_get. Ha a kulcs-érték párt korábban kiírt struktúrák képviselik, akkor ez az eljárás így néz ki.

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

A bemutatott lista bemutatja, hogy a struktúrák dumpján keresztül történő szerializálás hogyan teszi lehetővé, hogy megszabaduljon a dinamikus allokációktól nemcsak íráskor, hanem adatok olvasásakor is. Funkcióból származik mdb_get a mutató pontosan azt a virtuális memóriacímet nézi, ahol az adatbázis az objektum byte-reprezentációját tárolja. Valójában egyfajta ORM-et kapunk, szinte ingyenesen, amely nagyon nagy sebességű adatolvasást biztosít. A megközelítés minden szépsége mellett meg kell emlékezni számos kapcsolódó jellemzőről.

1. A csak olvasható tranzakcióknál az értékstruktúrára mutató mutató garantáltan csak a tranzakció lezárásáig marad érvényben. Amint azt korábban megjegyeztük, a B-fa oldalai, amelyeken az objektum található, a másolás az írásra elvnek köszönhetően változatlanok maradnak mindaddig, amíg legalább egy tranzakció hivatkozik rájuk. Ugyanakkor, amint a hozzájuk tartozó utolsó tranzakció befejeződött, az oldalak újra felhasználhatók új adatokhoz. Ha szükséges, hogy az objektumok túléljék az őket létrehozó tranzakciót, akkor is le kell másolni őket.
2. Readwrite tranzakció esetén a kapott struktúraértékre mutató mutató csak az első módosítási eljárásig (adatírás vagy törlés) lesz érvényes.
3. Annak ellenére, hogy a szerkezet NodeValue nem teljes értékű, hanem vágott (lásd a "Kulcsok rendezése külső összehasonlítóval" alfejezetet), a mutatón keresztül könnyen elérheti a mezőit. A lényeg az, hogy ne hivatkozzunk rá!
4. A kapott mutatón keresztül semmilyen esetben sem módosíthatja a szerkezetet. Minden változtatást csak a módszerrel szabad végrehajtani mdb_put. Ennek ellenére ez nem fog működni, mivel a memóriaterület, ahol ez a szerkezet található, csak olvasható módban van leképezve.
5. Egy fájl átrendezése egy folyamat címterébe, például a maximális tárméret növelése érdekében a funkció használatával mdb_env_set_map_size teljesen érvényteleníti az összes tranzakciót és általában a kapcsolódó entitást, és különösen az objektumok olvasására mutató mutatókat.

Végül még egy olyan alattomos tulajdonság, hogy a lényegének feltárása nem fér bele még egy pontba. A B-fáról szóló fejezetben ábrát adtam lapjainak emlékben való elrendezéséről. Ebből következik, hogy a soros adatot tartalmazó puffer kezdetének címe abszolút tetszőleges lehet. Emiatt a mutató rájuk, kapott a szerkezetben MDB_val és egy szerkezetre mutató mutatóra öntve általában nincs igazítva. Ugyanakkor egyes chipek architektúrája (iOS esetében ez az armv7) megköveteli, hogy bármely adat címe egy gépszó méretének többszöröse legyen, vagy más szóval a rendszer bitességének. (armv7 esetén ez 32 bites). Más szóval, egy olyan művelet, mint *(int *foo)0x800002 rajtuk egyenlővé válik a szökéssel, és ítélettel kivégzéshez vezet EXC_ARM_DA_ALIGN. Kétféleképpen lehet elkerülni egy ilyen szomorú sorsot.

Az első az, hogy előzőleg átmásoljuk az adatokat egy ismert, igazított struktúrába. Például egy egyéni összehasonlítón ez a következőképpen jelenik meg.

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

Egy másik lehetőség, ha előre értesítjük a fordítót arról, hogy a kulcsot és értéket tartalmazó struktúrák nem igazíthatók attribútum használatával aligned(1). Az ARM-en ugyanez a hatás érvényesülhet elérni és a packed attribútum használatával. Tekintettel arra, hogy a szerkezet által elfoglalt hely optimalizálásához is hozzájárul, számomra ez a módszer előnyösebb, bár приводит az adathozzáférési műveletek költségeinek növelése érdekében.

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

Tartománylekérdezések

A rekordok csoportján való iterációhoz az LMDB kurzorabsztrakciót biztosít. Nézzük meg, hogyan dolgozhatunk vele egy olyan táblázat példáján, amely már ismerős felhasználói felhő metaadatokat tartalmaz.

A könyvtárban lévő fájlok listájának megjelenítése részeként meg kell találnia az összes kulcsot, amelyhez a gyermekfájlok és mappák társítva vannak. Az előző alfejezetekben a kulcsokat rendeztük NodeKey hogy először a szülőkönyvtár-azonosítójuk szerint legyenek rendezve. Így technikailag a mappa tartalmának megszerzésének feladata a kurzornak egy adott előtaggal rendelkező kulcscsoport felső határára való helyezésére, majd az alsó határig történő iterációra korlátozódik.

Szekvenciális kereséssel megtalálhatja a felső határt "a homlokon". Ehhez a kurzort az adatbázisban lévő teljes kulcslista elejére kell helyezni, majd addig kell növelni, amíg a szülőkönyvtár-azonosítóval ellátott kulcs meg nem jelenik alatta. Ennek a megközelítésnek két nyilvánvaló hátránya van:

1. A keresés lineáris összetettsége, bár, mint tudod, általában a fákban és különösen a B-fában, logaritmikus időben is elvégezhető.
2. Hiába, minden, a kívánt oldalt megelőző oldal felkerül a fájlból a fő memóriába, ami rendkívül drága.

Szerencsére az LMDB API hatékony módot biztosít a kurzor kezdeti pozicionálására, ehhez létre kell hozni egy kulcsot, amelynek értéke kisebb vagy egyenlő, mint az intervallum felső határán található kulcs. Például a fenti ábra listája kapcsán készíthetünk olyan kulcsot, amelyben a mező parentId egyenlő lesz 2-vel, és az összes többi nullával van kitöltve. Egy ilyen részben kitöltött kulcsot a függvény bemenetére táplálunk mdb_cursor_get működését jelzi 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);

Ha megtaláltuk a kulcscsoport felső határát, akkor addig iterálunk rajta, amíg vagy találkozunk, vagy a kulcs egy másikkal parentId, vagy egyáltalán nem fogynak ki a kulcsok

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

Ami jó, az mdb_cursor_get használatával végzett iteráció részeként nem csak a kulcsot, hanem az értéket is megkapjuk. Ha a kiválasztási feltételek teljesítéséhez szükség van többek között a rekord értékrészének mezőinek ellenőrzésére, akkor ezek további gesztusok nélkül saját maguk számára is elérhetőek.

4.3. Táblázatok közötti kapcsolatok modellezése

A mai napig sikerült minden szempontot figyelembe vennünk az egytáblás adatbázis tervezésének és munkavégzésének. Azt mondhatjuk, hogy a tábla rendezett rekordok halmaza, amely azonos típusú kulcs-érték párokból áll. Ha egy kulcsot téglalapként jelenít meg, a hozzá tartozó értéket pedig dobozként, akkor az adatbázis vizuális diagramját kapja.

.

A való életben azonban ritkán lehet ilyen kevés vérrel boldogulni. Egy adatbázisban gyakran először is több táblára van szükség, másodszor pedig az elsődleges kulcstól eltérő sorrendben történő kijelöléseket kell végrehajtani. Ez az utolsó rész ezek létrehozásának és összekapcsolásának kérdéseivel foglalkozik.

Index táblázatok

A felhőalkalmazásnak van egy „Galéria” része. Megjeleníti a médiatartalmakat a teljes felhőből, dátum szerint rendezve. Egy ilyen kijelölés optimális megvalósításához a fő táblázat mellett létre kell hozni egy másikat új típusú kulcsokkal. Tartalmaznak egy mezőt a fájl létrehozásának dátumával, amely elsődleges rendezési feltételként fog működni. Mivel az új kulcsok ugyanazokra az adatokra vonatkoznak, mint a mögöttes tábla kulcsai, ezért indexkulcsoknak nevezzük őket. Az alábbi képen narancssárgával vannak kiemelve.

Annak érdekében, hogy ugyanazon az adatbázison belül a különböző táblák kulcsait el lehessen választani egymástól, mindegyikhez egy további technikai mező tableId került. Azáltal, hogy a rendezésnél ez a legmagasabb prioritású, a kulcsokat először táblázatok szerint csoportosítjuk, és már a táblákon belül – saját szabályaink szerint.​

Az indexkulcs ugyanazokra az adatokra vonatkozik, mint az elsődleges kulcs. Ennek a tulajdonságnak az egyszerű megvalósítása az elsődleges kulcs értékrészének másolatának hozzárendelésével több szempontból is szuboptimális egyszerre:​

1. Területfoglalás szempontjából a metaadatok meglehetősen gazdagok lehetnek.
2. Teljesítmény szempontjából, mivel a csomóponti metaadatok frissítésekor két kulcsot kell felülírnia.
3. A kódtámogatás szempontjából ugyanis ha elfelejtjük frissíteni valamelyik kulcs adatait, akkor egy apró adatinkonzisztencia-hibát kapunk a tárhelyen.

Ezután megvizsgáljuk, hogyan lehet ezeket a hiányosságokat kiküszöbölni.

A táblák közötti kapcsolatok szervezése

A minta kiválóan alkalmas egy indextáblázat és a fő táblázat összekapcsolására "kulcs mint érték". Ahogy a neve is sugallja, az indexrekord érték része az elsődleges kulcs értékének másolata. Ez a megközelítés kiküszöböli az összes fent felsorolt, az elsődleges rekord értékrészének másolatának tárolásával kapcsolatos hátrányokat. Az egyetlen díj az, hogy az indexkulcs értékének lekéréséhez egy helyett 2 lekérdezést kell végrehajtania az adatbázisban. Sematikusan a kapott adatbázisséma a következő.

A táblák közötti kapcsolatok szervezésének másik mintája az "redundáns kulcs". Lényege, hogy további attribútumokat adjon a kulcshoz, amelyek nem a rendezéshez, hanem a hozzá tartozó kulcs újraalkotásához szükségesek, azonban a Mail.ru Cloud alkalmazásban valós példák vannak a használatára, hogy elkerüljük a mélyreható merülést konkrét iOS keretrendszerekkel összefüggésben hozok egy fiktív, de érthetőbb példát.

A Cloud mobilklienseknek van egy oldala, amely megjeleníti az összes fájlt és mappát, amelyet a felhasználó megosztott másokkal. Mivel viszonylag kevés ilyen fájl van, és sok konkrét információ kapcsolódik hozzájuk a nyilvánosságra vonatkozóan (kinek adnak hozzáférést, milyen jogokkal stb.), nem lesz ésszerű ezt az értékrésszel terhelni. a rekord a főtáblázatban. Ha azonban az ilyen fájlokat offline szeretné megjeleníteni, akkor is el kell tárolnia valahol. Természetes megoldás, ha külön táblázatot készítünk hozzá. Az alábbi ábrán a kulcsa "P" előtaggal van ellátva, a "propname" helyőrző pedig lecserélhető a pontosabb "public info" értékre.​

Minden egyedi metaadat, amelynek érdekében az új tábla létrejött, átkerül a rekord érték részébe. Ugyanakkor nem szeretném a főtáblában már tárolt fájlok és mappák adatait megkettőzni. Ehelyett redundáns adatok kerülnek a "P" kulcshoz a "csomópontazonosító" és az "időbélyeg" mezők formájában. Ezeknek köszönhetően összeállítható egy indexkulcs, amellyel megkaphatja az elsődleges kulcsot, amellyel végül megkaphatja a csomópont metaadatait.

Következtetés

Az LMDB megvalósítás eredményeit pozitívan értékeljük. Ezt követően az alkalmazáslefagyások száma 30%-kal csökkent.

Az elvégzett munka eredményei az iOS csapatán kívül találtak választ. Jelenleg az Android alkalmazás egyik fő "Fájlok" része is átállt az LMDB használatára, és további részek is készülnek. A C nyelv, amelyen a kulcsérték-tárolás van megvalósítva, jó segítség volt ahhoz, hogy az alkalmazás kezdetben platformfüggetlen legyen a C ++ nyelven. Az eredményül kapott C ++ könyvtár zökkenőmentes összekapcsolásához az Objective-C és a Kotlin platformkóddal egy kódgenerátort használtak. Djinni a Dropboxból, de ez egy másik történet.

Forrás: will.com