Короткий вміст
- Фатальна помилка Мартіна Клеппмана.
- Фізико-хімічна кінетика приділяє математику.
- Період напіврозпаду кластера.
- Вирішуємо нелінійні диференційні рівняння, не вирішуючи їх.
- Ноди як каталізатор.
- Передбачувальна сила графіків.
- 100 мільйонів років.
- Синергія.
У попередній замітці ми детально розбирали статтю Брюєра і його однойменну теорему. Цього разу займемося препаруванням поста Мартіна Клеппмана «The probability of data loss in large clusters».
У даному пості автор намагається промоделювати наступну задачу. Для збереження даних зазвичай використовується метод реплікації даних. При цьому, насправді, не важливо, чи використовується erasure кодування чи ні. В оригінальному пості автор ставить ймовірність випадання однієї ноди, а потім ставить питання: а яка ймовірність випадання даних при збільшенні числа нод?
Відповідь наведено на цій картинці:
Тобто. з ростом числа нод кількість втрачених даних зростає прямопропорційно.
Чому це важливо? Якщо ми розглянемо розміри сучасних кластерів, то побачимо, що їх число з плином часу безперервно зростає. А значить виникає резонне питання: чи варто турбуватися за збереження своїх даних і піднімати фактор реплікації? Адже це безпосередньо впливає на бізнес, вартість володіння тощо. Також на цьому прикладі можна чудово продемонструвати, як можна видати математично коректний, але неправильний результат.
Моделювання кластера
Для демонстрації помилковості розрахунків корисно розуміти, що таке модель і моделювання. Якщо модель погано описує реальну поведінку системи, то які б правильні формули не використовувалися, ми можемо легко отримати неправильний результат. А все через те, що наша модель може не враховувати якісь важливі параметри системи, якими не можна нехтувати. Мистецтво полягає в тому, щоб зрозуміти, що важливо, а що ні.
Для опису життєдіяльності кластера важливо враховувати динаміку змін і взаємозв'язок різних процесів. Це якраз і є слабкою ланкою оригінальної статті, тому що там бралася статична картинка без будь-яких особливостей, пов'язаних з реплікацією.
Для опису динаміки я буду використовувати методи хімічної кінетики, де я замість ансамблю частинок буду використовувати ансамбль нод. Наскільки я знаю, ніхто не використовував такий формалізм для опису поведінки кластерів. Тому буду імпровізувати.
Введемо такі позначення:
- : загальна кількість нод кластера
- : кількість працездатних нод (available)
- : кількість проблемних нод (failed)
Тоді очевидно, що:
У число проблемних нод я буду включати будь-які проблеми: диск навернувся, зламався процесор, мережа і т. п. Мені не важлива причина, важливий сам факт поломки і недоступності даних. Надалі, звичайно ж, можна враховувати більш тонку динаміку.
Тепер запишемо кінетичні рівняння процесів поломки і відновлення нод кластера:
Ці найпростіші рівняння говорять наступне. Перше рівняння описує процес поломки ноди. Воно не залежить від будь-яких параметрів і описує ізольований вихід ноди з ладу. Інші ноди в цьому процесі не беруть участі. Зліва використовується вихідний «склад» учасників процесу, а справа - продукти процесу. Константи швидкості і задають швидкісні характеристики процесів для поломки і відновлення нод відповідно.
З'ясуємо фізичний сенс констант швидкостей. Для цього запишемо кінетичні рівняння:
З цих рівнянь зрозумілий сенс констант і. Якщо припустити, що адмінів немає і кластер сам себе не зцілює (тобто), то відразу отримуємо рівняння:
Або
Тобто. величина - це період напіврозпаду кластера на запчастині, з точністю до. Нехай - характерний час переходу одиничної ноди зі стану в стан, а - характерний час переходу одиничної ноди зі стану в стан. Тоді
Вирішимо наші кінетичні рівняння. Відразу хочу обмовитися, що я буду зрізати кути скрізь, де це тільки можна, щоб отримати максимально прості аналітичні залежності, які буду використовувати для можливих передбачень і тюнінгу.
Оскільки максимальний ліміт на кількість рішень диференційних рівнянь досягнуто, то буду вирішувати ці рівняння методом квазістаціонарних станів:
З урахуванням того, що (це цілком розумне припущення, в іншому випадку треба купувати більш якісне залізо або більш просунутих адмінів), отримуємо:
Якщо покласти, що час відновлення приблизно 1 тиждень, а час смерті приблизно 1 рік, отримуємо, що частка зламаних нод:
Чанки
Позначимо через - кількість недореплікованих (underreplicated) чанків, які необхідно дореплікувати після випадання ноди при переході в стан. Тоді для обліку чанків, поправимо наші рівняння:
де - константа швидкості реплікації процесу другого порядку, а означає здоровий (healthy) чанк, який розчиниться в загальній масі чанків.
Третє рівняння необхідно пояснити. Воно описує процес другого порядку, а не першого:
Якби ми так зробили, то отримали б криву Клеппмана, що не входить в мої плани. Насправді в процесі відновлення беруть участь всі ноди, і чим більше нод, тим швидше йде процес. Пов'язано це з тим, що чанки з убитої ноди розподіляються приблизно рівномірно по всьому кластеру, тому кожному учаснику необхідно відреплікувати в раз менше. Це означає, що підсумкова швидкість відновлення чанків з убитої ноди буде пропорційна кількості доступних нод.
Варто також зазначити, що в рівнянні (3) зліва і справа стоїть, і при цьому він не витрачається. Хіміки б відразу заявили, що в даному випадку виступає в ролі каталізатора. І якщо уважно подумати, то так воно і є насправді.
Застосовуючи метод квазістаціонарних концентрацій миттєво отримуємо результат:
або
Дивовижний результат! Тобто. кількість чанків, які необхідно відреплікувати, не залежить від кількості нод! А пов'язано це якраз з тим, що збільшення числа нод збільшує результуючу швидкість реакції (3), тим самим компенсуючи більшу кількість нод. Каталіз!
Оцінимо це значення. - час відновлення чанків, як якщо б у нас була тільки одна нода. Нехай на ноді треба відреплікувати 5ТБ даних, при цьому потік реплікації в байтах задамо як 50МБ/с, тоді отримаємо:
Тобто. і можна не боятися за збереження даних. Тут варто врахувати, що втрата одного чанка з 3-х не призводить до втрати даних.
Планування реплікації
У попередньому розрахунку ми зробили неявне припущення про те, що ноди миттєво дізнаються про те, які конкретно чанки необхідно відреплікувати, і відразу ж починають процес їх реплікації. Насправді це абсолютно не так: майстру необхідно зрозуміти, що нода померла, потім зрозуміти які конкретно чанки необхідно відреплікувати і запустити процес реплікації на нодах. Все це не миттєво і займає якийсь час (scheduling).
Для врахування запізнювання використовуємося теорією перехідного стану або активованого комплексу, яка описує процес переходу через сідлову точку на багатовимірній поверхні потенційної енергії. З нашої точки зору у нас буде деякий додатковий проміжний стан, який означає, що цей чанк запланували на реплікацію, але процес реплікації ще не розпочато. Тобто. в наступну наносекунду реплікація точно почнеться, але не пікосекундою раніше. Тоді наша система прийме остаточний вигляд:
Вирішуючи його, знаходимо, що:
Застосовуючи метод квазістаціонарних концентрацій, знаходимо:
де:
Як бачимо, результат збігається з попереднім за винятком множника. Розглянемо 2 граничні випадки:
- . У цьому випадку всі міркування, наведені раніше, зберігаються: кількість чанків не залежить від числа нод, а значить не зростає зі зростанням кластера.
- . У цьому випадку і зростає лінійно зі зростанням числа нод.
Для визначення режиму оцінимо, чому рівна. - це характерний сумарний час виявлення недореплікованого чанка і планування його реплікації. Груба оцінка (використовуючи методику «пальцем у небо») дає значення 100 с. Тоді:
Таким чином подальше збільшення кластеру понад цю цифру за цих умов почне підвищувати ймовірність втрати чанку.
Що можна зробити для поліпшення ситуації? Здавалося б, можна поліпшити асимптотику зрушивши кордон шляхом збільшення, однак це лише збільшить значення без будь-якого реального поліпшення. Найвірніший спосіб: це зменшення, тобто час прийняття рішення для реплікації чанку, тому що залежить від характеристик заліза і на це програмними засобами вплинути важко.
Обговорення граничних випадків
Пропонована модель фактично розбиває сукупність кластерів на 2 табори.
До першого табору примикають порівняно невеликі кластери з кількістю нод < 1000. У цьому випадку ймовірність отримати недореплікований чанк описується простою формулою:
Для поліпшення ситуації можна застосовувати 2 підходи:
- Покращувати залізо, тим самим збільшуючи.
- Прискорювати реплікацію, зменшуючи.
Ці способи в цілому є досить очевидними.
У другому таборі ми маємо вже великі і надкрупні сервери з числом нод > 1000. Тут залежність буде визначатися наступним чином:
Тобто. буде прямопропорційно числу нод, а значить подальше збільшення кластера буде негативно позначатися на ймовірності появи недореплікованих чанків. Однак і тут можна істотно знизити негативні ефекти, використовуючи такі підходи:
- Продовжувати збільшувати.
- Прискорювати детектування недореплікованих чанків і подальше планування реплікації, тим самим зменшуючи.
2-й підхід щодо зменшення вже не є очевидним. Здавалося б, яка різниця, пройде 20 секунд або 100 секунд? Однак ця величина істотно впливає на ймовірність появи недореплікованих чанків. Також неочевидним є той факт, що пропадає залежність від, тобто сама швидкість реплікації не грає ролі. Воно і зрозуміло в цій моделі: з ростом числа нод ця швидкість тільки збільшується, тому на реплікацію чанка починає істотно впливати костянтна добавка «розгону» процесу реплікації, спрямована на виявлення і планування реплікації.
Варто зупинитися трошки детальніше на. Крім безпосереднього внеску в життєдіяльність чанків, збільшення благотворно позначається на кількості доступних нод, тому що
Тим самим збільшуючи кількість доступних нод. Таким чином, поліпшення безпосередньо позначається на наявність доступних ресурсів кластера, прискорюючи обчислення і одночасно підвищуючи надійність зберігання даних. З іншого боку, поліпшення якості заліза безпосередньо впливає на вартість володіння кластера. Описана модель дозволяє кількісно оцінювати економічну доцільність такого роду рішень.
Порівняння підходів
На закінчення я хотів би привести порівняння двох підходів. Про це красномовно скажуть наступні графіки.
З першого графіка можна тільки побачити лінійну залежність, однак вона не дасть відповіді на питання: «а що потрібно зробити, щоб поліпшити ситуацію?» Друга ж картинка описує більш складну модель, яка відразу може дати відповіді на питання про те, що робити і як вплинути на поведінку процесу реплікації. Більше того, вона дає рецепт швидкого способу, буквально в розумі, оцінювання наслідків тих чи інших архітектурних рішень. Інакше кажучи, передбачувальна сила розвиненої моделі знаходиться на якісно іншому рівні.
Втрата чанка
Знайдемо тепер характерний час втрати чанку. Для цього випишемо кінетику процесів утворення таких чанків з урахуванням ступеня реплікації = 3:
Тут через позначено кількість недореплікованих чанків, яким не вистачає двох копій, - проміжний стан, аналогічно, відповідний стану, а означає втрачений (lost) чанк. Тоді:
Де - характерний час утворення втраченого чанка. Вирішимо нашу систему для 2-х граничних випадків для випадку, коли.
, тоді
Для отримуємо:
Тобто. характерний час утворення втраченого чанка 100 мільйонів років! При цьому виходять приблизно схожі значення, тому що ми знаходимося в перехідній зоні. Величина характерного часу говорить сама за себе і кожен може зробити висновки сам.
Варто, однак, звернути увагу на одну особливість. У граничному випадку в той час, як є константою і не залежить від, у вираженні для ми отримуємо зворотну залежність, тобто зі зростанням кластера потрійна реплікація навіть покращує збереження даних! З подальшим зростанням кластеру ситуація змінюється рівно на протилежну.
Висновки
Стаття послідовно вводить інноваційний спосіб моделювання кінетики процесів великих кластерів. Розглянута наближена модель опису динаміки кластера дозволяє порахувати ймовірнісні характеристики, що описують втрату даних.
Звичайно, ця модель є лише першим наближенням до того, що реально відбувається на кластері. Тут ми лише враховували найбільш значущі процеси для отримання якісного результату. Але навіть така модель дозволяє судити про те, що відбувається всередині кластера, а також дає рекомендації для поліпшення ситуації.
Тим не менш, запропонований підхід дозволяє більш точні і достовірні результати, засновані на тонкому обліку різних факторів і аналізі реальних даних роботи кластера. Нижче наведено далеко не вичерпний список щодо поліпшення моделі:
- Ноди кластера можуть виходити з ладу через різні збої обладнання. Поломка конкретного вузла зазвичай має різну ймовірність. Більше того, поломка, наприклад, процесора, не втрачає дані, а лише дає тимчасову недоступність ноди. Це легко враховувати в моделі, вводячи різні стани, і т. д. з різними швидкостями процесів і різними наслідками.
- Не всі ноди однаково корисні. Різні партії можуть відрізнятися різним характером і частотою збоїв. Це таке можна враховувати в моделі, вводячи, і т. п. з різними швидкостями відповідних процесів.
- Додавання до моделі нод різних типів: з частково пошкодженими дисками, забанені та ін. Наприклад, можна детально проаналізувати вплив вимикання цілої стійки і з'ясування характерних швидкостей переходу кластера в стаціонарний режим. При цьому, чисельно вирішуючи диференційні рівняння процесів, можна наочно розглянути динаміку чанків і нод.
- Кожен диск має дещо відмінні характеристики читання/запису, включаючи латентність і пропускну здатність. Тим не менш, можна більш точно оцінювати константи швидкостей процесів, інтегруючи за відповідними функціями розподілу характеристик дисків, за аналогією з константами
