Usa un RandomAccessFile per creare un database di basso livello

Mentre cercavo nel sito di JavaWorld idee per Step by Step di questo mese , mi sono imbattuto solo in alcuni articoli che trattano l'accesso ai file di basso livello. Sebbene le API di alto livello come JDBC ci offrano la flessibilità e la potenza necessarie nelle applicazioni aziendali di grandi dimensioni, molte applicazioni più piccole richiedono una soluzione più semplice ed elegante.

In questo articolo costruiremo un'estensione della RandomAccessFileclasse che ci consentirà di archiviare e recuperare i record. Questo "file di record" sarà equivalente a una tabella hash persistente, consentendo la memorizzazione e il recupero di oggetti con chiave dall'archivio file.

Un primer su file e record

Prima di saltare a capofitto nell'esempio, iniziamo con un backgrounder di base. Inizieremo definendo alcuni termini relativi a file e record, quindi discuteremo brevemente la java.io.RandomAccessFiledipendenza dalla piattaforma e dalla classe .

Terminologia

Le seguenti definizioni sono sintonizzate sul nostro esempio, piuttosto che sulla terminologia del database tradizionale.

Record : una raccolta di dati correlati archiviati in un file. Un record in genere ha più campi, ciascuno dei quali è un elemento di informazioni denominato e digitato.

Chiave : un identificatore per un record. Le chiavi sono generalmente uniche.

File : una raccolta sequenziale di dati archiviati in una sorta di memoria stabile come un disco rigido.

Accesso non sequenziale ai file : consente di leggere i dati da posizioni arbitrarie nel file.

Puntatore di file - Un numero che contiene la posizione del prossimo byte di dati da leggere da un file.

Puntatore di record : un puntatore di record è un puntatore di file che punta alla posizione in cui inizia un determinato record.

Indice - Un mezzo secondario per accedere ai record in un file; ovvero, mappa le chiavi per registrare i puntatori.

Heap : un file sequenziale di record non ordinati e di dimensioni variabili. Un heap richiede un'indicizzazione esterna per accedere in modo significativo ai record.

Persistenza : si riferisce alla memorizzazione di un oggetto o di un record per un determinato periodo di tempo. Questo periodo di tempo è in genere più lungo l'arco di un unico processo, quindi gli oggetti sono di solito persisteva in file o database.

Panoramica della classe java.io.RandomAccessFile

La classe RandomAccessFileè il modo in cui Java fornisce l'accesso non sequenziale ai file. La classe ci consente di passare a una determinata posizione nel file utilizzando il seek()metodo. Una volta posizionato il puntatore del file, i dati possono essere letti e scritti nel file utilizzando le interfacce DataInpute DataOutput. Queste interfacce ci consentono di leggere e scrivere dati in modo indipendente dalla piattaforma. Altri metodi utili RandomAccessFileci consentono di controllare e impostare la lunghezza del file.

Considerazioni dipendenti dalla piattaforma

I database moderni si basano sulle unità disco per l'archiviazione. I dati su un'unità disco vengono archiviati in blocchi, che vengono distribuiti su tracce e superfici. Il tempo di ricerca del disco e il ritardo di rotazione determinano il modo in cui i dati possono essere archiviati e recuperati in modo più efficiente. Un tipico sistema di gestione del database si basa strettamente sugli attributi del disco per ottimizzare le prestazioni. Sfortunatamente (o fortunatamente, a seconda del tuo interesse per l'I / O di file di basso livello!), Questi parametri sono lontani dalla portata quando si utilizza un'API di file di alto livello come java.io. Dato questo fatto, il nostro esempio ignorerà le ottimizzazioni che la conoscenza dei parametri del disco potrebbe fornire.

Progettazione dell'esempio RecordsFile

Ora siamo pronti per progettare il nostro esempio. Per iniziare, definirò alcuni requisiti e obiettivi di progettazione, risolverò i problemi di accesso simultaneo e specificherò il formato di file di basso livello. Prima di procedere all'implementazione, esamineremo anche le principali operazioni di registrazione e gli algoritmi corrispondenti.

Requisiti e obiettivi

Il nostro obiettivo principale in questo esempio è utilizzare a RandomAccessFileper fornire un modo per archiviare e recuperare i dati dei record. Assoceremo una chiave di tipo Stringa ciascun record come mezzo per identificarlo in modo univoco. Le chiavi saranno limitate a una lunghezza massima, sebbene i dati di registrazione non saranno limitati. Ai fini di questo esempio, i nostri record saranno costituiti da un solo campo: un "blob" di dati binari. Il codice del file non tenterà di interpretare i dati del record in alcun modo.

Come secondo obiettivo di progettazione, richiederemo che il numero di record supportati dal nostro file non venga corretto al momento della creazione. Consentiremo al file di crescere e ridursi man mano che i record vengono inseriti e rimossi. Poiché i nostri dati di indice e record verranno archiviati nello stesso file, questa restrizione ci indurrà ad aggiungere ulteriore logica per aumentare dinamicamente lo spazio dell'indice riorganizzando i record.

L'accesso ai dati in un file è ordini di grandezza più lento rispetto all'accesso ai dati in memoria. Ciò significa che il numero di accessi ai file eseguiti dal database sarà il fattore di prestazioni determinante. Richiederemo che le nostre operazioni di database principali non dipendono dal numero di record nel file. In altre parole, avranno un tempo di ordine costante rispetto agli accessi ai file.

Come requisito finale, supporremo che il nostro indice sia abbastanza piccolo da poter essere caricato in memoria. Ciò renderà più semplice per la nostra implementazione soddisfare il requisito che determina il tempo di accesso. Eseguiremo il mirroring dell'indice in a Hashtable, che fornisce ricerche immediate nell'intestazione dei record.

Correzione del codice

Il codice di questo articolo presenta un bug che causa la generazione di un'eccezione NullPointerException in molti casi possibili. Esiste una routine denominata insureIndexSpace (int) nella classe astratta BaseRecordsFile. Il codice è destinato a spostare i record esistenti alla fine del file se l'area dell'indice deve espandersi. Dopo che la capacità del "primo" record viene reimpostata alla dimensione effettiva, viene spostata alla fine. Il dataStartPtr viene quindi impostato in modo che punti al secondo record nel file. Sfortunatamente, se c'era spazio libero nel primo record, il nuovo dataStartPtr non punterà a un record valido, poiché è stato incrementato della lunghezza del primo record piuttosto che della sua capacità. L'origine Java modificata per BaseRecordsFile può essere trovata in Resources.

di Ron Walkup

Senior Software Engineer

bioMerieux, Inc.

Sincronizzazione e accesso simultaneo ai file

Per semplicità, iniziamo supportando solo un modello a thread singolo, in cui è vietato che le richieste di file avvengano contemporaneamente. Possiamo ottenere ciò sincronizzando i metodi di accesso pubblico delle classi BaseRecordsFilee RecordsFile. Si noti che è possibile ridurre questa restrizione per aggiungere il supporto per letture e scritture simultanee su record non in conflitto: sarà necessario mantenere un elenco di record bloccati e letture e scritture interleave per richieste simultanee.

Dettagli del formato del file

Definiremo ora esplicitamente il formato del file dei record. Il file è costituito da tre regioni, ciascuna con il proprio formato.

La regione delle intestazioni dei file. Questa prima regione contiene le due intestazioni essenziali necessarie per accedere ai record nel nostro file. La prima intestazione, chiamata puntatore di inizio dati, è una longche punta all'inizio dei dati del record. Questo valore ci dice la dimensione della regione dell'indice. La seconda intestazione, denominata intestazione num record, è una intche fornisce il numero di record nel database. La regione delle intestazioni inizia sul primo byte del file e si estende per i FILE_HEADERS_REGION_LENGTHbyte. Useremo readLong()e readInt()per leggere le intestazioni e writeLong()e writeInt()per scrivere le intestazioni.

La regione dell'indice. Ogni voce nell'indice è costituita da una chiave e da un'intestazione del record. L'indice inizia sul primo byte dopo l'area delle intestazioni dei file e si estende fino al byte prima del puntatore di inizio dati. Da queste informazioni, possiamo calcolare un puntatore di file all'inizio di una qualsiasi delle n voci nell'indice. Le voci hanno una lunghezza fissa: i dati della chiave iniziano sul primo byte nella voce dell'indice e si estendono ai MAX_KEY_LENGTHbyte. L'intestazione del record corrispondente per una determinata chiave segue immediatamente dopo la chiave nell'indice. L'intestazione del record ci dice dove si trovano i dati, quanti byte può contenere il record e quanti byte contiene effettivamente. Le voci dell'indice nell'indice del file non sono in un ordine particolare e non vengono associate all'ordine in cui i record sono memorizzati nel file.

Registra regione dati. La regione dei dati del record inizia nella posizione indicata dal puntatore di inizio dati e si estende fino alla fine del file. I record vengono posizionati uno dopo l'altro nel file senza che sia consentito spazio libero tra i record. Questa parte del file è costituita da dati grezzi senza intestazione o informazioni chiave. Il file di database termina nell'ultimo blocco dell'ultimo record nel file, quindi non c'è spazio aggiuntivo alla fine del file. Il file cresce e si riduce man mano che i record vengono aggiunti ed eliminati.

La dimensione assegnata a un record non corrisponde sempre alla quantità effettiva di dati contenuti nel record. Il record può essere pensato come un contenitore: potrebbe essere solo parzialmente pieno. I dati di record validi sono posizionati all'inizio del record.

Operazioni supportate e relativi algoritmi

Il RecordsFilesosterrà le seguenti operazioni principali:

  • Inserisci: aggiunge un nuovo record al file

  • Leggi: legge un record dal file

  • Aggiorna: aggiorna un record

  • Elimina: elimina un record

  • Assicura capacità: aumenta la regione dell'indice per accogliere nuovi record

Prima di passare attraverso il codice sorgente, esaminiamo gli algoritmi scelti per ciascuna di queste operazioni:

Inserire. Questa operazione inserisce un nuovo record nel file. Per inserire, noi:

  1. Assicurati che la chiave da inserire non sia già contenuta nel file
  2. Assicurati che la regione dell'indice sia sufficientemente grande per la voce aggiuntiva
  3. Trova spazio libero nel file abbastanza grande da contenere il record
  4. Scrive i dati del record nel file
  5. Aggiungi l'intestazione del record all'indice

Leggere. Questa operazione recupera un record richiesto dal file in base a una chiave. Per recuperare un record, noi:

  1. Usa l'indice per mappare la chiave data all'intestazione del record
  2. Ricerca fino all'inizio dei dati (utilizzando il puntatore ai dati del record memorizzati nell'intestazione)
  3. Leggi i dati del record dal file

Aggiornare. Questa operazione aggiorna un record esistente con nuovi dati, sostituendo i nuovi dati con quelli vecchi. I passaggi per il nostro aggiornamento variano a seconda delle dimensioni dei nuovi dati del record. Se i nuovi dati rientrano nel record esistente, noi:

  1. Scrive i dati del record nel file, sovrascrivendo i dati precedenti
  2. Aggiorna l'attributo che contiene la lunghezza dei dati nell'intestazione del record

Altrimenti, se i dati sono troppo grandi per il record, noi:

  1. Eseguire un'operazione di eliminazione sul record esistente
  2. Eseguire un inserimento dei nuovi dati

Elimina. Questa operazione rimuove un record dal file. Per eliminare un record, noi:

  1. Recuperare lo spazio allocato al record da rimuovere riducendo il file, se il record è l'ultimo nel file, o aggiungendo il suo spazio a un record adiacente

  2. Rimuovere l'intestazione del record dall'indice sostituendo la voce da eliminare con l'ultima voce nell'indice; questo garantisce che l'indice sia sempre pieno, senza spazi vuoti tra le voci

Garantire capacità. Questa operazione assicura che la regione dell'indice sia sufficientemente grande da contenere voci aggiuntive. In un ciclo, spostiamo i record dalla parte anteriore alla fine del file finché non c'è spazio sufficiente. Per spostare un record noi:

  1. Individua l'intestazione del record del primo record nel file; si noti che questo è il record con i dati nella parte superiore dell'area dati del record, non il record con la prima intestazione nell'indice

  2. Leggi i dati del record di destinazione

  3. Aumenta il file in base alla dimensione dei dati del record di destinazione utilizzando il setLength(long)metodo inRandomAccessFile

  4. Scrive i dati del record in fondo al file

  5. Aggiorna il puntatore ai dati nel record che è stato spostato

  6. Aggiorna l'intestazione globale che punta ai dati del primo record

Dettagli di implementazione: passaggio al codice sorgente

Ora siamo pronti per sporcarci le mani e lavorare sul codice per l'esempio. Puoi scaricare la fonte completa da Risorse.

Nota: è necessario utilizzare la piattaforma Java 2 (precedentemente nota come JDK 1.2) per compilare il codice sorgente.

Classe BaseRecordsFile

BaseRecordsFileè una classe astratta ed è l'implementazione principale del nostro esempio. Definisce i principali metodi di accesso e una serie di metodi di utilità per la manipolazione di record e voci di indice.