This blog describes how online booking systems allow real-time seat booking, despite thousands of concurrent users.
This problem was discussed in detail in a live session at InterviewReady. You can view the edited videos here.
By the end of this blog, you will know the tradeoffs between consistency and latency in a distributed system.
BookMyShow's Booking System
Assume you are building an online booking system like BookMyShow. How do you allow multiple concurrent users to book seats in the same movie hall?
Two users may try to book the same or overlapping seats. Only one should be allowed to continue with the booking, while the other is asked to try again.
Your priority is meeting the above requirements with low latency impact and simple engineering.
1: Synchronous queue
The simplest idea is to process all booking requests synchronously.
This would behave like a single ticket counter at a stadium, where every booking request stands in the same queue.
There is no possibility of two overlapping bookings since the ticket counter would reject such a request.
1. A single queue ensures consistency but is prone to head-of-line blocking.
Do you see some problems with this approach?
- A single counter is prone to head-of-line blocking.
- The counter is a single point of failure.
- When customers increase, the queue is difficult to scale.
For these reasons, we reject the idea of a synchronous queue.
2: Aysnc queue
The next idea is to process requests in multiple queues. This would be like selling tickets with multiple ticket counters.
Here, there is a possibility of overlapping requests. Counter 1 and 2 may try to book the same seats simultaneously, leading to a conflict!
2. Asynchronous queues are difficult to coordinate.
If we force all bookings to wait on each other, using locks or synchronous processing, we find ourselves stuck with the problems of a single queue.
3: Event-specific queues
What happens if we keep separate queues for each event?
Every counter only deals with booking requests for a specific event. Ticket counters can reject overlapping requests.
3. Queues for every event.
But the benefit here is increased concurrency. Customers interested in different events can be processed simultaneously, reducing wait times and allowing horizontal scaling.
The drawback of this approach is poor scaling.
The number of queues is equal to the number of events. If we have thousands of events, we would need thousands of queues.
These queues would be sparsely populated, and take up memory.
4: Non-overlapping queues
The last idea is to limit the number of queues in our system.
Let's say we keep 3 ticket queues. How do we ensure all tickets are booked with zero overlap and maximum concurrency?
We simply group events.
- Counter 1 manages events E1, E4, E7, E10, etc…
- Counter 2 manages events E2, E5, E8, E11, etc…
- Counter 3 manages events E3, E6, E9, E12, etc…
We are effectively load-balancing booking requests on the ticket counters!
A simple form of load balancing is round-robin, as the above example shows. We could use any load-balancing algorithm, including sharding, least connections, etc…
This approach lets us trade between latency and memory. More queues means more memory, but shorter wait times (request latency).
Overall, this is the best approach.
The idea of distributing requests to non-overlapping queues comes up repeatedly in software engineering. The underlying concept of hashing is easy to understand and implement.
| Strategy | Consistency Mechanism | Latency | Memory Overhead |
|---|---|---|---|
| 1. Total Ordering | Automatic | High | Low |
| 2. No Ordering | Locks / Distributed Consensus | Low | High |
| 3. Key-based Ordering | Automatic | Low | High |
| 4. Group-based Ordering | Automatic | Configurable | Configurable |
If you are looking for more content on software engineering, try our System Design Course.