У јесен 2019. у иОС тиму Маил.ру Цлоуд догодио се дуго очекивани догађај. Главна база података за трајно складиштење стања апликације постала је веома егзотична за мобилни свет Лигхтнинг меморија мапирана база података (ЛМДБ). Испод реза нудимо вам детаљан преглед у четири дела. Прво, хајде да причамо о разлозима за такав нетривијалан и тежак избор. Затим ћемо прећи на разматрање три стуба у срцу ЛМДБ архитектуре: датотеке мапиране меморијом, Б+-стабло, приступ копирања на уписивање за имплементацију трансакција и мултиверзија. Коначно, за десерт - практични део. У њему ћемо погледати како да дизајнирамо и имплементирамо шему базе података са неколико табела, укључујући једну индексну, на врху АПИ-ја кључ/вредност ниског нивоа.

Садржина

1. Мотивација за имплементацију
2. ЛМДБ Поситионинг
3. Три стуба ЛМДБ
   КСНУМКС. Кит #1. Датотеке мапиране у меморију
   КСНУМКС. Кит #2. Б+-дрво
   КСНУМКС. Кит #3. Цопи-он-врите
4. Дизајнирање шеме података на врху АПИ-ја кључ/вредност
   КСНУМКС. Основне апстракције
   КСНУМКС. Моделирање таблица
   КСНУМКС. Моделирање односа између табела

1. Мотивација за имплементацију

Једне 2015. године, потрудили смо се да измеримо колико често интерфејс наше апликације заостаје. Урадили смо ово са разлогом. Добијали смо све чешће жалбе да понекад апликација престане да реагује на радње корисника: дугмад се не могу притиснути, листе се не померају итд. О механици мерења рекао на АвитоТецх-у, па овде дајем само редослед бројева.

Резултати мерења су за нас постали хладан туш. Испоставило се да смрзавања изазивају много више проблема него било који други. Ако је пре схватања ове чињенице главни технички показатељ квалитета био без судара, онда после фокуса померено без замрзавања.

Саградивши контролна табла са замрзавањем а после трошења квантитативан и квалитета анализом њихових разлога, главни непријатељ је постао јасан - тешка пословна логика изведена у главној нити апликације. Природна реакција на ову срамоту била је горућа жеља да се она гурне у радне токове. Да бисмо систематски решили овај проблем, прибегли смо архитектури са више нити заснованој на лаким актерима. Посветио сам га његовој адаптацији за иОС свет две нити на колективном Твитеру и чланак о Хабреу. Као део актуелног наратива, желим да истакнем оне аспекте одлуке који су утицали на избор базе података.​

​Акторски модел организације система претпоставља да вишенитност постаје његова друга суштина. Модел објекти у њему воле да прелазе границе тока. И то не раде понекад и ту и тамо, већ скоро стално и свуда.​

База података је једна од компоненти камена темељца у представљеном дијаграму. Његов главни задатак је да имплементира макрообразац Схаред Датабасе. Ако се у свету предузећа користи за организовање синхронизације података између услуга, онда у случају архитектуре актера – података између нити. Дакле, била нам је потребна база података која не би изазвала ни минималне потешкоће при раду са њом у окружењу са више нити. Конкретно, то значи да објекти добијени из њега морају бити барем безбедни за нити, а идеално потпуно непроменљиви. Као што знате, ово друго се може користити истовремено из неколико нити без прибегавања било каквом закључавању, што има благотворно дејство на перформансе.

Други значајан фактор који је утицао на избор базе података био је наш цлоуд АПИ. Инспирисан је приступом синхронизације који је усвојио гит. Као и он, циљали смо на оффлине-фирст АПИ, што изгледа више него прикладно за клијенте у облаку. Претпостављало се да ће они само једном испумпати потпуно стање облака, а затим ће до синхронизације у огромној већини случајева доћи кроз увођење промена. Авај, ова прилика је још само у теоријској зони, а клијенти нису научили како да раде са закрпама у пракси. За то постоји низ објективних разлога, које ћемо, да не бисмо одлагали увод, оставити иза заграда. Оно што је много више интересантно су поучни закључци лекције о томе шта се дешава када АПИ каже „А“, а његов потрошач не каже „Б“.

Дакле, ако замислите гит, који приликом извршавања команде за повлачење, уместо да примењује закрпе на локални снимак, упоређује своје пуно стање са пуним стањем сервера, онда ћете имати прилично тачну представу о томе како се синхронизација одвија у облаку клијентима. Лако је претпоставити да да бисте га имплементирали, морате да доделите два ДОМ стабла у меморији са мета-информацијама о свим серверским и локалним датотекама. Испоставило се да ако корисник складишти 500 хиљада датотека у облаку, онда је за синхронизацију потребно поново креирати и уништити два стабла са 1 милион чворова. Али сваки чвор је агрегат који садржи граф подобјеката. У том светлу, резултати профилисања су очекивани. Испоставило се да чак и без узимања у обзир алгоритма спајања, сама процедура стварања и накнадног уништавања огромног броја малих објеката кошта прилично пени. Ситуацију погоршава чињеница да је основна операција синхронизације укључена у велики број корисничких скрипти. Као резултат тога, поправљамо други важан критеријум у избору базе података - могућност имплементације ЦРУД операција без динамичке алокације објеката.

Остали захтеви су традиционалнији и њихова цела листа је следећа.

1. Сигурност нити.
2. Мултипроцессинг. Диктирано жељом да се користи иста инстанца базе података за синхронизацију стања не само између нити, већ и између главне апликације и иОС екстензија.
3. Способност представљања ускладиштених ентитета као непроменљивих објеката.​
4. Нема динамичких алокација у оквиру ЦРУД операција.
5. Подршка трансакцијама за основна својства КИСЕЛИНА: атомичност, конзистентност, изолованост и поузданост.
6. Брзина на најпопуларнијим случајевима.

Са овим скупом захтева, СКЛите је био и остао добар избор. Међутим, у оквиру проучавања алтернатива, наишао сам на књигу „Почетак рада са ЛевелДБ“. Под њеним руководством написан је бенчмарк који упоређује брзину рада са различитим базама података у реалним сценаријима у облаку. Резултат је премашио наша најлуђа очекивања. У најпопуларнијим случајевима - добијање курсора на сортираној листи свих датотека и сортираној листи свих датотека за дати директоријум - ЛМДБ се показао 10 пута бржим од СКЛите-а. Избор је постао очигледан.

2. ЛМДБ позиционирање

ЛМДБ је веома мала библиотека (само 10К редова) која имплементира најнижи основни слој база података – складиште.

Горњи дијаграм показује да поређење ЛМДБ-а са СКЛите-ом, који такође имплементира више нивое, генерално није тачније од СКЛите-а са основним подацима. Било би поштеније навести исте машине за складиштење као једнаке конкуренте - БеркелеиДБ, ЛевелДБ, Сопхиа, РоцксДБ, итд. Постоје чак и развоји где ЛМДБ делује као компонента машине за складиштење за СКЛите. Први такав експеримент био је 2012. године потрошен би ЛМДБ Ховард Цху. Налази Испоставило се да је толико интригантно да су његову иницијативу покупили ентузијасти ОСС-а и нашла свој наставак у личности ЛумоСКЛ. У јануару 2020. аутор овог пројекта био је Ден Ширер представљено то на ЛинукЦонфАу.

ЛМДБ се углавном користи као механизам за базе података апликација. Библиотека свој изглед дугује програмерима ОпенЛДАП, који су били веома незадовољни БеркелеиДБ-ом као основом за њихов пројекат. Почевши од скромне библиотеке бтрее, Хауард Чу је успео да створи једну од најпопуларнијих алтернатива нашег времена. Свој веома цоол извештај посветио је овој причи, као и унутрашњој структури ЛМДБ-а. „База података мапираних у муњевитој меморији“. Добар пример освајања складишта поделио је Леонид Јурјев (ака илео) из Поситиве Тецхнологиес у свом извештају на Хигхлоад 2015 „ЛМДБ мотор је посебан шампион“. У њему он говори о ЛМДБ-у у контексту сличног задатка имплементације РеОпенЛДАП-а, а ЛевелДБ је већ био предмет упоредне критике. Као резултат имплементације, Поситиве Тецхнологиес је чак имао виљушку која се активно развија МДБКС са веома укусним карактеристикама, оптимизацијама и исправке грешака.

ЛМДБ се често користи као складиште какав јесте. На пример, претраживач Мозилла Фирефок izabrao то за бројне потребе и, почевши од верзије 9, Ксцоде преферирано његов СКЛите за складиштење индекса.

Мотор је такође оставио траг у свету развоја мобилних уређаја. Трагови његове употребе могу бити наћи у иОС клијенту за Телеграм. ЛинкедИн је отишао још даље и изабрао ЛМДБ као подразумевано складиште за свој домаћи оквир за кеширање података Роцкет Дата, о чему рекао У свом чланку из 2016.

ЛМДБ се успешно бори за место на сунцу у ниши коју је оставио БеркелеиДБ након што је дошао под контролу Орацле-а. Библиотека је вољена због своје брзине и поузданости, чак и у поређењу са својим колегама. Као што знате, нема бесплатних ручкова, и желео бих да нагласим компромис са којим ћете морати да се суочите када бирате између ЛМДБ и СКЛите. Горњи дијаграм јасно показује како се постиже повећана брзина. Прво, не плаћамо додатне слојеве апстракције на врху диска за складиштење. Јасно је да добра архитектура и даље не може без њих, и они ће се неизбежно појавити у коду апликације, али ће бити много суптилнији. Неће садржати функције које нису потребне за одређену апликацију, на пример, подршку за упите у СКЛ језику. Друго, постаје могуће оптимално имплементирати мапирање операција апликације на захтеве за складиштење на диску. Ако СКЛите у мом раду се заснива на просечним статистичким потребама просечне апликације, онда сте ви, као програмер апликације, добро свесни главних сценарија оптерећења. За продуктивније решење, мораћете да платите већу цену како за развој почетног решења тако и за његову каснију подршку.

3. Три стуба ЛМДБ

Пошто смо погледали ЛМДБ из птичје перспективе, дошло је време да се уђе дубље. Следећа три одељка ће бити посвећена анализи главних стубова на којима почива архитектура складиштења:

1. Меморијски мапирани фајлови као механизам за рад са диском и синхронизацију интерних структура података.
2. Б+-стабло као организација структуре ускладиштених података.
3. Цопи-он-врите као приступ за обезбеђивање АЦИД трансакцијских својстава и мултиверзија.

3.1. Кит #1. Датотеке мапиране у меморију

Датотеке мапиране меморијом су толико важан архитектонски елемент да се чак појављују у називу спремишта. Питања кеширања и синхронизације приступа сачуваним информацијама су у потпуности препуштена оперативном систему. ЛМДБ не садржи никакве кеш меморије у себи. Ово је свесна одлука аутора, пошто читање података директно из мапираних датотека омогућава вам да одсечете много углова у имплементацији мотора. Испод је далеко од потпуне листе неких од њих.

1. Одржавање конзистентности података у складишту када се ради са њима из неколико процеса постаје одговорност оперативног система. У следећем одељку, ова механика је размотрена детаљно и са сликама.
2. Одсуство кеш меморије у потпуности елиминише ЛМДБ из режијских трошкова повезаних са динамичким алокацијама. Читање података у пракси значи постављање показивача на тачну адресу у виртуелној меморији и ништа више. Звучи као научна фантастика, али у изворном коду за складиштење сви позиви цаллоц-у су концентрисани у функцији конфигурације складиштења.
3. Одсуство кеша такође значи и одсуство закључавања повезаних са синхронизацијом њиховог приступа. Читачи, од којих може бити произвољан број читача у исто време, не наилазе ни на један мутекс на свом путу до података. Због тога, брзина читања има идеалну линеарну скалабилност на основу броја ЦПУ-а. У ЛМДБ-у се синхронизују само операције модификације. У исто време може постојати само један писац.
4. Минимум логике кеширања и синхронизације елиминише изузетно сложен тип грешака повезаних са радом у окружењу са више нити. На конференцији Усеник ОСДИ 2014 биле су две занимљиве студије базе података: „Сви системи датотека нису креирани једнаки: о сложености израде апликација које су усклађене са падом“ и „Мучење база података ради забаве и профита“. Од њих можете добити информације како о поузданости ЛМДБ-а без преседана, тако ио готово беспрекорној имплементацији АЦИД трансакцијских својстава, која је супериорнија од СКЛите-а.
5. Минимализам ЛМДБ-а омогућава да се машинска репрезентација његовог кода у потпуности налази у Л1 кеш меморији процесора са пратећим карактеристикама брзине.

Нажалост, у иОС-у, са датотекама мапираним меморијом, све није тако без облака као што бисмо желели. Да бисмо свесније говорили о недостацима повезаним са њима, потребно је запамтити опште принципе имплементације овог механизма у оперативним системима.

Опште информације о датотекама мапираним меморијом

Са сваком апликацијом која се покреће, оперативни систем повезује ентитет који се зове процес. Сваком процесу се додељује непрекидни опсег адреса у које смешта све што му је потребно за рад. На најнижим адресама налазе се одељци са кодом и тврдо кодираним подацима и ресурсима. Следи растући блок динамичког адресног простора, који нам је добро познат под именом хеап. Садржи адресе ентитета који се појављују током рада програма. На врху је меморијска област коју користи стек апликација. Она или расте или се скупља; другим речима, њена величина такође има динамичку природу. Да би се спречило да се стек и гомила међусобно потискују и ометају, они се налазе на различитим крајевима адресног простора. Постоји рупа између два динамичка одељка на врху и на дну. Оперативни систем користи адресе у овом средњем одељку да повеже различите ентитете са процесом. Конкретно, може да повеже одређени континуирани скуп адреса са датотеком на диску. Таква датотека се зове меморијска мапа.​

Адресни простор додељен процесу је огроман. Теоретски, број адреса је ограничен само величином показивача, која је одређена битним капацитетом система. Ако би физичка меморија била мапирана на њу 1-на-1, онда би први процес прогутао цео РАМ и не би било говора о било каквом мултитаскингу.​

Међутим, из нашег искуства знамо да савремени оперативни системи могу истовремено да извршавају онолико процеса колико желите. Ово је могуће због чињенице да они само додељују много меморије процесима на папиру, али у стварности учитавају у главну физичку меморију само онај део који је овде и сада тражен. Стога се меморија повезана са процесом назива виртуелна.

Оперативни систем организује виртуелну и физичку меморију у странице одређене величине. Чим је одређена страница виртуелне меморије тражена, оперативни систем је учитава у физичку меморију и упарује их у посебној табели. Ако нема слободних слотова, онда се једна од претходно учитаних страница копира на диск, а она која је тражена заузима њено место. Овај поступак, на који ћемо се ускоро вратити, назива се замена. Слика испод илуструје описани процес. На њему је учитана страница А са адресом 0 и постављена на главну меморијску страницу са адресом 4. Ова чињеница се одразила у табели кореспонденције у ћелији број 0.​

Прича је потпуно иста са датотекама мапираним у меморију. Логично, они су наводно непрекидно и у потпуности лоцирани у виртуелном адресном простору. Међутим, они улазе у физичку меморију страницу по страницу и само на захтев. Измена таквих страница се синхронизује са фајлом на диску. На овај начин можете да извршите И/О фајл једноставним радом са бајтовима у меморији - све промене ће језгро оперативног система аутоматски пренети у изворну датотеку.​
​
Слика испод показује како ЛМДБ синхронизује своје стање када ради са базом података из различитих процеса. Пресликавањем виртуелне меморије различитих процеса у исту датотеку, ми де фацто обавезујемо оперативни систем да транзитивно синхронизује одређене блокове њихових адресних простора један са другим, где изгледа ЛМДБ.​
​

Важна нијанса је да ЛМДБ, подразумевано, модификује датотеку података путем механизма за писање системског позива и приказује саму датотеку у режиму само за читање. Овај приступ има две важне последице.

Прва последица је заједничка за све оперативне системе. Његова суштина је да дода заштиту од ненамерног оштећења бази података нетачним кодом. Као што знате, извршне инструкције процеса су слободне за приступ подацима са било ког места у његовом адресном простору. Истовремено, као што смо се управо сетили, приказивање датотеке у режиму читања и писања значи да било која инструкција такође може да је модификује. Ако то уради грешком, покушавајући, на пример, да заиста препише елемент низа у непостојећем индексу, онда може случајно да промени датотеку мапирану на ову адресу, што ће довести до оштећења базе података. Ако је датотека приказана у режиму само за читање, онда ће покушај промене одговарајућег адресног простора довести до хитног прекида програма са сигналом SIGSEGV, а датотека ће остати нетакнута.

Друга последица је већ специфична за иОС. Ни аутор ни други извори то експлицитно не помињу, али без њега ЛМДБ не би био погодан за рад на овом мобилном оперативном систему. Следећи одељак је посвећен његовом разматрању.

Специфичности меморијских мапираних датотека у иОС-у

Био је диван извештај на ВВДЦ-у 2018 „Дубоко зарон у иОС меморију“. То нам говори да су у иОС-у све странице које се налазе у физичкој меморији једне од 3 врсте: прљаве, компримоване и чисте.

Чиста меморија је колекција страница које се могу безболно испразнити из физичке меморије. Подаци које садрже могу се поново учитати по потреби из оригиналних извора. У ову категорију спадају датотеке мапиране меморије само за читање. иОС се не плаши да у било ком тренутку испразни странице мапиране у датотеку из меморије, јер је загарантовано да ће бити синхронизоване са датотеком на диску.
​
Све измењене странице завршавају у прљавој меморији, без обзира где се првобитно налазиле. Конкретно, датотеке мапиране меморијом модификоване уписивањем у виртуелну меморију повезане са њима биће класификоване на овај начин. Отварање ЛМДБ са заставом MDB_WRITEMAP, након што унесете измене, ово можете лично да проверите.​

​Чим апликација почне да заузима превише физичке меморије, иОС је подвргава компресији прљаве странице. Укупна меморија коју заузимају прљаве и компримоване странице чини такозвани меморијски отисак апликације. Када достигне одређену граничну вредност, системски демон ООМ убице долази након процеса и насилно га прекида. Ово је посебност иОС-а у поређењу са десктоп оперативним системима. Насупрот томе, смањење меморијског отиска заменом страница са физичке меморије на диск није обезбеђено у иОС-у. Разлози се могу само нагађати. Можда је процедура интензивног премештања страница на диск и назад превише енергетска за мобилне уређаје, или иОС штеди ресурсе поновног писања ћелија на ССД дисковима, или можда дизајнери нису били задовољни укупним перформансама система, где је све стално замењују. Како год било, чињеница остаје чињеница.

Добра вест, већ поменута раније, је да ЛМДБ подразумевано не користи ммап механизам за ажурирање датотека. То значи да иОС класифицира приказане податке као чисту меморију и не доприноси меморијском отиску. Ово можете да проверите помоћу алата Ксцоде који се зове ВМ Трацкер. Снимак екрана испод приказује стање иОС виртуелне меморије Цлоуд апликације током рада. На почетку су у њему иницијализоване 2 ЛМДБ инстанце. Првом је било дозвољено да прикаже свој фајл на 1ГиБ виртуелне меморије, другом - 512МиБ. Упркос чињеници да оба складишта заузимају одређену количину резидентне меморије, ниједна од њих не доприноси прљавој величини.

А сада је време за лоше вести. Захваљујући механизму замене у 64-битним десктоп оперативним системима, сваки процес може да заузме онолико виртуелног адресног простора колико дозвољава слободан простор на хард диску за његову потенцијалну замену. Замена свап-а компресијом у иОС-у радикално смањује теоретски максимум. Сада сви живи процеси морају стати у главну (читај РАМ) меморију, а сви они који се не уклапају морају бити приморани да се прекину. Ово је наведено као у горе поменутом извештај, и ин званична документација. Као последица тога, иОС озбиљно ограничава количину меморије доступне за доделу путем ммап-а. Ево овде Можете погледати емпиријска ограничења количине меморије која се може доделити различитим уређајима користећи овај системски позив. На најсавременијим моделима паметних телефона иОС је постао издашан за 2 гигабајта, а на врхунским верзијама иПад-а – за 4. У пракси, наравно, морате се фокусирати на најниже подржане моделе уређаја, где је све веома тужно. Што је још горе, гледајући стање меморије апликације у ВМ Трацкер-у, открићете да ЛМДБ није једини који тврди да је меморијско мапиран. Добре комаде поједу системски алокатори, датотеке ресурса, оквири слика и други мањи предатори.

На основу резултата експеримената у Цлоуд-у, дошли смо до следећих компромисних вредности за меморију коју је доделио ЛМДБ: 384 мегабајта за 32-битне уређаје и 768 за 64-битне уређаје. Након што се овај волумен потроши, све операције модификације почињу да се завршавају кодом MDB_MAP_FULL. Такве грешке уочавамо у нашем мониторингу, али оне су довољно мале да се у овој фази могу занемарити.

Неочигледан разлог за прекомерну потрошњу меморије од стране складишта могу бити дуговечне трансакције. Да бисмо разумели како су ова два феномена повезана, помоћи ће нам разматрање преостала два стуба ЛМДБ.

3.2. Кит #2. Б+ дрво

Да бисте емулирали табеле на врху складишта кључ/вредност, следеће операције морају бити присутне у његовом АПИ-ју:

1. Уметање новог елемента.
2. Потражите елемент са датим кључем.
3. Уклањање елемента.
4. Итерирајте по интервалима кључева по редоследу којим су сортирани.

Најједноставнија структура података која може лако имплементирати све четири операције је бинарно стабло претраге. Сваки од његових чворова представља кључ који дели цео подскуп подређених кључева у два подстабла. Лева садржи оне које су мање од родитеља, а десна оне које су веће. Добијање уређеног сета кључева постиже се једним од класичних обилазака дрвета.​

Бинарна стабла имају две фундаменталне мане које их спречавају да буду ефикасна као структура података заснована на диску. Прво, степен њихове равнотеже је непредвидив. Постоји знатан ризик од добијања стабала у којима се висине различитих грана могу јако разликовати, што значајно погоршава алгоритамску сложеност претраге у односу на очекивану. Друго, обиље унакрсних веза између чворова лишава бинарна стабла локације у меморији.Блиски чворови (у смислу веза између њих) могу се налазити на потпуно различитим страницама у виртуелној меморији. Као последица тога, чак и једноставно прелажење неколико суседних чворова у стаблу може захтевати посету упоредивом броју страница. Ово је проблем чак и када говоримо о ефикасности бинарних стабала као структуре података у меморији, пошто стално ротирање страница у кешу процесора није јефтино задовољство. Када је реч о честом преузимању страница повезаних са чворовима са диска, ситуација постаје потпуна жалосно.

Б-стабла, као еволуција бинарних стабала, решавају проблеме идентификоване у претходном параграфу. Прво, они се самоуравнотежују. Друго, сваки њихов чвор дели скуп подређених кључева не на 2, већ на М уређене подскупове, а број М може бити прилично велик, реда неколико стотина, или чак хиљада.

Тиме:

1. Сваки чвор садржи велики број већ наручених кључева и стабла су врло кратка.
2. Стабло добија својство локалности локације у меморији, пошто се кључеви који су блиске вредности природно налазе један поред другог на истим или суседним чворовима.
3. Број транзитних чворова приликом спуштања стабла током операције претраге је смањен.
4. Број циљних чворова који се читају током упита опсега је смањен, пошто сваки од њих већ садржи велики број наручених кључева.

ЛМДБ користи варијацију Б-стабла званог Б+ стабло за складиштење података. Горњи дијаграм приказује три типа чворова који постоје у њему:

1. На врху је корен. Он материјализује ништа више од концепта базе података унутар складишта. Унутар једне ЛМДБ инстанце можете креирати неколико база података које деле мапирани виртуелни адресни простор. Сваки од њих почиње од свог корена.
2. На најнижем нивоу су листови. Они и само они садрже парове кључ-вредност ускладиштене у бази података. Иначе, ово је посебност Б+-дрвета. Ако редовно Б-стабло складишти делове вредности у чворовима свих нивоа, онда је варијација Б+ само на најнижој. Пошто смо поправили ову чињеницу, даље ћемо назвати подтип стабла који се користи у ЛМДБ једноставно Б-стабло.
3. Између корена и листова постоји 0 или више техничких нивоа са навигационим (гранским) чворовима. Њихов задатак је да поделе сортирани сет кључева између листова.

Физички, чворови су блокови меморије унапред одређене дужине. Њихова величина је вишеструка од величине меморијских страница у оперативном систему, о чему смо горе говорили. Структура чвора је приказана испод. Заглавље садржи мета информације, од којих је најочигледнија, на пример, контролни збир. Следе информације о офсетима у којима се налазе ћелије са подацима. Подаци могу бити или кључеви, ако је реч о навигационим чворовима, или цели парови кључ/вредност у случају листова.​ Више о структури страница можете прочитати у раду. „Евалуација продавница кључева и вредности високих перформанси“.

Пошто смо се позабавили унутрашњим садржајем чворова странице, даље ћемо представити ЛМДБ Б-стабло на поједностављен начин у следећем облику.

Странице са чворовима налазе се узастопно на диску. Странице са већим бројем налазе се на крају датотеке. Такозвана мета страница садржи информације о помацима по којима се могу пронаћи корени свих стабала. Приликом отварања датотеке, ЛМДБ скенира датотеку страницу по страницу од краја до почетка у потрази за исправном мета страницом и преко ње проналази постојеће базе података.​

Сада, имајући идеју о логичкој и физичкој структури организације података, можемо прећи на разматрање трећег стуба ЛМДБ. Уз његову помоћ се све модификације складишта дешавају трансакцијски и изоловано једна од друге, дајући бази података као целини својство мултиверзије.

3.3. Кит #3. Цопи-он-врите

Неке операције Б-стабла укључују уношење низа промена у његове чворове. Један пример је додавање новог кључа чвору који је већ достигао свој максимални капацитет. У овом случају, потребно је, прво, да се чвор подели на два, и друго, да се дода веза ка новом детету у свом надређеном чвору. Овај поступак је потенцијално веома опасан. Ако се из неког разлога (пад, нестанак струје, итд.) деси само део промена из серије, онда ће дрво остати у неконзистентном стању.

Једно традиционално решење за прављење базе података отпорном на грешке је додавање додатне структуре података на диску поред Б-стабла - евиденције трансакција, такође познатог као дневник за уписивање унапред (ВАЛ). То је датотека на чијем се крају планирана операција уписује стриктно пре модификације самог Б-стабла. Стога, ако се открије оштећење података током самодијагнозе, база података консултује евиденцију да би се довела у ред.

ЛМДБ је одабрао другачији метод као свој механизам толеранције грешака, који се зове копирање на писање. Његова суштина је да уместо да ажурира податке на постојећој страници, прво их у потпуности копира и изврши све измене у копији.​

Затим, да би ажурирани подаци били доступни, потребно је променити везу ка чвору који је постао актуелан у свом родитељском чвору. Пошто га такође треба модификовати за ово, такође се претходно копира. Процес се наставља рекурзивно све до корена. Последња ствар коју треба променити су подаци на мета страници.​

Ако се изненада процес сруши током процедуре ажурирања, онда или нова мета страница неће бити креирана, или неће бити уписана на диск у потпуности, а њен контролни збир ће бити нетачан. У било ком од ова два случаја, нове странице ће бити недоступне, али старе неће бити погођене. Ово елиминише потребу да ЛМДБ пише унапред дневник да би одржао конзистентност података. Де фацто, структура складиштења података на горе описаном диску истовремено преузима своју функцију. Одсуство експлицитне евиденције трансакција је једна од карактеристика ЛМДБ која обезбеђује велику брзину читања података.​

Добијени дизајн, назван Б-стабло само за додавање, природно обезбеђује изолацију трансакција и више верзија. У ЛМДБ, свака отворена трансакција је повезана са тренутно релевантним кореном стабла. Док се трансакција не заврши, странице стабла повезане са њом никада неће бити промењене или поново коришћене за нове верзије података. Дакле, можете да радите колико год желите са тачно скупом података који је био релевантан у том тренутку трансакција је отворена, чак и ако се складиште и даље активно ажурира у овом тренутку. Ово је суштина мултиверзије, што ЛМДБ чини идеалним извором података за наше вољене UICollectionView. Након отварања трансакције, нема потребе да повећавате меморијски отисак апликације журним пумпањем тренутних података у неку структуру у меморији, из страха да не останете без ичега. Ова карактеристика разликује ЛМДБ од истог СКЛите-а, који се не може похвалити таквом потпуном изолацијом. Након отварања две трансакције у овој другој и брисања одређеног записа унутар једне од њих, више неће бити могуће добити исти запис у оквиру друге преостале.

Друга страна новчића је потенцијално значајно већа потрошња виртуелне меморије. Слајд показује како ће изгледати структура базе података ако се модификује истовремено са 3 отворене трансакције читања гледајући различите верзије базе података. Пошто ЛМДБ не може поново да користи чворове који су доступни из корена повезаних са тренутним трансакцијама, продавница нема другог избора осим да додели још један четврти корен у меморији и још једном клонира измењене странице испод њега.​

Овде би било корисно подсетити се одељка о датотекама мапираним меморијом. Чини се да додатна потрошња виртуелне меморије не би требало много да нас брине, јер не доприноси меморијском отиску апликације. Међутим, истовремено је примећено да је иОС веома шкрт у додељивању и не можемо, као на серверу или десктопу, да обезбедимо ЛМДБ регион од 1 терабајта и да уопште не размишљамо о овој функцији. Ако је могуће, требало би да покушате да век трајања трансакција буде што краћи.

4. Дизајнирање шеме података на врху АПИ-ја кључ/вредност

Хајде да започнемо нашу АПИ анализу гледајући основне апстракције које пружа ЛМДБ: окружење и базе података, кључеви и вредности, трансакције и курсори.

Напомена о листи кодова

Све функције у јавном ЛМДБ АПИ-ју враћају резултат свог рада у облику кода грешке, али у свим наредним листама њена верификација је изостављена ради краткоће. виљушка Ц++ омоти лмдбкк, у коме се грешке материјализују као изузеци Ц++.

Као најбржи начин да повежете ЛМДБ са пројектом за иОС или мацОС, предлажем мој ЦоцоаПод ПОСЛМДБ.

4.1. Основне апстракције

Животна средина

Структура MDB_env је спремиште унутрашњег стања ЛМДБ. Породица функција са префиксом mdb_env омогућава вам да конфигуришете нека од његових својстава. У најједноставнијем случају, иницијализација мотора изгледа овако.

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

У апликацији Маил.ру Цлоуд променили смо подразумеване вредности само два параметра.

Први је величина виртуелног адресног простора на који је мапирана датотека за складиштење. Нажалост, чак и на истом уређају, специфична вредност може значајно да варира од покретања до покретања. Да би се узела у обзир ова карактеристика иОС-а, максимални волумен складишта се бира динамички. Почевши од одређене вредности, она се узастопно преполови до функције mdb_env_open неће вратити резултат другачији од ENOMEM. У теорији, постоји и супротан начин - прво додијелите минимум меморије мотору, а затим, када се прими грешка, MDB_MAP_FULL, повећајте га. Међутим, много је трновитији. Разлог је у томе што је процедура за поновно додељивање меморије (ремап) коришћењем функције mdb_env_set_map_size поништава све ентитете (курзоре, трансакције, кључеве и вредности) претходно примљене од машине. Узимање у обзир оваквог развоја догађаја у кодексу ће довести до његове значајне компликације. Међутим, ако вам је виртуелна меморија веома важна, онда би то могао бити разлог да боље погледате виљушку која је отишла далеко напред МДБКС, где је међу најављеним функцијама „аутоматско прилагођавање величине базе података у ходу“.

Други параметар, чија нам подразумевана вредност није одговарала, регулише механику обезбеђивања сигурности навоја. Нажалост, најмање иОС 10 има проблема са подршком за локално складиштење нити. Из тог разлога, у горњем примеру, спремиште се отвара са заставицом MDB_NOTLS. Поред овога, било је и неопходно виљушка Ц++ омотач лмдбккда исечемо променљиве са овим атрибутом и у њему.

Базе података

База података је засебна инстанца Б-стабла, о којој смо горе говорили. Његово отварање се дешава унутар трансакције, што у почетку може изгледати мало чудно.

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

Заиста, трансакција у ЛМДБ је ентитет за складиштење, а не одређени ентитет базе података. Овај концепт вам омогућава да изводите атомске операције над ентитетима који се налазе у различитим базама података. У теорији, ово отвара могућност моделирања табела у облику различитих база података, али сам у једном тренутку кренуо другим путем, детаљно описаним у наставку.

Кључеви и вредности

Структура MDB_val моделира концепт и кључа и вредности. Репозиторијум нема појма о њиховој семантици. За њу је нешто друго само низ бајтова дате величине. Максимална величина кључа је 512 бајтова.

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

Користећи компаратор, продавница сортира кључеве у растућем редоследу. Ако га не замените својим, користиће се подразумевани, који их сортира бајт по бајт по лексикографском редоследу.​

Трансакција

Структура трансакције је детаљно описана у претходног поглавља, па ћу овде укратко поновити њихова главна својства:

1. Подржава сва основна својства КИСЕЛИНА: атомичност, конзистентност, изолованост и поузданост. Не могу а да не приметим да постоји грешка у погледу издржљивости на мацОС-у и иОС-у која је исправљена у МДБКС-у. Више можете прочитати у њиховој РЕАДМЕ.
2. Приступ вишенитности описан је шемом „један писац / више читача“. Писци блокирају једни друге, али не блокирају читаоце. Читаоци не блокирају писце или једни друге.
3. Подршка за угнежђене трансакције.
4. Подршка за више верзија.

Мултиверзија у ЛМДБ-у је толико добра да желим да је демонстрирам на делу. Из кода испод можете видети да свака трансакција ради са тачно оном верзијом базе података која је била актуелна у време када је отворена, потпуно изолована од свих наредних промена. Иницијализација меморије и додавање тест записа у њега не представља ништа занимљиво, па су ови ритуали остављени испод спојлера.

Додавање тестног уноса

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

Препоручујем да испробате исти трик са СКЛите-ом и видите шта ће се десити.

Мултиверзија доноси веома лепе погодности у живот иОС програмера. Користећи ово својство, можете лако и природно да прилагодите брзину ажурирања извора података за обрасце на екрану, на основу разматрања корисничког искуства. На пример, узмимо функцију апликације Маил.ру Цлоуд, као што је аутоматско учитавање садржаја из галерије системских медија. Уз добру везу, клијент може да дода неколико фотографија у секунди на сервер. Ако ажурирате након сваког преузимања UICollectionView са медијским садржајем у корисничком облаку, можете заборавити на 60 фпс и глатко померање током овог процеса. Да бисте спречили честа ажурирања екрана, морате некако да ограничите брзину којом се подаци мењају у основном UICollectionViewDataSource.

Ако база података не подржава више верзија и дозвољава вам да радите само са тренутним тренутним стањем, онда да бисте креирали временски стабилан снимак података, морате га копирати или у неку структуру података у меморији или у привремену табелу. Сваки од ових приступа је веома скуп. У случају складиштења у меморији, добијамо трошкове како у меморији, узроковане складиштењем конструисаних објеката, тако и у времену, повезане са редундантним ОРМ трансформацијама. Што се тиче привременог стола, ово је још скупље задовољство, које има смисла само у не-тривијалним случајевима.

ЛМДБ-ово мултиверзионо решење решава проблем одржавања стабилног извора података на веома елегантан начин. Довољно је само да отворите трансакцију и воила - док је не завршимо, скуп података ће гарантовано бити исправљен. Логика његове брзине ажурирања је сада у потпуности у рукама слоја презентације, без додатних трошкова значајних ресурса.

Курсори

Курсори обезбеђују механизам за уредно понављање парова кључ-вредност путем обиласка Б-стабла. Без њих, било би немогуће ефикасно моделирати табеле у бази података, којима се сада окрећемо.

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

Својство редоследа кључева вам омогућава да конструишете апстракцију високог нивоа као што је табела на врху основних апстракција. Хајде да размотримо овај процес на примеру главне табеле клијента у облаку, која кешира информације о свим датотекама и фасциклама корисника.

Схема табеле

Један од уобичајених сценарија за који треба прилагодити структуру табеле са стаблом фолдера је избор свих елемената који се налазе унутар датог директоријума. Добар модел организације података за ефикасне упите ове врсте је Листа суседства. Да бисте га имплементирали изнад складишта кључ/вредност, потребно је сортирати кључеве датотека и фасцикли на такав начин да су груписани на основу њиховог чланства у надређеном директоријуму. Поред тога, да би се садржај директоријума приказао у форми познатом кориснику Виндовс-а (прво фасцикле, затим датотеке, оба поређана по абецедном реду), потребно је укључити одговарајућа додатна поља у кључ.

​На доњој слици је приказано како би, на основу задатка, могао изгледати приказ кључева у облику низа бајтова. Бајтови са идентификатором родитељског директоријума (црвени) се постављају прво, затим са типом (зелено) и у репу са именом (плаво). Пошто су сортирани по подразумеваном ЛМДБ компаратору по лексикографском редоследу, поређају се у потребан начин. Узастопно прелажење тастера са истим црвеним префиксом даје нам њихове повезане вредности оним редоследом којим би требало да буду приказане у корисничком интерфејсу (десно), без потребе за додатном накнадном обрадом.

Серијализација кључева и вредности

У свету су измишљене многе методе за серијализацију објеката. Пошто нисмо имали другог захтева осим брзине, изабрали смо најбржи могући за себе – депонију меморије коју заузима инстанца структуре језика Ц. Дакле, кључ елемента директоријума може се моделовати са следећом структуром 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
    };
}

У првом поглављу о критеријумима одабира базе података, поменуо сам минимизирање динамичких алокација унутар ЦРУД операција као важан фактор селекције. Код функције serialize показује како се у случају ЛМДБ могу потпуно избећи приликом убацивања нових записа у базу података. Долазни низ бајтова са сервера се прво трансформише у структуре стека, а затим се тривијално бацају у складиште. С обзиром да такође нема динамичких алокација унутар ЛМДБ, можете добити фантастичну ситуацију по иОС стандардима - користите само стацк меморију за рад са подацима дуж целе путање од мреже до диска!

Наручивање кључева са бинарним компаратором

Однос редоследа кључа је специфициран посебном функцијом која се зове компаратор. Пошто машина не зна ништа о семантици бајтова које садрже, подразумевани компаратор нема другог избора осим да распореди кључеве по лексикографском редоследу, прибегавајући поређењу бајт по бајт. Коришћење за организовање структура је слично бријању секиром. Међутим, у једноставним случајевима сматрам да је овај метод прихватљив. Алтернатива је описана у наставку, али овде ћу приметити неколико грабуља разбацаних дуж ове стазе.

Прва ствар коју треба запамтити је меморијска репрезентација примитивних типова података. Дакле, на свим Аппле уређајима, целобројне варијабле се чувају у формату Мали Ендиан. То значи да ће најмањи бајт бити са леве стране и неће бити могуће сортирати целе бројеве коришћењем поређења бајт по бајт. На пример, покушај да се ово уради са скупом бројева од 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, подразумевани бинарни компаратор више није погодан за поређење кључа. Ако га не заменимо својим, онда ће дужина имена бити приоритетнији фактор у сортирању од самог имена.

ЛМДБ омогућава свакој бази података да има сопствену функцију поређења кључева. Ово се ради помоћу функције 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 // ...
}​

Све док су сви кључеви у бази података истог типа, безусловно пребацивање њихове бајтове репрезентације на тип структуре кључа апликације је легално. Овде постоји једна нијанса, али ће о њој бити речи у наставку у пододељку „Записи о читању“.

Сериализинг Валуес

ЛМДБ ради изузетно интензивно са кључевима сачуваних записа. Њихово међусобно поређење се дешава у оквиру било које примењене операције, а учинак целог решења зависи од брзине компаратора. У идеалном свету, подразумевани бинарни компаратор би требало да буде довољан за упоређивање кључева, али ако бисте морали да користите сопствени, онда би процедура за десеријализацију кључева у њему требало да буде што бржа.

База података није посебно заинтересована за вредностни део записа (вредност). Његова конверзија из бајт репрезентације у објекат се дешава само када то већ захтева код апликације, на пример, да се прикаже на екрану. Пошто се ово дешава релативно ретко, захтеви за брзину за ову процедуру нису толико критични, а у њеној имплементацији смо много слободнији да се фокусирамо на практичност.На пример, за серијализацију метаподатака о датотекама које још увек нису преузете користимо NSKeyedArchiver.

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

Међутим, постоје тренуци када је учинак и даље важан. На пример, када чувамо метаинформације о структури датотека корисничког облака, користимо исти меморијски думп објеката. Врхунац задатка генерисања серијализоване репрезентације је чињеница да су елементи директоријума моделовани хијерархијом класа.​

Да би се то имплементирало у језику Ц, специфична поља наследника су смештена у посебне структуре, а њихова веза са основним је специфицирана кроз поље типа унион. Стварни садржај уније је специфициран преко типа техничког атрибута.

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.

Читање уноса

За читање записа у ЛМДБ користите функцију 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 показивач гледа тачно на адресу виртуелне меморије где база података чува бајт репрезентацију објекта. У ствари, добијамо неку врсту ОРМ-а који обезбеђује веома велику брзину читања података готово бесплатно. Упркос свој лепоти приступа, потребно је запамтити неколико карактеристика повезаних са њим.

1. За трансакцију само за читање, показивач на структуру вредности гарантовано остаје важећи само док се трансакција не затвори. Као што је раније напоменуто, странице Б-стабла на којима се налази објекат, захваљујући принципу копирања на уписивање, остају непромењене све док су референциране у најмање једној трансакцији. У исто време, чим се заврши последња трансакција повезана са њима, странице се могу поново користити за нове податке. Ако је неопходно да објекти преживе трансакцију која их је генерисала, онда их и даље треба копирати.
2. За трансакцију реадврите, показивач на резултујућу структуру вредности ће важити само до прве процедуре модификације (писања или брисања података).
3. Иако структура NodeValue није пуноправан, али скраћен (погледајте пододељак „Наручивање кључева помоћу екстерног компаратора“), можете безбедно приступити његовим пољима преко показивача. Главна ствар је да га не дереференцирате!
4. Ни у ком случају не треба мењати структуру преко примљеног показивача. Све промене се морају извршити само путем методе mdb_put. Међутим, без обзира колико тешко желите да то урадите, то неће бити могуће, јер је меморијска област у којој се налази ова структура мапирана у режиму само за читање.
5. Поново мапирајте датотеку у адресни простор процеса у сврху, на пример, повећања максималне величине меморије помоћу функције mdb_env_set_map_size потпуно поништава све трансакције и повезане ентитете уопште и указује на одређене објекте посебно.

Најзад, још једна особина је толико подмукла да се откривање њене суштине не уклапа само у још један пасус. У поглављу о Б-стаблу дао сам дијаграм како су његове странице распоређене у меморији. Из овога следи да адреса почетка бафера са серијализованим подацима може бити апсолутно произвољна. Због тога је показивач на њих примљен у структури MDB_val и сведено на показивач на структуру, у општем случају се испоставља да није поравнато. У исто време, архитектуре неких чипова (у случају иОС-а ово је армв7) захтевају да адреса било ког податка буде вишеструка од величине машинске речи или, другим речима, величине бита система ( за армв7 је 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). На АРМ-у можете имати исти ефекат постићи и коришћењем атрибута пацкед. С обзиром да такође помаже у оптимизацији простора који заузима структура, овај метод ми се чини пожељнијим, иако приводит до повећања трошкова операција приступа подацима.

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

Опсег упита

За понављање преко групе записа, ЛМДБ обезбеђује апстракцију курсора. Хајде да погледамо како да радимо са њим на примеру табеле са већ познатим метаподацима корисничког облака.

Као део приказивања листе датотека у директоријуму, потребно је пронаћи све кључеве са којима су повезане његове подређене датотеке и фасцикле. У претходним одељцима сортирали смо кључеве NodeKey тако да су првенствено поређани према ИД-у родитељског именика. Дакле, технички, задатак преузимања садржаја фасцикле се своди на постављање курсора на горњу границу групе кључева са датим префиксом и затим понављање до доње границе.

Горња граница се може пронаћи директно секвенцијалном претрагом. Да бисте то урадили, курсор се поставља на почетак целе листе кључева у бази података и даље се повећава све док се испод њега не појави кључ са идентификатором родитељског директоријума. Овај приступ има 2 очигледна недостатка:

1. Сложеност линеарне претраге, иако се, као што је познато, у дрвећу уопште, а посебно у Б-дрвету, може извршити у логаритамском времену.​
2. Узалуд, све странице које претходе оној која се тражи се подижу из датотеке у главну меморију, што је изузетно скупо.

На срећу, ЛМДБ АПИ пружа ефикасан начин за почетно позиционирање курсора.Да бисте то урадили, морате да генеришете кључ чија је вредност очигледно мања или једнака кључу који се налази на горњој граници интервала. На пример, у односу на листу на горњој слици, можемо направити кључ у коме је поље 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​​

Оно што је лепо је да као део итерације помоћу мдб_цурсор_гет добијамо не само кључ, већ и вредност. Ако је, да бисте испунили услове узорковања, потребно да проверите, између осталог, поља из дела вредности записа, онда су она сасвим доступна без додатних покрета.

4.3. Моделирање односа између табела

До сада смо успели да размотримо све аспекте пројектовања и рада са једном табеларном базом података. Можемо рећи да је табела скуп сортираних записа који се састоји од истог типа парова кључ-вредност. Ако прикажете кључ као правоугаоник и припадајућу вредност као паралелепипед, добићете визуелни дијаграм базе података.

​

Међутим, у стварном животу ретко је могуће проћи са тако мало крвопролића. Често је у бази података потребно, прво, имати неколико табела, а друго, направити селекције у њима по редоследу различитом од примарног кључа. Овај последњи одељак посвећен је питањима њиховог стварања и међусобног повезивања.

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

Апликација у облаку има одељак „Галерија“. Приказује медијски садржај из целог облака, сортиран по датуму. Да бисте оптимално применили такав избор, поред главне табеле потребно је да направите још једну са новом врстом кључева. Они ће садржати поље са датумом креирања датотеке, које ће служити као примарни критеријум сортирања. Пошто се нови кључеви позивају на исте податке као и кључеви у главној табели, они се називају индексни кључеви. На слици испод они су истакнути наранџастом бојом.

Да би се кључеви различитих табела одвојили један од другог у оквиру исте базе података, додато је додатно техничко поље таблеИд у све њих. Тиме што ћемо га учинити највишим приоритетом за сортирање, постићи ћемо груписање кључева прво по табелама, а унутар табела - према сопственим правилима.​

Кључ индекса упућује на исте податке као и примарни кључ. Једноставна имплементација ове особине кроз повезивање са њом копије дела вредности примарног кључа није оптимална са неколико тачака гледишта:

1. Што се тиче заузетог простора, метаподаци могу бити прилично богати.
2. Са становишта перформанси, пошто када ажурирате метаподатке чвора, мораћете да их препишете користећи два кључа.
3. Са становишта подршке коду, ако заборавимо да ажурирамо податке за један од кључева, добићемо неухватљиву грешку недоследности података у складишту.

Затим ћемо размотрити како да отклонимо ове недостатке.

Организовање односа између табела

Образац је веома погодан за повезивање табеле индекса са главном табелом "кључ као вредност". Као што му име каже, део вредности индексног записа је копија вредности примарног кључа. Овај приступ елиминише све горе наведене недостатке повезане са чувањем копије дела вредности примарног записа. Једини трошак је да да бисте добили вредност помоћу индексног кључа, морате да направите 2 упита бази података уместо једног. Шематски, резултујућа шема базе података изгледа овако.

Други образац за организовање односа између табела је "сувишни кључ". Његова суштина је да се кључу додају додатни атрибути који су потребни не за сортирање, већ за поновно креирање придруженог кључа.У апликацији Маил.ру Цлоуд постоје стварни примери његове употребе, међутим, како би се избегло дубоко урањање у контексту конкретних иОС оквира, даћу измишљен, али јаснији пример.​

Цлоуд мобилни клијенти имају страницу која приказује све датотеке и фасцикле које је корисник поделио са другим људима. Будући да је таквих фајлова релативно мало, а уз њих постоји много различитих типова специфичних информација о публицитету (коме је дозвољен приступ, са којим правима итд.), неће бити рационално оптерећивати вредносни део забележи у главној табели са њим. Међутим, ако желите да прикажете такве датотеке ван мреже, и даље их морате негде сачувати. Природно решење је да се за то направи посебан сто. У дијаграму испод, његов кључ има префикс „П“, а чувар места „пропнаме“ се може заменити специфичнијом вредношћу „јавне информације“.​

Сви јединствени метаподаци, ради чувања којих је креирана нова табела, стављају се у вредностни део записа. У исто време, не желите да дуплирате податке о датотекама и фасциклама које су већ ускладиштене у главној табели. Уместо тога, редундантни подаци се додају кључу „П“ у облику поља „ИД чвора“ и „временска ознака“. Захваљујући њима, можете конструисати индексни кључ, из којег можете добити примарни кључ, из којег, коначно, можете добити метаподатке чвора.

Закључак​

Резултате имплементације ЛМДБ оцењујемо позитивно. Након тога, број замрзнутих апликација се смањио за 30%.

Резултати обављеног посла одјекнули су изван иОС тима. Тренутно је један од главних одељака „Датотеке“ у Андроид апликацији такође прешао на коришћење ЛМДБ, а други делови су на путу. Језик Ц, у којем је имплементирано складиште кључ/вредност, био је добра помоћ да се у почетку креира оквир апликације око њега на више платформи у Ц++. Генератор кода је коришћен за неприметно повезивање резултирајуће Ц++ библиотеке са кодом платформе у Објецтиве-Ц и Котлину Дјинни са Дропбок-а, али то је сасвим друга прича.

Извор: ввв.хабр.цом