System requirements
Functional:
List functional requirements for the system (Ask the chat bot for hints if stuck.)...
- user can reserve a parking spot
- user pays for reservation
- user can park a car on the parking spot
- user can leave before the reservation time expires
- there are three different parking spots - compact, standard size, and electric charger
- when a user reserves but fails to show up, charge for the first 24 hours
Non-Functional:
List non-functional requirements for the system...
- favor consistency over availability because we don't want double booking
- scalability - we are designing this parking lot for an international company with thousands of employees and parking lots across nations
Capacity estimation
Estimate the scale of the system you are going to design...
I assume:
- the company has operations in 10 different countries
- the company has 100 parking lots, on average, in one country
- on average, each parking lots has a capacity of 200 cars. 70% standard cars, 20% compact cars, and 10% electric charging stations.
- 80% of users use it for short term parking aka 4 hours or less
- 20% of users use it for long term parking aka more than 4 hours
- for each parking lot, we have an average of 50 reservations requests per day
estimation:
- 10 * 100 = 1000 parking lots
- for each day, the system will receive 50,000 reservation requests per day
- each reservation request consists of:
- user id (20 bytes)
- car type (1 byte)
- reservation start time (8 bytes)
- reservation end time (8 bytes)
- roughly totaling 40 bytes
- each day, we would add 400 KB of data
- in 2 years, this would add up to roughly 300mb of data needed
this estimate leads me to choose a relational database for storage as relational database gives strong consistency garuntee to avoid double bookings.
API design
Define what APIs are expected from the system...
APIs used by users:
check_capacity(lot_ID, vehicle_type, start_date_time, end_date_time): returns the number of open spots in the given parking lot. It also returns the price.
reserve_spot(user_ID, lot_ID, vehicle_type, start_date_time, end_date_time): it returns the reservation ID and the price.
pay(user_ID, reservation_ID)
APIs used by gate checking service at the parking lot:
vehicle_arrived(reservation_ID, date_time)
vehicle_left(reservation_ID, date_time)
Database design
Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...
Reservation table:
- reservation_ID (primary key)
- lot_ID (foreign key)
- user_ID (foreign key)
- start_time
- end_time
- vehicle_type (foreign key)
- payment_status (paid, unpaid, canceled)
- completion_status (to be completed, fulfilled, canceled)
Vehicle_Type table:
- vehicle_type_ID
Lot table:
- lot_ID (primary key)
- contact_info_ID (foreign key)
- Lot_Space ID (foreign key to Lot_Space table)
- capacities (foreign key to Lot_Capacity table)
Lot_Capacity table:
- lot_space ID (primary key)
- vehicle_type (foreign key to Vehicle_Type)
- number of space
Contact_Info table:
- contact_info_ID (primary key)
- contact_type
- contact_value
User table:
- user_ID (primary key)
- contact_info_ID (foreign key)
- vehicles (foreign key to Vehicle table)
Vehicle table:
- vehicle_ID (primary key)
- vehicle_type (foreign key to Vehicle_Type table)
Transaction table:
- transaction_ID (primary key)
- user_ID (foreign key)
- vehicle_ID (foreign key)
- check_in_date_time
- check_out_date_time
High-level design
You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...
CDN caches static contents for high performance.
Rate Limiter protects the service from DOS attacks.
Load Balancer distributes requests to App Servers using weighted round robin algorithm.
As discussed above, RDB is used as the data store.
App Server uses Redis Cache for performance gain.
Request flows
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
check_capacity() is handled by Reservation Server consulting the data in the database.
reserve_spot() is handled by Reservation Server, which creates a new entry in Reservations table.
It would create a request for payment, which is queued by Message Queue and submitted to the external Payment System.
reserve_spot() may fail if multiple users are trying to book the same spot. Return an error and ask the client to try calling reserve_spot() again.
It would also fail if the lot is full. In that case, the client should not retry. Reservation Server may return helpful information such as estimated time spots may open up in the future.
vehicle_arrived() and vehicle_left() are handled by Transaction Server, which modifies the Transaction table to keep track of vehicle checkins and checkouts.
If vehicle does not arrive after some number of hours (e.g. 24 hours), reservation would be canceled. The user would be charged for 1 day of payment.
If inconsistent state happens, e.g., vehicle_left() is called before corresponding vehicle_arrived(), administrator at the lot should be notified. The service would assume the vehicle arrived around the corresponding reservation start time.
Detailed component design
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
One important algorithm is how to find an open spot when reserve_spot() call is made.
To support this functionality, we would chop 24 hours into 15 minutes. One day would be represented by 96 slots. Since we just need to store occupied / unoccupied, we can use one bit to represent the 15 minute slot. 1 spot requires 96 bits per day. 35040 bits (~4KB) per year.
When reserve_spot(start_time, end_time) is called, the algorithm would be:
- Convert start_time and end_time into index. For example, 00:00 on January 1st would be index 0. 00:15 would be index 1, and so on.
- Create a bitmap with 1's representing time between start_time and end_time.
- Compare this bitmap to the bitmaps representing occupied time of parking spots. Scan from parking spot 0 (closest to entrance) to N (farthest from the entrance).
This algorithm would find the closest parking spot that is available for the desired time slot.
Because this search is bound by the number of parking slots (100s) and the granularity of reservation (15 minutes), it would be performant enough.
It would probably be possible to use Interval Tree data structure to optimize this algorithm further, if further optimization is required.
Trade offs/Tech choices
Explain any trade offs you have made and why you made certain tech choices...
The biggest decision point was the database. For this service, I chose Relational Database over NoSQL Database. The data size, estimated at increasing ~300MB in 2 years, is well within the capacity of a RDB. RDB provides strong consistency, which is beneficial for a reservation service. Once a reservation is made, the user needs the system to honor it 100%, without the risk of double booking or a reservation mistakingly deleted.
NoSQL database, for example MongoDB, would provide a better horizontal scalability than RDB. But for this service, I decided the benefit of RDB outweighs that of NoSQL DB.
Failure scenarios/bottlenecks
Try to discuss as many failure scenarios/bottlenecks as possible.
One bottleneck scenario is when a large number of people gather in a place near one of the parking lots, e.g., for Olympics Games.
This would put a burden on the reservation work flow (reserve_spot(), pay()). Transaction Server would be fine, as the number of requests to Transaction Server would be limited by the physical limitation of the parking lots (i.e. how many spots they have).
To prepare for such an event, all the software components must be replicated horizontally to have enough capacity. Rate Limits have to be configured to smooth out extreme level of traffic.
The database tables must be replicated in multiple ways (e.g. a copy within data center, a copy in another data center, a copy in a different region) for fault tolerance and disaster recovery.
Monitoring system must be put in place to monitor the health of all the servers and components.
Future improvements
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
I think this builds a foundation for more feature development in the future, e.g., additional services, more vehicle and parking types (very large vehicles, buses and trucks, motorcycles and bicycles, charging stations).
Optimizations and availability improvement based on geographic locations would be a good area to invest further. For example, using Global Load Balancer so that clients get routed to the closest data center. Replicating databases between different geographic locations as a back up mechanism in case of a regional disaster.