System requirements

Functional:

1. Acquire Lock: A client can acquire a lock on a resource.
2. Release Lock: A client can release a lock when done.
3. Timeout / TTL: Locks automatically expire to prevent deadlocks.
4. Fairness: Requests should be served roughly in order (FIFO) when possible.
5. Concurrent Clients: Multiple clients can request locks concurrently.

Non-Functional:

1. High Availability: System continues working despite node failures.
2. Scalability: Can handle increasing numbers of locks and clients.
3. Low Latency: Fast lock acquisition and release.
4. Consistency: A resource is locked by at most one client at a time.

Capacity estimation

• 70k ops/sec workload (example 100k clients, 5 locks, TTL=10s).
• Each lock record ~120B; 1M locks = ~120MB RAM.
• Network: ~63 MB/sec for replication.
• 4–6 Raft clusters (3–5 nodes each) for horizontal scaling.
• SLA: <10ms acquire/release, <50ms P99 latency.

API design

POST /lock/acquire

POST /lock/release

POST /lock/renew

resource: The unique identifier of the thing you want to lock (e.g., "file_123", "user:42").

client_id: The ID of the client (or session) requesting the lock.

ttl: Time-to-live (in milliseconds). How long the lock should be valid before it auto-expires.

Database design

KV stores like etcd, Consul, ZooKeeper, Redis provide:

• CAS (Compare-And-Swap) or SETNX (set if not exists).
• Leases with TTL (auto-expire).
• Linearizable reads/writes (strong consistency).
• Fast performance (in-memory with persistence).

High-level design

Consensus Metadata Store (Raft cluster like etcd): authoritative lock state & durable FIFO queues, fencing token generation, wait-for graph for detection. Guarantees linearizability.

API Gateway (stateless): accept client requests, forward to metadata store (or local cache for granted locks), handle renewals, timeouts, and metrics.

Clients : robust client library with heartbeat/renew, local retry/backoff, and API wrappers.

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

ResourceID: unique identifier for the lock.

Lock Modes: Exclusive (X) and Shared (S).

Lease / TTL: locks are leased; TTL ensures automatic release on client crash.

LeaseID / LockToken: unique token returned to the holder; required for release/renew.

Fencing Token: monotonically increasing integer issued on each grant; used by clients to fence stale holders (e.g., database writes must include fencing token).

FIFO Wait Queue: each resource has a queue of pending requests stored durably in consensus to ensure fairness.

Acquire algorithm:

1. Client sends Acquire request to any frontend.
2. APIGW appends a request record to the resource’s queue in the consensus log (etcd).
3. Consensus node evaluates head of queue:
   • If head and compatible with current holders (e.g., no X lock held or S-mode compatibilities) → grant:
     • issue lease_id, assign expires_at = now + ttl_ms.
     • increment global fencing_token for that resource and return it.
     • remove request from queue (durable).
   • Else leave in queue; return queue position if client asked.
4. When a lock is released (or TTL expires), leader evaluates queue head(s) and grants next eligible one(s) following FIFO, ensuring compatibility (S vs X).
5. Renew must be called prior to expires_at — extended by writing to consensus to update expires_at for lease_id (or a faster path: renew directly to leader, but persistently updating expiry prevents split-brain issues).

This gives strict FIFO fairness and survivability.

Trade offs/Tech choices

1) Consensus vs leaderless vs external service

Options

• Raft (etcd/consensus groups per shard) — leader-based replication.
• Paxos (classic, e.g. Chubby-style) — academically proven but more complex to implement.
• Leaderless (CRDTs, quorum-writes like Cassandra) — no single leader; eventual consistency.
• Use an existing service: ZooKeeper, etcd, Consul, or Redis (with Redlock).

Trade-offs

• Strong consistency & linearizability: Raft/Paxos win. Guarantees single-writer semantics and simpler reasoning about correctness (critical for locks). Cost: write path requires quorum commit → higher latency.
• Availability/latency during partitions: Leaderless or eventual options may allow more writes in partitions but risk split-brain and correctness issues for locks.
• Operational complexity: Rolling upgrades, leader election, and leader placement are simpler with mature Raft libraries/etcd; Paxos implementations are rarer and trickier.
• Implementation cost: Reusing etcd/consensus libraries massively reduces risk vs implementing your own consensus.

Recommendation

• For correctness-required locks use Raft (e.g., etcd core or a Raft implementation). For best-effort locking where occasional risk is acceptable and ultra-low latency is prioritized, Redis/Redlock may be fine.

2) Sharding strategy

Options

• Consistent hashing (resource_id → shard)
• Range-based (e.g., lexicographic ranges)
• Hash-with-affinity for multi-key collocating

Trade-offs

• Consistent hashing: Excellent horizontal scale and even distribution, simpler resharding. Harder to do efficient atomic multi-locks when keys span shards.
• Range sharding: Makes multi-key atomic ops easier if keys are colocated by range, but hotspots and resharding are painful.
• Affinity / co-location: If your application often locks groups of keys together, collocate those resource groups into the same shard to avoid cross-shard transactions.

Recommendation

• Use consistent hashing by default, but provide an API or client-side guidance to allow applications to request collocation or use namespaces so the app can place related resources together.

3) Lease model (TTL) design

Options

• Short TTLs (e.g., seconds)
• Long TTLs (tens of seconds/minutes)
• Client-keepalive with server-validated renewals
• Lease auto-extension serverside

Trade-offs

• Short TTLs: Faster recovery from crashed clients, but higher renewal overhead and greater risk of accidental expiry if network hiccups occur.
• Long TTLs: Less renew traffic, but longer time to recover from deadholders.
• Renewal frequency: Higher frequency reduces accidental expiry but increases load and places demands on client reliability.
• Auto-extension: Convenient but risky — server-side heuristics may extend locks erroneously if client is unhealthy.

Recommendation

• Use moderate TTL (a multiple of expected operation duration) and require clients to renew at TTL/2. Expose tuning knobs per workload. Implement a configurable grace/retry window to avoid accidental expiry on transient network blips.

4) Fairness vs throughput

Options

• Strict FIFO queueing per lock (fair)
• Optimistic granting (race + CAS) (high throughput)
• Priority queues (admin overrides)

Trade-offs

• FIFO ensures fairness and predictable latency but increases queuing state and potentially throughput cost (more serialized state transitions).
• Optimistic races (first to write) are lower-latency in high-throughput scenarios but allow starvation and unfairness.
• Priority adds complexity and can break fairness guarantees.

Recommendation

• Default to FIFO queueing for most shared resources. Offer an opt-out mode (best-effort / high-throughput) for performance-sensitive caches or ephemeral locks.

5) Multi-resource locking

Options

• Client-side canonical ordering (simple, prevents deadlock)
• Two-phase commit (2PC) / distributed transaction coordinator (atomic)
• Lock leasing + optimistic concurrency with rollback

Trade-offs

• Canonical ordering: Simple, low complexity, prevents cycles, but requires client cooperation and may be slower due to retries on contention.
• 2PC: Provides atomic multi-locks but is complex, adds blocking phases, and increases latency and failure surface (coordinator failure recovery).
• Optimistic approaches: Lower latency when conflicts rare, but require retries and careful application logic.

Recommendation

• Prefer canonical ordering for most use-cases. Offer an optional transactional multi-lock API for workloads that absolutely need atomic multi-resource semantics, implemented via a coordinator and limited to small lock sets.

6) API & transport

Options

• gRPC (HTTP/2) — low-latency, bi-directional streaming (watches).
• HTTP/JSON (REST) — universal compatibility.
• Binary RPC (custom) — potentially lower overhead, but more work.

Trade-offs

• gRPC: Ideal for high-performance clients, streaming watch APIs, and good for typed protobuf-based contracts. Slightly more work to support browsers.
• HTTP/JSON: Easier to adopt broadly, lower friction for web clients, but higher overhead and poorer streaming support.

Recommendation

• Primary API via gRPC with generated client libraries (Go/Java/Python/Node). Provide an HTTP/JSON gateway for browser/HTTP-only clients.

7) Storage & persistence

Options

• In-memory + Raft WAL + snapshots (common)
• Direct persistent store (RocksDB) behind Raft for huge state
• External DB for long-term audit/history

Trade-offs

• In-memory + WAL balances speed and durability—Raft ensures durability via WAL; snapshots keep state compact.
• RocksDB is more durable for large state (millions of locks) but adds complexity and I/O cost.
• External DB useful for audit logs; keep lock state in the consensus group.

Recommendation

• Use in-memory with WAL + snapshot. If lock count and metadata blow up, persist per-shard state to RocksDB or other embedded KV with periodic compaction.

8) Hotspots & contention handling

Techniques

• Split hot resources into sub-resources (namespace:resource:shard).
• Backpressure & rate-limiting on acquisition attempts.
• Batching and coalescing renewals or releases.
• Leader pinning / bring leaders closer to clients.

Trade-offs

• Mitigations reduce tail-latency but change application data model (need to split resource semantics).

Recommendation

• Monitor per-resource queue lengths and provide tooling to re-shard or split hot keys. Expose rate-limit and TTL tuning per resource.

9) Failure handling & correctness trade-offs

Options

• Strict linearizability (every operation goes through Raft leader commit)
• Stale reads from followers (reduce latency for read-heavy workloads)
• Relax consistency for availability during partitions

Trade-offs

• Linearizability simplifies correctness proofs at cost of latency and availability in partitions.
• Stale reads reduce latency but must be clearly documented to clients (not for acquire path).
• Relaxation can permit progress but makes correctness tricky for locks.

Recommendation

• Acquire/release must be linearizable. Allow stale follower reads only for monitoring/metrics/inspections with explicit flags.

10) Language, runtime, and libraries

Choices

• Implementation language: Go or Rust for server (mature ecosystems for networking, concurrency; Go has etcd/raft code available).
• Raft libraries: etcd/raft (Go), Hashicorp Raft (Go), raft-rs (Rust).
• Client libs: generate from protobuf (gRPC) for Java/Go/Python/Node.

Trade-offs

• Go: quick development, memory-managed, excellent gRPC and raft libraries (etcd). Widely used in infra.
• Rust: performance and safety, but smaller ecosystem and longer dev time.
• Java: enterprise ecosystem, heavier runtime.

Recommendation

• Use Go for server (etcd/raft code reuse) and protobuf/gRPC for clients. Rust is a good choice if low-level performance and memory control are required and team has expertise.

11) Observability & operational choices

Must-haves

• Metrics (Prometheus), structured logs with request/session IDs, distributed traces (OpenTelemetry), alerts for high queue depth/leader churn/lease expirations.

Trade-offs

• More telemetry increases Ops cost and storage but is necessary to diagnose distributed problems.

Recommendation

• Instrument everything by default and provide sampling for high-throughput traces.

12) Security & multi-tenancy

Choices

• mTLS for node-node and client-node comms.
• ACLs with resource namespaces and tokens.
• Per-tenant rate limits and quotas.

Trade-offs

• Security adds config and operational steps but is essential in production.

Recommendation

• Enforce mTLS and token-based ACLs. Allow per-namespace policy.

13) When to reuse an existing product vs build

Use existing if

• You want battle-tested consensus and session semantics: use etcd or ZooKeeper for locking primitives (with ephemeral znodes in ZooKeeper).
• You need a simple low-latency lock with relaxed correctness: Redis + Redlock.

Build if

• You need sharded, high-scale FIFO-queue locks with built-in fairness, multi-tenant policies, and specialized multi-lock semantics that existing systems don’t provide out-of-the-box.

Recommendation

• Start by evaluating etcd (or ZooKeeper) + application-side queueing pattern. Only build custom sharded system if you need more scale or advanced fairness/multi-lock features.

14) Recommended stacks for typical needs

1. Strict correctness + moderate throughput (default enterprise)
   • Server: Go, etcd/raft per-shard
   • API: gRPC + HTTP gateway
   • Persistence: in-memory state + WAL + snapshots
   • TTL renewals: client heartbeats (TTL/2)
   • Observability: Prometheus + OpenTelemetry
   • Security: mTLS + ACLs
2. Ultra-low latency, best-effort locking (ephemeral caches)
   • Server: Redis cluster (single-master or primary-replica per shard)
   • Lock algorithm: Redlock (careful; understand limitations)
   • API: redis protocol + client libs
   • Use-case: cache invalidation, ephemeral locks where rare mis-grants acceptable
3. High-scale (millions of locks), fairness, multi-region readers
   • Server: Sharded Raft groups (Go), consistent hashing, localized leaders
   • Cross-region: local leaders in each region with async cross-region replication for reads, and optional global coordinator for cross-region atomic ops
   • Persistence: RocksDB per node for huge state
   • Extra: Hotspot detection & dynamic sharding
4. Small/simple project / PoC
   • Use etcd (single cluster), use ephemeral leases, let application use canonical-order for multi-locks.

15) Non-functional / operational trade-offs summary

• Consistency vs Availability: For locks, favor consistency. Availability can be tuned by replication factor and placement.
• Latency vs Durability: Lowering replication or using followers for reads reduces latency but weakens durability or read freshness.
• Complexity vs Guarantee: Implementing 2PC or global transactions provides stronger API but much higher complexity and latencies.
• Fairness vs Throughput: Strict FIFO ensures fairness but increases latency under contention.

Failure scenarios/bottlenecks

1. Leader crash

• What happens: Raft leader of a shard goes down mid-operation.
• Impact: Pending Acquire/Release RPCs fail or time out. Locks already committed remain safe (linearizability via Raft).
• Recovery: Followers elect new leader (100–500ms typical). Clients retry via gateway/redirect.
• Mitigation:
  • Keep Raft election timeouts tuned (not too long = faster failover, not too short = avoid split votes).
  • Clients should implement retry/backoff with idempotent request IDs.
  • For hot shards, consider 5-node groups to improve quorum resilience.

2. Network partition

• What happens: Cluster splits into majority and minority.
• Impact: Only majority side makes progress; minority rejects or times out. Clients routed to minority see failures.
• Correctness: Mutual exclusion preserved (no split-brain) because only majority can commit.
• Mitigation:
  • Deploy Raft members across failure domains (zones/regions) to maximize chance of majority surviving.
  • Gateway must reroute clients to surviving majority quickly.
  • Use shorter DNS/gRPC timeouts and retries to fail over fast.

3. Client crash while holding lock

• What happens: Session heartbeats stop; lease expires.
• Impact: Locks auto-released after TTL. Next in queue gets granted.
• Mitigation:
  • Use moderate TTLs (few seconds).
  • Clients renew at TTL/2.
  • Optionally allow short grace window to avoid accidental expiry from transient network blips.

4. Client pause (GC stop-the-world, network lag)

• What happens: Session misses heartbeat, lease expires even though client is alive.
• Impact: Lock may be reassigned to another client → two clients think they hold it.
• Mitigation:
  • Leases are server authoritative. When client resumes, its renewals will be rejected if session already expired.
  • Clients must check lease expiry before using lock.
  • Build in fencing tokens (monotonic lock version numbers) so downstream resources can reject stale holders.

5. Shard hotspot (one lock/resource very contended)

• What happens: A single resource’s queue grows; leader becomes bottleneck.
• Impact: Long tail latencies, unfairness if queue mismanaged.
• Mitigation:
  • Monitor queue depth; split resource into sub-locks if possible.
  • Apply backoff + jitter on client retries.
  • Rate-limit acquisitions per client to avoid thundering herds.

6. Clock skew

• What happens: Nodes disagree on time → incorrect lease expirations if wall clock used.
• Impact: Premature release or stale lease extension.
• Mitigation:
  • Use monotonic logical time (Raft log index or leader’s monotonic clock) for lease expirations.
  • Never rely on client wall clock.

7. Shard data loss

• What happens: Majority of nodes in shard lose disk or data corruption.
• Impact: Locks lost; system must rebuild state.
• Mitigation:
  • Durable WAL + periodic snapshots.
  • Replicate shards across zones.
  • For critical workloads, back up Raft snapshots externally.
  • Expose “shard rebuild” tools that clear locks safely (clients must retry).

8. Gateway failure

• What happens: Gateway crashes or loses connectivity.
• Impact: Clients can’t route requests.
• Mitigation:
  • Gateways should be stateless & horizontally scalable.
  • Clients should support multiple gateway addresses or direct node connections.

9. Thundering herd on lock release

• What happens: Many queued clients wake up simultaneously after a lock is freed.
• Impact: Burst of Acquire RPCs → leader overload.
• Mitigation:
  • Server grants next holder directly from queue (don’t let everyone race).
  • Notify exactly one waiter at a time.
  • Use event streams (watch API) instead of polling.

10. Leader thrash (frequent elections)

• What happens: Network instability or overloaded node causes repeated elections.
• Impact: Lock availability flaps; client retries spike.
• Mitigation:
  • Keep Raft heartbeats stable (low latency network).
  • Use dedicated nodes for consensus, separate from heavy client workloads.
  • Alert on high leader change rate.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?