Loading...
17 million URLs per day
~20 GB of URLs per day
~4 TB storage
create(long_url)
POST: domain.com/api/create
body: {url=long_url}
Return 200 OK with shortened URL in body
read(short_url)
GET: domain.com/{short_url}
body: none
Return redirect response to the long URL
If not found, return 404 error. We may return a 404 immediately after a read due to lack of consistency, which is acceptable.
We can use a single NoSQL database for this for better scalability and latency, as we don't need ACID guarantees. This is a read heavy workload, so data replication is important to manage all read requests.
Schema:
shortened url - string
long url - string
creation time - datetime
URL readers and creators both hit a load balancer which hit web servers. We have our NoSQL database that stores our URLs with the schema mentioned previously. This database In front of this database is a write-through cache and then a load balancer. We also have a daily chron job that reads through the db and removes URLs older than 6 months.
Creation: Hit load balancer, then go to web server. The web server turns the long URL into a shortened URL using random characters. It then checks the database to see if this URL is used or not (with base 62 encoding this is a rare but possible occurence with 8 characters). If this URL has not been used before, write to cache and database. Database is sharded on short URL. Write to one database and it will replicate on other duplicates of that shard over time (not consistent, but this is fine for our use case)
Read: Hit load balancer, then hit cache. If not in cache, hit database load balancer then hit a replica in the proper shard of the database.
Delete: as mentioned earlier, this is a chron job. This reads through the entire DB (only around 4 TB * ~ 4 replication), so this isn't too expensive. It deletes anything from the DB that is too old. This job is ran every day during quiet hours.
Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...
Cache can use LRU for eviction. We evict the last used URL from the cache.
The database is interesting. This is a very read heavy workload, and only needs to be written once and never updated. Also, there is no need for relational system. We choose NoSQL database for lower latency and better scalability.
We choose NoSQL over relational as we are using scalability and latency over ACID guarantees. It is okay for writes to be eventually consistent in our use case, so we use an asynchronous replication strategy.
We can use MongoDB for a specific choice. Our database is very read heavy, which makes it a smart decision. We can also adjust the schema later with this.
For our cache choice, we can use memcache for its simplicity and faster usage. There is no need for more complex cache options like redis, as we just need simple key value cache.
There can be issues overloading the database with reads, which is our biggest bottleneck. If one link is extremely popular, it can overload the cache shard. Load balancers are also single point of failures, which can be resolved by using multiple load balancers with failover mechanisms.
There is also a possibility of DDOS on the creation API, as it is currently open without any limiting.
We should improve latency by creating database replicas in multiple geographic locations. This requires many more servers and complex data replication strategies.
Another thing is to limit users from making too many requests by using rate limiting + authentication. This adds more systems to the architecture but prevents people from overloading our database with writes.