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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  • Determine which bin it should be stored in, based on the bin limits you've chosen.
  • Если корзина не заполнена, добавьте значение в список корзин.
  • Если корзина заполнена, удалите значение в верхней части списка ящиков и добавьте новое значение в конец списка ящиков. Это означает, что старые ценности со временем выбрасываются.

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

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

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

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

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

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

Поскольку недавно мы почувствовали, что время отклика одного из наших веб-приложений ухудшилось, мы решили потратить некоторое время на настройку производительности приложений. В качестве первого шага мы хотели получить полное представление о текущем времени отклика. Для оценки производительности использование минимального, максимального или среднего времени отклика - плохая идея: «Среднее» - это зло оптимизации производительности и часто так же полезно, как «средняя температура пациента в больнице» »( Блог производительности MySQL < / а>). Вместо этого настройщикам производительности следует смотреть на процентиль: «Процентиль - это значение переменной, ниже которого падает определенный процент наблюдений» (Википедия). Другими словами: 95-й процентиль - это время, за которое 95% запросов были выполнены. Следовательно, целевые показатели производительности, связанные с процентилем, могут быть похожи на «95-й процентиль должен быть ниже 800 мс». Установление таких целей производительности - это одно, а эффективное отслеживание их для действующей системы - другое.

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

Такого решения, на которое я надеялся, похоже, просто не существует. Поразмыслив, я пришел к другой идее: для того типа оценки эффективности, который я искал, нет необходимости получать точный процентиль. Примерного ответа вроде «95-й процентиль составляет от 850 мс до 900 мсек» будет вполне достаточно. Снижение требований таким образом делает реализацию чрезвычайно простой, особенно если известны верхняя и нижняя границы возможных результатов. Например, меня не интересуют времена отклика, превышающие несколько секунд - они в любом случае очень плохи, независимо от того, 10 или 15 секунд.

Итак, вот идея реализации:

1. Определите любое случайное количество периодов времени ответа (например, 0-100ms, 100-200ms, 200-400ms, 400-800ms, 800-1200ms,…)
2. Подсчитайте количество ответов и количество ответов в каждом сегменте (для времени ответа 360 мс увеличьте счетчик для сегмента 200–400 мс)
3. Оцените n-й процентиль, суммируя счетчик для сегментов, пока сумма не превысит n процентов от общей суммы.

Это так просто. И вот код.

Некоторые основные моменты:

public void increment(final int millis) {
    final int i = index(millis);
    if (i < _limits.length) {
        _counts[i]++;
    }
    _total++;
}
 
public int estimatePercentile(final double percentile) {
    if (percentile < 0.0 || percentile > 100.0) {
        throw new IllegalArgumentException("percentile must be between 0.0 and 100.0, was " + percentile);
    }
 
    for (final Percentile p : this) {
        if (percentile - p.getPercentage() <= 0.0001) {
            return p.getLimit();
        }
    }
    return Integer.MAX_VALUE;
}

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

Кстати, используя Google Charts и счетчики 60 процентилей, я смог построить красивый график из одного часа собранных времен ответа:

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

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

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

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

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

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

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

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

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

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

Вы можете попробовать следующую структуру:

Взять на вход н, т.е. n = 100.

Мы будем хранить массив диапазонов [min, max], отсортированных по min с count.

Вставка значения x - бинарный поиск min диапазона для x. Если не найден, выберите предыдущий диапазон (где min ‹x). Если значение принадлежит диапазону (x ‹= max), увеличьте count. В противном случае вставьте новый диапазон с помощью [min = x, max = x, count = 1].

Если количество диапазонов достигает 2 * n - свернуть / объединить массив в n (половину), взяв min из нечетного и max < / em> от четных записей, суммируя их количество.