Loading...
Assuming 10 million DAU and 10% of them creating URL we should expect around 1 million URLs created per day (12 per sec).
I will assume each short URL is accessed about 100 times per day which gives us about 1200 reads/redirects per second.
Each long url has average size of 50 characters, round up to 200 bytes + plus timestamp, ttl, short url and some overhead equals approx 500 bytes per URL. At 1m writes per day this amounts to 500MB per day, or 180GB per year. can be handled by a single DB for 5-10 years.
There are many more reads and the rows don't change often, so a cache can be put in front of the DB.
Endpoints:
Database: most of the load is reading and it is a search by short code; there is no need for relations between objects so a key value DB with good indexing and sharding capabilities will be good enough.
A cache in front of the database should save the most frequently used entries. Since entries get a ttl on creation this ttl can be set for them in the cache as well.
Because the performance and scaling requirements for writing and reading are different we will have a separate service for creating URLs and for reading. Both are stateless and can easily and elastically scale horizontally.
There is a load balancer in front of each service instances which can balance in a round robin way since the services are stateless.
All GET requests are served by a CDN to make sure the short URLs are resolved into the originals with the smallest possible latency.
Codes can be a base62 encoding of a monotonically increasing counter.
There are only two operations in the db: create and read by short code. Because the read is always by a single value we can use a key-value database where the short code will be the key and the long code will be ad document of the following form:
{"url": "...", "timestamp" : "", "time_to_live": "..."}. We need and index over the short URL for fast lookups.In this case the TTL would be implemented in app.
We could also use a SQL db which would also have an index over short code and the reads would contain a filter to make sure the expired records are not returned. Then we would need a separate process occasionally deleting the expired records.
If sharding is implemented the keys must be randomly distributed across shards to avoid hot shards.
If the shards are replicated we must also ensure a duplicate short-code is never inserted - so we need strong consistency on writes: once the mapping for a URL is written to a replica no other replica may receive a different value for the same key. On the other hand, when reading, if a read lands on a replica which still hasn't gotten the value, it is ok because it will probably be there on retry.
Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.
Generating the short url:
After receiving the original URL, the service will fetch the highest value of the counter, increase it and encode it in base 62 encoding. It will then save the value of the long url, the creation timestamp and the ttl in the db with the short code as the primary unique key. The enry will be written to the cache at the same time.
I'd use a shuffled base62 alphabet to encode a scrambled counter — sequential internally, unguessable externally.
Multiple short URLs are allowed for a single long URL because they may be created at different times with different TTLs.
Alternatively, we could first check if the long url already is in the db and then return the short code after updating the ttl in its entry.
The endpoint must have a rate limiter per IP, for security reasons.
If the short URL is removed it needs to be purged from the database and cache.
Redirecting to the long url:
A request for the short url will first hit CDN, if the cache entry exists it will be served from there and a 302 response will be served with the appropriate CAche-Control headers (max age can match the ttl of the url). If not, the redirect service will search for the long url in the cache, if the entry is expired it will search in the DB where it may find the entry. The entry may be expired in which case the service should return a 404 and issue a delete command.
Cache: every write to DB will first be written to the cache with a individual TTL. The entries may be deleted from the cache if they are not frequently used even before the expiry of the ttl.
1. Cache stampede (thundering herd) If a viral link's cache entry expires while millions of requests are arriving, every request would miss the cache and hit the database at once, potentially overwhelming it. Mitigation: single-flight / request coalescing — only one request per key is allowed to query the database and repopulate the cache; all other concurrent requests wait on that one. Hot entries are also given lazy TTL refreshes so they aren't evicted while still in heavy use.
2. ID generator failure (write-path SPOF) The centralized counter is the only component that cannot scale horizontally — if it goes down, all create requests fail. Mitigation: shard the counter into disjoint ranges — each ID-generator node owns a block of codes (e.g., node 1 owns 0–1M, node 2 owns 1M–2M) so it can generate codes independently without coordination. This removes the single point of failure and still guarantees uniqueness.
3. Cache node crash A crashed cache node isn't fatal — reads just fall through to the database. The risk is the sudden traffic spike on the DB. Mitigation: treat the cache as an optimization, never the source of truth; keep the database with enough headroom to absorb a full cache-miss storm. The tombstone-in-DB design ensures correctness even when cache is gone.
4. Database failure Reads survive via replicas, but writes (creates) fail. Mitigation: automatic failover to a standby primary for the write path.
5. Replication lag A newly created URL may briefly 404 on a read replica that hasn't caught up. Mitigation: acceptable as a transient error — but the create response is only returned after the write is durable, so the 404 window is small.
6. Slow downstream dependency If the database hangs, every redirect could block on a slow query, causing request pileup across the service. Mitigation: aggressive client timeouts and circuit breakers — fail fast with a 500 rather than queue up and stall the entire service.