Design a Short Link Service
People turn long web addresses into short links and share them. Visitors who open a short link are sent on to the original address, which is by far the most common request. Owners see how many times their link was opened, and links nobody uses eventually expire. How you place link creation, click counting and the clean-up job decides how robust the service is.
Constraints
- A redirect must complete within 100 ms
- About 4,000 redirects per second at peak, and about 1 new link for every 50 redirects
- A short code must never be issued twice
- Counting clicks must never slow down or block a redirect
- Unused links are removed by a background job
- Keep infrastructure under $7,000 a month
Scenarios to survive
Regular day
Steady, read-heavy traffic.
Interviewer asks: Why does a redirect service cache so well, and what do you do about the one request in fifty that writes?
A link goes viral (3x)
One short link is posted somewhere huge and traffic triples.
Interviewer asks: Almost all of the extra traffic is for a single code. Which component feels it first, and what absorbs it?
The click counter hangs
Whatever runs click counting becomes 25x slower.
Interviewer asks: Counting is slow. Should a visitor wait for it? Where would you count so that this cannot happen?
The cache is lost
Every lookup falls through to the database.
Interviewer asks: With the cache gone, can the database carry the redirect load alone? What would you do first?
Readers on every continent
The same number of requests, but 60% of them now come from Europe and Asia.
Interviewer asks: A link is opened in Singapore. What has to cross the ocean to answer it, and what does not?
What a good design must do
- Redirects meet the latency target at peak
- At least 98% of redirects are served when traffic is three times higher
- Total monthly cost stays within $7,000
- Redirects are served from a cache in front of storage
- Something creates links, and never issues the same code twice
- Something counts clicks
- A hung click counter cannot slow redirects
- Something removes unused links
- The design explains how short codes are generated
- People on every continent get their redirect within the target