Sharded counters

Deep dive

How it works

In: increments from many threads; occasional reads · Out: the total (not a snapshot) · State: one padded cell per thread or CPU · Cost: increment O(1) with no shared-line contention (order of 5-10 ns); read O(shards)

cores:   c0      c1      c2      c3
cells: [ 17 ] [  5 ] [ 42 ] [  9 ]   each on its own 128-byte line
read:  17 + 5 + 42 + 9 = 73

1. Allocate a power-of-two number of cells ≥ the core count, each padded to 128 bytes.
2. Each thread picks a cell once (round-robin thread index, or the current CPU id) and increments it with a relaxed atomic add.
3. Readers load every cell (relaxed) and sum.
4. Variants: adaptive (Java LongAdder): start with one base word; on a failed CAS (contention), create cells and rehash the thread's probe. Batched (Linux percpu_counter): per-CPU deltas folded into a global value when they exceed a batch size, so approximate reads are O(1).

Code

use std::cell::Cell;
use std::sync::atomic::{AtomicU64, AtomicUsize, Ordering::Relaxed};

#[repr(align(128))]
struct Shard(AtomicU64);

pub struct ShardedCounter { shards: Box<[Shard]>, mask: usize }

static NEXT_THREAD: AtomicUsize = AtomicUsize::new(0);
thread_local! {
    static THREAD_IDX: Cell<usize> = const { Cell::new(usize::MAX) };
}
fn thread_idx() -> usize {
    THREAD_IDX.with(|c| {
        if c.get() == usize::MAX { c.set(NEXT_THREAD.fetch_add(1, Relaxed)); } // once per thread
        c.get()
    })
}

impl ShardedCounter {
    pub fn new() -> Self {
        let n = std::thread::available_parallelism().map_or(8, |n| n.get()).next_power_of_two();
        ShardedCounter { shards: (0..n).map(|_| Shard(AtomicU64::new(0))).collect(), mask: n - 1 }
    }
    #[inline]
    pub fn add(&self, x: u64) {
        // Relaxed: the counter publishes no other data. Atomic because threads > shards may share a cell.
        self.shards[thread_idx() & self.mask].0.fetch_add(x, Relaxed);
    }
    /// Not a snapshot: increments racing with the scan may or may not be counted.
    pub fn sum(&self) -> u64 {
        self.shards.iter().map(|s| s.0.load(Relaxed)).sum()
    }
}

/// Cheaper still: a thread-local batch flushed every FLUSH increments (approximate reads).
pub struct LocalBatch<'a> { target: &'a ShardedCounter, pending: u64 }
impl<'a> LocalBatch<'a> {
    const FLUSH: u64 = 1024;
    pub fn new(target: &'a ShardedCounter) -> Self { LocalBatch { target, pending: 0 } }
    #[inline]
    pub fn inc(&mut self) {
        self.pending += 1; // plain add, ~1 cycle
        if self.pending == Self::FLUSH { self.target.add(self.pending); self.pending = 0; }
    }
}
impl Drop for LocalBatch<'_> {
    fn drop(&mut self) { if self.pending > 0 { self.target.add(self.pending); } }
}

Complexity and constants

• Memory: shards × 128 B; 64 shards = 8 KB per counter.
• A read touches every shard line: with 64 shards, order of 64 cache misses (several µs) if all were recently written. Fine for metrics, bad for hot-path checks.

Efficiency

• Cost: from the table above, all order of: contended single atomic 50-100+ ns per increment, sharded atomic 5-10 ns, thread-local batch about 1 ns, per-CPU without atomics 1-2 ns. A read touches every shard: with 64 shards, order of 64 cache misses (several µs). Memory: shards × 128 B, 8 KB for 64 shards. Bound: coherence traffic on writes; reads are O(shards).
• Levers:
  • pad each cell to 128 B — keeps each core's line local, no false sharing (false sharing) — always
  • thread-local batch flushed every 1,024 increments — about 1 ns per increment (Code above) — approximate reads are fine
  • cell by current CPU (rseq, Linux 4.18+) — plain per-CPU updates, no atomics — threads outnumber cores
  • adaptive cells grown on CAS failure (Java LongAdder) — one word when uncontended, shards only under contention — unknown contention
  • read rarely, never on the hot path — sum() costs O(shards) misses — metrics scraped every few seconds
• Naive → standard → state of the art:
  • one shared AtomicU64 · 50-100+ ns per contended increment, flat or negative scaling
  • padded sharded atomics · order of 5-10 ns, linear scaling
  • thread-local batches or rseq per-CPU slots · order of 1-2 ns, linear scaling

Implementation notes

• Choose cells by thread index (stable, cheap) or by current CPU (sched_getcpu, rdpid; order of 10-20 ns unless cached). CPU-based is better when threads outnumber cores; migrations are harmless because increments stay atomic.
• Linux restartable sequences (rseq, 4.18+) let user space update a per-CPU slot with plain instructions, restarting if preempted; TCMalloc's per-CPU caches use it.
• Linux percpu_counter: per-CPU s32 deltas, folded into a global s64 under a spinlock once |delta| ≥ batch (default batch scales with CPU count). percpu_counter_read() is O(1) approximate, percpu_counter_sum() exact-ish.
• For per-key counters (millions of keys), shard the map per thread and merge periodically instead of sharding each counter.
• Rate limiting and quotas need a fast "are we over the limit" check: keep a local budget per shard and refill from a global pool (the same idea as batching).

Pitfalls

• Forgetting the padding: shards in one line are slower than one counter (false sharing).
• Using sum() on a hot path (e.g. for every admission decision).
• Expecting sum() to be monotonic across readers or exact at a moment; it is neither guaranteed under concurrent writes (it is between the before and after totals for increment-only counters).
• Resetting by storing 0 into each cell while writers run: increments between the stores are lost or double counted. Use per-reader baselines (delta from the last read) instead.
• Thread-local batches lost on thread exit if not flushed (the Drop above handles it; thread pools that never exit need periodic flushes).

Variants and alternatives

In production

OS kernels: Linux percpu_counter and per-CPU vm_stat/SNMP statistics. Language runtimes and libraries: Java LongAdder (and the same striping in ConcurrentHashMap's CounterCells for size()), Prometheus Java client counters (DoubleAdder), Go runtime per-P statistics, Go xsync.Counter, Folly ThreadCachedInt. Memory allocators: TCMalloc per-CPU caches (rseq).

Implementations

Sources

• Silas Boyd-Wickizer, Austin T. Clements, Yandong Mao, Aleksey Pesterev, M. Frans Kaashoek, Robert Morris, Nickolai Zeldovich, An Analysis of Linux Scalability to Many Cores, OSDI 2010. paper
• Faith Ellen, Yossi Lev, Victor Luchangco, Mark Moir, SNZI: Scalable NonZero Indicators, PODC 2007. paper
• Doug Lea, java.util.concurrent.atomic.LongAdder and Striped64 (JDK 8 source and Javadoc). docs · code
• Paul E. McKenney, Is Parallel Programming Hard, And, If So, What Can You Do About It?, chapter "Counting". book