Математические модели и алгоритмы организации потоков данных для оптимизации поиска и хранения информации в системах резервного копирования

3.2. Включающий поиск.99.

3.2.1 Оценка сложности включающего поиска.102.

3.2.2. Недревовидность оптимальных ИГ включающего поиска в общем случае.104.

3.2.3. Древовидностъ оптимальных ИГ включающего поиска в классе бесповторных сетей.106.

3.2.4. Алгоритмы включающего поиска.107.

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

3.3.1. Представление бинарного поиска с помощью графовой модели 114.

3.3.2. Оптимизация алгоритма бинарного поиска в информационно-графовой модели.118.

3.3.3. Мгновенное решение.121.

3.4. Поиск объектов информационной системы с помощью решения задач о доминировании. 125.

3.4.1. Одномерный случай. 126.

3.4.2. Многомерный случай. 127.

3.5. Фоновый алгоритм поиска. 130.

3.6. Полученные результаты и выводы. 134.

Глава 4. Математическое моделирование процессов, происходящих в аппаратуре резервного копирования и хранения информации на ленточном носителе. 135.

4.1. Получение аналитической зависимости ЭДС от волновых потерь на выходе магнитной головки воспроизведения при записи амплитудно-модулированного сигнала. 135.

4.2. Влияние неравномерности скорости протягивания ленты в стримерах на динамику ее перекосов. 142.

4.3. Исследование влияния напряженно-деформированного состояния ленточного носителя на динамическую точность регистрации информации. 150.

4.3.1. Расчет колебаний и деформаций ленточного носителя, идентифицированного трехзвенной «стандартной «моделью ^q.

4.3.2. Анализ планарных колебаний ленты, идентифицированной моделью Пойтинга-Томсона. 158.

4.3.3. Вероятностная модель участка ленточного носителя, находящегося под воздействием случайной нагрузки. ^.

4.4. Полученные результаты и выводы.170.

Заключение

171.

Литература

174.

Приложение.185.

Акт о внедрении результатов диссертационной работы. 186.

Актуальность темы

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

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

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

Тем не менее, если данная технология дополняется уже испытанным хранением на лентах, то предприятие получает большой выигрыш в гибкости и достаточную защищенность данных. Это следует из того, что важные для жизнедеятельности предприятия данные профессионалы предпочитают хранить на надежной ленте в сейфе, где ей не страшны ни вирусы, ни отказ диска, ни потеря питания, пока лента хранится автономно. Ни один вращающийся носитель данных не предлагает этих важных преимуществ при столь низкой цене. Стоимость в расчете на 1 Гбайт в случае VXA-3 равна приблизительно 0,25 евро при общей емкости 240 Гбайт сжатых данных. Для LTO 3 (Ultrium 3) цена снижается до 0,10 евро за 1 Гбайт при емкости в 800 Гбайт сжатых данных.

При правильном хранении ленты исправно служат гораздо дольше десяти лет. По данным производителя, ленточные носители VXA-2 и VXA-3, к примеру, выдерживают 20 тыс. «проходов», что соответствует примерно 1000 полных резервных копирований. Таким образом, можно удобно хранить и управлять многими поколениями данных. Кроме того, для некоторых пользователей подобный образ действий обеспечивает своего рода «эффект бумаги»: лент или картриджей можно касаться и делать на них пометки, к тому же они сравнительно не чувствительны к грубым воздействиям.

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

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

Объектом исследования являются сети хранения данных, устройства резервного копирования и хранения информацииинфокоммуникационные системыинформационно-графовые модели данныхмеханизм транспортирования ленты (MTJI) — магнитная лента (MJI).

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

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

Для достижения поставленной цели решены следующие задачи:

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

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

— предложить модель протокола резервирования информации, основанная на модели типа клиент-север, и рассмотрены различные конфигурации его реализации в зависимости от поставленных задач;

— рассмотреть процессы протекания потоков контроля соединения и данных во время операции резервного копирования и восстановления информации;

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

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

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

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

— определить степень влияния параметров движения ленточного носителя на динамические характеристики MTJIпровести исследования вынужденных продольных и планарных колебаний участка ленты под воздействием продольной нагрузки с учетом распределенности параметроввывести аналитические выражения для напряженно-деформированного состояния ленты.

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

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

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

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

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

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

На защиту выносятся разработанные автором диссертации математические и алгоритмические модели организации потоков данных для оптимизации поиска и хранения информации в системах резервного копирования, в том числе:

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

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

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

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

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

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

— получение аналитических зависимостей вероятностных характеристик смещения ленты, реологические свойства которой идентифицируются моделью Кельвина-Фойгта, на которую воздействуют случайные возмущения, рассматриваемые как стационарный случайный процесс, путем применения метода Бубнова-Галеркина для нестационарных задач с предварительным сведением краевой задачи к виду, в котором краевые условия становятся нулевыми, решения системы дифференциальных уравнений второго порядка относительно «обобщенных координат», являющихся случайными функциями, вероятностные характеристики которых определяются по известной корреляционной функции натяжения ленты.

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

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

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

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

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

— использование аналогии между упругостью и вязко-упругостью, применение к уравнениям движения, реологического состояния и краевым условиям для вязкоупругого тела преобразования Лапласа, сведения краевой задачи с помощью обобщения метода Бубнова-Галеркина к системе линейных алгебраических уравнений относительно переменных, к которым впоследствии применяется метод обращения Лапласа с помощью полиномов Лежандра, позволил получать расчетные зависимости для вынужденных продольных и планарных колебаний ленточного носителя под воздействием продольной нагрузки с учетом распределенности параметров для трехзвенной реологической модели;

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

Реализация работы в производственных условиях. Полученные результаты использованы и апробированы для опытно-производственной эксплуатации системы организации потоков данных в Тульском филиале ОАО «ЦентрТелеком».

Созданные модели и алгоритмы позволили повысить эффективность организации системы резервирования информации и уменьшить временные затраты на поиска информационных объектах в базах данных.

Апробация работы. Результаты работы докладывались на российских и международных научно-технических конференциях и конгрессах: VII Всероссийской НТК «Повышение эффективности средств обработки информации на базе математического моделирования» (Тамбов, 2004) — XXXI Международной конференции «Информационные технологии в науке, образовании, телекоммуникациях и бизнесе» (Украина, Крым, Ялта — Гурзуф, 2004) — Международном симпозиуме «Надежность и качество» (Пенза, 2004;2005) — VI Международном конгрессе по математическому моделированию (Нижний Новгород, 2004) — V Международной НТК «Проблемы техники и технологии телекоммуникаций» (Самара, 2004) — VII Молодежной НТК «Наукоемкие технологии и интеллектуальные системы» (Москва, 2005) — Всероссийской НТК «Компьютерные и информационные технологии в науке, инженерии и управлении» (Таганрог, 2005) — Международной НТК «Искусственный интеллект-2005» (п. Дивноморское, 2005) — Международной НТК «Интеллектуальные и многопроцессорные систе-мы-2005» (Таганрог, 2005) — XXXIII Международной конференции «Информационные технологии в науке, социологии, экономике и бизнесе» (Украина, Крым, Ялта — Гурзуф, 2006) — VII Международной НТК «Проблемы техники и технологии телекоммуникаций» (Самара, 2006).

Публикации. Результаты работы отражены в 17 научных трудах: 7 статей в центральной печати, 9 публикаций в сборниках материалов всероссийских и международных научно-технических конференций, 1 депонированная рукопись (объемом 21 страницу). Автор имеет 7 научных трудов в изданиях, рекомендуемых ВАКом для публикации основных результатов диссертаций.

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

Диссертация содержит введение, 4 главы и заключение, изложенные на 186 с. машинописного текста. В работу включены 48 рис., 6 табл., список литературы из 135 наименований и приложение, в котором представлен акт об использовании результатов работы.

ЗАКЛЮЧЕНИЕ

.

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

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

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

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

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

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

6. Для проведения динамического расчета поведения ленточного носителя в MTJI составлена математическая модель, учитывающая сложный характер зависимости между напряжением и деформацией. Использование в ней аналогии между упругостью и вязкоупругостыо, применение к уравнениям движения, реологического состояния и краевым условиям для вязкоупругого тела преобразования Лапласа, сведения краевой задачи с помощью обобщения метода Бубнова-Галеркина к системе линейных алгебраических уравнений позволило получить расчетные зависимости для вынужденных продольных и пла-нарных колебаний участка ленточного носителя под воздействием продольной нагрузки с учетом распределенности параметров для трехзвенной реологической модели.

7. Применение метода Бубнова-Галеркина для нестационарных задач с предварительным сведением краевой задачи к виду, в котором краевые условия становятся нулевыми, позволяет находить стохастические характеристики смещения ленты, реологические свойства которой идентифицируются моделью Кельвина-Фойгта, на которую воздействуют стационарные случайные процессы. Эффективность методики заключается в возможности численно-аналитического решения без неоправданно больших затрат. Она позволяет определить степень влияния параметров ленточного носителя на динамические характеристики.

8. Составлена стохастическая модель продольных колебаний вязкоупру-гого ленточного носителя с учетом распределенности его параметров. В результате применения корреляционной теории случайных процессов и обобщения метода Бубнова-Галеркина получены расчетные формулы для нахождения корреляционной функции натяжения ленты, что позволяет определить степень влияния параметров внешнего воздействия на колебания ленты и прогнозировать динамические свойства МТЛ при случайном воздействии.