Подсчет количества запросов в секунду/минуту на основе временных меток за последние N секунд

Как эффективно использовать память для вычисления 10 запросов в секунду на основе временных меток входящих данных за последние 60 секунд?

У меня есть следующие 10-значные временные метки Unix:

1458573970
1458573970
1458573970
1458573971
1458573972
1458573971
1458573973
1458573975
1458573980

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

В конце концов будет отсечка в 60 секунд, поэтому я хочу отслеживать 60-секундную отсечку для каждых 10 запросов в секунду. (Поэтому мне нужно определить, получаю ли я непрерывно 10 запросов в секунду в среднем в течение последних 60 секунд.)

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

Я думал о том, чтобы сделать что-то подобное, но у меня не совсем сформировано решение.


algorithm sliding-window
person AAA    schedule 27.11.2019    source источник
comment
Можете ли вы уточнить, что вы подразумеваете под средним количеством запросов в секунду? У вас есть 9 запросов за 95 секунд, поэтому среднее количество запросов в секунду будет около 0.1.   -  person Nico Schertler    schedule 27.11.2019
comment
Извините, были опечатки. Я обновил свой вопрос.   -  person AAA    schedule 27.11.2019
comment
Итак, вы хотите иметь окно в 60 секунд и рассчитать частоту запросов для этого окна, скользя по всему вашему набору данных? Или вы знаете, когда происходит отсечка 60 секунд, и вместо этого хотите отдельные окна?   -  person Nico Schertler    schedule 27.11.2019
comment
Да, есть 60-секундная отсечка, но набор данных, который я предоставил, — это всего лишь пример. У нас могут быть тысячи или миллионы меток времени в основном в хронологическом порядке.   -  person AAA    schedule 27.11.2019
comment
Мой вопрос заключался в том, знаете ли вы, в какое время происходит отключение. Или, если вы предпочитаете раздвижное окно.   -  person Nico Schertler    schedule 27.11.2019
comment
Мне нужно раздвижное окно. Я не знаю, когда происходит отсечка, когда я перебираю данные.   -  person AAA    schedule 27.11.2019

Ответы (2)


arrow_upward
0
arrow_downward

Вы можете использовать фильтр EMA. При таком подходе вам нужно всего лишь использовать 2 ячейки памяти, не зависящие от частоты данных и размера окна — rate_accumulator и last_time_event.

См. следующую демонстрацию/тест:

#!/usr/bin/perl

my @data = qw(1558573970 1558573970 1558573970 1558573971 1558573972 1558573971 1558573973 1558573975 1558573980);
my $tlast = 0;
my $rate  = 0;

for(my $t = 1; $t < 100000; $t += 6) { # sim mode
#foreach my $t(@data) { # real data
  my $dt = $t - $tlast;
  if($dt > 0) {
    $rate *= exp(-$dt / 60.0);
  }
  $rate++;
  $tlast = $t;
}

$rate -= 0.5; # Maybe, is not need
print "rate=$rate\n";

Такая система, в которой вычисления exp() заменены двоичными сдвигами (для повышения производительности), используется в подсистеме DNS Amplifying Protection в Emercoin узел.

person olegarch    schedule 27.11.2019
comment
Можете ли вы объяснить, почему мы итерируем от 1 к 100000? - person AAA; 27.11.2019
comment
Это просто создание фиктивного временного ряда для целей моделирования. Вы можете изменить эти параметры, чтобы контролировать длину временного ряда или изменить значение в t+=6. при текущих параметрах отправляет 1 тик в 6 виртуальных секунд, т.е. частота 10 тиков в минуту. Вы можете поиграть с этими параметрами, чтобы протестировать алгоритм на других рядах данных. Или прокомментируйте, раскомментируйте foreach и проверьте свои реальные данные. - person olegarch; 27.11.2019
comment
Спасибо. Как мне проверить запросы в секунду за последние 60 секунд? Это возвращаемое значение? - person AAA; 29.11.2019
comment
Если я ввожу одну и ту же временную метку для этого алгоритма и запускаю цикл 70 раз, я получаю среднюю скорость 70. Но это не учитывает последние 60 секунд средних запросов в секунду, если бы я хотел ограничиться 10 запросами в секунду... - person AAA; 29.11.2019
comment
Алгоритм вычисляет скорость за скользящее окно. Размер окна = 60 с, см. строку -$dt / 60.0. Если вы хотите изменить размер окна - измените 60 на другое значение. Кроме того, если вы хотите перевести скорость в минуту в скорость в секунду, вы можете разделить ее на 60 или другой фактический размер окна. - person olegarch; 29.11.2019
comment
Разделите это на 60 -- разделите что на 60? Оно уже разделено на 60 в exp(-$dt / 60.0). Также является ли $dt разницей между отметкой времени ввода и последней отметкой времени? Трудно читать код. Я не пользователь Perl. - person AAA; 29.11.2019
comment
Да, $dt (дельта-время) — это разница между отметкой времени ввода и последней отметкой времени. Что касается пользователя perl, вы можете прочитать математическую статью в Википедии об EMA, ссылка указана в 1-м абзаце ответа. Или поищите другие математические объяснения или примеры кода. Кроме того, в исходном ответе я предоставил вам информацию о высокопроизводительном приложении, доступном с открытым исходным кодом. Здесь используется тот же алгоритм, который вычисляет пороговое соотношение для нарушителей блоков с высоким соотношением к EMA-окну. Это C, а не Perl: github.com/emercoin/ emercoin/blob/master/src/emcdns.cpp#L1026 - person olegarch; 29.11.2019

arrow_upward
0
arrow_downward

Простой подход со скользящим окном может выглядеть следующим образом:

const windowWidth = 60
int upper = 0 // index of the upper window boundary (exclusive)
for lower from 0 to length of data - 1
    // push the upper bound to include 60 seconds
    while timestamps[upper] - timestamps[lower] < windowWidth
        ++upper
    if upper < length of data - 1
        // Add special handling for the case timestamps[upper - 1] - timestamps[lower] == 0 if needed
        requestRate = (upper - lower) / (timestamps[upper - 1] - timestamps[lower])
        report avg or check for validity
person Nico Schertler    schedule 27.11.2019