Loading...
Generate a short link for a URL
Retrieve the long link using the short link
Generating custom links
Important aspects:
Handling link colisions
Length of the short url
Short_url generation algorithm - base 62 encoding
High availability - 100 M DAU
Availability over consistency
Response time:
- 1 sec for generating URL
-10 ms for redirecting to long url
100 M DAU users
Let's assume 100 M URL read request
and 10 M URL generation requests
10 M * 365 = 4 B per year
read requests = 100 M /24*60*60 = 1 k/s
write requests = 100/s
We should also consider potential spikes in usage e.g.
cater for spikes of 10 times average load so 10k/s for read requests and 1k/s for write requests
base 62 encoding - letters a-zA-Z0-9
Database:
short_url - varchar(100) - 100 bytes
long_url - varchar (max) - 200 bytes
id - bigint - 8 bytes
userId - bigint - 8 bytes
creation date - datetime - 8 bytes
324 bytes * 4B = 1200 B = 1.2 TB per year
if we implement expiry policy for short_urls then we will need less space
POST /api/v1/shorten
body
{
"long_url": "http://test.com?verylongurl"
}
returns JSON
{
"short_url": "http://short",
"long_url": "http://test.com?verylongurl",
"creation_time":
"expiration_time":
}
we should introduce validation of the long_url parameter
rate limiting will help prevent system from overloading if there is request spikes
GET /api/v1/redirect/
400 bad requests
404 not found
429 too many requests
Authentication implemented using OAuth, user token will be passed in header for security, not in request body
URL Mapping table
id
user_id
short_url
long_url
creation_time
add index on short_url & user_id
User table
user_id
user_name
user_email
We can use either SQL or NoSQL database for storing mapping, however NoSQL database will probably be faster and databases like Casandra or Dynamo Db already come with sharding support, which would help us to manage large number of short urls
We will introduce Redis cache which can handle up to 1M request per sec for fast reads for GET api.
URL Cache
short_url
long_url
expiry policy of 7 days can be implemented in Redis using TTL setting. We will introduce a periodically running expiry job which will remove expired mappings from database.
Load Balancer will provide a way to distribute the load between multiple instances of both Read and Write Service.
API will be stateless so we can scale both services easily
Read Service will use Redis cache for fast retrieval of the mappings. We will also introduce rate limiting
Write service will save URLs in database so we will have to introduce rate limiting on the number of requests so that database can handle the load, we can store the URL generation requests on a queue and generate response asynchronously
We will need multiple instances of write and readservice for resilience but also for scalability
Write flow:
Short Url generation algorithm:
Read flow:
Collision handling can be solved by adding userId and additional counter or timestamp to the url
We are prioritising availability over consistency, that is why we are introducing Redis cache for read service for low latency of reads, however as cache is updated after the data are stored by write service in database, there might be some lage before new short_urls will be available.
We are introducing expiry of URLs to reduce the amount of space we need to store all urls.
Try to discuss as many failure scenarios/bottlenecks as possible.
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?