Concurrency and Synchronization Questions

Covers the principles and practical techniques for safely coordinating concurrent execution and access to shared resources. Topics include models of concurrency such as threads, processes, interrupt handlers, and tasks in a real time operating system; differences between preemptive and cooperative scheduling; shared data hazards including race conditions and read modify write hazards; critical sections and approaches to protect them including disabling interrupts in embedded contexts and scoped locks. Synchronization primitives and patterns are included: mutexes, binary semaphores, counting semaphores, condition variables, message queues, atomic operations and lock free primitives such as compare and swap. Memory ordering concerns and memory barrier usage on multi core systems are covered, along with priority inversion and priority inheritance. Also addressed are deadlock, livelock, and starvation concepts and avoidance strategies, granularity and performance trade offs of locking, and practical synchronization patterns. Preparation should include identifying and fixing races in code, designing correct concurrent interfaces, and debugging and testing techniques such as stress testing, instrumentation, deterministic replay, race detectors, static analysis, and code review strategies.

MediumTechnical

85 practiced

During a release, an intermittent race causes data corruption in production. You're the on-call SRE: describe immediate mitigation steps to reduce customer impact, how you'd determine whether to rollback or patch, and practical steps to reconcile corrupted data if necessary.

Sample Answer

Situation: During a production release an intermittent race condition started corrupting customer records.

Immediate mitigation (first 15–60 minutes)- Triage & contain: disable the offending feature flag or pause the rollout (circuit-break) and remove write access paths that trigger the race (API gateway rule, deployment pause).- Reduce blast radius: switch affected services to read-only where feasible, route new writes to a safe queue, or divert traffic to a stable version.- Detect & monitor: enable/raise alerts for corruption signatures, increase logging (trace IDs, request payloads) and snapshot current system state (DB backups, logs, offsets).- Communicate: notify on-call, product, engineering, and customers (status page) with an initial incident summary and ETA for updates.

Decide rollback vs patch- Estimate scope & risk: if corruption is ongoing or write path causes irreversible damage, prefer immediate rollback to the last known-good release.- If rollback itself risks further inconsistency (complex migrations), and a small hotfix can atomically avoid corruption, patch only if deploy is fast, well-tested, and reversible.- Use decision criteria: rate of new corruptions, ease/speed of rollback, rollback-tested runbook, and customer impact/SLO breach.

Reconciliation steps (after containment)- Identify affected records: run deterministic checksums, schema validations, and application-level invariants; use delayed logs/traces to map impacted entities.- Restore or repair: if clean backups exist, restore to a staging cluster and replay non-corrupt writes; otherwise write targeted repair scripts that apply idempotent fixes using business rules.- Audit & verify: run validation suites on repaired data, spot-check with customers if needed, and run canary users before full re-enable.- Post-incident: perform RCA, add guards (mutexes, stronger invariants, tests, Chaos/flake tests), improve monitoring and runbook, and communicate final impact and remediation to stakeholders.

HardSystem Design

88 practiced

Design a locking strategy for a high-throughput distributed cache that must support 100k ops/sec and provide per-key strong consistency for writes. Discuss per-key locks versus shard-leader approaches, lease durations, failure modes, and how to minimize tail latency under heavy contention.

Sample Answer

Requirements:- Functional: per-key strong consistency for writes (linearizable per key), 100k ops/sec sustained, low tail latency.- Non-functional: high availability, predictable latency under contention, SLOs for p99/p999.

High-level architecture:- Fronting stateless proxies (API gateways) route requests via consistent-hash to a key-shard owner (shard leader) or to per-key lock manager.- Backing store = distributed in-memory cache (sharded Redis/Coherent cluster) with durable write-behind optional.- Lock/coordination layer: choose between per-key locks (fine-grained) or shard-leaders (coarse-grained).

Compare approaches1) Per-key locks- Implementation: a distributed lock service (lightweight) — e.g., each proxy requests a lease for a specific key from a lock store (etcd/consensus-based or Redis SET NX with TTL + fencing token).- Pros: maximum concurrency across keys, minimal unnecessary serialization.- Cons: many small locks (100k/sec implies high lock churn), heavier metadata and lease maintenance, more tail risk if many contended keys.

2) Shard-leader (per-shard leader)- Implementation: partition keyspace into N shards; each shard elects a leader (Raft). All writes for keys in that shard go through shard leader which serializes writes.- Pros: fewer leaders to manage, cheaper consensus amortized across many keys, simpler failure handling.- Cons: contention within shard can create hotspot and higher latency; less parallelism than per-key locks.

Hybrid recommendation (SRE-practical):- Use shard-leader as primary coordination for control-plane stability and lower metadata load. Make shards small enough (e.g., 1000s of shards) to distribute load so 100k ops/sec is feasible per cluster.- For hot keys inside a shard, use delegated per-key fast-path: shard leader grants short-lived exclusive leases for single keys to a proxy (lease delegation). Then proxy performs local-exclusive writes directly to cache, returning fencing token to ensure linearizability.

Lease durations and renewal- Use conservative short TTLs: set lease << typical operation latency (e.g., 50–200ms depending on SLO). Short leases minimize blocking during failures.- Clients must renew before 1/2 TTL to avoid expiry races. Use heartbeats batched for multiple keys when a proxy holds many leases.- Always include fencing tokens (monotonic epoch) attached to the lease so stale holders cannot override new holders after failover.

Failure modes & handling- Lease holder crash: expiry leads shard leader to revoke or reissue; ensure fencing token prevents stale writes.- Network partition: use leader election with consensus for shard leaders; deny new leases until quorum to avoid split-brain.- High lock churn: autoscale proxy pool and shards; use backpressure when lock-store backlog grows.- Clock skew: avoid relying on absolute clock — use logical counters/fencing tokens from leader.

Minimizing tail latency under heavy contention- Fast-path: delegated lease to proxy avoids round-trips to leader for steady workloads.- Optimistic concurrency for reads/most writes: try single-round conditional writes (CAS) with retries and exponential backoff; only fall back to exclusive lease when CAS fails repeatedly.- Backoff and jitter: randomized exponential backoff for contended keys, with capped retries.- Prioritize p99: apply admission control—limit concurrent in-flight operations per key to bound queue lengths; shed non-critical work early.- Batch operations where possible and coalesce multiple writes to same key at proxy.- Instrumentation & autoscaling: monitor lock acquisition latency, queue depths, ops/sec per shard; scale shards or rebalance hot keys automatically.- Use local cache for reads with read-after-write guarantees ensured by lease/fencing for writers; reads consult lease-holder or leader if unsure.

Operational practices (SRE)- Define SLOs for p50/p95/p99 latency and error budget for leader election, lock acquire.- Chaos testing: simulate leader failover, lease expiry, network partitions to validate fencing and tail behavior.- Alerts on hotspots, high contention, long lease-grant latencies, and increased retries.- Rolling upgrades: ensure leader handoff and lease revocation before node drain.

Trade-offs- Per-key locks = best concurrency, higher coordination cost.- Shard leaders = simpler, more robust at scale; hybrid delegation gives most practical balance for 100k ops/sec.

This design gives linearizable per-key writes while minimizing metadata overhead and tail latency through delegated leases, fencing tokens, optimistic fast-paths, and operational controls.

MediumTechnical

57 practiced

Design instrumentation to detect increasing lock contention in production over time for a core service. What metrics would you collect (examples: lock hold time histogram, wait time percentiles, number of blocked threads), how would you visualize them, and what automated alerts or thresholds would you configure to notify SREs before customer impact?

Sample Answer

High-level goal: detect rising lock contention early (before customer-visible latency/throughput regressions) by measuring both per-lock and system-level signals, visualizing trends, and alerting on anomalies and thresholds tied to SLO risk.

Metrics to collect (per lock or lock-class + aggregate):- Lock acquire wait time histogram (ms buckets, high-res e.g., 0-1ms,1-5,5-10,...,>1s)- Lock hold time histogram (same buckets)- Wait time percentiles (p50,p90,p95,p99,p999) and trends- Number of threads blocked/waiting on lock (instant and time-series)- Contention events/sec (count of lock failed-fast attempts / retries / spin counts)- Lock acquisition rate (acquires/sec) and successful fast-path rate (no-wait %)- Thread pool queue length and runnable threads (correlate)- Application latency percentiles and error rate (to tie to customer impact)- Sampling trace spans showing lock wait/hold per request (distributed tracing tag)

Visualization:- Per-lock dashboard: sparkline + heatmap of hold/wait histograms; percentile time-series; blocked threads gauge.- Aggregate dashboard: stacked heatmap of top-N contended locks by wait-time; correlation panel showing lock p99 vs request p99 and throughput.- Latency correlation: scatter plot lock wait p99 vs request latency; trace examples linked.- Rate-of-change panels: derivatives for p95/p99 over last 1h/6h/24h.

Alerts / automated thresholds:- Warning: lock wait p95 increased >2x vs baseline (rolling 7-day median) AND absolute p95 > X ms (e.g., 50ms) — for investigation.- Critical: lock wait p99 > Y ms (e.g., 200–500ms) OR blocked threads > 80% of worker threads OR acquisition failure/retry rate > threshold — trigger paged alert.- Anomaly detection: ML/seasonal baseline alert for unusual upward drift over 30–60 minutes.- SLO-bound alert: if request latency SLO burn rate rises and correlates with lock contention (cross-evaluated), escalate immediately.

Runbook / automated actions:- Alert payload includes top contended locks, traces, impacted hosts, and recent deploys.- Auto-annotation of deploys/rollouts to reduce false positives.- Short-term mitigations: automatically divert traffic away from top-affected instances, or scale horizontally if safe.- Post-incident: record root cause, add instrumentation (e.g., finer buckets), and set new baselines.

Rationale: combine direct lock metrics (wait/hold) with system indicators and tracing so alerts are specific (low false positives) and actionable (tells which lock, service, and traces). Use relative (baseline) and absolute thresholds to catch both gradual regressions and acute spikes.

EasyTechnical

65 practiced

You're reviewing a pull request that adds a new shared cache protected by a global lock. List five specific concurrency-related items you would look for in the code review to prevent bugs and performance regressions, and recommend two test cases or stress tests the author should add before merging.

HardSystem Design

53 practiced

Compare coordination approaches for configuration changes: consensus (Raft/Paxos), leaderless replication (CRDTs), and lease-based locking. For an SRE managing global configuration with strong SLOs, discuss availability, consistency, latency, operational complexity, and failure recovery trade-offs for each approach and give recommended use cases.

Sample Answer

Requirements (assumed): global config store for many read-heavy clients, occasional writes/rollouts, strong SLOs for correctness and low-latency reads, ability to roll back, and predictable failure behavior.

High-level trade-offs (consensus / CRDTs / lease-based locking):

1) Consensus (Raft/Paxos)- Availability: CP in CAP — favors consistency; requires quorum for writes, so regional partitions reduce availability for updates but reads can be served by followers if configured (may be stale).- Consistency: Strong linearizable consistency possible (with leader and sync writes).- Latency: Write latency = cross-quorum RTT (global=high) unless multi-region quorums or read-local/write-global optimizations used.- Operational complexity: Moderate–high: maintain leader election, handle log compaction, backups, versioning, and careful rolling upgrades.- Failure recovery: Predictable; leader failover and log replication ensure no data loss if quorums preserved. Recovery requires quorum restoration.- Best for: critical config that must be strictly consistent (feature flags controlling safety-critical behavior, auth/ACLs).

2) Leaderless replication (CRDTs)- Availability: AP in CAP — high availability and partition tolerance for both reads/writes; clients can update locally and merge later.- Consistency: Eventual; deterministic merge avoids conflicts but not strictly linearizable — last-writer semantics avoided but semantics differ.- Latency: Low local write/read latency; excellent for geo-local operations.- Operational complexity: Moderate: design/choose appropriate CRDT types, migrations, ensure idempotency and bounded metadata growth.- Failure recovery: Easy: replicas converge; healing after partition is automatic if all ops are durable.- Best for: non-safety-critical, high-availability config (UI preferences, rate-limit hints, feature-rollouts where eventual convergence is acceptable).

3) Lease-based locking- Availability: Depends — reads can be local; writes require lease holder. If lease is lost (clock skew, lag), writes blocked until lease re-acquired -> can reduce availability for writes.- Consistency: Can provide strong consistency for the leased writer; needs careful clock/heartbeat management to avoid split-brain.- Latency: Reads fast if served locally from lease holder; write latency includes lease acquisition/renewal RTT.- Operational complexity: High in distributed/global context: lease time-tuning, clock sync, safe handoffs, handling stuck leases.- Failure recovery: Risky: expired/forgotten leases can cause staleness or double-write unless conservative timeouts used. Recovery often manual or requires fencing.- Best for: single-writer workloads, controlled rollout windows, leader-controlled migrations, and operations requiring exclusive change windows.

SRE recommendations- For strict correctness and auditable rollouts (ACLs, billing config): use consensus (Raft) with multi-region quorum design, read replicas, and a fast path for reads (lease reads/linearizable read optimization).- For globally distributed, highly-available but non-critical settings: use CRDTs with monitoring for divergence and clear decay/compaction policies.- For operational tasks needing exclusive control (schema changes, cluster-wide migrations): use lease-based locking combined with consensus-backed lease store (i.e., store leases in Raft) to get predictable fencing.- Hybrid pattern: store authoritative state in consensus, expose local caches updated via reliable streaming; use CRDTs for locally resolvable overlays and leases for exclusive admin ops.

Operational best practices: strong monitoring/alerts for divergence, automated rollback playbooks, versioned config schemas, canary/gradual rollout, and rehearsed failover/runbook for leader or lease failures.

Unlock Full Question Bank

Get access to hundreds of Concurrency and Synchronization interview questions and detailed answers.

Join thousands of developers preparing for their dream job.