Techniques
Production idioms — the smart tricks you weave into algorithms and systems. Exponential backoff, idempotency keys, reservoir sampling, Snowflake IDs, leases, and more.
Grouped by category · 63 entries
Reliability
6Grow retry intervals exponentially and add randomization so clients don't synchronize their retries.
Calling any unreliable downstream (network, third-party API (Application Programming Interface), flaky DB). Without jitter, a thundering-herd of clients all retry at the same moment after an outage.
AWS SDK clients retry with full jitter: sleep = random(0, base × 2^attempt). Both Google and Stripe SDKs follow the same pattern.
def retry(fn, max_attempts=5, base_ms=100, cap_ms=10_000):
for attempt in range(max_attempts):
try:
return fn()
except TransientError:
if attempt == max_attempts - 1:
raise
backoff = min(cap_ms, base_ms * 2 ** attempt)
jitter = random.uniform(0, backoff)
time.sleep(jitter / 1000)Caller sends a unique key with each request; server dedupes on it so retries don't double-charge.
Any non-idempotent mutation that might be retried: payments, signups, order creation. Network errors mid-flight are normal; you don't know whether the server committed.
Stripe's `Idempotency-Key` header. Server stores key → response for 24h; second request with the same key returns the cached response instead of re-running the work.
If the first request hasn't returned by some threshold (p95, the 95th percentile latency), fire a second one and take whichever finishes first.
Tail-latency-sensitive reads where the long tail is wasted (e.g., a single slow replica). Costs ~2x reads on the tail but slashes p99 (99th percentile) latency.
Google's BigTable + Spanner read clients hedge to a second replica after ~95th percentile of recent latency. Used internally by search to keep query latency consistent.
Bound the total time spent retrying, not the number of attempts. Each retry costs from the same budget.
Any call inside a larger request that itself has a timeout. Counting attempts is the wrong unit: 5 retries with backoff can blow past your caller's 200ms service level agreement (SLA).
gRPC's context deadlines. Each downstream remote procedure call (RPC) inherits a deadline; retries must finish before it expires. Envoy and Istio implement the same with a `x-envoy-upstream-rq-timeout-ms` header.
Track failures from a dependency; once they exceed a threshold, open the circuit and fail fast for a cool-down period.
Calling a dependency that can degrade your own health if you keep retrying. Without a breaker, your threads pile up on a slow call and the whole service stops responding.
Netflix Hystrix popularized the pattern (now Resilience4j in the JVM world). Envoy / Istio have it built into the service mesh. Pattern: closed → open after N failures → half-open after timeout → closed if probe succeeds.
state = "CLOSED"; failures = 0
def call(fn):
if state == "OPEN" and now() < open_until: raise Tripped()
if state == "OPEN": state = "HALF_OPEN"
try:
result = fn()
failures = 0; state = "CLOSED"
return result
except:
failures += 1
if failures >= THRESHOLD:
state = "OPEN"; open_until = now() + COOLDOWN
raiseWhen a non-critical dependency fails, return a useful partial response instead of erroring the whole request.
Composite responses where some fields are nice-to-have. Recommendations down → show the page without them. Search facets down → return results, drop facets.
Amazon's product page shows the product even if reviews, recommendations, or 'also bought' services time out. Each component has a fallback (empty list, cached snapshot, or skeleton).
Approximation
4Probabilistic set membership in tiny memory. No false negatives; tunable false-positive rate.
When 'might be there' is good enough and you want to short-circuit an expensive lookup. Reading a row that doesn't exist is wasted input/output (I/O); a bloom filter says 'definitely not, skip it.'
Cassandra puts a bloom filter in front of every SSTable to skip reads that would miss. Chrome historically used one for the malicious-URL (Uniform Resource Locator) list (millions of URLs, ~2MB).
Estimate cardinality (unique count) of a massive set using a few KB of memory and a small error margin.
Counting unique visitors, distinct query terms, or unique IPs across billions of events. Exact counts require O(n) memory; HyperLogLog (HLL) gets you within ~1% in O(log log n).
Redis's `PFADD` / `PFCOUNT` commands. Used by ad networks for daily unique reach, by BigQuery for `APPROX_COUNT_DISTINCT`.
Estimate frequency of items in a stream using sublinear memory; never underestimates.
Heavy-hitter detection in streams: 'which user is making the most requests right now?' Real exact counters would explode memory at internet scale.
Used in Cloudflare's distributed denial-of-service (DDoS) detection, in Twitter's heavy-hitter analytics, and as a building block for top-K queries on streams.
Sample k items uniformly at random from a stream of unknown (and unboundedly large) length.
When the dataset is too large or unbounded to hold in memory, and you need a representative random subsample. Logs sampling, A/B testing of streaming events, telemetry.
Distributed tracers (Jaeger, OpenTelemetry) use reservoir sampling to keep a representative slice of traces under a fixed memory budget.
def reservoir(stream, k):
sample = []
for i, item in enumerate(stream):
if i < k:
sample.append(item)
else:
j = random.randint(0, i)
if j < k:
sample[j] = item
return sampleIdentifiers & Ordering
564-bit unique IDs: [timestamp][machine-id][sequence]. Time-ordered, distributed, no central coordinator.
Need globally unique IDs that are also roughly sortable by creation time, across many shards/machines. Beats UUIDs for index locality (better B-tree fanout).
Twitter coined Snowflake in 2010 for tweet IDs. Discord uses a variant for messages. Sonyflake (Sony) and Instagram's ID gen are spiritual descendants.
// 41 bits timestamp | 10 bits machine | 12 bits sequence
long id = ((now - EPOCH) << 22) | (machineId << 12) | (sequence++ & 0xFFF);Timestamp-prefixed UUID — sortable, monotonic, still 128-bit and globally unique.
When you want UUID's uniqueness guarantees but also need DB index locality. UUID v4 randomness wrecks B-tree caches; v7 keeps recent writes hot.
Postgres 16 partitioning works far better with UUID v7 keys than v4 because adjacent inserts land on the same page. Many ORMs (Object-Relational Mappers like Prisma, Drizzle) recommend v7 for new tables.
Each node maintains a counter; events carry a vector of counters that captures partial causal ordering.
Detecting concurrent updates in a distributed store. Two versions with incomparable vectors are concurrent (a conflict); one strictly dominates the other if its vector is >= in every position.
Riak and DynamoDB use vector clocks (Dynamo paper). When you `GET` a key and see two versions, you reconcile — same primitive amazon.com uses for shopping cart merge.
Single counter per node, advanced to max(local, received) + 1 on every message. Gives total ordering of causally related events.
When you need 'happens-before' ordering across distributed events but don't need to detect concurrency (just to break ties consistently).
Foundational primitive behind Paxos, Raft, and many conflict-free replicated data types (CRDTs). Cassandra uses Lamport-style timestamps for last-write-wins reconciliation.
A dedicated service hands out strictly increasing 64-bit IDs. Simpler than Snowflake when you don't need offline generation.
URL (Uniform Resource Locator) shortener short codes, order numbers, anywhere you need dense sequential IDs (not random). Trade-off: single point of contention unless you shard it.
Bitly's hash-vs-counter hybrid. Internally, many systems pre-allocate ranges (e.g., 'this server reserves IDs 1M-2M') so the central service is hit infrequently.
Throughput & Flow
6When a downstream component is slow, signal upstream to slow down (don't just buffer and OOM).
Anywhere a producer can outrun a consumer: streams, queues, network sockets, UI event loops. Without backpressure, slowness becomes outages.
Node.js streams expose `.write()` returning false; Reactive Streams (RxJava, Project Reactor) make backpressure first-class via `request(n)`. Kafka consumers use offset commits as natural backpressure.
Coalesce many small operations into one large one to amortize fixed per-request overhead.
Remote procedure call (RPC) overhead dominating real work. Network round trips, DB inserts, S3 puts, log writes. Trade latency (wait for batch to fill) for throughput.
Kafka producer's `linger.ms` waits up to N ms to fill a batch. DynamoDB's BatchWriteItem can do 25 puts per call. GraphQL's DataLoader pattern is request-scoped batching.
Wait until a flurry of events stops for N ms, then act once. Drops everything in between.
User input that you only want to act on once they pause — search-as-you-type firing a query, window resize firing a re-layout.
Search input firing the API (Application Programming Interface) call 300ms after the last keystroke. React libraries use `useDebouncedValue` for this. Different from throttle (throttle still fires periodically).
function debounce(fn, ms) {
let t;
return (...args) => {
clearTimeout(t);
t = setTimeout(() => fn(...args), ms);
};
}Emit at most once per N ms regardless of how often it's called. Unlike debounce, never goes silent.
Scroll handlers, mouse-move analytics, anything that fires constantly where you want a steady downsampled signal rather than 'wait for stop.'
Scroll-based animations throttled to 60fps (16ms). Analytics 'on page heartbeat' fired at most every 5s. Rate-limiting outbound API (Application Programming Interface) calls.
Bucket refills at rate R; each request takes one token. Allows controlled bursts up to bucket size.
Rate limiting where occasional bursts are fine. Most general-purpose throttle: e.g., 100 req/min average, allow 30 in a burst.
AWS API Gateway, Stripe, Cloudflare all use token bucket variants. Linux's tc traffic shaper uses it for QoS.
class TokenBucket:
def __init__(self, capacity, refill_per_sec):
self.capacity = capacity
self.tokens = capacity
self.refill = refill_per_sec
self.last = time.time()
def allow(self):
now = time.time()
self.tokens = min(self.capacity,
self.tokens + (now - self.last) * self.refill)
self.last = now
if self.tokens >= 1:
self.tokens -= 1
return True
return FalseRequests enter a queue, processed at fixed rate. Smooths out bursts entirely — no spike ever reaches downstream.
When the downstream cannot handle bursts at all (legacy DB, third-party with strict queries per second (QPS)). Token bucket allows bursts; leaky bucket guarantees a smooth rate.
Outbound webhook delivery: enqueue, drain at N per second so the receiver isn't slammed. Many billing systems use it for outbound API (Application Programming Interface) calls to providers.
Coordination
6Grant time-bounded exclusive ownership. Holder must renew before expiry; if it dies, the lease auto-releases.
Leader election, distributed locks, work assignment. Avoids 'zombie owner' problems where a crashed node holds a lock forever.
Kubernetes leader election (controllers all try to grab a lease in a ConfigMap, renew every few seconds). Chubby and etcd are built around lease primitives.
Write to W replicas, read from R replicas, with W + R > N. Guarantees any read sees at least one of the writes.
Tunable consistency in a replicated store. Lower W and R = faster + cheaper but eventual; higher = stronger consistency but slower and less available.
Cassandra and DynamoDB expose read/write consistency per request. Spanner and CockroachDB use Paxos/Raft (a flavor of quorum) for every write.
On a quorum read, if replicas disagree, write the freshest version back to the stale ones in the background.
Eventually-consistent stores where you tolerate some stale replicas but want them to converge without a separate sweep process.
Cassandra and Dynamo do this on every read above CL.ONE. Combined with anti-entropy, replicas converge even without explicit reconciliation.
Background process that compares replicas using a Merkle tree of data and ships only the differing ranges.
Keeping replicas in sync when read-repair alone won't reach cold data. Catch-up after a node was offline for a long time.
Cassandra's nodetool repair builds Merkle trees per range. DynamoDB does similar. Riak and Bitcoin/Ethereum P2P sync use the same Merkle-tree-difference trick.
Periodic 'I'm alive' signal. Absence of N consecutive heartbeats means the peer is presumed dead.
Failure detection in any distributed system: cluster membership, load balancers, service mesh. Foundation for failover.
Kubernetes kubelet → control plane heartbeats. ZooKeeper ephemeral nodes are heartbeat-tied. Akka clusters, Cassandra gossip, Redis Sentinel — all heartbeat-based.
Read a value with its version, send update conditional on version unchanged. Server rejects if someone else wrote in the meantime.
Multiple writers to the same row, but contention is rare. Avoids the throughput hit of pessimistic locks; conflicts surface as 'retry the operation.'
DynamoDB's `ConditionExpression`, S3's `If-Match` ETag, HTTP (Hypertext Transfer Protocol) PUT with `If-Match`, Git's push (rejects non-fast-forward). Postgres multi-version concurrency control (MVCC) + SELECT FOR UPDATE NOWAIT is a hybrid.
Concurrency
10Mutual-exclusion primitive: at most one thread holds the lock at a time, serializing access to a critical section.
Any shared mutable state touched by multiple threads where correctness depends on read-modify-write being atomic. Default first reach for senior backends before optimizing.
Java's `synchronized` / `ReentrantLock`, Python's `threading.Lock`, Linux kernel `spinlock_t` and `mutex_t`. The JDK's `ConcurrentHashMap` segments used to be backed by per-segment ReentrantLocks.
private final ReentrantLock lock = new ReentrantLock();
private long balance;
public void deposit(long amount) {
lock.lock();
try {
balance += amount;
} finally {
lock.unlock();
}
}Allow many concurrent readers OR one exclusive writer, but never both — boosts throughput on read-heavy state.
Shared state with read:write ratio greater than ~10:1 and non-trivial critical sections. Wrong choice for short critical sections — the rwlock bookkeeping costs more than a plain mutex.
Java's `ReentrantReadWriteLock` and `StampedLock`, Linux kernel `rwsem`, pthread `pthread_rwlock_t`. Used inside many in-memory caches and the JDK's `ConcurrentSkipListMap` ancestor structures.
private final ReentrantReadWriteLock rw = new ReentrantReadWriteLock();
private Map<String, String> cache = new HashMap<>();
public String get(String k) {
rw.readLock().lock();
try { return cache.get(k); }
finally { rw.readLock().unlock(); }
}
public void put(String k, String v) {
rw.writeLock().lock();
try { cache.put(k, v); }
finally { rw.writeLock().unlock(); }
}Hardware-level atomic instruction: write a new value only if the current value matches expected; otherwise retry.
Single-word updates (counters, flags, single-pointer head/tail) under contention where a mutex's blocking is overkill. Powers nearly every lock-free data structure.
x86 `LOCK CMPXCHG`, ARM `LDREX/STREX`. Java's `AtomicLong`, `AtomicReference`, `LongAdder`. Go's `sync/atomic`. The Linux kernel's `atomic_cmpxchg`.
AtomicLong counter = new AtomicLong(0);
public long incrementAndGet() {
long cur;
do {
cur = counter.get();
} while (!counter.compareAndSet(cur, cur + 1));
return cur + 1;
}Wait on a predicate while holding a lock; another thread signals when the predicate may now be true, atomically releasing and re-acquiring the lock.
Producer-consumer coordination, bounded queues, anything where a thread needs to block until 'state X is true' without busy-waiting.
Java's `Object.wait/notify` and `Condition.await/signal` (used inside `ArrayBlockingQueue`). pthread `pthread_cond_t`. Python's `threading.Condition`.
lock = threading.Lock()
cv = threading.Condition(lock)
queue = []
def consume():
with cv:
while not queue:
cv.wait()
return queue.pop(0)
def produce(item):
with cv:
queue.append(item)
cv.notify()Counter with atomic acquire/release: lets at most N permits be held simultaneously. Generalizes the mutex (N=1).
Bounding concurrent access to a finite resource pool: DB connections, outbound HTTP (Hypertext Transfer Protocol) slots, GPU memory. Also for classic signaling patterns.
Java's `Semaphore`, Python's `threading.Semaphore`, Linux kernel `struct semaphore`. Most JDBC connection pools (HikariCP) use a semaphore-like counter to cap in-flight connections.
Semaphore dbSlots = new Semaphore(10);
public Row query(String sql) throws InterruptedException {
dbSlots.acquire();
try {
return runQuery(sql);
} finally {
dbSlots.release();
}
}Pre-allocated worker threads pull tasks from a shared queue, so you pay thread-creation cost once and bound concurrency.
Server workloads with many short tasks. Default for any JVM service handling requests; avoids the cost and unboundedness of one-thread-per-task.
Java's `ThreadPoolExecutor` and `ForkJoinPool` (which backs `CompletableFuture` and parallel streams). Tomcat / Jetty / Netty all use fixed-size pools. Python's `concurrent.futures.ThreadPoolExecutor`.
ExecutorService pool = new ThreadPoolExecutor(
16, 64, // core, max
60L, TimeUnit.SECONDS,
new ArrayBlockingQueue<>(1000), // bounded queue
new ThreadPoolExecutor.CallerRunsPolicy()
);
Future<Result> f = pool.submit(() -> handle(req));Producers offer work to a fixed-capacity queue; consumers drain it. Bound provides natural backpressure when consumers fall behind.
Decoupling fast producers from slower consumers (log shipping, request handoff, batch ingestion). Unbounded queues are an anti-pattern — they hide backpressure until OOM.
Java's `ArrayBlockingQueue` and `LinkedBlockingQueue` (used inside `ThreadPoolExecutor`). Disruptor's ring buffer at LMAX. Kafka producer's in-memory `RecordAccumulator` queue.
BlockingQueue<Event> q = new ArrayBlockingQueue<>(10_000);
// producer
boolean accepted = q.offer(event, 50, TimeUnit.MILLISECONDS);
if (!accepted) metrics.dropped.inc();
// consumer
while (true) {
Event e = q.take();
process(e);
}Per-thread variable: every thread sees its own copy, eliminating sharing and therefore eliminating the need to synchronize.
Non-thread-safe objects you want to reuse per thread (SimpleDateFormat, Random, request-scoped context). Cheaper than allocating per call, safer than sharing.
Java's `ThreadLocal<T>` / `InheritableThreadLocal` powers SLF4J's MDC, Spring's `RequestContextHolder`, and Hibernate's session-per-thread. JDK's `ThreadLocalRandom` avoids contention on the global `Random` seed.
private static final ThreadLocal<SimpleDateFormat> ISO =
ThreadLocal.withInitial(() -> new SimpleDateFormat("yyyy-MM-dd'T'HH:mm:ss"));
public String format(Date d) {
return ISO.get().format(d);
}Never mutate a shared object; on write, copy it and atomically swap the reference. Readers are entirely lock-free.
Heavily-read, rarely-written shared state: routing tables, config snapshots, listener lists. Writes get expensive (full copy), so it loses if writes are frequent.
Java's `CopyOnWriteArrayList` (used for listener registries in Swing / Spring), `String`, persistent collections in Clojure / Scala. The Linux kernel's RCU is a related pattern.
private volatile Map<String, Route> routes = Map.of();
public Route lookup(String k) {
return routes.get(k); // lock-free read
}
public synchronized void addRoute(String k, Route r) {
Map<String, Route> next = new HashMap<>(routes);
next.put(k, r);
routes = Map.copyOf(next); // atomic publish
}Represent an in-flight computation as a value you can compose, chain, and await — no manual callback threading.
I/O-bound services with many in-flight calls (fan-out to downstreams, parallel DB + cache reads). Lets one OS thread drive thousands of logical operations.
Java's `CompletableFuture` (backed by ForkJoinPool), Python's `asyncio` + `await`, JavaScript's Promises, Rust's `tokio` futures. Netflix's Zuul 2 and gRPC-Java both fan out via CompletableFuture.
CompletableFuture<User> u = async(() -> userSvc.get(id));
CompletableFuture<Profile> p = async(() -> profileSvc.get(id));
CompletableFuture<Response> resp = u.thenCombine(p, Response::new)
.orTimeout(200, TimeUnit.MILLISECONDS)
.exceptionally(ex -> Response.fallback());Distributed Systems
10Leader-based consensus protocol: one elected leader replicates an append-only log to followers; entries commit once a majority quorum acknowledges.
You need a small, strongly-consistent replicated state machine: config store, metadata, leader registry, or coordination. Optimizes for understandability over raw throughput.
etcd (Kubernetes control plane), Consul, CockroachDB's range leases, TiKV, and HashiCorp Nomad all run Raft. Spanner uses Paxos for the same role.
# Raft commit (leader side, simplified)
def append_entries(entry):
log.append(entry)
acks = 1 # self
for f in followers:
if f.replicate(entry, prev_index, prev_term):
acks += 1
if acks > len(cluster) // 2:
commit_index = entry.index
apply_to_state_machine(entry)
return OK
return RETRYTune per-operation consistency by requiring W replicas to ack writes and R replicas to answer reads. If R + W > N, every read overlaps the latest write.
Leaderless Dynamo-style stores where you want to trade latency vs durability per call. N=3, W=2, R=2 is the canonical 'sloppy quorum' default.
DynamoDB, Cassandra (consistency levels ONE/QUORUM/ALL), Riak. Cassandra's LOCAL_QUORUM picks W = ceil(N/2) + 1 within one datacenter to avoid cross-region latency.
Each replica tags writes with a per-node counter map. Comparing two versions reveals causal order, concurrency, or strict dominance.
Leaderless replication where multiple writers may touch the same key. Lets the system detect siblings (concurrent versions) instead of silently dropping one.
Amazon Dynamo (the 2007 paper), Riak, and Voldemort use version vectors. Cassandra skipped them and uses last-write-wins timestamps instead, which is simpler but lossy.
# Compare two vector clocks
def compare(a, b):
a_dominates = all(a.get(n, 0) >= b.get(n, 0) for n in a | b)
b_dominates = all(b.get(n, 0) >= a.get(n, 0) for n in a | b)
if a_dominates and b_dominates: return "equal"
if a_dominates: return "a_after_b"
if b_dominates: return "b_after_a"
return "concurrent" # siblings, app must mergeEach node periodically picks a random peer and exchanges state. Information spreads epidemically in O(log n) rounds with bounded per-node bandwidth.
Membership, failure detection, and cluster metadata where eventual convergence is fine and you want no central coordinator. Scales to thousands of nodes.
Cassandra's cluster membership, Consul's SWIM-based serf layer, Redis Cluster's gossip bus, and HashiCorp Memberlist all use gossip for liveness and config.
A would-be leader acquires a time-bounded lease in a consensus store; it must renew before expiry or lose leadership. Bounds split-brain to one lease window.
You need at-most-one writer or coordinator and can tolerate a short unavailability gap on failover. Safer than ZK ephemeral nodes alone because clocks are bounded.
Chubby (Google's lock service) pioneered this, Kubernetes controller-manager and kube-scheduler elect a leader via a Lease object in etcd, and CockroachDB range leases use it.
Replicas build a tree of hashes over their key ranges; comparing root then children lets them find divergent ranges in O(log n) hops instead of full scans.
Background repair between leaderless replicas after partitions, dropped writes, or hinted-handoff misses. Cheap when divergence is rare.
Cassandra's nodetool repair, DynamoDB's anti-entropy, and Riak active anti-entropy all use Merkle trees. Git's object store uses the same idea for packfile transfer.
Data types whose merge function is commutative, associative, and idempotent, so any two replicas converge to the same value without coordination.
Collaborative editing, offline-first apps, shopping carts, presence counters. When you need multi-writer convergence without server-side conflict resolution.
Redis CRDTs (Enterprise active-active), Riak data types (counters, sets, maps), Automerge / Yjs in Figma and Linear-style editors, Apple Notes sync.
# G-Counter (grow-only CRDT counter)
class GCounter:
def __init__(self, node): self.node = node; self.counts = {}
def inc(self):
self.counts[self.node] = self.counts.get(self.node, 0) + 1
def value(self):
return sum(self.counts.values())
def merge(self, other): # commutative, idempotent
for n, v in other.counts.items():
self.counts[n] = max(self.counts.get(n, 0), v)Coordinator asks all participants to PREPARE; if all vote yes it sends COMMIT, otherwise ABORT. Blocks if the coordinator crashes between phases.
Cross-shard or cross-database atomicity where you control all participants and tolerate the blocking window. Common inside one datacenter.
MySQL XA transactions, PostgreSQL prepared transactions, Spanner's participant leaders run 2PC on top of Paxos groups, MongoDB cross-shard transactions.
If a target replica is down, a healthy node stores the write locally with a 'hint' and forwards it once the target recovers. Keeps write availability high.
Leaderless or multi-master systems where short replica outages should not fail writes. Pairs with anti-entropy for durability if the hint-holder also dies.
Cassandra hinted handoff, DynamoDB sloppy-quorum writes, Riak. Hints typically have a TTL (Time To Live; 3 hours in Cassandra default) before anti-entropy takes over.
Replicas arranged in a chain: writes enter at the head, flow through every link, commit at the tail. Reads served by tail give linearizable results with simple logic.
Storage systems wanting linearizable reads without quorum coordination, willing to pay write latency = sum of hops. Simpler failure handling than Paxos.
Microsoft Azure Storage (the layered DFS), CRAQ (Chain Replication with Apportioned Queries), Hibari, and FAWN. Used in Azure's stream layer at exabyte scale.
Database Internals
8Balanced, fan-out heavy tree where leaves hold sorted keys (and in B+trees, are linked for range scans). Lookup, insert, delete in O(log n).
Default secondary index in nearly every relational database (Postgres, MySQL/InnoDB, SQL (Structured Query Language) Server). Great for point lookups, equality, range, ORDER BY, and prefix matches.
InnoDB clusters the primary key as a B+tree; secondary indexes store primary key as the row pointer. Postgres uses a B+tree (the `btree` access method) as the default index type.
-- Postgres: index on (status, created_at) supports
-- WHERE status = 'open' ORDER BY created_at LIMIT 50
CREATE INDEX idx_orders_status_created
ON orders (status, created_at);Buffer writes in an in-memory memtable, flush sorted runs (SSTables) to disk, then merge them in background compaction passes.
Write-heavy workloads where sequential I/O dominates: RocksDB, LevelDB, Cassandra, ScyllaDB, HBase. Trades read amplification (multiple levels to probe) and space amplification (during compaction) for write throughput.
RocksDB: memtable -> L0 (overlapping SSTables) -> L1..Ln (each level ~10x larger, non-overlapping). Leveled compaction keeps read amp of the LSM (Log-Structured Merge-tree) roughly O(L) levels.
Hash table over a column; O(1) average point lookup, but no order, so no range scans or ORDER BY.
Equality-only workloads on a single key, especially in memory. Redis hashes, Postgres `USING HASH` indexes, Memcached, and join hash tables in query execution.
Postgres `CREATE INDEX ... USING HASH (email)` for `WHERE email = ?` only. A B-tree on the same column also costs O(log n) and adds range support, which is why hash indexes are rare in practice.
Add the columns you SELECT into the index so the query plan never visits the heap. The index alone covers the read.
Read-heavy queries with a stable column list, especially when the table is wide and the heap visit is the expensive part. Postgres `INCLUDE`, SQL Server included columns, MySQL secondary indexes that already carry the PK.
`CREATE INDEX idx ON orders (user_id) INCLUDE (status, total)` lets `SELECT status, total FROM orders WHERE user_id = ?` run as an index-only scan; EXPLAIN shows `Index Only Scan` with zero heap fetches if the visibility map is up to date.
CREATE INDEX idx_orders_user_covering
ON orders (user_id)
INCLUDE (status, total);
-- EXPLAIN: Index Only Scan using idx_orders_user_covering
SELECT status, total FROM orders WHERE user_id = 42;Each write produces a new row version tagged with the transaction id; readers see the version visible to their snapshot. Readers never block writers, writers never block readers.
Any mixed read/write OLTP workload where long analytic reads should not block point updates. Postgres, Oracle, MySQL/InnoDB, and most modern relational engines use some flavor of MVCC.
Postgres stores `xmin` / `xmax` per row tuple. A SELECT under REPEATABLE READ takes a snapshot at statement (or transaction) start; concurrent UPDATEs create new tuples that the snapshot ignores. VACUUM later reclaims dead tuples.
Append every change to a sequential log and fsync before touching the data pages. On crash, replay the log to recover committed work.
Durability is required and random page writes are too slow. Used by Postgres WAL, MySQL redo log, SQLite WAL mode, RocksDB WAL, Kafka log segments, and HDFS edits log.
Postgres: a COMMIT is acknowledged once its WAL records are fsynced to `pg_wal/`. Dirty data pages are flushed lazily at checkpoint. Replication streams the same WAL to standbys.
Persist the result of a query as a real table; refresh on schedule, on demand, or incrementally as base tables change.
Expensive aggregations or joins that are read far more often than the underlying data changes. Dashboards, leaderboards, and OLAP rollups are textbook cases.
Postgres `CREATE MATERIALIZED VIEW daily_revenue AS SELECT day, SUM(total) FROM orders GROUP BY day;` then `REFRESH MATERIALIZED VIEW CONCURRENTLY daily_revenue` nightly. Snowflake and BigQuery offer incrementally maintained variants.
Attach a small probabilistic filter to each SSTable. A point lookup checks the filter first and skips the file if it says 'definitely not present'.
Read paths in LSM (Log-Structured Merge-tree) engines where most lookups miss most files. RocksDB, Cassandra, HBase, and Parquet readers all use bloom filters to cut read amplification.
RocksDB enables a per-SSTable bloom filter by default. With 10 bits per key the false-positive rate is ~1%, so for a 7-level LSM you typically read 1 SSTable instead of 7 on a point GET.
Networking & OS
8Algorithms that decide how fast TCP (Transmission Control Protocol) sends. Loss-based (Reno, Cubic) treat packet loss as congestion; model-based (BBR) measures bottleneck bandwidth and round-trip time (RTT) directly.
Anywhere you tune kernel TCP for high bandwidth-delay-product links (CDN (Content Delivery Network) egress, cross-region replication). Cubic is the Linux default; BBR shines on lossy long-fat networks (LFNs) where Cubic backs off too aggressively.
Google switched YouTube and google.com egress to BBR around 2016 and saw 4-14 percent throughput gains on average across regions, with much larger wins on lossy mobile links. Set with `sysctl net.ipv4.tcp_congestion_control=bbr`.
TLS (Transport Layer Security) 1.2 needs 2 round trips before app data flows. TLS 1.3 collapses that to 1 round trip (1-RTT) for new sessions and 0 round trips (0-RTT) for resumed ones using pre-shared keys (PSK).
Any HTTPS edge where latency matters. Forcing TLS 1.3 on your load balancer typically saves 50-100ms per new connection vs 1.2, more on high-RTT mobile links.
Cloudflare and Fastly default to TLS 1.3 with 0-RTT optional. 0-RTT lets a returning client send a GET inside the first packet, but the server must treat 0-RTT data as replayable, so it is limited to idempotent reads.
Many concurrent streams over a single TCP (Transmission Control Protocol) connection, each with its own flow control. Fixes HTTP (Hypertext Transfer Protocol) 1.1 head-of-line blocking at the HTTP layer but not at TCP.
Browser-facing services serving many small assets, or gRPC backends. One TLS connection per origin instead of 6, which slashes handshake overhead and lets the server prioritize streams.
gRPC is built on HTTP/2 streams. A single client connection can carry thousands of in-flight remote procedure calls (RPCs); the server schedules responses as data is ready. Loss of one packet still stalls all streams (TCP head-of-line) which is why HTTP/3 exists.
HTTP (Hypertext Transfer Protocol) 3 runs over QUIC, a UDP (User Datagram Protocol) based transport with built-in TLS (Transport Layer Security) 1.3, per-stream flow control, and connection migration across IP changes.
Mobile clients on flaky networks, or any service hit by HTTP/2's TCP head-of-line blocking. QUIC streams are independent at the transport layer, so one lost packet only stalls one stream.
YouTube, Facebook, and Cloudflare serve HTTP/3 to ~30 percent of traffic. A phone moving from Wi-Fi to LTE keeps the same QUIC connection (via connection ID) instead of redoing the TLS handshake.
Reuse TCP (Transmission Control Protocol) and TLS (Transport Layer Security) connections across requests instead of opening a new one each time. Avoids the 3-way handshake plus TLS handshake on every call.
Any client making repeated calls to the same host. Without pooling, a Lambda hitting DynamoDB pays ~50ms of handshake per call; with pooling, subsequent calls are sub-millisecond setup.
Node's `http.Agent({ keepAlive: true })`, Go's `http.Transport` (pooled by default), Java's `HttpClient`. AWS SDK v3 reuses HTTPS agents; v2 famously did not, which is why a lot of Lambdas paid hidden handshake tax.
// Node.js: explicit keepAlive
const https = require("https");
const agent = new https.Agent({
keepAlive: true,
maxSockets: 50,
keepAliveMsecs: 30_000,
});
fetch(url, { agent });Nagle's algorithm coalesces small writes to reduce tinygrams. Combined with delayed-ACK on the receiver, it can stall small request/response pairs for ~40ms waiting for the next ack.
Latency-sensitive request/response over TCP (Transmission Control Protocol) with small payloads: RPC (Remote Procedure Call), Redis, database protocols. Set TCP_NODELAY on the socket; almost every RPC library does this by default.
Classic symptom: small HTTP POST shows a 40ms p50 floor that nothing else explains. Cause: client writes header then body in separate calls, Nagle holds the body, server's delayed-ACK waits for more data. `setsockopt(fd, IPPROTO_TCP, TCP_NODELAY, 1)` fixes it.
Readiness-based (epoll, kqueue) or completion-based (io_uring, IOCP) APIs that let one thread watch tens of thousands of file descriptors without a thread per connection.
Any server expecting more than ~10k concurrent connections. Thread-per-connection caps out at the thread count you can schedule; epoll scales to whatever your file descriptor (fd) limit allows.
Nginx, Redis, Node.js (via libuv), and Envoy are all single-threaded event loops over epoll. io_uring (Linux 5.1+) goes further with submission/completion queues shared with the kernel, removing syscalls per op; ScyllaDB and recent Postgres patches use it.
Move bytes from disk to socket without copying through user space. The kernel hands page-cache pages directly to the NIC's DMA engine.
Static file servers, video CDN (Content Delivery Network) origin nodes, Kafka brokers shipping log segments. Removes 2 copies and 2 context switches per buffer; throughput goes up and CPU goes down.
Kafka's broker uses `sendfile(2)` to push committed log segments straight from the page cache to consumer sockets, which is a big part of why a single broker can saturate a 10GbE NIC. Nginx uses it for static content via the `sendfile on;` directive.