Mastering System Design Interview: Creating a Scalable Parking Garage System

Hello everyone, welcome to episode 14 of the Learn System Design podcast with me, your host Ben Kitchell.

Just at the top, I want to give some more context for the URL shortener from the last episode. There was a really great conversation over on the Discord, brought up originally by Space Script and added on by cgdzan. So sorry if I'm saying your name wrong there. I lacked an explanation for how we could have an auto incrementing number that satisfies both the requirement of being atomic while also not having it be a single point of failure.

You can view my full explanation over on the Discord if you'd like, but the short answer is you can utilize a no SQL database and have that auto increment your numbers, then have a redundant service like a set of lambdas that pull from that DB in an atomic fashion. Something like DynamoDB actually offers that out of the box.

If you want a less expensive option, you should reach for something like Zookeeper, which has the ability to use atomic messagings to keep all of your servers on the exact same configuration. My original plan was to have it be a single service that simply returns an incrementing number. Since that's not overly complex, you wouldn't need to update it and you could just host it on something stable like aws, which the likelihood of AWS going down is far larger than I need a number.

However, this podcast isn't about how would you handle something that might not happen. It's a podcast to design a system and prepare for the worst case scenario. Hopefully that helps clarify the omission from the last episode. In a similar vein, I have started implementing new changes to the podcast. Most of you should at least see a new logo. There's also a new website you should see. You know the changes start percolating as they come through. Here's a quick quiz for you.

If I did change the image, which I did, and someone doesn't see that image change, they still see the old image. Why do you think they aren't seeing the new one? What? What do you think would be causing that? And if you said the cache, you're correct. Whether it's caching in the browser, caching at the app layer, or even the CDN where the image is actually hosted and it's just cached there, it's just getting a stale version of that cache. Anyway, on to today's topic.

An interview question that gets frequently asked when you're applying at places like Amazon. Today we will be designing a parking lot system. It what is A parking lot system I actually had the same question as you when I first heard this. Maybe this is something more common in other parts of the world, but the idea of reserving a parking spot for a long time seemed very strange to me.

Nonetheless, a parking lot system is a way for someone to either purchase a ticket as they pull up into the parking lot, or reserve a spot in advance for a certain amount of time and then either way process that payment accordingly. What then are the functional requirements? Well, with this particular problem, the amount of things that you could do is seemingly endless. Maybe this is why Amazon is so keen on asking it.

It's an easy problem for less experienced engineers to get lost in feature planning and trying to design something that has 100 features rather than sticking to a good solid 3. If you promise 67 things which would be easy again for this particular system, you'll end up burning your entire time trying to plan for every edge case. Instead, as I've said before, focus on the bare bones of what the system is. It allows a user to reserve a spot and pay for it.

So for the functional requirements, we need to have a user, and since the user will be paying us actual money, we should actually make use of the user experience having security and authentication. The user should be able to reserve a spot, right? And it probably goes without saying that no one spot can have more than one user at a time. Two cars can't park in the same spot. And lastly, we need to provide a way for the user to actually pay for the spot they reserved.

We could do a lot of extras here, like having specialty spots for electric cars or compact cars or motorcycles. I've seen online people mentioning having a guidance system for how to get to your particular spot, but again, this is all overkill. We want to keep it contained to a few things. And so as I've mentioned, there's a ton of extra choices and features. But again, hammering this point home, you can always add new features later. The key is to build a good foundation that's scalable.

For that foundation, we will have the following functional requirements. We will allow for creating and authenticating a user, a user can reserve a spot, and a user can pay for their spot based on an hourly rate. And again, this problem is one of the things I point to when it comes to the idea that everyone has differing opinions when it comes to designing a system for scale. Here's why. When it comes to the cap theorem, what do you think are the two traits this system should have?

Let's walk through each one quickly shall we? Consistency? Well, one of our core functional requirements is that no spot can have more than one user at a single time, right? So eventual consistency is just not going to work. Alternatively, we need the system to always be up, right? We can't have people who can't pay their bills, especially if our system requires you to pay the bill before you're allowed to exit.

It's an absurd idea to have people be held hostage because we didn't expect our system to scale so they can't get out of the parking spot, right? And lastly, I hope that you all remember the golden rule of the CAP theorem. For those of you who don't know it, its partition tolerance is non negotiable. In today's world, you always have to have the P in the CAP theorem. So your decision will always come down to consistency or availability and never both.

Your reservation system going down should have no effect on your users being able to log in or to pay their bill, right? That's what partition tolerance is. We find ourselves then in a bit of a catch 22, right? Like consistency, availability. We kind of need both in this instance. And I've had many conversations with colleagues and in my opinion, people fall in two different camps. The first camp is have eventual consistency and rely on your system to handle everything later.

And if two people purchase the same parking spot, simply reassign them to another spot. I know this sounds crazy, but airlines book all the time and as much as we hate it, we accept it, we deal with it, the user isn't charged, then generally they will be okay with a new spot or being told like, hey, there was an error processing your charge for myself. I fall into the other camp and I'll let you decide on which one you feel better. Don't think because I'm in one camp you can't be in the other.

This is the beauty of engineering and software design as a whole, is that we can have differing opinions and have strong opinions, but we should be accepting of other opinions and be open to the idea of change. And if you have a strong argument for the other side, please email me or jump on the discord. I would love to hear it, because I am nothing if not flexible. So why then do I say consistency is more important than availability?

Well, because these days I find it easier to have something be available with an uptime of 99.99%, which is generally achievable. And I find that easier to deal with than losing customers constantly because they're angry, because they have a bad experience when you think about restaurants like Raising Cane's or Chick Fil A. These are both chicken restaurants in the United States. One of the biggest things people go to when they talk about these restaurants are the customer satisfaction.

The customer feels like they're having a great experience and that's why people go back. Yes, the food is good and that helps. But having people that are kind and patient and having a good experience ordering is really what drives a lot of their growth. So then again, I say consistency is the most important thing. The other non functional requirements are probably pretty obvious, one being security. If users using any sort of purchasing system, you need to protect the user data.

There is no argument here. Consider this a core tenet of system design. People care more about their money than most other things in this world. Charging someone an incorrect amount or leaking their credit card info is always bad. No matter how many times it happens, it is a terrible experience for the user. And lastly, we have latency. We don't want the user feeling like it takes a long time to reserve a spot or to pay their bill.

We want to make the user experience as strong and as fast as possible from end to end. And to recap on that, our system should be consistent, secure and have low latency. These are our three non functional requirements when it comes to our capacity estimates. I'm going to immediately

pull from our web Crawler episode. If you remember, we learned that 1 billion of anything a month is equivalent to 400 things, requests or whatever a second. Giving this a quick thought, I don't see us having a billion users using our parking lot system a month. That seems outlandish, right? Instead, let's do a thought exercise. What would we think is a more realistic number? For me, 1 million still seems a bit high. I think it's a good start though.

So maybe we just take it down one more notch to like 100k. 100,000 doesn't seem too crazy to me. It's roughly 3,000 a day. @ that rate, I would call us a very successful parking garage. Let's do our quick napkin math then to get a good idea of the amount of users we'll be handling a second. Again, 1 billion is 400 a second. One million is 0.1% of a billion. So that would give us roughly what, 40 cars a second? Again, seems really high. So instead, let's take about 10% of that.

Since 100,000 is 10% of a million, 10% of 40 is 4.4cars a second spread out across multiple chains of a parking garage feels a lot More realistic. And that's about my experience when it comes to, like, a busy parking garage multiplied across again, multiple chains. If we have 100 cars coming in a month, we have to expect that some of them will be making reservations in the future. A quick Google search will tell you the number of people who reserve parking spots is around 29%.

And as most of you will know when performing these estimates, I hate making things harder. And if you're in an interview, you can't Google this number and figure out that it's 29%. So instead, we're going to choose a number that seems close and makes it a lot easier for us to actually work with the data. Right. And I recommend you do this again at all times in interviews. Don't use percentages like 13, 14, 17, use 10, use 15, use 20, whatever you're best at.

If you're really great at math, and I have no doubts that some of you could probably do this, a lot of this in your head, and you're very confident, then absolutely go with those more accurate percentages. But if you're just making a number up on the spot, why not use something that's nice and round? So 25% of people reserve their spot. That means around 25,000 people a month will reserve their spot.

And if we make a rough assumption that the info we will need to be Saved is around 100 megabytes in size per user, then we can say we will need around 2.5 terabytes a month or around 24 terabytes of storage a year. And so to recap here, we will need around 24 terabytes a year. We're handling around four cars a second.

But remember, that latency needs to be incredibly low since we're handling payment processing, and a lot of the times people who reserve their spots are in a rush, like at an airport, things like that. We want the latency to be very low to get the. The user in, get their money, and have them have a great experience. Next, let's talk about our database models. This will probably be our largest undertaking yet of tables to date. We won't have a ton, but we will have more than we've had before.

And they're all important in their own way. This will probably sound familiar to a lot of you, but the first table we will have is just a simple users table. This users table will help us keep track of payment information or vehicles or spots and, and things like that. Right? It ties the user something tangible to the different parts of our system that User table will of course have a unique user id. It will have an email property, a password property created at timestamp property, as always.

But we will also have vehicle ID which will be a foreign key relation to the vehicles table. The vehicle table will have what you probably expect like a year, a make, a model and a color of a vehicle, these sorts of things. But it will also have a license plate property so that we can easily identify a vehicle. And also, as always, a vehicle ID that is just a unique identifier for this property to a table. Next, we will have a reservation table.

Again, we'll have a reservation ID that is a unique number. It'll be a primary key for the table. It will also probably be what we index on to make searching functions faster. And you know all these things already if you don't go back and listen to the first few episodes. It will also have a created at and a paid at timestamp to help us keep an audit trail for ourselves and also be able to verify purchases.

In the same vein, we'll also need a paid amount, a value to keep track of how much the user paid for a reservation. Furthermore, we'll need a vehicle id, a user ID and a spot id, which again will map to these different tables to help us have forward key relations across all of our data. Speaking of spots, we will also need a parking spot table. This will of course have a spot id, its unique identifier.

It will also have a is available and is handicap property to help identify specific things about a spot. These are the sort of things that you want to bring to an interview or to a design when you're talking with product. These little things that you think about what makes a parking lot different from a URL shortener, something like that. These like, is it a handicap spot? Is it, you know, have an is available?

Because, you know, these things won't apply to everything, but they're very helpful in showing that you can think about the specifics of a system. We'll also need a floor number and a garage ID to help us keep track of the multiple locations. And finally, we will need an hourly rate that'll be a floating point number and it helps us calculate the cost. So if we have more fancy shaded spots, if it's completely out in the sun, is there ones that are closer to the airport?

If we're, you know, a parking garage that's near an airport or closer to whatever the the thing is that you're parking at, then you may want to charge a higher hourly rate for Those premium spots. So we need to be able to have that variable cost. These locations will also need a specific table which we'll call the garage table. And it'll have just a garage ID and an address field.

Again, you know, having all of these different tables, you could go crazy with it and you know, use normal form to the fourth degree and have everything incredibly laid out. But in my experience, just showing that you think about the data and you know how the data relates and then you have specific things for the specific system is more than enough to show that you're putting thought into the system and you're not just getting caught up in the weeds.

Next, let's talk about the public facing APIs for this system. They'll be pretty straightforward. Looking at our functional requirements, we can pick out most of what we need. We will want a route to create a user a simple post request to v1user with just an email, password and vehicle information that we mentioned before. We'll go into the vehicle table that covers our first functional requirement pretty much in full. The next route will be creating a reservation.

Again, a post request to V1 reservation. We'll need a body request that has a specific spot, a vehicle ID and a paid amount that is a total calculated based on the hourly rate and the duration of which they want to actually hold the spot. We'll also need a way of fetching that reservation.

So we'll need a get request to V1 reservation with that reservation ID in the query params and then we'll obviously want to authenticate that specific user and after being authenticated they can see a full list of all of their reservations specific to that user. And finally we will need a route to actually process our payment. In this case we could have a post request to v1 payment slash the reservation ID that'll accept the reservation ID in the query param.

Again, this will need to be authenticated so as not to allow anyone to under to know, you know, the purchase cost of a specific spot for someone else. And lastly, while not really captured in the requirements, we will need a route to add, list or remove vehicles to specific users and these can be captured with the V1 vehicles prefix routes and where we have put post and get and delete and whatever else we might need for adding a vehicle.

If you've ever built a simple CRUD application, then you're familiar as part of the data flow. The actual payment will be forwarded out to a third party system to be processed fully. While we could process all of this in house for the sake of this design, we are relying on a third party system, something like Stripe.

This helps us save time to focus just on the parking garage system, while also helping us avoid that extra layer of security and handling transactions and making sure that our billing information is all taken care of and audited and everything else that comes with handling people's money. A lot of the times, as long as the main feature isn't handling business financial transactions, I will just say I'm using a third party service for these sorts of things.

In the last example you might remember me mentioning using like AWS S3 to handle bucket storage. And to me that's the exact same thing. It's another way of utilizing a third party to save time, simplify the design, and also simplify the cause of concern for the system. And now we get to the part where I normally point you to an imager link or an image link hosted somewhere down below in the Show Notes.

And for this one I'm going to try and skip that and instead talk about the design and explain my design choices. And hopefully if you find the images more helpful, drop me an email, shoot me a message on discord, and I'll try and include both, and I'll try to include both in the future. I just want to try and dial in the best way to consume for this design aspect portion. As always, the first part of the design, we should start with just a fairly bare bones setup.

We'll have a front end client that's maybe like mobile or desktop or something like that. It'll send a request to our backend service and at this point the backend service will do all the authentication, the communication to the database. And the backend service will also be communicating with that third party financial service to process those payments. As we mentioned before, for our database, I chose to go with the relational database service.

This allows to handle our data in a relational way. Since the user has a vehicle and a spot and a ticket tied to the user that's tied to the vehicle and all of these things are coupled together in the data. There's just a lot of overlap and a lot of connection between all of them. I find that using a relational database is a good place to start. And this bare bones setup should be more than enough to handle, you know, like 5K requests and not have a lot of intervention.

You know, it can handle all of our API routes without any little extra services needed at this level. Building upon that, our next version of this is handling more load and decreasing our latency. So we should Identify our bottleneck. In this case, it's probably pretty obvious if you've listened to our last episodes. The bottleneck is our database. And a quick, pain free way of getting some latency down while also not doing too much work on your database is just to add a simple DB cache.

If we find the cache isn't enough, we can also set up a load balancer, set up multiple instances of our backend service, have it be auto scaling, and again, that should also bring down our latency, as it were, if the bottleneck, instead of being the database, becomes our backend service in that scenario again.

From there, if we find that the database is still a bigger bottleneck, we can work on our indexing, we can spin out, read replicas, or even just start hashing those and setting up shards based on those hashes. These things are obviously more intensive, they obviously take a lot more work. So they're things that I would mention later as we want to scale and, you know, if we're still finding the database is our bottleneck, we can scale those things.

So be sure to think about where your bottleneck is even as you, you know, go further through this. Now that we have scaled a bit for latency, we can focus on an interesting question. How do we keep it consistent? Consistency gets tricky when it comes to systems like this, because what if I am someone who wants to buy a parking spot, but you, a completely separate person, also want to be purchasing that parking spot for an overlapping amount of time? How does the system resolve who gets the spot?

Or better yet, how can we stop someone from purchasing a spot in the first place if it overlaps with the time that someone else is purchasing currently?

The answer is distributed locking. In our first scenario, when we had a single backend service and a single db, we could have a simple lock on the backend service that would do everything we need, right? The lock would have a timer, it would be attached to that spot, and it'll either be purchased or the lock will release after like two minutes. And because it's a relational database, we have that atomic command, right?

But what happens when we have DB with multiple replicas and we have a few different instances of our backend service? If one backend service applies a lock, how do the other services know about it? We could spin out the locking service to a single service that only focuses on handling these locks.

But then, as I mentioned at the top of this episode, we have a single point of failure and we can't check every instance across the pool on whether or not it has a lock on this specific thing because then our latency goes through the roof, right? The solution, much like our already implemented cache, is actually Redis, and there are an abundance of libraries that offer distributed locking with Redis in many different languages.

And I'll actually have a link down in the Show Notes with Redis blog post about all of these different libraries and everything like that. But the simple case is you can use a Redis cluster to have multiple versions of Redis and then have a simple lock that's just a variable in Redis with a time limit for when the key should expire. Remember, Redis at its core is just a key value store with a time to live with it by default.

So having a simple variable that's like the Garage ID plus Spot ID and have a time to live of like two minutes, be your lock is incredibly helpful. When someone else tries to get that spot, you first check the cache, see if the combination exists. If it does, then it can't be purchased currently. And if not, you check the database and you check the Spot for the is available property, which will also need to be false before allowing someone to purchase a Spot.

To simplify, the database handles any spots that are already taken, and the distributed lock system in our cache will handle someone who's currently trying to purchase that Spot.

If the spot's available, then you'll set that variable in Redis with the concatenation of Garage ID plus Spot id, and this will effectively block other users for the next couple of minutes, allowing you time to get your wallet and put in your card number and everything like that to actually purchase and reserve the Spot as needed. Distributed lock management is incredibly handy when it comes to keeping concurrency in a world full of microservices.

The benefits of using Redis for a distributed lock management is it's scalable, it's performant, it has Redis clustering so that you can share keys across Redis instances, and for the most part you're probably already using it as a DB cache anyway. And lastly, to cover our basis in terms of security and furthermore help with scalability to keep our latency low, we'll split our backend service into multiple other services that can be scaled as the load gets higher.

We will need a user service for handling user creation and user deletion and all that stuff. We'll need a vehicle service for handling, adding and removing vehicles. We'll need a parking service that will handle our SPOT management, including interfacing with that distributed lock manager that I just mentioned. And we'll also need a payment service that will act as an interface for our third party financial provider. And finally, we can set up an AWS gateway.

It helps as a load balancer, it helps as an authentication service. And since it can handle a lot of load without a lot of extra lift, it also handles our need of having to scale out our load balancer and deal with the networking side of things. And at that point you've got a really strong system, it scales accordingly, it can handle load and it can handle a burst of traffic, right?

And so yeah, I think that's a really solid design and you know enough to show that you, you think about the specifics, you're thinking about the scaling, you're thinking about the problem at hand, and you have a good reason for why you're using each one of these tools. I hope now that you feel confident on taking the world to building a parking lot empire. If nothing else, you'll be able to handle the load that comes from running that empire, should it ever occur.

I'm really glad I was able to speak about distributed lock management. It's one of my favorite secret techniques to pull out an interview to show that I'm doing my homework and I'm keeping up with new fun designs and new ways of tackling old problems. If you tackled this design in a different way, you know, send me an email, drop it on Discord. Or you know, just drop it on Discord to say hello. I want to continue growing that as a resource, as part of the community.

I do my best to keep everything as free as possible. So I will never ever charge for being a part of the Discord. If you hear ads on any episodes, it's basically my way of trying to keep this free and keep it as free as possible. I'll also be working on newer ways to help me out if you can, you know, easier, cheaper ways. You know, for the time being, the best way is to support me on Patreon. Currently, I only ask for a dollar a month and you get access to episodes a week before anyone else.

And you can find the links both for the Patreon and the Discord in the show notes below. Speaking of Discord, I want to thank everyone on it for their questions, their answers, their feedback, etc. You know, just thank you for helping me grow it and, you know, be a part of this, this whole thing. And that includes everyone. But you know, not just limited to Beer, X Space Script, CG Doozen and vb. You all rock.

I appreciate you for keeping the Discord alive and just, you know, giving me great ideas and giving me feedback and, you know, asking questions. I also want to give the biggest thank yous to everyone who supported me on Patreon. It seriously means so much to me. I'm still working on updating and getting that RSS feed to help this be a better streamlined process.

But yeah, all of these people, including Lu How Mina Konji Dabatham, Jem Dhruv Shantak Shridevi Kaluri Antonio Essex Lethierry Sergey Buguera Pranav Leah Whitelaw Lucas Anderson Kalyan Dasika Sergey Buguera Anil Dugar Jake Mooney Charles Cazals Eduardo Muth Martinez Waho Soarez Adrian Kuric Gabriel Jasper Klotzel Nathaniel Sutton Florian Brighter Clavianess thank you so so, so very much. And again, if I pronounce your name wrong, just send me an audio message on Patreon.

Email Discord anywhere you can find me. Please help me help you. And sham you messaged me on Patreon you were having trouble finding the Discord. It should be down in the show notes. If it's not, let me know. I did also reply to your DM with an invite to the Discord. And yeah, thank you for letting me know that you couldn't get in it and hopefully we can get you in there and get you all taken care of.

Apart from all that, I'm hoping to start recording some episodes, some extra bonus episodes going over the Designing Data Intensive Applications book. It is, if you're not aware, it is the holy bible when it comes to learn system design.

It's a lot of what I go through for these episodes and it's something I don't go to frequently for my own work and and I'm hoping I can provide that as a bonus for people in the Patreon and then also anyone else who wants to get extra bonus content here and there. And then I'm also very curious if any of you that listen to this podcast want to hear me cover things that aren't technical or things that aren't system design.

I can talk about algorithms, I can talk about just tech news, I can talk about music, I can do other things as well. If that's something where you just like the sound of my voice or you know, whatever, just let me know if that's something that might interest you and maybe I can spin something out. But otherwise, if you, the listener, have been enjoying these episodes, please share them with a colleague or a friend. Special thanks to those of you have written some reviews.

And you know, even if you haven't written them, if you've just given it five stars, I deeply appreciate it. If you don't think it's five stars, drop me an email. Send me an email or discord message. Learnsystem designpodmail.com Remember to include your name if you'd like a shout out. If you'd like to support this podcast and help me pay my bills, feel free to jump over to Patreon and consider becoming a member.

All podcasts are inspired by Crystal Rose, all music written and performed by the wonderful Aimless Orbiter. You can check out more of his music@soundcloud.com aimlessorbitermusic and with all that being said, this is Ben I'm scaling down SA.