Loading...
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
we care about high availability
redirects should be as quick as possible
eventual consistency is fine on the read path
this should be heavily read, not write, optimized
to help with availability, we should be easily horizontally scalable
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
low redirect latency is a requirement
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
POST /shorten
body: {URL: longUrl, expiresAt: time (optional)}
returns
200 with the new, shortened URL
400 when the request is malformed
in the backend, this hashes the original URL and stores the hash and the long url in the db
GET /{hash}
returns
302 with the long URL to automatically redirect
404 when the requested hash doesn't exist in the db
400 for malformed request
in the backend, this uses the primary key of the hash to look up the longer URL in O(1)
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. The CDN also helps us with the NFR for fast redirects, since hitting the cache will be very quick. In a cache miss, it should still be acceptable because the db lookup is O(1) and we can horizontally scale read replicas to match demand
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
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. if there's a hash collision, we should just be able to retry up to 3 times with a different timestamp, and the probabilities say we'll be okay. If key generation fails, we should just be able to use a UUID that's generated from the db. That's guaranteed to be unique and it'll be quick and function identically
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. This covers the TTL
cache misses go to the read replicas, then get put in the cache after they're retrieved. It is a write aside cache and LRU