Na podzim 2019 se v týmu Mail.ru Cloud iOS odehrála dlouho očekávaná událost. Hlavní databáze pro trvalé ukládání stavu aplikací se pro mobilní svět stala poměrně exotickou Lightning Memory-Mapped Database (LMDB). Pod střihem zveme vaši pozornost k jeho podrobné recenzi ve čtyřech částech. Nejprve si promluvme o důvodech takové netriviální a obtížné volby. Pak přejděme k úvahám o třech velrybách v srdci architektury LMDB: soubory mapované v paměti, B + strom, přístup kopírování při zápisu pro implementaci transakčních a multiverzí. Na závěr jako dezert - praktická část. V něm se podíváme na to, jak navrhnout a implementovat základní schéma s několika tabulkami, včetně indexové, nad nízkoúrovňovým rozhraním klíč-hodnota API.​

Obsah

1. Motivace realizace
2. Polohování LMDB
3. Tři velryby LMDB
   3.1. Velryba #1. Soubory mapované v paměti
   3.2. Velryba #2. B+-strom
   3.3. Velryba #3. copy-on-write
4. Návrh datového schématu nad rozhraním API klíč–hodnota
   4.1. Základní abstrakce
   4.2. Stolové modelování
   4.3. Modelování vztahů mezi tabulkami

1. Motivace realizace

Jednou za rok, v roce 2015, jsme se postarali o metriku, jak často rozhraní naší aplikace zaostává. Neudělali jsme jen tohle. Stále více si stěžujeme na to, že někdy aplikace přestane reagovat na akce uživatele: nestisknou se tlačítka, neposouvají se seznamy atd. O mechanice měření řekl jsem na AvitoTech, takže zde uvádím pouze pořadí čísel.

Výsledky měření se pro nás staly studenou sprchou. Ukázalo se, že problémů způsobených zamrzáním je mnohem více než kterékoli jiné. Jestliže před uvědoměním si této skutečnosti byl hlavním technickým ukazatelem kvality bezporuchový, pak po zaměření posunutý na freeze free.

Po vybudování přístrojová deska zamrzne a strávit kvantitativní и kvalita analýzou jejich příčin se ukázal hlavní nepřítel - těžká obchodní logika vykonávající se v hlavním vláknu aplikace. Přirozenou reakcí na tuto ostudu byla spalující touha strčit ji do pracovních proudů. Pro systematické řešení tohoto problému jsme se uchýlili k vícevláknové architektuře založené na odlehčených hercích. Její úpravy jsem věnoval světu iOS dvě vlákna v kolektivním twitteru a článek o Habrém. V rámci aktuálního příběhu chci zdůraznit ty aspekty rozhodnutí, které ovlivnily výběr databáze.​

Actor model organizace systému předpokládá, že multithreading se stává jeho druhou podstatou. Modelové objekty v něm rády překračují hranice vláken. A nedělají to někdy a na některých místech, ale téměř neustále a všude.

Databáze je jednou ze základních komponent v prezentovaném diagramu. Jeho hlavním úkolem je implementovat makro vzor Sdílená databáze. Pokud se v podnikovém světě používá k organizaci synchronizace dat mezi službami, pak v případě architektury aktérů dat mezi vlákny. Potřebovali jsme tedy takovou databázi, se kterou práce ve vícevláknovém prostředí nečiní ani minimální potíže. Konkrétně to znamená, že objekty z něj odvozené musí být minimálně vláknově bezpečné a v ideálním případě vůbec neměnitelné. Jak víte, ten lze použít současně z několika vláken, aniž by se uchýlil k jakémukoli druhu zámků, což má příznivý vliv na výkon.

Druhým významným faktorem, který ovlivnil výběr databáze, bylo naše cloudové API. Bylo inspirováno přístupem git k synchronizaci. Jako on, na kterého jsme mířili offline první API, což vypadá pro cloudové klienty více než vhodně. Předpokládalo se, že pouze jednou vypumpují plný stav cloudu a poté dojde v naprosté většině případů k synchronizaci prostřednictvím postupných změn. Bohužel, tato možnost je zatím pouze v teoretické zóně a v praxi se klienti s patchi nenaučili. Má to řadu objektivních důvodů, které, abychom nezdržovali úvod, vynecháme ze závorky. Nyní jsou mnohem zajímavější poučné výsledky lekce o tom, co se stane, když API řeklo „A“ a jeho spotřebitel neřekl „B“.

Pokud si tedy představíte git, který při provádění příkazu Pull namísto aplikování záplat na místní snímek porovnává svůj plný stav s úplným serverovým stavem, pak budete mít poměrně přesnou představu o způsobu synchronizace. se vyskytuje v cloudových klientech. Je snadné uhodnout, že pro jeho implementaci je nutné v paměti alokovat dva DOM stromy s metainformacemi o všech serverových a lokálních souborech. Ukazuje se, že pokud uživatel uloží 500 tisíc souborů v cloudu, pak je k jeho synchronizaci nutné znovu vytvořit a zničit dva stromy s 1 milionem uzlů. Ale každý uzel je agregát obsahující graf podobjektů. V tomto světle se výsledky profilování očekávaly. Ukázalo se, že i bez zohlednění slučovacího algoritmu samotný postup vytvoření a následného zničení velkého množství malých objektů stojí pěkný cent. Situaci zhoršuje skutečnost, že základní synchronizační operace je zahrnuta ve velkém množství uživatelských skriptů. V důsledku toho fixujeme druhé důležité kritérium při výběru databáze - schopnost implementovat operace CRUD bez dynamické alokace objektů.

Další požadavky jsou tradičnější a jejich úplný seznam je následující.

1. Bezpečnost závitu.
2. Multiprocessing. Je to diktováno přáním používat stejnou instanci databáze k synchronizaci stavu nejen mezi vlákny, ale také mezi hlavní aplikací a rozšířeními iOS.
3. Schopnost reprezentovat uložené entity jako neměnné objekty.​
4. Nedostatek dynamických alokací v rámci operací CRUD.
5. Podpora transakcí pro základní vlastnosti ACIDKlíčová slova: atomicita, konzistence, izolace a spolehlivost.
6. Rychlost na nejoblíbenější případy.

S touto sadou požadavků byl a stále je SQLite dobrou volbou. V rámci studia alternativ jsem však narazil na knihu „Začínáme s LevelDB“. Pod jejím vedením byl napsán benchmark, který porovnává rychlost práce s různými databázemi v reálných cloudových scénářích. Výsledek předčil ta nejdivočejší očekávání. V nejoblíbenějších případech - získání kurzoru na seřazený seznam všech souborů a seřazený seznam všech souborů pro daný adresář - se LMDB ukázalo být 10krát rychlejší než SQLite. Volba byla jasná.

2. Polohování LMDB

LMDB je knihovna, velmi malá (pouze 10K řádků), která implementuje nejnižší základní vrstvu databází – úložiště.

Výše uvedený diagram ukazuje, že srovnání LMDB s SQLite, který implementuje ještě vyšší úrovně, obecně není správnější než SQLite s Core Data. Bylo by spravedlivější uvádět stejné úložné motory jako rovnocenné konkurenty – BerkeleyDB, LevelDB, Sophia, RocksDB atd. Dochází dokonce k vývoji, kdy LMDB funguje jako komponenta storage engine pro SQLite. První takový experiment v roce 2012 strávil autor LMDB Howard Chu. výsledky Ukázalo se, že je to tak zajímavé, že se jeho iniciativy chopili nadšenci OSS a našli její pokračování tváří v tvář LumoSQL. V lednu 2020 je autorem tohoto projektu Den Shearer prezentovány to na LinuxConfAu.

Hlavní použití LMDB je jako engine pro aplikační databáze. Knihovna vděčí za svůj vzhled vývojářům OpenLDAP, kteří byli silně nespokojeni s BerkeleyDB jako základem jejich projektu. Odstrkování od skromné ​​knihovny bstrom, Howard Chu dokázal vytvořit jednu z nejpopulárnějších alternativ naší doby. Tomuto příběhu věnoval svou velmi cool zprávu, stejně jako vnitřní struktuře LMDB. "Mapovaná databáze Lightning Memory". Leonid Yuriev (aka yleo) z Positive Technologies ve své přednášce na Highload 2015 „Motor LMDB je zvláštní šampion“. Hovoří v něm o LMDB v souvislosti s podobným úkolem implementace ReOpenLDAP a LevelDB už byl podroben komparativní kritice. V důsledku implementace získala Positive Technologies dokonce aktivně se vyvíjející vidlici MDBX s velmi chutnými funkcemi, optimalizacemi a oprava chyb.

LMDB se často používá také jako úložiště. Například prohlížeč Mozilla Firefox vybral to pro řadu potřeb a od verze 9 Xcode přednostně jeho SQLite pro ukládání indexů.

Engine se uchytil i ve světě mobilního vývoje. Stopy jeho použití mohou být najít v klientovi iOS pro Telegram. LinkedIn šel ještě o krok dále a zvolil LMDB jako výchozí úložiště pro svůj domácí rámec pro ukládání dat do mezipaměti, Rocket Data, o kterém řekl v článku z roku 2016.

LMDB úspěšně bojuje o místo na slunci ve výklenku, který nechal BerkeleyDB po přechodu pod kontrolu Oracle. Knihovna je oblíbená pro svou rychlost a spolehlivost i ve srovnání s vlastním druhem. Jak víte, neexistují žádné obědy zdarma a rád bych zdůraznil kompromis, kterému budete muset čelit při výběru mezi LMDB a SQLite. Výše uvedený diagram jasně ukazuje, jak je dosaženo zvýšené rychlosti. Za prvé, neplatíme za další vrstvy abstrakce nad diskovým úložištěm. Samozřejmě se bez nich v dobré architektuře stejně neobejdete a nevyhnutelně se objeví v kódu aplikace, ale budou mnohem tenčí. Nebudou mít funkce, které konkrétní aplikace nevyžaduje, například podporu dotazů v jazyce SQL. Za druhé, je možné optimálně implementovat mapování aplikačních operací na požadavky na diskové úložiště. Pokud SQLite v mé práci vychází z průměrných potřeb průměrné aplikace, pak jako vývojář aplikace dobře znáte hlavní scénáře zatížení. Za produktivnější řešení budete muset zaplatit zvýšenou cenu jak za vývoj počátečního řešení, tak za jeho následnou podporu.

3. Tři velryby LMDB

Po pohledu na LMDB z ptačí perspektivy je čas jít hlouběji. Následující tři části budou věnovány analýze hlavních velryb, na kterých spočívá architektura úložiště:

1. Paměťově mapované soubory jako mechanismus pro práci s diskem a synchronizaci vnitřních datových struktur.
2. B+-strom jako organizace uložené datové struktury.
3. Copy-on-write jako přístup k poskytování transakčních vlastností ACID a multiverze.

3.1. Velryba #1. Soubory mapované v paměti

Soubory mapované v paměti jsou natolik důležitým architektonickým prvkem, že se objevují i ​​v názvu úložiště. Problémy s ukládáním do mezipaměti a synchronizací přístupu k uloženým informacím jsou zcela na milosti operačního systému. LMDB v sobě neobsahuje žádné mezipaměti. Toto je vědomé rozhodnutí autora, protože čtení dat přímo z namapovaných souborů vám umožňuje mnoho problémů při implementaci enginu. Níže je zdaleka ne úplný seznam některých z nich.

1. Udržování konzistence dat v úložišti při práci s nimi z několika procesů se stává odpovědností operačního systému. V další části je tato mechanika rozebrána podrobně a s obrázky.
2. Absence mezipamětí zcela zbavuje LMDB režie související s dynamickými alokacemi. Čtení dat je v praxi nastavení ukazatele na správnou adresu ve virtuální paměti a nic víc. Zní to jako fantazie, ale ve zdroji úložiště jsou všechna volání calloc soustředěna ve funkci konfigurace úložiště.
3. Absence cache znamená také absenci zámků spojených se synchronizací pro přístup k nim. Čtečky, kterých může současně existovat libovolný počet, na své cestě k datům nenarazí na jediný mutex. Díky tomu má rychlost čtení ideální lineární škálovatelnost z hlediska počtu CPU. V LMDB jsou synchronizovány pouze úpravy. V jednu chvíli může být pouze jeden spisovatel.
4. Minimum logiky ukládání do mezipaměti a synchronizace chrání kód před extrémně složitým typem chyb spojených s prací ve vícevláknovém prostředí. Na konferenci Usenix OSDI 2014 proběhly dvě zajímavé databázové studie: „Všechny systémy souborů nejsou stvořeny stejně: O složitosti vytváření aplikací konzistentních s pády“ и Mučící databáze pro zábavu a zisk. Z nich můžete získat informace jak o bezprecedentní spolehlivosti LMDB, tak o téměř bezchybné implementaci ACID vlastností transakcí, které ji předčí ve stejném SQLite.
5. Minimalismus LMDB umožňuje strojovou reprezentaci jeho kódu kompletně umístit do L1 cache procesoru s výslednými rychlostními charakteristikami.

Bohužel v iOS nejsou soubory mapované v paměti tak růžové, jak bychom si přáli. Abychom o nevýhodách s nimi spojených mluvili vědoměji, je nutné připomenout obecné zásady implementace tohoto mechanismu do operačních systémů.

Obecné informace o souborech mapovaných v paměti

S každou spustitelnou aplikací operační systém spojuje entitu nazývanou proces. Každému procesu je přidělen souvislý rozsah adres, do kterých umístí vše, co potřebuje k práci. Nejnižší adresy obsahují sekce s kódem a pevně zakódovaná data a zdroje. Dále přichází vzestupně rostoucí blok dynamického adresního prostoru, který je nám dobře znám jako halda. Obsahuje adresy entit, které se objevují během činnosti programu. Nahoře je oblast paměti používaná zásobníkem aplikací. Buď roste, nebo se zmenšuje, jinými slovy, jeho velikost má také dynamický charakter. Aby se stoh a halda vzájemně netlačily a nepřekážely, jsou odděleny na různých koncích adresního prostoru.Mezi dvěma dynamickými sekcemi je nahoře a dole otvor. Adresy v této střední části používá operační systém k přidružení k procesu různých entit. Zejména může mapovat určitou souvislou sadu adres do souboru na disku. Takový soubor se nazývá soubor mapovaný v paměti.​

Adresový prostor přidělený procesu je obrovský. Teoreticky je počet adres omezen pouze velikostí ukazatele, která je dána bitovostí systému. Pokud by mu byla přiřazena fyzická paměť 1 v 1, pak by první proces spolykal celou RAM a o nějakém multitaskingu by nemohlo být ani řeči.​

​Ze zkušenosti však víme, že moderní operační systémy mohou spouštět tolik procesů, kolik chcete současně. Je to možné díky tomu, že procesy alokují hodně paměti pouze na papíře, ale ve skutečnosti do hlavní fyzické paměti načítají jen tu část, která je tady a teď žádaná. Paměť spojená s procesem se proto nazývá virtuální.

Operační systém organizuje virtuální a fyzickou paměť do stránek určité velikosti. Jakmile je určitá stránka virtuální paměti požadována, operační systém ji načte do fyzické paměti a zapíše mezi ně korespondenci do speciální tabulky. Pokud nejsou žádné volné sloty, zkopíruje se jedna z dříve načtených stránek na disk a požadovaná stránka se nahradí. Tento postup, ke kterému se za chvíli vrátíme, se nazývá swapování. Níže uvedený obrázek ilustruje popsaný proces. Na ní byla načtena stránka A s adresou 0 a umístěna na hlavní paměťovou stránku s adresou 4. Tato skutečnost se projevila v korespondenční tabulce v buňce číslo 0.​

Se soubory namapovanými v paměti je příběh úplně stejný. Logicky jsou údajně průběžně a celé umístěny ve virtuálním adresním prostoru. Do fyzické paměti se však dostávají stránku po stránce a pouze na vyžádání. Úprava takových stránek je synchronizována se souborem na disku. Můžete tedy provádět I/O souboru, jednoduše pracovat s bajty v paměti – všechny změny budou automaticky přeneseny jádrem operačního systému do původního souboru.​
​
Obrázek níže ukazuje, jak LMDB synchronizuje svůj stav při práci s databází z různých procesů. Mapováním virtuální paměti různých procesů na stejný soubor de facto zavazujeme operační systém k tranzitivní synchronizaci určitých bloků jejich adresních prostorů mezi sebou, což je místo, kde se LMDB dívá.​
​

Důležitou nuancí je, že LMDB ve výchozím nastavení upravuje datový soubor prostřednictvím mechanismu systémového volání zápisu a samotný soubor se zobrazuje v režimu pouze pro čtení. Tento přístup má dva důležité důsledky.

První důsledek je společný pro všechny operační systémy. Jeho podstatou je přidat ochranu proti nechtěnému poškození databáze nesprávným kódem. Jak víte, spustitelné instrukce procesu mají volný přístup k datům odkudkoli v jeho adresovém prostoru. Zároveň, jak jsme si právě vzpomněli, zobrazení souboru v režimu čtení-zápis znamená, že jakákoliv instrukce jej může navíc upravit. Pokud to udělá omylem a pokusí se například skutečně přepsat prvek pole na neexistujícím indexu, může tímto způsobem náhodně změnit soubor namapovaný na tuto adresu, což povede k poškození databáze. Pokud je soubor zobrazen v režimu pouze pro čtení, pak pokus o změnu adresního prostoru, který mu odpovídá, povede ke zhroucení programu se signálem SIGSEGVa soubor zůstane nedotčen.

Druhý důsledek je již specifický pro iOS. Autor ani žádné jiné zdroje to výslovně nezmiňují, ale bez toho by byl LMDB pro běh na tomto mobilním operačním systému nevhodný. Další část je věnována jeho úvahám.

Specifika souborů mapovaných v paměti v iOS

V roce 2018 byla na WWDC nádherná zpráva iOS Memory Deep Dive. Říká, že v iOS patří všechny stránky umístěné ve fyzické paměti do jednoho ze 3 typů: špinavé, komprimované a čisté.

Čistá paměť je kolekce stránek, které lze bezpečně vyměnit z fyzické paměti. Data, která obsahují, lze podle potřeby znovu načíst z jejich původních zdrojů. Do této kategorie spadají soubory mapované pouze pro čtení. iOS se nebojí stránky namapované do souboru kdykoli uvolnit z paměti, protože je zaručena jejich synchronizace se souborem na disku.
​
Všechny upravené stránky se dostanou do špinavé paměti, bez ohledu na to, kde jsou původně umístěny. Zejména soubory mapované v paměti upravené zápisem do virtuální paměti s nimi spojené budou také klasifikovány tímto způsobem. Otevření LMDB s vlajkou MDB_WRITEMAP, po provedení změn se můžete sami přesvědčit.​

Jakmile aplikace začne zabírat příliš mnoho fyzické paměti, iOS její špinavé stránky zkomprimuje. Kolekce paměti obsazené špinavými a komprimovanými stránkami je tzv. paměťová stopa aplikace. Když dosáhne určité prahové hodnoty, systémový démon OOM zabijáka následuje proces a násilně jej ukončí. To je zvláštnost iOS oproti desktopovým operačním systémům. Naproti tomu snížení paměťové náročnosti přehozením stránek z fyzické paměti na disk není v iOS poskytováno.O důvodech lze pouze hádat. Možná je postup intenzivního přesouvání stránek na disk a zpět pro mobilní zařízení příliš energeticky náročný, nebo iOS šetří prostředky na přepisování buněk na SSD disky, nebo možná nebyli konstruktéři spokojeni s celkovým výkonem systému, kde je vše neustále vyměňovány. Ať je to jak chce, faktem zůstává.

Dobrou zprávou, již zmíněnou dříve, je, že LMDB standardně nepoužívá k aktualizaci souborů mechanismus mmap. Z toho vyplývá, že vykreslená data jsou systémem iOS klasifikována jako čistá paměť a nepřispívají k paměťové stopě. To lze ověřit pomocí nástroje Xcode s názvem VM Tracker. Níže uvedený snímek obrazovky ukazuje stav virtuální paměti aplikace iOS Cloud během provozu. Na začátku v něm byly inicializovány 2 instance LMDB. Prvnímu bylo povoleno namapovat svůj soubor na 1GiB virtuální paměti, druhému - 512MiB. Navzdory skutečnosti, že obě úložiště zabírají určité množství rezidentní paměti, žádné z nich nepřispívá k špinavé velikosti.

Nyní je čas na špatné zprávy. Díky swapovacímu mechanismu v 64bitových desktopových operačních systémech může každý proces zabírat tolik virtuálního adresového prostoru, kolik volné místo na pevném disku umožňuje jeho potenciální swapování. Nahrazení swapu kompresí v iOS drasticky snižuje teoretické maximum. Nyní se všechny živé procesy musí vejít do hlavní (čtení RAM) paměti a všechny, které se nevejdou, podléhají nucenému ukončení. Je to zmíněno jako výše zprávaa v oficiální dokumentace. V důsledku toho iOS výrazně omezuje množství paměti dostupné pro alokaci prostřednictvím mmap. Tady zde můžete se podívat na empirická omezení množství paměti, která by mohla být přidělena na různá zařízení pomocí tohoto systémového volání. Na nejmodernějších modelech smartphonů se iOS stal velkorysým o 2 gigabajty a u špičkových verzí iPadu o 4. V praxi se samozřejmě musíte zaměřit na nejmladší podporované modely zařízení, kde je vše velmi smutné. Ještě horší je, když se podíváte na stav paměti aplikace ve VM Trackeru, zjistíte, že LMDB není zdaleka jediný, kdo si nárokuje paměť mapovanou na paměť. Dobré kusy sežerou systémové alokátory, zdrojové soubory, rámce obrázků a další menší predátoři.

V důsledku experimentů v cloudu jsme přišli s následujícími kompromisními hodnotami paměti přidělené LMDB: 384 megabajtů pro 32bitová zařízení a 768 pro 64bitová zařízení. Poté, co je tento objem vyčerpán, začnou se veškeré modifikační operace dokončovat s kódem MDB_MAP_FULL. Takové chyby pozorujeme při našem monitorování, ale jsou dostatečně malé, aby je v této fázi zanedbaly.

Nezřejmým důvodem nadměrné spotřeby paměti úložištěm mohou být transakce s dlouhou životností. Abychom pochopili, jak spolu tyto dva jevy souvisí, pomůže nám zvážit zbývající dvě velryby LMDB.

3.2. Velryba #2. B+-strom

Chcete-li emulovat tabulky nad úložištěm párů klíč–hodnota, musí být v jeho rozhraní API přítomny následující operace:

1. Vložení nového prvku.
2. Vyhledejte prvek s daným klíčem.
3. Odstranění prvku.
4. Iterujte klíčové intervaly v pořadí řazení.

Nejjednodušší datovou strukturou, která může snadno implementovat všechny čtyři operace, je binární vyhledávací strom. Každý z jeho uzlů je klíčem, který rozděluje celou podmnožinu podřízených klíčů do dvou podstromů. Vlevo jsou ty, které jsou menší než rodič, a vpravo ty, které jsou větší. Získání uspořádané sady klíčů je dosaženo jedním z klasických procházení stromem.​

Binární stromy mají dvě základní nevýhody, které jim brání být efektivní jako datová struktura disku. Za prvé, stupeň jejich rovnováhy je nepředvídatelný. Existuje značné riziko získání stromů, ve kterých se výška různých větví může velmi lišit, což výrazně zhoršuje algoritmickou složitost vyhledávání ve srovnání s tím, co se očekává. Za druhé, množství křížových vazeb mezi uzly zbavuje binární stromy místa v paměti.Blízké uzly (ve smyslu vazeb mezi nimi) mohou být umístěny na úplně jiných stránkách ve virtuální paměti. V důsledku toho může i jednoduché procházení několika sousedních uzlů ve stromu vyžadovat návštěvu srovnatelného počtu stránek. To je problém, i když mluvíme o efektivitě binárních stromů jako struktury dat v paměti, protože neustálé otáčení stránek v mezipaměti procesoru není levné. Pokud jde o časté vyvolávání stránek souvisejících s uzly z disku, věci jsou opravdu špatné. žalostný.

B-stromy, které jsou evolucí binárních stromů, řeší problémy uvedené v předchozím odstavci. Za prvé, jsou samovyvažující. Za druhé, každý z jejich uzlů rozděluje sadu podřízených klíčů nikoli na 2, ale na M uspořádané podmnožiny a počet M může být poměrně velký, v řádu několika stovek nebo dokonce tisíců.

Tím:

1. Každý uzel má velké množství již objednaných klíčů a stromy jsou velmi nízké.
2. Strom získává vlastnost lokality v paměti, protože klíče, které jsou svou hodnotou blízko, jsou přirozeně umístěny vedle sebe na jednom nebo sousedních uzlech.
3. Snižuje počet tranzitních uzlů při sestupu ze stromu během vyhledávací operace.
4. Snižuje počet cílových uzlů čtených pro dotazy na rozsah, protože každý z nich již obsahuje velký počet uspořádaných klíčů.

LMDB používá k ukládání dat variantu B-stromu nazvanou B+ strom. Výše uvedený diagram ukazuje tři typy uzlů, které obsahuje:

1. Nahoře je kořen. Nepředstavuje nic jiného než koncept databáze v úložišti. V rámci jedné instance LMDB můžete vytvořit více databází, které sdílejí mapovaný virtuální adresní prostor. Každý z nich začíná od svého vlastního kořene.
2. Na nejnižší úrovni jsou listy (list). Jsou to jen ony, které obsahují páry klíč-hodnota uložené v databázi. To je mimochodem zvláštnost B+-stromů. Pokud normální B-strom ukládá hodnotové části do uzlů všech úrovní, pak B+-variace je pouze na té nejnižší. Když jsme tuto skutečnost opravili, v následujícím budeme nazývat podtyp stromu použitý v LMDB jednoduše B-strom.
3. Mezi kořenem a listy je 0 nebo více technických úrovní s navigačními (větevními) uzly. Jejich úkolem je rozdělit seřazenou sadu klíčů mezi listy.

Fyzicky jsou uzly bloky paměti předem určené délky. Jejich velikost je násobkem velikosti paměťových stránek v operačním systému, o kterých jsme hovořili výše. Struktura uzlu je uvedena níže. Hlavička obsahuje metainformace, z nichž nejzřetelnější je například kontrolní součet. Dále následuje informace o offsetech, podél kterých jsou umístěny buňky s daty. Rolí dat mohou být buď klíče, mluvíme-li o navigačních uzlech, nebo celé páry klíč-hodnota v případě listů Více o struktuře stránek se dočtete v práci "Hodnocení vysoce výkonných obchodů klíč-hodnota".

Poté, co jsme se zabývali vnitřním obsahem uzlů stránky, budeme dále zjednodušeně reprezentovat LMDB B-strom v následující podobě.

Stránky s uzly jsou na disku sekvenčně uspořádány. Stránky s vyšším číslem jsou umístěny na konci souboru. Takzvaná meta stránka (metastránka) obsahuje informace o offsetech, pomocí kterých lze najít kořeny všech stromů. Když je soubor otevřen, LMDB skenuje soubor stránku po stránce od konce k začátku a hledá platnou metastránku a najde prostřednictvím ní existující databáze.​

Nyní, když máme představu o logické a fyzické struktuře organizace dat, můžeme přistoupit k uvažování o třetí velrybě LMDB. S jeho pomocí dochází ke všem úpravám úložiště transakčně a vzájemně izolovaně, což dává databázi jako celku také vlastnost multiverze.

3.3. Velryba #3. copy-on-write

Některé operace B-stromu zahrnují provedení celé řady změn jeho uzlů. Jedním příkladem je přidání nového klíče do uzlu, který již dosáhl své maximální kapacity. V tomto případě je nutné za prvé rozdělit uzel na dva a za druhé přidat odkaz na nový odštěpený podřízený uzel v jeho nadřazeném uzlu. Tento postup je potenciálně velmi nebezpečný. Pokud z nějakého důvodu (havárie, výpadek proudu atd.) dojde pouze k části změn ze série, pak strom zůstane v nekonzistentním stavu.

Jedním z tradičních řešení, jak zajistit odolnost databáze proti chybám, je přidat vedle B-stromu další diskovou datovou strukturu, transakční protokol, také známý jako zápis napřed (WAL). Jde o soubor, na jehož konci, přísně před úpravou samotného B-stromu, se zapíše zamýšlená operace. Pokud je tedy během vlastní diagnostiky zjištěno poškození dat, databáze konzultuje protokol, aby se vyčistila.

LMDB zvolila jako mechanismus odolnosti proti chybám jinou metodu, která se nazývá copy-on-write. Jeho podstatou je, že namísto aktualizace dat na existující stránce je nejprve zcela zkopíruje a provede všechny úpravy již v kopii.​

Dále, aby byla k dispozici aktualizovaná data, je nutné změnit vazbu na uzel, která se v nadřazeném uzlu ve vztahu k němu zaktualizovala. Vzhledem k tomu, že je k tomu také nutné upravit, je také předem zkopírován. Proces pokračuje rekurzivně až do kořene. Údaje na metastránce se mění jako poslední.​

Pokud proces během aktualizační procedury náhle selže, pak se buď nevytvoří nová meta stránka, nebo nebude až do konce zapsána na disk a její kontrolní součet bude nesprávný. V obou těchto případech budou nové stránky nedostupné a staré stránky nebudou ovlivněny. To eliminuje potřebu, aby LMDB zapisovala dopředu protokol, aby byla zachována konzistence dat. Svou funkci de facto současně přebírá výše popsaná struktura ukládání dat na disku. Absence explicitního transakčního protokolu je jednou z funkcí LMDB, která poskytuje vysokou rychlost čtení dat.​

Výsledný konstrukt, nazývaný pouze append-only B-tree, přirozeně poskytuje izolaci transakcí a multiverze. V LMDB má každá otevřená transakce přidružen aktuální kořen stromu. Dokud nebude transakce dokončena, stránky stromu, které jsou s ní spojeny, nebudou nikdy změněny ani znovu použity pro nové verze dat. Můžete tak pracovat, jak dlouho budete chtít, přesně s datovým souborem, který byl relevantní na době, kdy byla transakce otevřena, a to i v případě, že se úložiště v tomto okamžiku nadále aktivně aktualizuje. To je podstata multiverze, díky čemuž je LMDB ideálním zdrojem dat pro naše milované UICollectionView. Po otevření transakce nemusíte zvětšovat paměťovou stopu aplikace, narychlo pumpovat aktuální data do nějaké struktury v paměti a bát se, že vám nic nezbyde. Tato funkce odlišuje LMDB od stejného SQLite, který se nemůže pochlubit takovou úplnou izolací. Po otevření dvou transakcí v druhém z nich a smazání určitého záznamu v rámci jednoho z nich již nelze získat stejný záznam v druhém zbývajícím.

Odvrácenou stranou mince je potenciálně výrazně vyšší spotřeba virtuální paměti. Snímek ukazuje, jak bude vypadat struktura databáze, pokud bude upravena současně se 3 otevřenými transakcemi čtení při pohledu na různé verze databáze. Protože LMDB nemůže znovu použít uzly, které jsou dosažitelné z kořenů souvisejících se skutečnými transakcemi, úložiště nemá jinou možnost, než alokovat v paměti další čtvrtý kořen a znovu pod něj naklonovat upravené stránky.

Zde nebude zbytečné připomínat část o souborech mapovaných v paměti. Zdá se, že další spotřeba virtuální paměti by nás neměla příliš trápit, protože nepřispívá k paměťové stopě aplikace. Zároveň však bylo poznamenáno, že iOS je při přidělování velmi skoupý a nemůžeme poskytnout oblast LMDB o velikosti 1 terabajt na serveru nebo desktopu z ramene pána a vůbec o této funkci neuvažovat. Pokud je to možné, měli byste se snažit udržet životnost transakcí co nejkratší.

4. Návrh datového schématu nad rozhraním API klíč–hodnota

Začněme analyzovat API tím, že se podíváme na základní abstrakce poskytované LMDB: prostředí a databáze, klíče a hodnoty, transakce a kurzory.

Poznámka k výpisům kódů

Všechny funkce ve veřejném API LMDB vracejí výsledek své práce ve formě chybového kódu, ale ve všech následujících výpisech je jeho kontrola pro stručnost vynechána, v praxi jsme pro interakci s úložištěm použili vlastní kód. Vidlička C++ obaly lmdbxx, ve kterém se chyby zhmotňují jako výjimky C++.

Jako nejrychlejší způsob připojení LMDB k projektu iOS nebo macOS nabízím svůj CocoaPod POSLMDB.

4.1. Základní abstrakce

životní prostředí

Struktura MDB_env je úložištěm vnitřního stavu LMDB. Rodina prefixových funkcí mdb_env umožňuje konfigurovat některé jeho vlastnosti. V nejjednodušším případě inicializace motoru vypadá takto.

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

V aplikaci Mail.ru Cloud jsme změnili výchozí hodnoty pouze u dvou parametrů.

První je velikost virtuálního adresového prostoru, na který je soubor úložiště mapován. Bohužel i na stejném zařízení se konkrétní hodnota může výrazně lišit běh od běhu. Abychom zohlednili tuto funkci iOS, vybíráme maximální velikost úložiště dynamicky. Od určité hodnoty se postupně snižuje na polovinu až do funkce mdb_env_open nevrátí jiný výsledek než ENOMEM. Teoreticky existuje opačný způsob - nejprve přidělte enginu minimum paměti a poté, když se objeví chyby MDB_MAP_FULL, zvyšte to. Je však mnohem trnitější. Důvodem je postup pro přemapování paměti pomocí funkce mdb_env_set_map_size zneplatní všechny entity (kurzory, transakce, klíče a hodnoty) přijaté z enginu dříve. Účtování o takovém obratu událostí v kódu povede k jeho značné komplikaci. Pokud je vám přesto virtuální paměť velmi drahá, pak to může být důvod podívat se na fork, který šel daleko dopředu. MDBX, kde mezi deklarovanými funkcemi je „automatická úprava velikosti databáze za běhu“.

Druhý parametr, jehož výchozí hodnota nám nevyhovovala, reguluje mechaniku zajištění bezpečnosti závitu. Bohužel minimálně v iOS 10 jsou problémy s podporou lokálního úložiště vláken. Z tohoto důvodu je ve výše uvedeném příkladu úložiště otevřeno s příznakem MDB_NOTLS. Navíc to také vyžadovalo Vidlička C++ obal lmdbxxvyjmout proměnné pomocí a v tomto atributu.

Databáze

Databáze je samostatnou instancí B-stromu, o kterém jsme hovořili výše. K jeho otevření dochází uvnitř transakce, což se na první pohled může zdát trochu zvláštní.

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

Transakce v LMDB je ve skutečnosti entita úložiště, nikoli konkrétní databáze. Tento koncept umožňuje provádět atomické operace na entitách umístěných v různých databázích. Teoreticky to otevírá možnost modelování tabulek ve formě různých databází, ale kdysi jsem šel jinou cestou, podrobně popsanou níže.

Klíče a hodnoty

Struktura MDB_val modeluje koncept klíče i hodnoty. O jejich sémantice nemá úložiště ani ponětí. Pro ni je něco, co je jiné, jen polem bajtů dané velikosti. Maximální velikost klíče je 512 bajtů.

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

Obchod používá komparátor k řazení klíčů ve vzestupném pořadí. Pokud jej nenahradíte vlastním, použije se výchozí, který je seřadí bajt po bajtu v lexikografickém pořadí.​

Transakce

Transakční zařízení je podrobně popsáno v předchozí kapitola, takže zde zopakuji jejich hlavní vlastnosti v krátkém řádku:

1. Podpora všech základních vlastností ACIDKlíčová slova: atomicita, konzistence, izolace a spolehlivost. Nemohu si pomoci, ale z hlediska odolnosti na macOS a iOS je v MDBX opravena chyba. Více si můžete přečíst v jejich README.
2. Přístup k multithreadingu je popsán schématem „jeden zapisovatel / více čtenářů“. Spisovatelé se navzájem blokují, ale neblokují čtenáře. Čtenáři neblokují spisovatele ani sebe navzájem.
3. Podpora pro vnořené transakce.
4. Podpora multiverzí.

Multiverze v LMDB je tak dobrá, že ji chci předvést v akci. Níže uvedený kód ukazuje, že každá transakce pracuje přesně s verzí databáze, která byla relevantní v době jejího otevření, a je zcela izolována od všech následných změn. Inicializace úložiště a přidání testovacího záznamu do něj není zajímavé, takže tyto rituály jsou ponechány pod spoilerem.

Přidání testovacího 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);

Volitelně doporučuji zkusit stejný trik s SQLite a uvidíte, co se stane.

Multiverze přináší do života iOS vývojáře velmi pěkné výhody. Pomocí této vlastnosti můžete snadno a přirozeně upravit rychlost aktualizace zdroje dat pro obrazovkové formuláře na základě zvážení uživatelské zkušenosti. Vezměme si například takovou funkci aplikace Mail.ru Cloud, jako je automatické načítání obsahu ze systémové galerie médií. Při dobrém připojení je klient schopen přidat na server několik fotografií za sekundu. Pokud aktualizujete po každém stažení UICollectionView s mediálním obsahem v uživatelském cloudu můžete během tohoto procesu zapomenout na 60 fps a plynulé rolování. Abyste zabránili častým aktualizacím obrazovky, musíte nějak omezit rychlost změny dat v základu UICollectionViewDataSource.

Pokud databáze nepodporuje multiverze a umožňuje pracovat pouze s aktuálním aktuálním stavem, pak pro vytvoření časově stabilního snímku dat je potřeba jej zkopírovat buď do nějaké datové struktury v paměti, nebo do dočasné tabulky. Každý z těchto přístupů je velmi drahý. V případě in-memory storage získáme jak paměťové náklady způsobené ukládáním zkonstruovaných objektů, tak časové náklady spojené s redundantními ORM transformacemi. Pokud jde o dočasný stůl, jedná se o ještě dražší potěšení, které má smysl pouze v netriviálních případech.

Multiverzování LMDB řeší problém udržování stabilního zdroje dat velmi elegantním způsobem. Stačí jen otevřít transakci a voilá - dokud ji nedokončíme, je zaručeno, že soubor dat bude opraven. Logika jeho rychlosti aktualizace je nyní zcela v rukou prezentační vrstvy, bez režie významných zdrojů.

Kurzory

Kurzory poskytují mechanismus pro řádnou iteraci párů klíč-hodnota procházením B-stromu. Bez nich by nebylo možné efektivně modelovat tabulky v databázi, ke které se nyní podíváme.

4.2. Stolové modelování

Vlastnost řazení klíčů vám umožňuje vytvořit abstrakci nejvyšší úrovně, jako je tabulka nad základními abstrakcemi. Zvažme tento proces na příkladu hlavní tabulky cloudového klienta, ve kterém jsou uloženy informace o všech souborech a složkách uživatele.

Schéma tabulky

Jedním z běžných scénářů, pro které by měla být struktura tabulky se stromem složek zpřesněna, je výběr všech prvků umístěných uvnitř daného adresáře Dobrým modelem organizace dat pro efektivní dotazy tohoto druhu je Seznam sousedů. Pro jeho implementaci nad úložištěm párů klíč-hodnota je nutné seřadit klíče souborů a složek tak, aby byly seskupeny podle příslušnosti k nadřazenému adresáři. Kromě toho, aby se obsah adresáře zobrazil ve formě známé uživateli Windows (nejdříve složky, pak soubory, obojí je řazeno abecedně), je nutné do klíče zahrnout odpovídající doplňková pole.

​Obrázek níže ukazuje, jak může na základě úlohy vypadat reprezentace klíčů jako pole bajtů. Nejprve se umístí bajty s identifikátorem nadřazeného adresáře (červená), pak s typem (zelená) a již na konci s názvem (modrá). požadovaným způsobem. Postupné procházení klíčů se stejnou červenou předponou nám dává hodnoty s nimi spojené v pořadí, v jakém by se měly zobrazovat v uživatelském rozhraní (vpravo), aniž by bylo potřeba jakékoli další následné zpracování.

Serializace klíčů a hodnot

Existuje mnoho metod pro serializaci objektů po celém světě. Protože jsme neměli žádný jiný požadavek než rychlost, zvolili jsme pro sebe ten nejrychlejší možný - výpis paměti obsazený instancí struktury jazyka C. Klíč adresářového prvku lze tedy modelovat pomocí následující struktury NodeKey.

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

Zachránit NodeKey ve skladu potřeba v objektu MDB_val umístěte ukazatel na data na adresu začátku struktury a pomocí funkce vypočítejte jejich velikost sizeof.

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

V první kapitole o kritériích výběru databáze jsem zmínil minimalizaci dynamických alokací v rámci operací CRUD jako důležitý faktor výběru. Kód funkce serialize ukazuje, jak se jim lze v případě LMDB zcela vyhnout při vkládání nových záznamů do databáze. Příchozí pole bajtů ze serveru je nejprve transformováno do zásobníkových struktur a poté jsou triviálně uloženy do úložiště. Vzhledem k tomu, že uvnitř LMDB také neexistují žádné dynamické alokace, můžete podle standardů iOS získat fantastickou situaci - používejte pouze zásobníkovou paměť pro práci s daty ze sítě na disk!

Objednací klíče s binárním komparátorem

Relace pořadí klíčů je dána speciální funkcí zvanou komparátor. Protože engine neví nic o sémantice bajtů, které obsahují, výchozí komparátor nemá jinou možnost, než uspořádat klíče v lexikografickém pořadí a uchýlit se k jejich porovnání bajt po bajtu. Použití k uspořádání struktur je podobné holení řezbářskou sekerou. V jednoduchých případech však tento způsob považuji za přijatelný. Alternativa je popsána níže, ale zde si všimnu několika hrábí rozházených po cestě.

První věc, kterou je třeba mít na paměti, je paměťová reprezentace primitivních datových typů. Na všech zařízeních Apple jsou tedy celočíselné proměnné uloženy ve formátu Malý Endian. To znamená, že nejméně významný bajt bude vlevo a nebudete moci třídit celá čísla pomocí jejich porovnání bajtů po bajtech. Například pokus o to se sadou čísel od 0 do 511 bude mít za následek následující výsledek.

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

K vyřešení tohoto problému musí být celá čísla uložena v klíči ve formátu vhodném pro bajtový komparátor. Funkce z rodiny pomohou provést potřebnou transformaci. hton* (zejména htons pro dvoubajtová čísla z příkladu).

Formát pro reprezentaci řetězců v programování je, jak víte, jeden celek historie. Pokud sémantika řetězců, stejně jako kódování použité k jejich reprezentaci v paměti, naznačuje, že může existovat více než jeden bajt na znak, pak je lepší okamžitě opustit myšlenku použití výchozího komparátoru.

Druhá věc, kterou je třeba mít na paměti, je principy zarovnání kompilátor pole struct. Kvůli nim mohou být v paměti mezi poli vytvořeny bajty s nesmyslnými hodnotami, což samozřejmě narušuje třídění bajtů. Chcete-li odstranit odpadky, musíte buď deklarovat pole v přesně definovaném pořadí, přičemž musíte mít na paměti pravidla zarovnání, nebo použít atribut v deklaraci struktury packed.

Objednávání klíčů externím komparátorem

Klíčová srovnávací logika se může ukázat jako příliš složitá pro binární komparátor. Jedním z mnoha důvodů je přítomnost technických oborů uvnitř konstrukcí. Jejich výskyt ilustruji na příkladu nám již známého klíče pro adresářový prvek.

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

Přes svou jednoduchost v drtivé většině případů spotřebovává příliš mnoho paměti. Vyrovnávací paměť titulků je 256 bajtů, ačkoli v průměru názvy souborů a složek zřídka přesahují 20-30 znaků.

Jednou ze standardních technik pro optimalizaci velikosti záznamu je jeho oříznutí, aby odpovídalo jeho skutečné velikosti. Jeho podstatou je, že obsah všech polí s proměnnou délkou je uložen ve vyrovnávací paměti na konci struktury a jejich délky jsou uloženy v samostatných proměnných.V souladu s tímto přístupem je klíč NodeKey se transformuje následujícím způsobem.

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

Dále během serializace není specifikována jako velikost dat sizeof celá struktura a velikost všech polí je pevná délka plus velikost skutečně použité části vyrovnávací paměti.

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

V důsledku refaktoringu jsme získali výraznou úsporu místa, které zabírají klávesy. Ovšem vzhledem k technické oblasti nameLength, výchozí binární komparátor již není vhodný pro porovnání klíčů. Pokud jej nenahradíme vlastním, pak bude délka názvu při řazení prioritnějším faktorem než samotný název.

LMDB umožňuje každé databázi mít vlastní funkci porovnání klíčů. To se provádí pomocí funkce mdb_set_compare přísně před otevřením. Z pochopitelných důvodů nelze databázi měnit po celou dobu její životnosti. Na vstupu komparátor obdrží dva klíče v binárním formátu a na výstupu vrátí výsledek porovnání: menší než (-1), větší než (1) nebo rovný (0). Pseudokód pro NodeKey vypadá 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 // ...
}​

Dokud jsou všechny klíče v databázi stejného typu, je legální bezpodmínečně přetypovat jejich bytovou reprezentaci na typ aplikační struktury klíče. Je zde jedna nuance, ale ta bude probrána o něco níže v podsekci „Reading Records“.

Serializace hodnot

S klíči uložených záznamů pracuje LMDB mimořádně intenzivně. Vzájemně se porovnávají v rámci libovolné operace aplikace a na rychlosti komparátoru závisí výkon celého řešení. V ideálním světě by měl pro porovnání klíčů stačit výchozí binární komparátor, ale pokud byste opravdu museli použít svůj vlastní, pak by postup deserializace klíčů v něm měl být co nejrychlejší.

Databáze se nijak zvlášť nezajímá o Hodnotovou část záznamu (hodnotu). K jeho převodu z bajtové reprezentace na objekt dochází pouze tehdy, když je to již vyžadováno kódem aplikace, například k jeho zobrazení na obrazovce. Vzhledem k tomu, že k tomu dochází poměrně zřídka, nejsou požadavky na rychlost tohoto postupu tak kritické a při jeho implementaci se můžeme mnohem více soustředit na pohodlí. Například pro serializaci metadat o souborech, které ještě nebyly staženy, používáme NSKeyedArchiver.

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

Jsou však chvíle, kdy na výkonu záleží. Například při ukládání metainformací o struktuře souborů uživatelského cloudu používáme stejný výpis paměti objektů. Vrcholem úkolu generování jejich serializované reprezentace je skutečnost, že prvky adresáře jsou modelovány hierarchií tříd.​

Pro jeho implementaci v jazyce C jsou specifická pole dědiců vyjmuta do samostatných struktur a jejich spojení se základním je specifikováno prostřednictvím pole typu union. Vlastní obsah svazku je specifikován pomocí atributu typ technický.

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

Přidávání a aktualizace záznamů

Serializovaný klíč a hodnotu lze přidat do úložiště. K tomu slouží funkce mdb_put.

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

Ve fázi konfigurace lze úložišti povolit nebo zakázat ukládání více záznamů se stejným klíčem.​​ Pokud je duplikace klíčů zakázána, můžete při vkládání záznamu určit, zda je aktualizace již existujícího záznamu povolena či nikoli. Pokud k roztřepení může dojít pouze v důsledku chyby v kódu, můžete se proti němu pojistit zadáním příznaku NOOVERWRITE.

Čtení záznamů

Funkce pro čtení záznamů v LMDB je mdb_get. Pokud je pár klíč–hodnota reprezentován dříve uloženými strukturami, pak tento postup vypadá 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ý výpis ukazuje, jak vám serializace prostřednictvím výpisu struktur umožňuje zbavit se dynamických alokací nejen při zápisu, ale i při čtení dat. Odvozeno z funkce mdb_get ukazatel se dívá přesně na adresu virtuální paměti, kde databáze ukládá bajtovou reprezentaci objektu. Ve skutečnosti získáme jakési ORM, téměř zdarma poskytující velmi vysokou rychlost čtení dat. Se vší krásou tohoto přístupu je nutné pamatovat na několik funkcí s ním spojených.

1. U transakce pouze pro čtení je zaručeno, že ukazatel na strukturu hodnot zůstane platný pouze do uzavření transakce. Jak bylo uvedeno dříve, stránky B-stromu, na kterých se objekt nachází, zůstávají díky principu kopírování při zápisu nezměněny, pokud se na ně odkazuje alespoň jedna transakce. Zároveň, jakmile je dokončena poslední transakce s nimi spojená, lze stránky znovu použít pro nová data. Pokud je nutné, aby objekty přežily transakci, která je vytvořila, musí být přesto zkopírovány.
2. U transakce čtení a zápisu bude ukazatel na výslednou hodnotu struktury platný pouze do první procedury úpravy (zápis nebo mazání dat).
3. I když struktura NodeValue ne plnohodnotné, ale ořezané (viz podsekce "Objednávání klíčů externím komparátorem"), přes ukazatel se snadno dostanete do jeho polí. Hlavní je to nedereferencovat!
4. V žádném případě nemůžete upravovat strukturu prostřednictvím přijatého ukazatele. Všechny změny musí být provedeny pouze prostřednictvím metody mdb_put. Se vší touhou to však nebude fungovat, protože paměťová oblast, kde se tato struktura nachází, je mapována v režimu pouze pro čtení.
5. Přemapujte soubor na adresový prostor procesu, abyste například pomocí této funkce zvýšili maximální velikost úložiště mdb_env_set_map_size zcela zneplatní všechny transakce a související entity obecně a zejména ukazatele na čtení objektů.

Konečně ještě jedna vlastnost je tak záludná, že odhalení její podstaty se nevejde jen do jednoho dalšího bodu. V kapitole o B-stromu jsem uvedl schéma organizace jeho stránek v paměti. Z něj vyplývá, že adresa začátku bufferu se serializovanými daty může být naprosto libovolná. Z tohoto důvodu je ukazatel na ně získaný ve struktuře MDB_val a přetypování na ukazatel na strukturu je obecně nezarovnané. Architektury některých čipů (v případě iOS se jedná o armv7) přitom vyžadují, aby adresa jakýchkoli dat byla násobkem velikosti strojového slova, nebo jinými slovy bitovosti systému. (pro armv7 je to 32 bitů). Jinými slovy, operace jako *(int *foo)0x800002 na nich se rovná útěku a vede k popravě s rozsudkem EXC_ARM_DA_ALIGN. Existují dva způsoby, jak se takovému smutnému osudu vyhnout.

Prvním z nich je předem zkopírovat data do známé zarovnané struktury. Například na vlastním komparátoru se to projeví následovně.

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

Alternativním způsobem je upozornit kompilátor předem, že struktury s klíčem a hodnotou nelze zarovnat pomocí atributu aligned(1). Na ARM může být stejný efekt dosáhnout a pomocí atributu packed. Vzhledem k tomu, že také přispívá k optimalizaci prostoru zabraného konstrukcí, zdá se mi tato metoda výhodnější приводит zvýšit náklady na operace přístupu k datům.

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

Dotazy na rozsah

Pro iteraci přes skupinu záznamů poskytuje LMDB abstrakci kurzoru. Podívejme se, jak s ním pracovat, na příkladu nám již známé tabulky s uživatelskými cloudovými metadaty.

V rámci zobrazení seznamu souborů v adresáři musíte najít všechny klíče, ke kterým jsou přiřazeny jeho podřízené soubory a složky. V předchozích podsekcích jsme seřadili klíče NodeKey tak, že jsou nejprve seřazeny podle ID jejich nadřazeného adresáře. Technicky se tedy úkol získání obsahu složky redukuje na umístění kurzoru na horní hranici skupiny klíčů s danou předponou a následnou iteraci na spodní hranici.

Horní hranici "na čele" najdete sekvenčním vyhledáváním. Za tímto účelem se kurzor umístí na začátek celého seznamu klíčů v databázi a poté se inkrementuje, dokud se pod ním neobjeví klíč s identifikátorem nadřazeného adresáře. Tento přístup má 2 zjevné nevýhody:

1. Lineární složitost vyhledávání, i když, jak víte, ve stromech obecně a v B-stromu konkrétně, může být provedeno v logaritmickém čase.​
2. Marně se všechny stránky předcházející požadované stránce přesunou ze souboru do hlavní paměti, což je extrémně drahé.

Naštěstí LMDB API poskytuje efektivní způsob počáteční pozice kurzoru. K tomu je třeba vytvořit klíč, jehož hodnota je známá jako menší nebo rovna klíče umístěnému na horní hranici intervalu. Například ve vztahu k seznamu na obrázku výše můžeme vytvořit klíč, ve kterém je pole parentId se bude rovnat 2 a všechny ostatní jsou vyplněny nulami. Takto částečně vyplněný klíč je přiveden na vstup funkce mdb_cursor_get indikující provoz 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);

Pokud je nalezena horní hranice skupiny klíčů, iterujeme přes ni, dokud se buď nepotkáme, nebo klíč s jiným parentIdnebo klíče nedojdou 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​​

Co je fajn, v rámci iterace pomocí mdb_cursor_get získáme nejen klíč, ale i hodnotu. Pokud je pro splnění výběrových podmínek nutné zkontrolovat mimo jiné pole z hodnotové části záznamu, pak jsou sama sobě bez dalších gest celkem přístupná.

4.3. Modelování vztahů mezi tabulkami

K dnešnímu dni se nám podařilo zvážit všechny aspekty návrhu a práce s jednotabulkovou databází. Můžeme říci, že tabulka je množina seřazených záznamů skládajících se z párů klíč-hodnota stejného typu. Pokud zobrazíte klíč jako obdélník a jeho přidruženou hodnotu jako rámeček, získáte vizuální diagram databáze.

​

V reálném životě je však jen zřídka možné vyjít s tak malým množstvím krve. V databázi je často vyžadováno za prvé mít několik tabulek a za druhé v nich provádět výběry v jiném pořadí, než je primární klíč. Tato poslední část je věnována otázkám jejich tvorby a propojení.

Indexové tabulky

Cloudová aplikace má sekci „Galerie“. Zobrazuje mediální obsah z celého cloudu seřazený podle data. Pro optimální realizaci takového výběru je třeba vedle hlavní tabulky vytvořit další s novým typem klíčů. Budou obsahovat pole s datem vytvoření souboru, které bude fungovat jako primární kritérium řazení. Protože nové klíče odkazují na stejná data jako klíče v podkladové tabulce, nazývají se indexové klíče. Na obrázku níže jsou zvýrazněny oranžově.

Aby bylo možné oddělit klíče různých tabulek od sebe v rámci stejné databáze, bylo ke všem přidáno další technické pole tableId. Tím, že to bude nejvyšší priorita pro třídění, seskupíme klíče nejprve podle tabulek a již uvnitř tabulek - podle našich vlastních pravidel.​

Indexový klíč odkazuje na stejná data jako primární klíč. Přímá implementace této vlastnosti přidružením kopie hodnotové části primárního klíče není optimální z několika hledisek najednou:​

1. Z hlediska obsazeného prostoru mohou být metadata poměrně bohatá.
2. Z hlediska výkonu, protože při aktualizaci metadat uzlu budete muset přepsat dva klíče.
3. Z pohledu podpory kódu přeci jen, pokud zapomeneme aktualizovat data pro některý z klíčů, dostaneme jemný bug nekonzistence dat v úložišti.

Dále zvážíme, jak tyto nedostatky odstranit.

Organizace vztahů mezi tabulkami

Vzor se dobře hodí pro propojení indexové tabulky s hlavní "klíč jako hodnota". Jak název napovídá, hodnotová část záznamu indexu je kopií hodnoty primárního klíče. Tento přístup odstraňuje všechny výše uvedené nevýhody spojené s ukládáním kopie hodnotové části primárního záznamu. Jediným poplatkem je, že pro získání hodnoty indexovým klíčem musíte do databáze zadat 2 dotazy místo jednoho. Schematicky je výsledné schéma databáze následující.

Dalším vzorem pro uspořádání vztahů mezi tabulkami je "redundantní klíč". Jeho podstatou je přidání dalších atributů ke klíči, které nejsou potřeba pro třídění, ale pro opětovné vytvoření přidruženého klíče. Existují však reálné příklady jeho použití v aplikaci Mail.ru Cloud, aby se zabránilo hlubokému ponoru do kontextu konkrétních iOS frameworků uvedu fiktivní, ale o to srozumitelnější příklad.

Cloud mobilní klienti mají stránku, která zobrazuje všechny soubory a složky, které uživatel sdílí s ostatními lidmi. Protože takových souborů je relativně málo a je s nimi spojeno mnoho konkrétních informací o publicitě (komu je umožněn přístup, s jakými právy atd.), nebude racionální zatěžovat je hodnotovou částí záznam v hlavní tabulce. Pokud však chcete takové soubory zobrazovat offline, pak je stejně musíte někam uložit. Přirozeným řešením je vytvořit pro něj samostatný stůl. V níže uvedeném diagramu má jeho klíč předponu „P“ a zástupný symbol „propname“ lze nahradit konkrétnější hodnotou „public info“.​

Všechna jedinečná metadata, kvůli kterým byla nová tabulka vytvořena, se přesunou do hodnotové části záznamu. Zároveň nechci duplikovat data o souborech a složkách, které jsou již uloženy v hlavní tabulce. Místo toho jsou do klíče "P" přidána redundantní data ve formě polí "ID uzlu" a "časové razítko". Díky nim můžete zkonstruovat indexový klíč, pomocí kterého získáte primární klíč, pomocí kterého nakonec získáte metadata uzlu.

Závěr

Výsledky implementace LMDB hodnotíme kladně. Po něm se počet zamrznutí aplikací snížil o 30 %.

Výsledky odvedené práce našly odezvu i mimo tým iOS. V současné době také jedna z hlavních sekcí „Files“ v aplikaci pro Android přešla na používání LMDB a další části jsou na cestě. Jazyk C, ve kterém je úložiště klíč-hodnota implementováno, byl dobrým pomocníkem k tomu, aby se aplikace svázala kolem něj napříč platformami v jazyce C++. Pro bezproblémové propojení výsledné C++ knihovny s platformovým kódem v Objective-C a Kotlin byl použit generátor kódu Jinni z Dropboxu, ale to je jiný příběh.

Zdroj: www.habr.com