System Design: Hotel Booking

[@SDFC]

NOTES & CORRECTIONS: --- • I have come to find that this is actually Square's ONLY system design interview question for at least L5 and L6! • Files: • Pastebin of the text file from the right half of my screen: pastebin.com/uzyyrXJQ • Excalidraw link for the final diagram from the video: excalidraw.com/#json=qqyfbvt3VZW0fCgCzdg6r,6CNHryEEkM0xH_qfcidxnQ • Imgur album of each "checkpoint" and approach from the video: imgur.com/kUGt514 I've gotten a lot of feedback that the scale I designed for was very unrealistically high (which was kind of the point, because none of the 4-6 system design books that I own actually cover distributed transactions all that well...) AND a viewer has found a phenomenal way to do manual sharding that would avoid having to do distributed transactions at all, so: I have created the following draft of 8 total approaches to this problem: imgur.com/R8LO4Rm • Approach 3 is probably all that you'd ever need for the scale that this problem would usually be presented with • Approach 4 uses the sharding idea that was found for scaling up writes without adding distributed transactions • Approach 5 through 8 are completely unnecessary but demonstrate ideas and approaches for handling distributed transactions that I wish was more accessible in the materials that currently exist for system design interviews (I literally have 20 books on system design, and I'm still not happy with what I've been able to find) • The biggest piece of content that's missing from the infographic of 8 approaches is currently the pros & cons of each approach. I'd actually like to do a much more cleaned up and thorough recording of this video at some point, and it will be driven off the infographic of 8 different approaches attached above in this comment that's currently a draft.

[@TheChrool]

I used this in an interview for L5 at square, and they told me I failed because my SD was too advanced for the requirements and they didnt think the db datastructure would work well. I guess it really depends on how the interviewer is feeling on the day.

[@wij8044]

I ran into a similar issue where my interviewer informed me my estimations for booking were astronomically high. Turns out my interviewer was right, the numbers in this video for calculating data sizes is too high.

[@rey-op7je]

What it means the DB data structure wont work well?

[@LiuLutetium]

Why have a separate inventory and reservations DB?

[@ZhiminHe]

first, you don't need to update both inventory and reservation. inventory can be inferred from the reservations. secondly, it's okay for inventory to be out of sync sometimes - the user might see something as available but the booking can fail. that happens occasionally on real websites and it's acceptable.

[@whyrutryingsohard]

There is the common case the room will be "holded" for certain user for a period of time (let's say 30 mins) By that requirement we can still put the record in inventory or redis without making the real reservation, this pattern is used by common high-volumn e-commerce website (e.g. alibaba)

[@DavidBarnett-p7f]

Thank you for the video! My brain is stuck on one thing :) I see you would want to use a string for the price so you don't have to worry about overflow depending on the currency, but I think what you lose may be more than you gain. Assuming your database supported a reasonable range of costs (64bit integers would for sure, 32 most likely would unless it's a hotel on the moon :)). It would make more sense to store a common currency (e.g. dollars) and do any conversions per customer? You could store cents instead of dollars if you're concerned with floating point errors. Using a string would mean you wouldn't be able to do very useful things like ask the database "Give me all rooms which are available and cost < $40". If you store a string then you would be doing a lexicographic comparison and "40" > "200". If you stored a string you would have to pull all available rooms into memory, convert the price to a string and then filter. This would be way more expensive in time, processing power, and bandwidth than pushing the query down to the database. Storing a string makes more sense to me on the payment side. Depending on the conversion you may have to support fractional cents. But, you also aren't as likely to do as many queries for ranges for payments than you are to query against room cost. I'm curious what others think and thank you again!

[@StyleTrick]

Really good content, glad you went into the details that a lot of system design seem to skip!

[@blumaukko1790]

Super high quality content! Thanks for sharing. Would be great to see a video on Zookeeper and how exactly it helps with distributed TXs.

[@SDFC]

Database Internals by Alex Petrov has several chapters going over how distributed transactions work in several real-world databases and services, such as Spanner and Calvin

[@johnhancock2206]

@@SDFC also Zookeeper lecture from MIT course kzbin.info/www/bejne/ppPQqqWEn9-Xes0

[@abhishekdhillon7110]

In some system design videos, I see multiple services talking to a common DB which is usually a big NO NO going by microservices best practices. Any opinions on that?

[@SDFC]

I think it's acceptable for services to share a database when they're owned by the same team (which was relatively common at least at Amazon) But if services owned by two different teams are directly accessing the same database, then yes, that's a pretty big NO-NO 😊 Something that's rather unusual about system design interviews is that there's typically not much consideration for designing a distributed system in a way where multiple teams would be working on it. I have explored that concept a bit in at least one or two other videos. Even in a senior role, you might do "cross-team work", but it seems like there typically shouldn't be design work at that scope to make a "full greenfield end-to-end design spanning multiple teams" -- I think this might be a different story for principal engineers though, so I'm probably going to try to ask one about their thoughts on that at some point. In practice, some extra splits might be determined by presenting to upper management some trade-off between throughput of work on some initiative vs the headcount that can be allocated, while also considering the bare minimum scope since certain things probably just can't be done without however many infra components

[@abhishekdhillon7110]

Thanks for the detailed explaination. This was very helpfull. Keep up the great work. 😊👍

[@planschmuh]

Thanks, buddy, this helped me a lot with my first ever system design interview. I got an L5 top band offer from Square. Let me know if and how I can buy you a beer!

[@alicezhang3504]

Why are the inventory table and reservations table on different databases? If they were on the same database could we avoid the need to do 2PC? Is it because of the sizes of the tables?

[@tianwenchu1663]

A very good point, however I think the data storage and load request distribution between inventory and reservation can be much different. Reservation may be shared on userId, if we have certain requests of checking one person's total reserverations within 2years.

[@nandinisengupta9928]

I had the same question. He briefly explains this at this kzbin.info/www/bejne/d53IaHmkbpdkfbM - "when you have multiple tables, you cannot do partitioning"

[@aaryanbhagat4852]

Quite informative, I willl suggest some minor timestamps for these long form of videos.

[@SDFC]

Great idea! I've marked that as something that I want to do with future videos. I'll try to get around to some of the already existing videos this weekend. Thanks a ton for the suggestion! :)

[@kinako.omochi-]

Thanks for the great tutorial! I think DynamoDB supports ACID with Transactions operations which can perfectly handle the all-or-nothing.

[@yunaf4609]

Thanks for the explanation! This was great!

[@boombasach]

Extremely good content. I think an improvement area could be deep diving into actual reservation with some state management - like reserved, blocked, booked, canceled etc.

[@zhehou844]

(Should 'roomsCount' and 'roomsRemaining' be in another table other than Inventory? Otherwise, if a room is reserved, all the room records in Inventory need udpate those 2 attributes?) - I see now. You mean we just select a random available room, right? But we can also have 2 tables, one is for general room available information, and one is for each room's available information?

[@John-nhoJ]

For the inventoryDb, how many different date entries does a single room have? Does it have one row for each date for the next two years?

[@SDFC]

There is a record for every single date. Depending on whether the schema does a counter for roomTypeId or rooms are individual records (there was 2 approaches for the schema), you would either have one new date entry per roomTypeId or possibly per room. As for "next two years", You can either pro-actively generate records with a nightly batch job or something like that OR alternatively use the absence of a record to "show" that there are no reservations for it (e.g. when you're doing the roomTypeId counter approach, you could "count up" the number of bookings for a given roomTypeId and also store the max counter for that roomTypeId either denormalized on each record or in some kind of cache thing)

[@functionator]

@@SDFC Have you considered using a one-to-many relation between room and room reservations? Room reservations will contain the room_id as a FK and have start/end date columns. Each room reservation record can be created when a reservation is made. The query shouldn't been too difficult to run as well, but possibly slower.

[@functionator]

Reading chapter on Transactions from DDIA. Realized the approach I suggested wouldn't work, primarily due to write skew with phantoms. Essentially, the database cannot create a lock on a record (reservation record) that does not exist. So materializing it with precompute will allow records to exist and locked.

[@dobriykote]

One issue I noticed in your design is that booking service accesses inventory DB - according to MSs design pattern the service would never access other service DB directly except through the service itself. But I like initial estimation section. Thx!

[@stefancovic6493]

For Inventory DB, why not use some unique Id as PK and set it as UUID? Why date in inventory DB, is it not better to have a from and to fields in reservation DB? Isn't it better to check if room is available by checking the dates you want reservation for with the reservations inside Reservation DB? Btw, great video, learned some new things, and to what details I need to pay attention. Thank you!

[@SDFC]

So, with a sharded DB, the auto-increment feature breaks down a bit unless you also put a machine ID in there. However, that unique identifier isn't really going to add much value because you're doing look-ups by the buildingID, roomTypeId, and date anyways. I guess that does perhaps help a bit with the write operation if you give the primary key during the listings/read phase of what the end user does. However, I haven't seen that done very much in practice on the distributed database set-ups that I've seen in the industry. I think that does make sense to use to and from fields for the reservation DB; I'm not sure why I hadn't really thought about doing that instead of the current approach where the range is flattened into multiple records. As for determining whether a room is available by checking dates in the reservation DB, that would be a bad idea because you'd have to run an expensive count operation and you'd also potentially have to check both the to and from data for each of the records you're scanning through for whether the requested availability start date is between the reservation start and end date. The 2nd half isn't quite as bad, but the count aggregation part would be.

[@stefancovic6493]

@@SDFC Thank you! This clears things up!

[@baiyuli97]

How would 2PC work across two dynamoDB tables? AFAIK there is no concept of making a request to lock a key (i.e. prepare phase) in the DDB API.

[@baiyuli97]

Also, it would be good to specify how Raft or zookeeper would actually facilitate the transaction

[@mounikachillamcherla3526]

What about search for listings DB? Don't we need geo based db like GoeHashId as one of the fields or do quad tree based search ?

[@SDFC]

I kept the scope of the problem constrained. I think the hotel booking problem typically doesn't include geo-based search, but I could totally see an interviewer doing that if they wanted to add a "going the extra mile" feature to the problem. I did cover a couple geo-based problems that do show how to do something similar: - proximity service - uber However, I do think that adding geo-based search functionality would be a particularly interesting feature for this problem since it'd typically be very read-heavy traffic volume, unlike uber. (Proximity service / Yelp is the most similar to how geo-based search would get added for this problem.) I hope to cover geo-based search for the hotel booking problem as a "follow-up feature" if I make another expanded video about this problem. :)

[@simonhuang3193]

Instead of trying to do atomic transactions across different database nodes, could we instead shard the data by a shared id? For example sharding by roomTypeId. That way the Inventory and Reservations can be stored on the same database node and we wouldn't need to use ZooKeeper to coordinate transactions across nodes for booking rooms.

[@SDFC]

that’s actually wildly insightful and I think it’d actually work (if anything implemented it) however, you usually kinda have to do “federation” (github.com/donnemartin/system-design-primer#federation) prior to partitioning, and I don’t know of any NoSQL databases that support “cross-table partition keys” (there’s actually no term yet for your idea that I’m aware of) spanner or cockroachdb are the only ones that I could imagine might do something like that, but I’m skeptical they actually do have it implemented I think roomTypeId would work if a partition was just 1-to-1 with a value, but it probably doesn’t sufficiently break it down into small enough partitions-for reference, cassandra does 100 partitions by default (IIRC) and then evenly distributes them across however many nodes that you’re running that instance on-so you’d probably still want to use roomId+buildingId (or at least one of those two attributes) since the reservation and inventory involved in the transaction should always match for both tables (roomTypeId should always match as well, but might not have have enough variation in the values on its own)

[@simonhuang3193]

​ @System Design Fight Club I was thinking more of having a monolithic database instead of federation. I found a section in Alex Xu's System Design vol 2 that goes into more detail, the "Data consistency among services" section under the Hotel Reservation System. Unless I understand it wrong, couldn't you prevent the need for 2PC / Paxos / Raft by making sure no atomic transaction needs to access more than one database node? I also didn't think NoSQL databases would be an option for this problem, that would be interesting to consider! I figured at least a Repeatable Read isolation level would be required to solve the double-booking issue. I'm not sure if any NoSQL databases can achieve that isolation level

[@SDFC]

@@simonhuang3193 I actually ended up talking about this with the principal engineer that runs A Life Engineered, and I think you're definitely correct that 2PC could be completely avoided while scaling up writes AND maintaining real-time constraints through coordination. I actually have a list of around 8 different approaches to this problem now, and I really hope to retry this problem again sometime soon and include that approach as one of the options for tackling a super high write volume

[@simonhuang3193]

@@SDFC That's awesome, thanks for all of your hard work and content!

[@SDFC]

the list of 8 approaches is now available in the pinned comment at the top of the comments section

[@Am-zr4pl]

Thank you, this was a great design.

[@markj6302]

thanks for the video. why is the primary key 4 attributes? i'm a newish (3yrs) full stack enginner but have lent a little more into frontend and have barely touched DB's, any resources you could suggest? Thanks!

[@markj6302]

some more questions, why would the admin need their own admin service? couldn't they use the booking service with elevated privileges? do you think caching is important to talk about? i imagine in this case you'd want a server cache with write-through

[@nikolai.x]

What are the resources without links? Grokking and Alex Xu?

[@SDFC]

Here's a pic that I used to post around places that organizes a lot of my favorite resources into one place: imgur.com/a/7Ay2Uf8 The things you're looking for are from the books section on the left side of the pic... I really ought to just organize this into a PDF or something that I can give people a link to. Here they are again in text format (hope youtube doesn't completely butcher the formatting here): * System Design Interview (Volume 1) by Alex Xu * Amazon: www.amazon.com/dp/B08CMF2CQF/ * ISBN: 979-8664653403 * System Design Interview (Volume 2) by Alex Xu * Amazon: www.amazon.com/dp/1736049119/ * ISBN: 978-1736049112 * Grokking the System Design Interview * designgurus.org/course/grokking-the-system-design-interview * Amazon: www.amazon.com/dp/B09NRJT1NF/ * ISBN: 979-8766433668

[@Panikulam]

Why is dealing with floats for money a bad idea?

[@vhmolinar]

Just one consideration: page view != reads as much as reservations != writes. A reservation would include a few reads along with some upserts.

[@ziggyzhang4156]

20:54 I don't understand how paxos or Raft consensus algorithms fit into the picture here? In this scenario we have to use 2 phase commit because we are writing different data to 2 entirely different databases, it's not like consensus algorithm which is used for transaction writes among equivalent nodes for the same database, in those cases, paxos/raft achieve even better reliability but functionally equivalent to 2PC, but not in this heterogenous distributed transaction case, right? Consensus algorithm relies on tolerance of partial failure, which is not the case here --- all participants have to succeed or fail together. Also after you mentioned outsourcing to those consensus algorithms, you then mentioned "outsourcing to Zookeeper", my understanding though now you're just coming back to 2PC but just saying to make Zookeeper to do the coordinator job for you, so it doesn't have anything to do with paxos/raft any more, is that right?

[@anupamdialpad]

My understanding is that 1. Zookeeper is used to get a Lock on the 2 dbs. Lock ensures atomicity on the 2 dbs. 2. Since Zookeeper runs in distributed nodes, it is fault tolerant. Whereas Booking service is not fault tolerant since it runs on a single node. 3. Zookeeper uses Paxos to maintain the transaction logs on all the nodes in the Zookeeper cluster. Hence a consensus algorithm is required.

[@ziggyzhang4156]

@@anupamdialpad yeah if the consensus stuff was for zookeeper that makes sense. Don't think that's what the video was saying or at least was not made clear there lol

[@jofla]

subscribed, thanks for the video!

[@alfonsocvu]

Great channel name

[@alicearies]

There is 86400 seconds in one day, not 100k. I guess that was an approx, rounding up? (a lot)

[@SDFC]

Those numbers don’t have to be exact; you just want to get within an order of magnitude. Most people just round it up to 100k, otherwise doing the math by hand in real interviews would be significantly more challenging. It’s also rather rare to do these machine count estimates in interviews to begin with - I landed several competing senior offers back in early 2022 without doing any machine count estimates. Google and Facebook expect them for senior+ roles though. (Also, early 2022 was admittedly a much different labor market)

[@numbsafari]

I really recommend digging in more to how the payment processor side works. I think if you were to dig into that, you'd learn some valuable things that you could then apply to this design and make it better, both technically simpler and more able to meet various real world business needs. One thing this sort of solution can't address is that when those coordinated writes roll back, you are going to lose a lot of information about end-user intention. They requested a room reservation, but it was declined. You lose that information if the solution is to erase the room reservation with transactional semantics. Having a way to see those failed room reservations is probably valuable information both for customer service, as well as to identify and understand customer demand for limited resources.

[@SDFC]

I did actually end up digging into how a payment processor (specifically, stripe) works for my next topic on inventory tracking systems. For that one, I specifically wanted to expose an interface for distributed transactions, so it particularly made sense there. Otherwise, I do agree that payment processors are very valuable to have an understanding of how they work despite being a bit on the "domain knowledge" side; so even overall, that's a very great call out, and I really appreciate the input on that. :) "when those coordinated writes roll back, you are going to lose a lot of information about end-user intention" Well, for partial failures, you either need to drive it forward (something like retries) or drive it backwards (rollback or compensating transactions if you're doing sagas), and in this case, it's more reasonable to drive it backwards. As for the lost user info, in the real world, it makes a lot of sense to have lots of user analytics and metrics on stuff like that; I agree.

[@numbsafari]

@@SDFC if the point is to do an interview and get a job, then I think this is a bad approach. If the point is to show a text book example of using distributed transactions at the business service layer, then ok. But you haven’t really discussed the trade offs, and anybody interviewing your for a job where this is relevant will probably discount you as a candidate for saying “I really want to do transactions here”, because the point is to solve the problem, not force a technical choice. But, maybe that’s just me. Seems to be consistent feedback, though.

[@karelvanderwalt3625]

miro?

[@SDFC]

I'm using excalidraw. I've heard of Miro but haven't really tried it out. Another one that I particularly liked at work is draw.io

[@numbsafari]

Another issue with this design is that you have multiple deployment units, services, that are reading and writing to the same underlying physical storage. That is going to make data migrations incredibly annoying and error prone to roll out.

[@SDFC]

Data migrations definitely have been incredibly annoying whenever I've seen similar patterns to this one in the real world, yes. We typically try to minimize the pain by exclusively adding new attributes, rather than trying to rename any of them or have a pre-existing attribute suddently start returning a very differently formatted or computed value (e.g. unix epoch timestamp int, such as 1666246040, converted to ISO 8601 string, such as "2022-10-19T18:30:00Z" -- which we'd do by creating a new attribute rather than changing in-place, and then beginning to populate the new field with the appropriate value, doing a backfill, and then finally updating the business logic code to read from the new field instead) The most painful has been when the primary key needs to change for a NoSQL database (which I've done), or some other non-backwards compatible change has to be made. TL;DR - Yup. It's pretty painful, but "issue"? I'd like to hear an alternative...

[@vladmirgolobovic518]

Please stick to usual naming convention when explaining technical terms, instead of coming up with your own. This pattern you are describing is pretty much universally known as master/slave. I was like, what is "leader/follower"? Until I got it what you meant.

[@ToddSkelton]

It's no longer PC to use the term master/slave, so leader/follower is the new way to say it.

[@whyrutryingsohard]

lmao