книги2 / монография 31
.pdf
Министерство науки и высшего образования РФ
Федеральное государственное бюджетное учреждение науки
Институт проблем управления им. В.А. Трапезникова
Российской академии наук
В.В. Кульба, Е.А. Микрин, С.К. Сомов
Репликация данных в динамических распределенных информационных системах
Научное электронное издание
Москва ИПУ РАН
2023
УДК 004.75:004.056 ББК 32.973.202
К90
Кульба В.В. Репликация данных в динамических распределенных информационных системах / В.В. Кульба, Е.А. Микрин, С.К. Сомов; Институт проблем управления им. В.А. Трапезникова РАН, Минобрнауки России. – Электрон. текстовые дан. (1 файл: 3,6 Мб). – Москва : ИПУ РАН, 2023. – 1 CD-R. – Систем. требования: Pentium 4; 1,3 ГГц и выше; Windows XP/7/8; Acrobat Reader 4.0 или выше. –
Загл. с титул. экрана. – ISBN 978-5-91450-265-9. – № госрегистрации 0322300668. – Текст: электронный.
Внаучном издании рассмотрены особенности репликации данных в динамических распределенных системах обработки данных, параметры работы которых могут меняться, что повлияет на эффективность их работы и потребует нового размещения реплик данных в узлах систем.
Вработе представлены модели и алгоритмы поиска оптимального размещения реплик в динамических системах и в мобильных сетях MANET с примерами их работы.
Работа предназначена для научных работников и специалистов в области ИТ.
Рецензенты: д.т.н., профессор Акинфиев В.К., д.т.н., профессор Лебедев В.Г.
Утверждено к печати Редакционным советом Института
Текст воспроизводится в виде, утвержденном Редакционным советом Института
ISBN 978-5-91450-265-9 |
© ИПУ РАН, 2023 |
ПРЕДИСЛОВИЕ
Многие годы выдающийся российский ученый, генеральный конструктор пилотируемых программ РФ, генеральный конструктор ОАО РКК «Энергия» им. С.П. Королева, академик РАН, член президиума РАН, руководитель Секции машиностроения и процессов управления ОЭММПУ РАН Евгений Анатольевич Микрин был неформальным научным руководителем группы сотрудников ИПУ РАН (далее – Институт). Эта группа была создана по предложению Е.А. Микрина в один из самых тяжелых периодов жизни страны (в период так называемого «дикого капитализма»). В тот период Е.А. Микрин был руководителем департамента РКК «Энергия». Под его руководством и при его непосредственном участии постоянно совершенствовались математическое и программное обеспечение систем управления космических кораблей типа «Союз» и исследовательских модулей «Заря», «Звезда», МКС и многих других объектов.
Основной целью работ созданной группы, которая стала объединяющим звеном дружной эффективной работы сотрудников, являлась разработка теоретических основ проектирования информационно-управляющих систем космических аппаратов. Группой был опубликован ряд коллективных монографий, основная из которых – «Теоретические основы проектирования информационно-управляющих систем космических аппаратов» под редакцией д-ра техн. наук Е.А. Микрина. Данная книга является примером системного рассмотрения основных проблем создания информационно-управляющих систем жесткого реального времени.
Результаты исследований, как отмечал академик Б.Е. Черток, «были использованы в качестве оптимальных методических технических решений при создании бортовых комплексов управления МКС и других космических аппаратов. Успешная реализация космических программ доказывает исключительную практическую ценность предлагаемого научного труда». Одновременно был опубликован ряд научных статей в различных журналах, в том числе и в журнале «Проблемы управления», членом редсовета которого Е.А. Микрин был много лет.
Серьезные научные и методологические результаты были также получены при разработке следующего направления: «Модели и
методы обеспечения сохранности данных и их эффективного использования в распределенных системах».
В данном направлении рассмотрен ряд методов решения актуальных задач обеспечения сохранности данных и повышения эффективности их использования в распределенных системах различного масштаба и назначения. Распределенные системы получили за последние десятилетия широчайшее распространение во многих областях деятельности человека. Такие системы используются в промышленности, торговле, банковском деле, космосе, здравоохранении, системах связи, в обучении и в военных областях. Они обслуживают огромное количество пользователей, обрабатывают и хранят гигантские объемы информации разного рода.
Сучетом этих особенностей предложены методы оперативного
ивосстановительного резервирования массивов данных и программных модулей в компьютерных сетях. Предложены модели
исформулированы задачи динамической репликации данных в распределенных системах. Представлена модель и формулировка задачи репликации данных в мобильных сетях с учетом их особенностей.
Методы поиска оптимального размещения реплик в узлах распределенной системы, имеющей динамические параметры работы, используют различные технологии и эвристики для перераспределения реплик (миграции экземпляров реплик) по узлам сети или изменения числа реплик, использующихся в системе.
Для решения сформулированных задач предложены оригинальные алгоритмы их решения и приведены примеры работы этих алгоритмов.
Материал работы основан на использовании большого количества источников, что является еще одним достоинством данной работы, и может быть полезен ученым, занимающимся проблемами сохранности данных, а также аспирантам и студентам соответствующих специальностей.
Полученные под научным руководством академика РАН Е.А. Микрина результаты имеют значение не только для космической отрасли, но и для развития науки в нашей стране. Большинство перспективных направлений будут разрабатываться в ИПУ РАН и в дальнейшем.
ОГЛАВЛЕНИЕ |
|
ВВЕДЕНИЕ............................................................................................. |
7 |
ГЛАВА 1. КРАТКАЯ ИСТОРИЯ РАЗВИТИЯ МЕТОДОВ |
|
РЕПЛИКАЦИИ ДАННЫХ В РАСПРЕДЕЛЕННЫХ |
|
ИНФОРМАЦИОННЫХ СИСТЕМАХ............................... |
8 |
ГЛАВА 2. МЕТОДЫ РЕАЛИЗАЦИИ РЕПЛИКАЦИИ ДАННЫХ |
|
В РАСПРЕДЕЛЕННЫХ ИНФОРМАЦИОННЫХ |
|
СИСТЕМАХ....................................................................... |
10 |
2.1. Методы оптимального размещения реплик........................ |
12 |
2.2. Группа методов статического размещения реплик............ |
14 |
2.3. Группа методов динамического размещения реплик........ |
16 |
ГЛАВА 3. ДИНАМИЧЕСКАЯ РЕПЛИКАЦИЯ МАССИВОВ |
|
ДАННЫХ В РАСПРЕДЕЛЕННЫХ СИСТЕМАХ, |
|
ИМЕЮЩИХ ИЗМЕНЯЮЩИЕСЯ ПАРАМЕТРЫ |
|
РАБОТЫ ............................................................................. |
19 |
3.1.Формальная модель распределенной системы,
использующей репликацию массивов данных................... |
23 |
3.2. Параметры задачи оптимального размещения реплик...... |
25 |
3.2.1. Затраты на хранение реплик в узлах системы............ |
28 |
3.2.2. Затраты на функционирование распределенной |
|
системы........................................................................... |
29 |
3.2.3. Среднее время обработки запросов в системе............ |
36 |
3.2.4. Приоритет узлов сети, генерирующих запросы |
|
к массивам данных и их репликам............................... |
38 |
3.3.Формулировка и решение задачи адаптивного
размещения реплик массивов данных................................. |
40 |
3.3.1. Описание эвристического алгоритма размещения |
|
реплик массивов............................................................ |
43 |
3.3.2. Тестирование эвристического алгоритма |
|
размещения реплик массивов данных......................... |
49 |
3.3.3. Описание работы алгоритма при тестировании......... |
57 |
3 |
|
3.3.4. Анализ результатов работы алгоритма ....................... |
67 |
3.4.Задача поиска распределения реплик, оптимального
по среднему времени обработки запросов.......................... |
76 |
3.5.Тест №2 алгоритма решения задачи оптимального
размещения реплик............................................................... |
77 |
3.6.Тест №3 алгоритма решения задачи оптимального
размещения реплик............................................................... |
82 |
3.7.Анализ эффективности эвристического алгоритма
оптимального адаптивного размещения реплик................ |
86 |
|
ГЛАВА 4. ДИНАМИЧЕСКАЯ РЕПЛИКАЦИЯ ФРАГМЕНТОВ |
|
|
ТАБЛИЦ ДАННЫХ В РАСПРЕДЕЛЕННЫИНЫХ |
|
|
ИНФОРМАЦИОННЫХ СИСТЕМАХ............................. |
89 |
|
4.1. Методы фрагментации таблиц данных............................... |
91 |
|
4.1.1. |
Горизонтальная фрагментация таблиц........................ |
92 |
4.1.2. |
Вертикальная фрагментация таблиц............................ |
93 |
4.2.Метод вертикальной фрагментации таблиц баз данных
распределенной системы...................................................... |
95 |
|
4.2.1. Этап 1. |
Анализ предметных областей |
|
пользователей ................................................................ |
96 |
|
4.2.2. Этап 2. |
Синтез программных модулей |
|
и логической структуры фрагментов........................... |
97 |
|
4.2.3. Этап 3. |
Размещение фрагментов таблиц |
|
по узлам сети.................................................................. |
99 |
|
4.3.Этап синтеза программных модулей и логической
структуры фрагментов таблиц............................................. |
99 |
4.4.Метод динамического размещения фрагментов
таблиц в узлах распределенной системы.......................... |
105 |
4.5. Формальная модель метода динамического |
|
перераспределения фрагментов таблиц............................ |
106 |
4.5.1. Параметры и ограничения размещения |
|
фрагментов таблиц...................................................... |
107 |
4 |
|
4.5.2. Параметры запросов к фрагментам и процессов |
|
|
|
их обработки в узлах сети........................................... |
108 |
4.5.3. |
Вес фрагмента таблицы, размещенного |
|
|
в конкретном узле системы........................................ |
111 |
4.5.4. Затраты на функционирование распределенной |
|
|
|
системы......................................................................... |
113 |
4.5.5. |
Среднее время обработки запроса в системе............ |
116 |
4.6.Формулировка и алгоритм решения задачи
оптимального размещения фрагментов............................ |
117 |
|
4.6.1. |
Формулировка задачи................................................. |
117 |
4.6.2. |
Алгоритм решения задачи.......................................... |
118 |
4.7.Пример № 1 решения задачи оптимального
размещения фрагментов таблиц........................................ |
123 |
4.8.Пример № 2 решения задачи оптимального размещения
фрагментов таблиц.............................................................. |
133 |
ГЛАВА 5. РАЗДЕЛЕНИЕ УЗЛОВ РАСПРЕДЕЛЕННОЙ |
|
СИСТЕМЫ НА ЛОГИЧЕСКИЕ КЛАСТЕРЫ И |
|
РАЗМЕЩЕНИЕ В НИХ ФРАГМЕНТОВ ТАБЛИЦ |
|
ДАННЫХ.......................................................................... |
141 |
5.1. Проблема логической кластеризации узлов |
|
распределенной системы.................................................... |
142 |
5.2. Группировка узлов системы в логические кластеры....... |
143 |
5.2.1. Предлагаемый метод группировки узлов |
|
распределенной системы в логические кластеры..... |
147 |
5.2.2. Эвристический алгоритм группировки узлов |
|
в кластеры .................................................................... |
148 |
5.2.3. Пример работы алгоритма группировки узлов |
|
в логические кластеры................................................ |
153 |
5.2.4. Распределение реплик фрагментов таблиц |
|
по логическим кластерам............................................ |
155 |
5 |
|
ГЛАВА 6. ДИНАМИЧЕСКАЯ РЕПЛИКАЦИЯ ДАННЫХ |
|
В МОБИЛЬНЫХ БЕСПРОВОДНЫХ СЕТЯХ |
|
С ПРОИЗВОЛЬНОЙ СТРУКТУРОЙ MANET.............. |
157 |
6.1. Виды мобильных сетей....................................................... |
158 |
6.2.Особенности сетей MANET, влияющие на репликацию
данных в этих сетях............................................................ |
162 |
6.3. Особенности маршрутизации в ad hoc сетях MANET..... |
167 |
6.4. Краткий обзор методов репликации данных |
|
в мобильных сетях .............................................................. |
169 |
6.4.1. Методы репликации, основанные на подсчете |
|
частоты доступа к данным.......................................... |
170 |
6.4.2. Другие методы репликации........................................ |
172 |
6.4.3. Метод E-SAF распределения реплик по узлам |
|
мобильной сети............................................................ |
172 |
6.5. Эвристический метод распределения реплик |
|
в ad hoc сети MANET.......................................................... |
176 |
6.5.1. Описание формальной модели предлагаемого |
|
метода распределения реплик.................................... |
179 |
6.5.2.Описание эвристического алгоритма передислокации реплик элементов данных
в сети MANET ............................................................. |
184 |
6.6.Пример работы эвристического алгоритма
в произвольном узле сети MANET.................................... |
189 |
|
6.6.1. |
Исходные данные для работы алгоритма.................. |
189 |
6.6.2. |
Описание работы алгоритма в трех узлах сети ........ |
195 |
ЗАКЛЮЧЕНИЕ................................................................................... |
200 |
|
ЛИТЕРАТУРА.................................................................................... |
201 |
|
6
ВВЕДЕНИЕ
Несмотря на постоянное улучшение эффективности и надежности работы аппаратных средств вычислительной техники, программного обеспечения, средств связи и технологий по хранению и обработке данных актуальной остается проблема значительных финансовых потерь организаций, вызванных незапланированными простоями используемых ими систем обработки данных из-за потери или искажения данных.
В процессе проектирования и создания распределенных систем обработки данных (РСОД) различного назначения и масштаба критически важным является обеспечение требуемого уровня сохранности данных, надежности работы системы и ее высокой производительности.
В работе рассматриваются формальные модели и методы, которые могут быть использованы на этапе проектирования РСОД различного масштаба и назначения для повышения сохранности данных, используемых в этих системах. В работе приведены формальные модели и методы репликации данных, которые обеспечивают повышение эффективности использования ресурсов распределенных систем с точки зрения затрат на их эксплуатацию, повышение надежности работы системы, и уровня сохранности данных, а также для уменьшения времени реакции системы на запросы пользователей и прикладных процессов к данным, используемым в системе.
7
ГЛАВА 1. КРАТКАЯ ИСТОРИЯ РАЗВИТИЯ МЕТОДОВ РЕПЛИКАЦИИ ДАННЫХ В РАСПРЕДЕЛЕННЫХ ИНФОРМАЦИОННЫХ СИСТЕМАХ
На протяжении первых лет развития технологий обработки данных средствами вычислительной техники наблюдался некоторый дисбаланс. Основные усилия направлялась на развитие аппаратных
ипрограммных средств работы с данными. Сами данные воспринимались как нечто простое и очевидное, а технологии хранения данных на периферийных устройствах (перфокарты и перфоленты, магнитные ленты и т.д.) были вторичными по отношению к основному процессу обработки данных.
Однако, постепенно, по мере роста объемов и сложности структуры используемых данных и по мере возрастания ценности данных для бизнеса, а также роста требований к надежности и скорости обработки данных, компании – производители средств вычислительной техники и программного обеспечения стали уделять значительное внимание вопросам повышения сохранности данных, оптимизации затрат на их хранение, обработку и восстановление данных в случае их разрушения.
Это привело к появлению новых направлений научных исследований в области разработки формальных моделей и методов резервирования и восстановления ванных для обеспечения высокого уровня сохранности, а также формальных моделей и методов оптимального размещения массивов данных по узлам компьютерных сетей с учетом различных дисциплин обработки запросов к данным.
ВСоветском Союзе и за рубежом первые научные работы по данным направлениям появились в шестидесятых-семидесятых годах прошлого века [1–7]. В этих работах рассматривались задачи надежного использования данных в автономных информационных системах, работающих на базе отдельных компьютеров, и компьютеров, объединенных каналами связи в вычислительные сети,
ираспределенных базах данных [8–10]. В Институте Проблем Управления РАН также активно велись исследования по данной теме [11–17]. С течением времени количество работ, посвященных данной тематике, постоянно росло в силу актуальности проблемы.
Резкий всплеск количества таких работ произошел после того, как появились промышленные компьютерные сети, что обеспечило
8