Ivkin I

Въведение.

Един от основните проблеми при съхраняването на толкова голям брой файлове е необходимостта от интензивна работа с тях. В случай, че тези файлове постоянно се изискват за преместване, актуализиране, изтриване или добавяне на нови файлове, натоварването на файловата система се увеличава драстично. Първо, трябва постоянно да актуализирате файловата таблица, второ, фрагментацията се увеличава и трето, свободно място на устройството се губи. По-скоро тясно място е предварително разпределеният размер на клъстера във файловата система. В случай, че има много файлове и те са толкова малки, че не надвишават размера на клъстера (например 32 килобайта), режийните разходи за тяхното съхранение могат да бъдат сравними с общия размер на съхраняваните данни.

Определение на изходните данни.

Броят на файловете трябва да е достатъчно голям. Много съвременни файлови системи използват специфично изпълнение на файлова таблица (която е база данни), която съхранява информация за съдържанието на томове на външно устройство за съхранение. Например във файловата система NTFS тази функция се изпълнява от MFT - Главна файлова таблица - в нея редовете съответстват на файловете за обем, а колоните съответстват на атрибутите на файла. При значителен брой файлове броят на записите в тази таблица става толкова голям, че забавя работата с файловата система. В хода на практическата работа беше разкрито, че когато се използва файловата система NTFS, работата значително се забавя с няколкостотин милиона файла. Следователно необходимият брой файлове за съхранение трябва да надвишава 200 милиона и да бъде ограничен до приблизително 1 милиард файла.

Проектиране на структура от данни за съхранение на файлове.

Тази стратегия за съхранение се нарича произволно съхранение. Стратегията за случайно съхранение по правило има доста висока ефективност при вмъкване на нови данни; тя се оценява като O (1). В същото време има проблем с потенциално ниско време за извличане, но този проблем се решава чрез използване на индекси.

Размерът на съхранените данни не е задължителен. В този случай ще е необходимо да се прочетат данните до първата срещана последователност от байтове, която условно ще се нарича "разделител". Този метод е допустим, но експериментът показва, че в този случай производителността на четене леко намалява, тъй като данните трябва да се четат на малки порции и за всяка порция е необходимо да се провери дали е открит разделителят. Следователно за всеки запис в индекса е необходимо да се съхраняват данни като отместването спрямо началото на файла и размера на съхранените данни.

Съхранението на отместването като брой байтове от началото на файла е неефективно поради следните причини. В случай, че 32-битово неподписано цяло число се използва като контейнер за тази стойност, максимално възможната стойност може да бъде само 2 32 или 4 гигабайта данни. Това е сравнително малък размер на данните, който бързо ще бъде надвишен, ако има голям брой файлове. Следователно ще е необходимо да се използва 64-битово цяло число, което веднага води до необходимостта да се съхраняват 8 байта за всяко отместване от началото на файла. Лесно е да се изчисли, че за един милион файлове разходите за съхраняване на информация за компенсации ще бъдат приблизително равни на 8 мегабайта, а за сто милиона - 800 мегабайта. Това потребление на памет е неефективно, така че трябва да изберете различен индикатор.

По-специално във файловата система NTFS, размерът на блока е 512 байта. Това означава, че данните трябва да се записват (и да се четат) на външното устройство за съхранение в блокове от 512 байта или на парчета, които се делят на 512 (в този случай блокирането ще се извърши от самата файлова система). За да се избегнат проблеми с крайните данни, чийто размер не е кратен на 512, е необходимо да се осигури запис за подравняване, който ще направи размера на останалите данни кратен на 512.

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

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

Съответно публикуваният индекс на данните трябва да се основава на следните показатели:

1) идентификатор на файл (това може да бъде например хеш функция от името му, глобално уникален идентификатор GUID и т.н.) - вероятно той трябва да заема 8 байта (64-битово цяло число);

2) отместване спрямо началото на двоичния обект - 4 байта;

3) размерът на съхранените данни - 4 байта;

4) в случай на използване на няколко обекта, идентификаторът на двоичен обект - вероятно 1 байт, позволява използването на 256 двоични обекта, които ще имат общ размер в системата NTFS от около половин петабайт.

За бързи търсения индексът трябва да бъде организиран в структура, която позволява бързи и ефективни търсения. Като такава структура се предлага да се използва червено-черно дърво за търсене.

Въз основа на тази метаинформация индексът може да бъде възстановен, но е очевидно, че когато алгоритъмът за възстановяване на индекса работи, LOB няма да бъде наличен за четене и запис. Това явление може да се нарече престой или „студен старт“ на системата, отговорна за съхранението на двоичния обект. По този начин всеки запис в голям двоичен обект трябва да се състои от метаинформация, действителни данни и подравняване и има структурата, показана на фигурата.

Фигура 1 - Структурата на запис в голям двоичен обект

За управление на данни в голям двоичен обект се използва флаг или флаг, стойността му може да бъде зададена в диапазона от 0 до 2, което означава съответно „активен“, „изтрит“, „в очакване“. За да изтриете данни от обект, просто маркирайте запис с флаг "изтрит" и изтрийте данните от индекса, докато следващия път, когато индексът бъде възстановен, изтритите записи просто ще бъдат пропуснати. Стойността „в очакване“ се използва при добавяне на данни. Ако новите данни заемат повече от 512 байта заедно с метаинформация, вероятно в случай на софтуерни или хардуерни неизправности те няма да бъдат добавени напълно, тъй като операцията за пълно добавяне на тези данни към обекта няма да бъде атомна. За да се избегнат потенциални проблеми с повреда на данните, когато се добавят нови данни, те първо се добавят с изчакващия флаг, а когато добавянето завърши, флагът се променя на активен. Изчакващите записи също се изключват, когато индексът се възстановява, защото това означава, че те са били повредени и процесът на запис не е завършен.

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