Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• Low latency
• Scalable
• High Availability

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

• 100 million DAU
• High read/write ratio. For every URL that is created, it will be read many times. Let's assume average 100 reads per write: 100/1
• Storage requirements: 100 million DAU * an estimate of 5 URLs per user = 500 million urls per day. Storage involves mapping a short url to a long one = storing both. So let's say the short url is 12 characters and the long one could be 64 characters. So 76 characters = 76 bytes roughly 75 * 500 million = 37.5GB per day = after one year we need 37.5 * 365 = 13.7TB. This is entering the order in which sharding may be necessary (10s of TB)
• Growth: Let's estimate 1 million users per day = 365 million users per year.
• Bandwidth: 100 million DAU * ?
• QPS ?

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

POST /api/long-urls

body {

"longUrl": string

}

GET /api/long-url/[shortUrl]

High-Level Design

Describe the overall system architecture. Identify the main components needed to solve the problem end-to-end. Use the diagramming tool to create a block diagram.

Load balancer sits in front of the server, after the CDN. It routes traffic between multiple servers. Use a Level 7 load balancer here to route traffic intelligently.

We will have a read server and a write server. This separation is crucial to allow us to scale these servers separately, since reads/write demand may not always be directly correlated.

The servers handles API routes for GET and POST.

• GET checks if the cache contains the URL and if not, fetches directly from the server, and updates the cache. Otherwise, fetches from the Redis cache.

The write server.

• POST writes directly to the database. The ID is the short url. The server computes the ID by hashing the URL, and then encoding it in a high base (e.g. base62). It inserts a row with the ID as the short URL and the long URL.

45GB/day means that database sharding will be required.

Consistent hashing on the URL's database ID to partition shards?

CDN can actually cache the response to /api/[shortUrl] since it never changes!

Given the high read/write ratio, we are optimizing for high-read count here. This means: Caching! So, a redis cache sits in front of our database and caches responses to requests for any given URL, with the short url as the hash key, and the long url as the hash value in each KV string. Since the URL mappings never change, and extremely long TTL can be used. Maybe lazy-caching since some URLs may never be used and we don't want to overfill the cache.

Due to the nature of this system, some URLs will be read far, far more than others, with some extremely hot paths. This means that we need to optimize for hot-read-paths.

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

Entities:

URL

{

shortURL: string; primary key

longURL: string;

createdAt; number

}

Stick with SQL - keep it simple.

The standard access pattern here is a query by shortURL, so we need an index on shortURL

BTree?

Since we are sharding the DB due to the scale, we need to decide on how the data is split. A simple approach here could be splitting on the shortURL using consistent hashing, since the hashing algorithm used to create shortURL should make this split data evenly.

CAP

We will always need to have partition error tolerance.

So the question is do we prioritize consistency or availability.

Eventual consistency is satisfactory here, since 404 on a new link is tolerable for the increase in availability (but isn't this the same in this case? - i.e. we will either see 404 if we prioritize availaibility, or a rejection of requests if we prioritize consistency?

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.

Ok! I'll have a go.

1. Key Generation Service.
   1. How are short codes generated: MD5 hash long URL? And then encode in base 62? To shorten
   2. How do we avoid collisions: enforce uniqueness on the primary key, shortURL. If two users create the same shortURL, the second user will just regeneraye the hash again?
   3. Is it a standalone service?: it runs inside the write server
   4. Doe sit pre-generate batches of keys: no not required, the algorithm is lightweight.
2. Caching Layer:
   1. Circuit breaker pattern: If the caching layer fails, then the database would be flooded with requests. We can deal with this the circuit breaker pattern. Wrap the database API in a rate limiter. Once the number of requests exceeds a certain number, reject further requests with a stale cache response, or something similar. Meanwhile, a redis cache replica comes online.
3. Database Sharding
   1. Consistent Hashing works with a virtual ring with a fixed number of points (usually a very high number, which matches the hashing algorithm number space). Which items are stored in which DB is determined by by hashing the partition key. On the ring, the hashes before each DB's marker, until the previous one, fall in it's section. The DB marker is determined by hashing it's name with modulo [NUMBER OF DBs]
   2. When a node is added, it's marker is placed half-way between two existing nodes. Then, the first half of the subsequent DBs section's rows are moved into the new node's section.
   3. When a node is removed, all of the keys of that node then belong to the next node in the ring.
   4. Problem #1: Adding or removing a node places significant strain on one node (e.g. when adding a node half of a previous nodes rows must be moved, when removing a node, the next node then has lots of additional rows to be added). Solution: 'virtual nodes'. Instead of splitting sections simply by each DB, we create lots of duplicate nodes for each DB - each by hashing db_one_1, db_one_2, ..., db_two_1, db_two_2, ... Hashing this way naturally intermixes lots of nodes representing each DB, such that when a node is added or removed, the strain is spread between the other databases, rather than all being placed on one node.
   5. Problem #2: Hot-spots. Some keys are in far more/less demand than others, resulting in some DBs receiving more traffic than others:
      1. Solution: replicas: store the same row duplicated across multiple nodes, with traffic routed between them to even the load
      2. Key salting, create multiple keys, and spread the data between them. each key will hash to a different db, spreading the data, which will then be aggregated on read