Requirements

Functional Requirements:

Business objects:

Long URLs

short URLs

Relationships:

given a short url, get the corresponding long url

given a long url, generate a short url

URLs are immutable be design, since what we return to them is just the hash of the long url

Non-Functional Requirements:

we care about high availability

redirects should be as quick as possible

eventual consistency is fine

this should be heavily read, not write, optimized

we need to be very careful with security. Someone could for example give us an infinite redirect by linking 2 tiny urls together, which could cost us a lot of money or DOS us. we also could be held responsible for scammers/phishing, but that's out of scope for this

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

DAU, maybe something like 50 million reads and 100k writes per day. Obviously read heavy

50M/86400*5 = we need to handle 2900 reads/s with enough room for some peak load

100k/86400 = 1 writes per second average, aim a little higher for peak loads, maybe 5x again

storage:

writing 100k per day means 36M a year. If we store long url, hash, and expiration time, say that's a kb for ease of calculation, that means 36Mkb or 36GB over the course of a year. Very small, we don't need to worry about sharding or anything probably for awhile

API Design

POST /shorten

body: {URL: longUrl, expiresAt: time (optional)}

returns the new, shortened URL to the user

in the backend, this hashes the original URL and stores the hash and the long url in the db

GET /{hash}

returns the original long URL

we should probably have some way that automatically redirects. I think there's a way to do that. Like we return a 302 or something that tells the browser to go to a different place, which is the long URL

in the backend, this uses the primary key of the hash to look up the longer URL in O(1)

High-Level Design

starting from the back and going forward

we need a nosql database that doesn't need to be sharded right now

we should have some connected microservices, with a large number of read replicas and a few write replicas, mirroring our expected traffic patterns. replicated load balancers direct traffic

in front of those, there should be caches. In fact, even better than that, we should use a CDN. It's highly likely that the url popularity will be regionally distributed. we can relieve a lot of pressure on the DB by having a CDN in front of everything. It should probably be a cache aside, so when there's a cache miss we can put it back in there. And probably least recently used should be evicted from the cache first when it needs to be

Database Design

URL object

ID (primary key) which is just the hash of the long url. This should also be the shard key, and we should use consistent hashing so we don't need to redistribute everything when we add a new node

long url (string)

date created (DATETIME) a nice to have

expiration (DATETIME) the actual time that it expires, instead of just the time to live, which requires calculation. Should be indexed so that we can have a job go through and delete everything that's expired. nullable if someone sets it to be permanent

I'm going to go with NoSQL for this, since eventual consistency is fine and it will scale horizontally better, which is kind of nice. It also gives us flexibility to add more fields later if we want more easily

Detailed Component Design

for key generation, we should use a hash. there might be collisions, which is important to think about. Someone might want to link to the same URL, but with a different TTL. We should, when hashing, add the current unix epoch time to the hash that we generate. The actual hash that we get doesn't really matter, since it'll just look random, and going down to millisecond precision makes it extremely likely we won't have to ever worry about collisions. If there is a collision, we should fail loudly and have the user retry

Security will be interesting. We need to worry about infinite redirects first. As a baseline, we shouldn't allow someone to pass in a tinyurl as the existing short url. Having a CDN also helps, because if someone tries to infinite redirect, they'll just be hitting the CDN and not our actual servers. If someone is able to cache bust though, we should have IP based rate limiting at a minimum in place

for the cleanup job, we can probably use a built in function of whatever nosql database we use, instead of relying on a cron