System Design - TinyUrl

Seite 1

TinyUrl:

Why TinyUrl?

Easy for users to share links. Eg:Twitter , bcoz it has character limit.

Requirements and goals of the system

Functional

It should shorten

Should redirect

Expiration - option

Alias for user - option

Non Functional

Highly available

Not be able to guess. Clean hasing

Latency less - real time.

Extended reqs

Analytics - count of redirection

REST Api

Capacity Estimates

Traffic - It will be read heavy. Read/Write ratio around 100:1

So for 500 Mil URL shortening, we have 200 URLs/sec write and 20k read

Storage:

For 500 million with each 500 bytes for 5 years it is 15TB

Bandwidth

So for 200 urls/sec and 500 bytes it is around 100 kb/s for write

10 mb/s for read

Memory

If we store data with 80/20 rule, ie store 20% data of read it will be 20k * 24 * 3600 ie around 1.7 Billion

20% of 1.7 Bill request mulitplied by size ie 500 is around 170 GB.

System APIs

createUrl(api_key, original_url, alias = None, expiration = None)

delete(api_key, url_key(shortened)). Limit api_key/ user. Stop abuse

Database Design

A few observations about nature of the data we are going to store:

We need to store billions of records.

Each object we are going to store is small (less than 1K).

There are no relationships between records, except if we want to store which user created what URL.

Our service is read-heavy.

If we choose NoSQL, we cannot store UserID in the URL table (as there are no foreign keys in NoSQL), for that we would need a third table which will store the mapping between URL and the user.

Basic System Design and Algo

Encode32 or 64.

MD5 or SHA256 hashing

Unique ur (if duplicate urls sequenced overflow by appending userid or random key

key value for short and actual using keys db

6 character key into 64^6 ie 412 gb

key concurrency ( lock key )

single point of failure, have multiple copies of keys

Data Partitioning and Sharding

Hash based - cotent hasing

Range based - hashing

Cache replication

LRU - if miss update cache servers with new data

Load Balancers

Between Clients and Application servers

Between Application Servers and database servers

Between Application Servers and Cache servers

Purgin DB

Lazy clean up

Delete when user accesses the expired URL. See diagram`

Telemetry

Have details regarding count, country, location etc

Security and Permissions

Permisson db with key as hash(generated key) and value as URL.