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

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

Постановка задачи

Рассмотрим некоторую систему резервного копирования, которая создает копии данных в последовательные запланированные моменты времени {tk, где k = 0; 1; 2 … T}. Систему данных для резервного копирования на момент времени tj ∈ tk обозначим как Dj. Будем отныне всегда предполагать, что начальное состояние данных D0 – пустое, а D1 нет, то есть D0=Ø, D1≠Ø. Каждая сделанная копия данных сохраняется в некотором хранилище данных – репозитории. Каждую такую копию будем называть элементом репозитория. Элемент репозитория, который содержит изменения между состояниями данных с момента tl до момента tl+n, то есть от Dl до Dl+n, обозначим как Rln , где l и n – целые, причем n > 0, l ≥ 0. Учитывая, что начальное состояние данных пустое, R0n фактически означает полную резерв- ную копию состояния данных в момент tn, то есть копию Dn.

Имеет смысл операция объединения элементов репозитория. Например, объединяя полную резервную копию системы данных на момент t_l , то есть R ₀ ^l , с элементом репозитория, содержащим изменения между состояниями данных c момента времени t_l до момента t_l+n , то есть c R _l ⁿ , мы получаем полную резервную копию системы данных на момент t_l+n , то есть R ₀ ^l+n . Следует заметить, что не все элементы могут быть объединены друг с другом, нет смысла, например, объединять элементы, содержащие изменения данных в непоследовательные периоды времени. Для объединения несочетаемых элементов репозитория введем элемент X , который будет обозначать некий «испорченный» элемент.

Множество всех элементов репозитория обозначим Rep. Rep включает в себя все возможные элементы репозитория и введенный «испорченный» элемент X :

Rep = {X ; R i ^} i= 0,1,2...; j = 1,2,3... =

• = {X ; R0 ; R0 ; R0 ;•••; R1 ; R1 ; R1 ;•••; Rk ; Rk ; Rk ;•••} -

• Операцию объединения элементов репозитория ⊕ на множестве всех элементов репозитория Rep введем следующим образом:

• 1-    X Ф X = X; Rln Ф X = X Ф Rn = X;

n +n

Ri j, если i < j и j = i + ni; X, в противном случае.

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

При моделировании алгоритмов резервного копирования требуется построить схему создаваемых элементов репозитория в общем виде. Для получения количественных характеристик

2- R^- e R j j =«

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

Моделирование алгоритмов резервного копирования

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

Полное резервное копирование

Процесс резервирования включает копирование всех файлов и папок, выбранных для резервного копирования вне зависимости от того, изменились они или нет, в каждый момент резервирования t j g t k , , как показано на рис. 1.

Определение. Алгоритм резервного копирования, в процессе работы которого последовательно в моменты времени ^{t k , где ^k = 0; 1; 2 „. T } создается набор элементов репозитория вида R = { R 0 ; R 0 ; R 3 ;...; R T }, называется алгоритмом полного резервного копирования.

Рис. 2. Инкрементное резервное копирование

Дифференциальное резервное копирование

При дифференциальном резервировании изна-чально,в момент времени t₁ создается полная резервная копия данных R 0 , а затем, в последующие мо-менты,создаются копии,содержащие каждый файл, который был изменен с момента последнего полного резервирования (рис.3).

Рис. 3. Дифференциальное резервное копирование

Рис. 1. Полное резервное копирование

Инкрементное резервное копирование

Изначально, в момент времени t₁ создается полная резервная копия данных R 1 , а затем, в последующие моменты, создаются копии фай-лов,измененных с момента последнего резервирования. Рис. 2 иллюстрирует данную схему.

Определение. Алгоритм резервного копирования, в процессе работы которого последовательно в моменты времени { t k , где к = 0; 1; 2 ... T } создается набор элементов репозитория вида R = {R 1 ; R 1 ; R 2 ;...; R T - 1 } , называется инкрементным.

Определение. Алгоритм резервного копирования, в процессе работы которого последовательно в моменты времени {t k , где к = 0; 1; 2 ... T } создается набор элементов репозитория вида R = { R 0 ; R 1 ; R ;...; R T ^{- 1} } , называется дифференциальным.

Мультиуровневое резервное копирование

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

Определение. Алгоритм резервного копирова-ния,в процессе работы которого последовательно в моментывремени { t k , где к = 0; 1; 2 ... T } создается набор элементов репозитория вида (1),называется мультиуровневой схемой для количества уровней L равного l + 1,и где для каждого i -го уровня создается n_i элементов репозитория:

■■Т 1Т1Т1ТЖ1Т1Т1Т1Т1Т1ТЖ)

Рис. 4. Мультиуровневое резервное копирование

R = { R 0 A '< 0 ^{+ 1}

;{{ R

A 2 ' i i

A l '< 0 ^{+ 1}

}

i , ^ o ;{{ R

A 3 ' i 2

A i .<0 + A 2 '< 1 + 1

}

<2. ;{...;{{R

A k + 1 '4

A i ' <0 + ••• +A k '< k- 1 + 1

к . ;{-

•{{ R A ll — ^{1 - i} l — ² .             }       -{{ R A ll ^-i l —1 ⁺¹ .

’ll A 1l - i ₀ + ... + A ll _- 2 - i l - 3 + 1 i - -2 * 0’1 1 A 1l - i ₀ + ... + A ll-1 - i l - 2

+ 1 ^} i i -1 * ⁰ ’ ^{RA\ - i ₀ + ... + A ll - i _l -1 + i _l + 1 ^} i l = ^0,1,.

...., n -J i l -1 = 0,1,

...., n -1 — 1 ^} i i — 2 = 0,1,

■..., n i -2 ^- 1

"""^} i k + 1 = 0,1,..., n k + 1 “1 ^} i k = 0,1

n _k

-1 """ ^} i ₃ = 0,1,...,

n ₃

-1 ^} i 2 = 0,1,..., П 2

-1 ) z 1 = 0,1,...,

n ₁

-1 ^} i o = 0,1,..., n o

-1

,где

{ R k }

условное выражение истинно

= { R k }; { R k }

условное выражение ложно

= 0.

A i = (n i + 1) • ni — i • ni — 2 - • ni + 2 • nt + i • ni, A i = n i + 1, ^{R k } _г-= 1,2,..., n = ^{R k ; R k ;

R k } -

На рис.4 представлена иллюстрация работы алгоритма мультиуровневой схемы для следующих параметров: L = 3, n o = 2, n i = 2, ⁿ 2 = 2, T = 12. Сплошными линиями на рисунке обозначены операции резервного копирования нулевого уровня,пунк-тиром – первого,пунктиром с точками – второго.

Схема Костелло, Юманса, Ву

Резервное копирование при работе данного алгоритма ведется параллельно, в несколько уровней. В результате создается совокупность L наборов элементов репозитория. На нулевом уровне создание резервных копий идентично ин- крементной схеме. Все прочие уровни избыточны

– создаются для увеличения скорости восстановления (см. [3]).

Определение. Алгоритм резервного копиро- вания, в процессе работы которого последова-

{ t k , где k = 0; 1; 2 _ T }

тельно в моменты времени

создается набор элементов репозитория вида (2), является схемой Костелло, Юманса, Ву (далее в обозначениях – WcU), где b – параметр схемы – «база» (base).

На рис. 5 представлена иллюстрация схемы для следующих параметров: L = 3, b = 2, T = 12.

R = { R 0 ;{ R 1 }i _{= 1} , ₂„

bi-1

., T - < ^;{^^Ry- 1 b .b_{H + (}i- I ₎.bl- 1 + 1 ^}

J=1                          i=1,2,

T _y^H b.b j- 1 ^}l= 2,3,..., L^} . floor ( —bj^—)

^^^^^ S nl W nl |У r>l IT nl IT rj IT nl IT nl IT 7>1 IT nl IT r>l IT nl IT nl 1

Рис. 5. Резервное копирование схемы Костелло, Юманса, Ву

Частичное создание на рис. 5 обозначено элементами репозитория в скобках.

Алгоритм резервного копирования «Z scheme»

«Z scheme» осуществляет параллельные операции резервного копирования также в несколько потоков, в результате создается совокупность L наборов элементов репозитория. На нулевом уровне создание резервных копий идентично инкрементной схеме. Все прочие уровни избыточны – создаются для увеличения скорости восстановления (см.[4]).

Определение. Алгоритм резервного копиро-вания,в процессе работы которого последовательно в моменты времени { t k , где к = 0; 1; 2 . . T } создается набор элементов репозитория вида

R = ^{R 0 ;{^R 1 }i= i,2,..., T-i^;{{R 1 ^}_;= 1,2..... т-ь^1-' ^} i = 2,3,...,l ^} ’называ ^- ется алгоритмом резервного копирования « Z scheme ».

На рис.6 представлена частичная иллюстрация алгоритма резервного копирования « Z scheme» для следующих параметров: L = 4, b = 2, T = 12.Пунк-тирные линии означают исключение из создаваемого элемента репозитория изменений,относящихся к указываемому пунктиром периоду.

Получение количественных        Р характеристик моделируемых алгоритмов

Для того чтобы получить количественные характеристики объема репозитория, требуемого для хранения создаваемых элементов репозитория, необходимо каждому элементу репозитория

^" T IT _, IT _, IT _, IT _, IT _, IT _, IT _, IT _, IT _, W_, IT _, 1

Рис. 6. Резервное копирование схемы «Z scheme»

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

Итак, предположим, что объем данных D₁ равен V 1 e R + . Предположим также, что между двумя любыми последовательными моментами времени, когда создаются резервные копии, данные увеличиваются на некоторую постоянную величину так, что объем D_l , l > 0 равен V₁ + p · V₁ ·( l – 1), где p будем называть коэффициентом увеличения данных.

Предположим теперь, что между двумя любыми последовательными моментами времени, когда создаются резервные копии, данные изменяются на некоторую величину так, что объем изменений между Dl и Dl+1 равен d(Уi (1 + pQ -1)). Названный объем изменений не включает добавляемую часть. В дальнейшем d будем называть коэффициентом изменения данных. Такие предположения о характере изменения данных соответствуют статистике накопления данных в реальных системах, что можно проследить по данным исследований, например, компании Teradactyl LLC, занимающейся разработкой систем резервного копирования [5], и по данным исследований, проведенных в Технологическом Институте в Джорджии, США[2].

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

Введем функцию vols: Rep ^ R+, которая будет ставить в соответствие каждому элементу репозитория положительное действительное число, обозначающее объем требуемой памяти для хранения этого элемента. Значение функции складывается из объема прибавленных дан- ных 0приб , объема измененных данных ©изм. и объема служебных данных Θслужебн. за промежуток, соответствующий аргументу, то есть vols = 0 приб. + 0 изм. + 0 служебн. •

Рассмотрим некий элемент репозитория Rln, тогда vols(Rl ) = © приб. (Rl ) + 0 изм. (Rl ) + 0 служебн. (Rf )

Объем прибавленных данных Θ приб . иобъем измененных данных Θизм. с учетом наших предположений выражают формулы (3). Случай,когда l = 0, выделяется отдельно из-за предположения, что начальное состояние данных пустое, а последующее за ним нет, поэтому в этих случаях элемент объем измененных данных также пуст, а объем прибавленных данных включает начальный объем V1.

Объем служебных данных Θ _{служебн .} зависит прежде всего от конкретной реализации системы резервногокопированияитребуетмоделирования в каждом отдельном случае. Однако невозможно пренебречь учетом данной составляющей, ибо в отдельных случаях доля служебных данных может составлять десятки процентов в совокупном объеме репозитория.

В результате получим функцию vols, определяемую (4).

1. © приб . (R l ) =

( V 1 + V 1 "  P " ( n - 1)), если l = 0;

V 1 • (1 + p • (l + n - 1)) - V 1 • (1 + p • (l - 1)) = V 1 • p • n, если l * 0.

2. ® приб\ X) = 0 ;

0, если l = 0;

1. 0 изм. ( R l ) =^

n

£ ( V i + V 1 • p • ( t - 1))( d • (1 - d )'),

если l ^ 0. ^;

( n' = 1

• 2 . 0 изм . ( X) = 0 ;

^{( V} 1 ⁺ V 1 • P • ^{( n -} 1)) ⁺ © служебн . , если l = 0;

1. vols ( R n ) = <

V 1

n

• p • n + V i • ⁽¹ + p • ⁽ t ^- 1)) ^ ^{( d} ' ^{(1 -} d ) n 1 ) + © служебн .

n' = 1

если l ^ 0. ;

• 2 . vols ( X ) = 0 .

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

Сопоставление модельных данныхс экспериментальными

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

Изначально аналитически полученные результаты были сопоставлены с данными экспериментов, проведенных в Университете Мериленда в Балтиморе, США[2], где испытывался прототип реальной системы резервного копирования в ре- альных условиях, результаты которых представлены на рис. 8. В модели были заданы идентичное начальное состояние данных, коэффициенты роста и изменения объема данных. Анализ показал, что получаемые данные адекватны данным рассмотренного эксперимента.

600 Gb

Full

500 Gb            Legato Level

Z Scheme

Incremental

Рис. 7. Изменение объема репозитория

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

В разработанной системе резервного копирования предусмотрено хранение следующей служебной информации: файлового индекса системы резервируемых данных на каждый момент создания резервных копий; список элементарных операций, производимых в каждый момент резервного копирования; другие данные, объем которых не превосходит 0,01% от общего объема служебных данных. Объем файлового индекса линейно зависит от объема файловой структуры системы резервируемых данных. Список элементарных операций линейно зависит от объема копируемых изменений.

Используя известные предположения о характере роста и изменения данных, а также выяснив объем записей в создаваемых индексах и списках, была построена модель объема служебных данных с максимальным отклонением менее 3,47% и средним отклонением 1,18% по всем проведенным испытаниям.

В целом, анализ получаемых результатов сопоставления показал довольно высокую точность аналитических данных.В частности, рассмотрим результаты экспериментов со следующими параметрами: начальное состояние данных V₁ = 1610612736 (1,5 Гб), коэффициенты роста p = 0,5% и изменения объема данных d = 0,2%. Данные были собраны за 365 периодов резервного копирования (эмуляция одного года с ежедневным резервным копированием). На рис. 8-9 отображены данные, полученные аналитически. На рис. 9 отдельно отображены алгоритмы мультиуровневой схемы, схемы Костелло, Юманса, Ву, «Z scheme», инкрементного копирования в более детализированном виде.

Рис. 8. Изменение объема репозитория

Рис. 9. Изменение объема репозитория

Точность аппроксимации в модели реальных данных для резервного копирования составляла в среднем 0,01% на каждом шаге. Наиболее чувствительны к точности аппроксимации схемы, где много элементов репозитория ( R _l ⁿ ) , объединяющих изменения за несколько периодов, то есть с большими значениями параметра n и ненулевым l , ибо в этом случае имеет место накопление ошибки. Так, например, при работе дифференциальной схемы параметр n постоянно увеличивается, этим и объясняется наименьшая точность среди других рассмотренных алгоритмов.

В среднем отклонение модельных от экспериментальных данных по всем экспериментам составило 0,85%. Средние и максимальные отклонения для различных схем резервного копирования показаны в таблице 1.

Таблица 1. Отклонение модельных данных от экспериментальных

Тип резервного копирования	Среднее отклонение, %	Максимальное отклонение, %
Полное	0,47	0,78
Дифференциальное	1,26	1,47
Инкрементное	0,63	0,94
Мультиуровне-вое	1,00	1,27
WCU(lev. 0-4; b = 2)	0,89	1,16
Z-Scheme (lev. 0-4; b = 2)	0,83	0,98

Иллюстрация изменения отклонения в динамике представлена на рис. 10.

Выводы

Полученные результаты показали достаточную точность аналитических данных для приме- нения описанного метода для построения оценок требуемого объема репозитория.

Рис. 10. Отклонение модельных данных от экспериментальных

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

Рассмотренный метод пригоден также для построения систем прогнозирования в современных системах резервного копирования.