System requirements

Functional:

• Users can generate a short URL that's unique
• Users are redirected to long URL from short URL
• Users can create their own custom alias
• Users can specify the expiration time optionally

Non-Functional:

• Highly available
• Low latency
• Unguessable short links

Extension:

• Analytics and tracking

Capacity estimation

We expect our design to be read heavy, we will assume an 100:1 read to write ratio. Let's assume we have 100 mil new URL shortenings per month, then we will have 500 mil redirects per month.

Traffic estimate:

• We will have 100 mil / (30 * 100,000 seconds) = 30 write per second
• Then we will have 3000 reads per second
• In peak times we will multiply each by 2, so 60 writes per second and 6000 reads per second

Storage est:

• Let's assume we store the short urls indefinitely
• then we will be storing 1 billion short urls per year, or 10 billion in 10 years
• Assuming each object is 500 bytes, we have 10 billion * 500 bytes = 10 * 10^9 * 5 * 10 ^2 = 5 * 10^12 = 5 TB

Bandwidth Est:

• Incoming to our service for writes is 500 bytes * 30 writes/s = 15 KB / s
• Outgoing to the client for reads is 3000 * 500 bytes = 1 MB /s

Memory: We probably want to cache the 20% most popular short URLs for redirects, since we read around 3000 per second, thats around 3000 * 10 ^ 5 per day. 3 * 10^ 8 * 500 bytes * 0.2 = 3 * 10^10 = 30 GB

If we have servers that can take around 8000 requests per second, with around 3 million writes and 300 million reads per day, we expect around 37500 servers needed

API design

• Createurl(dev key, long url, expiration date - optional, custom alias- optional)
• deleteurl(dev key, short url key)
• Redirect(short url key) , on loading a short url, we lookup the short url and do a HTTP 302 redirect if it exists else we return an error

dev key ensures we adhere to quotas for the given user

Database design

We consider that:

1. The data is structured, we may need to store users, and mappings between the user and the created URL
2. we may also need permissions in the future
3. read heavy
4. data we store is small

We expect the schema to look like the following:

• User table:
• pkey, name, email, creation date, last login
• URL table:
• short url key as pkey
• long url
• expiration date
• creation date
• user id

We will opt to use a no sql for the storage of short urls and the users table given there is not many relations. Something like mongoDB will be good here for consistency in writes and its suitable for read heavy operations

We can consider range based query or hash based sharding for the database, to prevent bottle necks, we can go with consistent hashing on the keys

High-level design

In the encoding of the URL, we will use an offline key generation service. This keeps track of a used and unused key table. When it delegates keys to the servers, it moves the keys to the used key table. We will be generating keys of length 6, it will use a distributed lock to ensure it does not give a key to multiple servers. We will also keep a backup KGS in case of disaster mitigation or KGS failure. When KGS dies, the backup takes over to continue generate the keys.

We can add caches to multiple places, such as a db cache for faster lookup. We will use LRU eviction policy here since popular urls will be used more recently. Each cache entry holds the short to long URL mapping.

We can also cache at the app server, the KGS will send over some keys to the server, after it marks it as used. Then the server can use the values in the cache.

In case of a cache miss, we fetch from the backend db, then replicate the values to each cache.

We can also add load balancers between the client and the app server, app server and the database and the cache servers. We could use round robin or more advanced algorithms to detect heavy/light loads

Request flows

Creating a new url:

• The server fetches a new key for the url and stores the mapping in the database. Then sends the short url back to the client
• If a user submits a custom alias, check if it is taken already, if it is,send back an error, otherwise add this key to the used key table in the KGS
• MongoDB here will ensure we do not overwrite

Redirect:

• On request of a short url, check if a key mapping exists, if it does, do a HTTP 302 redirect for the client. We can prevent our db from becoming a bottle neck with a range based sequencer, this gives a basic mapping of the servers to the short url.

Deletion:

• Server checks if the key exists, then deletes it if it does

Detailed component design

Dig deeper into 2-3 components and explain in detail how they work. For example, how well does each component scale? Any relevant algorithm or data structure you like to use for a component? Also you could draw a diagram using the diagramming tool to enhance your design...

Trade offs/Tech choices

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

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?