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:

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.
Create a bitmap with 1's representing time between start_time and end_time.
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.

Trade offs/Tech choices

The biggest decision point was the database. For this service, I chose Relational Database over NoSQL Database. The data size, estimated at increasing ~300MB in 2 years, is well within the capacity of a RDB. RDB provides strong consistency, which is beneficial for a reservation service. Once a reservation is made, the user needs the system to honor it 100%, without the risk of double booking or a reservation mistakingly deleted.

NoSQL database, for example MongoDB, would provide a better horizontal scalability than RDB. But for this service, I decided the benefit of RDB outweighs that of NoSQL DB.

Failure scenarios/bottlenecks
One bottleneck scenario is when a large number of people gather in a place near one of the parking lots, e.g., for Olympics Games.

This would put a burden on the reservation work flow (reserve_spot(), pay()). Transaction Server would be fine, as the number of requests to Transaction Server would be limited by the physical limitation of the parking lots (i.e. how many spots they have).

To prepare for such an event, all the software components must be replicated horizontally to have enough capacity. Rate Limits have to be configured to smooth out extreme level of traffic.

The database tables must be replicated in multiple ways (e.g. a copy within data center, a copy in another data center, a copy in a different region) for fault tolerance and disaster recovery.

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

Future improvements

I think this builds a foundation for more feature development in the future, e.g., additional services, more vehicle and parking types (very large vehicles, buses and trucks, motorcycles and bicycles, charging stations).

Optimizations and availability improvement based on geographic locations would be a good area to invest further. For example, using Global Load Balancer so that clients get routed to the closest data center. Replicating databases between different geographic locations as a back up mechanism in case of a regional disaster.

Question

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:



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.
Create a bitmap with 1's representing time between start_time and end_time. 
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.

Trade offs/Tech choices


The biggest decision point was the database.  For this service, I chose Relational Database over NoSQL Database.  The data size, estimated at increasing ~300MB in 2 years, is well within the capacity of a RDB.  RDB provides strong consistency, which is beneficial for a reservation service.  Once a reservation is made, the user needs the system to honor it 100%, without the risk of double booking or a reservation mistakingly deleted.  



NoSQL database, for example MongoDB, would provide a better horizontal scalability than RDB.  But for this service, I decided the benefit of RDB outweighs that of NoSQL DB.  



Failure scenarios/bottlenecks
One bottleneck scenario is when a large number of  people gather in a place near one of the parking lots, e.g., for Olympics Games.  



This would put a burden on the reservation work flow (reserve_spot(), pay()).  Transaction Server would be fine, as the number of requests to Transaction Server would be limited by the physical limitation of the parking lots (i.e. how many spots they have).  



To prepare for such an event, all the software components must be replicated horizontally to have enough capacity.  Rate Limits have to be configured to smooth out extreme level of traffic.  



The database tables must be replicated in multiple ways (e.g. a copy within data center, a copy in another data center, a copy in a different region) for fault tolerance and disaster recovery. 



Monitoring system must be put in place to monitor the health of all the servers and components.



Future improvements


I think this builds a foundation for more feature development in the future, e.g., additional services, more vehicle and parking types (very large vehicles, buses and trucks, motorcycles and bicycles, charging stations).



Optimizations and availability improvement based on geographic locations would be a good area to invest further.  For example, using Global Load Balancer so that clients get routed to the closest data center.  Replicating databases between different geographic locations as a back up mechanism in case of a regional disaster.

Accepted Answer

⚹ Your design for the efficient parking lot system is quite comprehensive and well thought out. Here is a detailed feedback on the specific components you mentioned: ⚹ ### Detailed Component Design ⚹ The sequence diagram you provided effectively illustrates the flow of messages for client reservations and payments, as well as notifications to the Transaction System. This is crucial for understanding the interactions between different components of your system. ⚹ ### Algorithm for Finding Open Spots ⚹ Your algorithm for finding open spots is efficient and well-suited for the problem at hand. By dividing the day into 15-minute slots and using a bitmap to represent occupied/unoccupied slots, you have created a space-efficient solution. ⚹ ⚹ The steps of the algorithm are clear: ⚹ 1. ⚹ Convert `start_time` and `end_time` into indices. ⚹ 2. ⚹ Create a bitmap with 1's representing the time between `start_time` and `end_time`. ⚹ 3. ⚹ Compare this bitmap to the bitmaps representing occupied time of parking spots. ⚹ 4. ⚹ Scan from parking spot 0 (closest to entrance) to N (farthest from the entrance) to find the closest available spot. ⚹ ⚹ The use of an Interval Tree for further optimization is a good consideration for future improvements. ⚹ ### Tech Choices ⚹ Your choice of a Relational Database (RDB) over a NoSQL database is justified given the requirements of your system. ⚹ ‖ ▪ ⋮ **Data Size**: The estimated data size (~300MB in 2 years) is manageable within an RDB. ‖ ‖ ▪ ⋮ **Consistency**: RDBs provide strong consistency, which is crucial for a reservation system to avoid double bookings or accidental deletions. ‖ ‖ ▪ ⋮ **Scalability**: While NoSQL databases offer better horizontal scalability, the benefits of strong consistency in an RDB outweigh this for your use case. ‖ ### Failure Scenarios/Bottlenecks ⚹ You have identified a potential bottleneck scenario during high traffic events, such as the Olympics. Your preparation strategies are sound: ⚹ ‖ ▪ ⋮ **Horizontal Replication**: Replicating software components horizontally to handle increased capacity. ‖ ‖ ▪ ⋮ **Rate Limits**: Implementing rate limits to manage extreme traffic levels. ‖ ‖ ▪ ⋮ **Database Replication**: Replicating database tables within the data center, across different data centers, and in different regions for fault tolerance and disaster recovery. ‖ ‖ ▪ ⋮ **Monitoring System**: Setting up a monitoring system to track the health of all servers and components. ‖ ### Future Improvements ⚹ Your suggestions for future improvements are forward-thinking and practical: ⚹ ‖ ▪ ⋮ **Additional Services**: Introducing more services and accommodating different vehicle types (e.g., large vehicles, buses, motorcycles, bicycles, charging stations). ‖ ‖ ▪ ⋮ **Geographic Optimizations**: Implementing geographic optimizations such as Global Load Balancers to route clients to the closest data center and replicating databases across different geographic locations for regional disaster recovery. ‖ ⚹ Overall, your design is robust and well-prepared for both current needs and future expansions. ⚹

Sia