Lab Notebook — Reproducible Benchmarks & Latency Numbers

Question

How long does it take to read one byte from each level of the memory hierarchy on a modern server?

Setup

Numbers are typical for an x86-64 cloud VM circa 2024 (Skylake-class CPU, 3 GHz, NVMe SSD, 25 Gbit network). Latency varies with hardware; ratios are stable.

Readings (ns)

Takeaway

Cache locality dominates algorithmic complexity for small n. A well-laid-out array beats a smart tree of pointers up to 10,000 elements because the array never misses cache; the tree pays L2 / L3 / RAM penalties on every pointer chase.

Question

How deep does a B+tree get for a billion-row index?

Setup

Each internal node holds 200 keys (typical for 4 KiB pages with 8-byte keys + 8-byte child pointers). Each leaf holds rows. Depth = ⌈log_b(n)⌉ + 1.

Readings (levels)

Takeaway

B-trees stay shallow because of the wide fan-out. A binary tree at 10 million rows is 24 levels deep; the B+tree is 4. That's the difference between 24 disk seeks and 4 — the order-of-magnitude that makes databases feasible.

Question

Given m bits per element and k hash functions, what false-positive rate do you get?

Setup

Standard Bloom filter formula: FPR ≈ (1 − e^(−kn/m))^k, with optimal k = (m/n) ln 2. Numbers below assume optimal k.

Readings (% false positive)

Takeaway

Doubling the bits-per-element roughly squares the FPR. Cassandra and RocksDB use 10 bits/elt (~1% FPR) by default. Higher precision is rarely worth it: the cost of the rare false positive is one extra disk read.

Question

How many probes does an open-addressing hash table take per lookup as load factor α rises?

Setup

Linear probing with random hashing. Expected probes per successful lookup ≈ ½(1 + 1/(1−α)). Numbers below are mean probes for a successful lookup.

Readings (probes)

Takeaway

Resize before α crosses 0.75. Open-addressing tables go unstable in their tail, not their mean — at α = 0.9 the p99 of a probe sequence is well into the dozens. Robin-hood hashing softens the tail; it does not move the wall.

Question

How many SSTables does a point lookup touch in an LSM tree, with and without bloom filters?

Setup

Worst case: N levels means N SSTable lookups. With bloom filters at FPR p, expected disk reads ≈ p × (N − 1) + 1.

Readings (avg disk reads)

Takeaway

Bloom filters are not optional for LSM point reads. They convert what would be 7-10× read amplification into ~1 disk read on the average path, at the cost of ~12 bits/key in RAM. RocksDB enables them by default for exactly this reason.

Question

How much does each modern compressor reduce a 1 MB JSON document, and at what speed?

Setup

Squash benchmark v0.7, x86-64, default level for each. JSON corpus from the Squash dataset. Numbers are MB/s for compress and decompress.

Readings (mixed)

Takeaway

For real-time encode (logs, RPC bodies), zstd is the clear winner — same ratio as gzip, 5x encode speed, 4x decode. Brotli only wins for static web assets where you encode once and decode billions of times.

Question

How much smaller is a Protobuf message vs the equivalent JSON for typical record shapes?

Setup

Compared on five common shapes: a payments record, an analytics event, a user profile, a search hit, a config blob. Sizes are uncompressed.

Readings (% of JSON)

Takeaway

25–45% reduction is typical. Small numeric values benefit most (varint encoding); deeply nested optional fields benefit less. After gzip, the gap narrows considerably — gzipped JSON is often within 10% of gzipped Protobuf. Protobuf still wins on parse cost and schema discipline.

Question

How much smaller is the same data in a columnar format with appropriate encodings?

Setup

Same 1 GB time-series table (timestamp, sensor_id, value, tag). Stored in CSV, Parquet+Snappy (default), Parquet+ZSTD, ORC. ClickBench-style measurements.

Readings (MB on disk)

Takeaway

Columnar formats win by storing each column contiguously and applying type-aware encodings (RLE, delta, dictionary) before the entropy coder runs. The 10× edge over compressed CSV is why every analytics warehouse — BigQuery, Snowflake, ClickHouse, Redshift — is column-oriented.

Question

How much of a JSON payload is structural overhead (keys, braces, quotes, commas) for typical small rows?

Setup

Five representative rows of varying field count and value type. "Value bytes" is the sum of value lengths; "structural" is everything else.

Readings (% structural)

Takeaway

A "JSON event" is 50-70% braces and key names. This is why MessagePack, CBOR, Avro and Protobuf can shrink small payloads dramatically — the field tag is a single byte, not a quoted string. Compression flattens this advantage; uncompressed wires do not.

Question

How does mean wait time grow as utilisation ρ approaches 1?

Setup

Standard M/M/1 result: mean wait W = (1/μ) × ρ/(1−ρ). Below: ρ vs the multiplier on baseline service time.

Readings (× service time)

Takeaway

Aim for 60–70% utilisation for latency-sensitive services. The (1−ρ) denominator makes the curve hyperbolic past 0.9. A "well-utilised" 95% server is in the latency death zone.

Question

If you fan out a query to N parallel workers and wait for all, how does the system's p99 latency change?

Setup

Each worker has independent latency with a heavy-tailed distribution (Weibull-like, p99 ≈ 5× p50). System latency is the max of N samples.

Readings (× single-worker p50)

Takeaway

In fan-out, the tail dominates. Mitigations from Dean & Barroso 2013: hedged requests (fire two, take the first), bounded latency (timeout and partial result), tied requests (cancel the slow one when the first returns). Without them, p99 of the system explodes.

Question

If a fraction s of work is inherently serial, how much speedup can N parallel cores give you?

Setup

Amdahl 1967: speedup = 1 / (s + (1−s)/N). Below: speedup at N = 16, 64, 256, ∞ for typical serial fractions.

Readings (× speedup)

Takeaway

Adding cores past Amdahl's ceiling only burns money. The bigger the system gets, the more important the serial 1-5% becomes — locks, cross-shard coordination, leader-only operations. The optimisation that pays at scale is removing the serial fraction, not adding cores.

Question

How much does false sharing cost when two cores update independent variables that happen to share a 64-byte cache line?

Setup

Microbenchmark: each core does 10⁸ atomic increments on its own counter. "Same cache line" places counters within 64 bytes; "padded" pads each counter to its own line.

Readings (normalised throughput)

Takeaway

Pad hot per-thread state to a full cache line (64 B on x86, 128 B on Apple silicon). Java has @Contended, C++ has alignas(64) std::hardware_destructive_interference_size. The cost of getting it wrong is invisible on a single core and catastrophic at scale.

Question

How many bytes hit disk per byte logically written, by compaction strategy?

Setup

RocksDB with default level-style compaction, ~10 levels, 10× growth factor. Numbers from Facebook's 2016 RocksDB paper and follow-ups.

Readings (× write amp)

Takeaway

Choosing between B-tree and LSM is choosing what to amplify. B-tree: low write amp, higher random I/O. LSM: high write amp, sequential I/O — perfect for SSDs. Universal compaction (used by ScyllaDB) trades space for write amp.

Question

How does storage cost change as you add replicas or switch to erasure coding?

Setup

Per-byte storage overhead for each scheme. Durability target: probability the data is lost in a year given typical disk AFR ~1%.

Readings (% of raw bytes)

Takeaway

Erasure coding gives more durability than 3× replication at half the storage cost. The trade is CPU on writes (encoding) and slower repair (decode N shards to rebuild one). For warm/cold tiers EC dominates; for hot reads 3× replication still wins on tail latency.

Question

Given a drive's DWPD (drive writes per day) rating, how does database write amplification translate into lifetime years?

Setup

Modern enterprise SSD: 1.92 TB capacity, 1 DWPD over 5-year warranty. "Effective DWPD" = host writes ÷ capacity, with the database's write-amp factor.

Readings (years to wear out)

Takeaway

On write-heavy LSM workloads, drive endurance — not capacity — sizes the cluster. Buy 3 DWPD drives or pre-shrink write amp with universal compaction. The hidden cost of "we're replacing drives every year" is one of the strongest arguments for tuning compaction.

Question

For a TCP connection with window W and round-trip time R, what is the maximum throughput?

Setup

Throughput ≤ W / R. Below: max throughput at common RTTs for typical windows. The default Linux TCP receive window is auto-tuned up to 6 MB.

Readings (Mbps)

Takeaway

Throughput on long-fat pipes is window-bound, not bandwidth-bound. Confirm receive-buffer auto-tuning is on (it is by default on Linux ≥ 2.6.17) and consider BBR for high-RTT high-bandwidth paths. The classic "my 1 Gbps link only does 50 Mbps" story is almost always a window problem.

Question

How much does each TLS variant cost in round trips and milliseconds on a 50 ms RTT link?

Setup

Round trips before first application byte. ms = RTTs × 50 ms (the dominant cost). CPU cost not included.

Readings (ms before first byte)

Takeaway

Default to TLS 1.3 everywhere; the cold handshake savings alone are worth the migration. QUIC (HTTP/3) folds the transport handshake into the TLS handshake — one round trip instead of two — which is why CDN providers default to it on lossy networks.

Question

How many concurrent in-flight requests can a single client maintain?

Setup

Browser-default behaviour against a single origin. Numbers reflect Chrome / Firefox 2024 settings.

Readings (concurrent streams)

Takeaway

HTTP/2 multiplexing eliminated the "six connections per origin" hack browsers used for a decade. HTTP/3 fixes the remaining issue: a packet loss in one HTTP/2 stream blocked all the others because TCP delivered bytes in order. QUIC streams are independent.

Question

What round-trip latency floor does the speed of light impose between regions?

Setup

Great-circle distance × 2 ÷ 200,000 km/s gives the theoretical floor. Real RTT is typically 1.3-1.5× this due to non-direct fibre paths.

Readings (ms RTT)

Takeaway

No software optimisation can beat physics. A user in Sydney hitting a US-east API will see at least 200 ms before any code runs. Multi-region strategies — read replicas, edge compute, anycast — exist because of this floor, not despite it.

Question

Under a Zipf-distributed access pattern, what hit ratio does a cache of size k achieve out of N keys?

Setup

Zipf with α = 1.0 (typical for web traffic). Hit ratio = sum of probability mass for the top-k keys, ≈ H(k)/H(N) where H is the harmonic number.

Readings (% hit)

Takeaway

A cache holding 1% of the keyspace catches half the traffic for typical Zipf-distributed access. This is why CDNs work — most users want a small popular subset. The long tail is real, but it is not the bill.

Question

On a real workload, what hit ratio does each eviction policy achieve at the same cache size?

Setup

ARC and W-TinyLFU benchmarks from the Caffeine project, search trace, cache size = 1% of unique keys.

Readings (% hit)

Takeaway

Modern admission policies (W-TinyLFU, used by Caffeine) close ~70% of the gap between LRU and the optimal Belady oracle. Free wins for any cache that's big enough to matter. The implementation tradeoff is some metadata per entry — usually 2-4 bits.

Question

How does adding a regional cache between edge and origin change the origin request rate?

Setup

Each layer's hit ratio multiplies. Cloudflare Tiered Cache and similar architectures from Fastly, AWS CloudFront.

Readings (% origin load)

Takeaway

Tiered caching is multiplicative. The edge catches the easy 90%; the regional catches half of what the edge missed; the result is a 100× origin offload. CDN providers price tiered cache as a premium feature for exactly this reason — it is the largest single cost lever for high-traffic sites.

Question

How much latency does a quorum write add over a single-node write?

Setup

Paxos / Raft both require a round trip from leader to a majority of followers. Numbers below assume 2 ms intra-AZ, 4 ms cross-AZ in a 3-node, 3-AZ cluster.

Readings (ms write latency)

Takeaway

Strong consistency costs at least one cross-zone RTT per write. Multi-region strong consistency costs at least one cross-region RTT — typically 80-200 ms. Designs like Spanner buy back some of this with TrueTime; most systems accept the cost or relax to eventual consistency.

Question

How does async replication lag behave as the primary approaches its write capacity?

Setup

Same M/M/1 dynamics as exp 06, applied to the WAL streaming pipeline. Lag scales as ρ/(1−ρ) once the replica is the bottleneck.

Readings (s lag)

Takeaway

Replication lag is a leading indicator of primary saturation. Alert at 5 seconds; page at 30. The fix is almost never "make replication faster" — it is "shed load from the primary" (cache, batch, async writes).

Question

How well-synchronised are clocks across a fleet?

Setup

Typical observed skew between independent servers, by sync method.

Readings (ms skew)

Takeaway

Trusting wall-clock time across servers is a bug. Use logical clocks (Lamport, vector) or hybrid logical clocks (Cockroach) for ordering. If you must use wall-clock, allow at least 30 ms of skew, mark events as "happened within a window," and never rely on millisecond-precise causality.

Question

What downtime budget does each common SLO actually allow?

Setup

Allowed downtime per quarter (90 days) for each availability target.

Readings (min/quarter)

Takeaway

Each extra nine costs roughly 10× the engineering. Pick SLOs by user impact, not aspiration. Most consumer products live happily at 99.9%; payments and healthcare push for 99.99%; only telcos and stock exchanges genuinely need five-nines architectures.

Question

How many unique time-series do common label-set patterns create?

Setup

Each combination of label values creates a distinct time-series. Prometheus / Mimir scrape memory grows roughly linearly in series count.

Readings (distinct time-series)

Takeaway

Label values must come from a closed, small set. user_id, request_id, session_id are forbidden as labels — those belong in logs or traces, never metrics. Prometheus reference: target ≤ 10M series total per instance.

Question

What does logging cost in commercial SaaS observability platforms?

Setup

Datadog Logs at standard pricing (mid-2024). Average log line ~250 bytes. 30-day retention. Volumes per service per day.

Readings ($ / month)

Takeaway

Sample. Tier hot vs cold logs. Move debug-level off the hot path entirely. The "log everything, forever" default at scale is a six-figure mistake. Self-hosted alternatives (Loki, Vector + S3) cost 20-50× less but require operational effort.

Question

For a service handling N requests, what fraction of "interesting" traces does each sampling strategy keep?

Setup

Imagine a 1M-request hour, with 1% being "slow" (>p99) and 0.1% being "errored". Sampling fractions kept by each strategy.

Readings (% of total traces)

Takeaway

Head-based sampling is cheap but loses tail and error events. Tail-based sampling sees the whole trace before deciding to keep it — much more useful but requires a buffering layer. Production traces ship with adaptive: keep all errors, all slow, plus a fixed % of fast happy-path.

Question

For a password of given alphabet and length, how long does brute force take at 1 trillion guesses/second?

Setup

Modern hashcat on a single 8×RTX-4090 rig achieves ~10¹² SHA-256 guesses/second (~10⁹ for bcrypt at cost 12). Time to exhaust the keyspace, in years.

Readings (years to exhaust)

Takeaway

Length beats character variety: a four-word passphrase beats a "Tr0ub@dor" type 10-char password by orders of magnitude. Use a password manager, generate 16+ chars or 5+ diceware words. Use bcrypt / Argon2 with cost ≥ 12 to slow the attacker by ~1000×.

Question

How many bytes does each TLS cert-chain configuration add to the first round trip?

Setup

Server certificate plus its chain in the ServerHello. RSA-2048 cert ≈ 1.5 KB; ECDSA P-256 cert ≈ 0.5 KB. Initial congestion window is typically 10 segments × 1460 bytes ≈ 14.6 KB.

Readings (KB cert + chain)

Takeaway

A bloated cert chain crosses the initcwnd boundary and triggers an extra round trip on the very first connection. Use ECDSA where possible (5× smaller). Strip unnecessary intermediates from your chain. Test with ssllabs.com.