Во есента 2019 година, се случи долгоочекуваниот настан во тимот на Mail.ru Cloud iOS. Главната база на податоци за постојано складирање на состојбата на апликацијата стана многу егзотична за мобилниот свет База на податоци мапирана со молња меморија (LMDB). Под кројот ви нудиме детален преглед на истиот во четири дела. Прво, да разговараме за причините за таков нетривијален и тежок избор. Потоа ќе продолжиме да ги разгледуваме трите столба во срцето на LMDB архитектурата: датотеки мапирани со меморија, B+-дрво, пристап копирање-на-пишување за имплементација на трансакционалност и мултиверзија. Конечно, за десерт - практичниот дел. Во него ќе погледнеме како да дизајнираме и имплементираме шема на база на податоци со неколку табели, вклучително и индексна, на врвот на API-то со клучна вредност на ниско ниво.

содржина

1. Мотивација за имплементација
2. Позиционирање LMDB
3. Три столба на LMDB
   3.1. Кит број 1. Датотеки мапирани со меморија
   3.2. Кит број 2. Б+-дрво
   3.3. Кит број 3. Копирај-на-пишување
4. Дизајнирање шема за податоци на врвот на API со клучна вредност
   4.1. Основни апстракции
   4.2. Моделирање на табели
   4.3. Моделирање на односи меѓу табелите

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

Една година во 2015 година, се трудевме да измериме колку често заостанува интерфејсот на нашата апликација. Ова го направивме со причина. Добивме почести поплаки дека понекогаш апликацијата престанува да реагира на дејствата на корисникот: копчињата не може да се притиснат, списоците не се лизгаат итн. За механиката на мерењата изјави на AvitoTech, па овде давам само редослед на броеви.

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

Имајќи изградено контролна табла со замрзнувања и по трошењето квантитативни и квалитет анализа на нивните причини, главниот непријател стана јасен - тешка деловна логика извршена во главната нишка на апликацијата. Природната реакција на овој срам беше горливата желба да се втурне во работните струи. За систематски да го решиме овој проблем, прибегнавме кон архитектура со повеќе нишки заснована на лесни актери. Го посветив на неговата адаптација за светот на iOS две нишки на колективниот Твитер и статија за Хабре. Како дел од тековниот наратив, сакам да ги истакнам оние аспекти на одлуката што влијаеле на изборот на базата на податоци.

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

Базата на податоци е една од основните компоненти на претставениот дијаграм. Неговата главна задача е да ја имплементира макрошемата Заедничка база на податоци. Ако во светот на претпријатијата се користи за организирање на синхронизација на податоци помеѓу услугите, тогаш во случај на архитектура на актер - податоци помеѓу нишки. Така, ни требаше база на податоци што нема да предизвика ни минимални тешкотии при работа со неа во опкружување со повеќе нишки. Особено, ова значи дека предметите добиени од него мора да бидат барем безбедни за нишки и идеално целосно непроменливи. Како што знаете, вториот може да се користи истовремено од неколку нишки без прибегнување кон какво било заклучување, што има корисен ефект врз перформансите.

Вториот значаен фактор што влијаеше на изборот на базата на податоци беше нашиот Cloud API. Беше инспириран од пристапот за синхронизација усвоен од git. Слично на него, ние цели кон офлајн-прво API, што изгледа повеќе од соодветно за клиентите во облак. Се претпоставуваше дека тие ќе ја испумпуваат целосната состојба на облакот само еднаш, а потоа синхронизацијата во огромното мнозинство на случаи ќе се случи преку воведување промени. За жал, оваа можност е сè уште само во теоретската зона, а клиентите не научиле како да работат со закрпи во пракса. За тоа има низа објективни причини, кои за да не го одложиме воведувањето, ќе ги оставиме зад загради. Сега, она што е од многу поголем интерес се поучните заклучоци од лекцијата за тоа што се случува кога API вели „А“, а неговиот потрошувач не вели „Б“.

Значи, ако го замислите git, кој при извршување на командата за повлекување, наместо да применува закрпи на локална слика, ја споредува неговата целосна состојба со состојбата на целосниот сервер, тогаш ќе имате прилично точна идеја за тоа како се случува синхронизацијата во облакот. клиенти. Лесно е да се погоди дека за да го имплементирате, треба да доделите две DOM стебла во меморијата со мета-информации за сите сервери и локални датотеки. Излегува дека ако корисникот складира 500 илјади датотеки во облакот, тогаш за да ги синхронизирате, неопходно е да се рекреираат и уништат две дрвја со 1 милион јазли. Но, секој јазол е агрегат кој содржи график на подобјекти. Во оваа светлина, резултатите од профилирањето беа очекувани. Се покажа дека дури и без да се земе предвид алгоритмот за спојување, самата постапка за создавање и последователно уништување на огромен број мали предмети чини прилично денар Ситуацијата се влошува со фактот што основната операција за синхронизација е вклучена во голем број на кориснички скрипти. Како резултат на тоа, го поправаме вториот важен критериум при изборот на база на податоци - способноста да се имплементираат операции CRUD без динамична распределба на објекти.

Другите барања се потрадиционални и целата нивна листа е како што следува.

1. Безбедност на конец.
2. Мултипроцесирање. Диктирано од желбата да се користи истата база на податоци за да се синхронизира состојбата не само помеѓу нишките, туку и помеѓу главната апликација и екстензии за iOS.
3. Способност да се претстават зачуваните ентитети како непроменливи објекти.​
4. Нема динамични алокации во операциите на CRUD.
5. Поддршка за трансакции за основни својства Киселина: атомност, конзистентност, изолација и доверливост.
6. Брзина на најпопуларните случаи.

Со овој сет на барања, SQLite беше и останува добар избор. Меѓутоа, како дел од проучувањето на алтернативите, наидов на една книга „Започнување со LevelDB“. Под нејзино раководство, беше напишан репер за споредување на брзината на работа со различни бази на податоци во сценарија на вистински облак. Резултатот ги надмина нашите најлуди очекувања. Во најпопуларните случаи - добивање курсор на сортирана листа на сите датотеки и сортиран список на сите датотеки за даден директориум - LMDB се покажа дека е 10 пати побрз од SQLite. Изборот стана очигледен.

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

LMDB е многу мала библиотека (само 10K редови) која го имплементира најнискиот основен слој на бази на податоци - складирање.

Горенаведениот дијаграм покажува дека споредувањето на LMDB со SQLite, кое исто така имплементира повисоки нивоа, генерално не е поточно од SQLite со основни податоци. Би било пофер да се наведат истите мотори за складирање како еднакви конкуренти - BerkeleyDB, LevelDB, Sophia, RocksDB, итн. Има дури и случувања каде што LMDB делува како компонента на моторот за складирање за SQLite. Првиот таков експеримент беше во 2012 година потрошени од LMDB Хауард Чу. Наоди испадна толку интригантна што неговата иницијатива беше прифатена од ентузијасти на OSS и го најде своето продолжение во личноста LumoSQL. Во јануари 2020 година, автор на овој проект беше Ден Ширер презентирани тоа на LinuxConfAu.

LMDB главно се користи како мотор за бази на податоци за апликации. Библиотеката им го должи својот изглед на програмерите OpenLDAP, кои беа многу незадоволни од BerkeleyDB како основа за нивниот проект. Почнувајќи од скромна библиотека бдрво, Хауард Чу успеа да создаде една од најпопуларните алтернативи на нашето време. Тој го посвети својот многу кул извештај на оваа приказна, како и на внатрешната структура на LMDB. „База на податоци мапирана со молња меморија“. Добар пример за освојување складиште беше споделен од Леонид Јуриев (ака yleo) од Positive Technologies во неговиот извештај на Highload 2015 година „ЛМДБ моторот е посебен шампион“. Во него, тој зборува за LMDB во контекст на слична задача за спроведување на ReOpenLDAP, а LevelDB веќе беше предмет на компаративна критика. Како резултат на имплементацијата, Positive Technologies имаше дури и активно развивање вилушка MDBX со многу вкусни карактеристики, оптимизации и поправени грешки.

LMDB често се користи како складиште како што е. На пример, прелистувачот Mozilla Firefox избрал тоа за голем број потреби и, почнувајќи од верзијата 9, Xcode претпочитан неговиот SQLite за складирање на индекси.

Моторот исто така остави свој белег во светот на мобилниот развој. Траги од неговата употреба може да биде најдете во клиентот iOS за Telegram. LinkedIn отиде уште подалеку и го избра LMDB како стандардно складирање за својата домашна рамка за кеширање податоци Rocket Data, за која изјави во неговата статија во 2016 година.

LMDB успешно се бори за место на сонцето во нишата што ја остави BerkeleyDB откако дојде под контрола на Oracle. Библиотеката е сакана поради нејзината брзина и сигурност, дури и во споредба со нејзините врсници. Како што знаете, нема бесплатни ручеци и би сакал да ја нагласам компромисот со кој ќе треба да се соочите при изборот помеѓу LMDB и SQLite. Дијаграмот погоре јасно покажува како се постигнува зголемена брзина. Прво, не плаќаме за дополнителни слоеви на апстракција на врвот на складирањето на дискот. Јасно е дека добрата архитектура сè уште не може без нив, и тие неизбежно ќе се појават во кодот на апликацијата, но тие ќе бидат многу посуптилни. Тие нема да содржат функции што не се потребни од одредена апликација, на пример, поддршка за прашања на јазикот SQL. Второ, станува возможно оптимално да се имплементира мапирање на операциите на апликацијата на барањата за складирање на дискот. Ако SQLite во мојата работа се базира на просечните статистички потреби на просечна апликација, тогаш вие, како развивач на апликации, добро ги знаете главните сценарија на обемот на работа. За попродуктивно решение, ќе треба да платите зголемена цена и за развојот на првичното решение и за неговата последователна поддршка.

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

Откако го погледнавме LMDB од птичја перспектива, време беше да се оди подлабоко. Следните три дела ќе бидат посветени на анализа на главните столбови на кои почива архитектурата за складирање:

1. Датотеки мапирани со меморија како механизам за работа со диск и синхронизирање на внатрешни структури на податоци.
2. B+-дрво како организација на структурата на зачуваните податоци.
3. Копирај-на-пишување како пристап за обезбедување својства на трансакцијата ACID и мултиверзија.

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

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

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

За жал, во iOS, со датотеки мапирани со меморија, сè не е толку без облак како што би сакале. За да зборуваме за недостатоците поврзани со нив посвесно, неопходно е да се запамети општите принципи на имплементација на овој механизам во оперативните системи.

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

Со секоја апликација што се извршува, оперативниот систем поврзува ентитет наречен процес. На секој процес му е распределен близок опсег на адреси во кои поставува сè што му е потребно за да работи. На најниските адреси има делови со код и тврдокодирани податоци и ресурси. Следува растечки блок од динамичен адресен простор, добро познат под името куп. Ги содржи адресите на ентитетите кои се појавуваат за време на работата на програмата. На врвот е мемориската област што ја користи стекот на апликации. Таа или расте или се собира со други зборови, нејзината големина има и динамична природа. За да се спречи оџакот и купот да се туркаат и да се мешаат едни со други, тие се наоѓаат на различни краеви од просторот за адреси. Има дупка помеѓу двата динамички делови на врвот и на дното. Оперативниот систем користи адреси во овој среден дел за да поврзе различни ентитети со процесот. Конкретно, може да поврзе одреден континуиран сет на адреси со датотека на дискот. Таквата датотека се нарекува мемориски мапирана

Адресниот простор доделен на процесот е огромен. Теоретски, бројот на адреси е ограничен само од големината на покажувачот, што се одредува според бит капацитетот на системот. Ако физичката меморија беше мапирана со неа 1-на-1, тогаш првиот процес ќе ја проголта целата RAM меморија и нема да се зборува за било какво мултитаскинг.

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

Оперативниот систем организира виртуелна и физичка меморија во страници со одредена големина. Штом одредена страница виртуелна меморија е барана, оперативниот систем ја вчитува во физичката меморија и ги совпаѓа во посебна табела. Ако нема бесплатни слотови, тогаш една од претходно вчитаните страници се копира на дискот, а онаа што се бара го зазема своето место. Оваа постапка, на која ќе се вратиме наскоро, се нарекува замена. Сликата подолу го илустрира опишаниот процес. На неа, страницата А со адреса 0 беше вчитана и ставена на главната мемориска страница со адреса 4. Овој факт се одрази во табелата за кореспонденција во ќелијата број 0.​

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

Важна нијанса е тоа што LMDB, стандардно, ја менува датотеката со податоци преку механизмот за системски повик за пишување и ја прикажува самата датотека во режим само за читање. Овој пристап има две важни последици.

Првата последица е заедничка за сите оперативни системи. Нејзината суштина е да додаде заштита од ненамерно оштетување на базата на податоци со неточен код. Како што знаете, извршните инструкции на процесот се бесплатни за пристап до податоци од каде било во неговиот адресен простор. Во исто време, како што штотуку се сетивме, прикажувањето на датотека во режим за читање-запишување значи дека секоја инструкција исто така може да ја измени. Ако таа го направи ова по грешка, обидувајќи се, на пример, да презапише елемент од низа на непостоечки индекс, тогаш таа може случајно да ја смени датотеката мапирана на оваа адреса, што ќе доведе до оштетување на базата на податоци. Ако датотеката е прикажана во режим само за читање, тогаш обидот за промена на соодветниот адресен простор ќе доведе до итен прекин на програмата со сигнал SIGSEGV, и датотеката ќе остане недопрена.

Втората последица е веќе специфична за iOS. Ниту авторот, ниту кој било друг извор експлицитно не го споменува, но без него LMDB не би бил погоден за работа на овој мобилен оперативен систем. Следниот дел е посветен на неговото разгледување.

Специфики на датотеки мапирани со меморија во iOS

Имаше прекрасен извештај на WWDC во 2018 година „Длабоко нуркање во меморијата на iOS“. Тоа ни кажува дека во iOS, сите страници лоцирани во физичката меморија се еден од трите типа: валкани, компресирани и чисти.

Чистата меморија е збирка на страници што може безболно да се истоварат од физичката меморија. Податоците што ги содржат може повторно да се вчитаат по потреба од нивните оригинални извори. Датотеките мапирани со меморија само за читање спаѓаат во оваа категорија. iOS не се плаши да ги растоварува страниците мапирани на датотека од меморијата во секое време, бидејќи тие се загарантирани да се синхронизираат со датотеката на дискот.
​
Сите изменети страници завршуваат во валкана меморија, без разлика каде првично биле лоцирани. Конкретно, датотеките мапирани со меморија, модифицирани со запишување во виртуелната меморија поврзана со нив, ќе бидат класифицирани на овој начин. Отворање на LMDB со знаме MDB_WRITEMAP, откако ќе направите промени во него, можете лично да го потврдите ова.​

Штом апликацијата почнува да зафаќа премногу физичка меморија, iOS ја подложува на компресија на валкани страници. Вкупната меморија окупирана од валкани и компресирани страници го сочинува таканаречениот мемориски отпечаток на апликацијата. Откако ќе достигне одредена праг вредност, демонот на системот за убијци OOM доаѓа по процесот и насилно го прекинува. Ова е особеноста на iOS во споредба со десктоп оперативните системи. Спротивно на тоа, намалувањето на меморијата со замена на страници од физичка меморија на диск не е предвидено во iOS Причините може да се погодат само. Можеби постапката на интензивно преместување страници на дискот и назад е премногу енергија за мобилните уреди, или iOS го заштедува ресурсот за препишување ќелии на SSD-дискови, или можеби дизајнерите не биле задоволни од севкупните перформанси на системот, каде што сè е постојано се менуваат. Како и да е, фактот останува факт.

Добрата вест, веќе спомената претходно, е дека LMDB стандардно не го користи механизмот mmap за ажурирање датотеки. Ова значи дека прикажаните податоци се класифицирани од iOS како чиста меморија и не придонесуваат за отпечатокот на меморијата. Можете да го потврдите ова користејќи алатка Xcode наречена VM Tracker. Сликата од екранот подолу ја прикажува состојбата на виртуелната меморија iOS на апликацијата Cloud за време на работата. На почетокот, во него беа иницијализирани 2 LMDB инстанци. На првиот му беше дозволено да ја прикаже својата датотека на 1GiB виртуелна меморија, на вториот - 512MiB. И покрај фактот дека двете складишта зафаќаат одредена количина на резидентна меморија, ниту една од нив не придонесува за валкана големина.

И сега е време за лоши вести. Благодарение на механизмот за замена во 64-битни десктоп оперативни системи, секој процес може да зазема онолку виртуелен адресен простор колку што дозволува слободниот простор на хард дискот за неговата потенцијална замена. Замената на swap со компресија во iOS радикално го намалува теоретскиот максимум. Сега сите живи процеси мора да се вклопат во главната (читај RAM) меморија, а сите што не се вклопуваат мора да бидат принудени да прекинат. Ова е наведено како во погоре споменатото извештај, и внатре официјална документација. Како последица на тоа, iOS сериозно ја ограничува количината на меморија достапна за распределба преку mmap. Еве тука Може да ги погледнете емпириските граници на количината на меморија што може да се распредели на различни уреди користејќи го овој системски повик. Кај најмодерните модели на паметни телефони, iOS стана дарежлив за 2 гигабајти, а на врвните верзии на iPad - за 4. Во пракса, се разбира, треба да се фокусирате на моделите на уреди со најниска поддршка, каде што сè е многу тажно. Уште полошо, гледајќи ја состојбата на меморијата на апликацијата во VM Tracker, ќе откриете дека LMDB е далеку од единствениот што тврди дека е мапиран со меморија. Добрите парчиња ги изедуваат системските распределувачи, датотеките со ресурси, рамки за слики и други помали предатори.

Врз основа на резултатите од експериментите во Облакот, дојдовме до следните компромисни вредности за меморијата доделена од LMDB: 384 мегабајти за 32-битни уреди и 768 за 64-битни уреди. Откако ќе се потроши овој волумен, сите операции за модификација почнуваат да завршуваат со кодот MDB_MAP_FULL. Ваквите грешки ги забележуваме во нашето следење, но тие се доволно мали што во оваа фаза може да се занемарат.

Неочигледна причина за прекумерна потрошувачка на меморија од складиштето може да бидат долготрајните трансакции. За да разбереме како овие два феномени се поврзани, ќе ни помогне со разгледување на преостанатите два столба на LMDB.

3.2. Кит број 2. Б+-дрво

За да се емулираат табели на врвот на складиштето со вредност на клучот, следните операции мора да бидат присутни во неговото API:

1. Вметнување нов елемент.
2. Пребарајте елемент со даден клуч.
3. Отстранување на елемент.
4. Повторете во интервали на копчињата по редоследот по кој се подредени.

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

Бинарните стебла имаат две основни недостатоци кои ги спречуваат да бидат ефективни како структура на податоци базирана на диск. Прво, степенот на нивната рамнотежа е непредвидлив. Постои значителен ризик да се добијат дрвја во кои висините на различни гранки може многу да се разликуваат, што значително ја влошува алгоритамската сложеност на пребарувањето во споредба со очекуваното. Второ, изобилството на вкрстени врски помеѓу јазлите ги лишува бинарните дрвја од локалитет во меморијата. Како последица на тоа, дури и едноставното преминување на неколку соседни јазли во дрвото може да бара посета на споредлив број на страници. Ова е проблем дури и кога зборуваме за ефективноста на бинарните дрвја како структура на податоци во меморијата, бидејќи постојаното ротирање страници во кешот на процесорот не е евтино задоволство. Кога станува збор за често преземање страници поврзани со јазли од дискот, ситуацијата станува целосно жално.

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

Притоа:

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

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

1. На врвот е коренот. Не се материјализира ништо повеќе од концептот на база на податоци во складиштето. Во рамките на еден LMDB пример, можете да креирате неколку бази на податоци кои споделуваат мапиран виртуелен адресен простор. Секој од нив започнува од својот корен.
2. На најниско ниво се лисјата. Тие и само тие ги содржат паровите клуч-вредност зачувани во базата на податоци. Патем, ова е особеноста на Б+-дрвата. Ако редовното Б-дрво складира вредносни делови во јазли од сите нивоа, тогаш варијацијата B+ е само на најниската. Откако ќе го поправиме овој факт, ние понатаму ќе го наречеме подтипот на дрвото што се користи во LMDB едноставно Б-дрво.
3. Помеѓу коренот и листовите има 0 или повеќе технички нивоа со навигациски (гранки) јазли. Нивната задача е да го поделат сортираниот сет на клучеви меѓу листовите.

Физички, јазлите се блокови на меморија со однапред одредена должина. Нивната големина е повеќекратна од големината на мемориските страници во оперативниот систем, за што разговаравме погоре. Структурата на јазолот е прикажана подолу. Заглавието содржи мета информации, од кои најочигледна на пример е контролната сума. Следуваат информации за поместувањата во кои се наоѓаат ќелиите со податоци. Податоците можат да бидат или копчиња, ако зборуваме за навигациски јазли, или цели парови клуч-вредности во случај на листови.​ Можете да прочитате повеќе за структурата на страниците во делото. „Евалуација на продавници со клучна вредност со високи перформанси“.

Откако се занимававме со внатрешната содржина на јазлите на страниците, понатаму ќе го претставиме LMDB B-дрвото на поедноставен начин во следната форма.

Страниците со јазли се наоѓаат последователно на дискот. Повисоките нумерирани страници се наоѓаат кон крајот на датотеката. Таканаречената мета страница содржи информации за поместувањата со кои можат да се најдат корените на сите дрвја. Кога отворате датотека, LMDB ја скенира датотеката страница по страница од крај до почеток во потрага по валидна мета-страница и преку неа ги наоѓа постоечките бази на податоци.​

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

3.3. Кит број 3. Копирај-на-пишување

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

Едно традиционално решение за правење база на податоци толерантна за грешки е да се додаде дополнителна структура на податоци на дискот до Б-дрвото - дневник за трансакции, исто така познат како дневник за однапред запишување (WAL). Тоа е датотека на крајот на која планираната операција е напишана строго пред да се измени самото Б-дрво. Така, ако се открие расипување на податоците при самодијагностика, базата на податоци го консултира дневникот за да се стави во ред.

LMDB избра поинаков метод како механизам за толеранција на грешки, наречен copy-on-write. Нејзината суштина е што наместо да ги ажурира податоците на постоечката страница, прво ги копира целосно и ги прави сите модификации во копијата.

Следно, за да бидат достапни ажурираните податоци, неопходно е да се смени врската до јазолот што стана актуелен во неговиот матичен јазол. Бидејќи исто така треба да се измени за ова, тој исто така се копира претходно. Процесот продолжува рекурзивно сè до коренот. Последното нешто што треба да се промени е податоците на мета страницата.​

Ако ненадејно процесот падне за време на процедурата за ажурирање, тогаш или нема да се креира нова мета-страница, или нема целосно да се запише на дискот, а неговата контролна сума ќе биде неточна. Во секој од овие два случаи, новите страници ќе бидат недостапни, но старите нема да бидат засегнати. Ова ја елиминира потребата LMDB да пишува однапред дневник за да се одржи конзистентноста на податоците. Де факто, структурата на складирање податоци на дискот опишан погоре истовремено ја презема својата функција. Отсуството на експлицитен дневник за трансакции е една од карактеристиките на LMDB што обезбедува голема брзина на читање податоци.​

Резултирачкиот дизајн, наречен B-дрво само за додатоци, природно обезбедува изолација на трансакциите и мулти-верзија. Во LMDB, секоја отворена трансакција е поврзана со моментално релевантниот корен од дрво. Сè додека трансакцијата не биде завршена, страниците на дрвото поврзани со неа никогаш нема да се променат или повторно да се користат за нови верзии на податоците трансакцијата беше отворена, дури и ако складиштето продолжи активно да се ажурира во овој момент. Ова е суштината на мултиверзијата, што го прави LMDB идеален извор на податоци за нашата сакана UICollectionView. Откако ќе отворите трансакција, нема потреба да го зголемувате меморискиот отпечаток на апликацијата со набрзина испумпување на тековните податоци во некоја структура во меморијата, поради страв да не останете без ништо. Оваа карактеристика го разликува LMDB од истиот SQLite, кој не може да се пофали со таква целосна изолација. Откако ќе отворите две трансакции во второто и избришавте одреден запис во една од нив, веќе нема да биде можно да се добие истиот запис во вториот преостанат.

На другата страна на паричката е потенцијално значително поголема потрошувачка на виртуелна меморија. Слајдот покажува како ќе изгледа структурата на базата на податоци доколку се менува истовремено со 3 отворени трансакции за читање кои гледаат во различни верзии на базата на податоци. Бидејќи LMDB не може повторно да ги користи јазлите достапни од корените поврзани со тековните трансакции, продавницата нема друг избор освен да одвои уште еден четврти корен во меморијата и уште еднаш да ги клонира изменетите страници под него.

Тука би било корисно да се потсетиме на делот за датотеки мапирани со меморија. Се чини дека дополнителната потрошувачка на виртуелна меморија не треба многу да не загрижува, бидејќи не придонесува за меморискиот отпечаток на апликацијата. Сепак, во исто време, беше забележано дека iOS е многу скржав во неговото доделување и не можеме, како на сервер или десктоп, да обезбедиме LMDB регион од 1 терабајт и воопшто да не размислуваме за оваа функција. Ако е можно, треба да се обидете да го направите животниот век на трансакциите што е можно пократок.

4. Дизајнирање шема за податоци на врвот на API со клучна вредност

Да ја започнеме нашата API анализа со гледање на основните апстракции обезбедени од LMDB: околина и бази на податоци, клучеви и вредности, трансакции и курсори.

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

Сите функции во јавното LMDB API го враќаат резултатот од нивната работа во форма на код за грешка, но во сите последователни списоци неговата верификација е испуштена заради краткост. Во пракса, ние дури и користевме свој за да комуницираме со складиштето вилушка C++ обвивки lmdbxx, во кој грешките се материјализираат како исклучоци на C++.

Како најбрз начин за поврзување на LMDB со проект за iOS или macOS, го предлагам мојот CocoaPod POSLMDB.

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

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

Структура MDB_env е складиштето на внатрешната состојба на LMDB. Семејство на функции со префикс mdb_env ви овозможува да конфигурирате некои од неговите својства. Во наједноставниот случај, иницијализацијата на моторот изгледа вака.

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

Во апликацијата Mail.ru Cloud, ги сменивме стандардните вредности на само два параметри.

Првата е големината на виртуелниот адресен простор на кој е мапирана датотеката за складирање. За жал, дури и на ист уред, специфичната вредност може значително да варира од старт до старт. За да се земе предвид оваа карактеристика на iOS, максималниот волумен на складирање се избира динамички. Почнувајќи од одредена вредност, таа секвенцијално се преполовува до функцијата mdb_env_open нема да врати резултат различен од ENOMEM. Во теорија, постои и спротивен начин - прво доделете минимум меморија на моторот, а потоа, кога ќе се примат грешки, MDB_MAP_FULL, зголемете го. Сепак, тоа е многу повеќе трнливо. Причината е што постапката за прераспределба на меморијата (remap) со користење на функцијата mdb_env_set_map_size ги поништува сите ентитети (курсори, трансакции, клучеви и вредности) претходно добиени од моторот. Земајќи го предвид овој пресврт на настаните во кодот ќе доведе до негова значајна компликација. Ако, сепак, виртуелната меморија ви е многу важна, тогаш ова може да биде причина да погледнете одблизу на вилушката што отиде далеку напред MDBX, каде што меѓу најавените функции има „автоматско прилагодување на големината на базата на податоци при летот“.

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

Бази на податоци

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

MDB_txn *txn;​
MDB_dbi dbi;​
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn);​
mdb_dbi_open(txn, NULL, MDB_CREATE, &dbi);​
mdb_txn_abort(txn);

Навистина, трансакцијата во LMDB е ентитет за складирање, а не одредена база на податоци. Овој концепт ви овозможува да вршите атомски операции на ентитети лоцирани во различни бази на податоци. Во теорија, ова ја отвора можноста за моделирање на табели во форма на различни бази на податоци, но едно време тргнав по друг пат, детално опишан подолу.

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

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

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

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

Трансакција

Структурата на трансакцијата е детално опишана во претходното поглавје, па овде накратко ќе ги повторам нивните главни својства:

1. Ги поддржува сите основни својства Киселина: атомност, конзистентност, изолација и доверливост. Не можам да не забележам дека има грешка во однос на издржливоста на macOS и iOS што беше поправена во MDBX. Можете да прочитате повеќе во нивните README.
2. Пристапот кон повеќенишки е опишан со шемата „еден писател / повеќе читатели“. Писателите меѓусебно се блокираат, но не ги блокирајте читателите. Читателите не ги блокираат писателите или едни со други.
3. Поддршка за вгнездени трансакции.
4. Поддршка за мултиверзии.

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

Додавање тест запис

MDB_env *env;
MDB_dbi dbi;
MDB_txn *txn;

mdb_env_create(&env);
mdb_env_open(env, "./testdb", MDB_NOTLS, 0664);

mdb_txn_begin(env, NULL, 0, &txn);
mdb_dbi_open(txn, NULL, 0, &dbi);
mdb_txn_abort(txn);

char k = 'k';
MDB_val key;
key.mv_size = sizeof(k);
key.mv_data = (void *)&k;

int v = 997;
MDB_val value;
value.mv_size = sizeof(v);
value.mv_data = (void *)&v;

mdb_txn_begin(env, NULL, 0, &txn);
mdb_put(txn, dbi, &key, &value, MDB_NOOVERWRITE);
mdb_txn_commit(txn);

MDB_txn *txn1, *txn2, *txn3;
MDB_val val;

// Открываем 2 транзакции, каждая из которых смотрит
// на версию базы данных с одной записью.
mdb_txn_begin(env, NULL, 0, &txn1); // read-write
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn2); // read-only

// В рамках первой транзакции удаляем из базы данных существующую в ней запись.
mdb_del(txn1, dbi, &key, NULL);
// Фиксируем удаление.
mdb_txn_commit(txn1);

// Открываем третью транзакцию, которая смотрит на
// актуальную версию базы данных, где записи уже нет.
mdb_txn_begin(env, NULL, MDB_RDONLY, &txn3);
// Убеждаемся, что запись по искомому ключу уже не существует.
assert(mdb_get(txn3, dbi, &key, &val) == MDB_NOTFOUND);
// Завершаем транзакцию.
mdb_txn_abort(txn3);

// Убеждаемся, что в рамках второй транзакции, открытой на момент
// существования записи в базе данных, её всё ещё можно найти по ключу.
assert(mdb_get(txn2, dbi, &key, &val) == MDB_SUCCESS);
// Проверяем, что по ключу получен не абы какой мусор, а валидные данные.
assert(*(int *)val.mv_data == 997);
// Завершаем транзакцию, работающей хоть и с устаревшей, но консистентной базой данных.
mdb_txn_abort(txn2);

Ви препорачувам да го пробате истиот трик со SQLite и да видите што ќе се случи.

Мултиверзијата носи многу убави поволности во животот на развивачот на iOS. Користејќи го ова својство, можете лесно и природно да ја прилагодите брзината на ажурирање на изворот на податоци за формите на екранот, врз основа на размислувањата за корисничкото искуство. На пример, да земеме карактеристика на апликацијата Mail.ru Cloud, како што е автоматско вчитување содржина од медиумската галерија на системот. Со добра врска, клиентот може да додаде неколку фотографии во секунда на серверот. Ако ажурирате по секое преземање UICollectionView со медиумска содржина во облакот на корисникот, можете да заборавите околу 60 fps и непречено лизгање за време на овој процес. За да спречите чести ажурирања на екранот, треба некако да ја ограничите брзината со која податоците се менуваат во основата UICollectionViewDataSource.

Ако базата на податоци не поддржува мултиверзија и ви дозволува да работите само со моменталната моментална состојба, тогаш за да креирате временски стабилна слика од податоците, треба да ја копирате или во некоја структура на податоци во меморијата или во привремена табела. Секој од овие пристапи е многу скап. Во случај на складирање во меморијата, добиваме трошоци и во меморијата, предизвикани од складирање на конструирани објекти, и со време, поврзани со непотребни ORM трансформации. Што се однесува до привремената маса, ова е уште поскапо задоволство, има смисла само во нетривијални случаи.

Мултиверзивното решение на LMDB го решава проблемот со одржување на стабилен извор на податоци на многу елегантен начин. Доволно е само да се отвори трансакција и Voila - додека не го завршиме, се гарантира дека сетот на податоци ќе биде фиксиран. Логиката за неговата брзина на ажурирање сега е целосно во рацете на слојот за презентација, без значајни ресурси.

Покажувачи

Покажувачите обезбедуваат механизам за уредно повторување преку паровите клуч-вредност преку преминување на Б-дрвото. Без нив, би било невозможно ефективно да се моделираат табелите во базата на податоци, на кои сега се обраќаме.

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

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

Шема на табела

Едно од вообичаените сценарија за кое треба да се приспособи структура на табела со дрво на папки е изборот на сите елементи лоцирани во даден директориум Список на соседството. За да се имплементира на врвот на складиштето со вредност на клучеви, неопходно е да се подредат клучевите на датотеките и папките на таков начин што тие се групирани врз основа на нивното членство во родителскиот директориум. Покрај тоа, за да се прикаже содржината на директориумот во форма позната на корисникот на Windows (прво папки, потоа датотеки, и двете подредени по азбучен ред), неопходно е да се вклучат соодветните дополнителни полиња во клучот.

​Сликата подолу покажува како, врз основа на задачата, може да изгледа претставата на клучевите во форма на бајт низа. Бајтите со идентификаторот на матичниот именик (црвено) се ставаат прво, потоа со типот (зелено) и во опашката со името (сино) Подредени според стандардниот LMDB според лексикографски редослед потребен начин. Секвенцијално поминување на копчињата со истиот црвен префикс ни ги дава нивните поврзани вредности по редоследот што треба да се прикажат во корисничкиот интерфејс (десно), без да бара дополнителна пост-обработка.

Сериски копчиња и вредности

Во светот се измислени многу методи за серијалирање на објекти. Бидејќи немавме други барања освен брзината, го избравме најбрзиот можен за себе - депонија од меморијата окупирана од примерок од јазичната структура C Така, клучот на елементот на директориумот може да се моделира со следнава структура NodeKey.

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

За да заштедите NodeKey во складиште потребни во објектот MDB_val поставете го покажувачот на податоци на адресата на почетокот на структурата и пресметајте ја нивната големина со функцијата sizeof.

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

Во првото поглавје за критериумите за избор на бази на податоци, го спомнав минимизирањето на динамичките распределби во операциите на CRUD како важен фактор за избор. Код на функција serialize покажува како во случајот на LMDB тие можат целосно да се избегнат при вметнување на нови записи во базата на податоци. Дојдовната низа бајти од серверот прво се трансформира во структури на стек, а потоа тие тривијално се фрлаат во складиштето. Имајќи предвид дека исто така нема динамични алокации во LMDB, можете да добиете фантастична ситуација според стандардите на iOS - користете само стек меморија за да работите со податоци по целата патека од мрежата до дискот!

Клучеви за подредување со бинарен компаратор

Односот за редослед на клучеви е одреден со посебна функција наречена компаратор. Бидејќи моторот не знае ништо за семантиката на бајтите што ги содржат, стандардниот компаратор нема друг избор освен да ги распореди копчињата по лексикографски редослед, прибегнувајќи кон споредба од бајт по бајт. Користењето за организирање структури е слично на бричење со секира за сечкање. Меѓутоа, во едноставни случаи овој метод го сметам за прифатлив. Алтернативата е опишана подолу, но овде ќе забележам неколку гребла расфрлани по оваа патека.

Првото нешто што треба да се запамети е мемориското претставување на примитивните типови на податоци. Така, на сите уреди на Apple, целобројните променливи се зачувуваат во формат Малиот Ендијан. Ова значи дека најмалку значајниот бајт ќе биде лево и нема да биде возможно да се сортираат цели броеви користејќи споредба од бајт по бајт. На пример, обидот да го направите ова со множество броеви од 0 до 511 ќе го дадете следниот резултат.

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

За да се реши овој проблем, цели броеви мора да се складираат во клучот во формат соодветен за споредувачот на бајти-бајти. Функциите од семејството ќе ви помогнат да ја извршите потребната трансформација hton* (особено htons за двобајтни броеви од примерот).

Форматот за претставување на низи во програмирањето е, како што знаете, целина историја. Ако семантиката на низите, како и кодирањето што се користи за нивно претставување во меморијата, сугерира дека може да има повеќе од еден бајт по знак, тогаш подобро е веднаш да се напушти идејата за користење на стандарден компаратор.

Втората работа што треба да се има на ум е принципи на усогласување компајлер на поле за структура. Поради нив, бајти со вредности на ѓубре може да се формираат во меморијата помеѓу полињата, што, се разбира, го прекинува сортирањето бајт-бајт. За да го елиминирате ѓубрето, треба или да ги декларирате полињата по строго дефиниран редослед, имајќи ги предвид правилата за усогласување или да го користите атрибутот во декларацијата за структурата packed.

Нарачување клучеви со надворешен компаратор

Клучната логика за споредба може да биде премногу сложена за бинарен компаратор. Една од многуте причини е присуството на технички полиња во структурите. Ќе го илустрирам нивното појавување користејќи го примерот на клуч за елемент на директориумот што ни е веќе познат.

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

И покрај неговата едноставност, во огромното мнозинство на случаи троши премногу меморија. Баферот за името зафаќа 256 бајти, иако во просек имињата на датотеките и папките ретко надминуваат 20-30 знаци.

Една од стандардните техники за оптимизирање на големината на записот е да се „отсече“ до вистинската големина. Неговата суштина е дека содржината на сите полиња со променлива должина се складира во бафер на крајот од структурата, а нивните должини се складираат во посебни променливи.​ Според овој пристап, клучот NodeKey се трансформира на следниов начин.

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

Понатаму, кога се серијализира, големината на податоците не е одредена sizeof целата структура, а големината на сите полиња е фиксна должина плус големината на всушност користениот дел од баферот.

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

Како резултат на рефакторирањето, добивме значителни заштеди во просторот окупиран од клучеви. Сепак, поради техничката област nameLength, стандардниот бинарен компаратор повеќе не е соодветен за споредба на клучеви. Ако не го замениме со наше, тогаш должината на името ќе биде поприоритетен фактор при сортирањето од самото име.

LMDB овозможува секоја база на податоци да има своја функција за споредба на клучеви. Ова е направено со помош на функцијата mdb_set_compare строго пред отворањето. Од очигледни причини, не може да се менува во текот на целиот живот на базата на податоци. Компараторот добива два копчиња во бинарен формат како влез, а на излезот го враќа споредбениот резултат: помал од (-1), поголем од (1) или еднаков на (0). Псевдокод за NodeKey изгледа така.

int compare(MDB_val * const a, MDB_val * const b) {​
    NodeKey * const aKey = (NodeKey * const)a->mv_data;​
    NodeKey * const bKey = (NodeKey * const)b->mv_data;​
    return // ...
}​

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

Сериски вредности

LMDB работи исклучително интензивно со клучевите на зачуваните записи. Нивната споредба меѓу себе се случува во рамките на секоја применета операција, а перформансите на целото решение зависи од брзината на компараторот. Во идеален свет, стандардниот бинарен компаратор треба да биде доволен за споредување на клучевите, но ако треба да користите свои, тогаш постапката за десериализација на клучевите во него треба да биде што е можно побрза.

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

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

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

За да се имплементира во јазикот C, одредени полиња на наследниците се ставаат во посебни структури, а нивната поврзаност со основната се одредува преку поле на тип унија. Вистинската содржина на унијата е специфицирана преку типот на технички атрибут.

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

Додавање и ажурирање записи

Серискиот клуч и вредноста може да се додадат во продавницата. За да го направите ова, користете ја функцијата mdb_put.

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

Во фазата на конфигурација, на складирањето може да му се дозволи или да му се забрани складирање на повеќе записи со истиот клуч. Ако кршењето може да се случи само како резултат на грешка во кодот, тогаш можете да се заштитите од тоа со наведување на знамето NOOVERWRITE.

Читање записи

За да читате записи во LMDB, користете ја функцијата mdb_get. Ако парот клуч-вредност е претставен со претходно исфрлени структури, тогаш оваа постапка изгледа вака.

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

Презентираниот список покажува како сериизацијата преку структурната депонија ви овозможува да се ослободите од динамичните алокации не само при пишување, туку и при читање податоци. Произлезено од функцијата mdb_get покажувачот гледа точно во адресата на виртуелната меморија каде што базата на податоци ја чува бајтската претстава на објектот. Всушност, добиваме еден вид ORM кој обезбедува многу висока брзина на читање податоци речиси бесплатно. И покрај сета убавина на пристапот, неопходно е да се запамети неколку карактеристики поврзани со него.

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

Конечно, уште една карактеристика е толку подмолна што откривањето на нејзината суштина не се вклопува само во друг пасус. Во поглавјето за Б-дрвото, дадов дијаграм за тоа како неговите страници се распоредени во меморијата. Од ова произлегува дека адресата на почетокот на баферот со сериски податоци може да биде апсолутно произволна. Поради ова, покажувачот кон нив доби во структурата 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). На АРМ може да го имате истиот ефект постигне и користејќи го атрибутот спакуван. Имајќи предвид дека помага и за оптимизирање на просторот окупиран од конструкцијата, овој метод ми се чини претпочитан, иако приводит до зголемување на трошоците за операциите за пристап до податоци.

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

Прашања за опсег

За повторување преку група записи, LMDB обезбедува апстракција на курсорот. Ајде да погледнеме како да работиме со него користејќи го примерот на табела со метаподатоци за кориснички облак што веќе ни се познати.

Како дел од прикажувањето на список на датотеки во директориумот, неопходно е да се најдат сите клучеви со кои се поврзани неговите детски датотеки и папки. Во претходните потсекции ги подредивме клучевите NodeKey така што тие се првенствено наредени според ID на родителскиот именик. Така, технички, задачата за преземање на содржината на папката се сведува на поставување на курсорот на горната граница на групата копчиња со даден префикс и потоа повторување до долната граница.

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

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

За среќа, LMDB API обезбедува ефикасен начин за првично позиционирање на курсорот За да го направите ова, треба да генерирате клуч чија вредност е очигледно помала или еднаква на клучот што се наоѓа на горната граница на интервалот. На пример, во однос на листата на сликата погоре, можеме да направиме клуч во кој полето parentId ќе биде еднакво на 2, а сите останати се полни со нули. Таквото делумно пополнето копче се доставува до влезот на функцијата mdb_cursor_get што укажува на операцијата MDB_SET_RANGE.

NodeKey upperBoundSearchKey = {​
    .parentId = 2,​
    .type = 0,​
    .nameLength = 0​
};​
MDB_val value, key = serialize(upperBoundSearchKey);​
MDB_cursor *cursor;​
mdb_cursor_open(..., &cursor);​
mdb_cursor_get(cursor, &key, &value, MDB_SET_RANGE);

Ако се најде горната граница на група клучеви, тогаш повторуваме над неа додека не се сретнеме или клучот не се сретне со друг parentId, или клучевите воопшто нема да се потрошат

do {​
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);​
    // processing...​
} while (MDB_NOTFOUND != rc && // check end of table​
         IsTargetKey(key));    // check end of keys group​​

Она што е убаво е што како дел од повторувањето користејќи mdb_cursor_get, го добиваме не само клучот, туку и вредноста. Ако, за да ги исполните условите за земање примероци, треба, меѓу другото, да ги проверите полињата од вредносниот дел на записот, тогаш тие се доста достапни без дополнителни гестови.

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

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

​

Меѓутоа, во реалниот живот ретко е можно да се помине со толку малку крвопролевање. Често во базата на податоци се бара, прво, да има неколку табели, и второ, да се прават селекции во нив по редослед различен од примарниот клуч. Овој последен дел е посветен на прашањата за нивното создавање и меѓусебно поврзување.

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

Облак апликацијата има дел „Галерија“. Прикажува медиумска содржина од целиот облак, подредени по датум. За оптимално спроведување на таков избор, веднаш до главната табела треба да креирате друга со нов тип на клучеви. Тие ќе содржат поле со датумот на креирање на датотеката, што ќе дејствува како примарен критериум за сортирање. Бидејќи новите клучеви се однесуваат на истите податоци како и клучевите во главната табела, тие се нарекуваат индексни клучеви. На сликата подолу тие се означени со портокалова боја.

Со цел да се одделат клучевите на различни табели едни од други во истата база на податоци, на сите им беше додадено дополнително техничко поле tableId. Со тоа што ќе го направиме највисок приоритет за сортирање, ќе постигнеме групирање на клучеви прво по табели, а во табели - според нашите сопствени правила.

Индексниот клуч ги упатува истите податоци како примарниот клуч. Директната имплементација на ова својство преку поврзување со него копија од вредносниот дел од примарниот клуч не е оптимална од неколку гледни точки:

1. Во однос на зафатениот простор, метаподатоците може да бидат доста богати.
2. Од гледна точка на изведба, бидејќи при ажурирање на метаподатоците на јазол, ќе треба да ги преработите со помош на два копчиња.
3. Од гледна точка на поддршка на кодот, ако заборавиме да ги ажурираме податоците за еден од клучевите, ќе добиеме неостварлива грешка со недоследност на податоците во складирањето.

Следно, ќе разгледаме како да ги отстраниме овие недостатоци.

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

Моделот е добро прилагоден за поврзување на табелата со индекси со главната табела „клуч како вредност“. Како што сугерира неговото име, вредносниот дел од индексот е копија од вредноста на примарниот клуч. Овој пристап ги елиминира сите горенаведени недостатоци поврзани со складирање на копија од вредносниот дел од примарниот запис. Единствениот трошок е што за да се добие вредност по индексен клуч, треба да направите 2 барања во базата на податоци наместо едно. Шематски, добиената шема на базата на податоци изгледа вака.

Друг модел за организирање на односите помеѓу табелите е „непотребен клуч“. Нејзината суштина е да се додадат дополнителни атрибути на клучот, кои се потребни не за сортирање, туку за повторно создавање на поврзаниот клуч Во апликацијата Mail.ru Cloud има вистински примери за негова употреба, сепак, со цел да се избегне длабоко нурнување во. Во контекст на специфичните рамки за iOS, ќе дадам фиктивен, но појасен пример

Мобилните клиенти во Cloud имаат страница што ги прикажува сите датотеки и папки што корисникот ги споделил со други луѓе. Бидејќи има релативно малку такви датотеки и има многу различни видови конкретни информации за публицитетот поврзани со нив (кому му е дозволен пристап, со какви права итн.), нема да биде рационално да се оптоварува вредносниот дел од запишете во главната табела со него. Меѓутоа, ако сакате да прикажувате такви датотеки офлајн, сепак треба да ги зачувате некаде. Природно решение е да се создаде посебна табела за тоа. На дијаграмот подолу, неговиот клуч е со префикс „P“, а заштитното место „прописно име“ може да се замени со поконкретната вредност „јавни информации“.​

Сите уникатни метаподатоци, заради складирање на кои е креирана нова табела, се ставаат во вредносниот дел од записот. Во исто време, не сакате да ги дуплирате податоците за датотеките и папките што се веќе зачувани во главната табела. Наместо тоа, вишокот податоци се додаваат на копчето „P“ во форма на полињата „ID на јазол“ и „временски печат“. Благодарение на нив, можете да конструирате индексен клуч, од кој можете да добиете примарен клуч, од кој, конечно, можете да добиете метаподатоци за јазлите.

Заклучок

Резултатите од имплементацијата на LMDB ги оценуваме позитивно. После тоа, бројот на замрзнувања на апликации се намали за 30%.

Резултатите од сработеното одекнаа надвор од тимот на iOS. Во моментов, еден од главните секции „Датотеки“ во апликацијата Андроид исто така се префрли на користење на LMDB, а други делови се на пат. Јазикот C, во кој е имплементирана продавницата за клучеви со вредност, беше добра помош за првично да се создаде рамка за апликација околу неа меѓу-платформа во C++. Беше користен генератор на код за беспрекорно поврзување на добиената библиотека C++ со кодот на платформата во Objective-C и Kotlin Џини од Dropbox, но тоа е сосема друга приказна.

Извор: www.habr.com