Contatore di decremento con alta concorrenza nel sistema distribuito

Question

Contatore di decremento con alta concorrenza nel sistema distribuito

#1 da (3 voti)
#2 da (1 voti)

1

Sto lavorando su un problema in cui una chiamata per ridurre un contatore arriverà a un servizio e se il contatore è maggiore a zero allora la chiamata dovrebbe essere in grado di ridurlo altrimenti fallire.

Piuttosto semplice? eh!

Per una richiesta ottieni il valore del contatore, riduci e rimetti

Bene diventa interessante con i vincoli di seguito:

La richiesta è sandbox: così la richiesta può arrivare a qualsiasi host, ogni richiesta crea un nuovo thread e muore dopo aver restituito la risposta. (Quindi nessun aggiornamento di batch possibile out of the box, in altre parole non è possibile aggiornare il contatore con -10 per conto di 10 richieste se ogni richiesta voleva fare -1)
Massimizza la percentuale di successo delle richieste parallele per lo stesso aggiornamento contatore
Riduci l'impatto sulla latenza dovuto alla soluzione (< 700ms)
Il contatore è archiviato in un archivio dati (diciamo che DynamoDB potrebbe non essere l'archivio dati giusto per accedere alla stessa chiave con una frequenza elevata in quanto provoca una partizione calda e aumentare il throughput solo per supportare questo strano modello di chiamata non è accettabile)

Qual è il problema esattamente, chiedi?

L'accesso allo stesso record molte volte tende a creare uno scenario di partizionamento a caldo in cui la maggior parte dei sottostanti data store inizia a rallentare quando il tipo di richiesta / modello di accesso sembra un tipo di attacco. (non suggerire di mantenere un throughput elevato per supportare il pattern, non è accettabile!)
Elaborazione diretta di una richiesta utilizzata per funzionare quando non vi è alcuna contesa o per non dire che molte richieste parallele aggiornano lo stesso contatore. Ora la maggior parte delle richieste (99%) non riusciranno a causa di casi di errore di blocco / condizionali e i tentativi richiederanno molto tempo a tutti loro per avere successo. (Sto bene alcune richieste falliscono ~ 10%)

Informazioni sui guasti: "errore dovuto al contatore che raggiunge 0" non è riprovabile mentre "errore dovuto a blocco / casi di errore condizionale" è riprovabile.

L'obiettivo è massimizzare il più possibile il tasso di successo della richiesta parallela.

Nota a margine:

Non sono limitato o limitato con particolare modello di dati o negozio. Ciò significa che puoi elaborare qualsiasi modello di dati che ti aiuti a risolvere il problema in modo efficiente e a scegliere qualsiasi archivio dati che ritieni sia giusto per tale caso d'uso.

Ho una soluzione abbastanza buona (usando casualità) di cui posso parlare in seguito. (Non metterlo in primo piano per mantenere il problema aperto e interessante da risolvere piuttosto che discutere una singola soluzione)

Volevo raccogliere pensieri qui, come ti avvicinerai!

concurrency parallelism distributed-system

posta gitesh.tyagi 18.01.2017 - 12:52

fonte

2 risposte

Leggi altre domande sui tag concurrency parallelism distributed-system

Il mio file system implementato utilizzando il pattern Composite richiede un singleton? Duplicazione di una chiave in una tabella di mappatura invece di unirsi

score 3 · Answer 1

Una soluzione facile sarebbe quella di dividere il contatore in N "bucket" diversi, ciascuno contenente un numero X / N (arrotondamento) dove X è il valore iniziale del contatore.

Ogni thread quindi sceglierà un bucket casuale e ne ridurrà il valore. Se il valore del bucket è già 0, il thread può provare ad accedere al bucket successivo e ripetere. In questo caso non stai scrivendo nulla, quindi ti costa solo una nuova operazione di lettura finché non trovi un bucket valido.

Questo ridurrebbe il tasso di collisione fino a 1 / N della situazione originale. L'overhead effettivo dipenderà dal numero di bucket e dai tempi di accesso, quindi è impossibile giudicare in base a un limite di tempo specifico come 700ms. Se questo diventa un problema reale (di cui dubito strongmente), è possibile estendere la soluzione aggiungendo un lavoro pianificato per ridistribuire i valori nei bucket (sommare tutti i bucket e distribuire nuovamente il risultato, in modo da ridurre la possibilità di avere un bucket contenere il valore 0, che comporterebbe la necessità di una nuova lettura).

La parte migliore del corso è che non devi configurare nuovi elementi architettonici (ad esempio il processore di coda) a parte una logica più complessa nel contatore e pochi record invece di uno solo.

score 1 · Answer 2

Dove esiste una fonte di record di verità su un valore di dati come un contatore, e questo valore è universale per tutti i processi in esecuzione e volatile poiché molti processi possono eseguire operazioni che modificano il valore di detto valore, allora sarà necessario tipo di record o blocco della transazione sul campo. Solo un processo può modificare il valore del contatore in una volta. Questo è certo.

Non entrerò nei dettagli su come bloccare un record di tabella. La sfida diventa quindi la questione di come gestiamo al meglio il giusto ed equo accesso al contatore del decremento da parte di tutti i processi concorrenti, e come possiamo farlo in un modo efficiente che minimizzi i fallimenti delle chiamate. Dopotutto, non vorremmo che 10 processi concorrenti ricevessero costantemente un valore mentre altri 20 processi più latenti ricevessero per lo più errori.

La prima cosa che farei sarebbe garantire che ottenere il valore del contatore e il decremento del valore esista come un'unica transazione completa. Se sono due chiamate separate, il valore ricevuto potrebbe non essere aggiornato al momento in cui l'operazione di decremento viene invocata.

In secondo luogo, il modo più giusto ed equo di distribuire l'accesso all'IMO è tramite un'interfaccia Coda messaggi asincrona. Le richieste di decremento e recupero del valore del contatore si accodano e possono essere elaborate una alla volta mantenendo l'ordine in cui sono state inviate le richieste. I client MQ che inviano i messaggi riceveranno la risposta appropriata in modo asincrono su una coda di risposta tramite l'ID di correzione. I client dell'interfaccia possono attendere un periodo di timeout designato prima di decidere di non riuscire.

I problemi con l'approccio di cui sopra sono che la capacità di elaborare i messaggi deve essere mediamente più veloce del tempo di picco medio della richiesta per evitare timeout. Altrimenti, si potrebbero verificare grandi volumi di richieste alla fine della coda, che scadono e falliscono prima che abbiano la possibilità di essere elaborate.