Yn ystod cwymp 2019, cynhaliwyd digwyddiad hir-ddisgwyliedig yn nhîm iOS Cloud Mail.ru. Mae'r brif gronfa ddata ar gyfer storio cyflwr cymwysiadau yn barhaus wedi dod yn eithaf egsotig ar gyfer y byd symudol Cronfa Ddata Cof Mellt (LMDB). O dan y toriad, gwahoddir eich sylw at ei adolygiad manwl mewn pedair rhan. Yn gyntaf, gadewch i ni siarad am y rhesymau dros ddewis mor ddibwys ac anodd. Yna gadewch i ni symud ymlaen i ystyried tri morfil sydd wrth wraidd pensaernïaeth LMDB: ffeiliau cof-mapio, coeden B +, dull copi-ar-ysgrifennu ar gyfer gweithredu trafodion ac amldroad. Yn olaf, ar gyfer pwdin - y rhan ymarferol. Ynddo, byddwn yn edrych ar sut i ddylunio a gweithredu sgema sylfaenol gyda sawl tabl, gan gynnwys mynegai un, ar ben yr API lefel isel o werth allweddol.

Cynnwys

1. Cymhelliad Gweithredu
2. Lleoli LMDB
3. Tri morfil LMDB
   3.1. Morfil #1. Ffeiliau cof-mapio
   3.2. Morfil #2. B+ - coeden
   3.3. Morfil #3. copi-ar-ysgrifennu
4. Dylunio sgema data ar ben yr API gwerth bysell
   4.1. Tyniadau sylfaenol
   4.2. Modelu Tabl
   4.3. Modelu perthnasoedd rhwng tablau

1. Cymhelliant gweithredu

Unwaith y flwyddyn, yn 2015, fe wnaethom ofalu am gymryd metrig, pa mor aml y mae rhyngwyneb ein cymhwysiad yn llusgo. Nid dim ond hyn a wnaethom. Mae gennym fwy a mwy o gwynion am y ffaith bod y rhaglen weithiau'n rhoi'r gorau i ymateb i weithredoedd defnyddwyr: nid yw botymau'n cael eu pwyso, nid yw rhestrau'n sgrolio, ac ati. Ynglŷn â mecaneg mesuriadau meddai ar AvitoTech, felly dyma roi trefn y rhifau yn unig.

Daeth canlyniadau'r mesur yn gawod oer i ni. Mae'n troi allan bod y problemau a achosir gan rewi yn llawer mwy nag unrhyw un arall. Os, cyn sylweddoli'r ffaith hon, roedd y prif ddangosydd technegol o ansawdd yn rhydd o ddamwain, yna ar ôl y ffocws symud ar rewi rhad ac am ddim.

Wedi adeiladu dangosfwrdd gyda rhewi ac wedi gwario meintiol и ansawdd dadansoddiad o'u hachosion, daeth y prif elyn yn amlwg - gweithredu rhesymeg busnes trwm ym mhrif edefyn y cais. Ymateb naturiol i'r gwarth hwn oedd awydd tanbaid i'w wthio i ffrydiau gwaith. I gael datrysiad systematig i'r broblem hon, fe wnaethom droi at bensaernïaeth aml-edau yn seiliedig ar actorion ysgafn. Cysegrais ei haddasiadau ar gyfer y byd iOS dwy edau yn y twitter cyfunol a erthygl ar Habré. Fel rhan o’r stori gyfredol, rwyf am bwysleisio’r agweddau hynny ar y penderfyniad a ddylanwadodd ar y dewis o’r gronfa ddata.​

Mae'r model actor o drefniadaeth systemau yn cymryd yn ganiataol mai aml-edau yw ei ail hanfod. Mae gwrthrychau model ynddo yn hoffi croesi ffiniau edau. Ac maen nhw'n gwneud hyn nid weithiau ac mewn rhai mannau, ond bron yn gyson ac ym mhobman.

Mae'r gronfa ddata yn un o gydrannau conglfaen y diagram a gyflwynir. Ei brif dasg yw gweithredu patrwm macro Cronfa Ddata a Rennir. Os yn y byd menter fe'i defnyddir i drefnu cydamseru data rhwng gwasanaethau, yna yn achos pensaernïaeth actor, data rhwng edafedd. Felly, roedd angen cronfa ddata o'r fath arnom, ac nid yw gweithio gyda hi mewn amgylchedd aml-edau yn achosi hyd yn oed ychydig iawn o anawsterau. Yn benodol, mae hyn yn golygu bod yn rhaid i'r gwrthrychau sy'n deillio ohono fod o leiaf yn ddiogel rhag edau, ac yn ddelfrydol heb fod yn fudradwy o gwbl. Fel y gwyddoch, gellir defnyddio'r olaf ar yr un pryd o sawl edafedd heb droi at unrhyw fath o gloeon, sy'n cael effaith fuddiol ar berfformiad.

Yr ail ffactor arwyddocaol a ddylanwadodd ar y dewis o'r gronfa ddata oedd ein API cwmwl. Fe'i hysbrydolwyd gan y dull git o gydamseru. Fel ef yr oeddem yn anelu ato API cyntaf all-lein, sy'n edrych yn fwy na phriodol ar gyfer cleientiaid cwmwl. Tybiwyd mai dim ond unwaith y byddent yn pwmpio cyflwr llawn y cwmwl allan, ac yna byddai cydamseru yn y mwyafrif helaeth o achosion yn digwydd trwy newidiadau treigl. Ysywaeth, mae'r posibilrwydd hwn yn dal i fod yn y parth damcaniaethol yn unig, ac yn ymarferol, nid yw cleientiaid wedi dysgu sut i weithio gyda chlytiau. Mae yna nifer o resymau gwrthrychol am hyn, ac er mwyn peidio ag oedi cyn cyflwyno, byddwn yn gadael allan o'r cromfachau. Nawr yn llawer mwy diddorol yw canlyniadau addysgiadol y wers am yr hyn sy'n digwydd pan ddywedodd yr API "A" ac nid oedd ei ddefnyddiwr yn dweud "B".

Felly, os dychmygwch git, sydd, wrth weithredu gorchymyn tynnu, yn hytrach na chymhwyso clytiau i giplun lleol, yn cymharu ei gyflwr llawn â'r gweinydd llawn un, yna bydd gennych syniad eithaf cywir o gydamseru yn digwydd mewn cleientiaid cwmwl. Mae'n hawdd dyfalu, ar gyfer ei weithredu, bod angen dyrannu dwy goeden DOM er cof gyda meta-wybodaeth am yr holl weinyddion a ffeiliau lleol. Mae'n ymddangos, os yw defnyddiwr yn storio 500 mil o ffeiliau yn y cwmwl, yna i'w cydamseru, mae angen ail-greu a dinistrio dwy goeden gyda 1 miliwn o nodau. Ond mae pob nod yn agreg sy'n cynnwys graff o wrthrychau. Yn y goleuni hwn, disgwylid y canlyniadau proffilio. Mae'n troi allan, hyd yn oed heb ystyried yr algorithm uno, mae'r union weithdrefn o greu ac yna dinistrio nifer fawr o wrthrychau bach yn costio ceiniog eithaf.Mae'r sefyllfa'n cael ei gwaethygu gan y ffaith bod y gweithrediad cydamseru sylfaenol wedi'i gynnwys mewn nifer fawr o sgriptiau defnyddwyr. O ganlyniad, rydym yn gosod yr ail faen prawf pwysig wrth ddewis cronfa ddata - y gallu i weithredu gweithrediadau CRUD heb ddyraniad deinamig o wrthrychau.

Mae gofynion eraill yn fwy traddodiadol, ac mae eu rhestr lawn fel a ganlyn.

1. Diogelwch edafedd.
2. Amlbrosesu. Wedi'i bennu gan yr awydd i ddefnyddio'r un enghraifft cronfa ddata i gydamseru cyflwr nid yn unig rhwng edafedd, ond hefyd rhwng y prif gymhwysiad ac estyniadau iOS.
3. Y gallu i gynrychioli endidau sydd wedi'u storio fel gwrthrychau na ellir eu cyfnewid
4. Diffyg dyraniadau deinamig o fewn gweithrediadau CRUD.
5. Cymorth Trafodion ar gyfer Priodweddau Sylfaenol ACIDGeiriau allweddol: atomigrwydd, cysondeb, ynysu a dibynadwyedd.
6. Cyflymder ar yr achosion mwyaf poblogaidd.

Gyda'r set hon o ofynion, roedd SQLite yn ddewis da ac yn dal i fod. Fodd bynnag, fel rhan o'r astudiaeth o ddewisiadau eraill, deuthum ar draws llyfr "Dechrau Arni gyda LevelDB". O dan ei harweinyddiaeth, ysgrifennwyd meincnod sy'n cymharu cyflymder gwaith gyda gwahanol gronfeydd data mewn senarios cwmwl go iawn. Roedd y canlyniad yn rhagori ar y disgwyliadau mwyaf gwyllt. Ar yr achosion mwyaf poblogaidd - cael cyrchwr ar restr wedi'i didoli o'r holl ffeiliau a rhestr wedi'i didoli o'r holl ffeiliau ar gyfer cyfeiriadur penodol - roedd LMDB 10 gwaith yn gyflymach na SQLite. Daeth y dewis yn amlwg.

2. Lleoli LMDB

Mae LMDB yn llyfrgell, fach iawn (dim ond llinellau 10K) sy'n gweithredu'r haen sylfaenol isaf o gronfeydd data - storio.

Mae'r diagram uchod yn dangos nad yw cymharu LMDB â SQLite, sy'n gweithredu lefelau uwch fyth, yn fwy cywir yn gyffredinol na SQLite gyda Data Craidd. Byddai'n fwy teg dyfynnu'r un peiriannau storio â chystadleuwyr cyfartal - BerkeleyDB, LevelDB, Sophia, RocksDB, ac ati Mae hyd yn oed ddatblygiadau lle mae LMDB yn gweithredu fel cydran injan storio ar gyfer SQLite. Yr arbrawf cyntaf o'r fath yn 2012 wedi treulio awdur LMDB Howard Chu. Canfyddiadau troi allan i fod mor ddiddorol fel bod ei flaengaredd wedi'i godi gan selogion yr OSS, a chanfod ei barhad yn wyneb LumoSQL. Ym mis Ionawr 2020 awdur y prosiect hwn yw Den Shearer cyflwyno mae ar LinuxConfAu.

Prif ddefnydd LMDB yw fel peiriant ar gyfer cronfeydd data cymwysiadau. Mae'r llyfrgell yn ddyledus i'r datblygwyr OpenLDAP, a oedd yn anfodlon iawn â BerkeleyDB fel sail eu prosiect. Gwthio i ffwrdd o'r llyfrgell ostyngedig btree, Roedd Howard Chu yn gallu creu un o'r dewisiadau amgen mwyaf poblogaidd o'n hamser. Rhoddodd ei adroddiad cŵl iawn i'r stori hon, yn ogystal ag i strwythur mewnol LMDB. "Cronfa Ddata Cof Mellt". Leonid Yuriev (aka yleo) gan Positive Technologies yn ei sgwrs yn Highload 2015 "Mae'r injan LMDB yn bencampwr arbennig". Ynddo, mae'n sôn am LMDB yng nghyd-destun tasg debyg o weithredu ReOpenLDAP, ac mae LevelDB eisoes wedi cael beirniadaeth gymharol. O ganlyniad i'r gweithredu, cafodd Positive Technologies hyd yn oed fforch sy'n datblygu'n weithredol MDBX gyda nodweddion blasus iawn, optimizations a atgyweiriadau byg.

Defnyddir LMDB yn aml fel storfa yn ogystal â storfa hefyd. Er enghraifft, porwr Mozilla Firefox dewis ar gyfer nifer o anghenion, ac, gan ddechrau o fersiwn 9, Xcode ffafriedig ei SQLite i storio mynegeion.

Daliodd yr injan ymlaen hefyd ym myd datblygu ffonau symudol. Gall olion ei ddefnydd fod i ddod o hyd yn y cleient iOS ar gyfer Telegram. Aeth LinkedIn un cam ymhellach a dewisodd LMDB fel storfa ddiofyn ar gyfer ei fframwaith storio data cartref, Rocket Data, am ba un dweud mewn erthygl yn 2016.

Mae LMDB yn ymladd yn llwyddiannus am le yn yr haul yn y gilfach a adawyd gan BerkeleyDB ar ôl y cyfnod pontio dan reolaeth Oracle. Mae'r llyfrgell yn cael ei charu am ei chyflymder a'i dibynadwyedd, hyd yn oed o'i chymharu â'i math ei hun. Fel y gwyddoch, nid oes unrhyw ginio am ddim, a hoffwn bwysleisio’r cyfaddawd y bydd yn rhaid ichi ei wynebu wrth ddewis rhwng LMDB a SQLite. Mae'r diagram uchod yn dangos yn glir sut mae'r cyflymder cynyddol yn cael ei gyflawni. Yn gyntaf, nid ydym yn talu am haenau ychwanegol o dynnu ar ben storio disg. Wrth gwrs, mewn pensaernïaeth dda, ni allwch wneud hebddynt o hyd, ac mae'n anochel y byddant yn ymddangos yn y cod cais, ond byddant yn llawer teneuach. Ni fydd ganddynt nodweddion nad oes eu hangen ar raglen benodol, er enghraifft, cefnogaeth ar gyfer ymholiadau yn yr iaith SQL. Yn ail, mae'n dod yn bosibl i weithredu'r mapio gweithrediadau cais i geisiadau i storio disg yn optimaidd. Os SQLite yn fy ngwaith yn dod o anghenion cyfartalog cais cyfartalog, yna rydych chi, fel datblygwr cais, yn ymwybodol iawn o'r senarios prif lwyth. I gael datrysiad mwy cynhyrchiol, bydd yn rhaid i chi dalu tag pris uwch ar gyfer datblygu'r datrysiad cychwynnol a'i gefnogaeth ddilynol.

3. Tri morfil LMDB

Ar ôl edrych ar y LMDB o olwg aderyn, mae'n bryd mynd yn ddyfnach. Bydd y tair adran nesaf yn cael eu neilltuo i ddadansoddi'r prif forfilod y mae'r bensaernïaeth storio yn dibynnu arnynt:

1. Ffeiliau wedi'u mapio cof fel mecanwaith ar gyfer gweithio gyda disg a chydamseru strwythurau data mewnol.
2. B+-tree fel sefydliad o'r strwythur data sydd wedi'i storio.
3. Copi-ar-ysgrifennu fel dull o ddarparu priodweddau trafodion ACID ac amlfersiwn.

3.1. Morfil #1. Ffeiliau cof-mapio

Mae ffeiliau wedi'u mapio cof yn elfen bensaernïol mor bwysig fel eu bod hyd yn oed yn ymddangos yn enw'r ystorfa. Mae materion yn ymwneud â storio a chydamseru mynediad i wybodaeth sydd wedi'i storio ar drugaredd y system weithredu yn gyfan gwbl. Nid yw LMDB yn cynnwys unrhyw caches ynddo'i hun. Mae hwn yn benderfyniad ymwybodol gan yr awdur, gan fod darllen data yn uniongyrchol o ffeiliau wedi'u mapio yn caniatáu ichi dorri llawer o gorneli wrth weithredu'r injan. Isod mae rhestr ymhell o fod yn gyflawn o rai ohonynt.

1. Mae cynnal cysondeb data yn y storfa wrth weithio gydag ef o sawl proses yn dod yn gyfrifoldeb y system weithredu. Yn yr adran nesaf, trafodir y mecanig hwn yn fanwl a chyda lluniau.
2. Mae absenoldeb caches yn rhyddhau LMDB yn llwyr o'r gorbenion sy'n gysylltiedig â dyraniadau deinamig. Mae darllen data yn ymarferol yn gosod y pwyntydd i'r cyfeiriad cywir mewn cof rhithwir a dim byd mwy. Mae'n swnio fel ffantasi, ond yn y ffynhonnell ystorfa, mae'r holl alwadau calloc wedi'u crynhoi yn swyddogaeth ffurfweddu'r ystorfa.
3. Mae absenoldeb caches hefyd yn golygu absenoldeb cloeon sy'n gysylltiedig â chydamseru i gael mynediad iddynt. Nid yw darllenwyr, y gall rhif mympwyol ohonynt fodoli ar yr un pryd, yn dod ar draws un mutex ar eu ffordd i'r data. Oherwydd hyn, mae gan y cyflymder darllen scalability llinol delfrydol o ran nifer y CPUs. Yn LMDB, dim ond gweithrediadau addasu sy'n cael eu cydamseru. Dim ond un llenor a all fod ar y tro.
4. Mae isafswm o resymeg caching a synchronization yn arbed y cod rhag math hynod gymhleth o wallau sy'n gysylltiedig â gweithio mewn amgylchedd aml-edau. Roedd dwy astudiaeth cronfa ddata ddiddorol yng nghynhadledd Usenix OSDI 2014: "Nid yw'r holl Systemau Ffeil wedi'u Creu'n Gyfartal: Ynghylch Cymhlethdod Crefftau Cymwysiadau Cwymp-Cyson" и Arteithio Cronfeydd Data er Hwyl ac Elw. Oddi wrthynt gallwch gael gwybodaeth am ddibynadwyedd digynsail LMDB, a gweithrediad bron yn ddi-ffael o briodweddau ACID trafodion, sy'n rhagori arno yn yr un SQLite.
5. Mae minimaliaeth LMDB yn caniatáu i gynrychiolaeth peiriant ei god gael ei osod yn llwyr yn storfa L1 y prosesydd gyda'r nodweddion cyflymder canlyniadol.

Yn anffodus, yn iOS, nid yw ffeiliau cof-fapio mor rosy ag yr hoffem. I siarad am yr anfanteision sy'n gysylltiedig â nhw yn fwy ymwybodol, mae angen cofio'r egwyddorion cyffredinol ar gyfer gweithredu'r mecanwaith hwn mewn systemau gweithredu.

Gwybodaeth gyffredinol am ffeiliau cof-mapio

Gyda phob cymhwysiad gweithredadwy, mae'r system weithredu yn cysylltu endid a elwir yn broses. Rhoddir ystod gyfagos o gyfeiriadau i bob proses, lle mae'n gosod popeth sydd ei angen arni i weithio. Mae'r cyfeiriadau isaf yn cynnwys adrannau â chod a data ac adnoddau â chod caled. Nesaf daw'r bloc cynyddol o ofod cyfeiriad deinamig, sy'n adnabyddus i ni fel y domen. Mae'n cynnwys cyfeiriadau endidau sy'n ymddangos yn ystod gweithrediad y rhaglen. Ar y brig mae ardal y cof a ddefnyddir gan y pentwr cais. Mae naill ai'n tyfu neu'n crebachu, mewn geiriau eraill, mae gan ei faint natur ddeinamig hefyd. Fel nad yw'r pentwr a'r domen yn gwthio ac yn ymyrryd â'i gilydd, maent yn cael eu gwahanu ar wahanol bennau'r gofod cyfeiriad Mae twll rhwng y ddwy adran ddeinamig ar y brig a'r gwaelod. Mae'r cyfeiriadau yn yr adran ganol hon yn cael eu defnyddio gan y system weithredu i gysylltu â phroses o endidau amrywiol. Yn benodol, gall fapio set barhaus benodol o gyfeiriadau i ffeil ar ddisg. Gelwir ffeil o'r fath yn ffeil cof-map

Mae'r gofod cyfeiriad a neilltuwyd i broses yn enfawr. Yn ddamcaniaethol, mae nifer y cyfeiriadau yn gyfyngedig yn unig gan faint y pwyntydd, sy'n cael ei bennu gan bitness y system. Pe bai cof corfforol yn cael ei neilltuo iddo 1-in-1, yna byddai'r broses gyntaf yn llyncu'r RAM cyfan, ac ni fyddai unrhyw gwestiwn o unrhyw amldasgio.

Fodd bynnag, rydym yn gwybod o brofiad y gall systemau gweithredu modern redeg cymaint o brosesau ag y dymunwch ar yr un pryd. Mae hyn yn bosibl oherwydd eu bod yn dyrannu llawer o gof i brosesau yn unig ar bapur, ond mewn gwirionedd maent yn llwytho i mewn i'r prif gof corfforol dim ond y rhan y mae galw amdani yma ac yn awr. Felly, gelwir y cof sy'n gysylltiedig â'r broses yn rhithwir.

Mae'r system weithredu yn trefnu cof rhithwir a chorfforol yn dudalennau o faint penodol. Cyn gynted ag y bydd galw am dudalen benodol o gof rhithwir, mae'r system weithredu yn ei lwytho i gof corfforol ac yn gosod gohebiaeth rhyngddynt mewn tabl arbennig. Os nad oes slotiau rhad ac am ddim, yna mae un o'r tudalennau a lwythwyd yn flaenorol yn cael ei gopïo i ddisg, ac mae'r un y gofynnwyd amdano yn cymryd ei le. Gelwir y weithdrefn hon, y byddwn yn dychwelyd ati yn fuan, yn gyfnewid. Mae'r ffigur isod yn dangos y broses a ddisgrifir. Arddi, cafodd tudalen A gyda chyfeiriad 0 ei llwytho a'i gosod ar y brif dudalen cof gyda chyfeiriad 4. Adlewyrchwyd y ffaith hon yn y tabl gohebiaeth yng nghell rhif 0.

Gyda ffeiliau cof-fapio, mae'r stori yn union yr un fath. Yn rhesymegol, maent i fod i gael eu gosod yn barhaus ac yn gyfan gwbl yn y gofod cyfeiriad rhithwir. Fodd bynnag, maent yn mynd i mewn i gof corfforol dudalen wrth dudalen a dim ond ar alw. Mae addasu tudalennau o'r fath yn cael ei gysoni â'r ffeil ar ddisg. Felly, gallwch chi berfformio ffeil I / O, gan weithio gyda bytes yn y cof yn unig - bydd yr holl newidiadau'n cael eu trosglwyddo'n awtomatig gan gnewyllyn y system weithredu i'r ffeil wreiddiol.
​
Mae'r ddelwedd isod yn dangos sut mae LMDB yn cydamseru ei gyflwr wrth weithio gyda'r gronfa ddata o wahanol brosesau. Trwy fapio cof rhithwir gwahanol brosesau ar yr un ffeil, rydym yn de facto yn gorfodi'r system weithredu i gydamseru blociau penodol o'u gofodau cyfeiriad â'i gilydd, a dyna lle mae LMDB yn edrych.
​

Arlliw pwysig yw bod LMDB yn addasu'r ffeil ddata yn ddiofyn trwy fecanwaith galw'r system ysgrifennu, ac mae'r ffeil ei hun yn cael ei harddangos yn y modd darllen yn unig. Mae gan y dull hwn ddau oblygiad pwysig.

Mae'r canlyniad cyntaf yn gyffredin i bob system weithredu. Ei hanfod yw ychwanegu amddiffyniad rhag difrod anfwriadol i'r gronfa ddata trwy god anghywir. Fel y gwyddoch, mae cyfarwyddiadau gweithredadwy proses yn rhydd i gael mynediad at ddata o unrhyw le yn ei ofod cyfeiriad. Ar yr un pryd, fel yr oeddem newydd ei gofio, mae arddangos ffeil yn y modd darllen-ysgrifennu yn golygu y gall unrhyw gyfarwyddyd ei addasu hefyd. Os bydd hi'n gwneud hyn trwy gamgymeriad, gan geisio, er enghraifft, trosysgrifo elfen arae mewn mynegai nad yw'n bodoli, yna fel hyn gall newid y ffeil a fapiwyd i'r cyfeiriad hwn yn ddamweiniol, a fydd yn arwain at lygredd cronfa ddata. Os dangosir y ffeil yn y modd darllen-yn-unig, yna bydd ymgais i newid y gofod cyfeiriad sy'n cyfateb iddo yn arwain at ddamwain y rhaglen gyda'r signal SIGSEGV, a bydd y ffeil yn aros yn gyfan.

Mae'r ail ganlyniad eisoes yn benodol i iOS. Nid yw'r awdur nac unrhyw ffynonellau eraill yn sôn amdano'n benodol, ond hebddo, byddai LMDB yn anaddas i redeg ar y system weithredu symudol hon. Mae'r adran nesaf wedi'i neilltuo i'w hystyriaeth.

Manylion ffeiliau cof-mapio yn iOS

Yn 2018, cafwyd adroddiad gwych yn WWDC iOS Memory Deep Dive. Mae'n dweud bod yn iOS holl dudalennau lleoli mewn cof corfforol yn perthyn i un o 3 math: budr, cywasgedig a glân.

Mae cof glân yn gasgliad o dudalennau y gellir eu cyfnewid yn ddiogel allan o gof corfforol. Gellir ail-lwytho'r data sydd ynddynt o'u ffynonellau gwreiddiol yn ôl yr angen. Mae ffeiliau cof-fap darllen yn unig yn perthyn i'r categori hwn. Nid yw iOS yn ofni dadlwytho'r tudalennau sydd wedi'u mapio i ffeil o'r cof ar unrhyw adeg, gan eu bod yn sicr o gael eu cysoni â'r ffeil ar ddisg.
​
Mae pob tudalen wedi'i haddasu yn mynd i mewn i gof budr, ni waeth ble maen nhw wedi'u lleoli'n wreiddiol. Yn benodol, bydd ffeiliau cof-fap a addaswyd trwy ysgrifennu i'r cof rhithwir sy'n gysylltiedig â nhw hefyd yn cael eu dosbarthu fel hyn. Agor LMDB gyda baner MDB_WRITEMAP, ar ôl gwneud newidiadau iddo, gallwch weld drosoch eich hun.​

​Cyn gynted ag y bydd rhaglen yn dechrau cymryd gormod o gof corfforol, mae iOS yn cywasgu ei dudalennau budr. Y casgliad o gof a feddiannir gan dudalennau budr a chywasgedig yw ôl troed cof y cymhwysiad fel y'i gelwir. Pan fydd yn cyrraedd gwerth trothwy penodol, mae daemon system lladdwr OOM yn dod ar ôl y broses ac yn ei derfynu'n rymus. Dyma hynodrwydd iOS o'i gymharu â systemau gweithredu bwrdd gwaith. Mewn cyferbyniad, ni ddarperir gostwng ôl troed y cof trwy gyfnewid tudalennau o gof corfforol i ddisg yn iOS. Ni ellir ond dyfalu am y rhesymau. Efallai bod y weithdrefn ar gyfer symud tudalennau'n ddwys i ddisg ac yn ôl yn cymryd gormod o ynni ar gyfer dyfeisiau symudol, neu mae iOS yn arbed yr adnodd o ailysgrifennu celloedd ar yriannau SSD, neu efallai nad oedd y dylunwyr yn fodlon â pherfformiad cyffredinol y system, lle mae popeth yn cyfnewid yn gyson. Boed hynny fel y bo, mae'r ffaith yn parhau.

Y newyddion da, a grybwyllwyd eisoes yn gynharach, yw nad yw LMDB yn defnyddio'r mecanwaith mmap i ddiweddaru ffeiliau yn ddiofyn. Mae'n dilyn bod y data wedi'i rendro yn cael ei ddosbarthu fel cof glân gan iOS ac nid yw'n cyfrannu at ôl troed y cof. Gellir gwirio hyn gan ddefnyddio'r offeryn Xcode o'r enw VM Tracker. Mae'r sgrin isod yn dangos cyflwr cof rhithwir y cymhwysiad iOS Cloud yn ystod y llawdriniaeth. Ar y dechrau, dechreuwyd 2 achos LMDB ynddo. Caniatawyd i'r cyntaf fapio ei ffeil i 1GiB o gof rhithwir, yr ail - 512MiB. Er gwaethaf y ffaith bod y ddau storfa yn meddiannu rhywfaint o gof preswylwyr, nid yw'r naill na'r llall yn cyfrannu at y maint budr.

Nawr mae'n amser am y newyddion drwg. Diolch i'r mecanwaith cyfnewid mewn systemau gweithredu bwrdd gwaith 64-did, gall pob proses gymryd cymaint o le rhith-gyfeiriad ag y mae'r gofod rhydd ar y ddisg galed yn caniatáu ar gyfer cyfnewid posibl. Mae disodli cyfnewid â chywasgu yn iOS yn lleihau'r uchafswm damcaniaethol yn sylweddol. Nawr mae'n rhaid i bob proses fyw ffitio i mewn i'r prif gof (darllenwch RAM), ac mae pob un nad yw'n ffitio yn destun terfyniad gorfodol. Crybwyllir fel yn yr uchod adroddiad, ac yn dogfennaeth swyddogol. O ganlyniad, mae iOS yn cyfyngu'n ddifrifol ar faint o gof sydd ar gael i'w ddyrannu trwy mmap. Yma yma gallwch edrych ar y terfynau empirig ar faint o gof y gellid ei ddyrannu ar wahanol ddyfeisiau gan ddefnyddio'r alwad system hon. Ar y modelau mwyaf modern o ffonau smart, mae iOS wedi dod yn hael gan 2 gigabeit, ac ar fersiynau uchaf y iPad - erbyn 4. Yn ymarferol, wrth gwrs, mae'n rhaid i chi ganolbwyntio ar y modelau dyfais a gefnogir ieuengaf, lle mae popeth yn drist iawn. Hyd yn oed yn waeth, o edrych ar gyflwr cof y cais yn VM Tracker, fe welwch fod LMDB ymhell o fod yr unig un sy'n hawlio cof wedi'i fapio gan gof. Mae talpiau da yn cael eu bwyta gan ddyranwyr systemau, ffeiliau adnoddau, fframweithiau delwedd, ac ysglyfaethwyr llai eraill.

O ganlyniad i arbrofion yn y Cwmwl, fe wnaethom lunio'r gwerthoedd cyfaddawd canlynol o gof a ddyrannwyd gan LMDB: 384 megabeit ar gyfer dyfeisiau 32-bit a 768 ar gyfer rhai 64-bit. Ar ôl i'r gyfrol hon gael ei defnyddio, mae unrhyw weithrediadau addasu yn dechrau cwblhau gyda'r cod MDB_MAP_FULL. Rydym yn sylwi ar gamgymeriadau o'r fath yn ein monitro, ond maent yn ddigon bach i gael eu hesgeuluso ar hyn o bryd.

Gall rheswm nad yw'n amlwg dros fwyta gormod o gof trwy storio fod yn drafodion hirhoedlog. Er mwyn deall sut mae'r ddau ffenomen hyn yn gysylltiedig, bydd yn ein helpu i ystyried y ddau forfil LMDB sy'n weddill.

3.2. Morfil #2. B+ - coeden

I efelychu tablau ar ben storfa gwerth allweddol, rhaid i'r gweithrediadau canlynol fod yn bresennol yn ei API:

1. Mewnosod elfen newydd.
2. Chwiliwch am elfen ag allwedd benodol.
3. Dileu elfen.
4. Ailadrodd dros gyfnodau allweddol yn eu trefn.

Y strwythur data symlaf sy'n gallu gweithredu'r pedwar gweithrediad yn hawdd yw coeden chwilio ddeuaidd. Mae pob un o'i nodau yn allwedd sy'n rhannu'r is-set gyfan o allweddi plentyn yn ddwy is-goeden. Ar y chwith mae'r rhai sy'n llai na'r rhiant, ac ar y dde - y rhai sy'n fwy. Cyflawnir cael set drefnus o allweddi trwy un o'r llwybrau coed clasurol

Mae gan goed deuaidd ddau anfantais sylfaenol sy'n eu hatal rhag bod yn effeithiol fel strwythur data disg. Yn gyntaf, mae graddau eu cydbwysedd yn anrhagweladwy. Mae risg sylweddol o gael coed lle gall uchder gwahanol ganghennau amrywio'n fawr, sy'n gwaethygu cymhlethdod algorithmig y chwiliad yn sylweddol o'i gymharu â'r hyn a ddisgwylir. Yn ail, mae'r toreth o groesgysylltiadau rhwng nodau yn amddifadu coed deuaidd o leoliad yn y cof.Gellir lleoli nodau agos (yn nhermau cysylltiadau rhyngddynt) ar dudalennau cwbl wahanol mewn cof rhithwir. O ganlyniad, efallai y bydd angen ymweld â nifer tebyg o dudalennau hyd yn oed er mwyn croesi sawl nod cyfagos mewn coeden. Mae hon yn broblem hyd yn oed pan fyddwn yn siarad am effeithiolrwydd coed deuaidd fel strwythur data cof, gan nad yw cylchdroi tudalennau yn gyson yn storfa'r prosesydd yn rhad. O ran codi tudalennau sy'n gysylltiedig â nodau oddi ar ddisg yn aml, mae pethau'n mynd yn ddrwg iawn. gresynus.

Mae coed B, gan eu bod yn esblygiad o goed deuaidd, yn datrys y problemau a nodwyd yn y paragraff blaenorol. Yn gyntaf, maent yn hunan-gydbwyso. Yn ail, mae pob un o'u nodau yn rhannu'r set o allweddi plentyn nid yn 2, ond yn is-setiau gorchymyn M, a gall y rhif M fod yn eithaf mawr, yn ôl trefn rhai cannoedd neu hyd yn oed filoedd.

A thrwy hynny:

1. Mae gan bob nod nifer fawr o allweddi a archebwyd eisoes ac mae'r coed yn isel iawn.
2. Mae'r goeden yn caffael eiddo'r ardal er cof, gan fod allweddi sy'n agos o ran gwerth wedi'u lleoli'n naturiol wrth ymyl ei gilydd ar un nod neu nodau cyfagos.
3. Yn lleihau nifer y nodau tramwy wrth ddisgyn y goeden yn ystod gweithrediad chwilio.
4. Yn lleihau nifer y nodau targed a ddarllenir ar gyfer ymholiadau ystod, gan fod pob un ohonynt eisoes yn cynnwys nifer fawr o allweddi archebedig.

Mae LMDB yn defnyddio amrywiad o'r goeden B o'r enw'r goeden B+ i storio data. Mae’r diagram uchod yn dangos y tri math o nodau y mae’n eu cynnwys:

1. Ar y brig mae'r gwraidd. Nid yw'n gwireddu dim mwy na'r cysyniad o gronfa ddata o fewn ystorfa. O fewn un enghraifft LMDB, gallwch greu cronfeydd data lluosog sy'n rhannu'r gofod cyfeiriad rhithwir wedi'i fapio. Mae pob un ohonynt yn dechrau o'i wreiddyn ei hun.
2. Ar y lefel isaf mae'r dail (deilen). Nhw a dim ond nhw sy'n cynnwys y parau gwerth allweddol sydd wedi'u storio yn y gronfa ddata. Gyda llaw, dyma hynodrwydd coed B+. Os yw coeden B arferol yn storio'r rhannau gwerth ar nodau pob lefel, yna dim ond ar yr un isaf mae'r amrywiad B+. Ar ôl cywiro'r ffaith hon, yn yr hyn sy'n dilyn byddwn yn galw'r isdeip o'r goeden a ddefnyddir yn LMDB yn goeden B yn unig.
3. Rhwng y gwreiddyn a'r dail, mae 0 neu fwy o lefelau technegol gyda nodau llywio (cangen). Eu tasg yw rhannu'r set o allweddi wedi'u didoli rhwng y dail.

Yn gorfforol, mae nodau yn flociau o gof o hyd a bennwyd ymlaen llaw. Mae eu maint yn lluosrif maint y tudalennau cof yn y system weithredu, y buom yn siarad amdanynt uchod. Mae strwythur y nodau i'w weld isod. Mae'r pennawd yn cynnwys meta-wybodaeth, a'r mwyaf amlwg ohonynt, er enghraifft, yw'r siec. Nesaf daw gwybodaeth am wrthbwyso, ar hyd pa gelloedd â data sydd wedi'u lleoli. Gall rôl data fod naill ai'n allweddi, os ydym yn sôn am nodau llywio, neu barau gwerth bysell cyfan yn achos dail. Gallwch ddarllen mwy am strwythur tudalennau yn y gwaith "Gwerthusiad o Storfeydd Gwerth Allweddol Perfformiad Uchel".

Ar ôl ymdrin â chynnwys mewnol y nodau tudalen, byddwn yn cynrychioli'r goeden B LMDB ymhellach mewn ffordd symlach yn y ffurf ganlynol.

Trefnir tudalennau gyda nodau yn olynol ar ddisg. Lleolir tudalennau gyda nifer uwch tua diwedd y ffeil. Mae'r dudalen meta fel y'i gelwir (tudalen meta) yn cynnwys gwybodaeth am wrthbwyso, y gellir ei ddefnyddio i ddod o hyd i wreiddiau'r holl goed. Pan agorir ffeil, mae LMDB yn sganio'r ffeil fesul tudalen o'r diwedd i'r dechrau i chwilio am dudalen meta ddilys ac yn dod o hyd i gronfeydd data presennol drwyddi.

Nawr, gyda syniad o strwythur rhesymegol a chorfforol trefniadaeth data, gallwn symud ymlaen i ystyried trydydd morfil LMDB. Gyda'i help ef y mae'r holl addasiadau storio yn digwydd yn drafodion ac ar wahân i'w gilydd, gan roi'r eiddo aml-fersiwn i'r gronfa ddata gyfan hefyd.

3.3. Morfil #3. copi-ar-ysgrifennu

Mae rhai gweithrediadau coed B yn cynnwys gwneud cyfres gyfan o newidiadau i'w nodau. Un enghraifft yw ychwanegu allwedd newydd at nod sydd eisoes wedi cyrraedd ei gapasiti mwyaf. Yn yr achos hwn, mae angen, yn gyntaf, rhannu'r nod yn ddau, ac yn ail, ychwanegu dolen i'r nod plentyn wedi'i nyddu newydd yn ei riant. Gall y weithdrefn hon fod yn beryglus iawn. Os mai dim ond rhan o'r newidiadau o'r gyfres sy'n digwydd am ryw reswm (cwymp, toriad pŵer, ac ati), yna bydd y goeden yn parhau i fod mewn cyflwr anghyson.

Un ateb traddodiadol i wneud cronfa ddata yn oddefgar o fai yw ychwanegu strwythur data ychwanegol ar ddisg, y log trafodion, a elwir hefyd yn log ysgrifennu ymlaen llaw (WAL), wrth ymyl y goeden B. Mae'n ffeil, ac ar ei diwedd, yn union cyn addasu'r goeden B ei hun, mae'r gweithrediad arfaethedig yn cael ei ysgrifennu. Felly, os canfyddir llygredd data yn ystod hunan-ddiagnosis, mae'r gronfa ddata yn ymgynghori â'r log i lanhau ei hun.

Mae LMDB wedi dewis dull gwahanol fel ei fecanwaith goddefgarwch bai, a elwir yn gopi-ar-ysgrifennu. Ei hanfod yw, yn lle diweddaru'r data ar dudalen sy'n bodoli eisoes, ei fod yn ei gopïo'n gyfan gwbl gyntaf ac yn gwneud yr holl addasiadau sydd eisoes yn y copi.

Ymhellach, er mwyn i'r data wedi'i ddiweddaru fod ar gael, mae angen newid y ddolen i'r nod sydd wedi dod yn gyfredol yn y nod rhiant mewn perthynas ag ef. Gan fod angen ei addasu ar gyfer hyn hefyd, mae hefyd yn cael ei gopïo ymlaen llaw. Mae'r broses yn parhau recursively yr holl ffordd at y gwraidd. Y data ar y dudalen meta yw'r olaf i newid

Os bydd y broses yn chwalu'n sydyn yn ystod y weithdrefn ddiweddaru, yna ni fydd tudalen meta newydd yn cael ei chreu, neu ni fydd yn cael ei hysgrifennu ar ddisg tan y diwedd, a bydd ei gwiriad yn anghywir. Yn y naill achos neu'r llall, ni fydd modd cyrraedd y tudalennau newydd ac ni fydd yr hen rai yn cael eu heffeithio. Mae hyn yn dileu'r angen i LMDB ysgrifennu log ymlaen llaw i gynnal cysondeb data. De facto, mae strwythur storio data ar y ddisg, a ddisgrifir uchod, yn cymryd ei swyddogaeth ar yr un pryd. Mae absenoldeb log trafodion penodol yn un o nodweddion LMDB, sy'n darparu cyflymder darllen data uchel

Mae'r lluniad canlyniadol, a elwir yn atodiad-yn-unig B-tree, yn naturiol yn darparu ynysu trafodion ac amlfersiwn. Yn LMDB, mae gan bob trafodiad agored wreiddyn coeden gyfoes sy'n gysylltiedig ag ef. Cyn belled nad yw'r trafodiad wedi'i gwblhau, ni fydd tudalennau'r goeden sy'n gysylltiedig ag ef byth yn cael eu newid na'u hailddefnyddio ar gyfer fersiynau newydd o ddata. Felly, gallwch weithio cyhyd ag y dymunwch yn union gyda'r set ddata a oedd yn berthnasol yn y amser agorwyd y trafodiad, hyd yn oed os yw'r storfa yn parhau i gael ei diweddaru'n weithredol ar hyn o bryd. Dyma hanfod amlfersiwn, gan wneud LMDB yn ffynhonnell ddata ddelfrydol ar gyfer ein hanwyliaid UICollectionView. Ar ôl agor trafodiad, nid oes angen i chi gynyddu ôl troed cof y cais, gan bwmpio'r data cyfredol ar frys i mewn i ryw strwythur cof, gan ofni cael eich gadael heb ddim. Mae'r nodwedd hon yn gwahaniaethu LMDB o'r un SQLite, na all ymffrostio o'r fath ynysu llwyr. Ar ôl agor dau drafodiad yn yr olaf a dileu cofnod penodol o fewn un ohonynt, ni ellir cael yr un cofnod mwyach o fewn yr ail un sy'n weddill.

Ochr fflip y darn arian yw'r defnydd sylweddol uwch o gof rhithwir o bosibl. Mae'r sleid yn dangos sut olwg fydd ar strwythur y gronfa ddata os caiff ei addasu ar yr un pryd gyda 3 thrafodyn darllen agored yn edrych ar fersiynau gwahanol o'r gronfa ddata. Gan na all LMDB ailddefnyddio nodau y gellir eu cyrraedd o'r gwreiddiau sy'n gysylltiedig â'r trafodion gwirioneddol, nid oes gan y storfa ddewis ond dyrannu pedwerydd gwreiddyn arall yn y cof ac unwaith eto clonio'r tudalennau wedi'u haddasu oddi tano.

Yma ni fydd yn ddiangen dwyn i gof yr adran ar ffeiliau cof-map. Mae'n ymddangos na ddylai'r defnydd ychwanegol o gof rhithwir ein poeni rhyw lawer, gan nad yw'n cyfrannu at ôl troed cof y rhaglen. Fodd bynnag, ar yr un pryd, nodwyd bod iOS yn stingy iawn wrth ei ddyrannu, ac ni allwn ddarparu rhanbarth LMDB 1 terabyte ar weinydd neu bwrdd gwaith o ysgwydd y meistr a pheidio â meddwl am y nodwedd hon o gwbl. Lle bo modd, dylech geisio cadw oes y trafodion mor fyr â phosibl.

4. Dylunio sgema data ar ben yr API gwerth bysell

Gadewch i ni ddechrau dosrannu'r API trwy edrych ar y tyniadau sylfaenol a ddarperir gan LMDB: amgylchedd a chronfeydd data, allweddi a gwerthoedd, trafodion a chyrchyddion.

Nodyn am restrau cod

Mae pob swyddogaeth yn API cyhoeddus LMDB yn dychwelyd canlyniad eu gwaith ar ffurf cod gwall, ond ym mhob rhestriad dilynol mae ei wiriad yn cael ei hepgor er mwyn bod yn gryno. Yn ymarferol, fe wnaethom ddefnyddio ein cod ein hunain i ryngweithio â'r gadwrfa. fforch C++ deunydd lapio lmdbxx, lle mae gwallau'n dod i'r amlwg fel eithriadau C++.

Fel y ffordd gyflymaf i gysylltu LMDB â phrosiect iOS neu macOS, rwy'n cynnig fy CocoaPod POSLMDB.

4.1. Tyniadau sylfaenol

Amgylchedd

Strwythur MDB_env yw'r ystorfa o gyflwr mewnol y LMDB. Teulu o swyddogaethau rhagosodedig mdb_env yn eich galluogi i ffurfweddu rhai o'i briodweddau. Yn yr achos symlaf, mae cychwyniad yr injan yn edrych fel hyn.

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

Yn y cais Cloud Mail.ru, fe wnaethom newid y gwerthoedd rhagosodedig ar gyfer dau baramedr yn unig.

Yr un cyntaf yw maint y gofod cyfeiriad rhithwir y mae'r ffeil storio wedi'i fapio iddo. Yn anffodus, hyd yn oed ar yr un ddyfais, gall y gwerth penodol amrywio'n sylweddol o redeg i redeg. Er mwyn cymryd y nodwedd hon o iOS i ystyriaeth, rydym yn dewis yr uchafswm storio yn ddeinamig. Gan ddechrau o werth penodol, mae'n haneru'n olynol tan y swyddogaeth mdb_env_open ni fydd yn dychwelyd canlyniad heblaw ENOMEM. Mewn theori, mae yna ffordd gyferbyn - yn gyntaf rhowch leiafswm o gof i'r injan, ac yna, pan dderbynnir gwallau MDB_MAP_FULL, ei gynyddu. Fodd bynnag, mae'n llawer mwy arswydus. Y rheswm yw bod y weithdrefn ar gyfer ail-fapio cof gan ddefnyddio'r swyddogaeth mdb_env_set_map_size yn annilysu pob endid (cyrchyddion, trafodion, allweddi a gwerthoedd) a dderbyniwyd gan yr injan yn gynharach. Bydd rhoi cyfrif am y fath dro o ddigwyddiadau yn y cod yn arwain at ei gymhlethdod sylweddol. Serch hynny, os yw cof rhithwir yn annwyl iawn i chi, yna gall hyn fod yn rheswm i edrych ar y fforc sydd wedi mynd ymhell ymlaen. MDBX, lle ymhlith y nodweddion datganedig mae “addasiad maint cronfa ddata awtomatig ar-y-hedfan”.

Mae'r ail baramedr, nad oedd ei werth diofyn yn addas i ni, yn rheoleiddio'r mecaneg o sicrhau diogelwch edau. Yn anffodus, o leiaf yn iOS 10, mae problemau gyda chymorth storio lleol edau. Am y rheswm hwn, yn yr enghraifft uchod, agorir y storfa gyda'r faner MDB_NOTLS. Yn ogystal, mae hefyd yn ofynnol fforch C++ deunydd lapio lmdbxxi dorri newidynnau gyda ac yn y nodwedd hon.

Cronfeydd data

Mae'r gronfa ddata yn enghraifft ar wahân o'r goeden B y buom yn sôn amdani uchod. Mae ei agoriad yn digwydd y tu mewn i drafodiad, a all ar y dechrau ymddangos ychydig yn rhyfedd.

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

Yn wir, mae trafodiad yn LMDB yn endid storio, nid cronfa ddata benodol. Mae'r cysyniad hwn yn caniatáu ichi berfformio gweithrediadau atomig ar endidau sydd wedi'u lleoli mewn gwahanol gronfeydd data. Mewn theori, mae hyn yn agor y posibilrwydd o fodelu tablau ar ffurf gwahanol gronfeydd data, ond ar un adeg es i'r ffordd arall, a ddisgrifir yn fanwl isod.

Allweddi a gwerthoedd

Strwythur MDB_val modelu'r cysyniad o allwedd a gwerth. Nid oes gan yr ystorfa unrhyw syniad am eu semanteg. Iddi hi, rhywbeth sy'n wahanol yn unig yw amrywiaeth o beit o faint penodol. Y maint allwedd mwyaf yw 512 beit.

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

Mae'r storfa'n defnyddio cymharydd i ddidoli'r bysellau mewn trefn esgynnol. Os na fyddwch chi'n rhoi eich un chi yn ei le, yna bydd yr un rhagosodedig yn cael ei ddefnyddio, sy'n eu didoli beit-wrth-beit yn nhrefn geiriadurol.

Trafodiad

Disgrifir y ddyfais trafodiad yn fanwl yn bennod flaenorol, felly dyma ailadrodd eu prif briodweddau mewn llinell fer:

1. Cefnogaeth i bob eiddo sylfaenol ACIDGeiriau allweddol: atomigrwydd, cysondeb, ynysu a dibynadwyedd. Ni allaf helpu ond nodi bod nam wedi'i osod yn MDBX o ran gwydnwch ar macOS ac iOS. Gallwch ddarllen mwy yn eu README.
2. Disgrifir yr ymagwedd at aml-edau gan y cynllun "ysgrifennwr sengl / darllenwyr lluosog". Mae ysgrifenwyr yn rhwystro ei gilydd, ond nid ydynt yn rhwystro darllenwyr. Nid yw darllenwyr yn rhwystro ysgrifenwyr na'i gilydd.
3. Cefnogaeth ar gyfer trafodion nythu.
4. Cymorth amldroad.

Mae amlfersiwn yn LMDB mor dda fel fy mod am ei ddangos ar waith. Mae'r cod isod yn dangos bod pob trafodiad yn gweithio gyda'r union fersiwn o'r gronfa ddata a oedd yn berthnasol ar adeg ei hagor, gan ei bod wedi'i hynysu'n llwyr o'r holl newidiadau dilynol. Nid yw cychwyn yr ystorfa ac ychwanegu cofnod prawf ati o unrhyw ddiddordeb, felly mae'r defodau hyn yn cael eu gadael o dan y sbwyliwr.

Ychwanegu cofnod prawf

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

Yn ddewisol, rwy'n argymell rhoi cynnig ar yr un tric gyda SQLite a gweld beth sy'n digwydd.

Mae amlgyfeirio yn dod â buddion neis iawn i fywyd datblygwr iOS. Gan ddefnyddio'r eiddo hwn, gallwch yn hawdd ac yn naturiol addasu'r gyfradd diweddaru ffynhonnell data ar gyfer ffurflenni sgrin yn seiliedig ar ystyriaethau profiad y defnyddiwr. Er enghraifft, gadewch i ni gymryd nodwedd o'r fath o gais Mail.ru Cloud fel llwytho cynnwys yn awtomatig o oriel cyfryngau'r system. Gyda chysylltiad da, mae'r cleient yn gallu ychwanegu sawl llun yr eiliad i'r gweinydd. Os byddwch yn diweddaru ar ôl pob llwytho i lawr UICollectionView gyda chynnwys cyfryngau yng nghwmwl y defnyddiwr, gallwch chi anghofio am 60 fps a sgrolio llyfn yn ystod y broses hon. Er mwyn atal diweddariadau sgrin aml, mae angen i chi rywsut gyfyngu ar y gyfradd newid data yn y sail UICollectionViewDataSource.

Os nad yw'r gronfa ddata yn cefnogi amlfersiwn ac yn caniatáu i chi weithio gyda'r cyflwr presennol presennol yn unig, yna i greu ciplun data sefydlog amser, mae angen i chi ei gopïo naill ai i strwythur data mewn cof neu i dabl dros dro. Mae'r naill neu'r llall o'r dulliau hyn yn ddrud iawn. Yn achos storio mewn cof, rydym yn cael y costau cof a achosir gan storio gwrthrychau adeiledig a'r costau amser sy'n gysylltiedig â thrawsnewidiadau ORM diangen. O ran y bwrdd dros dro, mae hwn yn bleser hyd yn oed yn ddrutach, sy'n gwneud synnwyr dim ond mewn achosion nad ydynt yn ddibwys.

Mae amlgyfeirio LMDB yn datrys y broblem o gynnal ffynhonnell ddata sefydlog mewn ffordd gain iawn. Mae'n ddigon i agor trafodiad a voila yn unig - nes i ni ei gwblhau, mae'r set ddata yn sicr o fod yn sefydlog. Mae rhesymeg ei gyfradd ddiweddaru bellach yn gyfan gwbl yn nwylo'r haen gyflwyno, heb unrhyw orbenion o adnoddau sylweddol.

Cyrchwyr

Mae cyrchyddion yn darparu mecanwaith ar gyfer iteriad trefnus dros barau gwerth allweddol trwy groesi coeden B. Hebddynt, byddai'n amhosibl modelu'r tablau yn y gronfa ddata yn effeithiol, y byddwn yn troi ati nawr.

4.2. Modelu Tabl

Mae'r briodwedd archebu allwedd yn caniatáu i chi adeiladu tyniad lefel uchaf fel tabl ar ben tyniadau sylfaenol. Gadewch i ni ystyried y broses hon ar yr enghraifft o brif dabl y cleient cwmwl, lle mae gwybodaeth am holl ffeiliau a ffolderi'r defnyddiwr yn cael ei storio.

Sgema Tabl

Un o'r senarios cyffredin y dylid hogi strwythur tabl gyda choeden ffolder ar ei gyfer yw dewis yr holl elfennau sydd wedi'u lleoli y tu mewn i gyfeiriadur penodol Model trefnu data da ar gyfer ymholiadau effeithlon o'r math hwn yw Rhestr Addasrwydd. Er mwyn ei weithredu ar ben y storfa gwerth allweddol, mae angen didoli allweddi ffeiliau a ffolderi yn y fath fodd fel eu bod yn cael eu grwpio yn seiliedig ar berthyn i'r cyfeiriadur rhiant. Yn ogystal, er mwyn arddangos cynnwys y cyfeiriadur yn y ffurf sy'n gyfarwydd i ddefnyddiwr Windows (ffolderi yn gyntaf, yna ffeiliau, mae'r ddau yn cael eu didoli yn nhrefn yr wyddor), mae angen cynnwys y meysydd ychwanegol cyfatebol yn yr allwedd.

Mae'r llun isod yn dangos sut, yn seiliedig ar y dasg, y gall cynrychioliad allweddi fel amrywiaeth o beit edrych. Yn gyntaf, gosodir y bytes gyda'r rhifwr cyfeiriadur rhiant (coch), yna gyda'r math (gwyrdd), ac eisoes yn y gynffon gyda'r enw (glas). Wedi'u didoli yn ôl y cymharydd LMDB rhagosodedig mewn trefn geiriadurol, fe'u trefnir yn y ffordd ofynnol. Mae croesi bysellau dilyniannol gyda'r un rhagddodiad coch yn rhoi'r gwerthoedd sy'n gysylltiedig â nhw yn y drefn y dylid eu harddangos yn y rhyngwyneb defnyddiwr (ar y dde), heb fod angen unrhyw ôl-brosesu ychwanegol.

Cyfresoli Allweddi a Gwerthoedd

Mae yna lawer o ddulliau ar gyfer cyfresoli gwrthrychau ledled y byd. Gan nad oedd gennym unrhyw ofyniad arall heblaw cyflymder, fe wnaethom ddewis yr un cyflymaf posibl i ni ein hunain - tomen cof a feddiannwyd gan enghraifft o strwythur iaith C. Felly, gellir modelu allwedd elfen cyfeiriadur gan y strwythur canlynol NodeKey.

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

I achub NodeKey mewn angen storio mewn gwrthrych MDB_val gosodwch y pwyntydd i'r data ar gyfeiriad dechrau'r strwythur, a chyfrifwch eu maint gyda'r swyddogaeth sizeof.

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

Yn y bennod gyntaf ar feini prawf dewis cronfa ddata, soniais am leihau dyraniadau deinamig fel rhan o weithrediadau CRUD fel ffactor dethol pwysig. Cod swyddogaeth serialize yn dangos sut, yn achos LMDB, y gellir eu hosgoi yn llwyr pan fydd cofnodion newydd yn cael eu rhoi yn y gronfa ddata. Mae'r casgliad o beitau sy'n dod i mewn o'r gweinydd yn cael ei drawsnewid yn strwythurau stac yn gyntaf, ac yna'n cael eu dympio'n ddibwys i'r storfa. O ystyried nad oes unrhyw ddyraniadau deinamig hefyd y tu mewn i LMDB, gallwch gael sefyllfa wych yn ôl safonau iOS - defnyddiwch gof pentwr yn unig i weithio gyda data yr holl ffordd o'r rhwydwaith i'r ddisg!

Archebu allweddi gyda chymharydd deuaidd

Rhoddir y berthynas trefn allweddol gan swyddogaeth arbennig o'r enw cymharydd. Gan nad yw'r injan yn gwybod dim am semanteg y beit sydd ynddynt, nid oes gan y cymharydd rhagosodedig unrhyw ddewis ond gosod yr allweddi mewn trefn geiriadurol, gan droi at eu cymhariaeth beit-wrth-beit. Mae ei ddefnyddio i drefnu strwythurau yn debyg i eillio â bwyell gerfio. Fodd bynnag, mewn achosion syml, rwy'n gweld y dull hwn yn dderbyniol. Disgrifir y dewis arall isod, ond yma nodaf un neu ddau o raciau wedi'u gwasgaru ar hyd y ffordd.

Y peth cyntaf i'w gadw mewn cof yw cynrychiolaeth cof mathau o ddata cyntefig. Felly, ar bob dyfais Apple, mae newidynnau cyfanrif yn cael eu storio yn y fformat Endian Bach. Mae hyn yn golygu y bydd y beit lleiaf arwyddocaol ar y chwith, ac ni fyddwch yn gallu didoli cyfanrifau gan ddefnyddio eu cymhariaeth beit-wrth-beit. Er enghraifft, bydd ceisio gwneud hyn gyda set o rifau o 0 i 511 yn arwain at y canlyniad canlynol.

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

I ddatrys y broblem hon, rhaid storio'r cyfanrifau yn yr allwedd mewn fformat sy'n addas ar gyfer y cymharydd beit. Bydd swyddogaethau'r teulu yn helpu i gyflawni'r trawsnewid angenrheidiol. hton* (yn benodol htons ar gyfer rhifau beit dwbl o'r enghraifft).

Y fformat ar gyfer cynrychioli tannau mewn rhaglennu yw, fel y gwyddoch, yn ei gyfanrwydd Hanes. Os yw semanteg llinynnau, yn ogystal â'r amgodio a ddefnyddir i'w cynrychioli yn y cof, yn awgrymu y gallai fod mwy nag un beit fesul cymeriad, yna mae'n well rhoi'r gorau i'r syniad o ddefnyddio cymharydd rhagosodedig ar unwaith.

Yr ail beth i'w gadw mewn cof yw egwyddorion aliniad struct maes casglwr. O'u herwydd, gellir ffurfio bytes â gwerthoedd sothach yn y cof rhwng caeau, sydd, wrth gwrs, yn torri didoli beit. Er mwyn dileu sbwriel, rhaid i chi naill ai ddatgan y caeau mewn trefn a ddiffinnir yn llym, gan gadw'r rheolau aliniad mewn cof, neu ddefnyddio'r nodwedd yn y datganiad strwythur packed.

Archebu allweddi gan gymharydd allanol

Efallai y bydd y rhesymeg gymhariaeth allweddol yn troi allan i fod yn rhy gymhleth ar gyfer cymharydd deuaidd. Un o'r nifer o resymau yw presenoldeb meysydd technegol y tu mewn i'r strwythurau. Byddaf yn dangos eu digwyddiad ar yr enghraifft o allwedd sydd eisoes yn gyfarwydd i ni ar gyfer elfen cyfeiriadur.

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

Er ei symlrwydd i gyd, yn y mwyafrif helaeth o achosion mae'n defnyddio gormod o gof. Mae'r byffer teitl yn 256 beit, er ar gyfartaledd anaml y bydd enwau ffeiliau a ffolderi yn fwy na 20-30 nod.

Un o'r technegau safonol ar gyfer optimeiddio maint cofnod yw ei docio i gyd-fynd â'i faint gwirioneddol. Ei hanfod yw bod cynnwys pob maes hyd newidiol yn cael ei storio mewn byffer ar ddiwedd y strwythur, ac mae eu hyd yn cael eu storio mewn newidynnau ar wahân.Yn unol â'r dull hwn, yr allwedd NodeKey yn cael ei drawsnewid yn y modd canlynol.

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

Ymhellach, yn ystod cyfresoli, heb ei nodi fel maint y data sizeof mae'r strwythur cyfan, a maint yr holl feysydd yn hyd sefydlog ynghyd â maint y rhan o'r byffer a ddefnyddir mewn gwirionedd.

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

O ganlyniad i'r ailffactorio, cawsom arbedion sylweddol yn y gofod a feddiannwyd gan yr allweddi. Fodd bynnag, oherwydd y maes technegol nameLength, nid yw'r cymharydd deuaidd rhagosodedig bellach yn addas ar gyfer cymhariaeth allweddol. Os na fyddwn yn rhoi ein rhai ein hunain yn ei le, yna bydd hyd yr enw yn ffactor mwy blaenoriaeth wrth ddidoli na'r enw ei hun.

Mae LMDB yn caniatáu i bob cronfa ddata gael ei swyddogaeth gymharu allweddol ei hun. Gwneir hyn gan ddefnyddio'r swyddogaeth mdb_set_compare yn union cyn agor. Am resymau amlwg, ni ellir newid cronfa ddata drwy gydol ei hoes. Yn y mewnbwn, mae'r cymharydd yn derbyn dwy allwedd mewn fformat deuaidd, ac yn yr allbwn mae'n dychwelyd canlyniad y gymhariaeth: llai na (-1), mwy na (1) neu hafal (0). Ffuggod ar gyfer NodeKey edrych felly.

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

Cyn belled â bod yr holl allweddi yn y gronfa ddata o'r un math, mae'n gyfreithiol i fwrw eu cynrychiolaeth beit yn ddiamod i'r math o strwythur cais yr allwedd. Mae yna un naws yma, ond bydd yn cael ei drafod ychydig yn is yn yr isadran “Reading Records”.

Cyfresi Gwerth

Gydag allweddi cofnodion wedi'u storio, mae LMDB yn gweithio'n hynod ddwys. Maent yn cael eu cymharu â'i gilydd o fewn fframwaith unrhyw weithrediad cais, ac mae perfformiad yr ateb cyfan yn dibynnu ar gyflymder y cymharydd. Mewn byd delfrydol, dylai'r cymharydd deuaidd rhagosodedig fod yn ddigon i gymharu bysellau, ond os oedd yn rhaid i chi ddefnyddio'ch allwedd eich hun mewn gwirionedd, yna dylai'r weithdrefn ar gyfer dad-gyfrifo allweddi ynddo fod mor gyflym â phosibl.

Nid oes gan y gronfa ddata ddiddordeb arbennig yn rhan Gwerth y cofnod (gwerth). Mae ei drosi o gynrychiolaeth beit i wrthrych yn digwydd dim ond pan fo'n ofynnol eisoes gan god y cais, er enghraifft, i'w arddangos ar y sgrin. Gan fod hyn yn digwydd yn gymharol anaml, nid yw'r gofynion ar gyfer cyflymder y weithdrefn hon mor hanfodol, ac wrth ei gweithredu rydym yn llawer mwy rhydd i ganolbwyntio ar gyfleustra. Er enghraifft, i gyfresoli metadata am ffeiliau nad ydynt wedi'u llwytho i lawr eto, rydym yn defnyddio NSKeyedArchiver.

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

Fodd bynnag, mae yna adegau pan fydd perfformiad yn bwysig. Er enghraifft, wrth arbed meta-wybodaeth am strwythur ffeil y cwmwl defnyddiwr, rydym yn defnyddio'r un dymp cof gwrthrych. Uchafbwynt y dasg o gynhyrchu eu cynrychiolaeth gyfresol yw’r ffaith bod elfennau cyfeiriadur yn cael eu modelu gan hierarchaeth dosbarth.

Ar gyfer ei weithredu yn yr iaith C, mae meysydd penodol yr etifeddion yn cael eu cymryd allan i strwythurau ar wahân, a nodir eu cysylltiad â'r un sylfaen trwy faes o'r math undeb. Pennir cynnwys gwirioneddol yr undeb trwy'r math o briodoledd technegol.

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

Ychwanegu a diweddaru cofnodion

Gellir ychwanegu'r allwedd a'r gwerth cyfresol i'r siop. Ar gyfer hyn, defnyddir y swyddogaeth mdb_put.

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

Yn y cam ffurfweddu, gellir caniatáu neu wahardd yr ystorfa i storio cofnodion lluosog gyda'r un allwedd. ​Os gwaherddir dyblygu allweddi, yna wrth fewnosod cofnod, gallwch benderfynu a ganiateir diweddaru cofnod sydd eisoes yn bodoli ai peidio. Os mai dim ond o ganlyniad i wall yn y cod y gall ffraio ddigwydd, yna gallwch yswirio yn ei erbyn trwy nodi'r faner NOOVERWRITE.

Cofnodion Darllen

Y swyddogaeth ar gyfer darllen cofnodion yn LMDB yw mdb_get. Os yw'r pâr gwerth allweddol yn cael ei gynrychioli gan strwythurau a ddympiwyd yn flaenorol, yna mae'r weithdrefn hon yn edrych fel hyn.

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

Mae'r rhestriad a gyflwynir yn dangos sut mae cyfresoli trwy domen o strwythurau yn caniatáu ichi gael gwared ar ddyraniadau deinamig nid yn unig wrth ysgrifennu, ond wrth ddarllen data. Yn deillio o swyddogaeth mdb_get mae'r pwyntydd yn edrych yn union ar y cyfeiriad cof rhithwir lle mae'r gronfa ddata yn storio cynrychiolaeth beit y gwrthrych. Yn wir, rydym yn cael math o ORM, bron yn rhad ac am ddim yn darparu cyflymder uchel iawn o ddata darllen. Gyda holl harddwch y dull, mae angen cofio sawl nodwedd sy'n gysylltiedig ag ef.

1. Ar gyfer trafodiad darllen yn unig, mae pwyntydd i strwythur gwerth yn sicr o barhau'n ddilys nes bod y trafodiad wedi'i gau. Fel y nodwyd yn gynharach, mae tudalennau'r goeden B y mae'r gwrthrych yn byw arni, diolch i'r egwyddor copi-ar-ysgrifennu, yn aros yn ddigyfnewid cyn belled â bod o leiaf un trafodiad yn cyfeirio atynt. Ar yr un pryd, cyn gynted ag y bydd y trafodiad olaf sy'n gysylltiedig â nhw wedi'i gwblhau, gellir ailddefnyddio'r tudalennau ar gyfer data newydd. Os oes angen i wrthrychau oroesi'r trafodiad a'u creodd, yna mae'n rhaid eu copïo o hyd.
2. Ar gyfer trafodiad readwrite, dim ond tan y weithdrefn addasu gyntaf (ysgrifennu neu ddileu data) y bydd y pwyntydd at y gwerth strwythur canlyniadol yn ddilys.
3. Er bod y strwythur NodeValue heb fod yn llawn, ond wedi'i docio (gweler yr is-adran "Gorchymyn allweddi gan gymharydd allanol"), trwy'r pwyntydd, gallwch chi gael mynediad hawdd i'w feysydd. Y prif beth yw peidio â dadgyfeirio ato!
4. Ni allwch mewn unrhyw achos addasu'r strwythur trwy'r pwyntydd a dderbyniwyd. Rhaid gwneud pob newid trwy'r dull yn unig mdb_put. Fodd bynnag, gyda'r holl awydd i wneud hyn, ni fydd yn gweithio, gan fod yr ardal cof lle mae'r strwythur hwn wedi'i leoli wedi'i fapio yn y modd darllen yn unig.
5. Ail-fapiwch ffeil i ofod cyfeiriad proses er mwyn, er enghraifft, cynyddu'r maint storio mwyaf gan ddefnyddio'r swyddogaeth mdb_env_set_map_size yn annilysu'n llwyr yr holl drafodion ac endidau cysylltiedig yn gyffredinol ac awgrymiadau i ddarllen gwrthrychau yn benodol.

Yn olaf, mae un nodwedd arall mor llechwraidd fel nad yw datgelu ei hanfod yn cyd-fynd ag un pwynt arall yn unig. Yn y bennod ar y goeden B, rhoddais ddiagram o drefniadaeth ei thudalennau er cof. Mae'n dilyn ohono y gall cyfeiriad dechrau'r byffer gyda data cyfresol fod yn gwbl fympwyol. Oherwydd hyn, y pwyntydd iddynt, a gafwyd yn y strwythur MDB_val a bwrw i pwyntydd i strwythur yn gyffredinol heb ei alinio. Ar yr un pryd, mae saernïaeth rhai sglodion (yn achos iOS, armv7 yw hwn) yn ei gwneud yn ofynnol i gyfeiriad unrhyw ddata fod yn lluosrif maint gair peiriant, neu, mewn geiriau eraill, bitness y system (ar gyfer armv7, mae hyn yn 32 did). Mewn geiriau eraill, llawdriniaeth fel *(int *foo)0x800002 arnynt yn gyfystyr i ddianc ac yn arwain i ddienyddio gyda rheithfarn EXC_ARM_DA_ALIGN. Mae dwy ffordd i osgoi tynged mor drist.

Yr un cyntaf yw copïo'r data i strwythur aliniad hysbys ymlaen llaw. Er enghraifft, ar gymharydd arfer, bydd hyn yn cael ei adlewyrchu fel a ganlyn.

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

Ffordd arall yw hysbysu'r casglwr ymlaen llaw ei bod yn bosibl na fydd strwythurau ag allwedd a gwerth yn cael eu halinio gan ddefnyddio priodoledd aligned(1). Gall yr un effaith fod ar ARM cyflawni a defnyddio'r priodoledd llawn. O ystyried ei fod hefyd yn cyfrannu at optimeiddio'r gofod a feddiannir gan y strwythur, mae'r dull hwn yn ymddangos yn well i mi, er приводит cynyddu cost gweithrediadau mynediad data.

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

Ystod Ymholiadau

I ailadrodd dros grŵp o gofnodion, mae LMDB yn darparu echdynnu cyrchwr. Gadewch i ni edrych ar sut i weithio gydag ef gan ddefnyddio'r enghraifft o dabl gyda metadata cwmwl defnyddwyr sydd eisoes yn gyfarwydd i ni.

Fel rhan o arddangos rhestr o ffeiliau mewn cyfeiriadur, mae angen i chi ddod o hyd i'r holl allweddi y mae ei ffeiliau plentyn a'i ffolderi yn gysylltiedig â nhw. Yn yr is-adrannau blaenorol, gwnaethom ddidoli'r allweddi NodeKey fel eu bod yn cael eu harchebu yn gyntaf gan eu ID cyfeiriadur rhiant. Felly, yn dechnegol, mae'r dasg o gael cynnwys ffolder yn cael ei leihau i osod y cyrchwr ar ffin uchaf grŵp o allweddi gyda rhagddodiad penodol, ac yna iteriad i'r ffin isaf.

Gallwch ddod o hyd i'r rhwymiad uchaf "ar y talcen" trwy chwiliad dilyniannol. I wneud hyn, mae'r cyrchwr yn cael ei osod ar ddechrau'r rhestr gyfan o allweddi yn y gronfa ddata ac yna'n cael ei gynyddu nes bod yr allwedd gyda'r dynodwr cyfeiriadur rhiant yn ymddangos oddi tano. Mae gan y dull hwn 2 anfantais amlwg:

1. Cymhlethdod llinol y chwiliad, er, fel y gwyddoch, mewn coed yn gyffredinol ac mewn coeden B yn benodol, gellir ei wneud mewn amser logarithmig.
2. Yn ofer, mae pob tudalen sy'n rhagflaenu'r un a ddymunir yn cael ei godi o'r ffeil i'r prif gof, sy'n hynod ddrud.

Yn ffodus, mae'r API LMDB yn darparu ffordd effeithlon o leoli'r cyrchwr i ddechrau.I wneud hyn, mae angen i chi ffurfio allwedd y gwyddys bod ei werth yn llai na neu'n hafal i'r allwedd sydd wedi'i leoli ar ffin uchaf yr egwyl. Er enghraifft, mewn perthynas â'r rhestr yn y ffigur uchod, gallwn wneud allwedd y mae'r maes parentId Bydd yn hafal i 2, ac mae'r gweddill i gyd yn cael eu llenwi â sero. Mae allwedd o'r fath wedi'i llenwi'n rhannol yn cael ei fwydo i fewnbwn y swyddogaeth mdb_cursor_get yn nodi gweithrediad 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);

Os canfyddir ffin uchaf y grŵp o allweddi, yna ailadroddwn drosto nes i ni gwrdd neu'r allwedd ag un arall parentId, neu ni fydd yr allweddi yn rhedeg allan o gwbl

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

Yr hyn sy'n braf, fel rhan o iteriad gan ddefnyddio mdb_cursor_get, rydym yn cael nid yn unig yr allwedd, ond hefyd y gwerth. Os, er mwyn cyflawni'r amodau dethol, mae angen gwirio, ymhlith pethau eraill, y meysydd o ran gwerth y cofnod, yna maent yn eithaf hygyrch iddynt eu hunain heb ystumiau ychwanegol.

4.3. Modelu perthnasoedd rhwng tablau

Hyd yma, rydym wedi llwyddo i ystyried pob agwedd ar ddylunio a gweithio gyda chronfa ddata un bwrdd. Gallwn ddweud bod tabl yn set o gofnodion wedi'u didoli sy'n cynnwys parau gwerth allweddol o'r un math. Os ydych yn arddangos allwedd fel petryal a'i werth cysylltiedig fel blwch, byddwch yn cael diagram gweledol o'r gronfa ddata.

​

Fodd bynnag, mewn bywyd go iawn, anaml y mae'n bosibl ymdopi â chyn lleied o waed. Yn aml mewn cronfa ddata mae'n ofynnol, yn gyntaf, i gael sawl tabl, ac yn ail, i wneud detholiadau ynddynt mewn trefn wahanol i'r cywair cynradd. Mae'r adran olaf hon wedi'i neilltuo i faterion eu creu a'u cydgysylltiad.

Tablau mynegai

Mae gan yr app cwmwl adran "Oriel". Mae'n dangos cynnwys cyfryngau o'r cwmwl cyfan, wedi'i drefnu yn ôl dyddiad. Er mwyn gweithredu detholiad o'r fath yn y ffordd orau bosibl, wrth ymyl y prif dabl, mae angen i chi greu un arall gyda math newydd o allweddi. Byddant yn cynnwys maes gyda'r dyddiad y crëwyd y ffeil, a fydd yn gweithredu fel y prif faen prawf didoli. Oherwydd bod yr allweddi newydd yn cyfeirio at yr un data â'r allweddi yn y tabl gwaelodol, fe'u gelwir yn allweddi mynegai. Maent wedi'u hamlygu mewn oren yn y llun isod.

Er mwyn gwahanu allweddi gwahanol dablau oddi wrth ei gilydd o fewn yr un gronfa ddata, mae tableId maes technegol ychwanegol wedi'i ychwanegu at bob un ohonynt. Trwy ei wneud yn flaenoriaeth uchaf ar gyfer didoli, byddwn yn grwpio'r allweddi yn gyntaf fesul tablau, ac eisoes y tu mewn i'r byrddau - yn unol â'n rheolau ein hunain.

Mae'r allwedd mynegai yn cyfeirio at yr un data â'r allwedd gynradd. Mae gweithrediad syml yr eiddo hwn trwy gysylltu ag ef gopi o ran gwerth yr allwedd gynradd yn is-optimaidd o sawl safbwynt ar unwaith:

1. O safbwynt gofod, gall y metadata fod yn eithaf cyfoethog.
2. O safbwynt perfformiad, oherwydd wrth ddiweddaru'r metadata nod, bydd yn rhaid i chi drosysgrifo dwy allwedd.
3. O safbwynt cefnogaeth cod, wedi'r cyfan, os byddwn yn anghofio diweddaru'r data ar gyfer un o'r allweddi, byddwn yn cael byg cynnil o anghysondeb data yn y storfa.

Nesaf, byddwn yn ystyried sut i gael gwared ar y diffygion hyn.

Trefniadaeth perthnasoedd rhwng byrddau

Mae'r patrwm yn addas iawn ar gyfer cysylltu tabl mynegai â'r prif un "allwedd fel gwerth". Fel y mae ei enw'n awgrymu, mae rhan gwerth y cofnod mynegai yn gopi o'r prif werth allweddol. Mae'r dull hwn yn dileu'r holl anfanteision a restrir uchod sy'n gysylltiedig â storio copi o ran gwerth y cofnod cynradd. Yr unig ffi yw bod angen i chi wneud 2 ymholiad i'r gronfa ddata yn lle un er mwyn cael y gwerth wrth y fysell fynegai. Yn sgematig, mae sgema'r gronfa ddata sy'n deillio o hynny fel a ganlyn.

Patrwm arall ar gyfer trefnu perthnasoedd rhwng byrddau yw "allwedd segur". Ei hanfod yw ychwanegu priodoleddau ychwanegol i'r allwedd, sydd eu hangen nid ar gyfer didoli, ond ar gyfer ail-greu'r allwedd cysylltiedig.Mae yna enghreifftiau go iawn o'i ddefnydd yn y cais Cloud Mail.ru, fodd bynnag, er mwyn osgoi plymio'n ddwfn i mewn i'r cyd-destun fframweithiau iOS penodol, rhoddaf enghraifft ffug, ond mwy dealladwy.

Mae gan gleientiaid symudol cwmwl dudalen sy'n dangos yr holl ffeiliau a ffolderau y mae'r defnyddiwr wedi'u rhannu â phobl eraill. Gan mai cymharol ychydig o ffeiliau o'r fath sydd, a bod llawer o wybodaeth benodol am gyhoeddusrwydd yn gysylltiedig â hwy (i bwy y rhoddir mynediad, pa hawliau, ac ati), ni fydd yn rhesymegol i faich arno â gwerth-rhan o y cofnod yn y prif dabl. Fodd bynnag, os ydych chi am arddangos ffeiliau o'r fath all-lein, yna mae angen i chi ei storio yn rhywle o hyd. Ateb naturiol yw creu bwrdd ar wahân ar ei gyfer. Yn y diagram isod, mae ei allwedd wedi'i rhagddodi â "P", a gellir disodli'r deiliad lle "propname" gyda'r gwerth mwy penodol "gwybodaeth gyhoeddus".

Mae'r holl fetadata unigryw, y crëwyd y tabl newydd er ei fwyn, yn cael ei symud i ran gwerth y cofnod. Ar yr un pryd, nid wyf am ddyblygu'r data am ffeiliau a ffolderi sydd eisoes wedi'u storio yn y prif dabl. Yn lle hynny, mae data diangen yn cael ei ychwanegu at yr allwedd "P" ar ffurf y meysydd "node ID" a "timestamp". Diolch iddyn nhw, gallwch chi adeiladu allwedd mynegai, y gallwch chi gael yr allwedd gynradd trwyddo, ac yn olaf, gallwch chi gael metadata'r nod.

Casgliad

Rydym yn gwerthuso canlyniadau gweithredu LMDB yn gadarnhaol. Ar ôl hynny, gostyngodd nifer y ceisiadau rhewi gan 30%.

Mae canlyniadau'r gwaith a wnaed wedi canfod ymateb y tu allan i'r tîm iOS. Ar hyn o bryd, mae un o'r prif adrannau "Ffeiliau" yn y cymhwysiad Android hefyd wedi newid i ddefnyddio LMDB, ac mae rhannau eraill ar y ffordd. Roedd yr iaith C, lle mae'r storfa gwerth allweddol yn cael ei weithredu, yn help da i ddechrau gwneud y cais yn rhwymo o'i gwmpas yn draws-lwyfan yn yr iaith C ++. Ar gyfer cysylltiad di-dor o'r llyfrgell C ++ sy'n deillio o hynny gyda chod platfform yn Amcan-C a Kotlin, defnyddiwyd generadur cod Djinni o Dropbox, ond stori arall yw honno.

Ffynhonnell: hab.com