Concurrent Queue - LCRQ - Diuven's Blog

Intro

Concurrent queue is used in locks, databases, load balancers / task schedulers, transaction logging, HFT, network packet processing It is not easy to coordinate the dozens of threads enq/deq ing all at once, while keeping a good throughput. As of last year, LCRQ is known to be the best performing algorithm.

Let’s see how it works.

Original LCRQ Paper

Baseline & Simple approaches

Reminder & notations

For queue, we need to support enqueue(x), dequeue() -> x. In the array-based queue, enq will increment the tail, and deq will increment the head by one. CAS, FAA, linearizability(correctness) Cell

First of all, we can think of using the concurrent linked list from the previous blog post [], and just maintain additional tail & head pointer with CAS.

This would be extremely slow – everyone would be trying to write to tail/head, and fail in most cases.
Also, note that head/tail and the value cells are impossible to write at once. We should somehow figure out a way to be okay with some mismatches between the cells and the head & tail.

If we had infinite amount of memory, we could do this:

Head , Tail : Long  // 64-bit counters
A: E[]  // Infinite array for elements of type E

fun Enqueue (item : E) = while ( true ) {
    t := Tail.FAA(1)
    if (A[t].CAS(null, item)) return
}

fun Dequeue (): E = while ( true ) {
    if (Head >= Tail) return null  // empty ?
    h := Head.FAA(1)
    if (A[h] == null && A[h].CAS(null, ⊥)) continue
    return A[h]
}

This may seem a bit too excessive, but every parts are essential to guarantee the correctness. Few things to observe and think about:

Each operation takes a ‘ticket’, and is ‘assigned’ one corresponding cell to work on. Either it succeeds there, or fail and restart the whole operation. There can only be one Enqueue and one Dequeue assigned to a single cell.
The array A is infinite, and each cell’s lifetime will look like null -> <item> or null -> ⊥. Once the queue ‘passes through’ the cell, it will never be accessed again.
- Also, because of the first point, there is only one (Enq) thread which can do null -> <item> and one (Deq) thread which can do null -> ⊥.
The empty check in Deq is not atomic. i.e. the version we read for Head and Tail will be different.
- However, since both Head and Tail only increases, if we read Head, and then read Tail, and it was Head >= Tail, we can say for sure that there was a time that the queue was actually empty.
- ($Head_{t_1} >= Head_{t_0}$, and $Head_{t_0} >= Tail_{t_1}$, then $Head_{t_1} >= Tail_{t_1}$)
- Which means, failed Deq will linearize on the read of Tail.
Head might ‘overtake’ the Tail, if we’re unlucky. If the empty check in Deq passes by small margin for 50 threads, and they all do Head.FAA(1), then Head will be larger than Tail.
Because of that, Deq should handle the case where it sees the null instead of the expected <item>. How? It simply marks the cell ⊥, and retry.
- Note that there can be only one Deq operation will work on this cell, so no need to worry about double write, ABA, etc.
- For Enq which was assigned here, it will simply fail to CAS, and move on.
- This means, conceptually, this cell is now ‘skipped’; it is not used, and never gonna be used. This can be seen as a ‘hole’ in the infinite array.
- This may be caused because of either Enq was slow to CAS, or lots of Deq go past the Head.
This means all operations are never blocked – even if some Enq threads are frozen, Deq threads just mark cells as dead and move on.
- However, the cycle count may be unbounded (i.e. livelock). If a Deq, Enq pair work in order of Enq.FAA, Deq.FAA, Deq.CAS, Enq.CAS, ..., then they will never terminate.
In ‘most’, ‘typical’ cases, both Enq and Deq will success CAS, and return right away.
Even though we have distributed threads to different cells, all threads are still updating Head and Tail value, with FAA.

Concurrent Ring Queue

Ok. But we don’t have infinite array. How to make this reasonable? Similar to the sequential case, we will use a ring buffer to ‘simulate’ the infinite array, based on the above algorithm. But unlike in the sequential case, we need more jargons to ensure the correctness.

Overview on how it works:

We will only have one finite buffer, but we will keep Head and Tail indices as if we have infinite array. i.e. values of Head and Tail will grow without wrapping around, but threads will access cell with index = ticket % capacity, and epoch = ticket / capacity.
- This means, unlike the infinite case, there may be multiple Enq/Deq threads accessing the same cell. However, it still holds that there can be only one Enq and Deq thread with the same ticket number (i.e. index, epoch pair).
When the buffer is full, Enq will fail and we’ll consider queue as Closed.
To simulate the infinite array, we will put the epoch in each cell, so that threads can decide whether the current cell is actually mine, or someone else’s.
- A cell will have two words (8B * 2), one for the item, one for the epoch. From the buffer index and the epoch, we know where this cell represents in the (conceptual) infinite array.
- Consecutive cells in the buffer may not represent the consecutive cells in the consecutive infinite array. Some cells may have lagging epochs due to lagging threads.
Enqueue, Dequeue transition: If the cell was mine (i.e. my ticket index == conceptual cell index), then the logic is same as before. Enq tries to CAS cell as item, Deq tries to read, or CAS cell as empty.
- Successful Deq will move this cell forward, so that later Enq thread can use this cell for their work. (i.e. increment epoch by one)
If it wasn’t, then I’m looking either behind or ahead.
- In case of behind (my ticket index > conceptual cell index):
  - For Enq, I can use the cell only if it is empty. If it isn’t, it probably mean the queue is full. Check that and retry.
  - Empty transition: For Deq, I can update the epoch of the empty cell, for the same reason of null -> ⊥ (make a hole and move on) case above.
  - Unsafe transition: If the cell isn’t empty for Deq, then it means that Deq operation which should have emptied this cell is not done yet, but I have already overtaken it.
    - I will skip, but my matching (same ticket index) Enq operation might write in this cell if it arrives after the cell became empty. This is a problem, since there will never be a Deq thread to collect it.
    - To avoid this, I mark this cell with a ‘unsafe’ bit, so that Enq threads can skip if that’s the case. (i.e. Enq will write to this thread, only if it certainly knows that its matching Deq hasn’t started yet. Otherwise, it will skip.)
    - This ‘safe’ bit is saved inside the epoch word.
- In case of ahead (my ticket index < conceptual cell index), it means I was sleeping so long so that other threads came around the buffer after the full epoch. I’m too outdated, so I’ll just retry.

If we increase the ring buffer size, the complex (and slow) cases will almost never happen. So we have all the security measures for correctness, but in performance perspective, most threads will simply get the ticket, read/write the cell once and terminate.

Note that the closing condition may not hold throughout the whole closing operation, but such state must have existed during the operation, as mentioned in the infinite queue.

Even though we have spread the threads to its corresponding cell, cells may be located in the same cache line and cause false sharing and performance degradation. To avoid this, authors have implemented with optimized memory pattern; for 64B cache line and 8B word, they placed the cells like {0, n, 2n, .. 7n}, {1, n+1, 2n+1, .. 7n+1}, …, so that neighboring cells are placed in the different cache line.

The linearization point is last FAA for successful Enq and Deq (also, Enq should always linearize before Deq). For failed (closed or empty) operations, linearization point is straightforward.

LCRQ

Now, we have the linearizable ring queue (CRQ). To implement the full queue, we should support the multiple CRQ to handle infinite number of operations.

LCRQ simply manages the linked list of CRQs with CAS. When the queue grows and needs the another CRQ, it appends the new CRQ to the tail. Since it is swapped with CAS, there can only be one chain of CRQs. Also, note that even if the new CRQ is appended late (i.e. multiple operations have already worked on the existing CRQ and it now have empty slots), the subsequent operations will work on the new tail CRQ. (i.e. the non-tail CRQs may have empty slots) We can see that the linearization point is the successful CAS for such operations. Similar applies to the Dequeue operations.

Note that the closed queue never reopens. Since real-world implementations use efficient reclamation methods to recycle such memory spaces of objects, both space and time overhead is minimal.

Limitations, Future works

Although LCRQ uses two FAA objects to mitigate contention on one CAS pointer, is still is bottlenecked by those two objects on high contention; all threads sequentializes on two object for FAA. This can be mitigated by faster FAA as shown in Aggregating Funnels paper.

Also, this original LCRQ uses a double-width CAS to manage both epoch and value in the queue cell. dw-CAS is not as widely supported as the single CAS, and may require extra work and setup. To avoid this, LPRQ paper provides a tweak on this algorithm to use only standard single-width CAS.

References

(LCRQ) Fast Concurrent Queues for x86 Processors https://dl.acm.org/doi/10.1145/2442516.2442527

(LPRQ) The State-of-the-Art LCRQ Concurrent Queue Algorithm Does NOT Require CAS2 https://dl.acm.org/doi/10.1145/3572848.3577485

(YMC Queue) A wait-free queue as fast as fetch-and-add https://dl.acm.org/doi/abs/10.1145/2851141.2851168

(Aggregating Funnels) Aggregating Funnels for Faster Fetch&Add and Queues https://dl.acm.org/doi/10.1145/3710848.3710873