come contare il numero di richieste nell’ultimo secondo, minuto e ora

Esiste un ipotetico server Web che supporta solo un’API molto semplice: il conteggio delle richieste ricevute nell’ultima ora, minuto e secondo. Questo server è molto popolare nel mondo e ha ricevuto migliaia di richieste al secondo.

Mirare a trovare come restituire accuratamente questi 3 conteggi ad ogni richiesta?

Le richieste arrivano sempre, quindi la finestra di un’ora, un minuto e un secondo è diversa per richiesta. Come gestire una finestra diversa per richiesta in modo che i conteggi siano corretti per richiesta?

Se è richiesta una precisione del 100%:

Avere una lista collegata di tutte le richieste e 3 conteggi – per l’ultima ora, l’ultimo minuto e l’ultimo secondo.

Avrai 2 puntatori nella lista collegata – per un minuto fa e per un secondo fa.

Un’ora fa sarà alla fine della lista. Ogni volta che l’ora dell’ultima richiesta è più di un’ora prima dell’ora corrente, rimuoverla dall’elenco e diminuire il conteggio delle ore.

I puntatori minuto e secondo punteranno alla prima richiesta che si è verificata rispettivamente dopo un minuto e un secondo fa. Ogni volta che il tempo della richiesta è più di un minuto / secondo prima dell’ora corrente, sposta il puntatore verso l’alto e diminuisce il conteggio dei minuti / secondi.

Quando arriva una nuova richiesta, aggiungila a tutti e 3 i conteggi e aggiungila in primo piano nella lista concatenata.

Le richieste per i conteggi comporterebbero semplicemente la restituzione dei conteggi.

Tutte le operazioni di cui sopra sono ammortizzate tempo costante.

Se è accettabile una precisione inferiore al 100%:

La complessità dello spazio per quanto sopra potrebbe essere un po ‘troppo, a seconda di quante richieste al secondo si otterrebbero in genere; puoi ridurre questo sacrificando leggermente la precisione come segue:

Avere una lista collegata come sopra, ma solo per l’ultimo secondo. Anche avere i 3 conteggi.

Quindi disporre di un array circolare di 60 elementi che indica i conteggi di ciascuno degli ultimi 60 secondi. Ogni volta che passa un secondo, sottrarre l’ultimo (più vecchio) elemento dell’array dal conteggio dei minuti e aggiungere l’ultimo secondo conteggio alla matrice.

Avere un array circolare simile per gli ultimi 60 minuti.

Perdita di precisione: il conteggio dei minuti può essere distriggersto da tutte le richieste in un secondo e il conteggio delle ore può essere distriggersto da tutte le richieste in un minuto.

Ovviamente questo non ha davvero senso se si ha una sola richiesta al secondo o meno. In questo caso puoi mantenere l’ultimo minuto nell’elenco collegato e disporre semplicemente di un array circolare per gli ultimi 60 minuti.

Ci sono anche altre variazioni su questo – il rapporto tra precisione e spazio utilizzato può essere regolato secondo necessità.

Un timer per rimuovere vecchi elementi:

Se rimuovi i vecchi elementi solo quando arrivano nuovi elementi, verrà ammortizzato in tempo costante (alcune operazioni potrebbero richiedere più tempo, ma passeranno in media a tempo costante).

Se si desidera il tempo costante reale, è inoltre ansible eseguire un timer che rimuove i vecchi elementi, e ogni invocazione di questo (e, naturalmente, inserimenti e controllo dei conteggi) richiederà solo un tempo costante, poiché si rimuove al massimo un numero di elementi inseriti nel tempo costante dall’ultimo tick del timer.

Per fare ciò per la finestra temporale di T secondi, disporre di una struttura dati della coda in cui si accodano i timestamp delle singole richieste man mano che arrivano. Quando si desidera leggere il numero di richieste ricevute durante la finestra più recente di T secondi, prima rilasciare dalla “vecchia” fine della coda quei timestamp più vecchi di T secondi, quindi leggere la dimensione della coda. È inoltre necessario eliminare gli elementi ogni volta che si aggiunge una nuova richiesta alla coda per mantenere le sue dimensioni limitate (presupponendo una velocità limitata per le richieste in entrata).

Questa soluzione funziona con precisione arbitraria, ad es. Precisione millisecondo. Se vi accontentate di restituire risposte approssimative, ad esempio per la finestra temporale di T = 3600 (un’ora), consolidate le richieste che rientrano nello stesso secondo in un singolo elemento di coda, rendendo le dimensioni della coda delimitate da 3600. Penso che sarebbe più di bene, ma in teoria perde la precisione. Per T = 1, puoi eseguire il consolidamento a un millisecondo se lo desideri.

In pseudocodice:

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() 

Perché non usare solo un array circolare? Abbiamo 3600 elementi in quella matrice.

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

se vuoi l’ultimo secondo, restituisci l’ultimo elemento di questo array. se vuoi last minute, restituisci la sum degli ultimi 60 elementi. se vuoi l’ultima ora, restituisci la sum dell’intero array (3600 elementi).

Non è la sua una soluzione semplice ed efficace?

Grazie

Deryk

Una soluzione è così:

1) Utilizzare un array circolare di lunghezza 3600 (60 * 60 secondi in un’ora) per conservare i dati per ogni secondo nell’ultima ora.

Per registrare i dati per un secondo nuovo, rilascia i dati dell’ultimo secondo nell’array circolare spostando il puntatore della testa dell’array circolare.

2) In ogni elemento dell’array circolare, invece di contenere il numero di richieste in un determinato secondo, registriamo la sum cumulativa per il numero di richieste che vediamo in precedenza e il numero di richieste per un periodo può essere calcolato da requests_sum.get(current_second) - requests_sum.get(current_second - number_of_seconds_in_this_period)

Tutte le operazioni come increament() , getCountForLastMinute() , getCountForLastHour() possono essere eseguite in tempo O(1) .

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

Ecco un esempio di come funziona.

Se il conteggio delle richieste è richiesto negli ultimi 3 secondi, come segue: 1st second: 2 requests 2nd second: 4 requests 3rd second: 3 requests

L’array circolare sarà simile a questo: sum = [2, 6, 9] dove 6 = 4 + 2 e 9 = 2 + 4 + 3

In questo caso:

1) se vuoi ottenere il conteggio delle richieste dell’ultimo secondo (il conteggio delle richieste del 3 ° secondo), calcola semplicemente la sum[2] - sum[1] = 9 - 6 = 3

2) se si desidera ottenere il conteggio delle ultime due richieste (il conteggio delle richieste del 3 ° secondo e il conteggio delle richieste del secondo secondo), semplicemente calcolando la sum[2] - sum[0] = 9 - 2 = 7

È ansible creare un array di dimensioni 60×60 per ogni secondo nell’ora e utilizzarlo come buffer circolare. Ogni voce contiene il numero di richieste per un dato secondo. Quando ti sposti al secondo successivo, cancellalo e inizia a contare. Quando ci si trova alla fine della matrice, si ricomincia da 0, eliminando in modo efficace tutti i conteggi prima di 1 ora.

  1. Per ora: sum di tutti gli elementi
  2. Minuto: sum di restituzione delle ultime 60 voci (da currentIndex)
  3. Per secondo: conteggio di ritorno su currentIndex

Quindi tutti e tre hanno O (1) spazio e complessità temporale. L’unico inconveniente è che ignora i millisecondi, ma puoi applicare la stessa nozione anche per includere millisecondi.

Il codice seguente è in JS. Ti restituirà il conteggio in O (1). Ho scritto questo programma per un’intervista in cui il tempo era pre-definito di 5 minuti. Ma puoi modificare questo codice per secondi, minuti e così via. Fammi sapere come va.

  1. Crea un object che avrà millisecondi come chiave e contatore come valore
  2. Aggiungi una proprietà denominata totalCount e definiscila come 0
  3. Con ogni contatore di incrementi di accessi definito nel passaggio 1 e totalCount
  4. Aggiungi un metodo chiamato clean_hits, chiama questo metodo ogni millisecondo
  5. Nel metodo clean_hits rimuovi ogni voce (al di fuori del nostro intervallo di tempo) dall’object che abbiamo creato e sottrai quel conteggio da totalCount prima di eliminare la voce

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

Ho dovuto risolvere questo problema in Go, e non penso di aver ancora visto questo approccio, ma potrebbe anche essere molto specifico per il mio caso d’uso.

Poiché si collega a un’API di terze parti e deve limitare le proprie richieste, ho semplicemente tenuto un contatore per l’ultimo secondo e un contatore per gli ultimi 2 minuti (i due contatori di cui avevo bisogno)

 var callsSinceLastSecond, callsSinceLast2Minutes uint64 

Quindi lanciavo le mie richieste in routine separate quando i contatori delle chiamate erano al di sotto del limite consentito

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

E alla fine di ogni routine andavo a decrementare atomicamente il contatore.

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

E sembra funzionare finora senza alcun problema con alcuni test piuttosto pesanti finora.

Che ne pensi di un semplice elenco di timestamp? Ogni volta che si effettua una richiesta, si aggiunge il timestamp corrente all’elenco. E ogni volta che si desidera verificare se si è sotto il limite di velocità, si rimuovono prima i timestamp più vecchi di 1 ora per evitare l’overflow dello stack (hehe) quindi si conta il numero di timestamp nell’ultimo secondo, minuto, qualunque sia.

Potrebbe essere fatto facilmente in 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]) 

Immagino che questo possa essere ottimizzato ma tu vedi l’idea.