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

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

Итак, ваш вопрос действительно спрашивает: «Как лучше всего динамически объединить мои данные? Существует множество подходов, но если вы хотите минимизировать свои предположения о диапазоне или распределении значений, которые вы можете получить, тогда простой подход состоит в усреднении по сегментам фиксированного размера 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-е значение в отсортированном списке.

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

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

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

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

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

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

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

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

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

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

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

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

[

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

].