T-Digest: Потокова Оцінка Квантилів

Основна ідея: центроїди замість початкових значень

t-digest ніколи не зберігає окремі дані точки після їхнього поглинання в ескіз; замість цього воно підтримує відсортований набір центроїдів, де кожен центроїд відстежує лише два числа: поточне середнє значення призначених йому значень та кількість значень, які він представляє. Коли приходить новий точковий даних, алгоритм знаходить найближчий центроїд, до якого дозволено об'єднати, враховуючи обмеження розміру, описане нижче, оновлює середнє значення цього центроїда як зважене середнє та збільшує його кількість, або створює новий одиночний центроїд, якщо немає жодного підходящого кандидата для об'єднання. Періодично або безперервно, залежно від реалізації, центроїди перекомпонуються шляхом сортування їх та жадібного злиття сусідніх, поки злиття не тримає кожен центроїд у межах свого обмеження розміру. Результатом є структура даних, пам'яттю якої потрібно лише задану кількість центроїдів, зазвичай в діапазоні кількох сотень, незалежно від того, чи поглинув digest тисячу точок або трильйони, оскільки старі індивідуальні значення ніколи не зберігаються, лише підсумовані центроїди, які приблизно відображають розташування маси розподілу.

Функція масштабування: чому хвоста притаманна більша роздільна здатність

Визначуваним інновацією t-digest є нерівномірне правило розміщення для того, наскільки великий центр розподілу дозволено збільшуватись відповідно до його положення в загальному рангу розподілу. Кожен центр має пов’язану з ним позицію квантиля q, приблизно частку від загального обсягу даних, що лежать нижче нього, і функція масштабування алгоритму відображає q на обмежений розмір, який є малим, коли q близький до 0 або 1, тобто ближче до мінімального або максимального значення даних, і великим, коли q близький до 0.5, медіана. Часто використовувана функція масштабування базується на арксинус-трансформації, k(q), пропорційній (2/π) помноженій на арксинус(2q - 1), яка розтягує поблизу хвостів і стискає в центрі, тому рівні збільшення внутрішнього масштабу k відповідають значно більш дрібній роздільній здатності квантилів поблизу екстремумів, ніж поблизу центру. Практично це означає, що t-digest може виділити десятки маленьких центрів для представлення верхніх та нижніх 1% даних з високою точністю, тоді як середні 98% підсумовуються порівняно невеликою кількістю більших центрів, компроміс, який точно відповідає тому, що більшість реальних випадків використання моніторингу та аналітики піклуються про те, чи перетнув 99,9-й квантиль поріг SLA, а не про те, наскільки латентність медіани становила 40 або 41 мілісекунди.

Об'єднання, пакетне побудови та параметр стиснення

T-Digest розкриває один регульований важіль, зазвичай званий параметром стиснення, який контролює загальний бюджет і, відповідно, компроміс між точністю та пам’яттю. Більше значення параметра стиснення дозволяє більше центроїдів і більш високу роздільну здатність на кожному квантилі, але це вимагає більше пам’яті та трохи більших обчислень на операцію злиття, тоді як менше значення зберігає схему невеликою, але приймає грубішу точність, особливо в хвостах, де менша кількість дозволених центроїдів означає, що середні кластери охоплюють ширший діапазон значень. У багатьох випадках digests будуються поступово, коли дані надходять по одній точці одночасно, але їх також можна будувати більш ефективно пакетно, сортуючи групу буферованих точок і зливаючи їх усі разом проти існуючого списку центроїдів, що амортизує вартість підтримки відсортованого порядку та зазвичай дає трохи більш точний кінцевий digest, ніж вставлення по одній точці одночасно. Особливо корисним є те, що дві незалежно побудовані t-digests, скажімо, з двох різних серверів, кожен з яких узагальнює свій власний сегмент трафіку, можуть бути об’єднані в один поєднаний digest, який приблизно представляє собою об’єднання обох основних наборів даних, що робить t-digest природно підходящим для розподілених та паралельних конвеєрних систем агрегації.

Оцінка квантилів з списку центроїдів

Щоб відповісти на запит квантиля, такий як, що саме значення відповідає 95-му процентилю, алгоритм проходить відсортований список центроїдів, накопичуючи їх кількість до тих пір, поки не буде досягнутий цільовий ранг, потім інтерполює всередині або між відповідними центроїдами, щоб отримати гладку оцінку замість блокуючої та безперервної. Оскільки кожен центроїд представляє кластер значень, приблизно представлений одним середнім значенням, ця інтерполяція є за своєю природою приблизною, і помилка на будь-якому заданому квантилі залежить від того, наскільки грубими є центроїди поблизу цього квантиля, що повертає нас до причини, чому функція scale підтримує тонкі центроїди в хвостових кластерах. Важливо також, що t-digest є зворотним у протилежному напрямку, підтримуючи запити типу кумулятивної функції розподілу, які запитують, який відсоток даних падає нижче певного значення, використовуючи той самий список центроїдів і симметричну схему інтерполяції. Обидва напрямки запитів виконуються за час, пропорний кількості центроїдів, що по суті є миттєвим порівняно з сортуванням повного набору даних, що робить t-digest практичним для інтерактивних дашбордів, які потребують відповідей про процентиль під запитом від потоків даних, що накопичуються в режимі реального часу.

Де знаходиться t-digest у реальних системах

t-digest став стандартним інструментом, де потрібні приблизні відсоткові значення для потокових даних великого обсягу без вартості зберігання кожного спостереження. Він інтегрований в платформи моніторингу та огляду систем для обчислення відсоткових значень затримки запитів у розподілених сервісах, в двигуни запитів великих даних і колонові системи аналітики для приблизних агрегатних функцій над масивними наборами даних, а також у часових серійних базах даних, які ефективно обчислюють відносні відсоткові метрики. Порівняно з альтернативними потоковими схемами квантилів, такими як алгоритм GK (Greenwald-Khanna) або прості фіксовані гістограми, t-digest популярний завдяки тому, що його торгівля між точністю та пам'яттю налаштовується одним інтуїтивно зрозумілим параметром, його сумісність для злиття робить розподілене агрегування простим, і його упередження до точності хвостів природним чином узгоджується з тим, що оператори насправді піклуються, коли спостерігають виробничі системи. Варто пам'ятати про торговлю: t-digest надає приблизні, а не точні відповіді з обмеженнями похибок, які доведені як малі в хвостах, але можуть бути порівняно більшими близько медіани, тому застосунки, яким потрібні точні відсоткові значення для невеликих наборів даних, які комфортно поміщаються в пам'яті, все ще можуть віддавати перевагу методам торта сортування.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте T-Digest: Streaming Quantile Estimation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.