Capstone: design and defend a system end to end

Every earlier lesson showed one skill. A real round needs all of them in 45 minutes, with an interviewer who changes the problem. This lesson is that round, from the first question to the closing.

A weak answer has good parts that do not connect. The numbers in the estimate are forgotten when the design appears, and again at the deep dive. A strong answer keeps one set of numbers from the start to the end. When the interviewer changes something, the answer changes the numbers first and the drawing second.

At SDE-1 level you should finish the six steps with help. At SDE-2 level you should defend a change with numbers, unasked. At SDE-3 level you should also choose the hardest part yourself and say when you would change the design again.

Think of a driving test. The examiner does not test one skill. You drive a whole route, and the examiner adds surprises, such as a blocked road. The test is whether you keep driving calmly and safely.

A capstone is the same: one full design round that joins the skills of lessons 2 to 6, and 114. You build a simple design, then defend it. To defend a design means to answer each change and each question with a number and a trade-off, and to keep the drawing correct.

One table that runs the whole round

Make one numbers table. It has one row for each part of the design. It has four columns: the part, its load (the work it gets), its limit (the most work it can do), and load divided by limit. Write it after the design step. Update it after every change, and say aloud that you did.

Two facts help you read the table.

• A part over 100% cannot cope. Plan for about 70% at the busiest time, so that a small rise does not break it. For servers, lesson 15 gives this rule: peak load / (limit of one server x 0.7), rounded up, plus 1 spare server.
• Adding copies fixes a part that is stateless, which means it keeps nothing between two requests (lesson 26). It does not fix a single database. That part needs a change in the design.

The parts of the design, each from an earlier lesson

• A load balancer is a server in front of your servers. It passes each request to one of them (lesson 28).
• A cache is a fast store that keeps copies of data that is read often. The time to live (TTL) is how long a copy may stay before it expires (lesson 31).
• The leader is the database server that takes all writes. A follower copies the leader (lesson 39). With synchronous copying, the leader says "saved" only after the follower has the change. With asynchronous copying, it does not wait.
• Failover means that a follower takes the leader's job when the leader dies (lesson 41).
• An idempotency key is a unique value that the app sends with an order. If the app sends the order again (a retry), it sends the same key. The server sees that it is a repeat and creates only one order (lesson 61).

How the defence goes

Lesson 114 gave the minutes. The first five steps take 24 minutes. Then come a twist, your own deep dive, a second twist, and a closing summary. For a twist, use the five moves: say it back, ask one question, redo the arithmetic, find what breaks first, say the trade-off. For your dive, choose the part that is worst if it fails. At the end, say which parts you did not examine.

After the round, review it with the six questions of lesson 116.

The interviewer says: "Design a food-ordering app." We use the numbers of lesson 3.

Assumptions (made up to teach with, not real traffic):

• 500,000 orders arrive in the busiest 2 hours. One order makes 20 requests: 16 menu or list reads, 3 tracking reads and 1 order write.
• One server answers 500 requests per second. The database answers 2,000 operations per second. A read and a write count the same.
• The menu must open in under 2 seconds. Downtime is at most 60 minutes a month. A confirmed order is never lost. Orders grow 3 times in a year.
• There are 50,000 restaurants. A cached menu is 100 KB. One cache server answers 50,000 reads per second.

Steps 1 to 4 (14 minutes).

• Requests: 500,000 x 20 = 10,000,000. The busiest 2 hours are 7,200 seconds. 10,000,000 / 7,200 = 1,389 requests per second.
• Orders per second: 500,000 / 7,200 = 69.4. Menu reads: 16 x 69.4 = 1,111. Tracking reads: 3 x 69.4 = 208. Writes: 69. The sum is 1,388, which is 1,389 before rounding.
• Entities: restaurant, menu item, order. API: getMenu(restaurantId), placeOrder(items, idempotencyKey), trackOrder(orderId).
• Data flow for placeOrder: phone, load balancer, one server, the database saves the order, the answer returns.

Step 5, the design (10 minutes). Phone, then a load balancer, then servers, then one database. Servers, with the rule of lesson 15: 500 x 0.7 = 350 requests per second for one server. 1,389 / 350 = 3.97, so 4, plus 1 spare = 5. Each of the 5 servers gets 1,389 / 5 = 278 requests per second, which is 56% of 500. If one breaks, 4 are left: 1,389 / 4 = 347, which is 69%. Database: 1,389 / 2,000 = 69%.

Storage. Assumption: 1,000,000 orders a day, 2 KB each. That is 2 GB a day, and 2 GB x 365 = 730 GB in a year.

Minute 24, twist 1: "Orders grow 3 times. The menu must still open in 2 seconds."

1. Say it back: 3 x 1,389 = 4,167 requests per second.
2. One question: "Do menus change during the evening?" Answer: "Rarely."
3. Arithmetic: 4,167 / 350 = 11.9, so 12 servers, plus 1 spare = 13.
4. What breaks first: the 5 servers have a limit of 5 x 500 = 2,500, so they are at 4,167 / 2,500 = 167%. The database is at 4,167 / 2,000 = 208%. This answers the predict box. Both are over, and the database is further over. Adding servers fixes the servers. It cannot fix the one database, so the design must change there.
5. The fix is a menu cache with a TTL of 1 hour. The 50,000 menus take 50,000 x 100 KB = 5 GB. Each menu can miss at most once an hour, so misses are at most 50,000 / 3,600 = 13.9 per second. Tracking reads are 3 x 208.3 = 625 per second. Writes are 208 per second. The database gets 13.9 + 625 + 208 = 847 operations per second, which is 847 / 2,000 = 42%. Menu reads are 16 x 208.3 = 3,333 per second, and one cache server answers about 50,000, so 7%.

Trade-off: "A menu cache solves the database limit: 4,167 operations fall to 847 per second. It costs 5 GB of memory and menus up to 1 hour old. I would change it if menus changed often."

Minute 31, my own dive. Beat 1. Which part is worst if it fails? The database. It is one machine, and it holds every order: 730 GB after a year. If it dies, no order can be saved. So I add a follower, and the choice is how it copies.

• Beat 2, the numbers. Orders at 3 times growth: 208 per second. Assumption: the checker of lesson 41 asks every 5 seconds and needs 3 failed checks, which is 15 seconds. Promotion takes 10 seconds, and the apps need 5 seconds to find the new leader. That is 15 + 10 + 5 = 30 seconds with no writes. In 30 seconds, about 208.3 x 30 = 6,250 orders try to arrive.
• Beat 3, two options. With asynchronous copying, the lag (how far the follower is behind the leader) is assumed to be 1 second. The orders lost are about 208 x 1 = 208. With synchronous copying, no confirmed order is lost. But each order write waits for the follower. Assumption (lesson 39): a disk write takes 1 ms. A round trip in one data centre takes 0.5 ms (lesson 14). So each write waits about 0.5 + 1 = 1.5 ms more. Writes also wait if the follower is down.
• Beat 4, choose. "Synchronous copying solves 'a confirmed order is never lost'. It costs about 1.5 ms for each order, and writes wait if the follower is down. I would change it if the follower were in another city, where the wait is far longer." A failover of 30 seconds is 0.5 minutes. The budget is 60 minutes, so one failover uses 0.5 / 60 = 0.8%. The apps retry with the same idempotency key, so a retry makes no second order.
• Beat 5. "Does this answer your question?"

I skip the cache failure: if it died, the database would get 4,167 operations, which is 208%. I say that I skipped it.

Minute 38, twist 2: "A restaurant must change a price, and customers must see it within 1 minute."

First, in both options the order step reads the real price from the database, so nobody pays an old price. That adds 1 read for each order: 208 per second.

• Option A: TTL of 60 seconds. Each menu can miss once a minute: 50,000 / 60 = 833 per second. The database gets 833 + 625 + 208 + 208 = 1,874 (1,875 before rounding), which is 94%. That is over the 70% plan.
• Option B: keep the 1-hour TTL, and delete a menu from the cache when the restaurant saves an edit. Assumption: 2,000 edits an hour, which is 2,000 / 3,600 = 0.6 per second. The misses are 13.9 + 0.6 = 14.5 per second. The database gets 14.5 + 625 + 208 + 208 = 1,056, which is 53%.

Trade-off: "Deleting on edit solves fresh prices at 53% load. It costs code in the edit path, and a failed delete leaves an old price on screen for up to 1 hour. The order step still charges the real price. I would change it if deletes failed often."

Minute 42, the closing, and the final table.

"The app needs 4,167 requests per second after growth. Thirteen servers, a menu cache, and a database with a synchronous follower meet it, even when one server or the leader fails. I did not examine the cache failure or the load balancer."

• One numbers table solves a design that moves away from its numbers. It costs about a minute at each change. I would drop it only if the interviewer wants a talk about ideas and no numbers.
• Defending each change with a cost solves a design that sounds good and has no reason behind it. It costs time, so you cover fewer parts. I would cover fewer parts, and say which I skipped, rather than give a change without a cost.
• A cache with delete on edit solves both load and fresh prices. It costs a delete in the edit path. I would use a short TTL alone when there are few menus.

"A capstone design should have many parts, to look senior." This design has a load balancer, servers, a cache, and a database with a follower. Each has a number behind it. A part with no number is a cost with no reason.

"If my design changes during the round, my first answer was weak." The design changed three times: a cache, synchronous copying and delete on edit. Each change came from a number, not a mistake.

"Numbers belong to the estimate step only." In this round the numbers came back in the design, both twists and the dive. A number used once is not an answer.

1. Name the four columns of the numbers table. Name the three moments of the defence in the worked example.
2. Orders grow 5 times instead of 3 times. (a) How many requests per second? How many servers do you need, with the rule of lesson 15? (b) With the 1-hour menu cache, no edits, how busy is the database?
3. A candidate says: "I will set the menu TTL to 5 seconds, so prices are always fresh." There are 3,333 menu reads per second, spread evenly over the 50,000 menus. What does this do to the database? What do you say instead?