How to design a booking system to avoid overlapping reservation
Thanks to AirBnB or Booking.com you can book a hotel or an apartment for several days, but have you ever thought how these systems manage concurrent bookings, preventing several reservations of the same place.
The problem
Let’s define our problem in more detail. The system allows users to book a room (apartment) for some period of time. Two or more users should be able to do it in parallel unless their stays overlap. However, if they do overlap, at least one of the bookings should fail and the user(s) would get an error.
Example:
Case 1.
User1 wants to book a room from September 1 to September 7
User2 wants to book a room from September 8 to September 13
The process should be successful for both users.
Case 2.
User1 wants to book a room from September 1 to September 7
User2 wants to book a room from September 3 to September 10
At least one of the users should get an error.
The complexity of the problem may be seen from the following sequence diagram of the naive approach:
As we see bookings are successfully created for both requests, even though their time periods overlap.
What if we try to create a unique index on booking dates? For example:
‘CREATE UNIQUE INDEX idx_bookings_dates ON bookings (room_id, start_date, end_date);’
Well, it would prevent only bookings with the same start and end dates but won’t work for the aforementioned example where all the start/end dates are different.
I doubt there is one and only solution for this problem, but there are a couple of options I want to describe, each of them may be suitable for certain circumstances. And, of course, each of them has its own advantages and tradeoffs.
Option 1: Multiple Booking Items
Ok, we know that a unique index for the whole booking doesn’t work for this case, but we can create a separate item for each day of the booking period and create a unique index for this table:
Inserting several bookings with at least one identical day simultaneously causes the unique index violation and the whole transaction fails.
Pros:
- simple to implement
- unique indexes are supported by all the relational databases and by many NoSQL
Cons:
- redundant entities in the database
- not very flexible if you need to book not only days but also time slots
Option 2: Post-check
In this solution, our system allows overlapping bookings, but does consistency checks after creation. If this check fails and there are several bookings for the same date, the system cancels all of them except one.
Notice: there should be criteria on how to choose which of the overlapping bookings should be deleted, otherwise the system should delete all of them, which is usually not acceptable from the business side.
I personally wouldn’t go for this one. However easy it seems, it opens a space for possible failures. What if the removal request to the database fails? Of course, you can handle it with a consistency check performed asynchronously, but it adds complexity both on the engineering and business sides.
Pros:
- doesn’t require any additional database features
Cons:
- risk of inconsistent state
- additional complexity
Option 3: Row lock
Luckily, a unique index is not the only feature modern databases offer for us. Another great tool in their toolbox is record lock (or row lock in SQL databases). An exclusive lock on the row (room in our case) would prevent any other request from getting the same lock on the same record.
If you use Postgres, you are probably familiar with SELECT … FOR UPDATE queries. All the other RDBMS also support locks as it is an important feature for every ACID-compatible transactional system. However, not all the NoSQL databases can offer you such functionality. So, as an alternative, I would suggest using message queues, which can also guarantee that only one booking at a time is created.
Pros:
- no additional records in the database
- turns parallel access into sequential
Cons:
- not all databases support locks
- risk of deadlocks
- lock brings additional overhead to every query
Conclusion
I’ve covered several possible solutions to one problem. If you wonder which one to choose, there is no ready answer. I would say, if you use a relational database, there is no point in not using the features it offers. Using indexes and locks you reuse what was already done by DB developers and, therefore, pass a part of your workload to them. So, I would use this approach when it’s possible. Of course, it’s possible to implement the same task without these tools, but you should keep in mind that it would increase your system complexity and you will have to maintain and test your solution more carefully, while built-in database features were used and tested thousands of times.
Anyways, if you have other ideas or know how Airbnb and Booking.com actually handled this issue, feel free to share below in the comments section.
