Free lesson · System Design Interviews

Step 5: Database Design

Hard9 min readsystem-designinterview-prep

This is where you show the interviewer you've thought beyond boxes and arrows. The database schema, the indexing strategy, and the short code generation algorithm are where the real engineering happens in a URL shortener. These are the decisions that determine whether the system works at scale or falls apart under load.

Let me walk through each decision the way I'd discuss it in an interview - starting with the schema, then the short code generation (which is the single most interesting design challenge in this system), and finally the sharding strategy for when a single database isn't enough.

The Schema

CREATE TABLE url_mappings (
    id              BIGSERIAL PRIMARY KEY,
    short_code      VARCHAR(20) NOT NULL UNIQUE,
    long_url        TEXT NOT NULL,
    created_at      TIMESTAMP NOT NULL DEFAULT NOW(),
    expires_at      TIMESTAMP NOT NULL,
    click_count     BIGINT NOT NULL DEFAULT 0,
    creator_ip      INET,
    
    -- Indexes
    INDEX idx_short_code (short_code),    -- Primary lookup for redirects
    INDEX idx_expires_at (expires_at)     -- For cleanup job
);

Why These Columns

Why short_code Is NOT the Primary Key

You might wonder: why not use short_code as the primary key instead of a separate id column?

Integer primary keys produce smaller, faster B-tree indexes. The short_code UNIQUE constraint creates a separate index that handles lookups. At 55 TB over 5 years, index efficiency matters.

Tip: Mention this in interviews if the interviewer asks about schema choices. "I'm using an integer primary key instead of the short code because integer B-tree indexes are more compact and faster than variable-length string indexes. The short_code column has its own UNIQUE index for the lookup path. At our scale of billions of rows, the index efficiency difference is measurable."

Short Code Generation - The Core Design Challenge

This is the question within the question. How do you generate 7-character codes that are unique, unpredictable (for auto-generated codes), and fast to generate at 1,000 per second?

There are three main approaches. Each has different trade-offs.

Approach 1: Hash + Truncate

Hash the long URL (or the long URL + a salt/timestamp) and take the first 7 characters as the short code.

import hashlib
import base64

def generate_short_code_hash(long_url):
    # Hash the URL with a salt for uniqueness
    salt = str(time.time()) + str(random.random())
    hash_input = long_url + salt
    
    # MD5 produces 128 bits → Base64 encode → take first 7 chars
    hash_bytes = hashlib.md5(hash_input.encode()).digest()
    base64_str = base64.urlsafe_b64encode(hash_bytes).decode()
    
    # Replace non-URL-safe characters
    short_code = base64_str[:7].replace('+', 'a').replace('/', 'b')
    
    return short_code

Collision handling: Even with 3.5 trillion possible codes and only 182 billion URLs over 5 years (5% utilization), hash collisions are possible because hash functions don't distribute evenly into 7-character truncations. You must check the database for collisions and retry if one occurs.

def create_url_with_hash(long_url):
    for attempt in range(5):  # Max 5 collision retries
        short_code = generate_short_code_hash(long_url)
        try:
            db.execute(
                "INSERT INTO url_mappings (short_code, long_url, expires_at) "
                "VALUES (%s, %s, NOW() + INTERVAL '5 years')",
                short_code, long_url
            )
            return short_code  # Success - no collision
        except UniqueViolation:
            continue  # Collision - retry with different salt
    
    raise Exception("Failed to generate unique code after 5 attempts")

flowchart TD
    URL["Long URL + salt"] --> HASH["MD5/SHA256 hash"]
    HASH --> TRUNCATE["Take first 7 chars<br/>(Base62 encoded)"]
    TRUNCATE --> CHECK{"Exists in DB?"}
    CHECK -->|"No"| INSERT["Insert into DB ✓"]
    CHECK -->|"Yes (collision)"| RETRY["New salt, retry"]
    RETRY --> HASH

Hash and truncate approach. The long URL plus a random salt is hashed using MD5 or SHA-256. The hash is Base62 encoded and truncated to 7 characters. The resulting code is checked against the database for uniqueness. If it's unique, it's inserted. If there's a collision, a new salt is generated and the process retries. At 5 percent code space utilization, collisions are rare but must be handled.

Approach 2: Counter + Base62 Conversion

Use a global auto-incrementing counter. Convert the counter value to Base62 to get the short code.

def int_to_base62(num):
    """Convert an integer to a Base62 string."""
    chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
    if num == 0:
        return chars[0]
    
    result = []
    while num > 0:
        result.append(chars[num % 62])
        num //= 62
    
    return ''.join(reversed(result))

# Counter: 1 → "1"
# Counter: 100000 → "q0U"  
# Counter: 1000000000 → "15FTGg"
# Counter: 10000000000 → "aUKYOz"

Where does the counter live? Options:

The pre-allocated range approach is the best for interviews:

flowchart TB
    subgraph RANGE_SERVER["Range Allocation Service"]
        COUNTER["Global counter<br/>(in database or ZooKeeper)"]
    end
    
    subgraph SERVER1["Write Server 1"]
        R1["Local range: 1,000,000 - 1,999,999<br/>Next: 1,000,042"]
    end
    
    subgraph SERVER2["Write Server 2"]
        R2["Local range: 2,000,000 - 2,999,999<br/>Next: 2,000,017"]
    end
    
    subgraph SERVER3["Write Server 3"]
        R3["Local range: 3,000,000 - 3,999,999<br/>Next: 3,000,103"]
    end
    
    COUNTER -->|"Allocate range<br/>of 1 million"| SERVER1
    COUNTER -->|"Allocate range<br/>of 1 million"| SERVER2
    COUNTER -->|"Allocate range<br/>of 1 million"| SERVER3

Pre-allocated counter ranges. A central range allocation service manages a global counter. Each write server requests a range of 1 million counter values. Server 1 gets the range 1 million to 1,999,999. Server 2 gets 2 million to 2,999,999. Server 3 gets 3 million to 3,999,999. Each server increments its local counter without any coordination - no database call, no lock, no network request per URL creation. When a server exhausts its range, it requests a new one. If a server crashes, the unused portion of its range is wasted - but that's a tiny fraction of the 3.5 trillion code space.

Why this works: Each server increments its local counter with zero coordination. No database call per URL creation. No distributed lock. The only coordination is when a server needs a new range (every 1 million URLs - roughly every 16 minutes at 1,000 QPS).

Interview: What to say: "For code generation, I'd use pre-allocated counter ranges. A central service assigns each write server a block of 1 million counter values. Each server increments its local counter and converts to Base62 - this is a pure in-memory operation with zero coordination. When the range is exhausted, the server requests a new block. The trade-off is that if a server crashes, the unused portion of its range is wasted - but losing a few thousand codes out of 3.5 trillion is insignificant."

Approach 3: Random Generation

Simply generate a random 7-character Base62 string and check for uniqueness.

import random
import string

def generate_random_code():
    chars = string.ascii_letters + string.digits  # a-z, A-Z, 0-9
    return ''.join(random.choices(chars, k=7))

This is the simplest approach but requires a database uniqueness check for every creation. At 5% code space utilization, collision probability per attempt is ~5% - so roughly 1 in 20 attempts collides and needs retry. At higher utilization, collisions become more frequent.

Comparison of All Three Approaches

Warning: Counter-based codes are sequential and guessable. If code a3Xb9k exists, an attacker can guess that a3Xb9l (the next counter value in Base62) also exists. This enables enumeration attacks - an attacker can scan through codes and discover all URLs. Mitigate by shuffling the counter bits or by adding a random component after the Base62 conversion. Mention this security concern in your interview.

Handling Custom Short Codes

When a user requests a custom code like my-brand, the flow is different:

def create_custom_url(long_url, custom_code):
    # 1. Validate the custom code
    if len(custom_code) < 3 or len(custom_code) > 20:
        raise ValidationError("Code must be 3-20 characters")
    if not re.match(r'^[a-zA-Z0-9-]+

    
    
  

, custom_code):
        raise ValidationError("Only alphanumeric characters and hyphens")
    if custom_code in RESERVED_WORDS:
        raise ValidationError("This code is reserved")
    
    # 2. Check uniqueness and insert atomically
    try:
        db.execute(
            "INSERT INTO url_mappings (short_code, long_url, expires_at) "
            "VALUES (%s, %s, NOW() + INTERVAL '5 years')",
            custom_code, long_url
        )
        return custom_code
    except UniqueViolation:
        raise ConflictError("This short code is already taken")

The UNIQUE constraint on short_code handles both auto-generated and custom codes - they share the same namespace. No additional logic needed.

Sharding Strategy (For Year 2+)

When the database exceeds ~10 TB (roughly year 2), you'll need to shard. The question is: what's the shard key?

short_code is the right shard key. The dominant operation (redirect) uses short_code as the lookup key. Sharding by short_code ensures every redirect query hits exactly one shard - no scatter-gather, no cross-shard joins. This optimizes the 100:1 read-heavy workload.

-- Conceptual sharding by short_code
-- Shard = hash(short_code) % num_shards

Shard 0: short_codes where hash(code) % 4 == 0
Shard 1: short_codes where hash(code) % 4 == 1
Shard 2: short_codes where hash(code) % 4 == 2
Shard 3: short_codes where hash(code) % 4 == 3

URL Expiration and Cleanup

URLs have an expires_at timestamp. Two mechanisms handle expired URLs:

Lazy deletion (on read): When a redirect request comes in, check if expires_at < NOW(). If expired, return 404 and optionally delete the row. This is free - the check happens during the normal lookup.

Background cleanup job: A periodic job (daily) scans for and deletes expired URLs to reclaim storage.

-- Background cleanup: delete URLs expired more than 7 days ago
-- (7-day grace period in case of clock skew or user timezone confusion)
DELETE FROM url_mappings 
WHERE expires_at < NOW() - INTERVAL '7 days'
LIMIT 100000;  -- Batch delete to avoid long-running transactions

Key Takeaways

1. Use an integer primary key, not short_code. Integer B-tree indexes are smaller and faster than variable-length string indexes. At billions of rows, this efficiency matters.

2. Pre-allocated counter ranges are the best code generation strategy for interviews. Zero coordination per creation, guaranteed uniqueness, simple to explain. Mention the predictability concern and how to mitigate it.

3. Hash + truncate is the simplest correct approach but requires collision handling. Good for simpler systems. The collision check adds a database round-trip per creation.

4. Shard by short_code because redirects are the dominant operation. 100:1 read-heavy means you optimize the read path. short_code as shard key means every redirect hits exactly one shard.

5. Custom codes share the same namespace as auto-generated codes. The UNIQUE constraint on short_code handles both. No separate table or lookup needed.

6. Expire URLs with lazy deletion + background cleanup. Lazy deletion catches expired URLs at read time for free. Background cleanup reclaims storage for URLs nobody is requesting anymore.

Exercise: Exercise 1: Implement the pre-allocated counter range approach in pseudocode. Include: the range allocation service that maintains the global counter, the write server that requests and uses ranges, and the recovery logic when a write server crashes mid-range. How do you prevent two servers from getting the same range? (Hint: atomic compare-and-swap on the counter.)

Exercise 2: The interviewer says: "I'm worried about sequential codes being guessable. How do you make them unpredictable while still using the counter approach?" Design a solution that scrambles the counter value into a non-sequential short code. (Hint: use a bijective function - a reversible shuffle/encryption of the counter bits - so you can still decode the short code back to the counter if needed.)

Exercise 3: Design the database schema for a URL shortener with detailed analytics: click count by hour, by country, and by device type. Where do you store click events? (Hint: not in the url_mappings table - that would make it write-heavy. Separate the click data into a time-series optimized store.)

Back to System Design Interviews