Design a URL shortener

01Problem and scope

A URL shortener stores a mapping from a short code to a destination URL and resolves that code with an HTTP redirect. Its main engineering responsibilities are unique allocation, durable creation, fast lookup, and defined deletion and expiration behavior. It does not download, compress, or proxy the destination page. For example, a create request maps q7Lm2Ax9 to https://events.example/register?event=design-day&campaign=poster; a browser requests https://s.example/q7Lm2Ax9, receives the redirect, and then contacts the destination website.

Clarify whether destinations can change, whether custom aliases are required, and whether readers must authenticate. This design assumes immutable destinations, public redirects, authenticated creation, optional aliases and expiry, and a maximum 30-second revocation delay for new redirect requests. Immediate security revocation would require a stronger read contract and a different caching decision.

Support creation, resolution, owner listing, deletion and delayed basic statistics. Exclude a marketing dashboard, destination crawling in the request path, editable destinations and authenticated private links from the first implementation. We will discuss the private-link extension later. These exclusions matter: an immutable public mapping can be copied widely; an authorization decision cannot simply inherit that caching policy. The following numbers are hypothetical interview assumptions, not measurements of a company's deployment.

02Functional requirements

1. Create: Return success only after the mapping is stored so it will survive the specified storage-node or availability-zone failure.
2. Resolve: A currently active code returns its original destination; never another creator's destination.
3. Delete: Only the owner may revoke; new requests stop redirecting within 30 seconds.
4. Expire: Requests whose authoritative time is past the deadline do not redirect.
5. List: An owner can page through their mappings without exposing another owner's records.
6. View statistics: Counts may arrive late and are explicitly approximate under telemetry loss.

Request identity and custom aliases

The creator authenticates, submits one destination and receives one code. A repeated submission with the same request identity returns the same code; a deliberately separate request may create another code for the same destination. This avoids combining unrelated campaign statistics merely because two URLs match. An alias such as design-day is a first-claim allocation: another account receives a conflict, never ownership of the existing alias.

Permanent codes and error behavior

Codes are never reused, including after expiry. A printed poster can outlive the retention period, so recycling its alias would create a dangerous new meaning. Unknown and deleted links return an unavailable response without disclosing private account details. Users can see processing or retryable errors; silently inventing a replacement destination is never acceptable. If a destination itself fails, that is outside the shortener's availability promise.

03Non-functional requirements

Redirect speed and revocation are linked: serving a cached mapping avoids a storage read, but that copy cannot immediately know its owner deleted the link. A cache freshness lease is the storage authority's permission to use the copy until a fixed deadline. The targets below set the allowed delay and the failures the service must survive.

1. Latency: Redirect p95 below 50 ms and creation p95 below 300 ms inside the serving region.
2. Availability: 99.95% successful eligible redirects per month. Validate this target under load and failure; replicas alone do not establish it.
3. Durability: Accepted creation survives one storage-node or availability-zone failure.
4. Regional recovery: Initially allow 15 minutes of potential data loss, the recovery point objective (RPO), and one hour to restore service, the recovery time objective (RTO) from replicated backups. Test these objectives separately from node/zone failover.
5. Retention: Plan for five years of mappings. Permanent code ownership outlives payload retention.
6. Revocation and expiry: Stop redirecting new requests within 30 seconds of deletion; responses already emitted may finish. Never serve beyond the mapping's expiry or original freshness deadline.
7. Clock budget: Use 25-second cache leases plus five seconds reserved for measured skew and transport. If monitoring exceeds that reserve, stop using cached mappings until revalidation.
8. Security: Encrypt transport, authorize owner operations, and retain click metadata only as long as the product needs it.

Invariants and partition behavior

The revocation guarantee deliberately limits redirect availability during a long partition. The regional RPO permits losing recent mappings, not reusing their codes. New random links may use a distinct recovery prefix or hostname while the old namespace remains read-only. The one-hour recovery target covers serving recoverable mappings; it does not prove that missing allocation history is complete.

04Capacity estimates

Workload assumptions and arithmetic

Assume 500 million new links in a 30-day month and 100 redirects per creation. There are 30 × 24 × 3,600 = 2,592,000 seconds in that month. Average writes are 500,000,000 / 2,592,000 = 193/s; average reads are 50,000,000,000 / 2,592,000 = 19,290/s. A fivefold planning peak is 965 creates/s and 96,450 redirects/s. Benchmark these independently: reads and writes consume different resources.

Worked estimates

Capacity implications and limits

The 700-byte cache figure includes an assumed allowance for key and entry overhead; allocator fragmentation and redundancy add more. At a measured 95% hit rate, peak database reads become 96,450 × 0.05 ≈ 4,823/s. Losing the entire cache restores almost 96,450 reads/s, a twentyfold jump. A cache failure can therefore multiply database load. Limit how many cache misses may fall back to the database. The ratio alone does not prove a 95% hit rate: measure the actual popularity distribution and the effect of the 25-second freshness lease.

05APIs and contracts

Request and response example

The creator sends POST /v1/links, authenticated as account u17, with header Idempotency-Key: create-204 and body {"url":"https://events.example/register?event=design-day&campaign=poster","expiresAt":"2027-01-01T00:00:00Z"}. Success returns 201 {"code":"q7Lm2Ax9","shortUrl":"https://s.example/q7Lm2Ax9"}. The server stores a hash of the validated request payload; retrying the same key with a different payload returns 409. Idempotency means the same logical operation produces the same result despite repeated transport attempts.

Interface contracts

Validation and response semantics

Use Cache-Control: no-store on browser redirect responses for this revocation contract; internal caching remains controlled by the service. A permanent redirect cached outside our control would undermine deletion semantics. Return 429 with retry guidance for creation quota exhaustion, and 503 for unavailable authority. Resolve an unknown code with 404; expiration and deletion may also use that response to minimize enumeration clues. A timed-out POST is an unknown outcome, so the client repeats its original key instead of allocating a fresh one.

06Data model and access patterns

For the initial single-database design, use unique keys for code claims and a transaction to save the mapping and creation result together.

The two records answer different questions. Link says which destination a code owns; Request says which result belongs to a creator's submission. Keeping both is necessary because a caller can lose a successful response and retry without intending to create another link.

The owner listing uses (ownerId, createdAt DESC, code DESC); expiry cleanup uses (expiryBucket, expiresAt, code). A primary-key constraint or conditional insert resolves simultaneous ownership claims atomically.

The reader's query is SELECT destination, expiresAt, deletedAt, version FROM Link WHERE code='q7Lm2Ax9'. The cache stores those fields plus validatedAt and an absolute validUntil, not a sliding “25 seconds after every hit.” Statistics are derived from click events and never determine whether a mapping exists. Listing indexes may lag after the later sharding step; the creation response and code lookup remain authoritative.

At scale, hash the complete code to a logical partition, then use a routing map to locate that partition's replicated leader. Hash (ownerId, requestKey) to a request partition. The code partition and request partition may be managed by different storage groups, called their owners; they therefore do not share one local transaction. Each partition group owns its own serial writes and committed log. An asynchronous owner index supports listing; a stalled index cannot make an allocated code available to someone else. A compact permanent tombstone preserves claimed aliases after bulky URL payloads are reclaimed.

07Basic working design

Single-server transaction

Use one application server and one SQL database. The app validates the creator's request, begins a transaction, and checks the owner/request-key identity. If a completed row exists with the same payload, it returns that result. Otherwise it chooses eight random base-62 characters, inserts the Link, and inserts the Request result within that same local transaction. A duplicate random code aborts that allocation attempt and causes a retry; a duplicate request key makes the server read the winner's result.

Base 62 uses the ten digits and the uppercase and lowercase English letters as its code alphabet. Random selection makes repeated candidates uncommon; the database's unique key, not the choice of alphabet, decides whether a candidate can be allocated.

Commit and retry boundary

The application reports success only after the database commits. A process crash before commit leaves no accepted link. After commit, a crash can hide the HTTP response but not remove the durable mapping. The reader's GET performs a primary-key lookup and checks deletion/expiry before returning a redirect. This baseline already demonstrates the central guarantee without a cache, queue, ID service, or sharding layer.

Maintenance and baseline limits

An administrator can inspect q7Lm2Ax9 and request u17/create-204 in one transaction when diagnosing a timeout. A scheduled job scans expired rows for reclamation, while every read independently enforces expiry. This is important even at small scale: cleanup is an efficiency operation, not the access-control clock. Start with backups and restore testing. One server can be a reasonable first product, but its availability and storage limits do not satisfy the final workload.

08Find the baseline flaws

The baseline's single transaction preserves creation retries, but its capacity is limited. Splitting that transaction or adding a cache can introduce new correctness failures while addressing scale. The examples below distinguish the existing capacity limit from those additional races.

09Improve the design, step by step

1. First, replicate the authoritative database and add stateless API instances. The trigger is a single process or zone failure violating accepted-write durability. A leader commits through a majority of three replicas in separate failure domains; APIs use health-checked routing. This survives one failed replica and removes an app bottleneck. It adds replication latency, failover operations and minority unavailability. Asynchronous replicas are cheaper for write latency but cannot satisfy the same acknowledged-loss rule; choose them only for a weaker disaster-recovery contract.

2. Second, add internal mapping caches and coalesced refills. The trigger is the measured tenfold read deficit. Many repeated reads use copies, while one in-flight refill per code per cache region suppresses a miss storm. Each copy carries an absolute authority-issued validity deadline. This reduces normal database load but costs RAM, cache operations and a bounded revocation delay. A cache outage can overload storage, so the API caps how many cache misses may reach the database per second. Keeping all reads authoritative is simpler and preferable while measured throughput permits it.

3. Third, partition retained mappings and separate retry reservation from mapping creation. Storage growth triggers this step. A durable PENDING request row reserves one candidate and createToken; conditional mapping insertion then executes at the code owner; completion records the result back at the request owner. A retry resumes the recorded candidate. This distributes bytes and queries without a global transaction, but adds a second durable workflow and cleanup/repair work. A transactional distributed SQL system is a valid alternative when its cross-partition transactions meet the measured cost and latency budget. SQL is not inherently disqualified by scale.

4. Fourth, move statistics and cleanup off the redirect path. The trigger is variable aggregation latency and large expiry scans. Bound a telemetry queue, batch counters, and sweep an expiry index. Redirects no longer wait for analytics; costs become worker capacity, retention and possibly missing counts. Billing-grade exact counting would instead need a durable event acknowledgement and stronger deduplication. We reject that extra latency because this product explicitly promises approximate statistics.

10Detailed architecture

Separate creation and redirect pools

The edge terminates TLS and routes creation and redirect traffic to separate API pools so a creation-abuse spike cannot consume every redirect worker. Creation checks account authentication and quotas. A partition router maps request identities and codes to their respective storage groups; this is routing metadata, not an independent authority that may invent mappings. When an API uses an outdated route, the storage group returns a moved-partition response; the API refreshes the route and its ownership-version number, called an epoch.

Partition authority and fencing

Each storage group contains a leader and replicas; its atomic conditional writes protect keys it owns. During migration, the old owner is fenced from new writes before the new epoch accepts them. Fencing here means the storage write path rejects an obsolete ownership epoch; simply telling clients to refresh is insufficient. The final diagram shows one representative replica group, not a claim that all 30 billion rows sit on one server.

Read copies and asynchronous work

Redirect workers check the internal cache, then contact the authoritative code owner on a miss or expired lease. They may use replicated hot cache entries because public immutable destinations dominate reads. Owner listing, analytics aggregation, and expiry reclamation are asynchronous derived work. A separate expiry worker marks/reclaims records through the same code authority. The diagram's asynchronous arrows represent work that may finish after the response, such as statistics updates. Creation must wait for a durable commit, and an expired cache entry must wait for a current storage read before the API can return success.

Concrete stack and durability assumptions

A practical baseline can use PostgreSQL for transactions and a Redis or Memcached tier only for disposable mapping copies. The final partition-owner diagram specifies stronger storage requirements: conditional writes, durable replication, safe failover, and verified current reads. Use an established implementation providing those guarantees or a supported distributed SQL transaction path; ordinary PostgreSQL streaming replicas do not become a safe majority-election protocol merely because three databases are drawn. A managed store may hide physical shards, leaving only the logical ownership and retry protocol visible to the application.

11Write path and acknowledgement

Creation must preserve one result across retries even when the request record and code mapping have different partition owners. The following request uses account u17, key create-204, candidate q7Lm2Ax9 and allocation token t204 to show the durable transitions.

1. The creator submits u17/create-204. The API authenticates u17, validates the complete URL without changing encoded semantics, and calculates the request payload hash.
2. At the request partition, insert PENDING(candidate=q7Lm2Ax9, token=t204, payloadHash=H) if absent. Competing copies of this request read the same durable candidate and token.
3. Route q7Lm2Ax9 to its code partition. Conditionally insert the mapping with createToken=t204. The operation succeeds only if the code is absent, or recognizes the existing mapping with the same token as its own previous success.
4. If another token owns the candidate, atomically replace the request's candidate only while it is still the recorded rejected candidate; retry the new candidate. A custom alias instead completes with a conflict. Once a mapping was accepted, never rotate that candidate merely because a response timed out.
5. Mark the request COMPLETE(result=q7Lm2Ax9) after verifying that the mapping has the same creation token. Return success. Asynchronous listing receives an idempotent mapping-created event or scans committed changes.
6. If the API dies between steps 3 and 5, retry sees PENDING, repeats step 3, finds t204, and completes the same result. It does not create a second link.

Retain a compact request-to-code identity for the accepted retry contract; do not silently forget old request identities while promising unlimited retries. Operationally bound retry records by an explicitly documented retention window if storage requires it, and make clients use fresh keys only for intentional new operations.

12Read and delivery path

Redirect serving checks both mapping validity and permission to use a cached copy. This trace resolves q7Lm2Ax9 and shows why an expired lease requires a fresh authoritative read.

1. The reader requests /q7Lm2Ax9. The redirect pool validates code syntax and applies an abuse limit without requiring a creator login.
2. It reads the cached mapping. A hit is usable only if current safe time is before both validUntil and expiresAt, and the record is active.
3. On a miss, the worker joins one refill for this code. The router contacts the current code authority, whose read returns mapping version 2 and a lease ending 25 seconds after authoritative validation. The deadline is anchored to that validation, never delayed by a slow network response.
4. The worker rejects an already-expired response and caches a still-valid one. Inserting it does not extend the lease. Negative results get a short bounded cache lifetime to avoid suppressing a just-created code indefinitely.
5. It returns 302 and the original Location, then emits a bounded best-effort click event. The reader's browser makes a separate connection to the conference site.
6. At lease expiry, a fresh authority read is required. If deletion committed, the response becomes unavailable. If authority cannot be reached, the service returns 503 rather than refresh stale state locally.

A read replica with unknown lag cannot issue a fresh lease for the revocation contract. Route revalidation to the leader or a replica with a protocol that proves sufficiently current committed state. The cache saves repeated work; it cannot manufacture knowledge during a partition.

For strict expiry, compare the expiration with a conservative upper bound on current time, including measured clock uncertainty. This may stop a link slightly early but cannot grant extra life to an already-expired mapping. Lease issuance must also anchor its deadline to the authoritative validation operation, for example conservatively before a verified current read begins, rather than to the later cache insertion time.

13Correctness deep dive

Code-space arithmetic

Retry-token ownership proof

Late-refill revocation proof

14Failure and recovery

15Operations, security, and cost

Latency, validation-age and failure signals

Track redirect p95/p99 and eligible-response success, separating cache hits, revalidations and rejected overload. Alert on the longest elapsed time since a served mapping was last checked against current storage, not only hit rate: a high hit rate can conceal broken revocation. Measure request records stuck PENDING, conditional-insert conflicts, ownership-epoch rejection, expiry sweep lag and approximate analytics drop count. Exercise clock-skew alarms because our bound includes a five-second reserve.

URL validation and authorization

Validate only intended URL schemes, impose length limits, and authorize deletion/listing using server-derived identity. A short unguessable code is not a team permission grant. If threat scanning is added, run it in an isolated outbound-fetch service with destination validation, redirect limits and blocked private-network ranges; never let the create API become an internal-network request tool. Rate-limit enumeration and creation abuse independently. Apply privacy retention to referrers and IP-derived statistics.

Cache economics

Cache economics can be stated without guessing cloud prices. Let a database lookup cost C units and a cache lookup cost 0.05C. At 95% hits, cost per lookup is 0.05C + 0.05C = 0.10C before fixed memory/operations, versus C without a cache. The saving must exceed the cost of maintaining approximately 7 GB per hot-set copy and the operational risk. Recalculate with measured hit rates.

Migration and recovery drills

Roll out shard migration by copying a partition, verifying row counts/checksums, replaying changes, fencing the old epoch, then switching routing. Shadow reads compare old/new answers before cutover. Test crashes between every create state transition, cache outage under peak load, a deletion with lost invalidation, and restoring tombstones alongside mappings.

Privacy-aware click analytics

For redirect analytics, record a minimized event such as code, time bucket, coarse country/region, referrer category and client/browser category when the privacy policy permits. These dimensions answer where and when a link is used; keep raw identifiers out of long-lived aggregates and specify retention. Analytics loss or duplication must not change redirect correctness.

16Decision ledger and limitations

A sequential counter encoded in base 62 is an alternative allocation mechanism, but exposes predictable IDs and needs a scalable counter authority. A key-generation service can reserve unused batches durably before distribution; failover must not hand one batch to two owners, and a crashed consumer should waste unused keys rather than reuse uncertain ones. We reject it initially because 965 peak creates/s does not justify that separate service.

The design does not promise instant global deletion, private reader authorization, accurate billing counts or zero regional-disaster data loss. Its next scaling limit may be a small number of hot mappings, route metadata churn, or the retained tombstone/index footprint; measure before adding another database technology.

17Interview closing

“I designed an immutable public mapping service for public short links. Creation and redirects have different loads: roughly 193 average writes and 19,290 average reads per second, with a fivefold peak. I began with one SQL transaction, then added replicated authority, caches for repeated lookups, and code partitions for five-year storage. The database's conditional insert decides ownership; random codes merely make conflicts infrequent. A durable request reservation and token let a timed-out creation recover its original mapping across partitions.

“The reader's redirect validates a cached mapping's absolute lease and expiry, then returns a small 302 response. Analytics and reclamation are asynchronous. I deliberately trade at most 30 seconds of revocation delay for cached reads, and reject stale reads after that deadline during an authority outage. The main remaining risks are cache-loss amplification and hot-key concentration. I would next measure hit rate under the lease policy and run a peak-load cache-failure test.”

If the interviewer says, “private team links must revoke immediately,” adapt the contract explicitly: authenticate each reader, associate membership/version state with the mapping, and perform an authoritative permission check or implement coordinated revocation before returning success. Re-estimate read load because the public-data cache cannot authorize access. Do not claim the existing 30-second design already meets the stronger requirement.

Recall the key ideas

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