PID-регулятор для Cinnamon
Це переклад статті Uber PID Controller for Cinnamon
У попередньому дописі ми розглянули Cinnamon та його основні компоненти. У цій другій частині ми детально розглянемо rejector і, зокрема, як використовуємо PID-регулятори для створення ефективного та мінімалістичного механізму відхилення запитів.
PID-регулятор — це механізм керування із замкненим контуром, який, отримуючи зворотний зв’язок, безперервно намагається звести до нуля обчислене значення похибки, що називається цільовою функцією. Його концептуальна основа відома понад 300 років, а математичне формулювання було надане у 1922 році. Він широко використовується в промисловості — від регулювання температури в печі до керування курсом судна. І виявилося, що вони чудово підходять для швидкого обчислення стабільного коефіцієнта відхилення запитів у load shedder’ах (чого нам не вдалося досягти з альтернативами, такими як AIMD та CoDel).
Рисунок 1: Пневматичний PID-регулятор, де три ручки керують складовими P, I та D.
Основним викликом для Cinnamon було знайти таку цільову функцію для PID-регулятора, яку б можна було перевикористати у різних сервісах без потреби змінювати конфігурацію. В Uber є сервіси, де один інстанс обробляє тисячі запитів за секунду (RPS), і є такі, що обробляють лише 10 RPS на інстанс. З огляду на величезну кількість мікросервісів, нам потрібне рішення без конфігурації. У цьому дописі ми опишемо цільову функцію, як ми її сформували та як вона працює на практиці.
Вступ
Для нагадування: діаграма нижче демонструє архітектуру Cinnamon. У цьому дописі ми зосередимося на частині, виділеній червоною рамкою:
Рисунок 2: Архітектурна діаграма Cinnamon із виділеною частиною PID-регулятора.
Головна мета rejector — визначити, яку частку запитів потрібно відхиляти під час перенавантаження endpoint’а. Ми прагнемо, щоб це співвідношення було стабільним, інакше виникатимуть осциляції затримок. Отже, воно має адаптуватися до патернів сервісу. Також, оскільки логіка Cinnamon застосовується до кожного запиту, додаткові витрати мають бути мінімальними (і за latency, і за використанням ресурсів).
Далі ми покажемо, як ці три цілі досягаються за допомогою PID-регулятора.
Архітектура
Rejector складається з двох частин:
a) online-частина — приймає або відхиляє запит залежно від його пріоритету;
b) offline-частина — періодично (зазвичай кожні 500 мс) перераховує поріг.
Online-частина дуже ефективна: вона зчитує пріоритет запиту та порівнює його з атомарною змінною, що містить поточний поріг. Якщо пріоритет вищий за поріг — запит приймається, інакше — відхиляється.
Offline-частина визначає, чи перевантажений endpoint, і якщо так — який відсоток запитів потрібно відсікти. Цей відсоток перетворюється на поріг пріоритету шляхом аналізу останніх 1 000 запитів. Завдяки цьому Cinnamon автоматично адаптується до змін патернів трафіку.
Для визначення відсотка відсікання Cinnamon використовує PID-регулятор на основі:
- Кількості запитів, що надходять у пріоритетну чергу
- Кількості запитів, що виходять із черги до сервісу
Контекст: PID-регулятор
Перш ніж зануритися в те, як Cinnamon використовує PID controller, ми хочемо коротко описати, як вони працюють загалом (якщо ви вже знайомі з темою — можете пропустити цей розділ).
Уявіть круїз-контроль в автомобілі, завдання якого — визначити, яку потужність повинен видати двигун, щоб перейти з поточної швидкості до цільової (наприклад, з 20 до 80 км/год). Потужність, яку потрібно подати, значною мірою залежить від того, з якою швидкістю ви рухаєтесь зараз (наприклад, на 20 км/год автомобіль має прискорюватися сильніше, ніж на 70 км/год). Коли автомобіль досягає 80 км/год, він в ідеалі повинен підтримувати приблизно той рівень потужності, який зараз подається на двигун. PID-регулятор ідеально підходить для цього випадку, оскільки він динамічно коригує подачу потужності навіть тоді, коли змінюються дорожні умови (наприклад, підйом або спуск).
PID-регулятор складається з трьох частин/складових (пропорційної, інтегральної та диференціальної), де:
- Proportional — це різниця між цільовим значенням і поточним значенням. Отже, чим далі поточне значення від цільового, тим більшою буде складова P.
- Integral — це сума історичних значень P. У прикладі вище, коли круїз-контроль досягає 80 км/год, значення P буде нульовим, але складова I залишатиметься ненульовою і таким чином забезпечить підтримку потужності, щоб автомобіль залишався на 80 км/год.
- Derivative — це швидкість зміни P. Отже, якщо P сильно змінюється, D допомагає дещо згладити цей ефект. (Ми не будемо зупинятися на D, оскільки не виявили його корисним для Cinnamon).
Значення PID у певний момент часу — це зважена сума трьох складових вище, де ваги кожної складової зазвичай називають Kp, Ki та Kd. Цей замкнений контур зворотного зв’язку показано на блок-схемі нижче, а також те, як ми використовуємо його в Cinnamon (на високому рівні):
Рисунок 3: Схема PID-регулятора для Cinnamon
Ідея полягає в тому, що коли сервіс перевантажений, ми використовуємо пропускну здатність запитів для обчислення P(t), яке потім використовується для обчислення складових P, I та D. Результат цього значення подається в Cinnamon (всередині сервісу), що впливає на пропускну здатність запитів (і таким чином знову повертається до PID як зворотний зв’язок).
Якщо вас цікавить математичний опис наведеного вище, ми рекомендуємо статтю у Wikipedia про PID-регулятори. Зверніть увагу, що в математичному формулюванні PID-регуляторів інтегральна складова є сумою за всю історію, тоді як у Cinnamon ми обмежуємо її останніми 30 секундами, щоб зменшити перекриття різних патернів запитів, але в іншому Cinnamon дотримується описаного підходу.
Обчислення відсотка відсікання
Повертаючись до Cinnamon, мета його PID-регулятора — керувати відсотком відхилення таким чином, щоб:
- Він підтримував мінімальну довжину черги очікування, таким чином мінімізуючи час перебування в черзі
- Він підтримував кількість одночасно виконуваних запитів на рівні ліміту, таким чином повністю використовуючи сервіс
Якби ми мали лише ціль №1, можна було б легко створити rejector, який відхиляв би всі запити, окрім одного. У такому випадку часу очікування в черзі не було б, але це суттєво обмежило б пропускну здатність сервісу. Додавання цілі №2 до PID-регулятора означає, що він має певний механізм зворотного тиску, якщо PID «перестарається» та відхилить занадто багато. Якщо порівняти з круїз-контролем: якщо його PID-регулятор перевищить необхідну потужність і подасть забагато енергії на двигун, надлишкова швидкість також створить зворотний тиск у PID-регулятор.
На зображенні нижче показано взаємозв’язок між чергою запитів та inflight-запитами. У цьому прикладі inflight-ліміт дорівнює п’яти (тобто одночасно можуть оброблятися п’ять запитів), з яких обробляються лише три. Крім того, є ще три запити в черзі. Таким чином, ця ситуація порушує обидві цілі: ми не повністю використовуємо inflight-ліміт і маємо запити в черзі. Зверніть увагу, що PID-регулятор не має нічого спільного з оцінюванням inflight-ліміту — це завдання auto-tuner, який буде описано в наступному дописі.
Рисунок 4: Внутрішні компоненти scheduler та зв’язок між inflight і чергою запитів
Беручи це до уваги, ми використовуємо наступну формулу для обчислення значення P для Cinnamon:
tпозначає часовий період (наприклад, 500 мс)in(t)— загальна кількість запитів, що надійшли до черги запитів протягом періоду калібрування (зверніть увагу, що це число включає лише прийняті запити, а не ті, що були відхилені rejector’ом; на діаграмі вище позначено як in)out(t)— кількість запитів, що вийшли з черги протягом періоду калібрування (тобто ті, що передані сервісу для обробки; на діаграмі вище позначено як out)freeInflight(t)— різниця між поточною кількістю inflight-запитів і inflight-лімітом (позначено зеленими блоками на діаграмі вище)out'(t)— ідентичне доout(t), за винятком випадку, колиout(t)дорівнює нулю; тодіout'(t)дорівнює inflightLimit
Якщо розкласти це на складові, інтуїція досить проста. В ідеальному випадку за певний період часу кількість запитів, що надходять у чергу, має дорівнювати кількості запитів, які витягуються з черги та передаються сервісу (іншими словами — переходять у стан inflight). Таким чином, ми приходимо до початкового рівняння:
Ця перша версія говорить, що якщо P1(t) є додатним (тобто in > out), нам потрібно відсікти більше запитів, оскільки черга зростає. З іншого боку, якщо P1(t) є від’ємним (тобто in < out), сервіс спорожнює чергу (що добре), але це може означати, що ми відсікаємо занадто багато. Однак ця версія не враховує рівень використання сервісу. Наприклад, якщо in і out дорівнюють 5, тоді P1(t) дорівнює нулю, і згідно з формулою ми відсікаємо правильно. Але якщо в будь-який момент часу лише один запит переходить у inflight, а ліміт дорівнює 5, ми маємо невикористану пропускну здатність. Тому в наступній ітерації ми розширюємо формулу, щоб врахувати кількість невикористаних inflight-слотів, тобто freeInflight:
У цьому випадку, якщо in(t) і out(t) мають однакове значення, а freeInflight(t) дорівнює нулю, ми маємо ідеальну ситуацію: сервіс повністю насичений, і кількість запитів, що надходять у чергу, дорівнює кількості запитів, що з неї виходять. З іншого боку, якщо freeInflight(t) не дорівнює нулю, а in(t) і out(t) однакові, значення P буде від’ємним і зменшить рівень відсікання, що і є бажаним (ми фактично відхиляємо занадто багато).
Останній крок — врахувати, що різні сервіси обробляють широкий спектр RPS. Якщо, наприклад, in(t) – out(t) = 1 для інстансу сервісу, який обробляє 1 000 RPS, не слід відсікти стільки ж (якщо взагалі потрібно), як у випадку інстансу, що обробляє 1 RPS. Тому ми нормалізуємо значення P кількістю запитів у періоді, що дорівнює out(t). Є один виняток — можуть бути періоди, коли жодного запиту не було оброблено, і тоді ми використовуємо inflightLimit як оцінку нормалізатора. Таким чином, отримуємо наступну формулу:
Варто зазначити, що рівняння не містить явної згадки про кількість таймаутів у черзі, оскільки це неявно враховується в різниці між in(t) та out(t). Також можна запитати: що якщо in більше за out і freeInflight не дорівнює нулю, тоді значення P може дорівнювати нулю (і виглядати як адекватне)? Це не проблема, оскільки коли in більше за out і є вільні inflight-слоти, надлишок вхідних запитів швидко буде призначено до inflight-слотів, що означає, що в наступному періоді перекалібрування freeInflight дорівнюватиме нулю.
З точки зору реалізації це можна зробити дуже ефективно. Потрібні лише два атомарні лічильники в «гарячому» шляху, які інкрементуються, коли запит входить у чергу, і коли він виходить із неї та передається в код сервісу. Таким чином, фоновий процес перекалібрування зберігає останні зафіксовані значення цих двох лічильників і може обчислити різницю з моменту попереднього періоду перекалібрування.
Значення P, визначене вище, обчислюється під час кожного перекалібрування та передається до PID-регулятора, включаючи додавання до історії. Порівняно зі стандартним PID-регулятором, ми трохи модифікували інтегральну складову, зробивши історію обмеженою. Зазвичай інтегральна частина PID-регулятора враховує всю історію (наприклад, для круїз-контролю — від моменту його ввімкнення), але для load shedding ми помітили, що кожен випадок перенавантаження може відрізнятися, тому обмеження історії зменшує перекриття між послідовними перенавантаженнями та краще адаптується до змінних патернів запитів. Зазвичай ми обмежуємо її 30 секундами.
Щоб знайти константи Kp та Ki для рівняння PID, ми провели багатоденний тест, у якому поступово змінювали обидві константи, запускали навантажувальні тести та аналізували результати. У результаті ми виявили, що Kp = 0.1 і Ki = 1.4 працюють найкраще. Існує багато інших методів, які ми могли б використати, але наразі цей підхід добре себе зарекомендував.
Співвідношення до порога
На основі коефіцієнта (ratio), обчисленого PID-регулятором, rejector повинен визначити поріг пріоритету, який необхідно відсікати (нагадаємо, що кожен запит має пріоритет, який ми порівнюємо з порогом). Для цього ми зберігаємо інформацію про останні, скажімо, 1 000 запитів і їхній пріоритет (вибір 1 000 забезпечує хорошу вибірку трафіку навіть для endpoint’ів із високим RPS). Припустімо, що PID-регулятор встановлює коефіцієнт на рівні 10%; ми можемо використати кумулятивний розподіл пріоритетів останніх 1 000 запитів, щоб визначити відповідний поріг, як показано на діаграмі нижче:
Рисунок 5: Кумулятивний розподіл пріоритетів запитів
Для цього сервісу, який отримав однакову кількість запитів від tier 1 до tier 4, поріг у 10% відповідає tier 4 та cohort 84.
Експеримент
У першому дописі ми вже показали, що Cinnamon здатний підтримувати стабільний коефіцієнт відхилення, навіть коли auto-tuner змінює inflight-ліміт. Тому тут ми хочемо зосередитися саме на PID-регуляторі та перевірити, наскільки швидко він може змінювати коефіцієнт відхилення (як у бік збільшення, так і в бік зменшення) у відповідь на зміни навантаження.
Більш конкретно, ми хочемо протестувати PID-регулятор, надсилаючи різні обсяги трафіку до сервісу, а потім відстежити, наскільки швидко PID реагує і як швидко досягає стабільного порогу відхилення. Для цього ми повторно використали ту саму тестову конфігурацію, що й у дописі 1, де тестовий сервіс розподілений на двох бекенд-вузлах і здатний обробляти приблизно ~1 300 RPS загалом. Щоб ізолювати вплив саме PID-регулятора, ми вимкнули auto-tuner і вручну встановили inflight-ліміт. Ми надсилаємо базове навантаження у 1 000 RPS, а потім у різні моменти часу збільшуємо RPS, щоб перевищити ліміт.
Результат цього експерименту показано на графіках нижче (експеримент тривав приблизно ~25 хвилин). Верхній графік показує загальний вхідний RPS (жовта лінія) та goodput/прийнятий RPS (зелена лінія). Нижній графік показує гістограму коефіцієнта відхилення, де кожен інстанс генерує один набір даних кожні 500 мс. Один важливий аспект цих графіків полягає в тому, що базова time-series база даних (M3) має мінімальну роздільну здатність 10 секунд, що означає, що для графіка коефіцієнта відхилення всі точки даних групуються в інтервали по 10 секунд, які видно як «вежі» точок.
Рисунок 6: Вхідний RPS (жовта лінія), прийнятий RPS (зелена), та поріг відхилення
Наприклад, о 16:05 на діаграмі вище ми збільшуємо навантаження з приблизно ~3 000 RPS до ~6 500 RPS (жовта лінія), з яких приблизно ~1 300 RPS приймаються (зелена лінія), а решта — відхиляються. Із підвищенням навантаження коефіцієнт відхилення швидко зростає з ~30% до ~75%, і це займає лише 10 секунд (ймовірно, навіть менше, але ми не можемо це побачити через обмеження часової роздільної здатності). Нарешті, після зростання навантаження коефіцієнт відхилення швидко стабілізується в межах 70%–80%. Ми називаємо цей інтервал у 10 процентних пунктів (також ppt) rejection span, і, як можна помітити, rejection span становить приблизно ~10 ppt для всіх стабільних станів вхідного RPS.
Цікавим є те, що хоча rejection span для заданого RPS становить близько 10 процентних пунктів, цей інтервал не збільшується навіть тоді, коли Cinnamon змушений відхиляти значну частину трафіку. Коли ми експериментували з іншими механізмами (наприклад, AIMD або CoDel), ми зазвичай отримували вузький rejection span, коли коефіцієнт відхилення був малим, але дуже широкий rejection span (наприклад, 30 ppt) при великих коефіцієнтах відхилення (наприклад, >50%). Ми вважаємо, що історична складова PID є ключовою для досягнення цих стабільних інтервалів відхилення, оскільки вона «пам’ятає», що було зроблено раніше, і таким чином запобігає коливанням між повним відхиленням усіх запитів і відсутністю відхилення (до чого схильний CoDel).
Підсумок
Використовуючи PID-регулятор, Cinnamon здатний швидко реагувати на зміни навантаження під час перенавантаження і, що ще важливіше, знаходити стабільне співвідношення відсікання, яке забезпечує мінімальну довжину черги запитів і водночас максимально ефективно використовує ресурси сервісу. Крім того, ми побачили, що PID-регулятор добре працює як для сервісів із низьким трафіком, так і для сервісів із високим трафіком, де зазвичай спостерігається rejection span на рівні приблизно ~10 ppt (чого не було в ранніх ітераціях PID-регулятора).