Loading…
Loading…
Design a URL shortening service like bit.ly. Users submit a long URL and receive a short alias (e.g., short.ly/xK9p2). Clicking the short URL redirects to the original.
Write throughput: 100M URLs/day ≈ 1,160 writes/sec
Read throughput: 10B redirects/day ≈ 116,000 reads/sec → read:write ratio ~100:1
Storage: Average URL = 500 bytes. 100M × 365 × 5 years × 500 bytes ≈ 90 TB over 5 years
Short code length: Base62 with 7 chars → 62^7 ≈ 3.5 trillion unique codes. Enough for centuries.
Client
│
▼
Load Balancer
│
├── Write Service → generates short code → writes to DB + cache
└── Read Service → looks up short code → 301 redirect
│
[Redis Cache] → [Cassandra / DynamoDB]
Key insight: reads vastly outnumber writes. Optimise the read path with an in-memory cache (Redis). The cache is populated on first read and expires with the URL's TTL.
Snowflake ID generator — a widely-used pattern for generating unique, roughly time-sortable IDs without a central coordinator:
64-bit ID layout: [1 unused bit][41-bit timestamp][10-bit machine ID][12-bit sequence]
class SnowflakeIdGenerator {
private final long machineId;
private long lastTimestamp = -1L;
private long sequence = 0L;
SnowflakeIdGenerator(long machineId) { this.machineId = machineId; }
synchronized long nextId() {
long timestamp = System.currentTimeMillis();
if (timestamp == lastTimestamp) {
sequence = (sequence + 1) & 0xFFF; // 12-bit mask
if (sequence == 0) timestamp = waitNextMillis(lastTimestamp); // sequence exhausted this millisecond
} else {
sequence = 0;
}
lastTimestamp = timestamp;
return (timestamp << 22) | (machineId << 12) | sequence;
}
private long waitNextMillis(long last) {
long ts = System.currentTimeMillis();
while (ts <= last) ts = System.currentTimeMillis();
return ts;
}
}
The resulting long ID is then encoded to a short, URL-safe string via Base62 (digits + upper/lowercase letters), which is what actually appears in the shortened URL — Snowflake solves uniqueness without coordination, Base62 solves making a large number look like a short code.
Why not just a random string? A random approach needs a collision check against the database on every generation (an extra read before every write); Snowflake IDs are unique by construction, so no collision-check round-trip is needed at all.
A URL shortener is a common vector for phishing and malware distribution specifically because the short link hides the actual destination from the user until after they've clicked — this is a real abuse case the design must account for, not an edge case. Standard mitigation: check the submitted long URL against a threat-intelligence blocklist (e.g. Google Safe Browsing's API, or a similar third-party feed) SYNCHRONOUSLY at shorten-time before creating the mapping, rejecting known-malicious URLs outright; for URLs not on any blocklist yet, some systems additionally re-check periodically after creation (since a legitimate site can be compromised after a short link to it already exists) and disable the short link retroactively if it's later flagged.
The POST /shorten endpoint (unlike the read-heavy redirect path) needs its own rate limiting (API Rate Limiting Gateway) — without it, the create endpoint is an easy vector for abuse (mass-generating short links for spam campaigns, or exhausting the ID space maliciously, though Snowflake's ID space is large enough that exhaustion isn't realistic). A per-IP and per-account limit on creation, distinct from the redirect endpoint's own (much higher) traffic tolerance, is the standard mitigation.
On each redirect: async-publish a click event { shortCode, timestamp, referrer, userAgent, approxLocation }
to a message queue (Message Queue System) — NEVER synchronously written on the hot
redirect path itself, since that would add latency to every single redirect for a
feature (analytics) that isn't required for the redirect to succeed
Click tracking must be decoupled from the redirect's critical path — the redirect response should be returned to the client immediately, with the click event published asynchronously (fire-and-forget to a queue) for a separate analytics pipeline to consume and aggregate. Synchronously writing an analytics record before returning the 301 would directly violate the sub-10ms p99 redirect latency requirement stated in Requirements, for a feature that has no bearing on whether the redirect itself succeeds.
POST /api/v1/shorten
Body: { longUrl, customAlias?, ttlDays? }
Response: { shortUrl, expiresAt }
GET /{shortCode}
Response: 301 Redirect to longUrl
404 if not found or expired
url_mappings
shortCode VARCHAR(8) PK
longUrl TEXT NOT NULL
userId VARCHAR(36) nullable
createdAt TIMESTAMP
expiresAt TIMESTAMP nullable (null = never expires)
Why Cassandra / DynamoDB? The access pattern is key-value: lookup by shortCode. Wide-column stores are optimised for this and scale horizontally. PostgreSQL works fine at smaller scale.
CREATE TABLE urls (
id BIGINT PRIMARY KEY, -- the Snowflake ID itself
short_code VARCHAR(10) NOT NULL, -- Base62-encoded id
long_url TEXT NOT NULL,
created_at TIMESTAMP NOT NULL,
expires_at TIMESTAMP,
click_count BIGINT DEFAULT 0
);
CREATE UNIQUE INDEX idx_short_code ON urls (short_code); -- the hot read path: lookup by short_code on every redirect
CREATE INDEX idx_expires_at ON urls (expires_at); -- supports a background job cleaning up expired URLs
The unique index on short_code is the single most important index in this schema — it's on the read path for every redirect request, which per the capacity estimation is the overwhelming majority of traffic; without it, every redirect would be a full table scan.
Class-level design for the shortening service:
interface IdGenerator { long nextId(); }
interface UrlRepository { void save(ShortUrl url); Optional<ShortUrl> findByShortCode(String code); }
class UrlShorteningService {
private final IdGenerator idGenerator;
private final UrlRepository repository;
private final Base62Encoder encoder;
ShortUrl shorten(String longUrl, Duration ttl) {
long id = idGenerator.nextId();
String shortCode = encoder.encode(id);
ShortUrl url = new ShortUrl(id, shortCode, longUrl, Instant.now(), Instant.now().plus(ttl));
repository.save(url);
return url;
}
}
IdGenerator and UrlRepository as interfaces (not concrete classes referenced directly) is Dependency Inversion applied directly — UrlShorteningService depends on abstractions, making the Snowflake generator and the specific database swappable without touching this class.
shortCode hash for even distribution