Loading...
100M new writes per day with 100:1 read ratio.
Approximately 1200 writes/s -> 120k reads/s
Permanent links by default, TTL optional for 24h/7d/30d
Original link average size -100-200bytes - upper bound of 2048
Shortened form approximately 7 char base62 (0-9, A-Z, a-z) unique id
Approx 1kb per set of links
Total 36.5TB/year
Redirect path < 100ms p99
Creation path < 200ms p95 as it is not user-facing
Scalability
As above functional requirements + need to scale app/db/cache independently
Reliability
99.99% reliable
Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...
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...
create link: input long url -> receive short form url
redirect shortened link : input short form url -> receive long form url -> perform redirection via DNS
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.
For write API -> Client, client requests url shortening through CDN to a load balancer to the server to hash url. URL with shorterned is writen to hot DB as a key-value pair and sent back and stored in CDN on the way back to client. Client is now able to share the shortened link. Optional settings for client to set TTL. A backend worker process will periodically remove links that have expired.
For read API -> client requests with a shortened link. If CDN has the link in its own key value store, it will return it to the client which can be used to lookup DNS to access the actual site. If CDN does not have this link, it will request it through the load balancer and main servers. If the key exists in the hot store, send it to the CDN to store it for future users and return the original link to the client.
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...
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
Shortener algorithm is based on an auto-incremented integer that is encoded in base62. This will ensure that no two links return the same shortened value. However, this causes a write bottleneck. We can then use range batching where each server is assigned blocks of integer IDs (10k) and autoincrements independently. Even if the id block generator fails, servers will continue assigning based on the current block until generator comes back online
To obfuscated against crawls, we can XOR the ID with our own encoded secret. This will create values which jump around unpredictably.
As data amount is extremely high, sharding is expected. We can use the same auto-incremented value as a shard key. Suppose we have 10 shards, we mod 10 to get the remainder to get the shard value to store in.
Master - slave setup where master performs writes while slave provides read. We aim to scale up the slave since reads are 100x more when read traffic spikes. To soften the write spikes to the master, we implement a FIFO queue with a throughput of 2x 1200/shards so that it is able to hit average with 50% throughput and has buffer to accommodate spikes.
If there is an edit/regenerate function, we implement cache invalidation by writing through the CDN when it gets the new shortened link for an existing long link.
We also implement a rate limiter to limit based on IP throttling and exponential backoff to prevent abuse.
CDN to optimize traffic based on geography as a trip to the main servers is extremely costly for most places in the world. The first user will suffer a cache miss and a long time to return but subsequent users will be extremely fast.
Ideally we can push the data to CDN whenever it is created by the main server or even created by the CDN server itself since it is light weight. However, this will mean we will need to content with replication logic and it is simpler for a main server to handle the work. Potential to have CDNs host lightweight servers and simple replication for hot spots but not necessary. Main server should always be present for things like billing and account management.
Postulate that old links get rarely used. A process can be ran to check if links are no longer in use after a long time and can be moved over to a cold db that is cheaper and optimized for writes. Long time can mean >1 year, it depends on the use case. If the url is ever requested and the original link cannot be found on hot db, we can lookup the cold db. However this does add extra overhead for links that dont exist since a cold store read can be expensive. This is mitigated by the fact that most people share proper links and dont tend to type (and make mistakes) manually.