System requirements

Functional:

• Two endpoints: one for creating mappings and one for resolving a shortlink
  • POST /shortlinks - takes a long URL and returns a short URL
  • GET /shortlinks/shortUrl - takes a short URL and returns a redirect to the long URL
  • in practice, we'd run the GET endpoint if a user enters <our_domain>/shortUrl

Non-Functional:

• Prioritize availability over consistency (it's ok if we take a short amount of time to propagate the mapping)
• Low latency on redirects (<200ms)

Out of scope:

• Link analytics
• Link admin dashboard for managing (like scheduling)

Capacity estimation

Assuming we have 1M shortlinks created per month, and let's assume we have 100x more shortlinks read than those created, that's:

• 1M POST /shortlinks per month
  • ~30K shortlinks written per day
  • 0.3 shortlinks created per second
• 100M GET /shortlinks per month
  • 3M shortlinks read per day
  • 30 shortlinks read per second

With this scale, we need only 1 machine + an additional for failover, however that assumes evenly distributed traffic. Even for bursty workloads, our POSTs should be fine, so I'd separate into a POST service and a READ service that gets the mappings, so we can autoscale our read cluster separately from the writes. For each cluster, we'd need to propagate them to two separate availability zones for failover. Long latency in practice comes to about 300ms which is too high for our low latency requirement, so we'd need to use geographic replication to maintain the SLA.

API design

• POST /shortlinks
  • BODY { "longUrl": "long_url_goes_here" }
  • RESPONSE 200 {"shortUrl": "short_url_goes_here"}
• GET /shortlinks/shortUrl
  • RESPONSE 401 if shortUrl doesn't exist
  • RESPONSE 302 to longUrl if shortUrl exists

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

High-level design

• Client request comes in
• We resolve it using a L7 proxy to either the read cluster or the writer cluster which sits behind L4 load balancers
• Both the read cluster and write cluster write to/read from the database
  • The writer cluster first writes to a distributed cache before persisting in the database, offloading read pressure

Request flows

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

Detailed component design

• How do we generate shortUrls?
  • We could use a hash of a distributed counter. In this case, we use Redis' INCR to increment a distributed counter atomically and just bijective map it to base62. This would ensure no collisions, but attackers could simply iterate from a given URL however and crawl all shortUrls.
  • Practically, we can just stop attackers through rate-limiting and malicious traffic analysis, but if we care to fix it at the root, we can first encrypt the counter using a small block size cipher like a 64-bit encryption algorithm. This gives us a sufficiently small, unique and bijective value that we can base62 encode. This gives us benefits of uniqueness (no collisions) and also prevents enumeration, but encrypting isn't free so this could slow down write performance.
  • When a URL mapping is created, we immediately add to the cache first and then the database.
• How do we expire URLs and maintain cache-DB consistency?
  • Most services maintain never expiring URLs, which is easy because the output space of 7+ character base62 shortUrl codes is extremely large and is almost guaranteed to never exhaust in a reasonable timeframe.
  • If we do expire URLs, like short aliases, we can use a TTL in the cache.
  • If a URL is expired in the cache, we assume the mapping does not exist. Since this would only really apply to aliased URLs, we can just wait until the next time a user wants to use that alias.

Trade offs/Tech choices

• Cache: Redis
  • highly availably, natively distributed, atomic counter ops built in
  • supports complex cache primitives beyond strings and more eviction policies -- main reason to use it over memcached
• Database: Dynamo
  • Simple, scalable, highly available, and we don't need expensive operations like JOINs (ding against Postgres)
  • Reads are extremely cheap
  • Our data is mostly KV mappings

Failure scenarios/bottlenecks

For scaling, our system should well to handle high read traffic and write throughput, however there are a few bottlenecks:

• Concurrent read connections
  • It's possible we get so many reads at once that we have too many connections to the DB. 20K connections is about the limit for a typical PostgresQL instance. For this reason, we'd pool the connections and choose a pool based on consistent hashing. We'd have a maximum number of pools and increase the current pool size based on the number of clusters (we'd tune this number so we can evenly distribute the traffic to pools), we choose the pool based on the hash of the host machine identifier.
• Geographic scaling the cache
  • We can propagate the popular cache values to a CDN which has international POP servers. We can also use LRU propagation to propagate based on the TLD of the longUrl, so we can move Indian short urls to servers close to India, etc.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?