{"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>\n> An url shortener makes links easier to share on social media, track for analytics, and remember.\n>\n> **Popular Examples:** [**tinyurl.com**](https://tinyurl.com/)**,** [**bitly.com**](https://bitly.com/)\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\n### Functional Requirements\n\n1. **Shorten URL:** Given a long URL, generate a unique short URL.\n2. **Redirect:** When a short URL is accessed, redirect the user to the original long URL.\n3. **Custom Aliases:** Allow users to create custom short codes (if available).\n4. **Expiration:** Support link expiration with default and custom TTLs.\n5. **Analytics:** Track basic click counts for each short URL.\n\n### Non-Functional Requirements\n\n1. **High Availability:** The system must be highly available (e.g., 99.99%).\n2. **Low Latency:** Redirect requests must complete in under 50ms (p99).\n3. **Uniqueness:** Each short code maps to exactly one long URL, and short codes never collide.\n4. **Scalability:** Should handle a large number of read and write requests (100:1 read-to-write ratio).\n5. **Durability:** Once a short URL is created, the mapping must not be lost.\n\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 \"expires_at\": \"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- **expires_at** *(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 \"expires_at\": \"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- **expires_at**: 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 302 Found\nLocation: https://www.example.com/some/very/long/url\n```\n\n\n- `302 Found`: Default. The browser contacts the service on every click, which preserves click tracking and lets us update or expire links.\n- `301 Moved Permanently`: Optional, for links that never change. It is faster on repeat visits, but the browser caches the destination and stops contacting the service, so click tracking is lost.\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\nFour components work together to serve both write and read traffic. The diagram maps out how they connect, with the load balancer routing URL creation requests to the write path and redirect requests to the read path:\n\n\n```mermaid\nflowchart TD\n C[Client]:::primary\n LB[Load Balancer]:::green\n\n UGS([URL Generation
Service]):::orange\n RS([Redirection
Service]):::orange\n DB[(Database)]:::teal\n\n C --> LB\n LB -->|Write| UGS\n LB -->|Read| RS\n UGS --> DB\n RS --> DB\n\n classDef primary fill:#00ceff,stroke:#000,color:#000\n classDef green fill:#69db7c,stroke:#000,color:#000\n classDef orange fill:#ffa94d,stroke:#000,color:#000\n classDef teal fill:#38d9a9,stroke:#000,color:#000\n```\n\n\n### 1. Clients\n\nClients are end-users or applications interacting with the system through web browsers, mobile apps, or third-party integrations. They call `POST /shorten` to generate short URLs and `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 distributes incoming traffic across them. If a server fails, it reroutes traffic to healthy instances, which keeps the system available and fault tolerant. It can also handle SSL termination and basic request filtering such as rate limiting.\n\n### 3. URL Generation Service\n\nThis service handles all **write operations**. It validates incoming URLs, generates a unique short code, handles any **custom alias** the user provides, and stores metadata such as the expiry date, creation time, and user ID. Since 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**, so it must be fast, stateless, and horizontally scalable.\n\nFor a given short code, it looks up the original long URL, checks that the link is still valid (not expired or deleted), and issues an HTTP **301 (permanent)** or **302 (temporary)** redirect based on the system’s policy. It also caches frequently accessed mappings to minimize database hits.\n\n### 5. Database\n\nThe database stores the mapping between **short codes and long URLs**, along with relevant metadata. It must support high read throughput to sustain redirection traffic and durable writes so that links are never lost.\n\n### Flow: Creating a Short URL\n\nThe sequence below traces a single shorten request from the client through the load balancer, the write service, and finally into the database:\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, and since reads dominate (1 billion per day), it must be heavily optimized. For each request it looks up the long URL for the given short code, checks whether the link has expired, and returns an HTTP redirect response.\n\n#### Cache Layer (Redis)\n\nTo achieve sub-50ms latency at 35,000 QPS, we need a distributed cache. It stores frequently accessed URL mappings, which reduces database load for popular links and provides sub-millisecond lookup times.\n\n### Flow: Redirecting to Original URL\n\nBecause redirects dominate at 100:1, the read path checks Redis first and only falls back to the database on a miss. The sequence below shows both the cache-hit and cache-miss branches, ending in an HTTP 302 redirect to the 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 produce codes that are **unique** (no collisions between different URLs), **compact** (small enough to keep the short link truly \"short\"), **efficient** (generated quickly without bottlenecks), and **scalable** (working 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: [`https://example.com/`](https://example.com/)\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: 06d68bdbae12cb1837095f97771be94c\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, since `62^8 < 2^48 < 62^9`.\n>\n> Even a 7-character code spans `62^7` ≈ **3.5 trillion** combinations, 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: [`https://example.com/courses/system-design`](https://example.com/courses/system-design)\n2. Generate an MD5 hash of the long URL. MD5 produces a 128-bit hash, typically a 32-character hexadecimal string: `06d68bdbae12cb1837095f97771be94c`\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: `06d68bdbae12`\n4. Convert these bytes to decimal: `06d68bdbae12` (hexadecimal) → `7,518,539,197,970` (decimal)\n5. Encode the result into a Base62 encoded string: `28MoyG9a`\n\nThe specific choice of 6 bytes (48 bits) is important because it produces a decimal number that converts to a Base62 string of approximately 8 characters.\n\nThis method is **deterministic.** The same long URL will *always* produce the same short code. That makes duplicates easy to detect, and it lets multiple servers 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 → `28MoyG9a`\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 conditional write that fails if the key is already present, or a UNIQUE constraint violation in a relational store), 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\n28MoyG9a → 28MoyG9a-1 → 28MoyG9a-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 locks the key, increments its value by one, returns the new value, and releases the lock. This atomicity ensures that even under heavy concurrency, no two servers 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\nPutting the steps together, the sequence below shows a client submitting a long URL, the application server calling Redis INCR to get a unique integer, encoding it to Base62, and persisting the mapping before returning the finished short URL:\n\n\n```mermaid\nsequenceDiagram\n autonumber\n participant C as Client\n participant AS as Application Server\n participant RC as Redis Counter Service\n participant DB as URL Mapping DB\n\n C->>AS: POST /shorten (long URL)\n AS->>RC: INCR url_counter\n RC-->>AS: 123456789\n AS->>AS: Base62(123456789) = \"15ftgG\"\n AS->>DB: INSERT { short_code: \"15ftgG\", long_url: \"https://example.com/...\" }\n AS-->>C: https://sho.rt/15ftgG\n```\n\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\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 64-bit ID combines a **shard ID** in the top 10 bits (up to 1024 shards) with a **local counter value** in the remaining 54 bits.\n\n**Formula:** `global_id = (shard_id << 54) | local_counter`\n\nThis gives each shard up to 2⁵⁴ (≈18 quadrillion) IDs, far more than the system will ever need, so wraparound is not a concern.\n\nThis removes the single bottleneck and enables horizontal scaling, while still guaranteeing global uniqueness as long as 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\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\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 (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**, keyed by the short code (e.g., `xyz`) with the long URL as the value.\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 a separate \"check, then write\" in application code, push the uniqueness guarantee down to the storage layer with a single **atomic conditional write** that only succeeds if the key does not already exist.\n\nThe custom alias occupies the **same key space** as generated short codes (it is stored as the `short_code`), so a redirect resolves both kinds of code the same way.\n\nThe exact primitive depends on the store:\n\n- **DynamoDB:** `PutItem` with a condition expression `attribute_not_exists(short_code)`.\n- **Cassandra:** `INSERT ... IF NOT EXISTS`, a lightweight transaction.\n- **Relational store:** a `PRIMARY KEY` or `UNIQUE` constraint on the short code, with the insert rejected on violation.\n\n**Example (DynamoDB conditional write):**\n\n\n```python\n# Only succeeds if the short code (alias) is not already taken\ntable.put_item(\n Item={\n \"short_code\": \"summer-sale\",\n \"long_url\": \"https://www.my-ecommerce-store.com/products/summer-collection-2025\",\n \"is_custom\": True,\n },\n ConditionExpression=\"attribute_not_exists(short_code)\",\n)\n```\n\n\nIf the conditional write fails because the key is taken, the service returns `409 Conflict` for a custom alias, or generates a new code and retries for an auto-generated one.\n\n---\n\n## 6.4 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 across multiple geographic regions. A primary region handles all writes, each region keeps read replicas of the database, and latency-based DNS routes users to the nearest region.\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# 7. Follow-ups\n\nWith the core design complete, two common extensions remain: expiring links and counting clicks.\n\n## 7.1 Supporting Link Expiration\n\nLink expiration is essential for maintaining both **security** and **data hygiene**.\n\nIt is common in time-sensitive campaigns such as marketing or event promotions, security-critical links like password resets or invitations, and routine 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 url_mappings 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\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\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\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\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\nEvery redirect request performs a real-time expiration check, so users experience instant and accurate expiration behavior.\n\n##### Step 2: Lazy Cleanup for Data Hygiene\n\nA **low-frequency background job** (weekly or monthly) deletes or archives long-expired links. 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\nSuppose a link expires in **5 minutes (300 seconds)**, but its CDN or Redis cache entry is set with a **TTL of 24 hours**. Even after the link expires, cached redirects keep getting served, which violates user expectations and can create 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## 7.2 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 how many people clicked a link, which campaigns perform best, and 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, a few conditions are typically applied: only **HTTP 302/301** redirects count, requests that result in **expired**, **invalid**, or **bot traffic** are excluded, and 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 url_mappings SET click_count = click_count + 1 WHERE short_code = 'abc123';\n```\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\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\n1. A background job periodically aggregates and updates the persistent store:\n\n\n```sql\nUPDATE url_mappings\nSET click_count = click_count + :redis_count\nWHERE short_code = 'abc123';\n```\n\n\n1. Reset the Redis counter after flushing.\n\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\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]:::teal\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 teal fill:#38d9a9,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\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\n# Quiz","pageType":"system-design-interviews"}

Get Premium