Algoritmo per limitare la velocità di elaborazione degli articoli

2

Ho bisogno di elaborare un gran numero di elementi di dati, e ho bisogno di limitare la velocità con cui vengono elaborati. Ad esempio, non più di 20 articoli al minuto.

Ho pensato ad un algoritmo per questo, dove terrei una lista con il tempo in cui ogni articolo passato è stato elaborato, quindi posso sapere quanti più posso elaborare in un dato momento.

Tuttavia, questo non è molto elegante poiché ho bisogno di gestire questo elenco. Mi chiedo, c'è qualche algoritmo noto che gestisce questo problema?

Modifica

Per rispondere ai commenti: l'elaborazione dovrebbe essere il più veloce possibile. E sono intervalli di 1 minuto, non importa quando iniziano. Trasmetterò dati a un server, quindi l'obiettivo non è sovraccaricare quel server. Tuttavia, più velocemente l'elaborazione può essere eseguita, meglio è.

    
posta this.lau_ 22.03.2017 - 10:40
fonte

5 risposte

3

I will be sending data to a server, so the goal is not to overload that server.

Quindi lascia che quel server restituisca un segnale quando è pronto per ottenere più dati.

Se c'è un messaggio di errore con cui risponde quando sovraccaricato, puoi eseguire una regolazione dinamica. Si inviano pacchetti completi al server fino a quando non si verifica un errore, quindi si attende x time (e si riduce il calcolo non consentendo il calcolo di più elementi fino a quando la coda di invio non è piena) e si prova a inviare nuovamente il pacchetto e continuare a inviare pacchetti completati.

Questo ha il vantaggio che se si aggiorna il server ricevente non è necessario regolare la manopola (codificata).

    
risposta data 22.03.2017 - 12:45
fonte
2

Supponiamo che ogni attività (attività di elaborazione correlata all'elemento dei dati) termini in una coda sul server. Per ottenere i 20 lavori al minuto in modo semplice, è possibile impostare un'attività ricorrente, che ogni minuto preleva al massimo 20 elementi dalla coda di input e li inserisce in una coda di elaborazione, che viene quindi elaborata da 1 o più filettature.

Il modo in cui lo fai dipende dal tuo ecosistema e dall'ambiente di programmazione. In F #, ad esempio, potresti usare MailboxProcessor<> da FSharp.Control namespace per creare uno stile di soluzione per attore, facendo proprio questo. In C #, è possibile utilizzare il modello Task. Su Pony (sì, questo è anche un linguaggio di programmazione;)), potresti usare gli attori (come tutto ciò che fai lì, è usare gli attori). In ambienti C / C ++ piuttosto bassi, è possibile allocare un piccolo pool di thread (1.una frazione del numero dei core del server), che quindi estraggono le loro attività dalla coda di elaborazione (furto del lavoro). E così via.

Questo produce ancora picchi di carico sul tuo server, poiché ogni minuto funzionerà in modo aggressivo sulle attività di elaborazione degli elementi programmati.

Se si desidera ottenere un carico di fondo più bilanciato entro il lasso di tempo di 1 minuto, è necessario prendere in considerazione ulteriori dettagli sul codice di elaborazione. Se, ad esempio, il tempo di elaborare 1 elemento è piuttosto costante e non molto variabile nella complessità di elaborazione, è possibile eseguire una stima dinamica del tempo di elaborazione per 1 elemento e quindi tracciare i 20 elementi dalla coda di input, solo per pianificare una frazione di essi ogni 60/20 = 3 secondi (alcune attività precedenti potrebbero ancora essere in esecuzione, dato che il server ha anche altre cose da fare e il suo carico di lavoro non è costante). Quanti da pianificare è quindi l'obiettivo dello stimatore.

L'ultimo problema rimasto di cui preoccuparsi è la contropressione. Se si limita strongmente la velocità di elaborazione degli articoli, ma l'afflusso di nuove attività è fuori dal controllo di questi server, la coda di input aumenterà senza limiti. Quindi, piuttosto, proverei a limitare l'elaborazione più o meno, a seconda della lunghezza della coda di input. Oppure aggiungi una reale contropressione alla comunicazione client / server. Ad esempio, chiedi al tuo server di richiedere 20 articoli ogni minuto (in un batch) invece di mandare il client al server come preferisci.

A meno che non si tratti di una sorta di progetto di ricerca o ci siano altre ragioni interessanti, non prenderei in considerazione l'idea di diventare troppo sofisticato su questo problema. Mantenerlo semplice approccio ti fa risparmiare tempo, linee di codice (e in quanto tale, potenziali bug) e in casi estremi l'aspetto divertente dei tuoi colleghi (se sei andato fuori bordo con la tua soluzione).

Se in realtà si programma il lato client (e non il lato server come ho supposto sopra) e se il codice del server ha fatto cattive scelte di vita (nessuna contropressione nel protocollo), si può ancora fare ciò che ho descritto sopra per ottenere il vostro strozzamento. Quello che ho chiamato la coda di input sopra sarebbe ora la tua coda di uscita. E il tuo compito, che è pianificato una volta al minuto, ora richiama al massimo 20 elementi dalla coda di output e li invia come batch al server.

    
risposta data 22.03.2017 - 12:20
fonte
0

Dato che vuoi iniziare l'elaborazione non appena il vincolo temporale ti consente (invece di iniziare l'elaborazione in burst di 20 voci e di attendere un minuto intermedio), potresti usare due code, una piccola coda di blocco e una coda più grande di elementi di attesa.

La coda piccola è una coda di blocco che conserva un registro rotante degli ultimi venti elementi estratti dalla coda con data / ora. Ogni volta che un elemento viene estratto dalla parte anteriore della coda, il timestamp corrente viene aggiunto al registro e la voce meno recente rimossa. L'inserimento di nuovi elementi nella coda è bloccato fino a quando la voce meno recente nel registro è almeno 60 anni nel passato. Il server di elaborazione prende un elemento da questa coda quando possibile.

La coda più grande accetta molti input (coda illimitata se alla fine vuoi processare ogni input, ma potresti anche impostare una capacità massima o negare l'aggiunta di nuovi elementi in base al tempo di attesa atteso o qualcosa del genere). Un processo di trasferimento prende elementi dalla coda di attesa, lo inserisce nella coda piccola o nei blocchi finché non è possibile farlo (che in base alla progettazione della coda piccola garantisce il vincolo temporale).

Vantaggio dell'utilizzo di due code: è possibile scalare il back-end utilizzando più server di elaborazione, ciascuno con il proprio vincolo temporale, la propria coda piccola e il proprio lavoro di trasferimento. La coda più grande davanti funge da bilanciamento del carico.

    
risposta data 22.03.2017 - 12:54
fonte
0

Mantieni la semplicità

Non dovresti aver bisogno di code o strutture dati aggiuntive oltre a quelle che hai già escogitato per gestire la coda di elementi e la logica per elaborarli. Basta incollare un'istruzione Sleep (o il suo equivalente nella tua lingua) da qualche parte nel tuo ciclo principale e renderla configurabile.

A meno che non ci sia qualche NFR che mi manca, non c'è motivo di renderlo più complicato di così.

La mia risposta sarebbe diversa se si facessero volumi elevati, necessari esattamente 20 articoli in esattamente un minuto o se il sistema richiedesse un livello di disponibilità molto alto. Altrimenti, Keep It Simple Stupid .

    
risposta data 22.03.2017 - 13:10
fonte
0

La freaket freaks è probabilmente l'opzione migliore, ma per aggiungere qualche dettaglio in più ..

Se l'obiettivo è di essere gentile con il server o con gli altri client, il server può dirti meglio quando è sotto stress. Ma il primo passo nel sostegno dovrebbe semplicemente essere la prioritizzazione del lavoro e l'accodamento. Se il server sa che il tuo lavoro non è così sensibile alla latenza come altri lavori, in genere non dovrebbe importare la frequenza con cui invii i lavori; saranno sottoposti a una priorità (ritardata) se necessario.

Nel peggiore dei casi, il server può effettivamente emettere un HTTP 429 (troppe richieste).

Tutto ciò detto, se questo non è fattibile per voi dal lato server, la soluzione lato client più semplice e scalabile sarebbe quella di inserire un piccolo ritardo tra ogni richiesta. Idealmente, utilizza un ritardo proporzionale al tempo di elaborazione della richiesta e "quanto è bello" che stai cercando di essere per il server ... Potrebbe non comportare 20 lavori al minuto, ma saprai per certo che sei lasciando il server da solo almeno il P% delle volte.

P è semplicemente un numero puoi scegliere e utilizzare per ritardare le richieste in funzione del tempo di richiesta più recente. (O come media mobile o altro).

    
risposta data 22.03.2017 - 13:50
fonte

Leggi altre domande sui tag