Как подсчитать количество запросов в последнюю секунду, минуту и ​​час

Ответ 1

Если требуется 100% -ная точность:

У вас есть связанный список всех запросов и 3 подсчета - за последний час, последнюю минуту и ​​последнюю секунду.

У вас будет 2 указателя в связанном списке - минута назад и еще секунду назад.

Час назад будет в конце списка. Всякий раз, когда время последнего запроса больше, чем за час до текущего времени, удалите его из списка и уменьшите счет часов.

Мгновенный и второй указатели указывают на первый запрос, который произошел через минуту и ​​секунду назад соответственно. Всякий раз, когда время запроса больше минуты/секунды до текущего времени, сдвиньте указатель и уменьшите счет минуты/секунды.

Когда приходит новый запрос, добавьте его ко всем 3 подсчетам и добавьте его в начало связанного списка.

Запросы на подсчеты будут просто включать возврат счетчиков.

Все вышеперечисленные операции - это амортизированное постоянное время.

Если допустима точность менее 100%:

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

У вас есть связанный список, как указано выше, но только за последнюю секунду. Также имеют 3 подсчета.

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

Иметь аналогичную круговую матрицу за последние 60 минут.

Потеря точности: счетчик минут может быть отключен всеми запросами в секунду, а счетчик часов может быть отключен всеми запросами через минуту.

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

Существуют и другие варианты этого - коэффициент точности в пространстве может быть скорректирован по мере необходимости.

Таймер для удаления старых элементов:

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

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

Ответ 2

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

Это решение работает до произвольной точности, например. миллисекундной точности. Если вы довольны возвратом приблизительных ответов, вы можете, например, для временного окна T = 3600 (час) консолидируйте запросы, входящие в ту же секунду в один элемент очереди, делая размер очереди ограниченным на 3600. Я думаю, что это было бы более чем нормально, но теоретически теряет точность. Для T = 1 вы можете сделать консолидацию на миллисекундах, если хотите.

В псевдокоде:

queue Q

proc requestReceived()
  Q.insertAtFront(now())
  collectGarbage()

proc collectGarbage()
  limit = now() - T
  while (! Q.empty() && Q.lastElement() < limit)
    Q.popLast()

proc count()
  collectGarbage()
  return Q.size()

Ответ 3

Почему бы просто не использовать круговой массив? У нас есть 3600 элементов в этом массиве.

index = 0;
Array[index % 3600] = count_in_one_second. 
++index;

если вы хотите в последнюю секунду, верните последний элемент этого массива. если вы хотите в последнюю минуту, верните сумму из последних 60 элементов. если вы хотите последний час, верните сумму всего массива (3600 элементов).

Разве это не его простое и эффективное решение?

Спасибо

Deryk

Ответ 4

Следующий код находится в JS. Он вернет вам счет в O (1). Я написал эту программу для интервью, где время было определено как 5 минут. Но вы можете изменить этот код на секунды, минуты и так далее. Дайте мне знать, как это происходит.

• Создайте объект, который будет иметь миллисекунды как ключ и счетчик как значение
• Добавьте свойство totalCount и предопределите его как 0
• С каждым регистратором счетчика приращений, определенного на шаге 1, и totalCount
• Добавьте метод clean_hits, вызовите этот метод каждые миллисекунды

• В методе clean_hits удалите каждую запись (вне нашего временного диапазона) из созданного объекта и вычтите этот счет из totalCount, прежде чем удалять запись

  this.hitStore = { "totalCount" : 0};

Ответ 5

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

• За час: вернуть сумму всех элементов
• Для минут: возврат суммы последних 60 записей (от currentIndex)
• Для второго: количество возвратов на currentIndex

Таким образом, все три имеют O (1) пространство и временную сложность. Единственным недостатком является то, что он игнорирует миллисекунды, но вы можете применить одно и то же понятие, чтобы включить миллисекунды.

Ответ 6

Одно из решений:

1) Используйте круговой массив длиной 3600 (60 * 60 секунд в час), чтобы удерживать данные за каждую секунду в последний час.

Чтобы записать данные за новую секунду, отбросьте последние данные в круговом массиве, перемещая указатель на указатель кругового массива.

2) В каждом элементе массива кругов вместо того, чтобы удерживать количество запросов в определенную секунду, мы записываем суммарную сумму для количества запросов, которые мы видим ранее, и количество запросы на период могут быть рассчитаны на requests_sum.get(current_second) - requests_sum.get(current_second - number_of_seconds_in_this_period)

Все операции типа increament(), getCountForLastMinute(), getCountForLastHour() можно выполнить в O(1) времени.

=============================================== ==========================

Вот пример того, как это работает.

Если у нас есть счетчик запросов за последние 3 секунды, как это: 1st second: 2 requests 2nd second: 4 requests 3rd second: 3 requests

Круговой массив будет выглядеть так: sum = [2, 6, 9] где 6 = 4 + 2 и 9 = 2 + 4 + 3

В этом случае:

1), если вы хотите получить последний второй счетчик запросов (счетчик запросов 3-й секунды), просто вычислив sum[2] - sum[1] = 9 - 6 = 3

2), если вы хотите получить счетчик последних двух секунд (счетчик запросов 3-й и счетчик второго второго запроса), просто вычислив sum[2] - sum[0] = 9 - 2 = 7

Ответ 7

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

В Python это можно сделать легко:

import time

requestsTimestamps = []

def add_request():
    requestsTimestamps.append(time.time())

def requestsCount(delayInSeconds):
    requestsTimestamps = [t for t in requestsTimestamps if t >= time.time() - 3600]
    return len([t for t in requestsTimestamps if t >= time.time() - delayInSeconds])

Я думаю, это можно оптимизировать, но вы видите эту идею.