System requirements

Functional:

URL Shortening:

1.The system should provide a mechanism to shorten long URLs.

2.Shorten URLS should be unique and not collide with existing ones

Redirection:

3.When users access a shortened URL, they should be redirected to the original long URL.

4.The redirection process should be fast and seamless.

--- Extra if asked

Custom Alias:

5.Users should have the option to customize their short URLs with a chosen alias (if available).

6.Alias should be unique across the system.

Expiration:

7.Provide an option for users to set an expiration date for their short URLs.

8.The link will by default expire after a certain period if no expiration date is set.

Non-Functional:

Scalability:

1.The system should handle a large number of URL shortening requests and clicks.

2.Scalability should be achieved through horizontal scaling.

Performance:

3.The redirection process should be fast, with minimal latency.

4.Ensure that the system can handle concurrent access without performance degradation.

Reliability:

5.The service should be highly available and have minimal downtime.

6.Implement mechanisms for fault tolerance and disaster recovery.

Storage:

7.Efficiently store and retrieve a large number of short URLs and their associated data.

8.Use reliable and scalable storage solutions.

Backup and Recovery:

1.Regularly backup data to prevent data loss.

2.Implement a recovery process to restore data in case of failures.

Capacity estimation

Let us assume our service will have the following usage patterns:

• 1 million new URL shortenings per day. which means an average 30 million shortenings per month.
• 10 million unique users.
• 100 million URL redirections per day.

Below are the number of url that we will have to store in our database for a 5 year period: 30 million * 5 years * 12 months = 1.8 Billion

Storage Estimation for 5 years:

• • Short URLs: 1.8 Billion * 8 bytes = 14.4 GB
  • Long URLs: 1.8 Billion * 500 bytes = 900 GB
  • Other metadata: 1.8 Billion * 100 bytes = 180 GB

Total: ~1TB for 5 years (per database)

API design

1. POST /api/shortenURL : This is the API that accepts the original URL, gives back the short url to the user.
2. GET /RedirectUrl : This is the API that will accept the short URL and redirect to the original URL.

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

• Table 1: Short_URL
  • id (Primary Key)
  • short_url
  • original_url
  • created_at
  • expiration_date

• Table 2: User
  • user_id (Primary Key)
  • name
  • email
  • password
  • Created_at

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

user --> LoadBalancer --> Application Server ( URL shorening service) APIS

Application Server --> checks in database if present return short uRL,

We can use in-memory caches like Redis or Memcached to store the most frequently accessed URLs.

if not found, generate short end url and save it.

Hashing or ID Generation: A unique short URL is generated using techniques such as:

• Base62 encoding (base-62 uses a set of 62 characters: a-z, A-Z, 0-9)

URL redirection service:

Same given shortURL, if found in storeage return.

or else error

Caching: Redis

Database:

MSSQL: DataIntegrtity, Scalling through Sharding

MongoDB : large Dataset, with flexible design, slowers the read. Not

Cassandra/Dynamo DB:

For highly scalable, distributed systems, you can use NoSQL databases like Cassandra or DynamoDB. These are great for horizontally scaling out the system and providing high availability

Database choice:

Using a NoSQL database for a URL shortening service has several advantages, making it a good choice for certain aspects of the system. Here are some reasons why a NoSQL database may be suitable for this scenario:

1. Schema Flexibility:
   1. NoSQL databases, such as MongoDB or Redis, provide schema flexibility, allowing you to store data in a flexible, JSON-like format. This is beneficial for a URL-shortening service where the structure of data (e.g., short URLs, custom aliases, analytics) may evolve.
2. Scalability:
   1. NoSQL databases are generally designed to scale horizontally, making it easier to handle the growing volume of data and increasing traffic associated with a URL-shortening service. As the number of short URLs and analytics data increases, you can add more nodes to distribute the load.
3. High Write Throughput:
   1. URL shortening services involve a high volume of write operations, especially when generating and storing new short URLs. NoSQL databases are often optimized for high write throughput, making them suitable for scenarios where new data is frequently added.
4. Document-Oriented Storage:
   1. Many NoSQL databases are document-oriented, allowing you to store data in a JSON-like format. This is advantageous for storing complex data structures associated with short URLs, such as metadata, analytics, and custom alias information.

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

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

CAP Theorem Implications for URL Shortening Service:

• AP (Availability and Partition Tolerance):
  • In a URL-shortening service, high availability is often more critical than strict consistency. Users expect quick access to short URLs, and downtime or delays in availability are less acceptable. Therefore, prioritizing availability and partition tolerance is a common choice.
• Consistency Trade-offs:
  • Achieving strong consistency across all nodes in a distributed system can introduce delays, especially during periods of network partition or high traffic. The system might choose eventual consistency, where all nodes will eventually converge to the same state, but immediate consistency might not be guaranteed.
• Eventual Consistency:
  • Since URL shortening services often involve distributed data across multiple nodes or data centers, eventual consistency might be a pragmatic approach. Users might experience temporary inconsistencies between nodes, but the system would work towards converging to a consistent state over time.

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?