System requirements

Functional:

create a new tiny url

update/delete an existing tiny url

uniqueness of the generated tiny url

Non-Functional:

randomness so that web crawler cannot iterate through all the data by finding a pattern

ttl based or permanent url mapping?

different customers create different mappings for the same url

do we allow multiple tiny urls for the same web address?

Capacity estimation

create qps: < 100

delete: < 10, optional, or can even be ignored

no update allowed atm

so let's just use 100 as the total write qps volume

plus, write qps should be relatively stable.

lookup: 10k, with traffic surge: 3x

number of entries calculation:

new url entries generated per day : 100 * 3600 * 24 = 8.64M

let's assume we do have a ttl of 30 days. So the total number of entries we need in the storage for is 8.64M * 30 = 260M

url length: 2083 characters each 1 bytes so 2k bytes per url. Let's use average number of 1k for simplicity.

total storage is 260M * 1k bytes = 260G

API design

create(string originalURL) uuid

delete(uuid urlID)

lookup(string shortenedURL) string

Database design

urlID uuid

originalURL string

parsedURL string

createAtTsMs long

High-level design

client: mobile, web

apigateway: auth, service discovery/routing, protocol translation

backend server: implements the actual business logic with the defined api

cache: handle frequent visited urls to prevent hot key. also prevent malicious traffic when visiting non-existing urls.

database: persistent storage layer of storing data

cachine schema

key: parsedURL

value: originalURL

Request flows

illustrated in the diagram

Detailed component design

tinyurl server: it can be autoscaled based on cpu. Also if we consider in-memory cache to handle hot-key issue at the very first place, we might need to consider autoscale on memory as well.

cache(both in memory and distributed): we can start with in-memory cache and if the application is overloaded by memory, we can also go with the distributed cache



Trade offs/Tech choices

it's a key-value storage so NoSQL seems to be a no-brainer, either Dynamo(AWS) or Firestore/Datastore(GCP).

primary key is the uuid based url id. but we do need to secondary index on the parsedURL in order to support to fast lookup.

we might also need to index on originalurl depending on whether we need to dedupe on the original url or not.

Failure scenarios/bottlenecks

DB down, degraded mode, no create but can still support reads

cache is down, needs to be careful since the traffic might also overflow the database. In this circumstances, we might need to load shedding traffic at the api gateway layer

tinyurl server is down, also consider load shedding

Future improvements

in terms of handling negative caching, we can save the volume of storing negative caching entries by using a bloom filter, which adds an additional layer between tiny url server and the cache layer.

Also if we by default use 7 days ttl, we can get rid of database layer and only use cache + SSD/non-SSD hard drive in terms of persisting entries with ttl