Its core logic is simple: The elements are stored in a priority queue, sorted based on their scheduled time (earliest to expire is at head of the queue). During poll/take operations, the head element can be returned only if/when it’s scheduled time has expired.
Though, this can potentially mean multiple threads synchronizing on the head element causing overhead.
This is resolved using Leader-Follower pattern which is improvement on Half-Sync/Half-Async pattern.
This makes the DelayedQueue implementation quite fascinating.
The source code for DelayQueue can be found here. Leader-Follower paper can be found here
Suppose there is an scheduled task at the head of the queue with timeout of 5 seconds. All the threads wanting
to take/poll the element have to sleep (aka timed-wait) for 5 seconds. Once 5 seconds are over and element
is eligible to be taken out of the queue, all threads will vie for same element.
Instead, one thread is chosen as leader at the beginning, and only that threads awaits 5 seconds.
All other threads will wait on a condition. Once 5 seconds are over, the leader will take the element,
and signal the condition so that someone else can become the leader and get the next element in the queue.
Leader awaits for the head element to expire
All other threads await on a condition
Leader takes the element after expiry & signals the condition
One of the other threads becomes the new leader
The above algorithm should become clearer as we walk-through the source code below.
DelayedQueue stores instances of Delayed instances.
Add / Offer
Get the element at head of the queue if expired else return null.
Get the element at head of the queue if expired else block until expiry.
Get element at head of the queue if expired else wait for given duration or element’s expiry whichever is shorter.
We skipped few methods, but even then this is one of the shorter source codes we’ve seen so far. I was initially
lost as to why we needed a leader and a condition. Going through the paper helped.
Hit me in the up in the comments for any queries or concerns.