System requirements

Functional:

1. Be able to generate short URLs from long ones

Non-Functional:

1. The system should be available
2. 
   

Capacity estimation

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

API design

1. POST : create_short(long_url) return 200 on successful creation, and write to our database along with the shortened URL,if the URL is already (we will look up the URL because we have indexed the long URL and return the short if it exists). Will return a 500 if we are unable to create the short.

1. GET: get_long(short_url) looks up the table and returns the long_url, we can use a DNS server to return the IP address also. If the URL does not exists we can return a 400

Database design

Since our service requires a high read/write throughput and the data does not follow a relational pattern, we will use a noSQL database like MongoDB. We will use a TTL mechanism to auto-delete old records to address scalability. To help with scalability and faster retrievals, we will use sharding based on the hash of the long URL. While this approach may introduce an uneven balance amongst the shards, we can potentially shard the uneven zones, further creating shards within shard. We will use a range based sharding strategy based on the hash range of long urls.

This ensures faster read/writes.

To address efficient distribution amongst the shard we will use consistent hashing to mitigate rebalances if nodes are added/removed/

Furthermore, to help with fault tolerance, we will use database replicas; the replicas will be updated as soon as possible based on the volume of change and a minimum amount of time.

To improve query time we will index our database on the long URL and have a second index on our short_url

1)key: long URL

2) value: short URL

High-level design

graph LR

A[Client] --Read Request --> B(Load Balancer)

B -- Distribute --> C(Server 1)

B -- Distribute --> D(Server 2)

C -- Check Cache --> E(Cache)

E -- Cache Hit --> C

E -- Cache Miss --> F(Database)

F -- Read --> C

C -- Return Data --> A

A -- Write Request --> B

B -- Distribute --> D

D -- Write to Database --> G(Database)

G -- Replicate Write --> H(Replica 1)

G -- Replicate Write --> I(Replica 2)

Request flows

sequenceDiagram

participant Client

participant LoadBalancer

participant Server1

participant Server2

participant Cache

participant Database

participant Replica1

participant Replica2

Client ->> LoadBalancer: Send Request

LoadBalancer ->> Server1: Distribute Request

Server1 ->> Cache: Check Cache (Read)

Cache -->> Server1: Cache Hit

Server1 -->> Client: Return Data (Cache Hit)

Server1 -->> Database: Read Data if Cache Miss (Read)

Database -->> Server1: Return Data

Server1 -->> Client: Return Data

Client ->> LoadBalancer: Send Write Request

LoadBalancer ->> Server2: Distribute Write Request

Server2 -->> Database: Write to Database (Write-Around)

Database -->> Replica1: Replicate Write

Database -->> Replica2: Replicate Write

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?