Книги по разным темам Pages:     | 1 | 2 | 3 | Электронный журнал ИССЛЕДОВАНО В РОССИИ 746 Резервирование, тиражирование и восстановление данных в параллельных интероперабельных вычислительных системах с динамически изменяемой конфигурацией.

Рожков К.Н. (rozhkov@mail.primorye.ru) Институт математики и компьютерных наук ДВГУ, г. Владивосток Введение Одним из перспективных направлений развития информационных технологий становится метакомпьютинг. Использование компьютерных сетей различного масштаба для создания единой вычислительной инфраструктуры требует особого внимания к обеспечению целостности данных в таких системах.

В работах [5, 6, 7, 8] проведен подробный анализ вопросов обеспечения целостности данных в распределенных вычислительных системах, разработаны и исследованы методы резервирования, тиражирования и восстановления данных. Однако, для обеспечения нормального процесса функционирования метакомпьютера необходимо наличие возможности динамического изменения его конфигурации в зависимости от некоторых внешних факторов. К таким факторам можно отнести, прежде всего, выход из строя одного или нескольких узлов сети или необходимость динамического подключения к метакомпьютеру новых узлов с целью увеличения его производительности.

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

Электронный журнал ИССЛЕДОВАНО В РОССИИ 747 Аппаратная архитектура метакомпьютера и математическая модель системы Аппаратная архитектура метакомпьютера и математическая модель системы более подробно описаны в статье Объектно-ориентированный анализ как средство моделирования параллельных интероперабельных систем с динамически изменяемой конфигурацией. Здесь же ограничимся кратким определением основных понятий.

Основные понятия и определения Математическая модель системы построена методом объектноориентированного анализа и представлена в виде диаграмм Сущность-Связь [11] в нотации Шлеер-Меллора [10].

Введем основные определения.

Здесь под объектом будем понимать конкретный опознаваемый предмет, единицу или сущность (реальную или абстрактную), имеющую четко определенное функциональное назначение в данной предметной области. [11, 12] Под абстракцией (сущностью) будем понимать существенные характеристики объекта, которые отличают его от всех других объектов и четко определяют его концептуальные границы для наблюдателя. [1] Под атрибутом будем понимать абстракцию одной характеристики, которой обладают все абстрагированные как объект сущности. [10] Под состоянием будем понимать положение объекта, в котором применяется определенный набор правил, иний поведения, предписаний и физических законов.

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

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

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

Процесс функционирования системы вкратце может быть описан следующим образом:

1. Пользователь через интерфейс Блока управления Задачами осуществляет запуск Задачи.

2. Задача запрашивает у Системы Домен, получает его и инициализирует все Узлы Процессами.

3. Процессы начинают обработку своих Баз данных.

Электронный журнал ИССЛЕДОВАНО В РОССИИ 748 4. Задача осуществляет синхронизацию процессов.

5. В ходе работы Процесса на узле осуществляется резервирование соответствующих Базы данных и Данных узла а также тиражирование данных (при необходимости). В этом процессе принимают участие Таблицы и Механизмы тиражирования и резервирования а также соответствующие Мониторы.

6. В случае выхода из строя того или иного Узла или Базы данных ее восстановление осуществляется соответствующим Механизмом восстановления.

Возможная архитектура метакомпьютера представлена на рис. 1.

Рис.1 Архитектура метакомпьютера Электронный журнал ИССЛЕДОВАНО В РОССИИ 749 Резервирование и тиражирование данных [6] Особенности обновления и использования баз данных позволяют выделить следующие стратегии их резервирования:

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

2. Используются особенности обновления баз текущих данных, которые заключаются в том, что в качестве копий текущей базы служат ее предыстории (предыдущие копии базы и массивы изменений). Если текущая база разрушилась, то она восстанавливается программой обновления из предыдущей базы и массива изменений.

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

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

С целью упрощения изложения совпадающие стратегии тиражирования и резервирования будем называть дублированием.

Резервирование Базы данных Общие положения Рассмотрим функционирование Процесса на Узле с точки зрения резервирования.

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

Далее будет рассмотрен процесс функционирования стратегий и проведено сравнение эффективности стратегий по следующим критериям:

1. Критерий максимальной надежности.

2. Критерий максимального быстродействия.

3. Критерий минимизации величины потерь при сбое.

Исследование стратегий резервирования (дублирования) Стратегия I. На рис. 2 представлено функционирование Процесса при использовании данной стратегии. База данных F00 дублируется копиями F0r, r = 1,k Электронный журнал ИССЛЕДОВАНО В РОССИИ 750 F1 F1 Fp p p F0 q F0 q Fq q t = 0 t = 1 t = k Рис. 2. Функционирование Процесса при использовании Стратегии I Вероятность того, что База данных не будет разрушена за единичный интервал времени при ее использовании, есть p. Вероятность разрушения Базы данных за единичный интервал времени ее использования q = 1 - p. Вероятность разрушения Базы данных за время ее хранения принимается равной нулю. Если копия F0r(r = 0, k - 1) разрушается в заданный единичный интервал времени, следующая копия Fr+1 используется в следующий интервал для завершения обработки Прикладным процессом и т.д.

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

p + pq + pq2 + Е + pqk + qk+1 = и вероятность успешного решения задачи = pk+1 при наличии k копий = 1 - qk+1, I где индекс I означает использование первой стратегии дублирования.

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

При априори больших k используется центральная предельная теорема. В этом случае можно записать:

{E(X ) - X E(X ) +} = 1-, откуда k определяется в виде:

k = {-1}2, где 2 = -2, E(X) = qp-1, 2 - допустимые пределы изменений k для заданного уровня риска ; t - стандартное переменное отклонение.

Детерминированная оценка k определена при условии, что мала при заданной величине 1 = таким образом, получаем:

k = ln(1-)(ln q)-1 - Рассмотрим временные характеристики процессов при использовании стратегии I.

Электронный журнал ИССЛЕДОВАНО В РОССИИ 751 Время создания k копий определим как:

E[T1(1)] = k, где - время создания одной копии.

Среднее время решения задачи при наличии k копий и при условии, что она решена успешно, определяется в виде E[TI(2)] = p-1[1-qk+1[1+(k+1)p]], где - интервал времени использования Базы данных (обновления Базы).

С другой стороны, среднее время, затраченное на обработку Базы данных, вне зависимости от того, будет она завершена успешно или нет, определяется из выражения E[TI(3)] = p-1[1-qk+1] Таким образом, планируемое среднее время задействования Узла (или использование стратегии I) E[TI] = E[TI(1)] + E[TI(3)] Стратегия II. Модель формулируется следующим образом (рис. 3): пусть в начальный момент времени t = 0 рассматриваемый Процесс находится в состоянии, при котором имеется База данных F00 и k ее предысторий, и требуется создать обновленную Базу F1. Таким образом, имеется a = k + 2 состояний системы.

qq qq F(kF- F-1 F0 Fpp pp p t = -k - 1 t = -k t = - (k - 1) t = - 1 t = 0t = Рис. 3. Функционирование Процесса при использовании Стратегии II За фиксированное единичное время с вероятностью p обновленная База данных F1 может быть создана, а с вероятностью q = 1 - p База F00 может быть разрушена, и Процесс будет находиться в состоянии F-1. Работа Процесса продолжается до тех пор, пока База F00 и k ее предысторий не будут разрушены, ибо не будет создана обновленная База F1 в соответствии со второй стратегией дублирования.

Определим следующие характеристики Процесса при данной стратегии дублирования: вероятность обновления Базы F00 (вероятность создания обновленной Базы F1); вероятность разрушения Базы F00 и k ее предысторий; продолжительность функционирования Узла до обновления Базы, до разрушения всех предысторий, а также среднее время функционирования Узла.

Пусть обновление Базы совершается в некоторые моменты времени t = 1, 2, 3,Е и будем интерпретировать их исходы как перемещения шарика по целочисленным точкам действительной прямой между двумя поглощающими экранами. В момент времени t=0 шарик находится в положении x = z = k + 1, а в моменты t = 1, 2 Е он перемещается на один шаг влево или вправо в зависимости от успеха или неудачи соответствующего обновления, т.е. совершает случайное блуждание. Таким образом, положение шарика в произвольный момент времени определяет количество неразрушенных баз после окончания -го обновления. Работа заканчивается, когда шарик в первый раз попадает в положение x = 0 или x = a, т.е. эти граничные положения явЭлектронный журнал ИССЛЕДОВАНО В РОССИИ 752 яются поглощающими экранами. Создание обновленной Базы F1 интерпретируется как поглощение в точке x = a, а разрушение Базы F00 и k ее копий - как поглощение в точке x = 0. Возможные состояния Процесса ограничены положениями x = 0, 1, 2, Е a.

Пусть qz - вероятность того, что База F00 и k ее копий будут разрушены, а pz - вероятность того, что База F00 будет обновлена. В терминах случайных блужданий qz и pz означают вероятность того, что точка, выходящая из z, будет поглощена экраном x = 0 или x = a соответственно. Если Процесс находится в состоянии z, то после первой попытки обновления она перейдет в состояние z - 1 ибо z + 1, и поэтому при 1 < z < a - qz = pqz+1 + qqz-При z = q - 1 = k + 1 первая попытка обновления может привести Процесс в состояние F1, и поэтому qa-1 = q qa-2 + p При z = 1 первая же попытка обновления может привести к разрушению последней хранящейся предыстории текущей Базы, и предыдущее уравнение запишется в виде q1 = pq2 + q Очевидна справедливость граничных условий q0 = 1, qa = Вероятность успешного обновления Базы F00 равна вероятности того, что База F00 и k ее предысторий не будут разрушены, т.е.

(p/q)a - (p - q)a - z pz = (p/q)a - При a = k + 2 и z = k + pk + 1 - qk - II = pk +1 = (p/q)a - Вероятность разрушения Базы F00 и k ее предысторий qk + 1 (q - p) qk +1 = qk + 2 - pk + Детерминированная оценка для k при 2 = определяется следующим образом k = ln(p/q)-1ln[1 - (1 - )-1(1 - p/q)] - Статистическая оценка для k может быть определена аналогично ее определению для стратегии I.

Рассмотрим временные характеристики функционирования Процесса при использовании стратегии 2. Для определения средней продолжительности работы Узла до обновления Базы F00 и до разрушения этой Базы и k ее предысторий применим метод производящих функций [9]. Данная задача аналогична задаче определения продолжительности случайного перемещения шарика из исходного состояния при наличии двух поглощающих экранов при z = k + 2 и z = 0. Так же, как и раньше, исходным положением шарика является z (0 < z < k + 2). Пусть Uz - вероятность того, что Электронный журнал ИССЛЕДОВАНО В РОССИИ 753 процесс закончится на -м шаге у экрана z = 0. После первой попытки обновления система попадет или в точку z + 1 или в точку z - 1, и при 1 < z < k + 1, > 1 можно записать Uz, +1 = pUz+1, + qUz-1, Данное уравнение является разностным и зависит от двух переменных z и Граничные условия являются следующими:

U0, = Uk+2,=0 при и при граничных условиях D0 = 0, Dk+2 = 0. Учитывая, что z = k + 1 и q < p, получаем k + 1 (k + 2)[1- (qp-1)]k+E[TII] = Dk+1 = q - p (q - p)[1 - (qp-1)k+2 ] При q -> 1/2 Dz = z(a - z) и при z = k + 1 E[TII] = Dk+1 = (k + 1), где a = k + 2.

Стратегия III. Функционирование Процесса при использовании стратегии III представлено на рис. 4.

Pages:     | 1 | 2 | 3 |    Книги по разным темам