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

Съдържание

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

1. Мотивация за изпълнение

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

Резултатите от измерването се превърнаха в студен душ за нас. Оказа се, че проблемите, причинени от замръзването, са много повече от всички други. Ако преди осъзнаването на този факт основният технически индикатор за качество беше безавариен, то след фокуса изместен без замразяване.

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

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

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

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

Така че, ако си представите git, който при изпълнение на команда за изтегляне, вместо да прилага пачове към локална моментна снимка, сравнява пълното си състояние с пълното сървърно, тогава ще имате доста точна представа за това как се синхронизира възниква в облачни клиенти. Лесно е да се досетите, че за изпълнението му е необходимо да се разпределят две DOM дървета в паметта с мета-информация за всички сървърни и локални файлове. Оказва се, че ако потребителят съхранява 500 хиляди файла в облака, за да го синхронизира, е необходимо да пресъздаде и унищожи две дървета с 1 милион възли. Но всеки възел е съвкупност, съдържаща графика на подобекти. В тази светлина резултатите от профилирането бяха очаквани. Оказа се, че дори и без да се вземе предвид алгоритъма за сливане, самата процедура за създаване и след това унищожаване на огромен брой малки обекти струва доста пари.Ситуацията се утежнява от факта, че основната операция за синхронизация е включена в голям брой на потребителски скриптове. В резултат на това фиксираме втория важен критерий при избора на база данни - възможността за изпълнение на CRUD операции без динамично разпределение на обекти.

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

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

С този набор от изисквания SQLite беше и все още е добър избор. Въпреки това, като част от проучването на алтернативите, попаднах на една книга „Първи стъпки с LevelDB“. Под нейно ръководство е написан бенчмарк, който сравнява скоростта на работа с различни бази данни в реални облачни сценарии. Резултатът надмина и най-смелите очаквания. В най-популярните случаи - получаване на курсор върху сортиран списък с всички файлове и сортиран списък с всички файлове за дадена директория - LMDB се оказа 10 пъти по-бърз от SQLite. Изборът стана очевиден.

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

LMDB е библиотека, много малка (само 10K реда), която реализира най-ниския фундаментален слой от бази данни - съхранение.

Диаграмата по-горе показва, че сравняването на LMDB с SQLite, който прилага още по-високи нива, обикновено не е по-правилно от SQLite с Core Data. Би било по-справедливо да цитираме едни и същи машини за съхранение като равностойни конкуренти - BerkeleyDB, LevelDB, Sophia, RocksDB и т.н. Има дори разработки, при които LMDB действа като компонент на машина за съхранение за SQLite. Първият подобен експеримент през 2012г изразходвани от LMDB Хауърд Чу. резултати се оказа толкова интригуващ, че инициативата му беше подета от ентусиасти на OSS и намери своето продължение в лицето на LumoSQL. През януари 2020 г. автор на този проект е Den Shearer представени на LinuxConfAu.

Основната употреба на LMDB е като двигател за бази данни на приложения. Библиотеката дължи появата си на разработчиците OpenLDAP, които бяха силно недоволни от BerkeleyDB като основа на техния проект. Отблъскване от скромната библиотека btree, Хауърд Чу успя да създаде една от най-популярните алтернативи на нашето време. Той посвети своя много готин доклад на тази история, както и на вътрешната структура на LMDB „Базата данни с карта на светкавичната памет“. Леонид Юриев (известен още като yleo) от Positive Technologies в неговата реч на Highload 2015 „LMDB двигателят е специален шампион“. В него той говори за LMDB в контекста на подобна задача за внедряване на ReOpenLDAP, а LevelDB вече е претърпял сравнителна критика. В резултат на внедряването Positive Technologies дори получи активно развиваща се вилица MDBX с много вкусни функции, оптимизации и изчистване на бъгове.

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

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

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

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

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

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

3.1. Кит №1. Картирани в памет файлове

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

1. Поддържането на последователността на данните в хранилището при работа с тях от няколко процеса става отговорност на операционната система. В следващия раздел тази механика е разгледана подробно и със снимки.
2. Липсата на кешове напълно освобождава LMDB от режийните разходи, свързани с динамичните разпределения. Четенето на данни на практика е настройка на показалеца на правилния адрес във виртуалната памет и нищо повече. Звучи като фантазия, но в източника на хранилището всички извиквания на calloc са концентрирани във функцията за конфигуриране на хранилището.
3. Липсата на кешове също означава липса на ключалки, свързани със синхронизацията за достъп до тях. Четящите устройства, от които може да съществува произволен брой едновременно, не срещат нито един мютекс по пътя си към данните. Благодарение на това скоростта на четене има идеална линейна мащабируемост по отношение на броя на процесорите. В LMDB се синхронизират само операции за модифициране. Може да има само един писател в даден момент.
4. Минимум логика за кеширане и синхронизация предпазва кода от изключително сложен тип грешки, свързани с работата в многонишкова среда. На конференцията на Usenix OSDI 2014 имаше две интересни проучвания на бази данни: „Всички файлови системи не са създадени еднакви: относно сложността на изработването на съвместими със срив приложения“ и Измъчване на бази данни за забавление и печалба. От тях можете да получите информация както за безпрецедентната надеждност на LMDB, така и за почти безупречното изпълнение на ACID свойствата на транзакциите, което го надминава в същия SQLite.
5. Минимализмът на LMDB позволява машинното представяне на неговия код да бъде изцяло поставено в L1 кеша на процесора с произтичащите от това скоростни характеристики.

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

Обща информация за картографирани в памет файлове

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

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

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

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

С картираните в паметта файлове историята е абсолютно същата. Логично, те се предполага, че непрекъснато и изцяло са разположени във виртуалното адресно пространство. Те обаче влизат във физическата памет страница по страница и само при поискване. Промяната на такива страници се синхронизира с файла на диска. По този начин можете да извършвате файлов I / O, просто работейки с байтове в паметта - всички промени ще бъдат автоматично прехвърлени от ядрото на операционната система към оригиналния файл.​
â € <
Изображението по-долу демонстрира как LMDB синхронизира състоянието си, когато работи с базата данни от различни процеси. Чрез картографиране на виртуалната памет на различни процеси върху един и същ файл, ние де факто задължаваме операционната система да синхронизира преходно определени блокове от техните адресни пространства един с друг, което е мястото, където изглежда LMDB.
â € <

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

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

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

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

През 2018 г. имаше прекрасен доклад на WWDC Дълбоко гмуркане в паметта на iOS. Той разказва, че в iOS всички страници, разположени във физическата памет, принадлежат към един от 3 вида: мръсни, компресирани и чисти.

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

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

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

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

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

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

3.2. Кит №2. B+-дърво

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

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

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

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

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

По този начин:

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

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

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

Физически възлите са блокове памет с предварително определена дължина. Размерът им е кратен на размера на страниците с памет в операционната система, за които говорихме по-горе. Структурата на възела е показана по-долу. Заглавката съдържа мета-информация, най-очевидната от която например е контролната сума. Следва информация за отместванията, по които са разположени клетките с данни. Ролята на данните може да бъде или ключове, ако говорим за навигационни възли, или цели двойки ключ-стойност в случай на листа Можете да прочетете повече за структурата на страниците в работата „Оценка на магазини за ключ-стойност с висока производителност“.

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

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

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

3.3. Кит #3. копиране при запис

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

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

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

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

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

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

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

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

4. Проектиране на схема за данни върху API за ключ-стойност

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

Бележка относно списъците с кодове

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

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

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

Заобикаляща среда

Структура 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 Cloud променихме стойностите по подразбиране само за два параметъра.

Първият е размерът на виртуалното адресно пространство, към което е нанесен файлът за съхранение. За съжаление, дори на едно и също устройство, конкретната стойност може да варира значително от изпълнение на изпълнение. За да вземем предвид тази функция на iOS, ние избираме динамично максималния размер на паметта. Започвайки от определена стойност, тя последователно се разполовява до функцията mdb_env_open няма да върне резултат, различен от ENOMEM. На теория има обратен начин - първо заделяйте минимум памет на двигателя и след това, когато се получат грешки MDB_MAP_FULL, увеличете го. Той обаче е много по-трънлив. Причината е, че процедурата за пренасочване на паметта с помощта на функцията mdb_env_set_map_size обезсилва всички обекти (курсори, транзакции, ключове и стойности), получени от двигателя по-рано. Отчитането на такъв обрат на събитията в кода ще доведе до значителното му усложняване. Ако все пак виртуалната памет е много скъпа за вас, тогава това може да е причина да погледнете вилицата, която е отишла далеч напред. MDBX, където сред декларираните функции има „автоматично регулиране на размера на базата данни в движение“.

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

Данни на Guide-Bulgaria.com

Базата данни е отделен екземпляр на 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. Използвайки това свойство, можете лесно и естествено да коригирате скоростта на актуализиране на източника на данни за екранни формуляри въз основа на съображения за потребителско изживяване. Например, нека вземем такава функция на приложението Mail.ru Cloud като автоматично зареждане на съдържание от системната медийна галерия. При добра връзка клиентът може да добавя няколко снимки в секунда към сървъра. Ако актуализирате след всяко изтегляне UICollectionView с медийно съдържание в облака на потребителя можете да забравите за 60 fps и плавно превъртане по време на този процес. За да предотвратите честите актуализации на екрана, трябва по някакъв начин да ограничите скоростта на промяна на данните в базата UICollectionViewDataSource.

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

Multiversioning 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 целочислените променливи се съхраняват във формат Малкият Ендиан. Това означава, че най-малко значимият байт ще бъде отляво и няма да можете да сортирате цели числа, като използвате тяхното сравнение байт по байт. Например, опитът да направите това с набор от числа от 0 до 511 ще доведе до следния резултат.

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

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

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

Второто нещо, което трябва да имате предвид е принципи на подравняване компилатор на struct поле. Поради тях байтове с боклук стойности могат да се формират в паметта между полетата, което, разбира се, нарушава сортирането на байтове. За да премахнете боклука, трябва или да декларирате полетата в строго определен ред, като имате предвид правилата за подравняване, или да използвате атрибута в декларацията на структурата 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 работи изключително интензивно. Те се сравняват помежду си в рамките на всяка операция на приложението, а производителността на цялото решение зависи от скоростта на компаратора. В един идеален свят двоичният компаратор по подразбиране трябва да е достатъчен за сравняване на ключове, но ако наистина трябва да използвате свой собствен, тогава процедурата за десериализация на ключове в него трябва да бъде възможно най-бърза.

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

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

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

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

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-дървото, на което се намира обектът, благодарение на принципа на копиране при запис, остават непроменени, докато поне една транзакция се отнася до тях. В същото време, веднага след като последната транзакция, свързана с тях, бъде завършена, страниците могат да бъдат използвани повторно за нови данни. Ако е необходимо обектите да оцелеят след транзакцията, която ги е създала, те все още трябва да бъдат копирани.
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 така че те първо да бъдат подредени по ID на тяхната родителска директория. По този начин технически задачата за получаване на съдържанието на папка се свежда до поставяне на курсора върху горната граница на група ключове с даден префикс, последвано от итерация до долната граница.

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

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, получаваме не само ключа, но и стойността. Ако, за да изпълните условията за избор, е необходимо да проверите, наред с други неща, полетата от стойностната част на записа, тогава те са напълно достъпни за себе си без допълнителни жестове.

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

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

â € <

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

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

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

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

Индексният ключ се отнася до същите данни като първичния ключ. Директното внедряване на това свойство чрез свързване с него на копие на стойностната част на първичния ключ е неоптимално от няколко гледни точки едновременно:

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

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

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

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

Друг модел за организиране на връзки между таблици е "излишен ключ". Същността му е да добави допълнителни атрибути към ключа, които са необходими не за сортиране, а за пресъздаване на свързания ключ.Има обаче реални примери за използването му в приложението Mail.ru Cloud, за да се избегне дълбокото гмуркане в в контекста на специфични iOS рамки, ще дам един измислен, но по-разбираем пример.

Облачните мобилни клиенти имат страница, която показва всички файлове и папки, които потребителят е споделил с други хора. Тъй като има сравнително малко такива файлове и има много конкретна информация относно публичността, свързана с тях (на кого е предоставен достъп, с какви права и т.н.), няма да е рационално да ги натоварваме със стойностната част на записът в главната таблица. Ако обаче искате да показвате такива файлове офлайн, все пак трябва да ги съхранявате някъде. Естествено решение е да се създаде отделна маса за него. В диаграмата по-долу нейният ключ е с префикс "P", а контейнерът "propname" може да бъде заменен с по-конкретната стойност "public info".​

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

Заключение

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

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

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