УДК 004.65

ПРИМЕНЕНИЕ БИНАРНЫХ ОБЪЕКТОВ В КАЧЕСТВЕ ХРАНИЛИЩ ДЛЯ БОЛЬШОГО КОЛИЧЕСТВА ФАЙЛОВ

Ивкин Игорь Михайлович
Пензенский Государственный Университет
Аспирант кафедры МО и ПЭВМ

Аннотация
Статья посвящена применению бинарных объектов в качестве хранилищ для большого количества файлов.

Ключевые слова: бинарные объекты, хранилище файлов


USE OF BINARY OBJECTS AS REPOSITORIES FOR LARGE AMOUNTS OF FILES

Ivkin Igor Michaylovitch
Penza State University
Post-graduate of department of CS

Abstract
This article is about use of binary objects as repositories for large amounts of files.

Keywords: binary objects, file repositories


Рубрика: 05.00.00 ТЕХНИЧЕСКИЕ НАУКИ

Библиографическая ссылка на статью:
Ивкин И.М. Применение бинарных объектов в качестве хранилищ для большого количества файлов // Современные научные исследования и инновации. 2012. № 6 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2012/06/15556 (дата обращения: 30.09.2017).

Введение.

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

Одна из серьезных проблем при хранении такого большого количества файлов – необходимость интенсивной работы с ними. В том случае, если эти файлы постоянно требуется перемещать, обновлять, удалять или добавлять новые файлы, резко возрастает нагрузка на файловую систему. Во-первых, приходится постоянно обновлять файловую таблицу, во-вторых, возрастает фрагментация, в-третьих, нерационально расходуется свободное пространство на накопителе. Довольно узким местом является заранее выделяемый размер кластера в файловой системе. В том случае, если файлов очень много, и они настолько небольшие, что не превосходят размер кластера (например, 32 килобайта), накладные расходы на их хранение могут быть сопоставимы с общим размером хранимых данных.

В данной работе предлагается метод хранения и управления большим количеством однотипных файлов, основанный на использовании больших бинарных объектов. Данный метод должен в определенной степени решить обозначенные выше проблемы.  Большие бинарные объекты или BLOB (Binary Large OBject) представляют собой массивы двоичных данных. Преимущественно, такие объекты используются в СУБД и являются специальными типами данных, предназначенными для хранения крупных файлов в базе данных, таких как изображения, видеоролики, а также других типов.

Определение исходных данных.

Количество файлов должно быть достаточно большим. Во многих современных файловых системах используется определенная реализация файловой таблицы (представляющей собой базу данных), в которой хранится информация о содержимом томов внешнего запоминающего устройства. Например, в файловой системе NTFS такую функцию выполняет MFT – Master File Table – в ней строки соответствуют файлам тома, а столбцы – атрибутам файлов. При значительном количестве файлов число записей в данной таблице становится большим настолько, что это замедляет работу с файловой системой. В ходе практической деятельности было выявлено, что при использовании файловой системы NTFS работа существенно замедляется при нескольких сотнях миллионов файлов. Таким образом, требуемое количество файлов для хранения должно превышать 200 миллионов и ограничиваться приблизительно миллиардом файлов.

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

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

Такая стратегия размещения данных в хранилище называется произвольным хранением.  У стратегии произвольного хранения, как правило, достаточно высокая эффективность вставки новых данных, она оценивается как О(1). При этом существует проблема потенциально низкого времени извлечения, однако, эта проблема решается использованием индексов.

Наиболее простой и очевидный вариант – использовать в качестве адреса определенной записи в составе файла смещение относительно начала файла, заданное в количестве байт. Таким образом, для чтения можно будет немедленно переместиться к указанной позиции в файле. Однако, здесь есть две проблемы: во-первых, необходимо знать также, каков размер хранимых данных по определенному адресу, чтобы иметь возможность быстро считать их, во-вторых, хранение смещения в виде количества байт – неэффективное в плане потребления ресурсов решение.

Размер хранимых данных можно не использовать. В таком случае необходимо будет считывать данные до первой встречаемой последовательности байт, которая условно будет названа «разделителем». Этот метод допустим, но эксперимент показал, что в таком случае несколько снижается быстродействие чтения, поскольку считывать данные приходится небольшими порциями и для каждой порции необходимо проверять, не встретился ли разделитель. Следовательно, для каждой записи в индексе необходимо хранить такие данные, как смещение относительно начала файла и размер хранимых данных.

Хранение смещения в виде количества байт от начала файла является неэффективным по следующим соображениям. В том случае, если в качестве контейнера для этого значения используется 32-битное беззнаковое целое число, максимально возможное значение может быть только 232, или 4 гигабайта данных. Это достаточно небольшой размер данных, который, при наличии большого количества файлов, будет быстро превышен. Следовательно, необходимо будет использовать 64-битное целое число, что сразу приводит к необходимости хранить 8 байт для каждого смещения относительно начала файла. Нетрудно подсчитать, что для миллиона файлов расходы на хранение информации о смещениях окажутся приблизительно равными 8 мегабайтам, а для ста миллионов – 800 мегабайтам. Такой расход памяти является неэффективным, поэтому необходимо выбрать другой показатель.

Важной задачей, помимо обеспечения простоты адресации и извлечения данных, является повышение скорости добавления новых данных. Как было выявлено ранее, ожидается высокая интенсивность поступающих и обновляющихся данных, следовательно, алгоритму придется справляться с высокими нагрузками.

По мнению автора, в данном случае можно решить обе задачи одним действием: обеспечить высокую скорость записи и сократить накладные расходы на хранение адреса размещенных данных. Для этого необходимо записывать данные на внешнее запоминающее устройство напрямую, минуя этап буферизации данных. Это несколько повышает нагрузку на внешнее запоминающее устройство и может способствовать его более быстрому изнашиванию, однако, существенно повышает быстродействие. Для обеспечения такого поведения необходимо, на этапе реализации алгоритма предусмотреть разбиение информации на блоки, соответствующие минимально допустимому для записи размеру блока в файловой системе используемой операционной системы. Таким образом, операции записи будут атомарны.

В частности, в файловой системе NTFS, размер блока составляет 512 байт. Это означает, что данные должны записываться (и считываться) на внешнее запоминающее устройство блоками по 512 байт или порциями, размер которых кратен 512 (в таком случае разбиение на блоки будет осуществлять сама файловая система). Для того, чтобы избежать проблем с концевыми данными, размер которых не кратен 512, необходимо предусмотреть запись выравнивания, которое позволит сделать размер оставшихся данных кратным 512.

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

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

Это позволяет использовать для хранения смещения 32-битное целое беззнаковое число и, следовательно, потребуется 4 байта для хранения смещения по каждому из сохраненных файлов. Для файловой системы NTFS такой подход позволяет адресовать большие бинарные объекты размером 232*512 байт, что составляет 2 терабайта. В том случае, если размер сохраняемых данных достаточно велик и превосходит этот показатель, можно использовать несколько больших бинарных объектов, но в таком случае потребуется хранить, помимо смещения и размера хранимых данных, еще и идентификатор бинарного объекта, в котором содержатся требуемые данные.

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

Индекс по размещаемым данным должен, соответственно, основываться на следующих показателях:

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

2)    смещение относительно начала бинарного объекта – 4 байта;

3)    размер хранимых данных – 4 байта;

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

Для быстроты поиска индекс должен быть организован в виде структуры, позволяющей осуществлять быстрый и эффективный поиск. В качестве такой структуры предлагается к использованию красно-черное дерево поиска.

Следует, однако, отметить, что индекс должен обладать способностью самовосстановления. Это означает, что в случае аппаратных или программных сбоев, индекс должен быть восстановлен в кратчайшие сроки и без ошибок. Для решения этой задачи автор считает необходимым хранить в бинарном объекте помимо самих данных дополнительную мета-информацию. Также эта мета-информация должна использоваться для облегчения управления содержимым бинарного объекта.

На основе этой мета-информации индекс может быть восстановлен, однако, очевидно, что при работе алгоритма по восстановлению индекса, большой бинарный объект будет недоступен для чтения и записи. Это явление можно назвать временем простоя или «холодным запуском» системы, отвечающей за хранение бинарного объекта. Таким образом, каждая запись в большом бинарном объекте должна состоять из мета-информации, фактических данных и выравнивания и имеет структуру, представленную на рисунке.

Рисунок 1 – Структура записи в большом бинарном объекте

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

Для управления данными в большом бинарном объекте используется признак или флаг, его значение может устанавливаться в диапазоне от 0 до 2, что обозначает, соответственно, «активно», «удалено», «в ожидании». Для удаления данных из объекта достаточно пометить запись флагом «удалено» и удалить данные из индекса, при этом при следующем перестроении индекса удаленные записи будут просто пропускаться. Значение «в ожидании» используется при добавлении данных. Если новые данные занимают более, чем 512 байт вместе с мета-информацией, есть вероятность, что при программных или аппаратных сбоях они будут добавлены не полностью, поскольку операция полного добавления этих данных в объект не будет являться атомарной. Во избежание потенциальных проблем, связанных с повреждением данных, при добавлении новых данных, они сначала добавляются с флагом «в ожидании», а по завершении добавления флаг меняется на «активно». При перестроении индекса записи с флагом «в ожидании» также исключаются, поскольку это означает, что они были повреждены, и процесс записи не был завершен окончательно.

Для контроля целостности данных используется контрольная сумма, которая также хранится в мета-информации каждой записи. Она высчитывается на основе данных, помещаемых в бинарный объект, а при получении данных она рассчитывается еще раз и сравнивается со значением, хранящимся в мета-информации. Это позволяет избежать ошибок, связанных с повреждением данных при транспортировке по сети и подобных им, а также сознательного искажения хранимых данных, например, в случае злого умысла.



Все статьи автора «Toledo»


© Если вы обнаружили нарушение авторских или смежных прав, пожалуйста, незамедлительно сообщите нам об этом по электронной почте или через форму обратной связи.

Связь с автором (комментарии/рецензии к статье)

Оставить комментарий

Вы должны авторизоваться, чтобы оставить комментарий.

Если Вы еще не зарегистрированы на сайте, то Вам необходимо зарегистрироваться: