Loading...
[Senior-level deep dive topic. This is a discussion you want to have at the functional requirement gathering stage because the two approaches would be quite different.]
Let’s discuss a trade-off between a simple, in-memory lock, vs a consensus algorithm (e.g. Paxos) based distributed lock.
Simple, one-node lock:
Consensus algorithm based lock:
In this exercise, we will design the second type of lock.
Usage scenario:
No numbers were given. I assume:
TTL indicates how long the lock will have before expiring, in milliseconds. The default value would be some large number, e.g., 1 hour or 1 day.
-> returns success or failure
Note that it does not wait. If the lock has already been taken, this request would fail immediately.
Client releases the lock.
Client can refresh the TTL of the lock by calling the API.
Because of the low latency requirement, I assume the main data store to be a local memory.
Data model would be:
See the diagram.
[Mid-level deep dive topic]
When client makes acquire_lock() request, the request is sent to the primary node of the lock service. There are total 5 nodes (one primary, 4 replicas).
The primary initiates Paxos run to create a consensus that the client has acquired the lock. If it successfully completes the run (by receiving acknowledgement from majority of replicas), the lock has officially been acquired by the client.
[Senior-level deep dive topic.]
The core purpose of this system is for all the clients to be able to agree on something. For example, if we have a RDB system which consists of 10 servers, which is the primary and which are the read replicas?
Let’s say the existing primary has just crashed. All the remaining 9 servers volunteer to become the primary. Without a proper synchronization mechanism, every server may think it is the primary (and starts to accept write requests from clients …). This would lead to data inconsistency, which is a very undesirable state.
A Distributed Locking system solves this problem. Once the first server’s attempt to acquire the lock succeeds, it becomes the primary. The consensus algorithm in the Distributed Lock system makes sure that only one server can acquire the lock. There is no risk of multiple primaries.
It is possible to build the Distributed Lock system without the consensus mechanism. One node stores the lock in memory. Since it is only one node, it would be simple and fast.
However, the major drawback of this approach is that it is not fault tolerant. It creates a single point of failure. If the node goes down or becomes unreachable, the clients have no ways of synchronizing their requests.
Consensus algorithm based Distributed Lock would be slower than the simple, one-node approach, but would be much more fault tolerant.
See the discussion about simple vs consensus based system in the requirements section.
[Mid-level deep dive topic]
Because the consensus algorithm ensures that the nodes in Distributed Lock service are always in agreement, any of the nodes can take over as the leader, if the leader crashes or becomes unavailable. The nodes would use the consensus algorithm to select the leader.
[Mid-level deep dive topic]
Paxos takes significant amount of computation and messages. Therefore, if there are many locks, Paxos algorithm may become a bottleneck.
We can look into more performant algorithms, such as Multi-Paxos or Raft.
In addition, we can shard the Distributed Lock system. For example, servers that make up a distributed database and servers that make up a distributed message queue (e.g. Kafka) both need a Distributed Lock (e.g. for leader election). However, these two groups of servers do not have to synchronize between each other. Therefore, we can have one Distributed Lock service (consisting of, say, 5 nodes) for the database, and another for the message queue.
[Mid-level deep dive topic]
Let's look at the simple deadlock scenario:
Client A takes Lock 1. It now wants to take Lock 2.
Client B takes Lock 2. It now wants to take Lock 1.
We can take several approaches to prevent this from happening:
a. Ordering. Make sure clients have to take locks in some order, e.g., in an increasing order. This would prevent Client B from taking Lock 2, avoiding the deadlock. Pro: a clean solution. Con: clients must act according to the protocol.
b. Timeout. Make sure clients do not keep trying forever. For example, Client B can try to take a lock for 1 minute, and give up after that. This would let Client A to take Lock 2. Pro: a simple solution. Con: clients must act according to the protocol.
c. Maintain a graph of which clients need which locks. By detecting a cycle in a graph, we can detect a deadlock. Once it's detected, we can force expiration of a lock involved. Pro: efficient approach, as it takes an action only when there's a deadlock. Con: we need to create a mechanism for server to let the client know it is expiring a lock.
As we are trying to build a generic system, the timeout based approach seems to be simple and generally useful. If we need more sophisticated solutions, we can invest more in solutions like the graph based approach.
[Mid-level deep dive topic]
If requests are received out of order, suboptimal outcome can occur. For example, if release_lock() is received before acquire_lock(), then the system would ignore release_lock(), and hold the lock until it expires. To avoid this, the requests should have sequence numbers. Lock Service can maintain historical requests for some time, and use them to avoid misbehaving like that.
Since a distributed synchronization is such a critical component, I would try using formal methods to prove the correctness of the design and implementation. There are well established formal methods based testing mechanisms such as TLA+.