Na jeseň roku 2019 došlo v tíme Mail.ru Cloud iOS k dlho očakávanej udalosti. Hlavná databáza pre trvalé ukladanie stavu aplikácie sa stala pre mobilný svet veľmi exotickou Lightning Memory-Mapped Database (LMDB). Pod zostrihom vám ponúkame jeho podrobnú recenziu v štyroch častiach. Najprv si povedzme o dôvodoch takejto netriviálnej a ťažkej voľby. Potom prejdeme k zváženiu troch pilierov v srdci architektúry LMDB: pamäťovo mapované súbory, B+-strom, prístup kopírovania pri zápise na implementáciu transakcií a multiverzie. Nakoniec, ako dezert - praktická časť. V ňom sa pozrieme na to, ako navrhnúť a implementovať databázovú schému s niekoľkými tabuľkami, vrátane indexovej, nad nízkoúrovňovým API kľúč-hodnota.

Obsah

1. Motivácia na realizáciu
2. LMDB polohovanie
3. Tri piliere LMDB
   3.1. Veľryba #1. Súbory mapované v pamäti
   3.2. Veľryba #2. B+-strom
   3.3. Veľryba #3. Kopírovanie pri zápise
4. Navrhovanie dátovej schémy nad rozhraním API kľúč – hodnota
   4.1. Základné abstrakcie
   4.2. Stolové modelovanie
   4.3. Modelovanie vzťahov medzi tabuľkami

1. Motivácia pre realizáciu

Jeden rok v roku 2015 sme si dali tú námahu zmerať, ako často rozhranie našej aplikácie zaostáva. Urobili sme to z nejakého dôvodu. Častejšie sme dostávali sťažnosti, že aplikácia niekedy prestane reagovať na akcie používateľa: nedajú sa stlačiť tlačidlá, neposúvajú sa zoznamy atď. O mechanike meraní povedal na AvitoTech, tak tu uvádzam len poradie čísel.

Výsledky merania sa pre nás stali studenou sprchou. Ukázalo sa, že problémov spôsobených zamrznutím je oveľa viac ako ktorékoľvek iné. Ak pred uvedomením si tejto skutočnosti bol hlavným technickým ukazovateľom kvality bezporuchový, tak po zameraní posunutý na freeze free.

Po vybudovaní prístrojová doska so zamrznutím a po výdavkoch kvantitatívne и kvalita analýzou ich dôvodov sa ukázal hlavný nepriateľ - ťažká obchodná logika vykonávaná v hlavnom vlákne aplikácie. Prirodzenou reakciou na túto hanbu bola spaľujúca túžba strčiť ju do pracovných prúdov. Na systematické vyriešenie tohto problému sme sa uchýlili k viacvláknovej architektúre založenej na ľahkých hercoch. Venoval som ho jeho prispôsobeniu pre svet iOS dve vlákna na kolektívnom Twitteri a článok o Habrém. V rámci súčasného rozprávania chcem zdôrazniť tie aspekty rozhodnutia, ktoré ovplyvnili výber databázy.​

​Actor model organizácie systému predpokladá, že multithreading sa stáva jeho druhou podstatou. Modelové objekty v nej radi prekračujú hranice potokov. A nerobia to niekedy a tu a tam, ale takmer neustále a všade.​

Databáza je jedným zo základných prvkov v prezentovanom diagrame. Jeho hlavnou úlohou je implementácia makrovzoru Zdieľaná databáza. Ak sa v podnikovom svete používa na organizáciu synchronizácie údajov medzi službami, potom v prípade architektúry aktérov - údajov medzi vláknami. Potrebovali sme teda databázu, ktorá by nespôsobovala ani minimálne ťažkosti pri práci s ňou vo viacvláknovom prostredí. Predovšetkým to znamená, že objekty získané z neho musia byť prinajmenšom bezpečné pre vlákna a ideálne úplne nemenné. Ako viete, ten možno použiť súčasne z niekoľkých vlákien bez toho, aby ste sa uchýlili k uzamknutiu, čo má priaznivý vplyv na výkon.

Druhým významným faktorom, ktorý ovplyvnil výber databázy, bolo naše cloudové API. Bol inšpirovaný prístupom synchronizácie, ktorý prijal git. Rovnako ako on sme mierili na offline-first API, čo pre cloudových klientov vyzerá viac ako vhodné. Predpokladalo sa, že iba raz vypumpujú celý stav cloudu a potom dôjde v drvivej väčšine prípadov k synchronizácii prostredníctvom zavádzania zmien. Bohužiaľ, táto možnosť je zatiaľ len v teoretickej zóne a klienti sa v praxi s náplasťami nenaučili pracovať. Je na to viacero objektívnych dôvodov, ktoré, aby sme nezdržiavali úvod, vynecháme zátvorky. Oveľa zaujímavejšie sú teraz poučné závery lekcie o tom, čo sa stane, keď API povie „A“ a jeho spotrebiteľ nepovie „B“.

Ak si teda predstavíte git, ktorý pri vykonávaní príkazu pull namiesto aplikovania opráv na lokálnu snímku porovnáva svoj úplný stav s úplným stavom servera, budete mať pomerne presnú predstavu o tom, ako prebieha synchronizácia v cloude. klientov. Je ľahké uhádnuť, že na jeho implementáciu musíte v pamäti prideliť dva stromy DOM s metainformáciami o všetkých serveroch a lokálnych súboroch. Ukazuje sa, že ak používateľ uloží 500 tisíc súborov v cloude, potom na jeho synchronizáciu je potrebné znovu vytvoriť a zničiť dva stromy s 1 miliónom uzlov. Ale každý uzol je agregát obsahujúci graf čiastkových objektov. V tomto svetle sa očakávali výsledky profilovania. Ukázalo sa, že aj bez zohľadnenia algoritmu zlučovania stojí samotný postup vytvorenia a následného zničenia obrovského množstva malých objektov pekný cent.Situáciu zhoršuje skutočnosť, že základná synchronizačná operácia je zahrnutá vo veľkom počte používateľských skriptov. V dôsledku toho fixujeme druhé dôležité kritérium pri výbere databázy - schopnosť implementovať operácie CRUD bez dynamickej alokácie objektov.

Ostatné požiadavky sú tradičnejšie a ich celý zoznam je nasledovný.

1. Bezpečnosť závitu.
2. Viacnásobné spracovanie. Diktované túžbou používať rovnakú inštanciu databázy na synchronizáciu stavu nielen medzi vláknami, ale aj medzi hlavnou aplikáciou a rozšíreniami iOS.
3. Schopnosť reprezentovať uložené entity ako nemenné objekty.​
4. Žiadne dynamické alokácie v rámci operácií CRUD.
5. Podpora transakcií pre základné vlastnosti ACID: atomicita, konzistencia, izolácia a spoľahlivosť.
6. Rýchlosť v najpopulárnejších prípadoch.

S týmto súborom požiadaviek bol a zostáva SQLite dobrou voľbou. V rámci štúdia alternatív som však natrafil na knihu „Začíname s LevelDB“. Pod jej vedením bol napísaný benchmark porovnávajúci rýchlosť práce s rôznymi databázami v reálnych cloudových scenároch. Výsledok prekonal naše najdivokejšie očakávania. V najpopulárnejších prípadoch – získanie kurzora na zoradený zoznam všetkých súborov a zoradený zoznam všetkých súborov pre daný adresár – sa LMDB ukázalo byť 10-krát rýchlejšie ako SQLite. Voľba sa stala zrejmou.

2. Polohovanie LMDB

LMDB je veľmi malá knižnica (iba 10 XNUMX riadkov), ktorá implementuje najnižšiu základnú vrstvu databáz – úložisko.

Vyššie uvedený diagram ukazuje, že porovnanie LMDB s SQLite, ktorý tiež implementuje vyššie úrovne, nie je vo všeobecnosti správnejšie ako SQLite s Core Data. Bolo by spravodlivejšie citovať rovnaké úložné motory ako rovnocenných konkurentov – BerkeleyDB, LevelDB, Sophia, RocksDB atď. Existujú dokonca vývojové trendy, v ktorých LMDB funguje ako komponent úložiska pre SQLite. Prvý takýto experiment sa uskutočnil v roku 2012 strávil od LMDB Howard Chu. výsledky sa ukázalo byť natoľko zaujímavé, že jeho iniciatívu prevzali nadšenci OSS a svoje pokračovanie našli v osobe LumoSQL. V januári 2020 bol autorom tohto projektu Den Shearer prezentované na LinuxConfAu.

LMDB sa používa hlavne ako motor pre aplikačné databázy. Knižnica vďačí za svoj vzhľad vývojárom OpenLDAP, ktorí boli veľmi nespokojní s BerkeleyDB ako základom ich projektu. Počnúc skromnou knižnicou btree, Howard Chu dokázal vytvoriť jednu z najpopulárnejších alternatív našej doby. Svoju skvelú správu venoval tomuto príbehu, ako aj vnútornej štruktúre LMDB. "Lightning Memory-maped Database". Dobrý príklad dobytia skladovacieho zariadenia zdieľal Leonid Yuryev (aka yleo) z Positive Technologies vo svojej správe na Highload 2015 „Motor LMDB je špeciálny šampión“. V ňom hovorí o LMDB v kontexte podobnej úlohy implementácie ReOpenLDAP a LevelDB už bol predmetom komparatívnej kritiky. V dôsledku implementácie mala spoločnosť Positive Technologies dokonca aktívne sa rozvíjajúcu vidlicu MDBX s veľmi chutnými funkciami, optimalizáciami a opravy chýb.

LMDB sa často používa ako úložisko. Napríklad prehliadač Mozilla Firefox vybral pre množstvo potrieb a od verzie 9 aj Xcode preferovaný jeho SQLite na ukladanie indexov.

Motor sa presadil aj vo svete mobilného vývoja. Stopy po jeho použití môžu byť nájsť v klientovi iOS pre Telegram. LinkedIn zašiel ešte ďalej a vybral LMDB ako predvolené úložisko pre svoj domáci rámec na ukladanie údajov do vyrovnávacej pamäte Rocket Data, o ktorom povedal vo svojom článku z roku 2016.

LMDB úspešne bojuje o miesto na slnku vo výklenku, ktorý nechal BerkeleyDB po tom, čo sa dostal pod kontrolu Oracle. Knižnica je obľúbená pre svoju rýchlosť a spoľahlivosť, dokonca aj v porovnaní s jej rovesníkmi. Ako viete, obedy zadarmo neexistujú a rád by som zdôraznil kompromis, ktorému budete musieť čeliť pri výbere medzi LMDB a SQLite. Vyššie uvedený diagram jasne ukazuje, ako sa dosiahne zvýšená rýchlosť. Po prvé, neplatíme za ďalšie vrstvy abstrakcie nad diskovým úložiskom. Je jasné, že dobrá architektúra sa bez nich stále nezaobíde a nevyhnutne sa objavia v kóde aplikácie, ale budú oveľa jemnejšie. Nebudú obsahovať funkcie, ktoré konkrétna aplikácia nevyžaduje, napríklad podporu pre dotazy v jazyku SQL. Po druhé, je možné optimálne implementovať mapovanie aplikačných operácií na požiadavky na diskové úložisko. Ak SQLite v mojej práci je založený na priemerných štatistických potrebách priemernej aplikácie, potom ako vývojár aplikácií dobre poznáte hlavné scenáre pracovného zaťaženia. Za produktívnejšie riešenie budete musieť zaplatiť zvýšenú cenu ako za vývoj prvotného riešenia, tak aj za jeho následnú podporu.

3. Tri piliere LMDB

Po pohľade na LMDB z vtáčej perspektívy nastal čas ísť hlbšie. Nasledujúce tri časti budú venované analýze hlavných pilierov, na ktorých spočíva architektúra úložiska:

1. Pamäťovo mapované súbory ako mechanizmus pre prácu s diskom a synchronizáciu interných dátových štruktúr.
2. B+-strom ako organizácia štruktúry uložených dát.
3. Copy-on-write ako prístup k poskytovaniu vlastností ACID transakcií a multiverzie.

3.1. Veľryba #1. Súbory mapované v pamäti

Pamäťovo mapované súbory sú natoľko dôležitým architektonickým prvkom, že sa objavujú aj v názve úložiska. Otázky cachovania a synchronizácie prístupu k uloženým informáciám sú úplne ponechané na operačný systém. LMDB v sebe neobsahuje žiadne vyrovnávacie pamäte. Toto je vedomé rozhodnutie autora, pretože čítanie údajov priamo z mapovaných súborov vám umožňuje znížiť množstvo problémov v implementácii motora. Nižšie je uvedený zďaleka nie úplný zoznam niektorých z nich.

1. Udržiavanie konzistencie dát v úložisku pri práci s ním z viacerých procesov sa stáva zodpovednosťou operačného systému. V ďalšej časti je táto mechanika diskutovaná podrobne a s obrázkami.
2. Absencia vyrovnávacích pamätí úplne eliminuje LMDB z réžie spojenej s dynamickými alokáciami. Čítanie údajov v praxi znamená nastavenie ukazovateľa na správnu adresu vo virtuálnej pamäti a nič viac. Znie to ako sci-fi, ale v zdrojovom kóde úložiska sú všetky volania calloc sústredené vo funkcii konfigurácie úložiska.
3. Absencia cache znamená aj absenciu zámkov spojených so synchronizáciou ich prístupu. Čítačky, ktorých môže byť súčasne ľubovoľný počet, na ceste k dátam nestretnú ani jeden mutex. Vďaka tomu má rýchlosť čítania ideálnu lineárnu škálovateľnosť na základe počtu CPU. V LMDB sa synchronizujú iba úpravy. Naraz môže byť len jeden spisovateľ.
4. Minimálne ukladanie do vyrovnávacej pamäte a logika synchronizácie eliminuje extrémne zložitý typ chýb spojených s prácou vo viacvláknovom prostredí. Na konferencii Usenix OSDI 2014 boli dve zaujímavé databázové štúdie: „Všetky súborové systémy nie sú stvorené rovnako: o zložitosti vytvárania aplikácií konzistentných s pádmi“ и „Mučiace databázy pre zábavu a zisk“. Z nich môžete získať informácie o bezprecedentnej spoľahlivosti LMDB a takmer bezchybnej implementácii vlastností transakcie ACID, ktorá je lepšia ako u SQLite.
5. Minimalizmus LMDB umožňuje, aby bola strojová reprezentácia jeho kódu úplne umiestnená v L1 cache procesora s následnými rýchlostnými charakteristikami.

Bohužiaľ, v systéme iOS so súbormi s pamäťovou mapou nie je všetko také bez mráčika, ako by sme chceli. Aby sme o nedostatkoch, ktoré s nimi súvisia, hovorili vedomejšie, je potrebné pamätať na všeobecné princípy implementácie tohto mechanizmu v operačných systémoch.

Všeobecné informácie o súboroch mapovaných v pamäti

S každou spustenou aplikáciou operačný systém spája entitu nazývanú proces. Každému procesu je pridelený súvislý rozsah adries, do ktorých umiestňuje všetko, čo potrebuje na fungovanie. Na najnižších adresách sú sekcie s kódom a pevne zakódovanými údajmi a zdrojmi. Ďalej prichádza rastúci blok dynamického adresného priestoru, ktorý je nám dobre známy pod názvom halda. Obsahuje adresy subjektov, ktoré sa objavujú počas prevádzky programu. V hornej časti je oblasť pamäte, ktorú používa zásobník aplikácií. Buď rastie, alebo sa zmenšuje, inými slovami, jeho veľkosť má tiež dynamický charakter. Aby sa stoh a halda navzájom netlačili a nerušili, sú umiestnené na rôznych koncoch adresného priestoru. Medzi dvoma dynamickými sekciami v hornej a dolnej časti je diera. Operačný systém používa adresy v tejto strednej časti na priradenie rôznych entít k procesu. Najmä môže priradiť určitú súvislú množinu adries k súboru na disku. Takýto súbor sa nazýva pamäťovo mapovaný.​

Adresný priestor pridelený procesu je obrovský. Počet adries je teoreticky obmedzený len veľkosťou ukazovateľa, ktorý je určený bitovou kapacitou systému. Ak by sa k nej namapovala fyzická pamäť 1:1, potom by úplne prvý proces zhltol celú pamäť RAM a o multitaskingu by nebolo ani reči.​

​Z našich skúseností však vieme, že moderné operačné systémy dokážu súčasne vykonávať toľko procesov, koľko chcete. Je to možné vďaka tomu, že procesom alokujú veľa pamäte len na papieri, no v skutočnosti do hlavnej fyzickej pamäte načítajú len tú časť, ktorá je tu a teraz žiadaná. Preto sa pamäť spojená s procesom nazýva virtuálna.

Operačný systém organizuje virtuálnu a fyzickú pamäť do stránok určitej veľkosti. Akonáhle je určitá stránka virtuálnej pamäte požadovaná, operačný systém ju načíta do fyzickej pamäte a porovnáva ju v špeciálnej tabuľke. Ak nie sú k dispozícii žiadne voľné sloty, potom sa na disk skopíruje jedna z predtým načítaných stránok a nahradí ju požadovaná stránka. Tento postup, ku ktorému sa čoskoro vrátime, sa nazýva swapovanie. Nasledujúci obrázok znázorňuje opísaný proces. Na nej bola načítaná stránka A s adresou 0 a umiestnená na hlavnú pamäťovú stránku s adresou 4. Táto skutočnosť sa prejavila v tabuľke korešpondencie v bunke číslo 0.​

Príbeh je úplne rovnaký so súbormi namapovanými do pamäte. Logicky sú údajne nepretržite a úplne umiestnené vo virtuálnom adresnom priestore. Do fyzickej pamäte však vstupujú stránku po stránke a len na požiadanie. Úprava takýchto stránok je synchronizovaná so súborom na disku. Týmto spôsobom môžete vykonať I/O súboru jednoduchou prácou s bajtami v pamäti – všetky zmeny automaticky prenesie jadro operačného systému do zdrojového súboru.​
​
Obrázok nižšie ukazuje, ako LMDB synchronizuje svoj stav pri práci s databázou z rôznych procesov. Mapovaním virtuálnej pamäte rôznych procesov do rovnakého súboru de facto zaväzujeme operačný systém, aby medzi sebou tranzitívne synchronizoval určité bloky ich adresných priestorov, kde sa LMDB pozerá.​
​

Dôležitou nuansou je, že LMDB štandardne upravuje dátový súbor prostredníctvom mechanizmu systémového volania zápisu a zobrazuje samotný súbor v režime len na čítanie. Tento prístup má dva dôležité dôsledky.

Prvý dôsledok je spoločný pre všetky operačné systémy. Jeho podstatou je pridanie ochrany pred neúmyselným poškodením databázy nesprávnym kódom. Ako viete, spustiteľné inštrukcie procesu majú voľný prístup k údajom odkiaľkoľvek v jeho adresnom priestore. Zároveň, ako sme si práve spomenuli, zobrazenie súboru v režime čítania a zápisu znamená, že akákoľvek inštrukcia ho môže tiež upraviť. Ak to urobí omylom a pokúsi sa napríklad skutočne prepísať prvok poľa na neexistujúcom indexe, môže náhodne zmeniť súbor namapovaný na túto adresu, čo povedie k poškodeniu databázy. Ak je súbor zobrazený v režime len na čítanie, potom pokus o zmenu príslušného adresného priestoru povedie k núdzovému ukončeniu programu signálom SIGSEGVa súbor zostane nedotknutý.

Druhý dôsledok je už špecifický pre iOS. Autor ani žiadne iné zdroje to výslovne neuvádzajú, no bez toho by LMDB nebolo vhodné na prevádzku na tomto mobilnom operačnom systéme. Ďalšia časť je venovaná jej úvahe.

Špecifiká súborov mapovaných v pamäti v systéme iOS

Na WWDC v roku 2018 bola úžasná správa „Hlboký ponor do pamäte iOS“. Hovorí nám, že v systéme iOS sú všetky stránky umiestnené vo fyzickej pamäti jedným z 3 typov: špinavé, komprimované a čisté.

Čistá pamäť je súbor stránok, ktoré možno bezbolestne uvoľniť z fyzickej pamäte. Údaje, ktoré obsahujú, je možné podľa potreby znova načítať z pôvodných zdrojov. Do tejto kategórie patria súbory mapované len na čítanie. iOS sa nebojí stránky namapované do súboru kedykoľvek uvoľniť z pamäte, keďže je zaručená ich synchronizácia so súborom na disku.
​
Všetky upravené stránky skončia v špinavej pamäti, bez ohľadu na to, kde boli pôvodne umiestnené. Týmto spôsobom budú klasifikované najmä súbory mapované v pamäti upravené zápisom do virtuálnej pamäte, ktorá je s nimi spojená. Otvorenie LMDB vlajkou MDB_WRITEMAP, po vykonaní zmien si to môžete osobne overiť.​

Akonáhle aplikácia začne zaberať príliš veľa fyzickej pamäte, iOS ju vystaví kompresii špinavých stránok. Celková pamäť obsadená špinavými a komprimovanými stránkami predstavuje takzvanú pamäťovú stopu aplikácie. Akonáhle dosiahne určitú prahovú hodnotu, systémový démon OOM zabijáka nasleduje proces a násilne ho ukončí. Toto je zvláštnosť iOS v porovnaní s desktopovými operačnými systémami. Na rozdiel od toho zníženie pamäťovej stopy výmenou stránok z fyzickej pamäte na disk nie je v systéme iOS k dispozícii.Dôvody možno len hádať. Možno je postup intenzívneho presúvania stránok na disk a späť pre mobilné zariadenia príliš náročný na energiu, alebo iOS šetrí zdroje na prepisovanie buniek na SSD diskoch, alebo možno dizajnéri neboli spokojní s celkovým výkonom systému, kde je všetko neustále vymieňané. Nech je to akokoľvek, faktom zostáva fakt.

Dobrou správou, už spomenutou skôr, je, že LMDB štandardne nepoužíva na aktualizáciu súborov mechanizmus mmap. To znamená, že zobrazené údaje sú systémom iOS klasifikované ako čistá pamäť a neprispievajú k zaťaženiu pamäte. Môžete to overiť pomocou nástroja Xcode s názvom VM Tracker. Snímka obrazovky nižšie zobrazuje stav virtuálnej pamäte iOS aplikácie Cloud počas prevádzky. Na začiatku v ňom boli inicializované 2 inštancie LMDB. Prvý mal povolené zobraziť svoj súbor na 1GiB virtuálnej pamäte, druhý - 512MiB. Napriek tomu, že obe úložiská zaberajú určité množstvo rezidentnej pamäte, žiadne z nich neprispieva k špinavej veľkosti.

A teraz je čas na zlé správy. Vďaka swapovaciemu mechanizmu v 64-bitových desktopových operačných systémoch môže každý proces zaberať toľko virtuálneho adresného priestoru, koľko umožňuje voľné miesto na pevnom disku pre jeho potenciálny swap. Nahradenie swapu kompresiou v iOS radikálne znižuje teoretické maximum. Teraz sa všetky živé procesy musia zmestiť do hlavnej (čítaj RAM) pamäte a všetky tie, ktoré sa nezmestia, musia byť nútené ukončiť. Toto je uvedené ako vo vyššie uvedenom správaa v oficiálna dokumentácia. V dôsledku toho iOS výrazne obmedzuje množstvo pamäte dostupnej na pridelenie prostredníctvom mmap. Tu tu Pomocou tohto systémového volania sa môžete pozrieť na empirické limity množstva pamäte, ktorá môže byť pridelená rôznym zariadeniam. Na najmodernejších modeloch smartfónov sa iOS stal veľkorysým o 2 gigabajty a na špičkových verziách iPadu o 4. V praxi sa samozrejme musíte zamerať na najnižšie podporované modely zariadení, kde je všetko veľmi smutné. Ešte horšie je, že pri pohľade na stav pamäte aplikácie vo VM Trackeri zistíte, že LMDB nie je ani zďaleka jediná, ktorá tvrdí, že má pamäťovú mapu. Dobré kusy zožerú systémové alokátory, zdrojové súbory, rámce obrázkov a iní menší predátori.

Na základe výsledkov experimentov v cloude sme dospeli k nasledujúcim kompromisným hodnotám pre pamäť pridelenú LMDB: 384 megabajtov pre 32-bitové zariadenia a 768 pre 64-bitové zariadenia. Po vyčerpaní tohto objemu sa všetky modifikačné operácie začnú s kódom MDB_MAP_FULL. Takéto chyby pozorujeme pri našom monitorovaní, ale sú dostatočne malé na to, aby sa v tomto štádiu mohli zanedbať.

Nezrejmým dôvodom nadmernej spotreby pamäte úložiskom môžu byť dlhotrvajúce transakcie. Aby sme pochopili, ako tieto dva javy súvisia, pomôže nám zváženie zostávajúcich dvoch pilierov LMDB.

3.2. Veľryba #2. B+-strom

Ak chcete emulovať tabuľky v hornej časti úložiska kľúč – hodnota, v jeho rozhraní API musia byť prítomné nasledujúce operácie:

1. Vloženie nového prvku.
2. Vyhľadajte prvok s daným kľúčom.
3. Odstránenie prvku.
4. Opakujte intervaly kľúčov v poradí, v akom sú zoradené.

Najjednoduchšia dátová štruktúra, ktorá môže jednoducho implementovať všetky štyri operácie, je binárny vyhľadávací strom. Každý z jeho uzlov predstavuje kľúč, ktorý rozdeľuje celú podmnožinu dcérskych kľúčov do dvoch podstromov. Ľavý obsahuje tie, ktoré sú menšie ako rodič, a pravý obsahuje tie, ktoré sú väčšie. Získanie objednanej sady kľúčov sa dosiahne jedným z klasických prechodov cez strom.​

Binárne stromy majú dve základné chyby, ktoré im bránia byť efektívnymi ako dátová štruktúra založená na disku. Po prvé, stupeň ich rovnováhy je nepredvídateľný. Existuje značné riziko získania stromov, v ktorých sa výška rôznych vetiev môže značne líšiť, čo výrazne zhoršuje algoritmickú zložitosť vyhľadávania v porovnaní s tým, čo sa očakáva. Po druhé, množstvo krížových väzieb medzi uzlami zbavuje binárne stromy miesta v pamäti.Blízke uzly (v zmysle spojenia medzi nimi) môžu byť umiestnené na úplne iných stránkach vo virtuálnej pamäti. V dôsledku toho môže aj jednoduchý prechod niekoľkých susedných uzlov v strome vyžadovať návštevu porovnateľného počtu stránok. To je problém aj vtedy, keď hovoríme o efektivite binárnych stromov ako dátovej štruktúry v pamäti, keďže neustále rotovanie stránok vo vyrovnávacej pamäti procesora nie je lacná záležitosť. Pokiaľ ide o časté získavanie stránok spojených s uzlami z disku, situácia sa úplne stáva poľutovaniahodné,

B-stromy, ktoré sú evolúciou binárnych stromov, riešia problémy uvedené v predchádzajúcom odseku. Po prvé, sú samovyvažujúce. Po druhé, každý z ich uzlov rozdeľuje množinu dcérskych kľúčov nie na 2, ale na M usporiadané podmnožiny a počet M môže byť dosť veľký, rádovo niekoľko stoviek alebo dokonca tisícov.

Týmto:

1. Každý uzol obsahuje veľké množstvo už objednaných kľúčov a stromy sú veľmi krátke.
2. Strom nadobúda vlastnosť lokality umiestnenia v pamäti, pretože kľúče, ktoré sú svojou hodnotou blízko, sa prirodzene nachádzajú vedľa seba na rovnakých alebo susedných uzloch.
3. Počet tranzitných uzlov pri zostupe zo stromu počas pátracej operácie je znížený.
4. Počet cieľových uzlov načítaných počas dotazov na rozsah je znížený, pretože každý z nich už obsahuje veľký počet usporiadaných kľúčov.

LMDB používa na ukladanie údajov variáciu B-stromu nazývanú B+ strom. Vyššie uvedený diagram zobrazuje tri typy uzlov, ktoré v ňom existujú:

1. V hornej časti je koreň. Zhmotňuje nič iné ako koncept databázy vo vnútri skladu. V rámci jednej inštancie LMDB môžete vytvoriť niekoľko databáz, ktoré zdieľajú namapovaný priestor virtuálnych adries. Každý z nich začína od svojho vlastného koreňa.
2. Na najnižšej úrovni sú listy. Iba oni obsahujú páry kľúč – hodnota uložené v databáze. Mimochodom, toto je zvláštnosť B+-stromov. Ak bežný B-strom ukladá časti hodnoty v uzloch všetkých úrovní, potom je variácia B+ iba v tom najnižšom. Po odstránení tejto skutočnosti budeme podtyp stromu použitý v LMDB ďalej nazývať jednoducho B-strom.
3. Medzi koreňom a listami je 0 alebo viac technických úrovní s navigačnými (vetvovými) uzlami. Ich úlohou je rozdeliť vytriedenú sadu kľúčov medzi listy.

Fyzicky sú uzly bloky pamäte vopred určenej dĺžky. Ich veľkosť je násobkom veľkosti pamäťových stránok v operačnom systéme, o ktorej sme hovorili vyššie. Štruktúra uzla je uvedená nižšie. Hlavička obsahuje meta informácie, z ktorých najzreteľnejší je napríklad kontrolný súčet. Ďalej prichádza informácia o posunoch, v ktorých sa bunky s údajmi nachádzajú. Dátami môžu byť buď kľúče, ak hovoríme o navigačných uzloch, alebo celé páry kľúč – hodnota v prípade listov.​ Viac o štruktúre stránok si môžete prečítať v práci "Hodnotenie vysokovýkonných obchodov s kľúčovou hodnotou".

Keď sme sa zaoberali vnútorným obsahom uzlov stránok, budeme ďalej zjednodušene reprezentovať B-strom LMDB v nasledujúcej forme.

Stránky s uzlami sú umiestnené postupne na disku. Vyššie očíslované strany sú umiestnené na konci súboru. Takzvaná meta stránka obsahuje informácie o posunoch, podľa ktorých možno nájsť korene všetkých stromov. Pri otváraní súboru LMDB skenuje súbor stránku po stránke od konca po začiatok a hľadá platnú metastránku a prostredníctvom nej nájde existujúce databázy.​

Teraz, keď máme predstavu o logickej a fyzickej štruktúre organizácie údajov, môžeme prejsť k tretiemu pilieru LMDB. S jeho pomocou sa všetky modifikácie úložiska vyskytujú transakčne a navzájom izolovane, čo dáva databáze ako celku vlastnosť multiverzie.

3.3. Veľryba #3. Kopírovanie pri zápise

Niektoré operácie B-stromu zahŕňajú vykonanie série zmien v jeho uzloch. Jedným príkladom je pridanie nového kľúča do uzla, ktorý už dosiahol svoju maximálnu kapacitu. V tomto prípade je potrebné po prvé rozdeliť uzol na dva a po druhé pridať odkaz na nový začínajúci podradený uzol v jeho rodičovi. Tento postup je potenciálne veľmi nebezpečný. Ak sa z nejakého dôvodu (zrútenie, výpadok prúdu atď.) vyskytne len časť zmien zo série, strom zostane v nekonzistentnom stave.

Jedným z tradičných riešení na zabezpečenie odolnosti databázy voči chybám je pridanie ďalšej dátovej štruktúry na disk vedľa B-stromu – protokolu transakcií, ktorý je známy aj ako protokol WAL (write-ahead log). Je to súbor, na konci ktorého je zamýšľaná operácia napísaná striktne pred úpravou samotného B-stromu. Ak sa teda počas vlastnej diagnostiky zistí poškodenie údajov, databáza konzultuje protokol, aby sa dala do poriadku.

LMDB zvolila inú metódu ako mechanizmus odolnosti voči chybám, nazývanú copy-on-write. Jej podstatou je, že namiesto aktualizácie údajov na existujúcej stránke ju najskôr celú skopíruje a vykoná všetky úpravy v kópii.​

Ďalej, aby boli aktualizované údaje dostupné, je potrebné zmeniť prepojenie na uzol, ktorý sa stal aktuálnym v nadradenom uzle. Keďže aj na to je potrebné ho upraviť, skopíruje sa tiež vopred. Proces pokračuje rekurzívne až po koreň. Posledná vec, ktorú treba zmeniť, sú údaje na metastránke.​

Ak počas procesu aktualizácie náhle dôjde k zlyhaniu procesu, potom sa buď nevytvorí nová metastránka, alebo sa úplne nezapíše na disk a jej kontrolný súčet bude nesprávny. V každom z týchto dvoch prípadov budú nové stránky nedostupné, ale staré nebudú ovplyvnené. To eliminuje potrebu, aby LMDB zapisovala vopred protokol, aby sa zachovala konzistencia údajov. De facto súčasne preberá svoju funkciu aj štruktúra uloženia dát na disku popísaná vyššie. Absencia explicitného protokolu transakcií je jednou z vlastností LMDB, ktorá poskytuje vysokú rýchlosť čítania dát.​

Výsledný dizajn, nazývaný iba append-only B-tree, prirodzene poskytuje izoláciu transakcií a vytváranie viacerých verzií. V LMDB je každá otvorená transakcia spojená s aktuálne relevantným koreňom stromu. Kým sa transakcia nedokončí, stránky stromu, ktoré sú s ňou spojené, sa nikdy nezmenia ani znovu nepoužijú pre nové verzie údajov. Môžete tak pracovať, ako dlho chcete, presne s tou množinou údajov, ktorá bola v danom čase relevantná. transakcia bola otvorená, aj keď sa úložisko v tomto čase naďalej aktívne aktualizuje. Toto je podstata multiverzie, vďaka čomu je LMDB ideálnym zdrojom údajov pre našich milovaných UICollectionView. Po otvorení transakcie nie je potrebné zvyšovať pamäťovú stopu aplikácie rýchlym čerpaním aktuálnych údajov do nejakej štruktúry v pamäti, zo strachu, že vám nezostane nič. Táto funkcia odlišuje LMDB od rovnakého SQLite, ktorý sa nemôže pochváliť takou úplnou izoláciou. Po otvorení dvoch transakcií v druhom z nich a vymazaní určitého záznamu v rámci jednej z nich už nebude možné získať rovnaký záznam v rámci druhej zostávajúcej.

Odvrátenou stranou mince je potenciálne výrazne vyššia spotreba virtuálnej pamäte. Snímka ukazuje, ako bude vyzerať štruktúra databázy, ak sa zmení súčasne s 3 otvorenými transakciami čítania pri pohľade na rôzne verzie databázy. Keďže LMDB nemôže opätovne použiť uzly dosiahnuteľné z koreňových adresárov spojených s aktuálnymi transakciami, obchod nemá inú možnosť, ako alokovať ďalší štvrtý koreňový adresár v pamäti a znova pod ním naklonovať upravené stránky.​

Tu by bolo užitočné pripomenúť si časť o súboroch mapovaných v pamäti. Zdá sa, že dodatočná spotreba virtuálnej pamäte by nás nemala veľmi znepokojovať, keďže neprispieva k pamäťovej stope aplikácie. Zároveň sa však poznamenalo, že iOS je pri prideľovaní veľmi skúpy a nemôžeme, ako na serveri alebo desktope, poskytnúť oblasť LMDB s veľkosťou 1 terabajt a na túto funkciu vôbec nemyslieť. Ak je to možné, mali by ste sa snažiť, aby životnosť transakcií bola čo najkratšia.

4. Návrh dátovej schémy nad rozhraním API kľúč – hodnota

Začnime našu analýzu API pohľadom na základné abstrakcie poskytované LMDB: prostredie a databázy, kľúče a hodnoty, transakcie a kurzory.

Poznámka k výpisom kódov

Všetky funkcie vo verejnom LMDB API vracajú výsledok svojej práce vo forme chybového kódu, no vo všetkých nasledujúcich výpisoch je jeho overenie z dôvodu stručnosti vynechané.​ V praxi sme na interakciu s úložiskom dokonca použili naše vlastné vidlička C++ obaly lmdbxx, v ktorom sa chyby zhmotňujú ako výnimky C++.

Ako najrýchlejší spôsob pripojenia LMDB k projektu pre iOS alebo macOS navrhujem môj CocoaPod POSLMDB.

4.1. Základné abstrakcie

Životné prostredie

Štruktúra MDB_env je úložisko vnútorného stavu LMDB. Skupina funkcií s predponou mdb_env umožňuje konfigurovať niektoré jeho vlastnosti. V najjednoduchšom prípade inicializácia motora vyzerá takto.

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

V aplikácii Mail.ru Cloud sme zmenili predvolené hodnoty iba dvoch parametrov.

Prvým je veľkosť priestoru virtuálnych adries, na ktorý je súbor úložiska mapovaný. Bohužiaľ, aj na tom istom zariadení sa konkrétna hodnota môže výrazne líšiť od behu k behu. Aby sa zohľadnila táto funkcia systému iOS, maximálny objem úložiska sa vyberá dynamicky. Počnúc od určitej hodnoty sa postupne znižuje na polovicu až po funkciu mdb_env_open nevráti výsledok odlišný od ENOMEM. Teoreticky existuje aj opačný spôsob - najskôr prideliť motoru minimum pamäte a potom, keď sa objavia chyby, MDB_MAP_FULL, zvýšte to. Je však oveľa tŕnistejšia. Dôvodom je postup na opätovné pridelenie pamäte (premapovanie) pomocou funkcie mdb_env_set_map_size zruší platnosť všetkých entít (kurzorov, transakcií, kľúčov a hodnôt), ktoré boli predtým prijaté z nástroja. Zohľadnenie tohto obratu udalostí v kóde povedie k jeho významnej komplikácii. Ak je však pre vás virtuálna pamäť veľmi dôležitá, môže to byť dôvod, prečo sa bližšie pozrieť na fork, ktorý zašiel ďaleko vpred MDBX, kde medzi avizované funkcie patrí „automatická úprava veľkosti databázy za chodu“.

Druhý parameter, ktorého predvolená hodnota nám nevyhovovala, reguluje mechaniku zaistenia bezpečnosti závitu. Bohužiaľ, minimálne iOS 10 má problémy s podporou lokálneho úložiska vlákien. Z tohto dôvodu je vo vyššie uvedenom príklade úložisko otvorené s príznakom MDB_NOTLS. Okrem toho to bolo aj nevyhnutné vidlička C++ obal lmdbxxvystrihnúť premenné s týmto atribútom a v ňom.

databázy

Databáza je samostatná inštancia B-stromu, o ktorej sme hovorili vyššie. K jeho otvoreniu dochádza v rámci transakcie, čo sa na prvý pohľad môže zdať trochu zvláštne.

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

Transakcia v LMDB je v skutočnosti úložnou entitou, nie špecifickou databázovou entitou. Tento koncept vám umožňuje vykonávať atómové operácie na entitách umiestnených v rôznych databázach. Teoreticky sa tým otvára možnosť modelovania tabuliek vo forme rôznych databáz, no ja som sa svojho času vybral inou cestou, podrobne popísanou nižšie.

Kľúče a hodnoty

Štruktúra MDB_val modeluje koncept kľúča aj hodnoty. Úložisko netuší o ich sémantike. Pre ňu je niečo iné len pole bajtov danej veľkosti. Maximálna veľkosť kľúča je 512 bajtov.

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

Pomocou porovnávača obchod triedi kľúče vo vzostupnom poradí. Ak ho nenahradíte vlastným, použije sa predvolený, ktorý ich zoradí bajt po byte v lexikografickom poradí.​

Transakcie

Štruktúra transakcie je podrobne opísaná v predchádzajúca kapitola, takže tu stručne zopakujem ich hlavné vlastnosti:

1. Podporuje všetky základné vlastnosti ACID: atomicita, konzistencia, izolácia a spoľahlivosť. Nemôžem si pomôcť, ale všimol som si, že existuje chyba týkajúca sa trvanlivosti v systémoch macOS a iOS, ktorá bola opravená v MDBX. Viac sa dočítate v ich README.
2. Prístup k multithreadingu je opísaný schémou „jeden zapisovateľ / viac čitateľov“. Spisovatelia sa navzájom blokujú, ale neblokujú čitateľov. Čitatelia neblokujú spisovateľov ani seba navzájom.
3. Podpora pre vnorené transakcie.
4. Podpora multiverzií.

Multiverzia v LMDB je taká dobrá, že ju chcem ukázať v praxi. Z nižšie uvedeného kódu môžete vidieť, že každá transakcia pracuje presne s verziou databázy, ktorá bola aktuálna v čase jej otvorenia, pričom je úplne izolovaná od všetkých následných zmien. Inicializácia úložiska a pridanie testovacieho záznamu do neho nepredstavuje nič zaujímavé, takže tieto rituály sú ponechané pod spojlerom.

Pridanie testovacieho záznamu

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

Odporúčam vám vyskúšať rovnaký trik s SQLite a uvidíte, čo sa stane.

Multiverzia prináša veľmi pekné výhody do života vývojára iOS. Pomocou tejto vlastnosti môžete jednoducho a prirodzene upraviť rýchlosť aktualizácie zdroja údajov pre obrazovkové formuláre na základe úvah o používateľskej skúsenosti. Vezmime si napríklad funkciu cloudovej aplikácie Mail.ru, ako je automatické načítanie obsahu zo systémovej galérie médií. S dobrým pripojením je klient schopný pridať na server niekoľko fotografií za sekundu. Ak aktualizujete po každom stiahnutí UICollectionView s mediálnym obsahom v užívateľskom cloude môžete pri tomto procese zabudnúť na 60 fps a plynulé rolovanie. Aby ste predišli častým aktualizáciám obrazovky, musíte nejakým spôsobom obmedziť rýchlosť, ktorou sa menia údaje v podklade UICollectionViewDataSource.

Ak databáza nepodporuje multiverziu a umožňuje vám pracovať len s aktuálnym aktuálnym stavom, tak na vytvorenie časovo stabilného snímku dát je potrebné skopírovať ju buď do nejakej dátovej štruktúry v pamäti, alebo do dočasnej tabuľky. Každý z týchto prístupov je veľmi drahý. V prípade in-memory storage získame náklady jednak v pamäti, spôsobené ukladaním skonštruovaných objektov, jednak v čase, spojeném s redundantnými ORM transformáciami. Pokiaľ ide o dočasný stôl, je to ešte drahšie potešenie, ktoré má zmysel iba v netriviálnych prípadoch.

Multiverzné riešenie LMDB rieši problém udržiavania stabilného zdroja dát veľmi elegantným spôsobom. Stačí otvoriť transakciu a voila - kým ju nedokončíme, je zaručené, že súbor údajov bude opravený. Logika rýchlosti aktualizácie je teraz úplne v rukách prezentačnej vrstvy bez režijných nákladov na značné zdroje.

Kurzory

Kurzory poskytujú mechanizmus na riadnu iteráciu párov kľúč-hodnota prostredníctvom prechodu B-stromom. Bez nich by nebolo možné efektívne modelovať tabuľky v databáze, na ktorú sa teraz obraciame.

4.2. Stolové modelovanie

Vlastnosť zoradenia kľúčov vám umožňuje zostaviť abstrakciu na vysokej úrovni, ako napríklad tabuľku nad základnými abstrakciami. Zoberme si tento proces pomocou príkladu hlavnej tabuľky cloudového klienta, ktorý ukladá informácie o všetkých súboroch a priečinkoch používateľa.

Schéma tabuľky

Jedným z bežných scenárov, pre ktorý by mala byť štruktúra tabuľky so stromom priečinkov prispôsobená, je výber všetkých prvkov nachádzajúcich sa v danom adresári. Dobrým modelom organizácie údajov pre efektívne dopyty tohto druhu je Zoznam susedov. Na jeho implementáciu nad úložiskom hodnôt kľúča je potrebné triediť kľúče súborov a priečinkov tak, aby boli zoskupené na základe ich členstva v nadradenom adresári. Okrem toho, aby sa obsah adresára zobrazil vo forme známej používateľovi Windows (najskôr priečinky, potom súbory, oboje zoradené podľa abecedy), je potrebné do kľúča zahrnúť zodpovedajúce dodatočné polia.

​Obrázok nižšie ukazuje, ako môže na základe danej úlohy vyzerať reprezentácia kľúčov vo forme bajtového poľa. Najprv sa umiestnia bajty s identifikátorom nadradeného adresára (červená), potom s typom (zelená) a na konci s názvom (modrá). požadovaným spôsobom. Postupné prechádzanie kľúčov s rovnakou červenou predponou nám dáva ich priradené hodnoty v poradí, v akom by sa mali zobrazovať v používateľskom rozhraní (vpravo), bez toho, aby bolo potrebné ďalšie dodatočné spracovanie.

Serializácia kľúčov a hodnôt

Vo svete bolo vynájdených veľa metód na serializáciu objektov. Keďže sme nemali inú požiadavku okrem rýchlosti, zvolili sme pre seba tú najrýchlejšiu možnú - výpis pamäte obsadenej inštanciou štruktúry jazyka C. Kľúč adresárového prvku teda možno modelovať s nasledujúcou štruktúrou NodeKey.

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

Zachrániť NodeKey v sklade potrebné v objekte MDB_val umiestnite ukazovateľ údajov na adresu začiatku štruktúry a vypočítajte ich veľkosť pomocou funkcie sizeof.

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

V prvej kapitole o kritériách výberu databáz som spomenul minimalizáciu dynamických alokácií v rámci operácií CRUD ako dôležitý faktor výberu. Kód funkcie serialize ukazuje, ako sa im možno v prípade LMDB úplne vyhnúť pri vkladaní nových záznamov do databázy. Prichádzajúce bajtové pole zo servera sa najskôr transformuje na zásobníkové štruktúry a potom sa triviálne uložia do úložiska. Vzhľadom na to, že vo vnútri LMDB tiež neexistujú žiadne dynamické alokácie, môžete podľa štandardov iOS získať fantastickú situáciu - na prácu s údajmi pozdĺž celej cesty zo siete na disk používajte iba zásobníkovú pamäť!

Objednávanie kľúčov s binárnym komparátorom

Vzťah poradia kľúčov je špecifikovaný špeciálnou funkciou nazývanou komparátor. Keďže motor nevie nič o sémantike bajtov, ktoré obsahujú, predvolený komparátor nemá inú možnosť, ako usporiadať kľúče v lexikografickom poradí a uchýliť sa k porovnávaniu bajtov po bajtoch. Použitie na organizáciu štruktúr je podobné holeniu sekerou. V jednoduchých prípadoch však považujem túto metódu za prijateľnú. Alternatíva je opísaná nižšie, ale tu si všimnem niekoľko hrablí roztrúsených pozdĺž tejto cesty.

Prvá vec, ktorú si treba zapamätať, je pamäťová reprezentácia primitívnych dátových typov. Na všetkých zariadeniach Apple sú teda celočíselné premenné uložené vo formáte Malý Endian. To znamená, že najmenej významný bajt bude vľavo a nebude možné triediť celé čísla pomocou porovnávania bajtov po bajtoch. Napríklad, ak sa to pokúsite urobiť so sadou čísel od 0 do 511, výsledkom bude nasledujúci výsledok.

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

Na vyriešenie tohto problému musia byť celé čísla uložené v kľúči vo formáte vhodnom pre bajtový komparátor. Funkcie z rodiny vám pomôžu uskutočniť potrebnú premenu hton* (najmä htons pre dvojbajtové čísla z príkladu).

Formát na reprezentáciu reťazcov v programovaní je, ako viete, jeden celok história. Ak sémantika reťazcov, ako aj kódovanie použité na ich reprezentáciu v pamäti, naznačujú, že na jeden znak môže byť viac ako jeden bajt, potom je lepšie okamžite opustiť myšlienku použitia predvoleného komparátora.

Druhá vec, ktorú treba mať na pamäti, je princípy zosúladenia kompilátor poľa štruktúry. Vďaka nim sa v pamäti medzi poľami môžu vytvárať bajty s hodnotami odpadu, čo, samozrejme, prerušuje triedenie bajtov. Ak chcete odstrániť odpadky, musíte buď deklarovať polia v presne definovanom poradí, pričom treba mať na pamäti pravidlá zarovnania, alebo použiť atribút v deklarácii štruktúry packed.

Objednávanie kľúčov s externým komparátorom

Kľúčová logika porovnávania môže byť pre binárny komparátor príliš zložitá. Jedným z mnohých dôvodov je prítomnosť technických odborov v konštrukciách. Ich výskyt ilustrujem na príklade kľúča pre nám už známy adresárový prvok.

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

Napriek svojej jednoduchosti v drvivej väčšine prípadov spotrebuje príliš veľa pamäte. Vyrovnávacia pamäť pre názov zaberá 256 bajtov, hoci v priemere názvy súborov a priečinkov zriedka presahujú 20-30 znakov.

Jednou zo štandardných techník na optimalizáciu veľkosti záznamu je „orezať“ ho na skutočnú veľkosť. Jeho podstatou je, že obsah všetkých polí s premenlivou dĺžkou je uložený vo vyrovnávacej pamäti na konci štruktúry a ich dĺžky sú uložené v samostatných premenných.​ Podľa tohto prístupu je kľúč NodeKey sa transformuje nasledovne.

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

Ďalej, pri serializácii nie je špecifikovaná veľkosť údajov sizeof celú štruktúru a veľkosť všetkých polí je pevná dĺžka plus veľkosť skutočne použitej časti vyrovnávacej pamäte.

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

V dôsledku refaktoringu sme dosiahli výraznú úsporu priestoru, ktorý zaberajú kľúče. Avšak kvôli technickej oblasti nameLength, predvolený binárny komparátor už nie je vhodný na porovnávanie kľúčov. Ak ho nenahradíme vlastným, tak dĺžka názvu bude pri zoraďovaní vyššou prioritou ako samotný názov.

LMDB umožňuje každej databáze mať vlastnú funkciu porovnávania kľúčov. To sa vykonáva pomocou funkcie mdb_set_compare presne pred otvorením. Z pochopiteľných dôvodov ho nie je možné počas životnosti databázy meniť. Komparátor dostane ako vstup dva kľúče v binárnom formáte a na výstupe vráti výsledok porovnania: menší ako (-1), väčší ako (1) alebo rovný (0). Pseudokód pre NodeKey vyzerá to tak.

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

Pokiaľ sú všetky kľúče v databáze rovnakého typu, bezpodmienečné pretypovanie ich bajtovej reprezentácie na typ štruktúry kľúča aplikácie je legálne. Je tu jedna nuansa, ale o nej sa bude diskutovať nižšie v podsekcii „Čítanie záznamov“.

Serializácia hodnôt

LMDB mimoriadne intenzívne pracuje s kľúčmi uložených záznamov. K ich vzájomnému porovnávaniu dochádza v rámci akejkoľvek aplikovanej operácie a od rýchlosti komparátora závisí výkon celého riešenia. V ideálnom svete by na porovnanie kľúčov mal stačiť predvolený binárny komparátor, ale ak by ste museli použiť svoj vlastný, potom by mal byť postup deserializácie kľúčov v ňom čo najrýchlejší.

Databázu zvlášť nezaujíma hodnotová časť záznamu (hodnota). K jej konverzii z bajtovej reprezentácie na objekt dochádza iba vtedy, keď to už vyžaduje kód aplikácie, napríklad na jej zobrazenie na obrazovke. Keďže sa to stáva pomerne zriedka, požiadavky na rýchlosť tohto postupu nie sú také kritické a pri jeho implementácii sa môžeme oveľa viac sústrediť na pohodlie. Napríklad na serializáciu metadát o súboroch, ktoré ešte neboli stiahnuté, používame NSKeyedArchiver.

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

Sú však chvíle, keď na výkone stále záleží. Napríklad pri ukladaní metainformácií o štruktúre súborov používateľského cloudu používame rovnaký výpis pamäte objektov. Vrcholom úlohy generovania ich serializovanej reprezentácie je skutočnosť, že prvky adresára sú modelované hierarchiou tried.​

Na implementáciu v jazyku C sú špecifické polia dedičov umiestnené v samostatných štruktúrach a ich spojenie so základnou je špecifikované prostredníctvom poľa typu union. Aktuálny obsah zväzku je špecifikovaný cez technický typ atribútu.

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

Pridávanie a aktualizácia záznamov

Serializovaný kľúč a hodnotu je možné pridať do obchodu. Ak to chcete urobiť, použite funkciu mdb_put.

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

Vo fáze konfigurácie možno úložisku povoliť alebo zakázať ukladanie viacerých záznamov s rovnakým kľúčom. Ak je duplikácia kľúčov zakázaná, potom pri vkladaní záznamu môžete určiť, či je aktualizácia existujúceho záznamu povolená alebo nie. Ak k rozstrapkaniu môže dôjsť iba v dôsledku chyby v kóde, môžete sa pred ním chrániť zadaním príznaku NOOVERWRITE,

Čítanie záznamov

Na čítanie záznamov v LMDB použite funkciu mdb_get. Ak je pár kľúč – hodnota reprezentovaný predtým uloženými štruktúrami, potom tento postup vyzerá takto.

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

Prezentovaný zoznam ukazuje, ako vám serializácia prostredníctvom výpisu štruktúry umožňuje zbaviť sa dynamických alokácií nielen pri zápise, ale aj pri čítaní údajov. Odvodené z funkcie mdb_get ukazovateľ sa presne pozerá na adresu virtuálnej pamäte, kde databáza ukladá bajtovú reprezentáciu objektu. V skutočnosti získame akýsi druh ORM, ktorý poskytuje veľmi vysokú rýchlosť čítania dát takmer zadarmo. Napriek všetkej kráse prístupu je potrebné pamätať na niekoľko funkcií, ktoré sú s ním spojené.

1. Pre transakciu určenú len na čítanie je zaručené, že ukazovateľ na štruktúru hodnôt zostane platný len do uzavretia transakcie. Ako bolo uvedené vyššie, stránky B-stromu, na ktorých sa nachádza objekt, vďaka princípu kopírovania pri zápise zostávajú nezmenené, pokiaľ na ne odkazuje aspoň jedna transakcia. Zároveň, hneď ako sa dokončí posledná transakcia s nimi spojená, môžu byť stránky znovu použité pre nové dáta. Ak je potrebné, aby objekty prežili transakciu, ktorá ich vygenerovala, musia sa skopírovať.
2. ​​Pre transakciu readwrite bude ukazovateľ na výslednú štruktúru hodnôt platný len do prvej procedúry úpravy (zápis alebo vymazanie údajov).
3. Hoci štruktúra NodeValue nie plnohodnotné, ale orezané (pozri podsekciu „Objednávanie kľúčov pomocou externého komparátora“), môžete k jeho poliam bezpečne pristupovať cez ukazovateľ. Hlavná vec nie je dereferencovať to!
4. Za žiadnych okolností by sa štruktúra nemala meniť prostredníctvom prijatého ukazovateľa. Všetky zmeny musia byť vykonané iba prostredníctvom metódy mdb_put. Avšak bez ohľadu na to, ako tvrdo to chcete urobiť, nebude to možné, pretože oblasť pamäte, kde sa nachádza táto štruktúra, je mapovaná v režime iba na čítanie.
5. Premapujte súbor do priestoru adries procesu, napríklad za účelom zvýšenia maximálnej veľkosti úložného priestoru pomocou funkcie mdb_env_set_map_size úplne ruší všetky transakcie a súvisiace entity vo všeobecnosti a poukazuje najmä na určité objekty.

Napokon ďalšia vlastnosť je taká zákerná, že odhalenie jej podstaty sa nezmestí len do ďalšieho odseku. V kapitole o B-strome som uviedol schému, ako sú jeho stránky usporiadané v pamäti. Z toho vyplýva, že adresa začiatku vyrovnávacej pamäte so serializovanými dátami môže byť absolútne ľubovoľná. Z tohto dôvodu sa ukazovateľ na ne dostal do štruktúry MDB_val a zredukovaný na ukazovateľ na štruktúru sa vo všeobecnom prípade ukáže ako nezarovnaný. Zároveň architektúry niektorých čipov (v prípade iOS ide o armv7) vyžadujú, aby adresa akýchkoľvek údajov bola násobkom veľkosti strojového slova alebo inými slovami bitovej veľkosti systému ( pre armv7 je to 32 bitov). Inými slovami, operácia ako *(int *foo)0x800002 na nich sa rovná úteku a vedie k poprave s verdiktom EXC_ARM_DA_ALIGN. Existujú dva spôsoby, ako sa vyhnúť takémuto smutnému osudu.

Prvá sa scvrkáva na predbežné kopírovanie údajov do zjavne zarovnanej štruktúry. Napríklad na vlastnom porovnávači sa to prejaví nasledovne.

int compare(MDB_val * const a, MDB_val * const b) {
    NodeKey aKey, bKey;
    memcpy(&aKey, a->mv_data, a->mv_size);
    memcpy(&bKey, b->mv_data, b->mv_size);
    return // ...
}

Alternatívnym spôsobom je vopred upozorniť kompilátor, že štruktúry kľúč – hodnota nemusia byť zarovnané podľa atribútov aligned(1). Na ARM môžete mať rovnaký efekt dosiahnuť a pomocou atribútu packed. Vzhľadom na to, že to tiež pomáha optimalizovať priestor zaberaný konštrukciou, zdá sa mi táto metóda vhodnejšia приводит k zvýšeniu nákladov na operácie prístupu k údajom.

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

Dotazy na rozsah

Na iteráciu skupiny záznamov poskytuje LMDB abstrakciu kurzora. Pozrime sa na to, ako s ním pracovať na príklade tabuľky s nám už známymi používateľskými cloudovými metadátami.

V rámci zobrazenia zoznamu súborov v adresári je potrebné nájsť všetky kľúče, ku ktorým sú priradené jeho podradené súbory a priečinky. V predchádzajúcich podkapitolách sme zoradili kľúče NodeKey tak, že sú primárne zoradené podľa ID nadradeného adresára. Technicky teda úloha načítania obsahu priečinka spočíva v umiestnení kurzora na hornú hranicu skupiny kľúčov s danou predponou a následnom iterovaní k dolnej hranici.

Hornú hranicu možno nájsť priamo sekvenčným vyhľadávaním. Za týmto účelom sa kurzor umiestni na začiatok celého zoznamu kľúčov v databáze a ďalej sa inkrementuje, kým sa pod ním neobjaví kľúč s identifikátorom nadradeného adresára. Tento prístup má 2 zrejmé nevýhody:

1. Zložitosť lineárneho vyhľadávania, aj keď, ako je známe, v stromoch vo všeobecnosti a najmä v B-strome sa môže vykonávať v logaritmickom čase.
2. Márne sa všetky strany predchádzajúce hľadanej stránke preberú zo súboru do hlavnej pamäte, čo je extrémne drahé.

Našťastie LMDB API poskytuje efektívny spôsob počiatočného umiestnenia kurzora. Aby ste to dosiahli, musíte vygenerovať kľúč, ktorého hodnota je zjavne menšia alebo rovná kľúču umiestnenému na hornej hranici intervalu. Napríklad vo vzťahu k zoznamu na obrázku vyššie môžeme urobiť kľúč, v ktorom je pole parentId sa bude rovnať 2 a všetky ostatné sú vyplnené nulami. Takýto čiastočne vyplnený kľúč sa dodáva na vstup funkcie mdb_cursor_get označujúci operáciu 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);

Ak sa nájde horná hranica skupiny kľúčov, potom cez ňu iterujeme, kým sa nestretneme, alebo kým sa kľúč nestretne s iným parentIdalebo sa kľúče neminú vôbec.​

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

Čo je pekné, je to, že ako súčasť iterácie pomocou mdb_cursor_get získame nielen kľúč, ale aj hodnotu. Ak na splnenie podmienok vzorkovania potrebujete okrem iného skontrolovať polia z hodnotovej časti záznamu, potom sú celkom dostupné bez ďalších gest.

4.3. Modelovanie vzťahov medzi tabuľkami

Teraz sa nám podarilo zvážiť všetky aspekty navrhovania a práce s databázou s jednou tabuľkou. Môžeme povedať, že tabuľka je množina zoradených záznamov pozostávajúca z rovnakého typu párov kľúč – hodnota. Ak zobrazíte kľúč ako obdĺžnik a pridruženú hodnotu ako rovnobežnosten, získate vizuálny diagram databázy.

​

V skutočnom živote je však zriedka možné vyjsť s tak malým množstvom krviprelievania. V databáze je často potrebné po prvé mať niekoľko tabuliek a po druhé v nich robiť výbery v poradí odlišnom od primárneho kľúča. Táto posledná časť je venovaná problematike ich tvorby a prepojenia.

Indexové tabuľky

Cloudová aplikácia má sekciu „Galéria“. Zobrazuje mediálny obsah z celého cloudu zoradený podľa dátumu. Ak chcete optimálne implementovať takýto výber, musíte vedľa hlavnej tabuľky vytvoriť ďalšiu s novým typom kľúčov. Budú obsahovať pole s dátumom vytvorenia súboru, ktoré bude fungovať ako primárne kritérium triedenia. Pretože nové kľúče odkazujú na rovnaké údaje ako kľúče v hlavnej tabuľke, nazývajú sa indexové kľúče. Na obrázku nižšie sú zvýraznené oranžovou farbou.

S cieľom oddeliť kľúče rôznych tabuliek od seba v rámci tej istej databázy bolo ku všetkým pridané ďalšie technické pole tableId. Tým, že to bude najvyššia priorita triedenia, dosiahneme zoskupenie kľúčov najskôr podľa tabuliek a v rámci tabuliek - podľa našich vlastných pravidiel.​

Indexový kľúč odkazuje na rovnaké údaje ako primárny kľúč. Priama implementácia tejto vlastnosti prostredníctvom priradenia kópie hodnotovej časti primárneho kľúča nie je optimálna z niekoľkých hľadísk:

1. Pokiaľ ide o zaberaný priestor, metadáta môžu byť dosť bohaté.
2. Z hľadiska výkonu, keďže pri aktualizácii metadát uzla ich budete musieť prepísať pomocou dvoch kľúčov.
3. Z pohľadu podpory kódu, ak zabudneme aktualizovať dáta pre niektorý z kľúčov, dostaneme nepolapiteľnú chybu nekonzistencie dát v úložisku.

Ďalej zvážime, ako tieto nedostatky odstrániť.

Usporiadanie vzťahov medzi tabuľkami

Vzor je vhodný na prepojenie indexovej tabuľky s hlavnou tabuľkou "kľúč ako hodnota". Ako už názov napovedá, hodnotová časť záznamu indexu je kópiou hodnoty primárneho kľúča. Tento prístup odstraňuje všetky vyššie uvedené nevýhody spojené s ukladaním kópie hodnotovej časti primárneho záznamu. Jedinou cenou je, že na získanie hodnoty pomocou indexového kľúča musíte do databázy zadať 2 dopyty namiesto jedného. Schematicky výsledná schéma databázy vyzerá takto.

Ďalším vzorom na organizovanie vzťahov medzi tabuľkami je "nadbytočný kľúč". Jeho podstatou je pridanie ďalších atribútov ku kľúču, ktoré sú potrebné nie na triedenie, ale na opätovné vytvorenie priradeného kľúča. V aplikácii Mail.ru Cloud však existujú skutočné príklady jeho použitia, aby ste sa vyhli hlbokému ponoru do kontext konkrétnych iOS frameworkov, uvediem fiktívny, no o to jasnejší príklad.​

Cloudoví mobilní klienti majú stránku, ktorá zobrazuje všetky súbory a priečinky, ktoré používateľ zdieľal s inými ľuďmi. Keďže takýchto súborov je pomerne málo a je s nimi spojených veľa rôznych typov špecifických informácií o publicite (kto má udelený prístup, s akými právami atď.), nebude racionálne zaťažovať hodnotovú časť zaznamenajte s ním do hlavnej tabuľky. Ak však chcete takéto súbory zobrazovať offline, musíte si to ešte niekam uložiť. Prirodzeným riešením je vytvorenie samostatného stola. Na obrázku nižšie má jeho kľúč predponu „P“ a zástupný symbol „propname“ možno nahradiť špecifickejšou hodnotou „public info“.​

Všetky jedinečné metaúdaje, pre ukladanie ktorých bola nová tabuľka vytvorená, sú umiestnené v hodnotovej časti záznamu. Zároveň nechcete duplikovať údaje o súboroch a priečinkoch, ktoré sú už uložené v hlavnej tabuľke. Namiesto toho sa do kľúča „P“ pridajú nadbytočné údaje vo forme polí „ID uzla“ a „časová pečiatka“. Vďaka nim môžete zostrojiť indexový kľúč, z ktorého získate primárny kľúč, z ktorého nakoniec získate metadáta uzla.

Záver

Výsledky implementácie LMDB hodnotíme pozitívne. Po nej sa počet zamrznutí aplikácií znížil o 30 %.

Výsledky vykonanej práce zarezonovali mimo tímu iOS. V súčasnosti sa jedna z hlavných sekcií „Súbory“ v aplikácii pre Android tiež prepne na používanie LMDB a ďalšie časti sú na ceste. Jazyk C, v ktorom je implementovaný ukladací priestor kľúč-hodnota, bol dobrým pomocníkom pri prvotnom vytvorení aplikačného rámca okolo neho naprieč platformami v C++. Na bezproblémové prepojenie výslednej knižnice C++ s kódom platformy v Objective-C a Kotlin bol použitý generátor kódu Djinni z Dropboxu, ale to je úplne iný príbeh.

Zdroj: hab.com