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