generate unique shortened URL (6 to 8 characters).
a-z, A-Z, and 0-9 makes a total of 62 possible characters.
stores the short url.
when accessing the short url, look up and redirects to the original.
users cannot edit or delete short urls.
Non-Functional:
high availability, scalability, and fault tolerance.
Monitoring service including tracking click rate.
Capacity estimation
assume 100 million request per day and 100 bytes per request.
assume the short urls will be stored for 10 years
10^8*365*10=365 billion unique urls.
QPS=10^8/10^5=1000
Peak QPS=1000 * 2=2000
Read/write ratio is 10 to 1
read QPS=1000*10=10000
storage=10^8*100*365~=4TB per year
API design
POST original url to /api/shorten
requet parameter: {longUrl: longUrlString}
return short url
GET short url from /api/shortUrl
return longUrl with 301 redirect
Database design
relational database
auto increment id
long url
short url
High-level design
flowchart TD
B["client"];
C{"server"};
D["Database"];
n1["Monitoring Service"];
B --> C;
C --> D;
C --> n1;
Request flows
shortening service
client sends long url to server.
server hashes long url to short url and stores it in the database.
server sends back the short url to client.
visiting service
client queries short url.
server looks up the corresponding long url from database and sends back the short url with redirect.
monitoring service records click rate.
Detailed component design
Hashing deep dive
hash value length
to hold 365 billion unique urls, the hash value length is at least 7 as 62^7~=3.5 trillion
Common hash functions
CRC32
MD5
SHA-1
These common hash functions generate hash value length more than 7.
Customize a hash function to generate hash value length of 7.
to solve collision, append a predefined string to the long url
querying database for each request is expensive, we can use a bloom filter in front of the database to reduce stress.
A bloom filter is a space-efficient probabilistic technique to test if an element is a member of a set.
URL redirecting deep dive
Read requests are much more than write requests, and they are stateless.
horizontally scale web servers with load balancing to handle the loads.
Add database read replicas.
Add Redis cache in front of database to reduce database queries.
Trade offs/Tech choices
301 redirect. A 301 redirect shows that the requested URL is “permanently” moved to the long URL. Since it is permanently redirected, the browser caches the response, and subsequent requests for the same URL will not be sent to the URL shortening service. Instead, requests are redirected to the long URL server directly.
302 redirect. A 302 redirect means that the URL is “temporarily” moved to the long URL, meaning that subsequent requests for the same URL will be sent to the URL shortening service first. Then, they are redirected to the long URL server.
If the priority is to reduce the server load, using 301 redirect makes sense as only the first request of the same URL is sent to URL shortening servers. However, if analytics is important, 302 redirect is a better choice as it can track click rate and source of the click more easily.
Users may not need to access the short url immediately, write latency (which is OK to be slow) with read latency.
We also trade off consistency with availability. We want the request to be serving reads as fast as possible without fully waiting for all replications to complete.
Failure scenarios/bottlenecks
Malicious urls can be sent to disrupt servers.
Relational database is difficult to scale, consider using noSql.