Презентація на тему:
Основнi поняття вiдмовостiйкостi i надiйна групова розсилка

Лекція 14. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Дмитро Георгійович Старший викладач кафедри ММСА ННК «ІПСА» Національний технічний університет України «Київський політехнічний інститут» м. Київ, Україна Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

Питання заняття Поняття вiдмовостiйкостi. Вiдмовостiйкiсть процесiв. Надiйний зв'язок «клiєнт-сервер». Надiйна групова розсилка. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

1. Поняття вiдмовостiйкостi Здатнiсть системи надавати послуги за наявностi вiдмов називають вiдмовостiйкiстю (fault tolerance). Розподiлена система вiдмовляє (fail) якщо вона не в змозi виконувати свою роботу. Помилкою (error) називають стан системи, який може призвести до непрацездатностi. Помилкою є також отримання пошкоджених пакетiв даних каналами зв'язку. Причиною помилок може бути вiдмова (fault), зокрема пошкодження лiнiй комунiкацiї. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

1.1. Види відмов перехiднi (transienr faults), тобто одноразовi; перемежованi (intermittent faults), якi виникають час вiд часу; постiйнi (permanent faults), якi зберiгаються постiйно. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

1.2. Відмовостійкість Вiдмовостiйкiсть тiсно пов'язана з поняттям надiйних систем (Dependable System). Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

1.3. Надійність Надiйнiсть визначає сукупнiсть вимог до розподiлених систем, включаючи: доступнiсть (availability) - готовнiсть до роботи; безвiдмовнiсть (reliability) - здатнiсть системи працювати без вiдмов; безпечнiсть (safety) - здатнiсть системи в разi вiдмов не призводити до катастрофiчного стану (ситуацiї); ремонтопридатнiсть (maintainability), що визначає складнiсть усунення вiдмов або вiдхилень у роботi розподiленої системи. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

1.4. Типи відмов поломки (crash failure), коли сервер раптово припиняє працювати i виконувати свою роботу; пропуск даних (omission failure) у разi неправильного реагування на запити. Розрiзняють: пропуск приймання (receive omission), наприклад, у разi неотримання запиту, зокрема внаслiдок того, що на серверi не запущено вiдповiдного процесу; пропуск передавання (send omission), коли сервер виконує свою роботу, але не в змозi надiслати вiдповiдь, зокрема, у разi переповнення буфера. Є багато iнших типiв пропускiв даних, зокрема, зумовлених помилкою в програмi; Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

1.4. Типи відмов (продовження) помилки синхронiзацiї (timing failure), якi виникають, якщо час очiкування вiдповiдi бiльший вiд зазначеного або невизначений, зокрема, помилка працездатностi (performance failure), зумовлена надто пiзнiм отриманням даних пiд час передавання мультимедiйної iнформацiї; помилки вiдповiдi (response failure), якi полягають у неправильних вiдповiдях сервера. Якщо виникають помилки значення (value failure), сервер повертає неправильну вiдповiдь на запит (наприклад, для пошукової машини). Якщо виникають помилки стану (state transition failure), сервер вiдхиляється вiд правильного потоку керування. Зокрема, вiн не в змозi розпiзнати отримане повiдомлення; Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

1.4. Типи відмов (продовження) довiльнi помилки (arbitrary failure) або вiзантiйськi помилки (Byzantine failures), за яких сервер надсилає випадкове повiдомлення у випадковi моменти часу. Наслiдком є одержання клiєнтом неправильних вiдповiдей за умови, що клiєнт сприймає їх як правильнi; вiдомi також помилки аварiйних зупинок (fail-stop failures). У системах зупинки без повiдомлення помилки (fail-silent systems) за помилку може сприйматись дуже повiльна робота сервера. Сервер може посилати випадковi повiдомлення, якi сприймаються iншими процесами як iнформацiйне «смiття», тому вони не призводять до помилки i вважаються безпечними (fail-safe). Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

1.5. Відмовостійкість Вiдмовостiйка РIС має бути здатною до маскування факту помилок вiд iнших процесiв. Основний метод такого маскування - використання надлишковостi (redundancy). Розрiзняють такi типи введення надлишковостi: iнформацiйна, яка забезпечується застосуванням завадостiйких кодiв; часова, що полягає у повторному виконаннi дiй, зокрема, повторна транзакцiя. Часова надлишковiсть важлива для прохiдних i перемiжних вiдмов; фiзична, яка реалiзується на апаратному або програмному рiвнi наприклад, iз застосуванням рiзноманiтних методiв резервування. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

1.6. Модульне резервування (Triple Modular Redundancy) В1-В6 - функцiональнi модулi; G1-G6 - схеми голосування «два з трьох». Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

2. Вiдмовостiйкiсть процесiв Процеси РIС - основнi складовi реалiзацiї послуг системи. Надлишковiсть забезпечується створенням груп iдентичних процесiв. Коли повiдомлення отримує група, воно передається всiм членам групи. Групи можуть бути динамiчними i статичними. Для процесу, який надсилає повiдомлення у виглядi запиту процесу-виконавцю (наприклад, серверу), реалiзується хоча б один iз процесiв цiєї групи. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

2.1. Структурна органiзацiя групи процесiв Структурна органiзацiя групи процесiв може бути довiльною. Найбiльшого поширення набули одноранговi групи з довiльними зв'язками мiж процесами групи та iєрархiчнi групи, у яких один iз процесiв вирiзняється як координатор iнших. Тобто в однорангових групах отримання вiдповiдi на запит вiдбувається колективно, а в iєрархiчнiй - координатор виконує вибiр процесiв-виконавцiв. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

2.2. Взаємодiя процесiв Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

2.3. Структурна органiзацiя групи процесiв (продовження) Одноранговi системи складнiшi за будовою й ефективнiшi, оскiльки втрата одного чи декiлькох процесiв дозволяє продовжити оброблення повiдомлення. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

2.4. Методи створення і знищення групп Поширеними методами знищення i створення груп є створення сервера груп (group server) i розподiленого керування членства процесiв розподiленої групи. Сервер груп централiзовано отримує запити до груп i реалiзує БД груп системи i членства в них окремих процесiв. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

2.5. Централiзоване розподiлення запитiв мiж групами Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

2.6. Метод розподiленого керування Метод розподiленого керування членством доцiльно застосовувати для групових розсилань повiдомлення. Зовнiшнiй учасник групи взаємодiї може надiслати повiдомлення всiм членам групи й оголосити намiр увiйти до групи. Вихiд з групи здiйснюється надсиланням повiдомлення «продавання» членам групи. Аварiйний вихiд члена визначається за результатами звернення до нього iнших членiв групи. Якщо немає вiдгуку пiд час звернення, вiдбувається примусове вилучення з групи. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

2.7. Механiзм маскування помилок Проблеми виникають у разi одночасної вiдмови кiлькох членiв, що призводить до непрацездатностi групи. Повторне складання групи з працездатних процесiв реалiзується за спецiальними протоколами. Механiзм маскування помилок здiйснюється реплiкацiєю процесiв i органiзацiєю груп. Залежно вiд моделi вiдмови, потрiбна рiзна кiлькiсть процесiв для маскування. Так, за наявностi призупинення К процесiв К+1-й процес забезпечує роботу системи для найпростiших моделей. Для вiзантiйських помилок потрiбно 2К+1 реплiкованих процесiв. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

2.8. Взаємодiя процесiв Реальна взаємодiя процесiв у групах реалiзовується через застосування певних узгоджень мiж процесами пiд час прийняття рiшень. Алгоритми розподiленого узгодження припускають рiзнi передумови роботи системи: надiйнiсть каналiв передавання повiдомлень мiж процесами, механiзм оброблення повiдомлень, визначення достовiрностi вiдповiдей, способи визначення непрацездатностi процесiв i їх вилучення тощо. Простi моделi не вiдповiдають реальним системам, а бiльш складнi моделi потребують складнiших алгоритмiчних розв'язань. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

2.9. Узгодження у РІС Узгодження у розподiлених системах неможливе за наявностi дефектного процесу, який припиняє свою роботу без сповiщення. Це характерно для дуже повiльних процесiв, якi неможливо вiдрiзнити вiд працездатних. Визначення конкретного розв'язання в кожному випадку потребує глибоких теоретичних дослiджень. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3. Надiйний зв'язок «клiєнт-сервер» Надiйний зв'язок забезпечується рiзними рiвнями взаємодiї. Можна виокремити надiйний зв'язок нижнього рiвня, зокрема з використанням TCP-протоколiв, та верхнього рiвня iз застосуванням RPC та RMI. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.1. Помилки взаємодії з RPC неспроможнiсть клiєнта виявити сервер; утрата повiдомлення iз запитом вiд клiєнта до сервера; поломка сервера пiсля отримання запиту; утрата зворотного повiдомлення вiд сервера до клiєнта; поломка клiєнта пiсля отримання вiдповiдi. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.2.1. Неспроможнiсть клiєнта виявити сервер Неспроможнiсть клiєнта виявити сервер може бути наслiдком вимкнення сервера або змiни сервером версiї iнтерфейсу i вiдповiдного скелетону. Вирiшенням проблеми є примусове спричинення подiї виключення (exception). Наприклад, у Java використовують обробник сигналiв (подiй), який спричиняє появу вiдповiдного сигналу. Це порушує прозорiсть. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.2.2. Втрата повiдомлення iз запитом вiд клiєнта до сервера Для визначення втрати повiдомлення iз запитом вiд клiєнта до сервера застосовують таймер. У разi переповнення таймера i неотримання пiдтвердження повiдомлення надсилається повторно. Повторне надсилання дозволяє нормально продовжити виконання процес. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.2.3. Поломка сервера пiсля отримання запиту Поломка сервера пiсля отримання запиту призводить до двох ситуацiй: поломка до вiдправлення зворотного повiдомлення; поломка початку оброблення. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.2.3. Поломка сервера пiсля отримання запиту (а) i до отримання запиту (б) Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.2.3. Нормальна робота сервера Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.2.3. Поломка сервера пiсля отримання запиту (продовження) Основнi методи вирiшення цiєї проблеми: очiкування перевантаження сервера або спроба зв'язатись з iншим сервером та повторення операцiї («семантика мiнiмум один раз» - at least once semantics); вiдмова вiд подальших спроб i повернення повiдомлення про помилку («семантика максимум один раз» - at most once semantics); що гарантує не бiльше одного виклику RPC; клiєнт не отримує жодної допомоги i жодних гарантiй. Виклик RPC або не виконується, або вiдбувається довiльну кiлькiсть разiв. Привабливою виглядає «семантика в точностi один раз», але при цьому виникає складнiсть її реалiзацiї. Таким чином, поломка сервера кардинально змiнює природу RPC i зумовлює розподiл мiж одно процесорними i розподiленими системами. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.2.4. Втрата зворотного повiдомлення вiд сервера до клiєнта Утрата зворотного повiдомлення вiд сервера до клiєнта призводить до невпевненостi клiєнта щодо причин вiдсутностi вiдповiдi. Частина операцiй може, наприклад, повторюватись довiльну кiлькiсть разiв («iдемпотентний запит»). Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.2.5. Поломка клiєнта пiсля отримання вiдповiдi Поломка клiєнта пiсля отримання вiдповiдi призводить до ситуацiї «сироти» (orphanes), яка породжує кiлька проблем, зокрема, втрату процесорного часу, блокування файлiв або iнше зв'язування ресурсiв. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.2.5. Рішення проблеми сиріт Розв'язанням цiєї проблеми є: знищення сирiт (extermination). Недолiком є надлишковiсть обсягу iнформацiї, можливiсть породження внучатих сирiт (grandorphans), вплив розподiлу мережi на фрагменти, зокрема, внаслiдок поломок шлюзiв; реiнкарнацiя (reincarnation) без записування на диск. Час розбивається на епохи з послiдовною нумерацiєю. У разi перевантаження надсилає широкомовнi повiдомлення всiм машинам з повiдомленням своєї епохи. Iз надходженням на сервер всi вiддаленi обчислення за запитом клiєнта припиняються; Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

3.2.5. Рішення проблеми сиріт (продовження) варiант м'якої реiнкарнацiї (gentle reincarnation). Iз надходженням повiдомлення про змiну епох, за наявностi на машинi вiддалених обчислень, робиться спроба знайти їх власника. Обчислення припиняються в разi вiдсутностi власника; вичерпання часу (expiration), за яким кожному виклику RPC надається стандартний час роботи Т. Пiсля завершення часу робиться запит (оренди) наступного термiну. Значення Т вибирається достатнiм для вмирання сирiт, що призводить до непередбачених наслiдкiв. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4. Надiйна групова розсилка Пiд надiйним груповим розсиланням (reliable multicasting) розумiють гарантоване доставляння повiдомлення всiм членам групи процесiв, яким воно надiслано. Вирiзняють надiйне розсилання в умовах надiйного зв'язку з хибним функцiонуванням i розсилання за наявностi надiйного зв'язку з коректно працюючими процесами. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.1. Ненадійний зв’язок Можлива також наявнiсть ненадiйного зв'язку для базової системи зв'язку, що може призвести до втрат повiдомлень. Просте надiйне розсилання в цiй ситуацiї досягається нумерацiєю повiдомлень i аналiзом, виконаним вiдправником вiдповiдей (позитивних або негативних) про отримання повiдомлень. Ненадходження його вiдправнику призводить до повторного розсилання повiдомлення. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.2. Велика кiлькість одержувачiв повiдомлень У разi великої кiлькостi одержувачiв повiдомлень i використання пiдтверджень вiд одержувачiв може виникнути ефект зворотного удару (feedback implosion), який полягає у критичному для вiдправника повiдомлення потоку пiдтверджень. Цей потiк може зменшуватись за рахунок формування одержувачем повiдомлень лише негативних пiдтверджень, тобто повiдомлень з певними номерами. Але у вiдправника залишається проблема бункерування старих повiдомлень, що може спричинити перевантаження буфера. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.3. Схеми надiйного розсилання неiєрархiчне керування зворотним зв'язком; iєрархiчне керування зворотним зв'язком. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.3.1. Модель пригнiчення вiдгукiв Для неiєрархiчного керування використовується модель пригнiчення вiдгукiв (feedback suppression), яку покладено в основу масштабованого розсилання SRM (Scalable Reliable Multicasting). У SRM повертається лише негативне пiдтвердження, яке розсилається вiдправнику i рештi членiв групи, якi отримують повiдомлення. У результатi вони вiдмовляються вiд надсилання своїх негативних пiдтверджень, що сприяє полiпшенню масштабованостi розподiленої системи. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.3.1. Застосування SRM Проблемами застосування SRM є потреба в одночасному надсиланнi негативних пiдтверджень кiлькома одержувачами та переривання роботи процесiв, якi успiшно отримали повiдомлення. Iєрархiчне керування зворотним зв'язком передбачає розбиття групи на пiдгрупи з власними координаторами. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.3.2. Iєрархiчне керування зворотним зв'язком Iєрархiчне керування зворотним зв'язком передбачає розбиття групи на пiдгрупи з власними координаторами. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.3.2. Iєрархiчне надiйне групове розсилання повiдомлень С - координатор; S - вiдправник повiдомлення; R - одержувач повiдомлення Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.3.2. Локальнi координатори Локальнi координатори вiдповiдають за оброблення запитiв на повторне передавання. Цi запити надсилаються одержувачами пiдгрупи локальної мережi. Координатор пiдтримує буфер повiдомлень. Якщо сам координатор пропускає повiдомлення, то вiн звертається до координатора батькiвської пiдгрупи. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.3.2. Схема з пiдтвердженням У схемi з пiдтвердженням локальний координатор надсилає пiдтвердження батькiвському координатору. З отриманням пiдтвердження повiдомлення всiма членами пiдгрупи i їх нащадками координатор вилучає повiдомлення з власного буфера. Iснує цiлий ряд проблем побудови дерев пiдгруп, зокрема на основi маршрутизаторiв, якi доповнюються функцiями групового розсилання. Доставлянням повiдомлень у разi групового розсилання в певнiй послiдовностi за умови всiм процесам групи або нiкому якщо можлива наявнiсть помилок у процесах, називають проблему атомарного групового розсиллання AMP (atomic multicast problem). Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.3.2. Приклад Прикладом застосування є реплiкованi БД надбудови над розподiленою системою. Кожнiй реплiцi вiдповiдає процес БД. Змiни надсилаються всiм членам групи реплiк i далi виконуються локально. У разi поломки реплiка AMP передбачає вiдмову в розсиланнi повiдомлень групi. Реплiки групи можуть вилучити поламану реплiку на пiдставi нового узгодження про членство, забезпечуючи подальшу правильну роботу. Подальше входження реплiки до групи встановлюється входженням її зi встановленням стану, який вiдповiдає поточним станам реплiк групи. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.4. Склад груп Отже, надiйне групове розсилання може бути визначено в термiнах груп процесiв i змiнах членства в групi та описано у виглядi моделi доставлення i приймання повiдомлень. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.4. Розподiлена система iз розподiленням засобiв отримання i доставляння повiдомлень Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.5. Пересилання повідомлень Розподiленi системи мiстять комунiкацiйний рiвень з локальним буфером для зберiгання повiдомлень. За атомарного групового розсилання повiдомлення m, що розсилається членам групи, асоцiюється зi списком процесiв-отримувачiв. Список розсилання вiдповiдає поданню групи (group view), тобто групи процесiв, з якими працює вiдправник у момент розсилання повiдомлення m. Процеси групи G мають однакове подання i погоджуються з розв'язанням за AMP. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.6. Вихід з групи У разi виходу з групи змiнюється подання, i членам групи надсилається повiдомлення vc про входження або вихiд процесу з групи G. Таким чином, у системi мiстяться повiдомлення m i vc, i треба гарантувати, що m або буде доставлено процесам з G до отримання ними vc, або взагалi не доставлено. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.7. Вiртуально-синхронна розсилка Доставлення m припускає вiдмову в разi поломки вiдправника m i отримання членами групи G повiдомлення про аварiйне завершення. Повiдомлення m iгнорується у разi поломки вiдправника до його вiдання. У разi вiдмови вiдправника у ходi розсилання повiдомлення або приймається, або вiдмовляється всiма процесами, що залишились. Надiйне групове розсилання з цими властивостями називають вiртуально-синхронним (virtually synchronous). Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.8. Принцип вiртуально-синхронного групового розсилання повiдомлень {1} - процес Р1 приєднується до групи; {2} - надiйне групове розсилання кiлькох повiдомлень; {3} - вiдмова процесу РЗ; {4} - часткове групове розсилання вiд процесу РЗ анулюється; {5} - вiдновлення роботи процесу РЗ i приєднання до групи Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.9. Приклад У момент 1 до групи надсилається процес P1. До моменту 3 здiйснюється надiйне розсилання двох повiдомлень. У момент 3 вiдбувається поломка РЗ i повiдомлення, якi надсилає процес, анулюються. До моменту 5 на пiдставi нового узгодження вiдбувається робота групи з процесiв Р1, Р2, Р4. Пiсля приєднання РЗ у момент 5 процес РЗ бере участь у груповому розсиланнi повiдомлень. Принцип вiртуального синхронного розсилання випливає з факту групового розсилання у промiжках мiж змiнами подання, яке утворюють бар'єри, неподоланнi для розсилання. Це дозволяє розробнику додатка вважати, що груповi розсилання вiдбуваються в рiзнi епохи. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.10. Послiдовнiсть розсилань повiдомлень Для групових розсилань важливою є послiдовнiсть розсилань повiдомлень. Можна виокремити чотири основнi варiанти: надiйне неупорядковане групове розсилання (reliable unordered multicast); групове розсилання у послiдовностi FIFO; надiйне причинно-упорядковане групове розсилання; повнiстю упорядковане групове розсилання. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.10.1. Вiртуальне синхронне групове розсилання Вiртуальне синхронне групове розсилання не гарантує послiдовностi надходження повiдомлень до рiзних процесiв. Процеси не ламаються, а комунiкацiйний рiвень передає вiдповiдному процесу повiдомлення у визначенiй послiдовностi. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.10.1. Опис взаємодiї трьох процесiв Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.10.2. Групове розсилання у послiдовностi FIFO Згiдно з цим варіантом комунiкацiйний рiвень має доставляти повiдомлення в послiдовностi їх вiдправлення (reliable FIFO - ordered multicast). Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.10.2. Пересилання повiдомлень за FIFO Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.10.3. Надiйне причинно-упорядковане групове розсилання Згiдно з третiм варiантом упорядкованого розсилання (reliable cassualy-ordered multicast) повiдомлення доставляється вiдповiдно до потенцiйного причинного зв'язку мiж ними. Наприклад, якщо m1 причинно передує m2, то послiдовнiсть їх доставляння буде m1, m2, незалежно вiд того, належать вони одному чи рiзним вiдправникам. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.10.4. Повнiстю упорядковане групове розсилання Варiант повнiстю упорядкованого групового розсилання (total-ordered multicast) передбачає, що незалежно вiд того, як упорядковано доставляння повiдомлення (причинно, за FIFO або неупорядковано), додатково вимагається, щоб повiдомлення доставлялось усiм членам групи в такiй самiй послiдовностi. Для попереднього прикладу P2 можна спочатку отримати m3, а потiм ml. Процес Р3 порушує упорядкованiсть, оскiльки отримує m3, а потiм m1. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.11. Вiртуальне синхронне надiйне групове розсилання Вiртуальне синхронне надiйне групове розсилання, яке пiдтримує повнiстю упорядковане доставлення, називають атомарним груповим розсиланням (atomic multicasting). Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.12. Види вiртуально-синхронного надiйного групового розсилання Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.13. Приклад реалізації надiйного групового доставляння Прикладом реалiзацiї надiйного групового доставляння є система Isis, яка грунтується на використаннi в мережi TCP механiзмiв наскрiзного зв'язку. Вiдмова вiдправника повiдомлення m може бути лише до вiдправлення m. Повiдомлення отримуються комунiкацiйним рiвнем за FIFO на основi з'єднання за протоколом TCP. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.13.1. Стiйкі повiдомлення (stable) Кожний процес групи G зберiгає m до отримання його всiма членами групи, а саме m називають стiйким повiдомленням (stable). Нехай за поточного подання Gj необхiдно встановити нове подання Gj+i, яке вiдрiзняється вiд Gj не менше, нiж одним процесом. Деякий процес Р дiзнається про змiну подання на пiдставi повiдомлення, можливо вiд процесу, який входить у групу або покидає її, або вiд процесу, який виявив вiдмову одного з процесiв групи, що має бути вилученим iз групи. Наприклад, процес 4 повiдомив про вiдмову процесу 7. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.13.1. Розсилання процесом 4 повiдомлення про змiну подання Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.13.2. Зміна подання Нехай процес 6 дозволяє змiнити подання Gi на Gi+1 i надсилає нестiйкi повiдомлення (порожнiй прямокутник) (помiчає їх як стiйкi) i повiдомлення узгодження (зафарбований прямокутник) на всi члени групи, крiм процесу 7. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.13.2. Розсилання процесом 6 нестiйких повiдомлень i повiдомлень узгодження Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.13.3. Узгодження подання Пiсля отримання процесом Р повiдомлення узгодження (flush message) для подання Gi+1 вiд iншого процесу вiн може встановити нове подання на пiставi отриманих повiдомлень узгодження. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.13.3. Установлення процесiв нового подання за повiдомленням узгодження Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.13.3. Узгодження подання (продовження) Процес Q, отримавши повiдомлення m вiдповiдно до подання Gi, доставляє його з урахуванням послiдовностi. У разi його повтору вiн пропускає m. Отримавши повiдомлення про змiну подання Gi+1 процес Q також пересилає свої нестiйкi повiдомлення з подальшим пересиланням повiдомлення узгодження членам Gi+1. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

4.13.3. Властивості протоколу Недолiком цього протоколу є його неспроможнiсть запобiгати збоям процесiв у момент оголошення нової змiни подання. Тобто припущення, що до встановлення нового подання Gi+1 кожним членом Gi+1 жоден процес у Gi+1 не вiдмовить. Цю проблему розв'язують через оголошення про змiну подань для довiльного подання Gi+k ще до того як попереднi змiни будуть встановленi всiма процесами. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

Питання заняття Поняття вiдмовостiйкостi. Вiдмовостiйкiсть процесiв. Надiйний зв'язок «клiєнт-сервер». Надiйна групова розсилка. Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010

Питання? Розподілені інформаційні системи www.simulation.kiev.ua/dis/ Основнi поняття вiдмовостiйкостi i надiйна групова розсилка Діденко Д.Г. © 2010