Design a system to take user-provided URLs and transform them to a shortened URLs that redirect back to original.

Questions:

1. How many URLs shall we keep?

2. Read > Write ?

Solution:

1. URL encoding:

URL --> (a...zA..Z0..9-_) 65^n URLs.

hash: md5 etc.

How to resolve collision?

2. Cache:

KEY-VALUE

LFU or LRU: LFU is better, Frequency

Multi Cache Servers

• Sharding: hash(URL) % N
• Standby: *n

ZooKeeper

3. Reliability:

• Replica: Cross region, master slave
• Recovery: master: checkpoints, slave: recreate, meta data
• Consistency

4. Rate limit

Block user when requests more than 10/min or 100/hour or 1000/day ...

one bucket every one minute

Memcache

    key: 1400_op_username

    value: counter

Design Tiny URL