Loading...
Estimation:
Roughly speaking, let's assume this would total 128 byte in total.
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.
APIs used by gate checking service at the parking lot:
Entities (User, Reservation, Parking_Lot)
User (ID, Name)
Reservation (ID, User, Parking_Lot, Slot, Start_Date, End_Date, Payment)
Parking_Lot (ID, Country, Location, Number_Of_Slots)
Payment (ID, ...)
{The table regarding the parking gate checking the car in and out} Transaction (ID, Reservation_ID, Start_Time)
[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.
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 countries * 100 lots * 200 spots * 4KB = 8GB of data. This would easily fit into cache and RDB. Therefore, bitmap approach seems suitable for this problem.
Explain any trade offs you have made and why you made certain tech choices...
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).
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.