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

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

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