No outono de 2019, ocorreu un evento moi esperado no equipo de iOS de Mail.ru Cloud. A base de datos principal para o almacenamento persistente do estado da aplicación volveuse moi exótica para o mundo móbil Base de datos mapeada con memoria Lightning (LMDB). Debaixo do corte ofrecémosche unha revisión detallada do mesmo en catro partes. En primeiro lugar, imos falar sobre as razóns para unha elección tan non trivial e difícil. Despois pasaremos a considerar os tres piares no corazón da arquitectura LMDB: ficheiros mapeados en memoria, árbore B+, enfoque de copia en escritura para implementar transaccionalidade e multiversión. Finalmente, para a sobremesa - a parte práctica. Nela veremos como deseñar e implementar un esquema de base de datos con varias táboas, incluída unha de índice, enriba da API de valor clave de baixo nivel.

Contido

1. Motivación para a implantación
2. Posicionamento LMDB
3. Tres piares da LMDB
   3.1. Balea #1. Ficheiros mapeados na memoria
   3.2. Balea #2. Árbore B+
   3.3. Balea #3. Copiar sobre escribir
4. Deseño dun esquema de datos encima da API de clave-valor
   4.1. Abstraccións básicas
   4.2. Modelado de táboas
   4.3. Modelización de relacións entre táboas

1. Motivación para a implantación

Un ano en 2015, tomámonos a molestia de medir a frecuencia con que se atrasa a interface da nosa aplicación. Fixémolo por un motivo. Recibimos queixas máis frecuentes de que en ocasións a aplicación deixa de responder ás accións dos usuarios: non se poden pulsar botóns, non se desprazan as listas, etc. Sobre a mecánica das medidas contou en AvitoTech, así que aquí dou só a orde dos números.

Os resultados das medicións convertéronse nunha ducha fría para nós. Resultou que hai moitos máis problemas causados ​​polas conxelacións que calquera outro. Se antes de darse conta deste feito o principal indicador técnico de calidade era libre de accidentes, entón despois do foco desprazado en freeze free.

Ter construído panel de control con conxelación e despois de gastar cuantitativo и calidade análise das súas razóns, o principal inimigo quedou claro - pesada lóxica empresarial executada no fío principal da aplicación. A reacción natural a esta desgraza foi un desexo ardente de empurralo nos fluxos de traballo. Para solucionar este problema de forma sistemática, recorremos a unha arquitectura multi-fíos baseada en actores lixeiros. Dediqueino á súa adaptación para o mundo iOS dous fíos en Twitter colectivo e artigo sobre Habré. Como parte da narrativa actual, quero facer fincapé naqueles aspectos da decisión que influíron na elección da base de datos.​

O modelo de actor da organización do sistema asume que o multithreading convértese na súa segunda esencia. Os obxectos modelados nel gústalles cruzar os límites das correntes. E non fan isto ás veces e aquí e alí, senón case constantemente e en todas partes

A base de datos é un dos compoñentes fundamentais do diagrama presentado. A súa tarefa principal é implementar o macropatrón Base de datos compartida. Se no mundo empresarial úsase para organizar a sincronización de datos entre servizos, entón no caso da arquitectura de actores - datos entre fíos. Así, necesitábamos unha base de datos que non causase nin sequera as mínimas dificultades ao traballar con ela nun ambiente multiproceso. En particular, isto significa que os obxectos obtidos del deben ser polo menos seguros para fíos e, idealmente, completamente non mutables. Como sabes, este último pódese usar simultaneamente desde varios fíos sen recorrer a ningún bloqueo, o que ten un efecto beneficioso no rendemento.

O segundo factor significativo que influíu na elección da base de datos foi a nosa API na nube. Inspirouse no enfoque de sincronización adoptado por git. Como el, apuntámonos API offline-primer, que parece máis que apropiado para os clientes na nube. Supoñíase que só bombearían o estado completo da nube unha vez, e despois a sincronización na inmensa maioría dos casos produciríase mediante a implementación de cambios. Por desgraza, esta oportunidade aínda está só na zona teórica e os clientes non aprenderon a traballar con parches na práctica. Hai unha serie de razóns obxectivas para iso, que, para non demorar a introdución, deixaremos corchetes. Agora, o que interesa moito máis son as conclusións instrutivas da lección sobre o que ocorre cando unha API di "A" e o seu consumidor non di "B".

Entón, se imaxinas git, que ao executar un comando pull, en lugar de aplicar parches a unha instantánea local, compara o seu estado completo co estado completo do servidor, terás unha idea bastante precisa de como se produce a sincronización na nube. clientes. É doado adiviñar que para implementalo, cómpre asignar dúas árbores DOM na memoria con metainformación sobre todos os ficheiros locais e servidores. Resulta que se un usuario almacena 500 mil ficheiros na nube, entón para sincronizalo é necesario recrear e destruír dúas árbores con 1 millón de nós. Pero cada nodo é un agregado que contén unha gráfica de subobxectos. A este respecto, agardaban os resultados do perfil. Resultou que aínda sen ter en conta o algoritmo de fusión, o propio procedemento de crear e posteriormente destruír un gran número de pequenos obxectos custa un céntimo.A situación vese agravada polo feito de que a operación de sincronización básica está incluída nun gran número. de scripts de usuario. Como resultado, fixamos o segundo criterio importante na elección dunha base de datos: a capacidade de implementar operacións CRUD sen asignación dinámica de obxectos.

Outros requisitos son máis tradicionais e toda a súa lista é a seguinte.

1. Seguridade do fío.
2. Multiprocesamento. Ditado polo desexo de usar a mesma instancia de base de datos para sincronizar o estado non só entre fíos, senón tamén entre a aplicación principal e as extensións de iOS.
3. A capacidade de representar entidades almacenadas como obxectos non mutables
4. Non hai asignacións dinámicas dentro das operacións CRUD.
5. Soporte de transaccións para propiedades básicas ÁCIDO: atomicidade, consistencia, illamento e fiabilidade.
6. Velocidade nos casos máis populares.

Con este conxunto de requisitos, SQLite foi e segue sendo unha boa opción. Porén, como parte do estudo das alternativas, atopeime cun libro "Introducción a LevelDB". Baixo o seu liderado, escribiuse un punto de referencia que comparaba a velocidade de traballo con diferentes bases de datos en escenarios de nube reais. O resultado superou as nosas expectativas máis salvaxes. Nos casos máis populares - conseguir un cursor nunha lista ordenada de todos os ficheiros e unha lista ordenada de todos os ficheiros para un determinado directorio - LMDB resultou ser 10 veces máis rápido que SQLite. A elección fíxose evidente.

2. Posicionamento LMDB

LMDB é unha biblioteca moi pequena (só 10K filas) que implementa a capa fundamental máis baixa de bases de datos: o almacenamento.

O diagrama anterior mostra que comparar LMDB con SQLite, que tamén implementa niveis máis altos, xeralmente non é máis correcto que SQLite con Core Data. Sería máis xusto citar os mesmos motores de almacenamento que competidores iguais: BerkeleyDB, LevelDB, Sophia, RocksDB, etc. Incluso hai desenvolvementos nos que LMDB actúa como un compoñente do motor de almacenamento para SQLite. O primeiro experimento deste tipo foi en 2012 gastado por LMDB Howard Chu. Descubrimentos resultou tan intrigante que a súa iniciativa foi recollida polos entusiastas da OSS e atopou a súa continuación na persoa. LumoSQL. En xaneiro de 2020, o autor deste proxecto foi Den Shearer presentado en LinuxConfAu.

LMDB úsase principalmente como motor para bases de datos de aplicacións. A biblioteca debe a súa aparencia aos desenvolvedores OpenLDAP, que estaban moi descontentos con BerkeleyDB como base para o seu proxecto. Partindo dunha modesta biblioteca btree, Howard Chu foi capaz de crear unha das alternativas máis populares do noso tempo. Dedicou a súa reportaxe moi chula a esta historia, así como á estrutura interna de LMDB. "A base de datos mapeada con memoria Lightning". Un bo exemplo de conquista dunha instalación de almacenamento foi compartido por Leonid Yuryev (alias yleo) de Positive Technologies no seu informe en Highload 2015 "O motor LMDB é un campión especial". Nela, fala de LMDB no contexto dunha tarefa semellante de implementación de ReOpenLDAP, e LevelDB xa foi obxecto de críticas comparativas. Como resultado da implementación, Positive Technologies incluso tivo unha bifurcación en desenvolvemento activo MDBX con características, optimizacións e moi saborosas correccións de erros.

LMDB úsase a miúdo como almacenamento tal e como está. Por exemplo, o navegador Mozilla Firefox escolleu para unha serie de necesidades e, a partir da versión 9, Xcode preferido o seu SQLite para almacenar índices.

O motor tamén deixou a súa marca no mundo do desenvolvemento móbil. Rastros do seu uso poden ser atopar no cliente iOS para Telegram. LinkedIn foi aínda máis alá e elixiu LMDB como o almacenamento predeterminado para o seu marco de almacenamento en caché de datos propio Rocket Data, sobre o que dixo no seu artigo de 2016.

LMDB está loitando con éxito por un lugar ao sol no nicho que BerkeleyDB deixou baixo o control de Oracle. A biblioteca é querida pola súa velocidade e fiabilidade, mesmo en comparación cos seus compañeiros. Como sabedes, non hai xantares gratuítos, e gustaríame subliñar o compromiso que terás que afrontar ao elixir entre LMDB e SQLite. O diagrama anterior demostra claramente como se consegue aumentar a velocidade. En primeiro lugar, non pagamos por capas adicionais de abstracción ademais do almacenamento en disco. Está claro que unha boa arquitectura aínda non pode prescindir deles, e inevitablemente aparecerán no código da aplicación, pero serán moito máis sutís. Non conterán funcións que non sexan requiridas por unha aplicación específica, por exemplo, soporte para consultas na linguaxe SQL. En segundo lugar, faise posible implementar de forma óptima o mapeamento das operacións das aplicacións nas solicitudes de almacenamento en disco. Se SQLite no meu traballo baséase nas necesidades estatísticas medias dunha aplicación media, entón vostede, como desenvolvedor de aplicacións, coñece ben os principais escenarios de carga de traballo. Para unha solución máis produtiva, terá que pagar un prezo máis elevado tanto polo desenvolvemento da solución inicial como polo seu posterior soporte.

3. Tres piares da LMDB

Unha vez mirado a LMDB dende a vista de paxaro, era hora de afondar. Os seguintes tres apartados dedicaranse a unha análise dos principais piares nos que se apoia a arquitectura de almacenamento:

1. Ficheiros mapeados en memoria como mecanismo para traballar co disco e sincronizar estruturas de datos internas.
2. Árbore B+ como organización da estrutura dos datos almacenados.
3. Copy-on-write como enfoque para proporcionar propiedades de transacción ACID e multiversión.

3.1. Balea #1. Ficheiros mapeados en memoria

Os ficheiros mapeados na memoria son un elemento arquitectónico tan importante que incluso aparecen no nome do repositorio. Os problemas de almacenamento en caché e sincronización do acceso á información almacenada déixanse totalmente ao sistema operativo. LMDB non contén ningún caché dentro de si. Esta é unha decisión consciente do autor, xa que ler datos directamente dos ficheiros mapeados permítelle cortar moitas curvas na implementación do motor. Abaixo está unha lista lonxe de ser completa dalgúns deles.

1. Manter a coherencia dos datos no almacenamento cando se traballa con el desde varios procesos pasa a ser responsabilidade do sistema operativo. Na seguinte sección, esta mecánica é discutida en detalle e con imaxes.
2. A ausencia de cachés elimina completamente a LMDB da sobrecarga asociada ás asignacións dinámicas. Ler datos na práctica significa poñer un punteiro ao enderezo correcto na memoria virtual e nada máis. Parece ciencia ficción, pero no código fonte de almacenamento todas as chamadas a calloc concéntranse na función de configuración de almacenamento.
3. A ausencia de cachés tamén significa a ausencia de bloqueos asociados á sincronización do seu acceso. Os lectores, dos que pode haber un número arbitrario de lectores ao mesmo tempo, non atopan nin un só mutex no seu camiño cara aos datos. Debido a isto, a velocidade de lectura ten unha escalabilidade lineal ideal en función do número de CPU. En LMDB, só se sincronizan as operacións de modificación. Só pode haber un escritor á vez.
4. Un mínimo de almacenamento en caché e lóxica de sincronización elimina o tipo extremadamente complexo de erros asociados ao traballo nun ambiente multiproceso. Houbo dous estudos de bases de datos interesantes na conferencia Usenix OSDI 2014: "Non todos os sistemas de ficheiros se crean iguais: sobre a complexidade de crear aplicacións consistentes en fallos" и "Torturando bases de datos para divertirse e lucrar". Deles pode obter información tanto sobre a fiabilidade sen precedentes de LMDB como sobre a implementación case impecable das propiedades de transacción ACID, que é superior á de SQLite.
5. O minimalismo de LMDB permite que a representación da máquina do seu código estea completamente localizada na caché L1 do procesador coas características de velocidade conseguintes.

Desafortunadamente, en iOS, con ficheiros mapeados en memoria, non todo está tan sen nubes como nos gustaría. Para falar máis conscientemente das deficiencias asociadas a elas, é necesario lembrar os principios xerais de implementación deste mecanismo nos sistemas operativos.

Información xeral sobre ficheiros mapeados en memoria

Con cada aplicación que se executa, o sistema operativo asocia unha entidade chamada proceso. A cada proceso asígnaselle un rango contiguo de enderezos nos que coloca todo o que precisa para operar. Nos enderezos máis baixos hai seccións con código e datos e recursos codificados. A continuación vén un bloque crecente de espazo de enderezos dinámicos, moi coñecido por nós baixo o nome de montón. Contén os enderezos das entidades que aparecen durante o funcionamento do programa. Na parte superior está a área de memoria utilizada pola pila de aplicacións. Crece ou contrae; é dicir, o seu tamaño tamén ten un carácter dinámico. Para evitar que a pila e o montón se empurran e interfiran entre si, están situados en diferentes extremos do espazo de enderezos. Hai un burato entre as dúas seccións dinámicas na parte superior e na parte inferior. O sistema operativo usa enderezos nesta sección central para asociar unha variedade de entidades co proceso. En particular, pode asociar un determinado conxunto continuo de enderezos cun ficheiro do disco. Este ficheiro chámase asignado de memoria.​

O espazo de enderezos asignado ao proceso é enorme. Teoricamente, o número de enderezos está limitado só polo tamaño do punteiro, que está determinado pola capacidade de bits do sistema. Se a memoria física se asignase a ela de 1 a 1, entón o primeiro proceso devoraría toda a RAM e non se falaría de ningunha tarefa multitarea.

Non obstante, pola nosa experiencia sabemos que os sistemas operativos modernos poden executar simultáneamente tantos procesos como se desexe. Isto é posible debido a que só asignan moita memoria aos procesos en papel, pero en realidade cargan na memoria física principal só a parte que se demanda aquí e agora. Polo tanto, a memoria asociada a un proceso chámase virtual.

O sistema operativo organiza a memoria virtual e física en páxinas dun tamaño determinado. Tan pronto como se demanda unha determinada páxina de memoria virtual, o sistema operativo cárgaa na memoria física e as combina nunha táboa especial. Se non hai ranuras libres, cópiase no disco unha das páxinas cargadas previamente e a que se demanda ocupa o seu lugar. Este procedemento, ao que volveremos en breve, chámase intercambio. A seguinte figura ilustra o proceso descrito. Nela cargouse a páxina A co enderezo 0 e colocouse na páxina da memoria principal co enderezo 4. Este feito reflectiuse na táboa de correspondencia da cela número 0.​

A historia é exactamente a mesma cos ficheiros asignados á memoria. Loxicamente, supostamente están localizados de forma continua e integramente no espazo de enderezo virtual. Non obstante, ingresan na memoria física páxina por páxina e só previa solicitude. A modificación destas páxinas está sincronizada co ficheiro no disco. Deste xeito, pode realizar E/S de ficheiros simplemente traballando con bytes na memoria; todos os cambios serán transferidos automaticamente polo núcleo do sistema operativo ao ficheiro fonte.
​
A imaxe de abaixo demostra como LMDB sincroniza o seu estado cando traballa coa base de datos desde diferentes procesos. Ao mapear a memoria virtual de diferentes procesos ao mesmo ficheiro, de facto obrigamos ao sistema operativo a sincronizar de forma transitiva certos bloques dos seus espazos de enderezos entre si, onde mira LMDB.
​

Un matiz importante é que LMDB, por defecto, modifica o ficheiro de datos mediante o mecanismo de chamada do sistema de escritura e mostra o propio ficheiro en modo de só lectura. Este enfoque ten dúas consecuencias importantes.

A primeira consecuencia é común a todos os sistemas operativos. A súa esencia é engadir protección contra danos non intencionados á base de datos por código incorrecto. Como sabes, as instrucións executables dun proceso son gratuítas para acceder aos datos desde calquera lugar do seu espazo de enderezos. Ao mesmo tempo, como acabamos de lembrar, mostrar un ficheiro en modo lectura-escritura significa que calquera instrución tamén pode modificalo. Se o fai por erro, tentando, por exemplo, sobrescribir un elemento da matriz nun índice inexistente, pode cambiar accidentalmente o ficheiro asignado a este enderezo, o que provocará a corrupción da base de datos. Se o ficheiro se amosa en modo de só lectura, o intento de cambiar o espazo de enderezos correspondente provocará unha terminación de emerxencia do programa cun sinal. SIGSEGV, e o ficheiro permanecerá intacto.

A segunda consecuencia xa é específica para iOS. Nin o autor nin ningunha outra fonte o mencionan explícitamente, pero sen el LMDB non sería axeitado para funcionar neste sistema operativo móbil. O seguinte apartado está dedicado á súa consideración.

Especificacións dos ficheiros asignados á memoria en iOS

Houbo un informe marabilloso na WWDC en 2018 "Inmersión profunda da memoria de iOS". Indícanos que en iOS, todas as páxinas situadas na memoria física son de tres tipos: sucias, comprimidas e limpas.

A memoria limpa é unha colección de páxinas que se poden descargar sen dor da memoria física. Os datos que conteñen pódense volver cargar segundo sexa necesario desde as súas fontes orixinais. Os ficheiros asignados en memoria de só lectura entran nesta categoría. iOS non ten medo de descargar as páxinas asignadas a un ficheiro da memoria en calquera momento, xa que se garante que se sincronizarán co ficheiro do disco.
​
Todas as páxinas modificadas acaban na memoria sucia, sen importar onde se atopasen orixinalmente. En particular, clasificaranse deste xeito os ficheiros mapeados en memoria modificados mediante a escritura na memoria virtual asociada a eles. Apertura de LMDB con bandeira MDB_WRITEMAP, despois de facer cambios nela, podes verificalo persoalmente.​

Tan pronto como unha aplicación comeza a ocupar demasiada memoria física, iOS sométea a unha compresión de páxina sucia. A memoria total ocupada polas páxinas sucias e comprimidas constitúe a chamada pegada de memoria da aplicación. Unha vez que alcanza un determinado valor limiar, o daemon do sistema OOM killer aparece despois do proceso e termina por forza. Esta é a peculiaridade de iOS en comparación cos sistemas operativos de escritorio. En cambio, en iOS non se proporciona a redución da pegada na memoria intercambiando páxinas da memoria física ao disco. Os motivos só se poden adiviñar. Quizais o procedemento de mover páxinas de forma intensiva ao disco e cara atrás consuma demasiado enerxía para os dispositivos móbiles, ou iOS aforra o recurso de reescribir as celas nas unidades SSD, ou quizais os deseñadores non estaban satisfeitos co rendemento xeral do sistema, onde todo está intercambiado constantemente. Sexa como for, o feito segue sendo un feito.

A boa noticia, xa mencionada anteriormente, é que LMDB por defecto non usa o mecanismo mmap para actualizar ficheiros. Isto significa que os datos mostrados son clasificados por iOS como memoria limpa e non contribúen á pegada da memoria. Podes verificalo usando unha ferramenta Xcode chamada VM Tracker. A seguinte captura de pantalla mostra o estado da memoria virtual iOS da aplicación Cloud durante a operación. Ao comezo, inicializáronse nel 2 instancias LMDB. O primeiro foi autorizado a mostrar o seu ficheiro en 1 GiB de memoria virtual, o segundo - 512 MiB. A pesar de que ambos os dous almacenamentos ocupan unha certa cantidade de memoria residente, ningún deles contribúe ao tamaño sucio.

E agora é o momento das malas noticias. Grazas ao mecanismo de intercambio dos sistemas operativos de escritorio de 64 bits, cada proceso pode ocupar tanto espazo de enderezos virtuais como o permita o espazo libre no disco duro para o seu intercambio potencial. Substituír o intercambio por compresión en iOS reduce radicalmente o máximo teórico. Agora todos os procesos vivos deben encaixar na memoria principal (de lectura RAM) e todos aqueles que non encaixan deben ser forzados a finalizar. Isto indícase como no anteriormente mencionado informee en documentación oficial. Como consecuencia, iOS limita severamente a cantidade de memoria dispoñible para a súa asignación mediante mmap. Aquí aquí Podes ver os límites empíricos da cantidade de memoria que se pode asignar en diferentes dispositivos mediante esta chamada ao sistema. Nos modelos de teléfonos intelixentes máis modernos, iOS fíxose xeneroso en 2 gigabytes, e nas versións superiores do iPad - en 4. Na práctica, por suposto, tes que centrarte nos modelos de dispositivos compatibles máis baixos, onde todo é moi triste. Peor aínda, mirando o estado da memoria da aplicación en VM Tracker, verá que LMDB está lonxe de ser o único que afirma estar mapeado na memoria. Boas pezas son devoradas polos asignadores do sistema, ficheiros de recursos, marcos de imaxes e outros depredadores máis pequenos.

En base aos resultados dos experimentos na nube, chegamos aos seguintes valores de compromiso para a memoria asignada por LMDB: 384 megabytes para dispositivos de 32 bits e 768 para dispositivos de 64 bits. Despois de esgotar este volume, as operacións de modificación comezan a rematar co código MDB_MAP_FULL. Observamos este tipo de erros na nosa vixilancia, pero son o suficientemente pequenos como para que nesta fase se poidan descoidar.

Unha razón non obvia para o consumo excesivo de memoria polo almacenamento poden ser as transaccións de longa duración. Para comprender como están conectados estes dous fenómenos, axudaranos a considerar os dous piares restantes da LMDB.

3.2. Balea #2. Árbore B+

Para emular táboas enriba dun almacenamento de clave-valor, as seguintes operacións deben estar presentes na súa API:

1. Insirendo un novo elemento.
2. Busca un elemento cunha clave determinada.
3. Eliminando un elemento.
4. Iterar sobre intervalos de claves na orde en que se ordenan.

A estrutura de datos máis sinxela que pode implementar facilmente as catro operacións é unha árbore de busca binaria. Cada un dos seus nodos representa unha clave que divide todo o subconxunto de claves fillas en dúas subárbores. O esquerdo contén os que son máis pequenos que o pai, e o dereito contén os que son máis grandes. A obtención dun conxunto ordenado de claves conséguese mediante un dos clásicos percorridos de árbores.​

As árbores binarias teñen dous fallos fundamentais que lles impiden ser eficaces como estrutura de datos baseada en disco. En primeiro lugar, o grao do seu equilibrio é imprevisible. Existe un risco considerable de obter árbores nas que as alturas das distintas ramas poden diferir moito, o que empeora notablemente a complexidade algorítmica da busca en comparación co esperado. En segundo lugar, a abundancia de enlaces cruzados entre nós priva ás árbores binarias da localidade na memoria.Os nodos próximos (en termos de conexións entre eles) pódense localizar en páxinas completamente diferentes na memoria virtual. Como consecuencia, incluso un simple percorrido por varios nodos veciños nunha árbore pode requirir visitar un número comparable de páxinas. Este é un problema mesmo cando falamos da eficacia das árbores binarias como estrutura de datos en memoria, xa que rotar constantemente páxinas na caché do procesador non é un pracer barato. Cando se trata de recuperar con frecuencia páxinas asociadas aos nodos do disco, a situación faise completamente deplorable.

As árbores B, sendo unha evolución das árbores binarias, resolven os problemas identificados no parágrafo anterior. En primeiro lugar, son autoequilibrados. En segundo lugar, cada un dos seus nodos divide o conxunto de claves fillas non en 2, senón en subconxuntos ordenados M, e o número M pode ser bastante grande, da orde de varios centos ou incluso miles.

Así:

1. Cada nodo contén un gran número de claves xa ordenadas e as árbores son moi curtas.
2. A árbore adquire a propiedade da localidade de localización na memoria, xa que as claves que teñen un valor próximo sitúanse naturalmente unhas á beira das outras nos mesmos nodos ou veciños.
3. Redúcese o número de nodos de tránsito ao descender dunha árbore durante unha operación de busca.
4. O número de nodos de destino lidos durante as consultas de intervalo redúcese, xa que cada un deles xa contén un gran número de claves ordenadas.

LMDB usa unha variación da árbore B chamada árbore B+ para almacenar datos. O diagrama anterior mostra os tres tipos de nodos que existen nel:

1. Na parte superior está a raíz. Non se materializa máis que o concepto de base de datos dentro dun almacén. Dentro dunha instancia de LMDB, pode crear varias bases de datos que compartan un espazo de enderezos virtuais mapeado. Cada un deles parte da súa propia raíz.
2. No nivel máis baixo están as follas. Eles e só eles conteñen os pares clave-valor almacenados na base de datos. Por certo, esta é a peculiaridade das árbores B+. Se unha árbore B normal almacena partes de valor en nós de todos os niveis, entón a variación B+ só está na máis baixa. Unha vez solucionado este feito, chamaremos ademais ao subtipo da árbore usada en LMDB simplemente unha árbore B.
3. Entre a raíz e as follas hai 0 ou máis niveis técnicos con nós de navegación (rama). A súa tarefa é dividir o conxunto de chaves ordenadas entre as follas.

Fisicamente, os nodos son bloques de memoria dunha lonxitude predeterminada. O seu tamaño é un múltiplo do tamaño das páxinas de memoria do sistema operativo, que comentamos anteriormente. A estrutura do nodo móstrase a continuación. A cabeceira contén metainformación, a máis obvia, por exemplo, é a suma de verificación. A continuación vén información sobre os desplazamentos nos que se atopan as celas con datos. Os datos poden ser claves, se falamos de nós de navegación, ou pares de clave-valor enteiros no caso das follas.​ Podes ler máis sobre a estrutura das páxinas no traballo. "Avaliación de tendas de valor clave de alto rendemento".

Despois de tratar o contido interno dos nodos da páxina, representaremos ademais a árbore B LMDB dun xeito simplificado na seguinte forma.

As páxinas con nodos sitúanse secuencialmente no disco. As páxinas con números máis altos sitúanse cara ao final do ficheiro. A chamada páxina meta contén información sobre as compensacións polas que se poden atopar as raíces de todas as árbores. Ao abrir un ficheiro, LMDB escanea o ficheiro páxina por páxina de principio a fin en busca dunha metapáxina válida e a través dela atopa bases de datos existentes.

Agora, tendo unha idea da estrutura lóxica e física da organización de datos, podemos pasar a considerar o terceiro piar de LMDB. É coa súa axuda que todas as modificacións de almacenamento ocorren de forma transaccional e illadas entre si, dándolle á base de datos no seu conxunto a propiedade de multiversión.

3.3. Balea #3. Copiar sobre escribir

Algunhas operacións da árbore B implican facer unha serie de cambios nos seus nodos. Un exemplo é engadir unha nova chave a un nodo que xa alcanzou a súa capacidade máxima. Neste caso, é necesario, en primeiro lugar, dividir o nodo en dous e, en segundo lugar, engadir unha ligazón ao novo nodo fillo incipiente no seu pai. Este procedemento é potencialmente moi perigoso. Se por algún motivo (accidente, apagón, etc.) só se producen parte dos cambios da serie, entón a árbore permanecerá nun estado inconsistente.

Unha solución tradicional para facer que unha base de datos sexa tolerante a fallos é engadir unha estrutura de datos adicional no disco xunto á árbore B: un rexistro de transaccións, tamén coñecido como rexistro de escritura anticipada (WAL). É un ficheiro ao final do cal se escribe estrictamente a operación prevista antes de modificar a propia árbore B. Así, se se detecta corrupción de datos durante o autodiagnóstico, a base de datos consulta o rexistro para poñerse en orde.

LMDB escolleu un método diferente como mecanismo de tolerancia a fallos, chamado copy-on-write. A súa esencia é que, en lugar de actualizar os datos dunha páxina existente, primeiro cópiaa por completo e fai todas as modificacións na copia.

A continuación, para que os datos actualizados estean dispoñibles, é necesario cambiar a ligazón ao nodo que se fixo actual no seu nodo pai. Dado que tamén hai que modificar para iso, tamén se copia previamente. O proceso continúa recursivamente ata a raíz. O último que hai que cambiar son os datos da metapáxina.​​

Se de súpeto durante o procedemento de actualización o proceso falla, non se creará unha nova metapáxina ou non se escribirá completamente no disco e a súa suma de verificación será incorrecta. En calquera destes dous casos, as páxinas novas non serán accesibles, pero as antigas non se verán afectadas. Isto elimina a necesidade de que LMDB escriba o rexistro con antelación para manter a coherencia dos datos. De feito, a estrutura de almacenamento de datos no disco descrita anteriormente adquire simultaneamente a súa función. A ausencia dun rexistro de transaccións explícito é unha das características de LMDB que proporciona unha alta velocidade de lectura de datos

O deseño resultante, chamado árbore B de só adición, proporciona naturalmente illamento de transaccións e multiversiones. En LMDB, cada transacción aberta está asociada coa raíz da árbore relevante actualmente. Ata que se complete a transacción, as páxinas da árbore asociada a ela nunca serán modificadas nin reutilizadas para novas versións dos datos. Así, podes traballar o tempo que queiras exactamente co conxunto de datos que fose relevante nese momento. abriuse a transacción, aínda que o almacenamento continúe actualizándose activamente neste momento. Esta é a esencia da multiversión, facendo de LMDB unha fonte de datos ideal para o noso querido UICollectionView. Despois de abrir unha transacción, non hai que aumentar a pegada de memoria da aplicación bombeando apresuradamente os datos actuais nalgunha estrutura en memoria, por temor a quedar sen nada. Esta característica distingue a LMDB do mesmo SQLite, que non pode presumir de tal illamento total. Unha vez abertas dúas operacións nesta última e eliminado un determinado rexistro dentro dunha delas, xa non será posible obter o mesmo rexistro dentro do segundo restante.

A outra cara da moeda é o consumo potencialmente significativamente maior de memoria virtual. A diapositiva mostra como será a estrutura da base de datos se se modifica simultaneamente con 3 transaccións de lectura abertas mirando diferentes versións da base de datos. Dado que LMDB non pode reutilizar os nós accesibles desde as raíces asociadas ás transaccións actuais, a tenda non ten máis remedio que asignar outra cuarta raíz na memoria e clonar de novo as páxinas modificadas baixo ela.

Aquí sería útil lembrar a sección sobre ficheiros mapeados en memoria. Parece que o consumo adicional de memoria virtual non debe preocuparnos moito, xa que non contribúe á pegada de memoria da aplicación. Non obstante, ao mesmo tempo, observouse que iOS é moi tacaño á hora de asignalo e non podemos, como nun servidor ou nun escritorio, proporcionar unha rexión LMDB de 1 terabyte e non pensar nesta función en absoluto. Se é posible, debes intentar que a vida útil das transaccións sexa o máis curta posible.

4. Deseño dun esquema de datos enriba da API clave-valor

Comecemos a nosa análise da API mirando as abstraccións básicas que ofrece LMDB: ambiente e bases de datos, claves e valores, transaccións e cursores.

Unha nota sobre as listas de códigos

Todas as funcións da API pública LMDB devolven o resultado do seu traballo en forma de código de erro, pero en todas as listas posteriores omítese a súa verificación por motivos de brevidade. Na práctica, ata usamos o noso propio para interactuar co repositorio. garfo Envoltorios C++ lmdbxx, no que os erros se materializan como excepcións C++.

Como a forma máis rápida de conectar LMDB a un proxecto para iOS ou macOS, suxiro o meu CocoaPod POSLMDB.

4.1. Abstraccións básicas

Medio ambiente

Estrutura MDB_env é o repositorio do estado interno da LMDB. Familia de funcións prefixadas mdb_env permite configurar algunhas das súas propiedades. No caso máis sinxelo, a inicialización do motor é así.

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

Na aplicación Mail.ru Cloud, cambiamos os valores predeterminados de só dous parámetros.

O primeiro é o tamaño do espazo de enderezos virtuais ao que se asigna o ficheiro de almacenamento. Desafortunadamente, mesmo no mesmo dispositivo, o valor específico pode variar significativamente dunha execución a outra. Para ter en conta esta función de iOS, o volume máximo de almacenamento selecciónase de forma dinámica. Partindo dun determinado valor, redúcese secuencialmente á metade ata a función mdb_env_open non devolverá un resultado diferente de ENOMEM. En teoría, tamén existe o camiño contrario: primeiro asignar un mínimo de memoria ao motor e despois, cando se reciben erros, MDB_MAP_FULL, aumentalo. Porén, é moito máis espiñento. O motivo é que o procedemento para reasignar memoria (reasignación) mediante a función mdb_env_set_map_size invalida todas as entidades (cursores, transaccións, claves e valores) recibidas previamente do motor. Tendo en conta este xiro dos acontecementos no código levará á súa importante complicación. Non obstante, se a memoria virtual é moi importante para ti, isto pode ser un motivo para mirar máis de cerca o garfo que foi moi adiante MDBX, onde entre as funcións anunciadas hai o "axuste automático de tamaño da base de datos sobre a marcha".

O segundo parámetro, cuxo valor predeterminado non nos conveña, regula a mecánica para garantir a seguridade do fío. Desafortunadamente, polo menos iOS 10 ten problemas co soporte para o almacenamento local de fíos. Por este motivo, no exemplo anterior, o repositorio ábrese coa bandeira MDB_NOTLS. Ademais disto, tamén era necesario garfo Envoltorio C++ lmdbxxpara recortar variables con este atributo e nel.

Bases de datos

A base de datos é unha instancia separada da árbore B, que comentamos anteriormente. A súa apertura prodúcese dentro dunha transacción, o que pode parecer un pouco estraño ao principio.

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 feito, unha transacción en LMDB é unha entidade de almacenamento, non unha entidade de base de datos específica. Este concepto permite realizar operacións atómicas sobre entidades situadas en diferentes bases de datos. En teoría, isto abre a posibilidade de modelar táboas en forma de diferentes bases de datos, pero no seu momento tomei un camiño diferente, descrito en detalle a continuación.

Claves e valores

Estrutura MDB_val modela o concepto tanto de clave como de valor. O repositorio non ten idea da súa semántica. Para ela, outra cousa é só unha matriz de bytes dun tamaño determinado. O tamaño máximo da clave é de 512 bytes.

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

Usando un comparador, a tenda ordena as claves en orde ascendente. Se non o substitúe polo seu, entón utilizarase o predeterminado, que os ordena byte a byte en orde lexicográfica.​

Transaccións

A estrutura da transacción descríbese en detalle en capítulo anterior, así que aquí repetirei brevemente as súas principais propiedades:

1. Admite todas as propiedades básicas ÁCIDO: atomicidade, consistencia, illamento e fiabilidade. Non podo evitar notar que hai un erro en termos de durabilidade en macOS e iOS que foi corrixido en MDBX. Podes ler máis nas súas README.
2. O enfoque do multithreading descríbese polo esquema de "escritor único / lectores múltiples". Os escritores bloquean entre si, pero non bloquean os lectores. Os lectores non bloquean aos escritores nin entre si.
3. Soporte para transaccións aniñadas.
4. Soporte multiversión.

A multiversión en LMDB é tan boa que quero demostralo en acción. A partir do código de abaixo podes ver que cada transacción funciona exactamente coa versión da base de datos que estaba actual no momento en que se abriu, quedando completamente illada de todos os cambios posteriores. Iniciar o almacenamento e engadirlle un rexistro de proba non representa nada interesante, polo que estes rituais quedan baixo o spoiler.

Engadindo unha entrada de proba

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

Recomendo que probe o mesmo truco con SQLite e vexa que pasa.

A multiversión trae vantaxes moi agradables á vida dun programador de iOS. Usando esta propiedade, pode axustar de forma sinxela e natural a taxa de actualización da fonte de datos para os formularios de pantalla, en función das consideracións da experiencia do usuario. Por exemplo, tomemos unha función da aplicación Mail.ru Cloud como a carga automática de contido da galería multimedia do sistema. Cunha boa conexión, o cliente é capaz de engadir varias fotos por segundo ao servidor. Se actualizas despois de cada descarga UICollectionView con contido multimedia na nube do usuario, podes esquecer uns 60 fps e un desprazamento suave durante este proceso. Para evitar actualizacións frecuentes da pantalla, cómpre limitar dalgún xeito a velocidade á que cambian os datos no subxacente UICollectionViewDataSource.

Se a base de datos non admite multiversión e permite traballar só co estado actual actual, entón para crear unha instantánea dos datos estable no tempo, cómpre copiala nunha estrutura de datos en memoria ou nunha táboa temporal. Calquera destes enfoques é moi caro. No caso do almacenamento en memoria, obtemos custos tanto en memoria, causados ​​polo almacenamento de obxectos construídos, como no tempo, asociados a transformacións ORM redundantes. En canto á mesa temporal, este é un pracer aínda máis caro, que só ten sentido en casos non triviais.

A solución multiversión de LMDB resolve o problema de manter unha fonte de datos estable dun xeito moi elegante. Basta con abrir unha transacción e listo - ata que a completemos, o conxunto de datos está garantido para ser corrixido. A lóxica da súa velocidade de actualización está agora enteiramente en mans da capa de presentación, sen sobrecarga de recursos significativos.

Cursores

Os cursores proporcionan un mecanismo para a iteración ordenada sobre pares clave-valor a través do percorrido da árbore B. Sen eles, sería imposible modelar eficazmente as táboas da base de datos, á que agora nos diriximos.

4.2. Modelado de táboas

A propiedade da orde de claves permítelle construír unha abstracción de alto nivel, como unha táboa sobre as abstraccións básicas. Consideremos este proceso usando o exemplo da táboa principal dun cliente na nube, que almacena en caché información sobre todos os ficheiros e cartafoles do usuario.

Esquema de táboa

Un dos escenarios habituais para os que se debe adaptar unha estrutura de táboa cunha árbore de cartafoles é a selección de todos os elementos situados nun directorio determinado.Un bo modelo de organización de datos para consultas eficientes deste tipo é Lista de adxacencia. Para implementalo enriba do almacenamento de clave-valor, é necesario ordenar as claves dos ficheiros e cartafoles de forma que se agrupen en función da súa pertenza ao directorio principal. Ademais, para mostrar o contido do directorio na forma familiar dun usuario de Windows (primeiro cartafoles, despois ficheiros, ambos ordenados alfabeticamente), é necesario incluír na clave os campos adicionais correspondentes.

A imaxe de abaixo mostra como, en función da tarefa que se está a realizar, pode verse unha representación de claves en forma de matriz de bytes. En primeiro lugar colócanse os bytes co identificador do directorio pai (vermello), despois co tipo (verde) e na cola co nome (azul).Estando ordenados polo comparador LMDB predeterminado en orde lexicográfica, ordénanse no forma requirida. A percorrer secuencialmente as teclas co mesmo prefixo vermello proporciónanos os seus valores asociados na orde en que deberían mostrarse na interface de usuario (á dereita), sen necesidade de ningún post-procesamento adicional.

Serialización de claves e valores

No mundo inventáronse moitos métodos para serializar obxectos. Dado que non tiñamos outro requisito que non fose a velocidade, escollemos o máis rápido posible para nós: un volcado da memoria ocupada por unha instancia da estrutura da linguaxe C. Así, a clave dun elemento de directorio pódese modelar coa seguinte estrutura NodeKey.

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

Salvar NodeKey no almacenamento necesario no obxecto MDB_val sitúa o punteiro de datos no enderezo do inicio da estrutura e calcula o seu tamaño coa función sizeof.

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

No primeiro capítulo sobre os criterios de selección de bases de datos, mencionei a minimización das asignacións dinámicas dentro das operacións CRUD como un importante factor de selección. Código de función serialize mostra como no caso de LMDB poden evitarse completamente ao inserir novos rexistros na base de datos. A matriz de bytes entrantes do servidor transfórmase primeiro en estruturas de pila, e despois bótanse trivialmente no almacenamento. Tendo en conta que tampouco hai asignacións dinámicas dentro de LMDB, podes obter unha situación fantástica segundo os estándares de iOS: usa só a memoria de pila para traballar con datos ao longo de todo o camiño desde a rede ata o disco.

Ordenar claves cun comparador binario

A relación de orde das claves é especificada por unha función especial chamada comparador. Dado que o motor non sabe nada da semántica dos bytes que conteñen, ao comparador predeterminado non lle queda outra que organizar as claves en orde lexicográfica, recorrendo a unha comparación byte a byte. Usalo para organizar estruturas é semellante a afeitarse cun machado. Non obstante, en casos sinxelos paréceme aceptable este método. A alternativa descríbese a continuación, pero aquí notarei un par de anciños espallados por este camiño.

O primeiro que hai que lembrar é a representación da memoria dos tipos de datos primitivos. Así, en todos os dispositivos Apple, as variables enteiras almacénanse no formato Pequeno Endian. Isto significa que o byte menos significativo estará á esquerda e non será posible ordenar os enteiros mediante unha comparación byte por byte. Por exemplo, ao tentar facelo cun conxunto de números do 0 ao 511 producirase o seguinte resultado.

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

Para resolver este problema, os enteiros deben almacenarse na clave nun formato axeitado para o comparador de bytes-bytes. As funcións da familia axudaranche a levar a cabo a transformación necesaria hton* (en particular htons para números de dobre byte do exemplo).

O formato para representar cadeas na programación é, como sabes, un todo historia. Se a semántica das cadeas, así como a codificación utilizada para representalas na memoria, suxire que pode haber máis dun byte por carácter, entón é mellor abandonar inmediatamente a idea de usar un comparador predeterminado.

O segundo que hai que ter en conta é principios de aliñamento compilador de campos de estrutura. Debido a eles, pódense formar bytes con valores de lixo na memoria entre campos, o que, por suposto, rompe a clasificación byte-byte. Para eliminar o lixo, cómpre declarar os campos nunha orde estrictamente definida, tendo en conta as regras de aliñamento, ou ben usar o atributo na declaración de estrutura. packed.

Pedido de chaves cun comparador externo

A lóxica de comparación de claves pode ser demasiado complexa para un comparador binario. Unha das moitas razóns é a presenza de campos técnicos dentro das estruturas. Ilustrarei a súa aparición usando o exemplo dunha clave para un elemento de directorio que xa nos é familiar.

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

A pesar da súa sinxeleza, na gran maioría dos casos consome demasiada memoria. O búfer para o nome ocupa 256 bytes, aínda que, de media, os nomes de ficheiros e cartafoles raramente superan os 20-30 caracteres.

Unha das técnicas estándar para optimizar o tamaño dun rexistro é "recortalo" ao tamaño real. A súa esencia é que os contidos de todos os campos de lonxitude variable almacénanse nun búfer ao final da estrutura e as súas lonxitudes almacénanse en variables separadas. Segundo este enfoque, a clave NodeKey transfórmase do seguinte xeito.

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

Ademais, ao serializar, non se especifica o tamaño dos datos sizeof toda a estrutura, e o tamaño de todos os campos é unha lonxitude fixa máis o tamaño da parte realmente usada do búfer.

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

Como resultado da refactorización, conseguimos un importante aforro no espazo que ocupan as chaves. Porén, debido ao ámbito técnico nameLength, o comparador binario predeterminado xa non é axeitado para a comparación de claves. Se non o substituímos polo noso, entón a lonxitude do nome será un factor de maior prioridade na clasificación que o propio nome.

LMDB permite que cada base de datos teña a súa propia función de comparación de claves. Isto faise usando a función mdb_set_compare estrictamente antes de abrir. Por razóns obvias, non se pode cambiar ao longo da vida útil da base de datos. O comparador recibe dúas claves en formato binario como entrada, e na saída devolve o resultado da comparación: menor que (-1), maior que (1) ou igual a (0). Pseudocódigo para NodeKey parece así.

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 todas as claves da base de datos sexan do mesmo tipo, é legal emitir incondicionalmente a súa representación de bytes ao tipo de estrutura de chaves da aplicación. Aquí hai un matiz, pero comentarase a continuación na subsección "Rexistros de lectura".

Serialización de valores

LMDB traballa intensamente coas claves dos rexistros almacenados. A súa comparación entre si ocorre no marco de calquera operación aplicada e o rendemento de toda a solución depende da velocidade do comparador. Nun mundo ideal, o comparador binario predeterminado debería ser suficiente para comparar claves, pero se tivese que usar a súa propia, entón o procedemento para deserializar as claves debería ser o máis rápido posible.

A base de datos non está especialmente interesada na parte de valor do rexistro (valor). A súa conversión dunha representación de bytes a un obxecto só ocorre cando o código da aplicación xa o require, por exemplo, para mostralo na pantalla. Dado que isto ocorre relativamente raramente, os requisitos de velocidade para este procedemento non son tan críticos, e na súa implementación somos moito máis libres de centrarnos na comodidade.Por exemplo, para serializar metadatos sobre ficheiros que aínda non se descargaron, utilizamos NSKeyedArchiver.

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

Non obstante, hai momentos nos que o rendemento aínda importa. Por exemplo, ao gardar metainformación sobre a estrutura de ficheiros dunha nube de usuario, usamos o mesmo vocado de memoria de obxectos. O máis destacado da tarefa de xerar unha representación serializada deles é o feito de que os elementos dun directorio están modelados por unha xerarquía de clases.

Para implementalo na linguaxe C, os campos específicos dos herdeiros colócanse en estruturas separadas, e a súa conexión co base especifícase a través dun campo de tipo unión. Os contidos reais da unión especifícanse mediante o tipo de atributo técnico.

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

Engadir e actualizar rexistros

A clave e o valor serializados pódense engadir á tenda. Para iso, use a función mdb_put.

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

Na fase de configuración, pódese permitir ou prohibir ao almacenamento almacenar varios rexistros coa mesma clave. Se a duplicación de claves está prohibida, ao inserir un rexistro, pode determinar se se permite ou non actualizar un rexistro existente. Se o desgaste só pode producirse como resultado dun erro no código, pode protexerse del especificando a bandeira NOOVERWRITE.

Lectura de entradas

Para ler rexistros en LMDB, use a función mdb_get. Se o par clave-valor está representado por estruturas previamente envorcadas, este procedemento ten o seguinte aspecto.

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

A lista presentada mostra como a serialización mediante o volcado de estruturas permite desfacerse das asignacións dinámicas non só ao escribir, senón ao ler datos. Derivado da función mdb_get o punteiro mira exactamente o enderezo da memoria virtual onde a base de datos almacena a representación en bytes do obxecto. De feito, obtemos unha especie de ORM que proporciona unha velocidade de lectura de datos moi alta case de forma gratuíta. A pesar de toda a beleza do enfoque, é necesario lembrar varias características asociadas a el.

1. Para unha transacción de só lectura, o punteiro á estrutura de valor está garantido para permanecer válido só ata que se peche a transacción. Como se indicou anteriormente, as páxinas da árbore B nas que se atopa un obxecto, grazas ao principio de copia sobre escritura, permanecen inalteradas sempre que sexan referenciadas por polo menos unha transacción. Ao mesmo tempo, tan pronto como se complete a última transacción asociada a eles, as páxinas pódense reutilizar para novos datos. Se é necesario que os obxectos sobrevivan á transacción que os xerou, aínda deben ser copiados.
2. ​​Para unha transacción de lectura de escritura, o punteiro á estrutura de valores resultante só será válido ata o primeiro procedemento de modificación (escritura ou eliminación de datos).
3. Aínda que a estrutura NodeValue non completo, pero recortado (consulte a subsección "Ordenar claves mediante un comparador externo"), pode acceder con seguridade aos seus campos a través do punteiro. O principal é non desreferencialo!
4. En ningún caso se debe modificar a estrutura a través do punteiro recibido. Todos os cambios deben facerse só a través do método mdb_put. Non obstante, por moito que queiras facelo, non será posible, xa que a área de memoria onde se atopa esta estrutura está mapeada en modo de só lectura.
5. Volve asignar un ficheiro ao espazo de enderezos do proceso para, por exemplo, aumentar o tamaño máximo de almacenamento mediante a función mdb_env_set_map_size invalida por completo todas as transaccións e entidades relacionadas en xeral e apunta a determinados obxectos en particular.

Finalmente, outra característica é tan insidiosa que revelar a súa esencia non encaixa só noutro parágrafo. No capítulo sobre a árbore B, dei un diagrama de como están dispostas as súas páxinas na memoria. Diso dedúcese que o enderezo do inicio do búfer con datos serializados pode ser absolutamente arbitrario. Por iso, o punteiro a eles recibiu na estrutura MDB_val e reducido a un punteiro a unha estrutura, resulta que non está aliñado no caso xeral. Ao mesmo tempo, as arquitecturas dalgúns chips (no caso de iOS é armv7) requiren que a dirección de calquera dato sexa un múltiplo do tamaño da palabra da máquina ou, noutras palabras, do tamaño de bit do sistema ( para armv7 é de 32 bits). Noutras palabras, unha operación como *(int *foo)0x800002 sobre eles equivale a fuxir e leva á execución cun veredicto EXC_ARM_DA_ALIGN. Hai dous xeitos de evitar un destino tan triste.

O primeiro redúcese á copia preliminar de datos nunha estrutura obviamente aliñada. Por exemplo, nun comparador personalizado isto reflectirase do seguinte xeito.

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

Unha forma alternativa é notificar ao compilador con antelación que as estruturas clave-valor poden non estar aliñadas aos atributos. aligned(1). En ARM podes ter o mesmo efecto acadar e usando o atributo empaquetado. Tendo en conta que tamén axuda a optimizar o espazo que ocupa a estrutura, este método paréceme preferible, aínda que приводит a un aumento do custo das operacións de acceso a datos.

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

Consultas de intervalos

Para iterar sobre un grupo de rexistros, LMDB proporciona unha abstracción do cursor. Vexamos como traballar con el usando o exemplo dunha táboa con metadatos da nube de usuarios que xa nos coñecemos.

Como parte da visualización dunha lista de ficheiros nun directorio, é necesario atopar todas as claves coas que están asociados os seus ficheiros e cartafoles fillos. Nos subapartados anteriores ordenamos as claves NodeKey de tal xeito que están ordenados principalmente polo ID do directorio principal. Así, tecnicamente, a tarefa de recuperar o contido dun cartafol redúcese a situar o cursor no límite superior do grupo de claves cun prefixo dado e despois iterar ata o límite inferior.

O límite superior pódese atopar directamente mediante unha busca secuencial. Para iso, colócase o cursor ao principio de toda a lista de claves da base de datos e increméntase aínda máis ata que aparece debaixo dela unha clave co identificador do directorio pai. Este enfoque ten dúas desvantaxes obvias:

1. Complexidade de busca lineal, aínda que, como é sabido, nas árbores en xeral e nunha árbore B en particular pode realizarse en tempo logarítmico.
2. En balde, todas as páxinas que preceden á que se busca lévanse do ficheiro á memoria principal, que é moi cara.

Afortunadamente, a API LMDB proporciona un xeito eficaz de situar inicialmente o cursor. Para iso, cómpre xerar unha clave cuxo valor sexa, obviamente, menor ou igual á clave situada no límite superior do intervalo. Por exemplo, en relación á lista da figura anterior, podemos facer unha chave na que o campo parentId será igual a 2, e todo o resto está cheo de ceros. Dita tecla parcialmente cuberta entrégase á entrada da función mdb_cursor_get indicando a operación 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 se atopa o límite superior dun grupo de claves, iteramos sobre el ata que nos atopamos ou a chave se atopa con outra. parentId, ou as chaves non se esgotarán en absoluto.​

do {​
    rc = mdb_cursor_get(cursor, &key, &value, MDB_NEXT);​
    // processing...​
} while (MDB_NOTFOUND != rc && // check end of table​
         IsTargetKey(key));    // check end of keys group​​

O bo é que, como parte da iteración usando mdb_cursor_get, obtemos non só a clave, senón tamén o valor. Se, para cumprir as condicións de mostraxe, precisa comprobar, entre outras cousas, os campos da parte de valor do rexistro, entón son bastante accesibles sen xestos adicionais.

4.3. Modelización de relacións entre táboas

Ata agora, conseguimos considerar todos os aspectos do deseño e do traballo cunha base de datos dunha soa táboa. Podemos dicir que unha táboa é un conxunto de rexistros ordenados que consiste no mesmo tipo de pares clave-valor. Se mostra unha clave como un rectángulo e o valor asociado como un paralelepípedo, obtén un diagrama visual da base de datos.

​

Non obstante, na vida real raramente é posible sobrevivir con tan pouco derramamento de sangue. Moitas veces nunha base de datos requírese, en primeiro lugar, ter varias táboas e, en segundo lugar, facer seleccións nelas nunha orde diferente da clave primaria. Este último apartado está dedicado ás cuestións da súa creación e interconexión.

Táboas índice

A aplicación na nube ten unha sección "Galería". Mostra o contido multimedia de toda a nube, ordenado por data. Para implementar de forma óptima tal selección, xunto á táboa principal debes crear outra cun novo tipo de claves. Conterán un campo coa data de creación do ficheiro, que actuará como criterio de ordenación principal. Dado que as novas claves fan referencia aos mesmos datos que as claves da táboa principal, chámanse claves de índice. Na imaxe de abaixo están resaltados en laranxa.

Para separar as claves de diferentes táboas entre si dentro da mesma base de datos, engadiuse a todas elas un tableId de campo técnico adicional. Ao facer que sexa a máxima prioridade para a ordenación, conseguiremos agrupar as claves primeiro por táboas e dentro das táboas, segundo as nosas propias regras.

A clave de índice fai referencia aos mesmos datos que a clave primaria. Unha implementación sinxela desta propiedade mediante a asociación con ela dunha copia da parte de valor da clave primaria non é óptima desde varios puntos de vista:

1. En termos de espazo ocupado, os metadatos poden ser bastante ricos.
2. Desde o punto de vista do rendemento, xa que ao actualizar os metadatos dun nodo, haberá que reescribilos mediante dúas teclas.
3. Desde o punto de vista do soporte de código, se esquecemos actualizar os datos dunha das claves, obteremos un erro esquivo de inconsistencia de datos no almacenamento.

A continuación, consideraremos como eliminar estas deficiencias.

Organización das relacións entre táboas

O patrón é moi axeitado para vincular a táboa de índice coa táboa principal "clave como valor". Como o seu nome indica, a parte do valor do rexistro de índice é unha copia do valor da chave primaria. Este enfoque elimina todas as desvantaxes mencionadas anteriormente asociadas ao almacenamento dunha copia da parte de valor do rexistro principal. O único custo é que para obter un valor por clave de índice, cómpre facer 2 consultas á base de datos en lugar dunha. Esquemáticamente, o esquema da base de datos resultante ten este aspecto.

Outro patrón para organizar as relacións entre táboas é "chave redundante". A súa esencia é engadir atributos adicionais á chave, que non son necesarios para ordenar, senón para recrear a chave asociada.Na aplicación Mail.ru Cloud hai exemplos reais do seu uso, con todo, para evitar un mergullo profundo no contexto de frameworks iOS específicos, vou dar un exemplo ficticio, pero máis claro.​

Os clientes móbiles na nube teñen unha páxina que mostra todos os ficheiros e cartafoles que o usuario compartiu con outras persoas. Dado que hai relativamente poucos ficheiros deste tipo, e hai moitos tipos diferentes de información específica sobre a publicidade asociada a eles (a quen se lle concede acceso, con que dereitos, etc.), non será racional cargar a parte do valor do rexistrar con ela na táboa principal. Non obstante, se queres amosar estes ficheiros sen conexión, aínda debes almacenalos nalgún lugar. Unha solución natural é crear unha táboa separada para iso. No diagrama de abaixo, a súa chave ten o prefixo "P" e o marcador de posición "propname" pódese substituír polo valor máis específico "public info".

Todos os metadatos únicos, co fin de almacenar os que se creou a nova táboa, colócanse na parte de valor do rexistro. Ao mesmo tempo, non quere duplicar os datos sobre ficheiros e cartafoles que xa están almacenados na táboa principal. Pola contra, engádense datos redundantes á clave "P" en forma de campos "ID de nodo" e "marca de tempo". Grazas a eles, pódese construír unha clave de índice, a partir da cal pode obter unha clave primaria, da que, finalmente, pode obter metadatos de nodos.

Conclusión

Valoramos positivamente os resultados da implantación de LMDB. Despois diso, o número de aplicacións conxeladas diminuíu nun 30%.

Os resultados do traballo feito repercutiron máis aló do equipo de iOS. Actualmente, unha das principais seccións "Ficheiros" da aplicación de Android tamén pasou a usar LMDB, e outras partes están en camiño. A linguaxe C, na que se implementa o almacén de clave-valor, foi unha boa axuda para crear inicialmente un marco de aplicacións ao seu redor multiplataforma en C++. Utilizouse un xerador de código para conectar perfectamente a biblioteca C++ resultante co código da plataforma en Objective-C e Kotlin Djinni de Dropbox, pero esa é unha historia completamente diferente.

Fonte: www.habr.com