Използвайте RandomAccessFile за изграждане на база данни на ниско ниво

Докато търсих в сайта на JavaWorld идеи за този месец стъпка по стъпка , попаднах на само няколко статии, обхващащи достъп до файлове на ниско ниво. Въпреки че API на високо ниво като JDBC ни дават гъвкавостта и мощта, необходими за големи корпоративни приложения, много по-малки приложения изискват по-просто и елегантно решение.

В тази статия ще изградим разширение за RandomAccessFileкласа, което ни позволява да съхраняваме и извличаме записи. Този "файл с записи" ще бъде еквивалентен на постоянна хеш-таблица, позволяваща съхраняване и извличане на ключови обекти от хранилището на файлове.

Буквар за файлове и записи

Преди да скочим стремглаво в примера, нека започнем с основен фон. Ще започнем с дефиниране на някои термини, отнасящи се до файлове и записи, след което ще обсъдим накратко java.io.RandomAccessFileзависимостта от класа и платформата.

Терминология

Следните определения са настроени по-скоро на нашия пример, отколкото на традиционната терминология на базата данни.

Запис - Колекция от свързани данни, съхранявани във файл. Записът обикновено има множество полета, всяко от които е наименуван и въведен елемент на информация.

Ключ - Идентификатор на запис. Ключовете обикновено са уникални.

Файл - Последователно събиране на данни, съхранявани в някакъв вид стабилно хранилище, като твърд диск.

Непоследователен достъп до файл - Позволява четене на данни от произволни местоположения във файла.

Файлов указател - Число, заемащо позицията на следващия байт данни, които трябва да бъдат прочетени от файл.

Показалец за запис - указателят за запис е указател на файл, който сочи към местоположението, където започва определен запис.

Индекс - Вторично средство за достъп до записи във файл; това означава, че картографира ключове за записване на указатели.

Heap - Пореден файл от неподредени и променливи записи. Купчината изисква известно външно индексиране, за да има смислен достъп до записите.

Постоянство - Отнася се за съхраняване на обект или запис за определен период от време. Този период от време обикновено е по-дълъг от периода на един процес, така че обектите обикновено се съхраняват във файлове или бази данни.

Преглед на класа java.io.RandomAccessFile

Class RandomAccessFileе начинът на Java да осигури несеквенсивен достъп до файлове. Класът ни позволява да преминем към определено място във файла с помощта на seek()метода. След като показалеца на файл е бил поставен, данните могат да бъдат четени от и записани във файла с помощта на DataInputи DataOutputинтерфейси. Тези интерфейси ни позволяват да четем и записваме данни по независим от платформата начин. Други удобни методи RandomAccessFileни позволяват да проверяваме и задаваме дължината на файла.

Съображения, зависими от платформата

Съвременните бази данни разчитат на дискови устройства за съхранение. Данните на дисковото устройство се съхраняват в блокове, които се разпределят по трасета и повърхности. Времето за търсене на диска и закъснението при въртене диктуват как данните могат да бъдат най-ефективно съхранени и извлечени. Типична система за управление на база данни разчита тясно на атрибутите на диска, за да рационализира производителността. За съжаление (или за щастие, в зависимост от интереса ви към входно-изходни файлове на ниско ниво!), Тези параметри са далеч от обсега, когато използвате API на файлове на високо ниво, като например java.io. Като се има предвид този факт, нашият пример ще пренебрегне оптимизациите, които знанието за параметрите на диска може да осигури.

Проектиране на RecordsFile пример

Сега сме готови да проектираме нашия пример. За начало ще изложа някои изисквания и цели за проектиране, ще разреша проблеми с едновременния достъп и ще посоча файловия формат на ниско ниво. Преди да пристъпим към внедряването, ще разгледаме и основните операции по запис и съответните им алгоритми.

Изисквания и цели

Нашата основна цел в този пример е да използваме a, за RandomAccessFileда осигурим начин за съхраняване и извличане на данни от записи. Ще свържем ключ от тип Stringс всеки запис като средство за уникалното му идентифициране. Бутоните ще бъдат ограничени до максимална дължина, въпреки че данните за записа няма да бъдат ограничени. За целите на този пример нашите записи ще се състоят само от едно поле - „петно“ от двоични данни. Кодът на файла няма да се опитва по никакъв начин да интерпретира данните от записа.

Като втора цел на дизайна ще изискваме броят на записите, които поддържа нашият файл, да не бъде фиксиран по време на създаването. Ще позволим на файла да расте и да се свива, докато записите се вмъкват и премахват. Тъй като данните ни за индекси и записи ще се съхраняват в един и същ файл, това ограничение ще ни накара да добавим допълнителна логика за динамично увеличаване на пространството на индекса чрез реорганизиране на записите.

Достъпът до данни във файл е с порядъци по-бавен от достъпа до данни в паметта. Това означава, че броят на достъпите до файлове, които базата данни изпълнява, ще бъде определящият фактор за производителност. Ще изискваме основните ни операции с базата данни да не зависят от броя на записите във файла. С други думи, те ще имат постоянно време за поръчка по отношение на достъпа до файлове.

Като последно изискване ще приемем, че нашият индекс е достатъчно малък, за да се зареди в паметта. Това ще улесни прилагането ни да изпълни изискването, което диктува времето за достъп. Ще отразяваме индекса в a Hashtable, който осигурява незабавно търсене в заглавието на записа.

Корекция на кода

Кодът за тази статия има грешка, която го кара да хвърля NullPointerException в много възможни случаи. Има рутина с име insureIndexSpace (int) в абстрактния клас BaseRecordsFile. Кодът е предназначен да премести съществуващите записи в края на файла, ако областта на индекса трябва да се разшири. След като капацитетът на "първия" запис бъде възстановен до действителния му размер, той се премества до края. След това dataStartPtr се настройва да сочи към втория запис във файла. За съжаление, ако в първия запис имаше свободно място, новият dataStartPtr няма да сочи към валиден запис, тъй като той бе увеличен с дължината на първия запис, а не с неговия капацитет. Модифицираният Java източник за BaseRecordsFile може да бъде намерен в Resources.

от Ron Walkup

Старши софтуерен инженер

bioMerieux, Inc.

Синхронизация и едновременен достъп до файлове

За улеснение започваме като поддържаме само модел с една нишка, при който е забранено да се извършват едновременно заявки за файлове. Ние можем да постигнем това чрез синхронизиране на методите за публичен достъп на BaseRecordsFileи RecordsFileкласове. Имайте предвид, че можете да облекчите това ограничение, за да добавите поддръжка за едновременни четения и записи на несъвместими записи: Ще трябва да поддържате списък с заключени записи и да четете и записвате едновременно за едновременни заявки.

Подробности за файловия формат

Сега изрично ще дефинираме формата на файла със записите. Файлът се състои от три региона, всеки със собствен формат.

Регионът на заглавките на файлове. Този първи регион съдържа двете основни заглавки, необходими за достъп до записите в нашия файл. Първият хедър, наречен указател за стартиране на данни, е, longкойто сочи към началото на данните от записа. Тази стойност ни казва размера на индексния регион. Вторият заглавие, наречен заглавка num records, е, 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. Намерете заглавката на записа на първия запис във файла; имайте предвид, че това е записът с данни в горната част на областта с данни на записа, а не записът с първата заглавка в индекса

  2. Прочетете данните на целевия запис

  3. Увеличете файла по размера на данните на целевия запис, като използвате setLength(long)метода вRandomAccessFile

  4. Запишете данните от записа в долната част на файла

  5. Актуализирайте указателя за данни в записа, който е преместен

  6. Актуализирайте глобалния заглавие, което сочи към данните на първия запис

Подробности за изпълнението - стъпка през изходния код

Вече сме готови да си замърсим ръцете и да работим с кода за примера. Можете да изтеглите пълния източник от ресурси.

Забележка: Трябва да използвате платформата Java 2 (известна преди като JDK 1.2), за да компилирате източника.

Class BaseRecordsFile

BaseRecordsFileе абстрактен клас и е основната реализация на нашия пример. Той дефинира основните методи за достъп, както и множество полезни методи за манипулиране на записи и записи в индекса.