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

На правах рукописи

Рябков Николай Сергеевич -

АЛГОРИТМЫ СИНХРОНИЗАЦИИ ДАННЫХ БЕЗ СОХРАНЕНИЯ СОСТОЯНИЯ

Специальность 05 13 11 - Математическое обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

□ ОЗ 174608

Москва - 2007

003174608

Работа выполнена в Российском государственном университете нефти и газа им. И М. Губкина

Научный руководитель - доктор технических наук, профессор Ретинская Ирина Владимировна

Официальные оппоненты - доктор технических наук, доцент

Ирина Гургеновна Игнатова

- кандидат технических наук, доцент Кривошеее Анатолий Олегович

Ведущая организация - Московский государственный институт электроники и математики

Защита состоится «06» ноября 2007 г в 15 часов 30 минут в ауд 308 на заседании диссертационного совета Д 212 200 14 при Российском государственном университете нефти и газа им И М Губкина, по адресу 119991, г Москва, Ленинский проспект, 65

С диссертацией можно ознакомиться в библиотеке Российского государсгвенного университета нефти и газа им ИМ Губкина

Автореферат разослан «оЧу> Ю 2007г

Ученый секретарь

диссертационного совета Д 212 200 14, д т

А В Егоров

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

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

Учеными из исследовательского центра корпорации NEC (Khrabrov А, Sobti S, Yianilos P N) был предложен алгоритм, позволяющий сократить затраты трафика в системах без сохранения состояния Этот алгоритм является, в некотором смысле, адаптацией

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

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

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

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

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

• разработан алгоритм синхронизации баз данных без сохранения состояния на основе механизма хэш-функций,

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

• построена и исследована математическая модель предложенного алгоритма, позволяющая производить эффективную настройку алгоритма,

• пред ложенные алгоритмы реализованы в виде программных средств

Методы исследования. Для решения поставленных задач использовались методы теории вероятностей, теоретической криптографии, теории оптимизации и математической статистики Для программной реализации использован язык программирования С#, программная среда Microsoft NET Framework 20 и сервер баз данных Microsoft SQL Server Express 2005

На защиту выносятся:

1 Алгоритм синхронизации баз данных без сохранения состояния на основе хэш-функций, позволивший более эффективно локализовать область измененных данных

2 Три алгоритма измельчения интервалов, позволяющие эффективно учитывал, особенности и неоднородности в синхронизируемых данных

3 Математическая модель рассматриваемого алгоритма, позволяющая производить максимально точную настройку алгоритма под конкретные условия использования

Научная новизна диссертационной работы определяется следующими результатами

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

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

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

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

В результате внедрения одной из вариаций данного алгоритма в Федеральном агентстве по техническому регулированию и метрологии в рамках проекта АИС «Метрконтроль» была получена возможность производить автоматическое восстановление состояния глобальных справочников на удаленных узлах и предотвращение распространения некорректных данных далее по всей филиальной сети

Программа была зарегистрирована в реестре программ для ЭВМ, свидетельство № 2006613419

Достоверность полученных результатов подтверждается строгостью использования математического аппарата и опытом эксплуатации программы в Федеральном агентстве по техническому регулированию и метрологии

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

• Федеральное агентство по техническому регулирования и метрологии -подсистема репликации АИС «Метрконтроль»

• Российский Государственный Университет им И М Губкина - при чтении курсов «Методы обработки экспериментальных данных и планирование экспериментов» и «Компьютерное моделирование»

Апробация Результаты диссертации прошли апробацию на научных конференциях Международные научно-практические конференции «Телематика», г Санкт-Петербург, 2005, 2006 г г, The international workshop on Computer Science and Information Technologies, September 19-21, Ufa, 2005, ежегодной научно-технической конференции профессорско-преподавательского состава МГУЛ, 2006, XIV Международная студенческая школа-семинар, МГИЭМ, 2006, Всероссийская научно-практическая конференция «Математика, информатика, естествознание в экономике и обществе - 2006», МФЮА, Москва

Работа была удостоена диплома 1-й степени на Всероссийском конкурсе инновационных проектов аспирантов и студентов 2006 года

б

Публикации Результаты диссертации изложены в 10 печатных работах, в том числе в 2 статьях в изданиях, рекомендованных ВАК для защиты докторских и кандидатских диссертаций и 7 сборниках материалов, трудов и тезисов Международных и Всероссийских конференций

Структура и объем работы Диссертационная работа состоит из введения, четырех глав, разбитых на разделы, и заключения Работа содержит 125 страниц, включая 1 таблицу, 13 рисунков Список литературы содержит 101 наименование

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении обоснована актуальность темы, изложены цели и задачи исследования Определены научная новизна и практическое значение полученных результатов Обоснована структура диссертации, приведены основные положения, выносимые на защиту

В первой главе рассматриваются существующие технологии построения сложных информационных систем и алгоритмы систем репликации Системы репликации условно разделяются на два класса системы с сохранением состояния и системы без сохранения состояния Рассмотрены основные характеристики, особенности и недостатки каждого из существующих подходов к организации репликации данных Основным недостатком систем с сохранением состояния является тот факт, что в таких системах восстановление после сбоя (после изменения данных на удаленном узле) достаточно затруднительно Для систем с сохранением состояния встает другая проблема - слишком больших расходов трафика Приводится обоснование необходимости создания алгоритма, устраняющего оба эти недостатка

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

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

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

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

функции возвращающей 128-битное хэш-значение для обнаружения

по следующей формуле

Для идеальной хэш-

коллизии с вероятностью 10 12 необходимо перебрать 2,6x1с)13 возможных входных значений

Хэш-функции используются в критически важных с точки зрения безопасности приложениях, в связи с чем, с момента появления нового алгоритма вычисления хэш-функции начинаются поиски уязвимостей в этом алгоритме Алгоритм считается уязвимым, если предложен способ, позволяющий получить коллизию, не прибегая к полному перебору Как известно, срок жизни (до момента обнаружения серьезной уязвимости) у алгоритмов хэширования в среднем варьируется от 3-х до 12 лет Дальнейшее использование уязвимых алгоритмов хэширования необходимо проводить с большой осторожностью

( Начало )

Ра1би«ни«

Вычисление

Нет

Рис 1 Блок-схема работы алгоритма

В связи С этим, в диссертации рассмотрен вопрос о возможности применения таких

алгоритмов для

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

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

Блок-схема предлагаемого алгоритма приведена на Рис 1 Отметим, что предусловием для использования предлагаемого алгоритма является знание о множестве общих сущностей на узле-источнике и на узле-получателе В случае если для идентификации записей используется

последовательная нумерация, то для обнаружения лишних записей на узле-получателе и новых записей на узле-источнике можно применить анализ соответствующих непрерывных интервалов Код для этого анализа может быть написан напрямую на языке запросов к базе (SQL) Для новых записей на узле-источнике операция, которую необходимо произвести, заранее известна - это вставка На узле-получателе операция также известна - это удаление

1 На первом шаге исходное множество общих сущностей узла-источника и узла-получателя разбивается на некоторые области (интервалы) Интервал может состоять из произвольного числа столбцов и произвольного числа строк. В предельном случае интервалом называется одна ячейка таблицы Координаты и размеры интервалов известны на узле источнике и на узле получателе Начальный размер интервала является параметром алгоритма и выбирается в соответствии с конкретными условиями использования системы

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

3 Полученные хэш-значения для каждого интервата сравниваются Т к для того, чтобы сравнить хэш-значения, необходимо провести их передачу по сети, то и на данном этапе от выбранного алгоритма хэширования, а точнее от размера хэш-значений напрямую зависит производительность системы Если хэш-значения совпадают, то интервалы признаются равными и алгоритм для этих интервалов заканчивается

4 Если в пункте 3 хэш-значения интервала не совпали, то производится проверка, является ли рассматриваемый интервал интервалом минимального размера Интервал может быть идентифицирован как интервал минимального размера несколькими способами Минимальный

ю

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

5 Если рассматриваемый интервал является интервалом минимального размера, то интервал признается различающимся на узле-источнике и на узле-получателе Производится передача этого интервала на удаленный узел и алгоритм для него заканчивается

6 Если интервал не является интервалом минимального размера, то некоторым способом производится измельчение этого интервала на подшггервалы, и алгоритм продолжается уже для измельченного множества интервалов, начиная с пункта 2

В пункте 6 указанного алгоритма производится измельчение интервалов на подшггервалы, при этом способ измельчения в самом алгоритме не указан Дело в том, что от того, каким именно образом на каждом шаге будут измельчаться интервалы на подинтервалы, зависит эффективность анализа системой особенностей и неоднородностей реплицируемых данных Фактически предлагается не алгоритм репликации данных, а некоторое семейство алгоритмов При этом способ измельчения интервалов можно менять произвольным образом не только в момент внедрения, но и после его Новые модули с алгоритмами измельчения интервалов могут быть написаны на основании некоторого опыта, полученного в процессе эксплуатации системы Такой подход, а именно

вынесение части алгоритма в отдельные взаимозаменяемые модули, известен специалистам в области объектно-ориентированного проектирования как паттерн или шаблон проектирования «Стратегия».

Далее рассмотрены простейшие алгоритмы, которые могут быть реализованы при таком подходе:

1. Метод деления отрезка пополам является хорошо известным и успешно применяется для решения многих алгоритмических задач. В данном случае интервал, в котором предположительно находятся изменения, делится на две части, после чего процесс повторяется для каждой из полученных частей. На Рис. 2 приведен пример работы такого алгоритма. Штриховкой показана область, для которой хэш-значения не совпали. Заметим также, что на каждом шаге деление может производиться как по вертикали, так и по горизонтали. В простейшем случае можно просто чередовать направление измельчения интервала.

2. Метод отслеживания истории изменений позволяет учитывать тот факт, что в реальности у многих таблиц существуют часто и редко меняющиеся области. Наиболее применимо это к колонкам таблицы. Например, цена товара может меняться часто, а его артикул или наименование редко или вообще никогда. В этом случае производится отслеживание частоты изменений той или иной области таблицы. Этот процесс показан на Рис. 2, где более сильной штриховкой обозначены области, которые чаще меняются. Идея такой стратегии измельчения состоит в отделении часто

д.

£

Деление История Настройка отрезка изменений экспертом пополам

Рис. 2 Способы измельчения интервалов

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

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

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

В третьей главе разработана и исследована оптимизационная модель алгоритма Дтя настройки алгоритма предлагается минимизировать целевую функцию параметров работы алгоритма

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

• С, (байт) - количество данных в таблице, 1 < С^ £ 5 000.000 000,

• С2 - доля измененных записей в таблице, 0 £ С2 £ 1,

• С3 (байт/с) - скорость передачи данных по сети, 0 £ С3 £ 1 000.000,

• С4 (байт/с) - скорость обновления данных - рассчитывается исходя из конкретных условий внедрения системы

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

• С5 - количество частей, на которые алгоритм измельчения разбивает интервал, 2 £ С5 £10

Предлагаемый алгоритм может использовать различные способы вычисления хэш-значения (на практике будут рассматриваться 6 возможных хэш-функций, наиболее часто включаемых в современные криптографические библиотеки) Для настройки алгоритма указывается множество хэш-функций АХэш, упорядоченное от наименее надежной функции к максимально надежной \хэш А„Хэш Соответственно перед началом оптимизации указывается

• С6 - минимально допустимый номер хэш-функции в множестве АХзш Выбирается исходя из необходимых требований к надежности алгоритма, 1£Сб=г6

Для каждой хэш-функции из описанного множества указываются следующие константы

• С7 (./V) (байг/с) - скорость обнаружения изменений в таблице, где N номер

хэш-функции, - получается исходя из конкретных условий внедрения системы,

• С8(Лг)(байт) - размер хэш-значения, где N номер хэш-функции, 64 2 С8 £512

Рассмотрим искомые параметры рассматриваемого алгоритма.

• Xj (байт) - принимает натуральные значения, наложены следующие ограничения 1 £ Хг <, Cj Обозначает начальные размеры интервалов, на которые разбивается таблица,

• Х2(байт) - принимает натуральные значения, наложены следующие ограничения 1 < Х2 £ Хг Обозначает минимальный размер интервала,

• Х3 - принимает натуральные значения, наложены следующие ограничения С6 s Х3 < п

Отметим, что далее во всех формулах квадратные скобки [| обозначают операцию округления вверх до ближайшего целого - операция Ceding [0] = 0, [0,3] = 1, [0,5] = 1, [1] = 1

Для рассматриваемого алгоритма можно выделить две целевых функции

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

ЕСу>шарнсе=ЕОбнаружения + ЕПередачи +ЕОбновления Д®1 УПрОЩеШМ МОЖНО

учесть тот факт, что собственно вычисления не ведут к какому-либо существенному увеличению затрат Это происходит по той причине, что затраты на работу серверов не зависят от того, производит ли сервер расчеты или простаивает Таким образом, функция финансовых затрат вырождается в затраты на передачу данных ЕСушшриое = ЕПередти В этом случае можно

прямо перейти от финансовых единиц измерения к единицам измерения объема информации УСуммар,юе=УШредти Объем переданных данных

можно выразить как объем переданной служебной информации и собственно объем переданных данных УШра)ачи =УСяужебной +УДшшых В общем

случае в итоге на передачу данных будет потрачено * Х2 Количество итераций, которые необходимо

Данных '

С *с

провести для локализации изменения, зависит от выбранного алгоритма измельчения интервалов, начального размера интервалов и минимального

На каждом шаге необходимо

размера интервала |1°§с5 - 1°8с5

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

Отметим, что на первом шаге алгоритм

интервалов

сг*с2*{с5)"

анализирует таблицу целиком Таким образом, получаем объем переданной служебной информации

VСлужебной

■2

д*с2*(с5 у

«-1

В итоге получаем задачу оптимизации

тт(РПередачи)^

А хЛ

Ъ=2

д*с2*(с5)("1}

я

ч

2 В случае же, если стоит цель минимизировать время сеанса репликации, то строится функция, отражающая затраты времени на проведение сеанса передачи данных

Т =т +т +т

Суммарное Обнаружения Передачи Обновления

Тпередачи можно вычислить, если известна из начальных условий скорость передачи данных ТПередачи=УПередти/С3 Время обновления можно получить по следующей формуле

Обновления

^Обновления = *С2)/С4 Время обнаружения изменений зависит от количества хэш-значений, подлежащих анализу на каждом шаге и от размера данных, для которых формируется хэш-значение

-1)

С\*С2*(С5У

X,

(С5)

1-1

Здесь также необходимо учесть хэш-

значения, сгенерированные при первичном анализе таблицы Получаем время обнаружения

Обнаруж

/Од)

С1*С2*(С5)Н'1

<-1

В итоге получаем задачу оптимизации т1П(^суЛшарное)' где

{Сх + Х1 *

2/1-2

С,*С2*(С5)'

-I

*1г \Н

/С7(Х3)+

слх3у

г *с

Ч 2

X,

С,

*X,

, [108с5 *Г108С.

,1-2

С^С2*(С5)

X,

/с,+

с *с

Ч 2

2

Х2/С4,

Остальные константы могут принимать те же значения, что и в первом случае.

В частности в случае, если для рассматриваемого набора возможных алгоритмов хэширования верно, что менее надежные функции всегда вычисляются быстрее, чем более надежные, то для модели всегда будет выгодно выбрать минимально допустимый с точки зрения надежности хэш-алгоритм. В этом случае параметр ХЗ фактически исключается из рассмотрения. В этом случае получаем, что функция Б зависит от двух переменных. На Рис. 3 приведен пример графика этой функции для следующих значений: С 1=2000000000, С2=0.001, С3=128000, С4= 100000000, С5=2, С6=1, С7=10000000, С8=64. Выброс ближе к началу координат происходит по той причине, что при уменьшении начального размера интервала происходит резкое увеличение количества хэш-значений (а значит и количества служебных данных), которые необходимо передать на первом шаге. Если рассматривать участок функции для XI принимает значения в интервале 80 000-5 000 000, то она имеет вид, как показано на Рис. 4. Как видно из рисунка, функция имеет сильно ломаный вид. Это связано с использованием функции округления вверх до ближайшего целого. Вблизи оси XI функция меняется незначительно. По мере удаления от оси XI колебания функции приобретают все более существенный характер. При этом необходимо учесть тот факт, что график приведен для совершенно определенных значений констант. В действительности эти оценки будут во многом приблизительны. В связи с этим предпочтительным видится поиск некоторой области, в которой функция будет принимать достаточно малые значения. В этом смысле наиболее подходящими кажутся области около оси XI, где колебания функции не яшмются столь существенными.

Рис. 3 Общий вид функции

Рис.-

Детализированный вид

Полученная модель является задачей дискретного программирования с нелинейной целевой функцией Отметим, что поиск оптимального решения в этом случае достаточно затруднителен, т к целевая функция многоэкстремальная Для поиска оптимальных значений описанной модели были исследованы различные методы оптимизации Задача решалась одним из вариантов метода генетических алгоритмов При таком способе решения каждый параметр некоторым способом кодировался (наиболее распространенной является последовательность нулей и единиц) Совокупность чисел, описывающих параметры алгоритма, являлась решением задачи минимизации целевой функции Метод генетических алгоритмов работал следующим образом

1 Формируется некоторое начальное множество возможных решений

2 На основании этого множества формируется множество новых решений (путем случайного изменения существующих решений, а также склеивания или вставки частей существующих решений)

3 Решети ранжируются по значению целевой функции После этого по некоторому алгоритму наименее эффективные решения отсеиваются Происходит переход на шаг 2

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

Далее в этой главе приводятся примеры расчетов данной модели для различных значений констант

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

составляющих программного средства и особенностей работы с ними. Пример работы

программы приведен на Рис. 5.

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

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

ЗАКЛЮЧЕНИЕ

Основные результаты работы состоят в следующем:

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

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

Сервер репликации элпуиен Открыт порт: 3334 Клиент репликации запуидн

Подключение к серверу успеино: 12?.0.0.1:3334 Подключение клиента: 127.0.0.1:4455 Процесс клиентской репликации запдоюн Процесс серверной репликации залучен

Начальные размеры таблицы: Интервал:: начальный идентификатор: 1, • , начальный номер колонки 0, конечный номер к Получено 1 локальных непрерывных интервалов Получено 1 непрерывных интервалов г. сервера Получено 1 оке1их непрерывных интервалов Получено 0 строк данных

Найден различающийся интервал: Интервал:: начальный » к 2„ начальный номер колонки конечный номер колонки я Найден различающийся интервал: Интервал:: начальный идентификатор: 5. 1 н 2, начальный номер колонки Й, конечный номер колонки 3 Найден различавшийся интервал: Итере**:: начальный ицпшмФииатор: 95, ок 2, начальный номер колонки 0, конечный номер колонки 3 Найден различающийся интервал: Интервал:: начальный идентификатор: 9?, чмелп сгрН ок 2„ начальный номер колонки 0. конечный номер колонки 3

Найден интервал минимального размера: Ннтервол:: начальный идентификатор: 3, ло строк 2, начальный номер колонки 0, конечный номер колонки й. Производит» >есылка на удаленный узел.

Рис. 5 Пример работы программы

3 Разработана и исследована различными методами модель алгоритма, позволяющая, исходя из некоторых известных характеристик аппаратно-программного обеспечения, на котором будет производиться внедрение, подобрать оптимальные параметры алгоритма

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

СПИСОК ОПУБЛИКОВАННЫХ СТАТЕЙ

1 Рябков Н С Аналитический обзор методов репликации и синхронизации баз данных М Качество, инновации, образование №4,2006 С 56-63,

2 Ретинская И В, Рябков Н С Синхронизация данных с учетом неоднородности реплицируемой информации «Новые информационные технологии» М №5,2007 С 47-55

3 Ryabkov N S Database integrity support problems in distributed systems The international workshop on Computer Science and Information Technologies Ufa, 2005 pp 235-236,

4 Рябков H С , Ретинская И В Алгоритм синхронизации баз данных при помощи хэш-функций на основе нелинейного разбиения таблиц Труды XIII Всероссийской научно-методической конференции «Телематика 2006» Из-во СПб, 2006 Том 1,С 234-235,

5 Рябков Н С Новый алгоритм синхронизации баз данных при помощи хэш-функций Тезисы докладов XIV международной студенческой школы-семинара М МГИЭМ, 2006 С 312-313,

6 Рябков Н С Конкурсная работа Алгоритм синхронизации баз данных при помощи хэш-функций на основе нелинейного разбиения таблиц Сборник материалов всероссийского конкурса инновационных проектов аспирантов и студентов М ГНИИ ИТТ «Информатика», 2006 С 101-102,

7 Рябков Н С Неоднородность информации в системах репликации баз данных без сохранения состояния Сборник материалов Всероссийской

научно-практической конференции «Математика, информатика, естествознания в науке и обществе» М'МФЮА, 2006 С 59-60,

8 Рябков НС Оптимизация алгоритма синхронизации баз данных при помощи хэш-функций на основе нелинейного разбиения таблиц Сборник тезисов к VIII Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий» Улан-Удэ 2007, Ч 1, С 72-74,

9 Рябков Н С, Ретинская И В Математическая модель синхронизации баз данных при помощи хэш-функций Труды XIV Всероссийской научно-методической конференции «Телематика 2007» Из-во СПб, 2007 Том 2, С 359-360,

10 Скуратов А К, Ретинская И В , Рябков Н С О проблемах интеграции ERP и PDM - систем Труды XII Всероссийской научно-методической конференции «Телематика-2005» Из-во СПб, 2005 Том1,С 44,

Подписано в печать 7% С'')-2 ОС" Формат 60x90/16

Объем Тираж 1 СО

Заказ

119991, Москва, Ленинский просп, 65 Отдел оперативной полиграфии РГУ нефти и газа им И М Губкина

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

Введение.

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

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

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

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

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

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

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

1.5. Обоснование необходимости создания алгоритма синхронизации без сохранения состояния.

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

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

Учеными из исследовательского центра корпорации 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. Алгоритм синхронизации баз данных без сохранения состояния на основе хэш-функций, позволившие более эффективно локализовать область измененных данных.

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

3. Математическая модель рассматриваемого алгоритма, позволяющая производить максимально точную настройку алгоритма под конкретные условия использования.

Научная новизна диссертационной работы определяется следующими результатами:

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

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

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

Практическое значение результатов работы.

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

В результате внедрения (см. Приложение 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 сборниках материалов, трудов и тезисов Международных и Всероссийских конференций.

Основные результаты работы состоят в следующем.

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

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

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

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

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

6. Эффективность использования предложенных алгоритмов подтверждена опытом эксплуатации системы репликации АИС «Метрконтроль» в федеральном агентстве по техническому регулированию и метрологии. Это позволяет рекомендовать предложенный подход к дальнейшему развитию и использованию в системах репликации, где существуют повышенные требования к надежности самой системы и сохранности реплицированных данных.

Список опубликованных статей

1.Ryabkov N.S. Database integrity support problems in distributed systems. The international workshop on Computer Science and Information Technologies. Ufa, 2005. pp. 235-236;

2. Рябков H.C., Ретинская И.В. Алгоритм синхронизации баз данных при помощи хэш-функций на основе нелинейного разбиения таблиц. Труды XIII Всероссийской научно-методической конференции «Телематика 2006». Из-во СПб, 2006. Том 1, С. 234-235;

3. Рябков Н.С. Новый алгоритм синхронизации баз данных при помощи хэш-функций. Тезисы докладов XIV международной студенческой школы-семинара. М.: МГИЭМ, 2006. С. 312-313;

4. Рябков Н.С. Аналитический обзор методов репликации и синхронизации баз данных. М.: Качество, инновации, образование. №4, 2006. С. 56-63;

5. Рябков Н.С. Конкурсная работа: Алгоритм синхронизации баз данных при помощи хэш-функций на основе нелинейного разбиения таблиц. Сборник материалов всероссийского конкурса инновационных проектов аспирантов и студентов. М.:ГНИИ ИТТ «Информатика», 2006. С. 101-102;

6. Рябков Н.С. Неоднородность информации в системах репликации баз данных без сохранения состояния. Сборник материалов Всероссийской научно-практической конференции «Математика, информатика, естествознания в науке и обществе». М.: МФЮА, 2006. С.59-60;

7. Рябков Н.С. Оптимизация алгоритма синхронизации баз данных при помощи хэш-функций на основе нелинейного разбиения таблиц.

Сборник тезисов к VIII Всероссийской научно-технической конференции «Теоретические и прикладные вопросы современных информационных технологий». Улан-Удэ: 2007, Ч. 1, С. 72-74;

8. Рябков Н.С. Синхронизация данных с учетом неоднородности реплицируемой информации. «Новые информационные технологии». М: № 5,2007. С. 47-55.

9. Рябков Н.С., Ретинская И.В. Математическая модель синхронизации баз данных при помощи хэш-функций. Труды XIV Всероссийской научно-методической конференции «Телематика 2007». Из-во СПб, 2007. Том 2, С. 359-360;

10. Скуратов А.К., Ретинская И.В., Рябков Н.С. О проблемах интеграции ERP и PDM - систем. Труды XII Всероссийской научно-методической конференции «Телематика-2005». Из-во СПб, 2005. Том 1,С. 44;

Заключение

1. Вентцель Е.С. Введение в исследование операций. М: Советское радио, 1964. 392 с.

2. Беллман Р., Дрейфус С. Прикладные задачи динамического программирования/Пер. с анг. М: Наука, 1965. 460 с.

3. Вагнер Г. Основы исследования операций. T.l М: Мир, 1972. 336с.

4. Вороновский Г.К. и др. Генетические алгоритмы, искусственные нейронные сети и проблемы виртуальной реальности. Харьков: ОСНОВА, 1997.-107 с.

5. Буч г. Объектно ориентированный анализ и проектирование с примерами приложений на С++/Пер. с англ. - Спб: Бином, 1998.560 с.

6. Дьяконов В.П. Математическая система MAPLE V R3/R4/R5, М: СОЛОН, 1998.-399 с.

7. Брассар Ж. Современная криптология/пер. с англ. М.: Полимед, 1999.-176 с.

8. Горбунов-Посадов М.М. Расширяемые программы. М.: Полиптих, 1999,336 стр.

9. Дейт К. Дж. Введение в системы баз данных/Пер. с англ. М.: ИД Вильяме, 2001.- 1072 с.

10. Уилсон С.Ф., Мейплс Б., Лендгрейв Т. Принципы проектирования и разработки программного обеспечения. Учебный курс MCSD./nep. с англ. 2-е изд. испр. - М: Русская редакция, 2002. -736 с.

11. Баркер С., Создание приложений баз данных в среде Visual Basic .Net и ADO.Net : советы, рекомендации, примеры/Пер. с анг. М: Вильяме, 2003.- 560 с.

12. Маклин С., Нафтел Дж., Уильяме К., Microsoft .NET Remoting/TIep. с англ. М.: Русская редакция, 2003. - 384 с.

13. Ньюкомер Э. Веб-сервисы: XML, WSDL, SOAP и UDDI/Пер с англ. Спб.: Питер, 2003. - 256 с.

14. Стивене У. UNIX: разработка сетевых приложений/Пер. с англ. -Спб.: Питер, 2003.- 1088 с.

15. Щербаков Л.Ю., Домашев А.В. Прикладная криптография. Использование и синтез криптографических интерфейсов. М.: Русская Редакция, 2003.-416 с.

16. Белоусов В.Е. Алгоритмы репликации данных в распределенных системах обработки информации. Дис. на соискание ученой степени канд. техн. наук. Пенза, 2005.

17. Катлип Р., Медик Д. DB2: решения по интеграции/Пер с англ. -М: КУДИЦ-Образ, 2005. 320 с.

18. Лю Б, Теория и практика неопределенного программирования/Пер с англ. М: Бином, 2005. - 416 с.

19. Гладков Л.А., Курейчик В.В., Курейчик В.М., Генетические алгоритмы. М.: ФИЗМАТЛИТ, 2006. 320 с.

20. Макаров А. В., Скоробогатов С. Ю., Чеповский А. М., Common Intermediate Language и системное программирование в Microsoft. NET. М: Бином, 2006. 328 с.

21. Рутковская Д., Пилиньский М., Рутковский Л. Нейронные сети, генетические алгоритмы и нечеткие системы/Пер. с польск. -М.:Горячая линия Телеком, 2006. - 452 с.

22. Ганделрой М., Джорден Д., Чанц Д. Освоение Microsoft SQL Server 2005/Пер с англ. М: Вильяме, 2007. - 1104 с.

23. Кайт Т. Oracle для профессионалов. Архитектура, методики программирования и основные особенности версий 9i и lOg/Пер с англ. М: Вильяме, 2007. - 848 с.

24. Рихтер Д., CLR via С#. Программирование на платформе Microsoft .NET Framework 2.0 на языке С#/Пер. с англ. М.: Русская редакция, 2007. -656 с.

25. Thomas R.H., A Majority Consensus Approach to Concurrency Control for Multiple Copy Databases. ACM TODS 4 (2), June, 1979, P. 180209.

26. Golberg D., Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989. PP 432.

27. Whitley D. The GENITOR Algorithm and Selection Pressure: Why Rank-Based Allocation of Reproductive Trials is Best/Лп Proc. of the Third International Conference on Genetic Algorithms, 1989, P. 116-121.

28. Daemen J. et al, Collisions for Schnorr's Hash Function FFT-Hash/Яп Proc. of Asiacrypt'91,1991. P. 447-480.

29. Kelly J., Davis Jr. and L. A hybrid genetic algorithm for classification/Tin Proc. of the 12th International Joint Conference on Artificial Intelligence, 1991, P. 645-650.

30. Bloomer J., Power Programming with RPC. O'Reilly, 1992. PP 518.

31. Coad P. Object-Oriented Patterns. Communications of the ACM, V 35 N9,1992, pp. 152-159

32. Holland H. John. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence. MIT Press, 1992. P. 228.

33. Klein M., Windows Programmer's Guide to Dlls and Memory Management. Sams, 1992, PP 450.

34. Rivest R. RFC 1321. The MD5 message digest algorithm. IETF RFC-1321,1992.

35. Schraudolph, N. N. and Belew, R. K. Dynamic parameter encoding for genetic algorithms. Machine Learning Journal 1992, Volume 9, Number 1, P. 9-22.

36. Corcoran A. L., Wainwright R. L., A parallel island model genetic algorithm for the multiprocessor scheduling problem/Лп Proc. of the 1994 ACM symposium on Applied computing, 1994. P. 483-487.

37. Rudolpgh G. Convergence analysis of canonical genetic algorithms// In IEEE Transactions on Neural Networks., 1994. Vol. 5. P. 96-101.

38. Brin S., Davis J. and Garcia-Molina H. Copy detection mechanisms for digital documents//In Proc. of the 1995 ACM SIGMOD International Conference on Management of Data. P. 398-409.

39. Gamma E. et al. Design Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Professional, 1995. PP. 465.

40. Gunter D., Client/Server Programming With RPC and DCE. Que, 1995. PP-756.

41. FIPS 180-1, Secure hash standard, NIST, US Department of Commerce, Washington D. C., 1995.

42. Metzger P. and Simpson W., IP Authentication using Keyed MD5. IETF Network Working Group, RFC 1828, August 1995.

43. Preneel B.and van Oorschot P., MD-x MAC and building fast MACs from hash functions// In Proc. of Crypto 95,1995. pp. 1.

44. Bellare M., Canetti R. and Krawczyk H. Keying Hash Functions for Message Authentication/An Proc. of CRYPTO 1996. P. 1-15.

45. Krishnamoorthy C.S., Rajeev S. Artificial Intelligence and Expert Systems for Engineers. CRC, 1996. PP. 297.

46. Tridgell A., Mackerras P. The RSYNC Algorithm/Technical Report TR-CS-96-05, Department of Computer Science, The Australian National University, Canberra, Australia, 1996.

47. Dobbertin H. RIPEMD with Two-Round Compress Function is Not Collision-Free/Journal of Ciyptology 10:1,1997. P. 51-70.

48. Renzel K. and Keller W. Client/Server Architectures for Business Information Systems, PloP'1997 Tech Report.

49. Renzel К. and Keller W. Three Layer Architecture. Software Architectures and Design Patterns in Business Applications, Technical Report TUM-I9746,1997.

50. Rogerson D., Inside Com. Microsoft Press, 1997. PP 376.

51. Brown C. et al., Effective COM: 50 Ways to Improve Your COM and MTS-based Applications. Addison-Wesley Professional, 1998. PP 222.

52. Chung P.E. et al, DCOM and CORBA Side by Side, Step By Step, and Layer by Layer/C++Report Magazine, 1998, 1 (Jan.), P. 18-29.

53. Mitchell M. An Introduction to Genetic Algorithms, MIT Press, 1998. PP.-221.

54. Abernethy R. et al., COM/DCOM Unleashed. Sams Publishing, 1999. PP 700.

55. Cho J., Garcia-Molina H. Synchronizing a database to improve freshness// In Proc. of SIGMOD conf. May 2000. P. 117-128.

56. Khrabrov A., Sobti S., Yianilos P. N. Synchronizable Databases for the Web/Tech. Rep., NEC Research Institute, 4 Independence Way, Princeton, NJ, December 2000.

57. Levine J., Linkers and Loaders. Morgan Kaufmann, 2000. PP 256.

58. Stone J., Partridge C. When the CRC and TCP checksum disagree//In Proc. of the 2000 ACM SIGCOMM conf., 2000. P. 309-313.

59. Tridgell A., Efficient Algorithms for Sorting and Synchronization. PhD Thesis, April 2000.

60. Baneijee A. et al, Professional C# Web Services: Building .NET Web Services with ASP.NET and .NET Remoting. Wrox Press, 2001. PP 550.

61. Garvan F., The MAPLE Book. Chapman & Hall, 2001. PP 496.

62. Muthitacharoen A., Chen В., Mazieres D. A low-bandwidth network file system// In Proc. XVIII ACM symposium on Operating systems principles, 2001. P. 174-187.

63. Whitley D. L., An overview of evolutionary algorithms practical issues and common pitfalMnformation & Software Technology 2001, Vol. 43, P. 817-831.

64. Cho J., Ntoulas A. Effective change detection using sampling/Technical report, UCLA Computer Science Department, 2002.

65. Fowler M. et al, Patterns of Enterprise Application Architecture, Addison Wesley, 2002, PP. 560.

66. Longshaw J., Sharp A., Microsoft Visual J# .NET (Core Reference). Microsoft Press, 2002. PP 944.

67. Ahn C.W., Ramakrishna R.S. Elitism-based compact genetic algorithms//In IEEE Transactions on Evolutionary Computation, Vol. 7, 2003. P. 367-385.

68. Heck A., Introduction to Maple. Springer, 2003. PP 848.

69. Henson V. An Analysis of Compare-by-Hash//In Proc. of the Ninth Workshop on Hot Topics in Operating Systems (HotOS IX), Lihue, HI, May 2003. P. 13-18.

70. Thorsteinson P., Ganesh G., .NET Security and Cryptography. Prentice Hall, 2003. PP 496.

71. Weisfeld M., Object-Oriented Thought Process. Sams, 2003. PP -228.

72. Bellare M. and Kohno T. Hash function balance and its impact on birthday attacks/Лп Proc. Advances in Ciyptology EUROCRYPT 2004, Lecture Notes in Computer Science, Vol. 3027 (2004). P. 401-418.

73. Henson V. Guidelines for Using Compare-by-hash. Электронный ресурс. / Электрон. дан. 2004 — Режим доступа: http://infohost.nmt.edu/~val/review/hash2.html, свободный.

74. Krafzig D., Banke К., Slama D. Enterprise SOA: Service-Oriented Architecture Best Practices. Prentice Hall, 2004. PP 408.

75. Muller F., The MD2 Hash Function Is Not One-Way//In Proc. of Asiacrypt'2004,2004. P. 214-229.

76. Wang X. et al. Collisions for Hash Functions MD4, MD5, HAVAL-128 and RIPEMD//CRYPTO 2004, Ciyptology ePrint Archive, Report 2004.

77. Gray О and van Ingen C. Empirical measurements of disk failure rates and error rates/Technical Report MSR-TR-2005-166, December 2005.

78. Henderson K., The Guru's Guide to Transact-SQL. Addison-Wesley Professional, 2005. PP 592.

79. Johnson G. Programming Microsoft ADO.NET 2.0 Applications: Advanced Topics. Microsoft Press, 2005. PP. 528.

80. Kozierok C., The TCP/IP Guide: A Comprehensive, Illustrated Internet Protocols Reference. No Starch Press, 2005. PP -1616.

81. Lin Y. et al, Middleware based Data Replication providing Snapshot Isolation//In Proc. ACM SIGMOD International Conference on Management of Data, 2005. P. 419-430.

82. Powell G. Beginning Database Design. Wrox, 2005. PP 504.

83. Overview & Comparison of Data Replication Architectures. Progress Software Whitepaper, 2005.

84. Rammer I., Szpuszta M., Advanced .NET Remoting. Apress, 2005. PP 608.

85. Xiaoyun W., Hongbo Y. How to Break MD5 and Other Hash Functions//In Proc. of EUROCRYPT 2005, P. 19-35.

86. Black J. Compare-by-Hash: a reasoned analysis/Tin Proc. USENIX Annual Technical Conference-Systems and Experience Track 2006, P. 8590.

87. Duffy J., Sharp A., Professional .NET Framework 2.0. Wrox , 2006. PP 624.

88. Hogenson G., C++/CLI: The Visual С++ Language for .NET . Apress, 2006. PP 448.

89. Marshall D. Programming Microsoft Visual C# 2005: The Language. Microsoft Press, 2006. PP. 600.

90. Northrup Т., Wildermuth S., Ryan B. MCTS Self-Paced Training Kit (Exam 70-536): Microsoft .NET Framework 2.0 Application Development Foundation. Microsoft Press, 2006. PP. 1000.

91. Rankins R. et. al., Microsoft(R) SQL Server 2005 Unleashed. Sams, 2006. PP- 1752.

92. Shan Т., Hua W. A Service-Oriented Solution Framework for Internet Banking/International Journal of Web Services Research 2006, Vol. 3, Issue 1, P. 29-48.

93. Shan Т., Hua W. Solution Architecture for N-Tier Applications/An Proc. of the 3rd IEEE International Conference on Services Computing (SCC 2006), P. 349-356.

94. Schwarz T. et al, Disk Failure Investigations at the Internet Archive/Work in Progress Report, 14th NASA Goddard 23rd IEEE Conference on Mass Storage Systems and Technologies (MSST2006), 2006.

95. Tanenbaum A., Steen M., Distributed Systems: Principles and Paradigms. Prentice Hall, 2006. PP 704.

96. Klein S., Professional WCF Programming: .NET Development with the Windows Communication Foundation. Wrox, 2007. PP 430.

97. McMurtry C., Windows Communication Foundation Unleashed. Sams, 2007. PP 720.

98. Pinheiro E., Weber W., and Barroso L. A. Failure trends in a large disk drive population/ZIn Proc. of the 5th USENIX Conference on File and Storage Technologies (FAST'07), 2007. P. 17-28.

99. Veerman E., Sarka D, Loria J. MCTS Self-Paced Training Kit (Exam 70-445): Microsoft SQL Server(TM) 2005 Business Intelligence Implementation and Maintenance. Microsoft Press, 2007. PP. 620.