Restaurant Reservations (OpenTable)

The problem

"Design OpenTable." Diners search restaurants near them and book a table for a party size and a time, such as 4 people on Friday at 8 pm. Restaurants also take walk-ins and phone bookings, on a tablet at the host stand.

This practice problem reuses the pattern of Design Hotel Booking. What's new: slots instead of nights, search across many restaurants, the host's tablet, and diners who never come. Park joining tables and paying the bill in the app.

The numbers

From the interviewer: 1 million reservations a day, about 100 searches each. Round a day to 100,000 seconds (86,400 really); busy hours run about 5× the average.

• Searches: 1 million × 100 = 100 million a day, 1,000 a second on average (about 1,160 with 86,400), so about 5,000 a second at busy hours.
• Bookings: about 10 a second on average, 50 at busy hours: easy for one database.
• Restaurants read: each search looks at about 50 nearby: 5,000 × 50 = 250,000 restaurant evenings a second.
• Storage: say 50,000 restaurants, booked up to 30 days ahead, 3 table sizes, 24 slots an evening: 108 million slot rows, about 54 GB at 500 bytes each.

Tables and slots: a booking takes 6 rows

Luigi's has 6 two-tops, 8 four-tops and 2 six-tops, open 5 pm to 11 pm, and a party keeps its table about 90 minutes. So the table plan keeps a row per table size per 15-minute slot. Ana's party of 4 at 8:00 holds a 4-top until 9:30, so her booking adds 1 to the 6 rows from 8:00 to 9:15:

slot   before  after Ana
7:45   8 of 8  8 of 8
8:00   6 of 8  7 of 8
8:15   6 of 8  7 of 8
8:30   5 of 8  6 of 8
8:45   5 of 8  6 of 8
9:00   5 of 8  6 of 8
9:15   4 of 8  5 of 8
9:30   4 of 8  4 of 8

As a hotel stay takes its nights, the 6 conditional updates are one transaction, in time order, every slot or none. A time is open only if all 6 rows have a table left. Party size picks the row: 1–2 people a 2-top, 3–4 a 4-top, 5–6 a 6-top. The host picks the actual table on arrival: if no slot counts more parties than tables and parties leave on time, one is always free.

A row per evening, like a hotel's night, can't tell 6 pm from 8 pm, though a 4-top can seat 4 parties an evening. A booking that takes only its 8:00 row lets an 8:30 booking sell Ana's table again.

Search near me: open times worked out ahead

Search finds the restaurants near Ana with map cells, as in Nearby Places, then needs their open times around 8 pm for 4. Working those out per search means reading 250,000 restaurant evenings of slot rows a second: at least 50 database servers, at about 5,000 reads each.

But Luigi's Friday open times are the same for every diner, and change only when its plan does: about 50 bookings a second at busy hours across all restaurants, 5,000 times fewer than the reads. So the booking service works them out on every change and saves one entry per restaurant per evening, every party size in it. After Ana's booking, Luigi's entry for 4:

start  open
7:30   full
7:45   full
8:00   1 table left
8:15   1 table left
8:30   2 tables left

Search reads 50 entries and keeps the times within 30 minutes of 8 pm. About 3 cache servers answer 250,000 reads a second, and 1.5 million entries (30 evenings of 50,000 restaurants) at about 1 KB are 1.5 GB. An entry can be a moment old, so the booking still checks the real rows.

The host's tablet: one table plan

At 4:30 pm a caller wants Friday 8:00 for 4 just as Ben books it online, and one 4-top is left. A tablet with its own plan, synced every 5 minutes, would give both the table. Giving the website 6 tables and the tablet 2 wastes them on quiet nights.

Instead the tablet books through the same booking service, the same conditional update on the same 6 rows. Ben's update reaches 8:00 first; the caller's waits on the row lock, finds 8 of 8 and changes 0 rows, so the host offers 8:30. Seating a walk-in adds 1 to the rows from now. Tables kept for walk-ins are a limit in the same rows, like a hotel's overbooking margin.

No-shows

Say 1 in 10 parties never come on a Friday. A scheduled job, as in the Job Scheduler, texts each diner the day before, reply C to confirm or X to cancel, and an X gives the slot rows back at once. On busy nights the restaurant can also ask for a card, saved by the payment provider and charged a fee only when the host marks a no-show.

Overbooking fits badly: a hotel walks an extra guest to a room nearby, but a restaurant's extra party waits at the door. Canceling unconfirmed bookings is worse: diners who never read the text still come.

Same pattern as Hotel Booking

Counts per size per unit of time, changed by conditional updates in one transaction; search apart from booking, from a ready copy, while the booking decides; an idempotency key on every booking; and a cancel that gives the slots back only once.

Summary

• Scope: tables for a party and a time, search near you, walk-ins, no-shows.
• Data: a row per table size per 15-minute slot; a booking takes 6.
• Numbers: about 5,000 searches and 50 bookings a second at busy hours.
• Services: search, booking, and the host's tablet through booking.
• Scale: open times worked out on every change, one entry per restaurant per evening.
• No-shows: a text to confirm; a card for a fee on busy nights.