Coalescing queues

[isaiah perumalla]

use case: have a producer sending lots market data events that trigger some revaluation/processing . The consumer is just interested in the latest event, we want some way for the producer to update events on the queue with the latest data if it has not been consumed yet. each event has a key associated to it (e.g. instrument name, or currency pair e.g. EURUSD)

solution 1:

initially had a custom data structure which was a combination of 1P1C queue, and a custom open addressed hash table. basic idea was

the producer  would check hash table if the key exists, if it did exist the value for the associated key was updated (this involves a CAS operation if CAS failed it meant consumer had consumed the entry already ). if the key does not exist  it was added to the hashtable and put the key on to the queue. consumer would take keys from the queue and look up the values for associated key from the hash table, once consumed the entry in hashtable was set to null (also a CAS operation if CAS failed it meant the producer updated the value, and consume would have to retry ) .

was not satisfied with the above approach as there is a CAS operation for each poll operation even for single producer single consumer . 

solution 2:

I has a look at the coalescing ring buffer ( https://nickzeeb.wordpress.com/2013/03/07/the-coalescing-ring-buffer/ ) this looks interesting  but not sure if its any better than solution 3 below

solution 3:

simple 1P1C queue, let consumer do a batch take and do the coalescing on the consumer thread before processing the events , this to me seems like the simplest and cleanest approach.

are there any other ways to solve this problem 

thanks

isaiah

[Greg Young]

"initially had a custom data structure which was a combination of 1P1C
queue, and a custom open addressed hash table. basic idea was
the producer would check hash table if the key exists, if it did
exist the value for the associated key was updated (this involves a
CAS operation if CAS failed it meant consumer had consumed the entry
already ). if the key does not exist it was added to the hashtable
and put the key on to the queue."

If 1p1c why do you need a CAS?

> --
> You received this message because you are subscribed to the Google Groups
> "mechanical-sympathy" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to mechanical-symp...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.



--
Studying for the Turing test

[isaiah perumalla]

CAS is needed as producer and consumer could be updating the same hashtable entry at the same time. 

without CAS the consumer could miss some updates.

Example

Lets say there is  "EURUSD" already on the queue with value A in hashtable 

1) producer has an update B for EURUSD, it sees  the key is already present in the table with value A . 

2) consumer takes the value for EURUSD -> A before producer has updated it with new value B

3) producer has updated the value to B, but this update is never seen by the consumer 

> email to mechanical-sympathy+unsub...@googlegroups.com.

[Greg Young]

Why are producer and consumer sharing state?

On Mon, Jul 6, 2015 at 12:21 AM, isaiah perumalla

>> > email to mechanical-symp...@googlegroups.com.

>> > For more options, visit https://groups.google.com/d/optout.
>>
>>
>>
>> --
>> Studying for the Turing test
>

> --
> You received this message because you are subscribed to the Google Groups
> "mechanical-sympathy" group.
> To unsubscribe from this group and stop receiving emails from it, send an

> email to mechanical-symp...@googlegroups.com.

[Michael Barker]

The advantage of the coalescing ring buffer over a straight 1p1c with consumer coalescing is that if the consumer is so slow that the buffer fills up it is still possible for the producer to push updates as it will scan for the appropriate entry in the unconsumed portion of the ring buffer.  This will of course depend on the total number of coalescing keys (e.g. symbols) that are in use and the total size of the ring buffer.  If the latter is larger than the former there is a good chance that the producer will always be able to make progress without losing updates.   With a 1p1c, when the buffer fills updates will be lost.  The coalescing works really well if you have a few really busy instruments.  This is often the case in most trading systems.  Our major crosses see a lot more traffic than the minor ones.

Mike.

[isaiah perumalla]

For solution 1: Interested to know how this can be done with out sharing state