Loading...
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
Let's assume we receive 1 URL submission every second, so that's 86.4k per day, 1 write per second
Assuming that some users share their shortened URLs over the internet and some totally forget about theirs, a read to write ratio of 10 seems reasonable, 10 reads per second
I do not know much about bandwidths and how much each request takes and what the size depends on so I'm assuming 10KB for each redirect so 864KB per day
Storage is 86.4k * 500 bytes each = 43.2MB/day
Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...
Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.
Client -> DNS -> Load balancer/proxy -> server -> cache -> database
This will also get sent to CDN for faster responses, additionally we'll also implement an internal cache for the URLs most frequently used
Our data format will stay the same and we also need accurate results so a SQL database seems like a good option
Although NoSQL databases are better for scalability but we scale our SQL database like many companies do with Postgres
Server will handle all the logic regarding short URL generation and redirection, cache/database fetching, receiving requests
The proxy will distribute the requests between multiple servers if needed and shield our internal IPs from attackers
For URL generation we can use hash of the URL received and store it in our DB, to avoid duplication we can set a salt value and also save it in the DB or incorporate the current time to make the hash unqiue, so whenever we receive a URL redirect we can just check our DB for mapping, all that matters is that our DB should have the mapping and short URLs to be unique. A simple table of key value pair suffices as well
A separate server for write queries and a faster one for the read queries is the optimal solution, we don't have to worry about DB consistency either as only one server writes
Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...
For URL generation, I would choose the strategy of random 7 chars
So the DB rows will be 'url_id, short_url, long_url, created_at, expires_at'
no real use of id
SQL is better because the format is not bound to change and scaling will not be an issue either, NoSQL is better for scaling but SQL suffices. We also need accurate results
user table will be 'user_id, url_id'
event table will be 'url_id, clicks, visits'
user to url is one to many
select long_url from urls where short_url is
insert into urls (url_id, short_url, long_url)
for dashboard, select url_id from users where user_id is
url_id and short_url should be indexed
if there is no expiry on urls then sql is better otherwise nosql as we might have to scale dbs, and horizontal scaling is way better in nosql, also write wait for some time is acceptable
we'll shard according to hash of short_urls
no duplicate logic is way easier in sql but achievable in nosql
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
shortener service:
user logs in and inputs a long url, hits submit
we make up random 7 characters, if already present in DB which is rare we try again
this is our new short url as prefix to some base url of our shortener service
we insert it into db
redirect service:
user tries to go to a url whose base is our shortener service
we extract the short_code out of it, and try to check in db if it exists
for db we make a hash of the short code (predefined hashing mechanism), by looking at the initials of hash we figure out which shard of db to check
before checking in that shard we try its cache, if it doesnt exist (cache miss) we then try the sahrd
if it doesnt exist in that shard we give 404, else we execute our query
select long_url from urls where short_url is extracted_code
then we redirect user to that long_url instead
if we're using a db like dynamo then the entries will auto delete, we'll also make sure that they're evicted from respective shard caches as well
we'll also introduce rate limiting to IP, 4-5 per minute
if a shard is unavailable we already have a master slave architecture in place, the backup shard will become the main shard till the unavailable one is fixed
if the cache goes down then we'll directly use the shard instead
each shard will have a cache so responses are quicker, cache are fast so they'll be checked before shards
there was no reason to pick random 7 chars over base62, any hashing will do its work as we're maintaining a db anyway
if base62 is predictable, we can a secret value, but secret might be leaked