Utilisez un RandomAccessFile pour créer une base de données de bas niveau

En cherchant sur le site de JavaWorld des idées pour l' étape par étape de ce mois-ci , je n'ai trouvé que quelques articles couvrant l'accès aux fichiers de bas niveau. Bien que les API de haut niveau telles que JDBC nous offrent la flexibilité et la puissance nécessaires dans les grandes applications d'entreprise, de nombreuses petites applications nécessitent une solution plus simple et plus élégante.

Dans cet article, nous allons créer une extension de la RandomAccessFileclasse qui nous permet de stocker et de récupérer des enregistrements. Ce «fichier d'enregistrements» équivaudra à une table de hachage persistante, permettant aux objets à clé d'être stockés et récupérés à partir du stockage de fichiers.

Une introduction aux fichiers et aux enregistrements

Avant de plonger tête baissée dans l'exemple, commençons par un document d'information de base. Nous commencerons par définir quelques termes relatifs aux fichiers et aux enregistrements, puis nous discuterons brièvement java.io.RandomAccessFiledes dépendances de classe et de plate-forme.

Terminologie

Les définitions suivantes sont adaptées à notre exemple plutôt qu'à la terminologie traditionnelle des bases de données.

Record - Une collection de données associées stockées dans un fichier. Un enregistrement comporte généralement plusieurs champs, chacun étant un élément d'information nommé et saisi.

Clé - Un identifiant pour un enregistrement. Les clés sont généralement uniques.

Fichier - Une collection séquentielle de données stockées dans une sorte de stockage stable tel qu'un disque dur.

Accès au fichier non séquentiel - Permet de lire les données à partir d'emplacements arbitraires dans le fichier.

Pointeur de fichier - Un nombre contenant la position du prochain octet de données à lire à partir d'un fichier.

Pointeur d'enregistrement - Un pointeur d'enregistrement est un pointeur de fichier qui pointe vers l'emplacement où commence un enregistrement particulier.

Index - Un moyen secondaire d'accéder aux enregistrements dans un fichier; c'est-à-dire qu'il mappe des clés pour enregistrer des pointeurs.

Heap - Un fichier séquentiel d'enregistrements non ordonnés et de taille variable. Un tas nécessite une indexation externe afin d'accéder de manière significative aux enregistrements.

Persistance - Fait référence au stockage d'un objet ou d'un enregistrement pendant une certaine durée. Cette durée est généralement plus longue que la durée d'un processus, de sorte que les objets sont généralement conservés dans des fichiers ou des bases de données.

Vue d'ensemble de la classe java.io.RandomAccessFile

La classe RandomAccessFileest la façon dont Java fournit un accès non séquentiel aux fichiers. La classe nous permet de sauter à un certain emplacement dans le fichier en utilisant la seek()méthode. Une fois le pointeur de fichier positionné, les données peuvent être lues et écrites dans le fichier à l'aide des interfaces DataInputet DataOutput. Ces interfaces nous permettent de lire et d'écrire des données de manière indépendante de la plate-forme. D'autres méthodes pratiques RandomAccessFilenous permettent de vérifier et de définir la longueur du fichier.

Considérations dépendant de la plate-forme

Les bases de données modernes reposent sur des lecteurs de disque pour le stockage. Les données sur un lecteur de disque sont stockées dans des blocs, qui sont répartis sur les pistes et les surfaces. Le temps de recherche du disque et le délai de rotation déterminent la manière dont les données peuvent être stockées et récupérées le plus efficacement possible. Un système de gestion de base de données typique dépend étroitement des attributs du disque afin de rationaliser les performances. Malheureusement (ou heureusement, en fonction de votre intérêt pour les E / S de fichiers de bas niveau!), Ces paramètres sont loin d'être atteints lors de l'utilisation d'une API de fichiers de haut niveau telle que java.io. Compte tenu de ce fait, notre exemple ne tiendra pas compte des optimisations que la connaissance des paramètres du disque pourrait apporter.

Conception de l'exemple RecordsFile

Nous sommes maintenant prêts à concevoir notre exemple. Pour commencer, je vais exposer certaines exigences et objectifs de conception, résoudre les problèmes d'accès simultané et spécifier le format de fichier de bas niveau. Avant de procéder à l'implémentation, nous examinerons également les principales opérations d'enregistrement et leurs algorithmes correspondants.

Exigences et objectifs

Notre objectif principal dans cet exemple est d'utiliser a RandomAccessFilepour fournir un moyen de stocker et de récupérer des données d'enregistrement. Nous associerons une clé de type Stringà chaque enregistrement afin de l'identifier de manière unique. Les clés seront limitées à une longueur maximale, bien que les données d'enregistrement ne soient pas limitées. Pour les besoins de cet exemple, nos enregistrements seront constitués d'un seul champ - un "blob" de données binaires. Le code de fichier n'essaiera en aucun cas d'interpréter les données d'enregistrement.

Comme deuxième objectif de conception, nous exigerons que le nombre d'enregistrements pris en charge par notre fichier ne soit pas fixé au moment de la création. Nous allons permettre au fichier de grandir et de se réduire au fur et à mesure que les enregistrements sont insérés et supprimés. Étant donné que nos données d'index et d'enregistrement seront stockées dans le même fichier, cette restriction nous amènera à ajouter une logique supplémentaire pour augmenter dynamiquement l'espace d'index en réorganisant les enregistrements.

L'accès aux données d'un fichier est de plusieurs ordres de grandeur plus lent que l'accès aux données en mémoire. Cela signifie que le nombre d'accès aux fichiers que la base de données effectue sera le facteur de performance déterminant. Nous exigerons que nos principales opérations de base de données ne dépendent pas du nombre d'enregistrements dans le fichier. En d'autres termes, ils auront un temps d'ordre constant en ce qui concerne les accès aux fichiers.

Enfin, nous supposerons que notre index est suffisamment petit pour être chargé en mémoire. Cela permettra à notre implémentation de répondre plus facilement à l'exigence qui dicte le temps d'accès. Nous refléterons l'index dans un Hashtable, qui fournit des recherches immédiates d'en-tête d'enregistrement.

Correction du code

Le code de cet article a un bogue qui le pousse à lever une NullPointerException dans de nombreux cas possibles. Il existe une routine nommée insureIndexSpace (int) dans la classe abstraite BaseRecordsFile. Le code est destiné à déplacer les enregistrements existants à la fin du fichier si la zone d'index doit se développer. Une fois que la capacité du «premier» enregistrement a été réinitialisée à sa taille réelle, elle est déplacée à la fin. Le dataStartPtr est ensuite défini pour pointer vers le deuxième enregistrement du fichier. Malheureusement, s'il y avait de l'espace libre dans le premier enregistrement, le nouveau dataStartPtr ne pointera pas vers un enregistrement valide, car il a été incrémenté de la longueur du premier enregistrement plutôt que de sa capacité. La source Java modifiée pour BaseRecordsFile se trouve dans Ressources.

de Ron Walkup

Ingénieur logiciel senior

bioMérieux, Inc.

Synchronisation et accès simultané aux fichiers

Pour plus de simplicité, nous commençons par prendre en charge uniquement un modèle à un seul thread, dans lequel les demandes de fichiers sont interdites de se produire simultanément. Nous pouvons accomplir cela en synchronisant les méthodes d'accès public des classes BaseRecordsFileet RecordsFile. Notez que vous pouvez assouplir cette restriction pour ajouter la prise en charge des lectures et écritures simultanées sur des enregistrements non conflictuels: vous devrez maintenir une liste des enregistrements verrouillés et entrelacer les lectures et écritures pour les demandes simultanées.

Détails du format de fichier

Nous allons maintenant définir explicitement le format du fichier d'enregistrements. Le fichier se compose de trois régions, chacune avec son propre format.

La région des en-têtes de fichier. Cette première région contient les deux en-têtes essentiels nécessaires pour accéder aux enregistrements de notre fichier. Le premier en-tête, appelé pointeur de début de données, est un longpointant vers le début des données d'enregistrement. Cette valeur nous indique la taille de la région d'index. Le deuxième en-tête, appelé en- tête num records, est un intqui donne le nombre d'enregistrements dans la base de données. La région des en-têtes commence sur le premier octet du fichier et s'étend sur les FILE_HEADERS_REGION_LENGTHoctets. Nous utiliserons readLong()et readInt()pour lire les en-têtes et writeLong()et writeInt()pour écrire les en-têtes.

La région d'index. Chaque entrée de l'index se compose d'une clé et d'un en-tête d'enregistrement. L'index commence sur le premier octet après la région des en-têtes de fichier et s'étend jusqu'à l'octet avant le pointeur de début de données. À partir de ces informations, nous pouvons calculer un pointeur de fichier vers le début de l'une des n entrées de l'index. Les entrées ont une longueur fixe - les données clés commencent sur le premier octet de l'entrée d'index et étendent les MAX_KEY_LENGTHoctets. L'en-tête d'enregistrement correspondant pour une clé donnée suit immédiatement après la clé dans l'index. L'en-tête d'enregistrement nous indique où se trouvent les données, combien d'octets l'enregistrement peut contenir et combien d'octets il contient réellement. Les entrées d'index dans l'index de fichier ne sont dans aucun ordre particulier et ne correspondent pas à l'ordre dans lequel les enregistrements sont stockés dans le fichier.

Enregistrer la région de données. La région de données d'enregistrement commence à l'emplacement indiqué par le pointeur de début de données et s'étend jusqu'à la fin du fichier. Les enregistrements sont positionnés dos à dos dans le fichier sans espace libre autorisé entre les enregistrements. Cette partie du fichier est constituée de données brutes sans en-tête ni information clé. Le fichier de base de données se termine sur le dernier bloc du dernier enregistrement du fichier, il n'y a donc pas d'espace supplémentaire à la fin du fichier. Le fichier grandit et se réduit à mesure que des enregistrements sont ajoutés et supprimés.

La taille allouée à un enregistrement ne correspond pas toujours à la quantité réelle de données que contient l'enregistrement. L'enregistrement peut être considéré comme un conteneur - il ne peut être que partiellement plein. Les données d'enregistrement valides sont positionnées au début de l'enregistrement.

Opérations prises en charge et leurs algorithmes

Le RecordsFilesupportera les opérations principales suivantes:

  • Insérer - Ajoute un nouvel enregistrement au fichier

  • Lire - Lit un enregistrement à partir du fichier

  • Mettre à jour - Met à jour un enregistrement

  • Supprimer - Supprime un enregistrement

  • Garantir la capacité - Agrandit la région d'index pour accueillir de nouveaux enregistrements

Avant de parcourir le code source, passons en revue les algorithmes choisis pour chacune de ces opérations:

Insérer. Cette opération insère un nouvel enregistrement dans le fichier. Pour insérer, nous:

  1. Assurez-vous que la clé insérée n'est pas déjà contenue dans le fichier
  2. Assurez-vous que la région d'index est suffisamment grande pour l'entrée supplémentaire
  3. Trouver de l'espace libre dans le fichier suffisamment grand pour contenir l'enregistrement
  4. Ecrire les données d'enregistrement dans le fichier
  5. Ajouter l'en-tête d'enregistrement à l'index

Lis. Cette opération récupère un enregistrement demandé du fichier en fonction d'une clé. Pour récupérer un enregistrement, nous:

  1. Utilisez l'index pour mapper la clé donnée à l'en-tête de l'enregistrement
  2. Rechercher jusqu'au début des données (en utilisant le pointeur vers les données d'enregistrement stockées dans l'en-tête)
  3. Lire les données de l'enregistrement dans le fichier

Mettre à jour. Cette opération met à jour un enregistrement existant avec de nouvelles données, en remplaçant les nouvelles données par les anciennes. Les étapes de notre mise à jour varient en fonction de la taille des nouvelles données d'enregistrement. Si les nouvelles données correspondent à l'enregistrement existant, nous:

  1. Ecrire les données d'enregistrement dans le fichier en écrasant les données précédentes
  2. Mettre à jour l'attribut qui contient la longueur des données dans l'en-tête de l'enregistrement

Sinon, si les données sont trop volumineuses pour l'enregistrement, nous:

  1. Effectuer une opération de suppression sur l'enregistrement existant
  2. Effectuer une insertion des nouvelles données

Effacer. Cette opération supprime un enregistrement du fichier. Pour supprimer un enregistrement, nous:

  1. Récupérez l'espace alloué à l'enregistrement en cours de suppression en réduisant le fichier, si l'enregistrement est le dernier du fichier, ou en ajoutant son espace à un enregistrement adjacent

  2. Supprimez l'en-tête de l'enregistrement de l'index en remplaçant l'entrée supprimée par la dernière entrée de l'index; cela garantit que l'index est toujours plein, sans espaces vides entre les entrées

Assurer la capacité. Cette opération garantit que la région d'index est suffisamment grande pour accueillir des entrées supplémentaires. Dans une boucle, nous déplaçons les enregistrements du début à la fin du fichier jusqu'à ce qu'il y ait suffisamment d'espace. Pour déplacer un enregistrement, nous:

  1. Recherchez l'en-tête d'enregistrement du premier enregistrement du fichier; notez qu'il s'agit de l'enregistrement avec des données en haut de la région de données d'enregistrement - et non de l'enregistrement avec le premier en-tête de l'index

  2. Lire les données de l'enregistrement cible

  3. Augmentez le fichier de la taille des données de l'enregistrement cible à l'aide de la setLength(long)méthode deRandomAccessFile

  4. Écrivez les données d'enregistrement au bas du fichier

  5. Mettre à jour le pointeur de données dans l'enregistrement qui a été déplacé

  6. Mettre à jour l'en-tête global qui pointe vers les données du premier enregistrement

Détails d'implémentation - pas à pas dans le code source

Nous sommes maintenant prêts à mettre la main à la pâte et à travailler sur le code de l'exemple. Vous pouvez télécharger la source complète à partir de Resources.

Remarque: vous devez utiliser la plate-forme Java 2 (anciennement connue sous le nom de JDK 1.2) pour compiler la source.

Classe BaseRecordsFile

BaseRecordsFileest une classe abstraite et est la principale implémentation de notre exemple. Il définit les principales méthodes d'accès ainsi qu'une série de méthodes utilitaires pour manipuler les enregistrements et les entrées d'index.