URL shortener and Pastebin

A URL shortener turns a long address into a short key and redirects whoever opens it. Pastebin stores a block of text and returns a short link to it. They look different, but both map a short key to stored content, both read far more than they write, and both need unique keys that never collide. We design the shortener fully, then show exactly what changes for Pastebin.

Functional: create a short link from a long URL, redirect a short link to its long URL, optionally choose a custom alias, optionally set an expiry (default several years).

Non-functional: redirects must be fast and highly available, since a broken link is a broken product. Keys must be hard to guess, so people cannot browse everyone else's links. Writes can be slightly slower than reads.

Using the numbers from the estimation lesson: 500 million new links per month is about 200 writes per second. With reads 100 times as many, that is about 20,000 redirects per second. Five years of links is 30 billion records at about 500 bytes each, so around 15 TB. Reads are about 10 MB per second of bandwidth, which is small. The hot 20 percent of daily reads needs about 170 GB of cache.

POST /links    { url, alias?, expiresAt? }  ->  201 { shortUrl }
GET  /{key}                                   ->  302 Location: long URL
DELETE /links/{key}                           ->  204

A 302 (temporary) redirect makes the browser ask us every time, so we can count clicks and honor expiry. A 301 (permanent) lets the browser cache it forever, which saves load but hides all later visits from us. Choose 302 when analytics or expiry matter.

The main record is small: key (primary key), long URL, created time, expiry time, owner. There are no joins, billions of rows, and every read is a lookup by key. That suits a key value or wide column store, with a small relational table for users.

Keys of seven characters from 62 symbols (a to z, A to Z, 0 to 9) give 62 to the power 7, about 3.5 trillion combinations, far more than our 30 billion links. Six characters give about 56 billion, which also fits. How do we produce unique keys?

Option 1: hash and truncate. Hash the long URL (for example with MD5), encode it in base 62, and keep the first seven characters. It needs no coordination, but truncation makes collisions possible, and the same URL submitted by two people gives the same key. You must check the database and retry on a collision, for example by adding a counter to the input.

Option 2: a counter. Hand out 1, 2, 3 and so on, encoded in base 62. There are no collisions, but a single counter is a bottleneck and a single point of failure, and sequential keys are easy to guess.

Option 3: a key generation service. Pre-generate random unique keys offline and store them in a table of unused keys. When a server needs keys, it takes a batch, say a thousand, and the service moves them to a used table so nobody receives them twice. App servers then create links from their local batch with no database lookup and no collision check. If a server dies, its unused keys are lost, which is acceptable because the space is huge. Run a standby copy of the service so it is not a single point of failure.

Option 3 is the usual choice for this scale: fast, collision free, and unguessable because the keys are random.

Redirects dominate, and a few links are very popular. A cache in front of the database serves most of them from memory. Use least-recently-used eviction and size it from the 80/20 rule. A cached entry carries the expiry, so an expired link is not served from stale memory. On a miss, read the database, then fill the cache.

• Sharding: partition by a hash of the key, using consistent hashing so adding a shard moves few keys. Sharding by hash of key spreads load far better than by user.
• Replication: keep several copies of each shard. Redirects can read from any replica, and a replica can be promoted if the primary dies.
• Load balancing: put balancers between clients and app servers, and between app servers and the cache or database tiers if needed.
• Consistency: a brand new link may briefly be missing on a replica, which is acceptable. Key allocation, by contrast, must never hand one key to two URLs.

Do not scan the whole database for expired links. Use two cheap mechanisms. Lazy deletion: when a request finds an expired link, return not found and delete it then. Background cleanup: a low priority job removes expired rows in small batches at quiet times, returning their keys to the pool. Both keep the hot path fast.

Count clicks by emitting an event for each redirect to a queue, and aggregate it elsewhere, so analytics never slows a redirect. Protect the service with rate limiting per client for link creation, validate URLs and block known malicious targets, and let private links require permission. Random keys, not sequential ones, stop enumeration.

Pastebin stores text, not a short string, so the content is large and variable.

• A paste may be up to a few megabytes, so limit its size.
• Say 1 million new pastes a day averaging 10 KB. That is about 12 writes per second, 10 GB per day, 3.65 TB per year, and about 18 TB over five years. Reads are perhaps five times writes, about 60 per second, far fewer than the shortener.
• Store the content in an object store (cheap, durable, made for blobs) and keep only the metadata in the database: key, object location, expiry, owner. The database stays small and fast.
• Keys come from the same key generation service.
• Expiry, caching of popular pastes, and cleanup work exactly the same way, except cleanup also deletes the object.
• Serve content through a CDN if pastes are widely read.

The lesson is reuse: the same key service, cache, sharding and expiry machinery fit both products, and only the payload changes from a short string to a blob in object storage.

• The key service must be replicated, and servers need enough local keys to survive its brief outage.
• A viral link is a hot key. The cache absorbs it, and a very hot key can be copied to several cache nodes.
• Cache outage sends everything to the database, so protect the database with rate limits and warm the cache gradually.