През есента на 2019 година в екипа на iOS в Облака Mail.ru настъпи дългоочакваното събитие. Основната база данни за персистентно съхранение на състоянието на приложението стана доста екзотична за мобилния свят. Lightning Memory-Mapped Database (LMDB). Под кат ще намерите подробен преглед в четири части. Първо, ще говорим за причините, които направиха избора толкова нетривиален и труден. След това ще преминем към разглеждането на трите основи на архитектурата на LMDB: файлове, отразени в паметта, B+-дърво, подход copy-on-write за реализиране на транзакционност и многовариантност. Накрая, накрая — практическа част. В нея ще разгледаме как да проектираме и реализираме схема на база данни с множество таблици, включително индексна, над нискоуровневото API с ключ-стойност.

Съдържание

1. Мотивация за внедряване
2. Позициониране на LMDB
3. Трите основи на LMDB
   3.1. Основа №1. Файлове, отразени в паметта
   3.2. Основа №2. B+-дърво
   3.3. Основа №3. Copy-on-write
4. Проектиране на схема на данни над API с ключ-стойност
   4.1. Основни абстракции
   4.2. Моделиране на таблици
   4.3. Моделиране на връзки между таблиците

1. Мотивация за внедряване

Някъде около 2015 година се заехме с измерването колко често интерфейсът на нашето приложение забавя. Не го правихме безпричинно. Получавахме все повече оплаквания, че понякога приложението спира да реагира на действията на потребителите: бутоните не се натискат, списъците не се скролват и т.н. Аз се занимавах с механиката на измерванията в AvitoTech, затова тук цитирам само ориентировъчни цифри. разказвах Резултатите от измерванията станаха за нас истински шок. Оказа се, че проблемите, причинени от загубите на реакция, са много повече от всичките други. Докато до осъзнаването на този факт основният технически показател за качество беше безпогрешността, след това фокусът

се премести към свободата от замръзвания. Изграждането на

дашборд с замръзвания и провеждането на количествен и качествен и анализ на причините за тях, стана ясен основният враг — тежката бизнес логика, изпълняваща се в основния поток на приложението. Естествената реакция на това безобразие беше силното желание да я разпределим по работни потоци. За системното решаване на тази задача прибегнахме до многопоточна архитектура, базирана на леки актьори. На нейното адаптиране за света на iOS посвещавам две теми в колективния Twitter и статия на Хабра . В рамките на текущото повествование искам да подчертая онези аспекти от решението, които повлияха на избора на база данни.. В рамках же текущего повествования хочу подчеркнуть те аспекты решения, которые повлияли на выбор базы данных.​

Акторният модел на организация на системата предполага, че многопоточността става нейна втора същност. Обектите в модела обичат да преминават граници на нишките. И те не го правят понякога и къде-как, а практически постоянно и навсякъде.

Базата данни е един от ключовите компоненти в представената схема. Нейната основна задача е реализирането на макропатерна. Споделена база данни. Докато в ентерпрайзния свят с нея организират синхронизация на данни между услугите, в случая на акторната архитектура — данните между нишките. Така че, ни трябва такава база данни, работата с която в многопоточна среда не предизвиква дори минимални затруднения. По-конкретно, това означава, че обектите, получени от нея, трябва да са поне потокобезопасни, а в идеалния случай и напълно немодифицируеми. Както е известно, последните могат да се използват едновременно от множество нишки, без да се налага да прибягваме до каквито и да било блокировки, което благоприятно влияе на производителността.

Вторият важен фактор, повлиял на избора на база данни, стана нашето облачно API. То беше вдъхновено от подхода за синхронизация, прилаган в git. Както в него, ние целяхме да постигнем offline-first API, което за облачните клиенти изглежда повече от подходящо. Предполагаше се, че те ще изтеглят веднъж цялостното състояние на облака, а след това синхронизацията ще се случва в подавляващата част от случаите чрез налагане на промени. За съжаление, тази възможност все още остава само в теоретичната си фаза, а на практика клиентите все още не са научили как да работят с пачовете. Има редица обективни причини за това, които, за да не удължавам въведението, ще оставим настрана. В момента много по-интересни са поучителните изводи от урока за това какво се случва, когато API каже „А“, а потребителят му не каже „Б“.

Ако си представите git, който при изпълнение на командата pull вместо да прилага пачове към локалния снапшот, сравнява целия му статус с този на сървъра, вие ще имате доста точна представа как става синхронизацията в облачните клиенти. Не е трудно да се досетите, че за целта е нужно да се алокират в паметта две DOM дървета с метаинформация за всички сървърни и локални файлове. Получава се, че ако потребителят съхранява 500 хиляди файла в облака, за да го синхронизирате, е необходимо да се възстановят и унищожат две дървета с 1 милион възли. А всеки възел представлява агрегат, съдържащ граф на подобекти. В този контекст резултатите от профилирането се оказаха очаквани. Установи се, че дори без да се взема предвид алгоритмиката за сливане, самата процедура по създаването и последващото разрушаване на огромно количество малки обекти е доста разходна. Положението се усложнява от факта, че основната операция по синхронизация е включена в много потребителски сценарии. В резултат на това фиксираме втория важен критерий при избора на база данни — възможността за изпълнение на CRUD операции без динамично алокиране на обекти.

Другите изисквания са по-традиционни и списъкът им изглежда по следния начин.

1. Потокобезопасност.
2. Мултипроцессност. Продиктувана от желанието да се използва един и същ инстанс на базата данни за синхронизация на състоянието не само между потоките, но и между основното приложение и екстеншъните за iOS.
3. Възможността за представяне на съ храняваните единици като немутируеми обекти.
4. Отсъствието на динамични алокации в рамките на CRUD операциите.
5. Поддръжка на транзакции с основни свойства ACID: атомарност, консистентност, изолираност и надеждност.
6. Скорост при най-популярните сценарии.

Добър избор с такъв набор от изисквания беше и остава SQLite. Въпреки това, при изучаването на алтернативи, попаднах на книга «Getting Started with LevelDB». Под ней беше написан бенчмарк, сравняващ скоростта на работа с различни бази данни в рамките на реални облачни сценарии. Резултатът надмина най-смелите очаквания. При най-популярните случаи — получаване на курсор на сортиран списък на всички файлове и сортиран списък на всички файлове за определена директория — LMDB се оказа десет пъти по-бърза от SQLite. Изборът стана очевиден.

2. Позициониране на LMDB

LMDB е библиотеката, много малка (само 10К реда), реализираща най-долния основен слой на бази данни — хранилище.

Представената схема показва, че сравнението на LMDB със SQLite, което реализира и по-високи нива, не е по-правилно отколкото сравнението между SQLite и Core Data. За равноправни конкуренти би било по-справедливо да се събират подобни хранилища — BerkeleyDB, LevelDB, Sophia, RocksDB и др. Има дори разработки, при които LMDB е компонент на storage engine за SQLite. Първият такъв експеримент е проведен през 2012 година от автора на LMDB Хауърд Чу. Резултати се оказаха толкова интригуващи, че начинанието му беше подхванато от ентусиасти в OSS, и продължи под формата на LumoSQL. През януари 2020 авторът на този проект Ден Шиърър представи го представи на LinuxConfAu.

Основното приложение на LMDB е като engine за приложни бази данни. Библиотеката дължи своето съществуване на разработчиците на OpenLDAP, които не бяха доволни от BerkeleyDB като основа на проекта си. Изхождайки от скромната библиотека btree, Хауърд Чу успя да създаде една от най-популярните алтернативи в наши дни. Тази история, а също и вътрешната структура на LMDB, той посвети на много интересната си лекция «Lightning Memory-mapped Database». Добър пример за овладяване на хранилище даде Леонид Юриев (aka yleo) от Positive Technologies в своята лекция на Highload 2015 «LMDB — специален шампион». В нея той разказва за LMDB в контекста на подобна задача при реализацията на ReOpenLDAP, а сравнителната критика беше насочена към LevelDB. В резултат на внедряването, Positive Technologies дори създаде активно развиващ се fork MDBX с много интересни функции, оптимизации и багфиксове..

LMDB често се използва и като хранилище as is. Например, браузърът Mozilla Firefox избра го за редица нужди, а, започвайки от версия 9, Xcode предпочете го пред SQLite за съхранение на индекси.

Двигателят стана популярен в света на мобилната разработка. Следите от неговото използване могат бъдат намерени да се намерят в iOS клиента на Telegram. LinkedIn отиде още по-далеч и избра LMDB за подразбираща се система за съхранение за домашния фреймворк за кеширане на данни Rocket Data, за което разказа пише в статията си от 2016 година.

LMDB успешно се бори за мястото си на слънцето в нишата, оставена от BerkeleyDB след прехвърлянето под контрола на Oracle. Библиотеката е обичана заради скоростта и надеждността си дори в сравнение с подобни. Както е известно, безплатни обеди не съществуват и е важно да подчертаем търговския компромис, с който ще се сблъскате при избора между LMDB и SQLite. Схемата по-горе ясно показва как се постига повишената скорост. Първо, не плащаме за допълнителни слоеве на абстракция над дисковото хранилище. Разбира се, в добра архитектура не можем да се минем без тях, но те ще бъдат много по-тънки. В тях няма да има функции, които не са необходими за конкретното приложение, например, поддръжка на заявки на SQL език. На второ място, се появява възможност за оптимално реализиране на мапинга на приложните операции на заявки към дисковото хранилище. Докато SQLite в своята работа изхожда от средностатистическите нужди на средностатистическото приложение, вие като приложен разработчик прекрасно знаете основните сценарии на натоварване. За по-производително решение трябва да платите с по-високи цени както за разработката на първоначалното решение, така и за последващото му поддържане.

3. Трите стълба на LMDB

След като погледнем на LMDB от височина, дойде времето да се спуснем по-дълбоко. Следващите три раздела ще бъдат посветени на анализа на основните стълбове, на които се опира архитектурата на хранилището:

1. Отображаемите в паметта файлове като механизъм за работа с диска и синхронизация на вътрешните структури на данните.
2. B+-деревото като организация на структурата на съхраняваните данни.
3. Copy-on-write като подход за осигуряване на ACID свойства на транзакциите и многовариантността.

3.1. Стълб №1. Файлове, отразени в паметта

Отображаемите в памет файлове са толкова важен архитектурен елемент, че дори присъстват в името на хранилището. Въпросите за кеширане и синхронизация на достъпа до съхраняваната информация са изцяло оставени на операционната система. LMDB не съдържа никакви кешове от вътрешната си страна. Това е осъзнато решение на автора, тъй като четенето на данни директно от отразените файлове позволява да се избегнат множество ъгли в реализацията на двигателя. По-долу давам далеч не пълен списък на някои от тях.

1. Поддържането на консистентност на данните в хранилището при работа с него от множество процеси става задължение на операционната система. В следващия раздел тази механика е разгледана в подробности и с изображения.
2. Липсата на кешове напълно освобождава LMDB от разходите, свързани с динамично алокации. Четенето на данни в практиката представлява задаване на указател на правилния адрес във виртуалната памет и не повече. Звучи като фантастика, но в източниците на хранилището всички повиквания saalloc са съсредоточени в функцията за конфигуриране на хранилището.
3. Липсата на кешове означава и липса на блокировки, свързани с синхронизацията на тяхния достъп. Читателите, които едновременно могат да съществуват произволно количество, не срещат нито един мютекс по пътя си към данните. По този начин скоростта на четене има идеална линейна мащабируемост спрямо количеството на CPU. В LMDB синхронизацията се подлага само на модифициращите операции. Писателят в всеки момент може да бъде само един.
4. Минимумът на логиката за кеширане и синхронизация освобождава кода от изключително сложни видове грешки, свързани с работата в многопоточна среда. На конференцията Usenix OSDI 2014 имаше две интересни изследвания на бази данни: «All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications» и «Torturing Databases for Fun and Profit». От тях може да се почерпи информация както за безпрецедентната надеждност на LMDB, така и за практически безупречната реализация на ACID-свойствата на транзакциите, превъзхождаща тази в SQLite.
5. Минимализмът на LMDB позволява машинното представяне на нейния код напълно да се вмести в L1 кеша на процесора с произтичащите от това скорости.

За съжаление, на iOS с изобразените в паметта файлове не всичко е толкова безоблачно, колкото бихме искали. За да обсъдим свързаните с тях недостатъци по-подробно, е необходимо да си припомним общите принципи на реализация на този механизъм в операционните системи.

Общи сведения за изобразените в паметта файлове

С всяко изпълнимо приложение операционната система асоциира субект, наречен процес. На всеки процес се выделя непрекъснат интервал от адреси, в който той разполага всичко необходимо за работата си. В най-ниските адреси се намират секции с код и вградени данни и ресурси. След това идва нарастващият блок от динамично адресно пространство, добре познат ни под името heap. В него се съдържат адреси на субекти, които се появяват по време на работа на програмата. В горната част се намира област от паметта, използвана от стека на приложението. Той нараства и се свива, с други думи, размерът му също има динамична природа. За да не се сблъскват стекът и heap, те са разделени на различни краища на адресното пространство. Между двете динамични секции в горната и долната част има дупка. Адресите в този срединен участък операционната система използва, за да асоциира с процеса различни субекти. В частност, тя може да асоциира на определен непрекъснат набор от адреси — файл на диска. Такъв файл се нарича изобразен в паметта.

Отделеното на процеса адресно пространство е огромно. Теоретичното количество адреси е ограничено единствено от размера на указателя, определящ се от битността на системата. Ако той бе 1-в-1 съпоставен с физическата памет, то първият процес щеше да изяде цялата оперативна памет и ни за каква многозадачност не би могло да стане и дума.

Обаче от своя опит знаем, че съвременните операционни системи могат едновременно да изпълняват неограничено много процеси. Това е възможно, благодарение на факта, че те само на хартия отделят много памет на процесите, а в действителност зареждат в основната физическа памет само оная част, която се търси тук и сега. Затова паметта, асоциирана с процеса, се нарича виртуална.

Операционната система организира виртуалната и физическата памет под формата на страници с определен размер. Веднага щом някоя страница от виртуалната памет бъде поискана, операционната система я зарежда във физическата памет и установява съответствието между тях в специална таблица. Ако няма свободни слотове, една от по-рано заредените страници се копира на диска, а поискваната заема нейното място. Тазипроцедура, към която скоро ще се върнем, се нарича свопинг (swapping). На схемата по-долу е илюстриран описаният процес. На нея страница А с адрес 0 е заредена и поставена на страница на основната памет с адрес 4. Този факт е отразен в таблицата за съответствия в клетка номер 0.

Историята с отображените в паметта файлове е идентична. Логически те якобы непрекъснато и изцяло са разположени в виртуалното адресно пространство. Въпреки това, физическата памет ги приема на страницов принцип и само при искане. Модификацията на тези страници се синхронизира с файла на диска. По този начин може да се извършва файлов вход/изход, просто работейки с байтове в паметта — всички промени автоматично ще бъдат пренесени от ядрото на операционната система към оригиналния файл.
​
Изображението по-долу демонстрира как LMDB синхронизира състоянието си при работа с база данни от различни процеси. Като мапваме виртуалната памет на различни процеси към един и същи файл, де факто ние задължаваме операционната система транзитивно да синхронизира определени блокове от техните адресни пространства, към които LMDB се обръща.
​

Важен нюанс е, че LMDB по подразбиране модифицира файла с данни чрез механизма на системния извикване write, а самият файл се отразява в режим само за четене. Този подход има две важни последствия.

Първото последствие е общо за всички операционни системи. Същността му е в добавянето на защита от непреднамерено повреждане на базата данни от неправилен код. Както е известно, изпълняемите инструкции на процеса имат свободен достъп до данните от всяко място в адресното пространство. В същото време, както току-що споменахме, показването на файл в режим на четене и запис означава, че всяка инструкция може също така да го модифицира. Ако тя направи това по грешка, опитвайки се, например, реально да презапише елемент от масив с несъществуващ индекс, може случайно да промени файла, отразен на този адрес, което ще доведе до повреждане на базата данни. Ако файлът обаче е показан в режим само за четене, опитът да се промени съответното адресно пространство ще доведе до аварийно завършване на програмата с сигнал SIGSEGV, и файлът ще остане целостен.

Второто последствие вече е специфично за iOS. Нито авторът, нито каквито и да било други източници не го споменават явно, но без него LMDB нямаше да бъде пригодна за работа в тази мобилна операционна система. На него е посветен следващият раздел.

Спецификата на показаните в паметта файлове в iOS

През 2018 година на WWDC имаше страхотна лекция «iOS Memory Deep Dive». В нея се разказва, че в iOS всички страници, разположени в физическата памет, спадат към един от 3 типа: замърсени, компресирани и чисти.

Чистата памет е съвкупност от страници, които могат безпроблемно да бъдат изтеглени от физическата памет. Данните в тях могат при необходимост да бъдат заредени отново от техните първоначални източници. Файловете, отразени в режим само за четене, попадат именно в тази категория. iOS не се притеснява да изхвърли от паметта страниците, отразени на файл, по всяко време, тъй като те са гарантирано синхронизирани с файла на диска.
​
В замърсената памет попадаха всички модифицирани страници, независимо къде са разположени първоначално. В частност, така ще бъдат класифицирани и файловете, отразени в паметта, променени чрез запис в свързаната с тях виртуална памет. Отваряйки LMDB с флага MDB_WRITEMAP, след като направите промени в нея, можете лично да се уверите в това.

Когато приложението започне да заема твърде много физическа памет, iOS компресира неговите dirty страници. Общото количество памет, заето от dirty и компресирани страници, се нарича memory footprint на приложението. Когато достигне определен праг, системният демон OOM killer намесва и принудително прекратява процеса. В това се състои особеността на iOS в сравнение с настолните операционни системи. За разлика от тях, в iOS не е предвидено понижаване на memory footprint чрез свопинг на страници от физическата памет на диска. Причините за това могат само да се предполагат. Може би процедурата по интензивно преместване на страници на диска и обратно е твърде енергийно разходна за мобилни устройства или iOS пести ресурс от запис на клетки на SSD дисковете, или може би проектантите не са били удовлетворени от цялостната производителност на системата, в която всичко непрекъснато се свопва. Каквото и да е, фактът остава факт.

Добрата новина, вече спомената по-рано, е, че LMDB по подразбиране не използва механизма mmap за актуализиране на файлове. Следователно отразените данни се класифицират от iOS като clean memory и не допринасят за memory footprint. Това може да се провери с помощта на инструмента на Xcode, наречен VM Tracker. На екрана по-долу е показано състоянието на виртуалната памет на iOS приложението Облака по време на работа. В началото бяха инициализирани 2 инстанса LMDB. Първият получи разрешение да отрази своя файл на 1GiB виртуална памет, вторият — на 512MiB. Въпреки че и двете хранилища заемат определен обем резидентна памет, нито едно от тях не допринася за dirty size.

А сега време за лоши новини. Благодарение на механизма за свопинг в 64-битните настолни операционни системи всеки процес може да заеме толкова виртуално адресно пространство, колкото позволява свободното пространство на твърдия диск за неговия потенциален своп. Замяната на свопинга с компресия в iOS радикално намалява теоретичния максимум. Сега всички текущи процеси трябва да се вместят в основната (имайте предвид оперативната) памет, а всички, които не се вместят, подлежат на принудително прекратяване. За това се споменава и в споменатото по-горе. в доклада, така и в официалната документацияВ резултат на това, iOS строго ограничава размера на паметта, достъпна за разпределение чрез mmap. Ето го. тук Можете да се запознаете с емпиричните ограничения на обема памет, който е успял да се алокира на различни устройства чрез тази системна повикване. На най-съвременните модели смартфони iOS са предоставени 2 гигабайта, а на топ версиите на iPad — 4. На практика, разбира се, трябва да се ориентирате по най-ниските подкрепяни модели устройства, където всичко е много тъжно. Още по-лошо, когато погледнете състоянието на паметта на приложението в VM Tracker, можете да откриете, че LMDB не е единствения кандидат за памет с карта. Значителни части отиват при системните алокатори, файловете с ресурси, фреймворките за работа с изображения и други по-малки хищници.

В резултат на експериментите в Облака стигнахме до следните компромисни стойности за алокирана LMDB памет: 384 мегабайта за 32-битови устройства и 768 — за 64-битови. След изчерпването на този обем, всички модифициращи операции започват да завършват с код MDB_MAP_FULL. Такива грешки наблюдаваме в нашия мониторинг, но те са достатъчно малко, за да можем да пренебрегнем тях на този етап.

Неочевидната причина за прекомерната консумация на памет от хранилището може да бъдат дългоживеещи транзакции. За да разберем как са свързани тези две явления, ще ни помогне разглеждането на останалите две основи на LMDB.

3.2. Основа №2. B+-дърво

За да се емулират таблиците върху key-value хранилище, е необходимо в неговото API да присъстват следните операции:

1. Вмъкване на нов елемент.
2. Търсене на елемент с даден ключ.
3. Изтриване на елемент.
4. Итериранем по интервали от ключове в реда на тяхната подредба.

Най-простата структура от данни, с помощта на която могат лесно да се реализират всички четири операции, е бинарното дърво за търсене. Всеки негов възел представлява ключ, разделящ целия подмножество от дъщерни ключове на две поддървета. В лявото са събрани тези, които са по-малки от родителския, а в дясното — тези, които са по-големи. Получаването на подреден набор от ключове се постига чрез едно от класическите обходи на дървото.

Бинарните дървета имат два основни недостатъка, които не им позволяват да бъдат ефективни като дискова структура от данни. Първо, степента на тяхната балансировка е непредсказуема. Има значителен риск да се получат дървета, в които височината на различните клони може да се различава значително, което значително влошава алгоритмичната сложност на търсенето в сравнение с очакваното. На второ място, изобилието от кръстосани връзки между възлите лишава бинарните дървета от локалност в паметта. Близките възли (от гледна точка на връзките между тях) могат да се намират на напълно различни страници в виртуалната памет. В резултат, дори за прост обход на няколко съседни възла в дървото може да се изисква да се посетят съпоставимо количество страници. Това е проблем дори когато говорим за ефективността на бинарните дървета като in-memory структура от данни, тъй като постоянната ротация на страниците в кеша на процесора е скъпо удоволствие. Когато става въпрос за често извличане на свързани със възлите страници от диска, положението става наистина зле.

B-деревата, будейки еволюция на бинарните дървета, решават обозначените в предишния параграф проблеми. Първо, те са самобалансирующие се. Второ, всеки техен възел разделя множеството от дъщерни ключове не на 2, а на M подредени подмножества, като числото M може да бъде доста голямо, от порядъка на няколко стотин или дори хиляди.

Благодарение на това:

1. Във всеки възел се намира голямо количество вече подредени ключове и дърветата стават много ниски.
2. Дървото придобива свойството на локалност в разположението в паметта, тъй като близките по стойност ключове естествено се намират в близост един до друг на един или съседни възли.
3. Намалява броят на транзитните възли при спускане по дървото по време на операция на търсене.
4. Намалява броят на четените целеви възли при range-запитвания, тъй като в тях вече има голямо количество подредени ключове.

В LMDB за съхраняване на данни се използва една от вариациите на B-дерево, наречена B+-дерево. На схемата по-горе са изобразени три типа възли, които в него присъстват:

1. Върхът съдържа корена (root). Той представлява концепцията за база данни в хранилището. В рамките на един инстанс LMDB могат да се създадат няколко бази данни, разделящи помежду си виртуалното адресно пространство. Всяка от тях започва със свой собствен корен.
2. На най-долното ниво са листата (leaf). Само те съдържат парите ключ-стойност, съхранявани в базата данни. Това е специфичното за B+-дърветата. Докато обикновеното B-дерево съхранява стойностите (value) в възлите на всички нива, B+-вариацията ги съхранява само на най-долното ниво. Приемайки този факт, по-нататък ще наричаме подтипът на дървото, използвано в LMDB, просто B-дерево.
3. Между корена и листата се намират 0 или повече технически нива с навигационни (branch) възли. Тяхната задача е да разделят сортирането на ключовете между листата.

Физически, възлите са блокове памет с предварително зададена дължина. Размерът им е кратен на размера на паметните страници в операционната система, за които говорихме по-горе. По-долу е представена структурата на възела. В хедъра се съдържа метаинформация, като най-очевидната за примера е контролна сума. Следва информация за офсетите, където се намират клетките с данни. Като данни могат да действат либо ключовете, ако говорим за навигационни възли, либо цели двойки ключ-стойност в случая на листата. По-подробно за структурата на страниците може да се прочете в работа «Evaluation of High Performance Key-Value Stores».

След като разгледахме вътрешното съдържание на възлите-страници, B-деревото на LMDB ще представим опростено по следния начин.

Страниците с възли последователно се разполагат на диска. Страниците с по-висок номер са разположени по-близо до края на файла. Наречената мета-страница (meta page) съдържа информация за офсетите, по които могат да се намерят корените на всички дървета. При отваряне на файла, LMDB последователно сканира файла от края към началото в търсене на валидна мета-страница и вече чрез нея намира съществуващите бази данни.

Сега, след като имаме представа за логическата и физическата структура на организацията на данните, можем да преминем към разглеждането на третия кит на LMDB. Именно с негова помощ всички модификации на хранилището протичат транзакционно и изолирано една от друга, придавайки на базата данни в цялост и свойството на множество версии.

3.3. Кит №3. Copy-on-write

Някои операции с B-дерево предвиждат извършването на серия от промени в неговите възли. Един от примерите е добавянето на нов ключ в възел, който вече е достигнал максималния капацитет. В такъв случай е необходимо, първо, да се раздели възелът на два, и на второ, да се добави връзка към новосъздадения дъщерен възел в неговия родител. Тази процедура е потенциално много опасна. Ако по някаква причина (срив, прекъсване на захранването и т.н.) се случи само част от промените от серията, то дървото ще остане в неконсистентно състояние.

Едно от традиционните решения за осигуряване на устойчивост на базата данни при повреди е добавянето на допълнителна дискова структура данни до B-деревото — лог на транзакции, известен също като write-ahead log (WAL). Той представлява файл, в който в края се записва предполагаемата операция стриктно преди модификацията на самото B-дерево. По този начин, ако по време на самодиагностика се открие повреда на данните, базата данни се консултира с лог файла, за да се върне в ред.

LMDB избра друг метод за осигуряване на устойчивост при повреди, наречен copy-on-write. Същността му е, че вместо да актуализира данните на съществуващата страница, тя първо я копира цялата и всички модификации се извършват вече в копието.

След това, за да бъдат актуализираните данни достъпни, е необходимо да се промени връзката към актуализирания възел в родителския към него възел. Понеже и за това е необходимо да се модифицира, той също предварително се копира. Процесът продължава рекурсивно до самия корен. Последните се променят данните на мета-страницата.

Ако по време на процедурата за обновление статусът прекъсне аварийно, новата мета-страница може или да не бъде създадена, или да не бъде записана на диска до края, като нейният контрольна сума ще бъде некоректна. В който и да е от тези два случая новите страници няма да са достъпни, а старите няма да бъдат засегнати. Това освобождава LMDB от необходимостта да води журнал за предварително записване за поддържане на консистентността на данните. Де-факто структурата за съхранение на данните на диска, описана по-горе, също изпълнява и тази функция. Липсата на журнал за транзакции в явен вид е една от характеристиките на LMDB, която осигурява висока скорост на четене на данни.

Получената конструкция, наречена append-only B-tree, естествено осигурява изолация на транзакциите и мултиверсионност. В LMDB с всяка отворена транзакция е асоцииран текущият корен на дървото. Докато транзакцията не бъде завършена, страниците, свързани с нея, никога няма да бъдат променяни или повторно използвани за нови версии на данни. По този начин можете да работите неограничено с онзи набор от данни, който е актуален в момента на откриването на транзакцията, дори когато хранилището активно се обновява. В това се състои същността на мултиверсионността, която прави LMDB идеален източник на данни за всички нас. UICollectionView. При откриването на транзакция не е необходимо да увеличавате memory footprint на приложението, бързо извличайки актуалните данни в някаква in-memory структура, страхувайки се да не останете с празни ръце. Тази характеристика отличава LMDB от SQLite, който не може да се похвали с такава пълна изолация. При отваряне на две транзакции в него и премахване на определен запис в рамките на една от тях, този запис вече не може да бъде получен и в рамките на втората оставена.

Обратната страна на медала е потенциално значително по-високото потребление на виртуална памет. На слайда е показана как ще изглежда структурата на базата данни, ако се модифицира едновременно с 3 отворени транзакции за четене, гледащи на различни версии на базата данни. Тъй като LMDB не може да преизползва възлите, достижими от корените, свързани с актуалните транзакции, хранилището няма какво друго да направи освен да разположи в паметта още един четвърти корен и отново да клонира под него модифицираните страници.

Тук е уместно да си припомним раздела за файлове, картографирани в паметта. Изглежда, че допълнителното потребление на виртуална памет не би трябвало да ни притеснява особено, тъй като то не допринася за memory footprint на приложението. Въпреки това, отбелязано е, че iOS е много стисната в разпределението му, и нямаме възможност, както на сървър или десктоп, да предоставим зоната на LMDB от 1 терабайт и да не мислим за този аспект. По възможност трябва да се стремим да направим живота на транзакциите колкото се може по-кратък.

4. Проектиране на схема от данни над key-value API

Разборът на API ще започнем с разглеждане на основните абстракции, предоставени от LMDB: околната среда и бази данни, ключове и стойности, транзакции и курсори.

Забележка за кодовите листинги

Всички функции в публичния API на LMDB връщат резултата от изпълнението си под формата на код на грешка, но в следващите листинги проверката на този код е пропусната в интерес на лаконичността. На практика ние използвахме собствен форка C++ обвивки lmdbxx, в който грешките се материализират под формата на изключения C++.

Като най-бърз начин за свързване на LMDB с проект за iOS или macOS, предлагам своя CocoaPod POSLMDB.

4.1. Основни абстракции

Околната среда (environment)

Структура MDB_env е вместилище на вътрешното състояние на LMDB. Семейство функции с префикс mdb_env позволява конфигуриране на някои от свойствата му. В най-простия случай инициализацията на движка изглежда по следния начин.

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

В приложението Облака Mail.ru променихме стойностите по подразбиране само на два параметъра.

Първият от тях е размерът на виртуалното адресно пространство, на което се отразява файлът за съхранение. За съжаление, дори на едно и също устройство конкретното значение може да се различава значително от стартиране до стартиране. За да се вземе предвид тази особеност на iOS, максималният обем на съхранението се определя динамично. Започвайки от определена стойност, той последователно се намалява, докато функцията mdb_env_open не върне резултат, различен от ENOMEM. В теорията съществува и противоположният път — първо да се задели минимум памет за двигателя, а след това, при получаване на грешки MDB_MAP_FULL, да се увеличава. Въпреки това, той е много по-труден. Причината е, че процедурата за повторно разпределение на паметта (remap) с помощта на функцията mdb_env_set_map_size инвалидира всички сущности (курсове, транзакции, ключове и стойности), получени от двигателя по-рано. Вземането предвид на такъв обрат в събитията в кода ще доведе до значително усложнение. Ако, все пак, виртуалната памет е много важна за вас, то това може да е причина да погледнете в напреднал Fork, MDBX, който предлага функцията "automatic on-the-fly database size adjustment."

Вторият параметър, чиято стойност по подразбиране не ни устройва, регулира механиката за осигуряване на безопасност при работа с нишки. За съжаление, поне в iOS 10 има проблеми с поддръжката на thread local storage. Поради тази причина в примера по-горе хранилището се отваря с флага MDB_NOTLS. Освен това беше необходимо и форкване C++ обертка lmdbxx, за да се премахнат променливите с този атрибут от нея.

Бази данни

Базата данни представлява отделен инстанс на B-дерево, за което говорихме по-горе. Нейното отваряне се извършва вътре в транзакция, което вначалото може да изглежда малко странно.

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

В действителност, транзакцията в LMDB е сущност на съхранението, а не на конкретната база данни. Такава концепция позволява извършването на атомни операции над сущности, които се намират в различни бази данни. В теорията това отваря възможност за моделиране на таблици под формата на различни бази, но аз по времето си избрах друг път, описан подробно по-долу.

Ключове и стойности

Структура MDB_val моделира концепция както на ключа, така и на стойността. Хранилището не разполага нито с най-лютивото представа за тяхната семантика. За него едното и другото са просто масив от байтове с определен размер. Максималният размер на ключа е 512 байта.

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

С помощта на компаратора хранилището подрежда ключовете по нарастващ ред. Ако не го замените с ваш собствен, ще се използва по подразбиране, който ги сортира байт по байт в лексикографски ред.

Транзакции

Устройството на транзакциите е подробно описано в предишната глава, затова тук кратко ще повторя основните им свойства:

1. Поддържа всички основни свойства ACID: атомарност, последователност, изолираност и надеждност. Не мога да не отбележа, че по отношение на издръжливостта на macOS и iOS има бъг, който е поправен в MDBX. Подробности можете да прочетете в тяхната README.
2. Подходът към многопоточността се описва със схема «един писател / множество читатели». Писателите блокират един друг, но не блокират читателите. Читателите не блокират нито писателите, нито помежду си.
3. Поддръжка на вложени транзакции.
4. Поддръжка на мултиверсионност.

Мултиверсионността в LMDB е толкова добра, че искам да я демонстрирам в действие. От кода по-долу е видно, че всяка транзакция работи именно с версията на базата данни, която е била актуална в момента на нейното отваряне, будейки напълно изолирана от всички последващи промени. Инициализацията на хранилището и добавянето на тестова записка не представляват нищо интересно, затова тези ритуали са оставени под спойлер.

Добавяне на тестова записка

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

Факултативно препоръчвам да опитате същия трик с SQLite и да видите какво ще излезе.

Мултиверсността внася много приятни предимства в живота на iOS разработчика. С помощта на това свойство можем лесно и неусетно да регулираме скоростта на обновяване на източника на данни (data source) за екранни форми, като взимаме под внимание потребителския опит. Например, нека разгледаме такава функция на приложението Облака Mail.ru, като автоматично зареждане на съдържание от системната медийна галерия. При добро свързване клиентът е способен да добавя на сървъра няколко снимки в секунда. Ако след всяко зареждане актуализираме UICollectionView с медийните съдържания в облака на потребителя, можем да забравим за 60 fps и плавно превъртане по време на този процес. За да предотвратим чести обновления на екрана, е необходимо по някакъв начин да ограничим скоростта на изменение на данните в основата UICollectionViewDataSource.

Ако базата данни не поддържа многовариантност и позволява работа само с текущото актуално състояние, то за създаването на стабилен за времето моментна снимка на данните е необходимо да се извърши нейното копиране либо в определена in-memory структура от данни, либо в временна таблица. Всеки от тези подходи е много разходен. В случая на in-memory хранилище получаваме разходи както по памет, причинени от съхраняването на конструирани обекти, така и по време, свързани с излишните ORM-преобразувания. Що се отнася до временната таблица, това е още по-скъпо удоволствие, което има смисъл само в нетривиални случаи.

Многовариантността на LMDB решава задачата за поддържане на стабилен източник на данни много елегантно. Достатъчно е просто да отворим транзакция и вуаля — докато не я завършим, наборът от данни е гарантирано фиксиран. Логиката на скоростта на нейното обновление сега изцяло и напълно е в ръцете на презентационния слой при пълно отсъствие на разходите за значителни ресурси.

Курсори

Курсорите предоставят механизъм за подредено итерации по двойките ключ-стойност чрез обход на B-дерево. Без тях не бихме могли ефективно да моделираме таблици в базата данни, към които преминаваме.

4.2. Моделиране на таблици

Свойството на подреденост на ключовете позволява изграждането на високо ниво над основни абстракции като таблица. Нека разгледаме този процес на примера на основната таблица на облачния клиент, в която е кеширана информация за всички файлове и папки на потребителя.

Схема на таблицата

Един от честите сценарии, за който структурата на таблицата с дърво от папки трябва да бъде подготвена — извличането на всички елементи, разположени в зададена директория. Добра модел на организация на данните за ефективни заявки от този вид е Списък на съседството. За нейното реализиране върху хранилище с ключ-стойност е необходимо да се сортират ключовете на файловете и папките по такъв начин, че да се групират на основание принадлежността си към родителската директория. Освен това, за да се показва съдържанието на директорията в познат за потребителя Windows вид (първо папките, след това файловете, и двата типа са сортирани по азбучен ред), е необходимо да се включат в ключа съответните допълнителни полета.

На изображението по-долу е показано как, в зависимост от поставената задача, може да изглежда представянето на ключовете под формата на массив от байтове. Първо се нареждат байтовете с идентификатора на родителската директория (червени), после - с типа (зелени) и накрая - с името (сини). Когато са сортирани с подразбиращия се компаратор на LMDB в лексикографски ред, те се организират по необходимия начин. Последователното обхождане на ключовете с един и същ червен префикс ни дава свързаните с тях стойности в реда, в който те трябва да бъдат представени в потребителския интерфейс (вдясно), без да изисква допълнителна постобработка.

Сериализация на ключове и стойности

В света са създадени множество методи за сериализация на обекти. Тъй като не ни имаше никакво друго изискване, освен скоростта, ние избрахме най-бързия от възможните - дамп на паметта, заета от инстанса на структура от езика C. Така, ключът на елемента от директорията може да бъде моделиран по следната структура NodeKey.

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

За запазване NodeKey в хранилището е необходимо в обекта MDB_val да позиционирате указателя на данните на адреса на началото на структурата, а размерът им да се изчисли с функцията sizeof.

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

В първата глава относно критериите за избор на база данни споменах минимизацията на динамичните алокации в рамките на CRUD операциите. Кодът на функцията serialize показва как в случая на LMDB те могат напълно да бъдат избегнати при вмъкване на нови записи в базата данни. Пристигналият масив от байтове от сървъра първо се трансформира в стекови структури, а след това те по тривиален начин се дампят в хранилището. Имайки предвид, че в LMDB също няма динамични алокации, можем да получим фантастична по мерките на iOS ситуация - да използваме за работа с данните по целия им маршрут от мрежата до диска само стекова памет!

Подреждане на ключовете с бинарен компаратор

Отношението на ключовете се задава от специална функция, наречена компаратор. Тъй като механизмът не знае нищо за семантиката на байтовете, които съдържат, на стандартния компаратор не остава нищо друго освен да подреди ключовете в лексикографски ред, преглеждайки ги по отделни байтове. Използването му за подреждане на структури е като да се бръснем с инструмент за рязане на месо. Въпреки това, в по-прости случаи, намирам този метод за приемлив. Алтернативата е описана малко по-долу, а тук ще спомена две-три препятствия, които ще срещнете по пътя.

Първото, за което трябва да помните, е представянето в паметта на примитивни типове данни. Така, на всички устройства на Apple цели числа се съхраняват в формат Little Endian. Това означава, че най-малко значимият байт ще се намира вляво и не можем да сортираме цели числа, използвайки сравнение по байтове. Например, опитът да го направим с набор от числа от 0 до 511 ще доведе до следния резултат.

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

За решаването на този проблем, целите числа трябва да се съхраняват в ключа в подходящ за байтовия компаратор формат. Нужното преобразуване ще помогнат функции от семейството на hton* (по-специално htons за двубайтови числа от примера).

Форматът на представяне на низовете в програмирането е, както е известно, цялостен история. Ако семантиката на низовете и използваната за тях представяне в паметта кодировка предполагат, че на символ може да съответства повече от един байт, то е по-добре да се откажете от идеята за използване на стандартния компаратор.

Второто, което трябва да имате предвид, са принципите на подравняване на компилатора на полета в структурата. Поради тях в паметта между полетата могат да се образуват байтове с ненужни стойности, което, разбира се, разваля подреждането по байтове. За премахване на нежеланите байтове, трябва или да декларирате полета в строго определен ред, като спазвате правилата за подравняване, или да използвате атрибута packed.

Подреждане на ключовете от външен компаратор

Логиката на сравнение на ключовете може да се окаже твърде сложна за бинарния компаратор. Една от многото причини е наличието на технически полета в структури. Ще илюстрирам тяхното възникване на примера на вече познатия ни ключ за елемент в директорията.

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

Въпреки своята простота, в голямото мнозинство случаи той консумира твърде много памет. Буферът за имена заема 256 байта, въпреки че средната дължина на имената на файловете и папките рядко надвишава 20-30 символа.

Една от стандартните техники за оптимизиране на размера на записа е „отрязването“ му до реалния размер. Същността е, че съдържанието на всички променливи полета се съхранява в края на структурата, а техните дължини – в отделни променливи. Според този подход ключ NodeKey се трансформира по следния начин.

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

След това при сериализацията като размер на данните се посочва не sizeof цялата структура, а размерът на всички полета с фиксирана дължина плюс размерът на реално използваната част от буфера.

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

В резултат на извършена рефакторизация получихме значителна икономия на място за ключовете. Но заради техническото поле nameLength, стандартният бинарен компаратор вече не е подходящ за сравняване на ключовете. Ако не го заменим с наш, дължината на името ще бъде по-важен фактор при сортирането от самото име.

LMDB позволява на всяка база данни да зададе своя функция за сравнение на ключовете. Това става чрез функцията mdb_set_compare строго преди отварянето. По очевидни причини, в течение на живота на базата данни тя не може да бъде променяна. На вход компараторът получава два ключа в бинарен формат, а на изхода връща резултат от сравнението: по-малко (-1), повече (1) или равни (0). Псевдокодът за NodeKey изглежда така.

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

Докато в базата данни всички ключове имат един и същи тип, безусловното преобразуване на байтовото им представяне в типа на приложната структура на ключа е законно. Тук има един нюанс, но той ще бъде разгледан по-долу в подраздела „Четене на записи“.

Сериализация на стойности

Работата с ключовете на записките в LMDB е изключително интензивна. Сравнението между тях се извършва по време на всяка приложение на операция, а производителността на цялото решение зависи от скоростта на компаратора. В идеалния свят за сравнение на ключовете би трябвало да е достатъчен подразбиращият се бинарен компаратор, но ако е необходимо да използвате свой собствен, процедурата по десериализация на ключовете в него трябва да бъде колкото се може по-бърза.

Частта с стойността на записката (value) не буди особен интерес за базата данни. Нейното преобразуване от байтово представяне в обект става само когато е необходимо на приложния код, например, за показване на екран. Тъй като това става сравнително рядко, изискванията към скоростта на тази процедура не са толкова критични и при нейното изпълнение сме много по-свободни да се съсредоточим върху удобството. Например, за сериализация на метаданни за още незаредени файлове използваме NSKeyedArchiver.

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

Въпреки това, в определени случаи производителността все пак има значение. Например, при запазване на метаинформация за файловата структура на потребителското облако, използваме същата паметна дамп на обектите. Интересното в задачата за формирането на тяхното сериализирано представяне е фактът, че елементите на директорията се моделират чрез йерархия от класове.

За нейното реализиране на C специфичните полета на наследниците се изнасят в отделни структури, а връзката им с базовия клас се задава чрез поле от тип union. Актуалното съдържание на union-а се задава чрез техническия атрибут type.

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

Добавяне и обновяване на записи

Сериализираният ключ и стойност могат да бъдат добавяни в хранилището. За целта се използва функцията mdb_put.

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

В конфигурационном этапе для хранилища можно разрешить или запретить хранение нескольких записей с одинаковым ключом. Если дублирование ключей запрещено, во время вставки записи можно определить, допустимо ли обновление уже существующей записи или нет. Если перезапись может произойти только по ошибке в коде, то можно защититься, установив флаг NOOVERWRITE.

Чтение записей

Для чтения записей в LMDB предназначена функция mdb_get. Если пара ключ-значение была ранее представлена в дампированных структурах, то процесс выглядит следующим образом.

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

Представленный листинг показывает, как сериализация через дамп структур позволяет избавиться от динамических аллокаций не только при записи, но и при чтении данных. Указатель, полученный из функции mdb_get смотрит точно по тому адресу виртуальной памяти, где база данных хранит байтовое представление объекта. По сути, мы получаем нечто вроде ORM, обеспечивающего очень высокую скорость чтения данных практически без дополнительных затрат. Однако при всей привлекательности подхода важно помнить о нескольких связанных с ним особенностях.

1. Для транзакций только на чтение указатель на структуру-значение будет гарантированно оставаться валидным только до тех пор, пока транзакция не будет завершена. Как упоминалось ранее, страницы B-дерева, на которых находится объект, благодаря принципу copy-on-write остаются неизменными, пока на них ссылается хотя бы одна транзакция. Однако, как только последняя связанная с ними транзакция завершается, страницы могут быть повторно использованы для новых данных. Если необходимо, чтобы объекты пережили транзакцию, породившую их, их всё равно придётся скопировать.
2. Для транзакций на чтение и запись указатель на полученную структуру-значение будет валидным только до первой модифицирующей операции (записи или удаления данных).
3. Несмотря на то, что структура NodeValue является неполной и обрезанной (см. подраздел «Упорядочивание ключей внешним компаратором»), через указатель можно спокойно обращаться к её полям. Главное — не разыменовывать его!
4. Никак не трябва да модифицирате структурата чрез получения указател. Всички промени трябва да се извършват само чрез метода mdb_put. Въпреки всичките усилия, няма да успеете, тъй като областта на паметта, където се намира тази структура, е картографирана в режим на само четене.
5. Ремапирането на файла в адресното пространство на процеса с цел, например, увеличаване на максималния размер на хранилището с функцията mdb_env_set_map_size пълно инвалидиране на всички транзакции и свързаните с тях единици изцяло, включително указателите на прочетените обекти.

Накрая, още една особеност е толкова коварна, че разкриването на същността й не може да се впише просто в още една точка. В главата за B-деревото представих схема на устройството на страниците му в паметта. От нея следва, че адресът на началото на буфера с сериализираните данни може да бъде абсолютно произволен. Заради това указателят към тях, получен в структурата MDB_val и приведен към указател на структура, може в общия случай да не бъде подравнен. В същото време архитектурите на някои чипове (в случая iOS е armv7) изискват адресът на всякакви данни да бъде кратен на размера на машинното слово или, иначе казано, на битността на системата (за armv7 — това е 32 бита). С други думи, операция като *(int *foo)0x800002 с тях е равносилна на побег и води до присъда EXC_ARM_DA_ALIGN. Можете да избегнете толкова печална участ по два начина.

Първият начин се състои в предварително копиране на данните в предварително подравнена структура. Например, при кастомния компаратор това ще се отрази по следния начин.

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

Алтернативният път е предварително да уведомите компилатора, че структурите с ключ и стойност могат да не са подравнени, с помощта на атрибута aligned(1). На ARM същия ефект може да се постигне да се постигне и с помощта на атрибута packed. Като се има предвид, че той също така допринася за оптимизацията на заеманото от структурата място, този метод ми се струва предпочитан, макар и предлага с повишаване на цената на операциите за достъп до данни.

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

Диапазонни заявки

За итерация през група записи в LMDB е предвидена абстракция на курсора. Как да работим с него, ще разгледаме на примера на познатата ни таблица с метаданни на облака на потребителя.

В рамките на показването на списък с файлове в директория е необходимо да се намерят всички ключове, с които са асоциирани нейните дъщерни файлове и папки. В предходните подраздели сортирахме ключовете NodeKey така, че те да бъдат подредени първо по идентификатор на родителската директория. По този начин, технически, задачата за получаване на съдържанието на папката се свежда до установяване на курсора в горната граница на групата ключове с определен префикс и последваща итерация до долната граница.

Горната граница може да бъде намерена "направо" чрез последователно търсене. За целта курсора се установява в началото на целия списък с ключове в базата данни и след това се увеличава, докато под него не се намери ключ с идентификатор на родителската директория. Този подход има два очевидни недостатъка:

1. Линейна сложност на търсенето, въпреки че, както е известно, в дърветата като цяло и в B-деревата в частност, то може да се извърши за логаритмично време.
2. Ненужно се повдигат от файла в основната памет всички страници, предхождащи търсената, което е изключително скъпо.

За щастие в API LMDB е предвиден ефективен начин за първоначално позициониране на курсора. За целта е необходимо да се състави такъв ключ, чиято стойност ще е очевидно по-малка или равна на ключа, намиращ се на горната граница на интервала. Например, за списъка в графиката по-горе, можем да направим такъв ключ, в който полето parentId ще бъде равно на 2, а всички останали попълнени с нули. Такъв частично попълнен ключ се подава на вход на функцията mdb_cursor_get с указание операция 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);

Ако горната граница на групата ключове е намерена, продължаваме да итерираме по нея, докато не срещнем или ключ с друг parentId, или ключовете напълно не свършат.

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​

Приятно, что с помощью mdb_cursor_get мы получаем не только ключ, но и значение. Если для выполнения условий выборки нужно проверить поля из value-части записи, они доступны без дополнительных действий.

4.3. Моделиране на връзките между таблиците

Към момента разгледахме всички аспекти на проектирането и работата с еднотаблична база данни. Можем да кажем, че таблицата е набор от подредени записи, състоящи се от еднотипни двойки ключ-стойност. Ако представим ключа като правоъгълник, а свързаната с него стойност като паралелепипед, получаваме визуална схема на базата данни.

​

Въпреки това, в реалния живот рядко успяваме да избегнем сложни ситуации. Често е необходимо в базата данни да имате няколко таблици и освен това да правите селекции в ред, различен от първичния ключ. Тази последна част е посветена на създаването и свързването им.

Индексни таблици

В облачното приложение има раздел „Галерия“. В него се показва медиаконтент от цялото облако, подреден по дата. За оптимално изпълнение на такава селекция до основната таблица трябва да добавим още една с нов тип ключове. В нея ще се съдържа поле с дата на създаване, което ще служи като основен критерий за сортиране. Тъй като новите ключове сочат към същите данни като ключовете в основната таблица, те се наричат индексни. На изображението по-долу те са подчертавани в оранжево.

За да разделим ключовете на различни таблици в рамките на една база данни, на всички тях е добавено допълнително техническо поле tableId. Като го направим най-приоритетно за сортиране, ще постигнем групиране на ключовете първо по таблици, а вътре - по свои правила.

Индексният ключ сочи същите данни, които и първичният. Пряката реализация на това свойство чрез асоциация с копие на value-частта на първичния ключ не е оптимална от няколко гледни точки.

1. От гледна точка на заетото място, тъй като метаданните могат да бъдат доста обширни.
2. От гледна точка на производителността, тъй като при обновяване на метаданните, възлите ще трябва да извършат запис на две ключа.
3. От гледна точка на поддръжката на кода, само ни е нужно да забравим да актуализираме данните за един от ключовете, за да получим трудноуловим бъг на неконсистентност на данните в хранилището.

Нека разгледаме как да премахнем тези недостатъци.

Организация на връзките между таблиците

За свързване на индексната таблица с основната, подходящ е шаблонът «ключ като стойност». Както подсказва името му, в ролята на стойност в индексния запис влиза копие на стойността на първичния ключ. Този подход неутрализира всички изброени по-горе недостатъци, свързани с съхраняването на копие на стойността на първоначалния запис. Единствената такса е, че за получаване на стойност по индексния ключ трябва да се направят 2 запитвания към базата данни вместо едно. Схематичната структура на получената база данни изглежда по следния начин.

Още един шаблон за организация на връзките между таблиците е «изобилна ключова стойност». Неговата същност е в добавянето на допълнителни атрибути към ключа, които не са нужни за сортиране, а за реконструиране на свързания ключ. В приложението Облака Mail.ru има реални примери за използването му, но за да избегнем дълбочинно потапяне в контекста на специфични iOS фреймворкове, ще дам измислен, но по-разбираем пример.

В облачните мобилни клиенти има страница, на която се изобразяват всички файлове и папки, до които потребителят е предоставил достъп на други хора. Тъй като такива файлове относително малко, а всякакъв вид свързана с тях специфична информация за публичността е много (кому е предоставен достъп, с какви права и т.н.), ще бъде нерационално да утежняваме стойността на записа в основната таблица. Въпреки това, ако решим да показваме такива файлове офлайн, все пак трябва да ги съхраняваме някъде. Естественият вариант на решението е да създадем отделна таблица за тях. На схемата по-долу, ключът ѝ има префикс «P», а плейсхолдера «propname» може да бъде заменен с по-конкретната стойност «публична информация».

Всички уникални метаданни, заради които беше създадена новата таблица, се извеждат във value-частта на записа. В същото време не желаем да дублираме данните за файловете и папките, които вече се съхраняват в основната таблица. Вместо това в ключа „P“ се добавят излишни данни под формата на полета „node ID“ и „timestamp“. Благодарение на тях можем да конструираме индексен ключ, по който да получим първичния ключ, с който накрая да получим метаданните на нодата.

Заключение

Оценяваме резултатите от внедряването на LMDB положително. След него броят на зависванията на приложението намаля с 30%.

Резултатите от извършената работа намериха отзвук извън екипа на iOS. В момента един от основните раздели „Файлове“ в приложението за Android също премина на използване на LMDB, а други части са на път. Езикът C, на който е реализирано key-value хранилището, се оказа добро предимство, за да създадем приложен обвивка около него кросплатформено на езика C++. За безшевно свързване на получената C++ библиотека с платформения код на Objective-C и Kotlin беше използван кодогенератор. Djinni от Dropbox, но това е съвсем друга история.

Източник: habr.com