Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Links must be able to support analytics.
• URL should not be easily reversed engineered such as incrementing or UUID where it is time dependent

Non-Functional Requirements:

• High availability
• Low latency
• Horizontal scalability
• Assuming a medium-scale system, with about 1B users, and 10% of which are active, which is 100M users, each creating about 3 request/minute on average, we can expect 300 request/minute, or roughly 5 request/second. Considering the longevity of the system for 100 years, we can expect 5*60*60*365*100 = 657M possibly unique URL.

API Design

Define the APIs expected from the system. This is your chance to analyze and define the read and write paths so that you can come up with the high-level design...

Domain name: trnc.io

Available endpoints:

POST trnc.io/api/v1

{

url: 'https://codemia.io"

}

returns {url: 'trnc.io/api/v1/cmio'}

GET trnc.io/api/v1/cmio

302 redirect to https://codemia.io

GET trnc.io/api/v1/analytics

(internal analytics use)

API Gateway (Edge Tier) This is the single entry point for all client traffic. It handles rate limiting to prevent abuse or denial of service attacks. It also manages load balancing, routing incoming traffic to the appropriate backend service based on the request endpoint.

Write Path (Shorten URL Service) This service handles POST requests to create new short links. Instead of generating IDs on the fly, it requests a precomputed unique string from the Key Generation Service. It pairs this short string with the original long URL and saves the record to the primary MongoDB database.

Read Path (Retrieve URL Service) This service handles GET requests for redirection. It is separated from the write service so it can scale independently to handle the massive read volume. It checks the Caching Layer first. If the short URL is found, it immediately returns a 302 redirect. If it is a cache miss, it fetches the data from a secondary MongoDB database, updates the cache, and then redirects the user.

Key Generation Service (KGS) A dedicated background service that precomputes millions of unique random base62 strings. It stores these unused strings in a separate database table. The KGS assigns small blocks of these precomputed keys to the Write Path servers. This guarantees that IDs are hard to guess, prevents database collisions entirely, and keeps the write process extremely fast.

Caching Layer (Redis) An in-memory cache placed between the Retrieve URL Service and the databases. URL shorteners are extremely read-heavy. Storing the most frequently accessed URLs in Redis prevents the database from being overwhelmed and ensures the redirection latency stays as low as possible. When a cache miss occurs, the system fetches the URL from the database and writes it to Redis with a Time-to-Live (TTL) setting to prevent memory bloat.

• Database Tier (MongoDB) The persistent storage layer uses a Primary-Secondary setup. The primary node handles all new write operations. The secondary nodes handle the read operations. This isolates the read traffic from the write traffic and provides high availability if the primary node goes down.

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

1. Services: split shorten-url service and retrieve url service. Service will likely be heavily read. So separating these services will allow us to scale them independently.
2. Hashing algorithm: Precompute 1B unique keys and store than in the DB instead of using incremental ids as that is predictable.
   1. Other potential implementation:
      1. Incremental ID + random increments
         1. Pros: easy to implement
         2. Cons: Predictable
      2. Hashing the url
         1. Pros: easy to implement and deterministic
         2. Cons: does not fulfil the requirement of analytics where we need unique shortened urls to help keep track
      3. random generation
         1. Pros: simple implementation
         2. Cons: collision, but trade off alright since collision is rare
3. Database:
   1. Choice: NoSQL db like mongoDB
   2. Strategy: 1 primary, 1 secondary backup
   3. Based on our defined non-functional requirement regarding the requests, 1 primary noSQL db will be able to support the request. However, we still choose to have a secondary DB to allow for high availability in case of failure. Seek for simplicity instead.
   4. Other potential implementation:
      1. Consistent hashing
         1. Pros: if we needed multiple databases, then we are able to shard evenly
         2. Cons: Extra complexity. Unbalanced databases (solved with virtual servers)
      2. Cache only db
         1. Pros: lightning fast, support twice as fast as noSql
         2. Cons: mem only, lose data
4. URL length: There are 26 characters in the english alphabet, multiply by two for capitalised letters, add an additional 10 for numbers and we have 56 characters. To determine the length of the url, we can reverse engineer by using log(657000000)/log(56) ~ 6 characters long, which can create 30,840,979,456 requests. Approximately 4690 years. By using 6 characters length, we are able to support the storage required for a base62 encoding.
5. Status code: 302 to force client to send request to our servers so that we can support analytics. Downside is that we will receive more requests, but we will be able to support this with our design.