Noong taglagas ng 2019, isang pinakahihintay na kaganapan ang naganap sa Mail.ru Cloud iOS team. Ang pangunahing database para sa patuloy na pag-iimbak ng estado ng application ay naging napaka-exotic para sa mobile na mundo Database ng Lightning Memory-Mapped (LMDB). Sa ibaba ng hiwa nag-aalok kami sa iyo ng isang detalyadong pagsusuri nito sa apat na bahagi. Una, pag-usapan natin ang mga dahilan para sa gayong hindi mahalaga at mahirap na pagpipilian. Pagkatapos ay magpapatuloy tayo upang isaalang-alang ang tatlong haligi sa gitna ng arkitektura ng LMDB: memory-mapped na mga file, B+-tree, copy-on-write na diskarte para sa pagpapatupad ng transactionality at multiversion. Sa wakas, para sa dessert - ang praktikal na bahagi. Dito ay titingnan natin kung paano magdisenyo at magpatupad ng isang database schema na may ilang mga talahanayan, kabilang ang isang index, sa itaas ng mababang antas ng key-value na API.

nilalaman

1. Pagganyak para sa pagpapatupad
2. Pagpoposisyon ng LMDB
3. Tatlong haligi ng LMDB
   3.1. Balyena #1. Mga file na naka-memorya
   3.2. Balyena #2. B+-puno
   3.3. Balyena #3. Copy-on-write
4. Pagdidisenyo ng schema ng data sa itaas ng key-value API
   4.1. Mga pangunahing abstraction
   4.2. Pagmomodelo ng Table
   4.3. Pagmomodelo ng mga ugnayan sa pagitan ng mga talahanayan

1. Pagganyak para sa pagpapatupad

Isang taon noong 2015, naghirap kami para sukatin kung gaano kadalas nahuhuli ang interface ng aming application. Ginawa namin ito para sa isang dahilan. Nakatanggap kami ng mas madalas na mga reklamo na kung minsan ay humihinto ang application sa pagtugon sa mga aksyon ng user: hindi mapindot ang mga button, hindi nag-i-scroll ang mga listahan, atbp. Tungkol sa mekanika ng mga sukat sinabi sa AvitoTech, kaya dito ko lang binibigay ang pagkakasunod-sunod ng mga numero.

Ang mga resulta ng pagsukat ay naging malamig na shower para sa amin. Ito ay naging mas maraming mga problema na dulot ng mga freeze kaysa sa iba pa. Kung bago napagtanto ang katotohanang ito ang pangunahing teknikal na tagapagpahiwatig ng kalidad ay walang pag-crash, pagkatapos ay pagkatapos ng pagtuon inilipat sa freeze free.

Ang pagkakaroon ng binuo dashboard na may mga freeze at pagkatapos gumastos dami и kalidad pagtatasa ng kanilang mga dahilan, ang pangunahing kaaway ay naging malinaw - mabigat na lohika ng negosyo na naisakatuparan sa pangunahing thread ng application. Ang natural na reaksyon sa kahihiyan na ito ay isang nagniningas na pagnanais na itulak ito sa mga daloy ng trabaho. Upang sistematikong malutas ang problemang ito, ginamit namin ang isang multi-threaded na arkitektura batay sa magaan na aktor. Inilaan ko ito sa adaptasyon nito para sa mundo ng iOS dalawang thread sa kolektibong Twitter at artikulo sa Habré. Bilang bahagi ng kasalukuyang salaysay, gusto kong bigyang-diin ang mga aspetong iyon ng desisyon na nakaimpluwensya sa pagpili ng database.​

Ipinapalagay ng modelo ng aktor ng organisasyon ng system na ang multithreading ang nagiging pangalawang esensya nito. Ang mga bagay na modelo sa loob nito ay gustong tumawid sa mga hangganan ng stream. At ginagawa nila ito hindi minsan at dito at doon, ngunit halos palagi at saanman.​

Ang database ay isa sa mga sangkap na batong panulok sa ipinakitang diagram. Ang pangunahing gawain nito ay upang ipatupad ang macropattern Nakabahaging Database. Kung sa mundo ng negosyo ito ay ginagamit upang ayusin ang pag-synchronize ng data sa pagitan ng mga serbisyo, pagkatapos ay sa kaso ng arkitektura ng aktor - data sa pagitan ng mga thread. Kaya, kailangan namin ng database na hindi magdudulot ng kahit kaunting mga paghihirap kapag nagtatrabaho dito sa isang multi-threaded na kapaligiran. Sa partikular, nangangahulugan ito na ang mga bagay na nakuha mula dito ay dapat na hindi bababa sa thread-safe, at perpektong ganap na hindi nababago. Tulad ng alam mo, ang huli ay maaaring gamitin nang sabay-sabay mula sa maraming mga thread nang hindi gumagamit ng anumang pag-lock, na may kapaki-pakinabang na epekto sa pagganap.

Ang pangalawang makabuluhang salik na nakaimpluwensya sa pagpili ng database ay ang aming cloud API. Ito ay inspirasyon ng diskarte sa pag-synchronize na pinagtibay ng git. Tulad niya, tinutukan namin offline-unang API, na mukhang higit pa sa naaangkop para sa mga cloud client. Ipinapalagay na isang beses lang nilang i-pump out ang buong estado ng cloud, at pagkatapos ay magaganap ang pag-synchronize sa karamihan ng mga kaso sa pamamagitan ng paglulunsad ng mga pagbabago. Sa kasamaang palad, ang pagkakataong ito ay nasa theoretical zone lamang, at ang mga kliyente ay hindi natutunan kung paano magtrabaho sa mga patch sa pagsasanay. Mayroong isang bilang ng mga layunin na dahilan para dito, na, upang hindi maantala ang pagpapakilala, mag-iiwan kami ng mga bracket. Ngayon, ang higit na kawili-wili ay ang mga nakapagtuturong konklusyon ng aralin tungkol sa kung ano ang mangyayari kapag sinabi ng isang API na "A" at hindi "B" ang sinabi ng consumer nito.

Kaya, kung iniisip mo ang git, na, kapag nagsasagawa ng isang pull command, sa halip na mag-apply ng mga patch sa isang lokal na snapshot, inihahambing ang buong estado nito sa buong estado ng server, pagkatapos ay magkakaroon ka ng isang medyo tumpak na ideya kung paano nangyayari ang pag-synchronize sa cloud mga kliyente. Madaling hulaan na upang maipatupad ito, kailangan mong maglaan ng dalawang puno ng DOM sa memorya na may meta-impormasyon tungkol sa lahat ng server at mga lokal na file. Ito ay lumalabas na kung ang isang gumagamit ay nag-iimbak ng 500 libong mga file sa cloud, pagkatapos ay upang i-synchronize ito ay kinakailangan upang muling likhain at sirain ang dalawang puno na may 1 milyong mga node. Ngunit ang bawat node ay isang pinagsama-samang naglalaman ng isang graph ng mga subobject. Sa ganitong paraan, inaasahan ang mga resulta ng profiling. Ito ay lumabas na kahit na hindi isinasaalang-alang ang pagsasama-sama ng algorithm, ang mismong pamamaraan ng paglikha at kasunod na pagsira sa isang malaking bilang ng mga maliliit na bagay ay nagkakahalaga ng isang medyo sentimos. Ang sitwasyon ay pinalala ng katotohanan na ang pangunahing operasyon ng pag-synchronize ay kasama sa isang malaking bilang ng mga script ng gumagamit. Bilang resulta, inaayos namin ang pangalawang mahalagang criterion sa pagpili ng database - ang kakayahang ipatupad ang mga operasyon ng CRUD nang walang dynamic na paglalaan ng mga bagay.

Ang iba pang mga kinakailangan ay mas tradisyonal at ang kanilang buong listahan ay ang mga sumusunod.

1. Kaligtasan ng thread.
2. Multiprocessing. Idinidikta ng pagnanais na gamitin ang parehong halimbawa ng database upang i-synchronize ang estado hindi lamang sa pagitan ng mga thread, kundi pati na rin sa pagitan ng pangunahing application at mga extension ng iOS.
3. Ang kakayahang kumatawan sa mga nakaimbak na entity bilang mga hindi nababagong bagay.​
4. Walang mga dynamic na alokasyon sa loob ng mga pagpapatakbo ng CRUD.
5. Suporta sa transaksyon para sa mga pangunahing katangian ACID: atomicity, consistency, isolation at reliability.
6. Bilis sa pinakasikat na mga kaso.

Sa hanay ng mga kinakailangan na ito, ang SQLite ay at nananatiling isang mahusay na pagpipilian. Gayunpaman, bilang bahagi ng pag-aaral ng mga alternatibo, nakatagpo ako ng isang libro "Pagsisimula sa LevelDB". Sa ilalim ng kanyang pamumuno, isang benchmark ang isinulat na naghahambing sa bilis ng trabaho sa iba't ibang mga database sa totoong cloud scenario. Ang resulta ay lumampas sa aming pinakamaligaw na inaasahan. Sa pinakasikat na mga kaso - pagkuha ng cursor sa isang pinagsunod-sunod na listahan ng lahat ng mga file at isang pinagsunod-sunod na listahan ng lahat ng mga file para sa isang naibigay na direktoryo - ang LMDB ay naging 10 beses na mas mabilis kaysa sa SQLite. Ang pagpili ay naging malinaw.

2. LMDB Positioning

Ang LMDB ay isang napakaliit na library (10K row lang) na nagpapatupad ng pinakamababang pangunahing layer ng mga database - storage.

Ipinapakita ng diagram sa itaas na ang paghahambing ng LMDB sa SQLite, na nagpapatupad din ng mas matataas na antas, ay karaniwang hindi mas tama kaysa sa SQLite na may Core Data. Mas magiging patas na banggitin ang parehong mga storage engine bilang pantay na mga kakumpitensya - BerkeleyDB, LevelDB, Sophia, RocksDB, atbp. Mayroong kahit na mga pag-unlad kung saan gumaganap ang LMDB bilang bahagi ng storage engine para sa SQLite. Ang unang naturang eksperimento ay noong 2012 nagastos ng LMDB Howard Chu. Natuklasan naging sobrang nakakaintriga na ang kanyang inisyatiba ay kinuha ng mga mahilig sa OSS, at natagpuan ang pagpapatuloy nito sa tao LumoSQL. Noong Enero 2020, ang may-akda ng proyektong ito ay si Den Shearer iniharap ito sa LinuxConfAu.

Ang LMDB ay pangunahing ginagamit bilang isang makina para sa mga database ng aplikasyon. Utang ng library ang hitsura nito sa mga developer OpenLDAP, na lubos na hindi nasisiyahan sa BerkeleyDB bilang batayan para sa kanilang proyekto. Simula sa isang maliit na library btree, nakagawa si Howard Chu ng isa sa mga pinakasikat na alternatibo sa ating panahon. Inilaan niya ang kanyang napaka-cool na ulat sa kuwentong ito, pati na rin sa panloob na istraktura ng LMDB. "Ang Lightning Memory-mapped Database". Ang isang magandang halimbawa ng pagsakop sa isang pasilidad ng imbakan ay ibinahagi ni Leonid Yuryev (aka yleo) mula sa Positive Technologies sa kanyang ulat sa Highload 2015 "Ang LMDB engine ay isang espesyal na kampeon". Sa loob nito, pinag-uusapan niya ang tungkol sa LMDB sa konteksto ng isang katulad na gawain ng pagpapatupad ng ReOpenLDAP, at ang LevelDB ay napapailalim na sa paghahambing na pagpuna. Bilang resulta ng pagpapatupad, ang Positive Technologies ay nagkaroon pa ng aktibong pagbuo ng tinidor MDBX na may napakasarap na tampok, pag-optimize at mga pag-aayos ng bug.

Ang LMDB ay kadalasang ginagamit bilang isang as-is storage. Halimbawa, Mozilla Firefox browser pinili ito para sa maraming pangangailangan, at, simula sa bersyon 9, Xcode ginusto ang SQLite nito para sa pag-iimbak ng mga index.

Ang makina ay gumawa din ng marka nito sa mundo ng mobile development. Bakas ng paggamit nito ay maaaring mahanap sa iOS client para sa Telegram. Ang LinkedIn ay nagpatuloy pa at pinili ang LMDB bilang default na imbakan para sa kanyang homegrown data caching framework Rocket Data, tungkol sa kung saan sinabi sa kanyang artikulo noong 2016.

Ang LMDB ay matagumpay na nakikipaglaban para sa isang lugar sa araw sa niche na iniwan ng BerkeleyDB matapos itong mapasailalim sa kontrol ng Oracle. Ang aklatan ay minamahal dahil sa bilis at pagiging maaasahan nito, kahit na kumpara sa mga kapantay nito. Tulad ng alam mo, walang libreng tanghalian, at gusto kong bigyang-diin ang trade-off na kailangan mong harapin kapag pumipili sa pagitan ng LMDB at SQLite. Malinaw na ipinapakita ng diagram sa itaas kung paano nakakamit ang pagtaas ng bilis. Una, hindi kami nagbabayad para sa mga karagdagang layer ng abstraction sa ibabaw ng disk storage. Malinaw na hindi pa rin magagawa ng isang mahusay na arkitektura kung wala ang mga ito, at hindi maiiwasang lilitaw ang mga ito sa code ng aplikasyon, ngunit magiging mas banayad ang mga ito. Hindi sila maglalaman ng mga feature na hindi kinakailangan ng isang partikular na application, halimbawa, suporta para sa mga query sa wikang SQL. Pangalawa, nagiging posible na mahusay na ipatupad ang pagmamapa ng mga pagpapatakbo ng application sa mga kahilingan sa imbakan ng disk. Kung SQLite sa aking trabaho ay batay sa average na pang-istatistika na mga pangangailangan ng isang average na application, pagkatapos ikaw, bilang isang developer ng application, ay lubos na nakakaalam ng mga pangunahing sitwasyon ng workload. Para sa isang mas produktibong solusyon, kailangan mong magbayad ng mas mataas na tag ng presyo para sa pagbuo ng paunang solusyon at para sa kasunod na suporta nito.

3. Tatlong haligi ng LMDB

Ang pagkakaroon ng pagtingin sa LMDB mula sa isang mata ng ibon, oras na upang palalimin. Ang susunod na tatlong seksyon ay ilalaan sa pagsusuri ng mga pangunahing haligi kung saan nakasalalay ang arkitektura ng imbakan:

1. Memory-mapped na mga file bilang isang mekanismo para sa pagtatrabaho sa disk at pag-synchronize ng mga panloob na istruktura ng data.
2. B+-tree bilang isang organisasyon ng istruktura ng nakaimbak na data.
3. Copy-on-write bilang isang diskarte upang magbigay ng mga katangian ng transaksyon ng ACID at multiversion.

3.1. Balyena #1. Mga file na naka-memorya

Ang memory-mapped na mga file ay isang mahalagang elemento ng arkitektura na lumilitaw pa nga ang mga ito sa pangalan ng repositoryo. Ang mga isyu sa pag-cache at pag-synchronize ng pag-access sa naka-imbak na impormasyon ay ganap na naiwan sa operating system. Ang LMDB ay hindi naglalaman ng anumang mga cache sa loob nito. Ito ay isang nakakamalay na desisyon ng may-akda, dahil ang pagbabasa ng data nang direkta mula sa mga naka-map na file ay nagbibigay-daan sa iyo upang i-cut ang maraming mga sulok sa pagpapatupad ng engine. Nasa ibaba ang isang malayo sa kumpletong listahan ng ilan sa kanila.

1. Ang pagpapanatili ng pagkakapare-pareho ng data sa imbakan kapag nagtatrabaho dito mula sa ilang mga proseso ay nagiging responsibilidad ng operating system. Sa susunod na seksyon, ang mekanika na ito ay tinalakay nang detalyado at may mga larawan.
2. Ang kawalan ng mga cache ay ganap na nag-aalis ng LMDB mula sa overhead na nauugnay sa mga dynamic na alokasyon. Ang pagbabasa ng data sa pagsasanay ay nangangahulugan ng pagtatakda ng isang pointer sa tamang address sa virtual memory at wala nang iba pa. Ito ay parang science fiction, ngunit sa storage source code lahat ng mga tawag sa calloc ay puro sa storage configuration function.
3. Ang kawalan ng mga cache ay nangangahulugan din ng kawalan ng mga kandado na nauugnay sa pag-synchronize ng kanilang pag-access. Ang mga mambabasa, kung saan maaaring magkaroon ng di-makatwirang bilang ng mga mambabasa sa parehong oras, ay hindi nakatagpo ng isang solong mutex sa kanilang pagpunta sa data. Dahil dito, ang bilis ng pagbabasa ay may perpektong linear scalability batay sa bilang ng mga CPU. Sa LMDB, ang mga pagpapatakbo ng pagbabago lamang ang naka-synchronize. Maaari lamang magkaroon ng isang manunulat sa isang pagkakataon.
4. Ang isang minimum na pag-cache at lohika ng pag-synchronize ay nag-aalis ng sobrang kumplikadong uri ng mga error na nauugnay sa pagtatrabaho sa isang multi-threaded na kapaligiran. Mayroong dalawang kawili-wiling pag-aaral sa database sa kumperensya ng Usenix OSDI 2014: "Lahat ng File System ay Hindi Nagagawang Pantay-pantay: Sa Pagiging Kumplikado ng Paggawa ng Crash-Consistent na Application" и "Pagpapahirap sa mga Database para sa Kasayahan at Kita". Mula sa kanila maaari kang makakuha ng impormasyon tungkol sa parehong hindi pa nagagawang pagiging maaasahan ng LMDB at ang halos walang kamali-mali na pagpapatupad ng mga katangian ng transaksyon ng ACID, na higit na mataas kaysa sa SQLite.
5. Ang minimalism ng LMDB ay nagbibigay-daan sa representasyon ng makina ng code nito na ganap na matatagpuan sa L1 cache ng processor na may mga kasunod na katangian ng bilis.

Sa kasamaang palad, sa iOS, na may memory-mapped na mga file, ang lahat ay hindi walang ulap gaya ng gusto namin. Upang pag-usapan ang tungkol sa mga pagkukulang na nauugnay sa kanila nang mas sinasadya, kinakailangang tandaan ang mga pangkalahatang prinsipyo ng pagpapatupad ng mekanismong ito sa mga operating system.

Pangkalahatang impormasyon tungkol sa mga file na naka-memorya

Sa bawat application na tumatakbo, ang operating system ay nag-uugnay ng isang entity na tinatawag na isang proseso. Ang bawat proseso ay inilalaan ng magkadikit na hanay ng mga address kung saan inilalagay nito ang lahat ng kailangan nito para gumana. Sa pinakamababang mga address ay may mga seksyon na may code at hard-coded na data at mapagkukunan. Susunod ay dumaraming bloke ng dynamic na address space, na kilala sa amin sa ilalim ng pangalang heap. Naglalaman ito ng mga address ng mga entity na lumilitaw sa panahon ng pagpapatakbo ng programa. Sa itaas ay ang memory area na ginagamit ng application stack. Ito ay lumalaki o umuurong; sa madaling salita, ang laki nito ay mayroon ding dinamikong kalikasan. Upang maiwasang magtulak at makasagabal ang stack at heap sa isa't isa, matatagpuan ang mga ito sa magkaibang dulo ng address space. May butas sa pagitan ng dalawang dynamic na seksyon sa itaas at ibaba. Gumagamit ang operating system ng mga address sa gitnang seksyong ito upang iugnay ang iba't ibang entity sa proseso. Sa partikular, maaari nitong iugnay ang isang tiyak na tuloy-tuloy na hanay ng mga address sa isang file sa disk. Ang nasabing file ay tinatawag na memory-mapped.​

Malaki ang address space na nakalaan sa proseso. Sa teorya, ang bilang ng mga address ay limitado lamang sa laki ng pointer, na tinutukoy ng bit capacity ng system. Kung ang pisikal na memorya ay nakamapa dito 1-to-1, kung gayon ang pinakaunang proseso ay lalamunin ang buong RAM, at walang pag-uusapan tungkol sa anumang multitasking.​

Gayunpaman, mula sa aming karanasan, alam namin na ang mga modernong operating system ay maaaring sabay-sabay na magsagawa ng maraming proseso hangga't ninanais. Posible ito dahil sa katotohanan na naglalaan lamang sila ng maraming memorya sa mga proseso sa papel, ngunit sa katotohanan ay naglo-load sila sa pangunahing pisikal na memorya lamang ang bahaging iyon na hinihiling dito at ngayon. Samakatuwid, ang memorya na nauugnay sa isang proseso ay tinatawag na virtual.

Ang operating system ay nag-aayos ng virtual at pisikal na memorya sa mga pahina ng isang tiyak na laki. Sa sandaling ang isang tiyak na pahina ng virtual memory ay in demand, ang operating system ay naglo-load ito sa pisikal na memorya at itugma ang mga ito sa isang espesyal na talahanayan. Kung walang mga libreng puwang, kung gayon ang isa sa mga naunang na-load na mga pahina ay kinopya sa disk, at ang hinihiling ay tumatagal ng lugar nito. Ang pamamaraang ito, na babalikan natin sa ilang sandali, ay tinatawag na swapping. Ang figure sa ibaba ay naglalarawan ng prosesong inilarawan. Dito, ang pahina A na may address 0 ay na-load at inilagay sa pangunahing pahina ng memorya na may address 4. Ang katotohanang ito ay makikita sa talahanayan ng pagsusulatan sa cell number 0.​

Ang kuwento ay eksaktong pareho sa mga file na naka-mapa sa memorya. Logically, sila ay dapat na tuloy-tuloy at ganap na matatagpuan sa virtual address space. Gayunpaman, pumapasok sila sa pahina ng pisikal na memorya sa bawat pahina at kapag hiniling lamang. Ang pagbabago ng naturang mga pahina ay naka-synchronize sa file sa disk. Sa ganitong paraan, maaari kang magsagawa ng file I/O sa pamamagitan lamang ng pagtatrabaho sa mga byte sa memorya - lahat ng mga pagbabago ay awtomatikong ililipat ng kernel ng operating system sa source file.​
​
Ang larawan sa ibaba ay nagpapakita kung paano sini-synchronize ng LMDB ang estado nito kapag nagtatrabaho sa database mula sa iba't ibang proseso. Sa pamamagitan ng pagmamapa ng virtual memory ng iba't ibang proseso sa parehong file, de facto namin obligado ang operating system na palipat-lipat na i-synchronize ang ilang mga bloke ng kanilang mga address space sa isa't isa, kung saan ang LMDB ay tumitingin.​
​

Ang isang mahalagang nuance ay ang LMDB, bilang default, ay binabago ang data file sa pamamagitan ng write system call mechanism, at ipinapakita ang file mismo sa read-only na mode. Ang pamamaraang ito ay may dalawang mahalagang kahihinatnan.

Ang unang kahihinatnan ay karaniwan sa lahat ng mga operating system. Ang kakanyahan nito ay upang magdagdag ng proteksyon laban sa hindi sinasadyang pinsala sa database sa pamamagitan ng maling code. Tulad ng alam mo, ang mga executable na tagubilin ng isang proseso ay libre upang ma-access ang data mula sa kahit saan sa address space nito. Kasabay nito, tulad ng naalala lang namin, ang pagpapakita ng isang file sa read-write mode ay nangangahulugan na ang anumang pagtuturo ay maaari ring baguhin ito. Kung nagawa niya ito nang hindi sinasadya, sinusubukan, halimbawa, na aktwal na i-overwrite ang isang elemento ng array sa isang hindi umiiral na index, pagkatapos ay maaari niyang aksidenteng baguhin ang file na nakamapang sa address na ito, na hahantong sa katiwalian ng database. Kung ang file ay ipinapakita sa read-only na mode, ang pagtatangka na baguhin ang kaukulang address space ay hahantong sa isang emergency na pagwawakas ng programa na may signal. SIGSEGV, at mananatiling buo ang file.

Ang pangalawang kinahinatnan ay partikular na sa iOS. Hindi ito tahasang binanggit ng may-akda o anumang iba pang mapagkukunan, ngunit kung wala ito ay hindi magiging angkop ang LMDB para sa pagtakbo sa mobile operating system na ito. Ang susunod na seksyon ay nakatuon sa pagsasaalang-alang nito.

Mga detalye ng mga file na naka-memorya sa iOS

Nagkaroon ng magandang ulat sa WWDC noong 2018 "IOS Memory Deep Dive". Sinasabi nito sa amin na sa iOS, ang lahat ng page na matatagpuan sa pisikal na memorya ay isa sa 3 uri: marumi, naka-compress at malinis.

Ang malinis na memorya ay isang koleksyon ng mga pahina na maaaring walang sakit na i-unload mula sa pisikal na memorya. Ang data na naglalaman ng mga ito ay maaaring i-reload kung kinakailangan mula sa mga orihinal na mapagkukunan nito. Ang mga read-only na memory-mapped na file ay nabibilang sa kategoryang ito. Ang iOS ay hindi natatakot na i-unload ang mga pahinang naka-map sa isang file mula sa memorya anumang oras, dahil ang mga ito ay garantisadong mai-synchronize sa file sa disk.
​
Ang lahat ng binagong pahina ay napupunta sa maruming memorya, saanman sila orihinal na matatagpuan. Sa partikular, ang mga file na naka-memorya na binago sa pamamagitan ng pagsulat sa virtual memory na nauugnay sa mga ito ay mauuri sa ganitong paraan. Binubuksan ang LMDB na may flag MDB_WRITEMAP, pagkatapos gumawa ng mga pagbabago dito, maaari mo itong i-verify nang personal.​

​Sa sandaling magsimulang kumuha ng masyadong maraming pisikal na memorya ang isang application, isasailalim ito ng iOS sa maruming page compression. Ang kabuuang memorya na inookupahan ng marumi at naka-compress na mga pahina ay bumubuo sa tinatawag na memory footprint ng application. Kapag naabot na nito ang isang tiyak na halaga ng threshold, ang OOM killer system daemon ay darating pagkatapos ng proseso at pilit itong tinatanggal. Ito ang kakaiba ng iOS kumpara sa mga desktop operating system. Sa kabaligtaran, ang pagbabawas ng memory footprint sa pamamagitan ng pagpapalit ng mga pahina mula sa pisikal na memory patungo sa disk ay hindi ibinigay sa iOS. Ang mga dahilan ay maaari lamang hulaan. Marahil ang pamamaraan ng masinsinang paglipat ng mga pahina sa disk at pabalik ay masyadong nakakaubos ng enerhiya para sa mga mobile device, o ang iOS ay nagse-save ng mapagkukunan ng muling pagsusulat ng mga cell sa SSD drive, o marahil ang mga designer ay hindi nasiyahan sa pangkalahatang pagganap ng system, kung saan ang lahat ay patuloy na pinagpalit. Maging ito ay maaaring, ang katotohanan ay nananatiling isang katotohanan.

Ang magandang balita, na nabanggit na kanina, ay ang LMDB bilang default ay hindi gumagamit ng mmap na mekanismo para mag-update ng mga file. Nangangahulugan ito na ang ipinapakitang data ay inuri ng iOS bilang malinis na memorya at hindi nakakatulong sa memory footprint. Maaari mong i-verify ito gamit ang isang Xcode tool na tinatawag na VM Tracker. Ang screenshot sa ibaba ay nagpapakita ng estado ng iOS virtual memory ng Cloud application habang tumatakbo. Sa simula, 2 instance ng LMDB ang nasimulan dito. Ang una ay pinahintulutan na ipakita ang kanyang file sa 1GiB ng virtual memory, ang pangalawa - 512MiB. Sa kabila ng katotohanan na ang parehong mga imbakan ay sumasakop sa isang tiyak na halaga ng memorya ng residente, wala sa kanila ang nag-aambag ng maruming sukat.

At ngayon ay oras na para sa masamang balita. Salamat sa mekanismo ng swap sa 64-bit na desktop operating system, ang bawat proseso ay maaaring sumakop ng mas maraming virtual address space gaya ng pinapayagan ng libreng hard disk space para sa potensyal na swap nito. Ang pagpapalit ng swap ng compression sa iOS ay radikal na binabawasan ang theoretical maximum. Ngayon ang lahat ng mga proseso ng buhay ay dapat magkasya sa pangunahing (read RAM) na memorya, at lahat ng mga hindi magkasya ay dapat piliting wakasan. Ito ay nakasaad tulad ng sa nabanggit sa itaas ulat, at sa opisyal na dokumentasyon. Bilang resulta, mahigpit na nililimitahan ng iOS ang dami ng memory na magagamit para sa paglalaan sa pamamagitan ng mmap. Dito dito Maaari mong tingnan ang mga empirical na limitasyon ng dami ng memory na maaaring ilaan sa iba't ibang device gamit ang system call na ito. Sa pinakamodernong mga modelo ng smartphone, ang iOS ay naging mapagbigay ng 2 gigabytes, at sa mga nangungunang bersyon ng iPad - ng 4. Sa pagsasagawa, siyempre, kailangan mong tumuon sa pinakamababang suportadong mga modelo ng device, kung saan ang lahat ay napakalungkot. Ang mas masahol pa, sa pamamagitan ng pagtingin sa estado ng memorya ng application sa VM Tracker, makikita mo na ang LMDB ay malayo sa nag-iisang nag-aangkin na memory-mapped. Ang mga magagandang tipak ay kinakain ng mga allocator ng system, mga resource file, mga framework ng imahe, at iba pang maliliit na mandaragit.

Batay sa mga resulta ng mga eksperimento sa Cloud, dumating kami sa mga sumusunod na halaga ng kompromiso para sa memorya na inilaan ng LMDB: 384 megabytes para sa 32-bit na mga aparato at 768 para sa 64-bit na mga aparato. Matapos maubos ang volume na ito, magsisimulang magtapos sa code ang anumang pagpapatakbo ng pagbabago MDB_MAP_FULL. Nakikita namin ang mga ganitong pagkakamali sa aming pagsubaybay, ngunit ang mga ito ay sapat na maliit na sa yugtong ito ay maaari silang mapabayaan.

Ang isang hindi malinaw na dahilan para sa labis na pagkonsumo ng memorya ng imbakan ay maaaring pangmatagalang mga transaksyon. Upang maunawaan kung paano konektado ang dalawang phenomena na ito, tutulungan tayo sa pamamagitan ng pagsasaalang-alang sa natitirang dalawang haligi ng LMDB.

3.2. Balyena #2. B+-puno

Upang tularan ang mga talahanayan sa itaas ng isang imbakan ng key-value, ang mga sumusunod na operasyon ay dapat na nasa API nito:

1. Paglalagay ng bagong elemento.
2. Maghanap ng isang elemento na may ibinigay na susi.
3. Pag-alis ng isang elemento.
4. Ulitin sa pagitan ng mga susi sa pagkakasunud-sunod ng mga ito.

Ang pinakasimpleng istraktura ng data na madaling ipatupad ang lahat ng apat na operasyon ay isang binary search tree. Ang bawat node nito ay kumakatawan sa isang key na naghahati sa buong subset ng mga child key sa dalawang subtree. Ang kaliwa ay naglalaman ng mga mas maliit kaysa sa magulang, at ang kanan ay naglalaman ng mga mas malaki. Ang pagkuha ng nakaayos na hanay ng mga susi ay nakakamit sa pamamagitan ng isa sa mga klasikong tree traversal.​

Ang mga binary tree ay may dalawang pangunahing mga bahid na pumipigil sa mga ito na maging epektibo bilang istruktura ng data na nakabatay sa disk. Una, ang antas ng kanilang balanse ay hindi mahuhulaan. May malaking panganib na makakuha ng mga puno kung saan ang taas ng iba't ibang mga sanga ay maaaring mag-iba nang malaki, na makabuluhang nagpapalala sa algorithmic na kumplikado ng paghahanap kumpara sa kung ano ang inaasahan. Pangalawa, ang kasaganaan ng mga cross-link sa pagitan ng mga node ay nag-aalis ng mga binary tree ng lokalidad sa memorya. Ang mga close node (sa mga tuntunin ng mga koneksyon sa pagitan ng mga ito) ay maaaring matatagpuan sa ganap na magkakaibang mga pahina sa virtual memory. Bilang kinahinatnan, kahit na ang isang simpleng pagtawid ng ilang kalapit na mga node sa isang puno ay maaaring mangailangan ng pagbisita sa isang maihahambing na bilang ng mga pahina. Ito ay isang problema kahit na kapag pinag-uusapan natin ang pagiging epektibo ng mga binary tree bilang isang in-memory na istraktura ng data, dahil ang patuloy na pag-ikot ng mga pahina sa cache ng processor ay hindi isang murang kasiyahan. Pagdating sa madalas na pagkuha ng mga pahina na nauugnay sa mga node mula sa disk, ang sitwasyon ay nagiging ganap nakakalungkot.

Ang mga B-tree, bilang isang ebolusyon ng mga binary tree, ay malulutas ang mga problemang natukoy sa nakaraang talata. Una, sila ay nagbabalanse sa sarili. Pangalawa, ang bawat isa sa kanilang mga node ay naghahati sa hanay ng mga susi ng bata hindi sa 2, ngunit sa M ordered subsets, at ang bilang M ay maaaring masyadong malaki, sa pagkakasunud-sunod ng ilang daan, o kahit na libu-libo.

Sa gayon:

1. Ang bawat node ay naglalaman ng malaking bilang ng na-order na mga susi at ang mga puno ay napakaikli.
2. Nakukuha ng puno ang pag-aari ng lokalidad ng lokasyon sa memorya, dahil ang mga susi na malapit sa halaga ay natural na matatagpuan sa tabi ng isa't isa sa pareho o kalapit na mga node.
3. Ang bilang ng mga transit node kapag bumababa sa isang puno habang may operasyon sa paghahanap ay nababawasan.
4. Ang bilang ng mga target na node na nabasa sa mga query sa hanay ay nababawasan, dahil ang bawat isa sa kanila ay naglalaman na ng malaking bilang ng mga naka-order na key.

Gumagamit ang LMDB ng variation ng B-tree na tinatawag na B+ tree upang mag-imbak ng data. Ang diagram sa itaas ay nagpapakita ng tatlong uri ng mga node na umiiral dito:

1. Sa itaas ay ang ugat. Ito ay walang iba kundi ang konsepto ng isang database sa loob ng isang bodega. Sa loob ng isang halimbawa ng LMDB, maaari kang lumikha ng ilang mga database na nagbabahagi ng isang nakamapang virtual address space. Ang bawat isa sa kanila ay nagsisimula sa sarili nitong ugat.
2. Sa pinakamababang antas ay ang mga dahon. Sila at sila lang ang naglalaman ng mga pares ng key-value na nakaimbak sa database. Siyanga pala, ito ang kakaiba ng B+-trees. Kung ang isang regular na B-tree ay nag-iimbak ng mga bahagi ng halaga sa mga node ng lahat ng antas, kung gayon ang pagkakaiba-iba ng B+ ay nasa pinakamababa lamang. Kapag naayos na ang katotohanang ito, tatawagin pa nating B-tree ang subtype ng punong ginamit sa LMDB.
3. Sa pagitan ng ugat at dahon ay may 0 o higit pang teknikal na antas na may navigational (branch) node. Ang kanilang gawain ay hatiin ang pinagsunod-sunod na hanay ng mga susi sa pagitan ng mga dahon.

Sa pisikal, ang mga node ay mga bloke ng memorya ng isang paunang natukoy na haba. Ang kanilang laki ay isang maramihang laki ng mga pahina ng memorya sa operating system, na tinalakay namin sa itaas. Ang istraktura ng node ay ipinapakita sa ibaba. Ang header ay naglalaman ng meta impormasyon, ang pinaka-halata kung saan halimbawa ay ang checksum. Susunod ang impormasyon tungkol sa mga offset kung saan matatagpuan ang mga cell na may data. Ang data ay maaaring maging alinman sa mga key, kung pinag-uusapan natin ang tungkol sa mga navigation node, o ang buong key-value pairs sa kaso ng mga dahon.​ Maaari kang magbasa nang higit pa tungkol sa istruktura ng mga pahina sa trabaho "Pagsusuri ng Mga Tindahan ng Mataas na Pagganap ng Key-Value".

Ang pagkakaroon ng pakikitungo sa panloob na nilalaman ng mga node ng pahina, higit pa naming kakatawanin ang LMDB B-tree sa isang pinasimpleng paraan sa sumusunod na anyo.

Ang mga pahina na may mga node ay matatagpuan nang sunud-sunod sa disk. Ang mas mataas na bilang na mga pahina ay matatagpuan sa dulo ng file. Ang tinatawag na meta page ay naglalaman ng impormasyon tungkol sa mga offset kung saan matatagpuan ang mga ugat ng lahat ng puno. Kapag binubuksan ang isang file, ini-scan ng LMDB ang pahina ng file sa pamamagitan ng pahina mula sa dulo hanggang simula sa paghahanap ng wastong meta page at sa pamamagitan nito ay nahahanap ang mga umiiral nang database.​

Ngayon, sa pagkakaroon ng ideya ng lohikal at pisikal na istruktura ng organisasyon ng data, maaari tayong magpatuloy upang isaalang-alang ang ikatlong haligi ng LMDB. Ito ay sa tulong nito na ang lahat ng mga pagbabago sa imbakan ay nangyayari sa transaksyon at sa paghihiwalay mula sa isa't isa, na nagbibigay sa database sa kabuuan ng pag-aari ng multiversion.

3.3. Balyena #3. Copy-on-write

Ang ilang mga operasyon ng B-tree ay nagsasangkot ng paggawa ng isang serye ng mga pagbabago sa mga node nito. Ang isang halimbawa ay ang pagdaragdag ng bagong key sa isang node na naabot na ang pinakamataas na kapasidad nito. Sa kasong ito, kinakailangan, una, na hatiin ang node sa dalawa, at pangalawa, upang magdagdag ng link sa bagong namumuong child node sa magulang nito. Ang pamamaraang ito ay potensyal na lubhang mapanganib. Kung sa ilang kadahilanan (pag-crash, pagkawala ng kuryente, atbp.) bahagi lamang ng mga pagbabago mula sa serye ang nangyari, kung gayon ang puno ay mananatili sa isang hindi pare-parehong estado.

Isang tradisyunal na solusyon para sa paggawa ng database fault-tolerant ay ang magdagdag ng karagdagang on-disk data structure sa tabi ng B-tree - isang log ng transaksyon, na kilala rin bilang write-ahead log (WAL). Ito ay isang file sa dulo kung saan ang inilaan na operasyon ay nakasulat nang mahigpit bago baguhin ang B-tree mismo. Kaya, kung ang data corruption ay nakita sa panahon ng self-diagnosis, ang database ay kumunsulta sa log upang ayusin ang sarili nito.

Ang LMDB ay pumili ng ibang paraan bilang isang mekanismo ng pagpapahintulot sa kasalanan, na tinatawag na copy-on-write. Ang kakanyahan nito ay sa halip na i-update ang data sa isang umiiral na pahina, kinokopya muna ito nang buo at ginagawa ang lahat ng mga pagbabago sa kopya.​

Susunod, para maging available ang na-update na data, kailangang baguhin ang link sa node na naging kasalukuyang sa parent node nito. Dahil kailangan din itong baguhin para dito, ito ay kinopya rin muna. Ang proseso ay nagpapatuloy nang paulit-ulit hanggang sa ugat. Ang huling bagay na babaguhin ay ang data sa meta page.​​

Kung biglang nag-crash ang proseso sa panahon ng proseso ng pag-update, kung gayon ang alinman sa isang bagong meta page ay hindi malilikha, o hindi ito ganap na isusulat sa disk, at ang checksum nito ay magiging mali. Sa alinman sa dalawang kasong ito, hindi maaabot ang mga bagong page, ngunit hindi maaapektuhan ang mga luma. Inaalis nito ang pangangailangan para sa LMDB na magsulat ng maagang log upang mapanatili ang pagkakapare-pareho ng data. Sa katunayan, ang istraktura ng imbakan ng data sa disk na inilarawan sa itaas ay sabay-sabay na tumatagal sa pag-andar nito. Ang kawalan ng isang tahasang log ng transaksyon ay isa sa mga tampok ng LMDB na nagbibigay ng mataas na bilis ng pagbabasa ng data.​

Ang resultang disenyo, na tinatawag na append-only B-tree, ay natural na nagbibigay ng paghihiwalay ng transaksyon at multi-bersyon. Sa LMDB, ang bawat bukas na transaksyon ay nauugnay sa kasalukuyang nauugnay na ugat ng puno. Hanggang sa makumpleto ang transaksyon, ang mga pahina ng punong nauugnay dito ay hindi kailanman mababago o muling gagamitin para sa mga bagong bersyon ng data. Kaya, maaari kang magtrabaho hangga't gusto mo gamit ang eksaktong hanay ng data na may kaugnayan sa panahong iyon ang transaksyon ay binuksan, kahit na ang storage ay patuloy na aktibong ina-update sa oras na ito. Ito ang kakanyahan ng multiversion, na ginagawang perpektong data source ang LMDB para sa ating minamahal UICollectionView. Sa pagbubukas ng isang transaksyon, hindi na kailangang dagdagan ang memory footprint ng application sa pamamagitan ng pagmamadali sa pagbomba ng kasalukuyang data sa ilang in-memory na istraktura, dahil sa takot na mawalan ng anumang bagay. Ang tampok na ito ay nakikilala ang LMDB mula sa parehong SQLite, na hindi maaaring ipagmalaki ang naturang kabuuang paghihiwalay. Ang pagkakaroon ng pagbubukas ng dalawang transaksyon sa huli at pagtanggal ng isang partikular na tala sa loob ng isa sa mga ito, hindi na posibleng makuha ang parehong tala sa loob ng pangalawang natitirang tala.

Ang flip side ng coin ay ang potensyal na mas mataas na pagkonsumo ng virtual memory. Ipinapakita ng slide kung ano ang magiging hitsura ng istraktura ng database kung binago ito nang sabay-sabay sa 3 bukas na read transaction na tumitingin sa iba't ibang bersyon ng database. Dahil hindi magagamit muli ng LMDB ang mga node na maaabot mula sa mga ugat na nauugnay sa kasalukuyang mga transaksyon, walang pagpipilian ang tindahan kundi maglaan ng isa pang pang-apat na ugat sa memorya at muling i-clone ang mga binagong pahina sa ilalim nito.​

Dito magiging kapaki-pakinabang na alalahanin ang seksyon sa memory-mapped na mga file. Tila ang karagdagang pagkonsumo ng virtual memory ay hindi dapat mag-alala sa amin, dahil hindi ito nakakatulong sa memory footprint ng application. Gayunpaman, sa parehong oras, nabanggit na ang iOS ay napakakuripot sa paglalaan nito, at hindi kami maaaring, tulad ng sa isang server o desktop, magbigay ng isang LMDB na rehiyon na 1 terabyte at hindi mag-isip tungkol sa tampok na ito. Kung maaari, dapat mong subukang gawing maikli ang buhay ng mga transaksyon hangga't maaari.

4. Pagdidisenyo ng schema ng data sa itaas ng key-value API

Simulan natin ang aming pagsusuri sa API sa pamamagitan ng pagtingin sa mga pangunahing abstraction na ibinigay ng LMDB: kapaligiran at mga database, mga susi at halaga, mga transaksyon at mga cursor.

Isang tala tungkol sa mga listahan ng code

Ang lahat ng mga function sa pampublikong LMDB API ay nagbabalik ng resulta ng kanilang trabaho sa anyo ng isang error code, ngunit sa lahat ng kasunod na listahan ay tinanggal ang pagpapatunay nito para sa kapakanan ng kaiklian. tinidor C++ wrapper lmdbxx, kung saan ang mga error ay ginawa bilang mga pagbubukod sa C++.

Bilang pinakamabilis na paraan para ikonekta ang LMDB sa isang proyekto para sa iOS o macOS, iminumungkahi ko ang aking CocoaPod POSLMDB.

4.1. Mga pangunahing abstraction

Kapaligiran

Kaayusan MDB_env ay ang imbakan ng panloob na estado ng LMDB. Pamilya ng prefix na function mdb_env nagbibigay-daan sa iyo na i-configure ang ilan sa mga katangian nito. Sa pinakasimpleng kaso, ganito ang hitsura ng pagsisimula ng engine.

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

Sa application na Mail.ru Cloud, binago namin ang mga default na halaga ng dalawang parameter lamang.

Ang una ay ang laki ng virtual address space kung saan ang storage file ay nakamapa. Sa kasamaang palad, kahit na sa parehong device, ang partikular na halaga ay maaaring mag-iba nang malaki mula sa run hanggang run. Upang isaalang-alang ang feature na ito ng iOS, dynamic na pinipili ang maximum na dami ng storage. Simula mula sa isang tiyak na halaga, ito ay sunud-sunod na hinahati hanggang sa pag-andar mdb_env_open hindi magbabalik ng resultang naiiba sa ENOMEM. Sa teorya, mayroon ding kabaligtaran na paraan - unang maglaan ng isang minimum na memorya sa makina, at pagkatapos, kapag natanggap ang mga error, MDB_MAP_FULL, dagdagan mo. Gayunpaman, ito ay mas matinik. Ang dahilan ay ang pamamaraan para sa muling paglalaan ng memorya (remap) gamit ang function mdb_env_set_map_size nagpapawalang-bisa sa lahat ng entity (mga cursor, transaksyon, susi at halaga) na dating natanggap mula sa makina. Ang pagsasaalang-alang sa pagliko ng mga kaganapan sa code ay hahantong sa makabuluhang komplikasyon nito. Kung, gayunpaman, ang virtual memory ay napakahalaga sa iyo, kung gayon ito ay maaaring isang dahilan upang tingnang mabuti ang tinidor na nauna nang malayo. MDBX, kung saan kabilang sa mga inihayag na feature ay mayroong "awtomatikong on-the-fly database size adjustment".

Ang pangalawang parameter, ang default na halaga na hindi nababagay sa amin, ay kinokontrol ang mga mekanika ng pagtiyak sa kaligtasan ng thread. Sa kasamaang palad, hindi bababa sa iOS 10 ay may mga problema sa suporta para sa lokal na storage ng thread. Para sa kadahilanang ito, sa halimbawa sa itaas, ang imbakan ay binuksan gamit ang bandila MDB_NOTLS. Bilang karagdagan dito, kinakailangan din tinidor C++ wrapper lmdbxxupang gupitin ang mga variable na may ganitong katangian at sa loob nito.

Mga database

Ang database ay isang hiwalay na halimbawa ng B-tree, na tinalakay namin sa itaas. Ang pagbubukas nito ay nangyayari sa loob ng isang transaksyon, na maaaring medyo kakaiba sa simula.

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

Sa katunayan, ang isang transaksyon sa LMDB ay isang storage entity, hindi isang partikular na database entity. Binibigyang-daan ka ng konseptong ito na magsagawa ng mga atomic operation sa mga entity na matatagpuan sa iba't ibang database. Sa teorya, binubuksan nito ang posibilidad ng pagmomodelo ng mga talahanayan sa anyo ng iba't ibang mga database, ngunit sa isang pagkakataon ay kumuha ako ng ibang landas, na inilarawan nang detalyado sa ibaba.

Mga susi at halaga

Kaayusan MDB_val modelo ang konsepto ng parehong susi at halaga. Walang ideya ang repository tungkol sa kanilang semantika. Para sa kanya, ang iba ay isang hanay lamang ng mga byte ng isang ibinigay na laki. Ang maximum na laki ng key ay 512 bytes.

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

Gamit ang isang comparator, inaayos ng tindahan ang mga susi sa pataas na pagkakasunud-sunod. Kung hindi mo ito papalitan ng sarili mo, gagamitin ang default, na nag-uuri sa kanila ng byte-by-byte sa lexicographic order.​

Mga Transaksyon

Ang istraktura ng transaksyon ay inilarawan nang detalyado sa nakaraang kabanata, kaya dito ko uulitin sandali ang kanilang mga pangunahing katangian:

1. Sinusuportahan ang lahat ng mga pangunahing katangian ACID: atomicity, consistency, isolation at reliability. Hindi ko maiwasang tandaan na mayroong isang bug sa mga tuntunin ng tibay sa macOS at iOS na naayos sa MDBX. Maaari mong basahin ang higit pa sa kanilang README.
2. Ang diskarte sa multithreading ay inilalarawan ng "iisang manunulat / maramihang mambabasa" na pamamaraan. Ang mga manunulat ay nagba-block sa isa't isa, ngunit huwag humarang sa mga mambabasa. Hindi hinaharangan ng mga mambabasa ang mga manunulat o ang isa't isa.
3. Suporta para sa mga nested na transaksyon.
4. Multiversion support.

Napakaganda ng multiversion sa LMDB na gusto kong ipakita ito sa aksyon. Mula sa code sa ibaba makikita mo na ang bawat transaksyon ay gumagana nang eksakto sa bersyon ng database na kasalukuyang sa oras na ito ay binuksan, na ganap na nakahiwalay sa lahat ng kasunod na pagbabago. Ang pagsisimula ng storage at pagdaragdag ng test record dito ay hindi kumakatawan sa anumang bagay na kawili-wili, kaya ang mga ritwal na ito ay naiwan sa ilalim ng spoiler.

Pagdaragdag ng entry sa pagsubok

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

Inirerekomenda ko na subukan mo ang parehong trick sa SQLite at tingnan kung ano ang mangyayari.

Ang multiversion ay nagdadala ng napakagandang perks sa buhay ng isang iOS developer. Gamit ang property na ito, madali at natural mong maisasaayos ang rate ng pag-update ng data source para sa mga form ng screen, batay sa mga pagsasaalang-alang sa karanasan ng user. Halimbawa, kumuha tayo ng feature ng Mail.ru Cloud application gaya ng autoloading content mula sa system media gallery. Sa isang mahusay na koneksyon, ang kliyente ay maaaring magdagdag ng ilang mga larawan sa bawat segundo sa server. Kung mag-a-update ka pagkatapos ng bawat pag-download UICollectionView na may nilalamang media sa cloud ng user, maaari mong kalimutan ang tungkol sa 60 fps at maayos na pag-scroll sa panahon ng prosesong ito. Upang maiwasan ang madalas na pag-update ng screen, kailangan mong limitahan ang rate kung saan nagbabago ang data sa pinagbabatayan UICollectionViewDataSource.

Kung ang database ay hindi sumusuporta sa multiversion at nagbibigay-daan sa iyo upang gumana lamang sa kasalukuyang kasalukuyang estado, pagkatapos ay upang lumikha ng isang time-stable na snapshot ng data kailangan mong kopyahin ito alinman sa ilang in-memory na istraktura ng data o sa isang pansamantalang talahanayan. Ang alinman sa mga pamamaraang ito ay napakamahal. Sa kaso ng in-memory storage, nakakakuha tayo ng mga gastos sa memorya, sanhi ng pag-iimbak ng mga constructed na bagay, at sa oras, na nauugnay sa mga kalabisan na pagbabagong ORM. Tulad ng para sa pansamantalang talahanayan, ito ay isang mas mahal na kasiyahan, na may katuturan lamang sa mga di-maliit na kaso.

Niresolba ng multiversion solution ng LMDB ang problema sa pagpapanatili ng matatag na data source sa napaka-eleganteng paraan. Ito ay sapat na upang magbukas lamang ng isang transaksyon at voila - hanggang sa makumpleto namin ito, ang set ng data ay garantisadong maayos. Ang lohika para sa bilis ng pag-update nito ay nasa kamay na ng presentation layer, na walang overhead ng mga makabuluhang mapagkukunan.

Mga cursor

Nagbibigay ang mga cursor ng mekanismo para sa maayos na pag-ulit sa mga pares ng key-value sa pamamagitan ng B-tree traversal. Kung wala ang mga ito, imposibleng epektibong imodelo ang mga talahanayan sa database, na ngayon ay bumaling tayo.

4.2. Pagmomodelo ng Table

Ang pag-aari ng key na pag-order ay nagbibigay-daan sa iyo na bumuo ng isang mataas na antas ng abstraction tulad ng isang talahanayan sa itaas ng mga pangunahing abstraction. Isaalang-alang natin ang prosesong ito gamit ang halimbawa ng pangunahing talahanayan ng isang cloud client, na nag-cache ng impormasyon tungkol sa lahat ng mga file at folder ng user.

Schema ng talahanayan

Ang isa sa mga karaniwang sitwasyon kung saan dapat iayon ang istraktura ng talahanayan na may puno ng folder ay ang pagpili ng lahat ng elemento na matatagpuan sa loob ng isang partikular na direktoryo. Ang isang magandang modelo ng organisasyon ng data para sa mahusay na mga query ng ganitong uri ay Listahan ng Adjacency. Upang ipatupad ito sa itaas ng imbakan ng key-value, kinakailangang pagbukud-bukurin ang mga susi ng mga file at folder sa paraang nakagrupo ang mga ito batay sa kanilang membership sa parent directory. Bilang karagdagan, upang maipakita ang mga nilalaman ng direktoryo sa form na pamilyar sa isang gumagamit ng Windows (unang mga folder, pagkatapos ay mga file, parehong pinagsunod-sunod ayon sa alpabeto), kinakailangang isama ang kaukulang karagdagang mga patlang sa susi.

Ang larawan sa ibaba ay nagpapakita kung paano, batay sa gawaing nasa kamay, ang isang representasyon ng mga susi sa anyo ng isang byte array ay maaaring magmukhang. Ang mga byte na may pagkakakilanlan ng direktoryo ng magulang (pula) ay unang inilalagay, pagkatapos ay may uri (berde) at sa buntot na may pangalan (asul). Iniuuri ayon sa default na LMDB comparator sa lexicographical na pagkakasunud-sunod, ang mga ito ay inayos sa kinakailangang paraan. Ang sunud-sunod na pagtawid sa mga key na may parehong pulang prefix ay nagbibigay sa amin ng kanilang nauugnay na mga halaga sa pagkakasunud-sunod na dapat nilang ipakita sa user interface (sa kanan), nang hindi nangangailangan ng anumang karagdagang post-processing.

Pagse-serye ng Mga Susi at Halaga

Maraming mga pamamaraan para sa pagse-serialize ng mga bagay ang naimbento sa mundo. Dahil wala kaming ibang kinakailangan maliban sa bilis, pinili namin ang pinakamabilis na posible para sa aming sarili - isang dump ng memorya na inookupahan ng isang halimbawa ng istraktura ng wikang C. Kaya, ang susi ng isang elemento ng direktoryo ay maaaring mamodelo sa sumusunod na istraktura NodeKey.

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

Isalba NodeKey sa imbakan na kailangan sa bagay MDB_val iposisyon ang data pointer sa address ng simula ng istraktura, at kalkulahin ang kanilang laki gamit ang function sizeof.

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

Sa unang kabanata sa pamantayan sa pagpili ng database, binanggit ko ang pagliit ng mga dynamic na alokasyon sa loob ng mga operasyon ng CRUD bilang isang mahalagang kadahilanan sa pagpili. Code ng pag-andar serialize ay nagpapakita kung paano sa kaso ng LMDB sila ay ganap na maiiwasan kapag nagpasok ng mga bagong tala sa database. Ang papasok na byte array mula sa server ay unang binago sa mga istruktura ng stack, at pagkatapos ay itinapon ang mga ito sa imbakan. Isinasaalang-alang na wala ring mga dynamic na alokasyon sa loob ng LMDB, maaari kang makakuha ng kamangha-manghang sitwasyon ayon sa mga pamantayan ng iOS - gumamit lamang ng stack memory upang gumana sa data sa buong landas mula sa network hanggang sa disk!

Pag-order ng mga susi gamit ang binary comparator

Tinukoy ang key order relationship ng isang espesyal na function na tinatawag na comparator. Dahil walang alam ang makina tungkol sa mga semantika ng mga byte na nilalaman nito, ang default na comparator ay walang pagpipilian kundi ayusin ang mga susi sa pagkakasunud-sunod ng lexicographic, na gumagamit ng isang byte-by-byte na paghahambing. Ang paggamit nito sa pag-aayos ng mga istruktura ay katulad ng pag-ahit gamit ang isang palakol. Gayunpaman, sa mga simpleng kaso nakita kong katanggap-tanggap ang pamamaraang ito. Ang kahalili ay inilarawan sa ibaba, ngunit dito ko mapapansin ang ilang mga rake na nakakalat sa landas na ito.

Ang unang bagay na dapat tandaan ay ang representasyon ng memorya ng mga primitive na uri ng data. Kaya, sa lahat ng mga aparatong Apple, ang mga variable ng integer ay naka-imbak sa format Little Endian. Nangangahulugan ito na ang hindi bababa sa makabuluhang byte ay nasa kaliwa, at hindi posible na pagbukud-bukurin ang mga integer gamit ang isang byte-by-byte na paghahambing. Halimbawa, ang pagsisikap na gawin ito sa isang hanay ng mga numero mula 0 hanggang 511 ay magbubunga ng sumusunod na resulta.

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

Upang malutas ang problemang ito, ang mga integer ay dapat na naka-imbak sa key sa isang format na angkop para sa byte-byte comparator. Ang mga pag-andar mula sa pamilya ay tutulong sa iyo na isagawa ang kinakailangang pagbabago hton* (sa partikular htons para sa mga double-byte na numero mula sa halimbawa).

Ang format para sa kumakatawan sa mga string sa programming ay, tulad ng alam mo, isang buo kuwento. Kung ang mga semantika ng mga string, pati na rin ang pag-encode na ginamit upang kumatawan sa mga ito sa memorya, ay nagmumungkahi na maaaring mayroong higit sa isang byte bawat karakter, kung gayon mas mahusay na agad na iwanan ang ideya ng paggamit ng isang default na comparator.

Ang pangalawang bagay na dapat tandaan ay mga prinsipyo ng pagkakahanay compiler ng patlang ng istraktura. Dahil sa kanila, ang mga byte na may mga halaga ng basura ay maaaring mabuo sa memorya sa pagitan ng mga patlang, na, siyempre, sinisira ang byte-byte na pag-uuri. Upang alisin ang basura, kailangan mong magdeklara ng mga field sa isang mahigpit na tinukoy na pagkakasunud-sunod, na isinasaisip ang mga panuntunan sa pag-align, o gamitin ang attribute sa deklarasyon ng istraktura packed.

Pag-order ng mga susi gamit ang isang panlabas na comparator

Ang pangunahing lohika ng paghahambing ay maaaring masyadong kumplikado para sa isang binary comparator. Isa sa maraming dahilan ay ang pagkakaroon ng mga teknikal na larangan sa loob ng mga istruktura. Ilalarawan ko ang kanilang paglitaw gamit ang halimbawa ng isang susi para sa isang elemento ng direktoryo na pamilyar na sa amin.

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

Sa kabila ng pagiging simple nito, sa karamihan ng mga kaso kumokonsumo ito ng masyadong maraming memorya. Ang buffer para sa pangalan ay tumatagal ng hanggang 256 byte, bagaman sa average na mga pangalan ng file at folder ay bihirang lumampas sa 20-30 character.

​Ang isa sa mga karaniwang pamamaraan para sa pag-optimize ng laki ng isang tala ay ang "pagputol" nito sa aktwal na laki. Ang kakanyahan nito ay ang mga nilalaman ng lahat ng variable-length na mga field ay naka-imbak sa isang buffer sa dulo ng istraktura, at ang kanilang mga haba ay naka-imbak sa magkahiwalay na mga variable.​ Ayon sa diskarteng ito, ang susi NodeKey ay binago bilang mga sumusunod.

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

Dagdag pa, kapag nagse-serialize, hindi tinukoy ang laki ng data sizeof ang buong istraktura, at ang laki ng lahat ng mga patlang ay isang nakapirming haba kasama ang laki ng aktwal na ginamit na bahagi ng buffer.

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

Bilang resulta ng refactoring, nakatanggap kami ng makabuluhang pagtitipid sa espasyong inookupahan ng mga susi. Gayunpaman, dahil sa teknikal na larangan nameLength, ang default na binary comparator ay hindi na angkop para sa pangunahing paghahambing. Kung hindi namin ito papalitan ng sarili namin, ang haba ng pangalan ay magiging mas mataas na priority factor sa pag-uuri kaysa sa pangalan mismo.

Binibigyang-daan ng LMDB ang bawat database na magkaroon ng sarili nitong pangunahing function ng paghahambing. Ginagawa ito gamit ang function mdb_set_compare mahigpit bago buksan. Para sa mga malinaw na dahilan, hindi ito mababago sa buong buhay ng database. Ang comparator ay tumatanggap ng dalawang key sa binary format bilang input, at sa output ay ibinabalik nito ang resulta ng paghahambing: mas mababa sa (-1), mas malaki sa (1) o katumbas ng (0). Pseudocode para sa NodeKey parang ganun.

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 // ...
}​

Hangga't ang lahat ng mga susi sa database ay may parehong uri, ang walang pasubali na pag-cast ng kanilang byte na representasyon sa uri ng istraktura ng application key ay legal. Mayroong isang nuance dito, ngunit ito ay tatalakayin sa ibaba sa subsection na "Reading Records".

Pagse-serye ng mga Halaga

Ang LMDB ay gumagana nang labis sa mga susi ng mga nakaimbak na tala. Ang kanilang paghahambing sa bawat isa ay nangyayari sa loob ng balangkas ng anumang inilapat na operasyon, at ang pagganap ng buong solusyon ay nakasalalay sa bilis ng comparator. Sa isang perpektong mundo, ang default na binary comparator ay dapat sapat upang ihambing ang mga susi, ngunit kung kailangan mong gumamit ng iyong sarili, kung gayon ang pamamaraan para sa pag-deserialize ng mga susi dito ay dapat na mas mabilis hangga't maaari.

Ang database ay hindi partikular na interesado sa bahagi ng halaga ng talaan (halaga). Ang conversion nito mula sa isang byte na representasyon sa isang bagay ay nangyayari lamang kapag ito ay kinakailangan na ng application code, halimbawa, upang ipakita ito sa screen. Dahil medyo bihira itong mangyari, ang mga kinakailangan sa bilis para sa pamamaraang ito ay hindi gaanong kritikal, at sa pagpapatupad nito ay mas malaya kaming tumuon sa kaginhawahan. Halimbawa, para i-serialize ang metadata tungkol sa mga file na hindi pa nai-download, ginagamit namin NSKeyedArchiver.

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

Gayunpaman, may mga pagkakataon na mahalaga pa rin ang pagganap. Halimbawa, kapag nagse-save ng metainformation tungkol sa istraktura ng file ng isang user cloud, ginagamit namin ang parehong memory dump ng mga bagay. Ang highlight ng gawain ng pagbuo ng isang serialized na representasyon ng mga ito ay ang katotohanan na ang mga elemento ng isang direktoryo ay na-modelo ng isang hierarchy ng mga klase.​

Upang ipatupad ito sa wikang C, ang mga tiyak na larangan ng mga tagapagmana ay inilalagay sa magkahiwalay na mga istruktura, at ang kanilang koneksyon sa base ng isa ay tinukoy sa pamamagitan ng isang larangan ng uri ng unyon. Ang aktwal na mga nilalaman ng unyon ay tinukoy sa pamamagitan ng uri ng teknikal na katangian.

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

Pagdaragdag at pag-update ng mga tala

Maaaring idagdag ang serialized na key at value sa store. Upang gawin ito, gamitin ang function mdb_put.

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

Sa yugto ng pagsasaayos, ang imbakan ay maaaring pahintulutan o ipagbawal na mag-imbak ng maramihang mga tala na may parehong susi. Kung ang pagdoble ng mga susi ay ipinagbabawal, kung gayon kapag nagpasok ng isang talaan, maaari mong matukoy kung ang pag-update ng isang umiiral nang talaan ay pinapayagan o hindi. Kung ang fraying ay maaari lamang mangyari bilang isang resulta ng isang error sa code, maaari mong protektahan ang iyong sarili mula dito sa pamamagitan ng pagtukoy sa bandila NOOVERWRITE.

Pagbabasa ng mga entry

Upang basahin ang mga tala sa LMDB, gamitin ang function mdb_get. Kung ang pares ng key-value ay kinakatawan ng mga dati nang itinapon na mga istraktura, magiging ganito ang pamamaraang ito.

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

Ang ipinakita na listahan ay nagpapakita kung paano nagbibigay-daan sa iyo ang serialization sa pamamagitan ng structure dump na alisin ang mga dynamic na alokasyon hindi lamang kapag nagsusulat, ngunit kapag nagbabasa ng data. Nagmula sa function mdb_get eksaktong tinitingnan ng pointer ang virtual memory address kung saan iniimbak ng database ang byte na representasyon ng object. Sa katunayan, nakakakuha kami ng isang uri ng ORM na nagbibigay ng napakataas na bilis ng pagbasa ng data na halos walang bayad. Sa kabila ng lahat ng kagandahan ng diskarte, kinakailangang tandaan ang ilang mga tampok na nauugnay dito.

1. Para sa isang readonly na transaksyon, ang pointer sa istraktura ng halaga ay ginagarantiyahan na mananatiling wasto lamang hanggang sa sarado ang transaksyon. Tulad ng nabanggit kanina, ang mga B-tree na pahina kung saan matatagpuan ang isang bagay, salamat sa copy-on-write na prinsipyo, ay nananatiling hindi nagbabago hangga't ang mga ito ay isinangguni ng hindi bababa sa isang transaksyon. Kasabay nito, sa sandaling makumpleto ang huling transaksyong nauugnay sa kanila, maaaring magamit muli ang mga page para sa bagong data. Kung kinakailangan para sa mga bagay na mabuhay sa transaksyon na nabuo sa kanila, kailangan pa rin silang kopyahin.
2. Para sa isang readwrite na transaksyon, ang pointer sa resultang istraktura ng halaga ay magiging wasto lamang hanggang sa unang pamamaraan ng pagbabago (pagsusulat o pagtanggal ng data).
3. Bagaman ang istraktura NodeValue hindi ganap, ngunit na-trim (tingnan ang subsection na "Pag-order ng mga key gamit ang isang panlabas na comparator"), maaari mong ligtas na ma-access ang mga field nito sa pamamagitan ng pointer. Ang pangunahing bagay ay hindi i-dereference ito!
4. Sa anumang pagkakataon dapat baguhin ang istraktura sa pamamagitan ng natanggap na pointer. Ang lahat ng mga pagbabago ay dapat gawin lamang sa pamamagitan ng pamamaraan mdb_put. Gayunpaman, gaano man kahirap ang gusto mong gawin ito, hindi ito magiging posible, dahil ang lugar ng memorya kung saan matatagpuan ang istrakturang ito ay naka-map sa readonly mode.
5. I-remap ang isang file sa puwang ng address ng proseso para sa layunin ng, halimbawa, pagtaas ng maximum na laki ng storage gamit ang function mdb_env_set_map_size ganap na nagpapawalang-bisa sa lahat ng mga transaksyon at mga kaugnay na entity sa pangkalahatan at mga pointer sa ilang partikular na mga bagay.

Sa wakas, ang isa pang tampok ay napaka-insidious na ang pagbubunyag ng kakanyahan nito ay hindi angkop sa isa pang talata. Sa kabanata tungkol sa B-tree, nagbigay ako ng diagram kung paano nakaayos ang mga pahina nito sa memorya. Ito ay sumusunod mula dito na ang address ng simula ng buffer na may serialized na data ay maaaring maging ganap na arbitrary. Dahil dito, ang pointer sa kanila ay natanggap sa istraktura MDB_val at binawasan sa isang pointer sa isang istraktura, lumalabas na hindi nakahanay sa pangkalahatang kaso. Kasabay nito, ang mga arkitektura ng ilang chips (sa kaso ng iOS ito ay armv7) ay nangangailangan na ang address ng anumang data ay isang multiple ng laki ng machine word o, sa madaling salita, ang bit size ng system ( para sa armv7 ito ay 32 bits). Sa madaling salita, isang operasyon tulad ng *(int *foo)0x800002 sa kanila ay katumbas ng pagtakas at humahantong sa pagpapatupad na may hatol EXC_ARM_DA_ALIGN. Mayroong dalawang paraan upang maiwasan ang gayong malungkot na kapalaran.

Ang una ay bumagsak sa paunang pagkopya ng data sa isang malinaw na nakahanay na istraktura. Halimbawa, sa isang custom na comparator ito ay makikita bilang mga sumusunod.

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 // ...
}

Ang isang alternatibong paraan ay ang pag-abiso sa compiler nang maaga na ang mga istruktura ng key-value ay maaaring hindi nakahanay sa katangian aligned(1). Sa ARM maaari kang magkaroon ng parehong epekto upang makamit at gamit ang naka-pack na katangian. Isinasaalang-alang na nakakatulong din ito upang ma-optimize ang espasyo na inookupahan ng istraktura, ang pamamaraang ito ay tila mas gusto sa akin, bagaman приводит sa pagtaas ng halaga ng mga operasyon sa pag-access ng data.

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

Mga query sa hanay

Upang umulit sa isang pangkat ng mga talaan, ang LMDB ay nagbibigay ng cursor abstraction. Tingnan natin kung paano ito gagawin gamit ang halimbawa ng isang talahanayan na may user cloud metadata na pamilyar na sa amin.

Bilang bahagi ng pagpapakita ng listahan ng mga file sa isang direktoryo, kinakailangang hanapin ang lahat ng mga susi kung saan nauugnay ang mga child file at folder nito. Sa mga nakaraang subsection ay pinagsunod-sunod namin ang mga susi NodeKey na ang mga ito ay pangunahing inutusan ng ID ng parent directory. Kaya, sa teknikal, ang gawain ng pagkuha ng mga nilalaman ng isang folder ay bumababa sa paglalagay ng cursor sa itaas na hangganan ng pangkat ng mga susi na may ibinigay na prefix at pagkatapos ay umulit sa ibabang hangganan.

Ang upper bound ay direktang matatagpuan sa pamamagitan ng sequential search. Upang gawin ito, inilalagay ang cursor sa simula ng buong listahan ng mga susi sa database at dagdagan pa hanggang sa lumitaw ang isang key na may identifier ng direktoryo ng magulang sa ibaba nito. Ang diskarte na ito ay may 2 halatang kawalan:

1. Ang pagiging kumplikado ng linear na paghahanap, bagaman, tulad ng nalalaman, sa mga puno sa pangkalahatan at sa isang B-tree sa partikular, maaari itong isagawa sa oras ng logarithmic.​
2. Sa walang kabuluhan, ang lahat ng mga pahina bago ang hinahanap ay itinaas mula sa file patungo sa pangunahing memorya, na napakamahal.

Sa kabutihang palad, ang LMDB API ay nagbibigay ng isang epektibong paraan upang paunang iposisyon ang cursor. Upang gawin ito, kailangan mong bumuo ng isang key na ang halaga ay malinaw na mas mababa o katumbas ng key na matatagpuan sa itaas na hangganan ng pagitan. Halimbawa, na may kaugnayan sa listahan sa figure sa itaas, maaari kaming gumawa ng isang susi kung saan ang field parentId ay magiging katumbas ng 2, at ang lahat ng natitira ay puno ng mga zero. Ang nasabing key na bahagyang napuno ay ibinibigay sa input ng function mdb_cursor_get na nagpapahiwatig ng operasyon 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);

Kung ang itaas na hangganan ng isang pangkat ng mga susi ay matatagpuan, pagkatapos ay inuulit namin ito hanggang sa magkita kami o ang susi ay matugunan ang isa pa. parentId, o hindi mauubos ang mga susi.​

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​​

Ang maganda ay bilang bahagi ng pag-ulit gamit ang mdb_cursor_get, nakukuha namin hindi lamang ang susi, kundi pati na rin ang halaga. Kung, upang matupad ang mga kundisyon ng sampling, kailangan mong suriin, bukod sa iba pang mga bagay, ang mga patlang mula sa bahagi ng halaga ng tala, kung gayon ang mga ito ay lubos na naa-access nang walang karagdagang mga galaw.

4.3. Pagmomodelo ng mga ugnayan sa pagitan ng mga talahanayan

Sa ngayon, nagawa naming isaalang-alang ang lahat ng aspeto ng pagdidisenyo at pagtatrabaho sa isang solong talahanayan na database. Masasabi nating ang talahanayan ay isang hanay ng mga pinagsunod-sunod na talaan na binubuo ng parehong uri ng mga pares ng key-value. Kung magpapakita ka ng isang susi bilang isang parihaba at ang nauugnay na halaga bilang isang parallelepiped, makakakuha ka ng isang visual na diagram ng database.

​

Gayunpaman, sa totoong buhay ay bihirang posible na makayanan ang napakaliit na pagdanak ng dugo. Kadalasan sa isang database ay kinakailangan, una, na magkaroon ng ilang mga talahanayan, at pangalawa, upang gumawa ng mga seleksyon sa mga ito sa isang pagkakasunud-sunod na naiiba mula sa pangunahing susi. Ang huling seksyon na ito ay nakatuon sa mga isyu ng kanilang paglikha at pagkakaugnay.

Mga talahanayan ng index

Ang cloud application ay may seksyong "Gallery". Nagpapakita ito ng nilalaman ng media mula sa buong ulap, pinagsunod-sunod ayon sa petsa. Upang mahusay na maipatupad ang gayong pagpili, sa tabi ng pangunahing talahanayan kailangan mong lumikha ng isa pa na may bagong uri ng mga susi. Maglalaman ang mga ito ng field na may petsa kung kailan ginawa ang file, na magsisilbing pangunahing pamantayan sa pag-uuri. Dahil ang mga bagong key ay tumutukoy sa parehong data tulad ng mga key sa pangunahing talahanayan, ang mga ito ay tinatawag na mga index key. Sa larawan sa ibaba sila ay naka-highlight sa orange.

Upang paghiwalayin ang mga susi ng iba't ibang mga talahanayan mula sa bawat isa sa loob ng parehong database, isang karagdagang teknikal na field tableId ay idinagdag sa lahat ng mga ito. Sa pamamagitan ng paggawa nitong pinakamataas na priyoridad para sa pag-uuri, makakamit muna namin ang pagpapangkat ng mga susi ayon sa mga talahanayan, at sa loob ng mga talahanayan - ayon sa sarili naming mga panuntunan.​

Ang index key ay tumutukoy sa parehong data bilang pangunahing key. Ang isang tuwirang pagpapatupad ng property na ito sa pamamagitan ng pag-uugnay dito ng isang kopya ng bahagi ng halaga ng pangunahing key ay hindi pinakamainam mula sa ilang mga punto ng view:

1. Sa mga tuntunin ng espasyo na kinuha, ang metadata ay maaaring maging mayaman.
2. Mula sa pananaw ng pagganap, dahil kapag ina-update ang metadata ng isang node, kakailanganin mong muling isulat ito gamit ang dalawang key.
3. Mula sa punto ng view ng suporta sa code, kung nakalimutan nating i-update ang data para sa isa sa mga susi, makakakuha tayo ng mailap na bug ng hindi pagkakapare-pareho ng data sa storage.

Susunod, isasaalang-alang natin kung paano aalisin ang mga pagkukulang na ito.

Pag-aayos ng mga relasyon sa pagitan ng mga talahanayan

Ang pattern ay angkop para sa pag-uugnay ng index table sa pangunahing talahanayan "susi bilang halaga". Gaya ng ipinahihiwatig ng pangalan nito, ang bahagi ng halaga ng talaan ng index ay isang kopya ng pangunahing halaga ng pangunahing key. Tinatanggal ng diskarteng ito ang lahat ng nabanggit na disadvantages na nauugnay sa pag-iimbak ng kopya ng bahagi ng halaga ng pangunahing talaan. Ang tanging gastos ay upang makakuha ng isang halaga sa pamamagitan ng index key, kailangan mong gumawa ng 2 query sa database sa halip na isa. Sa eskematiko, ang resultang database schema ay ganito ang hitsura.

Ang isa pang pattern para sa pag-aayos ng mga relasyon sa pagitan ng mga talahanayan ay "redundant key". Ang kakanyahan nito ay upang magdagdag ng mga karagdagang katangian sa susi, na kinakailangan hindi para sa pag-uuri, ngunit para sa muling paglikha ng nauugnay na susi. Sa application ng Mail.ru Cloud mayroong mga tunay na halimbawa ng paggamit nito, gayunpaman, upang maiwasan ang malalim na pagsisid sa ang konteksto ng mga partikular na balangkas ng iOS, magbibigay ako ng isang kathang-isip, ngunit isang mas malinaw na halimbawa.​

Ang mga cloud mobile client ay may page na nagpapakita ng lahat ng file at folder na ibinahagi ng user sa ibang tao. Dahil medyo kakaunti ang mga ganoong file, at maraming iba't ibang uri ng partikular na impormasyon tungkol sa publisidad na nauugnay sa kanila (kung sino ang nabigyan ng access, kung anong mga karapatan, atbp.), hindi makatwiran na pasanin ang halaga ng bahagi ng itala sa pangunahing talahanayan kasama nito. Gayunpaman, kung gusto mong ipakita ang mga ganoong file nang offline, kailangan mo pa rin itong iimbak sa isang lugar. Ang isang natural na solusyon ay ang lumikha ng isang hiwalay na talahanayan para dito. Sa diagram sa ibaba, ang susi nito ay may prefix na "P", at ang placeholder na "propname" ay maaaring palitan ng mas partikular na halaga na "pampublikong impormasyon."​

Ang lahat ng natatanging metadata, para sa kapakanan ng pag-iimbak kung saan nilikha ang bagong talahanayan, ay inilalagay sa bahagi ng halaga ng talaan. Kasabay nito, hindi mo gustong i-duplicate ang data tungkol sa mga file at folder na nakaimbak na sa pangunahing talahanayan. Sa halip, idinaragdag ang redundant na data sa "P" key sa anyo ng mga field na "node ID" at "timestamp". Salamat sa kanila, maaari kang bumuo ng isang index key, kung saan makakakuha ka ng pangunahing key, kung saan, sa wakas, maaari kang makakuha ng metadata ng node.

Konklusyon

Positibong tinatasa namin ang mga resulta ng pagpapatupad ng LMDB. Pagkatapos nito, ang bilang ng mga pag-freeze ng aplikasyon ay nabawasan ng 30%.

Ang mga resulta ng gawaing ginawa ay umalingawngaw sa kabila ng iOS team. Sa kasalukuyan, ang isa sa mga pangunahing seksyon ng "Mga File" sa Android application ay lumipat din sa paggamit ng LMDB, at ang iba pang mga bahagi ay nasa daan. Ang wikang C, kung saan ipinatupad ang key-value store, ay isang magandang tulong para sa simula ay lumikha ng isang framework ng application sa paligid nito na cross-platform sa C++. Ginamit ang isang code generator upang walang putol na ikonekta ang nagresultang C++ library na may platform code sa Objective-C at Kotlin Jinni mula sa Dropbox, ngunit iyon ay isang ganap na naiibang kuwento.

Pinagmulan: www.habr.com