Use un RandomAccessFile para construir una base de datos de bajo nivel

Mientras buscaba ideas en el sitio de JavaWorld para el Paso a paso de este mes , encontré solo algunos artículos que cubrían el acceso a archivos de bajo nivel. Aunque las API de alto nivel, como JDBC, nos brindan la flexibilidad y la potencia necesarias en aplicaciones de grandes empresas, muchas aplicaciones más pequeñas requieren una solución más simple y elegante.

En este artículo, crearemos una extensión para la RandomAccessFileclase que nos permite almacenar y recuperar registros. Este "archivo de registros" será equivalente a una tabla hash persistente, lo que permitirá que los objetos con clave se almacenen y recuperen del almacenamiento de archivos.

Introducción a archivos y registros

Antes de saltar de cabeza al ejemplo, comencemos con un fondo básico. Comenzaremos definiendo algunos términos relacionados con archivos y registros, luego discutiremos brevemente la clase java.io.RandomAccessFiley la dependencia de la plataforma.

Terminología

Las siguientes definiciones se ajustan a nuestro ejemplo, en lugar de a la terminología tradicional de bases de datos.

Registro : una colección de datos relacionados almacenados en un archivo. Un registro suele tener varios campos, cada uno de los cuales es un elemento de información con nombre y tipo.

Clave : un identificador de un registro. Las claves suelen ser únicas.

Archivo : una colección secuencial de datos almacenados en algún tipo de almacenamiento estable, como un disco duro.

Acceso no secuencial a archivos : permite que los datos se lean desde ubicaciones arbitrarias en el archivo.

Puntero de archivo : un número que contiene la posición del siguiente byte de datos que se leerá de un archivo.

Puntero de registro : un puntero de registro es un puntero de archivo que apunta a la ubicación donde comienza un registro en particular.

Índice : un medio secundario para acceder a los registros de un archivo; es decir, asigna claves para registrar punteros.

Montón : un archivo secuencial de registros desordenados y de tamaño variable. Un montón requiere alguna indexación externa para acceder de manera significativa a los registros.

Persistencia : se refiere al almacenamiento de un objeto o registro durante un período de tiempo determinado. Este periodo de tiempo es normalmente más largo que el lapso de un proceso, por lo que los objetos son por lo general persistió en archivos o bases de datos.

Descripción general de la clase java.io.RandomAccessFile

La clase RandomAccessFilees la forma en que Java proporciona acceso no secuencial a los archivos. La clase nos permite saltar a una determinada ubicación en el archivo utilizando el seek()método. Una vez que se ha colocado el puntero del archivo, los datos se pueden leer y escribir en el archivo utilizando las interfaces DataInputy DataOutput. Estas interfaces nos permiten leer y escribir datos de manera independiente de la plataforma. Otros métodos prácticos RandomAccessFilenos permiten comprobar y establecer la longitud del archivo.

Consideraciones dependientes de la plataforma

Las bases de datos modernas dependen de unidades de disco para su almacenamiento. Los datos en una unidad de disco se almacenan en bloques, que se distribuyen entre pistas y superficies. El tiempo de búsqueda del disco y el retraso de rotación dictan cómo se pueden almacenar y recuperar los datos de la manera más eficiente. Un sistema de administración de base de datos típico se basa en gran medida en los atributos del disco para optimizar el rendimiento. Desafortunadamente (o afortunadamente, dependiendo de su interés en la E / S de archivos de bajo nivel), estos parámetros están lejos de su alcance cuando se utiliza una API de archivos de alto nivel como java.io. Dado este hecho, nuestro ejemplo ignorará las optimizaciones que podría proporcionar el conocimiento de los parámetros del disco.

Diseño del ejemplo de RecordsFile

Ahora estamos listos para diseñar nuestro ejemplo. Para empezar, expondré algunos requisitos y objetivos de diseño, resolveré problemas de acceso concurrente y especificaré el formato de archivo de bajo nivel. Antes de continuar con la implementación, también veremos las operaciones del registro principal y sus algoritmos correspondientes.

Requisitos y metas

Nuestro principal objetivo en este ejemplo es utilizar a RandomAccessFilepara proporcionar una forma de almacenar y recuperar datos de registros. Asociaremos una clave de tipo Stringcon cada registro como un medio para identificarlo de manera única. Las claves estarán limitadas a una longitud máxima, aunque los datos del registro no estarán limitados. Para los propósitos de este ejemplo, nuestros registros constarán de un solo campo: un "blob" de datos binarios. El código de archivo no intentará interpretar los datos del registro de ninguna manera.

Como segundo objetivo de diseño, exigiremos que la cantidad de registros que admite nuestro archivo no se fije en el momento de la creación. Permitiremos que el archivo crezca y se reduzca a medida que se insertan y eliminan registros. Debido a que nuestros datos de índice y registro se almacenarán en el mismo archivo, esta restricción hará que agreguemos lógica adicional para aumentar dinámicamente el espacio del índice reorganizando los registros.

Acceder a los datos de un archivo es un orden de magnitud más lento que acceder a los datos de la memoria. Esto significa que el número de accesos a archivos que realice la base de datos será el factor determinante de rendimiento. Requeriremos que las operaciones de nuestra base de datos principal no dependan de la cantidad de registros en el archivo. En otras palabras, estarán en un tiempo de orden constante con respecto a los accesos a archivos.

Como requisito final, asumiremos que nuestro índice es lo suficientemente pequeño como para cargarlo en la memoria. Esto facilitará que nuestra implementación cumpla con el requisito que dicta el tiempo de acceso. Reflejaremos el índice en a Hashtable, que proporciona búsquedas inmediatas de encabezados de registros.

Corrección de código

El código de este artículo tiene un error que hace que arroje una NullPointerException en muchos casos posibles. Hay una rutina denominada insureIndexSpace (int) en la clase abstracta BaseRecordsFile. El código está destinado a mover los registros existentes al final del archivo si es necesario expandir el área de índice. Una vez que la capacidad del "primer" registro se restablece a su tamaño real, se mueve al final. El dataStartPtr se establece para que apunte al segundo registro del archivo. Desafortunadamente, si había espacio libre en el primer registro, el nuevo dataStartPtr no apuntará a un registro válido, ya que se incrementó por la longitud del primer registro en lugar de su capacidad. La fuente Java modificada para BaseRecordsFile se puede encontrar en Recursos.

de Ron Walkup

Ingeniero de programación superior

bioMerieux, Inc.

Sincronización y acceso concurrente a archivos

Para simplificar, comenzamos por admitir solo un modelo de un solo hilo, en el que se prohíbe que las solicitudes de archivos sucedan al mismo tiempo. Podemos lograr esto sincronizando los métodos de acceso público de las clases BaseRecordsFiley RecordsFile. Tenga en cuenta que puede relajar esta restricción para agregar soporte para lecturas y escrituras concurrentes en registros no conflictivos: deberá mantener una lista de registros bloqueados e intercalar lecturas y escrituras para solicitudes concurrentes.

Detalles del formato de archivo

Ahora definiremos explícitamente el formato del archivo de registros. El archivo consta de tres regiones, cada una con su propio formato.

La región de encabezados de archivo. Esta primera región contiene los dos encabezados esenciales necesarios para acceder a los registros de nuestro archivo. El primer encabezado, llamado puntero de inicio de datos, es un longque apunta al inicio de los datos del registro. Este valor nos dice el tamaño de la región del índice. El segundo encabezado, llamado encabezado deint número de registros , es un encabezado que proporciona el número de registros en la base de datos. La región de encabezados comienza en el primer byte del archivo y se extiende por FILE_HEADERS_REGION_LENGTHbytes. Usaremos readLong()y readInt()para leer los encabezados y writeLong()y writeInt()para escribir los encabezados.

La región del índice. Cada entrada del índice consta de una clave y un encabezado de registro. El índice comienza en el primer byte después de la región de encabezados de archivo y se extiende hasta el byte antes del puntero de inicio de datos. A partir de esta información, podemos calcular un puntero de archivo al inicio de cualquiera de las n entradas del índice. Las entradas tienen una longitud fija: los datos clave comienzan en el primer byte de la entrada de índice y se extienden por MAX_KEY_LENGTHbytes. El encabezado de registro correspondiente para una clave determinada sigue inmediatamente después de la clave en el índice. El encabezado del registro nos dice dónde se encuentran los datos, cuántos bytes puede contener el registro y cuántos bytes contiene realmente. Las entradas de índice en el índice de archivo no están en un orden particular y no se asignan al orden en el que se almacenan los registros en el archivo.

Registre la región de datos. La región de datos de registro comienza en la ubicación indicada por el puntero de inicio de datos y se extiende hasta el final del archivo. Los registros se colocan uno al lado del otro en el archivo sin dejar espacio libre entre los registros. Esta parte del archivo consta de datos sin procesar sin encabezado ni información clave. El archivo de base de datos termina en el último bloque del último registro del archivo, por lo que no hay espacio adicional al final del archivo. El archivo crece y se reduce a medida que se agregan y eliminan registros.

El tamaño asignado a un registro no siempre corresponde a la cantidad real de datos que contiene el registro. El registro se puede considerar como un contenedor; puede que solo esté parcialmente lleno. Los datos de registro válidos se colocan al comienzo del registro.

Operaciones compatibles y sus algoritmos

El RecordsFileapoyará las siguientes operaciones principales:

  • Insertar: agrega un nuevo registro al archivo

  • Leer: lee un registro del archivo

  • Actualizar: actualiza un registro

  • Eliminar: elimina un registro

  • Garantizar la capacidad: aumenta la región del índice para dar cabida a nuevos registros.

Antes de recorrer el código fuente, repasemos los algoritmos elegidos para cada una de estas operaciones:

Insertar. Esta operación inserta un nuevo registro en el archivo. Para insertar, nosotros:

  1. Asegúrese de que la clave que se inserta no esté ya contenida en el archivo
  2. Asegúrese de que la región del índice sea lo suficientemente grande para la entrada adicional
  3. Encuentre espacio libre en el archivo lo suficientemente grande como para guardar el registro
  4. Escriba los datos del registro en el archivo
  5. Agregue el encabezado del registro al índice

Leer. Esta operación recupera un registro solicitado del archivo basado en una clave. Para recuperar un registro, nosotros:

  1. Use el índice para asignar la clave dada al encabezado del registro
  2. Busque hasta el inicio de los datos (usando el puntero para registrar los datos almacenados en el encabezado)
  3. Leer los datos del registro del archivo

Actualizar. Esta operación actualiza un registro existente con nuevos datos, reemplazando los nuevos datos por los antiguos. Los pasos para nuestra actualización varían, dependiendo del tamaño de los nuevos datos de registro. Si los nuevos datos encajan en el registro existente, nosotros:

  1. Escriba los datos del registro en el archivo, sobrescribiendo los datos anteriores
  2. Actualizar el atributo que contiene la longitud de los datos en el encabezado del registro

De lo contrario, si los datos son demasiado grandes para el registro, nosotros:

  1. Realizar una operación de eliminación en el registro existente
  2. Realizar una inserción de los nuevos datos

Eliminar. Esta operación elimina un registro del archivo. Para eliminar un registro, nosotros:

  1. Recupere el espacio asignado al registro que se está eliminando reduciendo el archivo, si el registro es el último en el archivo, o agregando su espacio a un registro adyacente

  2. Elimine el encabezado del registro del índice reemplazando la entrada que se está eliminando con la última entrada en el índice; esto asegura que el índice esté siempre lleno, sin espacios vacíos entre las entradas

Asegurar la capacidad. Esta operación asegura que la región del índice sea lo suficientemente grande para acomodar entradas adicionales. En un bucle, movemos los registros desde el principio hasta el final del archivo hasta que haya suficiente espacio. Para mover un registro:

  1. Busque el encabezado del registro del primer registro del archivo; tenga en cuenta que este es el registro con datos en la parte superior de la región de datos de registro, no el registro con el primer encabezado en el índice

  2. Leer los datos del registro de destino

  3. Haga crecer el archivo por el tamaño de los datos del registro de destino utilizando el setLength(long)método enRandomAccessFile

  4. Escriba los datos del registro al final del archivo.

  5. Actualizar el puntero de datos en el registro que se movió

  6. Actualice el encabezado global que apunta a los datos del primer registro

Detalles de implementación: paso a paso por el código fuente

Ahora estamos listos para ensuciarnos las manos y trabajar en el código del ejemplo. Puede descargar la fuente completa de Recursos.

Nota: debe utilizar la plataforma Java 2 (anteriormente conocida como JDK 1.2) para compilar el código fuente.

Clase BaseRecordsFile

BaseRecordsFilees una clase abstracta y es la implementación principal de nuestro ejemplo. Define los principales métodos de acceso, así como una gran cantidad de métodos de utilidad para manipular registros y entradas de índice.