System Design of Tiny Url

Why do we need URL shortening

For example, if we shorten this page through TinyURL:

https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600916475904/

We would get:

http://tinyurl.com/jlg8zpc

How to generate Tiny URL

Suppose a tinyURL is 7 characters long and each character can be taken from following 62 alphabets

We can generate 62^7 ( ~= 3.5 trillion) tinyURLs from 62 alphabets having 7 characters length.(除以每天预计生成的条数可以预估url多久枯竭并且根据url长度预估需要的存储空间)

System Design of Tiny Url

根据自增ID 来生成对应的base 62编码url ，这样不会发生collision。如果多机并发顺序生成id 保持同步需要使用分布式锁效率极低。所以考虑使用range counter 对id进行范围切割。

例如：

1 -- 100k ~ 200k

2 -- 200k ~ 300k

n -- ...

使用zookeeper来实现range counter，因为zookeeper 作为nosql 具有最终一致性高可用性以及高可扩展性。

当webserver要生成url时先访问缓存如果没有命中，且本地没有range或者range枯竭向zk申请range 将转换结果同步到persistence and cache。如果服务器宕机则擦除zk中对应的range。

System Design of Tiny Url