En la aŭtuno de 2019, long-atendita evento okazis en la Mail.ru Cloud iOS-teamo. La ĉefa datumbazo por konstanta stokado de aplika stato fariĝis tre ekzotika por la movebla mondo (LMDB). Sub la tranĉo ni proponas al vi detalan revizion pri ĝi en kvar partoj. Unue, ni parolu pri la kialoj de tia ne-triviala kaj malfacila elekto. Tiam ni daŭrigos por konsideri la tri kolonojn ĉe la koro de la LMDB-arkitekturo: memor-mapitaj dosieroj, B+-arbo, kopio-sur-skriba aliro por efektivigado de transakco kaj multiversio. Fine, por deserto - la praktika parto. En ĝi ni rigardos kiel desegni kaj efektivigi datumbazan skemon kun pluraj tabeloj, inkluzive de indeksa, aldone al la malaltnivela ŝlosilvalora API.
Enhavo
3.1.
3.2.
3.3.
4.1.
4.2.
4.3.
1. Instigo por efektivigo
Unu jaron en 2015, ni prenis la penon mezuri kiom ofte la interfaco de nia aplikaĵo malfruiĝas. Ni faris ĉi tion ial. Ni ricevis pli oftajn plendojn, ke foje la aplikaĵo ĉesas respondi al agoj de la uzanto: butonoj ne povas esti premitaj, listoj ne ruliĝas, ktp. Pri la mekaniko de mezuradoj ĉe AvitoTech, do ĉi tie mi donas nur la ordon de nombroj.
La mezurrezultoj fariĝis malvarma duŝo por ni. Montriĝis, ke estas multe pli da problemoj kaŭzitaj de frostiĝoj ol iu ajn alia. Se antaŭ ol konscii ĉi tiun fakton la ĉefa teknika indikilo de kvalito estis senkraŝo, tiam post la fokuso sur frosto libera.
Konstruinte kaj post elspezado и analizo de iliaj kialoj, la ĉefa malamiko iĝis klara - peza komerca logiko efektivigita en la ĉefa fadeno de la apliko. La natura reago al tiu ĉi malhonoro estis arda deziro ŝovi ĝin en laborfluojn. Por sisteme solvi ĉi tiun problemon, ni apelaciis al plurfadena arkitekturo bazita sur malpezaj aktoroj. Mi dediĉis ĝin al ĝia adapto por la iOS-mondo sur kolektiva Tvitero kaj . Kiel parto de la nuna rakonto, mi volas emfazi tiujn aspektojn de la decido, kiuj influis la elekton de la datumbazo.
La aktormodelo de sistema organizo supozas ke multifadenado iĝas sia dua esenco. Modelaj objektoj en ĝi ŝatas transiri fluajn limojn. Kaj ili faras tion ne foje kaj ĉi tie kaj tie, sed preskaŭ konstante kaj ĉie.
La datumbazo estas unu el la bazŝtonoj en la prezentita diagramo. Ĝia ĉefa tasko estas efektivigi la makroskemon . Se en la entreprena mondo ĝi estas uzata por organizi datuman sinkronigon inter servoj, tiam en la kazo de aktorarkitekturo - datumoj inter fadenoj. Tiel, ni bezonis datumbazon kiu ne kaŭzus eĉ minimumajn malfacilaĵojn kiam oni laboras kun ĝi en multfadena medio. Aparte tio signifas, ke objektoj akiritaj de ĝi devas esti almenaŭ faden-sekuraj, kaj ideale tute neŝanĝeblaj. Kiel vi scias, ĉi-lasta povas esti uzata samtempe el pluraj fadenoj sen recurri al iu ajn ŝlosilo, kiu havas utilan efikon al agado.
La dua signifa faktoro, kiu influis la elekton de datumbazo, estis nia nuba API. Ĝi estis inspirita de la sinkroniga aliro adoptita de git. Kiel li, ni celis , kiu aspektas pli ol taŭga por nubaj klientoj. Oni supozis, ke ili nur unufoje elpupus la plenan staton de la nubo, kaj tiam sinkronigado en la superforta plimulto de kazoj okazus per lanĉado de ŝanĝoj. Ve, ĉi tiu ŝanco ankoraŭ estas nur en la teoria zono, kaj klientoj ne lernis kiel labori kun diakiloj praktike. Estas kelkaj objektivaj kialoj por tio, kiujn, por ne prokrasti la enkondukon, ni postlasos krampojn. Nun, kio multe pli interesas estas la instruaj konkludoj de la leciono pri tio, kio okazas kiam API diras "A" kaj ĝia konsumanto ne diras "B".
Do, se vi imagas git, kiu, kiam vi plenumas tiran komandon, anstataŭ apliki flikojn al loka momentfoto, komparas sian plenan staton kun la plena servila stato, tiam vi havos sufiĉe precizan ideon pri kiel okazas sinkronigo en nubo. klientoj. Estas facile konjekti, ke por efektivigi ĝin, vi devas asigni du DOM-arbojn en memoro kun meta-informoj pri ĉiuj serviloj kaj lokaj dosieroj. Rezultas, ke se uzanto stokas 500 mil dosierojn en la nubo, tiam por sinkronigi ĝin necesas rekrei kaj detrui du arbojn kun 1 miliono da nodoj. Sed ĉiu nodo estas agregaĵo enhavanta grafeon de subobjektoj. En ĉi tiu lumo, la profilaj rezultoj estis atenditaj. Evidentiĝis, ke eĉ sen konsideri la kunfandan algoritmon, la procedo mem krei kaj poste detrui grandegan kvanton da malgrandaj objektoj kostas belan denaron.La situacio estas pligravigita de la fakto, ke la baza sinkroniga operacio estas inkluzivita en granda nombro. de uzantaj skriptoj. Kiel rezulto, ni fiksas la duan gravan kriterion en elektado de datumbazo - la kapablo efektivigi CRUD-operaciojn sen dinamika atribuo de objektoj.
Aliaj postuloj estas pli tradiciaj kaj ilia tuta listo estas jena.
- Sekureco pri fadenoj.
- Multiprocesado. Diktita de la deziro uzi la saman datumbazan petskribon por sinkronigi staton ne nur inter fadenoj, sed ankaŭ inter la ĉefa aplikaĵo kaj iOS-etendaĵoj.
- La kapablo reprezenti stokitajn entojn kiel neŝanĝeblajn objektojn.
- Neniuj dinamikaj asignoj ene de CRUD-operacioj.
- Transakcia subteno por bazaj propraĵoj : atomeco, konsistenco, izoliteco kaj fidindeco.
- Rapido en la plej popularaj kazoj.
Kun ĉi tiu aro de postuloj, SQLite estis kaj restas bona elekto. Tamen, kadre de la studo de alternativoj, mi trovis libron . Sub ŝia gvidado, komparnormo estis skribita komparante la rapidecon de laboro kun malsamaj datumbazoj en realaj nubaj scenaroj. La rezulto superis niajn plej sovaĝajn atendojn. En la plej popularaj kazoj - ricevi kursoron sur ordigita listo de ĉiuj dosieroj kaj ordigita listo de ĉiuj dosieroj por donita dosierujo - LMDB montriĝis 10 fojojn pli rapida ol SQLite. La elekto iĝis evidenta.
2. LMDB Pozicionado
LMDB estas tre malgranda biblioteko (nur 10K vicoj) kiu efektivigas la plej malsupran fundamentan tavolon de datumbazoj - stokado.
La supra diagramo montras, ke kompari LMDB kun SQLite, kiu ankaŭ efektivigas pli altajn nivelojn, ĝenerale ne estas pli ĝusta ol SQLite kun Core Data. Estus pli juste citi la samajn stokajn motorojn kiel egalajn konkurantojn - BerkeleyDB, LevelDB, Sophia, RocksDB, ktp. Estas eĉ evoluoj, kie LMDB funkcias kiel stoka motorkomponento por SQLite. La unua tia eksperimento estis en 2012 de LMDB . montriĝis tiel interesa, ke lia iniciato estis reprenita de OSS-entuziasmuloj, kaj trovis ĝian daŭrigon en la persono. . En januaro 2020, la aŭtoro de ĉi tiu projekto estis Den Shearer ĝi ĉe LinuxConfAu.
LMDB estas plejparte uzata kiel motoro por aplikaĵaj datumbazoj. La biblioteko ŝuldas sian aspekton al la programistoj , kiuj estis tre malkontenta kun BerkeleyDB kiel la bazo por sia projekto. Komencante de modesta biblioteko , Howard Chu povis krei unu el la plej popularaj alternativoj de nia tempo. Li dediĉis sian tre bonegan raporton al ĉi tiu rakonto, same kiel al la interna strukturo de LMDB. . Bona ekzemplo de konkerado de stokejo estis dividita fare de Leonid Yuryev (alinome ) de Positive Technologies en sia raporto ĉe Highload 2015 . En ĝi, li parolas pri LMDB en la kunteksto de simila tasko efektivigi ReOpenLDAP, kaj LevelDB jam estis submetata al kompara kritiko. Kiel rezulto de la efektivigo, Positive Technologies eĉ havis aktive evoluantan forkon kun tre bongustaj trajtoj, optimumigoj kaj .
LMDB estas ofte uzata kiel tia stokado. Ekzemple, retumilo Mozilla Firefox ĝin por kelkaj bezonoj, kaj, ekde la versio 9, Xcode ĝia SQLite por stoki indeksojn.
La motoro ankaŭ faris sian markon en la mondo de movebla disvolviĝo. Spuroj de ĝia uzo povas esti en la iOS-kliento por Telegram. LinkedIn iris eĉ plu kaj elektis LMDB kiel la defaŭltan stokadon por sia hejma datuma kaŝmemorkadro Rocket Data, pri kiu en sia artikolo en 2016.
LMDB sukcese batalas por loko en la suno en la niĉo lasita de BerkeleyDB post kiam ĝi venis sub la kontrolon de Oracle. La biblioteko estas amata pro sia rapideco kaj fidindeco, eĉ kompare kun siaj samuloj. Kiel vi scias, ne ekzistas senpagaj tagmanĝoj, kaj mi ŝatus emfazi la kompromison, kiun vi devos alfronti kiam vi elektas inter LMDB kaj SQLite. La supra diagramo klare montras kiel pliigita rapideco estas atingita. Unue, ni ne pagas por pliaj tavoloj de abstraktado aldone al disko-stokado. Estas klare, ke bona arkitekturo ankoraŭ ne povas malhavi ilin, kaj ili neeviteble aperos en la aplika kodo, sed ili estos multe pli subtilaj. Ili ne enhavos funkciojn kiuj ne estas postulataj de specifa aplikaĵo, ekzemple, subteno por demandoj en la SQL-lingvo. Due, fariĝas eble optimume efektivigi mapadon de aplikaĵoperacioj sur petoj al diskstokado. Se SQLite baziĝas sur la averaĝaj statistikaj bezonoj de averaĝa aplikaĵo, tiam vi, kiel programisto de aplikaĵo, bone konas la ĉefajn laborŝarĝajn scenarojn. Por pli produktiva solvo, vi devos pagi pliigitan prezon kaj por la disvolviĝo de la komenca solvo kaj por ĝia posta subteno.
3. Tri kolonoj de LMDB
Rigardinte la LMDB el birda vido, estis tempo pli profundiĝi. La venontaj tri sekcioj estos dediĉitaj al analizo de la ĉefaj kolonoj sur kiuj la stoka arkitekturo ripozas:
- Memor-mapitaj dosieroj kiel mekanismo por labori kun disko kaj sinkronigi internajn datumstrukturojn.
- B+-arbo kiel organizo de la strukturo de stokitaj datenoj.
- Kopi-sur-skribi kiel aliro por provizi ACID-transakciajn proprietojn kaj multiversion.
3.1. Baleno numero 1. Memor-mapitaj dosieroj
Memor-mapitaj dosieroj estas tiom grava arkitektura elemento, ke ili eĉ aperas en la nomo de la deponejo. Temoj de kaŝmemoro kaj sinkronigado de aliro al stokitaj informoj estas tute lasitaj al la operaciumo. LMDB ne enhavas iujn ajn kaŝmemorojn en si mem. Ĉi tio estas konscia decido de la aŭtoro, ĉar legi datumojn rekte de mapitaj dosieroj permesas vin tranĉi multajn angulojn en la motora efektivigo. Malsupre estas malproksima de kompleta listo de kelkaj el ili.
- Konservi la konsistencon de datumoj en la stokado kiam oni laboras kun ĝi de pluraj procezoj fariĝas la respondeco de la operaciumo. En la sekva sekcio, ĉi tiu mekaniko estas diskutita detale kaj kun bildoj.
- La foresto de kaŝmemoroj tute eliminas LMDB de la supra kosto asociita kun dinamikaj asignoj. Legi datumojn praktike signifas meti montrilon al la ĝusta adreso en virtuala memoro kaj nenion pli. Ĝi sonas kiel sciencfikcio, sed en la stoka fontkodo ĉiuj alvokoj al calloc koncentriĝas en la stoka agorda funkcio.
- La foresto de kaŝmemoroj ankaŭ signifas la foreston de seruroj asociitaj kun sinkronigado de ilia aliro. Legantoj, el kiuj povas ekzisti arbitra nombro da legantoj samtempe, ne renkontas eĉ unu mutekso survoje al la datumoj. Pro tio, la legadrapideco havas idealan linearan skaleblon bazitan sur la nombro da CPUoj. En LMDB, nur modifaj operacioj estas sinkronigitaj. Povas esti nur unu verkisto samtempe.
- Minimumo de kaŝmemoro kaj sinkroniga logiko forigas la ekstreme kompleksan tipon de eraroj asociitaj kun laborado en multfadena medio. Estis du interesaj datumbazaj studoj ĉe la Usenix OSDI 2014-konferenco: и . De ili vi povas kolekti informojn pri kaj la senprecedenca fidindeco de LMDB kaj la preskaŭ senmanka efektivigo de ACID-transakciaj proprietoj, kiu estas pli alta ol tiu de SQLite.
- La minimumismo de LMDB permesas al la maŝina reprezentado de ĝia kodo esti tute lokita en la L1-kaŝmemoro de la procesoro kun la sekvaj rapidecaj trajtoj.
Bedaŭrinde, en iOS, kun memor-mapitaj dosieroj, ĉio ne estas tiel sennuba kiel ni ŝatus. Por paroli pri la mankoj asociitaj kun ili pli konscie, necesas memori la ĝeneralajn principojn por efektivigi ĉi tiun mekanismon en operaciumoj.
Ĝeneralaj informoj pri memor-mapitaj dosieroj
Kun ĉiu aplikaĵo, kiu funkcias, la operaciumo asocias enton nomitan procezo. Al ĉiu procezo estas asignita apuda gamo da adresoj, en kiuj ĝi metas ĉion, kion ĝi bezonas por funkcii. Ĉe la plej malaltaj adresoj estas sekcioj kun kodo kaj malmolaj datumoj kaj rimedoj. Poste venas kreskanta bloko de dinamika adresspaco, bone konata al ni sub la nomo amaso. Ĝi enhavas la adresojn de estaĵoj kiuj aperas dum la funkciado de la programo. Supre estas la memorareo uzata de la aplika stako. Ĝi aŭ kreskas aŭ kontraktiĝas; alivorte, ĝia grandeco ankaŭ havas dinamikan naturon. Por malhelpi la stakon kaj amason puŝi kaj interferi unu kun la alia, ili situas ĉe malsamaj finoj de la adresspaco. Estas truo inter la du dinamikaj sekcioj ĉe la supro kaj malsupro. La operaciumo uzas adresojn en ĉi tiu meza sekcio por asocii diversajn entojn kun la procezo. Aparte, ĝi povas asocii certan kontinuan aron de adresoj kun dosiero sur la disko. Tia dosiero nomiĝas memor-mapita.
La adresspaco asignita al la procezo estas grandega. Teorie, la nombro da adresoj estas limigita nur per la grandeco de la montrilo, kiu estas determinita per la bitkapacito de la sistemo. Se fizika memoro estus mapita al ĝi 1-al-1, tiam la plej unua procezo englutus la tutan RAM, kaj oni ne parolus pri iu multitasking.
Tamen, el nia sperto ni scias, ke modernaj operaciumoj povas samtempe efektivigi tiom da procezoj kiom dezirate. Ĉi tio eblas pro tio, ke ili nur asignas multe da memoro al procezoj surpapere, sed fakte ili ŝarĝas en la ĉefan fizikan memoron nur tiun parton, kiu estas postulata ĉi tie kaj nun. Tial, la memoro asociita kun procezo estas nomita virtuala.
La operaciumo organizas virtualan kaj fizikan memoron en paĝojn de certa grandeco. Tuj kiam certa paĝo de virtuala memoro estas postulata, la operaciumo ŝarĝas ĝin en fizikan memoron kaj kongruas ilin en speciala tabelo. Se ne estas liberaj fendoj, tiam unu el la antaŭe ŝarĝitaj paĝoj estas kopiita al la disko, kaj tiu postulata anstataŭas. Ĉi tiu procedo, pri kiu ni revenos baldaŭ, nomiĝas interŝanĝado. La suba figuro ilustras la priskribitan procezon. Sur ĝi, paĝo A kun adreso 0 estis ŝarĝita kaj metita sur la ĉefmemorpaĝon kun adreso 4. Ĉi tiu fakto estis reflektita en la koresponda tabelo en ĉela numero 0.
La rakonto estas ĝuste la sama kun dosieroj mapitaj al memoro. Logike, ili estas supozeble kontinue kaj tute lokitaj en la virtuala adresspaco. Tamen ili eniras fizikan memoron paĝo post paĝo kaj nur laŭpeto. Modifo de tiaj paĝoj estas sinkronigita kun la dosiero sur disko. Tiamaniere, vi povas fari dosieron I/O simple laborante kun bajtoj en memoro - ĉiuj ŝanĝoj estos aŭtomate transdonitaj de la operaciuma kerno al la fontdosiero.
La suba bildo montras kiel LMDB sinkronigas sian staton kiam laboras kun la datumbazo de malsamaj procezoj. Mapante la virtualan memoron de malsamaj procezoj al la sama dosiero, ni fakte devigas la operaciumon transitive sinkronigi iujn blokojn de iliaj adresspacoj unu kun la alia, kie LMDB aspektas.
Grava nuanco estas, ke LMDB, defaŭlte, modifas la datumdosieron per la skriba sistemvoka mekanismo, kaj montras la dosieron mem en nurlegebla reĝimo. Ĉi tiu aliro havas du gravajn konsekvencojn.
La unua konsekvenco estas komuna al ĉiuj operaciumoj. Ĝia esenco estas aldoni protekton kontraŭ neintencita damaĝo al la datumbazo per malĝusta kodo. Kiel vi scias, la plenumeblaj instrukcioj de procezo estas liberaj aliri datumojn de ie ajn en ĝia adresspaco. Samtempe, kiel ni ĵus memoris, montri dosieron en lego-skriba reĝimo signifas, ke ĉiu instrukcio ankaŭ povas modifi ĝin. Se ŝi faras tion erare, provante, ekzemple, efektive anstataŭigi tabelelementon ĉe neekzistanta indekso, tiam ŝi povas hazarde ŝanĝi la dosieron mapitan al ĉi tiu adreso, kio kondukos al korupto de la datumbazo. Se la dosiero estas montrata en nurlegebla reĝimo, tiam provo ŝanĝi la respondan adresspacon kondukos al kriz-ĉesigo de la programo kun signalo. SIGSEGV, kaj la dosiero restos sendifekta.
La dua konsekvenco jam estas specifa por iOS. Nek la aŭtoro nek aliaj fontoj eksplicite mencias ĝin, sed sen ĝi LMDB ne taŭgus por funkcii per ĉi tiu movebla operaciumo. La sekva sekcio estas dediĉita al ĝia konsidero.
Specifaĵoj de memor-mapitaj dosieroj en iOS
Estis mirinda raporto ĉe WWDC en 2018 . Ĝi diras al ni, ke en iOS, ĉiuj paĝoj situantaj en fizika memoro estas unu el 3 tipoj: malpuraj, kunpremitaj kaj puraj.
Pura memoro estas kolekto de paĝoj, kiuj povas esti senpere malŝarĝitaj el fizika memoro. La datumoj kiujn ili enhavas povas esti reŝargitaj laŭbezone de ĝiaj originaj fontoj. Nurlegeblaj memor-mapitaj dosieroj apartenas al ĉi tiu kategorio. iOS ne timas malŝarĝi la paĝojn mapitajn al dosiero el memoro iam ajn, ĉar ili estas garantiitaj esti sinkronigitaj kun la dosiero sur disko.
Ĉiuj modifitaj paĝoj finiĝas en malpura memoro, negrave kie ili estis origine lokitaj. Aparte, memor-mapitaj dosieroj modifitaj skribante al la virtuala memoro asociita kun ili estos klasifikitaj tiamaniere. Malfermante LMDB kun flago MDB_WRITEMAP, post fari ŝanĝojn al ĝi, vi povas kontroli tion persone.
Tuj kiam aplikaĵo komencas okupi tro da fizika memoro, iOS submetas ĝin al malpura paĝa kunpremo. La tuta memoro okupata de malpuraj kaj kunpremitaj paĝoj konsistigas la tiel nomatan memorpiedsignon de la aplikaĵo. Post kiam ĝi atingas certan sojlan valoron, la OOM-murdintosistema demono venas post la procezo kaj perforte finas ĝin. Ĉi tio estas la propreco de iOS kompare kun labortablaj operaciumoj. Kontraste, redukti la memoran spuron per interŝanĝado de paĝoj de fizika memoro al disko ne estas provizita en iOS.La kialoj estas nur diveneblaj. Eble la procedo de intense movi paĝojn al disko kaj reen estas tro energikonsuma por porteblaj aparatoj, aŭ iOS ŝparas la rimedon de reverkado de ĉeloj sur SSD-diskoj, aŭ eble la projektistoj ne kontentiĝis pri la ĝenerala rendimento de la sistemo, kie ĉio estas. konstante interŝanĝita. Estu kiel ajn, la fakto restas fakto.
La bona novaĵo, jam menciita antaŭe, estas, ke LMDB defaŭlte ne uzas la mmap-mekanismon por ĝisdatigi dosierojn. Ĉi tio signifas, ke la montrataj datumoj estas klasifikitaj de iOS kiel pura memoro kaj ne kontribuas al la memorsigno. Vi povas kontroli ĉi tion per Xcode-ilo nomata VM Tracker. La ekrankopio sube montras la staton de la virtuala memoro de iOS de la aplikaĵo Nubo dum funkciado. Komence, 2 LMDB-instancoj estis pravigitaj en ĝi. La unua rajtis montri sian dosieron sur 1GiB de virtuala memoro, la dua - 512MiB. Malgraŭ tio, ke ambaŭ stokejoj okupas certan kvanton da loĝanta memoro, neniu el ili kontribuas malpuran grandecon.
Kaj nun estas tempo por malbonaj novaĵoj. Dank'al la interŝanĝmekanismo en 64-bitaj labortablaj operaciumoj, ĉiu procezo povas okupi tiom da virtuala adrespaco kiom permesas la libera diskospaco por sia ebla interŝanĝo. Anstataŭigi interŝanĝon per kunpremado en iOS radikale reduktas la teorian maksimumon. Nun ĉiuj vivantaj procezoj devas konveni en la ĉefan (legu RAM) memoron, kaj ĉiuj tiuj, kiuj ne taŭgas, devas esti devigitaj ĉesiĝi. Ĉi tio estas deklarita kiel en la supre menciita , kaj en . Sekve, iOS severe limigas la kvanton de memoro disponebla por asigno per mmap. Jen Vi povas rigardi la empiriajn limojn de la kvanto de memoro kiu povus esti asignita sur malsamaj aparatoj uzante ĉi tiun sisteman vokon. Sur la plej modernaj saĝtelefonaj modeloj, iOS fariĝis malavara je 2 gigabajtoj, kaj ĉe supraj versioj de la iPad - je 4. Praktike, kompreneble, vi devas koncentriĝi sur la plej malaltaj subtenataj aparato-modeloj, kie ĉio estas tre malĝoja. Eĉ pli malbone, rigardante la memoran staton de la aplikaĵo en VM Tracker, vi trovos, ke LMDB estas malproksima de la nura pretendanta esti memor-mapita. Bonajn pecojn forkonsumas sistemaj alsigniloj, rimeddosieroj, bildkadroj kaj aliaj pli malgrandaj predantoj.
Surbaze de la rezultoj de eksperimentoj en la Nubo, ni venis al la sekvaj kompromisaj valoroj por la memoro asignita de LMDB: 384 megabajtoj por 32-bitaj aparatoj kaj 768 por 64-bitaj aparatoj. Post kiam ĉi tiu volumo estas eluzita, ĉiuj modifaj operacioj komencas finiĝi kun la kodo MDB_MAP_FULL. Ni observas tiajn erarojn en nia monitorado, sed ili estas sufiĉe malgrandaj, ke en ĉi tiu etapo ili povas esti neglektitaj.
Ne-evidente kialo de troa memorkonsumo per la stokado povas esti longdaŭraj transakcioj. Por kompreni kiel ĉi tiuj du fenomenoj estas kunligitaj, ni helpos konsiderante la ceterajn du kolonojn de la LMDB.
3.2. Baleno #2. B+-arbo
Por kopii tabelojn aldone al ŝlosilvalora stokado, la sekvaj operacioj devas ĉeesti en ĝia API:
- Enmetante novan elementon.
- Serĉu elementon kun donita ŝlosilo.
- Forigante elementon.
- Ripetu inter intervaloj de ŝlosiloj en la ordo en kiu ili estas ordigitaj.
La plej simpla datumstrukturo, kiu povas facile efektivigi ĉiujn kvar operaciojn, estas binara serĉarbo. Ĉiu el ĝiaj nodoj reprezentas ŝlosilon kiu dividas la tutan subaron de infanŝlosiloj en du subarbojn. La maldekstra enhavas tiujn, kiuj estas pli malgrandaj ol la gepatro, kaj la dekstra enhavas tiujn, kiuj estas pli grandaj. Akiro de ordigita aro de ŝlosiloj estas atingita per unu el la klasikaj arbotrapasoj.
Binaraj arboj havas du fundamentajn difektojn, kiuj malhelpas ilin esti efikaj kiel disko-bazita datumstrukturo. Unue, la grado de ilia ekvilibro estas neantaŭvidebla. Estas konsiderinda risko akiri arbojn en kiuj la altecoj de malsamaj branĉoj povas multe varii, kio signife plimalbonigas la algoritman kompleksecon de la serĉo kompare kun tio, kion oni atendas. Due, la abundo de krucligoj inter nodoj senigas binarajn arbojn de loko en memoro.Proksimaj nodoj (laŭ ligoj inter ili) povas troviĝi sur tute malsamaj paĝoj en virtuala memoro. Sekve, eĉ simpla trairo de pluraj najbaraj nodoj en arbo povas postuli viziti komparebla nombro da paĝoj. Ĉi tio estas problemo eĉ kiam ni parolas pri la efikeco de binaraj arboj kiel en-memora datumstrukturo, ĉar konstante turni paĝojn en la procesora kaŝmemoro ne estas malmultekosta plezuro. Kiam temas pri ofte retrovi paĝojn asociitajn kun nodoj de disko, la situacio fariĝas tute .
B-arboj, estante evoluo de binaraj arboj, solvas la problemojn identigitajn en la antaŭa paragrafo. Unue, ili estas mem-ekvilibraj. Due, ĉiu el iliaj nodoj dividas la aron de infanŝlosiloj ne en 2, sed en M ordigitajn subarojn, kaj la nombro M povas esti sufiĉe granda, sur la ordo de kelkaj centoj, aŭ eĉ miloj.
Per tio:
- Ĉiu nodo enhavas grandan nombron da jam ordigitaj ŝlosiloj kaj la arboj estas tre mallongaj.
- La arbo akiras la posedaĵon de loko de loko en memoro, ĉar ŝlosiloj kiuj estas proksimaj en valoro estas nature situantaj unu apud la alia sur la sama aŭ najbaraj nodoj.
- La nombro da transitnodoj dum malsupreniro de arbo dum serĉoperacio estas reduktita.
- La nombro da celnodoj legitaj dum intervaldemandoj estas reduktita, ĉar ĉiu el ili jam enhavas grandan nombron da ordigitaj ŝlosiloj.
LMDB uzas varion de la B-arbo nomita B+-arbo por stoki datenojn. La supra diagramo montras la tri specojn de nodoj kiuj ekzistas en ĝi:
- Supre estas la radiko. Ĝi materiigas nenion pli ol la koncepto de datumbazo ene de magazeno. Ene de unu LMDB-instanco, vi povas krei plurajn datumbazojn, kiuj kunhavas mapitan virtualan adresspacon. Ĉiu el ili komenciĝas de sia propra radiko.
- Ĉe la plej malalta nivelo estas la folioj. Ili kaj nur ili enhavas la ŝlosil-valorajn parojn konservitajn en la datumbazo. Cetere, ĉi tio estas la propreco de B+-arboj. Se regula B-arbo stokas valorpartojn en nodoj de ĉiuj niveloj, tiam la B+-vario estas nur ĉe la plej malsupra. Riparinte ĉi tiun fakton, ni plu nomos la subtipo de la arbo uzata en LMDB simple B-arbo.
- Inter la radiko kaj folioj estas 0 aŭ pli da teknikaj niveloj kun navigaciaj (branĉaj) nodoj. Ilia tasko estas dividi la ordigitan aron de ŝlosiloj inter la folioj.
Fizike, nodoj estas blokoj de memoro de antaŭfiksita longo. Ilia grandeco estas oblo de la grandeco de memorpaĝoj en la operaciumo, kiun ni diskutis supre. La noda strukturo estas montrita malsupre. La kaplinio enhavas metainformojn, la plej evidenta el kiuj ekzemple estas la ĉeksumo. Poste venas informoj pri la ofsetoj, en kiuj troviĝas la ĉeloj kun datumoj. La datumoj povas esti aŭ ŝlosiloj, se ni parolas pri navigaj nodoj, aŭ tutaj ŝlosil-valoraj paroj en la kazo de folioj. Vi povas legi pli pri la strukturo de paĝoj en la verko. .
Pritraktinte la internan enhavon de paĝaj nodoj, ni plue reprezentos la LMDB-B-arbon en simpligita maniero en la sekva formo.
Paĝoj kun nodoj troviĝas sinsekve sur disko. Pli altaj paĝnumeroj troviĝas al la fino de la dosiero. La tiel nomata meta paĝo enhavas informojn pri la ofsetoj, per kiuj la radikoj de ĉiuj arboj troviĝas. Malfermante dosieron, LMDB skanas la dosieron paĝon de fino ĝis komenco serĉante validan metapaĝon kaj tra ĝi trovas ekzistantajn datumbazojn.
Nun, havante ideon pri la logika kaj fizika strukturo de datuma organizo, ni povas daŭrigi por konsideri la trian kolonon de LMDB. Estas kun ĝia helpo ke ĉiuj konservaj modifoj okazas transakcie kaj izole unu de la alia, donante al la datumbazo entute la posedaĵon de multiversio.
3.3. Baleno numero 3. Kopi-sur-skribi
Kelkaj B-arbaj operacioj implikas fari serion de ŝanĝoj al ĝiaj nodoj. Unu ekzemplo estas aldoni novan ŝlosilon al nodo, kiu jam atingis sian maksimuman kapablon. En ĉi tiu kazo, estas necese, unue, dividi la nodon en du, kaj due, aldoni ligon al la nova burĝona infana nodo en ĝia gepatro. Ĉi tiu proceduro estas eble tre danĝera. Se ial (kraŝo, elektropaneo, ktp.) nur parto de la ŝanĝoj de la serio okazas, tiam la arbo restos en malkonsekvenca stato.
Unu tradicia solvo por fari datumbazon erartolerema estas aldoni aldonan surdiskan datumstrukturon apud la B-arbo - transakcia protokolo, ankaŭ konata kiel skribanta protokolo (WAL). Ĝi estas dosiero ĉe la fino de kiu la celita operacio estas skribita strikte antaŭ modifi la B-arbon mem. Tiel, se datumkorupto estas detektita dum mem-diagnozo, la datumbazo konsultas la protokolon por meti sin en ordo.
LMDB elektis malsaman metodon kiel faŭltolereman mekanismon, nomitan kopio-sur-skribi. Ĝia esenco estas, ke anstataŭ ĝisdatigi datumojn sur ekzistanta paĝo, ĝi unue kopias ĝin tute kaj faras ĉiujn modifojn en la kopio.
Poste, por ke la ĝisdatigitaj datumoj estu disponeblaj, necesas ŝanĝi la ligon al la nodo, kiu fariĝis aktuala en sia gepatra nodo. Ĉar ĝi ankaŭ devas esti modifita por tio, ĝi ankaŭ estas kopiita antaŭe. La procezo daŭras rekursie ĝis la radiko. La lasta afero por ŝanĝi estas la datumoj sur la meta paĝo.
Se subite la procezo frakasas dum la ĝisdatiga procedo, tiam aŭ nova metapaĝo ne estos kreita, aŭ ĝi ne estos tute skribita en diskon, kaj ĝia ĉeksumo estos malĝusta. En ĉiu el ĉi tiuj du kazoj, novaj paĝoj estos neatingeblaj, sed malnovaj ne estos tuŝitaj. Ĉi tio forigas la bezonon, ke LMDB skribu antaŭen protokolon por konservi datuman konsistencon. Fakte, la strukturo de datumstokado sur la disko priskribita supre samtempe prenas sian funkcion. La foresto de eksplicita transakcia protokolo estas unu el la trajtoj de LMDB, kiu provizas altan rapidecon de legado de datumoj
La rezulta dezajno, nomita nur almetanta B-arbo, nature disponigas transakcian izolitecon kaj multi-versioning. En LMDB, ĉiu malferma transakcio estas rilata al la nuntempe rilata arboradiko. Ĝis la transakcio finiĝos, la paĝoj de la arbo asociita kun ĝi neniam estos ŝanĝitaj aŭ reuzitaj por novaj versioj de la datumoj.Tiel, vi povas labori tiom longe kiom vi volas kun ĝuste la aro de datumoj, kiu estis grava tiutempe. la transakcio estis malfermita, eĉ se la stokado daŭre estas aktive ĝisdatigita ĉi-momente. Ĉi tio estas la esenco de multiversio, igante LMDB ideala datumfonto por nia amato UICollectionView. Malferminte transakcion, ne necesas pliigi la memoran spuron de la aplikaĵo per haste elpumpante aktualajn datumojn en iun en-memoran strukturon, pro timo resti sen nenio. Ĉi tiu trajto distingas LMDB de la sama SQLite, kiu ne povas fanfaroni pri tia totala izolado. Malferminte du transakciojn en ĉi-lasta kaj foriginte certan rekordon ene de unu el ili, ne plu eblos akiri la saman rekordon ene de la dua restanta.
La dorsflanko de la monero estas la eble signife pli alta konsumo de virtuala memoro. La diapozitivo montras kiel aspektos la datumbaza strukturo se ĝi estas modifita samtempe kun 3 malfermitaj legaj transakcioj rigardantaj malsamajn versiojn de la datumbazo. Ĉar LMDB ne povas reuzi nodojn atingeblajn de radikoj asociitaj kun nunaj transakcioj, la vendejo havas neniun elekton sed asigni alian kvaran radikon en memoro kaj denove kloni la modifitajn paĝojn sub ĝi.
Ĉi tie estus utile rememori la sekcion pri memormapitaj dosieroj. Ŝajnas, ke la plia konsumo de virtuala memoro ne multe zorgu nin, ĉar ĝi ne kontribuas al la memorspuro de la aplikaĵo. Tamen, samtempe oni rimarkis, ke iOS estas tre avara en asignado de ĝi, kaj ni ne povas, kiel sur servilo aŭ labortablo, provizi LMDB-regionon de 1 terabajto kaj tute ne pensi pri ĉi tiu funkcio. Se eble, vi devus provi fari la vivdaŭron de transakcioj kiel eble plej mallonga.
4. Desegni datumskemon supre de la ŝlosilvalora API
Ni komencu nian API-analizon rigardante la bazajn abstraktaĵojn provizitajn de LMDB: medio kaj datumbazoj, ŝlosiloj kaj valoroj, transakcioj kaj kursoroj.
Noto pri kodaj listoj
Ĉiuj funkcioj en la publika LMDB API resendas la rezulton de sia laboro en formo de erarkodo, sed en ĉiuj postaj listoj ĝia konfirmo estas preterlasita pro koncizeco. En praktiko, ni eĉ uzis nian propran por interagi kun la deponejo. C++ envolvaĵoj , en kiu eraroj realiĝas kiel C++-esceptoj.
Kiel la plej rapida maniero por konekti LMDB al projekto por iOS aŭ macOS, mi sugestas mian CocoaPod .
4.1. Bazaj Abstraktaĵoj
Medio
strukturo MDB_env estas la deponejo de la interna stato de la LMDB. Prefiksita funkcio familio mdb_env permesas al vi agordi kelkajn el ĝiaj propraĵoj. En la plej simpla kazo, motoriniciigo aspektas tiel.
mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512)
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);En la aplikaĵo Mail.ru Cloud, ni ŝanĝis la defaŭltajn valorojn de nur du parametroj.
La unua estas la grandeco de la virtuala adresspaco al kiu estas mapita la stokaddosiero. Bedaŭrinde, eĉ sur la sama aparato, la specifa valoro povas varii signife de kuro al kuro. Por konsideri ĉi tiun funkcion de iOS, la maksimuma stokada volumo estas dinamike elektita. Komencante de certa valoro, ĝi estas sinsekve duonigita ĝis la funkcio mdb_env_open ne redonos rezulton malsaman de ENOMEM. En teorio, ekzistas ankaŭ la kontraŭa maniero - unue asignu minimumon da memoro al la motoro, kaj poste, kiam eraroj estas ricevitaj, MDB_MAP_FULL, pliigi ĝin. Tamen, ĝi estas multe pli dorna. La kialo estas, ke la procedo por re-asigni memoron (remap) uzante la funkcion mdb_env_set_map_size nuligas ĉiujn entojn (kursorilojn, transakciojn, ŝlosilojn kaj valorojn) antaŭe ricevitajn de la motoro. Konsideri ĉi tiun turnon de eventoj en la kodo kondukos al ĝia grava komplikaĵo. Se, tamen, virtuala memoro estas tre grava por vi, tiam ĉi tio povas esti kialo por pli detale rigardi la forkon, kiu iris malproksime antaŭen. , kie inter la anoncitaj ecoj ekzistas "aŭtomata sur-la-muŝe datumbaza grandalĝustigo".
La dua parametro, kies defaŭlta valoro ne konvenis al ni, reguligas la mekanikon por certigi fadenan sekurecon. Bedaŭrinde, almenaŭ iOS 10 havas problemojn kun subteno por fadena loka stokado. Tial, en la supra ekzemplo, la deponejo estas malfermita kun la flago MDB_NOTLS. Krom tio, ĝi ankaŭ estis necesa C++ envolvaĵo eltranĉi variablojn kun ĉi tiu eco kaj en ĝi.
Datumbazoj
La datumbazo estas aparta B-arba kazo, kiun ni diskutis supre. Ĝia malfermo okazas ene de transakcio, kio povas ŝajni iom stranga komence.
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);Efektive, transakcio en LMDB estas konserva ento, ne specifa datumbaza ento. Ĉi tiu koncepto permesas fari atomajn operaciojn sur estaĵoj situantaj en malsamaj datumbazoj. Teorie, ĉi tio malfermas la eblecon modeligi tabelojn en la formo de malsamaj datumbazoj, sed iam mi prenis alian vojon, priskribitan detale sube.
Ŝlosiloj kaj valoroj
strukturo MDB_val modeligas la koncepton de kaj ŝlosilo kaj valoro. La deponejo ne havas ideon pri ilia semantiko. Por ŝi, io alia estas nur tabelo de bajtoj de difinita grandeco. La maksimuma ŝlosila grandeco estas 512 bajtoj.
typedef struct MDB_val {
size_t mv_size;
void *mv_data;
} MDB_val;Uzante komparilon, la vendejo ordigas la ŝlosilojn en suprena ordo. Se vi ne anstataŭigas ĝin per via, tiam la defaŭlta estos uzata, kiu ordigas ilin bajto-post-bajto en leksikografia ordo.
Transakcioj
La transakcia strukturo estas detale priskribita en , do ĉi tie mi mallonge ripetos iliajn ĉefajn ecojn:
- Subtenas ĉiujn bazajn ecojn : atomeco, konsistenco, izoliteco kaj fidindeco. Mi ne povas ne rimarki, ke estas cimo pri fortikeco en macOS kaj iOS, kiu estis riparita en MDBX. Vi povas legi pli en ilia .
- La aliro al multfadenado estas priskribita per la skemo "ununura verkisto / multoblaj legantoj". Verkistoj blokas unu la alian, sed ne blokas legantojn. Legantoj ne blokas verkistojn aŭ unu la alian.
- Subteno por nestitaj transakcioj.
- Multiversia subteno.
Multversio en LMDB estas tiel bona ke mi volas pruvi ĝin en ago. El la suba kodo vi povas vidi, ke ĉiu transakcio funkcias ĝuste kun la versio de la datumbazo kiu estis aktuala en la momento kiam ĝi estis malfermita, estante tute izolita de ĉiuj postaj ŝanĝoj. Iniciatigi la stokadon kaj aldoni testan rekordon al ĝi ne reprezentas ion interesan, do ĉi tiuj ritoj restas sub la spoiler.
Aldonante testan eniron
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);Mi rekomendas, ke vi provu la saman lertaĵon kun SQLite kaj vidu kio okazas.
Multiversion alportas tre belajn avantaĝojn al la vivo de iOS-programisto. Uzante ĉi tiun posedaĵon, vi povas facile kaj nature ĝustigi la ĝisdatigon de la datumfonto por ekranformoj, surbaze de uzant-spertaj konsideroj. Ekzemple, ni prenu funkcion de la Mail.ru Cloud-apliko kiel aŭtomate ŝargi enhavon de la sistema amaskomunikila galerio. Kun bona konekto, la kliento povas aldoni plurajn fotojn sekundo al la servilo. Se vi ĝisdatigas post ĉiu elŝuto UICollectionView kun amaskomunikila enhavo en la nubo de la uzanto, vi povas forgesi pri 60 fps kaj glata movo dum ĉi tiu procezo. Por malhelpi oftajn ekranajn ĝisdatigojn, vi devas iel limigi la rapidecon, je kiu datumoj ŝanĝiĝas en la suba UICollectionViewDataSource.
Se la datumbazo ne subtenas multiversion kaj permesas vin labori nur kun la nuna nuna stato, tiam por krei temp-stabilan momentfoton de la datumoj vi devas kopii ĝin aŭ al iu en-memora datumstrukturo aŭ al provizora tabelo. Ajna el ĉi tiuj aliroj estas tre multekosta. En la kazo de enmemora stokado, ni ricevas kostojn kaj en memoro, kaŭzitaj de stokado de konstruitaj objektoj, kaj en tempo, asociitaj kun redundaj ORM-transformoj. Koncerne la provizoran tablon, ĉi tio estas eĉ pli multekosta plezuro, kiu havas sencon nur en ne bagatelaj kazoj.
La multversia solvo de LMDB solvas la problemon pri konservado de stabila datumfonto en tre eleganta maniero. Sufiĉas nur malfermi transakcion kaj voila - ĝis ni kompletigos ĝin, la datumaro estas garantiita esti fiksita. La logiko por ĝia ĝisdatiga rapideco nun estas tute en la manoj de la prezenta tavolo, sen superŝarĝo de signifaj rimedoj.
Kurseroj
Kurseroj disponigas mekanismon por orda ripetado super ŝlosil-valoraj paroj tra B-arba travojaĝado. Sen ili, estus neeble efike modeligi la tabelojn en la datumbazo, al kiu ni nun turnas sin.
4.2. Tabla Modelado
La posedaĵo de ŝlosila mendo permesas al vi konstrui altnivelan abstraktadon kiel tabelon super bazaj abstraktaĵoj. Ni konsideru ĉi tiun procezon uzante la ekzemplon de la ĉefa tablo de nuba kliento, kiu konservas informojn pri ĉiuj dosieroj kaj dosierujoj de la uzanto.
Tabelskemo
Unu el la oftaj scenaroj, por kiuj tabelstrukturo kun dosierujo-arbo devus esti tajlorita, estas la elekto de ĉiuj elementoj situantaj ene de antaŭfiksita dosierujo. Bona datuma organiza modelo por efikaj demandoj de ĉi tiu speco estas . Por efektivigi ĝin aldone al la ŝlosilvalora stokado, necesas ordigi la ŝlosilojn de dosieroj kaj dosierujoj tiel, ke ili estu grupigitaj laŭ sia membreco en la gepatra dosierujo. Krome, por montri la enhavon de la dosierujo en la formo konata al Vindoza uzanto (unue dosierujoj, poste dosieroj, ambaŭ ordigitaj alfabete), necesas enmeti la respondajn kromajn kampojn en la ŝlosilon.
La suba bildo montras kiel, surbaze de la nuna tasko, povus aspekti reprezentado de ŝlosiloj en formo de bajta tabelo. La bajtoj kun la identigilo de la gepatra dosierujo (ruĝa) estas metitaj unue, poste kun la tipo (verda) kaj en la vosto kun la nomo (blua).Estante ordigitaj per la defaŭlta LMDB-komparilo en leksikografa ordo, ili estas ordigitaj en la postulata maniero. Sinsekve trapasi klavojn kun la sama ruĝa prefikso donas al ni iliajn rilatajn valorojn en la ordo, kiam ili devus esti montrataj en la uzantinterfaco (dekstre), sen postuli aldonan post-traktadon.
Seriigante Ŝlosilojn kaj Valorojn
Multaj metodoj por seri objektoj estis inventitaj en la mondo. Ĉar ni havis neniun alian postulon krom rapideco, ni elektis la plej rapidan ebla por ni mem - forĵetaĵo de la memoro okupata de okazo de la lingvostrukturo C. Tiel, la ŝlosilo de dosieruja elemento povas esti modeligita per la sekva strukturo. NodeKey.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Ŝpari NodeKey en stokado bezonata en objekto MDB_val poziciigu la datummontrilon al la adreso de la komenco de la strukturo, kaj kalkulu ilian grandecon per la funkcio sizeof.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = sizeof(NodeKey),
.mv_data = (void *)key
};
}En la unua ĉapitro pri datumbazaj elektkriterioj, mi menciis minimumigi dinamikajn asignojn ene de CRUD-operacioj kiel gravan elektfaktoron. Funkcia kodo serialize montras kiel en la kazo de LMDB ili povas esti tute evititaj kiam oni enmetas novajn rekordojn en la datumbazon. La envenanta bajta tabelo de la servilo unue estas transformita en stakstrukturojn, kaj poste ili estas banale forĵetitaj en stokadon. Konsiderante, ke ankaŭ ne ekzistas dinamikaj asignoj ene de LMDB, vi povas akiri mirindan situacion laŭ iOS-normoj - uzu nur stakan memoron por labori kun datumoj laŭ la tuta vojo de la reto al la disko!
Mendado de ŝlosiloj per binara komparilo
La ŝlosila orda rilato estas specifita per speciala funkcio nomata komparilo. Ĉar la motoro scias nenion pri la semantiko de la bajtoj kiujn ili enhavas, la defaŭlta komparilo havas neniun elekton ol aranĝi la ŝlosilojn en leksikografa sinsekvo, recurrante al bajto-post-bajta komparo. Uzi ĝin por organizi strukturojn similas al razi per hakilo. Tamen en simplaj kazoj mi trovas ĉi tiun metodon akceptebla. La alternativo estas priskribita sube, sed ĉi tie mi notos kelkajn rastilojn disigitajn laŭ ĉi tiu vojo.
La unua afero por memori estas la memorprezentado de primitivaj datumtipoj. Tiel, sur ĉiuj Apple-aparatoj, entjeraj variabloj estas stokitaj en la formato . Tio signifas, ke la malplej signifa bajto estos maldekstre, kaj ne eblos ordigi entjerojn per bajto-post-bajta komparo. Ekzemple, provi fari tion kun aro de nombroj de 0 ĝis 511 produktos la sekvan rezulton.
// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)Por solvi ĉi tiun problemon, la entjeroj devas esti stokitaj en la ŝlosilo en formato taŭga por la bajta-bajta komparilo. Funkcioj de la familio helpos vin efektivigi la necesan transformon hton* (precipe htons por dubajtaj nombroj el la ekzemplo).
La formato por reprezenti ŝnurojn en programado estas, kiel vi scias, tutaĵo . Se la semantiko de ĉenoj, same kiel la kodigo uzata por reprezenti ilin en memoro, sugestas, ke povas esti pli ol unu bajto per signo, tiam estas pli bone tuj forlasi la ideon uzi defaŭltan komparilon.
La dua afero memorinda estas strukturkampa kompililo. Pro ili, bajtoj kun rubaj valoroj povas esti formitaj en memoro inter kampoj, kio, kompreneble, rompas bajto-bajtan ordigon. Por forigi rubon, vi devas aŭ deklari kampojn en strikte difinita ordo, konservante alignajn regulojn en menso, aŭ uzi la atributon en la strukturo-deklaro. packed.
Mendado de ŝlosiloj per ekstera komparilo
La ŝlosila kompara logiko povas esti tro kompleksa por binara komparilo. Unu el la multaj kialoj estas la ĉeesto de teknikaj kampoj ene de strukturoj. Mi ilustros ilian aperon uzante la ekzemplon de ŝlosilo por dosieruja elemento, kiu jam estas konata al ni.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Malgraŭ ĝia simpleco, en la granda plimulto de kazoj ĝi konsumas tro da memoro. La bufro por la nomo okupas 256 bajtojn, kvankam averaĝe dosieroj kaj dosierujoj malofte superas 20-30 signojn.
Unu el la normaj teknikoj por optimumigi la grandecon de rekordo estas "tondi" ĝin al la reala grandeco. Ĝia esenco estas, ke la enhavo de ĉiuj variablo-longaj kampoj estas stokitaj en bufro ĉe la fino de la strukturo, kaj iliaj longoj estas stokitaj en apartaj variabloj. Laŭ ĉi tiu aliro, la ŝlosilo NodeKey estas transformita jene.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Plue, dum seriigado, la datumgrandeco ne estas specifita sizeof la tuta strukturo, kaj la grandeco de ĉiuj kampoj estas fiksa longo plus la grandeco de la efektive uzata parto de la bufro.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
.mv_data = (void *)key
};
}Rezulte de la refaktorado, ni ricevis signifajn ŝparaĵojn en la spaco okupita de ŝlosiloj. Tamen, pro la teknika kampo nameLength, la defaŭlta binara komparilo ne plu taŭgas por ŝlosila komparo. Se ni ne anstataŭigas ĝin per nia propra, tiam la longo de la nomo estos pli alta prioritata faktoro en ordigo ol la nomo mem.
LMDB permesas al ĉiu datumbazo havi sian propran ŝlosilan komparan funkcion. Ĉi tio estas farita uzante la funkcion mdb_set_compare strikte antaŭ malfermo. Pro evidentaj kialoj, ĝi ne povas esti ŝanĝita dum la tuta vivo de la datumbazo. La komparilo ricevas du klavojn en binara formato kiel enigo, kaj ĉe la eligo ĝi resendas la komparrezulton: malpli ol (-1), pli granda ol (1) aŭ egala al (0). Pseŭdokodo por NodeKey aspektas tiel.
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 // ...
}Tiel longe kiel ĉiuj ŝlosiloj en la datumbazo estas de la sama tipo, senkondiĉe gisi sian bajtan reprezentadon al la speco de la aplika ŝlosilstrukturo estas laŭleĝa. Estas unu nuanco ĉi tie, sed ĝi estos diskutita malsupre en la subsekcio "Legado de Rekordoj".
Seriigante Valorojn
LMDB laboras ekstreme intense kun la ŝlosiloj de stokitaj rekordoj. Ilia komparo unu kun la alia okazas en la kadro de ajna aplikata operacio, kaj la agado de la tuta solvo dependas de la rapideco de la komparilo. En ideala mondo, la defaŭlta binara komparilo devus sufiĉi por kompari ŝlosilojn, sed se vi devis uzi la proprajn, tiam la procedo por deserialigi ŝlosilojn en ĝi devus esti kiel eble plej rapida.
La datumbazo ne interesiĝas precipe pri la valorparto de la rekordo (valoro). Ĝia konvertiĝo de bajta reprezentado al objekto okazas nur kiam ĝi jam estas postulata de la aplika kodo, ekzemple, por montri ĝin sur la ekrano. Ĉar tio okazas relative malofte, la rapidecpostuloj por ĉi tiu proceduro ne estas tiel kritikaj, kaj en ĝia efektivigo ni estas multe pli liberaj koncentriĝi pri oportuno.Ekzemple, por seriigi metadatumojn pri dosieroj kiuj ankoraŭ ne estis elŝutitaj, ni uzas NSKeyedArchiver.
NSData *data = serialize(object);
MDB_val value = {
.mv_size = data.length,
.mv_data = (void *)data.bytes
};Tamen, estas tempoj kiam rendimento ankoraŭ gravas. Ekzemple, dum konservado de metainformoj pri la dosierstrukturo de uzantnubo, ni uzas la saman memorforĵeton de objektoj. La kulminaĵo de la tasko generi seriigitan reprezentadon de ili estas la fakto, ke la elementoj de dosierujo estas modeligitaj de hierarkio de klasoj.
Por efektivigi ĝin en la C-lingvo, specifaj kampoj de la heredantoj estas metitaj en apartajn strukturojn, kaj ilia ligo kun la baza estas specifita per kampo de tipo unio. La fakta enhavo de la unio estas specifita per la teknika atributtipo.
typedef struct NodeValue {
EntityId localId;
EntityType type;
union {
FileInfo file;
DirectoryInfo directory;
} info;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeValue;Aldono kaj ĝisdatigo de registroj
La seriigita ŝlosilo kaj valoro povas esti aldonitaj al la vendejo. Por fari tion, uzu la funkcion mdb_put.
// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);En la agorda stadio, la konservado povas esti permesita aŭ malpermesita stoki plurajn rekordojn per la sama ŝlosilo.Se duobligo de ŝlosiloj estas malpermesita, tiam dum enmetado de rekordo, vi povas determini ĉu ĝisdatigi ekzistantan rekordon estas permesita aŭ ne. Se frakasado povas okazi nur kiel rezulto de eraro en la kodo, tiam vi povas protekti vin kontraŭ ĝi specifante la flagon NOOVERWRITE.
Legante enskribojn
Por legi rekordojn en LMDB, uzu la funkcion mdb_get. Se la ŝlosil-valora paro estas reprezentita per antaŭe forĵetitaj strukturoj, tiam ĉi tiu proceduro aspektas tiel.
NodeValue * const readNode(..., NodeKey * const key) {
MDB_val rawKey = serialize(key);
MDB_val rawValue;
mdb_get(..., &rawKey, &rawValue);
return (NodeValue * const)rawValue.mv_data;
}La prezentita listo montras kiel seriigo per strukturo-dump ebligas vin forigi dinamikajn atribuojn ne nur dum skribado, sed dum legado de datumoj. Derivita de funkcio mdb_get la montrilo rigardas precize la virtualan memoradreson kie la datumbazo stokas la bajtan reprezentadon de la objekto. Fakte, ni ricevas specon de ORM kiu provizas tre altan datuman legadon preskaŭ senpage. Malgraŭ la tuta beleco de la aliro, necesas memori plurajn trajtojn asociitajn kun ĝi.
- Por nurlegebla transakcio, la montrilo al la valorstrukturo estas garantiita por resti valida nur ĝis la transakcio estas fermita. Kiel antaŭe notite, la B-arbaj paĝoj, sur kiuj troviĝas objekto, danke al la principo de kopio-sur-skribi, restas senŝanĝaj kondiĉe ke ili estas referencitaj de almenaŭ unu transakcio. Samtempe, tuj kiam la lasta transakcio asociita kun ili finiĝas, la paĝoj povas esti reuzitaj por novaj datumoj. Se necesas, ke objektoj postvivu la transakcion kiu generis ilin, tiam ili ankoraŭ devas esti kopiitaj.
- Por reskriba transakcio, la montrilo al la rezulta valorstrukturo validos nur ĝis la unua modifa proceduro (skribado aŭ forigo de datumoj).
- Kvankam la strukturo
NodeValuene plentaŭga, sed eltondita (vidu subsekcion "Mendi klavojn per ekstera komparilo"), vi povas sekure aliri ĝiajn kampojn per la montrilo. La ĉefa afero estas ne dereferenci ĝin! - Neniam la strukturo estu modifita per la ricevita montrilo. Ĉiuj ŝanĝoj devas esti faritaj nur per la metodo
mdb_put. Tamen, kiom ajn vi volas fari tion, tio ne eblos, ĉar la memorareo kie ĉi tiu strukturo situas estas mapita en nurlega reĝimo. - Remapu dosieron al la proceza adresspaco por, ekzemple, pliigi la maksimuman stokan grandecon uzante la funkcion
mdb_env_set_map_sizetute nuligas ĉiujn transakciojn kaj rilatajn entojn ĝenerale kaj montrilojn al certaj objektoj aparte.
Fine, alia trajto estas tiel insida, ke malkaŝi ĝian esencon ne konvenas al nur alia alineo. En la ĉapitro pri la B-arbo, mi donis diagramon pri kiel ĝiaj paĝoj estas aranĝitaj en memoro. El tio sekvas, ke la adreso de la komenco de la bufro kun seriigitaj datumoj povas esti absolute arbitra. Pro tio, la montrilo al ili ricevis en la strukturo MDB_val kaj reduktita al montrilo al strukturo, ĝi montriĝas nevicigita en la ĝenerala kazo. Samtempe, la arkitekturoj de iuj blatoj (en la kazo de iOS tio estas armv7) postulas, ke la adreso de ajna datumo estu oblo de la grandeco de la maŝinvorto aŭ, alivorte, la bita grandeco de la sistemo ( por armv7 ĝi estas 32 bitoj). Alivorte, operacio kiel *(int *foo)0x800002 sur ili egalas eskapi kaj kondukas al ekzekuto kun verdikto EXC_ARM_DA_ALIGN. Estas du manieroj eviti tian malĝojan sorton.
La unua resumas al prepara kopiado de datumoj en evidente vicigitan strukturon. Ekzemple, sur kutima komparilo ĉi tio estos reflektita jene.
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 // ...
}Alternativa maniero estas sciigi la kompililon anticipe ke ŝlosilvaloraj strukturoj eble ne estas atribut-vicigitaj. aligned(1). Sur ARM vi povas havi la saman efikon kaj uzante la pakita atributo. Konsiderante ke ĝi ankaŭ helpas optimumigi la spacon okupitan de la strukturo, ĉi tiu metodo ŝajnas al mi preferinda, kvankam al pliigo de la kosto de operacioj de aliro al datumoj.
typedef struct __attribute__((packed)) NodeKey {
uint8_t parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Intervalaj demandoj
Por ripeti grupon de rekordoj, LMDB disponigas kursoran abstraktadon. Ni rigardu kiel labori kun ĝi uzante la ekzemplon de tabelo kun uzantnubo metadatenoj jam konataj al ni.
Kiel parto de montrado de listo de dosieroj en dosierujo, necesas trovi ĉiujn ŝlosilojn kun kiuj ĝiaj filaj dosieroj kaj dosierujoj estas asociitaj. En la antaŭaj subfakoj ni ordigis la ŝlosilojn NodeKey tia ke ili estas ĉefe ordigitaj per la ID de la gepatra dosierujo. Tiel, teknike, la tasko preni la enhavon de dosierujo estas meti la kursoron sur la supran limon de la grupo de ŝlosiloj kun antaŭfiksita prefikso kaj tiam ripetadi al la malsupra limo.
La supra limo troveblas rekte per sinsekva serĉo. Por fari tion, la kursoro estas metita komence de la tuta listo de ŝlosiloj en la datumbazo kaj plu pliigita ĝis ŝlosilo kun la identigilo de la gepatra dosierujo aperas sub ĝi. Ĉi tiu aliro havas 2 evidentajn malavantaĝojn:
- Lineara serĉkomplekseco, kvankam, kiel estas konata, en arboj ĝenerale kaj en B-arbo aparte ĝi povas esti farita en logaritma tempo.
- Vane ĉiuj paĝoj antaŭ la serĉata estas levitaj de la dosiero al la ĉefa memoro, kiu estas ege multekosta.
Feliĉe, la LMDB API provizas efikan manieron komence poziciigi la kursoron.Por fari tion, vi devas generi ŝlosilon kies valoro estas evidente malpli ol aŭ egala al la ŝlosilo situanta ĉe la supra limo de la intervalo. Ekzemple, rilate al la listo en la supra figuro, ni povas fari ŝlosilon en kiu la kampo parentId estos egala al 2, kaj ĉiuj ceteraj estas plenigitaj per nuloj. Tia parte plenigita ŝlosilo estas liverita al la funkcio-enigo mdb_cursor_get indikante la operacion 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);Se la supra limo de grupo de ŝlosiloj estas trovita, tiam ni ripetas super ĝi ĝis aŭ ni renkontas aŭ la ŝlosilo renkontas alian parentId, aŭ la ŝlosiloj tute ne elĉerpiĝos.
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 groupKio estas bela estas, ke kiel parto de la ripeto uzante mdb_cursor_get, ni ricevas ne nur la ŝlosilon, sed ankaŭ la valoron. Se, por plenumi la specimenajn kondiĉojn, vi devas interalie kontroli la kampojn el la valorparto de la rekordo, tiam ili estas sufiĉe alireblaj sen aldonaj gestoj.
4.3. Modeligado de rilatoj inter tabeloj
Nuntempe ni sukcesis konsideri ĉiujn aspektojn de desegnado kaj laboro kun unu-tabla datumbazo. Ni povas diri, ke tabelo estas aro de ordigitaj registroj konsistantaj el la sama speco de ŝlosil-valoraj paroj. Se vi montras ŝlosilon kiel rektangulon kaj la rilatan valoron kiel paralelepipedo, vi ricevas vidan diagramon de la datumbazo.
Tamen en la reala vivo malofte eblas elteni per tiom malmulte da sangoverŝado. Ofte en datumbazo necesas, unue, havi plurajn tabelojn, kaj due, fari elektojn en ili en ordo malsama ol la ĉefa ŝlosilo. Ĉi tiu lasta sekcio estas dediĉita al la temoj de ilia kreado kaj interkonekto.
Indeksaj tabeloj
La nuba aplikaĵo havas sekcion "Galerio". Ĝi montras amaskomunikilan enhavon de la tuta nubo, ordigita laŭ dato. Por optimume efektivigi tian elekton, apud la ĉefa tablo vi devas krei alian kun nova speco de ŝlosiloj. Ili enhavos kampon kun la dato kiam la dosiero estis kreita, kiu funkcios kiel la ĉefa ordiga kriterio. Ĉar la novaj ŝlosiloj referencas la samajn datumojn kiel la ŝlosiloj en la ĉeftabelo, ili estas nomitaj indeksaj ŝlosiloj. En la suba bildo ili estas reliefigitaj oranĝe.
Por apartigi la ŝlosilojn de malsamaj tabeloj unu de la alia ene de la sama datumbazo, kroma teknika kampa tableId estis aldonita al ĉiuj el ili. Farante ĝin la plej alta prioritato por ordigo, ni atingos grupigon de ŝlosiloj unue laŭ tabeloj, kaj ene de tabeloj - laŭ niaj propraj reguloj.
La indeksa ŝlosilo referencas la samajn datumojn kiel la ĉefa ŝlosilo. Simpla efektivigo de ĉi tiu posedaĵo per asocii kun ĝi kopion de la valorparto de la primara ŝlosilo ne estas optimuma de pluraj vidpunktoj:
- Laŭ spaco okupata, la metadatenoj povas esti sufiĉe riĉaj.
- El rendimento vidpunkto, ĉar ĝisdatigante la metadatenojn de nodo, vi devos reverki ĝin per du klavoj.
- De la vidpunkto de kodsubteno, se ni forgesas ĝisdatigi la datumojn por unu el la ŝlosiloj, ni ricevos eviteblan cimon de datuma nekongrueco en la stokado.
Poste ni konsideros kiel forigi ĉi tiujn mankojn.
Organizado de rilatoj inter tabloj
La ŝablono bone taŭgas por ligi la indeksan tabelon kun la ĉefa tabelo "ŝlosilo kiel valoro". Kiel ĝia nomo sugestas, la valorparto de la indeksa rekordo estas kopio de la primara ŝlosilvaloro. Ĉi tiu aliro forigas ĉiujn supre menciitajn malavantaĝojn asociitajn kun stokado de kopio de la valorparto de la primara rekordo. La nura kosto estas, ke por akiri valoron per indeksa ŝlosilo, vi devas fari 2 demandojn al la datumbazo anstataŭ unu. Skeme, la rezulta datumbaza skemo aspektas tiel.
Alia ŝablono por organizi rilatojn inter tabloj estas "redunda ŝlosilo". Ĝia esenco estas aldoni kromajn atributojn al la ŝlosilo, kiuj estas bezonataj ne por ordigo, sed por rekrei la rilatan ŝlosilon.En la aplikaĵo Mail.ru Cloud estas realaj ekzemploj de ĝia uzo, tamen, por eviti profundan plonĝon en la kuntekston de specifaj iOS kadroj, mi donos fikcian, sed sed pli klaran ekzemplon.
Nubaj moveblaj klientoj havas paĝon, kiu montras ĉiujn dosierojn kaj dosierujojn, kiujn la uzanto dividis kun aliaj homoj. Ĉar ekzistas relative malmultaj tiaj dosieroj, kaj ekzistas multaj malsamaj specoj de specifaj informoj pri reklamado asociita kun ili (kiu estas koncedita aliro, kun kiuj rajtoj, ktp.), ne estos racie ŝarĝi la valoran parton de la registri per ĝi en la ĉeftabelo. Tamen, se vi volas montri tiajn dosierojn eksterrete, vi ankoraŭ bezonas konservi ĝin ie. Natura solvo estas krei apartan tablon por ĝi. En la suba diagramo, ĝia ŝlosilo estas prefiksita per "P", kaj la lokokupilon "propnomo" povas esti anstataŭigita per la pli specifa valoro "publika informo".
Ĉiuj unikaj metadatenoj, por konservi la novan tabelon, estas metitaj en la valorparton de la rekordo. Samtempe, vi ne volas duobligi la datumojn pri dosieroj kaj dosierujoj, kiuj jam estas konservitaj en la ĉefa tabelo. Anstataŭe, redundaj datumoj estas aldonitaj al la ŝlosilo "P" en la formo de la kampoj "noda ID" kaj "tempomarko". Danke al ili, vi povas konstrui indeksan ŝlosilon, el kiu vi povas akiri ĉefan ŝlosilon, el kiu, finfine, vi povas akiri nodajn metadatumojn.
Konkludo
Ni taksas la rezultojn de la efektivigo de LMDB pozitive. Post ĝi, la nombro de aplikaj frostiĝoj malpliiĝis je 30%.
La rezultoj de la laboro farita resonis preter la iOS-teamo. Nuntempe, unu el la ĉefaj "Dosieroj" sekcioj en la Android-aplikaĵo ankaŭ ŝanĝis al uzado de LMDB, kaj aliaj partoj estas survoje. La C-lingvo, en kiu la ŝlosilvalora vendejo estas efektivigita, estis bona helpo por komence krei aplikaĵan kadron ĉirkaŭ ĝi transplatforma en C++. Kodgeneratoro estis uzita por perfekte ligi la rezultan C++-bibliotekon kun platformkodo en Objective-C kaj Kotlin de Dropbox, sed tio estas tute alia historio.
fonto: www.habr.com