System requirements

Functional:

• POST: Generate a shorten URL with 8 characters from an original URL.
• GET: Given a valid shorten URL, redirect to the original URL.
• User can customize the alias for shorten URL.
• User can setup a TTL for the shorten URL. Default TTL will be assigned if no TTL is provided

Non-Functional:

• Service must maintain high availability
• Service must maintain low latency
• Service must be scalable horizontally

Capacity estimation

Let's assume that the service serves 1 million POST requests and 10 million GET requests per day.

• 1 write : 10 reads
• 11 TPS for writes and 110 TPS for read
• 30 million POST and 3000 million GET per month
• 30 * 12 months * 5y = 1800 million = 1.8 b post requests for 5 year period
• 3b * 12 months * 5y = 180b GET requests for 5 year period

API design

• POST: create_short(): This API takes original URL as a parameter and return the tiny URL
• GET: get_long(): This API takes the tiny URL as a parameter and return the original URL for redirection

Database design

Since our data doesn't follow relation pattern, we can use Nosql to store our data

URL table (with TTL)

• hash id(short URL with prefix for collision) (primary key)
• original url
• Create at (for logging)
• Request ID (for logging)

High-level design

1. URL shorten service:
2. Generates short URL and store them into DB
3. Manage the collision, TTL, and consistence for alias
4. Redirection service:
5. Retrieve the original URL from DB and handles the redirection
6. Load Balancer:
7. Handles large numbers of requests. We can have LBs in
8. between clients and Web service

between Web services and our micro services(shorten service and redirection service)

1. between web service and caching service
2. Caching:
3. Store data into in-memory caching layer can ensure the low latency of reading since reading from DB is slow
4. Rate limiter:
5. Have control of threshold of read and writes in our services to prevent our system gets overloaded

Request flows

• GET Flow

1. Client sends a read request to LoadBalancer
2. LoadBalancer distributes the request to Redirection server 1
3. Redirection server1 checks the Cache for data (Read)
4. Cache returns a Cache Hit to Redirection server 1
5. Redirection Server1 returns the data to Client (Cache Hit)
6. If Cache Miss, Redirection Server1 reads data from Database
7. Database returns the data that contains the original URL to Redirection server 1
8. Redirection server 1 returns the data to Client

• POST Flow

1. Client sends a Write Request to LoadBalancer
2. LoadBalancer distributes the Write Request to URL shorten Server 1
3. URL shorten Server 1 writes data to the Database (Write-Around)
4. Database replicates the write operation to Replica1
5. Database replicates the write operation to Replica2

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

Encoding option:

1. Base62 can ensure each character has 62 options which can reduce the chance of collision.

Data base Option:

1. NOSQL: Since the data is not relational, we require heavy reads, writes, and fast look-up. Also, we will have better scalability.

Consistency:

1. Strong consistency across all nodes usually creates delays and high latency, especially during the period of high network traffic, hence the service can use eventual consistency to ensure the performance

Caching:

1. Having a caching layer can improve the API latency performance and availability and reduce the read traffic from database. Even when sometimes the DB is not reachable for some reason, as long as the cache as data, service can still be able to retrieve the original links.

Failure scenarios/bottlenecks

1. DB outage:
2. Redirection and URL shortening services heavily depend on the database. A failure to reach the database or high latency to get the result might drop the availability of service and lead to bad user experience
3. High traffic peak:
4. Sudden spikes in traffic could overwhelm the system in case the URL is added as a backlink to a popular webpage.

Future improvements

1. Implement CDN with caching to further optimize the latency and performance for the service.
2. Deploy service to multiple regions to also optimize the latency.
3. Integration with analysis tool or logging service to monitor the overall availability of the service to detect any bottleneck in early stage.