Kyoto cabinet
| Kyoto Cabinet | ||
|---|---|---|
| Información general | ||
| Tipo de programa | Base de datos | |
| Autor | Mikio Hirabayashi | |
| Desarrollador | Fall Labs | |
| Lanzamiento inicial | 2009 | |
| Licencia | GPL | |
| Información técnica | ||
| Programado en | C++ | |
| Versiones | ||
| Última versión estable | 1.2.76 () | |
| Enlaces | ||
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[editar]
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[editar]
En 2007 se desarrolló Tokyo Cabinet como sucesor de QDBM con estos objetivos:[1]
- 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[editar]
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[editar]
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[editar]
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.
Las funciones del API son reentrantes y disponibles en entornos multihilo. Los diferentes objetos de la base de datos pueden ser manejados en paralelo. Para realizar operaciones simultáneas sobre el mismo objeto de la base de datos, se usa rwlock (bloque de lectura y escritura) para control de exclusión. De este modo, cuando un hile de escritura está operando sobre un objeto, los demás hilos de escritura están bloqueados. Sin embargo, cuando un hilo de lectura está actuando, los otros hilos de lectura no se bloquean. La granularidad del bloqueo depende en la estructura del dato. La base de datos de hash bloquea registros, la del árbol binario bloquea páginas.
Con el fin de mejorar las prestaciones y la concurrencia, Kyoto Cabinet usa las operaciones atómicas nativas de las CPU más populares tales como incremento atómico y CAS (compare-and-swap). Las primitivas de bloqueo proporcionadas por el entorno nativo -como puede ser el paquete de hilos de POSIX- son sustituidos por las propias primitivas que usan CAS.
Interfaces simples y flexibles[editar]
Kyoto Cabinet proporciona APIs simples basados en diseño orientado a objetos. Cada operación sobre la base de datos se encapsula y publica como métodos claros: `open', `close', `set', `remove', `get' &c. Las clases de las bases de datos hash y árbol binario se derivan de una clase abstracta común superior que define en interfaz. Portar una aplicación de una base de datos a otra es una tarea sencilla. Incluso el API polimórfico de la base de datos puede asignarse en tiempo de ejecución.
Kyoto Cabinet soporta el perfil de "visitante". Pueden definirse operaciones arbitrarias sobre la base de datos y funciones a invocar. La clase "visitante" encapsula la función a invocar y sus datos de estado. La clase database tiene el método "accept", el cual acepta una instancia de la clave "visitante" y llama a su función con los datos del registro. El valor devuelto por la función invocada aparece como nuevo estado del registro.
Adicionalmente se proporcionan una cantidad de utilidades tales como "búsqueda de prefijo", "búsqueda regex", "logging", "backup en caliente", "pseudo-instantánea" y "fusión". También se proporciona un entorno para "MapReduce", que aunque no está distribuido, es útil para cálculo de agregados que usen menos CPU y memoria. La base de datos en texto plano es una interfaz que trata un fichero plano como un fichero de base de datos. Resulta útil usar un fichero de texto para entrada o salida de MapReduce. La base de datos de índice es un frontal para una base de datos polimórfica que mejora la eficiencia de la operación `append'. Resulta útil para construir índices inversos.
Aunque el grueso del API está desarrollado en C++, también se proporcionan llamadas en otros lenguajes como C, Java, Python, Ruby, Perl y Lua. Inferfaz por línea de comandos también está disponible para todos los API, lo que resulta muy útil para prototipado, test y depuración.
Véase también[editar]
Referencias[editar]
- ↑ «Tokyo Cabinet第1版基本仕様書» (html). 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を置き換える製品だと言えます。».
Enlaces externos[editar]
| Control de autoridades |
|
|---|
Datos: Q11110864