System requirements

Functional:

List functional requirements for the system (Ask the chat bot for hints if stuck.)...

• Be able to generate unique short URL
• Users should be able to easily copy the shortened URL
• Optionally, users should be able to pick a customized name for the URL
• Optionally, users should be able to specify expiration time.

Non-Functional:

List non-functional requirements for the system...

• Highly available
• URL redirection should have low latency
• Shortened URLs should be random (not predictable)

Capacity estimation

Estimate the scale of the system you are going to design...

Traffic

This system should be read-heavy - most will be redirection requests compared to new URL generation. -> Assume a 100:1 ration between reads and writes.

Assume 500 million new URLs per month -> 50 billion redirections (reads) in the same period.

Queries per second for URL shortenings per second would be 500M / (30days * 24 hours * 3600 seconds) ~= 200 URL/sec

URL redirections will be 20000/sec

Storage

Assume we store every URL shortening request (and the associated link) for 5 years. Since we expect 500M URLs every month -> 500 million * 12 months * 5 years = 30 billion

Assume each stored object is about 500 bytes - 30 billion * 500 bytes = 15TB

Bandwidth

Write requests -> 200 new URLS per second -> 200 * 500 bytes = 100 KB/sec

Read requests -> 20000 * 500 bytes = 10 MB/sec

Memory

Using the 80-20 rule, we'd like to cache 20% hot URLs.

Since we have 20K requests per second, 20K * 3600 seconds * 24 hours ~= 1.7 billion. 20% of that: 1.7 billion * 0.2 * 500 bytes ~= 1.7 GB. This is amount of cache we'd need.

API design

Define what APIs are expected from the system...

# A successful call returns the shortened URL; returns error code otherwise def createURL( apiDevKey, originalUrl, custom_alias=None, userName=None, expireDate=None ) -> String

def deleteURL( apiKevKey, urlKey )

A malicious user can put us out of business by consuming all URL keys in the current design. To prevent abuse, we can limit users via their api_dev_key. Each api_dev_key can be limited to a certain number of URL creations and redirections per some time period (which may be set to a different duration per developer key)

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

A few observations about the nature of the data to store:

1. Need to store billions of records
2. Each object is small (less than 1kb)
3. There are no relationships between records—other than storing which user created a URL
4. The service/system is read-heavy.

A NoSQL store like DynamoDB or Cassandra would be a better choice.

For tables:

URL table

• column name, type, key
• hash, varchar(16), primary key
• originalURL, varchar(512)
• createDate, datetime
• expireDate, datetime
• userId, int

User table

• column name, type, key
• userId, int, primary key
• name, varchar(20)
• email, varchar(32)
• createDate, datetime
• lastLogin, datetime

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design. If you are unfamiliar with the tool, you can simply describe your design to the chat bot and ask it to generate a starter diagram for you to modify...

See High Level Diagram

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Client sends a "shorten URL" request to the server. The server will hash the given URL, then reach out to the encoding service with the hash.

After encoding, encoding service stores the encoded string (shortened URL) to the DB, and then return the shortened URL to the server, then to the client.

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...

Using base64 encoding, a 6 letters long key would result in 64^6 ≈ 68.7 billion possible strings.

Using base64 encoding, an 8 letters long key would result in 64^8 ≈ 281 trillion possible strings.

With 68.7B unique strings, let’s assume six letter keys would suffice for our system

If we use the MD5 algorithm as our hash function, it’ll produce a 128-bit hash value. After base64 encoding, we’ll get a string having more than 21 characters (since each base64 character encodes 6 bits of the hash value).

Now we only have space for 6 characters per short key; how will we choose our key then? We can take the first 6 (or 8) letters for the key. This could result in key duplication; to resolve that, we can choose some other characters out of the encoding string or swap some characters.

Possible issues:

1. If multiple users enter the same URL, they can get the same shortened URL, which is not acceptable.
2. What if parts of the URL are URL-encoded?

We can have a standalone Key Generation Service (KGS) that generates random six-letter strings beforehand and stores them in a database (let’s call it key-DB). Whenever we want to shorten a URL, we will take one of the already-generated keys and use it. This approach will make things quite simple and fast. Not only are we not encoding the URL, but we won’t have to worry about duplications or collisions. KGS will make sure all the keys inserted into key-DB are unique.

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?