Кевин Чен | Инженер-программист, стажер, Visibility
Брайан Оверстрит | Инженер-программист, видимость

В этом посте мы расскажем об алгоритмах и инфраструктуре, которые мы разработали для создания масштабируемой системы обнаружения аномалий в реальном времени для ключевых показателей рабочего таймсерии Pinterest. Читайте дальше, чтобы узнать о наших знаниях, уроках и планах на будущее.

Фон

Pinterest использует внутреннюю систему показателей и панелей под названием Statsboard, которая позволяет командам в режиме реального времени получать информацию о состоянии своих сервисов. Используя Statsboard, инженеры могут создавать предупреждения, используя язык, который объединяет обычные операции с временными рядами в простой интерфейс. Эти предупреждения включают:

  • Статические пороговые значения. Пороговые значения, которые предупреждают пользователя, когда система или служба достигают уровня (например, 95% использования ЦП), указывающего на какой-либо сбой.
  • Различия между неделями. Сезонные оповещения, которые означают, что точки данных в текущий момент времени на определенную долю ниже (например, на 10%), чем неделей ранее.

Однако многие показатели роста выручки и трафика Pinterest (например, запросы сайтов, логины пользователей) демонстрируют динамические закономерности, которые затрудняют установку предупреждений на основе правил. Без системы обнаружения аномалий, способной построить модель для обработки этих динамических показателей, пользователи сталкиваются с тремя нежелательными ситуациями оповещения:

  • Временная неизменность. Оповещения о статическом пороге, учитывающие снижение сезонных показателей (например, веб-трафика) в течение дня, приведут к ложным срабатываниям в ночное время, когда эти показатели естественным образом уменьшаются. Чтобы зафиксировать поведение процессов генерации метрик, которые меняются со временем, наше оповещение должно быть параметризовано по времени.
  • Крайние случаи правила. Предположим, мы создали статический порог, который разрешает страницы только с 8 утра до 8 вечера. Если инцидент произойдет в 20.01, страница не появится. Пограничные случаи в системах, основанных на правилах, могут привести к слепым пятнам и дополнительным уровням сложности.
  • Нормальная интерпретация аномалий. Если в среду произойдет инцидент, который приведет к снижению показателей всего сайта, в следующую среду мы можем получить массу предупреждений о еженедельном увеличении. Мы должны позаботиться о том, чтобы не рассматривать аномальное поведение как нормальное поведение, иначе мы получим ложные сигналы тревоги, когда вернемся к нормальному состоянию.

Обнаружение аномалий

В мире существует множество литературы по обнаружению аномалий - от пакетов с открытым исходным кодом, таких как AnomalyDetection в Twitter или Luminol от Linkedin, до академических работ, таких как статьи Роба Хайндмана об обнаружении аномалий на основе функций. Мы можем разделить самые популярные из этих методов обнаружения аномалий временных рядов на четыре широкие категории (которые не являются ни исключающими, ни всеобъемлющими):

  1. Модели пространства состояний: экспоненциальное сглаживание, Холт-Винтерс, ARIMA
  2. Декомпозиция: классическая декомпозиция, STL
  3. Глубокое обучение: повторяющиеся нейронные сети
  4. Снижение размерности: RPCA, SOM, дискорд, кусочно-линейный

На практике мы наблюдали лучшую производительность с моделями декомпозиции. Многие модели машинного обучения плохо справляются с обнаружением аномалий из-за их тенденции чрезмерно соответствовать обучающим данным. Для обнаружения аномалий нам необходимо уметь распознавать и извлекать даже аномалии, которых мы раньше не видели. Модели разложения хорошо справляются с этой задачей, явно удаляя коррелированные компоненты (сезонность, тренд) из временных рядов, что дает нам возможность применять статистические тесты с гауссовскими предположениями об остатках, сохраняя при этом исходные атрибуты аномалий.

Требования обнаружения аномалий для наблюдения

Чтобы построить систему обнаружения аномалий для наблюдения, мы должны учитывать ряд требований:

  • Сведите к минимуму ложные срабатывания. Ложные срабатывания вызывают сонливость и злость инженеров, что снижает их чувствительность к предупреждениям, что приводит к снижению производительности и потенциально пропущенным инцидентам в будущем. Чтобы избежать этого, мы предупреждаем только о наиболее серьезных аномалиях и позволяем пользователям создавать собственные правила для предупреждений, если им нужна дополнительная специфичность.
  • Оповещение в течение нескольких минут. При возникновении инцидента дежурные инженеры должны быть уведомлены как можно скорее, чтобы минимизировать воздействие. Мы обрабатываем каждую входящую точку данных в режиме реального времени и определяем, является ли это аномалией, в течение минуты после прибытия.
  • Масштабирование до миллионов временных рядов: наши системы наблюдения обрабатывают сотни миллионов точек данных потоковых данных временных рядов каждую секунду. Алгоритмы декомпозиции уже эффективны по сравнению с большинством методов машинного обучения, но мы вносим некоторые изменения, чтобы добиться дополнительной производительности. Мы также автоматически масштабируем наших специалистов по прогнозированию с помощью Teletraan, чтобы реагировать на возросший спрос.

  • Будьте устойчивы к аномалиям: при возникновении аномалии наша система не должна включать эти данные в нашу оценку нормального поведения. Чтобы избежать этого, мы используем надежную статистику и длинные окна исторических данных (до трех недель).
  • Будьте устойчивы к отсутствию данных. Иногда в показателях могут отсутствовать точки данных. Наиболее распространенная реализация декомпозиции (R’s STL) не поддерживает пропущенные значения, поэтому мы должны позаботиться о том, чтобы допускать подобные пробелы в нашем методе декомпозиции.
  • Примите во внимание возможность принятия мер. Некоторые аномалии гораздо важнее и требуют действий, чем другие. Наши правила, установленные пользователем, могут помочь отфильтровать возможные отклонения от шума.

Далее мы рассмотрим проблемы, с которыми мы столкнулись при развертывании наших моделей в режиме реального времени.

Как обновить нашу модель в режиме реального времени?

Большая часть литературы по обнаружению аномалий посвящена поиску ретроспективных аномалий в статическом наборе данных, то есть подгонке модели с помощью процедуры нелинейной оптимизации, такой как LBFGS или Nelder-Mead, а затем выявлении аномалий в обучающем наборе.

Однако, если мы хотим найти аномалии в реальном времени, однократного обучения недостаточно - мы должны постоянно поддерживать нашу модель в актуальном состоянии, чтобы адаптироваться к последнему поведению нашей метрики. Таким образом, мы должны использовать один из четырех подходов к обновлению параметров нашей модели с течением времени.

  1. Обновления методом грубой силы. Самое простое решение - просто пересчитывать наши параметры в самом последнем окне данных каждый раз, когда поступает новая точка данных. Однако это может быть невозможно, если подгонка модели к окну слишком сложна в вычислительном отношении.
  2. Запланированные обновления. Мы можем кэшировать параметры нашей модели на определенный период времени, например, 24 часа, и повторно обучать новые точки данных в конце каждого периода. Однако может возникнуть чрезмерное количество ложных срабатываний, если поведение нашей метрики изменится до запланированного обновления.
  3. Обновления, управляемые событиями: если была обнаружена высокая ошибка прогноза для недавнего набора точек данных, мы можем использовать это как возможность повторно вычислить параметры нашей модели. Обновления, связанные с событиями, непредсказуемы, что может привести к операционным проблемам в будущем.
  4. Онлайн-обновления: некоторые алгоритмы также можно переформулировать для работы в онлайн-настройках: постоянное считывание новых точек данных и эффективное обновление параметров для каждой точки данных.

В нашем случае мы обнаружили, что операционные издержки на отладку систем по расписанию или событий перевешивают их преимущества. Вместо этого мы используем онлайн-обновления, когда они доступны, и обновления методом грубой силы в противном случае. Чтобы преобразовать наши алгоритмы в онлайн-настройку, мы используем Online Gradient Descent в качестве оптимизатора.

Оценка сезонности и тенденций

Наиболее часто используемая сегодня форма декомпозиции, называемая STL, использует процедуру регрессии под названием Loess, которая неоднократно подбирает полиномы низкой степени для подмножеств данных. К сожалению, эта процедура не масштабируется для аналитики в реальном времени.

Вместо оценки сезонности с итеративным методом Лёсса мы вместо этого используем простой набор эффективных методов оценки сезонности (например, Фурье, историческая выборка). Мы также заменяем компонент тренда в STL надежной статистикой, а именно. медиана, основанная на алгоритме обнаружения аномалий S-H-ESD в Твиттере.

Интервалы прогнозов

Когда у нас есть прогнозы, мы можем использовать интервалы прогнозирования, чтобы определить, является ли точка данных аномалией, на основе ее расстояния от нашего прогноза. Для этого мы можем воспользоваться правилом трех сигм, которое гласит, что 99,73% значений нормального распределения лежат в пределах трех стандартных отклонений от среднего. Если входящая точка данных составляет более трех стандартных отклонений остатка от нашего прогноза, мы можем обоснованно классифицировать эту точку как аномалию.

Если остаточные данные не являются нормальными (например, когда временной ряд содержит аномалии), мы можем использовать преобразования мощности, чтобы попытаться восстановить нормальный набор данных. Но если эти преобразования не работают, мы все равно можем прибегнуть к другим мерам, например к выборке из предыдущих ошибок, чтобы получить оценку неопределенности.

После того, как мы сгенерировали эти интервалы, мы можем преобразовать их в визуальные полосы на стороне пользовательского интерфейса для простоты интерпретации и настройки нашими конечными пользователями.

Теперь давайте посмотрим на инфраструктуру, которая поддерживает эти алгоритмы.

Архитектура обнаружения аномалий

У нас есть сервер прогнозирования, который отвечает за построение прогнозов на один шаг вперед для показателей Statsboard в режиме реального времени и сохранение их в нашей базе данных временных рядов (TSDB).

Сервер прогнозирования состоит из набора работников автомасштабирования и сервера с очередью заданий и планировщиком, который каждую минуту отправляет задания с прогнозом на один вперед. Для пакетных заданий мы предварительно объединяем перекрывающиеся запросы окна данных, чтобы минимизировать сеть и операции ввода-вывода. Мы интегрируемся с существующим пользовательским интерфейсом Statsboard и инфраструктурой предупреждений, чтобы предоставить средства обнаружения аномалий, предупреждения и информационные панели.

Резюме

Обнаружение аномалий играет важную роль в обеспечении видимости показателей, которые демонстрируют сложные закономерности, которые нельзя смоделировать с помощью традиционных предупреждений. Обнаруженные аномалии отображаются на информационных панелях в реальном времени и предупреждают соответствующих пользователей, когда что-то идет не так.

Благодаря использованию надежных, масштабируемых и интерпретируемых алгоритмов наша система обнаружения аномалий помогает инженерам распознавать инциденты и реагировать на них по мере их возникновения, сводя к минимуму влияние на бизнес Pinterest и наших пиннеров.

Благодарности

Дай Нгуен создал пользовательский интерфейс для этого проекта. Особая благодарность Наоману Аббасу, Хумшину Гео, Колину Пробаско и Вей Чжу из команды Visibility, а также Егору Горшкову из команды Traffic за рекомендации по дизайну и проверку.