1 Вступ
Балансування навантаження і придатність важливі в розподіленні в онлайн надійних системах. Крішна і Шін визначають толерантність до помилки як "здатність системи, негайно відповісти на несподівану помилку технічного забезпечення або програми" [13]. Багато толерантних до помилок обчислювальних систем, віддзеркалюють усі дії, наприклад кожна дія виконується на двох або більше подвійних системах таким чином, що, якщо одина робить, інша може прийняти її роботу. У [2] толерантності до помилки для розподіленого обчислення йдеться від широкої точки зору. Перевага користування кластерами, окрім толерантності до помилки, − навантаження, що розділяється між комп'ютерами [15]. Один може управляти цією задачею динамічно, де трансферні рішення не залежать від фактичного поточного стану системи. Задача з динамічною політикою є швидше непередбачувана. Інакше − слін користуватися статичною політикою, на якій загалом заснована інформація поведінки системи. Тут, трансферне рішення є незалежне від фактичного поточного стану системи. Це робить їх менш комплексними і більш передбачуваними, ніж динамічна політика [7].
Задача, що вивчається в цій статті: як рівномірно поширюють навантаження поточні комп'ютери, коли один або більше комп'ютерів в кластері вимкнені? Ми вважаємо це статичний перерозподіл роботи.
Є головний комп'ютер, який виконує додаток за нормальних умов і вторинний комп'ютер, який приймає задачу, коли головний комп'ютер вимкнений. Можливо, також є третій комп'ютер, який приймає задачу, коли головний і вторинний комп'ютери − вимкнені, і так далі. Коли усі комп'ютери працюють, ми вживаємо захотів, щоб навантаження поширювалося порівну. Навантаження на деяких комп'ютерах буде, проте зростати, коли один або більше комп'ютерів вимикаються, але і за цих умов ми хотіли б розповсюдити навантаження як можна порівну на комп'ютерах, що залишилися.
Поширення навантаження, коли комп'ютер вимкнений вирішене списком відновлення процесів, що виконуються на помилковому комп'ютері. Сукупність усіх списків відновлень названа схемою відновлення. Отже поширення навантаження повністю визначене схемою відновлення незважаючи на число комп'ютерів, які вимикаються.
Найбільше кластерних виконувачів підтримують цей вид оновлення при помилках, наприклад nodelist в Sun Cluster [17], список пріорітетів MC/ServiceGuard (HP) [5], каскадна група в HACMP (IBM) [6], і лист представлення в Windows Server 2003 clusters (Microsoft, earlier called MSCS) [14].
Задача виявлення оптимальних (чи навіть кращих) схем відновлення вивчається в [8,9,10]. У цій статті ми обчислюємо схеми відновлення, гарантію завантажження балансу для більшого числа комп'ютерів в кластері. Робота розглядає найгірший сценарій випадку, який дуже релевантний в системах реального часу.
Проблемне формулювання представляється в Секції 2. Наше попереднє дослідження на цій задачі описується в Секції3. У секціях 4 і 5 ми подали головні результати укладення представлені в Секції 6.
2. Проблемне формулювання
Ми припускаємо, що робота, що виконується кожним з n комп'ютерів, має бути переміщена, як одна атомна одиниця. Це дуже загальний сценарій, у тому числі випадки, коли:
• робота, що виконується комп'ютером, робиться від однієї зовнішньої системи (в упакані в стек схеми відновлення здійснюються в зовнішніх системах, як другий, третій, четвертий,... альтернативні місця (альтернативні кластерні вузли) призначення у разі, якщо голвний, вторинний,... місця призначення вимкнені);
• є одна мережева адреса для кожного комп'ютера і ми користуємося протоколом IP (або подібною технікою);
• усю роботу, що виконується комп'ютером, робить один процес або група пов'язаних процесів, використовуючи загальні місцеві ресурси і отже має бути переміщений як одна одиниця.
У [11,12] ми обговорюємо випадок, коли ряд незалежних процесів виконує кожен комп'ютер. Результати, представлені тут, можуть бути легко узагальнені до випадку з числом незалежних процесів на кожному комп'ютері при використанні тієї ж техніки, як в попередній статті [11,12].
Розглянемо
кластер з n
ідентичними вузлами, які за нормальних
умов виконують один процес кожен. Усі
процеси виконують ту ж кількість роботи.
Ми бичимо схему відновлення для кластера,
який визначає, де процес треба знову
почати якщо його поточний вузол вимкнений.
Схема відновлення повинна тримати
навантаження балансним до кластера,
коли навіть найнесприятливіша комбінація
вузлів вимкнена. Схема відновлення має
бути о вичислена для великого n
у багатоплинному часі. Схема відновлення
R
складається із списків n
відновлень – один список на процес.
Нехай S
є послідовність відстаней, тобто
послідовність додатніх цілих чисел S
=<s1,
s2,
…, sn
–
1>
де
j
(i=1,…,n-1)
− відстань між пошкодженим вузлом і
вузлом на якому процес треба знову
почати в i−тому
кроці. Нехай потім R0
є списком відновлень просес 0 (виконуючи
на комп'ютері 0). Список відновлень, від
якого ми конструюємо послідовність S:
R0
=<0,
s1,
s1
+ s2,
s1
+ s2
+ s3,
…, s1+…+sn
–
1>.
(ми
повертаємося до цього в Секції 4.4)
Коли один вузол в кластері ламається, навантаження на найбільш завантаженому вузлі в кластері (давайте називати це, вузол Z) міститиме дві роботи: власнe його і робота від вузла . Коли два вузли в кластері вимикаються, є дві можливості. Якщо обоє спочатку в послідовності рівні, навантаження на Z може містити три роботи: його власну, від вузла і від вузла . Ця ситуація представляється на Мал. 1a). Вузли і − пошкоджені вузли. Друга можливість − тоді, коли два перші номери в послідовності відмінні . У такому разі, Z може містити тільки дві роботи: його власну і від вузла або від вузла. Ця ситуація представляється на Мал. 1b). Тому, навантаження найгіршого випадку на Z менший, коли, ніж, коли s1 ≠ s2 Мал. 1b) також показує ситуації, коли три вузли в кластері вимикаються. Потім навантаження на Z може містити три роботи: його власну і від вузлів . Відмітьте, що в цьому випадку вузол − також пошкоджений вузол. Нійгірший випадок для трьох пошкоджених вузлів є тоді, коли перші з трьох номерів в послідовності рівні, тобто s1=s2=s3. У такому разі, Z міститиме чотири роботи: його власну і від вузлів.
Мал. 1 Сценарій з трьма заламаними вузлами