Исследование и разработка методов и алгоритмов резервного копирования данных, на жестких дисках

Исследование и разработка методов и алгоритмов резервного копирования данных, на жестких дисках ОГЛАВЛЕНИЕ ВВЕДЕНИЕ 3 Глава 1. ОБЗОР СОВРЕМЕННОГО СОСТОЯНИЯ ПРОБЛЕМ СУЩЕСТВУЮЩИХ МЕТОДОВ И АЛГОРИТМОВ РЕЗЕРВНОГО КОПИРОВАНИЯ ДАННЫХ НА ЖЕСТКИХ ДИСКАХ. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЙ 1.1 Принципы организации данных на жестких дисках. Запись, копирование, удаление данных с жесткого диска 1.2 Обзор существующих методов и алгоритмов резервного копирования данных на жестких дисках. Исследование предметной области 1.3 Постановка задачи 26 ВВЕДЕНИЕ Актуальность темы. Информации, хранящейся в компьютерных системах, угрожает множество опасностей.

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

Как показывает общемировая статистика, основными причинами потерь данных являются неисправная работа аппаратных средств (44%) и человеческие ошибки (32%), в основном тех, кто имеет максимальный уровень доступа к системам хранения данных компании. 14% всех случаев потерь данных происходят вследствие ошибок программного обеспечения, другие 7% происходят из-за компьютерных вирусов, а вследствие стихийных бедствий – только 3%. Сбои приводят к приостановлению бизнес-процессов и потере данных, тем самым ставят под вопрос существование бизнеса в целом.

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

Выявить оптимальное решение очень непросто, особенно учитывая широкое многообразие существующих путей реализации систем хранения и резервного копирования, а также довольно высокую динамику изменения цен и появления новых технологий на IT рынке. У клиентов разные приоритеты, однако, существует общая для всех проблема – стремительный рост объемов хранимых данных, составляющий 50-100% в год. Так по результатам исследования компании IDC – совокупный объем информации, хранящейся в электронном виде, в 2006 году составил 161 эксабайт (1 эксабайт равен 1018 байт). Аналитики предполагают, что за период с 2006 по 2010 годы общий объем информации увеличится, по крайней мере, в шесть раз. Соответственно, все серьезнее становится проблема надежного хранения данных и скорости доступа к ним. При таких темпах роста традиционные системы становятся неэффективными, необходима оптимизация процессов хранения, создания резервных копий, внедрение решений класса ILM (Information Lifecycle Management - управление жизненным циклом информации) . Резервное копирование в глазах большинства специалистов все еще не является достаточно надежным. 45% респондентов заявили, что в примерно 10% случаях испытывали неудовлетворительный результат при использовании всякого рода систем резервного копирования, причем по сравнению с данными опроса 2007 года этот показатель удвоился. Отчасти это объясняется неверным выбором инструментов.

По данным компании IDC, причиной 40% случаев полной утраты данных американскими компаниями является пренебрежительное отношение к технологиям хранения. При этом только 10% из этих компаний смогли вернуться к бизнесу и лишь 4% из них выжили в течение последующих трех лет. Действительно, построение высокоэффективной системы хранения данных, отвечающих реальным требованиям организации, а также выбор наиболее подходящей системы резервного копирования – процесс весьма сложный и трудоемкий.

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

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

Для этого требуется комплексное исследование количественных характеристик избыточности известных алгоритмов резервирования: полного, дифференциального, мультиуровневого, алгоритма А. М. Костелло, К. Юманса, Ф. Ву, алгоритма Z Scheme. Целью данной работы является исследование и разработка методов и алгоритмов резервного копирования данных на жестких дисках.

В дипломной работе поставлены и решены следующие задачи: 1. Дать обзор современного состояния проблем существующих методов и алгоритмов резервного копирования данных на жестких дисках; 2. Исследовать свойства и параметры алгоритма типа disk snap-shot backup и files/folders backup; 3. Разработать функциональную схему алгоритма резервного копирования данных на жестких дисках; 4. Разработать структурную схему алгоритма резервного копирования данных на жестких дисках; 5. Провести экспериментальную проверку разработанного алгоритма резервного копирования данных на дисках; 6. Сопоставить полученные при экспериментах результаты с результатами ранее разработанных методов. Объект исследования — системы резервного копирования данных.

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

Глава 1.

ОБЗОР СОВРЕМЕННОГО СОСТОЯНИЯ ПРОБЛЕМ СУЩЕСТВУЮЩИХ МЕТОДОВ И АЛГОРИТМОВ РЕЗЕРВНОГО КОПИРОВАНИЯ ДАННЫХ НА ЖЕСТКИХ ДИСКАХ. ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЙ

ОБЗОР СОВРЕМЕННОГО СОСТОЯНИЯ ПРОБЛЕМ СУЩЕСТВУЮЩИХ МЕТОДОВ И АЛГОРИТМОВ... ПОСТАНОВКА ЗАДАЧИ ИССЛЕДОВАНИЙ. Принципы организации данных на жестких дисках. Запись, копирование, уд... Количество секторов может быть разным в зависимости от плотности дорож... Секторы, создаваемые с помощью стандартных программ форматирования, им...

заключение (или суффикс — suffix portion), в котором находится контрольная сумма (checksum), необходимая для проверки целостности данных. В большинстве новых дисководов вместо заголовка используется так называемая запись No-ID, вмещающая в себя больший объем данных.

Помимо указанных областей служебной информации, каждый сектор содержит область данных емкостью 512 байт. При низкоуровневом (физическом) форматировании всем байтам данных присваивается некоторое значение, например F6h. Утверждать, что размер любого сектора равен 512 байт, не вполне корректно. На самом деле в каждом секторе можно записать 512 байт данных, но область данных — это только часть сектора.

Каждый сектор на диске обычно занимает 571 байт, из которых под данные отводится только 512 байт. В различных накопителях пространство, отводимое под заголовки (header) и заключения (trailer), может быть разным, но, как правило, сектор имеет размер 571 байт. Чтобы очистить секторы, в них зачастую записываются специальные последовательности байтов. Заметим, что, кроме промежутков внутри секторов, существуют промежутки между секторами на каждой дорожке и между самими дорожками.

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

В этом случае его можно начать считывать сразу, не дожидаясь, пока диск совершит дополнительный оборот. В некоторых накопителях, работающих с чередованием (interleave) 1:1, упомянутой задержки недостаточно. Дополнительное время можно обеспечить за счет смещения секторов таким образом, чтобы первый сектор дорожки под головкой появлялся с задержкой. Идентификатор (ID) сектора состоит из полей записи номеров цилиндра, головки и сектора, а также контрольного поля CRC для проверки точности считывания информации ID. В большинстве контроллеров седьмой бит поля номера головки используется для маркировки дефектных секторов в процессе низкоуровневого форматирования или анализа поверхности. Однако такой метод не является стандартным, и в некоторых устройствах дефектные секторы помечаются иначе.

Но, как правило, отметка делается в одном из полей ID. Интервал включения записи следует сразу за байтами CRC; он гарантирует, что информация в следующей области данных будет записана правильно.

Кроме того, он служит для завершения анализа CRC (контрольной суммы) идентификатора сектора. В поле данных можно записать 512 байт информации. За ним располагается еще одно поле CRC для проверки правильности записи данных. В большинстве накопителей размер этого поля составляет два байта, но некоторые контроллеры могут работать и с более длинными полями кодов коррекции ошибок (Error Correction Code — ECC). Записанные в этом поле байты кодов коррекции ошибок позволяют при считывании обнаруживать и исправлять некоторые ошибки.

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

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

Размер этого интервала зависит от возможных значений частоты вращения диска и сигнала синхронизации при форматировании и записи. Информация, записываемая в заголовке сектора, имеет огромное значение, поскольку содержит данные о номере цилиндра, головки и сектора. Все эти сведения (за исключением поля данных, байтов CRC и интервала отключения записи) записываются на диск только при форматировании низкого уровня. Различают два вида форматирования диска: - физическое, или форматирование низкого уровня; - логическое, или форматирование высокого уровня.

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

При организации нескольких разделов на одном накопителе каждый из них может использоваться для работы под управлением своей операционной системы либо представлять отдельный том (volume), или логический диск (logical drive). Тому, или логическому диску, система присваивает буквенное обозначение.

Таким образом, форматирование жесткого диска выполняется в три этапа. 1. Форматирование низкого уровня. 2. Организация разделов на диске. 3. Форматирование высокого уровня. В процессе форматирования низкого уровня дорожки диска разбиваются на секторы. При этом записываются заголовки и заключения секторов (префиксы и суффиксы), а также формируются интервалы между секторами и дорожками.

Область данных каждого сектора заполняется фиктивными значениями или специальными тестовыми наборами данных. В накопителях на гибких дисках количество секторов на дорожке определяется типом дискеты и дисковода; количество секторов на дорожке жесткого диска зависит от интерфейса накопителя и контроллера. Практически во всех накопителях IDE и SCSI используется так называемая зонная запись с переменным количеством секторов на дорожке. Дорожки, более удаленные от центра, а значит, и более длинные содержат большее число секторов, чем близкие к центру.

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

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

Еще одно свойство зонной записи состоит в том, что скорость обмена данными с накопителем может изменяться и зависит от зоны, в которой в конкретный момент располагаются головки. Происходит это потому, что секторов во внешних зонах больше, а угловая скорость вращения диска постоянна (т. е. линейная скорость перемещения секторов относительно головки при считывании и записи данных на внешних дорожках оказывается выше, чем на внутренних). Метод зонной записи был принят производителями жестких дисков, что позволило повысить емкость устройств на 20-50% по сравнению с накопителями, в которых число секторов на дорожке является фиксированным.

Сегодня зонная запись используется почти во всех накопителях IDE и SCSI. При форматировании высокого уровня операционная система создает структуры для работы с файлами и данными. В каждый раздел (логический диск) заносится загрузочный сектор тома (Volume Boot Sector — VBS), две копии таблицы размещения файлов (FAT) и корневой каталог (Root Directory). С помощью этих структур данных операционная система распределяет дисковое пространство, отслеживает расположение файлов и даже "обходит", во избежание проблем, дефектные участки на диске.

В сущности, форматирование высокого уровня — это не столько форматирование, сколько создание оглавления диска и таблицы размещения файлов. "Настоящее" форматирование — это форматирование низкого уровня, при котором диск разбивается на дорожки и секторы.

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

По прогнозам ожидается, что в ближайшее время будет наблюдаться постепенный переход от использования магнитных лент в качестве основного носителя к использованию жестких дисков. По прогнозу IDC общемировой рынок дисковых систем хранения будет продолжать бурный рост, общий объем продаваемых накопителей данных будет увеличиваться на 50% ежегодно. На сегодняшний день капитальные вложения для внедрения систем резервного копирования с использованием жестких дисков выше, чем с применением магнитных лент. В то же время, эксплуатационные расходы сравнимы, а во многих случаях ниже, при использовании решений на базе жестких дисков. Считается, что срок службы массивов активных жестких дисков равен 5-7 годам . 1.2 Обзор существующих методов и алгоритмов резервного копирования данных на жестких дисках.

Исследование предметной области Защита ценной информации хранящейся на персональных компьютерах – это приоритет номер один как для организаций, так и для простых пользователей.

Для того чтобы избежать потери важной информации, необходимо проводить регулярное резервное копирование или бэкап (от англ. backup – защита, поддержка) данных. Рассмотрим определение понятия резервного копирования по версии SNIA (Storage Networking Industry Association) . Резервная копия (англ. backup copy) – данные, хранимые на энергонезависимых носителях, обычно удаленно, предназначенные для восстановления, в случае если оригинал копии данных утерян или недоступен. Резервное копирование – это периодическое дублирование или создание запасных копий критически важных данных с целью их восстановления в случае потери оригинала.

Можно сказать, что резервное копирование – это страхование от потери информации в случае поломки оборудования или случайного удаления файлов пользователем. Все системы резервного копирования данных можно разделить на три типа согласно используемому методу копирования: это может быть пофайловое копирование, блочное или копирование данных на уровне приложений.

Система блочного резервного копирования (англ. image-level или block-level backup) работает напрямую с носителем, игнорируя файловую структуру, и сохраняя все содержимое полностью – операционную систему, рабочие данные, настройки и прочее. Преимуществом выполнения данного вида резервного копирования является высокая скорость. Однако обычно при выполнении операций копирования требуется приостановить работу приложений, чтобы копия была целостной (англ. consistent). Некоторые системы (англ. sparse image backup) обнаруживают неиспользуемые блоки и исключают их копирование.

При использовании блочного резервного копирования, довольно затруднительным является восстановление частных файлов. При выполнении операций резервного копирования на файловом уровне (англ. file-level или file-based backup) используется файловая система. В этом случае относительно простой задачей является восстановление некоторых конкретных файлов. В целом же операции резервного копирования длятся дольше, возникает дополнительная загрузка операционной системы, а также появляется проблема доступа к открытым файлам.

Резервное копирование может производиться на уровне приложений (англ. application-level backup). Операции копирования и восстановления производятся посредством использования специально предусмотренного в резервируемом приложении программного интерфейса API (англ. Application Programming Interface). Резервная копия представляет собой набор файлов и возможно других объектов, определяемых самим приложением, которые вместе являются отображением состояния приложения на некоторый момент времени.

При данном способе резервного копирования может иметь место проблема совместимости между разными версиями приложений и систем резервного копирования, реализующих соответствующий интерфейс. Современные системы резервного копирования реализуются как программно (англ. software-based), так и аппаратно (англ. hardware-based), а также в сочетании программных и аппаратных компонентов. Использование чисто программных средств относительно более дешево и универсально.

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

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

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

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

Итак, рассмотрим некоторую систему резервного копирования, которая создает копии данных в последовательные запланированные моменты времени {tk, где k=0,1,2,…,T}. Систему данных для резервного копирования на момент времени tjtk обозначим как Dj. При описании алгоритмов будем предполагать, что начальное состояние данных D0 – пустое, а D1 нет. Каждая сделанная копия данных сохраняется в некотором хранилище данных - репозитории.

Каждую такую копию будем называть элементом репозитория. Элемент репозитория, который содержит изменения между состояниями данных с момента tl до момента tl+n, то есть от Dl до Dl+n обозначим как n l R , где l и n – целые, причем n>0, l≥0. Учитывая, что начальное состояние данных пустое, n R0 фактически означает полную резервную копию состояния данных в момент tn, то есть копию Dn. Рассмотрим различные алгоритмические подходы в системах резервного копирования, как традиционные, так и нетривиальные; используя введенную терминологию, дадим определения и запишем общий вид, который может быть использован для дальнейшего количественного анализа. 1. Полное резервное копирование Полное резервное копирование (англ. full backup) является традиционным подходом в резервном копировании.

Процесс резервирования включает копирование всех данных, выбранных для резервного копирования, вне зависимости изменились они или же нет, в каждый момент резервирования tj ϵ tk, как показано на рисунке 1. Рис. 1. Алгоритм полного резервного копирования Определение.

Алгоритм резервного копирования, в процессе работы которого последовательно в моменты времени {tk, где k=0,1,2,…,T} создается набор элементов репозитория вида R={R01; R02; R03; … R0T}, называется алгоритмом полного резервного копирования. Такой метод является простейшим алгоритмическим подходом. Следует заметить следующие недостатки: копирование всех файлов является медленным, а хранение полных резервных копий на каждый момент времени требует много места. 2. Инкрементное резервное копирование Инкрементное резервное копирование (англ. incremental backup) также является традиционным алгоритмическим подходом.

Изначально, в момент времени t1 создается полная резервная копия данных, а затем, в последующие моменты, создаются копии R01 файлов, измененных с момента последнего резервирования, то есть R11, R12 и так далее. Рисунок 2 иллюстрирует данную схему. Рис.2. Алгоритм инкрементного резервного копирования Определение.

Алгоритм резервного копирования, в процессе работы которого последовательно в моменты времени {tk, где k=0,1,2,…,T} создается набор элементов репозитория вида R={R01; R11; R11; … RТ-11}, называется инкрементным. Инкрементное резервирование занимает меньше времени, так как данных копируется меньше. Однако процесс восстановления данных занимает значительное количество времени, так как требуется доступ к большим объемам данных, ибо должны быть восстановлены данные из полной резервной копии, плюс данные всех последующих инкрементных резервирований. Возможен еще один вариант работы, когда каждая создаваемая инкрементная копия тут же применяется к существующей полной резервной копии, в этом случае называемой зеркало (англ. мirror), и затем создается обратная инкрементная копия (англ. reverse incremental). В результате работы такой схемы в наличии всегда существует полная резервная копия и набор обратных инкрементных, содержащих данные об изменениях для возможного восстановления на предыдущие моменты времени. 3. Дифференциальное резервное копирование При дифференциальном резервном копировании (англ. differential backup) изначально, в момент времени t1 создается полная резервная копия данных R01, а затем, в последующие моменты, создаются копии, содержащие данные, измененные с момента последнего полного резервирования, то есть R11, R12 и так далее.

Данная схема проиллюстрирована на рисунке 3. Рис.3. Алгоритм дифференциального резервного копирования Определение.

Алгоритм резервного копирования, в процессе работы которого последовательно в моменты времени {tk, где k=0,1,2,…,T} создается набор элементов репозитория вида R={R01; R11; R12; … R1Т-1}, называется дифференциальным.

Дифференциальное резервирование ускоряет процесс восстановления – для восстановления необходимо восстановить данные из полной резервной копии и последней дифференциальной. 4. Мультиуровневое резервное копирование Между крайностями традиционных алгоритмов полного и инкрементного копирования есть другие алгоритмы позволяющие найти нужный баланс между основными характеристиками процессов резервного копирования.

Мультиуровневая схема (англ. multi-level backup) работает таким образом: резервное копирование ведется в несколько уровней: на 0-ом уровне создаются полные резервные копии; на последующих – копируются файлы, модифицированные с момента предыдущего резервного копирования более низкого уровня.

Рис.4. Алгоритм мультиуровневого резервного копирования На рисунке 4 представлена иллюстрация работы алгоритма мультиуровневой схемы для трех уровней и 12-ти периодов резервного копирования. Сплошными линиями на рисунке обозначены операции резервного копирования нулевого уровня, пунктиром – первого, пунктиром с точками – второго. Опустим запись работы в общем виде для этой и последующих схем, потому что они довольно сложны и каждая требует дополнительных пояснений.

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

Так на некоторые дни выпадает необходимость сохранять в десятки раз больше данных, чем в другие, то есть пользователь должен содержать оборудование, которое должно справляться с потребностями нулевого уровня, и которое будет простаивать большую часть времени. 5. Схема А.М. Костелло, К. Юманса, Ф. Ву Рассмотрим схему резервного копирования, разработанную А.М. Костелло, К. Юмансом и Ф. Ву в Университете Калифорнии в Беркли, США. При работе данного алгоритма копирование ведется параллельно, в несколько уровней, в результате создается совокупность наборов элементов репозитория.

На 0-ом уровне создание резервных копий идентично инкрементной схеме. Все прочие уровни избыточны – создаются для увеличения скорости восстановления. Рис.5. Схема Костелло-Юманса-Ву На рисунке 5 представлена иллюстрация схемы Костелло-Юманса-Ву для трех уровней и 12-ти периодов резервного копирования (параметр схемы ―база b=2). Частичное создание на рисунке обозначено элементами репозитория в скобках.

Сплошными линиями на рисунке обозначены операции резервного копирования нулевого уровня, пунктиром – первого, пунктиром с точками – второго. Элементы резервного копирования создаются постепенно в несколько подходов, за несколько моментов резервного копирования, что обеспечивает ровное использование объема репозитория во времени и делает пригодным для online-режима работы. 6. Алгоритм «Z scheme» Алгоритм резервного копирования «Z scheme» разработан в Технологическом Институте в Джорджии, США. «Z scheme» осуществляет параллельные операции резервного копирования также в несколько потоков, в результате создается совокупность наборов элементов репозитория.

На нулевом уровне создание резервных копий идентично инкрементной схеме. Все прочие уровни избыточны и создаются для увеличения скорости восстановления. Файлы копируются некоторым потоком уровня i если только он был изменен bi моментов создания резервных копий (например, дней) назад, где b – внешний параметр схемы, называемый базой (англ. base). Нулевой уровень есть не что иное, как инкрементная схема.

Алгоритм «Z scheme» близок по основным характеристикам к мультиуровневой схеме, но лишен недостатка связанного с неравномерным использованием памяти. В результате работы схем резервного копирования создаются наборы элементов репозитория. Для того чтобы получить количественные характеристики объема репозитория, требуемого для работы того или иного алгоритма, необходимо каждому элементу репозитория поставить в соответствие некоторое действительное число, обозначающее его объем.

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

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

Нужно, однако, заметить, что каждый алгоритм резервного копирования в такого рода модели будет давать несколько меньшие значения, что объясняется отсутствием учета наличия служебной информации необходимой в реальных системах резервного копирования для работы. Чтобы это компенсировать, нужно ввести корректирующие коэффициенты. Данный подход построения оценок был проверен путем сопоставления модельных данных с результатами экспериментов, проведенных в Университете Мериленда в Балтиморе, США , где испытывались системы резервного копирования в реальных условиях.

Для иллюстрации работы схем приведем данные одного из модельных экспериментов на рисунке 6. Рис.6. Схемы резервного копирования Анализ показал, что этот подход имеет достаточную точность не только для сравнительной оценки алгоритмов, но и для вычисления абсолютных величин объемов репозитория. К примеру, отличие модельных данных от экспериментальных для схемы полного резервного копирования составило менее 3%. Описанный метод применим при проектировании новых схем резервного копирования, ибо помогает априорно аналитически оценивать одну из основных характеристик процессов резервирования – объем требуемого места для хранения.

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

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

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

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