Requirements


Functional Requirements:


  • Allow reservation of a parking spot.
  • Process payment for the reservation.
  • Gate check-in/out.
  • Enable parking of a car in the reserved spot.
  • Support early departure before reservation time expires.
  • Handle no show.



Non-Functional Requirements:


  • need to support multiple parking lots.
  • we need to support 10-100 million DAU.
  • daily queries per parking lot 1K-10K, roughly 1K parking lots, which means total queries of 1-10 million queries per day.
  • we need to support horizontal scaling
  • low latency for digital services like browsing parking lots and spots < 200ms. for physical actions such as opening/closing a gate a couple of seconds is acceptable.
  • high availability for most of the system, strong consistency for payment.
  • environment - IoT devices for gates, parking lot sensors, mobile/web app for user
  • durability - payment data and reservation data has to be durable
  • fault tolerance - we need to handle reservation/payment failure, gates have to work otherwise users might get stuck
  • security - payment has to be secured


API Design

Relevant Models:

  • Users
  • ParkingLot
  • ParkingSpot
  • Reservation


all endpoint should only work for authenticated and authorized users.

error codes should be appropriate to user authorization based on reservations:

403 forbidden- if that user didn't reserve that spot

500 server error - in the case of server side error


for viewing all parking lots

GET /api/v1/parking-lots?page={page-number}&limit={num-items} -> ParkingLot[]


for viewing all parking spots in a specific parking lot

GET /api/v1/parking-lots/{lot-id}?cursor={spot-id}&limit={num-items} -> ParkingSpot[]


for booking a parking spot in a specific parking lot

POST /api/v1/reservations/{lot-id}/{spot-id} -> 201 created

{

startTime: ...

endtime: ...

}


for triggering a gate open

POST /api/v1/gates/{lot-id}/main/open -> 200 OK


for triggering a gate close

POST /api/v1/gates/{lot-id}/main/close -> 200 OK


for locking/unlocking a parking spot

POST /api/v1/gates/{lot-id}/spot/{spot-id}/open -> 200 OK


for locking/unlocking a parking spot

POST /api/v1/gates/{lot-id}/spot/{spot-id}/close -> 200 OK


Note: closing action for the main gate might be redundant since the gate can automatically close and the only necessary action is to open it.


High-Level Design


API - we want the system to be able to be responsive so we'll use a CDN so static data can be close to the user.

we also want to be able to spread the load across our services as well as well as user the correct service so we'll use an API gateway that will also serve as our layer 7 load balancer across regional services, and handles other services like authentication, authorization, and rate limiting.


to reserve a parking spot the user fetches data from the database, using the read server, back to the API gateway. now the user can view various parking lots, and in turn request more detail for a specific parking lot in a similar way.

eventually the user will pick a specific parking spot, which will the API gateway will use the reservations server to process the request using a 3rd party service to be secure, like stripe.


the request is then saved to the database, while for the requested duration + overhead of 10 minutes, gives the user access to the main gate only, for the parking spot it stays with specific times.


the user than reaches the gate and opens it via a request reaching the API gateway and using the gates service to trigger the gate(open/close). the user then proceeds to their respective parking spot based on the reservation and open the dedicated lock in a similar way.


when the user leaves they are able to exit the parking spot and lock it and exit the main gate by opening it up.


storage - for the storage we'll use a relational database like PostgresDB.

out data models are:

User - column of id(primary key), name, email, createdAt, etc.

ParkingLot - id(primary key), address, capacity, createdAt, etc.

ParkingSpot - id(primary key), parking lot id(foreign key), status.

Reservation - id(primary key), id(foreign key), parking lot id(foreign key), startTime, endTime, createdAt, etc.

Gate - id, status


caching - we'll use a one instance of Redis as a cache aside to keep the most looked up data. another "pending" Redis instance to aid the reservation service - when a user wants to book a parking spot, the id of that parking spot is saved to the cache with a TTL with a value of 15 minutes. when another user wants to see the available parking spots the ones in the "pending" cache. one of the user will lock it first and hence it will prevent an option of double-booking. when a reservation transaction ends successfully the DB already know that the status of that parking spot is now RESERVED, and won't show it again until it is freed. if the user reserving quits, transaction fails multiple times or the reservation time end, that user will be kicked out of the reservation page and the entry in the "pending" cache will be removed since the TTL time ended.


handling burst traffic in a case of an event





Detailed Component Design

latency - we've already introduced CDNs and caches to lower the latency. we can add indices to the various database table. basic indexes(using b-tree) for the id's are good, and we could also use an index on the parking lot's name/address. in reality a better option would be to use the PostGis extension to PostgresDB and index the parking lots based on the location, since users would most likely search a parking lot based on a needed location.


scalability - we have 100 million DAU and around 10 queries per user throughout the day. lets assume a unformal distribution throughout the day, and we get 10K requests per second. so we need multiple server instances to handle the viewing/lookup service and the reservation service, also the gates but at a smaller scale. each of these scaled up services performs roughly the same amount of work and intensity so we'll also add a L4 load balancer with a round robin strategy to distribute the load. rough estimates of 1B registered users lead to about 0.2TB of data, total parking lot data of 1000 of them is roughly 0.2 MB, total parking spots size is roughly 1 GB and total reservations across a single day is 5GB. which means a single optimized instance of PostgresDB can hold all the data for well over 10 years.


rate limiting - well use a token bucket algorithm and add a tokens table to the database to keep track of how many times a user tries to book parking spot to prevent parking spot scalping. also when this happens return meaningful response 429 too many requests and in the header add a retry-after and a time.


in case of request failures we can introduce timeout and retires with exponential backoff with jitter. as well as


for handling burst traffic, in case of an event in some arena nearby, we can introduce a queue to keep people from overloading the services and only allow a fixed amount so the servers won't crash under the load. once a user finished, the user from the top of the queue is granted access.


durability - for the database we can introduce a secondary database and snapshots every hour. we also want redundancy on the Redis instances since we don't want double booking and we don't want a thundering herd on the database.


cache - for the "pending" Redis cluster, which is using a locking mechanism, we'll use the TTL eviction policy with 15 minutes, which is a standard for reservations. for the viewing Redis cache we'll use an LRU eviction policy to keep the data fresh and also a TTL of 30 seconds to prevent bloating.


we do want to achieve high availability so we can introduce backup replicas, as stated before, to achieve that.


to achieve strong consistency during the reservation phase, we use a dedicated "pending" Redis cluster, which again is using a Redis locking mechanism, to hold data of a spot being reserved at the moment but the payment process for it hasn't finished yet. the locking mechanism prevent concurrent updates to the same entry at the database.

Redis provides a simple mechanism for implementing distributed locks using the SETNX command, which sets a key only if it does not already exist. When a user attempts to reserve a parking spot, a lock can be acquired on that specific spot. If two users try to reserve the same spot simultaneously, the first one to acquire the lock will proceed, while the second will fail and receive a message to try another parking spot. the strategy is basically a 'Check-Then-Commit' strategy.

the cache save the unique id of the spot and the id of the pending user with TTL with a value of 15 minutes. that way there is no double booking - a single user is registered first and enters the cache, the other one won't even see the spot as available since the reservations server fetches data from both the database and the cache and only show data from the database but not from the cache. after the user is done paying for the parking spot the information is written in the database and either cleared from the cache by the TTL eviction policy or manually by the reservation server that batches 'done/processed' requests. when a user leaves the parking spot, we can see it by him using the opening the parking spot gate, we update the database that the parking spot is available again, unless another person has reserved it in advance, and in that case we leave it as reserved.


handling overlapping intervals - will be done by the frontend/mobile app, reservations service and database(using a constraint which will be checked using CHECKED). each one should only allow reserving a spots in intervals of 10 minutes. a spot is allowed only if it doesn't overlap with existing reserved intervals, which could be seen on the client. also start and end times of the reservation must be valid, meaning start < end and end-start >= 10 minutes.