Restaurant Reservation System
Topic: Restaurant Reservation System
Interviewer: Marco Y
Interviewee: jack
Level: L5 (Senior)
QR Code:
Sign up
Mock System Design Interview Summary
Interview Overview
Date: 9/4/2022
Target level: L5
Duration: 45 minutes
Topic covered: Restaurant reservation system
Drawing tool used: app.diagrams.net
Requirements
Functional requirements
Register restaurant
Search
Do actual reservation
Maintenance of the reservation: view, modify, cancel
Reservation is most important
Scaling requirements
High available
Low latency
Consistency
Highly concurrent - make sure first-come-first serve when multiple customers select at the same time
60,000 restaurants
1 billion bookings a year
QPS = 1 billion / 365 / 86400 = 500
(editor comment: the result should be ~32)
System Design
External APIs
System design
Interviewee:
Restaurant MGM service
SQL database is better for the scenario
During reservation, you may not want to hit the database, so you need a cache
Interviewer: like to see the basic flow first
Interviewee: removed cache, added notification service
Interviewer: what database to use?
Interviewee: SQL (for transaction support)
Tables:
Restaurant:
Location
Hours
geohash
Interviewer: focus on reservation part
Interviewee:
Tables:
RsID
Capacity
TableID
is_available
Reservation table:
Restaurant ID FK
CustomerID FK
Reservation ID
Table ID
Party Size
Date/time
Status
Seating tables / inventory
Table ID
Reservation ID
time/date
Party size
Interviewer: how to populate inventory?
Interviewee: populate daily using timeslots + tables
API:
Post create restaurantID/
Post /restaurantID/tableId/time
Customer:
Getavailable restaurants by location/type
Make reservation:
Post restaurantID/time/customerId, size
Interviewer: How to prevent conflicting reservation?
Interviewee:
Prevent on UI (greyed button)
Add idempotent ID to prevent booking twice
Race condition. Two users at similar time can cause concurrent issues
We can add constraint in database to ensure there is enough inventory.
We can introduce pessimistic or optimistic locking
Pessimistic locking may cause deadlocks.
Lock particular row
Optimistic locking can work better
We can introduce a version number
Increase version number when making a reservation
Interviewer: there may be lots of contention in holiday or for popular location
Interviewee: add database constraint
Interviewer: peak hour may create high load
Interviewee: add cache, restaurant ID, table, time. value/number of available.
The requests will hit cache first.
Interviewer: show the flow
Interviewee:
someone tries to reserve a table 2pm
Control flow hits cache
Cache miss. Cache fetches from DB
2nd user tries to reserve the same table 2pm
Interviewer: how do you maintain cache consistency
Interviewee:
during update, we quickly update cache then database
Interviewer and Audience Feedback
Feedback from interviewer:
Did a great job
Knowledgeable about various components
Drew diagram
Scale estimates
Picking database
API
Suggestions
Focus more on requirement
MQ, location service, not related to the requirements. We can save some time by skipping these component.
At the beginning we can just design a workable solution
Practice to do mental math / estimation
QPS = 31, so the result was incorrect
Be more affirmative when making design choices (I want to choose instead of I may choose)
Interviewee:
Estimation part was wrong. 1 billion
I like to draw the full picture first. I drew the cache
Additional system
Lots of table. All service points to the same database
It feels different service should have their own database
Optimistic locking vs pessimistic locking
Monolithic service
Micro service. Separate these databases:
Reservation database
Inventory database
2PC or saga
Interviewer: hotel reservation system from Alex Xu can be blueprint
Audience:
Can we reserve a specific table or just # of seats/any table?
Interviewer:
Usually by table type and number of tables, instead of specific table
Hotel reservation: room type not room ID
Audience:
We can use table size, party size
Audience:
How do we handle concurrency of 2 customers reserving the same table
Interviewee:
Microservice. 2PC
Monolithic: constraint. Check if the table is available.
Audience:
What constraint do we use?
Interviewee:
Should be a chunk of code
Constraint should be at database
Transaction should be rollback
Constraint check table available number - reserve number > 0
Check constraint is less portable.
Optimistic lock.
Audience:
Unique constraint of composite unique key
tableID + timeslot ID + dateID
Audience
Different from hotel.
Lock the date, table type + counter
Audience
If they click the button at the same time
In backend update at the same time
Audience
2 people assigned to the same table ID
Audience Nobody will book by table ID
Audience
Then unique constraint will not work
Audience
Select for update (locking)
Or use counter + constraint
SQL constraint reserved seats <= available seats
Audience
Total available, booked numbers
Total available >= booked numbers
Audience
Ticket booking system has similar problem
12306 订票系统
There are specific seat ID in the ticketing system
Audience
秒杀系统
Should add a queue
Audience
Reservation be canceled.
Audience
You can increase and decrease the counter.
Audience
DDIA: phantom write
Data isolation
How to design to avoid write impacting read
Audience
If we put the counter in Redis
Audience
There is no need for cache with this type of throughput
Audience
QPS 32
Small traffic
Audience
Create 30 minute slots
Timeslot ID, table type, restaurant ID
Audience
Overbook
Some tables for walkin
Some tables exceeds time, then we can provide walking table to people with reservation
Audience
Hard for customer to estimate the end time
The business will need to estimate
Usually the customer can only reserve the beginning hour of a time segment (say evening, lunch)