Design a URL Shortener

Given: https://example.com/very/long/url?with=params&and=more
Return: https://sho.rt/abc123

Visit https://sho.rt/abc123
  → 301/302 redirect to https://example.com/very/long/url?with=params&and=more

Non-functional:
  - Redirect latency: < 50ms
  - Availability: 99.99%
  - 100M URLs created per day
  - 10B redirects per day

import string
import random

CHARSET = string.ascii_letters + string.digits  # a-z, A-Z, 0-9

def generate_key(url: str) -> str:
    # Option 1: Random key (simple, risk of collision)
    return ''.join(random.choices(CHARSET, k=7))

def generate_key_deterministic(url: str) -> str:
    # Option 2: Hash-based (deterministic, check for collision)
    import hashlib
    hash_val = int(hashlib.md5(url.encode()).hexdigest(), 16)
    key = ""
    while hash_val > 0:
        key += CHARSET[hash_val % 62]
        hash_val //= 62
    return key[:7]

def generate_key_autoincrement() -> str:
    # Option 3: Auto-increment + Base62 (guaranteed unique)
    counter = redis.incr("url_counter")
    key = ""
    while counter > 0:
        key = CHARSET[counter % 62] + key
        counter //= 62
    return key

CREATE TABLE urls (
    id BIGSERIAL PRIMARY KEY,
    short_key VARCHAR(7) UNIQUE NOT NULL,
    original_url TEXT NOT NULL,
    created_at TIMESTAMP DEFAULT NOW(),
    expires_at TIMESTAMP,
    user_id BIGINT,
    click_count BIGINT DEFAULT 0
);

CREATE INDEX idx_urls_short_key ON urls(short_key);
CREATE INDEX idx_urls_user_id ON urls(user_id);
CREATE INDEX idx_urls_created_at ON urls(created_at);

Client ──► API Gateway ──► URL Service
                               │
                               ├── Write path:
                               │   Generate key → Store in DB → Cache in Redis
                               │
                               └── Read path:
                                   Lookup key → Cache hit? Serve
                                            → Cache miss? DB lookup → Cache → Serve