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

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

«иои4239б

Аникин Николай Александрович

УПРАВЛЕНИЕ ПАРАЛЛЕЛЬНЫМ ВЫПОЛНЕНИЕМ ТРАНЗАКЦИЙ В РАСПРЕДЕЛЕННЫХ ГЕТЕРОГЕННЫХ БАЗАХ ДАННЫХ ПРИ ДОСТУПЕ ИЗ МОБИЛЬНОЙ СРЕДЫ

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

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

1 0 |'нп„ 2й12

Москва-2012

005042396

Работа выполнена на кафедре «Кибернетика»

Национального исследовательского ядерного университета «МИФИ»

Научный руководитель:

кандидат технических наук, доцент, доцент кафедры «Кибернетика» НИЯУ МИФИ Храмов Александр Александрович

Официальные оппоненты:

доктор технических наук, профессор, профессор кафедры «Экономика и менеджмент в промышленности» НИЯУ МИФИ Гусева Анна Ивановна

кандидат технических наук, доцент, доцент кафедры «Информатика и программное обеспечение вычислительных систем» МИЭТ Ашарина Ирина Владимировна

Ведущая организация:

ФГБОУ ВПО «Московский государственный горный университет»

Защита состоится « 22 »_мая_2012 г. в 10 час. на заседании

диссертационного совета Д 212.125.01 при Московском авиационном институте (национальном исследовательском университете) «МАИ» по адресу: 125993, г. Москва, А-80, ГСП-3, Волоколамское шоссе, д. 4.

С диссертацией можно ознакомиться в библиотеке МАИ.

Отзывы на автореферат в двух экземплярах, заверенные печатью, просим направлять по адресу: 125993, г. Москва, А-80, ГСП-3, Волоколамское шоссе, д. 4, Ученый совет МАИ.

Автореферат разослан « 20 » апреля_2012 г.

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

диссертационного совета Д 212.125.01 кандидат технических наук

А.В. Корнеенкова

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

За последние несколько лет также получили серьезное развитие мобильные технологии. Большое количество исследований и разработок как в области мобильных устройств (сотовые телефоны, смартфоны, карманные и переносные компьютеры), так и в области средств связи (GPRS - одна из первых технологий мобильного интернета, ее улучшенный аналог EDGE, развивающиеся в последние годы технологии Wi-Fi, Wi-MAX, 3G) позволили наделить мобильные устройства значительно большей функциональностью. Сфера применения этих технологий широка: начиная от простейших интернет-приложений для просмотра веб-страниц и электронной почты и заканчивая приложениями для электронной коммерции, интернет-банкинга, оплаты услуг.

В последние годы в науке сформировалось отдельное направление, изучающее вопросы управления гетерогенными базами данных в распределенной и одновременно мобильной среде (под «мобильной средой» подразумевается то, что доступ в систему осуществляется с мобильного устройства и, как правило, по беспроводному каналу связи). В зарубежной литературе это направление получило название MDAS - Mobile Data Access System (МСДД - мобильная система доступа к данным).

Новые технологии порождают новые вопросы и проблемы в уже, казалось бы, хорошо изученной области распределенных БД. Доступ к таким системам значительно усложняется, как только клиент БД перестает использовать постоянный, надежный и быстрый канал связи, а ресурсы устройства, с которого осуществляется доступ, становятся сильно ограниченными. Одна из основных задач, требующих решения, — управление параллельным выполнением транзакций (concurrency control) в системе МСДД. Методы, разработанные для распределенных БД, в которых и сервера, и

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

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

Цель диссертационной работы

Цель диссертационной работы состоит в решении проблемы управления параллельным выполнением транзакций на глобальном уровне в МСДД, которая объединяет несколько реляционных СУБД, использующих разные методы управления параллельным выполнением транзакций на локальном уровне.

Задачи диссертационной работы

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

1. анализ и классификация существующих решений в области систем совместного доступа к информации;

2. исследование современных методов управления параллельным выполнением транзакций в системах мульти-БД и МСДД;

3. разработка математической модели МСДД;

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

5. разработка метода и алгоритма работы глобального менеджера транзакций (concurrency-control manager), отвечающего за обеспечение сериализуемости транзакций в МСДД;

6. разработка структурной модели МСДД и реализация её прототипа;

7. реализация предложенного метода и его применение на примере мобильной платежной системы;

8. оценка эффективности метода при работе с реальными СУБД.

Методы исследования

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

Научные результаты и их новизна

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

1. разработана математическая модель МСДД, описывающая данные, транзакции и истории транзакций в системе и отличающаяся от существующих моделей тем, что учитывает особенности управления транзакциями в СУБД, использующих БпарзИо^изоляцию (изоляцию «моментальных снимков»);

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

3. предложен новый метод управления параллельным выполнением транзакций в МСДД, учитывающий специфику мобильной среды и позволяющий интегрировать любые СУБД, обеспечивающие сериализуемость локальных транзакций (без существенных нарушений их локальной автономности), и СУБД, использующие БпарзЬс^-изоляциго (с частичным нарушением автономности);

4. доказана корректность метода управления параллельным выполнением транзакций в МСДД;

5. впервые предложено решение для интеграции СУБД, обеспечивающих сериализуемость локальных транзакций, и СУБД, использующих БпарБИо^изоляцию, в мобильной среде;

6. разработана методика применения полученных теоретических результатов на практике;

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

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

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

интегрировать в рамках глобальной системы практически все используемые в широкой практике реляционные СУБД и гарантировать глобальную сериализуемость транзакций.

Разработанные программные средства были использованы при создании и внедрении системы мобильных платежей в ООО «ПС груп», что подтверждается актом о промышленном внедрении и использовании результатов диссертационной работы.

Реализация и внедрение результатов работы

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

Основные положения, выносимые на защиту:

1. математическая модель МСДД;

2. метод управления параллельным выполнением транзакций в МСДД, позволяющий интегрировать реляционные СУБД, обеспечивающие сериализуемость локальных транзакций, и СУБД, использующие БпарзИо^изоляцию;

3. структурная модель МСДД;

4. алгоритм работы глобального менеджера транзакций МСДД;

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

Апробация работы

Основные положения диссертационной работы докладывались и обсуждались на конференциях и семинарах: XIII и XIV международных телекоммуникационных конференциях студентов и молодых ученых «МОЛОДЕЖЬ И НАУКА» (Москва, 2010, 2011), девятой международной практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2010), 7-ой международной

научно-практической конференции «Интеллектуальные технологии в образовании, экономике и управлении» (Воронеж, 2010), международной научно-практической конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании '2010» (Одесса, 2010), XIX и XX международных научно-технических семинарах «Современные технологии в задачах управления, автоматики и обработки информации» (Алушта, 2011).

Публикации

По теме диссертации опубликовано 10 печатных работ: 4 статьи в журналах, включенных ВАК РФ в перечень ведущих рецензируемых научных журналов и изданий [1, 2, 3, 4], 1 статья в других журналах [5] и 5 тезисов докладов [6,7, 8,9,10].

Структура и объем работы

Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка из 128 наименований и приложений. Общий объем диссертации - 230 страниц машинописного текста, в том числе: 160 страниц основного текста и 23 страниц приложений, 39 рисунков, 17 таблиц.

СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе приведена классификация различных глобальных информационных систем в распределенной среде в зависимости от степени их распределенности, гетерогенности и автономности. Выделен отдельный класс таких систем - системы мультибаз данных (мульти-БД), объединяющие гетерогенные локальные СУБД (ЛСУБД) с сохранением их полной автономности (см. рис. 1 ниже). Более подробно рассмотрена одна из разновидностей систем мульти-БД - мобильные системы доступа к данным (МСДД), особенность которых заключается в том, что клиенты системы находятся в беспроводной сети (см. рис. 2 ниже).

Изучена задача управления параллельным выполнением транзакций (обеспечения сериализуемости глобальных транзакций) в МСДД, включающей реляционные СУБД [1]. Описаны проблемы, возникающие при обеспечении сериализуемости и атомарности глобальных транзакций и предотвращении глобальных взаимоблокировок, а также проблемы, порождаемые спецификой

мобильной среды (ограниченные ресурсы мобильных устройств - клиентов системы, непредвиденные разрывы соединения и т. д. [5]). Проведен обзор общих подходов и конкретных методов решения описанных проблем. Сделан вывод о том, что существующие методы управления параллельным выполнением транзакций в МСДЦ обладают рядом недостатков, либо не применялись на практике, либо рассматривают вопросы интеграции только тех СУБД, которые обеспечивают локальную сериализуемость, в то время как не все из них обладают этим свойством.

Рис. 1. Схема системы мульти-БД

Большинство популярных на сегодняшний день коммерческих и бесплатных СУБД используют Snapshot-изоляцию (или изоляцию «моментального снимка») для управления параллельным выполнением транзакций, которая не гарантирует локальной сериализуемости транзакций в полной мере [7]. Термин «моментальный снимок» отражает тот факт, что для каждой транзакции создается снимок (snapshot) данных на момент ее начала, и все операции чтения работают с этой копией данных. На практике это

8

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

Рис. 2. Схема МСДД (БС - базовая станция; БД - база данных)

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

В работе показана актуальность разработки нового метода управления параллельным выполнением транзакций в МСДД, учитывающего специфику мобильной среды и позволяющего интегрировать одновременно СУБД, обеспечивающие локальную сериализуемость, и СУБД, использующие БпарзЬо^изоляцию транзакций. По результатам проведенного анализа сформулированы задачи диссертационного исследования.

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

Обозначим транзакцию как Т,, некоторую операцию 0] транзакции Тп

работающую с некоторыми данным х в БД, - как О0(х). Будем предполагать,

что база данных статична, данные не добавляются и не удаляются, а только считываются операцией чтения или изменяются операцией записи, то есть Оj е {read, write}, для краткости будем обозначать эти операции как г:(х) и w,(x) соответственно. Также через Nt е {abort, commit} обозначим состояние завершения транзакции Tt, для краткости эти операции будем обозначать как а, и с, соответственно. Через OS, обозначим набор всех операций в Тп то есть,

OS, = U Оу ■ Множество данных, над которыми транзакция производит j

операции чтения, будем обозначать RS (read-set). Множество данных, над которыми транзакция производит операции записи, - WS (write-set). Объединение этих множеств — BS = RS U WS (base-set). Тогда:

Транзакция 7J - это частичный порядок Т, ={ZP -<,}, где X,- область всех операций транзакции 7] (включая состояние завершения), а -<; — нерефлексивное и транзитивное отношение, которое определяет порядок операций так, что: 1.

2. VO.eOSr. Ov*,N,\

3. VOy, eOSnVx: если 0:j = r(x) и Olk = w(x), тогда либо Оц <,Ол, либо 0,к<,0и.

Математическая модель МСДД имеет следующий вид (точные определения всех понятий даны в диссертационной работе, см. также [1]):

• МСДД: MDAS = < MDR, MFf >, где MDB = y^ LDBl - множество

данных в системе, LDB' - множество данных, хранящихся в к -ой ЛСУБД;

• История транзакций МСДД: MH = <1M,GH>, где IM = {LH\LH2,...,LH"};

• История локальных транзакций в А:-ой ЛСУБД: LHk = (£*,-<*„), где X* =ЦЕ*; -<kLH ; Z) - область операций транзакции

7}eLT*UGSTl;

• История глобальных транзакций:

GH = (ZC//> "<оя)> ГДе ' Э Uj^COT !

• История глобальных субтранзакций в ¿-ой ЛСУБД:

GSHk = akGSH,^GSH), где Scot = i <s„ 2 <„ \ I) - область операций транзакции Tj е GST*;

• Множество локальных транзакций в ¿-ой ЛСУБД: LT* , где LTk - i-ая транзакция к-ой ЛСУБД, такая что BS, с LDB';

• Множество глобальных субтранзакций в ¿-ой ЛСУБД: GST* =|J(GiSr,* > гДе GSTk - глобальная субтранзакция,

выполняющаяся в рамках /-ой глобальной транзакции в ¿-ой ЛСУБД, такая что BS/ с LDB';

• BS( - множество данных, над которыми / -ая транзакция производит операции чтения и/или записи.

В работе сформулированы критерии сериализуемости и SI-сериализуемости локальной истории транзакций (последний критерий позволяет определить правильность параллельного выполнения транзакций при использовании Snapshot-изоляции). Доказаны необходимые и достаточные условия сериализуемости истории системы мульти-БД [9]:

Теорема 1. Пусть MH = <\M.,GH> - история системы мульти-БД,

состоящей из т локальных СУБД, и LH = {LHx,...,LHm}. Для того, чтобы история МН была сериализуема необходимо и достаточно, чтобы:

1. все истории локальных транзакций \/LH е LH были сериализуемы;

2. существовал порядок выполнения глобальных транзакций О, такой, что во всех историях локальных транзакций LHk (1<к<т) глобальные субтранзакции GST* сериализуются в соответствии с порядком О.

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

обеспечения сериализуемости истории системы мульти-БД, необходимо и достаточно обеспечить (или проверить), чтобы глобальные субтранзакции были сериализованы в одном и том же порядке во всех локальных СУБД [8].

Для определения порядка сериализации транзакций в ЛСУБД различных типов предложены методы, использующие знания о локальных схемах управления параллельным выполнением транзакций. Методы основаны на следующих утверждениях, доказанных в работе.

Лемма 1. Пусть локальная СУБД использует протокол на основе временных меток (ТО - Timestamp Ordering - или MVTO - Multi-Version Timestamp Ordering) для сериализации транзакций, и Я - история локальных транзакций на множестве транзакций Т = {Т1,...,Тп}, полученная в результате использования этого протокола. Тогда Я сериализуема и порядок сериализации транзакций в Я совпадает с порядком их временных меток.

Лемма 2. Пусть локальная СУБД использует протокол сериализации транзакций SS2PL (Strong Strict 2-Phase Locking - сильная строгая двухфазная блокировка), и Я - история локальных транзакций на множестве транзакций Т = {7;,...,Гп}, полученная в результате использования этого протокола. Тогда Я сериализуема и порядок сериализации транзакций в Я совпадает с порядком их фиксации.

Таким образом, для определения порядка сериализации глобальных субтранзакций в локальных СУБД, использующих протоколы временных меток (как обычный, так и мультиверсионный) достаточно знать порядок их временных меток, то есть, в каком порядке субтранзакции были направлены в эти ЛСУБД. Для локальных СУБД, использующих протокол SS2PL достаточно знать, в каком порядке субтранзакции были зафиксированы в этих СУБД [3]. Этот порядок и будет соответствовать порядку сериализации.

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

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

12

глобальную сериализуемость транзакций. Локальная автономность СУБД при этой нарушается лишь незначительно.

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

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

Стоит отметить, что существующие методы обеспечения локальной сериализуемости для ЗпарзЬоЬизоляции либо нарушают локальную автономность еще больше (требуется изменение менеджера транзакций самой ЛСУБД), либо неприемлемо снижают производительность системы (например, требуется блокировать целые таблицы). Кроме того, даже при таких ограничениях они не рассматривают вопросы обеспечения глобальной сериализуемости и не позволяют узнать порядок сериализации транзакций в ЛСУБД. Таким образом, предложенный подход позволяет обеспечить сериализуемость транзакций на глобальном уровне без уменьшения производительности ЛСУБД при существенно меньших нарушениях локальной автономности.

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

Лемма 3. Пусть А#ЗС(#,<«с) - мультиверсионный граф предшествования, содержащий все зафиксированные транзакции, где Н - 81-сериализуемая история локальных транзакций на множестве транзакций

1 = {Т],...,Тп), а <гс - отношение порядка версий для Я, такое что х, <к X] <=> с, . Тогда для любой зафиксированной транзакции Та и любой фиксируемой транзакции Ть,Ъфа новая дуга вида Ть ->Гя может добавиться в граф только в том случае, если транзакция Ть началась до того, как была зафиксирована Та.

Следствие из леммы 3. Если локальная СУБД использует ЗпарвЬо^ изоляцию в качестве протокола управления параллельным выполнением транзакций, то для обеспечения сериализуемости истории локальных транзакций необходимо и достаточно гарантировать, чтобы мультиверсионный граф предшествования для этой истории был ацикличен. При этом любую транзакцию 7] можно безопасно удалять из графа (то есть эта транзакция гарантированно не может в будущем послужить причиной возникновения нового цикла в графе) при соблюдении следующих условий:

1. все транзакции, начатые до фиксации транзакции Тп завершились (были зафиксированы или отменены);

2. ни одна дуга в графе не направлена в вершину, соответствующую транзакции Тг

В случае если локальная СУБД не использует ни один из рассмотренных протоколов управления параллельным выполнением транзакций (ТО, МУТО, 882РЬ, Б1), или используемый ею протокол неизвестен (что, вообще говоря, является очень редким случаем), но при этом известно, что СУБД обеспечивает локальную сериализуемость, предлагается использовать существующий метод принудительных конфликтов.

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

1. Каждая глобальная транзакция, поступающая в систему, разбивается на глобальные субтранзакции и выполняется в соответствующих ЛСУБД.

2. В каждой ЛСУБД определяется порядок сериализации всех глобальных субтранзакций. Способ определения порядка зависит от типа ЛСУБД:

2.1. если ЛСУБД использует протокол ТО или МУТО, то порядок сериализации определяется по порядку, в котором были начаты субтранзакции в этой ЛСУБД;

2.2. если ЛСУБД использует протокол 882РЬ, то порядок сериализации определяется по порядку фиксации субтрагоакций;

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

2.4. если ЛСУБД использует другой или неизвестный протокол, но гарантирует локальную сериализуемость транзакций, то порядок сериализации определяется при помощи метода принудительных конфликтов.

3. Глобальные транзакции допускаются к фиксации только в том случае, если порядок сериализации их субтранзакций одинаков во всех ЛСУБД.

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

Теорема 2. Предложенный метод гарантирует сериализуемость истории транзакций системы мульти-БД при следующих условиях:

1. каждая ЛСУБД для управления параллельным выполнением транзакций использует либо Snapshot-изоляцию, либо любой протокол, обеспечивающий локальную сериализуемость транзакций;

2. каждая ЛСУБД позволяет получить информацию о том, когда глобальные субтранзакции переходят в состояние «READY» (в соответствии с протоколом двухфазной фиксации);

3. каждой глобальной транзакции соответствует максимум одна субтранзакция в каждой ЛСУБД.

Таким образом, предложен метод управления параллельным выполнением транзакций в МСДД, особенностью которого является то, что он позволяет интегрировать в рамках МСДД любые реляционные СУБД, либо обеспечивающие локальную сериализуемость транзакций, либо использующие Snapshot-изоляцию [4]. Для СУБД, использующих протоколы управления параллельным выполнением транзакций Timestamp Ordering, Multiversion Timestamp Ordering, Strong String Two-Phase Locking, метод полностью сохраняет их локальную автономность, не оказывая при этом существенного влияния на производительность. Для СУБД, использующих неизвестный протокол, но гарантирующих локальную сериализуемость, применяется метод принудительных конфликтов. Для СУБД, использующих Snapshot-изоляцию, предложенный метод позволяет гарантировать как локальную сериализуемость транзакций, так и глобальную сериализуемость при интеграции нескольких

СУБД такого типа (за счет частичного нарушения локальной автономности). В рамках математической модели доказана корректность метода.

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

Локальные пользователи

ЛСУБД 1 ЛСУБД2 ЛСУБД N

Рис. 3. Структурная модель МСДЦ

В алгоритме работы глобального менеджера транзакций использован подход «снизу вверх», то есть сначала локальные СУБД независимо друг от

друга определяют, в каком порядке транзакции будут сериализованы в каждой из них, а глобальный менеджер транзакций на основе собранной из локальных СУБД информации определяет, можно ли сохранить сериализуемость уже на глобальном уровне [2].

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

Фаза 1. Фаза чтения/записи. Глобальный менеджер транзакций обрабатывает поступающую от клиента глобальную транзакцию. Последняя разбивается на глобальные субтранзакции (максимум по одной субтранзакции на каждую локальную СУБД). Операции глобальных транзакций выполняются в локальных СУБД по мере поступления. Если в глобальной транзакции участвует хотя бы одна ЛСУБД, использующая протокол управления параллельным выполнением транзакций с применением блокировок (или неизвестный протокол), то возможно возникновение глобальной взаимоблокировки с участием данной транзакции (это относится и к СУБД, применяющим Snapshot-изоляцию: в теории для сохранения Snapshot-изоляции транзакциям запрещено одновременно обновлять одни и те же данные, на практике это условие реализуется, как правило, с помощью механизма строгой двухфазной блокировки для операций записи; например, в СУБД Oracle и PostgreSQL используется именно такая реализация). Поэтому перед отправкой первой операции в такую ЛСУБД менеджер транзакций устанавливает глобальный таймаут tDEADL0CK_ma0ur для этой транзакции. При поступлении команды на фиксацию глобальной транзакции от клиента глобальный менеджер транзакций посылает всем задействованным в транзакции СУБД сообщение «ргераге-to-commit» в соответствии с протоколом двухфазной фиксации. Если хотя бы одна глобальная субтранзакция откатывается (по причине локальной взаимоблокировки или невозможности обеспечить локальную сериализуемость), то вся глобальная транзакция откатывается. То же самое происходит в случае, если для какой-либо операции истекает таймаут 'deadlock-timeow (ситуация глобальной взаимоблокировки). Если все глобальные субтранзакции переходят в состояние «READY», то глобальная транзакция переходит в фазу проверки.

Фаза 2. Фаза проверки. После того, как все глобальные субтранзакции перешли в состояние «READY», глобальному менеджеру транзакций становится доступна информация о порядке их сериалзиации в локальных СУБД. На основании этой информации строится глобальный граф

17

предшествования (Global Serialization Graph - GSG). Если после добавления проверяемой транзакции и соответствующих ей дуг GSG содержит цикл, то, очевидно, субтранзакции как минимум двух глобальные транзакций были сериализованы в разном порядке в локальных СУБД, и, следовательно, история глобальных транзакций не является сериализуемой — проверяемая глобальная транзакция откатывается, а добавленные для нее дуги удаляются из графа GSG. В противном случае глобальная транзакция успешно проходит проверку.

Фаза 3. Фаза фиксации. Если глобальная транзакция прошла проверку, то она может записать данные в БД и может быть зафиксирована. Если нет -транзакция должна быть отменена.

Назначения компонента (САЗ) в этой системе — на основе синтаксического анализа запроса определять множества читаемых (RS) и записываемых (WS) данных, необходимых для определения порядка сериализации транзакций в СУБД, использующих Snapshot-изоляцию. Для этого предлагается строить приблизительные множества с помощью анализа предикатов в секции WHERE SQL-запросов. «Приблизительные» в данном случае означает, что построенные множества RS и WS могут быть не равны реальным, но обязательно должны полностью их включать. Например, для запроса «SELECT х FROM t WHERE х >= 1 AND х <= 3» будет выделен предикат «х >= 1 AND х <= 3», и будет построено множество RS = {x:1<jc<3}, тогда как на самом деле в таблице может вообще не быть записей, удовлетворяющих условию, или может быть одна запись, например, с х = 2, но не может быть записей, не входящих в RS.

Предлагается считать минимальным элементом данных один кортеж в реляционном отношении (одну строку таблицы). Можно были бы пойти дальше и строить более точные множества, считая единицей данных каждый элемент кортежа, однако это видится излишним усложнением системы. Кроме того, принцип работы с данными на уровне строк применяется в большинстве популярных на сегодняшний день СУБД.

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

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

18

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

По предложенной методике было проведено моделирование работы и нагрузочное тестирование разработанного прототипа [10]. Получены следующие результаты (см. рис. 4 и 5 ниже).

При вычислении скорости обработки транзакций учитывались только успешные (не отмененные из-за локального или глобального конфликта) транзакции. При вычислении времени обработки одной транзакций учитывались все транзакции.

Из графиков видно, что при отсутствии какого-либо управления параллельным выполнением транзакций на глобальном уровне количество одновременных глобальных транзакций менее 75 -ти не является достаточным, чтобы полностью загрузить локальные СУБД при использованной аппаратной конфигурации серверов, - с ростом количества транзакций практически линейно растет и скорость их обработки. При количестве транзакций 75-400 скорость обработки примерно постоянна, а затем начинает падать из-за слишком большого количества отмен транзакций на локальном уровне. При дополнительном контроле транзакций на глобальном уровне (с применением предложенного метода) скорость обработки транзакций снижается незначительно. Более того, при экспоненциальном росте общего времени обработки транзакций составляющая, вносимая дополнительным контролем на глобальном уровне («накладные расходы» при использовании метода), растет линейно, что подтверждает теоретические выводы, сделанные в третьей главе. К тому же, сама по себе эта составляющая невелика: при 600 одновременно

выполняемых глобальных транзакциях только порядка 10-15% времени уходит на обеспечение сериализуемости истории глобальных транзакций.

Скорость обработки транзакций

_ 14

X

ш

и 12

£ 6 » 4

5 10 15 25 50 75 100 150 200 300 400 500 600 количество одновременных глобальных транзакций (Л/6)

-Без какого-либо контроля

-С применением предложенного метода

Рис. 4. Зависимость скорости обработки транзакций от количества одновременных

глобальных транзакций

Время обработки одной транзакции

100 200 300 400 500

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

-Время обработки транзакции в Л СУБД

-Накладные расходы при использовании предложенного метода

Рис. 5. Зависимость времени обработки одной глобальной транзакции от количества одновременных глобальных транзакций

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

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

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

В приложениях представлены: БНФ грамматики, использованной для синтаксического анализа БС^Ь-запросов, фрагмент журнала работы компонента синтаксического анализа запросов, поясняющий процесс анализа, пользовательский интерфейс разработанной платежной системы, результаты моделирования работы и нагрузочного тестирования прототипа.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Основные результаты, полученные автором диссертационного исследования, состоят в следующем:

1. Проведена классификация глобальных информационных систем в распределенной среде, подробно рассмотрены мобильные системы доступа к данным (МСДЦ) - распределенные гетерогенные базы данных, состоящие из автономных локальных СУБД, клиенты которых работают в беспроводной сети. Изучена проблематика управления параллельным выполнением транзакций в таких системах на глобальном уровне.

2. Выполнен обзор существующих методов управления параллельным выполнением транзакций в таких системах. Сделан вывод о том, что существующие решения обладают рядом недостатков, или не применялись на практике, или рассматривают вопросы интеграции только тех СУБД, которые обеспечивают локальную сериализуемость, в то время как многие современные СУБД, использующие ЗпаряЬотзоляцию (изоляцию «моментальных снимков»), не обладают этим свойством.

3. Предложена математическая модель МСДД, описывающая данные, транзакции и истории транзакций в системе и отличающаяся от существующих моделей тем, что учитывает особенности управления транзакциями в СУБД, использующих БпарзЬоЬизоляцию (81). Формализованы критерии сериализуемости и 81-сериализуемости локальных историй транзакций. Доказаны необходимые и достаточные условия сериализуемости глобальной истории транзакций.

4. Впервые предложен метод управления параллельным выполнением транзакций в МСДЦ, позволяющий интегрировать как СУБД, обеспечивающие локальную сериализуемость транзакций, так и СУБД, использующие БпарБЬо!-изоляцию. На основе математической модели сформулированы и доказаны теоремы, подтверждающие правильность работы метода.

5. Разработанный метод обеспечивает атомарность глобальных транзакций, их сериализуемость и отсутствие глобальных взаимоблокировок. Для СУБД, гарантирующих локальную сериализуемость, метод полностью сохраняет их локальную автономность, не оказывая при этом существенного влияния на производительность. Для СУБД, использующих БпарзИоОизоляцию, — позволяет гарантировать как локальную сериализуемость транзакций, так и глобальную сериализуемость при интеграции нескольких СУБД такого типа (за счет частичного нарушения локальной автономности).

6. Разработана структурная модель МСДД, позволяющая использовать полученные теоретические результаты на практике. Описаны алгоритмы работы глобального менеджера транзакций, учитывающие специфику мобильной среды, проведена оценка сложности алгоритмов.

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

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

9. Реализован прототип МСДД на примере системы мобильных платежей. Прототип успешно прошел внедрение и апробацию в ООО «ПС груп».

10. Разработанные модели МСДД и методы управления параллельным выполнением транзакций в МСДД могут быть использованы при создании практически любых распределенных мобильных систем со стационарными базами данных и мобильными клиентами. Использование предложенного алгоритма работы глобального менеджера транзакций позволяет уменьшить время обработки транзакций по сравнению с существующими алгоритмами и

уменьшить нагрузку на каналы связи, позволяя тем самым сокращать издержки и создавать более быстрые мобильные приложения.

Основные положения диссертационной работы опубликованы в следующих работах:

1. Храмов, А. А. Проблемы управления параллельным доступом в мобильных системах доступа к данным и методы их решения [Текст] / Александр Александрович Храмов, Николай Александрович Аникин // Вестник Московского авиационного института. - М. : Изд-во МАИ, 2010. - Т. 17, № 6. -С. 129-138. - ISSN 0869-6101.

2. Храмов, А. А. Протокол управления параллельным доступом в мобильной системе доступа к данным, включающей базы данных, использующие критерий Snapshot-изоляции [Текст] / Александр Александрович Храмов, Николай Александрович Аникин // Вестник Московского авиационного института. - М. : Изд-во МАИ, 2011. - Т. 18, № 2. - С. 180-185. -ISSN 0869-6101.

3. Аникин, Н. А. Метод определения порядка сериализации транзакций в системах управления базами данных, использующих протокол строгой двухфазной блокировки [Текст] / Николай Александрович Аникин // Электронный журнал «Труды МАИ». — 2010. - № 42. -http://www.mai.ru/science/trudy/.

4. Храмов, А. А. Методы обеспечения глобальной сериализуемости транзакций в мобильных системах доступа к данным [Текст] / Александр Александрович Храмов, Николай Александрович Аникин И Информационно-измерительные и управляющие системы. Интеллектуальные системы и технологии (журнал в журнале). - М., 2011. - Т. 9, № 10. - С. 52-57. - ISSN 2070-0814.

5. Аникин, Н. А. Особенности использования мобильных устройств в системах мульти-БД [Текст] / Николай Александрович Аникин // Высокие технологии, исследования, промышленность: сборник трудов Девятой международной практической конференции «Исследование, разработка и применение высоких технологий в промышленности». - СПб. : Изд-во Политехи. Ун-та, 2010. - Т. 1. - С. 117-124. - ISBN 978-5-7422-2557-7.

6. Аникин, Н. А. Анализ существующих решений и постановка задачи создания перспективной системы мобильных платежей [Текст] / Николай Александрович Аникин // Научная сессия НИЯУ МИФИ-2010. XIII

Международная телекомуникационная конференция студентов и молодых ученых "МОЛОДЕЖЬ И НАУКА.". Тезисы докладов. В 3-х частях. Ч. 2. - М. : НИЯУ МИФИ, 2010. - С. 32-33. - ISBN 978-5-7262-1229-6.

7. Аникин, Н. А. Методы обеспечения сериализуемости транзакций в СУБД, использующих Snapshot-изоляцию [Текст] / Николай Александрович Аникин // Интеллектуальные технологии в образовании, экономике и управлении : Сб. матер. 7-ой Межд. научн.-практ. конф. - Воронеж : ЮниПресс, 2010. - С. 174-178.

8. Аникин, Н. А. Методы обеспечения глобальной сериализуемости транзакций в системах мульти-БД [Текст] / Николай Александрович Аникин // Научная сессия НИЯУ МИФИ-2011. XIV международная телекоммуникационная конференция студентов и молодых ученых «Молодежь и наука». Тезисы докладов. Ч.З. - М.: НИЯУ МИФИ, 2010. - С. 99-100.

9. Аникин, Н. А. Интеграция СУБД, обеспечивающих локальную сериализуемость, и СУБД, использующих Snapshot-изоляцию, в рамках системы мульти-БД [Текст] / Николай Александрович Аникин // Сборник научных трудов по материалам международной научно-практической конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании '2010». Том 3. Технические науки. - Одесса : Черноморье, 2010. - С. 28-33.

10. Храмов, А. А. Прототип мобильной системы доступа к . данным, обеспечивающей глобальную сериализуемость транзакций [Текст] / Александр Александрович Храмов, Николай Александрович Аникин // Современные технологии в задачах управления, автоматики и обработки информации : тез. докладов XX Междунар. научн.-техн. семинара (г. Алушта, 12-24 сентября 2011 г.). - Пенза : Изд-во ПТУ, 2011. - С. 80-81. - ISBN 978-5-94170-377-7.

Множительный центр МАИ (НИУ) Заказ от C»Y201¿r- ТиР3* /

61 12-5/2489

Национальный исследовательский ядерный университет «МИФИ»

УПРАВЛЕНИЕ ПАРАЛЛЕЛЬНЫМ ВЫПОЛНЕНИЕМ ТРАНЗАКЦИЙ В РАСПРЕДЕЛЕННЫХ ГЕТЕРОГЕННЫХ БАЗАХ ДАННЫХ ПРИ ДОСТУПЕ ИЗ МОБИЛЬНОЙ СРЕДЫ

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

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

Аникин Николай Александрович

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель: кандидат технических наук, доцент Храмов Александр Александрович

Москва-2012

Оглавление

Введение........................................................................................................................7

Глава 1. Мобильные системы доступа к данным (МСДД):

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

1.1. Классификация систем совместного доступа к информации................14

1.2. Проблемы разработки систем мульти-БД (СМБД) и МСДД.................19

1.2.1. Характеристики СМБД...................................................................19

1.2.1.1. Проблемы, возникающие при разработке СМБД...............23

1.2.2. Особенности использования мобильных устройств в СМБД.....24

1.2.2.1. Проблемы, возникающие при разработке МСДД..............26

1.3. Управление параллельным выполнением транзакций............................28

1.3.1. Основы обработки транзакций в централизованной среде.........28

1.3.2. Основы обработки транзакций в среде мульти-БД......................31

1.3.3. Проблемы управления параллельным выполнением транзакций в СМБД...................................................................................33

1.3.3.1. Сериализуемость транзакций...............................................33

1.3.3.2. Взаимоблокировки транзакций............................................35

1.3.3.3. Атомарность транзакций.......................................................37

1.3.3.4. Интеграция СУБД, использующих БпарзЬог-изоляцию.... 39

1.3.4. Проблемы управления параллельным выполнением транзакций в МСДД...................................................................................41

1.4. Обзор существующих решений в области управления параллельным выполнением транзакций в МСДД.........................................42

1.4.1. Общие подходы к обеспечению сериализуемости

глобальных транзакций в среде мульти-БД............................................42

2

1.4.1.1. Полная автономность локальных узлов..............................43

1.4.1.2. Менее строгие критерии сериализуемости.........................46

1.4.1.3. Частичное нарушение локальной автономности................48

1.4.1.4. Использование специфических знаний о ЛСУБД..............50

1.4.1.5. Использование семантики транзакций................................52

1.4.2. Методы обеспечения сериализуемости транзакций и алгоритмы работы менеджера транзакций заданий в МСДД...............52

1.4.3. Методы обеспечения сериализуемости локальных транзакций при использовании Snapshot-изоляции...............................59

1.5. Постановка задачи......................................................................................61

1.6. Выводы.........................................................................................................63

Глава 2. Разработка метода управления параллельным выполнением транзакций в МСДД...................................................................................................64

2.1. Анализ особенностей существующих методов.......................................64

2.2. Анализ задачи и общая схема МСДД.......................................................66

2.3. Математическая модель транзакций в СМБД.........................................68

2.3.1. Основные понятия...........................................................................68

2.3.2. История транзакций.........................................................................71

2.3.3. Сериализуемость истории транзакций..........................................74

2.3.4. Мультиверсионное управление параллельным выполнением транзакций..................................................................................................76

2.3.4.1. Мультиверсионная история транзакций.............................76

2.3.4.2. Сериализуемость мультиверсионной истории...................78

2.3.4.3. Мультиверсионный граф предшествования.......................79

2.3.5. Snapshot-изоляция............................................................................81

2.4. Обеспечение атомарности глобальных транзакций................................83

3

2.4.1. Возможные решения в случае, если протокол 2РС не поддерживается..........................................................................................85

2.5. Метод обеспечения глобальной сериализуемости..................................86

2.5.1. Необходимые и достаточные условия сериализуемости.............86

2.5.2. Определение порядка сериализации глобальных субтранзакций в локальных СУБД..........................................................90

2.5.2.1. СУБД, использющие протоколы ТО и MVTO...................90

2.5.2.2. СУБД, использующие протокол SS2PL..............................94

2.5.2.3. СУБД, использующие Snapshot-изоляцию.........................98

2.5.2.4. СУБД, использующие неизвестный протокол..................104

2.5.3. Доказательство корректности метода..........................................105

2.6. Выводы.......................................................................................................107

Глава 3. Структурная модель МСДД и алгоритмы работы

глобального менеджера транзакций.......................................................................109

3.1. Структурная модель МСДД.....................................................................109

3.1.1. Обобщенная модель.......................................................................109

3.1.2. Компонент передачи данных........................................................111

3.1.3. Компонент синтаксического анализа запросов..........................112

3.1.4. Компонент доступа к метаданным...............................................115

3.1.5. Адаптеры ЛСУБД..........................................................................116

3.1.6. Глобальный менеджер транзакций..............................................118

3.2. Обработка глобальных транзакций.........................................................118

3.2.1. Обобщенный алгоритм обработки транзакций..........................118

3.2.2. Проверка глобальной сериализуемости......................................123

3.2.2.1. Построение глобального графа предшествования...........123

3.2.2.2. Добавление транзакций в граф...........................................124

3.2.2.3. Исключение лишних транзакций из графа.......................130

3.2.3. Решение проблем, порождаемых мобильной средой................133

3.2.3.1. Модификация протокола двухфазной фиксации.............133

3.2.3.2. Обработка непредвиденных обрывов соединения...........135

3.2.3.3. Дополнительная прямая проверка.....................................136

3.2.4. Блок-схема алгоритма обработки транзакций............................138

3.2.5. Оценка сложности алгоритмов.....................................................143

3.3. Протокол взаимодействия клиента с МСДД..........................................144

3.4. Масштабируемость системы....................................................................148

3.5. Выводы.......................................................................................................150

Глава 4. Программное обеспечение для управления МСДД,

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

4.1. Структура разработанного программного обеспечения.......................152

4.1.1. Модуль управления.......................................................................155

4.1.1.1. Компонент передачи данных..............................................156

4.1.1.2. Глобальный менеджер транзакций....................................157

4.1.1.3. Компонент синтаксического анализа запросов................162

4.1.1.4. Компонент доступа к метаданным.....................................166

4.1.2. Модуль тестирования....................................................................167

4.2. Реализация прототипа МСДД, использующего

предложенный метод, на примере системы мобильных платежей............171

4.2.1. Общее описание системы MidlPay...............................................171

4.2.2. Операции, доступные пользователю системы............................173

4.2.3. Вопросы безопасности..................................................................176

5

4.2.4. Применение технологии МСДД...................................................178

4.3. Моделирование процесса работы МСДД и результаты использования разработанного прототипа....................................................181

4.4. Выводы.......................................................................................................188

Заключение...............................................................................................................189

Список использованных источников.....................................................................191

Приложение 1...........................................................................................................208

Приложение 2...........................................................................................................212

Приложение 3...........................................................................................................217

Приложение 4...........................................................................................................218

Приложение 5...........................................................................................................223

Приложение 6...........................................................................................................229

ВВЕДЕНИЕ

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

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

За последние несколько лет также получили серьезное развитие и мобильные технологии. Причем, большое количество исследований и разработок было проведено как в области мобильных устройств (сотовые телефоны, смартфоны, карманные и переносные компьютеры), так и в области средств связи (GPRS - одна из первых технологий мобильного интернета, ее улучшенный аналог EDGE, развивающиеся в последние годы технологии Wi-Fi, Wi-MAX, 3G). Эти технологии помогают наделить мобильные устройства значительно большей функциональностью, и сфера применения этих технологий очень широка: начиная от простейших интернет-приложений для просмотра веб-страниц и электронной почты и заканчивая приложениями для электронной коммерции, интернет-банкинга, оплаты различных услуг.

В последние годы сформировалось отдельное направление в науке, изучающее вопросы управления гетерогенными базами данных в распределенной и одновременно мобильной среде (под «мобильной средой» подразумевается то, что доступ в систему осуществляется с мобильного устройства и, как правило, по беспроводному каналу связи). В зарубежной литературе это направление получило название MDAS - Mobile Data Access System (МСДД - мобильная система доступа к данным).

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

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

Цель диссертационной работы.

Цель диссертационной работы состоит в решении проблемы управления параллельным выполнением транзакций на глобальном уровне в МСДД, которая объединяет несколько реляционных СУБД, использующих разные методы управления параллельным выполнением транзакций на локальном уровне.

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

1. анализ и классификация существующих решений в области систем совместного доступа к информации;

2. исследование современных методов управления параллельным выполнением транзакций в системах мульти-БД и МСДД;

3. разработка математической модели МСДД;

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

5. разработка метода и алгоритма работы глобального менеджера транзакций (concurrency-control manager), отвечающего за обеспечение сериализуемости транзакций в МСДД;

6. разработка структурной модели МСДД и реализация её прототипа;

7. реализация предложенного метода и его применение на примере мобильной платежной системы;

8. оценка эффективности метода при работе с реальными СУБД.

Методы исследования.

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

Научные результаты и их новизна.

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

1. разработана математическая модель МСДД, описывающая данные, транзакции и истории транзакций в системе и отличающаяся от существующих моделей тем, что учитывает особенности управления транзакциями в СУБД, использующих Snapshot-изоляцию (изоляцию «моментальных снимков»);

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

3. предложен новый метод управления параллельным выполнением транзакций в МСДД, учитывающий специфику мобильной среды и позволяющий интегрировать любые СУБД, обеспечивающие сериализуемость локальных транзакций (без существенных нарушений их локальной автономности), и СУБД, использующие 8парз1ю1:-изоляцию (с частичным нарушением автономности);

4. доказана корректность метода управления параллельным выполнением транзакций в МСДД;

5. впервые предложено решение для интеграции СУБД, обеспечивающих сериализуемость локальных транзакций, и СУБД, использующих БпарзЬо^изоляцию, в мобильной среде;

6. разработана методика применения полученных теоретических результатов на практике;

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

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

Разработанные модели МСДД и методы управления параллельным выполнением транзакций в МСДД могут быть использованы при создании практически любых распределенных мобильных систем со стационарными БД и мобильными клиентами. Для таких систем предложенный метод позволяет интегрировать в рамках глобальной системы практически все используемые в широкой практике реляционные СУБД и гарантировать глобальную сериализуемость транзакций. При этом, как показало моделирование, дополнительный контроль транзакций на глобальном уровне приводит к падению производительности системы не более чем на 10-15%, при выполнении 600 одновременных глобальных транзакций.

Реализация и внедрение результатов работы.

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

Апробация работы.

Основные положения диссертационной работы докладывались и обсуждались на конференциях и семинарах: XIII и XIV международных телекоммуникационных конференциях студентов и молодых ученых «МОЛОДЕЖЬ И НАУКА» (Москва, 2010, 2011), девятой международной практической конференции «Исследование, разработка и применение высоких технологий в промышленности» (Санкт-Петербург, 2010), 7-ой международной научно-практической конференции «Интеллектуальные технологии в образовании, экономике и управлении» (Воронеж, 2010), международной научно-практической конференции «Современные проблемы и пути их решения в науке, транспорте, производстве и образовании '2010» (Одесса, 2010), XIX и XX международных научно-технических семинарах «Современные технологии в задачах управления, автоматики и обработки информации» (Алушта, 2011).

Публикации.

По теме диссертации опубликовано 10 печатных работ: 5 тезисов докладов и 5 статей в журналах, в том числе 4 статьи в журналах, включенных ВАК РФ в перечень ведущих рецензируемых научных журналов и изданий.

11

Структура и объем работы.

Диссертационная работа состоит из введения, четырех глав, заключения, библиографического списка из 128 наименований и приложений. Общий объем диссертации - 230 страниц машинописного текста, в том числе: 160 страниц основного текста и 23 страницы приложений, 39 рисунков, 17 таблиц.

Содержание работы.

В первой главе приводится классификация р