Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.
• Short URLs range from 6 to 12 characters for the path.
• Long URLs can not be edited after short URL generation.
• No de-duplication of long URLs.

Non-Functional Requirements:

• Highly available
• Scalable
• Low latency

API Design

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

• Post /shorten
  • body: longUrl
  • returns: shortUrl
• Get /{code}
  • returns: redirect (PermanentRedirect)
• Delete /{code}
  • returns: Ok
• Get /stats/{code}
  • returns: Clicks, count at

High-Level Design

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.

Components:

• Shortening Services - contains APIs. Multiple Data Centers across the globe. Every Data Center has N number of service instances.
• Regional Redis Sentinel - Caches URL mappings regionally.
• Global KV store - Cassandra or Dynamo DB like NoSQL database.
• Kafka - Emit click metrics
• Metrics Workers - Workers listens to Kafka, batches stats on their end and periodically pushes to special container in KV store.

Short URL creation flow:

1. Clients send request to Shortening Service / Post endpoint
2. CDN runs rules if allowed forward request to Shortening Service
3. Shortening Service sanitizes request
4. Shortening Service checks rate limiting rules
5. Shortening Service generates identity and then base62 short key
6. Shortening Service puts data into KV Store
7. Returns Short URL
8. Asynchronously validate long URL by using external sources like Google Safe Browsing

Short URL get flow:

1. Clients send request to Shortening Service / Get endpoint
2. CDN runs rules if allowed forward request to Shortening Service
3. Shortening Service checks rate limiting rules
4. checks regional Redis cache
5. If not found, checks if data exist in KV store and fetch
6. If found, put into cache and return 301 redirect response to long URL
7. Emit metric to Kafka
8. Metric Workers pull data from Kafka and periodically push stats to another container of KV store

Detailed Component Design

Deep dive into 2-3 key components. Explain how they work, how they scale, discuss tradeoffs, capacity, and any relevant algorithms or data structures.

Short URL generation algorithm - URLs long varies, and they can be quiet long. Building short URL directly from Long URL is not a good idea as we have limitation requirement for short URL length. Better to generate numeric ID. The ID definitely should be unique, otherwise we risk ad creating duplicated short URL. So, IDs either should be incremented from the one source which can be either ID generation service or should be generated in distinct way. Auto incrementing is simple but naive approach and will slow down the short URL generation flow. I prefer Snowflake approach. Let's assign ID to every running data center and service instance. Snowflake has 64 bits. 1st bit is preserved, next 41 bit is milliseconds since custom epoch. IN original snowflake, next 10 ID is considered as machine ID, next 12 is auto incremented sequence ID on this machine during the specified millisecond. Considering URL generation is mostly manually triggered, and we can increase machine ID bits from 10 to 15, and leave remaining 7 bits for incremental number.

We may do simple base62 conversion. 62 because we have 26 letters, with both lower and upper cases it makes 52 and plus 10 digits. So, in the end short URL length becomes always 11.

If we want less characters, we can generate IDs incrementally in each DC, then the length of short URL will start with less than 6 digits and increase by usage. So, it is tradeoff. For simplicity let's assume we go for Snowflake here.

Security / Sanitizing - We should sanitize the URL, ensure it is valid. We may asynchronously run background tasks, fetch recently mapped long URLs, get their headers, and verify if they are dangerous or not. Also we may check if the long URL is safe by threat intelligence sources like Google Safe Browsing or internal blocklists.

Protection - Protection should be actual in Load Balancer level globally, and user specific limits, like no more than 5 post requests can be made.

For get flow, we return permanent redirection which keeps data in cache of browsers and CDNs at edge for a while. OUr services exposed to CDN only and not exposed publicky. CDN protects our services from bots, DDOS attacks, also we implement rate limiting rules.

Business level Rate limiting mostly needs to be applied to post and delete endpoint as throttling get not makes sense from busienss point of view beside attacks. I would use token bucket algo which allows byrst of traffic, and when throttles return 429 response with retry after headers.

Database - We should keep Long Url, the snowflake ID, created by which user in simplest form. We keep data in Cassandra/ Dynamo Db like Key-Value store because it is easy to replicate data across regions, implement sharding. We allow users to generate short URLs for duplicate long URLs. So, our read pattern is fetch long Url by ID. Which means as partition key we use ID.

We may need to store stats like data. How write ratio will be same with read ratio of main flow. For that reason, better to emit events to Kafka like system. If that flow has issues, main flow should be unaffacted. Better to not update stats for a while, instead of failing to process get and post requests. Kafka receives events and partitions them by short ID. Consumer groups reads in batches and keep in memory, and peridocically persist to special container in KV store.

Caching - Such services tend to have quiet higher read rates. We may receive quiet spike of get requests for popular short URL. We keep actively used data in per DC specific Redis cache. So during the read flow, Redis, later KV store.

As an eviction policy I would choose LFU. And also added some TTL which is equal to a few minutes. Anytime item in cache is used reset TTL.

When the short URL is deleted we delete immediately item from Redis cache.