System requirements

Functional:

1. generate shortened url for long url
2. if the long url already has been shortened, return the existing shortened one
3. return the long url for the shortened url

Non-Functional:

1. low latency
2. high availability
3. data duration

Capacity estimation

1. DAU 1000,000
2. read (click) 100
3. generate 5
4. QPS for read： 100 * 1000,000 / 100,000 = 1k qps
5. QPS for write: 50 qps
6. 1 k QPS can be handled in one machine (if having more users, will use database clusters)

API design

RESTFUL

GET: api/v1/get_long_url?url=

POST: api/v1/generate_short_url?url=

Database design

client can submit long url to generate short url

each record will contain a record id, short url and long url

High-level design

Request flows

For generate short url:

1. Client will make a POST request with long url as payload
2. If the long url already exists in DB, will return the recorded short url
3. otherwise it will generate a record containing the short url and return it

For redirect to long url:

1. If the user will make a GET request with the short url
2. If the short url is in DB, will redirect
3. otherwise 404 code

Detailed component design

1. For database, the record id can have some options:

a. use hashcode to generate (hash collision possible)

b. Use base 65 (or larger number to contain symbols) to generate a number from the long url , easier to check the long url

c. use snowflake id to contain timestamp in the record id (easier for expire the record)

2.Base on QPS, read is about 1k QPS

write is about 50 QPS

One SQL DB machine is enough.

But we can provide a cluster (2 or 3 master and multiple slaves SQL database machines) to enhance availability and reduce processing time)

We can have a cache and expiration period for hot spot urls

3 DB size:

50 * 100 byte * 100,000 per day = 0.5 GB per day

1 yr = 15 Gb * 12 = 180 GB

10 yr = 1.8 TB

Trade offs/Tech choices

a.

1. One trade off is availability vs high consistency
2. If there are conflicts in this service, availability > consistency (and the chance of generating a short url for a long url at the same time is low)
3. So, if read QPS is higher enough, might turn to NoSQL database and select eventual consistency

b.

will not use scan, but build index on short/long urls for quick check if they are in database.

Failure scenarios/bottlenecks

1. Consistency if we use NO SQL solution
2. No analytics service

Future improvements

1. maybe add a solution for strong consistency for business purpose for some customers
2. add analytics service to gather information (and maybe use smarter cache solutions)