System Design of Tiny Url

朱雀 2021-11-09 14:02 402阅读 0赞

Why do we need URL shortening

For example, if we shorten this page through TinyURL:

> [https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600916475904/][https_www.educative.io_collection_page_5668639101419520_5649050225344512_5668600916475904]

We would get:

> [http://tinyurl.com/jlg8zpc][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

*  a-z = 26
 *  A-Z = 26
 *  0-9 = 10

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

## **System Design** ##

![498881-20190724182641775-469570081.png][]

# #

## Detail ##

根据自增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。

![498881-20190724183753742-1046519381.png][]

reference：[https://www.youtube.com/watch?v=JQDHz72OA3c&list=LLzFCWqxDhIffTUi1VOx2iqw&index=6&t=0s][https_www.youtube.com_watch_v_JQDHz72OA3c_list_LLzFCWqxDhIffTUi1VOx2iqw_index_6_t_0s]

转载于:https://www.cnblogs.com/lnas01/p/11240031.html

[https_www.educative.io_collection_page_5668639101419520_5649050225344512_5668600916475904]: https://www.educative.io/collection/page/5668639101419520/5649050225344512/5668600916475904/
[http_tinyurl.com_jlg8zpc]: http://tinyurl.com/jlg8zpc
[498881-20190724182641775-469570081.png]: /images/20211109/eb60675f14cd418dbebc1ae2ee809961.png
[498881-20190724183753742-1046519381.png]: /images/20211109/9f2a5448cd874aaaabcb50667642bde3.png
[https_www.youtube.com_watch_v_JQDHz72OA3c_list_LLzFCWqxDhIffTUi1VOx2iqw_index_6_t_0s]: https://www.youtube.com/watch?v=JQDHz72OA3c&list=LLzFCWqxDhIffTUi1VOx2iqw&index=6&t=0s