Funtional requirement

1. UrlService.longToShort(longURL). User input a URL and get a shortened URL. If the long URL already has a shortened URL, just return the existed one, otherwise generate a new shortened URL.
2. UrlService.shortToLong(shortURL). User click a shortened URL and jump to the original URL.

No-functional requirement

1. Final consistency. We allow temporary inconsistency when writing into the database. But the finally user should be redirected to the same correct address when clicking on the same shortened URL.
2. availability

QPS

100 queries per second

Capacity

Assume the length of each short url is 6 characters and 100 bytes for each URL record.

The required space would be 100 * 100 * 3600 * 24 * 10^(-6) = 864 MB in one day. And it would be 864 * 365 * 2 * 10^(-3) = 630 GB in two years.

Database Design

I would use SQL because it supports transaction. There are two tables.

1. long_to_short
2. short_to_long

long_to_short table is used for returning a shortend URL while short_to_long table is used for jumping to the original address. We assume the URLs are permanent and different users would receive the same shortened URL when they input the same long URL. When we generate a short url for a long url, we must write in both tables. So we can use transaciton to manage the database to ensure the consistency.

long_to_short

id (pk)

long_url

short_url

short_to_long

id (pk)

short_url

long_url

API design

GET /{short_url}

return a redirected Http response

POST /{long_url}

return a short url

Algorithm

The key point is to design a generated algorithm.

1. Hash function
2. Random generation and remove the duplication
3. Base62 conversion

Hash function

Advantage: fast

Disadvantage: it's hard to design a perfect function without any hash confliction.

Random generation

Advantage: easy to implement

Disadvantage: As the number of short urls grows, there would be more and more duplications and decrease the speed

Base62 Conversion

Advantage: efficient

Disadvantage: depend on the auto-increment id

Overall, Base62 should be the most suitable method because we can use id in the table as our auto-increment id.

Optimization

1. There are more read operations than writing operations. So I would use Cache like Redis.
2. Use DNS to enable users in different places to visit different servers.
3. Use CDN to enable users acquire resources quickly.
4. Use loading balancers to allocate server resources reasonably.