Concurrency & Asynchronous Performance Questions

Using parallelism, concurrency, and asynchronous execution to improve throughput and responsiveness. Covers thread pools, event loops, async/non-blocking I/O, contention and lock overhead, and the coordination costs that limit parallel speedup. Focuses on the performance implications of concurrency choices rather than concurrency correctness alone.

HardTechnical

60 practiced

A high-throughput image cache implemented in Java uses a plain HashMap and LRU eviction. Under heavy concurrent access the app sees intermittent crashes and corrupted cache state. Design a thread-safe, performant caching approach for mobile that preserves LRU behavior. Discuss lock strategies (coarse lock vs striping), use of concurrent collections, memory pressure handling, and testing approaches to validate correctness under concurrency.

HardSystem Design

63 practiced

Design a thread-safe concurrent sorted set API that supports insert(key), remove(key), contains(key), iterate-in-order with weak consistency, and snapshot views. Discuss underlying data structures (concurrent skip lists, lock-coupling B-trees), lock-free versus fine-grained locking strategies, memory reclamation, and performance trade-offs for reads versus writes.

Sample Answer

Requirements & constraints:- Functional: insert(key), remove(key), contains(key), iterate-in-order (weakly consistent), snapshot views (point-in-time).- Non-functional: high concurrency, low-latency reads, reasonable memory, GC or manual reclamation environment, scalable to millions of keys.

High-level options- Concurrent skip list (e.g., Java ConcurrentSkipListMap): lock-free/optimistic pointer-based with O(log n) expected ops, excellent for read-heavy workloads and natural in-order iteration.- Lock-coupling B-tree (concurrent B+ tree): node-level locks, better cache locality and range-scan throughput for large datasets, higher write amplification.

Design proposal1. Core DS: a layered approach with a concurrent skip list as primary (simplicity + builtin in many runtimes) or a concurrent B+tree for very large on-heap datasets requiring compact nodes.2. Concurrency strategy: - Skip list: use lock-free / optimistic algorithms (marked pointers, CAS on next pointers). Readers (contains, iterate) are wait-free or lock-free; writers use CAS to splice nodes. - B+tree: fine-grained exclusive locks per node with lock-coupling for structural changes; readers acquire shared locks where supported or use optimistic reads validated by node version counters.3. Iteration semantics: - Weakly consistent iterator implemented by traversing next pointers without global locks; skip-list’s lock-free traversal tolerates concurrent inserts/removes and may reflect some but not all concurrent updates.4. Snapshot views: - Lightweight snapshot: increment global epoch and capture head pointer + versioning metadata; iterate following nodes that have version <= snapshot epoch. - Strong snapshot: copy-on-write persistent layer (e.g., path-copying B-tree) or produce a copy-on-write snapshot structure for long-lived consistent views.5. Memory reclamation: - In GC languages: rely on GC but use marked/retired flags to avoid ABA. - In manual memory: epoch-based reclamation or hazard pointers to prevent freeing nodes still visible to iterators/writers; combine with deferred free lists per thread.6. Trade-offs: - Lock-free skip list: excellent read throughput and low latency; writers contend on CAS hotspots and can suffer retries under heavy writes. - Lock-coupling B-tree: better write locality, fewer pointer overheads, better range-scan throughput; more complex locking and possible writer-induced blocking for readers. - Snapshots: cheap epochs provide weak consistent point-in-time; full persistent snapshots cost memory and CPU.7. Recommendations: - Default: concurrent skip list with hazard-pointer/epoch reclamation; provide two snapshot APIs: cheap epoch snapshot (weakly consistent) and optional full copy for strict isolation. - For very large data or heavy range scans: use node-sized B+tree with lock-coupling and versioned reads.8. Observability & testing: - Stress tests with synthetic workloads (read/write ratios), linearizability tests for single-key ops, and long-running iterator/snapshot correctness tests.9. Metrics to monitor: op latency tail, CAS failure rates, GC/pause times (if GCed), memory reclaimed backlog, snapshot creation time and memory.

This design balances simple, high-performance reads (lock-free skip list) with options for stronger snapshots and alternative B+tree implementation when range throughput or memory density requirements dominate.

HardSystem Design

64 practiced

Design a parallel sorting approach for a multi-core server that sorts very large in-memory arrays. Compare parallel quicksort, sample sort, and parallel merge sort in terms of load balancing, cache locality, synchronization costs, and scalability. Recommend an approach and justify your choice for a production in-memory sort service.

Sample Answer

Requirements and constraints:- Sort very large arrays entirely in RAM on a multi‑core server (N cores, large L3 caches).- Low latency and high throughput for many concurrent requests.- Stable resource usage, good worst‑case behavior, minimal synchronization overhead.- Memory footprint should remain reasonable; prefer in‑place or low extra memory.

High‑level options compared: Parallel Quicksort (task-parallel with partitioning), Sample Sort (distributed bucket/sample‑based), Parallel Merge Sort (divide-and-conquer merging with local sorts).

Comparison (load balancing, cache locality, synchronization, scalability)

1) Parallel Quicksort- Load balancing: Pivot quality drives balance. Random pivots or median-of-medians reduce imbalance, but worst-case skew can create hot threads. Work-stealing mitigates imbalance by scheduling smaller partitions dynamically.- Cache locality: Good for local partitions — in-place partitioning accesses contiguous regions, benefiting caches. However, recursive partitioning leads to many small working sets that may thrash higher-level caches if not tuned.- Synchronization costs: Low per-partition (task queue + work-stealing). Partition phase requires few atomic ops; minimal global barriers.- Scalability: Good for moderate cores with careful pivoting and work-stealing, but suffers if pivoting repeatedly creates very uneven partitions or deep recursion causing thread starvation.

2) Sample Sort- Load balancing: Excellent when samples are representative — choose p*log p samples and pick splitters so buckets are balanced with high probability. Provides near-uniform work distribution across cores.- Cache locality: Bucketing requires scattering elements to bucket buffers — can hurt locality unless done in block/batched moves and local buffers per thread. After redistribution each core sorts contiguous bucket, restoring good locality.- Synchronization costs: Redistribution needs coordination to compute bucket offsets (prefix sums) — global synchronization but limited (one or few barrier points). After redistribution, minimal sync.- Scalability: Very good for many cores and NUMA domains if splitters account for per-node differences and redistribution is optimized. Extra memory for buckets and sample arrays required.

3) Parallel Merge Sort- Load balancing: Straightforward: divide into N chunks, sort locally, then perform pairwise merges. Balancing relies on initial chunk sizes; cost of merges depends on data distribution (equal sizes simpler).- Cache locality: Local sorts have good locality. Merging streams accesses sequential memory, good for caches but merging large streams creates streaming patterns that may not reuse cache lines.- Synchronization costs: Merging stages often require global barrier at each merge level or coordinated merging; can be done with parallel multiway merge algorithms to reduce barriers but complexity increases.- Scalability: Good and predictable; overhead grows with number of merge levels (log N). For very large core counts, merge coordination and memory traffic (reading/writing full arrays multiple times) can limit scalability.

Recommendation for production in‑memory sort serviceChoose a hybrid Sample Sort tuned for the platform, with these justifications:- Predictable load balancing: Sampling+splitters yields near-uniform bucket sizes, avoiding worst-case imbalance common in quicksort.- High scalability: One redistribution step then fully parallel local sorts—scales to many cores and multiple NUMA nodes when splitter selection is NUMA-aware.- Controlled synchronization: Only a few global steps (sampling, prefix-sum for offsets); rest is embarrassingly parallel.- Cache & memory optimizations: Implement per-thread local buffers to batch writes into destination buckets, do in-place local sorts (e.g., introsort) on buckets for cache friendliness, and minimize memory copies by writing buckets into preallocated contiguous ranges. Use block partitioning and radix-based pre-bucketing for key types where applicable.- Fault/worst-case handling: If sampling indicates skewed distribution, fall back to recursive sample refinement or localized parallel quicksort for the heavy bucket.- Engineering practicality: Sample sort maps well to production needs: stable throughput, predictable resource usage, easier to tune for NUMA and SIMD optimizations. Provide metrics and adaptive tuning: sample size, bucket count, fallback thresholds.

Operational considerations- Make bucket count ~ k * core_count (k between 1–4) to improve granularity.- Use work‑stealing for local-sort tasks inside large buckets.- Pin threads per NUMA node; select splitters per node or perform hierarchical sample sort to reduce cross‑node traffic.- Instrument and autotune sample size, buffer sizes, and bucket strategy in production.

This hybrid sample-sort with pragmatic fallbacks gives the best combination of load balance, scalability, moderate synchronization, and cache-aware performance for a production in‑memory sorting service.

Unlock Full Question Bank

Get access to hundreds of Concurrency & Asynchronous Performance interview questions and detailed answers.

Join thousands of developers preparing for their dream job.