Содержание к диссертации
Введение
Глава 1. Обзор алгоритмов репликации данных 12
1.1. Технологии построения распределенных информационных систем 12
1.2. Требования к системам репликации данных 22
1.3. Различие систем репликации по принципу установления соединения 24
1.4. Различие систем репликации по способу обнаружения изменений 28
1.4.1. Алгоритмическое обнаружение изменений 29
1.4.2. Вероятностное обнаружение изменений 35
1.5. Обоснование необходимости создания алгоритма
синхронизации без сохранения состояния 39
1.6. Основные результаты и выводы 40
Глава 2. Алгоритм синхронизации без сохранения состояния
2.1. Определение хэш-функции 42
2.2. Алгоритм вычисления хэш-функции MD5 43
2.3. Применение хэш-функций для отождествления объектов 45
2.4. Алгоритм RSYNC 52
2.5. Синхронизация данных при помощи хэш-функций с одномерным измельчением данных 54
2.6. Синхронизация данных при помощи хэш-функций с двухмерным измельчением данных 56
2.6.1. Схема работы алгоритма 57
2.6.2. Алгоритмы измельчения интервалов 60
2.7. Основные результаты и выводы 63
ГЛАВА 3. Модель оптимизации алгоритма 66
3.1. Модель алгоритма 66
3.1.1. Константы 66
3.1.2. Параметры 69
3.1.3. Целевые функции 70
3.2. Оптимизация алгоритма 78
3.2.1. Обзор методов оптимизации 78
3.2.2. Оптимизация перебором 83
3.2.3. Оптимизация методом генетических алгоритмов 86
3.2.4. Графический анализ 97
3.3. Основные результаты и выводы 99
Глава 4. Программные средства синхронизации данных без сохранения состояния 101
4.1. Средства разработки 101
4.2. Архитектура системы и обзор составляющих классов 103
4.2.1. Общая сборка Common 103
4.2.2. Клиентская сборка ClientReplication 105
4.2.3. Серверная сборка ServerReplication 105
4.3. Анализ эффекта от внедрения системы синхронизации данных без сохранения состояния 108
4.4. Основные результаты и выводы 111
Заключение 113
Список опубликованных статей 115
Список литературы
- Различие систем репликации по принципу установления соединения
- Алгоритм вычисления хэш-функции MD5
- Целевые функции
- Архитектура системы и обзор составляющих классов
Введение к работе
Актуальность темы. Обработка информации на сегодняшний день является одной из важнейших сфер деятельности человека. Множество компьютерных систем, объединенных в единую сеть, формируют глобальное информационное пространство. Для того, чтобы такие системы работали слаженно, необходимо четкое понимание того, как и какой информацией эти системы обмениваются. Для хранения больших объемов информации в современном мире чаще всего используются различные базы данных. Соответственно, необходимые различным информационным системам, данные, представлены в них в виде набора таблиц и связей между ними. В процессе взаимодействия различных, территориально удаленных, друг от друга систем часто появляется необходимость использовать одни и те же данные на разных узлах. Проблему обновления данных на удаленном узле, в соответствии с изменениями, внесенном на локальном узле и призваны решать системы репликации (синхронизации) баз данных. Простейшим примером территориально распределенной ИС, для которой может понадобиться применение системы репликации, является ИС, которая обслуживает компанию с головным офисом и множеством филиалов. В головном офисе формируется некоторый набор справочников, который в дальнейшем должен быть распространен на все территориальные узлы компании.
Существующие системы репликации по способу формирования пакета изменений можно условно разделить на два класса: системы с сохранением состояния и системы без сохранения состояния. Системы с сохранением состояния хранят некоторую
дополнительную информацию о том, какие данные необходимо
передать на удаленный узел во время следующего сеанса
репликации. Системы без сохранения состояния этого не требуют. В
этих системах пакет изменений формируется прямо во время сеанса
репликации. Традиционно системы без сохранения состояния
считались неэффективными, так как их использование приводило к
очень большим расходам сетевого трафика. В связи с этим системы
с сохранением состояния являются гораздо более
распространенными. Однако у этих систем есть существенный
недостаток: в случае сбоя или целенаправленных действий по
изменению данных на узле получателе автоматическое приведение
данных в синхронизированное состояние является достаточно
затруднительным, если не невозможным. /
Учеными из исследовательского центра корпорации NEC (Khrabrov A., Sobti S., Yianilos P.N.) был предложен алгоритм, позволяющий сократить затраты трафика в системах без сохранения состояния. Этот алгоритм является, адаптацией идей известного алгоритма RSYNC (Remote Synchronization algorithm) применительно к базам данных. RSYNC использует две хэш-функции (быструю и медленную) для поиска и синхронизации различающихся участков файлов, не прибегая при этом к прямому сравнению данных. Однако такой алгоритм не позволяет эффективно учитывать особенности таблиц баз данных. Для этого необходим переход от одномерной модели представления данных как в RSYNC, к двухмерной.
Таким образом актуальной является задача разработки метода синхронизации баз данных, позволяющего проводить автоматическое восстановление после сбоя, сокращающего затраты
трафика во время сеанса репликации и позволяющего учитывать особенности и неоднородности синхронизируемой информации.
Цель и задачи диссертации. Целью работы является разработка и анализ алгоритма и программы репликации данных без сохранения состояния, в распределенных базах данных, позволяющий проводить автоматическое восстановление после сбоя и обеспечивающего сокращение затрат сетевого трафика.
Для достижения указанной цели в работе поставлены и решены следующие основные задачи:
изучены и классифицированы современные алгоритмы репликации данных;
разработан алгоритм синхронизации баз данных без сохранения состояния на основе механизма хэш-функций;
предложены три алгоритма измельчения интервалов, позволяющих более эффективно учитывать особенности реплицируемой базы;
построена и исследована математическая модель предложенного алгоритма, позволяющая производить эффективную настройку алгоритма;
предложенные алгоритмы реализованы в виде программных средств.
Методы исследования. Для решения поставленных задач использовались методы теории вероятностей, теоретической криптографии, теории оптимизации и математической статистики. Для программной реализации использован язык программирования С#,
программная среда Microsoft .NET Framework 2.0 и сервер баз данных Microsoft SQL Server Express 2005.
На защиту выносятся.
Алгоритм синхронизации баз данных без сохранения состояния на основе хэш-функций, позволившие более эффективно локализовать область измененных данных.
Три алгоритма измельчения интервалов, позволяющих эффективно учитывать особенности и неоднородности в синхронизируемых данных.
Математическая модель рассматриваемого алгоритма, позволяющая производить максимально точную настройку алгоритма под конкретные условия использования.
Научная новизна диссертационной работы определяется следующими результатами:
разработан новый алгоритм синхронизации баз данных, позволяющий производить автоматическое восстановление после сбоя и дающий возможность эффективно локализовать измененные участки данных;
разработаны три алгоритма измельчения интервалов таблицы, позволяющих производить более точную настройку системы уже после внедрения и дающие возможность анализировать и учитывать особенности данных в таблице;
разработана математическая модель предложенного алгоритма репликации, позволяющая подобрать наиболее эффективные для конкретных условий работы параметры алгоритма.
Практическое значение результатов работы.
Разработанный алгоритм был положен в основу системы репликации на базе хэш-функций. В отличие от других алгоритмов синхронизации баз данных предлагаемый алгоритм позволяет приводить базы в синхронизированное состояние во время первого же сеанса репликации, несмотря на то, были ли внесены какие-либо изменения в данные на узле получателе. При этом данный алгоритм расходует сетевой трафик эффективнее, чем другие алгоритмы синхронизации без сохранения состояния, поскольку производит сравнение не самих участков таблицы, а лишь их хэш-значений.
В результате внедрения (см. Приложение 1) одной из вариаций данного алгоритма в Федеральном агентстве по техническому регулированию и метрологии в рамках проекта АИС «Метрконтроль» была получена возможность производить автоматическое восстановление состояния глобальных справочников на удаленных узлах и предотвращение распространения некорректных данных далее по всей филиальной сети.
Программа была зарегистрирована в реестре программ для ЭВМ, свидетельство № 2006613419 (см. Приложение 3).
Достоверность полученных результатов подтверждена опытом эксплуатации программы в Федеральном агентстве по техническому
регулированию и метрологии и полученными положительными результатами работы.
Апробация. Результаты диссертации прошли апробацию на научных конференциях: Международные научно-практические конференции «Телематика», г. Санкт-Петербург, 2005, 2006, 2007 г.г.; The international workshop on Computer Science and Information Technologies, September 19-21, Ufa, 2005; ежегодной научно-технической конференции профессорско-преподавательского состава МГУЛ, 2006; XIV Международная студенческая школа-семинар, МГИЭМ, 2006; Всероссийская научно-практическая конференция «Математика, информатика, естествознание в экономике и обществе -2006», МФЮА, Москва; VIII Всероссийская научно-техническая конференция «Теоретические и прикладные вопросы современных информационных технологий». Улан-Удэ: 2007. Работа была удостоена диплома 1-й степени на Всероссийском конкурсе инновационных проектов аспирантов и студентов 2006 (см. Приложение 2).
Публикации. Результаты диссертации изложены в 10 печатных работах (2 работы опубликованы в изданиях, рекомендованных ВАК для защиты докторских и кандидатских диссертаций), в том числе в 2 статьях и 7 сборниках материалов, трудов и тезисов Международных и Всероссийских конференций.
Различие систем репликации по принципу установления соединения
Системы репликации можно классифицировать по различным признакам. Одним из таких признаков, как показано в [98], является принцип установления соединения:
Системы с очередью сообщений накапливают изменения в виде сообщений, которые передаются в порядке «первый пришел первый ушел» в момент сеанса репликации на удаленный узел. Средой передачи данных могут быть как некоторая сеть передачи данных, так и email, ftp и т.п. Такой способ передачи чем-то похож на взаимодействие между компьютерами в Интернете при помощи дейтаграмм (UDP). Изменения, передаваемые при репликации, могут накапливаться либо в виде снимков данных, либо напрямую в журнале транзакций (т.е. для накопления изменений не требуется никаких специальных средств для формирования этого списка). Проанализируем достоинства и недостатки этого метода. Достоинства:
1. Отсутствие интенсивных вычислений в момент передачи, процесс захвата изменений равномерно распределен по всему времени редактирования базы данных.
2. Отсутствие необходимости интенсивного двунаправленного обмена данными и как следствие -простота реализации. Один узел отправляет сообщения, а другой производит их анализ.
Недостатки:
1. Возможное разрастание этой очереди сообщений, вплоть до превышения ею размера исходной таблицы. Даже в том случае, если в базе хранятся только итоговые изменения данных между сеансами репликации, объем памяти, занимаемый захваченными изменениями, будет, как минимум, совпадать с объемом отслеживаемых данных. Если же система опирается на журнал транзакций, то, во-первых, это не избавляет от интенсивного использования ресурсов системы, но также вводит дополнительную проблему.
Очистка журнала транзакций является рутинной операцией по улучшению производительности системы. Однако в случае такого действия все изменения будут потеряны. Таким образом, все работающие с базой люди должны быть поставлены в известность о категорическом запрете таких действий. 2. Наличие проблемы восстановления удаленной копии после сбоя. Т.е. в случае, если изменения были переданы на удаленный узел, а потом на этом узле произошел сбой, то нет никакой возможности автоматически восстановить идентичность баз. Для того чтобы это было возможно, необходимо сохранять все изменения уже после их отправки с самого начала осуществления репликации между узлами. Это, как правило, невозможно по соображениям затрат ресурсов.
Системы с установлением соединения ориентированы на тесное взаимодействие между узлами в процессе репликации. Этот способ, по сути, похож на протокол TCP [81], используемый в сети Интернет. То есть, собственно до момента окончания обмена данными происходит многократный обмен различной информацией. Рассмотрим этот способ передачи данных подробнее. Достоинства:
1. Значительное сокращение затрат на хранение служебной информации. При таком подходе не происходит накопление данных об изменениях, так как всегда сравниваются существующие версии данных. Отметим, что это преимущество сходит на нет, если синхронизируются таблицы, для которых одним из требований является ведение истории изменений.
2. Не требуется модификации существующей базы данных, по крайней мере, не меняются существующие таблицы.
3. Не требуется постоянное присутствие администратора базы данных и контроль системы накопления изменений. Если проблемы и возникают, то только в строго определенные моменты, при этом восстановление системы (приведение системы в синхронное состояние) происходит быстро и без особых затрат.
Алгоритм вычисления хэш-функции MD5
Для примера, рассмотрим механизм вычисления хэш-значения при помощи функции MD5. Алгоритм MD5 вычисляет 128 битное хэш-значение для входных данных произвольной длинны. Блок входных данных модифицируется следующим образом: 1. К блоку справа дописывается единица; 2. К блоку справа дописывается столько нулевых битов, чтобы длина данных результирующего блока данных по модулю 512 стала равна 448; 3. К блоку справа дописывается 64 битное представление количества бит в блоке входных данных. Если длина входного блока не может быть представлена 64-битным числом, то записываются только младшие биты.
На этом этапе блок входных данных считается полностью подготовленным к вычислениям и начинается, собственно, процесс вычисления хэш-значения. В ходе вычисления алгоритм меняет четыре основных переменных: А, В, С, D, называемых также состоянием алгоритма. Эти переменные на первом шаге алгоритма инициализируются следующими константами: А = 0123 45 67; B = 89ABCDEF; C = FEDCBA98; D = 7654 3210.
Отметим, что на последнем шаге путем конкатенации значений этих переменных получается результирующее хэш-значение.
Далее, на первом шаге алгоритма инициализируется массив псевдослучайных чисел Т[1..64] следующим способом: T[i] = int(4294967296 sin(i) ). Также, на первом шаге определенным образом задается 64 элементный массив R[1..64], описывающий величину циклического сдвига на каждом шаге.
На каждом шаге алгоритм анализирует один 512-битный блок. Каждый такой блок рассматривается как последовательность из 16 32-х битных блоков данных М[і]. Для каждого такого блока выполняется шаг алгоритма MD5. Производится циклический сдвиг значений переменных состояния алгоритма: С=В; D=C; A=D;
Значение переменной В вычисляется по следующей формуле: B=(A+Fun(B,C,D)+M[i]+T[i]) «R[i]+B. В этой формуле операция « обозначает циклический сдвиг битов влево. Все операции сложения производятся по модулю 232.В качестве функции Fun по очереди выбирается одна из следующих функций: F(X,Y,Z)=(XANDY)OR(NOTXANDZ); G(X,Y,Z)=(XANDZ)OR(YANDNOTZ); H(X,Y,Z)=XXORYXORZ; I(X,Y,Z)=Y XOR (X OR NOT Z).
В приведенных выше функциях XOR обозначает булевскую функцию исключающее ИЛИ. AND обозначает булевскую функцию И. OR обозначает булевскую операцию ИЛИ. NOT обозначает булевскую операцию ОТРИЦАНИЕ.
Отметим, что, несмотря на найденные уязвимости в алгоритме MD5, он до сих пор остается достаточно эффективным для обнаружения малейших различий во входных сообщениях. В качестве примера можно привести, как малейшее изменение входных данных влечет за собой получение абсолютно иного хэш-значения: MD5("The quick brown fox jumps over the lazy dog") = 9el07d9d372bb6826bd81d3542a419d6; MD5("The quick brown fox jumps over the lazy eog") = ffd93fl6876049265fbaef4da268dd0e.
Целевые функции
Отметим, что далее во всех формулах квадратные скобки Г 1 обозначают операцию округления вверх до ближайшего целого -операция Ceiling: [О] = 0,[0,3] = 1,[0,5] = l,[l] = 1.
Для рассматриваемого алгоритма можно выделить две целевых функции. 1. В случае, если стоит цель максимально сократить финансовые затраты, то можно построить функцию цели, отражающую финансовые затраты на проведение сеанса синхронизации. Получаем следующую функцию: Е -Е +Е +Е
Суммарное Обнаружения Передачи Обновления Для упрощения можно предположить тот факт, что собственно вычисления не ведут к какому-либо существенному увеличению затрат. Это происходит по той причине, что затраты на работу серверов не зависят от того, производит ли сервер расчеты или простаивает. Таким образом, функция финансовых затрат вырождается в затраты на
Передачу даННЫХ: ЕСуммарте=ЕПередачи В ЭТ0М СЛУЧйЄ М0ЖН0 ПРЯМ0 перейти от финансовых единиц измерения к единицам измерения объема информации: УСулшарное=УПереда оачи
Объем переданных данных можно выразить как объем переданной служебной информации и собственно объем переданных данных: УПередачи = УСлужебной + УДанных. Доля измененных данных С2, начальное количество данных Cv Получаем суммарно измененных данных Cj С2. Для того, чтобы передать эти измененные данные на С С Ч zz X, интервалов минимального удаленный узел необходимо размера. Т.к. для передачи данных при помощи указанного алгоритма невозможно использовать дробное число интервалов, то в итоге будет передано С С X, интервалов минимального размера Х2. Получаем, что в итоге на передачу данных будет потрачено: V Данных С с X, х2.
Количество итераций, которые необходимо провести для локализации изменения зависит от выбранного алгоритма измельчения интервалов, начального размера интервалов и минимального размера интервала. На каждом шаге алгоритма интервал делится на С5 частей.
Таким образом, на протяжении / шагов размер рассматриваемого интервала уменьшится до —К. Алгоритм прекратит производить дальнейшее измельчение интервалов, когда размер одного интервала станет равен минимальному размеру интервала, т.е. когда выполнится равенство —1— = Х2. Выражая /из этого равенства, получаем N х. z = logc -rr- = log(: Xj-logc Х2. Получаем, что алгоритм за все 5 Л. 5 время произведет k gc -logcX2 итерации. На каждом шаге необходимо произвести передачу некоторого количества хэш-значений, которое зависит от номера итерации /, начального размера интервалов, начального объема данных, части измененных записей и собственно алгоритма измельчения интервалов. Отметим, что на первом шаге алгоритм анализирует всю таблицу
С, целиком, т.е. анализируется - - интервалов. В силу того, что число х\ интервалов должно быть целым, производится округление вверх до ближайшего целого. Получаем, что на первом шаге алгоритм рассматривается интервалов. На каждом последующем шаге алгоритма количество рассматриваемых интервалов, в силу применения методов измельчения, увеличивается в С5 раз. Получаем, что на втором шаге алгоритма будет проанализировано количество интервалов начального размера, необходимых для покрытия с с измененных данных
Архитектура системы и обзор составляющих классов
В сборку Common были включены классы, используемые и на клиенте и на сервере. Во-первых, это класс Interval. Этот класс описывает область данных в таблице. Этот класс является фундаментальным для всей системы, т.к. именно с ним производятся все основные операции описанного алгоритма. Класс Interval характеризуется начальной строкой интервала, количеством строк, начальной колонкой интервалом и количеством колонок.
Следующим важным компонентом этой сборки является интерфейс IDataProvider. Этот интерфейс определяет то, какие методы должны реализовывать классы, отвечающие за доступ к конкретной базе данных. Такой подход позволяет абстрагироваться от конкретного диалекта языка SQL, характерного именно для данной, конкретной СУБД, и сосредоточиться на функциях доступа к базе данных, важных самому приложению. Интерфейс IDataProvider определяет, что реализующие его классы должны уметь: определять размерность таблицы, с которой они работают; определять схему таблицы, с которой они работают; выявлять множества общих сущностей в таблице; обновлять данные на заданном интервале.
Заметим, что классом, реализующим интерфейс IDataProvider, является класс SqlDataProvider. Этот класс реализует все описанные методы и предназначен для работы с базами семейства Microsoft SQL Server.
Следующим важным классом является класс Hasher. Этот класс позволяет единообразно как на узле-получателе, так и на узле-источнике, вычислять хэш-значения на заданном интервале при помощи заданного алгоритма хэширования, используя для доступа к данным заданньщ произвольный провайдер доступа к данным (который в свою очередь реализует интерфейс IDataProvider).
В сборке ClientReplication существуют всего два класса. Класс Program содержит в себе точку входа в систему, и отвечает за разбор параметров, инициализацию сетевого соединения и инициализацию собственно механизма репликации.
Класс ReplicationEngine представляет собой основной механизм системы репликации на узле-получателе. Этот класс отвечает за обнаружение общих сущностей на узле получателе (для этого используются соответствующие методы интерфейса IDataProvider). Также этот класс обрабатывает получение хэш-значений интервалов с сервера, отправку серверу соответствующих хэш-значений интервалов клиента, получение с сервера обновленных данных и обновление локальной базы, а также завершение сеанса репликации по команде разрыва соединения полученной с сервера.
Сборка ServerReplication содержит в себе всю логику, относящуюся к функционированию сервера репликации на узле-источнике. Точкой входа в сборку, как и в клиентской версии, служит класс Program. Этот класс отвечает за инициализацию всей системы, настройку соответствующих параметров, и в частности определение того, на каком порту будет ожидаться подключение клиента.
Класс ReplicationEngine отвечает за функционирование основного механизма репликации на сервере. В нем реализована функциональность обнаружения общих сущностей на узле источнике и на узле получателе, механизм пересылки хэш-значений интервалов на клиент и получение соответствующих значений от клиента. Кроме этого именно в этом классе применяются различные алгоритмы измельчения интервалов на подинтервалы.
Это делается за счет классов, реализующих интерфейс IlntervalSplitStrategy. Этот интерфейс требует от реализующих его классов следующей функциональности: установка схемы таблицы, с которой работает данный алгоритм измельчения; установка начального размера интервала, на который разбивается таблица на первом шаге; установка минимального размера интервала, при достижении которого измельчение больше не будет производиться и интервал будет признан измененным; проверка интервала на минимальный размер (необходимо тем стратегиям измельчения, которые не используют абсолютную величину для определения минимального значения, а определяют его динамически);
