New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Offer returns false occasionally when space should exist #21

Closed
benjchristensen opened this Issue Jul 25, 2014 · 6 comments

Comments

Projects
None yet
2 participants
@benjchristensen

benjchristensen commented Jul 25, 2014

I have a use case where I'm using the queue size as a specific limit and relying on the offer rejection as a boundary. I found that it seems there are times when offer rejects even though there should be space available.

A unit test that demonstrates this behavior is here: https://github.com/benjchristensen/JCTools/blob/offer/jctools-core/src/test/java/org/jctools/queues/SpmcArrayQueueTest.java#L54

This test does the following

  • 1 thread offering values from Producer.request
  • 2 threads draining from the queue
  • as each of the draining threads pulls items from queue.poll it calls Producer.request which schedules onto the same producing thread offering more items via queue.offer
  • occasionally the offer rejects

I can't see anything wrong with the code that would cause more values to be offered than items polled.

This unit test works if I replace the SpmcArrayQueue with a synchronized LinkedList or ArrayBlockingQueue.

@nitsanw

This comment has been minimized.

Show comment
Hide comment
@nitsanw

nitsanw Jul 25, 2014

Contributor

@benjchristensen I'm aware of this issue and debating the right course of action. Currently I am favouring a weaker Queue interface where offer may return false if the next slot is not available and poll may return null if the next slot is empty. Confusingly this is not the same as the queue being full/empty.
When there are multiple consumers the CAS on the consumer index is done before reading the value and nulling it in the array. It is therefore possible for another consumer to progress ahead of another consumer that has not yet nulled the consumed slot. This creates a 'bubble' in the queue where the next slot observed by the producer may not be null even though the queue is not full.
The 'fix' to this issue will be for the producer to check the consumer index to verify if the queue is indeed full and if that is not the case spin until the next slot is available to write into. I'm not keen on this approach but would like to hear your view on the weakened guarantee.
Does this make the queue unfit for purpose? would you be able to use queues with this weaker guarantee?

Contributor

nitsanw commented Jul 25, 2014

@benjchristensen I'm aware of this issue and debating the right course of action. Currently I am favouring a weaker Queue interface where offer may return false if the next slot is not available and poll may return null if the next slot is empty. Confusingly this is not the same as the queue being full/empty.
When there are multiple consumers the CAS on the consumer index is done before reading the value and nulling it in the array. It is therefore possible for another consumer to progress ahead of another consumer that has not yet nulled the consumed slot. This creates a 'bubble' in the queue where the next slot observed by the producer may not be null even though the queue is not full.
The 'fix' to this issue will be for the producer to check the consumer index to verify if the queue is indeed full and if that is not the case spin until the next slot is available to write into. I'm not keen on this approach but would like to hear your view on the weakened guarantee.
Does this make the queue unfit for purpose? would you be able to use queues with this weaker guarantee?

@benjchristensen

This comment has been minimized.

Show comment
Hide comment
@benjchristensen

benjchristensen Jul 28, 2014

Thank you for jumping on this so quickly @nitsanw.

I think there are use cases where the weak version can work, but in some I'm not sure how to make it behave deterministically without causing other problems. I have use cases where I rely on the accuracy of offer/poll so that threads can be released, as I don't have threads dedicated to offering/polling. This means spinning is somewhat difficult to implement as I won't know if it is spinning due to "weak guarantees" or spinning because it's actually empty/full (because both just return null) and that would leave me with a bad choice – spin until it succeeds (possibly never) or spin until some arbitrary count (accepting either latency and/or an eventual non-deterministic failure).

For example, I may have n threads offering to a queue and then one of those will "win" the fight for draining the queue. The handoff from thread-to-thread in stealing the ability to drain is important, otherwise the whole system can just stop without anyone doing any work. If a value is in the queue, but the threads think the queue is empty, they'll stop draining and wait for a notification to start again, but they may never receive a notification if the value is the last to ever be offered.

In my use case this would likely mean I stop relying on offer/poll and put my own volatile counter in front and rely on it instead to handle my thread coordination – but I believe that defeats the point of the performance optimization in a weak implementation of offer/poll.

I also think that an implementation of the java.util.Queue interface needs to be a "drop in" replacement, as the interface is generally interpreted to come with a semantic contract, not just the method signatures (impls for single-threaded, mpmc, mpsc, mpsc each suggesting strong guarantees when used in those contexts). Thus, I'd suggest making the offer and poll methods retain the strong guarantee, but if the weak options are wanted, then have alternatives like weakOffer and weakPoll, similar to how lazySet and set exist.

benjchristensen commented Jul 28, 2014

Thank you for jumping on this so quickly @nitsanw.

I think there are use cases where the weak version can work, but in some I'm not sure how to make it behave deterministically without causing other problems. I have use cases where I rely on the accuracy of offer/poll so that threads can be released, as I don't have threads dedicated to offering/polling. This means spinning is somewhat difficult to implement as I won't know if it is spinning due to "weak guarantees" or spinning because it's actually empty/full (because both just return null) and that would leave me with a bad choice – spin until it succeeds (possibly never) or spin until some arbitrary count (accepting either latency and/or an eventual non-deterministic failure).

For example, I may have n threads offering to a queue and then one of those will "win" the fight for draining the queue. The handoff from thread-to-thread in stealing the ability to drain is important, otherwise the whole system can just stop without anyone doing any work. If a value is in the queue, but the threads think the queue is empty, they'll stop draining and wait for a notification to start again, but they may never receive a notification if the value is the last to ever be offered.

In my use case this would likely mean I stop relying on offer/poll and put my own volatile counter in front and rely on it instead to handle my thread coordination – but I believe that defeats the point of the performance optimization in a weak implementation of offer/poll.

I also think that an implementation of the java.util.Queue interface needs to be a "drop in" replacement, as the interface is generally interpreted to come with a semantic contract, not just the method signatures (impls for single-threaded, mpmc, mpsc, mpsc each suggesting strong guarantees when used in those contexts). Thus, I'd suggest making the offer and poll methods retain the strong guarantee, but if the weak options are wanted, then have alternatives like weakOffer and weakPoll, similar to how lazySet and set exist.

benjchristensen added a commit to benjchristensen/RxJava that referenced this issue Jul 28, 2014

Restore use of SpmcArrayQueue in RxRingBuffer
- Modification of SpmcArrayQueue with fix from JCTools/JCTools#21
- Restore RxRingBuffer to use SpmcArrayQueue
- this reduces object allocation significantly (see pull request for screenshots)
@nitsanw

This comment has been minimized.

Show comment
Hide comment
@nitsanw

nitsanw Jul 31, 2014

Contributor

@benjchristensen internal debate over this issue continues... I agree with your sentiment, but a bit heart broken that the Queue interface which is a single threaded mindset kind of interface is forced upon this concurrent data structure.
Can you illustrate your exact use case for me? having a volatile counter is not required, at worse you'll have to check isEmpty() after you get a null from offer().

Contributor

nitsanw commented Jul 31, 2014

@benjchristensen internal debate over this issue continues... I agree with your sentiment, but a bit heart broken that the Queue interface which is a single threaded mindset kind of interface is forced upon this concurrent data structure.
Can you illustrate your exact use case for me? having a volatile counter is not required, at worse you'll have to check isEmpty() after you get a null from offer().

@nitsanw

This comment has been minimized.

Show comment
Hide comment
@nitsanw

nitsanw Sep 4, 2014

Contributor

I have submitted to sense. More relaxed semantics will be pursued via a new interface in the future.

Contributor

nitsanw commented Sep 4, 2014

I have submitted to sense. More relaxed semantics will be pursued via a new interface in the future.

@nitsanw nitsanw closed this Sep 4, 2014

@benjchristensen

This comment has been minimized.

Show comment
Hide comment
@benjchristensen

benjchristensen commented Sep 4, 2014

Thanks @nitsanw

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment