System requirements

Functional:

1. User can reserve a parking spot.
2. User pays for the reservation.
3. User can park a car on the parking spot.
4. User can leave before the reservation time expires.
5. There are three different parking spots - compact size, standard size and with electric charger
6.  user account management such as registration, login and view reservation history
7. One common error case to handle is when a user makes a reservation, but fails to show up. In this case, we should charge for the first 24 hours

Non-Functional:

1. Scalability: Desigining for a company with 1000s of lots across the globe
2. Availability
3. Consistency: Once a reservation is made, the parking spot must be available for the user. No double-booking so strong consistency
4. Performance/response time
5. Legal compliance

Other considerations include indoor vs. outdoor parking, additional services, valet parking, and specific location selection.

Capacity estimation

Let's assume:

• Operations in 10 countries
• 100 parking lots on average in on country
• Each parking lot has 200 parking spots: 70% standard, 20% compact, 10% electronic cars with chargers
• 80% of users use it for short term parking, averaging 4 hours
• 20% of users use it for long term parking, averaging 5 days
• For each parking lot, there are on average 50 reservation requests per day

Estimation:

• 10 * 100 = 1000 parking lots * 200 spots = 200,000 spots
• Each day, 50 * 1000 = 50,000 reservation requests per day
• Each reservation consists of:
  • User ID (20 bytes)
  • Car Type (1 byte)
  • Reservation start time (8 bytes)
  • Reservation end time (8 bytes)
  • Total = about 40 bytes
• 40 bytes * 50,000 reservations = 2,000,000 bytes = 2MB
• 2 years = 365 * 2 = 730 * 2 MB = 1460 MB = 1.46GB
• Peak hours: 4 hours per day (morning and evening) constitutes 60% of dialy reservations
• Off-peak hours: Remaining 20 hours account for 40% of daily reservations
• Peak res/day: 50,000 * 0.6 = 30,000
• Non-peak res/day: 50,000 * 0.4 = 20,000
• Rate during peak hours: 30,000/4 = 7,500/hr
• Off-peak rate: 20,000/20 = 1000/hr
• Peak buffered reservations: 30,000 * 2 = 60,000
  • 60,000 / 4 hours = 15,000 reservations / hour
  • Data with buffered peak: 60,000 x 40 bytes =2,400,000 bytes = 2.4 MB
  • 2.4 MB/day * 730 days = 1780 MB = 1.78 GB

This estimate leads to using a relational database for storage as the size is well within the limits of the a relational database and not much vertical scaling will be needed due to the low memory usage. Also strong consistency is needed to make sure there are no double bookings. The response time does not need to be super fast so that is a trade off worth taking for this scenario.

Redis or Memcached: Utilize these for caching frequently accessed data such as reservation availability and parking spot statuses.

• Benefits:

• Reduced Database Load: Offload repetitive read operations to the cache.

• Improved Response Times: Provide faster access to data, enhancing user experience during peak times.

• Implementation Strategies:

• Cache Invalidation: Ensure that caches are updated or invalidated appropriately when reservations are made, modified, or canceled.

• Data Partitioning: Segment cached data based on regions or parking lot IDs to optimize access patterns.

API design

Public/External API (Used by users)::

• check_capacity(lot_ID, vehicle_type, start_date_time, end_date_time): returns the number of open spots for the given time frame in the supplied parking lot as well as the price
• reserve_spot(user_ID, lot_ID, vehicle_type, start_date_time, end_date_time): return reservation ID and the price
• pay(user_ID, reservation_ID, paymentMethod, amount, currnecy): POST request to send payment
  • response: paymentID, status, transactionID, receiptURL
  • errors: 400: Invalid payment details, 402: payment failed, 404: reservation not found
• cancel(user_ID, reservation_ID, reason):
  • response: status, refundAmount, refundId
  • errors: 400: Invalid Request, 404: Reservation not found, 422: cannot cancel (too late/already used)

Private/Internal API (Used by business/internal systems)

• vehicle_arrived(reservation_ID, date_time)
• vehicle_left(reservation_ID, date_time)

Database design

Reservation table:

• reservation_ID (primary key)
• lot_ID (foreign key)
• user_ID (foreign key)
• start_time
• end_time
• vehicle_type (foreign key)
• payment_status (paid, unpaid, cancelled)
• completion_status (to be completed, fulfilled, cancelled)

Vehicle_type table

• vehicle_type_id
• vehicle_type_name (string)

lot table:

• lot_ID (primary key)
• name
• location
• status

lot_capacity table:

• lot_space_ID
• vehicle_type_ID (foreign key to vehicle_type)
• number_of_spaces

contact_info_table:

• contact_info_ID (primary key)
• contact_type
• contact_value

user table:

• user_ID (primary key)
• contact_info_ID (foreign key)
• vehicles (foreign key to vehicle table)

vehicle table:

• vehicle_ID (primary key)
• vehicle_type (foreign key to vehicle_type table)

transaction table:

• transaction_ID (primary key)
• user_ID (foreign key)
• vehicle_ID (foreign key)
• check_in_date_time
• check_out_date_time

There can be enhancements, e.g., reviews for the parking lot, and reviews for the users. But for now, I will focus on the tables above.

High-level design

CDN caches static contents for high performance.

Rate Limiter protects teh service from DDOS attacks

Load Balancer distributes requests to App Servers using weighted round robing algorithm

RDB is DB

App Server uses Redis Cache for performance gain

Request flows

check_capacity() is handle by Reservation Server consulting the data in the database.

reserve_spot() is handled by Res Server which creates a new entry in Res table. It will create a request for payment, which queued by Message Queue and submitted to the external Payment System

reserve_spot() amy fail if multiple users are trying to book the same spot. Return an error and askl the client to try calling reserve_spot() again.

It will also fail if the lot is full. In that case, the client should not retry. Res server may return helpful information such as estimated time spots may open up in the future.

vehicle_arrived() and vehicle_left() are handled by Trans server, which modifies the Transaction table to keep track of vehicle checkins and checkouts

If vehicle does not arrive after some number of hours, reservation should be cancelled and user would be charged for 1 day of payment.

If incosisten state happens, e.g. vehicle_left() is called before corresponding vehicle_arrived(), administrator at the lot should be notified. The service should assume the vehicle arrived around the corresponding reservations start time.

Detailed component design

Sequence diagram depicts how messages flow for client to make a reservation and pay for it, and for the parking lot system to notify the Transaction System when the user's vehicle arrives and leaves.

It is important to find an open spot when reserve_spot() call is amde. We could 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 on bit to represent the 15 minute slot. 1 spot requires 96 bits per day. 200,000 spots * 96 bits = 20,000,000 bits / 8 = 2,500,000 bytes = 2.5MB * 365 days =912MB / year

When reserve_spot(start_time, end_time) is called the algorithm would be:

1. Convert start_time and end_time to 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)

This algorithm would find the closest parking spot that is available for the desired time slot

Because this search is bound by the number of parking slots (100s) and the granularity of reservation (15 minutes), it would be performant enough.

It would probably be possible to use interval tree data structure to optimize further.

Trade offs/Tech choices

The biggest decision was the database type and structure. SQL was chosen over NOSQL for reasons such as DB size that wouldn't require expensive vertical scaling, strict schemas, and strong consistency. New SQL could also be considered but it is more difficult to maintain/setup and SQL is likely better given this specific scenario.

Failure scenarios/bottlenecks

When a large number of people gather in one spot for a special event liekly to reach max capacity. Might put a burder on reservation work flow. Transaction server would be fine since it is limited by the number of spots.

To prepare for events like this, key components shoudl be replicated horizontally to have enough capacity. Rate limits have to be configured to smooth out extreme level of traffic.

Database tables should be replicated multiple ways:m one within data center, copy in another data center, copy in different region. This is for fault tolerance, disaster recovery, and mitigate single point of failure.

Monitoring system must be in place to monitor the health of all the servers and components.

Future improvements

More api endpoints like user signup,etc.

More calculations considering variations in reservations throughout the year/days

Additional services, more vehicle and parking types (different sizes)

Optimizations and availability improvement based on geographic locations would be a good area to invest further. Using global load balancer so that clients get routed to the closes data center. Replicating databases between different geographic locations as a backup mechanism in case of a regional disaster