DBM (informática)

En informática, DBM es una biblioteca y un formato de archivo que proporciona acceso rápido y con una sola tecla a los datos. Siendo una base de datos clave-valor del Unix original, dbm es uno de los primeros ejemplos de un sistema NoSQL.^[1]^[2]^[3]

Historia

La biblioteca original y el forma de archivo de dbm eran simplemente un motor de base de datos, escrito por Ken Thompson y publicado por AT&T en 1979. El nombre es una sigla de tres letras que significan DataBase Manager (Gestor de Bases de Datos), que también puede referenciar a la familia de motores de base de datos con APIs y funciones derivadas del primer dbm.

La biblioteca dbm almacena datos arbitrarios usando una sola clave (una clave primaria) en contenedores de tamaño fijo y usa técnicas de hashing para permitir la recuperación rápida de los datos por 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 disco. En la práctica, pueden ofrecer una solución más práctica para el almacenamiento de alta velocidad al que se accede por 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 por un único proceso a la vez. Un agente demonio 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 muchas de sus implementaciones sucesivas. Algunos ejemplos notables son:^[3]

ndbm ("new 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 dbm de mayor rendimiento que utiliza muchas de las mismas técnicas que Tokyo/Kyoto Cabinet. 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+ de copia en escritura mapeada en memoria 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 empaquetar una:

Tokyo Cabinet: Implementación de C empleando 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.^[8]
Tkrzw, sucesor con licencia de Apache 2.0 de Kyoto Cabinet.
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, donde gdbm es ubicuo en Linux . Las implementaciones Berkeley DB eran comunes en algunos sistemas operativos gratuito.^[2]^[9] Después de un cambio de licencia de Berkeley DB a GNU AGPL en 2013, proyectos como Debian se han trasladado a LMDB.^[10]

Fiabilidad

En 2018, un test de fuzzing AFL, usado en muchas bases de datos de la familia DBM, expuso bastantes problemas en la implementación cuando se intenta corromper o invalidar ficheros de la base de datos. Solo freecdb de Daniel J. Bernstein no tuvo problemas. Los autores de gdbm, tdb y lmdb respondieron rápidamente. Berkeley DB se quedó atrás debido a la gran cantidad de otros problemas;^[9] 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.^[10]

Véase también

Referencias

↑ Kew, 2007, p. 80: "DBMs have been with us since the early days of computing, when the need for fast keyed lookups was recognized. The original DBM is a UNIX-based library and file format for fast, highly-scalable keyed access to data. It was followed (in order) by NDBM ('new DBM'), GDBM ('GNU DBM'), and the Berkeley DB. This last is by far the most advanced, and the only DBM under active development today. Nevertheless, all of the DBMs from NDBM onward provide the same core functionality used by most programs, including Apache. A minimal-implementation SDBM is also bundled with APR, and is available to applications along with the other DBMs.
Although NDBM is now old - like the city named New Town ('Neapolis') by the Greeks in about 600BC and still called Naples today - it remains the baseline DBM. NDBM was used by early Apache modules such as the Apache 1.x versions of mod_auth_dbm and mod_rewrite. Both GDBM and Berkeley DB provide NDBM emulations, and Linux distributions ship with one or other of these emulations in place of the 'real' NDBM, which is excluded for licensing reasons. Unfortunately, the various file formats are totally incompatible, and there are subtle differences in behaviour concerning database locking. These issues led a steady stream of Linux users to report problems with DBMs in Apache 1.x."
↑ ^a ^b Hazel, 2001, p. 500: "The most common [single-key] format is called DBM. Most modern versions of Unix have a DBM library installed as standard, though this is not true of some older systems. The two most common DBM libraries are ndbm (standard on Solaris and IRIX) and Berkeley DB Version 2 or 3 (standard on several free operating systems). Exim supports both of these, as well as the older Berkeley DB Version 1, gdbm, and tdb."
↑ ^a ^b
Ladd y O'Donnell, 2001, pp. 823-824: "Most UNIX systems have some kind of DBM database. DBM is a set of library routines that manages data files consisting of key and value pairs. The DBM routines control how users enter and retrieve information from the database. Although it isn't the most powerful mechanism for storing information, using DBM is a faster method of retrieving information than using a flat file. Because most UNIX sites use one of the DBM libraries, the tools you need to store your information in a DBM database are readily available.
Almost as many flavors of the DBM libraries exist as there are UNIX systems. Although most of these libraries are compatible with each other, they all basically work the same way...
A list follows of some of the most popular DBM libraries available:
- DBM - DBM stores the database in two files. The first has the extension .Pag and contains the bitmap. The second, which has the extension .Dir, contains the data.
- NDBM - NDBM is much like DBM but with a few additional features; it was written to provide better storage and retrieval methods. Also, NDBM enables you to open many databases, unlike DBM, in which you are allowed to have only one database open within your script. Like DBM, NDBM stores its information in two files using the extensions .Pag and .Dir.
- SDBM - SDBM comes with the Perl archive, which has been ported to many platforms. Therefore, you can use DBM databases as long as a version of Perl exists for your computer. SDBM was written to match the functions provided with NDBM, so portability of code shouldn't be a problem. Perl is available on just about all popular platforms.
- GDBM - GDBM is the GNU version of the DBM family of database routines. GDBM also enables you to cache data, reducing the time that it takes to write to the database. The database has no size limit; its size depends completely on your system's resources. GDBM database files have the extension .Db. Unlike DBM and NDBM, both of which use two files, GDBM only uses one file.
- Berkeley db - The Berkeley db expands on the original DBM routines significantly. The Berkeley db uses hashed tables the same as the other DBM databases, but the library also can create databases based on a sorted balanced binary tree (BTREE) and store information with a record line number (RECNO). The method that you use depends completely on how you want to store and retrieve the information from a database. Berkeley db creates only one file, which has no extension."
↑ yigit, ozan. «sdbm.bun». cse.yorku.ca. Consultado el 8 de mayo de 2019.
↑ «class SDBM». Documentation for Ruby 2.4.0. «Note that Ruby comes with the source code for SDBM, while the DBM and GDBM standard libraries rely on external libraries and headers.»
↑ «QDBM: Quick Database Manager». fallabs.com. 2006. Archivado desde el original el 27 de febrero de 2020. Consultado el 28 de diciembre de 2020.
↑ «tdb: Main Page». tdb.samba.org.
↑ ^a ^b «Tokyo Cabinet第1版基本仕様書» [Fundamental Specifications of Tokyo Cabinet Version 1]. 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. «Tokyo CabinetはGDBMやQDBMの後継として次の点を目標として開発されました。これらの目標は達成されており、Tokyo Cabinetは従来のDBMを置き換える製品だと言えます。».
↑ ^a ^b Debroux, Lionel (16 de junio de 2018). «oss-security - Fun with DBM-type databases...». openwall.com.
↑ ^a ^b Surý, Ondřej (2014-06-19), «New project goal: Get rid of Berkeley DB (post jessie)», Debian, https://lists.debian.org/debian-devel/2014/06/msg00338.html.

Bibliografía

Hazel, Philip (2001). Exim: The Mail Transfer Agent. O'Reilly.
Ladd, Eric; O'Donnell, Jim (2001). Using XHTML, XML and Java 2: Platinum Edition. Que. ISBN 9780789724731.
Kew, Nick (2007). The Apache Modules Book: Application Development with Apache. Prentice Hall Professional. ISBN 9780132704502.

Biblioteca SDBM @ Apache
Matthew, Neil; Stones, Richard (2008). «Databases». Beginning Linux Programming. Wiley.
Olson, Michael A. (1999). «Berkeley DB». Proceedings of the FREENIX Track:1999 USENIX Annual Technical Conference.

Datos: Q961733

[2007-kew-apache-1] Kew, 2007, p. 80: "DBMs have been with us since the early days of computing, when the need for fast keyed lookups was recognized. The original DBM is a UNIX-based library and file format for fast, highly-scalable keyed access to data. It was followed (in order) by NDBM ('new DBM'), GDBM ('GNU DBM'), and the Berkeley DB. This last is by far the most advanced, and the only DBM under active development today. Nevertheless, all of the DBMs from NDBM onward provide the same core functionality used by most programs, including Apache. A minimal-implementation SDBM is also bundled with APR, and is available to applications along with the other DBMs.
Although NDBM is now old - like the city named New Town ('Neapolis') by the Greeks in about 600BC and still called Naples today - it remains the baseline DBM. NDBM was used by early Apache modules such as the Apache 1.x versions of mod_auth_dbm and mod_rewrite. Both GDBM and Berkeley DB provide NDBM emulations, and Linux distributions ship with one or other of these emulations in place of the 'real' NDBM, which is excluded for licensing reasons. Unfortunately, the various file formats are totally incompatible, and there are subtle differences in behaviour concerning database locking. These issues led a steady stream of Linux users to report problems with DBMs in Apache 1.x."

[2001-hazel-exim-2] Hazel, 2001, p. 500: "The most common [single-key] format is called DBM. Most modern versions of Unix have a DBM library installed as standard, though this is not true of some older systems. The two most common DBM libraries are ndbm (standard on Solaris and IRIX) and Berkeley DB Version 2 or 3 (standard on several free operating systems). Exim supports both of these, as well as the older Berkeley DB Version 1, gdbm, and tdb."

[2001-ladd-odonell-xhtml-3] Ladd y O'Donnell, 2001, pp. 823-824: "Most UNIX systems have some kind of DBM database. DBM is a set of library routines that manages data files consisting of key and value pairs. The DBM routines control how users enter and retrieve information from the database. Although it isn't the most powerful mechanism for storing information, using DBM is a faster method of retrieving information than using a flat file. Because most UNIX sites use one of the DBM libraries, the tools you need to store your information in a DBM database are readily available.
Almost as many flavors of the DBM libraries exist as there are UNIX systems. Although most of these libraries are compatible with each other, they all basically work the same way...
A list follows of some of the most popular DBM libraries available:
DBM - DBM stores the database in two files. The first has the extension .Pag and contains the bitmap. The second, which has the extension .Dir, contains the data.
NDBM - NDBM is much like DBM but with a few additional features; it was written to provide better storage and retrieval methods. Also, NDBM enables you to open many databases, unlike DBM, in which you are allowed to have only one database open within your script. Like DBM, NDBM stores its information in two files using the extensions .Pag and .Dir.
SDBM - SDBM comes with the Perl archive, which has been ported to many platforms. Therefore, you can use DBM databases as long as a version of Perl exists for your computer. SDBM was written to match the functions provided with NDBM, so portability of code shouldn't be a problem. Perl is available on just about all popular platforms.
GDBM - GDBM is the GNU version of the DBM family of database routines. GDBM also enables you to cache data, reducing the time that it takes to write to the database. The database has no size limit; its size depends completely on your system's resources. GDBM database files have the extension .Db. Unlike DBM and NDBM, both of which use two files, GDBM only uses one file.
Berkeley db - The Berkeley db expands on the original DBM routines significantly. The Berkeley db uses hashed tables the same as the other DBM databases, but the library also can create databases based on a sorted balanced binary tree (BTREE) and store information with a record line number (RECNO). The method that you use depends completely on how you want to store and retrieve the information from a database. Berkeley db creates only one file, which has no extension."

[4] DBM - DBM stores the database in two files. The first has the extension .Pag and contains the bitmap. The second, which has the extension .Dir, contains the data.

[5] NDBM - NDBM is much like DBM but with a few additional features; it was written to provide better storage and retrieval methods. Also, NDBM enables you to open many databases, unlike DBM, in which you are allowed to have only one database open within your script. Like DBM, NDBM stores its information in two files using the extensions .Pag and .Dir.

[6] SDBM - SDBM comes with the Perl archive, which has been ported to many platforms. Therefore, you can use DBM databases as long as a version of Perl exists for your computer. SDBM was written to match the functions provided with NDBM, so portability of code shouldn't be a problem. Perl is available on just about all popular platforms.

[7] GDBM - GDBM is the GNU version of the DBM family of database routines. GDBM also enables you to cache data, reducing the time that it takes to write to the database. The database has no size limit; its size depends completely on your system's resources. GDBM database files have the extension .Db. Unlike DBM and NDBM, both of which use two files, GDBM only uses one file.

[8] Berkeley db - The Berkeley db expands on the original DBM routines significantly. The Berkeley db uses hashed tables the same as the other DBM databases, but the library also can create databases based on a sorted balanced binary tree (BTREE) and store information with a record line number (RECNO). The method that you use depends completely on how you want to store and retrieve the information from a database. Berkeley db creates only one file, which has no extension."

[4] yigit, ozan. «sdbm.bun». cse.yorku.ca. Consultado el 8 de mayo de 2019.

[5] «class SDBM». Documentation for Ruby 2.4.0. «Note that Ruby comes with the source code for SDBM, while the DBM and GDBM standard libraries rely on external libraries and headers.»

[6] «QDBM: Quick Database Manager». fallabs.com. 2006. Archivado desde el original el 27 de febrero de 2020. Consultado el 28 de diciembre de 2020.

[7] «tdb: Main Page». tdb.samba.org.

[#1-8] «Tokyo Cabinet第1版基本仕様書» [Fundamental Specifications of Tokyo Cabinet Version 1]. 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. «Tokyo CabinetはGDBMやQDBMの後継として次の点を目標として開発されました。これらの目標は達成されており、Tokyo Cabinetは従来のDBMを置き換える製品だと言えます。».

[fuzz-9] Debroux, Lionel (16 de junio de 2018). «oss-security - Fun with DBM-type databases...». openwall.com.

[deb-10] Surý, Ondřej (2014-06-19), «New project goal: Get rid of Berkeley DB (post jessie)», Debian, https://lists.debian.org/debian-devel/2014/06/msg00338.html.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]