Kyoto Cabinet es una librería de rutinas para gestión de base de datos. La base de datos consiste en un simple fichero que contiene registros, cada uno de ellos constituido por una clave y un valor. Cada clave y cada valor consiste en una cadena de bytes de longitud variable. Datos binarios o ASCII pueden ser empleados tanto como clave o valor. Cada clave debe ser única en la base de datos. No existe en Kyoto Cabinet ni el concepto de tabla ni el de tipo. Los registros se organizan en una lista de hash o en un árbol binario.
Introducción
Se permiten los siguientes modos de acceso a la base de datos: almacenaje de un registro con clave y valor borrado de un registro sobre la base de su clave recuperación de un registro por su clave
Incluso se proporciona acceso transversal a cada clave. Estos métodos de acceso son similares a la librería original dbm (y sus secuelas: ndbm y gdbm) definida en el estándar UNIX. Kyoto Cabinet es una alternativa a dbm con altas prestaciones.
Cada operación sobre la base de datos organizada con hash' tiene una complejidad "O(1)". Por ello -en teoría- las prestaciones son constantes con independencia de la cantidad de datos contenida en ella. En la práctica, las prestaciones etán determinadas por la velocidad de acceso a la memoria principal. Si el tamaño de los datos contenidos en la base de datos es menor que la cantidad de memoria principal, la velocidad será comparable a la del acceso a memoria, que es mayor que std::map en STL. Desde luego que el tamaño de los datos puede ser mayor que el de la memoria principal, siendo el límite último los 8 exabytes. Incluso en ese caso, cada operación requeriría solo uno o dos accesos a disco.
Cada operación sobre la base de datos organizada con árbol binario tiene una complejidad "O(log N)". En teoría las prestaciones guardan una relación logarítmica con el volumen de los datos. Aunque las prestaciones del acceso aleatorio a datos de la base de datos organizada en árbol binario son inferiores frente a las obtenidas con los organizados en hash, el árbol binario soporta acceso secuencial por claves, el cual realiza búsqueda adelantada de cadenas y de rango para enteros. Las prestaciones del acceso secuencial son mucho mayores que las del acceso aleatorio.
Al estar basado el API en un diseño orientado a objetos, la base de datos en hash y en árbol binario poseen los mismos métodos heredados de la clase abstracta padre. Además de estas dos, esta clase proporciona otras otros siete tipos de organización: en hash está motorizada por el contenedor estándar std::unordered_map en árbol binario está motorizada con el contenedor estándar de std::map en stash (escondrijo) está motorizada con la implementación original de hash naif en caché hash está motorizada con la implementación original de mapa hash con doble enlace con algoritmo de borrado LRU en árbol de caché motorizado por la base de datos de caché hash y proporciona en mecanismo de árbol binario el directorio hash motorizado por el mecanismo de directorios del sistema de ficheros y almacena los registros como ficheros en un directorio en árbol de directorios motorizado por la base de datos de hash de directorios y proporciona el mecanismo en árbol binario
Todas las bases de datos tienen utilidades prácticas relacionadas con transacciones y cursores. También se incluyen programas para acceso mediante línea de comando.
Kyoto Cabinet funciona muy rápido. Por ejemplo, el tiempo necesario para almacenar un millón de registro en las base de datos basada en hash es de 0.9 segundos, y para la basada en árbol binario de 1.1 segundos. Además el tamaño de los datos se mantiene muy pequeño. Por ejemplo el encabezamiento de un registro es de 16 bytes para la base de datos en hash y 4 para la de árbol binario. La escalabilidad es enorme: puede alcanzar los 8 EB (9.22e18 bytes)
Kyoto Cabinet está escrito en C++, y proporciona APIs para C++, C, Java, Python, Ruby, Perl y Lua. Kyoto Cabinet está disponible en plataforma con API conforme con C++03 con extensiones de la librería TR1. Se distribuye como software libre con licencia GPL. La excepción de la licencia FOSS también se proporciona para acomodarse a productos que tengan otras licencias de código abierto y libres. Por otro lado también se ofrece licencia comercial. Si se usa Kyoto Cabinet dentro de un software propietario, se requiere la licencia comercial.
La base de datos original dbm la desarrolló Kenneth Thompson como parte del Unix original de AT&T. Tras ello se desarrollaron gran cantidad de secuelas, como NDBM, SDBM, GDBM, TDB y BerkeleyDB. En 2003, fue desarrollada QDBM como reemplazo de GDBM para mejorar sus prestaciones.
Características
En 2007 se desarrolló Tokyo Cabinet como sucesor de QDBM con estos objetivos: disminuir el espacio ocupado: menor tamaño del fichero de datos aumentar la velocidad: procesamiento más rápido mejorar el paralelismo: mayores prestaciones con procesadores multi-hilo mejorar la usabilidad: API simplificado aumentar la robustez: evita la corrupción del fichero incluso bajo catástrofes soportar arquitecturas de 64 bits: espacio de datos y de memoria enormes
En 2009 se desarrolló Kyoto Cabinet también como sucesor a QDBM. Frente a Tokyo Cabinet, se perseguían estas mejoras: disminuir el espacio ocupado: menor tamaño del fichero de datos mejorar el paralelismo: mayores prestaciones con procesadores multi-hilo aumentar la portabilidad : abstraer los niveles inferiores para soportar sistema no POSIX mejorar la usabilidad: API simplificado aumentar la robustez: evita la corrupción del fichero incluso bajo catástrofes
Se mantiene el desarrollo de ambas librerías ya que sus valores son distintos.
Implementación de la base de datos con hash
Kyoto Cabinet tiene la posibilidad de usar un algoritmo de hash para recuperar los registros. Si un almacén de datos tiene los bastantes elementos, el tiempo de recuperación tiene una complejidad "O(1)". Es decir, el tiempo que se requiere para recuperar un registro es constante, independiente del tamaño de los datos. Esto también aplica al almacenamiento o borrado. La colisión de los valores del hash se gestiona mediante un encadenamiento independiente. La estructura de datos del encadenamiento está compuesta por un árbol de búsqueda binario. Incluso si el almacén de datos tiene escasos elementos, la complejidad del tiempo de recuperación es "O(log n)".
Kyoto Cabinet consigue mejorar el tiempo de acceso -frente a Tokio Cabinet- cargando todo el almacén en RAM. Si el almacén ya está en RAM es posible acceder a una sección mediante un conjunto de las operaciones de acceso a ficheros como `lseek', `read' y `write'. El almacén que está grabado en disco no se carga en RAM con la llamada a `read' sino con `mmap'. Por ello, el tiempo de preparación de la conexión a la base de datos es muy pequeño, y dos o más procesos pueden compartir el mismo mapa de memoria.
La función hash utilizada es MurMurHash 2.0. Si el número de elementos en el almacén es de alrededor de la mitad de los elementos en la base de datos, la probabilidad de colisión del hash es del 55.3% (35.5% si el número es el mismo, 20.4% si hay el doble de ellos, 11.0% si hay cuatro veces más, 5.7% si hay ocho veces más). En ese caso, es posible recuperar y registro por medio de dos conjuntos de operaciones de ficheros.
Cuando se sobreescribe un registro con un valor cuyo tamaño es mayor que el existente, es necesario mover la región a otra posición en el fichero. Dado que la complejidad temporal de la operación depende del tamaño de la región de un registro, aumentar el valor indefinidamente resulta ineficiente. Sin embargo, Kyoto Cabinet enfoca el problema mediante alineamiento. Si el incremento del dato puede almacenarse en la región de reserva que sigue a un registro, no es necesario mover la región del registro.
De modo general, actualizaciones sucesivas van fragmentando la base de datos, y su tamaño crece rápidamente. Kyoto Cabinet resuelve este problema manteniendo una reserva de bloques libres y un mecanismo de desfragmentación automático. Si se elimina un registro o se mueve a otra posición, toda el bloque donde se encuentra será tratada como libre. La reserva de bloques libres los gestiona y rehúsa el más adecuado para un nuevo registro. La desfragmentación automática consiste en mover los bloques libres y los registros de manera independiente. Bloques libres consecutivos se agrupan en uno solo mayor.
Implementación de la base de datos con árbol binario
Aunque la base de datos en árbol binario funciona más lenta que la de hash, sí permite el acceso ordenado a cada registro. Este orden pueden asignarlo los usuarios. Los registros del árbol binario se ordenan y agrupan en páginas lógicas. Para cada una de esas páginas se mantiene un índice organizado en árbol binario balanceado. De este modo la complejidad temporal de la recuperación es de "O(log n)". Se proporciona un cursor para ordenar el acceso a registros. El cursor puede saltar a una posición especificada por una clave además de avanzar o retroceder desde la posición actual. Al estar la lista de registros doblemente encadenada, la complejidad de mover el cursor es "O(1)".
La base de datos en árbol binario está basada en la base de datos de hash. Al estar cada página del árbol grabada como un registro del hash, la base de datos en árbol binario hereda la eficiencia de la de hash. Al tener menos encabezamiento y el alineamiento ajustarse al tamaño de la página, el tamaño de la base de datos se reduce hasta la mitad de tamaño.
Aunque se requieren operaciones en muchas página para actualizar la base de datos en árbol binario, Kyoto Cabinet acelera el proceso haciendo caché de páginas para reducir el acceso a disco. Las páginas de caché están implementadas mediante una lista de páginas menos usadas (LRU) doble, haciendo que las páginas más accedidas se guarden en la lista caliente y las accedidas más recientemente en la lista tibia. Si el caché de páginas funciona eficientemente y el conjunto de índices se mantiene en memoria se minimiza el número de operaciones para acceder a un registro.
Funcionalidad práctica
Kyoto Cabinet posee mecanismos para realizar transacciones. Es posible ejecutar una serie de operaciones entre el principio y fin de la transacción de manera monolítica, o abortar la transacción y volver al estado anterior. Soporta dos niveles de aislamiento: serializable y read uncommitted. La durabilidad está asegurada mediante el log de escritura adelantada y paginación shadow.
Están soportados mecanismos automáticos para transacciones y recuperación. Si al abrir la base de datos se especifica la opción de transacción automática, cada operación de actualización se realizan transaccionalmente. Por esto se puede garantizar la durabilidad sin efectuar operaciones de transacción explícitas. El mecanismo de recuperación automática se pone en marcha si la base de datos ha cascado. Si se detecta inconsistencia al abrir la base de datos, todas las regiones son recorridas al estilo fsck y la base de datos reconstruida en lo posible.
Kyoto Cabinet proporciona dos modos de conexión a la base de datos: "lectura" y "escritura". Un lector puede recuperar datos pero no almacenar ni borrar, un escritor además puede escribir. El control de exclusión entre procesos se realiza por medio de bloqueos. Mientras que un "escritor" está conectado a la base de datos, ni lectores ni escritores pueden conectarse. Si un "lector" está conectado, otros "lectores" pueden conectarse, pero no "escritores". Con este mecanismo se garantiza la consistencia de datos cuando hay conexiones simultáneas en entornos multitarea.