Моделі та алгоритми оптимізації розподілених баз даних комп’ютерних інформаційних систем

Размещено на http://www.allbest.ru/

ДОНЕЦЬКИЙ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ

АВТОРЕФЕРАТ

МОДЕЛІ ТА АЛГОРИТМИ ОПТИМІЗАЦІЇ РОЗПОДІЛЕНИХ БАЗ ДАНИХ КОМП'ЮТЕРНИХ ІНФОРМАЦІЙНИХ СИСТЕМ

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

Робота виконана в Донецькому національному технічному університеті Міністерства освіти і науки України.

Науковий керівник: кандидат технічних наук, доцент Лаздинь Сергій Володимирович, доцент кафедри “Автоматизовані системи управління” Донецького національного технічного університету, м. Донецьк.

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

доктор технічних наук, професор Крулькевич Михайло Іванович, завідувач кафедри інформаційних систем управління Донецького національного університету, м. Донецьк;

кандидат технічних наук, доцент Ладиженський Юрій Валентинович, доцент кафедри прикладної математики та інформатики Донецького національного технічного університету, м. Донецьк.

Провідна установа: Харківський національний університет радіоелектроніки Міністерства освіти і науки України, м. Харків.

З дисертацією можна ознайомитись у бібліотеці Донецького національного університету за адресою: 83055, м. Донецьк, вул. Університетська, 24, гол. корп.

Автореферат розісланий “6” травня 2005 р.

Вчений секретар спеціалізованої вченої ради К 11.051.08 кандидат технічних наук, доцент Д.В. Шевцов

Загальна характеристика роботи

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

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

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

Таким чином, незважаючи на проведені дослідження, завдання оптимального розподілу даних у РБД не отримало остаточного рішення і є актуальним.

Зв'язок роботи з науковими програмами, планами, темами. Робота виконана в рамках наступних держбюджетних НДР ДонНТУ: Д-5-04 “Розробка методів моделювання та оптимізації корпоративних інформаційних систем з розподіленими базами даних” (№ державної реєстрації 0104U004059); Н-31-2000 “Розробка науково-методичних основ створення та застосування комп'ютерних інформаційних управляючих систем і технологій для наукової та навчальної роботи”, в яких автор брав участь як виконавець.

Мета роботи: Підвищення продуктивності роботи РБД комп'ютерних інформаційних систем за рахунок оптимізації розподілу даних по вузлах комп'ютерної мережі.

Для досягнення поставленої мети необхідно вирішити наступні основні завдання:

Провести системний аналіз РБД, виділити її типові компоненти. Вибрати і обґрунтувати метод моделювання РБД.

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

Обрати і обґрунтувати критерій ефективності функціонування РБД. Розробити алгоритм оптимізації розподілу даних по вузлах КІС з використанням моделі РБД.

Провести експериментальні дослідження на моделі РБД для реальної комп'ютерної інформаційної системи. За результатами аналізу показників роботи РБД розробити практичні рекомендації щодо підвищення продуктивності її роботи.

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

Розробити інструментальний засіб для аналізу характеристик і оптимізації РБД.

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

Предметом дослідження є моделі, методи та алгоритми оптимізації розподілу даних по вузлах комп'ютерних інформаційних систем.

Методи дослідження. У процесі розробки моделі РБД застосовувалися: методи системного аналізу і об'єктно-орієнтованого моделювання, мова UML; для вирішення задачі оптимізації розподілу даних - модифіковані генетичні алгоритми (ГА); для аналітичної обробки результатів моделювання - OLAP технології.

Наукова новизна отриманих результатів:

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

2. Для оцінки впливу параметрів технічних засобів і розподілу даних по вузлах комп'ютерної мережі на продуктивність системи як критерій ефективності роботи РБД вперше запропоновано використовувати сумарний середній час виконання запитів і розповсюдження оновлень.

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

4. Для визначення субоптимального розподілу даних у комп'ютерних інформаційних системах вперше разом з модифікованим генетичним алгоритмом використана об'єктна модель РБД, яка для заданого за допомогою ГА набору хромосом обчислює значення цільової функції (критерію ефективності).

Практичне значення отриманих результатів:

1. Моделювання роботи РБД дозволяє одержати оцінки тривалостей виконання запитів і розповсюдження оновлень, завантаженості каналів передачі даних і вузлів їхньої обробки, виявляти “вузькі місця”, що знижують загальну продуктивність комп'ютерних систем, і розробити практичні рекомендації з перерозподілу даних і зміни параметрів технічних засобів, що забезпечують підвищення ефективності роботи РБД.

2. Застосування модифікованого генетичного алгоритму з мультихромосомним подаванням рішень разом з об'єктною моделлю РБД дозволяє одержувати субоптимальні розподіли даних у системі (відхилення від оптимуму не більше 5%), що забезпечує підвищення продуктивності комп'ютерної системи до 30% без додаткових капітальних витрат.

3. Результати експериментальних досліджень і засновані на них практичні рекомендації щодо зміни параметрів розподіленої комп'ютерної інформаційної системи, програмний комплекс, побудований на об'єктній моделі і генетичному алгоритмі, впроваджені в ЗАТ ВО “Київ-Конті” (м. Донецьк). Їхнє використання дозволило знизити завантаження каналів передачі даних і скоротити середній час виконання запитів і розповсюдження оновлень, що забезпечило підвищення ефективності роботи РБД підприємства.

4. Результати дисертаційної роботи використані при виконанні держбюджетних НДР Д-5-04 “Розробка методів моделювання та оптимізації корпоративних інформаційних систем з розподіленими базами даних” (№ державної реєстрації 0104U004059), Н-31-2000 “Розробка науково-методичних основ створення та застосування комп'ютерних інформаційних управляючих систем і технологій для наукової та навчальної роботи” і в навчальному процесі кафедри “Автоматизовані системи управління” Донецького національного технічного університету.

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

Апробація результатів дисертації. Основні положення і результати дисертаційної роботи доповідались: на Міжнародній науково-практичній конференції “Єдиний інформаційний простір” (УДХТУ, Дніпропетровськ, 2003), VI науково-практичній міжнародній конференції “Інформаційні технології в освіті і управлінні” (ХДТУ, Нова Каховка, 2004), VI Міжнародній науково-практичній конференції “Системний аналіз та інформаційні технології” (НТУУ “КПІ”, Київ, 2004), а також обговорені і схвалені на наукових семінарах кафедр “Автоматизовані системи управління” Донецького національного технічного університету (2001 - 2005), і “Комп'ютерні технології” Донецького національного університету (2004).

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

Структура й обсяг дисертації. Дисертаційна робота складається зі вступу, п'яти розділів, висновків, списку літератури з 97 найменувань і 5 додатків, містить 55 рисунків, 25 таблиць. Загальний обсяг дисертації становить 194 сторінок, у тому числі 141 сторінок основного тексту.

Основний зміст роботи

У вступі обґрунтовано актуальність теми, сформульовано мету і завдання дослідження, наведено основні положення, що виносяться на захист.

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

Проведений огляд технологій організації РБД продемонстрував, що дані фізично розподіляються по вузлах КІС за допомогою фрагментації і реплікації (тиражування), а основними процесами, що перебігають у таких системах, є виконання запитів користувачів і розповсюдження оновлень. Аналіз можливостей сучасних СУБД (IBM DB2, Oracle, MS SQL Server, Ingress та ін.) показав, що вони забезпечують підтримку РБД, тим самим створюють передумови для широкого використання КІС з РБД.

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

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

У другому розділі побудовано загальну об'єктну модель РБД на основі моделей типових компонентів, розроблено алгоритм моделювання РБД.

У результаті проведеного системного аналізу виділені наступні типові компоненти РБД: вузол, канал передачі даних, прикладна програма, запит, таблиця. Для моделювання виділених типових компонентів РБД розроблені відповідні класи об'єктів. У процесі побудови моделей типових компонентів, їхніх взаємозв'язків і поводження застосовувалася уніфікована мова моделювання UML (Unified Modeling Language).

Розглянемо побудову об'єктних моделей типових компонентів. Для моделювання роботи вузла РБД розроблено відповідний клас об'єктів “Вузол РБД” (Node), основними властивостями якого є: продуктивність, загальний обсяг дискового простору, стан, черга обробки; і методи: обробка запиту, постановка запиту в чергу обробки, звільнення вузла. Час виконання обробки -го запиту (оновлення) на -му вузлі РБД визначається таким чином:

, (1)

де - кількість транзакцій типу TPC-C -го запиту (оновлення), , - кількість запитів (оновлень) в системі; - продуктивність -го вузла, tpmC (1/хв.), , - кількість вузлів у системі.

Клас “Канал передачі даних” (Channel) моделює роботу каналів передачі даних у процесі виконання запитів і розповсюдження оновлень. Властивостями класу є: пропускна здатність, стан, трафік, черга передачі; а методами: передача даних, постановка даних у чергу передачі, звільнення каналу. Час виконання передачі даних -го запиту (оновлення) по -му каналу визначається таким чином:

, (2)

де - обсяг даних -го запиту (оновлення), Мбайт; - пропускна здатність -го каналу передачі даних, Мбайт/с, , - кількість каналів передачі даних у системі.

Клас “Прикладна програма” (Application) моделює роботу програм, що функціонують на вузлах, та ініціюють запити та оновлення. Основні властивості класу: вузли виконання; запити, що ініціюються; математичні сподівання і дисперсії величин інтервалів між запусками прикладних програм; тривалостей їх виконання, інтервалів між моментами ініціації запитів. Методи класу: запуск прикладної програми; завершення прикладної програми; ініціація запиту. Обчислення моментів часу запуску та завершення -ї прикладної програми виконується таким чином:

, , (3)

де - поточний модельний час, с; , - значення випадкових величин: довжини інтервалу часу між запусками -ї прикладної програми і тривалості її виконання відповідно, с, , - кількість прикладних програм у системі.

Момент часу ініціації -ю прикладною програмою -го запиту (оновлення) визначається таким чином:

, (4)

де - значення випадкової величини інтервалу часу між моментами ініціації -го запиту (оновлення) -ю прикладною програмою, с.

Клас “Запит” (Query) моделює запит (оновлення) у РБД. Основними його властивостями є: підзапити, що ініціюються; математичне сподівання і дисперсія величини інтервалів часу між моментами ініціації підзапитів; обсяг запиту; складність і обсяг відповіді. Методи класу: запуск; постановка в чергу передачі; передача; постановка в чергу обробки; обробка; постановка відповіді в чергу передачі; передача відповіді; завершення запиту; ініціація підзапиту.

Клас “Таблиця РБД” (Dataset) є моделлю таблиці БД яка може бути фрагментованою. Основними його властивостями є: код таблиці; коди вузлів збереження; обсяг; код батьківської таблиці. Клас містить методи для перевірки обмежень на наявність хоча б однієї копії кожного фрагмента даних і на сумарний обсяг даних, що зберігаються на вузлі.

Загальна об'єктна модель РБД побудована як система взаємодіючих об'єктів її типових компонентів. Схема взаємозв'язків класів об'єктів моделі РБД зображена на рис. 1 у вигляді діаграми UML.

Рис. 1. Схема взаємозв'язків елементів моделі РБД

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

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

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

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

. (5)

де - кількість запитів у системі; - кількість оновлень у системі; - час виконання -го запиту, ; - час розповсюдження -го оновлення даних, .

Припустимо, що розглянута РБД є множиною фрагментів даних

де - кількість фрагментів даних у системі; які за допомогою фрагментації і реплікації розподілені на множині вузлів , з'єднаних множиною каналів передачі даних . На вузлах функціонує множина прикладних програм , які ініціюють виконання запитів і розповсюдження оновлень. Схема розподілу даних у РБД визначається матрицею , елементи якої набувають наступних значень:

У процесі функціонування РБД зі схемою розподілу, представленою матрицею , породжується множина запитів і множина оновлень для елементів яких визначені функції - час виконання запиту , ; - час розповсюдження оновлення , .

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

(6)

Часи виконання запитів і розповсюдження оновлень обчислюються за допомогою об'єктної моделі РБД.

Під час обчислення значень критерію (6) необхідно враховувати обмеження:

1. У РБД повинна бути присутня хоча б одна копія кожного фрагменту даних:

, (7)

де - елементи матриці схеми розподілу , .

2. Сумарний обсяг даних, що зберігаються на вузлі, не повинен перевищувати загальний дисковий простір даного вузла:

, (8)

де - обсяг -го фрагменту даних, ; - дисковий простір -го вузла, ;

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

, (9)

де - гранично допустимий час виконання запитів.

Ця задача є задачею оптимізації з дискретними змінними. Множина її рішень є счисленною і скінченною, в зв'язку з цим вона належить до класу комбінаторних задач. Кількість можливих рішень визначається виразом , де - кількість вузлів РБД; - кількість фрагментів даних, які необхідно розподілити по вузлах мережі.

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

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

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

Рис. 2. Схема взаємодії моделі РБД із ГА

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

Кожна хромосома є вектором бінарних значень, довжина якого дорівнює кількості фрагментів даних, які підлягають розподілу (рис. 3). Елементи матриці приймають значення “1”, якщо копія відповідного фрагменту даних знаходиться на вузлі, і “0” в іншому випадку. Таким чином, кожна хромосома кодує розміщення фрагментів даних на окремо взятому вузлі. Весь набір хромосом цілком кодує схему розміщення даних у РБД.

Рис. 3. Структура мультихромосоми

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

З урахуванням специфіки розв'язуваної задачі для ГА використані наступні стандартні оператори ГА: схрещування з двома точками розриву, відбір методом рулетки і мутація з заданою ймовірністю.

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

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

Для проведення експериментальних досліджень з використанням розробленої моделі і алгоритму оптимізації як об'єкт обрана комп'ютерна інформаційна система ЗАТ ВО “Київ-Конті”. Це підприємство є крупним виробником кондитерської продукції, входить у трійку лідерів вітчизняного кондитерського ринку і займає перше місце за темпами зросту обсягів виробництва (за інформацією сайту http://www.-kiev-konti.com). До складу компанії “Київ-Конті” входять 4 фабрики: - три в Україні (Донецька, Костянтинівська, Горлівська) і одна в Росії (Курська). Компанія має розподілену систему збуту, що складається з п'яти філій (складів продукції), з них чотири в Україні - у м. Донецьк, Київ, Львів, Миколаїв, і одна філія в Росії - м. Воронеж, а також кілька регіональних представництв (рис. 4).



Рис. 4. Вузли РБД комп'ютерної інформаційної системи “Київ-Конті”

За допомогою розробленої об'єктної моделі було проведено обчислювальні експерименти з метою аналізу роботи РБД і виявлення “вузьких місць” системи. Значення критерію ефективності (6) сумарного середнього часу виконання запитів і розповсюдження оновлень у системі, розраховане за допомогою моделі РБД, склало 111,77 с.

Аналіз середнього часу виконання запитів показав, що найбільший час виконання мають запити, що ініціюються на вузлах “Філія. Київ” і “Філія. Миколаїв”, та запити, які звертаються до таблиць, що зберігається на цих вузлах (рис. 5). Це пов'язано з тим, що при передачі даних використовуються повільні канали, що комутуються, зі швидкістю передачі 33,6 Кбіт/с, а також - з нераціональним розподілом даних по вузлах системи.



Рис. 5. Оцінки часу виконання запитів

Аналіз коефіцієнтів завантаження каналів передачі даних (рис. 6) показав, що найбільший коефіцієнт завантаження мають канали, що з'єднують Київську і Миколаївську філії з Центральним вузлом. Це пояснюється тим, що ними передаються досить великі обсяги даних, але при цьому вони є такими, що комутуються і мають невелику пропускну здатність.

Рис. 6. Коефіцієнти завантаження каналів передачі даних

Проведені на моделі РБД експерименти показали, що збільшення пропускної здатності цих каналів з 33,6 до 64 Кбіт/с дозволяє зменшити значення критерію ефективності РБД із 111,77 с до 94,87 с, що на 15,12%.

Раціональний перерозподіл таблиць і фрагментів даних, до яких звертаються зазначені запити (оновлення), призводить до збільшення продуктивності РБД, та зменшення часу відклику системи. Моделювання РБД показало, що після видалення копій фрагментів таблиці “Прихід/Витрати” з вузлів філій м. Києва і м. Миколаєва, коли ця таблиця залишається тільки на корпоративному сервері, середній час виконання запитів і розповсюдження оновлень зменшився ще на 18,19% і склав 77,61 с.

Таким чином, проведені за допомогою моделі РБД дослідження дозволили виявити в комп'ютерній системі “вузькі місця” і розробити практичні рекомендації, що забезпечують збільшення продуктивності роботи РБД на 30,56% при мінімальних витратах коштів.

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

Порівняння отриманих з його допомогою субоптимальних рішень проводилося з оптимумом, отриманим повним перебором. За допомогою процедури повного перебору було отримано мінімальне значення критерію ефективності , що склало 79,1 с. Час, витрачений на пошук оптимуму, склав приблизно 17 діб.

Проведено аналіз впливу величини розміру популяції і кількості поколінь на значення критерію ефективності роботи РБД (рис. 7). Аналіз отриманих залежностей продемонстрував, що доцільно прийняти значення, що забезпечують найбільше наближення до оптимуму,: розмір популяції і кількість поколінь .

Залежність значення критерію ефективності РБД (6) від ймовірностей застосування оператора рекомбінації і схрещування подано на рис. 8. З графіку видно, що значення, при яких спостерігається більше наближення одержуваних субоптимальних рішень до глобального мінімуму складають: і .

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

Рис. 7. Залежність критерію ефективності РБД від розміру популяції і кількості поколінь

Рис. 8. Залежність критерію ефективності РБД від ймовірностей застосування оператора рекомбінації і схрещування

Рис. 9. Залежність критерію ефективності РБД від ймовірностей застосування операторів мутації і рекомбінації



Рис. 10. Залежність критерію ефективності РБД від ймовірностей застосування операторів мутації і схрещування

У результаті, при визначених раніше параметрах ГА, було отримано найкраще субоптимальне значення критерію ефективності, яке становить 82,19 с. Абсолютне відхилення цієї величини від глобального мінімуму складає 3,09 с, відносне відхилення - 3,76%. При цьому зменшення сумарного середнього часу виконання запитів і розповсюдження оновлень у порівнянні зі значенням, отриманим при вихідному розподілу даних (111,77 с), склало 29,58 с чи 26,47%. Час пошуку субоптимального рішення з використанням ГА на ПЕОМ з процесором Intel Celeron 2,8 GHz складає 1 - 2 хв.

У п'ятому розділі наведено опис розробленого на підставі отриманих результатів дослідження програмного комплексу моделювання й оптимізації РБД, розглянуто результати його тестування і впровадження.

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

Рис. 11. Структура програмного комплексу моделювання й оптимізації РБД

Для розробки програмного комплексу використовувалися: засіб візуальної розробки додатків Borland C++ Builder; а також програмні продукти Microsoft: Access, Analysis Services, Excel.

Підсистема моделювання є програмною реалізацією розробленої об'єктної моделі РБД. Модель реалізована з використанням C++ Builder, для збереження вихідних даних і результатів моделювання використана СУБД Microsoft Access.

Підсистема аналізу результатів моделювання розроблена з використанням OLAP технології. Як OLAP сервер обрано Microsoft Analysis Services, як OLAP клієнт - Microsoft Excel. Для створення сховища даних з результатами моделювання на основі результатів моделювання використовуються засоби Microsoft Access.

Підсистема оптимізації розподілу даних складається з двох блоків. Перший - програмна реалізація оптимізаційного алгоритму на основі ГА, що дозволяє знаходити субоптимальне рішення, а другий - програмну реалізацію процедури повного перебору, що дозволяє знаходити глобальний оптимум задачі.

Перевірка правильності роботи розробленого програмного комплексу здійснювалась на реальних даних РБД комп'ютерної інформаційної системи ЗАТ ВО “Київ-Конті”. Отримані результати використані при модернізації комп'ютерної інформаційної системи ЗАТ ВО “Київ-Конті”, що дозволило підвищити її продуктивність, зменшити середній час відгуку системи на запити користувачів при мінімальних витратах коштів.

Висновки

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

Під час проведення дослідження отримані наступні основні результати:

1. Розроблено об'єктні моделі типових компонентів РБД: вузол, канал передачі даних, прикладна програма, запит, таблиця; для кожного класу об'єктів визначені їхні властивості і методи. Побудовано загальну модель РБД як систему взаємодіючих об'єктів її типових компонентів, що дозволяє моделювати процеси виконання запитів і розповсюдження оновлень.

2. Розроблено модифікований генетичний алгоритм, що забезпечує пошук субоптимального розподілу даних у системі, у якому використані мультихромосомне представлення рішень і оператор рекомбінації, а також стандартні оператори ГА: відбору, схрещування і мутації.

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

4. У результаті моделювання роботи розподіленої бази даних ЗАТ ВО "Київ-Конті" встановлено, що “вузькими місцями”, які знижують загальну продуктивність системи, є канали передачі даних у м. Київ і м. Миколаїв і нераціональне розміщення даних, що зумовлює велику тривалість виконання запитів і оновлень на цих вузлах. Для усунення цих недоліків запропоновано: підвищити пропускну здатність цих каналів з 33,6 до 64 Кбіт/с, що дозволяє зменшити сумарний середній час виконання запитів і розповсюдження оновлень на 15,1%; перерозподілити дані в системі, що дозволяє підвищити продуктивність РБД ще на 18,2%. Таким чином, за рахунок зміни параметрів РБД сумарний середній час виконання запитів і оновлень зменшився з 111,77 с до 77,16 с, чи на 30,56%.

5. Для модифікованого генетичного алгоритму визначено раціональні значення його параметрів: розмір популяції - 60, кількість поколінь - 20, ймовірності рекомбінації - 0,5, схрещування - 0,6, мутації - 0,07, при яких забезпечується визначення близького до оптимального значення критерію ефективності РБД. При цьому відхилення субоптимального значення від оптимуму, отриманого шляхом повного перебору, складає 3,76%, а сумарний середній час виконання запитів і розповсюдження оновлень зменшується з 111,77 с до 82,19 с, чи на 26,47% без додаткових матеріальних витрат, за рахунок оптимізації розміщення даних.

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

7. Розроблено практичні рекомендації щодо зміни параметрів РБД, програмний комплекс впроваджені в ЗАТ ВО "Київ-Конті" м. Донецьк і використані для модернізації комп'ютерної інформаційної системи підприємства, що дозволило підвищити її продуктивність, зменшити середній час виконання запитів і оновлень.

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

1. Лаздынь С.В., Телятников А.О. Динамическая модель распределенной базы данных компьютерной информационной системы // Наукові праці ДонДТУ. - Випуск 38. - Донецьк: РВА ДонДТУ, 2002. - С. 115-121.

2. Телятников А.О. Разработка объектной модели распределенной базы данных // Наукові праці ДонНТУ. Випуск 74. - Донецьк: ДонНТУ, 2004. - С. 192-200.

3. Лаздынь С.В., Телятников А.О. Оптимизация распределенных баз данных с использованием генетических алгоритмов // Вестник ХГТУ. - Херсон: ХГТУ, 2004. - № 1(19). - C. 236-239.

4. Телятников А.О. Моделирование и анализ работы распределенной базы данных с использованием объектно-ориентированного подхода // Наукові праці ДонНТУ. Випуск 90. - Донецьк: ДонНТУ, 2005. - С. 91-98.

5. Лаздынь С.В., Телятников А.О. Повышение эффективности распределенных баз данных с использованием объектно-ориентированного моделирования и генетических алгоритмов // Единое информационное пространство: Сб. докл. Междунар. научно-практич. конф. - Днепропетровск: ИПК ИнКомЦентра УГХТУ, 2003. - С. 23-26.

6. Лаздынь С.В., Телятников А.О. Новый подход к оптимизации распределения данных в компьютерных информационных системах // Тези доповідей учасників VI Міжнародної науково-практичної конференції “Системний аналіз та інформаційні технології”. - Київ: НТУУ “КПІ”, 2004. - С. 222-224.

Особистий внесок автора в публікаціях: [1] - дослідження РБД як об'єкту моделювання, визначення основних типових компонентів РБД, розроблення динамічної моделі РБД із застосуванням об'єктно-орієнтованого підходу; [3] - постановка задачі оптимізації РБД, обрання і обґрунтування критерію ефективності РБД, розроблення модифікованого генетичного алгоритму; [5] - розроблення об'єктної моделі РБД, використання апарату ГА для оптимізації розподілу даних, розроблення мультихромосомного кодування схеми розподілу даних, розроблення схеми взаємодії об'єктної моделі РБД із ГА; [6] - обґрунтування нового підходу до оптимізації РБД, заснованого на спільному використанні модифікованого ГА й об'єктної моделі РБД.

Анотація

Телятніков О.О. Моделі та алгоритми оптимізації розподілених баз даних комп'ютерних інформаційних систем. - Рукопис.

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

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

Аннотация

Диссертация на соискание ученой степени кандидата технических наук по специальности 05.13.06 - “Автоматизированные системы управления и прогрессивные информационные технологии”. Донецкий национальный университет, Донецк, 2005 г.

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

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

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

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

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

Annotation

Telyatnikov A.O. Optimization models and algorithms of the distributed databases of computer information systems. The manuscript.

The dissertation on competition of a scientific degree of Candidate of Tech-nical Sciences on a specialty 05.13.06 - “Automated control systems and progressive information technologies”. - Donetsk National University, Donetsk, 2005.

There is a new solution given in the dissertation of a current importance scientific problem of the distributed databases of computer information systems performance increase by optimizing the data distribution among the nodes of the computer network. The distributed databases performance is estimated by criterion of minimization of the total average time of queries processing and updates spreading. The object model of the distributed database as a system of interacting objects of its typical components is developed. The modified genetic algorithm with multichromosomal decisions coding is developed, providing the search of suboptimum data distribution in the system. The work results are used to determine the technical parameters of the distributed database and its performance increase by data redistribution among the nodes of the network.

Размещено на Allbest.ru

...