Cinnamon: використання столітніх технологій для створення потужного механізму скидання навантаження
Це переклад статті Uber Cinnamon: Using Century Old Tech to Build a Mean Load Shedder
Вступ
Uber має тисячі мікросервісів, які обслуговують приблизно 130 млн щомісячних користувачів — пасажирів, клієнтів Uber Eats і партнерів-водіїв. Трафік від цих користувачів призводить до мільйонів запитів за секунду (тобто RPS), агрегованих між нашими сервісами, як безпосередньо з онлайн-трафіку (наприклад, користувач натискає кнопку в застосунку), так і опосередковано з офлайн-трафіку (наприклад, batch-завдання, яке виконує агрегацію по поїздках). За такої складності неминуче виникають ситуації, коли один або кілька сервісів перевантажуються через сплески трафіку (наприклад, надто агресивне batch-завдання) або через уповільнення (наприклад, база даних починає працювати повільніше).
Щоб пом’якшити такі ситуації перевантаження, критично важливо застосовувати graceful degradation — поступову деградацію, за якої ми відсікаємо запити з нижчим пріоритетом (наприклад, batch-завдання) раніше, ніж будь-які запити з високим пріоритетом (наприклад, онлайн-запити клієнтів). Наша мета — забезпечити якісний користувацький досвід навіть тоді, коли окремі частини бекенду мають проблеми з навантаженням. З огляду на масштаб сервісної інфраструктури Uber, будь-яке рішення для graceful degradation має бути автоматичним і не вимагати конфігурації, оскільки навіть одна конфігураційна змінна на сервіс швидко перетвориться на значні інженерні витрати, враховуючи кількість сервісів, які ми експлуатуємо, і те, як часто такі значення застарівають.
Щоб вирішити ці дві проблеми, ми створили бібліотеку для відсікання навантаження (load shedder) — Cinnamon. Вона побудована на основі досвіду попереднього механізму відсікання навантаження — QALM, який забезпечував graceful degradation. Окрім graceful degradation, Cinnamon динамічно та безперервно регулює пропускну здатність сервісу (використовуючи модифікований алгоритм TCP-Vegas — відносно «молоду» ідею 1994 року) і таким чином динамічно коригує обсяг відсікання навантаження залежно від вхідних запитів (застосовуючи підхід PID controller, що бере початок у XVII столітті). Порівняно з попередніми підходами, Cinnamon здатний витримувати значно більші перевантаження, зберігаючи при цьому прийнятні затримки (P50 latency зростає на 50% при перенавантаженні 300%). Він є дуже ефективним і зазвичай додає лише 1 мікросекунду додаткових витрат на запит. Нарешті, Cinnamon не потребує конфігурації та швидко впроваджується в сервісах Uber.
Цей блог-пост — перший у серії з трьох матеріалів про Cinnamon. Серія буде цікавою для всіх — від читачів без попередніх знань про динамічні load shedder’и до тих, хто має глибоку експертизу в цій галузі. У цьому дописі ми надамо огляд Cinnamon і порівняємо його з QALM на основі CoDel. У наступних двох частинах ми детально розглянемо, як визначається коефіцієнт відхилення за допомогою PID-регулятора та як автоматично регулюється пропускна здатність за допомогою модифікованого алгоритму TCP Vegas.
Передумови
Перш ніж зануритися в те, як спроєктовано Cinnamon і як він працює, ми коротко опишемо, як працює QALM. Якщо ви вже читали блог-пост про QALM, можете пропустити цей розділ.
QALM використовує алгоритм Controlled Delay (a.k.a., CoDel) для виявлення перевантаження і, у разі перевантаження, відкидає запити з нижчим пріоритетом (якщо такі є). По суті, CoDel (а отже й QALM) відстежує чергу вхідних запитів і час, який кожен запит проводить у черзі. Якщо всі вони затримуються більш ніж, скажімо, на 5 мс у межах вікна 100 мс, тоді CoDel починає відсікати запити. У випадку QALM це означає відхилення будь-яких запитів із нижчим пріоритетом.
У будь-який момент часу QALM обмежує кількість запитів, що виконуються паралельно, що, своєю чергою, визначає пропускну здатність (capacity). Оскільки QALM реалізовано на Go, це обмеження впроваджується шляхом поміщення всіх запитів у канал (channel), з якого набір фонових goroutine обробляє їх до певного встановленого ліміту. Нарешті, щоб використовувати QALM, необхідно налаштувати пріоритети викликів (callers) і максимальну кількість одночасно оброблюваних запитів.
Під час розгортання QALM ми помітили, що частина з конфігурацією ускладнює впровадження, оскільки вимагає більше зусиль, ніж очікувалося. По-перше, визначення пріоритету лише на основі сервісу-викликача може не враховувати, що тестовий сервіс викликав ваш апстрім-сервіс, і таким чином запит насправді мав би бути низькопріоритетним (на діаграмі нижче показано цю проблему).
Рисунок 1: Діаграма двох сервісів, де Service 1 отримує онлайн-трафік від користувачів і від тестової системи. В обох випадках він викликає Service 2 для отримання інформації
У наведеному прикладі, якщо ми налаштовуємо пріоритети в Service 2, ми можемо встановити для запитів від Service 1 високий пріоритет (оскільки він обслуговує онлайн-трафік з наших мобільних застосунків). Але через те, що Service 1 також обслуговує тестові системи, ці запити будуть помилково класифіковані в Service 2 як високопріоритетні.
Крім того, складно встановити правильне значення максимальної кількості одночасних запитів, оскільки воно може досить швидко змінюватися залежно від патернів запитів, які обробляє ваш сервіс, а також від апаратного забезпечення (і «сусідів» на цьому обладнанні), на якому він працює. Також ми помітили, що використання каналів для load shedding може бути дорогим, оскільки вони є точками синхронізації.
Тому ми розпочали роботу над Cinnamon, щоб усунути ці проблеми, а саме:
- Краще поширення пріоритетів
- Відсутність потреби в конфігурації для використання
- Висока продуктивність
Архітектура
Cinnamon побудований як RPC middleware, який легко підключається до Go-сервісів Uber. Крім того, кожен запит маркується пріоритетом (на рівні edge), який поширюється вниз по стеку викликів, щоб усі сервіси, що обробляють певну частину запиту, знали, наскільки цей запит важливий для наших користувачів. Це зображено на діаграмі нижче:
Рисунок 2: Діаграма інтеграції Cinnamon у сервісну mesh-архітектуру Uber
На діаграмі вище запит з одного з наших застосунків надходить до Edge-системи, яка потім пересилає його до Service 1. У процесі обробки цього запиту Service 1 звертається до бази даних, а також до Service 2. Endpoint на рівні edge анотовано пріоритетом запиту, і ця інформація поширюється від edge до всіх downstream-залежностей за допомогою Jaeger. Завдяки поширенню цієї інформації всі сервіси в ланцюгу обробки запиту знають важливість запиту та те, наскільки він критичний для наших користувачів.
Маючи пріоритет, анотований для кожного запиту, і поширюючи його по всьому ланцюгу викликів, Cinnamon може діяти автономно для кожного інстансу сервісу, водночас зберігаючи глобальну узгодженість щодо того, які запити обслуговувати, а які відхиляти під час перевантажень.
Пріоритети
Cinnamon використовує пріоритет, прикріплений до запиту, а якщо його немає — встановлює значення за замовчуванням залежно від сервісу-викликача. Пріоритет фактично складається з двох різних компонентів — рівня (tier) та когорти (cohort). Рівень визначає, наскільки важливим є запит. В Uber ми використовуємо 6 рівнів — від 0 до 5, де рівень 0 є найвищим пріоритетом, а рівень 5 — найнижчим.
Когорти використовуються для додаткової сегментації запитів у межах одного рівня, щоб ми могли відсікати однакову підмножину запитів у різних сервісах. Підхід значною мірою натхненний підходом WeChat, де ми розподіляємо запити на 128 когорт на основі користувача, який бере участь у запиті. Таким чином, якщо сервісу потрібно відсікти, скажімо, 5% запитів рівня 1, це буде одна й та сама множина користувачів (тобто 5%), для яких запити будуть відсічені. Для цього ми використовуємо просту схему шардингу з хешуванням і певною часовою інформацією для групування та автоматичного зміщення користувачів між когортами, щоб ті самі користувачі не відсікалися завжди першими. Для узгодження з рівнями пріоритету найвищою пріоритетною когортою є 0, а найнижчою — когорта 127.
Маючи 6 рівнів і 128 когорт для кожного з них, ми отримуємо 768 різних пріоритетів, за якими можемо виконувати відсікання навантаження. Завдяки «лише» 768 різним пріоритетам ми також можемо побудувати дуже ефективну пріоритетну чергу з окремими бакетами для кожного пріоритету.
Архітектура бібліотеки
Після загального опису розгортання Cinnamon та механізму пріоритетів настав час зануритися в те, як побудована бібліотека Cinnamon.
Діаграма нижче показує життєвий цикл запиту під час проходження через middleware Cinnamon:
Рисунок 3: Проходження запиту через Cinnamon перед передачею до бізнес-логіки
Коли запит надходить, він проходить такі етапи:
- Priority: Спочатку ми переконуємося, що до запиту прикріплено пріоритет, а якщо ні — встановлюємо значення за замовчуванням на основі сервісу-викликача.
- Rejector: Далі запит потрапляє до rejector, який визначає, чи слід його відхилити.
- Priority Queue: Якщо запит прийнято, він потрапляє до пріоритетної черги, щоб гарантувати, що запити з найвищим пріоритетом плануються першими.
- Scheduler: Cinnamon дозволяє обробляти паралельно лише фіксовану кількість запитів, тому завдання scheduler — забезпечити, щоб ми обробляли стільки запитів одночасно, скільки дозволяє поточний ліміт, але не більше.
- Timeout: У випадках, коли занадто багато запитів накопичується в черзі, вони можуть вийти за таймаутом і повернути помилку rate limiting. Таймаут перебування в черзі зазвичай становить 33% від звичайного таймауту запиту.
Крім того, Cinnamon має два фонові потоки/goroutine — «PID controller» та «auto-tuner», які безперервно коригують поріг відхилення з урахуванням максимально дозволеної кількості одночасно виконуваних запитів. Можна запитати, чому їх дві і чому все не можна зробити лише встановленням правильного порога відхилення, але, на жаль, цього недостатньо. Коли сервіс перенавантажений, лише контроль максимальної кількості одночасних запитів недостатній, оскільки черга все одно може формуватися. З іншого боку, лише встановлення порога відхилення не запобігає перевантаженню сервісу, якщо він обробляє занадто багато запитів одночасно. Тому ми маємо дві goroutine: завдання PID controller — мінімізувати кількість запитів у черзі, тоді як завдання auto-tuner — максимізувати пропускну здатність сервісу без надмірного погіршення затримок відповіді.
Ми коротко опишемо ці два аспекти нижче. Для більш детальної інформації про них зверніться до наступних двох блог-постів.
Rejector
Компонент rejector має дві відповідальності:
a) визначити, чи перенавантажений endpoint, і b) якщо endpoint перенавантажений — відсікти певний відсоток запитів, щоб черга запитів залишалася якомога меншою.
Щоб визначити, чи перенавантажений endpoint, ми відстежуємо момент, коли черга запитів востаннє була порожньою, і якщо вона не спорожнювалася протягом, скажімо, останніх 10 секунд, ми вважаємо endpoint перенавантаженим (підхід натхненний Facebook).
Коли endpoint перенавантажений, фонова goroutine починає відстежувати вхідний та вихідний потоки запитів у пріоритетну чергу. На основі цих значень вона використовує PID controller для визначення частки запитів, які потрібно відсікти. PID-регулятор дуже швидко (у сенсі, що потрібно дуже мало ітерацій) знаходить правильний рівень, і після того як чергу запитів було спорожнено, PID гарантує, що ми лише повільно зменшуємо частку відсікання. Повільне зниження порога дозволяє обмежити осциляції, які погіршують затримки. Крім того, завдяки тому, що ми лише відстежуємо вхідний і вихідний потоки запитів у пріоритетну чергу, PID-регулятор залишається незалежним від того, чи обслуговує сервіс високий або низький обсяг RPS.
Scheduler
Якщо запит прийнято до обробки (тобто не відхилено), він переходить у пріоритетну чергу, де scheduler витягує запити з найвищим пріоритетом першими та передає їх до бізнес-логіки всередині сервісу, яка виконує фактичну обробку. Scheduler гарантує, що одночасно обробляється лише певна кількість запитів, щоб краще контролювати затримки. Ми називаємо це inflight-лімітом.
Фонова goroutine auto-tuner відстежує затримки endpoint’а та використовує суттєво модифіковану/розширену версію алгоритму керування Vegas TCP/IP для контролю inflight-ліміту. По суті, якщо затримка зростає, це може означати, що сервіс перенавантажений, і тоді inflight-ліміт зменшується. І навпаки, якщо затримки залишаються стабільними або знижуються, ліміт збільшується, щоб забезпечити вищу пропускну здатність.
Експериментальні результати
Щоб переконатися, що Cinnamon справді працює, ми провели низку експериментів, зокрема порівняли його з нашим наявним load shedder — QALM. Оцінюючи load shedder, ми хочемо перевірити, наскільки добре він:
- захищає сервіс і
- захищає наші основні потоки (core flows), відсікаючи насамперед запити з нижчим пріоритетом.
Щоб оцінити, наскільки добре обидва підходи захищають сервіс, ми порівнюємо throughput — кількість запитів, переданих до бекенду, та goodput — підмножину throughput, яка повертає успішну відповідь. В ідеалі goodput має бути якомога вищим за мінімального впливу на затримки. Крім того, для захисту наших основних потоків load shedder має, в ідеалі, відсікати трафік із нижчим пріоритетом раніше, ніж трафік із вищим пріоритетом.
У всіх випадках ми використовуємо тестовий сервіс із endpoint’ом, який виконує комбінацію операцій із виділення пам’яті, CPU-навантаження (сортування) та перепланування (через time.Sleep), щоб імітувати реальне робоче навантаження. Час відповіді цього endpoint’а становить приблизно 120 мс за відсутності навантаження.
Ми проводимо 5-хвилинні тести, у межах яких надсилаємо фіксовану кількість RPS (наприклад, 1 000), де 50% трафіку належить до tier 1 і 50% — до tier 5. Кожен запит має таймаут 1 секунду. Ми збираємо метрики P50 і P99 latency та goodput. У всіх випадках тести виконуються в продакшені, де ми маємо два бекенд-інстанси, на які надсилаємо запити з двох інших машин. Кожен бекенд має пропускну здатність приблизно ~650 RPS, отже загалом сервіс може обробляти 1 300 RPS.
Goodput
Першою метрикою, яку ми оцінюємо, є goodput, що по суті дорівнює <throughput> * (1 – <error-rate>), де error-rate включає як помилки rate limiting, так і таймаути. Ми групуємо результати за рівнями (tier) і включаємо error rate, щоб спростити порівняння (ми також додали базовий випадок — без увімкненого load shedder).
Рисунок 4: Goodput без load shedder, з Cinnamon та QALM.
Як видно, коли сервіс не перенавантажений (200–1 000 RPS), усі запити проходять. Коли ми досягаємо 1 500 RPS, обидва load shedder’и починають працювати, і QALM демонструє дещо вищий goodput (приблизно на ~2% вище), порівняно з Cinnamon (1 258 проти 1 280). Ймовірно, це пов’язано з тим, що auto-tuner має знайти правильний inflight-ліміт у поєднанні з шумом у нашому продакшн середовищі.
За 2 000 RPS і вище Cinnamon підтримує goodput, близький до максимальної пропускної здатності. Варто зазначити, що за вищих значень throughput сервіс витрачає все більше ресурсів на відхилення запитів, і тому його пропускна здатність знижується. QALM, зі свого боку, починає повертати помилки навіть для запитів tier 1 (більшість із них — таймаути), і за 3 000 RPS його загальний goodput становить 552, або 40% від пропускної здатності сервісу.
Затримки
Хоча goodput — це одна сторона медалі, зовсім інше питання — чи є затримки прийнятними. На графіках нижче показано P50 та P99 затримки для tier 1 (тобто для запитів із найвищим пріоритетом, які нас найбільше цікавлять):
Рисунок 5: P50 latency для tier 1
Рисунок 6: P99 latency для tier 1
(Зверніть увагу, що після 3 000 RPS сервіс повністю «падає» без load shedder, тому після цього ми не маємо базових точок для порівняння.)
За невеликого навантаження P99 становить приблизно ~140 мс для всіх варіантів і зростає до ~190 мс, коли система досить завантажена (1 000 RPS). Коли ми перевищуємо межу пропускної здатності (1 500 RPS+), обидва load shedder’и починають працювати, але профіль затримок починає суттєво відрізнятися. QALM досить швидко наближається до межі таймауту в 1 секунду (як для P50, так і для P99), тоді як Cinnamon утримує затримки нижче 500 мс (з P50 приблизно ~180 мс). Зверніть увагу, що розподіл затримок виглядає подібним і для tier 5.
Ключова відмінність у цих випадках полягає в тому, що PID-регулятор у Cinnamon здатний підтримувати стабільний рівень відхилення, завдяки чому уникається осциляція між «відхиляти все» і «не відхиляти нічого» (до чого схильний CoDel). Крім того, за високих значень throughput сервіс настільки перенавантажений, що CoDel вважає всі запити затриманими і відхиляє майже кожен запит (і це лише посилюється використанням одного Go-каналу).
Ми можемо фактично побачити ці коливання коефіцієнта відхилення, якщо наблизити один із випадків RPS. Графіки нижче показують частку успішних і помилкових відповідей, а також час відповіді для Cinnamon і QALM у випадку 4 000 RPS (для порівняння ми також включили 2-хвилинний базовий запуск із 700 RPS).
Рисунок 7: Два графіки показують, як throughput, goodput і затримки змінюються з часом для Cinnamon і QALM, коли ми надсилаємо 4 000 RPS до сервісу. Перший сплеск трафіку (до 700 RPS) є базовим сценарієм без load shedder.
Як видно, коефіцієнт відхилення (жовта лінія) для Cinnamon є досить стабільним (із невеликою кількістю таймаутів на початку через накопичення черги), тоді як QALM постійно повертає таймаути, і як частка успішних відповідей (зелена лінія), так і коефіцієнт відхилення коливаються (наприклад, частка успішних відповідей змінюється приблизно від ~0 до 500).
Взаємодія PID та Auto-Tuner
Ще один цікавий аспект — це взаємодія між PID-регулятором і auto-tuner. Щоб побачити це, розглянемо випадки з 1 500 та 2 000 RPS, які відображені на теплових картах нижче. Верхній графік показує, як змінюється inflight-ліміт, тоді як нижній — коефіцієнт відхилення.
Рисунок 8: Два графіки показують, як inflight-ліміт і auto-tuner взаємодіють у Cinnamon під час роботи на 1 500 і 2 000 RPS.
Спочатку для випадку з 1 500 RPS inflight-ліміт становить приблизно ~240, після чого знижується до ~60 і далі стабілізується на рівні близько 110. Auto-tuner потребує кілька хвилин, щоб виконати це коригування. Тим часом, оскільки ми надсилаємо 1 500 запитів за секунду, формується черга запитів, і в роботу вступає rejector. Коли auto-tuner коригує inflight (а отже і goodput), rejector відповідно налаштовується, щоб підтримувати чергу якомога меншою.
З іншого боку, у випадку з 2 000 RPS inflight-ліміт уже становить 110, тому він не потребує додаткового коригування і залишається на цьому рівні. Відповідно, rejector підтримує стабільний коефіцієнт відхилення на рівні приблизно ~30%.
Підсумок
З Cinnamon ми створили ефективний load shedder, який використовує підходи столітньої давності для динамічного встановлення порогів відхилення та оцінювання пропускної здатності сервісів. Він вирішує проблеми, які ми спостерігали з QALM (і, відповідно, з будь-яким load shedder на основі CoDel), а саме — Cinnamon здатний:
- Швидко знаходити стабільний коефіцієнт відхилення
- Автоматично регулювати пропускну здатність сервісу
- Використовуватися без встановлення будь-яких конфігураційних параметрів
- Мати дуже низькі накладні витрати
Слід зазначити, що під час проєктування та реалізації Cinnamon ми значною мірою надихалися технологіями та ідеями з широкого кола джерел (зокрема, Jaeger, WeChat, Facebook, Netflix та Amazon).