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.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10