Одеський національний політехнічний університет

УДК 681.3.06

Блажко Олександр Анатолiйович

ОПТИМІЗАЦІЙНА МОДЕЛЬ ТА ЗАСОБИ АСИНХРОННОГО ТИРАЖУВАННЯ ДАНИХ ДЛЯ ПОБУДОВИ СИСТЕМ РОЗПОДІЛЕНОЇ ОБРОБКИ ІНФОРМАЦІЇ

Спецiальнiсть 05.13.06 – Автоматизованi системи управлiння та прогресивнi iнформацiйнi технологiї

АВТОРЕФЕРАТ

дисертації на здобуття наукового ступеня

кандидата технічних наук

Одеса – 2001

Дисертація є рукописом.

Робота виконана на кафедрі "Системне програмне забезпечення" Одеського національного політехнічного університету міністерства освіти і науки України.

Науковий керівник кандидат технічних наук, доцент Кунгурцев Олексій Борисович, доцент кафедри "Системне програмне забезпечення" Одеського національного політехнічного університету

Офіційні опоненти: –

доктор технічних наук, професор Становський Олександр Леонідович, завідувач кафедри нафтогазового та хімічного машинобудування Одеського національного політехнічного університету;–

кандидат технічних наук, доцент Кошкін Костянтин Вікторович, завідувач кафедри інформаційних технологій Українського державного морського технiчного унiверситету ім. адм. Макарова (м. Миколаїв).

Провідна установа Харківський національний технічний університет радіоелектроніки, кафедра програмного забезпечення автоматизованих систем.

Захист відбудеться "25"жовтня 2001 року о 1330 годині на засіданні спеціалізованої вченої ради Д 41.052.01 Одеського національного політехнічного університету за адресою: 65044, м. Одеса, проспект Шевченка, 1, ауд. 400 -- А.

З дисертацією можна ознайомитись у бібліотеці Одеського національного політехнічного університету за адресою: 65044, м. Одеса, проспект Шевченка, 1.

Автореферат розіслано "21"вересня 2001 року.

Вчений секретар спеціалізованої

вченої ради, професор Ямпольський Ю.С.

ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

Актуальність теми. Розвиток комп`ютерних мереж у 80-х роках став поштовхом до активної розробки інформаційних систем (ІС) з розподіленою обробкою даних, яка базується на системах управління тиражуванням даних (СУТД) в розподілених базах даних (РБД). При тиражуванні набори даних дублюються на множині сполучених мережею каналів зв'язку комп`ютерів ІС (вузлів) з системами управління локальними базам даних (СУБД). В цих умовах СУТД повинна одночасно (синхронно) або із запізненням (асинхронно) узгоджувати значення копій даних в РБД, використовуючи, відповідно, синхронні або асинхронні протоколи тиражування.

Результатом багатьох досліджень в області тиражування даних стали розробки систем тиражування із синхронними протоколами тиражування, які впроваджувалися в ІС, насамперед, для забезпечення необхідного рівня надійності функціонування.

Поява глобальної мережі Internet та зменшення вартості одиниці збереження інформації на жорстких носіях вузлів дозволили створювати ІС для організацій, які складаються з територіально віддалених підрозділів. Бажана автономність роботи підрозділів в межах окремих вузлів, необхідність зменшення витрат на підтримку мережі каналів зв`язку між вузлами та забезпечення масштабованості протоколів тиражування виключають використання синхронних протоколів для узгодження копій баз даних.

В той же час, асинхронні протоколи підвищують ймовірність переводу копій баз даних в неузгоджений стан та ймовірність некоректного рішення задач ІС при використанні ними цих копій. Розв`язання існуючих протирічч між коректністю та продуктивністю асинхронних протоколів тиражування обумовлює актуальність досліджень в цій області.

Зв'язок роботи з науковими програмами, планами, темами. Тема дослідження дисертацiйної роботи входить до НДР кафедри “Системне програмне забезпечення” Одеського національного політехнічного університету (ОНПУ) № 329-73 “Програмні засоби автоматизованих систем. Розробка та дослідження методів і засобiв автоматизованих систем”, наукових напрямів і планів робіт лабораторії інформаційних систем ОНПУ, пов'язаних з розробкою інформаційної системи “Автоматизована система управління університетом” в ОНПУ, НДР № 1239-129 “Автоматизована система формування оперативної і звітної інформації на базі розподіленої обробки даних” за договором з Прикордонною держінспекцією по карантину рослин (ПДКР) по Одеській області, НДР № 729-144 загальноуніверситетської науково-дослідної лабораторії “ЕксПерт” ОНПУ.

Мета і задачі дослідження. Метою роботи є підвищення продуктивності та надійності інформаційної системи з розподіленою обробкою даних шляхом розробки та впровадження оптимізаційної моделі тиражування даних на основі асинхронних протоколів. Для досягнення цієї мети в роботі поставлені та вирішені наступні задачі:

·

· розроблено методику гранульованого розподілу інформаційних ресурсів (ГРІР) з впровадженням протоколів асинхронного тиражування для мінімізації навантаження операцій узгодження на вузли з копіями баз даних та мережу каналів зв`язку між ними;

· розроблено методику оцінки продуктивності системи асинхронного тиражування даних на основі натурних експериментів та її імітаційної моделі;

· розроблено та впроваджено систему асинхронного тиражування даних.

Об`єктом дослідження є процес тиражування даних в інформаційних системах з розподіленою обробкою інформації.

Предметом дослідження є асинхронні протоколи тиражування даних.

Методи дослідження. При розв`язанні задачі оптимального розподілу інформаційних ресурсів використані евристичні алгоритми вирішення задач математичного програмування з елементами теорії обчислювальних мереж; при моделюванні процесів тиражування - статистичні методи імітаційного моделювання з елементами теорії масового обслуговування; при формуванні моделі системи тиражування даних – методи теорії графів та множин.

Наукова новизна одержаних результатів полягає в розвитку і поглибленні теоретичних і методологічних основ підвищення ефективності систем асинхронного тиражування даних. Новими науковими результатами дисертаційного дослідження є:

·

· запропоновано модель формування операцій узгодження копій об`єктів тиражування на основі мінімальних потреб коректності результатів задач інформаційної системи та узгодженності використовуємих ними копій об`єктів з різним рівнем грануляції, яка дозволяє скоротити завантаження мережі каналів зв`язку між вузлами в процесі узгодження;

· вдосконалено аналітичну та імітаційну моделі процесів асинхронного тиражування даних завдяки врахуванню схем, топологій тиражування операцій узгодження даних та процесів виявлення і розв`язання конфліктів між цими операціями, що дозволило провести адекватну оцінку ефективності використання системи асинхронного тиражування даних у порівнянні з системою синхронного тиражування.

Практичне значення одержаних результатів.

На основі методики розподілу гранульованих інформаційних ресурсів розроблена система формування фізичної структури розподіленої бази даних. Система використана при проектуванні інформаційної системи "Автоматизована система управління вузом", яка функціонує в ОНПУ, що дозволило при підвищені кількості користувачів системи утримати показникі продуктивності систем управління базами даних на незмінному рівні.

Розроблено механізм тиражування даних в СУБД PostgreSQL, яка функціонує під ОС Linux, що дозволяє проектувати розподілені IС з низькими витратами на використання системного програмного забезпечення.

На основі структурно-функціональної моделі виявлення та розв`язання ймовірних конфліктів мiж операціями над копіями об`єктів тиражування розроблена підсистема управління конфліктами. Впровадження цієї підсистеми в інформаційну систему "Автоматизована система управління вузом", що функціонує в ОНПУ, дозволило забезпечити автономне беззупинне функціонування автоматизованих робочих місць підрозділів вузу при тимчасовому виході з ладу окремих ділянок комунікаційної мережі та знизило для клієнтів час відгуку системи на 50 % без модернізації апаратної частини ІС у порівнянні з існуючими алгоритмами формування структури СУТД.

Підсистема узгодження розподіленої бази даних впроваджена в інформаційну систему "Автоматизована система формування оперативної і звітної інформації на базі розподіленої обробки даних", яка розроблена для ПДКР по Одеській області. Це дозволило забезпечити прийнятний для користувачів інформаційної системи час відгуку без використання каналів зв`язку з високою пропускною спроможністю.

Результати роботи впроваджені також в учбовий процес на кафедрі "Cистемне програмне забезпечення" ОНПУ в дисципліні "Інформаційні системи та структури даних".

Особистий внесок здобувача. В [2] автору належить розробка методики угруповування клієнтів на вузлах інформаційної системи з розподіленою обробкою даних; в [3] автору належить розробка механiзму оцiнки серверного навантаження протоколiв тиражування; в [6] автору належить розробка методики пакетної передачі операцій узгодження даних; в роботі [8] автору належить методика створення моделі функціонування СУТД.

Апробація результатів дисертації. Матеріали роботи доповідалися та обговорювалися на VI Міжнародній конференції з автоматичного управління “Автоматика - 99” (Харків, 1999), VI і VII науково-методичних конференціях “Новi iнформацiйнi технологiї навчання в учбових закладах України” (Одеса, 1998, 2000), міжнародній науковій конференції “Інформаційна інфраструктура вищих учбових закладів” (Херсон, 1999) та на III Всеукраїнській конференції молодих науковців “Комп`ютерне моделювання та інформаційні технології в науці, економіці та освіті” (Кривий Ріг, 2001).

Публікації. Результати дисертації викладені в 8 публікаціях, у тому числі - в 5 статтях у фахових виданнях згідно з переліком ВАК України.

Структура дисертації. Дисертація складається із вступу, чотирьох розділів, трьох додатків. Обсяг дисертації - 168 стор., додатків - 30 стор. Дисертація містить 15 рисунків, 5 таблиць та посилання до 164 літературних джерел.

ОСНОВНИЙ ЗМІСТ РОБОТИ

У вступі обгрунтовується важливість та актуальність теми дисертації, викладені мета та задачі досліджень. Сформульовані основні положення та результати, досягнуті під час виконання роботи, їх наукова новизна.

У першому розділі розглядається стан питання з проблеми підвищення продуктивності та надійності ІС при використанні СУТД.

Для визначення межі наукових досліджень роботи розглянуто багатокритеріальну класифікацію ІС, на основі якої виділено клас ієрархічних транзакційно-аналітичних систем з детерміновано-часовими запитами (ІТА-системи). Ці ІС суміщають властивості систем з оперативної обробки транзакцій і систем прийняття рішень, мають територіальний розподіл користувачів (клієнтів), для яких процес взаємодії з БД носить, переважно, детермінований характер з інформаційними запитами, які враховують ієрархічність у взаємодії між підрозділами та орієнтовані на діапазон часу. ІТА-системи найбільш поширені в сучасних автоматизованих системах управління документооборотом організацій різного типу.

Розглянуто архітектуру ІС виділеного класу як сукупність апаратних та програмних компонентів та засоби підвищення продуктивності ІС за рахунок реконструкції кожного з цих компонентів. Аналіз впливу компонетів ІС на її продуктивність показав, що найбільший вплив має СУБД, а засобом підвищення продуктивності ІС в межах цього компонента є модернізація СУТД.

Розглянуто існуючі засоби побудови СУТД та механізми забезпечення узгодженого стану РБД, який підтримується протоколами синхронного тиражування операцій узгодження РБД (С-протоколами) та протоколами асинхронного тиражування (А-протоколами). Аналіз недоліків С-протоколів при їх використанні в СУТД ІС виділеного класу показав, що найбільш ефективним є використання А-протоколів.

Розглянуто існуючі моделі транзакцій та рівні їх ізоляції, які гарантують коректність результатів виконаних ними операцій та узгодженість стану БД. Показано, що транзакції, які автономно модифікують фізичні схеми РБД, узгодження яких виконується С-протоколами, забезпечують коректність своїх дій завдяки використанню стандартних (централізованих) рівнів ізоляції. Для визначення межі використання A-протоколів в СУТД, коли ослаблення потреб у квазіпослідовному плані виконання транзакцій не заперечує їх операціям, необхідно централізовані рівні доповнити розподіленими рівнями ізоляції транзакцій (РТ-рівні).

Існуючі алгоритми оптимального з точки зору мінімізації завантаження комунікаційних каналів зв'язку і часу відгуку системи та розподілу інформаційних ресурсів по вузлах РБД використовують схеми інформаційних потоків та інфраструктуру вузлів ІС без врахування особливостей функціонування A-протоколів. В той же час, показано, що врахування схем та протоколів тиражування, пакетної обробки операцій узгодження, функціональної схеми і схеми транзакцій задач ІС зменшує вплив СУТД на навантаження СУБД, що підвищує ефективність використання A-протоколів.

У СУТД вимоги по забезпеченню постійної узгодженості РБД, яка реалізується С-протоколами, при використанні А-протоколів ослаблюються до рівня вимог подійної узгодженості, коли РБД переходить до узгодженого стану через певний інтервал часу або у випадку виникненя певної події. Але автономність функціонування вузлів РБД призводить до того, що подійна узгодженість може бути гарантована тільки завдяки механізмам запобігання конфліктів між операціями узгодження та виявлення і розв`язання цих конфліктів, які повинні враховувати функціональну схему задач IС та РТ-рівні ізоляції транзакцій цих задач.

На основі проведеного аналізу стану питання виконана постановка задачі досліджень.

У другому розділі розглянуто формалізацію архітектури ІС та СУТД та запропоновано методику відображення параметрів моделі ІС на параметри моделі СУТД.

На основі аналізу структури ІС з точки зору її впливу на процесс формування архітектури СУТД, виділено компоненти ІС, формалізація яких описує математичну модель ІС у вигляді впорядкованої шістки

< Task , LDBS, Transact, Infra, Info, DBMS >,

де Task = {taskj} - множина, яка описує функції задач ІС, пов`язані з формуванням документів статистичного типу;

LDBS - граф логічної структури БД, який описує об`ємні залежності між відношеннями;

Transact = {Trj} - множина, яка описує функції taskj О Task задач ІС у вигляді транзакцій Trj;

Infra = <Node, Link> - граф інфраструктури вузлів ІС та мережі каналів зв`язку між ними;

Info = {infoi} - множина, елементи якої описують об`ємно-часові характеристики клієнтських інформаційних потоків;

DBMS - системні структури та механізми управління транзакціями, які використовуються в СУБД.

Елементи task О Task описуються трійками

<D, H, re>,

де D, H, re - відповідно, періодичність формування документу, його часовий діапазон та припустима відносна похибка використаних в документі агрегацій даних з БД.

Транзакції TrjОTransact представлені множиною елементів-пар

< otjk, operjk >,

де otjk = {ins, up, del, sel} - тип операції, відповідно, внесення, зміни, виключення та читання;

operjk = < R, A, W > - область даних в БД, над якою транзакція Trj виконує операцію otjk, де A, R Н LDBS, W - підмножина атрибутів, відносин логічної схеми БД та предикат опису діапазону значень, які входять до складу операції;

Граф Infra описується множиною вузлів-вершин Node={k: k=1,Nk} та множиною каналів зв'язку-дуг Link = {< li, lj, ltij >}, де li, lj - номери вузлів, що з`єднуються каналом зв`язку типу ltijО{Glink, Llink} (глобальний чи локальний тип зв`язку).

Елементи infoi О Info описуються трійками

<cln, F(L), Constr>,

де cln, F(L), Constr - відповідно, вузел розміщення клієнта, функція розподілення інтенсивності виконання його задач та множина предикатів-обмежень, які виділяють з БД необхідну для задач клієнта область даних.

Проектування РБД з тиражуванням даних складається з проектування фізичної структури РБД та протоколів тиражування даних, тому математична модель СУТД з достатньою повнотою описується у вигляді впорядкованої двійки

ReplicDBMS = < PDDS, ReplicProtocol >

де PDDS - множина локальних БД, які формують фізичну структуру РБД;

ReplicProtocol - А-протокол тиражування даних, який, в свою чергу, описується у вигляді впорядкованої четвірки

< RS, CS, RT, CMS >;

RS - схема тиражування операцій узгодження (Replication Schema);

CS - схема узгодження РБД (Consistency Schema);

RT - топологія тиражування (Replication Topology);

CMS - схема управління конфліктами (Conflict Management Schema).

Множина PDDS фізичної структури РБД описує фізичне розташування елементів логічної структури БД з формуванням об'єктів тиражування (ОТ) з різною мірою деталізування (грануляції): атрибут кортежу, кортеж, атрибут відношення, базове відношення, матеріалізоване уявлення. Елементами множини PDDS є двійки

< dba, PDS >,

де dba - ідентифікатор БД, який містить логічне ім`я БД та мережеву адресу вузла, на якому вона розташована;

PDS = { PDS(ri)} - фізична структура БД, яка описує ОТ з різним ступенем деталізації, де PDS(ri) = < R, A, P > - фізична структура відношення ri, A,R Н LDBS - відповідно, підмножина атрибутів, відношень логічної структури БД та предикат опису діапазону даних в БД.

Елементи множини RS описуються у вигляді трійки

< PDSi(rk), PDSj(rk), rst >,

де PDSi(rk), PDSj(rk) - фізичні структури відношення rk множин PDSi, PDSj фізичних структур БД, відповідно;

rst О {MM, MS, RO, MVR} - тип тиражування, відповідно, - "майстер-майстер", "майстер-підлеглий", "читання без модифікації", "читання матеріалізованого уявлення".

Елементи множини CS описуються як впорядковані п`ятірки

< PDSi(rk), PDSj(rk), ctp ,cd, nc >,

де PDSi(rk), PDSj(rk) - фізичні структури відношення rk i-ї та j-ї фізичних структур БД, відповідно;

ctp О {none, d(D(unc)), p(D(unc)), v(k)} - тип допустимого рівня розузгодження копій ОТ; none - узгодження без затримки; d(D(unc)) - узгодження з затримкою передачі останньої операції узгодження на D(unc) одиниць часу (період розузгодження); p(D)(unc) - узгодження з періодом D(unc); v(k) - узгодження копій останньою операцією з затримкою на k операцій;

cd О {snapshot, batch, oper} - ступінь деталізації процесу узгодження, - відповідно, узгодження “миттєвими знімками”, узгодження пакетами операцій, узгодження окремими операціями;

nc О {pull,pop} - визначає БД-ініціатор процеса узгодження (pull - PDSi(rk), pop - PDSj(rk)).

Елементи множини RT топології тиражування представлені трійкою

< PDSi(rk), PDSj(rm), NS >

де PDSi(rk), PDSj(rk) – відповідно, фізичні структури відношення rk i-ї та j-ї фізичних структур БД;

NS = {<i, j>} - множина пар-шляхів проходження операцій узгодження по локальним БД в РБД.

Для формалізації схеми управління конфліктами CMS при функціонуванні А-протоколів запропоновано розширену класифікацію конфліктів, які виникають в залежності від: типу операцій над ОТ (конфлікти sel-up та up-up), рівня деталізації операцій над ОТ (конфлікт рівня операцій, конфлікт рівня потока операцій, не обмеженого транзакційними примитивами фіксіції чи відкату, конфлікт рівня транзакцій, конфлікт рівня потока транзакцій), типу операції модифікації над ОТ (конфлікти ins-ins, ins-up та del-up). На основі класифікації запропонована множина типових конфліктів ConfType.

Схему управління конфліктами CMS, як структурно-функціональну модель виявлення та розв`язання ймовірних конфліктів між операціями узгодження ОТ, зображено у вигляді пари

CMS = < DRule, RRule >,

де DRule ={drulei}, RRule ={rrulei} - відповідно, множина правил виявлення конфліктів (ВК-правил) та правил розв'язання конфліктів (РК-правил) операцій модифікації PDSi(r).

Елемент drulei О DRule, який описує ВК-правила для операцій узгодження ОТОPDSi(r), зображено у вигляді впорядкованої трійки

<Confi, ConfStri, ConfDefi>,

де Confi Н ConfType, ConfStri Н DBMS, ConfDefi - відповідно, множина ймовірних конфліктів, мінімальна структура даних, яку повинна мати операція узгодження ОТОPDSi(r) для виявлення конфлікта типу Confi, та множина предикативних правил, які виявляють конфлікт.

До ВК-правил можна віднести такі правила: значень копій ОТ, версійних векторів копій ОТ з фізичними чи логічними мітками, контрольних запитів. Множина ConfStr має структуру відповідно правилу.

Наприклад, ВК-правило значень копій для ОТОPDSi(rk) математично еквивалентно елементу <{up-up}, PDSi(rk), {v(old)}, {vi(new) № vj(old) }>, де v(old), v(new) - старе та нове значення ОТ, які містить операція узгодження між PDSj(rk) та PDSi(rk), а ВК-правило контрольних запитів математично еквивалентно елементу <{up-up}, PDSi(rk), {Qcont, Qres}, {Ans(Qcont)№Qres}>, де Qcont - контрольний запит до БД PDSi, який перевіряє можливість виникнення конфлікта при виконанні операції узгодження ОТ, Qres - передбачена відповідь на запит Qcont, яка вказує на відсутність конфлікта.

РК-правила включають: правило регенерації операцій, правило скасування транзакції, правило комутації, функціональні правила, які базуються на компенсаційних транзакціях.

На основі представленої формалізації архітектури СУТД та ІС у вигляді їх математичних моделей запропоновано методику формування структур параметрів моделі СУТД, концептуальна схема якої зображена на рис. 1.

Методика містить набір алгоритмів, які формують структури параметрів моделі СУТД у такій послідовності: PDDS, RS, CS, RT, CMS.

В алгоритмі формування структури PDDS спочатку визначаються клієнтські групи, які об`єднуються за єдиним змістом множини Infra та мінімальним різновидом множини Constr М Info, що визначає рівні ієрархії інформаційних потреб клієнтів. Далі, з кожної клієнтської групи із використанням множини Transact, Info та LDBS формується структура множини PDS із описом рівнів ohi ієрархічної залежності між ОТ. Завдяки цьому, формується така первинна кількість та зміст локальних БД в РБД з функціональним приєднанням до них клієнтських задач, яка зменшує завантаження вузлів цими задачами. Поняття первинності змісту PDDS обумовлюється відсутністю врахування процесів узгодження РБД, яке здійснюється при вирішенні задачі гранульованого розподілу інформаційних ресурсів (ГРІР-задача).

Для формування множини RS розроблено алгоритм, на першому кроці якого будуються пари <PDSi, PDSj>: PDSi, PDSj О PDDS, i № j, PDSi З PDSj № Ж. На другому кроці для транзакцій trk = {<otkl, operkl>}ОTransact: operkl З PDSi № Ж, та транзакцій trm = {<otmn, opermn>}ОTransact: opermn З PDSj № Ж, визначається rstij = F(otkl, otmn).

Формування структури CS виконується з урахуванням максимальних вимог по узгодженості об`єктів тиражування та адекватних цим вимогам розподілених рівнів ізоляції транзакцій, що модифікують ці об`єкти. На основі аналізу існуючих СУТД з А-протоколами та функцій задач ІС різних типів введено три розподілені рівні ізоляції: детермінований рівень ізоляції (D-рівень), історичний рівень ізоляції (H-рівень), рівень ізоляції відносної похибки (RE-рівень).

Для транзакції Tri = {<otik, operik>} задачі taski = <Ti, Hi, rei> визначено умови її коректного функціонування на розподілених рівнях ізоляції, які описуються такими правилами.

Правило 1. Транзакція Tri коректно функціонує на D(D)-рівні, якщо: " Trj = {<otjm, operjm>} задачі taskj = <Dj, Hj, rej>, j№i, operjm З operik № Ж, Di З Dj = Ж.

Правило 2. Транзакція Tri коректно функціонує на H(D)-рівні ізоляції, якщо operik = <Rik, Aik, Wik>, Wik(date) Н Wik – предикат з умовами часу, та " Trj = {<otjm, operjm>}, operik = <Rjk, Ajk, Wjk>, Wik(date) Н Wik задачі taskj = <Dj, Hj, rej>, j№i, operjm З operik № Ж, Wjm(date) З Wik(date) = Ж.

Для визначення RE-рівня ізоляції введено поняття відносної похибки re(k) відхилення значень ОТ, які використовуються при формуванні документа статистичного типу, під час виконання над ним k операцій модифікації.

Правило 3. Транзакція Tri коректно функціонує на RE(k)-рівні ізоляції, якщо , operjm З operik № Ж.

Введено множину DTIL = {dtili}, елементи якої dtil О {D(D), Н(D), RE(k)} описують розподілені рівні ізоляції транзакції Tri. Алгоритм формування множини DTIL для транзакції Tri перевіряє її відповідность правилам (1, 2, 3), при задовільненні яких транзакції Tri приписується відповідний правилу рівень ізоляції dtil з включенням елемента <tri, dtil> до DTIL. Таким чином, формується зміст множини DTIL, яка описує поведінку транзакцій для забезпечення коректності результатів задач ІС.

Для формування структури CS запропоновано алгоритм, який для кожної трійки <PDSi, PDSj, rst> О RS визначає значення ctp, формуючи елементи <PDSi, PDSj, ctp, 'oper'>. Із множини Transact вибираються транзакції Trk = {<otkm, operkm>}, для яких operkm З PDSj № Ж. Кожна транзакція Trk включається в підмножину транзакцій, яка відповідає її рівню ізоляції dtilk.. В кожній сформованій непустій підмножині транзакцій визначається мінімальний ступінь рівня ізоляції, який привласнюється параметру ctp. Якщо всі підмножини пусті, то ctp = none, а процес узгодження фізичних схем PDSi, PDSj виконується C-протоколами. Таким чином, у результаті роботи алгоритма з'ясовується можливість використання A-протоколів з точки зору коректності результатів задач ІС, а ефективність іх використання з точки зору продуктивності СУТД визначається на етапі оптимізації моделі СУТД.

Визначення розподілених рівнів ізоляції транзакцій дозволяє оптимізувати потік операцій узгодження завдяки скасовунню застарілих операцій. Для аналізу можливого ступеня такого скасування введено коефіцієнт kcij допустимого зниження актуальності операцій узгодження між PDSi та PDSj :

,

де k - кількість застарілих операцій транзакцій, які виконуються на RE(k)-рівні ізоляції;

- інтенсивність операцій модифікації в PDSi;

- період розузгодження між PDSi та PDSj.

Клієнти ІС можуть входити до різних рівнів ієрархії інформаційного доступу. Ця характеристика клієнтів та фізична структура РБД з грануляцією ОТ дозволили визначити ohl-рівні ієрархічної залежності між ОТ вузлів РБД. Використання цього поняття дозволяє зменшити інтенсивність вихідних операцій узгодження ОТ i-го вузла РБД з максимальної інтенсивності до мінімальної - , де - максимальна кількість копій ОТ в РБД , , - відповідно, максимальний рівень ієрархічної залежності в РБД та рівень ієрархічної залежності ОТ в i-му вузлі.

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

,

де - вектор інтенсивності транзакцій задач клієнтів;

КС - вектор коефіцієнтів допустимого зниження актуальності операцій узгодження;

OHL - вектор рівнів ієрархічної залежності між ОТ.

Для вузлів, в яких функціонують транзакції з розподіленим рівнем ізоляції, СУТД невзмозі забезпечити подійну узгодженість РБД, якщо А-протокол тиражування приводить РБД в один з двох станів: стан неопізнанного (U-стан) та тупікового (D-стан) розузгодження. Для пошуку U-стану введено множину UC, елементи <PDSi(r),PDSj(r)> якої визначають відсутність в операції узгодження між PDSi(r), PDSj(r) та в журналі транзакцій структур даних, необхідних для роботи ВК-правил. Тобто, якщо UC№{Ж}, то U-стан не зв`явиться. Для пошуку D-стану введено граф DG = <A, W>, де AНPDS - множина вершин, W={<PDSi(r),PDSj(r)>} - множина дуг графа. Дуга <PDSi(r),PDSj(r)>ОW, якщо між операціями над PDSi(r),PDSj(r) існують конфлікти з ConfType, для яких rruleiПRrule та rrulejПRRule. Показано, що знаходження РБД у D-стані математично еквівалентно наявності циклів в графі DG.

Запропоновано ітераційний алгоритм реструктуризації PDDS, RT та RS, при яких СУТД забезпечує подійну узгодженість РБД. На першому кроці алгоритму формується множина UC. Якщо UC№{Ж}, виконується реструктуризація PDDS. Інакше будується граф DG. При наявності в графі циклів виконується пошук мінімальної реструктуризації RS та RT, яка виключає з графа дуги, що призвели до формування циклу. Якщо такої реструктуризації не знайдено, виконується повторна реструктуризація PDDS.

Запропонована методика формує структури PDDS та ReplicProtocol, які забезпечують коректність роботи СУТД, але не є оптимальними. Іх оптимізація розглядається в третьому роздіілі, де розв`язується задача гранульованого розподілу інформаційних ресурсів (ГРІР-задача).

В третьому розділі на основі математичної моделі ІС та СУТД сформульована математична постановка ГРІР-задачі та розроблено алгоритм її розв`язання.

Визначемо структуру СУТД, яка забезпечує максимальне підвищення продуктивності ІС за критерієм мінімального завантаження P вузлів РБД та мінімальної мережевої вартості C процесів узгодження вузлів.

Математична постановка ГРІР-задачі запропонована в такому вигляді. До вхідних даних задачі входять структури параметрів моделі ІС: Task, LDBS, Transact, Infra, Info, DBMS.

Необхідно визначити структури параметрів моделі СУТД: PDDS та ReplicProtocol = < RS, CS, RT, CMS >, при яких досягають мінімуму цільові функції:

а) завантаження P вузлів РБД:

(1)

де , , , , , - складники навантаження k-го вузла, що вносяться, відповідно, локальними операціями задач клієнтів, вхідними операціями узгодження РБД, процесами розв`язання конфліктів, процесами визначення адрес розсилки операцій узгодження, вихідними операціями узгодження РБД, які сформовані k-м вузлом.

б) вартості С процесу узгодження i-го та j-го вузлів РБД:

, (2)

де – вартість процесу зв`зку між i-м та j-м вузлами РБД;

– період активної роботи клієнтів i-го та j-го вузлів РБД;–

період розузгодження (роз`єднання) i-го та j-го вузлів РБД;

– вартість процесу передачі операцій узгодження між i-м та j-м вузлами РБД;

– інтенсивність операцій узгодження між i-м та j-м вузлами РБД;

– коефіцієнт зниження інтенсивності операцій узгодження між БД PDSi та PDSj.

Досягнутий оптімум цільових функцій повинен задовольняти таким обмеженням:

UC№{Ж}; (3)

DG - ациклічний граф; (4)

; (5)

де - об`єм фізичної структури PDSj , яка належить i-му вузлу;

- максимально допустимий об`єм БД, які можуть бути розташовані на i-му вузлі.

Функція (1) є математично еквівалентним описом задачі балансування завантаження вузлів, тобто задачі рівномірного розподілу завантаження клієнтів ІС по вузлах РБД.

Функція (2) є математично еквівалентним описом підзадачі мінімізації витрат на використання глобальної мережі каналів зв'язку між вузлами РБД.

Для розв`язання ГРІР-задачі в умовах багатокритеріальної оптимізації використано приведення декількох критеріїв до одного з використанням контрольних цифр. При цьому цільові функції (1) та (2) об`єднано у цільову функцію OPT , визначену як

, (6)

де , - відповідно, максимально допустимі значення середнього навантаження вузлів та вартості процесу узгодження вузлів РБД.

Задовільнення обмежень (3) та (4) вказує на існування ВК-правил та РК-правил, які при наявності конфліктів взмозі перевести РБД в несуперечливий стан, що гарантує подійну узгодженість РБД при роботі СУБД зі структурою DBMS, а СУТД - зі структурами СS, RS, RT.

Сформульована ГРІР-задача входить до класу нелінійних задач дискретного математичного програмування, обчислювальна складність розв`язання яких поліноміально залежить від розмірності. Тому для розв`язання ГРІР-задачі використано евристичний алгоритм, який базується на методі локальної оптимізації.

Алгоритм розв`язання ГРІР-задачі складається з двох етапів. На першому етапі визначається первинна структура СУТД. Для цього виконуються алгоритми формування первинної структури PDDS та ReplicProtocol, які на цьому етапі вважаються оптимальними, та визначається відповідне їм значення функції OPT, яке вважається мінімальним (OPT*).

На другому етапі алгоритма виконується перерозподіл задач клієнтів серед вузлів РБД з реструктуризацією Infra та PDDS. На першому кроці для кожного вузла РБД виконується ранжування клієнтів за іх індивідуальним навантаженням. На другому кроці послідовно в кожному i-му вузлі виділяються задачі клієнтів, які максимально завантажують вузол, і виконується їх “прив'язка” до j-го вузла (j№i). З урахуванням вимог до автономності виконання окремих задач клієнтів в рамках одного вузла, якщо при реструктуризації Infra підмножина даних, яка використовується задачами клієнта, належить фізичній схемі БД, що входить до i-го вузла, виконується реструктуризація PDDS. Після цього для вузлів, таких, що Transact З DTIL № {Ж}, виконується перевірка обмежень (3) та (4). При незадовільненні обмежень для визначення коректних структур виконується алгоритм пошуку мінімальних змін структур RS та RT. Якщо зміни структур не відбулись, виконується перехід на другий крок з метою реструктуризації PDDS. Інакше перевіряється обмеження (5), при задовільненні якого визначається значення функції OPT (OPT**). При OPT** > OPT* та при відсутності клієнтів, які ще не входили в процес перерозподілу, алгоритм завершено, інакше - перехід на другий крок.

У четвертому розділі запропоновано імітаційну модель функціонування СУТД, методику збору вхідних даних імітаційної моделі і ГРІР-задачі, наведено опис програмного забезпечення алгоритмів визначення структури СУТД і алгоритмів розв`язання ГРІР-задачі та представлено результати випробувань і проваджень в ІС СУТД, структура якої сформована в результаті розв`язання ГРІР-задачі.

Імітаційна модель розроблена у вигляді мережі массового обслуговування, яка описує взаємозв`язки між компонентами СУТД. Програмну реалізацію моделі розроблено з використанням системи Extend фірми Imagine That Inc.

Для збору вхідних даних імітаційної моделі та ГРІР-задачі запропоновано методику проведення натурних експериментів з використанням розроблених програм-генераторів транзакцій ІС. Кожний генератор імітує роботу програм користувачів ІС на рівні їх взаємодії з СУБД, виконуючи пов`язаний з цими програмами потік транзакцій.

В результаті роботи розроблено програмне забезпечення (ПЗ) СУТД для реляційної СУБД PostgreSQL, яка належить до класу малопотужних СУБД архітектури клієнт-сервер та функціонує в Unix-подібній операційній системі (ОС) Linux, та комплекс програм формування оптимальної структури СУТД. Розробка СУТД з використанням цього ПЗ, яке вільно розповсюджується, дозволила провести необхідні натурні експерименти із СУТД, яка складається з великої кількості вузлів, без обмежень на ліцензію. До того ж, в основі роботи лежать проекти ІС, які використовують це ПЗ.

Апробацію ефективності розв`язання ГРІР-задачі було проведено на прикладі ІС ОНПУ та ПДКР по Одеській області.

Для проведення експериментів в ІС ОНПУ робота її користувачів була імітована програмами-генераторами транзакцій. Було проведено експерименти з використанням трьох конфігурацій СУБД. В першій конфігурації використовувалася централізована СУБД. В другій конфігурації використовувалася структура СУТД, розроблена без розв`зання ГРІР-задачі, РБД якої містить 9 БД, розташованих на 9-ти вузлах ІС. В третій конфігурації структура СУТД розроблена в результаті розв`язання ГРІР-задачі, РБД якої містить 50 БД з ОТ трьох рівнів ієрархічної залежності (адміністрація, деканати, кафедри), які розташовані на 9-ти вузлах.

Результати натурних експериментів на реальній СУТД представлені на рис. 2. Рисунок зображує залежність коефіцієнта зниження середньго часу відгуку СУБД на запитання клієнтів від їх кількості в разі переходу з централізованої БД (перша конфігурація) до РБД (друга та третя конфігурації). Графік залежності (Стандарт) описує поведінку СУТД, структура якої розроблена з використанням існуючих методик, а графік залежності (ГРІР) описує поведінку СУТД, структура якої визначена в результаті розв`язання ГРІР-задачі. Як видно з рисунка, ефект від використання структури СУТД, визначеної при розв`язанні ГРІР-задачі, збільшується із зростаннням кількості користувачів ІС та досягає 50 %.

Для ІС ПДКР, РБД якої містить ОТ з трьома рівнями ієрархічної залежності (областний центр, пункти портової та термінальної служб), були проведені випробування на імітаційній моделі СУТД для визначення ефективності ГРІР-задачі при зростанні кількості вузлів РБД. Результати випробувань показали зменшення вартості процесів узгодження РБД на 30 % у порівнянні з існуючими методиками формування структури СУТД.

ВИСНОВКИ

1. Розглянуто ІС з властивостями систем з оперативною обробкою транзакцій і систем прийняття рішень, які мають територіальний розподіл користувачів (клієнтів), процес взаємодії яких з БД носить, переважно, детермінований характер з інформаційними запитами, які враховують ієрархічність у взаємодії між підрозділами та орієнтовані на діапазон часу. Встановлено, що для таких ІС найбільш ефективним є використання систем управління тиражуванням даних з A-протоколами тиражування. Встановлено, що для визначення A-протоколів, які забезпечують максимальний рівень продуктивності ІС та одночасно гарантують коректність результатів задач ІС, необхідно, окрім інфраструктури ІС, структури БД, враховувати також функціональну та транзакційну характеристику задач ІС.

2. Запропонована модель розширених рівнів ізоляції транзакцій, які автономно функціонують на вузлах РБД, та на її основі розроблена методика формування схеми узгодження об'єктів тиражування, адекватної вимогам задач ІС по коректності їх результатів, дозволили визначити межу коректного використання A-протоколів в СУТД.

3. Гранульований перерозподіл фізичної структури РБД з визначенням рівнів ієрархічної залежності між об`єктами тиражування та формуванням топології тиражування операцій узгодження копій об`єктів дозволив провести балансування завантаження вузлів РБД, яке забезпечує мінімальне зростання часу відгуку системи при зростанні кількості клієнтів та об`ємів БД.

4. Запропонована модель запобігання виникненню тупиково-невидимих конфліктів мiж операціями над копіями об`єктів тиражування дозволила визначити структуру СУТД, яка забезпечує автономну беззупинну роботу віддалених підрозділів з локальними БД без ризику переводу РБД до неузгодженного стану з неможливістю автоматичного узгодження РБД.

5. Запропонована структурно-функціональна модель виявлення та розв`язання ймовірних конфліктів мiж операціями над копіями об`єктів тиражування дозволила визначити правила автоматичного переводу РБД до узгодженного стану за прийнятний для задач ІС час.

6. Розроблена імітаційна модель СУТД, яка враховує параметри моделі ІС та моделі СУТД, показала ефективність запропонованої методики та відповідних алгоритмів розв`язання задачі гранульованого розподілу інформаційних ресурсів системи. Випробування структур СУТД на імітаційній моделі показали, що для ІС, в яких клієнти розподіляються між трьома та більше рівнями ієрархії доступу до інформації та використовують задачі, допустима коректність результатів роботи яких знижує актуальність операцій модифікації, використання моделі формування операцій узгодження об`єктів тиражування знижує вартість процесів узгодження РБД.

7. Результати роботи використовані при розробці ІС адміністративного управління ОНПУ, що дало змогу знизити час відгуку системи на 50 % без реконструкції апаратної частини ІС у порівнянні з існуючими алгоритмами формування структури СУТД. Впровадження результатів роботи при розробці розподіленої ІС ПДКР по Одеській області забезпечило прийнятний для користувачів час відгуку системи без додаткових витрат на використання високошвидкісних каналів зв`язку між вузлами РБД.

Список опублікованих праць за темою дисертації

8. Блажко А.А. Обнаружение и разрешение конфликтов при использовании оптимистических протоколов тиражирования // Проблемы программирования. – Киев: Ин-т программных систем, 2000. – С. 76 – 82.

9. Блажко А.А., Кунгурцев А.Б. Учет информационных связей между клиентами при построении распределенных баз данных // Труды Одесского политехнического университета. – Одесса, 1999. – Вып. 2(8). – С. 164 – 167.

10. Блажко А.А., Кунгурцев А.Б., Медведь Н.А. Анализ потоков транзакций с целью перераспределения информационных ресурсов // Вестник Харьковского государственного политехнического университета. – Харьков, 1999. – Вып. 73. – С. 19 – 23.

11. Блажко А.А. Обеспечение целостности распределенной базы данных при использовании оптимистических протоколов тиражирования // Труды Одесского политехнического университета. – Одесса, 2000. – Вып. 1(10). – С. 137 – 140.

12. Блажко А.А. Согласование автономно выполняющихся транзакций в тиражируемых базах данных // Вестник Харьковского государственного политехнического университета. – Харьков, 2000. – Вып. 81. – С. 30 – 32.

13. Блажко А.А., Кунгурцев А.Б. Согласование данных в распределенных информационных системах // Научные труды молодых ученых ОГПУ. – 1998. – № 4. – С. 126 – 132.

14. Блажко А.А. Реализация механизма тиражирования в информационной системе ОГПУ // Информационная инфраструктура высших учебных заведений. Сб. науч. тр., Санкт-Петербург, 1999. – Т.2. – С. 9 – 11.

15. Блажко А.А., Завалин А.А., Головатюк И.А. Моделирование систем управления асинхронным тиражированием данных // Комп`ютерне моделювання та інформаційні технології в науці, економіці та освіті: Збірник наукових праць: В 2-х томах. – Кривий Ріг: КДПУ, 2001. – Т. 1. – С. 20 – 25.

Блажко О.А. Оптимізаційна модель та засоби асинхронного тиражування даних для побудови систем розподіленої обробки інформації. – Рукопис.

Дисертація на здобуття наукового ступеня кандидата технічних наук за спеціальністю 05.13.06 – автоматизовані системи управління і прогресивні інформаційні технології. – Одеський національний політехнічний університет, Одеса, 2001.

Дисертація присвячена питанням проектування систем управління розподіленими базами даних з використанням асинхронних протоколів тиражуванням. В роботі виконано побудову моделі інформаційної системи, функціонально достатньої для подальшої побудови моделі системи тиражування. Запропоновано модель системи асинхронного тиражування, яка складається із структури розташування