← Back to Blog
EN中文

The Sign Bit as a Traffic Light: A Study in Lightweight RW Locks

In high-throughput distributed systems, we often face the classic concurrency problem: read-heavy, write-rare workloads.

Standard locks like std::shared_mutex or pthread_rwlock_t are general-purpose tools. But general-purpose often means compromise. When your system spends 99.9% of its time reading data and only 0.1% writing, every cycle spent acquiring a read lock adds up. Even a few extra atomic instructions or cache line bounces can become a significant bottleneck.

Today, we're dissecting a design pattern found in certain industrial-grade distributed libraries. It leverages the sign bit of a 32-bit integer and Linux Futexes to compress read-lock overhead to the absolute minimum. To clearly demonstrate the mechanics, we'll reconstruct the core idea using Zig.

The Core Idea: Locking Inside an Integer

The soul of this design is simple: The entire lock state lives in a single 32-bit integer (counter).

Recall that in a signed 32-bit integer (i32), the most significant bit (MSB, bit 31) is the sign bit.

  • If it's 0, the number is positive.
  • If it's 1, the number is negative.

The designers cleverly repurposed this:

  1. Lower 31 bits: Track the number of active readers.
  2. Highest bit (Bit 31): Acts as the Write Pending/Held Flag.

This layout gives us a massive advantage: The happy path for acquiring a read lock requires just one atomic instruction.

The Reader's Perspective: Optimism as a Strategy

In most RW lock implementations, a reader must check "is a writer waiting?" before entering to prevent writer starvation. This check usually involves separate state variables or complex CAS loops.

But here, the reader is extremely optimistic.

pub fn acquireRead(self: *LightweightRWLock) void {
    while (true) {
        // 1. Increment first, ask questions later!
        // This is an atomic add, returning the OLD value.
        const prev = self.counter.fetchAdd(1, .SeqCst);
        
        // 2. Check the result.
        // If the sign bit is 0 (positive), there was no writer.
        // We successfully incremented the reader count. We're in!
        if (prev & WRITE_BIT == 0) return;

        // 3. Oops, there was a writer (sign bit is 1).
        // We blindly incremented, so now we must undo our mistake.
        _ = self.counter.fetchSub(1, .SeqCst);
        
        // 4. Go to sleep in kernel space and wait for the writer to finish.
        self.waitForWriter();
    }
}

The Trade-off: The Rollback

This reveals an interesting trade-off:

  • Benefit: In the absence of writer contention (99.9% of the time), a reader performs only one fetchAdd and a bitwise check. This is faster than almost any standard library implementation because it minimizes memory barriers and state checks.
  • Cost: If a writer happens to be present (Write Bit is 1), the reader's fetchAdd becomes a "mistake." The reader must perform a fetchSub to roll back the counter. This wastes CPU cycles and can cause cache line bouncing.

This is a gambling design: it bets that writes are rare. If the bet pays off, throughput is immense. If it loses, the cost is real but manageable.

The Writer's Perspective: Claiming the Sign Bit

The writer logic is more assertive. When a writer wants the lock, it doesn't care how many readers are currently active. Its first priority is to flip the switch.

pub fn acquireWrite(self: *LightweightRWLock) void {
    while (true) {
        // 1. Try to atomically set the High Bit (Write Bit).
        // fetchOr sets the bit to 1 and returns the old value.
        const prev = self.counter.fetchOr(WRITE_BIT, .SeqCst);
        
        // 2. Was there already another writer?
        if (prev & WRITE_BIT != 0) {
            // Another writer beat us to it. Wait in line.
            self.waitForWriter();
            continue; // Retry after waking up
        }

        // 3. We claimed the sign bit!
        // New readers are now blocked (they'll see the 1 and rollback).
        // BUT! Old readers might still be reading.
        
        // 4. Wait for existing readers to drain.
        // As long as the lower 31 bits are not 0, we wait.
        while (self.counter.load(.SeqCst) & ~WRITE_BIT != 0) {
            self.waitForReaders();
        }
        
        // All readers are gone. The lock is ours.
        return;
    }
}

The writer uses fetchOr to claim the sign bit atomically. This instantly cuts off the flow of new readers. Then, the writer patiently waits for the current reader count to drop to zero.

Kernel Cooperation: Futex

While atomic operations are fast, busy-waiting (spinning) wastes CPU if the lock is held for any length of time. This is where Linux Futex (Fast Userspace Mutex) comes in.

In the Zig code above, waitForWriter and waitForReaders would wrap syscall(SYS_futex, ...) in a production environment.

  • Reader Waiting: When a reader sees the sign bit is 1, it calls futex_wait to suspend itself until the writer releases the lock (clears the bit and calls futex_wake).
  • Writer Waiting: When a writer sees readers are still active (count > 0), it sleeps, waiting for the last departing reader to wake it up.

This combination of user-space atomics for the fast path and kernel-space suspension for contention is the cornerstone of modern high-performance locking.

Summary

The takeaway here is that there is no perfect lock, only the right lock for the workload.

  1. Optimize the Hot Path: Reduce the most frequent operation (reading) to a single atomic instruction.
  2. Repurpose Integer Bits: The sign bit isn't just for math; it's a highly efficient state flag in concurrency control.
  3. Accept Rollbacks: To achieve extreme speed on the happy path, we accept the cost of rolling back operations on the cold path (contention).

Reconstructing such low-level primitives in a language like Zig, which offers precise control over memory layout and system calls, is an excellent exercise in systems programming.