System requirements


Functional:

  • User choose a slot to book for a certain duration
  • User pays for reservation
  • User park a car
  • User can leave before the reserved time
  • When a user makes a reservation, but fails to show up, he pays some money


Non-Functional:

  • Available
  • Consistent (CP) or Monolithic
  • Scalable



Capacity estimation

  • The company has operations in 10 countries.
  • The company has 100 parking lots, on average, in one country.
  • On average, each parking lot has a capacity of 200 cars.
  • 80% of users use it for short term parking, averaging 4 hours.
  • 20% of users use it for long term parking, averaging 5 days.
  • Each parking lot receives 200 reservation requests per day.


Estimation:

  • 10 * 100 = 1000 parking lots.
  • The system receives 200 * 1000 = 200.000 reservation requests per day.
  • Each reservation would mainly consists of:
    • Reservation ID (8 bytes)
    • User ID (8 bytes)
    • Car type (1 byte)
    • Reservation start time (8 byte)
    • Reservation end time (8 byte)


Roughly speaking, let's assume this would total 128 byte in total.


  • Each day, we will add 200K * 128 = 25.6MB of data.
  • In 2 years, it would add up to 25.6 * 365 * 2 * 1.5 = 280 GB (assuming future growth).





API design


  • GET check_capacity(lot_id, start_time, end_time):- Returns the number of open spots in the given parking lot and also returns the price.


  • POST reserve_spot(user_ID, lot_ID, start_time, end_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 finalises the reservation.


APIs used by gate checking service at the parking lot:


  • vehicle_arrived(reservation_ID, date_time)


  • vehicle_left(reservation_ID, date_time)




Database design

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)






Request flows

Request flows


[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.





Detailed component design

Reservation Service


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:


  1. 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.
  2. Create a bitmap with 1's representing time between start_time and end_time.
  3. 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).
  4. Create a reservation object with the bitmap.


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.





Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...






Failure scenarios/bottlenecks

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).





Future improvements

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.