System requirements

URL shortening is a server that takes as inout an url, and returns back a shorter version of the same url. A shorter URL is more manageable, and, it can also contain information about the content

Functional:

• the system must be able to accept an URL and to return the shortened version
• When accessed, he shortened URL should REDIRECT to the original URL
• Statistics: optional functionality could include some data analysis, such as the number of times the short url has been clicked
• Comprehensive error handling: the system should be able to handle errors
• Implement procedures and details about URL expiration or customization.

Non-Functional:

• Availability: we want the system to be largely available. This requires implementing fault-safe mechanism through component redundancy and data replication
• Scalability: the system should be easy to scale horizontally (add more nodes) and vertically (add more resources to existing nodes)
• Consistency: the relation between URLs must be identified in an unique way. A call to the short URL must always return the long URL and vice-versa
• Latency: shortURL should return in a short time (<30ms), same is true for redirection to the long url (10ms)

Capacity estimation

Assumptions:

1. Daily Users: We can estimate around 100,000 active users per day.
2. URLs Created: Let's assume each user creates 5 URLs on average, resulting in about 500,000 new URLs per day.
3. Redirection Requests: If we estimate that each shortened URL is accessed 20 times a day, we can calculate total redirects.

Calculations:

• New URLs Per Day: 500,000
• Total URL Requests Per Day:
  • For 500,000 URLs accessed 20 times = 10 million redirect requests per day.
• Total Data Storage:
  • If we assume each URL takes roughly 1 KB of storage, for our 500,000 URLs, that would mean approximately 500 MB per day.
• Short URL length: what should be the length of the returned short URL? Assuming we have 500k new URL per day, in 5 years we'll have 500k*365*5 ~ 500k * 2k = 1 billion short URL. To represent 1 billion combinations, assuming I use a base 64 encoding system, where base64 is composed by:
  • 52 alpha chars (a-z & A-Z)
  • 10 digits (0-9)
  • 2 special chars
  • with N bytes, I can represent 64^N shortUrls, hence I need to solve
    • N = log64(1000000000) ~ 7 Bytes

Summary:

• Daily URL Creation: 500,000
• Daily Redirect Requests: 10 million
• Daily Storage Requirements: 500 MB

API design

Let's assume we use HTTPS for communication and REST APIs

• getShortUrl(apiDevKey,longURL,userKey,expiration_time,customURL)
  • apiDevKey is a key associated with the user making the request, it's needed to check auth and also as rate limiter, in case the same user makes too many requests
  • longURL, original URL input
  • expiration_time, time of the shortURL before expiring. It can be a predefined interval (e.g. 1 year)
  • customURL, it is an optional feature, where user can specify a customURL which will be reflected the shortURL
  • return a HTTP response containing the response of the API.
    • 200: success. It embeds the shortURL in the answer
    • 505: internal server error
    • 404: not found
    • ...
• redirectTo(apiDevKey,shortURL)
  • increase click cnt
  • returns HTTP responses:
    • 304 redirection. We want out call to be redirected to the longURL found by the API

Database design

Key Entities:

1. URLs: Storing the mapping between the short URL and the original long URL.
2. Users: If you want user accounts, you'll need a table to store user information.
3. Analytics: To track access metrics for each shortened URL.

Entity-Relationship (ER) Diagram

Here's an ER diagram representing these entities and their relationships:

(see ER diagram included)

Explanation:

1. USER Table: Stores user information, including a unique identifier, username, email, and a hashed password.
2. URL Table: Stores mappings between the original long URLs and their corresponding shortened versions. It includes a reference to the creating user and timestamps to track when the URL was created.
3. ANALYTICS Table: Stores tracking information for each shortened URL, including the count of how many times it has been accessed and the last accessed timestamp.

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

Request flows

The system works in this way:

USE CASE 1:

• in the frontend, an user insert a longURL and trigger the getShortUrl API
• the DNS server returns the IP of our shorteningURL system
• the request goes to our shorteningURL web domain, where a Load Balancer redirects it in one of our API web servers, where the request is processed:
  • the system creates for an available shortURL and returns it.
  • NOTES: ShortURL can be created on-demand, hashing the incoming request, or can be pre-created and then assigned when a new request comes. More details in the "detailed component design" section
• A mapping of shortURL-longURL is created and stored on a persistent storage (DB). In this case, a good choice could be using a noSQL key-value DB
• the mapping can also be stored on a cache system for faster retrieval
• The new shortURL is displayed back to the user

USE CASE 2:

• the user click on a shortURL, triggering the redirectTo API
• After passing Load Balancers, the request is processed by an API server, which queries the cache system. If nothing is found, the request is redirected to the DB
• If not URL is found, the system returns an error response, for example 404 (Not Found) http response
• if the URL is found, a 304 response (redirect) is returned back, together with the original long link, where the user can be automatically redirected

Detailed component design

• Let's dive in the service which provide the shortURL. Given an URL, we basically have two choices to return a shortURL. In both cases, it is suggested to hash the longURL, eventually combining it with the timestamp and the userKey, if present. The hashing allows the system to avoid collisions and to simplify the retrieval of the shortURL in the map DB/cache

1. creating it on-demand: the system generates an hash which acts as key for the input, and based on that another base64 string, which is our desired shortURL
2. return a free one from an existing set: all the 1e9 shortURLs can be pre-computed, and stored on some "availableURLs" dictionary living on server/DB. When an user requests a shortURL, it just provides one, delete it from the availableURLs, write to an "usedURLs" table and also pushing it the key-value storage

Trade offs/Tech choices

• Caching system: we can use a caching system to store lastly used URLs, which are more likely to be called in an imminent future. This improves performance, but it is more difficult to maintain, since the cache can be out of sync with the main database, and also we introduce another point of failure.
• Use 2 DB for URL generation service, each of one will contain half of the data. We have 2 main advantages:
  • the traffic is distributed on this DBs
  • in case of failure of one, we can use the other

Failure scenarios/bottlenecks

To avoid failures, we can think of:

• Component replications: with only one server/DB, we risk that, in case of failures, our system crashes. To avoid this, we can have many servers running at the same time, with the load balancer redirecting the traffic to one of them (let's say with a simple Round Robin Strategy). This helps avoiding sending too many request on a server. And in general is a very good strategy for horizontal scaling.
• DB sharding: we can partition the URL DB in more pieces. Consistent hashing could be the strategy used to store data and avoid data to be unbalanced and/or difficuklt to move between different DB instances
• Data replication: we can keep a copy of DB tables, allowing each one of them to serve different geographic locations. This increase availability and performance. We can use a master-slave arhitecture, where the data are written only into the master table, and then replicated. In case the master fails, a slave can be elected as new master.

Future improvements

• We can use a better algorithm to redirect work to servers. Round Robin is a simple scheduler, we can use something which takes in count the state of the server, so that the request is redirected to the best available worker
• Monitoring: we can use a monitoring system which collects internal status of the component in the systems, displaying useful metrics, and alerting the system admin in case of failures
• caching strategy: we can use 20/80 strategy:
  • due to the fact that 80% of the traffic usually comes to 20% of the URLs,we can store those 20% in cache and keep them using an LRU (Last Recent Used) strategy to keep/clean it