Design a URL Shortener

# REST API Design for URL Shortener

# 1. Create Short URL
# POST /api/v1/urls
# Request Body:
# {
#   "long_url": "https://example.com/very/long/path",
#   "custom_alias": "my-link",       (optional)
#   "expiry_days": 365               (optional)
# }
# Response: { "short_url": "https://liziu.co/Ab3xK9" }

# 2. Redirect Short URL
# GET /{short_key}
# Response: 301 Redirect to original URL

# 3. Delete Short URL
# DELETE /api/v1/urls/{short_key}
# Response: 204 No Content

from flask import Flask, request, redirect, jsonify
import hashlib
import string

app = Flask(__name__)

class URLShortenerAPI:
    """REST API for URL Shortener Service"""

    def create_short_url(self, long_url: str,
                         custom_alias: str = None,
                         expiry_days: int = 365) -> dict:
        """
        Create a shortened URL.

        Args:
            long_url: The original URL to shorten
            custom_alias: Optional custom short key
            expiry_days: Days until the link expires

        Returns:
            dict with short_url and metadata
        """
        if custom_alias:
            if self.db.exists(custom_alias):
                raise ConflictError("Alias already taken")
            short_key = custom_alias
        else:
            short_key = self.generate_short_key(long_url)

        self.db.save(short_key, long_url, expiry_days)
        return {"short_url": f"https://liziu.co/{short_key}"}

    def redirect_url(self, short_key: str):
        """Look up short key and redirect to original URL."""
        # Check cache first, then database
        long_url = self.cache.get(short_key)
        if not long_url:
            long_url = self.db.get(short_key)
            self.cache.set(short_key, long_url)
        return redirect(long_url, code=301)

-- URL mapping table
CREATE TABLE urls (
    id            BIGINT PRIMARY KEY AUTO_INCREMENT,
    short_key     VARCHAR(7) UNIQUE NOT NULL,
    long_url      VARCHAR(2048) NOT NULL,
    created_at    TIMESTAMP DEFAULT CURRENT_TIMESTAMP,
    expires_at    TIMESTAMP,
    user_id       BIGINT,
    click_count   BIGINT DEFAULT 0,
    INDEX idx_short_key (short_key),
    INDEX idx_expires_at (expires_at)
);

-- User table (optional, for authenticated users)
CREATE TABLE users (
    id            BIGINT PRIMARY KEY AUTO_INCREMENT,
    email         VARCHAR(255) UNIQUE NOT NULL,
    api_key       VARCHAR(64) UNIQUE NOT NULL,
    created_at    TIMESTAMP DEFAULT CURRENT_TIMESTAMP
);

import string

# Base62 character set: a-z, A-Z, 0-9
CHARSET = string.ascii_lowercase + string.ascii_uppercase + string.digits
BASE = 62

def base62_encode(num: int) -> str:
    """
    Convert a numeric ID to a Base62 string.

    Example: 2009215674938 -> 'Ab3xK9z'

    Time:  O(log_62(n)) -- typically 7 iterations
    Space: O(1)
    """
    if num == 0:
        return CHARSET[0]

    result = []
    while num > 0:
        remainder = num % BASE
        result.append(CHARSET[remainder])
        num //= BASE

    return ''.join(reversed(result))


def base62_decode(short_key: str) -> int:
    """Convert a Base62 string back to a numeric ID."""
    num = 0
    for char in short_key:
        num = num * BASE + CHARSET.index(char)
    return num


# Example usage
unique_id = 2009215674938
short = base62_encode(unique_id)
print(f"Encoded: {unique_id} -> {short}")
# Encoded: 2009215674938 -> Ab3xK9z

decoded = base62_decode(short)
print(f"Decoded: {short} -> {decoded}")
# Decoded: Ab3xK9z -> 2009215674938

import hashlib

def hash_based_shorten(long_url: str, length: int = 7) -> str:
    """
    Generate a short key using MD5 hash.

    Pros: No need for a centralized counter
    Cons: Potential collisions require retry logic
    """
    hash_hex = hashlib.md5(long_url.encode()).hexdigest()

    # Take first 43 bits (enough for Base62 7-char key)
    hash_int = int(hash_hex[:11], 16)
    short_key = base62_encode(hash_int)[:7]

    return short_key

# Collision handling: if key exists, append counter and re-hash
def shorten_with_retry(long_url: str, db) -> str:
    """Handle collisions by retrying with modified input."""
    for attempt in range(5):
        candidate = hash_based_shorten(long_url + str(attempt))
        if not db.exists(candidate):
            return candidate
    raise Exception("Could not generate unique key after 5 attempts")

import redis

class URLCache:
    """
    Caching layer for URL Shortener.

    Strategy: Cache the top 20% most accessed URLs.
    With 4,000 reads/sec, we cache ~35 GB of hot data.
    """

    def __init__(self):
        self.client = redis.Redis(
            host='redis-cluster',
            port=6379,
            decode_responses=True
        )
        self.TTL = 86400  # 24 hours

    def get_url(self, short_key: str) -> str:
        """Look up URL in cache. Returns None on miss."""
        return self.client.get(f"url:{short_key}")

    def set_url(self, short_key: str, long_url: str):
        """Cache URL with TTL. Uses LRU eviction policy."""
        self.client.setex(
            f"url:{short_key}",
            self.TTL,
            long_url
        )

    def invalidate(self, short_key: str):
        """Remove URL from cache (e.g., on deletion)."""
        self.client.delete(f"url:{short_key}")