Алгоритмы синхронизации данных без сохранения состояния

• Автор: Рябков, Николай Сергеевич
• Шифр специальности: 05.13.11
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Москва
• Количество страниц: 128 с. : ил.

Содержание

Список обозначений и сокращений

Введение

Глава 1. Обзор алгоритмов репликации данных

1.1. Технологии построения распределенных информационных систем.

1.2. Требования к системам репликации данных

1.3. Различие систем репликации по принципу установления соединения.

1.4. Различие систем репликации по способу обнаружения изменений

1.4.1. Алгоритмическое обнаружение изменений.

1.4.2. Вероятностное обнаружение изменений.

1.5. Обоснование необходимости создания алгоритма синхронизации без сохранения состояния.
1.6. Основные результаты и выводы.
Глава 2. Алгоритм синхронизации без сохранения состояния.
2.1. Определение хэшфункции
2.2. Алгоритм вычисления хэшфункции М
2.3. Применение хэшфункций для отождествления объектов.
2.4. Алгоритм ЯБУНС.
2.5. Синхронизация данных при помощи хэшфункций с одномерным измельчением данных.
2.6. Синхронизация данных при помощи хэшфункций с двухмерным измельчением данных.
2.6.1. Схема работы алгоритма.
2.6.2. Алгоритмы измельчения интервалов
2.7. Основные результаты и выводы.
ГЛАВА 3. Модель оптимизации алгоритма
3.1. Модель алгоритма.
3.1.1. Константы.
3.1.2. Параметры.
3.1.3. Целевые функции.
3.2. Оптимизация алгоритма
3.2.1. Обзор методов оптимизации.
3.2.2. Оптимизация перебором.
3.2.3. Оптимизация методом генетических алгоритмов.
3.2.4. Графический анализ
3.3. Основные результаты и выводы.
Глава 4. Программные средства синхронизации данных без сохранения состояния
4.1. Средства разработки.
4.2. Архитектура системы и обзор составляющих классов
4.2.1. Общая сборка
4.2.2. Клиентская сборка С1 iii.
4.2.3. Серверная сборка vii.
4.3. Анализ эффекта от внедрения системы синхронизации данных
без сохранения состояния.
4.4. Основные результаты и выводы
Заключение.
Список опубликованных статей
Список литературы


Для того, чтобы такие системы работали слаженно, необходимо четкое понимание того, как и какой информацией эти системы обмениваются. Соответственно, необходимые различным информационным системам, данные, представлены в них в виде набора таблиц и связей между ними. В процессе взаимодействия различных, территориально удаленных, друг от друга систем часто появляется необходимость использовать одни и те же данные на разных узлах. Проблему обновления данных на удаленном узле, в соответствии с изменениями, внесенном на локальном узле и призваны решать системы репликации (синхронизации) баз данных. Простейшим примером территориально распределенной НС, для которой может понадобиться применение системы репликации, является ИС, которая обслуживает компанию с головным офисом и множеством филиалов. В головном офисе формируется некоторый набор справочников, который в дальнейшем должен быть распространен на все территориальные узлы компании. Системы без сохранения состояния этого не требуют. В этих системах пакет изменений формируется прямо во время сеанса репликации. Традиционно системы без сохранения состояния считались неэффективными, так как их использование приводило к очень большим расходам сетевого трафика. В связи с этим системы с сохранением состояния являются гораздо более распространенными. Однако у этих систем есть существенный недостаток: в случае сбоя или целенаправленных действий по изменению данных на узле получателе автоматическое приведение данных в синхронизированное состояние является достаточно затруднительным, если не невозможным. Учеными из исследовательского центра корпорации NEC (Khrabrov A. Sobti S. Yianilos P. N.) был предложен алгоритм, позволяющий сократить затраты трафика в системах без сохранения состояния. Этот алгоритм является, адаптацией идей известного алгоритма RSYNC (Remote Synchronization algorithm) применительно к базам данных. RSYNC использует две хэш-функции (быструю и медленную) для поиска и синхронизации различающихся участков файлов, не прибегая при этом к прямому сравнению данных. Однако такой алгоритм не позволяет эффективно учитывать особенности таблиц баз данных. Для этого необходим переход от одномерной модели представления данных KaKBRSYNC, к двухмерной. Цель и задачи диссертации. Целью работы является разработка и анализ алгоритма и программы репликации данных без сохранения состояния, в распределенных базах данных, позволяющий проводить автоматическое восстановление после сбоя и обеспечивающего сокращение затрат сетевого трафика. Методы исследования. Microsoft . NET Framework 2. Microsoft SQL Server Express . На защиту выносятся. Алгоритм синхронизации баз данных без сохранения состояния на основе хэш-функций, позволившие более эффективно локализовать область измененных данных. Три алгоритма измельчения интервалов, позволяющих эффективно учитывать особенности и неоднородности в синхронизируемых данных. Математическая модель рассматриваемого алгоритма, позволяющая производить максимально точную настройку алгоритма под конкретные условия использования. Практическое значение результатов работы. Разработанный алгоритм был положен в основу системы репликации на базе хэш-функций. В отличие от других алгоритмов синхронизации баз данных предлагаемый алгоритм позволяет приводить базы в синхронизированное состояние во время первого же сеанса репликации, несмотря на то, были ли внесены какие-либо изменения в данные на узле получателе. При этом данный алгоритм расходует сетевой трафик эффективнее, чем другие алгоритмы синхронизации без сохранения состояния, поскольку производит сравнение не самих участков таблицы, а лишь их хэш-значений. В результате внедрения (см. Приложение 1) одной из вариаций данного алгоритма в Федеральном агентстве по техническому регулированию и метрологии в рамках проекта АИС «Метрконтроль» была получена возможность производить автоматическое восстановление состояния глобальных справочников на удаленных узлах и предотвращение распространения некорректных данных далее по всей филиальной сети. Программа была зарегистрирована в реестре программ для ЭВМ, свидетельство № (см. Приложение 3).