Увосень 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 я прысвяціў два трэдыкі у калектыўным твітэры і артыкул на Хабры. У рамках жа бягучага апавядання хачу падкрэсліць тыя аспекты рашэння, якія паўплывалі на выбар базы дадзеных.

Акцёрная мадэль арганізацыі сістэмы мяркуе, што шматструменнасць становіцца яе другой сутнасцю. Аб'екты мадэлі ў ёй кахаюць перасякаць межы струменяў. І робяць яны гэта не часам і дзе-то, а амаль заўсёды і ўсюды.

База дадзеных з'яўляецца адным з краевугольных кампанентаў на прадстаўленай схеме. Яе асноўнай задачай з'яўляецца рэалізацыя макропатерна Shared Database. Калі ў энтэрпрайзным свеце з яго дапамогай арганізоўваюць сінхранізацыю дадзеных паміж сэрвісамі, то ў выпадку акторнай архітэктуры – дадзеныя паміж патокамі. Такім чынам, нам спатрэбілася такая база дадзеных, праца з якой у шматструменным асяроддзі не выклікае нават мінімальных складанасцяў. У прыватнасці, гэта азначае, што атрыманыя з яе аб'екты павінны быць як мінімум струменебяспечнымі, а ў ідэале і зусім немутабельнымі. Як вядома, апошнія можна выкарыстоўваць адначасова з некалькіх патокаў, не звяртаючыся да якіх бы там ні было блакіровак, што дабратворна адбіваецца на прадукцыйнасці.

Другім значным фактарам, якія паўплывалі на выбар базы дадзеных, стала наша хмарнае 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 ён прысвяціў свой вельмі круты даклад "The 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 усе старонкі, размешчаныя ў фізічнай памяці, адносяцца да аднаго з 3 тыпаў: 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 віртуальнай памяці, другому – 512МiB. Нягледзячы на тое, што абодва сховішчы займаюць вызначаны аб'ём рэзідэнтнай памяці, ніводны з іх не контрибутит у 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 рэгіён у 1 тэрабайт і не думаць аб гэтай асаблівасці зусім. Па магчымасці трэба старацца рабіць час жыцця транзакцый як мага карацейшым.

4. Праектаванне схемы дадзеных па-над key-value API

Разбор API пачнем з разгляду базавых абстракцый, якія прадстаўляюцца LMDB: асяроддзе і базы дадзеных, ключы і значэнні, транзакцыі і курсоры.

Заўвага аб лістынга кода

Усе функцыі ў публічным API LMDB вяртаюць вынік сваёй працы ў выглядзе кода памылкі, але на ўсіх наступных лістынга яго праверка апушчана ва ўгоду лаканічнасці. На практыцы мы і зусім для ўзаемадзеяння са сховішчам выкарыстоўвалі свой відэлец C++ абгорткі lmdbxx, у якім памылкі матэрыялізуюцца ў выглядзе выключэнняў C++.

У якасці найболей хуткага спосабу падлучэння LMDB да праекту для iOS або macOS прапаную свой CocoaPod POSLMDB.

4.1. Базавыя абстракцыі

Асяроддзе (environment)

Структура MDB_env з'яўляецца ёмішчам унутранага стану LMDB. Сямейства функцый з прэфіксам mdb_env дазваляе сканфігураваць некаторыя яго ўласцівасці. У найпростым выпадку ініцыялізацыя рухавічка выглядае наступным чынам.

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

У дадатку Аблокі Mail.ru значэння па змаўчанні мы мянялі толькі ў двух параметраў.

Першы з іх - гэта памер віртуальнай адраснай прасторы, на якое адлюстроўваецца файл сховішчы. Нажаль, нават на адной і той жа прыладзе пэўнае значэнне можа істотна адрознівацца ад запуску да запуску. Каб улічыць гэтую асаблівасць iOS, максімальны аб'ём сховішчы ў нас падбіраецца дынамічна. Стартуючы з нейкага значэння, ён паслядоўна палавініцца да таго часу, пакуль функцыя mdb_env_open не верне вынік выдатны ад ENOMEM. У тэорыі існуе і супрацьлеглы шлях - спачатку вылучыць рухавічка мінімум памяці, а затым, пры атрыманні памылак MDB_MAP_FULL, павялічваць яе. Аднак ён значна больш цярністы. Чыннік у тым, што працэдура перавылучэння памяці (remap) з дапамогай функцыі mdb_env_set_map_size інвалідуе ўсе сутнасці (курсоры, транзакцыі, ключы і значэнні), атрыманыя ад рухавічка раней. Улік такога павароту падзей у кодзе прывядзе да яго істотнага ўскладнення. Калі, тым не менш, віртуальная памяць вам вельмі дарагая, тое гэта можа быць падставай прыгледзецца да які пайшоў далёка наперад форку 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: атамарнасць, кансістэнтнасць, ізаляванасць і надзейнасць. Не магу не адзначыць, што ў часе durability на 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