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

Question

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 2

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

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

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

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

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

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

Answer 3

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

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

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

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 достаточно большой, но ограничен вашими требованиями к памяти), чтобы контролировать, остается ли предположение о нормальности все еще верным.