cdb , abreviatura de "base de datos constante", se refiere tanto a una biblioteca como a un formato de datos creado por Daniel J. Bernstein . cdb actúa como una matriz asociativa en disco , que asigna claves a valores y permite almacenar múltiples valores para una sola clave. Una base de datos constante solo permite dos operaciones: creación y lectura. Ambas operaciones están diseñadas para ser muy rápidas y altamente confiables. Dado que la base de datos no cambia mientras está en uso, varios procesos pueden acceder a una sola base de datos sin bloquearse. Además, dado que todas las modificaciones crean una base de datos de reemplazo, puede aprovechar la semántica del sistema de archivos UNIX para brindar una garantía de confiabilidad.
Las posiciones de los registros, las longitudes de claves y valores y los valores hash son cantidades de 32 bits y, por lo tanto, deben caber en 4 gigabytes. [1] cdb es utilizado por djbdns , fastforward, mess822, qmail y ucspi-tcp para proporcionar un acceso a datos altamente eficiente, confiable y simple.
Una base de datos contiene un conjunto de datos completo (por ejemplo, una única matriz asociativa) en un único archivo informático . Consta de tres partes: un encabezado de tamaño fijo, datos y un conjunto de tablas hash . Las búsquedas están diseñadas únicamente para claves exactas, aunque se pueden realizar otros tipos de búsquedas escaneando toda la base de datos. Las búsquedas se realizan utilizando el siguiente algoritmo :
Para búsquedas de claves con múltiples valores, se pueden encontrar valores adicionales simplemente reanudando la búsqueda en la siguiente ranura.
Todos los números (desplazamientos, longitudes y valores hash) son números enteros de 32 bits sin signo , almacenados en formato little endian . Las claves y los datos se consideran cadenas de bytes opacas y no tienen un tratamiento especial.
El encabezado de tamaño fijo al principio de la base de datos describe 256 tablas hash enumerando su posición dentro del archivo y su longitud en ranuras. Los datos se almacenan como una serie de registros, cada uno de los cuales almacena la longitud de la clave, la longitud de los datos, la clave y los datos. No hay reglas de alineación ni de ordenación. Los registros van seguidos de un conjunto de 256 tablas hash de longitudes variables. Dado que cero es una longitud válida, puede haber menos de 256 tablas hash almacenadas físicamente en la base de datos, pero aun así se considera que hay 256 tablas. Las tablas hash contienen una serie de ranuras, cada una de las cuales contiene un valor hash y un desplazamiento de registro. Las "ranuras vacías" tienen un desplazamiento de cero.
Los hashes son números enteros de 32 bits sin signo y comienzan con un valor de 5381. Para cada byte de la clave, el hash actual se multiplica por 33 y luego se aplica la operación XOR con el byte actual de la clave. Los bits de desbordamiento se descartan. Las ranuras y las tablas se calculan de manera trivial a partir de los hashes. La tabla de destino son simplemente los ocho bits más bajos del hash (es decir, hash módulo 256), y la ranura dentro de la tabla son los bits restantes del hash módulo la longitud de la tabla (es decir, hash dividido por 256 módulo la longitud de la tabla).
El código oficial de la biblioteca cdb es de dominio público : los archivos fuente individuales están marcados como tales y también están disponibles en el paquete de dominio público djbdns . Sin embargo, el resto del paquete cdb solía ser software libre de licencia , lo que significa que debe distribuirse textualmente. La licencia inusual y la simplicidad del formato han impulsado a otros a reimplementar la biblioteca y publicarla bajo términos más comunes, como la biblioteca TinyCDB de Michael Tokarev, disponible bajo el dominio público. [2] Ha habido algunas reimplementaciones que eliminan el límite de 4 GiB en el tamaño de clave/valor, sin embargo, esas modificaciones no son compatibles con el formato original, como este CDB de ancho variable que admite el formato de archivo CDB original, así como versiones de 16 y 64 bits.
En 2009, todo el CDB pasó a ser de dominio público. [3]
Cabe destacar que el creador de cdb no tiene la intención de que cdb se use como una biblioteca compartida . Esto difiere de prácticamente todas las bases de datos similares a dbm , como Berkeley DB . Muchas de las reimplementaciones se pueden usar como bibliotecas compartidas.