Loading...
[Generally speaking, you would like to keep the requirements scope small. You only have 35 - 50 min in an interview. If you have a lot of requirements, you'd risk running out of time. We could add many requirements here: vehicle type, indoor parking vs outdoor parking, additional services like car wash, and parking cars near the entrance to have a quick enter & exist experience, etc. But we will start with a small set of requirements. Easier to expand later than shrink.]
I assume:
Estimation:
[You do not need to provide this much detail in an actual interview. In fact, you should not, because of the time limit. The primary thing you are trying to establish is that the size requirement is small enough for RDB. At less than 1TB in 2 years, it's well within RDB's comfort zone. If it's a lot more (100TB, 500TB, 1PB ...) , then you would have to consider NoSQL DBs, and provide consistency in some other way.]
This estimate leads us to choose a relational database as the storage for reservations. The estimated size is within RDB's capabilities.
RDB gives strong consistency guarantee, which is suitable for a reservation system because avoiding inconsistency (e.g. double booking) is an important requirement.
The response time requirement is not very hard. If reservation takes a couple of seconds (instead of milliseconds), that would be acceptable.
[When there is a requirement for consistency, you usually would like to consider RDB as the first option. Consistency is the bread & butter of RDB, so if you can manage RDB's disadvantages (scalability, response time), it is usually a solid choice.]
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)
Returns the reservation ID and the price.
After reserve_spot(), user is forwarded to a 3rd party payment mechanism (e.g. PayPal or credit card). We assume that the user receives a token which proves the user made the payment.
complete_reservation(user_ID, reservation_ID, payment_token):
This verifies the payment token with the 3rd party payment mechanism, and finalizes the reservation.
APIs used by gate checking service at the parking lot:
vehicle_arrived(reservation_ID, date_time)
vehicle_left(reservation_ID, date_time)
[Mid-level deep dive topic. We do not think it is important for data models to be comprehensive, due to interview time limit. But particular details, e.g., how to model complex concepts, or which tables have many-to-many relationship and require a join table, can provide an interesting deep dive topic.]
Reservation table:
Reservation table is the key to this solution because the solution is about making reservations. It also joins User and Spot tables.
Spot table:
Lot table:
Contact_Info table:
User table:
Vehicle table:
Transaction table:
Here "transaction" means a process a vehicle coming in to the parking lot (check in) and getting out (check out).
[There can be enhancements, e.g., reviews for the parking lot, and reviews for the users. But again, better to focus and do fewer things well.]
API Gateway provides protection against DOS attacks, terminates TLS, and distributes client requests to appropriate service node.
As discussed earlier, primary data are stored in RDB.
Services use Redis Cache to store frequently used data for performance gain.
[Mid-level deep dive topic.]
User starts the journey by calling check_capacity(). It is handled by Reservation Service, which reads lot capacity information from the database.
reserve_spot() is handled by Reservation Service, which creates a new entry in Reservations table.
It would create a request for payment (e.g. a redirect URI), which it returns to the client.
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 Service may return helpful information such as estimated time spots may open up in the future.
Client makes the payment, and sends the payment token (confirmation) via complete_reservation().
vehicle_arrived() and vehicle_left() are handled by Transaction Service, which modifies the Transaction table to keep track of vehicle checkins and checkouts.
Transaction Monitor service periodically checks the database for non-arrivals. If a vehicle does not arrive some time (e.g. 8 hours) after the reserved time, 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.
[Senior level deep dive topic.]
Reservation Service has to find an appropriate open spot when the client asks for one.
Bitmap Approach
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:
This algorithm would find the closest parking spot that is available for the desired time slot.
(3) and (4) must be protected from concurrent access. We can use select for update functionality of RDB to lock the rows in Reservation table and write it. This way, only one thread can make a reservation.
Because this search is bound by constant numbers (the number of parking spots is in hundreds per parking lot, and there are 96 time slots in one day), it would be performant enough.
The strength of this approach is the O(1) search time per parking spot, because one bitmap represents all the reservations in the spot. The disadvantage is that the reservation can be made only at 15 minutes interval, and bitmaps take memory.
Interval Tree approach
Interval tree is a balanced binary search tree which store intervals (start time, end time) sorted by the start time. This provides O(log(n)) search time, given n is the number of reservations in the spot. This is slower than the bitmap approach. It is more memory efficient.
Consideration
To implement the bitmap approach, we would need 10 coutnries * 100 lots * 200 spots * 4KB = 8GB of data. This would easily fit into cache and RDB. Therefore, bitmap approach seems suitable for this problem.
[Junior level deep dive topic]
One decision point is the database. For this service, we chose Relational Database over NoSQL Database. The data size, estimated at ~300GB 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 key-value store or document DB, would provide a better horizontal scalability than RDB. But for this service, the benefit of RDBs in consistency and relational queries outweigh the benefit on NoSQL DBs (scalability).
[Mid level deep dive topic]
Care should be taken to make the system scalable and durable.
In terms of scalability (a lot of data stored), Database would be the primary bottleneck. All other components are either easily scalable because they are stateless (Reservation Service, Transaction Service) or support scalability natively (Cache, API Gateway).
Database can be partitioned by parking lot ID. This is beneficial because all the tables (e.g. Reservation, Spots) for a given parking lot would always be on one database node, avoiding scatter-gatherer pattern. The database should also have read replicas to enhance read performance and fault tolerance.
In terms of durability, a likely problematic scenario is when a large number of people gather in a place near one of the parking lots, e.g., for Olympics Games. Many people would want to book spots in one parking lot at the same time. We believe the bitmap and select-for-update approach we discussed in Detailed component design would provide sufficient durability, primarily because the number of spots per lot is small (100s).
For fault tolerance, 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.
I think this builds a foundation for more feature development in the future, e.g., additional services, vehicle and parking types (compact & standard & large vehicles, electric vehicles and charging stations), etc.
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.