2019 թվականի աշնանը Mail.ru Cloud iOS թիմում տեղի ունեցավ երկար սպասված իրադարձություն։ Հավելվածի վիճակի մշտական ​​պահպանման հիմնական տվյալների բազան շատ էկզոտիկ է դարձել բջջային աշխարհի համար Lightning Հիշողության քարտեզագրված տվյալների բազա (LMDB): Կտրվածքի տակ մենք ձեզ առաջարկում ենք դրա մանրամասն ակնարկը չորս մասից: Նախ, եկեք խոսենք նման ոչ տրիվիալ և դժվար ընտրության պատճառների մասին: Այնուհետև մենք կշարունակենք դիտարկել LMDB ճարտարապետության հիմքում ընկած երեք սյուները՝ հիշողության քարտեզագրված ֆայլեր, B+-tree, պատճենահանման վրա գրելու մոտեցում՝ գործարքների իրականացման համար և բազմատարբերակ: Վերջապես, աղանդերի համար՝ գործնական մասը։ Դրանում մենք կդիտարկենք, թե ինչպես նախագծել և իրականացնել տվյալների բազայի սխեման մի քանի աղյուսակներով, ներառյալ ինդեքսը, ցածր մակարդակի բանալի-արժեքի API-ի վերևում:

Պարունակություն

1. Իրականացման մոտիվացիա
2. LMDB դիրքավորում
3. LMDB-ի երեք սյուները
   3.1: Կետ #1. Հիշողության քարտեզագրված ֆայլեր
   3.2: Կետ #2. B+-ծառ
   3.3: Կետ #3. Պատճենել-գրել
4. Բանալին արժեքի API-ի վերևում տվյալների սխեմայի ձևավորում
   4.1: Հիմնական աբստրակցիաներ
   4.2: Սեղանի մոդելավորում
   4.3: Աղյուսակների միջև հարաբերությունների մոդելավորում

1. Իրականացման մոտիվացիա

2015 թ.-ին մեկ տարի մենք փորձեցինք չափել, թե որքան հաճախ է մեր հավելվածի ինտերֆեյսը ուշանում: Մենք դա արեցինք մի պատճառով. Մենք ավելի հաճախակի բողոքներ ենք ստացել, որ երբեմն հավելվածը դադարում է արձագանքել օգտատիրոջ գործողություններին. կոճակները չեն կարող սեղմվել, ցուցակները չեն պտտվում և այլն։ Չափումների մեխանիկայի մասին ասաց AvitoTech-ում, ուստի այստեղ ես տալիս եմ միայն թվերի հերթականությունը:

Չափումների արդյունքները մեզ համար դարձան սառը ցնցուղ։ Պարզվեց, որ սառցակալումների պատճառով առաջացած խնդիրները շատ ավելի շատ են, քան մյուսները։ Եթե ​​մինչ այս փաստը գիտակցելը որակի հիմնական տեխնիկական ցուցիչն առանց վթարի էր, ապա ֆոկուսից հետո տեղափոխվել է առանց սառեցման վրա:

Ունենալով կառուցել վահանակ սառեցումներով և ծախսելուց հետո քանակական и որակ դրանց պատճառների վերլուծության արդյունքում պարզ դարձավ հիմնական թշնամին. Այս խայտառակության բնական արձագանքը այն աշխատանքային հոսքերի մեջ մղելու բուռն ցանկությունն էր: Այս խնդիրը համակարգված լուծելու համար մենք դիմեցինք բազմաթելային ճարտարապետության՝ հիմնված թեթև դերասանների վրա: Ես այն նվիրեցի iOS-ի աշխարհի համար հարմարեցմանը երկու թել հավաքական Twitter-ում և հոդված Habré-ի մասին. Որպես ընթացիկ պատմվածքի մաս՝ ես ուզում եմ ընդգծել որոշման այն կողմերը, որոնք ազդել են տվյալների բազայի ընտրության վրա։

Համակարգի կազմակերպման դերասան մոդելը ենթադրում է, որ բազմալարայինությունը դառնում է նրա երկրորդ էությունը: Դրանում գտնվող մոդելային օբյեկտները սիրում են անցնել հոսքի սահմանները: Եվ նրանք դա անում են ոչ թե երբեմն և այստեղ և այնտեղ, այլ գրեթե անընդհատ և ամենուր

Տվյալների բազան ներկայացված դիագրամի հիմնաքարային բաղադրիչներից մեկն է: Նրա հիմնական խնդիրն է իրականացնել մակրոպատկերը Համօգտագործվող տվյալների բազա. Եթե ​​ձեռնարկության աշխարհում այն ​​օգտագործվում է ծառայությունների միջև տվյալների համաժամացման կազմակերպման համար, ապա դերասանական ճարտարապետության դեպքում՝ տվյալներ թելերի միջև: Այսպիսով, մեզ անհրաժեշտ էր տվյալների բազա, որը նույնիսկ նվազագույն դժվարություններ չառաջացնի դրա հետ բազմաշերտ միջավայրում աշխատելիս: Մասնավորապես, դա նշանակում է, որ դրանից ստացված օբյեկտները պետք է լինեն առնվազն թելերի համար անվտանգ և իդեալականորեն ամբողջովին անփոփոխ: Ինչպես գիտեք, վերջինս կարող է օգտագործվել միաժամանակ մի քանի թելերից՝ առանց որևէ կողպման դիմելու, ինչը բարենպաստ ազդեցություն է ունենում աշխատանքի վրա։

Երկրորդ կարևոր գործոնը, որն ազդեց տվյալների բազայի ընտրության վրա, մեր ամպային API-ն էր: Այն ոգեշնչված էր git-ի կողմից ընդունված համաժամացման մոտեցմամբ: Նրա պես մենք նպատակադրվեցինք օֆլայն-առաջին API, որն ավելի քան տեղին է թվում ամպային հաճախորդների համար: Ենթադրվում էր, որ նրանք միայն մեկ անգամ դուրս կբերեն ամպի ամբողջական վիճակը, իսկ հետո դեպքերի ճնշող մեծամասնությունում համաժամացումը տեղի կունենա փոփոխությունների միջոցով: Ավաղ, այս հնարավորությունը դեռ միայն տեսական գոտում է, և հաճախորդները գործնականում չեն սովորել, թե ինչպես աշխատել կարկատանների հետ: Դրա համար կան մի շարք օբյեկտիվ պատճառներ, որոնց ներածությունը չուշացնելու համար կթողնենք փակագծեր։ Այժմ, այն, ինչ շատ ավելի հետաքրքիր է, դասի ուսանելի եզրակացություններն են այն մասին, թե ինչ է տեղի ունենում, երբ API-ն ասում է «A», իսկ դրա սպառողը չի ասում «B»:

Այսպիսով, եթե պատկերացնեք git-ը, որը pull հրամանը կատարելիս, տեղային նկարի վրա patches կիրառելու փոխարեն, իր ամբողջական վիճակը համեմատում է ամբողջական սերվերի վիճակի հետ, ապա դուք բավականին ճշգրիտ պատկերացում կունենաք, թե ինչպես է համաժամացումը տեղի ունենում ամպում: հաճախորդներ. Հեշտ է կռահել, որ այն իրականացնելու համար հարկավոր է հիշողության մեջ հատկացնել երկու DOM ծառեր՝ բոլոր սերվերի և տեղական ֆայլերի մասին մետա-տեղեկատվությամբ: Ստացվում է, որ եթե օգտատերը ամպի մեջ պահում է 500 հազար ֆայլ, ապա դրա համաժամացման համար անհրաժեշտ է վերստեղծել և ոչնչացնել 1 միլիոն հանգույց ունեցող երկու ծառ։ Բայց յուրաքանչյուր հանգույց իրենից ներկայացնում է ենթաօբյեկտների գրաֆիկ պարունակող ագրեգատ: Այս լույսի ներքո պրոֆիլավորման արդյունքները սպասելի էին: Պարզվեց, որ նույնիսկ առանց միաձուլման ալգորիթմը հաշվի առնելու, հսկայական քանակությամբ փոքր օբյեկտների ստեղծման և հետագայում ոչնչացնելու գործընթացը բավականին կոպեկ արժե: Իրավիճակը սրվում է նրանով, որ հիմնական համաժամացման գործողությունը ներառված է մեծ թվով: օգտագործողի սկրիպտների: Արդյունքում մենք ամրագրում ենք տվյալների բազայի ընտրության երկրորդ կարևոր չափանիշը՝ առանց օբյեկտների դինամիկ տեղաբաշխման CRUD գործողություններ իրականացնելու հնարավորությունը:

Մյուս պահանջները ավելի ավանդական են, և դրանց ամբողջ ցանկը հետևյալն է.

1. Թելի անվտանգություն.
2. Բազմամշակում. Թելադրված է տվյալների բազայի նույն օրինակն օգտագործելու ցանկությամբ՝ վիճակը համաժամեցնելու ոչ միայն թելերի, այլ նաև հիմնական հավելվածի և iOS ընդլայնումների միջև:
3. Պահված սուբյեկտները որպես չփոփոխվող օբյեկտներ ներկայացնելու ունակություն
4. Չկան դինամիկ տեղաբաշխումներ CRUD գործառնությունների շրջանակներում:
5. Գործարքի աջակցություն հիմնական հատկությունների համար ACIDատոմականություն, հետևողականություն, մեկուսացում և հուսալիություն:
6. Արագություն ամենատարածված դեպքերի վրա:

Պահանջների այս փաթեթով SQLite-ը եղել և մնում է լավ ընտրություն: Այնուամենայնիվ, այլընտրանքների ուսումնասիրության շրջանակում ես հանդիպեցի մի գրքի «Սկսել LevelDB-ի հետ». Նրա ղեկավարությամբ գրվել է չափանիշ, որը համեմատում է աշխատանքի արագությունը տարբեր տվյալների բազաների հետ իրական ամպային սցենարներում: Արդյունքը գերազանցեց մեր ամենախիստ սպասումները: Ամենահայտնի դեպքերում՝ բոլոր ֆայլերի դասավորված ցանկի վրա կուրսոր ստանալը և տվյալ գրացուցակի բոլոր ֆայլերի տեսակավորված ցուցակը, LMDB-ն 10 անգամ ավելի արագ է ստացվել, քան SQLite-ը: Ընտրությունն ակնհայտ դարձավ.

2. LMDB դիրքավորում

LMDB-ն շատ փոքր գրադարան է (ընդամենը 10K տող), որն իրականացնում է տվյալների բազաների ամենացածր հիմնարար շերտը՝ պահեստավորումը:

Վերոնշյալ դիագրամը ցույց է տալիս, որ համեմատել LMDB-ն SQLite-ի հետ, որը նաև իրականացնում է ավելի բարձր մակարդակներ, ընդհանուր առմամբ ավելի ճիշտ չէ, քան SQLite-ը Core Data-ով: Ավելի ազնիվ կլիներ նշել նույն պահեստային շարժիչները որպես հավասար մրցակիցներ՝ BerkeleyDB, LevelDB, Sophia, RocksDB և այլն: Կան նույնիսկ զարգացումներ, որտեղ LMDB-ն գործում է որպես SQLite-ի պահեստավորման շարժիչի բաղադրիչ: Առաջին նման փորձը եղել է 2012թ ծախսեց LMDB-ի կողմից Հովարդ Չու. Արդյունքները Այնքան ինտրիգային ստացվեց, որ նրա նախաձեռնությունն ընդունվեց OSS-ի էնտուզիաստների կողմից և դրա շարունակությունը գտավ անձի մեջ. LumoSQL. 2020 թվականի հունվարին այս նախագծի հեղինակը Դեն Շիրերն էր ներկայացված այն LinuxConfAu-ում:

LMDB-ն հիմնականում օգտագործվում է որպես կիրառական տվյալների բազաների շարժիչ: Գրադարանը իր տեսքը պարտական ​​է մշակողներին OpenLDAP- ը, ովքեր խիստ դժգոհ էին BerkeleyDB-ից՝ որպես իրենց նախագծի հիմք: Սկսած համեստ գրադարանից բծառ, Հովարդ Չուն կարողացավ ստեղծել մեր ժամանակի ամենահայտնի այլընտրանքներից մեկը։ Նա իր շատ թույն ռեպորտաժը նվիրեց այս պատմությանը, ինչպես նաև LMDB-ի ներքին կառուցվածքին։ «Կայծակ հիշողության քարտեզագրված տվյալների շտեմարան». Պահեստային օբյեկտ նվաճելու լավ օրինակ է կիսվել Լեոնիդ Յուրիևի կողմից (aka յլեո) Positive Technologies-ից՝ Highload 2015-ի իր զեկույցում «LMDB շարժիչը հատուկ չեմպիոն է». Դրանում նա խոսում է LMDB-ի մասին ReOpenLDAP-ի ներդրման համանման առաջադրանքի համատեքստում, և LevelDB-ն արդեն ենթարկվել է համեմատական ​​քննադատության։ Իրականացման արդյունքում Positive Technologies-ը նույնիսկ ակտիվ զարգացող պատառաքաղ ունեցավ MDBX շատ համեղ հատկանիշներով, օպտիմալացումներով և սխալների շտկումներ.

LMDB-ն հաճախ օգտագործվում է որպես պահեստային պահոց: Օրինակ՝ Mozilla Firefox բրաուզերը ընտրեց այն մի շարք կարիքների համար, և, սկսած 9-րդ տարբերակից, Xcode-ից նախընտրելի իր SQLite-ը՝ ինդեքսները պահելու համար:

Շարժիչը իր հետքն է թողել նաև բջջային զարգացման աշխարհում: Դրա օգտագործման հետքերը կարող են լինել գտնել iOS հաճախորդում Telegram-ի համար: LinkedIn-ն ավելի հեռուն գնաց և ընտրեց LMDB-ն որպես լռելյայն պահոց իր հայրենական տվյալների քեշավորման Rocket Data շրջանակի համար, որի մասին պատմեց իր հոդվածում 2016 թ.

LMDB-ն հաջողությամբ պայքարում է արևի տակ տեղ գտնելու այն խորշում, որը թողել է BerkeleyDB-ն Oracle-ի վերահսկողության տակ անցնելուց հետո: Գրադարանը սիրված է իր արագությամբ և հուսալիությամբ, նույնիսկ համեմատած իր հասակակիցների հետ: Ինչպես գիտեք, անվճար լանչեր չկան, և ես կցանկանայի ընդգծել այն փոխզիջումը, որը դուք ստիպված կլինեք հանդիպել LMDB-ի և SQLite-ի միջև ընտրություն կատարելիս: Վերոհիշյալ դիագրամը հստակ ցույց է տալիս, թե ինչպես է ավելացել արագությունը: Նախ, մենք չենք վճարում սկավառակի պահեստի վերևում գտնվող աբստրակցիայի լրացուցիչ շերտերի համար: Հասկանալի է, որ լավ ճարտարապետությունը դեռ չի կարող անել առանց դրանց, և դրանք անխուսափելիորեն կհայտնվեն հավելվածի կոդում, բայց դրանք շատ ավելի նուրբ կլինեն: Դրանք չեն պարունակի առանձնահատկություններ, որոնք չեն պահանջվում կոնկրետ հավելվածի կողմից, օրինակ՝ աջակցություն SQL լեզվով հարցումներին: Երկրորդ, հնարավոր է դառնում օպտիմալ կերպով իրականացնել կիրառական գործողությունների քարտեզագրում սկավառակի պահեստավորման հարցումների վրա: Եթե ​​SQLite իմ աշխատանքում հիմնված է միջին հայտի միջին վիճակագրական կարիքների վրա, ապա դուք, որպես հավելվածի մշակող, քաջատեղյակ եք աշխատանքային ծանրաբեռնվածության հիմնական սցենարներին: Ավելի արդյունավետ լուծման համար դուք ստիպված կլինեք վճարել բարձր գին ինչպես սկզբնական լուծման, այնպես էլ դրա հետագա աջակցության համար:

3. LMDB-ի երեք սյուներ

Թռչնի հայացքից նայելով LMDB-ին, ժամանակն էր ավելի խորանալու: Հաջորդ երեք բաժինները նվիրված կլինեն հիմնական սյուների վերլուծությանը, որոնց վրա հիմնված է պահեստավորման ճարտարապետությունը.

1. Հիշողության քարտեզագրված ֆայլերը որպես սկավառակի հետ աշխատելու և ներքին տվյալների կառուցվածքների համաժամացման մեխանիզմ:
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 հասցեով A էջը և տեղադրվեց 4 հասցեով հիմնական հիշողության էջում:

Պատմությունը ճիշտ նույնն է հիշողության մեջ քարտեզագրված ֆայլերի դեպքում: Տրամաբանական է, որ դրանք իբր շարունակաբար և ամբողջությամբ տեղակայված են վիրտուալ հասցեների տարածքում: Այնուամենայնիվ, նրանք մտնում են ֆիզիկական հիշողություն էջ առ էջ և միայն պահանջի դեպքում: Նման էջերի փոփոխությունը համաժամացվում է սկավառակի վրա գտնվող ֆայլի հետ: Այսպիսով, դուք կարող եք կատարել ֆայլի I/O՝ պարզապես աշխատելով հիշողության բայթերի հետ. բոլոր փոփոխությունները օպերացիոն համակարգի միջուկի կողմից ավտոմատ կերպով կփոխանցվեն սկզբնաղբյուր ֆայլ:​
â € <
Ստորև բերված պատկերը ցույց է տալիս, թե ինչպես է LMDB-ն համաժամացնում իր վիճակը տարբեր գործընթացների տվյալների բազայի հետ աշխատելիս: Տարբեր գործընթացների վիրտուալ հիշողությունը նույն ֆայլի վրա քարտեզագրելով՝ մենք դե ֆակտո պարտավորեցնում ենք օպերացիոն համակարգին անցումային կերպով համաժամեցնել իրենց հասցեների տարածքների որոշ բլոկներ միմյանց հետ, որտեղ նայում է LMDB-ն:
â € <

Կարևոր նրբերանգն այն է, որ LMDB-ն լռելյայն կերպով փոփոխում է տվյալների ֆայլը գրելու համակարգի կանչի մեխանիզմի միջոցով և ցուցադրում է ֆայլը միայն կարդալու ռեժիմում: Այս մոտեցումը երկու կարևոր հետևանք ունի.

Առաջին հետևանքը բնորոշ է բոլոր օպերացիոն համակարգերին։ Դրա էությունն այն է, որ տվյալների բազան սխալ կոդով պաշտպանություն ավելացվի կանխամտածված վնասից: Ինչպես գիտեք, գործընթացի գործարկվող հրահանգներն անվճար են մուտք գործելու տվյալներ իր հասցեների տարածության ցանկացած կետից: Միևնույն ժամանակ, ինչպես նոր հիշեցինք, ֆայլը կարդալ-գրելու ռեժիմում ցուցադրելը նշանակում է, որ ցանկացած հրահանգ կարող է նաև փոփոխել այն: Եթե ​​նա դա անում է սխալմամբ՝ փորձելով, օրինակ, իրականում վերագրել զանգվածի տարրը գոյություն չունեցող ինդեքսի վրա, ապա նա կարող է պատահաբար փոխել այս հասցեի քարտեզագրված ֆայլը, ինչը կհանգեցնի տվյալների բազայի կոռուպցիայի: Եթե ​​ֆայլը ցուցադրվում է միայն կարդալու ռեժիմով, ապա համապատասխան հասցեի տարածքը փոխելու փորձը կհանգեցնի ծրագրի արտակարգ դադարեցման ազդանշանով: SIGSEGV, և ֆայլը կմնա անփոփոխ:

Երկրորդ հետևանքն արդեն հատուկ է iOS-ին։ Ոչ հեղինակը, ոչ էլ որևէ այլ աղբյուր բացահայտորեն չի նշում այն, բայց առանց դրա LMDB-ն հարմար չէր այս բջջային օպերացիոն համակարգով աշխատելու համար: Հաջորդ բաժինը նվիրված է դրա քննարկմանը:

Հիշողության քարտեզագրված ֆայլերի առանձնահատկությունները iOS-ում

2018 թվականին WWDC-ում հրաշալի զեկույց է եղել «iOS հիշողության խորը սուզում». Այն մեզ ասում է, որ iOS-ում ֆիզիկական հիշողության մեջ գտնվող բոլոր էջերը 3 տեսակներից մեկն են՝ կեղտոտ, սեղմված և մաքուր:

Մաքուր հիշողությունը էջերի հավաքածու է, որոնք կարող են առանց ցավի բեռնաթափվել ֆիզիկական հիշողությունից: Նրանց պարունակած տվյալները, ըստ անհրաժեշտության, կարող են վերաբեռնվել սկզբնական աղբյուրներից: Այս կատեգորիային են պատկանում միայն կարդալու հիշողության քարտեզագրված ֆայլերը: iOS-ը չի վախենում ցանկացած պահի հիշողությունից բեռնաթափել ֆայլի վրա քարտեզագրված էջերը, քանի որ դրանք երաշխավորված են համաժամեցվելու սկավառակի վրա գտնվող ֆայլի հետ:
â € <
Բոլոր փոփոխված էջերը հայտնվում են կեղտոտ հիշողության մեջ, անկախ նրանից, թե դրանք ի սկզբանե որտեղ են եղել: Մասնավորապես, այս կերպ կդասակարգվեն հիշողության քարտեզագրված ֆայլերը, որոնք փոփոխվել են դրանց հետ կապված վիրտուալ հիշողության մեջ գրելու միջոցով: LMDB-ի բացում դրոշով MDB_WRITEMAP, դրանում փոփոխություններ կատարելուց հետո կարող եք դա անձամբ հաստատել

Հենց որ հավելվածը սկսում է չափազանց շատ ֆիզիկական հիշողություն զբաղեցնել, iOS-ը այն ենթարկում է կեղտոտ էջերի սեղմման: Կեղտոտ և սեղմված էջերի զբաղեցրած ընդհանուր հիշողությունը կազմում է հավելվածի, այսպես կոչված, հիշողության հետքը: Երբ այն հասնում է որոշակի շեմային արժեքի, OOM մարդասպան համակարգի դեյմոնը գալիս է գործընթացից հետո և բռնի կերպով դադարեցնում այն: Սա է iOS-ի յուրահատկությունը՝ համեմատած աշխատասեղանի օպերացիոն համակարգերի հետ։ Ի հակադրություն, հիշողության ծավալի կրճատումը՝ էջերը ֆիզիկական հիշողությունից սկավառակ փոխանակելու միջոցով, նախատեսված չէ iOS-ում: Պատճառները կարելի է միայն գուշակել: Հավանաբար, էջերը ինտենսիվորեն սկավառակ և հետ տեղափոխելու ընթացակարգը չափազանց էներգիա է ծախսում շարժական սարքերի համար, կամ iOS-ը խնայում է SSD կրիչներում բջիջների վերագրման ռեսուրսը, կամ գուցե դիզայներները գոհ չեն եղել համակարգի ընդհանուր աշխատանքից, որտեղ ամեն ինչ կա: անընդհատ փոխանակված: Ինչքան էլ որ լինի, փաստը մնում է փաստ։

Լավ նորությունն այն է, որ LMDB-ն լռելյայնորեն չի օգտագործում mmap մեխանիզմը ֆայլերը թարմացնելու համար: Սա նշանակում է, որ ցուցադրվող տվյալները iOS-ի կողմից դասակարգվում են որպես մաքուր հիշողություն և չեն նպաստում հիշողության հետքերին: Դուք կարող եք դա հաստատել՝ օգտագործելով Xcode գործիքը, որը կոչվում է VM Tracker: Ստորև ներկայացված սքրինշոթը ցույց է տալիս Cloud հավելվածի iOS վիրտուալ հիշողության վիճակը շահագործման ընթացքում: Սկզբում դրանում սկզբնավորվել են 2 LMDB օրինակներ: Առաջինին թույլատրվել է ցուցադրել իր ֆայլը 1GiB վիրտուալ հիշողության վրա, երկրորդին՝ 512MiB: Չնայած այն հանգամանքին, որ երկու պահեստներն էլ որոշակի քանակությամբ ռեզիդենտ հիշողություն են զբաղեցնում, նրանցից ոչ մեկը չի նպաստում կեղտոտ չափին:

Եվ հիմա եկել է վատ լուրերի ժամանակը: 64-բիթանոց աշխատասեղանի օպերացիոն համակարգերում փոխանակման մեխանիզմի շնորհիվ յուրաքանչյուր գործընթաց կարող է զբաղեցնել այնքան վիրտուալ հասցեի տարածք, որքան թույլ է տալիս կոշտ սկավառակի ազատ տարածությունը դրա հնարավոր փոխանակման համար: IOS-ում swap-ը սեղմումով փոխարինելը արմատապես նվազեցնում է տեսական առավելագույնը: Այժմ բոլոր կենդանի պրոցեսները պետք է տեղավորվեն հիմնական (կարդալ RAM) հիշողության մեջ, և բոլոր նրանք, որոնք չեն տեղավորվում, պետք է ստիպված լինեն դադարեցնել: Այս մասին ասվում է վերը նշվածի պես զեկույցըեւ ներս պաշտոնական փաստաթղթեր. Որպես հետևանք, iOS-ը խստորեն սահմանափակում է հիշողության քանակը, որը հասանելի է mmap-ի միջոցով հատկացնելու համար: Այստեղ այստեղ Դուք կարող եք դիտարկել հիշողության քանակի էմպիրիկ սահմանները, որոնք կարող են տեղաբաշխվել տարբեր սարքերի վրա՝ օգտագործելով այս համակարգային զանգը: Սմարթֆոնների ամենաժամանակակից մոդելներում iOS-ը դարձել է առատաձեռն 2 գիգաբայթով, իսկ iPad-ի լավագույն տարբերակներում՝ 4-ով: Գործնականում, իհարկե, պետք է կենտրոնանալ ամենացածր աջակցվող սարքերի մոդելների վրա, որտեղ ամեն ինչ շատ տխուր է: Նույնիսկ ավելի վատ, VM Tracker-ում հավելվածի հիշողության վիճակին նայելով, դուք կգտնեք, որ LMDB-ն հեռու է միակից, որը պնդում է, որ հիշողության քարտեզագրված է: Լավ կտորները խժռում են համակարգի հատկացնողները, ռեսուրսների ֆայլերը, պատկերների շրջանակները և այլ փոքր գիշատիչները:

Ելնելով Cloud-ում կատարած փորձերի արդյունքներից՝ մենք եկանք LMDB-ի կողմից հատկացված հիշողության հետևյալ փոխզիջումային արժեքներին՝ 384 մեգաբայթ 32-բիթանոց սարքերի համար և 768՝ 64-բիթանոց սարքերի համար: Այս ծավալը սպառելուց հետո ցանկացած փոփոխող գործողություն սկսում է ավարտվել կոդով MDB_MAP_FULL. Մենք դիտարկում ենք նման սխալներ, բայց դրանք այնքան փոքր են, որ այս փուլում կարող են անտեսվել։

Պահեստի կողմից հիշողության ավելցուկ սպառման ոչ ակնհայտ պատճառ կարող են լինել երկարատև գործարքները: Հասկանալու համար, թե ինչպես են այս երկու երևույթները կապված, մեզ կօգնի դիտարկելով LMDB-ի մնացած երկու սյուները:

3.2. Կետ #2. B+-ծառ

Բանալին արժեքների պահեստի վերևում գտնվող աղյուսակները նմանակելու համար դրա API-ում պետք է առկա լինեն հետևյալ գործողությունները.

1. Նոր տարրի տեղադրում:
2. Որոնել տարր տվյալ բանալիով:
3. Տարրը հեռացնելը.
4. Կրկնել ստեղների ընդմիջումներով՝ ըստ նրանց դասավորվածության:

Ամենապարզ տվյալների կառուցվածքը, որը կարող է հեշտությամբ իրականացնել բոլոր չորս գործողությունները, երկուական որոնման ծառն է: Նրա հանգույցներից յուրաքանչյուրը ներկայացնում է բանալին, որը բաժանում է երեխայի ստեղների ամբողջ ենթաբազմությունը երկու ենթածառերի: Ձախը պարունակում է նրանք, որոնք ավելի փոքր են, քան ծնողը, իսկ աջը պարունակում է նրանք, որոնք ավելի մեծ են: Բանալների պատվիրված հավաքածու ձեռք բերելը ձեռք է բերվում դասական ծառերի անցումներից մեկի միջոցով

Երկուական ծառերն ունեն երկու հիմնարար թերություններ, որոնք թույլ չեն տալիս արդյունավետ լինել որպես սկավառակի վրա հիմնված տվյալների կառուցվածք: Նախ, դրանց հավասարակշռության աստիճանը անկանխատեսելի է։ Ծառեր ձեռք բերելու զգալի ռիսկ կա, որոնցում տարբեր ճյուղերի բարձրությունները կարող են մեծապես տարբերվել, ինչը զգալիորեն վատթարացնում է որոնման ալգորիթմական բարդությունը՝ համեմատած սպասվածի հետ: Երկրորդ, հանգույցների միջև խաչաձեւ կապերի առատությունը զրկում է երկուական ծառերին տեղայնությունից հիշողության մեջ: Փակ հանգույցները (նրանց միջև կապերի առումով) կարող են տեղակայվել վիրտուալ հիշողության բոլորովին այլ էջերում: Որպես հետևանք, նույնիսկ ծառի մի քանի հարևան հանգույցների պարզ անցումը կարող է պահանջել համեմատելի թվով էջեր այցելել: Սա խնդիր է նույնիսկ այն դեպքում, երբ մենք խոսում ենք երկուական ծառերի արդյունավետության մասին՝ որպես հիշողության տվյալների կառուցվածք, քանի որ պրոցեսորի քեշում անընդհատ պտտվող էջերը էժան հաճույք չէ: Երբ խոսքը գնում է սկավառակից հանգույցների հետ կապված էջերի հաճախակի վերբերման մասին, իրավիճակը դառնում է ամբողջությամբ ողբալի,

Բ-ծառերը, լինելով երկուական ծառերի էվոլյուցիա, լուծում են նախորդ պարբերությունում նշված խնդիրները: Նախ, դրանք ինքնահավասարակշռվում են: Երկրորդ, նրանց հանգույցներից յուրաքանչյուրը բաժանում է երեխայի ստեղների հավաքածուն ոչ թե 2, այլ M կարգավորված ենթաբազմությունների, և M թիվը կարող է բավականին մեծ լինել՝ մի քանի հարյուր կամ նույնիսկ հազարների կարգի:

Դրանով իսկ.

1. Յուրաքանչյուր հանգույց պարունակում է մեծ թվով արդեն պատվիրված բանալիներ, իսկ ծառերը շատ կարճ են:
2. Ծառը ձեռք է բերում հիշողության մեջ գտնվելու վայրի հատկությունը, քանի որ արժեքով մոտ ստեղները բնականաբար գտնվում են միմյանց կողքին նույն կամ հարևան հանգույցների վրա:
3. Որոնողական գործողության ընթացքում ծառից իջնելիս տարանցիկ հանգույցների թիվը կրճատվում է:
4. Տարածքի հարցումների ընթացքում կարդացվող թիրախային հանգույցների թիվը կրճատվում է, քանի որ դրանցից յուրաքանչյուրն արդեն պարունակում է մեծ թվով պատվիրված բանալիներ։

LMDB-ն օգտագործում է B-ծառի մի տարբերակ, որը կոչվում է B+ ծառ՝ տվյալների պահպանման համար: Վերևի դիագրամը ցույց է տալիս երեք տեսակի հանգույցներ, որոնք գոյություն ունեն դրանում.

1. Վերևում արմատն է: Այն նյութականացնում է ոչ այլ ինչ, քան պահեստի ներսում տվյալների բազայի գաղափարը: Մեկ LMDB օրինակի ընթացքում դուք կարող եք ստեղծել մի քանի տվյալների բազա, որոնք կիսում են քարտեզագրված վիրտուալ հասցեների տարածքը: Նրանցից յուրաքանչյուրը սկսվում է իր արմատից:
2. Ամենացածր մակարդակում տերևներն են: Նրանք և միայն նրանք պարունակում են տվյալների բազայում պահվող բանալի-արժեք զույգեր: Ի դեպ, սա B+-ծառերի յուրահատկությունն է։ Եթե ​​սովորական B-ծառը արժեքավոր մասեր է պահում բոլոր մակարդակների հանգույցներում, ապա B+ տատանումները միայն ամենացածրն են: Այս փաստը շտկելուց հետո մենք LMDB-ում օգտագործվող ծառի ենթատիպը կկոչենք պարզապես B-ծառ:
3. Արմատի և տերևների միջև կան 0 և ավելի տեխնիկական մակարդակներ՝ նավիգացիոն (ճյուղային) հանգույցներով։ Նրանց խնդիրն է բաժանել դասավորված բանալիների հավաքածուն տերևների միջև։

Ֆիզիկապես հանգույցները նախապես որոշված ​​երկարության հիշողության բլոկներ են: Նրանց չափը օպերացիոն համակարգի հիշողության էջերի չափի բազմապատիկն է, որը մենք քննարկեցինք վերևում: Հանգույցի կառուցվածքը ներկայացված է ստորև: Վերնագիրը պարունակում է մետա տեղեկատվություն, որոնցից ամենաակնհայտը, օրինակ, ստուգիչ գումարն է: Հաջորդը գալիս է տեղեկատվություն այն օֆսեթների մասին, որոնցում գտնվում են տվյալներ ունեցող բջիջները: Տվյալները կարող են լինել կամ ստեղներ, եթե մենք խոսում ենք նավիգացիոն հանգույցների մասին, կամ ամբողջ բանալին-արժեքային զույգեր՝ տերևների դեպքում: Դուք կարող եք ավելին կարդալ ստեղծագործության էջերի կառուցվածքի մասին: «Բարձր արդյունավետության հիմնական արժեք ունեցող խանութների գնահատում».

Անդրադառնալով էջի հանգույցների ներքին բովանդակությանը, մենք հետագայում կներկայացնենք LMDB B-ծառը պարզեցված ձևով հետևյալ ձևով:

Հանգույցներով էջերը հաջորդաբար տեղադրվում են սկավառակի վրա: Ավելի բարձր համարակալված էջերը գտնվում են ֆայլի վերջում: Այսպես կոչված մետա էջը պարունակում է տեղեկատվություն այն հատուցումների մասին, որոնց միջոցով կարելի է գտնել բոլոր ծառերի արմատները: Ֆայլ բացելիս LMDB-ն սկանավորում է ֆայլը էջ առ էջ ծայրից սկիզբ՝ վավեր մետա էջի որոնման համար և դրա միջոցով գտնում առկա տվյալների բազաները։​

Այժմ, պատկերացում ունենալով տվյալների կազմակերպման տրամաբանական և ֆիզիկական կառուցվածքի մասին, մենք կարող ենք անցնել LMDB-ի երրորդ սյունին: Նրա օգնությամբ է, որ պահեստավորման բոլոր փոփոխությունները տեղի են ունենում գործարքային և միմյանցից մեկուսացված՝ տվյալների բազան որպես ամբողջություն տալով մուլտիվերսիոն հատկություն։

3.3. Կետ #3. Պատճենել-գրել

B-tree-ի որոշ գործողություններ ներառում են մի շարք փոփոխություններ նրա հանգույցներում: Օրինակներից մեկն այն հանգույցին նոր բանալի ավելացնելն է, որն արդեն հասել է իր առավելագույն հզորությանը: Այս դեպքում անհրաժեշտ է, առաջին հերթին, բաժանել հանգույցը երկու մասի, և երկրորդ՝ ավելացնել հղում դեպի նրա ծնողի նոր բողբոջող երեխա հանգույցը: Այս ընթացակարգը պոտենցիալ շատ վտանգավոր է: Եթե ​​ինչ-ինչ պատճառներով (վթար, հոսանքազրկում և այլն) տեղի ունենա շարքի փոփոխությունների միայն մի մասը, ապա ծառը կմնա անհամապատասխան վիճակում:

Տվյալների բազայի սխալների նկատմամբ հանդուրժող դարձնելու ավանդական լուծումներից մեկը B-tree-ի կողքին սկավառակի վրա տվյալների լրացուցիչ կառուցվածք ավելացնելն է՝ գործարքների գրանցամատյան, որը նաև հայտնի է որպես առաջ գրելու մատյան (WAL): Դա ֆայլ է, որի վերջում նախատեսվող գործողությունը գրված է խիստ նախքան B-tree-ը փոփոխելը: Այսպիսով, եթե տվյալների կոռուպցիան հայտնաբերվի ինքնաախտորոշման ժամանակ, տվյալների բազան խորհրդակցում է գրանցամատյանի հետ՝ իրեն կարգի բերելու համար:

LMDB-ն որպես սխալների հանդուրժողականության մեխանիզմ ընտրել է մեկ այլ մեթոդ, որը կոչվում է պատճենահանում գրելու վրա: Դրա էությունն այն է, որ գոյություն ունեցող էջի տվյալները թարմացնելու փոխարեն նախ այն ամբողջությամբ պատճենում է և բոլոր փոփոխությունները կատարում պատճենում։​

Այնուհետև, որպեսզի թարմացված տվյալները հասանելի լինեն, անհրաժեշտ է փոխել հղումը դեպի այն հանգույցը, որն ընթացիկ է դարձել իր մայր հանգույցում։ Քանի որ դրա համար այն նույնպես պետք է փոփոխվի, այն նույնպես նախապես պատճենվում է: Գործընթացը ռեկուրսիվ կերպով շարունակվում է մինչև արմատը: Վերջին բանը, որ պետք է փոխվի, մետա էջի տվյալներն են։​

Եթե ​​թարմացման ընթացակարգի ընթացքում հանկարծ գործընթացը խափանվի, ապա կամ նոր մետա էջ չի ստեղծվի, կամ այն ​​ամբողջությամբ չի գրվի սկավառակի վրա, և դրա ստուգման գումարը սխալ կլինի: Այս երկու դեպքերից որևէ մեկում նոր էջերը անհասանելի կլինեն, բայց հին էջերը չեն տուժի: Սա վերացնում է LMDB-ի կողմից նախնական գրանցամատյան գրելու անհրաժեշտությունը տվյալների հետևողականությունը պահպանելու համար: Դե ֆակտո, վերը նկարագրված սկավառակի վրա տվյալների պահպանման կառուցվածքը միաժամանակ ստանձնում է իր գործառույթը: Գործարքների բացահայտ գրանցամատյանի բացակայությունը LMDB-ի առանձնահատկություններից մեկն է, որն ապահովում է տվյալների ընթերցման բարձր արագություն:

Ստացված դիզայնը, որը կոչվում է հավելված միայն B-tree, բնականաբար ապահովում է գործարքների մեկուսացում և բազմատեսակ: LMDB-ում յուրաքանչյուր բաց գործարք կապված է տվյալ պահին համապատասխան ծառի արմատի հետ: Քանի դեռ գործարքը չի ավարտվել, դրա հետ կապված ծառի էջերը երբեք չեն փոխվի կամ նորից օգտագործվեն տվյալների նոր տարբերակների համար: Այսպիսով, դուք կարող եք աշխատել այնքան ժամանակ, որքան ցանկանում եք, հենց տվյալ պահին համապատասխան տվյալների հավաքածուով: գործարքը բացվել է, նույնիսկ եթե պահոցը շարունակում է ակտիվորեն թարմացվել այս պահին: Սա բազմատեսակության էությունն է, որը LMDB-ն դարձնում է տվյալների իդեալական աղբյուր մեր սիրելիի համար UICollectionView. Գործարքը բացելուց հետո կարիք չկա մեծացնել հավելվածի հիշողության հետքը՝ հապճեպ կերպով ընթացիկ տվյալները մղելով հիշողության ինչ-որ կառուցվածք՝ վախենալով, որ ոչինչ չմնա: Այս առանձնահատկությունն առանձնացնում է LMDB-ն նույն SQLite-ից, որը չի կարող պարծենալ նման ամբողջական մեկուսացմամբ: Վերջիններիս մեջ բացելով երկու գործարք և դրանցից մեկի մեջ որոշակի գրառում ջնջելով՝ երկրորդ մնացածի ընթացքում այլևս հնարավոր չի լինի նույն գրառումը ստանալ։

Մետաղադրամի հակառակ կողմը վիրտուալ հիշողության պոտենցիալ զգալիորեն ավելի մեծ սպառումն է: Սլայդը ցույց է տալիս, թե ինչ տեսք կունենա տվյալների բազայի կառուցվածքը, եթե այն փոփոխվի միաժամանակ 3 բաց ընթերցման գործարքների հետ՝ դիտարկելով տվյալների բազայի տարբեր տարբերակները: Քանի որ LMDB-ն չի կարող վերօգտագործել ընթացիկ գործարքների հետ կապված արմատներից հասանելի հանգույցները, խանութը այլ ելք չունի, քան հիշողության մեջ հատկացնել ևս չորրորդ արմատ և ևս մեկ անգամ կլոնավորել դրա տակ գտնվող փոփոխված էջերը:

Այստեղ օգտակար կլինի հիշել հիշողության քարտեզագրված ֆայլերի բաժինը: Թվում է, թե վիրտուալ հիշողության հավելյալ սպառումը մեզ շատ չպետք է անհանգստացնի, քանի որ դա չի նպաստում հավելվածի հիշողության հետքին։ Սակայն միևնույն ժամանակ նշվեց, որ iOS-ը շատ ժլատ է այն հատկացնելու հարցում, և մենք չենք կարող, ինչպես սերվերի կամ աշխատասեղանի վրա, տրամադրել 1 տերաբայթանոց LMDB տարածաշրջան և ընդհանրապես չմտածել այս ֆունկցիայի մասին։ Հնարավորության դեպքում դուք պետք է փորձեք հնարավորինս կարճացնել գործարքների ժամկետը:

4. Բանալին արժեքի API-ի վերևում տվյալների սխեմայի նախագծում

Եկեք սկսենք մեր API-ի վերլուծությունը՝ դիտարկելով LMDB-ի կողմից տրամադրված հիմնական աբստրակցիաները՝ միջավայր և տվյալների բազաներ, բանալիներ և արժեքներ, գործարքներ և կուրսորներ:

Ծանոթագրություն կոդերի ցանկերի մասին

Հանրային LMDB API-ի բոլոր գործառույթները վերադարձնում են իրենց աշխատանքի արդյունքը սխալի կոդի տեսքով, սակայն բոլոր հետագա ցուցակներում դրա ստուգումը բաց է թողնվել՝ հակիրճ լինելու համար: Գործնականում մենք նույնիսկ օգտագործում էինք մերը՝ պահեստի հետ փոխազդելու համար: պատառաքաղ C++ փաթաթաներ lmdbxx, որտեղ սխալները նյութականացվում են որպես C++ բացառություններ։

Որպես iOS-ի կամ macOS-ի համար նախատեսված նախագծին LMDB-ին միացնելու ամենաարագ միջոցը, ես առաջարկում եմ իմ 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այս հատկանիշով և դրա մեջ փոփոխականները կտրելու համար:

Տվյալների բազա

Տվյալների բազան առանձին B-tree օրինակ է, որը մենք քննարկեցինք վերևում: Դրա բացումը տեղի է ունենում գործարքի ներսում, որը սկզբում կարող է մի փոքր տարօրինակ թվալ:

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

Իրոք, LMDB-ում կատարված գործարքը պահեստային միավոր է, այլ ոչ թե տվյալների բազայի հատուկ միավոր: Այս հայեցակարգը թույլ է տալիս կատարել ատոմային գործողություններ տարբեր տվյալների բազաներում տեղակայված սուբյեկտների վրա: Տեսականորեն սա բացում է աղյուսակների մոդելավորման հնարավորությունը տարբեր տվյալների շտեմարանների տեսքով, բայց մի ժամանակ ես գնացի այլ ճանապարհով, որը մանրամասն նկարագրված է ստորև:

Բանալիներ և արժեքներ

Կառուցվածք MDB_val մոդելավորում է և՛ հիմնական, և՛ արժեքի հայեցակարգը: Պահեստը պատկերացում չունի դրանց իմաստաբանության մասին։ Նրա համար մեկ այլ բան ընդամենը տվյալ չափի բայթերի զանգված է: Բանալու առավելագույն չափը 512 բայթ է:

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

Օգտագործելով համեմատիչ, խանութը դասավորում է բանալիները աճման կարգով: Եթե ​​այն չփոխարինեք ձերով, ապա կօգտագործվի լռելյայնը, որը դասակարգում է դրանք բայթ առ բայթ բառարանագրական կարգով:

Գործարքի

Գործարքի կառուցվածքը մանրամասն նկարագրված է նախորդ գլուխ, ուստի այստեղ ես համառոտ կկրկնեմ դրանց հիմնական հատկությունները.

1. Աջակցում է բոլոր հիմնական հատկություններին ACIDատոմականություն, հետևողականություն, մեկուսացում և հուսալիություն: Չեմ կարող չնկատել, որ macOS-ի և iOS-ի դիմացկունության առումով սխալ կա, որը շտկվել է MDBX-ում: Ավելին կարող եք կարդալ դրանցում առաջնային.
2. Multithreading-ի մոտեցումը նկարագրված է «մեկ գրող / բազմաթիվ ընթերցողներ» սխեմայով: Գրողները արգելափակում են միմյանց, բայց չեն արգելափակում ընթերցողներին: Ընթերցողները չեն արգելափակում գրողներին կամ միմյանց:
3. Աջակցություն ներդրված գործարքների համար:
4. Multiversion աջակցություն.

Multiversion-ը 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-ով և տեսնել, թե ինչ է տեղի ունենում:

Multiversion-ը շատ լավ առավելություններ է բերում iOS ծրագրավորողների կյանքում: Օգտագործելով այս հատկությունը՝ դուք հեշտությամբ և բնականաբար կարող եք հարմարեցնել տվյալների աղբյուրի թարմացման արագությունը էկրանի ձևերի համար՝ ելնելով օգտագործողի փորձից: Օրինակ՝ վերցնենք Mail.ru Cloud հավելվածի մի առանձնահատկություն, ինչպիսին է բովանդակության ավտոմատ բեռնումը համակարգի մեդիա պատկերասրահից: Լավ կապի դեպքում հաճախորդը կարող է վայրկյանում մի քանի լուսանկար ավելացնել սերվերին: Եթե ​​դուք թարմացնում եք յուրաքանչյուր ներբեռնումից հետո UICollectionView Օգտագործողի ամպի մեջ մեդիա բովանդակության դեպքում դուք կարող եք մոռանալ 60 կադր/վրկ արագությունը և սահուն ոլորումը այս գործընթացի ընթացքում: Էկրանի հաճախակի թարմացումները կանխելու համար դուք պետք է ինչ-որ կերպ սահմանափակեք տվյալների հիմքում ընկած տվյալների փոփոխման արագությունը UICollectionViewDataSource.

Եթե ​​տվյալների բազան չի աջակցում մուլտիվերսիան և թույլ է տալիս աշխատել միայն ընթացիկ վիճակի հետ, ապա տվյալների ժամանակի կայուն պատկեր ստեղծելու համար անհրաժեշտ է պատճենել այն կամ հիշողության մեջ գտնվող տվյալների կառուցվածքում կամ ժամանակավոր աղյուսակում: Այս մոտեցումներից որևէ մեկը շատ թանկ է: Հիշողության մեջ պահեստավորման դեպքում մենք ստանում ենք ծախսեր և՛ հիշողության մեջ, որոնք առաջանում են կառուցված օբյեկտների պահպանման արդյունքում, և՛ ժամանակի ընթացքում՝ կապված ավելորդ ORM փոխակերպումների հետ: Ինչ վերաբերում է ժամանակավոր սեղանին, ապա սա էլ ավելի թանկ հաճույք է, որն իմաստ ունի միայն ոչ տրիվիալ դեպքերում։

LMDB-ի բազմատեսակ լուծումը շատ էլեգանտ կերպով լուծում է տվյալների կայուն աղբյուրի պահպանման խնդիրը: Բավական է պարզապես բացել գործարքը և voila - քանի դեռ չենք ավարտել այն, տվյալների հավաքածուն երաշխավորված է ամրագրված: Թարմացման արագության տրամաբանությունն այժմ ամբողջությամբ գտնվում է ներկայացման շերտի ձեռքում, առանց զգալի ռեսուրսների գերբեռնվածության:

Կուրսորներ

Կուրսորներն ապահովում են B-ծառի անցման միջոցով բանալու-արժեք զույգերի վրա կանոնավոր կրկնման մեխանիզմ: Առանց դրանց անհնար կլիներ արդյունավետ կերպով մոդելավորել տվյալների բազայի աղյուսակները, որոնց մենք այժմ դիմում ենք:

4.2. Սեղանի մոդելավորում

Բանալների պատվիրման հատկությունը թույլ է տալիս կառուցել բարձր մակարդակի աբստրակցիա, ինչպիսին է աղյուսակը հիմնական աբստրակցիաների վերևում: Դիտարկենք այս գործընթացը՝ օգտագործելով ամպային հաճախորդի հիմնական աղյուսակի օրինակը, որը պահում է տեղեկությունները օգտվողի բոլոր ֆայլերի և թղթապանակների մասին:

Սեղանի սխեման

Ընդհանուր սցենարներից մեկը, որի համար պետք է հարմարեցվի թղթապանակի ծառով աղյուսակի կառուցվածքը, տվյալ գրացուցակում տեղակայված բոլոր տարրերի ընտրությունն է: Այս կարգի արդյունավետ հարցումների համար տվյալների կազմակերպման լավ մոդել է. Հարակից ցուցակ. Բանալին արժեքի պահեստի վերևում այն ​​իրականացնելու համար անհրաժեշտ է դասավորել ֆայլերի և թղթապանակների ստեղները այնպես, որ դրանք խմբավորվեն ծնող գրացուցակում իրենց անդամակցության հիման վրա: Բացի այդ, գրացուցակի բովանդակությունը Windows-ի օգտագործողին ծանոթ ձևով ցուցադրելու համար (նախ՝ թղթապանակներ, հետո ֆայլեր՝ երկուսն էլ դասավորված այբբենական կարգով), անհրաժեշտ է բանալիում ներառել համապատասխան լրացուցիչ դաշտեր։

Ստորև նկարը ցույց է տալիս, թե ինչպես կարող է նման լինել ստեղների ներկայացումը բայթային զանգվածի տեսքով, հիմնվելով առաջադրանքի վրա: Բայթերը սկզբում տեղադրվում են մայր գրացուցակի նույնացուցիչով (կարմիր), այնուհետև՝ տիպով (կանաչ), իսկ պոչի մեջ՝ անվանմամբ (կապույտ): Տեսակավորվելով լռելյայն LMDB համեմատիչով ըստ բառարանագրական կարգի՝ դրանք դասավորվում են. պահանջվող ձևով. Նույն կարմիր նախածանցով ստեղների հաջորդական անցումը մեզ տալիս է դրանց հարակից արժեքներն այն հաջորդականությամբ, որոնք պետք է ցուցադրվեն օգտագործողի միջերեսում (աջ կողմում), առանց որևէ լրացուցիչ հետմշակման պահանջելու:

Բանալիների և արժեքների սերիականացում

Աշխարհում հորինվել են օբյեկտների սերիականացման բազմաթիվ մեթոդներ։ Քանի որ մենք արագությունից բացի այլ պահանջ չունեինք, մենք մեզ համար ընտրեցինք հնարավոր ամենաարագը՝ C լեզվի կառուցվածքի օրինակով զբաղեցրած հիշողության աղբը: Այսպիսով, գրացուցակի տարրի բանալին կարող է մոդելավորվել հետևյալ կառուցվածքով. NodeKey.

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

Պահպանել NodeKey պահեստում, որն անհրաժեշտ է օբյեկտում MDB_val տեղադրեք տվյալների ցուցիչը կառուցվածքի սկզբի հասցեին և ֆունկցիայի միջոցով հաշվարկեք դրանց չափը sizeof.

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

Տվյալների բազայի ընտրության չափանիշներին վերաբերող առաջին գլխում ես նշեցի CRUD-ի գործառնությունների շրջանակներում դինամիկ հատկացումները նվազագույնի հասցնելը որպես ընտրության կարևոր գործոն: Ֆունկցիայի կոդը serialize ցույց է տալիս, թե ինչպես LMDB-ի դեպքում դրանք կարելի է ամբողջությամբ խուսափել տվյալների բազայում նոր գրառումներ մտցնելիս: Սերվերից մուտքային բայթային զանգվածը սկզբում վերածվում է ստեկ կառուցվածքների, այնուհետև դրանք աննշան կերպով թափվում են պահեստ: Հաշվի առնելով, որ LMDB-ի ներսում նույնպես չկան դինամիկ հատկացումներ, դուք կարող եք ֆանտաստիկ իրավիճակ ստանալ iOS-ի չափանիշներով. օգտագործեք միայն կուտակային հիշողություն՝ ցանցից մինչև սկավառակ ամբողջ ճանապարհով տվյալների հետ աշխատելու համար:

Բանալների պատվիրում երկուական համեմատիչով

Բանալինների կարգի հարաբերությունը սահմանվում է հատուկ գործառույթով, որը կոչվում է համեմատիչ: Քանի որ շարժիչը ոչինչ չգիտի դրանց պարունակած բայթերի իմաստաբանության մասին, լռելյայն համեմատողին այլ բան չի մնում, քան ստեղները դասավորել բառարանագրական կարգով՝ դիմելով բայթ առ բայթ համեմատությանը: Կառույցները կազմակերպելու համար այն օգտագործելը նման է կտրող կացինով սափրվելու: Այնուամենայնիվ, պարզ դեպքերում ես այս մեթոդը ընդունելի եմ համարում: Այլընտրանքը նկարագրված է ստորև, բայց այստեղ ես կնշեմ այս ճանապարհով ցրված մի քանի փոցխ:

Առաջին բանը, որ պետք է հիշել, պարզունակ տվյալների տեսակների հիշողության ներկայացումն է: Այսպիսով, Apple-ի բոլոր սարքերում ամբողջ թվային փոփոխականները պահվում են ձևաչափով Փոքրիկ Էնդիան. Սա նշանակում է, որ ամենաքիչ կարևոր բայթը կլինի ձախ կողմում, և հնարավոր չի լինի տեսակավորել ամբողջ թվերը՝ օգտագործելով բայթ առ բայթ համեմատություն։ Օրինակ՝ փորձելով դա անել 0-ից մինչև 511 թվերի հավաքածուով, կստացվի հետևյալ արդյունքը.

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

Այս խնդիրը լուծելու համար ամբողջ թվերը պետք է պահվեն բանալիում բայթ-բայթ համեմատողին հարմար ձևաչափով։ Ընտանիքի գործառույթները կօգնեն ձեզ իրականացնել անհրաժեշտ վերափոխումը hton* (մասնավորապես htons օրինակից կրկնակի բայթ թվերի համար):

Ծրագրավորման մեջ տողերի ներկայացման ձևաչափը, ինչպես գիտեք, մի ամբողջություն է պատմությունը. Եթե ​​տողերի իմաստաբանությունը, ինչպես նաև հիշողության մեջ դրանք ներկայացնելու համար օգտագործվող կոդավորումը հուշում են, որ մեկ նիշի համար կարող է լինել մեկ բայթից ավելի, ապա ավելի լավ է անմիջապես հրաժարվել լռելյայն համեմատիչ օգտագործելու գաղափարից:

Երկրորդ բանը, որ պետք է հիշել, այն է հավասարեցման սկզբունքները կառուցվածքի դաշտի կոմպիլյատոր: Դրանց շնորհիվ դաշտերի միջև հիշողության մեջ կարող են ձևավորվել աղբի արժեքներով բայթեր, ինչը, իհարկե, խախտում է բայթ-բայթ տեսակավորումը: Աղբը վերացնելու համար դուք պետք է կամ դաշտերը հայտարարեք խիստ սահմանված կարգով՝ հաշվի առնելով հավասարեցման կանոնները, կամ օգտագործեք հատկանիշը կառուցվածքի հռչակագրում։ 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. Միայն կարդալու գործարքի դեպքում արժեքի կառուցվածքի ցուցիչը երաշխավորված է, որ կգործի միայն մինչև գործարքի փակումը: Ինչպես նշվեց ավելի վաղ, B-tree էջերը, որոնց վրա գտնվում է օբյեկտը, պատճենահանման վրա գրելու սկզբունքի շնորհիվ, մնում են անփոփոխ այնքան ժամանակ, քանի դեռ դրանց հղում է արվում առնվազն մեկ գործարքով: Միևնույն ժամանակ, հենց դրանց հետ կապված վերջին գործարքն ավարտվի, էջերը կարող են նորից օգտագործվել նոր տվյալների համար: Եթե ​​անհրաժեշտ է, որ օբյեկտները գոյատևեն դրանց ստեղծած գործարքից, ապա դրանք դեռ պետք է պատճենվեն:
2. Ընթերցանության գործարքի համար ստացված արժեքի կառուցվածքի ցուցիչը վավեր կլինի միայն մինչև փոփոխման առաջին ընթացակարգը (տվյալների գրելը կամ ջնջումը):
3. Չնայած կառուցվածքը NodeValue ոչ լիարժեք, այլ կտրված (տես «Ստեղների պատվիրում արտաքին համեմատիչի միջոցով» ենթաբաժինը), դուք կարող եք ապահով մուտք գործել դրա դաշտերը ցուցիչի միջոցով: Հիմնական բանը դա չվերադարձնելն է։
4. Ոչ մի դեպքում կառուցվածքը չպետք է փոփոխվի ստացված ցուցիչի միջոցով: Բոլոր փոփոխությունները պետք է կատարվեն միայն մեթոդի միջոցով mdb_put. Այնուամենայնիվ, անկախ նրանից, թե որքան դժվար է դա անել, դա հնարավոր չի լինի, քանի որ հիշողության տարածքը, որտեղ գտնվում է այս կառուցվածքը, քարտեզագրված է միայն կարդալու ռեժիմով:
5. Վերափոխեք ֆայլը գործընթացի հասցեի տարածության մեջ, օրինակ՝ ֆունկցիայի միջոցով պահեստավորման առավելագույն չափը մեծացնելու նպատակով mdb_env_set_map_size ամբողջությամբ անվավեր է դարձնում բոլոր գործարքները և առնչվող սուբյեկտները ընդհանրապես և մատնանշում է որոշակի օբյեկտներ, մասնավորապես:

Վերջապես, մեկ այլ հատկանիշ այնքան նենգ է, որ դրա էության բացահայտումը միայն մեկ այլ պարբերության մեջ չի տեղավորվում։ B-ծառի մասին գլխում ես տվել եմ դիագրամ, թե ինչպես են նրա էջերը դասավորված հիշողության մեջ: Սրանից հետևում է, որ սերիականացված տվյալներով բուֆերի սկզբի հասցեն կարող է լինել բացարձակ կամայական։ Դրա պատճառով նրանց ցուցիչը ստացել է կառուցվածքում MDB_val և վերածվելով կառուցվածքի ցուցիչի, պարզվում է, որ այն ընդհանուր դեպքում անհամապատասխան է: Միևնույն ժամանակ, որոշ չիպերի ճարտարապետությունը (iOS-ի դեպքում դա armv7-ն է) պահանջում է, որ ցանկացած տվյալների հասցեն լինի մեքենայական բառի չափի կամ, այլ կերպ ասած, համակարգի բիթային չափի բազմապատիկ ( armv7-ի համար դա 32 բիթ է): Այսինքն՝ նման վիրահատություն *(int *foo)0x800002 դրանց վրա համարժեք է փախուստի և հանգեցնում է դատավճռով կատարման EXC_ARM_DA_ALIGN. Նման տխուր ճակատագրից խուսափելու երկու ճանապարհ կա.

Առաջինը հանգում է տվյալների նախնական պատճենմանը ակնհայտորեն համահունչ կառուցվածքի մեջ: Օրինակ, սովորական համեմատիչի վրա սա կարտացոլվի հետևյալ կերպ.

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

Այլընտրանքային միջոց է նախապես տեղեկացնել կոմպիլյատորին, որ առանցքային արժեքների կառուցվածքները չեն կարող հավասարեցվել ատրիբուտներին: aligned(1). ARM-ում կարող եք նույն ազդեցությունն ունենալ հասնելուն և օգտագործելով փաթեթավորված հատկանիշը: Հաշվի առնելով, որ այն նաև օգնում է օպտիմալացնել կառույցի զբաղեցրած տարածքը, այս մեթոդն ինձ նախընտրելի է թվում, չնայած. приводит տվյալների հասանելիության գործառնությունների արժեքի ավելացմանը:

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

Շրջանակի հարցումներ

Գրառումների խմբի վրա կրկնելու համար LMDB-ն տրամադրում է կուրսորի աբստրակցիա: Եկեք նայենք, թե ինչպես աշխատել դրա հետ՝ օգտագործելով աղյուսակի օրինակը, որտեղ օգտատերերի ամպային մետատվյալներն արդեն ծանոթ են մեզ:

Որպես գրացուցակում ֆայլերի ցանկի ցուցադրման մաս՝ անհրաժեշտ է գտնել բոլոր ստեղները, որոնց հետ կապված են նրա մանկական ֆայլերը և թղթապանակները: Նախորդ ենթաբաժիններում մենք դասավորեցինք ստեղները NodeKey այնպես, որ դրանք հիմնականում պատվիրված են ծնող գրացուցակի ID-ով: Այսպիսով, տեխնիկապես, թղթապանակի բովանդակությունը գտնելու խնդիրը հանգում է նրան, որ կուրսորը տեղադրվում է տվյալ նախածանցով ստեղների խմբի վերին սահմանի վրա և այնուհետև կրկնվում է դեպի ստորին սահման:

Վերին եզրագիծը կարելի է գտնել անմիջապես հաջորդական որոնման միջոցով: Դա անելու համար կուրսորը տեղադրվում է տվյալների բազայի ստեղների ամբողջ ցանկի սկզբում և հետագայում ավելացվում է այնքան ժամանակ, մինչև դրա տակ հայտնվի մայր գրացուցակի նույնացուցիչով բանալի: Այս մոտեցումն ունի 2 ակնհայտ թերություն.

1. Գծային որոնման բարդությունը, թեև, ինչպես հայտնի է, ծառերի մեջ ընդհանրապես և B-ծառում, մասնավորապես, այն կարող է իրականացվել լոգարիթմական ժամանակում։
2. Իզուր, փնտրվողին նախորդող բոլոր էջերը ֆայլից տեղափոխվում են հիմնական հիշողություն, ինչը չափազանց թանկ է:

Բարեբախտաբար, 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»-ով, իսկ «propname» տեղապահը կարող է փոխարինվել ավելի կոնկրետ «public info» արժեքով:

Բոլոր եզակի մետատվյալները, որոնց պահպանման համար ստեղծվել է նոր աղյուսակը, տեղադրվում են գրառումի արժեքային մասում: Միևնույն ժամանակ, դուք չեք ցանկանում կրկնօրինակել ֆայլերի և թղթապանակների տվյալները, որոնք արդեն պահված են հիմնական աղյուսակում: Փոխարենը ավելորդ տվյալներ են ավելացվում «P» ստեղնին՝ «հանգույցի ID» և «ժամանակի դրոշմ» դաշտերի տեսքով: Դրանց շնորհիվ դուք կարող եք կառուցել ինդեքսային բանալի, որից կարող եք ստանալ առաջնային բանալի, որից, վերջապես, կարող եք ստանալ հանգույցի մետատվյալներ։

Եզրակացություն

LMDB-ի իրականացման արդյունքները մենք դրական ենք գնահատում։ Դրանից հետո հայտերի սառեցումների թիվը նվազել է 30%-ով։

Կատարված աշխատանքի արդյունքներն արձագանքեցին iOS թիմից դուրս: Ներկայում Android հավելվածի հիմնական «Ֆայլեր» բաժիններից մեկը նույնպես անցել է LMDB-ի օգտագործման, իսկ մյուս մասերը ճանապարհին են։ C լեզուն, որում ներդրված է բանալիների արժեքի խանութը, լավ օգնեց սկզբնական շրջանում ստեղծել կիրառական շրջանակ դրա շուրջ՝ C++-ում խաչաձեւ հարթակ: Օգտագործվել է կոդի գեներատոր՝ ստացված C++ գրադարանը Objective-C-ում և Kotlin-ում պլատֆորմի կոդի հետ անխափան միացնելու համար։ Djիննի Dropbox-ից, բայց դա բոլորովին այլ պատմություն է:

Source: www.habr.com