System requirements

Functional:

1. Lock Acquisition: The system should allow clients to request and acquire locks on shared resources. The request should return success if the lock is acquired and failure if it is already held by another client.
2. Lock Release: Clients must be able to release locks they have acquired. Once a lock is released, other clients should have the opportunity to acquire it.
3. Lock Expiration (TTL): The system should support setting a Time-To-Live (TTL) for locks to prevent indefinite holding. If a client does not release the lock before the TTL expires, the lock should automatically be released.
4. Fairness: The system should ensure that lock acquisition is fair, meaning that clients should not be starved and should acquire locks in a reasonable order (e.g., FIFO - first in, first out).
5. Deadlock Prevention: There should be mechanisms in place to prevent deadlocks, which could occur if multiple clients are waiting for locks held by each other.
6. Client Identification: Each client should be uniquely identifiable, so that lock ownership and operations can be tracked and managed.
7. Synchronization: The system must ensure that read and write operations on locks are synchronized across distributed nodes to maintain consistency in the state of locks.
8. Error Handling: The system should return meaningful error messages when lock acquisition or release fails, including timeout or contention scenarios.
9. Statistics and Monitoring: The system should provide monitoring capabilities for tracking lock usage, performance metrics, and potential contention issues.

Before we start we have to figure out initial design as it would have a drastical effect on our system. We can choose single node lock database:

1) Pros: simple to implement and scale read throughput

2) Cons: single point of failure

Or we can do it distributed consesus style using Paxos or Raft algorithm for distributed consensys:

1) Pros: fault tolerant and durable,

2) Cons: slow and difficult to implement and reason about

Non-Functional:

1. Availability: The system should be highly available, ensuring that lock services remain operational even in the face of server failures or network issues.
2. Scalability: The system should be able to scale horizontally to handle an increasing number of clients and lock requests without significant degradation in performance.
3. Performance: The service should minimize latency in lock acquisition and release operations, ideally providing responses in milliseconds.
4. Fault Tolerance: The system must be resilient to failures, allowing continued operation despite the loss of some nodes within the distributed system.
5. Consistency: The system should ensure eventual consistency of the lock states across all nodes, meaning that after some time, all nodes will reflect the same state regarding lock ownership.
6. Security: The system should ensure that only authorized clients can acquire or release locks, potentially utilizing authentication and authorization mechanisms.
7. Monitoring and Logging: There should be monitoring capabilities for tracking usage patterns, performance metrics, and error rates to facilitate troubleshooting and optimization.

Capacity estimation

We assume that there are 1000 locks

1 lock has a size of 1kb

in total we would need to store 1000 * 10kb = 10Mb of memory

clients request 1000 locks per seond

10mb easily fits into 1 node

1 node can handle 1000 requests per second

API design

acquire(user_id, lock_id, TTL)

release(user_id, lock_id)

refresh(user_id, lock_id)

Database design

Lock <| -- AcquiredBy UserID

Lock : +int LockID PK

Lock : +int AcquiredBy FK

Lock: +DateTime AcquisitionTime

Lock: +DateTime ReleaseTime

User : +int UserID PK

User : +String UserName

User: +String Email

User: +String HashedPassword

User: +Datetime CreatedAt

High-level design

Request flows

Acquire flow

1) A client initiates request to acquire a lock

2) A request goes through a lock database that synchronizes lock states across replica using paxos algorithm

Release flow

1) A client sets TTL for a lock, the ttls is retunred in the response as TTL:time

2) Client calls release(user_id, lock_id) after TTL expires

2.1) If client didn' call release our background process invalidates teh lock after expired period

Refersh flow

1) A client sets TTL for a lock, the ttls is retunred in the response as TTL:time

2) Client calls refresh(user_id, lock_id) before TTL expires and thus refresh the TTL of existing lock

Detailed component design

The lockDB is a consensus based distributed storage that saves it's local updates as a write ahead log to provide durability for writes. Every node stores lock status in memory as the amount is not big and fits into 1 node easily. If the node goes down other nodes can elect a new leader that serves writes without losing existing locking log. Also by having a distributed consensus we create a linerizable storage across our db system and thus prevent any client potentially reading writes out of order which is very important in our system. It prevents a situation where a user might try to acquire a lock it thought it was free but was already taken by someone else

Trade offs/Tech choices

We use distributed lock db to provide fault tolerance and durability to our writes. Without it with a single node we have a single point of failure. We use distributed consensus like PAXOS or RAFT to create alinearizable storage for our writes because lock acuisition has an implicit order requirement where reading out of order writes can produce undesirable results in the ystem that can't be tolerated

Failure scenarios/bottlenecks

1) Deadlocks:

User A after acquiring Lock2 wants Lock1

User B after acquirring Lock1 wants Lock2

Nobody can proceed. Solutions:

1) Force clients to acquire locks in order for example restrict clients to acquire Lock1 first and then Lock2.

2) Add timeout param to acquire function so that clients won't try forever

3) Use background process similar to invalidation process that will detect mutual lock acuisition by maintaining a dependency graph of the locks and detecting a cycle in a graph thus breaking the deadlock

Out of order requests:

1) If release_lock comes before acquire_lock the latter should be ignored. We can achieve this using sequence number

Future improvements

Because distributed lock service is such a critical part of the system I would use formal verification methods to check the correctness of the implementation