Stack Overflow

The problem

"Design Stack Overflow." Programmers ask questions, others answer, and votes push the best answers up. Askers accept the answer that worked, writers earn reputation from votes, reputation unlocks actions such as downvoting, and questions carry tags. Most traffic is visitors from search engines reading old pages.

This practice problem reuses the pattern of Design Reddit. Five things are new: the accepted answer, reputation, privileges, tags, and a huge signed-out audience. Park chat rooms: real-time chat is a design of its own.

The numbers

From the interviewer: about 100 million question pages viewed a day and about 1 million votes a day. Round a day to 100,000 seconds (86,400 really); busy hours run about 5× the average.

• Page views: 100 million ÷ 100,000 = 1,000 a second on average (about 1,160 with 86,400), so about 5,000 a second at busy hours.
• Votes: about 10 a second. Pages are viewed about 100 times for every vote: reading is the busy path.

The accepted answer: one field on the question

Ben asked how to read a CSV file in Python and accepted a3, Ana's answer, which has 12 votes; a1 has 250 and a2 has 40. The interviewer wants the accepted answer pinned at the top, whatever its votes, so the page shows a3, then a1, then a2.

Store it as one accepted_answer_id on the question. A question has at most one accepted answer, and one field can't name two; switching to another answer is a single write. A flag on each answer needs two writes to switch, and a failure or two switches at once can leave two answers flagged. Faking the pin with a bonus of 1,000 votes shows a score of 1,012 that nobody cast, and the pin breaks as soon as another answer passes 1,012.

Reputation: points added in the background

Say an upvote on an answer earns its writer 10 points, an accepted answer 15, and a downvote costs 2 (Stack Overflow publishes its own table). When Cy upvotes a3:

1. The server saves Cy's vote row, which also tells it what changed (new − old, as in Reddit).
2. It puts the change on the vote queue.
3. It answers Cy: his arrow stays lit.
4. A worker takes the event off the queue and adds it to a3's score and to Ana's reputation.

Reputation is a count per user, updated asynchronously, as in the Distributed Counter lesson: Cy never waits for it, and a busy writer's points are added many at a time. Each change is also kept as a row (Ana, +10, upvote on a3), so an undone vote subtracts 10 and the total can be recounted.

Privileges: checked at every action

action            points needed (say)
upvote            15
comment anywhere  50
downvote          125
edit any post     2,000
vote to close     3,000

Cy has 130 points, so he can downvote, until 5 downvotes on his answers cost him 2 each: 130 − 5 × 2 = 120, under 125. The right check is on the server, at every action, against his reputation now: his next downvote is refused, and allowed again once he's back at 125. The thresholds sit in every server's memory and his reputation is one cached read, so the check is nearly free.

A flag saved the first time he reached 125 goes stale: at 120 he would keep downvoting until a job took it back, and moving a threshold would mean rewriting a flag on millions of accounts. Hiding buttons in the app is a courtesy, not a check: anyone can send the request straight to the API.

Tags: an index from tag to questions

Each question carries a few tags from a shared list. Browsing [python] [sql] uses Search Engine's inverted index, with tags for words, each list newest first:

tag     questions
mysql   q5
pandas  q6, q4
php     q5
python  q6, q4, q2, q1
sql     q4, q3, q1

Walking the python and sql lists together keeps the ids in both: q4, q1. A tags column searched with LIKE '%sql%' would scan every question and also match mysql, putting q5, a PHP question, on the sql page. Searching the question text finds questions that mention a word in passing and misses the ones that never say it.

Signed-out readers: cached pages

Most views come from people who aren't signed in. Say 90% of the 5,000 views a second at busy hours are signed out, and one app server builds about 1,000 pages a second. A signed-out page is the same for everyone, so cache the whole rendered page and purge it when its question or answers change: 4,500 views a second never reach the app servers, which build only 500, half of one server's work. Copies also expire after a minute or so, so vote counts catch up. A small number of well-tuned servers can serve a read-heavy site like this.

Building every page fresh is 10× the work, at least 5 servers' worth for pages that are the same for 9 readers in 10. Caching for a day with no purge shows an edited answer's old, broken code for up to a day.

Same pattern as Reddit

Votes are rows keyed by (user, post), each post keeps its score ready, and the vote queue lets the request answer before the counting is done.

POST /answers/a3/vote          {"dir": 1}
POST /questions/q7/accept      {"answer": "a3"}
GET  /questions/tagged/python+sql?cursor=…

Summary

• Data: the question holds its accepted_answer_id; the page shows it first, then by votes.
• Numbers: about 5,000 page views a second at busy hours, 100 per vote.
• Services: a worker adds votes to scores and reputation, off the vote queue.
• Scale: whole pages cached for signed-out readers, purged on edit.
• Privileges: checked on the server at every action.
• Tags: an index from each tag to its questions, newest first.