Процентные значения захвата данных в реальном времени

Я ищу алгоритм, который определяет процентили для записи живых данных.

Например, рассмотрим разработку серверного приложения.

Сервер может иметь время ответа следующим образом: 17 мс 33 мс 52 мс 60 мс 55 мс и др.

Полезно сообщить время ответа 90-го процентиля, время ответа 80-го процентиля и т.д.

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

Использование памяти масштабируется линейно с количеством запросов.

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

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

Ответ 1

Я считаю, что для этой проблемы существует много хороших приближенных алгоритмов. Хорошим первым решением является простое использование массива фиксированного размера (скажем, 1 тыс. Данных). Исправьте некоторую вероятность p. Для каждого запроса с вероятностью p запишите время его ответа в массив (заменив самое старое время там). Поскольку массив представляет собой подвыборку прямого потока, и поскольку подвыборка сохраняет распределение, то статистика по этому массиву даст вам приблизительную статистику полного потока в реальном времени.

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

Если вы обнаружите, что вам нужно слишком много памяти, чтобы дать вам достаточно точные статистические данные, вам придется больше копать. Хорошие ключевые слова: "потоковые вычисления", "статистика потока" и, конечно, "процентили". Вы также можете попробовать "ire и curses".

Ответ 2

Если вы хотите сохранить постоянное использование памяти, когда получаете все больше и больше данных, вам придется перепрофилировать эти данные как-то. Это означает, что вы должны применить какую-то схему rebinning. Вы можете подождать, пока вы не приобретете определенное количество сырых входов, прежде чем начинать реинжиниринг, но вы не можете полностью его избежать.

Итак, ваш вопрос действительно спрашивает: "Какой лучший способ динамического заполнения моих данных"? Существует множество подходов, но если вы хотите свести к минимуму свои предположения о диапазоне или распределении значений, которые вы можете получить, тогда простой подход заключается в среднем по ведрам фиксированного размера k с логарифмически распределенной шириной. Например, скажем, вы хотите сохранить 1000 значений в памяти в любой момент времени. Выберите размер для k, скажем 100. Выберите минимальное разрешение, скажем, 1 мс. Тогда

Первое ведро имеет значения между 0-1ms (width = 1ms)
Второе ведро: 1-3 мс (w = 2 мс)
Третий ковш: 3-7 мс (w = 4 мс)
Четвертое ведро: 7-15 мс (w = 8 мс)
...
Десятый ведро: 511-1023 мс (w = 512 мс)

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

По мере ввода новых значений вы можете выбрать, как вы хотите выполнить повторную выборку, в зависимости от ваших требований. Например, вы можете отслеживать скользящую среднюю , используйте first-in- first-out или какой-либо другой более сложный метод. См. Алгоритм Kademlia для одного подхода (используется Bittorrent).

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

Если вас действительно интересуют плюсы и минусы, то ответа на этот форум не может быть достаточно. Вы должны изучить теорию выборки. Там доступно огромное количество исследований по этой теме.

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

Изменить. Чтобы ответить на ваш комментарий, здесь приведен пример простого алгоритма бининга.

Вы сохраняете 1000 значений в 10 бункерах. Поэтому каждый бит содержит 100 значений. Предположим, что каждый бит реализован как динамический массив ( "список", в терминах Perl или Python).
Когда появляется новое значение:
- Определите, в каком ящике он должен быть сохранен, в зависимости от выбранных вами ограничений.
- Если бит не заполнен, добавьте его в список bin.
- Если бит заполнен, удалите значение в верхней части списка bin и добавьте новое значение в конец списка bin. Это означает, что старые значения сбрасываются со временем.
Чтобы найти 90-й процентиль, сортируйте мусор 10. 90-й процентиль - это первое значение в отсортированном списке (элемент 900/1000).

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

Еще один пример перестройки - downsampling; выбрасывая каждое пятое значение в отсортированном списке, например.

Надеюсь, этот конкретный пример поможет. Ключевым моментом, который следует убрать, является то, что существует множество способов достижения постоянного алгоритма старения памяти; только вы можете решить, что удовлетворительно, учитывая ваши требования.

Ответ 3

Я только что опубликовал пост в блоге на эту тему. Основная идея состоит в том, чтобы уменьшить требование для точного расчета в пользу "95% процентов ответов занимают 500 мс - 600 мс или меньше" (для всех точных процентилей 500 мс - 600 мс)

Вы можете использовать любое количество сегментов любого произвольного размера (например, 0 мс-50 мс, 50 мс-100 мс,... все, что соответствует вашему сценарию использования). Как правило, это не должно быть проблемой для всех запросов, которые превышают определенное время ответа (например, 5 секунд для веб-приложения) в последнем сегменте (то есть> 5000 мс).

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

Этот подход требует только 8 байт на сегмент, что позволяет отслеживать 128 блоков с 1 КБ памяти. Более чем достаточно для анализа времени отклика веб-приложения с гранулярностью 50 мс).

Например, вот диаграмма Google, которую я создал за 1 час захваченных данных (используя 60 счетчиков с 200 мс на ведро):

Хорошо, не правда ли? :) Читайте больше на моем блоге.

Ответ 4

(Прошло довольно много времени с тех пор, как был задан этот вопрос, но я хотел бы указать на несколько связанных научных работ)

Прошло немало исследований по приблизительным процентилям потоков данных за последние несколько лет. Несколько интересных работ с полными определениями алгоритмов:

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

Ответ 5

Попробуйте простой алгоритм, определенный в статье "Последовательная процедура для одновременного оценивания нескольких процентов" (Raatikainen). Его быстро, требуется 2 * м + 3 маркера (для m процентилей) и быстро приближается к точному приближению.

Ответ 6

Используйте динамический массив T [] больших целых чисел или что-то, где T [n] подсчитывает количество раз, когда время отклика составляло n миллисекунд. Если вы действительно делаете статистику в серверном приложении, то, возможно, время ответа 250 мс - ваш абсолютный лимит. Таким образом, ваш 1 КБ содержит одно 32-битное целое число для каждых мс между 0 и 250, и у вас есть место для переполнения бункера. Если вы хотите что-то с большим количеством бункеров, пойдите с 8-битными номерами на 1000 ящиков, а в тот момент, когда счетчик будет переполняться (т.е. 256-й запрос в это время ответа), вы смещаете биты во всех ячейках вниз на 1. (эффективно уменьшая вдвое значение в все бункеры). Это означает, что вы игнорируете все ящики, которые захватывают менее 1/127-й задержки, которые вылавливает наиболее посещаемый бит.

Если вам действительно нужен набор конкретных ящиков, я бы предложил использовать первый день запросов, чтобы создать разумный фиксированный набор ящиков. Любая динамика будет довольно опасной в реальном приложении с высокой чувствительностью к производительности. Если вы выберете этот путь, вам лучше знать, что вы делаете, или однажды вы получите вызов из постели, чтобы объяснить, почему ваш статистический трекер внезапно поедает 90% процессор и 75% памяти на рабочем сервере.

Что касается дополнительных статистических данных: для средних и дисперсий есть несколько хороших рекурсивных алгоритмов, которые занимают очень мало памяти. Эти две статистики могут быть достаточно полезными для множества распределений, потому что главная центральная предельная теорема утверждает, что распределения, которые возникают из достаточно большого числа независимые переменные подходят к нормальному распределению (которое полностью определяется средним значением и дисперсией), вы можете использовать один из <нормальных тестов > на последнем N ( где N достаточно велико, но ограничено вашими требованиями к памяти), чтобы следить за тем, чтобы предположение о нормальности все еще сохраняется.