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

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

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

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

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

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

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

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

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

Источник

8 ответов

Решение

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

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

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

Источник

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

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

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

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

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

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

http://j.mp/3bTf36

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

Источник

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

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

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

Источник

@thkala начал с цитат из литературы. Позвольте мне расширить это.

Реализации

  • T-дайджест из статьи Даннинга за 2019 год имеет эталонную реализацию на Java и порты на этой странице на Python, Go, Javascript, C++, Scala, C, Clojure, C#, Kotlin и порт C++ от facebook , а также порт ржавчины этот порт С++
  • Spark реализует «GK01» из статьи Гринвальда / Ханны 2001 г. для приблизительных квантилей.
  • Луч: org.apache.beam.sdk.transforms.ApproximateQuantiles имеет приблизительные квантили
  • Java: Guava: com.google.common.math.Quantiles реализует точные квантили, что требует больше памяти .
  • В корзине Rust: quantiles есть реализации алгоритма GK 2001 года «GK01» и алгоритма CKMS 2005 года. (внимание: я обнаружил, что реализация CKMS медленная - )
  • С++: квантили повышения имеют некоторый код, но я его не понял.
  • Я провел некоторое профилирование опций в Rust [ проблемассылка ] для 100 миллионов элементов и нашел GK01 лучшим, T-digest вторым и «сохранять 1% верхних значений в очереди приоритетов» третьим.

Литература

Дешевый хак для P99 <10M значений: просто сохраните верхний 1% в очереди с приоритетом!

Это прозвучит глупо, но если я хочу рассчитать P99 для 10 миллионов float64, я просто создал приоритетную очередь со 100 тысячами float32 (занимает 400 тысяч). Это занимает всего в 4 раза больше места, чем "GK01", и намного быстрее. Для 5 миллионов или меньше предметов он занимает меньше места, чем GK01!!

      struct TopValues {
    values: std::collections::BinaryHeap<std::cmp::Reverse<ordered_float::NotNan<f32>>>,
}

impl TopValues {
fn new(count: usize) -> Self {
    let capacity = std::cmp::max(count / 100, 1);
    let values = std::collections::BinaryHeap::with_capacity(capacity);
    TopValues { values }
}

fn render(&mut self) -> String {
    let p99 = self.values.peek().unwrap().0;
    let max = self.values.drain().min().unwrap().0;
    format!("TopValues, p99={:.4}, max={:.4}", p99, max)
}
fn insert(&mut self, value: f64) {
    let value = value as f32;
    let value = std::cmp::Reverse(unsafe { ordered_float::NotNan::new_unchecked(value) });

    if self.values.len() < self.values.capacity() {
        self.values.push(value);
    } else if self.values.peek().unwrap().0 < value.0 {
        self.values.pop();
        self.values.push(value);
    } else {
    }
}
}
Источник

Попробуйте простой алгоритм, определенный в статье "Последовательная процедура одновременной оценки нескольких процентилей" (Раатикайнен). Он быстрый, требует 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 - бинарный поиск минимального диапазона для x . Если не найден, выберите предыдущий диапазон (где min <x). Если значение принадлежит диапазону (x <= max), увеличить счетчик . В противном случае вставьте новый диапазон с [min = x, max = x, count = 1] .

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

Чтобы получить т.е. p95 пройти от конца, суммируя счет, пока следующее добавление не достигнет пороговой суммы>= 95% , возьмите p95 = min + (max - min) * partial.

Он остановится на динамических диапазонах измерений. n может быть изменено для обмена точности на память (в меньшей степени на процессор). Если вы сделаете значения более дискретными, т.е. округляя до 0,01 перед вставкой - быстрее стабилизируется на диапазонах.

Вы можете повысить точность, не предполагая, что каждый диапазон содержит равномерно распределенные записи, т.е. что-то дешевое, например, сумма значений, которая даст вам avg = sum / count , это поможет более точно прочитать значение p95 из диапазона, в котором оно находится.

Вы также можете вращать их, т.е. после m = 1 000 000 записей начните заполнять новый массив и возьмите p95 как взвешенную сумму по счетчику в массиве (если массив B имеет 10% от счетчика A, то он дает 10% от значения p95).

Источник
Другие вопросы по тегам