Requirements

Functional Requirements:

• For a given user, support up to N URL mappings
• A given mapping must provide an HTTP redirect to it's source URL
• Two shortcuts can be mapped to the same source
• The user should have the option to provide a custom mapping, default is random
• There should never be a collision in shortcut assignment
• User should be able to retire a mapping (or when their is account is closed).
• The user should be able to edit their existing mapping
• Only the owner of the mapping can edit the mapping

Non-Functional Requirements:

• 1000 Mappings requested per second
• Assume redirect service gets 1M RPS
• Redirect should occur within 20ms (that's our 99.99% SLA)
• The mapping creation should take less than 5 seconds
• URL should be as short as possible and still avoid collisions
• The redirect service should have 99.99% uptime since this is the primary business function

Capacity Estimation

Estimate the scale of the system. Consider daily active users, read/write ratio, storage requirements, bandwidth, and any relevant QPS calculations...

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

State:

> Mapping

>> CREATE /mapping/create

JSON body

• destination
• custom-mapping

>> UPDATE /mapping/edit/

JSON body

• destination

>> DELETE /mapping/delete/

No body

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.

State = mapping

Storage:

• KV store for READ (eventually consistent)
• SQL for creation

Services:

• Random Slug Service
  • Creates a queue of random slugs to use for the next mapping
  • The service has a job that checks the size of the queue, when queue is below say 500 slugs, generate another 500 slugs.
    • Use an algorithm that uses randomization to generate the slug
      • alphabet for a slug is [a-zA-Z0-9] < gets us 62 characters per letter in word. Assuming len 6, then 62^6 ~57B. Therefore at 7 letters ~ 3.5T
      • At len 7, 3.5T mappings, at 1K mappings per second. 3,600,000 per hour.
      • therefore 1M hours before worrying about collisions. 1M / 24 / 365 = 114y we start to worry
      • Let's stick with 7.
    • Check if the slug exists in the SQL db
    • if not used add to queue
  • When a service requests a slug from the queue, first remove it from the queue, then return it.
    • Queue access is synchronized. This way, two mappings cannot ever use the same slug.
• Mapping Service
  • Create's mapping by taking the customer url, and pairing with the next slug from the SlugService queue
    • optionally attempt to assign the custom slug provided by the customer if provided
    • add mapping to KV store
  • Update a mapping:
    • Check if the user owns the slug, else return 403 Forbidden
    • Then update mapping in KV store (eventually consistent)
  • Delete a mapping
    • Check if user owns the slug, else 403
    • Delete the mapping from the KV store
• Redirect Service
  • Requires high scale to support all the customers, therefore we will use an Load Balancer in front of a scalable service. E.g. ECS with paired with Auto Scaling group so during busy hours (9-5) we can scale up
  • Service takes slug, find it in the KV store, return
  • To Promote faster responses, we can utilize a redis cache, use LRU for eviction

Database Design

Define the data model. Identify the main entities, their attributes, and relationships. Consider the choice of database type (SQL vs NoSQL) and justify your decision based on access patterns...

Account Table:

accountId (PK) | Name | Address | Status (active)

Slug Table

slug (PK) | accountId

KV Store

slug | url

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.

Let's talk about slug generation and how to make it scale. Here's the plan.

We shard SQL DBs on slug. eg.

The first three letters have 62 * 62 possibilities = 3, 844, Let's divide this into 100 shards

Now we have multiple slug jobs, where each job also divides its work be randomly choosing the first two letters within a give shard range, (i.e. 100 different ranges), and then the last 5 letters are completely random using entropy.

Each customer account, on creation is assigned to one of these 100 shards.

Therefore that customer will ALWAYS use slugs that starts with letters that are part of their shard.

e.g. assume the first shard is aa - cc then, all slugs first this customer start with that range:

aaGGTT5, bcYY779

Consider:

> slugs are sharded into 100 groups. Therefore at 1000 RPS, only 10 writes are attempted per shard

> Also consider that the slugs are NOT derived on demand, but in advance, so the expensive computation is offloaded

in asynchronous jobs

> The ONLY real bottleneck is the Write contention on slug creation, and assignment of slug to account. But at 10RPS per shard, we should be able to handle this.