- Published on
Co nieco o System Designie - projektujemy URL Shortener
- Authors
- Name
- Piotr Kołodziejczyk
URL Shortener to jeden z tych problemów, które na pierwszy rzut oka wyglądają trywialnie. Wziąć długi link, zwrócić krótki. Tyle. A jednak bit.ly obsługuje miliardy kliknięć miesięcznie, ma analitykę, georouting i nie pada. Jak to działa pod spodem?
Wymagania
Funkcjonalne:
- Podajesz długi URL → dostajesz krótki (np.
shortly.pl/aB3xK2) - Wchodzisz na krótki URL → redirect do oryginalnego
- Opcjonalnie: własny alias (
shortly.pl/moja-firma) - Opcjonalnie: wygaśnięcie linku po czasie
Niefunkcjonalne:
- Redirect musi być szybki - poniżej 10ms (użytkownik tego nie czuje, ale SEO i UX tak)
- Write heavy? Nie. Stosunek odczytów do zapisów ≈ 100:1. Znacznie więcej kliknięć niż tworzonych linków
- Trwałość - raz stworzony link nie może zniknąć bez powodu
- Dostępność 99.9%
Szacunki
Tworzenie linków: 100 000 / dzień = ~1.2 req/s
Przekierowania: 10 000 000 / dzień = ~115 req/s
peak ×10 = ~1 150 req/s
Rozmiar rekordu: ~500 bajtów (short_code + long_url + metadata)
Storage / rok: 100 000 × 365 × 500 B ≈ 18 GB
Storage / 10 lat: ~180 GB
Storage jest śmieszny mały. Problem nie jest w dysku - jest w latencji przekierowania.
Base62 - skąd się bierze krótki kod
Tu jest serce systemu. Krótki URL to nic innego jak zakodowany identyfikator.
Mamy do dyspozycji znaki URL-safe bez cudzysłowów i znaków specjalnych:
0-9 → 10 znaków
a-z → 26 znaków
A-Z → 26 znaków
= 62 znaki łącznie → Base62
Ile unikalnych URLi zmieści się w N znakach?
1 znak: 62^1 = 62
2 znaki: 62^2 = 3 844
3 znaki: 62^3 = 238 328
4 znaki: 62^4 = 14 776 336
5 znaki: 62^5 = 916 132 832 (~916 milionów)
6 znaki: 62^6 = 56 800 235 584 (~56 miliardów)
7 znaki: 62^7 = 3 521 614 606 208 (~3.5 biliona)
6 znaków = 56 miliardów unikalnych URLi. Bit.ly ma ~40 miliardów linków. 6 znaków wystarcza.
Konwersja ID → Base62
Każdy rekord w bazie dostaje auto-inkrementujące się id (liczba całkowita). Żeby zamienić id na krótki kod, robimy konwersję systemu liczbowego - dokładnie tak jak z binarnego na heksadecymalny, tylko podstawa to 62.
ALPHABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
def encode(num: int) -> str:
if num == 0:
return ALPHABET[0]
result = []
while num:
result.append(ALPHABET[num % 62])
num //= 62
return ''.join(reversed(result))
def decode(code: str) -> int:
result = 0
for char in code:
result = result * 62 + ALPHABET.index(char)
return result
encode(1) → "1"
encode(62) → "10"
encode(12345678) → "FpSK"
encode(56800235583) → "zzzzzz" (max 6-znakowy)
Konwersja jest deterministyczna - ten sam id zawsze daje ten sam kod. Brak kolizji.
Dwa podejścia do generowania kodu
1. Auto-increment ID + Base62 (zalecane)
Baza danych generuje sekwencyjne id, kodujemy do Base62.
INSERT INTO urls (long_url, created_at) VALUES (?, ?)
RETURNING id → 12345678
encode(12345678) → "FpSK"
short_url = "shortly.pl/FpSK"
Zalety: zero kolizji, przewidywalna długość kodu, prosta implementacja.
Wada: kody są sekwencyjne - można enumerować URLe (FpSK, FpSL, FpSM...). Dla większości zastosowań to nie problem, ale jeśli linki mają być "nieprzegadywalne" - słabo.
2. Hash (MD5/SHA256) + przycinanie
Hashujesz długi URL, bierzesz pierwsze 6-7 znaków z Base62.
import hashlib, base64
def hash_url(long_url: str) -> str:
h = hashlib.md5(long_url.encode()).digest()
encoded = base64.b62encode(h) # lub własna implementacja
return encoded[:6]
Problem: kolizje. Dwa różne URLe mogą dać ten sam 6-znakowy prefiks. Trzeba sprawdzać w bazie i przy kolizji - co? Appendować sól i hashować ponownie, iteracyjnie.
hash("https://google.com")[:6] → "aB3xK2"
hash("https://youtube.com")[:6] → "aB3xK2" ← kolizja!
hash("https://youtube.com" + "1")[:6] → "mK9pLx" ← retry z solą
Przy małej skali kolizje są rzadkie, ale przy setkach milionów URLi zaczyna to boleć. Auto-increment jest prostsze i bezpieczniejsze.
Przepływ tworzenia linku
Klient API Server DB (PostgreSQL) Cache (Redis)
│ │ │ │
│── POST /shorten ────────▶│ │ │
│ { url: "https://..." } │ │ │
│ │── INSERT long_url ───▶│ │
│ │◀── id: 12345678 ──────│ │
│ │ │ │
│ │ encode(12345678) = "FpSK" │
│ │ │ │
│ │── SET FpSK → long_url ────────────────────▶│
│ │ (TTL: 24h) │ │
│◀── { short: "/FpSK" } ───│ │ │
Przepływ przekierowania - tu liczy się każda milisekunda
Klient CDN (CloudFront) API Server Redis PostgreSQL
│ │ │ │ │
│── GET /FpSK ──────▶│ │ │ │
│ │ (cache miss) │ │ │
│ │── GET /FpSK ─────▶│ │ │
│ │ │── GET FpSK ─▶│ │
│ │ │◀── long_url ─│ │
│ │ │ (hit ~1ms) │ │
│ │◀── 301/302 ───────│ │ │
│ │ Location: long_url │ │
│◀── 301/302 ────────│ │ │ │
Jeśli Redis ma rekord (cache hit) - baza danych w ogóle nie jest odpytywana. Latencja Redis ~0.5ms, cały redirect < 5ms.
Jeśli Redis nie ma (cache miss) - idziemy do PostgreSQL, ładujemy do cache, zwracamy. Pierwsze trafienie wolniejsze, każde kolejne szybkie.
301 vs 302 - ważna różnica
| 301 Permanent | 302 Temporary | |
|---|---|---|
| Przeglądarka cache'uje | Tak - na zawsze | Nie |
| Kolejne kliknięcia | Bezpośrednio do celu (omija serwer) | Zawsze przez serwer |
| Analityka kliknięć | Traci po pierwszym | Każde kliknięcie zliczane |
| Obciążenie serwera | Minimalne | Większe |
Jeśli chcesz zliczać kliknięcia → 302. Jeśli nie zależy ci na analityce → 301.
Architektura na AWS
┌─────────────────────────────────────────┐
│ AWS Cloud │
│ │
Klienci ─────────▶│ CloudFront (CDN) │
│ │ │
│ ▼ │
│ ALB (Load Balancer) │
│ │ │
│ ▼ │
│ ECS / Lambda │
│ (API: shorten + redirect) │
│ │ │ │
│ ▼ ▼ │
│ ElastiCache PostgreSQL │
│ (Redis) (RDS) │
│ hot cache source of truth │
└─────────────────────────────────────────┘
PostgreSQL zamiast DynamoDB - tym razem mamy relacyjne dane z auto-increment ID. Sekwencja w PostgreSQL jest atomowa i bezpieczna dla concurrent writes. Przy tej skali (18 GB / rok) PostgreSQL na RDS to overkill w dobrym sensie - znany, sprawdzony, tanie backupy.
Lambda zamiast ECS - operacje są bezstanowe i krótkie (< 100ms). Lambda idealnie pasuje, skaluje do zera w nocy.
CloudFront przed wszystkim - przekierowania można cache'ować na poziomie CDN. Kliknięcie w popularny link? CloudFront odpowiada z edge, serwer w ogóle nie widzi requestu.
Custom aliasy i wygasanie
Custom alias (shortly.pl/moja-firma):
ALTER TABLE urls ADD COLUMN custom_alias VARCHAR(50) UNIQUE;
Przy tworzeniu sprawdzamy czy alias jest wolny, jeśli zajęty - błąd 409. Priorytet przy lookupie: najpierw custom_alias, potem short_code.
Wygasanie linku:
ALTER TABLE urls ADD COLUMN expires_at TIMESTAMP;
Przy przekierowaniu sprawdzamy expires_at < NOW() → 410 Gone. Osobny cron (Lambda Event Bridge) czyści stare rekordy co dobę.
Co z enumeracją? (bezpieczeństwo)
Sekwencyjne kody (FpSK, FpSL, FpSM) można iterować i zbierać wszystkie URLe z systemu. Jeśli to problem:
- Losowy salt przy encode - do ID dodajesz losową stałą przed kodowaniem (salt trzymasz w konfiguracji, nie w DB)
- Hashids - biblioteka która "szyfruje" liczby całkowite na nieprzewidywalne stringi, deterministycznie
from hashids import Hashids
h = Hashids(salt="twoj-sekret", min_length=6)
h.encode(12345678) # "kRHp5X" - nieprzewidywalne
h.decode("kRHp5X") # [12345678]
Brak kolizji, brak sekwencyjności, nadal deterministyczne.
Kluczowe wnioski
- Base62 daje 56 miliardów unikalnych URLi w 6 znakach - więcej niż wystarczy
- Auto-increment + Base62 to prostsze i bezpieczniejsze niż hashowanie z obsługą kolizji
- Redis przed bazą danych - przekierowania muszą być szybkie, cache jest obowiązkowy
- 302 jeśli liczysz kliknięcia, 301 jeśli nie - różnica ma znaczenie
- PostgreSQL wystarcza - problem nie jest w skali zapisu, tylko w latencji odczytu