Statistiche in tempo reale degli ultimi 60 secondi con O (1) tempo e memoria [chiusa]

Question

Statistiche in tempo reale degli ultimi 60 secondi con O (1) tempo e memoria [chiusa]

#1 da (2 voti)
#2 da (0 voti)

1

Quale sarebbe un design pulito per un'app che memorizzasse le transazioni e restituisca una panoramica di quelle ricevute negli ultimi 60 secondi, operanti in tempo e memoria costanti (O (1))?

L'app dovrebbe esporre due endpoint, uno di loro in POST una nuova transazione e l'altro in GET le statistiche basate sulle transazioni degli ultimi 60 secondi. Come detto, entrambi devono essere eseguiti in O (1).

Alcune settimane fa mi è stato fornito questo requisito come parte di una sfida di codice, quindi assumiamo una piccola app in una singola macchina. Il mio approccio era il salvataggio delle transazioni sia su DB che su una cache, e avendo un'attività periodica, attivata ogni 1 ms, rimuovendo le voci più vecchie di 60 dalla cache. Quindi, scaricare le statistiche da esso era semplice. Penso che questo si traduca in O (1) per entrambi gli endpoint, ma ovviamente c'è un problema serio con questo approccio perché sono stato immediatamente respinto.

design architecture performance real-time caching

posta saralor 29.08.2017 - 12:54

fonte

2 risposte

Leggi altre domande sui tag design architecture performance real-time caching

Come controllare le dipendenze opzionali di una libreria di sola intestazione in 'CMake'? Controllo delle modifiche dell'utente dell'applicazione Web

score 2 · Answer 1

Bene, è abbastanza semplice:

Definisci la granularità dei tuoi rapporti.
Ottieni un array per 60 secondi, memorizzando il tempo e le statistiche cumulative per quel quantum.
Quando ottieni un rapporto, usa il modulo slot (now () / quantum) (60 secondi / quantum):
1. Se l'ora non è ora (), reimposta il record per now ().
2. Aggiungi i dati dei rapporti.
Quando ricevi una richiesta, aggiungi tutte le voci corrispondenti dai (60 secondi / quantici) della matrice per ottenere le statistiche finali e restituiscile.

In alternativa, se ottieni almeno un rapporto per quanto riguarda il quantum (potresti essere in grado di inserire i rapporti NULL secondo necessità), o puoi accettare una leggera variabilità nel tempo di elaborazione dei rapporti, puoi ottimizzare il ritorno delle statistiche:

Definisci granularità dei rapporti.
Ottieni un array per 60 secondi più uno, memorizzando le statistiche cumulative per la durata del programma.
Quando ottieni un rapporto, imposta tutti i record dall'ultimo aggiornamento effettuato uguale all'ultima su cui hai lavorato. Quindi aggiungi i dati dei rapporti al record corrente.
Quando ricevi una richiesta, restituisci la differenza tra il record corrente e quello di 60 secondi fa.

score 0 · Answer 2

Forse questo approccio potrebbe funzionare:

PUT(transaction):
  stats_hashtable[current_time()].calculate_and_append(transaction.data)
  stats_hashtable[current_time() + 1].calculate_and_append(transaction.data)
  stats_hashtable[current_time() + 2].calculate_and_append(transaction.data)
  //... and so on for each second until the next 60 seconds...
  stats_hashtable[current_time() + 59].calculate_and_append(transaction.data)
  stats_hashtable[current_time() + 60].calculate_and_append(transaction.data)


GET:
  overview_stats = stats_hashtable[current_time()]
  return overview_stats

EDIT: il mio approccio sopra è strettamente collegato alla parte "ultimi 60 secondi". Suggerisco un altro approccio, che varia in base all'intervallo di tempo utilizzando la variabile "n" (n = numero di secondi dell'intervallo di tempo per recuperare i dati consolidati delle transazioni). Questo approccio utilizza l'elaborazione parallela:

n = 60  
repo = hashtable by time or DB with index on the date info

//only executed once, in order to configure the environment
INIT:
  start n listeners for the PUT endpoint, 
  each endpoint is configured with a different offset, ranging from 0 to n-1

//main endpoint listener, offset = 0
PUT(transaction):
  repo[current_time()].calculate_and_append(transaction.data)
  send broadcast with the same request in order that all other listeners process this same transaction

//additional instances, offset can vary from 1 to n-1
PUT(transaction):
  get offset from configuration (env var, process argument, config file, etc)
  repo[current_time() + offset].calculate_and_append(transaction.data)

GET:
  overview_stats = repo[current_time()]
  return overview_stats