System requirements
Functional:
Big tech company internal app. employee facing. 1 parking lot. a lot spots.
user login
user reserve parking when provided a list of parking lot that automatically calculate the distance from workplace to parking lot, input is starttime and entime. return reserve id.send email and notification.
map navigation to reserved parking lot and auto show QR code after arrival.
need notification, reserve notification and reminder notification 1 hour and 15 mins before. location based notification when they arrive at entrance.
modification + cancellation of reservation and send notification.
staff or system will scan QR code
support types of car: standard, compact, bikes/motor cycles, EV
reserve open 7days before
user can store their car in app to make reservation faster
Non-Functional:
The key to this system is lock for reservation since all employee is reserved at peak hour.
for cost saving we need scalability on different time of the day. downgrade server off-peak hour.
data consistency is important, need all time consistency.
server reliability and availability is very important.
Capacity estimation
1000 users * 0.7 need for parking space = 700 space needed
have 350 space available. 150 standard. 70 SUV. 130 compact.
qps:
peak hour: 8-9am, 90% reservation in these hour.
700* 0.9 / 3600 = 0.2 qps
disk:
user info: 1K * 1000 = 1MB
space: 1K * 700 = 700K
replica * 3 = 5.1MB
network bandwidth:
peak hour: 8-9am, each request = 1K info, 0.2K per sec throughput
API design
/login?user_id={}&password={}
return success/not
/check_availability?user_id={}&car_type={}&car_type={}&starttime={}&endtime={}&work_place={}
return array[space_ids, distance]
/reserve?user_id={}&idemptant_key={}&workpace={}&car_type={}&starttime={}&endtime={}
user can also use car_id to make reservation
return option[reservation_id]
/list_reservation?user_id={}
return option[array[reservation_id, workplace, location]]
/navigation?current_location={}&target_location={}
/navigation_inside?current_location_ingarage={}&target_location_ingarage={}
/manage_reservation?user_id={}&reservation_id={}&workpace={}&car_type={}&starttime={}&endtime={}
support change car_type or change workplace or change type
/cancel_reservation?user_id={}&reservation_id={}
Database design
user table:
user_id
password
space table:
space_id int
type enum[standard, compact, ev, SUV, bikes]
level int
number int
longitude long
latitude long
car table:
car_id int
user_id
license_plate varchar(7)
state varchar(2)
workplace table:
workplace_id int
level int
longitude long
latitude long
reservation table:
reservation_id int auto increment
user_id int
space_id int
car_id int
starttime timestamp
endtime timestamp
status enum['reserved', 'user-entered', 'user-cancelled', 'finished', 'no-show']
High-level design
client app
backend server
sql databse with normalization.
cache for reading info.
message queue for notification.
message queue for backend request.
notification server for sending notification.
monitoring and alert system.
Request flows
normal case of reservation:
user -> backend server to check availability
user -> backend server to reserve
update space_id order by workspace_location - space_location and supported car type from no reservation at given time and insert reservation in same transaction
return reservation_id, space_location
ask user if need to navigate now
send email and app confirmation for reserve/management/cancel to message queue.
when cancel, mark status of reservation as cancelled so it can be reused.
navigation:
user in app integration with google map/apple map service to navigate to entrance of garage
detect user location
if user is at garage:pop up notification to show qr code, or user click button
qr code content: reservation_id, user_id, car license plate
staff/machine will use their handset or parking machine that scan user's QR code and check if reservation is valid within 15 min and let user in.
navigation from entrance to parking space:
while space_level != user_level:
navigate to ramp
else navigate from ramp to space
notification user when reserve time is {{configurable time or default time 15mins}} ended
when user_location == space_location:
ask if user want to navigate to exit
while exit_level != user_level:
navigate to ramp
else navigate from ramp to exit
if user not entered within 15 mins, ask for cancel, if user not entered in 1 hour, cancel and send notification. update reservation table as cancelled by no show.
Detailed component design
list and status check can be cached, put a redis with cache policy. write through mode will be suitable since write event is less frequent than read event.
database can be seperated for write and read, though this seperation can be substitued if we have cache.
server may be failure since we want high reliability. active-active or active-passive. trade off is can we tolerant down time during peak hour and what's our budget and priority.
database:
distance from workplace and parking space can be pre calculated and ranked. like in redis : Key: workplace_id , value = [array[parking_space_id]] ordered by distance
so that when calculating list of closest parking space it will be faster.
when reserve request: get top 10list of space_ids from workplace_id, join this list with no reservation space.
backup data every 5 mins and replay from WAL when problem.
monitor and alert:
backend server and sql db server will send memory usage, cpu load, rps processed to influxDB
log queue size(pending request size) to influxDB
Grafana query from influxDB to show system status
PD to set up alert from influxDB if cpu load > 70%
alert: pending request too much. Scale up server cluster or write/read isolation sql server or add more read instances.
Trade offs/Tech choices
notification: can be push or pull model
push mode: user and backend long polling connection, cronjob run every 1 mins to scan reservation table for 1 hour and 15 mins before reservation and push to a sns/kafka queue, another cron job send notification to user app.
dedup needed so no multiple notification. notification dedup logic: in mem cache table with key: reservation_id + "-" + notification_type["15mins", "1hour", "reservation", "cancel", "update"]. not make a lot sense in this case since it's not very time sensitive information
pull mode: user app store reservation info, start local notification so no OTA notification for 1hour/15mins. check status before send notification.
user app pull from server for notification each 1mins. once notification sent, remove message from message queue.
Failure scenarios/bottlenecks
peak hour case:
user -> backend server -> get an caller_id -> user app call backend server every 1sec for reserve/management/cancel event.
need to add a message queue for event. backend server will pick event from message queue and ack it when processed.
to improve user experience, we can have 'cancel' event as higher priority to be processed by backend server but it will make system more complex.
server may be failure since we want high reliability. active-active or active-passive. trade off is can we tolerant down time during peak hour and what's our budget and priority.
2 user want to reserve same spot:
in multiple backend server case, since we choose to use transaction so the table is locked when making reservation, means duplicate reservation will happen. although user will receive failure when making reservation, we can suggest other space based on the distance from workplace to parking space. so that user can click on next step.
Future improvements
may need to support multiple parking garage. add a new table and new column to space table.
when company is worldwide of 100k user of different timezone? peak request for write = 27 qps
read = 270 qps
add LB by hash of user_id to hit server
partition table by country or city of company
use interval tree or bitmap for time slots avaibility
reservation system and notification system can be seperated using differnet micro services to deploy.
add wait list system. Add a queue and table for wait list. after space is availble send notification of confirmation and update reservation from wait-list to reserved.