Designing a URL Shortener

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

Base62 Capacity Calculation
============================
 
Base62 character set: 0-9 (10) + a-z (26) + A-Z (26) = 62 characters
 
Length  |  Possible Codes    |  Human Readable
--------|--------------------|-----------------
1       |  62^1 = 62         |  62
2       |  62^2 = 3,844      |  ~4K
3       |  62^3 = 238,328    |  ~238K
4       |  62^4 = 14.8M      |  ~15 million
5       |  62^5 = 916M       |  ~1 billion
6       |  62^6 = 56.8B      |  ~57 billion
7       |  62^7 = 3.5T       |  ~3.5 trillion
8       |  62^8 = 218T       |  ~218 trillion
 
Our Requirements:
- 100M URLs/day × 365 days × 10 years = 365 billion URLs total
- Need buffer for deletions, collisions, custom codes
 
Conclusion:
- 6 characters (56.8B) insufficient for 10-year horizon
- 7 characters (3.5T) provides ~10x buffer - IDEAL
- 8 characters overkill for most use cases

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

// Base62 Encoding/Decoding Implementation
 
const BASE62_CHARS = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
const BASE = 62n; // Using BigInt for large numbers
 
/**
 * Encode a numeric ID to Base62 string
 * Example: 125 → "21" (1*62 + 25 + 10 + 26 = 125)
 */
function encodeBase62(id: bigint, minLength: number = 7): string {
    if (id === 0n) {
        return BASE62_CHARS[0].repeat(minLength);
    }
    
    let result = '';
    let num = id;
    
    while (num > 0n) {
        const remainder = Number(num % BASE);
        result = BASE62_CHARS[remainder] + result;
        num = num / BASE; // Integer division
    }
    
    // Pad to minimum length if needed
    while (result.length < minLength) {
        result = BASE62_CHARS[0] + result;
    }
    
    return result;
}
 
/**
 * Decode a Base62 string back to numeric ID
 * Example: "21" → 125
 */
function decodeBase62(code: string): bigint {
    let result = 0n;
    
    for (const char of code) {
        const index = BASE62_CHARS.indexOf(char);
        if (index === -1) {
            throw new Error(`Invalid Base62 character: ${char}`);
        }
        result = result * BASE + BigInt(index);
    }
    
    return result;
}
 
// Example usage:
// encodeBase62(1000000000n)     → "15FTGg"
// encodeBase62(3521614606207n)  → "zzzzzz" (max 6-char value)
// decodeBase62("a7Xk2B")        → corresponding integer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

// Auto-Increment ID Generation
 
async function createShortUrl(longUrl: string): Promise<ShortUrl> {
    // 1. Insert URL into database, get auto-generated ID
    const result = await db.query(
        'INSERT INTO urls (long_url, created_at) VALUES ($1, NOW()) RETURNING id',
        [longUrl]
    );
    
    const numericId = result.rows[0].id; // e.g., 1000000001
    
    // 2. Encode ID to Base62
    const shortCode = encodeBase62(BigInt(numericId)); // e.g., "15FTGh"
    
    // 3. Update record with short code (optional, for indexed lookup)
    await db.query(
        'UPDATE urls SET short_code = $1 WHERE id = $2',
        [shortCode, numericId]
    );
    
    return {
        shortCode,
        longUrl,
        shortUrl: `https://short.url/${shortCode}`
    };
}
 
// Redirect lookup is fast since ID is embedded in short code:
async function resolveShortCode(shortCode: string): Promise<string> {
    const numericId = decodeBase62(shortCode);
    
    // Direct lookup by primary key - extremely fast!
    const result = await db.query(
        'SELECT long_url FROM urls WHERE id = $1',
        [numericId]
    );
    
    return result.rows[0].long_url;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

-- Strategy: Range-based ID allocation
-- Each server reserves ID ranges, eliminating coordination
 
-- Server 1: IDs 1-1,000,000
-- Server 2: IDs 1,000,001-2,000,000
-- Server 3: IDs 2,000,001-3,000,000
 
-- ID Range Manager Table
CREATE TABLE id_ranges (
    server_id      INT PRIMARY KEY,
    range_start    BIGINT NOT NULL,
    range_end      BIGINT NOT NULL,
    current_value  BIGINT NOT NULL,
    created_at     TIMESTAMP DEFAULT NOW()
);
 
-- Each server atomically reserves a new range when needed:
UPDATE id_ranges 
SET range_start = (SELECT MAX(range_end) + 1 FROM id_ranges),
    range_end = (SELECT MAX(range_end) + 1000000 FROM id_ranges),
    current_value = (SELECT MAX(range_end) + 1 FROM id_ranges)
WHERE server_id = ?;
 
-- Alternative: Use stride-based approach
-- Server 1: 1, 4, 7, 10, ...  (n*3 + 1)
-- Server 2: 2, 5, 8, 11, ...  (n*3 + 2)  
-- Server 3: 3, 6, 9, 12, ...  (n*3 + 3)
 
-- This works but creates non-sequential IDs per server

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

import crypto from 'crypto';
 
/**
 * Generate short code by hashing the long URL
 * Uses first 43 bits of MD5/SHA hash, encoded in Base62
 */
function hashBasedShortCode(longUrl: string): string {
    // Step 1: Compute hash of URL
    const hash = crypto.createHash('md5').update(longUrl).digest();
    
    // Step 2: Take first 7 bytes (56 bits > 43 bits needed for 7 Base62 chars)
    const numeric = hash.readBigUInt64BE(0) & 0xFFFFFFFFFFFFn; // 48 bits
    
    // Step 3: Encode as Base62 (7 characters)
    return encodeBase62(numeric, 7);
}
 
// Problem: Different URLs may produce same short code (collision!)
// Solution: Check and handle collisions
 
async function createShortUrlWithHash(longUrl: string): Promise<ShortUrl> {
    let shortCode = hashBasedShortCode(longUrl);
    let attempt = 0;
    
    while (attempt < 5) {
        // Check if code already exists
        const existing = await db.query(
            'SELECT long_url FROM urls WHERE short_code = $1',
            [shortCode]
        );
        
        if (existing.rows.length === 0) {
            // Code is available
            await db.query(
                'INSERT INTO urls (short_code, long_url) VALUES ($1, $2)',
                [shortCode, longUrl]
            );
            return { shortCode, longUrl, shortUrl: `https://short.url/${shortCode}` };
        }
        
        if (existing.rows[0].long_url === longUrl) {
            // Same URL already shortened - return existing code
            return { shortCode, longUrl, shortUrl: `https://short.url/${shortCode}` };
        }
        
        // Collision! Different URL has same code
        // Strategy: Append attempt number and re-hash
        shortCode = hashBasedShortCode(longUrl + String(++attempt));
    }
    
    throw new Error('Failed to generate unique short code after 5 attempts');
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Collision Probability Analysis (Birthday Paradox)
=================================================
 
For a hash of k bits with n items:
P(collision) ≈ 1 - e^(-n²/2^(k+1))
 
With 7 Base62 characters (≈42 bits of entropy):
- 2^42 = 4.4 trillion possible values
 
At 100 billion URLs (10 years of data):
- P(at least one collision) ≈ 1 - e^(-(100B)²/(2*4.4T))
- P(collision) ≈ 1 - e^(-1136)
- P(collision) ≈ 100% (virtually guaranteed!)
 
Expected number of collisions:
- E[collisions] = n²/(2*2^k) = (100B)²/(2*4.4T) ≈ 1,136 collisions
 
Reality Check:
- With 7-character codes and 100 billion URLs, expect ~1000+ collisions
- This is manageable with collision resolution, but not negligible
- Using 8 characters (62^8 = 218T) reduces expected collisions to ~23

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Snowflake ID Structure (64 bits total)
======================================
 
┌─────────────────────────────────────────────────────────────────┐
│ 1 │          41 bits          │  10 bits  │     12 bits        │
│   │      (timestamp ms)       │ (machine) │    (sequence)       │
└───┴───────────────────────────┴───────────┴────────────────────┘
  │              │                    │              │
  │              │                    │              └─ Sequence number (0-4095)
  │              │                    │                 Reset each millisecond
  │              │                    │
  │              │                    └─ Machine/Worker ID (0-1023)
  │              │                       Unique per server
  │              │
  │              └─ Milliseconds since epoch (Jan 1, 2015)
  │                 ~69 years of range
  │
  └─ Sign bit (always 0 for positive)
 
Capacity:
- 41 bits timestamp: 2^41 ms = ~69 years from epoch
- 10 bits machine ID: 1024 unique machines
- 12 bits sequence: 4096 IDs per millisecond per machine
 
Total throughput: 4096 × 1000 = 4.1 million IDs/second/machine

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

/**
 * Snowflake-style ID Generator
 * Generates unique, time-sorted 64-bit IDs without coordination
 */
class SnowflakeGenerator {
    private readonly EPOCH = 1420070400000n; // Jan 1, 2015 UTC
    private readonly MACHINE_ID_BITS = 10n;
    private readonly SEQUENCE_BITS = 12n;
    
    private readonly maxMachineId = (1n << this.MACHINE_ID_BITS) - 1n;
    private readonly maxSequence = (1n << this.SEQUENCE_BITS) - 1n;
    
    private machineId: bigint;
    private sequence: bigint = 0n;
    private lastTimestamp: bigint = 0n;
    
    constructor(machineId: number) {
        this.machineId = BigInt(machineId);
        if (this.machineId > this.maxMachineId) {
            throw new Error(`Machine ID must be between 0 and ${this.maxMachineId}`);
        }
    }
    
    generate(): bigint {
        let timestamp = BigInt(Date.now()) - this.EPOCH;
        
        if (timestamp === this.lastTimestamp) {
            // Same millisecond - increment sequence
            this.sequence = (this.sequence + 1n) & this.maxSequence;
            
            if (this.sequence === 0n) {
                // Sequence overflow - wait for next millisecond
                timestamp = this.waitNextMillis(timestamp);
            }
        } else {
            // New millisecond - reset sequence
            this.sequence = 0n;
        }
        
        this.lastTimestamp = timestamp;
        
        // Compose the 64-bit ID
        return (timestamp << (this.MACHINE_ID_BITS + this.SEQUENCE_BITS)) |
               (this.machineId << this.SEQUENCE_BITS) |
               this.sequence;
    }
    
    private waitNextMillis(lastTimestamp: bigint): bigint {
        let timestamp = BigInt(Date.now()) - this.EPOCH;
        while (timestamp <= lastTimestamp) {
            timestamp = BigInt(Date.now()) - this.EPOCH;
        }
        return timestamp;
    }
}
 
// Usage for URL shortening:
const generator = new SnowflakeGenerator(42); // Machine #42
 
function createShortUrl(longUrl: string): ShortUrl {
    const id = generator.generate();           // e.g., 1234567890123456789n
    const shortCode = encodeBase62(id, 7);     // e.g., "4KbW8M2"
    
    // Store mapping in database
    await db.insert({ id, shortCode, longUrl });
    
    return { shortCode, longUrl };
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

Compact Snowflake (43 bits for 7-char Base62)
==============================================
 
┌─────────────────────────────────────────────────┐
│      32 bits        │  5 bits  │    6 bits     │
│   (timestamp secs)  │ (worker) │  (sequence)   │
└─────────────────────┴──────────┴───────────────┘
 
- 32 bits timestamp (seconds): ~136 years from epoch
- 5 bits worker ID: 32 workers maximum
- 6 bits sequence: 64 IDs per second per worker
 
Total: 43 bits → 8.8T possible IDs → fits in 7 Base62 chars
 
Throughput: 64 IDs/sec/worker × 32 workers = 2048 IDs/second
           (Sufficient for many use cases)
 
For higher throughput, use 8-character codes (218T capacity):
┌───────────────────────────────────────────────────────┐
│      35 bits        │  7 bits  │    8 bits          │
│   (timestamp secs)  │ (worker) │  (sequence)        │
└─────────────────────┴──────────┴────────────────────┘

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

/**
 * Range-Based ID Generator
 * 
 * Central service allocates ranges of IDs to worker servers.
 * Workers use their range locally without further coordination.
 */
 
// Central Range Allocator Service
class RangeAllocator {
    private nextRangeStart: bigint = 1n;
    private readonly rangeSize: bigint = 100000n; // 100K IDs per range
    
    async allocateRange(): Promise<{ start: bigint; end: bigint }> {
        return await this.db.transaction(async (tx) => {
            // Atomically get next range
            const result = await tx.query(
                'UPDATE range_counter SET value = value + $1 RETURNING value - $1 as start',
                [this.rangeSize]
            );
            
            const start = BigInt(result.rows[0].start);
            const end = start + this.rangeSize - 1n;
            
            return { start, end };
        });
    }
}
 
// Worker Server (URL Shortener Instance)
class RangeBasedIdGenerator {
    private currentId: bigint = 0n;
    private rangeEnd: bigint = 0n;
    
    constructor(private allocator: RangeAllocator) {}
    
    async getId(): Promise<bigint> {
        // Check if we need a new range
        if (this.currentId >= this.rangeEnd) {
            await this.fetchNewRange();
        }
        
        const id = this.currentId;
        this.currentId += 1n;
        return id;
    }
    
    private async fetchNewRange() {
        const range = await this.allocator.allocateRange();
        this.currentId = range.start;
        this.rangeEnd = range.end;
        console.log(`Fetched new range: ${range.start} - ${range.end}`);
    }
}
 
// Usage flow:
// 1. Server starts → requests range (e.g., 1-100,000)
// 2. Generates IDs 1, 2, 3, ... 99,999, 100,000
// 3. Requests new range (100,001-200,000)
// 4. Continues generating...

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79

/**
 * Custom Alias Handling
 */
 
const RESERVED_WORDS = new Set([
    'api', 'admin', 'login', 'logout', 'signup', 'settings',
    'www', 'mail', 'help', 'support', 'about', 'terms', 'privacy'
]);
 
const ALIAS_REGEX = /^[a-zA-Z0-9][a-zA-Z0-9_-]{1,29}$/;
 
interface AliasValidationResult {
    valid: boolean;
    error?: string;
}
 
function validateCustomAlias(alias: string): AliasValidationResult {
    // Normalize to lowercase for case-insensitive comparison
    const normalized = alias.toLowerCase();
    
    // Check format
    if (!ALIAS_REGEX.test(alias)) {
        return {
            valid: false,
            error: 'Alias must be 2-30 characters, alphanumeric with hyphens/underscores'
        };
    }
    
    // Check reserved words
    if (RESERVED_WORDS.has(normalized)) {
        return {
            valid: false,
            error: 'This alias is reserved and cannot be used'
        };
    }
    
    // Check for confusing patterns
    if (/^[0-9]+$/.test(alias)) {
        return {
            valid: false,
            error: 'Alias cannot be purely numeric (conflicts with auto-generated codes)'
        };
    }
    
    return { valid: true };
}
 
async function createWithCustomAlias(
    longUrl: string, 
    customAlias: string
): Promise<ShortUrl> {
    // Validate format
    const validation = validateCustomAlias(customAlias);
    if (!validation.valid) {
        throw new ValidationError(validation.error!);
    }
    
    const normalized = customAlias.toLowerCase();
    
    try {
        // Attempt to insert with unique constraint
        await db.query(
            `INSERT INTO urls (short_code, short_code_lower, long_url) 
             VALUES ($1, $2, $3)`,
            [customAlias, normalized, longUrl]
        );
        
        return {
            shortCode: customAlias,
            longUrl,
            shortUrl: `https://short.url/${customAlias}`
        };
    } catch (err) {
        if (err.code === 'UNIQUE_VIOLATION') {
            throw new ConflictError('This alias is already taken');
        }
        throw err;
    }
}