Exponential Backoff або «не завалити сервер»

    При будь-якій взаємодії клієнта і сервера ми стикаємося з необхідністю повторювати запити. Мережеве з'єднання може бути ненадійно, можуть бути проблеми на сервері або будь-які інші причини, через які необхідно повторити запит. Те ж саме стосується і взаємодії backend-сервера з базою даних або будь-яким іншим сховищем даних (іншим сервісом).
 
Ми сьогодні поговоримо про інтервал повторів запиту. Через який період часу після невдалого запиту можна його повторити? Давайте розглянемо дві стратегії: повтор через фіксований інтервал часу і експоненціальне відкладання (exponential backoff). Ми побачимо на симуляції, що за умови наявності великого числа клієнтів повтор через фіксований інтервал може не дати сервера «піднятися», а використання exponential backoff дозволяє уникнути цієї проблеми.
 
Питання інтервалу повторів стає важливим при проблемах на сервері. Дуже часто сервер здатний витримати навантаження від клієнтів, які відправляють запити в деякому «поточному» режимі, розподіляючи свої запити в часі випадковим чином. Якщо на сервері відбувається відмова, всі клієнти виявляють його і починають повторювати запити через деякий інтервал. Може виявитися, що частота таких запитів перевищує ту межу, яку сервер може обробляти.
 
Ще одним важливим моментом є те, що клієнт часто не може відрізнити проблеми на сервері від проблем з мережевим з'єднанням на стороні клієнта: якщо відповідь на запит не приходить в заданий інтервал часу, клієнт не може зробити висновок про те, в чому саме проблема. І поведінка клієнта (повтор запиту, інтервал повтору) будуть однаковими в обох ситуаціях.
 
 
 
 

Повтор через фіксований інтервал часу

 
Це найпростіша стратегія (і сама часто використовувана). У разі неуспішного виконання запиту клієнт повторює виконання запиту через інтервал T. Тут ми шукаємо компроміс між тим, щоб не "завалити" сервер занадто частими запитами в разі відмови, і між тим, щоб не погіршити user experience, занадто довго не повторюючи запити у випадку одиничних проблем в мережі.
 
Типовий інтервал повтору може становити від сотень мілісекунд до декількох секунд.
 
 

Експоненціальне відкладання (exponential backoff)

 
Алгоритм експоненціального відкладання можна записати на псевдокоде наступним чином:
 
 
delay = MinDelay

while True:
    error = perform_request ()
    if not error:
        # Ok, got response
        break

    # Error happened, pause between requests
    sleep (delay)

    # Calculate next delay
    delay = min (delay * Factor, MaxDelay)
    delay = delay + norm_variate (delay * Jitter)
 
 
У цьому псевдокоде
delay
— інтервал між запитами,
perform_request
виконує сам запит, а
norm_variate
обчислює нормальний розподіл.
 
Є наступні параметри алгоритму:
 
 
     
  • MinDelay
    — мінімальний (початковий) інтервал повтору (наприклад, 100 мс)
  •  
  • MaxDelay
    — обмеження на тривалість інтервалу повтору (наприклад, 15 хв)
  •  
  • Factor
    — коефіцієнт експоненціального наростання затримки (наприклад, 2)
  •  
  • Jitter
    — «тремтіння», визначає випадкову складову (наприклад, 0.1)
  •  
 
Обчислення інтервалу затримки працює досить просто: перший інтервал дорівнює
MinDelay
, потім в разі помилки виконання запиту інтервал збільшується в
Factor
раз, при цьому додається випадкова величина, пропорційна
Jitter
. Інтервал повтору обмежений
MaxDelay
(без урахування
Jitter
).
 
Чим даний спосіб обчислення повтору краще повтору через фіксований проміжок часу:
 
 
     
  • інтервал збільшується з кожною спробою, якщо сервер не може впоратися з потоком запитів, потік запитів від клієнтів буде зменшуватися з часом;
  •  
  • інтервали рандомізовані, тобто не буде «шквалу» запросив в такти, пропорційні фіксованому інтервалу.
  •  
 
Можна поставити резонне питання: а що якщо у клієнта просто поганий мережеве з'єднання? Адже алгоритм експоненціального відкладання буде весь час збільшувати інтервал запиту, а користувач не буде чекати нескінченно. Тут можна навести три міркування:
 
 
     
  • якщо з'єднання дійсно погане (невдалі 2, 3, 4 спроби), може і не варто повторювати запити так часто;
  •  
  • клієнт не знає в чому проблема (див. вище), і погіршити на якийсь час поведінка для користувача може не так вже і погано, в порівнянні з ситуацією, коли сервер буде завалений запитами і не зможе повернутися до нормальної життєдіяльності;
  •  
  • параметри
    Factor
    ,
    MaxDelay
    і
    MinDelay
    можна змінити, щоб сповільнити наростання періодичність повтору або обмежити його.
  •  
 
Для ілюстрації графіки інтервалу затримки при такому алгоритмі з параметрами:
 
 
     
  • блакитний графік:
    MinDelay
    100 мс,
    Factor
    2.7,
    Jitter
    0.1,
    MaxDelay
    10 хв;
  •  
  • зелений графік:
    MinDelay
    1 сек,
    Factor
    1.5,
    Jitter
    0.1,
    MaxDelay
    5 хв.
  •  
 
По горизонтальній осі — номер спроби.
 
 
 
Ті ж графіки, шкала логарифмічна:
 
 
 
 

Симуляція

 
Чи так легко повірити, що складність експоненціального відкладання виправдана? Давайте спробуємо провести симуляцію і з'ясувати ефект від різних алгоритмів. Симуляція складається з двох незалежних частин: клієнта і сервера, я їх опишу по черзі.
 
Сервер емулює типову для бази даних затримку відповіді на запит: до деякої межі кількості одночасних запитів сервер відповідає з фіксованою затримкою, а потім час відгуку починає наростати експоненціально залежно від кількості одночасних запитів. Якщо ми говоримо про backend-сервері, найчастіше його час відгуку також обмежено часом відгуку бази даних.
 
Сервер відповідає за
MinDelay
(100 мс), поки кількість одночасних з'єднань не перевищить
concurrencyLimit
(30), після цього час відгуку наростає експоненціально:
minDelay * factor ^ ((concurrency - concurrencyLimit) / K)
, де
Factor
,
K
— константи, а
concurrency
— поточне кількість одночасних з'єднань. Насправді сервер не виконує ніякої роботи, він відповідає на запит фіксованим відповіддю, але затримка обчислюється по вище вказаній формулі.
 
Клієнт моделює потік запитів від
N
клієнтів, кожен з яких виконує запити незалежно. Кожен потік клієнта виконує запити з інтервалами, відповідним експоненціальним розподілу з параметром
lambda
(мат. очікування інтервалу запитів одно
lambda
). Експоненціальне розподіл добре описує випадкові процеси, що відбуваються в реальному світі (наприклад, активність користувачів, яка призводить до запитів на сервер). При помилку виконання запиту (або при перевищенні часу очікування відповіді) клієнт починає повторювати запит або з простим фіксованим інтервалом, або за алгоритмом експоненціального відкладання.
 
Сценарій симуляції наступний: ми запускаємо клієнт і сервер з деякими параметрами, через 10-15 секунд виникає сталий режим, в якому запити виконуються успішно з невеликими затримками. Потім ми зупиняємо сервер (Емуліруем «падіння» сервера або мережеві проблеми) просто сигналом
SIGSTOP
, потік клієнтів це виявляє і починає повторювати запити. Потім відновлюємо роботу сервера і дивимося, як швидко робота сервера прийде в норму (або не прийде).
 
 

Код проекту

 
Код для симуляції написаний на Go і викладений на GitHub . Для складання потрібно Go 1.1 +, компілятор можна поставити з пакету ОС або скачати :
 
 
$ Git clone https://github.com/smira/exponential-backoff.git
$ Cd exponential-backoff
$ Go build-o client client.go
$ Go build-o server server.go
 
 
Простий сценарій: у першій консолі запускаємо сервер:
 
 
$. / Server
Jun 21 13:31:18.708: concurrency: 0, last delay: 0
...
 
 
Сервер очікує входять HTTP-запитів на порту 8070 і кожну секунду друкує на екран поточну кількість одночасних з'єднань і останню обчислену затримку обслуговування клієнтів.
 
В іншій консолі запускаємо клієнт:
 
 
$. / Client
OK: 98.00 req / sec, errors: 0.00 req / sec, timedout: 0.00 req / sec
OK: 101.00 req / sec, errors: 0.00 req / sec, timedout: 0.00 req / sec
OK: 100.00 req / sec, errors: 0.00 req / sec, timedout: 0.00 req / sec
...
 
 
Клієнт кожні 5 секунд друкує на екран статистику по успішним запитам, запитам, що завершився з помилкою, а також запитам, для яких був перевищений таймаут на очікування відповіді.
 
У першій консолі зупиняємо сервер:
 
 
Jun 21 22:11:08.519: concurrency: 8, last delay: 100ms
Jun 21 22:11:09.519: concurrency: 10, last delay: 100ms
^ Z
[1] + Stopped. / Server
 
 
Клієнт виявляє, що сервер зупинений:
 
 
OK: 36.00 req / sec, errors: 0.00 req / sec, timedout: 22.60 req / sec
OK: 0.00 req / sec, errors: 0.00 req / sec, timedout: 170.60 req / sec
OK: 0.00 req / sec, errors: 0.00 req / sec, timedout: 298.80 req / sec
OK: 0.00 req / sec, errors: 0.00 req / sec, timedout: 371.20 req / sec
 
 
Пробуємо відновити роботу сервера:
 
 
$ Fg
. / Server
Jun 21 22:13:06.693: concurrency: 0, last delay: 100ms
Jun 21 22:13:07.492: concurrency: 1040, last delay: 2.671444385s
Jun 21 22:13:08.492: concurrency: 1599, last delay: 16.458895305s
Jun 21 22:13:09.492: concurrency: 1925, last delay: 47.524196455s
Jun 21 22:13:10.492: concurrency: 2231, last delay: 2m8.580906589s
...
 
 
Кількість одночасних з'єднань наростає, збільшується затримка відповіді сервера, для клієнта це означатиме ще більше ситуацій таймаута, ще більше повторів, ще більше одночасних запитів, сервер буде збільшувати затримку ще більше, наш модельний сервіс «впав» і більше не підніметься.
 
Отстановім клієнт і перезапустити сервер, щоб почати спочатку з експоненціальним відкладанням повтору:
 
 
$. / Client-exponential-backoff
 
 
Повторимо ту ж послідовність дій з призупиненням і відновленням роботи сервера — сервер не впав і успішно піднявся, протягом короткого проміжку часу відновилася робота сервісу.
 
 

Замість висновку

У тестових клієнта і сервера є велика кількість параметрів, якими можна керувати як навантаженням, так і таймаут, поведінкою під навантаженням і т.п.:
 
 
$. / Client-h
$. / Server-h
 
 
Навіть в цій простій симуляції легко видно, що поведінка групи клієнтів (яких емулірет client) відрізняється у випадку «успішною» роботи і у випадку ситуації проблем (в мережі або на стороні сервера):
 
 
     
  • при нормальній роботі навантаження на сервер (кількість запитів в секунду) визначається випадковим розподілом, але буде приблизно постійно (з параметрами за замовчуванням близько 100 запитів в секунду);
  •  
  • в разі проблем при простій затримці кількість запитів досягає швидко високих значень (визначається тільки кількістю клієнтів і затримкою повтору);
  •  
  • в разі проблем при експоненційному відкладанні навантаження на сервер знижується з часом (поки сервер не зможе впоратися з навантаженням).
  •  
 
Порада: використовуйте експоненціальне відкладання при будь-якому повторі запиту — в клієнті при зверненні до сервера або в сервері при зверненні до бази даних або іншого сервісу.
 
Цей пост був написаний за матеріалами майстер-класу про високі навантаження і надійність.
    
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.