Lock free pub/sub queue
Original Publication Date: 2009-Jul-29
Included in the Prior Art Database: 2009-Jul-29
This article describes a concurrency algorithm allowing use of a publish/subscribing queue in such a way that subscription & unsubscription will not block the delivery or queuing of messages to/from other subscribers.
Lock free pub/sub queue
There is a general need for high throughput publish/subscribe mechanisms, e.g. WebSphere* Broker however even the lightweight brokers are heavyweight and unsuited to being embedded into a process internally publishing messages in the hundreds of thousands per second range.
A publish/subscribe queue, i.e. each message is processed by every subscriber, where publishing and consumption of messages are performed without locks meaning that actions performed on the queue such as subscribing, un-subscribing and publishing of new messages do not block or slow the rate at which existing subscribers can process messages.
Subscriptions to the queue are able to operate independently of one another, allowing subscribers to process messages as fast as they are individually able irrespective of the rate of consumption of other subscribers.
The queue consists of a linked list of messages, consumed from the tail and published to the head, and a record of the current number of subscribers. Each message has a count of the number of subscribers expected to process it, initialized to the number of subscribers on the queue at the time the message is published (iC). That per message count is the exact number of subscribers that will process that message. Once a subscriber has processed a message, that message's count is decremented and once the count equals zero that message is eligible to be deleted.
The current per message count (C) for any two messages, A and B, must meet the following invariant where A is closer to the head (newer) and B is closer to tail (older):
A.C >= B.C
Using a simple numeric count for tracking lifecycles of messages allows atomic modification of state, removing the need for a heavy lock. The stated method of determining when a message can be discarded means that every subscriber must process all messages that it is expected to do so, once and only once. The crux of the problem then is how to determine the first message on the queue that is expected to be processed by a new subscription irrespective of the interleaving of publishing, updates to message counts and queue count. Subscriptions and de-subscriptions are not performed concurrently.
Subscription follows this process:
1. increment the queue subscription count
2. determine the first message (X) queued using the incremented subscription count
If a subscription doesn't specify a starting message then an assumption can
be made that it starts with message X, otherwise:
3. if the subscription specifies a message to start at (Y) then increment C for Y through X, excluding X
Step 2 of the subscription process, i.e. determination of the first message queued using the incremented subscription count for a new subscription can be done as follows:
Step 2 details
Set up some management values:...