System requirements

Functional:

List functional requirements for the system (Ask interviewer if stuck)...

1. Given a long URL, create an associated short URL.
2. Given a short URL, return the associated long URL.

Non-Functional:

List non-functional requirements for the system...

1. Availability - This service has to be highly available. Especially functionality (2) (redirection).
2. Response time - Functionality (2) has to have low response time, e.g., less than 10ms. This is to ensure that the short URLs should have low redirect time so that the users would have a smooth experience browsing. Functionality (1) (creating short URL) can takes more time - less than 10 seconds.
3. Scalability - We will get more and more requests to create short URLs, so the storage has to be highly scalable. We should use horizontal scaling as the system grows.

API design

Define what APIs are expected from the system...

1. shortenUrl
2. request: url (String), custom_url (optional String)
3. response: short_url
4. redirect
5. request: shortUrl (string)
6. response: url (string)
7. fetchAnalytics
8. request: shortUrl (string)
9. response: numberOfClicks
10. deleteUrl
11. request: shortUrl (string)
12. response: succeed / failure

High-level design

You should identify enough components that are needed to solve the actual problem from end to end. Also remember to draw a block diagram using the diagramming tool to augment your design...

The system should contain:

1. A client, which should be a web-app. This web-app should give users access to shortenUrl, fetchAnalytics and deleteUrl APIs. While the last API, redirect, is usually accessed in the web.
2. There should be some gateway that distribute the traffic accross service, so that read / write traffic can be distributed accordingly.
3. A UrlWriteService that handles the creation and deletion of short urls. As mentioned in the requirement, this service handles more complicated read / write operation, and also not handling redirection. It is acceptable that these operation could take longer time.
4. A UrlReadService that handles reading of urls, mainly converting short url to long url. Some popular long url is worth caching, therefore, this should also talk to the cache layer.
5. A database that stores all urls and their metadata, analytics.
6. A cache to help serve the high volume of read.

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

1. The server. We need to use a good algorithm to generate the shortened url. We could use [0-9][a-z][A-Z] characters in the url, and that makes it 62 characters. To make sure all urls are unique, we need to make sure the url is at least 6 characters in length. There are several popular ways to achieve this. We choose a here as it is simpler and with lower computational cost than b (no need to use hashing function), and it is more secure than c.
   1. Randomly generate a 6-characters long string, query the database to see if it exists, if not, stores the string in the database. Otherwise, regenerates a string.
   2. Using some hash function to generate a hash value of a url, check the database to see if there is a collision, if so, use the next 6 characters, and so on, until the string is unique. If the hash is used up, fallback to a. Commonly used hash functions are MD5, SHA, etc.
   3. Use the row id of the database as the url.
2. The database fits in the disk of a single machine, so partition might not be needed. However, to ensure high availability of the service, the database should have redundancy. There could be a replica of the database, which serves as a backup. When a server writes to the database, it should write to both replicas, and when it reads from the database, it could read from one of them. All in all, to preserve data integrity and conflict detection, make sure r + w > n / 2.
   1. Replication & quorum
      1. Use 3 replicas (N=3) across independent failure domains (different AZ/rack/power).
      2. Writes commit to a majority: W > N/2 (e.g., W=2).
      3. To ensure overlap for correctness: R + W > N (e.g., R=1, W=2 or R=2, W=2).
   2. Normal read/write behavior
      1. Writes: go to the leader, then replicate; commit after W acks.
      2. Reads: either from leader (strong) or from any replica (faster, but must define staleness).
   3. Split-brain / network partition
      1. Only the side with a majority quorum can elect/keep a leader and accept writes.
      2. Minority side becomes read-only (or rejects requests) to avoid conflicting updates.
      3. Use leader term/epoch + fencing token so an old leader can’t keep writing after it’s isolated.
   4. Generator / power outage fallback
      1. Avoid correlated power failure by placing replicas in separate power domains (different AZ / generator / UPS chain).
      2. If one site loses power:
         1. Remaining replicas still form a quorum → automatic failover, writes continue (W=2).
         2. When power returns, the down replica rejoins as follower and catches up from the log.
3. Similarly, there should be redundency of the server to maintain high availability.
4. We will need a cache layer, in this case Redis might be a good choice, as that will help caching most popular urls.
   1. In read path, the UrlReadService should read from cache first. If it's a hit, it returns the content. If there is a miss, it reads from the database and write this content to cache.
   2. Similarly, UrlWriteService should update the cache as well as database. For new records, it inserts it into cache. For deleteRecord calls, it should invalidate the record in cache.
   3. Set a TTL, say 10 minutes, to make hot urls stay in cache. However, if cache is full, it should evict least frequently used keys
5. In order to balance the loads of different shards of database, each shard can be mapped to the short urls prefix. If a shard happens to contain more popular urls than the rest, we can further divide it into different shards (say, one shard handling urls starts with a-d can be devided further handle a-b and c-d).
6. Use per-ip rate limiting
   1. Rate limiting can use token bucket, choose a refill rate R and capacity B based on traffic pattern
   2. In case of rate limiting, set the header of "retry-after" with an exponential delay to avoid bursts of traffic

Database design

Defining the system data model early on will clarify how data will flow among different components of the system. Also you could draw an ER diagram using the diagramming tool to enhance your design...

The system use one table only

Schema:

id: (auto increment) (PK)

shortUrl: varchar

url: varchar

owner: varchar # userId

expirationDate: datetime

numberOfClicks: int