algorithm - minutos - Cómo contar el número de solicitudes en el último segundo, minuto y hora.

minutos a horas

Question

Existe un servidor web hipotético que admite solo una API muy simple: recuento de solicitudes recibidas en la última hora, minutos y segundos. Este servidor es muy popular en el mundo y recibió miles de solicitudes por segundo.

¿Desea encontrar la forma de devolver con precisión estos 3 puntos a cada solicitud?

Las solicitudes llegan todo el tiempo, por lo que la ventana de una hora, un minuto y un segundo es diferente por solicitud. ¿Cómo administrar una ventana diferente por solicitud para que los recuentos sean correctos por solicitud?

Answer 1

¿Por qué no usar una matriz circular? Tenemos 3600 elementos en esa matriz.

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

Si desea el último segundo, devuelva el último elemento de esta matriz. Si desea el último minuto, devuelva la suma de los últimos 60 elementos. Si desea la última hora, devuelva la suma de toda la matriz (3600 elementos).

¿No es su solución simple y efectiva?

Gracias

Deryk

Answer 2

¿Qué pasa con una simple lista de marcas de tiempo? Cada vez que realiza una solicitud, agrega la marca de tiempo actual a la lista. Y cada vez que quiera verificar si está por debajo del límite de velocidad, primero elimine las marcas de tiempo anteriores a 1 hora para evitar el desbordamiento de pila (jeje) y luego cuente la cantidad de marcas de tiempo en el último segundo, minuto, lo que sea.

Se podría hacer fácilmente en 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])

Supongo que esto puede optimizarse pero ves la idea.

Answer 3

Para hacer esto por la ventana de tiempo de T segundos, tenga una estructura de datos de cola en la que coloque las marcas de tiempo de las solicitudes individuales a medida que llegan. Cuando desee leer el número de solicitudes recibidas durante la ventana más reciente de T segundos, primero elimine del final "antiguo" de la cola las marcas de tiempo que son más antiguas que T segundos, luego lea el tamaño de la cola. También debe eliminar elementos cada vez que agregue una nueva solicitud a la cola para mantener su tamaño limitado (asumiendo una tasa limitada para las solicitudes entrantes).

Esta solución funciona con una precisión arbitraria, por ejemplo, una precisión de milisegundos. Si está contento con devolver respuestas aproximadas, puede, por ejemplo, para la ventana de tiempo de T = 3600 (una hora), consolidar las solicitudes que llegan en el mismo segundo en un solo elemento de la cola, haciendo que el tamaño de la cola esté delimitado por 3600. Creo que sería más que bien, pero teóricamente pierde precisión. Para T = 1, puede hacer la consolidación en el nivel de milisegundos si lo desea.

En pseudocódigo:

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 4

Puede crear una matriz de tamaño 60x60 por cada segundo en la hora y usarla como búfer circular. Cada entrada contiene el número de solicitudes para un segundo dado. Cuando pase al siguiente segundo, bórrelo y comience a contar. Cuando se encuentra en el final de la matriz, comienza nuevamente desde 0, por lo que se eliminan todos los conteos antes de 1 hora.

1. Por hora: retorno de la suma de todos los elementos.
2. Por minuto: devuelve la suma de las últimas 60 entradas (de currentIndex)
3. Para el segundo: volver a contar en el currentIndex

Así que los tres tienen O (1) espacio y complejidad de tiempo. El único inconveniente es que ignora los milisegundos, pero también puede aplicar la misma noción para incluir los milisegundos.

Answer 5

Tuve que resolver este problema en Go, y no creo que haya visto este enfoque todavía, pero también puede ser muy específico para mi caso de uso.

Como se está conectando a una API de terceros y necesita limitar sus propias solicitudes, simplemente mantuve un contador durante el último segundo y un contador durante los últimos 2 minutos (los dos contadores que necesitaba)

var callsSinceLastSecond, callsSinceLast2Minutes uint64

Luego lanzaría mis solicitudes en rutinas separadas de Go cuando los contadores de llamadas estaban por debajo de mi límite permitido

for callsSinceLastSecond > 20 || callsSinceLast2Minutes > 100 {
    time.Sleep(10 * time.Millisecond)
}

Y al final de cada rutina de ir, disminuiría atómicamente el contador.

go func() {
    time.Sleep(1 * time.Second)
    atomic.AddUint64(&callsSinceLastSecond, ^uint64(0))
}()

go func() {
    time.Sleep(2 * time.Minute)
    atomic.AddUint64(&callsSinceLast2Minutes, ^uint64(0))
}()

Y eso parece funcionar hasta ahora sin ningún problema con algunas pruebas bastante pesadas hasta ahora.

Answer 6

Una solución es así:

1) Use una matriz circular de longitud 3600 (60 * 60 segundos en una hora) para mantener los datos de cada segundo en la última hora.

Para registrar los datos para un segundo nuevo, suelte los datos del último segundo en la matriz circular moviendo el puntero de la cabeza de la matriz circular.

2) En cada elemento de la matriz circular, en lugar de mantener el número de solicitudes en un segundo en particular, registramos la suma acumulada para el número de solicitudes que vemos anteriormente, y la cantidad de solicitudes para un período se puede calcular con requests_sum.get(current_second) - requests_sum.get(current_second - number_of_seconds_in_this_period)

Todas las operaciones como increament() , getCountForLastMinute() , getCountForLastHour() se pueden realizar en O(1) .

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

Aquí hay un ejemplo de cómo funciona esto.

Si tenemos un recuento de solicitudes en los últimos 3 segundos como este: 1st second: 2 requests 2nd second: 4 requests 3rd second: 3 requests

La matriz circular se verá así: sum = [2, 6, 9] donde 6 = 4 + 2 y 9 = 2 + 4 + 3

En este caso:

1) si desea obtener el recuento de la solicitud del último segundo (el recuento de la solicitud del tercer segundo), simplemente calcule la sum[2] - sum[1] = 9 - 6 = 3

2) si desea obtener el recuento de solicitudes de los últimos dos segundos (el recuento de solicitudes del tercer segundo y el recuento de solicitudes del segundo segundo), simplemente calcule la sum[2] - sum[0] = 9 - 2 = 7

Answer 7

Following código está en JS. Le devolverá el conteo en O (1). Escribí este programa para una entrevista en la que el tiempo estaba predefinido en 5 minutos. Pero puede modificar este código por segundos, minutos, etc. Déjame saber como va.

1. Cree un objeto que tendrá milisegundos como clave y contador como valor
2. Agregue una propiedad llamada totalCount y predefina para ser 0
3. Con cada registro de registro de incremento de aciertos definido en el paso 1 y el totalCount
4. Agregue un método llamado clean_hits, llame a este método cada milisegundo

5. En el método clean_hits, elimine cada entrada (fuera de nuestro rango de tiempo) del objeto que creamos y reste esa cantidad de totalCount antes de eliminar la entrada

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

Answer 8

Si se requiere 100% de precisión:

Tenga una lista enlazada de todas las solicitudes y 3 recuentos: para la última hora, el último minuto y el último segundo.

Tendrá 2 punteros en la lista de enlaces, hace un minuto y hace un segundo.

Hace una hora estará al final de la lista. Siempre que la hora de la última solicitud sea más de una hora antes de la hora actual, elimínela de la lista y disminuya el número de horas.

Los punteros de minutos y segundos apuntarán a la primera solicitud que ocurrió después de un minuto y un segundo, respectivamente. Siempre que la hora de la solicitud sea más de un minuto / segundo antes de la hora actual, mueva el puntero hacia arriba y disminuya la cuenta de minutos / segundos.

Cuando llegue una nueva solicitud, agréguela a los 3 conteos y agréguela al frente de la lista enlazada.

Las solicitudes de los recuentos simplemente implicarían devolver los recuentos.

Todas las operaciones anteriores se amortizan a tiempo constante.

Si se acepta una precisión inferior al 100%:

La complejidad de espacio para lo anterior podría ser un poco demasiado, dependiendo de cuántas solicitudes por segundo obtendría normalmente; puede reducir esto sacrificando ligeramente la precisión de la siguiente manera:

Tenga una lista de enlaces como la anterior, pero solo para el último segundo. También tienen los 3 cargos.

Luego, tenga una matriz circular de 60 elementos que indiquen los conteos de cada uno de los últimos 60 segundos. Cada vez que pase un segundo, reste el último elemento (el más antiguo) de la matriz de la cuenta de minutos y agregue la última cuenta de segundo a la matriz.

Tener una matriz circular similar durante los últimos 60 minutos.

Pérdida de precisión: el conteo de minutos puede estar desactivado por todas las solicitudes en un segundo y el conteo de horas puede estar desactivado por todas las solicitudes en un minuto.

Obviamente, esto realmente no tendrá sentido si solo tiene una solicitud por segundo o menos. En este caso, puede mantener el último minuto en la lista enlazada y solo tener una matriz circular durante los últimos 60 minutos.

También hay otras variaciones en esto: la relación entre la precisión y el espacio utilizado se puede ajustar según sea necesario.

Un temporizador para eliminar elementos antiguos:

Si elimina elementos antiguos solo cuando ingresan elementos nuevos, se amortizará el tiempo constante (algunas operaciones pueden demorar, pero promediarán el tiempo constante).

Si desea un verdadero tiempo constante, también puede tener un temporizador en ejecución que elimine elementos antiguos, y cada invocación de este (y, por supuesto, las inserciones y la comprobación de los recuentos) solo tomará un tiempo constante, ya que se eliminan a lo sumo un número máximo de Elementos insertados en el tiempo constante desde el último tick del temporizador.