Loading...
8 characters max url
Not using a predictable sequence to generate urls
No overwriting an existing url - each entry is immutable
Leverage 302/307 redirects (non-permanent) for better analytics
(but has a perf hit)
Users can be across multiple regions
No custom url generation
1M new urls generated per day
10M urls read per day
1:10 write/read ratio
highly available, reliable, low latency
"eventually" consistent
1KB per url
No widely variable peak traffic
Rate limiting for abusive users
1e3 bytes/url * 1e6 urls/day * 400 days/yr -> 4e11 bytes/yr
-> ~400 GB/yr
1e6 urls/day * 400 days/yr -> 4e8 urls/yr
8^62 possible urls can be generated from 8 chars
(2^3)^62 -> 2^65 >> 4e8 urls/yr
POST:
/api/v1/create_url
body:
{
"url": "abc.com/some-long-url"
}
response:
{
"short": "bit.ly/avDwdwi2
}
GET:
/api/v1/
301 or 302 to the original url
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...
KV store:
key value
short_string -> original_url
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...
web client: sends requests to create or fetch a shortened url
api server
database
optional / for scale:
caching, load balancing, db read replicas, api server replicas, etc
Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...
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...
api server: stateless, behind a load balancer. Connects with database. Would handle auth or call to an auth service as well.
distributed KV store: shard data across multiple instances
"single leader, multiple follower" replication model, since the system is read-heavy
if leader goes down, elect a new leader after replication completes
cache: read-through cache, since each url is immutable
Explain any trade offs you have made and why you made certain tech choices...
302 vs 301: 301 has better perf since it leverages client-side caching in their browser, But 302 is better for our analytics so we can see our urls in use.
shortened url generation: hashing vs id generation
hashing is random, but risks collisions.
Id generation requires an id generator, and can result in predictable urls
Try to discuss as many failure scenarios/bottlenecks as possible.
collisions: we retry by appending a random/benign string to the input url each time, until we get a new url that isn't already saved. The space of 8^62 urls is sufficient to prevent too many collisions from happening.
failover: db server goes down: read-replica vs leader
api server goes down - another api server can handle those requests
db replication to avoid data loss.
cache restart: "pre warm" the cache upon restart
no need to worry about cache invalidation since urls are immutable.
Rate limiting to prevent DOS on writes
What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?
Configurable 301 vs 302 redirects, based on user settings.
use read-through caching for better perf
Support custom url generation
optional: leverage CDN to improve latency when requesting the most popular urls