Исследование эффективности и отказоустойчивости резервного копирования цифровых данных

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

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

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

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

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

Характеристики эффективности и отказоустойчивости

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

Если возможность порчи созданных резервных копий считать равновероятной, то на некоторый момент времени tj для восстановления существует Nj созданных элементарных копий, а для восстановления требуется Mj недублиро-ванных копий. Тогда при утрате одной копии вероятность того, что восстановление на момент

Nj-Mj tj окажется возможным, составит       7 -100%, средняя восстановимость по моментам t1 … tk бу- дет равна:

RPESekenM= ^ ^

•100%.

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

Суммарный объем резервных копий некоторого алгоритма РК «scheme» на некоторый момент t обозначим как BVolscheme(t), а время восстановления – RTimescheme(t). Средняя эффективность АERscheme показывает, насколько создаваемая алгоритмом «scheme» избыточность снижает время, требуемое для восстановления. Значение данного показателя равно величине (1/(RTimescheme))/ BVol , нормированной на значение эффектив-scheme ности в идеальном случае (1/(RTimemin))/BVolmin. Таким образом, выражение для средней эффективности имеет вид:

к

AERsc1ieme

RTirne_mm (?) RR™⁶. schemed ' BVoi_schemAtV . ^/_mm(O , к

Так как инкрементный алгоритм не резервирует дополнительных избыточных данных, то ему соответствует минимальный показатель BVol_min . Минимальное время восстановления требуется для алгоритма полного копирования. При дифференциальном резервировании [3] для восстановления требуется полная копия и одна копия с изменениями, что также характеризуется низким временем восстановления [5].

Теоретическая основа и методика расчета

Для вычисления показателей эффективности и восстановимости был применен разработанный способ моделирования работы процессов резервного копирования и восстановления [1]. Так, в модели рассматривается система резервного копирования, которая создает копии данных в последовательные моменты времени {4}a-= 1,2, T- Состояние данных для резервного копирования на момент времени t_j обозначается D_j , начальное состояние данных D ₀ предполагается пустым. Элементарные копии, содержащие изменения между состояниями данных с момента t_s до момента t_s+n , обозначаются R" или R ( s , n ), где s и n – целые, причем s ≥ 0, n > 0. Множество всех элементарных копий – Rep.

Так, в процессе инкрементного копирования, в моменты времени {fk}k=l.2..... T создаются резервные копии Р._ПеЛМ = К-д (см. рис. 1), при этом на момент t_T будет иметься набор элементов: R,._roXt_T> U^-^a^K;^¹;-;^-!}.

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

Функция Vol: Rep ^ R⁺ ставит в соответствие каждой элементарной копии положительное действительное число, обозначающее объем требуемой памяти для хранения:

Vol{R{t, m^ = Add It, m) + Difff, m) + Servf, m), где функция AddXt,m) показывает объем всех добавленных данных между некоторыми состояниями данных Dt и Dt+m, Diff It,nf – объем всех измененных данных, Delf,m) – объем удаленных данных, Serv^t, nf – объем служебных данных, хранимых в системе резервного копирования (см. рис. 2).

Vol(DM)

Vol(DJ /		Add(t,m)
		Diff(t,m)
		Del(t,m)

О,            D1+m

Рис. 2. Различие состояний данных

Объем хранилища резервных копий Volume _sc^_eme (tj ) , требуемый для работы некоторого алгоритма РК ( «scheme» ) на некоторый момент времени t_j , будет равен совокупному объему всех созданных элементарных копий:

Volumescheme <у) =   ^ Vol {R\

R^VchemAtp

В зависимости от области применения резервного копирования вводятся выражения, определяющие характер роста, изменения состояния данных. Рассмотрим случай, когда модель характеризуется следующим рядом условий: в каждый последующий момент времени t_k+1 по отношению к предыдущему t_k данные изменяются так, что Diff ( k , 1) = Vol ( Dk )· d , и растут так, что Add ( k , 1) = Vol ( Dk )· p , при этом часть данных удаляется Del ( k , 1) = Vol ( Dk )· m . Объем изменений на каждый момент совпадает с изменениями предыдущего момента с уровнем D . При этом первичное состояние данных равно некоторому начальному объему V , Vol ( D ₁) = V . Параметр объема V измеряется в байтах, а параметры p , d и m – в процентах. Функции, описывающие изменение и рост данных, будут иметь вид

Add(s,n) = V-4'^s-¹ (t" -(1-w)") Diff(s,n) = V •4^/S~¹ -(<7(1 — тУ”^х +(1- d — my A^,

Vol^D^VV-A-^-^

. L          ^"d-y-D^

где A = (1 - m) - (1---------— - m)

(1-d-m)      )

и T = (1 + p — m).

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

Характеристики каждого способа резервного копирования зависят от характера и уровней роста, изменения, повторяемости изменений, объема данных и свойств используемых носите- лей. Поэтому расчет единого показателя эффективности для алгоритмов РК необходимо вести в среднем по различным значениям выделенных влияющих факторов. В частности, зависимость показателя эффективности от параметров уровней роста и изменения данных для инкрементного алгоритма изображена на рис. 3. Иллюстрация разницы величин показателя эффективности в зависимости от фактора уровня повторения изменений (D = 90%, D = 10%) для инкрементного способа резервного копирования представлена на рис. 4.

Рис. 3. Зависимость эффективности от уровней ро- ста и изменения данных

Рис. 4. Влияние совпадения изменений на показа- тель эффективности

Способ избыточного копирования с повышенной эффективностью

На основе описанной методики расчета предложенных показателей был исследован широкий спектр алгоритмов, включающий: полное, инкрементное, дифференциальное резервирование; мультиуровневый способ [5], алгоритм [2], «Z scheme» [5]. В результате проведенного исследования было выявлено, что существует возможность построения нового алгоритма, с регулируемым балансом базовых характеристик процесса РК, с повышенной степенью эффективности вводимой избыточности.

Был разработан алгоритм резервного копирования, обозначаемый Braid ^k (от англ. braiding – плетение) и в общем виде задаваемый функцией выхода следующего вида:

^Braid¹¹ ^ ^ ^ v Init^k ^1 ’ ^ ^’ ^ Braid^k Element ^A+l ’ ^ Т ) j ’

R               t \ — \\Dstart ■             •          >             • lmtk ^ start ^end ) Ц^О )end-start>0 7 x^start )end-start>\ ’ "

\*-vsturt )end-slart>k-\ )end>skirt

BraidkElement start ^ 1 end / XXхstart-k-vi )i-\jjk\k=^ ’

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

Был разработан ряд усовершенствований, улучшающих показатели работы предложенного алгоритма. Так как наиболее приоритетным, как правило, является состояние данных последнего резервирования, то возможно временное создание дополнительных элементарных копий вида R ( k – 1, 1) на конечный момент t _k , которое позволит повысить вероятность восстановления к данному состоянию до 100%. Создание и хранение периодических дополнительных копий вида R ( x , 1) служат «мостами»-переходами между уровнями алгоритма, которые позволяют значительно увеличить вероятность восстановления при выходе из строя носителей резервных копий.

Анализ результатов расчетов

Рассмотрим результаты расчетов со следующими параметрами: значения роста и изменения в экспоненциальной модели в пределах от 0,001% до 1%, совпадение изменений 10-90%, данные за 365 моментов резервирования. Средние значения показателей эффективности (AERTime) и восстановимости (RProbE), рассчитанные для алгоритмов, представлены на рис. 5.

Рис. 5. Эффективность и восстановимость алгоритмов РК

Как можно видеть из представленных данных, наибольшей эффективностью обладает ин- крементный алгоритм («Incr»), но отсутствие избыточности обусловливает нулевое значение показателя восстановимости. Вторым по показателю средней эффективности является алгоритм плетения второй степени и с создаваемыми мостами переходов каждые десять моментов РК («BRAID2»). Его эффективность на 22% превосходит эффективность «Z scheme» с четырьмя уровнями («Z0-4»). Мультиуровневый алгоритм на основе схемы плетения с двумя уровнями («Mult(B2)») показывает на 50% большую эффективность, чем мультиуровневый алгоритм («Mult(D)»).

Соотношения величин объемов, требуемых для хранения копий различными способами РК, представлены на рис. 6. Важной особенностью является то, что для работы схемы плетения требуется сравнительно малый объем памяти для хранения копий. Согласно рис. 6, для работы схемы «BRAID2» потребовался в 2 раза больший объем репозитория, чем для инкрементного подхода (оптимального в данном смысле), что, в свою очередь, является более чем в два раза меньшим требованием, чем для следующего по показателю эффективности алгоритма «Z scheme», обозначенного «Z0-4». Для «Mult(D)» потребовался в два раза больший объем, чем для схемы «Mult(B2)». Алгоритм Костелло с соавт. («WCU0-4») показал средние результаты.

Рис. 6. Соотношение объемов копий различных алгоритмов РК

Заключение

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

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

Работа поддержана Аналитической ведомственной целевой программой «Развитие научного потенциала высшей школы 2009-10 г.г.» (№ 2.1.2/2485), а также Фондом содействия развитию малых форм предприятий в научно-технической сфере в рамках программы «УМНИК» 2008-10 г.г. (№ 08-2-8446).