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

Question

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

Настройте его, чтобы точно определить эти 3 счета для каждого запроса?

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

Answer 1

Чтобы сделать это для временного окна 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() 

Answer 2

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

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

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

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

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

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

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

Все вышеуказанные операции амортизируются постоянным временем.

Если меньше, чем 100% точность приемлема:

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

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

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

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

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

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

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

Таймера удалить старые элементы:

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

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

Answer 3

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

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

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

Answer 4

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

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

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

Не является ли его простым и эффективным решением?

Благодаря

Deryk

Answer 5

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

1. Создание объекта, который будет иметь миллисекунды как ключ и счетчик в качестве значения
2. Добавить свойство TOTALCOUNT и предопределить его быть 0
3. С каждого журнала хитов приращения счетчика, определенного на шаге 1 и TOTALCOUNT
4. Добавить метод называется clean_hits, вызовите этот метод каждую миллисекунду

5. в методе clean_hits удалить каждую запись (вне нашего диапазона времени) от объекта, который мы создали и вычитаем количество из TOTALCOUNT перед вами удалить запись

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

Answer 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-е секундного и количество запросов 2-й секундном), просто вычисление sum[2] - sum[0] = 9 - 2 = 7

Answer 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]) 

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