Requirements

Functional Requirements:

• User can reserve a parking spot by selecting specific date, time.
• User can check if the parking spot is available.
• User can pay parking fee using bank application or credit card.
• User can check-in to the parking spot.
• User can check-out from the parking spot.
• The system can cancel the reservation if user doesn't check in with in 15 minutes.

Non-Functional Requirements:

• Availability - Service is highly available, to support users at all time
• Consistency - Especially, reservation service to avoid double-booking.
• Scalability - The system aims to serve more than 100 k people daily. With 1000 request/s at peak time.

API Design

check_available(): get list of available parking spot at specific time slot

GET /check_availability?timeslot={time_slot}

response (200)

parking_ids: [available parking_id]

reserve(): reserve parking spot

POST /reserve

Body:

timeslot: slot of date time

parking_id: available parking id

response (200)

status: SUCCESS

check_in(): check in

POST /checkIn

Body:

• user_id
• parking_id
• datetime

response (200)

status: SUCCESS

check_out(): check out

post /checkOut

Body:

• user_id
• parking_id
• datetime

response (200)

status: SUCCESS

update(): update parking spot status after successful payment

post /update

Body:

• status
• parking_id
• time slot

response (200)

status: SUCCESS

High-Level Design

Microservice:

• we have 4 microservices
  • Check Available
  • Reserve
  • Check In
  • Check Out
• 3 rd party api
  • pay
• each one communicate with database through queue to avoid double write

Database:

• we will use SQL database for the system
• we have read replica to handle read load from microservice and keep syncing it with update log

Detailed Component Design

Reservation Service

• we have 2 options to check if the spot is available
• in case the spot is not available even partially we decline the later request
• bit map
  • To support this functionality, we would chop 24 hours into 15 minutes interval. In one day, we would have 96 slots. To store that one is occupied or not we use 1 bit (0 occupied 1 available) to represent the slot. 1 spot requires 96 bit per day, hence it requires 25040 bit per year (~4KB)
  • algorithm
    • convert start, endtime to index
    • For example 00:00 on January 1st will be converted to 0 and 01:00 will be converted to 4
    • compare if that specific spot already already has an interval that overlap this interval
    • in case it happen we will decline reservation request
    • else we will move on with payment service
  • interval trees
    • balanced binary search tree that stores (start, end) sorted by the start time
    • log(n) search (n is number of reservation in the spot)
  • we will stick with bit map because the space taken by the algorithm can be fitted in 8 GB ram and we have advantage of checking if the spot is available between start, end in O(1) in case it is overlap we decline the incoming interval
• Conflict
  • conflict will be handle by check-then-commit pattern to check if the spot is available before reserving that spot.
  • During the check the spot should be locked by marking its status as tentative
  • tentative -> Completed if the transaction is complete
  • else tentative -> Available
  • if the transaction is not completed in 5 minutes tentative -> available
  • with this one the first user to issue reserve api will change its status from Available -> Tentative
  • while the rest of them will not get available status
  • So that's how only one user can complete the reservation
• Availability
  • the availability will be ensure by deploy the system in different availability zone
• Stale cache
  • we implement cache write through so any update happen will also happen in cache then it will be written in database ensure that cache will always has update status
• Duplicate request
  • using FIFO queue to get rid of duplicate request before creating reservation object
• Expiration after create reservation object we also set cron job to delete the object if the payment status is not completed