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

Question

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

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

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

Полезно, чтобы сообщить 90-й процентиль времени отклика, восьмидесятых процентиль времени отклика и т. д.

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

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

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

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

Answer 1

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

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

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

Answer 2

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

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

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

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

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

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

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

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

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

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

• Когда новое значение приходит в:

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

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

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

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

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

Answer 3

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

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

Что касается дополнительных статистических данных: для средних и дисперсий есть nice recursive algorithms, которые занимают очень мало памяти. Эти две статистики могут быть достаточно полезными для множества распределений, потому что central limit theorem утверждает, что распределения, которые возникают из достаточно большого числа независимых переменных, приближаются к нормальному распределению (которое полностью определяется средним значением и дисперсией), вы можете использовать один из normality tests на последнем N (где N достаточно велико, но ограничено вашими требованиями к памяти), чтобы следить за тем, чтобы предположение о нормальности все еще сохраняется.

Answer 4

Я только что опубликовал blog post on this topic. Основная идея состоит в том, чтобы уменьшить потребность в точном вычислении в пользу «95% процентов ответов - 500 мс-600 мс или менее» (для всех точных процентилей 500 мс-600 мс)

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

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

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

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

response times http://j.mp/3bTf36

Ницца, не так ли?:) Read more on my blog.

Answer 5

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

Answer 6

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

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

• A fast algorithm for approximate quantiles in high speed data streams

• Space-and time-efficient deterministic algorithms for biased quantiles over data streams

• Effective computation of biased quantiles over data streams

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