Review: Bitly

Interview scope and guarantees

Create an immutable short link, redirect it, and allow its owner to revoke it. Custom aliases and expiry are optional; click analytics must not delay redirects. Target p99 redirect latency below 100 ms within a serving region. Revocation must reach the serving path within an explicitly agreed window.

Capacity worksheet

Assume 10 million creations/day and 1 billion redirects/day: about 116 writes/s and 11,574 reads/s on average. A 5× peak gives 579 writes/s and 57,870 reads/s. At 500 bytes per mapping, a year is 1.825 TB before indexes and replication. With a 95% cache hit rate, peak origin reads are still about 2,894/s; size for a cold cache too.

Concrete API contract

POST /links {url, customAlias?, expiresAt?} -> 201 {code}
GET /{code} -> 302 Location: target
DELETE /links/{code} -> 204
Idempotency-Key scopes create retries to an authenticated owner.

Data model and access paths

links(code PK, owner_id, target_url, created_at, expires_at, revoked_at, version)
UNIQUE(code); INDEX(owner_id, created_at, code)
creation_keys(owner_id, request_key, request_hash, code); UNIQUE(owner_id, request_key)

Evolve a solution and explain each change

Figure — Three architecture decisions for Bitly, including the pressure each introduces.

Step 1: One durable lookup

Store a unique code and destination; return a temporary redirect after checking expiry. Every redirect hits storage; a popular code concentrates reads.

Step 2: Cache the mapping

Cache immutable targets close to readers; include expiry and revocation state. Cache lifetime can violate the promised revocation interval.

Step 3: Separate analytics

Append bounded click events asynchronously and invalidate serving caches from durable changes. Analytics counts need their own deduplication and loss policy.

Responsibility overview

Figure — Connected responsibilities for Bitly. Trace the authoritative and derived paths separately.

Worked end-to-end scenario

Alice retries creation after a timeout. The API finds her existing idempotency record and returns the same code. A reader follows that code; the service checks expiry, resolves the target, and returns a redirect without fetching the destination. Now Alice revokes it while an edge still holds the mapping. A database update alone cannot prevent that edge from redirecting. Versioned invalidation and a bounded cache lifetime must match the published revocation contract. If the invalidator is down, either accept the stated stale window or put a current deny check on the serving path. The analytics queue can fail without blocking the redirect, provided dropped events are observable.

Why these access paths matter

Code lookup uses the unique primary key. Owner management uses an owner-and-creation index with a stable tie-breaker. A custom alias competes for the same code namespace; enforce uniqueness during insertion. A hot code requires replicated cached copies, whereas adding hash partitions mainly distributes different codes. Cache negative lookups briefly so newly created aliases do not remain invisible for a long time.

Build the baseline first

1. Client → link API → unique mapping table.
2. Redirect request → lookup → expiry check → 302.
3. Owner deletion → durable revocation → invalidation.

Evolve the design under load

1. Redirect edge → regional cache → mapping store.
2. Mapping change → outbox → cache invalidators.
3. Redirect event → bounded analytics stream.

Defend the hardest decision

Eight base62 characters provide 62^8, about 218 trillion possibilities. At one billion occupied codes, a new uniform candidate collides with probability roughly 0.00000458; collisions across the whole history are expected, so a database uniqueness constraint is mandatory. Retry a failed insert with a new candidate. Never check availability and insert as independent operations. Sequential allocation avoids random collisions but exposes enumeration and needs range allocation or another scalable allocator.

Failure and recovery analysis

A revoked link can survive in a cache even after the database is updated. Store a version, invalidate every serving layer, and make the advertised revocation bound consistent with cache lifetime. Do not claim instant revocation while issuing long-lived permanent redirects. For sensitive links, perform a current deny check before redirecting. If analytics fails, preserve redirects and account for dropped or replayed events separately.

Security and privacy boundary

Allow only approved URL schemes, limit link creation, and authorize edits by owner. A redirect service need not fetch the target; adding previews creates an SSRF boundary that needs separate controls.

Interview follow-ups with reasoning

Question: How would custom aliases change uniqueness and abuse protection?

Question: How do you handle a hot code?

Question: What changes for editable targets?

Operate and verify the design

Redirect p99, cache miss rate, origin saturation and revocation delay.

Revoke a heavily cached link during an invalidator outage; measure the actual stale-serving interval.

Compare alternatives

Design workshop: allocate, resolve, and revoke

Our core flows are create, redirect, and owner revocation. Analytics is asynchronous; accounts and billing are outside the interview baseline. Choose a redirect p95 below 100 ms and a controlled-cache revocation bound of 60 seconds as scenario targets, not measured service claims. If the interviewer requires immediate takedown, cached redirects need an online deny check and a different availability trade-off.

Eight base62 characters give 62^8 = 218,340,105,584,896 candidates. At one billion occupied codes, a fresh uniform candidate collides with probability about 0.00000458. This is the next-insert probability, not the probability that no pair ever collided over the system's life. The unique constraint is the correctness mechanism.

# Pseudocode: randomness proposes; the database decides.
for attempt in range(5):
    code = secure_random_base62(8)
    try:
        with transaction():
            claim_creation_key(owner, key, hash_request(body))
            insert_link(code, owner, target, expires_at)
            save_creation_result(owner, key, code)
        return code
    except CodeAlreadyExists:
        continue
raise RetryableAllocationFailure()

A retry first looks up the creation key and compares its fingerprint; the same key with a different URL returns 409. A concurrent uncommitted claim waits or produces a documented retryable response. The claim, mapping and recorded result commit together. A custom alias conflict returns 409 without random retry. Validate supported URL schemes and never shorten a javascript URL.

A counter alternative leases disjoint ID ranges transactionally: worker A receives [1000,1999], B [2000,2999]. Encoding 1000 in base62 repeatedly divides by 62; unused IDs after a crash are holes, not a reason to reuse the range. Counter backup/restore must never move below issued IDs. Random codes reduce enumeration but do not constitute authorization.

Figure — Redirect cache miss and later revocation.

A missing code returns 404; an expired link can return 410. For mutable/revocable targets use temporary redirects and explicit caching policy. A cache entry contains expiry and version; a late version-7 fill must not overwrite a known revocation version 8. Store a short-lived deny/version fence when invalidating, or cap the stale window and admit that guarantee. Origin fallback uses a per-key singleflight and a bounded connection pool, so a cold viral link cannot create unlimited database requests.

Figure — Allocator choices under failure.

At 57,870 peak redirects/s and 95% hits, the ordinary database path sees about 2,894 reads/s before hot-key effects. For 100-byte click events, that redirect peak produces roughly 5.8 MB/s of raw events. Sample analytics only under a stated product policy; use event IDs and bounded deduplication when exact counting is needed. Redirects must still succeed if analytics is unavailable.

Exercise: Range A is issued, the worker crashes after using 1000–1003, and the allocator restores its last durable allocation record. May it reissue 1004?

Redis counter command explains a primitive; its durability and failover contract still need separate treatment in this design.

Technical references

PostgreSQL transaction isolation and concurrent updates.