Systems and Concurrency
36 techniques · 24 tradeoffs · 32 Big O entries across concurrency, distributed systems, database internals, and networking and OS fundamentals.
Practice the QuizConcurrency
24Mutual-exclusion primitive: at most one thread holds the lock at a time, serializing access to a critical section.
Allow many concurrent readers OR one exclusive writer, but never both, boosts throughput on read-heavy state.
Hardware-level atomic instruction: write a new value only if the current value matches expected; otherwise retry.
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.
Counter with atomic acquire/release: lets at most N permits be held simultaneously. Generalizes the mutex (N=1).
Pre-allocated worker threads pull tasks from a shared queue, so you pay thread-creation cost once and bound concurrency.
Producers offer work to a fixed-capacity queue; consumers drain it. Bound provides natural backpressure when consumers fall behind.
Per-thread variable: every thread sees its own copy, eliminating sharing and therefore eliminating the need to synchronize.
Never mutate a shared object; on write, copy it and atomically swap the reference. Readers are entirely lock-free.
Represent an in-flight computation as a value you can compose, chain, and await, no manual callback threading.
O(1)One CAS instruction succeeds on the first try; the loop runs exactly once. The hardware `LOCK CMPXCHG` is constant time.
O(n)Each contender retries the CAS until it wins. With n threads racing, the expected number of retries per successful increment scales with n, the cache line ping-pongs between cores.
O(1)Uncontended acquire is one CAS on the lock word, constant time. No syscall, no context switch.
O(1)Same as a regular hash map: hash to a bucket, scan the (usually tiny) bucket. Reads in Java 8's `ConcurrentHashMap` are entirely lock-free; the only synchronization is `volatile` reads of bucket heads.
O(1)Array-backed ring buffer: take the lock, write at the tail index, advance the index, release. Each step is constant time. The blocking on full is separate from the algorithmic complexity.
O(log n)Skip list lookup expects O(log n) levels with O(1) work per level. The 'concurrent' part is about lock-free traversal via CAS, it doesn't change the asymptotic complexity.
O(n log n)Same as serial mergesort total work: work stealing changes wall-clock (span) by a factor of the worker count, not total work. The scheduler adds O(1) per fork/join on average via per-thread deques.
O(n)Each write allocates a fresh array and copies all n existing elements, then atomically swaps the reference. That's why copy-on-write is for read-mostly state, writes are linear.
Distributed Systems
24Leader-based consensus protocol: one elected leader replicates an append-only log to followers; entries commit once a majority quorum acknowledges.
Tune 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.
Each replica tags writes with a per-node counter map. Comparing two versions reveals causal order, concurrency, or strict dominance.
Each node periodically picks a random peer and exchanges state. Information spreads epidemically in O(log n) rounds with bounded per-node bandwidth.
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.
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.
Data types whose merge function is commutative, associative, and idempotent, so any two replicas converge to the same value without coordination.
Coordinator asks all participants to PREPARE; if all vote yes it sends COMMIT, otherwise ABORT. Blocks if the coordinator crashes between phases.
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.
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.
O(n)Leader sends one AppendEntries to each of n - 1 followers and receives n - 1 acks. That's 2(n - 1) = O(n) messages per commit round.
O(log n)Each round, the number of informed nodes roughly doubles (push gossip), so full coverage happens in ~log2(n) rounds with high probability.
O(log n)Compare roots; descend only into the mismatched child at each level. Tree depth is log n, so one mismatch is found in log n hash comparisons.
O(1)The coordinator fires R reads in parallel and waits for the first R acks. That's one round-trip regardless of R, modulo tail latency.
O(n)Prepare to n participants + n votes back + Commit to n + n acks = 4n = O(n). Plus log-force fsyncs at coordinator and each participant.
O(log n)Binary search the sorted ring of virtual-node positions for the first one >= hash(key). With v virtual nodes per real node, that's O(log(n * v)).
O(k)You inspect each of the k entries once, across the union of writer ids in both clocks, to decide whether one clock dominates the other or the two are concurrent. That is linear in the size of the clock.
O(n)The write must traverse head -> middle -> tail sequentially, so latency is proportional to chain length n in network hops.
Database Internals
22Balanced, 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).
Buffer writes in an in-memory memtable, flush sorted runs (SSTables) to disk, then merge them in background compaction passes.
Hash table over a column; O(1) average point lookup, but no order, so no range scans or ORDER BY.
Add the columns you SELECT into the index so the query plan never visits the heap. The index alone covers the read.
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.
Append every change to a sequential log and fsync before touching the data pages. On crash, replay the log to recover committed work.
Persist the result of a query as a real table; refresh on schedule, on demand, or incrementally as base tables change.
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'.
O(log n)Descend from root to leaf following the key. Each node holds many keys, so a billion-row index is typically only 3-4 levels deep, but the asymptotic cost is O(log n).
O(L)A read checks the memtable, then probes at most one SSTable per level (level 0 files can overlap, so possibly a few there), stopping at the first level that has the key. The worst case, a missing key, touches every level.
O(1)Hash the key, jump to the bucket, walk a short collision chain (or use open addressing). No order, so no range scans.
O(n)Read every page, evaluate the filter, emit matches. Cost model is roughly n / pages_per_second; parallelism lowers the wall clock but not the asymptotic work.
O(k)Hash the key k times and check k bits. No false negatives; false positives are tunable via bits-per-key and k.
O(log n + k)B+tree leaves are linked, so once you find the start key the scan is a linear walk through k entries. This is exactly why B+trees beat hash indexes for ranges.
O(1)Look at the tuple's xmin (creating txn) and xmax (deleting txn). Compare against the snapshot. The active-xid list is small in healthy systems.
O(n log n)Index builds typically sort the key column (O(n log n)), then bulk-load sorted leaves and walk up to build internal pages. Online builds (CONCURRENTLY) add a second pass to catch concurrent writes.
Networking & OS
22Algorithms that decide how fast TCP sends. Loss-based (Reno, Cubic) treat packet loss as congestion; model-based (BBR) measures bottleneck bandwidth and round-trip time (RTT) directly.
TLS 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).
Many concurrent streams over a single TCP connection, each with its own flow control. Fixes HTTP 1.1 head-of-line blocking at the HTTP layer but not at TCP.
HTTP 3 runs over QUIC, a UDP based transport with built-in TLS 1.3, per-stream flow control, and connection migration across IP changes.
Reuse TCP and TLS connections across requests instead of opening a new one each time. Avoids the 3-way handshake plus TLS handshake on every call.
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.
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.
Move bytes from disk to socket without copying through user space. The kernel hands page-cache pages directly to the NIC's DMA engine.
O(d)An iterative resolver asks one server per level, and each answer refers it to the next level down, so a cold lookup costs one round trip per level. In practice d is 2 to 4, and TTL caching collapses most lookups to O(1).
O(log n)Doubling each RTT means n = 2^k after k rounds, so k = log2(n). This is why short connections never reach full bandwidth: by the time slow-start ramps, the flow is done.
O(k)epoll keeps a kernel-side ready list updated as events arrive, so wait() only copies out the k ready entries, independent of n. poll/select rescan all n fds every call, which is what kills them at large n.
O(d)On a TLB miss the MMU walks the page table one level at a time, and each level is one memory read indexed by 9 bits of the virtual address. That is 4 reads on standard x86-64 and 5 with 5-level paging. Page-walk caches cut most walks short.
O(1)Constant work per switch: save registers, swap kernel stack, restore registers, maybe swap address space (TLB flush). The constant is small (~1-5 microseconds) but multiplied across millions of switches per second it dominates.
O(1)Fixed message exchange independent of payload size. TLS 1.2 was 2-RTT for new sessions; 1.3 cut that to 1 by sending key share in ClientHello.
O(n)Bytes have to be physically copied (or at least mapped) one by one. This is what zero-copy (sendfile, splice, MSG_ZEROCOPY, io_uring fixed buffers) eliminates by handing pages to the device directly.
O(log n)Each routing decision narrows the address space by a prefix, so depth grows logarithmically with the size of the address space. Real internet paths are usually 10-20 hops regardless of destination because of CIDR aggregation.