En informática, un DBM es una biblioteca y un formato de archivo que proporciona un acceso rápido a los datos con una sola tecla. Una base de datos de valores clave del Unix original , dbm es un ejemplo temprano de un sistema NoSQL . [1] [2] [3]
Historia
El formato de archivo y biblioteca dbm original era un motor de base de datos simple , originalmente escrito por Ken Thompson y lanzado por AT&T en 1979. El nombre es un acrónimo de tres letras para DataBase Manager , y también puede referirse a la familia de motores de base de datos con API y características. derivado del dbm original .
Los dbm biblioteca almacena arbitraria de datos mediante el uso de una sola tecla (una clave primaria ) en de tamaño fijo cubos y usos hash técnicas para permitir la recuperación rápida de los datos por la clave.
El esquema de hash utilizado es una forma de hash extensible , de modo que el esquema de hash se expande a medida que se agregan nuevos depósitos a la base de datos, lo que significa que, cuando está casi vacía, la base de datos comienza con un depósito, que luego se divide cuando se llena. Los dos depósitos secundarios resultantes se dividirán cuando se llenen, por lo que la base de datos crece a medida que se agregan claves.
La biblioteca dbm y sus derivados son bases de datos prerrelacionales : administran matrices asociativas , implementadas como tablas hash en el disco . En la práctica, pueden ofrecer una solución más práctica para el almacenamiento de alta velocidad al que se accede mediante clave, ya que no requieren la sobrecarga de conexión y preparación de consultas. Esto se equilibra con el hecho de que, por lo general, solo se pueden abrir para escritura mediante un único proceso a la vez. Un demonio de agente puede manejar solicitudes de múltiples procesos, pero introduce una sobrecarga de IPC .
Implementaciones
La biblioteca dbm original de AT&T ha sido reemplazada por sus muchas implementaciones sucesoras. Entre los ejemplos notables se incluyen: [3]
- ndbm ("nuevo dbm"), basado en el dbm original con algunas características nuevas.
- GDBM ("GNU dbm"), reescritura de GNU de la biblioteca que implementa las características de ndbm y su propia interfaz.
- sdbm ("small dbm"), una reescritura de dominio público de dbm . Es parte de las distribuciones estándar de Perl y Ruby . [4] [5]
- qdbm, un mayor rendimiento dbm empleando muchas de las mismas técnicas que Tokyo Cabinet / Kyoto. Escrito por el mismo autor antes de pasar a los gabinetes. [6]
- tdb, una base de datos simple utilizada por Samba que admite varios escritores. Tiene una API basada en gdbm. [7]
- Berkeley DB , 1991 reemplazo de ndbm por Sleepycat Software (ahora Oracle ) creado para evitar los derechos de autor de AT&T Unix en BSD . Cuenta con muchas extensiones como paralelismo, control transaccional, hash y almacenamiento de árbol B.
- LMDB : implementación de árbol B + mapeado en memoria de copia en escritura en C con una API de estilo Berkeley.
Las siguientes bases de datos están inspiradas en dbm, pero no proporcionan directamente una interfaz dbm, aunque sería trivial encapsular una:
- Tokyo Cabinet : implementación de C que emplea tablas hash , árbol B + o estructuras de matriz de longitud fija de FAL Labs. Tiene mejoras en el paralelismo. [8]
- Kyoto Cabinet : implementación de C ++ que emplea tablas hash , árbol B + o estructuras de matriz de longitud fija de FAL Labs. Tiene mejoras en el paralelismo. [9]
- Tkrzw , sucesor con licencia de Apache 2.0 del gabinete de Kyoto
- WiredTiger : base de datos con almacenamiento tradicional orientado a filas y a columnas.
Disponibilidad
En 2001, la implementación ndbm de DBM era estándar en Solaris e IRIX, mientras que gdbm es omnipresente en Linux . Las implementaciones de Berkeley DB eran estándar en algunos sistemas operativos gratuitos. [2] [10] Después de un cambio de licencia de Berkeley DB a GNU AGPL en 2013, proyectos como Debian se han trasladado a LMDB. [11]
Fiabilidad
Una prueba de fuzzing AFL de 2018 contra muchas bases de datos de la familia DBM expuso muchos problemas en las implementaciones cuando se trata de archivos de base de datos corruptos o no válidos. Solo freecdb de Daniel J. Bernstein no mostró fallas. Los autores de gdbm, tdb y lmdb respondieron rápidamente. Berkeley DB se quedó atrás debido a la gran cantidad de otros problemas; [10] las correcciones serían irrelevantes para los usuarios de software de código abierto debido a que el cambio de licencia los bloqueaba en una versión anterior. [11]
Ver también
- Base de datos incrustada
- Base de datos de archivos planos
- ISAM
- Base de datos de valores-clave
- Base de datos móvil
- NoSQL
- Semáforo (programación)
Referencias
- ^ Kew 2007 , p. 80: "Los DBM han estado con nosotros desde los primeros días de la informática, cuando se reconoció la necesidad de búsquedas rápidas por clave. El DBM original es una biblioteca y un formato de archivo basados en UNIX para un acceso rápido y altamente escalable a los datos por clave. seguido (en orden) por NDBM ('nuevo DBM'), GDBM ('GNU DBM') y Berkeley DB. Este último es, con mucho, el más avanzado y el único DBM en desarrollo activo en la actualidad. Sin embargo, todos los Los DBM desde NDBM en adelante proporcionan la misma funcionalidad básica que utilizan la mayoría de los programas, incluido Apache. Un SDBM de implementación mínima también se incluye con APR y está disponible para las aplicaciones junto con los otros DBM.
Aunque NDBM ahora es antiguo, como la ciudad llamada New Town ('Neapolis') por los griegos alrededor del año 600 a. C. y todavía se llama Nápoles en la actualidad; sigue siendo el DBM de referencia. NDBM fue utilizado por los primeros módulos de Apache, como las versiones Apache 1.x demod_auth_dbm
ymod_rewrite
. Tanto GDBM como Berkeley DB proporcionan emulaciones de NDBM , y las distribuciones de Linux se envían con una u otra de estas emulaciones en lugar e del NDBM 'real', que está excluido por razones de licencia. Desafortunadamente, los distintos formatos de archivo son totalmente incompatibles y existen diferencias sutiles en el comportamiento con respecto al bloqueo de la base de datos. Estos problemas llevaron a un flujo constante de usuarios de Linux a informar problemas con DBM en Apache 1.x. " - ↑ a b Hazel , 2001 , p. 500: "El formato [de clave única] más común se llama DBM. La mayoría de las versiones modernas de Unix tienen una biblioteca DBM instalada como estándar, aunque esto no es cierto para algunos sistemas más antiguos. Las dos bibliotecas DBM más comunes son ndbm (estándar en Solaris e IRIX) y Berkeley DB Versión 2 o 3 (estándar en varios sistemas operativos gratuitos). Exim es compatible con ambos, así como con la versión 1 de Berkeley DB, gdbm y tdb ".
- ^ a b Ladd & O'Donnell 2001 , págs. 823-824: "La mayoría de los sistemas UNIX tienen algún tipo de base de datos DBM. DBM es un conjunto de rutinas de biblioteca que administra archivos de datos que constan de pares de clave y valor. Las rutinas DBM controlan cómo los usuarios ingresan y recuperan información de la base de datos. Aunque no es el mecanismo más poderoso para almacenar información, el uso de DBM es un método más rápido para recuperar información que el uso de un archivo plano. Debido a que la mayoría de los sitios de UNIX usan una de las bibliotecas de DBM, las herramientas necesita almacenar su información en una base de datos DBM que están disponibles.
Existen casi tantos tipos de bibliotecas DBM como sistemas UNIX. Aunque la mayoría de estas bibliotecas son compatibles entre sí, todas funcionan básicamente de la misma manera ...
A continuación, se muestra una lista de algunas de las bibliotecas DBM más populares disponibles:- DBM : DBM almacena la base de datos en dos archivos. El primero tiene la extensión
.Pag
y contiene el mapa de bits. El segundo, que tiene la extensión.Dir
, contiene los datos. - NDBM : NDBM es muy parecido a DBM pero con algunas características adicionales; fue escrito para proporcionar mejores métodos de almacenamiento y recuperación. Además, NDBM le permite abrir muchas bases de datos, a diferencia de DBM, en el que solo puede tener una base de datos abierta dentro de su script. Como DBM, NDBM almacena su información en dos archivos usando las extensiones
.Pag
y.Dir
. - SDBM : SDBM viene con el archivo Perl, que se ha adaptado a muchas plataformas. Por lo tanto, puede usar bases de datos DBM siempre que exista una versión de Perl para su computadora. SDBM se escribió para que coincida con las funciones proporcionadas con NDBM, por lo que la portabilidad del código no debería ser un problema. Perl está disponible en casi todas las plataformas populares.
- GDBM : GDBM es la versión GNU de la familia DBM de rutinas de bases de datos. GDBM también le permite almacenar datos en caché, lo que reduce el tiempo que lleva escribir en la base de datos. La base de datos no tiene límite de tamaño; su tamaño depende completamente de los recursos de su sistema. Los archivos de base de datos GDBM tienen la extensión
.Db
. A diferencia de DBM y NDBM, que usan dos archivos, GDBM solo usa un archivo. - Berkeley db : Berkeley db amplía significativamente las rutinas originales de DBM. La base de datos de Berkeley usa tablas hash al igual que las otras bases de datos DBM, pero la biblioteca también puede crear bases de datos basadas en un árbol binario equilibrado ordenado (
BTREE
) y almacenar información con un número de línea de registro (RECNO
). El método que utilice depende completamente de cómo desee almacenar y recuperar la información de una base de datos. Berkeley db crea solo un archivo, que no tiene extensión ".
- DBM : DBM almacena la base de datos en dos archivos. El primero tiene la extensión
- ^ yigit, ozan. "sdbm.bun" . cse.yorku.ca . Consultado el 8 de mayo de 2019 .
- ^ "clase SDBM" . Documentación para Ruby 2.4.0 .
Tenga en cuenta que Ruby viene con el código fuente para SDBM, mientras que las bibliotecas estándar DBM y GDBM se basan en bibliotecas y encabezados externos.
- ^ "QDBM: Quick Database Manager" . fallabs.com . 2006.
- ^ "tdb: página principal" . tdb.samba.org .
- ^ "Tokyo Cabinet 第 1 版 基本 仕 様 書" [Especificaciones fundamentales de la versión 1 de Tokyo Cabinet]. Fall Labs (en japonés). 5 de agosto de 2010. Archivado desde el original el 28 de octubre de 2018 . Consultado el 25 de mayo de 2019 .
Gabinete de Tokio は GDBM や QDBM の 後 継 と し て 次 の 点 を 目標 と し て 開 発 さ れ ま し た。 こ れ ら の 目標 は さ れ て お り 、 Gabinete de Tokio は 従 を 来 の す 来 の
- ^ "Tokyo Cabinet 第 1 版 基本 仕 様 書" [Especificaciones fundamentales de la versión 1 de Tokyo Cabinet]. Fall Labs (en japonés). 5 de agosto de 2010. Archivado desde el original el 28 de octubre de 2018 . Consultado el 25 de mayo de 2019 .
Gabinete de Tokio は GDBM や QDBM の 後 継 と し て 次 の 点 を 目標 と し て 開 発 さ れ ま し た。 こ れ ら の 目標 は さ れ て お り 、 Gabinete de Tokio は 従 を 来 の す 来 の
- ^ a b Debroux, Lionel (16 de junio de 2018). "oss-security - Diversión con bases de datos de tipo DBM ..." openwall.com .
- ^ a b Surý, Ondřej (19 de junio de 2014). "Nuevo objetivo del proyecto: deshacerse de Berkeley DB (post jessie)" . debian-devel (lista de correo). Debian .
Bibliografía
- Hazel, Philip (2001). Exim: el agente de transferencia de correo . O'Reilly.
- Ladd, Eric; O'Donnell, Jim (2001). Utilizando XHTML, XML y Java 2: Platinum Edition . What. ISBN 9780789724731.
- Kew, Nick (2007). El libro de módulos de Apache: desarrollo de aplicaciones con Apache . Prentice Hall Professional. ISBN 9780132704502.
- Biblioteca SDBM @ Apache
- Matthew, Neil; Piedras, Richard (2008). "Bases de datos". Comenzando la programación de Linux . Wiley.
- Olson, Michael A .; Bostic, Keith; Seltzer, Margo (1999). "Berkeley DB" (PDF) . Actas de FREENIX Track: Conferencia técnica anual de 1999 USENIX .