Design a URL Shortener

Problem introduction

The URL shortener is the classic first HLD problem because the product fits in one sentence, yet every core idea of high-level design shows up: estimate first, notice that reads beat writes a hundred to one, generate unique IDs without a bottleneck, put a cache where the traffic is, and keep slow work (analytics) off the hot path. Get this one right and most read-heavy systems look familiar.

Problem statement

A courier company in Dhaka sends an SMS with every parcel: "Track your parcel: https://track.example.com/orders/2026/11/08/BD-7781-55210-DHK?lang=bn&utm_source=sms". It's long, it eats SMS characters (each extra SMS costs money), and on cheap phones it often breaks across two lines and stops working. With a shortener, the SMS says "sho.rt/15FTGg" and the link still opens the full page.

What we are building: a service that turns a long URL into a short code, and redirects anyone who opens the short link to the long URL, fast, for years.

Who uses it: businesses and marketers creating links (a few writes), and the public clicking them (a huge number of reads, from all over the world, often on slow mobile networks).

What it solves: links that fit in an SMS, a tweet or a QR code; one place to change where a campaign link points; and click counts for the people who created the links.

What makes it technically interesting: a code must never point to two URLs, so codes must be unique across many servers; the redirect is on the user's critical path, so it must take milliseconds even with billions of links; clicks must be counted without slowing the redirect; and an open "create a link" box attracts spammers and phishers.

Requirements

Functional requirements

1. Create: given a long URL (http or https), return a short code. Optionally accept a custom alias ("eid26") if it's free.
2. Redirect: opening sho.rt/<code> redirects to the long URL. Unknown codes return 404.
3. Count clicks: record a click for every redirect; the link owner can see totals (a few minutes of delay is fine).
4. Links don't expire by default (an optional expiry date is a nice extra).
5. Out of scope for this design: user accounts and dashboards, editing a link's target, link previews.

Non-functional requirements

Redirect latency, availability and uniqueness are the requirements that shape the design. Throughput for writes is modest; throughput for reads is not.

Capacity estimation

Assumptions (said out loud, round numbers):

• 100 million new links a month.
• Each link is opened about 100 times over its life, so reads are 100× writes.
• A stored link (code, long URL, owner, created time) is about 500 bytes.
• Links are kept for 5 years; storage is replicated 3 times.
• The busiest hour is about 3× the average.

Traffic

Storage

Bandwidth: a redirect response is tiny (a few hundred bytes of headers). 12,000 / s × 500 B ≈ 6 MB/s out at peak. The network isn't a concern.

Cache size: traffic is very skewed: a few campaign links get most of the clicks. If the top 20% of the links created in the last month (20 million) get 80% of the reads, caching them takes 20M × 500 B ≈ 10 GB, which fits in one Redis node's memory with room to spare.

Code length: 6 base62 characters give 62⁶ ≈ 56.8 billion codes; 7 give 3.5 trillion. Six billion links fit in six characters with lots of room; we'll start IDs at 1,000,000,000 so codes look the same length from day one (6 characters until about 56 billion).

What the numbers say: reads beat writes 100 to 1 and the data is small. The hard part is not storage but answering 12,000 lookups a second in milliseconds. So: a cache in front of the database, read replicas, and nothing slow on the redirect path.

API design

• Authentication: creating links and reading stats need an API key (or a logged-in session) so we can rate limit per client and attribute abuse. Redirects are public and anonymous.
• Idempotency: POST /v1/links accepts an Idempotency-Key; a retried request after a timeout gets the same code back instead of a second link. (Creating two codes for the same URL isn't harmful, but it wastes IDs and confuses stats.)
• Why GET /{code} is at the root: short links must be as short as possible; sho.rt/15FTGg beats sho.rt/r/15FTGg.
• 302, not 301, by default: a 301 is cached by browsers forever, so repeat visits never reach us, which saves load but loses click counts and makes it impossible to fix a wrong target. Use 301 only for links that will never change and whose clicks don't matter.

Database design

Access pattern: one table, always looked up by its key (code), written once and read many times, no joins on the hot path. That's a key-value pattern.

Choice: start with PostgreSQL (or MySQL). At 120 writes/s and 9 TB over five years, a single primary with read replicas handles it for a long time, and SQL gives us constraints (unique code), transactions for the ID allocator, and easy reporting. A key-value store (DynamoDB, Cassandra) becomes attractive when you want hands-off horizontal scaling across regions; it's a fine alternative, not a requirement.

CREATE TABLE links (
  code        VARCHAR(30)  PRIMARY KEY,            -- base62 ID or custom alias
  long_url    VARCHAR(2048) NOT NULL,
  owner_id    BIGINT        NOT NULL,             -- API key / account that created it
  created_at  TIMESTAMPTZ   NOT NULL DEFAULT now(),
  expires_at  TIMESTAMPTZ
);
CREATE INDEX links_owner ON links (owner_id, created_at DESC);  -- "my links" in the dashboard

-- The ID allocator: one row, bumped once per block of IDs.
CREATE TABLE id_blocks (name TEXT PRIMARY KEY, next_id BIGINT NOT NULL);
-- UPDATE id_blocks SET next_id = next_id + 1000 WHERE name = 'links' RETURNING next_id - 1000;

-- Clicks are not stored row-by-row in this table: they go to a queue and an analytics store.

• Primary key = code: the redirect lookup is a primary-key read, and the database itself enforces "a code never maps to two URLs" (an insert of an existing alias fails).
• No foreign keys on the hot path: owner_id references the accounts table, but we don't join on redirects.
• Replication: one primary for writes, two or more async replicas for reads. Read-after-write right after creation is handled by returning the new code from the primary and warming the cache with it.
• Partitioning later: if links outgrow one primary, shard by code (hash of the code, consistent hashing or a fixed number of logical partitions). Every redirect then touches exactly one shard.
• Clicks: 12,000 inserts a second into the links database would make writes the bottleneck. Instead clicks go through a queue into a store built for counting (a time-series or columnar store, or aggregated counters).

Visual architecture

We deliberately don't have: microservices (one service does both create and redirect), Kafka on day one (a managed queue or Redis Streams is enough at these numbers), or multiple regions (until availability or latency targets require it).

Request lifecycle

Creating a link

1. Client → LB → app: POST /v1/links with the URL and an API key.
2. App checks the API key, the rate limit, the URL format (http/https, at most 2,048 characters), and a blocklist of known-malicious domains.
3. App takes the next ID from its local block. Only once every 1,000 links does it touch the database to reserve a new block.
4. App encodes the ID in base 62 and inserts (code, url, owner) into the primary. The primary key guarantees uniqueness.
5. App writes the new pair to Redis (so the first clicks don't miss) and returns 201 with the short URL.

Opening a short link (cache miss, then hit)

1. Browser → DNS → LB → any app server: GET /15FTGg.
2. App asks Redis for code:15FTGg. Hit: go to step 5.
3. Miss: app reads the replica by primary key (a few milliseconds).
4. App writes the pair to Redis with a TTL (a day, refreshed on use), so the next request is a hit.
5. App pushes click 15FTGg onto the queue without waiting; if the queue is full, the click is dropped, not the redirect.
6. App answers 302 Location: <long URL>. The browser follows it to the real page.

Component deep dive

Generating unique codes

Three common options:

The counter becomes a bottleneck only if every link asks the database for the next number. So each app server reserves a block of IDs (here 1,000) with one UPDATE ... RETURNING, then hands them out from memory. A server that crashes wastes the rest of its block, which is harmless: we have 56 billion six-character codes.

If guessable codes are a problem (someone could walk through all links), pass the ID through a reversible scramble (a keyed permutation such as a small Feistel network) before encoding. It stays unique and still needs no lookup.

Caching redirects

Cache-aside with a TTL: read Redis, on a miss read a replica and fill Redis. Because a link's target never changes in our requirements, the cache never needs invalidation on edit; the TTL only keeps memory for links that stay popular. With an expiry or an edit feature, we'd delete the key when the link changes. Hot links (a campaign in a TV ad) can be served from a CDN edge with a short cache time, so even our load balancer doesn't see most of that traffic.

Counting clicks without slowing redirects

The redirect puts a small event (code, time, maybe country and device) on a queue and returns. A worker reads the queue and adds to per-code, per-minute counters in an analytics store. If the queue is full, we drop the click rather than delay the user: an approximate count is acceptable, a slow redirect is not. With a durable queue, clicks survive worker restarts; the worker should be idempotent (count each event ID once) because queues deliver at least once.

The core, runnable

This program is the heart of the design, small enough to read in one sitting: base62 encoding, an allocator that hands out ID blocks, per-server ID sources, an LRU cache standing in for Redis, a database map standing in for PostgreSQL, and a service that creates links and resolves redirects with cache-aside and an asynchronous click queue. Two "app servers" share one database, one cache and one allocator.

urlshortener/
├── go.mod
├── base62.go          Encode / Decode
├── ids.go             Allocator (shared) and IDs (one per server)
├── cache.go           LRU cache, hits and misses
├── shortener.go       DB, Service: Create, Resolve, click worker
├── shortener_test.go  round trip, no duplicates under concurrency, cache, validation, full queue
└── cmd/demo/main.go   two servers, a few links, ten redirects

// base62.go
package shortener

// The 62 characters a short code may use: digits, then lowercase, then uppercase.
const alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

// Encode writes a number in base 62. Different numbers always give different codes, so a
// unique ID becomes a unique code with no collision check.
func Encode(n uint64) string {
	if n == 0 {
		return "0"
	}
	var buf [11]byte // 62^11 > 2^64, so 11 characters always fit
	i := len(buf)
	for n > 0 {
		i--
		buf[i] = alphabet[n%62]
		n /= 62
	}
	return string(buf[i:])
}

// Decode turns a code back into its number; ok is false for a character outside the alphabet.
func Decode(code string) (n uint64, ok bool) {
	for i := 0; i < len(code); i++ {
		c := code[i]
		var d byte
		switch {
		case c >= '0' && c <= '9':
			d = c - '0'
		case c >= 'a' && c <= 'z':
			d = c - 'a' + 10
		case c >= 'A' && c <= 'Z':
			d = c - 'A' + 36
		default:
			return 0, false
		}
		n = n*62 + uint64(d)
	}
	return n, true
}

// ids.go
package shortener

import "sync"

// Allocator stands in for one row in the database: "the next unused ID". It hands out whole
// blocks, so an app server talks to it once per block, not once per link.
type Allocator struct {
	mu    sync.Mutex
	next  uint64
	block uint64
}

// NewAllocator starts handing out IDs at start, block IDs at a time.
func NewAllocator(start, block uint64) *Allocator {
	return &Allocator{next: start, block: block}
}

// Take reserves the next block and returns its first ID and the ID just after it.
func (a *Allocator) Take() (from, to uint64) {
	a.mu.Lock()
	defer a.mu.Unlock()
	from = a.next
	a.next += a.block
	return from, a.next
}

// IDs is one app server's private block of IDs. Inside the block it needs no coordination.
type IDs struct {
	mu        sync.Mutex
	alloc     *Allocator
	next, end uint64
	Blocks    int // how many blocks this server has taken
}

// NewIDs gives an app server its own ID source backed by the shared allocator.
func NewIDs(a *Allocator) *IDs { return &IDs{alloc: a} }

// Next returns a fresh ID, taking a new block when the current one runs out.
func (s *IDs) Next() uint64 {
	s.mu.Lock()
	defer s.mu.Unlock()
	if s.next == s.end {
		s.next, s.end = s.alloc.Take()
		s.Blocks++
	}
	id := s.next
	s.next++
	return id
}

// cache.go
package shortener

import (
	"container/list"
	"sync"
)

// Cache is a small LRU cache of code -> long URL, like one Redis in front of the database.
type Cache struct {
	mu           sync.Mutex
	cap          int
	order        *list.List // front = most recently used
	items        map[string]*list.Element
	Hits, Misses int
}

type entry struct{ code, url string }

// NewCache holds at most capacity links.
func NewCache(capacity int) *Cache {
	return &Cache{cap: capacity, order: list.New(), items: map[string]*list.Element{}}
}

// Get returns the cached URL for code and counts a hit or a miss.
func (c *Cache) Get(code string) (string, bool) {
	c.mu.Lock()
	defer c.mu.Unlock()
	e, ok := c.items[code]
	if !ok {
		c.Misses++
		return "", false
	}
	c.Hits++
	c.order.MoveToFront(e)
	return e.Value.(entry).url, true
}

// Put stores a link, evicting the least recently used one when full.
func (c *Cache) Put(code, url string) {
	c.mu.Lock()
	defer c.mu.Unlock()
	if e, ok := c.items[code]; ok {
		c.order.MoveToFront(e)
		return
	}
	if c.order.Len() == c.cap {
		old := c.order.Back()
		c.order.Remove(old)
		delete(c.items, old.Value.(entry).code)
	}
	c.items[code] = c.order.PushFront(entry{code, url})
}

// shortener.go
// Package shortener is the core of a URL shortener: unique codes from ID blocks, a database,
// a cache in front of it for redirects, and click counting that never slows a redirect down.
package shortener

import (
	"errors"
	"strings"
	"sync"
	"sync/atomic"
)

var (
	ErrBadURL   = errors.New("bad url (http or https only, at most 2048 characters)")
	ErrBadAlias = errors.New("bad alias: 4 to 30 letters, digits or dashes")
	ErrTaken    = errors.New("alias already taken")
	ErrNotFound = errors.New("no such code")
)

// DB is the source of truth: code -> long URL. Reads counts lookups that reached it.
type DB struct {
	mu    sync.Mutex
	links map[string]string
	Reads int
}

func NewDB() *DB { return &DB{links: map[string]string{}} }

// insert adds a link only if the code is free (a primary-key insert).
func (d *DB) insert(code, url string) bool {
	d.mu.Lock()
	defer d.mu.Unlock()
	if _, ok := d.links[code]; ok {
		return false
	}
	d.links[code] = url
	return true
}

func (d *DB) get(code string) (string, bool) {
	d.mu.Lock()
	defer d.mu.Unlock()
	d.Reads++
	url, ok := d.links[code]
	return url, ok
}

// Service is one app server. Several can share the same DB, cache and allocator.
type Service struct {
	ids     *IDs
	db      *DB
	cache   *Cache
	clicks  chan string
	mu      sync.Mutex
	counts  map[string]int
	dropped atomic.Int64 // clicks lost because the queue was full
	done    sync.WaitGroup
}

// NewService starts the background worker that counts clicks from a queue of queueSize.
func NewService(ids *IDs, db *DB, cache *Cache, queueSize int) *Service {
	s := &Service{ids: ids, db: db, cache: cache, clicks: make(chan string, queueSize), counts: map[string]int{}}
	s.done.Add(1)
	go func() {
		defer s.done.Done()
		for code := range s.clicks {
			s.mu.Lock()
			s.counts[code]++
			s.mu.Unlock()
		}
	}()
	return s
}

func validURL(u string) bool {
	return (strings.HasPrefix(u, "http://") || strings.HasPrefix(u, "https://")) &&
		len(u) <= 2048 && !strings.ContainsAny(u, " \t\n")
}

func validAlias(a string) bool {
	if len(a) < 4 || len(a) > 30 {
		return false
	}
	for _, c := range a {
		if !(c >= 'a' && c <= 'z' || c >= 'A' && c <= 'Z' || c >= '0' && c <= '9' || c == '-') {
			return false
		}
	}
	return true
}

// Create stores a long URL and returns its short code: the alias if one is given, otherwise
// the next ID in base 62.
func (s *Service) Create(longURL, alias string) (string, error) {
	if !validURL(longURL) {
		return "", ErrBadURL
	}
	code := alias
	if alias == "" {
		code = Encode(s.ids.Next())
	} else if !validAlias(alias) {
		return "", ErrBadAlias
	}
	if !s.db.insert(code, longURL) {
		return "", ErrTaken
	}
	return code, nil
}

// Resolve finds the long URL for a redirect: cache first, then the database (cache-aside).
// The click is put on a queue; if the queue is full the click is dropped, the redirect isn't.
func (s *Service) Resolve(code string) (string, error) {
	url, ok := s.cache.Get(code)
	if !ok {
		if url, ok = s.db.get(code); !ok {
			return "", ErrNotFound
		}
		s.cache.Put(code, url)
	}
	select {
	case s.clicks <- code:
	default:
		s.dropped.Add(1)
	}
	return url, nil
}

// Close stops taking clicks and waits until every queued click is counted.
func (s *Service) Close() { close(s.clicks); s.done.Wait() }

// Dropped is how many clicks were lost because the queue was full.
func (s *Service) Dropped() int64 { return s.dropped.Load() }

// Clicks returns the counted clicks for a code (after Close, the final number).
func (s *Service) Clicks(code string) int {
	s.mu.Lock()
	defer s.mu.Unlock()
	return s.counts[code]
}

// cmd/demo/main.go
// Command demo runs two app servers that share one database, one cache and one ID allocator.
package main

import (
	"fmt"

	shortener "urlshortener"
)

func main() {
	alloc := shortener.NewAllocator(1_000_000_000, 1000)
	db, cache := shortener.NewDB(), shortener.NewCache(2)
	idsA, idsB := shortener.NewIDs(alloc), shortener.NewIDs(alloc)
	a := shortener.NewService(idsA, db, cache, 100)
	b := shortener.NewService(idsB, db, cache, 100)
	fmt.Println("IDs start at 1,000,000,000 and are handed out in blocks of 1,000")

	create := func(name string, s *shortener.Service, url, alias string) string {
		code, err := s.Create(url, alias)
		if err != nil {
			fmt.Printf("  %s create %-36s -> error: %v\n", name, url, err)
			return ""
		}
		fmt.Printf("  %s create %-36s -> %s\n", name, url, code)
		return code
	}
	sale := create("A", a, "https://shop.example.com/eid-sale", "")
	news := create("B", b, "https://news.example.com/budget-2026", "")
	jobs := create("A", a, "https://jobs.example.com/backend", "")
	create("A", a, "https://shop.example.com/eid-sale", "eid26")
	create("B", b, "https://other.example.com/", "eid26")
	create("B", b, "ftp://files.example.com/x", "")
	fmt.Printf("  blocks taken: A %d, B %d\n", idsA.Blocks, idsB.Blocks)

	n, _ := shortener.Decode(sale)
	fmt.Printf("code %s is ID %d\n", sale, n)

	// Ten redirects: the sale link is popular. The cache holds 2 links.
	for _, code := range []string{sale, sale, news, sale, jobs, sale, sale, news, "zzzzzz", sale} {
		url, err := a.Resolve(code)
		if err != nil {
			fmt.Printf("  GET /%s -> 404 (%v)\n", code, err)
			continue
		}
		fmt.Printf("  GET /%s -> 302 %s\n", code, url)
	}
	a.Close()
	b.Close()
	fmt.Printf("cache: %d hits, %d misses; database reads: %d\n", cache.Hits, cache.Misses, db.Reads)
	fmt.Printf("clicks: %s=%d %s=%d %s=%d, dropped %d\n", sale, a.Clicks(sale), news, a.Clicks(news), jobs, a.Clicks(jobs), a.Dropped())
}

Running the demo:

$ go run ./cmd/demo
IDs start at 1,000,000,000 and are handed out in blocks of 1,000
  A create https://shop.example.com/eid-sale    -> 15FTGg
  B create https://news.example.com/budget-2026 -> 15FTWo
  A create https://jobs.example.com/backend     -> 15FTGh
  A create https://shop.example.com/eid-sale    -> eid26
  B create https://other.example.com/           -> error: alias already taken
  B create ftp://files.example.com/x            -> error: bad url (http or https only, at most 2048 characters)
  blocks taken: A 1, B 1
code 15FTGg is ID 1000000000
  GET /15FTGg -> 302 https://shop.example.com/eid-sale
  GET /15FTGg -> 302 https://shop.example.com/eid-sale
  GET /15FTWo -> 302 https://news.example.com/budget-2026
  GET /15FTGg -> 302 https://shop.example.com/eid-sale
  GET /15FTGh -> 302 https://jobs.example.com/backend
  GET /15FTGg -> 302 https://shop.example.com/eid-sale
  GET /15FTGg -> 302 https://shop.example.com/eid-sale
  GET /15FTWo -> 302 https://news.example.com/budget-2026
  GET /zzzzzz -> 404 (no such code)
  GET /15FTGg -> 302 https://shop.example.com/eid-sale
cache: 5 hits, 5 misses; database reads: 5
clicks: 15FTGg=6 15FTWo=2 15FTGh=1, dropped 0

Reading the output:

• Codes: A got the block starting at 1,000,000,000 and B the next one, so A's links are 15FTGg, 15FTGh and B's is 15FTWo. Each server took exactly one block for its links: one allocator round trip per 1,000 links.
• Alias: eid26 was free the first time; the second request for it fails with "alias already taken", enforced by the primary-key insert. The ftp:// link is rejected before it uses an ID.
• Decode: 15FTGg turns back into ID 1,000,000,000, so a code can be mapped to its shard without any lookup.
• Redirects: the cache holds only 2 links, yet the popular sale link stays in it. 5 of the 10 lookups were cache hits; the 5 misses include the first view of each link, a re-read after the jobs link pushed news out, and the unknown code. Only misses reached the database. (The demo doesn't warm the cache on create, so you can see the first miss; production does, as in the lifecycle above.)
• Clicks: 6, 2 and 1, counted by the background worker after the redirects had already been answered; nothing was dropped because the queue never filled.

The tests check what matters most: base62 round trips, no duplicate codes when 4 servers create 2,400 links concurrently (run with -race), that a cached link reads the database only once, validation and alias errors, and that a full click queue drops clicks rather than blocking redirects.

// shortener_test.go
package shortener

import (
	"errors"
	"sync"
	"testing"
)

func TestEncodeDecodeRoundTrip(t *testing.T) {
	for _, n := range []uint64{0, 1, 61, 62, 3843, 1_000_000_000, 1<<64 - 1} {
		got, ok := Decode(Encode(n))
		if !ok || got != n {
			t.Fatalf("Decode(Encode(%d)) = %d, %v", n, got, ok)
		}
	}
	if _, ok := Decode("ab-c"); ok {
		t.Fatal("'-' is not in the alphabet")
	}
}

func TestBlocksDontOverlapAcrossServers(t *testing.T) {
	alloc := NewAllocator(1, 50)
	db := NewDB()
	var servers []*Service
	for i := 0; i < 4; i++ {
		servers = append(servers, NewService(NewIDs(alloc), db, NewCache(8), 10))
	}
	var wg sync.WaitGroup
	var mu sync.Mutex
	seen := map[string]bool{}
	for _, s := range servers {
		for g := 0; g < 2; g++ {
			wg.Add(1)
			go func(s *Service) {
				defer wg.Done()
				for i := 0; i < 300; i++ {
					code, err := s.Create("https://example.com/x", "")
					if err != nil {
						t.Error(err)
						return
					}
					mu.Lock()
					if seen[code] {
						t.Errorf("duplicate code %s", code)
					}
					seen[code] = true
					mu.Unlock()
				}
			}(s)
		}
	}
	wg.Wait()
	if len(seen) != 4*2*300 {
		t.Fatalf("got %d codes, want %d", len(seen), 4*2*300)
	}
}

func TestResolveUsesTheCacheAfterTheFirstRead(t *testing.T) {
	db := NewDB()
	s := NewService(NewIDs(NewAllocator(100, 10)), db, NewCache(4), 10)
	code, _ := s.Create("https://example.com/a", "")
	for i := 0; i < 3; i++ {
		if url, err := s.Resolve(code); err != nil || url != "https://example.com/a" {
			t.Fatalf("Resolve = %q, %v", url, err)
		}
	}
	s.Close()
	if db.Reads != 1 {
		t.Fatalf("database reads = %d, want 1", db.Reads)
	}
	if s.Clicks(code) != 3 {
		t.Fatalf("clicks = %d, want 3", s.Clicks(code))
	}
}

func TestAliasAndValidation(t *testing.T) {
	s := NewService(NewIDs(NewAllocator(1, 10)), NewDB(), NewCache(2), 10)
	defer s.Close()
	if _, err := s.Create("https://a.example", "promo"); err != nil {
		t.Fatal(err)
	}
	if _, err := s.Create("https://b.example", "promo"); !errors.Is(err, ErrTaken) {
		t.Fatalf("err = %v, want ErrTaken", err)
	}
	if _, err := s.Create("javascript:alert(1)", ""); !errors.Is(err, ErrBadURL) {
		t.Fatalf("err = %v, want ErrBadURL", err)
	}
	if _, err := s.Create("https://a.example", "no"); !errors.Is(err, ErrBadAlias) {
		t.Fatalf("err = %v, want ErrBadAlias", err)
	}
	if _, err := s.Resolve("nothing"); !errors.Is(err, ErrNotFound) {
		t.Fatalf("err = %v, want ErrNotFound", err)
	}
}

func TestFullClickQueueDropsClicksNotRedirects(t *testing.T) {
	s := NewService(NewIDs(NewAllocator(1, 10)), NewDB(), NewCache(2), 0)
	code, _ := s.Create("https://example.com/", "")
	s.mu.Lock() // hold the counter so the worker can't drain the queue
	for i := 0; i < 5; i++ {
		if _, err := s.Resolve(code); err != nil {
			t.Fatal(err)
		}
	}
	dropped := s.Dropped()
	s.mu.Unlock()
	s.Close()
	if dropped == 0 {
		t.Fatal("expected some clicks to be dropped with a zero-size queue")
	}
}

$ go test -race -v ./...
=== RUN   TestEncodeDecodeRoundTrip
--- PASS: TestEncodeDecodeRoundTrip (0.00s)
=== RUN   TestBlocksDontOverlapAcrossServers
--- PASS: TestBlocksDontOverlapAcrossServers (0.01s)
=== RUN   TestResolveUsesTheCacheAfterTheFirstRead
--- PASS: TestResolveUsesTheCacheAfterTheFirstRead (0.00s)
=== RUN   TestAliasAndValidation
--- PASS: TestAliasAndValidation (0.00s)
=== RUN   TestFullClickQueueDropsClicksNotRedirects
--- PASS: TestFullClickQueueDropsClicksNotRedirects (0.00s)
PASS
ok  	urlshortener	1.020s
?   	urlshortener/cmd/demo	[no test files]

The same core in five more languages

Single-threaded versions with the same classes and the same output. The click "worker" runs when close() is called, which is enough to show the design; the Go version runs it concurrently.

"""A URL shortener's core: unique codes from ID blocks, a database, a cache in front of it
for redirects, and click counting that never slows a redirect down. Two app servers share
one database, one cache and one ID allocator."""
from collections import OrderedDict

ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"


def encode(n: int) -> str:
    """A number in base 62. Different numbers always give different codes."""
    if n == 0:
        return "0"
    out = []
    while n > 0:
        out.append(ALPHABET[n % 62])
        n //= 62
    return "".join(reversed(out))


def decode(code: str) -> int | None:
    n = 0
    for c in code:
        d = ALPHABET.find(c)
        if d < 0:
            return None
        n = n * 62 + d
    return n


class Allocator:
    """Stands in for one database row, "the next unused ID". Hands out whole blocks."""

    def __init__(self, start: int, block: int):
        self.next, self.block = start, block

    def take(self) -> tuple[int, int]:
        start = self.next
        self.next += self.block
        return start, self.next


class IDs:
    """One app server's private block of IDs."""

    def __init__(self, alloc: Allocator):
        self.alloc = alloc
        self.next = self.end = 0
        self.blocks = 0

    def take_next(self) -> int:
        if self.next == self.end:
            self.next, self.end = self.alloc.take()
            self.blocks += 1
        n = self.next
        self.next += 1
        return n


class Cache:
    """A small LRU cache of code -> long URL, like one Redis in front of the database."""

    def __init__(self, capacity: int):
        self.cap = capacity
        self.items: OrderedDict[str, str] = OrderedDict()  # last = most recently used
        self.hits = self.misses = 0

    def get(self, code: str) -> str | None:
        if code not in self.items:
            self.misses += 1
            return None
        self.hits += 1
        self.items.move_to_end(code)
        return self.items[code]

    def put(self, code: str, url: str) -> None:
        if code in self.items:
            self.items.move_to_end(code)
            return
        if len(self.items) == self.cap:
            self.items.popitem(last=False)
        self.items[code] = url


class DB:
    """The source of truth: code -> long URL. reads counts lookups that reached it."""

    def __init__(self):
        self.links: dict[str, str] = {}
        self.reads = 0

    def insert(self, code: str, url: str) -> bool:
        if code in self.links:
            return False
        self.links[code] = url
        return True

    def get(self, code: str) -> str | None:
        self.reads += 1
        return self.links.get(code)


class ShortenerError(Exception):
    pass


BAD_URL = "bad url (http or https only, at most 2048 characters)"
BAD_ALIAS = "bad alias: 4 to 30 letters, digits or dashes"
TAKEN = "alias already taken"
NOT_FOUND = "no such code"


def valid_url(u: str) -> bool:
    return u.startswith(("http://", "https://")) and len(u) <= 2048 and not any(c in u for c in " \t\n")


def valid_alias(a: str) -> bool:
    return 4 <= len(a) <= 30 and all(c.isascii() and (c.isalnum() or c == "-") for c in a)


class Service:
    """One app server. Clicks go on a bounded queue; a worker counts them later."""

    def __init__(self, ids: IDs, db: DB, cache: Cache, queue_size: int):
        self.ids, self.db, self.cache = ids, db, cache
        self.queue: list[str] = []
        self.queue_size = queue_size
        self.counts: dict[str, int] = {}
        self.dropped = 0

    def create(self, long_url: str, alias: str = "") -> str:
        if not valid_url(long_url):
            raise ShortenerError(BAD_URL)
        code = alias
        if alias == "":
            code = encode(self.ids.take_next())
        elif not valid_alias(alias):
            raise ShortenerError(BAD_ALIAS)
        if not self.db.insert(code, long_url):
            raise ShortenerError(TAKEN)
        return code

    def resolve(self, code: str) -> str:
        url = self.cache.get(code)
        if url is None:
            url = self.db.get(code)
            if url is None:
                raise ShortenerError(NOT_FOUND)
            self.cache.put(code, url)
        if len(self.queue) < self.queue_size:
            self.queue.append(code)
        else:
            self.dropped += 1
        return url

    def close(self) -> None:
        """The worker: count every queued click."""
        for code in self.queue:
            self.counts[code] = self.counts.get(code, 0) + 1
        self.queue.clear()

    def clicks(self, code: str) -> int:
        return self.counts.get(code, 0)


alloc = Allocator(1_000_000_000, 1000)
db, cache = DB(), Cache(2)
ids_a, ids_b = IDs(alloc), IDs(alloc)
a, b = Service(ids_a, db, cache, 100), Service(ids_b, db, cache, 100)
print("IDs start at 1,000,000,000 and are handed out in blocks of 1,000")


def create(name: str, s: Service, url: str, alias: str = "") -> str:
    try:
        code = s.create(url, alias)
    except ShortenerError as e:
        print(f"  {name} create {url:<36} -> error: {e}")
        return ""
    print(f"  {name} create {url:<36} -> {code}")
    return code


sale = create("A", a, "https://shop.example.com/eid-sale")
news = create("B", b, "https://news.example.com/budget-2026")
jobs = create("A", a, "https://jobs.example.com/backend")
create("A", a, "https://shop.example.com/eid-sale", "eid26")
create("B", b, "https://other.example.com/", "eid26")
create("B", b, "ftp://files.example.com/x")
print(f"  blocks taken: A {ids_a.blocks}, B {ids_b.blocks}")
print(f"code {sale} is ID {decode(sale)}")

# Ten redirects: the sale link is popular. The cache holds 2 links.
for code in [sale, sale, news, sale, jobs, sale, sale, news, "zzzzzz", sale]:
    try:
        print(f"  GET /{code} -> 302 {a.resolve(code)}")
    except ShortenerError as e:
        print(f"  GET /{code} -> 404 ({e})")
a.close()
b.close()
print(f"cache: {cache.hits} hits, {cache.misses} misses; database reads: {db.reads}")
print(f"clicks: {sale}={a.clicks(sale)} {news}={a.clicks(news)} {jobs}={a.clicks(jobs)}, dropped {a.dropped}")

// A URL shortener's core: unique codes from ID blocks, a database, a cache in front of it for
// redirects, and click counting that never slows a redirect down. Two app servers share one
// database, one cache and one ID allocator. IDs here stay far below 2^53, so numbers are exact.

const ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

/** A number in base 62. Different numbers always give different codes. */
function encode(n: number): string {
  if (n === 0) return "0";
  let out = "";
  while (n > 0) {
    out = ALPHABET[n % 62] + out;
    n = Math.floor(n / 62);
  }
  return out;
}

function decode(code: string): number | undefined {
  let n = 0;
  for (const c of code) {
    const d = ALPHABET.indexOf(c);
    if (d < 0) return undefined;
    n = n * 62 + d;
  }
  return n;
}

/** Stands in for one database row, "the next unused ID". Hands out whole blocks. */
class Allocator {
  next: number;
  readonly block: number;
  constructor(start: number, block: number) {
    this.next = start;
    this.block = block;
  }
  take(): [number, number] {
    const start = this.next;
    this.next += this.block;
    return [start, this.next];
  }
}

/** One app server's private block of IDs. */
class IDs {
  readonly alloc: Allocator;
  next = 0;
  end = 0;
  blocks = 0;
  constructor(alloc: Allocator) {
    this.alloc = alloc;
  }
  takeNext(): number {
    if (this.next === this.end) {
      [this.next, this.end] = this.alloc.take();
      this.blocks++;
    }
    return this.next++;
  }
}

/** A small LRU cache of code -> long URL; a Map keeps insertion order, oldest first. */
class LinkCache {
  readonly cap: number;
  readonly items = new Map<string, string>();
  hits = 0;
  misses = 0;
  constructor(capacity: number) {
    this.cap = capacity;
  }
  get(code: string): string | undefined {
    const url = this.items.get(code);
    if (url === undefined) {
      this.misses++;
      return undefined;
    }
    this.hits++;
    this.items.delete(code);
    this.items.set(code, url);
    return url;
  }
  put(code: string, url: string): void {
    if (this.items.has(code)) {
      this.items.delete(code);
    } else if (this.items.size === this.cap) {
      this.items.delete(this.items.keys().next().value!);
    }
    this.items.set(code, url);
  }
}

/** The source of truth: code -> long URL. reads counts lookups that reached it. */
class DB {
  readonly links = new Map<string, string>();
  reads = 0;
  insert(code: string, url: string): boolean {
    if (this.links.has(code)) return false;
    this.links.set(code, url);
    return true;
  }
  get(code: string): string | undefined {
    this.reads++;
    return this.links.get(code);
  }
}

class ShortenerError extends Error {}
const BAD_URL = "bad url (http or https only, at most 2048 characters)";
const BAD_ALIAS = "bad alias: 4 to 30 letters, digits or dashes";
const TAKEN = "alias already taken";
const NOT_FOUND = "no such code";

const validURL = (u: string) => (u.startsWith("http://") || u.startsWith("https://")) && u.length <= 2048 && !/[ \t\n]/.test(u);
const validAlias = (a: string) => a.length >= 4 && a.length <= 30 && /^[A-Za-z0-9-]+$/.test(a);

/** One app server. Clicks go on a bounded queue; a worker counts them later. */
class Service {
  readonly ids: IDs;
  readonly db: DB;
  readonly cache: LinkCache;
  readonly queueSize: number;
  readonly queue: string[] = [];
  readonly counts = new Map<string, number>();
  dropped = 0;
  constructor(ids: IDs, db: DB, cache: LinkCache, queueSize: number) {
    this.ids = ids;
    this.db = db;
    this.cache = cache;
    this.queueSize = queueSize;
  }
  create(longURL: string, alias = ""): string {
    if (!validURL(longURL)) throw new ShortenerError(BAD_URL);
    let code = alias;
    if (alias === "") code = encode(this.ids.takeNext());
    else if (!validAlias(alias)) throw new ShortenerError(BAD_ALIAS);
    if (!this.db.insert(code, longURL)) throw new ShortenerError(TAKEN);
    return code;
  }
  resolve(code: string): string {
    let url = this.cache.get(code);
    if (url === undefined) {
      url = this.db.get(code);
      if (url === undefined) throw new ShortenerError(NOT_FOUND);
      this.cache.put(code, url);
    }
    if (this.queue.length < this.queueSize) this.queue.push(code);
    else this.dropped++;
    return url;
  }
  /** The worker: count every queued click. */
  close(): void {
    for (const code of this.queue) this.counts.set(code, (this.counts.get(code) ?? 0) + 1);
    this.queue.length = 0;
  }
  clicks(code: string): number {
    return this.counts.get(code) ?? 0;
  }
}

const alloc = new Allocator(1_000_000_000, 1000);
const db = new DB();
const cache = new LinkCache(2);
const [idsA, idsB] = [new IDs(alloc), new IDs(alloc)];
const a = new Service(idsA, db, cache, 100);
const b = new Service(idsB, db, cache, 100);
console.log("IDs start at 1,000,000,000 and are handed out in blocks of 1,000");

function create(name: string, s: Service, url: string, alias = ""): string {
  try {
    const code = s.create(url, alias);
    console.log(`  ${name} create ${url.padEnd(36)} -> ${code}`);
    return code;
  } catch (e) {
    console.log(`  ${name} create ${url.padEnd(36)} -> error: ${(e as Error).message}`);
    return "";
  }
}

const sale = create("A", a, "https://shop.example.com/eid-sale");
const news = create("B", b, "https://news.example.com/budget-2026");
const jobs = create("A", a, "https://jobs.example.com/backend");
create("A", a, "https://shop.example.com/eid-sale", "eid26");
create("B", b, "https://other.example.com/", "eid26");
create("B", b, "ftp://files.example.com/x");
console.log(`  blocks taken: A ${idsA.blocks}, B ${idsB.blocks}`);
console.log(`code ${sale} is ID ${decode(sale)}`);

// Ten redirects: the sale link is popular. The cache holds 2 links.
for (const code of [sale, sale, news, sale, jobs, sale, sale, news, "zzzzzz", sale]) {
  try {
    console.log(`  GET /${code} -> 302 ${a.resolve(code)}`);
  } catch (e) {
    console.log(`  GET /${code} -> 404 (${(e as Error).message})`);
  }
}
a.close();
b.close();
console.log(`cache: ${cache.hits} hits, ${cache.misses} misses; database reads: ${db.reads}`);
console.log(`clicks: ${sale}=${a.clicks(sale)} ${news}=${a.clicks(news)} ${jobs}=${a.clicks(jobs)}, dropped ${a.dropped}`);

// A URL shortener's core: unique codes from ID blocks, a database, a cache in front of it for
// redirects, and click counting that never slows a redirect down. Two app servers share one
// database, one cache and one ID allocator.
use std::cell::RefCell;
use std::collections::{HashMap, VecDeque};
use std::rc::Rc;

const ALPHABET: &[u8] = b"0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

/// A number in base 62. Different numbers always give different codes.
fn encode(mut n: u64) -> String {
    if n == 0 {
        return "0".to_string();
    }
    let mut out = Vec::new();
    while n > 0 {
        out.push(ALPHABET[(n % 62) as usize]);
        n /= 62;
    }
    out.reverse();
    String::from_utf8(out).unwrap()
}

fn decode(code: &str) -> Option<u64> {
    code.bytes().try_fold(0u64, |n, c| ALPHABET.iter().position(|&a| a == c).map(|d| n * 62 + d as u64))
}

/// Stands in for one database row, "the next unused ID". Hands out whole blocks.
struct Allocator {
    next: u64,
    block: u64,
}

impl Allocator {
    fn take(&mut self) -> (u64, u64) {
        let start = self.next;
        self.next += self.block;
        (start, self.next)
    }
}

/// One app server's private block of IDs.
struct Ids {
    alloc: Rc<RefCell<Allocator>>,
    next: u64,
    end: u64,
    blocks: u32,
}

impl Ids {
    fn new(alloc: Rc<RefCell<Allocator>>) -> Self {
        Ids { alloc, next: 0, end: 0, blocks: 0 }
    }
    fn take_next(&mut self) -> u64 {
        if self.next == self.end {
            (self.next, self.end) = self.alloc.borrow_mut().take();
            self.blocks += 1;
        }
        self.next += 1;
        self.next - 1
    }
}

/// A small LRU cache of code -> long URL, like one Redis in front of the database.
struct Cache {
    cap: usize,
    order: VecDeque<String>, // back = most recently used
    items: HashMap<String, String>,
    hits: u32,
    misses: u32,
}

impl Cache {
    fn new(cap: usize) -> Self {
        Cache { cap, order: VecDeque::new(), items: HashMap::new(), hits: 0, misses: 0 }
    }
    fn touch(&mut self, code: &str) {
        self.order.retain(|c| c != code);
        self.order.push_back(code.to_string());
    }
    fn get(&mut self, code: &str) -> Option<String> {
        match self.items.get(code).cloned() {
            None => {
                self.misses += 1;
                None
            }
            Some(url) => {
                self.hits += 1;
                self.touch(code);
                Some(url)
            }
        }
    }
    fn put(&mut self, code: &str, url: &str) {
        if !self.items.contains_key(code) && self.items.len() == self.cap {
            let old = self.order.pop_front().unwrap();
            self.items.remove(&old);
        }
        self.items.insert(code.to_string(), url.to_string());
        self.touch(code);
    }
}

/// The source of truth: code -> long URL. reads counts lookups that reached it.
#[derive(Default)]
struct Db {
    links: HashMap<String, String>,
    reads: u32,
}

impl Db {
    fn insert(&mut self, code: &str, url: &str) -> bool {
        if self.links.contains_key(code) {
            return false;
        }
        self.links.insert(code.to_string(), url.to_string());
        true
    }
    fn get(&mut self, code: &str) -> Option<String> {
        self.reads += 1;
        self.links.get(code).cloned()
    }
}

const BAD_URL: &str = "bad url (http or https only, at most 2048 characters)";
const BAD_ALIAS: &str = "bad alias: 4 to 30 letters, digits or dashes";
const TAKEN: &str = "alias already taken";
const NOT_FOUND: &str = "no such code";

fn valid_url(u: &str) -> bool {
    (u.starts_with("http://") || u.starts_with("https://")) && u.len() <= 2048 && !u.contains([' ', '\t', '\n'])
}

fn valid_alias(a: &str) -> bool {
    (4..=30).contains(&a.len()) && a.chars().all(|c| c.is_ascii_alphanumeric() || c == '-')
}

/// One app server. Clicks go on a bounded queue; a worker counts them later.
struct Service {
    ids: Ids,
    db: Rc<RefCell<Db>>,
    cache: Rc<RefCell<Cache>>,
    queue: Vec<String>,
    queue_size: usize,
    counts: HashMap<String, u32>,
    dropped: u32,
}

impl Service {
    fn new(ids: Ids, db: Rc<RefCell<Db>>, cache: Rc<RefCell<Cache>>, queue_size: usize) -> Self {
        Service { ids, db, cache, queue: Vec::new(), queue_size, counts: HashMap::new(), dropped: 0 }
    }

    fn create(&mut self, long_url: &str, alias: &str) -> Result<String, &'static str> {
        if !valid_url(long_url) {
            return Err(BAD_URL);
        }
        let code = if alias.is_empty() {
            encode(self.ids.take_next())
        } else if !valid_alias(alias) {
            return Err(BAD_ALIAS);
        } else {
            alias.to_string()
        };
        if !self.db.borrow_mut().insert(&code, long_url) {
            return Err(TAKEN);
        }
        Ok(code)
    }

    fn resolve(&mut self, code: &str) -> Result<String, &'static str> {
        let cached = self.cache.borrow_mut().get(code);
        let url = match cached {
            Some(url) => url,
            None => {
                let url = self.db.borrow_mut().get(code).ok_or(NOT_FOUND)?;
                self.cache.borrow_mut().put(code, &url);
                url
            }
        };
        if self.queue.len() < self.queue_size {
            self.queue.push(code.to_string());
        } else {
            self.dropped += 1;
        }
        Ok(url)
    }

    /// The worker: count every queued click.
    fn close(&mut self) {
        for code in self.queue.drain(..) {
            *self.counts.entry(code).or_default() += 1;
        }
    }

    fn clicks(&self, code: &str) -> u32 {
        self.counts.get(code).copied().unwrap_or(0)
    }
}

fn create(name: &str, s: &mut Service, url: &str, alias: &str) -> String {
    match s.create(url, alias) {
        Ok(code) => {
            println!("  {name} create {url:<36} -> {code}");
            code
        }
        Err(e) => {
            println!("  {name} create {url:<36} -> error: {e}");
            String::new()
        }
    }
}

fn main() {
    let alloc = Rc::new(RefCell::new(Allocator { next: 1_000_000_000, block: 1000 }));
    let db = Rc::new(RefCell::new(Db::default()));
    let cache = Rc::new(RefCell::new(Cache::new(2)));
    let mut a = Service::new(Ids::new(alloc.clone()), db.clone(), cache.clone(), 100);
    let mut b = Service::new(Ids::new(alloc.clone()), db.clone(), cache.clone(), 100);
    println!("IDs start at 1,000,000,000 and are handed out in blocks of 1,000");

    let sale = create("A", &mut a, "https://shop.example.com/eid-sale", "");
    let news = create("B", &mut b, "https://news.example.com/budget-2026", "");
    let jobs = create("A", &mut a, "https://jobs.example.com/backend", "");
    create("A", &mut a, "https://shop.example.com/eid-sale", "eid26");
    create("B", &mut b, "https://other.example.com/", "eid26");
    create("B", &mut b, "ftp://files.example.com/x", "");
    println!("  blocks taken: A {}, B {}", a.ids.blocks, b.ids.blocks);
    println!("code {sale} is ID {}", decode(&sale).unwrap());

    // Ten redirects: the sale link is popular. The cache holds 2 links.
    for code in [&sale, &sale, &news, &sale, &jobs, &sale, &sale, &news, &"zzzzzz".to_string(), &sale] {
        match a.resolve(code) {
            Ok(url) => println!("  GET /{code} -> 302 {url}"),
            Err(e) => println!("  GET /{code} -> 404 ({e})"),
        }
    }
    a.close();
    b.close();
    let c = cache.borrow();
    println!("cache: {} hits, {} misses; database reads: {}", c.hits, c.misses, db.borrow().reads);
    println!("clicks: {sale}={} {news}={} {jobs}={}, dropped {}", a.clicks(&sale), a.clicks(&news), a.clicks(&jobs), a.dropped);
}