System requirements

Functional:

• As a user I can submit a form that contains a target URL field
• As a user, when I submit a valid URL via the form, I am shown a confirmation page with my short URL.
• As a user I receive a validation error if the URL is not in the correct format, encoding, etc.
• As a user, when I visit the short URL, I am 301 redirected to the long URL.

Non-Functional:

• System should hash the URL using a hashing algorithm to create the short URL slug.
• System should truncate the hash created to a variable length defined via configuration.
• System should avoid generating the same URLs more than once (avoid hash collisions)
  • Generate a UUID: When a new URL is submitted for shortening, generate a UUID for it.
  • Base62 Encode or Truncate: UUIDs are 128 bits, which translates into a long alphanumeric string. To make them suitable for URL shorteners, you would either:
  • Encode the UUID using Base62 to create a more compact, shorter representation.
  • Truncate or take a segment of the UUID and convert that segment into Base62 to fit within a 5-character limit.

3. Create the Slug: The final slug could be derived from the encoded or truncated version of the UUID to produce a relatively short identifier for use in URLs.

• System should be able to scale web form requests and API requests separately.
• API requests should be routed to multiple API service instances that autoscales as requests to the API spikes.
• System should save a record to the database, one column for the slug, another for the UUID (primary key), and another for the target URL.
• On lookup, system should save short URL and corresponding target url to application memory (e.g. Redis) to ensure fast retrieval from the application memory.
• URL / Slug generational should resolve in less than 50ms
• URL / Slug retrieval from the API should return in less than 100ms
• Page Redirection should resolve in less than 200ms
• Monitoring and Logging is required

Capacity estimation

• Creator visits: 10,000 per day
• URLs generated: Avg of 3 per creator visit (30,000/day)
• Database Storage
  • 30,000/day x 365 = 10,950,000 urls created per year
  • 10,950,000 records x 241 bytes/record = 2.63895 giga bytes per year (minimum capacity needed for database size for the first year)
• URL visitors (redirects): 100 avg per link per day.
  • Total traffic is ~2,000 concurrent requests per second (based off of 10,950,000 urls created in the first year visited 100 times per average)
• API requests should be minimized by Application Memory Caching. Since values are cached on creation, roughly estimating 20,000,000 reads from the the DB per year due to cache ttl changes (20 reads per second), and 10,950,000 (20 writes per second) if 30,000 are being created per day.

API design

1. /url/create (POST)
2. /url/:hash (GET)

Database design

The database design for this example is pretty simple since we don't have authentication.

Table: SHORT_URL

1. UUID numeric (PK)
2. slug varchar(5)
3. target_url varchar(200)

High-level design

1. Client
2. Web Server (HTTP requests, returns HTML)
3. API Gateway
4. Load Balancer ( Distribute traffic to multiple instances of API Service)
5. API Service (Generate slugs, Saves to the Database, Adds records to cache, Returns short URL to Web Server)
   1. Auto Scaling
6. Redis Cache (Application Memory)
7. Database (Aurora / Postgres)

Request flows

Create Flow

1. Client submits data via HTTP to Create the short URL
2. Web Server validates data and submits to the API via /url/create (POST)
3. Request is first received by the API gateway and is routed to the Load Balancer
4. Load Balancer checks to see what API service to hit and submits data
5. API Service generate the correct hash and UUID for the record
6. After successful creation, the API service creates the cache record in Redis and returns the appropriate data upstream

Read / Get Flow (Redirect) - CACHE HIT

1. Client sends request to Web Server
2. Webserver understands target URL has been requested
3. Webserver attempts to retrieve target data from Redis Cache and is found
4. If cache record exists, it returns a 301 redirect to client.

Read / Get Flow (Redirect) - CACHE MISS

1. Client sends request to Web Server
2. Webserver understands target URL has been requested
3. Webserver attempts to retrieve target data from Redis Cache and is not found
4. Webserver requests the data from via API gateway -> Load Balancer -> API Service -> Database

Webservers, ALBs, API Service and Databases all send logs and metrics to Cloudwatch.

Detailed component design

1. Web Server is a containerized application in AWS ECS with Autoscaling
2. AWS API Gateway, allows for routing and normalization of data
3. API Service is containerized Python Application Living in ECS with Autoscaling
4. Database uses AWS Aurora for autoscaling
5. Redis is also hosted on AWS.

Additional notes

1. To make this fault tolerant, replication to multiple regions and Availability Zones should be considered.

Trade offs/Tech choices

1. We could simplify the architecture by using Serverless Lambda function for the API Service, which would scale on demand. As a managed service is would be less costly. Additionally, it would remove the need for a Load Balancer. On the other hand, having it live in ECS allows for more control.
2. Chose API Gateway since it allows for normalizing data.
3. Chose Aurora (Postgres) for Database as it autoscales and allows us to have a read and write node. As the application scales, we can may want to create more complex data decisions that require complex joins.
4. Application memory via Redis Cache allows for micro second retrieval

Failure scenarios/bottlenecks

Main bottlenecks would be the read from the database, as spiked requests directly to the database can slow the application down.

Future improvements

Future improvements to the applications functionality:

1. Ability to login and do CRUD operations on URL
2. User can see analytics for each visit
3. User can chose a custom domain
4. Add DDOS attach protection via Cloudfront or Cloudflare
5. Add Web Response Cache (cache URL redirect) via CDN.