System requirements

Functional:

1. shorten URL
   1. short URL to 8 characters length
      1. md5 full hash with 128bits (16 bytes with 32 hex characters)
      2. sha256 full hash with 256 bits (32bytes with 64 hex characters)
      3. this means md5 might be a better option, because both will be truncated and extra bits of sha256 will not be needed
   2. each character is Hex so 8 bits per (both SHA-256 and MD5 generate hash values where each character (byte) in the raw output is 8 bits (1 byte))
   3. how to do :
      • hashing the link provided
      • md5 or sha256
        • md5 is faster but more collisions
        • to handle collisions we should just retry until we find a free one
2. Redirect Shortened URL
   • respond HTTP status code 302 which indicates a temporary redirect to client if available in our system
     • Error if not
   • Permanent redirect,
     • 301 http code is beneficial since we can have caches
     • some browsers cache these so they don't hit our servers all the time
   • We can incorporate a cache so we dont have to hit the DB all the time

Non-Functional:

1) Scalable

• Able to handle increasing load and also handle decreasing load (flexible)
• Able to handle large amounts of traffic (~1M DAU)

2) Availability

• Aiming for highly available

3) Consistency

• We can accept eventual consistency

4) Durability

• We don't want to lose data that has been committed to the system

Capacity estimation

1 million daily active users

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

Traffic:

• Redirects:
  • 1e6 per day means 1e8 redirects per day
  • 1e5 seconds per day meaning 1e8/1e5 is 1e3 redirects per second ~ 1000 TPS(Transactions Per Second. It’s a measure of how many individual operations or transactions your system can process in one second) 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:
  • Lets say we get 1000TPS meaning its 1000 * (size of the slug + size of the real link)

redirect transaction involves retrieving or processing two pieces of data:

1. 1. 1. 1. The slug: This is the short code from the URL itself.
         2. The real link: This is the full destination URL associated with that slug.
   • So lets say 1000TPS * 10KB ~ 10MB per second ~ not that bad

• Creation
  • minimal
  • 10 TPS is < 1MB per sec

Storage:

• 1e6 links per day, lets say 10KB per row
• 1e6 * 1e4 B ~ 1e10 B per day ~ 1e7KB per day ~ 1e4 MB per day ~10 GB per day
• 300 GB per month ~ 3600 GB per year
• 3.6 TB in 10 years ~ 20TB in 10 years

API design

generate_url

• parameters:
  • API Key

(Typically, the client uses an API key that was previously issued by the server. In many systems, during a registration or onboarding process, the server generates and provides the API key to the client. The client then includes this key in subsequent requests to authenticate itself.)

• • long_url
• returns
  • short_url
  • 200 HTTP code if able to generate

redirect_url

• parameters
  • API Key
  • short url
• returns:
  • 301 as permanent redirect
  • 404 if not present in our system

Database design

user_table

• user_id - primary key
• creation_date
• user_name

url_table

• url_id - primary key
• creation_date
• user_id - foreign key
• short_url
• long_url
• time_to_live

analytics_table

• short_url
• long_url
• user_agent
• user_ip
• referal
• http_code
• success
• device_type
• network_type

The analytics table is designed to store detailed information about each redirect event. It logs various attributes of every request, which can be used for monitoring, analysis, and optimization. Here’s what it typically tracks and why:

• Tracking Redirect Events:
  • Every time a short URL is accessed, an entry is made. This captures the event and allows you to review how often each URL is being used.
• User Behavior and Traffic Analysis:
  • User Agent: Captures the browser or client type.
  • User IP: Helps in understanding the geographical location of your users or detecting potential abuse.
  • Referral: Identifies where the traffic is coming from (e.g., another website, social media, etc.).
  • Device Type & Network Type: Provides insight into what devices or networks are most common among your users.
• Performance and Success Metrics:
  • HTTP Code & Success: Tracks the HTTP status codes returned and whether the redirect was successful. This information can help diagnose issues or errors in the redirect process.
• Business Intelligence:
• Analyzing this data helps you understand usage patterns, optimize performance, tailor marketing strategies, and even plan capacity for scaling the system.

High-level design

Components

• Load balancer
• Redirect Service
• Creation Service
• Database
  • Users
  • URLs
• Caches
  • Read flow

Request flows

Redirect flow:

1) user hits the load balancer first to determine where to redirect the user

2) we are pointed to the redirect service

3) now we have the request in the redirect service

4) we fetch the short url key from the cache

• if its not in the cache, we query the database for the long url
• if it is found, reply to the http request with a 301 and the long url

7) update the cache with key- value of shorturl: longurl

Creation flow:

1) user hits load balancer

2) we are sent to the creation service

3) here we generate a short url for the long url

4) lets say we do a hash for the long url ~ and then enode it to base64 so that the url is alphanumeric then truncate to 8 characters if its more than that

Base64 is shorter than Hex, less character

Hexadecimal:

Uses 16 symbols (0–9 and A–F). Each hex digit represents 4 bits.

→ 2 hex digits per byte (8 bits).

Base64:

Uses 64 symbols (typically A–Z, a–z, 0–9, and two additional characters, like '+' and '/'). Each Base64 character represents 6 bits.

5) we will try to insert this in the database, if it fails, because there is a unique constraint on the short url, we retry

Detailed component design

Bottlenecks will come from the read path of our system. Meaning 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.

Stateless: The service doesn't store client-specific state between requests. Each request must contain all the information needed to be processed.

1) Database consideration

• We will use a relational db for our users and url tables
  • we can shard the database 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 since instead of just one node
• We will use a database that can handle a lot of writes for our analytics table like cassandra
  • we choose cassandra since it can handle huge amounts of writes
  • it can handle huge amounts of writes since it uses a WAL and a LSM tree structure
    • optimized for writes

2) Cache consideration

1. Redirect service
   • 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
2. in CreationService

• we do a write through, so that we can update the cache right away

Refresh-Ahead:

• Proactively updates cache items before expiration.
• Reduces cache misses by ensuring data is fresh when requested.

Freshness & Consistency:

Even if a cache entry isn’t evicted, it might become stale if the underlying data changes. Refresh-ahead updates the data before it expires, ensuring that every cache hit returns current information.

Avoiding Expiry Bursts:

Without refresh-ahead, if many entries expire at once, a sudden surge of cache misses could overwhelm your database. Refresh-ahead smooths out these peaks by updating entries in the background.

Improved Performance:

By proactively refreshing the cache, you reduce the likelihood that a user request will have to wait for a database query, thus maintaining low latency and a good user experience.

Write-Through:

• Writes data to both the cache and the database simultaneously.
• Maintains consistency between the cache and the database.

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 a cassandra( WAL and a LSM tree ) as our main analytics database since it can handle a lot of traffic for writes. Since it is write optimized, it is a lot better than a relational database since relational databases use b-trees and will have slower writes

2) Since we do sharding - we have to keep in mind that we cannot join easily. Since we dont really need to join any data, it is a good choice for us.

Why sharding makes joins difficult:

• Data Distribution:
• Sharding involves partitioning data across multiple servers. When related data is stored on different shards, performing a join operation requires aggregating data from several nodes, which can introduce significant network latency and complexity.
• Performance Overhead:
• Joins across shards necessitate cross-node queries, which are typically slower and more resource-intensive compared to joins within a single database. This is why many distributed databases (like Cassandra) either don't support joins or discourage their use.
• Complex Query Logic:
• Managing and coordinating data across shards for join operations often requires custom application logic, making the system more complex and less efficient.

Why joins aren't really needed in a URL shortener design:

• Simple Data Model:
• In a URL shortener, the primary functionality is a simple key-value mapping between a short URL (or slug) and the long URL. This lookup can be handled with a single table (or a single shard) without the need to join data from multiple sources.
• Independent Entities:
• The URL records are self-contained; each short URL points directly to a long URL. There's no need to combine or correlate data from different tables or sources during a redirect, which eliminates the requirement for joins.
• Optimized for Speed:
• Since URL redirection needs to be extremely fast and efficient, avoiding joins helps reduce query complexity and latency, ensuring that each redirect operation is executed quickly.

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

In many modern system designs, especially those involving microservices, sharded data, and multiple replicas, Kubernetes is often mentioned because it provides a consistent and efficient way to manage the complexity of distributed systems.

Docker Swarm:

A native clustering tool for Docker containers. It's simpler to set up and manage compared to Kubernetes, though it may not offer as many advanced features.

Apache Mesos with Marathon:

Mesos is a cluster manager that abstracts resources from entire data centers, and Marathon serves as a container orchestration framework on top of Mesos. It’s used in large-scale environments that need to manage both containerized and non-containerized workloads.

HashiCorp Nomad:

A lightweight and flexible orchestrator that supports not only containers but also non-containerized applications. It's known for its simplicity and ease of integration with other HashiCorp tools.

Managed Services:

Cloud providers offer their own orchestration solutions, such as:

• AWS Elastic Container Service (ECS) and AWS Fargate
• Google Cloud Run
• Azure Container Instances
• These services manage much of the infrastructure for you, reducing operational overhead.

Failure scenarios/bottlenecks

1) The load balancer is a bottleneck and could fail. We will have a backup loads balancer who 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.

3) We rely on Kubernetes and it could fail.

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 in 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 east and west coast. Adding data centres in 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 datacenters or availability zones are down, we can redirect to other regions.

2) Improved algorithms when generating shortened URLS. Since currently we hash it our selves. 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 are able to 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.

Redis Sentinel is designed to handle cache failures. It continuously monitors Redis instances and, if it detects that the master has failed, it automatically promotes one of the replicas to be the new master

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