Design a URL shortener (TinyURL)

01Functional requirements

A shortener turns a long destination such as https://garden.example/events/autumn?ref=poster into https://go.example/garden24. Here, garden24 is the short code: the part after the service's domain. The database saves which destination belongs to that code.

1. FR1: Create unique short links. Let an owner submit a destination and receive a generated code, or choose an available name such as garden24. If the creation response is lost, retrying the same request must return the same link.

2. FR2: Open active links. When a visitor opens the short URL, find its saved destination and tell the browser to visit it. The browser, rather than the shortening service, loads the destination website.

3. FR3: Manage links. Let owners set an expiry date, list their links and disable a link. Expired or disabled links must stop working even before their stored data is physically deleted.

4. FR4: Restrict private links. Let an owner name the accounts allowed to open a private link. Knowing its URL is not sufficient permission.

5. FR5: Show usage reports. Count recorded visits by day and broad region. Tell owners how current the report is and whether overload caused missed records. This reporting is separate from opening the destination.

Out of scope

• Changing a link's destination after creation, custom domains and page previews.
• Giving a previously used code to another destination.

02Nonfunctional requirements

Use these proposed interview assumptions: ten million new links and one billion visits per day, with peak traffic five times the average. Confirm them before designing capacity.

1. NFR1: Fast redirects. At peak in the primary region, at least 95% of requests to open public links finish within 100 ms. Loading the destination website is measured separately.

2. NFR2: Available public links. Meet 99.95% public-redirect availability per calendar month. Creating links and generating reports can fail independently of opening existing links.

3. NFR3: Reliable creation. Return success only after saving the unique code, destination and original request result. Two owners cannot claim one code. Reject a changed request submitted under an already used request key.

4. NFR4: Disable within 60 seconds. After the main database saves a disable operation, no cached public copy may serve the link beyond 60 seconds. Copying an old entry must not restart that deadline.

5. NFR5: Enforce expiry and private permission. Check expiry on each visit. Check the current allowed-account list for private links; deny access if it cannot be checked. Browser and proxy caches must not bypass these checks.

6. NFR6: Explain report limits. Aim to count accepted visit records within one minute. Count a repeated record once. Counts may include bots and repeated visits by one person, and may miss visits when the reporting queue is full.

7. NFR7: Never reuse a code. After deleting the destination, keep a small used-code record. An old printed URL must never lead to a new owner's website.

03Estimate only what changes the design

1. Calculate request rates. A day has 86,400 seconds. Ten million creations ÷ 86,400 ≈ 116 creations/second; one billion visits ÷ 86,400 ≈ 11,600 redirects/second. Multiply by our assumed peak factor of five: 580 creations and 58,000 redirects/second. Opening existing links creates most of the traffic.

2. Calculate mapping storage. Assume 500 bytes for each code and its link details. One year adds 3.65 billion records: 1.83 TB before overhead. Three copies need about 5.5 TB before indexes, backups and used-code records. At 300 bytes per redirect response, average response traffic is about 3.5 MB/second before protocol overhead. The service sends a destination address, not the destination website's files.

3. Estimate a useful cache. A cache is an in-memory copy used to avoid repeated database reads. Suppose visitors open 20 million different codes in a day and we keep the most popular 10%. Two million records × 500 bytes = 1 GB before overhead and copies. Ten visits to garden24 still need one entry. Measure how many visits those selected entries actually serve; storing 10% of codes does not automatically avoid 90% of reads.

4. Check the code space. Seven characters chosen from uppercase letters, lowercase letters and digits give 62 choices at each position: 62 to the seventh power, about 3.52 trillion possible codes. One year's 3.65 billion used codes occupy about 0.10%. Six characters give 56.8 billion possibilities and about 6.4% occupancy. Random duplicate choices become more likely as the space fills; the database still checks every new code. A larger space does not replace private-access checks.

Decisions from these estimates

• Test caching popular destinations because redirects dominate traffic.
• Start code creation with random generation and a database uniqueness check. Measure it before adding another allocation service.
• Test an empty or failed cache: up to 58,000 lookups/second could reach the database. Limit that traffic to its tested capacity.

04API Design: Requests, Responses and Retries

Create a link

1. The owner signs in and submits the destination. The application uses the signed-in account, rather than trusting an owner name in the submitted JSON.
2. The client labels this creation request create-17. This is an idempotency key: reuse it when retrying this same operation after a timeout.
3. The service saves the request's result. A retry retrieves that result instead of creating another link.

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

{"destination":"https://garden.example/events/autumn?ref=poster","customAlias":"garden24","expiresAt":"2026-11-01T00:00:00Z","visibility":"public"}

{"code":"garden24","shortUrl":"https://go.example/garden24","state":"active","version":1}

Manage and open links

• GET /links/garden24 lets the owner inspect the link; GET /links?cursor=... lists the next page of owned links.
• DELETE /links/garden24 disables it and returns 204.
• For a link created with visibility:private, the owner uses PUT /links/garden24/permissions to replace its allowed-account list. The request supplies accountIds and expectedVersion; for example, ben identifies Ben’s signed-in account. The permission handler verifies the owner, compares the saved link version, and saves the list plus incremented version in one transaction. Return 200 with the new version, or 409 if another edit already changed it. A visitor still checks this current list on every private open.
• GET /links/garden24/stats?day=2026-10-24 returns the owner's report. For example, {"acceptedClicks":23,"through":"2026-10-24T12:00:00Z"} means 23 recorded visits, with processing complete through noon. Later records may still be waiting.
• A visitor opens https://go.example/garden24. The service returns 302 and a Location header containing the saved destination. Cache-Control: no-store tells browsers and proxies not to save that redirect and skip future checks.
• Opening returns 404 for an unknown code, 410 for an expired or disabled link, 401 when sign-in is required and 403 when the account is not allowed.

05Data Model and Storage Access Patterns

A mapping is the saved connection between a short code and a destination. Keep usage counts separately so reports do not repeatedly change the row used by redirects.

Why begin with a relational database?

1. A unique constraint prevents two saved links from owning garden24.
2. A transaction saves the link and creation result together: either both commit or neither does.
3. A reporting transaction can likewise save a processed visit ID and increase its daily count together.
4. A distributed key-value database is a later option for growth. It still needs a design that preserves these related updates; moving records to separate machines does not supply that guarantee automatically.

06Make one reliable path work

Start with one application, a main database and a backup database copy. The main database accepts changes. The backup can replace it after a failure, using the safeguards described later.

Create the short link

1. Mira enters the garden-event destination and asks for garden24, producing https://go.example/garden24.
2. The application asks the database to insert that code only if it is unused. Two simultaneous requests cannot both pass the database's unique constraint.
3. In the same transaction, save the destination, owner and result for creation request create-17. Return success only after the transaction commits. A retry of create-17 returns this saved result.
4. If Mira did not choose a name, generate a random seven-character code and try the same insert. If it is taken, generate another. Use a cryptographically secure random source, which is designed to make future choices hard to predict.

The example alphabet has 62 characters. Uppercase and lowercase remain distinct in storage and lookup. A URL-safe base-64 alphabet is another choice; ordinary base-64 includes characters needing special URL handling.

Open the short link

1. Ben clicks https://go.example/garden24. The application reads garden24 from the URL path.
2. The application finds that code's saved row in the main database. It rejects an expired or disabled link and checks Ben's account if the link is private.
3. For a permitted link, it sends the destination in a redirect response. Ben's browser then opens the destination website.

Record optional usage statistics

1. To provide Mira's usage report, the application creates a small visit record containing the code, time, broad region and a unique record ID. In this example, that ID is click-81. It identifies this recorded visit, not Ben's account.
2. Save the record in a queue—a waiting list of work for a background reporting program. The program counts visits after the redirect, so Ben does not wait for a report query.
3. Limit the queue and the time spent submitting to it. If it cannot accept a record, still redirect Ben and record that reporting lost an event. Disclose possible undercounting.
4. Initially, queue records and daily counts can use the same database. Move reporting to separate resources if measurements show that it slows lookups.

07Compare key allocation choices

The baseline creates a random code when needed. Compare other choices only after explaining what they change:

How prepared batches recover after a crash

1. The allocator—the program assigning batches—saves that batch 91 belongs to server A before replying to A. The batch contains 128 codes.
2. A uses seven codes, then crashes. Do not give its batch to B: A may have handed out more codes immediately before crashing than we can now confirm.
3. The simplest safe recovery abandons the uncertain remainder and gives B a different batch. At most 121 codes in the uncertain remainder are abandoned, rather than risking a duplicate link.
4. If A retries its allocation request, return the saved batch 91 assignment. Do not assign it again as a new operation.
5. If the allocator is replaced, prevent the old allocator from assigning batches. The next section on failures explains how storage rejects an old writer.

Generated codes and custom aliases share one set of names, so both must pass the same uniqueness check. At our assumed 580 creations/second, test the simple approach before taking on these batch-recovery rules.

08Scale the demonstrated bottleneck

1. Add capacity to the measured limit

• More database memory or a faster machine may be enough initially.
• Add application copies behind a load balancer when CPU or open connections become the limit.
• If one database is too large, group codes into logical partitions and assign groups to machines. Move selected groups when adding machines. Directly changing hash(code) % machineCount can move many records at once.

2. Cache popular destinations

1. Ben opens https://go.example/garden24. The application looks for garden24 in the in-memory cache.
2. If an unexpired entry exists, reuse its saved destination after the required access checks.
3. If the entry is missing, read garden24 from the main database and save a temporary cache copy. A missing entry is a cache miss; this lookup-then-load pattern is called cache-aside.
4. For thousands of simultaneous requests for garden24, let one request perform the database read while the others wait for its result. Limit total waiting and database reads. More database partitions alone cannot help one code that still lives in one partition.
5. Cache “not found” only briefly, so a new link does not stay hidden behind an old negative answer.

3. Enforce the 60-second disabling rule

1. Save the time the current database state was checked, plus link expiry and version, in the cache entry.
2. Set its deadline to the earlier of link expiry or 60 seconds after that check. For a check at 11:59:50, the deadline is no later than 12:00:50.
3. Copying the entry at 12:00:40 preserves 12:00:50. It does not buy another minute.
4. When Mira disables the link, save the change first, then request removal of cache copies. This removal is called invalidation; fixed deadlines still protect the promise if removal is delayed.
5. A backup database that has not received the disable change cannot justify a new deadline from its old row. Private links also require a current allowed-account check, even if their destination is cached.

09Trace a write and a read

Follow one visit from URL to report

1. Save the link. Mira creates https://go.example/garden24. The database saves garden24, its garden-event destination and the result for creation request create-17 together. If Mira loses the response, retrying that request returns the same link.
2. Find the destination. Ben clicks the short URL. The application extracts garden24 from the path. If the cache has no usable entry, it reads the main database and saves a temporary copy with a fixed expiry time.
3. Open the website. The application checks link expiry, disabled state and any private permission. It returns the permitted destination, and Ben's browser visits it.
4. Save a reporting record. Because Mira wants usage statistics, the application offers a visit record to the queue. Its unique ID, click-81, lets the reporting program recognize this same visit if work is retried.
5. Count it once. In one reporting-database transaction, check whether click-81 is in the processed-visit table. If absent, save it and increase garden24's count for that day and broad region. If already present, leave the count unchanged. The saved ID and count change must commit together.
6. Explain the report's delay. The background program may crash after counting but before acknowledging queue completion, so the queue can deliver click-81 again. Step 5 prevents a second count. Keep processed visit IDs for as long as the queue can redeliver those records. Mira's report says how far processing has reached—for example, “complete through noon.” A visit count grouped by day is the daily total; the progress timestamp is sometimes called a processing watermark.
7. Disable the link. Mira disables garden24. New main-database lookups reject it. Cache removal usually stops old copies sooner, while their unchanged deadlines enforce the 60-second limit.

Clean up without changing old links

• Delete destination and personal details under the retention policy, but keep a used-code marker, called a tombstone. The same garden24 URL must never point to a new owner's site.
• Find expired links through an expiry index or scheduled batches. Opening one link must not scan the whole database.
• State backup erasure separately. Refusing a redirect and deleting every stored copy are different operations.
• If reports slow lookups, give their queue, background programs and report database separate capacity. Link state remains in the main mapping database.

10Explain failures, security and cost

If the cache fails

1. Up to 58,000 peak lookups/second may reach the database. Test its real fallback capacity.
2. Limit simultaneous fallback reads and share one read among requests for the same missing code.
3. Gradually refill popular entries. Return a retryable overload error when fallback reads reach the database’s tested request or concurrency limit.

If the main database fails

1. A backup may take over. First ensure the old main database can no longer accept writes; losing contact does not prove that it stopped.
2. For example, the old writer has permission number 12. The replacement receives number 13, recorded by the storage or coordination system that approves writes.
3. Accepting a write must compare its permission number with the saved current number as part of the same indivisible storage operation. A late write carrying 12 is rejected after 13 takes over. A separate earlier check could race the replacement; issuing the number alone is insufficient.
4. This rejection of an old writer is called fencing. If the system cannot establish a single safe writer, pause creations instead of letting both claim the same code.

If reporting or batch allocation fails

• Keep valid redirects working when the report queue is full. Record and disclose missed reporting records.
• Retried reporting work uses the same visit ID and the check-and-count transaction described above.
• The baseline does not need a batch allocator. If an alternative relies on prepared batches and exhausts them, pause new creations while existing links continue opening.

Protect and measure the service

• Rate-limit abusive creation and repeated code guesses; review malicious destinations.
• Avoid logging sensitive URL query parameters. If previews are added, isolate the fetcher and block requests into private networks.
• Measure slow redirects, cache use, fallback reads, age of cached state, duplicate code attempts, reporting delays and dropped records. Each measure should reveal whether a stated requirement is being met.