The 8-Byte Lock: Packing a Reader-Writer Lock Into 64 Bits
💡Typhon is an embedded, persistent, ACID database engine written in .NET that speaks the native language of game servers and real-time simulations: entities, components, and systems.
It delivers full transactional safety with MVCC snapshot isolation at sub-microsecond latency, powered by cache-line-aware storage, zero-copy access, and configurable durability.
Series: A Database That Thinks Like a Game Engine
- Why I’m Building a Database Engine in C#
- What Game Engines Know About Data That Databases Forgot
- Microsecond Latency in a Managed Language
- Deadlock-Free by Construction
- Three Durability Modes, One WAL
- Building a Page Cache That Doesn’t Count
- MVCC at Microsecond Scale
- The 8-Byte Lock (this post)
- Why We Eliminated the Primary Key B+Tree (coming soon)
A reader-writer lock has a lot to keep track of. How many readers are inside right now. How many are queued at the door. How many writers are queued behind them. Which thread, exactly, is holding it exclusively — because releasing a lock you don’t own is a bug you want to catch loudly. Whether anyone has ever had to wait on it, so you can find your hot spots later.
In .NET the reflex answer is ReaderWriterLockSlim. It tracks all of that for you, and it costs you a heap object with a header, a sync block, an internal wait queue, and a call into the kernel when things get tense.
Typhon’s answer is a ulong. All of it — the counter, the three classes of waiter, the owning thread id, the contention flag, the state machine — lives in eight bytes, and every state transition is exactly one CompareExchange. Uncontended, it costs 19 nanoseconds.
This post is the bit layout, the pattern that makes it readable instead of a swamp of shifts and masks, the fairness ladder that stops readers from starving writers, and an honest accounting of the parts I got wrong. And it ends on the trade that actually decides which lock goes where: every feature in that word is paid for in bits — and when the lock lives inside a page that gets written to disk, bits are a great deal more expensive than they look.
📍 Where we are
The last post built revision chains — the per-component version lists that give every transaction its own frozen snapshot of the database. Chains get appended to while other threads are walking them, so something has to arbitrate. I waved at it and moved on: “a small reader-writer lock in the header.” This is that lock, and its smaller sibling.
And it connects to Deadlock-Free by Construction, which made a strong claim: Typhon has no deadlock detector because it holds no data locks across operations. That’s still true. But “no data locks” doesn’t mean “no locks” — it means the locks that remain are short, physical, and local: a latch on a page while you read its header, a latch on a chain while you splice a revision into it. Held for tens of nanoseconds, never across a wait, never two at once in an order that could cycle. Those latches are what this post is about, and their size is the whole design constraint.
🔒 Why not just use the lock in the box?
Steel-manning first: ReaderWriterLockSlim is a good general-purpose lock, and if you need a handful of them you should use it. The trouble is what “a handful” means here.
Typhon needs a latch on every page in the page cache. Every block chain in every allocator. Every archetype cluster. Every component table. That’s not a handful — in a database with a few gigabytes resident, that’s hundreds of thousands of locks, each one guarding a critical section that lasts about as long as a cache miss.
At that multiplicity, three things about the standard answer become disqualifying:
Allocation. Monitor inflates a sync block per object; the modern System.Threading.Lock that the lock statement now prefers is itself a class, and so is ReaderWriterLockSlim — a heap object with a header, plus internal wait-queue machinery. Whichever you pick, you get an object. But a lock that must be a field inside a page header, sitting in a memory-mapped file, cannot be an object at all. It has to be a value you can embed.
Size. Even if you could embed it, sixty-odd bytes of lock inside a page header you were trying to keep to a cache line is a non-starter. The lock has to be an incidental cost of the structure, not a dominant one.
The floor. Typhon’s cost model has a hierarchy, each rung roughly ten times the last:
| Level | What it is | Cost |
|---|---|---|
| 0 | Thread-local read | ~2 ns |
| 1 | Uncontended atomic (CAS) | ~5–10 ns |
| 2 | Contended atomic, true sharing | 20–140 ns |
| 3 | System call | ~500–1,000 ns |
| 4 | Context switch / blocking lock | ~10,000 ns |
| 5 | Thread oversubscription | 100,000+ ns |
A lock that blocks is a lock that can cost you Level 4. Ten microseconds, to protect a critical section that was going to last fifty nanoseconds — a 200× overhead on the thing you were trying to make fast. In a database targeting microsecond transactions, that single fact drives the whole design: stay on rungs 1 and 2, never touch rung 4 if the work is short enough to spin through.
So the requirement is a lock that is a plain value type, small enough to embed by the hundred-thousand, that transitions with atomics and never enters the kernel on the happy path. Nothing in the box does that. You have to build it.
🧩 What fits in sixty-four bits
AccessControl is one field — private ulong _data — carved up like this:
// 8 Shared usage counter (bits 0-7) up to 255 concurrent readers
// 8 Shared waiters (bits 8-15)
// 8 Exclusive waiters (bits 16-23)
// 8 Promoter waiters (bits 24-31)
// 16 Exclusive thread id (bits 32-47)
// 1 Contention flag (bit 48) sticky
// 13 Reserved (bits 49-61)
// 2 State (bits 62-63) Idle | Shared | Exclusive
Two design choices in there are worth pulling out.
Three separate waiter counters, not one. Readers waiting, writers waiting, and promoters waiting (a promoter is a thread that already holds shared access and wants to upgrade to exclusive) each get their own byte. That looks like a luxury until you see what it buys, which is the next section.
A sticky contention bit. Bit 48 is set — with a single atomic OR — the first time any thread has to wait on this lock, and it’s never cleared until Reset(). The fast path never reads it. It costs nothing to carry, and it means that at any later moment I can sweep every page in the cache and ask which of these locks has ever been contended, even once — a free, permanent, per-lock hot-spot map. It’s the cheapest profiling I have anywhere in the engine: one bit, set at most once, read only by tooling.
🧵 Why the thread id is exactly sixteen bits
The owning thread gets sixteen bits, and the field earns its keep: releasing an exclusive lock you don’t own is a protocol violation, and I want it to throw rather than quietly corrupt the word. But a fixed-width thread id invites the obvious question — what happens when you run out?
Nothing, and the reason is exactly why Environment.CurrentManagedThreadId exists separately from the OS thread id in the first place. The OS id is a sparse, opaque handle whose reuse is nobody’s contract. The managed id is deliberately the opposite: the runtime hands out the lowest available number, and a dead thread’s id goes straight back into the pool. Ids stay dense and small — they count the threads alive right now, not the threads that have ever existed.
That inverts the constraint, and it’s the whole reason sixteen bits is enough. Monotonic ids would make the field a lifetime budget: hand out 65,535 of them over the life of the process and the next thread wraps into someone else’s identity. Recycled ids make it a concurrency ceiling instead — 65,535 threads alive at the same instant. A server that churns through millions of threads over a week never moves that ceiling; it just keeps handing out the same low numbers. And 65,535 simultaneously-live threads inside an embedded database engine isn’t a limit to design around, it’s a diagnosis: if you’re there, the lock word is the least of your problems.
(It started at ten bits, which was a mistake — 1,024 is fine on a laptop and nonsense on a 512-core server.)
⚠️ The dependency I’m taking on, stated out loud. Lowest-available reuse is what the open-source runtime does; it is not what the runtime promises. No specification obliges
ManagedThreadIdto stay dense. I’m relying on an implementation detail, on purpose, and the reason I sleep at night is that the property is load-bearing for everybody who indexes anything by thread id — which is a lot of code, including the runtime’s own. The incentive to preserve it is enormous and the incentive to break it is zero. But an assumption you’ve reasoned about and written down is a design decision; the same assumption left implicit is a landmine. So: written down.
💎 The prettiest code in the engine
Here’s the problem with packing a lock into a word: the code turns into a swamp. Every operation becomes shift-mask-or-shift-back, and one misplaced & is a corruption bug that shows up as a hang under load three weeks later.
The fix is LockData — a ref struct that makes the word behave like an object while still committing like a word:
private ref struct LockData
{
private ref ulong _data; // points at the real lock word, in place
private ulong _initial; // what we read
private ulong _staging; // what we're building
public int SharedCounter
{
get => (int)(_staging & SharedCounterMask);
set => _staging = (_staging & ~SharedCounterMask) | (uint)value;
}
public ulong State
{
get => _staging & StateMask;
set => _staging = (_staging & ~StateMask) | value;
}
// ... SharedWaiters, ExclusiveWaiters, PromoterWaiters, ThreadId
public bool TryUpdate()
{
var succeed = Interlocked.CompareExchange(ref _data, _staging, _initial) == _initial;
if (!succeed) Fetch(); // someone beat us — re-read and let the caller retry
return succeed;
}
}
Now the actual lock logic reads like a state machine, because it is one:
case IdleState:
if (ld.CanShareStart)
{
ld.State = SharedState;
ld.SharedCounter = 1;
break; // fall through to TryUpdate()
}
...
Two fields assigned, and the whole thing publishes atomically. That’s the trick, and it’s the part I’d take to any other system: _staging is a local. Every one of those property setters is bit arithmetic on a value sitting in a register — no atomics, no memory barriers, no contention, because nobody else can see it. You mutate it as many times as you like, as legibly as you like, and pay for exactly one atomic operation at the end when TryUpdate publishes the finished word with a single CompareExchange.
A transition that touches four logical fields costs one CAS. Not four. And if it loses the race, Fetch() re-reads the word and the loop reassesses from the new reality — which is why every one of these operations is written as while (true) around a switch. Optimistic, retry-on-collision, no lock to take a lock.
The same file has one more trick worth stealing. Blocking calls take a ref WaitContext carrying a deadline and a cancellation token — but most callers want to wait forever and shouldn’t pay for the privilege. So they pass ref WaitContext.Null, and the struct checks once:
_isNullRef = Unsafe.IsNullRef(ref ctx);
// ...
public bool ShouldStop => !_isNullRef && _ctx.ShouldStop;
Unsafe.IsNullRef gives you a null reference rather than a nullable value: infinite wait costs one bool test, and the timeout machinery is genuinely absent rather than merely unused.
🪜 The fairness ladder
Now the payoff for those three waiter counters. The entire fairness policy of the lock is three one-line predicates:
public bool CanShareStart => (_staging & (PromoterWaitersMask | ExclusiveWaitersMask)) == 0;
public bool CanExclusiveStart => (_staging & PromoterWaitersMask) == 0;
public bool CanPromoteToExclusive => (_initial & SharedCounterMask) == 1;
Read them as a priority ladder — promoters beat writers beat readers:
- A new reader may only enter if no writer and no promoter is waiting. This is the anti-starvation rule. Under a heavy read load, a reader-preferring lock lets an endless stream of readers hold the door open forever and a writer waits until the workload changes. (This is the documented default behaviour of
ReaderWriterLockSlim.) Here, the instant one writer registers, the reader gate slams: incoming readers queue behind it, the in-flight readers drain, the writer goes. - A new writer stands down for promoters, because a promoter is a thread already holding shared access. Making it wait behind a fresh writer would be perverse — it’s already inside.
- A promoter may only upgrade when it is the sole reader (
counter == 1). Two threads both holding shared access and both trying to upgrade is the textbook promotion deadlock; the counter makes it structurally unrepresentable, because at most one of them can ever see a count of one.
Three masks, one comparison each. No queue, no condition variable, no priority-inheritance logic — a complete fairness policy expressed as “are these bytes zero.”
🤏 Four bytes, and what they cost you
Everything above — the waiter counters, the fairness ladder, the explicit state field — is features, and every feature in that word is paid for in bits. So there’s a second lock, AccessControlSmall, which spends half as many:
// 15 Shared counter (bits 0-14, max 32,767)
// 1 Contention flag (bit 15)
// 16 Thread id (bits 16-31)
Notice what’s missing. There is no state field. State is implied — a non-zero thread id means Exclusive, a non-zero counter means Shared, both zero means Idle. Which has a lovely consequence: the Idle → Exclusive transition, the most common one there is, becomes a single CAS against literal zero.
Also missing: all three waiter counters. And that is the trade, stated plainly — AccessControlSmall has no waiter tracking, therefore no fairness. A pending writer can be starved by a sustained stream of readers. Nothing clever recovers that; you either need the counters or you don’t.
So which lock goes where is a straight exchange of features against bytes — and the reason bytes are worth so much more than they look is that some of these locks are not merely in memory. They’re in the data.
A latch in a page header lives inside a page that gets written to disk. It is persistent state. Those four-versus-eight bytes are not a transient cost you can buy your way out of with more RAM — they are written on every flush, read back on every load, and they occupy space in the page that would otherwise be holding your data, in every page, for the life of the database. Multiply by a few million pages and the difference stops being an implementation detail and starts being a storage-format decision, which is the kind of decision you don’t get to revisit later.
That reframes the whole question. It isn’t “smaller is better” — it’s that the byte budget of a persistent structure is nothing like the byte budget of a heap object. So the rule is simply: on a structure that’s central, in-memory, long-lived and genuinely contended, fairness is worth eight bytes and you take the full lock. On a structure that gets serialized into a page, you take the four-byte one, spend the savings on data, and keep the critical sections short enough that starvation never has the time to develop.
📊 The numbers
Measured with BenchmarkDotNet on an Intel Xeon Platinum 8151 @ 3.40 GHz, Ubuntu 22.04, .NET 10. Each figure is a full acquire and release, single-threaded, with nobody to fight:
| Operation |
AccessControl (8 B) |
AccessControlSmall (4 B) |
|---|---|---|
| Shared: acquire + release | 18.8 ns | 17.0 ns |
| Exclusive: acquire + release | 21.5 ns | 24.5 ns |
| Promote shared → exclusive → demote | 44 ns | 45.5 ns |
That’s the floor, and it is Level 1 of the hierarchy: a CompareExchange on a line already sitting in this core’s L1, with no other core wanting it.
Now the opposite extreme — the same shared acquire/release, but with N−1 background threads hammering the same lock word in a tight loop:
| Threads contending | Shared: acquire + release |
|---|---|
| 2 | 940 ns |
| 4 | 1.86 µs |
| 8 | 2.00 µs |
Fifty to a hundredfold. Nothing about the lock changed between those two tables — same word, same instructions, same code path. The only difference is that the cache line is now being dragged from core to core on every attempt.
I want to be precise about what that second table is, though, because it would be easy to read it as a warning about Typhon and it isn’t one. It’s a hardware number, not an engine number. It’s what a contended CAS costs, obtained by constructing the worst case deliberately: many threads, one word, no work in between. And the engine is built so that scenario doesn’t arise.
There is no central lock in Typhon — no handful of monitors that every operation funnels through. There are hundreds of thousands of latches: one per page, per component table, per cluster, per block chain, each held for the tens of nanoseconds it takes to read a header or splice a pointer. For that table to describe the engine, a crowd of threads would have to want the same latch at the same instant. At this granularity, with hold times this short, that is close to a non-event. Not impossible — “almost never” isn’t “never” — but it is nowhere near the steady state the benchmark manufactures.
So read that second table as a receipt rather than a warning: it’s the bill you’d be handed for centralising your locking, and it’s why Typhon doesn’t. The answer to contention was never a cleverer lock — it’s granularity. Don’t make one lock hot; make a hundred thousand cold ones.
⚖️ Trade-offs, and what I got wrong
I nearly went hunting for three nanoseconds that were never there. The 4-byte lock measures slower at exclusive acquisition than the 8-byte one — 24.5 ns against 21.5 — which is the opposite of what its simpler fast path predicts, and I spent a while looking for the flaw in the compact design. There is no flaw. Every field read, every mask, every shift in both locks is register arithmetic, and register arithmetic is free: the entire price of the operation is the Interlocked. And a CAS has no fixed price, only a price in a context — the memory system decides what the line costs, not your bit fields. My bet is that the smaller struct is likelier to share its line with whatever sits beside it, so its CAS pays coherence traffic the other’s doesn’t. I have no proof and won’t pretend otherwise. But a three-nanosecond spread between two locks was never going to be a fact about the locks.
I shrink the lock to 4 bytes and then pad it back to 64. In ArchetypeClusterState the latch is wrapped in a [StructLayout(Size = 64)] struct so it owns an entire cache line — it sits beside hot mutable counters, and false sharing on a lock word is worse than a big lock word. Two threads taking two logically independent locks that happen to share a line will ping-pong it between cores on every CAS, at full contended cost, having never contended for anything; the engine’s spatial rules go so far as to forbid bit-packed latch arrays for exactly that reason. So the honest summary of the size story is not “smaller is better.” It’s: make the lock small enough to live where the data lives, then spend whatever padding it takes to keep its line to itself.
“Zero-cost telemetry” is very nearly true, and I should stop saying “zero.” Every acquire and release has a trace-event emit call, gated on a static readonly bool so the JIT can prove the branch dead and delete it. It works — but the off-path benchmark still shows roughly 2 ns per iteration surviving versus an empty method. Two nanoseconds on a 19 ns operation is about 10%, and calling that “free” would be exactly the kind of claim I’d disbelieve in someone else’s post.
🎯 The takeaway
The reusable idea isn’t the bit layout — yours will be different. It’s the staging pattern: read the whole word once, mutate a local copy as many times and as legibly as you want, publish it with one CompareExchange, and retry from the top if you lost.
That structure is what lets you have both of the things people assume are in tension. The lock’s state can be arbitrarily rich — five fields, a state machine, a fairness ladder, a diagnostic bit — because manipulating it is just arithmetic on a register that no other thread can see. And it can still be atomic, because “atomic” is a property of the single instruction that publishes the result, not of the reasoning that produced it.
Which leaves exactly one thing that costs anything: the publish. Not the shifts, not the masks, not how many fields you touched on the way — one CompareExchange, and a price set entirely by the state of the cache line it lands on. So the design lever that matters was never what you put in the word. It’s where the word lives. Pack it as densely and as cleverly as you like; then go make sure nothing else is touching its line.
Whenever you find yourself reaching for a lock to protect a small piece of state, ask whether the state could be the word instead. Often it fits. And when it fits, the lock stops being an object you acquire and becomes a number you agree on.
⏭️ What’s next
This whole post has been about making a latch cost as little as it possibly can. The next one is about the cheaper move — not having the structure at all. Typhon used to carry a primary-key B+Tree, for the very best of reasons: every database has a primary index. That’s simply what one does. It turned out to be a reflex imported from a world this engine doesn’t live in, because an ECS entity is found by its archetype and its key — it was never going to be walked to through an index. So the whole thing came out. Post #9: Why We Eliminated the Primary Key B+Tree — what it cost to keep, what replaced it, and how to spot the moment you’ve inherited an assumption instead of making a decision.
Follow the GitHub repo for source and benchmarks, or subscribe via RSS.