System requirements

Functional:

Encode a long URL to a short URL.

Decode a short URL to a long URL.

Non-Functional:

Stable.

High Availability

Capacity estimation

DAU =~100M

Assume:

a.Write:

0.1 write/user a day

Average write QPS = 100M*0.1/86400 =~100

Peak write QPS = 100*2 = 200

b.Read:

1/user a day

Average Read QPS = 100M*1/86400 = ~1000

Peak Read QPS = 1000*2 = 2000

c. Storage

100Byte/url

100M*0.1*100Byte = ~10G

API design

a. Create a short url:

POST /data/shorten

Data = {

"url" : "http://xxx",

...

}

Response = {

"shortURL" : "http://tiny/...",

"status": 200

}

b.Get a short url:

GET /

return and redirect to the long url.

Database design

We can use NoSQL

Table:

1.URL(Long to short) mapping table

Column: ID(int), LongUrl(varchar), shortUrl(varchar)

Index on LongUrl

2.URL(Short to long) mapping table

Column: ID(int), shortUrl(varchar), LongUrl(varchar)

Index on ShortUrl

High-level design

Request flows

a. Create a short URL

1. A Client sent request to Web Server with a long url;
2. Web Server send the long URL to database and check whether it exists. If not exist, return true to Web Server. Otherwise, return false.
3. Web Server generate the short url and insert it into Database.
4. Database return the id for the short URL
5. Web Server return the short URL to client

b.Visite a short URL

1. A Client request a short url to Web Server.
2. Web Server check the short url in Database.
3. If exists, Database returns the long url.
4. Web Server return to the client with http 301 redirect to the long URL.

Detailed component design

1.Database bases on the sequential ID to sharding horizally

Trade offs/Tech choices

Explain any trade offs you have made and why you made certain tech choices...

Failure scenarios/bottlenecks

Database use Master-Slave to make sure the stablity when a database server is down.

Master handles write and slaves handle read. If the Master is down, randomly pick a slave to be master.

Future improvements

1.reduce fetching time:

a. cache (use memcached) to store latest requested short url

b.cdn to get data by closest location