{"title":"Design URL Shortener","description":null,"content":"\n> **QUESTION**\n>\n> #### What is an URL Shortener?\n>\n> A URL shortener is a service that converts long URLs into compact, easy-to-share aliases. When users access the short URL, they are redirected to the original destination.\n>\n> \n> \n>\n> An url shortener makes links easier to share on social media, track for analytics, and remember.\n>\n> **Popular Examples: **[**tinyurl.com**](undefined)**, **[**bitly.com**](undefined)\n\n\nThis problem is a common choice in system design interviews and serves as a great starting point to practice designing scalable, high-traffic systems.\n\nIn this chapter, we will explore the **high-level design of a URL shortener**.\n\nLets start by clarifying the requirements.\n\n---\n\n# 1. Clarifying Requirements\n\nBefore starting the design, it's important to ask thoughtful questions to uncover hidden assumptions, clarify ambiguities, and define the system's scope more precisely.\n\nHere is an example of how a discussion between the candidate and the interviewer might unfold:\n\n\n> **DISCUSSION**\n>\n> **Candidate:** \"What is the expected scale? How many new URLs per day and how many redirects?\"\n>\n> **Interviewer:** \"Let's aim for 10 million new URLs per day and a 100:1 read-to-write ratio.\"\n>\n> **Candidate**: \"What characters are allowed in the shortened URL?\"\n>\n> **Interviewer**: \"Shortened URL can be a combination of numbers (0-9) and characters (a-z, A-Z).\"\n>\n> **Candidate:** \"Should users be able to specify custom aliases for their URLs?\"\"\n>\n> **Interviewer:** \"Custom aliases are a nice-to-have feature if time permits.\"\n>\n> **Candidate:** \"Do short URL need to expire after a certain time?\"\n>\n> **Interviewer:** \"Yes, there should be a default expiration date, with the option for users to override it.\"\n>\n> **Candidate:** \"Do we need analytics like click counts?\"\n>\n> **Interviewer:** \"Basic click counts would be good, but advanced analytics is not required.\"\n\n\nAfter gathering the details, we can summarize the key system requirements.\n\n## 1.1 Functional Requirements\n\n- **Shorten URL:** Given a long URL, generate a unique short URL.\n- **Redirect:** When a short URL is accessed, redirect the user to the original long URL.\n- **Custom Aliases:** Allow users to create custom short codes (if available).\n- **Expiration:** Support link expiration with default and custom TTLs.\n- **Analytics:** Track basic click counts for each short URL.\n\n## 1.2 Non-Functional Requirements\n\n- **High Availability:** The system must be highly available (e.g., 99.99%).\n- **Low Latency:** Redirect requests must complete in under 50ms (p99).\n- **Uniqueness:** Each long URL should map to a unique short URL.\n- **Scalability:** Should handle a large number of read and write requests (100:1 read-to-write ratio).\n- **Durability:** Once a short URL is created, the mapping must not be lost.\n\n---\n\n# 2. Back-of-the-Envelope Estimation\n\nTo understand the scale of our system, let’s make some reasonable assumptions.\n\n\n> **NOTE**\n>\n> #### Assumptions:\n>\n> - New links created: **10 million per day**\n> - **100:1 read/write ratio** ~**1 billion redirects per day**\n\n\n#### **Writes **(URL Shortening)\n\n- Average write QPS = `10,000,000 / (24 * 3600)` ≈ **115 QPS (steady state)**\n- Peak write load (3x factor) ≈ **350 QPS**\n\n#### **Reads **(Redirects)\n\n- Average read QPS = `1,000,000,000 / (24 * 3600)` ≈ **11,500 QPS (steady state)**\n- Peak read load (3x factor) ≈ **35,000 QPS**\n\n#### Storage (5 Years)\n\nEach URL mapping stores:\n\n- Short code: ~7 characters = 7 bytes\n- Long URL: average 200 characters = 200 bytes\n- User ID: UUID = 36 bytes\n- Timestamps, metadata: ~50 bytes\n\n**Total per record: ~300 bytes**\n\n- URLs per year: `10M/day * 365 days` = **3.65 billion URLs/year**\n- Storage per year: `3.65B * 300 bytes` = **~1.1 TB/year**\n- 5-year storage: **~5.5 TB**\n\n#### Short Code Length\n\nUsing Base62 encoding (a-z, A-Z, 0-9):\n\n- 6 characters: 62^6 = **56.8 billion** unique codes\n- 7 characters: 62^7 = **3.5 trillion** unique codes\n\nWith 3.65 billion URLs per year, a **7-character code** provides ample headroom for decades of growth.\n\n---\n\n# 3. Core APIs\n\nThe URL shortener service needs a minimal but powerful set of APIs to create, manage, and resolve shortened links. Below are the core** **endpoints.\n\n### **1. Create Short URL**\n\n#### Endpoint: `POST /shorten`\n\nThis endpoint takes a long URL (and optional parameters) and generates a corresponding short URL.\n\n##### **Sample Request:**\n\n\n```json\n{\n \"long_url\": \"https://example.com/very/long/url/that/needs/shortening\",\n \"custom_alias\": \"\",\n \"expiry_date\": \"2024-12-31T23:59:59Z\",\n \"user_id\": \"user123\"\n}\n```\n\n\n- **long_url** *(required)*: The original URL that needs shortening.\n- **custom_alias** *(optional)*: A user-defined alias for the short link (e.g., `/my-link`). If provided, the system validates uniqueness.\n- **expiry_date** *(optional)*: Timestamp when the short link should expire. If omitted, the link is permanent (or defaults to a system-wide policy).\n- **user_id** *(optional)*: Identifies the user creating the link. Useful for analytics, access control, and management features.\n\n##### **Sample Response:**\n\n\n```json\n{\n \"short_url\": \"http://short.url/abC123\",\n \"long_url\": \"https://example.com/very/long/url/that/needs/shortening\",\n \"expiry_date\": \"2024-12-31T23:59:59Z\",\n \"created_at\": \"2024-08-10T10:30:00Z\"\n}\n```\n\n\n- **short_url**: The shortened link generated by the system.\n- **long_url**: The original URL.\n- **expiry_date**: The expiration timestamp (if set).\n- **created_at**: When the short link was created.\n\n##### **Error Cases:**\n\n- `409 Conflict`: If a custom alias already exists.\n- `400 Bad Request`: If the URL is invalid.\n- `401 Unauthorized`: If the user is not authenticated.\n\n### **2. Redirect to Long URL**\n\n#### Endpoint: `GET /{short_code}`\n\nThis endpoint takes the short URL key and redirects the user to the corresponding long URL.\n\n##### **Sample Response:**\n\n\n```shell\nHTTP/1.1 301 Moved Permanently Location: https://www.example.com/some/very/long/url\n```\n\n\n- `301 Moved Permanently`: Used when the short link is permanent.\n- `302 Found`: Can be used for temporary redirects (if expiry or temporary policy applies).\n\n##### **Behavior:**\n\n- If the short URL exists and is active, return an HTTP redirect.\n- If the link has expired, return `410 Gone`.\n- If the link does not exist, return `404 Not Found`.\n\n### 3. Get URL Analytics\n\n#### Endpoint: `GET /analytics/{short_code}`\n\nRetrieves click statistics for a short URL.\n\n##### **Sample Response:**\n\n\n```json\n{\n \"short_code\": \"abc123\",\n \"total_clicks\": 15420,\n \"created_at\": \"2025-01-15T10:30:00Z\",\n \"last_accessed\": \"2025-01-20T14:22:00Z\"\n}\n```\n\n\n---\n\n# 4. High-Level Design\n\nAt a high level, our system must satisfy two core requirements:\n\n1. **URL Shortening:** Users should be able to submit a long URL and receive a shortened version.\n2. **Redirection:** When users access the short URL, they should be redirected to the original long URL.\n\nSince the system has a **100:1 read-to-write ratio** (1 billion reads vs. 10 million writes daily), we should design the read path (redirects) to be extremely optimized. We will separate the write service from the read service so each can scale independently.\n\n\n> **NOTE**\n>\n> Instead of presenting the full architecture at once, we'll build it incrementally by addressing one requirement at a time. This approach mirrors how you would explain the design in an interview.\n\n\n## 4.1 Requirement 1: URL Shortening\n\nWhen a user submits a long URL, we need to generate a unique short code, store the mapping, and return the short URL.\n\n## Components Needed\n\n N1\\n LB --> N2\\n LB --> N3\\n end\\n\\n UGS([\\\"URL Generation
Service\\\"]):::svc\\n RS([\\\"Redirection
Service\\\"]):::svc\\n DB[(Database)]:::db\\n\\n %% Connections\\n C --> LB\\n N1 -->|Write| UGS\\n N3 -->|Read| RS\\n UGS --> DB\\n RS --> DB\\n\\n %% Styling\\n classDef client fill:#00ceff,stroke:#000,color:#000\\n classDef lb fill:#69db7c,stroke:#000,color:#000\\n classDef lbNode fill:#69db7c,stroke:#000,color:#000\\n classDef svc fill:#ffa94d,stroke:#000,color:#000\\n classDef db fill:#69db7c,stroke:#000,color:#000\"} -->\n```mermaid\nflowchart TD\n %% Nodes\n C[Client]:::client\n\n subgraph LBG[\"Load Balancer\"]\n direction TB\n LB[ ]:::lb\n subgraph POOL[\" \"]\n direction LR\n N1[ ]:::lbNode\n N2[ ]:::lbNode\n N3[ ]:::lbNode\n end\n LB --> N1\n LB --> N2\n LB --> N3\n end\n\n UGS([\"URL Generation
Service\"]):::svc\n RS([\"Redirection
Service\"]):::svc\n DB[(Database)]:::db\n\n %% Connections\n C --> LB\n N1 -->|Write| UGS\n N3 -->|Read| RS\n UGS --> DB\n RS --> DB\n\n %% Styling\n classDef client fill:#00ceff,stroke:#000,color:#000\n classDef lb fill:#69db7c,stroke:#000,color:#000\n classDef lbNode fill:#69db7c,stroke:#000,color:#000\n classDef svc fill:#ffa94d,stroke:#000,color:#000\n classDef db fill:#69db7c,stroke:#000,color:#000\n```\n\n\n### **1. Clients**\n\nClients are end-users or applications interacting with the system via** **web browsers, mobile apps, or third-party integrations (e.g., APIs).\n\nThey use:\n\n- `POST /shorten` to generate short URLs.\n- `GET /{short_code}` to resolve and access the original URLs.\n\n### **2. Load Balancer**\n\nThe **Load Balancer** sits in front of all application servers and plays a key role in ensuring **high availability and scalability**.\n\n**Responsibilities:**\n\n- Distributes incoming traffic across multiple application servers.\n- Ensures high availability and fault tolerance by rerouting traffic if one server fails.\n- Can also perform SSL termination and basic request filtering (e.g., rate limiting).\n\n### **3. URL Generation Service**\n\nThis service handles all **write operations**, including creation and management of new short URLs.\n\n**Key Responsibilities:**\n\n- Validating input URLs.\n- Generating unique short codes.\n- Handling **custom aliases** provided by users.\n- Storing metadata like expiry date, creation time, and user ID.\n\nSince write traffic is relatively low compared to reads, this service doesn’t need to scale aggressively.\n\n### **4. Redirection Service**\n\nThe **Redirection Service** handles the overwhelming majority of traffic — typically **billions of GET requests per day**. It must be **ultra-fast**, **stateless**, and **horizontally scalable**.\n\n**Responsibilities:**\n\n- Looks up the original long URL for a given short code.\n- Determine if the link is still valid (not expired or deleted).\n- Issues an HTTP **301 (Permanent)** or **302 (Temporary)** redirect based on the system’s policy.\n- Caches frequently accessed mappings to minimize database hits.\n\nThis component’s design should focuse on **low latency**, **caching efficiency**, and **high read throughput**.\n\n### **5. Database**\n\nThe database stores the mapping between **short codes and long URLs**, along with relevant metadata.\n\nMust support:\n\n- **High read throughput** to sustain redirection traffic.\n- **Write durability** to ensure links are not lost.\n\n### Flow: Creating a Short URL\n\n\n```mermaid\nsequenceDiagram\n participant C as Client\n participant LB as Load Balancer\n participant WS as Write Service\n participant DB as Database\n\n C->>LB: POST /api/v1/shorten\n LB->>WS: Forward request\n WS->>WS: Validate URL\n WS->>WS: Generate short code\n WS->>DB: Store mapping\n DB-->>WS: Confirm write\n WS-->>LB: Return short URL\n LB-->>C: Response\n```\n\n\n1. Client sends a `POST /api/v1/shorten` request with the long URL.\n2. The **Load Balancer** routes the request to a **URL Shortening Service** instance.\n3. The service validates the URL format and generates a unique short code.\n4. The service stores the mapping (short_code -> long_url) in the **Database**.\n5. The service returns the complete short URL to the client.\n\n## 4.2 Requirement 2: URL Redirection\n\nWhen a user clicks a short URL, we need to look up the original URL and redirect them.\n\n### Additional Components Needed\n\n#### **Redirection Service**\n\nThis service handles all read operations. Since reads dominate (1 billion per day), this service must be highly optimized.\n\n**Responsibilities:**\n\n- Look up the long URL for a given short code.\n- Check if the link is expired.\n- Return an HTTP redirect response.\n\n#### **Cache Layer (Redis)**\n\nTo achieve sub-50ms latency at 35,000 QPS, we need a distributed cache.\n\n**Responsibilities:**\n\n- Store frequently accessed URL mappings.\n- Reduce database load for popular links.\n- Provide sub-millisecond lookup times.\n\n### Flow: Redirecting to Original URL\n\n\n```mermaid\nsequenceDiagram\n participant C as Client\n participant LB as Load Balancer\n participant RS as Read Service\n participant Cache as Redis Cache\n participant DB as Database\n\n C->>LB: GET /abc123\n LB->>RS: Forward request\n RS->>Cache: Lookup short code\n alt Cache Hit\n Cache-->>RS: Return long URL\n else Cache Miss\n RS->>DB: Query mapping\n DB-->>RS: Return long URL\n RS->>Cache: Update cache\n end\n RS->>RS: Check expiration\n RS-->>LB: 302 Redirect\n LB-->>C: Redirect to long URL\n```\n\n\n1. Client requests `GET /abc123`.\n2. The **Load Balancer** routes to a **Redirection Service** instance.\n3. The service first checks the **Redis Cache** for the short code.\n4. On cache hit, return the long URL immediately.\n5. On cache miss, query the **Database**, then populate the cache.\n6. The service validates the link is not expired.\n7. Return an HTTP 302 redirect to the original URL.\n\n---\n\n# 5. Database Design\n\n## 5.1 SQL vs NoSQL\n\nTo choose the right database for our needs, let's consider some factors that can affect our choice:\n\n\n> **SUCCESS**\n>\n> - We need to store billions of records.\n> - Most database operations are simple key-value lookups.\n> - Read queries are much higher than write queries.\n> - We don't need joins between tables.\n> - Database needs to be highly scalable and available.\n\n\nGiven these points, a **NoSQL database** like **DynamoDB** or **Cassandra** is a better option due to their ability to efficiently handle billions of simple key-value lookups and provide high scalability and availability.\n\n## 5.2 Database Schema\n\nEven though our system is simple, we should carefully design the schema to support both **redirection** and **user management**. At a minimum, we need two core tables.\n\n### **1. URL Mappings Table**\n\nStores the relationship between a short code and its corresponding long URL.\n\n\n| Field | Type | Description |\n|-------|------|-------------|\n| `short_code` | String (PK) | Unique identifier, partition key |\n| `long_url` | String | Original destination URL |\n| `user_id` | String | Creator's user ID (optional) |\n| `created_at` | Timestamp | When the link was created |\n| `expires_at` | Timestamp | When the link expires |\n| `click_count` | Integer | Number of redirects |\n| `is_custom` | Boolean | Whether this is a custom alias |\n\n\n**Indexes:**\n\n- Primary key on `short_code` for fast lookups.\n- Secondary index on `user_id` to list a user's links.\n\n### **2. Users Table (Optional)**\n\nStores user-related information for personalization, analytics, and management.\n\n\n| Field | Type | Description |\n|-------|------|-------------|\n| `user_id` | String (PK) | Unique user identifier |\n| `email` | String | User's email address |\n| `created_at` | Timestamp | Account creation date |\n| `api_key` | String | For programmatic access |\n\n\n---\n\n# 6. Design Deep Dive\n\nNow that we have the high-level architecture and database schema in place, let’s dive deeper into some critical design choices.\n\n## **6.1 Unique URL Generation**\n\nThe **short code generation strategy** is one of the most critical aspects of a URL shortener. A good algorithm should ensure that the generated codes are:\n\n- **Unique** → No collisions between different URLs.\n- **Compact** → Small enough to keep the short link truly “short.”\n- **Efficient** → Generated quickly without bottlenecks.\n- **Scalable** → Should work across distributed servers.\n\nLet's explore three primary approaches, moving from simple to highly scalable.\n\n### **Approach 1: Hashing + Encoding** (Deterministic)\n\nThis is one of the simplest and most popular techniques for generating short URLs.\n\nThe idea is to use a **cryptographic hash function** to create a unique fingerprint of the long URL, then **encode** it into a compact, URL-safe string.\n\n#### How It Works\n\n##### **1. Canonicalize the URL**\n\nBefore hashing, the URL must be standardized to avoid generating multiple short links for what is essentially the same destination.\n\n**Example: **The following URLs all point to the same page but would hash differently if not normalized:\n\n\n```shell\nhttps://Example.com/\nhttps://example.com\nhttps://example.com:443/\n```\n\n\n**Canonicalization Steps:**\n\n- Convert the domain to lowercase.\n- Remove default ports (`:80` for HTTP, `:443` for HTTPS).\n- Normalize trailing slashes.\n- Remove unnecessary query parameters (if business logic allows).\n\nAfter canonicalization, these all become: \n\n##### **2. Generate a Hash**\n\nApply a **cryptographic hash function** like `SHA-256`, `SHA-1`, or `MD5` to the canonicalized URL.\n\nFor example:\n\n\n```shell\nLong URL: https://example.com/courses/system-design\nMD5: 1b3aabf5266b0f178f52e45f4bb430eb\n```\n\n\nThis gives us a **fixed-length fingerprint** (128 bits for MD5, 256 bits for SHA-256).\n\n##### **3. Truncate and Encode**\n\nWe don’t need the full hash, it’s too long for a short link.\n\nInstead, we take the first few bytes (e.g., 48 bits = 6 bytes) and **encode** them using **Base62**.\n\n\n> **TIP**\n>\n> #### **Why Base62?**\n>\n> Base62 encoding uses a 62-character set (`A-Z`, `a-z`, `0-9`) that is URL-friendly. It's preferred over Base64, which includes `+` and `/`, characters that have special meaning in URLs and would require escaping. \n>\n> A 48-bit number, when Base62 encoded, produces a compact code of approximately 8 characters (`62^7 < 2^48 < 62^8`).\n>\n> This allows **~281 trillion** (62⁸) unique short codes, more than enough for most systems.\n\n\n#### **Example Workflow**:\n\n1. User submits a request to generate short url for the long url:\n2. Generate an MD5 hash of the long URL. MD5 produces a 128-bit hash, typically a 32-character hexadecimal string: `1b3aabf5266b0f178f52e45f4bb430eb`\n3. Instead of encoding the entire 128-bit hash, we typically use a portion of the hash (e.g., the first few bytes) to create a more manageable short URL. First 6 bytes of the hash: `1b3aabf5266b`\n4. Convert these bytes to decimal: `1b3aabf5266b` (hexadecimal) → `47770830013755` (decimal)\n5. Encode the result into a Base62 encoded string: `DZFbb43`\n\nThe specific choice of 6 bytes (48 bits) is important because it produces a decimal number that typically converts to a Base62 string of approximately 7 characters.\n\nThis method is **deterministic.** The same long URL will *always* produce the same short code.\n\nThis means:\n\n- You can detect duplicates easily.\n- Multiple servers can generate codes independently without coordination.\n\n#### **Collision Risks**\n\nHowever, **hash collisions** are possible because we truncate the hash.\n\nTwo different URLs could (rarely) produce the same short code:\n\n\n```shell\nhttps://example.com/page/123\nhttps://example.com/page/456\n```\n\n\n→ Might both hash to → `DZFbb43`\n\nEven though cryptographic hash collisions are rare, truncation reduces the available bit space, making collisions statistically inevitable at scale.\n\n#### **Collision Resolution Strategies**\n\nWhen a newly generated short code already exists in the database (detected via a UNIQUE constraint violation), we need a fallback strategy.\n\n##### **1. Re-hash with a Salt**\n\nAdd a **random salt** or nonce to the original URL and hash again: `hash = sha256(url + salt)`\n\nRepeat until a unique short code is found.\n\n##### **2. Append a Suffix**\n\nAttach a small counter or suffix to the colliding short code:\n\n\n```shell\nDZFbb43 → DZFbb43-1 → DZFbb43-2\n```\n\n\nBoth methods eliminate duplicates but come with trade-offs. \n\n**Trade-off:** Both resolution strategies negate the stateless benefit by requiring at least one database lookup, adding latency and complexity to the write path.\n\n---\n\n### **Approach 2: **Global Counter (Non-Deterministic)\n\nThis is one of the **simplest and most reliable** ways to generate short URLs.\n\nInstead of hashing, it relies on a **global, monotonically increasing counter** to ensure every short code is **unique** by design.\n\n#### How It Works\n\nThe entire system revolves around a **centralized counter service** that generates the *next available integer ID* in sequence and never repeats it.\n\n#### **1. Request a Unique ID**\n\nWhen an application server receives a request to shorten a URL, it contacts a **Counter Service** typically implemented with a fast in-memory data store like **Redis**, **etcd**, or **Zookeeper**.\n\nRedis provides the `INCR` command, which is **atomic** by nature.\n\n\n```shell\nINCR url_counter\n```\n\n\nEach time this command is called, Redis:\n\n- Locks the key temporarily.\n- Increments its value by one.\n- Returns the new value.\n- Releases the lock.\n\n**Atomicity ensures** that even under extreme concurrency, no two servers can ever get the same number.\n\n#### **2. Encode the ID**\n\nThe application server receives the unique integer ID (e.g., `123456789`) from the counter service. It then applies **Base62 encoding** to this number to create the final, compact short code.\n\n##### **Example Growth**:\n\n- ID `1,000` -> Base62 `g8`\n- ID `1,000,000` -> Base62 `4c9B`\n- ID `1,000,000,000` -> Base62 `15ftgG`\n\nEven after generating **a billion short URLs**, the code length stays under **6–7 characters**, which is extremely efficient.\n\n#### **End-to-End Example**\n\n\n[Embed: https://link.excalidraw.com/readonly/7QKESN0wPn5A4xMlbnMD](https://link.excalidraw.com/readonly/7QKESN0wPn5A4xMlbnMD)\n\n\n#### Pros\n\n- **Guaranteed Uniqueness**: Each ID is globally unique. No collision detection or retry logic needed.\n- **Simplicity and Speed: **Just one operation (`INCR`) per short URL.** **Sub-millisecond latency in Redis or etcd.\n- **Deterministic Length: **Short codes grow logarithmically with the total number of URLs.\n\n#### Cons\n\n- **Centralized Bottleneck: **Every URL creation request must pass through the counter service.Throughput is limited by the counter’s network and CPU capacity.\n- **Single Point of Failure (SPOF): **If the counter service (Redis, etc.) crashes, **no new URLs can be generated**. The read path (redirection) still works, but the write path halts.\n- **Predictability: **Since IDs are sequential, they can be easily guessed or decoded. A malicious user could increment IDs to discover private short links.\n\n#### **Addressing the Limitations**\n\nTo scale and secure this approach, modern URL shorteners extend it in two key ways.\n\n##### **Sharded Counters**\n\nInstead of one global counter, deploy **multiple counters**, each responsible for a subset of IDs. For example, 1024 counters distributed across regions or shards.\n\nEach ID combines:\n\n- A **shard ID** (10 bits → up to 1024 shards)\n- A **local counter value** (remaining bits)\n\n**Formula:** `global_id = (shard_id << 20) | local_counter`\n\nThis gives each shard up to 2²⁰ (≈1 million) IDs before wraparound.\n\n**Benefits:**\n\n- Removes the single bottleneck.\n- Enables horizontal scaling.\n- Still guarantees global uniqueness if shard IDs are unique.\n\n**Trade-off:** Slightly more complexity in managing shards and ensuring IDs don’t overlap.\n\n##### ID Obfuscation\n\nTo prevent sequential IDs from being easily decoded **shuffle bits** using a simple **Feistel cipher** or **XOR mask**.\n\nThe transformation is reversible (so you can still decode IDs if needed). This produces short codes that appear random even though they are derived from sequential IDs.\n\n\n```shell\n| Raw ID | Obfuscated ID | Base62 |\n| ------ | ------------- | ------- |\n| 1001 | 934023 | `Dgf7K` |\n| 1002 | 701293 | `xAq2B` |\n| 1003 | 442901 | `Kf2Tz` |\n```\n\n\nThis adds privacy without sacrificing performance.\n\n---\n\n### **Approach 3:** Distributed unique ID generator\n\nThis is the industry-standard solution for generating unique, non-deterministic IDs at a massive scale. It's a hybrid approach that avoids the need for a centralized counter.\n\n#### How It Works\n\nEach ID is a **64-bit integer** made up of multiple components that together guarantee uniqueness even across thousands of machines.\n\n\n```shell\n┌───────────────────────┬───────────────┬────────────┐\n│ Timestamp │ Worker ID │ Sequence │\n│ (41 bits) │ (10 bits) │ (12 bits) │\n└───────────────────────┴───────────────┴────────────┘\n```\n\n\n##### **1. Timestamp (41 bits)**\n\nThis represents the number of **milliseconds since a custom epoch** (a chosen start date, e.g., `Jan 1, 2020`).** **Using a **custom epoch** instead of the Unix epoch extends the lifetime of the system.\n\n41 bits can store `2^41` milliseconds, approximately **69.7 years** of continuous operation.\n\nSo if your epoch starts in 2025, you’ll have ID space until roughly **2094**.\n\n##### **2. Worker ID (10 bits)**\n\nEach worker (application server or service instance) gets a **unique identifier** at startup.\n\n- 10 bits → `2^10 = 1,024` unique workers per cluster.\n- Each worker can generate IDs **independently** without collisions.\n\n**Worker ID Assignment: **When a worker starts up, it connects to a coordination service like **ZooKeeper** or **etcd**. It registers itself and requests a unique worker ID, which it holds for its lifetime or for a set \"lease\" period. This startup coordination is vital to prevent two workers from accidentally using the same ID.\n\n##### **3. Sequence Number (12 bits)**\n\nThis is a local, in-memory counter that tracks how many IDs the worker has generated within the **same millisecond**.\n\n- 12 bits → `2^12 = 4,096` IDs per millisecond per worker.\n- That’s **4.09 million IDs per second per worker** at full speed!\n\nIf a worker hits 4,096 requests within one millisecond, it must **wait** for the clock to tick to the next millisecond before continuing.\n\n#### Pros:\n\n- **Highly Scalable and Available: **ID generation is completely decentralized. If you need more write throughput, you simply add more application servers (workers). The failure of one worker has zero impact on the ability of other workers to continue generating IDs.\n- **Time-Ordered (K-Sortable): **IDs are roughly monotonically increasing. When these IDs are used as primary keys, new records are inserted near the end of the index. This is extremely efficient for writes and allows for highly effective time-based range queries (e.g., \"get all links created yesterday\").\n- **Ultra-Low Latency: **IDs are generated in-memory with **no network hops**.\n\n#### Cons:\n\n- **Clock Synchronization Required: **If a worker’s clock drifts backward (e.g., NTP sync issue), it might generate **duplicate timestamps**, breaking uniqueness.\n- **Infrastructure Overhead: **The system requires** a** **reliable coordination service** (e.g., ZooKeeper or etcd) to assign unique Worker IDs and s**trict time synchronization** across all servers using NTP or cloud time services.\n\n---\n\n### Summary and Recommendation\n\n\n| Strategy | Pros | Cons | Best For |\n| --- | --- | --- | --- |\n| **Hashing** | Deterministic, stateless generation. | Inevitable collisions require complex resolution. | Services where deduplicating identical URLs is a key feature. |\n| **Global Counter** | Guaranteed uniqueness, simple logic. | Central bottleneck, predictable IDs. | Small to medium-sized applications with moderate traffic. |\n| **Distributed ID** | Highly scalable, k-sortable, high throughput. | Complex to implement, sensitive to clock skew. | Large-scale, distributed systems requiring high availability and performance. |\n\n\n---\n\n## **6.2 Fast URL Redirections**\n\nThe **redirection service** is the most **performance-critical component** of a URL shortener.\n\nEvery time a user clicks a short link, this service must:\n\n1. **Resolve** the short code into the original long URL.\n2. **Redirect** the user as fast as possible.\n\nEven tiny delays (just a few milliseconds) can degrade user experience at scale, especially when serving **billions of redirects per day**.\n\n### **Choosing the Right Redirect Code**\n\nBefore optimizing performance, we must decide how to perform the redirect. \n\nThe choice between **301**, **302**, and **307** affects both **speed** and **control**.\n\n\n> **TIP**\n>\n> #### 301 vs. 302 Redirects\n>\n> ##### 301 (Moved Permanently)\n>\n> A `301` redirect tells browsers to **permanently caches** the redirect. Future clicks on the same short link will go directly to the long URL without contacting your service again.\n>\n> **Pros: Fastest for the end-user** after the first visit. Reduces load on your service significantly.\n>\n> **Cons:** You **lose all control and analytics**. You can no longer update the destination URL or count subsequent clicks, as the browser bypasses you completely.\n>\n> **Best for:** Links that should never change (e.g., permanent marketing URLs).\n>\n> ##### 302/307 (Temporary Redirect)\n>\n> A `302 Found` or `307 Temporary Redirect` tells the browser that the destination **might change** in the future. The browser **contacts your service** on every click to resolve the short code.\n>\n> **Pros: **Accurate **click tracking** and **analytics**.** **You can **update** or **expire** short links anytime.\n>\n> **Cons: **Slightly higher latency (each request hits your service).** **Adds read load to your infrastructure.\n>\n> ##### Recommendation\n>\n> Use **302** by default. It provides flexibility, analytics, and updatability, critical for any modern URL shortener.\n\n\n### The Read Path\n\nTo achieve low latency globally, we design a \"waterfall\" lookup path. The system tries to find the long URL in the fastest, closest cache available. It only proceeds to the next, slower layer on a cache miss.\n\n#### **Layer 1: Browser Cache**\n\nIf a **301 redirect** was previously issued, the browser already knows the final URL. The request **never reaches your servers,** the user is instantly redirected.\n\n#### **Layer 2: CDN / Edge Cache**\n\nFor global services, a **Content Delivery Network (CDN)** is essential. CDNs like **Cloudflare**, **Akamai**, or **Fastly** maintain edge servers near users worldwide.\n\n**Cache Hit: **The CDN instantly serves the cached `302` response with the long URL (≈10–50 ms latency).\n\n**Cache Miss: **The CDN forwards the request to your **origin server**.\n\n#### **Layer 3: In-Memory Cache (Redis/Memcached)**\n\nAt your application layer, the first lookup happens in a **distributed in-memory cache**.\n\n- **Cache Key:** The short code (e.g., `xyz`).\n- **Cache Value:** The long URL.\n\n**Cache Hit: **The application server immediately returns** **the long URL. The CDN then **caches this response** for future users (cache-aside pattern).\n\n**Cache Miss: **If not found in Redis, the application proceeds to the final layer, the database.\n\n#### **Layer 4: Database (Source of Truth)**\n\nThe database holds the **authoritative mapping** of short codes to long URLs. Since lookups are simple key-value reads, **NoSQL stores** like **DynamoDB**, **Cassandra**, or **ScyllaDB** are ideal.\n\n**Query Example:**\n\n\n```sql\nSELECT long_url FROM url_mapping WHERE short_code = 'xyz';\n```\n\n\nOnce retrieved:\n\n1. The app **writes the result to Redis** (with a TTL, e.g., 24 hours).\n2. The next lookup will hit Redis instead of the database.\n3. The app returns the `302` response to the CDN, which caches it.\n\n---\n\n## 6.3 Supporting Custom Aliases\n\nCustom aliases allow users to create human-readable short codes instead of system-generated ones.\n\n**For example:**\n\n\n```shell\nshort.com/summer-sale ✅ user-defined\nshort.com/aB7xY2 ⚙️ system-generated\n```\n\n\nThis feature is especially valuable for **marketing campaigns**, **social media sharing**, and **brand consistency**, where memorability and aesthetics matter.\n\nHowever, supporting custom aliases introduces challenges around **validation**, **uniqueness**, and **race conditions** that must be carefully handled to maintain system integrity.\n\n#### **1. API Design**\n\nThe API for link creation should accept an optional `custom_alias` parameter along with the long URL.\n\n\n```json\n{\n \"long_url\": \"https://www.my-ecommerce-store.com/products/summer-collection-2025\",\n \"custom_alias\": \"summer-sale\",\n \"expires_at\": \"2025-09-01T23:59:59Z\"\n}\n```\n\n\nIf the `custom_alias` field is not provided, the service falls back to **auto-generating** a short code using the ID generation algorithm.\n\n#### **2. Rigorous Validation**\n\nBefore creating a custom alias, the system must validate it against strict rules to prevent conflicts, misuse, or routing errors.\n\n- **Character Set**: The alias must only contain URL-safe characters. A regular expression like `^[a-zA-Z0-9_-]+$` is typically used to enforce this.\n- **Length Limits**: Enforce minimum and maximum lengths (e.g., 3-50 characters) to prevent abuse and maintain usability.\n- **Reserved Words**: The system must check the alias against a blocklist of reserved words. This list should include application routes (`/api`, `/admin`, `/login`), common terms (`/help`, `/contact`), and any potentially offensive words. This prevents users from hijacking critical application paths.\n\nAll checks should occur **before** any database operation to minimize load on backend systems.\n\n#### **3. **Ensuring Uniqueness and Handling Race Conditions\n\nThis is the most **critical** aspect of custom alias creation.\n\n##### **The Race Condition Problem**\n\nTwo users could try to claim the same custom alias (`summer-sale`) at the exact same moment.\n\n1. User A's request checks if `summer-sale` exists. (It doesn't).\n2. User B's request checks if `summer-sale` exists. (It still doesn't).\n3. User A's request inserts the record. (Success).\n4. User B's request tries to insert the record. (This will either fail or create a duplicate, depending on the database schema).\n\nWithout proper safeguards, both requests might initially think the alias is free leading to duplicate entries or inconsistent state.\n\n##### The Reliable Solution\n\nInstead of relying on application logic, use the **database itself** as the source of truth by defining a **UNIQUE constraint** on the alias column.\n\n**Schema Example:**\n\n\n```sql\nCREATE TABLE url_mapping (\n short_code VARCHAR(10) PRIMARY KEY,\n alias VARCHAR(50) UNIQUE,\n long_url TEXT NOT NULL,\n created_at TIMESTAMP DEFAULT CURRENT_TIMESTAMP\n);\n```\n\n\n---\n\n## 6.4 Supporting Link Expiration\n\nLink expiration is essential for maintaining both **security** and **data hygiene**.\n\nIt is commonly used in:\n\n- **Time-sensitive campaigns**, such as marketing or event promotions.\n- **Security-critical use cases**, like password reset or invitation links.\n- **System maintenance**, to prevent indefinite data growth.\n\nWithout proper expiration handling, a URL shortener’s database could grow endlessly, degrading performance and increasing storage costs.\n\nThere are two primary ways to handle expired links: **Active Deletion** and **Passive Expiration.**\n\n### 1. Active Deletion (Background Job)\n\nIn this model, a **scheduled worker process** periodically scans the database for expired links and deletes them.\n\n**Example:**\n\n\n```sql\nDELETE FROM links WHERE expires_at < NOW();\n```\n\n\nTypically, this runs every hour or day using a background job scheduler such as **Cron**, **Celery**, or **Airflow**.\n\n#### **Pros**\n\n- **Keeps the database clean:** Old records are removed regularly, reducing storage costs.\n- **Improves performance over time:** Fewer stale entries mean faster queries.\n\n#### **Cons**\n\n- **Resource-intensive:** Scanning large tables frequently can burden the database, especially at scale.\n- **Not real-time:** A link might stay active for minutes or hours after expiration until the job executes.\n- **Operational overhead:** Requires maintaining a reliable, scalable background worker infrastructure.\n\n### 2. Passive Expiration (Real-Time Check)\n\nIn this approach, the link is never physically deleted when it expires.\n\nInstead, the **application layer** checks the expiration timestamp during the redirect lookup.\n\n**Logic:**\n\n\n```python\nif link.expires_at < current_time:\n return \"Link expired\"\nelse:\n redirect_to(link.long_url)\n```\n\n\n#### **Pros**\n\n- **Real-time precision:** The link becomes inactive exactly at the expiration moment.\n- **Low overhead:** A simple timestamp comparison adds negligible latency.\n- **Simple to implement:** No additional background processes are required.\n\n#### **Cons**\n\n- **Data retention:** Expired links remain in the database indefinitely, consuming storage.\n- **Potential analytics noise:** Expired links still appear in historical datasets unless filtered.\n\n### 3. Recommended Hybrid Approach\n\nA **hybrid strategy** combines the precision of passive expiration with the efficiency of occasional cleanup.\n\n##### **Step 1: Passive Expiration for Read Path**\n\n- Every redirect request performs a real-time expiration check.\n- Users experience instant and accurate expiration behavior.\n\n##### **Step 2: Lazy Cleanup for Data Hygiene**\n\n- Run a **low-frequency background job** (weekly or monthly) to delete or archive long-expired links.\n- This prevents unbounded growth without adding continuous load to the database.\n\n### 4. Caching and Expiration Consistency\n\nA crucial design consideration is ensuring **all cache layers respect link expiration**.\n\nIf not handled carefully, caches might continue serving redirects **after** the link has expired.\n\n##### **Problem Example**\n\n- A link expires in **5 minutes (300 seconds)**.\n- The CDN or Redis cache entry is set with **TTL = 24 hours**.\n- Even after the link expires, cached redirects will still be served, violating user expectations and potentially creating security risks.\n\n##### Solution\n\nWhen writing to any cache, set the **cache TTL to the smaller of**:\n\n`TTL_cache = min(link.remaining_lifetime, default_cache_ttl)`\n\nThis ensures **cache TTLs align with link lifetimes** to prevent expired redirects from being served.\n\n---\n\n## 6.5 Analytics – Click Count\n\nA modern URL shortening system is not complete without **analytics**. The most fundamental metric is **click count** — the number of times each shortened link is accessed.\n\nThis data powers insights such as:\n\n- How many people clicked a link.\n- Which campaigns perform best.\n- Where and when traffic originates.\n\nHowever, counting clicks accurately at scale introduces challenges related to **performance**, **consistency**, and **real-time aggregation**.\n\n### What Is a \"Click\"?\n\nA **click** is registered whenever a user follows a shortened link that results in a **successful redirect** to the target URL.\n\nTo prevent double counting, certain conditions are typically applied:\n\n- Only **HTTP 302/301** redirects count.\n- Requests resulting in **expired**, **invalid**, or **bot traffic** are excluded.\n- Repeated requests from the same user within a short time window may be ignored.\n\n### Click Logging Flow\n\nWhen a user clicks a short link, two things happen simultaneously:\n\n1. The user must be redirected **instantly** (performance-critical).\n2. The system must **record the click** for analytics (accuracy-critical).\n\nTo avoid slowing down the redirect path, these actions are separated into **synchronous** and **asynchronous** operations.\n\nThis **decoupled design** ensures the redirect latency remains low while analytics are processed asynchronously.\n\n### Design Approaches\n\n#### **Approach 1: Direct Increment (Simple, Suitable for Low Scale)**\n\nEach redirect increments a counter directly in the database or cache.\n\n\n```sql\nUPDATE links SET click_count = click_count + 1 WHERE short_code = 'abc123';\n```\n\n\n**Pros**\n\n- Simple and easy to implement.\n- Click counts are always up to date.\n\n**Cons**\n\n- Write-heavy. Each redirect triggers a DB write.\n- Causes row-level contention under high concurrency.\n\n#### **Approach 2: Buffered Counting (Recommended for Scale)**\n\nFor high-traffic systems, direct increments are inefficient. Instead, **accumulate clicks in memory or a fast cache** and **flush** them periodically to the database.\n\n**Workflow**\n\n1. When a user clicks a link, increment a counter in Redis:\n\n\n```shell\nINCR link:abc123:clicks\n```\n\n\n2. A background job periodically aggregates and updates the persistent store:\n\n\n```sql\nUPDATE links \nSET click_count = click_count + redis_count\nWHERE link_id = abc123;\n```\n\n\n3. Reset the Redis counter after flushing.\n\n**Pros**\n\n- Significantly reduces database writes.\n- Handles high concurrency efficiently.\n- Redis operations are atomic and fast.\n\n**Cons**\n\n- Counts in the UI may lag slightly behind real time (depending on flush interval).\n\n#### **Approach 3: Event Streaming (For Real-Time Analytics)**\n\nLarge-scale systems such as Bitly or Google Analytics use **event-driven pipelines**.\n\nEach click generates an **event** that flows through systems like:\n\n\n```mermaid\nflowchart LR\n A[Redirect Service]:::primary --> B[Kafka]:::orange\n B --> C[Flink]:::secondary\n C --> D[ClickHouse]:::purple\n D --> E[Analytics Dashboard]:::rose\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef secondary fill:#38d9a9,stroke:#000,color:#000\n classDef purple fill:#9775fa,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef rose fill:#f783ac,stroke:#000,color:#000\n```\n\n\n- **Kafka / Kinesis** → message ingestion\n- **Flink / Spark Streaming** → aggregation\n- **Cassandra / Druid / ClickHouse** → analytics storage\n\nThis enables real-time dashboards and flexible queries across billions of clicks.\n\n**Pros**\n\n- Real-time analytics and flexible aggregation (by country, device, time).\n- Scales horizontally to billions of events.\n\n**Cons**\n\n- Higher operational complexity and cost.\n- Requires managing streaming infrastructure.\n\n---\n\n## 6.6 Handling High Availability\n\nThe redirect service is critical. Here's how to ensure 99.99% availability.\n\n### Multi-Region Deployment\n\nDeploy services in multiple geographic regions:\n\n- **Primary region:** Handles all writes.\n- **Read replicas:** Each region has read replicas of the database.\n- **DNS routing:** Route users to the nearest region using latency-based DNS.\n\n### Database Replication\n\nFor DynamoDB:\n\n- Enable Global Tables for automatic multi-region replication.\n- Writes in any region propagate to all regions within seconds.\n\nFor Cassandra:\n\n- Configure replication factor of 3.\n- Use `LOCAL_QUORUM` for reads to ensure consistency within a region.\n\n### Graceful Degradation\n\nIf the database is unreachable:\n\n1. Serve from cache (read path continues working).\n2. Queue writes for retry (write path degrades gracefully).\n3. Return cached stale data rather than errors.\n\n---\n\n# Summary\n\nDesigning a URL shortener teaches fundamental distributed systems concepts:\n\n\n| Topic | Key Takeaway |\n|-------|-------------|\n| **ID Generation** | Trade-off between simplicity (counter) and scalability (Snowflake) |\n| **Caching** | Essential for read-heavy workloads, cache-aside pattern |\n| **Database Choice** | NoSQL for simple key-value access patterns at scale |\n| **Expiration** | Hybrid approach: passive check + active cleanup |\n| **Analytics** | Decouple from critical path using buffered counting |\n| **Availability** | Multi-region deployment, replication, graceful degradation |\n\n\nThe key insight is that this system is read-heavy (100:1 ratio), so optimize aggressively for the read path while keeping writes simple and reliable.\n\n---\n\n# References\n\n- [Twitter Snowflake](undefined) - Original announcement of Twitter's distributed ID generation\n- [Base62 Encoding](undefined) - Understanding URL-safe encoding schemes\n- [DynamoDB Best Practices](undefined) - AWS guide for NoSQL database design\n- [Redis as a Cache](undefined) - Official Redis documentation on caching patterns\n\n---\n\n# Quiz","pageType":"system-design-interviews"}

Design URL Shortener

Ashish Pratap Singh

Get Premium