System requirements

Functional:

• Convert long URL to short URL -> Use hashing function like md5 or sha256.
• Redirect URL: When the server hits with short URL redirect with 301 so that the browser can cache the result.

Non-Functional:

• Fast response using cache.
• High availability.
• Batch processing.
• Eventual consistency can be tolerated.
• Auto scalable.
• Durability.

Capacity estimation

We should expect around 1 million daily active users.

• 100 redirects per day each.
• 1 times a day they create a new one.

For traffic:

• Redirects:
• 1e6 per day means 1e8 redirects per day.
• 1e5 seconds per day meaning 1e7/1e5 is 1e3 redirects per second ~ 1000 TPS for redirects
• Very doable
• Creation:
• 1e6 daily active users per day means 1e6 new links per day
• 1e6 / 1e5 is 1e1 which means ~10 TPS for creating new links

For throughput:

• Redirect:
• Let's say we get 1000 TPS meaning it's 1000 times the size of the slug + the size of the real link.
• So let's say 1000 TPS * 10KB ~ 10MB per second ~ not that bad.
• Creation
• Minimal
• 10 TPS is < 1MB per sec

Storage:

• 1e6 links per day, let's say 10KB per row
• 1e6 * 1e4 B ~1e10B per day ~ 1e7KB per day ~ 1e4 MB per day ~ 10GB per day
• 300GB per month ~ 3600 GB per year x 10 years is 36000 GB in 10 years
• 3.6 TB in 10 years ~ 20TB in 10 years.

API design

• Shorten_url
• Params: (long_url, user_id)
• Returns shorth_url
• 201 if successful
• Redirect_url
• Params: (short_url)
• 301 if redirected
• 404 if not found

Database design

Tables:

• User
• user_id
• creation_date
• user_name
• Long url
• id (primary key)
• creation_date
• user_id (foreign key)
• short_url (primary key)
• long_url
• ttl

High-level design

API Gateway is connected to a load balancer that spreads traffic between the different instances of the create URL service and redirect service.

These 2 services are connected to the same database.

The database has a caching layer.

Request flows

Redirect flow

1. Client makes request, and hits load balancer
2. If hashing code in URL go to redirect service
3. Check cache for corresponding long URL
4. If cache miss hit db to look for it
5. If found: return 301 and fill cache
6. If not found: return 404

Short URL flow

1. Client makes a request and hits load balancer
2. Sent to short URL service
3. Hash long URL and store hash in db along with the new short URL
4. Insert I db because of unique constraint, retry hashing function

Detailed component design

Bottlenecks will come from the read path of our system. This means the cache and the database will be hit with a ton of traffic.

Both services are stateless, so it is easy to scale them by adding more servers.

1) Database consideration

• We will use a relation db for our users and URL tables.
• we can shard the db using the hash of the short URL as the shard key.
• each shard will have a primary and secondary nodes - Two or three read replicas.
• Redirect service will target these read replicas.
• So now, the load will be shared with all these nodes instead of just one node.
• We will use a database that can handle a lot of writes for our analytics table like Cassandra
• we chose Cassandra since it can handle huge amounts of writes

2) Cache consideration

• In memory cache like Redis for the redirect service
• We will also deploy a Redis in a distributed manner
• We will have multiple nodes, splitting keys using consistent hashing
• use refresh-ahead so that we can update the cache in advance.
• In creationservice we do a write-through so that we can update the cache right away.

3) Load balancing

• A few load balancing algorithms like round robin, least connections, least load, least response
• We choose round-robin for simplicity

Trade offs/Tech choices

1) We use Cassandra as our main analytics database since it can handle a lot of traffic for writing. Since it is write optimized, it is a lot better than a relation db since relation db uses b-trees and will have slower writes

2) Since we do sharding - we have to keep I mind that we can't join easily. Since we don't really need to join any data, it is a good choice

3) Since we do read replicas - we need to keep in mind the delay in updating the replicas.

Since we have a cache that we update and since the first is returned optimistically. it should be covered.

4) Since we have a few nodes/shards/replicas we need to know how to manage this system. A tool like Kubernetes can be used to make sure our nodes are up and running.

Failure scenarios/bottlenecks

1) The load balancer is a bottleneck and could fail. We will have a backup loads balancer that is passive. Traffic will be redirected to it in case the main load balancer fails.

2) Nodes in the database and caches could fail. Since we are using Kubernetes, we rely on it to bring them back up.

3) Servers running the services could fail. Again, we rely on Kubernetes/ or other orchestration software to revive the services.

4) When a node in the Redis cluster fails, we could get a lot of cache misses. Since we use consistent hashing, we only get a minimal amount of keys that get affected since they are split between the nodes and virtual nodes.

5) Some database nodes could get too much traffic/data if the sharding is not done properly - a hot spot. We have to monitor this so that we can improve our key distribution. Sharding the large node should be enough to fix the issue temporarily.

Future improvements

1) Adding availability zones like the east and west coast. Adding data centers on multiple continents to get closer to users. This can reduce the load of the system since we balance the load among regions. Doing this also improves availability since now even if data centers or availability zones are down, we can redirect to other regions.

2) Improved algorithms when generating shortened URLS. Currently, we hash it ourselves. There is no causality, it is hard to order the shortened URLs. For this, we can use a technique like SnowFlake which integrates some of the bits in the returned value so we can have some order.

3) Using Terraform to manage the whole system. Since now there are a lot of moving parts, we need to use something that can make managing our system easier.

4) Using Redis Sentinel to manage our cache clusters can help us handle failure events.

5) We also need to discuss how our databases handle partition events. Like in primary/secondary where have to promote a secondary node to a primary. Voting mechanisms should be the new primary. How data is replicated among nodes. So we can gracefully recover from the backups/replicas.