URL Encoding & Base62

"Make me a short URL." Sounds trivial. The shortcode must be: unique, URL-safe, short (6-8 chars), and ideally non-guessable. Plus, you need to mint billions of them at thousands per second without coordination overhead. The encoding choice — Base62 vs Base64 vs hash-based — drives the whole system design. The classic URL-shortener interview question is really about this trade-off.

Alphabet: 0-9 a-z A-Z = 62 characters. All URL-safe (no escaping). Each character carries log₂(62) ≈ 5.95 bits.

• 6 chars = 62⁶ ≈ 56 billion codes
• 7 chars = 62⁷ ≈ 3.5 trillion codes
• 8 chars = 62⁸ ≈ 218 trillion codes

Why not Base64? Base64 includes + and / which aren't URL-safe — they'd need percent-encoding. URL-safe Base64 (- and _) is fine but visually ugly. Base62 reads like a license plate.

Why not hex (Base16)? Each char is only 4 bits → twice as long for the same key space. Base62 is the sweet spot of "URL-safe + readable + dense."

package snowflake

import (
    "sync"
    "time"
)

const (
    epoch     int64 = 1577836800000 // 2020-01-01 UTC ms
    machineBits = 10
    seqBits     = 12
    maxSeq      = (1 << seqBits) - 1
)

type Node struct {
    mu       sync.Mutex
    machine  int64 // 0..1023
    lastMs   int64
    seq      int64
}

func (n *Node) NextID() int64 {
    n.mu.Lock(); defer n.mu.Unlock()
    now := time.Now().UnixMilli() - epoch
    if now == n.lastMs {
        n.seq = (n.seq + 1) & maxSeq
        if n.seq == 0 {
            for now <= n.lastMs { now = time.Now().UnixMilli() - epoch }
        }
    } else { n.seq = 0 }
    n.lastMs = now
    return (now << (machineBits+seqBits)) | (n.machine << seqBits) | n.seq
}

// 4096 IDs/ms/machine × 1024 machines = 4B IDs/sec ceiling

Naive: a single Postgres counter. SELECT nextval('shortcode_seq'). Encode in Base62. Insert. Done.

Problem: every shortener creation takes a round-trip to one DB. At 10k QPS, the counter is a hot row. Single point of contention.

Range-batch trick — each app server reserves a range of 10,000 IDs from the central counter. It hands out IDs locally without DB calls. When the range runs low, it requests another range. Coordination overhead drops 10,000×. This is how Twitter Snowflake-style ID generators work.

Snowflake IDs — 64 bits split into: timestamp (41 bits) + machine ID (10 bits) + sequence-within-ms (12 bits). Each server generates locally with no coordination. Roughly time-ordered. Trivially Base62-encodable to ~11 chars.

Pre-generated random pool — for non-guessable codes (interview ask: "make codes hard to enumerate"), a worker pre-generates batches of cryptographically-random 7-char Base62 strings, deduplicates against existing codes, stores them as "available." App grabs one per insertion. No contention; no enumeration attack.

URL shortener is the canonical problem. Pastebin uses the same encoding tricks. Any "shareable link" feature (Google Drive shares, Notion pages, Stripe payment links) builds on these patterns.