A la tardor del 2019, va tenir lloc un esdeveniment molt esperat a l'equip d'iOS de Mail.ru Cloud. La base de dades principal per a l'emmagatzematge persistent de l'estat de l'aplicació s'ha convertit en força exòtica per al món mòbil (LMDB). Sota el tall, es convida la vostra atenció a la seva revisió detallada en quatre parts. Primer, parlem dels motius d'una elecció tan difícil i no trivial. A continuació, passem a la consideració de tres balenes al cor de l'arquitectura LMDB: fitxers assignats a memòria, arbre B +, enfocament de còpia sobre escriptura per implementar transaccions i multiversions. Finalment, per a les postres, la part pràctica. En ell, veurem com dissenyar i implementar un esquema base amb diverses taules, inclosa una d'índex, a la part superior de l'API de valor-clau de baix nivell.
Contingut
3.1.
3.2.
3.3.
4.1.
4.2.
4.3.
1. Motivació de la implementació
Un cop l'any, l'any 2015, ens vam encarregar de prendre una mètrica, amb quina freqüència es retarda la interfície de la nostra aplicació. No només hem fet això. Cada cop tenim més queixes pel fet que de vegades l'aplicació deixa de respondre a les accions de l'usuari: no es prem els botons, les llistes no es desplacen, etc. Sobre la mecànica de les mesures a AvitoTech, així que aquí només dono l'ordre dels números.
Els resultats de la mesura es van convertir en una dutxa freda per a nosaltres. Va resultar que els problemes causats per les congelacions són molt més que qualsevol altre. Si, abans d'adonar-se d'aquest fet, el principal indicador tècnic de la qualitat era lliure d'accidents, després del focus en lliure congelació.
Havent construït i havent gastat и anàlisi de les seves causes, el principal enemic va quedar clar: una lògica de negoci pesada que s'executava al fil principal de l'aplicació. Una reacció natural a aquesta desgràcia va ser un desig ardent d'empènyer-la a les corrents de treball. Per a una solució sistemàtica d'aquest problema, vam recórrer a una arquitectura multifils basada en actors lleugers. Vaig dedicar les seves adaptacions al món iOS al twitter col·lectiu i . Com a part de la història actual, vull destacar aquells aspectes de la decisió que van influir en l'elecció de la base de dades.
El model d'actor d'organització del sistema assumeix que el multithreading es converteix en la seva segona essència. Als objectes de model que hi ha els agrada creuar els límits del fil. I això no ho fan de vegades i en alguns llocs, sinó gairebé constantment i a tot arreu.
La base de dades és un dels components bàsics del diagrama presentat. La seva tasca principal és implementar un patró macro . Si al món empresarial s'utilitza per organitzar la sincronització de dades entre serveis, aleshores en el cas d'una arquitectura d'actor, les dades entre fils. Per tant, necessitàvem una base de dades d'aquest tipus, amb la qual treballar en un entorn multifils no causa ni tan sols dificultats mínimes. En particular, això vol dir que els objectes que se'n deriven han de ser almenys segurs per a fils i, idealment, no poden ser mutables. Com sabeu, aquest últim es pot utilitzar simultàniament des de diversos fils sense recórrer a cap tipus de bloqueig, la qual cosa té un efecte beneficiós en el rendiment.
El segon factor significatiu que va influir en l'elecció de la base de dades va ser la nostra API al núvol. Es va inspirar en l'enfocament git per a la sincronització. Com ell a qui apuntàvem , que sembla més que adequat per als clients del núvol. Es va suposar que només una vegada eliminarien l'estat complet del núvol, i després la sincronització en la gran majoria dels casos es produiria mitjançant canvis constants. Per desgràcia, aquesta possibilitat encara es troba només a la zona teòrica i, a la pràctica, els clients no han après a treballar amb pegats. Hi ha una sèrie de raons objectives per a això, que, per no endarrerir la introducció, deixarem fora dels parèntesis. Ara són molt més interessants els resultats instructius de la lliçó sobre què passa quan l'API va dir "A" i el seu consumidor no va dir "B".
Per tant, si us imagineu git, que, en executar una ordre d'extracció, en lloc d'aplicar pedaços a una instantània local, compara el seu estat complet amb el del servidor complet, aleshores tindreu una idea bastant precisa de com es sincronitza. es produeix als clients del núvol. És fàcil endevinar que per a la seva implementació és necessari assignar dos arbres DOM a la memòria amb metainformació sobre tots els fitxers del servidor i locals. Resulta que si un usuari emmagatzema 500 mil fitxers al núvol, per sincronitzar-lo, cal recrear i destruir dos arbres amb 1 milió de nodes. Però cada node és un agregat que conté un gràfic de subobjectes. En aquest sentit, s'esperaven els resultats del perfil. Va resultar que fins i tot sense tenir en compte l'algoritme de fusió, el mateix procediment de crear i després destruir un gran nombre d'objectes petits costa un bon cèntim. La situació s'agreuja pel fet que l'operació de sincronització bàsica s'inclou en un gran nombre. dels scripts d'usuari. Com a resultat, arreglem el segon criteri important per triar una base de dades: la capacitat d'implementar operacions CRUD sense assignació dinàmica d'objectes.
Altres requisits són més tradicionals i la seva llista completa és la següent.
- Seguretat del fil.
- Multiprocessament. Dictat pel desig d'utilitzar la mateixa instància de base de dades per sincronitzar l'estat no només entre fils, sinó també entre l'aplicació principal i les extensions d'iOS.
- La capacitat de representar entitats emmagatzemades com a objectes no mutables
- Manca d'assignacions dinàmiques dins de les operacions CRUD.
- Suport de transaccions per a propietats bàsiques Paraules clau: atomicitat, consistència, aïllament i fiabilitat.
- Velocitat en els casos més populars.
Amb aquest conjunt de requisits, SQLite era i continua sent una bona opció. Tanmateix, com a part de l'estudi de les alternatives, em vaig trobar amb un llibre . Sota el seu lideratge, es va escriure un punt de referència que compara la velocitat de treball amb diferents bases de dades en escenaris reals del núvol. El resultat va superar les expectatives més disparades. En els casos més populars: obtenir un cursor en una llista ordenada de tots els fitxers i una llista ordenada de tots els fitxers per a un directori determinat, LMDB va resultar ser 10 vegades més ràpid que SQLite. L'elecció es va fer evident.
2. Posicionament LMDB
LMDB és una biblioteca, molt petita (només 10K línies), que implementa la capa fonamental més baixa de bases de dades: l'emmagatzematge.
El diagrama anterior mostra que comparar LMDB amb SQLite, que implementa nivells encara més alts, generalment no és més correcta que SQLite amb Core Data. Seria més just citar els mateixos motors d'emmagatzematge com a competidors iguals: BerkeleyDB, LevelDB, Sophia, RocksDB, etc. Fins i tot hi ha desenvolupaments on LMDB actua com a component del motor d'emmagatzematge per a SQLite. El primer experiment d'aquest tipus el 2012 autor LMDB . va resultar tan intrigant que la seva iniciativa va ser recollida pels entusiastes de l'OSS i va trobar la seva continuació davant de . El gener de 2020 l'autor d'aquest projecte és Den Shearer a LinuxConfAu.
L'ús principal d'LMDB és com a motor per a bases de dades d'aplicacions. La biblioteca deu la seva aparença als desenvolupadors , que estaven molt descontents amb BerkeleyDB com a base del seu projecte. Allunyant-se de la humil biblioteca , Howard Chu va ser capaç de crear una de les alternatives més populars del nostre temps. Va dedicar el seu reportatge genial a aquesta història, així com a l'estructura interna de LMDB. . Leonid Yuriev (també conegut com ) de Positive Technologies a la seva ponència a Highload 2015 . En ell, parla de LMDB en el context d'una tasca similar d'implementació de ReOpenLDAP, i LevelDB ja ha estat objecte de crítiques comparatives. Com a resultat de la implementació, Positive Technologies fins i tot va obtenir una bifurcació en desenvolupament actiu amb característiques, optimitzacions i molt saboroses .
L'LMDB també s'utilitza sovint com a emmagatzematge. Per exemple, el navegador Mozilla Firefox per a diverses necessitats i, a partir de la versió 9, Xcode el seu SQLite per emmagatzemar índexs.
El motor també es va enganxar al món del desenvolupament mòbil. Els rastres del seu ús poden ser al client iOS per a Telegram. LinkedIn va fer un pas més enllà i va triar LMDB com a emmagatzematge predeterminat per al seu marc de memòria cau de dades de producció pròpia, Rocket Data, sobre el qual en un article del 2016.
LMDB està lluitant amb èxit per un lloc al sol al nínxol deixat per BerkeleyDB després de la transició sota el control d'Oracle. La biblioteca és estimada per la seva velocitat i fiabilitat, fins i tot en comparació amb la seva pròpia espècie. Com sabeu, no hi ha dinars gratuïts, i m'agradaria subratllar el compromís que haureu d'afrontar a l'hora de triar entre LMDB i SQLite. El diagrama anterior demostra clarament com s'aconsegueix l'augment de la velocitat. En primer lloc, no paguem capes addicionals d'abstracció a la part superior de l'emmagatzematge en disc. Per descomptat, en una bona arquitectura, encara no pots prescindir d'ells, i inevitablement apareixeran al codi de l'aplicació, però seran molt més prims. No tindran característiques que no siguin requerides per una aplicació específica, per exemple, suport per a consultes en llenguatge SQL. En segon lloc, és possible implementar de manera òptima el mapeig de les operacions de l'aplicació a les sol·licituds a l'emmagatzematge en disc. Si SQLite prové de les necessitats mitjanes d'una aplicació mitjana, llavors vostè, com a desenvolupador d'aplicacions, coneix bé els escenaris de càrrega principals. Per a una solució més productiva, haureu de pagar un preu més elevat tant pel desenvolupament de la solució inicial com pel seu suport posterior.
3. Tres balenes LMDB
Després de mirar l'LMDB a vista d'ocell, és hora d'aprofundir. Les tres seccions següents es dedicaran a l'anàlisi de les principals balenes sobre les quals es recolza l'arquitectura d'emmagatzematge:
- Fitxers assignats a memòria com a mecanisme per treballar amb disc i sincronitzar estructures de dades internes.
- Arbre B+ com a organització de l'estructura de dades emmagatzemades.
- Còpia sobre escriptura com a enfocament per proporcionar propietats transaccionals d'ACID i multiversions.
3.1. Balena #1. Fitxers assignats a memòria
Els fitxers assignats a la memòria són un element arquitectònic tan important que fins i tot apareixen al nom del dipòsit. Els problemes de la memòria cau i la sincronització de l'accés a la informació emmagatzemada estan totalment a mercè del sistema operatiu. LMDB no conté cap memòria cau en si mateix. Aquesta és una decisió conscient de l'autor, ja que llegir dades directament dels fitxers mapats us permet reduir molts racons en la implementació del motor. A continuació es mostra una llista lluny de ser completa d'alguns d'ells.
- Mantenir la coherència de les dades a l'emmagatzematge quan es treballa amb ella des de diversos processos passa a ser responsabilitat del sistema operatiu. A la següent secció, es parla d'aquesta mecànica amb detall i amb imatges.
- L'absència de memòria cau alleuja completament l'LMDB de la sobrecàrrega associada a les assignacions dinàmiques. Llegir dades a la pràctica és posar el punter a l'adreça correcta a la memòria virtual i res més. Sembla una fantasia, però a la font del dipòsit, totes les trucades de calloc es concentren a la funció de configuració del dipòsit.
- L'absència de memòria cau també significa l'absència de bloquejos associats a la sincronització per accedir-hi. Els lectors, dels quals pot existir un nombre arbitrari al mateix temps, no es troben amb un sol mutex en el camí cap a les dades. Per això, la velocitat de lectura té una escalabilitat lineal ideal pel que fa al nombre de CPU. A LMDB, només es sincronitzen les operacions de modificació. Només hi pot haver un escriptor alhora.
- Un mínim d'emmagatzematge en memòria cau i lògica de sincronització salva el codi d'un tipus d'error extremadament complex associat amb el treball en un entorn multiprocés. Hi va haver dos estudis de bases de dades interessants a la conferència Usenix OSDI 2014: и . D'ells podeu obtenir informació tant sobre la fiabilitat sense precedents de LMDB com sobre la implementació gairebé impecable de les propietats ACID de les transaccions, que la supera en el mateix SQLite.
- El minimalisme de LMDB permet que la representació de la màquina del seu codi es col·loqui completament a la memòria cau L1 del processador amb les característiques de velocitat resultants.
Malauradament, a iOS, els fitxers assignats a la memòria no són tan roses com voldríem. Per parlar dels inconvenients associats a ells de manera més conscient, cal recordar els principis generals per implementar aquest mecanisme en els sistemes operatius.
Informació general sobre fitxers assignats a memòria
Amb cada aplicació executable, el sistema operatiu associa una entitat anomenada procés. A cada procés se li assigna un rang contigu d'adreces en les quals col·loca tot el que necessita per funcionar. Les adreces més baixes contenen seccions amb codi i dades i recursos codificats. A continuació ve el bloc creixent d'espai d'adreces dinàmiques, conegut per nosaltres com el munt. Conté les adreces de les entitats que apareixen durant el funcionament del programa. A la part superior hi ha l'àrea de memòria utilitzada per la pila d'aplicacions. Creix o es redueix, és a dir, la seva mida també té un caràcter dinàmic. Perquè la pila i el munt no empenyin i interfereixin entre si, estan separats en diferents extrems de l'espai d'adreces Hi ha un forat entre les dues seccions dinàmiques a la part superior i inferior. El sistema operatiu utilitza les adreces d'aquesta secció central per associar-se amb un procés de diverses entitats. En particular, pot assignar un determinat conjunt continu d'adreces a un fitxer del disc. Aquest fitxer s'anomena fitxer assignat a memòria.
L'espai d'adreces assignat a un procés és enorme. Teòricament, el nombre d'adreces està limitat només per la mida del punter, que està determinada per la profunditat de bits del sistema. Si se li assignés memòria física 1 en 1, llavors el primer procés s'engoleixaria tota la memòria RAM i no hi hauria cap qüestió de multitasca.
No obstant això, sabem per experiència que els sistemes operatius moderns poden executar tants processos com vulgueu al mateix temps. Això és possible a causa del fet que destinen molta memòria als processos només en paper, però en realitat només carreguen a la memòria física principal aquella part que es demana aquí i ara. Per tant, la memòria associada al procés s'anomena virtual.
El sistema operatiu organitza la memòria virtual i física en pàgines d'una mida determinada. Tan bon punt es requereix una determinada pàgina de memòria virtual, el sistema operatiu la carrega a la memòria física i posa una correspondència entre elles en una taula especial. Si no hi ha ranures lliures, una de les pàgines carregades anteriorment es copia al disc i la sol·licitada ocupa el seu lloc. Aquest procediment, al qual tornarem en breu, s'anomena intercanvi. La figura següent il·lustra el procés descrit. En ella es va carregar la pàgina A amb l'adreça 0 i es va col·locar a la pàgina de memòria principal amb l'adreça 4. Aquest fet es va reflectir a la taula de correspondència de la cel·la número 0.
Amb els fitxers amb mapes de memòria, la història és exactament la mateixa. Lògicament, suposadament es col·loquen de forma contínua i íntegra a l'espai d'adreces virtuals. Tanmateix, entren a la memòria física pàgina per pàgina i només sota demanda. La modificació d'aquestes pàgines es sincronitza amb el fitxer del disc. Així, podeu realitzar E/S de fitxers, simplement treballant amb bytes a la memòria: tots els canvis seran transferits automàticament pel nucli del sistema operatiu al fitxer original.
â € <
La imatge següent mostra com LMDB sincronitza el seu estat quan treballa amb la base de dades des de diferents processos. En mapejar la memòria virtual de diferents processos en el mateix fitxer, obliguem de facto el sistema operatiu a sincronitzar de manera transitiva certs blocs dels seus espais d'adreces entre si, que és on mira LMDB.
â € <
Un matís important és que LMDB modifica el fitxer de dades de manera predeterminada mitjançant el mecanisme de crida del sistema d'escriptura i el fitxer en si es mostra en mode de només lectura. Aquest enfocament té dues implicacions importants.
La primera conseqüència és comuna a tots els sistemes operatius. La seva essència és afegir protecció contra danys inadvertits a la base de dades per codi incorrecte. Com sabeu, les instruccions executables d'un procés són gratuïtes per accedir a les dades des de qualsevol lloc del seu espai d'adreces. Al mateix temps, com acabem de recordar, mostrar un fitxer en mode lectura-escriptura vol dir que qualsevol instrucció també pot modificar-lo a més. Si ho fa per error, intentant, per exemple, sobreescriure realment un element de matriu en un índex inexistent, d'aquesta manera pot canviar accidentalment el fitxer assignat a aquesta adreça, la qual cosa conduirà a la corrupció de la base de dades. Si el fitxer es mostra en mode de només lectura, un intent de canviar l'espai d'adreces corresponent provocarà un bloqueig del programa amb el senyal. SIGSEGV, i el fitxer romandrà intacte.
La segona conseqüència ja és específica d'iOS. Ni l'autor ni cap altra font ho mencionen explícitament, però sense ell, LMDB no seria apte per funcionar en aquest sistema operatiu mòbil. El següent apartat està dedicat a la seva consideració.
Especificacions dels fitxers assignats a la memòria a iOS
El 2018, hi va haver un informe meravellós a la WWDC . Diu que a iOS totes les pàgines ubicades a la memòria física pertanyen a un dels 3 tipus: bruta, comprimida i neta.
La memòria neta és una col·lecció de pàgines que es poden canviar de manera segura de la memòria física. Les dades que contenen es poden tornar a carregar des de les seves fonts originals segons sigui necessari. Els fitxers assignats a memòria només de lectura entren en aquesta categoria. iOS no té por de descarregar les pàgines assignades a un fitxer de la memòria en qualsevol moment, ja que es garanteix que es sincronitzen amb el fitxer del disc.
â € <
Totes les pàgines modificades entren a la memòria bruta, independentment d'on es trobin originalment. En particular, també es classificaran d'aquesta manera els fitxers mapats de memòria modificats escrivint a la memòria virtual associada a ells. Obertura de LMDB amb bandera MDB_WRITEMAP, després de fer-hi canvis, podeu comprovar-ho vosaltres mateixos.
Tan bon punt una aplicació comença a ocupar massa memòria física, iOS comprimeix les seves pàgines brutes. La col·lecció de memòria ocupada per pàgines brutes i comprimides és l'anomenada petjada de memòria de l'aplicació. Quan arriba a un determinat valor llindar, el dimoni del sistema OOM killer arriba després del procés i l'acaba per força. Aquesta és la peculiaritat d'iOS en comparació amb els sistemes operatius d'escriptori. En canvi, la reducció de l'empremta de memòria canviant pàgines de la memòria física al disc no es proporciona a iOS, només es pot endevinar els motius. Potser el procediment per moure de manera intensiva les pàgines al disc i cap enrere consumeix massa energia per als dispositius mòbils, o iOS estalvia el recurs de reescriure cel·les en discs SSD, o potser els dissenyadors no estaven satisfets amb el rendiment global del sistema, on tot està intercanviat constantment. Sigui com sigui, el fet segueix sent.
La bona notícia, ja esmentada anteriorment, és que LMDB no utilitza el mecanisme mmap per actualitzar fitxers de manera predeterminada. D'aquesta manera, iOS classifica les dades renderitzades com a memòria neta i no contribueixen a la petjada de memòria. Això es pot verificar mitjançant una eina Xcode anomenada VM Tracker. La captura de pantalla següent mostra l'estat de la memòria virtual de l'aplicació iOS Cloud durant el funcionament. Al principi, s'hi van inicialitzar 2 instàncies LMDB. Al primer se li va permetre mapar el seu fitxer a 1 GiB de memòria virtual, el segon - 512 MiB. Tot i que ambdós emmagatzematges ocupen una certa quantitat de memòria resident, cap d'ells contribueix a la mida bruta.
Ara és el moment de les males notícies. Gràcies al mecanisme d'intercanvi dels sistemes operatius d'escriptori de 64 bits, cada procés pot ocupar tant espai d'adreces virtuals com l'espai lliure del disc dur permet el seu potencial intercanvi. Substituir l'intercanvi per compressió a iOS redueix dràsticament el màxim teòric. Ara tots els processos vius han d'encaixar a la memòria principal (llegir RAM) i tots aquells que no encaixen estan subjectes a la terminació forçada. S'esmenta com a l'anterior , i a . Com a conseqüència, iOS limita severament la quantitat de memòria disponible per a l'assignació mitjançant mmap. Aquí podeu veure els límits empírics de la quantitat de memòria que es podria assignar a diferents dispositius mitjançant aquesta trucada al sistema. En els models més moderns de telèfons intel·ligents, iOS s'ha tornat generós en 2 gigabytes, i en les versions superiors de l'iPad, en 4. A la pràctica, és clar, cal centrar-se en els models de dispositius compatibles més joves, on tot és molt trist. Encara pitjor, mirant l'estat de memòria de l'aplicació a VM Tracker, trobareu que LMDB està lluny de ser l'únic que reclama memòria assignada a memòria. Els bons trossos són menjats pels assignadors del sistema, fitxers de recursos, marcs d'imatge i altres depredadors més petits.
A partir dels resultats dels experiments al núvol, vam arribar als següents valors de compromís de memòria assignats per LMDB: 384 megabytes per a dispositius de 32 bits i 768 per a dispositius de 64 bits. Un cop esgotat aquest volum, totes les operacions de modificació comencen a completar-se amb el codi MDB_MAP_FULL. Observem aquests errors en el nostre seguiment, però són prou petits com per deixar-los de banda en aquesta etapa.
Una raó no òbvia del consum excessiu de memòria per l'emmagatzematge poden ser les transaccions de llarga durada. Per entendre com es relacionen aquests dos fenòmens, ens ajudarà a considerar les dues balenes LMDB restants.
3.2. Balena #2. B+-arbre
Per emular taules a la part superior d'un magatzem de valor-clau, les operacions següents han d'estar presents a la seva API:
- Inserció d'un element nou.
- Cerca un element amb una clau determinada.
- Eliminació d'un element.
- Itereu per intervals clau en el seu ordre d'ordenació.
L'estructura de dades més senzilla que pot implementar fàcilment les quatre operacions és un arbre de cerca binari. Cadascun dels seus nodes és una clau que divideix tot el subconjunt de claus fills en dos subarbres. A l'esquerra hi ha els que són més petits que el pare, i a la dreta, els que són més grans. L'obtenció d'un conjunt ordenat de claus s'aconsegueix mitjançant un dels clàssics recorreguts d'arbres.
Els arbres binaris tenen dos inconvenients fonamentals que impedeixen que siguin efectius com a estructura de dades de disc. En primer lloc, el grau del seu equilibri és impredictible. Hi ha un risc considerable d'obtenir arbres en els quals l'alçada de les diferents branques pot variar molt, la qual cosa empitjora notablement la complexitat algorítmica de la cerca en comparació amb l'esperada. En segon lloc, l'abundància d'enllaços creuats entre nodes priva els arbres binaris de localitat a la memòria, ja que els nodes propers (en termes d'enllaços entre ells) es poden localitzar en pàgines completament diferents de la memòria virtual. Com a conseqüència, fins i tot un simple recorregut de diversos nodes veïns en un arbre pot requerir visitar un nombre comparable de pàgines. Aquest és un problema fins i tot quan parlem de l'eficiència dels arbres binaris com a estructura de dades a la memòria, ja que girar constantment les pàgines a la memòria cau del processador no és barat. Quan es tracta d'aixecar amb freqüència pàgines relacionades amb nodes del disc, les coses es posen molt malament. .
Els arbres B, al ser una evolució dels arbres binaris, resolen els problemes identificats en el paràgraf anterior. En primer lloc, s'autoequilibren. En segon lloc, cadascun dels seus nodes divideix el conjunt de claus fills no en 2, sinó en subconjunts ordenats M, i el nombre M pot ser força gran, de l'ordre de diversos centenars o fins i tot milers.
Així:
- Cada node té un gran nombre de claus ja ordenades i els arbres són molt baixos.
- L'arbre adquireix la propietat de la localitat a la memòria, ja que les claus que tenen un valor proper es troben naturalment una al costat de l'altra en un o nodes veïns.
- Redueix el nombre de nodes de trànsit quan es baixa l'arbre durant una operació de cerca.
- Redueix el nombre de nodes de destinació llegits per a consultes d'interval, ja que cadascun d'ells ja conté un gran nombre de claus ordenades.
LMDB utilitza una variant de l'arbre B anomenada arbre B+ per emmagatzemar dades. El diagrama anterior mostra els tres tipus de nodes que conté:
- A la part superior hi ha l'arrel. No materialitza res més que el concepte de base de dades dins d'un repositori. Dins d'una única instància LMDB, podeu crear diverses bases de dades que comparteixin l'espai d'adreces virtuals assignat. Cadascun d'ells parteix de la seva pròpia arrel.
- Al nivell més baix es troben les fulles (fulla). Són ells i només ells els que contenen els parells clau-valor emmagatzemats a la base de dades. Per cert, aquesta és la peculiaritat dels arbres B+. Si un arbre B normal emmagatzema les parts de valor als nodes de tots els nivells, aleshores la variació B+ només es troba a la més baixa. Un cop solucionat aquest fet, a continuació anomenarem el subtipus de l'arbre utilitzat a LMDB simplement un arbre B.
- Entre l'arrel i les fulles, hi ha 0 o més nivells tècnics amb nodes de navegació (ramificació). La seva tasca és dividir el conjunt de claus ordenats entre les fulles.
Físicament, els nodes són blocs de memòria d'una longitud predeterminada. La seva mida és múltiple de la mida de les pàgines de memòria del sistema operatiu, de la qual hem parlat més amunt. L'estructura del node es mostra a continuació. La capçalera conté metainformació, la més òbvia de les quals, per exemple, és la suma de control. A continuació ve la informació sobre els desplaçaments, al llarg de les quals es troben les cel·les amb dades. El paper de les dades pot ser o bé les claus, si parlem de nodes de navegació, o parelles clau-valor senceres en el cas de les fulles. Podeu llegir més informació sobre l'estructura de les pàgines a l'obra. .
Després d'haver tractat el contingut intern dels nodes de la pàgina, representarem encara més l'arbre B LMDB d'una manera simplificada en la forma següent.
Les pàgines amb nodes es disposen seqüencialment al disc. Les pàgines amb un nombre més alt es troben al final del fitxer. L'anomenada meta pàgina (meta pàgina) conté informació sobre desplaçaments, que es pot utilitzar per trobar les arrels de tots els arbres. Quan s'obre un fitxer, LMDB escaneja el fitxer pàgina per pàgina des del final fins al principi a la recerca d'una meta pàgina vàlida i troba les bases de dades existents a través d'ella.
Ara, tenint una idea de l'estructura lògica i física de l'organització de les dades, podem procedir a considerar la tercera balena de LMDB. És amb la seva ajuda que totes les modificacions d'emmagatzematge es produeixen de manera transaccional i aïlladament entre si, donant a la base de dades en conjunt també la propietat multiversió.
3.3. Balena #3. còpia sobre escriptura
Algunes operacions de l'arbre B impliquen fer tota una sèrie de canvis als seus nodes. Un exemple és afegir una nova clau a un node que ja ha arribat a la seva capacitat màxima. En aquest cas, cal, en primer lloc, dividir el node en dos i, en segon lloc, afegir un enllaç al nou node fill separat del seu pare. Aquest procediment és potencialment molt perillós. Si per algun motiu (accident, tall de corrent, etc.) només es produeix una part dels canvis de la sèrie, aleshores l'arbre romandrà en un estat inconsistent.
Una solució tradicional per fer que una base de dades sigui tolerant a errors és afegir una estructura de dades addicional basada en disc, el registre de transaccions, també conegut com a registre d'escriptura anticipada (WAL), al costat de l'arbre B. És un fitxer, al final del qual, estrictament abans de la modificació del propi arbre B, s'escriu l'operació prevista. Així, si es detecta corrupció de dades durant l'autodiagnòstic, la base de dades consulta el registre per netejar-se.
LMDB ha escollit un mètode diferent com a mecanisme de tolerància a errors, que s'anomena còpia sobre escriptura. La seva essència és que en lloc d'actualitzar les dades d'una pàgina existent, primer les copia completament i fa totes les modificacions que ja estan a la còpia.
A més, perquè les dades actualitzades estiguin disponibles, cal canviar l'enllaç al node que s'ha actualitzat al node pare en relació amb aquest. Com que també s'ha de modificar per a això, també es precopia. El procés continua recursivament fins a l'arrel. Les dades de la meta pàgina són les últimes a canviar.
Si de sobte el procés es bloqueja durant el procediment d'actualització, no es crearà una meta pàgina nova o no s'escriurà al disc fins al final i la seva suma de comprovació serà incorrecta. En qualsevol d'aquests dos casos, les pàgines noves seran inaccessibles i les velles no es veuran afectades. Això elimina la necessitat que LMDB escrigui el registre per tal de mantenir la coherència de les dades. De fet, l'estructura d'emmagatzematge de dades al disc, descrita anteriorment, assumeix simultàniament la seva funció. L'absència d'un registre de transaccions explícit és una de les característiques de LMDB, que proporciona una alta velocitat de lectura de dades
La construcció resultant, anomenada arbre B només per afegir, proporciona naturalment aïllament de transaccions i multiversions. A LMDB, cada transacció oberta té associada una arrel d'arbre actualitzada. Mentre la transacció no s'hagi completat, les pàgines de l'arbre associades a aquesta mai no es canviaran ni es reutilitzaran per a noves versions de dades. Així, podeu treballar durant el temps que vulgueu exactament amb el conjunt de dades que era rellevant a la moment en què es va obrir la transacció, fins i tot si l'emmagatzematge continua actualitzat activament en aquest moment. Aquesta és l'essència de la multiversion, fent de LMDB una font de dades ideal per al nostre estimat UICollectionView. Després d'haver obert una transacció, no cal augmentar la petjada de memòria de l'aplicació, bombejant ràpidament les dades actuals a una estructura a la memòria, tenint por de quedar-se sense res. Aquesta característica distingeix LMDB del mateix SQLite, que no pot presumir d'un aïllament tan total. Havent obert dues operacions en aquesta darrera i eliminant un determinat registre dins d'una d'elles, ja no es podrà obtenir el mateix registre dins del segon restant.
L'altra cara de la moneda és el consum potencialment significativament més gran de memòria virtual. La diapositiva mostra com serà l'estructura de la base de dades si es modifica al mateix temps amb 3 transaccions de lectura obertes mirant diferents versions de la base de dades. Com que LMDB no pot reutilitzar nodes als quals es pot accedir des de les arrels associades a les transaccions reals, l'emmagatzematge no té més remei que assignar una altra quarta arrel a la memòria i clonar de nou les pàgines modificades a sota.
Aquí no serà superflu recordar la secció sobre fitxers assignats a memòria. Sembla que el consum addicional de memòria virtual no ens hauria de molestar gaire, ja que no contribueix a la petjada de memòria de l'aplicació. Tanmateix, al mateix temps, es va assenyalar que iOS és molt avar a l'hora d'assignar-lo i no podem proporcionar una regió LMDB d'1 terabyte en un servidor o escriptori des de l'espatlla del mestre i no pensar en aquesta característica. Quan sigui possible, hauríeu d'intentar que la vida útil de les transaccions sigui tan curta com sigui possible.
4. Dissenyar un esquema de dades a la part superior de l'API clau-valor
Comencem a analitzar l'API mirant les abstraccions bàsiques que ofereix LMDB: entorn i bases de dades, claus i valors, transaccions i cursors.
Una nota sobre les llistes de codi
Totes les funcions de l'API pública LMDB retornen el resultat del seu treball en forma de codi d'error, però en tots els llistats posteriors s'omet la seva comprovació per concisió. A la pràctica, hem utilitzat el nostre propi codi per interactuar amb el repositori. Embolcalls C++ , en què els errors es materialitzen com a excepcions de C++.
Com a forma més ràpida de connectar LMDB a un projecte iOS o macOS, ofereixo el meu CocoaPod .
4.1. Abstraccions bàsiques
Medi ambient
Estructura MDB_env és el dipòsit de l'estat intern de l'LMDB. Família de funcions prefixades mdb_env permet configurar algunes de les seves propietats. En el cas més senzill, la inicialització del motor es veu així.
mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512)
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);A l'aplicació Mail.ru Cloud, hem canviat els valors predeterminats només per a dos paràmetres.
El primer és la mida de l'espai d'adreces virtuals al qual està assignat el fitxer d'emmagatzematge. Malauradament, fins i tot en el mateix dispositiu, el valor específic pot variar significativament d'una execució a una altra. Per tenir en compte aquesta característica d'iOS, seleccionem la quantitat màxima d'emmagatzematge de forma dinàmica. A partir d'un valor determinat, es redueix successivament a la meitat fins a la funció mdb_env_open no retornarà un altre resultat que ENOMEM. En teoria, hi ha una manera oposada: primer assigneu un mínim de memòria al motor i després, quan es rebin errors. MDB_MAP_FULL, augmenta-ho. Tanmateix, és molt més espinós. El motiu és que el procediment per reasignar la memòria utilitzant la funció mdb_env_set_map_size invalida totes les entitats (cursors, transaccions, claus i valors) rebudes anteriorment del motor. Tenir en compte aquest gir dels esdeveniments al codi comportarà una complicació significativa. Si, tanmateix, la memòria virtual és molt estimada per a vostè, aquest pot ser un motiu per mirar la bifurcació que ha anat molt endavant. , on entre les característiques declarades hi ha "l'ajust automàtic de la mida de la base de dades sobre la marxa".
El segon paràmetre, el valor predeterminat del qual no ens convé, regula la mecànica per garantir la seguretat del fil. Malauradament, almenys a iOS 10, hi ha problemes amb el suport d'emmagatzematge local de fils. Per aquest motiu, a l'exemple anterior, el repositori s'obre amb la bandera MDB_NOTLS. A més, també requeria Embolcall C++ per tallar variables amb i en aquest atribut.
Bases de dades
La base de dades és una instància independent de l'arbre B del qual hem parlat anteriorment. La seva obertura es produeix dins d'una transacció, que en un principi pot semblar una mica estranya.
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);De fet, una transacció a LMDB és una entitat d'emmagatzematge, no una base de dades específica. Aquest concepte permet realitzar operacions atòmiques sobre entitats situades en diferents bases de dades. En teoria, això obre la possibilitat de modelar taules en forma de diferents bases de dades, però en un moment vaig anar a l'altre costat, descrit amb detall a continuació.
Claus i valors
Estructura MDB_val modela el concepte tant de clau com de valor. El repositori no té ni idea de la seva semàntica. Per a ella, una cosa diferent és només una matriu de bytes d'una mida determinada. La mida màxima de la clau és de 512 bytes.
typedef struct MDB_val {
size_t mv_size;
void *mv_data;
} MDB_val;La botiga utilitza un comparador per ordenar les claus en ordre ascendent. Si no el substituïu pel vostre, s'utilitzarà el predeterminat, que els ordena byte a byte per ordre lexicogràfic.
Transaccions
El dispositiu de transacció es descriu detalladament a , així que aquí repetiré les seves propietats principals en una breu línia:
- Suport per a totes les propietats bàsiques Paraules clau: atomicitat, consistència, aïllament i fiabilitat. No puc evitar assenyalar que pel que fa a la durabilitat a macOS i iOS, hi ha un error corregit a MDBX. Podeu llegir més a les seves .
- L'enfocament del multithreading es descriu mitjançant l'esquema "un escriptor / múltiples lectors". Els escriptors es bloquegen els uns als altres, però no els lectors. Els lectors no bloquegen els escriptors ni els uns als altres.
- Suport per a transaccions imbricades.
- Suport multiversió.
La multiversion a LMDB és tan bona que vull demostrar-ho en acció. El codi següent mostra que cada transacció funciona exactament amb la versió de la base de dades que era rellevant en el moment de la seva obertura, quedant completament aïllada de tots els canvis posteriors. Inicialitzar el repositori i afegir-hi un registre de prova no té cap interès, per la qual cosa aquests rituals es queden sota el spoiler.
Afegeix una entrada de prova
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);Opcionalment, recomano provar el mateix truc amb SQLite i veure què passa.
La multiversion aporta avantatges molt agradables a la vida d'un desenvolupador d'iOS. Amb aquesta propietat, podeu ajustar de manera fàcil i natural la taxa d'actualització de la font de dades per als formularis de pantalla en funció de les consideracions de l'experiència de l'usuari. Per exemple, prenem una característica de l'aplicació Mail.ru Cloud com la càrrega automàtica de contingut de la galeria multimèdia del sistema. Amb una bona connexió, el client pot afegir diverses fotos per segon al servidor. Si actualitzeu després de cada descàrrega UICollectionView amb contingut multimèdia al núvol de l'usuari, podeu oblidar uns 60 fps i un desplaçament suau durant aquest procés. Per evitar actualitzacions freqüents de la pantalla, heu de limitar d'alguna manera la taxa de canvi de dades a la base UICollectionViewDataSource.
Si la base de dades no admet multiversions i us permet treballar només amb l'estat actual actual, per crear una instantània de dades estable en el temps, haureu de copiar-la a una estructura de dades a la memòria o a una taula temporal. Qualsevol d'aquests enfocaments és molt car. En el cas de l'emmagatzematge en memòria, obtenim tant els costos de memòria causats per l'emmagatzematge d'objectes construïts com els costos de temps associats a transformacions ORM redundants. Pel que fa a la taula temporal, aquest és un plaer encara més car, que només té sentit en casos no trivials.
Multiversioning LMDB resol el problema de mantenir una font de dades estable d'una manera molt elegant. N'hi ha prou amb obrir una transacció i voilà: fins que la completem, es garanteix que el conjunt de dades s'arreglarà. La lògica de la seva taxa d'actualització està ara completament en mans de la capa de presentació, sense cap sobrecàrrega de recursos significatius.
Cursors
Els cursors proporcionen un mecanisme per a la iteració ordenada sobre parells clau-valor travessant un arbre B. Sense ells, seria impossible modelar eficaçment les taules de la base de dades, a la qual ara ens dirigim.
4.2. Modelatge de taula
La propietat d'ordenació de claus us permet construir una abstracció de nivell superior, com ara una taula a sobre d'abstraccions bàsiques. Considerem aquest procés a l'exemple de la taula principal del client del núvol, en què s'emmagatzema la informació sobre tots els fitxers i carpetes de l'usuari.
Esquema de taula
Un dels escenaris habituals per als quals s'ha d'afinar l'estructura d'una taula amb un arbre de carpetes és seleccionar tots els elements situats dins d'un directori determinat.Un bon model d'organització de dades per a consultes eficients d'aquest tipus és . Per implementar-lo a sobre de l'emmagatzematge del valor-clau, cal ordenar les claus dels fitxers i carpetes de manera que s'agrupin en funció de la pertinença al directori principal. A més, per mostrar el contingut del directori en la forma que conegui un usuari de Windows (primer les carpetes, després els fitxers, tots dos estan ordenats alfabèticament), cal incloure els camps addicionals corresponents a la clau.
La imatge següent mostra com, segons la tasca, pot semblar la representació de les claus com a matriu de bytes. Primer, es col·loquen els bytes amb l'identificador del directori pare (vermell), després amb el tipus (verd), i ja a la cua amb el nom (blau) En ser ordenats pel comparador LMDB predeterminat en ordre lexicogràfic, s'ordenen en la manera requerida. Travessar seqüencialment tecles amb el mateix prefix vermell ens proporciona els valors associats a elles en l'ordre en què s'han de mostrar a la interfície d'usuari (dreta), sense requerir cap postprocessament addicional.
Serialització de claus i valors
Hi ha molts mètodes per serialitzar objectes arreu del món. Com que no teníem cap altre requisit que no fos la velocitat, vam triar el més ràpid possible per a nosaltres mateixos: un abocament de memòria ocupat per una instància de l'estructura del llenguatge C. Per tant, la clau d'un element de directori es pot modelar amb l'estructura següent NodeKey.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Guardar NodeKey en necessitat d'emmagatzematge en objecte MDB_val col·loca el punter a les dades a l'adreça de l'inici de l'estructura i calcula la seva mida amb la funció sizeof.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = sizeof(NodeKey),
.mv_data = (void *)key
};
}En el primer capítol sobre els criteris de selecció de bases de dades, vaig esmentar la minimització de les assignacions dinàmiques com a part de les operacions CRUD com un factor de selecció important. Codi de funció serialize mostra com, en el cas de LMDB, es poden evitar completament quan s'insereixen nous registres a la base de dades. La matriu de bytes entrants del servidor es transforma primer en estructures de pila i després s'aboquen trivialment a l'emmagatzematge. Atès que tampoc hi ha assignacions dinàmiques dins de LMDB, podeu obtenir una situació fantàstica segons els estàndards d'iOS: feu servir només memòria de pila per treballar amb dades des de la xarxa fins al disc!
Ordenació de claus amb un comparador binari
La relació d'ordre clau ve donada per una funció especial anomenada comparador. Com que el motor no sap res de la semàntica dels bytes que contenen, el comparador predeterminat no té més remei que disposar les claus per ordre lexicogràfic, recorrent a la seva comparació byte a byte. Usar-lo per organitzar estructures és semblant a afaitar-se amb una destral de tallar. Tanmateix, en casos senzills, trobo que aquest mètode és acceptable. L'alternativa es descriu a continuació, però aquí notaré un parell de rasclets escampats pel camí.
El primer que cal tenir en compte és la representació de memòria dels tipus de dades primitius. Així, a tots els dispositius Apple, les variables senceres s'emmagatzemen en el format . Això vol dir que el byte menys significatiu estarà a l'esquerra i no podreu ordenar els nombres enters utilitzant la seva comparació byte a byte. Per exemple, si intenteu fer-ho amb un conjunt de nombres del 0 al 511, obtindreu el resultat següent.
// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)Per resoldre aquest problema, els nombres enters s'han d'emmagatzemar a la clau en un format adequat per al comparador de bytes. Les funcions des de la família ajudaran a dur a terme la transformació necessària. hton* (en particular htons per a números de doble byte de l'exemple).
El format per representar cadenes a la programació és, com sabeu, un tot . Si la semàntica de les cadenes, així com la codificació utilitzada per representar-les a la memòria, suggereix que hi pot haver més d'un byte per caràcter, és millor abandonar immediatament la idea d'utilitzar un comparador predeterminat.
La segona cosa a tenir en compte és compilador de camps struct. A causa d'ells, es poden formar bytes amb valors d'escombraries a la memòria entre camps, cosa que, per descomptat, trenca l'ordenació de bytes. Per eliminar les escombraries, heu de declarar els camps en un ordre estrictament definit, tenint en compte les regles d'alineació, o bé utilitzar l'atribut a la declaració d'estructura. packed.
Ordenació de claus per un comparador extern
La lògica de comparació de claus pot resultar massa complexa per a un comparador binari. Un dels molts motius és la presència de camps tècnics dins de les estructures. Il·lustraré la seva aparició amb l'exemple d'una clau que ja ens coneixem per a un element de directori.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Per tota la seva senzillesa, en la gran majoria dels casos consumeix massa memòria. La memòria intermèdia de títol és de 256 bytes, encara que, de mitjana, els noms de fitxers i carpetes rarament superen els 20-30 caràcters.
Una de les tècniques estàndard per optimitzar la mida d'un registre és retallar-lo perquè s'ajusti a la seva mida real. La seva essència és que els continguts de tots els camps de longitud variable s'emmagatzemen en una memòria intermèdia al final de l'estructura i les seves longituds s'emmagatzemen en variables separades. D'acord amb aquest enfocament, la clau NodeKey es transforma de la següent manera.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;A més, durant la serialització, no s'especifica com a mida de dades sizeof tota l'estructura i la mida de tots els camps és de longitud fixa més la mida de la part del buffer realment utilitzada.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
.mv_data = (void *)key
};
}Com a resultat de la refactorització, vam aconseguir un important estalvi en l'espai que ocupaven les claus. Tanmateix, per l'àmbit tècnic nameLength, el comparador binari predeterminat ja no és adequat per a la comparació de claus. Si no el substituïm pel nostre, aleshores la longitud del nom serà un factor més prioritari en l'ordenació que el nom en si.
LMDB permet que cada base de dades tingui la seva pròpia funció de comparació de claus. Això es fa mitjançant la funció mdb_set_compare estrictament abans d'obrir. Per raons òbvies, una base de dades no es pot canviar al llarg de la seva vida útil. A l'entrada, el comparador rep dues claus en format binari, i a la sortida retorna el resultat de la comparació: menor que (-1), major que (1) o igual (0). Pseudocodi per NodeKey sembla així.
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 // ...
}Sempre que totes les claus de la base de dades siguin del mateix tipus, és legal emetre incondicionalment la seva representació de bytes al tipus de l'estructura de l'aplicació de la clau. Hi ha un matís aquí, però es discutirà una mica més avall a la subsecció "Lectura de registres".
Serialització de valors
Amb les claus dels registres emmagatzemats, LMDB treballa de manera extremadament intensa. Es comparen entre si en el marc de qualsevol operació d'aplicació i el rendiment de tota la solució depèn de la velocitat del comparador. En un món ideal, el comparador binari predeterminat hauria de ser suficient per comparar les claus, però si realment haguéssiu d'utilitzar les vostres pròpies, el procediment per deserialitzar les claus hauria de ser el més ràpid possible.
La base de dades no està especialment interessada en la part Valor del registre (valor). La seva conversió d'una representació de bytes a un objecte només es produeix quan el codi de l'aplicació ja ho requereix, per exemple, per mostrar-lo a la pantalla. Com que això passa relativament poques vegades, els requisits per a la velocitat d'aquest procediment no són tan crítics, i en la seva implementació som molt més lliures de centrar-nos en la comoditat. Per exemple, per serialitzar metadades sobre fitxers que encara no s'han descarregat, fem servir NSKeyedArchiver.
NSData *data = serialize(object);
MDB_val value = {
.mv_size = data.length,
.mv_data = (void *)data.bytes
};Tanmateix, hi ha moments en què el rendiment importa. Per exemple, quan desem metainformació sobre l'estructura de fitxers del núvol de l'usuari, utilitzem el mateix bolcat de memòria d'objectes. El més destacat de la tasca de generar la seva representació serialitzada és el fet que els elements d'un directori estan modelats per una jerarquia de classes.
Per a la seva implementació en el llenguatge C, els camps específics dels hereus es treuen en estructures separades, i la seva connexió amb la base s'especifica mitjançant un camp de tipus unió. El contingut real de la unió s'especifica mitjançant l'atribut tècnic tipus.
typedef struct NodeValue {
EntityId localId;
EntityType type;
union {
FileInfo file;
DirectoryInfo directory;
} info;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeValue;Afegir i actualitzar entrades
La clau i el valor serialitzats es poden afegir a la botiga. Per a això s'utilitza la funció mdb_put.
// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);En l'etapa de configuració, es pot permetre o prohibir al repositori emmagatzemar diversos registres amb la mateixa clau. Si la duplicació de claus està prohibida, en inserir un registre, podeu determinar si es permet o no actualitzar un registre ja existent. Si el desgast només es pot produir com a resultat d'un error al codi, podeu assegurar-vos-hi especificant la bandera NOOVERWRITE.
Registres de lectura
La funció per llegir registres a LMDB és mdb_get. Si el parell clau-valor està representat per estructures prèviament abocades, aquest procediment té aquest aspecte.
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 llista presentada mostra com la serialització mitjançant un abocament d'estructures us permet desfer-vos de les assignacions dinàmiques no només en escriure, sinó també en llegir dades. Derivat de la funció mdb_get el punter mira exactament a l'adreça de memòria virtual on la base de dades emmagatzema la representació en bytes de l'objecte. De fet, obtenim una mena d'ORM, gairebé gratuïta, que proporciona una velocitat de lectura de dades molt alta. Amb tota la bellesa de l'enfocament, cal recordar diverses característiques associades.
- Per a una transacció només de lectura, es garanteix que un punter a una estructura de valor només romandrà vàlid fins que es tanqui la transacció. Com s'ha assenyalat anteriorment, les pàgines de l'arbre B on resideix l'objecte, gràcies al principi de còpia sobre escriptura, romanen sense canvis sempre que almenys una transacció hi faci referència. Al mateix temps, tan bon punt es completi l'última transacció associada a ells, les pàgines es podran reutilitzar per a noves dades. Si és necessari que els objectes sobrevisquin a la transacció que els va crear, encara s'han de copiar.
- Per a una transacció de reescriptura, el punter a l'estructura-valor resultant serà vàlid només fins al primer procediment de modificació (escriptura o eliminació de dades).
- Tot i que l'estructura
NodeValueno complet, sinó retallat (vegeu la subsecció "Ordenar claus per un comparador extern"), mitjançant el punter, podeu accedir fàcilment als seus camps. El més important és no desreferenciar-lo! - En cap cas es pot modificar l'estructura mitjançant el punter rebut. Tots els canvis s'han de fer només mitjançant el mètode
mdb_put. Tanmateix, amb totes les ganes de fer-ho, no funcionarà, ja que l'àrea de memòria on es troba aquesta estructura està mapejada en mode de només lectura. - Reassigneu un fitxer a l'espai d'adreces d'un procés per, per exemple, augmentar la mida màxima d'emmagatzematge mitjançant la funció
mdb_env_set_map_sizeinvalida completament totes les transaccions i les entitats relacionades en general i els punters per llegir objectes en particular.
Finalment, una característica més és tan insidiosa que la revelació de la seva essència no encaixa només en un punt més. En el capítol sobre l'arbre B, vaig donar un diagrama de l'organització de les seves pàgines a la memòria. D'això se'n dedueix que l'adreça de l'inici del buffer amb dades serialitzades pot ser absolutament arbitrària. Per això, el punter a ells, obtingut a l'estructura MDB_val i llançar a un punter a una estructura generalment no està alineat. Al mateix temps, les arquitectures d'alguns xips (en el cas d'iOS, això és armv7) requereixen que l'adreça de qualsevol dada sigui un múltiple de la mida d'una paraula màquina, o, en altres paraules, el bitness del sistema. (per a armv7, això és de 32 bits). En altres paraules, una operació com *(int *foo)0x800002 sobre ells s'equipara a escapar i condueix a l'execució amb un veredicte EXC_ARM_DA_ALIGN. Hi ha dues maneres d'evitar un destí tan trist.
El primer és copiar prèviament les dades en una estructura alineada coneguda. Per exemple, en un comparador personalitzat, això es reflectirà de la següent manera.
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 // ...
}Una forma alternativa és notificar al compilador amb antelació que les estructures amb una clau i un valor poden no estar alineades mitjançant un atribut. aligned(1). A ARM pot tenir el mateix efecte i utilitzant l'atribut empaquetat. Tenint en compte que també contribueix a l'optimització de l'espai que ocupa l'estructura, aquest mètode em sembla preferible, tot i que augmentar el cost de les operacions d'accés a les dades.
typedef struct __attribute__((packed)) NodeKey {
uint8_t parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Consultes d'interval
Per iterar sobre un grup de registres, LMDB proporciona una abstracció del cursor. Vegem com treballar-hi utilitzant l'exemple d'una taula amb metadades del núvol d'usuaris que ja ens coneixen.
Com a part de mostrar una llista de fitxers en un directori, heu de trobar totes les claus amb les quals s'associen els fitxers i carpetes fills. En els subapartats anteriors, hem ordenat les claus NodeKey de manera que primer s'ordenen per l'identificador del seu directori principal. Així, tècnicament, la tasca d'obtenir el contingut d'una carpeta es redueix a situar el cursor al límit superior d'un grup de claus amb un prefix donat, seguit d'iteració fins al límit inferior.
Podeu trobar el límit superior "al front" mitjançant la cerca seqüencial. Per fer-ho, el cursor es col·loca al principi de tota la llista de claus de la base de dades i després s'incrementa fins que la clau amb l'identificador del directori pare apareix a sota. Aquest enfocament té 2 inconvenients evidents:
- La complexitat lineal de la cerca, encara que, com sabeu, en arbres en general i en arbre B en particular, es pot fer en temps logarítmic.
- En va, totes les pàgines que precedeixen a la desitjada s'eleven del fitxer a la memòria principal, que és extremadament cara.
Afortunadament, l'API LMDB proporciona una manera eficient de posicionar inicialment el cursor. Per fer-ho, cal formar una clau el valor de la qual se sap que és inferior o igual a la clau situada al límit superior de l'interval. Per exemple, en relació a la llista de la figura anterior, podem fer una clau en què el camp parentId serà igual a 2, i tota la resta s'omple de zeros. Aquesta clau parcialment plena s'alimenta a l'entrada de la funció mdb_cursor_get indicant el funcionament 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);Si es troba el límit superior del grup de claus, iterem sobre ell fins que ens trobem o la clau amb una altra. parentId, o les claus no s'esgotaran gens.
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 groupEl que és bo, com a part de la iteració amb mdb_cursor_get, obtenim no només la clau, sinó també el valor. Si, per complir les condicions de selecció, cal comprovar, entre altres coses, els camps de la part de valor del registre, llavors són bastant accessibles per ells mateixos sense gestos addicionals.
4.3. Modelització de relacions entre taules
Fins ara, hem aconseguit considerar tots els aspectes del disseny i el treball amb una base de dades d'una sola taula. Podem dir que una taula és un conjunt de registres ordenats format per parells clau-valor del mateix tipus. Si mostreu una clau com a rectangle i el seu valor associat com un quadre, obtindreu un diagrama visual de la base de dades.
â € <
Tanmateix, a la vida real, poques vegades és possible sobreposar-se amb tan poca sang. Sovint en una base de dades es requereix, en primer lloc, tenir diverses taules i, en segon lloc, realitzar-hi seleccions en un ordre diferent de la clau primària. Aquest darrer apartat està dedicat a les qüestions de la seva creació i interconnexió.
Taules d'índex
L'aplicació al núvol té una secció "Galeria". Mostra contingut multimèdia de tot el núvol, ordenat per data. Per a la implementació òptima d'aquesta selecció, al costat de la taula principal, n'heu de crear una altra amb un nou tipus de claus. Contindran un camp amb la data de creació del fitxer, que actuarà com a criteri d'ordenació principal. Com que les claus noves fan referència a les mateixes dades que les claus de la taula subjacent, s'anomenen claus d'índex. Es destaquen en taronja a la imatge següent.
Per tal de separar les claus de diferents taules entre si dins de la mateixa base de dades, s'ha afegit un tableId de camp tècnic addicional a totes elles. En fer que sigui la màxima prioritat per a l'ordenació, agruparem les claus primer per taules, i ja dins de les taules, segons les nostres pròpies regles.
La clau d'índex fa referència a les mateixes dades que la clau primària. La implementació senzilla d'aquesta propietat associant-hi una còpia de la part de valor de la clau primària és subòptima des de diversos punts de vista alhora:
- Des del punt de vista d'espai ocupat, les metadades poden ser força riques.
- Des del punt de vista del rendiment, ja que en actualitzar les metadades del node, caldrà sobreescriure dues claus.
- Des del punt de vista del suport de codi, després de tot, si ens oblidem d'actualitzar les dades d'una de les claus, obtindrem un subtil error d'incoherència de dades a l'emmagatzematge.
A continuació, analitzarem com eliminar aquestes mancances.
Organització de les relacions entre taules
El patró és molt adequat per enllaçar una taula d'índex amb la principal "clau com a valor". Com el seu nom indica, la part del valor del registre d'índex és una còpia del valor de la clau primària. Aquest enfocament elimina tots els desavantatges enumerats anteriorment associats a l'emmagatzematge d'una còpia de la part de valor del registre primari. L'única tarifa és que per obtenir el valor mitjançant la clau d'índex, heu de fer 2 consultes a la base de dades en lloc d'una. Esquemàticament, l'esquema de la base de dades resultant és el següent.
Un altre patró per organitzar les relacions entre taules és "clau redundant". La seva essència és afegir atributs addicionals a la clau, que no són necessaris per ordenar, sinó per recrear la clau associada. No obstant això, hi ha exemples reals del seu ús a l'aplicació Mail.ru Cloud, per evitar una immersió profunda en el context de marcs iOS específics, donaré un exemple fictici, però més entenedor.
Els clients mòbils al núvol tenen una pàgina que mostra tots els fitxers i carpetes que l'usuari ha compartit amb altres persones. Com que hi ha relativament pocs fitxers d'aquest tipus, i hi ha molta informació específica sobre la publicitat associada a ells (a qui es concedeix l'accés, amb quins drets, etc.), no serà racional carregar-los amb la part de valor de l'entrada a la taula principal. Tanmateix, si voleu mostrar aquests fitxers fora de línia, encara haureu d'emmagatzemar-los en algun lloc. Una solució natural és crear una taula separada. Al diagrama següent, la seva clau té el prefix "P" i el marcador de posició "propname" es pot substituir pel valor més específic "informació pública".
Totes les metadades úniques, pel bé de les quals es va crear la taula nova, es mouen a la part de valor del registre. Al mateix temps, no vull duplicar les dades sobre fitxers i carpetes que ja estan emmagatzemats a la taula principal. En canvi, s'afegeixen dades redundants a la clau "P" en forma dels camps "ID de node" i "marca de temps". Gràcies a ells, podeu construir una clau d'índex, mitjançant la qual podeu obtenir la clau primària, mitjançant la qual, finalment, podeu obtenir les metadades del node.
Conclusió
Valorem positivament els resultats de la implementació de LMDB. Després d'això, el nombre d'aplicacions congelades va disminuir un 30%.
Els resultats del treball realitzat han trobat resposta fora de l'equip d'iOS. Actualment, una de les seccions principals "Fitxers" de l'aplicació d'Android també ha passat a utilitzar LMDB, i altres parts estan en camí. El llenguatge C, en el qual s'implementa l'emmagatzematge del valor-clau, va ser una bona ajuda per tal que inicialment l'aplicació s'unís al seu voltant multiplataforma en el llenguatge C++. Per a una connexió perfecta de la biblioteca C ++ resultant amb el codi de plataforma a Objective-C i Kotlin, es va utilitzar un generador de codi. de Dropbox, però això és una altra història.
Font: www.habr.com