Lock-Free in Java: Scenario 09 - K-FIFO Queues and the Art of Relaxed Ordering

Part 1: The Midnight Revelation

Midnight, Tuesday. The system was running smoothly, processing a torrent of real-time event data. Then, out of nowhere, the dreaded 'Out of Memory' error appears. And then silence. The system goes down.

I've been in this industry long enough to know that feeling - that sinking sensation when you realize something fundamental is broken. We'd spent countless hours fine-tuning our Java code, optimizing every possible line. Our load balancer was distributing work across 16 worker threads, each pulling tasks from a central queue. The architecture was textbook-correct. Yet here we were, watching the system crumble under what should have been manageable load.

The post-mortem revealed a familiar villain: Garbage Collection. But not in the way I expected. Our GC logs showed frequent stop-the-world pauses, each one lasting 40-80 milliseconds. In a system designed to process 100,000 events per second while serving 500 queries per second, these pauses were catastrophic. Each pause meant thousands of events backing up, queues filling, memory pressure increasing, and eventually - the dreaded OOM.

But here's what made this problem interesting: our system didn't actually need strict ordering. We were running a load balancer. Task scheduling. Event aggregation. In all these cases, we only needed "approximately correct" ordering - not perfect FIFO semantics. An event processed slightly out of order wasn't a bug; it was perfectly acceptable.

That realization was the breakthrough. We'd been paying a massive performance tax for ordering guarantees we didn't need. Enter the K-FIFO Queue.

Part 2: Understanding the FIFO Tax

Before diving into the solution, let's understand why strict FIFO ordering is so expensive. This isn't just academic theory - it directly explains why our system was failing.

The Serialization Problem

A strict FIFO queue makes a fundamental promise: elements will be dequeued in exactly the order they were enqueued. This sounds simple, but think about what it implies for concurrent access.

If Producer A enqueues element 1, and Producer B enqueues element 2, and element 1 was enqueued "first," then element 1 must be dequeued before element 2. But what does "first" mean in a concurrent system? To establish this ordering, we need some form of serialization - a single point where the order is established.

Loading diagram...

This serialization is the bottleneck. Every producer must acquire the same lock, establishing a total order. Under contention, this creates lock convoys, context switches, and - crucially for our story - allocation pressure from the synchronization infrastructure.

The True Cost of Perfect Ordering

Let me quantify what we were observing. Our ArrayBlockingQueue-based implementation showed:

Performance Characteristics:

Single lock protecting all operations
Average operation latency: 300-500 nanoseconds
Throughput ceiling: approximately 2 million operations per second
p99 latency: 15 milliseconds (when GC kicked in)

But the hidden cost was worse. Under contention, the JVM's ReentrantLock was allocating wait queue nodes. At 50,000 operations per second with 16 producer threads, we were generating nearly 3 MB/second of synchronization-related allocations. These small objects promoted to old gen, triggering mixed GC cycles that caused the devastating pauses.

Here's what our naive implementation looked like:

View source

public class StrictFIFOQueue<T> {
 
    private final Object[] buffer;
    private final int capacity;
    private final ReentrantLock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();
 
    private int head = 0;
    private int tail = 0;
    private int count = 0;
 
    public StrictFIFOQueue(int capacity) {
        this.capacity = capacity;
        this.buffer = new Object[capacity];
    }
 
    public void enqueue(T element) throws InterruptedException {
        lock.lock();
        try {
            while (count == capacity) {
                notFull.await();  // Allocates under contention!
            }
            buffer[tail] = element;
            tail = (tail + 1) % capacity;
            count++;
            notEmpty.signal();
        } finally {
            lock.unlock();
        }
    }
 
    @SuppressWarnings("unchecked")
    public T dequeue() throws InterruptedException {
        lock.lock();
        try {
            while (count == 0) {
                notEmpty.await();
            }
            T element = (T) buffer[head];
            buffer[head] = null;
            head = (head + 1) % capacity;
            count--;
            notFull.signal();
            return element;
        } finally {
            lock.unlock();
        }
    }
}

The code looks clean. It's correct. It's textbook. And it was killing our system.

The Insight: Approximate Ordering Is Often Enough

The breakthrough came when I asked a simple question: What would actually break if we relaxed the ordering guarantee?

In our load balancer:

Tasks would still get processed
Every task would eventually complete
The only difference: task A might complete before task B even if B was submitted first

For our use case, this was completely acceptable. In fact, it's what most load balancers do anyway - they route to the first available worker, not the worker that will process in submission order.

The same logic applies broadly. In task scheduling, workers grab available work and the scheduler doesn't guarantee execution order. Event aggregation computes statistics over streams where order within short windows doesn't matter. Logging pipelines might deliver entries slightly out of order, but timestamps provide the true ordering. And metrics collection involves sampling and aggregating where exact ordering is irrelevant.

This insight led me to the K-FIFO queue.

Part 3: K-FIFO Queues - The Theory

A K-FIFO queue provides a weaker but still useful ordering guarantee: when you dequeue an element, it will be among the K oldest elements in the queue. Not necessarily THE oldest, but within the oldest K.

Loading diagram...

Why K-FIFO Enables Parallelism

The magic of K-FIFO is that it allows us to break the serialization bottleneck. Instead of one queue, we maintain K independent segments. Each segment is essentially a single-producer, single-consumer (SPSC) queue - the simplest and fastest concurrent data structure possible.

Loading diagram...

Producers are assigned to segments (via thread ID hashing or round-robin). Each producer only writes to its assigned segment - no contention with other producers. The consumer round-robins through segments, pulling from whichever has data.

The K Guarantee

Why is this still "approximately FIFO"? Consider the worst case: an element E is enqueued to segment 0, and then K-1 elements are enqueued to segments 1 through K-1. The consumer checks segment 1 first, finds an element, and returns it before E.

But the consumer will check segment 0 within the next K dequeue operations (since there are only K segments). So E will be returned within K operations of when it "should" have been returned. Hence the K-FIFO guarantee.

Theoretical Bounds

The K-FIFO relaxation provides remarkable performance improvements:

Metric	Strict FIFO	K-FIFO (K=segments)
Producer contention	All producers compete	Zero (per-segment ownership)
Lock overhead	One lock per operation	Zero locks (lock-free possible)
Memory barriers	Full fence per operation	Minimal (release/acquire pairs)
Cache behavior	Severe bouncing	Per-segment locality

The theoretical throughput scales linearly with K, up to the point where other bottlenecks (memory bandwidth, consumer processing) become limiting.

Part 4: Designing the K-FIFO Queue

Let's design our K-FIFO queue from first principles. The key insight is that we're trading ordering for parallelism - and we need to make that trade explicit in our design.

Architecture Overview

Loading diagram...

Segment Design: The Building Block

Each segment is an SPSC queue. This is critical - SPSC queues are the simplest lock-free structure because:

Only one thread writes (producer) - no write contention
Only one thread reads (consumer) - no read contention
Only need memory ordering between the one writer and one reader

/**
 * Single-Producer Single-Consumer (SPSC) queue segment.
 *
 * Thread-safety:
 * - offer() must only be called by the owning producer thread
 * - poll() must only be called by the single consumer thread
 * - These methods can be called concurrently (producer vs consumer)
 */
public class Segment<T> {
 
    // VarHandle for atomic operations
    private static final VarHandle HEAD;
    private static final VarHandle TAIL;
 
    static {
        try {
            MethodHandles.Lookup lookup = MethodHandles.lookup();
            HEAD = lookup.findVarHandle(Segment.class, "head", long.class);
            TAIL = lookup.findVarHandle(Segment.class, "tail", long.class);
        } catch (ReflectiveOperationException e) {
            throw new ExceptionInInitializerError(e);
        }
    }
 
    // Cache line padding to prevent false sharing
    @SuppressWarnings("unused")
    private long p01, p02, p03, p04, p05, p06, p07;
 
    /** Next position for producer to write. Only modified by producer. */
    private volatile long tail = 0;
 
    @SuppressWarnings("unused")
    private long p11, p12, p13, p14, p15, p16, p17;
 
    /** Next position for consumer to read. Only modified by consumer. */
    private volatile long head = 0;
 
    @SuppressWarnings("unused")
    private long p21, p22, p23, p24, p25, p26, p27;
 
    private final Object[] buffer;
    private final int capacity;
    private final int mask;
 
    public Segment(int capacity) {
        // Round up to power of 2 for fast modulo
        this.capacity = Integer.highestOneBit(capacity - 1) << 1;
        this.mask = this.capacity - 1;
        this.buffer = new Object[this.capacity];
    }
 
    /**
     * Adds an element to this segment.
     *
     * @param element The element to add
     * @return true if successful, false if segment is full
     */
    public boolean offer(T element) {
        long currentTail = tail;
        long currentHead = (long) HEAD.getAcquire(this);
 
        // Check if full
        if (currentTail - currentHead >= capacity) {
            return false;
        }
 
        // Write the element
        int index = (int) (currentTail & mask);
        buffer[index] = element;
 
        // Publish with release semantics
        // This ensures the buffer write is visible before tail advances
        TAIL.setRelease(this, currentTail + 1);
 
        return true;
    }
 
    /**
     * Removes and returns an element from this segment.
     *
     * @return The element, or null if segment is empty
     */
    @SuppressWarnings("unchecked")
    public T poll() {
        long currentHead = head;
        long currentTail = (long) TAIL.getAcquire(this);
 
        // Check if empty
        if (currentHead >= currentTail) {
            return null;
        }
 
        // Read the element
        int index = (int) (currentHead & mask);
        T element = (T) buffer[index];
        buffer[index] = null;  // Help GC
 
        // Advance head with release semantics
        HEAD.setRelease(this, currentHead + 1);
 
        return element;
    }
 
    public boolean isEmpty() {
        return head >= tail;
    }
 
    public int size() {
        long currentTail = tail;
        long currentHead = head;
        long size = currentTail - currentHead;
        return (int) Math.max(0, Math.min(size, capacity));
    }
}

The K-FIFO Queue: Orchestrating Segments

Now we build the K-FIFO queue on top of our segments:

View source

/**
 * K-FIFO Queue: A concurrent queue with relaxed ordering guarantees.
 *
 * This queue guarantees that any dequeued element was among the K oldest
 * elements in the queue at some point during the dequeue operation,
 * where K is the number of segments.
 *
 * Performance characteristics:
 * - Producer: ~50-100ns per offer (no contention between producers)
 * - Consumer: ~50-100ns per poll
 * - Throughput: 6-10M ops/sec with multiple producers
 *
 * @param <T> Element type
 */
public class KFIFOQueue<T> {
 
    private final Segment<T>[] segments;
    private final int segmentCount;
    private final int segmentMask;
 
    // For round-robin producer assignment
    private final AtomicInteger producerIndex = new AtomicInteger(0);
 
    // For round-robin consumer polling
    private int consumerIndex = 0;
 
    // Thread-local segment assignment for producers
    private final ThreadLocal<Integer> threadSegment = ThreadLocal.withInitial(() -> {
        // Assign each producer thread to a segment
        return producerIndex.getAndIncrement() & segmentMask;
    });
 
    /**
     * Creates a K-FIFO queue with the specified number of segments.
     *
     * @param segmentCount Number of segments (K value). Should be >= number of producer threads.
     *                     Will be rounded up to power of 2.
     * @param segmentCapacity Capacity of each segment.
     */
    @SuppressWarnings("unchecked")
    public KFIFOQueue(int segmentCount, int segmentCapacity) {
        // Round up to power of 2 for fast modulo
        this.segmentCount = Integer.highestOneBit(segmentCount - 1) << 1;
        this.segmentMask = this.segmentCount - 1;
 
        this.segments = new Segment[this.segmentCount];
        for (int i = 0; i < this.segmentCount; i++) {
            this.segments[i] = new Segment<>(segmentCapacity);
        }
    }
 
    /**
     * Adds an element to the queue.
     *
     * This method is thread-safe and can be called by multiple producer threads
     * concurrently. Each producer is assigned to its own segment, eliminating
     * contention between producers.
     *
     * @param element The element to add
     * @return true if successful, false if the assigned segment is full
     */
    public boolean offer(T element) {
        if (element == null) {
            throw new NullPointerException("Null elements not permitted");
        }
 
        int segmentIndex = threadSegment.get();
        return segments[segmentIndex].offer(element);
    }
 
    /**
     * Removes and returns an element from the queue.
     *
     * This method must only be called by a single consumer thread.
     * It checks segments in round-robin order, providing the K-FIFO guarantee.
     *
     * @return An element, or null if the queue is empty
     */
    public T poll() {
        // Check each segment starting from current position
        for (int i = 0; i < segmentCount; i++) {
            int index = (consumerIndex + i) & segmentMask;
            T element = segments[index].poll();
 
            if (element != null) {
                // Advance starting position for next poll
                consumerIndex = (index + 1) & segmentMask;
                return element;
            }
        }
 
        // All segments empty
        return null;
    }
 
    /**
     * Drains available elements into the provided consumer.
     * More efficient than repeated poll() calls.
     *
     * @param consumer Function to process each element
     * @return Number of elements drained
     */
    public int drain(java.util.function.Consumer<T> consumer) {
        int total = 0;
 
        // Drain each segment in turn
        for (int round = 0; round < segmentCount; round++) {
            for (int i = 0; i < segmentCount; i++) {
                int index = (consumerIndex + i) & segmentMask;
                T element;
 
                while ((element = segments[index].poll()) != null) {
                    consumer.accept(element);
                    total++;
                }
            }
        }
 
        return total;
    }
 
    /**
     * Returns approximate total size across all segments.
     */
    public int size() {
        int total = 0;
        for (Segment<T> segment : segments) {
            total += segment.size();
        }
        return total;
    }
 
    /**
     * Returns true if all segments appear empty.
     */
    public boolean isEmpty() {
        for (Segment<T> segment : segments) {
            if (!segment.isEmpty()) {
                return false;
            }
        }
        return true;
    }
 
    /**
     * Returns the K value (number of segments).
     */
    public int getK() {
        return segmentCount;
    }
}

Notice the cache line padding in the Segment class. This is crucial for performance. Let me explain why.

Modern CPUs transfer data in cache lines, typically 64 bytes on x86-64. When one core modifies a byte in a cache line, the entire line is invalidated in all other cores' caches. This is called "false sharing" when unrelated data happens to share a cache line.

In our Segment class:

tail is written by the producer, read by the consumer
head is written by the consumer, read by the producer

If these fields were on the same cache line, every write would invalidate the other thread's cache, causing expensive memory traffic. The padding ensures each field gets its own cache line:

Bytes 0-55:   Padding (p01-p07)
Bytes 56-63:  tail field
Bytes 64-119: Padding (p11-p17)
Bytes 120-127: head field
Bytes 128-183: Padding (p21-p27)

This simple optimization can improve throughput by 2-3x under contention.

Part 5: Deep Dive - Memory Ordering and Correctness

Lock-free programming is notoriously tricky. Let's prove our implementation is correct by analyzing the memory ordering.

The Producer's View

When a producer calls offer():

public boolean offer(T element) {
    long currentTail = tail;                              // [1] Read tail
    long currentHead = (long) HEAD.getAcquire(this);     // [2] Acquire-read head
 
    if (currentTail - currentHead >= capacity) {
        return false;                                     // [3] Full check
    }
 
    int index = (int) (currentTail & mask);
    buffer[index] = element;                             // [4] Write element
 
    TAIL.setRelease(this, currentTail + 1);             // [5] Release-write tail
 
    return true;
}

The key orderings enforce correctness. [4] before [5]: the release-write at [5] ensures the buffer write at [4] is visible to any thread that observes the new tail value — this is the "publication," because we don't advance tail until the element is written. [2] reads head with acquire semantics to ensure we see the consumer's latest head update and any buffer nullification it performed.

The Consumer's View

When the consumer calls poll():

public T poll() {
    long currentHead = head;                             // [1] Read head
    long currentTail = (long) TAIL.getAcquire(this);    // [2] Acquire-read tail
 
    if (currentHead >= currentTail) {
        return null;                                     // [3] Empty check
    }
 
    int index = (int) (currentHead & mask);
    T element = (T) buffer[index];                       // [4] Read element
    buffer[index] = null;                                // [5] Clear slot
 
    HEAD.setRelease(this, currentHead + 1);             // [6] Release-write head
 
    return element;
}

The key orderings mirror the producer's guarantees. [2] acquires tail, pairing with the producer's release-write — if we see tail = N, we're guaranteed to see all buffer writes for positions < N. [4] after [2]: the acquire semantics establish a happens-before relationship, ensuring we see the element the producer wrote. Finally, [5] and [6] after [4] ensures we read the element before clearing the slot and advancing head, preventing use-after-free scenarios.

Proving the K-FIFO Property

Let's prove the queue maintains the K-FIFO property. Consider any element E added to segment S at time T1.

Claim: E will be dequeued within K dequeue operations after it becomes the oldest element in the queue.

Proof:

At some time T2 >= T1, E becomes the oldest element (all elements added before T1 have been dequeued).
The consumer checks segments in round-robin order.
Within K consecutive poll() calls, the consumer will check segment S.
When the consumer checks segment S, E is at the head (it's the oldest in that segment, and all older elements globally have been dequeued).
Therefore, E will be dequeued within K operations.

This proof assumes no new elements are added between T1 and when E is dequeued. In practice, new elements may arrive, but the K-FIFO property holds relative to the queue state at any given moment.

The ABA Problem: Why We Don't Have It

Classic lock-free algorithms often struggle with the ABA problem: a value changes from A to B and back to A, making CAS think nothing changed when in fact the state has evolved.

Our design sidesteps this elegantly:

Position-based indexing: We use monotonically increasing positions (head and tail), not pointers.
No CAS on critical path: SPSC queues don't need CAS - only one thread writes each variable.
Long positions: 64-bit positions won't wrap around in realistic scenarios.

This is a significant advantage over more complex MPMC designs.

Part 5B: Understanding VarHandle and Memory Access Modes

Before moving to production concerns, let's take a deeper look at how VarHandle works. Understanding these primitives is essential for writing correct lock-free code.

The VarHandle API

Java 9 introduced VarHandle as a replacement for the older sun.misc.Unsafe operations. VarHandle provides type-safe, well-defined atomic operations with explicit memory ordering semantics.

// Creating VarHandles at class initialization
private static final VarHandle HEAD;
private static final VarHandle TAIL;
private static final VarHandle BUFFER;
 
static {
    try {
        MethodHandles.Lookup lookup = MethodHandles.lookup();
 
        // For instance fields
        HEAD = lookup.findVarHandle(Segment.class, "head", long.class);
        TAIL = lookup.findVarHandle(Segment.class, "tail", long.class);
 
        // For array elements
        BUFFER = MethodHandles.arrayElementVarHandle(Object[].class);
    } catch (ReflectiveOperationException e) {
        throw new ExceptionInInitializerError(e);
    }
}

Memory Access Modes Explained

VarHandle provides five access modes, each with different ordering guarantees:

1. Plain Access

long value = (long) HEAD.get(this);           // Plain read
HEAD.set(this, 42L);                           // Plain write

No ordering guarantees. The compiler and CPU can reorder freely. Only use for data that doesn't need synchronization.

2. Opaque Access

long value = (long) HEAD.getOpaque(this);     // Opaque read
HEAD.setOpaque(this, 42L);                     // Opaque write

Guarantees atomic access and no reordering with other opaque operations on the same variable. But no ordering with operations on other variables.

3. Acquire/Release

long value = (long) HEAD.getAcquire(this);    // Acquire read
HEAD.setRelease(this, 42L);                    // Release write

This is what we use in K-FIFO. Release-write ensures all prior writes are visible. Acquire-read ensures all subsequent reads see those writes. This creates a "synchronizes-with" relationship.

4. Volatile Access

long value = (long) HEAD.getVolatile(this);   // Volatile read
HEAD.setVolatile(this, 42L);                   // Volatile write

Full sequential consistency. All threads see a total order of all volatile operations. Most expensive, but sometimes necessary.

5. Compare-and-Set

boolean success = HEAD.compareAndSet(this, expected, newValue);
long witness = (long) HEAD.compareAndExchange(this, expected, newValue);

Atomic conditional updates. Essential for lock-free algorithms when multiple threads compete to update the same variable.

Why Acquire/Release Is Enough for K-FIFO

In our K-FIFO queue, we don't need full volatile semantics. Here's why:

Loading diagram...

The release-write at the producer ensures all prior buffer writes complete before the tail update is visible. The acquire-read at the consumer ensures it sees those buffer writes after observing the tail update. This is precisely the synchronization we need - no more, no less.

Performance Impact of Memory Ordering

Different access modes have different costs on different architectures:

Architecture	Acquire/Release	Volatile
x86-64	0-1 cycles	20-100 cycles
ARM	5-15 cycles	30-150 cycles
POWER	10-20 cycles	40-200 cycles

On x86-64, acquire/release are nearly free because the architecture has strong memory ordering. On ARM and POWER with weaker memory models, they require explicit fence instructions. Volatile is expensive everywhere because it requires a full memory barrier.

This is why we carefully choose acquire/release over volatile - the performance difference is significant on some architectures.

Common VarHandle Patterns in Lock-Free Code

Pattern: Publication via Release

// Producer writes data, then publishes
data[index] = computeValue();
PUBLISHED.setRelease(this, index);
 
// Consumer observes publication, then reads data
int idx = (int) PUBLISHED.getAcquire(this);
if (idx != UNPUBLISHED) {
    useValue(data[idx]);  // Guaranteed to see computeValue() result
}

Pattern: Double-Checked Initialization

public Object getInstance() {
    Object local = (Object) INSTANCE.getAcquire(this);
    if (local == null) {
        synchronized (this) {
            local = (Object) INSTANCE.getAcquire(this);
            if (local == null) {
                local = createInstance();
                INSTANCE.setRelease(this, local);
            }
        }
    }
    return local;
}

Pattern: Spin-Wait with Acquire

while (true) {
    long seq = (long) SEQUENCE.getAcquire(sequences, index);
    if (seq == expectedSequence) {
        // Condition met, proceed
        break;
    }
    Thread.onSpinWait();  // CPU hint for spin-waiting
}

Part 6: Handling Edge Cases and Production Concerns

A correct algorithm isn't enough for production. Let's address real-world concerns.

Segment Overflow: What Happens When a Segment Is Full?

In our basic implementation, offer() returns false when the assigned segment is full. But this might not be acceptable in all scenarios. Here are strategies:

Strategy 1: Overflow to Other Segments

public boolean offerWithOverflow(T element) {
    int primary = threadSegment.get();
 
    // Try primary segment first
    if (segments[primary].offer(element)) {
        return true;
    }
 
    // Overflow: try other segments
    for (int i = 1; i < segmentCount; i++) {
        int index = (primary + i) & segmentMask;
        if (segments[index].offer(element)) {
            return true;
        }
    }
 
    return false;  // All segments full
}

This weakens the per-segment ownership but maintains the K-FIFO property.

Strategy 2: Dynamic Segment Resizing

public boolean offerWithResize(T element) {
    int segmentIndex = threadSegment.get();
    Segment<T> segment = segments[segmentIndex];
 
    if (segment.offer(element)) {
        return true;
    }
 
    // Segment full - try to resize
    synchronized (this) {
        // Double-check after acquiring lock
        if (segment.offer(element)) {
            return true;
        }
 
        // Create larger segment and migrate
        Segment<T> newSegment = new Segment<>(segment.capacity * 2);
        // ... migration logic
        segments[segmentIndex] = newSegment;
    }
 
    return segments[segmentIndex].offer(element);
}

This is more complex but prevents data loss.

Strategy 3: Blocking with Backpressure

public void put(T element) throws InterruptedException {
    while (!offer(element)) {
        if (Thread.interrupted()) {
            throw new InterruptedException();
        }
        Thread.onSpinWait();
    }
}

Simple, but can lead to unbounded spinning. Consider adding exponential backoff.

Consumer Starvation: Ensuring Fairness Across Segments

Our round-robin consumer prevents starvation, but an unbalanced producer distribution could cause issues. Consider:

// Track segment processing for monitoring
private final long[] segmentPollCounts = new long[segmentCount];
 
public T pollWithMetrics() {
    for (int i = 0; i < segmentCount; i++) {
        int index = (consumerIndex + i) & segmentMask;
        T element = segments[index].poll();
 
        if (element != null) {
            segmentPollCounts[index]++;
            consumerIndex = (index + 1) & segmentMask;
            return element;
        }
    }
    return null;
}
 
// Monitor for imbalance
public double getSegmentImbalance() {
    long min = Long.MAX_VALUE, max = 0;
    for (long count : segmentPollCounts) {
        min = Math.min(min, count);
        max = Math.max(max, count);
    }
    return (double) max / (min + 1);
}

Graceful Shutdown

Concurrent data structures need careful shutdown handling:

private volatile boolean shuttingDown = false;
 
public boolean offer(T element) {
    if (shuttingDown) {
        throw new IllegalStateException("Queue is shutting down");
    }
    // ... rest of implementation
}
 
public void shutdown() {
    shuttingDown = true;
}
 
public List<T> drainRemaining() {
    List<T> remaining = new ArrayList<>();
    T element;
    while ((element = poll()) != null) {
        remaining.add(element);
    }
    return remaining;
}

Memory Leaks: Helping the GC

Notice how we set buffer[index] = null after reading an element. This is critical. Without it, the buffer holds references to consumed elements until those slots are reused, potentially causing memory leaks in long-running systems.

// WRONG: Memory leak potential
T element = (T) buffer[index];
// buffer still references element!
 
// CORRECT: Help GC
T element = (T) buffer[index];
buffer[index] = null;

Part 7: Benchmarks and Real-World Results

Theory is nice, but does it actually perform? Let's measure.

Benchmark Setup

All benchmarks ran on an Intel Xeon E5-2680 v4 (14 cores, 28 threads) with 128GB RAM, using OpenJDK 17.0.2 with G1GC and an 8GB heap, measured with JMH 1.36.

@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 5, time = 2)
@Measurement(iterations = 10, time = 2)
@Fork(3)
@State(Scope.Benchmark)
public class KFIFOBenchmark {
 
    @Param({"4", "8", "16"})
    int producerCount;
 
    @Param({"4", "8", "16"})
    int segmentCount;
 
    private StrictFIFOQueue<Long> strictQueue;
    private KFIFOQueue<Long> kfifoQueue;
 
    @Setup
    public void setup() {
        strictQueue = new StrictFIFOQueue<>(65536);
        kfifoQueue = new KFIFOQueue<>(segmentCount, 65536 / segmentCount);
    }
 
    @Benchmark
    @Group("strict")
    @GroupThreads(4)
    public void strictOffer(Blackhole bh) throws InterruptedException {
        strictQueue.enqueue(System.nanoTime());
    }
 
    @Benchmark
    @Group("strict")
    @GroupThreads(1)
    public void strictPoll(Blackhole bh) throws InterruptedException {
        bh.consume(strictQueue.dequeue());
    }
 
    @Benchmark
    @Group("kfifo")
    @GroupThreads(4)
    public void kfifoOffer(Blackhole bh) {
        kfifoQueue.offer(System.nanoTime());
    }
 
    @Benchmark
    @Group("kfifo")
    @GroupThreads(1)
    public void kfifoPoll(Blackhole bh) {
        bh.consume(kfifoQueue.poll());
    }
}

Throughput Results

Configuration	Strict FIFO	K-FIFO (K=4)	K-FIFO (K=8)	K-FIFO (K=16)
4 producers	2.1M ops/s	6.2M ops/s	7.1M ops/s	7.4M ops/s
8 producers	1.8M ops/s	7.8M ops/s	9.2M ops/s	10.1M ops/s
16 producers	1.4M ops/s	6.1M ops/s	8.9M ops/s	11.3M ops/s

The results are striking. K-FIFO achieves 3-8x higher throughput depending on configuration. While strict FIFO throughput decreases with more producers due to increasing contention, K-FIFO throughput increases with more producers up to K, then saturates — the contention that cripples strict FIFO becomes parallelism that feeds K-FIFO.

Latency Distribution

Strict FIFO (4 producers):

p50:   187 ns
p90:   423 ns
p99:   2,340 ns
p99.9: 15,234 ns

K-FIFO (4 producers, K=4):

p50:   52 ns
p90:   78 ns
p99:   145 ns
p99.9: 412 ns

The tail latencies tell the real story. At p99.9, K-FIFO is 37x better than strict FIFO. Those rare high-latency events in the strict queue? They're the lock convoys and GC pauses we were fighting.

GC Behavior Comparison

We ran a 5-minute sustained load test with 8 producers:

Strict FIFO:

Young GC events: 234
Total GC pause time: 4,120ms
Max pause: 127ms
Allocation rate: 4.2 MB/sec

K-FIFO (K=8):

Young GC events: 18
Total GC pause time: 270ms
Max pause: 21ms
Allocation rate: 0.4 MB/sec

92% reduction in GC pause time. This was the root cause of our midnight production incident, and K-FIFO eliminated it.

Scaling Analysis

Let's examine how performance scales with different configurations:

Loading diagram...

The throughput increases rapidly as K approaches the number of producers, then plateaus. Beyond K = producer count, adding more segments provides diminishing returns - the consumer becomes the bottleneck, not producer contention.

Cache Analysis with perf

Using Linux perf to analyze cache behavior reveals why K-FIFO performs better:

# Run with perf to measure cache events
perf stat -e cache-references,cache-misses,L1-dcache-load-misses,LLC-load-misses \
    java -jar kfifo-benchmark.jar

Strict FIFO results (4 producers):

1,234,567,890  cache-references
  123,456,789  cache-misses              (10.0% of refs)
   89,012,345  L1-dcache-load-misses
   12,345,678  LLC-load-misses

K-FIFO results (4 producers, K=4):

  456,789,012  cache-references          (63% fewer)
   22,345,678  cache-misses              (4.9% of refs)
   15,678,901  L1-dcache-load-misses     (82% fewer)
    2,345,678  LLC-load-misses           (81% fewer)

The dramatic reduction in cache misses explains the latency improvement. When producers don't contend for the same cache lines, they can operate independently at CPU cache speed rather than waiting for cache coherency traffic.

Memory Bandwidth Analysis

We also measured memory bandwidth utilization:

Strict FIFO:

Memory reads: 4.2 GB/s
Memory writes: 2.1 GB/s
Cache invalidation traffic: High

K-FIFO:

Memory reads: 1.8 GB/s
Memory writes: 0.9 GB/s
Cache invalidation traffic: Minimal

The reduced memory bandwidth leaves more headroom for other system operations and improves overall system stability under load.

Visualization: Latency Over Time

Loading diagram...

Part 8: When K-FIFO Is the Right Choice

K-FIFO queues aren't universally better than strict FIFO. Let's clearly delineate when to use each.

Use K-FIFO When:

1. Ordering Is Approximate By Nature

Many systems have inherent ordering ambiguity. Load balancers distribute work to available workers without guaranteeing execution order. Event aggregators compute statistics over streams where micro-ordering doesn't affect results. Logging pipelines rely on timestamps for true ordering, making queue ordering supplementary. Task schedulers implement fair scheduling that doesn't require strict FIFO.

2. High Throughput Trumps Ordering

When you need millions of operations per second and can tolerate approximate ordering:

Real-time data processing
High-frequency trading order routing
Telemetry collection
Stream processing pipelines

3. Multiple Independent Producers

K-FIFO excels when producers are naturally independent:

Per-thread event collectors
Per-connection request handlers
Sharded data processors

4. GC Pressure Is Problematic

If you're seeing GC-related latency spikes:

Low-latency systems
Real-time applications
Systems with tight p99 SLAs

Stick With Strict FIFO When:

1. Ordering Is Semantically Required

Some use cases demand exact ordering. Message queues with ordering guarantees like Kafka partitions and JMS ordered delivery depend on strict sequencing. Event sourcing requires events to replay in exact order, and transactional systems need operations to serialize.

2. Consumers Depend on Order

When downstream processing assumes ordering:

Sequence number validation
Incremental aggregation with ordering assumptions
Replay and recovery scenarios

3. Simplicity Wins

When the performance gain isn't worth the complexity:

Low-throughput systems (< 10K ops/sec)
Systems where correctness trumps performance
Teams without lock-free expertise

4. Single Producer

With only one producer, strict FIFO has no contention overhead. The K-FIFO's complexity isn't justified.

Decision Matrix

Loading diagram...

Real-World Use Case: High-Frequency Trading Order Router

Let me share a detailed example from our production system. Our order router receives orders from multiple trading desks (8 producer threads) and routes them to exchanges based on best execution algorithms.

Original Architecture (Strict FIFO):

public class OrderRouter {
    private final BlockingQueue<Order> orderQueue = new ArrayBlockingQueue<>(10000);
    private final ExecutorService routingExecutor;
 
    public void submitOrder(Order order) throws InterruptedException {
        orderQueue.put(order);  // Blocks if queue is full
    }
 
    public void routeOrders() {
        while (running) {
            Order order = orderQueue.take();  // Blocks if empty
            routeToExchange(order);
        }
    }
}

This worked fine at 10,000 orders/day. When we scaled to 100,000 orders/day with market volatility spikes, we hit problems:

Order submission latency spiked to 50ms during high volume
GC pauses caused missed execution windows
p99 latency made our SLA unachievable

Refactored Architecture (K-FIFO):

public class OrderRouter {
    // K=8 to match 8 trading desk threads
    private final KFIFOQueue<Order> orderQueue = new KFIFOQueue<>(8, 2048);
 
    public boolean submitOrder(Order order) {
        // Non-blocking - return immediately if segment full
        return orderQueue.offer(order);
    }
 
    public void routeOrders() {
        while (running) {
            Order order = orderQueue.poll();
            if (order != null) {
                routeToExchange(order);
            } else {
                Thread.onSpinWait();  // CPU-friendly wait
            }
        }
    }
}

Results:

Order submission latency: 50ms -> 200ns (250x improvement)
GC pauses: eliminated
p99 latency: 45ms -> 800ns
Throughput: 10x higher peak capacity

The key insight: order execution doesn't require strict FIFO. Markets are already non-deterministic - an order submitted 1 microsecond earlier doesn't guarantee earlier execution. What matters is low latency and high throughput, both of which K-FIFO delivers.

Real-World Use Case: Log Aggregation Pipeline

Another production use case: centralizing logs from 200+ microservices.

Requirements:

Handle 500,000 log events/second at peak
Never drop logs in normal operation
Never block application threads
Minimal memory overhead

Architecture:

public class LogAggregator {
    // One segment per service type (web, api, worker, etc.)
    private final KFIFOQueue<LogEvent> logQueue = new KFIFOQueue<>(16, 65536);
 
    // Called by log appender in each service
    public void append(LogEvent event) {
        if (!logQueue.offer(event)) {
            // Segment full - this is rare, track it
            droppedLogCounter.increment();
 
            // Optional: try overflow to other segments
            for (int i = 0; i < 16; i++) {
                if (logQueue.offerWithOverflow(event)) {
                    overflowCounter.increment();
                    return;
                }
            }
        }
    }
 
    // Batch consumer for efficiency
    public void flushToStorage() {
        List<LogEvent> batch = new ArrayList<>(1000);
 
        logQueue.drainTo(batch, 1000);
 
        if (!batch.isEmpty()) {
            storageWriter.writeBatch(batch);
        }
    }
}

Results:

Zero application thread blocking
99.99% log delivery rate
Consistent 50ns append latency
75% reduction in log pipeline memory usage

Real-World Use Case: Metrics Collection

For application performance monitoring, we collect metrics from instrumented code:

public class MetricsCollector {
    private final KFIFOQueue<Metric> metricsQueue = new KFIFOQueue<>(
        Runtime.getRuntime().availableProcessors(),
        8192
    );
 
    // Called from hot paths - must be fast
    public void record(String name, long value) {
        // Pre-allocated metric object pool
        Metric metric = metricPool.acquire();
        metric.set(name, value, System.nanoTime());
 
        if (!metricsQueue.offer(metric)) {
            // Return to pool if couldn't enqueue
            metricPool.release(metric);
            droppedMetrics.increment();
        }
    }
 
    // Background aggregation thread
    public void aggregate() {
        Map<String, LongSummaryStatistics> stats = new HashMap<>();
 
        metricsQueue.drain(metric -> {
            stats.computeIfAbsent(metric.name(), k -> new LongSummaryStatistics())
                 .accept(metric.value());
            metricPool.release(metric);
        });
 
        publishToMonitoring(stats);
    }
}

The combination of K-FIFO queue with object pooling achieves sub-100ns overhead per metric, making fine-grained instrumentation practical without impacting application performance.

Part 9: Advanced Patterns and Optimizations

Let's explore some advanced techniques for getting even more performance from K-FIFO queues.

Pattern 1: Batched Operations

Instead of polling one element at a time, drain in batches:

public int drainTo(Collection<T> collection, int maxElements) {
    int drained = 0;
 
    for (int round = 0; round < 2 && drained < maxElements; round++) {
        for (int i = 0; i < segmentCount && drained < maxElements; i++) {
            int index = (consumerIndex + i) & segmentMask;
            Segment<T> segment = segments[index];
 
            T element;
            while (drained < maxElements && (element = segment.poll()) != null) {
                collection.add(element);
                drained++;
            }
        }
    }
 
    return drained;
}

Batching amortizes the overhead of segment scanning and improves cache utilization.

Pattern 2: Weighted Round-Robin

If some segments receive more traffic, weight the consumer's attention:

private final int[] segmentWeights;
private int currentWeight = 0;
 
public T pollWeighted() {
    int startIndex = consumerIndex;
    int checksRemaining = Arrays.stream(segmentWeights).sum();
 
    while (checksRemaining > 0) {
        int index = consumerIndex;
        int weight = segmentWeights[index];
 
        if (currentWeight < weight) {
            T element = segments[index].poll();
            if (element != null) {
                currentWeight++;
                return element;
            }
        }
 
        currentWeight = 0;
        consumerIndex = (consumerIndex + 1) & segmentMask;
        checksRemaining--;
    }
 
    return null;
}

Pattern 3: Affinity-Aware Segment Assignment

Instead of arbitrary thread-to-segment mapping, use CPU affinity:

private final ThreadLocal<Integer> affinitySegment = ThreadLocal.withInitial(() -> {
    // Map to segment based on CPU core
    // This improves cache locality
    try {
        // Platform-specific: get current CPU
        int cpu = getCurrentCpu();  // JNI or /proc/self/stat parsing
        return cpu & segmentMask;
    } catch (Exception e) {
        return producerIndex.getAndIncrement() & segmentMask;
    }
});

When producer threads have CPU affinity, this keeps related data on the same cache.

Pattern 4: Hybrid Mode for Mixed Workloads

Some systems need both high throughput and occasional strict ordering:

public class HybridQueue<T> {
    private final KFIFOQueue<T> fastPath;
    private final StrictFIFOQueue<T> orderedPath;
 
    public void offer(T element, boolean requireOrdering) {
        if (requireOrdering) {
            orderedPath.enqueue(element);
        } else {
            fastPath.offer(element);
        }
    }
 
    public T poll() {
        // Prioritize ordered path to maintain ordering for those elements
        T element = orderedPath.tryDequeue();
        if (element != null) {
            return element;
        }
        return fastPath.poll();
    }
}

Pattern 5: Statistics and Monitoring

Production systems need observability:

public class MonitoredKFIFOQueue<T> extends KFIFOQueue<T> {
 
    private final LongAdder offerSuccess = new LongAdder();
    private final LongAdder offerFailure = new LongAdder();
    private final LongAdder pollSuccess = new LongAdder();
    private final LongAdder pollEmpty = new LongAdder();
    private final Histogram latencyHistogram = new Histogram();
 
    @Override
    public boolean offer(T element) {
        long start = System.nanoTime();
        boolean result = super.offer(element);
        long duration = System.nanoTime() - start;
 
        latencyHistogram.record(duration);
 
        if (result) {
            offerSuccess.increment();
        } else {
            offerFailure.increment();
        }
 
        return result;
    }
 
    @Override
    public T poll() {
        T result = super.poll();
 
        if (result != null) {
            pollSuccess.increment();
        } else {
            pollEmpty.increment();
        }
 
        return result;
    }
 
    public QueueStats getStats() {
        return new QueueStats(
            offerSuccess.sum(),
            offerFailure.sum(),
            pollSuccess.sum(),
            pollEmpty.sum(),
            latencyHistogram.getSnapshot()
        );
    }
}

Part 10: Production Deployment Checklist

Before deploying K-FIFO queues in production, walk through this checklist.

Configuration

Segment count >= producer threads: Each producer should ideally have its own segment
Segment capacity sized for burst: Plan for 2-3x expected peak burst
Power-of-2 sizing: Both segment count and capacity should be powers of 2
JVM tuned for low latency: Consider -XX:+UseZGC or -XX:+UseShenandoahGC

Monitoring

Segment utilization metrics: Track how full each segment gets
Throughput counters: Ops/sec for offer and poll
Latency histograms: p50, p90, p99, p99.9 for both operations
GC metrics: Pause frequency, duration, allocation rate

Testing

Stress test with production load: Verify behavior under expected peak
Failure injection: What happens when segments overflow?
Long-running tests: Check for memory leaks over hours/days
Thread variation tests: Verify behavior with different producer counts

Operational

Graceful shutdown procedure: How do you drain the queue?
Backpressure strategy: What happens when producers outpace consumers?
Alerting thresholds: When should ops be notified?
Runbook entries: Document common issues and resolutions

Part 11: Comparison with Alternatives

K-FIFO isn't the only approach to high-performance concurrent queues. Let's compare.

vs. LMAX Disruptor

The Disruptor uses a similar ring buffer approach but with different trade-offs:

Aspect	K-FIFO	Disruptor
Learning curve	Moderate	Steep
Configuration	Simple	Complex
Batching	Manual	Built-in
Wait strategies	Basic	Multiple options
Dependencies	None	Library
Use case	General	Event processing

Choose Disruptor when: You need sophisticated event processing with multiple consumers, batching, and complex wait strategies.

Choose K-FIFO when: You need a simpler drop-in replacement for standard queues with better performance.

vs. JCTools Queues

JCTools provides battle-tested lock-free queues:

// JCTools MPSC queue
MpscArrayQueue<Event> queue = new MpscArrayQueue<>(1024);
queue.offer(event);
Event e = queue.poll();

Aspect	K-FIFO	JCTools MPSC
Ordering	K-FIFO	Strict FIFO
Producer contention	None	Low (CAS-based)
Maturity	Custom	Production-proven
Flexibility	High	Fixed

Choose JCTools when: You need strict FIFO with proven production reliability.

Choose K-FIFO when: You can trade ordering for even higher throughput.

vs. LinkedTransferQueue

Java's built-in option for high-performance queuing:

LinkedTransferQueue<Event> queue = new LinkedTransferQueue<>();
queue.offer(event);
Event e = queue.poll();

Aspect	K-FIFO	LinkedTransferQueue
Bounded	Yes	No
Memory	Fixed	Growing
GC pressure	Minimal	Moderate
Throughput	Very high	High

Choose LinkedTransferQueue when: You need unbounded queues with good general-purpose performance.

Choose K-FIFO when: Bounded size, minimal GC, and maximum throughput are priorities.

Part 12: Conclusion and Lessons Learned

That midnight incident taught me something I won't forget: the data structures we choose have profound implications beyond correctness. Our perfectly correct ArrayBlockingQueue was killing our system. The ordering guarantee we thought we needed was actually a performance anchor dragging us down.

The K-FIFO queue isn't magic. It's a trade-off made explicit. By relaxing the ordering guarantee from "exactly FIFO" to "among the K oldest," we gained a 3-5x throughput improvement (from 2M to 6-10M ops/sec), 37x better tail latency (p99.9 dropped from 15ms to 400ns), and a 92% reduction in GC pressure (from 4.2 MB/sec allocations to 0.4 MB/sec).

But more than the numbers, I learned a deeper lesson about systems design: question your assumptions. We assumed strict ordering. We assumed the standard library was optimal. We assumed the problem was elsewhere. Each assumption was wrong.

The real skill in performance engineering isn't knowing exotic algorithms. It's asking the right questions:

What guarantees do we actually need?
What are we paying for guarantees we don't use?
Where is the real bottleneck?

The K-FIFO queue answered our immediate problem. But the methodology - measure, understand, question, optimize - applies everywhere.

So the next time you reach for a BlockingQueue, pause for a moment. Ask yourself: Do I really need strict FIFO? Or am I paying a tax I don't need to pay? The answer might surprise you.

And remember: measure, understand, optimize - in that order.

Part 13: Debugging and Troubleshooting K-FIFO Queues

Lock-free code is notoriously difficult to debug. When things go wrong, they often go wrong in subtle, hard-to-reproduce ways. Here's a comprehensive guide to debugging K-FIFO implementations.

Common Symptoms and Their Causes

Symptom: Data Corruption (Reading Wrong Values)

Possible causes:

Missing memory barriers - element read before producer finishes writing
Index calculation errors - reading from wrong slot
ABA problem - slot reused before read completes

Debugging approach:

// Add validation to poll()
public T poll() {
    long currentHead = head;
    long currentTail = (long) TAIL.getAcquire(this);
 
    if (currentHead >= currentTail) {
        return null;
    }
 
    int index = (int) (currentHead & mask);
    T element = (T) buffer[index];
 
    // Debug: Validate element isn't the sentinel value
    if (element == POISONED_SENTINEL) {
        throw new IllegalStateException(
            "Read poisoned slot at index=" + index +
            " head=" + currentHead + " tail=" + currentTail
        );
    }
 
    buffer[index] = POISONED_SENTINEL;  // Mark slot as consumed for debugging
    HEAD.setRelease(this, currentHead + 1);
 
    return element;
}

Symptom: Lost Elements (Elements Enqueued But Never Dequeued)

Possible causes:

Producer thinks segment is full when it isn't
Consumer skips segments
Head/tail wraparound issues

Debugging approach:

// Add element tracking
private final ConcurrentHashMap<T, Long> enqueueTimestamps = new ConcurrentHashMap<>();
private final ConcurrentHashMap<T, Long> dequeueTimestamps = new ConcurrentHashMap<>();
 
public boolean offer(T element) {
    boolean result = segments[threadSegment.get()].offer(element);
    if (result) {
        enqueueTimestamps.put(element, System.nanoTime());
    }
    return result;
}
 
public T poll() {
    T element = /* ... actual poll logic ... */;
    if (element != null) {
        Long enqueueTime = enqueueTimestamps.remove(element);
        if (enqueueTime == null) {
            throw new IllegalStateException("Dequeued element that was never enqueued: " + element);
        }
        dequeueTimestamps.put(element, System.nanoTime());
    }
    return element;
}
 
// Periodic health check
public void validateNoLostElements(long maxAgeNanos) {
    long now = System.nanoTime();
    for (Map.Entry<T, Long> entry : enqueueTimestamps.entrySet()) {
        if (now - entry.getValue() > maxAgeNanos) {
            System.err.println("WARNING: Element stuck in queue: " + entry.getKey() +
                " age=" + (now - entry.getValue()) / 1_000_000 + "ms");
        }
    }
}

Symptom: Deadlock or Livelock

K-FIFO is lock-free by design, so true deadlock shouldn't occur. But you might see:

Consumer spinning forever on empty segments
Producers spinning forever on full segments
Thread starvation from unfair scheduling

Debugging approach:

// Add spin counters
public T poll() {
    int spinCount = 0;
    int emptySegmentCount = 0;
 
    for (int i = 0; i < segmentCount; i++) {
        int index = (consumerIndex + i) & segmentMask;
        T element = segments[index].poll();
 
        if (element != null) {
            if (spinCount > 1000) {
                System.err.println("WARNING: Consumer spun " + spinCount +
                    " times, checked " + emptySegmentCount + " empty segments");
            }
            consumerIndex = (index + 1) & segmentMask;
            return element;
        }
 
        emptySegmentCount++;
        spinCount++;
    }
 
    return null;
}

Using Thread Dumps for Diagnosis

When K-FIFO behaves unexpectedly, thread dumps reveal where threads are spending time:

# Get thread dump
jcmd <pid> Thread.print
 
# Or using jstack
jstack <pid>

Look for patterns like:

Multiple producer threads in the same method - indicates contention
Consumer thread in Thread.onSpinWait() - normal when queue is empty
Producer threads blocked outside queue code - upstream issue

Testing Strategies for Lock-Free Code

Strategy 1: Stress Testing

@Test
void stressTestKFIFO() throws InterruptedException {
    KFIFOQueue<Long> queue = new KFIFOQueue<>(8, 4096);
    AtomicLong produced = new AtomicLong(0);
    AtomicLong consumed = new AtomicLong(0);
    AtomicBoolean running = new AtomicBoolean(true);
    List<Throwable> errors = Collections.synchronizedList(new ArrayList<>());
 
    // Start 8 producer threads
    List<Thread> producers = new ArrayList<>();
    for (int p = 0; p < 8; p++) {
        Thread t = new Thread(() -> {
            try {
                while (running.get()) {
                    long value = produced.incrementAndGet();
                    while (!queue.offer(value) && running.get()) {
                        Thread.onSpinWait();
                    }
                }
            } catch (Throwable e) {
                errors.add(e);
            }
        });
        t.start();
        producers.add(t);
    }
 
    // Start consumer thread
    Thread consumer = new Thread(() -> {
        try {
            while (running.get() || !queue.isEmpty()) {
                Long value = queue.poll();
                if (value != null) {
                    consumed.incrementAndGet();
                }
            }
        } catch (Throwable e) {
            errors.add(e);
        }
    });
    consumer.start();
 
    // Run for 30 seconds
    Thread.sleep(30_000);
    running.set(false);
 
    // Wait for completion
    for (Thread t : producers) t.join(5000);
    consumer.join(5000);
 
    // Drain remaining
    while (queue.poll() != null) consumed.incrementAndGet();
 
    // Verify
    assertTrue(errors.isEmpty(), "Errors occurred: " + errors);
    assertEquals(produced.get(), consumed.get(),
        "Lost elements: produced=" + produced.get() + " consumed=" + consumed.get());
}

Strategy 2: Jcstress Testing

For rigorous concurrency testing, use OpenJDK's jcstress:

@JCStressTest
@State
@Outcome(id = "1, 1", expect = ACCEPTABLE, desc = "Both saw each other's writes")
@Outcome(id = "0, 0", expect = ACCEPTABLE, desc = "Neither saw each other's writes")
@Outcome(id = "1, 0", expect = ACCEPTABLE, desc = "Observer saw producer's write")
@Outcome(id = "0, 1", expect = FORBIDDEN, desc = "Impossible: consumer read before write")
public class KFIFOCorrectnessTest {
 
    private final Segment<Integer> segment = new Segment<>(16);
 
    @Actor
    public void producer(II_Result r) {
        segment.offer(42);
        r.r1 = 1;
    }
 
    @Actor
    public void consumer(II_Result r) {
        Integer value = segment.poll();
        r.r2 = (value != null && value == 42) ? 1 : 0;
    }
}

Strategy 3: Property-Based Testing

Use property-based testing to find edge cases:

@Property
void kfifoMaintainsKFIFOProperty(
    @ForAll @Size(min = 1, max = 100) List<Integer> elements,
    @ForAll @IntRange(min = 2, max = 16) int k
) {
    KFIFOQueue<Integer> queue = new KFIFOQueue<>(k, 128);
 
    // Enqueue all elements
    for (int e : elements) {
        assertTrue(queue.offer(e));
    }
 
    // Dequeue and verify K-FIFO property
    Set<Integer> remaining = new HashSet<>(elements);
    List<Integer> dequeued = new ArrayList<>();
 
    while (!queue.isEmpty()) {
        Integer e = queue.poll();
        assertNotNull(e);
        assertTrue(remaining.remove(e), "Duplicate element: " + e);
        dequeued.add(e);
    }
 
    assertEquals(elements.size(), dequeued.size());
    // Note: Can't verify strict K-FIFO without tracking enqueue order per segment
}

Profiling Lock-Free Code

Use async-profiler for low-overhead profiling:

# Profile CPU usage
./profiler.sh -e cpu -d 30 -f profile.html <pid>
 
# Profile lock contention (even for lock-free, shows CAS retries)
./profiler.sh -e lock -d 30 -f locks.html <pid>
 
# Profile cache misses
./profiler.sh -e cache-misses -d 30 -f cache.html <pid>

Performance Regression Detection

Set up continuous benchmarking to catch regressions:

@Benchmark
@BenchmarkMode(Mode.SampleTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public void kfifoOfferPoll(Blackhole bh, BenchmarkState state) {
    state.queue.offer(System.nanoTime());
    bh.consume(state.queue.poll());
}
 
// In CI pipeline:
// 1. Run benchmark
// 2. Compare against baseline
// 3. Fail if p99 latency regresses by > 10%

Appendix A: Complete Implementation

For reference, here's the complete K-FIFO queue implementation:

package com.techishthoughts.lockfree;
 
import java.lang.invoke.MethodHandles;
import java.lang.invoke.VarHandle;
import java.util.concurrent.atomic.AtomicInteger;
 
/**
 * K-FIFO Queue: A concurrent queue with relaxed ordering guarantees.
 *
 * This queue guarantees that any dequeued element was among the K oldest
 * elements in the queue at some point during the dequeue operation,
 * where K is the number of segments.
 *
 * Thread safety:
 * - offer() is safe for concurrent calls from multiple producer threads
 * - poll() must only be called from a single consumer thread
 *
 * Performance characteristics:
 * - Producer: ~50-100ns per offer (no inter-producer contention)
 * - Consumer: ~50-100ns per poll
 * - Throughput: 6-10M ops/sec with multiple producers
 *
 * @param <T> Element type stored in the queue
 */
public class KFIFOQueue<T> {
 
    /**
     * SPSC (Single-Producer Single-Consumer) segment.
     */
    public static class Segment<T> {
 
        private static final VarHandle HEAD;
        private static final VarHandle TAIL;
 
        static {
            try {
                MethodHandles.Lookup lookup = MethodHandles.lookup();
                HEAD = lookup.findVarHandle(Segment.class, "head", long.class);
                TAIL = lookup.findVarHandle(Segment.class, "tail", long.class);
            } catch (ReflectiveOperationException e) {
                throw new ExceptionInInitializerError(e);
            }
        }
 
        // Cache line padding
        @SuppressWarnings("unused")
        private long p01, p02, p03, p04, p05, p06, p07;
 
        private volatile long tail = 0;
 
        @SuppressWarnings("unused")
        private long p11, p12, p13, p14, p15, p16, p17;
 
        private volatile long head = 0;
 
        @SuppressWarnings("unused")
        private long p21, p22, p23, p24, p25, p26, p27;
 
        private final Object[] buffer;
        private final int capacity;
        private final int mask;
 
        public Segment(int capacity) {
            this.capacity = Integer.highestOneBit(capacity - 1) << 1;
            this.mask = this.capacity - 1;
            this.buffer = new Object[this.capacity];
        }
 
        public boolean offer(T element) {
            long currentTail = tail;
            long currentHead = (long) HEAD.getAcquire(this);
 
            if (currentTail - currentHead >= capacity) {
                return false;
            }
 
            int index = (int) (currentTail & mask);
            buffer[index] = element;
            TAIL.setRelease(this, currentTail + 1);
 
            return true;
        }
 
        @SuppressWarnings("unchecked")
        public T poll() {
            long currentHead = head;
            long currentTail = (long) TAIL.getAcquire(this);
 
            if (currentHead >= currentTail) {
                return null;
            }
 
            int index = (int) (currentHead & mask);
            T element = (T) buffer[index];
            buffer[index] = null;
            HEAD.setRelease(this, currentHead + 1);
 
            return element;
        }
 
        public boolean isEmpty() {
            return head >= tail;
        }
 
        public int size() {
            long size = tail - head;
            return (int) Math.max(0, Math.min(size, capacity));
        }
 
        public int capacity() {
            return capacity;
        }
    }
 
    private final Segment<T>[] segments;
    private final int segmentCount;
    private final int segmentMask;
    private final AtomicInteger producerIndex = new AtomicInteger(0);
    private final ThreadLocal<Integer> threadSegment;
    private int consumerIndex = 0;
 
    @SuppressWarnings("unchecked")
    public KFIFOQueue(int segmentCount, int segmentCapacity) {
        this.segmentCount = Integer.highestOneBit(segmentCount - 1) << 1;
        this.segmentMask = this.segmentCount - 1;
        this.segments = new Segment[this.segmentCount];
 
        for (int i = 0; i < this.segmentCount; i++) {
            this.segments[i] = new Segment<>(segmentCapacity);
        }
 
        this.threadSegment = ThreadLocal.withInitial(() ->
            producerIndex.getAndIncrement() & segmentMask
        );
    }
 
    public boolean offer(T element) {
        if (element == null) {
            throw new NullPointerException("Null elements not permitted");
        }
        return segments[threadSegment.get()].offer(element);
    }
 
    public T poll() {
        for (int i = 0; i < segmentCount; i++) {
            int index = (consumerIndex + i) & segmentMask;
            T element = segments[index].poll();
 
            if (element != null) {
                consumerIndex = (index + 1) & segmentMask;
                return element;
            }
        }
        return null;
    }
 
    public int drain(java.util.function.Consumer<T> consumer) {
        int total = 0;
        for (int round = 0; round < segmentCount; round++) {
            for (int i = 0; i < segmentCount; i++) {
                int index = (consumerIndex + i) & segmentMask;
                T element;
                while ((element = segments[index].poll()) != null) {
                    consumer.accept(element);
                    total++;
                }
            }
        }
        return total;
    }
 
    public int size() {
        int total = 0;
        for (Segment<T> segment : segments) {
            total += segment.size();
        }
        return total;
    }
 
    public boolean isEmpty() {
        for (Segment<T> segment : segments) {
            if (!segment.isEmpty()) {
                return false;
            }
        }
        return true;
    }
 
    public int getK() {
        return segmentCount;
    }
}

Appendix B: Quick Reference

Algorithm Summary

Structure:

K independent SPSC (Single-Producer Single-Consumer) segments
Each producer assigned to one segment
Single consumer round-robins through segments

Guarantee:

Dequeued element was among K oldest at time of dequeue
NOT strict FIFO - order may vary within K elements

Performance:

Producers: Zero contention (per-segment ownership)
Consumer: O(K) segment checks per dequeue
Throughput: 6-10M ops/sec (vs 2M for strict FIFO)

Trade-off:

Relaxed ordering for higher throughput
Suitable when approximate ordering is acceptable

Performance Comparison

Metric	Strict FIFO	K-FIFO (K=8)
Throughput	~2M ops/s	~9M ops/s
p50 latency	187ns	52ns
p99.9 latency	15,234ns	412ns
GC allocation	4.2 MB/s	0.4 MB/s
Producer contention	High	None

When to Use

✅ USE K-FIFO	❌ AVOID K-FIFO
Load balancing	Message ordering required
Task scheduling	Event sourcing
Event aggregation	Single producer
Logging pipelines	Low throughput systems
Metrics collection	Team lacks lock-free experience
Real-time processing	Simplicity preferred

Appendix C: Further Reading

Academic Papers

"Wait-free queues with multiple enqueuers and dequeuers" - Michael & Scott
"Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms" - Michael & Scott
"The k-FIFO problem" - Afek et al.

Books

"The Art of Multiprocessor Programming" - Herlihy & Shavit
"Java Concurrency in Practice" - Goetz et al.
"Is Parallel Programming Hard, And, If So, What Can You Do About It?" - McKenney

Libraries

JCTools: https://github.com/JCTools/JCTools
LMAX Disruptor: https://lmax-exchange.github.io/disruptor/
Chronicle Queue: https://github.com/OpenHFT/Chronicle-Queue

Blogs

Mechanical Sympathy: https://mechanical-sympathy.blogspot.com/
Preshing on Programming: https://preshing.com/
Martin Thompson's Blog: https://mechanical-sympathy.blogspot.com/

Appendix D: Glossary of Terms

Acquire semantics: A memory ordering constraint ensuring that all reads and writes after an acquire operation see the effects of all writes before the corresponding release operation.

Cache line: The unit of data transfer between main memory and CPU cache, typically 64 bytes on modern x86-64 processors. Understanding cache lines is crucial for avoiding false sharing.

CAS (Compare-And-Swap): An atomic instruction that compares a memory location with an expected value and, if they match, updates it to a new value. The foundation of most lock-free algorithms.

False sharing: A performance problem that occurs when independent data items reside on the same cache line, causing unnecessary cache invalidations when either is modified.

K-FIFO: A queue with relaxed ordering guarantees where any dequeued element was among the K oldest elements at some point during the dequeue operation.

Lock-free: A progress guarantee where the system as a whole makes progress even if individual threads are delayed. Some thread will always complete its operation in a finite number of steps.

Memory barrier (fence): An instruction that enforces ordering constraints on memory operations, preventing the CPU and compiler from reordering reads and writes across the barrier.

MPSC (Multi-Producer Single-Consumer): A queue access pattern where multiple producer threads can enqueue concurrently, but only a single consumer thread dequeues.

Release semantics: A memory ordering constraint ensuring that all reads and writes before a release operation are visible to any thread that performs an acquire operation on the same variable.

SPSC (Single-Producer Single-Consumer): A queue access pattern with exactly one producer and one consumer thread. SPSC queues are the simplest to implement correctly and offer the best performance.

VarHandle: A Java API introduced in Java 9 that provides fine-grained control over memory ordering and atomic operations, replacing the use of sun.misc.Unsafe.

Wait-free: A stronger progress guarantee than lock-free, where every thread completes its operation in a bounded number of steps regardless of other threads.

Appendix E: Checklist for Implementing Your Own K-FIFO Queue

If you're implementing K-FIFO from scratch, use this checklist:

Design Phase:

Determine K value based on expected producer count
Choose segment capacity based on burst requirements
Decide on overflow strategy (fail, retry other segments, block)
Plan memory layout to avoid false sharing

Implementation Phase:

Use VarHandle for all atomic operations
Add cache line padding between hot fields
Use release semantics for publication (tail updates)
Use acquire semantics for consumption (tail reads)
Clear buffer slots after reading (help GC)
Use long positions to avoid wraparound issues

Testing Phase:

Unit tests for single-threaded behavior
Stress tests with many producers
Long-running tests for memory leaks
Property-based tests for invariants
Jcstress tests for memory ordering bugs

Deployment Phase:

Add monitoring metrics (throughput, latency, utilization)
Configure alerting thresholds
Document operational procedures
Establish performance baseline

Maintenance Phase:

Run benchmarks in CI to catch regressions
Monitor production metrics
Review segment balance periodically
Update documentation with lessons learned

This article is part of the Lock-Free in Java series. The complete source code is available at https://github.com/techishthoughts-org/off_heap_algorithms

K-FIFO Queues: Relaxed Ordering for Maximum Throughput