ПРОБЛЕМИ РОЗПОДІЛЕНИХ СИСТЕМ

У цьому розділі докладно розглядаються проблеми, які згадувалися в розділі 213 Ключова проблема розподілених систем полягає в тому, що комунікаційні мережі, принаймні, мережі, які охоплюють велику територію, або глобальні мережі, поки залишаються повільними Звичайна глобальна мережа найчастіше має середню швидкість передачі даних від 5 до 10 тисяч байтів в секунду Звичайний же жорсткий диск має швидкість обміну даними близько 5-10 мільйонів байтів в секунду (З іншого боку, деякі локальні мережі підтримують швидкість обміну даними того ж порядку, що і диски) Тому основне завдання розподілених систем (щонайменше, у разі глобальної мережі, а також до деякої міри і в разі локальної мережі) – мінімізувати використання мереж, тобто мінімізувати кількість і обсяг переданих повідомлень Вирішення цього завдання, в свою чергу, утруднюється изза проблем в декількох додаткових областях Нижче наведено список таких областей, хоча не можна гарантувати, що він є повним

■ Обробка запитів

■ Управління каталогом

■ Поширення оновлень

■ Управління відновленням

■ Управління паралельністю

Обробка запитів

Щоб вирішити завдання мінімізації використання мережі, процес оптимізації запитів повинен бути розподіленим, як і процес виконання запитів Інакше кажучи, в загальному випадку процес оптимізації буде включати етап глобальної оптимізації, за яким підуть етапи локальної оптимізації на кожному що бере участь вузлі Наприклад, припустимо, що запит Q переданий на виконання на вузол X, і припустимо, що запит Q потребує зєднання відносини Ry на вузлі Y, що містить 10 тис кортежів, з відношенням Rz на вузлі z, що містить 10 млн кортежів Оптимізатор на вузлі х повинен вибрати глобальну стратегію виконання запиту Q У даному випадку очевидно, що було б вигідніше переслати ставлення Ry на вузол Z, а не ставлення Rz на вузол Y (або, залежно від кардинальності результату зєднання, може виявитися, що краще переслати і ставлення Ry, і ставлення Rz на вузол X) Припустимо, що вирішено переслати дані відносини Ry на вузол Z, тому реальна стратегія виконання зєднання на вузлі Z визначатиметься локальним оптимізатором цього вузла

Наведена нижче більш детальна ілюстрація розглянутого підходу заснована на прикладі, взятому з однією з ранніх статей ротного (Rothnie) і Гудмана (Goodman) [2131]

Примітка Фактично наведені тут дані тепер трохи застаріли у звязку

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

■&nbsp&nbsp&nbsp&nbsp База даних постачальників і деталей (Спрощена)

,, . S {S #, CITY} 10 000 збережених кортежів на вузлі А Р {Р #, COLOR} 100 000 збережених кортежів на вузлі В SP {S #, Р #} 1 000 000 збережених кортежів на вузлі А

Припустимо, що кожен бережене кортеж має довжину 25 байт (200 біт)

■&nbsp&nbsp&nbsp&nbsp Запит (Отримати номери лондонських постачальників деталей червоного кольору)

( ( S JOIN SP JOIN P ) WHERE CITY = London AND

COLOR = COLOR (Red) ) { S# }

■&nbsp&nbsp&nbsp&nbsp Оцінка кардинальності деяких проміжних результатів

Кількість поставок, виконаних постачальниками з Лондона 100 000

■&nbsp&nbsp&nbsp&nbsp Передбачувані параметри ліній передачі даних

000 біт / с Затримка доступу                                                                                                                                                                                                                                                                        0,1 з

Тепер коротко розглянемо шість можливих стратегій виконання цього запиту, і для кожної стратегії i розрахуємо загальний час Ti передачі даних за такою формулою:

(Загальна затримка доступу) +

(Загальний обсяг даних / швидкість передачі даних)

У цьому випадку вона зводиться до такої формули (час у секундах):

(Кількість повідомлень / 10) + (кількість бітів / 50000)

Пересилання записів про деталі на вузол А і обробка запиту на вузлі А

Т [1] = 0,1 + (100000 * 200) / 50000

= 400 с (приблизно 6,67 хв)

Пересилання записів про постачальників і постачаннях на вузол В і обробка запиту на вузлі В

Т [2] = 0,2 + ((10000 + 1000000) * 200) / 50000 = 4040 с (приблизно 1,12 ч)

Зєднання відносин постачальників і поставок на вузлі А, скорочення результату для отримання даних лише про постачальників з Лондона з подальшою перевіркою на вузлі в кожного обраного постачальника відповідних деталей для визначення того, чи має деталь червоний колір Кожна з таких перевірок вимагає передачі двох повідомлень – запиту і відповіді Час передачі цих повідомлень буде мало порівняно із затримкою доступу

Т [3] = 20000 с (приблизно 5, 5, 6 год) Скорочення даних про деталі на вузлі в для визначення тільки тих деталей, які мають червоний колір, а потім для кожної з обраних деталей перевірка на вузлі А наявності поставок, що повязують цю деталь з постачальником з Лондона Кожна з таких перевірок вимагає передачі двох повідомлень Час передачі цих повідомлень також буде мало в порівнянні з затримкою доступу

Т [4] = 2 с (приблизно) Зєднання відносин постачальників і поставок на вузлі А, скорочення результату для отримання даних лише про постачальників з Лондона, отримання проекції цих результатів за атрибутами s # і Р # і пересилання результату на вузол в Завершення обробки на вузлі в

Т [5] = 0,1 + (100000 * 200) / 50000

= 400 с (приблизно 6,67 хв)

Скорочення даних про деталі на вузлі в для отримання відомостей лише про тих деталях, які мають червоний колір, і пересилання результату на вузол А Завершення обробки на вузлі А

Т [6] = 0,1 + (10 * 200) / 50000 = 0,1 с (приблизно)

У табл 211 підведені підсумки за результатами обробки різних варіантів запиту

Нижче наведені коментарі до цих результатів

■ Кожна з шести стратегій являє можливий підхід до проблеми, але откло нения за часом передачі даних величезні Найбільше час в два мільйони разів більше, ніж найменше

■ Швидкість обміну даними і затримки доступу – важливі фактори у виборі стратегії

■ Для поганих стратегій час обчислень і введення-виведення мізерно мало порівня нению з часом передачі даних

Примітка Фактично для найкращих стратегій це співвідношення може залежати від додаткових обставин [2133] Така велика розбіжність може також не спостерігається у випадку використання швидких локальних мереж,,

838     Частина V Додаткові теми

Крім того, деякі стратегії дозволяють виконувати паралельну обробку на

Таблиця 211 Можливі стратегії розподіленої обробки запиту (зведення)

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

Управління каталогом

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

1&nbsp Централізоване зберігання Єдиний загальний каталог зберігається на окремому центральному вузлі

2&nbsp Повна реплікація Загальний каталог цілком зберігається на кожному вузлі

3&nbsp Часткове секціонування Кожен вузол підтримує власний каталог для обєктів, які на ньому зберігаються Загальний каталог являє собою обєднань ня всіх цих непересічних локальних каталогів

4&nbsp Поєднання підходів 1 і 3 На кожному вузлі підтримується свій локальний каталог, як передбачено в підході 3 Крім того, окремий центральний вузол опору вождающейся обєднану копію всіх цих локальних каталогів, як передбачено в підході 1

Кожен підхід має свої недоліки При підході 1 очевидно порушується принцип відсутності залежності від центрального вузла. При підході 2 значною мірою втрачається незалежність вузлів, оскільки всяке оновлення каталогу має поширюватися на кожен вузол При підході 3 нелокальні операції стають занадто дорогими (для пошуку віддаленого обєкта потрібно доступ в середньому до половини всіх вузлів) Підхід 4 ефективніший порівняно з підходом 3 (для пошуку віддаленого обєкта потрібно доступ лише до одного віддаленого каталогу), але в цьому випадку знову порушується принцип відсутності залежності від центрального вузла Тому

на практиці в системах зазвичай не використовується жоден з цих чотирьох підходів

Як приклад розглянемо підхід, який застосовується в системі R * [2137]

Перш ніж описати структуру каталогу системи R *, необхідно сказати кілька слів про механізм іменування обєктів у цій системі Присвоєння імен обєктам –

це взагалі дуже важливе питання для розподілених систем Оскільки два окремих вузла X і У можуть мати обєкт (скажімо, базову змінну відносини) з одним і тим же імям, припустимо, R, потрібно певний механізм (зазвичай – уточнення за допомогою імені вузла) для того, щоб усунути неоднозначність, тобто гарантувати унікальність імені в межах всієї системи Але, якщо уточнені імена, такі як ХR і

R, надаватимуться системою користувачеві, буде порушено вимогу незалежності від розміщення Тому необхідні засоби відображення імен для користувача у відповідні системні імена

Тепер викладемо підхід до розглянутої проблеми, прийнятий в системі R * У цій системі розрізняються вводяться імена, за допомогою яких користувачі зазвичай звертаються до обєктів (наприклад, в конструкції SELECT мови SQL), і загальносистемні імена, які представляють собою глобально унікальні внутрішні ідентифікатори

для цих же обєктів Загальносистемні імена мають чотири описаних нижче компонента

■&nbsp&nbsp&nbsp&nbsp Ідентифікатор творця, тобто ідентифікатор користувача, який вперше викликав на виконання операцію CREATE для створення даного обєкту

■&nbsp&nbsp&nbsp&nbsp Ідентифікатор вузла творця, тобто ідентифікатор вузла, на якому була введена відповідна операція CREATE

■&nbsp&nbsp&nbsp&nbsp Локальне імя, тобто неуточнене імя обєкта

■&nbsp&nbsp&nbsp&nbsp Ідентифікатор вузла походження, тобто ідентифікатор вузла, на якому обєкт зберігався спочатку

Ідентифікатори користувача унікальні на вузлі, тоді як ідентифікатори вузла унікальні глобально Розглянемо, наприклад, таке общесистемное імя

MARILYN @ NEWYORK STATS @ LONDON

Воно позначає обєкт (для визначеності будемо вважати, що це – базова змінна відносини) з локальним імям STATS, створений користувачем MARILYN на вузлі в Нью-Йорку і спочатку збережений на вузлі в Лондоне3 Це імя гарантовано захищене від будь-яких змін, навіть якщо обєкт надалі буде переміщений на інший вузол (див нижче)

Як вже вказувалося, користувачі зазвичай посилаються на обєкти з допомогою вводяться імен Введене імя, як показано нижче, являє собою просте, неуточнене імя – або компонент локальне імя загальносистемного імені (у наведеному вище прикладі – STATS), або синонім для цього загальносистемного імені, який в системі R * визначається за допомогою спеціального оператора CREATE SYNONYM

CREATE SYNONYM MSTATS FOR MARILYN @ NEWYORK STATS @ LONDON

3 В системі R * базові змінні відносини відображаються безпосередньо на збережені змінні відносини А фактично такий підхід застосовується майже у всіх системах, відомих автору Деякі критичні зауваження з приводу зазначеного стану справ наведені у додатку А

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

SELECT .. FROM STATS .. SELECT .. FROM MSTATS ..

У першому випадку, тобто при використанні локального імені, система буде виходити з того, що всі компоненти загальносистемного імені визначаються за замовчуванням, а саме – що обєкт створений даним користувачем, створений на даному вузлі і збережений на даному вузлі До речі, завдяки такому допущенню за замовчуванням старі додатки системи System R можуть виконуватися без будь-яких виправлень у новій версії системи R * (тобто після перевизначення даних системи System R для системи R *)

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

Крім таблиць синонімів, на кожному вузлі підтримуються описані нижче дані

1 Запис каталогу для кожного обєкта, місцем створення якого є зазначений ний вузол

2 Запис каталогу для кожного обєкта, зберігається в даний час на даному вузлі

Припустимо тепер, що користувач видав запит, що містить посилання на синонім MSTATS Спочатку система виконає пошук відповідного загальносистемного імені у відповідній таблиці синонімів (виключно локальний перегляд) Після того як стане відомий вузол створення (у нашому прикладі це вузол у Лондоні), можна буде опитати каталог вузла в Лондоні (тут ми для спільності увазі віддалений перегляд – Перша віддалене звернення) Каталог вузла з Лондона буде містити запис для обєкта відповідно до п 1 Якщо обєкт і раніше зберігається на вузлі в Лондоні, він буде знайдений Однак, якщо обєкт переміщений, скажімо, на вузол в ЛосАнджелесе, запис каталогу на вузлі в Лондоні буде містити відомості про це і система повинна буде опитати каталог на вузлі в Лос-Анджелесі (друге віддалене звернення) Каталог на вузлі в Лос-Анджелесі буде містити запис для шуканого обєкта згідно п 2 Таким чином, для пошуку обєкта буде виконано не більше двох віддалених звернень

Крім того, якщо обєкт знову буде потрібно перемістити, скажімо, на вузол в СанФранциско, системою будуть виконані такі дії

■ Вставка запису в каталог на вузлі в Сан-Франциско

■ Видалення запису з каталогу на вузлі в Лос-Анджелесі

■ Оновлення запису каталогу на вузлі в Лондоні, який тепер буде вказувати на вузол в Сан-Франциско замість вузла в Лос-Анджелесі

У результаті обєкт завжди може бути знайдений з допомогою не більше двох віддалених звернень І це повністю розподілена схема – немає ніякого вузла з основним каталогом і немає ніякого єдиного джерела відмови всередині системи

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

Поширення оновлень

Основна проблема реплікації даних, як вказувалося в розділі 213, полягає в тому, що оновлення будь-якого заданого логічного обєкта має поширюватися по всіх збереженим копіям цього обєкта Складнощі, які негайно виникають в цьому випадку, полягають у тому, що деякий вузол, що містить копію даного обєкта, в момент поновлення може виявитися недоступним, оскільки сталася відмова вузла або мережі під час оновлення Таким чином, очевидна стратегія негайного розповсюдження оновлень по всім існуючим копіям буде, ймовірно, є неприйнятною, оскільки вона має на увазі, що будь-яка операція оновлення, а значить, і вся включає її транзакція, закінчиться аварійно, якщо одна із потрібних копій в момент оновлення виявиться недоступною У якомусь сенсі при цій стратегії дані будуть менше доступними, ніж за відсутності реплікації Таким чином, зникає одне з головних переваг реплікації, яке вказувалося в попередньому розділі

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

■ Одна копія для кожного реплицируемой обєкта встановлюється як первинна

копія, а всі залишилися копії – як вторинні

■ Первинні копії різних обєктів знаходяться на різних вузлах (тому дана схема також є розподіленою)

■ Операції поновлення вважаються логічно завершеними, як тільки оновлена ​​первинна копія Вузол, що містить таку копію, відповідатиме за поширеною ня поновлення на вторинні копії протягом деякого подальшого часу укладання

■&nbsp&nbsp&nbsp&nbsp Примітка Це подальший час, тим не менш, має передувати опера ції завершення транзакції COMMIT, якщо повинні гарантуватися властивості ACID розподілених транзакцій (див глави 15 і 16) Додаткові зауваження з цього питання будуть наведені нижче

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

Як вже вказувалося, внаслідок вимоги гарантії дотримання властивостей ACID транзакцій, весь процес розповсюдження оновлень має бути завершений перш, ніж відповідна транзакція може бути зафіксована  {Синхронна реплікація) Однак кілька комерційних продуктів підтримують менш сувору форму реплікації, в якій поширення оновлень відкладається на пізніший час (можливо, на деякий вказуване користувачем час), а НЕ обовязково виконується в рамках відповідної транзакції {Асинхронна реплікація) Безумовно, що визначення терміна реплікація, на жаль, носить на собі в тій чи іншій мірі

відбиток властивостей цих продуктів, в результаті чого, принаймні, на комерційному ринку, під ним майже завжди мається на увазі, що поширення оновлень відкладається до тих пір, поки відповідна транзакція не завершиться (наприклад, див [211], [2116] і [2118]) Недолік подібного підходу з затримкою розповсюдження оновлень полягає, безумовно, у тому, що база даних не може більше гарантувати узгодженості всіх її даних у будь момент4 Насправді, користувач навіть може не знати, чи узгоджена база даних

Завершуючи цей підрозділ, наведемо кілька наведених нижче додаткових зауважень щодо підходу з затримкою розповсюдження оновлень

1 Концепція реплікації в системі з затримкою розповсюдження оновлень мо же розглядатися як застосування ідеї знімків, мова про які йшла в главі 10 Насправді, для позначення такого виду реплікації краще було б вико ристовувати інший термін Тоді можна було б зберегти термін репліка для обо значення того, що розуміється під ним у звичайному сенсі (а саме – точна копія) Але слід зазначити, що знімки розглядаються як призначені тільки для читання (не рахуючи їх періодичного оновлення), тоді як некото рие системи дозволяють користувачам оновлювати такі репліки безпосередньо (див [2118]) Безумовно, останній варіант являє собою порушення прин ципу незалежності від реплікації

2 Ми не стверджуємо, що затримка розповсюдження оновлень – погана ідея

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

3 Одна з причин (можливо, навіть головна причина), по якій реплікація в комерційних продуктах реалізована із затримкою поширення, укладає ся в наступному: альтернатива, тобто оновлення всіх дублікатів перед виконан ням операції COMMIT, вимагає підтримки двухфазной фіксації транзакції (див наступний підрозділ), що може істотно вплинути на виробник ність системи Саме по цієї причини в компютерних журналах іноді зустрі чаются статті з спантеличують назвами, такими як Реплікація або двох фазна фіксація” (Спантеличують, оскільки в них фактично порівнюються характеристики двох принципово різних підходів)

4 Безумовно, якщо всі операції перевірки цілісності виконуються негайно (див глави 9 і 16), то такі ситуації стають неможливими І навіть якщо така перевірка відкладається до етапу виклику оператора COMMIT (а такий підхід розглядається нами як логічно неправильний, але застосовується в багатьох системах), подібні ситуації не виникатимуть Тому, в певному сенсі, відкладене поширення можна розглядати як ще більш логічно неправильний підхід, ніж відкладену перевірку (якщо тільки можна міркувати в термінах більш або менш неправильного)

Управління відновленням

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

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

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

ний, а значить, додаткове навантаження на комунікації

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

Розглянемо повторно процес двухфазной фіксації транзакцій, описаний раніше, в главі 15 Звернімося до рис 214, на якому показано взаємодію між координатором і звичайним учасником Для спільності припустимо, що координатор і учасник знаходяться на різних вузлах, крім того, на даному малюнку вісь часу спрямована зліва направо (але іноді тимчасова послідовність порушується) До того ж для спрощення припустимо, що в транзакції затребувано виконання операції COMMIT, а не ROLLBACK Після отримання запиту на операцію COMMIT координатор організовує наступний описаний нижче двофазний процес

■ Кожному учаснику координатор віддає розпорядження приготуватися до фіксації або відкоту транзакції На рис 214 показано повідомлення приготуватися, відправлене в момент t1 і отримане учасником у момент t2 Далі учасник примусово поміщає запис в журнал локального агента зі свого фізичного журналу, а потім видає координатору підтвердження ОК. Безумовно, якщо виникне якась помилка (Зокрема, якщо відбудеться збій у роботі локального агента), буде передано повідомлення Not OK. На малюнку це повідомлення, яке для простоти позначено як ОК, відправлено в момент t3 та отримано координатором в момент t4 Як вже зазначалося вище, учасник тепер втрачає автономність: він повинен робити те, що йому буде наказувати координатор Крім того, будь-які ресурси, які заблоковані локальним агентом, повинні залишатися заблокованими до тих пір, поки учасник не отримає і не виконає розпорядження координатора

■ Після отримання підтвердження від усіх учасників координатор приймає рішення або зафіксувати транзакцію, якщо всі відповіді були ОК, або виконати відкат транзакції в іншому випадку Потім у момент t5 координатор вносить до свого фізичний журнал запис про прийняте рішення Час t5 служить кордоном між першою і другою фазами фіксації транзакції

■ Будемо вважати, що було прийнято рішення про фіксації транзакції У цьому випадку координатор віддасть розпорядження всім учасникам виконати, тобто запустити обробку операції фіксації для локального агента На рис 214 показано повідомлення виконати, відправлене в момент t6 і отримане учасником у момент t7 Учасник виконує операцію фіксації для локального агента і відправляє підтвердження виконано координатору На малюнку підтвердження відправлений координатору в момент t8 та отримано координатором в момент t9

ш Після того як координатором будуть отримані всі підтвердження, процес повністю завершується

Рис 214 Двофазна фіксація транзакції

На практиці, безумовно, цей процес в цілому значно складніше, ніж описано вище, оскільки необхідно ще подбати про можливі відмови вузла або мережі, які можуть відбутися в будь-який момент Припустимо, наприклад, що на вузлі координатора збій стався в деякий момент t між відмітками часу t5 і t6 У процесі відновлення роботи вузла процедура повторного пуску виявить у журналі відомості про те, що в момент відмови деяка транзакція перебувала на другій фазі двофазного процесу фіксації, після чого процес буде продовжений, починаючи з відправки учасникам повідомлень виконати. Відзначимо, що в період від t3 до t7 учасник перебуває в стані відсутності певної інформації про стан транзакції Якщо відбудеться відмова вузла координатора в момент t, як зазначено вище, період відсутності певної інформації може виявитися досить тривалим

Теоретично, безумовно, було б бажано, щоб процес двухфазной фіксації виявився стійким до будь-яким можливим збоїв На жаль, нескладно зрозуміти, що ця мета, по суті, недосяжна, тобто не існує якого кінцевого протоколу, який би гарантував, що всі учасники одночасно зафіксують успішно завершився транзакцію або одночасно її скасують, зіткнувшись при виконанні з деяким відмовою Припустимо протилежне, що такий протокол існує Нехай N— мінімальна кількість повідомлень, які потрібні для роботи подібного протоколу Тепер припустимо, що останнє з цих N повідомлень загублено через збої Тоді або це повідомлення не було необхідним, а це суперечить припущенню про те, що N— мінімальна кількість повідомлень, або протокол в такій ситуації працювати не буде І в тому, і в іншому випадку виникає протиріччя, з якого випливає, що такого протоколу не існує

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

■ По-перше, як було зазначено в анотації до [156], якщо агент на деякій кон конкретному вузлі учасника виконує операції тільки читання, такий учасник при завершенні першої фази процесу може відповісти ігноруйте моє присутст віє і координатор дійсно може ігнорувати такого учасника у дру рій фазі процесу

■ По-друге (і це зазначено в анотації до [156]), якщо всі учасники в першій фазі процесу дадуть відповідь ігноруйте моя присутність, друга фаза може бути повно стю пропущена

■ І по-третє, існує два важливих варіанту основної схеми, які назива ються варіантами передбачуваної фіксації і передбачуваного відкату, відпо венно, які будуть описані більш детально в кількох наступних абзацах

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

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

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

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

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

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

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

часу написання даної книги схема передбачуваного відкату сталафактичним

стандартом в реалізованих системах

Управління паралельністю

Як зазначено в розділі 213, управління паралельним доступом в більшості розподілених систем будується на використанні механізму блокування, тобто точно так, як і в більшості нерозподілених систем Однак в розподілених системах запити на перевірку, установку і скасування блокування стають повідомленнями (Якщо вважати, що даний обєкт розташований на віддаленому вузлі), а повідомлення створюють додаткові витрати Розглянемо, наприклад, транзакцію т поновлення обєкта, для якого існують дублікати на п віддалених вузлах Якщо кожен вузол відповідає за блокування обєктів, які на ньому зберігаються (як передбачається відповідно до принципу локальної незалежності), то безпосередня реалізація буде вимагати принаймні 5л таких повідомлень:

■ n запитів на блокування

■ n дозволів на блокування

■ n повідомлень про оновлення

■ n підтверджень

■ n запитів на зняття блокування

Безумовно, ми можемо розумно скористатися, як і в попередньому випадку, комбінованими повідомленнями Наприклад, можна обєднати повідомлення запиту на блокування і повідомлення про оновлення, а також повідомлення про дозвіл блокування і повідомлення про підтвердження Але навіть у цьому випадку загальний час оновлення може бути на порядок більше, ніж в централізованій системі

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

блокування буде обробляти вузол, що містить його первинну копію (нагадаємо, що первинні копії різних обєктів будуть в загальному випадку розміщуватися на різних

вузлах) При використанні цієї стратегії набір всіх копій обєкта з точки зору блокування можна розглядати як єдиний обєкт, а загальна кількість повідомлень буде скорочено з 5л до 2л +3 (один запит блокування, один дозвіл блокування, л

оновлень, л підтверджень і один запит на зняття блокування) Але зверніть увагу на те, що це рішення тягне за собою серйозну втрату незалежності – транзакція може тепер не завершитися, якщо первинна копія виявиться недоступною, навіть

якщо в транзакції виконувалося лише читання і локальна копія була доступна (Зазначимо, що блокування первинної копії потрібно не тільки для операцій оновлення, а й для операцій вибірки [156] Таким чином, у стратегії первинної копії

є небажаний побічний ефект – зниження рівня продуктивності та доступності як для вибірки, так і для оновлення)

Інша проблема, що стосується блокувань в розподілених системах, полягає в тому,

що блокування може привести до стану глобальної взаимоблокировки, охоплює два або більше вузлів Звернемося, наприклад, до рис 215, де показана описана нижче послідовність подій

1 Агент транзакції Т2 на вузлі х очікує, поки агент транзакції Т1 на вузлі х осво бодіт блокування

2 Агент транзакції т1 на вузлі X очікує, поки агент транзакції Т1 на вузлі Y завер шитий транзакцію

3 Агент транзакції Т1 на вузлі Y очікує, поки агент транзакції Т2 на вузлі У осво бодіт блокування

4 Агент транзакції Т2 на вузлі Y очікує, поки агент транзакції Т2 на вузлі X завер шитий транзакцію Це явна взаімоблокіровка

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

Витончена (і розподілена) схема для визначення стану глобальної блокування описана в статтях про систему R * (наприклад, [2137])

Примітка Як вказувалося в главі 16, в дійсності не всі системи розпізнають стан взаимоблокировки – деякі замість цього просто використовують механізм тайм-ауту З очевидних причин дане зауваження відноситься, зокрема, і до розподілених систем

Рис 215 Приклад стану глобальної взаимоблокировки

Джерело: Дейт К Дж, Введення в системи баз даних, 8-е видання: Пер з англ – М: Видавничий дім «Вільямс», 2005 – 1328 с: Ил – Парал тит англ

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*