RandomAccessFileを使用して、低レベルのデータベースを構築します

今月のステップバイステップのアイデアをJavaWorldのサイトで検索したところ、低レベルのファイルアクセスを扱った記事がいくつかありました。JDBCなどの高レベルAPIは、大規模なエンタープライズアプリケーションに必要な柔軟性とパワーを提供しますが、多くの小規模なアプリケーションには、よりシンプルで洗練されたソリューションが必要です。

この記事では、RandomAccessFileレコードの保存と取得を可能にするクラスの拡張機能を構築します。この「レコードファイル」は永続的なハッシュテーブルと同等であり、キー付きオブジェクトを保存したり、ファイルストレージから取得したりできます。

ファイルとレコードの入門書

例に真っ向から飛び込む前に、基本的な背景説明から始めましょう。ファイルとレコードに関連するいくつかの用語を定義することから始め、次にクラスjava.io.RandomAccessFileとプラットフォームの依存関係について簡単に説明します。

用語

次の定義は、従来のデータベース用語ではなく、この例に合わせて調整されています。

レコード-ファイルに保存されている関連データのコレクション。通常、レコードには複数のフィールドがあり、それぞれが名前付きで入力された情報項目です。

キー-レコードの識別子。キーは通常一意です。

ファイル-ハードドライブなどのある種の安定したストレージに保存されているデータの順次コレクション。

非順次ファイルアクセス-ファイル内の任意の場所からデータを読み取ることができます。

ファイルポインタ-ファイルから読み取るデータの次のバイトの位置を保持する数値。

レコードポインタ-レコードポインタは、特定のレコードが始まる場所を指すファイルポインタです。

インデックス-ファイル内のレコードにアクセスするための2番目の手段。つまり、キーをレコードポインタにマップします。

ヒープ-順序付けされていない可変サイズのレコードのシーケンシャルファイル。ヒープは、レコードに有意義にアクセスするために、いくつかの外部インデックスを必要とします。

永続性-オブジェクトまたはレコードを特定の期間保存することを指します。この時間の長さは、通常、長い一つのプロセスのスパンよりも、そのオブジェクトは通常されている永続ファイルまたはデータベースに。

クラスjava.io.RandomAccessFileの概要

クラスRandomAccessFileは、ファイルへの非順次アクセスを提供するJavaの方法です。このクラスを使用すると、seek()メソッドを使用してファイル内の特定の場所にジャンプできます。ファイルポインタが配置されると、DataInputおよびDataOutputインターフェイスを使用してファイルからデータを読み書きできます。これらのインターフェースにより、プラットフォームに依存しない方法でデータの読み取りと書き込みを行うことができます。の他の便利な方法をRandomAccessFile使用すると、ファイルの長さを確認して設定できます。

プラットフォームに依存する考慮事項

最新のデータベースは、ストレージをディスクドライブに依存しています。ディスクドライブ上のデータはブロックに保存され、トラックとサーフェスに分散されます。ディスクのシーク時間と回転遅延により、データを最も効率的に保存および取得する方法が決まります。一般的なデータベース管理システムは、パフォーマンスを合理化するためにディスクの属性に密接に依存しています。残念ながら（または幸いなことに、低レベルのファイルI / Oに関心がある場合は！）、などの高レベルのファイルAPIを使用する場合、これらのパラメーターは手の届かないところにありますjava.io。この事実を考えると、この例では、ディスクのパラメーターの知識が提供できる最適化を無視します。

RecordsFileの例の設計

これで、例を設計する準備が整いました。まず、いくつかの設計要件と目標を設定し、同時アクセスの問題を解決し、低レベルのファイル形式を指定します。実装に進む前に、メインのレコード操作とそれに対応するアルゴリズムについても説明します。

要件と目標

この例の主な目標は、を使用しRandomAccessFileてレコードデータを保存および取得する方法を提供することです。String一意に識別する手段として、タイプのキーを各レコードに関連付けます。レコードデータは制限されませんが、キーは最大長に制限されます。この例では、レコードは1つのフィールド（バイナリデータの「ブロブ」）のみで構成されます。ファイルコードは、レコードデータを解釈しようとはしません。

2番目の設計目標として、ファイルがサポートするレコードの数を作成時に固定しないようにする必要があります。レコードの挿入と削除に応じて、ファイルを拡大および縮小できるようにします。インデックスとレコードデータは同じファイルに保存されるため、この制限により、レコードを再編成することでインデックススペースを動的に増やすロジックが追加されます。

ファイル内のデータへのアクセスは、メモリ内のデータへのアクセスよりも桁違いに遅くなります。これは、データベースが実行するファイルアクセスの数がパフォーマンス要因を決定することを意味します。メインのデータベース操作がファイル内のレコード数に依存しないようにする必要があります。言い換えれば、それらはファイルアクセスに関して一定の順序時間になります。

最後の要件として、インデックスがメモリにロードするのに十分小さいと想定します。これにより、実装がアクセス時間を規定する要件を満たすことが容易になります。インデックスをにミラーリングしHashtableます。これにより、レコードヘッダーがすぐに検索されます。

コード訂正

この記事のコードにはバグがあり、多くの場合にNullPointerExceptionがスローされます。抽象クラスBaseRecordsFileにはinsureIndexSpace（int）という名前のルーチンがあります。このコードは、インデックス領域を拡張する必要がある場合に、既存のレコードをファイルの最後に移動することを目的としています。「最初の」レコードの容量が実際のサイズにリセットされた後、最後に移動されます。次に、dataStartPtrは、ファイルの2番目のレコードを指すように設定されます。残念ながら、最初のレコードに空き領域がある場合、新しいdataStartPtrは、容量ではなく最初のレコードの長さだけインクリメントされるため、有効なレコードを指しません。BaseRecordsFileの変更されたJavaソースは、「リソース」にあります。

ロンウォークアップから

シニアソフトウェアエンジニア

bioMerieux、Inc。

同期と同時ファイルアクセス

簡単にするために、ファイル要求が同時に発生することを禁止されているシングルスレッドモデルのみをサポートすることから始めます。これはBaseRecordsFile、RecordsFileクラスとクラスのパブリックアクセスメソッドを同期することで実現できます。この制限を緩和して、競合しないレコードでの同時読み取りと書き込みのサポートを追加できることに注意してください。ロックされたレコードのリストを維持し、同時要求の読み取りと書き込みをインターリーブする必要があります。

ファイル形式の詳細

ここで、レコードファイルの形式を明示的に定義します。このファイルは3つの領域で構成されており、それぞれに独自の形式があります。

ファイルヘッダー領域。この最初の領域には、ファイル内のレコードにアクセスするために必要な2つの重要なヘッダーが含まれています。最初のヘッダは、呼び出されたデータは、ポインタを開始し、あるlong記録データの先頭を指していること。この値は、インデックス領域のサイズを示します。呼ばれる第二のヘッダ、NUMレコードヘッダは、あるintデータベース内のレコードの数を示しています。ヘッダー領域は、ファイルの最初のバイトから始まり、FILE_HEADERS_REGION_LENGTHバイト単位で拡張されます。私たちは、使用しますreadLong()とreadInt()、ヘッダーを読み取るために、とwriteLong()とwriteInt()のヘッダーを書くこと。

インデックス領域。インデックスの各エントリは、キーとレコードヘッダーで構成されます。インデックスは、ファイルヘッダー領域の後の最初のバイトから始まり、データ開始ポインターの前のバイトまで拡張されます。この情報から、インデックス内のn個のエントリのいずれかの先頭へのファイルポインタを計算できます。エントリの長さは固定されています。キーデータはインデックスエントリの最初のバイトから始まり、バイトを拡張しMAX_KEY_LENGTHます。特定のキーに対応するレコードヘッダーは、インデックス内のキーの直後に続きます。レコードヘッダーは、データの場所、レコードが保持できるバイト数、および実際に保持しているバイト数を示します。ファイルインデックスのインデックスエントリは特定の順序ではなく、レコードがファイルに保存されている順序にマップされません。

データ領域を記録します。レコードデータ領域は、データ開始ポインタで示された場所から始まり、ファイルの終わりまで拡張されます。レコードはファイル内で連続して配置され、レコード間に空き領域は許可されません。ファイルのこの部分は、ヘッダーやキー情報のない生データで構成されています。データベースファイルは、ファイルの最後のレコードの最後のブロックで終了するため、ファイルの最後に余分なスペースはありません。レコードが追加および削除されると、ファイルは拡大および縮小します。

レコードに割り当てられたサイズは、レコードに含まれる実際のデータ量に常に対応しているとは限りません。レコードはコンテナと考えることができます-部分的にしか満たされていない可能性があります。有効なレコードデータは、レコードの先頭に配置されます。

サポートされている操作とそのアルゴリズム

RecordsFile次の主要な操作をサポートします：

  • 挿入-ファイルに新しいレコードを追加します

  • 読み取り-ファイルからレコードを読み取ります

  • 更新-レコードを更新します

  • 削除-レコードを削除します

  • 容量の確保-新しいレコードに対応するためにインデックス領域を拡大します

ソースコードをステップ実行する前に、これらの各操作に対して選択されたアルゴリズムを確認しましょう。

インサート。この操作により、ファイルに新しいレコードが挿入されます。挿入するには、次のようにします。

  1. 挿入するキーがファイルに含まれていないことを確認してください
  2. インデックス領域が追加のエントリに対して十分な大きさであることを確認してください
  3. レコードを保持するのに十分な大きさのファイル内の空き領域を見つけます
  4. レコードデータをファイルに書き込む
  5. レコードヘッダーをインデックスに追加します

読んだ。この操作は、キーに基づいてファイルから要求されたレコードを取得します。レコードを取得するには、次のようにします。

  1. インデックスを使用して、指定されたキーをレコードヘッダーにマップします
  2. データの先頭までシークします（ヘッダーに格納されているレコードデータへのポインターを使用）
  3. ファイルからレコードのデータを読み取ります

更新。この操作により、既存のレコードが新しいデータで更新され、新しいデータが古いデータに置き換えられます。更新の手順は、新しいレコードデータのサイズによって異なります。新しいデータが既存のレコードに適合する場合、次のことを行います。

  1. 以前のデータを上書きして、レコードデータをファイルに書き込みます
  2. レコードのヘッダーのデータの長さを保持する属性を更新します

それ以外の場合、データがレコードに対して大きすぎる場合は、次のようにします。

  1. 既存のレコードに対して削除操作を実行します
  2. 新しいデータの挿入を実行します

削除します。この操作により、ファイルからレコードが削除されます。レコードを削除するには、次のようにします。

  1. レコードがファイル内の最後のレコードである場合はファイルを縮小するか、隣接するレコードにそのスペースを追加することにより、削除されるレコードに割り当てられたスペースを再利用します。

  2. 削除するエントリをインデックスの最後のエントリに置き換えることにより、レコードのヘッダーをインデックスから削除します。これにより、エントリ間に空のスペースがなく、インデックスが常にいっぱいになります。

容量を確保します。この操作により、インデックス領域が追加のエントリを収容するのに十分な大きさになるようにします。ループでは、十分なスペースができるまで、ファイルの先頭から末尾にレコードを移動します。1つのレコードを移動するには、次のようにします。

  1. ファイルの最初のレコードのレコードヘッダーを見つけます。これは、レコードデータ領域の上部にデータがあるレコードであり、インデックスの最初のヘッダーを持つレコードではないことに注意してください。

  2. ターゲットレコードのデータを読み取る

  3. 次のsetLength(long)方法を使用して、ターゲットレコードのデータのサイズでファイルを拡張します。RandomAccessFile

  4. ファイルの最後にレコードデータを書き込みます

  5. 移動されたレコードのデータポインタを更新します

  6. 最初のレコードのデータを指すグローバルヘッダーを更新します

実装の詳細-ソースコードをステップスルー

これで、手を汚して、例のコードを処理する準備が整いました。完全なソースはリソースからダウンロードできます。

注：ソースをコンパイルするには、Java 2プラットフォーム（旧称JDK 1.2）を使用する必要があります。

クラスBaseRecordsFile

BaseRecordsFileは抽象クラスであり、この例の主要な実装です。これは、メインのアクセスメソッドと、レコードおよびインデックスエントリを操作するための多数のユーティリティメソッドを定義します。