System requirements

Functional:

1. Users can reserve a parking spot.
2. User pays for the reservation.
3. User can park a car on the reservation.
4. User can leave the parking spot before the reservation time expires.
5. There are three types of parking lots, compact, standard and one with an electric charger.
6. We handle the case in which the user makes a reservation but does not show up. In this case, we charge the user for 2 hours and cancel the reservation automatically after 6 hours.

Non-Functional:

1. Scalability - Our system will be used by a company with 1000s of parking lots all across the country.
2. Consistency - A parking lot being displayed as empty on the system should actually be empty, our result should hence be consistent at all times.
3. Availability - We try to ensure high degree of availability although, we are prioritizing consistency over availability.
4. There can be other considerations, like parking indoor or outdoors, parking close to the entrance of the parking lot for quick entry and exit, car wash service while the car is parked but these would not be addressed in this design.

Capacity estimation

1. Assumptions
   1. Company operates in 10 countries
   2. Company has roughly 100 parking lots in each country, on average
   3. On average, each parking lot has a size of 100 cars, 20% of which would go towards compact cars, 70% towards standard cars and 10 % towards EVs.
   4. Each parking lot gets 100 reservation requests per day.
2. Estimations
   1. 10 * 100 = 1000 total parking lots
   2. Each user sends 2 requests to our server on average, we have 1000 parking lots each with 100 cars, totaling to 100,000 cars. Total requests served in a day = 2 * 100,000 = 200,000 requests a day.
   3. Each request consists of -
      1. Unique User ID (64 Bytes)
      2. Car Type (1 Byte)
      3. Reservation Start Time (8 Bytes)
      4. Reservation End Time (8 Bytes)
      5. Totaling roughly 100 bytes
   4. Total data that needs to be stored in a day = 100 * 200,000 Bytes = 2 * 10^7 Bytes = 20 GB
   5. In one year, we would need 365 * 20 GB = 730 GB of storage
   6. In 10 years, we would use 7300 GB or roughly 7.5 TB of storage

API design

APIs used by the user would be the following -

1. checkCapacity (lotID, vehicleType, startTime, endTime) - Returns the number and location of the available parking spots based on the given parameters.
2. makeReservation (lotID, spotID, userID, startTime, endTime) - Makes a reservation in the lot with lotID and in the spot spotID, the spot is selected by the user. This function returns a reservation ID auto generated by our system.
3. makePayment (reservationID, userID) - Make a payment for a reservation.

APIs used by the Parking Lot staff would be the following -

1. vehicleArrived (reservationID, dateTime) - Marks that a vehicle has arrived for the given reservation ID.
2. vehicleDeparted (reservationID, dateTime) - Marks that a vehicle has departed for the given reservation ID.

Database design

Based on the estimates done above, we should go for a database that offers high consistency, for that purpose, going with a relational database makes sense. A database like MySQL or PostgreSQL which used Single Leader replication would handle write conflicts well. Among the two, we go with Oracle MySQL since it is more equipped to handle cases where might run into write conflicts, since it uses pessimistic concurrency control in the form of Two Phase Locking.

Our database can be sharded based on the region, we just need to make sure to replicate data across data centers to avoid data loss in case of a failure.

Our tables would look like given below.

1. Reservation
   1. reservation_id Primary Key
   2. lot_id Foreign Key
   3. user_id Foreign Key
   4. start_time
   5. end_time
   6. vehicle_type Foreign Key
   7. payment_status
2. Lot
   1. lot_id Primary Key
   2. contact_id Foreign Key
   3. capacity
3. User
   1. user_id Primary Key
   2. first_name
   3. second_name
   4. email
   5. phone
   6. vehicle_id Foreign Key
4. Vehicle
   1. vehicle_id Primary Key
   2. vehicle_type Foreign Key
5. Vehicle Type
   1. vehicle_type_id Primary Key
   2. vehicle_type_name
6. Transactions
   1. id Primary Key
   2. user_id Foreign Key
   3. reservation_id Foreign Key
   4. time

High-level design

1. CDN caches static content for better performance. A CDN service like Akamai or Cloudfare can be used. This is horizontally scaled.
2. Rate Limiter protects our system from Distributed Denial of Service attacks. This is horizontally scaled.
3. Load Balancer balances load on our servers using a weighted Round Robin scheme. This is horizontally scaled.
4. API server uses Redis cache for performance gains.

flowchart TD CL[client] --> CDN[CDN] CDN-->RL[Rate Limiter] RL --> LB[Load Balancer] LB --> GW[API Gateway] GW --> RES[Reservation Server] RES --> CC[Cache] RES --> DB[Database] RES --> MQ[Message Queue] GW --> TX[Transaction Server] TX --> DB TX --> CC MQ-->PAY[Payment System]

Request flows

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

reserve_spot() is handled by Reservation Server, which creates a new entry in Reservations table.

It would create a request for payment, which is queued by Message Queue and submitted to the external Payment System.

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 Server may return helpful information such as estimated time spots may open up in the future.

vehicle_arrived() and vehicle_left() are handled by Transaction Server, which modifies the Transaction table to keep track of vehicle check-ins and checkouts.

If vehicle does not arrive after some number of hours (e.g. 24 hours), 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.

sequenceDiagram Client->>+Reservation Server: reserve_spot() Reservation Server->>+Client: reservation_ID, price Client->>+Reservation Server: pay() Reservation Server->>+Payment System: Payment Request Payment System ->>+ Reservation Server: Payment Result Parking Lot ->>+ Transaction Server: vehicle_arrived() Parking Lot ->>+ Transaction Server: vehicle_left()

Detailed component design

See Sequence Diagram. It 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.

One important algorithm is how to find an open spot when reserve_spot() call is made.

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 be:

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

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 this algorithm further, if further optimization is required.

The payment for the service will be redirected to an Payment Service Provider like Stripe or VISA since payments need a high degree a security which will be expensive to implement from scratch. We can create a ledger to record all payment transactions and then send the daily report to our provider for cross checking.

During our payments, we can make use of idempotency to make sure payments for a transaction happen only once. We will need a unique key generator for this purpose, for which we can use a Base 62 unique ID generator. The unique transaction ID can serve as our idempotency key.

Trade offs/Tech choices

1. The choice of database (relational in our case) is important since a relational database can maintain a high degree of consistency, whereas non-relational databases would have struggled with that. A relational database is also able to better handle race conditions better, which is crucial in our design. Two users should not be able to book the same spot in any condition.
2. A non-relational database would offer a higher degree of horizontal scalability, improving performance.

Failure scenarios/bottlenecks

A problem could in cases where a large number of people try to make a reservation in case of an event, like a concert for a popular music band or artist, classic thundering herd problem. This could overwhelm the system. Although, it should be pointed that our transaction system would only receive requests proportional to the number of parking slots we have, which is not much.

To combat this, we horizontally scale all components, rate limit requests to maintain smooth operations. We also replicate aggressively to handle data loss in case of a disaster. Also, a monitor system could be put in to check the health of all our services.

Future improvements

1. Adding more types of vehicles and parking spot types.
2. Have the load balance redirect a request to the geographically most optimal server.
3. We could provide the functionality to let the user cancel a reservation up until a day before, processing a full refund in case a payment is made.
4. Implement dynamic rates for the parking spots based on current demands.