System requirements

Functional:

The system allows users to shorten URLs:

• Generation of short unique URLs based on a long URLs (short URLs can be customized)
• Redirection to the original long URL
• Basic user management (account creation, login/logout, ability to view the users created short URLs)
• Analytics (amount of redirections for each short URLs) and various statistics such as geographic information
• The short URL should expire after a certain amount of time
• API integration for advanced users
• Error handling (URL that no longer exists...)

Non-Functional:

Performance requirements:

• Low latency for URL redirection should be low (less than 100ms)
• URL lookup in less than 10ms (caching will be necessary)

Availability:

• Uptime of 99.9%

Reliability:

• Strong consistency

Security:

• DoS protection
• Anti-phishing protection

Capacity estimation

Users and traffic growth:

• 1 million users in the first year
• 10% more users per month
• 10-30% are users creators (create about 4 shorts URLs daily)

Requests estimation

• 4 short URLs/day for 30% of 1M users : 300000 * 4 * 365 = 438 millions short URLs created each year

Storage requirements:

• With average of 100 chars/URL : 40GB/year

API design

string CreateShortUrl(string longUrl)

string GetLongUrl(string shortUrl)

string DeleteShortUrl(string shortUrl)

bool SuspendShortUrl(string shortUrl, datetime until)

bool ChangeLongUrl(string shortUrl, string newLongUrl)

Database design

There is no very complex relationships in the data model. We can consider a NoSQL technology (key-value store for instance) in order to scale better.

The service is more read intensive than write so it can scale by adding more read replicas of the database.

The url lookup can be made faster by using a distributed cache.

Url entity

• [PK] id
• [FK] owner_id
• short
• long
• creation_date
• redirection_count
• active

User entity

• [PK] id
• email
• password
• creation_date

High-level design

The client can be an anonymous user who clicked on a short URL or a authenticated user who wants to edit urls.

A load balancer is used to distribute evenly the requests from all users among serveral application servers. It could also be used as a rate-limiter.

Reading: servers will look for the urls first in the distributed cache and then in the database if the requested url isn't cached.

Writing: requests are pushed to a distributed queue so the service can handle peaks

Request flows

Creation:

• Users can create a new shorten URL using the web interface or the API
• New creation requests will be pushed to the queue
• A service will pool from the queue and serialize the newly created short URL to the database

Retrieval:

• Users can read a URL either by using the API or by accessing the short URL that will redirect them to the long URL
• The service will first check the cache
• If not found in the cache, the long URL will be retrieved from the database
• The found URL will be cached if not already
• The user will be redirected to the long URL if the service is accessed from the short URL

Detailed component design

• The queuing system helps the service from scaling well during peak of write operations because it allows asynchronous processing
• The cache helps to reduce work on the database during peak of read operations because the data are retrieve from memory instead of disk

Trade offs/Tech choices

We need to prioritize availability and partition tolerance in this case so we have to do some concession about consistency. Users must indeed:

• Be redirected to the correct URL without any delay
• Even in case of network failure or node failure

But we can tolerate some delay before a newly created URL is readable from all clients (eventual consistency)

Failure scenarios/bottlenecks

In case a database node fails:

• If it is the primary, a new primary will be elected among the replicas

If two short URLs are created with the same long URLs:

• We need a way to generate two different short URL so it is not possible to simply hash the long URL. We must pass another info to the hash algorithm like a timestamp and/or an ID

Future improvements

• Provide a way to customize URLs (with a name for branding for instance)