Loading...
Take a new URL input and encode it (and return it)
Fetch a URL by ID
Store somewhere
Redirect
Allow reporting suspicious links
CDN for caching
High durability - (write durability more important than write latency, a small delay is fine) once a write is acknowledged it should basically never be lost
Redirect latency - must be fast. this means that _reads_, which are going to be the more common path, have to be optimized.
Availability/Fault tolerance - should be highly available. frustrating to end users if down
Scalability - should be horizontally scalable. should be straightforward - must read from a central datastore but there isn't a lot of synchronization required across instances. Ideally, can be configured by load balancer or similar to spin up on
100M DAU
~ 0.1 URLs/day (optimistic)
This is 10 million writes per day, or ~100 per second, spiking to a few multiples of that during peak hours
Read:write ration 1:100 -> 1B redirects/day
Redirect QPS ≈ 1B / 86,400s ≈ 11.6K reads/sec steady state; plan for ~30K QPS peak
Storage
~ 500 bytes per mapping (metadata ~100B (maybe!), 200B URL (probably), 7 byte key)
10M writes a day brings us to ~2 TB/year
Growth
Because this is terabytes of data after a year, we absolutely must archive after a few years maximum. There are a number of possible places to archive it
Very straightforward:
PUT: takes a url, generate key, store
Return a shortened URL.
GET: takes a key, returns the
Cache with varnish/Fastly/Cloudflare/similar
On Write:
Client writes to server via LB. no cache.
Server generates unique key
Server writes to datastore.
After X period, this document gets archived.
On read
Cache hit - return url with redirect
Cache miss - load balancer calls server, server fetches URL from the database. The server then uses that to warm the cache. Return to user.
Use a dynamo db style KV store for the mappings table. Partition key = short key. this makes lookups extremely fast and easy, and can easily TTL/maintain strong write consistency and handle read loads. reads can be eventually consistent as a transient read error right after creation is not an issue.
mapping = short_key: {url, metadata, timestamp, creator, ...}
Cache strategy:
TTL can be fairly extensive. Don't want it to be forever, because the link could rot/occupies cache space/risks serving malicious or stale data longer if we can't do it. I'd say a month and tune as needed.
Eviction policy: reports of staleness, unlikely event of database mutation (Eg for administrative purposes)
handling cache misses under a thundering herd - request coalescing is a good first line of defense. implement an inflight request key. some synchronization is necessary so requests don't race between check and insert. this limits it on a per server instance, which is a caveat but should be good enough for a front line before the cache warms. (other options might include db read replicas)
Sharding the mappings table:
This can be done around consistently hashing the short ID, so that each ID is reliably sharded to a single location. don't have to gather results. hot shards are protected by the CDN. Continually resharding is expensive. we should continue archiving to avoid it. if we absolutely have to, we can establish a new routing table, and migrate the shards in batches, switching over and verifying. we can dual write during this migration. but this is painful. it's better to avoid it via archiving.
ID generation - this makes sense as a base62 encoding of a randomly derived. Counter based ones, even when made less guessable, become a coordination concern. Cost of a retry is relatively low and we're already sacrificing latency, so let's retry on collision.
Abusive IPs can be rate limited by drawing down from a token bucket per user. If they make two many requests we can hit them with a 429.