Requirements

Functional Requirements:

• Create a short URL for a given long URL.
• Return the long URL associated with a given short URL.

Non-Functional Requirements:

• High availability
• Low latency for READs, a single user request is effectively 2 requests - One for getting the long url and redirection.
• Scalability (Horizontal)

Capacity Estimate

Assume,

100M Reads, 1M Writes per day

R/W = 100 (For every URL created, it is used on avg 100 times)

Peak Read: 10% - 10M reads per second

Peak Write: 10% - 100K writes per second

Assume,

(long_url, short_url, timestamp) + other metadata is about 100KB per row.

So,

1M * 0.1MB = 100GB per day

100GB per day,

36.5TB per year.

Assume, 10 year retention - 365TB of storage.

Assume, Data beyond three years has less than 10% of recall rate, so ~100TB in hot storage, rest can be archived.

API Design

POST /url-shortener/create

Req: Long URL

Res: Short URL

GET /url-shortener/{short_url}

Res: Is a redirect to the long url

Assume, Auth, Edit and Delete are out of scope for this.

High-Level Design

Client sends a request which is routed to geographically most available instance.

For READ, the request is checked against the server cache first then a read replica.

For WRITE, the request is checked for uniqueness and then write back (first cache then DB)

Database Design

Table:

PRIMARY_KEY UUID (since multi instance)

SHORT_URL is generated by a hash of the long url.

LONG_URL is stored as it is for future redirection.

CREATED_ON is timestamp when it was created.

Detailed Component Design

The system is heavily READ. For high availability, we can have a combination of Cache and Read Replicas. READ is expected to have low latency. Immediate READ after a WRITE is not expected, we can have a cache first write back then synced to DB and other replicas.

Tradeoffs:

There is latency between WRITE and first READ.

For preventing attackers,

We can use a combination of SALT and timestamp based approach, so attacker can't replicate the URL generation.

ID Generation Strategies:

Auto Increment (Sequence):

Pros: Short Size, Fast

Cons: Needs Syncs across multiple instances

UUID

Pros: Fast, Non duplicate

Cons: Large Size Defeats the purpose of short

Twitter Snowflake:

0 + TIMESTAMP + NODE_ID + SEQ_NUM

Pros: Fast, Compact

Cons: Needs Sync Clock, clock drift can cause duplicates.

Redis:

Central Redis Node will have Distributed counter

Pros:

Fast, Compact

Cons:

If redis fails then duplication is possible, loss of data.

Sharding:

Assuming unique distribution of the spikes across all the primary key, we can use the primary key as the shard key.

Caching Strategies:

Cache Eviction Policy: LFU (Least Frequenctly Used)

If URL is disabled/updated, we can implement a PUSH based model to update the cache.