Процентили сбора данных в реальном времени

Question

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

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

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

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

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

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

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

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

Answer 1

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

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

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

Answer 2

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

Итак, ваш вопрос на самом деле заключается в том, «какой лучший способ динамического объединения моих данных»?Существует множество подходов, но если вы хотите свести к минимуму свои предположения о диапазоне или распределении значений, которые вы можете получить, тогда простой подход — усреднить по сегментам фиксированного размера. к, с логарифмически распределенной шириной.Например, предположим, что вы хотите одновременно хранить в памяти 1000 значений.Выберите размер для к, скажем, 100.Выберите минимальное разрешение, скажем, 1 мс.Затем

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

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

По мере поступления новых значений вы можете выбрать способ повторной выборки в зависимости от ваших требований.Например, вы можете отслеживать скользящее среднее, использовать первым прибыл, первым обслужен, или какой-либо другой, более сложный метод.См. Кадемлия алгоритм для одного подхода (используется Битторрент).

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

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

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

Редактировать:Чтобы ответить на ваш комментарий, вот пример простого алгоритма группирования.

• Вы храните 1000 значений в 10 ячейках.Таким образом, каждый интервал содержит 100 значений.Предположим, что каждый контейнер реализован как динамический массив («список» в терминах Perl или Python).

• Когда появляется новое значение:

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

• Чтобы найти 90-й процентиль, отсортируйте ячейку 10.90-й процентиль — это первое значение в отсортированном списке (элемент 900/1000).

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

Другой пример ребининга: понижение частоты дискретизации;например, выбрасывая каждое пятое значение в отсортированном списке.

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

Answer 3

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

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

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

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

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

Приятно, не так ли?:) Подробнее читайте в моем блоге.

Answer 4

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

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

• Быстрый алгоритм для приблизительных квантилей в высокоскоростных потоках данных.

• Экономичные по пространству и времени детерминированные алгоритмы для смещенных квантилей в потоках данных

• Эффективное вычисление смещенных квантилей в потоках данных

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

Answer 5

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

Answer 6

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

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

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