En el otoño de 2019, tuvo lugar un evento largamente esperado en el equipo Mail.ru Cloud iOS. La base de datos principal para el almacenamiento persistente del estado de la aplicación se ha vuelto bastante exótica para el mundo móvil. (LMDB). Debajo del corte, se invita su atención a su revisión detallada en cuatro partes. Primero, hablemos de las razones de una elección tan difícil y no trivial. Luego, pasemos a la consideración de tres ballenas en el corazón de la arquitectura LMDB: archivos mapeados en memoria, árbol B +, enfoque de copia en escritura para implementar transaccionales y multiversiones. Finalmente, para el postre, la parte práctica. En él, veremos cómo diseñar e implementar un esquema de base de datos con varias tablas, incluida una de índice, además de la API de clave-valor de bajo nivel.
contenido
3.1.
3.2.
3.3.
4.1.
4.2.
4.3.
1. Motivación para la implementación
Una vez al año, en 2015, nos encargamos de tomar una métrica, con qué frecuencia se retrasa la interfaz de nuestra aplicación. No solo hicimos esto. Cada vez tenemos más quejas sobre el hecho de que, en ocasiones, la aplicación deja de responder a las acciones del usuario: los botones no se presionan, las listas no se desplazan, etc. Sobre la mecánica de las medidas. en AvitoTech, así que aquí solo doy el orden de los números.
Los resultados de la medición se convirtieron en una ducha fría para nosotros. Resultó que los problemas causados por las heladas son mucho más que cualquier otro. Si, antes de darse cuenta de este hecho, el principal indicador técnico de calidad estaba libre de fallas, luego de que el enfoque en libre de congelación.
Habiendo construido y habiendo gastado и análisis de sus causas, el enemigo principal quedó claro: la lógica empresarial pesada que se ejecuta en el subproceso principal de la aplicación. Una reacción natural a esta desgracia fue un ardiente deseo de introducirlo en los flujos de trabajo. Para una solución sistemática de este problema, recurrimos a una arquitectura de subprocesos múltiples basada en actores ligeros. Le dediqué adaptaciones para el mundo iOS. en el twitter colectivo y . Como parte de la historia actual, quiero enfatizar aquellos aspectos de la decisión que influyeron en la elección de la base de datos.
El modelo de actor de la organización del sistema asume que los subprocesos múltiples se convierten en su segunda esencia. A los objetos del modelo les gusta cruzar los límites de los hilos. Y lo hacen no a veces y en algunos lugares, sino casi constantemente y en todas partes.
La base de datos es uno de los componentes fundamentales del diagrama presentado. Su tarea principal es implementar un patrón macro. . Si en el mundo empresarial se utiliza para organizar la sincronización de datos entre servicios, entonces, en el caso de una arquitectura de actor, datos entre hilos. Por lo tanto, necesitábamos una base de datos de este tipo, trabajar con ella en un entorno de subprocesos múltiples no causa ni siquiera dificultades mínimas. En particular, esto significa que los objetos derivados de él deben ser al menos seguros para subprocesos e, idealmente, no mutables en absoluto. Como sabes, este último puede usarse simultáneamente desde varios hilos sin recurrir a ningún tipo de bloqueo, lo que tiene un efecto beneficioso en el rendimiento.
El segundo factor importante que influyó en la elección de la base de datos fue nuestra API en la nube. Se inspiró en el enfoque de git para la sincronización. Como él, apuntamos a , que parece más que apropiado para clientes en la nube. Se asumió que solo bombearían una vez el estado completo de la nube, y luego la sincronización en la gran mayoría de los casos ocurriría a través de cambios continuos. Por desgracia, esta posibilidad todavía se encuentra solo en la zona teórica y, en la práctica, los clientes no han aprendido a trabajar con parches. Hay una serie de razones objetivas para ello, que, para no retrasar la introducción, dejaremos fuera de paréntesis. Ahora mucho más interesantes son los resultados instructivos de la lección sobre lo que sucede cuando la API dice "A" y su consumidor no dice "B".
Entonces, si imagina git, que, al ejecutar un comando de extracción, en lugar de aplicar parches a una instantánea local, compara su estado completo con el servidor completo, entonces tendrá una idea bastante precisa de cómo sincronización se produce en los clientes de la nube. Es fácil adivinar que para su implementación es necesario asignar dos árboles DOM en la memoria con metainformación sobre todos los servidores y archivos locales. Resulta que si un usuario almacena 500 mil archivos en la nube, para sincronizarlos, es necesario recrear y destruir dos árboles con 1 millón de nodos. Pero cada nodo es un agregado que contiene un gráfico de subobjetos. En este sentido, los resultados del perfilado eran los esperados. Resultó que incluso sin tener en cuenta el algoritmo de combinación, el procedimiento mismo de crear y luego destruir una gran cantidad de objetos pequeños cuesta bastante dinero. La situación se ve agravada por el hecho de que la operación de sincronización básica está incluida en una gran cantidad. de guiones de usuario. Como resultado, fijamos el segundo criterio importante al elegir una base de datos: la capacidad de implementar operaciones CRUD sin asignación dinámica de objetos.
Otros requisitos son más tradicionales y su lista completa es la siguiente.
- Seguridad del hilo.
- Multiprocesamiento. Dictado por el deseo de utilizar la misma instancia de base de datos para sincronizar el estado no solo entre subprocesos, sino también entre la aplicación principal y las extensiones de iOS.
- La capacidad de representar entidades almacenadas como objetos no mutables.
- Falta de asignaciones dinámicas dentro de las operaciones CRUD.
- Soporte de transacciones para propiedades básicas Palabras clave: atomicidad, consistencia, aislamiento y confiabilidad.
- Velocidad en los casos más populares.
Con este conjunto de requisitos, SQLite fue y sigue siendo una buena opción. Sin embargo, como parte del estudio de alternativas, encontré un libro . Bajo su liderazgo, se escribió un punto de referencia que compara la velocidad de trabajo con diferentes bases de datos en escenarios de nube reales. El resultado superó las expectativas más salvajes. En los casos más populares, obtener un cursor en una lista ordenada de todos los archivos y una lista ordenada de todos los archivos para un directorio determinado, LMDB resultó ser 10 veces más rápido que SQLite. La elección se hizo evidente.
2. Posicionamiento LMDB
LMDB es una biblioteca, muy pequeña (solo 10K líneas), que implementa la capa fundamental más baja de bases de datos: almacenamiento.
El diagrama anterior muestra que comparar LMDB con SQLite, que implementa niveles aún más altos, generalmente no es más correcto que SQLite con Core Data. Sería más justo citar los mismos motores de almacenamiento como competidores iguales: BerkeleyDB, LevelDB, Sophia, RocksDB, etc. Incluso hay desarrollos en los que LMDB actúa como un componente de motor de almacenamiento para SQLite. El primer experimento de este tipo en 2012. autor LMDB . resultó ser tan intrigante que su iniciativa fue recogida por los entusiastas de OSS, y encontró su continuación frente a . En enero de 2020 el autor de este proyecto es Den Shearer en LinuxConfAu.
El uso principal de LMDB es como motor para bases de datos de aplicaciones. La biblioteca debe su apariencia a los desarrolladores. , que estaban muy insatisfechos con BerkeleyDB como base de su proyecto. Alejándose de la humilde biblioteca , Howard Chu pudo crear una de las alternativas más populares de nuestro tiempo. Dedicó su genial informe a esta historia, así como a la estructura interna de LMDB. . Leonid Yuriev (alias ) de Positive Technologies en su charla en Highload 2015 . En él, habla de LMDB en el contexto de una tarea similar de implementación de ReOpenLDAP, y LevelDB ya ha sido objeto de críticas comparativas. Como resultado de la implementación, Positive Technologies incluso obtuvo una bifurcación en desarrollo activo con características muy sabrosas, optimizaciones y .
LMDB también se usa a menudo como almacenamiento tal cual. Por ejemplo, el navegador Mozilla Firefox para una serie de necesidades y, a partir de la versión 9, Xcode su SQLite para almacenar índices.
El motor también se puso de moda en el mundo del desarrollo móvil. Las huellas de su uso pueden ser en el cliente de iOS para Telegram. LinkedIn fue un paso más allá y eligió LMDB como el almacenamiento predeterminado para su marco de almacenamiento en caché de datos de cosecha propia, Rocket Data, sobre el cual en un artículo de 2016.
LMDB está luchando con éxito por un lugar bajo el sol en el nicho dejado por BerkeleyDB después de la transición bajo el control de Oracle. La biblioteca es amada por su velocidad y confiabilidad, incluso en comparación con su propia clase. Como saben, no hay almuerzos gratis, y me gustaría enfatizar la compensación que tendrá que enfrentar al elegir entre LMDB y SQLite. El diagrama anterior demuestra claramente cómo se logra el aumento de velocidad. En primer lugar, no pagamos por capas adicionales de abstracción además del almacenamiento en disco. Por supuesto, en una buena arquitectura, aún no puede prescindir de ellos, e inevitablemente aparecerán en el código de la aplicación, pero serán mucho más delgados. No tendrán características que no sean requeridas por una aplicación específica, por ejemplo, soporte para consultas en lenguaje SQL. En segundo lugar, es posible implementar de manera óptima la asignación de operaciones de aplicaciones a solicitudes de almacenamiento en disco. Si SQLite proviene de las necesidades promedio de una aplicación promedio, entonces usted, como desarrollador de aplicaciones, conoce bien los principales escenarios de carga. Para una solución más productiva, tendrá que pagar un precio mayor tanto por el desarrollo de la solución inicial como por su soporte posterior.
3. Tres ballenas LMDB
Después de mirar la LMDB a vista de pájaro, es hora de profundizar. Los siguientes tres apartados estarán dedicados al análisis de las principales ballenas sobre las que se apoya la arquitectura de almacenamiento:
- Archivos mapeados en memoria como mecanismo para trabajar con disco y sincronizar estructuras de datos internas.
- B+-tree como una organización de la estructura de datos almacenada.
- Copy-on-write como un enfoque para proporcionar propiedades transaccionales ACID y multiversiones.
3.1. Ballena #1. Archivos mapeados en memoria
Los archivos mapeados en memoria son un elemento arquitectónico tan importante que incluso aparecen en el nombre del repositorio. Los problemas de almacenamiento en caché y sincronización del acceso a la información almacenada están completamente a merced del sistema operativo. LMDB no contiene ningún caché dentro de sí mismo. Esta es una decisión consciente del autor, ya que la lectura de datos directamente de los archivos mapeados le permite reducir muchos gastos en la implementación del motor. A continuación se muestra una lista lejos de ser completa de algunos de ellos.
- Mantener la coherencia de los datos en el almacenamiento cuando se trabaja con ellos desde varios procesos pasa a ser responsabilidad del sistema operativo. En la siguiente sección, esta mecánica se analiza en detalle y con imágenes.
- La ausencia de cachés libera completamente a LMDB de la sobrecarga asociada con las asignaciones dinámicas. Leer datos en la práctica es establecer el puntero en la dirección correcta en la memoria virtual y nada más. Suena como una fantasía, pero en la fuente del repositorio, todas las llamadas calloc se concentran en la función de configuración del repositorio.
- La ausencia de cachés también significa la ausencia de bloqueos asociados a la sincronización para acceder a ellos. Los lectores, de los cuales puede existir un número arbitrario al mismo tiempo, no encuentran un solo mutex en su camino hacia los datos. Debido a esto, la velocidad de lectura tiene una escalabilidad lineal ideal en términos de número de CPU. En LMDB, solo se sincronizan las operaciones de modificación. Sólo puede haber un escritor a la vez.
- Un mínimo de lógica de sincronización y almacenamiento en caché salva el código de un tipo extremadamente complejo de errores asociados con el trabajo en un entorno de subprocesos múltiples. Hubo dos estudios de bases de datos interesantes en la conferencia Usenix OSDI 2014: и . De ellos puede obtener información sobre la confiabilidad sin precedentes de LMDB y la implementación casi perfecta de las propiedades ACID de las transacciones, que lo supera en el mismo SQLite.
- El minimalismo de LMDB permite que la representación de la máquina de su código se coloque completamente en el caché L1 del procesador con las características de velocidad resultantes.
Desafortunadamente, en iOS, los archivos mapeados en memoria no son tan atractivos como nos gustaría. Para hablar sobre las desventajas asociadas con ellos de manera más consciente, es necesario recordar los principios generales para implementar este mecanismo en los sistemas operativos.
Información general sobre archivos mapeados en memoria
Con cada aplicación ejecutable, el sistema operativo asocia una entidad llamada proceso. A cada proceso se le asigna un rango contiguo de direcciones en las que coloca todo lo que necesita para funcionar. Las direcciones más bajas contienen secciones con código y datos y recursos codificados. Luego viene el bloque de crecimiento ascendente del espacio de direcciones dinámicas, bien conocido por nosotros como el montón. Contiene las direcciones de las entidades que aparecen durante el funcionamiento del programa. En la parte superior está el área de memoria utilizada por la pila de aplicaciones. O crece o se encoge, es decir, su tamaño también tiene un carácter dinámico. Para que la pila y el montón no se empujen ni interfieran entre sí, están separados en diferentes extremos del espacio de direcciones.Hay un agujero entre las dos secciones dinámicas en la parte superior e inferior. El sistema operativo utiliza las direcciones en esta sección central para asociar una variedad de entidades con el proceso. En particular, puede asignar un determinado conjunto continuo de direcciones a un archivo en el disco. Dicho archivo se denomina archivo mapeado en memoria.
El espacio de direcciones asignado a un proceso es enorme. En teoría, el número de direcciones está limitado solo por el tamaño del puntero, que está determinado por el bitness del sistema. Si se le asignara memoria física 1 en 1, entonces el primer proceso engulliría toda la RAM y no habría dudas sobre la multitarea.
Sin embargo, sabemos por experiencia que los sistemas operativos modernos pueden ejecutar tantos procesos como desee al mismo tiempo. Esto es posible debido al hecho de que asignan mucha memoria a los procesos solo en papel, pero en realidad cargan en la memoria física principal solo la parte que se demanda aquí y ahora. Por lo tanto, la memoria asociada al proceso se llama virtual.
El sistema operativo organiza la memoria virtual y física en páginas de un tamaño determinado. Tan pronto como se solicita una determinada página de memoria virtual, el sistema operativo la carga en la memoria física y establece una correspondencia entre ellas en una tabla especial. Si no hay ranuras libres, entonces una de las páginas previamente cargadas se copia en el disco y la solicitada ocupa su lugar. Este procedimiento, al que volveremos en breve, se denomina intercambio. La siguiente figura ilustra el proceso descrito. En ella se cargó la página A con dirección 0 y se colocó en la página de memoria principal con dirección 4. Este hecho se reflejó en la tabla de correspondencia en la celda número 0.
Con los archivos mapeados en memoria, la historia es exactamente la misma. Lógicamente, se supone que se colocan de forma continua y completa en el espacio de direcciones virtuales. Sin embargo, ingresan a la memoria física página por página y solo bajo demanda. La modificación de tales páginas se sincroniza con el archivo en el disco. Por lo tanto, puede realizar E / S de archivos, simplemente trabajando con bytes en la memoria: el kernel del sistema operativo transferirá automáticamente todos los cambios al archivo original.
La siguiente imagen muestra cómo LMDB sincroniza su estado cuando trabaja con la base de datos de diferentes procesos. Al mapear la memoria virtual de diferentes procesos en el mismo archivo, de facto obligamos al sistema operativo a sincronizar transitivamente ciertos bloques de sus espacios de direcciones entre sí, que es donde busca LMDB.
Un matiz importante es que LMDB modifica el archivo de datos de forma predeterminada a través del mecanismo de llamada al sistema de escritura, y el archivo en sí se muestra en modo de solo lectura. Este enfoque tiene dos implicaciones importantes.
La primera consecuencia es común a todos los sistemas operativos. Su esencia es agregar protección contra daños inadvertidos a la base de datos por código incorrecto. Como sabe, las instrucciones ejecutables de un proceso son libres de acceder a los datos desde cualquier lugar en su espacio de direcciones. Al mismo tiempo, como acabamos de recordar, mostrar un archivo en modo lectura-escritura significa que cualquier instrucción también puede modificarlo. Si hace esto por error, tratando, por ejemplo, de sobrescribir un elemento de matriz en un índice inexistente, de esta manera puede cambiar accidentalmente el archivo asignado a esta dirección, lo que provocará daños en la base de datos. Si el archivo se muestra en modo de solo lectura, un intento de cambiar el espacio de direcciones correspondiente provocará que el programa se bloquee con la señal SIGSEGVy el archivo permanecerá intacto.
La segunda consecuencia ya es específica de iOS. Ni el autor ni ninguna otra fuente lo mencionan explícitamente, pero sin él, LMDB no sería adecuado para ejecutarse en este sistema operativo móvil. La siguiente sección está dedicada a su consideración.
Detalles de los archivos mapeados en memoria en iOS
En 2018, hubo un informe maravilloso en WWDC . Dice que en iOS todas las páginas ubicadas en la memoria física pertenecen a uno de 3 tipos: sucias, comprimidas y limpias.
La memoria limpia es una colección de páginas que se pueden intercambiar de forma segura fuera de la memoria física. Los datos que contienen se pueden recargar desde sus fuentes originales según sea necesario. Los archivos mapeados en memoria de solo lectura entran en esta categoría. iOS no teme descargar las páginas asignadas a un archivo de la memoria en cualquier momento, ya que se garantiza que se sincronizarán con el archivo en el disco.
Todas las páginas modificadas se almacenan en la memoria sucia, sin importar dónde se encuentren originalmente. En particular, los archivos mapeados en memoria modificados escribiendo en la memoria virtual asociada a ellos también se clasificarán de esta manera. Abriendo LMDB con bandera MDB_WRITEMAP, después de hacerle cambios, puedes verlo por ti mismo.
Tan pronto como una aplicación comienza a ocupar demasiada memoria física, iOS comprime sus páginas sucias. La colección de memoria ocupada por páginas sucias y comprimidas es la llamada huella de memoria de la aplicación. Cuando alcanza un cierto valor de umbral, el demonio del sistema OOM killer viene después del proceso y lo termina por la fuerza. Esta es la peculiaridad de iOS en comparación con los sistemas operativos de escritorio. Por el contrario, iOS no permite reducir el consumo de memoria mediante el intercambio de páginas de la memoria física al disco. Uno solo puede adivinar las razones. Tal vez el procedimiento para mover páginas de manera intensiva al disco y viceversa consume demasiada energía para los dispositivos móviles, o iOS ahorra el recurso de reescribir celdas en unidades SSD, o tal vez los diseñadores no estaban satisfechos con el rendimiento general del sistema, donde todo está intercambiado constantemente. Sea como fuere, el hecho permanece.
La buena noticia, ya mencionada anteriormente, es que LMDB no utiliza el mecanismo mmap para actualizar archivos de forma predeterminada. De ello se deduce que iOS clasifica los datos procesados como memoria limpia y no contribuye a la huella de memoria. Esto se puede verificar usando la herramienta Xcode llamada VM Tracker. La siguiente captura de pantalla muestra el estado de la memoria virtual de la aplicación iOS Cloud durante el funcionamiento. Al principio, se inicializaron 2 instancias de LMDB en él. Al primero se le permitió asignar su archivo a 1 GiB de memoria virtual, al segundo, a 512 MiB. A pesar de que ambos almacenamientos ocupan una cierta cantidad de memoria residente, ninguno de ellos contribuye al tamaño sucio.
Ahora es el momento de las malas noticias. Gracias al mecanismo de intercambio en los sistemas operativos de escritorio de 64 bits, cada proceso puede ocupar tanto espacio de direcciones virtuales como el espacio libre en el disco duro permita su posible intercambio. Reemplazar swap con compresión en iOS reduce drásticamente el máximo teórico. Ahora todos los procesos vivos deben caber en la memoria principal (RAM de lectura), y todos aquellos que no caben están sujetos a terminación forzada. Se menciona como en el anterior y en . Como consecuencia, iOS limita severamente la cantidad de memoria disponible para la asignación a través de mmap. Aquí puede ver los límites empíricos en la cantidad de memoria que podría asignarse en diferentes dispositivos usando esta llamada al sistema. En los modelos más modernos de teléfonos inteligentes, iOS se ha vuelto generoso en 2 gigabytes, y en las versiones superiores del iPad, en 4. En la práctica, por supuesto, debe concentrarse en los modelos de dispositivos compatibles más jóvenes, donde todo es muy triste. Peor aún, al observar el estado de la memoria de la aplicación en VM Tracker, encontrará que LMDB está lejos de ser el único que reclama memoria asignada a la memoria. Los asignadores del sistema, los archivos de recursos, los marcos de imagen y otros depredadores más pequeños se comen buenos trozos.
Como resultado de los experimentos en la nube, obtuvimos los siguientes valores de compromiso de la memoria asignada por LMDB: 384 megabytes para dispositivos de 32 bits y 768 para dispositivos de 64 bits. Una vez que se agota este volumen, cualquier operación de modificación comienza a completarse con el código MDB_MAP_FULL. Observamos tales errores en nuestro monitoreo, pero son lo suficientemente pequeños como para ignorarlos en esta etapa.
Una razón no obvia para el consumo excesivo de memoria por parte del almacenamiento pueden ser las transacciones de larga duración. Para comprender cómo se relacionan estos dos fenómenos, nos ayudará considerar las dos ballenas LMDB restantes.
3.2. Ballena #2. árbol B+
Para emular tablas encima de un almacén de clave-valor, las siguientes operaciones deben estar presentes en su API:
- Insertando un nuevo elemento.
- Buscar un elemento con una clave determinada.
- Eliminación de un elemento.
- Iterar sobre intervalos clave en su orden de clasificación.
La estructura de datos más simple que puede implementar fácilmente las cuatro operaciones es un árbol de búsqueda binaria. Cada uno de sus nodos es una clave que divide todo el subconjunto de claves secundarias en dos subárboles. A la izquierda están los que son más pequeños que el padre y a la derecha, los que son más grandes. La obtención de un conjunto ordenado de claves se logra a través de uno de los clásicos recorridos en árbol.
Los árboles binarios tienen dos inconvenientes fundamentales que les impiden ser efectivos como estructura de datos de disco. Primero, el grado de su equilibrio es impredecible. Existe un riesgo considerable de obtener árboles en los que la altura de las distintas ramas puede variar mucho, lo que empeora significativamente la complejidad algorítmica de la búsqueda respecto a lo esperado. En segundo lugar, la abundancia de enlaces cruzados entre nodos priva a los árboles binarios de localidad en la memoria.Los nodos cercanos (en términos de enlaces entre ellos) pueden ubicarse en páginas completamente diferentes en la memoria virtual. Como consecuencia, incluso un simple recorrido de varios nodos vecinos en un árbol puede requerir visitar un número comparable de páginas. Esto es un problema incluso cuando hablamos de la efectividad de los árboles binarios como una estructura de datos en memoria, ya que rotar constantemente las páginas en el caché del procesador no es barato. Cuando se trata de generar con frecuencia páginas relacionadas con nodos desde el disco, las cosas se ponen realmente mal. .
Los árboles B, al ser una evolución de los árboles binarios, resuelven los problemas identificados en el párrafo anterior. En primer lugar, son autoequilibrantes. En segundo lugar, cada uno de sus nodos divide el conjunto de claves secundarias no en 2, sino en M subconjuntos ordenados, y el número M puede ser bastante grande, del orden de varios cientos o incluso miles.
De este modo:
- Cada nodo tiene una gran cantidad de claves ya ordenadas y los árboles son muy bajos.
- El árbol adquiere la propiedad de localidad en la memoria, ya que las claves que tienen un valor cercano se ubican naturalmente una al lado de la otra en uno o nodos vecinos.
- Reduce el número de nodos de tránsito al descender del árbol durante una operación de búsqueda.
- Reduce la cantidad de nodos de destino leídos para consultas de rango, ya que cada uno de ellos ya contiene una gran cantidad de claves ordenadas.
LMDB utiliza una variante del árbol B llamada árbol B+ para almacenar datos. El diagrama anterior muestra los tres tipos de nodos que contiene:
- En la parte superior está la raíz. No materializa nada más que el concepto de una base de datos dentro de un repositorio. Dentro de una única instancia de LMDB, puede crear varias bases de datos que comparten el espacio de direcciones virtuales asignadas. Cada uno de ellos parte de su propia raíz.
- En el nivel más bajo están las hojas (hoja). Son ellos y solo ellos los que contienen los pares clave-valor almacenados en la base de datos. Por cierto, esta es la peculiaridad de los árboles B+. Si un árbol B normal almacena las partes de valor en los nodos de todos los niveles, entonces la variación B+ está solo en el más bajo. Habiendo solucionado este hecho, en lo que sigue llamaremos al subtipo del árbol usado en LMDB simplemente un árbol B.
- Entre la raíz y las hojas, hay 0 o más niveles técnicos con nodos de navegación (rama). Su tarea es dividir el juego ordenado de llaves entre las hojas.
Físicamente, los nodos son bloques de memoria de una longitud predeterminada. Su tamaño es un múltiplo del tamaño de las páginas de memoria en el sistema operativo, de las que hablamos anteriormente. La estructura del nodo se muestra a continuación. El encabezado contiene metainformación, la más obvia de las cuales, por ejemplo, es la suma de verificación. Luego viene información sobre compensaciones, a lo largo de las cuales se ubican las celdas con datos. El papel de los datos puede ser claves, si hablamos de nodos de navegación, o pares clave-valor completos en el caso de las hojas. Puede leer más sobre la estructura de las páginas en el trabajo. .
Habiendo tratado el contenido interno de los nodos de la página, representaremos aún más el árbol B de LMDB de manera simplificada en el siguiente formulario.
Las páginas con nodos se organizan secuencialmente en el disco. Las páginas con un número más alto se encuentran hacia el final del archivo. La llamada página meta (meta página) contiene información sobre las compensaciones, que se pueden usar para encontrar las raíces de todos los árboles. Cuando se abre un archivo, LMDB escanea el archivo página por página desde el final hasta el principio en busca de una metapágina válida y encuentra las bases de datos existentes a través de ella.
Ahora, teniendo una idea de la estructura lógica y física de la organización de datos, podemos proceder a considerar la tercera ballena de LMDB. Es con su ayuda que todas las modificaciones de almacenamiento ocurren transaccionalmente y de forma aislada entre sí, dando a la base de datos como un todo también la propiedad de múltiples versiones.
3.3. Ballena #3. Copiar en escrito
Algunas operaciones de árbol B implican realizar toda una serie de cambios en sus nodos. Un ejemplo es agregar una nueva clave a un nodo que ya alcanzó su capacidad máxima. En este caso, es necesario, en primer lugar, dividir el nodo en dos y, en segundo lugar, agregar un enlace al nuevo nodo secundario derivado en su padre. Este procedimiento es potencialmente muy peligroso. Si por alguna razón (fallo, corte de energía, etc.) solo ocurre una parte de los cambios de la serie, entonces el árbol permanecerá en un estado inconsistente.
Una solución tradicional para hacer que una base de datos sea tolerante a fallas es agregar una estructura de datos basada en disco adicional, el registro de transacciones, también conocido como registro de escritura anticipada (WAL), junto al árbol B. Es un archivo, al final del cual, estrictamente antes de la modificación del propio árbol B, se escribe la operación prevista. Por lo tanto, si se detecta corrupción de datos durante el autodiagnóstico, la base de datos consulta el registro para limpiarse.
LMDB ha elegido un método diferente como mecanismo de tolerancia a fallas, que se denomina copia en escritura. Su esencia es que en lugar de actualizar los datos en una página existente, primero la copia por completo y realiza todas las modificaciones ya en la copia.
Además, para que los datos actualizados estén disponibles, es necesario cambiar el enlace al nodo que se ha actualizado en el nodo principal en relación con él. Dado que también necesita ser modificado para esto, también se copia previamente. El proceso continúa recursivamente hasta la raíz. Los datos en la metapágina son los últimos en cambiar.
Si el proceso falla repentinamente durante el procedimiento de actualización, no se creará una nueva metapágina o no se escribirá en el disco hasta el final, y su suma de verificación será incorrecta. En cualquiera de estos dos casos, las nuevas páginas serán inaccesibles y las antiguas no se verán afectadas. Esto elimina la necesidad de que LMDB escriba por adelantado el registro para mantener la coherencia de los datos. De facto, la estructura de almacenamiento de datos en el disco, descrita anteriormente, asume simultáneamente su función. La ausencia de un registro de transacciones explícito es una de las características de LMDB, que proporciona una alta velocidad de lectura de datos.
La construcción resultante, llamada árbol B de solo agregar, naturalmente proporciona aislamiento de transacciones y multiversiones. En LMDB, cada transacción abierta tiene asociada una raíz de árbol actualizada. Mientras la transacción no se complete, las páginas del árbol asociadas a ella nunca se cambiarán ni se reutilizarán para nuevas versiones de datos. Por lo tanto, puede trabajar todo el tiempo que desee exactamente con el conjunto de datos que era relevante en el momento. momento en que se abrió la transacción, incluso si el almacenamiento continúa actualizándose activamente en este momento. Esta es la esencia de las versiones múltiples, lo que convierte a LMDB en una fuente de datos ideal para nuestros queridos UICollectionView. Habiendo abierto una transacción, no necesita aumentar la huella de memoria de la aplicación, bombeando apresuradamente los datos actuales en alguna estructura en memoria, sin miedo a quedarse sin nada. Esta característica distingue a LMDB del mismo SQLite, que no puede presumir de un aislamiento tan total. Habiendo abierto dos transacciones en este último y borrando un determinado registro dentro de uno de ellos, ya no se puede obtener el mismo registro dentro del segundo restante.
La otra cara de la moneda es el consumo potencialmente significativamente mayor de memoria virtual. La diapositiva muestra cómo se verá la estructura de la base de datos si se modifica al mismo tiempo con 3 transacciones de lectura abiertas que buscan diferentes versiones de la base de datos. Dado que LMDB no puede reutilizar los nodos a los que se puede acceder desde las raíces asociadas con las transacciones reales, el almacenamiento no tiene más remedio que asignar otra cuarta raíz en la memoria y, una vez más, clonar las páginas modificadas debajo de ella.
Aquí no será superfluo recordar la sección sobre archivos mapeados en memoria. Parece que el consumo adicional de memoria virtual no debería molestarnos mucho, ya que no contribuye a la huella de memoria de la aplicación. Sin embargo, al mismo tiempo, se observó que iOS es muy tacaño al asignarlo, y no podemos proporcionar una región LMDB de 1 terabyte en un servidor o escritorio desde el hombro del maestro y no pensar en esta función en absoluto. Cuando sea posible, debe intentar que la vida útil de las transacciones sea lo más corta posible.
4. Diseñar un esquema de datos sobre la API de clave-valor
Empecemos a analizar la API observando las abstracciones básicas proporcionadas por LMDB: entorno y bases de datos, claves y valores, transacciones y cursores.
Una nota sobre las listas de códigos
Todas las funciones en la API pública de LMDB devuelven el resultado de su trabajo en forma de un código de error, pero en todos los listados posteriores se omite su verificación en aras de la concisión. En la práctica, usamos nuestro propio código para interactuar con el repositorio. Envolturas de C++ , en el que los errores se materializan como excepciones de C++.
Como la forma más rápida de conectar LMDB a un proyecto iOS o macOS, ofrezco mi CocoaPod .
4.1. Abstracciones básicas
Ambiente
Estructura MDB_env Este es el repositorio del estado interno de la LMDB. Familia de funciones prefijadas mdb_env permite configurar algunas de sus propiedades. En el caso más simple, la inicialización del motor se ve así.
mdb_env_create(env);
mdb_env_set_map_size(*env, 1024 * 1024 * 512)
mdb_env_open(*env, path.UTF8String, MDB_NOTLS, 0664);En la aplicación Mail.ru Cloud, cambiamos los valores predeterminados solo para dos parámetros.
El primero es el tamaño del espacio de direcciones virtuales al que se asigna el archivo de almacenamiento. Desafortunadamente, incluso en el mismo dispositivo, el valor específico puede variar significativamente de una ejecución a otra. Para tener en cuenta esta característica de iOS, seleccionamos la cantidad máxima de almacenamiento de forma dinámica. Partiendo de un cierto valor, se reduce sucesivamente a la mitad hasta que la función mdb_env_open no devolverá un resultado que no sea ENOMEM. En teoría, hay una forma opuesta: primero asigne un mínimo de memoria al motor y luego, cuando se reciban errores MDB_MAP_FULL, aumentarlo. Sin embargo, es mucho más espinoso. La razón es que el procedimiento para reasignar la memoria usando la función mdb_env_set_map_size invalida todas las entidades (cursores, transacciones, claves y valores) recibidas del motor anteriormente. Dar cuenta de tal giro de eventos en el código conducirá a una complicación significativa. Sin embargo, si la memoria virtual es muy querida para usted, entonces esta puede ser una razón para mirar la bifurcación que se ha adelantado mucho. , donde entre las características declaradas se encuentra el “ajuste automático sobre la marcha del tamaño de la base de datos”.
El segundo parámetro, cuyo valor predeterminado no nos convenía, regula la mecánica para garantizar la seguridad de los subprocesos. Desafortunadamente, al menos en iOS 10, hay problemas con el soporte de almacenamiento local de subprocesos. Por esta razón, en el ejemplo anterior, el repositorio se abre con la bandera MDB_NOTLS. Además, también requería contenedor de C++ para cortar variables con y en este atributo.
Bases de datos
La base de datos es una instancia separada del árbol B del que hablamos anteriormente. Su apertura se produce dentro de una transacción, lo que en un principio puede parecer un poco extraño.
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 hecho, una transacción en LMDB es una entidad de almacenamiento, no una base de datos específica. Este concepto le permite realizar operaciones atómicas en entidades ubicadas en diferentes bases de datos. En teoría, esto abre la posibilidad de modelar tablas en forma de diferentes bases de datos, pero en un momento fui por el otro lado, que se describe en detalle a continuación.
Claves y valores
Estructura MDB_val modela el concepto de clave y valor. El repositorio no tiene idea de su semántica. Para ella, algo que es diferente es solo una matriz de bytes de un tamaño determinado. El tamaño máximo de clave es de 512 bytes.
typedef struct MDB_val {
size_t mv_size;
void *mv_data;
} MDB_val;La tienda utiliza un comparador para ordenar las claves en orden ascendente. Si no lo reemplaza por el suyo, se utilizará el predeterminado, que los ordena byte a byte en orden lexicográfico.
Transacciones
El dispositivo de transacción se describe en detalle en , por lo que aquí repetiré sus principales propiedades en una breve línea:
- Soporte para todas las propiedades básicas Palabras clave: atomicidad, consistencia, aislamiento y confiabilidad. No puedo dejar de notar que en términos de durabilidad en macOS e iOS, hay un error corregido en MDBX. Puedes leer más en su .
- El enfoque de subprocesos múltiples se describe mediante el esquema de "escritor único / lectores múltiples". Los escritores se bloquean unos a otros, pero no bloquean a los lectores. Los lectores no bloquean a los escritores ni entre ellos.
- Soporte para transacciones anidadas.
- Soporte multiversión.
El multiversioning en LMDB es tan bueno que quiero demostrarlo en acción. El siguiente código muestra que cada transacción funciona exactamente con la versión de la base de datos que era relevante en el momento de su apertura, quedando completamente aislada de todos los cambios posteriores. Inicializar el repositorio y agregarle un registro de prueba no tiene interés, por lo que estos rituales se dejan bajo el spoiler.
Agregar una entrada de prueba
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);Opcionalmente, recomiendo probar el mismo truco con SQLite y ver qué sucede.
Multiversioning trae beneficios muy agradables a la vida de un desarrollador de iOS. Con esta propiedad, puede ajustar fácil y naturalmente la frecuencia de actualización de la fuente de datos para los formularios de pantalla en función de las consideraciones de la experiencia del usuario. Por ejemplo, tomemos una característica de la aplicación Mail.ru Cloud como la carga automática de contenido desde la galería de medios del sistema. Con una buena conexión, el cliente puede agregar varias fotos por segundo al servidor. Si actualizas después de cada descarga UICollectionView con contenido multimedia en la nube del usuario, puede olvidarse de los 60 fps y el desplazamiento suave durante este proceso. Para evitar actualizaciones de pantalla frecuentes, debe limitar de alguna manera la tasa de cambio de datos en la base UICollectionViewDataSource.
Si la base de datos no admite la creación de versiones múltiples y le permite trabajar solo con el estado actual, entonces para crear una instantánea de datos estables en el tiempo, debe copiarla en alguna estructura de datos en memoria o en una tabla temporal. Cualquiera de estos enfoques es muy costoso. En el caso del almacenamiento en memoria, obtenemos tanto los costos de memoria causados por el almacenamiento de objetos construidos como los costos de tiempo asociados con las transformaciones ORM redundantes. En cuanto a la mesa temporal, este es un placer aún más costoso, que solo tiene sentido en casos no triviales.
Multiversioning LMDB resuelve el problema de mantener una fuente de datos estable de una manera muy elegante. Basta con abrir una transacción y listo: hasta que la completemos, se garantiza que el conjunto de datos se corregirá. La lógica de su tasa de actualización ahora está completamente en manos de la capa de presentación, sin sobrecarga de recursos significativos.
Cursores
Los cursores proporcionan un mecanismo para la iteración ordenada sobre pares clave-valor atravesando un árbol B. Sin ellos, sería imposible modelar efectivamente las tablas en la base de datos, a la que nos dirigimos ahora.
4.2. Modelado de tablas
La propiedad de ordenación de claves le permite construir una abstracción de nivel superior, como una tabla sobre abstracciones básicas. Consideremos este proceso en el ejemplo de la tabla principal del cliente en la nube, en la que se almacena en caché la información sobre todos los archivos y carpetas del usuario.
Esquema de tabla
Uno de los escenarios comunes para los que se debe afinar la estructura de una tabla con un árbol de carpetas es seleccionar todos los elementos ubicados dentro de un directorio dado.Un buen modelo de organización de datos para consultas eficientes de este tipo es . Para implementarlo sobre el almacenamiento de clave-valor, es necesario ordenar las claves de los archivos y carpetas de tal manera que se agrupen según su pertenencia al directorio principal. Además, para mostrar el contenido del directorio en la forma familiar para un usuario de Windows (primero las carpetas, luego los archivos, ambos están ordenados alfabéticamente), es necesario incluir los campos adicionales correspondientes en la clave.
La siguiente imagen muestra cómo, según la tarea, puede verse la representación de las claves como una matriz de bytes. Primero se colocan los bytes con el identificador del directorio padre (rojo), luego con el tipo (verde), y ya en la cola con el nombre (azul), al ser ordenados por el comparador LMDB por defecto en orden lexicográfico, se ordenan en la forma requerida. Recorrer secuencialmente las teclas con el mismo prefijo rojo nos brinda los valores asociados con ellas en el orden en que deberían mostrarse en la interfaz de usuario (derecha), sin requerir ningún procesamiento posterior adicional.
Serialización de claves y valores
Hay muchos métodos para serializar objetos en todo el mundo. Como no teníamos otro requisito que la velocidad, elegimos el más rápido posible para nosotros: un volcado de memoria ocupado por una instancia de la estructura del lenguaje C. Por lo tanto, la clave de un elemento de directorio se puede modelar mediante la siguiente estructura NodeKey.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;Ahorrar NodeKey en necesidad de almacenamiento en objeto MDB_val coloque el puntero a los datos en la dirección del comienzo de la estructura y calcule su tamaño con la función sizeof.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = sizeof(NodeKey),
.mv_data = (void *)key
};
}En el primer capítulo sobre los criterios de selección de la base de datos, mencioné la minimización de las asignaciones dinámicas como parte de las operaciones CRUD como un factor de selección importante. Código de función serialize muestra cómo, en el caso de LMDB, se pueden evitar por completo cuando se insertan nuevos registros en la base de datos. La matriz de bytes entrantes del servidor se transforma primero en estructuras de pila y luego se vuelcan trivialmente en el almacenamiento. Dado que tampoco hay asignaciones dinámicas dentro de LMDB, puede obtener una situación fantástica según los estándares de iOS: ¡use solo memoria de pila para trabajar con datos desde la red hasta el disco!
Ordenar claves con un comparador binario
La relación de orden clave está dada por una función especial llamada comparador. Dado que el motor no conoce la semántica de los bytes que contienen, el comparador predeterminado no tiene más remedio que ordenar las claves en orden lexicográfico, recurriendo a su comparación byte a byte. Usarlo para arreglar estructuras es como afeitarse con un hacha. Sin embargo, en casos simples, encuentro aceptable este método. La alternativa se describe a continuación, pero aquí señalaré un par de rastrillos esparcidos por el camino.
Lo primero que hay que tener en cuenta es la representación en memoria de los tipos de datos primitivos. Entonces, en todos los dispositivos Apple, las variables enteras se almacenan en el formato . Esto significa que el byte menos significativo estará a la izquierda y no podrá ordenar números enteros usando su comparación byte por byte. Por ejemplo, intentar hacer esto con un conjunto de números del 0 al 511 dará como resultado el siguiente resultado.
// value (hex dump)
000 (0000)
256 (0001)
001 (0100)
257 (0101)
...
254 (fe00)
510 (fe01)
255 (ff00)
511 (ff01)Para resolver este problema, los números enteros deben almacenarse en la clave en un formato adecuado para el comparador de bytes. Las funciones de la familia ayudarán a llevar a cabo la transformación necesaria. hton* (En particular htons para números de doble byte del ejemplo).
El formato para representar cadenas en programación es, como sabes, todo un . Si la semántica de las cadenas, así como la codificación utilizada para representarlas en la memoria, sugiere que puede haber más de un byte por carácter, entonces es mejor abandonar de inmediato la idea de usar un comparador predeterminado.
Lo segundo a tener en cuenta es compilador de campos de estructura. Debido a ellos, se pueden formar bytes con valores basura en la memoria entre campos, lo que, por supuesto, interrumpe la clasificación de bytes. Para eliminar la basura, debe declarar los campos en un orden estrictamente definido, teniendo en cuenta las reglas de alineación, o usar el atributo en la declaración de la estructura. packed.
Ordenación de claves por un comparador externo
La lógica de comparación de claves puede resultar demasiado compleja para un comparador binario. Una de las muchas razones es la presencia de campos técnicos dentro de las estructuras. Ilustraré su aparición en el ejemplo de una clave que ya nos es familiar para un elemento de directorio.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameBuffer[256];
} NodeKey;A pesar de su sencillez, en la gran mayoría de los casos consume demasiada memoria. El búfer de título es de 256 bytes, aunque en promedio los nombres de archivos y carpetas rara vez superan los 20-30 caracteres.
Una de las técnicas estándar para optimizar el tamaño de un registro es recortarlo para que se ajuste a su tamaño real. Su esencia es que los contenidos de todos los campos de longitud variable se almacenan en un búfer al final de la estructura, y sus longitudes se almacenan en variables separadas.De acuerdo con este enfoque, la clave NodeKey se transforma de la siguiente manera.
typedef struct NodeKey {
EntityId parentId;
uint8_t type;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeKey;Además, durante la serialización, no se especifica como el tamaño de los datos sizeof toda la estructura, y el tamaño de todos los campos es de longitud fija más el tamaño de la parte realmente utilizada del búfer.
MDB_val serialize(NodeKey * const key) {
return MDB_val {
.mv_size = offsetof(NodeKey, nameBuffer) + key->nameLength,
.mv_data = (void *)key
};
}Como resultado de la refactorización, obtuvimos un ahorro importante en el espacio que ocupan las teclas. Sin embargo, debido al campo técnico nameLength, el comparador binario predeterminado ya no es adecuado para la comparación de claves. Si no lo reemplazamos con el nuestro, entonces la longitud del nombre será un factor más prioritario en la clasificación que el nombre mismo.
LMDB permite que cada base de datos tenga su propia función de comparación de claves. Esto se hace usando la función mdb_set_compare estrictamente antes de abrir. Por razones obvias, una base de datos no se puede cambiar a lo largo de su vida. A la entrada, el comparador recibe dos claves en formato binario, ya la salida devuelve el resultado de la comparación: menor que (-1), mayor que (1) o igual (0). Pseudocódigo para NodeKey tiene este aspecto.
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 // ...
}Siempre que todas las claves en la base de datos sean del mismo tipo, es legal convertir incondicionalmente su representación de bytes al tipo de estructura de aplicación de la clave. Hay un matiz aquí, pero se discutirá un poco más abajo en la subsección "Lectura de registros".
Serialización de valores
Con las claves de los registros almacenados, LMDB trabaja de forma extremadamente intensa. Se comparan entre sí en el marco de cualquier operación de aplicación, y el rendimiento de toda la solución depende de la velocidad del comparador. En un mundo ideal, el comparador binario predeterminado debería ser suficiente para comparar claves, pero si realmente tuviera que usar el suyo propio, entonces el procedimiento para deserializar las claves debería ser lo más rápido posible.
La base de datos no está particularmente interesada en la parte de valor del registro (valor). Su conversión de una representación de bytes a un objeto ocurre solo cuando el código de la aplicación ya lo requiere, por ejemplo, para mostrarlo en la pantalla. Dado que esto sucede relativamente raramente, los requisitos para la velocidad de este procedimiento no son tan críticos, y en su implementación somos mucho más libres para centrarnos en la conveniencia.Por ejemplo, para serializar metadatos sobre archivos que aún no se han descargado, usamos NSKeyedArchiver.
NSData *data = serialize(object);
MDB_val value = {
.mv_size = data.length,
.mv_data = (void *)data.bytes
};Sin embargo, hay ocasiones en las que el rendimiento sí importa. Por ejemplo, al guardar metainformación sobre la estructura de archivos de la nube del usuario, usamos el mismo volcado de memoria del objeto. Lo más destacado de la tarea de generar su representación serializada es el hecho de que los elementos de un directorio están modelados por una jerarquía de clases.
Para su implementación en el lenguaje C, los campos específicos de los herederos se sacan en estructuras separadas, y su conexión con la base se especifica a través de un campo del tipo unión. El contenido real de la unión se especifica a través del atributo técnico de tipo.
typedef struct NodeValue {
EntityId localId;
EntityType type;
union {
FileInfo file;
DirectoryInfo directory;
} info;
uint8_t nameLength;
uint8_t nameBuffer[256];
} NodeValue;Agregar y actualizar entradas
La clave serializada y el valor se pueden agregar a la tienda. Para ello se utiliza la función mdb_put.
// key и value имеют тип MDB_val
mdb_put(..., &key, &value, MDB_NOOVERWRITE);En la etapa de configuración, se puede permitir o prohibir que el repositorio almacene varios registros con la misma clave. Si se prohíbe la duplicación de claves, al insertar un registro, puede determinar si se permite o no actualizar un registro ya existente. Si el deshilachado solo puede ocurrir como resultado de un error en el código, puede asegurarse especificando la bandera NOOVERWRITE.
Registros de lectura
La función para leer registros en LMDB es mdb_get. Si el par clave-valor está representado por estructuras volcadas previamente, entonces este procedimiento se ve así.
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 lista presentada muestra cómo la serialización a través de un volcado de estructuras le permite deshacerse de las asignaciones dinámicas no solo al escribir, sino también al leer datos. Derivado de la función mdb_get el puntero mira exactamente a la dirección de memoria virtual donde la base de datos almacena la representación de bytes del objeto. De hecho, obtenemos una especie de ORM, casi gratis, que proporciona una velocidad de lectura de datos muy alta. Con toda la belleza del enfoque, es necesario recordar varias características asociadas con él.
- Para una transacción de solo lectura, se garantiza que un puntero a una estructura de valor seguirá siendo válido solo hasta que se cierre la transacción. Como se señaló anteriormente, las páginas del árbol B en el que reside el objeto, gracias al principio de copia en escritura, permanecen sin cambios siempre que al menos una transacción se refiera a ellas. Al mismo tiempo, tan pronto como se complete la última transacción asociada con ellos, las páginas se pueden reutilizar para nuevos datos. Si es necesario que los objetos sobrevivan a la transacción que los creó, aún deben copiarse.
- Para una transacción de lectura y escritura, el puntero al valor de estructura resultante será válido solo hasta el primer procedimiento de modificación (escritura o eliminación de datos).
- Aun cuando la estructura
NodeValueno completo, pero recortado (consulte la subsección "Pedido de claves por un comparador externo"), a través del puntero, puede acceder fácilmente a sus campos. ¡Lo principal es no desreferenciarlo! - En ningún caso podrá modificar la estructura a través del puntero recibido. Todos los cambios deben realizarse únicamente a través del método
mdb_put. Sin embargo, con todas las ganas de hacer esto, no funcionará, ya que el área de memoria donde se encuentra esta estructura está mapeada en modo de solo lectura. - Reasignar un archivo al espacio de direcciones de un proceso para, por ejemplo, aumentar el tamaño máximo de almacenamiento usando la función
mdb_env_set_map_sizeinvalida por completo todas las transacciones y entidades relacionadas en general y los punteros para leer objetos en particular.
Finalmente, otra característica es tan insidiosa que la revelación de su esencia no cabe en un solo punto más. En el capítulo sobre el árbol B, di un diagrama de la organización de sus páginas en la memoria. De ello se deduce que la dirección del comienzo del búfer con datos serializados puede ser absolutamente arbitraria. Por ello, el puntero hacia ellos, obtenido en la estructura MDB_val y la conversión a un puntero a una estructura generalmente no está alineada. Al mismo tiempo, las arquitecturas de algunos chips (en el caso de iOS, es armv7) requieren que la dirección de cualquier dato sea un múltiplo del tamaño de una palabra de máquina o, en otras palabras, el bitness del sistema. (para armv7, esto es 32 bits). En otras palabras, una operación como *(int *foo)0x800002 en ellos se equipara a la fuga y conduce a la ejecución con un veredicto EXC_ARM_DA_ALIGN. Hay dos maneras de evitar un destino tan triste.
El primero es copiar los datos en una estructura alineada conocida de antemano. Por ejemplo, en un comparador personalizado, esto se reflejará de la siguiente 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 es notificar al compilador por adelantado que las estructuras con una clave y un valor pueden no estar alineadas usando un atributo. aligned(1). En ARM se puede obtener el mismo efecto y usando el atributo empaquetado. Teniendo en cuenta que también contribuye a la optimización del espacio ocupado por la estructura, este método me parece preferible, aunque aumentar el costo de las operaciones 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 rango
Para iterar sobre un grupo de registros, LMDB proporciona una abstracción de cursor. Veamos cómo trabajar con él usando el ejemplo de una tabla con metadatos de nube de usuario que ya nos son familiares.
Como parte de la visualización de una lista de archivos en un directorio, debe encontrar todas las claves con las que están asociados sus archivos y carpetas secundarios. En las subsecciones anteriores, ordenamos las claves NodeKey para que primero se ordenen por su ID de directorio principal. Así, técnicamente, la tarea de obtener el contenido de una carpeta se reduce a colocar el cursor en el límite superior de un grupo de claves con un prefijo dado, seguido de una iteración al límite inferior.
Puede encontrar el límite superior "en la frente" mediante una búsqueda secuencial. Para hacer esto, el cursor se coloca al principio de la lista completa de claves en la base de datos y luego se incrementa hasta que la clave con el identificador del directorio principal aparece debajo. Este enfoque tiene 2 inconvenientes obvios:
- La complejidad lineal de la búsqueda, aunque como sabes, en árboles en general y en un B-tree en particular, se puede hacer en tiempo logarítmico.
- En vano, todas las páginas que preceden a la deseada se suben del archivo a la memoria principal, lo cual es extremadamente costoso.
Afortunadamente, la API de LMDB proporciona una forma eficiente de posicionar inicialmente el cursor. Para hacer esto, debe formar una clave de este tipo, cuyo valor será menor o igual que la clave ubicada en el límite superior del intervalo. . Por ejemplo, en relación con la lista de la figura anterior, podemos hacer una clave en la que el campo parentId será igual a 2, y todos los demás se llenan con ceros. Tal clave parcialmente llena se alimenta a la entrada de la función mdb_cursor_get indicando 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);Si se encuentra el límite superior del grupo de claves, iteramos sobre él hasta que nos encontremos o la clave con otro parentId, o las llaves no se agotará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 groupLo bueno es que, como parte de la iteración con mdb_cursor_get, no solo obtenemos la clave, sino también el valor. Si, para cumplir con las condiciones de selección, es necesario verificar, entre otras cosas, los campos de la parte de valor del registro, entonces son bastante accesibles para ellos sin gestos adicionales.
4.3. Modelado de relaciones entre tablas
Hasta la fecha, hemos logrado considerar todos los aspectos del diseño y el trabajo con una base de datos de una sola tabla. Podemos decir que una tabla es un conjunto de registros ordenados que consisten en pares clave-valor del mismo tipo. Si muestra una clave como un rectángulo y su valor asociado como un cuadro, obtiene un diagrama visual de la base de datos.
Sin embargo, en la vida real, rara vez es posible arreglárselas con tan poca sangre. A menudo en una base de datos se requiere, en primer lugar, tener varias tablas y, en segundo lugar, realizar selecciones en ellas en un orden diferente a la clave principal. Esta última sección está dedicada a los temas de su creación e interconexión.
Tablas de índice
La aplicación en la nube tiene una sección de "Galería". Muestra contenido multimedia de toda la nube, ordenado por fecha. Para la implementación óptima de dicha selección, junto a la tabla principal, debe crear otra con un nuevo tipo de claves. Contendrán un campo con la fecha de creación del archivo, que actuará como criterio principal de clasificación. Dado que las nuevas claves hacen referencia a los mismos datos que las claves de la tabla subyacente, se denominan claves de índice. Están resaltados en naranja en la imagen de abajo.
Para poder separar las claves de diferentes tablas entre sí dentro de una misma base de datos, se ha añadido a todas ellas un campo técnico adicional tableId. Al convertirlo en la prioridad más alta para la clasificación, agruparemos las claves primero por tablas y ya dentro de las tablas, de acuerdo con nuestras propias reglas.
La clave de índice se refiere a los mismos datos que la clave principal. La implementación sencilla de esta propiedad al asociarla con una copia de la parte de valor de la clave principal es subóptima desde varios puntos de vista a la vez:
- Desde el punto de vista del espacio ocupado, los metadatos pueden ser bastante ricos.
- Desde el punto de vista del rendimiento, ya que al actualizar los metadatos del nodo, deberá sobrescribir dos claves.
- Desde el punto de vista del soporte de código, después de todo, si olvidamos actualizar los datos de una de las claves, obtendremos un error sutil de inconsistencia de datos en el almacenamiento.
A continuación, consideraremos cómo eliminar estas deficiencias.
Organización de relaciones entre tablas.
El patrón es muy adecuado para vincular una tabla de índice con la principal. "clave como valor". Como su nombre lo indica, la parte del valor del registro de índice es una copia del valor de la clave principal. Este enfoque elimina todas las desventajas enumeradas anteriormente asociadas con el almacenamiento de una copia de la parte del valor del registro principal. La única tarifa es que para obtener el valor mediante la clave de índice, debe realizar 2 consultas a la base de datos en lugar de una. Esquemáticamente, el esquema de la base de datos resultante es el siguiente.
Otro patrón para organizar las relaciones entre tablas es "llave redundante". Su esencia es agregar atributos adicionales a la clave, que no son necesarios para ordenar, sino para recrear la clave asociada.Sin embargo, hay ejemplos reales de su uso en la aplicación Mail.ru Cloud, para evitar profundizar en el contexto de marcos específicos de iOS, daré un ejemplo ficticio, pero más comprensible.
Los clientes móviles en la nube tienen una página que muestra todos los archivos y carpetas que el usuario ha compartido con otras personas. Dado que hay relativamente pocos archivos de este tipo, y hay mucha información específica sobre la publicidad asociada con ellos (a quién se otorga acceso, con qué derechos, etc.), no será racional cargarlo con la parte de valor de la entrada en la tabla principal. Sin embargo, si desea mostrar dichos archivos sin conexión, aún debe almacenarlos en algún lugar. Una solución natural es crear una tabla separada para ello. En el siguiente diagrama, su clave tiene el prefijo "P", y el marcador de posición "propname" se puede reemplazar con el valor más específico "public info".
Todos los metadatos únicos, por los cuales se creó la nueva tabla, se mueven a la parte de valor del registro. Al mismo tiempo, no quiero duplicar los datos sobre archivos y carpetas que ya están almacenados en la tabla principal. En su lugar, se agregan datos redundantes a la clave "P" en forma de campos "ID de nodo" y "marca de tiempo". Gracias a ellos, puede construir una clave de índice, mediante la cual puede obtener la clave principal, mediante la cual, finalmente, puede obtener los metadatos del nodo.
Conclusión
Evaluamos positivamente los resultados de la implementación de LMDB. Después de eso, el número de congelamientos de aplicaciones disminuyó en un 30%.
Los resultados del trabajo realizado han encontrado respuesta fuera del equipo de iOS. Actualmente, una de las secciones principales de "Archivos" en la aplicación de Android también ha cambiado a usar LMDB, y otras partes están en camino. El lenguaje C, en el que se implementa el almacenamiento de clave-valor, fue una buena ayuda para que la aplicación se vinculara inicialmente a su alrededor entre plataformas en el lenguaje C ++. Para una conexión perfecta de la biblioteca C ++ resultante con el código de la plataforma en Objective-C y Kotlin, se utilizó un generador de código de Dropbox, pero esa es otra historia.
Fuente: habr.com