Requirements

Functional Requirements:

• User can generate the short URL with QR Code from provided URL
• The short URL is immutable, so it cannot be delete
• When user click the short URL or scan the QR code the user will be redirect to the origin URL

Non-Functional Requirements:

• High Availability: the service can serve 24/7
• The redirection latency should lower than 100ms
• Support 1 Billion QR Code generation and 100 Million Users.

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

### Create a short URL and QR code

POST v1/short_url

Body

{

url

}

Response

{

token

}

### Redirect to the original url

Since we choose to use the immutable short url so the redirect status code can be 308 not 307.

GET v1/short_url/:token

Response

308 status code permanent redirect

Location: origin_url

### Get the QR Code image

GET v1/qr_code/:token?dimension={dim}&border={border}

Response

{ image_location }

High-Level Design

### Short URL creation flow

Client => API Gateway => Short URL service => DB

• The user call the `POST /v1/short_url` with request body `{ url }`.
• The service check the request URL is valid or not. If yes, generate the unique token for the URL and save it to the DB
• The token must be unique in the whole service
• Server responses the `token` with `201 Created`

### Redirect to the original URL

Client => API Gateway => Short URL service => DB

• The user call the `GET /v1/short_url/:token`.
• The gateway check the URL whether cache or not. If yes, it response the cache http response directly to trigger the redirect. If not, pass throught service.
• Server valid the token first, if valid, access the DB to find the origin URL and response the 308 with `location: origin_url`

### Retrieve QR code image

Client => API Gateway => Short URL service => DB

• The user call the `GET v1/qr_code/:token?dimension={dim}&border={border}`.
• Server valid the token first and check the DB to make sure the token existed. And generate the QR code image via the token and response the image to the client.

All the invalid token response 422.

If we need more closable cache for user we can add CDN as the first layer instead of API gateway for user to cache the URL mapping or QR Code image on CDN to reduce the service loading.

Database Design

Relation Database

Table ShortURL

{

id uuid primary_key

token string unique

created_at timestampz

url string

}

I will chose the relation database, but this service use the object database is also workable.

~200GB total data fits on a single node; immutable URLs + CDN-cached 308s keep DB read load minimal, so a single relational DB with one replica suffices.

Detailed Component Design

### Unique token generation

We need enough entropy to generate the unique token. So, we can use the sha-256 like hash function to generate the fixed number hashed value. The hash function transform the URL to the deterministic fixed number string. Since we need to prevent the the same URL generate the same hash, we can use the secret or nonce generate by the random number to make the hash totally random.

After hashing we need to shorten the token size to improve the transfer and readable. But we should consider the collision probability to handle shorten. This is depends on the key space and total URLs we assume to save in our service. I choose to use base62 which have 62 keyspace. In our case, we need to support at least 10B urls, so the 6 digits is enough for us which can cover around 50B tokens.

### Redirection Latency

1. Indexing the token and we use unqiue above so we have indexed the token in the DB design
2. Caching

CDN cache the URL mappings when user first access. so the rest of user can access it from cache on CDN directly to reduce the origin service loading. Since our token's URL is immutable so we don't need to consider the cache invalidate in our case.

Since all redirects are served from the CDN cache, a viral link never hammers the origin DB — the CDN absorbs the hotspot.