Cooperative Concurrency Control for Write-Intensive Key-Value Workloads

Key-value stores — the fast in-memory databases behind online services — are all tuned for read-heavy traffic, but real workloads increasingly have many writes, and the standard trick of pinning each key's writes to one thread to avoid locking then wrecks load balance; this work from EPFL and Georgia Tech builds C-4, a co-design that teaches the network card to split writes into independent ones it can spread across threads and dependent ones it funnels to a single thread that batches them into one update, cutting tail latency by up to 5 times and lifting throughput up to 1.7 times while keeping strong consistency.

Why this problem is worth solving

The whole difficulty lives in one design decision, so it is worth being precise about it.

The reason this matters more than it used to is that the workloads have changed, in two distinct ways.

What people did before, and where it broke

• Static exclusive write, no balancing (EREW). Hash every request, read or write, to a fixed thread; never balance anything. Where it broke. With no load balancing at all, transient queues form on busy threads and throughput saturates well below the hardware’s potential.
• Concurrent readers, partitioned writes (CREW, the state of the art). Let reads run on any thread and balance freely, but keep each key’s writes pinned to one thread. Where it broke. It handles read-heavy traffic beautifully but cannot balance writes, so as the write fraction rises its tail latency climbs toward EREW and skew overwhelms the hot writer.
• Frequency-scale the overloaded core. Detect the buried hot-writer thread and clock it faster. Where it broke. A single core’s clock headroom cannot absorb the load a badly-skewed workload dumps on it; it is a band-aid, not a fix.
• Multi-version concurrency frameworks (RLU, MV-RLU). Let writers create new versions so readers never lock, enabling write balancing in software. Where it broke. Version management — logging, commit, garbage collection — adds overhead ruinous at microsecond scale: ported to a key-value store, write latency rose several-fold to dozens of times, and the store could not even meet its latency target at low load.
• Software delegation (flat combining, remote core locking). Funnel all writes to a shared key to one core through software queues. Where it broke. The software shuffling of requests between cores to serialize them is itself the overhead CREW was trying to avoid, essentially reimplementing partitioning with extra cost.
• The gap. Every approach either forbade write balancing to stay lock-free, or bought balancing with synchronization overhead that microsecond serving cannot afford. What was missing was a way to balance the writes that are safe to move and efficiently absorb the ones that are not, without locks — which is exactly what write-intensive key-value serving needs.

How C-4 works

The idea

Sort the writes into two kinds and give each its own remedy. The insight that unlocks everything is that static partitioning treats all writes as if they conflict, when in truth two writes clash only if they touch the same key. So C-4 separates writes into independent ones — to different keys, which can safely run on any thread — and dependent ones — to the same key, which must be serialized. The two classes get opposite treatments: independent writes are load-balanced to spread the work, while dependent writes are deliberately concentrated on one thread so they can be batched. Classifying a stream of operations into the kind you can freely rearrange and the kind you must handle carefully, then applying a different mechanism to each, is the same strategy the distributed-training communication work covered elsewhere on this site uses, splitting communication into the part it can overlap by reordering and the part it must hide by decomposing, and treating each on its own terms.

Make the exclusive lock exist only during the instant of a real conflict. Static partitioning is permanently conservative: a key belongs to its one thread forever, whether or not anyone is writing it. C-4’s dynamic policy keeps the single-writer guarantee but shrinks it to the moment it is actually needed — a key becomes exclusive to a thread only while a write to it is in flight, and the instant that write completes the key is free to be balanced anywhere again. The network card holds these ephemeral ownerships in a tiny table, so the restriction applies precisely when two writes genuinely collide and never otherwise. Separating the fixed question of what owns a resource from the fleeting question of when it is truly in use, and imposing the constraint only in that narrow window, is the same discipline the memory-resizing work covered elsewhere on this site follows, decoupling what to resize from when so the costly rule fires only at the moment it matters.

Turn the overloaded hot thread’s burden into a chance to do less. When skew dumps a torrent of writes to one key onto a single thread, the naive response is to make that thread faster; C-4 instead makes it do less work. Because all those writes target the same item, the thread gathers them into one private log and applies them as a single combined update, so instead of paying the coherence cost of writing the shared cache line once per request, it pays it once per batch. Counterintuitively, the busier the hot key gets, the more the thread can batch, so its cost per write falls as load rises. Letting a single unit absorb many correlated requests together, rather than paying a fresh cost for each, is the same move the serverless orchestration work covered elsewhere on this site makes, reusing one busy container to serve a queue of requests for the same function instead of spinning up a new one every time.

Following a burst of writes through C-4

Under heavy skew this can cap throughput even when writes are only a few percent of traffic.

Why it works

• Only truly conflicting writes need to be serialized. Static partitioning pins every key’s writes to one thread to avoid locks, forbidding all write balancing → but two writes actually conflict only when they hit the same key, which is rare under uniform load → so the network card can freely balance independent writes and make a key exclusive only while a write to it is in flight, reaching near-ideal tail latency.
• Deciding write placement in the card keeps it lock-free and cheap. Balancing writes dynamically would normally need synchronization, or broadcasting ownership to thousands of clients → but a small table in the network card tracks which thread owns each active key and routes writes accordingly → so threads still avoid atomic instructions while the store gains write balancing, at a hardware cost of a fraction of a percent.
• Skew that overwhelms one thread becomes an opportunity to batch. Heavy skew funnels a flood of writes to the hottest key onto a single thread, saturating it while others idle → but because those writes all target the same item, that thread can compact them into one update instead of applying each separately → so the bottleneck thread does less work per write as load rises, not more.
• Batching in a private log avoids the coherence traffic that makes hot writes slow. Applying each write to the shared datastore repeatedly invalidates and refetches the hot cache line, so service time climbs with load → but gathering writes into a thread-private batch touches no shared lines and writes the datastore once → so the hot thread’s per-write time falls, dropping from 908 to 243 nanoseconds.
• Deferring the batch’s responses keeps the store linearizable. Acknowledging a compacted write before its batch is applied would let a later read miss it → but holding every response until the window closes makes concurrent reads legally free to return the old value → so batching preserves strong consistency instead of weakening it.

What it costs (trade-offs and scope)

• It is evaluated entirely in simulation. The results come from cycle-accurate full-system simulation of a 64-core server with a modeled network card; the hardware table’s area and power are analytical estimates, and no physical system was built.
• It needs a specialized network card and RPC stack. The dynamic balancing requires a card that terminates network protocols in hardware, parses application headers, and runs a programmable load balancer — features the authors expect in future products, not commodity cards today.
• The two mechanisms are workload-specific and can hurt off-target. Dynamic balancing helps uniform write-heavy traffic; compaction helps skewed traffic; and compaction actually slows uniform workloads by a few percent through fruitless queue scanning, so the system must apply the right one for the workload.
• Compaction trades a latency floor for throughput. Under light load, windows open but gather few writes, and closing only at the latency deadline creates a tail-latency jump; an adaptive early-close would fix it but is not implemented. It also deliberately delays write acknowledgements until a window closes.
• The benefit shrinks for small items. When key-value pairs are tiny, the fixed cost of building a batch approaches the cost of a single store, so the hot-thread speedup falls to modest levels, though throughput still improves.
• It preserves only single-key consistency. Linearizability holds per key; multi-key atomicity is out of scope, left to higher transaction layers.
• The concurrency-framework baselines are outside their design point. General multi-versioning frameworks look very poor here, but they were not built for microsecond-scale key-value serving, so the comparison flatters C-4’s specialization.

The evaluation

Check yourself

Sources

The paper is “Cooperative Concurrency Control for Write-Intensive Key-Value Workloads” by Mark Sutherland, Babak Falsafi, and Alexandros Daglis, published at ASPLOS 2023, DOI 10.1145/3567955.3567957. The authors are at EcoCloud, EPFL and the Georgia Institute of Technology.

This explainer is written from the full 17-page text. Everything above comes from the paper’s own sections: the introduction and motivation establishing the rise of write-intensive workloads and the KVS workload taxonomy (the read-mostly regions that are handled and the uniform-write-heavy and skewed read-write regions that are not); the tradeoff analysis showing static write partitioning as the shared root cause and the two insights (independent writes can be balanced, dependent writes can be compacted); the queueing model quantifying that dynamic partitioning reaches near-ideal tail latency and compaction boosts skewed-workload throughput 1.5 to 2 times; the C-4 design describing dynamic CREW realized in the network card with the Exclusive Writer Table and software write compaction with its linearizability argument (deferring responses until a window closes); the implementation on the NeBuLa architecture with MICA (adding only 105 lines for compaction) and the hardware-cost analysis (a 128-entry table at 0.004 square millimeters and 6.85 milliwatts, 0.002 percent of a 64-core chip); and the evaluation reporting up to 5 times lower 99th-percentile tail latency for write-heavy workloads, up to 1.7 times higher throughput for skewed workloads, the hot thread’s service time falling from 908 to 243 nanoseconds under compaction, and the item-size sensitivity showing gains from 1.33 to 1.6 times across key-value sizes.