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

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.
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.
Similarly, there should be redundency of the server to maintain high availability.
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
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).
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

Submissions

Displaying Solutions with Scores Ranging from 1 to 10

Submissions

Displaying Solutions with Scores Ranging from 1 to 10