Ticket Locks: The Architecture of Predictability

In the deep waters of systems programming, raw speed is often less important than predictable latency.

Standard spinlocks, typically built around atomic Compare-and-Swap (CAS) loops, suffer from a critical flaw under high contention: unfairness. When a lock is released, the hardware arbiter decides who gets it next based on processor topology or sheer luck, not waiting time. This leads to starvation and erratic P99 latency spikes.

Enter the Ticket Lock. It trades the chaotic scramble of CAS for the orderly discipline of a FIFO queue, ensuring that every thread gets its turn.

1. The Deli Counter Model

The mechanism is simple, mirroring a physical "take a number" system:

1. next_ticket: The dispenser. Threads atomically fetch-and-increment this value to get their position in line.
2. current_ticket: The display. Shows who is currently being served.

Threads spin on current_ticket until it matches their hand-held number. This guarantees strict FIFO ordering—no one cuts in line.

2. A Minimal Reference: C++20

Before examining the cache-aware version, it helps to see the bare mechanism in isolation. This C++20 implementation exposes the two-counter logic clearly, without any memory layout constraints:

#include <atomic>
#include <thread>

class TicketLock {
    // The next ticket to be issued
    std::atomic<size_t> next_ticket_{0};
    // The ticket currently being served
    std::atomic<size_t> now_serving_{0};

public:
    void lock() {
        // 1. Atomically grab a ticket
        // memory_order_relaxed is sufficient here because the fetch_add is atomic,
        // and the subsequent acquire load provides the necessary barrier.
        size_t my_ticket = next_ticket_.fetch_add(1, std::memory_order_relaxed);

        // 2. Wait for our number to be called
        while (now_serving_.load(std::memory_order_acquire) != my_ticket) {
            // Hint to the CPU that we are spinning to save power/pipeline resources
            #if defined(__x86_64__) || defined(_M_X64)
                __builtin_ia32_pause();
            #elif defined(__aarch64__)
                asm volatile("yield");
            #endif
        }
    }

    void unlock() {
        // 3. Call the next number
        // Use release semantics to ensure writes in the critical section are visible
        size_t current = now_serving_.load(std::memory_order_relaxed);
        now_serving_.store(current + 1, std::memory_order_release);
    }
};

This captures the essential idea but makes no guarantees about where these counters land in memory—a gap that proves costly at scale, and that we address next.

3. Zig Implementation: Explicit Memory Layout

One of Zig's superpowers is its explicit control over memory alignment. In high-performance locking, where variables sit in memory matters as much as the algorithm itself.

Here is a production-grade implementation that respects CPU cache lines:

const std = @import("std");
const atomic = std.atomic;

/// TicketLock: A fair synchronization primitive
/// Enforces strict FIFO ordering via dual counters
pub const TicketLock = struct {
    // Critical Optimization: Align counters to 64 bytes (typical cache line)
    // to prevent False Sharing between the dispenser and the display.
    next_ticket: atomic.Value(u64) align(64) = atomic.Value(u64).init(0),
    current_ticket: atomic.Value(u64) align(64) = atomic.Value(u64).init(0),

    /// Acquire: Take a ticket and wait
    pub fn acquire(self: *TicketLock) void {
        // 1. Atomic Fetch-and-Add
        // This single atomic write establishes the global order.
        const my_ticket = self.next_ticket.fetchAdd(1, .Monotonic);

        // 2. Spin Wait (Read-Only)
        // Spin until the display shows our number.
        while (self.current_ticket.load(.Acquire) != my_ticket) {
            // Hint to the CPU that we are in a spin loop to save power/pipeline slots
            std.atomic.spinLoopPause();
        }
    }

    /// Release: Call the next number
    pub fn release(self: *TicketLock) void {
        // 3. Store-Release
        // Incrementing this value unblocks the specific thread holding (my_ticket + 1).
        const current = self.current_ticket.load(.Unordered);
        self.current_ticket.store(current + 1, .Release);
    }
};

4. The Cost of False Sharing

Notice the align(64) directives. These aren't just for show.

In modern multi-core processors, the L1/L2 cache operates on "cache lines" (usually 64 bytes). If next_ticket (written by arriving threads) and current_ticket (written by the lock holder) reside on the same cache line, cores will constantly invalidate each other's caches via the MESI protocol, even though they are touching different variables. This phenomenon is called False Sharing, and it can decimate performance.

By forcing alignment, we ensure these hot variables live in separate cache lines, minimizing unnecessary bus traffic:

• next_ticket: written primarily by newly arriving threads competing for a position.
• current_ticket: written by the lock holder on release, read by all waiters.

The C++20 version above would suffer this contention silently. The Zig version makes the fix explicit and verifiable at compile time.

5. Trade-offs

Gains

Determinism: Starvation is eliminated among competing threads. Every thread gets its turn in strict arrival order—a hard guarantee that CAS-based locks cannot provide.

Low Overhead: In uncontended or lightly contended scenarios, the cost is one atomic fetch-and-increment plus a comparison, cheaper than any OS-assisted mutex.

The Global Spinning Problem

While Ticket Locks solve fairness, they are not a silver bullet. They still suffer from global spinning:

• All waiting threads spin on the same variable (current_ticket).
• When current_ticket is updated, every waiting core invalidates its cache line and re-reads from memory.
• On a machine with 100+ cores, this "thundering herd" of cache coherence traffic can saturate the interconnect.

For extreme scale, MCS locks and CLH locks are the superior choice—each thread spins on its own local variable, confining coherence traffic to a single node. The trade-off is meaningfully more complex bookkeeping. For moderate contention, or when strict ordering is a hard requirement, the Ticket Lock remains the right tool.

Conclusion

The Ticket Lock exemplifies how algorithmic fairness can reduce tail latency:

1. Fairness is an architectural choice: We accept slightly higher overhead for stable, predictable performance.
2. Hardware empathy is non-negotiable: Simple alignment tweaks can prevent invisible performance cliffs.
3. Order matters: For moderate contention or when strict ordering is critical, a simple FIFO queue remains the most reliable, deterministic choice.