Bitly (URL Shortener)

Sharpened prompt. Design a link shortener serving 100M new links/day and 10B redirects/day, with a P99 redirect latency under 30ms globally, per-click analytics, custom aliases, and the ability to revoke a malicious link within seconds.

The naive version of this problem is a hash map. Everything interesting comes from three tensions: redirects must be fast enough to be invisible, clicks must all be counted, and those two requirements fight each other.

1. Problem framing

Functional requirements

• POST /links — shorten a long URL, optionally with a custom alias and an expiry.
• GET /{code} — redirect to the target.
• GET /links/{code}/stats — clicks over time, by geography, referrer, device.
• Revoke or re-target an existing link.

Non-functional requirements

Property	Target	Consequence
Redirect latency	P99 < 30ms globally, < 10ms at edge PoP	Data must live near the user, not in one region
Availability of redirects	99.99%	The read path must survive the write path being down
Durability of mappings	No lost links, ever	Mappings go to a durable store before the code is returned
Analytics freshness	< 1 minute	Async pipeline is fine; synchronous counting is not
Read:write ratio	100:1	Optimise ruthlessly for reads

Back-of-the-envelope

Writes:   100M links/day        ≈ 1,160 writes/sec avg,  ~5,000/sec peak
Reads:    10B redirects/day     ≈ 116,000 reads/sec avg, ~500,000/sec peak
Storage:  100M × 500 bytes/day  ≈ 50 GB/day ≈ 18 TB/year (+ index overhead)
Keyspace: Base62, 7 chars       = 62^7 ≈ 3.5 trillion codes
          At 100M/day that is ~95 years of runway. 7 characters it is.
Analytics: 10B events/day × 200 bytes ≈ 2 TB/day raw, ~200 GB/day columnar-compressed

The keyspace calculation is worth saying out loud, because it justifies the ID scheme: with 3.5 trillion slots and 36 billion links a year, collisions are not the problem — coordination is.

2. High-level architecture

Two paths share the page and never block each other: the redirect path (client → edge → maybe origin → 302) and the analytics path (edge log tap → Kafka → Flink → ClickHouse). If Kafka is down, redirects still work; you lose analytics, which is the correct thing to lose.

3. Component inventory

Component	Concrete choice	Why this one
Edge compute	CloudFront Functions (cloudfront-js-2.0) or Cloudflare Workers	Sub-millisecond V8 isolate at the viewer-request phase. Lambda@Edge is a container and adds 5–15ms — the wrong tool here.
Edge datastore	CloudFront KeyValueStore / Workers KV	In-process memory read at the PoP, no network hop. Capped at 5 MB, which is a feature: it forces you to treat it as a hot-set shield, not a database.
L1 cache	Caffeine (JVM) or Ristretto (Go), W-TinyLFU	Absorbs viral bursts inside the app process. See why not LRU.
L2 cache	Redis Cluster, allkeys-lfu	Shared hot set across the fleet; LFU rather than LRU for the same scan-resistance reason.
Primary store	DynamoDB (or Cassandra/ScyllaDB)	Pure key-value access by code. No joins, no range scans on the read path, predictable single-digit-ms lookups, trivial horizontal scaling.
ID allocation	etcd or ZooKeeper handing out ranges	Coordination once per 100k IDs instead of once per write.
Event bus	Kinesis Data Streams → MSK, or Kafka directly	Ordered, replayable, decouples billing-grade counting from serving.
Stream processor	Flink	Event-time windows, exactly-once sinks, and it is where dedup lives.
Analytics store	ClickHouse (or Pinot)	Sub-second GROUP BY country, referrer over billions of rows; a row store cannot do this.

4. Data model and API

-- Primary mapping table (DynamoDB item shape shown as SQL for readability)
CREATE TABLE links (
  code          VARCHAR(12) PRIMARY KEY,   -- partition key, Base62
  long_url      TEXT        NOT NULL,
  owner_id      BIGINT,
  created_at    TIMESTAMPTZ NOT NULL,
  expires_at    TIMESTAMPTZ,               -- DynamoDB TTL attribute
  status        SMALLINT    NOT NULL,      -- 0 active, 1 disabled, 2 malware
  is_custom     BOOLEAN     NOT NULL
);

-- Reverse index, so re-shortening the same URL by the same owner is idempotent
CREATE TABLE links_by_url (
  owner_id      BIGINT,
  url_hash      BYTEA,                     -- sha256(normalise(long_url))
  code          VARCHAR(12),
  PRIMARY KEY (owner_id, url_hash)
);

POST /v1/links
Content-Type: application/json
Idempotency-Key: 8f14e45f-ea6a-4c7b-9f0a-1b2c3d4e5f60

{ "url": "https://example.com/some/very/long/path", "alias": "launch2026", "expires_at": null }

201 Created
{ "code": "launch2026", "short_url": "https://bit.ly/launch2026" }

The Idempotency-Key matters more than it looks: a client retry after a timeout must not burn a second code and leave an orphan.

5. The toughest parts

5.1 Generating IDs at 5,000/sec with no single point of failure

Why it's hard. The three obvious options each fail. A relational AUTO_INCREMENT is a single writer — it is both a bottleneck and a SPOF, and it makes multi-region writes impossible. Hashing the URL (md5(url)[:7]) produces collisions that require a read-before-write on every insert, and at 3.5 trillion slots your collision rate is low but your IOPS waste is real, plus the same URL shortened twice by two users returns the same code, which breaks per-owner analytics. Pure random 7-char strings need a uniqueness check against a table with tens of billions of rows on every single write.

Solution — distributed range allocation. Each write node leases a disjoint block of the 64-bit counter space from etcd, then hands out IDs from memory with an atomic increment. Coordination happens once per 100,000 links instead of once per link.

// Range allocator: one etcd round-trip per 100k IDs, then pure in-memory issuance.
type Allocator struct {
    next, end uint64
    mu        sync.Mutex
    kv        clientv3.KV
}

const blockSize = 100_000

func (a *Allocator) Next(ctx context.Context) (uint64, error) {
    a.mu.Lock()
    defer a.mu.Unlock()
    if a.next >= a.end {
        if err := a.leaseBlock(ctx); err != nil { // CAS on etcd key "id/cursor"
            return 0, err
        }
    }
    id := a.next
    a.next++
    return id, nil
}

// leaseBlock does a compare-and-swap so two nodes can never win the same block.
func (a *Allocator) leaseBlock(ctx context.Context) error {
    for {
        resp, _ := a.kv.Get(ctx, "id/cursor")
        cur := decode(resp.Kvs[0].Value)
        txn := a.kv.Txn(ctx).
            If(clientv3.Compare(clientv3.ModRevision("id/cursor"), "=", resp.Kvs[0].ModRevision)).
            Then(clientv3.OpPut("id/cursor", encode(cur+blockSize)))
        ok, err := txn.Commit()
        if err != nil { return err }
        if ok.Succeeded {
            a.next, a.end = cur, cur+blockSize
            return nil
        } // lost the race, retry
    }
}

Then Base62-encode, but not the raw counter — sequential IDs make your entire link corpus enumerable by a scraper.

const alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

// Feistel network: a keyed, reversible permutation of the 42-bit ID space.
// Output is uniformly scattered, still collision-free, still 7 chars.
func obfuscate(id uint64) uint64 {
    l, r := uint32(id>>21)&0x1FFFFF, uint32(id)&0x1FFFFF
    for i := 0; i < 4; i++ {
        l, r = r, l^(round(r, i)&0x1FFFFF)
    }
    return uint64(l)<<21 | uint64(r)
}

func encode(n uint64) string {
    if n == 0 { return "0" }
    buf := make([]byte, 0, 11)
    for n > 0 {
        buf = append(buf, alphabet[n%62])
        n /= 62
    }
    slices.Reverse(buf)
    return string(buf)
}

The trade-off to state. Leased blocks mean IDs are not globally monotonic and a node crash wastes up to 100k codes. With 3.5 trillion codes, wasting a few million on restarts is free. Say that number — it converts an apparent flaw into a deliberate choice.

Alternative worth naming: Twitter Snowflake (timestamp | machine ID | sequence) gives 64-bit IDs with no coordination at all, but encodes to 11 Base62 characters and leaks creation time. Range allocation buys shorter URLs at the cost of one dependency.

5.2 Custom aliases: a uniqueness race across regions

Why it's hard. Generated codes cannot collide by construction. Custom aliases can — two users can request launch2026 in the same millisecond in two regions. And the check-then-write pattern (if not exists: write) is a textbook race. There is also a policy problem hiding in here: reserved words (admin, api, login), profanity, and homograph attacks (paypa1 vs paypal).

Solution. Make the claim a single atomic conditional write in the primary store, not a read followed by a write:

# DynamoDB: the condition expression is evaluated inside the storage node.
try:
    table.put_item(
        Item={"code": alias, "long_url": url, "owner_id": uid, "is_custom": True},
        ConditionExpression="attribute_not_exists(code)",
    )
except ClientError as e:
    if e.response["Error"]["Code"] == "ConditionalCheckFailedException":
        raise AliasTaken(alias)   # 409, deterministic, no lock held anywhere
    raise

For multi-region active-active, custom aliases must be routed to a single home region per alias (hash the alias to a region) or written through a globally-linearizable store (DynamoDB global tables are last-writer-wins and will silently lose one of the two claims — that is the trap). Say this explicitly: "Generated codes I'll serve active-active; custom alias creation I pin to a home region, because last-writer-wins on a namespace claim is a correctness bug, not an eventual-consistency inconvenience."

Reserved words go in a compiled prefix trie loaded at boot; confusables go through Unicode skeleton normalisation (UTS-39) before the uniqueness check.

5.3 The 10ms redirect: terminating at the edge

Why it's hard. A user in Jakarta hitting an origin in us-east-1 pays 200ms+ in round-trip time before your server even reads the request. No amount of backend optimisation fixes the speed of light. But the edge cannot hold billions of links, and it cannot talk to Kafka.

Solution. Put the hot 0.1% at the edge and let everything else fall through. Traffic is Zipfian: roughly 50k codes carry the large majority of requests.

import cf from 'cloudfront';
const kvs = cf.kvs();

async function handler(event) {
  const request = event.request;
  const code = request.uri.slice(1);
  if (!code) return request;              // root path, let origin handle it

  try {
    const target = await kvs.get(code);   // in-process memory read, < 1ms
    return {
      statusCode: 302,
      statusDescription: 'Found',
      headers: {
        'location': { value: target },
        // Short private cache: absorbs repeat clicks, keeps revocation fast.
        'cache-control': { value: 'private, max-age=60' },
      },
    };
  } catch (err) {
    return request;                        // MISS -> forward to origin
  }
}

Returning the request object unmodified is what makes CloudFront continue to the origin; returning a response object terminates at the edge. On a miss, the origin resolves from Redis/DynamoDB and responds with Cache-Control: public, max-age=300, so the standard CloudFront cache absorbs the next five minutes of traffic for that code even though it never entered the KV store.

A background worker watching the click stream promotes any code exceeding ~10 clicks/minute into the edge KV store, which propagates to all PoPs in 2–10 seconds. Cold link → warm CDN cache → hot edge KV is a three-stage escalator, and describing it is a strong signal.

The 301-vs-302 decision is the classic follow-up and deserves its own treatment: HTTP 301 vs 302 for shorteners. Short version: 302 with a 60-second private Cache-Control, because analytics and revocation are the product.

Edge store limits worth knowing (they make the answer concrete): CloudFront KVS caps at 5 MB total, 512-byte keys, 1 KB values, so roughly 45,000–55,000 short-link records. Links whose target exceeds 1 KB simply never get promoted.

5.4 Viral links and cache pollution

Why it's hard. A link goes viral and pulls 500k QPS in ten seconds. Meanwhile a crawler sweeps 100,000 distinct cold links. Under plain LRU, the crawler's one-hit-wonders enter at the head of the list and evict the steady-state high-value keys, so a second later the valuable traffic all misses and lands on the database at once.

Solution — admission control, not just eviction. W-TinyLFU (Caffeine, Ristretto) keeps a Count-Min Sketch of recent frequencies and asks, on every insert, "is this candidate more frequent than the victim I would evict?" A one-hit-wonder with frequency 1 loses to a resident key with frequency 50 and is never admitted.

Cache<String, String> l1 = Caffeine.newBuilder()
    .maximumSize(1_000_000)                       // ~200 MB of short strings
    .expireAfterWrite(Duration.ofMinutes(5))      // bounds staleness after revocation
    .refreshAfterWrite(Duration.ofMinutes(1))     // async refresh, never a stall
    .recordStats()
    .build(code -> redis.get(code));              // L1 miss falls through to L2

Pair it with singleflight so that a miss on a hot key produces exactly one downstream fetch rather than 50,000:

var g singleflight.Group

func resolve(ctx context.Context, code string) (string, error) {
    v, err, _ := g.Do(code, func() (any, error) {  // concurrent callers coalesce
        return db.Get(ctx, code)
    })
    return v.(string), err
}

The full mechanism, including why 2Q/SLRU also works, is in Cache eviction: LRU vs W-TinyLFU.

5.5 Counting 10B clicks/day without touching the read path

Why it's hard. Incrementing a counter row per click is 116k writes/sec of contention on the hottest rows in the system, and it puts the analytics database in the redirect's critical path. If ClickHouse hiccups, redirects must not.

Solution — log, then aggregate, never count inline. The edge emits the click through CloudFront Real-Time Logs (out-of-band, zero added latency, because edge functions cannot make outbound network calls at all) into Kinesis; Flink windows and rolls up; ClickHouse serves the dashboard.

// Flink: 1-minute tumbling rollups, event time, with bounded lateness for mobile.
clicks
  .assignTimestampsAndWatermarks(
      WatermarkStrategy.<Click>forBoundedOutOfOrderness(Duration.ofMinutes(2))
          .withTimestampAssigner((c, ts) -> c.eventTimeMs))
  .keyBy(c -> new Key(c.code, c.country, c.referrer))
  .window(TumblingEventTimeWindows.of(Time.minutes(1)))
  .allowedLateness(Time.hours(1))
  .aggregate(new CountAndUniques())      // count + HyperLogLog of visitor hashes
  .sinkTo(clickhouseSink);               // idempotent upsert on (code, minute, dims)

Unique-visitor counts use HyperLogLog: ~12 KB per sketch for a 2% error on cardinalities into the billions, and sketches merge, so a daily unique count is the union of 1,440 minute sketches rather than a re-scan.

Make the sink idempotent on (code, minute, country, referrer) so that a Flink restart replaying from the last checkpoint overwrites rather than double-counts. This is how you get effectively-once accounting without distributed transactions.

5.6 Abuse: revoking a malicious link in seconds

Why it's hard. Shorteners are phishing infrastructure by nature — they hide the destination. When Trust & Safety flags bit.ly/xyz as malware, it must stop redirecting everywhere within seconds. But you have deliberately built four layers of caching (browser, CDN, edge KV, Redis, L1) whose entire purpose is to not ask you again. This is the direct cost of §5.3, and interviewers love pulling on it.

Solution — bound every layer's staleness and push an explicit purge.

1. Never emit a 301 and never emit a long max-age. private, max-age=60 caps browser staleness at one minute.
2. On revocation, fan out in parallel: delete from edge KV, issue a CDN path invalidation for /xyz, DEL from Redis, and publish to a Redis Pub/Sub channel that every app instance subscribes to for L1 invalidation.
3. Write status = 2 to the primary store first, so any layer that repopulates gets the blocked state.

async def revoke(code: str, reason: str):
    await ddb.update_item(Key={"code": code},
                          UpdateExpression="SET #s = :blocked",
                          ExpressionAttributeNames={"#s": "status"},
                          ExpressionAttributeValues={":blocked": 2})
    await asyncio.gather(
        kvs.delete_key(code),                       # edge KV, propagates in ~5s
        cdn.create_invalidation(paths=[f"/{code}"]),# CDN cache
        redis.delete(f"link:{code}"),               # L2
        redis.publish("link:invalidate", code),     # L1 across the fleet
    )

Detection is asynchronous and layered: check the target against the Google Safe Browsing API at creation time, re-scan on a schedule (attackers shorten a benign page and swap the destination later — so re-target is itself a scan trigger), and run a Flink job on the click stream flagging codes with anomalous velocity from a narrow referrer set.

5.7 Expiry, deletion, and reclaiming a keyspace you promised not to reuse

Why it's hard. At 100M links/day, expired and abandoned links accumulate into tens of billions of dead rows. But you must not recycle a code: an old link in an email from 2019 pointing at someone else's site is worse than a 404, and if the recycled code was in someone's browser cache with a 301, it is a hijack.

Solution. Treat expiry as a status change, not a delete. Use the store's native TTL (DynamoDB TTL, Cassandra USING TTL) to drop the payload while retaining a compact tombstone — a Bloom-filter-backed "issued codes" set so the allocator's Feistel permutation is never asked to re-mint one. Because IDs come from a monotonically leased counter, this is free: the counter never goes backwards, so codes are never reissued regardless of what you delete. State that explicitly — it is a design property you got for free from §5.1, and noticing it is the kind of thing that lands.

Cold links (no click in 12 months) migrate from DynamoDB to S3 + Athena, cutting the hot store by an order of magnitude. Resolution of an archived link is allowed to take 2 seconds; nobody is clicking it interactively.

6. What breaks first

Load event	First failure	Mitigation
One viral link at 500k QPS	L2 Redis hot shard CPU-saturates	L1 W-TinyLFU absorbs it in-process; edge KV promotion removes it from origin entirely
Crawler sweeping cold links	Cache hit rate collapses, DynamoDB throttles	Admission control (§5.4) plus per-IP rate limiting at the edge
Kafka partition unavailable	Analytics lag; redirects unaffected	The tap is out-of-band by construction; buffer at the producer, backfill from CDN standard logs in S3
etcd cluster loses quorum	New links fail; redirects unaffected	Each write node still has up to 100k unissued IDs in its leased block — hours of runway
Region loss	Reads served from other regions	Read path is multi-region; custom-alias writes fail over with a documented RPO

Notice the pattern in that table: every failure degrades writes or analytics, never redirects. That is the availability argument for the whole architecture, and it is worth saying in exactly those words.

7. Cheat sheet

• ID: etcd-leased 100k blocks → Feistel permutation → Base62, 7 chars, 3.5T keyspace, ~95 years of runway.
• Read path: edge function + edge KV for the hot 50k → CDN cache → L1 Caffeine (W-TinyLFU) → Redis → DynamoDB.
• 302, not 301, with private, max-age=60 — analytics and revocation are the product.
• Analytics: out-of-band real-time logs → Kinesis/Kafka → Flink event-time windows + HLL → ClickHouse. Never counts inline.
• Custom aliases: conditional write (attribute_not_exists), home region per alias, never LWW.
• Abuse: every cache layer has bounded staleness plus an explicit purge fan-out.
• The one-liner: "This is a read-heavy key-value lookup with a Zipfian hot set, so the whole design is a cache hierarchy that reaches the edge, plus a strictly out-of-band counting pipeline."