Design a URL Shortener

Problem এর পরিচয়

URL shortener হলো HLD এর চিরচেনা প্রথম problem, কারণ product টা এক বাক্যে বলা যায়, অথচ high-level design এর প্রায় সব মূল idea এখানে আসে: আগে আন্দাজ, তারপর খেয়াল করা যে read write এর একশো গুণ, কোনো bottleneck ছাড়া unique ID বানানো, যেখানে traffic সেখানে cache বসানো, আর ধীর কাজ (analytics) গরম পথ থেকে সরিয়ে রাখা। এটা ঠিকঠাক বুঝলে বেশিরভাগ read-heavy system চেনা চেনা লাগবে।

Problem statement

ঢাকার একটা courier company প্রতিটা parcel এর সাথে একটা SMS পাঠায়: "Track your parcel: https://track.example.com/orders/2026/11/08/BD-7781-55210-DHK?lang=bn&utm_source=sms"। এত long link SMS এর অক্ষর খেয়ে ফেলে (প্রতিটা বাড়তি SMS এ টাকা লাগে), আর সস্তা phone এ প্রায়ই দুই লাইনে ভেঙে গিয়ে কাজই করে না। Shortener থাকলে SMS এ লেখা থাকে "sho.rt/15FTGg", আর link টা তবুও পুরো page খোলে।

কী বানাচ্ছি: এমন একটা service যেটা একটা long URL কে একটা ছোট code বানায়, আর ছোট link খুললে যে কাউকে long URL এ পাঠিয়ে দেয়, দ্রুত, বছরের পর বছর।

কে ব্যবহার করে: business আর marketer রা link বানায় (অল্প write), আর সাধারণ মানুষ সেগুলো click করে (প্রচুর read, সারা দুনিয়া থেকে, প্রায়ই slow mobile network এ)।

কী সমস্যা মেটায়: এমন link যেটা একটা SMS, tweet বা QR code এ ধরে; একটা campaign link কোথায় যাবে সেটা বদলানোর একটা জায়গা; আর link বানানো মানুষদের জন্য click এর হিসাব।

Technically কোথায় মজা: একটা code কখনো দুইটা URL দেখাতে পারবে না, তাই অনেক server জুড়ে code unique হতে হবে; redirect হলো user এর অপেক্ষার পথে, তাই শত কোটি link থাকলেও millisecond এ হতে হবে; click গুনতে হবে redirect কে slow না করে; আর খোলা একটা "link বানাও" box spammer আর phisher দের টানে।

Requirement

Functional requirement

1. Create: একটা long URL (http বা https) দিলে একটা ছোট code ফেরত দাও। চাইলে একটা custom alias ("eid26") নাও, যদি সেটা ফাঁকা থাকে।
2. Redirect: sho.rt/<code> খুললে long URL এ redirect। অচেনা code এ 404।
3. Click গোনা: প্রতিটা redirect এ একটা click রেকর্ড করো; link এর মালিক মোট সংখ্যা দেখতে পারবে (কয়েক মিনিট দেরি চলবে)।
4. Default এ link expire হয় না (optional expiry তারিখ থাকলে ভালো)।
5. এই design এর scope এর বাইরে: user account আর dashboard, link এর গন্তব্য edit করা, link preview।

Non-functional requirement

Redirect এর latency, availability আর uniqueness, এই তিনটাই design এর আকৃতি ঠিক করে। Write এর throughput সামান্য; read এর throughput সামান্য না।

Capacity আন্দাজ

ধরে নেওয়া (মুখে বলা, গোল সংখ্যা):

• মাসে 10 কোটি নতুন link।
• প্রতিটা link জীবনে মোটামুটি 100 বার খোলা হয়, তাই read write এর 100 গুণ।
• একটা রাখা link (code, long URL, owner, তৈরির সময়) মোটামুটি 500 byte।
• Link 5 বছর রাখা হয়; storage 3 বার replicate হয়।
• সবচেয়ে ব্যস্ত ঘণ্টা গড়ের মোটামুটি 3 গুণ।

Traffic

Storage

Bandwidth: একটা redirect এর response খুব ছোট (কয়েকশো byte এর header)। 12,000 / s × 500 B ≈ peak এ সেকেন্ডে 6 MB বাইরে যায়। Network চিন্তার বিষয় না।

Cache এর size: traffic খুব অসমান: কয়েকটা campaign link বেশিরভাগ click পায়। গত মাসে বানানো link এর উপরের 20% (2 কোটি) যদি 80% read পায়, ওগুলো cache করতে লাগে 2 কোটি × 500 B ≈ 10 GB, যেটা একটা Redis node এর memory তে আরামে ধরে।

Code এর দৈর্ঘ্য: 6টা base62 অক্ষরে হয় 62⁶ ≈ 5,680 কোটি code; 7টায় 3.5 লাখ কোটি। 600 কোটি link ছয় অক্ষরে অনেক জায়গা রেখেই ধরে; ID শুরু করব 1,000,000,000 থেকে, যাতে প্রথম দিন থেকেই code একই দৈর্ঘ্যের দেখায় (প্রায় 5,600 কোটি পর্যন্ত 6 অক্ষর)।

সংখ্যা কী বলছে: read write কে 100 এ 1 এ হারায় আর data ছোট। কঠিন অংশ storage না, সেকেন্ডে 12,000 lookup millisecond এ উত্তর দেওয়া। তাই: database এর সামনে একটা cache, read replica, আর redirect এর পথে ধীর কিছু না।

API design

• Authentication: link বানাতে আর stats পড়তে API key (বা login করা session) লাগে, যাতে প্রতি client rate limit দেওয়া যায় আর অপব্যবহার কার সেটা বোঝা যায়। Redirect public আর নামহীন।
• Idempotency: POST /v1/links একটা Idempotency-Key নেয়; timeout এর পরে retry করা request দ্বিতীয় link না পেয়ে একই code ফেরত পায়। (একই URL এর জন্য দুইটা code ক্ষতিকর না, কিন্তু ID নষ্ট করে আর stats গুলিয়ে দেয়।)
• GET /{code} root এ কেন: short link যত ছোট হয় তত ভালো; sho.rt/15FTGg, sho.rt/r/15FTGg এর চেয়ে ভালো।
• Default এ 302, 301 না: 301 browser চিরকাল cache করে, তাই বারবার visit আমাদের কাছে আসেই না, এতে load বাঁচে কিন্তু click এর হিসাব হারায়, আর ভুল গন্তব্য ঠিক করা অসম্ভব হয়ে যায়। 301 শুধু সেই link এ যেগুলো কখনো বদলাবে না আর যাদের click গুরুত্বপূর্ণ না।

Database design

Access pattern: একটা table, সবসময় তার key (code) দিয়ে খোঁজা, একবার লেখা আর বহুবার পড়া, গরম পথে কোনো join নেই। এটা key-value ধরনের pattern।

বাছাই: শুরু করো PostgreSQL (বা MySQL) দিয়ে। সেকেন্ডে 120 write আর পাঁচ বছরে 9 TB তে read replica সহ একটা primary অনেকদিন সামলায়, আর SQL দেয় constraint (unique code), ID allocator এর জন্য transaction, আর সহজ report। Key-value store (DynamoDB, Cassandra) আকর্ষণীয় হয় যখন region জুড়ে হাত না লাগিয়ে horizontal scaling চাও; এটা ভালো বিকল্প, required না।

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: redirect এর lookup একটা primary-key read, আর database নিজেই "একটা code কখনো দুইটা URL দেখাবে না" নিশ্চিত করে (আগে থেকে থাকা alias insert করতে গেলে fail করে)।
• গরম পথে কোনো foreign key নেই: owner_id accounts table কে দেখায়, কিন্তু redirect এ আমরা join করি না।
• Replication: write এর জন্য একটা primary, read এর জন্য দুই বা বেশি async replica। তৈরির ঠিক পরের read-after-write সামলানো হয় primary থেকে নতুন code ফেরত দিয়ে আর cache এ সেটা রেখে দিয়ে।
• পরে partitioning: link একটা primary ছাড়িয়ে গেলে code ধরে shard করো (code এর hash, consistent hashing বা fixed কয়টা logical partition)। তখন প্রতিটা redirect ঠিক একটা shard ছোঁয়।
• Click: links database এ সেকেন্ডে 12,000টা insert দিলে write ই bottleneck হয়ে যেত। তার বদলে click যায় একটা queue দিয়ে গোনার জন্য বানানো একটা store এ (time-series বা columnar store, বা জমানো counter)।

Architecture এর ছবি

যা জেনেবুঝে রাখিনি: microservices (একটা service ই create আর redirect দুইটা করে), প্রথম দিন থেকে Kafka (এই সংখ্যায় একটা managed queue বা Redis Streams যথেষ্ট), বা একাধিক region (যতক্ষণ না availability বা latency র লক্ষ্য সেটা চায়)।

একটা request এর জীবন

একটা link বানানো

1. Client → LB → app: URL আর একটা API key সহ POST /v1/links।
2. App API key, rate limit, URL এর format (http/https, সর্বোচ্চ 2,048 অক্ষর), আর জানা ক্ষতিকর domain এর blocklist check করে।
3. App নিজের local block থেকে পরের ID নেয়। প্রতি 1,000টা link এ মাত্র একবার নতুন block নিতে database ছোঁয়।
4. App ID টা base 62 এ encode করে (code, url, owner) primary তে insert করে। Primary key uniqueness নিশ্চিত করে।
5. App নতুন জোড়াটা Redis এ লেখে (যাতে প্রথম click গুলো miss না হয়) আর short URL সহ 201 ফেরত দেয়।

একটা short link খোলা (cache miss, তারপর hit)

1. Browser → DNS → LB → যেকোনো app server: GET /15FTGg।
2. App Redis এর কাছে code:15FTGg চায়। Hit হলে: ধাপ 5 এ যাও।
3. Miss: app primary key দিয়ে replica পড়ে (কয়েক millisecond)।
4. App জোড়াটা একটা TTL দিয়ে Redis এ লেখে (একদিন, ব্যবহারে নতুন হয়), তাই পরের request hit।
5. App অপেক্ষা না করে click 15FTGg queue তে দেয়; queue ভরা থাকলে click টা বাদ পড়ে, redirect না।
6. App উত্তর দেয় 302 Location: <long URL>। Browser আসল page এ চলে যায়।

Component গুলো গভীরে

Unique code বানানো

তিনটা চেনা উপায়:

Counter bottleneck হয় শুধু যদি প্রতিটা link database এর কাছে পরের সংখ্যা চায়। তাই প্রতিটা app server একটা UPDATE ... RETURNING দিয়ে ID এর একটা block (এখানে 1,000) নিজের করে নেয়, তারপর memory থেকে দেয়। কোনো server crash করলে তার block এর বাকিটা নষ্ট হয়, তাতে ক্ষতি নেই: আমাদের 5,600 কোটি ছয় অক্ষরের code আছে।

Code আন্দাজ করা যাওয়া যদি সমস্যা হয় (কেউ সব link এক এক করে ঘুরে দেখতে পারে), encode এর আগে ID টাকে একটা উল্টানো যায় এমন এলোমেলো করার ধাপের মধ্য দিয়ে পাঠাও (ছোট একটা Feistel network এর মতো key দেওয়া permutation)। Unique থাকে, আর তবুও কোনো lookup লাগে না।

Redirect cache করা

TTL সহ cache-aside: Redis পড়ো, miss হলে একটা replica পড়ে Redis ভরো। আমাদের requirement এ link এর গন্তব্য কখনো বদলায় না, তাই edit এ cache invalidate করার দরকার নেই; TTL শুধু সেই link গুলোর জন্য memory রাখে যেগুলো জনপ্রিয় থাকে। Expiry বা edit এর feature থাকলে link বদলানোর সময় key মুছে দিতাম। গরম link (TV বিজ্ঞাপনের একটা campaign) ছোট cache time দিয়ে CDN edge থেকে serve করা যায়, তাতে সেই traffic এর বেশিরভাগ আমাদের load balancer ও দেখে না।

Redirect slow না করে click গোনা

Redirect একটা ছোট event (code, সময়, হয়তো দেশ আর device) একটা queue তে দিয়ে ফেরত আসে। একটা worker queue পড়ে একটা analytics store এ প্রতি code, প্রতি মিনিটের counter এ যোগ করে। Queue ভরা থাকলে user কে দেরি না করিয়ে click টাই বাদ দিই: আন্দাজের হিসাব মেনে নেওয়া যায়, slow redirect না। টেকসই queue হলে worker restart এও click টিকে থাকে; worker কে idempotent হতে হবে (প্রতিটা event ID একবারই গোনো), কারণ queue at least once দেয়।

চালিয়ে দেখার মতো core

এই program টাই design এর হৃদয়, এক বসায় পড়ে ফেলার মতো ছোট: base62 encoding, একটা allocator যেটা ID এর block দেয়, প্রতি server এ ID এর উৎস, Redis এর জায়গায় একটা LRU cache, PostgreSQL এর জায়গায় একটা database map, আর একটা service যেটা link বানায় আর cache-aside আর asynchronous click queue দিয়ে redirect খোঁজে। দুইটা "app server" একটা database, একটা cache আর একটা allocator share করে।

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())
}

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

Output টা পড়ো:

• Code: A পেয়েছে 1,000,000,000 থেকে শুরু হওয়া block আর B পরেরটা, তাই A এর link 15FTGg, 15FTGh আর B এর 15FTWo। প্রতিটা server তার link গুলোর জন্য ঠিক একটা block নিয়েছে: প্রতি 1,000 link এ allocator এ একবার যাওয়া।
• Alias: প্রথমবার eid26 ফাঁকা ছিল; দ্বিতীয়বার চাইলে "alias already taken" দিয়ে fail করে, primary-key insert এটা নিশ্চিত করে। ftp:// link টা কোনো ID খরচ করার আগেই বাতিল।
• Decode: 15FTGg আবার ID 1,000,000,000 এ ফিরে যায়, তাই কোনো lookup ছাড়াই একটা code কোন shard এর সেটা বের করা যায়।
• Redirect: cache এ মাত্র 2টা link ধরে, তবু জনপ্রিয় sale link টা ভেতরে থেকে যায়। 10টা lookup এর 5টা cache hit; 5টা miss এর মধ্যে আছে প্রতিটা link এর প্রথম দেখা, jobs link news কে বের করে দেওয়ার পর news আবার পড়া, আর অচেনা code টা। শুধু miss গুলোই database এ পৌঁছেছে। (Demo create এর সময় cache গরম করে না, যাতে প্রথম miss টা দেখা যায়; production করে, উপরের lifecycle এর মতো।)
• Click: 6, 2 আর 1, background worker গুনেছে redirect গুলোর উত্তর দেওয়ার পরে; queue কখনো ভরেনি বলে কিছুই বাদ পড়েনি।

Test গুলো সবচেয়ে জরুরি জিনিসগুলো দেখে: base62 এর round trip, 4টা server একসাথে 2,400 link বানালেও কোনো duplicate code নেই (-race দিয়ে চালানো), cache করা link database একবারই পড়ে, check আর alias এর error, আর ভরা click queue redirect আটকে না দিয়ে click বাদ দেয়।

// 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]

একই core আরো পাঁচটা language এ

একই class আর একই output সহ single-threaded version। close() call করলে click এর "worker" চলে, design দেখাতে এটুকুই যথেষ্ট; Go version এটা একসাথে (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);
}