Scenarios

Write amplification first. B+tree: a 16 KB page per 200-byte row ≈ 80×, plus the log and the SSD's own amplification (about 240× at the flash with a 3× factor). Leveled LSM: T × L ≈ 30; tiered about 3–4, but with up to 30 runs per read.

With 90% writes the LSM wins. Bloom filters, with more bits on the smaller levels, keep point reads near one I/O.

They are the LSM's weak spot, merging across all runs. Make time part of the sort key, or add a time-partitioned layer so a scan touches few runs. Use a sparse index on the immutable files.

Compaction stalls hurt p99, so pace compaction; watch for key skew.

With 8 KB rows, choose a B-tree, or separate values from keys.

Twice the data taking about 12 times as long is a cliff, not linear growth: the hash table stopped fitting in memory and the operator started spilling to disk.

Memory per distinct key and the number of partitions, then skew: one hot key gives one task most of the work.

Reduce state per key, pre-aggregate before the shuffle, salt hot keys, or raise memory or the partition count so each partition fits. Or choose a sort-based plan, whose cost degrades smoothly instead of falling off a cliff.

Sort-based aggregation has a lower peak speed.

Pages end up about 69% full (about 45% space overhead), and every insert writes a random page, inflating the working set.

Inserts append at the right edge and pages fill completely, but the last page and its latch become a hot spot that limits concurrency.

Time-ordered keys for write-heavy tables. If concurrent inserts contend on the hot page, prefix the key with a small shard number so there are several right edges.

You have converted fragmentation into contention.

This is an interval-overlap join, which a one-dimensional sorted structure cannot answer directly, so the engine falls back to comparing everything with everything.

Divide time into fixed bins and copy each contract into every bin it touches; each is copied about (mean length ÷ bin width) + 1 times. With 10-day contracts and 5-day bins, about 3 copies. Then equi-join on the bin and filter for exact overlap.

Narrow bins mean more copies; wide bins mean more false candidates to filter. Also cluster the events table by time, so file pruning works.

The engine fully sorted the input, O(n log n) with memory proportional to the input, hence the spill, when the question needs only 10 items.

A bounded heap of 10: O(n log 10) time, O(10) memory, and an exact answer. If the engine cannot plan that, aggregate by depot first (there are few depots), then take the top 10.

Before reaching for approximation, restrict the question.

A stage takes as long as its slowest task. The range boundaries came from a poor sample, so one range received about ten times its share of the data.

Take a bigger sample, enough to resolve the keys near the boundaries; split ranges that hold a single hot key (sort by a secondary key, or salt it); and measure partition sizes before sorting.

Sampling costs a pass over the data, or a fraction of it.

Runs: 1 TB ÷ 8 GB = 128. The merge fan-in is bounded by memory ÷ efficient read size, 8 GB ÷ 128 KB, so tens of thousands are possible and only 128 are needed: one merge pass.

Total I/O is about 4 TB (read and write for run generation, then again for the merge). At 2 GB/s that is about 2,000 s, roughly 33 minutes.

A loser tree for the merge, and normalized keys that compare with a plain memcmp. Do not tune the number of passes; there is only one.

Invertible: O(1) state.

Not invertible. Use a monotonic deque on one thread, or one-minute panes in a distributed engine, combining 30 panes per output.

Holistic: an exact answer needs memory proportional to window × cardinality, which is how such jobs run out of memory. The only bounded answer is a sketch, with its error.

The deque needs ordered, single-threaded access. Panes cost O(window ÷ slide) per output, but parallelize and tolerate out-of-order data.

Exact sets cost about 200 million × 16 bytes = 3.2 GB per day per combination of dimensions, multiplied by every combination.

One HyperLogLog per (day, dimension combination): 12 KB each, with 0.81% error. Retries are harmless because the sketch is idempotent. Weekly and monthly numbers are merges of the stored daily sketches, exact under union, so the error does not grow with the period.

Store sketches, not estimates: summing daily estimates would count returning visitors many times.

Questions like "visitors who saw both A and B" are intersections, where HyperLogLog's error can exceed the answer: pay for Theta sketches, or keep raw data for those queries. And a new dimension cannot be added later without the raw data.

Without a filter, 40% of lookups pay about 100 µs for nothing. A Bloom filter at 10 bits per key (1% false positives) removes 99% of that, saving about 0.4 × 99 µs ≈ 40 µs per lookup on average. Memory: 1.25 GB per billion keys.

If files are immutable, an XOR or ribbon filter saves about 15% more memory at no real cost, since compaction rebuilds filters anyway. Use a blocked layout so a probe costs one cache miss. If keys are deleted often from mutable files, consider a cuckoo filter, accepting that inserts can fail.

If most lookups found their key, the filter would be pure overhead.

Space-Saving or Misra-Gries with, say, 10,000 counters, a tiny fraction of 100 MB. The error is at most N / k = 10¹⁰ / 10⁴ = 10⁶ events per counter.

No item with more than a million views can be missed, but the order among the survivors is reliable only where their true counts differ by more than the error.

Show the list without exact rank numbers, or make a second pass with exact counters for just the candidates. Count-Min with a heap also works, but is larger and probabilistic.

Counting is not idempotent, so deduplicate retried events upstream.

No. Quantiles do not merge from quantiles. Shard A with p99 = 100 ms over 1,000 requests and shard B with p99 = 20 ms over 9,000 have a combined p99 anywhere between 20 and 100 ms; their average means nothing.

Store a mergeable digest per minute and merge upwards.

t-digest if tail accuracy at p99 or p99.9 matters and an empirical guarantee is acceptable; KLL if you need a provable rank error; fixed-bucket histograms are the cheapest mergeable option, but only as good as their bucket boundaries.

All pairs is about 10¹⁴ comparisons.

A 128-value MinHash signature per document (similarity error about 1/√128 ≈ 9%), then LSH banding with, for example, b = 16 bands of r = 8 rows (threshold about 0.71) to produce candidate pairs, then verify each candidate exactly.

Pairs with 0.9 similarity are found with probability about 0.9999; pairs at 0.6, much less often. Some borderline duplicates will be missed: choose b and r from the similarity you care about.

This is the one structure in the family whose error silently changes the output, so measure recall on a labelled sample.

One bitmap per value: 6 × 5·10⁹ bits = 3.75 GB for status, but 2,000 × 5·10⁹ bits = 1.25 TB for depot.

Each bitmap is split into chunks of 65,536 rows. Sparse chunks, with fewer than 4,096 set rows, are stored as 16-bit arrays; dense chunks as 8 KB bitmaps. Space becomes proportional to the number of rows: about 5·10⁹ × 16 bits = 10 GB for depot, while status (dense) stays near 3.75 GB.

Word-parallel AND and OR, with popcount for counts.

The table is immutable, so indexes are rebuilt with compaction; new rows go to a delta that the rebuild merges.

No in-place updates, and build time. Chunks near the 4,096 boundary waste some space.

Coordination, not computation: by the Universal Scalability Law, throughput falls past a peak number of threads.

Profile cache-coherence events (for example with perf c2c) and look for a global counter, a shared queue's head and tail, or a reader-writer lock.

1. Partition by a hash of the key into single-writer shards, so the index needs no lock.
2. Hand events to the shards through single-producer, single-consumer rings, with head and tail on separate cache lines and batched publication.
3. Replace the global counter with padded per-thread counters, summed when read.

If each cache-line transfer takes 70 ns, a shared counter caps out near 14 million increments per second for the whole machine, however many threads you add.

Sharding is limited by skew (a hot key pushes one shard to 100%), and queries across shards need a merge. Check by fitting the scalability curve before and after: the coherency term should drop to near zero.

A persistent map (for example a hash array mapped trie). Writers build new versions by copying the path to the root, 5 or 6 nodes of about 256 bytes each for a billion entries, and publish with one compare-and-swap on the root. Readers load the root once and need no locks and no writes, so read throughput scales with cores. Reports hold on to an old root, which gives the 02:00 snapshot for free.

For the writer, 2–10× slower and larger than a mutable map, and garbage you must collect.

Epoch-based reclamation, or a garbage-collected language. Alert on the age of the oldest active reader: one stalled reader blocks reclamation, and memory grows without bound.

With a single thread and no need for snapshots, a plain mutable map wins.

A collector blocked by its slowest reader.

Vacuum cannot remove row versions newer than the oldest open snapshot, so a long-running or idle-in-transaction session blocks it.

Expiring snapshots keeps every file reachable from a retained snapshot, so a long retention window or a pinned reader keeps old files alive.

Find the oldest open transaction or snapshot, set statement and idle-in-transaction timeouts, shorten retention to what audit actually needs (for example 168 hours), and alert on the age of the oldest snapshot.

Shorter retention means less time travel and less slack for slow jobs.

500,000 items per second is modest. An uncontended lock costs about 20 ns, so even a plain mutex spends about 500,000 × 20 ns = 10 ms per second on the lock, roughly 1% of one core. Four producers add contention, but not enough to reach the knee.

A mutex, because it is simpler. Move to a multi-producer ring buffer, with fetch-and-add to claim slots, only if profiling shows time spent waiting for the lock.

Head and tail on separate cache lines; depth from Little's Law (500,000 × 20 ms of backlog = 10,000, rounded up to 16,384); a full ring means backpressure.

Lock-free buys predictability under preemption, not throughput. Wait-free slot claiming is the only option that bounds tail latency.

With skew, most operations hit a few bins. Lock striping (say 16 segments) or per-bin compare-and-swap then concentrates contention on one stripe or one cache line. The design assumed uniform keys. Padding will not help: the problem is the data, not the layout.

1. Split hot keys across several sub-entries and combine them on read (salting).
2. Make reads of hot keys write nothing, using immutable or versioned values.
3. Route hot keys to dedicated single-writer shards.
4. Use per-core counters for aggregate values.

Fit the scalability curve with uniform and with skewed keys; the contention term should jump for the skewed case.

1. Min/max statistics on the timestamp prune files, if the data is clustered by time. Cliff: unclustered data prunes nothing.
2. A Bloom filter per file on the tracking ID at 1% false positives. Cliff: filters too large for memory, or mistyped IDs hitting the SSD.
3. A sparse index with 8,192-row granules narrows to one granule. Cliff: the wrong granule size.
4. A block scan reads about 8,192 rows.

25,000 files; 7 selected by time; about 1.06 expected after the Bloom filters; one granule. About 8,192 rows examined out of 5 billion.

Every stage errs only towards "maybe", so no result is lost.

Keep filters and indexes resident; a lookup then costs one or two SSD page reads.

The merge policy decides how many sorted runs a read must consult and how often each byte is rewritten.

Leveled merging keeps few runs per level, so reads are cheap but each byte is rewritten tens of times. Tiered merging rewrites less, but reads must check more runs.

With reads 20× writes, choose leveled (or a hybrid), with a Bloom filter per run to cut read cost further. Watch the collector: old files can be deleted only when the slowest reader has finished with them.

Merging falls behind, runs pile up, and read latency climbs without warning.