Gunakan RandomAccessFile untuk membangun database tingkat rendah

Saat saya mencari ide di situs JavaWorld untuk Langkah demi Langkah bulan ini , saya hanya menemukan beberapa artikel yang membahas tentang akses file tingkat rendah. Meskipun API tingkat tinggi seperti JDBC memberi kita fleksibilitas dan daya yang dibutuhkan dalam aplikasi perusahaan besar, banyak aplikasi yang lebih kecil memerlukan solusi yang lebih sederhana dan elegan.

Pada artikel ini, kita akan membuat ekstensi ke RandomAccessFilekelas yang memungkinkan kita menyimpan dan mengambil record. "File catatan" ini akan setara dengan hashtable yang persisten, memungkinkan objek kunci untuk disimpan dan diambil dari penyimpanan file.

Sebuah primer tentang file dan catatan

Sebelum kita melompat langsung ke contoh, mari kita mulai dengan latar belakang dasar. Kami akan mulai dengan mendefinisikan beberapa istilah yang berkaitan dengan file dan catatan, lalu kami akan membahas secara singkat kelas java.io.RandomAccessFiledan ketergantungan platform.

Terminologi

Definisi berikut disesuaikan dengan contoh kita, daripada terminologi database tradisional.

Rekam - Kumpulan data terkait yang disimpan dalam file. Rekaman biasanya memiliki beberapa bidang, masing-masing merupakan item informasi yang diberi nama dan diketik.

Key - Pengidentifikasi untuk rekaman. Kunci biasanya unik.

File - Kumpulan data berurutan yang disimpan dalam beberapa jenis penyimpanan stabil seperti hard drive.

Akses file tidak penting - Memungkinkan data dibaca dari lokasi arbitrer di file.

File pointer - Angka yang menahan posisi byte berikutnya dari data untuk dibaca dari file.

Record pointer - Record pointer adalah penunjuk file yang menunjuk ke lokasi di mana rekaman tertentu dimulai.

Indeks - Cara sekunder untuk mengakses catatan dalam file; yaitu, memetakan kunci untuk merekam petunjuk.

Heap - File berurutan dari record yang tidak berurutan dan berukuran variabel. Heap memerlukan beberapa pengindeksan eksternal agar dapat mengakses record secara bermakna.

Persistence - Mengacu pada penyimpanan objek atau rekaman untuk jangka waktu tertentu. Panjang ini waktu biasanya lebih lama dari waktu satu proses, sehingga benda biasanya bertahan dalam file atau database.

Tinjauan kelas java.io.RandomAccessFile

Kelas RandomAccessFileadalah cara Java untuk menyediakan akses tidak penting ke file. Kelas memungkinkan kita untuk melompat ke lokasi tertentu dalam file dengan menggunakan seek()metode. Setelah penunjuk file diposisikan, data dapat dibaca dari dan ditulis ke file menggunakan antarmuka DataInputdan DataOutput. Antarmuka ini memungkinkan kami membaca dan menulis data dengan cara yang tidak bergantung platform. Metode praktis lainnya RandomAccessFilememungkinkan kita untuk memeriksa dan mengatur panjang file.

Pertimbangan yang bergantung pada platform

Database modern mengandalkan drive disk untuk penyimpanan. Data pada disk drive disimpan dalam blok, yang didistribusikan ke seluruh trek dan permukaan. The disk mencari waktu dan rotasi penundaan mendikte bagaimana data dapat secara efisien disimpan dan diambil. Sistem manajemen database yang khas sangat bergantung pada atribut disk untuk merampingkan kinerja. Sayangnya (atau untungnya, bergantung pada minat Anda pada file I / O tingkat rendah!), Parameter ini berada jauh dari jangkauan saat menggunakan API file tingkat tinggi seperti java.io. Mengingat fakta ini, contoh kami akan mengabaikan pengoptimalan yang dapat diberikan oleh pengetahuan tentang parameter disk.

Mendesain contoh RecordsFile

Sekarang kami siap merancang contoh kami. Untuk memulai, saya akan menjelaskan beberapa persyaratan dan tujuan desain, menyelesaikan masalah akses bersamaan, dan menentukan format file tingkat rendah. Sebelum melanjutkan ke penerapan, kita juga akan melihat operasi rekaman utama dan algoritme yang sesuai.

Persyaratan dan tujuan

Tujuan utama kami dalam contoh ini adalah menggunakan a RandomAccessFileuntuk menyediakan cara menyimpan dan mengambil data rekaman. Kami akan mengaitkan kunci tipe Stringdengan setiap record sebagai cara untuk mengidentifikasinya secara unik. Panjang kunci akan dibatasi, meskipun data rekaman tidak akan dibatasi. Untuk keperluan contoh ini, catatan kita hanya akan terdiri dari satu bidang - "gumpalan" data biner. Kode file tidak akan mencoba menafsirkan data rekaman dengan cara apa pun.

Sebagai tujuan desain kedua, kami akan meminta agar jumlah record yang didukung file kami tidak diperbaiki pada saat pembuatan. Kami akan mengizinkan file untuk tumbuh dan menyusut saat catatan dimasukkan dan dihapus. Karena indeks dan data catatan kita akan disimpan dalam file yang sama, pembatasan ini akan menyebabkan kita menambahkan logika tambahan untuk secara dinamis menambah ruang indeks dengan mengatur ulang catatan.

Mengakses data dalam file lipat lebih lambat daripada mengakses data dalam memori. Artinya, jumlah akses file yang dilakukan database akan menjadi faktor penentu performa. Kami akan mengharuskan operasi database utama kami tidak bergantung pada jumlah record di file. Dengan kata lain, mereka akan memiliki waktu pemesanan yang konstan sehubungan dengan akses file.

Sebagai persyaratan terakhir, kami akan menganggap indeks kami cukup kecil untuk dimuat ke dalam memori. Ini akan mempermudah implementasi kami untuk memenuhi persyaratan yang menentukan waktu akses. Kami akan mencerminkan indeks di a Hashtable, yang menyediakan pencarian header rekaman langsung.

Koreksi Kode

Kode untuk artikel ini memiliki bug yang menyebabkannya memunculkan NullPointerException dalam banyak kemungkinan kasus. Ada rutinitas bernama insureIndexSpace (int) di kelas abstrak BaseRecordsFile. Kode ini dimaksudkan untuk memindahkan rekaman yang ada ke akhir file jika area indeks perlu diperluas. Setelah kapasitas rekaman "pertama" disetel ulang ke ukuran sebenarnya, rekaman itu dipindahkan ke akhir. DataStartPtr kemudian diatur untuk menunjuk ke catatan kedua dalam file. Sayangnya, jika ada ruang kosong di rekaman pertama, dataStartPtr baru tidak akan menunjuk ke rekaman yang valid, karena itu bertambah dengan panjang rekaman pertama daripada kapasitasnya. Sumber Java yang dimodifikasi untuk BaseRecordsFile dapat ditemukan di Resources.

dari Ron Walkup

Insinyur Perangkat Lunak Senior

bioMerieux, Inc.

Sinkronisasi dan akses file secara bersamaan

Untuk mempermudah, kita mulai dengan hanya mendukung model single-thread, di mana permintaan file dilarang terjadi secara bersamaan. Kita dapat melakukannya dengan menyinkronkan metode akses publik dari kelas BaseRecordsFiledan RecordsFile. Perhatikan bahwa Anda dapat melonggarkan pembatasan ini untuk menambahkan dukungan untuk pembacaan dan penulisan secara bersamaan pada record yang tidak berkonflik: Anda harus mempertahankan daftar record yang dikunci dan interleave read dan write untuk permintaan yang berbarengan.

Rincian format file

Kami sekarang akan secara eksplisit menentukan format file catatan. File tersebut terdiri dari tiga wilayah, masing-masing dengan formatnya sendiri.

Wilayah header file. Region pertama ini menyimpan dua header penting yang diperlukan untuk mengakses record di file kami. Header pertama, disebut penunjuk awal data, adalah longyang menunjuk ke awal data rekaman. Nilai ini menunjukkan ukuran wilayah indeks. Header kedua, disebut header num records, adalah intyang memberikan jumlah record dalam database. Wilayah header dimulai pada byte pertama file dan diperpanjang untuk FILE_HEADERS_REGION_LENGTHbyte. Kami akan menggunakan readLong()dan readInt()untuk membaca header, writeLong()dan writeInt()untuk menulis header.

Wilayah indeks. Setiap entri dalam indeks terdiri dari kunci dan header rekaman. Indeks dimulai pada byte pertama setelah wilayah header file dan meluas hingga byte sebelum penunjuk awal data. Dari informasi ini, kita dapat menghitung penunjuk file ke awal salah satu entri n dalam indeks. Entri memiliki panjang tetap - data kunci dimulai pada byte pertama dalam entri indeks dan diperpanjang MAX_KEY_LENGTHbyte. Header record yang sesuai untuk kunci tertentu mengikuti segera setelah kunci dalam indeks. Header record memberi tahu kita di mana lokasi data, berapa byte yang dapat disimpan record, dan berapa byte yang sebenarnya dipegangnya. Entri indeks dalam indeks file tidak dalam urutan tertentu dan tidak dipetakan ke urutan penyimpanan catatan dalam file.

Rekam wilayah data. Wilayah data rekaman dimulai pada lokasi yang ditunjukkan oleh penunjuk awal data dan meluas ke akhir file. Rekaman diposisikan secara berurutan dalam file tanpa ada ruang kosong yang diizinkan di antara rekaman. Bagian file ini terdiri dari data mentah tanpa header atau informasi kunci. File database berakhir di blok terakhir dari catatan terakhir dalam file, jadi tidak ada ruang tambahan di akhir file. File tumbuh dan menyusut saat catatan ditambahkan dan dihapus.

Ukuran yang dialokasikan ke rekaman tidak selalu sesuai dengan jumlah data aktual yang dikandung rekaman. Rekor dapat dianggap sebagai wadah - mungkin hanya sebagian penuh. Data catatan yang valid ditempatkan di awal catatan.

Operasi yang didukung dan algoritme mereka

The RecordsFileakan mendukung operasi utama sebagai berikut:

  • Sisipkan - Menambahkan catatan baru ke file

  • Baca - Membaca rekaman dari file

  • Perbarui - Memperbarui catatan

  • Hapus - Menghapus record

  • Pastikan kapasitas - Menumbuhkan wilayah indeks untuk mengakomodasi catatan baru

Sebelum kita melangkah melalui kode sumber, mari kita bahas algoritma yang dipilih untuk masing-masing operasi ini:

Memasukkan. Operasi ini memasukkan catatan baru ke dalam file. Untuk memasukkan, kami:

  1. Pastikan kunci yang dimasukkan belum ada di dalam file
  2. Pastikan wilayah indeks cukup besar untuk entri tambahan
  3. Temukan ruang kosong di file yang cukup besar untuk menyimpan rekaman
  4. Tulis data record ke file
  5. Tambahkan header record ke indeks

Baca. Operasi ini mengambil rekaman yang diminta dari file berdasarkan kunci. Untuk mengambil record, kita:

  1. Gunakan indeks untuk memetakan kunci yang diberikan ke header record
  2. Cari ke awal data (menggunakan penunjuk ke data catatan yang disimpan di header)
  3. Baca data catatan dari file

Memperbarui. Operasi ini memperbarui catatan yang ada dengan data baru, menggantikan data baru dengan yang lama. Langkah-langkah untuk pembaruan kami berbeda-beda, bergantung pada ukuran data catatan baru. Jika data baru cocok dengan catatan yang ada, kami:

  1. Tulis data rekaman ke file, menimpa data sebelumnya
  2. Perbarui atribut yang menyimpan panjang data di header record

Sebaliknya, jika datanya terlalu besar untuk dicatat, kami:

  1. Lakukan operasi penghapusan pada rekaman yang ada
  2. Lakukan penyisipan data baru

Menghapus. Operasi ini menghapus record dari file. Untuk menghapus record, kami:

  1. Dapatkan kembali ruang yang dialokasikan ke rekaman yang sedang dihapus dengan menyusutkan file, jika rekaman adalah yang terakhir dalam file, atau dengan menambahkan ruangnya ke rekaman yang berdekatan

  2. Hapus header record dari indeks dengan mengganti entri yang dihapus dengan entri terakhir di indeks; ini memastikan indeks selalu penuh, tanpa spasi kosong di antara entri

Pastikan kapasitas. Operasi ini memastikan wilayah indeks cukup besar untuk menampung entri tambahan. Dalam satu putaran, kami memindahkan rekaman dari depan ke akhir file hingga tersedia cukup ruang. Untuk memindahkan satu record kita:

  1. Temukan header record dari record pertama dalam file; perhatikan bahwa ini adalah record dengan data di bagian atas record data region - bukan record dengan header pertama dalam indeks

  2. Baca data catatan target

  3. Kembangkan file dengan ukuran data rekaman target dengan menggunakan setLength(long)metode diRandomAccessFile

  4. Tulis data record ke bagian bawah file

  5. Perbarui penunjuk data dalam catatan yang dipindahkan

  6. Perbarui header global yang mengarah ke data rekaman pertama

Detail implementasi - melangkah melalui kode sumber

Kami sekarang siap untuk mengotori tangan kami dan mengerjakan kode sebagai contoh. Anda dapat mengunduh sumber lengkap dari Sumber.

Catatan: Anda harus menggunakan platform Java 2 (sebelumnya dikenal sebagai JDK 1.2) untuk mengompilasi sumber.

Kelas BaseRecordsFile

BaseRecordsFileadalah kelas abstrak dan merupakan implementasi utama dari contoh kami. Ini mendefinisikan metode akses utama serta banyak metode utilitas untuk memanipulasi catatan dan entri indeks.