Восени 2019 року в iOS команді Хмари Mail.ru відбулася довгоочікувана подія. Основною базою даних для персистентного зберігання стану програми стала дуже екзотична для мобільного світу Lightning Memory-Mapped Database (LMDB). Під катом до вашої уваги пропонується її докладний огляд у чотирьох частинах. Спочатку поговоримо про причини такого нетривіального та важкого вибору. Потім перейдемо до розгляду трьох китів у основі архітектури LMDB: відображені у пам'ять файли, B+-дерево, copy-on-write підхід реалізації транзакционности і мультиверсионности. Зрештою, на солодке – практична частина. У ній розглянемо, як поверх низькорівневого key-value API спроектувати та реалізувати схему бази з декількома таблицями, включаючи індексну.

Зміст

Мотивація застосування
Позиціонування LMDB
Три кити LMDB
3.1. Кіт №1. Memory-mapped files
3.2. Кіт №2. B+-дерево
3.3. Кіт №3. Copy-on-write
Проектування схеми даних поверх key-value API
4.1. Базові абстракції
4.2. Моделювання таблиць
4.3. Моделювання зв'язків між таблицями

1. Мотивація застосування

Одного року так у 2015 ми перейнялися зняттям метрики, як часто інтерфейс нашої програми кладе. Зайнялися ми цим не так. У нас почастішали скарги на те, що іноді програма перестає реагувати на дії користувача: кнопки не натискаються, списки не скроляться і т.п. Про механіку вимірювань я розповідав на AvitoTech, тому тут наводжу лише порядок цифр.

Результати вимірів стали для нас холодним душем. Виявилося, що проблем, спричинених зависаннями, набагато більше, ніж будь-яких інших. Якщо до розуміння цього факту головним технічним показником якості був crash free, то після фокусу змістився на freeze free.

Побудувавши дашборд із зависаннями і провівши кількісний и якісний аналіз їх причин, став зрозумілим головний ворог - важка бізнес-логіка, що виконується в головному потоці програми. Природною реакцією на це неподобство стало пекуче бажання розпихати її по робочих потоках. Для системного вирішення цього завдання ми вдалися до багатопоточної архітектури на основі легковажних акторів. Її адаптації для світу iOS я присвятив дві тредики у колективному твіттері та статтю на Хабрі. У рамках поточної розповіді хочу підкреслити ті аспекти рішення, які вплинули на вибір бази даних.

‚Акторна модель організації системи передбачає, що багатопоточність стає її другою суттю. Об'єкти моделі у ній люблять перетинати межі потоків. І роблять вони це не іноді і подекуди, а завжди і скрізь.

База даних є одним з наріжних компонентів на представленій схемі. Її основним завданням є реалізація макропатерну. Спільна база даних. Якщо в ентерпрайзному світі з його допомогою організовують синхронізацію даних між сервісами, то у разі акторної архітектури дані між потоками. Таким чином, нам знадобилася така база даних, робота з якою в багатопотоковому середовищі не викликає навіть мінімальних складнощів. Зокрема, це означає, що отримані з неї об'єкти мають бути як мінімум потокобезпечними, а в ідеалі зовсім немутабельними. Як відомо, останні можна використовувати одночасно з декількох потоків, не вдаючись до будь-яких блокувань, що сприятливо позначається на продуктивності.

Другим значущим фактором, що вплинув на вибір бази даних, стало наше хмарне API. Воно було надихнуто підходом до синхронізації, прийнятої на озброєння у git. Як і він ми цілилися у offline-first API, Яке для хмарних клієнтів виглядає більш ніж доречно. Передбачалося, що вони лише одного разу викачуватимуть повний стан хмари, а потім синхронізація у переважній кількості випадків відбуватиметься через накочування змін. На жаль, ця можливість все ще знаходиться лише в теоретичній зоні, а на практиці працювати з патчами клієнти так і не навчилися. Тому є низка об'єктивних причин, які, щоб не затягувати вступ, залишимо за дужками. Зараз набагато більший інтерес представляють повчальні підсумки уроку про те, що відбувається коли API сказало «А», а його споживач не сказав «Б».

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

Інші вимоги більш традиційні та їх список цілком виглядає так.

Потокобезпека.
Мультипроцесність. Продиктована бажанням використовувати один і той же інстанс бази даних для синхронізації стану не тільки між потоками, а й між основною програмою та екстеншенами iOS.
Можливість представляти сутності, що зберігаються у вигляді немутабельних об'єктів.
Відсутність динамічних алокацій у межах операцій CRUD.
Підтримка транзакціями базових властивостей ACID: атомарність, консистентність, ізольованість та надійність.
Швидкість на найпопулярніших кейсах.

Хорошим вибором із таким набором вимог був і залишається SQLite. Однак у рамках вивчення альтернатив, мені під руку потрапила книжка "Getting Started with LevelDB". Під її керівництвом було написано бенчмарк, який порівнює швидкість роботи з різними базами даних у рамках реальних хмарних сценаріїв. Результат перевершив найсміливіші очікування. На найпопулярніших кейсах - отримання курсору на сортований список всіх файлів і сортований список всіх файлів для заданої директорії - LMDB виявилася швидше SQLite у 10 разів. Вибір став очевидним.

2. Позиціонування LMDB

LMDB - це бібліотечка, дуже невелика (всього 10К рядків), що реалізує нижній основний шар баз даних - сховище.

Наведена схема показує, що порівнювати LMDB з SQLite, який реалізує ще й вищі рівні, загалом не коректніше, ніж SQLite з Core Data. Як рівноправних конкурентів буде більш справедливим наводити такі ж двигуни-сховища - BerkeleyDB, LevelDB, Sophia, RocksDB та ін Є навіть розробки, де LMDB виступає як компонент storage engine для SQLite. Першим такий експеримент у 2012 році провів автор LMDB Howard Chu. Результати виявилися настільки інтригуючими, що його починання було підхоплено ентузіастами OSS і знайшло своє продовження в особі LumoSQL. У січні 2020 року автор цього проекту Den Shearer презентував його на LinuxConfAu.

Головне застосування LMDB знаходить як двигун для прикладних баз даних. Своєю появою бібліотека зобов'язана розробникам OpenLDAP, які були сильно не задоволені BerkeleyDB як основа свого проекту. Відштовхнувшись від скромної бібліотечки btree, Howard Chu зміг створити одну з найпопулярніших у наш час альтернатив. Цій історії і внутрішньому пристрої LMDB він присвятив свою дуже круту доповідь "Lightning Memory-mapped Database". Хорошим прикладом підкорення сховища поділився Леонід Юр'єв (aka yleo) з Positive Technologies у своїй доповіді на Highload 2015 "Рух LMDB - особливий чемпіон". У ньому він розповідає про LMDB у контексті схожого завдання реалізації ReOpenLDAP, а порівняльну критику зазнала вже LevelDB. За підсумками впровадження у Positive Technologies навіть з'явився форк, що активно розвивається. MDBX з дуже смачними фічами, оптимізаціями та багфіксами.

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

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

LMDB успішно бореться за місце під сонцем у ніші, залишеній BerkeleyDB після переходу під контроль Oracle. Бібліотеку люблять за швидкість та надійність навіть у порівнянні з собі подібними. Як відомо, безкоштовних обідів не буває, і хочеться наголосити на trade-off, з яким доведеться зіткнутися при виборі між LMDB і SQLite. Схема вище наочно демонструє, рахунок чого досягається підвищена швидкість. По-перше, ми не платимо за додаткові шари абстракції поверх дискового сховища. Зрозуміло, у хорошій архітектурі без них все одно не обійтися, і вони неминуче з'являться в коді програми, однак вони будуть набагато тоншими. У них не буде фіч, які не потрібні конкретним додатком, наприклад, підтримки запитів на мові SQL. По-друге, з'являється можливість оптимально реалізувати мапінг прикладних операцій на запити дискового сховища. Якщо SQLite у своїй роботі виходить із середньостатистичних потреб середньостатистичного застосування, то ви як прикладний розробник чудово обізнані про основні сценарії навантаження. За більш продуктивне рішення доведеться заплатити зрослим цінником як розробку початкового рішення, і його подальшу підтримку.

3. Три кити LMDB

Подивившись на LMDB з висоти пташиного польоту, настав час спускатися глибше. Наступні три розділи будуть присвячені розбору основних китів, на яких лежить архітектура сховища:

Відображені в пам'ять файли як механізм роботи з диском та синхронізація внутрішніх структур даних.
B+-дерево як організація структури даних, що зберігаються.
Copy-on-write як підхід для забезпечення ACID-властивостей транзакцій та мультиверсійності.

3.1. Кіт №1. Memory-mapped files

Файли, що відображаються в пам'ять, — настільки важливий архітектурний елемент, що вони навіть фігурують у назві сховища. Питання кешування і синхронізації доступу до інформації цілком і повністю віддані на відкуп операційній системі. LMDB не містить у собі будь-яких кешів. Це усвідомлене рішення автора, оскільки читання даних безпосередньо з відображених файлів дозволяє зрізати безліч кутів у реалізації движка. Нижче наводжу далеко не повний перелік деяких із них.

Підтримка консистентності даних у сховищі під час роботи з ним із кількох процесів стає обов'язком операційної системи. У наступному розділі дана механіка розглянута у подробицях та з картинками.
Відсутність кешів повністю позбавляє LMDB від накладних витрат, пов'язаних із динамічними аллокаціями. Читання даних на практиці являє собою встановлення вказівника на правильну адресу у віртуальній пам'яті і не більше. Звучить як фантастика, але у вихідних записах сховища всі виклики сalloc зосереджені у функції конфігурування сховища.
Відсутність кешів означає відсутність блокувань, пов'язаних із синхронізацією до їх доступу. Читачі, яких одночасно може існувати довільна кількість, не зустрічають на своєму шляху до даних жодного м'ютексу. За рахунок цього швидкість читання має ідеальну лінійну масштабованість за кількістю CPU. У LMDB синхронізації піддаються лише модифікуючі операції. Письменник у кожний момент часу може бути лише один.
Мінімум логіки кешування та синхронізації позбавляє код вкрай складного виду помилок, пов'язаних з роботою в багатопотоковому середовищі. На конференції Usenix OSDI 2014 було два цікаві дослідження баз даних: «Всі файли системи не створені еквівалентно: на комплексності з crash-consistent Applications» и Torturing Databases for Fun and Profit. З них можна отримати інформацію як про безпрецедентну надійність LMDB, так і про практично бездоганну реалізацію ACID-властивостей транзакцій, що перевершує її в тому ж SQLite.
Мінімалістичність LMDB дозволяє машинному представленню її коду повністю розміщуватися в L1-кеші процесора з швидкісними характеристиками, що звідси випливають.

На жаль, в iOS з файлами, що відображаються в пам'ять, все не так безхмарно, як хотілося б. Щоб поговорити про пов'язані з ними недоліки більш свідомо, необхідно згадати загальні принципи реалізації цього механізму операційних системах.

Загальні відомості про файли, що відображаються в пам'ять

З кожним додатком, що виконується, операційна система асоціює сутність під назвою процес. Кожному процесу виділяється безперервний інтервал адрес, у якому він розміщує все необхідне йому до роботи. У найнижчих адресах розташовуються секції з кодом та захардшкіреними даними та ресурсами. Далі йде блок динамічного адресного простору, що росте вгору, добре відомий нам під ім'ям heap. У ньому містяться адреси сутностей, які у процесі роботи програми. Вгорі розташовується область пам'яті, що використовується стеком програми. Він то росте, то стискається, тобто його розмір також має динамічну природу. Щоб стек і heap не штовхалися і не заважали один одному, вони розведені по різних кінцях адресного простору. Адреси в цій серединній ділянці операційна система використовує для асоціації з процесом різних сутностей. Зокрема, вона може поставити у відповідність комусь безперервному набору адрес - файл на диску. Такий файл називається відображеним у пам'ять.

Виділене процесу адресний простір величезний. Теоретично кількість адрес обмежена лише розміром покажчика, що визначається бітністю системи. Якби йому 1-в-1 була зіставлена фізична пам'ять, то перший же процес зжер би всю оперативу, і ні про яку багатозадачність не могло б йти й мови.

Однак зі свого досвіду ми знаємо, що сучасні операційні системи можуть одночасно виконувати скільки завгодно багато процесів. Це можливо завдяки тому, що вони тільки на папері виділяють процесам купу пам'яті, а насправді завантажують в основну фізичну пам'ять тільки ту частину, яка потрібна тут і зараз. Тому проасоційована із процесом пам'ять називається віртуальною.

Операційна система організує віртуальну та фізичну пам'ять у вигляді сторінок певного розміру. Як тільки якась сторінка віртуальної пам'яті виявилася затребуваною, операційна система завантажує її у фізичну пам'ять і проставляє між ними відповідність у спеціальній таблиці. Якщо вільні слоти відсутні, одна з раніше завантажених сторінок копіюється на диск, а затребувана встає її місце. Ця процедура, до якої ми невдовзі повернемося, називається свопінгом (swapping). Рисунок нижче ілюструє описаний процес. На ньому сторінка А з адресою 0 була завантажена та розміщена на сторінці основної пам'яті з адресою 4. Цей факт знайшов своє відображення у таблиці відповідностей у комірці номер 0.

З відображеними в пам'ять файлами історія така сама. Логічно вони нібито безперервно і повністю розміщуються у віртуальному адресному просторі. Однак у фізичну пам'ять вони потрапляють посторінково і лише на вимогу. Модифікація таких сторінок синхронізується із файлом на диску. Таким чином можна виконувати файлове введення/виведення, просто працюючи з байтами в пам'яті, - всі зміни будуть автоматично перенесені ядром операційної системи до вихідного файлу.

Нижче показано, як LMDB синхронізує свій стан при роботі з базою даних з різних процесів. Замапуючи віртуальну пам'ять різних процесів на той самий файл, де-факто ми зобов'язуємо операційну систему транзитивно синхронізувати між собою певні блоки їх адресних просторів, куди і дивиться LMDB.

Важливий аспект полягає в тому, що LMDB за замовчуванням модифікує файл з даними через механізм системного виклику write, а сам файл відображає в режимі read-only. Такий підхід має два важливі наслідки.

Перше слідство — загальне всім операційних систем. Його суть полягає у додаванні захисту від ненавмисного пошкодження бази даних некоректним кодом. Як відомо, інструкції процесу, що виконуються, вільні звертатися до даних з будь-якого місця його адресного простору. У той же час, як ми тільки-но згадали, відображення файлу в режимі read-write означає, що будь-яка інструкція може його ще й модифікувати. Якщо вона зробить це помилково, намагаючись, наприклад, насправді перезаписати елемент масиву за неіснуючим індексом, то таким чином вона може випадково змінити замалений на цю адресу файл, що призведе до псування бази даних. Якщо файл відображено в режимі read-only, то спроба змінити відповідний йому адресний простір призведе до аварійного завершення програми з сигналом. SIGSEGVі файл залишиться в цілісності.

Друге слідство вже специфічне для iOS. Ні автор, ні будь-які інші джерела про нього явно не згадують, але без нього LMDB була б непридатна для роботи в цій мобільній операційній системі. Його розгляду присвячено наступний розділ.

Специфіка відображених у пам'ять файлів у iOS

У 2018 році на WWDC була чудова доповідь "iOS Memory Deep Dive". У ньому розповідається, що в iOS всі сторінки, розташовані у фізичній пам'яті, відносяться до одного з трьох типів: dirty, compressed і clean.

Clean memory – це сукупність сторінок, які можуть бути безболісно вивантажені із фізичної пам'яті. Дані, що знаходяться в них, можна за необхідності завантажити заново з їх початкових джерел. Read-only memory-mapped файли потрапляють саме до цієї категорії. iOS не боїться будь-якої миті вивантажувати відображені на файл сторінки з пам'яті, оскільки вони гарантовано синхронізовані з файлом на диску.

У dirty memory потрапляють усі модифіковані сторінки, де вони спочатку не розташовувалися. Зокрема, так буде класифіковано і memory-mapped файли, змінені через запис в проасоційовану з ними віртуальну пам'ять. Відкривши LMDB з прапором MDB_WRITEMAP, після внесення змін до цього можна переконатися особисто.

Як тільки додаток починає займати занадто багато фізичної пам'яті, iOS піддає його dirty станиці компресії. Сукупність пам'яті, що займається dirty і compressed сторінками, становить так званий memory footprint програми. Після досягнення ним певного порогового значення, за процесом приходить системний демон OOM killer і примусово його завершує. У цьому полягає особливість iOS у порівнянні з десктопними операційними системами. На відміну від них зниження memory footprint за допомогою свопінгу сторінок з фізичної пам'яті на диск в iOS не передбачено. Про причини можна лише гадати. Можливо процедура інтенсивного переміщення сторінок на диск і назад занадто енерговитратна для мобільних пристроїв або 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 далеко ще не єдина, хто претендує на memory-mapped пам'ять. Хороші шматки від'їдають системні алокатори, файли з ресурсами, фреймворки для роботи із зображеннями та інші дрібніші хижаки.

За підсумками експериментів в Хмарі ми прийшли до наступних компромісних значень LMDB пам'яті, що виділяється: 384 мегабайт для 32-бітних пристроїв і 768 - для 64-бітних. Після використання цього обсягу будь-які модифікуючі операції починають завершуватися з кодом MDB_MAP_FULL. Такі помилки ми спостерігаємо в нашому моніторингу, але їх досить мало, щоб на даному етапі їх можна було знехтувати.

Неочевидною причиною надмірного споживання пам'яті сховищем можуть стати довготривалі транзакції. Для розуміння, як пов'язані ці два явища, нам допоможе розгляд двох китів LMDB, що залишилися.

3.2. Кіт №2. B+-дерево

Для емулювання таблиць поверх key-value сховища необхідно, щоб у його API були присутні наступні операції:

Вставте новий елемент.
Пошук елемента із заданим ключем.
Видалення елемента.
Ітерування за інтервалами ключів у порядку їх сортування.

Найпростішою структурою даних, за допомогою якої легко реалізувати всі чотири операції, є бінарне дерево пошуку. Кожен його вузол є ключем, що ділить все підмножина дочірніх ключів на два піддерева. У лівому зібрані ті, які менші від батьківського, а у правому — які більші. Отримання впорядкованого набору ключів досягається рахунок одного з класичних обходів дерева.

У бінарних дерев є два фундаментальні недоліки, які не дозволяють їм бути ефективними як дискова структура даних. По-перше, ступінь їхньої збалансованості непередбачувана. Є чималий ризик отримати дерева, в яких висота різних гілок може сильно відрізнятися, що значно погіршує алгоритмічну складність пошуку порівняно з очікуваною. По-друге, велика кількість крос-посилань між вузлами позбавляє бінарні дерева локальності в пам'яті. Близькі вузли (з точки зору зв'язків між ними) можуть знаходитися на різних сторінках у віртуальній пам'яті. Як наслідок, навіть для простого обходу кількох сусідніх вузлів у дереві може знадобитися відвідати порівнянну кількість сторінок. Це є проблемою навіть коли ми розмірковуємо про ефективність бінарних дерев як in-memory структури даних, оскільки постійна ротація сторінок у кеші процесора – недешеве задоволення. Коли ж мова заходить про часте підняття пов'язаних з вузлами сторінок з диска, то стан справ стає зовсім вже плачевним.

B-дерева, будучи еволюцією бінарних дерев, вирішують зазначені у попередньому абзаці проблеми. По-перше, вони самобалансуються. По-друге, кожен їх вузол розбиває безліч дочірніх ключів не так на 2, але в M впорядкованих підмножин, причому число M може бути досить великим, близько кількох сотень, або навіть тисяч.

За рахунок цього:

У кожному вузлі є велика кількість вже впорядкованих ключів і дерева виходять дуже низькими.
Дерево набуває властивість локальності розміщення в пам'яті, оскільки близькі за значенням ключі природно розташовуються поруч один з одним на одному або сусідніх вузлах.
Зменшується кількість транзитних вузлів під час спуску деревом під час операції пошуку.
Зменшується кількість зчитуваних цільових вузлів при range-запитах, оскільки в кожному з них міститься велика кількість впорядкованих ключів.

У LMDB для зберігання даних використовується одна з варіацій B-дерева під назвою B+-дерево. На схемі вище зображено три типи вузлів, які в ньому бувають:

На вершині розташований корінь (root). Він матеріалізує собою що інше, як концепцію бази даних усередині сховища. Всередині одного інстансу LMDB можна створювати кілька баз даних, які розділяють між собою замаплене віртуальне адресний простір. Кожна з них починається зі свого власного кореня.
На самому нижньому рівні знаходиться листя (leaf). Саме вони і тільки вони містять пари ключ-значення, що зберігаються в базі даних. До речі, в цьому полягає особливість B+-дерев. Якщо звичайне B-дерево зберігає value-частини у вузлах всіх рівнів, то B+-варіація лише на нижньому. Зафіксувавши цей факт, далі називатимемо підтип дерева, що використовується в LMDB, просто B-деревом.
Між коренем та листям розміщується 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 необхідності вести write ahead log для підтримки консистентності даних. Де-факто структура зберігання даних на диску, описана вище, одночасно бере на себе та його функцію. Відсутність лога транзакцій у явному вигляді - одна з фішок LMDB, що забезпечує високу швидкість читання даних.

Конструкція під назвою append-only B-tree, що вийшла, природним чином забезпечує ізоляцію транзакцій і мультиверсійність. У LMDB з кожною відкритою транзакцією асоціюється актуальний корінь дерева. Доки транзакція не завершена, сторінки пов'язаного з нею дерева ніколи не будуть змінені або повторно використані під нові версії даних. якщо сховище у цей час продовжує активно оновлюватись. У цьому полягає суть мультиверсійності, що робить LMDB ідеальним джерелом даних всіма нами коханого UICollectionView. Відкривши транзакцію, не потрібно підвищувати memory footprint програми, спішно викачуючи актуальні дані в яку-небудь in-memory структуру, боячись залишитися біля розбитого корита. Ця особливість вигідно відрізняє LMDB від того ж SQLite, який такою тотальною ізоляцією похвалитися не може. Відкривши в останньому дві транзакції і видаливши якийсь запис в рамках однієї з них, цей же запис вже не вийде отримати і в рамках другої, що залишилася.

Зворотною стороною медалі є потенційно значно більша витрата віртуальної пам'яті. На слайді зображено, як виглядатиме структура бази даних, якщо відбувається її модифікація одночасно з 3 відкритими транзакціями на читання, що дивляться різні версії бази даних. Оскільки LMDB не може повторно використовувати вузли, досяжні з коренів, пов'язаних з актуальними транзакціями, сховищу не залишається нічого іншого, окрім як розмістити в пам'яті ще один четвертий корінь і в черговий раз розхиляти під ним сторінки, що модифікуються.

Тут не зайвим буде згадати розділ про memory-mapped файли. Начебто додаткова витрата віртуальної пам'яті не повинна нас сильно турбувати, оскільки вона не робить вкладу в memory footprint програми. Однак в той же час було відзначено, що iOS дуже скупа на її виділення, і ми не можемо як на сервері або десктопі з панського плеча надати LMDB регіон в один терабайт і не думати про цю особливість зовсім. По можливості потрібно намагатися робити час життя транзакцій якомога коротшим.

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 інвалідує всі сутності (курсори, транзакції, ключі та значення), отримані від движка раніше. Облік такого повороту подій у коді призведе до його суттєвого ускладнення. Якщо, тим не менш, віртуальна пам'ять вам дуже дорога, то це може бути приводом придивитися до форка, що пішов далеко вперед. 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;

За допомогою компаратора сховище впорядковує ключі зростання. Якщо не замінити його власним, то використовуватиметься дефолтний, який сортує їх побайтово у лексикографічному порядку.

Транзакції

Пристрій транзакцій докладно описано в попередньому розділітому коротким рядком повторю їх основні властивості:

Підтримка всіх базових властивостей ACID: атомарність, консистентність, ізольованість та надійність. Не можу не відзначити, що в частині тривалості на macOS та iOS є баг, виправлений у MDBX. Детальніше можна почитати в них README.
Підхід до багатопоточності описується схемою "single writer / multiple readers". Письменники блокують одне одного, але не блокують читачів. Читачі не блокують ані письменників, ані один одного.
Підтримка вкладених транзакцій.
Підтримка мультиверсії.

Мультиверсійність у 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. Моделювання таблиць

Властивість упорядкованості ключів дозволяє конструювати поверх базових абстракцій таку високорівневу як таблиця. Розглянемо цей процес на прикладі основної таблиці хмарного клієнта, в якій закешована інформація про всі файли та папки користувача.

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

Одним із частих сценаріїв, під який має бути заточена структура таблиці з деревом папок - вибірка всіх елементів, розташованих усередині заданої директорії. Хорошою моделлю організації даних для ефективних запитів такого роду є Список суміжності. Для втілення поверх key-value сховища необхідно відсортувати ключі файлів і папок таким чином, щоб вони групувалися на підставі приналежності до батьківської директорії. Крім того, щоб відображати вміст директорії у звичному користувачеві 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 для двобайтових чисел із прикладу).

Формат подання рядків у програмуванні - це, як відомо, ціла історія. Якщо семантика рядків і використовувана їхнього уявлення у пам'яті кодування передбачає, що у символ може припадає більше одного байта, то ідеї використання дефолтного компаратора краще відразу відмовитися.

Друге, що треба пам'ятати принципи вирівнювання компілятор полів структури. Через них у пам'яті між полями можуть утворюватися байти зі сміттєвими значеннями, що, звичайно ж, ламає побайтове сортування. Для ліквідації сміття потрібно або оголошувати поля у строго визначеному порядку, тримаючи в голові правила вирівнювання, або використовувати в оголошенні структури атрибут 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. Актуальний вміст об'єднання задається через технічний атрибут 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, що практично безкоштовно забезпечує дуже високу швидкість читання даних. При всій красі підходу необхідно пам'ятати про кілька пов'язаних з ним особливостей.

Для readonly транзакції покажчик на структуру-значення буде гарантовано залишатися валідним лише доти, доки транзакція не буде закрита. Як було зазначено раніше, сторінки B-дерева, на яких розташовується об'єкт, завдяки принципу copy-on-write залишаються незмінними, поки на них посилається хоча б одна транзакція. У той же час, як тільки остання пов'язана з ними транзакція завершується, сторінки можуть бути використані для нових даних. Якщо необхідно, щоб об'єкти переживали транзакцію, що породила, то їх все-таки доведеться скопіювати.
Для readwrite транзакції покажчик на отриману структуру-значення буде валідним лише до першої процедури, що модифікує (запис або видалення даних).
Незважаючи на те, що структура NodeValue не повноцінна, а підрізана (див. підрозділ «Упорядкування ключів зовнішнім компаратором»), через покажчик можна спокійно звертатися до її полів. Головне його не розіменовувати!
У жодному разі не можна модифікувати структуру через отриманий покажчик. Усі зміни мають здійснюватися лише через метод mdb_put. Втім, при всьому бажанні зробити це і не вийде, оскільки область пам'яті, де ця структура розташовується, замаплена в режимі readonly.
Remap файлу на адресний простір процесу з метою, наприклад, збільшення максимального розміру сховища за допомогою функції 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;

Range-запити

Для ітерування групи записів в LMDB передбачена абстракція курсора. Про те, як з ним працювати, розглянемо на прикладі вже знайомої нам таблиці з метаданими хмари користувача.

У межах відображення списку файлів у директорії необхідно знайти всі ключі, з якими проасоційовано її дочірні файли та папки. У попередніх підрозділах ми відсортували ключі NodeKey таким чином, щоб вони насамперед були впорядковані за ідентифікатором батьківської директорії. Таким чином, технічно завдання отримання вмісту папки зводиться до встановлення курсору на верхню межу групи ключів із заданим префіксом з подальшим ітеруванням до нижньої межі.

Знайти верхню межу можна "у лоб" послідовним пошуком. Для цього курсор встановлюється на початок списку ключів у базі даних і далі інкрементується доти, поки не під ним не опиниться ключ з ідентифікатором батьківської директорії. Цей підхід має 2 очевидні недоліки:

Лінійна складність пошуку, хоча, як відомо, у деревах взагалі і в B-дереві зокрема його можна здійснити за логарифмічний час.
Даремно піднімаються з файлу в основну пам'ять усі сторінки, що передують шуканій, що дуже дорого.

На щастя в 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-частини первинного ключа неоптимально відразу з кількох точок зору:

З погляду займаного місця через те, що метадані можуть бути дуже багатими.
З точки зору продуктивності, тому що при оновленні метаданих ноди доведеться робити перезапис за двома ключами.
З точки зору підтримки коду, варто забути оновити дані по одному з ключів, як ми отримаємо важковловимий баг неконсистентності даних у сховищі.

Далі розглянемо, як ліквідувати ці недоліки.

Організація зв'язків між таблицями

Для зв'язку індексної таблиці з основною добре підходить патерн «ключ як значення». Як випливає з його назви як value-частини індексного запису виступає копія значення первинного ключа. Цей підхід нівелює всі перелічені вище недоліки, пов'язані зі зберіганням копії value-частини первинного запису. Єдина плата - для отримання значення за індексним ключем потрібно зробити 2 запити до бази даних замість одного. Схематично схема бази даних, що вийшла, виглядає наступним чином.

Ще одним патерном організації зв'язку між таблицями є «надлишковий ключ». Його суть у додаванні в ключ додаткових атрибутів, які потрібні не для сортування, а для відтворення пов'язаного ключа. зате більш зрозумілий приклад.

У хмарних мобільних клієнтах є сторінка, де відображаються всі файли та папки, до яких користувач надав доступ іншим. Оскільки таких файлів відносно мало, а різного роду пов'язаної з ними специфічної інформації про публічність багато (кому надано доступ, з якими правами тощо) не буде раціонально обтяжувати їй value-частина запису в основній таблиці. Однак якщо захотіти відображати такі файли в офлайні, то зберігати її десь таки потрібно. Природним варіантом рішення є заклад окремої таблиці. На схемі нижче її ключ має префікс "P", а плейсхолдер "propname" може бути замінений на більш конкретне значення "public info".

Всі унікальні метадані, для зберігання яких і заводилася нова таблиця, виносяться у value-частина запису. У той же час, ті дані про файли та папки, які вже зберігаються в основній таблиці, не хочеться дублювати. Натомість у ключ «P» додаються надлишкові дані в особі полів «node ID» та «timestamp». Завдяки ним можна сконструювати індексний ключ, яким отримати первинний ключ, яким, нарешті, отримати метадані ноди.

Висновок

Підсумки впровадження LMDB оцінюємо позитивно. Після нього кількість зависань програми зменшилася на 30%.

Результати зробленої роботи знайшли відгук за межами команди iOS. На даний момент один з головних розділів "Файли" у додатку для Android також перейшов на використання LMDB, а інші частини - на підході. Мова C, на якому реалізовано key-value сховище, з'явився гарною підмогою, щоб спочатку зробити прикладну обв'язку навколо нього кроссплатформенно мовою С++. Для безшовного з'єднання бібліотеки C++ з платформним кодом на Objective-C і Kotlin був використаний кодогенератор Джинні від Dropbox, але це вже зовсім інша історія.

Джерело: habr.com

Блиск і злидні key-value бази даних LMDB у додатках для iOS