URL Shortener System Design — Architecture Decision Records

Introduction

The purpose of this article is to analyze and digest the URL shortener system and practice the ADR. It’s just a practice, not for the real case.

In this article, we will list challenges and focus on the key decisions.

Agenda

• Understanding Requirements (defining scope)
• Challenges, Estimating Scale, and Bottleneck
• System Design Overview
• Technical Stack & Infra
• Workflow
• Architecture Decision Records

Understanding Requirements (defining scope)

Functional requirements

• Shorten a URL (URL shortening)
• Accept a valid long URL and return a shorten URL
• Example: [https://example.com/article?id=1234](https://example.com/article?id=1234) ⇒ [https://tinyurl.com/xYz12](https://tinyurl.com/xYz12)
• Redirect to original URL (URL redirection)
• When accessing the short URL, redirect to the original long URL
• Prevent duplicated short URLs
• If the same long URL is submitted, return the same short URL or handle according to configuration (unless custom alias is used)
• User authentication
• Allow users to register/login to manage URLs, view analytics, and set expiration

Non-functional requirements

• High availability (HA)
• system must be available 24/7 with 99.9% uptime
• Low latency
• URL redirection should occur in milliseconds
• shortening URLs should be near-instantaneous
• Scalability
• system must handle millions or billions of URLs, supporting high read volume (URL redirection) and moderate write volume (URL shortening)
• Reliability
• ensure data persistence
• no data loss even during failures (replication, write acknowledgment / quorum)
• use durable storage and backups

Unique URL Generation Strategies

• Random string generation: create a fixed-length string from random characters
• unpredictable, no obvious pattern
• risk of collisions, requires collision handling
• okay for unpredictability, but adds complexity
• UUID (Universally Unique Identifier): 128-bit globally identifier
• guarantees uniqueness, no central coordination
• very long, not user-friendly
• not ideal for TinyURL due to length
• Hashing with salt: hashes the original URL (e.g., SHA-256 + salt)
• unique, secure, hard to reverse
• may not be short, collision possible, needs mapping storage
• useful for security-focused cases, but not optimal for shortening
• Base62 encoding: converts incrementing ID to Base62 (0-9, a-z, A-Z)
• short, compact, deterministic, easy to implement
• needs counter management to avoid collisions
• recommended for TinyURL (fast)

Challenges, Estimating Scale, and Bottleneck

Estimating Scale

• Estimated user traffic
• Daily active users (DAU): 10 million
• Monthly active users (MAU): 300 million
• New Short URLs/day: 100000 (1% of DAU)
• Redirect requests/day: 50 million (5 per user)
• Memory requirement (hot URL cache)
• cache top 1M most accessed URLs
• each mapping: 500 bytes
• total memory: 500 MB
• Network bandwidth (URL redirection)
• 50M redirects/day * 700 bytes = 35 GB/day
• avg throughput: 0.4 MB/sec
• peak throughput: 5 MB/sec

Data Size & Storage needs

• Storage requirement (URL mapping DB)
• 100K new URLs/day * 400 bytes = 50 MB/day
• Yearly data = 18GB + overhead
• Round up to 50GB/year (with indexes, logs, backups)

Challenges and Bottlenecks

• High read volume
• focus on cache and fast DB reads
• Write throughput is moderate
• unique URL generation: base62 + zookeper
• prevent duplications: single-key atomic conditional write
• durability: write acknowledgment / quorum
• Latency sensitivity in redirects
• low latency infra needed
• Plan for burst traffic with autoscaling & CDN support

System Design Overview

CAP Trade-off

According to the non-functional requirements, we may have to choose AP in this application.

For most operations, users can afford eventually consistency between different nodes. Also, the low latency means we may have to give up the consistency.

However, the consistency is important for custom alias operations (this feature is not in our case). For this operation, they should be CP. CP will avoid conflicts.

Components Diagram

There are a few important components in the following diagram.

• URL Generation service (URL Shorten service)
• contain logic for key generation, duplicate checking, alias validation
• Redirection service
• high performance resolver for short keys ⇒ long URLs
• User management service
• handle user authentications

Technical Stack & Infra

Collision Handling in Distributed URL generation — Zookeeper

• Why collisions happens?
• Multiple services generating IDs independently ⇒ risks of duplications
• No global configurations ⇒ Base62 encoding same ID ⇒ incorrect URL mapping
• What is [Zookeeper](https://zookeeper.apache.org/)?
• Distributed coordinate service by Apache
• Ensure synchronization across nodes in distributed system
• Zookeeper as a solution
• automatic ID generation using Zookeeper-managed global counter
• guarantees each instances gets a unique ID
• use znodes to store and manage counters
• supports distributed locking to serialize ID generation
• Flow
• service requests next ID from Zookeeper
• Zookeeper increments global counter atomically
• ID is Base62 encoded and used as TinyURL - mapping stored in DB (optional)

API Gateway

• Request routing
• Authentication (verify JWT locally), authorization
• Rate limiting => throttling

Authentication

• Implement OAuth 2.0 with JWT token for secure, stateless auth

Storage & Database

• Relational DB (e.g., PostgreSQL with incremental IDs)
• users
• NoSQL DB (e.g., DynamoDB for scalibility)
• mappings(short URL -> original URL), metadata (owner_id, created_at)

Cache

• Redis or Memcahced for high-speed lookup

Infra

• horizontal scaling for URL generation services (scalability & performance)
• load balancer to distribute traffic across service instances (high availability)
• failover-ready infrastructure using cloud-managed DBs or services (high availability)
• replication in DB to avoid single point of failure (high scalability, high availability)

Workflow

The following sequence diagram shows how components work together.

1. URL Generation

• Client application
• User submits long URL to the API Gateway
• API Gateway
• Verifies JWT locally
• Send the request to the URL Generation service
• URL Generation service
• Check if the generated TinyURL is existing, if so, return the result with the generated TinyURL
• Request a unique ID from Zookeeper (ensure no collisions)
• Encodes it (e.g., Base62 ) to create the short URL - Stores the mapping to DB and Redis cache (long URL → short URL) => write-through strategy
• Return the result with the generated TinyURL

2. Redirection Flow

• Client application
• User hits short URL
• The request will be sent to the API Gateway
• API Gateway
• Forwards to the Redirection service
• Redirection service
• Checks cache for the short URL (fast path)
• If not found, queries the DB (cold path)
• Redirect user to the original long URL

Architecture Decision Records

ADR 1. URL Generation and Redirection Share a Single Mapping Store

In our scenario, the DynamoDB is used by the URL Generation service and the Redirection service. It violates the database-per-service principle of the microservice architecture.

The reason is the latency sensitivity in redirects. It will add the additional latency to the redirction operation.

ADR 2. Cross-Database Short-Code Ownership via DynamoDB owner_id and GSI

In this project, we use the polyglot persistence strategy for databases.

• mappings(short URL -> original URL), metadata (owner_id, created_at) => use DynamoDB (high capacity, high frequency, key-value, eventually consistency)
• users => use PostgreSQL (low capacity, relational-query, strong consistency)

Because tables are in different database, we need a solution to list short URLs for an user and find the owner of the short URL. Our solution has 2 items.

• Add a field owner_id in the metadata table (DynamoDB), the field points to the user_id of the users table (PostgreSQL)
• Create global secondary index (GSI) and specify the owner_id field as the alternative primary key

def list_urls_by_user(user_id):
    return dynamodb.query(
        IndexName="owner_id-index",
        KeyConditionExpression="owner_id = :uid",
        ExpressionAttributeValues={":uid": user_id}
    )

Reference

• Mastering System Design: From Basics to Cracking Interviews

Summary

Thanks for your patient. I am Sean. I work as a software engineer.

This article is my note. Please feel free to give me advice if any mistakes. I am looking forward to your feedback.

• The Daily Learning website

[embed]Search Articles for Web Development | ALayman Daily Learning ALayman Daily learning provides articles, challenges, or videos to people who are also self-learner for programming.www.alayman.io