Design a URL shortener

01What the short link actually does

Someone prints an event poster containing a registration address. The original address is long, so our service gives them https://s.example/q7Lm2Ax9. When another person opens that address, the browser should reach the original registration page. The service stores a code-to-destination mapping; it does not compress or host the destination page.

For this interview, support creating a link, resolving it, choosing an optional custom alias, expiring it and deleting it as its owner. Destinations do not change after creation. Redirects are public; creation and owner actions require authentication. Click statistics may arrive late. Private links, billing-grade counts and immediate worldwide revocation are separate requirements to discuss if requested.

Two rules matter immediately. A code must never resolve to another creator's destination, and a successful creation must have a durable stored mapping. An unavailable destination is outside our service: we can return the correct redirect even when the event website is down. Ask how quickly deletion must take effect, because that decision later determines whether cached redirects are acceptable.

02Functional requirements

Agree on these supported actions before selecting components.

1. Create and manage links. Authenticated owners create immutable destination mappings, optionally request a custom alias and expiry, list their own links, and delete them.

2. Resolve a public code. An active code returns an HTTP redirect to its saved destination. Missing or expired links return an unavailable-link result; deletion follows the cache-freshness policy below. The destination page is fetched by the browser.

3. Recover a repeated creation. Repeating the same owner-scoped request and payload returns the same link during the supported retry window. Conflicting aliases or changed payloads are rejected.

4. Record lightweight statistics. Collect approximate click statistics asynchronously; delayed or lost analytics must not change the redirect result.

03Non-functional requirements

Use these as illustrative interview assumptions to agree with the interviewer. Numerical targets require measurement; they are not claims about an existing product or a proven implementation. p95 (the 95th percentile) means 95% of measured operations finish within the stated time.

1. Workload. Plan for approximately 965 creates/s and 96,450 redirects/s at peak, with 30 billion claimed codes after five years. These are the illustrative assumptions derived below.

2. Response time. Target p95 of 50 ms for redirects and 200 ms for creation, measured from regional service ingress to response at the planning peak under normal operation. Internet transit and destination-site loading are outside these measurements.

3. Durability and availability. A successful creation must survive an application restart or one database-node failure within the serving region. Unsafe writes stop rather than acknowledge an unprotected mapping; regional disaster recovery is a separate requirement.

4. Identity and retries. Codes never change owners or destinations, including after deletion. Retain creation results for at least 24 hours so a matching retry within that window cannot create another link.

5. Cache freshness. Expiry is checked on every serving path. Deletion has eventual visibility with best-effort invalidation and one-minute internal cache entries; this is not a hard global one-minute revocation guarantee.

6. Access and abuse. Owner actions require current authentication and ownership checks. Limit creation abuse and accept only supported destination schemes; a public random code is not a private-access credential.

04Follow one creation and one visit

Begin with one application and one relational database. The application receives a destination URL, generates a candidate code and inserts a row containing that code and destination. The code column has a unique constraint, which means the database rejects a second row with the same code. After the transaction commits, the application returns the short URL.

The visit follows three steps:

1. The browser requests /q7Lm2Ax9.
2. The application looks up that exact code, checks that the row is active and unexpired, and returns HTTP 302 with the destination in the Location response header.
3. The browser makes a second request to the destination website.

The shortener's response contains a header and perhaps a small body; it does not carry the destination page's images or video.

This is already a complete useful service. A missing or expired code returns an unavailable-link response rather than an invented destination. One indexed lookup can serve each redirect. A database transaction publishes a complete mapping before the creator receives success. Next, use the workload to decide when lookup cost or storage growth justifies more components.

05Estimate the work that could outgrow the baseline

Assume 500 million creations in a 30-day month and 100 visits per creation. These are interview assumptions, not traffic measured from a named company. There are 2,592,000 seconds in that month, giving about 193 creates and 19,290 redirects per second on average. With a fivefold planning peak, test approximately 965 creates and 96,450 redirects per second.

The calculations identify a read-heavy lookup service. They do not prove that every mapping needs caching or that SQL cannot work. Measure indexed lookup capacity and the distribution of repeated visits. A small number of frequently visited codes can dominate requests even when most stored links are rarely read. That observation motivates a cache more directly than the total row count does.

06Make creation, retry and ownership explicit

The creator sends a destination and optional expiry with an owner-scoped request key.

Creation request

POST /v1/links
Idempotency-Key: create-204
Content-Type: application/json

Example request body

{
  "destination": "https://events.example/registration/design-day",
  "expiresAt": "2030-12-31T23:59:59Z"
}

Idempotency means retrying this same logical request returns its existing result rather than creating another link. Store the key under the authenticated owner and compare the supplied payload before replaying a result. Reusing it with different input is a conflict.

For a custom alias such as design-day, return a conflict if somebody already owns it. Do not silently generate another alias after the caller asked for an exact one. Validate allowed URL schemes and length; preserve the destination's encoded meaning rather than casually rewriting it.

A creation timeout is an unknown outcome: the database may have committed before the response disappeared. The client retries create-204 or retrieves its status. A request key identifies an operation; two intentionally separate creations may legitimately target the same destination and keep different statistics.

07Store the mapping and the answer to a retried request

Use two records so a redirect mapping and its creation result have distinct purposes.

In the baseline, insert both within one database transaction so neither becomes visible alone. If concurrent copies of one request choose different candidate codes, the request-key constraint lets only one transaction commit; the loser rolls back its tentative mapping and returns the winner’s saved result. A code collision from an unrelated request instead chooses another candidate.

The main lookup uses the code's primary-key index. Owner listing instead needs an index ordered by (ownerId, createdAt, code). A pagination cursor records the last time-and-code pair; the code breaks ties between links created at the same timestamp. These are different access patterns, so a fast code index does not automatically make owner listing efficient.

Never reuse a previously issued code for unrelated content. Somebody may still have an old poster or bookmark after the original link expires. Retain a compact claim or deletion marker even if old destination bytes are removed. This consumes some permanent identity storage but avoids giving an old URL a new owner. A scheduled cleanup job can reclaim expired payloads; reads must check expiry independently because that job may run late.

08Generate candidates; let storage decide uniqueness

Eight characters drawn from digits and upper- and lowercase letters give 62^8, about 218 trillion possible codes. With 30 billion permanently claimed codes, approximately 0.0137% of the space is occupied. A random candidate is therefore likely to be unused, but random generation never proves uniqueness.

Suppose two application servers both choose q7Lm2Ax9. Each tries an insert against the same unique code constraint. One succeeds; the other sees a collision, chooses a new random candidate and retries. A prior lookup saying “absent” would not be enough: both servers could read that answer before either writes.

A sequential number encoded in base 62 is another option. It avoids random collision retries but needs a safe allocation mechanism and produces predictable identifiers. A separate service can allocate batches, although that adds another component and failover responsibility. At the assumed creation rate, random candidates plus enforced uniqueness are a defensible starting choice.

Keep successful request results long enough for the documented client retry window. After that window, clients need explicit status recovery or a new intentional operation; do not promise indefinite retry recovery while discarding the record that makes it possible.

09Add a cache for repeated visits, then distribute storage

If measured database capacity is below the redirect peak, place an internal cache in front of lookups. A redirect first checks the cache; a miss reads the database and stores the result. Let simultaneous misses for one code share one database lookup, so a viral link does not trigger hundreds of identical cache refills. LRU eviction removes entries that have not been used recently when memory is full; it is a starting policy to test against actual traffic.

Caching creates a visibility tradeoff. A cached destination may remain after its owner deletes the database row. For this worked design, use fixed one-minute cache entries and best-effort invalidation when deletion commits. This gives eventual deletion visibility, not a hard worldwide one-minute deadline: a delayed old read can refill the cache after invalidation. State that limitation explicitly. Strict deadlines require the advanced freshness protocol. Send Cache-Control: no-store on browser redirects so the browser does not retain an uncontrolled redirect after our internal entry expires.

Replicated database storage protects against configured failures; application replicas allow independent request handling. Add partitions when retained bytes or measured throughput justify them. Hashing the code distributes distinct mappings, but one viral code remains one hot key and needs replicated cache copies. For the scaled worked design, choose a distributed SQL store that supports the same atomic mapping/request transaction across its partitions. This preserves the retry rule while adding distributed-transaction latency and operational cost, which must fit the measured budget. A separate cross-partition reservation workflow is an Advanced alternative; splitting the tables without either mechanism would lose the creation guarantee.

For this failure target, configure the selected SQL store to acknowledge mapping/request commits only after a durable majority of three replicas in independent failure domains within one region. Verify that its failover preserves those commits; merely enabling an asynchronous replica does not meet the requirement.

10Explain a lost response and a lost cache

The creation transaction commits Link(q7Lm2Ax9) and the result for u17/create-204, then the application crashes before replying. On retry, the service finds the saved request result and returns the original short URL. The user receives one logical link even though the network carried two attempts. If the crash happened before commit, neither row is committed and the retry may perform the creation.

A cache failure produces a different problem: extra database load. At a measured 95% cache-hit rate, a peak of 96,450 redirects/s sends about 4,823 reads/s to storage. Losing the cache can send almost the entire peak there, roughly twenty times more. Limit concurrent database fallbacks and return a retryable error when that budget is exhausted. An unlimited queue merely turns overload into long waits and memory exhaustion.

For database failover, acknowledge writes only under the chosen durability policy and direct writes to the current database leader. Read replicas can be useful, but lag can hide a newly created link or retain a deleted one. Explain which reads may tolerate that delay. Backups address accidental deletion and larger disasters; replication is not a substitute for testing a restore.

11Protect the service and measure the user experience

Public short links attract spam, malicious destinations and enumeration. Rate-limit creation by authenticated account and apply separate read-abuse controls. A hard-to-guess code is not authorization for private content. If threat scanning is required, run outbound fetching in an isolated service with destination restrictions; the redirect worker should not fetch arbitrary URLs into the application network.

Measure creation and redirect latency separately, cache-hit rate, database fallback load, collision retries, unavailable-link responses and replication or recovery lag. Test a viral link and total cache loss rather than only uniform random traffic. Watch deletion behavior as well as raw availability: quickly returning an invalid link is not a successful user outcome.

Emit click statistics asynchronously so a popular link does not update one contested counter on every request. Under the chosen approximate contract, events may be delayed or lost within a documented buffer policy. Keep personal click data minimal. Cost is driven by retained mapping/index bytes, replicated cache memory, lookup work and the small redirect responses. The target website's delivery bill is not ours.

12Check the design against the requirements

Use the agreed lists to check the finished design. The tests below still need to establish the targets; a proposed mechanism is not a measured result. FR refers to the numbered functional requirements above; NFR refers to the numbered non-functional requirements.

13Rapid revision

Remember: Randomness supplies candidates; the unique insert prevents two owners from claiming one code.

A concise spoken answer should follow the browser through one creation and one visit, justify the unique constraint, use the traffic estimate to introduce caching, and then explain what happens when the cache or response disappears. Name stronger revocation and cross-partition retry requirements as follow-up work rather than silently claiming they are solved.

Recall the key ideas

Answer from memory before opening each card. Explain why the choice works and what it costs. Revisit missed cards tomorrow.